Login | Register

Efficient Data Dissemination in Wireless Ad Hoc Networks


Efficient Data Dissemination in Wireless Ad Hoc Networks

Harutyunyan, Louisa (2014) Efficient Data Dissemination in Wireless Ad Hoc Networks. PhD thesis, Concordia University.

[thumbnail of Harutyunyan_PhD_F2014.pdf]
Text (application/pdf)
Harutyunyan_PhD_F2014.pdf - Accepted Version
Available under License Spectrum Terms of Access.


In this thesis, we study the problem of efficient data dissemination in wireless sensor and mobile ad hoc networks. In wireless sensor networks we study two problems: (1) construction of virtual backbones and clustering hierarchies to achieve efficient routing, and (2) placement of multiple sinks, where each sensor is at a bounded distance to several sinks, to analyze and process data before sending it to a central unit. Often connected dominating sets have been used for such purposes. However, a connected dominating set is often vulnerable due to frequent node failures in wireless sensor networks. Hence, to provide a degree of fault-tolerance we consider in problem (1) a 2-connected (k,r)-dominating set, denoted D(2,k,r), to act as a virtual backbone or a clustering hierarchy, and in problem (2) a total (k,r)-dominating set to act as sinks in wireless sensor networks.

Ideally, the backbone or the number of sinks in the network should constitute the smallest percentage of nodes in the network. We model the wireless sensor network as a graph. The total (k,r)-dominating set and the 2-connected (k,r)-dominating set have not been studied in the literature. Thus, we propose two centralized approximation algorithms to construct a D(2,k,r) in unit disk graphs and in general graphs. We also derive upper bounds on the total (k,r)-domination number in graphs of girth at least 2k+1 as well as in random graphs with non-fixed probability p.

In mobile ad hoc networks we propose a hexagonal based beacon-less flooding algorithm, HBLF, to efficiently flood the network. We give sufficient condition that even in the presence of holes in the network, HBLF achieves full delivery. Lower and upper bounds are given on the number of forwarding nodes returned by HBLF in a network with or without holes. When there are no holes in the network, we show that the ratio of the shortest path returned by HBLF to the shortest path in the network is constant. We also present upper bounds on the broadcast time of HBLF in a network with or without holes.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (PhD)
Authors:Harutyunyan, Louisa
Institution:Concordia University
Degree Name:Ph. D.
Program:Computer Science
Date:28 August 2014
Keywords:ad hoc networks, sensor networks, mobile ad hoc networks, beacon-less flooding, domination number, total (k,r)-domination number, random graphs
ID Code:978892
Deposited On:20 Nov 2014 19:28
Last Modified:18 Jan 2018 17:47
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

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top