# The Exploration of Network Coding in IEEE 802.15.4 Networks

Authors: Deze Zeng; Song Guo; Victor Leung; Jiankun Hu
Journal: International Journal of Digital Multimedia Broadcasting
 (2011)

---

## Abstract

Wireless personal area networks (WPANs) are getting popular in a variety of fields such as smart home, office automation, and e-healthcare. In WPANs, most devices are considerably energy constrained, so the
communication protocol should be energy efficient. The IEEE 802.15.4 is designed as a standard protocol for low power, low data rate, low complexity, and short range connections in WPANs. The standard supports allocating several numbers of collision-free guarantee time slots (GTSs) within a superframe for some time-critical transmissions. Recently, COPE was proposed as a promising network coding architecture to essentially improve the throughput of wireless networks. In this paper, we exploit the network coding technique at coordinators to improve energy efficiency of the WPAN. Some related practical issues, such as GTS allocation and multicast, are also discussed in order to exploit the network coding opportunities efficiently. Since the coding opportunities are mostly exploited, our proposal achieves both higher energy efficiency and throughput performance than the original IEEE 802.15.4.


---

## Body

## 1. Introduction

Wireless sensor network (WSN) is a kind of network consisting of a collective of sensor nodes systematically connected by wireless radio. A sensor node may be equipped with one or several different sensors with different sensing abilities, for example, temperature sensing, light sensing, and pressure sensing. WSNs show great potential to and have been widely deployed for many applications involving monitoring, tracking, and controlling, such as home automation, environment monitoring, industrial and agricultural monitoring and controlling, and wild animal tracking. Yet there are still many challenge issues hindering the further development of WSNs. This is because most sensor nodes are constrained by their low processing capability, low memory spaces, and limited power supply. In addition, wireless sensor nodes are usually attached with radio transceiver with short-range communication capabilities. The transceiver is one of the most energy consumable parts. Hence, one key issue to tackle the challenge is to design a suite of communication protocols in a low complexity and enabling low-power connections between sensor nodes in WSN.Wireless personal area network (WPAN) is a kind of WSN, which has also been widely deployed in various automation systems, such as home/office automation systems and e-healthcare systems. WPANs have also drawn a lot of attention from both academia and industry. The IEEE 802.15.4 is a standard formed by the WPAN working group, which specifies the physical layer and medium access control (MAC) layer protocols for low-rate WPANs (LR-WPANs). Above IEEE 802.15.4, an association of industrial companies formed ZigBee Alliance [1] and published ZigBee standard which specifies a suite of high level communication protocols, for example, network layer protocol and security specifications, targeting simpler and less expensive solutions for LR-WPANs.The IEEE 802.15.4 physical layer specifies the possible operation frequency bands as well as the modulation techniques. Recently, the work group is planning to expand the available frequency bands. Depending on whether a beacon frame is used or not, the IEEE 802.15.4 MAC layer specification defines two transmission modes, non-beacon-enabled and beacon-enabled mode. In the non-beacon-enabled mode, it simply makes use of unslotted carrier sense multiple access with collision avoidance (CSMA/CA) to control the medium access distributively. While in the beacon-enabled mode, besides the contention-based slotted CSMA/CA access control in the contention access period (CAP), the protocol also defines contention free period (CFP) for devices that require dedicated bandwidth or low-latency transmission. The IEEE 802.15.4 also defines two kinds of devices probably used in the LR-WPANs, the full function device (FFD) with all the IEEE 802.15.4 functions and features specified by the standard and the reduced function device (RFD) with only limited functionality to lower cost and complexity. A FFD can take the role as the PAN coordinator while a RFD can only talk to the FFD.The IEEE 802.15.4 network can be built as star topology (Figure1(a)), peer-to-peer topology (Figure 1(b)), and cluster tree (Figure 1(c)). In each topology, at least one FFD is required to serve as the coordinator of the network. In the star topology, all communications, including the transmissions between the devices, must go through the coordinator. Although in peer-to-peer topology the devices can communicate directly with each other, the coordinator is still required. In this paper, we mainly consider the LR-WPANs in home areas where star topology is widely adopted because of its simplicity and effectiveness. A star topology consists of one coordinator and several devices, as shown in Figure 1(a). The coordinator is responsible for management of an LR-WPAN, such as association/disassociation of the devices and medium access coordination of the devices in the LR-WPAN. It also relays packets for the devices who need to talk with each other since they cannot communicate directly according to the IEEE 802.15.4 specification.Various topologies in IEEE 802.15.4 networks.
(a)
Star topology(b)
Peer-to-Peer topology(c)
Cluster tree topologyThe special scenario exhibits a good network coding opportunity. Network coding [2, 3] is an emerging technique that has been proposed as a promising method to improve the throughput via encoding the packets at the intermediate routers/relays. In particular, by exploring the broadcast nature of wireless communication medium, COPE [3] has been proved by a practical implementation in IEEE 802.11 network as an efficient network coding architecture that can substantially increase the throughput of wireless networks.While, in IEEE 802.15.4 networks, the coordinator can also exploit network coding for the traffic between devices other than simply relaying them directly, the way should be in a lower complexity with lower energy consumption as lower power is an important requirement of LR-WPAN compared to IEEE 802.11 WLAN. Therefore, several issues such as how to apply network coding in LR-WPANs and how the network coding performs in LR-WPANs still need to be studied. We first consider the communication pattern in LR-WPANs and try to discover the network coding opportunities. Then, some practical issues, such as GTS allocation and multicast, are also considered in order to exploit the network coding opportunities efficiently. Simulation studies provide a deep insight to how the network coding performs in LR-WPANs. Our experimental results indicate that network coding provides a good alternative to improve the performance of wireless networks in terms of both throughput and energy consumption.The rest of this paper is organized as follows. The background and related work are presented in Section2. Section 3 describes how to integrate network coding into IEEE 802.15.4 protocols in detail. Section 4 presents the experimental results. Section 5 concludes the paper.


## 2. Background and Related Work

In this section, we first briefly introduce the IEEE 802.15.4 beacon-enabled transmission as the background of this paper. Then we show some related research results in the literatures.


### 2.1. Overview of the IEEE 802.15.4 Beacon-Enabled Transmission

