Sage Journals: Discover world-class research

Abstract

Network coding–based routing has been widely considered as a promising technology to improve the network throughput of wireless multihop network. However, existing network coding aware routings have the problem of failure decoding and usually neglect the transmission scheduling, which degrades the gain of network coding. In this article, a common network coding condition and traffic matching supported network coding aware routing is proposed for wireless multihop network. In this, common network coding condition is proposed to avoid the problem of failed decoding. In addition, traffic matching mechanism is presented to promote the occurrence of network coding. Besides, a coding and load aware routing metric, which jointly considers the network coding opportunity and node load, is designed to evaluate the discovered paths. Extensive simulations on NS2 demonstrate that CTNR increases the number of coding opportunities and network coding occurrence, and improves network throughput.

Keywords

Wireless multihop network network coding routing network coding condition traffic matching load balancing

Introduction

Wireless multihop network¹ consists of nodes with wireless communication capability. Each node in wireless multihop network acts as both end device and router. The typical wireless multihop networks include wireless mesh networks (WMNs),² wireless sensor networks (WSNs),³ mobile ad hoc networks (MANETs),⁴ and vehicular ad hoc networks (VANETs).⁵ Compared with other wireless communication systems, for example, cellular network, the wireless multihop network can be easily deployed at low cost without fixed infrastructure and can be applied in many fields, such as emergency communication, environmental monitoring, and so on.

The transmission in a wireless multihop network from source to destination, which is out of the transmission range of the source, needs the relaying of intermediated nodes. Therefore, routing which determines the path of the transmission is critical to the performance of wireless multihop network.^6–8 However, due to the open nature of wireless channel, the transmission in wireless multihop network is easily influenced by wireless interference, which leads to low network throughput and makes routing in wireless multihop network a great challenge.

From the perspective of traditional information theory, any operation to the received packets at intermediate node brings no gain and store-forward manner has been widely recognized as the main working manner for network. In 2000, network coding was first proposed by Ahlswede et al.,⁹ which illustrated that network coding at intermediate node can increase the multicast transmission rate. Li et al.¹⁰ further gave the proof that the transmission rate of multicast using network coding can achieve the theoretical upper bound of multicast rate determined by the max-flow min-cut theory. In particular, the network coding in wireless network can reduce the number of transmissions, improve network throughput, and alleviate wireless interference.¹¹ Therefore, network coding is especially suitable for wireless multihop network.¹²

To demonstrate the advantages of network coding in wireless environment, take the scenario in Figure 1 as an example. In Figure 1, there are two flows: $flow 1$ and $flow 2$ . $flow 1$ wants to send packet $P 1$ to node 3 via node 2, while $flow 2$ wants to send packet $P 2$ to node 1 via node 2. If the traditional store-forward manner is used in the network, four transmissions are needed as shown in Figure 1(a). However, if node 2 XORs the received packets and broadcasts the coded packet $P 1 \oplus P 2$ , node 1 can obtain native packet $P 2$ through $(P 1 \oplus P 2) \oplus P 1 = P 2$ , and node 2 can get $P 1$ through $(P 1 \oplus P 2) \oplus P 2 = P 1$ as shown in Figure 1(b). It is obvious from Figure 1 that only three transmissions are needed using network coding compared with the store-forward manner, and the number of transmissions is reduced by 25%.

Figure 1.

Comparison of store-forward manner and network coding in multihop network. (a) Store-forward manner. (b) Network coding manner.

Due to the potentials of network coding in improving the performance of wireless multihop network, some network coding–based routings^13–15 have been proposed. The network coding applied in routings is network layer network coding, instead of physical layer network coding.¹⁶ The physical layer network coding can also improve the network throughput. However, each packet involving physical layer network coding needs to be synchronized strictly, which is difficult to be realized in the distributed wireless multihop network. Therefore, the network layer network coding is usually exploited in the routings for wireless multihop network. Actually, the network coding applied in routings can be divided into intraflow network coding and interflow network coding, according to the packets involving network coding belong to the same flow or different flows. The intraflow network coding–based routings usually use random linear network coding and combine with opportunistic routing to improve the reliability of transmission,¹⁵ whereas interflow network coding–based routings usually exploit XOR operation to reduce the number of transmissions and improve network throughput. The interflow network coding–based routing, which is also known as network coding aware routing or coding aware routing, is the focus of this article.

The coding opportunity architecture (COPE)¹⁷ for wireless multihop network and classical coding topologies were proposed. But the network coding opportunities discovery in COPE is independent of routing discovery, and the classical coding topologies are limited within one hop range of coding node, which both neglect potential coding opportunities. The routing with opportunistically coded exchanges (ROCX) and the concept of network coding aware¹⁸ were proposed, which combine network coding opportunities discovery with routing discovery to increase coding opportunities among routes. But ROCX detects coding opportunities based on the classical coding topologies.

The distributed coding aware routing (DCAR)¹⁹ was proposed. In DCAR, the multihop network coding condition (MNCC) was proposed, which extends the range of classical coding topologies in COPE. However, the false coding effect may exist in some scenarios using MNCC,²⁰ and generalized coding condition (GNCC) and free-ride-oriented routing (FORM)²⁰ were proposed. Network coding and interference are jointly investigated by Peng et al.²¹ and Hou et al.²² But Peng et al.²¹ exploits the classical coding topologies as ROCX to detect coding opportunities, and the network coding condition is not considered by Peng et al.²¹ The improved generalized coding condition (IGCC) was proposed.²³ But the overheard packets in IGCC must be native packets. And IGCC includes five rules and is hard to be realized. The distributed greedy coding aware deterministic routing (DGCDR) was proposed.²⁴ Nevertheless, the coding condition in DGCDR is only necessary, not sufficient.

The classic network coding routings put emphasis on the increasing of coding opportunities through improving the network coding conditions.^13–15 However, existing network coding conditions are only valid under certain conditions and may lead to failure decoding problem in certain scenarios. On the other hand, network coding opportunity at one node only means that network coding potentially take place at the node, but existing coding aware routings exploit opportunistic network coding scheduling (ONCS) for packets transmission scheduling, which cannot guarantee the occurrence of network coding. Take the scenario in Figure 1(b) as an example. The network coding needs packets from different flows. But due to the wireless channel contention, the wireless node cannot receive packets from different flows at the same time, for example, node 2 can only receive P1 and P2 one by one. If P1 is not queued at node 2, and sent out immediately after being received, the coding operation of $P 1 \oplus P 2$ will not take place. Therefore, the packets transmission scheduling directly affects the occurrence of network coding, and finally influence the performance of coding aware routings.

Currently, some network coding–oriented scheduling algorithms have been proposed.^25–31 The flow-based scheduling algorithm was proposed²⁵ to improve the throughput of COPE. Markov model–based scheduling algorithms were presented.^26–31 But the references^26–29 only considered the simple chain topology and infinite length queue, which are not real in wireless multihop network. Shao et al.³⁰ proposed traffic shaping–based transmission scheduling. Lu and Wan³¹ presented the low-jitter wireless transmission algorithm based on buffer management (BLJCR). However, references^25,29,30 do not consider the improvement of network coding condition.

To solve the problems of network coding condition and transmission scheduling in existing network coding aware routings, this article proposes common network coding condition and traffic matching supported network coding aware routing (CTNR) for wireless multihop network. In CTNR, the common network coding condition (CNCC) is proposed. CNCC can be applied to determine the network coding opportunity of general scenarios, for example, multiple flows with multiple coding nodes. In addition, the traffic matching mechanism (TMM) is presented to match the packets from different flows existing network coding opportunity, which increases the number of actual network coding occurrence. Extensive simulations on NS2 demonstrate that CTNR increases the number of coding opportunities, the percent of coding packets and improve the network throughput.

The contributions of this article are as follows:

The CNCC is proposed to detect network coding opportunities. The proof of sufficiency and necessity of CNCC is presented. The CNCC can be applied in the scenarios of multiple flows with multiple coding nodes. Based on CNCC, more coding opportunities can be discovered and the undecodable problem of previous network coding condition can be avoided.

The TMM is proposed to solve the scheduling problem of wireless network coding. Through traffic matching, the packets from different flows at the node existing coding opportunity can be matched to promote the occurrence of network coding.

A CLRM is presented, which jointly considers the node load and coding opportunity. CLRM can balance the network load and postpone network congestion.

This article is organized as follows: The related works and motivations are presented in “Related works and motivations” section. “Design of CTNR” section gives the detailed design of CTNR routing algorithm. Simulation details and performance analysis are presented in “Simulations and performance analysis” section. “Conclusion” section concludes this article.

Related works and motivations

Before delving into the related works of network coding aware routings, related terms in network coding aware routings are given first. If one node v is on one flow f, and the packets of flow f take place network coding at v, then v is called coding node of flow f and the flow f is called coded flow. For one flow f, if there is no coding node on f, then the flow f is called native flow. The packet that has never been coded is native packet, whereas the packet that has been coded is coded packet.

COPE¹⁷ is proposed by Katti et al. to address the unicast routing through exploiting network coding in wireless multihop network. And five classical coding topologies (Chain topology, “X” topology, Cross topology, and Wheel topology) existing coding opportunities are given in COPE as shown in Figure 2.

Figure 2.

Classical coding topologies in COPE. (a) Chain topology. (b) “X” topology. (c) Cross topology. (d) Wheel topology.

However, it is obvious from Figure 2 that the coding topologies in COPE require that decoding must take place at the next hop of the coding node, which limits the range of coding topologies. On the other hand, the network coding function in COPE is placed between the network layer and MAC layer, which means that network coding in COPE is independent of the routing discovery. Actually, the coding opportunities in COPE are discovered based on five classical coding topologies in the discovered routes, which may miss the routes with more coding opportunities.

