A novel cross-layer design using comb-shaped quadratic packet mapping for video delivery over 802.11e wireless ad hoc networks

The existing video coding standards are dominated by two tracks: the ITU H.26x family and the ISO/IEC MPEG-x family [16]. H.261 was mainly proposed for video conferencing, MPEG-1 for VCD, H.262/MPEG-2 for DVD and DVB, MPEG-4 [17] for low-bit-rate video streaming, and H.264/MPEG-4 AVC [18] for high definition TV. In recent years, scalable video coding [19] for scalable video streaming over heterogeneous networking bandwidths or terminal displays and multi-view video coding [20] for stereoscopic video/3D or free-viewpoint TV have become the main streams of research interest and may generate promising applications.

To achieve a better rate-distortion, i.e., better quality for a given bit rate or lower bit rate for the same quality, the general trend for advanced video coding is to increase the complexity of the coding algorithms, including spatial prediction intra a video frame and temporal prediction inter video frames. If a video frame referenced by other video frames for decoding is lost, it will cause error propagation to those frames, and may make them undecodable unless the lost video frame is error concealed. In general, there are three types of coded video frames: I (Intra-coded) frames, P (Predictive-coded) frames, and B (Bi-directionally predictive-coded) frames. In order to shorten or stop the error propagation, a periodic Group of Pictures (GOP) structure should be adopted.

Figure 3a demonstrates a typical GOP structure with a period of nine video frames (i.e., IBBPBBPBB), where the predictive dependences among the I/P/B video frames are illustrated. The simplest importance level of the I/P/B frames is: I > P > B. The reasons are given as follow. (1) The I frame is intra-coded and its decoding is independent of other frames, but it is referenced by its succeeding P and B frames within the same GOP structure; the loss or damage of a I frame can cause a serious error propagation to its subsequently received P and B frames and make them undecodable unless error concealed, and thus the I frame is the most important one. (2) The P frame is uni-directionally predictive-coded and its decoding needs to reference its preceding I or P frame, and it is also referenced by its succeeding P and surrounding B frames; thus, it should take the second place in the importance level. (3) The B frame is bi-directionally predictive-coded and its decoding needs to reference both its preceding and succeeding I or P frames, but it will not be referenced by other video frames, and thus it causes no error propagation and should be marked as the least important one. This simple I/P/B frame importance scheme was adopted by both AM [14] and EAM [15] in their cross-layer design frameworks. However, it is obvious that such a simple video frame importance scheme ignores the potential importance differences among P frames, since the loss or damage of a P frame may potentially cause a specific error propagation, the effect of which depends on its frame position in the GOP.

A further importance classification scheme among P frames called EPL has been proposed in [21]. Figure 3b demonstrates the basic idea of EPL for the {IPPP...} GOP patterns with periods of 9 and 12 video frames, where the video importance indexing for each video frame is quite straight forward: I is still the most important one, and the earlier position a P frame is located within a GOP, the more important it is. However, they did not apply the EPL concept to the scenario of 802.11e.

The objective of 802.11e EDCA and the service differentiated classes of ACs (voice, video, generic data) have been well described in Section 1. Figure 1 shows the priorities of these ACs, from high to low, where AC[3] has the highest one and AC[0] has the lowest one. The higher priority an AC has, the shorter delay and random backoff time for channel access it would be assigned with. The priority of each AC is assigned based on its QoS requirements using a set of four parameters (AIFS, CW_min, CW_max, TXOPlimit). Collisions among the ACs of an 802.11e QoS Station (QSTA) are resolved by its virtual collision handler. A better assignment of these parameters can lead to a more efficient transmission performance through these ACs [22‐24]. Table 1 lists the values of the parameter sets for all the ACs of 802.11e EDCA.

