Efficient localized broadcast algorithms in mobile ad hoc networks

The broadcast operation has a most fundamental role in mobile ad hoc networks because of the broadcasting nature of radio transmission, i.e., when a sender transmits a packet, all nodes within the sender's transmission range will be affected by this transmission. The benefit of this property is that one packet can be received by all neighbors while the negative effect is that it interferes with other transmissions. Flooding ensures that the entire network receives the packet but generates many redundant transmissions which may trigger a serious broadcast storm problem that may collapse the entire network. The broadcast storm problem can be avoided by providing efficient broadcast algorithms that aim to reduce the number of nodes that retransmit the broadcast packet while still guaranteeing that all nodes receive the packet. This dissertation focuses on providing several efficient localized broadcast algorithms to reduce the broadcast redundancy in mobile ad hoc networks. In my dissertation, the efficiency of a broadcast algorithm is measured by the number of forward nodes for relaying a broadcast packet. A classification of broadcast algorithms for mobile ad hoc networks has been provided at the beginning. Two neighbor-designating broadcast algorithms, called total dominant pruning and partial dominant pruning, have been proposed to reduce the number of the forward nodes. Several extensions based on the neighbor-designating approach have also been investigated. The cluster-based broadcast algorithm shows good performance in dense networks, and it also provides a constant upper bound approximation ratio to the optimum solution for the number of forward nodes in the worst case. A generic broadcast framework with K hop neighbor information has a trade-off between the number of the forward nodes and the size of the K-hop zone. A reliable broadcast algorithm, called double-covered broadcast, is proposed to improve the delivery ratio of a broadcast package when the transmission error rate of the network is high. The effectiveness of all these algorithms has been confirmed by simulations.