An Adaptive Opportunistic Network Coding Mechanism in Wireless Multimedia Sensor Networks

Abstract

The network coding technique is promising for improving the performance of video communication in wireless multimedia sensor networks. However, some special characteristics of existing wireless network coding mechanisms degrade the performance of video data delivery. This work begins with a thorough investigation and understanding of the performance limitations of existing wireless network coding mechanisms. On this basis, we propose an Adaptive Opportunistic Network Coding mechanism (AONC) to improve the transmission quality of video stream in wireless multimedia sensor networks. First, we propose a novel asymmetric coding method to process the video data of different lengths. The aim is to improve data exchange gain. Second, we design an opportunistic forwarding strategy based on dynamic priority to ensure that packets have a better chance to be coded and transmitted, thus achieving much higher throughput. Finally, we present a traffic-aware data scheduling algorithm, working together with the above network coding mechanism, to reduce the loss of potential coding opportunities. Our simulation results demonstrate that, compared with the existing typical network coding mechanisms, AONC can greatly enhance video transmission quality and efficiently utilize bandwidth and energy resources.

1. Introduction

As the bandwidth of wireless channels increases and low-cost hardware device such as CMOS cameras appears, wireless multimedia sensor networks (WMSNs), that is, networks of wireless embedded devices that allow retrieving video and audio streams in real time from the physical environment, have drawn tremendous attention from academia and industry [1–3]. WMSNs can enhance a lot of potential applications such as video surveillance, traffic enforcement, control systems, remote health monitoring, and industrial process control. Multimedia sensors in WMSNs have severe resource constraints including bandwidth, energy, storage, processing capability, and achievable data rate [4], while the delivery of multimedia data is resource demanding. These constraints and challenges, in combination with the transmission reliability required by video applications, make video communication in such environment a challenging proposition.

Network coding is one of the most important achievements on the theory of information processing and transmission. The concept is first proposed for achieving the min-cut capacity in the context of multicast communication [5]. Since then, there are various studies concerning theoretical limitations and practical applications of network coding. COPE [6] is the first practical network coding mechanism for supporting efficient unicast communication in wireless network. Motivated by COPE, recent research includes loss-aware coding mechanism [7, 8], opportunistic forwarding strategy [9, 10], coding-aware routing [11–13], rate-adaptive transmission scheme [14–16], QoS-aware scheduling algorithm [17–19], data broadcast protocol [20, 21], and so forth. These studies demonstrate that network coding has an excellent performance in terms of network throughput, energy efficiency, robustness, and so forth. As a result, network coding is a promising technique for supporting video streaming over WMSNs. However, real-time video data transmission is fundamentally different from traditional data communication. Some special characteristics of existing network coding mechanisms degrade the performance of wireless video delivery. In recent years, the existing typical network coding mechanisms proposed in literature do not take the characteristics of video streaming into account and cannot be used directly in wireless video delivery.

This work focuses on performance improvement of video communication in WMSNs. We begin with a thorough investigation and understanding of the performance limitations of existing typical wireless network coding mechanisms. On this basis, we propose an Adaptive Opportunistic Network Coding mechanism (AONC) in WMSNs. The main mechanisms of the AONC consist of three parts. First, unlike these traditional network coding methods, AONC adopts a novel asymmetric coding method to improve data exchange gain efficiently. Second, an opportunistic forwarding strategy with dynamic priority is designed to ensure that packets have a better chance to be coded and transmitted by one forwarder, thus achieving much higher throughput. Finally, we present a traffic-aware data scheduling algorithm, working together with above network coding mechanism. The purpose is to reduce the loss of potential coding opportunities. Our simulation results show that, compared with the existing typical network coding mechanisms, AONC improves the video transmission quality greatly and achieves significant gains in terms of bandwidth and energy efficiency.

The remainder of this paper is organized as follows. Section 2 presents a thorough investigation and understanding of the performance limitations of combining network coding and video streaming. In Section 3, we propose the AONC and present the details of its implementation. Section 4 involves thorough analysis and evaluation of the AONC performance in simulation methodology. Finally, Section 5 concludes this paper and outlines some perspectives for future work.

2. Problem Description

Although these existing wireless network coding mechanisms have demonstrated its capability of improving the network throughput, they still cannot efficiently support video communication. The aim of this paper is to overcome these limitations. We now describe the limitations from the following three aspects.

(1) Traditional Symmetric Coding Method Degrades the Performance of Video Communication

To illustrate the performance limitation of traditional symmetric coding method, we consider two simple examples shown in Figure 1. As shown in Figure 1(a), the data packets of different lengths saved in the output queue are divided into three sets, and we assume that data packets in any two sets meet coding condition. We will present the model of output queue later in Section 3.1. Figure 1(b) provides an example of a simple network coding method, that is, XOR operation in 1 : 1 symmetric mode, to demonstrate the restriction of this coding method. The length of an encoded packet is approximately equal to the size of the largest packet. Due to the difference in the length of video data packets, the coding space utilization is maintained at a low level. A node needs to transmit three times. Obviously, this method is inefficient, and the throughput gain is hard to be improved greatly. Considering the above severe limitation, we propose a novel asymmetric coding method. Figure 1(c) shows the advantage of XOR operation in asymmetric mode. A node only needs to transmit once. The method can adapt the video data of different lengths and has great potential to improve the performance of video communication. We will present the details of its implementation later in Section 3.2.