For the separation of network coding and routing in COPE, the network coding aware concept was proposed by Ni et al.¹⁸ in ROCX. ROCX combines network coding function with the routing function, which can proactively detect coding opportunities in routing discovery phase. Compared with COPE, ROCX can find the routes with more coding opportunities. Take the scenario in Figure 3 as an example. In Figure 3, there are eight nodes and two flows, $flow 1$ and $flow 2$ . Then node 5 wants to send packets to node 8. If the number of hops is taken as routing metric, $path 1$ and $path 2$ will be discovered by node 5, but $path 1$ will be chosen by COPE, since $path 1$ needs three hops and $path 2$ needs four hops. After the $path 1$ has been chosen as routing, the network coding function will detect the coding opportunities in $path 1$ . However, there is no coding opportunity in $path 1$ . If ROCX is exploited, node 5 also finds $path 1$ and $path 2$ , but ROCX finds that if $path 2$ is chosen as routing, coding opportunities will exist at node 4 and node 9, and fewer transmissions will be needed compared with $path 1$ . However, ROCX also detects coding opportunities based on the classical coding topologies of COPE.

Figure 3.

Comparison example of COPE and ROCX in route selection.

In DCAR,¹⁹ the MNCC of two flows at the intersecting node is given. Figure 4 illustrates an example of the multihop coding topology. In Figure 4, the node 4 overhear packet from node 7, which are both two hops away from the coding node, node 2. It is clear from Figure 4 that the overhearing and decoding can be multihop away from the coding node, which extends the range of coding topology and increases the number of network coding opportunities.

Figure 4.

Example of multihop coding topology in COPE.

Actually, the MNCC is valid only when the two intersecting flows are both native flows. However, when one of the intersecting flows is coded flow, the MNCC may be not valid anymore in a certain scenario. Guo et al.²⁰ found the invalid problem of MNCC in a certain scenario and presented some improved strategies as shown in Figure 5.

Figure 5.

Example of undecodable problem of multihop network coding condition in DCAR and improvement strategies. (a) Undecodable problem example of MNCC in DCAR. (b) Insert node A before node 6. (c) Insert node B after node 9. (d) Establish the wireless link between node 2 and node 9.

In Figure 5(a), there are three flows, $flow 1$ , $flow 2$ , and $flow 3$ . $flow 1$ and $flow 3$ intersect at node 5, whereas $flow 2$ and $flow 3$ intersect at node 6. According to MNCC, there exists coding opportunity at node 5 for $flow 1$ and $flow 3$ , and $flow 2$ and $flow 3$ can be coded at node 6. However, once $flow 1$ and $flow 3$ are coded at node 5, the $flow 3$ becomes a coded flow and MNCC is not valid in fact. Then if $flow 2$ and $flow 3$ are coded at node 6, the destination of $flow 2$ will eventually get the undecodable packet $P 1 \oplus P 2$ , instead of intended native packet $P 2$ . And improving strategies are given in Figure 5(b)–(d). In Figure 5(b), assume node A is between node 5 and node 6, and overhears $P 1$ from node 2. A can retrieve the native packet $P 3$ through decoding, and node 10 can get $P 2$ finally. In Figure 5(c), if node B is inserted between node 9 and node 10, and node B can overhear $P 1 \oplus P 3$ from node 5, then node B can obtain the native packet $P 2$ through decoding. In Figure 5(d), assume node 9 can overhear packet $P 1$ from node 2, then node 10 can obtain $P 2$ in final through decoding at node 9 and node 10, respectively.

Based on the improving strategies of MNCC, the general network coding condition (GNCC)²⁰ was proposed. However, one item of the GNCC requires that the packet that participates in network coding should be native packet, which is too strict. On the other hand, GNCC considers the scenarios of two native flows or one coded flow with one native flow.²¹ In an actual network, the scenario of two code flows may also appear. In addition, the GNCC only presented general guiding method, instead of formal and specific rules to detect coding opportunity as MNCC.

The interference and network coding are also jointly considered.^21,22 However, in the research of Peng et al.²¹ the network coding opportunity is detected based on the classical coding topologies as COPE, whereas the network coding condition is even not investigated by Hou et al.²² The improved general network coding condition (IGNCC) and the drawbacks of GNCC were proposed.²³ However, the IGNCC requires the overhead packets must be native packets, which is a great limitation to overhearing. In addition, IGNCC includes up to five rules to identify the network coding opportunity, which is complicated to realize in a real network. The necessary, but not sufficient network coding condition is presented.²⁴ Although the coding condition is simple and easy to realize,²⁴ the not sufficient network coding condition may also result in the failure decoding problem, which degrades the gain of network coding.

The increasing of network coding opportunities is an important goal of existing network coding aware routings. However, network coding opportunity only means that network coding may happen, but cannot guarantee the inevitable occurrence of each network coding. Actually, the traffic transmission scheduling directly influences the actual occurrence of network coding. Take the scenario in Figure 1(b) as an example. If the packets of $flow 1$ and $flow 2$ are not queued, and node 2 sends out the received packets immediately, then network coding will never happen at node 2, although there indeed exists coding opportunity for $flow 1$ and $flow 2$ at node 2. The reason is that node 2 can only receive packet from one node, node 1 or node 3, at any time, due to the open nature of wireless channel. And it is impossible for node 2 to have packets from both $flow 1$ and $flow 2$ at the same time, which is prerequisite for the occurrence of network coding. Therefore, the scheduling of packets transmission is critical to the occurrence of network coding in network coding aware routings, which directly affects the network coding gain.

Figure 1(b) demonstrates the extreme situation where node 2 cannot queue received packets. In fact, even in the situation that the packets can be queued, the occurrence of network coding is still influenced by the transmission scheduling and arrival order of packets. Some researchers had realized the importance of packets transmission scheduling to the network coding aware routings. Zhao and Medard²⁵ analyzed queue changing and packets transmission of the cross-coding topology in COPE. The virtual queue for each flow is designed at coding node to improve the performance of COPE. However, the packets transmission scheduling²⁵ is round-robin manner, which neglects the different arrival time of packets that can be coded together. The Markov model and optimized algorithms are exploited to analyze and optimize the network coding scheduling.^26–29 However, these four references^26–29 only investigate the scheduling in classical coding topologies (e.g. chain topology or cross topology) with infinite length queue at each node, which is too ideal to exist in a real wireless multihop network. In addition, the computing cost of the optimized algorithms^26–29 used may greatly increase in wireless multihop network.

Shao et al.³⁰ proposed the traffic shaping based–transmission scheduling mechanism to increase the number of occurrence of network coding in WSN. But the network coding condition is not considered. The queue length–based transmission scheduling mechanism is presented for the network coding aware routing.³¹ Before the packets transmission, the network jitter training phase is run first to search the optimal threshold of queue length control policy. However, the network is dynamic, which lead to the fluctuation of the optimal threshold. And the threshold³¹ is fixed.

Design of CTNR

CNCC

In network coding aware routings, network coding condition defines the method to detect network coding opportunities. Therefore, network coding condition determines the capability of network coding aware routing to exploit network coding, which is crucial to network coding aware routings.

Actually, the network coding condition should meet the following requirements: (1) The destination of each flow that involves network coding can get the intended native packet. (2) The method defined by network coding condition should be operable and include specific calculation. In this section, the existing network coding conditions are analyzed first, then the CNCC is presented and proved.

Before delving into the analysis of existing network coding conditions, the notations of related terms are defined first. For a node $v$ , the neighbors set of $v$ is expressed by $N (v)$ . For any node $v \in N (v)$ , there is a wireless link between $v$ and $v'$ . If a flow $f$ traverses through node $v$ , then $v \in f$ . For a flow $f$ and a node $v \in f$ , $U (v, f)$ is the set of upstream nodes of $v$ on flow $f$ , whereas $D (v, f)$ is the set of downstream nodes of $v$ on flow $f$ . If there is a flow $f$ , which traverses through nodes A, B, C, D, and E, then $U (C, f) = A, B$ and $D (C, f) = D, E$ . The node where network coding takes place is coding node, whereas the node where coded packet is decoded is called decoding node.

Lemma 1

One hop network coding condition (ONCC)

The sufficient and necessary network coding condition is that, each next hop of the coded packets can decode the encoded packet and obtain the intended native packet.

The Lemma 1 is proposed in COPE.¹⁷ It is obvious from Lemma 1 that the next hop of the coding node is just the decoding node, which limits the coding topologies within one hop of the coding node as shown in Figure 2. Besides, the ONCC puts emphasis on the decodable of the coded packets at the next hop of coding node and does not give the detailed computing method to detect coding opportunities. In fact, in COPE, the network coding opportunities are detected through comparing the flows topology with the classical coding topologies.

Lemma 2

MNCC

Assume two flows, $f_{1}$ and $f_{2}$ , intersect at node $v$ , and the channel condition and scheduling are ideal, then the sufficient and necessary network coding condition for $f_{1}$ and $f_{2}$ at node $v$ is as follows:

$\exists d_{1} \in D (v, f_{1})$ , such that $d_{1} \in N (s_{2})$ , $s_{2} \in U (v, f_{2})$ , or $d_{1} \in U (c, f_{2})$ .

$\exists d_{2} \in D (v, f_{2})$ , such that $d_{2} \in N (s_{1})$ , $s_{1} \in U (v, f_{1})$ , or $d_{2} \in U (c, f_{1})$ .

The Lemma 2 is presented in DCAR.¹⁸ As illustrated in Figure 5, MNCC holds when both $f_{1}$ and $f_{2}$ are native flows. However, when $f_{1}$ or $f_{2}$ is coded flow, the MNCC may not hold anymore and probably result in the undecodable problem of coding packets.

Lemma 3

GNCC

For a potential coding node, the GNCC is that

There exist upstream decode-capable nodes, that can extract the intended native packet for the node on the considered flow.

There exist downstream acquisition nodes, which can overhear enough packets (either native or encoded) to decode, on other flows associated with the encoding function at this node.

The Lemma 3 is presented²⁰ based on the analysis of Figure 5. However, the item (1) of the GNCC is not essential. The analysis in Figure 5 considers one native flow and one coded flow, but the scenario with two coded flows are not investigated. In addition, Lemma 3 presents the principles of network coding condition instead of specific calculating method with operability.

