# Scalable Video Streaming for Single-Hop Wireless Networks Using a Contention-Based Access MAC Protocol

Authors: Monchai Lertsutthiwong; Thinh Nguyen; Alan Fern
Journal: Advances in Multimedia
 (2008)

---

## Abstract

Limited bandwidth and high packet loss rate pose a serious challenge for video streaming applications over
wireless networks. Even when packet loss is not present, the bandwidth fluctuation, as a result of an arbitrary number
of active flows in an IEEE 802.11 network, can significantly degrade the video quality. This paper aims to enhance the
quality of video streaming applications in wireless home networks via a joint optimization of video layer-allocation
technique, admission control algorithm, and medium access control (MAC) protocol. Using an Aloha-like MAC
protocol, we propose a novel admission control framework, which can be viewed as an optimization problem that
maximizes the average quality of admitted videos, given a specified minimum video quality for each flow. We present
some hardness results for the optimization problem under various conditions and propose some heuristic algorithms
for finding a good solution. In particular, we show that a simple greedy layer-allocation algorithm can perform
reasonably well, although it is typically not optimal. Consequently, we present a more expensive heuristic algorithm
that guarantees to approximate the optimal solution within a constant factor. Simulation results demonstrate that our
proposed framework can improve the video quality up to 26% as compared to those of the existing approaches.


---

## Body

## 1. Introduction

Recent years
have witnessed an explosive growth in multimedia wireless applications such as
video streaming and conferencing [1]. One of the reasons for this tremendous growth is the
wide deployment of the IEEE 802.11 wireless LANs (WLANs) in both private home
and enterprise networks. Despite of these seemingly successes, many fundamental
problems of transmitting multimedia data over wireless networks remain
relatively unsolved. One of the challenges is how to efficiently guarantee a
specified bandwidth for a video flow in a wireless network. The popular WLAN,
particularly Distributed Coordination Function (DCF) in typical IEEE 802.11
[2] which operates under
a contention-based channel access mechanism, does not provide a mechanism to
guarantee minimum bandwidth for multiple concurrent flows. As a result, a video
application may experience significant quality degradation due to free
admission of an arbitrarily large number of flows. Nevertheless, Point
Coordination Function (PCF) in typical IEEE 802.11 and HCF Controlled Channel
Access (HCCA) in IEEE 802.11e [3] are able to provide a polled access mechanism to
guarantee the minimum bandwidth. However, to take advantage of PCF and HCCA
mechanisms, a scheduler and a queuing mechanism at the AP are needed to control
and to regulate the polling frequency in HCCA and PCF to provide flows with the
requested throughputs. That said, this paper considers a contention-based
approach to admission control, similar to the work of Banchs et al. [4] in which, the parameters of
the IEEE 802.11e in the contention-based mode are set appropriately to enable
flows to achieve their requested throughputs or reduce the delay.Admission control prevents a new flow from joining the
network in order to maintain a reasonable quality of the existing flows. The
decision to admit or reject a new flow that requests to enter a wireline link
is arguably easier to make, compared to that of a wireless link. A simple
admission control algorithm for a wireline link can keep track of the total
used bandwidth. The available bandwidth is then equal to the difference between
the link capacity and used bandwidth. A new flow is admitted if its requested
bandwidth is smaller than the available bandwidth of the link by some
threshold, otherwise it is rejected. Theoretically, the same algorithm can be
applied to a wireless link if a time division multiple access (TDMA) scheme is
used to allocate bandwidth for each flow. Using a TDMA scheme,  each flow is
assigned to a set of exclusive time slots for
transmitting its data, thus eliminating the multiuser interference associated
with a wireless link. As a result, the admission control algorithm can
determine its available bandwidth precisely and make the decision to admit or
reject a new flow accordingly.However, such a protocol may require a centralized
scheduling algorithm, which may not be feasible in a distributed environment.
Therefore, existing Medium Access Control (MAC) protocols, such as the IEEE
802.11, employ a random access approach that allows the flows to compete for
shared channel efficiently. That is, IEEE 802.11 protocol enables the flows to
achieve high throughputs, while minimizing their collisions. Thus,
characterizing the wasted bandwidth from collisions is specific to a MAC
protocol.The problem of MAC protocols such as the IEEE 802.11
is the multiuser interference, that is, the collisions between the new flow and
the existing flows, which reduce all the flow's throughputs. The number of
these collisions increases nonlinearly with the number of competing flows,
making it harder for an admission control algorithm to determine the resulted
throughputs of all the flows in order to make the right decision [5]. In particular, for a simple
single-hop wireless network, to decide whether or not to admit a new flow, the
admission control algorithm must ensure that the available bandwidth is at
least K+H Kbps, where K is the total requested bandwidth including
that of the new flow, and H is the incurred overhead from the collisions.
While K is given to the algorithm, determining H is nontrivial when using a typical MAC
protocol. Computing H is even more difficult in a multihop wireless
network.Even when an algorithm can determine precisely the
collision bandwidth, it is not always beneficial to employ the traditional
admission control framework in which, the decision to admit a new flow is
solely based on the bandwidth and delay requirements of all the flows. Instead,
with the advance in video coding techniques, we argue that the criterion for
flow admission should be the visual quality of the video streams. That is, the
inputs to the admission control algorithm are the minimum visual quality of the
video streams, not their bandwidth and delay requirements. The former approach
assumes that each video is coded at a certain bit rate, thus any lesser rate
provided by the network is unacceptable since the video playback will be
interrupted frequently. On the other hand, with scalable video coding
techniques, the video is encoded in a layered hierarchy. Thus, a video can be
transmitted at different bit rates (or number of video layers), albeit at
different visual qualities. The advantage of this approach is that a larger
number of flows can be allowed to enter a network as long as the video quality
of each flow does not fall below a specified minimum threshold. The objective
is then to maximize the average quality of all the admitted videos, given a
specified minimum video quality for each stream, and the current available
bandwidth.That said, our paper aims to enhance the quality of
video streaming applications in wireless home networks via a joint optimization
of video layer-allocation technique, admission control algorithm, and MAC
protocol. While it is possible to extend our framework to multihop wireless ad
hoc environment, for clarity, our discussion is limited to a one-hop wireless
network, for example, the network of all the wireless hosts (devices) within a
home or a small building such that every host can hear the transmissions of all
other hosts. Using an Aloha-like MAC protocol [6], we present a novel
admission control framework, which can be viewed as an optimization problem
that maximizes the average quality of admitted videos, given a specified
minimum video quality for each flow. In particular, using scalable video
streams, our framework allows more flows to enter the network, as long as the
video quality of each flow does not fall below a specified minimum threshold.
We then present some hardness results for the optimization problem under
various conditions and propose two heuristic algorithms for obtaining a good
solution. We show that a simple greedy layer-allocation algorithm can perform
reasonable well, although it is typically not optimal. Consequently, we present
a more expensive heuristic algorithm that guarantees to approximate the optimal
solution within a constant factor.The outline of paper is as follows. We first discuss a
few related works on admission control for wireless networks and scalable video
coding in Section2. In Section 3, we describe a MAC protocol to be used in
conjunction with the admission control algorithm. We then formulate the
admission control framework as an optimization problem in Section 4. In
Section 5, we provide some hardness results for the optimization problem, and
corresponding heuristic algorithms for obtaining good solutions. Simulation
results will be given in Section 6. We then summarize our contributions and
conclude our paper with a few remarks in Section 7.


## 2. Related Work

Providing QoS
for flows on the Internet is extremely difficult, if not impossible, due to its
original design to scale with large networks. The current design places no
limit to the number of flows entering the network,
or attempts to regulate the bandwidth of individual
flows. As a result, bandwidth of multimedia applications over the Internet
often cannot be guaranteed. To that end, many scalable coding techniques have
been proposed for video transmission over the Internet. Scalable video coding
techniques are employed to compress a video bit stream in a layered hierarchy
consisting of a base layer and several enhancement layers [7]. The base layer contributes
the most to the visual quality of a video, while the enhancement layers provide
successive quality refinements. As such, using a scalable video bit stream, the
sender is able to adapt the video bit rate to the current available network
bandwidth by sending the base layer and an appropriate number of enhancement
layers [8–14]. The receiver is then able to view the video at a
certain visual quality, depending on network conditions.We note that scalable video coding techniques can
mitigate the insufficient bandwidth problem, but the fundamental issue is the
lack of bandwidth to accommodate all the flows. Thus, admission control must be
used. While it is difficult to implement admission control on a large and
heterogeneous network, for example, the Internet, it is possible to implement
some form of control or regulation in small networks, for example, WLAN.
Consequently, there have been many researches on providing some form of QoS for
media traffic in WLANs [15–21]. Recently, the introduction
of the new medium access control protocol of the IEEE 802.11e called the Hybrid
coordination function (HCF); van der Schaar et al. [22] proposed an HCF Controlled Channel Access- (HCCA-)
based admission control for video streaming applications that can admit a
larger number of stations simultaneously.Many other
existing admission control algorithms for WLANs have also been proposed. Gao et
al. [23] provided an
admission control by using a physical rate-based scheme in IEEE 802.11e. They
use the long-term average physical rates to compute the reservation of the
channel for some amount of time called the transmission opportunity (TXOP) for
each station then distribute TXOP's to everyone. Their framework provides some
certain level of admission control. Xiao and Li [24] used the measurements to
provide flow protection (isolation) in the IEEE 802.11e network. Their
algorithm is simple, yet effective. The algorithm requires the access point (AP)
to broadcast the necessary information to other wireless stations. In
particular, the AP announces the budget in terms of the remaining transmission
time for each traffic class (there are 4 traffic classes in the IEEE 802.11e)
through the beacon frames. When the time budget for a class is depleted, the
new streams of this class will not be admitted. Xiao and Li's work set a fixed
limit on the transmission time for the entire session,  resulting in low
bandwidth utilization when every traffic class does not
approach its limit. Recently, Bai et al. [25] improved the bandwidth utilization of Xiao and Li's
work by dynamically changing the transmission time of each class based on the
current traffic condition. There are also other admission control schemes
implemented at different layers of the network stack. For example, Barry et al.
[26] proposed to
monitor the channel using virtual MAC frames and estimate the local service
level by measuring virtual frames. Shah et al. [27] proposed an application
layer admission control based on MAC layer measurement using data packets.
Valaee and Li [28]
proposed a service curve based admission procedure using probe packets. Pong
and Moors [29]
proposed admission control strategy for QoS of flows in IEEE 802.11 by
adjusting the contention windows size and the transmission opportunity. All
these admission control schemes do not take quality of the traffic,
particularly video quality in our framework, into consideration directly. On
the other hand, we advocate a direct cross-layer optimization of video quality,
admission control algorithm, and MAC protocol, simultaneously. Most similar to our
work is that of Banchs et al. [4]. Since we will be using this scheme for performance
comparisons, we delay the discussion until Section 6.


## 3. MAC Protocol

As discussed
previously, the amount of wasted bandwidth from collisions in a wireless
network is different when using different MAC protocol. In this section, we
describe an Aloha-like MAC protocol [6] to be used in the proposed admission control framework
that aims at maximizing the average quality of
admitted videos, given a specified minimum video quality for each flow. In
order to contrast the advantages of the new MAC protocol, we first briefly
describe the existing IEEE 802.11e protocols in the contention-based access
mode.


### 3.1. Contention-Based Access Mechanism

The
contention-based channel access scheme in existing IEEE 802.11e protocol called
Enhanced Distributed Channel Access (EDCA), which defines a set of QoS
enhancements for WLAN applications through modifications to the MAC layer. To
access the channel, a host first senses the channel. If the channel is idle for
more than the Arbitration Interframe Space (AIFS) time, it starts sending the
data. Otherwise, it sets a backoff timer for a random number of time slots between[0,CWmin] where CWmin is the minimum contention window size. The
backoff timer is decremented by one for each idle time slot after the AIFS time
and halts decrementing when a transmission is detected. The decrementing
resumes when the channel is sensed idle again for an AIFS time. A host can
begin transmission on the channel as soon as its backoff timer reaches zero. If
a collision occurs, that is, no acknowledgment packet is received after a short
period of time, the backoff timer is chosen randomly between [0,(CWmin+1)2i−1], where i is the number of retransmission attempts. In
effect, the contention window size is doubled for each retransmission in order
to reduce the traffic in a heavily loaded network. Every time a host obtains
the channel successfully, it can reserve the channel for some amount of time
(TXOP). Unlike the IEEE 802.11b, IEEE 802.11e can tune the transmission
parameters (i.e., CWmin, CWmax,
TXOP, AIFS) to provide QoS support for certain applications. The EDCA is able
to operate either in ad hoc or infrastructure modes.The advantage of the existing IEEE 802.11 protocols is
that it is bandwidth efficient. That is, based on the current traffic
condition, each host adjusts its rate to achieve high throughput while
minimizing the number of collisions. On the other hand, the rate of a flow
cannot be controlled precisely unless we use PCF or HCCA. Often, this is
problematic for video applications. In particular, without using PCF or HCCA,
the fluctuation in achievable throughput would likely occur in the existing
IEEE 802.11 protocols due to their best effort behaviors. However, PCF and HCCA
require to have such a perfect scheduler in order to guarantee the achievable
throughputs of all the flows. Thus, we argue for a different MAC protocol
which, when used, would produce a stable throughput for a flow. Furthermore, it
is preferable to implement the new MAC protocol with minimal hardware modification
to the existing IEEE 802.11 devices. Indeed, this is possible.


### 3.2. Proposed MAC protocol

