Login | Register

Virtual backbone formation in wireless ad hoc networks

Title:

Virtual backbone formation in wireless ad hoc networks

Kassaei, Hossein (2010) Virtual backbone formation in wireless ad hoc networks. Masters thesis, Concordia University.

[img]
Preview
Text (application/pdf)
MR67117.pdf - Accepted Version
4MB

Abstract

We study the problem of virtual backbone formation in wireless ad hoc networks. A virtual backbone provides a hierarchical infrastructure that can be used to address important challenges in ad hoc networking such as efficient routing, multicasting/broadcasting, activity-scheduling, and energy efficiency. Given a wireless ad hoc network with symmetric links represented by a unit disk graph G = (V, E ), one way to construct this backbone is by finding a Connected Dominating Set (CDS) in G , which is a subset V' ✹ V such that for every node u, u is either in V' or has a neighbor in V' and the subgraph induced by V' is connected. In a wireless ad hoc network with asymmetric links represented by a directed graph G = (V, E ), finding such a backbone translates to constructing a Strongly Connected Dominating and Absorbent Set (SCDAS) in G . An SCDAS is a subset of nodes V' ✹ V such that every node u is either in V' or has an outgoing and an incoming neighbor in V' , and the subgraph induced by V' is strongly connected. Based on most of its applications, minimizing the size of the virtual backbone is an important objective. Therefore, we are interested in constructing CDSs and SCDASs of minimal size. We give efficient distributed algorithms with linear time and message complexities for the construction of the CDS in ad hoc networks with symmetric links. Since topology changes are quite frequent in most ad hoc networks, we propose schemes to locally maintain the CDS in the face of such changes. We also give a distributed algorithm for the construction of the SCDAS in ad hoc networks with asymmetric links. Extensive simulations show that our algorithms outperform all previously known algorithms in terms of the size of the constructed sets.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Kassaei, Hossein
Pagination:ix, 118 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science and Software Engineering
Date:2010
Thesis Supervisor(s):Narayanan, L
ID Code:979218
Deposited By: Concordia University Library
Deposited On:09 Dec 2014 17:55
Last Modified:18 Jan 2018 17:48
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Back to top Back to top