Abstract
We consider the network connectivity problem in a wireless ad hoc network. Network connectivity is measured by the conductance of the network, also called the Cheeger constant of the graph. A partition algorithm based on this measure is developed that divides the network at the bottleneck area. After the network is bisected, a relay node may be deployed between the two parts to increase the conductance of the network. The relay node deployment problem is formulated as an integer linear program to maximize the number of connections between the nodes on the two sides of the cut, and then a convex optimization algorithm is used to find the precise location of the relay node, which is within the convex hull defined by the radio transmission ranges of all the nodes that can connect to the relay node. The relay node significantly relieves the bottleneck, and the graph connectivity measured by other metrics such as the widely used Fiedler value are also increased.
Recommended Citation
M. X. Cheng et al., "Wireless Ad Hoc Networks Connectivity Assessment and Relay Node Deployment," Proceedings - IEEE Global Communications Conference, GLOBECOM, pp. 399 - 404, article no. 7036841, Institute of Electrical and Electronics Engineers, Jan 2014.
The definitive version is available at https://doi.org/10.1109/GLOCOM.2014.7036841
Department(s)
Computer Science
International Standard Serial Number (ISSN)
2576-6813; 2334-0983
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2024 Institute of Electrical and Electronics Engineers, All rights reserved.
Publication Date
01 Jan 2014
