Cross layer network optimization for OFDMA systems using message passing algorithm
A method determines channel state information of a channel of a wireless network. Each of the wireless devices is configured to operate over the wireless network. An allocation of available transmission resources is performed according to a utility-based cross-layer resource management framework that transforms a utility function into an equivalent bipartite graph to concurrently maximize throughput and fairness in the resource allocation.
1. A method of allocating wireless subcarrier bandwidth, comprising:
defining a bipartite graph having first and second disjoint node sets;
assigning users to the first set of nodes such that each node of the first set of nodes is assigned to only one user;
assigning each sub-carrier to one and only one node of a second set of nodes;
using edges, connecting each node of the first set of nodes to every node of the second set of nodes;
weighting each edge using a value produced from a subcarrier-dependent and rate-dependent utility function;
numerically ordering unique edge weightings such that each unique edge weighting has at least one adjacent edge weighting and at least some of the unique edge weightings have a duplicate edge weighting that is not ordered;
for duplicate edge weightings identifying a perturbation factor between adjacent unique edge weightings;
perturbing all duplicate weightings by a random variable which is greater than zero and less than the perturbation factor; and
using a message passing algorithm to allocate data rates and subcarriers to users.
2. The method according to claim 1 , wherein the first set of nodes is assigned to unique user/data rate allocation combinations.
3. The method according to claim 2 , wherein for every user, a node is assigned for each rate allocation of a plurality of potential rate allocations.
4. The method according to claim 1 , wherein perturbation factors are assigned by a process comprising:
for all of the duplicate weightings except the last duplicated weighting, identifying a perturbation factor that lies at the midpoint of the duplicate weighting and the next largest duplicate weighting; and
for the last duplicate weighting, identifying a perturbation factor that is equal to the duplicate weighting.
5. The method according to claim 1 , wherein at least one perturbation factor is determined as one half a distance between a unique edge weighting and the next largest unique edge weighting.
6. The method according to claim 1 , wherein the first set of nodes is opposing and disjoint from the second set of nodes, and the message passing algorithm comprises:
(a) passing messages from each node of the first set of nodes to every node of the second set of nodes, the messages respectively being the edge weightings;
(b) passing messages from each node of the second set of nodes to every node of the first set of nodes, the messages respectively being the edge weightings;
(c) for one of the first set of nodes, assuming that each node is assigned to the opposing node that sent the largest message;
(d) determining if every node is assigned to one and only one opposing node; and
(e) if any node is not assigned to one and only one opposing node:
(e1) modifying all edge weightings by:
W new =W old −W largest
where W new is a modified edge weight, W old is a previous edge weighting and W largest is the largest edge weighting for all opposing nodes except for the node having the weighting being modified; and
(e2) repeating steps (a) through (d).
7. The method according to claim 6 , wherein W old is an original edge weighting before any edge weighting modification.
8. The method according to claim 1 , wherein the message passing algorithm is a beta-min-sum belief algorithm.
9. The method according to claim 1 , wherein the sub-carriers are subcarriers of an OFDMA wireless communication system.
10. The method according to claim 1 , wherein if the number of nodes of the first set of nodes does not equal the number of nodes of the second set of nodes, the method further comprises adding dummy nodes to the first or second set of nodes to achieve equality in the number of nodes in both sets.
11. The method according to claim 10 , wherein
the first set of nodes is opposing the second set of nodes, and
if the number of nodes of the first set of nodes does not equal the number of nodes of the second set of nodes, the method further comprises:
connecting each dummy node to every opposing node using dummy edges; and
assigning a zero edge weighting to each dummy edge.
12. The method according to claim 1 , wherein the argument of the utility function is a function of a long term average data rate for a user and a function of a modulation level currently being allocated to the user.
13. The method according to claim 1 , wherein the bandwidth allocation utility function is represented by the following formula
max
r
[
n
]
ρ
w
Δ
f
M
∑
i
=
1
M
∑
k
=
1
K
∑
p
=
0
P
-
1
U
i
′
(
r
_
i
[
n
-
1
]
)
D
p
[
n
]
δ
ikp
[
n
]
,
subject
to
{
P
[
k
,
n
]
≤
P
max
∀
k
r
i
[
n
]
∈
F
π
∀
i
lim
n
->
∞
r
_
i
[
n
]
≥
c
i
∀
i
where ρ w is a fixed factor, Δf denotes a frequency spacing between adjacent sub-carriers, M is the number of users, U′ i is the derivative of a utility function of user i which is a function of average past rates of the user r i [n−1], D p [n] is a pth modulation level and δ ikp [n] indicates an assignment of the D p [n] to user i over sub-carrier k during a current transmission frame n, P[k,n] is a transmission power used over the kth sub-carrier during an epoch, P max is a maximum power per subcarrier that cannot be exceeded, r i [n] denotes an instantaneous data rate assigned to the ith user over the current transmission interval, F π represents the set of feasible/potential data rates, r i [n] is the long-term average data rate of the ith user and c i is a target data rate for the ith user.