Data Dissemination in Wireless Sensor Networks with Network Coding

Recently, more research attention has been directed towards wireless sensor networks. Once deployed, sensors are expected to operate for extended periods of time, and it is impractical to physically reach all sensors. However, it is quite often necessary to update the software running on those sensors or add new functionality to the sensors [1‐3]. Reprogramming the network needs to reliably disseminate large data objects (50–100 KB) to every sensor in the network with energy efficiency [2].

Protocols for reliably disseminating large data objects in WSNs have been developed over years. Protocols in [1‐4] achieve data dissemination reliability through different mechanisms such as hop-by-hop recovery, NACKs or ACKs mechanisms, while another requirement of disseminating large objects in WSNs, energy efficiency, has not been well studied.

In WSNs, energy consumption is a critical issue and sleep scheduling has been well studied as a conservative approach to minimize the energy consumption due to idle listening [5, 6]. Though sleep scheduling can save energy, sensors in sleep mode cannot receive data packets. In addition, due to the unreliability of wireless communication, a sensor may not receive the packet successfully even when it is in active mode [7]. Hence, a data packet may be transmitted several times in order to be disseminated to all sensors, which wastes energy and increases the delay of the whole data dissemination process. In other words, the data dissemination process consists of sending native data packets and recovering "wanted" packets that each sensor has not received due to sleep scheduling and/or link unreliability. In order to complete the data dissemination process in a timely manner and achieve energy efficiency, it is crucial to assure that the maximum number of "wanted" packets at all sensors can be recovered at each time slot.

Recently, network coding has become a promising approach to improve the system throughput in wireless networks. Network coding with XORs operation in wireless broadcast has been studied in [8], which shows the advantage of the proposed XORs coding scheme over the traditional wireless broadcast in the bandwidth efficiency through simulations and theoretical analysis. In XORs coding, a coded packet carries both the coding vector information and the encoded data. Thus, upon receiving a coded packet, the receiver knows which packets are encoded together and how to decode the packet with the available packets at the receiver. The work in [9] has proved that optimal XORs encoding decision for wireless broadcast, which decides the coding vector of each coded packet, is an NP-hard problem. Heuristic algorithms of encoding decision problem for wireless broadcast and multicast are proposed in [9, 10]. However, the proposed encoding decision approach can only be applied to the scenario where all receivers remain active during the whole time period of recovery. Such an approach can not be applied to WSNs with sleep scheduling because different sets of active sensors may be available at different time slots.

In this paper, given the sleep scheduling information at the sensors, we aim to determine an effective XORs encoding strategy such that the minimum number of transmissions is required in order for each sensor in the network to successfully receive the whole set of disseminated data packets. Thus, energy consumption can be reduced and the data dissemination process can be accomplished in a timely manner. To achieve such an objective, it is important to maximize the expected number of active sensors that can decode out one "wanted" data packet at each time slot in the recovery process, which is the focus of this paper. The contribution of the proposed work is summarized as follows.

The rest of the paper is organized as follows. Related work is reviewed in Section 2. Section 3 introduces the system architecture and data dissemination schemes. The problem description and its complexity is presented in Section 4. Section 5 describes the algorithm design. Theoretical analysis is given in Section 6. Section 7 gives the simulation results. Finally, we conclude the paper in Section 8.

In this section, we review the related work of network coding in WSNs. Network coding is originally proposed in information theory [11] and recently has become a promising approach to improve the system throughput in wireless networks [11‐16]. Adaptive network coding is proposed in [17] to reduce traffic in the process of software updates where linear network coding technique is used. As computation ability and the memory at sensor nodes are very limited, the complexity of linear encoding and decoding introduces extra overhead. Thus, it is more appropriate to use XORs operation in WSNs since both encoding and decoding operations are much simpler. In fact, XORs coding has been widely used in wireless networks to reduce the complexity of linear network coding [8, 10, 18, 19].

COPE proposed in [18] improves the throughput of unicast with XORs coding. By exploiting the broadcast nature of wireless medium, each node buffers overheard packets for a short time and notifies its neighbors which packets it has heard. When a node transmits a packet, it uses its knowledge of what its neighbors have heard to perform opportunistic coding and XORs multiple packets to transmit them as a single packet while ensuring that each intended next-hop has enough information to decode the encoded packet.

