Sparse power efficient topology for wireless networks

Abstract

We consider how to construct power efficient wireless ad hoc networks. We propose two different methods combining several well-known proximity graphs including the Gabriel graph and the Yao graph, which can be constructed locally and efficiently. Firstly, we combine the Gabriel structure and the Yao structure. The constructed topology has at most O(n) edges and each node has a bounded out-degree. Secondly, we use the Yao structure and then use the reverse of the Yao structure. The constructed topology is guaranteed to be connected if the original unit disk graph is connected. Every node has a bounded degree. The experimental results show that it has a bounded unicasting and broadcasting power stretch factor in practice.