Kapasite kısıtlı en küçük kapsayan ağaç algoritmaları
Algorithms for capacitated minimum spanning tree problem
- Tez No: 488269
- Danışmanlar: DOÇ. DR. ORHAN DAĞDEVİREN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: Türkçe
- Üniversite: Ege Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Uluslararası Bilgisayar Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 84
Ö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.
Özet (Çeviri)
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.
Benzer Tezler
- Distributed and self-stabilizing algorithms for capacitated graph theory problems
Kapasite kısıtlı çizge teorisi problemleri içindağıtık ve öz-kararlı algoritmalar
CAN UMUT İLERİ
Doktora
İngilizce
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiUluslararası Bilgisayar Ana Bilim Dalı
DOÇ. DR. ORHAN DAĞDEVİREN
- Assessment of urbanization history of Addis Ababa city, Ethiopia
Addıs Ababa cıty, Ethıopıa'nın kentleşme tarihinin değerlendirilmesi
ABDURAHMAN HUSSEN YIMER
Yüksek Lisans
İngilizce
2023
Şehircilik ve Bölge PlanlamaMersin ÜniversitesiŞehir ve Bölge Planlama Ana Bilim Dalı
DOÇ. DR. ALİ CENAP YOLOĞLU
- Solving the multi-depot location-routing problem with lagrangian relaxation
Çoğul depolu tesis yeri belirleme - rotalama probleminin lagrange gevşetme yöntemi ile çözülmesi
ÖZYURT ZEYNEP
Yüksek Lisans
İngilizce
2007
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
Y.DOÇ.DR. DENİZ AKSEN
- Self-organized network management model for next generation wireless heterogeneous systems
Yeni nesil kablosuz çoktürel sistemlerde kendini düzenleyen ağ yönetim modeli
ÖZGÜR UMUT AKGÜL
Yüksek Lisans
İngilizce
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. BERK CANBERK
- Demir çelik sektörü ve demir çelik sektöründe sermaye maliyeti
Iron and steel sector and cost of capital in iron and steel sector
ALİ DİKMEN
Yüksek Lisans
Türkçe
2002
İşletmeMarmara ÜniversitesiSermaye Piyasası ve Borsa Ana Bilim Dalı
YRD. DOÇ. DR. MAHMUT HAYATİ ERİŞ