To address the problems of existing network coding conditions, the CNCC is presented in this article. Before giving the definition of CNCC, the scenario with two coded flows is analyzed first. Figure 6 demonstrates the different result of example scenario with two coded flows. In Figure 6, there are four flows and 22 nodes. $flow 1$ and $flow 2$ intersect at node 7, whereas $flow 3$ and $flow 4$ intersect at node 13. At this time all the 4 flows are native flows. According to MNCC, $flow 1$ and $flow 2$ can be coded at node 7, whereas $flow 3$ and $flow 4$ can be coded at node 13. Then $flow 2$ and $flow 3$ both become coded flows, and they intersect at node 15.

Figure 6.

Examples of two intersecting coded flows. (a) Unsuccessful decoding. (b) Correct decoding through overhearing coded packers. (c) Correct decoding through multiple overhearing and decoding. (d) Correct decoding with decoding to get native packets for the next encoding.

As shown in Figure 6(a), it appears that $flow 2$ can be coded with $flow 3$ at node 15 according to MNCC. However, if $flow 2$ and $flow 3$ are coded at node 15, neither $flow 2$ nor $flow 3$ can eventually get intended native packet, which is also called false decoding effect. Actually, $flow 2$ and $flow 3$ are coded flows and MNCC no longer holds.

In Figure 6(b), $flow 2$ overhears coded packet $P 3 \oplus P 4$ from node 14 at node 9, and $flow 3$ overhears coded packet $P 1 \oplus P 2$ from node 8 at node 16. If the $flow 2$ is coded at node 15 with $flow 3$ , then all the four destinations of the four flows can get intended native packets. It is obvious from Figure 6(b) that the overheard packets by $flow 2$ and $flow 3$ are just the packets involving the coding at node 15.

In Figure 6(c), the destinations of the four flows can obtain native packets, respectively. It is interesting to observe that $flow 2$ get the native packet $P 2$ eventually at node 11 after multiple decoding. After $flow 2$ is coded with $flow 3$ at node 15, the coded packets $P 1 \oplus P 2 \oplus P 3 \oplus P 4$ is sent to node 9. At the intermediate nodes, node 9, node 10, and node 11, $P 1 \oplus P 2 \oplus P 3 \oplus P 4$ is decoded one time at each node. And finally, node 11 gets the native packet $P 2$ .

In Figure 6(d), $flow 2$ is coded with $flow 1$ at node 7. And $flow 2$ is decoded at node 8 just one hop after node 7. Besides, $flow 3$ is also decoded at node 14 just after the coding at node 13. Therefore, when $flow 2$ and $flow 3$ intersect at node 15, the packets from $flow 2$ and $flow 3$ are both native packets. And finally, both $flow 2$ and $flow 3$ can get intended native packets.

Based on the above analysis of the example scenario in Figure 6, the design of CNCC should consider the following aspects:

The overhearing node is just the decoding node. As depicted in Figure 6, each overhearing node decoded the coded packets using the overheard packet.

The overhearing through wireless channel should be beneficial to decoding, no matter whether the overheard packet is native packet or coded packet. Take the scenario in Figure 6(b), for example, the node 9 overhears the coded packet $P 3 \oplus P 4$ from node 14, and node 10 overhears native packet $P 1$ from node 1. Both $P 3 \oplus P 4$ and $P 1$ are helpful to the decoding for getting the native packet $P 2$ .

Since CNCC considers the coding problem of coded flows, the decoding needs multiple decoding and multiple overhearing. As shown in Figure 6(c), the $flow 2$ experiences three decoding operations before obtaining the native packet $P 2$ at node 11.

Although decoding takes places at overhearing node, the decoding after coding can make the subsequent coding clearer and easier to decoding, when there are multiple decoding options. As illustrated in Figure 6(d), if $flow 2$ is not decoded at node 8, $P 3 \oplus P 4$ will participate in the coding at node 15. Then $flow 3$ need to consider eliminate $P 1$ from the coded packet after the coding at node 15.

Before delving into the definition of CNCC, related terms are presented first. Assume one node $v \in N (u)$ , then the packet sent by node $u$ can be overheard by node $v$ . The node $v$ is called overhearing node, whereas the node $u$ is called overheard node. And the packet overheard by node $v$ form node $u$ is expressed as $H (u)$ . In a special situation, the node $v$ is just the node $u$ , that is, $u = v$ , although the overhearing no longer exists, the packet from $u$ is still expressed as $H (u)$ . In addition, the XOR operation of $m$ overheard packets is denoted by $X_{i = 1}^{m} H (u_{i})$ , and there is $X_{i = 1}^{m} H (u_{i}) = H (u_{1}) \oplus H (u_{2}) \dots \oplus H (u_{m})$ . Assume the coded packet $P_{c}$ is the XOR operation result of $n$ native packet, that is, $P_{c} = X_{i = 1}^{n} p_{i}$ , then the symbol $SN (P_{c})$ is the set of native packets that generate $P_{c}$ through coding, that is, $S N (P_{c}) = {p_{i} | P_{c} = X_{i = 1}^{n} p_{i}}$ . In addition, the symbol $| SN (P_{c}) |$ is the number of elements in $SN (P_{c})$ . Assume there is one node $v$ on flow $f$ and the node $v$ sends packet $P$ of flow $f$ . If $| SN (P) | < | SN (P_{c}) |$ and $SN (P) \subset SN (P_{c})$ , then node $v$ is the decoding related node of $P_{c}$ , and the flow $f$ is called the decoding related flow of $P_{c}$ . The set of decoding related nodes of $P_{c}$ is expressed as $DRS (P_{c})$ .

Theorem 1

CNCC for 2 flows (CNCC-2)

Assume two flows, $f_{1}$ and $f_{2}$ intersect at node $v$ . The original native packets at sources of $f_{1}$ and $f_{2}$ are $P_{1}$ and $P_{2}$ , respectively. Before the node $v$ , $f_{1}$ and $f_{2}$ may have been coded or not. Assume the XOR operation result of packets from $f_{1}$ and $f_{2}$ at node $v$ is $P_{c}$ . The sufficient and necessary condition for $f_{1}$ and $f_{2}$ to carry on network coding at node $v$ and successful decoding for each flow is as follows:

1. $\exists d_{1 i} \in D (v, f_{1})$ , such that $d_{1 i} \in N (u_{2 i})$ , $u_{2 i} \in DRS (P_{c})$ , or $d_{1 i} \in U (v, f_{2})$ , $u_{2 i} \in DRS (P_{c})$ , $i = 1, \dots, m$ , and $P_{c} \oplus X_{i = 1}^{m} H (u_{2 i}) = P_{1}$ .

2. $\exists d_{2 j} \in D (v, f_{2})$ , such that $d_{2 j} \in N (u_{1 j})$ , $u_{1 j} \in DRS (P_{c})$ , or $d_{2 j} \in U (v, f_{1})$ , $u_{1 j} \in DRS (P_{c})$ , $j = 1, \dots, n$ , and $P_{c} \oplus X_{i = 1}^{m} H (u_{1 j}) = P_{2}$ .

Proof

The sufficiency proof of CNCC-2 and the necessity proof of CNCC-2 are investigated, respectively.

Proof of sufficiency

Assume the item (1) and (2) of CNCC are satisfied. Besides, the coding result of $f_{1}$ and $f_{2}$ at node $v$ is $P_{c}$ . According to item (1), each $d_{i}$ is just the overhearing node and decoding node for $f_{1}$ . At node $d_{11}$ , the overheard packet from $u_{21}$ is $H (u_{21})$ , and the following decoding operation is performed, and the decoding result is $D C_{11} (P_{c})$

D C_{11} (P_{c}) = P_{c} \oplus H (u_{21})

(1)

At node $d_{12}$ , the overheard packet from $u_{22}$ is $H (u_{22})$ , and the following decoding operation is performed, and the decoding result is $D C_{2} (P_{c})$

D C_{12} (P_{c}) = D C_{11} (P_{c}) \oplus H (u_{22})

(2)

The operations at $d_{1 i}$ $(2 < i < m - 1)$ is similar with that at node $d_{12}$ . At the node $d_{1 (m - 1)}$ , the decoding result is $D C_{(m - 1)} (P_{c})$

D C_{1 (m - 1)} (P_{c}) = D C_{1 (m - 2)} (P_{c}) \oplus H (u_{2 (m - 1)})

(3)

Finally, at the node $d_{1 m}$ , the decoding result is $D C_{m} (P_{c})$

D C_{1 m} (P_{c}) = D C_{1 (m - 1)} (P_{c}) \oplus H (u_{2 m})

(4)

Replace the $D C_{(m - 1)} (P_{c})$ in equation (4) with the definition of $D C_{(m - 1)} (P_{c})$ in equation (3) and so on, the equation (4) eventually can be expressed as follows

D C_{1 m} (P_{c}) = P_{c} \oplus X_{i = 1}^{m} H (u_{2 i})

(5)

According to the item (1) of CNCC, there is $P_{c} \oplus X_{i = 1}^{m} H (u_{2 i}) = P_{1}$ , so $D C_{1 m} (P_{c}) = P_{1}$ , which means that $f_{1}$ can get the native packet $P_{1}$ at node $d_{1 m}$ . Similarly, we can get $D C_{2 m} (P_{c}) = P_{2}$ , which means that $f_{2}$ can get the native packet $P_{2}$ at node $d_{2 n}$ . Therefore, both $f_{1}$ and $f_{2}$ can get intended native packets respectively, that is, both $f_{1}$ and $f_{2}$ can decode to get native packets successfully. So, the $f_{1}$ and $f_{2}$ can be coded at node $v$ . The sufficiency of CNCC-2 is proved.

Proof of necessity