Figure 2 shows the virtual collision resolution among the ACs of 802.11e EDCA. Immediate access can be granted for the transmission attempt of any AC[n] queue (n = 0, 1, 2, 3) only after the medium is idle longer than AIFS(AC[n]). In case of busy medium, a fixed time interval plus a random backoff time is needed before AC[n] can transmit a packet. AIFS(AC[n]) is the minimum time interval after which the QSTA detecting the idle channel can start a random backoff timer chosen from [0, CW(AC[n])] for collision avoidance among ACs. For each channel access attempt, CW(AC[n]) is initialized to CW_min(AC[n]) and the random backoff timer starts to count down in units of slot when the channel is free for one AIFS. The station starts to transmit when the backoff timer reaches zero and the channel is still idle. If unsuccessful, CW(AC[n]) is doubled for another channel access attempt until up to CW_max(AC[n]). TXOPlimit(AC[n]) is the maximum duration which allows the QSTA to transmit a burst of MAC frames without entering another channel contention period. Notably, as shown in the last column of Table 1, AC[2] (video) has a longer TXOPlimit than AC[3] (voice), whereas the zero values of TXOPlimit for both AC[1] and AC[0] represent that the QSTA can only transmit one MAC frame in a new contention period.

To address the performance limitation issue of 802.11e, Ksentini et al. [13] proposed a QoS cross-layer framework to exploit both the application layer and the 802.11e MAC layer features. In their work, data-partitioning for H.264 video source and packet marking in NAL (Network Abstraction Layer) were applied in the application layer, and the SM algorithm assigned these packets to different ACs of 802.11e EDCA in the MAC layer based on their marked priorities. Their results showed that such a cross-layer design with further differentiation among video packets could provide a better quality than EDCA, where video packets are all mapped together into a single AC, namely AC[2]. As aforementioned, both the EDCA mechanism and the SM algorithm assumes that all the ACs are FIFO based, thus not AQM based, and this may lead to a dramatic video quality degradation in heavy network congestion.

To address this issue, instead of mapping prioritized video packets into different ACs, Lin et al. [14] proposed the AM algorithm based on the priorities of video packets. According to the queue length of AC[2], denoted as QL₂, AM can probabilistically determine whether the prioritized video packets should enter AC[2] or other lower-priority ACs, namely AC[1] or AC[0]. In terms of queuing discipline, AM can be viewed as a variant of WRED (Weighted Random Early Detection) [25], which is AQM based and widely deployed in broadband backbone core routers to realize differentiated services by using different low queue thresholds, denoted as threshold _low , within a single physical queue, where its total physical queue length is considered to determine the differentiated packet drop-probabilities. Likewise, to support service differentiation for prioritized video packets in the AC[2] of 802.11e, AM adopts the total physical queue length of AC[2] to determine the differentiated downward-mapping-probabilities of video packets; however, unlike WRED, AM uses the same pair of (threshold _low , threshold _high ) for all prioritized video packets but different mark probabilities, i.e. probabilities when QL₂ is approaching threshold _high from the low side, or denoted as MaxProb _I/P/B , to determine the differentiated downward-mapping-probabilities to AC[1] or AC[0]. In other words, each prioritized video packet type follows a specific RED function of QL₂ and the corresponding MaxProb _I/P/B in AM.

As shown in Figure 4, for each RED function in AM, there are three downward-mapping or downward-transition periods: (1) Zero Transition (QL₂ ≦ threshold _low ), (2) Linearly Proportional Transition (threshold _low < QL₂ <threshold _high ), and (3) Full Transition (QL₂ ≧ threshold _high ). The highest-priority video packet is the most preferred one to enter AC[2], and the lowest-priority one has the highest chance to be downward mapped into other lower-priority ACs. In [14], MPEG-4 video source files were analyzed, and video packets were classified according to their I/P/B types, with priorities from high to low for simplicity. The authors of [14] also applied the same experimental setup for SM and EDCA, and their results showed that AM outperforms both SM and EDCA.

The authors of [15] proposed an enhanced version of AM (EAM) in the H.264 coding scheme, where the same AQM was applied to AC[2] with a different set of low and high thresholds for the queue length of AC[2], and a more subtle consideration was given to those downward-transitioned video packets into AC[1] or AC[0]. Instead of a fixed probability for going to AC[1] or AC[0], EAM further considered the traffic condition of AC[1] to determine the destiny of those downward-transitioned video packets, and the underline principle is to allow these video packets make the best use of AC[1] unless it is too congested, since AC[1] has a better resource for channel access than AC[0]. Unfortunately, they only showed that the performance of EAM was better than EDCA. Neither various traffic effects were studied, nor a direct performance comparison between EAM and AM was given.

