Int'l J. of Communications, Network and System Sciences
Vol.07 No.10(2014), Article ID:50519,13 pages
10.4236/ijcns.2014.710042

Network Coding and Quality of Service for Mobile Ad Hoc Networks

Michael Hay1, Basil Saeed1, Chung-Horng Lung1, Thomas Kunz1, Anand Srinivasan2

1Systems and Computer Engineering, Carleton University, Ottawa, Canada

2EION Inc, Ottawa, Canada

Email: mhay@sce.carleton.ca, bsaeed@sce.carleton.ca, chlung@sce.carleton.ca, tkunz@sce.carleton.ca, anand@eion.ca

Copyright © 2014 by authors and Scientific Research Publishing Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

Received 22 August 2014; revised 18 September 2014; accepted 30 September 2014

ABSTRACT

Network Coding is a relatively new forwarding paradigm where intermediate nodes perform a store, code, and forward operation on incoming packets. Traditional forwarding approaches, which employed a store and forward operation, have not been able to approach the limit of the max-flow min-cut throughput wherein sources transmitting information over bottleneck links have to compete for access to these links. With Network Coding, multiple sources are now able to transmit packets over bottleneck links simultaneously, achieving the max-flow min-cut through- put and increasing network capacity. While the majority of the contemporary literature has focused on the performance of Network Coding from a capacity perspective, the aim of this research has taken a new direction focusing on two Quality of Service metrics, e.g., Packet Delivery Ratio (PDR) and Latency, in conjunction with Network Coding protocols in Mobile Ad Hoc Networks (MANETs). Simulations are performed on static and mobile environments to determine a Quality of Service baseline comparison between Network Coding protocols and traditional ad hoc routing protocols. The results show that the Random Linear Network Coding protocol has the lowest Latency and Dynamic Source Routing protocol has the highest PDR in the static scenarios, and show that the Random Linear Network Coding protocol has the best cumulative performance for both PDR and Latency in the mobile scenarios.

Keywords:

Network Coding, Mobility, Quality of Service, Mobile Ad Hoc Networks, Performance Evaluation

1. Introduction

Broadcasting is a linear transmission mechanism, including multimedia traffic, in real time. Several types of multimedia devices, such as computers and mobile devices, 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 digital multimedia broadcasting standards support high definition television, multiple standard definition television program streams, and private data applications, such as multimedia pager data burst, audio streaming, video streaming, etc.

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 communications paradigm presents challenges not seen in the 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 media access control (MAC) model used for layer 2 of the network stack or the data link layer.

As wire line and wireless networks scale and evolve to support more users, Internet Service Providers (ISPs) are interested in knowing and predicting Quality of Service (QoS) metrics such as Throughput, Delay, and Reliability, as this knowledge can be used to define value propositions for consumers and increase revenue.

Network Coding (NC) has emerged as a promising paradigm that has the potential to increase the capacity of a network. First proposed by Ahlswede et al. [1] for wire line networks, current research has presented a new focus where Network Coding is slowly being integrated into the wireless domain. While there is growing evidence for the impact of NC routing protocols on the throughput for both wired and wireless networks, other equally important aspects for QoS, e.g., delay and reliability, remain largely understudied. Further, there are various NC schemes and different routing protocols for MANETs. The effect of those NC schemes on different routing protocols needs to be investigated to better understand the impact on QoS, which could provide practically useful information for ISPs.

As the popularity of multimedia video and the number of mobile units increase rapidly (from 19.4 million in 2010 to projected 198.2 million in 2016 [2] ), more emphasis is placed by ISPs to guarantee an expected level of service or QoS. Furthermore, multimedia applications, such as video and voice over IP (VoIP), require low Latency and largely in sequence for packet transmissions to ensure that the quality of experience (QoE) is preserved on the receiving end. A well defined QoS solution for these media can guarantee that the user experience is not degraded.

While there exists limited support for QoS in some infrastructure modes of wireless communication, the need for QoS support for MANETs becomes critical due to changing link properties, mobility, power consumption, and route maintenance [3] .