In the new MAC
protocol, the contention window size is not doubled after every unsuccessful
retransmission attempt. Instead, depending on the rate requested by a host, it
is assigned to a fixed value. All other operations
are exactly identical to those of the IEEE 802.11 protocol. We argue that when
a proper admission control is employed, eliminating the doubling ofCW in the IEEE 802.11 protocol helps to increase
the bandwidth efficiency since the rate of each host is not reduced
unnecessarily. We note that the existing works with EDCA cannot precisely
control the rate due to best effort behavior. Furthermore, the transmission parameters
(i.e., CWmin, CWmax,
TXOP, AIFS) in EDCA are not designed to achieve the exact rate (on average).
This would result in unnecessarily increasing in either the transmission rate
comparing to requested rate or unexpected collision. However, our proposed
protocol is able to solve such problems in contention based IEEE 802.11e.Based on the above discussion, it is crucial for an
admission control algorithm to determine whether or not there exists a set ofCWs for each host that satisfies their requested
rates without doubling CWs. To answer this question, we now proceed
with an analysis of the new MAC protocol.We assume the use of reservation packets, that is,
Request-To-Send/Clear-To-Send (RTS/CTS) packets. RTS/CTS packets are employed
to reduce the collision traffic as well as eliminating the hidden terminal
problem [30]. The main
idea is to send small packets to reserve the channel for the actual data
transmission. By doing so, collisions only occur with the small packets, hence
reducing the amount of wasted bandwidth. Since we assume that all the hosts can
hear each other's transmissions, we do not have the hidden terminal problem.
Our use of RTS/CTS is simply to reduce the collision bandwidth.Our analysis is based on time-slotted,
reservation-based protocols similar to the Aloha protocol, where the time taken
to make a reservation is a geometrically distributed random variable with
parameterp.
The significant difference between our protocol and the Aloha protocol is that
all the hosts in our network are assumed to be able to hear each other
transmissions. Therefore, a host will not attempt to transmit if it determines
that the channel is busy, that is, some host is sending. Thus, a host will
attempt to send an RTS packet with probability p only if it determines that the channel is
idle.Assume the host transmits the packets with some
probabilityp.
To translate the transmission probability p back to the contention window size used in
IEEE 802.11 protocol, CW can be set to 2/p.
We note that this is only an approximation since CW in the IEEE 802.11 protocol is not reset at
every time slot. To simplify the analysis, we further assume that every host
can start at most one flow at any point in time. A straightforward
generalization to support multiple flows per host is to consider all the flows
from one host as one single large flow with the transmission probability p.
Whenever a host successfully obtains the channel, it selects a packet from one
of its flows to send. The probability of a packet selected from a particular
flow then equals the ratio of that flow's throughput to the total throughput of
all the flows on the same host. This approach would result in the correct
average required throughputs for all the flows.For a network withN flows, our objective is to determine whether
or not there exists a set of p1,p2,…,pN and for each flow such that all the flows
achieve their specified throughputs R1,R2,…,RN, taking into account collisions. Since the rates Ri's depend on the percentages of successful
slots, we first characterize the percentages of collided, successful, and idle
slots, given pi's for each flow i.
To that end, let us denote
the following:(i)
I: percentage of idle slots,(ii)
Si: percentage of successful RTS slots for a flow i,(iii)
C: percentage of collided slots,(iv)
Ri′: throughput of flow i as a fraction of the channel capacity.
Note that I+C+∑iSi=1.
Suppose the transmission probability for a new flow is p,
then for C-type slots, in which collisions occur, the new
traffic would have no impact on it. For S-type slots, with probability p,
it may cause a collision. For an I-type slots, with probability p,
it would become a S-type slot. Otherwise it stays the same. Using the
above argument, we can calculate I, S,
and C after the new flow starts. In particular, the
new idle, collided, and successful probabilities can be calculated using the
current I,C,S,
and p as(1)Snew=Scurrent(1−p)+Icurrentp,Inew=Icurrent−Icurrentp,Cnew=1−Inew−Snew.Here, we denote S=∑iSi.
Similarly, we can calculate the successful probability Si as(2)Si,new=Si,current(1−p),for any existing flow i,
and the successful probability for the new flow (SN+1) as(3)SN+1=Icurrentp.Using the equations above, one
can compute the I's, C's, and Si's for N flows, given the transmission probabilities p1,p2,…,pN.
In particular, the following algorithm can be used to compute the collision
probability C,
which will be used in the admission control algorithm later.Algorithm1 enables us to compute the successful
probability precisely based on the given transmission probabilities pi's. On the other hand, one typically wants to
determine the transmission probabilities pi's, given the requested rates Ri′'s from each flow i.
Since the rate Ri′ is proportional to the corresponding
successful probability Si,
we now show how to compute pi's based on Si's. We then show how to relate Si's to Ri′'s, completing our objective.Algorithm 1:Computing C,
given the transmission probabilities pi's.
C=Compute_C(p1,p2,…,pN,N)I=1C=0S=0fori=1 to NdoS=S×(1−pi)+I×piI=I−I×piC=1−I−Send forreturnCIn principle, (1)–(3) enable us to write down a set of N equations with N unknown variables p1,p2,…,pN in terms of the known variables Si's, and solve for pi's. Unfortunately, these equations are not
linear, and therefore difficult to solve. We propose an algorithm to find the pi's given Si's based on the following observation. When a
flow i stops, I will increase by Si.
If flow
i starts again with the same transmission
probability pi as before, its successful probability remains Si as before. Hence, the following equations
hold:(4)(I+Si)pi=Si,pi=SiI+Si.This is true because I+Si is the probability of idle slots without flow i.
Hence, after the flow i starts, its successful probability is (I+Si)pi which should also equal precisely to Si,
the successful probability before it stops. Thus, we have N such equations corresponding to N flows. We also have the
constraint(5)I+C+S=1,where C and S are the collision and successful probabilities
for all the flows. We note that I is the same for every equation since it is the
probability of idle slots when all flows are active. Now, we can solve for N+1 unknowns, that is, N for pi's and one for I.
Solving this set of N+1 equations is simple since each equation is
linear except (5). Equation (5) is nonlinear in pi because C and S are polynomials in pi which are the results from (1)–(3). However,
(5) will be used as a constraint. Since I∈[0,1],
one can systematically try different values of I from large to small, that is, 1 to 0. For each
value of I,
we compute pi's according to (4). All the pi's are then input to Algorithm 1 to compute C.
We then test to see whether or not I+C+S approximately equals 1. If so, we have an
admissible set of solutions. If not, we increase I by a small value and repeat the procedure. If
the algorithm cannot find such I for the entire range of I∈[0,1],
then the solution does not exist. This indicates invalid Si's.Typically,Ri′'s, not Si's, are given. Therefore, to use the procedure
above, we first calculate the Si's in terms of Ri′'s. With minimal modification from IEEE
802.11e standard, our framework uses IEEE 802.11e frame formats and the timing
diagram as shown in Figure 1. After the channel is idle for a period time equal
to a distributed interframe space (DIFS) time slots, instead of counting down CW before beginning a new transmission, the host
sends RTS with probability p to reserve the shared channel. That means we
set AIFS=DIFS as same as the one in typical IEEE 802.11 standard [2]. Because all hosts can
listen to each other transmissions, the collision
will occur only if there is more than one host initiating RTS's at exactly the
same time slot. Otherwise, the host successfully reserves the channel, then that
host can begin the transmission for TXOP time slots without further collision. A host
detects unsuccessful transmission of an RTS if none of the CTS arrives within
DIFS time slots. Note that a host needs to wait for a short period of time
called Short Interframe Space (SIFS) where SIFS<DIFS before sending an ACK as shown in Figure
1. To be fair among all the flows with the same traffic class [3], that is, video streams,
everyone uses the same TXOP where TXOP=CTS+PHYhdr+MAChdr+PAYLOAD+ACK+3SIFS+DIFS.Figure 1
Timing diagram with RTS/CTS for our proposed framework.Suppose afterT time slots where T is large, we observe that there are Ki successful transmissions of RTS and Ki×TXOP slots of data transmission for each flow i.
Then by definition, we have(6)Si=KiT−∑i=1NKi×TXOP=Ki×TXOP/TTXOP×(1−∑i=1NKi×TXOP/T)=Ri′TXOP×(1−∑i=1NRi′),where Ri′=Ki×TXOP/T can be thought of as the host i's requested bandwidth in terms of a fraction
of the channel capacity, and N is the number of flows. If the channel
capacity is BW,
then the transmission rate Ri can be computed such that Ri=Ri′×BW.
For example, if channel capacity (BW) is 54 Mbps, and host i requests the rate (Ri) of 27 Mbps, then Ri′=0.5.Using (6), given the specified rates Ri′'s, one can compute the corresponding Si's, which are then used in the following
algorithm to determine the transmission probabilities pi's, if there are such p's.We note that for each unsuccessful RTS
transmission, we waste the channel equal toRTS+DIFS time slots. On the other
hand, each successful RTS transmission uses only RTS time slots. Furthermore,
Algorithm 2 explicitly considers the percentage of collided, successful, and
idle slots with respect to RTS transmissions to reserve the channel. This
results in total=I′+C(RTS+DIFS)+∑i=1NSi(RTS) where total is close to (or equal to) 1. We now describe
our proposed admission control framework.Algorithm 2:Compute pi's given all Ri′'s.
[p1,p2,…,pN,success]=Compute_p(R1′,R2′,…,RN′,N)ϵ=0.01I′=1{I′ is the percentage of idle slots}search_step=0.01success=0fori=1 to NdoSi=Ri′TXOP×(1−∑i=1NRi′)end forwhileI′<1dofori=1 to Ndopi=SiI′+Siend for{run Algorithm 1 to compute collision probability C}C=Compute_C(p1,p2,…,pN,N)total=I′+C(RTS+DIFS)+∑i=1NSi(RTS){check for boundary condition smaller ϵ results in higher accuracy}if(abs(total−1)<ϵ)thensuccess=1return[p1,p2,…,pN,success]end ifI′=I′−search_stependwhile{fail to find p,
success=0}return[0,0,…,0,success]


## 3.1. Contention-Based Access Mechanism

The
contention-based channel access scheme in existing IEEE 802.11e protocol called
Enhanced Distributed Channel Access (EDCA), which defines a set of QoS
enhancements for WLAN applications through modifications to the MAC layer. To
access the channel, a host first senses the channel. If the channel is idle for
more than the Arbitration Interframe Space (AIFS) time, it starts sending the
data. Otherwise, it sets a backoff timer for a random number of time slots between[0,CWmin] where CWmin is the minimum contention window size. The
backoff timer is decremented by one for each idle time slot after the AIFS time
and halts decrementing when a transmission is detected. The decrementing
resumes when the channel is sensed idle again for an AIFS time. A host can
begin transmission on the channel as soon as its backoff timer reaches zero. If
a collision occurs, that is, no acknowledgment packet is received after a short
period of time, the backoff timer is chosen randomly between [0,(CWmin+1)2i−1], where i is the number of retransmission attempts. In
effect, the contention window size is doubled for each retransmission in order
to reduce the traffic in a heavily loaded network. Every time a host obtains
the channel successfully, it can reserve the channel for some amount of time
(TXOP). Unlike the IEEE 802.11b, IEEE 802.11e can tune the transmission
parameters (i.e., CWmin, CWmax,
TXOP, AIFS) to provide QoS support for certain applications. The EDCA is able
to operate either in ad hoc or infrastructure modes.The advantage of the existing IEEE 802.11 protocols is
that it is bandwidth efficient. That is, based on the current traffic
condition, each host adjusts its rate to achieve high throughput while
minimizing the number of collisions. On the other hand, the rate of a flow
cannot be controlled precisely unless we use PCF or HCCA. Often, this is
problematic for video applications. In particular, without using PCF or HCCA,
the fluctuation in achievable throughput would likely occur in the existing
IEEE 802.11 protocols due to their best effort behaviors. However, PCF and HCCA
require to have such a perfect scheduler in order to guarantee the achievable
throughputs of all the flows. Thus, we argue for a different MAC protocol
which, when used, would produce a stable throughput for a flow. Furthermore, it
is preferable to implement the new MAC protocol with minimal hardware modification
to the existing IEEE 802.11 devices. Indeed, this is possible.


## 3.2. Proposed MAC protocol

