计算机科学 ›› 2023, Vol. 50 ›› Issue (2): 13-22.doi: 10.11896/jsjkx.221100134

• 边缘智能协同技术及前沿应用 • 上一篇    下一篇

Distributed Weighted Data Aggregation Algorithm in End-to-Edge Communication Networks Based on Multi-armed Bandit

Yifei ZOU1, Senmao QI1, Cong'an XU2,3, Dongxiao YU1   

  1. 1 School of Computer Science and Technology,Shandong University,Qingdao 266237,China
    2 Naval Aviation University,Yantai 264000,China
    3 Advanced Technology Research Institute,Beijing Institute of Technology,Jinan 250300,China
  • 收稿日期:2022-11-15 修回日期:2023-01-16 出版日期:2023-02-15 发布日期:2023-02-22

Distributed Weighted Data Aggregation Algorithm in End-to-Edge Communication Networks Based on Multi-armed Bandit

Yifei ZOU1, Senmao QI1, Cong'an XU2,3, Dongxiao YU1   

  1. 1 School of Computer Science and Technology,Shandong University,Qingdao 266237,China
    2 Naval Aviation University,Yantai 264000,China
    3 Advanced Technology Research Institute,Beijing Institute of Technology,Jinan 250300,China
  • Received:2022-11-15 Revised:2023-01-16 Online:2023-02-15 Published:2023-02-22
  • Contact: Dongxiao YU (dxyu@sdu.edu.cn)
  • Supported by:
    National Natural Science Foundation of China(NSFC)(62102232,62122042,61971269) and Natural Science Foundation of Shandong Province Under(ZR2021QF064)

Abstract: As a combination of edge computing and artificial intelligence,edge intelligence has become a promising technique and provided its users with a series of fast,precise,and customized services.In edge intelligence,when learning agents are deployed on the edge side,the data aggregation from the end side to the designated edge devices is an important research topic.Considering the various importance of end devices,this paper studies the weighted data aggregation problem in a single hop end-to-edge communication network.Firstly,to make sure all the end devices with various weights are fairly treated in data aggregation,a distributed end-to-edge cooperative scheme is proposed.Then,to handle the massive contention on the wireless channel caused by end devices,a multi-armed bandit (MAB) algorithm is designed to help the end devices find their most appropriate update rates.Diffe-rent from the traditional data aggregation works,combining the MAB enables our algorithm a higher efficiency in data aggregation.With a theoretical analysis,we show that the efficiency of our algorithm is asymptotically optimal.Comparative experiments with previous works are also conducted to show the strength of our algorithm.

Key words: Weighted data aggregation, End-to-edge communication, Multi-armed bandit, Edge intelligence

中图分类号: 

  • TP393