Due to the added benefit that NC protocols provide, we are motivated to investigate the effect that NC protocols have on selected QoS metrics for various routing protocols used in MANETs. It is both theoretically and practically important to understand the impact that NC protocols have on QoS for MANETs. The NC protocols that have been investigated in this study include: XOR, Reed Solomon (RS), and Random Linear Network Coding (RLNC). Ad hoc routing protocols, see Section 3.1, try to address the QoS and QoE issue in different ways, based on a packet-forwarding paradigm. Therefore, a comparison between these ad hoc protocols, NC protocols, and a combination of routing and NC protocols will aid in understanding the impact that NC has on the QoS for MANETs.

Not many studies have been reported in the literature on the effect of NC on QoS metrics for MANETs. Moreover, three different mobility models also have been used for the investigation: Random Waypoint, Reference Point Group, and Manhattan Grid. Thus, the main contribution of this paper is a systematic investigation of the potential benefits of several NC techniques by comparing them with various routing protocols for MANETs coupled with those three different mobility models. A number of simulations have been performed using NS2 to compare the QoS results for various techniques or a combination of techniques.

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

Originally Network Coding theory was developed in the context of wire line networks where multicast packets traveling through a network were combined using techniques, such as: 1) XOR, 2) Reed Solomon, or 3) Random Linear Network Coding.

2.1. XOR Network Coding

Traditional transmission over a wired or wireless medium could be described as consisting of the following parts. Using the topology shown in Figure 1 [4] , node 1 sends information to node 2, who then forwards this information to node 3. Node 3 then transmits to node 2 who forwards the information to node 1 taking a total of 4 time slots.

For XOR NC, if nodes 1 and 3 wish to exchange information it could be performed via the following: 1) node 1 transmits to node 2, 2) node 3 transmits to node 2, 3) node 2 performs a coding operation on the information and transmits to both nodes 1 and 3, taking a total of 3 time slots as seen in Figure 2 [4] . 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. For example, consider an XOR coding scheme based on the topology shown in Figure 1(b). The relay upon receiving the packets from nodes 1 and 3, XORs both packets together, transmitting the new XOR' packet such as:

(1)

where denotes the bit-wise exclusive OR over the entire length of the frame [4] . Each receiver, upon receiving this XOR'ed packet will extract the information intended to be sent to it via XORing the received packet with its own packet originally sent to the relay. For example, node 1 will be intent upon receiving so it will perform the operation:

(2)

2.2. Reed Solomon (RS) Network Coding

In a telecommunications medium, errors occur randomly due to signal attenuation, interference, cross talk, and other factors. Recovering from these errors has lead to a large area of theory referred to as Channel Coding or Forward Error Correction (FEC) coding. In this communications paradigm, the sender encodes its transmission using an Error Correcting Code (ECC), adding redundant data to the original symbol. The redundant data is subsequently used at the receiver to recover from a limited number of random bit errors. Two subcategories of FEC codes are 1) block codes, and 2) convolution codes. Block codes operate on fixed blocks of data, while convolution codes operate on bit streams of arbitrary length.

Block codes operate on fixed length data segments, by adding redundant parity information bits, producing a new data segment of bits in length. Reed Solomon (RS) codes were first introduced in the seminal

Figure 1. Standard routing techniques.

Figure 2. XOR Network Coding routing techniques.

work [5] , which is used for block codes. The authors of [6] created a novel NC technique using RS coding. In this work, the authors applied RS coding to groups of packets received from multiple sources. The authors exploited the fact that in order for neighbors to receive a batch of packets, they need only to receive k (k < n) packets provided that they also have native packets stored locally. With packets already retained locally, the node can decode the rest of the missing packets. For more detail the reader is referred to [7] .

2.3. Random Linear Network Coding (RLNC)