In the new MAC
protocol, the contention window size is not doubled after every unsuccessful
retransmission attempt. Instead, depending on the rate requested by a host, it
is assigned to a fixed value. All other operations
are exactly identical to those of the IEEE 802.11 protocol. We argue that when
a proper admission control is employed, eliminating the doubling ofCW in the IEEE 802.11 protocol helps to increase
the bandwidth efficiency since the rate of each host is not reduced
unnecessarily. We note that the existing works with EDCA cannot precisely
control the rate due to best effort behavior. Furthermore, the transmission parameters
(i.e., CWmin, CWmax,
TXOP, AIFS) in EDCA are not designed to achieve the exact rate (on average).
This would result in unnecessarily increasing in either the transmission rate
comparing to requested rate or unexpected collision. However, our proposed
protocol is able to solve such problems in contention based IEEE 802.11e.Based on the above discussion, it is crucial for an
admission control algorithm to determine whether or not there exists a set ofCWs for each host that satisfies their requested
rates without doubling CWs. To answer this question, we now proceed
with an analysis of the new MAC protocol.We assume the use of reservation packets, that is,
Request-To-Send/Clear-To-Send (RTS/CTS) packets. RTS/CTS packets are employed
to reduce the collision traffic as well as eliminating the hidden terminal
problem [30]. The main
idea is to send small packets to reserve the channel for the actual data
transmission. By doing so, collisions only occur with the small packets, hence
reducing the amount of wasted bandwidth. Since we assume that all the hosts can
hear each other's transmissions, we do not have the hidden terminal problem.
Our use of RTS/CTS is simply to reduce the collision bandwidth.Our analysis is based on time-slotted,
reservation-based protocols similar to the Aloha protocol, where the time taken
to make a reservation is a geometrically distributed random variable with
parameterp.
The significant difference between our protocol and the Aloha protocol is that
all the hosts in our network are assumed to be able to hear each other
transmissions. Therefore, a host will not attempt to transmit if it determines
that the channel is busy, that is, some host is sending. Thus, a host will
attempt to send an RTS packet with probability p only if it determines that the channel is
idle.Assume the host transmits the packets with some
probabilityp.
To translate the transmission probability p back to the contention window size used in
IEEE 802.11 protocol, CW can be set to 2/p.
We note that this is only an approximation since CW in the IEEE 802.11 protocol is not reset at
every time slot. To simplify the analysis, we further assume that every host
can start at most one flow at any point in time. A straightforward
generalization to support multiple flows per host is to consider all the flows
from one host as one single large flow with the transmission probability p.
Whenever a host successfully obtains the channel, it selects a packet from one
of its flows to send. The probability of a packet selected from a particular
flow then equals the ratio of that flow's throughput to the total throughput of
all the flows on the same host. This approach would result in the correct
average required throughputs for all the flows.For a network withN flows, our objective is to determine whether
or not there exists a set of p1,p2,…,pN and for each flow such that all the flows
achieve their specified throughputs R1,R2,…,RN, taking into account collisions. Since the rates Ri's depend on the percentages of successful
slots, we first characterize the percentages of collided, successful, and idle
slots, given pi's for each flow i.
To that end, let us denote
the following:(i)
I: percentage of idle slots,(ii)
Si: percentage of successful RTS slots for a flow i,(iii)
C: percentage of collided slots,(iv)
Ri′: throughput of flow i as a fraction of the channel capacity.
Note that I+C+∑iSi=1.
Suppose the transmission probability for a new flow is p,
then for C-type slots, in which collisions occur, the new
traffic would have no impact on it. For S-type slots, with probability p,
it may cause a collision. For an I-type slots, with probability p,
it would become a S-type slot. Otherwise it stays the same. Using the
above argument, we can calculate I, S,
and C after the new flow starts. In particular, the
new idle, collided, and successful probabilities can be calculated using the
current I,C,S,
and p as(1)Snew=Scurrent(1−p)+Icurrentp,Inew=Icurrent−Icurrentp,Cnew=1−Inew−Snew.Here, we denote S=∑iSi.
Similarly, we can calculate the successful probability Si as(2)Si,new=Si,current(1−p),for any existing flow i,
and the successful probability for the new flow (SN+1) as(3)SN+1=Icurrentp.Using the equations above, one
can compute the I's, C's, and Si's for N flows, given the transmission probabilities p1,p2,…,pN.
In particular, the following algorithm can be used to compute the collision
probability C,
which will be used in the admission control algorithm later.Algorithm1 enables us to compute the successful
probability precisely based on the given transmission probabilities pi's. On the other hand, one typically wants to
determine the transmission probabilities pi's, given the requested rates Ri′'s from each flow i.
Since the rate Ri′ is proportional to the corresponding
successful probability Si,
we now show how to compute pi's based on Si's. We then show how to relate Si's to Ri′'s, completing our objective.Algorithm 1:Computing C,
given the transmission probabilities pi's.
C=Compute_C(p1,p2,…,pN,N)I=1C=0S=0fori=1 to NdoS=S×(1−pi)+I×piI=I−I×piC=1−I−Send forreturnCIn principle, (1)–(3) enable us to write down a set of N equations with N unknown variables p1,p2,…,pN in terms of the known variables Si's, and solve for pi's. Unfortunately, these equations are not
linear, and therefore difficult to solve. We propose an algorithm to find the pi's given Si's based on the following observation. When a
flow i stops, I will increase by Si.
If flow
i starts again with the same transmission
probability pi as before, its successful probability remains Si as before. Hence, the following equations
hold:(4)(I+Si)pi=Si,pi=SiI+Si.This is true because I+Si is the probability of idle slots without flow i.
Hence, after the flow i starts, its successful probability is (I+Si)pi which should also equal precisely to Si,
the successful probability before it stops. Thus, we have N such equations corresponding to N flows. We also have the
constraint(5)I+C+S=1,where C and S are the collision and successful probabilities
for all the flows. We note that I is the same for every equation since it is the
probability of idle slots when all flows are active. Now, we can solve for N+1 unknowns, that is, N for pi's and one for I.
Solving this set of N+1 equations is simple since each equation is
linear except (5). Equation (5) is nonlinear in pi because C and S are polynomials in pi which are the results from (1)–(3). However,
(5) will be used as a constraint. Since I∈[0,1],
one can systematically try different values of I from large to small, that is, 1 to 0. For each
value of I,
we compute pi's according to (4). All the pi's are then input to Algorithm 1 to compute C.
We then test to see whether or not I+C+S approximately equals 1. If so, we have an
admissible set of solutions. If not, we increase I by a small value and repeat the procedure. If
the algorithm cannot find such I for the entire range of I∈[0,1],
then the solution does not exist. This indicates invalid Si's.Typically,Ri′'s, not Si's, are given. Therefore, to use the procedure
above, we first calculate the Si's in terms of Ri′'s. With minimal modification from IEEE
802.11e standard, our framework uses IEEE 802.11e frame formats and the timing
diagram as shown in Figure 1. After the channel is idle for a period time equal
to a distributed interframe space (DIFS) time slots, instead of counting down CW before beginning a new transmission, the host
sends RTS with probability p to reserve the shared channel. That means we
set AIFS=DIFS as same as the one in typical IEEE 802.11 standard [2]. Because all hosts can
listen to each other transmissions, the collision
will occur only if there is more than one host initiating RTS's at exactly the
same time slot. Otherwise, the host successfully reserves the channel, then that
host can begin the transmission for TXOP time slots without further collision. A host
detects unsuccessful transmission of an RTS if none of the CTS arrives within
DIFS time slots. Note that a host needs to wait for a short period of time
called Short Interframe Space (SIFS) where SIFS<DIFS before sending an ACK as shown in Figure
1. To be fair among all the flows with the same traffic class [3], that is, video streams,
everyone uses the same TXOP where TXOP=CTS+PHYhdr+MAChdr+PAYLOAD+ACK+3SIFS+DIFS.Figure 1
Timing diagram with RTS/CTS for our proposed framework.Suppose afterT time slots where T is large, we observe that there are Ki successful transmissions of RTS and Ki×TXOP slots of data transmission for each flow i.
Then by definition, we have(6)Si=KiT−∑i=1NKi×TXOP=Ki×TXOP/TTXOP×(1−∑i=1NKi×TXOP/T)=Ri′TXOP×(1−∑i=1NRi′),where Ri′=Ki×TXOP/T can be thought of as the host i's requested bandwidth in terms of a fraction
of the channel capacity, and N is the number of flows. If the channel
capacity is BW,
then the transmission rate Ri can be computed such that Ri=Ri′×BW.
For example, if channel capacity (BW) is 54 Mbps, and host i requests the rate (Ri) of 27 Mbps, then Ri′=0.5.Using (6), given the specified rates Ri′'s, one can compute the corresponding Si's, which are then used in the following
algorithm to determine the transmission probabilities pi's, if there are such p's.We note that for each unsuccessful RTS
transmission, we waste the channel equal toRTS+DIFS time slots. On the other
hand, each successful RTS transmission uses only RTS time slots. Furthermore,
Algorithm 2 explicitly considers the percentage of collided, successful, and
idle slots with respect to RTS transmissions to reserve the channel. This
results in total=I′+C(RTS+DIFS)+∑i=1NSi(RTS) where total is close to (or equal to) 1. We now describe
our proposed admission control framework.Algorithm 2:Compute pi's given all Ri′'s.
[p1,p2,…,pN,success]=Compute_p(R1′,R2′,…,RN′,N)ϵ=0.01I′=1{I′ is the percentage of idle slots}search_step=0.01success=0fori=1 to NdoSi=Ri′TXOP×(1−∑i=1NRi′)end forwhileI′<1dofori=1 to Ndopi=SiI′+Siend for{run Algorithm 1 to compute collision probability C}C=Compute_C(p1,p2,…,pN,N)total=I′+C(RTS+DIFS)+∑i=1NSi(RTS){check for boundary condition smaller ϵ results in higher accuracy}if(abs(total−1)<ϵ)thensuccess=1return[p1,p2,…,pN,success]end ifI′=I′−search_stependwhile{fail to find p,
success=0}return[0,0,…,0,success]


## 4. Admission Control Framework

### 4.1. Architecture

Due to a
typical small size of a single-hop network, our admission control algorithm
runs at the AP or an elected host. We assume that all hosts are collaborative.
That is, each host obeys the admission protocol which operates as follows.For simplicity, in this paper, we assume that there is
no cross-traffic of any kinds except videos. In general, to accommodate other
nontime sensitive traffic in the proposed framework, one can perhaps set the
minimal throughput requirements for the traffic. Each host can send videos to
and receive from the Internet, or they can send videos among each other. When a
host wants to inject a new video stream into the network, it first requests to
join the network by sending a message to the AP. For video streaming
applications, the message may contain the rate distortion profile of the video,
which specifies the different distortion amounts and the corresponding number
of layers used. The message also contains the maximum allowable distortion for
a video. Note that for live video applications, the rate-distortion profile is
typically not known ahead of time, but can be estimated. That said, the focus
of this paper will be on streaming applications. Upon receiving the request,
the AP (or some elected host) will run the admission control algorithm to
produce a set transmission probabilitiespi's for each flow i that maximizes the average visual quality of
all the flows, given the maximum distortion levels for each video and overall
bandwidth constraint. If such transmission probabilities exist, the AP will
broadcast the transmission probabilities pi's to all the hosts.Upon receiving AP's instructions, each hosti begins to transmit its packets with
probability pi (or roughly setting its contention window to 2/pi) when it observes that the channel is idle.
Each transmission probability pi corresponds to a particular rate (or number of
layers). If there is no feasible set of transmission probabilities, the AP will
inform the new flow that it cannot join the network at this moment.


### 4.2. Problem Formulation

We are now at
the position to formulate a rate-distortion optimization problem for multiple
layered video streams under bandwidth and distortion constraints. We note that
the average throughput per unit time or transmission rateRi for a flow i can be achieved by setting its transmission
probability pi.
When there is enough bandwidth for everyone, pi's are set to large values so that all the
layers of all the video streams would be sent. When there is not enough
bandwidth, for example, due to too many flows, the layers from certain videos
are dropped resulting in the least average distortion over all the videos. For
a simple scenario, we assume that there is no packet loss during transmission.
The transmission rate Ri(li) for flow i is proportional to the number of transmitted
video layers li.The optimization problem studied in this paper is to
select the optimal number of video layers to transmit for each ofN hosts (or N flows) while maximizing the overall video
quality. Furthermore, the inclusion of the bandwidth overhead term H=C+S due to channel contention access (collision
and reservation bandwidth used for RTS/CTS packets) makes our optimization
problem distinct from other optimization problems. In particular, the problem
is specified by giving: for each host, a function Di(li),
that gives the reduction in distortion when using li layers at host i,
a rate function Ri(li) that gives the required bandwidth for
transmitting li layers from host i,
an overhead function H(l1,…,lN) that gives the amount of bandwidth consumed by
overhead (e.g., due to the channel contention) for a given assignment of layers
to hosts, lower bounds on the reduction in distortion for each i denoted by Zi,
and finally a bound on the total bandwidth BW.
Given these quantities, the optimization problem is as follows:
(7)maximize∑i=1NDi(li)overlisubjecttoDi(li)≥Zi,∑i=1NRi(li)+H(l1,…,lN)≤BW.That is, we must find the optimal assignment of layers
to each host that maximizes the reduction in total distortion subject to
bandwidth and local minimum reduction in distortion constraints. In particular,
there exists a solution if we are able to compute a set of transmission
probabilitiespi's corresponding to an optimal assignment of
layers for everyone. A necessary condition is that each flow i is required to maximize its total reduction in
distortion Di at least Zi.
Nevertheless, the way to select the layer depends on what layer-selection
strategies we use (e.g., greedy algorithm, exhaustive search). Note that
propagation delay and processing delay can be negligible due to operating in a
single-hop network. However, the delay variation or jitter would likely affect
the performance of the protocol. The detail analysis of throughput jitter is
discussed in Section 6.3. Next, we will study the computational properties of
the layer-selection problem and show that while in general the problem is
computationally hard, under certain reasonable conditions, a simple greedy
layer-allocation algorithm can be guaranteed to perform close to optimal.


## 4.1. Architecture

Due to a
typical small size of a single-hop network, our admission control algorithm
runs at the AP or an elected host. We assume that all hosts are collaborative.
That is, each host obeys the admission protocol which operates as follows.For simplicity, in this paper, we assume that there is
no cross-traffic of any kinds except videos. In general, to accommodate other
nontime sensitive traffic in the proposed framework, one can perhaps set the
minimal throughput requirements for the traffic. Each host can send videos to
and receive from the Internet, or they can send videos among each other. When a
host wants to inject a new video stream into the network, it first requests to
join the network by sending a message to the AP. For video streaming
applications, the message may contain the rate distortion profile of the video,
which specifies the different distortion amounts and the corresponding number
of layers used. The message also contains the maximum allowable distortion for
a video. Note that for live video applications, the rate-distortion profile is
typically not known ahead of time, but can be estimated. That said, the focus
of this paper will be on streaming applications. Upon receiving the request,
the AP (or some elected host) will run the admission control algorithm to
produce a set transmission probabilitiespi's for each flow i that maximizes the average visual quality of
all the flows, given the maximum distortion levels for each video and overall
bandwidth constraint. If such transmission probabilities exist, the AP will
broadcast the transmission probabilities pi's to all the hosts.Upon receiving AP's instructions, each hosti begins to transmit its packets with
probability pi (or roughly setting its contention window to 2/pi) when it observes that the channel is idle.
Each transmission probability pi corresponds to a particular rate (or number of
layers). If there is no feasible set of transmission probabilities, the AP will
inform the new flow that it cannot join the network at this moment.


## 4.2. Problem Formulation

We are now at
the position to formulate a rate-distortion optimization problem for multiple
layered video streams under bandwidth and distortion constraints. We note that
the average throughput per unit time or transmission rateRi for a flow i can be achieved by setting its transmission
probability pi.
When there is enough bandwidth for everyone, pi's are set to large values so that all the
layers of all the video streams would be sent. When there is not enough
bandwidth, for example, due to too many flows, the layers from certain videos
are dropped resulting in the least average distortion over all the videos. For
a simple scenario, we assume that there is no packet loss during transmission.
The transmission rate Ri(li) for flow i is proportional to the number of transmitted
video layers li.The optimization problem studied in this paper is to
select the optimal number of video layers to transmit for each ofN hosts (or N flows) while maximizing the overall video
quality. Furthermore, the inclusion of the bandwidth overhead term H=C+S due to channel contention access (collision
and reservation bandwidth used for RTS/CTS packets) makes our optimization
problem distinct from other optimization problems. In particular, the problem
is specified by giving: for each host, a function Di(li),
that gives the reduction in distortion when using li layers at host i,
a rate function Ri(li) that gives the required bandwidth for
transmitting li layers from host i,
an overhead function H(l1,…,lN) that gives the amount of bandwidth consumed by
overhead (e.g., due to the channel contention) for a given assignment of layers
to hosts, lower bounds on the reduction in distortion for each i denoted by Zi,
and finally a bound on the total bandwidth BW.
Given these quantities, the optimization problem is as follows:
(7)maximize∑i=1NDi(li)overlisubjecttoDi(li)≥Zi,∑i=1NRi(li)+H(l1,…,lN)≤BW.That is, we must find the optimal assignment of layers
to each host that maximizes the reduction in total distortion subject to
bandwidth and local minimum reduction in distortion constraints. In particular,
there exists a solution if we are able to compute a set of transmission
probabilitiespi's corresponding to an optimal assignment of
layers for everyone. A necessary condition is that each flow i is required to maximize its total reduction in
distortion Di at least Zi.
Nevertheless, the way to select the layer depends on what layer-selection
strategies we use (e.g., greedy algorithm, exhaustive search). Note that
propagation delay and processing delay can be negligible due to operating in a
single-hop network. However, the delay variation or jitter would likely affect
the performance of the protocol. The detail analysis of throughput jitter is
discussed in Section 6.3. Next, we will study the computational properties of
the layer-selection problem and show that while in general the problem is
computationally hard, under certain reasonable conditions, a simple greedy
layer-allocation algorithm can be guaranteed to perform close to optimal.


## 5. Computational Complexity of Layer Optimization

In this
section, we study the computational complexity of the layer allocation problem
described above, showing both hardness results and conditions under which
optimal and approximate solutions can be guaranteed in polynomial time. Our
optimization problem is distinct from most other bandwidth optimization
problems by its inclusion of the overhead termH in the bandwidth constraint. Thus, existing
algorithms and complexity proofs do not directly apply to our problem. Below,
we first consider the complexity of solving the problem optimally, and then we
consider efficient approximation algorithms.


### 5.1. Computing Optimal Solutions

