英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
The Impact of Mobility on Grossip Algorithms
Anand Dilip Sarwate, Member, IEEE, and Alexandros G. Dimakis, Member, IEEE
移动性对流言算法的影响
摘要—本文研究了节点移动性对网络中平均流言算法收敛时间的影响。结果表明，少量的完全移动节点可以显著减少收敛时间。并开发了一种通过根据节点的移动性模式合并节点来得出收敛时间下限的方法。利用该方法证明了当节点在同一方向上具有一维迁移率时，收敛时间最多可提高一个常数。利用马尔可夫链理论中的技巧得到了收敛时间的上界，表明只要迁移路径有明显的重叠，简单的迁移模型就可以显著地加速流言的产生。仿真结果表明，不同的移动性模式对分布式算法的收敛性有显著的影响。
索引词-共识协议，分布式算法，分布式平均，分布式处理，流言协议，马尔可夫链，移动性，对等网络，无线传感器网络。
- 引言
流言算法是用于在网络中传播和处理信息的分布式消息传递方案[1]。平均一致性[2]–[4]和平均流言算法[5]，[6]是一个重要的方案特例，它们能够以稳健和分布式的方式计算数据的线性函数。这种方案在分布式估计、定位和优化[7]-[9]以及传感器测量的压缩感知和现场估计[11]中有着广泛的应用。在本文中，我们研究计算线性函数的流言算法，而不讨论诸如信息传播之类的相关问题（参见，例如，[12]和[13]以及其中的参考文献）。
流言算法由于其分布性和健壮性，自然适合于无线自组织和传感器网络应用。最近，无线通信的广播特性被用来改善收敛性[10]，[14]，[15]。无线网络的另一个关键特征是节点移动性。据我们所知，移动性对流言算法的影响尚未得到充分研究。在本文中，我们尝试分析移动性如何（或能否）帮助流言算法的收敛。对于随机几何图（RGG）或网格（大型无线自组织网络和传感器网络的流行模型拓扑）中的固定节点，标准流言在通信需求方面是极其浪费的；甚至网格上优化的标准流言算法也收敛得非常慢，需要消息[6]，[16] 在精度ε范围内计算平均值。请注意，这与要求每个节点将其估算信息泛洪到所有其他节点的顺序相同。在生成树上求平均数并将平均数返回到所有节点的明显解决方案只需要消息。显然，在动态自组织网络中构造和维护生成树会带来显着的开销和复杂性，但是二次消息是为容错而付出的高昂代价。在这种情况下，什么样的移动性模式是有益的，并且需要多少个移动节点来提高融合速度？我们的结果表明，在某些情况下，某些类型的移动性可以显着加速收敛。这项研究是了解移动性如何影响迭代消息传递方案的收敛性的第一步，至少对于成对平均的特殊案例而言。
- 主要结论
我们的第一个结果是，如果节点具有完全的移动性，而其他节点固定在网格中，则收敛时间将降至。因此，即使是一小部分的移动节点也可以更改收敛所需的消息顺序。特别是如果节点恒定且具有完全移动性，则收敛时间将下降至完全连通图的数量级。
我们的第二个结果是某些移动方式可能没有好处。我们证明，即使网络的所有节点在同一方向（例如水平方向）上都具有一维移动性，这也不会在收敛时间内产生任何好处。从直观上讲，这是因为信息仍必须沿另一个方向（例如垂直方向）扩散。最后，我们证实了具有随机选择方向的一维移动性与完全移动性一样好。
为了获得这些结果，我们开发了一种通过合并具有相似移动性区域的节点来推论流言算法与移动节点的收敛时间下界的新方法。该方法基于马尔可夫链收敛时间的特征，该函数用一种称为Dirichlet形式的函数来实现的[17]。上界是使用所谓的Poincareacute;不等式[18]和相关规范路径方法[19]推导的；该技术以前也曾被用于研究流言算法[20]。这个技术相当通用。我们解释了对网格网络和RGG的应用，但是这些方法可以应用于其他拓扑。
-
- 网络模型及初步研究
- 时间模型
我们使用异步时间模型[6]，[21]，它与无线网络的分布式特性非常匹配。我们假设每个传感器都有一个独立的时钟，其“滴答”分布为速率lambda;Poisson过程。我们的分析是基于根据速率lambda;Poisson过程，用等效的单个虚拟全局时钟滴答数来测量时间。时间模型的精确分析见[6]。我们将两个连续时钟周期之间的时间称为一个时隙。这种建模假设导致了一个离散时间系统，其中在每个时隙中均匀选择一个传感器。
在本文中，我们将分析所需消息的数量，而不必担心延迟。因此，我们可以相对于通信时间调整时隙的长度，从而在每个时隙中网络中只有一个分组存在的可能性很高。注意，这个假设只是为了分析方便。在实际实现中，网络中可能会同时存在多个数据包，但相关的问题不在本文讨论范围之内。
- 网络和移动模型
假设我们有一批n个探员。在第一个时隙中，每个节点i从一个初始位置开始。我们将用表示初始值的向量x（0）。我们算法的目标是让每个节点估计平均值
为了实现此目标，节点之间相互传递消息以传达其估计值。我们假设此通信始终成功，并且消息是实数；消息量化在流言和共识算法中的作用是一个活跃的研究领域[22] – [29]。节点可以在一个区域 内行动. 我们可以将 认成顶点集 和边集 的图 。节点在不同的地点。 和 可以传递消息(但不包括v=vi或，v，vi没有通讯路径的情况)。另一个例子是 视为单元正方，并且如果允许 和 通讯，则 比要小 . 对于 中节点位置, 可以与其他节点通讯。如果 在 . 在本文中，我们将使用两个网络来说明我们的结果。并且，我们描述的方法可以用具有双向通信的通用网络。
- 我们的第一个例子是 离散点阵。节点位置 是{0,2，，， -1}2 and两点之间路径 和 ，如果 1)mod 并且j,=(j 1)mod.，每个位置有一个节点，在时间为0时它们各自占用不同位置。对于位置，我们称之为行坐标和列坐标。
- 第二个例子是单位面上的RGG模型。通过将单元正方形边缘“粘合”在一起，由形成单元面。节点位置在[0,1]2中。如果座席之间在网络上的距离小于 =其中cgt;=10，可以确保随后讨论的一些有用的规律性[20]。同样，对于位于(i,j)的节点，我们将其称i为行坐标和y为列坐标。
基于节点的移动性下，在每个时间步长，节点都会根据固定的概率分布移动到选定的新位置。因此，座席位置的顺序是独立的，并根据分布相同地分布（i.i.d.）我们将分布的集合称为基于节点的移动性模式。本文的理论结果是基于节点的移动性。尤其我们研究了一些简单的移动性示例。
- 基于节点的移动性的一个简单示例是完全统一的移动性。在此模型中，是的均一分布。这对应于每个节点在同一时间可能处于任何位置的情况。这类似于Grossglauser和Tse提出的模型[30]。我们还将考虑在静态网络中添加了完全移动的节点。
- 在水平移动性模型中，每个节点每次都统一选择一个新的水平位置。对于平面，它从中统一选择一个新的列坐标。对于RGG，它从[0,1]中统一选择一个新的水平坐标。
- 在双向模型中，每个节点始终选择是否会水平或垂直移动。在每个时间步长，水平节点均匀地选择一个新的水平坐标，而垂直节点均匀地选择一个新的垂直坐标。
- 在平面的局部模型中，最初从位置开始的节点(i,j)会在以(2m 1)2大小为平方的平方中统一选择一个新位置。也就是说，水平坐标均匀分布在中，垂直坐标均匀地分布在中。一旦选择了新坐标，节点即可与网络中相同或相邻位置的其他节点通信。
我们所有移动性模型中的关键是，假设在每个时隙中，移动节点的位置都是独立来选择的，类似于Grossglauser和Tse [30]。 目前流行的移动性模型，如随机行走模型[31]，[32]，随机航点模型[33]和随机方向模型[34]，都具有时间依赖性。但是，如果一个时隙的持续时间与流动性模型的混合时间相当或更长，则节点的位置将几乎是独立的。 如果延迟不是问题，我们总是可以将时隙的持续时间设置为具有该属性，并且在仿真中我们表明，如果我们不允许混合移动性模型，那么移动性就没有那么有用。我们相信我们的分析结果可以用来约束这些更现实的模型，但我们将此留给以后的工作。
- 算法及主要结果
- 算法
我们将考虑的流言算法是Boyd等人的标准最近邻留言算法的简单扩展。[6] 这就自然地包括了移动性模型。在每个时隙中，节点独立地移动到新位置。随机选择一个节点，根据该图选择其邻居之一，然后与该邻居进行计算。更准确地说，每次发生以下事件。
1）每个节点根据移动性分布选择一个新位置。
2）随机选择一个节点并选择一个邻居从集合。例如，如果是图，则
3）节点i，j交换值并且更新他们的估计。
由于算法是随机的，因此我们有兴趣在其运行时间上提供概率边界。 给定，平均时间[6]是向量有概率接近归一化真实均值的最早时间比更好
其中表示欧几里得范数。 注意，这本质上是测量概率收敛速度。 Denantes等人的分析 [36]表明，间隙的边界产生了消失误差的渐近确定性速率。界限既可以用来限制概率的收敛速度，也可以用来证明平均误差几乎可以肯定地渐近指数递减。
- 主要结果
我们的主要结果表明了移动性在加速流言算法收敛方面的优势（或缺乏优势）。对于没有移动性的网格或环型网络，平均时间是。 对于RGG上的网络，其连接半径如前所述进行选择，平均时间为
- 对于RGG和平面上的水平移动性，与节点完全不移动的情况相比，平均时间最多缩短恒定时间
- 对于双向移动，每个节点最初选择是垂直移动还是水平移动，收敛时间在完全移动的恒定因子之内
- 对于具有完全移动性的网络上的非移动节点，收敛时间为
- 对于局部移动模型，每个节点以正方形移动
- 收敛时间的上界和下界
A. 收敛分析
在算法的每个步骤中，节点更新其平均值的估计值 . 让 表示当时的平均估计。对节点 和 并定义矩阵
向量ei在第i个坐标中为1，在其他位置为0。 如果该(i,j)对在时间t平均，则新的平均向量为
移动性和节点选择中的随机性导致矩阵上的概率分布。由于移动性和选择是i.i.d. 随着时间的推移，我们可以将更新写为
是i.i.d.随机矩阵。用表示该随机矩阵的期望值。不难看出这是一个（对称）随机矩阵，因此对应于马尔可夫链。假设Pij是在算法的步骤2中选择了节点i并在其邻居集中选择了节点j的概率。 然后，很明显，并且
博伊德等人的开创性工作[6] 证明了随机流言算法的收敛时间是由Markov链的混合时间决定的。数学上，我们的问题是如何分析新特征（在这种情况下是移动性）引起的新图的混乱时间，然后将其与没有移动性的旧图进行比较。对于具有转移矩阵的马尔可夫链，收敛性平稳分布的速率由的第二大特征值给出。注意，最大特征值是1。将弛豫时间定义为间隙的倒数
以下定理在[6]中（另请参见[1]）。
定理1（收敛）：
如果是对称的并且n足够大，则
B. 下界
在本节中，我们提供了一种在基于智能体的移动性下构造成对流言算法的收敛时间下限的一般方法。主要的观点是对图中的一组顶点进行分区，并合并所有在分区的同一元素中支持移动性的节点。这引起了与流言算法的马尔可夫链上的变换。通过使用马尔可夫链弛豫时间的极值表征，我们可以定义下限将原始流言算法中的松弛时间由马尔可夫链的松弛时间决定。剩下的唯一问题是选择一个分区具有严格的下限，这必须通过检查来完成。我们可以使用这种技术来证明水平移动性不能改善网络或RGG的流言收敛性。
定理2：令是位置集合的任何分区，设为由所有移动性被限制的节点的集合形成的马尔科夫链转化的矩阵。然后
证明：我们从开始。让成为一个分区。基于节点的移动模式，让
成为行动受限的节点的集合。 我们可以在对应于流言算法的马尔可夫链的状态集上创建一个映射
该地图F包括了移动性受限的节点，并使其他节点保持不变。 让表示的F图像。对于具有转移概率和平稳分布的Markov链，我们可以定义具有转移的Markov链
这是从函数中引出的链[17，Ch.4，p. 37]。 该链的静态分布为
我们可以用Dirichlet形式表示Markov链的弛豫时间[17]。 给定马尔可夫链状态空间上具有转移矩阵和平稳分布的实值函数，Dirichlet形式为
这个弛豫时间由给出：
以下收缩原理表明，诱导链至少与原始链相同。 此结果在[17，Ch.4，p.37]，这里我们提供一个简短的证明。
声明1：让M成为有限状态空间上的马尔可夫链，并使成为任意映射。 然后，链的松弛时间由下限引起的由（3）式给出的过渡矩阵限制了原始链的松弛时间
(5)
我们在（4）中使用松弛时间的极值性质。 对于由给出的诱导链，让（4）中的极值达到最高。我们可以创建一个从到下界的函数。让每个k设置g(i)=
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[240108]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
