Return to search

Duality and Genetic Algorithms for the Worst-Case-Coverage Deployment Problem in Wireless Sensor Networks

In this thesis, 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 worst-case-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.

Identiferoai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0721105-140137
Date21 July 2005
CreatorsPeng, Yi-yang
ContributorsTsang-Ling Sheu, Rung-Hung Gau, Wei-Kuang Lai, Chun-Hung Lin, Jen-yi Pan
PublisherNSYSU
Source SetsNSYSU Electronic Thesis and Dissertation Archive
LanguageCholon
Detected LanguageEnglish
Typetext
Formatapplication/pdf
Sourcehttp://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0721105-140137
Rightsoff_campus_withheld, Copyright information available at source archive

Page generated in 0.0017 seconds