Abstract
We study a novel “coverage by directional sensors” problem with tunable orientations on a set of discrete targets. We propose a Maximum Coverage with Minimum Sensors (MCMS) problem in which coverage in terms of the number of targets to be covered is maximized whereas the number of sensors to be activated is minimized. We present its exact Integer Linear Programming (ILP) formulation and an approximate (but computationally efficient) centralized greedy algorithm (CGA) solution. These centralized solutions are used as baselines for comparison. Then we provide a distributed greedy algorithm (DGA) solution. By incorporating a measure of the sensors residual energy into DGA, we further develop a Sensing Neighborhood Cooperative Sleeping (SNCS) protocol which performs adaptive scheduling on a larger time scale. Finally, we evaluate the properties of the proposed solutions and protocols in terms of providing coverage and maximizing network lifetime through extensive simulations. Moreover, for the case of circular coverage, we compare against the best known existing coverage algorithm.
Article PDF
We’re sorry, something doesn't seem to be working properly.
Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.
Avoid common mistakes on your manuscript.
References
Slijepcevic S, Potkonjak M (2001) Power efficient organization of wireless sensor networks, in IEEE International Conference on Communications (ICC), Helsinki, Finland, Vol. 2, pp. 472–476
Tian D, Georganas ND (2002) A coverage-preserving node scheduling scheme for large wireless sensor networks, in Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), Atlanta, GA, United States, pp. 32–41
Wang X, Xing G, Zhang Y, Lu C, Pless R, and Gill C (2003) Integrated coverage and connectivity configuration in wireless sensor networks, in Proceedings of the First International Conference on Embedded Networked Sensor Systems (SenSys), Los Angeles, CA, United States, pp. 28–39
Zhang H, Hou JC (2005) Maintaining sensing coverage and connectivity in large sensor networks, The Wireless Ad Hoc and Sensor Networks: An International Journal
Cardei M, Du DZ (2005) Improving wireless sensor network lifetime through power aware organization, ACM Wireless Networks 11:333–340
Megrian S, Potkonjak M (2003) Low power 0/1 coverage and scheduling techniques in sensor networks, University of California, Los Angeles, Department of Computer Science, Tech. Rep. 030001
Cardei M, Thai MT, Li Y, Wu W (2005) Energy-efficient target coverage in wireless sensor networks, in Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Vol. 3, Miami, FL, United States, March, 1976–1984
Cheng MX, Ruan L, Wu W, (2005) Achieving minimum coverage breach under bandwidth constraints in wireless sensor networks, in Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Vol. 3: Miami, FL, United States, pp. 2638–2645
Hochbaum DS (1997) Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. Approximation Algorithms for NP-hard Problems. PWS
He T, Huang C, Blum BM, Stankovic JA, Abdelzaher T (2003) Range-free localization schemes in large-scale sensor networks, in Proceedings of the Annual International Conference on Mobile Computing and Networking (MOBICOM), San Diego, CA, United States, pp. 81–95
“Ilog cplex” version 9.0. “[Online]. Available: http://www.ilog.com/products/cplex/”
Feeney LM, Nilsson M (2001) Investigating the energy consumption of a wireless network interface in an ad hoc networking environment, in Proceedings of 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Vol. 3: Anchorage, AK, United States, pp. 1548–1557
Yan T, He T, Stankovic J (2003) Differentiated surveillance for sensor networks, in Proceedings of the First International Conference on Embedded Networked Sensor Systems (SenSys), Los Angeles, CA, United States, pp. 51–62
Ye F, Zhong G, Cheng J, Lu S, Zhang L (2003) Peas: A robust energy conserving protocol for long-lived sensor networks, in Proceedings of 23rd International Conference on Distributed Computing Systems (ICDCS), Providence, RI, United States, pp. 28–37
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ai, J., Abouzeid, A.A. Coverage by directional sensors in randomly deployed wireless sensor networks. J Comb Optim 11, 21–41 (2006). https://doi.org/10.1007/s10878-006-5975-x
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10878-006-5975-x