We propose a novel topology control algorithm for each wireless node to locally select communication neighbors and adjust its transmission power, such that that all nodes together self-form an energy efficient topology for both unicast and broadcast communications.
In geometric terms, the network topology has the following desirable properties:
planarity (to guarantee packet delivery), spanner (to
keep an energy efficient path for any pair of nodes), bounded-degree (to reduce
contention), low-weight (to enable efficient broadcasting).
To the best of our knowledge, this is the first
localized algorithm to build such structure with all these desirable properties,
which enable energy efficient unicast and broadcast in a single structure.
Previously, only a centralized algorithm was reported in BGS02.
In addition, any two incident links in the final network topology are
Θ-separated.
We also show that the expected average interference of the final structure is
bounded by a small constant. In the proposed
algorithm, each node selects communication links only only according to local
information, hence the topology can be always updated locally and dynamically.
Moreover, by assuming that the node ID and its position can be
represented in O(log n) bits for a wireless network of n nodes,
the total number messages of our methods is in the range of [5n,13n],
where each message is O(\log n) bits. Our
theoretical results are corroborated in the simulations.