›› 2011, Vol. 26 ›› Issue (6): 962-970.doi: 10.1007/s11390-011-1193-9

Special Issue: Computer Networks and Distributed Computing

• Computer Network and Internet • Previous Articles     Next Articles

Minimum-Time Aggregation Scheduling in Duty-Cycled Wireless Sensor Networks

Bo Yu (于博) and Jian-Zhong Li (李建中), Member, CCF   

  1. School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China
  • Received:2010-06-25 Revised:2011-09-13 Online:2011-11-05 Published:2011-11-05
  • About author:Bo Yu received his B.S. and M.S. degrees in computer science and tech-nology from Harbin Institute of Tech-nology, China, in 2006 and 2008, re-spectively. He is currently a Ph.D. candidate in the School of Computer Science and Technology, Harbin In-stitute of Technology. His research interests include wireless sensor net-works, distributed algorithms.
    Jian-Zhong Li is a professor in the School of Computer Science and Technology at the Harbin Institute of Technology, China. In the past, he worked as a visiting scholar at the University of California at Berke-ley, USA, as a staff scientist in the Information Research Group at the Lawrence Berkeley National Labora-tory, USA, and as a visiting profes-sor at the University of Minnesota, USA. His research in-terests include data management systems, sensor networks and data intensive computing. He has published more than 150 papers in refereed journals and conferences, and has been involved in the program committees of major com-puter science and technology conferences, including SIG-MOD, VLDB, ICDE, INFOCOM, ICDCS, and WWW. He is a member of CCF.
  • Supported by:

    This work is supported by the Key Project of National Natural Science Foundation of China under Grant No. 61033015, the National Natural Science Foundation of China/Research Grants Council of Hong Kong Joint Research Scheme under Grant No. 60831160525, and the National Natural Science Foundation of China under Grant No. 60933001.

Aggregation is an important and commonplace operation in wireless sensor networks. Due to wireless interfe- rences, aggregation in wireless sensor networks often suffers from packet collisions. In order to solve the collision problem, aggregation scheduling is extensively researched in recent years. In many sensor network applications such as real-time monitoring, aggregation time is the most concerned performance. This paper considers the minimum-time aggregation scheduling problem in duty-cycled wireless sensor networks for the first time. We show that this problem is NP-hard and present an approximation algorithm based on connected dominating set. The theoretical analysis shows that the proposed algorithm is a nearly-constant approximation. Simulation shows that the scheduling algorithm has a good performance.

[1] Mainwaring A, Culler D, Polastre J, Szewczyk R, Ander-son J. Wireless sensor networks for habitat monitoring. InProc. the 1st ACM International Workshop on Wireless Sen-sor Networks and Applications (WSNA 2002), Atlanta, USA,Sept. 28, 2002, pp.88-97.

[2] Szewczyk R, Osterweil E, Polastre J, Hamilton M, Mainwar-ing A, Estrin D. Habitat monitoring with sensor networks.Communications of the ACM { Wireless Sensor Networks,2004, 47(6): 34-40.

[3] Szewczyk R, Mainwaring A, Polastre J, Anderson J, Culler D.An analysis of a large scale habitat monitoring application. InProc. the 2nd ACM Conference on Embedded Networked Sen-sor Systems (Sensys 2004), Baltimore, USA, Nov. 3-5, 2004,pp.214-226.

[4] Shrivastava N, Mudumbai R, Madhow U, Suri S. Target track-ing with binary proximity sensors. ACM Transactions onSensor Networks, 2009, 5(4): 251-264.

[5] Jeong J, Hwang T, He T, Du D. MCTA: Target tracking algo-rithm based on minimal contour in wireless sensor networks.In Proc. the 26th Annual IEEE Conference on ComputerCommunications (INFOCOM 2007), Anchorage, USA, May6-12, 2007, pp.2371-2375.

[6] Madden S, Franklin M J, Hellerstein J M, Hong W. TAG: Atiny aggregation service for ad-hoc sensor networks. In Proc.the 5th Symp. Operating Systems Design and Implementa-tion (OSDI 2002), Boston, USA, Dec. 9-11, 2002, pp.131-146.

[7] Shrivastava N, Buragohain C, Agrawal D, Suri S. Medians andbeyond: New aggregation techniques for sensor networks. InProc. the 2nd ACM Conference on Embedded Networked Sen-sor Systems (Sensys 2004), Baltimore, USA, Nov. 3-5, 2004,pp.239-249.

[8] Chu D, Deshpande A, Hellerstein J, Hong W. Approximatedata collection in sensor networks using probabilistic models.In Proc. the 22nd International Conference on Data Engi-neering (ICDE 2006), Atlanta, USA, Apr. 3-8, 2006, p.48.

[9] Huang S C H, Wan P J, Vu C T, Li Y, Yao F. Nearly constantapproximation for data aggregation scheduling in wireless sen-sor networks. In Proc. the 26th Annual IEEE Conference onComputer Communications (INFOCOM 2007), Anchorage,USA, May 6-12, 2007, pp.366-372.

[10] Wan P J, Huang S C H, Wang L, Wan Z, Jia X. Minimum-latency aggregation scheduling in multihop wireless networks.In Proc. the 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2009), NewOrleans, USA, May 18-21, 2009, pp.185-193.

