Distributed Maintenance of Ressource Efficient Wireless Network Topologies Problems

Matthias Grünewald, Tamás Lukovszki, Christian Schindelhauer, Klaus Volbert


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 with respect to degree, spanner-properties, radio interferences, i.e. the Yao-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).

Further, 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.