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, Bilim ve Teknoloji, Elektrik ve Elektronik Mühendisliği, Information and Records Management, Science and Technology, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: İngilizce
- Üniversite: Université libre de Bruxelles (École polytechnique de Bruxelles)
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 57
Ö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
- Optimal resource allocation for delay and energy constrained wireless networks
Gecikme ve enerji kısıtlı kablosuz ağlarda optimal kaynak özgüleme
YALÇIN ŞADİ
Doktora
İngilizce
2015
Elektrik ve Elektronik MühendisliğiKoç ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. SİNEM ÇÖLERİ ERGEN
- 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
- 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
- Tasarsız ağlarda ve çok kullanıcılı çok girişli çok çıkışlı haberleşme sistemlerinde üstdüşüm kodlama kullanımı.
Superposition coding in ad-hoc networks and downlink multi-user multiple input multiple output systems
AHMET ZAHİD YALÇIN
Doktora
Türkçe
2018
Elektrik ve Elektronik MühendisliğiTOBB Ekonomi ve Teknoloji ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. AYŞE MELDA YÜKSEL TURGUT