Novel Section-Based Joint Network Coding and Scheduling Scheme in WMNs: JNCS
Novel Section-Based Joint Network Coding and Scheduling Scheme in WMNs: JNCS
ETRI Journal. 2015. Apr, 37(2): 380-386
Copyright © 2015, Electronics and Telecommunications Research Institute(ETRI)
  • Received : August 08, 2014
  • Accepted : November 21, 2014
  • Published : April 01, 2015
Export by style
Cited by
About the Authors
Jae Ryong Cha
Gwang Hun Baek

Guaranteeing quality of service over a multihop wireless network is difficult because end-to-end (ETE) delay is accumulated at each hop in a multihop flow. Recently, research has been conducted on network coding (NC) schemes as an alternative mechanism to significantly increase the utilization of valuable resources in multihop wireless networks. This paper proposes a new section-based joint NC and scheduling scheme that can reduce ETE delay and enhance resource efficiency in a multihop wireless network. Next, this paper derives the average ETE delay of the proposed scheme and simulates a TDMA network where the proposed scheme is deployed. Finally, this paper compares the performance of the proposed scheme with that of the conventional sequential scheduling scheme. From the performance analysis and simulation results, the proposed scheme gives more delay- and energy-efficient slot assignments even if the NC operation is applied, resulting in a use of fewer network resources and a reduction in ETE delay.
I. Introduction
Wireless mesh networks (WMNs) are a key technology for next-generation wireless networking. With its popularity, supporting quality of service (QoS) over multihop wireless networks is becoming an issue because end-to-end (ETE) delay is accumulated at every hop in a multihop flow. To solve the delay issues, a time division multiple access (TDMA)–based media access control (MAC) is incorporated into the 802.11 TGs MAC Enhancement Proposals standard [1] . Most TDMA scheduling schemes for WMNs have been proposed for determining the minimum frame length. However, it is reported that minimizing the number of time slots cannot guarantee that the ETE delay of a multihop flow diminishes [2] . The authors in [2] [3] have proposed the idea that time slots be sequentially allocated in a multihop flow so as to minimize ETE delay.
Recently, research has been conducted on network coding (NC) schemes as an alternative mechanism to significantly increase the utilization of valuable resources in multihop WMNs. It is known that a representative practical XOR-based NC scheme called COPE, first appearing in [4] , is very simple and effective. In the field of joint NC and scheduling (JNCS), almost all studies have focused on improving network throughput, which is the fundamental objective of NC [5] [10] . There have been no papers that describe the design of JNCS with consideration of a delay bound. This paper extends the sequential link scheduling scheme proposed in [3] to the field of JNCS schemes. More specifically, this paper proposes a sequential scheduling scheme where the aforementioned practical XOR-based NC scheme is cooperated in order that the packets are transferred to the multihop away destination with minimum delay and resource utilization is enhanced.
II. Related Works
In the literature, there have been a few studies in the field of JNCS in multihop wireless networks. The authors of [10] have proposed a new framework for NC in ad hoc wireless networks. They have extended NC to wireless packet networks under realistic assumptions such as omnidirectional transmissions, single transceiver per node, and interference effects among concurrent transmissions [10] . They have also considered a simple wireless network topology to illustrate how NC can improve throughput and energy efficiency objectives beyond routing solutions. In addition, they have extended the NC problem to general wireless networks in conjunction with a scheduling-based MAC protocol.
Second, the authors of [8] have proposed a general framework to develop optimal and adaptive JNCS schemes. They have applied this framework to propose an optimal scheduling scheme adapted to the conventional scheme called COPE. They have also designed XOR-Sym, a new NC scheme, and its associated optimal scheduling scheme. Furthermore, they have shown that designing appropriate MAC scheduling algorithms is critical for achieving the throughput gains expected from NC [8] .
Third, a study proposed by [11] has made important contributions to the field of JNCS. It attempts to analyze joint routing and NC for wireless unicast traffic. The proposed approach is an extension of the theoretical framework of [12] , which allows for broadcast transmission and optimization of routing with XOR-based NC with and without opportunistic listening [9] . This study is based on the protocol interference model and employs an approximated model to compute the broadcast rate. The limitation of this study is that it only computes bounds. Moreover, the joint NC and routing problem is formulated for a given set of predefined routing paths for each source node [9] .
Next, the authors of [7] have designed a distributed framework that facilitates choosing the best rate on each link while considering the need for overhearing and dictates the choice of which decoding recipient will acknowledge the reception of an encoded packet. Their goal is to drive the network toward achieving the best trade-off between the achievable NC gain and the inherent rate gain possible on a link. In the transmission rate and ACKer selection framework proposed by this study, transmitters adapt the bit rate taking into consideration that their packets will be overheard by neighbors, while most previous studies either assume a fixed transmission rate or do not consider the impact of using diverse variable rates on the NC gain [7] .
As mentioned before, these studies have been focused on improving the throughput efficiency in a network, which is the fundamental objective of NC. Almost all of these conventional studies have been based on TDMA. However, these schemes may suffer from a scheduling delay (also called frame delay) determined by a sequence of time slots allocated on a path although they can enhance throughput efficiency. This scheduling delay increases the ETE delay, which may result in failure to guarantee the QoS of applications [2] [3] . Therefore, we propose a novel section-based JNCS scheme, called JNCS, that not only obtains an NC gain (enhanced throughput efficiency) but also takes into consideration the aforementioned scheduling delay to minimize the ETE delay, ultimately guaranteeing the QoS of applications in TDMA-based multihop wireless networks.
III. Proposed Section-Based JNCS Scheme
In this paper, we focus on wireless mesh backbone networks. For convenience of presentation, we refer to a wireless mesh backbone network as WMN in the rest of this paper.
We model a WMN with a topological graph connecting the nodes in the wireless range of each other. The network can be represented with a directed connected graph, G ( B , E ), where B = { b 1 , ... , bm } is a set of nodes and E = { e 1 , ... , eg } is a set of directed links, and it is said that any two nodes, say u and v , are neighbors if ( u , v ) ∈ E . In the network, there is a set F of flows, and flow f (∈ F ) is specified by a node set R ( f ) ={ p 1 , ... , pq }, where pk is the k th node in a multihop flow (2 ≤ q ) ( k = 1: source node, 1 < k < q : intermediate node, and k = q : destination node).
Figure 1(a) shows a well-known X constellation for NC, which is composed of two predecessor nodes, Pa and Pb , an NC coordinator, R , and two successor nodes, Sa and Sb . The two packets from both flows have to be relayed via R . In the conventional slot scheduling, four transmissions (slots) are necessary for the successful delivery of two packets. However, if NC is employed, only three transmissions (slots) are necessary — that is, Pa R unicasting in a slot, Pb R unicasting in a slot, and R ’s broadcasting to Sb and Sa in a (common broadcasting) slot. This is because R broadcasts the encoded packet that is the XOR combination of the packets transferred from the two predecessor nodes Pa and Pb , as shown in Fig. 1(a) . NC can also be used in the case of non-opportunistic listening [13] . For more details on the baseline NC operation, refer to [4] .
PPT Slide
Lager Image
Example of NC operation: (a) X constellation and (b)–(d) NC operation for two flows.
According to the results in [1] [3] , if sequentiality is guaranteed, then the ETE delay is minimized because the slots scheduled in a multihop flow are sequentially arranged within one frame. The sequentiality means a multihop slot allocation satisfying the condition s ( ek ) < s ( e k+1 ), where s ( ek ) denotes slot indexes allocated for the link ek (1 ≤ k H ) in a multihop flow.
The proposed JNCS scheme, which is based on flow, employs a new concept, section . First of all, this paper will describe the proposed sequential scheduling scheme where the NC operation is not performed. It is assumed that all of the nodes know the highest hop value, H , in the network. This value can be obtained by dispersively exchanging some control packets [3] . In the proposed scheme, all nodes manage the equal length of the frame and the frame is divided into H sections. Next, prior to slot scheduling, every node selects an interference-free slot that it can use for communication with a neighbor node. To select the interference-free slot, we adopt the channel locking algorithm proposed by [14] , which employs the following four states: idle, request, release, and grant.
Figures 1(b) 1(d) and Fig. 2 denote an example to explain how the proposed scheme performs a slot allocation. Consider two flows (flow #1 and flow #2) that are on a 5 by 5 grid network (see Figs. 1(b) and 1(c) ). And, in Fig. 2 , the checkered slots mean the ones occupied by other flows prior to the slot allocation by flows #1 and #2. Note that the basic idea to guarantee the sequentiality in the proposed scheme is to perform the special slot allocation with the ith hop being scheduled in the i th section. It is assumed that flow #1 first schedules slots ( Fig. 2(b) ). Therefore, in this example, the link e1 is allocated in section #1. Likewise, links e 2 and e 3 are allocated in section #2 and section #3, respectively. Because this section-based slot allocation can satisfy the sequentiality condition, the ETE packet transmission is possible within one frame. On the other hand, in the proposed scheme, the sequentiality can also be satisfied even when the NC operation is performed. To describe the proposed scheme when employing the NC operation, we define an NC set as having five nodes that make up the X constellation of Fig. 1(a) . We also define x ( ei ) and x ( gj ) as the section indexes of links ei and gj , respectively. Links ei and gj are each links of the two flows related to the NC operation.
PPT Slide
Lager Image
Basic operation of the proposed scheme: (a) existing allocation, (b)–(c) allocation status without NC, and (d) allocation status with NC (slot release).
According to the result in [13] , when considering energy requirements, it is reported that fewer than 1% of coding operations are related to the combination of more than three packets. Therefore, in this paper, it is assumed that an NC coordinator performing the XOR-based NC operation manages only two flows. During the routing process, each node manages routing tables (forward and reverse tables) [15] . Based on both these tables, prior to performing the proposed scheme, each node finds an NC set where NC operation is possible. Each node finds an NC set based on the following criteria for an X constellation:
  • ■Pais beyond the communication range ofPb.
  • ■Sais beyond the communication range ofSb.
  • ■Sbmust overhear the packets transferred fromPa.
  • ■Samust overhear the packets transferred fromPb.
In Fig. 1(d) , if considering the NC set criteria for the X constellation, links e 2 and g 2 become the ones for the predecessor nodes, links e 3 and g 3 become the ones for the successor nodes, and node #12 becomes the NC coordinator R . In this case, the slots for the two predecessor nodes are allocated in the same second section, and the slots for the two successor nodes are allocated in the same third section. In this case, R determines the second slot of section #3 as the common broadcasting slot. Meanwhile, the third slot of section #3 is released for the use of other flows. By doing this, the sequentiality can be guaranteed even when using the NC operation. Because one slot per NC operation can be reduced, it can lead to better resource utilization in the network.
If considering all possible combinations of the slot allocation in an NC set for X constellation, then there exist only the four conditions shown in Fig. 3 . The first condition means that two predecessor nodes in an NC set belong to the same section. This condition is the same as the one mentioned in the above example. This condition can guarantee the sequentiality of the slots on a multihop flow because s ( ei ) and s ( gj ) always proceed s ( e i+1 ) and s ( g j+1 ), respectively.
PPT Slide
Lager Image
Four NC conditions depending on slot allocation: (a) x(ei) = x(gj), (b) x(ei) = x(gj) + 1, (c) x(ei) = x(gj) − 1, and (d) x(ei) < x(gj) −1 or x(ei) > x(gj) +1 where j≠1.
The second condition means that the section for the predecessor node of flow #1 is behind the section for the predecessor node of flow #2, where the distance between the two sections is only equal to one. Similar to the first condition, this condition can also guarantee sequentiality because s ( ei ) and s ( gj ) always precede s ( e i+1 ) and s ( g j+1 ). For the above first and second conditions, R sets the common broadcasting slot to s ( g j+1 ); that is, the left slot out of the candidates for broadcasting.
The third condition means that the section for the predecessor node of flow #1 precedes the section for the predecessor node of flow #2, where the distance between the two sections is only equal to one. In this condition, s ( e i+1 ) precedes s ( gj ). In this case, by swapping s ( e i+1 ) and s ( gj ), sequentiality can be guaranteed. However, this case needs to exchange additional control packets between R and the corresponding predecessor node. For the third condition, R sets s ( e i+1 ) as a common broadcasting slot.
Under the last condition, s ( e i+1 ) always precedes s ( gj ), where the distance between the two sections is always more than two. In this case, R has two options. One is to set s ( g j+1 ) as the common broadcasting slot, resulting in the slot sequence s ( e i−1 ), s ( ei) , s ( e i+2 ), and s ( e i+1 ). In this case, sequentiality is broken. The other is to select s ( e i+1 ) as a common broadcasting slot, resulting in the slot sequence s ( g j+1 ), s ( g j−1 ), and s ( gj ). This case also does not satisfy the sequentiality in a multihop flow. Thus, because the distance between the sections of two predecessor nodes is more than two, sequentiality cannot always be guaranteed.
Therefore, the proposed scheme cannot guarantee sequentiality only for the fourth NC condition. NC coordinator R can decide whether to perform NC operation for the fourth condition; for example, performing the fourth condition at the cost of additional delay or not performing that condition at the cost of the coding gain. The decision may be different depending on the QoS requirements of applications.
IV. Multihop Packet Delay Analysis
In this section, an ETE delay analysis of the proposed scheme is performed. The ETE delay means the time taken for each source node to transfer a packet to a destination. In the proposed scheme, one slot can be released whenever an NC operation is performed. Therefore, the ETE delay of the proposed scheme without NC operation is the upper bound of the ETE delay of the proposed scheme with NC operation. Therefore, we now derive the upper bound of the ETE delay of the proposed scheme. In the proposed scheme, all nodes allocate slots by using section and hop information. First of all, assume that the hop distance, h ( i ), of a source node, i , is evenly distributed. That is, there is an equal number of source nodes for each of the hop distances 1, 2, ... , H , where H denotes the maximum number of hops in the network. Thus, all N nodes in the network try to allocate slots in section x (1). In section x (2), ( N N / H ) nodes try to allocate slots, and in the last section, x ( H ), N / H nodes try to allocate slots. Accordingly, given L slots, the number of slots necessary in the i th section, Li , can be calculated by
L i ={ N(i1) N H j=1 H1 { N(j1) N H } L iH, L k=1 H1 N(k1) N H j=1 H { N(j1) N H } L i=H,
where ⌊*⌋ means the integer less than or equal to *. In addition, the ETE delay a packet experiences in section x ( i ) is composed of three components: the time between the start of a frame and the end of the ( i −1)th section; the time between the start of the i th section and the slot scheduled for the destination in the i th section; and the transmission time at the destination. If considering the above components, then the ETE delay a packet experiences in section x ( i ) is given by
D(i)=( j=1 i1 L j )T+ L j 2 T+T            =[ ( j=1 i1 L j )+ L j 2 +1 ]T,
where T denotes a unit slot time.
Finally, the average ETE delay can be obtained by
D ¯ = k=1 H D(k) H .
From (2), it can be seen that the average ETE delay is a function of the frame size L . Therefore, the average ETE delay of the proposed scheme is increased as the frame size is increased. However, the ETE delay is bounded by the frame size.
V. Performance Analysis Results
- 1. Simulation Scenarios
To evaluate the delay performance of the proposed section-based JNCS scheme, we have simulated a grid network with 49 nodes by using an OPNET simulator. The vertical and horizontal distances between two adjacent nodes are 100 m, and the communication range of each node is set as 200 m. Depending on the distance between nodes, there may exist various constellations besides the aforementioned X constellation. Therefore, in this paper, we have additionally considered the string and hybrid constellations, which can be formed during simulation. We assumed that there are enough slots for reservation in the frame. As the simulation proceeds, each node creates a multihop flow for a real-time application. As soon as all source nodes complete the multihop slot allocation algorithm, they generate one packet per frame before transmitting the packet in their allocated slot. As performance metrics, we consider the average ETE delay and average coding gain. The average ETE delay means the time taken for each source node to transfer a packet to a destination. And, the coding gain is defined by
coding gain = h η total N ( h η total N ) η NC ,
where h denotes the number of hops; η total denotes the total number of packets (transmissions) transferred per node; N denotes the total number of nodes in the network; and η NC denotes the number of transmissions reduced by NC.
- 2. Simulation and Analysis Results
Table 1 shows the simulation parameters and preliminary results. Figure 4 shows the ETE delay of both the conventional scheme and the proposed section-based JNCS scheme with an increase in the packet inter-arrival time, where packets arrive deterministically. The conventional scheme refers to the sequential link scheduling algorithm proposed in [2] . We applied the conventional XOR-based network coding scheme to this scheme for the performance comparison. In Fig. 4 , the solid line indicates the numerical result and the dotted lines indicate the simulation results. In Fig. 4 , SECTION-T1 and SECTION-T2 denote the average ETE delay of the proposed section-based schemes with Type 1 (T1) and Type 2 (T2), respectively. T1 is the case where the NC coordinator performs the NC operation for the fourth NC condition, and T2 is the case where the NC coordinator does not perform the NC operation for the fourth NC condition. The packet inter-arrival time is set as unit slot time × 0.001/ w , where w increases from 0.1 to 1 in steps of 0.1. If the value of w is 0.5, then each node generates one packet per every two frames. On the other hand, if the value of w is 1, then each node generates one packet per frame. Therefore, increasing the value of w is the same as increasing the packet inter-arrival rate. According to the simulation results, when there are no errors in the wireless channel, all schemes show stable performance regardless of the increase in the value of w. This is because each node generates at most one packet per frame, resulting in no primary queuing delay in the network. Primary queuing delay means the delay that occurs when the packet arrival rate in a source node is higher than the packet transmission (service) rate [3] . However, as the transmission power is decreased from 0 dBm to −2 dBm, the ETE delay is increased. Especially with a high traffic load (for example, when w ≥ 0.9), the ETE delay is sharply increased. This is because the packets experience a large delay owing to the packet retransmission caused by wireless channel errors, not by the primary queuing delay. Meanwhile, in the conventional sequential link scheduling with NC (SLS-NC) scheme, half the NC flows experience an extra delay whose value is equal to the frame length. This is because the sequentiality is broken. Therefore, the conventional SLS-NC scheme experiences the lowest delay performance.
Simulation environments and preliminary results.
Simulation environments
Communication range (m) 200
Per-node distance (m) 100
Number of nodes 49
Frame size (slots) 200
Unit slot time (ms) 1
Pathloss model Free space
Shadowing Log-normal dist. (standard deviation: 4 dB)
Preliminary results
Average number of hops, h 4.1
Maximum number of hops, H 13
Average one-hop degree 4
Average two-hop degree 10
Total number of NC points 20
# of NC points not meeting fourth NC condition 9
PPT Slide
Lager Image
Average ETE delay vs. w (packet inter-arrival rate) in deterministic packet arrival: (a) no errors, (b) 0 dBm of TX power, (c) −1 dBm of TX power, and (d) −2 dBm of TX power.
In the proposed SECTION-T2, the network loses almost as much NC gain as the number of NC points satisfying the fourth NC condition because the NC coordinator does not perform the NC operation for the fourth NC condition. However, the average ETE delay is smaller than that of the proposed SECTION-T1 because the sequentiality can be guaranteed. In the case of the proposed SECTION-T1, the NC coordinator does perform the NC operation for the fourth NC condition at the cost of extra delay. Therefore, it experiences slightly higher delay than the proposed SECTION-T2. However, it can obtain the entire NC gain at the cost of the small increase in the ETE delay. Table 2 shows the average coding gain of all the schemes used for the performance comparison. First, because the proposed SECTION-T2 does not perform the NC operation for the fourth NC condition, the average coding gain is lower than that of the other schemes. Except for the proposed SECTION-T2, all the schemes have the same coding gain because they all perform the NC operation for all NC points.
Average coding gain in simulated network.
Lists Average coding gain
Conventional SLS-NC 1.11
Proposed SECTION-T1 1.11
Proposed SECTION-T2 1.04
VI. Conclusion
In this paper, a novel section-based joint NC and Scheduling (JNCS) scheme, called JNCS, was proposed. The proposed scheme can obtain the same (or similar) NC gain as the conventional SLS-NC scheme, as well as guaranteeing sequentiality with a small overhead, thereby decreasing the ETE delay in multihop WMNs. In conclusion, by applying the conventional XOR-based NC to the sequential link scheduling, the proposed scheme gives more delay-efficient slot assignments that result in better channel utilization, while at the same time using less network resources and energy. It is expected that the proposed scheme can be applied to several systems; for example, a tactical multi-functional multi-radio device that needs multihop voice transmissions with low power, or an unmanned aerial vehicle relay system that needs multihop data and voice transmission.
Corresponding Author
Jae Ryong Cha received his BS, MS, and PhD degrees in electrical engineering from Ajou University, Suwon, Rep. of Korea, in 2004, 2006, and 2013, respectively. He has been with the Agency for Defense Development as a senior researcher since 2013. He was the recipient of the first ever Radio Frequency Identification/Ubiquitous Sensor Network paper award and IEEE Seoul Section Student Paper Award in 2005 and 2011, respectively. His research interests include issues for quality of service in multi-hop communication networks and unmanned aerial vehicle systems.
Gwang Hun Baek received his BS and MS degrees in electrical engineering from Gyungpook National University, Daegu, Rep. of Korea, in 1988 and 1990, respectively. He has been with the Agency for Defense Development as a principal researcher since 1990. He is currently pursuing his PhD degree in electrical engineering at Chungbuk National University, Cheongju, Rep. of Korea. His research interests include satellite and unmanned aerial vehicle systems.
Trung T.M. , Mo J. 2010 “A Multichannel TDMA MAC Protocol to Reduce End-to-End Delay in Wireless Mesh Networks,” ETRI J. 32 (5) 819 - 822    DOI : 10.4218/etrij.10.0210.0102
Djukic P. , Valaee S. 2009 “Delay Aware Link Scheduling for Multi-hop TDMA Wireless Networks,” IEEE/ACM Trans. Netw. 17 (3) 870 - 883    DOI : 10.1109/TNET.2008.2005219
Cha J.R. , Park H.-J. , Kim J.-H. 2012 “New Delay-Efficient TDMA-Based Distributed Schedule in Wireless Mesh Networks,” EURASIP J. Wireless Commun. Netw. 369 - 381
Katti S. 2008 “XORs in the Air: Practical Wireless Network Coding,” IEEE/ACM Trans. Netw. 16 (3) 497 - 510    DOI : 10.1109/TNET.2008.923722
Mogre P.S. “Core: Centrally Optimized Routing Extensions for the IEEE 802.16 MeSH Mode,” IEEE Conf. Local Comput. Netw. Montreal, Canada Oct 14–17, 2008 58 - 65
Wang N. , Ansari N. “Identifying the Network Coding Opportunity,” IEEE Sarnoff Symp. Princeton, NJ, USA Apr. 12–14, 2010 1 - 5
Kim T.-S. “A Framework for Joint Network Coding and Transmission Rate Control in Wireless Networks,” IEEE INFOCOM San Diego, CA, USA Mar. 14–19, 2010 1 - 9
Chaporkar P. , Proutiere A. 2007 “Adaptive Network Coding and Scheduling for Maximizing Throughput in Wireless Networks,” Int. Conf. Mobile Comput. Netw. New York, NY, USA 135 - 146
Shabdanov S. , Rosenberg C. , Mitran P. “Joint Routing, Scheduling, and Network Coding for Wireless Multihop Networks,” Int. Symp. WiOpt Princeton, NJ, USA May 9–13, 2011 33 - 40
Sagduyu Y.E. , Ephremides A. “Joint Scheduling and Wireless Network Coding,” WiOpt Riva Del Garda, Italy Apr. 3–7, 2005
Sengupta S. , Rayanchu S. , Banerjee S. “An Analysis of Wireless Network Coding for Unicast Sessions: The Case for Coding-Aware Routing,” IEEE INFOCOM Anchorage, AK, USA May 6–12, 2007 1028 - 1036
Jain K. 2005 “Impact of Interference on Multi-hop Wireless Network Performance,” Wireless Netw. 11 (4) 471 - 487    DOI : 10.1007/s11276-005-1769-9
Cui T. , Chen L. , Ho T. “Energy Efficient Opportunistic Network Coding for Wireless Networks,” IEEE INFOCOM Phoenix, AZ, USA Apr. 13–18, 2008 361 - 365
Rhee I. 2009 “DRAND: Distributed Randomized TDMA Scheduling for Wireless Ad Hoc Networks,” IEEE Trans. Mobile Comput. 8 (10) 1384 - 1396    DOI : 10.1109/TMC.2009.59
2006 IEEE 802.11s. Draft Amendment: ESS Mesh Networks