In beacon-enabled mode, the channel time is divided into superframes bounded by the beacon frames transmitted from the coordinator, as shown in Figure2. The time between two consecutive beacon frames is defined as the beacon interval (BI). BI is further divided into two periods, active period and inactive period. All the transmissions happen in and only in the active period, while, in the inactive period, all the devices in the network go into a low-power mode or sleep mode for energy saving. The active period is also referred to as superframe duration (SD). The inactive period is optional according to the requirement of the applications.Figure 2
The superframe structure defined in IEEE 802.15.4.By default, the nodes compete for medium access using slotted CSMA/CA within the contention access period (CAP) during SD. The IEEE 802.15.4 protocol also offers the possibility of having a contention-free period (CFP) within the SD. The CFP is optionally activated upon request from a node. It consists of several numbers of guaranteed time slots (GTSs). The device, which needs dedicated bandwidth to transmit to or receive from the coordinator, can transmit a GTS request command to the coordinator. Upon reception of this request, the coordinator checks whether there are sufficient resources and, if possible, allocates the requested GTSs such that the device can communicate with the coordinator in the reserved GTS in a collision-free way. There are up to seven GTSs that can be allocated provided that there are sufficient capacity available. If the available resources are not sufficient, the GTS allocation request fails and the corresponding node then has to send its data frames during the CAP. A detailed description of the GTS management and the slotted CSMA/CA mechanism is presented in [4].


### 2.2. Related Work

Since the IEEE 802.15.4 was proposed, a lot of work has been done focusing on how to optimize its performance [5–10]. Compared to other wireless techniques, a key difference is the introduction of GTS in IEEE 802.15.4. As a result, the GTS optimization has received particular attentions to improve IEEE 802.15.4 performance.In [5], the authors propose an implicit GTS allocation mechanism (i-Game) to improve bandwidth utilization, by allocating GTS to devices implicitly based not only on the remaining time slots but also on the traffic specifications of the flows, their delay requirements, and the available bandwidth resources. An adaptive GTS allocation (AGA) scheme is proposed in [6]. It uses dynamic priority control to allocate GTS to devices, in which GTSs are allocated in a nondecreasing order of the devices' priorities, and a starvation avoidance mechanism is also presented. Bhatti et al. propose a set of new MAC superframes with an aim to lower the response latency and to enhance the reliability in [11]. They swap the position of CFP and CAP in the superframe such that a failed GTS transmission can be retransmitted immediately in the CAP, and as a result the delay can be reduced. Because the FCFS GTS allocation scheme does not meet the requirement of some delay-sensitive or time-critical applications, an optimal work-conserving scheduling algorithm is designed in [7] to meet the delay constraints of time-sensitive transactions. Shrestha et al. formulate the GTS allocation problem as a knapsack problem and provide an optimal GTS allocation scheme to wireless body-area sensor networks such that a minimum bandwidth requirement is satisfied for on-body sensor devices [8]. In [10], the whole wireless sensor network is formulated as a multilevel tree and a framework is devised to construct a flow-balance TDMA schedules for solving the underlying rate differentiation problem using the GTS facility of the standard. A backward compatible energy efficient 802.15.4 MAC protocol for beacon-enabled sensor networks called Deployable Energy Efficient MAC Protocol (DEEP) is proposed in [9]. DEEP modifies the IEEE 802.15.4 beacon frame structure by removing GTS descriptors from the beacons when requested. Therefore, the beacon frame is shortened and the energy consumption can be reduced.Network coding origins from the seminal work [2] and has been proposed as a promising technique to improve the throughput via encoding the packets at the intermediate relay. Later, Katti et al. [3] first derive that the network coding gain is at most 2, which is also validated by their proposed practical COPE system. Liu and Xue [12] characterize the achievable rate regions and find the theoretical optimal sum rates for a basic 3-node topology. Liu et al. [13] show the benefit of network coding for 1D and 2D networks. Keshavarz-Haddad and Riedi [14] prove that the gain of network coding in terms of transport capacity is bounded by a constant factor in an arbitrary wireless network under traditional channel models. Le et al. [15] derive an upper bound of the throughput gain as n/(n+1) in an n-node network based on the encoding number. Iraji et al. [16] propose a new analytical model for throughput evaluation of a wireless tandem network coding based on a multiclass open queueing network. More recently, Umehara et al. [17] provide explicit expressions of the throughput for a single-relay two-hop wireless CSMA system. Seferoglu et al. [18] take into consideration both network coded flows and induced conflicts between nodes in the optimization of intersession wireless network coding. Khreishah et al. [19] propose a joint optimal coding, scheduling, and rate-control scheme using pairwise intersession coding for wireless multihop networks. Nevertheless, little work focuses on applying and exploiting the recent advanced results in network coding into IEEE 802.15.4 networks.


## 2.1. Overview of the IEEE 802.15.4 Beacon-Enabled Transmission

In beacon-enabled mode, the channel time is divided into superframes bounded by the beacon frames transmitted from the coordinator, as shown in Figure2. The time between two consecutive beacon frames is defined as the beacon interval (BI). BI is further divided into two periods, active period and inactive period. All the transmissions happen in and only in the active period, while, in the inactive period, all the devices in the network go into a low-power mode or sleep mode for energy saving. The active period is also referred to as superframe duration (SD). The inactive period is optional according to the requirement of the applications.Figure 2
The superframe structure defined in IEEE 802.15.4.By default, the nodes compete for medium access using slotted CSMA/CA within the contention access period (CAP) during SD. The IEEE 802.15.4 protocol also offers the possibility of having a contention-free period (CFP) within the SD. The CFP is optionally activated upon request from a node. It consists of several numbers of guaranteed time slots (GTSs). The device, which needs dedicated bandwidth to transmit to or receive from the coordinator, can transmit a GTS request command to the coordinator. Upon reception of this request, the coordinator checks whether there are sufficient resources and, if possible, allocates the requested GTSs such that the device can communicate with the coordinator in the reserved GTS in a collision-free way. There are up to seven GTSs that can be allocated provided that there are sufficient capacity available. If the available resources are not sufficient, the GTS allocation request fails and the corresponding node then has to send its data frames during the CAP. A detailed description of the GTS management and the slotted CSMA/CA mechanism is presented in [4].


## 2.2. Related Work