Mai et al. [26] proposed another extreme idea that goes back to the original case of EDCA where all the ACs are FIFO based, namely they did not rely on finding a good AQM to enhance the video transmission quality. Instead, when a video packet arrives at MAC, any AC queue which has the shortest estimated delay time among all the ACs will be selected to serve the video packet. However, such a selection among all the ACs involves complicated queue delay time calculations for all the ACs, since they always mutually affect each other.

The concept of DVFI is based on the PSNR degradation due to the transmission loss of a single video frame. In general, it contains two effects: (1) imperfect error concealment (IEC) on the lost video frame itself; and (2) error propagation (EP) to those successfully received surrounding video frames which will be decoded by referencing the lost video frame. The principle for determining the importance level of a video frame is that the more PSNR is degraded due to a lost video frame, the more significant the lost video frame is.

The video-frame-based PSNR is defined in (1), where a frame size of M × N pixels is assumed, and ( f i , j - f i,j ′ ) stands for the luminosity difference per pixel due to the video quality degradation. Note that the most degraded part of PSNR usually occurs in the luminosity, and this is also adopted throughout the rest of the article.

The objective of the proposed CQM algorithm is to find a good AQM-based video packet mapping algorithm among ACs in the 802.11e MAC layer that can make the best use of the DVFI scheme for video packet importance so as to achieve further video transmission quality enhancement over the existing works. The CQM achieves this objective via the following two principles.

In our proposed CQM algorithm, Principle 1 can be achieved by forming multi-branched and comb-shaped downward transition probability functions for video packets based on the queue length of AC[2], denoted as QL₂, as shown in Figure 8. Like AM and EAM, each branch (say branch i) of probability function in CQM is also characteristic of one pair of low (L) and high (H) thresholds, (th _L [i], th _H [i]), which separates the downward transition for DVFI group i into three phases: (1) Zero Transition (QL₂ ≦ th _L [i]), (2) Quadratically Proportional Transition (th _L [i] < QL₂ <th _H [i]), and (3) Full Transition (QL₂ ≧ th _H [i]). However, the CQM is unique and novel based on the following:

More details of the CQM algorithm, including Principles 1 and 2, can be found from the pseudo code of CQM, as given in Figure 9. This pseudo code consists of a step function for I frames which merges threshold _high and threshold _low together at maximum _AC[ 2]_buffer _size - 1 (in units of packet) and a comb-shaped structure of five-branch functions for P frames. This can be clearly seen if the input argument packet _type in the function call to DVFI _CQM(...) is carefully understood. The function call to Min _Delay() implements the idea of Principle 2, where the minimum delays of AC[1] and AC[0] can be estimated based on the following concept: the delay time of AC[i] is proportional to a ratio R, as defined in (3).

where QL(AC[i])) is the queue length of AC[i] and it is assumed that no retry is allowed for AC[i] if unsuccessful channel access occurs due to collision. Thus, the item CWmin(AC[i]) 2 reflects the average delay time contributed from the random backoff timer chosen from [0, CW_min(AC[i])]. Other studies such as the shape of the comb structure and the branch multiplicity, in terms of symmetric and asymmetric combs as well as five and ten branches, can be found in Section 4.

The following simulation setup was established in this study. Eight YUV reference video sequences [27] were adopted for testing, with half of them in the QCIF (176 × 144) format and the other half in the CIF (352 × 288) format. Table 2 lists these eight video sequences and marks their levels of motion to explain why they can be representative, where the numbers of video frames of these video sequences are also summarized, including total, I, and P frames.