Network coding with XORs operation in wireless broadcast has also been studied in [8], which shows the advantage of the proposed network coding scheme over traditional wireless broadcast in bandwidth efficiency through simulations and theoretical analysis. However, encoding decision has not been given in [8]. The work in [9] has proved that optimal XORs encoding decision problem for wireless broadcast is an NP-hard problem.

Several heuristic algorithms for encoding decision in wireless broadcast and multicast have been proposed in [9, 10]. With the knowledge of the "wanted" packet set at each receiver, an auxiliary graph is constructed. The encoding decision during the recovery process is then converted to a clique partition problem in the auxiliary graph. However, the proposed encoding decision algorithms can only be applied to the scenario where all receivers remain active during the time period of recovery. Such an approach cannot be applied to WSNs since different set of active sensors may be available at different time slots. Thus, encoding decision in WSNs with sleep scheduling cannot be converted into finding a minimum clique partition in the graph.

The work in [20] proposes a retransmission scheme, which only uses reception estimation to determine the coding set selection. However, the reception estimation at the source node may not be accurate enough, consequently, some receivers may not be able to decode useful information from the coded packet and more retransmissions will be needed. In addition, the coding decision based on reception estimation does not consider the impact of sleep scheduling, which affects the decoding probability at the receivers in low duty-cycled WSNs.

In this paper, we propose to use XORs coding in data dissemination in a large scale WSN which is organized as a multihop cluster hierarchy [21]. A multihop cluster hierarchical architecture consists of multiple layers as shown in Figure 1. In the lowest layer, all the nodes in the network are grouped into clusters. In addition, besides being a member in a cluster, a node may act as a cluster head in a down layer cluster, for example, in the figure. Within each cluster, the cluster head communicates with its member sensors in a one-hop fashion [22]. We also assume that each sensor is aware of its one-hop neighbors' sleep scheduling and the reliability of the wireless links between the sensor to its neighbors. This can be easily accomplished by one-hop information exchange and link loss inference [23].

Our data dissemination process is conducted at each cluster head so as to make sure that finally all the sensors obtain the updating packets. In a multihop cluster hierarchy, if a cluster head in an intermediate layer starts to transmit the received packet immediately after receiving one fresh packet, the gain of network coding cannot be fully utilized. On the other hand, if a cluster head waits and starts to transmit packets until it receives all packets from the cluster head in the upper layer, it will waste bandwidth and introduce extra delay. In order to achieve the balance between bandwidth efficiency and network coding gain, we propose to use a threshold to determine when the current cluster head starts to transmit the packets to its member nodes. Specifically, for each cluster head, after obtaining fresh native packets, where and is the number of native packets available at its upper-layer cluster head, it will conduct XORs coding scheme to transmit the packets to its member nodes. In the simulation part, we will study the impact of the threshold on the delay and energy consumption.

In the rest of the paper, we focus on how a cluster head encodes the packets and transmits them to its member sensors. The coding decision at other cluster heads can use the same approach.

As we mentioned earlier, the data dissemination process consists of sending native data packets and recovering "wanted" packets for each receiver. We now give an example to show that network coding can indeed recover "wanted" packets for all neighbors more efficiently.

Suppose that four packets , and need to be transmitted to sensors and as shown in Figure 2. The sleep scheduling at each receiver is given in Figure 2(a) where 1 denotes that this sensor is active at the current time slot, otherwise, it is in sleep mode. For the sake of simplicity, in this example, we assume that no packet is lost due to unreliable wireless communication, which means that a sensor can receive a packet successfully when it is in active mode. We also assume that an active sensor can only transmit or receive one packet at each time slot [5]. We show that different data dissemination approaches will lead to different finishing time of data dissemination.

We now discuss how the cluster head can maintain "wanted" packet set at each member sensor. After sending out a packet, the cluster head needs to collect the "wanted" packet set at each member sensor. In order to reduce ACKs implosion, only the active receivers that have received a packet at current time slot successfully and can obtain/decode one "wanted" packet from the received packet will send an ACK message to the cluster head. Thus, according to ACKs from receivers, the cluster head can derive the "wanted" packet set for each active receiver.