The derivation of Network Coding technique is important and well-explained in the literature, but most researchers do not explain how to incorporate the capacity gain of Network Coding in practical network systems. Given the results from Network Coding theory, we know that there may exist a finite field for which we can choose linear coefficients that will allow us to encode packets together so that multiple sources may achieve the broadcast capacity of an arbitrary network simultaneously. However, how large should the finite field be in practice, and since we are choosing coefficients for the linear combinations and form them in matrices how can we ensure that all matrices are full rank? A proof for an appropriate field size is presented in [8] - [10] .

The choice of linear codes presents a problem in that one would need complete knowledge of the connected network graph to ensure that all matrices are full rank. However, if the coefficients are chosen randomly at every node (as is the case in Random Linear Network Coding) then there exists no need for any centralized control architecture. The issue that would then become apparent is what is the probability of choosing linear codes at random so that all are full rank, a scenario necessary for no decoding errors in the network? From [9] it was shown that the matrices will be full rank with a high probability of 0.996.

With the knowledge of appropriate field sizes as well as a distributed coding scheme that can be employed independently throughout the network, the task now is to take the Network Coding theory and apply it to packet transmissions. Each packet could be considered as a symbol in regards to the classical Network Coding theory. And any receiver can recover (with a high probability) from any received packets using RLNC [10] . The additional overhead of RLNC for each packet due to extra header information containing the global encoding vectors is relatively small [10] . However, the advantages of RLNC are that it provides a distributed protocol in which each receiver can decode packets without any knowledge of network topology and receivers can decode information in the presence of node or link failures [10] .

Packets related to the same set or source vectors are usually transmitted sequentially over the same network edge. Furthermore, the number of packets traveling on an edge related to the same set of source vectors varies over time due to packet loss and network congestion. Therefore, synchronization of packets related to the same set of source vectors becomes an important issue.

Chou et al. [10] proposed a buffering model to deal with the synchronization issue. Packets related to the same set of h source vectors are part of the same generation and h is called the generation size. All packets of the same generation have the same generation number in the packet header while different generations will use a subsequently different generation number in their headers. Using a buffer, each node can then store incoming packets sorted by the generation number. When there exists a transmission opportunity, a node can generate a new packet based on linear combinations of received packets (held in its buffer) from the same generation [10] .

When a destination indicates that it has enough linear combinations to decode the current generation, source nodes empty that generation from their buffer and continue creating linear combinations of packets consisting of the next generation. The next section of this report will discuss the NC techniques that have been developed to date.

3. Performance Metrics and Simulation Results

Current research NC has focused on the systemic capacity problem: how to increase capacity (add more users/traffic to the network) without changing the infrastructure (adding more physical resources). It has been shown that NC can increase the amount of information transmitted per unit time [1] [11] [12] , thereby increasing capacity.

While it is easier to evaluate static topologies, MANETs have an implicit quality that is not taken into consideration in these simulations and studies—mobility. A challenging addition to this research extends the current state-of-the-art, focusing not on capacity but on the generalized QoS for MANETs, and the impact that mobility can have on NC protocols in MANETs. The following sections discuss the routing protocols under study, mobility models used, and QoS metrics used for evaluation.

3.1. Research Methods

3.1.1. Routing Protocols

Disseminating information through a network requires a path from a source to the desired destination. This path is created by intermediate nodes via a routing protocol. Different routing protocols may create different paths through the network, each path having its own unique performance and QoS attributes such as throughput, delay, and reliability.

A first set of routing protocols were taken from the vast literature on routing in MANETs. Unlike the fixed infrastructure, implicit qualities of MANETs, such as mobility, require more dynamic route selection algorithms and therefore employ their own unique routing protocols. The following will provide a description of the ad hoc routing protocols under study.

· Ad hoc On-Demand Distance Vector (AODV): AODV [13] is a unicast routing protocol designed for the dynamic nature of ad hoc networks. Nodes route information through the network using messages such as route request (RREQ), route reply (RREP), and route errors (RERR). When a route to a new destination is needed the sender will broadcast RREQ throughout the network to identify the path to destination. The route is made available by unicasting RREP back to the sender. Each node in the network will store a routing table containing the reverse path towards the nodes originating the RREP messages. To accommodate for the dynamic nature of the ad hoc network, RERR messages are used to notify other nodes when a link is no longer active between 2 nodes.

