Telsiz duyarga ağlarında ağırlıklı bağlı baskın küme algoritmaları

Abstract

Telsiz duyarga ağları askeri, gıda, tarım vb. alanlarda sıkça kullanılmaktadır. Telsiz duyarga ağlarında iletişim için kullanılan enerji miktarını azaltmak ve ağın yaşam süresini artırmak için iletişim omurgası olarak bağlı baskın kümeler kullanılmaktadır. Kullanılan küme ne kadar küçük olursa o kadar az düğümün enerjisi azalmaktadır. Dolayısıyla bağlı baskın kümeler (CDS) oluşturulurken, bu kümenin küçük olması istenmektedir. Fakat bağlı baskın kümelerin küçük boyutlarda olması yeterli olmayabilmektedir. Bağlı baskın küme içerisinde enerjisi düşük olan düğümler seçilirse düğümün enerjisi daha çabuk biterek omurganın çalışmasını durdurabilmektedir. Bu yüzden bağlı baskın kümeye konulacak düğümler seçilirken kalan enerji seviyelerinin de dikkate alınması gerekmektedir. Bağlı baskın kümeyi oluşturan düğümlerin ağırlıklarının toplamları minimal olan bağlı baskın kümelere minimal ağırlıklı bağlı baskı küme (MWCDS) denilmektedir. Bu çalışmada iki yeni MWCDS algoritması önerilmiştir. Algoritmalardan ilki düğümlerin ağırlıklarının yanında düğümler arasında bulunan en kısa yolları da dikkate alarak CDS’i oluşturan minimal ağırlık ve yönlendirme maliyetli bağlı baskın küme (MWOC-CDS) algoritmasıdır. İkinci algoritma ise komşularına göre daha farklı düğümlere bağlanabilen kritik düğümleri dikkate alarak bağlı baskın kümeyi oluşturan kritik düğüm tabanlı minimal ağırlıklı bağlı baskın küme (CN-MWCDS) algoritmasıdır.

Wireless sensor networks are often used in military, food, agriculture areas etc. To decrease energy amount consumed in the communication and increase lifetime of the network, connected dominating sets are used as a communication backbone in wireless sensor networks. Due to the total energy consumption of CDSs with few nodes is much less than CDSs with high cardinality the connected dominating sets are desired to have few nodes. However, decreasing the size of CDSs may not be enough. If nodes with low energy are selected in CDS, nodes stop working before other nodes by running out of energy. This situation causes the backbone to fail. Thus, while nodes are being choosed, their energy level should be considered. A CDS whose nodes’ total weight is minimal, is named as the minimal weighted connected dominating set (MWCDS). In this work, two new MWCDS algorithms are proposed. The first one is the minimal weighted and routing cost connected dominating set (MWOC-CDS) algorithm which construct CDS by considering the shortest paths between two nodes as well as nodes’ weights. The second one is critical node based the minimal weighted connected dominating set (CN-MWCDS) algorithm which construct CDS by considering critical nodes that can connect many different nodes than its neighbors.