More Web Proxy on the site http://driver.im/

research-article

Random walk based routing protocol for wireless sensor networks

Authors:

Issam Mabrouki,

Xavier Lagrange,

Gwillerm FrocAuthors Info & Claims

ValueTools '07: Proceedings of the 2nd international conference on Performance evaluation methodologies and tools

Article No.: 71, Pages 1 - 10

Published: 22 October 2007 Publication History

Abstract

In recent years, design of wireless sensor networks using methodologies and mechanisms from other disciplines has gained popularity for addressing many networking aspects and providing more flexible and robust algorithms. We address in this paper the problem of random walk to model routing for data gathering in wireless sensor networks. While at first glance, this approach may seem to be overly simplistic and highly inefficient, many encouraging results that prove its comparability with other approaches have been obtained over the years. In this approach, a packet generated from a given sensor node performs a random motion until reaching a sink node where it is collected. The objective of this paper is to give an analytical model to evaluate the performance of the envisioned routing scheme with special attention to two metrics: the mean system data gathering delay and the induced spatial distribution of energy consumption. The main result shows that this approach achieves acceptable performance for applications without too stringent QoS requirements provided that the ratio of sink nodes over the total number of sensor nodes is carefully tuned.

References

[1]

MC13192, 2.4 GHz low power transceiver for the IEEE 802.15.4 standard, may 2007.

[2]

M. Alanyali, V. Saligrama, and O. Sava. A random-walk model for distributed computation in energy-limited network. In Proc. of 1st Workshop on Information Theory and its Application, 2006.

[3]

C. Avin and C. Brito. Efficient and robust query processing in dynamic environments using random walk techniques. In Proc. of the third international symposium on Information processing in sensor networks, 2004.

Digital Library

[4]

X. Bai, S. Kumar, Z. Yun, D. Xuan, and T. H. Lai. Deploying wireless sensors to achieve both coverage and connectivity. In Proceedings of the Seventh International Symposium on Mobile Ad Hoc Networking and Computing (ACM MobiHoc), Florence, Italy, 2006.

Digital Library

[5]

A. Chakrabarti, A. Sabharwal, and B. Aazhang. Multi-hop communication is order-optimal for homogeneous sensor networks. In Proc. of the third international symposium on Information processing in sensor networks, pages 178--185, NY, USA, April 2004. ACM Press.

Digital Library

[6]

P. Chen, B. O'Dea, and E. Callaway. Energy efficient system design with optimum transmission range for wireless ad hoc networks. In Proc. of the IEEE International Conference on Communications, volume 1, pages 945--952, April 2002.

[7]

S. Dolev, E. Schiller, and J. Welch. Random walk for self-stabilizing group communication in ad-hoc networks. In Proc. of the 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02). IEEE Computer Society, 2002.

Digital Library

[8]

S. Ergen and P. Varaiya. On multi-hop routing for energy efficiency. IEEE Communications Letters, 9(10):880--881, October 2005.

[9]

C. Gkantsidis, M. Mihail, and A. Saberi. Random walks in peer-to-peer networks. In Proc. of IEEE INFOCOM, 2004.

[10]

R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley Professional, 2nd edition, 1994.

Digital Library

[11]

B. D. Hughes. Random Walks and Random Environments. Oxford University Press, New York, 1995.

[12]

R. Kershner. The number of circles covering a set. American Journal of Mathematics, 61(3):665--671, July 1939.

[13]

S. K. Lando. Lectures on Generating Functions. American Mathematical Society, 2003.

[14]

L. Lima and J. Barros. Random walks on sensor networks. In Proc. of the 5th International Syposium on Modeling and Optimization in Mobile, Ad hoc, and Wireless Networks, April 2007.

[15]

K. Lindenberg, V. Seshadri, K. E. Shuler, and G. H. Weiss. Lattice random walks for sets of random walkers. first passage times. Journal of Statistical Physics, 23(1):11--25, July 1980.

[16]

L. H. Liyanage, C. M. Gulati, and J. M. Hill. A bibliography on applications of random-walks in theoretical chemistry and physics. Advances in Molecular Relaxation and Interaction Processes, 22:53--72, 1982.

[17]

E. W. Montroll and G. H. Weiss. Random walks on lattices. II. Journal of Mathematical Physics, 6(2):167--181, February 1965.

[18]

H. Scher and M. Lax. Stochastic transport in a disordered solid. I. theory. Phys. Rev. B, 7(10):4491--4502, May 1973.

[19]

