|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Session 8A: Coverage and Connectivity
|
|
|
|
|
Title:
|
Target Coverage Problem in Wireless Sensor Networks: A Column Generation Based Approach
|
|
|
|
|
Author(s):
|
Yu Gu, USTC, P.R. China ; Jie Li, University of Tsukuba, Japan; Baohua Zhao, Department of Computer Science in the University of Science and Technology of China, P.R. China; Yusheng Ji, National Institute of Informatics, Japan
|
|
|
|
|
Abstract:
|
Target coverage problem in wireless sensor networks remains quite a challenge. Due to nonlinear nature, previous work has mainly focused on heuristic algorithms, which remain difficult to characterize and have no performance guarantee. Therefore, no theoretical result is known yet. To fill in the blank, this paper offers two major theoretical results.
The first result is two lifetime upper bounds, which could be used to justify performance of previously proposed heuristic algorithms. One upper bound is based on the relaxation and reformulation technique while the other is derived by relaxing coverage constraints, e.g. from that every target should be covered by at least $K(K>0)$ sensors at any given moment, to that every target should be covered by at least $K$ sensors on average. We study the interesting connection between those two bounds and thus endow them with physical meanings.
Considering that an optimal algorithm for the target coverage problem is of great value, we propose the second result: a column generation based (CG) approach. The objective is to find an optimal schedule, defined as a time table specifying from what time up to what time which sensor watches which targets while the maximum lifetime has been obtained. We also offer an in-depth theoretic analysis as well as several novel techniques to further optimize the approach. Numerical results not only demonstrate that the lifetime upper bounds are very tight, but also verify that the proposed CG based approach constantly yields the optimal or near optimal solution.
|
|
|
|
|
|
|
|
|
