Efficient Broadcasting in Multi-Hop Wireless Networks With a Realistic Physical Layer

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 paper 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.