University of Illinois Urbana-Champaign

Improving Connectivity of Wireless Ad-Hoc Networks

Li, Ning; Hou, Jennifer C.

Content Files
Improving Connectivity of Wireless Ad-Hoc Networks.pdf

Permalink

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

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
Date of Ingest
2009-04-17T14:58:04Z
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
Genre of Resource
Technical Report
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

Research and Tech Reports - Computer Science PRIMARY