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 Unıversıty Of Texas At Dallas
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Ö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
- Yeni koronavirüs (SARS CoV-2) pandemisinin yayılımı üzerine matematiksel modellerin Pell-Lucas polinom çözümleri: Türkiye örneği
Pell-Lucas polynomial solutions of mathematical models on the spread of the novel coronavirus (SARS CoV-2) pandemic: The example of Turkey
GAMZE YILDIRIM
- A genetic algorithm for the resource constrained project scheduling problem
Kısıtlı kaynaklı iş programlaması probleminin genetik algoritmalar ile çözülmesi
ERDEM ÖZLEYEN
Yüksek Lisans
İngilizce
2011
İnşaat MühendisliğiOrta Doğu Teknik Üniversitesiİnşaat Mühendisliği Bölümü
DOÇ. DR. RIFAT SÖNMEZ
- Independent task assignment for heterogeneous systems
Heterojen sistemler için bağımsız iş atama
ERTUĞRUL KARTAL TABAK
Doktora
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Bölümü
PROF. DR. CEVDET AYKANAT
- Mathematical models for maritime terminal operations
Kıyı terminali operasyonları için matematiksel modeller
CELAL ÖZGÜR ÜNSAL
Doktora
İngilizce
2019
Endüstri ve Endüstri MühendisliğiKoç ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. CEYDA OĞUZ
- Optimal scheduling for full duplex wireless powered communication networks
Tam çift yönlü kablosuz güçlendirilmiş iletişim ağları için optimum zamanlama
MUHAMMAD SHAHİD IQBAL
Doktora
İngilizce
2021
Elektrik ve Elektronik MühendisliğiKoç ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. SİNEM ÇOLERİ
