Kapasite kısıtlı en küçük kapsayan ağaç algoritmaları

Basit Öğe Kaydı
dc.contributor.advisorDağdeviren, Orhan
dc.contributor.authorAşçı, Mustafa
dc.date.accessioned2020-10-25T14:07:32Z
dc.date.available2020-10-25T14:07:32Z
dc.date.issued2017en_US
dc.date.submitted2017
dc.departmentFen Bilimleri Enstitüsüen_US
dc.description.abstractTelsiz 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 log⁡n) 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 log⁡n) 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.en_US
dc.description.abstractThe 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 log⁡n) 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 log⁡n) 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.en_US
dc.identifier.urihttps://hdl.handle.net/11454/59213
dc.language.isotren_US
dc.publisherEge Üniversitesi, Fen Bilimleri Enstitüsüen_US
dc.relation.publicationcategoryTezen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectKapasite Kısıtlı Kapsayan En Küçük Ağaç Problemien_US
dc.subjectTelsiz Duyarga Ağlarıen_US
dc.subjectTopoloji Kontrolüen_US
dc.subjectEnerji Etkin Ağlaren_US
dc.subjectCapacitated Minimum Spanning Tree Problemen_US
dc.subjectWireless Sensor Networksen_US
dc.subjectTopology Controlen_US
dc.subjectEnergy Efficient Networksen_US
dc.titleKapasite kısıtlı en küçük kapsayan ağaç algoritmalarıen_US
dc.title.alternativeAlgorithms for capacitated minimum spanning tree problemen_US
dc.typeMaster Thesisen_US

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Küçük Resim
İsim:
mustafaasci2017.pdf
Boyut:
3.22 MB
Biçim:
Adobe Portable Document Format
Açıklama:
Yüksek lisans tez dosyası
İndir
Lisans paketi
Listeleniyor 1 - 1 / 1
Küçük Resim Yok
İsim:
license.txt
Boyut:
1.44 KB
Biçim:
Item-specific license agreed upon to submission
Açıklama:
İndir

Koleksiyon

Fen Bilimleri Enstitüsü Tez Koleksiyonu