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

Network-wide broadcast (simply broadcast) is a frequent operation in wireless ad hoc networks. A simple flooding 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 efficiency 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 first 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 efficient multicast and broadcast protocols; energy efficient topology control protocols; and energy efficient virtual backbone construction protocols for wireless ad hoc networks and sensor networks.