A Wireless Video Transmission Scheme Based on MAC-independent Opportunistic Routing &Encoding Protocol

Published Online November 2010 in MECS

• I.    I NTRODUCTION

0.8

Recently, Real-time Video Streaming Service over wireless sensor network (WSN) has caught significant attention in both research and industrial domains. Due to the inherent nature of WSN such as poor link quality, there are still many representative challenges for realtime video streams transmission. Such as limited and time-varying network available bandwidth, large delay due to frequent disconnection and change of video path, higher bit error rate (BER) and high quality and high

This work is supported in part by the Natural Science Found Research Project 60833009 and 60773158

throughput requirements of video streams[1, 2]. In order to transport high-quality video to end user over wireless video sensor network (WVSN) efficiently, many technologies has been proposed such as opportunistic routing and network coding for video transmission.

The idea of opportunistic routing is to exploit spatial diversity to combating the scare spectrum resources and channel variations [3]. Unlike traditional routing schemes which choose the next-hop before transmitting a packet, opportunistic routing allows any node that overhears the transmission and is closer to the destination to participate in forwarding the packet. This result in the high transmission successful probability while data delivering in wireless environment.

R1

R2

S 0.9 R2 0.9D

0.3-----

0.7   *■0.8

Rn

• Figure 1. the theory of opportunistic routing

The basic idea can be illustrated as Figure 1. In this figure, S, Rx and D represent the source node, relay nodes and destination node respectively. The numerals on the lines denote the data successful delivering probability for each wireless link. According to the conventional multi-hop routing, the direct path will be selected to deliver data packets for the minimal hop counts. But the transmission counts expectation is 3.33 to deliver a packet successfully. If we select a path with two hops, such as S-R2-D, the transmission counts expectation can be reduce down to 2.22 for that this two hops path can bring higher throughput and lower error rate than the direct path. For the broadcast nature of the wireless medium, D may receive a part of the data which is sent by S occasionally. It can be used to increase the network utilization. For the packets can be received from different relay nodes, it can be considered as a special multipath routing scheme. Different from the conventional multipath routing protocol, in opportunistic routing, the relay nodes are selected from the set of nodes which have already received the packets but can not be predetermined.

From the basic theory of opportunistic routing, we can see that the shorter path is selected and the packets may be transmitted by uncertain path with disorder sequence. These characteristics of opportunistic routing can be benefit to deliver video data. The shorter path can reduce the transmission distortion and latency. The uncertain path can balance the network loads and nodes’ resource consumption, and it makes the network more robustness.

ExOR and MORE both base on the unit of packets, in contrast, a method of partial packet recovery for wireless networks is described in [6]. The scheme is called Partial Packet Recovery (PPR) system that improves aggregate network capacity by greatly reducing the number of redundant bits transmitted. The key insight is to use information from the physical layer to improve error resilience by two novel techniques: the SoftPHY interface and post-amble decoding. Take both the ideas of opportunistic routing and PPR, a symbol-level network coding for wireless networks is presented in [7]. This scheme incorporates two additional techniques to improve performance: increased concurrency and congestion-aware forwarding.

Streaming video is inherently more challenging than normal data. The tight time constraints of video data and the predicatively-coded property of video data results in different levels of importance across video packets are not considered in the above opportunistic routing protocols. In [8], a time-aware opportunistic relay (TOR) scheme is proposed which operates in the media access control (MAC) layer. To relay video packets in a time-aware manner, a relay deadline is computed for each packet, which is used by relay nodes to determine whether to relay or discard the packet. The authors assume that only one node (the video server) is the traffic source. In [9] a similar scheme that considers multiple video streams is introduced. The authors develop schemes NCV (Network Coding for Video) and NCVD (Deeper) for network code selection and packet scheduling that take into account both (i) the importance and deadlines of video packets and (ii) the network state and the received/overheard packets in the neighborhood. But the schemes have shortage that nodes need to know the contents of the virtual buffers of all their neighbors, in order to code

To further enhance the real-time video quality, a source adaptive frame discard algorithm considering transmission speed and video deadline is presented in this paper. In this algorithm, the historical transmission delay times are recorded to estimate current network speed. Using video deadline, frames predicted to be delayed are discarded adaptively in the source node to get better overall video quality. The simulation results show that this algorithm can significantly reduce frame loss rate and improve video quality.

In some practice application scenarios, there are usually need to deliver multiple video streams over multihop wireless network. It can’t work effectively with the originally MORE protocol in such scenarios. In this paper, we modify the MORE protocol and design an adaptive scheme to support multiple video streams transmission over the multi-hop wireless video sensor network. The simulation results show that our approach can work effectively with multiple video traffics.

