TY - GEN
T1 - Utility-optimal medium access control
T2 - INFOCOM 2006: 25th IEEE International Conference on Computer Communications
AU - Lee, Jang Won
AU - Chiang, Mung
AU - Calderbank, A. Robert
PY - 2006/12/1
Y1 - 2006/12/1
N2 - This paper analyzes and designs medium access control (MAC) protocols for wireless ad-hoc networks through the network utility maximization (NUM) framework. We first reverse-engineer the current exponential backoff (EB) type of MAC protocols such as the BEB (binary exponential backoff) in the IEEE 802.11 standard through a non-cooperative gametheoretic model. This MAC protocol is shown to be implicitly maximizing, using a stochastic subgradient, a selfish local utility at each link in the form of expected net reward for successful transmission. While the existence of a Nash equilibrium can be established, neither convergence nor social welfare optimality is guaranteed due to the inadequate feedback mechanism in the EB protocol. This motivates the forward-engineering part of the paper, where a network-wide utility maximization problem is formulated, using a collision and persistence probability model and aligning selfish utility with total social welfare. By adjusting the parameters in the utility objective functions of the NUM problem, we can also control the tradeoff between efficiency and fairness of radio resource allocation through a rigorous and systematic design. We develop two distributed algorithms to solve the MAC design NUM problem, which lead to random access protocols that have slightly more message passing overhead than the current EB protocol, but significant potential for efficiency and fairness improvement. We provide readily-verifiable sufficient conditions under which convergence of the proposed algorithms to a global optimality of network utility can be guaranteed, and through numerical examples illustrate the value of the NUM approach to the complexity-performance tradeoff in MAC design.
AB - This paper analyzes and designs medium access control (MAC) protocols for wireless ad-hoc networks through the network utility maximization (NUM) framework. We first reverse-engineer the current exponential backoff (EB) type of MAC protocols such as the BEB (binary exponential backoff) in the IEEE 802.11 standard through a non-cooperative gametheoretic model. This MAC protocol is shown to be implicitly maximizing, using a stochastic subgradient, a selfish local utility at each link in the form of expected net reward for successful transmission. While the existence of a Nash equilibrium can be established, neither convergence nor social welfare optimality is guaranteed due to the inadequate feedback mechanism in the EB protocol. This motivates the forward-engineering part of the paper, where a network-wide utility maximization problem is formulated, using a collision and persistence probability model and aligning selfish utility with total social welfare. By adjusting the parameters in the utility objective functions of the NUM problem, we can also control the tradeoff between efficiency and fairness of radio resource allocation through a rigorous and systematic design. We develop two distributed algorithms to solve the MAC design NUM problem, which lead to random access protocols that have slightly more message passing overhead than the current EB protocol, but significant potential for efficiency and fairness improvement. We provide readily-verifiable sufficient conditions under which convergence of the proposed algorithms to a global optimality of network utility can be guaranteed, and through numerical examples illustrate the value of the NUM approach to the complexity-performance tradeoff in MAC design.
KW - Ad-hoc network
KW - Mathematical programming/optimization
KW - Medium access control (MAC)
KW - Network control by pricing
KW - Network utility maximization
KW - Wireless network
UR - http://www.scopus.com/inward/record.url?scp=33646422015&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33646422015&partnerID=8YFLogxK
U2 - 10.1109/INFOCOM.2006.252
DO - 10.1109/INFOCOM.2006.252
M3 - Conference contribution
AN - SCOPUS:33646422015
SN - 1424402212
SN - 9781424402212
T3 - Proceedings - IEEE INFOCOM
BT - Proceedings - INFOCOM 2006
Y2 - 23 April 2006 through 29 April 2006
ER -