ALCOMFT-TR-03-127

Matthias Grünewald, Tamás Lukovszki, Christian Schindelhauer and Klaus Volbert
Distributed Maintenance of Resource Efficient Wireless Network Topologies
Paderborn. Work package 2. December 2003.

Abstract: Multiple hop routing in mobile ad hoc networks can minimize energy consumption and increase data throughput. Yet, the problem of radio interferences remain. However if the routes are restricted to a basic network based on local neighborhoods, these interferences can be reduced such that standard routing algorithms can be applied.

We compare different network topologies for these basic networks, i.e. the Yao-graph (aka. Theta-graph) and some also known related models, which will be called the SymmY-graph (aka. YS-graph), the SparsY-graph (aka.YY-graph) and the BoundY-graph. Further, we present a promising network topology called the HL-graph (based on Hierarchical Layers).

First we compare the degree and spanner-properties. Then, we consider communication features. Our hardware model allows sector-independent directed communication, adjustable sending power, one frequency, and interference detection. We investigate how these network topologies bound the number of (uni- and bidirectional) interferences and whether these basic networks provide energy-optimal or congestion-minimal routing.

Then, we compare the ability of these topologies to handle dynamic changes of the network when radio stations appear and disappear. For this we measure the number of involved radio stations and present distributed algorithms for repairing the network structure.

It turns out that in a worst-case scenario the SparsY-graph combines good performance in terms of interferences, energy and congestion: For energy it allows a constant factor approximation and a O(log n) approximation of the congestion. However, all Yao-graph based topologies have only linear time algorithm for rebuilding the graph after one station appears or disappears because a linear number of stations is involved in the worst case. For the HL-graph we need only logarithmic time and a logarithmic number of involved stations. Further, it provides a linear approximation of the energy optimal path system, and allows path systems approximating the minimal congested routing by a factor of O(log² n).

Postscript file: ALCOMFT-TR-03-127.ps.gz (588 kb).