基于Gossip算法的分布式平均共识问题研究

摘要

在无线传感器网络中,平均共识问题是一类十分重要的问题。平均共识问题的目标是使得网络中所有节点达到初始状态均值的一致状态,它可以被广泛的用于参数估计、定位、同步等方面。对于平均共识问题,如果按照传统的方法将网络中的数据直接汇聚到某个节点中,将造成大量的路由开销和瓶颈效应。而Gossip算法利用节点的本地信息处理能力,仅通过随机的唤醒网络中的节点并与邻居节点进行数据交换的方式使网络达到平均共识状态,从而避免了网络中路由的开销和瓶颈效应。由于Gossip算法在分布式信息处理方面的优良性质,受到了学术界的广泛关注。
　　本文首先建立了平均共识问题和网络拓扑结构的一般模型,然后在该模型下对几种典型的Gossip算法的收敛性和收敛速度进行了分析。单播Gossip算法能够收敛于网络的初始均值,但是收敛速度较慢;而广播Gossip算法虽然收敛速度较快,但是现有的广播Gossip算法无法收敛于初始状态的均值或者根本就无法证明其收敛性。为了弥补广播Gossip算法的不足,本文提出了一种基于侦听的广播Gossip算法,它既继承了广播Gossip算法中利用无线信道天然广播特性的主要思想,又采用了单播Gossip算法中随机选择邻居节点的更新模式。接着,利用遍历系数的方法证明了基于侦听的广播Gossip算法的收敛性。虽然由于算法唤醒概率与具体网络结构有关,并没有得到基于侦听的广播Gossip算法收敛速度的数学表达式,但是通过仿真比较了该算法与几种现有广播Gossip算法的性能。仿真结果表明,在几何随机图中,基于侦听的广播Gossip算法能够收敛于网络的初始均值,并且具有最快的归一化均方误差曲线下降速度。随着网络中节点数的增加,基于侦听的广播Gossip算法的收敛速度有所降低,但是与其他算法相比仍然具有优势,考虑到网络中的节点数目以及网络拓扑结构的未知性,算法的整体性能也值得肯定。在存在链路丢失的情况下,算法的收敛性依然能够得到保障,并且从仿真结果来看算法的收敛速度也并未受到较大影响。最后介绍了在ARM11平台上对基于侦听的广播Gossip算法的实现方法,并且对算法的实际性能进行了测试。

目录

封面

中文摘要

英文摘要

目录

第1章 绪 论

1.1 课题背景及研究的目的和意义

1.2国内外在该方向的研究现状及分析

1.3 基于Gossip算法的平均共识问题应用

1.4本文的主要工作和内容安排

第2章 Gossip算法的基本理论

2.1分布式平均共识问题的数学模型

2.2网络结构的数学模型

2.3经典单播Gossip算法

2.4经典广播Gossip算法

2.5改进的广播Gossip算法

2.6本章小结

第3章 基于侦听的广播Gossip算法

3.1基于侦听的广播Gossip算法

3.2基于侦听的广播Gossip算法的收敛性

3.3本章小结

第4章 基于侦听的广播Gossip算法的仿真与实现

4.1基于侦听的广播Gossip算法性能仿真

4.2基于侦听的广播Gossip算法的实现与测试

4.3 本章小结

结论

参考文献

攻读硕士学位期间发表的论文及其它成果

声明

致谢