Efficient Information Dissemination in Wireless Multi-hop. (2008)

Many protocols and applications in wireless multi-hop networks indispensably use broad- casting to delivery messages to all nodes in a network. Wireless routing protocols such as DSR, AODV and ODRMP broadcast route discovery messages, and many application protocols exchange query and response messages by broadcasting. Hence, the eﬃciency of broadcasting is critical to eﬃciency of these wireless protocols. Eﬃcient wireless broadcast- ing is a topic that this thesis studies where eﬃciency is measured by the total transmission number to broadcast one unit data to the whole network. The study is done in two ways: extending classical methods and utilizing a novel method, network coding. Classical broadcasting protocols are based on store-and-forward routing that views pack- ets as atomic objects and lets a node store incoming packets in its local queue for some delay, before forwarding one or several copies of the packets to its neighbors. Among the classical broadcast protocols, the simplest and most widely used broadcast protocol is pure ﬂood- ing. Pure ﬂooding reliably provides total coverage of a network, but causes redundancy of packets, resulting in unnecessary collisions, and enormous ineﬃciency. To combat this inef- ﬁciency, many eﬃcient broadcast protocols have been studied using probabilistic algorithms such as a gossip protocol, or algorithms based on topology control such as a Multi-Point Relay (MPR) based protocol. These broadcast protocols have been successfully used in many wireless protocols standardized in IEEE 802.11 and IETF. One possible application of the broadcast protocols is wireless mesh networks standard- ized in 802.11Working Group S. The 802.11 mesh networks face challenges such as ineﬃcient broadcasting of so-called associated station information that is partially updated; there ex- ists redundancy between newly updated data and already broadcasted data. This thesis addresses these challenges by introducing an Association Discovery Protocol (ADP) that is combined with MPR-based broadcasting and integrated with an extension of an Optimized Link State Routing (OLSR) protocol for the 802.11 mesh networks. The results of analysis with modeling and simulation show that the protocol eﬀectively decreases control overhead. However, for continuous data traﬃc, there exists another possible broadcast solution, which could theoretically outperform the broadcast protocols with classical store-and-forward routing and would not require precise topology information. This solution is network coding. Theoretically, network coding enables an optimized solution for wireless broadcasting in a polynomial time, while it is NP-complete with classical store-and-forward routing and only approximation algorithms exist. Hence, broadcasting with network coding is, theoretically, at least as eﬃcient as any other broadcasting. This thesis focuses on utilizing network coding speciﬁcally as a practical solution for eﬃcient wireless broadcasting. For the practical solution, this thesis proposes simple al- gorithms based on intuitive rationale about optimal eﬃciency of wireless network coding. The eﬃciency of the proposed simple algorithms is theoretically analyzed, and proven to be asymptotically optimal. The eﬃciency also is experimentally analyzed and shown, in some examples, to outperform other broadcasting with classical store-and-forward routing. Finally, from these simple algorithms we derive a practical broadcasting protocol executing with a simple and eﬃcient coding method (that is, random linear coding). In addition, we propose a simple novel method for real-time decoding that could be combined with the practical network coding broadcasting protocol.