[1]CAI Z,SHI T.Distributed Query Processing in the Edge Assisted IoT Data Monitoring System[J].IEEE Internet of Things Journal,2021,8(16):12679-12693.
[2]ZHU T,SHI T,LI J,et al.Task Scheduling in Deadline-Aware Mobile Edge Computing Systems[J].IEEE Internet of Things Journal,2019,6(3):4854-4866.
[3]YU L,SHEN H,CAI Z,et al.Towards Bandwidth Guaranteefor Virtual Clusters under Demand Uncertainty in Multi-tenant Clouds[J].IEEE Transactions on Parallel and Distributed Systems,2018,29(2):450-465.
[4]DENG S,ZHAO H,FANG W,et al.Edge intelligence:The confluence of edge computing and artificial intelligence[J].IEEE Internet of Things Journal,2020,7(8):7457-7469.
[5]KAUR M,MUNJAL A.Data aggregation algorithms for wireless sensor network:a review[J].Ad Hoc Networks,2020,100:102083.
[6]SUMALEE A,HO H W.Smarter and more connected:Futureintelligent transportation system[J].Iatss Research,2018,42(2):67-71.
[7]RANDHAWA S,JAIN S.Dahda:dynamic adaptive hierarchical data aggregation for clustered wireless sensor networks[J].Wireless Personal Communications,2017,97(4):6369-6399.
[8]GUPTA G P,MISRA M,GARG K.Towards scalable and load-balanced mobile agents-based data aggregation for wireless sensor networks[J].Computers & Electrical Engineering,2017,64:262-276.
[9]EL FISSAOUI M,BENI-HSSANE A,SAADI M.Mobile agent protocol-based energy aware data aggregation for wireless sensor networks[C]//Procedia computer science.2017:25-32.
[10][10] LEI Y,QIN H,CHEN W,et al.Secure Data AggregationScheme Based on Dynamic Multi-cluster Key Management Mo-del[J].Computer Science,2011,38(9):36-40.
[11]YU D,ZOU Y,XU M,et al.Competitive age of information in dynamic iot networks[J].IEEE Internet of Things Journal,2020,8(20):15160-15169.
[12]YU D,ZOU Y,ZHANG Y,et al.An exact implementation of the abstract mac layer via carrier sensing in dynamic networks[J].IEEE/ACM Transactions on Networking,2021,29(3):994-1007.
[13]RICHA A,SCHEIDELER C,SCHMID S,et al.An efficient and fair mac protocol robust to reactive interference[J].IEEE/ACM Transactions on Networking,2012,21(3):760-771.
[14]XU H,HUANG L,ZHANG Y,et al.Energy-efficient cooperative data aggregation for wireless sensor networks[J].Journal of Parallel and Distributed Computing,2010,70(9):953-961.
[15]XIAO S,LI B,YUAN X.Maximizing precision for energy-efficient data aggregation in wireless sensor networks with lossy links[J].Ad Hoc Networks,2015,26:103-113.
[16]NIKNAM S,DHILLON H S,REED J H.Federated learning for wireless communications:Motivation,opportunities,and challenges[J].IEEE Communications Magazine,2020,58(6):46-51.
[17]LI F,YU D,YANG H,et al.Multi-armed-bandit-based spec-trum scheduling algorithms in wireless networks:A survey[J].IEEE Wireless Communications,2020,27(1):24-30.
[18]CHEN S,WANG X,ZHOU P,et al.Heterogeneous semi-asynchronous federated learning in internet of things:A multi-armed bandit approach[J].IEEE Transactions on Emerging Topics in Computational Intelligence,2022,6(5):1113-1124.
[19]XIA W,QUEK T Q,GUO K,et al.Multi-armed bandit-based client scheduling for federated learning[J].IEEE Transactions on Wireless Communications,2020,19(11):7108-7123.
[20]DHAND G,TYAGI S.Data aggregation techniques in wsn:Survey[J].Procedia Computer Science,2016,92:378-384.
[21]GHATE V V,VIJAYAKUMAR V.Machine learning for data aggregation in wsn:A survey[J].International Journal of Pure and Applied Mathematics,2018,118(24):1-12.
[22]DONG H,WEI S,LIU X,et al.A Survey of Routing Methods for Wireless Sensor Networks Oriented to Environment Awareness[J].Computer Science,2018,45(1):14-22.
[23]FENG H Y,ZHOU L,DING Q L.Data Aggregation Algorithm for Wireless Sensor Networks Based on Data Stream and Network Coding[J].Computer Science,2015,42(5):136-140.
[24]XU D,LI T,LI Y,et al.Edge intelligence:Architectures,challenges,and applications[J].arXiv:2003.12172,2020.
[25]ABBASI-DARESARI S,ABOUEI J.Toward cluster-basedweighted compressive data aggregation in wireless sensor networks[J].Ad Hoc Networks,2016,36:368-385.
[26]RAZZAQ M,KWON G R,SHIN S.Energy efficient dijkstra-based weighted sum minimization routing protocol for wsn[C]//2018 Third International Conference on Fog and Mobile Edge Computing(FMEC).IEEE,2018:246-251.
[27]ZHANG X,TAO L,YAN F,et al.Shortest-latency opportunistic routing in asynchronous wireless sensor networks with independent duty-cycling[J].IEEE Transactions on Mobile Computing,2019,19(3):711-723.
[28]YANG L,ZOU Y,XU M,et al.Distributedconsensus for blockchains in internet-of-things networks[J].Tsinghua Science and Technology,2022,27(5):817-831.
[29]ZOU Y,XU M,YU J,et al.A fast consensus forpermissioned wireless blockchains[J].IEEE Internet of Things Journal,2021.
[30]CHEN Y,SUN X,JIN Y.Communication-efficient federateddeeplearning with layerwise asynchronous model update and temporallyweighted aggregation[J].IEEE Transactions on Neural Networks Andlearning Systems,2019,31(10):4229-4238.
[31]MA Z,ZHAO M,CAI X,et al.Fast-convergent federated lear-ning with class-weighted aggregation[J].Journal of Systems Architecture,2021,117:102125-102131.
[32]ALEXANDRU A B,PAPPAS G J.Private weighted sum aggregationfor distributed control systems[J].IFAC-Papers OnLine,2020,53(2):11081-11088.
[33]ADACHI R,YAMASHITA Y,KOBAYASHI K.Distributedestimationbased on weighted data aggregation over delayed sensor networks[J].IFAC Journal of Systems and Control,2020,14:100109-100115.
[34]KULESHOV V,PRECUP D.Algorithms for multi-armed bandit problems[J].arXiv:1402.6028,2014.
[1] 杨昕, 李挥, 阙建明, 马震太, 李更新, 姚尧, 王滨, 蒋傅礼.
面向未来网络的安全高效防护架构
Efficiently Secure Architecture for Future Network
计算机科学, 2023, 50(3): 360-370. https://doi.org/10.11896/jsjkx.220600265
[2] 陈祎鹏, 杨哲, 谷飞, 赵雷.
一种基于博弈论的移动边缘计算资源分配策略
Resource Allocation Strategy Based on Game Theory in Mobile Edge Computing
计算机科学, 2023, 50(2): 32-41. https://doi.org/10.11896/jsjkx.220300198
[3] 常沙, 吴亚辉, 邓苏, 马武彬, 周浩浩.
基于李雅普诺夫优化的移动群智感知在线任务分配策略
Online Task Allocation Strategy Based on Lyapunov Optimization in Mobile Crowdsensing
计算机科学, 2023, 50(2): 50-56. https://doi.org/10.11896/jsjkx.221100179
[4] Cui ZHANG, En WANG, Funing YANG, Yong jian YANG , Nan JIANG.
UAV Frequency-based Crowdsensing Using Grouping Multi-agentDeep Reinforcement Learning
UAV Frequency-based Crowdsensing Using Grouping Multi-agentDeep Reinforcement Learning
计算机科学, 2023, 50(2): 57-68. https://doi.org/10.11896/jsjkx.221100114
[5] 郑鸿强, 张建山, 陈星.
空-天-地一体化移动边缘计算系统的部署优化和计算卸载
Deployment Optimization and Computing Offloading of Space-Air-Ground Integrated Mobile Edge Computing System
计算机科学, 2023, 50(2): 69-79. https://doi.org/10.11896/jsjkx.220600057
[6] 尚玉叶, 袁家斌.
深空环境中基于云边端协同的任务卸载方法
Task Offloading Method Based on Cloud-Edge-End Cooperation in Deep Space Environment
计算机科学, 2023, 50(2): 80-88. https://doi.org/10.11896/jsjkx.220800156
[7] 杨昕, 李更新, 李挥.
EHFM:一种面向多源网络攻击告警的高效层级化数据过滤方案
EHFM:An Efficient Hierarchical Filtering Method for Multi-source Network Malicious Alerts
计算机科学, 2023, 50(2): 324-332. https://doi.org/10.11896/jsjkx.220800049
[8] 代亮, 吴益钵, 汪贵平.
蜂窝车联网连通性研究综述与展望
Review and Prospect of Connectivity Research on Cellular-V2X
计算机科学, 2023, 50(1): 285-293. https://doi.org/10.11896/jsjkx.211000164
[9] 程文辉, 张乾元, 程梁华, 向朝参, 杨振东, 沈鑫, 张乃凡.
空地协同移动群智感知研究综述
Review of Mobile Air-Ground Crowdsensing
计算机科学, 2022, 49(11): 242-249. https://doi.org/10.11896/jsjkx.220400264
[10] 于浩雯, 刘波, 周娜琴, 林伟伟, 柳鹏.
多云工作流调度综述
Survey of Multi-cloud Workflow Scheduling
计算机科学, 2022, 49(11): 250-258. https://doi.org/10.11896/jsjkx.211200234
[11] 李晓波, 陈鹏, 帅彬, 夏云霓, 李建岐.
边缘环境下轨迹预测性感知的在线边缘服务分配
Novel Predictive Approach to Trajectory-aware Online Edge Service Allocation in Edge Environment
计算机科学, 2022, 49(11): 277-283. https://doi.org/10.11896/jsjkx.211100029
[12] 卞庆荣, 程宝雷, 樊建席, 潘志勇.
蜻蜓网络上完全独立生成树的构造算法
Construction Algorithm of Completely Independent Spanning Tree in Dragonfly Network
计算机科学, 2022, 49(11): 284-292. https://doi.org/10.11896/jsjkx.211000037
[13] 刘培文, 舒辉, 吕小少, 赵耘田.
基于有限状态机的内核漏洞攻击自动化分析技术
Automatic Analysis Technology of Kernel Vulnerability Attack Based on Finite State Machine
计算机科学, 2022, 49(11): 326-334. https://doi.org/10.11896/jsjkx.211200039
[14] 何源, 邢长友, 张国敏, 宋丽华, 余航.
面向网络侦察欺骗的差分隐私指纹混淆机制
Differential Privacy Based Fingerprinting Obfuscation Mechanism Towards NetworkReconnaissance Deception
计算机科学, 2022, 49(11): 351-359. https://doi.org/10.11896/jsjkx.220400285
[15] 潘雨, 王帅辉, 张磊, 胡谷雨, 邹军华, 王田丰, 潘志松.
复杂网络社团发现综述
Survey of Community Detection in Complex Network
计算机科学, 2022, 49(11A): 210800144-11. https://doi.org/10.11896/jsjkx.210800144
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!