Presented By:PAR Guillermo BARRENETXEA
ingénieur de télécommunication, Universidad Publica de Navarra, Espagne
de nationalité espagnole

---

DISTRIBUTED ROUTING ALGORITHMS
FOR SENSOR NETWORKS

Abstract

Recent advances in wireless communications and computing technology are enabling the emergence of low-cost devices that incorporate sensing, processing, and communication functionalities. A large number of these devices are deployed in the field to create a sensor network for both monitoring and control purposes. Sensor networks are currently an active research area mainly due to the potential of their applications. However, the deployment of a working large scale sensor network still requires solutions to a number of technical challenges that stem primarily from the constraints imposed by simple sensor devices: limited power, limited communication bandwidth, and small storage capacity. In view of all these particular constraints, we require a new paradigm for communication, which consists of new algorithms specifically conceived for sensor networks. This thesis concentrates on the routing problem, that is, moving data among different network locations, and on the interactions between routing and coding, that is, how sensors code the observations. We start by designing efficient and computationally simple decentralized algorithms to transmit data from one single source to one single destination. We formalize the corresponding routing problem as a problem of constructing suitably constrained random walks on random graphs and derive distributed algorithms to compute the local parameters of the random walk that induces a uniform load distribution in the network. The main feature of this routing formulation is that it is possible to route messages along all possible routes between the source and the destination node, without performing explicit route discovery/repair computations and without maintaining explicit state information about available routes at the nodes. A natural extension to the single-source/single-destination scenario is to consider multiple sources and/or multiple destinations. Depending on the structure and goal of the network, nodes exhibit different communication patterns. We analyze the problem of routing under three different communication models, namely uniform communication, central data gathering, and border data gathering. For each of these models, we derive capacity limits and propose constructive routing strategies that achieve this capacity. An important constraint of sensor networks is the limited storage capacity available at the nodes. We analyze the problem of routing in networks with small buffers. We develop new approximation models to compute the distribution on the queue size at the nodes which provide a more accurate distribution than the usual Jackson’s Theorem. Using these models, we design routing algorithms that minimize buffer overflow losses. Routing in large and unreliable networks, such as sensor networks, becomes prohibitively complex in terms of both computation and communication: due to temporary node failures, the set of available routes between any two nodes changes randomly. We demonstrate that achieving robust communications and maximizing the achievable rate per node are incompatible goals: while robust communications require the use of as many paths as possible between the source and the destination, maximizing the rate per node requires using only a few of the available paths. We propose a family of routing algorithms that explores this trade-off, depending on the degree of reliability of the network. The performance of routing algorithms in sensor networks can be significantly improved by considering the interaction of the source coding mechanism with the transport mechanism. We jointly optimize both the source coding and the routing algorithm in a common scenario encountered in sensor network, namely, real-time data transmission. We demonstrate that the combination of specially designed coding techniques, such as multiple description coding, and multipath routing algorithms, performs significantly better that the usual routing and coding schemes. In summary, this thesis revisits the classic routing problem in the light of distributed schemes for networks with resource-limited nodes. Introduction
1.1 The emergence of sensor networks
Recent advances in computing technology and wireless communications are enabling the
emergence of small and inexpensive devices incorporating communication, processing, and
sensor functionalities. Some of these devices are commercially available for a low price [66].
Although we are still far from truly inexpensive devices, the decreasing price of wireless
hardware is contributing to the proliferation of sensor networks for monitoring and control
purposes: a large quantity of these devices is deployed in the field to create a densely distributed
network of embedded signal sensors, processors and controllers.
One of the main reasons for the current rapid development of sensor networks is the
potential of its applications and its relevance in various research fields. Sensor networks applications
range from important societal issues such as environmental and habitatmonitoring,
traffic control, emergency scenarios, and health care, to economical issues such as production
control and structure monitoring [27; 41; 16; 28]. Sensor networks have also a great potential
as a research tool in experimental sciences: They facilitate the acquisition, processing, and
interpretation of data that with the current centralized measurement systems would be very
difficult and expensive. In addition to this, sensor networks allow data harvesting in scenarios
of difficult access or in adverse environments, and at spatial densities that are much finer than
with previous approaches.
However, the development of a working large scale sensor network still requires solutions
to a number of technical and theoretical challenges, due mainly to the constraints imposed
by the wireless sensor devices: Common devices used in sensor networks are generally very
limited in power, communication bandwidth, processing capabilities, and storage capacity.
Consequently, these devices present a high degree of unreliability, and information loss as
well as temporary failures are common in the network.
In view of all these particular features, sensor networks require a new paradigm for communications:
we need new tools (theories, heuristics, designs) specifically conceived for
sensor networks. Of particular interest for this thesis is the routing problem, that is, moving
data among different network locations.


for more infromation aout this yopic,please follow :
http://biblion.epfl.ch/EPFL/theses/2005/...TH3420.pdf