QoS topology control in ad hoc wireless networks

Wireless network topology control has drawn considerable attentions recently. However, priori arts assumed that the wireless ad hoc networks are modeled by unit disk graphs (UDG), i.e., two mobile hosts can communicate as long as their Euclidean distance is no more than a threshold. However, practically, the networks are never so perfect as unit disk graphs: the transmission ranges may vary due to various reasons such as the device differences, the network control necessity, and the perturbation even the transmission radii are set as the same. Thus, we assume that each mobile host has its own transmission range. The networks are modeled by mutual inclusion graphs (MG), where two nodes are connected iff they are within the transmission range of each other. Previously, no method is known for topology control when the networks are modeled as mutual inclusion graphs. The paper proposes the first distributed mechanism to build a sparse power efficient network topology for non-uniform ad hoc wireless networks. The method also works for networks with directional antennas. We first extend the Yao structure to build a spanner with a constant length and power stretch factor for mutual inclusion graph. We then propose two efficient localized algorithms to construct connected sparse network topologies. The first structure, called extended Yao-Yao, has node degree at most O(log γ), where γ = maxumaxuv∈MG rurv. The second structure, called extended Yao and Sink, has node degree bounded by O(log γ), and is a length and power spanner. The methods are based on a novel partition strategy of the space surrounded each mobile host. Both algorithms have communication cost O(n), where each message has O(log n) bits