Improving Connectivity of Wireless Ad-Hoc Networks

Li, Ning; Hou, Jennifer C.

Permalink

https://hdl.handle.net/2142/10920 Copy

Description

Title

Improving Connectivity of Wireless Ad-Hoc Networks

Author(s)

• Li, Ning
• Hou, Jennifer C.

Issue Date

2004-10

Keyword(s)

• wireless networks
• ad hoc networks

Abstract

A fully connected topology is critical to many fundamental network operations in wireless ad-hoc networks. In this paper, we consider the problem of deploying additional wireless nodes to improve the connectivity of an existing wireless network. Specifically, given a disconnected wireless network, we investigate how to deploy as few additional nodes as possible so that the augmented network can be connected. The problem is termed as the Connectivity Improvement (CI) problem. We first prove that CI is NP-complete, and then present a Delaunay Triangulation-based algorithm, Connectivity Improvement using Delaunay Triangulation (CIDT). Depending on the priority based on which the components in a disconnected network should be chosen to connect, we devise several different versions of CIDT. We also present two additional optimization techniques to further improve the performance of CIDT. Finally, we verify the effectiveness of CIDT, and compare the performance of its variations via J-Sim simulation.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/10920

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections