A dual approach for the worst-case-coverage deployment problem in ad-hoc wireless sensor networks

Rung-Hung Gau*, Yi Yang Peng

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

10 Scopus citations

Abstract

In this paper, we propose and evaluate algorithms for solving the worst-case-coverage deployment problem in ad-hoc wireless sensor networks. The worst-case-coverage deployment problem is to deploy additional sensors in the wireless sensor field to optimize the worst-case coverage. We derive a duality theorem that reveals the close relation between the maximum breach path and the minimum Delaunay cut. The duality theorem is similar to the well-known max-flow-min-cut theorem in the field of network optimization. The major difference lies in the fact that the object function we study in this paper is nonlinear rather than linear. Based on the duality theorem, we propose an efficient dual algorithm to solve the worstcase-coverage deployment problem. In addition, we propose a genetic algorithm for deploying a number of additional sensors simultaneously. We use analytical proofs and simulation results to justify the usage of the proposed approaches.

Original languageEnglish
Title of host publication2006 IEEE International Conference on Mobile Ad Hoc and Sensor Sysetems, MASS
PublisherIEEE Computer Society
Pages427-436
Number of pages10
ISBN (Print)1424405076, 9781424405077
DOIs
StatePublished - 1 Jan 2006
Event2006 IEEE International Conference on Mobile Ad Hoc and Sensor Sysetems, MASS - Vancouver, BC, Canada
Duration: 9 Oct 200612 Oct 2006

Publication series

Name2006 IEEE International Conference on Mobile Ad Hoc and Sensor Systems, MASS
Volume1

Conference

Conference2006 IEEE International Conference on Mobile Ad Hoc and Sensor Sysetems, MASS
CountryCanada
CityVancouver, BC
Period9/10/0612/10/06

Keywords

  • Delaunay triangles
  • Duality
  • Sensor networks
  • Voronoi diagram
  • Worst-case coverage

Fingerprint Dive into the research topics of 'A dual approach for the worst-case-coverage deployment problem in ad-hoc wireless sensor networks'. Together they form a unique fingerprint.

Cite this