有限干扰下一种稳定的分布式监控算法

doi:10.11896/jsjkx.240200050

摘要/Abstract

摘要： 分布式监控问题作为分布式系统中的一个热点领域,主要关注如何高效地协调多个传感器与中枢处理器之间的计算任务。与将所有传感器信号实时传输至中枢的低效方法相比,分布式算法通过逐轮统计、汇总结果后再发送给中枢,显然更经济。良好的分布式监控算法能以较小的通信代价完成对特定目标的监控任务,有效节约传感器电能,延长使用寿命。该类算法对通信效率和准确性有双重需求。然而,目前对于基于预设概率分布的分布式阈值监控问题的研究相对有限,且现有研究往往基于理想化的假设,导致所设计的算法对实际干扰缺乏抵抗能力。通过引入干扰因素来模拟现实世界的复杂性,旨在寻找更为鲁棒的分布式监控算法。所提算法通过合理选择通信时机,不仅减少了通信次数,显著降低了通信代价,同时也保证了有干扰的环境下的分布式算法的准确性。所提算法的准确性可以在理论层面得到证明,其通信代价在干扰较少时可达到O(KloglogN)。这一研究为分布式监控算法提供了新的视角,为现实复杂监控问题的解决提供了有力支持。

关键词: 随机算法, 抽样, 分布式监控, 数据流, 数值监控

Abstract: Distributed monitoring is a pivotal area in the field of distributed systems.It focuses on the coordination of computational tasks between multiple sensors and a central processor.Typically,sensors notify the central processor immediately upon receiving signals,leading to energy wastage.However,this traditional communication mechanism is inefficient for several reasons.Firstly,the central processor often only needs summarized information,like the total number of signals received over a period.Secondly,sensors buried within objects rely on battery power,making replacements challenging.Lastly,the energy consumed in communication surpasses that needed for computation.In contrast,distributed algorithms summarize results before transmitting to the central processor,proving to be more economical.Good distributed tracking algorithms not only achieve tracking tasks with smaller communication costs,conserving sensor energy and prolonging lifespan,but also demand considerations for communication efficiency and accuracy.However,current research on distributed threshold monitoring problems based on preset probability distributions is relatively limited.Existing studies often rely on idealized assumptions,resulting in algorithms lacking robustness against real-world interference.This paper introduces interference to simulate the complexities of the real world,aiming to identify more robust distributed tracking algorithms.The proposed algorithm reduces communication rounds by judiciously selecting the thresholds for sensors to send notifications to the central processor,significantly reducing communication costs.Additionally,it ensures algorithm accuracy in the presence of interference.The algorithm's accuracy is theoretically proven,while its communication cost can reach O(KloglogN) when interference is limited.This study provides a fresh perspective on distributed tracking algorithms,supporting the solution of practical tracking problems.

Key words: Random algorithm, Sampling, Distributed monitoring, Data streams, Functional monitoring

中图分类号:

TP311

严欣愉, 黄增峰. 有限干扰下一种稳定的分布式监控算法[J]. 计算机科学, 2024, 51(11A): 240200050-7. https://doi.org/10.11896/jsjkx.240200050

YAN Xinyu, HUANG Zengfeng. Robust Distributed Monitoring Algorithm Under Limited Interference[J]. Computer Science, 2024, 51(11A): 240200050-7. https://doi.org/10.11896/jsjkx.240200050

参考文献

