Efficient broadcasting in multi-hop wireless networks with a realistic physical layer

Authors: Gary K.W. Wong, Hai Liu, Xiaowen Chu, Yiu-Wing Leung, Chun Xie

Abstract: 
Almost all existing broadcasting algorithms assume an ideal physical layer, in which a successful transmission is guaranteed if the distance between communicating nodes is less than a certain threshold, e.g., a transmission range. However, wireless communication links normally suffer from the characteristics of realistic physical layer, which significantly reduce the reliability of broadcasting among the nodes. This work addresses the minimal broadcasting problem in multi-hop wireless networks with a realistic physical layer. Given a probability p , the problem is to design a distributed broadcasting algorithm such that each node in the network receives the broadcasting packet with probability no less than p and the number of retransmissions is minimized. We show that this problem is NP-hard and propose a distributed greedy algorithm which maximizes the gain cost ratio at each node. We prove that the proposed algorithm guarantees that each node receives the broadcasting packet with probability no less than p , and analyze upper bound on the number of total retransmissions in the network. Simulation results show that our algorithm can provide near 100% coverage to the wireless network with a realistic physical layer, and reduce the number of retransmissions compared with modified traditional flooding schemes kFlooding (pure flooding with multiple times) and ACK-Flooding (pure flooding with acknowledgement). We believe our algorithmic solution is efficient and practical for general existing multi-hop wireless networks.

Keywords:
Energy-efficiency wireless
Multi-hop wireless network
Broadcasting efficiency
Unreliable network
NP-hardness
Minimum retransmission broadcast problem

Published in: Ad Hoc Networks (Volume 11, Issue 4, January 2013)

Publisher: Elsevier

ISSN Information: 1570-8705

Efficient broadcasting in multi-hop wireless networks with a realistic physical layer

Bình luận của bạn

*

*

*

*

 Captcha

Gửi bình luận nhập lại