Supporting Multi-Missions In Wireless Sensor Networks
Open Access
- Author:
- Liu, Changlei
- Graduate Program:
- Computer Science and Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- May 05, 2010
- Committee Members:
- Guohong Cao, Dissertation Advisor/Co-Advisor
Guohong Cao, Committee Chair/Co-Chair
Thomas F Laporta, Committee Member
Sencun Zhu, Committee Member
Runze Li, Committee Member - Keywords:
- sensor network
multi-mission
wireless
approximation algorithm
coverage
landmine
monitoring - Abstract:
- The recent advances in sensing devices, embedded computing and wireless communication technology has sparked the emergence of the wireless sensor networks. However, most of the sensor networks nowadays only target for a single mission, and may not be cost effective from the resource management point of view. Therefore, in this dissertation, we focus on the design of multi-mission sensor network which is envisioned to support multiple applications of diverse requirements with a single network. To support multiple missions, several challenges naturally arise. The first challenge comes from the fact that the missions or the mission requirements may change over time. Therefore, the network needs to be enriched with the adaptation capability to explicitly handle the mission switch. Second, since sensor network has limited resources, e.g., energy, sensing, bandwidth, etc, these resources have to be shared by the multiple missions. An efficient resource allocation scheme, therefore, should maximize the total profit by taking account into all the mission requirements. Third, since mission-driven sensor network is usually deployed in the harsh, unattended, dynamic environment, it is important to monitor the sensor status, based on which decisions about the mission switch can be made. While more challenges can be listed here, in this dissertation, we primarily focus on these three aspects, namely, mission switch, resource allocation, and network monitoring. Each of the aspects is examined under different contexts within an integrated framework, and briefly summarized in the following. First, we study the mission switch in a surveillance application. As mission switches, e.g., the network is commanded to last for a longer time, some sensors may have to sleep longer during each duty cycle. Then the original sensor deployment may not be able to satisfy the coverage and lifetime requirements at the same time, and the coverage may need to be traded for network lifetime. To deal with this tradeoff, we propose the concept of spatial-temporal coverage, in contrast to the traditional area coverage. Our goal is to schedule the sensor activity to maximize the total spatial-temporal coverage during a specified network lifetime. Both centralized and distributed heuristics are proposed, with the approximation factor of the centralized algorithm proved to be $frac{1}{2}$. Second, we explore the resource allocation in the landmine networks and investigate how to accomplish multiple missions with the minimum resources usage. Specifically, we have studied a multi-target defense scenario, where our mission is to destroy the multiple intruding targets using the minimum cost pre-deployed landmines. Due to the NP Complexity of the problem, we have proposed a greedy algorithm and a layering algorithm, whose approximation ratios are derived. Third, we have proposed the multi-poller based monitoring architecture for mission driven sensor networks. Compared with the single poller scheme, the multi-poller scheme significantly reduces the false alarm rate, while keeping the similar bandwidth consumption. To construct the monitoring architecture, we formulate a many-to-many poller-pollee assignment problem and present three distributed algorithms (i.e., random, deterministic, and hybrid). We have also explored the hop-by-hop aggregation opportunity between the poller and pollee, and formulate the optimal aggregation path problem. We solve this NP-hard problem by designing an opportunistic greedy algorithm, which achieves an approximation ratio of $frac{5}{4}$. As far as we know, this is the first proved constant approximation ratio applied to the aggregation path selection schemes over the wireless sensor networks.