NDLI: Decentralized Routing in Nonhomogeneous Poisson Networks

Content Provider	IEEE Xplore Digital Library
Author	Chi Zhang Pan Li Fang, Y. Khargonekar, P.P.
Copyright Year	2008
Description	Author affiliation: Dept. of Electr. & Comput. Eng., Univ. of Florida, Gainesville, FL (Chi Zhang; Pan Li; Fang, Y.; Khargonekar, P.P.)
Abstract	In his seminal work, Jon Kleinberg considers a small-world network model consisting of a k-dimensional lattice augmented with shortcuts. Under the assumption that the probability of a shortcut being present between two nodes u and v decays as a power, d(u,v) -\alpha, of the distance d(u,v) between them, Kleinberg shows that decentralized routing scheme such as greedy geographic routing is efficient if alpha=k and that there is no efficient decentralized routing algorithm if alpha\neq k. The results are extended to a continuum model recently, wherein the nodes are distributed as a homogeneous Poisson point process by Franceschetti and Meester, Draief and Ganesh. In our work, we extend the result further to a more realistic model constructed from a nonhomogeneous Poisson point process, wherein each node is connected to all its neighbors within some fixed radius, as well as possessing random shortcuts to more distant nodes. More importantly, we show that in nonhomogeneous cases, the necessary and sufficient condition for greedy geographic routing to be efficient is that the probability of a shortcut being present from node u to v should be inversely proportional to the number of nodes which are closer to u than v is. We also demonstrate some applications of our results to wireless networks.
Starting Page	478
Ending Page	485
File Size	341668
Page Count	8
File Format	PDF
ISBN	9780769531724
ISSN	10636927
DOI	10.1109/ICDCS.2008.83
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-06-17
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Routing Ad hoc networks Wireless networks Social network services Algorithm design and analysis Distance measurement Lattices
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

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

Social network analysis concepts in the design of wireless Ad Hoc network protocols

On the Longest RNG Edge of Wireless Ad Hoc Networks

Geometric spanners for wireless ad hoc networks

Exploiting congestion information in network and higher layer protocols in multihop wireless ad hoc networks

Analysis of Clustering and Routing Overhead for Clustered Mobile Ad Hoc Networks

A generic distributed broadcast scheme in ad hoc wireless networks

Energy-aware distributed routing algorithm to tolerate network failure in wireless sensor networks

DRIFT: Efficient Message Ordering in Ad Hoc Networks Using Virtual Flooding

On Cooperative Caching in Wireless P2P Networks

Decentralized Routing in Nonhomogeneous Poisson Networks

Similar Documents

Social network analysis concepts in the design of wireless Ad Hoc network protocols

On the Longest RNG Edge of Wireless Ad Hoc Networks

Geometric spanners for wireless ad hoc networks

Exploiting congestion information in network and higher layer protocols in multihop wireless ad hoc networks

Analysis of Clustering and Routing Overhead for Clustered Mobile Ad Hoc Networks

A generic distributed broadcast scheme in ad hoc wireless networks

Energy-aware distributed routing algorithm to tolerate network failure in wireless sensor networks

DRIFT: Efficient Message Ordering in Ad Hoc Networks Using Virtual Flooding

On Cooperative Caching in Wireless P2P Networks

Decentralized Routing in Nonhomogeneous Poisson Networks