Abstract

In wireless ad hoc networks, maintaining network connectivity is very important as high-level network functions all depend on it. However, how to measure network connectivity remains a fundamental challenge. For example, a network can have good overall k-connectivity and yet still have a communication bottleneck. In this paper, we address how to locate bottlenecks and relieve them. A new connectivity measure based on the Cheeger's Constant is used for bottleneck discovery, and a partition algorithm that divides the network at the bottleneck is developed. After the network is partitioned, we consider deploying a relay node to increase the conductance of the network across the partition. The relay node deployment problem is formulated as an integer linear program to maximize the number of connections between 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. We show that the relay node significantly relieves the bottleneck and improves network connectivity, which is manifested by several network connectivity metrics. The partition and relay node deployment algorithms are then extended to the case where multiple relay nodes are available. Multiway partition and multiple relay node deployment algorithms are presented. Simulation results show this approach effectively enhances network connectivity with a small number of relay nodes.

Department(s)

Computer Science

Publication Status

Open Archive

Comments

National Science Foundation, Grant CMMI-1551448

Keywords and Phrases

Linear programming; Network connectivity; Optimization

International Standard Serial Number (ISSN)

0304-3975

Document Type

Article - Journal

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2024 Elsevier, All rights reserved.

Publication Date

17 Jan 2017

Download

Full Text Link

Share

 
COinS