Finding Minimum Transmission Radii for Preserving Connectivity and Constructing Minimal Spanning Trees in Ad Hoc and Sensor Networks

摘要

The minimum transmission radius R that preserves ad hoc network connectivity is equal to the longest edge in the minimum spanning tree. This article proposes to use the longest LMST (local MST, recently proposed message free approximation of MST) edge to approximate R using a wave propagation quazi-localized algorithm. Despite small number of additional edges in LMST with respect to MST, they can extend R by about 33% its range on networks with up to 500 nodes. We then prove that MST is a subset of LMST and describe a quazi-localized scheme for constructing MST from LMST. The algorithm eliminates LMST edges which are not in MST by a loop breakage procedure, which iteratively follows dangling edges from leaves to LMST loops, and breaks loops by eliminating their longest edges, until the procedure finishes at a single leader node, which then broadcasts R to other nodes.