skip to main content
article

Optimal stochastic policies for distributed data aggregation in wireless sensor networks

Published: 01 October 2009 Publication History

Abstract

The scenario of distributed data aggregation in wireless sensor networks is considered, where sensors can obtain and estimate the information of the whole sensing field through local data exchange and aggregation. An intrinsic tradeoff between energy and aggregation delay is identified, where nodes must decide optimal instants for forwarding samples. The samples could be from a node's own sensor readings or an aggregation with samples forwarded from neighboring nodes. By considering the randomness of the sample arrival instants and the uncertainty of the availability of the multiaccess communication channel, a sequential decision process model is proposed to analyze this problem and determine optimal decision policies with local information. It is shown that, once the statistics of the sample arrival and the availability of the channel satisfy certain conditions, there exist optimal control-limit-type policies that are easy to implement in practice. In the case that the required conditions are not satisfied, the performance loss of using the proposed control-limit-type policies is characterized. In general cases, a finite-state approximation is proposed and two on-line algorithms are provided to solve it. Practical distributed data aggregation simulations demonstrate the effectiveness of the developed policies, which also achieve a desired energy-delay tradeoff.

References

[1]
A. Boulis, S. Ganeriwal, and M. B. Srivastava, "Aggregation in sensor networks: An energy-accuracy trade-off," Ad Hoc Netw., vol. 1, no. 2-3, pp. 317-331, 2003.
[2]
L. Xiao, S. Boyd, and S. Lall, "A space-time diffusion scheme for peer-to-peer least-squares estimation," in Proc. IEEE Int. Conf. Info. Process. Sensor Netw., Nashville, TN, Apr. 2006, pp. 168-176.
[3]
J.-Y. Chen, G. Pandurangan, and D. Xu, "Robust computation of aggregates in wireless sensor networks: Distributed randomized algorithms and analysis," in Proc. IEEE Int. Conf. Info. Process. Sensor Netw., Los Angeles, CA, Apr. 2005, pp. 348-355.
[4]
V. Delouille, R. Neelamani, and R. Baraniuk, "Robust distributed estimation in sensor networks using embedded polygons algorithm," in Proc. IEEE Int. Conf. Info. Process. Sensor Netw., Berkeley, CA, Apr. 2004, pp. 405-413.
[5]
R. Cristescu and M. Vetterli, "On the optimal density for real-time data gathering of spatio-temporal processes in sensor networks," in Proc. IEEE Int. Conf. Info. Process. Sensor Netw., Los Angeles, CA, Apr. 2005, pp. 159-164.
[6]
W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, "Energy-efficient communication protocol for wireless microsensor networks," in Proc. Hawaii Int. Conf. Syst. Sci., Manoa, HI, Jan. 2000, pp. 1-10.
[7]
I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "Wireless sensor networks: A survey," Comput. Netw., vol. 38, no. 4, pp. 393-422, 2002.
[8]
Z. Ye, A. A. Abouzeid, and J. Ai, "Optimal policies for distributed data aggregation in wireless sensor networks," ECSE Dept., RPI, Troy, NY, 2008.
[9]
"Crossbow, MPR/MIB User's Manual Rev. A, Doc. 7430-0021-08," Crossbow Technology, Inc., 2007.
[10]
T. He, B. M. Blum, J. A. Stankovic, and T. F. Abdelzaher, "AIDA: Adaptive application-independent data aggregation in wireless sensor networks," Trans. Embed. Comput. Syst., vol. 3, no. 2, pp. 426-457, May 2004.
[11]
C. Intanagonwiwat, R. Govindan, and D. Estrin, "Directed diffusion: A scalable and robust communication paradigm for sensor networks," in Proc. ACM Int. Conf. Mobile Comput. Netw., Boston, MA, Aug. 2000, pp. 56-67.
[12]
S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong, "TAG: A tiny aggregation service for ad-hoc sensor networks," in Proc. Symp. Oper. Syst. Design and Implement., Boston, MA, Dec. 2002, pp. 131-146.
[13]
W. R. Heinzelman, J. Kulik, and H. Balakrishnan, "Adaptive protocols for information dissemination in wireless sensor networks," in Proc. ACM Int. Conf. Mobile Comput. Network., Seattle, WA, Aug. 1999, pp. 174-185.
[14]
I. Solis and K. Obraczka, "In-network aggregation trade-offs for data collection in wireless sensor networks," Computer Science Dept., UCSC, Santa Cruz, CA, 2003.
[15]
F. Hu, X. Cao, and C. May, "Optimized scheduling for data aggregation in wireless sensor networks," in Proc. Int. Conf. Inf. Technol.: Coding and Comput., Las Vegas, NV, Apr. 2005, pp. 557-561.
[16]
M. L. Puterman, Markov Decision Processes--Discrete Stochastic Dynamic Programming. New York, NY: Wiley, 1994.
[17]
E. Altman, "Applications of markov decision processes in communication networks," in Handbook of Markov Decision Processes: Methods and Applications. Norwell, MA: Kluwer, pp. 489-536, 2002.
[18]
T. S. Ferguson, "Optimal stopping and applications," 2004 {Online}. Available: http://www.math.ucla.edu/~tom/Stopping/Contents.html
[19]
Y. S. Chow, H. Robbins, and D. Siegmund, Great Expectations: The Theory of Optimal Stopping. Boston, MA: Houghton Mifflin, 1971.
[20]
T. Ferguson, "A poisson fishing model," in Festschrift for Lucien Le Cam--Research Papers in Probability and Statistics. New York: Springer-Verlag, 1997, pp. 235-244.
[21]
N. Starr and M. Woodroofe, "Gone fishin': Optimal stopping based on catch times," Statistics Dept., Univ. Michigan, Ann Arbor, MI, 1974.
[22]
A. Z. Broder and M. Mitzenmacher, "Optimal plans for aggregation," in Proc. ACM Symp. Principles Distrib. Comput., Monterey, CA, 2002, pp. 144-152.
[23]
I. Demirkol, C. Ersoy, and F. Alagoz, "MAC protocols for wireless sensor networks: A survey," IEEE Commun. Magazine, vol. 44, no. 4, pp. 115-121, Apr. 2006.
[24]
S. P. Singh and R. C. Yee, "An upper bound on the loss from approximate optimal-value functions," Mach. Learning, vol. 16, no. 3, pp. 227-233, 1994.
[25]
A. G. Barto, S. J. Bradtke, and S. P. Singh, "Learning to act using real-time dynamic programming," Artif. Intell., vol. 72, no. 1-2, pp. 81-138, Jan. 1995.
[26]
S. J. Bradtke, "Incremental dynamic programming for online adaptive optimal control," Ph. D. dissertation, Univ. Massachusetts, Amherst, MA, 1994.
[27]
J. N. Tsitsiklis, "Asynchronous stochastic approximation and Q-learning," MIT, Cambridge, MA, Tech. Rep. LIDS-P-2172, 1993.
[28]
M. Asadpour and R. Siegwart, "Compact Q-learning optimized for micro-robots with processing and memory constraints," Robot. Auton. Syst., no. 48, pp. 49-61, 2004.
[29]
N. Cressie, Statistics for Spatial Data. New York: Wiley, 1991.
[30]
S. Haykin, Adaptive Filter Theory. London, U.K.: Prentice-Hall, 2001.

