Finding minimum transmission radii for preserving connectivity and constructing minimal spanning trees in ad hoc and sensor networks

摘要

Ad hoc networks are normally modeled by unit graphs, where two nodes are connected if and only if their distance is at most the transmission radius R, equal for all nodes. Larger than necessary values of R cause communication interference and consumption of increased energy, while smaller values may disable data communication tasks such as routing and broadcasting. It was recognized that the minimum value of R that preserves the network connectivity is equal to the longest edge in the minimum spanning tree. However, all existing solutions for finding R rely on algorithms that require global network knowledge or inefficient straightforward distributed adaptations of centralized algorithms. This article proposes to use the longest LMST (local minimum spanning tree, recently proposed message free approximation of MST) edge to approximate R using a wave propagation quasi-localized algorithm. The differences between exact and so approximated values of R are estimated for two and three-dimensional random unit graphs. Despite small number of additional edges in LMST with respect to MST (under 5%), 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 quasi-localized scheme for constructing MST from LMST It needs less than 7 messages per node on average (for networks tip to 500 nodes). 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 node (as a byproduct, this single node can also be considered as an elected leader of the network). This so elected leader also learns longest MST edge in the process, and may broadcast it to other nodes. We also describe an algorithm for updating MST when a single node is added to the network. (C) 2004 Elsevier Inc. All rights reserved.