· Dynamic Source Routing (DSR): In DSR [14] , if a sender does not have an existing route to its desired destination it will use route discovery to find a route. The route discovery is a broadcast message to all neighboring nodes, accumulating a route record along the way. When the destination receives the route discovery it will send a route reply message containing a copy of the accumulated route record, using the reverse path (i.e., the reverse of the accumulated route record). Route Maintenance is used to detect broken links in the network.

· Optimized Link-State Routing (OLSR): Each node using OLSR [15] selects a subset of neighboring nodes to be multipoint relay (MPRs) and only MPRs are responsible for disseminating control traffic through the network. This has the effect of limiting the overhead of broadcasting control traffic through the network. All nodes in the network will periodically transmit HELLO messages to their immediate neighbors for link sensing. Active links will be placed in a local link set. Based on the partial topology knowledge (which needs to be updated periodically), nodes can determine the shortest path to all reachable destinations.

· Partial Dominant Pruning (PDP): PDP [16] is a broadcast protocol that employs the Dominant Pruning (DP) algorithm to reduce the number of broadcast messages coding the network. Unlike the traditional blind flooding, where nodes simply rebroadcast all received information, DP identifies a minimum set of 1-hop neighbor to reach all as yet unreached 2-hop neighbors. PDP is a further optimization of DP that uses fewer forwarding nodes to disseminate the information through the network. PDP makes selections for each data packet to be forwarded, based on its current knowledge of the local topology, including which 2-hop neighbors already received the data packet.

· Simplified Multicast Forwarding (SMF): SMF [17] is another broadcast protocol. Similar to PDP, the goal of SMF is to only have a subset of the network perform the broadcast process, thereby reducing the congestion and overhead required to disseminate a packet from source to destination. A reduced relay set is constructed which is a subset of all possible routers. In other words, SMF separates packet forwarding periodically selects a subset of nodes to act as forwarders. That reduces the cost of making the same selection multiple times, but also takes away the possibility of considering which 2-hop neighbors received a packet already.

A second set of routing protocols employ the concept of Network Coding as explained above. Various NC protocols have been engineered in the contemporary literature. Most fall into three categories:

· XOR: Various XOR NC protocols have been proposed in the literature [18] [19] . This research uses XOR NC implemented over PDP and SMF protocols as described in [19] .

· Reed Solomon: The RS NC protocol implemented over PDP and SMF [19] has been adopted.

· RLNC: Various RLNC implementations have been found in the literature [10] [20] . This research uses the RLNC protocol found in [20] .

3.1.2. Mobility Models

With wireless ad hoc networks, nodes are free to move about within a radius of another access point or node. Thus for simulation, one can define node coordinates manually throughout the simulation time or use an external tool to create movement scenarios. Various mobility models have been discussed for ad hoc networks [13] [21] . Since the goal of this research is to study the impact of mobility within the ad hoc network, the following list provides a brief description of the mobility models used.

· Random Waypoint: The Random Waypoint mobility model is one of the most popular models in the literature. Nodes are initially distributed randomly throughput the simulation area. Each node then waits a random amount of pause time before deciding to move. One a node has decided to move, it will select a random destination in the simulation area and a speed that is uniformly distributed between [minspeed, maxspeed]. Once at the destination, the node will again pause for a random amount of time before repeating another random movement to a new destination with a new speed [13] .

· Reference Point Group Mobility: In Reference Point Group Mobility [13] , mobile nodes travel in one or more groups in the simulation area. The movement of each group of nodes is defined by a group motion vector that describes the movement of the group center. Individual nodes randomly move about their own predefined reference points RP(t). As time progresses from t to t + 1, an individual node will follow a movement vector that is calculated based on the current node RP(t) and the new node reference point RP(t + 1) that is based on the new group center at time t + 1.