S. D. Servetto and G. Barrenechea. Constrained random walks on random graphs: routing algorithms for large scale wireless sensor networks. In Proc. of the 1st ACM international workshop on Wireless sensor networks and applications, pages 12--21, NY, USA, 2002. ACM Press.

Digital Library

[20]

H. Tian, H. Shen, and T. Matsuzawa. Random walk routing for wireless sensor networks. In Proc. of the Sixth International Conference on Parallel and Distributed Computing Applications and Technologies, pages 196--200, Washington, DC, USA, 2005. IEEE Computer Society.

Digital Library

Cited By

Singh VVerma SKumar M(2018)DBCSWireless Personal Communications: An International Journal10.1007/s11277-017-5103-599:1(351-369)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1007/s11277-017-5103-5
Jhumka ABradbury MLeeke M(2015)Fake source-based source location privacy in wireless sensor networksConcurrency and Computation: Practice & Experience10.1002/cpe.324227:12(2999-3020)Online publication date: 25-Aug-2015
https://dl.acm.org/doi/10.1002/cpe.3242
Dhanapala DJayasumana AHan Q(2011)On random routing in wireless sensor gridsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2010.10.01671:3(369-380)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1016/j.jpdc.2010.10.016
Show More Cited By

Index Terms

Random walk based routing protocol for wireless sensor networks
1. Computing methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Index terms have been assigned to the content through auto-classification.

Recommendations

From Rosenstock model to random walk based routing in wireless sensor networks
VALUETOOLS '09: Proceedings of the Fourth International ICST Conference on Performance Evaluation Methodologies and Tools

In this paper, we investigate random walk based routing in wireless sensor networks (WSN) that contains sink nodes independently distributed at random. Our goal is to quantify the effectiveness of such techniques based on the derivation of closed-form ...
Compressive sensing based random walk routing in wireless sensor networks

Random walk (RW) routing for monitoring purposes in Wireless Sensor Networks (WSNs) has been proven to be an energy-efficient method. In this paper, we exploit the integration between Compressive Sensing (CS) and RW to reduce energy consumption for such ...
An efficient cluster-based communication protocol for wireless sensor networks

A wireless sensor network is a network of large numbers of sensor nodes, where each sensor node is a tiny device that is equipped with a processing, sensing subsystem and a communication subsystem. The critical issue in wireless sensor networks is how ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ValueTools '07: Proceedings of the 2nd international conference on Performance evaluation methodologies and tools

October 2007

708 pages

ISBN:9789639799004

General Chair:
Peter Glynn
Stanford University

Sponsors

Publisher

ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering)

Brussels, Belgium

Publication History

Published: 22 October 2007

Check for updates

Author Tags

Qualifiers

Research-article

Conference

Valuetools07

Sponsor:

Valuetools07: Second International Conference on Performance Evaluation Methodologies and Tools & Workshops

October 22 - 27, 2007

Nantes, France

Acceptance Rates

ValueTools '07 Paper Acceptance Rate 45 of 83 submissions, 54%;

Overall Acceptance Rate 90 of 196 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
669
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Singh VVerma SKumar M(2018)DBCSWireless Personal Communications: An International Journal10.1007/s11277-017-5103-599:1(351-369)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1007/s11277-017-5103-5
Jhumka ABradbury MLeeke M(2015)Fake source-based source location privacy in wireless sensor networksConcurrency and Computation: Practice & Experience10.1002/cpe.324227:12(2999-3020)Online publication date: 25-Aug-2015
https://dl.acm.org/doi/10.1002/cpe.3242
Dhanapala DJayasumana AHan Q(2011)On random routing in wireless sensor gridsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2010.10.01671:3(369-380)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1016/j.jpdc.2010.10.016
Li YZhang Z(2010)Random walks on digraphsProceedings of the 29th conference on Information communications10.5555/1833515.1833871(2775-2783)Online publication date: 14-Mar-2010
https://dl.acm.org/doi/10.5555/1833515.1833871
Rodero-Merino LAnta ALópez LCholvi V(2010)Performance of random walks in one-hop replication networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2009.10.00654:5(781-796)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1016/j.comnet.2009.10.006
Tzevelekas LOikonomou KStavrakakis I(2010)Random walk with jumps in large-scale random geometric graphsComputer Communications10.1016/j.comcom.2010.01.02633:13(1505-1514)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1016/j.comcom.2010.01.026
Dhanapala DJayasumana AHan Q(2009)Performance of random routing on grid-based sensor networksProceedings of the 6th IEEE Conference on Consumer Communications and Networking Conference10.5555/1700527.1700763(941-945)Online publication date: 11-Jan-2009
https://dl.acm.org/doi/10.5555/1700527.1700763

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents