移动机会网络中的节点分簇路由算法

张霖 王兰

摘要：移动机会网络中的数据传输具有随机性特点，但源节点和目的节点的最优传输路径选择问题一直是研究的热点，该文提出一种节点分簇路由算法，即Node Clustering Routing Algorithm （NCRA）算法，该算法通过节点随机分簇找出簇头，再通过各簇头节点的数据选择传输，完成数据包的转发，最终将数据从源节点传输到目的节点，并找出最优信息传递路径。通过仿真实验，并与移动机会网络的Epidemic算法和OSNN算法比较，NCRA算法优化了网络数据传输路径，且具有传输效率高，能量消耗少，数据冗余少的特点。

关键词：移动机会网络;网络节点;分簇;数据传输

中图分类号：TP393 文献标识码：A

文章编号：1009-3044（2020）21-0023-03

开放科学（资源服务）标识码（OSID）：

1 引言

信息技术的高速发展给人们带来了巨大的生活便利，移动网络，无线网络等的出现更是为人类生产和生活缩小了物理距离，使人们即使相隔千里亦可以通过网络连线，实时分享生活点滴。特别地，在无线网络环境中，存在着多种类型的网络，如无线传感器网络，AdHoc网络，社交网络，移动机会网络等。

移动机会网络是一种延迟容忍类自组织性网络。其特点是源节点和目的节点间没有预先规划好的传输路径，完全依靠途径节点间的移动相遇完成信息传递，节点的移动规律是“携带一存储一转发”。移动机会网络具有较多的应用场景，如手持设备组网，车载网络，野外数据收集等。

在移动机会网络环境中，节点间的数据传输效率问题一直是研究热点。许多学者通过研究路由算法来不断优化节点传输过程，利用数学概率计算，或利用贪心算法，神经网络等技术，结合移动机会网络特点，设计开发了多种路由转发算法，不断改进前人的方案，取得了一定进步和成效，但在数据传输过程中，仍然存在网络资源浪费，传输安全风险大，传输性能不够等问题。

本文研究了一种移动机会网络中的节点分簇路由算法（Node Clustering Routing Algorithm（NCRA））算法，该算法先根据节点分布情况自由组合分簇，并在自由组成的簇中竞选出簇头节点，数据传输过程中，只需要考虑各簇头节点的传输路径，结合最短路径算法将各簇头节点间的逻辑距离进行比较，得出当前节点的最优邻居节点，进行下一跳选择传输。该算法能有效减少数据传输过程中的数据冗余和，节约网络资源，优化数据传输过程。

2 相关工作

文献[1]提出了Epidemic路由协议，该协议在节点移动过程中，利用节点的相遇和移动来完成数据交互。其核心思想是讲当前节点携带的数据通过复制副本的方式传输给相遇节点。因此每个传输节点都需要在缓存区中存储传递数据。该协议的本质是一种洪泛的路由协议。PROPHET路由协议[2]在Epi-demic协议基础上做了技术改进，该方案中，消息传递给下一跳节点前，会通过简单的数学概率计算，预先估计一条数据传输路线[3]，从而找出更合适的下一跳节点，优化传输路径。文献[4]利用了数学异或运算的特点，在数据传输过程中，通过节点信息的异或比较，找出最优的下一跳，从而找出最优的传输路径，完成节点数据转发。

基于复制的传输方案解决了移动节点的数据快速传输问题，但该方案同时也制造了大量数据冗余，浪费了网络资源，且传输性能不高。基于相遇预测型的路由协议通过对相遇概率的计算减少数据信息的洪泛传递，但根据历史信息进行概率估计可能与实际传输情况不符，影响数据传输的准确性[5]。通过寻找最优下一跳的方案较好地优化了数据传输路径，但却忽略了各移动节点的能力差异，较大的数据运算为节点带来了较大的负担。各种路由协议各有所长，但也各自存在着相应的弊端。

本文基于文献[4]，改进了其传输方案，设计了移动机会网络中的节点分簇路由算法，通过节点组合分簇方案，结合最小生成树分析法，在获取最优下一跳节点的同时，有效减轻弱节点[6]的传输负担，达到节约网络资源，提升数据传输性能的目的。

3 节点分簇路由算法

3.1 移动机会模型

移動机会网络通过各个节点的移动创造相遇机会实现节点之间的网络通信，但只有在同一个连通区域内的节点之间才可以完成通信[7-8]。现假定在某一个时刻s，网络由t个不同的连通区域组成，其中图1表示s时刻随机两个连通区域的机会网络结构图。

