In this report we use Network Utility Maximization (NUM) Framework to study the joint assignment of rate and reliability among sources in multi-hop wireless network. Formulating the above problem in the NUM framework can lead to natural functional decomposition into layers and distributed algorithms. The optimality is preserved through messages passing between layers and local messages exchanging among nodes.The framework reasons (joint) cross layer design. Heuristic layering turns out to be solving a NUM optimization problem. This is so called “Layering as optimization decomposition”. Especially, our problem leads tocongestion controlat transport layer and the adaptive codingat the physical layer. The messages passing between layers are congestion prices (Lagrange multipliers). Updating is performed distributively using local messages.
Each sources has a utility function, where is an information data rate andis thereliability of sources. We assume that the utility function isa continuous, increasing, and concave function of and.
Each sources has its information data rate bounded between aminimum and a maximum: and, and has a minimumreliability requirement.The reliability of source sis defined as
Assume
is the end-to-end error probability
is the code rate of source sat link l
is the information data rate of source s
is the transmission data rate of source sat link l
is the error probability of source sat link l
is an increasing function of reflecting the rate-reliability trade-off
is the set of links used by source s
is the set of sources using link l
is the capacity of link l
Assume
maximize
subject to
and
: the Lagrange multiplier on linklwith an interpretation of “congestion price”, the price per unit rate to use linkl
: the Lagrange multiplier on source swith an interpretation of “reliability price”, the price perunit reliability that the source smust pay to the network
: with an interpretation of “end-to-end congestion price” on source s
: with an interpretation of “aggregate reliability price”paid by sources using link l
The Lagrange dual function is
The dual problem is
minimize
subject to
Since the Lagrangian is separable, this maximization of theLagrangian overcan be conducted in parallel at each source s
maximize
subject to
and on each linkl
maximize
subject to
dual problem can be solved by using the gradient projection algorithm as
is the step size.
Algorithm 1 for Integrated Dynamic Reliability Policy
Source problem and reliability price update at sources:
Source problem
maximize
subject to
Price update
where is the end-to-endreliability at iteration t.
Link problem and congestion price update at linkl:
Link problem
maximize
subject to
Price update
where is the aggregate information rate on linkl at iterationt.
In Algorithm 1, to solve problem (8), source sneeds to know, the sum of’s of links that are along its path .This can be obtained by notification from the links, e.g.,through the presence or timing of acknowledgment packets inTCP. To carry out price update (9), the source needs to knowthe sum of error probabilities of the links that are along its path[i.e., its own reliability that are offered by the network].This can be obtained by the notification from the destination
that canmeasure its end-to-end reliability. To solve link problem(10), each link needs to know, the sum of’s fromsources using this link. This can be obtained by the notificationfrom these sources. To carry out price update (11),the link needs to know , the aggregate information data rateof the sources that are using it. This can be measured by the linkitself.
a linear topology consisting of four linksand eight users
maximize
subject to
By introducing the auxiliary variables, which can be interpreted as the allocated transmission capacity to source sat link l,
maximize
subject to
We introduce another layer, i.e., link layer (), by using a vertical decomposition of the optimization problem.
It is a GP, let ,
maximize
subject to
The Lagrange dual function is
The dual problem is
minimize
subject to
Algorithm 2 for Differentiated Dynamic Reliability Policy
Source problem and reliability price update at sources:
Source problem
maximize
subject to
Price update
where is the end-to-endreliability at iteration t.
Link problem and congestion price update at linkl:
Link problems
Link-layer problem
maximize
subject to ;
Physical-layer problem for source
maximize
subject to
Price update
Reference:
[1] Lee, J.-W.; Mung Chiang; Calderbank, A.R., "Price-based distributed algorithms for rate-reliability tradeoff in network utility maximization," Selected Areas in Communications, IEEE Journal on , vol.24, no.5, pp. 962-976, May 2006
[2] M. Chiang “Balancing transport and physical layer in wireless multihop networks: Jointly optimal congestion control and power control,” IEEE J. Sel. Areas Commun., vol. 23, pp. 104, Jan. 2005.
[3] Mung Chiang; Low, S.H.; Calderbank, A.R.; Doyle, J.C., "Layering as Optimization Decomposition: A Mathematical Theory of Network Architectures," Proceedings of the IEEE , vol.95, no.1, pp.255-312, Jan. 2007
[4] Palomar, D.P.; Mung Chiang, "A tutorial on decomposition methods for network utility maximization," Selected Areas in Communications, IEEE Journal on , vol.24, no.8, pp.1439-1451, Aug. 2006
[5] Lee Jang-Won; Tang Ao; Huang Jianwei; Mung Chiang; Robert, A., "Reverse-Engineering MAC: A Non-Cooperative Game Model," Selected Areas in Communications, IEEE Journal on , vol.25, no.6, pp.1135-1147, August 2007
[6] Jang-Won Lee; Mung Chiang; Calderbank, A.R., "Utility-Optimal Random-Access Control," Wireless Communications, IEEE Transactions on , vol.6, no.7, pp.2741-2751, July 2007
[7] Jang-Won Lee; Chiang, M.; Calderbank, R.A., "Jointly optimal congestion and contention control based on network utility maximization," Communications Letters, IEEE , vol.10, no.3, pp. 216-218, Mar 2006