research-article

A model framework for greedy routing in a sensor network with a stochastic power scheme

Authors:

Holger P. Keeler,

Peter G. TaylorAuthors Info & Claims

ACM Transactions on Sensor Networks (TOSN), Volume 7, Issue 4

Article No.: 34, Pages 1 - 28

https://doi.org/10.1145/1921621.1921628

Published: 04 February 2011 Publication History

Abstract

A stochastic model is formulated and analyzed to study the advancements of messages under greedy routing in a sensor network with a power-saving scheme. The aim of this model is give a better understanding of stochastic dependencies arising in the system and to offer a method of computing the advancement of message under greedy routing. We observe that the majority of the stochastic dependence from a routing path is captured by including only the previous forwarding node location. We examine a simple uncoordinated power-saving scheme with a new understanding of its effects on local node density. We propose a method for sensibly limiting the number of transmission reattempts before concluding there is no node in the forwarding region. All expressions involving multidimensional integrals are derived and evaluated readily with quasi-Monte Carlo integration methods. An importance sampling function is derived to speed up the quasi-Monte Carlo methods. The integral expressions are compared to simulations and give very agreeable results.

References

[1]

Baccelli, F. and Blaszczyszyn, B. 2009a. Stochastic Geometry and Wireless Networks, Vol. I - Theory. NOW Publishers, Delft, The Netherlands.

Digital Library

[2]

Baccelli, F. and Blaszczyszyn, B. 2009b. Stochastic Geometry and Wireless Networks, Vol. II - Theory. NOW Publishers, Delft, The Netherlands.

Digital Library

[3]

Bose, P., Morin, P., Stojmenovic, I., and Urrutia, J. 1999. Routing with guaranteed delivery in ad hoc wireless networks. In Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications. ACM, 48--55.

Digital Library

[4]

Dousse, O., Mannersalo, P., and Thiran, P. 2004. Latency of wireless sensor networks with uncoordinated power saving mechanisms. In Proceedings of the 5th ACM International Symposium on Mobile Ad hoc Networking and Computing. ACM, 109--120.

Digital Library

[5]

Fabian, K., Roger, W., Yan, Z., and Aaron, Z. 2003. Geometric ad-hoc routing: Of theory and practice. In Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing. ACM, 63--72.

Digital Library

[6]

Finn, G. 1987. Routing and addressing problems in large metropolitican-scale internetworks. ISI Resear. rep.

[7]

Frey, H. 2004. Scalable geographic routing algorithms for wireless ad hoc networks. IEEE Netw. 18, 4, 18--22.

Digital Library

[8]

Galassi, M., Davies, J., Theiler, J., Gough, B., Jungman, G., Alken, P., Booth, M., and Rossi, F. 2009. GNU Scientific Library Reference Manual 3rd Ed. Network Theroy Ltd.

Digital Library

[9]

Haenggi, M. 2005. On routing in random Rayleigh fading networks. IEEE Trans. Wirel. Comm. 4, 4, 1553--1562.

Digital Library

[10]

Haenggi, M., Andrews, J., Baccelli, F., Dousse, O., and Franceschetti, M. 2009. Stochastic geometry and random graphs for the analysis and design of wireless networks. IEEE J. Select. Areas Comm. 27, 7, 1029--1046.

Digital Library

[11]

Halton, J. 1960. On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numer. Math. 2, 1, 84--90.

Digital Library

[12]

Hou, T.-C. and Li, V. 1986. Transmission range control in multihop packet radio networks. IEEE Trans. Comm. 34, 1, 38--44.

[13]

Karp, B. and Kung, H. T. 2000. Greedy perimeter stateless routing for wireless networks. In Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 00). 243--254.

Digital Library

[14]

Keeler, H. P. 2009. A stochastic analysis of greedy routing in a spatially dependent sensor network. http://www.ms.unimelb.edu.au/~keeler/VaryingLambda.pdf.

[15]

Keeler, H. P. 2010. Stochastic routing models in sensor networks. Ph.D. thesis, University of Melbourne.

[16]

Keeler, H. P. and Taylor, P. G. 2010. A stochastic analysis of a greedy routing scheme in sensor networks. SIAM J. Appl. Math. 70, 7, 2214--2238.

