## Ishizaki-lab.net

**Statistical Time-Access Fairness Index of One-Bit**
**Feedback Fair Scheduler**
Department of Systems Design and Engineering
diversity comes from the fact that the wireless channel state
Since the utilization of multiuser diversity in wireless net-
processes of diﬀerent users are usually independent for the
works can increase the information theoretic capacity, much
same shared medium. Since the utilization of multiuser di-
attention has been paid to schedulers exploiting multiuser
versity in wireless networks can increase the information the-oretic capacity, much attention has been paid to schedulers
diversity. It is known that there exists a tradeoﬀ between
exploiting multiuser diversity (see, e.g., [5, 8, 10, 14, 19] and
the capacity and fairness achieved by schedulers exploiting
multiuser diversity. Due to its good balance between the
To achieve the eﬃcient use of the bandwidth, multiuser
capacity and fairness, the one-bit feedback fair scheduler is
diversity can be exploited, for instance, in such a way that
considered as an attractive choice. The fairness is classi-
the scheduler in the BS (Base Station) selects the MS (Mo-
ﬁed into short term fairness and long term fairness. It isknown that the one-bit feedback fair scheduler has an ideal
bile Station) whose received SNR (Signal-to-Noise Ratio) is
long term fairness property. However, the short term fair-
the largest, and transmits packets to the selected MS at
ness properties of the scheduler have not been suﬃciently
each time slot. This scheduling scheme maximizes the in-
explored yet. Since packet level performances of individ-
formation theoretic capacity of the overall system, but it
ual MSs (Mobile Stations) are strongly aﬀected by short
becomes highly unfair when there are MSs having very dis-
term fairness, it is also important to examine the short term
parate channel conditions [22]. To solve this unfair problem,
fairness of the schedulers. In this paper, we focus on the
the proportional fair (PF) scheduling was proposed wherethe scheduler considers the

*normalized *SNR values of MSs,
short term fairness of the one-bit feedback fair scheduler.

deﬁned by the received SNR values divided by their corre-
As a short term fairness index, we consider the statistical
sponding average received SNR values, and selects the MS
time-access fairness index (STAFI). We then develop two
whose normalized SNR value is the largest. The PF schedul-
numerical methods to understand the transient properties
ing provides

*strict fairness *among MSs because the normal-
of the STAFI of the one-bit feedback fair scheduler. The
ized SNR values are i.i.d. (independent and identically dis-
ﬁrst method calculates the exact value of the STAFI by us-ing the inverse discrete FFT method. The second method
tributed) among MSs [22]. Here, strict fairness means that
estimates the asymptotic decay rate of the STAFI by using
the access probabilities of MSs to the wireless channel are
In practice, the normalized SNR values are quantized and
the quantized normalized SNR values are reported to the
BS by MSs. The PF scheduling is then performed at the
multiuser diversity, one-bit feedback fair scheduler, short
BS based on the quantized normalized SNR values. This
PF scheduling is called the QPF (Quantized PF) schedul-ing [4, 9].

In general, the information theoretic capacity
achieved by the QPF scheduler increases and approachesto that achieved by the PF scheduler as the number of its
In wireless networks, scheduling for eﬃcient bandwidth
quantization levels increases. On the other hand, from the
utilization is a key component to the success of quality-
viewpoint of reducing the feedback overheads (for report-
of-service (QoS) guarantees. One way to achieve eﬃcient
ing the quantized normalized SNRs) from MSs to the BS, a
bandwidth utilization of time-varying wireless channel is to
small number of quantization levels is desirable. For the re-
exploit diversity. Multiuser diversity [11] is a diversity ex-
duction of the feedback overheads, the one-bit feedback fair
isting between the channel states of diﬀerent users. This
scheduler, which is the QPF scheduler with two quantizationlevels, is considered as one of good candidates to implementin practice [3, 6, 7, 15, 16, 18, 20, 23]. It is reported that
Permission to make digital or hard copies of all or part of this work for
the one-bit feedback fair scheduler can achieve a relatively
personal or classroom use is granted without fee provided that copies are
good capacity if the quantization levels are appropriately
not made or distributed for profit or commercial advantage and that copies
determined [6]. It is known that the one-bit feedback fair
bear this notice and the full citation on the first page. To copy otherwise, to
scheduler also provides strict fairness among MSs.

republish, to post on servers or to redistribute to lists, requires prior specific
In this paper, we focus on the fairness of the one-bit feed-
permission and/or a fee.

*QTNA *2011, Aug. 23-26, 2011, Seoul, Korea
back fair scheduler. The fairness is classiﬁed into short term
Copyright 2011 ACM 978-1-4503-0758-1/11/08 .$10.00.

fairness and long term fairness [7, 18]. Short term fairness
indicates the ability of the scheduler on how equally it can
distribute network resources (e.g., service times) over mul-
tiple MSs in a ﬁnite observation period. On the other hand,long term fairness indicates the ability of the scheduler on
how equally it can distribute network resources over multi-
ple MSs in an inﬁnite observation period. Thus, long termfairness governs the (long run) average throughput of indi-vidual MSs, while short term fairness greatly aﬀects packetlevel performances such as delay and loss probability of in-
dividual MSs. Although the strict fairness mentioned aboveis ideal fairness for long term fairness, it does not guaranteegood fairness for short term fairness. Hence it is important
to examine the short term fairness of schedulers as well asthe long term fairness.

In wireline networks, the proportional fairness index is
usually used as a measure of short term fairness, and it char-

**Figure 1: System model**
acterizes the service discrepancy between two ﬂows

*i *and

*j*over any time interval [

*t*1

*, t*2) during which the two ﬂows arecontinuously backlogged. A fair scheduler for wireline net-
the STAFI where the assigned weights

*φi *in (2) are all equal
works guarantees the proportional fairness index to have a
to one. As mentioned above, it is known that the one-bit
feedback fair scheduler provides strict fairness, which means
an ideal long term fairness property. However, there are only
a few studies on the short term fairness properties of the one-
bit feedback fair scheduler [7] and they have not been suﬃ-
ciently explored yet, although the packet level performances

*i*(

*t*1

*, t*2) denotes the service in bits that ﬂow

*i *re-
of individual MSs are strongly aﬀected by the short term
1

*, t*2),