The remainder of the paper is organized as follows. Section II discusses the real-time video streaming transmission with MORE protocol. Section III describes the design of SAFDA algorithm. The complexity analysis of SAFDA algorithm is described in section IV. The multi-streaming schedule is proposed in section V. And the performance evaluations of our scheme are presented in Section VI. Finally, Section VII concludes this paper.

II VIDEO T RANSMISSION WITH MORE PROTOCOL

• A.    Data transmission process of MORE

  Based on the network coding technology, MAC-independent Opportunistic Routing & Encoding (MORE) protocol was proposed by Szymon Chachulski etc. in 2007 [5]. The theory of MORE is described as Figure 2. S, R and D represent the source node, relay nodes and destination node respectively. The numerals on the lines denote the data successful delivering probability for each wireless link.

0.5

P1                    P1

P2

Figure 2. the theory of MORE protocol

In the scenario showed as Figure 2, the conventional path will be S → R → D according to the successful delivering probability of links. In wireless communication environment, the nodes near from the destination node may hear the data broadcasting by the source node in a certain probability. For example, while packets P1 and P2 are broadcasting by S, the relay node R can receive P1 and P2 successfully, the destination node D may have received P1 at the same time. In this condition, only P2 need to be sent by R to D. It needs whole schedule to control R to deliver P2 to environment D while using ExOR protocol. For using network coding technology, P2 can be transmitted to D without whole schedule by using MORE protocol. A linear coding result with P1 and P2 (such as P1○+ P2) is sent to D from R. The complete data (P1, P2) can be got successfully at destination node D. In practice, random network coding coefficients are be used in MORE. The network coding result of P1 and P2 may like this: c1 • P1+c2 • P2 , where c1 and c2 are random coefficients.

The transmission process of MORE protocol can be simply described as follow:

• 1)    Before been sent, the source data will be packaged into some packets. Then, a certain amount packets are assembled into a batch. Network coding operation will be executed with this batch.

Pj' = T iCjP. (1)

C = (C ,,..., C .,..., C ,,) is the code vector of the j j1 ji jK result pj ' .

• 2)    Then, the packet head of MORE is added into those coded data packets. The packet head of MORE includes code vector, batch ID, source address and destination address etc.

• 3)    When relay nodes receive a coded packets, it check whether this packet include new information. If it is a new packet, it will be encoded with those old packets in the relay nodes together again through random network coding technology. Then, the coded new packet will be sent from this relay node. For linear encoding manner, the new coded packet is also the linear combination of the native packets.

• 4)    The destination node checks the received packets and discards those packets without new information. The native packets can be reconstructed when enough new coded packets have been received.

• 5)    After reconstructed the native packets, an ACK packet is send back to the source node by an certain feedback path. The ACK packets have higher priority than data packets in MORE protocol.

• 6)    When the source node received the ACK packet, the current batch packets transmission process is finish.

• B.    Video data packed

There are two ways to divide video data into batch packets: constant batch size and variable batch size. The constant batch size dividing method is simple, but this method may divide one frame data into different batch. The variable batch size dividing method is according to the video frame data size to divide different batch. This method can provide one frame data to be divided into the same batch packets.

In our research, we adopt the variable batch size dividing method. The video data is encoded by H.264. The first layer of H.264 coded streams is composed by

NAL unites. We can get every frame data by resolve those NAL unites information. We divide the video data into packets according to the video frame data unite. The detail of video data dividing batch process is as follow:

• 1)    set the batch size expectation value; For example, E(k)=32.

• 2)    If the batch’s size less than the expectation value, add each frame data packets to this batch, till the actual batch’s size exceed the expectation value.

• 3)    Adjust the batch’s size dynamically. When the actual size is more than expectation value, we set the size value which is the nearest to the expectation value as the actual batch size of the current batch. For example, we assume that the current batch size is 20. If the total batch’s size is less than 44 after add the last frame data packets, we set the new batch size as this batch actual size. Otherwise, we give up the last frame data and set 20 as the current batch actual size.

From above steps, we can insure that one frame data would not be divided into different batch, and make the actual batch size near the expectation value.

According to MORE protocol, the source node and the relay nodes encoding those batch packets and transmit the encoded batch packets to the next hop nodes. The destination node decode those received batch packets and get the packet’s head information from resolving the data packets’ head. Form the timestamp and sequence in the packet’s head, the packets’ order in original video sequence can make certain. Then, the received video can be reconstructed.

