移动机会网络中面向聚集点的数据转发策略

开篇：润墨网以专业的文秘视角，为您筛选了一篇移动机会网络中面向聚集点的数据转发策略范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：移动机会网络利用节点接触进行数据转发的特点非常适合实际环境下的自主组网需求，促使了大量应用的产生。考虑到这些节点通常是由人或车来携带，人类行为的参与是这些应用成功的关键因素之一。探讨了人类的移动行为对机会网络中数据转发性能的影响，发现人们总是在一些热点区域之间往返，而很少访问其他区域。基于上述现象，提出了一种基于人类聚集点的机会路由策略――聚集分发策略（GS）。GS假设每一个热点区域都配置一个接入点（AP），相对于其他移动节点，接入点有着较高的对信息进行缓存和分发的权限。理论分析证实GS的平均投递延迟低于喷雾等待机制，仿真结果显示GS同时提高了数据包投递率。

关键词：人类聚集点；数据转发；路由协议；性能评价；移动机会网络

0引言

近年来随着无线通信技术与移动感知技术的快速发展，目前的智能设备具有了强大的感知和通信能力。利用这些智能设备，可以方便地对物理世界中的感知数据进行收集或分享现实社区内的兴趣消息。这种感知/共享的通信模式通常被称为移动机会网络（Mobile Opportunistic Network， MON）[1]。与传统的无线传感网络和自组织网络相比，移动机会网络一个最重要的特征就是它不要求源目的对之间具有端到端连通的路径。这种新的特征使得移动机会网络能够很好地适应拓扑时变的场景，包括野生动物监测[2]、群智感知[3]、乡村通信[4]以及城市计算[5]等。

在上述情景中由于链路间歇性连接等原因，如何快速有效地投递数据包是移动机会网络面临的一大挑战。为了解决这个问题，研究人员设计了许多带有存储携带转发特点的路由算法。在它们之中，洪泛[6]是最早提出的一种数据包投递策略。它通过向网络中扩散数据包的多个备份来提高数据包被成功接收的概率。洪泛算法在包的投递率和平均投递延迟方面具有最优的性能，同时，过多的数据备份也意味着更高的网络代价（占用了更多的缓存空间、消耗了大量的能量及带宽等），导致网络性能降低。研究人员提出了一些智能的路由协议来改善洪泛算法的性能。比如，文献[7]提出了一种直接等待策略，当且仅当源节点遇到目的节点时才投递数据。文献[8]提出将数据包限制在两跳范围之内传播来减少开销。喷雾等待策略[9]是一种基于数据配额的路由方案，通过限制转发数据备份的数量来降低网络负载。文献[10]在文献[9]的基础上，提出了一类多副本自适应路由协议，通过中继节点适时地进行喷雾决策，并由喷雾决策算法决定是否增加新的消息副本，以此来达到对网络环境的快速感知和自适应。

上述算法假设所有节点遵循随机游走策略并且均匀访问每一个位置。然而，最近的研究结果[11-12]发现人类的移动行为具有一定的社会性，并不是完全随机的，这样就使得喷雾等待策略效率低下。

本文主要研究人类移动性对机会路由性能的影响。文献[13]发现人们总是在一些热点区域之间频繁往返，而其他区域则很少访问。也就是说，人类移动具有明显的自相似性。基于上述现象，本文提出了聚集分发（Gathering Spray，GS）策略，一种基于人类聚集点的机会路由策略。GS将人类移动模式的相关知识融入到数据转发过程中，通过利用这些聚集点来提高备份定制策略的性能。更准确地说，GS假定每一个聚集点配备一个有更高权限缓存和分发信息的接入点。当接入点携带一个数据包的多个备份时，它采用线性递减策略，将其中一个备份转发给相遇节点，该过程被称为慢速喷雾阶段。与此相对的是，当移动节点遇到接入点时，移动节点采用贪婪策略将之携带的K个备份中的K-1个转发给接入点，则称该过程为快速喷雾阶段。快速喷雾阶段减少了备份的传播延迟，慢速喷雾阶段则有利于提高数据包投递率，这主要是因为节点之间的大多数接触是在接入点附近发生的，这样接入点遇到目的节点的可能性就高于其他移动节点。实验结果显示GS在投递率方面相比SprayWait算法提升了15%，同时在传输延时方面下降了20%。具体来说，本文的主要贡献如下：