[17]

Kleinrock, L. and Silvester, J. 1978. Optimum transmission radii for packet radio networks or why six is a magic number. In Proceedings of the Conference IEEE National Telecommunications. 4.31--4.35.

[18]

Kocis, L. and Whiten, W. J. 1997. Computational investigations of low-dicrepancy sequences. ACM Trans. Math. Softw. 23, 2, 266--294.

Digital Library

[19]

Kotz, D., Newport, C., and Elliot, C. 2003. The mistaken axioms of wireless-network research. Tech. rep. tr2003-467, Dartmouth College.

[20]

Kranakis, E., Singh, H., and Urrutia, J. 1999. Compass routing on geometric networks. In Proceedings of the 11th Candian Conference on Computational Geometry.

[21]

Kuhn, F., Wattenhofer, R., and Zollinger, A. 2007. Ad hoc networks beyond unit disk graphs. Wirel. News 14, 5, 715--729.

Digital Library

[22]

Kuo, F. Y. and Sloan, I. H. 2005. Lifting the curse of dimensionality. Not. AMS 52, 11, 1320--1328.

[23]

Mauve, M., Widmer, A., and Hartenstein, H. 2001. A survey on position-based routing in mobile ad hoc networks. IEEE Netw. 15, 6, 30--39.

Digital Library

[24]

Niederreiter, H. 1992. &Racute;andom Number Generation and Quasi-Monte Carlo Methodsacute;. SIAM.

Digital Library

[25]

Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. 1994. Numerical Recipes in C 2nd Ed. Cambridge University Press.

[26]

Sobol, I. 1967. The distribution of points in a cube and the approximate evaluation of integrals. U.S.S.R. Comput. Math. Math. Phys. 7, 4, 86--112. (In Russian).

[27]

Spanier, J. and Maize, E. H. 1994. Quasi-random methods for estimating integrals using relatively small samples. SIAM Rev. 36, 1, 18--44.

Digital Library

[28]

Srinivasa, S. and Haenggi, M. 2008. Distance distributions in finite uniformly random networks: Theory and applications. http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5299075

[29]

Stojmenovic, I. 2002. Position-based routing in ad hoc networks. IEEE Comm. Mag. 40, 7, 128--134.

Digital Library

[30]

Stoyan, D., Kendall, W., and Mecke, J. 1995. Stochastic Geometry and its Applications 2nd Ed. Wiley.

[31]

Takagi, H. and Kleinrock, L. 1984. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Trans. Comm. 32, 3, 246--257.

[32]

The Mathworks. 2008. Matlab 7.7 - Statistics Toolbox. http://www.mathworks.com/products/statistics/.

[33]

Wang, X. and Sloan, I. H. 2005. Why are high-dimensional finance problems often of low effective dimension&quest; SIAM J. Sci. Comput. 27, 1, 159--183.

Digital Library

[34]

Zorzi, M. and Rao, R. R. 2003. Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Multihop performance. IEEE Trans. Mobile Comput. 2, 4, 337--348. 1536-1233.

Digital Library

[35]

Zorzi, M. and Rao, R. R. 2004. Energy-Efficient forwarding for ad hoc and sensor networks in the presence of fading. In Proceedings of the IEEE International Conference on Communications 7. 3784--3789.

Cited By

Blaszczyszyn BKeeler H(2019)Determinantal thinning of point processes with network learning applications2019 IEEE Wireless Communications and Networking Conference (WCNC)10.1109/WCNC.2019.8885526(1-8)Online publication date: Apr-2019
https://doi.org/10.1109/WCNC.2019.8885526
Yang ALi YKong FWang GChen E(2018)Security Control Redundancy Allocation Technology and Security Keys Based on Internet of ThingsIEEE Access10.1109/ACCESS.2018.28689516(50187-50196)Online publication date: 2018
https://doi.org/10.1109/ACCESS.2018.2868951
Antunes NJacinto GPacheco A(2015)Hop Count Distributions of the Furthest and Nearest Distance Routing Protocols in Mobile Ad Hoc NetworksSIAM Journal on Applied Mathematics10.1137/13094179175:2(335-349)Online publication date: Jan-2015
https://doi.org/10.1137/130941791
Show More Cited By

