Title :
Localized low-weight graph and its applications in wireless ad hoc networks
Author :
Xiang-Yang Li ; Yu Weng ; Peng-Jun Wan ; Wen-Zhan Song ; Frieder, O.
Author_Institution :
Dept. of Comput. Sci., Illinois Inst. of Technol., Chicago, IL, USA
Abstract :
We propose a new localized structure, namely, Incident MST and RNG Graph (IMRG), for topology control and broadcasting in wireless ad hoc networks. In the construction algorithm, each node first builds a modified relative neighborhood graph (RNG´), and then informs its one-hop neighbors its incident edges in RNG´. Each node then collects all its one-hop neighbors and the two-hop neighbors who have RNG edges to some of its one-hop neighbors, and builds an Euclidean minimum spanning tree of these nodes. Each node u keeps an edge uv only if uv is in the constructed minimum spanning tree. We analytically prove that the node degree of the IMRG is at most 6, it is connected and planar, and more importantly, the total edge length of the IMRG is within a constant factor of that of the minimum spanning tree. To the best of our knowledge, this is the first algorithm that can construct a structure with all these properties using small communication messages (at most 13n total messages, each with O(logn) bits) and small computation cost, where n is the number of wireless nodes. Test results are corroborated in the simulation study.
Keywords :
ad hoc networks; graph theory; telecommunication network topology; Euclidean minimum spanning tree; IMRG; incident MST-RNG graph; localized low-weight graph; modified relative neighborhood graph; one-hop neighbors; topology control; wireless ad hoc networks; Ad hoc networks; Application software; Computer science; Costs; Intelligent networks; Mobile ad hoc networks; Network topology; Relays; Tree graphs; Wireless networks;
Conference_Titel :
INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies
Print_ISBN :
0-7803-8355-9
DOI :
10.1109/INFCOM.2004.1354515