Kapasite kısıtlı en küçük kapsayan ağaç algoritmaları
Yükleniyor...
Dosyalar
Tarih
2017
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Ege Üniversitesi, Fen Bilimleri Enstitüsü
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
Telsiz duyarga ağlar (TDA) üzerinde bulunan düğümlerin sahip oldukları enerji kaynakları genellikle sınırlıdır. Bu sebeple düğümlerin kullandıkları algoritmaların, enerji-etkin algoritmalar olarak tasarlanması önemlidir. Kapasite kısıtlı en küçük kapsayan ağaç (KEKA) algoritmaları, TDA üzerinde enerji etkin yönlendirme patikaları oluşturmak ve oluşturulan alt ağaçlar arasında yük dengesi sağlamak için kullanılabilir. Birçok merkezi algoritma bu problemi çözmek için tasarlanmış olmasına rağmen problemin TDA'ya uygun enerji-etkin çözümü bulunmamaktadır. Bu problemle ilgili merkezi bir algoritma; TDA'da n düğümlü ağ üzerindeki çıkış düğümünde uygulamanın bit karmaşıklığı O(n^2 logn) bit olmaktadır. Bu çalışmada, TDA'da KEKA problemini çözmeyi hedefleyen iki algoritma önerilmiştir. DIST_PRIM (DPRIM) algoritmasını temel alan DCMST ve Esau-Williams (E-W) algoritmasını temel alan MCO algoritmalarının tasarımı verilmiştir. DCMST algoritmasının bit karmaşıklığı DIST_PRIM algoritmasıyla aynıdır, O(n^2)'dir. MCO algoritmasının bit karmaşıklığı O(n logn) bit'tir. Önerilen DCMST algoritmasının performansı, DPRIM ve DCMST algoritmasının merkezi olarak çalıştırıldığı (CENTRAL) algoritmayla karşılaştırılmıştır. MCO algoritmasının performansı, E-W algoritmasının merkezi olarak TDA üzerinde çözülüp (CENTEW), çözümün tüm düğümlere bildirildiği senaryo ile karşılaştırılmıştır. Elde edilen simülasyon sonuçlarına göre DCMST ve MCO algoritmalarının enerji tüketimi açısından CENTRAL ve CENTEW algoritmalarına göre daha etkin olduğu görülmüştür.
The devices, which are running on Wireless Sensor Networks (WSNs), generally have limited energy sources. Thus, makes foregrounding the design of "Energy-Aware" types of algorithms. Capacitated Minimum Spanning Tree (CMST) algorithms can be designed for finding energy-aware routing paths and for load-balancing among sub-trees connected to the sink device. Although, there are studies extensively in central settings there has not been any energy-efficient algorithm for the WSNs. The bit complexity of applying a central approach in the sink node is O(n^2 logn) bits on a network having n nodes. In this study, we present the design of algorithms which aim to solve CMST problem in WSNs. DCMST is based on DIST_PRIM (DPRIM) algorithm and MCO is based on Esau-Williams (E-W) algorithm. The bit complexity of the proposed DCMST algorithm is O(n^2) bits and identical with DIST_PRIM. The bit complexity of the proposed MCO algorithm is O(n logn) bits. We compare the performance of the proposed DCMST algorithm with DPRIM and central version of DCMST algorithm (CENTRAL). The performance of the proposed MCO algorithm with the straightforward implementation of E-W, where the problem is solved by the sink node and the result is sent to the other nodes (CENTEW) on WSN. According to the computational results, DPRIM and MCO algorithms are more efficient than CENTRAL and CENTEW algorithms with respect to the energy consumption.
The devices, which are running on Wireless Sensor Networks (WSNs), generally have limited energy sources. Thus, makes foregrounding the design of "Energy-Aware" types of algorithms. Capacitated Minimum Spanning Tree (CMST) algorithms can be designed for finding energy-aware routing paths and for load-balancing among sub-trees connected to the sink device. Although, there are studies extensively in central settings there has not been any energy-efficient algorithm for the WSNs. The bit complexity of applying a central approach in the sink node is O(n^2 logn) bits on a network having n nodes. In this study, we present the design of algorithms which aim to solve CMST problem in WSNs. DCMST is based on DIST_PRIM (DPRIM) algorithm and MCO is based on Esau-Williams (E-W) algorithm. The bit complexity of the proposed DCMST algorithm is O(n^2) bits and identical with DIST_PRIM. The bit complexity of the proposed MCO algorithm is O(n logn) bits. We compare the performance of the proposed DCMST algorithm with DPRIM and central version of DCMST algorithm (CENTRAL). The performance of the proposed MCO algorithm with the straightforward implementation of E-W, where the problem is solved by the sink node and the result is sent to the other nodes (CENTEW) on WSN. According to the computational results, DPRIM and MCO algorithms are more efficient than CENTRAL and CENTEW algorithms with respect to the energy consumption.
Açıklama
Anahtar Kelimeler
Kapasite Kısıtlı Kapsayan En Küçük Ağaç Problemi, Telsiz Duyarga Ağları, Topoloji Kontrolü, Enerji Etkin Ağlar, Capacitated Minimum Spanning Tree Problem, Wireless Sensor Networks, Topology Control, Energy Efficient Networks