Here, we
analyze the computational complexity of problem classes with the form given in
the previous section. We begin by stating three assumptions about the
optimization problem and consider the complexity under various subsets of these
assumptions.Assumption 1.
Uniform rate increase per level:(8)Ri(l+1)−Ri(l)=Rj(l′+1)−Rj(l′),for  anyi,j,l,l′.Assumption 2.
Diminishing
returns:(9)Di(l+1)−Di(l)≤Di(l)−Di(l−1),for  anyi,l.Assumption 3.
Invariant
overhead:(10)H(…,li+1,…)=H(…,lj+1,…),for  anyl1,…,lN.Below, we will also refer to the property of additive
overhead which means thatH(l1,…,lN) can be factored as a sum of the individual
overhead function Hi.
That is,(11)H(l1,…,lN)=∑i=1NHi(li).Intuitively, the first assumption states that the
amount by which the rate function increases is constant across all layers of
all streams. The second assumption states that within a particular stream,
higher layers may never reduce distortion more than the lower layers. Thus, it
will never be the case that a stream must include many lower layers with low
distortion reduction in order to get a big distortion reduction at a higher
layer. The third assumption states that, given a particular layer allocation
across layers, incrementing any layer by one produces the same increase in the overhead
function. This means that the overhead function is impartial to both the
particular stream that is incremented and the current number of layers
allocated to that stream.Our first result is that given the above three
assumptions (8)–(10), we can solve the optimization problem using an efficient
greedy layer-allocation algorithm. The algorithm proceeds as follows.
(1)
For each streami,
we initialize the layer count li to the smallest li such that Di(li)≥Zi.
If for some i this is not possible, then return “no
solution.”(2)
If it is not possible to increment the layer
count of any stream without violating the bandwidth constraints then terminate
and return the current layer counts. In other words, it is not possible to find
a feasible set of transmission probabilities for each host using the Algorithm2 in Section 3.(3)
Increment the layer count of streami by 1, where stream i is the stream that when incremented produces
the greatest reduction in distortion without violating bandwidth constraints.Proposition 1.
The greedy layer-allocation algorithm is optimal for any problem where Assumptions1, 2, and 3 hold.Proof.
We first introduce some notation. We
will use an allocation vectorL=〈l1,…,lN〉 to specify the layer allocation li to each host i where N is the total number of hosts. We will denote
by D(L) the reduction in distortion resulting from
allocation vector L.
A layer increment sequence is a sequence of host indices (i1,…,ik),
indicating the order of layers to increment finally arriving at a final
allocation vector where k is the total increments in layers.
Note that with invariant overhead and uniform rate
increase, each increment in the layer counts results in exactly the same
increase in bandwidth. This means that all optimal layer allocations will
satisfy∑ili=k for some value k.
That is, all optimal layer allocations will be a result of exactly k increments to layer counts. Thus, finding the
optimal layer allocation is equivalent to finding a length k layer increment sequence that results in the
best layer allocation starting from the null allocation.
Now, consider any layer allocationL and let i* be the index of the host that would be
selected by the greedy algorithm starting from L, and let Δ* be the reduction in distortion resulting from
the greedy step. Now consider any layer increment sequence (i1,…,iv) starting at L resulting in an allocation vector Lv.
We say that the sequence is an optimal v-step completion of L if the value of D(Lv) is the maximum possible when starting from L and incrementing v layers.
Our key claim is that there is always an optimalv-step completion to L that includes an increment to i*.
Assume that this was not the case and that the above sequence was an optimal
completion, implying that it does not contain an increment to i*.
We show that this leads to a contradiction. First, let Δj equal the reduction in distortion resulting
after adding the jth layer increment, and note that D(Lv) is equal to the sum of this sequence. By the
diminishing returns assumption, we have that Δ*≥Δj for all j.
This is true because the greedy algorithm selected the index i* with the largest decrease in distortion across
all layers and thus any further decreases resulting from incrementing any layer
must not be greater than that, otherwise this would violate diminishing
returns. Given this fact consider the new layer increment sequence (i*,i1,…,lv−1) and let L* equal the result of applying this sequence
starting at L.
It can be easily verified that this is a legal sequence, and that the
corresponding sequence of reductions in distortion is equal to (Δ*,Δ1,…,Δv−1).
Since D(L*) is simply the sum of this sequence and we know
that Δ*≥Δv this implies D(L*)≥D(Lv).
Thus, we have shown an optimal k-step completion that includes an increment to i*,
which gives a contradiction.
Using the above fact, it is straightforward to show by
induction on the number of greedy stepsk that the greedy algorithm always maintains an
optimal k-step completion of the null set, which
completes the proof.We now consider in Propositions2–4, the complexity of
this problem when each one of the above assumptions is lifted.Proposition 2.
The
class of decision problems  for which Assumptions2 and 3 hold but Assumption 1
does not is NP-complete even if one restricts the
overhead to be the constant zero function.Proof.
Our
problem is clearly in NP, as it is possible to enumerate possible layer
allocations and check them in polynomial time. Each layer-allocation
certificate is polynomial-size implying that the decision problem is in NP. To
show NP-hardness, we reduce from 0-1 knapsack problem. More formally, an
instance of 0-1 knapsack is a 4-tuple as shown in(12)〈{v1,…,vN},{c1,…,cN},V,C〉,where vi and ci,
and give the value and cost of the ith item, V is the value goal, and C is the cost limit. We will form the following
version of our problem as in(13)〈{1,…,1},{D1(l1),…,DN(lN)},{R1(l1),…,RN(lN)},H(l1,…,lN),V,C〉,where Di(li)=vi, Ri(li)=ci,
and H(l1,…,lN)=0 for all inputs. That is, we have only one
layer to allocate. The reduction in distortion and the rate function for that
layer are equal to vi and ci of the 0-1 knapsack problem, respectively.
Note that this problem does not satisfy the constant rate increase since ci can be different for each i.
However, it does satisfy Assumptions 2 and 3 trivially. It is straightforward
to show that the answer to the layer-allocation problem given by (13) will be
“yes” if and only if the answer is “yes” for the corresponding 0-1 knapsack
problem.Proposition 3.
The class of problems for
which Assumptions1 and 3 hold but Assumption 2 does not is NP-complete even if
one restricts the overhead to be the constant zero
function.Proof.
The
problem is in NP for the same reasons as above. For the purposes of this
problem, we will only consider the 0-1 knapsack problem with integer values ofvi, ci, V,
and C.
We can do this without loss of generality since we can always multiply all
numbers by the appropriate power of 10. Given an instance of the 0-1 knapsack
problem as specified in (12), our reduction constructs the following layer
allocation problem:(14)〈{c1,…,cN},{D1(l1),…,DN(lN)},{R1(l1),…,RN(lN)},H(l1,…,lN),V,C〉,where Di(li)=0 for li<ci, Di(ci)=vi, Ri(li)=li,
and H(l1,…,lN)=0.
The intuition here is that we have many layers in each stream, but only the
last layer actually reduces the distortion. This type of behavior violates
Assumption 2. Each layer adds exactly one unit of bandwidth which satisfies
Assumption 1 and the overhead is zero, which satisfies Assumption 3. Note also
that the number of layers for flow i is ci.
So in order to get a reduction in distortion of vi,
we must pay a bandwidth of ci,
which aligns with the 0-1 knapsack problem.
Given this reduction, it shows that there is a “yes”
answer for the constructed layer allocation problem if there is a “yes”
answer for the 0-1 knapsack instance.Finally, we show that Assumption3 is also necessary
in some sense. In particular, when it is lifted the problem becomes
computationally hard even when restricted to the class of problems with
additive overhead.Proposition 4.
The class of problems for which Assumptions1 and 2 hold but
Assumption 3 does not is NP-complete even if one
restricts to additive overhead.Proof.
Again here we will only consider the
integer knapsack problem. Given an instance of an integer 0-1 knapsack problem,
we construct the following instance of the layer allocation
problem:(15)〈{v1,…,vN},{D1(l1),…,DN(lN)},{R1(l1),…,RN(lN)},H(l1,…,lN),V,C〉,where Di(li)=li, Ri(li)=0,
and H(l1,…,lN)=∑iHi(li), where Hi(li)=ci for li>0 and Hi(0)=0.
So here we have the diminishing return property since for each layer we add a
single unit of reduction in distortion. We have the constant bandwidth property
trivially. But we do not have invariant overhead since when we move a layer li from 0 to 1 we get an increase in ci.
Only the overhead function occupies the bandwidth since all the rates are equal
to zero. Given this reduction, it is easy to verify that there is a “yes”
answer to the 0-1 knapsack instance if there is a “yes” answer to the
constructed layer allocation problem.Together these complexity results show that if we
remove any one of three assumptions, the problem becomes NP-hard and hence is
not likely to be solved by an efficient algorithm, in particular the greedy
algorithm. The results also show that this is true even if we place strict
restrictions on the form of the overhead function. Even if the overhead is
additive, the problem is hard as shown by Proposition4.In practice, it may often be possible to satisfy
Assumptions1 and 2. Unfortunately, we can show that the overhead function
arising in our protocol is not invariant as required by Assumption 3, and hence
an efficient optimal solution is still unlikely.Proposition 5.
The overhead of the proposed MAC protocol is not invariant.Proof.
We will show that the overhead of
proposed MAC protocol is not invariant by contradiction. Assuming that the
bandwidth overheadH=C+S,
bandwidth involved in reservation, is invariant, then(16)H′(i)=H′(j),where H′(i) and H′(j) denote the overhead resulted from adding δ bps (one layer) into flow i and flow j,
respectively. Since I+C+S=I+H=1,
we have(17)I′(i)=I′(j),where I′(i) and I′(j) denote the idle slots resulted from adding δ bps into flow i and flow j,
respectively. In particular, adding δ bps into flow i results in the increase of Si by Δ.
We can represent I in terms of Si as(18)I=∏i(1−pi)=∏i(1−SiI+Si)=∏i(II+Si).That is,(19)(I′(i)I′(i)+(Si+Δ))∏k≠i(I′(i)I′(i)+Sk)=(I′(j)I′(j)+(Sj+Δ))∏k≠j(I′(j)I′(j)+Sk).
Expanding
the product on both sides of (19), all product terms, except the one with
either Si or Sj,
will be canceled out, leading to(20)(I′(i)+(Si+Δ))(I′(i)+Sj)=(I′(j)+Si)(I′(j)+(Sj+Δ)).Since I′(i)=I′(j),
(20) is true if Si=Sj.
Since Si is directly proportional to Ri,
this implies that in order to achieve H′(i)=H′(j),
the current sending rate of any two video stream must be equal to each other.
This is not true in general, therefore the bandwidth overhead of the proposed
MAC protocol is not invariant.


### 5.2. Computing Approximate Solutions

Of the three
assumptions above, Assumption2, diminishing returns, is the one that is most
likely to be satisfied in application settings, since most coding schemes
exhibit diminishing returns behavior. Assumption 1, uniform rate increase, will
also often be satisfied, though it will rule out nonuniform rate coding
schemes. Assumption 3, invariant overhead, as we have seen is violated by our
protocol and we are unaware of other protocols that satisfy the assumption. In
this light, it is interesting to consider what can be said theoretically when
only Assumption 2 is satisfied. We know from Propositions 2 and 3 that in
general the problem is NP-hard to solve optimally with only Assumption 2,
however, this does not rule out the existence of efficient approximation
algorithms.In fact, using a slight modified the greedy
layer-allocation algorithm, we can obtain a solution guaranteed within a factor
of(1−e−1)≥0.63 from the optimal solution. We now describe the
first approximate algorithm.


#### 5.2.1. Double-Greedy Algorithm

This algorithm is based on the recent result in
[31]. We consider a
modified version of the original greedy algorithm, where at each step instead
of adding the video layer x that most increases in the reduction in
distortion, we add the layer that achieves the largest ratio of the reduction
in distortion to the increases in bandwidth, provided that adding x does not violate the total bandwidth
constraint BW.
That is, for each iteration, we add the layer x with maximum ratio of the reduction in
distortion to the increases in bandwidth, such that the total usage bandwidth is
less than BW.
The iteration repeats until no video layer can be added to the network without
violating the bandwidth constraint. Thus, it can be shown that even this
modified algorithm can yield arbitrarily poor results compared to the optimal
solution. However, if one returns the best solution found by either the
original greedy algorithm or the modified greedy algorithm, then one can
guarantee an approximation factor of 0.5(1−e−1).
We will call this algorithm the double-greedy algorithm.This
shows that by increasing the computation time by a factor of two over the
original greedy algorithm (i.e.,  we must now run both greedy and modified
greedy), it is possible to achieve a nontrivial approximation
bound. (Technically, it is not necessary to run the full greedy algorithm in
order to achieve the approximation bound. Rather, one needs
to only run the original greedy algorithm for one iteration
(i.e., selecting the best single element of the set) and then
to return the maximum of the best single element
and the result of the modified greedy algorithm. The results ofdouble-greedy are guaranteed to be at
least as good as this and often better, but with an increase in computation
time.)


#### 5.2.2. Triple-Greedy Algorithm

It turns out that by increasing the computation
further, but remaining polynomial time, it is possible to improve the
approximation bound to(1−e−1) for the constrained optimization problem,
which matches the result for the unconstrained problem, as proven in [31, 32]. The new algorithm simply
enumerates all triples of consecutive layers, denoted by T,
in each flow that do not violate the bandwidth constraint BW.
For each triple T,
the algorithm runs the modified greedy algorithm initialized to the set T then returns the set T′ among all of the triples that achieved the
highest ratio of the reduction in distortion to the increases in bandwidth.
This algorithm increases the runtime by a factor of O(|E|3) over the original greedy algorithm, but yields
a much stronger approximation result. We have the following result.Theorem 1.
Thedouble-greedy* and triple-greedy* algorithms achieve a
constant factor approximation bounds of 0.5(1−e−1) and 0.5(1−e−1),
respectively.Proof.
Due to space constraints, the reader is referred to the full
technical report for detail proofs of above results [33].


## 5.1. Computing Optimal Solutions