· Manhattan Grid Mobility: Another type of mobility is one with a geographic restriction in which nodes must follow a specific path or choose from a set of paths in the simulation area. Examples of these are the Freeway Model in which nodes have a set path or highway through the simulation area, or the Manhattan Grid [21] model used to simulate city streets. In Manhattan Grid, nodes will initially be placed randomly on one of the streets or alleys in the simulation area. Each node will remain stationary for a random amount of time (or pause time). After that time has expired, nodes will randomly select a destination from the existing set of streets or alleys and then follow the shortest path from source to destination.

3.1.3. QoS Metrics

In the contemporary literature most comparisons between protocol performances are based on capacity or throughput. This metric measure how much information can pass through a network in a given unit of time. To complement the existing literature, this research will focus on two QoS metrics detailed below.

Packet Delivery Ratio (PDR): PDR describes QoS metric and will be calculated using Equation (3). Here R is the number of received packets and T is the number of transmitted packets.

(3)

With a simulation consisting of more than one sending and receiving node this can be calculated as shown in Equation (4). Here N is the total number of nodes in the network and s is the number of source nodes sending traffic in the network.

(4)

This will yield a ratio between 0 and 1. A value of 1 meant that every packet that is sent in the network also gets received and there is no information loss. A value of zero indicates that all packets that are sent are lost and never reach their intended recipient.

Latency: Latency, as shown in Equation (5), is a measure of the amount of time it takes for a packet to be transmitted from source to destination and for a single packet can be expressed as:

(5)

In the case of a broadcast packet, this can be generalized to multiple receivers as shown in Equation (6) where N is the number of receiving nodes.

(6)

Averaging for all packets in the whole simulation, Latency can then be expressed as:

(7)

3.1.4. Mobility Model Metrics

Characteristics of a mobility model can be calculated to provide certain quantitative descriptions of the mobility. These metrics include averaged statistics defined in [22] unless cited otherwise.

· Relative Mobility: The speed at which nodes move with respect to all other nodes in the network and is calculated according to [12] .

· Average Node Degree: The number of nodes that each node is connected to averaged throughout the simulation time.

· Average Number of Partitions: The average number of partitions for the network throughout the simulation time. A value of 1 indicates that the network is connected at all times. A value greater than 1 indicates that this is not the case.

· Degree of Separation: The likelihood that two randomly chosen nodes are connected at a randomly chosen point in time throughout the simulation.

· Average Link Duration: The duration that links stay active throughout the simulation times.

· Standard Deviation of Average Link Duration: The standard deviation of the previous metric.

· Total Number of Links: The total number of links generated throughout the simulation time.

3.2. Simulation Design

This section provides the simulation setup and the results obtained in more detail.

3.2.1. Simulation Results

The main research objective was to evaluate the performance of both ad hoc routing and Network Coding routing protocols in the presence of mobility. Simulations were performed in NS2 using mobility files created in Bonnmotion [23] that control each node’s movement. Three different mobility scenarios were studied; 1) Random Waypoint, 2) Manhattan Grid, and 3) Reference Point Group Mobility. For each scenario, 100 mobility files were created for each chosen velocity of [0, 2, 4, 6, ×××, 16, 18, 20] m/s. One or multiple nodes are evenly distributed in the simulation area to act as broadcast sources to other nodes. In case of AODV/DSR/OLSR which are not broadcast protocols, source nodes have up to N connections where each connection represents a link between the source and a neighbor node. This makes AODV/DSR/OLSR to behave like broadcast protocols.

PDR and Latency were determined for each of the 100 simulations for all three mobility scenarios, for each routing protocol and then averaged. We also calculated the 95% confidence intervals to determine whether any observed performance differences are statistically significant. The 802.11 MAC layer was used for all wireless communications throughout these simulations. The important global NS2 parameters can be seen in Table 1. Table 2 shows the ten protocols under study and the abbreviations used on the figures.

3.2.2. Simulation Setup

This section contains the results of the simulations performed in NS2 for studying the PDR and Latency in MANETs. Different simulations were carried out in both static scenarios and mobile scenarios with three mobility models and velocities ranging from 2 to 20 m/s.

