基于侦听的Gossip平均共识技术的无线通信方法

摘要

基于侦听的Gossip平均共识技术的无线通信方法，涉及无线通信领域。它是为了在复杂的网络拓扑结构情况下仅通过本地节点和一跳邻居节点之间的信息交换使网络节点达到平均共识状态。其方法为：对包含有N个节点的无线传感器网络中所有节点进行初始化；选择Gossip迭代次数；然后逐次进行Gossip迭代，每次迭代后，无线传感器网络中的每个节点都将本地的补偿变量和本地状态值之和作为对于状态值均值的估计值。当完成迭代后，该无线传感器网络中的节点达到平均共识状态。本发明适用于无线通信。

说明书

技术领域

本发明涉及无线通信领域，具体涉及一种基于侦听的Gossip平均共识技术的通信方 法。

背景技术

随着信息技术的发展，通信的应用领域得到了极大的扩展，深入人们生活的各个方面。 因特网、电话网以及有线电视网等通信网络更是成为了人们生活不可缺少的一部分。但是， 值得注意的是并非所有网络都用于实时的信息交换，其中最典型的就是无线传感器网络， 这一类网络主要是用来进行数据采集、监测等工作。不可否认的是，对于无线传感器网络 也需要有一定的信息交换能力，一般无线传感器网络都是由多个节点组成，每个节点监测 到的都只是整个环境范围内的一部分。所以我们需要使传感器节点进行数据交换甚至于一 些简单的线性计算来获得我们想到的整体情况。例如，在一个城市中分布了许多温度传感 器，它们相互独立地测量城市中的温度，由于风向、建筑等条件的影响这些独立的测量值 往往没有那么重要。我们所关心的是整个地区的平均温度，这就需要通过这些传感器节点 之间的信息交换来完成。这个问题相对于现代的通信技术水平来说并困难，二十世纪以来， 人们已经实现了高速、远距离的信息传输。但是无线传感器网络有它的特殊性，因为这一 类网络存在的根本目的并不是为了通信，而是为了对我们所关心的参数进行测量。这就导 致了许多问题，其中最主要的可以分为如下两个方面：

第一个问题是无线传感器网络的建立有很大的随意性，这里所说的随意性包括了两种 含义，第一种含义是地点的随意性，无线传感器网络可能被建立在一片森林中用于监测森 林的湿度等指标也有可能被建立在建筑物中用以监测室内的空气质量，甚至可能被临时的 建立在受灾地区用于各种数据采集和监测，这就导致无线传感器网络无法保证具有固定基 站支持，因为建立一个基站无论从时间成本还是从经济成本来看都是高昂的。随意性的第 二个含义是网络拓扑结构的随意性，在无线传感器网络组网时，传感器节点大多数都是根 据实际的测量需要摆放的，而事先没有经过精心的设计和计算。这样，会导致网络的拓扑 结构有很大的任意性(当然，保证网络拓扑的联通性是对网络结构的最基本的要求)。

第二个问题是无线传感器节点的能力有限。由于成本的限制，传感器节点的能力并不 是很强，节点的存储能力和计算能力都相当有限，所以普通的传感器节点并不足以储存和 处理所有的网络数据。

第三个问题是能耗。由于网络建立的随意性，大多数无线传感器网络主要依靠电池提 供能量而没有持续的供电设施。所以如何能够在耗能尽量少的条件下尽可能准确的得到我 们需要的测量数据也是无线传感器网络的一个重要问题。由于无线传感器网络的特点传统 的路由协议并不是完全适用，因为这些路由协议的设计初衷都是为了实现点对点的通信， 而不强调对网络中的数据进行整合和计算。因此有必要针对无线传感器网络设计用于网络 数据整合和参数估计的路由方法。

根据以上分析，为了更加适用于无线传感器网络，路由方法必须满足几个条件。首先， 路由方法需要对网络的拓扑结构具有适应性并且对网络拓扑结构改变具有鲁棒性。无论是 出于对网络性能需求还是实际的条件限制，这个要求对于临时组网的无线传感器网络来说 非常重要。可以说，适用于任意拓扑结构的路由方法是无线传感器网络组网的基础，而对 网络拓扑结构改变的鲁棒性是对于无线传感器可靠性的保障。此外，由于节点能力的限制 以及能耗问题，无线传感器网络路由方法需要有较低的计算复杂度和空间复杂度，因为这 将直接影响到网络的成本和网络的生存时间。事实上，目前有许多路由方法能够实现无线 传感器网络的数据传输，但是它们的能量消耗问题和复杂度问题直接影响到了它们在无线 传感器网络中的应用。

在无线传感器网络中，分布式平均共识问题是一个具有挑战性的基础性问题。平均共 识指的是网络根据各个网络节点的初始状态通过信息的交换使各个节点最终达到一致状 态的过程。在工程应用中，很多实际问题最终都能够转化成平均共识问题，例如源定位问 题、同步问题、测量问题等，所以有效的解决分布式平均共识问题具有重要的实际应用价 值。随着通信基础理论研究的不断深入，平均共识问题在国际学术界得到了广泛的关注， 对于平均共识问题的研究取得了许多成果。其中，基于Gossip方法的平均共识问题在无 线传感器网络中的应用更是研究的热点。

Gossip方法在1984年由Tsitsiklis等人首次提出，该方法仅利用网络节点的本地信息 与它的邻居节点的信息进行数据交换，解决了分布条件下的平均共识问题。Gossip方法 可以被广泛的用于源定位问题、参数估计问题、卡尔曼滤波等，近年来更是受到了学术界 的广泛关注。

与传统的路由方法不同，Gossip路由方法强调通过节点的本地信息与邻居节点进行 数据交换的方式来进行数据更新，我们把一次数据更新过程称为一次迭代过程。由于在迭 代过程中，只涉及到一跳邻居节点信息和本地信息的交换，所以基于Gossip的网络并不 需要传统路由方法的路由建立过程和维护过程，也没有数据的转发过程，这就大大降低了 网络的能量消耗、延长了网络节点的生存期。同时Gossip方法是一种随机路由方法，避 免了网络中因信道竞争造成的“丢包”和网络阻塞等问题。并且，整个网络中所有的节点 地位对等，没有所谓的“中心节点”，也避免了瓶颈效应的存在。所以Gossip方法是对无 线传感器网络中平均共识问题的良好解决方案。

发明内容

本发明是为了降低无线信号传输过程中的丢包率，以及提高对拓扑结构变化的适应能 力，从而提供一种基于侦听的Gossip平均共识技术的无线通信方法。

基于侦听的Gossip平均共识技术的无线通信方法，它由以下步骤实现：

步骤一、对包含有N个节点的无线传感器网络中所有节点进行初始化，N为正整数；

步骤二、选择Gossip迭代次数；

步骤三、进行第A次Gossip迭代，所述A的初始值为1；每次Gossip迭代的方法为：

在无线传感器网络中任意选择一个节点作为初始唤醒节点，由所述初始唤醒节点发起 Gossip迭代，所述初始唤醒节点在与其相邻的节点中随机选择一个做为唤醒节点，并将 所述初始唤醒节点的状态值和伴随变量值发送该唤醒节点，使无线传感器网络进入Gossip 迭代状态；所述该无线传感器网络中未被唤醒的节点都处在侦听状态；

步骤四、无线传感器网络中的每个节点都将本地的补偿变量和本地状态值之和作为对 于状态值均值的估计值，并判断A的值是否达到步骤二获得的Gossip迭代次数的值，如 果判断结果为否，则令A＝A+1，并返回执行步骤三；如果判断结果为是，则结束Gossip 迭代，完成该无线传感器网络中基于侦听的Gossip平均共识，进而实现无线传感器网络 中所有节点间的无线通信。

步骤三中每个唤醒节点被选中的概率为：

步骤二中选择Gossip迭代次数的方法为：根据具体网络拓扑结构和需求的精度进行 选择。

