Picasso
We propose a novel framework, called Picasso (PredICtive cAching framework for faSt temporal StOrage), for increasing the performance of hardware and software storage solutions for very large temporal data sets. Our algorithms use temporal models to predict the access to temporal data which can lead to drastic reduction in cost. The decreased cost of storing and accessing temporal data will benefit both enterprise and scientific applications and provide for more efficient data-mining and time series analysis.
In 2009 alone the SIX Swiss Exchange executed more than 30 million security trades (http://bit.ly/bYm61T). Most of the data generated by these trades is temporal in nature and is stored in time-series (ordered sets of timestamp/value pairs). The Swiss stock-exchange example is miniscule compared to all temporal data generated by science, engineering, finance, and the Internet in general (consider the dominance of time-series in biology, climatology, structure analysis, etc.). Even the data stored by the popular web-service Twitter (http://twitter.com), can be considered as temporal.
Today, temporal data is rarely differentiated and treated specially, and if they are, solutions are ad-hoc, not proven optimal, and infrastructure specific. Often temporal data are stored in relational databases with significant space overhead (a time-series stored in Sybase, for example, used to occupy roughly 100 times more space compared to a naïve, binary, non-compressed representation of the same data). Even when properly organized and indexed, businesses lose hundreds of millions of dollars while waiting their traditional storage and database facilities to access and manipulate these data. Only a few months ago, Twitter run into the world headlines by experiencing network/capacity problems (http://bit.ly/d5acoY).
We propose a radically new approach that can change the way temporal data is handled. We call our proposed framework Picasso (PredICtive cAching framework for faSt temporal StOrage). Picasso has the potential of decreasing the access time to time-series and increasing the throughput of temporal data at least several orders-of-magnitude and beyond what is theoretically possible with existing storage, indexing, and caching schemes. To do that, Picasso borrows techniques from Artificial Intelligence (AI) modeling, temporal reasoning, and statistics. The main idea behind Picasso is to use predictive caching in a data storage solution specialized for temporal data/time-series.
The idea of Picasso is very simple. In many environments batch processes (derivation of data, indexing, etc.) account for a significant portion of the overall I/O load. These batch processes are fully predictable (known in advance) and repetitive. Our idea is to design a simple modeling language for describing the use of such back-end processes. The emphasis in this Picasso data access modeling language is temporal (i.e., frequency of data access, duration, etc.) but we also plan facilities for representing spatial access patterns (i.e., if time series X is read at time T, then, with high probability, time series Y is read at time T + 1). Based on this model, we can implement a scheduler that will predict the data use and fetch it in faster memory. The above modeling is sufficient for production, but during the design of the Picasso storage solution (recall that a temporal storage is a combination of hardware, software, network elements, APIs, etc) we plan to use additional modeling and statistical techniques.
Picasso is a highly relevant and practical project as indicated by the initial group of users who have expressed interest in the idea of predictive temporal storage. At the time of writing of this proposal we have received an expressed interest from the Financial Markets division of ING Group NV, Amsterdam. The ING group is a well-known global financial conglomerate of Dutch origin, offering banking, investments, life insurance and retirement services to over 85 million private, corporate and institutional customers in more than 40 countries from Europe, North and Latin America, Asia and Australia. The amount of temporal data used by ING is terabytes of data in hundreds of thousands of time series, used for trading strategy analyses, Value at Risk analyses etc.
High-Throughput Localization for Mobile Robots
In this project, we propose to capitalize on the research and know-how on Ultra Wide Band Technology as well as multi-robot distributed search and localization techniques acquired in previous MICS phases. The goal is to build a system that allows a team of mobile robots to locate themselves and other robots with high precision (order of a cm) very frequently (maybe once per second) and securely, in order to perform collaborative , such as distributed search, coverage, or mapping. We assume that the environment forbids the use of GPS (typically because it is indoors). The project will focus on distributed algorithms that can be efficiently implemented and on development of low power implementations on integrated circuits.
In a first phase, the mobile robots would be equipped with UWB impulse radio transmitters, and fixed, wall mounted UWB base stations are equipped with UWB receivers. This is optimal in a first phase as UWB senders are considerably simpler than receivers. The mobile robots transmit non coordinated trains of impulses, which are coded using cryptographic time hopping sequences unique to each robot. The base stations process the aggregate trains of impulses, recognize the signatures of all robots, and compute ranging information. Both robots and base stations are also equipped with standard communication channels used in mobile robotics (802.11, ZigBee or Bluetooth) for robot-to-robot and robot-to-base station communication.
In this phase we will apply robust ranging and detection techniques that were developed in MICS phase 2 and elsewhere to the problem of detection of one user among N. A detailed implementation will be analyzed with Matlab to validate the range of SNRs and density of nodes over which such an approach is feasible. On the base station side, we will also investigate emerging algorithms based on compressive sensing, as alternatives to the more classical maximum likelihood estimation methods. On the sender side, we will focus on developing low cost, low power specialized emitter and will implement a prototype with an integrated circuit. With the results of the first phase, the base station is passive from a radio viewpoint. While this has advantages of its own (stealthiness), it does not allow secure ranging as a two way channel is required for existing protocols.
Very Low radiated Power UWB Communication
Research and prototype of mobile ad-hoc senders and receivers that radiate very little power (order of μWatts), using Ultra-Wide Band (UWB) transmission technology. Rationales for the proposed project and state of the art UWB Communication. UWB is characterized by an extremely broad use of the radio spectrum which makes it relatively robust against channel impairments such as multipath fading. The primary characteristic of Ultra Wide Band (UWB) communication is that the power spectral density of the envisaged signaling strategy is extremely wideband (on the order of GHz in the 3.1-10.6 GHz band) and very low (on the order of thermal noise for a receiver beyond a distance of 5 meters from its correspondent transmitter). The latter is due to the strong limitation on the average emission level (-41 dBm/MHz) to limit the interference with the multitude of systems using regulated and unregulated spectrum in common with future UWB systems. The most common UWB transmission waveform is based on transmitting information through the use of short-term impulses, whose positions are modulated by a binary information source. This if often referred to as impulse radio. Impulse radio is a promising candidate for military imaging systems as well as other non-commercial sensor network applications because of its robustness to interference from signals (potentially from other non-UWB systems) occupying the same bandwidth. Impulse implementation simplicity and low-power consumption are also often cited as characteristics of impulse radio, although these have yet to be demonstrated in practical systems. Standards proposals for indoor Wireless Personal area Networks (WPAN) in the 3-5 GHz band (802.15.3) and for short-range sensors (802.15.4) are also considering this type of transmission scheme as an alternative to more classical signaling waveforms. In addition to Impulse Radio, FM UWB appears as an alternative that avoids pulse synchronization and low duty cycles while exhibiting low spectral roll-off and low power consumption. It may play a complementary role in low-power, low data rate (LDR) applications.
Dustbot
The DustBot project is aimed at designing, developing, testing and demonstrating a system for improving the management of urban hygiene based on a network of autonomous and cooperating robots, embedded in an Ambient Intelligence infrastructure. The robots will be able to operate in partially unstructured environments (such as squares, streets, parks, etc.) and to vacuum-clean them from rubbish and dirt. They will be able to transport small quantities of home garbage, collected on demand from citizens, at their doors. By using preloaded information on the environment (e.g. area maps) and inputs from on-board and external sensory systems, and by taking advantage of the benefits provided by the Ambient Intelligence platform, the robots will be able to move with a proper (and selectable) level of autonomy to carry out their tasks. The robots will be also equipped with multiple sensors for the monitoring of atmospheric pollutants (e.g. nitrogen oxides –NOx-, sulphur oxides –SOx-, ozone -O3-, benzene, COx, etc.), giving information on the environmental quality in real time. Robots will work as mobile stations, which will monitor pollutants levels in highly populated areas (e.g. pedestrian, central areas).
Acquired data will be also transferred onto dedicated databases by utilizing the features of the ubiquitous communications network. The robots and sensors will be part of an Ambient Intelligence platform, which will integrate not only sensors and tools for monitoring the environment and robot tasks execution, but also communications backhaul systems during clean up/emergency operations, databases technologies, knowledge discovery in databases (KDD) processes for extracting and increasing knowledge on urban hygiene management. Following the computation on stored data, feedback will be sent back to human actors (supervisors, decision makers, like municipality managers, etc.) and/or robotic operators, in order to perform actions. Web page of the project: www.dustbot.org
Pervasive Ultra-wideband Low Spectral Energy Radio Systems Phase II
The PULSERS (Pervasive Ultra-wideband Low Spectral Energy Radio Systems) project aims at exploration of the enormous potential of the innovative and disruptive radio technology embodied in Ultra-Wideband (UWB) and at enabling introduction of new services, applications and devices based on this technology.
PULSERS Main Objectives:
The Key objective of PULSERS is to provide significant contributions in the area of R&D related to UWB-Radio Technology (UWB-RT) with the ulti- mate goal of providing benefits to human, inter-machine and mixed communication needs. Bringing together experts on the topic from various European countries and cooperating with important UWB players from Asia, the PULSERS R&D organisations coming from key industrial and academic communities have the necessary critical mass to strongly advance the state-of-the-art and further the deployment of UWB-RT in Europe and world-wide.
PULSERS aims at realising the following major objectives:
- Materialise consolidated user application scenarios
- Provide UWB system solution verification platforms
- Perform interference and coexistence investigations
- Continue providing significant influence on regulation and standardisation on European and world wide level - Further development and verification of key technologies - Provide advanced technologies enabling large scale UWB exploitation
Technical Approach
The R&D work is system and integration rather than basic technology research oriented. The approach taken in Phase II is to leverage and build upon the investigations performed in the previous phase (2004 – 2005), maturing and realising the UWB physical layer (PHY), media access control (MAC), and system concepts developed. The research activities are considered within a system context, inherently leading to the development of comprehensive UWB-RT system solutions that are able to peaceful coexist and interoperate. The work on Low Data Rate Location racking (LDR-LT) and Very High Data Rate (VHDR) PHY will be aimed at significantly more ambitious performance targets than the current mainstream industrial developments. These goals can only be attained using a cross layer system view, and combining the benefits of innovative solutions on all layers. Specific investigations of the PHY for LDR-LT, and VHDR UWB-RT applications will be continued as well. PHY and MAC schemes will be investigated and implemented that go beyond the previous work within PULSERS and well beyond the work in major UWB standardisation efforts, as for example the IEEE working groups 802.15.3a and 802.15.4a. The project will take into account new regulatory constraints imposed by Europe’s upcoming UWB deployment rules being different from FCC rules (influenced by previous PULSERS activities in this field).
PULSERS R&D work on MAC and higher OSI layers for key UWB-RT applications scenarios is given a strong focus in Phase II. Work on these aspects across the layers will have a strong emphasis on system component integration, prototyping, and laboratory experimentation, on the basis of an industry driven commitment to complete system implementation and sophisticated system verification. The emphasis will be on system test beds that build on LDR-LT and VHDR base technologies. At the end of PULSERS Phase II comprehensive system verification platforms will be integrated, covering all OSI layers. A selection of key application scenarios will be verified in realistic environments through these platforms. The PHY will be based on UWB technology, while the applications will support enhanced connectivity, convenience, and increased efficiency for the user. The system demonstrators will allow exploration of selected LDR-LT applications, as well as some aspects of VHDR providing wireless digital visual interface (DVI). Application areas of particular interest include sensor networks for industrial application, control, and building automation, localisation and tracking solutions, multimedia applications for body area networks, and private home applications such as fast download of multimedia content into fixed, portable and mobile appliances (VHDR data transfer). In parallel to the main realisation tasks, PULSERS Phase II members continue to pursue advanced research topics in the area of distributed and colocated multiple antenna systems (MAS). Further a significant effort is still necessary to contribute in the crucially important activities on spectrum regulation and PHY/MAC standardisation, both at the European and world-wide level.
Key Issues
PULSERS ambitious targets may be summarized as i) R&D on UWB-RT technology, a challenging task in LDR-LT and VHDR, ii) use scenario and business case evaluation, system concept development and integrated system definition inclusive the verification platform implementation iii) contribution to regulation and standardisation targeting to set pre-conditions for harmonised and viable (from technical and economical point of view) legal and technical framework enabling the use if UWB-RT and thus starting a new era of locally spatial efficient spectrum (re) use. Selected high level project’s systems and technology targets to be achieved are:
- Wireless networking, where application and network management are supported by precise and up-to-date location information;
- Satisfy increasing demand for short range very high data rate wireless data transmission for computer and consumer electronics industry applications
- Availability of truly low power and low cost UWB-RT, which offers inherently significant benefits compared to state-of-the-art short- range wireless technologies
- Wireless systems based on UWB- RT coexisting with existing wireless systems and services applying principle of under laying spectrum use.
Expected Impact
The project members provide contributions to the Regulation and Standardisation as well as to the implementation of EC policies, especially concerning the Directive 1999/5/EC (the R&TTE Directive). PULSERS members are essential participants in the European regulation and standardisation process providing scientific excellence as well as significant practical support. UWB technology in general applies a novel approach of spectrum use (under laying spectrum use as secondary radio service) enabling reuse of the radio spectrum locally, following the principles of peaceful coexistence with other existing legal radio systems and this way massively increasing the spatial capacity. The project members actively contribute towards “a consolidated European approach regarding the spectrum requirements (terrestrial and satellites) in the evolution beyond 3G and a clear European understanding of the novel ways of optimising spectrum usage when moving beyond 3G.” More information can be found at http://www.pulsers.eu
HCF-Lite
La popularité des réseaux locaux radio (WLAN) est de plus en plus croissante. Le WLAN doit sa popularité croissante à l’avancement et à la maturité du standard IEEE 802.11b. Suite à la réussite du déploiement des réseaux 802.11b, ses concepteurs ont prouvé sa capacité d’offrir les services de transfert de données (i.e., data services) d’une façon simple, flexible et économique. Cette technologie, offre une mobilité et une connexion permanente à l’Internet dans les environnements de travail, les hopitaux, les campus universitaires, les usines, les aéroports et les marchés financiers.
Simultanément, les utilisateurs du WLAN ont commencé à s’intéresser à l’utilisation de leurs PC portables et agenda électroniques (i.e., PDA) pour le support d’applications multimédias à haut débit. Ces applications incluent, entre autres, la video/audio-streaming, la collaboration interactive, la videoconferencing, et la messagerie multimédia. Cependant, ces applications nécessitent une certaine qualité de service (QoS), par exemple, la garantie de la bande passante, du délai, de la gigue et du taux de perte.
Ainsi, dans le but de supporter des services de transmission du trafic multimédia, les concepteurs du 802.11 avaient lancé l’initiative de la spécification d’un nouveau standard, le 802.11e . Cette initiative de standardisation, couvre à la fois les environnements résidentiels (i.e., home environments) ainsi que commercials et se veut compatible avec les standards existants tels que 802.11b,a. Le groupe de travail 802.11 TGe (Task Group e) proposa, en novembre 2001, un document de base, le 802.11e draft, pour le support de la QoS dans le WLAN. Le draft 802.11e spécifie deux méthodes d’accès (MAC- Medium Access Control) génériques au canal radio, EDCF et HCF. EDCF (Enhanced Distributed Coordination Function) représente une fonction d’accès basée sur la définition des priorités pour offrir une certaine différentiation de service. Cette méthode d’accès est en cours d’évaluation dans le cadre du projet CCTI-QOS et son implémentation est également prévue. La méthode HCF (Hybrid Coordination Function) s’appui sur EDCF et définit une alternance de deux périodes opératoires, CFP (Contention free period) et CP (Contenton Period). Durant le mode opératoire CFP l’envoi de paquets est coordonné par une entité centrale (au sein de la station de base), ce qui permet de mieux traiter les flux à temps critique des applications multimédias.
Cependant, après plus de deux ans de travail, la proposition 802.11e n’a pas reçu un soutien suffisant (par les membres du 802.11e) pour sa standardisation. Nombreuses entreprises, e.g., opérateurs, constructeurs télécoms, et fournisseurs de services haut débit, continuent à attendre avec impatience la publication du standard 802.11e. Parmi les raisons majeures du retard de la standardisation, on cite :
- la complexité inhérente aux mécanismes de qualité de service conçus,
- les divergences des besoins du marché (priorité d’implémentation pour les services data, voice, ou audio visual),
- différentes approches et points de vue sur l’implémentation des mécanismes (i.e., HCF) considérés obligatoires par les uns et optionnels par les autres,
- introduction continue de nouveaux concepts de QoS et
- expansion continue des nouveaux membres.
Devant le risque d’un tel retard du 802.11e et ainsi l’émergence d’un standard de facto à l’extérieur de l’IEEE, un consensus d’une proposition finale (consensus proposal) à été, récemment (janvier 2003), soutenue par les membres du TGe. Cette dernière proposition (de consensus) simplifie la proposition 802.11e initiale.
Dans ce contexte, nous nous proposons à travers le projet HCF-Lite, d’implémenter et d’évaluer la performance des mécanismes de garantie de la QoS, i.e., HCF, dans un environnement de test réel. Ceci pourra contribuer à la maturité et l’essor, tant attendu, du standard 802.11e. D'un autre coté, le succès des futurs services multimédias mobiles sur WLAN (e.g., proposition CCTI-PDA avec VoIP et media streaming) passent nécessairement par une phase d'expérimentation et de validation sur une plate-forme supportant la qualité de service qu'il est indispensable de mettre à disposition.
Nous voyons que dans cette perspective, nous avons besoin de valider et de mettre en œuvre dans un environnement de développement les concepts de QoS définis dans le draft de consensus 802.11e et aussi les étendre par ceux en cours d’analyse et de conception dans le projet CCTI-QOS .
Actuellement, sur le marché, les produits (AP et cartes d’accès) supportant la QoS sur WLAN se font très rares et s’ils existent, implémentent des mécanismes propriétaires. En plus, le mode d’accès HCF que nous nous proposons d’implémenter et d’évaluer s’inscrit au cœur de la garantie de service sur le canal radio dans les réseaux WLAN.
Les utilisateurs WLAN demandent de plus en plus l’utilisation de plusieurs variantes d’applications multimédias,e.g., téléphonie sur IP, applications audio visuels, caractérisées par différents types de trafic, i.e., CBR et VBR. Ces applications nécessitent la garantie de la QoS, pour leur déploiement efficace et une expérience réussie pour l’utilisateur. Tout retard, d’une implémentation de la QoS sur WLAN pénalisera le déploiement attendu de ces services multimédias mobiles à valeur ajoutée.
Quality of Service in IEEE 802.11 WLANs
Overview
The proposed IEEE 802.11e draft standard defines new MAC protocols for QoS in wireless networks, mainly HCF and EDCF. EDCF is a contention-based channel access scheme and is part of HCF for infrastructure networks and may be used as a separate coordination function for wireless ad-hoc networks. Throughout the project, we have proposed to extend EDCF with a dynamic adaptation algorithm of the minimum contention window (CWmin) that enables each station to tune the size of the CWmin (the same approach is also applied for CWmax) used in its back-off algorithm at run time. The purpose of our scheme is to reduce delay and jitter and increase the efficiency of the transmission channel. Priorities between access categories are provisioned by tuning the size of the CWmin according to application requirements and channel conditions. The performances of the IEEE 802.11e EDCF, enhanced with our adaptation algorithm, are extensively investigated by simulations and compared with contention window adaptation schemes especially Slow Decrease (SD) schemes. Results obtained indicate that CWmin adaptation scheme outperforms the 802.11e EDCF standard in terms of channel utilization, throughput, and packet delay. More details about obtained results can be found in project reports research reports
Report - Results
|
