Tez No	İndirme	Tez Künye	Durumu
401535		Polynomial time exact solutions for forwarding set problems in wireless ad hoc networks / Yazar:MEHMET BAYSAN Danışman: DR. R. CHANDRASEKARAN ; DR. KAMİL SARAÇ Yer Bilgisi: The University of Texas at Dallas / Yurtdışı Enstitü Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora İngilizce 2008 69 s.
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.