Minimizing movement for target coverage in mobile sensor networks

Zhuofan Liao, Shigeng Zhang, Jiannong Cao, Weiping Wang, Jianxin Wang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

18 Citations (Scopus)

Abstract

Target coverage is an important problem in wireless sensor networks (WSNs), whose goal is to cover points of interest to collect data for further processing. With the emergence of mobile sensors, many researchers have exploited the mobility of sensors to improve coverage quality. However, little attention has been paid to minimize the sensor's movement, which consumes the majority of a sensor's limited energy. Since sensors have limited energy supply and their operation continues until their energy drains, movement of mobile sensors should be minimized to extend the lifetime of sensors. In this paper, we first formulate the problem of minimizing sensor's movement to achieve target coverage (MMTC), and prove it is at least NP-complete. Then for a special case of MMTC when targets are spacing greater than twice of the coverage radius, we transform MMTC into a typical assignment problem, and get the optimal solution by an extended Hungarian method. For general cases of MMTC, we further propose a target based Voronoi greedy algorithm (TV-Greedy) to find approximate optimal solutions. Analysis results show that TV-Greedy has a low complexity, can enhance the robustness of WSNs to sensor failure. Extensive simulations are conducted to evaluate our solutions, which exhibit good performance in large-scale WSNs.
Original languageEnglish
Title of host publicationProceedings - 32nd IEEE International Conference on Distributed Computing Systems Workshops, ICDCSW 2012
Pages194-200
Number of pages7
DOIs
Publication statusPublished - 24 Sep 2012
Event32nd IEEE International Conference on Distributed Computing Systems Workshops, ICDCSW 2012 - Macau, China
Duration: 18 Jun 201221 Jun 2012

Conference

Conference32nd IEEE International Conference on Distributed Computing Systems Workshops, ICDCSW 2012
CountryChina
CityMacau
Period18/06/1221/06/12

Keywords

  • multi-hop relay
  • placement
  • WiMAX mesh network

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Control and Systems Engineering

Cite this