Here, we
analyze the computational complexity of problem classes with the form given in
the previous section. We begin by stating three assumptions about the
optimization problem and consider the complexity under various subsets of these
assumptions.Assumption 1.
Uniform rate increase per level:(8)Ri(l+1)−Ri(l)=Rj(l′+1)−Rj(l′),for  anyi,j,l,l′.Assumption 2.
Diminishing
returns:(9)Di(l+1)−Di(l)≤Di(l)−Di(l−1),for  anyi,l.Assumption 3.
Invariant
overhead:(10)H(…,li+1,…)=H(…,lj+1,…),for  anyl1,…,lN.Below, we will also refer to the property of additive
overhead which means thatH(l1,…,lN) can be factored as a sum of the individual
overhead function Hi.
That is,(11)H(l1,…,lN)=∑i=1NHi(li).Intuitively, the first assumption states that the
amount by which the rate function increases is constant across all layers of
all streams. The second assumption states that within a particular stream,
higher layers may never reduce distortion more than the lower layers. Thus, it
will never be the case that a stream must include many lower layers with low
distortion reduction in order to get a big distortion reduction at a higher
layer. The third assumption states that, given a particular layer allocation
across layers, incrementing any layer by one produces the same increase in the overhead
function. This means that the overhead function is impartial to both the
particular stream that is incremented and the current number of layers
allocated to that stream.Our first result is that given the above three
assumptions (8)–(10), we can solve the optimization problem using an efficient
greedy layer-allocation algorithm. The algorithm proceeds as follows.
(1)
For each streami,
we initialize the layer count li to the smallest li such that Di(li)≥Zi.
If for some i this is not possible, then return “no
solution.”(2)
If it is not possible to increment the layer
count of any stream without violating the bandwidth constraints then terminate
and return the current layer counts. In other words, it is not possible to find
a feasible set of transmission probabilities for each host using the Algorithm2 in Section 3.(3)
Increment the layer count of streami by 1, where stream i is the stream that when incremented produces
the greatest reduction in distortion without violating bandwidth constraints.Proposition 1.
The greedy layer-allocation algorithm is optimal for any problem where Assumptions1, 2, and 3 hold.Proof.
We first introduce some notation. We
will use an allocation vectorL=〈l1,…,lN〉 to specify the layer allocation li to each host i where N is the total number of hosts. We will denote
by D(L) the reduction in distortion resulting from
allocation vector L.
A layer increment sequence is a sequence of host indices (i1,…,ik),
indicating the order of layers to increment finally arriving at a final
allocation vector where k is the total increments in layers.
Note that with invariant overhead and uniform rate
increase, each increment in the layer counts results in exactly the same
increase in bandwidth. This means that all optimal layer allocations will
satisfy∑ili=k for some value k.
That is, all optimal layer allocations will be a result of exactly k increments to layer counts. Thus, finding the
optimal layer allocation is equivalent to finding a length k layer increment sequence that results in the
best layer allocation starting from the null allocation.
Now, consider any layer allocationL and let i* be the index of the host that would be
selected by the greedy algorithm starting from L, and let Δ* be the reduction in distortion resulting from
the greedy step. Now consider any layer increment sequence (i1,…,iv) starting at L resulting in an allocation vector Lv.
We say that the sequence is an optimal v-step completion of L if the value of D(Lv) is the maximum possible when starting from L and incrementing v layers.
Our key claim is that there is always an optimalv-step completion to L that includes an increment to i*.
Assume that this was not the case and that the above sequence was an optimal
completion, implying that it does not contain an increment to i*.
We show that this leads to a contradiction. First, let Δj equal the reduction in distortion resulting
after adding the jth layer increment, and note that D(Lv) is equal to the sum of this sequence. By the
diminishing returns assumption, we have that Δ*≥Δj for all j.
This is true because the greedy algorithm selected the index i* with the largest decrease in distortion across
all layers and thus any further decreases resulting from incrementing any layer
must not be greater than that, otherwise this would violate diminishing
returns. Given this fact consider the new layer increment sequence (i*,i1,…,lv−1) and let L* equal the result of applying this sequence
starting at L.
It can be easily verified that this is a legal sequence, and that the
corresponding sequence of reductions in distortion is equal to (Δ*,Δ1,…,Δv−1).
Since D(L*) is simply the sum of this sequence and we know
that Δ*≥Δv this implies D(L*)≥D(Lv).
Thus, we have shown an optimal k-step completion that includes an increment to i*,
which gives a contradiction.
Using the above fact, it is straightforward to show by
induction on the number of greedy stepsk that the greedy algorithm always maintains an
optimal k-step completion of the null set, which
completes the proof.We now consider in Propositions2–4, the complexity of
this problem when each one of the above assumptions is lifted.Proposition 2.
The
class of decision problems  for which Assumptions2 and 3 hold but Assumption 1
does not is NP-complete even if one restricts the
overhead to be the constant zero function.Proof.
Our
problem is clearly in NP, as it is possible to enumerate possible layer
allocations and check them in polynomial time. Each layer-allocation
certificate is polynomial-size implying that the decision problem is in NP. To
show NP-hardness, we reduce from 0-1 knapsack problem. More formally, an
instance of 0-1 knapsack is a 4-tuple as shown in(12)〈{v1,…,vN},{c1,…,cN},V,C〉,where vi and ci,
and give the value and cost of the ith item, V is the value goal, and C is the cost limit. We will form the following
version of our problem as in(13)〈{1,…,1},{D1(l1),…,DN(lN)},{R1(l1),…,RN(lN)},H(l1,…,lN),V,C〉,where Di(li)=vi, Ri(li)=ci,
and H(l1,…,lN)=0 for all inputs. That is, we have only one
layer to allocate. The reduction in distortion and the rate function for that
layer are equal to vi and ci of the 0-1 knapsack problem, respectively.
Note that this problem does not satisfy the constant rate increase since ci can be different for each i.
However, it does satisfy Assumptions 2 and 3 trivially. It is straightforward
to show that the answer to the layer-allocation problem given by (13) will be
“yes” if and only if the answer is “yes” for the corresponding 0-1 knapsack
problem.Proposition 3.
The class of problems for
which Assumptions1 and 3 hold but Assumption 2 does not is NP-complete even if
one restricts the overhead to be the constant zero
function.Proof.
The
problem is in NP for the same reasons as above. For the purposes of this
problem, we will only consider the 0-1 knapsack problem with integer values ofvi, ci, V,
and C.
We can do this without loss of generality since we can always multiply all
numbers by the appropriate power of 10. Given an instance of the 0-1 knapsack
problem as specified in (12), our reduction constructs the following layer
allocation problem:(14)〈{c1,…,cN},{D1(l1),…,DN(lN)},{R1(l1),…,RN(lN)},H(l1,…,lN),V,C〉,where Di(li)=0 for li<ci, Di(ci)=vi, Ri(li)=li,
and H(l1,…,lN)=0.
The intuition here is that we have many layers in each stream, but only the
last layer actually reduces the distortion. This type of behavior violates
Assumption 2. Each layer adds exactly one unit of bandwidth which satisfies
Assumption 1 and the overhead is zero, which satisfies Assumption 3. Note also
that the number of layers for flow i is ci.
So in order to get a reduction in distortion of vi,
we must pay a bandwidth of ci,
which aligns with the 0-1 knapsack problem.
Given this reduction, it shows that there is a “yes”
answer for the constructed layer allocation problem if there is a “yes”
answer for the 0-1 knapsack instance.Finally, we show that Assumption3 is also necessary
in some sense. In particular, when it is lifted the problem becomes
computationally hard even when restricted to the class of problems with
additive overhead.Proposition 4.
The class of problems for which Assumptions1 and 2 hold but
Assumption 3 does not is NP-complete even if one
restricts to additive overhead.Proof.
Again here we will only consider the
integer knapsack problem. Given an instance of an integer 0-1 knapsack problem,
we construct the following instance of the layer allocation
problem:(15)〈{v1,…,vN},{D1(l1),…,DN(lN)},{R1(l1),…,RN(lN)},H(l1,…,lN),V,C〉,where Di(li)=li, Ri(li)=0,
and H(l1,…,lN)=∑iHi(li), where Hi(li)=ci for li>0 and Hi(0)=0.
So here we have the diminishing return property since for each layer we add a
single unit of reduction in distortion. We have the constant bandwidth property
trivially. But we do not have invariant overhead since when we move a layer li from 0 to 1 we get an increase in ci.
Only the overhead function occupies the bandwidth since all the rates are equal
to zero. Given this reduction, it is easy to verify that there is a “yes”
answer to the 0-1 knapsack instance if there is a “yes” answer to the
constructed layer allocation problem.Together these complexity results show that if we
remove any one of three assumptions, the problem becomes NP-hard and hence is
not likely to be solved by an efficient algorithm, in particular the greedy
algorithm. The results also show that this is true even if we place strict
restrictions on the form of the overhead function. Even if the overhead is
additive, the problem is hard as shown by Proposition4.In practice, it may often be possible to satisfy
Assumptions1 and 2. Unfortunately, we can show that the overhead function
arising in our protocol is not invariant as required by Assumption 3, and hence
an efficient optimal solution is still unlikely.Proposition 5.
The overhead of the proposed MAC protocol is not invariant.Proof.
We will show that the overhead of
proposed MAC protocol is not invariant by contradiction. Assuming that the
bandwidth overheadH=C+S,
bandwidth involved in reservation, is invariant, then(16)H′(i)=H′(j),where H′(i) and H′(j) denote the overhead resulted from adding δ bps (one layer) into flow i and flow j,
respectively. Since I+C+S=I+H=1,
we have(17)I′(i)=I′(j),where I′(i) and I′(j) denote the idle slots resulted from adding δ bps into flow i and flow j,
respectively. In particular, adding δ bps into flow i results in the increase of Si by Δ.
We can represent I in terms of Si as(18)I=∏i(1−pi)=∏i(1−SiI+Si)=∏i(II+Si).That is,(19)(I′(i)I′(i)+(Si+Δ))∏k≠i(I′(i)I′(i)+Sk)=(I′(j)I′(j)+(Sj+Δ))∏k≠j(I′(j)I′(j)+Sk).
Expanding
the product on both sides of (19), all product terms, except the one with
either Si or Sj,
will be canceled out, leading to(20)(I′(i)+(Si+Δ))(I′(i)+Sj)=(I′(j)+Si)(I′(j)+(Sj+Δ)).Since I′(i)=I′(j),
(20) is true if Si=Sj.
Since Si is directly proportional to Ri,
this implies that in order to achieve H′(i)=H′(j),
the current sending rate of any two video stream must be equal to each other.
This is not true in general, therefore the bandwidth overhead of the proposed
MAC protocol is not invariant.


## 5.2. Computing Approximate Solutions

Of the three
assumptions above, Assumption2, diminishing returns, is the one that is most
likely to be satisfied in application settings, since most coding schemes
exhibit diminishing returns behavior. Assumption 1, uniform rate increase, will
also often be satisfied, though it will rule out nonuniform rate coding
schemes. Assumption 3, invariant overhead, as we have seen is violated by our
protocol and we are unaware of other protocols that satisfy the assumption. In
this light, it is interesting to consider what can be said theoretically when
only Assumption 2 is satisfied. We know from Propositions 2 and 3 that in
general the problem is NP-hard to solve optimally with only Assumption 2,
however, this does not rule out the existence of efficient approximation
algorithms.In fact, using a slight modified the greedy
layer-allocation algorithm, we can obtain a solution guaranteed within a factor
of(1−e−1)≥0.63 from the optimal solution. We now describe the
first approximate algorithm.


### 5.2.1. Double-Greedy Algorithm

This algorithm is based on the recent result in
[31]. We consider a
modified version of the original greedy algorithm, where at each step instead
of adding the video layer x that most increases in the reduction in
distortion, we add the layer that achieves the largest ratio of the reduction
in distortion to the increases in bandwidth, provided that adding x does not violate the total bandwidth
constraint BW.
That is, for each iteration, we add the layer x with maximum ratio of the reduction in
distortion to the increases in bandwidth, such that the total usage bandwidth is
less than BW.
The iteration repeats until no video layer can be added to the network without
violating the bandwidth constraint. Thus, it can be shown that even this
modified algorithm can yield arbitrarily poor results compared to the optimal
solution. However, if one returns the best solution found by either the
original greedy algorithm or the modified greedy algorithm, then one can
guarantee an approximation factor of 0.5(1−e−1).
We will call this algorithm the double-greedy algorithm.This
shows that by increasing the computation time by a factor of two over the
original greedy algorithm (i.e.,  we must now run both greedy and modified
greedy), it is possible to achieve a nontrivial approximation
bound. (Technically, it is not necessary to run the full greedy algorithm in
order to achieve the approximation bound. Rather, one needs
to only run the original greedy algorithm for one iteration
(i.e., selecting the best single element of the set) and then
to return the maximum of the best single element
and the result of the modified greedy algorithm. The results ofdouble-greedy are guaranteed to be at
least as good as this and often better, but with an increase in computation
time.)


### 5.2.2. Triple-Greedy Algorithm

It turns out that by increasing the computation
further, but remaining polynomial time, it is possible to improve the
approximation bound to(1−e−1) for the constrained optimization problem,
which matches the result for the unconstrained problem, as proven in [31, 32]. The new algorithm simply
enumerates all triples of consecutive layers, denoted by T,
in each flow that do not violate the bandwidth constraint BW.
For each triple T,
the algorithm runs the modified greedy algorithm initialized to the set T then returns the set T′ among all of the triples that achieved the
highest ratio of the reduction in distortion to the increases in bandwidth.
This algorithm increases the runtime by a factor of O(|E|3) over the original greedy algorithm, but yields
a much stronger approximation result. We have the following result.Theorem 1.
Thedouble-greedy* and triple-greedy* algorithms achieve a
constant factor approximation bounds of 0.5(1−e−1) and 0.5(1−e−1),
respectively.Proof.
Due to space constraints, the reader is referred to the full
technical report for detail proofs of above results [33].


## 5.2.1. Double-Greedy Algorithm

This algorithm is based on the recent result in
[31]. We consider a
modified version of the original greedy algorithm, where at each step instead
of adding the video layer x that most increases in the reduction in
distortion, we add the layer that achieves the largest ratio of the reduction
in distortion to the increases in bandwidth, provided that adding x does not violate the total bandwidth
constraint BW.
That is, for each iteration, we add the layer x with maximum ratio of the reduction in
distortion to the increases in bandwidth, such that the total usage bandwidth is
less than BW.
The iteration repeats until no video layer can be added to the network without
violating the bandwidth constraint. Thus, it can be shown that even this
modified algorithm can yield arbitrarily poor results compared to the optimal
solution. However, if one returns the best solution found by either the
original greedy algorithm or the modified greedy algorithm, then one can
guarantee an approximation factor of 0.5(1−e−1).
We will call this algorithm the double-greedy algorithm.This
shows that by increasing the computation time by a factor of two over the
original greedy algorithm (i.e.,  we must now run both greedy and modified
greedy), it is possible to achieve a nontrivial approximation
bound. (Technically, it is not necessary to run the full greedy algorithm in
order to achieve the approximation bound. Rather, one needs
to only run the original greedy algorithm for one iteration
(i.e., selecting the best single element of the set) and then
to return the maximum of the best single element
and the result of the modified greedy algorithm. The results ofdouble-greedy are guaranteed to be at
least as good as this and often better, but with an increase in computation
time.)


## 5.2.2. Triple-Greedy Algorithm

It turns out that by increasing the computation
further, but remaining polynomial time, it is possible to improve the
approximation bound to(1−e−1) for the constrained optimization problem,
which matches the result for the unconstrained problem, as proven in [31, 32]. The new algorithm simply
enumerates all triples of consecutive layers, denoted by T,
in each flow that do not violate the bandwidth constraint BW.
For each triple T,
the algorithm runs the modified greedy algorithm initialized to the set T then returns the set T′ among all of the triples that achieved the
highest ratio of the reduction in distortion to the increases in bandwidth.
This algorithm increases the runtime by a factor of O(|E|3) over the original greedy algorithm, but yields
a much stronger approximation result. We have the following result.Theorem 1.
Thedouble-greedy* and triple-greedy* algorithms achieve a
constant factor approximation bounds of 0.5(1−e−1) and 0.5(1−e−1),
respectively.Proof.
Due to space constraints, the reader is referred to the full
technical report for detail proofs of above results [33].


## 6. Simulation Results

