Research Article
BibTex RIS Cite

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

Year 2020, Volume: 13 Issue: 2, 32 - 46, 16.12.2020

Mustafa Aşçı Can İleri Orhan Dağdeviren

Abstract

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.

Keywords

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

Supporting Institution

TÜBİTAK

Project Number

215E115

Thanks

Bu çalışma, 215E115 nolu proje kapsamında TÜBİTAK tarafından desteklemiştir.

References

  • [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] Papadimitriou, C. H., The complexity of the capacitated tree problem, Networks, 8(3), pp. 217-230, 1978.
  • [3] Ruiz y Ruiz, H. E., The capacitated minimum spanning tree problem, PhD Thesis, Universitat Politecnica de Catalunya, 2013.
  • [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] 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] 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] Santi, P., Topology control in wireless ad hoc and sensor networks, ACM Comput. Surv., 37(2), pp. 164-194, 2005.
  • [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] 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] 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] Chandy, K. M., Lo, T., The capacitated minimum spanning tree, Networks, 3(2), pp. 173-181, 1973.
  • [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] 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] Ö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] 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] 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] 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] Öncan, T., Design of capacitated minimum spanning tree with uncertain cost and demand parameters, Information Sciences, 177(20), pp. 4354-4367, 2007.
  • [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] 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] 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] Reimann, M., Laumanns, M., A hybrid aco algorithm for the capacitated minimum spanning tree problem, Hybrid Metaheuristics, pp. 1-10, 2004.
  • [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] 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] 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] 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] Erciyes, K., Dagdeviren, O., Cokuslu, D., Yilmaz, O., Gumus, H., Mobile ad hoc networks: Current status and Future trends, CRC Press, 2010.
  • [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.

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

Year 2020, Volume: 13 Issue: 2, 32 - 46, 16.12.2020

Mustafa Aşçı Can İleri Orhan Dağdeviren

Abstract

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.

Keywords

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

Project Number

215E115

References

  • [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] Papadimitriou, C. H., The complexity of the capacitated tree problem, Networks, 8(3), pp. 217-230, 1978.
  • [3] Ruiz y Ruiz, H. E., The capacitated minimum spanning tree problem, PhD Thesis, Universitat Politecnica de Catalunya, 2013.
  • [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] 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] 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] Santi, P., Topology control in wireless ad hoc and sensor networks, ACM Comput. Surv., 37(2), pp. 164-194, 2005.
  • [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] 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] 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] Chandy, K. M., Lo, T., The capacitated minimum spanning tree, Networks, 3(2), pp. 173-181, 1973.
  • [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] 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] Ö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] 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] 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] 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] Öncan, T., Design of capacitated minimum spanning tree with uncertain cost and demand parameters, Information Sciences, 177(20), pp. 4354-4367, 2007.
  • [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] 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] 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] Reimann, M., Laumanns, M., A hybrid aco algorithm for the capacitated minimum spanning tree problem, Hybrid Metaheuristics, pp. 1-10, 2004.
  • [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] 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] 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] 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] Erciyes, K., Dagdeviren, O., Cokuslu, D., Yilmaz, O., Gumus, H., Mobile ad hoc networks: Current status and Future trends, CRC Press, 2010.
  • [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.
There are 28 citations in total.

Details

Primary Language Turkish
Subjects Engineering
Journal Section Makaleler(Araştırma)
Authors

Mustafa Aşçı 0000-0003-3669-1870

Can İleri This is me 0000-0003-4136-9421

Orhan Dağdeviren 0000-0001-8789-5086

Project Number 215E115
Publication Date December 16, 2020
Published in Issue Year 2020 Volume: 13 Issue: 2

Cite

APA Aşçı, M., İleri, C., & Dağdeviren, O. (2020). Kapasite Farkında Topoloji Kontrol Algoritmalarının Telsiz Duyarga Ağlarında Deneysel Analizi. Türkiye Bilişim Vakfı Bilgisayar Bilimleri Ve Mühendisliği Dergisi, 13(2), 32-46.
AMA Aşçı M, İleri C, Dağdeviren O. Kapasite Farkında Topoloji Kontrol Algoritmalarının Telsiz Duyarga Ağlarında Deneysel Analizi. TBV-BBMD. December 2020;13(2):32-46.
Chicago Aşçı, Mustafa, Can İleri, and Orhan Dağdeviren. “Kapasite Farkında Topoloji Kontrol Algoritmalarının Telsiz Duyarga Ağlarında Deneysel Analizi”. Türkiye Bilişim Vakfı Bilgisayar Bilimleri Ve Mühendisliği Dergisi 13, no. 2 (December 2020): 32-46.
EndNote Aşçı M, İleri C, Dağdeviren O (December 1, 2020) Kapasite Farkında Topoloji Kontrol Algoritmalarının Telsiz Duyarga Ağlarında Deneysel Analizi. Türkiye Bilişim Vakfı Bilgisayar Bilimleri ve Mühendisliği Dergisi 13 2 32–46.
IEEE M. Aşçı, C. İleri, and O. Dağdeviren, “Kapasite Farkında Topoloji Kontrol Algoritmalarının Telsiz Duyarga Ağlarında Deneysel Analizi”, TBV-BBMD, vol. 13, no. 2, pp. 32–46, 2020.
ISNAD Aşçı, Mustafa et al. “Kapasite Farkında Topoloji Kontrol Algoritmalarının Telsiz Duyarga Ağlarında Deneysel Analizi”. Türkiye Bilişim Vakfı Bilgisayar Bilimleri ve Mühendisliği Dergisi 13/2 (December 2020), 32-46.
JAMA Aşçı M, İleri C, Dağdeviren O. Kapasite Farkında Topoloji Kontrol Algoritmalarının Telsiz Duyarga Ağlarında Deneysel Analizi. TBV-BBMD. 2020;13:32–46.
MLA Aşçı, Mustafa et al. “Kapasite Farkında Topoloji Kontrol Algoritmalarının Telsiz Duyarga Ağlarında Deneysel Analizi”. Türkiye Bilişim Vakfı Bilgisayar Bilimleri Ve Mühendisliği Dergisi, vol. 13, no. 2, 2020, pp. 32-46.
Vancouver Aşçı M, İleri C, Dağdeviren O. Kapasite Farkında Topoloji Kontrol Algoritmalarının Telsiz Duyarga Ağlarında Deneysel Analizi. TBV-BBMD. 2020;13(2):32-46.
 Download Cover Image

Article Acceptance

Use user registration/login to upload articles online.

The acceptance process of the articles sent to the journal consists of the following stages:

1. Each submitted article is sent to at least two referees at the first stage.

2. Referee appointments are made by the journal editors. There are approximately 200 referees in the referee pool of the journal and these referees are classified according to their areas of interest. Each referee is sent an article on the subject he is interested in. The selection of the arbitrator is done in a way that does not cause any conflict of interest.

3. In the articles sent to the referees, the names of the authors are closed.

4. Referees are explained how to evaluate an article and are asked to fill in the evaluation form shown below.

5. The articles in which two referees give positive opinion are subjected to similarity review by the editors. The similarity in the articles is expected to be less than 25%.

6. A paper that has passed all stages is reviewed by the editor in terms of language and presentation, and necessary corrections and improvements are made. If necessary, the authors are notified of the situation.

0

.   This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.