[1]JUANG P,OKI H,WANG Y,et al.Energy-efficient computing for wildlife tracking:design tradeoffs and early experiences with ZebraNet [J].SIGPLAN Not,2002,37(10):96-107.
[2]MADDEN S R,FRANKLIN M J,HELLERSTEIN J M,et al.TinyDB:an acquisitional query processing system for sensor networks [J].ACM Transactions on Database Systems,2005,30(1):122-173.
[3]KERALAPURA R,CORMODE G,ßRAMAMIRTHAM J.Communication-efficient distributed monitoring of thresholded counts [C]//Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data.Chicago,IL,USA;Association for Computing Machinery.2006:289-300.
[4]CORMODE G,MUTHUKRISHNAN S,YI K.Algorithms for distributed functional monitoring [J].ACM Trans Algorithms,2011,7(2):Article 21.
[5]GANGULY S,GAROFALAKIS M,RASTOGI R.Tracking set-expression cardinalities over continuous update streams [J].The VLDB Journal,2004,13(4):354-369.
[6]CORMODE G,GAROFALAKIS M,MUTHUKRISHNAN S,et al.Holistic aggregates in a networked world:distributed tracking of approximate quantiles [C]//Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data.Baltimore,Maryland:Association for Computing Machinery,2005:25-36.
[7]GIATRAKOS N,DELIGIANNAKIS A,GAROFALAKIS M,et al.Prediction-based geometric monitoring over distributed data streams [C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data.Scottsdale,Arizona,USA:Association for Computing Machinery,2012:265-276.
[8]BABCOCK B,OLSTON C.Distributed top-k monitoring [C]//Proceedings of the 2003 ACM SIGMOD International Confe-rence on Management of Data.San Diego,California;Association for Computing Machinery,2003:28-39.
[9]BAR-YOSSEF Z,JAYRAM T S,KUMAR R,et al.CountingDistinct Elements in a Data Stream [C]//Randomization and Approximation Techniques in Computer Science.Berlin,Heidelberg:Springer,2002.
[10]CORMODE G,GAROFALAKIS M.Approximate continuousquerying over distributed streams [J].ACM Transactions on Database Systems,2008,33(2):Article 9.
[11]OLSTON C,JIANG J,WIDOM J.Adaptive filters for conti-nuous queries over distributed data streams [C]//Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data.San Diego,California:Association for Computing Machinery,2003:563-574.
[12]AHMAD Y,BERG B,CETINTEMEL U,et al.Distributedoperation in the Borealis stream processing engine [C]//Procee-dings of the 2005 ACM SIGMOD International Conference on Management of Data.Baltimore,Maryland:Association for Computing Machinery,2005:882-884.
[13]CHERNIACK M,BALAKRISHNAN H,BALAZINSKA M,et al.Scalable Distributed Stream Processing [C]//Proceedings of the CIDR.2003.
[14]POPA N M,OPRESCU A.A Data-Centric Approach to Distri-buted Tracing[C]//Proceedings of the 2019 IEEE International Conference on Cloud Computing Technology and Science(CloudCom).2019:11-13.
[15]CHEN J,DEWITT D J,TIAN F,et al.NiagaraCQ:a scalablecontinuous query system for Internet databases [C]//Procee-dings of the 2000 ACM SIGMOD International Conference on Management of Data.Dallas,Texas,USA:Association for Computing Machinery,2000:379-390.
[16]MADDEN S,SHAH M,HELLERSTEIN J M,et al.Conti-nuously adaptive continuous queries over streams [C]//Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data.Madison,Wisconsin:Association for Computing Machinery,2002:49-60.
[17]DOBRA A,GAROFALAKIS M,GEHRKE J,et al.Processing complex aggregate queries over data streams [C]//Proceedings of the 2002 ACM SIGMOD International Conference on Ma-nagement of Data.Madison,Wisconsin:Association for Computing Machinery,2002:61-72.
[18]GILBERT A C,KOTIDIS Y,MUTHUKRISHNAN S,et al.How to summarize the universe:dynamic maintenance of quantiles [C]//Proceedings of the 28th International Conference on Very Large Data Bases.Hong Kong,China:VLDB Endowment,2002:454-465.
[19]WU H,GAN J,ZHANG R.Learning Based Distributed Tra-cking [C]//Proceedings of the 26th ACM SIGKDDInterna-tional Conference on Knowledge Discovery & Data Mining.Virtual Event,CA,USA:Association for Computing Machinery,2020:2040-2050.
[20]HUANG Z,YI K,ZHANG Q.Randomized Algorithms forTracking Distributed Count,Frequencies,and Ranks [J].Algorithmica,2019,81(6):2222-2243.
[21]CHUNG F,LU L.Concentration inequalities and martingale inequalities:a survey [J].Internet Mathematics,2006,3(1):79-127.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed