Project : ares
Section: New Results
Keywords : hybrid networks, architecture, auto-organization, MAC, quality of service, energy.
Protocols design
Participants : Isabelle Augé-Blum, Guillaume Chelius, Eric Fleury, Isabelle Guérin Lassous, Jialiang Lu, Nathalie Mitton, Thomas Noël, Fabrice Theoleyre, Tahiry Rafazindralambo, Cheikh Sarr, Fabrice Valois, Thomas Watteyne.
Architectural design
We are still working on ad hoc architecture and we have performed several industrial transfers. Based on the draft of ana6 ( http://www.dfn-pca.de/bibliothek/standards/ietf/none/internet-drafts/draft-chelius-adhoc-ipv6-00.txt), describing an IPv6 Addressing Architecture Support for mobile ad hoc networks, we have developped 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).
In [3], [12], [13] 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. Dealing with issues raised by such hybrid networks and addressing all challenges listed in MANet may require a departure from classical solutions available in the literature. To enable a full multi-hop connectivity without raising problems/inconsistencies regarding IP compatibility, we propose Ana4 (a.k.a. Ananas), a 2.5 layer architecture suitable for hybrid heterogeneous networks. In these articles, we present the architecture and implementations of Ana4 in the context of ad hoc and mesh networks as well as application fields where Ana4 is already used. We also present experimental measurements that show good performances with respect to a full IP solution (IP routing) and similar 2.5 approaches like MPLS.
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.
Last year, we proposed a way to "structure" the network by gathering nodes into groups called "clusters". Such a structure may then allow to apply classical routing schemes inside and between clusters. We studied it analytically and by simulation. This year, based on this structure and its different features, we have proposed different efficient algorithms for several functionalities. First, we have introduced a way to apply an efficient broadcasting scheme over it. This scheme allows either a broadcasting confined in a cluster or in the whole network. It has revealed to outperform existing broadcasting solutions for multi-hop wireless networks regarding energy savings, latency and robustness [41], [14], [15], [16], [35], [55], [61].
Then, we have introduced a way to route messages over this structure according to its special features. Indeed, clustering a network aims to allow a hierarchical routing. In relative works, hierarchical routing means applying a pro-active routing protocol inside clusters and a reactive one between clusters. However, as most of clustering schemes in the literature, our clustering scheme provides a constant number of clusters for an increasing number of nodes. Thus, applying a pro-active routing protocol inside the clusters lead to the same scalability problems than flat architectures. Therefore, we have proposed to apply the reverse approach for hierarchical routing, which means: a reactive routing protocol inside clusters (which would not generate too much latency since cluster radius was proved to be upper bounded by a constant) and a pro-active routing protocol between clusters (as the number of clusters is constant, the size of routing tables is in O(1)).
Nevertheless, this hierarchical routing approach needs a localization protocol to allow nodes to know in which cluster is the node they need to talk to [39]. It is actually an indirect routing. Therefore, we have also introduced a localization scheme which also takes advantage of the characteristics of the underlying cluster structure. It combines scalable advantages of DHT (Distributed Hashed Tables) and Interval Routing. This localization scheme has a time complexity in O(1) and requires a memory size in O(1) on nodes. Thus, globally, our indirect routing requires low memory size (O(1)), has a low time complexity (O(1)) and provides routes with a low stretch factor.
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 complexity analysis for a family of self-stabilizing vertex coloring algorithms 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. Similarly, the height of the induced DAG is much lower than the linear dependency to 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
This work was initiated in February'03 with Fabrice Theoleyre, currently Phd. student in the ARES team. This section deals with self-organization of ad hoc networks through a virtual topology. We consider a virtual topology 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 have investigated the behavior and the key properties of such self-organization. We have also introduced robustness and how to use this work to developp a mesh network in mobile ad hoc network.
In 2005, self-stabilization property was investigated [48]. 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.
Based on this virtual topology as a way to organize a spontaneous networks, the question is: how self-organization paradigms deal with network behavior? More precisely, how routing and location protocols can use the virtual topology we have introduced? A new routing protocol based on this self-organization is proposed (called VSR, Virtual Structure Routing [50], [51]). A proactive routing protocol is used inside the clusters and a reactive routing protocol is used of inter-cluster data request. The inter-cluster routing protocol uses the virtual backbone for route requests. In our proposition, a route between a source and a destination is a list of cluster id rather a list of nodes id. The important stability of the cluster topology provides more stable routes. Performance evaluation of this new self-organized routing protocol was done using OPNET Modeler network simulator. This proposition is compared with AODV (reactive routing protocol), OLSR (pro-active one) and CBRP (hierarchical one). Performances highlight the benefit of using self-organization mechanisms before to use a routing protocol. A similar approach was used to develop a location protocol dedicated for hybrid networks [49].
Currently, we are studying the trade-off between network capacity and self-organization [44]. Testbeds of self-organization protocol are scheduled using the mesh networks of the CITI.
Self-configuration and self-organisation in communicating objects netwokrs
This work is financed and supported by France Telecom R&D under CRE No 46128746 with PACIFIC team. This research project is also the PhD thesis of Jia-Liang Lu.
The goal is to identify the key mechanisms to deploy communicating objects networks or sensor networks in an autonomous way. So, self-configuration, self-organization and self-healing are the main topics we study. During the first year of this PhD. thesis, a global overview of these topics was done for France Télecom R&D. So, three reports were produced:
Chapter 1: Communicating objects: Taxonomy and Survey
Chapter 2: Survey of Self-configuration: Addressing, Communication and Service
Chapter 3: Survey of Self-organization: Towards an efficient network
Currently, a new approach combining self-configuration and self-organization is studied.
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 [64]. 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.
QoS in ad hoc networks
Evaluation of the BRuIT protocol
This year, we have proposed enhancements and evaluations of BRuIT [22], a bandwidth reservation protocol for ad hoc networks we designed in 2000/2001. BRuIT (Bandwidth Reservation under InTerferences) takes into account influence of distant emitters on medium availability. The goal is to consider the carrier sensing area. Some experiments showed that with IEEE 802.11b interface cards, the carrier sensing area radius is about twice the communication range. Therefore, in the first version of BRuIT, each mobile takes the decision to accept or reject a flow according to the bandwidth used in its one-hop and two-hop neighborhood. But twice the transmission range is not equivalent to two hops. We have evaluated both the average number of undetected jammers, i.e. nodes that are within two times the transmission range but that are not reachable by at most n hops long path for different n values, and over-detected neighbors, i.e. nodes that are reachable in at most n hops but that are not within two times the transmission range. Results show that there is a clear gain from considering one-hop neighborhood to two-hops. The number of undetected neighbors is reduced by about 35 % and the number of over-detected neighbors is null. Increasing n does not result in a significant gain, for example, considering three- hops neighborhood only reduces the number of undetected neighbors by 10 % compared to two-hops while the number of over-detected neighbors reaches 40 % of the total number of considered jammers. Therefore, considering more than two hops makes the evaluation less accurate and that's why BRuIT keeps on considering these informations for resources availability evaluation.
In order to evaluate BRuIT, we have compared it by simulation with AODV a best-effort reactive routing protocol. BRuIT and AODV are similar in the route research process, therefore such a comparison shows the cost of providing guarantees. The simulation results show that this protocol enhances the network usage by not overloading the medium at the cost of longer routes and a larger establishment time. Nevertheless, the load is better balanced in the network, therefore network capacity is not overloaded. This results in more stable routes and less control traffic as almost no reconstructions are needed.
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 [10], [47]. 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 developped 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 constraint
We have initiated a study on the energy consumption in wireless ad hoc 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. More precisely, our work is focused on a specific communication pattern called broadcast, where data are distributed from a source node to each node of the network. Broadcast is a common and frequent process during a sensor network lifetime. It is useful for auto-organization, parameter/data dissemination or control regulation. Conventional energy aware protocols manage the energy consumption by adjusting the transmission power of sensor nodes. 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 work focuses on the determination of minimum-cost (i.e., minimum energy consumption) broadcast and sensing schemes. Our main contribution [23], [7] is to take into account both the transmission and reception costs and to derive analytical bounds to the minimum energy broadcast and minimum energy sensing problems.
We are also investigating the optimal radio range that minimizes the energy globally consummed 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 adaptative algorithm where nodes tune their powers with regard to an on-line evaluation of the local node intensity. This work is based on the previous modelling and analysis of the behavior of multi hop wireless path [54].
Real-time communication in wireless sensor network
This work has started in February 2005 with Thomas Watteyne, who is currently a Phd. student in the ARES team. Our goal is to propose new protocols for real-time communication in wireless sensor networks. Critical applications sometimes 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.
To our knowledge, only few works have so far dealt with hard real-time, where no message can reach its destination late. Only one protocol proposes a hard real-time MAC protocol, but with hard to meet assumptions on the nodes placement and their embedded components (radios need to use multiple frequencies, nodes have to be grouped in hexagonal cells with a router node in the middle...).
Our first results let us define a new MAC protocol [53] 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. Having only a one-dimensional network frees ourselves from routing considerations, in order to focus on the MAC layer. In our protocol, run-time has two modes. Reliable collision-free communication is guaranteed during the run-time protected mode. A second mode, called unprotected mode is used when collisions are not likely. It is prone to collisions but provides a near optimal transmission speed of the alarm messages toward the sink node. After initialization, the network's run-time starts in unprotected mode. In case of collision, the network switches into a protected mode. The sink decides when to switch back to unprotected mode. Our protocol provides both bounded worst case times and good average times thanks to the switching between those two run-time modes.
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). Future work include extending our protocol to three dimensions, thus proposing a hard real-time routing protocol.