Index Terms

A model framework for greedy routing in a sensor network with a stochastic power scheme
1. Mathematics of computing
  1. Probability and statistics
    1. Stochastic processes

Recommendations

Three-dimensional greedy routing in large-scale random wireless sensor networks

In this paper, we investigate how to design greedy routing to achieve sustainable and scalable in a large-scale three-dimensional (3D) sensor network. Several 3D position-based routing protocols were proposed to seek either delivery guarantee or energy-...
A greedy-based stable multi-path routing protocol in mobile ad hoc networks

With the increasing popularity of multimedia, there is a growing tendency in mobile ad hoc networks (MANETs) to establish stable routes with long route lifetimes, low control overhead and high packet delivery ratios. According to recent analytical ...
Greedy Routing with Anti-Void Traversal for Wireless Sensor Networks

The unreachability problem (i.e., the so-called void problem) that exists in the greedy routing algorithms has been studied for the wireless sensor networks. Some of the current research work cannot fully resolve the void problem, while there exist ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Sensor Networks

ACM Transactions on Sensor Networks Volume 7, Issue 4

February 2011

252 pages

ISSN:1550-4859

EISSN:1550-4867

DOI:10.1145/1921621

Issue’s Table of Contents

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 04 February 2011

Accepted: 01 August 2010

Revised: 01 August 2010

Received: 01 August 2009

Published in TOSN Volume 7, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
413
Total Downloads

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

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Blaszczyszyn BKeeler H(2019)Determinantal thinning of point processes with network learning applications2019 IEEE Wireless Communications and Networking Conference (WCNC)10.1109/WCNC.2019.8885526(1-8)Online publication date: Apr-2019
https://doi.org/10.1109/WCNC.2019.8885526
Yang ALi YKong FWang GChen E(2018)Security Control Redundancy Allocation Technology and Security Keys Based on Internet of ThingsIEEE Access10.1109/ACCESS.2018.28689516(50187-50196)Online publication date: 2018
https://doi.org/10.1109/ACCESS.2018.2868951
Antunes NJacinto GPacheco A(2015)Hop Count Distributions of the Furthest and Nearest Distance Routing Protocols in Mobile Ad Hoc NetworksSIAM Journal on Applied Mathematics10.1137/13094179175:2(335-349)Online publication date: Jan-2015
https://doi.org/10.1137/130941791
Banaei ACline DGeorghiades CCui S(2015)On asymptotic statistics for geometric routing schemes in wireless ad hoc networksIEEE/ACM Transactions on Networking10.1109/TNET.2014.230347723:2(559-573)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1109/TNET.2014.2303477
Zhu LLi CWang YLuo ZLiu ZLi BWang X(2015)On Stochastic Analysis of Greedy Routing in Vehicular NetworksIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2015.244677116:6(3353-3366)Online publication date: 24-Nov-2015
https://dl.acm.org/doi/10.1109/TITS.2015.2446771
Shen HBai GZhao LGe JTang Z(2015)L2ORWireless Personal Communications: An International Journal10.1007/s11277-014-2214-082:1(401-422)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1007/s11277-014-2214-0
Deng JHuang SHan Y(2012)An Online Relay Selection Scheme in Power Controllable Wireless Sensor NetworksInternational Journal of Distributed Sensor Networks10.1155/2012/2135988:6(213598)Online publication date: Jan-2012
https://doi.org/10.1155/2012/213598
Keeler HTaylor P(2012)Random Transmission Radii in Greedy Routing Models for Ad Hoc Sensor NetworksSIAM Journal on Applied Mathematics10.1137/11082354772:2(535-557)Online publication date: Jan-2012
https://doi.org/10.1137/110823547
KEELER H(2012)A stochastic analysis of greedy routing in a spatially dependent sensor networkEuropean Journal of Applied Mathematics10.1017/S095679251200006X23:04(485-514)Online publication date: 27-Mar-2012
https://doi.org/10.1017/S095679251200006X

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents