Bandwidth reservation in multihop wireless networks: Complexity and mechanisms

Leonidas Georgiadis; Philippe Jacquet; Bernard Mans

Bandwidth reservation in multihop wireless networks: Complexity and mechanisms

Leonidas Georgiadis^*, Philippe Jacquet, Bernard Mans

^*Corresponding author for this work

School of Computing

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

25 Citations (Scopus)

Abstract

We show that link interferences in multihop wireless networks make the problem of selecting a path satisfying bandwidth requirements an NP-complete problem, even under simplified rules for bandwidth reservation. This is in sharp contrast to path selection in wireline networks where efficient polynomial algorithms exist. We also describe a distributed mechanism for the problem of slot allocation according to bandwidth reservation in a wireless slotted environment.

Original language	English
Title of host publication	Proceedings - 24th International Conference on Distributed Computing Systems Workshops
Editors	N.-F. Tzeng, M. Takizawa
Place of Publication	Los Alamitos, CA
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	762-767
Number of pages	6
Volume	24
ISBN (Print)	0769520863
Publication status	Published - 2004
Event	Proceedings - 24th International Conference on Distributed Computing Systems Workshops - Hachioji, Japan Duration: 23 Mar 2004 → 24 Mar 2004

Other

Other	Proceedings - 24th International Conference on Distributed Computing Systems Workshops
Country/Territory	Japan
City	Hachioji
Period	23/03/04 → 24/03/04

Cite this

@inproceedings{5bd79346a64b4e4191959709334bb73c,

title = "Bandwidth reservation in multihop wireless networks: Complexity and mechanisms",

abstract = "We show that link interferences in multihop wireless networks make the problem of selecting a path satisfying bandwidth requirements an NP-complete problem, even under simplified rules for bandwidth reservation. This is in sharp contrast to path selection in wireline networks where efficient polynomial algorithms exist. We also describe a distributed mechanism for the problem of slot allocation according to bandwidth reservation in a wireless slotted environment.",

author = "Leonidas Georgiadis and Philippe Jacquet and Bernard Mans",

year = "2004",

language = "English",

isbn = "0769520863",

volume = "24",

pages = "762--767",

editor = "N.-F. Tzeng and M. Takizawa",

booktitle = "Proceedings - 24th International Conference on Distributed Computing Systems Workshops",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

note = "Proceedings - 24th International Conference on Distributed Computing Systems Workshops ; Conference date: 23-03-2004 Through 24-03-2004",

}

Georgiadis, L, Jacquet, P & Mans, B 2004, Bandwidth reservation in multihop wireless networks: Complexity and mechanisms. in N-F Tzeng & M Takizawa (eds), Proceedings - 24th International Conference on Distributed Computing Systems Workshops. vol. 24, Institute of Electrical and Electronics Engineers (IEEE), Los Alamitos, CA, pp. 762-767, Proceedings - 24th International Conference on Distributed Computing Systems Workshops, Hachioji, Japan, 23/03/04.

Bandwidth reservation in multihop wireless networks: Complexity and mechanisms. / Georgiadis, Leonidas; Jacquet, Philippe; Mans, Bernard.
Proceedings - 24th International Conference on Distributed Computing Systems Workshops. ed. / N.-F. Tzeng; M. Takizawa. Vol. 24 Los Alamitos, CA: Institute of Electrical and Electronics Engineers (IEEE), 2004. p. 762-767.

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

TY - GEN

T1 - Bandwidth reservation in multihop wireless networks

T2 - Proceedings - 24th International Conference on Distributed Computing Systems Workshops

AU - Georgiadis, Leonidas

AU - Jacquet, Philippe

AU - Mans, Bernard

PY - 2004

Y1 - 2004

N2 - We show that link interferences in multihop wireless networks make the problem of selecting a path satisfying bandwidth requirements an NP-complete problem, even under simplified rules for bandwidth reservation. This is in sharp contrast to path selection in wireline networks where efficient polynomial algorithms exist. We also describe a distributed mechanism for the problem of slot allocation according to bandwidth reservation in a wireless slotted environment.

AB - We show that link interferences in multihop wireless networks make the problem of selecting a path satisfying bandwidth requirements an NP-complete problem, even under simplified rules for bandwidth reservation. This is in sharp contrast to path selection in wireline networks where efficient polynomial algorithms exist. We also describe a distributed mechanism for the problem of slot allocation according to bandwidth reservation in a wireless slotted environment.

UR - https://www.scopus.com/pages/publications/3042640532

M3 - Conference proceeding contribution

AN - SCOPUS:3042640532

SN - 0769520863

VL - 24

SP - 762

EP - 767

BT - Proceedings - 24th International Conference on Distributed Computing Systems Workshops

A2 - Tzeng, N.-F.

A2 - Takizawa, M.

PB - Institute of Electrical and Electronics Engineers (IEEE)

CY - Los Alamitos, CA

Y2 - 23 March 2004 through 24 March 2004

ER -

Bandwidth reservation in multihop wireless networks: Complexity and mechanisms

Abstract

Other

Other files and links

Fingerprint

Cite this