In this
section, we provide a comprehensive evaluation of the proposed optimized
framework for video streaming in single-hop networks. In particular, the
simulations provide the visual quality of video streams, as measured by mean
square error (MSE), when admission control is employed in conjunction with different
layer allocation algorithms and the proposed MAC protocol. The layer allocation
algorithms of interest are the optimal, the equal rate, the greedy, and the
double greedy algorithms. We intentionally omit the results for the
triple-greedy algorithm since in our simulations, they are observed to be
identical to those of the double-greedy algorithm. This suggests that perhaps
for the bit rates and distortion levels of typical video layers, the
double-greedy algorithm is sufficient to obtain a good solution.We note that the optimal algorithm employs an
exhaustive search scheme. That is, it examines all the possible combinations of
video layers and chooses the one that results in the lowest distortion, that
is, smallest MSE that satisfies the bandwidth and distortion constraints. Thus,
the optimal algorithm is prohibitively expensive when the numbers of video
layers and hosts are large. The optimal algorithm, however, produces the
smallest MSE and is thus used to evaluate the goodness of other algorithms. The
equal rate algorithm allocates an equal amount of bandwidth to every video
(hosts), layer by layer in a round robin fashion until the constraint on total
used bandwidth is no longer satisfied. The greedy and double greedy algorithms
are previously described in Sections5.1 and 5.2,
respectively.In all our simulations, we use two sets of standard
video profiles, each set consists of three-layered videos, as shown in Tables1
and 2 [7, 34–37]. Depending on the
scenarios, a simulation may use either one or both sets of the video profiles.Table 1
Standard video profiles—set I.
LayerAkiyoCoastguardForemanBit rates (Kbps)Distortion (MSE)Reduction in distortion (MSE)Bit rates (Kbps)Distortion (MSE)Reduction in distortion (MSE)Bit rates (Kbps)Distortion (MSE)Reduction in distortion (MSE)164——32123.90—64——212883.77—112103.0620.8412871.30—319263.5420.2316087.7215.3419256.6314.67425650.4813.0620878.189.5425646.0310.60532038.2912.1925671.306.8832039.186.85638432.595.7030465.036.2738433.355.83744827.744.8535257.957.0844829.054.30851223.614.1340051.656.3051225.893.16Table 2
Standard video profiles—set II.
LayerForeman 1 (FGS-temporal scalability mode)Coastguard (FGS)Foreman 2 (FGS-AFP mode)Bit rates (Kbps)Distortion (MSE)Reduction in distortion (MSE)Bit rates (Kbps)Distortion (MSE)Reduction in distortion (MSE)Bit rates (Kbps)Distortion (MSE)Reduction in distortion (MSE)114057.03—11060.68—38442.96—224033.0523.9816051.659.0351231.1211.84334021.8911.1624043.967.6964026.434.69444016.305.5930038.295.6776822.553.88554011.464.8436031.127.1789619.193.3666408.672.7942026.484.63102417.911.2877407.241.4349024.162.33115215.961.9588405.871.3759020.563.60128014.221.7499404.591.2873017.503.06140813.270.951085014.892.611190011.563.33


### 6.1. Protocol Evaluation

We first
compare the performance of the proposed MAC protocol against the standard IEEE
802.11 without admission control [2]
and the IEEE 802.11e with admission control. In particular, for the IEEE
802.11e with admission control, we use the mechanism proposed by Banchs et al.
[4]. This mechanism is
somewhat similar to ours, in the sense that each flow i achieves its throughput by setting the
contention window CWi to an appropriate size. For our proposed MAC,
we can approximate CWi=2/pi.
The fundamental difference, however, is in the formulation which leads to two
different algorithms, and consequently different behaviors. In the IEEE 802.11e
with admission control, Banchs et al. formulated the admission control process
as maximizing the total throughput from all the flows subject to the constraint
on the relative throughput for each flow. In particular, the algorithm tries to
set the values of the contention window for each flow in such a way to maximize R=R1+R2+⋯RN,
while ensuring that R1/R1=n1,R2/R1=n2,…,RN/R1=nN, where N, Ri,
and {n1,…,nN} are the number of flows, the throughput rate
for flow i,
and a set of given requirements, respectively. Note that we randomly choose R1 as a reference flow. As a direct result, the
throughput obtained by each flow might be higher than what is specified,
especially when the specified aggregate throughput is much smaller than the network
capacity. On the other hand, our algorithm produces precisely the specified
rate for each flow. As will explained shortly, the ability to precisely control
the rate will enable an efficient cross-layer optimization.Our simulator is a time-driven, packet-based simulator
written in MATLAB. It is designed to mimic as close as possible to the real
operations using all the critical parameters in the IEEE 802.11e protocol. For
all the simulations, the parameters specified for frequency hopping spread spectrum
(FHSS) PHY layer with the channel capacity of 1 Mbps are shown in Table3. We
note that the MAChdr for IEEE 802.11e contains 2 bytes for a QoS field in addition to that
of IEEE 802.11. We also assume that the processing and propagation delays are
zero.Table 3
FHSS system parameters for IEEE 802.11e used to obtain numerical results.
ParameterValuePacket payload1500
bytesMAC
header (MAChdr)36
bytesPHY
header (PHYhdr)16
bytesRTS20bytes+PHYhdrCTS14 bytes+PHYhdrACK14 bytes+PHYhdrChannel capacity (BW)1 MbpsSlot
time50
microsecondsSIFS28
microsecondsDIFS128
microsecondsRTS
time out(RTS/BW×8×106)+DIFS microsecondsWe first show the simulation results for a single-hop
wireless network consisting of 3 hosts. Each host sends exactly one video to
other host over a limited channel capacity (BW) of 1 Mbps. These flows are assumed to be in
the same traffic class. The minimum throughput requirements for flows 1 (R1) and 2 (R2) are set to 200 Kbps and 300 Kbps,
respectively. The minimum throughput of flow 3 (R3) increases linearly from 115 Kbps to 370 Kbps
with a step size of 15 Kbps. For the IEEE 802.11e with admission control, CWi's are set according to the admission control
algorithm while for the standard IEEE 802.11 without admission control, CWmin and CWmax are set to 15 and 1023, respectively.Figures2(a)–2(c) show the observed throughputs for
IEEE 802.11 without admission control, IEEE 802.11e with admission control, and
our proposed admission control as a function of the flow 3's throughput. As
seen, the standard IEEE 802.11 performs well when the total requested
throughput is smaller than the network capacity. Without admission control,
however, flow 3 cannot achieve its requested throughput of greater than 320 Kbps. On the other hand, the IEEE 802.11e with admission control performs very
well as the throughput for each flow is consistently above its specified
minimum requirement. Unlike the IEEE 802.11e, our proposed admission control
produces a precise requested throughput for each flow. As a result, the
collision rate (wasted bandwidth) is much smaller than that of the standard and
the IEEE 802.11e as shown in Figure 2(d), even when the total useful
throughputs in both schemes are approximately the same. This is an advantage of
using the proposed MAC protocol. Not surprisingly, the total bandwidth usage
for our algorithm is much smaller than those of other protocols as shown in
Figure 2(e) for a specified set of rates.Performance comparisons for the
proposed protocol versus IEEE 802.11 and IEEE 802.11e protocols. (a) Throughput
for flow 1, (b) throughput for flow 2, (c) throughput for flow 3, (d) overall
collision, and (e) overall bandwidth usage.
(a)(b)(c)(d)(e)We now show the performance of the proposed
contention-based MAC protocols when a large number of hosts competing for a
shared medium. Specifically, we simulate a scenario consisting of 30 hosts, and
the bandwidth capacity is set to 54 Mbps. Each host injects one flow. The throughput
of flow 1 (R1) increases linearly from 120 Kbps to 460 Kbps
with a step size of 20 Kbps. The throughput of flow 2 (R2) increases linearly from 80 Kbps to 590 Kbps
with a step size of 30 Kbps. For the remaining flows (R3–R30), their throughput requirements are set to
200 Kbps. The parameters specified for direct sequence spread spectrum-orthogonal frequency division multiplexing (DSSS-OFDM) PHY layer with long preamble
PPDU format are shown in Table 4. In this simulation, the PHYhdr and the control packets (RTS/CTS/ACK) are sent at only 1 Mbps while
the data portion is sent at the full rate of 54 Mbps.Table 4
DSSS-OFDM system parameters for IEEE 802.11e used to obtain numerical results.
ParameterValuePacket payload1500
bytesCoding
rate3/4MAC
header (MAChdr)36
bytesPHY
header (PHYhdr)32
bytesRTS20bytes+PHYhdrCTS14 bytes+PHYhdrACK14 bytes+PHYhdrChannel capacity (BW)54 MbpsSlot
time20
microsecondsSIFS10
microsecondsDIFS50
microsecondsRTS
time out352
microsecondsFigures3(a)–3(d) show the observed throughputs  for
IEEE 802.11e resulted from using our proposed admission control as a function
of the flow 1's throughput. As seen, they all achieve the desired throughputs.
Note however, because PHYhdr portions and control packets are sent at much slower rate (1 Mbps),
this results in low rate of overall data portions as shown in Figure 3(e).
Also, the collision rate in our proposed protocol is about 1% of channel
capacity when the total bandwidth usage is 90%. Figure 3(f) represents the
transmission probability for each host corresponding to their requested
throughputs. As seen, our proposed MAC protocol performs reasonably well even
in the network with a large number of competing hosts.Proposed protocol validation with 30 flows over 54 Mbps
bandwidth. (a) Throughput for flows 1 and 2, (b) throughput for flows 3–10, (c)
throughput for flows 11–20, (d) throughput for flows 21–30, (e) overall
bandwidth usage, (f) transmission probability.
(a)(b)(c)(d)(e)(f)We now show the simulation results when applying
cross-layer optimization for transmitting 3 video flows. First, to provide some
intuitions about the interactions between the proposed MAC protocol and the
layer allocation algorithms described in Section5.2. Specifically, we present
the simulation results for various quantities, for example, throughputs,
transmission probabilities, when using a simple greedy layer allocation. The
simulation parameters are shown in Table 3. Since all video streams are in
the same traffic class, they use the same TXOP where TXOP=CTS+PHYhdr+MAChdr+PAYLOAD+ACK+3SIFS+DIFS. We use standard video profile set I in this
simulation. Figure 4(a) shows the average throughputs of different video streams increasing with
the normalized bandwidth usage. From left to right, each point in the graph
represents an additional layer being added to one of the videos according to
the greedy algorithm. The rightmost point denotes the final number of layers
for each video. Adding a layer to any video on each graph at this point would
violate the bandwidth constraint. In other words, with the addition of a new
layer, Algorithm 2 in Section 3 will not be able to find a set of
transmission probabilities that satisfies the requested rates for all the
videos. We note that, at this point, the total bandwidth usage is 95%,
indicating a relatively high-bandwidth utilization.Performance results using the greedy algorithm. (a) Throughput, (b)
transmission probability; (c) percentage ofS slots, (d) percentage of I, C,
and S slots, (e) distortion in MSE, (f)
rate-distortion characteristic.
(a)(b)(c)(d)(e)(f)Figure4(b) shows the transmission probabilities for
each host as a function of normalized bandwidth usage. As expected, as the
number of layers increases for each video, their transmission probabilities
also increase accordingly to ensure a higher chance for data transmissions. It
is interesting to note that the transmission probabilities increase almost
exponentially to compensate for roughly linear increase in the overall
throughput. Figure 4(c) shows the corresponding increases percentage of
successful slots (over the number of nondata slots) for different video
streams, as a direct result of an increase in transmission probabilities.However, as the transmission probabilities increase,
the percentage of collision slots also increases substantially as shown in
Figure4(d). Of course, the percentage of idle slots decreases accordingly.
This agrees with our intuition about the proposed MAC protocol. We note that by
using this MAC protocol, one is able to control the rate of the flows precisely
by tuning their transmission probabilities. These rates, in turn, control the
visual quality of the video streams. Figure 4(e) shows the
visual quality of the three video streams in terms of MSE as a function of
normalized bandwidth usage. In this case, the greedy algorithm, which minimizes
the total MSE for all the flows given the bandwidth constraint, yields an MSE
of 38, 71, and 46 for Akiyo, Coastguard, and Foreman sequences, respectively.
Figure 4(f) shows the actual bandwidth percentage for various packet types. As
seen, only minimal bandwidth overhead (2%) is incurred when using the RTS of 36
bytes and packet payload of 1500 bytes.


### 6.2. Layer Allocation Algorithm Performance

We now show the
performance of different layer allocation algorithms. For simplicity, we assume
there is no packet loss. Furthermore, by using standard video profiles
H.264/SVC in Table1, we require that the distortion levels (MSE) for Akiyo,
Coastguard, and Foreman cannot be greater than 63, 103, and 56, respectively.
For this simulation, these MSE values are chosen rather arbitrarily, but in
practice a user can specify his or her visual quality requirement. Figures 5(a)
and 5(b) show the distortions resulted from using different algorithms
for video profiles in Tables 1 and 2, respectively. For Table 2, the maximum
distortion requirements for Foreman 1, Coastguard, and Foreman 2 are 21, 51,
and 31, respectively. As expected, the optimal algorithm (exhaustive search)
always produces the lowest distortion, albeit it has the highest computational
cost.Distortion performances of different algorithms for
(a) video profiles in Table1, (b) video profiles in Table 2.
(a)(b)Figure5(a) shows that the performances of the greedy
and the double greedy are all identical for video profiles in Table 1. At 0.8 Mbps, the greedy and the double greedy algorithms fail to find the optimal
solutions. However, the performances of the greedy, the double greedy, and the
optimal algorithms are all identical at the capacity channel of 1 Mbps and 1.2 Mbps. This suggests that greedy and double greedy algorithms perhaps are
sufficient in practice. As expected, the equal rate algorithm performs worst
since it does not even try to minimize the overall distortion.On the other hand, Figure5(b) shows that the greedy
algorithm fails to find the optimal solutions in two instances (BW=1.6 Mbps and 2.4 Mbps). In contrast, the
double greedy algorithm typically finds the optimal solutions. This is,
however, not guaranteed as the double-greedy algorithm does not converge to
optimal solution for BW=1.6 Mbps. We note that as described in
Section 5.2, the computational cost of the double-greedy algorithm is twice
that of the greedy algorithm since it must run the greedy and modified greedy
algorithms and pick the best one. The modified greedy algorithm is the basic
greedy algorithm, where at each step instead of adding the layer that most
decreases the distortion,  we add the layer that achieves the largest ratio of
the reduction in distortion to the layer bit rate, provided that adding the
layer does not violate the bandwidth constraint. The modified greedy algorithm
might or might not produce a better solution than that of the greedy algorithm.
Both the greedy and modified algorithms can produce an arbitrarily bad
solution, while the double-greedy algorithm, which returns the best solution
(lower distortion) of the greedy and modified greedy algorithms, guarantees
that its solution is a constant approximation factor to the optimal solution.Tables5 and 6 show the detail information associated
with different algorithms for the video profiles I and II, respectively. As
seen, the optimal algorithm always achieved in the
lowest distortion. In all cases, the bandwidth overhead is relatively small,
indicating the ability of the framework to utilize the bandwidth efficiently.
Note that there are some other overhead bandwidths (i.e., PHYhdr, MAChdr, SIFS, DIFS, ACK) that amount to 8 to 10% of the total bandwidth.Table 5
Detail information associated with different
algorithms for video profiles I (BW=1.2 Mb/s).
DistortionNormalized bandwidth usage (%)Transmission probability(MSE)TotalOverheadSOverheadCThroughputOthersAkiyoCoastguardForemanOptimal solution129.1298.472.110.0787.868.430.02150.02690.0215Greedy129.1298.472.110.0787.868.430.02150.02690.0215Modified greedy129.1298.472.110.0787.868.430.02150.02690.0215Double greedy129.1298.472.110.0787.868.430.02150.02690.0215Equal rate135.4293.562.000.0283.528.020.00460.00510.0046Table 6
Detail information associated with different
algorithms for video profiles II (BW=2.4 Mb/s).
DistortionNormalized bandwidth usage (%)Transmission probability(MSE)TotalOverheadSOverheadCThroughputOthersForeman 1CoastguardForeman 2Optimal solution51.7895.862.010.0683.7410.050.01400.01290.0165Greedy52.0297.142.040.0884.8410.180.02030.01550.0280Modified greedy51.7895.862.010.0683.7410.050.01400.01290.0165Double greedy51.7895.862.010.0683.7410.050.01400.01290.0165Equal rate52.6096.472.020.0784.2610.120.01650.01860.0165


