Distributed topology control in mobile ad-hoc networks

Mobility of nodes in a mobile ad-hoc network (MANET) is an important challenge in topology control. Some of the problems in this field include identifying appropriate transmission range, efficient use of channel by reducing the broadcast messages, reducing the message overhead in the network, better communication among the mobile nodes in the ad-hoc network without interference and efficient routing protocols. There are various approaches to address these problems and one such approach is to find a connected dominating subgraph (set), CDS, for a given connected graph to route messages, assuming static network without mobility. Finding a minimum CDS is NP-hard. Our contribution in this thesis is a distributed topology control algorithm to find a minimal CDS for a given connected graph which satisfies the connected, dominating, shortest path and minimality properties. This work is a modification of the algorithm proposed by Venkatesan and Young in [1]. This distributed algorithm makes use of local two hop neighborhood information to decide which nodes will be part of minimal CDS. Proofs and simulation results are presented to show the effectiveness of the algorithm.