Performance of distributed algorithms for topology control in wireless networks

We try to close the gap between theoretical investigations of wireless network topologies and realistic wireless environments. For point-to-point communication, we examine theoretically well-analyzed sparse graphs, i.e. the Yao-graph, the SparsY-graph, and the SymmY-graph. We present distributed algorithms that can be used to build up these graphs in time $O(log n)$ per node without the use of any geo-graphical positioning system. Our algorithms are based only on local knowledge and local decisions and make use of power control to establish communication links with low energy-cost. We compare these algorithms with respect to congestion, dilation, and energy. For congestion we introduce different measures that allow us to investigate the difference between real-world wireless networks and models for wireless communication at a high level of abstraction. For more realistic simulations we extend our simulation environment SAHNE. We use a realistic transmission model for directed communication that uses sector subdivision. Finally, our experimental results show that our topologies and algorithms work well in a distributed environment and we give some recommendations for the topology control based on our simulations.