Assume $f_{1}$ and $f_{2}$ can be coded at node $v$ . Obviously, $f_{1}$ and $f_{2}$ can get the native packet through decoding at overhearing nodes after node $v$ . As analyzed in Figure 6, multiple decoding may be needed to get the native packet. For flow $f_{1}$ , assume $m$ decoding operations are needed after coding at node $v$ , that is, there will be $m$ overhearing nodes in the $D (v, f_{1})$ . For any overhearing node $d_{1 i}$ $(1 < i < m)$ , it overhears the packet that is beneficial to decoding, that is, the overheard packet should be from the decoding related node of $P_{c}$ . Therefore, there exist node $u_{2 i}$ , which is the neighbor of $d_{1 i}$ , and $u_{2 i} \in DRS (P_{c})$ . In special situation, the $u_{2 i}$ is just the node $d_{1 i}$ , that is, $d_{1 i} = u_{2 i} \in U (v, f_{2})$ . Through the wireless channel, the node $d_{1 i}$ can overhear the packet $H (u_{2 i})$ for decoding. At any decoding node $d_{1 i}$ $(1 < i < m)$ , the received packet is XORed with the overheard packet $H (u_{2 i})$ . And finally, at node $d_{1 m}$ , the XOR result of decoding is $P_{c} \oplus X_{i = 1}^{m} H (u_{2 i})$ . Since $d_{1 m}$ is the last decoding node, $d_{1 m}$ should be able to get the native packet $P_{1}$ , that is, $P_{c} \oplus X_{i = 1}^{m} H (u_{2 i}) = P_{1}$ . And the item (1) holds. Similarly, the item (2) holds as well. And the necessity of CNCC-2 is proved.

Based on the proof of sufficiency and necessity, the Theorem 1 is proved. The scenarios in Figure 6 are used to show the application of CNCC-2. In Figure 6(b), $flow 2$ and $flow 3$ intersect at node 15, $P_{c}$ is $P 1 \oplus P 2 \oplus P 3 \oplus P 4$ . According to CNCC, there are (1) $9 \in D (15, flow 2)$ , $9 \in N (14)$ , $14 \in DRS (P_{c})$ , $H (14) = P 3 \oplus P 4$ ; $10 \in D (15, flow 2)$ , $10 \in N (1)$ , $1 \in DRS (P_{c})$ , $H (1) = P 1$ ; $Pc \oplus H (14) \oplus H (1) = P 2$ ; (2) $16 \in D (15, flow 3)$ , $16 \in N (8)$ , $8 \in DRS (P_{c})$ , $H (8) = P 1 \oplus P 2$ ; $17 \in D (15, f l o w 3)$ , $17 \in N (18)$ , $18 \in DRS (P_{c})$ , $H (18) = P 4$ ; $P_{c} \oplus H (8) \oplus H (18) = P 3$ . $flow 2$ and $flow 3$ in Figure 6(b) satisfy the (1) and (2) of the CNCC-2. Therefore, $flow 2$ and $flow 3$ can be coded at node 15 according to CNCC-2, and the result in Figure 6(b) confirms it.

In Figure 6(b), $flow 2$ and $flow 3$ intersect at node 15, $P_{c}$ is $P 1 \oplus P 2 \oplus P 3 \oplus P 4$ . According to CNCC, there are (1) $9 \in D (15, flow 2)$ , $9 \in N (2)$ , $2 \in DRS (P_{c})$ , $H (2) = P 1$ ; $10 \in D (15, flow 2)$ , $10 \in N (21)$ , $21 \in DRS (P_{c})$ , $H (21) = P 4$ ; $11 \in D (15, flow 2)$ , $11 \in N (12)$ , $12 \in DRS (P_{c})$ , $H (12) = P 3$ ; $Pc \oplus H (2) \oplus H (21) \oplus H (12) = P 2$ and (2) $16 \in D (15, flow 3)$ , $16 \in N (8)$ , $8 \in DRS (P_{c})$ , $H (8) = P 1 \oplus P 2$ ; $17 \in D (15, flow 3)$ , $17 \in N (18)$ , $18 \in DRS (P_{c})$ , $H (18) = P 4$ ; $Pc \oplus H (8) \oplus H (18) = P 3$ . $flow 2$ and $flow 3$ in Figure 6(b) satisfy the (1) and (2) of the CNCC-2. Therefore, $flow 2$ and $flow 3$ can be coded at node 15 according to CNCC-2. And Figure 6(b) confirms that $flow 2$ and $flow 3$ indeed can be coded and both flows can get native packets finally.

Theorem 2

CNCC for multiple flows (CNCC-M)

Assume $M$ flows, $f_{1}, f_{2}, \dots, f_{M}$ , intersect at node $v$ . The original native packets at sources of the $M$ flows are $P_{1}, P_{2}, \dots, P_{M}$ , respectively. Besides, the packets of the $M$ flows arriving at node $v$ are $P'_{1}'$ , $P_{2}'$ , ⋯, $P'_{M}$ respectively. Before the node $v$ , the $M$ flows, $f_{1}$ , $f_{2}$ , ⋯, $f_{M}$ , may have been coded or not. Assume the XOR operation result of packets from the $M$ flows, $f_{1}$ , $f_{2}$ , ⋯, $f_{M}$ , at node $v$ is $P_{c} = {P^{'}}_{1} \oplus {P^{'}}_{2} \oplus \dots \oplus {P^{'}}_{M} = X_{i = 1}^{m} {P^{'}}_{i}$ . The sufficient and necessary condition for the $M$ flows, $f_{1}$ , $f_{2}$ , ⋯, $f_{M}$ , to carry on network coding at node $v$ and successful decoding for each flow is that any two flows of the $M$ flows, $f_{i}$ and $f_{j}$ $(i \neq j)$ , satisfy CNCC-2.

Proof

The sufficiency proof and the necessity proof of CNCC-M are investigated, respectively.

Proof of sufficiency

Assume any two flows of the $M$ flows, $f_{i}$ and $f_{j}$ $(i \neq j)$ , satisfy CNCC-2. According to CNCC-2, flow $f_{i}$ can eventually get its native packet $P_{i}$ through ${P'}_{i} \oplus {P'}_{j} \oplus X_{k = 1}^{m_{i j}} H (u_{j k})$ . To simplify the equation, the symbol $X_{k = 1}^{m_{i j}} H (u_{j k})$ for $f_{i}$ and $f_{j}$ is replaced by $K_{ij}$ .

When $M = 2$ , the CNCC-M becomes CNCC-2, which has just been proved. When $M = 3$ , there is $P_{c} = P_{1}' \oplus P_{2}' \oplus P_{3}'$ . Since $f_{1}$ and $f_{2}$ satisfy CNCC-2, then according to CNCC-2 there are

P_{1} = P'_{1} \oplus P'_{2} \oplus K_{12}

(6)

P_{2} = P'_{1} \oplus P'_{2} \oplus K_{21}

(7)

Similarly, for $f_{1}$ and $f_{3}$ , there are

P_{1} = P'_{1} \oplus P'_{3} \oplus K_{13}

(8)

P_{3} = P'_{1} \oplus P_{3}' \oplus K_{31}

(9)

And for $f_{2}$ and $f_{3}$ , there are

P_{2} = P'_{2} \oplus P'_{3} \oplus K_{23}

(10)

P_{3} = P_{2'} \oplus P_{3'} \oplus K_{32}

(11)

Perform XOR operation on the left and right sides of the equations (6), (9), and (10), then there is

\begin{matrix} P_{1} \oplus P_{2} \oplus P_{3} = P_{1}' \oplus P_{1}' \oplus P_{2}' \oplus P_{2}' \oplus P_{3}' \oplus P_{3}' \oplus \\ K_{12} \oplus K_{31} \oplus K_{23} = K_{12} \oplus K_{31} \oplus K_{23} \end{matrix}

(12)

Perform XOR operation on the left and right sides of the equations (6) and (7), then there is

\begin{matrix} P_{1} \oplus P_{2} = {P'}_{1} \oplus {P'}_{1} \oplus P_{2}' \oplus P_{2}' \oplus K_{12} \oplus K_{21} \\ = K_{12} \oplus K_{21} \end{matrix}

(13)

Perform XOR operation on the left and right sides of the equations (12) and (13), then there is

P_{3} = K_{23} \oplus K_{31} \oplus K_{21}

(14)

Similarly, there are

P_{2} = K_{12} \oplus K_{23} \oplus K_{13}

(15)

P_{1} = K_{31} \oplus K_{12} \oplus K_{32}

(16)

Based on the result of equations (14)–(16), the three flows can get the intended native packets through decoding.

When $M = 4$ , there is $P_{c} = P_{1}' \oplus P_{2}' \oplus P_{3}' \oplus P_{4}'$ . Since $f_{1}$ and $f_{4}$ satisfy CNCC-2, then according to CNCC-2 there are

P_{1} = P_{1}' \oplus P'_{4} \oplus K_{14}

(17)

P_{4} = P'_{1} \oplus P'_{4} \oplus K_{41}

(18)

According to equation (6) and $P_{c} = P_{1}' \oplus P_{2}' \oplus P_{3}' \oplus P_{4}'$ , there is

P_{c} = P_{1}' \oplus P_{2}' \oplus P_{3}' \oplus P_{4}' = K_{12} \oplus P_{1} \oplus P_{3}' \oplus P_{4}'

(19)

According to equation (8), the equation (19) can be expressed as

P_{c} = K_{12} \oplus K_{13} \oplus P_{1}' \oplus P_{4'}

(20)

According to equation (17), the equation (20) can be expressed as

P_{c} = K_{12} \oplus K_{13} \oplus K_{14} \oplus P_{1}

(21)

Therefore, there are $P_{1} = P_{c} \oplus K_{12} \oplus K_{13} \oplus K_{14}$ . Similarly, there are $P_{2} = P_{c} \oplus K_{21} \oplus K_{23} \oplus K_{24}$ , $P_{3} = P_{c} \oplus K_{31} \oplus K_{32} \oplus K_{34}$ , and $P_{4} = P_{c} \oplus K_{41} \oplus K_{42} \oplus K_{43}$ .

