Topology control for broadcasting over energy constrained wireless ad hoc networks

Broadcasting is a major mode of communications for efficient information dissemination. Wireless channels naturally support broadcast in that a single transmission can be heard by many others within the communication boundary. Therefore, if we take good advantage of this natural broadcast property of wireless channel for broadcasting purpose, great savings in network resource are achievable. A wireless ad hoc network is a network consisting of autonomous nodes communicating each other over the wireless channel. It is different from the conventional wireless networks in that there is no pre-deployed infrastructure. Because the actual network topology is unknown until nodes are deployed in physical environments, autonomous network formation is a necessity and hence routing is one of the most fundamental functions to support any network service. In wireless ad hoc networks, nodes can directly communicate with other nodes that are within the reach of each other. If a direct communication link does not exist, nodes can still communicate through multiple hop links by relaying traffic for other nodes. Multihop communication raises challenging trade-offs to save energy, whether to reach many nodes simultaneously with large power or to reach a number of nodes with small power due to the broadcast property of the wireless channel. Since wireless ad hoc networks consist of nodes with scarce battery energy resource, and broadcast is a network-wide operation involving all network nodes, broadcast routing design for battery energy efficiency is a crucial factor for a prolonged network operation.; In this dissertation, we consider topology control problems through nodes' transmit power control either to minimize total transmit power or to maximize network lifetime using omnidirectional or directional antenna systems. For the NP-complete minimum energy broadcast problem, we present various heuristics based on geometric and local search optimization techniques. The maximum lifetime problem is analysed in a graph-theoretic approach. For a static network, we formulate the problem as a bottleneck optimization problem and present a polynomial time optimal algorithm. For a dynamic network, we present load-balancing techniques through periodic tree update and demonstrate that network lifetime can be extended approximately by twice the optimal static network lifetime.