Static Scenarios are a baseline scenario in which all the nodes of the network are stationary throughout the simulation time. A total of 40 nodes were placed in a simulation area of 1000 m × 1000 m. All simulations were 200 seconds in length with Constant Bit Rate (CBR) traffic starting at the 20 second mark. The average PDR and Latency metrics can be seen in Table 3 and Table 4, respectively, along with the lower and upper bounds of the 95% confidence interval. From the perspective of PDR, it appeared that since all routes were static that the main differentiating factor in protocol performance was the protocols’ ability to quickly establish routes to the desti-

Table 1. NS2 global parameters.

Table 2. Abbreviations used in figures.

Table 3. Static PDR.

Table 4. Static Latency.

nation, low protocol overhead and low collision rates. As a result, the performance of RLNC in terms of PDR is worse than that of the unicast ad hoc routing protocols. From the perspective of Latency, the best protocol is RLNC, but its standard deviation is second best behind OLSR. We can also see that with static routes the other two types of networking coding, XOR and RS, perform poorly.

Three mobility scenarios were performed for velocities ranging from 2 to 20 m/s. The resulting data is averaged over 100 simulation iterations for the same scenario and velocity. The mobility scenarios included:

· Random Waypoint Simulations: The same NS2 parameters were used as in the static scenarios, except node mobility. For each routing protocol, 100 mobility files were created with Bonnmotion for each velocity between 2 to 20 m/s. The average PDR and Latency for the Random Waypoint simulations can be seen in Figure 3 and Figure 4. Unlike the static simulations, here it can be seen that for PDR the protocols employing Network Coding perform better than protocols without Network Coding. Even the small change in routes introduced by mobility caused the performance of the unicast routing protocols to degrade as velocity increased.

· Manhattan Grid Simulations: As with Random Waypoint, the same NS2 parameters were used. When deciding upon the appropriate number of horizontal and vertical roads in the simulation area we chose 12 square blocks which is a good approximation of an average city layout in a one square kilometer simulation area. The PDR and Latency results are shown in Figure 5 and Figure 6, respectively. It can be seen the best PDR performing protocol is DSR followed by XOR coding, RLNC, and then RS coding. For Latency, the best protocol is OLSR followed by RLNC and PDP/SMF with no coding. As with the Random Waypoint simulations, the XOR and RS coding protocols perform poorly.

· Reference Point Group Mobility Simulations: In this scenario, the number of groups in the simulation area was chosen to be 1 and the same NS2 parameters were used. The PDR and Latency results are presented in Figure 7 and Figure 8, respectively. Here it can be seen that in terms of PDR all protocols perform between 0.94 - 0.99. The worst performing protocol is actually RLNC at 0.94. In terms of Latency, the best performing protocols are DSR and OLSR followed by PDP/SMF with no coding, then RLNC.

· For both static and mobile scenarios, Bonnmotion was used to calculate averaged statistics for each mobility scenario used. These metrics were calculated to aid in the understanding of the characteristics of each mobility scenario and how that impacts the routing protocol performance. These metrics can be seen in Table 5. Each value in the table represents an average over the 100 movement scenarios created for that mobility model and velocity. An explanation on the meaning of each column can be found in [23] . Note that there are two Link Duration columns representing two separate and distinctly unique statistics.

3.2.3. Research Summary

With most of the literature focusing on throughput for a routing protocols performance, this novel research has presented simulation results from the QoS perspective. Some interesting results were observed.

· RLNC: For RLNC, for mobile scenarios with low relative mobility and low Node Degree (such as a static scenario), RLNC achieves very low PDR when compared to all other protocols. RLNC provided the best PDR results in the Manhattan Grid scenarios. In fact, as the velocity of the nodes increased the PDR actually improved as seen in Figure 4. This characteristic was not seen in any other protocol. RLNC performs well in

Figure 3. PDR for Random Waypoint simulations.

Figure 4. Latency for Random Waypoint simulations.

Figure 5. PDR for Manhatten Grid simulations.

Figure 6. Latency for Manhatten Grid simulations.

