N状态二进制一致性算法设计及其优化
|
摘要
针对二进制一致性算法扩展性差、经验依赖性强的缺点,提出了一种N状态分布式二进制一致性算法。首先,基于Gossip算法的平均一致性思想和轮盘赌思想,更新无线传感器网络状态均值和当前状态均值的偏差程度,计算所有可能更新状态的初始概率分布;然后,利用遗传算法优化初始概率分布,得到准确率较高的最优概率分布。仿真结果表明,在相同状态个数条件下,本文所设计的算法具有更好的准确率和收敛时间。
Given the disadvantages of poor expansibility and strong experience dependence of existing binary consensus algorithms, we propose an N-state distributed binary consensus algorithm. Firstly, based on the idea of average consensus of the Gossip algorithm and the roulette idea, the degree of deviation between the state average of the wireless sensor network and the current state average is updated, and the initial probabilistic distribution of all possible update states is calculated. Secondly, the genetic algorithm is applied to optimize the initial probability distribution and obtain the optimal probability distribution with better accuracy. The results show that the proposed algorithm has higher accuracy and shorter convergence time under the same number of states.
Given the disadvantages of poor expansibility and strong experience dependence of existing binary consensus algorithms, we propose an N-state distributed binary consensus algorithm. Firstly, based on the idea of average consensus of the Gossip algorithm and the roulette idea, the degree of deviation between the state average of the wireless sensor network and the current state average is updated, and the initial probabilistic distribution of all possible update states is calculated. Secondly, the genetic algorithm is applied to optimize the initial probability distribution and obtain the optimal probability distribution with better accuracy. The results show that the proposed algorithm has higher accuracy and shorter convergence time under the same number of states.
引文
[1] Wang Shuai,Yang Wen,Shi Hong-bo.Consensus-based filtering algorithm with packet-dropping [J].Acta Automatica Sinica,2010,36(12):1689-1696.(in Chinese)
[2] Duan Xiao-ming.The consensus algorithms design and analysis in wireless sensor networks [D].Hangzhou:Zhejiang University,2016.(in Chinese)
[3] Benezit F,Thiran P,Vetterli M.Interval consensus:From quantized gossip to voting [C]//Proc of the 2009 IEEE International Conference on Acoustics,Speech and Signal Processing,2009:3661-3664.
[4] Perron E,Vasudevan D,Vojnovic M.Using three states for binary consensus on complete graphs [C]//Proc of 2009 IEEE INFOCOM,2009:2527-2535.
[5] Draief M,Vojnovic M.Convergence speed of binary interval consensus [J].SIAM Journal on Control and Optimization,2012,50(3):1087-1109.
[6] Abdaoui A,Elfouly T M.Distributed binary consensus algorithm in wireless sensor networks with faulty nodes [C]//Proc of GCC Conference and Exhibition,2013:495-500.
[7] Gogolev A E,Marcenaro L.Efficient binary consensus in randomized and noisy environments [C]//Proc of IEEE 9th International Conference on Intelligent Sensors,Sensor Networks and Information Processing,2014:1-6.
[8] Mostofi Y,Malmirchegini M.Binary consensus over fading channels [J].IEEE Transactions on Signal Processing,2010,58(12):6340-6354.
[9] Abdaoui A,El-Fouly T M.TOSSIM and distributed binary consensus algorithm in wireless sensor networks [J].Journal of Network & Computer Applications,2014,41(1):451-458.
[10] Al-Nakhala N,Riley R,Elfouly T M.Binary consensus in sensor motes [C]//Proc of Wireless Communications and Mobile Computing Conference,2013:1337-1342.
[11] Boyd S,Ghosh A,Prabhakar B,et al.Randomized gossip algorithms [J].IEEE Transactions on Information Theory,2006,52(6):2508-2530.
[12] Lin X,Boyd S.Fast linear iterations for distributed averaging [C]//Proc of IEEE Conference on Decision and Control,2004:4997-5002.
[13] Fan Sha.Fast distributed consensus filtering of wireless sensor network [D].Kunming:Kunming University of Science and Technology,2016.(in Chinese)
[14] Zhang Peng,Feng Xu-xiang,Ge Xiao-qing.A hardware resource allocation method for multi-antenna ground station based on improved genetic algorithm [J].Computer Enginering & Science,2017,39(6):1155-1163.(in Chinese)
[1] 王帅,杨文,侍洪波.带丢包一致性滤波算法研究[J].自动化学报,2010,36(12):1689-1696.
[2] 段晓明.无线传感器网络中一致性算法设计与分析[D].杭州:浙江大学,2016.
[13] 范莎.无线传感器网络的分布式快速一致性滤波[D].昆明:昆明理工大学,2016.
[14] 张鹏,冯旭祥,葛小青.基于改进遗传算法的多天线地面站硬件资源分配方法[J].计算机工程与科学,2017,39(6):1155-1163.
[2] Duan Xiao-ming.The consensus algorithms design and analysis in wireless sensor networks [D].Hangzhou:Zhejiang University,2016.(in Chinese)
[3] Benezit F,Thiran P,Vetterli M.Interval consensus:From quantized gossip to voting [C]//Proc of the 2009 IEEE International Conference on Acoustics,Speech and Signal Processing,2009:3661-3664.
[4] Perron E,Vasudevan D,Vojnovic M.Using three states for binary consensus on complete graphs [C]//Proc of 2009 IEEE INFOCOM,2009:2527-2535.
[5] Draief M,Vojnovic M.Convergence speed of binary interval consensus [J].SIAM Journal on Control and Optimization,2012,50(3):1087-1109.
[6] Abdaoui A,Elfouly T M.Distributed binary consensus algorithm in wireless sensor networks with faulty nodes [C]//Proc of GCC Conference and Exhibition,2013:495-500.
[7] Gogolev A E,Marcenaro L.Efficient binary consensus in randomized and noisy environments [C]//Proc of IEEE 9th International Conference on Intelligent Sensors,Sensor Networks and Information Processing,2014:1-6.
[8] Mostofi Y,Malmirchegini M.Binary consensus over fading channels [J].IEEE Transactions on Signal Processing,2010,58(12):6340-6354.
[9] Abdaoui A,El-Fouly T M.TOSSIM and distributed binary consensus algorithm in wireless sensor networks [J].Journal of Network & Computer Applications,2014,41(1):451-458.
[10] Al-Nakhala N,Riley R,Elfouly T M.Binary consensus in sensor motes [C]//Proc of Wireless Communications and Mobile Computing Conference,2013:1337-1342.
[11] Boyd S,Ghosh A,Prabhakar B,et al.Randomized gossip algorithms [J].IEEE Transactions on Information Theory,2006,52(6):2508-2530.
[12] Lin X,Boyd S.Fast linear iterations for distributed averaging [C]//Proc of IEEE Conference on Decision and Control,2004:4997-5002.
[13] Fan Sha.Fast distributed consensus filtering of wireless sensor network [D].Kunming:Kunming University of Science and Technology,2016.(in Chinese)
[14] Zhang Peng,Feng Xu-xiang,Ge Xiao-qing.A hardware resource allocation method for multi-antenna ground station based on improved genetic algorithm [J].Computer Enginering & Science,2017,39(6):1155-1163.(in Chinese)
[1] 王帅,杨文,侍洪波.带丢包一致性滤波算法研究[J].自动化学报,2010,36(12):1689-1696.
[2] 段晓明.无线传感器网络中一致性算法设计与分析[D].杭州:浙江大学,2016.
[13] 范莎.无线传感器网络的分布式快速一致性滤波[D].昆明:昆明理工大学,2016.
[14] 张鹏,冯旭祥,葛小青.基于改进遗传算法的多天线地面站硬件资源分配方法[J].计算机工程与科学,2017,39(6):1155-1163.