Scalable medium access control for in-network data aggregation

ABSTRACT

We present conflict-free and contention-based medium access control (MAC) protocols designed for resource-aware data collection in sensor networks. We are interested in the performance of these schemes when used in in-network data aggregation systems. We introduce a Listen-and-Suppress (LAS) MAC protocol paradigm which can conserve network and node resources and cut delays through the interaction between the constituent nodes. In LAS-TDMA and LAS-CSMA, nodes listen to the channel and suppress their transmissions and sleep if their data is not needed. Under these conditions, we compare conflict-free scheduling and random scheduling in a general setting along several performance metrics. We find that, for conflict-free scheduling, collecting the aggregate minimum or maximum of a data value in records residing on n nodes in the network requires, on average, O(lg n) record transmissions and O(n lg n) listens collectively. Without our scheme, n transmissions and n² collective listens are required. We simulate in the random scheduling domain, and examine how delay can be reduced by increasing the offered load on the channel at the cost of greater power dissipation due to collisions. For networks of 20 nodes, LAS-CSMA reduces the average delay by 58% in comparison to CSMA, and for networks of 100 nodes, it reduces the average delay by 80%.

REFERENCES

• 1: Muneeb Ali , Umar Saif , Adam Dunkels , Thiemo Voigt , Kay Römer , Koen Langendoen , Joseph Polastre , Zartash Afzal Uzmi, Medium access control issues in sensor networks, ACM SIGCOMM Computer Communication Review, v.36 n.2, April 2006 [doi>10.1145/1129582.1129592]
• 2: J. Burke, D. Estrin, M. Hansen, A. Parker, N. Ramanathan, S. Reddy, and M. Srivastava. Participatory sensing. ACM Sensys World Sensor Web Workshop, 2006.
• 3: I. Demirkol, C. Ersoy, and F. Alagoz. MAC protocols for wireless sensor networks: A survey. IEEE Communications Magazine, 44(4):115--121, Apr. 2006.
• 4: E. Fasolo, M. Rossi, J. Widmer, and M. Zorzi. In-network aggregation techniques for wireless sensor networks: a survey. Wireless Communications, IEEE {see also IEEE Personal Communications}, 14(2):70--87, April 2007.
• 5: Jie Gao , Leonidas Guibas , Nikola Milosavljevic , John Hershberger, Sparse data aggregation in sensor networks, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA [doi>10.1145/1236360.1236414]
• 6: Chalermek Intanagonwiwat , Deborah Estrin , Ramesh Govindan , John Heidemann, Impact of Network Density on Data Aggregation in Wireless Sensor Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.457, July 02-05, 2002
• 7: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 8: Roozbeh Jafari , Andre Encarnacao , Azad Zahoory , Foad Dabiri , Hyduke Noshadi , Majid Sarrafzadeh, Wireless Sensor Networks for Health Monitoring, Proceedings of the The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, p.479-781, July 17-21, 2005 [doi>10.1109/MOBIQUITOUS.2005.65]
• 9: Kurtis Kredo, II , Prasant Mohapatra, Medium access control in wireless sensor networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.4, p.961-994, March, 2007 [doi>10.1016/j.comnet.2006.06.012]
• 10: Sandeep S. Kulkarni , Mahesh (Umamaheswaran) Arumugam, TDMA Service for Sensor Networks, Proceedings of the 24th International Conference on Distributed Computing Systems Workshops - W7: EC (ICDCSW'04), p.604-609, March 23-24, 2004
• 11: K. Langendoen. Medium access control in wireless sensor networks. In H. Wu and Y. Pan, editors, Medium Access Control in Wireless Networks, Volume II: Practice and Standards. Nova Science Publishers, Inc., 2007.
• 12: G. Lu, B. Krishnamachari, and C. S. Raghavendra. An adaptive energy-efficient and low-latency MAC for data gathering in wireless sensor networks. IPDPS, 13:224a, 2004.
• 13: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for ad-hoc sensor networks, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844142]
• 14: Piyush Naik , Krishna M. Sivalingam, A survey of MAC protocols for sensor networks, Wireless sensor networks, Kluwer Academic Publishers, Norwell, MA, 2004
• 15: M. Neufeld, J. Fifield, C. Doerr, A. Sheth, and D. Grunwald. Softmac - flexible wireless research platform. In Fourth Workshop on Hot Topics in Networks (HotNets-IV), November 2005.
• 16: R. Pon, M. A. Batalin, V. Chen, A. Kansal, D. Liu, M. H. Rahimi, L. Shirachi, A. Somasundra, Y. Yu, M. M. Hansen, W. J. Kaiser, M. B. Srivastava, G. S. Sukhatme, and D. Estrin. Coordinated static and mobile sensing for environmental monitoring. In V. K. Prasanna, S. S. Iyengar, P. G. Spirakis, and M. Welsh, editors, DCOSS, volume 3560 of Lecture Notes in Computer Science, pages 403--405. Springer, 2005.
• 17: Raphael Rom , Moshe Sidi, Multiple access protocols: performance and analysis, Springer-Verlag New York, Inc., New York, NY, 1990
• 18: Robert Szewczyk , Alan Mainwaring , Joseph Polastre , John Anderson , David Culler, An analysis of a large scale habitat monitoring application, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031521]
• 19: N. A. Vasanthi , S. Annadurai, Energy Efficient Sleep Schedule for Achieving Minimum Latency in Query based Sensor Networks, Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing - Vol 2 - Workshops, p.214-219, June 05-07, 2006 [doi>10.1109/SUTC.2006.64]
• 20: Yong Yao , Johannes Gehrke, The cougar approach to in-network query processing in sensor networks, ACM SIGMOD Record, v.31 n.3, September 2002 [doi>10.1145/601858.601861]
• 21: Wei Ye , John Heidemann, Medium access control in wireless sensor networks, Wireless sensor networks, Kluwer Academic Publishers, Norwell, MA, 2004
• 22: Wei Ye , John Heidemann , Deborah Estrin, Medium access control with coordinated adaptive sleeping for wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.12 n.3, p.493-506, June 2004 [doi>10.1109/TNET.2004.828953]
• 23: R. G. Yonggang Jerry Zhao and D. Estrin. Computing aggregates for monitoring wireless sensor networks. In The First IEEE International Workshop on Sensor Network Protocols and Applications (SNPA 03), Anchorage, AK, USA, May 11 2003.
• 24: Vladimir I. Zadorozhny , Panos K. Chrysanthis , Prashant Krishnamurthy, A framework for extending the synergy between MAC layer and query optimization in sensor networks, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada [doi>10.1145/1052199.1052211]
• 25: J. Zhao, R. Govindan, and D. Estrin. Computing aggregates for monitoring wireless sensor networks, 2003.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Design, Performance, Theory

Keywords:
in-network data aggregation, medium access control, wireless sensor networks