Scheduling wireless ad hoc networks in polynomial time using claw-free conflict graphs
Başlık çevirisi mevcut değil.
- Tez No: 798150
- Danışmanlar: DR. MURİEL MEDARD
- Tez Türü: Yüksek Lisans
- Konular: Bilgi ve Belge Yönetimi, Elektrik ve Elektronik Mühendisliği, Bilim ve Teknoloji, Information and Records Management, Electrical and Electronics Engineering, Science and Technology
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: İngilizce
- Üniversite: Unıversıte Lıbre de Bruxelles (ecole Polytechnıque de Bruxelles)
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Özet yok.
Özet (Çeviri)
In this thesis, we address the scheduling problem in wireless ad hoc networks by exploiting the computational advantage that comes when such scheduling problems can be represented by claw-free conflict graphs. We consider activation of hyperedges in a hypergraph to model a wireless broadcast medium. It is possible to formulate a scheduling problem of network coded flows as finding maximum weighted independent set (MWIS) in the conflict graph of the network. Finding MWIS of a general graph is NP-hard leading to an NP-hard complexity of scheduling. Therefore, approximate solutions are proposed in prior works. In a claw-free conflict graph, MWIS can be found in polynomial time leading to a throughput optimal scheduling. We show that the conflict graph of certain wireless ad hoc networks are claw-free. If not, we suggest making physical modifications in the network setup or directly placing extra edges on the conflict graph in order to obtain claw-freeness in general networks. We explain our reasoning and detail different options of these modifications by using examples and illustrations. For networks where all claws in the conflict graph originate from a specific part of the network, a mixed scheduling algorithm is proposed. We evaluate the performance of breaking claws by introducing edges with simulations conducted on random networks and conclude that this method can perform nearly optimal under the necessary assumptions. In the end, we conclude the thesis and discuss some possible directions for future research.
Benzer Tezler
- Topology design and scheduling in STDMA based wireless ad hoc networks
Ad hoc kablosuz ağlarda topoloji tasarımı ve zaman çizelgelemesi
SADETTİN ALP ERGİN
Yüksek Lisans
İngilizce
2003
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. EZHAN KARAŞAN
- Improving network reliability by exploiting path diversity in ad hoc networks with bursty losses
Çoğuşma biçiminde yitimli tasarsız ağların yol çeşitlemesinden yararlanılarak ağ güvenilirliğinin iyileştirilmesi
ÖZLEYİŞ OCAKOĞLU
Yüksek Lisans
İngilizce
2005
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı ÜniversitesiMühendislik Bilimleri Ana Bilim Dalı
YRD. DOÇ. DR. ÖZGÜR ERÇETİN
- Energy-aware task scheduling over mobile ad hoc networks
Energy-aware task scheduling over mobile ad hoc networks
ALİ BOKAR
Doktora
İngilizce
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Bölümü
DR. CEVAT SENER
PROF. DR. MÜSLİM BOZYİGİT
- OLSR-aware cross-layer channel access scheduling in wireless mesh networks
Örgüsel ağlarda OLSR-duyarlı katmanlar arası kanal erişim planlaması
MİRAY KAŞ
Yüksek Lisans
İngilizce
2009
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Bölümü
YRD. DOÇ. DR. İBRAHİM KÖRPEOĞLU
- Joint link/packet scheduling, rate allocation and routing optimization in STDMA based wireless mesh networks
STDMA tabanlı tek-kanallı kablosuz örgü ağlarda birleşik link/paket planlaması, hız ataması ve yönlendirme eniyilemesi
AHMET EMRAH SEZGİN
Yüksek Lisans
İngilizce
2009
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik ve Elektronik Mühendisliği Bölümü
DOÇ. DR. EZHAN KARAŞAN