Figure 7. PDR for Reference Point Group Mobility simulations.

Figure 8. Latency for Reference Point Group Mobility simulations.

Table 5. Protocol independent metrics for all scenarios.

terms of Latency regardless of the movement scenario used. On the whole, for the mobile scenarios RLNC had the best cumulative performance for both PDR and Latency.

· XOR NC: For the static scenarios, XOR NC was only marginally better than OLSR in terms of PDR and had the worst performance for Latency. For the mobile scenarios, XOR NC had one of the best PDR results across all mobility scenarios but suffered from poor Latency across all mobile scenarios. The main reason is that there is a delay until the receiving node decides to encode the packet, as this node builds up a buffer to increase the chances of packets being coded together, i.e., increasing the coding opportunities. This may take a significant amount of time.

· RS NC: The performance of the RS coding was very similar to that of the XOR coding. For the mobile scenarios, RS NC achieved good PDR results and poor Latency across all mobile scenarios. Similar to XOR NC, this is also likely a function of the encoding process.

· Ad Hoc Protocols: There did not appear to be any one particular routing protocol that could effectively achieve both QoS parameters. The best protocol overall was shown to be DSR from a PDR perspective and OLSR for Latency. Whereas for NC, RLNC was a consistent performer across both metrics for all mobility scenarios.

· Protocol Independent Mobility Metrics: From [24] , the authors did posit that there were certain protocol independent metrics, such as average link duration and relative mobility that could account for the performance of an ad hoc routing protocol when in a mobile scenario. Their conclusion was that there does exist a high degree of correlation between the Average Degree of Spatial Dependence, Average Relative Speed, Average Link Duration, and the protocol performance metrics of packet delivery ratio and routing overhead. The mobility pattern influenced the connectivity which in turn influenced the protocol performance [24] . When comparing the throughput of ad hoc routing protocols for the mobility models of Random Waypoint to that of a Reference Point Group Mobility model, we found that for the same relative speed, nodes in the group mobility models had a higher Average Spatial Dependence, which lead to a higher link duration, fewer dropped packets and thus higher PDR. This relationship also appears in this research as shown in Table 5. For the ad hoc protocols, their average performance does increase when the relative mobility is low and the average node degree is high. However this characteristic effect was not as pronounced for RLNC. While its PDR performance did improve for high average node degree and low relative mobility as seen in the RPGM simulations, it also exhibited high performance for the Manhattan Grid simulations which were characterized by high relative mobility and low average node degree.

4. Conclusions

With the increase in wireless communications decade coupled with the need for increased data rates and QoS for multimedia applications, Network Coding has emerged and it has been shown to add values to the contemporary networking paradigm. While most contemporary research has presented the throughput performance of these new protocols, this paper has taken a new direction, focusing on the QoS of these routing protocols in terms of PDR and delay. QoS performance is critical for multimedia applications from the perspectives of both user experience and ISPs competitions.

From the simulation results we can conclude that the best overall performer has been RLNC, when compared to the nine other protocols. This was observed for both PDR and Latency. XOR and RS coding techniques performed well from the PDR perspective but lacked acceptable performance in the delay metric.

When observing the protocol independent metrics for all simulations it was shown that the effect of relative mobility and average node degree on the performance of RLNC was less than that of the other protocols. As such it is suggested that this be studied in more detail in future research.

