Convergence and Tradeoff of Utility-Optimal CSMA

Jiaping Liu; Yung Yi; Alexandre Proutière; Mung Chiang; H.Vincent Poor

6th International ICST Conference on Broadband Communications, Networks, and Systems

Research Article

Convergence and Tradeoff of Utility-Optimal CSMA

Download616 downloads

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.4108/ICST.BROADNETS2009.7401,
    author={Jiaping Liu and Yung Yi and Alexandre Prouti\'{e}re and Mung Chiang and H.Vincent Poor},
    title={Convergence and Tradeoff of Utility-Optimal CSMA},
    proceedings={6th International ICST Conference on Broadband Communications, Networks, and Systems},
    publisher={IEEE},
    proceedings_a={BROADNETS},
    year={2009},
    month={11},
    keywords={Algorithm design and analysis Clocks Convergence Message passing Multiaccess communication Scheduling algorithm Simulated annealing Stability Throughput Wireless networks},
    doi={10.4108/ICST.BROADNETS2009.7401}
}

Jiaping Liu
Yung Yi
Alexandre Proutière
Mung Chiang
H.Vincent Poor
Year: 2009
Convergence and Tradeoff of Utility-Optimal CSMA
BROADNETS
IEEE
DOI: 10.4108/ICST.BROADNETS2009.7401

Jiaping Liu¹^,*, Yung Yi²^,*, Alexandre Proutière³^,*, Mung Chiang¹^,*, H.Vincent Poor¹^,*

1: Department of Electrical Engineering, Princeton University, USA
2: Department of Electrical Engineering, KAIST, South Korea
3: Microsoft Research, Cambridge, UK

*Contact email: jiapingl@princeton.edu, yiyung@ee.kaist.ac.kr, alexandre.proutiere@microsoft.com, chiangm@princeton.edu, poor@princeton.edu

Abstract

It has been recently suggested by Jiang andWalrand that adaptive carrier sense multiple access (CSMA) can achieve optimal utility without any message passing in wireless networks. In this paper, a generalization of this algorithm is considered. In the continuous-time model, a proof is presented of the convergence of these adaptive CSMA algorithms to arbitrarily close to utility optimality, without assuming that the network dynamics freeze while the CSMA parameters are updated. In the more realistic, slotted-time model, the impact of collisions on the utility achieved is characterized, and the tradeoff between optimality at equilibrium and short-term fairness is quantified.

Keywords: Algorithm design and analysis Clocks Convergence Message passing Multiaccess communication Scheduling algorithm Simulated annealing Stability Throughput Wireless networks

Published: 2009-11-17
Publisher: IEEE
Modified: 2010-05-16

: http://dx.doi.org/10.4108/ICST.BROADNETS2009.7401