Project topics and materials
Get Complete Project Material File(s) Now! »
Efficient 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 [20]. We explain briefly each category and details eight broadcast protocols belonging to four categories. Because simulation of [20] showed that an MPR-based broadcast protocol was generally efficient 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 storeand- forward routing into four categories as seen in [20]: 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 transmission distance and let a node forward the received packet only if its forwarding reaches a sufficiently large additional coverage area. Neighbor knowledge approaches maintain neighborhood 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.In this section, we explain common operations for all protocols belong to four categories to process and to forward packets as seen in [6]. Each packet encapsulates one more broadcasted 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 originator 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 retransmitted, 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 message has already been considered for forwarding and should be retransmitted again.
Otherwise: the message must be considered for forwardin ”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 forwarding. 4. If the time to live of the message is greater than ’1’, the message MUST be retransmitted (as described later in steps 6 to 8).
Efficient Broadcasting Extension to Wireless Mesh Networks
MPR-based broadcasting is an efficient broadcasting method with classical store-and-forwardbroadcasting in wireless networks. MPR-based broadcasting reduces the transmission number by decreasing the size of a forwarder set. One practical application is to use the efficient MPR-based broadcast protocol with an OLSR protocol for mesh networks, which is specifically 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 extension 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 applied 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.
Practical Framework of Network Coding
In this chapter, we explain the practical framework of network coding in order to use linear coding and random linear coding. A shorter instant primer on network coding can be found in [49].
Linear Coding
Network coding, as well as its benefits were first introduced by Ahlswede et al [8]. Ahlswede et al. [8] showed that with network coding, as symbol size approaches infinity, a source can multicast information at a rate approaching the smallest minimum cut between the source and any receiver. Since then, coding methods to achieve the multicast max-flow rates had been researched. Li et al. [50] showed that in single source multicasting, linear coding on a finite field (Galois field) is sufficient to achieve the individual max-flow rates between the source and any receiver. Koetter and Medard [51] presented an algebraic framework that extended previous results to unreliable networks, and proved the applicability of the min-cut max-flow bound for networks with delay and cycles.
Table of contents :
Preface
Acknowledgments
1 Introduction
1.1 Overview
1.2 Contribution
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
2.3 Summary
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.1 Overview
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
4.8 Summary
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
5.3 Summary
6 Summary and Future work
Bibliography
