Project : ares

Section: New Results

Keywords : hybrid networks, wireless sensor networks, architecture, auto-organization, MAC, quality of service, energy.

Protocols design

Participants : Isabelle Augé-Blum, Elyes Ben Hamida, Nicolas Boulicault, Guillaume Chelius, Yu Chen, Eric Fleury, Isabelle Guérin Lassous, Karel Heurtefeux, Jialiang Lu, Nathalie Mitton, Thomas Noël, Tahiry Rafazindralambo, Cheikh Sarr, Fabrice Theoleyre, Fabrice Valois, Thomas Watteyne.

Sensor networks

In the last quarter 2005, we launched a new and transversal activity inside the INRIA ARES project on sensor network. The mains goals are to gather the research efforts produce in the various research domains of ARES and to offer a common platform where our team may launch experimentations in situ. Our first work was the design of the node hardware. This one year investment done under the project named Worldsens( http://www.worldsens.net) is now operational and we are able to test and deploy our own sensor applications. Note that this effort is done in a multidisciplinary collaboration, namely with the COMPSYS INRIA project and with the CEGELY laboratory.

In parallel to this hardware design and production, we have also invest in the development of a full integrated platform for the design, development, performance evaluation and profiling of applications for wireless sensor networks. A first main characteristic of Worldsens development platform is that once the design choices have been made, the simulation platform only handles the real application native code in order to test and validate the application at the instruction level. We do not want to impose to developers the task of rewriting their application in a particular description language or to transform low level parts of their code in order to be compliant with our simulation tools. In addition to this, we have designed our Worldsens simulation tools (WSim & WSNet) with respect to the following goals:

• Worldsens captures the behavior of the node application at a very low level, using the native code: instruction level, bit level and interrupt level.

• Worldsens reflects the behavior of the network. At the same time, one may tune the degree of accuracy from an ideal network layer where all transmitted packets are received to a network model taking into account collisions, SNR and radio propagation.

• In order to model the behavior of a global application, Worldsens handles large sensor networks, with hundred to thousand nodes.

• Worldsens handles precise timing in order to get the behavior of interruptions and byte level radio simulation.

In [16] and [17] we present and demonstrate the use of the Worldsens platform in the process of a fast prototyping of wireless sensor network applications & protocols.

In the CAPNET project we propose to deploy large-scale secure ambient dynamic networks so that they can be analyzed and modeled based on data obtained in real-life situations. The several and in situ test beds deployed will be an opportunity to gather large amount of experimental data in order to conduct studies on such ambient dynamics networks. One test bed will be composed of more than 200 sensor nodes, distributed to students at INSA de Lyon, in several departments. We ask them to carry them continuously in order to record not their location, but the interaction that a such dynamic network creates. Moreover, based on the knowledge of the underlying ambient networks, we will be able to deploy and test security mechanisms in order to guarantee the security of the data collected, to design strong privacy aware data gathering and also test the deployment of embedded ambient applications.

In order to setup this large experiments, a preliminary work in the design of the CAPNET application, is the design of the MAC layer and the neighbor discovery protocol. In order to get energy efficient neighbor discovery we choose to adopt a cross layer approach by designing and dimensioning both protocols (MAC & neighbor discovery) together. In [26], we analyze the impact of radio interferences on a discovery protocol. As expected, we prove that, in average a node discovers only a subset of its possible neighbors. We propose an analytical models that allow to compute the average number of neighbor as a function of the transmitting power of nodes and the density of nodes. This model allows to provision a given Hello packet protocol and to optimize it by adding sleeping periods.

Ad Hoc Architectural design

We have a continuous activity on the design of ad hoc architecture (namely an4 and ana6) and our main activity in 2006 was to perform support to our industrial transfers. Based on the draft of ana6. describing an IPv6 Addressing Architecture Support for mobile ad hoc networks and also a IPv4 version that introduces a 2.5 ad hoc layer, we have developed further our view of a global architecture for an ad hoc network. The notion of IPv6 connector introduced allows several network interfaces to be virtualized into a single addressable object. A host may have several ad hoc connectors and an interface may be bound to several ad hoc connectors. The ad hoc connector defines a set of addresses which indistinctly identifies all bounded interfaces. This notion of ad hoc connector is simply implemented in IPv6 by defining a third IPv6 local-use unicast address: ad hoc local addresses. Their validity is restricted to an ad hoc network. They provide a basic identification support for ad hoc nodes that can be extended by other configuration mechanisms such as stateless global address attribution. In the IPv6 architecture scheme, an ad hoc network may be at the same time, a multi-link subnet and a multi-link multi-subnet. Considering the whole ad hoc network as a multi-link subnet is achieved by matching a particular multicast scope, the subnet scope, with the ad hoc network. To support the multi-link multi-subnet vision, the notion of logical ad hoc sub-networks, also called area, is introduced. A area is a connected set of ad hoc connectors sharing a common area value. A specific range of multicast addresses is associated to each area. It enables the restriction of multicast groups to a given area. An implementation of this IPv6 ad hoc framework is now available under FreeBSD via sourceforge ( http://sourceforge.net/projects/anax).

Based on previous work where we we consider the problem of interconnecting several hosts in a spontaneous hybrid and heterogeneous network, i.e. an environment where wired and multi-hop wireless technologies are used we develop tools to monitor and manage such heterogeneous networks. We also enhance our software development of ana4 under Linux and Windows XP. The new version support QoS capabilities at the ad hoc layer (2.5) and allow to grant a privilege on stable wireless connexions or fastest interfaces.

In [18] we address the problem of duplicate address detection in Wireless Ad Hoc Networks. Our method rely on the use of the underlying medium and we do take into account the multicast advantage provided by the wireless medium.

Auto-organization in large scale networks

In order to be able to use ad hoc networks on a very large scale, flat routing protocol (reactive or proactive) is not really suitable. Indeed, both routing approaches become ineffective for large scale wireless ad hoc networks, because of link (flooding of control messages) and processing overhead (routing table computation). One well known solution to this scalability problem is to introduce a hierarchical routing by grouping geographically close nodes to each other in clusters and by using a "hybrid" routing scheme: classically proactive approach inside each cluster and reactive approach between clusters. Such an organization also presents numerous advantages such as more facility to synchronize stations in a group or to attribute new service zones.

We are also conducting works that focus on problems of fault tolerance and scale in distributed system [36], [37] Such systems motivate designs that autonomously recover from transient faults and spontaneous reconfiguration. Self-stabilization provides an elegant solution for recovering from such faults. We present algorithms in order to obtain fast Convergence in Self-stabilizing Wireless Networks. The underlying method is based on a a family of self-stabilizing vertex coloring algorithms and a trick that consist in braking symmetries in the context of wireless networks. Overall, our results show that the actual stabilization time is much smaller than the upper bound provided by previous studies.

In [24], we compare two self-organization and hierarchical routing protocols for ad hoc networks. These two protocols apply the reverse approach from the classical one, since they use a reactive routing protocol inside the clusters and a proactive routing protocol between the clusters. We compare them regarding the cluster organization they provide and the routing that is then performed over it. This study gives an idea of the impact of the use of recursiveness and of the partition of the DHT on self-organization and hierarchical routing in ad hoc networks.

In [37], we present a complexity analysis for a family of self-stabilizing vertex coloring algorithms in the context of multi-hop wireless networks. Such 'coloring' processes are used in several protocols for solving many different issues (clustering, synchronizing...). Overall, our results show that the actual stabilization time is much smaller than the upper bound provided by previous studies. Similarly, the height of the induced DAG is much lower than the linear dependency on the size of the color domain (that was previously announced). Finally, it appears that symmetry breaking tricks traditionally used to expedite stabilization are in fact harmful when used in networks that are not tightly synchronized.

Self-Organization with a virtual topology for hybrid networks

Two approaches of mobile ad hoc networks can be considered: the classical one where the network is viewed as flat and a more recent one where the network is structured through a logical view. In this work, the logical view is associated to a virtual topology: a virtual topology is defined as a hierarchical organization based on both backbone and clusters. The backbone constitutes a spine carrying control traffic, disseminating information in the network. The clusters provide services areas with a leader (the clusterhead). This structure has several major goals:

• To hierarchize the nodes in creating leaders and clients;

• To distribute roles taking into account the natural heterogeneity of hybrid networks;

• To create a logical view above the physical view;

• To introduce stability in a volatile environment.

In the first part of this work (year 2004), we investigated the behavior and the key properties of such self-organization. We have also introduced robustness and how to use this work to develop a mesh network in mobile ad hoc network. In 2005, self-stabilization and analytical properties was investigated. The goal was to demonstrate that it is always possible to provide a virtual topology despite the radio environment and the mobility effect. We have also shown that a local change only implies a local reconstruction on the virtual topology. The main objective was to provide layer 3 protocols taken into account this self-organization. A routing protocol (called VSR, Virtual Structure Routing) was proposed and a mobility management protocol too (SoMoM, )Self-Organized Mobility Management. These works highlighted the benefit provided by the use of a self-organisation. In 2006, intensive performance evaluation studies have been done in order to characterize how a routing protocol based on self-organization is more efficient than the classical flat approach (OLSR, DSR) or the hierarchical one (CBRP). In [62], VSR appears to be a good trade-off between pro-active and reactive protocols.

One another question is: because a self-organisation is based on better nodes which are more solicited for the network, bottlenecks can appear and, thus, the network capacity can decreased. We refer to the network capacity as a flow problem. In [51], an analytical framework to study the capacity in mobile ad hoc networks an hybride one is presented. The input of this model is the network topology, the routes provided by a routing protocol (OLSR for flat networks, VSR for structured one). The output provided upper and lower bounds. The main result is: in case of ad how network, the capacity is not affected by a self-organisation scheme but the capacity decreases strongly in case of hybride network.

Currently, we experiment the self-organisation scheme and the mobility management protocol using the mesh networks of the CITI laboratory. The software is available at http://sourceforge.net/projects/somom. The application is spontaneous extension of wireless networks.

Autonomic mechanisms for wireless sensor networks

This work is financed and supported by France Telecom R&D under CRE No 46128746 with PACIFIC team since November 2004. This research project funded the PhD thesis of Jia-Liang Lu. Mr Lu did his first year of his Ph.D. in the CITI laboratory and the two last year in the ILAB Team, FTRD Beijing, China.

The goal is to provide autonomic mechanisms for wireless sensor networks in order to allow spontaneous deployment without human intervention, without centralized control. We refer to autonomic mechanisms as self-* protocols. Self-* can be associated to self-configuration in order to configure the nodes Id. without human intervention. This mechanism provided also duplicated address detection protocol. Self-* is also associated to self-organisation where we provide a logical view of the network: the topology provided is a connected backbone. This self-organisation can be used for data-dissemination and/or data-aggregation. Finally, self-* also refer to self-healing in order to maintain active the self-organisation scheme. We provide an integrate self-configuration / self-organisation scheme. A patent is associated to this mechanism.

MAC protocols for ad hoc networks

The IEEE 802.11 MAC layer is known for its unfairness behavior in ad hoc networks. Introducing fairness in the 802.11 MAC protocol may lead to a global throughput decrease. It is still a real challenge to design a fair MAC protocol for ad hoc networks that is distributed, topology independent, that relies on no explicit information exchanges and that is efficient, i.e. that achieves a good aggregate throughput.

We have proposed a new MAC protocol based on 802.11, called MadMac, that provides more fairness than 802.11 while maintaining a good aggregated throughput in ad hoc networks [46]. MadMac is based on two main mechanisms. The first mechanisms is: a station divides its throughput by 2 at the MAC layer if it detects an activity from one or more stations. This division is done by introducing a extra waiting time before transmitting a new packet. The second mechanisms tries to fine tune this extra waiting time according to the activity/collision experiences by the station. These mechanisms are only based on information provided by the 802.11 MAC layer and its behavior is not probabilistic.

We have compared MadMac with 802.11 from fairness and efficiency points of view. These comparisons have been carried out in many basic scenarios that are known to lead to fairness issues and in more complex topologies. Results, from these simulations, show that, in most of the cases, MadMac provides a better fairness and maximizes the aggregate throughput when unfairness is solved.

Future works would be to investigate other ad hoc topologies like random topologies, and to propose an analytical evaluation of MadMac in order to make it fairer and efficient.

Solution to the performance anomaly of IEEE 802.11

In the widely used 802.11 standard, the so called performance anomaly is a well known issue. Several works have tried to solve this problem by introducing mechanisms such as packet fragmentation, backoff adaptation, or packet aggregation during a fixed time interval. In [45], we propose a novel approach solving the performance anomaly problem by packet aggregation using a dynamic time interval, which depends on the busy time of the wireless medium. Our solution differs from other proposition in the literature because of this dynamic time interval, which allows increasing fairness, reactivity, and in some cases efficiency. In this work, We propose an analytical evaluation of our protocol in the classical scenario where all stations are within communication range and a detailed simulation-based evaluation. We evaluate our protocol in terms of efficiency and of fairness on many configurations not limited to one hop networks. We also compare our solution to three different approaches that belong to the three main classes of solutions solving the performance anomaly.

QoS in ad hoc networks: evaluation of the available bandwidth

In this work, we try to propose a more accurate mechanism to evaluate the available bandwidth than the one used in the BRuIT protocol. Such an evaluation is necessary to provide an efficient QoS protocol to manage bandwidth in ad hoc networks.

The available or residual bandwith of a link is the maximum throughput that can be injected on a link without degrading the close communications. Therefore, we have proposed a new technique to estimate the available bandwidth to wireless nodes and by extension on one-hop links in IEEE 802.11-based ad hoc networks [59]. Our technique exploits the fact that both sender and emitter can estimate channel occupancy by monitoring their vicinity. It provides a non-intrusive estimation meaning that it does not generate any additional traffic to perform the evaluation. We have also developed a protocol based on this technique which periodically broadcasts node information on it's one hop neighborhood, so the receiver is able to compute its available bandwith with the sender.

We show by simulations that our technique provides an accurate and scalable estimation of the available bandwidth on wireless links in many ad hoc configurations. However, there are some topologies in which this technique does not give accurate estimates mainly due to phenomena like collisions, but we have proposed some improvements to adapt to these constraints.

Energy-efficient cross-layer design for Wireless Sensor Networks

Using cross-layering for energy efficiency

The layered approach has been introduced in traditional wired networks because it clearly separates the different tasks the communication stack needs to perform. This leaves the user the possibility to build his stack, assembling interchangeable layer blocks. Yet, this approach shows to have some drawbacks for Wireless Sensor Networks (WSN). This is mainly attributed to the low-energy nature of the nodes. In a fully layered approach, a given layers has a very abstract view of lower layers, and a situation can arise in which for example the radio module of the radio is constantly on (which is an issue of the physical layer), whereas the node is scheduled in such a way that there is no data to transmit or receive (which is an issue of the MAC layer). Energy is thus lost at the interface between layers.

To alleviate this effect, the concept of cross-layering has been introduced. Using cross-layering, we make layers work together to yield the most energy-efficient solution. Working together can mean increasing the interactions between layers, or merging different layers.

Using preamble-sampling in a cross-layering approach

Approximately 80% of a node's energy is used by the radio module, when this module is on. When the radio module is active, it can be either sending/receiving a message, or idle listening (listening to the medium for a message). In fact, it has been shown that the power consumed for idle listening is very close to the power used for sending/receiving. This means that the only way to reduce power consumption of a node (hence increase the node's lifetime), is to turn off its radio as much as possible.

Preamble sampling is a clever way of turning the node's radio off. Each node chooses its own sleep/wakeup schedule independently of the others and a node transmits a preamble before each data frame which is long enough to make sure that all potential receivers will get their data. According to the duty-cycle parameter, nodes switch periodically their radios on to sample the channel. If a node finds the channel is idle, it goes back to sleep immediately. However, if it detects a preamble transmission on the channel, then it keeps its radio on until it receives the subsequent data frame. After the reception of the data frame, the node sends an ACK frame, if needed, and goes back to sleep afterward. To be effective, preamble transmission needs to be at least as long as the check interval, the period between two consecutive instants of node wakeup. In this way, a node makes sure that all potential receivers are awake during its preamble transmission and they get the subsequent data frame.

We have applied the cross-layering approach to preamble-sampling MAC protocol. We have to take advantage of the low-energy nature of this MAC protocol, i.e. we have to build a routing layer which is tailored to preamble-sampling. With this in mind, we have designed 1hopMAC, a energy-efficient cross-layer MAC/routing protocol.

Energy consumption and neighborhood knowledge

As detailed in the above paragraphs dealing with self-organization, the main problem of a flat routing approach (as opposed to hierarchical), is that nodes needs to keep information about their neighbors. This is done by using hello message: each node broadcasts information about itself which is useful to its neighbors. Each node then builds a neighboring table, based on the received hello messages. In order to adapt to changes in topology (nodes can for example disappear because of battery exhaustion), this local broadcast needs to be done periodically. This simple proactive approach is very energy-inefficient, as information is constantly exchanged even if no useful information is brought into the network. We thus have adopted a reactive approach, in which a node learns about its neighborhood only when needed, having close to zero consumption when no useful information has to be exchanged.

The 1hopMAC protocol

We consider each node knows its geographical position, and the position of the destination node. Each node can does calculate its distance to destination. We will can this distance the metric of the node. A straightforward way to route a message from a given node to destination is to send it to the neighbor node with smallest metric (i.e. the one closest to destination). Using this simple flat routing algorithm, the message eventually reaches destination, in a multi-hop way. Nevertheless, nodes have to know there neighbors' positions. As explained before, this also involves some neighborhood knowledge. To be energy-efficient, we build this knowledge in a reactive way, and this is precisely what 1hopMAC does.

Without useful traffic, 1hopMAC behaves exactly like preamble sampling. Only when there is some information to transmit – generated or relayed by the node – it exits the preamble mode. The current node performs a sort of 3-way handshake: (1) it broadcasts a request message (2) each neighbor node hears that message and answers with a backoff time proportional to its metric and (3) the node sends the data to the node which answers first. After this, it resumes it's preamble sampling mode.

Changing the metric of the node for robustness

We have furthermore studies geographical routing techniques which guarantee delivery. Indeed, the simple greedy approach can fail. By changing the metric a node contains, we obtain an energy-efficient MAC/routing protocol for Wireless Sensor Networks which guarantees delivery.

Current and Future work

We are currently implementing 1hopMAC on GTSNetS, a network simulation developed at Georgia Tech, Atlanta, USA. The next step is to study the occurencies collisions with GTSNetS. As future work, we would like to port our solution from geographical routing to gradient based routing, in which a common destination node flood the network with a message so that each node knows it's distance to that destination. Routing can then be done by following the inverse path of that initialization message. With our protocol implemented in GTSNetS, we will be able to compare it with existing MAC protocols (e.g. IEEE 802.11), especially from a energy consumption point of view.

Energy constraint

We have pursued our studies on the energy consumption in wireless ad hoc and sensor networks. There has been an increased awareness of energy efficient protocols need for battery-powered devices in recent years. Though the optimization of the sensor network lifetime must take place at each stage, we focus mainly on the sensing and communication levels. Indeed, data transmission and reception using a wireless medium appears to be a highly energy consuming process. Nodes are assumed to adapt their transmission power to the minimum required to sustain communication.

In classical energy model, the amount of energy required to transmit data is proportional to the number of emitted bits and depends on both the communication range and the distance power gradient. Note that regarding this model, reception of a message is not a low cost operation and can not be neglected in comparison to the transmission cost. Indeed, the amount of energy needed for a reception is of the same order of magnitude as the one needed for transmission and is also proportional to the number of received bits. In consequence, as opposed to all the existing work done, energy aware protocols should not only try to reduce communication ranges but should also minimize the number of transmission and reception operations for each message. Our new work focuses on the determination of minimum-cost (i.e., minimum energy consumption) routing. Our main contribution [15] investigate the optimal radio range that minimizes the energy globally consumed by a geographical routing process. In a first step, we consider a common radio range for all nodes. In a second step, we derive a distributed algorithm which attributes variable radio ranges to the sensor nodes. Considering a geographical greedy routing protocol and a uniform distribution of nodes in the network area, we analytically evaluate the energy cost of a multi-hop communication. This cost evaluation corresponds to the asymptotic behavior of the routing protocol and turns out to be very accurate with regard to the results obtained by simulations. We show that this cost is function of the node intensity and we use this result to deduce the optimal radio range. We evaluate this range considering two energy consumption models, the first one considering the energy consumed by transmission operations only and the second one considering both transmission and reception operations. These results can be used in two ways. First, the range of the nodes can be tuned in advance as a function of the expected intensity of nodes during an off-line planning. Second, we propose an adaptive algorithm where nodes tune their powers with regard to an on-line evaluation of the local node intensity.

Real-time communication in wireless sensor network

The goal of this work is to propose new protocols for real-time communication in wireless sensor networks. Critical applications need to know guarantee and bounded response times after detecting a given event. For those applications, the underlying communication network needs to guarantee a given quality of service, mainly in terms of transmission delays and fault tolerance.

Our first results let us define a new MAC protocol [65] which guarantees timeliness constraints in the Worst Case, for a one dimensional wireless sensor network. Application examples include highway car accident monitoring, production chain surveillance, and railway train tracking. Our current work focuses on comparing our real-time protocol's performances with other more classical protocol's (where in case of collision alarms are retransmitted after a random waiting time), and extending our protocol to three dimensions, by proposing a hard real-time cross-layer protocol.