Font Size: a A A

Research On Optimization Problems For Coverage And Localization In Wireless Sensor Networks

Posted on:2016-12-21Degree:DoctorType:Dissertation
Country:ChinaCandidate:P WuFull Text:PDF
GTID:1108330482452164Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
In many applications, such as environmental monitoring and indoor localization, wireless sensors are deployed within the surveillance field. These nodes form a multi-hop network to collect surveillance data and forward surveillance data through a base station to end users. With received surveillance data, end users could remotely moni-tor environmental conditions in the surveillance field. In a sensor surveillance system, real-time monitoring indicates that the system could answer whether a target show up and where the target is in the surveillance field. The first question is about coverage and the second one is about localization. Focusing on target coverage and device-free localization, this thesis considers three problems, including stochastic target coverage with data fusion, minimizing receivers under link coverage model and energy efficient device free localization. (1) Considering the randomness of the target appearance, it is unnecessary to make all nodes in working state. We can prolong the network lifetime by carefully selecting a subset of sensors to sleep. Thus, given a specific requirement of system reliability, we consider how to maximize the network lifetime subject to the con-straint of stochastic coverage of random targets under data fusion model. We formalize the problem and prove that the problem is NP-hard. Then we provide a probabilistic set covering based algorithm for small scale networks and propose a greedy algorithm for large scale networks. Simulation results show that the network lifetime can be greatly improved if the system reliability is lowered.(2) Device-free localization could detect and locate human presence nearby via many wireless links. This actually provides us a new link-centric ’sensing’ model, dif-ferent from the traditional node-centric disk sensing model. Based on the new link coverage model, we investigate the target coverage problem with the minimum num-ber of receivers, i.e., how to deploy least receivers to cover all targets when senders are pre-deployed. By transforming DOMINATING SET to LINK COVER, we prove that the minimum link cover problem is NP-hard. Then we give two algorithms with guaranteed performance bounds. For density constrained link cover problem, we pro-pose a polynomial time approximation scheme (PTAS). Finally, extensive simulations demonstrate the effectiveness of our proposed algorithms.(3) Existing works on device-free localization mainly focus on improving local-ization accuracy, and none of them considers energy efficiency specifically. We present a device-free localization system EE-Loc to locate a user in an energy efficient manner. EE-Loc not only significantly reduces the energy consumption, but also achieves a lo-calization accuracy comparable to the state-of-the-art. It incorporates two mechanisms. First, EE-Loc uses only one bit information to describe link attenuation, which reduces transmitted data. Second, when tracking a user, EE-Loc deactivates many unneces-sary links with Kalman filter, which reduces unnecessary measurements. Real-world experiments with 16 sensor nodes show that EE-Loc has a localization accuracy com-parable to the state-of-the-art DFL systems. It improves energy efficiency by 27.05% for locating a stationary user, and reduces link measurements by 41.91% for tracking.
Keywords/Search Tags:Wireless sensor networks, Data fusion, Stochastic target coverage, Energy efficiency, Device-free localization
PDF Full Text Request
Related items