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