通信高效的分布式阈值监控算法设计与分析

doi:10.3778/j.issn.1002-8331.2406-0209

摘要/Abstract

摘要： 分布式阈值监控问题主要关注如何在多个传感器与一个中枢处理器之间高效地监控某个事件的累积数量是否超过了预设的阈值。现有的分布式阈值监控算法多以最小化通信次数为目标，这一指标虽然易于计算和优化，但并不能全面反映通信的真实代价。相比之下，通信的总比特数是一个更为精确的衡量标准。针对具有预设概率分布的分布式阈值监控问题，提出一种新的分布式监控算法（bits-based distributed tracking algorithm，BBDTA）。该算法以最小化通信比特数为目标，通过轮次统计、间隔汇报、询问与估计等机制，有效避免了传输大数值所带来的通信开销。该算法的通信代价在理论上得到证明，并与现有算法的理论值进行了比较，显示出其在通信效率上的提升。在均匀分布的条件下，该算法可以通过进一步的优化大幅降低通信代价。为验证算法BBDTA的性能，在多种实验条件下比较了BBDTA与其余四种常见的分布式监控算法，结果表明，该算法在多数场景中具有明显优势，验证了其在分布式监控问题中的实用性和高效性。

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

Abstract: The distributed threshold tracking problem focuses on efficiently monitoring whether the cumulative count of a particular event across multiple sensors exceeds a preset threshold. Current algorithms aim to minimize the number of communications, an easily computable metric, but this does not fully reflect the true cost. A more accurate measure is the total number of bits communicated. This paper introduces the bits-based distributed tracking algorithm (BBDTA), which minimizes communication bits using round statistics, interval reporting, inquiries, and estimations. Theoretical analysis demonstrates the communication cost of the BBDTA, showing its enhanced efficiency compared to existing algorithms. Under a uniform distribution, the algorithm can be further optimized to reduce costs. Experimental comparisons with four common algorithms reveal that the BBDTA has a distinct advantage in most scenarios, validating its practicality and efficiency.

Key words: random algorithm, sampling, distributed tracking, data streams, functional monitoring

严欣愉, 黄增峰. 通信高效的分布式阈值监控算法设计与分析[J]. 计算机工程与应用, 2025, 61(19): 260-272.

YAN Xinyu, HUANG Zengfeng. Design and Analysis of Communication-Efficient Distributed Threshold Tracking Algorithm[J]. Computer Engineering and Applications, 2025, 61(19): 260-272.

参考文献

[1] CABRAL A, WALDO J. Designing large-scale wireless sensor networks for urban environmental sensing[C]//Proceedings of the 2023 ACM International Joint Conference on Pervasive and Ubiquitous Computing & the 2023 ACM International Symposium on Wearable Computing. New York: ACM, 2023: 253-257.
[2] 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. New York: ACM, 2005: 25-36.
[3] CARNEY D, ?ETINTEMEL U, CHERNIACK M, et al. Monitoring streams: a new class of data management applications[C]//Proceedings of the 28th International Conference on Very Large Data Bases, 2002: 215-226.
[4] WIDOM J. Query processing, resource management, and approximation in a data stream management system[C]//Proceedings of the 2003 CIDR Conference, 2003.
[5] JUANG P, OKI H, WANG Y, et al. Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet[J]. ACM SIGPLAN Notices, 2002, 37(10): 96-107.
[6] 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.
[7] GREENWALD M, KHANNA S. Space-efficient online computation of quantile summaries[J]. ACM SIGMOD Record, 2001, 30(2): 58-66.
[8] CORMODE G, MUTHUKRISHNAN S. What’s hot and what’s not: tracking most frequent items dynamically[C]//Proceedings of the 22nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. New York: ACM, 2003: 296-306.
[9] MANKU G S, MOTWANI R. Approximate frequency counts over data streams[C]//Proceedings of the 28th International Conference on Very Large Data Bases, 2002: 346-357.
[10] GANGULY S, GAROFALAKIS M, RASTOGI R. Processing set expressions over continuous update streams[C]//Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2003: 265-276.
[11] ALON N, GIBBONS P B, MATIAS Y, et al. Tracking join and self-join sizes in limited storage[C]//Proceedings of the Eighteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. New York: ACM, 1999: 10-20.
[12] ALON N, MATIAS Y, SZEGEDY M. The space complexity of approximating the frequency moments[C]//Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. New York: ACM, 1996: 20-29.
[13] GILBERT A, KOTIDIS Y, MUTHUKRISHNAN S, et al. Surfing wavelets on streams: one-pass summaries for approximate aggregate queries[C]//Proceedings of the 27th International Conference on Very Large Data Bases, 2001: 79-88.
[14] CHARIKAR M, CHEN K, FARACH-COLTON M. Finding frequent items in data streams[J]. Theoretical Computer Science, 2004, 312(1): 3-15.
[15] BABCOCK B, OLSTON C. Distributed top-k monitoring[C]//Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2003: 28-39.
[16] CORMODE G, YI K. Tracking distributed aggregates over time-based sliding windows[C]//Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. New York: ACM, 2011: 213-214.
[17] GANGULY S, GAROFALAKIS M, RASTOGI R. Tracking set-expression cardinalities over continuous update streams[J]. The VLDB Journal, 2004, 13(4): 354-369.
[18] CORMODE G, MUTHUKRISHNAN S, YI K. Algorithms for distributed functional monitoring[J]. ACM Transactions on Algorithms, 2011, 7(2): 1-20.
[19] WU H, GAN J H, ZHANG R. Learning based distributed tracking[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2020: 2040-2050.
[20] KASHYAP S, RAMAMIRTHAM J, RASTOGI R, et al. Efficient constraint monitoring using adaptive thresholds[C]//Proceedings of the 2008 IEEE 24th International Conference on Data Engineering. Piscataway: IEEE, 2008: 526-535.
[21] SHARFMAN I, SCHUSTER A, KEREN D. A geometric approach to monitoring threshold functions over distributed data streams[J]. ACM Transactions on Database Systems, 2007, 32(4): 23.
[22] CORMODE G. The continuous distributed monitoring model[J]. ACM SIGMOD Record, 2013, 42(1): 5-14.
[23] HUANG Z F, YI K, ZHANG Q. Randomized algorithms for tracking distributed count, frequencies, and ranks[J]. Algorithmica, 2019, 81(6): 2222-2243.
[24] CHUNG F, LU L Y. Concentration inequalities and martingale inequalities: a survey[J]. Internet Mathematics, 2006, 3(1): 79-127.
[25] MCDIARMID C. Concentration[M]//Probabilistic methods for algorithmic discrete mathematics. Berlin, Heidelberg: Springer, 1998: 195-248.