由图1可得，A、B、C、D、E、F节点和G、H、I、J、K节点分别属于连通区域1和连通区域2，由机会网络的特性可知，连通区域1内的所有节点可以互相传递数据信息，如A节点的数据信息可以传递给B、C、D、E、F，连通区域2中节点的数据信息也可以互相传递，试想若希望将A节点的数据传递到不属于同一连通区域的H节点，则要通过节点不断移动到同一连通区域才可实现。

3.2 节点分簇描述

经过上文描述，现将图1中的任一连通区域中的各个节点实现分簇处理，分簇方法为，根据网络中节点的接收信号强度和节点连通度确定簇内成员，即根据无线网络中的节点物理位置相关性完成节点分组，定义α为评价尺度常量，表示节点间数据传输的最大距离门限值，现将网络环境中以评价尺度常量α划分为若干子区域，在每个子区域中随机选中一个节点t作为簇头，若任意节点v满足如下规则：

其中D（T，v）表示节点间通信链路函数，即表示任意节点v到簇头t的通信距离。

节点v加入当前t为簇头的簇T，分簇后的网络形成由各个簇组成的新的网络环境，在确定簇成员后，簇内成员发送自身数据包给簇头，簇头接收到各成员的数据包后进行数据融合处理，融合后的簇头中包含了各个节点的数据，同时消除了各节点中冗余的数据信息。

