Diz 37 en
On Distributed and Real-Time Routing in Sensor Networks
Author: Jiří Trdlička
The thesis is focused on in-network distributed and real-time routing algorithms for multi-hop sensor networks with linear cost functions and constant communication delays. The work aims mathematically derived algorithms which are based on the convex optimization theory and which are capable of computing an exact optimal solution e.g. in terms of the energy consumption. The work consists of three parts.
The first part is focused on centralized algorithms for real-time routing in sensor networks. Two routing algorithms are developed in this part. The first algorithm addresses problem with continuous data streams with a real-time constraints on communication delay. The second algorithm addresses problem, where the real-time data are send in messages with transmission periods significantly bigger than one hop communication delay. The both algorithms are based on a minimum-cost multi-commodity network flow model and use a network replication to include the real-time constraints. Solved by Linear Programming, they exhibit a very good performance, as is shown in our experiments. Surprisingly, the performance does not degrade even in the presence of an integral flow constraint, which makes the problems NP hard.
The second part of this work is focused on in-network distributed energy optimal routing algorithms for non-real-time data flow with linear objective functions. Three distributed routing algorithms are mathematically derived in this part: Two Loops Distributed Routing Algorithm (TLDRA),One Loop Distributed Routing Algorithm with Incremental flow update (OLDRAi) and One Loop Distributed Routing Algorithm with Optimal flow update (OLDRAo). The algorithms are based on the proximal-point method and the dual decomposition of convex optimization problem. The algorithms compute an exact energy optimal routing in the network without any central node or the knowledge about the whole network structure, using only peer-to-peer communication between neighboring nodes. In contrast to other works in this area, the presented approach is not limited to strictly convex objective functions and it even handles linear objective functions which makes the algorithm and proof of its convergence more difficult. Proofs of the algorithms convergence are presented.
The third part of this work derives a distributed routing algorithm for real-time data streams with constant communication delays. The algorithm is based on the OLDRAo and on the routing algorithm for continuous data streams with real-time constraints from the two previous parts.
The behaviors of all presented algorithms have been evaluated on benchmarks for energy optimal routing in multi-hop sensor networks, using Matlab.
- Jiří Trdlička, mailto:firstname.lastname@example.org, www.trdlicka.cz