{'fraction_non_alphanumeric': 0.030328303889604974, 'fraction_numerical': 0.007089241034195163, 'mean_word_length': 4.607780612244898, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An analytic study of a distributed EDCA-based QoS mapping for layered video delivery in WLAN

One of the key challenges in multimedia networks is video delivery over wireless channels. MRC (Multi-Resolution Coding) Layered video, divides video into a base layer and multiple enhancement layers. In this paper, we aim to improve video quality, impacted by high channel contention, through mapping individual video layers to EDCA (Enhanced Distributed Channel Access) access categories in order to maximize the average number of reconstructed video layers. We propose an adaptive cross layer video layers mapping technique that optimally enhances the QoS of wireless video transmission over IEEE 802.11e EDCA priority queues. The optimization is based on a dynamic program that takes into account the EDCA parameters and the layered dependency nature of layered video delivery. Our proposed technique makes use of a channel delay estimation model and an estimation of average video useful layers delivered. The optimal mapping strategies are selected by an optimization module based on the information from the analytical model. The accuracy of our optimized mapping technique performance is verified through extensive simulations. The obtained results illustrate significant trade-off between complexity and delivered video quality for canonical mapping schemes.


Introduction
The requirement of high video delivery quality over wireless networks is increasing day-by-day. Layered video, scalable video, and multiple resolutions coding (MRC), all refer to encoding techniques that fragment a video stream into a base layer and enhancement layers [14]. The base layer is necessary for decoding the video stream, whereas the enhancement layers improve its quality. This approach is useful for wired multicast, where a receiver with a congested link can download only the base layer, and avoid packets from other layers. With wireless, all layers share the medium. Thus, the enhancement layers reduce the bandwidth available to the base layer and further reduce the performance of poor receivers. The Quality-of-Service (QoS) of 802.11e [15] is achieved by providing different classes of frames with different priorities when accessing the radio channel. In the basic EDCA scheme, the video traffic is mapped automatically to two access classes. In this paper, we describe a distributed and adaptive cross-layer dynamic mapping techniques that map the arriving video packets into different EDCA Access Categories (ACs) to optimize layered video delivery by maximizing the expectation of the number of video layers received.. The remainder of this paper is organized as follows. We devote Section 2, for reviewing some related works from the literature for enhancing video delivery in wireless networks. Our proposal will be described in Section 3. We provide a deeper analysis of the main obtained results in Section 4. Section 5 summarizes the paper and outlines the future works.

Related Works
Many works have been presented in the literature to enhance video delivery in wireless environment. They described many features based on rate allocation, channel quality estimation, retry limit adaptation, queue length estimation..etc. In [7] the cross-layer QoS-optimized EDCA adaptation algorithms take into account the unequal error protection characteristics of video streaming, the IEEE 802.11e EDCA parameters and the lossy wireless nature. It makes use of two models, video distortion model and channel throughput estimation model to predict the video quality. The convex nature of optimization problem remains an open research issue. The work of rate allocation becomes challenging since heterogeneity exists in both the rate utilities of video streams and in wireless link qualities. In distributed manner the task can be performed, as many times the system lack centralized control. In [3], an optimization framework to distribute video rate allocation over wireless is proposed, taking into account this challenge. In [11] the authors investigate the packet loss behavior in the IEEE 802.11e wireless local area networks (WLANs) under various retry limit settings. Considering scalable video traffic delivery over the IEEE 802.11e WLANs, the presented study shows the importance of adaptiveness in retry limit settings for the Unequal Loss Protection (ULP) design. Based on the study, they present a simple yet effective retry limit based ULP which adaptively adjusts the retry limit setting of the IEEE 802.11e medium access control protocol to maintain a strong loss protection for critical video traffic transmission.
A new packet scheduler in cross layer environment for GSM/EDGE systems to improve QoS support of multiclast data services is proposed in [5]. The algorithm minimizes a prescribed cost functions given the current channel qualities and delay states of the packets in the queue. A cross-layer optimization for video streaming over wireless multimedia sensor networks is attempted in [4]. In 802.11s mesh networks, packets are differentiated and higher priorities are given to forward packets. When queue length of AC2 fills up, forward packets are remapped to lower access category AC3.
Weighted Fair Queuing [8] is efficient for wireless channels. It assigns weight for different flows and calculates the departure time based on the weights. Assigning weight to the individual flows helps in prioritizing the video packets and sending the packets in the flow which has more weight.
Forward Error Correction [9] is used to reduce the number of packets lost. This is done by adding redundant number of packets to the video sequences. The challenge is to add optimum number of packets suitable for both channel availability and queue length. An adaptive video packet scheduling algorithm used in WLAN is proposed in [10]. The data transmitted over the wireless channel should be reduced as much as we can consider of the limitation of wireless bandwidth, but not the video-quality. If the network load becomes higher and higher, the access point must compare the multiple video streams and find which one should be transmitted first. Unlike previous works, this paper addresses a simple and adaptive distributed mapping strategy based on EDCA access scheme. We describe an analytical model for selecting the best strategy to map video layers to each AC in order to maximize the reconstructed video layers taking into account the wireless channel contention model and the video layer dependency.

System Model
In this Section we describe in details our analytical model for wireless layered video delivery. Our solution is fully distributed as in [17]. It is based on EDCA mechanism, witch provides a differentiated, distributed access to the medium using different priorities for different types of traffic [15]. We consider a layered video source encoded into a base layer which contains the most important information, and enhanced layers that provide additional information for better video quality. We assume that the video layers have the same constant bitrate. Our aim is to select, from exhaustive search results, the best mapping strategy of video layers to different EDCA ACs, which decreases the dropping probability and improves the expected number of useful layers delivered to the destination, regarding different settings of EDCA parameters and traffic load.
Basically, an EDCA channel access function uses Arbitration Interframe Space (AIFS[AC]), Contention Window with its minimum and maximum value CW min [AC] and CW max [AC] respectively instead of DIFS,CW min andCW max , of the DCF (Distributed Coordination Function) respectively, for the contention process to transmit a packet that belongs to AC. These parameters can be used in order to differentiate the channel access among different priority traffic. The channel access priority goes from AC 4 , AC 3 , AC 2 , up to the highest priority AC 1 . As the priority of the AC increases, the values of the MAC parameters become smaller. Thus the AC with the shorter contention period has more priority to occupy the channel.

Analytical study
For ease of understanding, we present a simple EDCA model under saturation condition [13]. This model estimates the following: 1) interface queue dropping probability that computes the packets drop due to queue overflow, 2) a delay model that accounts for all events that contribute to the access delay, and finally 3) we derive the expected number of useful layers successfully delivered to the destination node regarding a defined layered video mapping strategy. These parameters capture the influence of the CW min[AC i ] and CW max[AC i ], AIFS, and Transmission Opportunity (T XOP) mechanisms. Moreover, we define the concepts of mapping, ordered mapping, exhaustive mapping, and canonical mapping. We compute the complexity of each mapping concept. Then, we present how the best mapping strategy is defined. Furthermore, we discuss the tradeoff between complexity and performance enhancement of layered video delivery over wireless network.
We assume that we have N video users (or subscriber stations SS), and n AC i number of AC i contending for the channel access. RL i,retry is the maximum retry limits of access category AC i .