These video sequences are encoded into H.264 (JM10.2) bit streams based on a GOP structure of {IPPP...} with periodic lengths of 9 or 15 video frames (denoted as GOP = 9 or GOP = 15) and a frame rate at 30 Hz, and packetized with the maximum transmission packet size of 1000 bytes over an 802.11e ad hoc network, as shown by the topology in Figure 12. To simplify the error propagation effect and confine it within a GOP, the number of reference frames N_ref is adopted to be 1. Note that N_ref is a new feature of H.264, but it is in general quite time-consuming and does not help much in coding efficiency unless for periodic motions. Furthermore, the error propagation could become more complicated if N_ref > 1, where error propagation might go beyond one GOP size. The EvalVid multimedia framework [28] integrated with the ns-2 network simulator [29] was used to provide the H.264 video streaming [30] over an ad hoc wireless network simulation environment, where the DSDV routing protocol was used and the adopted data rate of the wireless link was 1 Mbps. Four ad hoc nodes were setup, where one served as a video server and another as a video client with cross traffic flows established among both the connections (Node 1 → Node 2) and (Node 3 → Node 4). Table 3 defines six congestion cases of cross traffic, where Case n (n = 1, 2, 3, 4, 5, or 6) stands for, on each connection, n flows of cross traffic in voice (64 kbps per flow), UDP (10 kbps per flow), and TCP (not characteristic of constant-bit-rate, but featured by self-congestion-control in variable-bit-rate) are, respectively, established through AC[3], AC[1], and AC[0] of the traffic sender nodes.

As aforementioned in Section 3.1, the priority of a video packet is determined according to (2), i.e., the DVFI value of its associated video frame. Since this study primarily adopted the H.264 coding scheme with a periodic {IPPPPPPPP} (GOP = 9) pattern, it is interesting to see the DVFI distribution in terms of both I and P packets. The DVFI distribution certainly manifests itself as a much more precise priority scheme for video packets, compared to the two-level-priority scheme (denoted as I/P). The {IPPPPPPPPPPPPPP} (GOP = 15) case is also presented here to see how the GOP length affects the DVFI distribution. Figures 10 and 11 show the DVFI distributions of Foreman sequence coded with bit rate (i.e., IR) = 128 and 512 kbps, respectively, in two YUV formats (QCIF and CIF) and GOP lengths ({IPPP...} of GOP = 9 and GOP = 15). Two observations can be clearly seen as follow.

In addition to the Foreman sequence, the other selected video sequences have also been checked, and they all generated similar distributions and observations.

