Stability of the Max-Weight Protocol in Adversarial Wireless Networks

Cited 2 time in webofscience Cited 0 time in scopus
  • Hit : 96
  • Download : 0
In this paper, we consider the MAX-WEIGHT protocol for routing and scheduling in wireless networks under an adversarial model. This protocol has received a significant amount of attention dating back to the papers of Tassiulas and Ephremides. In particular, this protocol is known to be throughput-optimal whenever the traffic patterns and propagation conditions are governed by a stationary stochastic process. However, the standard proof of throughput optimality (which is based on the negative drift of a quadratic potential function) does not hold when the traffic patterns and the edge capacity changes over time are governed by an arbitrary adversarial process. Such an environment appears frequently in many practical wireless scenarios when the assumption that channel conditions are governed by a stationary stochastic process does not readily apply. In this paper, we prove that even in the above adversarial setting, the MAX-WEIGHT protocol keeps the queues in the network stable (i.e., keeps the queue sizes bounded) whenever this is feasible by some routing and scheduling algorithm. However, the proof is somewhat more complex than the negative potential drift argument that applied in the stationary case. Our proof holds for any arbitrary interference relationships among edges. We also prove the same stability of epsilon-approximate MAX-WEIGHT under the adversarial model. We conclude the paper with a discussion of queue sizes in the adversarial model as well as a set of simulation results.
Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
Issue Date
2014-12
Language
English
Article Type
Article
Keywords

SERVER ALLOCATION; CHANNELS; TIME; LINK

Citation

IEEE-ACM TRANSACTIONS ON NETWORKING, v.22, no.6, pp.1859 - 1872

ISSN
1063-6692
DOI
10.1109/TNET.2013.2288372
URI
http://hdl.handle.net/10203/201044
Appears in Collection
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 2 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0