### 6.3. Throughput Jitter Evaluation

The proposed
optimization framework guarantees that each flow will achieve its required
throughput when it is averaged over a long period of time. However, the
throughputs of the flows may fluctuate within a short period of time due to the
probabilistic nature of the channel contention access. These throughput
fluctuations may prevent smooth playback for many audio and video streaming
applications. To alleviate this problem, many streaming applications employ the
prebuffering technique in which, the receiver puts the received data into a
buffer for a short period of time before starting to playback. A longer buffer
results in a smoother playback session. On the other hand, using a larger buffer
results in larger initial delay and required memory. Interactive applications
such as video conferencing may not tolerate such large delay, and the
low-power wireless hosts may not have enough memory
for buffering. Thus, it is important to characterize the throughput jitter
resulting from using the protocol.Figure6(a) shows the ratio of the actual throughputs
to the requested throughputs of different flows in video profiles I, averaged
over every 300 kbytes. The channel capacity is set to 1 Mbps. Figure 6(b) shows
throughput ratios for different flows in the video profiles II, averaged over
every 600 kbytes, with the capacity channel set to 2 Mbps. As seen, the
throughput ratios fluctuate around 1, indicating that all the flows achieve
their required throughputs. The magnitudes of these fluctuations are also small
(e.g., 0–20%) suggesting that one can use a small streaming buffer for smooth
playback.Throughput jitter for each flow for (a) video profiles
in Table1, (b) video profiles in Table 2.
(a)(b)In this simulation, we repeatedly transmit three
videos from video profiles I for 20 minutes. We want to quantify how long a
streaming buffer should be in order to prevent lost packets due to late
arrival. To prevent throughput fluctuation, we also request a slightly larger
bandwidth than the recorded video bit rate. This bandwidth safety margin
provides robustness against possible throughput depletion during a session.
Figure7(a) to Figure 7(d) show the number of late packets as a function of
streaming buffer length for various bandwidth safety margins.Percentage of
late packets as a function of streaming buffer length (in seconds); (a) 0%
bandwidth safety margin, (b) 1% bandwidth safety margin, (c) 2% bandwidth
safety margin, (d) 3% bandwidth safety margin. The bit rates of Akiyo,
Coastguard, and Foreman are 192, 160, and 256 Kbps, respectively.
(a)(b)(c)(d)As seen, to have no late packet with no bandwidth
safety margin, a user receiving Akiyo needs to wait on average, 48 seconds to
smoothly playback a 20-minute video. Users receiving Coastguard and Foreman
need to wait up to 88 and 40 seconds, respectively. However, the required
waiting time reduces with the increase in the bandwidth safety margin. For
example, using the bandwidth safety margin of 3%, the waiting times for Akiyo,
Coastguard, and Foreman users are reduced to 24, 32, and 12 seconds,
respectively.We also quantify the throughput jitter of a flow as
the normalized standard deviation of its fractional throughput
is within a number of time slots.
Specifically,(21)Stdevn(Xi(T))=Stdev(Xi(T))Ri′,where Xi(T) is a fraction of the data slots of the flow i measured within T time slots, and Ri′ denotes its average long-term fractional
throughput. Clearly, a larger T should result in a smaller normalized
throughput standard deviation since we average the throughput over a longer
period of time. It is straightforward to show that(22)Stdevn(Xi(T))=TXOPi×(1−∑i=1NRi′)×Si×(1−Si)Ri′T,where N denotes the number of flows and Si's denotes the number of successful time slots
for flow i.
(This result can be obtained by noticing that the number of successful
transmission slots within a period T is binomially distributed with parameters Si and T(1−∑i=1NRi′).)To quantify the normalized throughput standard
deviation, we simulate three flows withR1′, R2′,
and R3′ being set to 0.1, 0.27, and 0.4, respectively.
Figure 8 shows the normalized throughput standard deviations for three
different flows as a function of buffer size (T). As expected, as T increases, the normalized throughput standard
deviation decreases. However, increasing T implies an increase in playback delay.Figure 8
Normalized throughput standard deviation as a function of buffer size (T).


### 6.4. Overall Performance

We now compare
the performance of our proposed framework against the existing IEEE 802.11
without admission control and IEEE 802.11e with admission control proposed by
Banchs et al. [4]. To
simulate realistic settings, packet losses are introduced into the simulations.
For simplicity, we assume that packet loss rates are identical for all the
receivers. We also assume that a packet will be transmitted repeatedly until it
is received successfully. As a result, the useful throughput reduces with an
increase in packet loss rate. The admission control module is assumed to be
able to measure the packet loss rate, and thus can determine the overall
effective throughput. Using the overall effective throughput and the video
profiles as inputs, it can use different optimization strategies to allocate
bandwidths for receivers to minimize the average distortion.Figure9(a) shows the average distortion for various
strategies when streaming the videos in profile I. As expected, the optimal
strategy, that is, exhaustive search, always provides the smallest average
distortion. The double-greedy algorithm also performs equally well. The greedy
algorithm performs slightly worse, followed by the equal rate algorithm, the
IEEE 802.11 protocol without admission control, and IEEE 802.11e with admission
control. The main reason for the worse performances when using the IEEE 802.11
and the IEEE 802.11e is the lack of layer allocation optimization. For the IEEE
802.11, due to the random contention-based access where each flow has an equal
chance of accessing the shared channel, all three flows obtain approximately
the same throughputs. However, this is not the optimal allocation for
minimizing the overall distortion. Intuitively, the IEEE 802.11 should perform
as well as the equal rate allocation. On the other hand, the equal rate
allocation scheme uses the proposed admission control which results in smaller
collision bandwidth as compared to that of IEEE 802.11. As a result, the
average distortion of the equal rate scheme is typically lower than that of the
IEEE 802.11.Distortions resulted from using various
protocols: (a) using video profiles I with channel capacity set to 1 Mbps, (b)
using video profiles II with channel capacity set to 2 Mbps.
(a)(b)However, admission control mechanism alone does not
improve the quality of the video. To see this, let us consider the performance
of the IEEE 802.11e with admission control. Using this scheme, one is able to
guarantee the minimum throughput rate for each flow. However, if after
providing these minimum throughputs for the flows, there is still much bandwidth
available, then as designed, the IEEE 802.11e protocol would allow each flow to
increase its throughput proportionally until the wireless capacity is reached.
The final throughput of each flow as obtained by the admission control
algorithm then dictates the quality of a video. In other words, the layer
allocation employed in this case is to allocate the rate proportionally
according to the initial conditions. For example, if the minimum rates (or
equivalently maximum distortions) for three flows are specified initially 200 Kbps, 400 Kbps, and 400 Kbps, then with a channel capacity of 2 Mbps, the IEEE
802.11e protocol will roughly allocate 400 Kbps, 800 Kbps, and 800 Kbps for
these flows (for sake of illustration, we assume no collision bandwidth). Clearly,
this allocation is not optimal as it does not take into account the distortion
profile for each video. That said, there is no reason why the IEEE 802.11e with
admission control should perform better than the IEEE 802.11 or other schemes
when there is enough bandwidth. In fact, Figure9(b) shows that the IEEE
802.11e results in a larger average distortion consistently when using video
profiles II. Our proposed framework which integrates the admission control with
layer allocation optimization enables us to achieve the lowest distortion.
Overall, our proposed framework improves the video quality up to 26% over that
of a typical IEEE 802.11 based network.


## 6.1. Protocol Evaluation

We first
compare the performance of the proposed MAC protocol against the standard IEEE
802.11 without admission control [2]
and the IEEE 802.11e with admission control. In particular, for the IEEE
802.11e with admission control, we use the mechanism proposed by Banchs et al.
[4]. This mechanism is
somewhat similar to ours, in the sense that each flow i achieves its throughput by setting the
contention window CWi to an appropriate size. For our proposed MAC,
we can approximate CWi=2/pi.
The fundamental difference, however, is in the formulation which leads to two
different algorithms, and consequently different behaviors. In the IEEE 802.11e
with admission control, Banchs et al. formulated the admission control process
as maximizing the total throughput from all the flows subject to the constraint
on the relative throughput for each flow. In particular, the algorithm tries to
set the values of the contention window for each flow in such a way to maximize R=R1+R2+⋯RN,
while ensuring that R1/R1=n1,R2/R1=n2,…,RN/R1=nN, where N, Ri,
and {n1,…,nN} are the number of flows, the throughput rate
for flow i,
and a set of given requirements, respectively. Note that we randomly choose R1 as a reference flow. As a direct result, the
throughput obtained by each flow might be higher than what is specified,
especially when the specified aggregate throughput is much smaller than the network
capacity. On the other hand, our algorithm produces precisely the specified
rate for each flow. As will explained shortly, the ability to precisely control
the rate will enable an efficient cross-layer optimization.Our simulator is a time-driven, packet-based simulator
written in MATLAB. It is designed to mimic as close as possible to the real
operations using all the critical parameters in the IEEE 802.11e protocol. For
all the simulations, the parameters specified for frequency hopping spread spectrum
(FHSS) PHY layer with the channel capacity of 1 Mbps are shown in Table3. We
note that the MAChdr for IEEE 802.11e contains 2 bytes for a QoS field in addition to that
of IEEE 802.11. We also assume that the processing and propagation delays are
zero.Table 3
FHSS system parameters for IEEE 802.11e used to obtain numerical results.
ParameterValuePacket payload1500
bytesMAC
header (MAChdr)36
bytesPHY
header (PHYhdr)16
bytesRTS20bytes+PHYhdrCTS14 bytes+PHYhdrACK14 bytes+PHYhdrChannel capacity (BW)1 MbpsSlot
time50
microsecondsSIFS28
microsecondsDIFS128
microsecondsRTS
time out(RTS/BW×8×106)+DIFS microsecondsWe first show the simulation results for a single-hop
wireless network consisting of 3 hosts. Each host sends exactly one video to
other host over a limited channel capacity (BW) of 1 Mbps. These flows are assumed to be in
the same traffic class. The minimum throughput requirements for flows 1 (R1) and 2 (R2) are set to 200 Kbps and 300 Kbps,
respectively. The minimum throughput of flow 3 (R3) increases linearly from 115 Kbps to 370 Kbps
with a step size of 15 Kbps. For the IEEE 802.11e with admission control, CWi's are set according to the admission control
algorithm while for the standard IEEE 802.11 without admission control, CWmin and CWmax are set to 15 and 1023, respectively.Figures2(a)–2(c) show the observed throughputs for
IEEE 802.11 without admission control, IEEE 802.11e with admission control, and
our proposed admission control as a function of the flow 3's throughput. As
seen, the standard IEEE 802.11 performs well when the total requested
throughput is smaller than the network capacity. Without admission control,
however, flow 3 cannot achieve its requested throughput of greater than 320 Kbps. On the other hand, the IEEE 802.11e with admission control performs very
well as the throughput for each flow is consistently above its specified
minimum requirement. Unlike the IEEE 802.11e, our proposed admission control
produces a precise requested throughput for each flow. As a result, the
collision rate (wasted bandwidth) is much smaller than that of the standard and
the IEEE 802.11e as shown in Figure 2(d), even when the total useful
throughputs in both schemes are approximately the same. This is an advantage of
using the proposed MAC protocol. Not surprisingly, the total bandwidth usage
for our algorithm is much smaller than those of other protocols as shown in
Figure 2(e) for a specified set of rates.Performance comparisons for the
proposed protocol versus IEEE 802.11 and IEEE 802.11e protocols. (a) Throughput
for flow 1, (b) throughput for flow 2, (c) throughput for flow 3, (d) overall
collision, and (e) overall bandwidth usage.
(a)(b)(c)(d)(e)We now show the performance of the proposed
contention-based MAC protocols when a large number of hosts competing for a
shared medium. Specifically, we simulate a scenario consisting of 30 hosts, and
the bandwidth capacity is set to 54 Mbps. Each host injects one flow. The throughput
of flow 1 (R1) increases linearly from 120 Kbps to 460 Kbps
with a step size of 20 Kbps. The throughput of flow 2 (R2) increases linearly from 80 Kbps to 590 Kbps
with a step size of 30 Kbps. For the remaining flows (R3–R30), their throughput requirements are set to
200 Kbps. The parameters specified for direct sequence spread spectrum-orthogonal frequency division multiplexing (DSSS-OFDM) PHY layer with long preamble
PPDU format are shown in Table 4. In this simulation, the PHYhdr and the control packets (RTS/CTS/ACK) are sent at only 1 Mbps while
the data portion is sent at the full rate of 54 Mbps.Table 4
DSSS-OFDM system parameters for IEEE 802.11e used to obtain numerical results.
ParameterValuePacket payload1500
bytesCoding
rate3/4MAC
header (MAChdr)36
bytesPHY
header (PHYhdr)32
bytesRTS20bytes+PHYhdrCTS14 bytes+PHYhdrACK14 bytes+PHYhdrChannel capacity (BW)54 MbpsSlot
time20
microsecondsSIFS10
microsecondsDIFS50
microsecondsRTS
time out352
microsecondsFigures3(a)–3(d) show the observed throughputs  for
IEEE 802.11e resulted from using our proposed admission control as a function
of the flow 1's throughput. As seen, they all achieve the desired throughputs.
Note however, because PHYhdr portions and control packets are sent at much slower rate (1 Mbps),
this results in low rate of overall data portions as shown in Figure 3(e).
Also, the collision rate in our proposed protocol is about 1% of channel
capacity when the total bandwidth usage is 90%. Figure 3(f) represents the
transmission probability for each host corresponding to their requested
throughputs. As seen, our proposed MAC protocol performs reasonably well even
in the network with a large number of competing hosts.Proposed protocol validation with 30 flows over 54 Mbps
bandwidth. (a) Throughput for flows 1 and 2, (b) throughput for flows 3–10, (c)
throughput for flows 11–20, (d) throughput for flows 21–30, (e) overall
bandwidth usage, (f) transmission probability.
(a)(b)(c)(d)(e)(f)We now show the simulation results when applying
cross-layer optimization for transmitting 3 video flows. First, to provide some
intuitions about the interactions between the proposed MAC protocol and the
layer allocation algorithms described in Section5.2. Specifically, we present
the simulation results for various quantities, for example, throughputs,
transmission probabilities, when using a simple greedy layer allocation. The
simulation parameters are shown in Table 3. Since all video streams are in
the same traffic class, they use the same TXOP where TXOP=CTS+PHYhdr+MAChdr+PAYLOAD+ACK+3SIFS+DIFS. We use standard video profile set I in this
simulation. Figure 4(a) shows the average throughputs of different video streams increasing with
the normalized bandwidth usage. From left to right, each point in the graph
represents an additional layer being added to one of the videos according to
the greedy algorithm. The rightmost point denotes the final number of layers
for each video. Adding a layer to any video on each graph at this point would
violate the bandwidth constraint. In other words, with the addition of a new
layer, Algorithm 2 in Section 3 will not be able to find a set of
transmission probabilities that satisfies the requested rates for all the
videos. We note that, at this point, the total bandwidth usage is 95%,
indicating a relatively high-bandwidth utilization.Performance results using the greedy algorithm. (a) Throughput, (b)
transmission probability; (c) percentage ofS slots, (d) percentage of I, C,
and S slots, (e) distortion in MSE, (f)
rate-distortion characteristic.
(a)(b)(c)(d)(e)(f)Figure4(b) shows the transmission probabilities for
each host as a function of normalized bandwidth usage. As expected, as the
number of layers increases for each video, their transmission probabilities
also increase accordingly to ensure a higher chance for data transmissions. It
is interesting to note that the transmission probabilities increase almost
exponentially to compensate for roughly linear increase in the overall
throughput. Figure 4(c) shows the corresponding increases percentage of
successful slots (over the number of nondata slots) for different video
streams, as a direct result of an increase in transmission probabilities.However, as the transmission probabilities increase,
the percentage of collision slots also increases substantially as shown in
Figure4(d). Of course, the percentage of idle slots decreases accordingly.
This agrees with our intuition about the proposed MAC protocol. We note that by
using this MAC protocol, one is able to control the rate of the flows precisely
by tuning their transmission probabilities. These rates, in turn, control the
visual quality of the video streams. Figure 4(e) shows the
visual quality of the three video streams in terms of MSE as a function of
normalized bandwidth usage. In this case, the greedy algorithm, which minimizes
the total MSE for all the flows given the bandwidth constraint, yields an MSE
of 38, 71, and 46 for Akiyo, Coastguard, and Foreman sequences, respectively.
Figure 4(f) shows the actual bandwidth percentage for various packet types. As
seen, only minimal bandwidth overhead (2%) is incurred when using the RTS of 36
bytes and packet payload of 1500 bytes.