III SAFDA ALGORITHM DESIGN

The data transmitted by MORE is the network coding results with a group of packets which include a few frames. It is difficult to set a uniform deadline for one packets group for that different frames have different deadlines. On the other hand, the receiver node can not decode the original packets before the packets group transmission finish. In order to adaptive the trait of MORE, we propose a source adaptive frame discarding algorithm which based on the network speed predict and frame deadline. It includes five points as follow: (1) the packets group can not be discarded in advance before the transmission has been finished; (2) the control of frames deadline is at source node; (3) the packets discard algorithm at source node is based on the priority of video frames; (4) the relay times of packets group is controlled by the transmission credit of each video stream; (5) the receiver node set a buffer with certain size.

• A.    A few parameter defination

X is the interval between two frames; a denotes the amount of frame in one GOP; F denotes the i,j first j frame in the first i GOP; Pi,kj denotes the first k packet in Fi, j ; Bi denotes the first i packet group.

In this paper, we assume that one GOP includes one second video data. The first frame is I frame and the others are P frames in one GOP.

• B.    Source node

At source node, the transmission rate is consistent with the average video code rate as much as possible. The first i packets group transmission begins after receive ACK of B i - 1 . The network speed is predicted by the transmission time of the several previous packets group. At the beginning, the source node sends n empty packets groups to the receiver node and recodes the total time T_n ⁰ _B and the packets amount P_n ⁰ _B . After the video packets groups begin transmission, the n previous packets groups’ transmission time and total packets amount are recoded as T_nⁱ_B and P_nⁱ_B .

We assume that the buffer length at receiver node is Nbuftt , and then the increased delay course by the buffer is Nbuf-a • X . We can calculate the relative deadline of each packet in the Fi, j as follow.

> JNb.f«X+^lo(i-T)+(j■ -1)), I > N,+1

D "I       «         , i < N bf + 1 ™

The absolute deadline of each packet in one frame can be expressed as (3).

t D "  t start + D ( P J                      (3)

Those frames in duration ( N buj tt + 1) • X can be received success with no deadline limited. The deadlines of frames behind the buffer length are calculated by the equation (1). The packet deadline will be saved in the packet head.

The current time express by tnow , and the packet deadline is tD , when it meet the following conditions (4), and the frame type is P, we select this packet as one packet of Bi . Otherwise, this packet will be discarded.

P T^{l - 1}

t now + -TT n b <"  t D + ^A t                  (4)

PnB

If this frame is an I frame, it will be kept and the adjacent several P frames will be discarded. The amount discard packet can be calculated by (5).

P T i ^{- 1} t now + "рД - ( t D +A t )

N discard "----------------------- (5)

A t is the adjust parameter, which control the calculation range of packet deadline.

• C.    Relay node

The relay frequency of packets group transmission is determined according to the transmission credit (TX_credit) in MORE protocol at relay nodes. The TX_credit describes the relay frequency limitation of packets group. It can be calculated as (6). With TX_credit, the relay frequency can be controlled without global scheduling.

z

TX credit = —---- ¹ ------ (6)

¹ У z, (1 - e ,)

Z—l j > i j v Ji'

In this equation, z_i denotes the packet relay frequency at relay nodes and e_ji is the packet loss rate form node j to node i .

• D.    Receiver node

The received packets groups are decoded by the order at receiver node. If there are any discarded frame is funded in the decoded sequence, the previous frame is used to take place the discarded frame. A packet buffer is maintained at received node at the same time. The amount of frames in the buffer is N buj tt . The video begin playing after the buffer is full.

IV T HE COMPLEXITY ANALYSIS OF SAFDA ALGORITHM

• A.    Time complexity

According to the algorithm description, the packet deadline needs only a little simple calculation at source node. So the time complexity of SAFDA algorithm is a constant level. But on the relay nodes, it is need to calculate the transmission time by iterative method. We assume that the amount of network nodes is N ， the time complexity is O ( N ² ) according to the MORE protocol. For the multi-streams application, we assume that the amount of streams is F ， the time complexity is O ( FN ²) .

• B.    Space complexity

The space requirement of the SAFDA algorithm focus on two aspects: 1) it is needed to preserve n historical packet groups to estimate the current network speed at source node; 2) the buffer size at receiver node ^is N buf ^a .

• C.    Algorithm parameter settings

There are three main parameters in SAFDA algorithm:

• •   A t : The control parameter of packet deadline

calculation. In usually, the value of A t is greater, the decision of packet drop time is more loose. Note that, the value of A t may be a negative value.

