Abstract
With the increased adoption of technologies like wireless sensor networks by real-world applications, dynamic network topologies are becoming the rule rather than the exception. Node mobility, however, introduces a range of problems (communication interference, path uncertainty, low quality of service and information loss, etc.) that are not handled well by periodically refreshing state information, as algorithms designed for static networks typically do. To address specifically this problem, the main contribution of this paper is the introduction of a novel mechanism (called ASH) for the creation of a quasi-static overlay on top of a mobile topology. It is powered by simple, local interactions between nodes and exhibits self-healing and self-organization capabilities with respect to failures and node mobility. We show that the overlay mechanism works without assumptions about position, orientation, speed, motion correlation, and trajectory prediction of the nodes. A preliminary evaluation by means of simulation shows that ASH succeeds in tackling node mobility, while consuming only minimal resources.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Abbasi AA, Younis M (2007) A survey on clustering algorithms for wireless sensor networks. Comput Commun 30(14–15): 2826–2841
Abelson H, Allen D, Coore D, Hanson C, Homsy G, Knight TF Jr, Nagpal R, Rauch E, Sussman GJ, Weiss R (2000) Amorphous computing. Commun ACM 43(5): 74–82
Akyildiz IF, Estrin D, Culler DE, Srivastava MB (eds) (2003) In: Proceedings of the 1st international conference on embedded networked sensor systems, SenSys 2003, Los Angeles, California, USA, November 5–7, 2003. ACM
Avin C, Brito C (2004) Efficient and robust query processing in dynamic environments using random walk techniques. In: IPSN 2004, pp 277–286
Bastien C, Michel D (2005) Cellular automata modeling of physical systems. Cambridge University Press, Cambridge
Bettstetter C (2001) International workshop on modeling analysis and simulation of wireless and mobile systems. In: MSWIM 2001, pp 19–27
Camp T, Boleng J, Davies V (2002) A survey of mobility models for ad hoc network research. Wirel Commun Mobile Comput 2(5): 483–502
Chaintreau A, Le Boudec J-Y, Ristanovic N (2009) The age of gossip: spatial mean field regime. In: SIGMETRICS/Performance 2009, pp 109–120
Chu T, Nikolaidis I (2004) Node density and connectivity properties of the random waypoint model. Comput Commun 27(10): 914–922 (Protocol engineering for wired and wireless networks)
De Rosa M, Goldstein S, Lee P, Pillai P, Campbell J (2008) Programming modular robots with locally distributed predicates. In Robotics and Automation, 2008. ICRA 2008. IEEE International Conference on pages 3156–3162. IEEE
Degesys J, Rose I, Patel A, Nagpal R (2007) Desync: self-organizing desynchronization and tdma on wireless sensor networks. In: IPSN 2007
Dhurandher SK, Singh GV (2005) Weight based adaptive clustering in wireless ad hoc networks. In: ICPWC 2005, pp 95–100
Dimakis A, Rabbat M (2005) Gossip and message-passing algorithms for sensor networks. IEEE Trans Inf Theory 58(3): 1731–1742
Goldstein Seth C, Campbell JD, Mowry TC (2005) Programmable matter. IEEE Comput 38(6): 99–101
Grossglauser M, Tse David NC (2002) Mobility increases the capacity of ad hoc wireless networks. IEEE/ACM Trans Netw 10(4): 477–486
Gupta P, Kumar PR (2000) The capacity of wireless networks. IEEE Trans Inf Theory 46(2): 388–404
Heinzelman WR, Ch A, Balakrishnan H (2000) Energy-efficient communication protocol for wireless microsensor networks. In: HICSS 2000, pp 3005–3014
Hnat TW, Sookoor TI, Hooimeijer P, Weimer W, Whitehouse K (2008) Macrolab: a vector-based macroprogramming framework for cyber-physical systems. In: SenSys 2008
Iwanicki K, van Steen M (2010) Gossip-based self-management of a recursive area hierarchy for large wireless sensornets. IEEE Trans Parallel Distrib Syst 21(4): 562–576
Jardosh A, Belding-Royer EM, Almeroth KC, Suri S (2003) Towards realistic mobility models for mobile ad hoc networks. In: MobiCom 2003
Johnson DB, Maltz DA (1996) Dynamic source routing in ad hoc wireless networks. In: Mobile Computing 1996
Karpelson M, Wei G-Y, Wood RJ (2009) Milligram-scale high-voltage power electronics for piezoelectric microrobots. In: ICRA 2009
Kempe D, Dobra A, Gehrke J (2003) Gossip-based computation of aggregate information. In: FOCS 2003
Khelil A, Becker C, Tian J, Rothermel K (2002) An epidemic model for information diffusion in manets. In: MSWiM 2002, pp 54–60
Lee K, Hong S, Kim SJ, Rhee I, Chong S (2009) Slaw: a mobility model for human walks. In: INFOCOM 2009, IEEE, pp 855–863
Mitchell M (2009) Complexity: a guided tour. Oxford University Press, Inc., New York
Royer EM, Melliar-Smith PM, Moser LE (2001) An analysis of the optimum node density for ad hoc mobile networks. In: ICC 2001, pp 857–861
Sarwate AD, Dimakis AG (2009) The impact of mobility on gossip algorithms. In: INFOCOM 2009, IEEE 10
Werner-Allen G, Tewari G, Patel A, Welsh M, Nagpal R (2005) Firefly-inspired sensor network synchronicity with realistic radio effects. In: SENSYS 2005
Xu K, Hong X, Gerla M (2002) An ad hoc network with mobile backbones. In: Communications, 2002. ICC 2002. IEEE international conference on vol 5. IEEE, pp 3138–3143
Yamins D (2008) A theory of local-to-global algorithms for one-dimensional spatial multi-agent systems. PhD thesis, Harvard, Cambridge, MA, USA, Adviser-Nagpal, Radhika
Youssef MA, Youssef A, Younis MF (2009) Overlapping multihop clustering for wireless sensor networks. In: IEEE transactions on parallel and distributed systems, pp 1844–1856
Yu JY, Chong PHJ (2005) A survey of clustering schemes for mobile ad hoc networks. IEEE Commun Surv Tutor 7(1): 32–48 (qtr. 2005)
Zhang Y, Ng JM, Low CP (2009) A distributed group mobility adaptive clustering algorithm for mobile ad hoc networks. Comput Commun 32(1): 189–202
Zorzi M, Rao RR (2003) Geographic random forwarding (geraf) for ad hoc and sensor networks: energy and latency performance. In: IEEE Transactions on Mobile Computing, 2003
Zuniga M, Avin C, Hauswirth M (2010) Querying dynamic wireless sensor networks with non-revisiting random walks. In: EWSN 2010, pp 49–64
Open Access
This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
About this article
Cite this article
Pruteanu, A., Dulman, S. ASH: tackling node mobility in large-scale networks. Computing 94, 811–832 (2012). https://doi.org/10.1007/s00607-012-0202-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00607-012-0202-3