On utilizing speed in networks of mobile agents

ABSTRACT

Population protocols are a model presented recently for networks with a very large, possibly unknown number of mobile agents having small memory. This model has certain advantages over alternative models (such as DTN) for such networks. However, it was shown that the computational power of this model is limited to semi-linear predicates only. Hence, various extensions were suggested.

We present a model that enhances the original model of population protocols by introducing a (weak) notion of speed of the agents. This enhancement allows us to design fast converging protocols with only weak requirements (for example, suppose that there are different types of agents, say agents attached to sick animals and to healthy animals, two meeting agents just need to be able to estimate which of them is faster, e.g., using their types, but not to actually know the speeds of their types).

Then, using the new model, we study the gathering problem, in which there is an unknown number of anonymous agents that have values they should deliver to a base station (without replications). We develop efficient protocols step by step searching for an optimal solution and adapting to the size of the available memory. The protocols are simple, though their analysis is somewhat involved. We also present a more involved result - a lower bound on the length of the worst execution for any protocol. Our proofs introduce several techniques that may prove useful also in future studies of time in population protocols.

References

1. M. K. Aguilera and S. Toueg. Timeliness-based wait-freedom: a gracefully degrading progress condition. In PODC'08, pages 305--314, 2008.
2. D. Angluin, J. Aspnes, Z. Diamadi, M. J. Fischer, and R. Peralta. Computation in networks of passively mobile finite-state sensors. DC, 18(4):235--253, 2006.
3. D. Angluin, J. Aspnes, and D. Eisenstat. Fast computation by population protocols with a leader. DC, 21(3):183--199, 2008.
4. D. Angluin, J. Aspnes, D. Eisenstat, and E. Ruppert. The computational power of population protocols. DC, 20(4):279--304, 2007.
5. D. Angluin, J. Aspnes, M. J. Fischer, and H. Jiang. Self-stabilizing population protocols. TAAS, 3(4), 2008.
6. J. Aspnes. Competitive analysis of distributed algorithms. In Online Algorithms, pages 118--146, 1996.
7. H. Attiya and J. Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics, 2nd Ed. Wiley, 2004.
8. A. Balasubramanian, B. N. Levine, and A. Venkataramani. DTN routing as a resource allocation problem. In SIGCOMM, pages 373--384, 2007.
9. J. Beauquier and J. Burman. Self-stabilizing synchronization in mobile sensor networks with covering. In DCOSS, 2010. To appear.
10. J. Beauquier, J. Burman, J. Clement, and S. Kutten. Brief announcement: Non-self-stabilizing and self-stabilizing gathering in networks of mobile agents - the notion of speed. In PODC, pages 286--287, 2009.
11. J. Beauquier, J. Burman, J. Clement, and S. Kutten. On utilizing speed in networks of mobile agents (extended abstract). Technical report, Technion, 2010. http://tx.technion.ac.il/~bjanna/pp.pdf.
12. J. Beauquier, J. Burman, and S. Kutten. Making population protocols self-stabilizing. In SSS, pages 90--104, 2009.
13. J. Beauquier, J. Clement, S. Messika, L. Rosaz, and B. Rozoy. Self-stabilizing counting in mobile sensor networks with a base station. In DISC, pages 63--76, 2007.
14. J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine. Maxprop: Routing for vehicle-based disruption-tolerant networks. In INFOCOM, 2006.
15. S. Cai, T. Izumi, and K. Wada. Space complexity of self-stabilizing leader election in passively-mobile anonymous agents. In SIROCCO, pages 113--125, 2009.
16. H. Dubois-Ferrière, M. Grossglauser, and M. Vetterli. Age matters: efficient route discovery in mobile ad hoc networks using encounter ages. In MobiHoc, pages 257--266, 2003.
17. C. Dwork, N. A. Lynch, and L. J. Stockmeyer. Consensus in the presence of partial synchrony. J. ACM, 35(2):288--323, 1988.
18. M. Fischer and H. Jiang. Self-stabilizing leader election in networks of finite-state anonymous agents. In OPODIS, pages 395--409, 2006.
19. T. Gao, C. Pesto, L. Selavo, Y. Chen, J. G. Ko, J. H. Lim, A. Terzis, A. Watt, J. Jeng, B. Chen, K. Lorincz, and M. Welsh. Wireless medical sensor networks in emergency response: Implementation and pilot results. In Technologies for Homeland Security, 2008 IEEE Conference on, pages 187--192, 2008.
20. M. Grossglauser and M. Vetterli. Locating nodes with EASE: Mobility diffusion of last encounters in ad hoc networks. In INFOCOM, 2003.
21. R. Guerraoui and E. Ruppert. Even small birds are unique: Population protocols with identifiers. In Technical Report CSE-2007-04. York University, 2007.
22. H. Hof. Applications of sensor networks. In Algorithms for Sensor and Ad Hoc Networks, pages 1--20, 2007.
23. S. Jain, K. R. Fall, and R. K. Patra. Routing in a delay tolerant network. In SIGCOMM, pages 145--158, 2004.
24. S. Jain, R. C. Shah, W. Brunette, G. Borriello, and S. Roy. Exploiting mobility for energy efficient data collection in wireless sensor networks. Mob. Netw. Appl., 11(3):327--339, 2006.
25. P. Juang, H. Oki, Y. Wang, M. Martonosi, L. Peh, and D. Rubenstein. Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet. In ASPLOS, pages 96--107, 2002.
26. S. Lahde, M. Doering, W. Pottner, G. Lammert, and L. C. Wolf. A practical analysis of communication characteristics for mobile and distributed pollution measurements on the road. Wirel. Comm. and Mob. Comput., 7(10):1209--1218, 2007.
27. J. Lundquist, D. Cayan, and M. Dettinger. Meteorology and hydrology in Yosemite National Park: A sensor network application. F. Zhao and L. Guibas (Eds.): IPSN 2003, LNCS, 2634:518--528, 2003.
28. H. Massey and L. H. Bedford. The role of satellites in observing and forecasting the global behaviour of the atmosphere: Discussion. Royal Society of London Proceedings Series A, 308:172-+, Jan. 1969.
29. L. Pelusi, A. Passarella, and M. Conti. Opportunistic networking: data forwarding in disconnected mobile ad hoc networks. Comm. Magazine, IEEE, 44:134--141, 2006.
30. D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Comm. ACM, 28(2):202--208, 1985.
31. Y. Sudo, J. Nakamura, Y. Yamauchi, F. Ooshita, H. Kakugawa, and T. Masuzawa. Loosely-stabilizing leader election in population protocols model. In SIROCCO, pages 295--308, 2009.
32. G. Tel. Introduction to Distributed Algorithms (2nd ed.). Cambridge University Press, 2000.
33. W. Zhao, M. H. Ammar, and E. W. Zegura. A message ferrying approach for data delivery in sparse mobile ad hoc networks. In MobiHoc, pages 187--198, 2004.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

• Theory of computation

  • Design and analysis of algorithms