Since the IEEE 802.15.4 was proposed, a lot of work has been done focusing on how to optimize its performance [5–10]. Compared to other wireless techniques, a key difference is the introduction of GTS in IEEE 802.15.4. As a result, the GTS optimization has received particular attentions to improve IEEE 802.15.4 performance.In [5], the authors propose an implicit GTS allocation mechanism (i-Game) to improve bandwidth utilization, by allocating GTS to devices implicitly based not only on the remaining time slots but also on the traffic specifications of the flows, their delay requirements, and the available bandwidth resources. An adaptive GTS allocation (AGA) scheme is proposed in [6]. It uses dynamic priority control to allocate GTS to devices, in which GTSs are allocated in a nondecreasing order of the devices' priorities, and a starvation avoidance mechanism is also presented. Bhatti et al. propose a set of new MAC superframes with an aim to lower the response latency and to enhance the reliability in [11]. They swap the position of CFP and CAP in the superframe such that a failed GTS transmission can be retransmitted immediately in the CAP, and as a result the delay can be reduced. Because the FCFS GTS allocation scheme does not meet the requirement of some delay-sensitive or time-critical applications, an optimal work-conserving scheduling algorithm is designed in [7] to meet the delay constraints of time-sensitive transactions. Shrestha et al. formulate the GTS allocation problem as a knapsack problem and provide an optimal GTS allocation scheme to wireless body-area sensor networks such that a minimum bandwidth requirement is satisfied for on-body sensor devices [8]. In [10], the whole wireless sensor network is formulated as a multilevel tree and a framework is devised to construct a flow-balance TDMA schedules for solving the underlying rate differentiation problem using the GTS facility of the standard. A backward compatible energy efficient 802.15.4 MAC protocol for beacon-enabled sensor networks called Deployable Energy Efficient MAC Protocol (DEEP) is proposed in [9]. DEEP modifies the IEEE 802.15.4 beacon frame structure by removing GTS descriptors from the beacons when requested. Therefore, the beacon frame is shortened and the energy consumption can be reduced.Network coding origins from the seminal work [2] and has been proposed as a promising technique to improve the throughput via encoding the packets at the intermediate relay. Later, Katti et al. [3] first derive that the network coding gain is at most 2, which is also validated by their proposed practical COPE system. Liu and Xue [12] characterize the achievable rate regions and find the theoretical optimal sum rates for a basic 3-node topology. Liu et al. [13] show the benefit of network coding for 1D and 2D networks. Keshavarz-Haddad and Riedi [14] prove that the gain of network coding in terms of transport capacity is bounded by a constant factor in an arbitrary wireless network under traditional channel models. Le et al. [15] derive an upper bound of the throughput gain as n/(n+1) in an n-node network based on the encoding number. Iraji et al. [16] propose a new analytical model for throughput evaluation of a wireless tandem network coding based on a multiclass open queueing network. More recently, Umehara et al. [17] provide explicit expressions of the throughput for a single-relay two-hop wireless CSMA system. Seferoglu et al. [18] take into consideration both network coded flows and induced conflicts between nodes in the optimization of intersession wireless network coding. Khreishah et al. [19] propose a joint optimal coding, scheduling, and rate-control scheme using pairwise intersession coding for wireless multihop networks. Nevertheless, little work focuses on applying and exploiting the recent advanced results in network coding into IEEE 802.15.4 networks.


## 3. Network Coding-Aware Bidirectional Communications

### 3.1. Motivation

The performance gain can be achieved by network coding under both GTS in CFP and CSMA in CAP, or even under the beacon-disable transmission model where only CSMA is possible. Most existing network coding strategies focus on the CSMA case, for example, COPE [3] and its variants proposed for IEEE 802.11 networks. To fill in the vacancy of research on performance improvement in IEEE 802.15.4 networks, we mainly study the issues on exploiting the network coding opportunities via GTS in this paper.Figure3 shows two network coding examples in which the relay node XORs packets from the transmitters and broadcasts the XORed packet to the receivers. The receivers can decode the XORed packet by XORing with the packets they have overheard (Figure 3(a)) or sent before (Figure 3(b)). The former one is known as intersession network coding, in which the receivers must overhear and buffer the packets that may help the decoding of the coded packet. The overhearing takes advantage of the broadcast nature of the wireless communication. The scenario in Figure 3(b) is called intrasession network coding, where the receivers do not need to overhear any packets but have to preserve the packets they have sent in their local buffer for the decoding of the coded packet.Illustration of various network coding strategies in wireless networks.
(a)
In X topology using intersession network coding, overhearing is required(b)
In chain topology using intrasession network coding, overhearing is not requiredIt has been proved that network coding can significantly improve the throughput of the network. Now, let us first investigate whether the network coding is beneficial to energy saving by the example shown in Figure3(b). Considering the scenario shown in Figure 3(b), there is a traffic from Alice to Bob and vice versa. The coordinator (PANC) controls the medium access of the two devices and also relays the data stream between them. Without network coding, the transmissions may be scheduled in the following way:(1)
Alice → PANC,(2)
PANC → Bob,(3)
Bob → PANC,(4)
PANC → Alice.We need 4 transmissions and 4 receptions to complete one transaction without network coding. However, if network coding is considered, the scheduling may go as(1)
Alice → PANC,(2)
Bob → PANC,(3)
Alice←PANC → Bob.Obviously, one transmission can be saved in one transaction compared to the case without network coding. Since the transmission dominates the energy consumption, saving transmissions is of great benefits to the energy efficiency. For more complicated situations from a practical point of view, several technical issues should be still carefully studied to exploit network coding opportunities in IEEE 802.15.4 networks in the following sections.


### 3.2. Network Coding Opportunities

Recalling the COPE built on the IEEE 802.11 networks, where the energy efficiency is not the major concern, we notice that the coordinator can discover the network coding opportunities by letting all the devices report the list of possessed packets. For example,Alice in Figure 3(a) shall tell the coordinator first that it has packet P1. Then, the coordinator can make a decision whether it can encode packet P1 with P2 or not. We think it not efficient for the IEEE 802.15.4 devices to report the packets they are possessing. Instead, we exploit the features of communications in WPANs. The communications in WPANs are usually stable and regular compared to the IEEE 802.11 networks. Furthermore, the overhearing in WPANs should be disabled since it consumes additional energy. As a result, we only focus on intrasession network coding.For intrasession network coding, the first thing to discover the network coding opportunity is to recognize the communication patterns. Whenever there is a relay request, the coordinator registers the source address and the destination address in a communication pattern table. When the coordinator has a packet to relay, it first looks up the table to check whether there is any traffic in the reverse direction. If there is, the communication can be viewed as bidirectional; otherwise it is unidirectional. Since there is no intrasession network coding opportunity in the unidirectional session, either between two devices or between a device and the coordinator, the coordinator simply ignores the unidirectional communication and makes efforts to discover the bidirectional communication first. For bidirectional communications in WPANs, we consider two typical traffic categories: irregular data (e.g., periodical or occasional data exchange) and regular stream (e.g., interactive multimedia applications).Only the information of traffic direction is not enough to define a network coding opportunity. If the communication rates in the two directions do not match well, network coding may degrade the performance as shown in [20]. So the transmission rate should also be taken into consideration. To measure the transmission rate, that is, the utilization of superframe slots, the coordinator maintains a superframe slide window to hold certain past superframes. We view the traffic with similar superframe slot utilization in both sides as the communication pattern with network coding opportunities. The process to identify the network coding opportunity is shown in Algorithm 1.Algorithm 1:Algorithm to discover the intrasession network coding opportunities.
(1) receive a packetp(2)if(3)p’s destination address or source address = the coordinator’s address then(4)  ignore(5)else(6)  update the superframe window with the number of slots for the receptionp(7)  lookup the communication pattern table and check the superframe utilization window(8)ifthere is a communication in reverse direction and the slot utilization difference  is less thanthe predetermined thresholdthen(9)   discover a coding opportunity(10)end if(11)end ifWe use an example to illustrate the algorithm with window size = 5 and threshold = 5. The coordinator first discovers that there is a bidirectional communication betweenAlice and Bob. It creates two communication pattern entries and also monitors the superframe slot utilization of both sides in the past 5 superframes. As shown in Table 1, the coordinator used 20 slots to receive packets from Alice while 16 slots from Bob. The transmission rates of both sides are similar to each other since their utilization difference is less than the threshold. Henceforth, the coordinator discovers a network coding opportunity between Alice and Bob and shall try to exploit the network coding opportunity.Table 1
An example of communication pattern table.
TransmitterReceiverSlide windowAliceBob44444BobAlice44440


### 3.3. Network Coding-Aware Session-Based GTS Allocation

Now the problem comes to how to exploit the discovered network coding opportunity. Intuitively the process should go this way: the coordinator shall first buffer a received packet and wait for the arrival of another packet from the network coding counterpart, then encode the two native packets into a coded packet, and finally multicast it to the two corresponding receivers. This shall work fine during the CAP using slotted CSMA/CA, provided that there is sufficient capacity available to satisfy the transmission requirements for both sides. However, when the bidirectional transmissions happen during the CFP, the GTS allocation shall be taken into account.Consider the scenario whereAlice and Bob have a video conversation on the visual doorbell. A comparatively large amount of streaming data will be transferred between them. Both of them may request a dedicated bandwidth for real-time communication. Suppose both request an 8-slot GTS in every two beacons as required by the application and the request from Alice comes first. Upon the reception of Alice's request, the coordinator may allocate an 8-slot GTS in the next superframe. After that, there may be no sufficient capacity to allocate additional 8-slot GTS to Bob since a minimum CAP duration must be reserved. If the GTS to Alice is not deallocated explicitly by Alice, Bob will continue tracking beacons and wait for aGTSDescPersistenceTime superframes as defined in the IEEE 802.15.4 [4]. In such case, Bob and other devices probably suffer starvation. According to the IEEE 802.15.4, the coordinator assumes that a device has stopped using its transmit-GTS [4] if a data frame is not received in the GTS from the device over at least 2*n superframes, where n is defined as follows:(1)n={28-macBeaconOrder0≤macBeaconOrder≤8,19≤macBeaconOrder≤14.As a result, a GTS shall be deallocated by the coordinator only when it has not been used for at least 2 superframes.Alice may not lose the GTS privilege and continue to use the GTS every 2 superframes. In home area WPAN, a lower mabBeaconOrder is preferred as it ensures quick response to emergency alert, such as firm alarm. In this case, the network coding opportunity may be lost. This is not acceptable even without the consideration of network coding as this will lead to a low utilization of the GTS. To tackle this issue, we propose a network coding-aware session-based (NCAS) GTS allocation scheme.At first, the coordinator allocates GTS by a device-based GTS allocation scheme same as the IEEE 802.15.4. The coordinator shall then track the GTS allocation and utilization of all the devices. Whenever the coordinator detects a network coding opportunity, it turns on the session-based allocation scheme for the two devices. It takes the traffic requirement as well as the GTS request into consideration. As presented before, the two devices usually share the same traffic requirement and the same GTS request. The coordinator shall allocate GTSs for both devices in every superframe and satisfy their traffic requirement at the same time. For the example above, the coordinator shall allocate 4-slot GTS for both devices in every superframe and a virtual link between the two device is created.Although we mainly concern the transmit-GTS, the two devices may also request the receive-GTS to obtain data from the coordinator. In such case, there are two transmit-GTS requests and two receive-GTS requests for each session. In NCAS-based GTS allocation scheme, all of them are considered as a whole and treated as two transmit-GTS requests and one receive-GTS request. As a result, the coordinator shall allocate three GTSs within one superframe so as to complete the network coding-based communication transaction within one superframe.As session-based GTS allocation scheme is incorporated, one may be concerned that whether it influences the communication of other devices because the session-based allocation violates the FCFS basis. For GTS requests from two devices within one session, the coordinator combines the two requests and treats it as the last-come. By such means, no negative impact will occur for the requests in between. For the subsequent requests, they are handled the same as in the IEEE 802.15.4.


### 3.4. Pseudo-Multicast for Intrasession Network Coding