*φi *denotes the assigned weight for ﬂow
fairness. In this paper, we develop two numerical methods

*i,j *is a constant which may depend on

*i *and

*j*. How-
ever, the proportional fairness index for wireline networks
to understand the transient properties of the STAFI of the
is not suitable for wireless networks. First, the hard de-
one-bit feedback fair scheduler. The ﬁrst method calculates
terministic guarantee where the proportional fairness index
the exact value of the STAFI by using the inverse discrete
always satisﬁes (1) does not take randomness inherent in the
FFT method. It enables us to precisely observe how the
wireless channel conditions into account. As a result, if we
STAFI changes as the progress of time. The second method
require the hard deterministic guarantee, schedulers do not
estimates the asymptotic decay rate of the STAFI by using
have the ﬂexibility to exploit short term channel variations
the theory of large deviations. It enables us to predict how
and to select users with better channel conditions (i.e., the
fast the STAFI approaches to ideal fairness as the progress
ﬂexibility to exploit multiuser diversity). Second, the pro-
portional fairness index considers fairness of users’ through-
The remainder of this paper is organized as follows. In
puts rather than channel access times. In wireless networks,
Section 2, we describe a system model considered in this pa-
users can transmit at diﬀerent rates depending on their cur-
per. We assume that the wireless channel process for each
rent channel quality. Thus, to normalize throughputs would
user is modeled by a discrete-time two-state Markov chain
require allowing the user with the worst channel quality to
and the channel processes are stationary.

have a disproportionately large share of channel access time.

sumptions, we analyze the STAFI of the one-bit feedback
This degrades the throughput performance of wireless net-
fair scheduler in Section 3. We then develop the two nu-
works. Hence, instead of the hard deterministic proportional
merical methods based on the analysis. Section 4 provides
fairness index, we need a more suitable short term fairness
numerical results to examine the transient statistical fairness
measure for wireless networks. To resolve those problems
properties of the one-bit feedback fair scheduler. Conclusion
which the proportional fairness index has, Liu et al. [13]
consider modiﬁcations to the proportional fairness index. Tomake the distinction between temporal and throughput fair-
ness, they deﬁne

*α*(

*t*1

*, t*2) as the service in

*time *(instead of
In this paper, we consider a wireless network consisting of

*W *(

*t*1

*, t*2) as the service in bits) that ﬂow

*i *receives during
a BS and

*K *MSs as shown in Fig. 1. We suppose that the
[

*t*1

*, t*2). Then, by relaxing the hard deterministic fairness
BS employs the one-bit feedback fair scheduler for downlink
guarantee to be a statistical one, they propose a

*statistical*
transmission from the BS to the MSs. We focus on downlink

*time-access fairness index *(STAFI) deﬁned as
transmission and analyze the STAFI of the one-bit feedback
We assume that the downlink channel of MS

*i *(

*i *= 1

*, . . . , K*)
is described by a Rayleigh fading channel model. Time axis
where

*f *(

*i, j, x*) is a probability distribution which may de-
is divided into physical (PHY) frames of equal size

*Tf *(sec)
and time index is given by

*t *= 0

*, *1

*, *2

*, · · · *. The PHY frame
In this paper, we focus on the one-bit feedback fair sched-
duration

*Tf *is considered to be the unit time in our model.