Figure 1

Packet mixing of different methods.

(2) The Priority Assignment of Coded Packets May Be Unreasonable

To maximize coding opportunities for throughput gain, a mechanism is needed to assign coded transmissions higher priority in scheduling. A common method to assign priority for a coded packet is based on the number of original packets. The greater the number of original packets is, the higher the priority of a coded packet is assigned. However, due to the difference in the length of video data, this method could not accurately indicate the actual amount of original data carried in a coded packet of a certain length. In addition, for the reason that there are only a few priority levels, collisions are most likely to occur. This property enables us to consider an opportunistic forwarding strategy based on dynamic priority. We will discuss it later in Section 3.3.

(3) With Traditional Data Scheduling Mechanism, Some Potential Coding Opportunities May Be Lost

Compression algorithms such as MPEG that are widely used in low-bitrate videos employ coding prediction, motion compensation, and varied length coding technologies to achieve a high efficient compression. However, the compressed video stream is a variable bitrate (VBR) and has very complex traffic characteristics. As a general queue scheduling mechanism, FIFO does not take these factors into account, resulting in loss of potential coding opportunities. Here we, respectively, give two examples, illustrated in Figures 2 and 3, to explain the reason why some potential coding opportunities are lost.

Figure 2

Data scheduling mechanism analyses (Case 1).

Figure 3

Data scheduling mechanism analyses (Case 2).

Figure 2(a) shows a general network scenario where there are five wireless nodes. Suppose that there exist three different flows, that is, $F 1$ , $F 2$ , and $F 3$ , and only $F 1$ - $F 2$ meets coding condition. There has no coding possibility at current time $t_{c}$ , if the amount of queued data of different flows is shown in Figure 2(b). We assume that arriving traffic volume from different flows during the next short interval $(t_{c}, t_{c} + d]$ is shown in Figure 2(c). In this case, some potential coding opportunities may be lost if data packets of $F 1$ are sent more during interval $(t_{c}, t_{c} + d]$ .

Figure 3(a) shows another general network scenario where there are five wireless nodes. Suppose that there exist four different flows, that is, $F 1$ , $F 2$ , $F 3$ , and $F 4$ . Under this scenario, $F 1$ - $F 2$ and $F 3$ - $F 4$ meet coding condition. In accordance with the amount of queued data from different flows shown in Figure 3(b), node R has no coding possibility. We assume that arriving traffic volume of different flows of the next short interval $(t_{c}, t_{c} + d]$ is shown in Figure 3(c). In this case, some potential coding opportunities may be lost if data packets of $F 1$ are sent more during interval $(t_{c}, t_{c} + d]$ .

AONC is designed to seize these potential coding opportunities effectively. The design details will be present later in Section 3.4.

3. Adaptive Opportunistic Network Coding Mechanism

We first describe our network coding model and introduce the notations used in this section. On this basis, the main mechanisms of the AONC are comprised of the following three parts: (1) an asymmetric coding method is used to improve data exchange gain; (2) an opportunistic forwarding strategy with dynamic priority is designed to achieve higher throughput; (3) a traffic-aware data scheduling algorithm is used to reduce the loss of coding opportunities.

3.1. Network Coding Model

We consider the application of network coding in WMSNs. We assume that intermediate nodes can perform network coding operations and combine packets from multiple incoming flows into a single outgoing packet. This packet is broadcasted to the entire neighborhood, thus reaching corresponding neighboring nodes. We assume that node network interface is set in promiscuous mode. The sensor nodes can snoop on all transmissions in their neighborhood and store the overheard data packets, whether they are intended for them or not. In this way, the sensor nodes can know the overheard and routed packets that each neighboring node possesses, such that it can make network coding operations based on this information.

As shown in Figure 4, each sensor node groups data packets in the output queue into data flows, assembling data packets of the same previous forwarder and next-hop receiver into one flow. The set of data flows is expressed as $Q = ⋃ f_{m}$ , $m \in M = {1, 2, \dots, | Q |}$ , where $| Q |$ denotes the number of flows in Q. Let $f_{m} = ⋃ p_{m n}$ , $n \in N_{m} = {1, 2, \dots, | f_{m} |}$ be the mth flow in Q, where $p_{m n}$ and $| f_{m} |$ , respectively, represent the nth data packet of $f_{m}$ and corresponding number of packets in it. Let $l_{m n} \in [1, L]$ be the length of $p_{m n}$ , where L denotes the length of maximum transmission unit. Each sensor node monitors flow information in real time and deletes $f_{m}$ when $| f_{m} | = 0$ in a period of time.

Figure 4

Flow-oriented virtual queue structure.