[11] Gandham S, Zhang Y, Huang Q. Distributed minimal timeconvergecast scheduling in wireless sensor networks. In Proc.the 26th International Conference on Distributed ComputingSystems (ICDCS 2006), Lisboa, Portugal, Jul. 4-7, 2006, p.50.

[12] Lu G, Sadagopan N, Krishnamachari B, Goel A. Delay ef-ficient sleep scheduling in wireless sensor networks. In Proc.the 24th Annual Joint Conference of the IEEE Computer andCommunications Societies (INFOCOM 2005), Miami, USA,Mar. 13-17, 2005, pp.2470-2481.

[13] Beutel J, Gruber S, Hasler A et al. PermaDAQ: A scientificinstrument for precision sensing and data recovery in environ-mental extremes. In Proc. the 8th ACM/IEEE Int. Conf. In-formation Processing in Sensor Networks (IPSN 2009), SanFrancisco, USA, Apr. 13-16, 2009, pp.265-276.

[14] Burri N, von Rickenbach P, Wattenhofer R. Dozer: Ultra-lowpower data gathering in sensor networks. In Proc. the 6thACM/IEEE International Conference on Information Pro-cessing in Sensor Networks (IPSN 2007), Cambridge, USA,Apr. 25-27, 2007, pp.450-459.

[15] Gu Y, He T. Data forwarding in extremely low duty-cycle sen-sor networks with unreliable communication links. In Proc.the 5th ACM Conference on Embedded Networked SensorSystems (Sensys 2007), Sydney, Australia, Nov. 6-9, 2007,pp.321-334.

[16] Guo S, Gu Y, Jiang B, He T. Opportunistic flooding in low-duty-cycle wireless sensor networks with unreliable links. InProc. the 15th Annual International Conference on Mo-bile Computing and Networking (MOBICOM 2009), Beijing,China, Sept. 20-25, 2009, pp.133-144.

[17] Wang F, Liu J. Duty-cycle-aware broadcast in wireless sen-sor networks. In Proc. the 28th Annual IEEE Conferenceon Computer Communications (INFOCOM 2009), Rio deJaneiro, Brazil, Apr. 19-25, 2009, pp.468-476.

[18] Deshpande A, Guestrin C, Madden S, Hellerstein J, HongW. Model-driven data acquisition in sensor networks. InProc. the 30th International Conference on Very Large DataBases (VLDB 2004), Toronto, Canada, Aug. 31-Sept. 3, 2004,pp.588-599.

[19] Considine J, Li F, Kollios G, Byers J. Approximate aggrega-tion techniques for sensor databases. In Proc. the 20th In-ternational Conference on Data Engineering (ICDE 2004),Boston, USA, Mar. 30-Apr. 2, 2004, pp.449-460.

[20] Sharaf M A, Beaver J, Labrinidis A, Chrysanthis P K. TiNA:A scheme for temporal coherency-aware in-network aggrega-tion. In Proc. the 3rd ACM International Workshop on DataEngineering for Wireless and Mobile Access (MobiDE 2003),San Diego, USA, Sept. 19, 2003, pp.69-76.

[21] Manjhi A, Nath S, Gibbons P B. Tributaries and deltas:Efficient and robust aggregation in sensor network streams.In Proc. the 24th ACM SIGMOD International Conferenceon Management of Data (SIGMOD 2005), Baltimore, USA,Jun. 14-16, 2005, pp.287-298.

[22] Nath S, Gibbons P B, Seshan S, Anderson Z R. Synopsis dif-fusion for robust aggregation in sensor networks. In Proc. the2nd ACM Conference on Embedded Networked Sensor Sys-tems (Sensys 2004), Baltimore, USA, Nov. 3-5, 2004, pp.250-262.

[23] Chen X, Hu X, Zhu J. Minimum data aggregation time prob-lem in wireless sensor networks. In Proc. the 1st Interna-tional Conference on Mobile Ad hoc and Sensor Networks(MSN 2005), Wuhan, China, Dec. 13-15, 2005, pp.133-142.