References

  1. Ahlswede, R., Cai, N., Li, S.-Y.R. and Yeung, R.W. (2000) Network Information Flow. IEEE Transactions on Information Theory, 46, 1204-1216. http://dx.doi.org/10.1109/18.850663
  2. MobiThinking (2012) Global Mobile Statistics 2012 Part A: Mobile Subscribers; Handset Market Share; Mobile Operators. http://mobithinking.com/
  3. Mohapatra, P., Li, J. and Gui, C. (2003) QoS in Mobile Ad Hoc Networks. IEEE Wireless Communications, 44-52.
  4. Zhang, S., Liew, S.C. and Lam, P. (2006) Physical-Layer Network Coding. Proceedings of the 12th Annual International Conference on Mobile Computing and Networking, 358-365.
  5. Reed, S. and Solomon, G. (1960) Polynomial Codes Over Certain Finite Fields. Journal of the Society for Industrial and Applied Mathematics, 8, 300-304. http://dx.doi.org/10.1137/0108018
  6. Jaggi, S., Sanders, P., Chou, P.A., Effros, M., Enger, S., Jain, K. and Tolhuizen, L. (2005) Polynomial Time Algorithms for Multicast Network Code Construction. IEEE Transactions on Information Theory, 51, 1973-1982. http://dx.doi.org/10.1109/TIT.2005.847712
  7. Li, E.L., Ramjee, R., Buddhikot, M.M. and Miller, S.C. (2007) Network Coding-Based Broadcast in Mobile Ad Hoc Networks. Proceedings of INFOCOM, Anchorage, 6-12 May 2007, 1739-1747.
  8. Koetter, R. and Medard, M. (2002) Beyond Routing: An Algebraic Approach to Network Coding. Proceedings of INFOCOM, 1, 122-130.
  9. Chou, P., Wu, Y. and Jain, K. (2003) Practical Network Coding. Proceedings of Allerton Conference on Communication, Control and Computing, October.
  10. Ho, T., Karger, D.R., Medard, M. and Koetter, R. (2003) Network Coding from a Network Flow Perspective. IEEE International Symposium on Information Theory, 29 June-4 July 2003, 441.
  11. Camp, T., Boleng, J. and Davies, V. (2002) A Survey of Mobility Models for Ad Hoc Network Research. Wireless Communications and Mobile Computing, 2, 483-502.
  12. Johansson, P., Larsson, T., Hedman, N., Mielczarek, B. and Degermark, M. (1999) Scenario-Based Performance Analysis of Routing Protocols for Mobile Ad Hoc Networks. Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, Seattle, 15-19 August 1999, 195-206.
  13. AODV (2003) Ad Hoc On-Demand Distance Vector (AODV) Routing. http://www.ietf.org/rfc/rfc3561.txt
  14. DSR (2007) The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4. http://www.ietf.org/rfc/rfc4728.txt
  15. OLSR (2003) Optimized Link State Routing Protocol (OLSR). http://www.ietf.org/rfc/rfc3626.txt
  16. Lou, W. and Wu, J. (2002) On Reducing Broadcast Redundancy in Ad Hoc Wireless Networks. IEEE Transactions on Mobile Computing, 1, 111-122. http://dx.doi.org/10.1109/TMC.2002.1038347
  17. SMF (2012) Simplified Multicast Forwarding. http://tools.ietf.org/html/draft-ietf-manet-smf-14
  18. Katti, S., Rahul, H., Hu, W., Katabi, D., Medard, M. and Crowcroft, J. (2006) XORs in the Air: Practical Wireless Network Coding. Proceedings of SIGCOMM, 36, 243-254.
  19. Kunz, T. and Li, L. (2010) Broadcasting in Multihop Mobile Tactical Networks: To Network Code or Not. Proceedings of IWCMC, Caen, 28 June-2 July 2010, 676-680. http://dx.doi.org/10.1145/1815396.1815551
  20. RLNC for NS2.27. http://telecom.dei.unipd.it/pages/read/58/
  21. Bai, F. and Helmy, A. (2004) A Survey of Mobility Models. Wireless Ad Hoc Networks.
  22. Bai, F., Sadagopan, N. and Helmy, A. (2003) The IMPORTANT Framework for Analyzing the Impact of Mobility on Performance of Routing Protocols for Adhoc Networks. Ad Hoc Networks, 1, 383-403. http://dx.doi.org/10.1016/S1570-8705(03)00040-4
  23. BonnMotion. http://net.cs.uni-bonn.de/wg/cs/applications/bonnmotion/
  24. Gajic, B., Riihijrvi, J. and Mahonen, P. (2009) Performance Evaluation of Network Coding: Effects of Topology and Network Traffic for Linear and XOR Coding. Journal of Communications, 4, 885-893.