Uplink scheduler for cellular packet access
View Patent ↗A method includes constraining total power received from cellular users accessing a base station through any one of a TDMA access, CDMA access, and a derivation of a TDMA/CDMA access, and scheduling users for access to the base station within the constrained total power in response to an optimization that for each time slot determines a group of time critical cellular users and their transmission power factoring in instantaneous location-dependent channel states and long term quality of service performance. In the preferred embodiment, the optimization includes an iterative solution of an NP-hard Knapsak problem with initialization of maximum transmit power per cellular user inversely proportional to at least one of an activity factor of a cellular user's channel, the cellular user's antenna gain, the instantaneous channel gain of a dedicated uplink channel for the cellular user, and other-cellular user to same-cellular user interference ratio, and directly proportional to total resource power consumption.
1. A method comprising the steps of:
constraining total power received from cellular users accessing a base station through any one of a TDMA access, CDMA access, and a derivation of a TDMA/CDMA access, and
scheduling users for access to the base station within the constrained total power in response to an optimization that for each time slot determines a group of time critical cellular users and their transmission power factoring in instantaneous location-dependent channel states and long term quality of service performance, wherein the optimization includes the following steps:
i) ∀i (backlogged users), letting
l
i
(
t
)
=
l
i
RoT
(
t
)
≡
(
1
-
L
*
(
t
)
)
(
1
+
f
)
G
dv
G
a
p
_
i
max
h
i
(
t
)
N
0
W
;
ii) sorting i's into a list U with decreasing
u
i
RoT
(
t
)
=
w
i
(
t
)
B
i
(
t
)
a
W
log
2
(
1
+
1
G
dv
G
a
l
i
RoT
(
t
)
(
1
+
f
)
-
(
1
+
f
-
ϕ
)
l
i
RoT
(
t
)
)
;
iii) moving the first user i from U into I(t), calculating i's (interference-free) SINR s i (t,I) (see below for the equation) and utility increment u i (t,I) (see below);
iv) removing the next user k from U and letting I′(t)=I(t)+{k}, then proceeding to check whether I′(t) offers better utility than I(t) below under RoT and s i min (∀iεI′(t)) constraints;
v) calculating I′(t)-defined SINR as follows:
s
i
(
t
,
I
′
)
=
p
_
i
max
h
i
(
t
)
N
0
W
+
(
1
+
f
)
G
d
v
G
a
∑
k
∈
I
′
(
t
)
,
k
≠
i
p
_
k
max
h
k
(
t
)
+
ϕ
G
d
v
G
a
p
_
i
max
h
i
(
t
)
,
∀
i
∈
I
′
(
t
)
;
vi) checking if ∃iεI′(t), s i (t, I′)<s i min , and if yes, going back to the previous step, otherwise proceeding to the next step;
vii) ∀iεI′(t), calculating I′(t)-defined per-user load and utility increment as follows
l
i
(
t
,
I
′
)
=
(
1
+
f
)
G
d
v
G
a
s
i
(
t
,
I
′
)
1
+
(
1
+
f
-
ϕ
)
G
d
v
G
a
s
i
(
t
,
I
′
)
,
u
i
(
t
,
I
′
)
=
w
i
(
t
)
B
i
(
t
)
α
W
log
2
(
1
+
s
i
(
t
,
I
)
)
;
viii) calculating
L
(
t
)
=
1
-
1
(
1
+
δ
)
Z
t
h
-
∑
∀
i
∈
I
′
(
t
)
l
i
(
t
,
I
′
)
;
If L(t)<0 or
∑
∀
i
∈
I
′
(
t
)
u
i
(
t
,
I
′
)
<
∑
∀
i
∈
I
(
t
)
u
i
(
t
,
I
)
,
and if U≠NULL, then going back to step iv);
ix) adding k to I(t): I(t)=I′(t), L*(t)=L(t); If U=NULL, stop with scheduling decision as {p i (t)= p i max 1 (iεI(t)) , ∀iεK}; otherwise, going back to Step iv).
2. An apparatus comprising:
a total power limit for receiving transmissions from cellular users through any one of a TDMA access, CDMA access, and a derivation of a TDMA/CDMA access, and
a scheduler for selecting access by the cellular users to a base station within the total power in response to an optimization that for each time slot determines a group of time critical cellular users and their transmission power factoring in instantaneous location-dependent channel states and long quality of service performance wherein the optimization includes at least one of:
an iterative solution of an NP-hard Knapsak problem with initialization of maximum transmit power per cellular user inversely proportional to at least one of an activity factor of a cellular user's channel (G dv ), the cellular user's antenna gain (G a ), the instantaneous channel gain of a dedicated uplink channel for the cellular user (h i (t), and other-cellular user to same-cellular user interference ratio (f), and directly proportional to total resource power consumption (L*(t)); and
for backlogged cellular users, a load defined per cellular user to be directly proportional to an activity factor of a cellular user's channel (G dv ), a cellular user's antenna gain (G a ), an instantaneous channel gain of a dedicated uplink channel for the cellular user (h i (t), optimal assignment of power allocation or all cellular users (p i −max ), other-cellular user to same-cellular user interference ratio (f), and inversely proportional to total received power by the base station (N o W).
3. An apparatus comprising:
a total power limit for receiving transmissions from cellular users through any one of a TDMA access, CDMA access, and a derivation of a TDMA/CDMA access, and
a scheduler for selecting access by the cellular users to a base station within the total power in response to an optimization that for each time slot determines a group of time critical cellular users and their transmission power factoring in instantaneous location-dependent channel states and long term quality of service performance wherein the optimization includes:
i) ∀i (backlogged users), letting
l
i
(
t
)
=
l
i
R
o
T
(
t
)
≡
(
1
-
L
*
(
t
)
)
(
1
+
f
)
G
d
v
G
a
p
_
i
max
h
i
(
t
)
N
0
W
;
ii) sorting i's into a list U with decreasing
u
i
R
o
T
(
t
)
=
w
i
(
t
)
B
i
(
t
)
α
W
log
2
(
1
+
1
G
d
v
G
a
l
i
R
o
T
(
t
)
(
1
+
f
)
-
(
1
+
f
-
ϕ
)
l
i
R
o
T
(
t
)
)
;
iii) moving the first user i from U into I(t), calculating i's (interference-free) SINR s i (t,I) (see below for the equation) and utility increment u i (t,I) (see below);
iv) removing the next user k from U and letting I′(t)=I(t)+{k}, then proceeding to check whether I′(t) offers better utility than I(t) below under RoT and s i min (∀iεI′(t)) constraints;
v) calculating I′(t)-defined SINR as follows:
s
i
(
t
,
I
′
)
=
p
_
i
max
h
i
(
t
)
N
0
W
+
(
1
+
f
)
G
d
v
G
a
∑
k
∈
I
′
(
t
)
,
k
≠
i
p
_
k
max
h
k
(
t
)
+
ϕ
G
d
v
G
a
p
_
i
max
h
i
(
t
)
,
∀
i
∈
I
′
(
t
)
;
vi) checking if ∃iεI′(t), s i (t,I′)<s i min , and if yes, going back to the previous step, otherwise proceeding to the next step;
vii) ∀iεI′(t), calculating I′(t)-defined per-user load and utility increment as follows
l
i
(
t
,
I
′
)
=
(
1
+
f
)
G
d
v
G
a
s
i
(
t
,
I
′
)
1
+
(
1
+
f
-
ϕ
)
G
d
v
G
a
s
i
(
t
,
I
′
)
,
u
i
(
t
,
I
′
)
=
w
i
(
t
)
B
i
(
t
)
α
W
log
2
(
1
+
s
i
(
t
,
I
)
)
;
viii) calculating
L
(
t
)
=
1
-
1
(
1
+
δ
)
Z
t
h
-
∑
∀
i
∈
I
′
(
t
)
l
i
(
t
,
I
′
)
;
If L(t)<0 or
∑
∀
i
∈
I
′
(
t
)
u
i
(
t
,
I
′
)
<
∑
∀
i
∈
I
(
t
)
u
i
(
t
,
I
)
,
and if U≠NULL, then going back to step iv);
ix) adding k to I(t): I(t)=I′(t), L*(t)=L(t); If U=NULL, stop with scheduling decision as {p i (t)= p i max 1 (iεI(t)) , ∀iεK}; otherwise, going back to Step iv).
4. A method comprising the steps of:
constraining total power received from cellular users accessing a base station through any one of a TDMA access, CDMA access, and a derivation of a TDMA/CDMA access, and
scheduling users for access to the base station within the constrained total power in response to an optimization that for each time slot determines a group of time critical cellular users and their transmission power factoring in instantaneous location-dependent channel states and long term quality of service performance, wherein the optimization includes at least one of:
iterating a solution to an NP-hard Knapsak problem with initialization of maximum transmit power per cellular user inversely proportional to at least one of an activity factor of a cellular user's channel (G dv ), the cellular user's antenna gain (G a ), the instantaneous channel gain of a dedicated uplink channel for the cellular user (h i (t), and other-cellular user to same-cellular user interference ratio (f), and directly proportional to total resource power consumption (L*(t));
for backlogged cellular users, defining the load per cellular user to be directly proportional to an activity factor of a cellular user's channel (G dv ), the cellular user's antenna gain (G a ), the instantaneous channel gain of a dedicated uplink channel for the cellular user (h i (t), optimal assignment of power allocation or all cellular users (p i −max ), other-cellular user to same-cellular user interference ratio (f), and inversely proportional to total received power by the base station (N o W); and
estimating the per-user load l i (t) as the ratio of maximum received power from cellular user i, if supposing the cellular user i is transmitting at its full power, to the maximum allowed total interference, (i.e., N t (t)W=N 0 WZ th ), estimating per-cellular user utility increment (u i RoT (T)) with total received power at the base station (N t (t)W=N 0 WZ th , i.e.), assuming each cellular user is facing the maximum allowable interference and estimating each backlogged user load l i (t) based on an existing interference with only active cellular users.