Geri Dön

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

Algorithms for capacitated minimum spanning tree problem

PDF İndir

  1. Tez No: 488269
  2. Yazar: MUSTAFA AŞÇI
  3. Danışmanlar: DOÇ. DR. ORHAN DAĞDEVİREN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2017
  8. Dil: Türkçe
  9. Üniversite: Ege Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Uluslararası Bilgisayar Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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 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.

Ö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 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.

Benzer Tezler

  1. Tez No

    531407

    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

    İngilizce

    2018

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge Üniversitesi

    Uluslararası Bilgisayar Ana Bilim Dalı

    DOÇ. DR. ORHAN DAĞDEVİREN

  2. Tez No

    846836

    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

    İngilizce

    2023

    Şehircilik ve Bölge PlanlamaMersin Üniversitesi

    Şehir ve Bölge Planlama Ana Bilim Dalı

    DOÇ. DR. ALİ CENAP YOLOĞLU

  3. Tez No

    200359

    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

    İngilizce

    2007

    Endüstri ve Endüstri MühendisliğiKoç Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    Y.DOÇ.DR. DENİZ AKSEN

  4. Tez No

    353810

    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

    İngilizce

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. BERK CANBERK

  5. Tez No

    111144

    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

    Türkçe

    2002

    İşletmeMarmara Üniversitesi

    Sermaye Piyasası ve Borsa Ana Bilim Dalı

    YRD. DOÇ. DR. MAHMUT HAYATİ ERİŞ

Geri Dön