任意选择一个t时刻的某个网络环境M为研究切人点，做出如下假设，假设M中有n个节点，将其根据物理位置相关性随机生成6个连通区域，即同时形成6个簇，随机指定各簇头，簇头将各自内部的节点信息数据融合处理，将分好的6个簇用集合表示为U={A，B，C，D，E，F 1，其中每个簇都能实现数据的转发;设当前时刻A为起始节点，且当前网络拓扑结构保持不变，构建如下网络连通图，如图2所示。根据图2得到连通图G=（U，v）其中，初始状态U={A}，V={B，C，D，E，F} ，图2中各节点间的横线表示各节点之间的逻辑传输距离。

3.3下一跳节点选取过程

每个簇节点中存放了各个簇中经过数据融合处理的数据信息，假设在当前时刻T，网络环境M中存在如上图2中的连通图。从A出发，寻找最优传输路径过程如下。

1）起始状态，只有A为当前节点，即U={A}，V={B，C，D，E.F}。

2）从A节点出发，比较V中的各代价边，分别标记各节点与初始节点A的逻辑距离，如D（A，3），B（A，6），E（A，5），C（A，∞），F（A，∞）。通过逻辑距离比较得到，当前最小边为D（A，3），即确定下一跳节点为D，此时，U={A，D），V={B，C，E，F）。

3）更新V中各个顶点与U的代价边，即B（D，2），C（D，6），E（A，5），F（A，。。），通过逻辑距离比较得到当前最小边为B（D，2），即确定下一跳节点为B，此时，U={A，D，B}，V={C，E，F）。

4）更新V中各个顶点与U的代价边，即C（B，7），E（B，4），F（B，6），通过逻辑距离比较得到当前最小边为E（B，4），即确定下一跳节点为E，此时，U={A，D，B，E}，v={C，F）。

5）更新V中各个顶点与U的代价边，即C（B，7），F（E，1），通过逻辑距离比较得到当前最小边为F（E，1），即确定下一跳节点为F，此时，U={A，D，B，E，F），V={C}。

6）更新V中各个顶点与U的代价边，即C（F，4），确定下一跳节点为C，此时，U={A，D，B，E，F，C），到此，路径规划结束。

8）统计依次插入的节点为A、D、B、E、F、C。则A一>D一>B一>E一>F一>C为当前最优路径。

3.4 算法设计

通过上一节内容总结出NCRA算法执行过程描述如下。

第一步：将当前节点存入集合V，其初始值为通信信息的第一个节点，该节点为当前节点m，把m并人集合U中，令U={ml。

第二步：采用节点逻辑路径比较访问法标记当前环境下的各节点逻辑距离，找出最小逻辑距离节点i，并将i并入集合U，令U={m，ij，

第三步：更新节点距U中最新节点的逻辑距离，找到下一最小逻辑距离节点k，并将k并人集合U=（m，j，k），

第四步，重复第三步，直到U中存在所有节点为止。

第五步：输出集合U中的所有节点，该集合顺序即为节点信息传输的最优路径。

4 仿真与实验分析

为验证NCRA算法的性能，实验采用ONEl.4仿真平台工具，通过与Epidemic算法和OSNN路由协议进行比较，在保证节点个数、节点传输范围以及节点移动速度一致的前提下分别采用三种算法进行仿真实验，在一定的时间内，观察节点密度变化对传输成功率，传输延迟以及路由开销的影响程度，将三种结果进行比对，综合分析得出实验结论。

图3中节点密度直接影响数据的传输成功率，节点密度较小时三个算法的传输成功率几乎都保持在10%-15%，但当节点密度不断增大时，NCRA算法的传输成功率明显优于另外两种算法，结合理论分析不难解释该仿真结果，NCRA算法通过节点分簇后比较节点逻辑距离选取传播距离最小的节点进行数据传递，因此取得较高的数据传播成功率。

由图4可以得出的结论是三种路由协议算法对数据传输延迟的影响都不是很大，其中Epidemic算法的延迟最小，NCRA算法较OSNN算法的传输延迟略小。出现这种情况的原因是Epidemic算法的特点为“遍地撒网”式，不对下一跳节点优化处理就直接转发，因此传输延迟小，而NCRA算法和OSNN算法在传输过程中要通过不同的处理方式选择下一跳路径，而选择过程就造成了传输延迟略高于Epidemic算法。另外，OSNN算法需要对每个节点进行计算比较，而NCRA算法只针对簇头节点进行比较计算，因此优化了传输流程，同时降低了传输延迟。

圖5中，当节点密度很小时，三种算法的路由开销相差无几，通过不断增加节点密度，Epidemic算法的路由开销明显增大，且一直处于高速上升状态，而OSNN和NCRA算法造成的路由开销明显低于Epidemic算法，其原因是OSNN和CNDTR算法是择优选择下一跳传输数据，因此每一跳只选择最优节点传输，因此造成路由开销比较小，而Epidemic算法是洪泛式传递，因此节点密度越大，其路由开销就会越大。由图看出，随着节点密度不断增大，NCRA算法造成的路由开销最小。

通过仿真实验以及结合理论知识的分析可得，NCRA算法能够在传输数据的同等条件下降低路由开销，并提高数据传输成功率。不可否认的是，因下一跳选择时需要计算选择，造成了传输延迟，但就总体性能而言，相对其他经典传输算法，NCRA算法具有一定优势。

5 结束语

本文提一种移动机会网络中的节点分簇路由算法（NodeClustering Routing Algorithm （NCRA》算法，通过将节点融合成簇后采用簇头节点通过节点间的逻辑距离比较，每次都选择最短路径来确定下一跳，最终获得最优传输路径，实现高效网络数据的传输，减少网络资源的浪费，节省路由开销。通过仿真实验验证，与Epidemic、OSNN算法进行比较，CNDTR算法可以节省路由开销的同时减少网络数据冗余。

参考文献：

[1] Vahdat A，Becker D.Epidemic Routing for Partially ConnectedAd Hoc Networks[J]，Master Thesis. 2000.

[2] Lindgren A， Doria A， Davies E，Grasic S.Probabilistic routingprotocol for intermittently connected networks[J]，lnternet Engi-neering Task Force （IETF）， 2007.

[3]任智，黄勇，陈前斌，等，機会网络路由协议[J].计算机应用研究，2010，30（3）：723-72.

[4]张霖，陈志刚，吴嘉，等.最优化选择邻居节点路由协议[J].小型微型计算机系统，2017（1）.

[5] Luo J ， Yu F R ， Chen Q ， et al. Adaptive Video StreamingWith Edge Caching and Video Transcoding Over Software-De-fined Mobile Networks： A Deep Reinforcement Learning Ap-proach[J]. IEEE Transactions on Wireless Communications，2020， 19（3）：1577-1592.

[6] Wen R ， Feng C ， Tang J ， et al. On Robustness of WetworkSlicing for Next-Generation Mobile Networks[J]. IEEE Trans-actions on Communications， 2019， 67（1）：430-444.

[7] Chhabra， Anshuman， Vashishth， et al. A fuzzy logic and gametheory based adaptive approach for securing opportunistic net-works against black hole attacks[J]. International Journal ofCommunication Systems， 2018.

[8] Fu X ， Yao H ， Postolache 0 ， et al. Message forwarding forWSN-Assisted Opportunistic Network in disaster scenarios[J].Journal of Network and Computer Applications， 2019， 137：11- 24.

基金项目：重庆第二师范学院青年项目（KY201926C）

作者简介：张霖（1993-），女（土家族），湖南常德人，助教，硕士研究生，研究方向为无线网络、网络安全;王兰（1991-），女，四川宜宾人，助教，硕士研究生，研究方向为信息安全。