Math @ Duke

Publications [#235857] of Robert Calderbank
Papers Published
 Lee, JW; Chiang, M; Calderbank, AR, Utilityoptimal medium access control: Reverse and forward engineering,
Proceedings  IEEE INFOCOM
(2006), ISSN 0743166X [doi]
(last updated on 2018/02/19)
Abstract: This paper analyzes and designs medium access control (MAC) protocols for wireless adhoc networks through the network utility maximization (NUM) framework. We first reverseengineer the current exponential backoff (EB) type of MAC protocols such as the BEB (binary exponential backoff) in the IEEE 802.11 standard through a noncooperative 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 forwardengineering part of the paper, where a networkwide 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 readilyverifiable 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 complexityperformance tradeoff in MAC design. © 2006 IEEE.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

