人口普查：移动自组网的快速、可扩展和强大数据聚合协议.

1介绍批准公开发行：无限制发行Census：在MANN中实现快速、可扩展和强大的数据聚合V. Kulathumani， A. Arora†2，M. SridharanB.2，K. Parker§2，and M.1西弗吉尼亚大学计算机科学系，西弗吉尼亚州摩根敦26505200The Samraksh Company，Dublin OH 430172018年10月4日，摘要本文介绍了人口普查，协议的数据聚合和统计计数在MANNETWORK。普查通过使用有偏随机游走在网络中循环一组令牌来操作，使得每个节点被至少一个令牌访问。该协议是无结构的，以避免在节点移动性的存在下用于维持结构的高消息传递开销。它偏向令牌的随机行走，以实现快速覆盖时间;该偏差涉及短但多跳的梯度，将令牌引导到迄今为止未访问的节点。因此，普查实现了O（N/k）的覆盖时间和O（Nlog（N）/k）的消息开销，其中N是网络中节点的数量，k是令牌的数量。值得注意的是，它具有可扩展性和鲁棒性，我们通过在不同网络密度和移动模型下的100到4000个节点的网络中进行模拟来证明这一点。关键词：随机游走，统计聚集，gossip，局部梯度1介绍本文介绍了人口普查，一个快速，可扩展和强大的数据聚合协议在移动自组网。Census是一种无结构的协议，它依赖于有偏随机游走来实现聚合。该协议通过使用偏置随机游走循环一个或多个令牌的集合来操作，以这样的方式，Kulathumani@mail.wvu.edu†anish. samraksh.comsamraksh.com§kenneth.parker@samraksh.comfjmanakagawa@mix.wvu.edu电子邮件联系人是vinod. kulathumani@mail.wvu.edu。这项工作得到了美国国防高级研究计划局（DARPA）合同FA 8750 -12-C-0278的部分支持。本文中包含的观点，意见和/或发现是作者的观点，不应被解释为代表国防部或美国的官方观点或政策。政府的arXiv：1409.7368v2 [cs.NI] 2015年9月1介绍批准公开发行：无限制发行网络被至少一个令牌访问。当节点获得对令牌的独占访问权时，我们说节点被令牌访问;节点可以使用访问周期将节点特定的信息添加请注意，单独访问所有节点的概念与整个网络上的令牌传播[6，23]不同，其中每个节点只需听到至少一个令牌就足够了，而不是独占访问令牌。存在用于全节点访问服务的许多应用，诸如投票、计算聚集（即，最大值、最小值或平均值），统计计数（即，估计满足状态谓词的节点的比例），以及计算网络中数据的经验分布[30]。 示例应用场景包括计算平均传感器测量值，计算军事网络中的营和弹药，以及计算车辆网络中的总流量密度。在具有稳定链路的静态网络中，可以通过遍历固定路由结构（如树或网络骨干）来实现数据聚合[26，25，17，18]。然而，在移动网络和具有频繁链路变化的网络中，拓扑驱动的结构很可能是不稳定的，并且引起用于维护的高通信开销。在最近的一篇论文中，我们分析了为什么像OLSR [19]这样的MANNETWORK路由协议无法扩展到100-150个节点以上，就扩展墙而言[21]。首先，随着网络规模的增加，路径更有可能发生故障-随着网络规模N的增加，路径连接间隔下降为O（N）。其次，即使节点速度的微小变化也会显著增加该路径的故障率和不稳定性。最后，为了成功地用于路由，需要比它们断裂的速率快得多地修复断裂的路径，并且这涉及用于发现断裂的路径并且然后修复这些路径的快速链路估计，这两者都引起高的消息开销。因此，与静态网络的情况相比，普查，利用随机游走的简单性，以实现令牌覆盖在移动自组网。随机游走对于移动自组织网络是有吸引力的，因为它们在网络动态中具有固有的稳定性，没有临界故障点，避免了结构维护，并且具有非常小的状态开销。事实上，Census在很大程度上与移动性无关-运动模型和节点速度对其性能几乎没有任何影响，因为该协议的主要组成部分只是令牌传递。在纯随机游走中，持有令牌的节点在其邻域中随机选择一个节点，并将令牌转移到该节点。任何令牌第一次访问节点时，节点可以将其状态添加到正在计算的聚合中重复该过程，直到访问完所有节点不幸的是，随机游走的覆盖时间为了加快覆盖时间，我们在本文中探索的想法，部分引导随机游走未访问的节点。批准公开发行：无限制发行1.1捐款摘要1介绍局部偏置：让我们首先考虑仅基于局部信息的偏置，在转发令牌时优先考虑因此如果在直接一跳邻域中存在一个或多个未访问节点（即，在令牌的通信范围内），令牌被传递到随机选择的未访问节点之一我们分析表明，本地偏见，本身，实现了覆盖时间为O（Nlog（N）/k），其中k是正在使用的令牌的数量。此外，我们证明，通过只使用本地偏置，网络的很大一部分可以覆盖没有显着浪费探索已经访问过的节点。然而，当网络中已经访问过的节点的比例上升超过一定的阈值时，局部偏置会表现出放缓。这是因为当令牌持有者的通信范围内的所有节点都已经被访问时，该方案简化为规范随机游走，直到未访问的节点成为邻居。虽然相对于N的收敛阶数仍然是O（Nlog（N）），但速度减慢会在收敛中产生长尾，并显着增加覆盖时间。为了弥补这一缺陷，我们使用了一种补充方法，进一步加快了覆盖时间，这是人口普查的基础。多跳梯度偏置（Census）：为了防止随机游走在访问过的节点区域中卡住，同时还有未访问过的节点需要探索，我们设置了短暂的临时多跳梯度来将令牌拉向未访问过的节点。我们分析表明，这会产生一个覆盖时间为O（N/k），其中k是正在使用的令牌的数量。因此，收敛阶数提高了log（N）的因子。在这样做时，人口普查引入了O（Nlog（N）/k）的梯度消息开销，以将令牌拉向未访问的节点。然而，这种开销通过减少所需的令牌传输次数来补偿事实上，我们的模拟表明，令牌传输与节点大小的比率，即，即使对于大到4000个节点的网络，梯度偏置随机游走的探索开销也保持接近2。1.1贡献概述我们介绍的思想，应用有偏随机游动的节点访问问题在MANNETWORK，据我们所知，这还没有被探索我们分析表明，人口普查有一个快速的覆盖时间为O（N/k）的网络规模N和令牌计数k。我们还表明，人口普查的总通信成本是O（Nlog（N）/k）。我们表征网络密度的覆盖时间和消息开销的影响。我们分析比较性能普查定期随机游走，洪水，八卦，扩散和结构为基础的路由协议以及。我们证实了我们所有的分析结果，人口普查使用ns-3为基础的模拟移动网络范围从100到4000个节点，在不同的网络密度和移动模型。我们的模拟结果表明，有偏随机游走是简单的，但有效的工具，实现可扩展的和强大的令牌覆盖的移动自组网。批准公开发行：无限制发行1.2 文件概要. 3普查方案1.2论文概要在第2节中，我们描述了系统模型。在第3节中，我们描述了人口普查协议。在第4节中，我们给出了Census的收敛时间和消息开销的分析特征，并将其与具有局部偏差的随机游动和纯随机游动（无偏差）进行了比较。在第5节中，我们评估了人口普查的性能，并将其与纯随机游走、带有局部偏差的随机游走、洪水、流言、扩散和基于结构的聚合协议进行了比较。在第6节中，我们将讨论在MANET中实施普查的考虑因素，如处理消息丢失和终止检测。我们将在第7节讨论相关工作，并在第8节做总结性评论2系统模型考虑一个由N个节点组成的移动网络，网络的宽度和高度为θ（<$N×<$N），网络的通信范围和通信密度与网络规模N无关。对于我们的分析，我们专注于节点的随机行走移动模型[4，27]，而为了模拟的目的，我们考虑了各种移动模型，如随机路点和高斯-马尔可夫。在随机行走移动性模型中，在每个间隔处，节点在范围[0， 2π]中均匀地选择随机方向，并且以在范围[vl，vh]中随机选择的恒定速度移动恒定距离γ。在每个间隔结束时，计算新的方向和速度。该模型在其特征上是布朗的;布朗模型可以被描述为该运动模型在小步长下的缩放极限[22]。随机行走运动模型导致节点位置均匀分布在网络中[4]。因此，尽管节点的密度是随时间变化的，但我们注意到，随着时间的推移，每单位磁盘通信范围的平均节点数是恒定的（表示为d）。在网络内均匀分布的随机位置处引入一个或多个令牌Census的目标是在网络中传递令牌，使得网络中的每个节点都至少被一个令牌访问。回想一下，我们说当节点独占访问令牌时，令牌会访问节点。3普查议定书普查由两个部分组成：（i）令牌传递，以及（ii）梯度设置。为了实现这些组件，每个节点存储三个变量，访问者，持有者和级别。变量visited是一个布尔值，批准公开发行：无限制发行223.1令牌传递3普查方案图1：在令牌传递期间，令牌可能被访问节点的岛（白色圆圈）包围，即，已经访问了所有相邻节点。尚未被访问的节点（由黑色圆圈表示）定期使用已访问节点的集合来设置梯度，以将令牌吸引到它们。一个节点是否被任何令牌访问过;visited在所有节点上初始为false。当令牌第一次到达节点时，visited设置为true。令牌被假定为在随机节点集合处发起。默认情况下，启动令牌的所有节点都标记为已访问，并初始化令牌值 到相应节点的数据。变量holder用于标识当前持有令牌的节点。当使用梯度偏置时，每个节点还参与梯度设置过程以将令牌吸引到未访问的节点。为此，每个节点使用状态变量level，其中0≤level≤1。未访问的节点位于level= 1。持有令牌的节点在收到令牌后立即将级别设置为03.1令牌传递3.1.1仅带局部偏差的令牌传递对于只有局部偏差的随机游走，令牌持有者宣布它有一个令牌。听到该消息并且尚未被访问的节点启动定时器以在所选间隔[0，..，Tr]。听到该消息并且已经被访问的节点启动定时器以在所选间隔[Tr，..，Tr]。这确保了未访问的节点有机会在访问的节点之前进行传输。此外，如果一个节点听到另一个请求被发送，它会抑制自己的请求。这确保了无论网络密度如何，发送的请求数量都保持较低且相当恒定。在令牌持有者处启动定时器Tr如果至少有一个未访问的节点发送请求，令牌持有者会随机挑选一个未访问的节点。否则，令牌持有者随机选择一个访问过的节点。令牌被传输到所选节点。接收令牌标记批准公开发行：无限制发行3.2 三个孩子普查方案如果它到目前为止还没有被访问过，那么它就被访问过。如果令牌用于数据聚合，则已经访问的节点可能不会再次将其信息添加到令牌。这结束了使用仅具有局部偏置的随机游走进行令牌传递的过程使用此过程，令牌继续迭代传递3.1.2带梯度偏置的令牌传递对于具有梯度偏差的随机游走（即人口普查），令牌持有者宣布它拥有令牌。听到该消息的节点在所选间隔Tr内的随机时隙发送请求。 启动计时器Tr在令牌持有者处接受对令牌的请求。级别>0的所有节点随机化它们的响应时间，并回复令牌公告以及它们的当前级别。level >0的节点是未访问过的节点（level= 1），或者是已经访问过的节点，现在是梯度的一部分（0 θ/（h2d），则在Census中令牌持有者的h跳内存在至少一个未访问节点，概率为p，其中θ =−ln（1 − p）.4人口普查分析批准公开发行：无限制发行证据设nu表示网络中在给定时间未访问的节点的数量，设ρu表示网络的均匀密度。注意，令牌可以以相等的概率被传送到任何未访问的邻居，导致随机游走均匀地遍历网络。因此，执行随机游走的令牌在移出之前不会访问聚集在一起的所有节点。在每一步中，要遍历的下一个节点的选择是随机的。因此，假设网络是连通的且均匀分布的，则令牌的随机游走预计将均匀地遍历网络事实上，随机游走2D移动模型导致节点位置均匀分布在网络中[4]。现在我们回想一下最近邻距离在二维空间中的分布 对于二维齐次Poisson点过程，最近邻距离的概率密度函数为[3]。f（π）= 2πρ ε（−ρπ ε2）（1）随机选择的节点与其最近邻居之间的距离小于或等于某个距离r的概率由下式给出：P（π r）= 1−e（−ρπr2）（2）如果我们将R表示为每个节点的通信范围，则我们观察到在h跳内存在至少一个未访问的节点（即，半径hR），只要未访问节点的密度ρu>（−ln（1−p））/（πh2R2）（3）回想一下我们的系统模型，有N个节点均匀分布在区域A上，d是网络在任何时候每单位通信范围（πR2）的节点因此，N/A=d/（πR2）。利用这个，ρuA/N >（−ln（1−p））/（h2d）（4）注意，ρuA/N表示网络中未访问节点的比例，因此我们有结果。显著性：当p = 0时。95，d = 10，h = 1，θ/（k2d）= 0. 3. 因此，只要少于70%的批准公开发行：无限制发行DΣi=1i=14.1带有局部偏差的随机游动4人口普查分析当节点被覆盖时，期望具有局部偏差的随机游走在95%的时间内在一跳内找到未访问的节点在h= 2的情况下，我们可以看到，直到大约90%的覆盖率，未访问的节点可以预期在令牌的2跳邻域内。这突出了有界局部偏置随机游动可以覆盖网络的很大一部分的程度，而无需浪费太多的探索，也无需任何支持网络结构。4.1具有局部偏差的定理4.2. 在具有平均密度d的N个节点和单个令牌的连通移动网络中，具有局部偏差的随机游走中的期望覆盖时间和期望令牌转移次数都是O（N（log（N/d）。证据从引理4.1中，我们注意到，只要z > θ/d，未访问邻居的期望数量就保持大于1。 因此，对于节点的一小部分（1-θ/d），令牌行进的预期距离为 1.一旦访问过的节点的比例超过（1-θ/d），就会出现减速，因为令牌可能会随机遍历已经访问过的节点的区域。现在，请注意，在令牌持有者的2跳距离内有4个d 只要其中一个节点未被访问，令牌就会以4d的预期访问时间找到它。因此，对于n个节点的fractionθ/d−θ/4d，由ya到ken的期望距离是4d。继续到zd的最大搜索区域，其中zd=N，令牌在访问所有节点之前经过的总距离和完全覆盖的预期时间由以下表达式给出无无无无无无无O（N−1） d）+（d − 4 d）4 d +.. +（（z −1）2）−）z）z=O（N−N+N（3+5/4+.. +（2<$z+1）/（<$z−1）2））z−1时间复杂度：O（N）（2 i +1）/i2）i=1z−1n =O（N + N. n（2）/（i）+N. （1）/（i2））= O（N（1 + log（z− 1））{欧拉调和级数近似}时间复杂度=O（N（1））时间复杂度O（log（N））4.2有梯度偏差的4人口普查分析批准公开发行：无限制发行因此，我们已经证明了在具有平均密度d的N个节点和单个令牌的连通移动网络中具有局部偏差的随机游走中的预期收敛时间和令牌转移的预期数量都是O（N（log（N/d）。推论4.3。在具有平均密度d和k个令牌的N个节点的连通移动网络中，具有局部偏差的随机游动的期望收敛时间和每个令牌的平均传输次数都是O（（N/k）log（N/d））。证据 注意，当k个令牌用于访问所有节点时，每个令牌平均负责N/k的区域，由此得出结果。使用上面的推论，我们观察到，对于N个令牌，预期的覆盖时间是O（N（log（N/d）。当使用log（N）令牌时，预期收敛时间为O（（N/log（N））log（N/d）），即，时间复杂度O（N）4.2有梯度偏差的定理4.4.在具有梯度偏差的人口普查中，平均密度为d的N个节点和单个令牌的连通移动网络中的预期覆盖时间和令牌转移的预期数量都是O（N（1 + 1/d））。证据类似于定理4.2中的分析，对于一小部分节点（1-θ/d），令牌的预期行进距离为1。然而，一旦访问节点的分数超过θ/d，梯度将被用于将令牌拉向未访问的节点。现在，请注意，在令牌持有者的2跳距离内有4个d节点。只要其中一个节点未被访问，令牌就会被拉向该节点。因此，对于n个节点的分数θ/d-θ/4d，由ya到ken的期望距离是2。继续直到最大距离为N/N，令牌在访问所有节点之前经过的总平均距离和完全覆盖的平均时间由以下表达式给出4.2有梯度偏差的4人口普查分析批准公开发行：无限制发行Σ无无无无无无无时间复杂度=O（（N −）+（ −）2 +.. +（）-N）N）d d4dN（ N− 1）2d）Ndn =O（N+1）（1+1/4+1/9+... +1/N））D 中国n=O（N+N（1））Di=1时间复杂度=O（N（1+1））因此，我们已经证明，在具有梯度偏差的人口普查中，平均密度为d的N个节点和单个令牌的连通移动网络中的预期收敛时间和令牌转移的预期数量都是O（N（1 + 1/d））。与定理4.2相比，我们注意到速度增加了log（N）倍。此外，我们稍后将通过模拟研究表明，使用梯度消除了具有局部偏差的随机游走收敛中的长尾，从而显著加快了速度。与推论4.3类似，我们注意到，对于k个令牌，具有梯度偏差的Census的覆盖时间是O（N/k（1 +1/d））。因此，对于N个令牌，预期的覆盖时间是O（N（1 + 1/d））。当使用log（N）令牌时，预期的覆盖时间是O（N/log（N）（1 + 1/d））。定理4.5. 在密度为d和k个令牌的N个节点的连通移动网络中，具有梯度偏差的人口普查中的预期梯度消息开销为O（（N/k）log（N/d））。P roof. 沿着定理4.2的线，我们注意到，对于n个节点的分数（θ/d -θ/4d），平均梯度建立成本将是4 d。并且，对于节点的分数（1/（（p − 1）2d）− 1/pd），梯度设置成本将是pd，其中pd = N/k。 然后，如定理4的证明中所示，对级数求和即可得出结果。2.因此，我们注意到，当使用梯度偏置时，将令牌拉向未访问的节点会产生额外的开销，但这可以通过减少所需令牌传输的数量和减少收敛时间来补偿此外，梯度消息开销随着令牌的数量线性降低批准公开发行：无限制发行4.3 与其他聚合技术的比较4人口普查分析4.3与其他聚合4.3.1结构化数据聚合在ad-hoc网络中，特别是在静态传感器网络中，聚集计算问题是一个研究得很好的问题。解决方案包括定向扩散[18]、收集树协议[17]、喷淋器[26]和TAG [25]。然而，在移动网络和具有频繁链路变化的网络中，拓扑驱动的结构很可能是不稳定的，并且引起用于维护的高通信开销。已经观察到，用于诸如OLSR [ 19]之类的MANNETWORK的路由协议无法扩展到超过100 - 150个节点[10]。在最近的一篇论文[21]中，我们分析了MANNET中这种缩放墙的原因首先，随着网络规模的增加，路径可能会更频繁地失败-网络中的中值路径连接间隔为O（N），其中N是网络规模。其次，我们观察到，基于结构的方法是不强大的运动模型和节点速度，因为即使是很小的变化，节点速度显着增加链路变化的频率，从而增加路径故障率和不稳定性。最后，为了成功地用于路由，需要以比它们断裂的速率快得多的速度修复断裂的路径。这涉及到快速链路估计，用于发现损坏的路径，然后修复这些路径，这两者都会产生很高的消息开销。毫不奇怪，这些协议都没有成功地适应或评估MANN。另一方面，我们观察到，人口普查能够扩展到数千个节点在高度移动的网络。我们还发现，它的性能在很大程度上不受运动模型和节点速度的影响（如图2所示）8和图9）。4.3.2洪水和流言一个结构自由的方法，如洪水数据从所有节点到每一个其他节点的消息传递成本为O（N2），并没有任何比人口普查快。或者，对于平均一致性等问题，可以使用多轮局部gossip，其中在每一轮中，节点平均其所有邻居的当前状态，并且重复此过程直到收敛[15，5]。然而，这种方法需要多次迭代，并且已经被证明具有O（N 2）的通信成本和完成时间，用于网格或随机几何图中的收敛，其中连接性基于局部性[29]。 Census的通信成本为O（Nlog（N）/k），它可以用于不仅仅是平均值的应用程序。一般聚合问题的泛洪和流言的一种变体是类似扩散的方法，其中发起节点广播N桶寄存器（网络中的每个节点每当一个节点接收到这个寄存器时，它就把自己的状态添加到寄存器中（如果还没有添加的话），并重新广播寄存器批准公开发行：无限制发行5 评价如果它在这个迭代中学习到任何新节点。该过程继续，直到所有节点具有N桶寄存器的完整副本。注意，在这种技术中，每个消息的大小是O（N），因此消息传递成本至少是N（N2）。此外，该技术假设网络中所有节点的ID都是先验已知的另一方面，Census不假设任何关于网络中节点的知识，并且具有低得多的通信成本。5评价在本节中，我们将定量评估Census在不同网络条件下的收敛特性和性能更具体地说，在第5.1节中，我们量化了Census的收敛特性，并与纯随机游动和具有局部偏差的随机游动进行了比较;我们的结果描述了Census中的梯度偏差通过减轻覆盖时间中的长尾而获得的改进。在第5.2节中，我们评估了在不同网络条件下（如密度，令牌数量，移动模型和速度）的消息开销和覆盖时间，并将其与仅具有局部偏置的随机游走进行对于使用ns-3进行的人口普查模拟，我们设置了范围从125到4000个节点的MANDROOM，这些节点具有不同数量的令牌，这些令牌在网络内的随机位置启动节点被均匀地部署在网络中，并且部署区域和通信范围被选择为使得平均邻居大小（d）保持恒定而与网络大小无关。我们在以下移动模型的模拟中测试d=7，10和13：平均节点速度范围为3至15 m/s。5.1收敛特性5.1.1纯随机游动、局部偏差随机游动和梯度偏差随机游动的比较在这里，我们比较了纯随机游动与局部和梯度偏差的收敛特性我们在随机2D步行移动模型中使用了100-500的网络大小和单个令牌，其中节点在特定方向上移动固定距离，然后选择新的随机方向。100%覆盖时间见图。2（a）. 我们观察到局部偏置比纯随机游动快2倍，梯度偏置比纯随机游动快12 - 14倍。值得注意的是，局部偏置实际上比纯随机游走快得多，从一开始，直到一个主要的批准公开发行：无限制发行2700局部偏差2400梯度偏差纯随机游动2100180015001200900600300网络规模100网络规模200网络规模300网络大小400网络规模5005.1融合特点51009080706050403020100(a)（b）第（1）款图2：（a）覆盖时间与网络规模（单个令牌）（b）给定试验的500个节点网络上的收敛模式，有和没有偏见网络的一部分被覆盖，但在尾部会发生减速这种收敛特性的差异如图所示2（b），其中我们显示了纯随机行走，局部和梯度偏置普查的500个节点的单一随机选择试验的收敛模式在这个特殊的试验中，我们观察到，直到65%左右，局部偏差与梯度偏差保持一致，但随后略有放缓这是因为，在此之前，局部偏置使令牌能够直接找到未访问的节点，并且很少有浪费的探索。在80%左右，局部偏置的减速更明显，而纯随机游走则自始至终都很慢。在这一点之后，当只使用局部偏置时，在寻找未访问的节点时有许多浪费的探索，而具有梯度偏置的普查自始至终以统一的速率进行。151614局部偏差梯度偏差1210108654201020304050607080 90 100覆盖（一）0500 1000 1500 2000 2500 3000 3500 4000网络规模(b)图3：（a）令牌传递开销作为覆盖百分比的函数（局部偏差）（b）探索开销与网络大小我们在图中更详细地分析了具有局部偏差的随机游走的探索开销的影响3（a）梯度偏置局部偏置纯随机游动令牌传输/访问节点100%覆盖时间（秒）令牌传输/网络规模覆盖率%100200 300400500050100150200网络规模时间5.2不同网络条件下的普查属性5评估批准公开发行：无限制发行该图绘制了在具有局部偏差的随机游走的不同覆盖阶段处令牌转移与访问节点数量的比率（在多次试验上平均）。该比率捕获了令牌被重复传递到已访问节点的浪费的探索。我们看到，在局部偏差的情况下，该比率保持在低水平（2），直到大约70- 80%，然后开始迅速上升。<这个观察结果与我们在引理4.1中的结果相吻合。但是，人口普查的代币仍然接近2，没有任何急剧上升。5.1.2作为网络规模函数的探测开销图3（b），我们比较了在100%覆盖的情况下，不同网络规模下令牌传输到访问节点的比率我们观察到，对于局部偏差，该比率随着log（N）而增长，而对于梯度偏差，它几乎是平坦的，与我们在定理4.2和定理4.4中的结果相匹配。冗余令牌传递在梯度偏差下非常低，即使对于4000个节点的网络，比率也保持接近2。探索开销因子指示覆盖所需的令牌传递事务的数量，因此比绝对覆盖时间更准确地表示收敛特性，绝对覆盖时间是非常特定于实现的。例如，在我们的实现中，每个事务（即，令牌通告、令牌请求和令牌传递的每次迭代）平均花费250ms。但是，使用[31]等方法，这个数字可能会小得多，这些方法使用协作通信来估计满足给定谓词的邻域大小。5.2不同网络条件下的普查属性在本节中，我们将评估在不同密度、令牌数量、移动模型和速度下Census的消息开销和覆盖时间（以及本地偏差）。5.2.1消息开销在图4中，我们比较了Census和local bias的消息开销。为了突出显示log因子开销，我们在y轴上显示了按网络大小标准化的消息，在x轴上显示了按网络大小标准化的消息。具有梯度偏置的令牌消息的值保持恒定，指示令牌消息随网络大小线性增长。局部偏置令牌消息和梯度设置消息的曲线随着log（N）增长，指示Nlog（N）消息传递开销。注意，与局部偏置方案相比，梯度设置成本通过显著减少Census中所需的令牌消息 这些结果显示5.2不同网络条件下的普查属性5评估批准公开发行：无限制发行50局部偏差标记梯度偏差标记40梯度设置令牌3020100100 200 300 400 500网络大小（N）图4：人口普查和本地偏差人口普查实现优越的性能，无论是在覆盖时间和消息开销的本地偏见，尽管使用短的多跳梯度。5.2.2多个令牌首先，我们量化了使用logN和log（N）令牌的影响。图5（a）显示了网络中Census和局部偏差的Census我们模拟的网络大小为125、250、500、1000、2000和4000。网络中使用的相应令牌数量分别为11、15、22、31、42和我们观察到覆盖时间仅以O（N）增长，与我们的分析相匹配。在图5（b）中，我们展示了使用log2（N）令牌的影响。我们模拟的网络大小为125、250、500、1000、2000和4000。网络中使用的相应令牌数量分别为7、8、9、10、11和12在这里，观察到的趋势是线性的。3002502001501005000500 1000 1500 2000 2500 3000 3500 4000网络规模（一）1500140013001200110010009008007006005004003002001000局部偏差梯度偏差500 1000 1500 2000 2500 3000 3500 4000网络规模（b）第（1）款图5：（a）覆盖时间与网络大小（logN令牌）（b）覆盖时间与网络大小（logN令牌）局部偏差梯度偏差100%覆盖时间（秒）消息/N100%覆盖时间（秒）5.2不同网络条件下的普查属性5评估批准公开发行：无限制发行密度7400密度10密度13300200100100%覆盖时间（秒）12001000局部偏差梯度偏差2000016000局部偏置标记梯度偏置标记梯度设置标记8006001200080004002004000013579 111315171921令牌量（一）0135791113151719 21令牌量（b）第（1）款图6：（a）覆盖时间与令牌数量（N= 500）（b）消息与令牌数量（N= 500）接下来，在图6（a）中，我们分析了作为令牌数量的函数的覆盖时间。 网络大小为500，令牌的数量从1到22不等。我们注意到，覆盖时间随令牌数量线性下降，与我们的分析相匹配。图6（b），我们比较了相同场景的消息传递开销对于Census，我们看到梯度消息开销随令牌数量线性下降。梯度偏置的令牌传递开销大致保持不变，因为开始时开销非常小。局部偏置的令牌传递开销随令牌数量线性下降5.2.3密度的影响0(a)（b）第（1）款图7：（a）密度的影响（局部偏差）（b）密度的影响（梯度偏差）图7，我们量化了平均邻域大小（d）对覆盖时间的影响我们已经考虑了单个令牌场景，以消除多个令牌的影响该图显示了在较高密度下覆盖时间的预期减少24002000密度7密度10密度13160012008004000100%覆盖时间（秒）消息100%覆盖时间（秒）100200300400500100200300 400500网络规模网络规模5.2不同网络条件下的普查属性5评估批准公开发行：无限制发行5.2.4流动模式的影响140012001000随机行走随机路点高斯-马尔可夫400300随机行走随机路点高斯-马尔可夫8006002004002001000100 200 300 400500网络规模（一）0100 200 300 400 500网络规模（b）第（1）款图8：（a）流动模式的影响（地方偏见）（b）流动模式的影响（普查）我们模拟人口普查下的其他移动模型，随机航路点和高斯马尔可夫。节点速度保持在2- 4 m/s的范围对于随机航路点，连续变化之间的暂停时间设置为2秒在高斯马尔可夫模型中，运动特征与时间相关，用参数α进行调整。我们设α = 0。75.在高斯马尔可夫模型中，速度和方向每1秒改变一次。从图8中，我们观察到，覆盖时间特性对于这些不同的移动性模型是相似的，即使确切的时间显示出一些变化，这表明相对于移动性模型的鲁棒性，特别是对于人口普查。5.2.5节点速度302010100200300400500100200300 400500网络规模网络规模(a)（b）第（1）款14003米/秒12007米/秒11米/秒15米/秒100080060040020003米/秒7米/秒11米/秒15米/秒00100%覆盖时间（秒）100%覆盖时间（秒）100%覆盖时间（秒）100%覆盖时间（秒）5.2不同网络条件下的普查属性5评估批准公开发行：无限制发行图9：（a）节点速度的影响（局部偏差）（b）节点速度的影响（梯度偏差）批准公开发行：无限制发行6讨论为了强调人口普查是强大的移动性引起的链路变化的速率，我们模拟人口普查在不同的节点速度。如图所示9，即使平均节点速度增加到15m/s，覆盖时间仍然相当稳定。对于具有局部偏差的随机游走，我们观察到对于较大的网络，覆盖时间随着节点速度的提高而提高。这可能是因为在更高的速度下，暂时与具有令牌的部分断开连接的节点倾向于更快地与连接的组件收敛，从而减少覆盖时间的长尾6讨论在本节中，我们将讨论一些问题和优化技术，这些问题和优化技术与使用随机游走进行令牌覆盖的核心思想无关，但在MANET中实施人口普查6.1可靠的令牌传输可靠的令牌传输对于成功运营至关重要。如果节点释放了令牌，但预期的接收者没有收到令牌回复消息，则令牌丢失。同时，如果发送节点依赖于确认来释放令牌，则有可能确认丢失并且创建重复令牌对于不允许重复计数的应用程序，这是一个问题。在实践中，这个程序如下所述。一旦发送了令牌应答，发送方就释放令牌（节点将持有者重置为零）。与此同时，它仍处于等待接收方的应答状态如果在时间Ta内没有接收到确认，则令牌发送消息被重复最多K次重试。 如果接收方多次收到令牌，它只会重复确认消息。但是，如果令牌发送方即使在K次重试之后也没有收到确认，则它会为令牌创建一个检查点：（a）将迄今为止计算出的集合与令牌ID一起附加到令牌，（b）创建新的令牌ID（可以通过在创建期间简单地将节点的ID分配给令牌来创建唯一的ID），以及（c）重置令牌集合。有可能令牌实际上已成功通过，但即使在这种情况下，检查点也不会创建重复计数。同时，该过程确保数据不会丢失。