Provisioned Placement of Directional Sensors for Covering Stationary Targets
Directional sensor networks have been increasingly deployed in various contexts or environments such as banks, warehouses and museums. Directional sensors, in contrast to normal omnidirectional sensors, are characterized with limited sensing angles, and their sensing region is thus usually modeled by sectors. This paper considers the provisioned deployment of directional sensors for covering a fixed number of stationary discrete targets in a two-dimensional field. Minimizing the number of directional sensors used is desirable for financial concerns. Such minimization is formulated as an Integer Linear Programming problem, which is then proved to be NP-complete. Subsequently, three approximation algorithms named Induction, LP-based and Randomized are proposed in turn. Finally simulation results are given to compare the performance of the three approximation algorithms as well as the classic greedy algorithm.
Jian Wang Na Guo Heng Luo
Department of Network Engineering Shanghai Second Polytechnic University Shanghai, China Shanghai Meida Info Company Shanghai, China Department of Computer Science Shanghai Jiaotong University Shanghai, China
国际会议
太原
英文
24-31
2010-10-22（万方平台首次上网日期，不代表论文的发表时间）