Improving connectivity of wireless ad hoc networks

N.  Li; J.C.  Hou

2nd International ICST Conference on Mobile and Ubiquitous Systems: Networking and Services

Research Article

Improving connectivity of wireless ad hoc networks

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1109/MOBIQUITOUS.2005.32,
    author={ N.  Li and  J.C.  Hou},
    title={Improving connectivity of wireless ad hoc networks},
    proceedings={2nd International ICST Conference on Mobile and Ubiquitous Systems: Networking and Services},
    publisher={IEEE},
    proceedings_a={MOBIQUITOUS},
    year={2005},
    month={11},
    keywords={},
    doi={10.1109/MOBIQUITOUS.2005.32}
}

N. Li
J.C. Hou
Year: 2005
Improving connectivity of wireless ad hoc networks
MOBIQUITOUS
IEEE
DOI: 10.1109/MOBIQUITOUS.2005.32

N. Li¹, J.C. Hou¹

1: Dept. of Comput. Sci., Illinois Univ., Urbana, IL, USA

Abstract

A fully connected network topology is critical to many fundamental operations in wireless ad hoc networks. We study the problem of deploying additional wireless nodes to improve the connectivity of an existing wireless network. Given a disconnected network, we consider the connectivity improvement (CI) problem, i.e., how to deploy as few additional nodes as possible so that the augmented network is connected. We first prove the NP-completeness of CI, and then present a Delaunay triangulation-based algorithm, connectivity improvement using Delaunay triangulation (CIDT). We discuss several variations of CIDT, and propose two additional optimization techniques to further improve the performance. Finally, we demonstrate the effectiveness of CIDT, and compare the performance of its variations via J-Sim simulation.

Published: 2005-11-21
Publisher: IEEE

: http://dx.doi.org/10.1109/MOBIQUITOUS.2005.32