• •    N_buf : The size of GOP buffer in receiver node. The size of the buffer is bigger; the frame loss rate is lower.

• •    n : The amount of packet groups used to estimate the current network state. The value is greater, the more historical conditions of network

V MULTIPLE STREAMS SCHEDULE

The originally MORE protocol can not work effectively to support multiple video streams application scenarios. In order to improve the multiple video streams transmission performance, we modify the MORE protocol and design an adaptive scheme to support multiple video streams over multi-hop wireless video sensor network in this section.

There are four methods to schedule multiple video streams in our research, simple cycle scheduling, optimized cycle schedule, sequence priority scheduling and the balance scheduling based on feed-back.

The simple cycle scheduling method assigns equal time strip for each video stream. Streams are delivered in their time strips turn by turn. This method is simple and easy to implement. It can provide the fair chance for each stream. But this method can not adapt to the income packets variety. If there is no new incoming packet, the time strip would be wasted. So, the efficiency of this method is low.

In order to improve the efficiency of the simply cycle schedule, we propose the optimized cycle scheduling method. We check the stream first whither it has new income packets before it’s time strip come turn. If there is no new income packet, we set this stream as no-active stream and skip it. Otherwise, this stream be sent in it’s time strip. This method can avoided the time strip be wasted effectively.

In the sequence priority scheduling method, we set different priority for each stream based on its packet sequence which has been send successfully. The higher sequence id has the lower priority to be scheduled. The higher sequence id represents that this stream has been sent more packets successfully in the past. We give more schedule chance to those streams which have more packets wait to be sent.

The design of above schedule methods focuses on the relay nodes. There only consider their income batch packets states on the relay nodes. The destination node received state is ignored which will lead to blindfold schedule. In our experiment, we often find that there only one or two streams can be replayed fluently while the other streams being replayed brokenly. In order to solve this problem, we design a novel balance schedule method based on the feedback from destination node. With this schedule method, the received batch packets during the recently past time span are recorded at the destination node and the amount of the received packets for each stream can be counted. The values recorded by the destination node are feedback to the source node with the ACK packets. The relay node also records the packet amount which has been delivered successfully recently. The values recorded by relay nodes are compared with the values in the ACK packets. Then we set higher priority for the stream which has lesser packets been received successfully by the destination node. It can make the transmission balance among the different streams as soon as possible with this schedule method. On the other hand, this method will bring several bytes additional burden for ACK packets.

In the next section, we compare the transmission performance among the four schedule methods above. From the experiment results, we can see that the balance schedule based on feedback can get better effect for multiple video streams schedule.

VI PERFORMANCE EVALUATIONS

In this section, we evaluate the SAFDA algorithm performance by simulation and compare it with the original MORE protocol. In our simulation, we consider two scenarios: 1) single video steam transmission; 2) multiple video streams transmission. We also compare the transmission performance among the four schedule methods described in the section V.

• A.    Single video steam transmission

  We select the foreman_2000.264 as the test video sequence, which contains 300 frames, duration 12 seconds. The frame size is GIF (352x288), the length of GOP is 25, the code rate is 2000Kbps and the average amount of packets in a frame is 5.2. In order to ensure the packets of a frame to be divided into a same packets group, the length of a packet group is set dynamically. In our experimentation, the packet groups divided mode includes three different types: k=var32 ， k=var48 and k=var64.

Figure 3. The video PSNR value with and without SAFDA

Figure 4. The subjective qualities of reconstructive video

We compare two scenarios in our simulation: with and without SAFDA algorithm. The parameters of SAFDA are set as At = 0 , Nbuf = 0 , n = 1 . After the packets groups arrive at the receiver node, those packets which arrive time before deadline are kept and the others are discarded. The discarded frame is replaced by the previous frame. The simulation results are showed as Fig.3.

From the Fig.3, we can see that the value of PSNR of received video can improve about 15db with SAFDA than without SADDA for MORE protocol (where k=var64). The comparison of subjective qualities of reconstructive video sequence at receiver node is showed in Fig.4. The left two pictures are the first 100 frame and the first 250 frame in the reconstructive video sequence with SAFDA. And the right two pictures are the corresponding frames in the reconstructive video sequence without SAFDA. We can see from Fig.2 that the picture quality with SAFDA is better than the old one obviously.

• B.    Multiple video streams transmission