1）在数据转发过程中考虑了人类聚焦点的影响，假设每个聚集区域都配备了一个接入点，用来充当移动节点之间的一座桥梁。

2）继承了零信息型路由策略和信息辅助型路由策略各自优点来设计数据备份的分发过程。围绕接入点，本文设计了两种喷雾策略，用来保证GS获得较高的投递率和较低的传输延迟。

1相关工作

利用额外节点辅助信息收集或数据转发是无线传感网和移动机会网络的研究热点之一。这主要是考虑到在一些具体应用[14-19]中，有时对数据传输的时效性要求较高，在这种情况下，单纯依靠系统中原有的节点，无法满足应用需求。这样一来，就需要主动部署一些移动节点或静态节点来帮助原有节点提高数据传输效率。这方面代表性工作主要包括：文献[14]提出一种“数据骡/渡口”的数据转发方式。通过在彼此不连通的感知区域之间部署称之为“数据骡”的移动节点完成数据转发。文献[15]通过控制“数据骡”的移动性来进一步提高数据转发效率。文献[16]设计了“数据骡”的两种移动方式：一种是由移动节点触发的，在这种情况下，移动节点按照原来预设的路线收集数据；另一种是感知节点触发的，当移动节点收到来自感知节点的数据请求时，移动节点调整自己的移动路线。Zhao等[17]对引入辅助节点所获得的网络性能增益与由此导致的额外开销之间的关系进行了研究。文献[18]进一步放宽了文献[16-17]中的假设条件，利用节点观察到的部分信息来控制“数据骡”的移动。文献[19]利用闭的游走模型来规划“渡口”的运动机制。

与上述在静态稀疏的传感网中部署移动节点帮助静态节点进行数据收集的方式不同，文献[20]分析了在移动机会网络中部署静态节点对系统性能的影响。文献[21]针对冗余数据包的删除问题，提出在人类经常活动的区域内放置静态节点来收集已成功投递的数据包的确认报文，利用这些确认报文来帮助移动节点删除多余的冗余数据。实验结果显示，该策略可以加快冗余数据包的删除。

与文献[21]不同的是，本文关注的是数据的转发问题，而不是冗余数据的删除问题（可以理解为缓冲区管理问题），这两个问题在移动机会网络的研究中是正交的。此外，本文分析了静态节点的引入对原有移动节点之间转发机制的影响，以及静态节点与移动节点之间的数据转发问题。

2数据转发策略

2.1聚集点

聚集点指的是人们在日常生活和工作中经常聚集的地方。它是人类社会中的一种常见现象。文献[13]对一些真实的数据集进行了分析，发现人们的移动性具有强烈的自相似性，经常往返于一些相对固定的场所，形成私人聚集区域（比如说家庭）和公共聚集区域（公司、商场、运动场所等）。利用人们的这种群聚行为，可以为设计有效的机会路由算法提供一些启发式知识。一个直观的认知是在这些聚集区域，人们相遇的概率要远远大于其他区域。本文提出在公共聚集区域内配置静态节点，来帮助移动节点完成数据转发。围绕移动节点之间、动静节点之间的数据转发问题，设计转发策略。

应用场景本文研究内容的一个典型应用场景是小区内PM2.5的检测。假设小区业主携带的智能手机上安装有一款检测PM2.5含量的应用软件。应用程序可以自动地将附近的智能手机组成一个临时的自组织网络，智能手机之间通过一跳或多跳的方式共享各自感知的PM2.5信息。基于收集到的多个设备的PM2.5信息，应用程序绘制小区内PM2.5含量的分布图，并将结果反馈给业主，使业主对所居住小区内的环境质量有一个直观的了解。为了提高PM2.5检测信息的收集速度，可以在业主频繁经过或活动的区域（比如小区的出入口或小区花园内）安装静态AP来辅助感知设备进行数据传输。

2.2GS算法

本文在社区移动模型[22]的基础上，对上述应用场景进行了抽象（见图1）。N-1个移动节点随机部署在一个面积为S的格子内。在格子的中央存在一个公共聚集区域，其内配置一个静态节点AP（Access Point）。在系统的初始状态，每个移动节点随机选取一个格子（非中央区域的任意一个格子）作为它的私人聚集区域。当节点在私人聚集区域时，它访问公共聚集区域的概率为p，其他区域的概率为1-p。当节点不在私人聚集区域时，它返回私人聚集区域的概率为q，其他区域的概率为1-q。

