Latency and connectivity analysis tools for wireless mesh networks

ABSTRACT

There has been a recent rise in interest in building networked control systems over a wireless network, whether they be for robot navigation, multi-robot systems, or traditional industrial automation. The wireless networks in these systems must deliver packets between the controller and the actuators/sensors reliably and with low latency. Furthermore, they should be amenable to modeling and characterization so they can be designed as part of a complete control system. Mesh networks are particularly suited for control applications because they provide greater reliability through path diversity.

This paper introduces tools for characterizing the end-to-end connectivity of two points in a wireless mesh network as a function of latency. In particular, we use tools derived from Markov chain models to compare end-to-end connectivity in two routing protocols running on the Data Link/MAC layer provided by Dust Network's Time Synchronized Mesh Protocol (TSMP): Directed Staged Flooding (DSF) and Dust Network's Unicast Path Diversity (UPD). These models also allow us to calculate the traffic load, the sensitivity of end-to-end connectivity to link estimation error, and the robustness of the network to node failure. The paper gives an example of how these tools can be used to evaluate the feasibility of running control applications over sensor networks.

REFERENCES

• 1: D. Culler, D. Estrin, and M. Srivastava, "Overview of sensor networks," in IEEE Computer, Special Issue in Sensor Networks, August 2004.
• 2: Industrial Standards and Automation Committee, "ISA-SP100 wireless systems for automation," http://www.isa.org, 2007.
• 3: Part 15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (LR-WPANs), LAN/MAN Standards Committee of the IEEE Computer Society, 3 Park Avenue, New York, NY 10016--5997, USA, October 2003, 802.15.4 Standard.
• 4: L. Schenato, "Optimal estimation in networked control systems subject to random delay and packet loss," in Proc. of the 45th IEEE Conference on Decision and Control, December 2006.
• 5: B. Sinopoli, L. Schenato, M. Franceschetti, K. Poolla, M. Jordan, and S. Sastry, "Kalman filtering with intermittent observations," IEEE Transactions on Automatic Control, September 2004.
• 6: J. P. Hespanha, P. Naghshtabrizi, and Y. Xu, "A survey of recent results in networked control systems," Proceedings of the IEEE, vol. 95, pp. 138--162, 2007.
• 7: C. Karlof, Y. Li, and J. Polastre, "ARRIVE: Algorithm for robust routing in volatile environments," University of California at Berkeley, Tech. Rep. UCB/CSD-03-1233, May 2002.
• 8: S. Dulman, T. Nieberg, J. Wu, and P. Havinga, "Trade-off between traffic overhead and reliability in multipath routing for wireless sensor networks," in Proceedings of the Wireless Communications and Networking Conference, 2003.
• 9: D. Ganesan, R. Govindan, S. Shenker, and D. Estrin, "Highly-resilient, energy-efficient multipath routing in wireless sensor networks," SIGMOBILE Mob. Comput. Commun. Rev., vol. 5, no. 4, pp. 11--25, 2001.
• 10: Dust Networks, Inc., "Technical overview of time synchronized mesh protocol (TSMP)," http://www.dustnetworks.com/docs/TSMP_Whitepaper.pdf, 2006.
• 11: A. Nasipuri, R. Castañeda, and S. R. Das, "Performance of multipath routing for on-demand protocols in mobile ad hoc networks," Mob. Netw. Appl., vol. 6, no. 4, pp. 339--349, 2001.
• 12: Y. Ganjali and A. Keshavarzian, "Load balancing in ad hoc networks: Single-path routing vs. multi-path routing," in INFOCOM, 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 2, 2004, pp. 1120--1125.
• 13: P. Chen and S. S. Sastry, "Latency and connectivity analysis tools for wireless mesh networks," EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2007-87, Jun 2007. [Online]. Available: http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-87.html
• 14: Dust Networks, Inc., SmartMesh-XT M2030 Product Specification, http://www.dustnetworks.com/docs/M2030.pdf, 2006, datasheet.
• 15: D. P. Bertsekas and J. N. Tsitsiklis, Introduction to Probability. Belmont, Massachusetts: Athena Scientific, 2002.
• 16: R. A. Horn and C. R. Johnson, Matrix Analysis. New York: Cambridge University Press, 1999.