### 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.