EDCA model
The proposed model is based on the Markov chain introduced in [1,13]. It extends the probability formulas to support differential T XOP Limit parameter in the different computed performance metrics [2]. In the following, we denote by τ i the probability that a node in the AC i transmits during a generic slot time and by p i the probability that AC i senses the medium busy around it. The τ i takes into account both internal and external collision.
Where b i,0,0 is the initial state of the AC i . We follow the basic EDCA backoff increase scheme [1]. From the point of view of one wireless node, the probability τ that the node access to the medium is: We aim to derive for a given AC i , the formulas of saturation throughput, delay, and queue dropping probability. We focus here on packet dropping due to both queue overflow, and reaching the maximum retry limit. We assume that the frame corruptions are only due to collisions, thus no channel error is considered.
The collision probability due to both internal and external collisions is, defined as follows, for an AC i : Where h ≺ i means that AC h has higher priority than AC i . Let p succ,i be the probability that an AC i succeeds to transmit a packet and p succ the probability that a node achieves a successful transmission.
We can obtain the total saturation throughput for the system as follows: Where E[P i ] is the payload transmitted in a transmission period for a class i, and E [L] is the length of a transmission period. According to [1,2] the throughput can be defined as: Where E [length data ]is the average data packet length, p succ the probability that a station transmit successfully, p coll the probability that a collision occurs foe station , T S i the transmission time, T C the collision time, K T XOP i the number of packets transmitted during transmission opportunity period, and θ is the duration of the slot time.
The access delay for each AC i is defined as: . Frame-dropping probability analysis Let P i,drop be the probability of packet drops (see Eq.9) Where P queue drop,i is the probability that a packet is dropped due to the queue overflow, and P i,drop,coll represents the probability of frame drops due to maximum retry limit [13]. Let K be the maximum size of the queue, and λ i is the application rate of an AC i . We assume an exponential arrivals and departures of packets in the queue. So the service rate is µ = 1 E[D i ] and the traffic intensity or the offered load is defined as ρ : We consider the M/G/1/K state transition diagram. Thus, P queue drop,i is the probability that there are K packets in the queue at an arbitrary time:

EDCA-based layered video delivery model
We first define the following concepts: Layered video concept: In video coding schemes such as H.264/AVC, the video content is partitioned into sequences of pictures, referred to as groups of pictures (GOPs), each beginning with an independently decodable intra-coded picture. A typical duration for a GOP is 1-2 seconds. Each GOP contains many pictures or frames. A GOP is divided into a sequence of packets for delivery over the network. Although a single frame may span multiple packets, or a single packet may contain more than one frame, we can assume that there will be multiple packets for a GOP, and in the case of constant bitrate video coding, the number of packets per GOP will be constant throughout a sequence. Layered video concept as MRC (Multi-Resolution Coding), divides the video into a base layer and multiple enhancement layers. The base layer can be decoded to provide a basic quality of video while the enhancement layers are used to refine the quality of the video. If the base-layer is corrupted, the enhancement layers become useless, even if they are received perfectly. Moreover, in MRC, receiving the K th layer is only helpful if the previous K−1 layers have been received. Thus, in layered coding, the video content is partitioned into multiple layers of sub-streams, and hence each GOP can be thought of as consisting of several sequences of packets, one for each layer. We assume that these sub-streams have a constant bitrate [19].

Calculation of expected number of useful layers
We aim to address an efficent video transmission scheme based on EDCA medium access mechanism, that maximizes the number of useful layers received at the destination node. We define the estimated number of video layers based on the probabilities of the individual dropping probability of each layer: Where P l i is the dropping probability of layer l i and L is the total number of video layers represented by S(L) = {l 1 , l 2 , ..l L } . P l i depends on which AC the layer l i is mapped to. Thus, for all layers assigned to AC 1 , the P l i is equal to P 1,drop , the layers assigned to AC 2 , the P l i is equal to P 2,drop , these mapped to AC 3 , the P l i P 3,drop and these mapped to AC 4 , the P l i is equal to P 4,drop . It can be shown that to calculate E[UL](L), we need two nested loops to calculate the product and the summation, which deems the complexity of calculating E[UL] is O(L 2 ). The P l i are pre-computed for all r = 1, ....L regarding ACs packet drop probabilities.
Having obtained the medium contention, the dropping probabilities, and the packet collision probabilities from the model described in the previous subsection, we can compute the expected number of useful layers received, under different traffic load, for each mapping vector. Let n max be the maximum number of ACs:{AC 1 , AC 2 , ..AC n max } (for EDCA, n max = 4). We aim to map S(L) to different set of ACs. We define M(L, n) = {m AC 1 , m AC 2 , m AC 3 , ..m AC n } an arbitrary mapping vector, that maps L layers to n ACs (1 ≤ n ≤ n max ). Where m AC i is the number of video layers selected from S(L) and assigned to AC i . This leads to L = ∑ n i=1 m AC i . We aim to investigate the video performance of different mapping strategies of video layers, within each GOP, to different EDCA ACs. We calculate the expected number of video layers metric for each mapping vector. Then, we select the best mapping strategy vector M(L, n) regarding the maximum estimated value of average useful layers. We believe that considering this metric in our mechanism gives an accurate information about video delivery quality. Furtheremore, we have to perform an exhaustive search algorithm for all possible mapping strategies of video layers to different EDCA ACs. The Complexity of search for exhaustive mapping strategies C exh mapp , when considering four ACs and L layers, is: Thus, from Equation 14, we deduce that the best strategy selection algorithm over exhaustive mapping has a high complexity, which is about C exh mapp = O(L 3 ). When considering n ACs, C exh mapp = O(L n−1 ). Hereafter, we aim to minimize this complexity by extracting the group to which the best strategy belongs. We divide the exhaustive mapping strategies into two groups: canonical and non-canonical.
Canonical mapping: In the canonical mapping, the number of layers assigned to each AC increases with the class priority level. This leads to m AC n ≥ m AC n+1 for any n: 1 ≤ n ≤ n max and {m AC n , m AC n+1 } ⊂ M cano (L, n). Where M cano (L, n) is a canonical mapping vector.
Ordered mapping: In the ordered mapping concept, if a video layer l i is assigned to an AC j , the layer l i ′ , where i ′ > i should be assigned to AC j ′ where j ′ ≥ j . Recall that, for simplicity, in our EDCA model we consider AC j has higher priority than AC j+1 .

Lemma:
Considering our distributed environment and constant layers bitrate, the optimal mapping vector exists in the canonical ordered mapping.

Proof:
We proceed to prove the lemma by contradiction. Let's con- . Regarding EDCA service differentiation medium access, P i,drop < P j,drop (see Equation 9). Thus, when assigning more layers to AC j , more layers will be dropped than assigning the same number of layers to AC i . We obtain P ′ drop < P * drop and therefore E ′ [UL](L) > E * [UL](L) , which gives M * (L, n) is not the optimal mapping vector, and the optimal value exists for M ∼ (L, n) with m AC i ≥ m AC j √ 1 ≤ i < j ≤ n. Ordered mapping: For a given mapping strategy, we suppose that it exists l i , witch is assigned to AC n and l j , ( j > i) is assigned to AC m has higher priority than AC n ). We know that: P succ,m > P succ,n (regarding the service differentiation addressed with EDCA model), thus the probability that l i collides is higher than the probability that l j collides, and so l j becomes useless even it is transmitted successfully when l i is lost. This leads to a decreasing on the number of average useful video layers delivered. Thus, we have to ensure ordered layers mapping to different ACs to enhance video delivery quality.
Hereafter, we present the Optimal Canonical Ordered Mapping (OCOM) algorithm that will calculate the Optimal mapping based on ordered canonical mapping. Let j the number of active ACs considered in the mapping vector M(L, j), and m i, j is the maximum number of layers assigned to AC i , √ i ,i ≤ j. Thus, m i, j is calculated as: Where the mod function calculates the remainder of dividing L by j. Thus for one AC , we obtain m 1,1 = L . Hereafter, we describe the OCOM algorithm. For two ACs, we define: We present the OCOM algorithm description for L layers and n ACs in Table I To optimize the computation time and to reduce the complexity of selecting the best mapping strategy vector algorithm presented above, we define a new dynamic program that can be used to calculate E [UL] recursively regarding the number of ACs used in the mapping strategy: 1. For n = 1: all L video layers are mapped to the highest AC: In this case C E d p [UL] = O(∑ n j=1 l AC j ). ∑ n j=1 l AC j = L. Therefore, the complexity obtained using the new recursive Equation (17) is equal to O(L) regardless of the number of ACs considered in the mapping strategy. This complexity is lower than the complexity obtained with Equation (13). We compute E d p [UL] for each canonical mapping possibility to select the best mapping. Let C ′ L,n the compexity of the best strategy using Equation (17). C ′ L,n = O(nL 3 ). An example of our EDCA-based model architecture, based on ordered canonical mapping, is shown in Figure 1. Although the algorithm OCOM is practically feasible, we are seeking to reduce the complexity to make it more practical and scalable to the number of layers. Hence, we're proposing an optimal distributed adaptive algorithm selecting a specific mapping strategy regarding obtained results and analysis. This algorithm aims to maximize the average useful layers delivered. We aim to obtain a good performance close to the best canonical solution results, with low complexity.
. step 2: Select the mapping strategy, regarding minimum tolerated packet drop percentage threshold δ for each ACs: The number of layers assigned to the queue cannot cause more than δ (arbitrary parameter) of interface queue packet drops. We still assign layers to the AC till the threshold is acheived. Then, we move to assign the remaining layer to next ACs. To perform step 2, that is described in the above sub-optimal algorithm, we can calculate the number of layers l i to be assigned to AC i and then, the mapping vector such that the estimated dropping probability is less then or equal to δ . Hence, we compute first ρ from Equation (12) by fixing the threshold δ and so the IFQ dropping probability. Then, we can deduce l i from Equation (11).
As wireless channel is time-varying, the dropping probabilities are computed periodically based on the available wireless resources. The mapping strategy is updated when the drops increase and the average useful layer decreases.
In this section, we report different analysis methodologies and results of the extensive simulation sets that have been done using Matlab. We consider layered video composed with L layers. The physical overhead of IEEE 802.11a is illustrated in Table 1. The data rate is 6Mb/s and the control rate is 6Mb/s. The EDCA parameters of each AC are presented in Table 2. Poisson distributed traffic consisting of 1024-bytes packets was generated to each AC regarding the selected mapping strategy. We aim to evaluate the performance of different mapping strategies (cano:OCOM, non-cano:selects the best mapping from non-canonical vectors, and the sub-optimal algorithm) for layered video to different access categories. In order to identify the adequate scheme that matches the best mapping strategy, we implemented an algorithm that defines all exhaustive mapping techniques described previously. For each described mapping, we compute the average useful layers and the dropping probability as defined in our analytical model. We classify the obtained set of mapping strategies, to canonical mapping and noncanonical mapping. For each simulation setting, and for each mapping group, we select the best strategy minimizing the packets drop and maximizing the average useful layers delivered. Estimated number of useful layers successfully received by the destination, is a good metric that informs strongly about video quality. We use this metric to evaluate our proposals. We report results for N = 10 and N = 18 with various video application rates. We observe the evaluation results in the case of video coding using 8 and 20 video layers, and we consider different TXOP durations. The obtained results confirms our analytical study, they show that the canonical mapping ensures the best expected number of useful layers successfully delivered to the destination. Moreover, Figure 3 and Figure 2, show that for low application rate with T XOP = 5 and T XOP = 20 the results obtained using canonical and non-canonical mapping have the same trends. Furthermore, the best video quality is obtained with the lowest number of layers (L = 8). Indeed, for low data rate, with 8 layers, the average useful layers is about 5. However, when considering 20 layers, only about 2 useful layers are delivered successfully to the destination. A  significant improvement is obtained with canonical mapping when we increase the data rate, and using T XOP = 2 gives better performance than using T XOP = 5. Moreover, Figure 4 shows that increasing the number of layers for the same number on contending nodes does not enhance video quality as the average useful layers is almost similar for both scenarios. Figure 5 shows the results obtained using canonical, non-canonical, and the sub-optimal algorithm described above for L = 8 and N = 10. The sub-optimal proposal outperforms the non-canonical mapping. The best performance results are obtained with the canonical mechanism. Hence, the sub-optimal algorithm results ensure a compromise between complexity and performance enhancement. We set the threshold of the sub-optimal respectively to δ = 10% and δ = 20%. Figure 6 shows that for low bitrate, the sub-optimal algorithm using δ = 10% gives better expected average useful layers than δ = 20%, and both results are lower than other mapping strategies results. However, the performance of sub-optimal scheme increases when the application rate increases and becomes similar to the canonical mapping strategy results . Based on the obtained results, we propose to dynamically map the video layers to different EDCA ACs regarding the estimated performance metric (expected number of useful layers). The results showed that canonical mapping strategy is recommended for high data rate and high number of layers used for video coding. As, our analytical re- sults show that the best solution belongs to canonical mapping strategies, thus, instead of performing an exhaustive search over all possible mapping combinations, to select the best mapping strategy, only canonical mapping strategies will be considered. This will decrease the complexity of the proposed adaptive algorithm and optimize the calculation performed to obtain best performance metrics. Furthermore, we proposed a simple sub-optimal mapping algorithm based on heuristic study to more reduce the complexity of computation. The selected strategy considered to transmit video layers, is automatically adapted in the available channel resources.

Conclusion and Future work
In this framework, we proposed a distributed layered video mapping technique, over EDCA ACs. The proposed algorithm dynamically maps video layers to EDCA's appropriate ACs. The optimal mapping strategy was selected based on the estimated maximum average useful layers delivered to the destination node. We showed that canonical mapping strategies ensure the best performance comparing to other different mapping possibilities, especially for high application data rate. The obtained results showed that the described algorithm helps in meeting the performance improvement and also in decreasing the packet drops. The implementation of this algorithm in our Qatar University wireless mesh network regarding the network resources, channel sensitivity and other feedback information in protocol optimization could be the future work.