Geri Dön

Scheduling wireless ad hoc networks in polynomial time using claw-free conflict graphs

Başlık çevirisi mevcut değil.

  1. Tez No: 798150
  2. Yazar: ALPER KÖSE
  3. Danışmanlar: DR. MURİEL MEDARD
  4. Tez Türü: Yüksek Lisans
  5. 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
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2017
  8. Dil: İngilizce
  9. Üniversite: Université libre de Bruxelles (École polytechnique de Bruxelles)
  10. Enstitü: Yurtdışı Enstitü
  11. Ana Bilim Dalı: Belirtilmemiş.
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

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

    İngilizce

    2003

    Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. EZHAN KARAŞAN

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

    İngilizce

    2015

    Elektrik ve Elektronik MühendisliğiKoç Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. SİNEM ÇÖLERİ ERGEN

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

    İngilizce

    2005

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı Üniversitesi

    Mühendislik Bilimleri Ana Bilim Dalı

    YRD. DOÇ. DR. ÖZGÜR ERÇETİN

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

    İngilizce

    2009

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent Üniversitesi

    Bilgisayar Mühendisliği Bölümü

    YRD. DOÇ. DR. İBRAHİM KÖRPEOĞLU

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

    Türkçe

    2018

    Elektrik ve Elektronik MühendisliğiTOBB Ekonomi ve Teknoloji Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. AYŞE MELDA YÜKSEL TURGUT