Eﬃcient Wireless Broadcasting with Store-and-Forward Routing
In this section, we categorize existing broadcast protocols with store-and-forward routing into four families: pure flooding, probability based approaches, area based approaches and neighbor-knowledge based approaches as is done in . We explain briefly each category and details eight broadcast protocols belonging to four categories. Because simulation of  showed that an MPR-based broadcast protocol was generally eﬃcient in various wireless network environments, we study the use of an MPR-based broadcast protocol in wireless mesh networks. In this section, we classify seven wireless broadcast protocols with store-and-forward routing into four categories as seen in : Pure flooding, probability based approaches, area based approaches and neighbor-knowledge based approaches.
Pure flooding lets every node forward all initially-received packets. Probability based approaches use some basic understanding of the network topology to assign a probability for a node to forward. Area based approaches assume that nodes have a common trans-mission distance and let a node forward the received packet only if its forwarding reaches a suﬃciently large additional coverage area. Neighbor knowledge approaches maintain neigh-borhood information by exchanging control messages such as a ’hello’ message packet, and use the maintained neighborhood information to decide if a node forwards the packet or not.
Common Operations: Packet Processing and Forwarding
In this section, we explain common operations for all protocols belong to four categories to process and to forward packets as seen in . Each packet encapsulates one more broad-casted messages and the packets are embedded in UDP datagram for transmission over the network.
Messages can be flooded onto the entire network, or flooding can be limited to nodes within a diameter (in terms of number of hops) from the originator of the message. Thus transmitting a message to the neighborhood of a node is just a special case of flooding. When flooding any control message, duplicate retransmissions will be eliminated locally (i.e., each node maintains a duplicate set to prevent transmitting the same message twice).
Each message in a packet has its own message header, which includes an originator address field, a Time To Live field and a message sequence number field. An originator address field contains the address of the node that originally generated this message. When a node has several network interfaces and addresses, a node chooses one address as a main address and uses it as an originator address. But in this thesis, we assume that a node has a network interface and an address. A message sequence number field uniquely identifies each message generated from the originator node. Message sequence numbers are used to ensure that a given message is not retransmitted more than once by any node. A Time To Live field contains the maximum number of hops a message will be transmitted. Before a message is retransmitted, the Time To Live must be decremented by 1. When a node receives a message with a Time To Live equal to 0 or 1, the message must not be retransmitted under any circumstances. Normally, a node would not receive a message with a TTL of zero. Thus, by setting this field, the originator of a message can limit the flooding radius. Upon receiving a packet, a node examines each of the message headers in a packet. A node may receive the same message several times. Thus, to avoid re-processing of some messages that were already received and processed, each node maintains a Duplicate Set. In this set, the node records information about the most recently received messages where duplicate processing of a message is to be avoided. For such a message, a node records a ”Duplicate Tuple” (D-addr, D-seq-num, D-retransmitted, D-time), where D-addr is the orig-inator address of the message, D-seq-num is the message sequence number of the message, D-retransmitted is a boolean indicating whether the message has been already retransmit-ted, D-time specifies the time at which a tuple expires and must be removed. In a node, the set of Duplicate Tuples are denoted the ”Duplicate set”. Thus, upon receiving a basic packet, a node must perform the following tasks for each encapsulated message:
1. If the packet contains no messages (i.e., the Packet Length is less than or equal to the size of the packet header), the packet must silently be discarded.
2. If the Time To Live of the message is less than or equal to zero), or if the message was sent by the receiving node, the message must silently be dropped.
3. Processing condition: if there exists a tuple in the duplicate set, where: (D-addr == Originator Address, AND D-seq-num == Message Sequence Number) then the message has already been completely processed and must not be processed again. Otherwise, the node processes the data in the message.
4. Forwarding condition: if there exists a tuple in the duplicate set, where: (D-addr == Originator Address, AND D-seq-num == Message Sequence Number), then the mes-sage has already been considered for forwarding and should be retransmitted again. Otherwise: the message must be considered for forwarding ”Default Forwarding Algorithm”: the default forwarding algorithm is the following:
1. If the sender of the packet is not detected to be in the one hop neighborhood of the node, the forwarding algorithm must silently stop here (and the message must not be forwarded).
2. If there exists a tuple in the duplicate set where: ( D-addr == Originator Address AND D-seq-num == Message Sequence Number ). then the message will be further considered for forwarding if and only if: D-retransmitted is false.
3. Otherwise, if such an entry doesn’t exist, the message is further considered for for-warding.
4. If the time to live of the message is greater than ’1’, the message MUST be retrans-mitted (as described later in steps 6 to 8).
Eﬃcient Broadcasting Extension to Wireless Mesh Net- works
MPR-based broadcasting is an eﬃcient broadcasting method with classical store-and-forward broadcasting in wireless networks. MPR-based broadcasting reduces the transmission num-ber by decreasing the size of a forwarder set. One practical application is to use the eﬃcient MPR-based broadcast protocol with an OLSR protocol for mesh networks, which is specif-ically standardized in IEEE 802.11 Working Group S. When we use the two protocols, an additional protocol should be added. The additional protocol is ADP, which decreases the control overhead distributed using an MPR-based broadcast protocol. We explain the ex-tension of an MPR-based broadcast protocol in wireless mesh networks as follows: we first explain wireless mesh networks in terms of their structure and contrast with other wireless networks such as Mobile Ad hoc Networks (MANET); we then describe other protocols ap-plied to wireless mesh networks; we explain an OLSR protocol using MPR-based broadcast protocol to distribute control messages;we introduce an association discovery protocol to decrease control overhead; we analyze the performance by using the association discovery protocol with a model; we detail experimental results and summarize the results to apply MPR-based broadcasting with an OLSR protocol and an association discovery protocol.
Wireless Mesh Networks (WMNs) have been proposed as a prominent network solution for ubiquitous networks , and industry standard groups such as IEEE 802.11 [29–31], 802.15  and 802.16  are developing new specifications for WMNs. The recent broad interest in WMNs is due to two major features of WMNs. First, WMNs are capitalizing on the self-organizing aspects of ad-hoc networks, and the ease of deployment with minimal preparation, requiring less administration and maintenance. Second, WMNs (particularly, for 802.11 networks) can capitalize on a broad installed base, and on a technology that has been already developed: they enable mesh clients to access networks, without requiring
them to execute an additional routing protocol (for instance, 802.11 stations). Instead of running a complex routing protocol, clients simply associate themselves with mesh routers and rely on mesh routers to access the whole WMN; the routing on the wireless mesh routers is transparent for the client. This feature may also be used by design, in order to isolate the routing functionality from the clients; then diﬀerent deployment of WMNs with diﬀerent features, could still accommodate the same wireless mesh client. This also allows lighter clients and simpler participation in heterogeneous networks.
Table of contents :
1.3 Thesis outline
2 Broadcast Protocols in Wireless Networks
2.1 Efficient Wireless Broadcasting with Store-and-Forward Routing
2.2 Efficient Broadcasting Extension to Wireless Mesh Networks
3 Network Coding Background
3.1 Introduction of Network Coding
3.2 Practical Framework of Network Coding
3.2.1 Linear Coding
3.2.2 Random Linear Coding
3.3 Theoretical Performance of Network Coding
3.3.1 Min-cut Max flow Theorem
3.3.2 Maximum Multicasting Rate of Network Coding
3.3.3 Maximum Broadcast Rate of Wireless Network Coding
3.3.4 Maximum Broadcast Rate of Random Linear Coding
3.4 Summary and a Problem Statement
4 Efficient Wireless Broadcasting with Network Coding
4.2 Related Work of Efficient Wireless Network Coding
4.3 Network Model and Evaluation Metrics
4.3.1 Network Model
4.3.2 Evaluation Metrics and Efficiency Bound of Store-Forward Broadcasting
4.3.3 Efficiency Measuring Tools and Methods
4.4 Principal Rationale
4.4.1 Operations of each node for Broadcasting with Random Linear Coding
4.4.2 Basic Principle for Rate Selection
4.4.3 Heuristic for Rate Selection: IRMS
4.5 Theoretical Analysis of Efficiency
4.5.1 Theoretical Analysis of Efficiency in 1D lattice torus networks
4.5.2 Proof of Asymptotical Optimality in 2 dimensional Euclidean Space
4.5.3 Proofs of the Achievable Broadcast Capacity
4.6 Experimental Efficiency Evaluation
4.6.1 Efficiency in Different Types of Networks
4.6.2 Distribution of the Min-cut
4.6.3 Random Unit Disk Graphs N, M
4.6.4 Difficulties for Distributed Rate Selection
4.7 Rate Selection Improvement : Dynamic Adaptation
4.7.1 Dynamic Heuristic for Rate Selection
4.7.2 Experimental Results
5 Network Coding Protocol
5.1 Algorithm and Packet Format
5.1.1 Framework for Broadcasting with Random Linear Coding
5.1.2 Termination Protocol
5.1.3 Packet Format
5.1.4 Performance Evaluation using NS-2
5.2 Real-time Decoding
5.2.1 Overview of Real-time Decoding
5.2.2 SEW (Sliding Encoding Window)
5.2.3 Real-Time Decoding: Effects of SEW
6 Summary and Future work