ارائه یک الگوریتم متمرکز مبتنی بر نمودار ورونوی برای تشخیص حفره در شبکه های حسگر بی سیم

نویسندگان

تحصیلات تکمیلی علوم پایه زنجان

چکیده

یکی از چالش‌های مهم در شبکه‌های حسگر بی‌سیم، تشخیص و محاسبه مساحت حفره‌ها در محیط می‌باشد. حفره‌ها‌ به دلایل مختلفی از جمله مرگ تصادفی حسگرها، انفجار در محیط و یا تمام شدن انرژی حسگرها در شبکه‌های حسگر بی-سیم ایجاد می‌گردند و وظیفه نظارتی شبکه‌های حسگر بی‌سیم را مختل می‌کنند. زمانی که حسگرها به صورت تصادفی در مناطقی مانند جنگل‌های متراکم و زمین‌های ناهموار قرار می‌گیرند، تشخیص حفره به صورت دستی در محیط امکان-پذیر نیست. به همین دلایل هدف ما در این مقاله ارائه یک الگوریتم متمرکز برای تشخیص و محاسبه مساحت حفره‌ها در محیط، با استفاده از رویکردهای هندسه محاسباتی است. ما در این مقاله مسئله تشخیص حفره را با در نظر گرفتن دو حالت بررسی می‌کنیم: 1- هنگامی که محیط شامل مانع نباشد و فقط مجموعه‌ای از حسگرها با شعاع متفاوت در محیط قرار گرفته باشند. 2- علاوه بر حسگرهای موجود در محیط، ناحیه موردنظر شامل مجموعه‌ای از موانع نیز باشد. در هر دو حالت الگوریتم‌های کارآیی ارائه داده و با استفاده از رویکردهای هندسه محاسباتی بعد از تشخیص حفـره‌های موجود در محیط، مساحت هر حفره را همراه با یال‌های مرزی به صورت دقیق گزارش می‌کنیم. پیچیدگی الگوریتم در حالت بدون مانع O(n 〖log〗^2 n) و در حالت با مانع O(n 〖log〗^2 n+nm^2) است و نتایج حاصل از شبیه‌سازی نشان می‌دهد که الگوریتم‌های ارائه شده حفره‌های موجود در محیط را به درستی تشخیص می‌دهند. در نتیجه، ما الگوریتم ارائه شده در حالت (1) را با یکی از الگوریتم‌های جدید ارائه شده مقایسه می‌کنیم. نتایج حاصل از شبیه-سازی کارا و دقیق بودن الگوریتم ما را نشان می‌دهد.

کلیدواژه‌ها


  1. L. Wei and W. Zhang, “Coverage hole and boundary nodes detection in wireless sensor networks,” Journal of Network and Computer Applications, vol. 48, pp. 35-43, 2015.
  2. M. Davoodi, E. Delfaraz, and S. Ghobadi, “Handoff Minimization in Wireless Networks With Group Mobility,” Journal of Electronical and Cyber Defence, vol. 4, no. 3, Serial No.15, 2016.
  3. K. Zhiping, H. Yu, and Q. Xiong, “Detection and recovery of coverage holes in wireless sensor networks,” Journal of Networks 8.4, pp. 822-828, 2013.
  4. Kalwaghe, N. Samidha, and A. V. Dusane, “Literature Review on Hole Detection and Healing in Wireless Sensor Network,” International Journal of Current Engineering and Technology 4.6, pp. 4184-4188, 2014.
  5. A. Ghosh, “Estimating coverage holes and enhancing coverage in mixed sensor networks,” Local Computer Networks, 29th Annual IEEE International Conference on, IEEE, 2004.
  6. P. K. Sahoo and W.-C. Liao, “HORA: A Distributed Coverage Hole Repair Algorithm for Wireless Sensor Networks,” Mobile Computing, IEEE Transactions on 14.7, pp. 1397-1410, 2015.
  7. P. Corke, R. Peterson, and D. Rus, “Finding holes in sensor networks,” In: Proceedings of the IEEE workshop on omniscient space: robot control, 2007.
  8. F. Li, B. Zhang, and J. Zheng, “Geographic hole-bypassing forwarding protocol for wireless sensor networks,” IET Commun, vol. 5, no. 6, pp. 737–44, 2011.
  9. J. Kanno, J. G. Buchart, R. R. Selmic, and V. Phoha, “Detecting coverage holes in wireless sensor networks,” In: Proceedings of the 17th mediterranean conference on control & automation, Greece, June 2009.
  10. B. Tong and W. Tavanapong, “On discovering sensing coverage holes in large-scale sensor networks,” Tech. Rep. TR 06-03, Computer Science, Iowa State University, March 2006.
  11. D. Du, F. Hwang, and S. Fortune, “Voronoi diagrams and Delaunay triangulations,” Euclidean Geometry and Computers, 1992.
  12. F. Aurenhammer, “Voronoi diagrams, a survey of a fundamental geometric data structure,” ACM Computing Surveys (CSUR) 23.3, pp. 345-405, 1991.
  13. G. Wang, G. Cao, and T. LaPorta, “A bidding protocol for deploying mobile sensors,” Network Protocols, 2003 Proceedings, 11th IEEE International Conference on, IEEE, 2003.
  14. G. Wang, G. Cao, and T. LaPorta, “Movement-assisted
  15. sensor deployment,” Mobile Computing, IEEE Transactions on 5.6, pp. 640-652, 2006.
  16. S. Babaie and S. S. Pirahesh, “Hole detection for increasing coverage in wireless sensor network using triangular structure,” arXiv preprint arXiv: 1203.3772, 2012.
  17. Fekete, P. Sandor, et al., “Neighborhood-based topology
  18. recognition in sensor networks, “Algorithmic Aspects of
  19. Wireless Sensor Networks, Springer Berlin Heidelberg, pp. 123-136, 2004.
  20. R. Ghrist and A. Muhammad, “Coverage and hole-detection in sensor networks via homology,” Proceedings of the 4th international symposium on Information processing in sensor networks, IEEE Press, 2005.
  21. V. De Silva, R. Ghrist, and A. Muhammad, “Blind Swarms for Coverage in 2-D,” Proc. Robotics: Science and Systems, pp. 335-342, June 2005.
  22. X. Li, D. K. Hunter, and K. Yang, “WLC12-1: Distributed coordinate-free hole detection and recovery,” Global Telecommunications Conference, GLOBECOM'06, IEEE, 2006.
  23. X. Li and D. K. Hunter, “Distributed coordinate-free hole recovery,” Communications Workshops, ICC Workshops' 08. IEEE International Conference on. IEEE, 2008.
  24. P. K. Sahoo, J.-Z. Tsai, and H.-L. Ke, “Vector method based coverage hole recovery in wireless sensor networks,” Communication Systems and Networks (COMSNETS), 2010 Second International Conference on. IEEE, 2010.
  25. H.-C. Ma, P. K. Sahoo, and Y.-W. Chen, “Computational geometry based distributed coverage hole detection protocol for the wireless sensor networks,” Journal of network and computer applications 34.5, pp. 1743-1756, 2011.
  26. C. Zhang, Y. Zhang, and Y. Fang, “Detecting coverage boundary nodes in wireless sensor networks,” Networking, Sensing and Control, 2006. ICNSC'06, Proceedings of the 2006 IEEE International Conference on, IEEE, 2006.
  27. K. Bi et al., “Topological hole detection in sensor networks with cooperative neighbors,” Systems and Networks Communications, 2006. ICSNC'06, International Conference on, IEEE, 2006.
  28. S. Funke, “Topological hole Detection in wireless sensor networks and its applications,” Proceedings of the 2005 joint workshop on foundations of mobile computing, ACM, 2005.
  29. S. Funke and C. Klein, “Hole detection or: how much geometry hides in connectivity,” Proceedings of the twenty-second annual symposium on Computational geometry, ACM, 2006.
  30. M. Sharir, “Intersection and closest-pair problems for a set of planar discs,” SIAM J. Comput., vol. 14, no. 2, pp. 448-468, 1985.