There are lots of applications where only periodic monitoring (sweep coverage) is sufficient instead of continuous monitoring. The main goal of sweep coverage problem is to minimize the number of mobile sensor nodes moving with uniform velocity required to guarantee coverage as per given sweep time. Sweep coverage problems are broadly categorized in three types depending on applications viz point sweep coverage, area sweep coverage and boundary sweep coverage. In this paper we have solved the problem of point sweep coverage, where a set of densely spaced points in the given region are periodically monitored using convex hull algorithm.

Sweep coverage problem; Area sweep coverage; Point sweep coverage; convex hull algorithm; Tessellation

[1] Gurbax Kaur, Ritesh Sharma, “A Review on Sweep Coverage in Wireless Sensor Networks”, International Journal of Computer Sciences and Engineering, Volume-4, Issue-6, Page No (113-117), June 2016, E-ISSN:2347-2693.
[2] Barun Gorian , Partha Sarthi Mandal,“Approximation algorithm for sweep coverage in wireless sensor networks ” ,Journal of Parallel and Distributed Computing , Volume-74, Issue-8, Page No(2699-2707), Aug 2014.
[3] Mo Li, Wei-Fang Cheng, Kebin Liu, Yunhao Liu,Xiang-Yang Li, Xiangke Liao, “Sweep coverage with mobile sensors”, Transaction on Mobile Computing , Volume-01, Issue-11, Page No (1534–1545), Nov 2011.
[4] Barun Gorian ,Partha Sarthi Mandal, “Point and area sweep coverage in wireless sensor networks”,11th International Symposium and Workshops on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), Tsukuba Science City, pp (140-145) ,May 13th-17th ,2013,ISBN : 978-1-61284-824-2.
[5] Nasimkhazan,Ali Braumandinia and Nima Ghazanfari Motlagh,“Node Placement and coverage in Asymmetric area”, International Journal of Advanced Research in Computer Science and Software Engineering, Volume-2, Issue-11, Page No (278-282), Nov 2012.
[6] R.A. Jarvis, “on the identification of the convex hull of a finite set of points in the plane”, Information Processing Letters, Volume-2, Issue-1, Page No (18-21), Dec 1973.
[7] Novella Bartolini, Tiziana Calamoneri, Emanuele G. Fusco, Annalisa Massini, Simone Silvestri , “ Push & pull: autonomous deployment of mobile sensors for a complete coverage”, Wireless Netw. , Volume-16, Issue-3, Page No (607–625), Jan 2009.
[8] Adrian Dumitrescu, MinghuiJiang, “Sweeping an oval to a vanishing point”, Elsevier: Discrete applied mathematics, Volume-159, Issue-14, Page No (1436-1442), Aug 2011.
[9] Edoardo S. Biagioni, Galen Sasaki,“Wireless sensor placement for Reliable and Efiicient data collection”,IEEE 36th Annual Hawaii International Conference on System Sciences, 2003. Proceedings of the - Big Island, HI, USA, January 6th-9th, 2003, ISBN: 0-7695-1874-5.
[10] Santosh kumar, Ten H .Lai, Anish Arora,“Barrrier coverage with wireless sensors”,Mobicom’05 Proceedings of the 11th annual international conference on Mobile computing and networking,Org by-ACM, NY, USA, pp(284-298) , August 28 , 2006 ,ISBN: 1-59593-020-5.
[11] Xiaojiang Du,Fengjing Lin, “Improving sensor network performance by deploying mobile sensors”,IEEE international performance, computing, and communications conference , Phoenix, AZ, USA ,pp(67-71),April 7th – 9th ,2005, ISBN: 0-7803-8991-3.
[12] Hung-Chi Chu, Wei-Kai Wang, Yong-Hsun Lai, “Sweep coverage mechanism for wireless sensor networks with approximate patrol times”, Ubiquitous Intelligence & Computing and 7th International Conference on Autonomic & Trusted Computing (UIC/ATC), Xian, Shaanxi, pp( 82–87) ,October 26th-29th,2010,ISBN: 978-0-7695-4272-0.
[13] Yi Ning Chen, Ko-Jui Lin ; Chang Wu Yu,”Dynamis coverage techniques in mobile wireless sensor networks” ,Fifth International Conference on Ubiquitous and Future Networks (ICUFN), Da Nang, pp(12-17), July 2nd -5th ,2013, ISSN:2165-8528.
[14] Min Xi, Kui Wu, Yong Qi, Jizhong Zhao, Yunhao Liu, Mo Li, “Run to potential:sweep coverage in wireless sensor networks” ,IEEE: International Conference on Parallel Processing (ICPP-2009),Sponsored by-IACC, Vienna , Austria , pp ( 50–57) ,September 22nd-25th , 2009 ,ISBN: 978-0-7695-3802-0.
[15] Gautam K. Das, Sandip Das, Subhas C. Nandy, Bhabani P. Sinha, “Efficient algorithm for placing a given number of base stations to cover a convex region”, Journal of. Parallel Distributed Computing,Volume- 66,Issue-11,Page No (1353 – 1358),July 2006.
[16] Junzhao Du,Yawei Li,Hui Liu and Kewai Sha, “ On sweep coverage with minimum mobile sensors”, 16th international conference on Parallel and Distributed System, Shanghai, pp(283-290). December 8th-10th, 2010, ISBN: 978-1-4244-9727-0.
[17] Fadi M. Al-Turjman, Hossam S. Hassanein, Mohamed A. Ibnkahla, “Connectivity optimization for wireless sensor networks applied to forest monitoring”, In: Proceedings of the IEEE International Conference on Communications, (ICC-09), IEEE Press, Piscataway, NJ, USA, pp( 285–290),June 14th-18th,2009, ISBN: 978-1-4244-3435-0.
[18] William F. Eddy, “A New Convex Hull Algorithm for Planar Sets”, ACM Transactions on Mathematical Software, Volume-3, Issue- 4, Page No (398-403), Dec 1977.
[19] Selim G. AKL,Godfried T.Toussaint, “A fast convex hull algorithm”, Information Processing Letter, Volume-7 , Issue-5,Page No(219-222),Aug 1978.
[20] A. Bykat, “Convex Hull Of A Finite Set Of Points In Two Dimensions”, Information Processing Letter, Volume-7, Issue-6, Page No (296-298), Oct 1978.
[21] Jack Sklansky “Finding the Convex Hull of Simple Polygon” Pattern Recognition Letters, Volume-1, Issue-2, Page No (79-83), Dec 1982.
[22] David Avis a, David Bremner, Raimund Seidel, “How good are convex hull algorithms?”, Computational Geometry ,Volume-7 ,Page No (265-301),1997.
[23] D.G.Anand,Dr.H.G.Chandrakanth,Dr.M.N.Giriprasad, “ Energy efficient coverage problems in wireless adhoc sensor networks”, Advanced Computing: An International Journal ( ACIJ ),Volume-2,Issue-2,Page No(42-50),March 2011.
[24] Ming Ma, Yuanyuan Yang, “Adaptive Triangular Deployment Algorithm for Unattended Mobile Sensor Networks”, Transactions on Computers, Volume-56, Issue-07, Page No (946-958), July 2007.