Efficient topology control for ad-hoc wireless networks with non-uniform transmission ranges

摘要: Wireless network topology control has drawn considerable attention recently. 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 their Euclidean distance is no more than a threshold. However, practically, never so perfect graphs: transmission ranges may vary due to various reasons such device differences, necessity, and perturbation of even set same originally. Thus, we assume each host its own range. The mutual inclusion (MG), where nodes connected iff they within range other. Previously, method known for when graphs.The paper proposes first distributed mechanism build sparse power efficient with non-uniform ranges. We extend Yao structure spanner constant length stretch factor graph. then propose localized algorithms construct topologies. structure, called extended Yao-Yao, node degree at most O(log γ), γ = maxu maxuv∈MG ru/rv. second Sink, bounded spanner. methods based on novel partition strategy space surrounded host. Both have communication cost O(n) under local broadcasting model, message n) bits.