Distributed topology control for mobile Ad Hoc networks: exploring the P/NP boundary

Abstract

The design goal of topology control in mobile ad hoc networks (MANET) discussed in this work is to construct a topology that guarantees network connectivity and maintain network performance. This work proposes, decentralized distributed Minimum Spanning Tree algorithm, a modification of Prim’s MST algorithm which is effective for topology control in MANET. The algorithm self-organizes the network topology. The process begins by each node constructing its own Minimum Spanning Tree (MST) topology, keeping on its tree only nodes that are one-hop away within its visible neighborhood. Followed by an optimization phase to ensure that the network has bi-directional links in order to maintain a strong network connectivity. The work also explored the Traveling Salesman Problem (TSP) boundary and proposed an approximation algorithm which is a modification of Christofides heuristics. Then lastly we discuss the merits and the demerits of the proposed topology control scheme and outline some relevant issues for future research.