With the information of "wanted" packet set of each receiver at each time slot in the recovery process, an encoding decision which aims to maximize the expected number of active sensors that can decode out one "wanted" packet at current time slot will be introduced in the following section.

In this section, we first describe the encoding decision problem that aims to decide which native packets should be encoded at each time slot in the recovering process such that the maximum expected number of active sensors at time slot can decode out one "wanted" native packet. Thus, we limit our discussion to the recovery process of one data dissemination batch in a cluster, which can also be applied to other batches in all other clusters.

Suppose that is the set of data packets in a batch which need to be disseminated to all the sensors in a cluster. Let be the set of active member sensors in the cluster at th time slot At each time slot, the cluster head can obtain its neighbor sensors' "wanted" packet set based on ACKs feedback. Let be 1 if packet is not available at active sensor at current time slot where , otherwise, let it be 0. Let and be the "wanted" data packet set of active sensor at current time slot as shown in Figure 2(b). Assume that is the probability that sensor can not successfully receive a packet from the cluster head when is in active mode.

Let be 1 if native packet is combined in current encoded packet, otherwise, let it be 0. Let be 1 if active sensor can decode out one "wanted" native packet from the current encoded packet where , otherwise, let it be 0. Considering unreliable wireless communication, the probability that an active sensor can successfully obtain one "wanted" packet at the current time slot is . Thus, at current time slot, the expected number of sensors that can decode out one "wanted" packet is , which needs to be maximized in order to save energy.

Still take Figure 2(d) as an example, after , the cluster head starts to recover the "wanted" packets at its member sensors. At , if the cluster head sends an encoded packet , in an ideal condition where no packet will be lost, active receivers can decode out one "wanted" packet by or . Assume that , , , in a practical wireless network where the probability of successfully receiving a packet at , , , and is and respectively due to unreliable wireless communication. Thus, the expected number of active receivers that can decode out one "wanted" packet after receiving the current encoded packet is , which is maximum at the current time slot. Thus, the cluster head will send out at the current time slot. In this paper, such an encoding decision problem using XORs coding is referred to as network coding based data dissemination (NCDD) problem.

In this section, we first introduce an auxiliary graph in which each vertex is assigned a weight. We then show that the proposed NCDD problem can be converted into finding a maximum weight clique problem in the auxiliary graph, based on which we develop a heuristic algorithm for the NCDD problem.

In this section, we firstly analyze the impact of packet loss probability and sleep probability on network coding gain. Then, we derive a threshold to decide whether the current sleep scheduling can save energy compared with no sleep scheduling. We only limit the analysis to one cluster in the multihop cluster hierarchy.

In this section, we demonstrate the effectiveness of our dissemination schemes through simulations using C simulator. In our simulations, a multihop cluster hierarchical WSN is randomly generated with the fixed value of the number of sensors if without specification. We group the packets required to send into batches, and each batch has packets. Recovery process with network coding starts after every native packets are transmitted. In a cluster, we randomly generate sensor 's sleep scheduling according to its sleeping probability .

To demonstrate the advantage of our coding scheme, we introduce two baseline algorithms, namely, dissemination without coding algorithm and dissemination with random_coding algorithm. Dissemination without coding algorithm randomly transmits a native "wanted" packet at each time slot until all receivers obtain their "wanted" data packets while dissemination with random_coding algorithm transmits an XORs packet which is randomly generated at each time slot until all receivers obtain their "wanted" packets.

In the simulation, we are interested in evaluating the performance of our coding schemes from the following perspectives.

For each setting, we simulate 150 instances and report the average performance.

This paper studies data dissemination in wireless sensor networks with network coding to achieve energy efficiency. In order to quickly complete the whole process of data dissemination, at each time slot in the recovery process, we aim to transmit an encoded packet such that the expected number of active sensors that can decode out one "wanted" packet is maximized. A maximum weight clique model is proposed here to achieve such an objective. We further study the impact of packet loss probability and sleep probability on network coding gain. We also analyze the impact of sleep probability on energy saving gain and derive a threshold which can be used to decide whether the current sleep scheduling is effective on energy saving or not. The simulation results verify the work proposed in the paper.