Computer Science ›› 2024, Vol. 51 ›› Issue (11A): 240200050-7.doi: 10.11896/jsjkx.240200050

• Network & Communication • Previous Articles     Next Articles

Robust Distributed Monitoring Algorithm Under Limited Interference

YAN Xinyu, HUANG Zengfeng   

  1. School of Data Science,Fudan University,Shanghai 200433,China
  • Online:2024-11-16 Published:2024-11-13
  • About author:YAN Xinyu,born in 1999,postgra-duate.His main research interests include statistics and machine learning.
    HUANG Zengfeng,born in 1986,Ph.D,professor,Ph.D supervisor.His main research interests include machine learning and big data algorithms.

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

CLC Number: 

  • TP311
[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.
[1] WANG Bin, ZHANG Xinyu, JIN Haiyan. Improved Differential Evolution Algorithm Based on Time-Space Joint Denoising [J]. Computer Science, 2024, 51(9): 299-309.
[2] XIAO Xiao, BAI Zhengyao, LI Zekai, LIU Xuheng, DU Jiajin. Parallel Multi-scale with Attention Mechanism for Point Cloud Upsampling [J]. Computer Science, 2024, 51(8): 183-191.
[3] HUANG Weijie, GUO Xianwei, YU Zhiyong, HUANG Fangwan. Active Sampling of Air Quality Based on Compressed Sensing Adaptive Measurement Matrix [J]. Computer Science, 2024, 51(7): 116-123.
[4] HAN Bing, DENG Lixiang, ZHENG Yi, REN Shuang. Survey of 3D Point Clouds Upsampling Methods [J]. Computer Science, 2024, 51(7): 167-196.
[5] YIN Baosheng, KONG Weiyi. Electra Based Chinese Event Detection Model with Dependency Syntax Tree [J]. Computer Science, 2024, 51(6A): 230600158-6.
[6] WANG Chenzhuo, LU Yanrong, SHEN Jian. Study on Fingerprint Recognition Algorithm for Fairness in Federated Learning [J]. Computer Science, 2024, 51(6A): 230800043-9.
[7] ZHENG Yifan, WANG Maoning. Imbalanced Data Oversampling Method Based on Variance Transfer [J]. Computer Science, 2024, 51(6A): 230400198-6.
[8] LI Zekai, BAI Zhengyao, XIAO Xiao, ZHANG Yihan, YOU Yilin. Point Cloud Upsampling Network Incorporating Transformer and Multi-stage Learning Framework [J]. Computer Science, 2024, 51(6): 231-238.
[9] WU Xiaoqin, ZHOU Wenjun, ZUO Chenglin, WANG Yifan, PENG Bo. Salient Object Detection Method Based on Multi-scale Visual Perception Feature Fusion [J]. Computer Science, 2024, 51(5): 143-150.
[10] HONG Yu, CHEN Hongchang, ZHANG Jianpeng, HUANG Ruiyang , LI Shaomei. Graph Sampling Algorithm Based on Representative Node Expansion to Maintain CommunityStructure [J]. Computer Science, 2024, 51(4): 117-123.
[11] ZHOU Shenghao, YUAN Weiwei, GUAN Donghai. Local Interpretable Model-agnostic Explanations Based on Active Learning and Rational Quadratic Kernel [J]. Computer Science, 2024, 51(2): 245-251.
[12] YUE Meng, WEN Cheng, HONG Xueting, YAN Simin. Airborne Software Provable Data Possession for Cloud Storage [J]. Computer Science, 2024, 51(11A): 240400040-10.
[13] JING Youxian, ZHU Qingsheng. ORB Algorithm Based on Key Point Density Optimization [J]. Computer Science, 2024, 51(11A): 240300048-5.
[14] DONG Yan, WEI Minghong, GAO Guangshuai, LIU Zhoufeng, LI Chunlei. Remote Sensing Orineted Object Detection Method Based on Dual-label Assignment [J]. Computer Science, 2024, 51(11A): 240100058-9.
[15] SUN Pengzhao, BI Kejun, TANG Chao, LI Dongfen, YING Shi, WANG Ruijin. Risk Assessment Model for Industrial Chain Based on Neighbor Sampling and GraphAttention Mechanism [J]. Computer Science, 2024, 51(10): 218-226.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!