Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-25T19:18:43.296Z Has data issue: false hasContentIssue false
  • English
  • Français

A stochastic analysis of greedy routing in a spatially dependent sensor network

Published online by Cambridge University Press:  27 March 2012

HOLGER P. KEELER
HOLGER P. KEELER*
Affiliation:
Department of Mathematics and Statistics, University of Melbourne, Victoria, 3010, Melbourne, Australia and INRIA, Paris, France email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

For a sensor network, a tractable spatially dependent node deployment model is presented with the property that the density is inversely proportional to the sink distance. A stochastic model is formulated to examine message advancements under greedy routing in such a sensor network. The aim of this work is to demonstrate that an inhomogeneous Poisson process can be used to model a sensor network with spatially dependent node density. Symmetric elliptic integrals and asymptotic approximations are used to describe the random behaviour of hops. Types of dependence that affect hop advancements are examined. We observe that the dependence between successive jumps in a multi-hop path is captured by including only the previous forwarding node location. We include a simple uncoordinated sleep scheme, and observe that the complexity of the model is reduced when sufficiently many nodes are asleep. All expressions involving multi-dimensional integrals are derived and evaluated with quasi-Monte Carlo integration methods based on Halton sequences and recently developed lattice rules. An importance sampling function is derived to speed up the quasi-Monte Carlo methods. The ensuing results agree extremely well with simulations.

Keywords

