Download the full-sized PDF of Probabilistic Connectivity of Underwater Sensor NetworksDownload the full-sized PDF



Permanent link (DOI):


Export to: EndNote  |  Zotero  |  Mendeley


This file is in the following communities:

Graduate Studies and Research, Faculty of


This file is in the following collections:

Theses and Dissertations

Probabilistic Connectivity of Underwater Sensor Networks Open Access


Other title
k-tree, Partial k-tree, A-CONN, SR-CONN
Type of item
Degree grantor
University of Alberta
Author or creator
Islam, Md Asadul
Supervisor and department
Professor Ehab S. Elmallah
Examining committee member and department
Professor Lorna Stewart Department of Computing Science
Professor Ehab S. Elmallah Department of Computing Science
Professor Janelle Harms Department of Computing Science
Department of Computing Science

Date accepted
Graduation date
Master of Science
Degree level
Underwater sensor networks (UWSNs) have recently attracted increasing research attention for their potential use in supporting many important applications and services. Examples include scientific applications such as studies of marine life, industrial applications such as monitoring underwater oil pipelines, humanitarian applications such as search and survey missions, and homeland security applications such as monitoring of ships and port facilities. The design of UWSNs, however, faces many challenges due to harsh water environments. In particular, nodes in such networks are subject to small scale and large scale uncontrollable movements due to water currents. Since maintaining network connectivity is crucial for performing many tasks that require node collaboration, it becomes important to quantify the likelihood that a network maintains connectivity during some interval of time of interest. In this thesis, we approach the above challenging problem by adopting a probabilistic model to describe node location uncertainty in semi-mobile and mobile deployments. Using this model, we devise a notion of probabilistic graphs to tackle the problem. We then formalize four probabilistic network connectivity problems that deal with fully and partially connected networks that may utilize relay nodes. Using the theory of partial k-trees, we devise algorithms that run in polynomial time, for any fixed k, to solve the formalized problems. We present simulation experiments to illustrate the use of the devised algorithms in the topological design of UWSNs.
Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.
Citation for previous publication
Md. Asadul Islam and Ehab S. Elmallah, Tree Bound on Probabilistic Connectivity of Underwater Sensor Networks, The 13th IEEE WLN workshop, Edmonton 2014 (To appear)

File Details

Date Uploaded
Date Modified
Audit Status
Audits have not yet been run on this file.
File format: pdf (PDF/A)
Mime type: application/pdf
File size: 1534906
Last modified: 2015:10:12 15:17:57-06:00
Filename: Islam_MdAsadul_201408_MSC.pdf
Original checksum: 41ef366cdd78af8b63479547d2ce1bb7
Activity of users you follow
User Activity Date