[24] Yu B, Li J, Li Y. Distributed data aggregation schedul-ing in wireless sensor networks. In Proc. the 28thAnnual IEEE Conference on Computer Communications(INFOCOM 2009), Rio de Janeiro, Brazil, Apr. 19-25, 2009,pp.2159-2167.

[25] Li Y, Guo L, Prasad S K. An energy-efficient distributed algo-rithm for minimum-latency aggregation scheduling in wirelesssensor networks. In Proc. the 30th International Conferenceon Distributed Computing Systems (ICDCS 2010), Genoa,Italy, Jun. 21-25, 2010, pp.827-836.

[26] Buettner M, Yee G V, Anderson E, Han R. X-MAC: A shortpreamble MAC protocol for duty-cycled wireless sensor net-works. In Proc. the 4th ACM Conference on EmbeddedNetworked Sensor Systems (Sensys 2006), Boulder, USA,Oct. 31-Nov. 3, 2006, pp.307-320.

[27] Sun Y, Gurewitz O, Du S, Tang L, Johnson D B. ADB: Anefficient multihop broadcast protocol based on asynchronousduty-cycling in wireless sensor networks. In Proc. the 7thACM Conference on Embedded Networked Sensor Systems(Sensys 2009), Berkeley, USA, Nov. 4-6, 2009, pp.43-56.

[28] Lai S, Ravindran B. On multihop broadcast over adaptivelyduty-cycled wireless sensor networks. In Proc. the 6th IEEEInternational Conference on Distributed Computing in Sen-sor Systems (DCOSS 2010), Santa Barbara, USA, Jun. 21-23,2010, pp.158-171.

[29] Jiao X, Lou W, Ma J, Cao J, Wang X, Zhou X. Duty-cycle-aware minimum latency broadcast scheduling in multi-hopwireless networks. In Proc. the 30th International Conferenceon Distributed Computing Systems (ICDCS 2010), Genoa,Italy, Jun. 21-25, 2010, pp.754-763.

[30] Clark B N, Colbourn C J, Johnson D S. Unit disk graphs.Discrete Mathematics, 1990, 86(1-3): 165-177.

[31] Garey M R, Johnson D S. Computers and Intractability: AGuide to the Theory of NP-Completeness. New York: W HFreeman & Co., 1979.
No related articles found!
Full text



[1] Jin-Woo Kim, Ju-Hum Kwon, Young-Gab Kim, Chee-Yang Song, Hyun-Seok Kim, and Doo-Kwon Baik. EAFoC: Enterprise Architecture Framework Based on Commonality[J]. , 2006, 21(6): 952 -964 .
[2] Wai-Ho Mak (麦伟豪), Yingcai Wu (巫英才), Ming-Yuen Chan (陈明远), and Huamin Qu (屈华民), Member, IEEE. Visibility-Aware Direct Volume Rendering[J]. , 2011, 26(2): 217 -228 .
[3] Li-Feng He, Yu-Yan Chao, and Kenji Suzuki. An Algorithm for Connected-Component Labeling, Hole Labeling and Euler Number Computing[J]. , 2013, 28(3): 468 -478 .
[4] Jinho Kim, Sang-Wook Kim, Sanghyun Park, Haixun Wang. Preface[J]. , 2013, 28(4): 583 -584 .
[5] Jeff Huang, Charles Zhang. Debugging Concurrent Software: Advances and Challenges[J]. , 2016, 31(5): 861 -868 .
[6] Hong-Cheng Huang, Jie Zhang, Zu-Fan Zhang, Zhong-Yang Xiong. Interference-Limited Device-to-Device Multi-User Cooperation Scheme for Optimization of Edge Networking[J]. , 2016, 31(6): 1096 -1109 .
[7] Shi-Min Hu, Niloy J. Mitra, Yizhou Yu. Preface[J]. , 2017, 32(3): 415 -416 .
[8] Xu-Zhou Zhang, Yun-Zhan Gong, Ya-Wen Wang, Ying Xing, Ming-Zhe Zhang. Automated String Constraints Solving for Programs Containing String Manipulation Functions[J]. , 2017, 32(6): 1125 -1135 .
[9] Zhao-Yang Wang, Bei-Hong Jin, Tingjian Ge, Tao-Feng Xue. Detecting Anomalous Bus-Driving Behaviors from Trajectories[J]. Journal of Computer Science and Technology, 2020, 35(5): 1047 -1063 .
[10] Hao-Ren Wang, Juan Lei, Ao Li, Yi-Hong Wu. A Geometry-Based Point Cloud Reduction Method for Mobile Augmented Reality System[J]. Journal of Computer Science and Technology, 2018, 33(6): 1164 -1177 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved