Chapter 23
Routing for Statistical Inference in Sensor Networks
A. Anandkumar,
A. Ephremides,
A. Swami, L. Tong,
A. Anandkumar
Adaptive Communications & Signal Processing, Electrical & Computer Engineering, Cornell University, Ithaca, NY, USA
Search for more papers by this authorA. Ephremides
Department of Electrical & Computer Engineering, University of Maryland, College Park, MD, USA
Search for more papers by this authorA. Anandkumar,
A. Ephremides,
A. Swami, L. Tong,
A. Anandkumar
Adaptive Communications & Signal Processing, Electrical & Computer Engineering, Cornell University, Ithaca, NY, USA
Search for more papers by this authorA. Ephremides
Department of Electrical & Computer Engineering, University of Maryland, College Park, MD, USA
Search for more papers by this authorBook Editor(s):Simon Haykin,
K. J. Ray Liu,
Simon Haykin
Department of Electrical Engineering, McMaster University, Hamilton, Ontario, Canada
Search for more papers by this authorK. J. Ray Liu
Department of Electrical & Computer Engineering, University of Maryland, College Park, MD, USA
Search for more papers by this authorSummary
This chapter contains sections titled:
-
Introduction
-
Spatial Data Correlation
-
Statistical Inference of Markov Random Fields
-
Optimal Routing for Inference with Local Processing
-
Conclusion and Future Work
-
Bibliographic Notes
-
References
REFERENCES
- D. P. Bertsekas and R. Gallager, Data Networks, Englewood Cliffs, NJ: Prentice Hall, 1992.
- R. Koetter and M. Medard, “An algebraic approach to network coding,” IEEE/ACM Trans. Networking, vol. 11, no. 5, pp. 782–795, 2003.
-
H. V. Poor, An Introduction to Signal Detection and Estimation. New York: Springer, 1994.
10.1007/978-1-4757-2341-0 Google Scholar
- Y. Sung, S. Misra, L. Tong, and A. Emphremides, “Cooperative routing for signal detection in large sensor networks,” IEEE J. Sel. Area Commun., vol. 25, no. 2, pp. 471–483, 2007.
- Y. Sung, L. Tong, and H. Poor, “Neyman-Pearson detection of Gauss-Markov signals in noise: Closed-form error exponent and properties,” IEEE Trans. Inform. Theory, vol. 52, no. 4, pp. 1354–1365, Apr. 2006.
- A. Deshpande, C. Guestrin, S. Madden, J. Hellerstein, and W. Hong, “Model-driven data acquisition in sensor networks,” in VLDB, 2004.
- R. Cristescu and M. Vetterli, “On the optimal density for real-time data gathering of spatio-temporal processes in sensor networks,” in IPSN, 2005, pp. 159–164.
- D. Marco, E. Duarte-Melo, M. Liu, and D. Neuhoff, “On the many-to-one transport capacity of a dense wireless sensor network and the compressibility of its data,” in Proc. IPSN, 2003, pp. 1–16.
- S. Yoon and C. Shahabi, “The clustered aggregation technique leveraging spatial and temporal correlations in wireless sensor networks,” ACM Trans. Sensor Networks, vol. 3, no. 1, 2007.
- J. Faruque and A. Helmy, “RUGGED: RoUting on finGerprint Gradients in sEnsor Networks,” in IEEE/ACS Intl. Conf. on Pervasive Services (ICPS), 2004, pp. 179–188.
- S. Pattem, B. Krishnamachari, and R. Govindan, “The impact of spatial correlation on routing with compression in wireless sensor networks,” in Proceedings of the Third International Symposium on Information Processing in Sensor Networks, 2004, pp. 28–35.
- D. Ganesan, B. Greenstein, D. Perelyubskiy, D. Estrin, and J. Heidemann, “An evaluation of multiresolution search and storage in resource-constrained sensor networks,” in Proceedings of the First ACM Conference on Embedded Networked Sensor Systems (SenSys), 2003.
-
A. Jindal and K. Psounis, “Modeling spatially correlated data in sensor networks,” ACM Trans. Sensor Networks, vol. 2, no. 4, pp. 466–499, 2006.
10.1145/1218556.1218558 Google Scholar
-
J. Besag, “Spatial interaction and the statistical analysis of lattice systems,” J. Roy. Stat. Soc., vol. 36, no. B, pp. 192–225, 1974.
10.1111/j.2517-6161.1974.tb00999.x Google Scholar
- J. Besag, “Statistical analysis of non-lattice data,” Statistician, vol. 24, no. 3, pp. 179–195, 1975.
- J. Hammersley and P. Clifford, “Markov fields on finite graphs and lattices,” unpublished manuscript, 1971.
- P. Clifford, “Markov random fields in statistics,” Disord. Phys. Syst., pp. 19–32, 1990.
- M. Cetin, L. Chen, J. Fisher, A. Ihler, O. Kreidl, R. Moses, M. Wainwright, J. Williams, and A. Willsky, “Graphical models and fusion in sensor networks,” in Wireless Sensor Networks: Signal Processing & Comm. Perspectives, Hoboken, NJ: Wiley, 2007, pp. 215–250.
-
S. Li, Markov Random Field Modeling in Computer Vision, London: Springer-Verlag, 1995.
10.1007/978-4-431-66933-3 Google Scholar
-
N. Cressie, Statistics for Spatial Data, New York: Wiley, 1993.
10.1002/9781119115151 Google Scholar
- W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “An application-specific protocol architecture for wireless microsensor networks,” IEEE Trans. W. Commun., vol. 1, no. 4, pp. 660–670, Oct. 2002.
- T. Kwon and M. Gerla, “Clustering with power control,” in Military Communications Conference Proceedings, IEEE, Vol. 2, 1999.
- C. Chow and C. Liu, “Approximating discrete probability distributions with dependence trees,” IEEE Trans. Inform. Theory, vol. 14, no. 3, pp. 462–467, 1968.
- S. Sanghavi, V. Tan, and A. Willsky, “Learning graphical models for hypothesis testing,” in IEEE Workshop on Stat. Signal Proc., 2007.
- S. Lauritzen, Graphical Models. Clarendon, 1996.
- K. Jung and D. Shah, “Approximate message-passing inference algorithm,” in IEEE ITW, 2007, pp. 224–229.
- J. Pearl, Probabilistic Reasoning in Intelligent Systems—Networks of Plausible Inference. Morgan Kaufmann, 1988.
- D. Eppstein, “All maximal independent sets and dynamic dominance for sparse graphs,” in Proc. of ACM-SIAM Symp. on Discrete Algorithms, 2005, pp. 451–459.
- N. Cressie and S. Lele, “New models for Markov random fields,” J. Appl. Prob., vol. 29, no. 4, pp. 877–884, 1992.
- R. Cowell, Probabilistic Networks and Expert Systems, Springer, 1999.
- E. Dynkin, “Necessary and sufficient statistics for a family of probability distributions,” Trans. Math. Stat. Prob., vol. 1, pp. 23–41, 1961.
-
B. Wu and K. Chao, Spanning Trees and Optimization Problems, Chapman & Hall, 2004.
10.1201/9780203497289 Google Scholar
- W. P. Tay, J. N. Tsitsiklis, and M. Z. Win, “Data fusion trees for detection: Does architecture matter?” IEEE Trans. Inform. Theory, 2007, submitted for publication.
- W. P. Tay, J. N. Tsitsiklis, and M. Z. Win, “On the sub-exponential decay of detection error probabilities in long tandems,” IEEE Trans. Inform. Theory, 2007, submitted for publication.
- L. Devroye, “The expected size of some graphs in computational geometry.” Comp. Math. App., vol. 15, no. 1, pp. 53–64, 1988.
- R. Gallager, P. Humblet, and P. Spira, “A distributed algorithm for minimum-weight spanning trees,” ACM Trans. Prog. Lang. Syst. (TOPLAS), vol. 5, no. 1, pp. 66–77, 1983.
- P. Humblet, “A distributed algorithm for minimum weight directed spanning trees,” IEEE Trans. Commun., vol. 31, no. 6, pp. 756–762, 1983.
- V. Vazirani, Approximation Algorithms, Springer, 2001.
- L. Kou, G. Markowsky, and L. Berman, “A fast approximation algorithm for Steiner trees,” Acta Informatica, vol. 15, pp. 141–145, 1981.
- G. Robins and A. Zelikovsky, “Improved Steiner tree approximation in graphs,” in Proc. of ACM-SIAM Symposium on Discrete Algorithms, 2000, pp. 770–779.
- G. Reich and P. Widmayer, “Beyond Steiner's problem: A vlsi oriented generalization,” in Proc. of Intl. Workshop on Graph-Theoretic Concepts in Computer Science, 1990, pp. 196–210.
- N. Garg, G. Konjevod, and R. Ravi, “A polylogarithmic approximation algorithm for the group Steiner tree problem,” J. Algorithms, vol. 37, no. 1, pp. 66–84, 2000.
- C. S. Helvig, G. Robins, and A. Zelikovsky, “Improved approximation bounds for the group Steiner problem,” in DATE ’98: Proceedings of the Conference on Design, Automation and Test in Europe, 1998, pp. 406–413.
- A. Anandkumar, L. Tong, A. Swami, and A. Ephremides, “Minimum cost data aggregation with localized processing for statistical inference,” in Proc. of IEEE INFOCOM, Phoenix, AZ, Apr. 2008, pp. 780–788.
-
P. Brémaud, Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues, Springer, 1999.
10.1007/978-1-4757-3124-8 Google Scholar
-
H. Rue and L. Held, Gaussian Markov Random Fields: Theory and Applications, London: Chapman and Hall, 2005.
10.1201/9780203492024 Google Scholar
- X. Guyon, Random Fields on a Network: Modeling, Statistics, and Applications, Springer, 1995.
- L. Chen, M. Wainwright, M. Cetin, and A. Willsky, “Multitarget-multisensor data association using the tree-reweighted max-product algorithm,” Proc. SPIE, vol. 5096, 2003, pp. 127–138.
- A. Ihler, J. Fisher III, R. Moses, and A. Willsky, “Nonparametric belief propagation for self-localization of sensor networks,” IEEE J. Sel. Areas Commun., vol. 23, no. 4, pp. 809–819, 2005.
- J. Williams, J. Fisher III, and A. Willsky, “An approximate dynamic programming approach to a communication constrained sensor management problem,” in Intl. Conf. on Information Fusion, Vol. 1, 2005.
- O. Kreidl and A. Willsky, “Inference with minimal communication: A decision-theoretic variational approach,” in Advances in Neural Information Processing Systems, 2006.
- O. Kreidl and A. Willsky, “Efficient message-passing algorithms for optimizing decentralized detection networks,” in IEEE Conf. on Decision and Control, 2006.
- C. Moallemi and B. Van Roy, “Consensus propagation,” vol. 52, no. 11, pp. 4753–4766, 2006.
- A. Dimakis, A. Sarwate, and M. Wainwright, “Geographic gossip: Efficient aggregation for sensor networks,” in Proceedings of the Fifth International Conference on Information Processing in Sensor Networks, 2006, pp. 69–76.
- R. Olfati-Saber, E. Franco, E. Frazzoli, and J. Shamma, “Belief consensus and distributed hypothesis testing in sensor networks,” in paper presented at the Workshop on Network Embedded Sensing and Control, Notre Dame University, Oct, 2005.
-
K. Akkaya and M. Younis, “A survey of routing protocols in wireless sensor networks,” Elsevier Adhoc Networks, vol. 3, pp. 325–349, 2005.
10.1016/j.adhoc.2003.09.010 Google Scholar
- R. Cristescu, B. Beferull-Lozano, M. Vetterli, and R. Wattenhofer, “Network correlated data gathering with explicit communication: NP-completeness and algorithms,” IEEE/ACM Trans. Networking (TON), vol. 14, no. 1, pp. 41–54, 2006.
- P. von Rickenbach and R. Wattenhofer, “Gathering correlated data in sensor networks,” paper presented at the Joint Workshop on Foundations of Mobile Computing, 2004, pp. 60–66.
- A. Goel and D. Estrin, “Simultaneous optimization for concave costs: Single sink aggregation or single source buy-at-bulk,” Algorithmica, vol. 43, no. 1, pp. 5–15, 2005.
- H. Gupta, V. Navda, S. Das, and V. Chowdhary, “Efficient gathering of correlated data in sensor networks,” in Proc. of ACM Intl. Symposium on Mobile Ad Hoc Networking and Computing, 2005, pp. 402–413.
- A. Scaglione and S. Servetto, “On the interdependence of routing and data compression in multi-hop sensor networks,” in Proc. MobiCom 2002, Atlanta, GA, Sept. 2002.
- S. Madden, M. Franklin, J. Hellerstein, and W. Hong, “TinyDB: An acquisitional query processing system for sensor networks,” ACM Trans. Database Syst., vol. 30, no. 1, pp. 122–173, 2005.
- J. Gehrke and S. Madden, “Query processing in sensor networks,” IEEE Pervasive Comput., vol. 3, no. 1, pp. 46–55, 2004.
- C. Intanagonwiwat, R. Govindan, and D. Esterin, “Directed diffusion: A scalable and robust paradigm for sensor networks,” in Proc. 6th ACM/Mobicom Conference, Boston, MA, 2000, pp. 56–67.
- B. Krishnamachari, D. Estrin, and S. Wicker, “Modeling data centric routing in wireless sensor networks,” in INFOCOM, New York, 2002.
- A. Giridhar and P. Kumar, “Toward a theory of in-network computation in wireless sensor networks,” Commun. Mag. IEEE, vol. 44, no. 4, pp. 98–107, 2006.
- R. Rajagopalan and P. Varshney, “Data aggregation techniques in sensor networks: A survey,” Commun. Surveys Tutorials IEEE, vol. 8, no. 4, pp. 48–63, 2006.
- S. Misra, L. Tong, and A. Ephremides, “Application dependent shortest path routing in ad-hoc sensor networks,” in Wireless Sensor Networks: Signal Processing & Comm. Perspectives, Hoboken, NJ: Wiley, 2007, pp. 277–310.
