Optimal resource allocation in a multi-hop OFDMA wireless network with cooperative relaying
View Patent ↗An optimal resource allocation strategy for OFDMA multi-hop wireless networks is disclosed. The system allocates one or more resources in a multi-hop network by solving one or more higher-layer sub-problem; solving one or more physical layer and media access control (PHY/MAC) layer sub-problems per tone per time slot with one of cooperative relaying of radio signals or spatial reusing of radio spectrum; updating prices; and allocating radio resources based on the PHY/MAC layer sub-problems.
1. A method to allocate one or more resources in a multi-hop network, comprising:
a. solving one or more higher-layer sub-problems;
b. solving one or more physical layer and media access control (PHY/MAC) layer sub-problems per tone per time slot with one of cooperative relaying of radio signals; or spatial reusing of radio spectrum; and no cooperative relaying of radio signals and no spatial reusing of the radio spectrum;
c. updating prices; and
d. allocating radio resources based on the PHY/MAC layer sub-problems;
P
ℓ
(
n
,
t
)
*
=
[
λ
ℓ
μ
S
(
ℓ
)
(
t
)
+
ò
-
1
G
ℓℓ
(
n
)
]
+
including
solving
ℓ
*
=
arg
max
ℓ
{
λ
ℓ
log
(
1
+
G
ℓℓ
(
n
)
P
ℓ
(
n
,
t
)
*
)
-
μ
S
(
ℓ
)
(
t
)
P
ℓ
(
n
,
t
)
*
|
ℓ
∈
t
(
)
}
.
2. The method of claim 1 , comprising solving one or more physical layer and media access control (PHY/MAC) layer sub-problems per tone per time slot with cooperative relaying of radio signals and no spatial reusing of radio spectrum.
3. The method of claim 2 , comprising:
P
ℓ
(
n
,
t
)
*
=
[
λ
ℓ
μ
S
(
ℓ
)
(
t
)
+
ò
-
1
G
k
*
,
S
(
ℓ
)
(
n
)
]
+
P
^
ℓ
(
n
,
t
)
*
(
k
i
)
=
1
η
i
2
[
λ
ℓ
η
i
μ
k
i
(
t
)
+
ò
-
1
G
Q
(
ℓ
)
,
k
i
(
n
)
]
+
ℓ
*
=
arg
max
ℓ
{
λ
ℓ
log
(
1
+
G
ℓℓ
(
n
)
P
ℓ
(
n
,
t
)
*
)
-
μ
S
(
ℓ
)
(
t
)
P
ℓ
(
n
,
t
)
*
|
ℓ
∈
,
λ
ℓ
log
(
1
+
G
k
*
,
S
(
ℓ
)
(
n
)
P
ℓ
(
n
,
t
)
*
)
-
μ
S
(
ℓ
)
(
t
)
P
ℓ
(
n
,
t
)
*
|
ℓ
∈
t
(
′
)
⋂
b
,
λ
ℓ
log
(
1
+
(
∑
k
∈
(
ℓ
)
G
Q
(
ℓ
)
,
k
(
n
)
P
^
ℓ
(
n
,
t
)
*
(
k
)
)
2
)
-
∑
k
∈
(
ℓ
)
μ
k
(
t
)
P
^
ℓ
(
n
,
t
)
*
(
k
)
|
ℓ
∈
}
.
4. The method of claim 1 , comprising solving one or more physical layer and media access control (PHY/MAC) layer sub-problems per tone per time slot with no cooperative relaying of radio signals but with spatial reusing of radio spectrum.
5. The method of claim 4 , comprising solving
max
∑
ℓ
∈
t
λ
ℓ
c
ℓ
(
n
,
t
)
-
∑
k
(
μ
ℓ
(
t
)
+
ò
)
∑
ℓ
∈
(
k
)
ℓ
∈
t
P
ℓ
(
n
,
t
)
subject
to
P
ℓ
(
n
,
t
)
≥
0
,
c
ℓ
(
n
,
t
)
≤
log
(
1
+
G
ℓℓ
(
n
)
P
ℓ
(
n
,
t
)
∑
ℓ
′
≠
ℓ
ℓ
′
∈
t
G
ℓℓ
′
(
n
)
P
ℓ
′
(
n
,
t
)
+
1
)
numerically with multiple initial points.
6. The method of claim 1 , comprising solving one or more physical layer and media access control (PHY/MAC) layer sub-problems per tone per time slot with cooperative relaying of radio signals and spatial reusing of radio spectrum.
7. The method of claim 6 , comprising solving
max
∑
ℓ
∈
t
(
′
)
λ
ℓ
c
ℓ
(
n
,
t
)
-
∑
k
(
μ
ℓ
(
t
)
+
ò
)
(
∑
ℓ
∈
(
k
)
ℓ
∈
(
⋃
b
)
⋂
t
(
′
)
P
ℓ
(
n
,
t
)
+
∑
ℓ
∈
k
∈
(
ℓ
)
P
^
ℓ
(
n
,
t
)
(
k
)
)
s
.
t
.
c
ℓ
(
n
,
t
)
≤
min
k
∈
(
ℓ
)
c
ℓ
,
k
(
n
,
t
)
,
∀
ℓ
∈
t
(
′
)
⋂
b
,
c
ℓ
,
k
(
n
,
t
)
=
Δ
log
(
1
+
G
k
,
S
(
ℓ
)
(
n
)
P
ℓ
(
n
,
t
)
∑
ℓ
′
≠
ℓ
ℓ
′
∈
(
⋃
b
)
⋂
t
(
′
)
G
k
,
S
(
ℓ
′
)
(
n
)
P
ℓ
′
(
n
,
t
)
+
∑
ℓ
′
≠
ℓ
ℓ
′
∈
c
⋂
t
(
′
)
∑
k
′
∈
G
k
,
k
′
(
n
)
P
^
ℓ
′
(
n
,
t
)
(
k
′
)
+
1
)
c
ℓ
(
n
,
t
)
≤
log
(
1
+
(
∑
k
∈
(
ℓ
)
G
Q
(
ℓ
)
,
k
(
n
)
P
^
ℓ
(
n
,
t
)
(
k
)
)
2
∑
ℓ
′
≠
ℓ
ℓ
′
∈
(
⋃
b
)
⋂
t
(
′
)
G
Q
(
ℓ
)
,
S
(
ℓ
′
)
(
n
)
P
ℓ
′
(
n
,
t
)
+
∑
ℓ
′
≠
ℓ
ℓ
′
∈
c
⋂
t
(
′
)
∑
k
′
∈
(
ℓ
′
)
G
Q
(
ℓ
)
,
k
′
(
n
)
P
^
ℓ
′
(
n
,
t
)
(
k
′
)
+
1
)
,
∀
ℓ
∈
t
(
′
)
⋂
c
c
ℓ
(
n
,
t
)
≤
log
(
1
+
G
ℓℓ
(
n
)
P
ℓ
(
n
,
t
)
∑
ℓ
′
≠
ℓ
ℓ
′
∈
(
⋃
b
)
⋂
t
(
′
)
G
ℓℓ
′
(
n
)
P
ℓ
′
(
n
,
t
)
+
∑
ℓ
′
≠
ℓ
ℓ
′
∈
c
⋂
t
(
′
)
∑
k
′
∈
(
ℓ
′
)
G
Q
(
ℓ
)
,
k
′
(
n
)
P
^
ℓ
′
(
n
,
t
)
(
k
′
)
+
1
)
,
∀
ℓ
∈
t
(
′
)
numerically with multiple initial points.
8. The method of claim 7 , comprising solving an approximate problem given by
max
∑
ℓ
∈
t
(
′
)
λ
ℓ
c
ℓ
(
n
,
t
)
-
∑
k
(
μ
ℓ
(
t
)
+
ò
)
(
∑
ℓ
∈
(
k
)
ℓ
∈
(
⋃
b
)
⋂
P
ℓ
(
n
,
t
)
+
∑
ℓ
∈
c
⋂
t
(
′
)
k
∈
(
ℓ
)
P
^
ℓ
(
n
,
t
)
(
k
)
)
s
.
t
.
c
ℓ
(
n
,
t
)
≤
-
1
d
log
(
∑
k
∈
(
ℓ
)
w
k
ⅇ
-
dc
ℓ
,
k
(
n
,
t
)
(
P
)
)
,
∀
ℓ
∈
t
(
′
)
⋂
b
,
c
ℓ
,
k
(
n
,
t
)
=
Δ
log
(
1
+
G
k
,
S
(
ℓ
)
(
n
)
P
ℓ
(
n
,
t
)
∑
ℓ
′
≠
ℓ
ℓ
′
∈
(
⋃
b
)
⋂
t
(
′
)
G
k
,
S
(
ℓ
′
)
(
n
)
P
ℓ
′
(
n
,
t
)
+
∑
ℓ
′
≠
ℓ
ℓ
′
∈
c
⋂
t
(
′
)
∑
k
′
∈
(
ℓ
′
)
G
k
,
k
′
(
n
)
P
^
ℓ
′
(
n
,
t
)
(
k
′
)
+
1
)
c
ℓ
(
n
,
t
)
≤
log
(
1
+
(
∑
k
∈
(
ℓ
)
G
Q
(
ℓ
)
,
k
(
n
)
P
^
ℓ
(
n
,
t
)
(
k
)
)
2
∑
ℓ
′
≠
ℓ
ℓ
′
∈
(
⋃
b
)
⋂
t
(
′
)
G
Q
(
ℓ
)
,
S
(
ℓ
′
)
(
n
)
P
ℓ
′
(
n
,
t
)
+
∑
ℓ
′
≠
ℓ
ℓ
′
∈
c
⋂
t
(
′
)
∑
k
′
∈
(
ℓ
′
)
G
Q
(
ℓ
)
,
k
′
(
n
)
P
^
ℓ
′
(
n
,
t
)
(
k
′
)
+
1
)
,
∀
ℓ
∈
t
(
′
)
⋂
c
ℓ
(
n
,
t
)
≤
log
(
1
+
G
ℓℓ
(
n
)
P
ℓ
(
n
,
t
)
∑
ℓ
′
≠
ℓ
ℓ
′
∈
(
⋃
b
)
⋂
t
(
′
)
G
ℓℓ
′
(
n
)
P
ℓ
′
(
n
,
t
)
+
∑
ℓ
′
≠
ℓ
ℓ
′
∈
c
⋂
t
(
′
)
∑
k
′
∈
(
ℓ
′
)
G
Q
(
ℓ
)
,
k
′
(
n
)
P
^
ℓ
′
(
n
,
t
)
(
k
′
)
+
1
)
,
∀
ℓ
∈
t
(
′
)
.
9. The method of claim 1 , comprising repeating (a)-(c) until convergence.
10. The method of claim 1 , wherein the solving the higher-layer sub-problem comprises solving:
maxs min −λ T x
subject to s min ≦s
Ax=s
x 0.
11. A system to allocate one or more resources in a multi-hop network, comprising:
one or more base stations; and
a radio resource controller coupled to the one or more base stations, the radio resource controller including computer readable code to:
solve one or more higher-layer sub-problems;
solve one or more physical layer and media access control (PHY/MAC) layer sub-problems per tone per time slot with one of: cooperative relaying of radio signals; or spatial reusing of radio spectrum; and no cooperative relaying of radio signals and no spatial reusing of the radio spectrum;
update prices; and
allocate radio resources based on the PHY/MAC layer sub-problems;
P
l
(
n
,
t
)
*
=
[
λ
l
μ
S
(
l
)
(
t
)
+
ò
-
1
G
ll
(
n
)
]
+
including
solving
l
*
=
arg
max
l
{
λ
l
log
(
1
+
G
ll
(
n
)
P
l
(
n
,
t
)
*
)
-
μ
S
(
l
)
(
t
)
P
l
(
n
,
t
)
*
❘
l
∈
A
t
(
G
)
}
.
12. The system of claim 11 , comprising code to solve one or more physical layer and media access control (PHY/MAC) layer sub-problems per tone per time slot with no cooperative relaying of radio signals and no spatial reusing of the radio spectrum.
13. The system of claim 11 , comprising code to solve one or more physical layer and media access control (PHY/MAC) layer sub-problems per tone per time slot with cooperative relaying of radio signals and no spatial reusing of radio spectrum.
14. The system of claim 11 , comprising code to solve one or more physical layer and media access control (PHY/MAC) layer sub-problems per tone per time slot with no cooperative relaying of radio signals but with spatial reusing of radio spectrum.
15. The system of claim 11 , comprising code to solve one or more physical layer and media access control (PHY/MAC) layer sub-problems per tone per time slot with cooperative relaying of radio signals and spatial reusing of radio spectrum.
16. A method to allocate one or more resources in a multi-hop network, comprising:
a. solving one or more higher-layer sub-problem(s);
b. solving one or more physical layer and media access control (PHY/MAC) layer sub-problems per tone per time slot with one of cooperative relaying of radio signals; spatial reusing of radio spectrum; and no cooperative relaying of radio signals but with spatial reusing of the radio spectrum;
c. updating prices; and
d. allocating radio resources based on the PHY/MAC layer sub-problems;
max
∑
l
∈
A
t
λ
l
c
l
(
n
,
t
)
-
∑
k
(
μ
l
(
t
)
+
ò
)
∑
l
∈
O
(
k
)
l
∈
A
t
P
l
(
n
,
t
)
including
solving
subject
to
P
l
(
n
,
t
)
≥
0
,
c
l
(
n
,
t
)
≤
log
(
1
+
G
ll
(
n
)
P
l
(
n
,
t
)
∑
l
′
≠
l
l
′
∈
A
t
G
ll
′
(
n
)
P
l
′
(
n
,
t
)
+
1
)
.