The impact of interference on optimal multi-path routing in ad hoc networks

Roland de Haan; Richardus J. Boucherie; Jan C.W. van Ommeren

doi:10.1007/978-3-540-72990-7_70

The impact of interference on optimal multi-path routing in ad hoc networks

Roland de Haan, Richardus J. Boucherie, Jan C.W. van Ommeren

Stochastic Operations Research

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

12 Downloads (Pure)

Abstract

We develop a queueing model characterizing explicitly the impact of interference on end-to-end performance measures such as throughput in ad hoc networks, emphasizing the performance trade-off between single-path and multi-path routing. It may seem attractive to employ multi-path routing, but as all nodes share a single channel, efficiency may drop due to increased interference levels thus yielding singlepath performance for some topologies. We formulate a nonlinear programming problem to optimize network performance. Next, we focus on network capacity and show that for this objective the optimum could be found by solving an exponential number of linear programmes. We propose a greedy algorithm that efficiently searches these programmes to approximate the optimal solution. Numerical results for small topologies provide structural insight in optimal path selection and demonstrate the excellent performance of the proposed algorithm. Besides, larger networks and more advanced scenarios with multiple source-destination pairs and different radio ranges are analyzed.

Original language	Undefined
Title of host publication	Managing Traffic Performance in Converged Networks, Proceedings International Teletraffic Congress, ITC-20
Editors	Lorne Mason, Tadeusz Drwiega, James Yan
Place of Publication	Berlin/Heidelberg
Publisher	Springer
Pages	803-815
Number of pages	13
ISBN (Print)	9783540729907
DOIs	https://doi.org/10.1007/978-3-540-72990-7_70
Publication status	Published - Sept 2007
Event	20th International Teletraffic Congress 2007 - Ottawa, Canada Duration: 17 Jun 2007 → 21 Jun 2007 Conference number: 20

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Number	Paper P-NS
Volume	4516
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th International Teletraffic Congress 2007
Abbreviated title	ITC 2007
Country/Territory	Canada
City	Ottawa
Period	17/06/07 → 21/06/07

Keywords

MSC-90C35
Ad hoc networks - Interference - Capacity - Multi-path routing - Network optimization
IR-62017
METIS-245774
EWI-11401

Access to Document

10.1007/978-3-540-72990-7_70

http://eprints.eemcs.utwente.nl/secure2/11401/01/2007-XHaanBoucherieOmmeren.pdf

Cite this

de Haan, R., Boucherie, R. J., & van Ommeren, J. C. W. (2007). The impact of interference on optimal multi-path routing in ad hoc networks. In L. Mason, T. Drwiega, & J. Yan (Eds.), Managing Traffic Performance in Converged Networks, Proceedings International Teletraffic Congress, ITC-20 (pp. 803-815). Article 10.1007/978-3-540-72990-7_70 (Lecture Notes in Computer Science; Vol. 4516, No. Paper P-NS). Springer. https://doi.org/10.1007/978-3-540-72990-7_70

de Haan, Roland ; Boucherie, Richardus J. ; van Ommeren, Jan C.W. / The impact of interference on optimal multi-path routing in ad hoc networks. Managing Traffic Performance in Converged Networks, Proceedings International Teletraffic Congress, ITC-20. editor / Lorne Mason ; Tadeusz Drwiega ; James Yan. Berlin/Heidelberg : Springer, 2007. pp. 803-815 (Lecture Notes in Computer Science; Paper P-NS).

@inproceedings{a33f3849460a495f8ab03d10b1833cd1,

title = "The impact of interference on optimal multi-path routing in ad hoc networks",

abstract = "We develop a queueing model characterizing explicitly the impact of interference on end-to-end performance measures such as throughput in ad hoc networks, emphasizing the performance trade-off between single-path and multi-path routing. It may seem attractive to employ multi-path routing, but as all nodes share a single channel, efficiency may drop due to increased interference levels thus yielding singlepath performance for some topologies. We formulate a nonlinear programming problem to optimize network performance. Next, we focus on network capacity and show that for this objective the optimum could be found by solving an exponential number of linear programmes. We propose a greedy algorithm that efficiently searches these programmes to approximate the optimal solution. Numerical results for small topologies provide structural insight in optimal path selection and demonstrate the excellent performance of the proposed algorithm. Besides, larger networks and more advanced scenarios with multiple source-destination pairs and different radio ranges are analyzed.",

keywords = "MSC-90C35, Ad hoc networks - Interference - Capacity - Multi-path routing - Network optimization, IR-62017, METIS-245774, EWI-11401",

author = "{de Haan}, Roland and Boucherie, {Richardus J.} and {van Ommeren}, {Jan C.W.}",

note = "10.1007/978-3-540-72990-7_70 ; 20th International Teletraffic Congress 2007 ; Conference date: 17-06-2007 Through 21-06-2007",

year = "2007",

month = sep,

doi = "10.1007/978-3-540-72990-7_70",

language = "Undefined",

isbn = "9783540729907",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

number = "Paper P-NS",

pages = "803--815",

editor = "Lorne Mason and Tadeusz Drwiega and James Yan",

booktitle = "Managing Traffic Performance in Converged Networks, Proceedings International Teletraffic Congress, ITC-20",

address = "Germany",

}

de Haan, R, Boucherie, RJ & van Ommeren, JCW 2007, The impact of interference on optimal multi-path routing in ad hoc networks. in L Mason, T Drwiega & J Yan (eds), Managing Traffic Performance in Converged Networks, Proceedings International Teletraffic Congress, ITC-20., 10.1007/978-3-540-72990-7_70, Lecture Notes in Computer Science, no. Paper P-NS, vol. 4516, Springer, Berlin/Heidelberg, pp. 803-815, 20th International Teletraffic Congress 2007, Ottawa, Canada, 17/06/07. https://doi.org/10.1007/978-3-540-72990-7_70

The impact of interference on optimal multi-path routing in ad hoc networks. / de Haan, Roland; Boucherie, Richardus J.; van Ommeren, Jan C.W.
Managing Traffic Performance in Converged Networks, Proceedings International Teletraffic Congress, ITC-20. ed. / Lorne Mason; Tadeusz Drwiega; James Yan. Berlin/Heidelberg: Springer, 2007. p. 803-815 10.1007/978-3-540-72990-7_70 (Lecture Notes in Computer Science; Vol. 4516, No. Paper P-NS).

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

TY - GEN

T1 - The impact of interference on optimal multi-path routing in ad hoc networks

AU - de Haan, Roland

AU - Boucherie, Richardus J.

AU - van Ommeren, Jan C.W.

N1 - Conference code: 20

PY - 2007/9

Y1 - 2007/9

N2 - We develop a queueing model characterizing explicitly the impact of interference on end-to-end performance measures such as throughput in ad hoc networks, emphasizing the performance trade-off between single-path and multi-path routing. It may seem attractive to employ multi-path routing, but as all nodes share a single channel, efficiency may drop due to increased interference levels thus yielding singlepath performance for some topologies. We formulate a nonlinear programming problem to optimize network performance. Next, we focus on network capacity and show that for this objective the optimum could be found by solving an exponential number of linear programmes. We propose a greedy algorithm that efficiently searches these programmes to approximate the optimal solution. Numerical results for small topologies provide structural insight in optimal path selection and demonstrate the excellent performance of the proposed algorithm. Besides, larger networks and more advanced scenarios with multiple source-destination pairs and different radio ranges are analyzed.

AB - We develop a queueing model characterizing explicitly the impact of interference on end-to-end performance measures such as throughput in ad hoc networks, emphasizing the performance trade-off between single-path and multi-path routing. It may seem attractive to employ multi-path routing, but as all nodes share a single channel, efficiency may drop due to increased interference levels thus yielding singlepath performance for some topologies. We formulate a nonlinear programming problem to optimize network performance. Next, we focus on network capacity and show that for this objective the optimum could be found by solving an exponential number of linear programmes. We propose a greedy algorithm that efficiently searches these programmes to approximate the optimal solution. Numerical results for small topologies provide structural insight in optimal path selection and demonstrate the excellent performance of the proposed algorithm. Besides, larger networks and more advanced scenarios with multiple source-destination pairs and different radio ranges are analyzed.

KW - MSC-90C35

KW - Ad hoc networks - Interference - Capacity - Multi-path routing - Network optimization

KW - IR-62017

KW - METIS-245774

KW - EWI-11401

U2 - 10.1007/978-3-540-72990-7_70

DO - 10.1007/978-3-540-72990-7_70

M3 - Conference contribution

SN - 9783540729907

T3 - Lecture Notes in Computer Science

SP - 803

EP - 815

BT - Managing Traffic Performance in Converged Networks, Proceedings International Teletraffic Congress, ITC-20

A2 - Mason, Lorne

A2 - Drwiega, Tadeusz

A2 - Yan, James

PB - Springer

CY - Berlin/Heidelberg

T2 - 20th International Teletraffic Congress 2007

Y2 - 17 June 2007 through 21 June 2007

ER -

de Haan R, Boucherie RJ, van Ommeren JCW. The impact of interference on optimal multi-path routing in ad hoc networks. In Mason L, Drwiega T, Yan J, editors, Managing Traffic Performance in Converged Networks, Proceedings International Teletraffic Congress, ITC-20. Berlin/Heidelberg: Springer. 2007. p. 803-815. 10.1007/978-3-540-72990-7_70. (Lecture Notes in Computer Science; Paper P-NS). doi: 10.1007/978-3-540-72990-7_70