The coded packet shall be relayed to both receivers simultaneously. It is straightforward and reasonable to broadcast the coded packet directly in the IEEE 802.11 networks when the energy is not a major concern. When it comes to the IEEE 802.15.4 networks, on the other hand, the broadcast is not energy efficient if irrelevant devices are involved. Therefore, a careful design of scheduling is required to make sure that both devices can receive the coded packet simultaneously. Otherwise, we may lose the benefit of network coding. To tackle these issues, we propose a Pseudo-Multicast for intrasession network coding in the IEEE 802.15.4 WPANs.A device on a beacon-enabled WPAN can determine whether any data are pending for it by examining thepending address information field [4] of the received beacon frame. As a result, if there is coded packet pending for two devices, the coordinator adds both corresponding addresses into the pending address information field to notify both sides. Upon reception of the beacon frames, both devices will transmit a MAC command requesting the data, using slotted CSMA/CA. The coordinator acknowledges the successful reception of the data request by transmitting an acknowledgment frame. However, the pending coded packet can not be sent immediately after one request. The coordinator shall wait until both requests are received. Due to the different duty cycle or some other reason, the two requests may not arrive within one superframe. Thus, the device who sends the request early shall wait for some time to get the coded packet. According to the IEEE 802.15.4, a device shall enable its receiver for at most macMaxFrameTotalWaitTime CAP symbols and then it may conclude that there are no data pending at the coordinator. To prevent this case, the coordinator shall relay the native packet to that device if the data request from the other side is not received within the macMaxFrameTotalWaitTime CAP symbols. Upon reception of both requests before the macMaxFrameTotalWaitTime CAP symbols, the coordinator sends the coded packet in a Pseudo-Multicast way.As we have known, it is not energy efficient to send the coded packet with broadcast address (0xffff). Instead of using broadcast, we advocate a Pseudo-Multicast to enable the simultaneous reception of both packets without negative impact on other devices. The Pseudo-Multicast actually is a unicast. The coordinator chooses address of the receiver which requested its pending data earlier as the destination address and sends the coded packet out. The device with the specified destination address receives the coded packet directly, while the other device should also take it as desired by recognizing the address of its network coding counterpart in the coded packet. When both devices successfully receive the coded packet, each device should acknowledge the successful reception by an acknowledgement frame, which is the same as specified in the IEEE 802.15.4.If the devices prefer to receive from the coordinator in the GTSs, as presented in last section, the coordinator may allocate a receive-GTS for both devices in the session. Thus, from the starting slot of the allocated GTS, both devices just turn on their receivers and wait for the pending coded packet.


## 3.1. Motivation

The performance gain can be achieved by network coding under both GTS in CFP and CSMA in CAP, or even under the beacon-disable transmission model where only CSMA is possible. Most existing network coding strategies focus on the CSMA case, for example, COPE [3] and its variants proposed for IEEE 802.11 networks. To fill in the vacancy of research on performance improvement in IEEE 802.15.4 networks, we mainly study the issues on exploiting the network coding opportunities via GTS in this paper.Figure3 shows two network coding examples in which the relay node XORs packets from the transmitters and broadcasts the XORed packet to the receivers. The receivers can decode the XORed packet by XORing with the packets they have overheard (Figure 3(a)) or sent before (Figure 3(b)). The former one is known as intersession network coding, in which the receivers must overhear and buffer the packets that may help the decoding of the coded packet. The overhearing takes advantage of the broadcast nature of the wireless communication. The scenario in Figure 3(b) is called intrasession network coding, where the receivers do not need to overhear any packets but have to preserve the packets they have sent in their local buffer for the decoding of the coded packet.Illustration of various network coding strategies in wireless networks.
(a)
In X topology using intersession network coding, overhearing is required(b)
In chain topology using intrasession network coding, overhearing is not requiredIt has been proved that network coding can significantly improve the throughput of the network. Now, let us first investigate whether the network coding is beneficial to energy saving by the example shown in Figure3(b). Considering the scenario shown in Figure 3(b), there is a traffic from Alice to Bob and vice versa. The coordinator (PANC) controls the medium access of the two devices and also relays the data stream between them. Without network coding, the transmissions may be scheduled in the following way:(1)
Alice → PANC,(2)
PANC → Bob,(3)
Bob → PANC,(4)
PANC → Alice.We need 4 transmissions and 4 receptions to complete one transaction without network coding. However, if network coding is considered, the scheduling may go as(1)
Alice → PANC,(2)
Bob → PANC,(3)
Alice←PANC → Bob.Obviously, one transmission can be saved in one transaction compared to the case without network coding. Since the transmission dominates the energy consumption, saving transmissions is of great benefits to the energy efficiency. For more complicated situations from a practical point of view, several technical issues should be still carefully studied to exploit network coding opportunities in IEEE 802.15.4 networks in the following sections.


## 3.2. Network Coding Opportunities

Recalling the COPE built on the IEEE 802.11 networks, where the energy efficiency is not the major concern, we notice that the coordinator can discover the network coding opportunities by letting all the devices report the list of possessed packets. For example,Alice in Figure 3(a) shall tell the coordinator first that it has packet P1. Then, the coordinator can make a decision whether it can encode packet P1 with P2 or not. We think it not efficient for the IEEE 802.15.4 devices to report the packets they are possessing. Instead, we exploit the features of communications in WPANs. The communications in WPANs are usually stable and regular compared to the IEEE 802.11 networks. Furthermore, the overhearing in WPANs should be disabled since it consumes additional energy. As a result, we only focus on intrasession network coding.For intrasession network coding, the first thing to discover the network coding opportunity is to recognize the communication patterns. Whenever there is a relay request, the coordinator registers the source address and the destination address in a communication pattern table. When the coordinator has a packet to relay, it first looks up the table to check whether there is any traffic in the reverse direction. If there is, the communication can be viewed as bidirectional; otherwise it is unidirectional. Since there is no intrasession network coding opportunity in the unidirectional session, either between two devices or between a device and the coordinator, the coordinator simply ignores the unidirectional communication and makes efforts to discover the bidirectional communication first. For bidirectional communications in WPANs, we consider two typical traffic categories: irregular data (e.g., periodical or occasional data exchange) and regular stream (e.g., interactive multimedia applications).Only the information of traffic direction is not enough to define a network coding opportunity. If the communication rates in the two directions do not match well, network coding may degrade the performance as shown in [20]. So the transmission rate should also be taken into consideration. To measure the transmission rate, that is, the utilization of superframe slots, the coordinator maintains a superframe slide window to hold certain past superframes. We view the traffic with similar superframe slot utilization in both sides as the communication pattern with network coding opportunities. The process to identify the network coding opportunity is shown in Algorithm 1.Algorithm 1:Algorithm to discover the intrasession network coding opportunities.
(1) receive a packetp(2)if(3)p’s destination address or source address = the coordinator’s address then(4)  ignore(5)else(6)  update the superframe window with the number of slots for the receptionp(7)  lookup the communication pattern table and check the superframe utilization window(8)ifthere is a communication in reverse direction and the slot utilization difference  is less thanthe predetermined thresholdthen(9)   discover a coding opportunity(10)end if(11)end ifWe use an example to illustrate the algorithm with window size = 5 and threshold = 5. The coordinator first discovers that there is a bidirectional communication betweenAlice and Bob. It creates two communication pattern entries and also monitors the superframe slot utilization of both sides in the past 5 superframes. As shown in Table 1, the coordinator used 20 slots to receive packets from Alice while 16 slots from Bob. The transmission rates of both sides are similar to each other since their utilization difference is less than the threshold. Henceforth, the coordinator discovers a network coding opportunity between Alice and Bob and shall try to exploit the network coding opportunity.Table 1
An example of communication pattern table.
TransmitterReceiverSlide windowAliceBob44444BobAlice44440