ad hoc networkelliptic integralsnon-stationary process
Type
Papers
Information
European Journal of Applied Mathematics , Volume 23 , Issue 4 , August 2012 , pp. 485 - 514
Copyright
Copyright © Cambridge University Press 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Digital Library of Mathematical Functions, Accessed 15 January 2010. URL: http://dlmf.nist.gov/.Google Scholar
[2]Akyildiz, I. F., Weilian, S., Sankarasubramaniam, Y. & Cayirci, E. (2002) A survey on sensor networks. IEEE Commun. Mag. 40, 102–114.CrossRefGoogle Scholar
[3]Baccelli, F. & Blaszczyszyn, B. (2009) Stochastic Geometry and Wireless Networks, Volume I - Theory, Vol. 1, NOW Publishers, Delft, The Netherlands.CrossRefGoogle Scholar
[4]Baccelli, F. & Blaszczyszyn, B. (2009) Stochastic Geometry and Wireless Networks, Volume II - Theory, Vol. 1, NOW Publishers, Delft, The Netherlands.CrossRefGoogle Scholar
[5]Bose, P., Morin, P., Stojmenovic, I. & Urrutia, J. (1999) Routing with guaranteed delivery in ad hoc wireless networks. In: 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, ACM, pp. 48–55.Google Scholar
[6]Carlson, B. (1979) Computing elliptic integrals by duplication. Numer. Math. 33, 1–16.CrossRefGoogle Scholar
[7]Carlson, B. (1995) Numerical computation of real or complex elliptic integrals. Numer. Algorithms, 10, 13–26.CrossRefGoogle Scholar
[8]Chong, C. & Kumar, S. P. (2003) Sensor networks: Evolution, opportunities and challenges. Proc. IEEE 91, 1274–1256.Google Scholar
[9]Giles, M. B., Kuo, F. Y., Sloan, I. H. & Waterhouse, B. J. (Nov 2008) Quasi-monte carlo for finance applications. In: Mercer, G. N. & Roberts, A. J. (editors), Proceedings of the 14th Biennial Computational Techniques and Applications Conference, CTAC-2008, vol. 50 of ANZIAM Journal, pp. C308–C323.Google Scholar
[10]Haenggi, M., Andrews, J., Baccelli, F., Dousse, O. & Franceschetti, M. (2009) Stochastic geometry and random graphs for the analysis and design of wireless networks. IEEE J. Sel. Areas Commun. 27, 1029–1046.CrossRefGoogle Scholar
[11]Hall, P. (1988) Intoduction to the Theory of Coverage Process, 1st ed., John Wiley and Sons., Hoboken, NJ.Google Scholar
[12]Halton, J. (1960) On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numer. Math. 2, 84–90.CrossRefGoogle Scholar
[13]Ishizuka, M. & Aida, M. (2004) Performance study of node placement in sensor networks. In: Proceedings 24th International Conference on Distributed Computing Systems Workshops, March 2004, pp. 598–603.Google Scholar
[14]Ishizuka, M. & Aida, M. (2007) Stochastic node placement improving fault tolerance in wireless sensor networks Electron. Commun. Japan 90, 2181–2191.CrossRefGoogle Scholar
[15]Karp, B. & Kung, H. T. (2000) Greedy perimeter stateless routing for wireless networks. In: Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000), Los Angeles, California, pp. 243–254.Google Scholar
[16]Keeler, H. P. (2010) Stochastic Routing Models in Sensor Networks, PhD thesis, University of Melbourne.Google Scholar
[17]Keeler, H. P. & Taylor, P. G. (2010) A stochastic analysis of a greedy routing scheme in sensor networks. SIAM J. Appl. Math. 70, 2214–2238.CrossRefGoogle Scholar
[18]Keeler, H. P. & Taylor, P. G. (2011) A model framework for greedy routing in a sensor network with a stochastic power scheme. ACM Trans. Sensor Netw. 7, 34:1–34:28.CrossRefGoogle Scholar
[19]Kuhn, F., Wattenhofer, R., Zhang, Y. & Zollinger, A. (2003) Geometric ad-hoc routing of theory and practice. In: 22 nd Annual Symposium on Principles of Distributed Computing, Boston, Massachusetts.Google Scholar
[20]Kullback, S. (1959) Information Theory and Statistics, 1st ed., Wiley, New York.Google Scholar
[21]Kuo, F.Lattice rule generating vectors, http://web.maths.unsw.edu.au/~fkuo/lattice/index.html. Personal Website. Accessed 4 August 2009.Google Scholar
[22]Kuo, F. Y. & Sloan, I. H. (2005) Lifting the curse of dimensionality. Not. AMS 52, 1320–1328.Google Scholar
[23]Mauve, M., Widmer, A. & Hartenstein, H. (2001) A survey on position-based routing in mobile ad hoc networks. IEEE Netw. 15, 30–39.CrossRefGoogle Scholar
[24]Niederreiter, H. (1992) Ŕandom Number Generation and Quasi-Monte Carlo Methods, SIAM, pp. 13–18.CrossRefGoogle Scholar
[25]Pallavi, M., Ram, S. S. & Manjunath, D. (2009) Path coverage by a sensor field: The nonhomogeneous case. ACM Trans. Sensor Netw. 5, 1–26.Google Scholar
[26]Sobol, I. (1967) The distribution of points in a cube and the approximate evaluation of integrals. U.S.S.R. Comput. Math., and Math. Phys. 7, 86–112. (In Russian).CrossRefGoogle Scholar
[27]Spanier, J. & Maize, E. H. (1994) Quasi-random methods for estimating integrals using relatively small samples. SIAM Rev. 36, 18–44.CrossRefGoogle Scholar
[28]Stojmenovic, I. (2002) Position-based routing in ad hoc networks. IEEE Commun. Mag. 40, 128–134.CrossRefGoogle Scholar
[29]Stoyan, D., Kendall, W. & Mecke, J. (1995) Stochastic Geometry and Its Applications, 2nd ed., Wiley, New York.Google Scholar
[30]Tubaishat, M. & Madria, S. (2003) Sensor networks: An overview. IEEE Potentials 22, 20–23.CrossRefGoogle Scholar
[31]Wong, R. (1989) Asymptotic Approximations to Integrals, Academic Press, New York.Google Scholar
[32]Zorzi, M. & Rao, R. R. (2003) Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Multihop performance. IEEE Trans. Mobile Comput. 2, 349–365.CrossRefGoogle Scholar