For the multiple video streams transmission scenario simulation, we consider two flows and three flows at different network conditions (high speed and normal speed). We set the packet group divided mode as k=var64. And the parameters with SAFDA are set as A t = 0 , N buj = 0 , n = 1 . We compare the fame loss rate between the MORE protocol with and without SAFDA algorithm. The simulation results are showed as Fig.5. In this figure, the circle points denote the frame loss rate with SAFDA; the triangle points denote the frame loss rate without SAFDA and the red line express the frame loss rate which is calculated according to the idea frame loss rate relationship. From this figure, we can see that the frame loss rate with SAFDA is close to idea result. The reconstructive video sequences of each flow can be improved much more by the MORE protocol with SAFDA algorithm in multiple flows application scenario.

Figure 5. The fame loss rate with and without SAFDA

• C.    The influence of A t and N_bu f

In order to study the influence of At and Nbuf , we also carry out a set of simulations with different values of At and Nbuf . For Nbuf , we take a value every 0.1. We take the value of At from (-1.00, 1.00) for each value of Nbuf . The value of n is fixed as n = 1. We recorder the frame loss rate for each combination of At and Nbuf .

If a frame can not be received by receiver node before deadline, it will be discarded. The results are showed as Fig.6. Different color lines express different value of N buf .

Figure 6. The influence of ^A t and N buf

From Fig.6, we can see that the frame loss rate decrease with the value increasing of N_buf . At the same time, the lowest frame loss rate have relationship with the combination of A t and N_buf . We find that the relationship between N_buf and A t is nearly linear relationship through data fitting. The fitting equation ^likes N buf = ^-A t .

• D.    Performance of multiple video streams schedule

In our experiment, we compare the performance of multiple streams schedule method with throughput rate, delivery ratio, delay, jitter, and the batch packets variance of mean. The experiment results are show as Figure 7~10 respectively.

Figure 7. Packet throughput with different flows

From Figure 7, we can see that the throughputs of the four schedule methods are like to be equal with two flows. The throughtput value increase with the flows amount added. But the throughput value of simple cycle scheduling method increase at first and drop down rapidly as the flows amuout reachs 5. The reason is that the simply cycle scheduling method is more easily lead to network congestion than the others methods. On the other hand, we can see from Figure 7, the feedback balance scheduling method can get better transmission balance among multiple flows by utilizing historic information of the relay nodes. The throughput variety is not sensitive with the increase of video flows amount.

From Figure 8, we can see that these four scheduling method have little influence to the delivery ratio of multiple video flows when the total network loads lower than the network bandwidth. As the total loads exceed the network bandwidth, the other three scheduling method can get higher packets delivery ratio than the simple cycle scheduling method. The feedback balance scheduling method gets the best performance among them.

Figure 8. Packet delivery ratio with different flows

Figure 9. Packet delay with different flows

Figure 10. Packet jitter with different flows

In Figure 9 and Figure 10, the delays of these four secheduling method increase with the video flows added. As the total network loads exceed the bandwidth, the delay and jitter become larger vehemently for the simply cycle scheduling method than the other three methods.

The batch packets variance of mean can reflect the transmission balance level among multiple video flows. The value is littler and the balance level is better. From

Figure 11, we can see that the feedback balance scheduling method can get the best balance performanc among these four scheduling methods. The sequence priority scheduling method gets better balance performance than the optimized cycle scheduling method. The simply cycle scheduling method is the worst among the four methods in balance performance.

Figure 11. The batch packets variance of mea n with different flows

VII C ONCLUSION

The real-time video streaming over WVSN is a difficult problem to be resolved. The latest Opportunistic routing protocol MORE, which can fully exploit spatial reuse of WVSN and randomly mix packets with network coding before forwarding them, performs much better than traditional protocols in throughput. It is suitable for video streaming transportation in WVSN. But the original protocol must be modified to support the time constraints of video data. The minimum transmission unit is packets group in MORE protocol. The bigger of packets group size, the higher throughput can arrive. On the other hand, the bigger size of packet group will lead to the frame end-to-end delay increase obviously. Addressing this problem, we propose a source adaptive frame discard algorithm (SAFDA) to reduce the delay and improve the reconstructive video quality based on network speed prediction. Some less important video frames are discarded at source node when the transmission rate is lower than the video code rate. For the multiple video flows application scenarios, we also propose four scheduling methods for multiple video flows with MORE protocol over WVSN. In our experiments, the performance of throughput, packet delivery ratio, delay, jitter, and the batch packets variance of mean are compared. The results show that the balance scheduling based on feedback method can get the best performance among these four methods.

A CKNOWLEDGMENT

This work is supported in part by the Natural Science Found Research Project 60833009 and 60773158 which mainly content is real-time video transmission in wireless sensor network.