Performance of random access scheduling schemes in multi-hop wireless networks

Changhee Joo; Ness B. Shroff

doi:10.1109/ACSSC.2006.355101

Performance of random access scheduling schemes in multi-hop wireless networks

Changhee Joo, Ness B. Shroff

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Citations (Scopus)

Abstract

The performance of scheduling schemes in multihop wireless networks has attracted significant attention in the recent literature. It is well known that optimal scheduling solutions require centralized information and lead to impractical implementations due to their enormous complexity (high-degree polynomial or NP-hard, depending on the interference scenario). Further, an important characteristic in many multi-hop scenarios is the need for distributed algorithms that operate on local information. Thus, in this paper we develop a constant-time random access distributed algorithm for scheduling in multihop wireless networks. An important feature of this scheme is that it achieves a 2-approximation efficiency ratio and can be implemented in an entirely distributed manner with low overhead.

Original language	English
Title of host publication	Conference Record of the 40th Asilomar Conference on Signals, Systems and Computers, ACSSC '06
Pages	1937-1941
Number of pages	5
DOIs	https://doi.org/10.1109/ACSSC.2006.355101
Publication status	Published - 2006
Externally published	Yes
Event	40th Asilomar Conference on Signals, Systems, and Computers, ACSSC '06 - Pacific Grove, CA, United States Duration: 2006 Oct 29 → 2006 Nov 1

Publication series

Name	Conference Record - Asilomar Conference on Signals, Systems and Computers
ISSN (Print)	1058-6393

Conference

Conference	40th Asilomar Conference on Signals, Systems, and Computers, ACSSC '06
Country/Territory	United States
City	Pacific Grove, CA
Period	06/10/29 → 06/11/1

ASJC Scopus subject areas

Signal Processing
Computer Networks and Communications

Access to Document

10.1109/ACSSC.2006.355101

Cite this

Performance of random access scheduling schemes in multi-hop wireless networks. / Joo, Changhee; Shroff, Ness B.
Conference Record of the 40th Asilomar Conference on Signals, Systems and Computers, ACSSC '06. 2006. p. 1937-1941 4176911 (Conference Record - Asilomar Conference on Signals, Systems and Computers).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Joo, C & Shroff, NB 2006, Performance of random access scheduling schemes in multi-hop wireless networks. in Conference Record of the 40th Asilomar Conference on Signals, Systems and Computers, ACSSC '06., 4176911, Conference Record - Asilomar Conference on Signals, Systems and Computers, pp. 1937-1941, 40th Asilomar Conference on Signals, Systems, and Computers, ACSSC '06, Pacific Grove, CA, United States, 06/10/29. https://doi.org/10.1109/ACSSC.2006.355101

@inproceedings{bd5871abe5d04bbfac7945207a003e6a,

title = "Performance of random access scheduling schemes in multi-hop wireless networks",

abstract = "The performance of scheduling schemes in multihop wireless networks has attracted significant attention in the recent literature. It is well known that optimal scheduling solutions require centralized information and lead to impractical implementations due to their enormous complexity (high-degree polynomial or NP-hard, depending on the interference scenario). Further, an important characteristic in many multi-hop scenarios is the need for distributed algorithms that operate on local information. Thus, in this paper we develop a constant-time random access distributed algorithm for scheduling in multihop wireless networks. An important feature of this scheme is that it achieves a 2-approximation efficiency ratio and can be implemented in an entirely distributed manner with low overhead.",

author = "Changhee Joo and Shroff, {Ness B.}",

year = "2006",

doi = "10.1109/ACSSC.2006.355101",

language = "English",

isbn = "1424407850",

series = "Conference Record - Asilomar Conference on Signals, Systems and Computers",

pages = "1937--1941",

booktitle = "Conference Record of the 40th Asilomar Conference on Signals, Systems and Computers, ACSSC '06",

note = "40th Asilomar Conference on Signals, Systems, and Computers, ACSSC '06 ; Conference date: 29-10-2006 Through 01-11-2006",

}

TY - GEN

T1 - Performance of random access scheduling schemes in multi-hop wireless networks

AU - Joo, Changhee

AU - Shroff, Ness B.

PY - 2006

Y1 - 2006

N2 - The performance of scheduling schemes in multihop wireless networks has attracted significant attention in the recent literature. It is well known that optimal scheduling solutions require centralized information and lead to impractical implementations due to their enormous complexity (high-degree polynomial or NP-hard, depending on the interference scenario). Further, an important characteristic in many multi-hop scenarios is the need for distributed algorithms that operate on local information. Thus, in this paper we develop a constant-time random access distributed algorithm for scheduling in multihop wireless networks. An important feature of this scheme is that it achieves a 2-approximation efficiency ratio and can be implemented in an entirely distributed manner with low overhead.

AB - The performance of scheduling schemes in multihop wireless networks has attracted significant attention in the recent literature. It is well known that optimal scheduling solutions require centralized information and lead to impractical implementations due to their enormous complexity (high-degree polynomial or NP-hard, depending on the interference scenario). Further, an important characteristic in many multi-hop scenarios is the need for distributed algorithms that operate on local information. Thus, in this paper we develop a constant-time random access distributed algorithm for scheduling in multihop wireless networks. An important feature of this scheme is that it achieves a 2-approximation efficiency ratio and can be implemented in an entirely distributed manner with low overhead.

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

U2 - 10.1109/ACSSC.2006.355101

DO - 10.1109/ACSSC.2006.355101

M3 - Conference contribution

AN - SCOPUS:47049094072

SN - 1424407850

SN - 9781424407859

T3 - Conference Record - Asilomar Conference on Signals, Systems and Computers

SP - 1937

EP - 1941

BT - Conference Record of the 40th Asilomar Conference on Signals, Systems and Computers, ACSSC '06

T2 - 40th Asilomar Conference on Signals, Systems, and Computers, ACSSC '06

Y2 - 29 October 2006 through 1 November 2006

ER -

Performance of random access scheduling schemes in multi-hop wireless networks

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this