Queue back-pressure random access in multihop wireless networks: Optimality and stability

Jiaping Liu, Aleksandr Stolyar, Mung Chiang, H. Vincent Poor

Research output: Contribution to journalArticle

Abstract

A model for wireless networks with slotted-Aloha-type random access and with multihop flow routes is considered. The goal is to devise distributed algorithms for utility-optimal end-to-end throughput allocation and queueing stability. A class of queue back-pressure random access algorithms (QBRAs), in which actual queue lengths of the flows in each node's close neighborhood are used to determine the nodes' channel access probabilities, is studied. This is in contrast to some previously proposed algorithms, which are based on deterministic optimization formulations and are oblivious to actual queues. QBRA is also substantially different from the well-studied "MaxWeight" type scheduling algorithms, even though both use the concept of back-pressure.

Original languageEnglish (US)
Pages (from-to)4087-4098
Number of pages12
JournalIEEE Transactions on Information Theory
Volume55
Issue number9
DOIs
StatePublished - Sep 4 2009
Externally publishedYes

Fingerprint

Wireless networks
Scheduling algorithms
Parallel algorithms
Throughput
scheduling

Keywords

  • Aloha
  • Distributed algorithm
  • Queue back-pressure
  • Random access
  • Stability
  • Throughput region

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Cite this

Queue back-pressure random access in multihop wireless networks : Optimality and stability. / Liu, Jiaping; Stolyar, Aleksandr; Chiang, Mung; Poor, H. Vincent.

In: IEEE Transactions on Information Theory, Vol. 55, No. 9, 04.09.2009, p. 4087-4098.

Research output: Contribution to journalArticle

@article{c4770d983de2446eafbcf8c2020df1ae,
title = "Queue back-pressure random access in multihop wireless networks: Optimality and stability",
abstract = "A model for wireless networks with slotted-Aloha-type random access and with multihop flow routes is considered. The goal is to devise distributed algorithms for utility-optimal end-to-end throughput allocation and queueing stability. A class of queue back-pressure random access algorithms (QBRAs), in which actual queue lengths of the flows in each node's close neighborhood are used to determine the nodes' channel access probabilities, is studied. This is in contrast to some previously proposed algorithms, which are based on deterministic optimization formulations and are oblivious to actual queues. QBRA is also substantially different from the well-studied {"}MaxWeight{"} type scheduling algorithms, even though both use the concept of back-pressure.",
keywords = "Aloha, Distributed algorithm, Queue back-pressure, Random access, Stability, Throughput region",
author = "Jiaping Liu and Aleksandr Stolyar and Mung Chiang and Poor, {H. Vincent}",
year = "2009",
month = "9",
day = "4",
doi = "10.1109/TIT.2009.2025563",
language = "English (US)",
volume = "55",
pages = "4087--4098",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "9",

}

TY - JOUR

T1 - Queue back-pressure random access in multihop wireless networks

T2 - Optimality and stability

AU - Liu, Jiaping

AU - Stolyar, Aleksandr

AU - Chiang, Mung

AU - Poor, H. Vincent

PY - 2009/9/4

Y1 - 2009/9/4

N2 - A model for wireless networks with slotted-Aloha-type random access and with multihop flow routes is considered. The goal is to devise distributed algorithms for utility-optimal end-to-end throughput allocation and queueing stability. A class of queue back-pressure random access algorithms (QBRAs), in which actual queue lengths of the flows in each node's close neighborhood are used to determine the nodes' channel access probabilities, is studied. This is in contrast to some previously proposed algorithms, which are based on deterministic optimization formulations and are oblivious to actual queues. QBRA is also substantially different from the well-studied "MaxWeight" type scheduling algorithms, even though both use the concept of back-pressure.

AB - A model for wireless networks with slotted-Aloha-type random access and with multihop flow routes is considered. The goal is to devise distributed algorithms for utility-optimal end-to-end throughput allocation and queueing stability. A class of queue back-pressure random access algorithms (QBRAs), in which actual queue lengths of the flows in each node's close neighborhood are used to determine the nodes' channel access probabilities, is studied. This is in contrast to some previously proposed algorithms, which are based on deterministic optimization formulations and are oblivious to actual queues. QBRA is also substantially different from the well-studied "MaxWeight" type scheduling algorithms, even though both use the concept of back-pressure.

KW - Aloha

KW - Distributed algorithm

KW - Queue back-pressure

KW - Random access

KW - Stability

KW - Throughput region

UR - http://www.scopus.com/inward/record.url?scp=69449088291&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=69449088291&partnerID=8YFLogxK

U2 - 10.1109/TIT.2009.2025563

DO - 10.1109/TIT.2009.2025563

M3 - Article

AN - SCOPUS:69449088291

VL - 55

SP - 4087

EP - 4098

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 9

ER -