Back to search

University of British Columbia

Design and analysis of a connected dominating set algorithm for mobile ad hoc networks

Abstract

dc:description

Wireless technology such as IEEE 802.11b allows a set of devices to communicate with each other in a peer-to-peer manner by dynamically forming mobile ad hoc networks. Routing in such networks is challenging due to node mobility, low power, constrained bandwidth and limited radio range. Most of the previous works are based on strategies that combine flooding and caching to discover routes proactively or on demand. But these algorithms suffer from scalability problems when there exist many spontaneous and short-term connections. This thesis describes the design and implementation of a backbone routing scheme, DCDS, which is inspired by the previous CDS and DSR algorithms. Like other CDS algorithms, it constructs and proactively maintains a backbone across the network; like DSR, it discovers routes on-demand and uses source routing. However, DCDS makes significant improvements on each of the algorithms on which it is based. It differs from the previous CDS work in that three key assumptions have been removed to make DCDS truly deployable in an IEEE 802.11 network: reliable broadcast, accurate neighbouring information, and a static setup phase. It differs from DSR in that route discovery is restricted to the backbone instead of flooding the entire network and data packets are delivered via multiple paths on the backbone. We have implemented the DCDS algorithm and simulated it using Glomosim. The evaluations clearly show that DCDS achieves significantly better scalability than DSR in a moderately dense network with reasonable mobility settings.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2004

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Cai, Kan

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/15472

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Cai, Kan. Design and analysis of a connected dominating set algorithm for mobile ad hoc networks. master's thesis, University of British Columbia, 2004. http://hdl.handle.net/2429/15472