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.
Original language | English (US) |
---|---|
Title of host publication | 2014 IEEE Global Communications Conference, GLOBECOM 2014 |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
Pages | 399-404 |
Number of pages | 6 |
ISBN (Electronic) | 9781479935116 |
DOIs | |
State | Published - Feb 9 2014 |
Externally published | Yes |
Event | 2014 IEEE Global Communications Conference, GLOBECOM 2014 - Austin, United States Duration: Dec 8 2014 → Dec 12 2014 |
Other
Other | 2014 IEEE Global Communications Conference, GLOBECOM 2014 |
---|---|
Country/Territory | United States |
City | Austin |
Period | 12/8/14 → 12/12/14 |
All Science Journal Classification (ASJC) codes
- Electrical and Electronic Engineering
- Computer Networks and Communications
- Communication