步骤二中选择Gossip迭代次数的方法为：

根据公式：

$\frac{0.5\log {ϵ}^{-1}}{\log {\lambda }_2{\left(W\right)}^{-1}}\le T_{\mathrm{ave}}(ϵ,P)\le \frac{3\log {ϵ}^{-1}}{\log {\lambda }_2{\left(W\right)}^{-1}}$

选择Gossip迭代次数；

式中：ε表示归一化最大误差值，λ₂(●)表示随机矩阵中的第二大特征值；Φ表示无 线传感器网络拓扑图的邻接矩阵；

W的取值为：

$W=I-\frac{1}{2N}\mathrm{diag}\left\{\Phi 1\right\}+\frac{1}{2N}\Phi .$

每次Gossip迭代的过程中：

对于初始唤醒节点i，将该节点的状态值、伴随变量值、补偿变量值发送给被选中的 节点j；然后将初始唤醒节点i的伴随变量置为0；

用数学形式表示成如下形式：

a_i(t+1)＝a_i(t)

c_i(t+1)＝0

b_i(t+1)＝b_i(t)

式中：α_i(t)表示节点i在t时刻的状态值，c_i(t)表示节点i在t时刻的伴随变量，b_i(t)表 示节点i在t时刻的补偿变量；被选中的节点j将在下一个时隙被唤醒。

每次Gossip迭代的过程中：

对于被选中的节点j，根据收到的信息进行更新：

$a_j(t+1)=\frac{a_j\left(t\right)+a_i\left(t\right)}{2}$

$c_j(t+1)=c_j\left(t\right)+\frac{1}{N}\left(\frac{a_j\left(t\right)-a_i\left(t\right)}{2}\right)+c_i\left(t\right)$

b_j(t+1)＝c_j(t+1)

其中，被选中的节点j将在下一个时隙被唤醒。

被唤醒节点j的其他邻居节点能够侦听到唤醒节点的信息，并且根据侦听到的信息更 新本地节点的状态：对于

m∈N_i，m≠j

有：

$a_m(t+1)=\frac{a_m\left(t\right)+a_i\left(t\right)}{2}$

$c_m(t+1)=c_m\left(t\right)+\frac{1}{N}\left(\frac{a_m\left(t\right)-a_i\left(t\right)}{2}\right)$

b_m(t+1)＝b_i(t)

无线传感器网络中未被唤醒的节点将保持原有状态不变：对于

$k\notin N_i,$k≠i

有：

a_k(t+1)＝a_k(t)

c_k(t+1)＝c_k(t)

b_k(t+1)＝b_k(t)

本发明基于侦听的Gossip平均共识技术，实现无线传感器网络中所有节点间的无线 通信，该方法能够使得无线传感器网络中所有的节点达到平均共识状态，与传统的平均共 识方法相比，本发明的无线信号传输过程中的丢包率低，对拓扑结构变化的适应能力强。

附图说明

图1经典单播Gossip技术的无线信号传输原理示意图；图2是存在丢包情况的单播 Gossip技术的无线信号传输原理示意图；图3是经典广播Gossip技术的无线信号传输原 理示意图；图4是本发明的基于侦听的Gossip技术的无线信号传输原理示意图；图5是 本发明的基于侦听的Gossip平均共识技术的无线信号传输方法的流程示意图；图6是具 体实施方式一中的网络拓扑结构仿真示意图；图7是具体实施方式一中的BGA-1方法节 点状态变化仿真示意图；图8是具体实施方式一中的BGA-2方法节点状态变化仿真示意 图；图9是具体实施方式一中的本发明节点状态变化仿真示意图。

具体实施方式

具体实施方式一、结合图1说明本具体实施方式，基于侦听的Gossip平均共识技术 的无线通信方法，它由以下步骤实现：

步骤一、对包含有N个节点的无线传感器网络中所有节点进行初始化，N为正整数；

步骤二、选择Gossip迭代次数；

