Graduation Semester and Year

2008

Language

English

Document Type

Dissertation

Degree Name

Doctor of Philosophy in Computer Science

Department

Computer Science and Engineering

First Advisor

Sajal Das

Abstract

With the fast advances in inexpensive sensor technology and wireless communications, the design and development of large-scale wireless sensor networks has become cost-effective and viable enough to attract the attention of a wide range of civilian, natural, and military applications, such as health and environmental monitoring, seism monitoring, and battlefields surveillance. The main challenge in the design of wireless sensor networks is the limited battery power of the sensors and the difficulty of replacing and/or recharging these batteries due to the nature of the monitored field, such as hostile environments, and cost. Thus, it is necessary that the sensors be densely deployed and energy-efficient protocols be designed to maximize the network lifetime while meeting the specific application requirements in terms of coverage and connectivity. In this dissertation, we propose a continuum percolation-based approach to compute the critical sensor spatial density above which a field is almost surely covered and the network is almost surely connected. This approach helps network designers achieve full coverage of a field with a minimum number of connected sensors, thus maximizing the network lifetime. In order to support different applications and environments with diverse requirements in terms of coverage and connectivity, we extend our above analysis to k-coverage with k = 3 using a deterministic approach so the network self-configures to meet these requirements. More specifically, we propose a unified, energy-efficient framework for connected k-coverage, duty-cycling, and geographic forwarding in wireless sensor networks. Our framework, called Cover-Sense-Inform (CSI), includes randomized centralized, pseudo-distributed, and distributed protocols for connected k-coverage along with geographic forwarding protocols in duty-cycled, k-covered wireless sensor networks. We prove that k-covered wireless sensor networks have connectivity that is higher than their degree of coverage k, thus providing architectures with high degree of fault-tolerance. In the centralized connected k-coverage protocol, the sink is responsible for selecting a minimum number of active sensors to fully k-cover a field while maintaining connectivity between them. Both of the pseudo-distributed connected k-coverage protocols consider different levels of network clustering and are run under the control of a subset of sensors, called cluster-heads, which are selected by the sink in each scheduling round. Each cluster-head is responsible for selecting a subset of active neighboring sensors to k-cover its cluster while guaranteeing connectivity between all active sensors. In the distributed connected k-coverage protocol, all the sensors are required to coordinate among themselves to fully k-cover a field while ensuring network connectivity. Simulation results show that our protocols select a minimum number of sensors, thus maximizing energy saving. Using a potential fields-based approach, we propose deterministic and hybrid geographic forwarding protocols for duty-cycled, k-covered wireless sensor networks with different levels of data aggregation. Simulation results show that CSI yields significant energy savings while guaranteeing high data delivery ratio. Besides, we extend CSI to address the stochastic connected k-coverage problem in wireless sensor networks using a more realistic sensing model that accounts for the stochastic properties of the sensors. We also extend CSI to three-dimensional wireless sensor networks and find that the extension of our analysis from two-dimensional to three-dimensional space is not straightforward. Finally, we propose a solution to the energy sink-hole problem, which is inherent to static wireless sensor networks, by exploiting energy heterogeneity, sink mobility, and energy aware Voronoi diagram. Simulation results show that our solution yields uniform energy consumption of all the sensors, thus extending the network lifetime.

Disciplines

Computer Sciences | Physical Sciences and Mathematics

Comments

Degree granted by The University of Texas at Arlington

Download

Share

COinS