Date & time
Wednesday, August 27, 2014
10:30 a.m. – 1:30 p.m.
10:30 a.m. – 1:30 p.m.
Thesis defences
Share this event:
PhD Oral Exam – Louisa Harutyunyan
Efficient Data Dissemination in Wireless Ad Hoc Networks
Cost
This event is free
Where
Engineering and Visual Arts Complex
1515 St. Catherine W.
Room Room EV-2.184
Wheel chair accessible
Yes
When studying for a doctoral degree (PhD), candidates submit a thesis that provides a critical review of the current state of knowledge of the thesis subject as well as the student’s own contributions to the subject. The distinguishing criterion of doctoral graduate research is a significant and original contribution to knowledge.
Once accepted, the candidate presents the thesis orally. This oral exam is open to the public.
Abstract
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 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 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 large girth as well as in random graphs with non-fixed probability p. In mobile ad hoc networks we propose a beacon-less 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.