Recall that the grouping issue of DVFI in Section 3.1.2, i.e., the video frames in a test video sequence can be segmented into N + 1 groups based on both the absolute order of their DVFI values and the equal population of video frames, i.e., N prioritized groups of P frames and 1 top-priority group of I frames. To match with the CQM packet mapping algorithm in the MAC layer, there should be accordingly N + 1 branches of mapping probability functions in CQM, i.e., comb-shaped functions of N branches (i.e., the comb's branching multiplicity) for P packets, and 1 step function for I packets. More details about the comb's shape and the threshold effects are given below.

The objective of understanding the performance effects due to the comb's shape and threshold settings of the proposed CQM algorithm have been well motivated in Section 4.1.2, where four case studies (SC-5B, AC-5B, SC-10B, AC-10B) have also been well defined. Figure 13 presents a combined view of the results based on these comb shapes and threshold settings under various tests of video input rates and congestion cases of cross traffic, the definitions of which can be found in Section 4.1.1. These results are based on the average PSNR of the Foreman QCIF video sequence, and they deliver the following messages.

Recall from Section 3.2 that the major principles of the proposed CQM packet mapping algorithm are to keep more important video packets in AC[2] to make the best use of its resources for better channel access while taking good care of those less significant video packets by choosing a better one between AC[1] and AC[0] which has a shorter queue delay time. It is thus interesting to see how the queuing effects of all the ACs support these design principles.

To follow the discussions in the previous section, it is convenient to take the Foreman QCIF sequence as an example, considering various video input rates and congestion cases of cross traffic. Let us start with observing the queue length of AC[2], or QL₂(t) for short. Figure 14 shows QL₂(t) of two typical video input rates, i.e., IR = 512 kbps and IR = 128 kbps, with the same congestion case of cross traffic (n = 4). Such a combination of IR and n can reinforce the main concept of Section 4.1.1, namely the same congestion case of cross traffic (n) could mean very different congestion levels of AC[2]. As shown in Figure 14, it is clearly seen that, in the case of IR = 512 kbps, all the QL₂(t) curves of different mapping algorithms are congested in different levels (from medium to high) and the congestion level of the proposed CQM algorithm is the minimum, and thus meets the goal of the design principle for AC[2], i.e., Principle 1, as explained in Section 3.2. Besides, it is also seen that the other AQM-based algorithms (EAM and AM in different thresholds settings) do perform better than EDCA (non-AQM-based). On the other hand, in the case of IR = 128 kbps, n = 4 still means very low congestions of AC[2] in all the mapping algorithms, and actually these QL₂(t) curves merge into the same one because none of them ever exceeds the lowest value of threshold _low , namely every AQM-based mapping algorithm behaves just like EDCA.

Figure 15 gives the time-averaged queue length of all the ACs as a function of n in the same video input rates, i.e., n ranges from 1 to 6 for IR = 512 kbps and from 1 to 8 for IR = 128 kbps, based on the same reasoning mentioned previously. For AC[2], both the IR cases again support the idea of Principle 1. For Principle 2, the Minimum-Delay-Time selection rule between AC[1] and AC[0] does show its effects in both the IR cases, as summarized below.

To understand more about the performance issue, PSNR-based performance evaluations can provide a much more intuitive way for comparison. To fully support the superiority of the proposed cross-layer design (DVFI+CQM), the existing frameworks with various threshold settings (as defined in Section 4.1.2) together with EDCA are compared under the combined test conditions of IR and n (as defined in Section 4.1.1).

Firstly, to see the impact of the GOP length to the PSNR performance, let us re-run the GOP = 9 and GOP = 15 cases for both Foreman CIF and QCIF. The results are summarized in Figures 16 and 17, where the following messages can be delivered.

To gain more understanding on the potential correlation of the PSNR-based performances to the DVFI distributions and mean values of lost I and P packets, we propose a novel performance metric called WPR, as defined in (4), to reason the influence by the relative distributions of I and P frames.

where the numerator N _received (I &P) is total number of received I and P packets, and the denominator w _I M _I + w _P M _P is the sum of the weighted DVFI means of lost I and P packets, with M _I being the DVFI mean of lost I packets and M _P being the DVFI mean of lost P packets, both of which are weighted by w _I and w _P , i.e., the ratio of lost I packets to the total number of lost video packets, and the ratio of lost P packets to the total number of lost video packets, respectively. The basic idea of WPR is that it presents a better video transmission quality when N _received (I &P) is large, and w _I M _I + w _P M _P is small. This idea makes a perfect sense, and it is not proposed to replace PSNR, but to provide a tool to observe how well both DVFI and CQM perform in the proposed cross-layer framework. Figure 18 shows a clear correlation between PSNR and WPR in the case of Foreman QCIF and GOP = 9. It is seen that WPR follows similar performance patterns as n increases for the various test frameworks in all the IR cases. We have conducted the same tests on the other video sequences, including Foreman CIF, Carphone (QCIF and CIF), News (QCIF and CIF), and Mother-&-Daughter (QCIF and CIF), and similar conclusions have been obtained. These results show a common conclusion: the design principles (recall Principles 1 and 2) have been well implemented in the proposed DVFI+CQM framework. Now, let us go one step back and concentrate on the PSNR-based performance evaluations for all these video sequences both in QCIF and CIF, and recall that they are chosen for test since they represent different motion levels: Foreman stands for a fast video, Carphone for medium-fast, News for medium-slow, and Mother-&-Daughter for slow. Figures 19, 20, and 21 summarize the performance evaluations for the latter three video sequences in both the QCIF and CIF formats. A consistent message from the performance evaluation of all the test video sequences can be delivered as follows.

Table 6 further gives the largest PSNR gains (dB) of the proposed DVFI+CQM framework over the existing ones among different congestion cases of cross traffic for the four input rates of video source (IR = 128, 256, 384, and 512 kbps) in all the test video sequences both in QCIF and CIF. The largest gains over the best existing framework I/P+EAM[10/45] range from 0.5 to 3.1 dB, and the ones over EDCA range from 2.2 to 5.3 dB.