Polynomial time solution to minimum forwarding set problem in wireless networks under disk coverage model

详细信息	查看全文 | 推荐本文 |

• 作者：Mehmet Baysan^a ; ^{mehmet.baysan@nih.gov}  ; [Author Vitae] ; Kamil Sarac^b ; ^{ksarac@utdallas.edu}  ; [Author Vitae] ; R. Chandrasekaran^b ; ^{chandra@utdallas.edu}  ; [Author Vitae]
• 关键词：Minimum forwarding set problem ; Multi-point relay ; Energy efficient communication ; Disk graphs
• 刊名：Ad Hoc Networks
• 出版年：2012
• 期刊代码：117_15708705
• 类别：cp
• 出版时间：September, 2012
• 卷：10
• 期：7
• 页码：1253-1266
• 文件大小：962 K

摘要

In this paper, we consider a practical problem, called Minimum Forwarding Set Problem (MFSP), that emerges within the context of implementing (energy efficient) communication protocols for wireless ad hoc or sensor networks. For a given node v, MFSP asks for a minimum cardinality subset of 1-hop neighbors of v to cover v鈥檚 2-hop neighbors. MFSP problem is also known as multi-point relay (MPR) problem. It is shown to be an NP-complete problem for its general case that does not consider the coverage characteristics of wireless transmissions. In this paper, we present two polynomial time algorithms to solve the MFSP problem under disk coverage model for wireless transmissions. In our earlier work, we presented a polynomial time algorithm for this problem under unit disk coverage model. In the current work, we present several observations on the geometric characteristics of wireless transmissions under disk coverage model and build two alternative dynamic programming based solutions with different run time and space complexities to the problem. Disk coverage model is a more general model because it allows nodes to use arbitrary power levels for transmissions. As a result, the presented algorithms provide a more practical solution that can be used as a building block for energy efficient communication protocols designed for wireless ad hoc and sensor networks.