Introduction
Nowadays, there is a vast interest of the scientific community for Wireless Sensor Networks (WSNs). Such networks have a wide scope of applications, like battlefield surveillance, health-care applications or environment monitoring. Protocols for WSNs are inherently distributed. Indeed, the nodes are spatially deployed on some area and two nodes can communicate if they are in the radio range of each other. Moreover, nodes are autonomous: they have no a priori global knowledge of the network and take their decisions asynchronously and based on their own local memory, which is not shared with any other node. The computation a node can perform is therefore limited by its local knowledge of the network.
WSNs are large-scale and can be deployed in many kind of area. Consequently, it is usually assumed that their topology is arbitrary. Furthermore, nodes can be added or removed on the fly or can run out of energy, so we cannot assume global knowledge on the network such as an upper bound on the number of nodes. Due to large-scale, human intervention cannot be envisioned to recharge the batteries in WSNs. Hence, maximizing the lifetime of the whole network is a crucial issue in WSNs. The dedicated protocols have to be energy-saving, for example by limiting the exchange of data.
Therefore, WSNs are large-scale, have time-evolving topology, error-prone (e.g., message losses, crashes), while being limited in terms of memory, computation power and battery supply. Classical solutions for wired networks are not suitable for WSNs and designers have to propose appropriate solutions. For example, new routing protocols have been developed. Nevertheless, in most cases, these solutions are validated by numerical simulations on particular networks or particular scheduling of actions. Our goal is to analytically prove general results on certain routing protocols for WSNs suggested by numerical simulations.
Context
The main focus of Project Terra is to analyze distributed algorithms that handle topological changes in large-scale WSNs. We focus on algorithms dedicated to WSNs mainly for the network and upper layers, namely, routing.
Routing protocols allow nodes to exchange data in multi-hop networks. Routing protocols can be all-to-all: every node is able to communicate with all nodes. They can also be all-to-one: a node is distinguished as the sink and all other nodes, called source nodes, must be able to transmit data to the sink on request or according to a schedule. Typically, in WSNs, source nodes are sensors and the sink is a base station that is linked to another network, like a gateway. Numerous techniques have been proposed to solve routing in WSNs. Flooding [1] is a classical all-to-all mechanism to route messages over a network: every message is iteratively broadcasted from nodes to all their neighbors until reaching the destination or a pre-defined maximum number of hops. Overlay-based protocols use a distributed underlying infrastructure in the network, such as a spanning tree [2], [3] or a clustering [4], [5]. Gradient based protocols [6], [7] provide all-to-one communication. Geographic routing protocols [8], [9] use geographic node position to find and forward messages toward the destination.
Probabilistic algorithms are well suited for networks with restricted amount of resources such as WSNs. For example, routing can be performed using random walks: until the message reaches the final destination, the next hop is randomly selected among the neighbors of the current node. Random walks allow the routing of messages using small data packets without control packets. They are well-suited for WSNs because they use neither any underlying infrastructure, nor any global knowledge on the network. Yamashita et al [10] use non-uniform probabilities to choose the next destination of the message improves the hitting time, i.e., the expected number of hops to reach some node (in our context, the sink).
Tabu lists are typical algorithmic objects which are used to solve combinatorial optimization problems such as the traveling salesman problem [11]. In optimization problems, information are stored in the tabu list to prevent the algorithm from considering the same solution several times. The tabu list is of bounded size, hence the solution depends on both insert and removal policies of the tabu list. In a preliminary work [12], we already investigated the use of tabu lists to enhance the routing with random walks. This technique is self-adaptive, consequently relevant for dynamic networks and efficient in terms of resource consumption. The target application of our paper was all-to-one routing in WSNs. Our goal was to reduce the number of hops to reach the sink without compromising other advantages of random walks, in particular the small length of their messages. Our solutions allow then to efficiently route message in WSNs. Moreover, in [13], we mixed probabilistic methods with overlay-based algorithms to obtain routing protocols that efficiently handle few topological changes.
Goals
Project Terra is devoted to the analytic evaluation of distributed protocols dedicated to WSNs.
Due to the characteristics of WSNs, those solutions must be resilient to topological changes. As mentioned above, new routing protocols have recently been developed at Verimag. Numerical simulations suggest that they are time-efficient, resource-efficient and inherently self-adaptive. Nowadays, those facts must be formally enunciated, then proved. This implies to be able to analytically evaluate the quality of the protocols based on the quantity of resources involved, the average computation time, but also, some new concepts such as the resiliency of the protocols against topological changes. This lead us to define a relevant metric to quantify this information and the models for topological change. Consequently, the Project Terra aims at providing new relevant complexity metrics for the efficiency of the algorithms dedicated to WSNs.
As a first step, the algorithms will be compared to each others: we will exhibit some classes of networks for which a given protocol is better than other solutions. Secondly, some analytical characterizations of the algorithms will be studied, providing worst and average case bounds on the metrics. For example, we would like to exhibit some typically worst-case topologies, for a given algorithm, and prove the theoretical bounds relative to these topologies. Finally, we will propose a method to analyze the behavior of such distributed algorithms based on continuous time Markov chain. The hitting time will be estimated using coupling techniques or "electrical network properties" of the random walk and performance bounds are derived providing hints for the system dimensioning [14].
Related projects
People involved
- Karine Altisen (Synchrone Verimag)
- Stéphane Devismes (Synchrone Verimag)
- Antoine Gerbaud (DCS Verimag)
- Pascal Lafourcade(DCS Verimag)
- Jean-Marc Vincent (Mescal Lig/Inria)
Meetings
All meetings take place at Verimag.
- August 23: Kickoff meeting;
- September 7: Introduction to Markov chains, part 1;
- September 14: Introduction to Markov chains, part 2;
- September 28: Hitting times for some Markov chains;
- October 04: Decomposition of Markov chains;
- October 05: Reversible Markov chains;
- October 18: Upper bounds on hitting times for simple random walks on finite graphs;
- October 25: Extremal graphs for hitting times;
- October 27: Electrical proof of Polya’s Theorem;
- Decembre 5: Percolation;
- Decembre 12: Proof of Harris-Kesten’s Theorem on percolation;
- January 27: Urn processes;
- February 13: Reinforced random walk;
- February 16: Martingales;
- February 21: Galton-Watson process; and
- February 28: Robbins-Monro algorithm, part 1.
Presentations
- October 21, Journées automnales ResCOM: Routage par marche aléatoire à liste tabou.
