Analysis and Comparison of Truly Distributed Solvers for Linear Least Squares Problems on Wireless Sensor Networks

详细信息    查看全文

• 作者：Karl E. Prikopa (16)
  Hana Straková (16)
  Wilfried N. Gansterer (16)
  
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8632
• 期：1
• 页码：403-414
• 全文大小：383 KB
• 参考文献：1. Reise, G., Matz, G., Grochenig, K.: Distributed field reconstruction in wireless sensor networks based on hybrid shift-invariant spaces. IEEE Transactions on Signal Processing?60(10), 5426-439 (2012) CrossRef
  2. Sayed, A.H.: Diffusion adaptation over networks. In: Academic Press Library in Signal Processing, vol.?3, pp. 323-54. Academic Press, Elsevier (2014)
  3. Shi, L., Song, W.Z., Xu, M., Xiao, Q., Kamath, G., Lees, J., Xing, G.: Imaging seismic tomography in sensor network. In: IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS), pp. 304-06 (2013)
  4. Reichenbach, F., Born, A., Timmermann, D., Bill, R.: A distributed linear least squares method for precise localization with low complexity in wireless sensor networks. In: Gibbons, P.B., Abdelzaher, T., Aspnes, J., Rao, R. (eds.) DCOSS 2006. LNCS, vol.?4026, pp. 514-28. Springer, Heidelberg (2006) CrossRef
  5. Kempe, D., Dobra, A., Gehrke, J.: Gossip-based computation of aggregate information. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 482-91 (2003)
  6. Gansterer, W.N., Niederbrucker, G., Straková, H., Schulze Grotthoff, S.: Scalable and fault tolerant orthogonalization based on randomized distributed data aggregation. Journal of Computational Science?4(6), 480-88 (2013) CrossRef
  7. Niederbrucker, G., Straková, H., Gansterer, W.N.: Improving fault tolerance and accuracy of a distributed reduction algorithm. In: SC Companion: High Performance Computing, Networking, Storage and Analysis, pp. 643-51 (2012)
  8. Khan, M.I., Gansterer, W.N., Haring, G.: Static vs. mobile sink: The influence of basic parameters on energy efficiency in wireless sensor networks. Computer Communications?36(9), 965-78 (2013) CrossRef
  9. Le Borgne, Y.A., Nowe, A., Abughalieh, N., Steenhaut, K.: Distributed regression for high-level feature extraction in wireless sensor networks. In: 2010 Seventh International Conference on Networked Sensing Systems (INSS), pp. 249-52 (2010)
  10. Shi, L., Song, W.Z., Kamath, G., Xing, G., Liu, X.: Distributed least-squares iterative methods in networks: A survey. Submitted to Computing Journal (2013)
  11. Renaut, R.A.: A parallel multisplitting solution of the least squares problem. Numerical Linear Algebra with Applications?5(1), 11-1 (1998) CrossRef
  12. Yang, L., Brent, R.: Parallel MCGLS and ICGLS methods for least squares problems on distributed memory architectures. The Journal of Supercomputing?29(2), 145-56 (2004) CrossRef
  13. Behnke, R., Salzmann, J., Lieckfeldt, D., Timmermann, D.: SDLS - Distributed least squares localization for large wireless sensor networks. In: International Conference on Ultra Modern Telecommunications & Workshops, pp. 1- (2009)
  14. Shakibian, H., Charkari, N.: MMS-PSO for distributed regression over sensor networks. In: IEEE Conference on Multisensor Fusion and Integration for Intelligent Systems (MFI), pp. 68-3 (2010)
  15. Zhou, Q., Kar, S., Huie, L., Poor, H.V.: Robust distributed least-squares estimation in sensor networks with node failures. In: IEEE Global Telecommunications Conference, pp.1- (2011)
  16. Cattivelli, F., Sayed, A.: Diffusion LMS strategies for distributed estimation. IEEE Transactions on Signal Processing?58(3), 1035-048 (2010) CrossRef
  17. Tu, S.Y., Sayed, A.: Diffusion strategies outperform consensus strategies for distributed estimation over adaptive networks. IEEE Transactions on Signal Processing?60(12), 6217-234 (2012) CrossRef
  18. Schizas, I.: Consensus in ad hoc WSNs with noisy links - Part II: Distributed estimation and smoothing of random signals. IEEE Transactions on Signal Processing?56(4), 1650-666 (2008) CrossRef
  19. Mateos, G., Schizas, I.D., Giannakis, G.B.: Performance analysis of the consensus-based distributed LMS algorithm. EURASIP Journal on Advances in Signal Processing?2009(1), 68:6-8:6 (2009)
  20. Schizas, I.D., Mateos, G., Giannakis, G.B.: Distributed LMS for consensus-based in-network adaptive processing. IEEE Transactions on Signal Processing?57(6), 2365-382 (2009) CrossRef
  21. Sluciak, O., Rupp, M.: Network size estimation using distributed orthogonalization. IEEE Signal Processing Letters?20(4), 347-50 (2013) CrossRef
  22. Straková, H., Gansterer, W.N., Zemen, T.: Distributed QR factorization based on randomized algorithms. In: Wyrzykowski, R., Dongarra, J., Karczewski, K., Wa?niewski, J. (eds.) PPAM 2011, Part I. LNCS, vol.?7203, pp. 235-44. Springer, Heidelberg (2012) CrossRef
  23. Straková, H., Gansterer, W.N.: A distributed eigensolver for loosely coupled networks. In: 21st Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP), pp. 51-7 (2013)
  
• 作者单位：Karl E. Prikopa (16)
  Hana Straková (16)
  Wilfried N. Gansterer (16)
  
  16. Faculty of Computer Science, University of Vienna, Vienna, Austria
  
• ISSN：1611-3349

文摘

The solution of linear least squares problems across large loosely connected distributed networks (such as wireless sensor networks) requires distributed algorithms which ideally need very little or no coordination between the nodes. We first provide an extensive overview of distributed least squares solvers appearing in the literature and classify them according to their communication patterns. We are particularly interested in truly distributed algorithms which do not require a fusion centre, cluster heads or any multi-hop communication. Beyond existing methods, we propose the novel least squares solver PSDLS, which utilises a recently developed distributed QR factorisation algorithm. All communication between nodes is exclusively performed within the push-sum algorithm for distributed aggregation. We analytically compare the communication cost of PSDLS and the existing truly distributed algorithms. In all these algorithms, the communication cost of reaching a predefined accuracy depends on many factors, including network topology, problem size, and settings of algorithm-specific parameters. We illustrate with simulation experiments that our novel PSDLS solver requires significantly fewer messages per node than the previously existing methods to reach a predefined solution accuracy.