Experimental Analysis of Capacity Aware Tree Based Topology Control Algorithms for Wireless Sensor Networks

Öz

Communication is the most important factor in the energy consumption of sensor nodes running on wireless sensor networks (WSNs). Densely connected networks are transformed into a sparsely connected network to minimize communication and provide energy efficiency. One of the methods used for the transformation is topology control. Topology control method generally provides a spanning tree for WSNs. The problem that aims to find the minimum spanning tree that provides capacity constraint is the capacitated minimum spanning tree (CMST) problem. Balancing the loads of subtrees affects the number of messages in the network and henceforth the energy-efficiency. In this study, we analyze the performance and load-balancing performance between subtrees of CMST algorithms on WSNs. The central CENTEW and distributed MCO algorithms developed based on the Esau-Williams algorithm are compared in terms of load balancing performance, sent and received message size, spent energy and elapsed time on TOSSIM simulator. According to the experimental results on 250-node networks, CENTEW uses less than 3.98 times less energy than MCO, although it consumes less time. The distributed CMST approach is energy-efficient and balances load more evenly.

Anahtar Kelimeler

• Wireless Sensor Networks
• Capacitated Minimum Spanning Tree Problem
• Energy Efficient and Load Balanced Networks
• Network Design
• Topology Control
• Esau-Williams Heuristic

Kapasite Farkında Topoloji Kontrol Algoritmalarının Telsiz Duyarga Ağlarında Deneysel Analizi

Öz

Haberleşme, telsiz duyarga ağları (TDA’lar) üzerinde çalışan duyarga düğümlerinin enerji tüketiminde en önemli etmendir. Haberleşmeyi en aza indirip, enerji etkinliği sağlamak amacıyla yoğun bağlı ağlar, seyrek bağlı bir ağa dönüştürülür. Bu dönüşüm için kullanılan yöntemlerden biri de topoloji kontrolüdür. Topoloji kontrolü yöntemiyle genelde TDA’lar için kapsayan ağaç oluşturulmaktadır. Kapsayan ağaçlardan kapasite kısıtını sağlayan, en düşük maliyetli ağacı bulmayı hedefleyen problem, kapasite kısıtlı en küçük ağaç (KEKA) problemidir. Alt ağaçların arasındaki yük dengesi, ağdaki mesaj sayısını ve enerji etkinliğini etkilemektedir. Bu çalışmada, TDA’lar üzerinde KEKA algoritmalarının performansı ve yük dengesi analiz edilmiştir. Esau-Williams algoritması referans alınarak geliştirilen merkezi CENTEW ve dağıtık MCO algoritmaları TOSSIM simülatörü üzerinde yük dengesi, gönderilen ve alınan mesaj boyutu, harcanan enerji ve geçen zaman kapsamlarında karşılaştırılmıştır. 250 düğümlük ağlar üzerinde yapılan deneysel sonuçlara göre CENTEW daha az zaman harcamasına rağmen MCO, 3,98 kat daha az enerji kullanmaktadır. Dağıtık KEKA yaklaşımının enerji-etkin olduğu ve yük dengesini sağladığı görülmüştür.

Anahtar Kelimeler

• Telsiz Duyarga Ağları
• Kapasite Kısıtlı Kapsayan En Küçük Ağaç Problemi
• Enerji Etkin ve Dengeli Ağlar
• Ağ Tasarımı
• Topoloji Kontrolü
• Esau-Williams Sezgiseli

Kaynakça

1. [1] Erciyes, K., Dagdeviren, O., Coskulu, D., Modeling and simulation of wireless sensor and mobile ad hoc networks, International conference on modellimg and simulation, 2006.
2. [2] Papadimitriou, C. H., The complexity of the capacitated tree problem, Networks, 8(3), pp. 217-230, 1978.
3. [3] Ruiz y Ruiz, H. E., The capacitated minimum spanning tree problem, PhD Thesis, Universitat Politecnica de Catalunya, 2013.
4. [4] Aşçı, M., İleri, C. U., Dağdeviren, O., An energy-efficient capacitated minium spanning tree algorithm for ropology control in Wireless Sensor Networks, 2017 25th Signal Processing and Communications Applications Conference (SIU), pp. 1-4, 2017.
5. [5] Deif, D., Gadallah, Y., Reliable wireless sensor networks topology control for critical internet of things applications, 2018 IEE Wireless Communications and Networking Conference (WCNC), pp. 1-6, 2018.
6. [6] Dubey, T. K., Mathur, R., Chouhan, D. N., Localization independent aspects of topology control in wireless sensor networks, Optical and Wireless Tech., Springer Singapore, pp. 1-6, 2018.
7. [7] Santi, P., Topology control in wireless ad hoc and sensor networks, ACM Comput. Surv., 37(2), pp. 164-194, 2005.
8. [8] Li, M., Li, Z., Vasilakos, A. V., A survey on topology control in wireless sensor networks: Taxonomy, comparative, study, and open issues, Proc of the IEEE, 101(12), pp. 2538-2557, 2013.

9. [9] Yun, D., Qingjun, Z., Xiaohui, C., Research on topology algorithm in heterogeneous wireless sensor networks based on the game theory, Proceedings of the 3rd International Conference on Intelligent Information Processing, ACM, pp. 112-119, 2018.
10. [10] Nayak, M. R., Tripathy, G., Rath, A. K., A distributed transmission power efficient fault-tolerant topology management mechanism for nonhomogeneous wireless sensor network, Progress in Advanced Comp. and Intelligent Eng., Springer Singapore, pp. 481-493, 2018.
11. [11] Chandy, K. M., Lo, T., The capacitated minimum spanning tree, Networks, 3(2), pp. 173-181, 1973.
12. [12] Esau, L. R., Williams K. C., On teleprocessing system design, part ii: A method for approximating the optimal network, IBM Systems Journal, 5(3), pp. 142-147, 1966.
13. [13] Lee, Y. J., Atiquzzaman, M., Least cost heuristic for the delay-constrained capacitated minimum spanning tree problem, Computer Communications, 28(11), pp. 1371-1379, 2005.
14. [14] Öncan, T., Altınel, İ. K., Parametric enhancements of the esau-williams heuristic for the capacitated minimum spanning tree problem, Journal of the Operational Research Society, 60(2), pp. 259-267, 2009.
15. [15] Battarra, M., Öncan, T., Altınel, I., Golden, B., Vigo, D., Phillips, E., An evolutionary approach for tuning parametric esau and williams heuristics, Journal of the Operational Research Society, 63(3), pp. 368-378, 2012.
16. [16] Campos, J., Martins, A., Souza, M., A hybrid vns algorithm for solving the multi-level capacitated minimum spanning tree problem, Electronic Notes in Discrete Mathemathics, 66, pp. 159-166, 2018.
17. [17] Kawatra, R., Bricker, D., A multiperiod planning model for the capacitated minimal spanning tree problem, European Journal of Operational Research, 121(2), pp. 412-419, 2000.
18. [18] Öncan, T., Design of capacitated minimum spanning tree with uncertain cost and demand parameters, Information Sciences, 177(20), pp. 4354-4367, 2007.
19. [19] de Souza, M. C., Duhamel, C., Ribeiro, C. C., A grasp heuristic for the capacitated minimum spanning tree problem using a memory-based local search strategy, Metaheuristics: Computer decision-making, Springer, pp. 627-657, 2003.
20. [20] Ahuja, R. K., Orlin, J. B., Sharma, D., Multi-excahnge neighborhood structures fort he capacitated minimum spanning tree problem, Math. Programming, 91(1), pp. 71-97, 2001.
21. [21] Ahuja, R. K., Orlin, J. B., Sharma, D., New neighborhood search structures for the capacitated minimum spanning tree problem, Technical Report by Massachusetts Inst. of Tech., Sloan School of Management, 1998.
22. [22] Reimann, M., Laumanns, M., A hybrid aco algorithm for the capacitated minimum spanning tree problem, Hybrid Metaheuristics, pp. 1-10, 2004.
23. [23] Martins, P., Enhanced second order algorithm applied to the capacitated minimum spanning tree problem, Computers & operations research, 34(8), pp. 2495-2519, 2007.
24. [24] Gamvros, I., Raghavan, S., Golden, B., An evolutionary approach to the multi-level capacitated minimum spanning tree problem, Telecommunications Network Design and Management, Springer, pp. 99-124, 2003.
25. [25] Ruiz, E., Albareda-Sambola, M., Fernandez, E., Resende, M. G., A biased random-key genetic algorihtm for the capacitated minimum spanning tree problem, Computers & Operations Research, 57, pp. 95-108, 2015.
26. [26] Levis, P., Lee, N., Welsh, M., Culler, D., Tossim: Accurate and scalable simultaion of entire tinyos applications, Proceedings of the 1st Inter. Conference on Embedded Networked Sensor Systems, ACM, pp. 126-137, 2003.
27. [27] Erciyes, K., Dagdeviren, O., Cokuslu, D., Yilmaz, O., Gumus, H., Mobile ad hoc networks: Current status and Future trends, CRC Press, 2010.
28. [28] Akram, V. K., Dagdeviren, O., DECK: A distributed, asynchronous and exact k-connectivity detection algorithm for Wireless Sensor Networks, Computer Communications, 116, pp. 9-20, 2018.