Method and apparatus for optimization of wireless mesh networks
A cross-layer optimization framework for designing of multi-radio/multi-channel wireless mesh networks with network coding to support multiple unicast applications is used. A column-generation-based primal-dual method is used to solve the optimization problem. For network-layer formation, a code construction scheme based on linear programming is used. Delay constraints are imposed on the network code construction so the possible impact of the extra decoding delay to the upper-layer Transmission Control Protocol/Internet Protocol (TCP/IP) performance may be reduced without changing the upper-layer protocols.
1. An apparatus for designing a wireless mesh network having a plurality of transmission sources and a plurality of nodes configured to communicate over a plurality of links, the apparatus comprising:
means for determining an optimization problem describing the wireless mesh network, wherein the optimization problem is a utility function maxU( R , f ) wherein R are unicast data rates and f are network flow rates;
means for determining a plurality of constraints for the optimization problem, wherein the plurality of constraints for the optimization problem comprises: f εF( R ), r i ≧0, ∀i, c εC( I ), and f l ≦c l , ∀l wherein:
f εF( R ) enforces the dependence between the achievable rates R and the data flows f ;
r i ≧0, ∀i is a data rate;
c εC( I ) is the relationship between the achievable link capacity c and transmission source allocation; and
f l ≦c l , ∀l bounds a sum of the flow rate on each link by a link capacity; and
means for determining a network code for the wireless mesh network by solving the optimization problem using a column-based primal-dual optimization method, wherein delay constraints are imposed on the network code to constrain the optimization problem, the delay constraints providing a transmission scheme in which antidotes are received at a decoding node prior to poisoned data.
2. The apparatus of claim 1 wherein the means for solving the optimization problem using a column-based primal-dual optimization method comprises:
means for generating a set V′ comprising one or more feasible link rates c k wherein V′={c k εC} k=1 K and K is the number of feasible link capacity vectors;
means for approximating C with C′ ⊂ C
wherein
C
′
=
{
c
_
|
c
_
=
∑
k
=
1
κ
α
k
c
_
k
,
s
.
t
.
∑
k
=
1
κ
α
k
=
1
,
α
k
≥
0
,
∀
k
}
;
means for determining a lower bound of the optimization problem which is a solution to the optimization problem;
means for determining one or more dual factors {λ l } l=1 L′ wherein L is the set of links connecting the plurality of nodes;
means for determining an upper bound of the optimization problem wherein the upper bound is
max
r
i
≥
0
,
∀
i
{
U
(
R
_
,
f
_
)
-
∑
l
=
1
L
′
λ
l
f
l
|
f
_
∈
F
(
R
_
)
}
+
max
c
_
∈
C
∑
l
=
1
L
′
λ
l
c
l
and wherein the dual factors {λ l } l=1 L′ are the corresponding Lagrangian multipliers associated with the constraints about {c l } in the optimization problem.
3. An apparatus for designing a wireless mesh network having a plurality of transmission sources and a plurality of nodes configured to communicate over a plurality of links, the apparatus comprising:
means for determining an optimization problem describing the wireless mesh network, wherein the optimization problem is
max
∑
l
=
1
L
′
λ
l
c
l
and further wherein L is the set of links over which the plurality of nodes are configured to communicate, c is an achievable link capacity, and λ is dual factor;
means for determining a plurality of constraints for the optimization problem, wherein the plurality of constraints for the optimization problem comprises:
a
n
,
m
=
∑
l
∈
O
(
n
)
ν
l
,
m
+
∑
l
∈
l
(
n
)
ν
l
,
m
,
a
n
,
m
≤
1
,
∀
n
,
m
;
∑
m
=
1
M
a
n
,
m
≤
I
n
,
n
∈
N
;
H
l
,
lPl
,
m
+
(
1
-
ν
l
,
m
)
σ
l
2
+
∑
j
≠
1
H
l
,
jPj
,
m
>
γ
l
,
m
t
;
H
l
,
lPl
′
,
m
+
(
1
-
ν
l
′
,
m
v
k
′
,
m
)
Z
l
,
l
′
σ
l
2
+
∑
j
≠
l
H
l
,
jPj
,
m
>
γ
l
,
m
,
t
∀
k
′
∈
O
(
n
′
)
;
and
∑
l
∈
O
(
n
)
∑
m
Pl
,
m
≤
P
n
,
max
,
∀
n
∈
N
,
wherein
:
m is a channel, I is a link, a n,m and v l,m are indicator variables, H is an effective power loss, P is a transmission power over a link, K is a number of feasible link capacity vectors, γ is a target signal-to-interference-plus-noise ratio, and Z is a constant large enough to guarantee
z
l
,
l
′
>
γ
l
,
m
t
(
σ
l
2
+
∑
j
≠
1
H
l
,
jPj
,
max
)
;
and
means for determining a network code for the wireless mesh network by solving the optimization problem using a column-based primal-dual optimization method, wherein delay constraints are imposed on the network code to constrain the optimization problem, the delay constraints providing a transmission scheme in which antidotes are received at a decoding node prior to poisoned data.