A distributed coordination framework for wireless sensor and actor networks

ABSTRACT

Wireless Sensor and Actor Networks (WSANs) are composed of a large number of heterogeneous nodes called sensors and actors. The collaborative operation of sensors enables the distributed sensing of a physical phenomenon, while the role of actors is to collect and process sensor data and perform appropriate actions.In this paper, a coordination framework for WSANs is addressed. A new sensor-actor coordination model is proposed, based on an event-driven clustering paradigm in which cluster formation is triggered by an event so that clusters are created on-the-fly to optimally react to the event itself and provide the required reliability with minimum energy expenditure. The optimal solution is determined by mathematical programming and a distributed solution is also proposed. In addition, a new model for actor-actor coordination is introduced for a class of coordination problems in which the area to be acted upon is optimally split among different actors. An auction-based distributed solution of the problem is also presented.Performance evaluation shows how global network objectives, such as compliance with real-time constraints and minimum energy consumption, can be reached in the proposed framework with simple interactions between sensors and actors that are suitable for large-scale networks of energy-constrained devices.

REFERENCES

• 1: I. F. Akyildiz and I. H. Kasimoglu, "Wireless sensor and actor networks: Research challenges," Ad Hoc Networks (Elsevier), vol. 2, no. 4, pp. 351--367, October 2004.
• 2: Tian He , John A. Stankovic , Chenyang Lu , Tarek Abdelzaher, SPEED: A Stateless Protocol for Real-Time Communication in Sensor Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.46, May 19-22, 2003
• 3: Chenyang Lu , Brian M. Blum , Tarek F. Abdelzaher , John A. Stankovic , Tian He, RAP: A Real-Time Communication Architecture for Large-Scale Wireless Sensor Networks, Proceedings of the Eighth IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'02), p.55, September 25-27, 2002
• 4: E. Felemban, C.-G. Lee, E. Ekici, R. Boder, and S. Vural, "Probabilistic QoS Guarantee in Reliability and Timeliness Domains in Wireless Sensor Networks," in Proceedings of IEEE INFOCOM 2005, Miami, FL, USA, Mar. 2005.
• 5: J. A. Stankovic, T. F. Abdelzaher, C. Lu, L. Sha, and J. Hou, "Real-time communication and coordination in embedded sensor networks," Proceedings of the IEEE, vol. 91, no. 7, pp. 1002--1022, 2003.
• 6: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 7: Y. Yu, B. Krishnamachari, and V. K. Prasanna, "Energy-latency tradeoffs for data gathering in wireless sensor networks," in Proceedings of IEEE INFOCOM 2004, Hong Kong S.A.R., P.R. China, 2004.
• 8: Jinyang Li , John Jannotti , Douglas S. J. De Couto , David R. Karger , Robert Morris, A scalable location service for geographic ad hoc routing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.120-130, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345931]
• 9: R. Jain, A. Puri, and R. Sengupta, "Geographical routing using partial information for wireless ad hoc networks," IEEE Personal Communications, pp. 48--57, February 2001.
• 10: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 11: Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, Worst-Case optimal and average-case efficient geometric ad-hoc routing, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778447]
• 12: W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, "An application-specific protocol architecture for wireless microsensor networks," IEEE Transactions on Wireless Communications, vol. 1, no. 4, pp. 660--670, Oct. 2002.
• 13: O. Younis and S. Fahmy, "Distributed clustering in ad-hoc sensor networks: A hybrid, energy-efficient approach," in Proceedings of IEEE INFOCOM 2004, Hong Kong S.A.R., P.R. China, March 2004.
• 14: Vivek P. Mhatre , Catherine Rosenberg , Daniel Kofman , Ravi Mazumdar , Ness Shroff, A Minimum Cost Heterogeneous Sensor Network with a Lifetime Constraint, IEEE Transactions on Mobile Computing, v.4 n.1, p.4-15, January 2005 [doi>10.1109/TMC.2005.2]
• 15: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, Initializing newly deployed ad hoc and sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023746]
• 16: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 17: Joseph Czyzyk , Michael P. Mesnier , Jorge J. Moré, The NEOS Server, IEEE Computational Science & Engineering, v.5 n.3, p.68-75, July 1998 [doi>10.1109/99.714603]
• 18: Bhaskar Krishnamachari , Deborah Estrin , Stephen B. Wicker, The Impact of Data Aggregation in Wireless Sensor Networks, Proceedings of the 22nd International Conference on Distributed Computing Systems, p.575-578, July 02-05, 2002
• 19: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 20: M. R. Garey and D. S. Johnson, Computer and Intractability. New York, NY: W. H. Freeman and Co., 1979.
• 21: T. Melodia, D. Pompili, and I. F. Akyildiz, "On the Interdependence of Distributed Topology Control and Geographical Routing in Ad Hoc and Sensor Networks," IEEE Journal of Selected Areas in Communications, vol. 23, no. 3, pp. 520--532, March 2005.
• 22: B. Sundararaman, U. Buy, and A. Kshemkalyani, "Clock synchronization for wireless sensor networks: a survey," Ad Hoc Networks (Elsevier), vol. 3, no. 3, pp. 281--323, May 2005.
• 23: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Wireless Networks, v.7 n.6, p.609-616, November 2001 [doi>10.1023/A:1012319418150]
• 24: G. Finn, "Routing and addressing problems in large metropolitan-scale internetworks," ISI res. rep ISU/RR- 87-180, Tech. Rep., March 1987.
• 25: R. P. McAfee and J. McMillan, "Auctions and bidding," Journal of Economic Literature, vol. 25, no. 2, pp. 699--738, June 1987.
• 26: B. P. Gerkey and M. J. Mataric, "Sold!: Auction methods for multirobot coordination," IEEE Transactions on Robotics and Automation, vol. 18, no. 5, pp. 758--768, October 2002.
• 27: P. Maillé and B. Tuffin, "Multi-bid auctions for bandwidth allocation in communication networks," in Proceedings of IEEE INFOCOM 2004, Hong Kong S.A.R., P.R. China, March 2004.
• 28: R. Fourer, D. M. Gay, and B. W. Kernighan, AMPL: A Modeling Language for Mathematical Programming. Duxbury Press / Brooks/Cole Publishing Company, 2002.
• 29: CPLEX solver. {Online}. Available: http://www.cplex.com
• 30: The J-Sim Simulator. {Online}. Available: http://www.j-sim.org/

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
energy efficiency, real-time communications, wireless sensor and actor networks