步骤三、进行第A次Gossip迭代，所述A的初始值为1；每次Gossip迭代的方法为： 在无线传感器网络中任意选择一个节点作为初始唤醒节点，由所述初始唤醒节点发起 Gossip迭代，所述初始唤醒节点在与其相邻的节点中随机选择一个做为唤醒节点，并将 所述初始唤醒节点的状态值和伴随变量值发送该唤醒节点，使无线传感器网络进入Gossip 迭代状态；所述该无线传感器网络中未被唤醒的节点都处在侦听状态；

步骤四、无线传感器网络中的每个节点都将本地的补偿变量和本地状态值之和作为对 于状态值均值的估计值，并判断A的值是否达到步骤二获得的Gossip迭代次数的值，如 果判断结果为否，则令A＝A+1，并返回执行步骤三；如果判断结果为是，则结束Gossip 迭代，完成该无线传感器网络中基于侦听的Gossip平均共识，进而实现无线传感器网络 中所有节点间的无线通信。

工作原理：本发明利用了无线信号的天然广播特性，在传统的单播Gossip方法的基 础上使节点通过侦听的方式获取相邻节点的部分信息从而加快状态值的收敛速度，同时通 过节点中的伴随变量值来补偿由于侦听方式所带来的网络均值漂移的问题，最后通过一次 洪泛过程使得所有的节点达到平均共识状态。

为了便于比较，以下首先介绍了经典单播Gossip方法和经典广播Gossip方法并且简 要的分析了它们各自的优缺点，在此基础上，提出了一种基于侦听的Gossip方法，有效 的解决了经典Gossip方法之中存在的问题。

如图1所示是经典单播Gossip方法的示意图，在该方法中，每个时隙都随机地唤醒 网络中的一个节点，被唤醒的节点随机地选择一个邻居节点并与之进行数据交换。在一个 有N个传感器节点的网络中，设a_k(t)表示网络中任意节点k在第t个时隙的状态，并把网 络中所有节点的状态用一个N维向量a(t)来表示。在第t个时隙内，假设i节点被唤醒，并 且与它的邻居节点j进行数据交换，如图1所示。网络中的状态变化可以表示成：

为了便于研究，我们把(11)式改写成向量的形式：

a(t+1)＝W(t)a(t)                            (2)

其中W(t)是一个N×N的随机矩阵，它主要取决于t时隙内被唤醒的节点，这样就得 到了经典单播Gossip方法的一般数学模型。对于随机矩阵W(t)有：

$W\left(t\right)·\overrightarrow{1}=\overrightarrow{1}---\left(3\right)$

${\overrightarrow{1}}^T·W\left(t\right)={\overrightarrow{1}}^T---\left(4\right)$

其中是一个N维全1列向量。从式(4)中可以看出，如果网络节点经过若干次迭 代之后达到一致状态，那么，在此之后的更新中，网络将保持这个状态不变。从式(5) 中可以看出经过单播Gossip过程之后，网络中各个节点值得总和保持不变。也就是说， 只要网络中各个节点的值达到一致的状态，那么这个一致状态将会等于网络初值的均值， 这个结论也可以从节点状态的更新过程中得到验证。

从方法模型可以看出，经典单播Gossip方法的实现十分简单，收敛性也得到了理论 证明。但是，经典单播Gossip方法的收敛速度过慢，严重影响了该方法的实际应用，除 了收敛速度的问题，经典的单播Gossip方法还存在另外一个问题。在实际的通信中，难 免会存在数据包丢失的情况，这将会导致单播Gossip方法收敛均值的改变。如图2所示， 可以看出，如果在某一次迭代过程中，i节点没有收到j节点的信息，则方法的收敛均值 将发生改变，改变量为：

$\Delta =\frac{a_i-a_j}{2N}---\left(5\right)$

所以，如果此刻节点i的值a_i与节点j的值a_j相差很大时，最终的收敛均值会发生很 大的改变。