uler and study the STAFI of the scheduler to explore its
Then, the received SNR process

*{z*(

*i*)(

*t*)

*} *(

*t *= 0

*, *1

*, . . .*) of
short term fairness properties. In particular, we consider
MS

*i *(

*i *= 1

*, . . . , K*) is a stationary stochastic process and

*z*(

*i*)(

*t*) at time

*t *is according to the following exponential
where

*fd *denotes the mobility-induced Doppler spread of
MSs and we assume that for all the MSs, the mobility-induced Doppler spreads are identical.

P

*{z*(

*i*)(

*t*)

*≤ x} *= 1

*− *exp(

*−x/*¯
We next consider the stationary probability vector

**s **=

*z*(

*i*) denotes the average received SNR of MS

*i *and
(

*s*0

*, s*1) of the 2-state discrete-time Markov chain

*{s*(

*i*)(

*t*)

*}*.

*z*(

*i*) = E[

*z*(

*i*)(

*t*)]. We assume that the received
Note here that for all the MSs, the channel state processes
SNR processes of the

*K *MSs are independent with each
have the same stationary probability vector due to the nor-
malization of the received SNRs. From (3), the stationaryprobability vector is given by

*s*0 = 1

*− e−γ*1

*,*
Under the one-bit feedback fair scheduling, the

*normal-*
*ized *SNR processes of MSs are considered, where the nor-
The state transition probabilities are then determined by
malized SNR process is deﬁned by the process

*{z*(

*i*)(

*t*)

*/*¯
(

*i *= 1

*, . . . , K*). To reduce the feedback overheads for re-
porting the normalized SNR from MSs to the BS, each MSquantizes or partitions the entire normalized SNR range into

*p*0

*,*0 = 1

*− p*0

*,*1

*,*
*p*1

*,*1 = 1

*− p*1

*,*0

*,*
two grades with threshold denoted by

*γ*1. We assume that

*i *(

*i *= 0

*, *1) and

*χ*(

*γ*1) are given by (5) and (4), re-
1 is

*a priori *determined. If

*z*(

*i*)(

*t*)

*/ *¯
spectively. (6) and (7) determine the transition probabil-
we say that the wireless channel state of MS

*i *is in state
ity matrix

**P **of the 2-state Markov chain, whose stationary

0 at time

*t*. If

*z*(

*i*)(

*t*)

*/*¯

*z*(

*i*)

*≥ γ*1, we say that the wireless
channel state of MS

*i *is in state 1 at time

*t*. We assumethat perfect channel estimation is possible at each MS andeach MS knows its average SNR ¯

*z*(

*i*) (

*i *= 1

*, . . . , K*). Then
MS

*i *can determine the grade of its channel to the BS with
Without loss of generality, we analyze the STAFI between
the knowledge of its normalized SNR.

MS 1 and and MS 2. To express the STAFI between MS
The one-bit feedback fair scheduler then operates as fol-
1 and MS 2, we introduce an auxiliary i.i.d. (independent
and identically distributed) stochastic sequence

*{v*(

*t*)

*} *(

*t *=0

*, *1

*, . . .*) according to the uniform distribution on [0

*, *1). We

*• *At every time

*t*, MS

*i *estimates its received normalized
also deﬁne a random variable

*ν*(

*t*) (

*t *= 0

*, *1

*, . . .*) by
SNR

*z*(

*i*)(

*t*)

*/*¯

*z*(

*i*) and examines if

*z*(

*i*)(

*t*)

*/*¯

*I*(

*s*(

*k*)(

*t*) = 1)

*,*
*• *If

*z*(

*i*)(

*t*)

*/*¯

*z*(

*i*) is greater than or equal to the threshold

*γ*1 (i.e., the wireless channel state of MS

*i *is in state
where

*I*(

*·*) denotes the indicator function. Note here that the
1), MS

*i *transmits on-bit feedback information to the
random variable

*ν*(

*t*) represents the number of MSs in state
BS. Otherwise (i.e., if the wireless channel state of MS
1 at time

*t*. Let

*c*(

*i*)(

*t*) (

*i *= 1

*, . . . , K*;

*t *= 0

*, *1

*, . . .*) denote a

*i *is in state 0), MS

*i *does not feedback any information
random variable representing the amount of service of MS
to the BS. We assume that the one-bit feedback infor-

*i *at time

*t*, i.e.,

*c*(

*i*)(

*t*) = 1 when the one-bit feedback fair
mation is transmitted through an error-free feedback
scheduler selects MS

*i *for downlink transmission at time

*t*,
channel from MSs to the BS without delay.

and

*c*(

*i*)(

*t*) = 0 otherwise.

*c*(1)(

*t*) and

*c*(2)(

*t*) can be expressed
For downlink transmission, the one-bit feedback sched-
uler at the BS randomly selects one of MSs which feed
< 1 (

*s*(1)(

*t*) = 1

*, v*(

*t*)

*∈ *[0

*, *1

*/ν*(

*t*)))

*,*
back at time

*t*. If there are no MSs who feed back, then
(

*ν*(

*t*) = 0

*, v*(

*t*)

*∈ *[0

*, *1

*/K*))

*,*
the scheduler randomly selects one of the

*K *MSs.

The scheduling is performed PHY frame-by-frame.

> 1 (

*s*(2)(

*t*) = 1

*,*
*v*(

*t*)

*∈ *[

*s*(1)(

*t*)

*/ν*(

*t*)

*, *(

*s*(1)(

*t*) + 1)

*/ν*(

*t*)])

*,*
*c*(2)(

*t*) = > 1 (

*ν*(

*t*) = 0

*,v*(

*t*)

*∈ *[1

*/K,*2

*/K*))

*,*
In this subsection, we consider a wireless channel state
process of MS

*i *(

*i *= 1

*, . . . , K*). Let

*{s*(

*i*)(

*t*)

*} *(

*t *= 0

*, *1

*, . . . *;

*i *=1

*, . . . , K*) denote the wireless channel state process of MS

*i*,
The amount service

*α*(

*i*)(

*t*0

*, t*0 +

*n*) for MS

*i *in [

*t*0

*, t*0 +

*n*) is
where

*s*(

*i*)(

*t*) = 1 if

*z*(

*i*)(

*t*)

*/*¯
1 and

*s*(

*i*)(

*t*) = 0 oth-
erwise. We assume that the channel state process

*{s*(

*i*)(

*t*)

*}*
(

*t *= 0

*, *1

*, . . . *;

*i *= 1

*, . . . , K*) of MS

*i *is well described by a

*α*(

*i*)(

*t*0

*, t*0 +

*n*) =
stationary discrete-time 2-state Markov chain [7, 12]. Let

**P **= (

*pi,j*) (

*i, j *= 0

*, *1) denote the transition probability

We are now ready to provide an expression of the STAFI of
matrix of the 2-state Markov chain. The transition prob-
the one-bit feedback fair scheduler. Let

*G*
ability matrix

**P **is determined as follows (for the detailed

*n*(

*x*) (

*n *= 1

*, *2

*, . . .*)
derivation of the transition probabilities, see [12]). We ﬁrst
consider the level crossing rate

*χ*(

*γ*) of the received normal-

*Gn*(

*x*) = P(

*|α*(1)(

*t*0

*, t*0 +

*n*)

*− α*(2)(

*t*0

*, t*0 +

*n*)

*| ≥ x*)
for any

*t*0. Note here that since we have assumed that all the
channel state processes are stationary,

*Gn*(

*x*) is independent
0. We further deﬁne the probability mass function

*gn*(

*x*)
series of

*z *as

*ηn*(

*z*) =

*l*=

*−n lzl*, where

*cl *(

*l *=

*−n, . . . , n*)
(

*n *= 1

*, *2

*, . . .*) by
is a (unknown) real constant satisfying 0

*≤ cl ≤ *1 and
Then the probability mass function

*gn*(

*x*)

*gn*(

*x*) = P(

*|α*(1)(

*t*0

*, t*0 +

*n*)

*− α*(2)(

*t*0

*, t*0 +

*n*)

*| *=

*x*)

*.*
is expressed as

*gn*(

*x*) =

*cx *+

*c−x*. Thus, if we determine the
In what follows, we analyze the STAFI

*G*
*l*=

*−n*, we obtain the probability
purpose, we deﬁne some matrices and vectors. We ﬁrst de-
mass function

*gn*(

*x*). The STAFI

*Gn*(

*x*) is then given by
ﬁne a (

*K − *1)

*× *(

*K − *1) matrix

**R **by

*n*(

*l*) = 1

*− *P

*x−*1
There are several possible methods to determine the un-
known real constants

*{cl}nl*=

*−n*. In this paper, we use the
[

**R**]

*i,j*
*inverse discrete FFT method *[17] to determine them. Since

*n*(

*x*) has a ﬁnite support, i.e.,

*gn*(

*x*) = 0 for

*x > n*, we
can calculate the exact value of

*gn*(

*x*) by using the inverse

*· K − *2

*− i pj−kpK−*2

*−i−j*+

*k,*
discrete FFT method. By using this method, we can pre-
cisely observe how the STAFI

*Gn*(

*x*) or the probability massfunction

*g*
where [

**R**]

*n*(

*x*) changes as the progress of time (i.e., with the

*i,j *(

*i, j *= 0

*, . . . , K − *2) denotes the (

*i, j*)th element
of

**R**. Note that

**R **is a transition probability matrix of the

For comparison, we consider a random scheduler which
Markov chain

*{r*(

*t*)

*} *(

*t *= 0

*, *1

*, . . .*), where

*r*(

*t*) is deﬁned
randomly selects a MS among

*K *MSs irrespective of their

*I*(

*s*(

*k*)(

*t*) = 1). Thus, [

**R**]

received SNR. For the STAFI of the random scheduler, we
conditional probability that

*j *MSs among the (

*K − *2) MSs
(excluding MS 1 and MS 2) are in state 1 at time

*t *given

*n*(

*z*) (

*n *= 1

*, *2

*, . . .*) by
that

*i *MSs among the (

*K − *2) MSs was in state 1 at time

*t − *1. Let

**r **denote the stationary probability vector of

**R**.

The stationary probability vector

**r **is given by

which corresponds to

*ηn*(

*z*) of the one-bit feedback fair sched-
[

**r**]

uler. Similar to the case of the one-bit feedback fair sched-

*ηn*(

*z*), we can calculate the exact value the STAFI
where [

**r**]

*n*(

*x*) and its probability mass function ˜

*j *(

*j *= 0

*, . . . , K − *2) denotes the

*j*th element of

**r**,

and

*s*0 and

*s*1 are given by (5). We then deﬁne a 4(

*K − *1)

*×*
Although the numerical method based on the inverse dis-
4(

*K − *1) matrix

**Q **by

crete FFT method provides the exact value of the STAFI

**Q **=

**P **⊗ **P **⊗ **R**,
*Gn*(

*x*), it is time-consuming when

*n *is large. It is thus dif-ﬁcult to get the exact value of the STAFI

*Gn*(

*x*) for large
where

*⊗ *denotes the Kronecker product,

**P **is determined

value of

*n*. However, by using the theory of large deviations,
by (6) and (7), and

**R **is deﬁned by (8).

we can estimate how fast the STAFI

*Gn*(

*nx*) decreases as
We next deﬁne a 4(

*K − *1)

*× *4(

*K − *1) diagonal matrix

*n → ∞*. In other words, we can predict how fast the STAFI

**D**(

*z*) by

approaches to ideal fairness as the progress of time. The

**D**(

*z*) = diag(

**d**
following Proposition shows that the STAFI

*G*
0

*,*0(

*z*)

*, ***d**0

*,*1(

*z*)

*, ***d**1

*,*0(

*z*)

*, ***d**1

*,*1(

*z*))

*,*
nentially decreases as

*n → ∞ *(for the derivation, see, e.g.,
where

**d**i,j (

*z*) (

*i, j *= 0

*, *1) is a 1

*× *(

*K − *1) vector given by

<

*z *+

*z−*1 +

*K − *2

**Proposition **1.

[

**d**
log

*Gn*(

*nx*) =

*− *min[Λ

*∗*(

*x*)

*, *Λ

*∗*(

*−x*)]

*,*
*where *Λ

*∗*(

*a*)

*is defined by *Λ

*∗*(

*a*) = sup [

*θa − *log

*δ*
[

**d**0

*,*1(

*z*)]

*k *=

*δC *(

*θ*)

*denotes the Perron-Frobenius eigenvalue of the ma-*

trix **C **(

*eθ*)

*.*
We hereafter call the term min[Λ

*∗*(

*x*)

*, *Λ

*∗*(

*−x*)] in Propo-
[

**d**1

*,*0(

*z*)]

*k *=

[

**d**1

*,*1(

*z*)]

*k *=

sition 1 the asymptotic decay rate of the STAFI

*Gn*(

*nx*).

for

*k *= 0

*, . . . , K − *2.

**Remark **1.

From the property of Λ

*∗*(

*x*), it can be shown
We then deﬁne 4(

*K *1)

*× *4(

*K − *1) matrix

**C**(

*z*) by

that Λ

*∗*(

*x*)

*≥ *0, Λ

*∗*(

*x*) is convex and it attains its minimumat

*x *= 0 [2]. Also, it can be shown that Λ

*∗*(

*x*) = Λ

*∗*(

*−x*).

**C **(

*z*) =

**QD**(

*z*)

*,*
where

**Q **and

**D**(

*z*) are deﬁned by (10) and (11), respectively.

*n*(

*z*) (

*n *= 1

*, *2

*, . . .*) by

*n*(

*nx*) =

*−*Λ

*∗*(

*x*)

*.*
*ηn*(

*z*) = (

**s **⊗ **s **⊗ **r**)

**C**(

*z*)

*n***e**,
We also see that the asymptotic decay rate of the STAFI
where

**e **denotes a 4(

*K − *1)

*× *1 vector whose elements are all

*Gn*(

*nx*) increases with the increase in

*x*, when the parame-
equal to one,

**s **and

**r **are given by (5) and (9), respectively,

ters

*K*,

*fd*,

*γ*1 and

*Tf *are ﬁxed.

and

**C **(

*z*) is deﬁned by (12).

We are now ready to present the analysis of the STAFI

*n*(

*x*). Note that

*ηn*(

*z*) can also be expressed in the power

**Table 1: Estimations of STAFI**
*K *= 30,

*γ*1 = 3

*.*78dB

*K *= 30,

*γ*1 = 3

*.*78dB

*K *= 20,

*γ*1 = 3

*.*78dB

*K *= 30,

*γ*1 = 3

*.*78dB

*K *= 30,

*γ*1 = 2

*.*00dB

*K *= 30,

*γ*1 = 2

*.*00dB

**Figure 3: STAFI ***G*
*n*(

*hn*)

**as a function of ***h ***(***γ*1 =

3

*.*78

**dB)**
*K *= 30,

*γ*1 = 6

*.*00dB

**Figure 4: STAFI ***G*
*n*(

*hn*)

**as a function of ***h ***(***γ*1 =

2

*.*00

**dB)**
**Figure 2: STAFI ***G*256(

*x*)

**as a function of ***x*
bit feedback fair scheduler whose threshold

*γ*1 is equal to
In this section, we provide numerical results to get insight

*x*, and “RS” means the random scheduler. In this ﬁgure,
about the properties of the STAFI of the one-bit feedback
we observe the following. For almost whole range of

*x*, the
fair scheduler. Throughout this subsection, we ﬁx the pa-
STAFIs

*G*256(

*x*) of the one-bit feedback fair schedulers are
rameters as

*fd *= 10Hz and

*Tf *= 1msec.

greater than the STAFI

*G*256(

*x*) of the random scheduler. In
First, we compare numerical results obtained by the in-
other words, the short term fairness provided by the one-bit
verse discrete FFT method with simulation results to con-
feedback fair schedulers is worse than that provided by the
ﬁrm the correctness of the numerical results. For various
random scheduler. This is due to the positive correlation of

*n*,

*x*, the number

*K *of MSs and the threshold

*γ*1, Table 1
the normalized SNR process

*{z*(

*i*)(

*t*)

*/*¯

*z*(

*i*)

*} *in time. We also
shows the STAFI