给定数据包m的K个备份，GS将整个数据转发过程划分为以下4个阶段：

1）当数据包m没有扩散至公共聚集区域时（静态节点AP没有收到该数据包时），对于任意一个携带L个备份的移动节点I（1

2）当一个携带L个备份的移动节点I遇到AP时（假定此时AP没有携带m的任意一个备份），I将L-1个备份转发给AP，同时自己保留一个备份。该阶段称之为快速喷雾阶段。

3）当静态节点AP收到m的多个数据备份时，如果AP遇到其他的移动节点D，AP向D转发m的一个备份，自己保留剩余的备份（该阶段称之为慢速喷雾阶段）。图3显示了上述AP与移动节点之间数据备份的转况。

4）当节点只携带m的一个备份时，进入直接等待阶段。在遇到目的节点时，完成数据投递。

由上述分析可知，步骤1）主要解决移动节点之间的备份分配问题。它采取二分法提高数据包的扩散速度（文献[9]已经证明，在一个同质的环境中，二分法具有最快的扩散速度）；步骤2）采用贪婪策略进行备份的分配；步骤3）采用线性递减的策略转发数据包的剩余备份，进一步降低转发代价，但同时并没有显著影响数据的传输延时以及投递率。这主要是由于AP比其他节点更有可能遇到目的节点。

3性能分析

本章对GS算法的传输延时进行分析。首先分析直接等待阶段的传输延时。当数据包m的K个备份分配完毕后，K个中继进入直接等待阶段。

令β表示移动节点之间的接触速率，γ表示移动节点和静态节点AP之间的接触速率（由文献[23]可知，在给定移动模型的情况下，上述两种接触速率均可以直接计算得出）。令EW表示等待阶段延时的期望，基于AP是否携带m的一个备份，有下面的引理1和引理2。

引理1等待延时。若AP没有携带m的任意一个备份，有：

EW=1/（βK）（1

证明由于K个移动节点遇到目的节点的时间是K个独立的、同分布的随机变量， 并且移动节点之间的接触速率满足指数分布[9]，则当AP没有携带m时，等待阶段的延时期望为1/（βK）。证毕。

引理2 等待延时。如果AP至少携带m的一个备份，则有：

EW=min [1/γ，1/（β（K-1））]（2

证明AP遇到目的节点的时间是1/γ，其余的K-1个移动节点遇到接收节点的时间是K-1个独立、同分布的随机变量的最小值1/（β（K-1））。因此， K个中继节点中任意一个遇到目的节点的时间是二者的最小值。证毕。

由引理1及引理2，可以得出如下结论。

定理1GS在等待阶段的延时EW可以统一表示为：

ββ+γK-11βK+1-ββ+γK-1min1γ，1β（K-1）（3

证明在单位时间内，某个移动节点遇到AP的次数是γ，遇到其他移动节点的次数是β，则移动节点遇到AP的概率是γ/（β+γ）。如果AP没有携带m的任意一个备份，说明前K-1个移动中继均没有遇到AP，这种情况发生的概率是ββ+γK-1。同样地，AP至少携带m的一个备份的概率是1-ββ+γK-1，则结合引理1及2，得出式（3）所示的结论。证毕。

下面对数据包转发阶段的延时进行分析。基于静态节点AP是否携带m的备份，有下面的引理3和4。

引理3转发阶段的延时，AP没有携带m的备份。令ED表示该种情况GS算法延时的期望，E（i）表示在i个备份被转发之后，预期的剩余延时。 有E（1）≈ED，其中E（1）由式（4）迭代表示：

E（i）=

1βi（N-i-1）+N-i-2N-i-1E（i+1）， i∈[1，K/2]

（K-iiE（i+1）+2i-KiE（i））N-i-2N-i-1+

1βi（N-i-1），i∈K2+1，K-1

EW，i=K （4

证明考虑在这样的一个时刻， 有i个移动节点携带m的一个或多个备份，假设其中Xi个节点携带多个备份，则这Xi个节点可以继续扩散多余的备份。假定节点之间的接触速率服从独立的指数分布，那么任意一个携带备份的节点（总数是i）遇到没有携带备份的节点（总数是N-i-1，注意这里不包括静态节点AP）的时间是1/（βi（N-i））。如果遇到的恰好是接收节点（概率是1/（N-i-1）），则完成数据投递。如果没有遇到接收节点（概率是（N-i-2）/（N-i-1）），存在着下面两种可能： 1）如果该节点携带多个备份（概率是（Xi/i）），则将自己携带数据包的备份数的一半转发给相遇节点。那么现在有i+1个节点至少携带一个备份，算法进入状态E（i+1）；2）如果该节点只携带一个备份（概率是（i-Xi）/i），则算法继续停留在状态E（i）。综合上面的过程，可以得到：

E（i）=（i-Xii E（i）+Xii E（i+1））N-i-2N-i-1+

1βi（N-i-1

利用文献[9]的结论，得到Xi=i （i∈[1，K/2]）以及Xi=K-i（i∈[（K/2）+1，K]）。代入上式，则可得到式（4）。证毕。

引理4转发阶段的延时，AP携带m的多个备份。当AP携带多个备份时，AP进入慢速转发阶段，其他携带多个备份的节点继续执行快速转发策略。与引理3类似，令EF表示GS算法延时的期望，可以得出E（1）≈EF，其中E（1）由式（5）迭代表示：

