Abstract
Wireless sensor networks have posed a number of challenging problems such as localization, deployment and tracking, etc. One of the interesting problems is the calculation of the coverage and exposure paths for the sensor networks. This paper presents a fully localized algorithm to solve the worst coverage problem first introduced by Meguerdichian et al. The nodes of the sensor network cooperate to construct the worst coverage path only by the one-hop neighbor’s information, thus avoiding the massive communication and conserving the energy. The correctness of the proposed algorithm is proved formally under the sensing diminishing model. Moreover, this algorithm can be easily extended to solve the minimal exposure problem with local information as well.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Meguerdichain S, Koushanfar F, Potkonjak M et al. Coverage problems in wireless ad-hoc sensor networks. In Proc. IEEE INFOCOM, 20th Annual Joint Conference of IEEE Computer and Communications Societies Alaska, Apr. 22–26, 2001, pp.1380–1387.
Li X Y, Wan P J, Frieder O. Coverage in wireless ad hoc sensor networks. IEEE Trans. Computers, Jun. 2003, 51(6): 753–763.
Meguerdichian S, Slijepcevic S, Karayan V et al. Localized algorithm in wireless ad hoc networks: Location discovery and sensor exposure. In Proc. The 2nd ACM Int. Symp. Mobile Ad Hoc Networking and Computing (MobiHOC), Long Beach, CA, USA, Oct. 4–5, 2001, pp.106–116.
Meguerdichain S, Koushanfar F, Qu G et al. Exposure in wireless ad-hoc sensor network. In Proc. The 7th Annual Int. Conf. Mobile Computing and Networking, Jul. 16–21, 2001, Rome, Italy, pp.139–150.
Fortune S. Voronoi diagrams and Delaunay triangulations. Computing in Euclidean Geometry, F K Hwang, D Z Du (eds.), Singapore: World Scientific, 1992, pp.192–233.
Edesnrunner H. Algorithm in Combinatorial Geometry. Springer-Verlag, 1987.
Preparata F P, Shamos M I. Computational Geometry: An Introduction. Spring-Verlag, 1985.
Marengoni M, Draper B A, Hanson A et al. System to place observer on a polyhedral terrain in polynomial time. Image and Vision Computing, Dec. 1996, 18(6): 773–780.
Mehta D P, Lopez M A, Lin L. Optimal coverage paths in ad-hoc sensor networks. In IEEE Int. Conf. Communications, Anchroage, Alaska, May 11–15, 2003, pp.507–511.
Xu H L, Huang L S, Wan Y Y et al. Localized algorithm for coverage in wireless sensor networks. In 6th Int. Conf. Parallel and Distributed Computing, Application and Technologies, Dalian, China, Dec. 5–8, 2005, pp.750–754.
Veltri G, Huang Q, Qu G et al. Minimal and maximal exposure path algorithms for wireless embedded sensor networks. In Proc. The 1st Int. Conf. Embedded Networked Sensor Systems (SenSys'03), Loc Angeles, USA. Nov. 5–7, 2003, pp.40–50.
Cormen T H, Leiserson C E, Rivest R L. Introduction to Algorithms. MIT Press and McGraw-Hill, 1990.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by China Next Generation Internet Program (Grant No. CNGI-04-10-2A).
Rights and permissions
About this article
Cite this article
Huang, LS., Xu, HL., Wang, Y. et al. Coverage and Exposure Paths in Wireless Sensor Networks. J Comput Sci Technol 21, 490–495 (2006). https://doi.org/10.1007/s11390-006-0490-1
Received:
Issue Date:
DOI: https://doi.org/10.1007/s11390-006-0490-1