*Gn*(

*x*) obtained by the inverse discrete
see that for small

*x *of

*G*256(

*x*), the one-bit feedback fair
FFT method. For comparison, Table 1 also shows the STAFI
scheduler with larger threshold

*γ*1 provides better fairness

*Gn*(

*x*) estimated by Monte Carlo simulation. The estima-
than that with smaller threshold. However, the situation is
tions by Monte Carlo simulation are the averages of 100
converse for large

*x *of

*G*256(

*x*). Thus, the one-bit feedback
estimates, and each estimate is the average of 106 samples.

fair scheduler with larger threshold

*γ*1 can keep the proba-
Table 1 shows the variances of the estimates, too. In Table 1,
bility of moderate unfairness lower, but it can causes serious
we conﬁrm that the inverse discrete FFT method yields cor-
unfairness with higher probability, compared to the one-bit
feedback fair scheduler with smaller threshold.

Next, we observe the eﬀect of the threshold

*γ*1 on the
Next we examine how the STAFI of the one-bit feedback
STAFI

*Gn*(

*x*). Fig. 2 shows the STAFI

*G*256(

*x*) of the one-
fair scheduler changes as the progress of time. Fig. 3 and
bit feedback fair scheduler as a function of

*x*.

4 exhibit the STAFI

*Gn*(

*hn*) as a function of

*h *for

*n *=
parison, Fig. 2 also shows the STAFI

*G*256(

*x*) of the ran-
64

*, *128

*, *256

*, *512. We set the number

*K *of MSs to 30, the
dom scheduler. In the ﬁgure, “1FF(

*x*dB)” means the one-
threshold

*γ*1 to 3.78dB in Fig. 3 and to 2.00dB in Fig. 4.

**Figure 5: STAFI ***Gn*(

*hn/K*)

**as a function of ***h ***(***γ*1 =

**Figure 6: Asymptotic decay rate of STAFI ***Gn*(

*hn/K*)

2

*.*74

**dB)**
**as a function of ***K*
for the scheduler with large threshold value, the asymptotic
In Fig. 3 and 4, we observe that under the one-bit feedback
decay rate of the STAFI

*Gn*(

*hn/K*) greatly decreases with
the increase in the number of MSs. This means that for the

*n*(

*hn*) rapidly decreases with the increase
of

*n *for every

*h*. In other words, the STAFI of the one-
scheduler with large threshold value, the speed approaching
bit feedback fair scheduler rapidly approaches to the strict
to the strict fairness as the progress of time becomes slow
with the increase in the number of MSs.

We next investigate how unfairness between two users is
resolved under the one-bit feedback fair scheduling. For this
purpose, we consider the STAFI

*Gn*(

*hn/K*) as a function
In this paper, we focus on the one-bit feedback fair sched-
of

*n *where

*h *is a parameter. Note here that the term

*n/K*
uler and numerically study the STAFI of the scheduler to
denotes the expected time-access which a user receives when
explore its short term fairness properties. We develop two
ideal fairness is achieved. Thus the STAFI

*Gn*(

*hn/K*) is
numerical methods to understand the transient properties of
considered as a measure indicating a deviation from the ideal
the STAFI of the one-bit feedback fair scheduler. The ﬁrst
fairness, where a large value of

*h *means a sever deviation
method calculates the exact value of the STAFI by using the
from the ideal fairness. Fig. 5 displays the STAFI

*Gn*(

*hn/K*)
inverse discrete FFT method. It enables us to precisely ob-
as a function of the observation period

*n *for

*h *= 2

*.*00

*, *4

*.*00
serve how the STAFI changes as the progress of time. The
denoted by “h=2.0” and “h=4.0”, respectively. In addition,
second method estimates the asymptotic decay rate of the
Fig. 5 shows the lines exp(

*−n*Λ

*∗*(

*h/K*)) for

*h *= 2

*.*00

*, *4

*.*00
STAFI by using the theory of large deviations. It enables us
denoted by “ADR(h=2.0)” and “ADR(h=4.0)”, respectively,
to predict how fast the STAFI approaches to ideal fairness
where Λ

