Abstract | ||
---|---|---|
The target coverage problem in wireless sensor networks is concerned with maximizing the lifetime of the network while continuously monitoring a set of targets. We add a QoS requirement to the target coverage such that the targets are covered by more than one sensor at any time. Given an integer vector Q, where q i is the minimum number of sensors to simultaneously cover targets i , the problem becomes Q-coverage problem. In this paper, we study the target Q-coverage problem. The objective is to maximize sensor network lifetime satisfying Q-coverage requirement. The problem is shown to be NP-complete and there is no known practical algorithm. We propose a heuristic and show that the proposed algorithm yields solution very near to the optimal solution. Our algorithm has two important features. It uses a greedy heuristic to generate Q-covers by prioritizing sensors in terms of the residual battery life and the algorithm assigns a small constant of lifetime to Q-covers so generated. In this process, it allows the sensors to participate in many Q-covers. We observe that the smaller the constant, the closer is the solution to optimal solution. Through experiments on randomly generated problem instances, we show that the proposed algorithm yields near-optimal solution. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1007/978-3-540-92295-7_39 | ICDCN |
Keywords | Field | DocType |
target coverage problem,optimal solution,proposed algorithm yields solution,problem instance,proposed algorithm yield,practical algorithm,near-optimal solution,q-coverage problem,target q-coverage problem,wireless sensor networks,q-coverage requirement,energy efficiency,greedy heuristic,satisfiability,sensor network,wireless sensor network | Residual,Key distribution in wireless sensor networks,Mathematical optimization,Heuristic,Efficient energy use,Computer science,Brooks–Iyengar algorithm,Quality of service,Greedy algorithm,Wireless sensor network,Distributed computing | Conference |
Volume | ISSN | Citations |
5408 | 0302-9743 | 27 |
PageRank | References | Authors |
1.07 | 7 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Manju Chaudhary | 1 | 30 | 1.46 |
Arun K. Pujari | 2 | 420 | 48.20 |