Performance evaluation of multi-path routing in reservation-based wireless networks

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Performance evaluation of multi-path routing in reservation-based wireless networks

Full text

Pdf (449 KB)

Source

International Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems archive
Proceedings of the 12th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems table of contents

Tenerife, Canary Islands, Spain

SESSION: Dissemination, multicast, routing table of contents

Pages 268-273

Year of Publication: 2009

ISBN:978-1-60558-616-8

Authors

Mattias Nissler	University of Kaiserslautern, Kaiserslautern, Germany
Reinhard Gotzhein	University of Kaiserslautern, Kaiserslautern, Germany

Sponsor

SIGSIM: ACM Special Interest Group on Simulation and Modeling

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 14, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1641804.1641849 What is a DOI?

ABSTRACT

Reservation-based wireless TDMA networks can provide deterministic quality-of-service guarantees to multi-hop data flows. The challenge is to route the flows and schedule appropriate transmission slots in a resource-efficient way. In this paper, we study the fundamental question whether multi-path routing, i.e. concurrent use of multiple paths for transmission of data belonging to the same flow, may yield better solutions to the joint routing and slot scheduling problem than single-path routing approaches. To answer this question, we first define an accurate network model. We then devise a branch-and-bound algorithm that computes optimal multi-path and single-path solutions to the joint routing and slot scheduling problem. We apply the algorithm to a large number of scenarios in randomly generated networks and compare optimal network load and end-to-end delay metric values in order to quantify the benefit of multi-path routing over the single-path approach. Our results show that in the studied settings, it is quite rare for multi-path solutions to surpass the optimal single-path solution. Multi-path routing should therefore not be considered an option to improve performance in reservation-based TDMA networks with random topologies.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. K. Marina and S. R. Das, "On-demand Multipath Distance Vector Routing in Ad Hoc Networks," in Proceedings of the Ninth International Conference on Network Protocols. Los Alamitos, CA, USA: IEEE Computer Society, 2001.
	2	R. M. Karp, "Reducibility Among Combinatorial Problems," in phComplexity of Computer Computations (Proceedings of a Symposium on the Complexity of Computer Computations), R. E. Miller and J. W. Thatcher, Eds. New York: Plenum Press, 1972, pp. 85--103.
	3	M. Nissler, "Modeling and Analysis of Optimal Slot Allocations in Wireless Ad-Hoc Networks," Diploma Thesis, University of Kaiserslautern, August 2008. [Online]. Available: http://agvs.informatik.uni-kl.de/publications/2008/Nis08/
	4	Texas Instruments, "2.4 GHz IEEE 802.15.4 / ZigBee-ready RF Transceiver," 2007. [Online]. Available: http://focus.ti.com/lit/ds/symlink/cc2420.pdf
	5	P. Becker, R. Gotzhein, and T. Kuhn, "Model-driven Performance Simulation of Self-organizing Systems with PartsSim," Praxis der Informationsverarbeitung und Kommunikation, vol. 31, no. 1, pp. 45--50, 2008.
	6	W.-H. Liao, Y.-C. Tseng, and K.-P. Shih, "A TDMA-based Bandwidth Reservation Protocol for QoS Routing in a Wireless Mobile Ad Hoc Network," in ICC 2002. IEEE International Conference on Communications, vol. 5, 2002, pp. 3186--3190.
	7	I. Jawhar and J. Wu, "A Race-Free Bandwidth Reservation Protocol for QoS Routing in Mobile Ad Hoc Networks," in Proceedings of the 37th Annual Hawaii Internation Conference on System Sciences, January 2004.
	8	Y.-S. Chen, Y.-C. Tseng, J.-P. Sheu, and P.-H. Kuo, "An on-demand, link-state, multi-path QoS routing in a wireless mobile ad-hoc network," Computer Communications, vol. 27, no. 1, pp. 27--40, January 2004.
	9	P. Björklund, P. Värbrand, and D. Yuan, "A Column Generation Method for Spacial TDMA Scheduling in Ad Hoc Networks," Ad Hoc Networks, vol. 2, no. 4, pp. 405--418, 2004.
	10	L. Tassiulas and A. Ephremides, "Jointly Optimal Routing and Scheduling in Packet Radio Networks," IEEE Transactions on Information Theory, vol. 38, no. 1, pp. 165--168, 1992.
	11	Y. Li and A. Ephremides, "A joint scheduling, power control, and routing algorithm for ad hoc wireless networks," Ad Hoc Networks, vol. 5, no. 7, pp. 959--973, 2007.
	12	Y. Ganjali and A. Keshavarzian, "Load Balancing in Ad Hoc Networks: Single-path Routing vs. Multi-path Routing," in INFOCOM 2004. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 2, 2004, pp. 1120--1125.
	13	E. Hyytiä and J. Virtamo, "On Optimality of Single-Path Routes in Massively Dense Wireless Multi-Hop Networks," in Proceedings of the 10th ACM Symposium on Modeling, analysis, and simulation of wireless and mobile systems. New York, NY, USA: ACM, 2007, pp. 28--35.