A study on vertex cover problem and its applications on wireless networks
Düğüm örtüsü problemi ve kablosuz ağlardaki uygulamaları üzerine bir çalışma
- Tez No: 657126
- Danışmanlar: DOÇ. DR. ORHAN DAĞDEVİREN
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2020
- Dil: İngilizce
- Üniversite: Ege Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Uluslararası Bilgisayar Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 112
Özet
Nesnelerin interneti kavramının giderek önem kazandığı günümüz dünyasında, birçok cihaz aynı ağ üzerinde ortak bir hedef için dağıtık olarak çalışarak günlük hayatımızı ve üretim süreçlerini önemli ölçüde kolaylaştırmaktadır. Bu tür ağlarda bağlantıların izlenmesi ve meydana gelen kopmalarda ağı yeniden ayaklandırmak büyük öneme sahiptir. Bu noktada ağlardaki bağlantıları izlemek için düğüm örtüsü problemi karşımıza çıkmaktadır. Düğüm örtüsü, çözüm kümesine giren düğümlerin çizge üzerindeki bütün bağlantıları izleyebildiği bir yapı sağlamaktadır. Bir hata sonucu ağdaki düğüm örtüsü özelliği bozulduğunda, ağı tekrardan düğüm örtüsü konumuna getirmemiz gerekir. Bu durumda karşımıza öz-kararlılık kavramı çıkmaktadır. Öz-kararlık sistemin olası bir hata durumunda dış müdehale olmaksızın kararlı hale erişebilmesi olarak tanımlanır. Telsiz duyarga ağları gibi tasarımsız yapılarda enerjinin ve kaynakların iyi yönetilmesi ve kullanılması gerekmektedir. Bu kısıtlamalardan yola çıkarak kapasite kısıtlı çizge teorik problemler önerilmiştir. Bu çalışmada iki önemli çalışma alanı olan öz-kararlılık kavramını ve kapasite kısıtlı problemleri düğüm örtüsü çatısı altında birleştirerek özgün algoritmalar önermekteyiz. Önerdiğimiz algoritmaların doğruluğunu teorik olarak ispatlayıp, benzetim sonuçlarını vererek tezimizi güçlendirimekteyiz. Önermiş olduğumuz SS-CVC1 ve SS-CVC2 algoritmaları gerek zaman gerek düğüm örtüsü performansı açısından tüm rakiplerinden daha başarılı sonuçlar vermişlerdir. Enerji kullanımı açısından, SS-CVC1 algoritması enerji tüketimi en az olan algoritma olmuştur. Önerilen algoritmalara ek olarak bazı önemli düğüm örtüsü algoritmalarının kapsamlı performans değerlendirmelerine yer verilmiştir.
Özet (Çeviri)
In today's world, where the concept of the Internet of Things is becoming increasingly popular, many devices work distributed over the same network for a common goal, significantly simplifying our daily life and production processes. In such networks, it is of great importance to monitor connections and to make the network available in case of breaks. At this point, in order to monitor connections in networks, we encounter the vertex cover problem. The vertex cover provides a structure where the nodes entering the solution set can monitor all connections on the graph. When the vertex cover property in the network breaks down as a result of a break, we need to bring the network back to the property where satisfies the vertex cover. In this case, the concept of self-stabilization arises. Self-stabilization can be defined as the ability of the system to reach the desired stable state again without external intervention in the event of a possible fault. In ad-hoc structures such as wireless sensor networks, energy and resources need to be well managed and used. Based on these constraints, capacitated graph theoretical problems have been proposed. In this study, we propose novel algorithms by combining the two significant fields of study, the concept of self-stabilization and capacitated problems, under the roof of the vertex cover problem. Having proved theoretically the correctness of the proposed algorithms, we shore up our thesis by giving simulation results. The proposed SS-CVC1 and SS-CVC2 algorithms provide better results than all of their counterparts in terms of both time and node cover performance. In terms of energy consumption, the SS-CVC1 algorithm has become the most efficient algorithm. In addition to the proposed algorithms, comprehensive performance evaluations of some important vertex cover algorithms are included in this dissertation.
Benzer Tezler
- Dikey dairesel silindirik açık su havuzlarında hidrodinamik kuvvetler
Hydrodynamic forces for vertical axis circular cylinder containing a concertric cylindrical hole in finite depth
MÜKERREM ERTEN(İLKIŞIK)
- İki boyutlu profillerin etrafındaki akış alanının hesaplamalı simülasyonu
Numerical simulation of the flow field around two dimensional hydrofoils
UĞUR ORAL ÜNAL
- Cisim genişlemeleri ve origami çizimleri
Field extensions and origami constructions
BURCU ŞANSAN
Yüksek Lisans
Türkçe
2019
Matematikİstanbul Teknik ÜniversitesiMatematik Mühendisliği Ana Bilim Dalı
DOÇ. DR. ERGÜN YARANERİ
- Aerodynamics of cross-flow with side jets
Yan jetli çapraz akışkanın aerodinamiği
FATİH GÜNEŞ
Yüksek Lisans
İngilizce
1998
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ. DR. İ. BEDİ ÖZDEMİR
- Investigation of oil-injected screw compressors performance based on energy efficiency and pressurized air quality
Verimlilik ve basınçlı hava kalitesi açısından yağ enjekteli vidalı kompresörlerin incelenmesi
ŞÜKRÜ ERİKLİ
Yüksek Lisans
İngilizce
2017
Kimya MühendisliğiYeditepe ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ALİ BAHADIR OLCAY