由于单播Gossip方法存在的局限性，人们一直在寻找新的Gossip方法来适应实际应 用的需求。经过分析我们惊喜地发现，无线信号具有天然的广播特性，也就是说，当某个 节点发出一个无线信号时，在它通信范围内的所有节点都能收到这个信号。从方法收敛速 度的角度来看，我们希望每个节点都尽可能快地获取其它节点的信息，而单播Gossip方 法中，在被唤醒节点发射无线信号时，只有被选中的节点处理了这个信息，其它的邻居节 点并没有处理这个信息。为了使被唤醒节点的所有邻居节点都能有效的利用接收到的信 息，人们提出了基于广播的Gossip方法。

经典广播Gossip方法如图3所示，在每一个时隙内随机的唤醒网络中的一个节点， 节点经过一次信号发射，将本节点的值广播到所有邻居节点，邻居节点更新它们的状态值。 在一个有N个传感器节点的网络中，设a_k(t)表示网络中任意节点k在第t个时隙的状态， 并把网络中所有节点的状态用一个N维向量a(t)来表示。在第t个时隙内，假设i节点被 唤醒，该方法可以表示成：

为了分析方便用矩阵的形式表示：

a(t+1)＝W(t)·a(t)                           (7)

同单播Gossip方法一样，W(t)是一个N×N的随机矩阵，它主要取决于t时隙内被唤醒的 节点，W(t)可以表示为：

从w(t)的表达式可以的出：

$W\left(t\right)·\overrightarrow{1}=\overrightarrow{1}---\left(9\right)$

${\overrightarrow{1}}^T·W\left(t\right)\ne {\overrightarrow{1}}^T---\left(10\right)$

从式(11)中可以发现，经典的广播Gossip方法不能保证网络中所有节点状态值的 和不变。因此，也不能保证该方法收敛于原始的均值。也就是说，当对于收敛均值的精度 要求不高，或者并不关心收敛于何值时(例如在同步问题中)，经典的广播Gossip方法才是 可用的，这就限制了广播Gossip方法的使用范围，但是广播Gossip方法的优点在于收敛 速度要明显快于单播Gossip方法。

由以上分析可以看出造成广播Gossip方法不收敛于均值的原因是：广播Gossip方法 在迭代的过程中并不能保持网络中节点值的和不变，而网络中的节点中又没 有采取相应的补偿措施。所以，迭代之后的收敛值于节点的唤醒次序有关，造成了网络均 值的随机性。为了解决广播Gossip方法不收敛于均值的问题，本专利在每个节点中引入 一个伴随变量c_i(t)，通过这两个伴随变量来补偿网络中节点和的漂移，至此每个节点中将 保存和更新两个值：节点状态值和伴随变量。对于伴随变量需要满足：

$\underset{i=1}{\overset{N}{\Sigma }}[a_i\left(t\right)+f\left(c_i\left(t\right)\right)]=f^{\prime }\left(\underset{i=1}{\overset{N}{\Sigma }}{a}_i\left(0\right)\right)---\left(11\right)$

其中f(●)、f′(●)是两个已知函数。

只要在每次迭代过程中使得(12)式成立，就能保证网络中有足够的信息来恢复网络 所有节点初值的和。为了同时具有经典广播Gossip方法的快速收敛性和单播Gossip方法 的优点，本发明提出了一种基于侦听模式的Gossip方法。如图4所示为本方法的原理示 意图，被唤醒的节点一个时隙内随机地选择一个邻居节点并且将它的状态值以及伴随变量 给被选择的节点。网络中其它节点处于侦听状态，能够侦听到邻居节点发出的信号，并且 根据侦听到的部分数据更新本地的状态值和伴随变量，这样不仅能够加快Gossip过程的 收敛速度同时还能够通过伴随变量的补偿作用保持网络均值不发生改变。

本发明的具体步骤详细为：

步骤一：初始化节点。在本方法中，每个节点中除了保存有当前自身状态值a_i(t)之 外，还保存有一个伴随变量c_i(t)和一个补偿变量b_i(t)。其中a_i(t)表示节点i在t时刻的状 态值，c_i(t)表示节点i在t时刻的伴随变量，b_i(t)表示节点i在t时刻的补偿变量。初始时， 每个节点的伴随变量和补偿变量都为零，即：

