Wireless ad hoc networks connectivity assessment and relay node deployment

Maggie Cheng, Yi Ling, Brian M. Sadler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


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 languageEnglish (US)
Title of host publication2014 IEEE Global Communications Conference, GLOBECOM 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781479935116
StatePublished - Feb 9 2014
Externally publishedYes
Event2014 IEEE Global Communications Conference, GLOBECOM 2014 - Austin, United States
Duration: Dec 8 2014Dec 12 2014


Other2014 IEEE Global Communications Conference, GLOBECOM 2014
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering
  • Computer Networks and Communications
  • Communication


Dive into the research topics of 'Wireless ad hoc networks connectivity assessment and relay node deployment'. Together they form a unique fingerprint.

Cite this