Topology control for ad hoc networks

An ad hoc network consists of a collection of transceivers that host communication over a wireless channel. This thesis is focused on improving the energy efficiency of wireless devices while maintaining a desirable network topology by adjusting the transmission power at each transceiver. Two fundamental optimization objectives regarding energy efficiency have been investigated in this research: minimizing the maximum transmission power used by any transceiver in the network (MAXP) and minimizing the sum of the transmission powers used by all of the transceivers (TOTAL P).; For the MAXP problem, we develop a general framework for all monotone and efficiently testable topology properties. Then we show that for a non-monotone property (e.g. the network topology is a TREE), this problem is NP-hard even without any optimization objective. Further, we establish that to minimize the number of transceivers that use the minimized maximum power is also NP-hard. Hence, we present two algorithms with provable constant approximation ratios for this problem when the topology property is 1-NODE C ONNECTED. With the TOTALP objective, the problem is NP-hard even for the simple property CONNECTED. Hence, we develop a general framework for approximation algorithms for monotone and efficiently testable topology properties. Based on this general framework, we obtain approximation algorithms for four graph properties.; Further, we investigate topology control problems under asymmetric power thresholds. We show that the asymmetry of power threshold can change the complexity of topology control problems and obtain approximate algorithms. We also present topology control algorithms that take into consideration the residual battery energy of each transceiver. We show that the complexity of this problem differs considerably based on whether or not the transceivers are allowed to vary their power levels.; Besides centralized algorithms, we also present distributed topology control solutions. We develop two distributed schemes. One is a message passing scheme such that our general framework for MAXP can be implemented in a distributed fashion. The other is a cluster-based topology control framework (called CLTC) that combines the centralized algorithms with clustering techniques.