E（i）=a+N-i-1N-ib， i∈[1，K）

EW， i=K （5）

其中：参数a表示任意一个携带m的节点与没有携带m的节点的间隔时长的最小值。

a=min （1β（i-1）（N-i），1γ（N-i））

b=min（i-Xii-1 E（i）+Xi-1i-1 E（i+1），E（i+1））

证明设在某个时刻，有i个节点携带m，其中包括一个静态节点AP，i-1个移动节点（假定其中的Xi个移动节点携带多个备份）。那么i-1个移动节点中的任意一个与其余N-i个移动节点相遇的最小时间间隔是1/（β（i-1）（N-i））。类似地，AP与N-i个移动节点相遇的最小时间间隔可以表示为1/（γ（N-i））。综合上述两种情况，可以得到参数a的表示。

下面的证明与引理3的证明类似。在这里只列出主要步骤。对于i-1个节点中的任意一个节点I，当它遇到N-i中的任意一个节点J时，I将自己携带m备份数的一半以概率（Xi-1）/（i-1）转发给J。如果是AP遇到J，AP分配m的一个备分给J。综合上面的情况，可以得到参数b的表示。注意i个节点没有遇到接收节点的概率是（N-i-1）/（N-i），得到式（5）。证毕。

与定理1类似，基于AP是否携带数据包的概率，可以得出GS转发阶段延时的统一表示（证明略）：

ββ+γK-1ED+1-ββ+γK-1EF（6

接下来分析GS与SprayWait算法的延时性能。令Dh表示GS的数据包投递延时，Ds表示SprayWait的数据包投递延时，得出：当β/γ≤ （lb k）/k，Dh≤Ds（1≤k≤K）。

证明首先分析等待阶段的延时。当AP没有携带数据包m的任意一个备份时，两者的延时相等；当AP携带m的一个备份时，由于AP遇到目的节点的可能性远大于其他的移动节点，而对另外的K-1个移动节点来说，它们在这两种策略下遇到目的节点的概率相同，所以GS等待阶段的延时低于SprayWait。

下面分析二者在备份转发阶段的延时。假定AP需要分配k个备份， 则它花费的时间为k/γ（这主要是因为AP每次分配一个备份给相遇节点，而AP与其他节点相遇一次的时间是1/γ）。现在假定这k个备份由移动节点来转发，则共需要转发lb k次（移动节点之间采用二分法进行备份的分配），所以花费的时间为（lb k）/β。则当β/γ≤（lb k）/k，GS转发阶段的延时要低于SprayWait。证毕。

4实验结果与分析

4.1实验环境

本文在.Net平台下集成了社区移动模型以及进行比较的两种路由算法： SprayWait和GS。整个实验场景如2.2节的图1所示。仿真区域S的面积为600m×600m，被划分为25个子区域，中间的子区域作为公共聚集区域。一共设置了4组实验，前两组中每组49个移动节点随机部署在S中，数据包的备份数K分别设置为4和8，后两组每组99个移动节点，静态节点AP部署在公共聚集区域。初始时，每个移动节点随机选择一个非公共聚集区域作为它的私人聚集区域。节点的移动速度为10m/s～30m/s，停留时间为1s。实验中用到的两个参数p、q的值分别设为0.8和0.9。仿真时间为100s，总共生成1000个数据包。实验的结果为100次随机实验的平均值，评价指标包括投递率以及平均传输延时。

4.2实验结果

图4显示了在不同的数据包存活时长下，三种算法在投递率方面的相对性能。整体而言，延长数据包的存活时间可以提高算法的投递率。与经典的SprayWait算法相比，GS仍然表现出了较优的路由性能，数据包的投递率在各组实验条件下平均提高了15%。

下面对GS与SprayWait算法的延时进行分析。由图5可以看出GS同样具有较优的延时性能。在稀疏的场景下（图5（a）与5（b）），平均传输一个数据包，GS花费23s（仿真时间为90s），而SprayWait需要28s，GS的平均延时下降了20%。同时，随着节点密度的增大以及备份数目的增多（如图5（c）与 5（d）所示），GS算法的性能增益有所收窄。这主要由于节点密度的增大导致移动节点之间的接触速率增大，从而降低了β与γ的比率，无法充分发挥静态节点AP的优势，数据包备份的分配策略倾向于SprayWait所提出的二分法。

5结语

考虑到人们在现实生活中的群聚性，本文提出一种面向聚集点的机会路由算法GS。通过在聚集区域配置静态节点来辅助移动节点进行数据转发，提高数据传输效率。围绕静态节点，GS将整个数据转发过程分为不同阶段：快速转发阶段、慢速转发阶段以及直接等待阶段。在快速转发阶段，移动节点采用贪婪策略加快数据包向静态节点转发的过程；在慢速转发阶段，静态节点采用线性递减的转发策略提高数据包投递率。最后当携带的数据包只剩余一个备份时，节点采取直接等待策略完成数据投递。理论分析与仿真结果验证了所提算法的正确性和有效性。

参考文献：

[1] JINDAL A， PSOUNIS K. Contentionaware analysis of routing schemes for mobile opportunistic networks[C]// Proceedings of the 1st International MobiSys Workshop on Mobile Opportunistic Networking. New York： ACM， 2007：1-8.

[2] HAAS Z， SMALL T. A new networking model for biological applications of Ad Hoc sensor networks[J]. IEEE/ACM Transactions on Networking， 2006， 14（1）： 27-40.

[3] GANTI R， YE F， LEI H. Mobile crowdsensing： current state and future challenges[J]. IEEE Communications Magazine， 2011， 49（11）： 32-39.

[4] PENTLAND A， FLETCHER R， HASSON A. Daknet： rethinking connectivity in developing nations [J]. Computer， 2004， 37（1）： 78-83.

[5] ZHAO D， MA H， LIU L， et al. On opportunistic coverage for urban sensing[C]// Proceedings of the IEEE 10th International Conference on Mobile AdHoc and Sensor Systems. Piscataway： IEEE， 2013： 231-239.

[6] VAHDAT A， BECKER D. Epidemic routing for partially connected Ad Hoc networks， Technical Report CS200006 [R]. Durham： Duke University， 2000.

[7] FRENKIEL R H， BADRINATH B R， BORRAS J， et al. The infostations challenge： Balancing cost and ubiquity in delivering wireless data [J]. IEEE Personal Communications， 2000， 7（2）： 66-71.

[8] GROSSGLAUSER M， TSE D. Mobility increases the capacity of AdHoc wireless networks [C]// INFOCOM 2001： Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications. Piscataway： IEEE， 2001， 3： 1360-1369.

[9] SPYROPOULOS T， PSOUNIS K， RAGHAVENDRA C S. Efficient routing in intermittently connected mobile networks： the multiplecopy case [J]. IEEE/ACM Transactions on Networking， 2008， 16（1）： 77-90.

[10] XU J， LI Q， ZHANG H， et al. Performance evaluation of adaptive spray routing for opportunistic networks[J]. Journal of Computer Research and Development， 2010， 47（9）：1622-1632.（徐佳， 李千目， 张宏，等. 机会网络中的自适应喷雾路由及其性能评估[J]. 计算机研究与发展， 2010， 47（9）：1622-1632.）