NDLI: Random walks and Green's function on digraphs: a framework for estimating wireless transmission costs

Content Provider	ACM Digital Library
Author	Li, Yanhua Zhang, Zhi-Li
Copyright Year	2013
Abstract	Various applications in wireless networks, such as routing and query processing, can be formulated as random walks on graphs. Many results have been obtained for such applications by utilizing the theory of random walks (or spectral graph theory), which is mostly developed for undirected graphs. However, this formalism neglects the fact that the underlying (wireless) networks in practice contain asymmetric links, which are best characterized by directed graphs (digraphs). Therefore, random walk on digraphs is a more appropriate model to consider for such networks. In this paper, by generalizing the random walk theory (or spectral graph theory) that has been primarily developed for undirected graphs to digraphs, we show how various transmission costs in wireless networks can be formulated in terms of hitting times and cover times of random walks on digraphs. Using these results, we develop a unified theoretical framework for estimating various transmission costs in wireless networks. Our framework can be applied to random walk query processing strategy and the three routing paradigms--best path routing, opportunistic routing, and stateless routing--to which nearly all existing routing protocols belong. Extensive simulations demonstrate that the proposed digraph-based analytical model can achieve more accurate transmission cost estimation over existing methods.
Starting Page	135
Ending Page	148
Page Count	14
File Format	PDF
ISSN	10636692
DOI	10.1109/TNET.2012.2191158
Volume Number	21
Issue Number	1
Journal	IEEE/ACM Transactions on Networking (TON)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-02-01
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Digraph Random walk Spectral graph theory Transmission cost Wireless networks
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering Computer Networks and Communications Software Computer Science Applications

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

Random Walks and Green's Function on Digraphs: A Framework for Estimating Wireless Transmission Costs

Random walks on digraphs: A theoretical framework for estimating transmission costs in wireless routing (2010)

Random Walks on Digraphs: A Theoretical Framework for Estimating Transmission Costs in Wireless Routing

Analysis of latency of stateless opportunistic forwarding in intermittently connected networks

Line digraphs and coined quantum random walks.

Design and performance of wireless data gathering networks based on unicast random walk routing

Optimal throughput-delay scaling in wireless networks: part I: the fluid model

Weighted spectral distribution for internet topology analysis: theory and applications

Stationary distribution and cover time of random walks on random digraphs. (2011).

Random walks and Green's function on digraphs: a framework for estimating wireless transmission costs

Similar Documents

Random Walks and Green's Function on Digraphs: A Framework for Estimating Wireless Transmission Costs

Random walks on digraphs: A theoretical framework for estimating transmission costs in wireless routing (2010)

Random Walks on Digraphs: A Theoretical Framework for Estimating Transmission Costs in Wireless Routing

Analysis of latency of stateless opportunistic forwarding in intermittently connected networks

Line digraphs and coined quantum random walks.

Design and performance of wireless data gathering networks based on unicast random walk routing

Optimal throughput-delay scaling in wireless networks: part I: the fluid model

Weighted spectral distribution for internet topology analysis: theory and applications

Stationary distribution and cover time of random walks on random digraphs. (2011).

Random walks and Green's function on digraphs: a framework for estimating wireless transmission costs