Geri Dön

Polynomial time exact solutions for forwarding set problems in wireless ad hoc networks

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

  1. Tez No: 401535
  2. Yazar: MEHMET BAYSAN
  3. Danışmanlar: DR. R. CHANDRASEKARAN, DR. KAMİL SARAÇ
  4. Tez Türü: Doktora
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2008
  8. Dil: İngilizce
  9. Üniversite: The University of Texas at Dallas
  10. Enstitü: Yurtdışı Enstitü
  11. Ana Bilim Dalı: Belirtilmemiş.
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 69

Özet

Özet yok.

Özet (Çeviri)

Network-wide broadcast (simply broadcast) is a frequent operation in wireless ad hoc net- works. A simple °ooding based implementation of broadcast may result in excessive use of system energy and wireless bandwidth that are two scarce resources in wireless ad hoc networks. One promising practical approach to improve the e±ciency of broadcast is to use localized algorithms that minimize the number of nodes involved in the propagation of broadcast messages. In this context, the minimum forwarding set problem (MFSP) (also known as multi-point relay (MPR) selection problem) has received a considerable attention in the research community. Even though the general form of the problem is shown to be NP- complete, the complexity of the problem has not been known under the practical application context of ad hoc networks. In this study, I present two polynomial time algorithms to solve the MFSP for wireless networks under unit disk coverage model and disk coverage model. Leveraging the practical characteristics of the application environment, I prove the existence of a certain class of optimal solutions that hold some nice properties. I then propose polynomial time algorithms to build an optimal solution within this class of solutions to a given instance of the MFSP problem. My algorithms are the ¯rst polynomial time solutions to the MFSP problem under these models. Furthermore I present a new version of MFSP which provides collision awareness. I believe that the work presented in this thesis will have an impact on the design and development of new algorithms for several wireless network applications including energy e±cient multicast and broadcast protocols; energy e±cient topology control protocols; and energy e±cient virtual backbone construction protocols for wireless ad hoc networks and sensor networks.

Benzer Tezler

  1. Ayrık yapıların tümleyen problemler yardımıyla incelenmesi

    A study of discrete structures by means of complementary problems

    ASLI GÜLER SERİNKEN

    Doktora

    Türkçe

    Türkçe

    2013

    MatematikEge Üniversitesi

    Bilgisayar Bilimleri Ana Bilim Dalı

    PROF. DR. URFAT NURIYEV

  2. Kombinatoryal optimizasyon problemlerinin çözümünde makine öğrenmesi temelli yaklaşımlar

    Machine learning based approaches in combinatorial optimization problems

    DUYGU SELİN TURAN

    Doktora

    Türkçe

    Türkçe

    2023

    MatematikEge Üniversitesi

    Matematik Ana Bilim Dalı

    PROF. DR. BURAK ORDİN

  3. Öğrenme-unutma etkili ve ayar süreli tek makine çizelgeleme problemleri için yeni çözüm yaklaşımları

    New solution approaches for single machine scheduling problems with learning-forgetting effects and setup times

    SETTAR MUŞTU

    Doktora

    Türkçe

    Türkçe

    2020

    Endüstri ve Endüstri MühendisliğiKırıkkale Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. TAMER EREN

  4. A Polyhedral approach to quadratic assignment problem

    Karesel atama problemine polyhedral bir yaklaşım

    AHMET SERTAÇ MURAT KÖKSALDI

    Yüksek Lisans

    İngilizce

    İngilizce

    1994

    Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. MUSTAFA AKGÜL

  5. A new heuristic algorithm for minimizing the makespan on identical parallel machines

    Özdeş paralel makinalarda yayılma alanını minimum değerine ulaştıracak sezgisel yeni bir algoritma

    SERHAT ÖZTÜRK

    Doktora

    İngilizce

    İngilizce

    2008

    Endüstri ve Endüstri MühendisliğiMarmara Üniversitesi

    Mühendislik Yönetimi Ana Bilim Dalı

    YRD. DOÇ. DR. SEROL BULKAN