Similarly, when $M = 5$ , there are $P_{1} \oplus P_{2} \oplus P_{3} \oplus P_{4} \oplus P_{5} = K_{12} \oplus K_{23} \oplus K_{34} \oplus K_{45} \oplus K_{51}$ , $P_{1} = K_{12} \oplus K_{32} \oplus K_{34} \oplus K_{54} \oplus K_{51}$ , $P_{2} = K_{12} \oplus K_{23} \oplus K_{43} \oplus K_{45} \oplus K_{15}$ , $P_{3} = K_{21} \oplus K_{23} \oplus K_{34} \oplus K_{54} \oplus K_{51}$ , $P_{4} = K_{12} \oplus K_{32} \oplus K_{34} \oplus K_{45} \oplus K_{15}$ , and $P_{5} = K_{21} \oplus K_{23} \oplus K_{43} \oplus K_{45} \oplus K_{51}$ .

Similarly, when $M = 6$ , there are $P_{1} = P_{c} \oplus K_{12} \oplus K_{13} \oplus K_{14} \oplus K_{15} \oplus K_{16}$ , $P_{2} = P_{c} \oplus K_{21} \oplus K_{23} \oplus K_{24} \oplus K_{25} \oplus K_{26}$ , $P_{3} = P_{c} \oplus K_{31} \oplus K_{32} \oplus K_{34} \oplus K_{35} \oplus K_{36}$ , $P_{4} = P_{c} \oplus K_{41} \oplus K_{42} \oplus K_{43} \oplus K_{45} \oplus K_{46}$ , $P_{5} = P_{c} \oplus K_{51} \oplus K_{52} \oplus K_{53} \oplus K_{54} \oplus K_{56}$ , and $P_{6} = P_{c} \oplus K_{61} \oplus K_{62} \oplus K_{63} \oplus K_{64} \oplus K_{65}$ .

Based on the above rules, when $M = 2 k + 1$ , there is $X_{i = 1}^{2 k + 1} P_{i} = X_{i = 1}^{2 k + 1} K_{i ((i + 1) % (2 k + 1))}$ . Then, each native packet can be obtained as the equations (14)–(16). When $M = 2 k$ , there is $P_{i} = X_{j = 1, j \neq i}^{2 k} K_{i j}$ .

Based on the above analysis, when any two flows of the $M$ flows satisfy the CNCC-2, the $M$ flows can be coded together, and each flow can obtain the native packets successfully through decoding. Therefore, the sufficiency of CNCC-M is proved.

Proof of necessity

Assume the $M$ flows can be coded at node $v$ and the coded packet is $P_{c} = X_{i = 1}^{M} {P'}_{i}$ , where the $P_{i}'$ is the packet arriving at node $v$ of flow $f_{i}$ . Then for any two flows of the $M$ flows, $f_{i}$ and $f_{j}$ , they both can obtain the intended native packets $P_{i}$ and $P_{j}$ through decoding. Assume $K_{i}$ and $K_{j}$ are the decoding parameters for $f_{i}$ and $f_{j}$ to obtain native packets $P_{i}$ and $P_{j}$ , respectively. The decoding operations can be expressed as follows

P_{i} = P_{c} \oplus K_{i}

(22)

P_{j} = P_{c} \oplus K_{j}

(23)

Although the $P_{c}$ as mentioned above is the XOR result of the $M$ arriving packets of the $M$ flows, the $P_{c}$ must contain $P_{i}'$ and $P_{j}'$ , and $P_{c}$ can be expressed as follows

P_{c} = P_{i}' \oplus P_{j}' \oplus P_{eij}

(24)

where $P_{eij}$ is the XOR result of packets that form the $P_{c}$ excluding $P_{i}'$ and $P_{j}'$ .

Assume $K_{id}$ is the XOR result of the decoding related packets of $P_{i}' \oplus P_{j}'$ and $K_{ind}$ is the XOR result of the not decoding related packets of $P_{i}' \oplus P_{j}'$ . Then the equation (22) can be expressed as

\begin{matrix} P_{i} = P_{i}' \oplus P_{j}' \oplus P_{eij} \oplus K_{id} \oplus K_{ind} \\ = P_{i}' \oplus P_{j}' \oplus K_{id} \oplus (P_{eij} \oplus K_{ind}) \end{matrix}

(25)

Similarly, assume $K_{jd}$ is the XOR result of the decoding related packets of $P_{i}' \oplus P_{j}'$ , and $K_{jnd}$ is the XOR result of the not decoding related packets of $P_{i}' \oplus P_{j}'$ . Then the equation (23) can be expressed as

\begin{matrix} P_{i} = P_{i}' \oplus P_{j}' \oplus P_{eij} \oplus K_{jd} \oplus K_{jnd} \\ = P_{i}' \oplus P_{j}' \oplus K_{jd} \oplus (P_{eij} \oplus K_{jnd}) \end{matrix}

(26)

Consider the $P_{eij}$ and $K_{ind}$ in equation (25). Since $P_{eij}$ is the XOR result of the packets generating $P_{c}$ excluding $P_{i}'$ and $P_{j}'$ , $P_{eij}$ is not related with $P_{i}'$ and $P_{j}'$ . In addition, $K_{ind}$ is the XOR result of the not decoding related packets of $P_{i}' \oplus P_{j}'$ , so the result of $(P_{eij} \oplus K_{ind})$ should be all zero. Otherwise, the result of equation (25) will include the packet except $P_{i'}$ and $P_{j'}$ . Besides, assume $P_{i}' \oplus P_{j}' = P_{cij}$ . Then the equation (25) is expressed as follows

P_{i} = P_{i}' \oplus P_{j}' \oplus K_{id} = P_{cij} \oplus K_{id}

(27)

Similarly, $P_{eij} \oplus K_{jnd}$ should also be all zero. And the equation (26) can be expressed as follows

P_{i} = P_{i}' \oplus P_{j}' \oplus K_{jd} = P_{cij} \oplus K_{jd}

(28)

Consider the equation (27), since the aim of $K_{id}$ is to recover $P_{i}$ from $P_{cij}$ , decoding will take place at downstream nodes, which overhear the decoding-related packets from neighbors. So, the $K_{id}$ can be expressed as $K_{i d} = X_{k = 1}^{m} H (u_{j k})$ , that is $\exists d_{ik} \in D (v, f_{i})$ , such that $d_{ik} \in N (u_{jk})$ , $u_{jk} \in DRS (P_{cij})$ , or $d_{ik} \in U (v, f_{j})$ , $u_{jk} \in DRS (P_{cij})$ , $k = 1, \dots, m$ , and there is

P_{c i j} \oplus X_{k = 1}^{m} H (u_{j k}) = P_{i}

(29)

where $u_{jk}$ is the node send decoding related packet of $P_{cij}$ .

Similarly, $K_{jd}$ can be expressed as $K_{j d} = X_{k = 1}^{n} H (u_{i k})$ , that is, $\exists d_{jk} \in D (v, f_{j})$ , such that $d_{jk} \in N (u_{ik})$ , $u_{ik} \in DRS (P_{cij})$ , or $d_{jk} \in U (v, f_{i})$ , $u_{ik} \in DRS (P_{cij})$ , $k = 1, \dots, n$ , and there is

P_{c i j} \oplus X_{k = 1}^{n} H (u_{i k}) = P_{j}

(30)

According to equations (29) and (30), $f_{i}$ and $f_{j}$ meet the requirement of the CNCC-2. In addition, since $f_{i}$ and $f_{j}$ are randomly selected from the $M$ flows, any two flows of the $M$ flows satisfy the CNCC-2 when the $M$ flows can be coded at $v$ and can be successfully decoded eventually. The necessity of CNCC-M is proved.

Based on the sufficiency and necessity proof of CNCC-M, the CNCC-M is proved.

Theorem 3

Assume $M$ flows intersect at node $v$ and satisfy the CNCC-M, then any $N$ $(N \leq M)$ flows of the $M$ flows also satisfy CNCC-M.

Proof

If the $M$ flows satisfy the CNCC-M, then any two flows of the $M$ flows satisfy the CNCC-2 according to the CNCC-M. Since the $N$ flows belong to the $M$ flows, any two flows of the $N$ flows, $f_{i}$ and $f_{j}$ , both belongs to the $M$ flows. Therefore, $f_{i}$ and $f_{j}$ satisfy the CNCC-2. Since any two flows of the $N$ flows satisfy CNCC-2, any $N$ flows of the $M$ flows also satisfy CNCC-M. Theorem 3 is proved.

Assume $M$ flows satisfy the CNCC-M at node $v$ , and the $M$ flows are coded together generating coded packet $P_{c}$ , then the coding degree of the $P_{c}$ is $M$ , the coding is called full coding, and the $P_{c}$ is a full coded packet. According to theorem 3, any $N$ $(N \leq M)$ flows of the $M$ flows also satisfy CNCC-M, the $N$ flows can also be coded at node $v$ . If only $N$ flows are coded at $v$ and the coded packet $P_{c'}$ is generated, then the coding degree of the $P_{c'}$ is $N$ , the coding is called nonfull coding, and the $P_{c'}$ is nonfull coded packet.

Load balancing and coding aware routing metric

In network coding aware routings, routing metric is used to evaluate the discovered paths. Therefore, routing metric is a critical aspect of network coding aware routings. The routing metric of CTNR should consider the following aspects:

Network coding benefit. Network coding reduces the number of transmissions, consumes less network resource, and improves network throughput. In addition, higher coding degree also brings better benefit. Therefore, the number of coding opportunities on paths and the coding degree at each coding nodes should be reflected in the design of the routing metric.

Network load. It is interesting from the analysis in “CNCC” section that network coding usually takes place at intersecting nodes. For new arriving flow, it needs to intersect with existing flows to create more coding opportunities, which may result in network congestion on the other hand. So, there should be a trade-off between load balancing and coding opportunities increasing.

Path quality. The discovered path consists of multiple wireless links. So, the path should avoid the wireless link with poor link quality, which easily results in packets lost and retransmission.

Considering the above factors, the coding and load aware routing metric (CLRM) is designed in this article.

Consider the wireless link $l_{ij}$ on the discovered path $P$ , which is the link between node $i$ and node $j$ . The quality of $l_{ij}$ can be evaluated through the expected transmission number (ETX) to finish one successful packet delivery. The ETX value of link $l_{ij}$ is defined as follows

ETX (l_{ij}) = \frac{1}{\sum_{k = 0}^{+ \infty} P (δ (l_{ij}) > k)}

(31)

where $δ (l_{ij})$ is the number of needed transmissions for one successful delivery, and $P (δ (l_{ij}) > k)$ is the probability that $δ (l_{ij})$ is larger than $k$ .

Consider the definition of $ETX (l_{ij})$ , it reflects the link quality of $l_{ij}$ on one hand. On the other hand, $ETX (l_{ij})$ is the expected transmission number, which reflects the network resource consumption of the link $l_{ij}$ and is an important factor of network coding gain. Now consider the coding opportunity at node $i$ . If the new arriving flow along the path $P$ can be coded at node $i$ with other $(k - 1)$ existing flows that traverse through node $i$ , then the packets of the $k$ flows can be coded into one coded packet and send out, and the resource consumption for the new arriving flow is $1 / k$ . Assume the $CodeSe t_{i}$ is the result returned by the coding opportunity discovery procedure, which indicates the set of flows that can be coded with the flow along $P$ at node $i$ . $| CodeSe t_{i} |$ is the number of flows involving network coding, that is, the coding degree at node $i$ .

To increase network coding opportunities, the new arriving flows in network coding aware routings tends to intersect with existing flows, which easily results in the traffic concentrating in part of the network and network congestion. Therefore, the node with heavy load should also be avoided in CLRM. To balance the network load, the load degree (LD) is designed to reflect the LD of the node. For link $l_{ij}$ , the LD value of node $i$ is denoted by symbol $LD (i)$ and is defined as follows

LD (i) = \max {1.0, \frac{(1.0 - α)}{(1.0 - que_pe r_{i})}}

(32)

where $que_pe r_{i}$ is the queue occupancy percentage of node $i$ , and $α$ is the threshold value for the queue occupancy percentage. It is clear from the equation (32) that when $que_pe r_{i}$ is below $α$ , the $LD (i)$ is always 1. However, once the $que_pe r_{i}$ is over $α$ , the value of $LD (i)$ increases sharply.

Then, the CLRM value of link $l_{ij}$ is defined as follows

CLRM (l_{ij}) = ETX (l_{ij}) \times \frac{1}{| CodeSe t_{i} |} \times LD (i)

(33)

And for the discovered path $P$ , its CLRM value is the sum of each link’s CLRM value and is shown as follows

CLRM (P) = \sum_{l_{ij} \in P}^{P} CLRM (l_{ij})

(34)

It is clear from the equations (33) and (34) that the higher coding degree and the lower ETX and LD values mean the lower CLRM value of $P$ and the better path quality. In summary, the design of CLRM owns the following characteristics: (1) CLRM considers the coding opportunity, LD, and link quality. (2) CLRM prefers the path with lower CLRM value. (3) CLRM prefers the path with more coding opportunities, higher coding degree, lower load, and better link quality. (4) The CLRM value of the path $P$ can be obtained through distributed manner.

TMM

The coding opportunity discovered according to CNCC means the potential network coding at one node, which cannot guarantee the occurrence of network coding due to the different arrival time of flows as discussed in “Related works and motivations” section. To improve the occurrence of network coding, the TMM is proposed.

In existing network coding aware routings, the packet is queued and sent out as first-in-first-out (FIFO) manner. However, the multiple packets from multiple flows in the queue may be coded into one coded packet. The transmission scheduling should be coding set oriented instead of packet oriented. The coding set is the result of coding opportunity discovery procedure, which indicates the set of flows that can be coded together. On the other hand, the FIFO queue cannot clearly demonstrate the arrival of packets of different flows. In CTNR, at intermediate node $i$ , each flow corresponds to one virtual queue to reflect the packets’ arrival of each flow.

In TMM, the arrived packets are mapped to the virtual queues of the corresponding flows. The coding set–oriented flows grouping algorithm (CFGA) is used to group the flows at node $i$ according to the CNCC. The details of the CFGA is illustrated in Figure 7. It is interesting from Figure 7 that only CNCC-2 is used in CFGA and CNCC-M does not appear in CFGA. Actually, the definition of CNCC-M is based on the definition of CNCC-2 as shown in theorem 2. The aim of using CNCC-2 in Figure 7 is to realize the CNCC-M. The result of CFGA are marked as $F G_{1}$ , $F G_{2}$ , $F G_{3}$ , ⋯, $F G_{M}$ . The flows belong to the same group, also called coding set, can be coded together. The packets of the flows in the same coding set are given to coding gate, which generates the coded packet. If the elements number of one coding set is 1, then there is only one flow in the coding set with one input into the coding gate, and the corresponding coding gate outputs the native packet of the flow.

Figure 7.

Coding set–oriented flows grouping algorithm.

Since the coding packets of coding sets are objects of transmission scheduling, each coding set is assigned the scheduling priority using the maximum virtual queue occupation ratio of the flow in one coding set. The details of the virtual queue occupation ratio based priority computation algorithm (VRPA) is given in Figure 8.

Figure 8.

Virtual queue occupation ratio based priority computation algorithm.

Besides, the coding set–oriented transmission scheduling algorithm (CTSA) determines the transmitting order of the packets from the coding gates based on VRPA and generates the gate control list to control the open/close of the coding gates. Assume the virtual queue head packets set of each coding set are $H S_{1}$ , $H S_{2}$ , $H S_{3}$ , ⋯, $H S_{M}$ . The detailed information of CTSA is shown in Figure 9.

Figure 9.

Coding set–oriented transmission scheduling algorithm.

Detailed routing discovery procedure of CTNR

When there is a data transmission task from source node $S$ to destination node $D$ , and there is no routing entry from $S$ to $D$ in the routing table of node $S$ , then node $S$ initiates the routing discovery procedure. In CTNR, four phases are needed to discover the routing from $S$ to $D$ .

1. Route request

The node $S$ generates the Route REQuest (RREQ) message and broadcasts it. Each neighbor that receives RREQ will record its ID into RREQ and broadcast it again. Finally, the RREQ reach node $D$ .

2. Route reply

When the destination receives RREQ message, it generates the corresponding Route REPly (RREP) message according to the information collected by RREQ. The RREQ will be transmitted to node $S$ along the opposite path discovered by RREP. At each intermediate node on the path, the information of flows and neighbors will be stored in the RREP.

3. Coding opportunity discovery

When the node $S$ receives RREP, it will generate the corresponding Coding Opportunities DIscovery (CODI) message. The CODI message will traverse through the path discovered by RREQ. Each intermediate node on the path will execute the coding opportunity discovery algorithm (CODA) as shown in Figure 10 to determine whether there is coding opportunity at the intermediate node, and if so, which flows can be code with the new arrival flow. CODI will eventually reach the destination node $D$ .

4. Route confirm

When the node $D$ received the first CODI message, and set up a time TOUT. Within the time of TOUT, the CLRM values of all the paths in the CODI messages that reach $D$ will be computed. The path with the least CLRM value is chosen as the final routing from $S$ to $D$ . Then node $D$ generates the Route CONfirm (RCON) message based on the information of the corresponding CODI message. Once the node $S$ receives the RCON message, it creates the routing entry from $S$ to $D$ according to the path information in RCON and begins to transmit packets.

Figure 10.

Coding opportunity discovery algorithm.

Simulations and performance analysis

Simulation parameters

To evaluate the performance of the proposed CTNR, extensive simulations are conducted using the NS-2 platform. The aims of the simulations are as follows: (1) verifying the correctness of the CNCC compared with existing network coding conditions, (2) evaluating the effectiveness of the TMM in increasing the occurrence of network coding, (3) quantifying the benefit of the CLRM under CNCC and TMM.

In the simulations, two scenarios are considered: (1) grid network with $6 \times 6$ nodes within a $1000 m \times 1000 m$ area, (2) random network with 36 nodes randomly deployed in a $1000 m \times 1000 m$ area. The grid network scenario and random network scenario are considered in many other classical network coding based routings, for example, COPE, DCAR, and so on. The grid network scenario is used to investigate the performance of CTNR in the network with well-distributed nodes, while the random network scenario is used to analyze the performance of CTNR in the network with random distributed nodes. In addition, COPE,¹⁷ DCAR,¹⁹ FORM,²⁰ BLJCR,³¹ and CTNR-no TMM are also simulated to compare the performance of CTNR. The CTNR-no TMM means that the TMM is not exploited to analyze the influence of TMM to CTNR. In real wireless multihop network, the source and destination of one communication are usually random. Therefore, the source destination pairs in the simulations are selected randomly from the nodes in the network. The other simulation parameters are shown in Table 1.

Table 1.

Simulation parameters.

Parameters	Value
MAC layer protocol	IEEE 802.11
Transport layer protocol	UDP
Traffic type	CBR
Rate of each CBR flow	100 Kbps
Nodes’ working mode	Promiscuous
Signal transmission range	250 m
Signal interference range	550 m
Channel capacity	2 Mbps
Packet size	512 byte
$QThreshold$	0.9
$α$	0.9
Number of nodes	36
Simulation area	$1000 m \times 1000 m$
Simulation time	1000 s

Performance analysis

Grid network

Figure 11 depicts the network throughput under different number of flows in the grid network. It is obvious from Figure 11 that the six routings are close and increase gradually when the number of flows is below 20. When the number of flows grows, CTNR has a gradually increasing superiority over other routings. The gaps among the six routings become larger when the number of flows is over 20. One interesting point is that when the number of flows is over 34, the throughput of COPE, DCAR, FORM, and BLJCR begins to decrease gradually, whereas CTNR and CTNR-TMM can still increase slowly.

Figure 11.

Network throughput under different number of flows in the grid network.

The reason is that COPE and BLJCR passively detect coding opportunities in discovered routings and exploit less network coding compared with other routings, which results in earlier network congestion and decreasing of throughput. Although DCAR and FORM improve the network coding condition, the decodable of coding packets cannot be guaranteed. Especially, the MNCC in DCAR is no longer valid for two coded flows, which results in packets retransmission and degrade of network throughput, even lower than BLJCR.

For CTNR, it exploits most network coding through CNCC and TMM. More network coding means more resource saving and network can accommodate more traffic, which postpone network congestion. On the other hand, the CLRM let the routings avoid the nodes with heavy load and balance network traffic. Therefore, CTNR outperforms other routings in network throughput. Since CTNR-no TMM cannot use TMM to create more network coding, the network throughput of CTNR-no TMM is lower than that of CTNR.

The average end-to-end delay under different number of flows in grid network is plotted in Figure 12. It can be seen from Figure 12 that the average end-to-end delay of the six routings rises gradually when the number of the flows is ascending. When the number of flows is below 12, CTNR has the largest delay and COPE has the least delay. When the number of flows is over 24, COPE has the largest delay and CTNR has the lowest delay.

Figure 12.

Average end-to-end delay under different number of flows in the grid network.

The reason for the phenomenon is that when the number of flows below 12, CTNR improves the occurrence through TMM, which delays potential packets for coding and results in the highest average end-to-end delay of CTNR compared with other routings. And CTNR-no TMM is lower than that of CTNR when the number of flows is below 12, since there is no TMM and packets delay for coding. Because COPE does not consider the coding opportunity in routing selection, the average end-to-end delay of COPE is smallest when the number of flows is small.

With the growth of the number of flows, the network tends to be congested, COPE, BLJCR, DCAR, and FORM increases rapidly and COPE becomes the largest one with the number of flows over 20. Compare with other routings, the CTNR can increase network coding through CNCC and TMM. In addition, nodes’ load is considered in CLRM, which can balance the network traffic and postpone the network congestion. Without TSN, the CTNR-no TSN can exploit less network coding and lead to slightly higher end-to-end delay when the number of flows is over 24.

The coded packets ratio is computed as the number of coded packets divided by the number of total packets. And the coded packets ratio reflects the ability of routings to exploit network coding. Figure 13 illustrates the coded packets ratio under different number of flows in the grid network. It is clear from Figure 13 that the coded packets ratio of the six routings increases with the growth of the number of flows. And the advantage of CTNR becomes obvious with the increasing of the number of flows. The coded packets ratio of CTNR is 5.1% larger than that of CTNR-TMM and 7.7% larger than that of FORM when there are 20 flows. When the number of flows increases to 40, the gaps in the coded packets ratio become 11.7% and 20.6%, respectively.

Figure 13.

Coded packets ratio under different number of flows in the grid network.

The reason is that more flows intersect each other and more coding opportunities will be discovered when the number of flows increases. Since BLJCR passively detects coding opportunities in discovered routings as COPE, the coded packet ratio of COPE and BLJCR are significantly lower than other routings. The MNCC in DCAR is only valid for two intersecting native flows, while FORM did not consider the coded opportunities of two coded flows. So DCAR and FORM are both lower than CTNR-no TMM and CTNR. Although CTNR-no TMM and CTNR both detect coding opportunities based on CNCC, the TMM in CTNR improves the occurrence of network coding. Therefore, the CTNR-no TMM is lower than CTNR especially with a higher number of flows.

However, not all coded packets can be decoded successfully due to the wireless loss or drawback of coding condition. The decoded packets ratio under different number of flows in the grid network is presented in Figure 14. The decoded packets ratio is computed as the number of decoded packets divided by the number of coded packets. It is interesting from Figure 14 that the decoded packets ratio of COPE, BLJCR, CTNR-no TMM, and CTNR is close and decreases slowly with the growth of the number of flows, whereas that of DCAR and FORM decreases rapidly with the growth of the number of flows.

Figure 14.

Decoded packets ratio under different number of flows in the grid network.

The reason behind the phenomenon is that the drawback of MNCC in DCAR and GNCC in FORM results in the fake coding opportunities, which lead to the packets undecodable problem of the coded packets. For COPE and BLJCR, although coded packets ratios are lower than other routings, the decoded packets ratio of COPE and BLJCR is close and larger than that of DCAR and FORM, because the coding opportunities in COPE and BLJCR can guarantee the successful decoding at the next hop of the coding node, according to the ONCC. Despite no TMM in CTNR-no TMM, both CTNR-no TMM and CTNR detect coding opportunities according to CNCC, which solves the fake coding opportunity problem and can guarantee the correctness of coding opportunity. However, the decoded packets ratio of COPE, BLJCR, CTNR-no TMM, and CTNR decrease slowly due to the wireless loss with the increase of the number of flows.

In the simulation of CTNR, the network coding opportunities at each node are determined according to CNCC. It is important and interesting to further distinguish which coding opportunity is based on CNCC-2, which coding opportunity is based on CNCC-M, and even which coding opportunity can be determined based on MNCC without CNCC. To investigate the contribution of the different coding condition in discovering coding opportunities of CTNR, the coding condition ratio is shown in Figure 15.

Figure 15.

Coding condition ratio of CTNR under different number of flows in the grid network.

It is obvious from Figure 15 that MNCC is larger than CNCC-2 and CNCC-M when the number of flows is small. However, MNCC decreases sharply with the growth of the number of flows. Contrary to MNCC, CNCC-2 grows rapidly with the number of flows between 6 and 22, and when the number of flows is over 22 the growth of CNCC is slow. Despite CNCC-M grows when the number of flows is over 8, the CNCC-M is always below 15. The phenomenon in Figure 15 indicates that when the number of flows is small, MNCC makes the largest contribution to the coding opportunity. When the number of flows is large, the majority coding opportunities are discovered based on CNCC-2. The reason is that when the number of flows is small, the majority of the flows are native flows at intersecting node and coding opportunities can be determined using MNCC. However, upon increasing the number of flows, many flows may intersect with other flows at multiple intermediate nodes. Then the flows may become coded flows at intermediate node, and only CNCC can be used to determine coding opportunities. However, compared with CNCC-2, CNCC-M involves more flows and need more strict requirements, which makes the coding opportunities based on CNCC-M is much smaller than that based on CNCC-2.

Random network

Figure 16 illustrates the network throughput under different number of flows in the random network. It is clear from Figure 16 that the gaps between CTNR and other routings become larger when the number of flows is over 24. The network throughput of COPE, DCAR, FORM, and BLJCR begin to decrease, whereas CTNR-no TMM and CTNR continue to increase slowly, when the number of flows is over 32. The reason is that CTNR detects coding opportunities using CNCC, which avoid the fake coding opportunities. In addition, the TMM increases the occurrence of network coding. Therefore, CTNR exploits more network coding and outperforms the other routings especially with higher number of flows, which is also the case in Figure 11.

Figure 16.

Network throughput under different number of flows in the random network.

Compared with Figure 11, it can be found from Figure 16 that the changing trend of the six routings is similar to that in Figure 11, but lower than that in Figure 11. The reason is that the nodes in the grid network are distributed evenly, whereas the nodes in the random network are placed randomly, which leads to higher node density. Since the node density is higher in random network, the wireless channel contention is more intense, which degrades the network throughput.

Figure 17 shows the average end-to-end delay under different number of flows in the random network. It can be found from Figure 17 that CTNR has a higher start point compared with other routings. Then the average end-to-end delay of CTNR rises gradually when the number of flows ascends. Then CTNR is lower than other routings when the number of flows is greater than 20. The reason behind the phenomenon is that the TMM of CTNR requires the early arrival packets to wait for the later packets to increase the occurrence of network coding, which increases the delay of packets, when the number of flows is low. However, network congestion occurs with the growth of number of flows, which leads to the sharp increase of average end-to-end delay in COPE, DCAR, FORM, and BLJCR. Since CTNR exploits more network coding, the congestion in the network using CTNR is postponed and the increase of average end-to-end delay of CTNR-no TMM and CTNR is slower than other routings.

Figure 17.

Average end-to-end delay under different number of flows in the random network.

Compared with Figure 12, it is obvious from Figure 17 that the two scenarios are close when the number of flows is low. However, the average end-to-end delay of the six routings in random network is higher than that in Figure 12. This because that the higher node density in random network leads to harder wireless medium occupation and prolongs the delay of the packets.

Figure 18 depicts the coded packets ratio under different number of flows in the random network. It is evident from Figure 18 that the coded packets ratio of the six routings ascends with the growth of the number of flows. And the gaps among the six routings become larger when the number of flows is over 16. Besides, CTNR-no TMM and CTNR outperform other routings and CTNR is larger than CTNR-no TMM especially with larger number of flows. This because that CTNR-no TMM and CTNR detect coding opportunities based on CNCC, which avoids fake coding opportunity and increases the number of coding. In addition, CTNR increases the occurrence of network coding through TMM, which further rise the coded packet ratio compared with CTNR-no TMM.

Figure 18.

Coded packets ratio under different number of flows in the random network.

Compared with Figure 13, the changing trend of the six routings is similar to that in Figure 13, and coding packets ratio of the six routings is slightly higher than that in Figure 13. The reason is that the higher node density in random network realizes more neighborhood relationship than that in grid network, which actually generates more coding opportunities in random network. The coded packets ratio reflects the number of coding opportunities in the network to some extent.

Figure 19 graphs the decoded packets ratio under different number of flows in the random network. It is clear from Figure 19 that the decoded packets ratio of COPE, BLJCR, CTNR-no TMM, and CTNR is stable and decreases slowly with the increase of the number of flows, whereas DCAR and FORM descend faster with the growth of the number of flows. The reason is that COPE and BLJCR require the decoding at the next hop of the coding node. CTNR-no TMM and CTNR discover coding opportunities based on CNCC, which has been proven to be necessary and sufficient. The slight descent of COPE, BLJCR, CTNR-no TMM, and CTNR is due to the wireless loss and network congestion when the network load is heavy. The MNCC of DCAR and GNCC of FORM cannot guarantee the correctness under the circumstance with two or more coded flows. Therefore, DCAR and FORM descend greatly with the growth of the number of flows. Compared with Figure 14, it is clear that the changing trend and the values in Figure 19 is close to that in Figure 14. The results in Figures 14 and 19 confirm that CTNR can improve the decoding of coded packets in both grid and random networks.

Figure 19.

Decoded packets ratio under different number of flows in the random network.

Figure 20 illustrates the coding condition ratio of CTNR under different number of flows in the random network. It is clear from Figure 20 that the MNCC is higher than CNCC-2 and CNCC-M, when the number of flows is below 14. However, MNCC decreases sharply, CNCC-2 grows fast and CNCC-M increases slowly, with the growth of the number of flows. And CNCC-2 is higher than MNCC and CNCC-M. The reason is that when the number of flows is below 14, the majority flows are native flows and coding opportunity can be judged using MNCC. The number of native flows decreases and the number of coded flows ascends as the number of flows rises. Then the coding opportunities must be detected based on CNCC and CNCC-2 outperforms CNCC-M and MNCC. Because the requirements of CNCC-2 is less than that of CNCC-M, the coding opportunities based on CNCC-2 is far larger than that of CNCC-M.

Figure 20.

Coding condition ratio of CTNR under different number of flows in the random network.

Compared with Figure 15, the trend of MNCC, CNCC-2, and CNCC-M in Figure 20 is the same as that in Figure 15. However, MNCC in Figure 20 begins to decrease when the number of flows is 4. In addition, CNCC-2 in Figure 20 starts to rise when the number of flows is 4. In Figure 15, the MNCC is 100%, whereas CNCC-2 and CNCC-M are both 0 when the number of flows is 4. The reason is that in the random network with higher node density, the flows more likely intersect with each other and more likely become coded flows with the growth of number of flows. Therefore, CNCC-2 in Figure 20 has an earlier increase compared with that in Figure 15.

Conclusion

The network coding conditions of existing network coding aware routings may lead to the undecodable problem of coded packets. In addition, the packets transmission scheduling is not considered in existing network coding aware routings which results in the loss of network coding occurrence. In this article, the CTNR is presented for wireless multihop network. The CNCC is given for detecting coding opportunities to avoid failed decoding problem, whereas the TMM is proposed to increase the occurrence of actual network coding. In addition, the CLRM is designed which jointly considers the network coding gain and node load. Comprehensive simulations on NS2 confirm that CTNR increases the network coding opportunities, rises the network coding occurrence, and improve the network throughput. The future work includes the implementation of CTNR on real wireless multihop network.

Footnotes

Acknowledgements

The authors wish to thank anonymous reviewers for their valuable comments and suggestions for the improvement of this article.

Handling Editor: Jinsong Wu

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was funded by National Natural Science Foundation of China, grant number 61502411 and 61871412, Natural Science Foundation of Jiangsu Province, grant number BK20150432 and BK20151299, Natural Science Research Project for Universities of Jiangsu Province, grant number 15KJB520034, China Postdoctoral Science Foundation, grant number 2015M581843, Jiangsu Provincial Qinglan Project, Jiangsu Provincial Government Scholarship for Overseas Studies, Teacher Overseas Training Program of Yancheng Institute of Technology, “2311” Talent Project of Yancheng Institute of Technology, Talents Project of Yancheng Institute of Technology, grant number KJC2014038, Project of Jiangsu Provincial Collaborative Innovation Center of Ecological Building Materials and Environmental Protection Equipment, grant number GX2015206.

ORCID iD

Xing Shao

References

Khanna

Chaturvedi

SK.

A comprehensive survey on multi-hop wireless networks: milestones, changing trends and concomitant challenges. Wirel Pers Commun 2018; 101(2): 677–722.

Pathak

Dutta

A survey of network design problems and joint design approaches in wireless mesh networks. IEEE Commun Surv Tut 2011; 13(3): 396–428.

Yick

Mukherjee

Ghosal

Wireless sensor network survey. Comput Netw 2008; 52(12): 2292–2330.

Boukerche

Turgut

Aydin

et al . Routing protocols in ad hoc networks: a survey. Comput Netw 2011; 55(13): 3032–3080.

Al-Sultan

Al-Doori

Al-Bayatti

et al . A comprehensive survey on vehicular ad hoc network. J Netw Comput Appl 2014; 37(1): 380–392.

Alotaibi

Mukherjee

A survey on routing algorithms for wireless ad-hoc and mesh networks. Comput Netw 2012; 56(2): 940–965.

Rehan

Fischer

Rehan

A critical review of surveys emphasizing on routing in wireless sensor networks—an anatomization under general survey design framework. Sensors 2017; 17(8): 1–37.

Sharef

Alsaqour

Ismail

Vehicular communication ad hoc routing protocols: a survey. J Netw Comput Appl 2014; 40(4): 363–396.

Ahlswede

Cai

SYR

et al . Network information flow. IEEE Trans Inform Theory 2000; 46(4): 1204–1216.

10.

SYR

Yeung

Cai

Linear network coding. IEEE Trans Inform Theory 2003; 49(2): 371–381.

11.

Farooqi

Tabassum

Rehmani

et al . A survey on network coding: from traditional wireless networks to emerging cognitive radio networks. J Netw Comput Appl 2014; 46(11): 166–181.

12.

Fragouli

Katabi

Markopoulou

et al . Wireless network coding: opportunities and challenges. In: Proceedings of the military communications conference, Orlando, FL, 29–31 October 2007, pp.29–31. New York: IEEE.

13.

Iqbal

Dai

Huang

et al . Survey of network coding-aware routing protocols in wireless networks. J Netw Comput Appl 2011; 34(6): 1956–1970.

14.

Xie

Chong

PHJ

IWH

et al . A survey of inter-flow network coding in wireless mesh networks with unicast traffic. Comput Netw 2015; 91(11): 738–751.

15.

Kafaie

Chen

Dobre

et al . Joint inter-flow network coding and opportunistic routing in multi-hop wireless mesh networks: a comprehensive survey. IEEE Commun Surv Tut 2018; 20(2): 1014–1035.

16.

Zhang

Chen

Marsic

MAC-layer proactive mixing for network coding in multi-hop wireless networks. Comput Netw 2010; 54(2): 196–207.

17.

Katti

Rahul

et al . XORs in the air: practical wireless network coding. IEEE/ACM Trans Netw 2008; 16(3): 497–510.

18.

Santhapuri

Zhong

et al . XORs in the air: practical wireless network coding. In: Proceedings of the workshop on wireless mesh networks, Reston, VA, 25–28 September 2006, pp.157–159. New York: IEEE.

19.

Lui

JCS

Chiu

DM.

DCAR: distributed coding-aware routing in wireless networks. IEEE Trans Mob Comput 2010; 9(4): 596–608.

20.

Guo

Zhou

et al . Analysis of general network coding conditions and design of a free-ride-oriented routing metric. IEEE Trans Veh Technol 2011; 60(4): 1714–1727.

21.

Peng

Wang

et al . A new coding- and interference-aware routing protocol in wireless mesh networks. Comput Electr Eng 2013; 39(6): 1822–1836.

22.

Hou

Lui

et al . Coding- and interference-aware routing protocol in wireless networks. Comput Commun 2013; 36(17): 1745–1753.

23.

Kok

Chow

Ishii

Improving network coding in wireless ad hoc networks. Ad Hoc Netw 2015; 33(10): 16–34.

24.

Chen

Yuan

et al . Distributed greedy coding-aware deterministic routing for multi-flow in wireless networks. Comput Netw 2016; 105(8): 194–206.

25.

Zhao

Medard

On analyzing and improving COPE performance. In: Proceedings of the information theory and applications workshop, San Diego, CA, 31 January–5 February 2010, pp.1–6. New York: IEEE.

26.

Chen

Letaief

Cao

Buffer-aware network coding for wireless networks. IEEE/ACM Trans Netw 2012; 20(5): 1389–1401.

27.

Mohapatra

Gautam

Shakkottai

et al . Network coding decisions for wireless transmissions with delay consideration. IEEE Trans Commun 2014; 62(8): 2965–2976.

28.

Hsu

Abedini

Gautam

et al . Opportunities for network coding: to wait or not to wait. IEEE/ACM Trans Netw 2015; 23(6): 1876–1889.

29.

Liu

Feng

Guo

A framework of joint scheduling and network coding for real-time traffic with diverse delay constraints. Wirel Pers Commun 2017; 97(3): 4855–4876.

30.

Shao

Wang

Zhao

et al . Traffic shaped network coding aware routing for wireless sensor networks. IEEE Access 2018; 6(11): 71767–71782.

31.

Wan

A low-jitter wireless transmission based on buffer management in coding-aware routing. Fut Internet 2015; 7(3): 307–328.

Common network coding condition and traffic matching supported network coding aware routing for wireless multihop network

Abstract

Keywords

Introduction

Related works and motivations

Design of CTNR

CNCC

Lemma 1

One hop network coding condition (ONCC)

Lemma 2

MNCC

Lemma 3

GNCC

Theorem 1

CNCC for 2 flows (CNCC-2)

Proof

Proof of sufficiency

Proof of necessity

Theorem 2

CNCC for multiple flows (CNCC-M)

Proof

Proof of sufficiency

Proof of necessity

Theorem 3

Proof

Load balancing and coding aware routing metric

TMM

Detailed routing discovery procedure of CTNR

Simulations and performance analysis

Simulation parameters

Performance analysis

Grid network

Random network

Conclusion

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

ORCID iD

References