分布式共识无线传感器网络广播Gossip算法研究

By launching messages on random walk instead of end-to-end routing, gossip algorithms are more suitable for distributed wireless sensor networks because congestion and link failure can be efficiently resisted. Great effort has been directed to the study of gossip algorithms for distributed consensus. Although there are many exciting research results of pairwise gossip algorithms, some natural defects, including slow rate of convergence and only availability in undirected graphs, influence their practical applications. To solve these problems, broadcast gossip algorithms were proposed in recent years.They can efficiently cope with directed links and utilize the broadcasting property of wireless media. In addition, broadcast gossip algorithms allow more than two nodes to accomplish updates at each iteration so the rate of convergence is faster than pairwise gossip algorithms. Unfortunately, all proposed broadcast gossip algorithms can be sort into two classes: one doesn't preserve average and another cannot be proven convergence by mathematics. Therefore, it's the first time that broadcast gossip algorithms proposed in this project can preserve average, meanwhile, the convergence can be proven by mathematics. After that, the tight upper bound and optimization of perturbation parameter will be analyzed, which will be an outstanding work that no one has accomplished before. Finnaly, the performance of broadcast gossip algorithms under noise channels and quantization errors will be discussed, which is still a theoretical blank for broadcast gossip algorithms.

Gossip算法由于采用了随机行走模式来传递数据，和端到端基于路由的通信方式相比，有效地避免了拥塞和路径失效问题，因而更适合于分布式的无线传感器网络。作为一个重要的应用，基于Gossip算法的分布式共识得到了国际上的广泛研究。但是，这一领域现有的研究成果普遍集中于成对Gossip算法，收敛速度慢并只能用于对称链路的网络。而近几年出现的广播Gossip算法，不但可以有效利用无线信道的单向广播特性，还可以在一次迭代过程中使多个节点完成数据平均，因此具有更优越的性能。但是目前国际上的广播Gossip算法，或者无法收敛于初始状态的均值，或者无法证明其收敛性。针对这些问题，本项目将在国际上首次提出在数学上可证明共识收敛于均值的广播Gossip算法；并首次在广播Gossip算法中提出加扰参数的上确界和最优化；首次分析广Gossip聊算法在信道干扰条件下的收敛性能以及在量化误差环境下的收敛精度性能。

Gossip算法由于其不需要特定的路由即可完成节点间的信息交换，所以特别适合于分布式共识信号处理，并被广泛地应用于无线传感器网络的分布式同步、分布式负载均衡和分布式参数估计等领域。目前国际上提出的各种Gossip算法，存在着收敛速度慢或无法收敛到初始状态均值等各种问题。针对这一现状，本项目提出了一系列利用无线信道广播特性来加速收敛的广播Gossip算法。并且本项目从数学上证明了所提出的各种算法能够保证收敛性，最重要的是其中的UBGA算法能够证明收敛到初始状态均值，这也是国际上所提出的第一个能证明收敛到平均共识的广播Gossip算法。针对新提出的广播Gossip算法需要节点获知其出度信息才能保证收敛到初始状态均值的实现问题，这一条件在工程中通常是很难保证的，因此本项目还提出了基于侦听的Gossip算法，该算法具有和广播Gossip算法相似的收敛速度，但更容易工程实现。此外，本项目针对无线信道易受到干扰、无线传感器节点可能移动和无线信道带宽受限等问题，分析了在移动和非理想信道条件下Gossip算法的收敛性和收敛误差。最后，本课题还开展了Gossip算法在分布式定位和分布式压缩感知等方面的研究。本项目的研究成果填补了国际上的研究空白，具有重要的理论意义和实用价值。