Bulut Tabanlı Büyük Ölçekli Sensör Ağları için En Küçük Kapsayan Ağaç Tabanlı Kümeleme Algoritması

Öz

Kablosuz sensör ağları (KSA'ları), ortamdan veri toplayan çok sayıda düğümden oluşabilir. KSA'lar, Nesnelerin İnterneti'nin önemli iletişim katmanı teknolojilerindendir. KSA'lar tarafından elde edilen veriler katlanarak büyüyebilir, bu sebepten büyük veri analiz teknikleri ve bulut bilişim teknolojilerini kullanmak son derece önemlidir. KSA'lar, habitat izleme, askeri gözetim, akıllı tarım, madenci güvenliği ve sağlık uygulamaları gibi çeşitli uygulamalarda kullanılabilir. Sensör düğümleri genellikle pilden güç alır, bu nedenle düğümlerin var olan enerjisini korumak, uygulamaların ömrünü uzatmak için çok önemlidir. KSA'lar sabit bir altyapıya sahip değildir, bu nedenle uygulama mesajları tasarsız bir şekilde çıkış (sink) düğümüne iletilir. Algılayıcı düğümlerin iletim aralığı sınırlı olduğu için çok zıplamalı (multi-hop) iletişim kullanılır. Kümeleme, KSA'larda çok zıplamalı yönlendirmeyi desteklemek için çok önemli bir yöntemdir. Veri toplama, zaman senkronizasyonu ve yük dengeleme, kümelemeden yararlanan iyi bilinen işlemlerden bazılarıdır. Kümeleme işleminde verimli iletişim yollarının seçilmesi ve düğümlerin bölümlere eşit olarak dağıtılması, ağ ömrünün artmasına neden olur. Bu makalede, KSA'lar için en küçük kapsayan ağaç tabanlı kümeleme ve omurga oluşturma algoritması (MICUB) öneriyoruz. Önerilen MICUB algoritması, düğüm koordinatlarını, iletim aralığını, algılama alanı boyutlarını ve bölüm numaralarını girer, kümeleme ve omurga bilgilerini çıkarır. MICUB algoritması ilk olarak en küçük kapsayan ağaç omurgasını oluşturur ve ağ alanını her bölümün bir küme olduğu eşit parçalara böler. Bu şekilde, omurga oluşumu için verimli bağlantılar seçilir ve kümeler dengeli bir şekilde oluşturulur. Küme içi bağlantılar, yine kümeler içinde bir en küçük kapsayan ağaç algoritması yürütülerek oluşturulur. Kümeleme kalitesini elde etmek için önerilen MICUB algoritmasının ve benzerlerinin varyasyon katsayısını ölçülmektedir. Bu sonuçlar, önerilen algoritmamızın düğüm sayılarına ve derecelerine karşı çok iyi performans gösterdiğini göstermektedir.

Anahtar Kelimeler

• Kablosuz Sensör Ağlar
• Kümeleme
• En Küçük Kapsayan Ağaç
• Nesnelerin İnterneti
• Bulut Bilişim
• Büyük Veri

A Minimum Spanning Tree based Clustering Algorithm for Cloud based Large Scale Sensor Networks

Abstract

Wireless sensor networks (WSNs) can be composed of huge numbers of nodes collecting data from the environment. WSNs are crucial communication layer technologies of Internet of Things. The obtained data by the WSNs can grow exponentially, hence utilizing big data analysis techniques and cloud computing technologies are of utmost importance. WSNs can be used in various applications such as habitat monitoring, military surveillance, smart agriculture, miner safety and healthcare applications. Sensor nodes are generally battery-powered, so conserving the residual energy of nodes is very important to prolong the lifetime of the applications. WSNs do not own a fixed infrastructure, hence messages of the applications transmitted in an ad hoc manner to the sink node. Since the transmission range of sensor nodes are limited, multi-hop communication is used. Clustering is a very important method for supporting multi-hop routing in WSNs. Data aggregation, time synchronization and load balancing are some of the well-known operations that benefit from clustering. Selecting efficient communication paths and distribution of nodes evenly to partitions in clustering operation lead to boost the network lifetime. In this paper, we propose a minimum spanning tree based clustering and backbone formation algorithm (MICUB) for WSNs. The proposed algorithm inputs node coordinates, transmission range, sensing area dimensions and partition numbers and outputs clustering and backbone information. MICUB algorithm first forms a minimum spanning tree backbone and divides the networking area into equal partitions where each partition is a cluster. In this manner, efficient links are selected for backbone formation and the clusters are constructed evenly. The intra-cluster links are constructed by again executing a minimum spanning tree algorithm inside the clusters. We measure the coefficient of variations of the proposed MICUB algorithm and its counterparts to obtain the clustering quality. These results show us that our proposed algorithm performs very well against node counts and degrees.

Keywords

• Wireless Sensor Networks
• Clustering
• Minimum Spanning Tree
• Internet of Things
• Cloud Computing
• Big Data

Kaynakça

1. Ahuja, M. and Zhu, Y. (1989) A distributed algorithm for minimum weight spanning trees based on echo algorithms. Proc. of the 9th Int. Conf. on Distributed Computing Systems, 5-9 June, pp. 2-8.
2. Awerbuch, B. (1987) Optimal distributed algorithms for minimum weight spanning tree, counting, leader election and related problems. Proc. of the 19th Annual ACM Symp. on Theory of Computing, New York, United States, pp. 230-240. ACM Press, New York.
3. Banerjee, S. and Khuller, S. (2000) A clustering scheme for hierarchical routing in wireless networks. Technical Report CS-TR-4103. UMD, College Park.
4. Chatterjee, M., Das, S. K., and Turgut, D. (2001) WCA: A weighted clustering algorithm for mobile ad hoc networks. Journal of Cluster Computing (Special Issue on Mobile Ad hoc Networks), 5, 193-204.
5. Dagdeviren, O. and Erciyes, K. (2006) A distributed backbone formation algorithm for mobile ad hoc networks. Proc. of the 4th Int. Symp. on Parallel and Distributed Processing and Applications, Sorrento, Italy, 4-6 December, pp. 219-230. Springer-Verlag, Berlin.
6. Dai, F. and Wu, J. (2004) An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Trans. on Parallel and Dist. Systems, 15(10), 908-920.
7. Gallagher, R. G., Humblet, P. A., and Spira, P. M. (1983) A distributed algorithm for minimum-weight spanning trees. ACM Trans. on Prog. Languages and Systems, pp. 6677. ACM Press, New York.
8. Harb, H., Makhoul, A., Idrees, A., Zahwe and O. and Taam, M.. (2017) Wireless Sensor Networks: A Big Data Source in Internet of Things. International Journal of Sensors, Wireless Communications and Control.

9. Kim, B.-.S, Kim, K.-I., Shah, B., Chow, F. and Kim, K. H. (2019) Wireless Sensor Networks for Big Data Systems, Sensors 19, no. 7, 1565.
10. Kruskal, J. B. (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. of the American Mathematical Society, 7(1), 48-50.
11. Lien, Y. N. (1988) A new node-join-tree distributed algorithm for minimum weight spanning trees. Proc. of the 8th Int. Conf. on Distributed Computing System, pp. 334-340. IEEE.
12. Liu, X., Zhu, R., Anjum, A., Wang, J., Zhang, H. and Ma, M. (2020) Intelligent data fusion algorithm based on hybrid delay-aware adaptive clustering in wireless sensor networks, Future Generation Computer Systems, vol.104, pp. 1-14.
13. Nanuvala, N. (2006) An enhanced algorithm to flnd dominating set nodes in ad hoc wireless networks. MSc. Thesis, Georgia State University.
14. Palaniswami, M., Rao, A. S., Kumar, D., Rathore, P. and Rajasegarar, S., (2020) The Role of Visual Assessment of Clusters for Big Data Analysis: From Real-World Internet of Things, IEEE Systems, Man, and Cybernetics Magazine, vol. 6, no. 4, pp. 45-53.
15. Tripathi, A. K., Sharma, K., Bala, M., Kumar, A., Menon, V. G. and Bashir, A. K. (2021) A Parallel Military-Dog-Based Algorithm for Clustering Big Data in Cognitive Industrial Internet of Things, IEEE Transactions on Industrial Informatics, vol. 17, no. 3, pp. 2134-2142.
16. Wang, Q., Guo, S., Hu, J. and Yang, Y., (2018) Spectral partitioning and fuzzy C-means based clustering algorithm for big data wireless sensor networks. EURASIP Journal on Wireless Communications and Networking, 54.
17. Vaiyapuri, T., Parvathy, V.S., Manikandan, Krishnaraj, V. N., Gupta, D. and Shankar, K. (2021) A Novel Hybrid Optimization for Cluster‐Based Routing Protocol in Information-Centric Wireless Sensor Networks for IoT Based Mobile Edge Computing. Wireless Personal Communications, https://doi.org/10.1007/s11277-021-08088-w.