Construction of a Low Energy Cost Power Spanner for Wireless Ad hoc Networks

Topology control in ad-hoc networks tries to lower node energy consumption by reducing transmission power and by confining interference, collisions and consequently retransmissions. In other words, we are given the communication graph G obtained when all the nodes transmit at maximum power, the goal is to identify a sparse subgraph G (also called power spanner) of G such that only energy-efficient links are retained in G . To achieve this goal, other desirable features of subgraph G have been identified. Having an upper bound on the maximum node degree of G is desirable to avoid bottlenecks in the Communication graph. We design algorithms that, given a unit-disc graph (UDG) G representing all feasible links, find a sparse subgraph G having maximum degree six and having minimum stretch factor. We propose method combining several well-known proximity graphs including Gabriel graph, Yao graph and LDS. We will show our algorithm (LECS) has low energy cost and small interference, compared with other known structures used in wireless ad hoc networks.