Polynomial time exact solutions for forwarding set problems in wireless ad hoc networks
Başlık çevirisi mevcut değil.
- Tez No: 401535
- Danışmanlar: DR. R. CHANDRASEKARAN, DR. KAMİL SARAÇ
- 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: 2008
- Dil: İngilizce
- Üniversite: The University of Texas at Dallas
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- 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
- 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
2013
MatematikEge ÜniversitesiBilgisayar Bilimleri Ana Bilim Dalı
PROF. DR. URFAT NURIYEV
- Kombinatoryal optimizasyon problemlerinin çözümünde makine öğrenmesi temelli yaklaşımlar
Machine learning based approaches in combinatorial optimization problems
DUYGU SELİN TURAN
- Öğ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
2020
Endüstri ve Endüstri MühendisliğiKırıkkale ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. TAMER EREN
- A Polyhedral approach to quadratic assignment problem
Karesel atama problemine polyhedral bir yaklaşım
AHMET SERTAÇ MURAT KÖKSALDI
Yüksek Lisans
İngilizce
1994
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MUSTAFA AKGÜL
- 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
2008
Endüstri ve Endüstri MühendisliğiMarmara ÜniversitesiMühendislik Yönetimi Ana Bilim Dalı
YRD. DOÇ. DR. SEROL BULKAN