Multimedia Streaming for Ad Hoc Wireless Mesh Networks Using Network Coding ()
1. Introduction
Broadcasting is a linear transmission mechanism including audio and video traffic in real time. Several types of devices such as TVs, radios, computers and mobile devices (cell phones) are used as receivers to gain access to one broadcasted traffic flow at a time per channel with pre-scheduled start and end times. The receivers are controlled by the users to be switched on or off, as well as being controlled by frequency tuning. Practically, all of the content offered by mobile, radio and TV stations today are available only in this approach. The digital multimedia broadcasting standards support high definition television (HDTV), multiple standard definition television (SDTV) program streams, and private data applications such as broadcast duplicate transmissions, multimedia pager data burst, HTML pages, audio streaming, video streaming, etc. [1].
With the explosion of Internet traffic seen over the past two decades, coupled with the ever increasing need to access critical data at any location, wireless networks have emerged as a means of effectively communicating in an on-demand fashion from nearly any location. This new communication paradigm is inherently based on a broadcast medium and presents challenges not seen in traditional wire line networks due to the nature of the wireless medium in which users must share access to: 1) frequencies or 2) time-slots controlled by the Medium Access Control (MAC) model used. The challenges include bandwidth limitations, mobility impacts, energy consumption, unreliable transmission, security issues and dead spots.
We have witnessed an explosive growth in the use of multimedia applications with mobile and static devices lately. Multimedia broadcasting in wireless networks intends to transmit concurrently identical multimedia traffic to multiple receivers. The main important trends for mobile and static multimedia broadcasting are: 1) Mobile traffic is growing significantly, and will be dominated by video and voice; 2) Mobile devices are getting more powerful; 3) mobile graphics are getting better [2]. As a result, mobile multimedia users are expected to grow rapidly as shown in Figure 1 which shows the growth trend for audio streaming applications presented in [3], and Figure 2 which shows the growth trend for TV and video user as it is expected to blossom to more than four hundred and fifty million by 2014 [2].
Figure 2. Mobile video/TV users from 2004-2014 [2].
Due to the above mentioned growth trend in the number of mobile users, the wireless multimedia broadcasting services are faced with a number of challenges: the wireless capacities are still limited and can not support rich multimedia traffic to mobile devices because of the increase in video and voice qualities, which leads to an increase in the packet size of the multimedia traffic (video and voice).
Furthermore, multimedia-streaming traffic is extremely time-sensitive, as it requires timely delivery of each multimedia packet. Packets that are received beyond an application-specific deadline are ignored by the application and the transmission therefore wastes precious wireless bandwidth. The original playout delay at the receiver essentially influences the application acceptance and the user’s reliability [4].
Exploiting the characteristics of the wireless medium, especially the broadcast communication channel, Network Coding (NC) has emerged as a promising paradigm in order to increase the capacity or the throughput of the network. NC originally was proposed by Ahlswede et al. [5] for wired networks, but Li et al. [6] were among the first to apply network coding to the wireless domain. All nodes (sending or intermediate nodes) act as a relay and also can combine several received packets into one or several encoded outgoing packets, thus the performance of the network increases in terms of throughput, delay, and etc.
Due to the benefits of NC and the increasing popularity of multimedia applications, we were motivated to apply NC mechanisms to multimedia wireless broadcasting applications. Likewise, many proposed broadcast protocols (with or without NC) have parameters that can be set to suitable values to tune their performance in the face of the above mentioned challenges. It is both theoretically and practically important to find a solution where several types of multimedia traffic can be delivered successfully to the destinations in a way that satisfies the customers.
In this paper, we have studied broadcast protocols that work well with both single source and multiple sources networks. The paper also has investigated the potential benefits of several NC techniques, such as Random Linear Network Coding (RLNC), Reed Solomon (RS) codes, and XOR, where the NC mechanism combines different packets generated by different sources into a single encoded packet. The paper investigates various NC techniques for multimedia streaming such as audio and video streaming. We have shown through simulations that RLNC is able to adapt well to audio and video streaming applications and to provide stable performance in terms of packet delivery ratio (PDR), latency and jitter. We also compare RLNC’s performance with three popular and efficient broadcast protocols, e.g., BCast, Simplified Multicast Forwarding (SMF) and Partial Dominant Pruning (PDP).
The rest of the paper is organized as follows. Section 2 introduces the protocols used in this paper. Section 3 describes the simulation environment and simulation results for various scenarios. Finally, in Section 4, we conclude the paper and suggest some possible lines for future research.
2. Background
This section first discusses the BCast, SMF, and PDP broadcast protocols which are used in the paper. BCast, SMF and PDP are three efficient broadcast protocols for Mobile Ad-hoc Networks (MANETs) and wireless mesh networks [7,8]. Following that, the section briefly describes some network coding schemes that have been used for broadcast. Those network coding schemes include XOR, RS, and RLNC.
2.1. BCast Protocol
The BCast protocol [8,9] is a scalable broadcast algorithm that uses 2-hop neighbor knowledge. Each node periodically sends discovery messages that contain a node’s identifier, e.g., IP address, and its list of identified neighbors. When the discovery messages are received by a node from all its neighbors, then this node has 2-hop topology information. For example, when node “B” receives a discovery packet from node “A”, then “B” knows all neighbors of “A”. Also, if “B” has neighbors not covered by one of its neighbors “A”, “B” prepares a discovery message to be broadcasted to its neighbors. If “B” receives a discovery message from another neighbor “C” before sending its own discovery message, “B” will drop the discovery message and initiates a new message with the newly received information.
BCast is also a reliable broadcast algorithm, where nodes buffer the most recent packets. For example, if node “A” receives packet “N” from sender “B”, “A” will check if packet “N-1” was received from the sender as well. If not, “A” will ask its neighbors to retransmit packet “N-1” by sending a “NACK” packet that includes the information about the missing or delayed packet. Nodes receiving a “NACK” packet will check their buffer, and if they have the missing or delayed packet buffered, they will schedule a retransmission. If nodes overhear another node retransmitting that packet, those nodes will cancel their own retransmission.
2.2. Simplified Multicast Forwarding
The Simplified Multicast Forwarding (SMF) protocol is an optimized multicast/broadcast protocol which provides a forwarding plane for packets from source to destination. The key benefit of the SMF protocol is the improvement of the performance of relays in dynamic networks. Using the concept of Multipoint Relays (MPRs) from the Optimized Link State Routing (OLSR) [10] Protocol, SMF heuristically selects only a subset of nodes to retransmit data packets to reach all nodes in a network. The subnet is created using a two-hop neighbor discovery mechanism by periodically sending Hello messages. The nodes then select and signal a subset of their onehop neighbors as MPR nodes. Moreover, SMF has a duplicated packet detection mechanism to avoid retransmiting any repetitive packets. This mechanism uses the IP address Identification “ID” field to detect any duplication where each packet has a unique “ID” field [7,11].
2.3. Partial Dominant Pruning
Dominant Pruning (DP) is a broadcast protocol which aims to minimize the number of transmissions. Similar to the case of SMF, DP uses HELLO messages to collect information about 2-hop neighbors in the network. Based on the collected information and the Partial Dominate Pruning (PDP) algorithm, the source node selects a set of nodes to broadcast the sent packet rather than having all source’s neighbors retransmit, taking into account which neighbors have already received the packet. This increases the data packet size, as more information will be attached to the header of the data packet. Moreover, the HELLO messages of the PDP algorithm are smaller, as they do not carry information about MPR selection, compared to SMF. The PDP algorithm is considered as one of the optimized broadcast protocol for MANETs and wireless mesh networks [7,12].
2.4. SMF and PDP with Network Coding Techniques
NC-based transmission techniques seek to combine packets from different sources and transmit these combined packets into a single or multiple transmissions [1]. The receiver decodes the received combined packets to recover the original/desired data when it receives enough information that is needed in the decoding procedure. As shown in Figure 3, if nodes “1” and “3” wish to exchange information it could be performed via the following: 1) node “1” transmits S1 to node “2”; 2) node “3” transmits S3 to node “2”; 3) node “2” performs a coding operation on the information and transmits S2 to both nodes “1” and “3”, taking a total of 3 time slots. The received information is then decoded at the edges, an operation that is based on the type of network coding employed in the original coding operation.
SMF and PDP have been extended with two NC techniques; XOR and Reed Solomon (RS) [7]. In both techniques, a node keeps monitoring the wireless medium and collects information about its 1-hop and 2-hop neighbors. A node opportunistically, and without additional control packets, maintains information about which packets were already received by what neighbor to guide its encoding decision. The exploit these coding opportunities, nodes accumulate data packets in a small internal buffer (typically 4 to 8 packets). Once the buffer is full or a protocol-specific timeout occurs, a node will determine which buffered packets to code together, based on its knowledge of the reception state of its neighbors and the specific NC scheme.
The XOR network coding (XOR-NC) technique is one of the simplest digital network coding techniques to encode and decode data packets. Using XOR-NC, the relay combines the received packets into one packet using an XOR operation and broadcasts the new packet to receivers. Receivers can then decode the encoded message by XORing it with their prior packet(s) [7].
Figure 3 shows an example of the XOR-NC approach which would be performed as following in the wireless networks. Both node “1” and node “3” send their packets respectively to the relay (node “2”) using different time slots. The relay combines the received packets into one