Abstract
Data aggregation is an essential yet time-consuming task in wireless sensor networks. This paper studies the well-known minimum-latency aggregation schedule problem and proposes an energy-efficient distributed scheduling algorithm named Clu-DDAS based on a novel cluster-based aggregation tree. Our approach differs from all the previous schemes where connected dominating sets or maximal independent sets are employed. This paper proves that Clu-DDAS has a latency bound of \(4R'+2 \varDelta -2\), where \(\varDelta \) is the maximum degree and \(R'\) is the inferior network radius which is smaller than the network radius \(R\). Our experiments show that Clu-DDAS has an approximate latency upper bound of \(4R'+1.085 \varDelta -2\) with increased \(\varDelta \). Clu-DDAS has comparable latency as the previously best centralized algorithm, E-PAS, but consumes 78 % less energy as shown by the simulation results. Clu-DDAS outperforms the previously best distributed algorithm, DAS, whose latency bound is \(16R'+\varDelta -14\) on both latency and energy consumption. On average, Clu-DDAS transmits 67 % fewer total messages than DAS. The paper also proposes an adaptive strategy for updating the schedule to accommodate dynamic network topology.
Similar content being viewed by others
References
Bloom BH (1970) Space/time trade-offs in hash coding with allowable errors. Commun ACM 13:422–426
Bo C, Ren D, Tang S, Li XY (2012) Locating sensors in the forest: a case study in GreenOrbs. In: Proc. IEEE international conference on computer communications (INFOCOM), pp 1026–1034
Boukerche A, Cheng X, Linus J (2003) Energy-aware data-centric routing in microsensor networks. in: Proc. ACM international conference on modeling, analysis and simulation of wireless and mobile systems (MSWiM), pp 42–49
Boukerche A, Cheng X, Linus J (2003) Energy-aware data-centric routing in microsensor networks. In: Proceedings of ACM MSWiM, pp 42–49
Chen X, Hu X, Zhu J (2005) Minimum data aggregation time problem in wireless sensor networks. Lect Notes Comput Sci 3794:133–142
Cheng S, Li J, Cai Z (2013) \(O(\epsilon )\)-approximation to physical world by sensor networks. INFOCOM, pp 3084–3092
Choi JY, Lee J, Lee K, Choi S, Kwon WH, Park HS (2006) Aggregation time control algorithm for time constrained data delivery in wireless sensor networks. In: Proc. vehicular technology conference (VTC), pp 563–567
Christer E (2011) Bloom Filter. Junct Press
Ding M, Cheng X, Xue G (2003) Aggregation tree construction in sensor networks. In: Proc. IEEE Vehicular Technology Conference(VTC), pp 2168–2172
Ding M, Cheng X, Xue G (2003) Aggregation tree construction in sensor networks. In: Proc. of IEEE VTC, vol 4, pp 2168–2172
Floyd RW (1962) Algorithm 97: shortest path. Commun ACM 5:345–370
Gupta P, Kumar P (2000) The capacity of wireless networks. IEEE Trans Inf Theory 46:388–404
Huddlestone-Holmes C, Gigan G, Woods G, Ruxton A (2007) Infrastructure for a sensor network on Davies Reef, Great Barrier Reef. In: Proc. intelligent sensors, sensor networks and information (ISSNIP), pp 675–679
Ji S, Cai Z (2013) Distributed data collection in large-scale asynchronous wireless sensor networks under the generalized physical interference model. IEEE/ACM Trans Netw 21:1270–1283
Kesselman A, Kowalski DR (2006) Fast distributed algorithm for convergecast in ad hoc geometric radio networks. J Parallel Distrib Comput 66:578–585
Li J, Cheng S, Gao H, Cai Z (2014) Approximate physical world reconstruction algorithms in sensor networks. IEEE Trans Parallel Distrib Syst 5:1–14
Luo C, Wu F, Sun J, Chen CW (2009) Compressive data gathering for large-scale wireless sensor networks. In: Proc. mobile computing and networking (MobiCom), pp 145–156
Mitzenmacher M (2002) Compressed bloom filters. IEEE/ACM Trans Netw 10:604–612
Murty RN, Mainland G, Rose I, Chowdhury AR (2008) CitySense: an urban scale wireless sensor network and testbed. In: Proc. technologies for homeland security (THS), pp 583–588
SCH, Wan PJ, Vu CT, Li Y, Yao F (2007) Nearly constant approximation for data aggregation scheduling in wireless sensor networks. In: Proc. IEEE international conference on computer communications (INFOCOM), pp 366–372
Wan PJ, Huang SCH, Wang L, Wan Z, Jia X (2009) Minimum-latency aggregation scheduling in multihop wireless networks. In: Proc. mobile ad hoc networking and computing (MobiHoc), pp 185–194
Wan PJ, Alzoubi KM, Frieder O (2004) Distributed construction of connected dominating set in wireless ad hoc networks. Mobile Netw Appl 9:141–149
Wegner G (1986) Uber ber endliche kreispackungen in der ebene. Studia Sci Math Hung 21:1–28
Wilson J, Bhargava V, Redfern A, Wright PK (2007) A wireless sensor network and incident command interface for urban firefighting. In: Proc. mobile and ubiquitous systems, computing, networking and services (MobiQuitous), pp 1–7
Wu Y, Li XY, Liu Y, Lou W (2010) Energy-efficient wake-up scheduling for data collection and aggregation. IEEE Trans Parallel Distrib Syst 11:275–287
Xu XH, Wang SG, Mao XF, Tang SJ, Li XY (2009) An improved approximation algorithm for data aggregation in multi-hop wireless sensor networks. In: Proc. foundations of wireless ad hoc and sensor networking and computing (FOWANC), pp 47–56
Yu B, Li J, Li Y (2009) Distributed data aggregation scheduling in wireless sensor networks. In: Proc. IEEE international conference on computer communications (INFOCOM), pp 2159–2167
Acknowledgments
This research was in part supported by Program for New Century Excellent Talents in University under Grant No. NCET-11-0955, Program Foundation of Heilongjiang Educational Committee for New Century Excellent Talents in University under Grant No. 1252-NCET-011, Program for Group of Science and Technology Innovation of Heilongjiang Educational Committee under Grant No. 2013TD012, the National Science Foundation (NSF) under Grants No. CNS-1152001 and CNS-1252292 and National Natural Science Foundation of China (NSFC) under Grant Nos. 61373083, 61370217, 61033015 and 61173094.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Guo, L., Li, Y. & Cai, Z. Minimum-latency aggregation scheduling in wireless sensor network. J Comb Optim 31, 279–310 (2016). https://doi.org/10.1007/s10878-014-9748-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-014-9748-7