NDLI: Randomized 3D Geographic Routing

Content Provider	IEEE Xplore Digital Library
Author	Flury, R. Wattenhofer, R.R.
Copyright Year	2008
Description	Author affiliation: Comput. Eng. & Networks Lab., ETH Zurich, Zurich (Flury, R.; Wattenhofer, R.R.)
Abstract	We reconsider the problem of geographic routing in wireless ad hoc networks. We are interested in local, memoryless routing algorithms, i.e. each network node bases its routing decision solely on its local view of the network, nodes do not store any message state, and the message itself can only carry information about O(1) nodes. In geographic routing schemes, each network node is assumed to know the coordinates of itself and all adjacent nodes, and each message carries the coordinates of its target. Whereas many of the aspects of geographic routing have already been solved for 2D networks, little is known about higher-dimensional networks. It has been shown only recently that there is in fact no local memoryless routing algorithm for 3D networks that delivers messages deterministically. In this paper, we show that a cubic routing stretch constitutes a lower bound for any local memoryless routing algorithm, and propose and analyze several randomized geographic routing algorithms which work well for 3D network topologies. For unit ball graphs, we present a technique to locally capture the surface of holes in the network, which leads to 3D routing algorithms similar to the greedy-face-greedy approach for 2D networks.
Starting Page	834
Ending Page	842
File Size	329626
Page Count	9
File Format	PDF
ISBN	9781424420254
ISSN	0743166X
DOI	10.1109/INFOCOM.2008.135
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-04-13
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Peer to peer computing Ad hoc networks Computer networks Laboratories Mobile ad hoc networks IP networks Routing protocols Hardware Communications Society Algorithm design and analysis
Content Type	Text
Resource Type	Article
Subject	Computer Science Electrical and Electronic Engineering

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in