## 3.3. Network Coding-Aware Session-Based GTS Allocation

Now the problem comes to how to exploit the discovered network coding opportunity. Intuitively the process should go this way: the coordinator shall first buffer a received packet and wait for the arrival of another packet from the network coding counterpart, then encode the two native packets into a coded packet, and finally multicast it to the two corresponding receivers. This shall work fine during the CAP using slotted CSMA/CA, provided that there is sufficient capacity available to satisfy the transmission requirements for both sides. However, when the bidirectional transmissions happen during the CFP, the GTS allocation shall be taken into account.Consider the scenario whereAlice and Bob have a video conversation on the visual doorbell. A comparatively large amount of streaming data will be transferred between them. Both of them may request a dedicated bandwidth for real-time communication. Suppose both request an 8-slot GTS in every two beacons as required by the application and the request from Alice comes first. Upon the reception of Alice's request, the coordinator may allocate an 8-slot GTS in the next superframe. After that, there may be no sufficient capacity to allocate additional 8-slot GTS to Bob since a minimum CAP duration must be reserved. If the GTS to Alice is not deallocated explicitly by Alice, Bob will continue tracking beacons and wait for aGTSDescPersistenceTime superframes as defined in the IEEE 802.15.4 [4]. In such case, Bob and other devices probably suffer starvation. According to the IEEE 802.15.4, the coordinator assumes that a device has stopped using its transmit-GTS [4] if a data frame is not received in the GTS from the device over at least 2*n superframes, where n is defined as follows:(1)n={28-macBeaconOrder0≤macBeaconOrder≤8,19≤macBeaconOrder≤14.As a result, a GTS shall be deallocated by the coordinator only when it has not been used for at least 2 superframes.Alice may not lose the GTS privilege and continue to use the GTS every 2 superframes. In home area WPAN, a lower mabBeaconOrder is preferred as it ensures quick response to emergency alert, such as firm alarm. In this case, the network coding opportunity may be lost. This is not acceptable even without the consideration of network coding as this will lead to a low utilization of the GTS. To tackle this issue, we propose a network coding-aware session-based (NCAS) GTS allocation scheme.At first, the coordinator allocates GTS by a device-based GTS allocation scheme same as the IEEE 802.15.4. The coordinator shall then track the GTS allocation and utilization of all the devices. Whenever the coordinator detects a network coding opportunity, it turns on the session-based allocation scheme for the two devices. It takes the traffic requirement as well as the GTS request into consideration. As presented before, the two devices usually share the same traffic requirement and the same GTS request. The coordinator shall allocate GTSs for both devices in every superframe and satisfy their traffic requirement at the same time. For the example above, the coordinator shall allocate 4-slot GTS for both devices in every superframe and a virtual link between the two device is created.Although we mainly concern the transmit-GTS, the two devices may also request the receive-GTS to obtain data from the coordinator. In such case, there are two transmit-GTS requests and two receive-GTS requests for each session. In NCAS-based GTS allocation scheme, all of them are considered as a whole and treated as two transmit-GTS requests and one receive-GTS request. As a result, the coordinator shall allocate three GTSs within one superframe so as to complete the network coding-based communication transaction within one superframe.As session-based GTS allocation scheme is incorporated, one may be concerned that whether it influences the communication of other devices because the session-based allocation violates the FCFS basis. For GTS requests from two devices within one session, the coordinator combines the two requests and treats it as the last-come. By such means, no negative impact will occur for the requests in between. For the subsequent requests, they are handled the same as in the IEEE 802.15.4.


## 3.4. Pseudo-Multicast for Intrasession Network Coding

The coded packet shall be relayed to both receivers simultaneously. It is straightforward and reasonable to broadcast the coded packet directly in the IEEE 802.11 networks when the energy is not a major concern. When it comes to the IEEE 802.15.4 networks, on the other hand, the broadcast is not energy efficient if irrelevant devices are involved. Therefore, a careful design of scheduling is required to make sure that both devices can receive the coded packet simultaneously. Otherwise, we may lose the benefit of network coding. To tackle these issues, we propose a Pseudo-Multicast for intrasession network coding in the IEEE 802.15.4 WPANs.A device on a beacon-enabled WPAN can determine whether any data are pending for it by examining thepending address information field [4] of the received beacon frame. As a result, if there is coded packet pending for two devices, the coordinator adds both corresponding addresses into the pending address information field to notify both sides. Upon reception of the beacon frames, both devices will transmit a MAC command requesting the data, using slotted CSMA/CA. The coordinator acknowledges the successful reception of the data request by transmitting an acknowledgment frame. However, the pending coded packet can not be sent immediately after one request. The coordinator shall wait until both requests are received. Due to the different duty cycle or some other reason, the two requests may not arrive within one superframe. Thus, the device who sends the request early shall wait for some time to get the coded packet. According to the IEEE 802.15.4, a device shall enable its receiver for at most macMaxFrameTotalWaitTime CAP symbols and then it may conclude that there are no data pending at the coordinator. To prevent this case, the coordinator shall relay the native packet to that device if the data request from the other side is not received within the macMaxFrameTotalWaitTime CAP symbols. Upon reception of both requests before the macMaxFrameTotalWaitTime CAP symbols, the coordinator sends the coded packet in a Pseudo-Multicast way.As we have known, it is not energy efficient to send the coded packet with broadcast address (0xffff). Instead of using broadcast, we advocate a Pseudo-Multicast to enable the simultaneous reception of both packets without negative impact on other devices. The Pseudo-Multicast actually is a unicast. The coordinator chooses address of the receiver which requested its pending data earlier as the destination address and sends the coded packet out. The device with the specified destination address receives the coded packet directly, while the other device should also take it as desired by recognizing the address of its network coding counterpart in the coded packet. When both devices successfully receive the coded packet, each device should acknowledge the successful reception by an acknowledgement frame, which is the same as specified in the IEEE 802.15.4.If the devices prefer to receive from the coordinator in the GTSs, as presented in last section, the coordinator may allocate a receive-GTS for both devices in the session. Thus, from the starting slot of the allocated GTS, both devices just turn on their receivers and wait for the pending coded packet.


