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

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.