## 6.2. Layer Allocation Algorithm Performance

We now show the
performance of different layer allocation algorithms. For simplicity, we assume
there is no packet loss. Furthermore, by using standard video profiles
H.264/SVC in Table1, we require that the distortion levels (MSE) for Akiyo,
Coastguard, and Foreman cannot be greater than 63, 103, and 56, respectively.
For this simulation, these MSE values are chosen rather arbitrarily, but in
practice a user can specify his or her visual quality requirement. Figures 5(a)
and 5(b) show the distortions resulted from using different algorithms
for video profiles in Tables 1 and 2, respectively. For Table 2, the maximum
distortion requirements for Foreman 1, Coastguard, and Foreman 2 are 21, 51,
and 31, respectively. As expected, the optimal algorithm (exhaustive search)
always produces the lowest distortion, albeit it has the highest computational
cost.Distortion performances of different algorithms for
(a) video profiles in Table1, (b) video profiles in Table 2.
(a)(b)Figure5(a) shows that the performances of the greedy
and the double greedy are all identical for video profiles in Table 1. At 0.8 Mbps, the greedy and the double greedy algorithms fail to find the optimal
solutions. However, the performances of the greedy, the double greedy, and the
optimal algorithms are all identical at the capacity channel of 1 Mbps and 1.2 Mbps. This suggests that greedy and double greedy algorithms perhaps are
sufficient in practice. As expected, the equal rate algorithm performs worst
since it does not even try to minimize the overall distortion.On the other hand, Figure5(b) shows that the greedy
algorithm fails to find the optimal solutions in two instances (BW=1.6 Mbps and 2.4 Mbps). In contrast, the
double greedy algorithm typically finds the optimal solutions. This is,
however, not guaranteed as the double-greedy algorithm does not converge to
optimal solution for BW=1.6 Mbps. We note that as described in
Section 5.2, the computational cost of the double-greedy algorithm is twice
that of the greedy algorithm since it must run the greedy and modified greedy
algorithms and pick the best one. The modified greedy algorithm is the basic
greedy algorithm, where at each step instead of adding the layer that most
decreases the distortion,  we add the layer that achieves the largest ratio of
the reduction in distortion to the layer bit rate, provided that adding the
layer does not violate the bandwidth constraint. The modified greedy algorithm
might or might not produce a better solution than that of the greedy algorithm.
Both the greedy and modified algorithms can produce an arbitrarily bad
solution, while the double-greedy algorithm, which returns the best solution
(lower distortion) of the greedy and modified greedy algorithms, guarantees
that its solution is a constant approximation factor to the optimal solution.Tables5 and 6 show the detail information associated
with different algorithms for the video profiles I and II, respectively. As
seen, the optimal algorithm always achieved in the
lowest distortion. In all cases, the bandwidth overhead is relatively small,
indicating the ability of the framework to utilize the bandwidth efficiently.
Note that there are some other overhead bandwidths (i.e., PHYhdr, MAChdr, SIFS, DIFS, ACK) that amount to 8 to 10% of the total bandwidth.Table 5
Detail information associated with different
algorithms for video profiles I (BW=1.2 Mb/s).
DistortionNormalized bandwidth usage (%)Transmission probability(MSE)TotalOverheadSOverheadCThroughputOthersAkiyoCoastguardForemanOptimal solution129.1298.472.110.0787.868.430.02150.02690.0215Greedy129.1298.472.110.0787.868.430.02150.02690.0215Modified greedy129.1298.472.110.0787.868.430.02150.02690.0215Double greedy129.1298.472.110.0787.868.430.02150.02690.0215Equal rate135.4293.562.000.0283.528.020.00460.00510.0046Table 6
Detail information associated with different
algorithms for video profiles II (BW=2.4 Mb/s).
DistortionNormalized bandwidth usage (%)Transmission probability(MSE)TotalOverheadSOverheadCThroughputOthersForeman 1CoastguardForeman 2Optimal solution51.7895.862.010.0683.7410.050.01400.01290.0165Greedy52.0297.142.040.0884.8410.180.02030.01550.0280Modified greedy51.7895.862.010.0683.7410.050.01400.01290.0165Double greedy51.7895.862.010.0683.7410.050.01400.01290.0165Equal rate52.6096.472.020.0784.2610.120.01650.01860.0165


## 6.3. Throughput Jitter Evaluation

The proposed
optimization framework guarantees that each flow will achieve its required
throughput when it is averaged over a long period of time. However, the
throughputs of the flows may fluctuate within a short period of time due to the
probabilistic nature of the channel contention access. These throughput
fluctuations may prevent smooth playback for many audio and video streaming
applications. To alleviate this problem, many streaming applications employ the
prebuffering technique in which, the receiver puts the received data into a
buffer for a short period of time before starting to playback. A longer buffer
results in a smoother playback session. On the other hand, using a larger buffer
results in larger initial delay and required memory. Interactive applications
such as video conferencing may not tolerate such large delay, and the
low-power wireless hosts may not have enough memory
for buffering. Thus, it is important to characterize the throughput jitter
resulting from using the protocol.Figure6(a) shows the ratio of the actual throughputs
to the requested throughputs of different flows in video profiles I, averaged
over every 300 kbytes. The channel capacity is set to 1 Mbps. Figure 6(b) shows
throughput ratios for different flows in the video profiles II, averaged over
every 600 kbytes, with the capacity channel set to 2 Mbps. As seen, the
throughput ratios fluctuate around 1, indicating that all the flows achieve
their required throughputs. The magnitudes of these fluctuations are also small
(e.g., 0–20%) suggesting that one can use a small streaming buffer for smooth
playback.Throughput jitter for each flow for (a) video profiles
in Table1, (b) video profiles in Table 2.
(a)(b)In this simulation, we repeatedly transmit three
videos from video profiles I for 20 minutes. We want to quantify how long a
streaming buffer should be in order to prevent lost packets due to late
arrival. To prevent throughput fluctuation, we also request a slightly larger
bandwidth than the recorded video bit rate. This bandwidth safety margin
provides robustness against possible throughput depletion during a session.
Figure7(a) to Figure 7(d) show the number of late packets as a function of
streaming buffer length for various bandwidth safety margins.Percentage of
late packets as a function of streaming buffer length (in seconds); (a) 0%
bandwidth safety margin, (b) 1% bandwidth safety margin, (c) 2% bandwidth
safety margin, (d) 3% bandwidth safety margin. The bit rates of Akiyo,
Coastguard, and Foreman are 192, 160, and 256 Kbps, respectively.
(a)(b)(c)(d)As seen, to have no late packet with no bandwidth
safety margin, a user receiving Akiyo needs to wait on average, 48 seconds to
smoothly playback a 20-minute video. Users receiving Coastguard and Foreman
need to wait up to 88 and 40 seconds, respectively. However, the required
waiting time reduces with the increase in the bandwidth safety margin. For
example, using the bandwidth safety margin of 3%, the waiting times for Akiyo,
Coastguard, and Foreman users are reduced to 24, 32, and 12 seconds,
respectively.We also quantify the throughput jitter of a flow as
the normalized standard deviation of its fractional throughput
is within a number of time slots.
Specifically,(21)Stdevn(Xi(T))=Stdev(Xi(T))Ri′,where Xi(T) is a fraction of the data slots of the flow i measured within T time slots, and Ri′ denotes its average long-term fractional
throughput. Clearly, a larger T should result in a smaller normalized
throughput standard deviation since we average the throughput over a longer
period of time. It is straightforward to show that(22)Stdevn(Xi(T))=TXOPi×(1−∑i=1NRi′)×Si×(1−Si)Ri′T,where N denotes the number of flows and Si's denotes the number of successful time slots
for flow i.
(This result can be obtained by noticing that the number of successful
transmission slots within a period T is binomially distributed with parameters Si and T(1−∑i=1NRi′).)To quantify the normalized throughput standard
deviation, we simulate three flows withR1′, R2′,
and R3′ being set to 0.1, 0.27, and 0.4, respectively.
Figure 8 shows the normalized throughput standard deviations for three
different flows as a function of buffer size (T). As expected, as T increases, the normalized throughput standard
deviation decreases. However, increasing T implies an increase in playback delay.Figure 8
Normalized throughput standard deviation as a function of buffer size (T).


## 6.4. Overall Performance

We now compare
the performance of our proposed framework against the existing IEEE 802.11
without admission control and IEEE 802.11e with admission control proposed by
Banchs et al. [4]. To
simulate realistic settings, packet losses are introduced into the simulations.
For simplicity, we assume that packet loss rates are identical for all the
receivers. We also assume that a packet will be transmitted repeatedly until it
is received successfully. As a result, the useful throughput reduces with an
increase in packet loss rate. The admission control module is assumed to be
able to measure the packet loss rate, and thus can determine the overall
effective throughput. Using the overall effective throughput and the video
profiles as inputs, it can use different optimization strategies to allocate
bandwidths for receivers to minimize the average distortion.Figure9(a) shows the average distortion for various
strategies when streaming the videos in profile I. As expected, the optimal
strategy, that is, exhaustive search, always provides the smallest average
distortion. The double-greedy algorithm also performs equally well. The greedy
algorithm performs slightly worse, followed by the equal rate algorithm, the
IEEE 802.11 protocol without admission control, and IEEE 802.11e with admission
control. The main reason for the worse performances when using the IEEE 802.11
and the IEEE 802.11e is the lack of layer allocation optimization. For the IEEE
802.11, due to the random contention-based access where each flow has an equal
chance of accessing the shared channel, all three flows obtain approximately
the same throughputs. However, this is not the optimal allocation for
minimizing the overall distortion. Intuitively, the IEEE 802.11 should perform
as well as the equal rate allocation. On the other hand, the equal rate
allocation scheme uses the proposed admission control which results in smaller
collision bandwidth as compared to that of IEEE 802.11. As a result, the
average distortion of the equal rate scheme is typically lower than that of the
IEEE 802.11.Distortions resulted from using various
protocols: (a) using video profiles I with channel capacity set to 1 Mbps, (b)
using video profiles II with channel capacity set to 2 Mbps.
(a)(b)However, admission control mechanism alone does not
improve the quality of the video. To see this, let us consider the performance
of the IEEE 802.11e with admission control. Using this scheme, one is able to
guarantee the minimum throughput rate for each flow. However, if after
providing these minimum throughputs for the flows, there is still much bandwidth
available, then as designed, the IEEE 802.11e protocol would allow each flow to
increase its throughput proportionally until the wireless capacity is reached.
The final throughput of each flow as obtained by the admission control
algorithm then dictates the quality of a video. In other words, the layer
allocation employed in this case is to allocate the rate proportionally
according to the initial conditions. For example, if the minimum rates (or
equivalently maximum distortions) for three flows are specified initially 200 Kbps, 400 Kbps, and 400 Kbps, then with a channel capacity of 2 Mbps, the IEEE
802.11e protocol will roughly allocate 400 Kbps, 800 Kbps, and 800 Kbps for
these flows (for sake of illustration, we assume no collision bandwidth). Clearly,
this allocation is not optimal as it does not take into account the distortion
profile for each video. That said, there is no reason why the IEEE 802.11e with
admission control should perform better than the IEEE 802.11 or other schemes
when there is enough bandwidth. In fact, Figure9(b) shows that the IEEE
802.11e results in a larger average distortion consistently when using video
profiles II. Our proposed framework which integrates the admission control with
layer allocation optimization enables us to achieve the lowest distortion.
Overall, our proposed framework improves the video quality up to 26% over that
of a typical IEEE 802.11 based network.


## 7. Conclusions

We have
proposed a framework to enhance the quality of video streaming applications in
wireless home networks via a joint optimization of video layer-allocation technique,
admission control algorithm, and MAC protocol. Using an Aloha-like MAC
protocol, our admission control framework which can be viewed as an
optimization problem that maximizes the average quality of admitted videos,
given a specified minimum video quality for each flow. We provided some
hardness results for the optimization problem under various conditions and
proposed two heuristic algorithms for obtaining a good solution. In particular,
we showed that a simple greedy layer-allocation algorithm can perform
reasonable well, although it is typically not optimal. Consequently, we
presented a more expensive heuristic algorithm that guarantees to approximate
the optimal solution within a constant factor. Based on our scenario,
simulation results demonstrated that our proposed framework can improve the
video quality up to 26% as compared to those of the existing approaches.



---

*Source: 928521-2008-07-14.xml*