c_i(0)＝0

b_i(0)＝0

步骤二：根据具体网络拓扑结构和需求的精度选择迭代次数。可以根据经验公式

$\frac{0.5\log {ϵ}^{-1}}{\log {\lambda }_2{\left(W\right)}^{-1}}\le T_{\mathrm{ave}}(ϵ,P)\le \frac{3\log {ϵ}^{-1}}{\log {\lambda }_2{\left(W\right)}^{-1}}$

其中ε表示归一化最大误差值，λ₂(●)表示矩阵的第二大特征值。

$W=I-\frac{1}{2N}\mathrm{diag}\left\{\Phi 1\right\}+\frac{1}{2N}\Phi$

Φ表示拓扑图的邻接矩阵。

步骤三：Gossip迭代过程。在网络中任意选择一个节点作为初始唤醒节点，由该节 点发起Gossip迭代过程，该节点在它的邻居节点中随机的选择一个并且将它的状态值和 伴随变量值发送给被选中的节点，网络进入Gossip迭代状态。网络中未被唤醒中的节点 都处在侦听状态，由于无线信号天然的广播特性，它们能够侦听到周围邻居节点之间的数 据流，假设用i表示t时刻被唤醒的节点，用N_i表示它的邻居节点集合，j表示t时刻被节 点i选中的邻居节点，每个邻居节点被选中的概率为Gossip迭 代过程可以表示成如下形式：

1、对于被唤醒的节点i，并且将本节点的状态值、伴随变量值、补偿变量值发送给 被选中的节点j。然后将本节点的伴随变量置为0。用数学形式表示成如下形式

a_i(t+1)＝a_i(t)

c_i(t+1)＝0

b_i(t+1)＝b_i(t)

下一个时隙中，被唤醒的节点将处于侦听状态。

2、对于被选中的节点j，根据收到的信息进行更新：

$a_j(t+1)=\frac{a_j\left(t\right)+a_i\left(t\right)}{2}$

$c_j(t+1)=c_j\left(t\right)+\frac{1}{N}\left(\frac{a_j\left(t\right)-a_i\left(t\right)}{2}\right)+c_i\left(t\right)$

b_j(t+1)＝c_j(t+1)

其中N表示网络中的节点总数。被选中的节点将在下一个时隙被唤醒。

3、被唤醒节点的其他邻居节点能够侦听到唤醒节点的信息，并且根据侦听到的信息 更新本地节点的状态。对于

m∈N_i，m≠j

$a_m(t+1)=\frac{a_m\left(t\right)+a_i\left(t\right)}{2}$

$c_m(t+1)=c_m\left(t\right)+\frac{1}{N}\left(\frac{a_m\left(t\right)-a_i\left(t\right)}{2}\right)$

b_m(t+1)＝b_i(t)

4、网络中的其他节点将保持原有状态不变：对于k≠i

a_k(t+1)＝a_k(t)

c_k(t+1)＝c_k(t)

b_k(t+1)＝b_k(t)

步骤四、每个节点都将本地的补偿变量和本地状态值之和作为对于状态值均值的估 计。当迭代次数达到预设的最大迭代次数时，结束迭代过程。

以下通过具体的仿真试验验证本发明的效果：

如图6所示为网络拓扑结构图，该拓扑是一个节点数为100个的几何随机图，图7-9 为在该拓扑结构中几种Gossip方法的节点状态变化曲线。从图7中可以看到BGA-1方法 的收敛速度较快，但是该方法的收敛值是一个随机值并不确定的等于网络的初始均值(图 中红线所示)。从图8可以看出BGA-2方法能够收敛于网络的初始均值，但是收敛速度较 慢。图9为本方法的节点状态变化曲线，本方法不仅收敛速度较BGA-2方法更快，而且 能够收敛于网络的初始均值，这使得本方法有更强的实际应用价值。