Steiner Zone Yaklaşımı İle Bölünmüş Kablosuz Algılayıcı Ağlarda Hareketli Veri Toplama

Year 2020, Volume: 13 Issue: 3, 217 - 224, 31.07.2020

İzzet Şenturk

https://doi.org/10.17671/gazibtd.660517

Cited By: 1

Abstract

Kablosuz algılayıcı ağlar genellikle zorlu çevresel koşullar altında faaliyetlerini sürdürürler. Donanımsal kısıtlar ve olumsuz kuşatanlar ağı oluşturan düğümleri kayıplara maruz bırakır. Ortaya çıkan hasarın boyutuna bağlı olarak ağ içerisinde, ağın geri kalanından yalıtılmış ayrık bağlı bileşenler ortaya çıkabilir. Bu tür durumlarda ağ bağlantısının hızlı ve tepkin şekilde onarılması için hareketli veri toplayıcılarından (HVT) faydalanılabilir. HVT, parçalanmış ağdaki bağlı bileşenleri belirli aralıklarla ziyaret ederek toplanan verilerin iletilmesine olanak sağlar. Çok-sekmeli yol atamanın mümkün olması, parçalanmış bir ağdan kablosuz veri iletimi ile veri toplayacak maliyet-etkin güzergahın tespiti problemini karmaşıklaştırmaktadır. Bu makale, belirtilen veri toplama problemini Yeterince Yakın Gezgin Satıcı Problemi (YYGSP) olarak ele alarak Steiner zone yaklaşımı ile her bir ağ parçası için ilgili veri toplama noktasını tayin eder. Önerilen yöntemin başarımının değerlendirilmesi için ziyaret edilen veri toplama noktalarının sayısı ve HVT’nin toplam seyahat mesafesi ölçülmüştür. Elde edilen sonuçlar, önerilen yöntemin, veri toplama noktalarının sayısını %67, toplam seyahat mesafesini ise %42 düşürdüğünü göstermektedir.

Keywords

KAA, bağlantının onarımı, hareketli veri toplama, yeterince yakın gezgin satıcı problemi, güzergah planlama

Supporting Institution

TÜBİTAK

Project Number

EEEAG-177050

A Steiner Zone Approach for Mobile Data Collection in Partitioned Wireless Sensor Networks

Abstract

Wireless sensor networks (WSNs) typically operate in harsh environmental conditions. Hardware constraints and external damage from inhospitable surroundings leave the nodes susceptible to node failures. Depending on the damage scale, the network can be subject to partitioning which segments the network into multiple isolated connected components. A prompt reactive approach to restore network connectivity is to employ a mobile data collector (MDC) that visits and collects data from partitions periodically. Availability of the wireless data communication through multi-hop routing in a partitioned network complicates designating the shortest possible route for data collection. This paper regards the mentioned data collection problem as the Close-enough Traveling Salesman Problem (CETSP) and employs Steiner zone approach to designate respective data collection points for corresponding partitions. We have assessed the proposed approach in terms of the number of points visited for data collection and the total travel distance of the MDC. Obtained results indicate that the proposed approach can reduce the number of data collection points up to 67% and total travel distance up to 42%.

Keywords

WSN, connectivity restoration, mobile data collection, close-enough traveling salesman problem, route planning

Project Number

EEEAG-177050

References

• I. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, “Wireless Sensor Networks: A Survey”, Computer Networks, 38(4), 393-422, 2002.
• W. K. G. Seah, Z. A. Eu, H. Tan, “Wireless Sensor Networks Powered by Ambient Energy Harvesting (WSN-HEAP) - Survey and Challenges”, 1st International Conference on Wireless Communication, Vehicular Technology, Information Theory and Aerospace Electronic Systems Technology, 1–5, May 2009.
• J. A. Gutierrez, M. Naeve, E. Callaway, M. Bourgeois, V. Mitter, B. Heile, “IEEE 802.15.4: A Developing Standard for Low-Power Low-Cost Wireless Personal Area Networks”, IEEE Network, 15(5), 12–19, 2001.
• M. A. Matin, M. M. Islam. “Overview of Wireless Sensor Network”, Wireless Sensor Networks-Technology and Protocols, 1-3, 2012.
• M. Younis, I. F. Senturk, K. Akkaya, S. Lee, F. Senel, “Topology Management Techniques for Tolerating Node Failures in Wireless Sensor Networks: A survey”, Computer Networks, 58, 254 – 283, 2014.
• I. F. Senturk, “Partition-aware Centrality Measures for Connectivity Restoration in Mobile Sensor Networks,”, International Journal of Sensor Networks, 30(1), 1–12, 2019.
• G. Gutin, A. P. Punnen, The Traveling Salesman Problem and Its Variations, Springer Science & Business Media, 12, 2006.
• T. Bektas, “The Multiple Traveling Salesman Problem: An Overview of Formulations and Solution Procedures”, Omega, 34(3), 209-219, 2006.
• C. E. Noon, J. C. Bean, “An Efficient Transformation of the Generalized Traveling Salesman Problem”, INFOR: Information Systems and Operational Research, 31(1), 39–44, 1993.
• A. Dumitrescu, J. S. Mitchell, “Approximation Algorithms for TSP with Neighborhoods in the Plane”, Journal of Algorithms, 48(1), 135–159, 2003.
• D. J. Gulczynski, J. W. Heath, C. C. Price, The Close Enough Traveling Salesman Problem: A Discussion of Several Heuristics, 271–283, Boston, MA: Springer US, 2006.
• C. H. Papadimitriou, “The Euclidean Travelling Salesman Problem is NP-Complete”, Theoretical Computer Science, 4(3), 237-244, 1977.
• R. Bellman, “Dynamic Programming Treatment of the Travelling Salesman Problem”, J. Acm, 9(1), 61–63, 1962.
• G. Reinelt, The Traveling Salesman: Computational Solutions for TSP Applications, Berlin, Heidelberg: Springer-Verlag, 1994.
• I. F. Senturk, G. Y. Kebe, “A Novel Shortest Path Routing Algorithm for Wireless Data Collection in Transportation Networks”, 2019 International Conference on Computer Science and Engineering (UBMK), 280-284, 2019.
• W. K. Mennell, Heuristics for Solving Three Routing Problems: Close-enough Traveling Salesman Problem, Close-enough Vehicle Routing Problem, Sequence-dependent Team Orienteering Problem, Ph.D. Dissertation, 2009.
• Z. Kang, Z. Hong, H. Hu, Q. Xiong, G. Xu, “Multi-objective Optimized Connectivity Restoring of Disjoint Segments Using Mobile Data Collectors in Wireless Sensor Network”, J Wireless Com Network, 65, 2017.
• N. Ghosh, I. Banerjee, “An Energy-efficient Path Determination Strategy for Mobile Data Collectors in Wireless Sensor Network”, Computers and Electrical Engineering, 48(C), 417–435, 2015.
• U. Sharma, C. R. Krishna, T. P. Sharma, "An Efficient Mobile Data Collector Based Data Aggregation Scheme for Wireless Sensor Networks”, 2015 IEEE International Conference on Computational Intelligence & Communication Technology, 292-298, 2015.
• D. Kim, R. N. Uma, B. H. Abay, W. Wu, W. Wang, A. O. Tokuta, “Minimum Latency Multiple Data MULE Trajectory Planning in Wireless Sensor Networks”, IEEE Transactions on Mobile Computing, 13(4), 838-851, 2014.
• D. V. Le, H. Oh, S. Yoon, “A Novel Hierarchical Cooperative Data Gathering Architecture Using Multiple Mobile Elements”, Sixth International Conference on Ubiquitous and Future Networks, 522-527, 2014.
• Internet: OR-Tools, https://developers.google.com/optimization, 11.04.2020.