We define “coding flows” as flows that transmit via an intermediate node, and their packets have opportunities to be encoded. The set of groups of coding flows is defined as $C = ⋃ g_{k}$ , $k \in K = {1, 2, \dots, | C |}$ , where $| C |$ represents the number of groups of coding flows in C. The kth group of coding flows is defined as $g_{k} = ⋃ f_{m}$ , $m \in M_{k} = {1, 2, \dots, | g_{k} |}$ , where $| g_{k} |$ represents the number of flows in $g_{k}$ . Let $n h_{m}$ and $p f_{m}$ be next-hop receiver and previous forwarder of $f_{m}$ . The set of neighboring nodes of $p f_{m}$ is defined as $n b (p f_{m})$ . The relationship between any two flows in a group of coding flows must satisfy

\begin{array}{l} R & = & {(i, j) | (n h_{i} = p f_{j} \lor n h_{i} \in n b (p f_{j})) \\ \land (n h_{j} = p f_{i} \lor n h_{j} \in n b (p f_{i}))}, i, j \in M_{k} . \end{array}

(1)

The set of signs of nonempty flows in $g_{k}$ is defined by $M_{k}^{'} = {m ∣ m \in M_{k}, | f_{m} | > 0}$ . Let $U = ⋃ f_{m}$ , $m \in M_{U} = {1, 2, \dots, | U |}$ be the set of flows that cannot be encoded, where $| U |$ represents corresponding number of flows. The set of signs of nonempty flows in $M_{U}$ is defined by $M_{U}^{'} = {m ∣ m \in M_{U}, | f_{m} | > 0}$ .

We define parameter φ to determine whether network coding conditions are met or not. If yes, φ is set to be 1, and otherwise, φ is set to be 0

