Topology control for mobile ad hoc networks
Errol L. Lloyd, Liang Zhao · 2007
A wireless ad hoc network is a network without any pre-existing infrastructure (such as fixed base stations) where the nodes can be deployed randomly. In a wireless ad hoc network, every node can communicate with any other node through direct wireless connections or multi-hop relays. We study topology control problems that are concerned with the assignment of power values to transceivers (nodes) of an ad hoc network so as to maintain a prespecified graph topology. Such problems can be formulated under several optimization objectives, including minimizing the maximum transmission power used by any node and minimizing the total transmission power used by all nodes. The benefits gained from minimizing transmission power in topology control are that (1) reducing power at each transceiver can prolong the lifetime of an ad hoc network, and (2) lower transmission power may cause lower channel contention and increase spatial frequency re-use. In our research, the major challenge comes from topology control for mobile ad hoc networks, which had not been previously studied from a theoretical viewpoint. Although this problem was proposed over a decade ago and there are a number of papers1 examining the problem from various perspectives, most of them only deal with stationary networks. There is no previous research that can optimally solve any topology control problem when node mobility is incorporated. In this dissertation, we establish four mobility models (i.e. SMN, GMN, CRMN and DMN) for mobile ad hoc networks. Under these models, we specify four groups of topology control problems in mobile ad hoc networks. The major contributions of this dissertation include solving the SMN problems optimally by three frameworks with one improving upon the other, solving the CRMN problems optimally, and establishing approximation algorithms for the DMN problems. For each algorithm, we analyze its computational complexity and present a formal proof for its correctness. Beyond the theoretical contributions, we provide experimental results through quantitative research. Here, we study the impact of clustering algorithms on the performance of a distributed topology control framework (i.e. the cluster based topology control framework—CLTC). Then, we compare the performances of existing distributed topology control algorithms for stationary networks and adapt them to mobile networks. In addition, the performance of the CLTC framework is compared with that of existing distributed topology control algorithms through analytical and experimental study. 1Since only a few of them are closely related to my research (hence listed in the references), the reader may search “mobile ad hoc networks” in IEEE Xplore to sense the large number of papers and broad range of topics studied in this field.