<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T14:36:51Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/3543" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/3543</identifier><datestamp>2017-03-21T15:57:58Z</datestamp><setSpec>com_10012_9900</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9914</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="d3b1a9eb-2f46-4177-a7f8-964e74cc84a8" confidence="600">Almahrog, Khalid</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2008-01-25T16:34:05Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2008-01-25T16:34:05Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2008-01-25T16:34:05Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2007</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/3543</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">As a result of the recent advances in the computation and communications industries,&#xd;
wireless communications-enabled computing devices are ubiquitous nowadays.&#xd;
Even though these devices are introduced to satisfy the user’s mobile computing&#xd;
needs, they are still unable to provide for the full mobile computing functionality&#xd;
as they confine the user mobility to be within certain regions in order to benefit&#xd;
from services provided by fixed network access points.&#xd;
Mobile ad hoc networks (MANETs) are introduced as the technology that potentially&#xd;
will make the nowadays illusion of mobile computing a tangible reality.&#xd;
MANETs are created by the mobile computing devices on an ad hoc basis, without&#xd;
any support or administration provided by a fixed or pre-installed communications&#xd;
infrastructure.&#xd;
Along with their appealing autonomy and fast deployment properties, MANETs&#xd;
exhibit some other properties that make their realization a very challenging task.&#xd;
Topology dynamism and bandwidth limitations of the communication channel adversely&#xd;
affect the performance of routing protocols designed for MANETs, especially&#xd;
with the increase in the number of mobile hosts and/or mobility rates.&#xd;
The Connected Dominating Set (CDS), a.k.a. virtual backbone or Spine, is&#xd;
proposed to facilitate routing, broadcasting, and establishing a dynamic infrastructure&#xd;
for distributed location databases. Minimizing the CDS produces a simpler&#xd;
abstracted topology of the MANET and allows for using shorter routes between&#xd;
any pair of hosts. Since it is NP-complete to find the minimum connected dominating&#xd;
set, MCDS, researchers resorted to approximation algorithms and heuristics&#xd;
to tackle this problem.&#xd;
The literature is rich of many CDS approximation algorithms that compete in&#xd;
terms of CDS size, running time, and signaling overhead. It has been reported&#xd;
that localized CDS creation algorithms are the fastest and the lightest in terms of&#xd;
signaling overhead among all other techniques. Examples of these localized CDS&#xd;
algorithms are Wu and Li algorithm and its Stojmenovic variant, the MPR algorithm,&#xd;
and Alzoubi algorithm. The designers of each of these algorithms claim&#xd;
that their algorithm exhibits the highest degree of localization and hence incurs the lowest cost in the CDS creation phase. However, these claims are not supported&#xd;
by any physical or at least simulation-based evidence. Moreover, the cost of maintaining&#xd;
the CDS (in terms of the change in CDS size, running time, and signaling&#xd;
overhead), in the presence of unpredictable and frequent topology changes, is an&#xd;
important factor that has to be taken into account -a cost that is overlooked most&#xd;
of the time.&#xd;
A simulation-based comparative study between the performance of these algorithms&#xd;
will be conducted using the ns2 network simulator. This study will focus&#xd;
on the total costs incurred by these algorithms in terms of CDS size, running time,&#xd;
and signaling overhead generated during the CDS creation and maintenance phases.&#xd;
Moreover, the effects of mobility rates, network size, and mobility models on the&#xd;
performance of each algorithm will be investigated. Conclusions regarding the pros&#xd;
and cons of each algorithm will be drawn, and directions for future research work&#xd;
will be recommended.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Mobile Ad hoc Networks</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Backbone foramtion algorithms</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Performance Evaluation</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Electrical and Computer Engineering</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Simulation-based Performance Evaluation of MANET Backbone Formation Algorithms</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="comment" qualifier="hidden" lang="en">This thesis was previously approved by the&#xd;
GSO.</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Systems Design Engineering</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Applied Science</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>