Cited By

View all
  • (2016)Efficient and robust serial query processing approach for large-scale wireless sensor networksAd Hoc Networks10.1016/j.adhoc.2016.04.01247:C(82-98)Online publication date: 1-Sep-2016
  • (2015)Performance Evaluation of Data Aggregation Functions using Markov Decision ProcessesProceedings of the 12th ACM Symposium on Performance Evaluation of Wireless Ad Hoc, Sensor, & Ubiquitous Networks10.1145/2810379.2810384(101-108)Online publication date: 2-Nov-2015
  • (2015)Optimal Aggregation Policy for Reducing Tail Latency of Web SearchProceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/2766462.2767708(63-72)Online publication date: 9-Aug-2015
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 17, Issue 5
October 2009
339 pages

Publisher

IEEE Press

Publication History

Published: 01 October 2009
Revised: 27 August 2008
Received: 24 February 2008
Published in TON Volume 17, Issue 5

Author Tags

  1. data aggregation
  2. energy-delay tradeoff
  3. semi-Markov decision processes (SMDPs)
  4. wireless sensor networks

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2016)Efficient and robust serial query processing approach for large-scale wireless sensor networksAd Hoc Networks10.1016/j.adhoc.2016.04.01247:C(82-98)Online publication date: 1-Sep-2016
  • (2015)Performance Evaluation of Data Aggregation Functions using Markov Decision ProcessesProceedings of the 12th ACM Symposium on Performance Evaluation of Wireless Ad Hoc, Sensor, & Ubiquitous Networks10.1145/2810379.2810384(101-108)Online publication date: 2-Nov-2015
  • (2015)Optimal Aggregation Policy for Reducing Tail Latency of Web SearchProceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/2766462.2767708(63-72)Online publication date: 9-Aug-2015
  • (2015)Markov Decision Processes With Applications in Wireless Sensor Networks: A SurveyIEEE Communications Surveys & Tutorials10.1109/COMST.2015.242068617:3(1239-1267)Online publication date: 1-Jul-2015
  • (2014)Advanced Principal Component-Based Compression Schemes for Wireless Sensor NetworksACM Transactions on Sensor Networks10.1145/262933011:1(1-34)Online publication date: 28-Jul-2014
  • (2010)Distributed opportunistic scheduling with two-level probingIEEE/ACM Transactions on Networking10.1109/TNET.2010.204261018:5(1464-1477)Online publication date: 1-Oct-2010

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media