*∗*(

*h/K*) is the asymptotic decay rate of the STAFI
In the numerical results, we observe that the STAFI of
rate Λ

*∗*(

*h/K*) from Proposition 1.

the one-bit feedback fair scheduler rapidly approaches to the
the number

*K *of MSs to 16 and the threshold

*γ*1 to 2.74dB.

strict fairness. We also observe that the threshold

*γ*1 aﬀects
We observe in the ﬁgure that in an asymptotic sense, i.e., as
the short term fairness property of the one-bit feedback fair

*n → ∞*, the STAFI

*Gn*(

*hn/K*) decreases exponentially as
scheduler. The one-bit feedback fair scheduler with larger
stated in Proposition 1. The asymptotic decay rates of the
threshold

*γ*1 can keep the probability of moderate unfair-
STAFI

*Gn*(

*hn/K*) seem to be equal to Λ

*∗*(

*h/K*). We also
ness lower, but it can causes serious unfairness with higher
see that as mentioned Proposition 1, the asymptotic decay
probability, compared to the one-bit feedback fair scheduler
rate of the STAFI

*Gn*(

*hn/K*) is large when the parameter
with smaller threshold. We ﬁnally observe that for the one-

*h *is large and

*K *is ﬁxed.

bit feedback fair scheduler with large threshold value, the
Finally we observe the eﬀect of the number

*K *of MSs on
asymptotic decay rate of the STAFI

*Gn*(

*hn/K*) becomes
the asymptotic decay rate of the STAFI

*Gn*(

*hn/K*). Using
small with the increase in the number of MSs. We conclude
Proposition 1, we estimate the asymptotic decay rate of the
that if rigorous fairness is required even in a relatively short
STAFI

*Gn*(

*hn/K*). Fig. 6 shows the estimated asymptotic
time period, we should consider the short term fairness of
decay rates as a function of the number

*K *of MSs for the
the scheduler as well as its information theoretic capacity
schedulers with the threshold values

*γ*1 = 2

*.*00

*, *3

*.*78

*, *6

*.*00dB.

when we determine the threshold

*γ*1.

In this ﬁgure, we observe that for the scheduler with

*γ*1 =2

*.*00dB, the asymptotic decay rate of the STAFI

*Gn*(

*hn/K*)
does not signiﬁcantly change with the increase in the number

*K *of MSs. However, for the scheduler with

*γ*
[1] J. A. Bucklew,

*Large deviation techniques in decision,*
*simulation, and estimation*, Wiley, 1990.

1 = 6

*.*00dB, the asymptotic decay rate of the
STAFI

*Gn*(

*hn/K*) decreases with the increase in the number
[2] C.-S. Chang,

*Performance guarantees in*
*K *of MSs in the range from

*K *= 10 to

*K *= 40. We see that

*communication networks*, Springer-Verlag, 2000.

[3] J. Diaz, O. Simeone, and Y. Bar-Ness, “Sum-rate of
eﬃcient support of quality of service over a fading
MIMO broadcast channels with one bit feedback,”
channel,”

*IEEE Trans. Veh. Technol.*, vol.54, no.3,

*Proc. of IEEE International Symposium on*
*Information Theory (ISIT ’06)*, pp.1944-1948, 2006.

[20] Y. Xue and T. Kaiser, “Exploiting multiuser diversity
en, O. Edfors and B.-A. Molin, “The eﬀect of
with imperfect one-bit channel state feedback,”

*IEEE*
feedback quantization on the throughput of a

*Trans. Veh. Technol.*, vol.56, no.1, pp.183–193, 2007.

multiuser diversity scheme,”

*Proc. of IEEE*
[21] M. D. Yacoub,

*Foundation of mobile radio*
*GLOBECOM 2003*, pp.497-501, 2003.

*engineering*, Boca Ration, FL:CRC, 1993.

[5] D. Gesbert and M.-S. Alouini, “How much feedback is
[22] L. Yang, M. Kang, and M.-S. Alouini, “On the
multi-user diversity really worth?,”

*Proc. of IEEE ICC*
capacity-fairness tradeoﬀ in multiuser diversity
systems,”

*IEEE Trans. Veh. Technol.*, vol.56, no.4,
[6] G. U. Hwang and F. Ishizaki, “Design of a fair
scheduling exploiting multiuser diversity with feedback
[23] W. Zhang and K.B. Letaief, “MIMO broadcast
reduction,”

*IEEE Communications Letters*, vol.12,
scheduling with limited feedback,”

*IEEE J. Sel. Areas*
*Commun.*, vol.25, no.7, pp.1457–1467, 2007.

[7] G. U. Hwang and F. Ishizaki, “Analysis of short term
fairness and its impact on packet level performance,”

*Performance Evaluation*, vol.67, no.12, pp.1340-1352,2010.

[8] F. Ishizaki and G. U. Hwang, “Queuing delay analysis
for packet schedulers with/without multiuser diversityover a fading channel,”

*IEEE Trans. Veh. Technol.*,vol.56, no.5, pp.3220–3227, 2007.

[9] F. Ishizaki and G. U. Hwang, “Throughput
performance of quantized proportional fair schedulingwith adaptive modulation and coding,”

*Proc. ofWireless Telecommunications Symposium (WTS)2009*, 2009.

[10] H. Kim and Y. Han, “An opportunistic channel
quality feedback scheme for proportional fairscheduling,”

*IEEE Communications Letters*, Vol.11,No.6, pp.501–503, 2007.

[11] R. Knopp and P. A. Humblet, “Information capacity
and power control in single-cell multiusercommunications,”

*Proc. of IEEE ICC ’95*, pp.331–335,1995.

[12] Q. Liu, S. Zhou, and G. B. Giannakis, “Queuing with
adaptive modulation and coding over wireless links:cross-layer analysis and design,”

*IEEE Trans. WirelessCommun.*, vol.4, pp.1142–1153, 2005.

[13] Y. Liu, S. Gruhl and E. W. Knightly, “WCFQ: an
opportunistic wireless scheduler with statisticalfairness bounds,”

*IEEE Trans. Wireless Commun.*,vol.2, no.5, pp.1017–1028, 2003.

[14] X. Qin and R. Berry, “Exploiting multiuser diversity
for medium access control in wireless networks,”

*Proc.*

of IEEE INFOCOM ’03, pp.1084–1094, 2003.

[15] S. Sanayei and A. Nosratinia, “Opportunistic downlink
transmission with limited feedback,”

*IEEE Trans.*

Infor. Theory, vol.53, no.11, pp.4363–4372, 2007.

[16] O. Somekh, A.M. Haimovich, and Y. Bar-Ness,
“Sum-rate analysis of downlink channels with 1-bit
feedback,”

*IEEE Communications Letters*, vol.11,no.2, pp.137–139, 2007.

[17] H. C. Tijms,

*A first course in stochastic models*, John
[18] B. Tan, L. Ying, and R. Srikant, “Short-term fairness
and long-term QoS,”

*Proc. of Conference onInformation Science and Systems (CISS)*,pp.1201–1204, 2008.

[19] D. Wu and R. Negi, “Utilizing multiuser diversity for

Source: http://www.ishizaki-lab.net/ishizaki/papers/qtna2011.pdf

Philmont Scout Ranch Chuck Wagon Menu and Ingredient List BEEF STEW – water, beef (beef, salt), potatoes, carrots, celery, peas, beef type flavor (autolyzed yeast extract, soy sauce, [soybeans, wheat, salt, partially hydrogenated soybean and cottonseed oil, lattice acid]), wheat flour (enriched with niacin, reduced iron, thiamine, riboflavin, folic acid), tomato paste, modified c

¡Esto es por lo qué importa el 11 de septiembre! por Elias Davidsson U n número de personas, especialmente de la izquierda, sostiene que en realidad no importa quienes cometieron las atrocidades del 11 de septiembre de 2001 - fanáticos musulmanes reaccionarios, imperialistas de los EE.UU. , o quien sea. Según este punto de vista, insistir en la identificación de los culpables no m