Communicating via fireflies: geographic routing on duty-cycled sensors

ABSTRACT

Geographic routing is a useful and scalable point-to-point communication primitive for wireless sensor networks. However, previous work on geographic routing makes the unrealistic assumption that all the nodes in the network are awake during routing. This overlooks the common deployment scenario where sensor nodes are duty-cycled to save energy. In this paper we investigate several important aspects of geographic routing over duty-cycled nodes. First, we extend existing geographic routing algorithms to handle the highly dynamic networks resulting from duty-cycling. Second, we provide the first formal analysis of the performance of geographic routing on duty-cycled nodes. Third, we use this analysis to develop an efficient decentralized sleep scheduling algorithm for reducing the number of awake nodes while maintaining both network coverage and a (tunable) target routing latency. Finally, we evaluate via simulation the performance of our approach versus running existing geographic routing algorithms on sensors duty-cycled according to previous sleep scheduling algorithms. Our results show, perhaps surprisingly, that a network of duty-cycled nodes can have slightly better routing performance than a static network that uses comparable energy. Our results further show that, compared to previous algorithms, our sleep scheduling algorithm significantly improves routing latency and network lifetime.

References

1. ABRAMS, Z., GOEL, A., AND PLOTKIN, S. Set k-cover algorithms for energy efficient monitoring in wireless sensor networks. In ACM/IEEE IPSN (2004).
2. BISWAS, S., AND MORRIS, R. Opportunistic routing in multi-hop wireless networks. In ACM SIGCOMM (2005).
3. CAO, Q., ABDELZAHER, T., HE, T., AND STANKOVIC, J. Towards optimal sleep scheduling in sensor networks for rare-event detection. In ACM/IEEE IPSN (2004).
4. CHEN, B., JAMIESON, K., BALAKRISHNAN, H., AND MORRIS, R. Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks. In ACM MobiCom (2001).
5. CHOUDHURY, R. R., AND VAIDYA, N. H. MAC-layer anycasting in ad hoc networks. ACM SIGCOMM CCR 34, 75--80 (2004).
6. DEMIRBAS, M., AND FERHATOSMANOGLU, H. Peer-to-peer spatial queries in sensor networks. In IEEE P2P (2003).
7. DUTTA, P., GRIMMER, M., ARORA, A., BIBYK, S., AND CULLER, D. Design of a wireless sensor network platform for detecting rare, random, and ephemeral events. In ACM/IEEE IPSN (2005).
8. FAN HSIN, C., AND LIU, M. Network coverage using low duty-cycled sensors: random & coordinated sleep algorithms. In ACM/IEEE IPSN (2004).
9. GAREY, M. R., AND JOHNSON, D. S. Computers and Intractability - A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, 1979.
10. HEKMAT, R., AND MIEGHEM, P. V. Degree distribution and hopcount in wireless ad-hoc networks. In IEEE ICON (2003).
11. KARP, B., AND KUNG, H. T. GPSR: Greedy perimeter stateless routing for wireless networks. In ACM MobiCom (2000).
12. KIM, Y.-J., GOVINDAN, R., KARP, B., AND SHENKER, S. Geographic routing made practical. In Usenix NSDI (2005).
13. KIM, Y.-J., GOVINDAN, R., KARP, B., AND SHENKER, S. Lazy cross-link removal for geographic routing. In ACM SenSys (2006).
14. LEONG, B., LISKOV, B., AND MORRIS, R. Geographic routing without planarization. In Usenix NSDI (2006).
15. LI, X., KIM, Y. J., GOVINDAN, R., AND HONG, W. Multi-dimensional range queries in sensor networks. In ACM SenSys (2003).
16. LI, X.-Y., WAN, P.-J., WANG, Y., AND YI, C.-W. Fault tolerant deployment and topology control in wireless networks. In ACM MobiHoc (2003).
17. MITZENMACHER, M., AND UPFAL, E. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
18. NATH, S., AND GIBBONS, P. B. Communicating via fireflies: Geographic routing on duty-cycled sensors. Tech. Rep. MSR-TR-2007-21, Microsoft Research, 2007.
19. PENROSE, M. D. On k-connectivity for a geometric random graph. Wiley Random Structures and Algorithms 15, 2 (1999), 145--164.
20. SHENKER, S., RATNASAMY, S., KARP, B., GOVINDAN, R., AND ESTRIN, D. Data-centric storage in sensornets. In ACM HotNets (2002).
21. STOJMENOVIC, I., SEDDIGH, M., AND ZUNIC, J. Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks. IEEE Trans. on Parallel and Distributed Systems 13, 1 (2002), 14--25.
22. SUN, F., AND SHAYMAN, M. On the average pairwise connectivity of wireless multihop networks. In IEEE Globecom (2005).
23. TAKAGI, H., AND KLEINROCK, L. Optimal transmission ranges for randomly distributed packet radio networks. IEEE Trans. on Communication 32, 3 (1984), 246--257.
24. TIAN, D., AND GEORGANAS, N. D. A coverage-preserving node scheduling scheme for large wireless sensor networks. In ACM WSNA (2002).
25. TOUSSAINT, G. T. The relative neighbourhood graph of a finite planar set. Pattern Recognition 12 (1980), 261--268.
26. WANG, X., XING, G., ZHANG, Y., LU, C., PLESS, R., AND GILL, C. Integrated coverage and connectivity configuration in wireless sensor networks. In ACM SenSys (2003).
27. XU, Y., HEIDEMANN, J., AND ESTRIN, D. Geography-informed energy conservation for ad hoc routing. In ACM MobiCom (2001).
28. ZHAO, J., AND GOVINDAN, R. Understanding packet delivery performance in dense wireless sensor networks. In ACM SenSys (2003).
29. ZORZI, M., AND RAO, R. R. Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Energy and latency performance. IEEE Trans. on Mobile Computing 2, 4 (2003), 349--365.

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

  • Real-time systems

• Networks

  • Network types

    • Mobile networks

    • Wireless access networks

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Process management

          • Scheduling