## 4. Performance Evaluation

To investigate how network coding performs in the beacon-enabled IEEE 802.15.4 WPANs, we have developed a Java-based simulator. It simulates the network topology shown in Figure3(a) where there are two devices communicating with each other via a single relay. The connections between the device and the relay are assumed as packetloss-free half-duplex channel. Each superframe consists of up to 16 time slots, and one traffic unit can be transmitted within a time slot.Two bidirectional traffic models are considered in our experiments. For the irregular traffic, data generation with a Poisson distribution is simulated. We investigate the performance of XOR-based network coding under various traffic loads (4 and 5) and mean packet arrival rates (0.2, 0.5, 0.8, and 1.0), which are defined as the number of traffic units per packet and the number of packets per superframe, respectively. For regular traffic with streaming data, packets are uniformly generated within each superframe with various loads from 1 to 5 traffic units per packet, below the network capacity with network coding. To study the energy consumption of the proposed scheme in our experiments, we follow the power model on the energy measurements for the CC1000 radio on Mica2 motes [21], which is a third generation mote module used for low-power WSNs. The parameters used in our simulations are summarized in Table 2.Table 2
Simulation parameters and power model.
Simulation parametersTraffic modelPoisson trafficStreaming trafficTraffic load (traffic units/packet)4 and 51, 2, 3, 4, 5Data arrival rate (packet/superframe)0.2, 0.5, 0.8, 1.0N/ASuperframe length (slots)16Power modelRadio power in idle (mW)1.38Radio power in receiving (mW)9.6Radio power in transmitting (mW)17To investigate the benefit of network coding in IEEE 802.15.4 network, we assume that all transmissions happen during the CFP since a key difference between IEEE 802.11 network and IEEE 802.15.4 network is the CFP. We consider an extreme condition that the whole superframes are statically allocated as GTSs to each device. The allocation remains unchanged for duration of the simulation. For network coding-aware allocation, we follow the session-based GTS allocation presented in Section3.3, while for conventional way, we adopt FIFO policy as described in [4].


### 4.1. Power Efficiency

In the first set of experiments, we evaluate and compare the power consumption for the schemes with and without network coding under different traffic scenarios. For streaming traffic, the packets arrive at every superframe with different traffic units, for example, 1, 2, 3, 4, or 5. For Poisson traffic, the mean packet arrival rates are 0.2, 0.5, 0.8, and 1.0 packet per superframe, and each packet has 4 or 5 traffic units. Recall that one traffic unit can be transmitted within one GTS, leading to 4 or 5 GTSs required by each device.The simulation results for the streaming traffic case are illustrated in Figure4(a). We notice that the energy consumptions of each device (Alice or Bob) are almost the same when the traffic load is between 1 and 4, no matter whether network coding is applied or not. Recall that one bidirectional communication can be completed within one superframe in either case, where 4-slot transmissions and 4-slot receptions are required for each device. As a result, each device consumes almost the same energy within a superframe no matter network coding is applied or not. The same observation can be made for Poisson traffic with traffic load of 4 traffic units per packet, as shown in Figure 4(b), indicating that intrasession XORed based network coding is not beneficial to power efficiency of the devices. On the other hand, we may also say that it does not introduce any additional energy overhead to the devices either.Power consumption comparison.
(a)
Power consumption when both devices have streaming data with different traffic units GTS(b)
Power consumption when both devices have Poisson traffic with different packet arrival rates (Packet size = 4)(c)
Power consumption when both devices have Poisson traffic with different packet arrival rates (Packet size = 5)When the traffic load is 5, less energy is consumed without network coding at each device for both streaming traffic in Figure4(a) and Poisson traffic in Figure 4(c).  This is because one bidirectional communication can be completed and either device transmits in 5 slots and receives in other 5 slots in a superframe if network coding is exploited. In contrast, one bidirectional communication is across at least two superframes without using network coding. Within one of the frames, a device may switch into idle state if no packets are intended. In conclusion, both devices keep busy during almost every superframe if network coding is exploited, while one device may switch into low-power state during some superframes if network coding is not exploited.We then study the power consumption of the relay node. From Figure4, we can see that network coding can always save power in all cases. For example, when the packet size is 4 in Poisson traffic, the relay needs 4 slots to transmit the encoded packets if the network coding is applied and 8 slots to relay the native ones if the network coding is not exploited. Therefore, 4 slots can be saved for the relay to complete one communication between the two nodes by exploiting the network coding opportunities. Similar observations apply to the packet size of 5 traffic units.One may also notice that the power saving of the relay with network coding is an increasing function of the packet size in streaming traffic in Figure4(a) or an increasing function of the packet arrival rate in Poisson traffic in both Figures 4(b) and 4(c). For example by exploiting network coding in Figure 4(b), the power is saved around 6% when the mean packet arrival rate is 0.2 and up to 45% when the mean rate is 1.0. This is because the higher the packet arrival rate is, the more network coding opportunities are possible to be exploited.Figure5 compares the number of packets directly relayed as native ones and the number of XORed packets under different packet arrival rates. No matter the packet size is 4 or 5, it can be always observed that higher rate exhibits more network coding opportunities. In the case when the packet size is 4 and the mean data rate is 0.2, most packets, around 3032, are relayed directly while only 664 packets are relayed as coded ones. When the packet arrival rate rises to 1.0, 19176 packets are relayed as coded ones while only 388 packets are directly relayed.Figure 5
The number of packets directly relayed or XORed under different data rates.


### 4.2. Throughput

The throughput for streaming traffic with various packet sizes and for Poisson traffic with various packet arrival rates, with/without network coding, is shown in Figure6. One may first notice that the same throughput is achieved when the packet sizes are less than 5, as shown in Figure 6(a). This is because, under these situations, a superframe with 16 time slots is enough for one bidirectional communication no matter network coding is used or not. Same phenomena can be also observed in Figure 6(b) when the packet size is 4. We may also note that the saved slots in each superframe by exploiting network coding could be utilized by other communication sessions if possible, resulting in an improved throughput.Throughput comparison.
(a)
Throughput of streaming traffic with different traffic units(b)
Throughput of Poisson traffic with different packet arrival ratesThe throughput improvement by network coding is significant when each packet has a length of 5 traffic units. To complete a whole bidirectional communication session, 20 slots are required if direct relay is used, while only 15 slots are required if network coding is applied. For example, the throughput is 7.90 with network coding but only 5.99 without network coding when the packet arrival rate is 1.0 as shown in Figure6(b).


## 4.1. Power Efficiency

In the first set of experiments, we evaluate and compare the power consumption for the schemes with and without network coding under different traffic scenarios. For streaming traffic, the packets arrive at every superframe with different traffic units, for example, 1, 2, 3, 4, or 5. For Poisson traffic, the mean packet arrival rates are 0.2, 0.5, 0.8, and 1.0 packet per superframe, and each packet has 4 or 5 traffic units. Recall that one traffic unit can be transmitted within one GTS, leading to 4 or 5 GTSs required by each device.The simulation results for the streaming traffic case are illustrated in Figure4(a). We notice that the energy consumptions of each device (Alice or Bob) are almost the same when the traffic load is between 1 and 4, no matter whether network coding is applied or not. Recall that one bidirectional communication can be completed within one superframe in either case, where 4-slot transmissions and 4-slot receptions are required for each device. As a result, each device consumes almost the same energy within a superframe no matter network coding is applied or not. The same observation can be made for Poisson traffic with traffic load of 4 traffic units per packet, as shown in Figure 4(b), indicating that intrasession XORed based network coding is not beneficial to power efficiency of the devices. On the other hand, we may also say that it does not introduce any additional energy overhead to the devices either.Power consumption comparison.
(a)
Power consumption when both devices have streaming data with different traffic units GTS(b)
Power consumption when both devices have Poisson traffic with different packet arrival rates (Packet size = 4)(c)
Power consumption when both devices have Poisson traffic with different packet arrival rates (Packet size = 5)When the traffic load is 5, less energy is consumed without network coding at each device for both streaming traffic in Figure4(a) and Poisson traffic in Figure 4(c).  This is because one bidirectional communication can be completed and either device transmits in 5 slots and receives in other 5 slots in a superframe if network coding is exploited. In contrast, one bidirectional communication is across at least two superframes without using network coding. Within one of the frames, a device may switch into idle state if no packets are intended. In conclusion, both devices keep busy during almost every superframe if network coding is exploited, while one device may switch into low-power state during some superframes if network coding is not exploited.We then study the power consumption of the relay node. From Figure4, we can see that network coding can always save power in all cases. For example, when the packet size is 4 in Poisson traffic, the relay needs 4 slots to transmit the encoded packets if the network coding is applied and 8 slots to relay the native ones if the network coding is not exploited. Therefore, 4 slots can be saved for the relay to complete one communication between the two nodes by exploiting the network coding opportunities. Similar observations apply to the packet size of 5 traffic units.One may also notice that the power saving of the relay with network coding is an increasing function of the packet size in streaming traffic in Figure4(a) or an increasing function of the packet arrival rate in Poisson traffic in both Figures 4(b) and 4(c). For example by exploiting network coding in Figure 4(b), the power is saved around 6% when the mean packet arrival rate is 0.2 and up to 45% when the mean rate is 1.0. This is because the higher the packet arrival rate is, the more network coding opportunities are possible to be exploited.Figure5 compares the number of packets directly relayed as native ones and the number of XORed packets under different packet arrival rates. No matter the packet size is 4 or 5, it can be always observed that higher rate exhibits more network coding opportunities. In the case when the packet size is 4 and the mean data rate is 0.2, most packets, around 3032, are relayed directly while only 664 packets are relayed as coded ones. When the packet arrival rate rises to 1.0, 19176 packets are relayed as coded ones while only 388 packets are directly relayed.Figure 5
The number of packets directly relayed or XORed under different data rates.


## 4.2. Throughput

The throughput for streaming traffic with various packet sizes and for Poisson traffic with various packet arrival rates, with/without network coding, is shown in Figure6. One may first notice that the same throughput is achieved when the packet sizes are less than 5, as shown in Figure 6(a). This is because, under these situations, a superframe with 16 time slots is enough for one bidirectional communication no matter network coding is used or not. Same phenomena can be also observed in Figure 6(b) when the packet size is 4. We may also note that the saved slots in each superframe by exploiting network coding could be utilized by other communication sessions if possible, resulting in an improved throughput.Throughput comparison.
(a)
Throughput of streaming traffic with different traffic units(b)
Throughput of Poisson traffic with different packet arrival ratesThe throughput improvement by network coding is significant when each packet has a length of 5 traffic units. To complete a whole bidirectional communication session, 20 slots are required if direct relay is used, while only 15 slots are required if network coding is applied. For example, the throughput is 7.90 with network coding but only 5.99 without network coding when the packet arrival rate is 1.0 as shown in Figure6(b).


## 5. Conclusion

In this paper, we have studied how to exploit network coding in the beacon-enabled IEEE 802.15.4 LR-WPAN and how it benefits the performance of the network in terms of power saving and throughput. Several important practical issues are studied, such as the discovery of network coding opportunities, GTS allocation for network coded transmissions in GTS during the CFP, and pseudo-multicast for simultaneous reception of coded packets without negative impact on other devices. All these concerns enable a realistic and efficient network coding paradigm in the IEEE 802.15.4 LR-WPAN. The simulation results further provide an insight to the understanding that network coding can improve the performance of IEEE 802.15.4 LR-WPAN in terms of both throughput and power efficiency.



---

*Source: 310647-2011-06-13.xml*