\begin{matrix} φ = {\begin{cases} 1, & | M_{k}^{'} | \geq 2, k \in K, \\ 0, & otherwise. \end{cases} \end{matrix}

(2)

The summarized notations in this paper are listed in Table 1.

Table 1

Notations used in this work.

Symbols	Definition
M	The set of signs of flows in output queue
$f_{m}$	The mth flow in output queue, $\| f_{m} \|$ represents the number of packet belonging to $f_{m}$ , $m \in M$
$N_{m}$	The set of signs of mth flow in output queue, $m \in M$
$p_{m n}$	The nth packet of mth flow
$l_{m n}$	The length of $p_{m n}$
L	The length of maximum transmission unit
C	The set of groups of coding flows, $\| C \|$ represents corresponding number of groups
K	The set of signs of groups of coding flows, $\| K \|$ represents corresponding number of signs
$g_{k}$	The kth group of coding flows, $\| g_{k} \|$ represents the number of flows in $g_{k}$ , $k \in K$
$M_{k}$	The set of signs of kth group of coding flows, $\| M_{k} \|$ represents corresponding number of signs, $k \in K$
$M_{k}^{'}$	The set of signs of nonempty flows belonging to kth group of coding flows, $\| M_{k}^{'} \|$ represents corresponding number of signs, $k \in K$
U	The set of flows that can not be encoded, $\| U \|$ represents corresponding number of flows
$M_{U}$	The set of signs of flows that cannot be encoded
$M_{U}^{'}$	The set of signs of nonempty flows in $M_{U}$ , $\| M_{U}^{'} \|$ represents corresponding number of signs
φ	Set to be 1 if network coding conditions are met and is set to be 0 otherwise

3.2. Asymmetric Network Coding Mechanism

3.2.1. Algorithm Design and Analysis

When a sensor node wants to send data, according to (2), if φ is set to be 1, the proposed asymmetric coding method can be used. The core idea is as follows. We, respectively, select the appropriate data packets from each flow in a predetermined group of coding flows and then splice these data packets belonging to the same flow. Finally, we combine corresponding splicing units in a single broadcast transmission. This method can greatly increase the amount of original data carried of a coded packet, thus increasing the information content per transmission. We believe that it is beneficial to provide better quality of video in network bandwidth constrained environments. The optimal selection for data packets belonging to one flow in a group of coding flows with maximize utilization can be formulated as follows:

\begin{array}{l} maximize \sum_{n \in N_{m}} l_{m n} \times x_{m n}, \\ s . t . \sum_{n \in N_{m}} l_{m n} \times x_{m n} \leq S, x_{m n} \in {0, 1}, \\ n \in N_{m}, m \in M_{k}^{'}, k \in K . \end{array}

(3)

Here, we refer to the space length limit as S. The random variable

x_{m n}

is set to be 1 if

p_{m n}

is selected and is set to 0 otherwise.

Let $Y_{m} (S)$ be the optimal length of the splicing unit according to (3). We define the set of signs of data packets in the splicing unit as follows:

\begin{matrix} N_{m, S} = \arg Y_{m} (S), m \in M_{k}^{'}, k \in K . \end{matrix}

(4)

Definition 1.

Space utilizationis a metric which is used to measure the amount of original data carried of a coded packet of a certain length.

This metric accurately reflects the enhancement of transmission efficiency that can be achieved during the transmission period of encoded packet. The space utilization based on asymmetric coding method can be expressed as

\begin{matrix} ASU (k, S) = \frac{\sum_{m \in M_{k}^{'}} Y_{m} (S)}{\max_{m \in M_{k}^{'}} Y_{m} (S)}, k \in K, S \in [1, L] . \end{matrix}

(5)

Traditional symmetric coding method uses FIFO queue scheduling mechanism; that is, the first data packet belonging to one flow (i.e., $p_{m 1}, m \in M_{k}^{'}$ ) in a group of coding flows will be selected for transmission. Therefore, we can express the space utilization based on traditional symmetric coding method as

\begin{matrix} SSU (k) = \frac{\sum_{m \in M_{k}^{'}} l_{m 1}}{\max_{m \in M_{k}^{'}} l_{m 1}}, k \in K, l_{m 1} \in [1, L] . \end{matrix}

(6)

Among all possible candidate data packets, AONC selects appropriate parameters k and S that maximizes space utilization

\begin{matrix} Z = \max_{k \in K} \max_{S \in [1, L]} ASU (k, S) . \end{matrix}

(7)

Theorem 2.

The proposed asymmetric coding method can provide higher space utilization than symmetric coding method can.

The proof is as follows:

\begin{array}{l} Z & \geq & max_{S \in [1, L]} ASU (k, S) \geq ASU (k, max_{m \in M_{k}^{'}} l_{m 1}) \\ \geq & SSU (k), k \in K, l_{m 1} \in [1, L] . \end{array}

(8)

Definition 3.

Data exchange gain indicates that the number of transmissions reduced by a successful encoded packet exchange.

Let ASG( $k, S$ ) and SSG(k), respectively, be the data exchange gain based on asymmetric and symmetric coding method

\begin{matrix} ASG (k, S) = \sum_{m \in M_{k}^{'}} | N_{m, S} |, k \in K, S \in [1, L], \end{matrix}

(9)

\begin{matrix} SSG (k) = | M_{k}^{'} |, k \in K . \end{matrix}

(10)

Combining (9) and (10), we have

\begin{array}{l} ASG (k, S) & \geq & | M_{k}^{'} | \times min_{m \in M_{k}^{'}} | N_{m, S} | \\ \geq & SSG (k, S), k \in K, S = L . \end{array}

(11)

The throughput provided by a successful coded packet exchange, which is based on asymmetric coding method, can be expressed as follows:

\begin{matrix} ATG (k, S) = \sum_{m \in M_{k}^{'}} \sum_{n \in N_{m, S}} l_{m n}, k \in K, S \in [1, L] . \end{matrix}

(12)

According to (8) and (11), we determine that asymmetric coding method has great potential to improve the performance of wireless video communication.

Algorithm 1 shows the pseudocode for the packet selection algorithm based on proposed asymmetric coding method.

Algorithm 1:Packet selection algorithm based on asymmetric coding method.

Input: $⋃ g_{k}$ , $k \in K$

Output: $⋃ p_{m n}$ , $m \in M_{i}$ , $n \in N_{m, J}$

(1) set i, J and ASUR_max to be 0

(2) for $k = 1 \dots | C |$

(3) for each $m \in M_{k}^{'}$

(4) calculate $Y_{m} (S)$ and record $N_{m, S}$

(5) end for

(6) end for

(7) for $k = 1 \dots | C |$

(8) for $S = 1 \dots L$

(9) calculate ASUR( $k, S$ )

(10) if (ASUR( $k, S$ ) > ASUR_max) then

(11) ASUR_max = ASUR( $k, S$ )

(12) $i = k$

(13) $J = S$

(14) end if

(15) end for

(16) end for

3.2.2. Design Details

The communication modules of sensor node are based typically either on IEEE 802.11 [22] standard or on IEEE 802.15.4 [23] standard. IEEE 802.15.4 compliant radio can only support a maximum rate of 250 kbps. At such low data rates, video streaming is possible only if sufficient preprocessing steps, such as dimensional reduction and descriptive representations (color histograms, object shape) are undertaken [24]. As a result, it cannot provide acceptable real-time video transmission in WMSN. Our solution is implemented on IEEE 802.11.

AONC performs packet coding and tagging at the MAC layer. It requires a modification to the DATA and ACK frame headers of the existing 802.11 MAC standard. Figure 5 shows the header fields modified or added for AONC. If encoded, it has a list RA[CFN] about receiver addresses, where CFN denotes the number of coding flows in a coded packet. PktNum[CFN] represents the number of original packets belonging to corresponding flow. For all the encoded packets, the corresponding list PktInfo[CFN][PktNum[CFN]] is used to record packet ID and packet length. The packet ID is generated by creating a 4-byte hash value out of the address of source node and the sequence number carried by the packet, similar to COPE [6]. The packet length is used to obtain the original data packets of a splicing unit. In order to efficiently acknowledge a splicing unit, we extend the structure of original ACK frame to include a new field, that is, PktID[PktNum]. In this way, a single ACK frame can acknowledge multiple data packets of a splicing unit.

Figure 5

MAC headers of AONC.

3.3. Opportunistic Forwarding Strategy Based on Dynamic Priority

The diversity among the intended forwarder or potential forwarder helpers provides the packet various options to be combined with different numbers of and flows of packets, or not coded at all. To maximize throughput provided by a coded packet, AONC adopts opportunistic forwarding strategy based on a dynamic priority assignment strategy. The priority settings should take data exchange gains and other factors into account. BEND [9] assigns coded transmissions higher priority, based on the number of the original packets, in packet scheduling. However, due to the difference in the length of video data, it cannot accurately indicate the actual amount of original data carried in a coded packet of a certain length. Considering the characteristics of video data, we propose a dynamic priority transmission strategy. When the forwarder nodes contend with each other to transmit their scheduled packets, AONC prioritizes them by assigning them dynamic back-off durations before medium access based on the metric; that is, parameter Z, defined in (7), used to indicate the degree of importance of a coded packet. The prioritization is achieved as follows:

\begin{matrix} C W_{\max} = ⌈ \frac{1024}{2^{(Z - 1) \times 2}} ⌉, \\ C W_{\min} = ⌈ \frac{512}{2^{(Z - 1) \times 2}} ⌉ . \end{matrix}

(13)

In this way, an encoded packet with higher space utilization is transmitted with a higher priority, thus achieving enhancement of transmission efficiency. For the noncoded data packets, parameter Z in (13) is set to be 1. On the one hand, it coordinates potential forwarders' accesses to make best use of the coding repository. The nodes with more efficient combination (i.e., an encoded packet with higher space utilization) can capture the media with higher possibilities. This is beneficial for improving data exchange gain and throughput gain. On the other hand, this method is necessary to effectively alleviate such contention and reduce the collision probability, thereby improving the video transmission reliability.

3.4. Traffic-Aware Data Scheduling Algorithm

3.4.1. Traffic Prediction Method

A prediction method is introduced to predict arriving traffic volume. On this basis, we design a traffic-aware data scheduling mechanism. The aim is to reduce the loss of coding opportunities.

In this work, we make use of adding-weight one-rank local-region method, based on chaos time series theory, to predict the arriving traffic volume in a short period of time. The essence of this method is to find $m + 1$ nearest neighbors of the center reference point in the reconstructed phase space and carry out single-step prediction in accordance with the evolution law of these $m + 1$ neighbor points. Suppose that we have a time series ${x (k), k = 1,2, \dots, N}$ of a traffic flow, and the state vector in reconstruction of phase space can be expressed as $X (t) = {x (t), x (t - τ), \dots, x [t - (m - 1) τ]}$ . The N, m and τ, respectively, represent the number of phase points, embedded dimension number, and time interval. Then the values around $X (t)$ can be fitted by formula: $X (t + 1) = a + b X (t)$ .

The above prediction method can be used to predict traffic volume for each fixed interval of time. We refer to the interval of time as I. $X (t + 1)$ represents traffic prediction value of the next time interval I. Let $t_{c}$ be current time. The traffic volume during time interval $(t_{c}, t_{c} + δ I]$ can be denoted as

\begin{matrix} F (t_{c} + δ I) = \sum_{δ \in N^{+}} X (t_{c} + δ) . \end{matrix}

(14)

A simulation experiment was designed to verify the applicability of the predicted method. Four different YUV QCIF video clips, that is, foreman, hall, coastguard, and mother-daughter [25], are used as video sources in WMSNs. We randomly select a video forwarding node and then collect the traffic information received from a video flow in a period of time. Data in successive intervals is collected. The interval I is set to be 0.1 s. We use the above prediction method to obtain predicted traffic volume and compare the bursty characteristic of it with that of original traffic volume. Figure 6 shows the comparison of the original traffic data and the predicted data. We can observe that there is no significant difference between original data and predicted data in the first 30 points, while the difference gradually increases in subsequent 30 points. The chaotic sequence is highly sensitive to the initial value. As time goes by, the prediction error is getting larger and larger. In order to obtain a relatively accurate data, we set δ to be 1 in our experiments, that is, predicted traffic volume within neighboring time interval $(t_{c}, t_{c} + I]$ .

Figure 6

Comparison of bursty nature of original data and prediction data.

3.4.2. Algorithm Design

We define parameter ω to determine whether the traffic-aware packet scheduling mechanism can be used when a sensor node needs to send data. The mechanism can be used if ω is set to be 1 and is set to be 0, otherwise

\begin{matrix} ω = {\begin{cases} 1, & \sum_{k \in K} | M_{K}^{'} | + | M_{U}^{'} | > 0 \land φ = 0, \\ 0, & otherwise. \end{cases} \end{matrix}

(15)

The main idea of data scheduling algorithm is as follows. Data packets belonging to U are selected for transmission if $| M_{U}^{'} | > 0$ . Otherwise, we need to select a appropriate flow to schedule so as to reduce the loss of coding opportunities if $\exists! m \in M_{k} \land | f_{m} | \geq 1$ . The flow selection algorithm is as follows.

Let $R_{m}$ be the amount of queued data belonging to a data flow at $t_{c}$

\begin{matrix} R_{m} = \sum_{n \in N} l_{m n}, m \in M, n \in N_{m}, l_{m n} \leq L . \end{matrix}

(16)

We estimate the amount of queued data belonging to $f_{m}$ at $t_{c} + δ I$ as follows:

\begin{matrix} T_{m} (t_{c} + δ I) \approx R_{m} + F_{m} (t_{c} + δ I), m \in M . \end{matrix}

(17)

Note that we set δ to be 1 in our experiments. Thus, we can obtain a relatively accurate estimation value with respect to the amount of queued data.

The mean and variance of $T_{m} (t_{c} + δ I)$ can be expressed as follows:

\begin{matrix} μ_{k} (t_{c} + δ I) = \frac{1}{| g_{k} |} \sum_{m \in M_{k}} T_{m} (t_{c} + δ I), \\ σ_{k} (t_{c} + δ I) = \sqrt{\frac{1}{| g_{k} |} \sum_{m \in M_{k}} {(T_{m} (t_{c} + δ I) - μ_{k} (t_{c} + δ I))}^{2}} . \end{matrix}

(18)

Reducing the variance is conducive to reduce the loss of coding opportunities. A natural step is to select appropriate flow that minimizes the variance. As a result, the corresponding flow to be selected can be denoted as follows:

\begin{matrix} k = \arg \min_{k \in K} σ_{k} (t_{c} + δ I) . \end{matrix}

(19)

The pseudocode for flow selection is summarized as Algorithm 2.

Algorithm 2:Flow selection algorithm.

Input: $⋃ f_{m}$ , $m \in M$

Output: flow sign i

(1) set iand $σ_{\max}$ to be 0

(2) if ( $| M_{U}^{'} | > 0$ ) then

(3) selects $m \in M_{U}^{'}$ according to FIFO

(4) $i = m$

(5) return;

(6) end if

(7) for $k = 1 \dots | C |$

(8) if ( $| M_{k}^{'} | > 0$ )

(9) calculate $σ_{k} (t_{c} + δ I)$

(10) if ( $σ_{k} (t_{c} + δ I) > σ_{\max}$ ) then

$(11)$ $σ_{\max} = σ_{k} (t_{c} + δ I)$

(12) for $m = 1 \dots | M_{k}^{'} |$

(13) if ( $| f_{m} | > 0$ ) then

$(14)$ $i = m$

(15) end if

(16) end for

(17) end if

(18) end if

$(19)$ end for

4. Performance Evaluation

This section involves thorough performance analyses and evaluation of AONC in simulation methodology. We design and conduct a series of simulation experiments. Section 4.1 describes the evaluation metrics and detailed simulation parameter settings. Section 4.2 presents and analyses the simulation results.

4.1. Performance Metrics

In this work, we use network simulator NS-2 [26] to implement the proposed algorithms. We now evaluate the AONC performance for supporting video communication in various scenarios, and compare it with typical network coding mechanisms, that is, COPE and BEND. Four different YUV QCIF video clips, that is, foreman, hall, coastguard, and mother-daughter [25], are used as video sources for our experiments. Each video clip is encoded as a standard MPEG-4 sequence, which consists of 300 video frames. Each video frame is fragmented into packets before transmission, and the maximum transmission packet size is 1000 bytes. The structure of the group of pictures (GOP) is IBBPBBPBB ( $N = 9$ , $M = 3$ ). The video source delivers video data to receiver at 30 fps. We fix the data rate at 2 Mbps, without any rate adaptation. Our PHY layer model adopts bit-error-rate (BER), which is set to be 2 × 10⁻⁶, to introduce random packet loss to simulate more realistic.

Three case studies are designed and conducted for evaluating the video transmission performance. We begin with a cross topology. Each peripheral node has three neighbors (the center and two other orthogonal peripheral nodes) and the center node has four neighbors (the peripheral nodes). We place four video flows originating from each of the peripheral nodes and terminating at the opposite node. Next, we use a 3-tier scenario, where tiers 1, 2 and 3 each consist of 3 nodes, referred to as 3-3-3 topologies, respectively. We set the separation distance between tiers, so that video flows between tiers 1 and 3 must use tier 2 node(s) as forwarders.

The distance among nodes of the same tier is small. We place four video flows randomly between tiers 1 and 3, two in the forward direction and two in the reverse direction. Then we generalize to a 5 × 5 mesh topology to test the performance of AONC in supporting video streaming in larger networks. Under this scenario, a nonperipheral node has eight neighbors, and a corner node has three neighbors. The diameter of the network is four hops. There are two video flows (using foreman and hall as video sources) and three constant bitrate (CBR) flows in the scenarios. The packet rate of these CBR flows is set to be 10 packets per second.

4.2. Simulation Experiments and Analyses

We now analyze and evaluate the performance of proposed AONC in terms of video transmission quality, network throughput, and energy utilization efficiency.

Figures 7(a)–7(c), respectively, provide PSNR value for each video frame in different scenarios. Note that the value is the average of each video frame of different video sequences. As shown in the result, AONC provides the best video transmission quality, next is BEND, followed by COPE. The 802.11 scheme, as expected, performs poorly. When using AONC, the PSNR values fluctuate little, and the average is higher. These adaptive schemes in AONC are not only able to achieve higher network throughput, but also improve the stability of the video transmission.

Figure 7

PSNR value for each video frame.

Figures 8(a)–8(c) show the average PSNR value of each video clip in different scenarios. On the one hand, the average PSNR of AONC is higher than that of the other three schemes. On the other hand, when using AONC, we can see that there is a little difference between the average PSNR values of different video clips. Therefore, it can be concluded that AONC can provide higher quality of video and higher reliability of video transmission. Actually, the video quality (in PSNR) of received sequences, achieved by AONC, is close to that of the original encoded sequences (no Error).

Figure 8

Average PSNR value for each video clip.

Figure 9 illustrates the reconstructed foreman video in 3-tier scenario, demonstrating that the received video quality of our proposed AONC is better than that obtained with the other three schemes. It is well known that video transmission has a high bandwidth requirement. However, the coding method and data scheduling scheme of existing network coding mechanisms degrade the network bandwidth utilization. As shown in Figures 9(b)–9(d), a large amount of packets are lost when BEND, COPE, and 802.11 are used to transmit video data, thereby causing interruptions, freezes, or jerkiness in the received video signal.

Figure 9

Visual comparison of the reconstructed video (foreman).

The bursty is one of the characteristics of video streaming. With the symmetric coding method, these traditional network coding mechanisms could not efficiently absorb video traffic and thus have limitations on the enhancement of throughput when available bandwidth is limited and insufficient to meet demand. Using traffic-aware data scheduling algorithm, AONC has the capability to capture these potential coding opportunities, thus eliminating the performance limitation in BEND and COPE. Figure 10 compares the throughput achieved of different mechanisms under corresponding scenarios, where cross and 3-tier topology may provide much more coding opportunities than 5 × 5 mesh topology. As shown in Figure 10(a), the difference of average receiving data rate between the cross topology and the 3-tier topology is the greatest, and AONC always performs better than the other three mechanisms. The throughput gains of AONC, BEND and COPE over 802.11 are plotted in Figure 10(b). We can observe that the throughput gain of AONC is obviously larger than that of BNED, and COPE. The gain we have is in the improvement of end-to-end throughput and reduction in bandwidth consumption.

Figure 10

Throughput.

Figure 11 shows the energy utilization efficiency of different mechanisms. Here we define the energy utilization efficiency as the number of obtained decodable video frames per unit of energy consumption. In WMSNs, sensor nodes consume most energy for data transmission and reception. Obviously, the enhancement of data exchange gain can greatly reduce energy consumption for data transmission. Comparing with the other three schemes, AONC achieves significant improvement in energy utilization efficiency.

Figure 11

Energy utilization efficiency.

5. Conclusion

The limited resources identify significant challenges for the reliable video transmission over WMSNs. There is great potential for network coding to enhance the performance of video transmission and bandwidth utilization. Recent studies demonstrate that network coding is a promising technique for performance improvement of video communication over WMSNs. However, these existing wireless network coding mechanisms have three limitations: (1) traditional symmetric coding method degrades the performance of video communication; (2) the priority assignment of coded packets may be unreasonable; (3) some potential coding opportunities may be lost when using traditional data scheduling mechanism. The aim of this paper is to overcome these limitations. In particular, we propose an Adaptive Opportunistic Network Coding mechanism (AONC).

The main contributions in our work are as follows. First, considering the characteristics of compressed video stream, we introduce a novel asymmetric coding method to improve data exchange gain. Second, an opportunistic forwarding strategy with dynamic priority is designed to ensure that packets have a better chance to be coded and transmitted. The purpose is to achieve higher throughput. Finally, we present a traffic-aware data scheduling algorithm, working together with above network coding mechanism, to reduce the loss of potential coding opportunities. We implement the AONC in NS-2 and carry out extensive evaluation. The simulation results demonstrate that, compared with the existing typical network coding mechanisms, AONC greatly improves the video transmission quality and achieves significant gains in terms of bandwidth and energy efficiency. As a result, we determine that the proposed new techniques are feasible for video communication in WMSNs.

Our ongoing work focuses on the implementation and validation of the proposed algorithms on the prototype system. In addition, one possible future direction of this work is how to provide resiliency network coding opportunity when traffic congestion occurs.

Footnotes

Acknowledgments

The authors would like to thank the anonymous reviewers for the constructive and valuable comments. The authors gratefully acknowledge the support and financial assistance provided by the National Natural Science Foundation of China under Grant no. 60673185 and 61073197, the Natural Science Foundation of Jiangsu Province under Grant no. BK2010548, the Scientific and Technological Support Project (Industry) of Jiangsu Province under no. BE2011186, the State Key Laboratory Program for Novel Software Technology (Nanjing University) under Grant no. KFKT2010 B08, and the Research Innovation Program for College Graduates in Jiangsu Province under Grant no. CXLX11 0262.

References

Akyildiz

I. F.

Melodia

Chowdury

K. R.

Wireless multimedia sensor networks: a survey

IEEE Wireless Communications 2007 16 6 32 39

H. D.

Tao

Multimedia sensor network and its research progresses

Journal of Software 2006 17 9 2013 2028

2-s2.0-33750457389

10.1360/jos172013

Dai

Wang

Akyildiz

I. F.

Correlation-aware QoS routing with differential coding for wireless video sensor networks

IEEE Transactions on Multimedia 2012 14 5 1469 1479

Melodia

Akyildiz

I. F.

Cross-layer QoS-aware communication for ultra wide band wireless multimedia sensor networks

IEEE Journal on Selected Areas in Communications 2010 28 5 653 663

Ahlswede

Cai

S. Y. R.

Yeung

R. W.

Network information flow

IEEE Transactions on Information Theory 2000 46 4 1204 1216

2-s2.0-0034229404

10.1109/18.850663

Katti

Rahul

Katabi

Medard

Crowcroft

XORs in the air: practical wireless network coding

Proceedings of ACM SIGCOMM

2006

Pisa, Italy

243 254

Seferoglu

Markopoulou

Ramakrishnan

K. K.

I²NC: intra- and inter-session network coding for unicast flows in wireless networks

Proceedings of the IEEE INFOCOM 2011

April 2011

Shanghai, China

1035 1043

2-s2.0-79960862938

10.1109/INFCOM.2011.5934877

Rayanchu

Sen

Baneriee

Senqupta

Loss-aware network coding for unicast wireless sessions: design, implementation, and performance evaluation

Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS '08)

June 2008

Annapolis, Md, USA

85 96

2-s2.0-57349187594

10.1145/1375457.1375468

Zhang

Chen

Y. P.

Marsic

MAC-layer proactive mixing for network coding in multi-hop wireless networks

Computer Networks 2010 54 2 196 207

2-s2.0-74449083988

10.1016/j.comnet.2009.04.013

10.

Yan

Zhang

Zheng

CORE: a coding-aware opportunistic routing mechanism for wireless mesh networks

IEEE Wireless Communications 2010 17 3 96 103

2-s2.0-77954188086

10.1109/MWC.2010.5490984

11.

Han

Zhong

Chen

Chan

Mok

A. K.

Coding-aware multi-path routing in multi-hop wireless networks

Proceedings of the IEEE International Performance Computing and Communications Conference (IPCCC '08)

December 2008

Austin, Tex, USA

93 100

2-s2.0-63049120746

10.1109/PCCC.2008.4745146

12.

Lui

J. C. S.

Chiu

D. M.

DCAR: distributed coding-aware routing in wireless networks

IEEE Transactions on Mobile Computing 2010 9 4 596 608

2-s2.0-77649271928

10.1109/TMC.2009.160

13.

Sengupta

Rayanchu

Banerjee

Network coding-aware routing in wireless networks

IEEE/ACM Transactions on Networking 2010 18 4 1158 1170

2-s2.0-77955776182

10.1109/TNET.2010.2042727

14.

Seferoglu

Markopoulou

Kozat

Network coding-aware rate control and scheduling in wireless networks

Proceedings of the IEEE International Conference on Multimedia and Expo (ICME '09)

July 2009

New York, NY, USA

1496 1499

2-s2.0-70449579170

10.1109/ICME.2009.5202787

15.

Chi

Jiang

Horiguchi

Joint design of network coding and transmission rate selection for multihop wireless networks

IEEE Transactions on Vehicular Technology 2010 59 5 2435 2444

2-s2.0-77953773551

10.1109/TVT.2010.2044429

16.

Hwang

C. S.

Moon

Rate adaptation for wireless network coding using partial overhearing

IEEE Communications Letters 2009 13 12 890 892

2-s2.0-73449105453

10.1109/LCOMM.2009.12.091324

17.

Seferoglu

Markopoulou

Video-aware opportunistic network coding over wireless networks

IEEE Journal on Selected Areas in Communications 2009 27 5 1 16

18.

Seferoglu

Markopoulou

Delay-optimized network coding for video streaming over wireless networks

Proceedings of the IEEE International Conference on Communications (ICC '10)

May 2010

Cape Town, South Africa

2-s2.0-77955398950

10.1109/ICC.2010.5502651

19.

Xuan

Lea

C. T.

Network-coding multicast networks with QoS guarantees

IEEE/ACM Transactions on Networking 2011 19 1 265 274

2-s2.0-79951950095

10.1109/TNET.2010.2062533

20.

Yang

Efficient broadcasting using network coding and directional antennas in MANETs

IEEE Transactions on Parallel and Distributed Systems 2010 21 2 148 161

2-s2.0-75449086088

10.1109/TPDS.2009.44

21.

Asterjadhi

Fasolo

Rossi

Widmer

Zorzi

Toward network coding-based protocols for data broadcasting in wireless Ad Hoc networks

IEEE Transactions on Wireless Communications 2010 9 2 662 673

2-s2.0-76949105496

10.1109/TWC.2010.02.081057

22.

IEEE Standard for Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, 802. 11 Standard, 1997

23.

IEEE Standard 802. 15. 4, Part 15. 4: Wireless Medium Access Control and Physical Layer Specification for Low Rate Wireless Personal Area Networks. IEEE Std. 802. 15. 4, December 2003

24.

Akyildiz

I. F.

Melodia

Chowdhury

K. R.

Wireless multimedia sensor networks: applications and testbeds

Proceedings of the IEEE 2008 96 10 1588 1605

2-s2.0-55549094400

10.1109/JPROC.2008.928756

25.

Video Trace Library http://trace.eas.asu.edu/yuv

26.

The Network Simulator-ns

http://nsnam.isi.edu/nsnam/index.php/Main_Page