TY - JOUR
T1 - A polynomial time solution to minimum forwarding set problem in wireless networks under unit disk coverage model
AU - Baysan, Mehmet
AU - Sarac, Kamil
AU - Chandrasekaran, Ramaswamy
AU - Bereg, Sergey
PY - 2009
Y1 - 2009
N2 - Network-wide broadcast (simply broadcast) is a frequently used operation in wireless ad hoc networks (WANETs). One promising practical approach for energy-efficient broadcast is to use localized algorithms to minimize the number of nodes involved in the propagation of the broadcast messages. In this context, the minimum forwarding set problem (MFSP) (also known as multipoint relay (MPR) 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 paper, we present a polynomial time algorithm to solve the MFSP for wireless network under unit disk coverage model. We prove the existence of some geometrical properties for the problem and then propose a polynomial time algorithm to build an optimal solution based on these properties. To the best of our knowledge, our algorithm is the first polynomial time solution to the MFSP under the unit disk coverage model. We believe that the work presented in this paper will have an impact on the design and development of new algorithms for several wireless network applications including energy-efficient multicast, broadcast, and topology control protocols for WANETs and sensor networks.
AB - Network-wide broadcast (simply broadcast) is a frequently used operation in wireless ad hoc networks (WANETs). One promising practical approach for energy-efficient broadcast is to use localized algorithms to minimize the number of nodes involved in the propagation of the broadcast messages. In this context, the minimum forwarding set problem (MFSP) (also known as multipoint relay (MPR) 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 paper, we present a polynomial time algorithm to solve the MFSP for wireless network under unit disk coverage model. We prove the existence of some geometrical properties for the problem and then propose a polynomial time algorithm to build an optimal solution based on these properties. To the best of our knowledge, our algorithm is the first polynomial time solution to the MFSP under the unit disk coverage model. We believe that the work presented in this paper will have an impact on the design and development of new algorithms for several wireless network applications including energy-efficient multicast, broadcast, and topology control protocols for WANETs and sensor networks.
KW - Minimum forwarding set problem
KW - Multipoint relays
KW - Network-wide broadcast
KW - Unit disk graphs
UR - http://www.scopus.com/inward/record.url?scp=67649336633&partnerID=8YFLogxK
U2 - 10.1109/TPDS.2008.169
DO - 10.1109/TPDS.2008.169
M3 - Article
AN - SCOPUS:67649336633
SN - 1045-9219
VL - 20
SP - 913
EP - 924
JO - IEEE Transactions on Parallel and Distributed Systems
JF - IEEE Transactions on Parallel and Distributed Systems
IS - 7
ER -