Epidemic机制下基于优先级的机会网络路由算法

技术领域

本发明涉及机会网络路由算法，作用是使机会网络中某些数据包得到优先转发。

背景技术

机会网络是一种不需要在源节点和目的节点之间存在完整路径，利用节点移动带来的相 遇机会实现网络通信的、时延和分裂可容忍的自组织网络。机会网络不同于传统的多跳无线 网络，它的节点不是被统一部署的，网络规模和节点初始位置未进行预先设置，源节点和目 的节点之间的路径事先不能确定是否存在。机会网络以“存储-携带-转发”模式逐跳传输信 息实现节点间通信，其体系结构与多跳无线网络不同，它在应用层与传输层之间插入一个被 称为束层的新的协议层。

由于机会网络能够处理网络分裂、时延等传统无线网络技术难以解决的问题，能满足恶 劣条件下的网络通信需要，其主要应用于缺乏通信基础设施、网络环境恶劣以及应对紧急突 发事件的场合。

在机会网络的许多应用场景中，有区别对待不同节点的需要。如在灾难场景中，救援人 员和普通民众携带的智能设备共同构成机会网络，此时救援人员节点发出的数据包应得到优 先传输。再如在一些开放性的场景下，会有一些志愿节点加入到机会网络中。在有志愿节点 参与的开放性机会网络中，应优先保证网络固有节点数据包的传输。

上述场景要求机会网络中节点具有优先级，部分节点以及这些节点产生的数据包可以优 先使用网络资源。

评价机会网络路由算法性能指标的度量值主要有：

1.传输成功率

传输成功率(Delivery Ratio)是在一定的时间内成功到达目标节点数据包总数和源节 点发出的需传输数据包总数之比，该指标刻画了路由算法正确转发数据包到目标节点的能力， 是最重要的指标。

2.路由开销

路由开销(Overhead)是指在一定时间内节点转发数据包的总数，通常用所有成功到达 目标节点的数据包数与所有节点转发的数据包总数之比来评价。路由开销高，意味着节点大 量地转发数据包，会使网络中充斥大量的数据包副本，增加数据包发生碰撞的概率，也会大 量地消耗节点能量。

3.传输延迟

传输延迟(Delivery Delay)是数据包从源节点到达目标节点所需的时间，通常采用平 均传输延迟来评价。传输延迟小意味路由算法传输能力强、传输效率高，也意味着在传输过 程中将会占用较少的网络资源。

发明内容

本发明涉及一种新的机会网络路由算法，该算法在Epidemic路由算法基础上引入了优先 级机制，该机制可以在不对网络总体性能产生严重影响的前提下，优先转发高优先级数据包。

在机会网络中按照Epidemic路由算法转发数据包，但数据包转发时要满足优先级条件。 有关优先级的描述如下：

1.机会网络中的节点具有发送和接收优先级；

2.节点可采用以下4种方式之一获得初始优先级：

(1)按照一定规则，通过声明确定自己的优先级；

(2)通过对节点移动速度、接口数量、传输速率、传输范围、转发意愿、可用缓存大 小、成功转发概率等因素计算得到优先级；

(3)由管理员规定优先级；

(4)采用默认优先级。

3.节点的发送优先级随时间的增加而增加，一旦节点有数据包被成功发送则该节点发 送优先级恢复到初始优先级；

4.数据包从始发源节点获得初始优先级，当数据包在节点缓存区中存储时其优先级随 时间增加而增加，当数据包被成功发送，数据包的优先级恢复为初始优先级；

5.当源节点的发送优先级和目标节点的接收优先级之和大于阀值时发送源节点中的数 据包；

6.当源节点要发送数据包的优先级和目标节点接收优先级之和大于阀值时发送数据 包。

Epidemic算法的可扩展性较差，当网络规模扩大、网络中传输的数据包增加时，网络性 能会显著下降。在开放性的机会网络中，当有志愿节点加入后，网络规模随之扩大，网络中 固有节点数据包传输会受到影响。而采用基于优先级的Epidemic算法可令机会网络中固有节 点具有较高优先级，保证固有节点数据包的优先传输。换言之，若仅对固有节点而言，基于 优先级的Epidemic算法可以保证机会网络具有较好可扩展性。

在网络规模扩大时，导致Epidemic算法性能下降的主要原因是由于过度泛洪使网络中充 斥大量的数据包副本，大量网络资源被消耗。基于优先级的Epidemic算法抑制了低优先级节 点数据包的传输，减少了网络中数据包副本的数量，在保证高优先级节点数据包传输的同时 可以一定程度地改善网络的总体性能。

附图说明

图1传输成功率比较

图2传输延迟比较

图3路由开销比较

具体实施方式

以下对本发明的原理和特征进行描述，所举实例只用于解释本发明，并非用于限定本发 明的范围。

本发明使用ONE(the Opportunistic Networking Environment)仿真平台实施所涉及 的路由算法。本发明模拟了携有智能蓝牙设备的行人步行于真实的城市场景中，以此来分析 路由算法的性能。具体场景设置如表1所示。

表1仿真场景设置

实施示例1

在本实施例中，将节点分为优先节点和普通节点，设置了2种优先级，具体如表2所示。

表2优先级设置

在表1场景中，以40个优先节点、40个普通节点为例，通过选取不同时间因子分析了 基于优先级Epidemic路由算法的性能。

在算法中，有源节点发送优先级P_s、目标节点接收优先P_r、数据包优先级P_p、时间因子 f_t，等待时间t_w和阀值v_t等多个可变因素，关系如式1所示。由式1可见，上述可变因素之 间是相互关联的，可以通过时间因子的作用来分析不同优先级、阀值设置对网络性能的影响。

P_s+P_r+f_t×t_w＞v_t或P_s+P_p+f_t×t_w＞v_t           式1

以Epidemic路由算法机制为基础，当满足式1条件时，发送数据包，结果如图1至图3 所示。

图1至图3描述了不同时间因子对网络性能影响，图中分别描述了优先节点、普通节点、 总体状况和相应的基线之比，其中总体状况描述了包含所有节点时的情况，基线分别对应相 应的无优先级结果。

由图1可以看出，优先级的引入可以大幅改善优先节点的性能，选择恰当的时间因子可 以在不影响总体性能的同时大大改善优先节点的性能，究其原因是由于优先级机制抑制了普 通节点过度泛洪行为，但当时间因子取值过大是，也会较大程度上影响普通节点的性能。

由图2可以看出，优先节点的传输延迟指标可以显著改善，但时间因子较少小时总体的 传输延迟稍有增加，在时间因子较大时传输延迟虽可大幅改善但相应的传输成功率较差。

由图3可以看出，在优先级机制下，优先节点、普通节点和总体状况的网络开销和时间 因子基本呈线性关系，当时间因子增加时由于抑制了普通节点数据包的转发网络开销随之下 降。

上述对实施例的分析表明，本发明所涉及的算法中，通过对节点优先级和时间因子的设 置可有效减少网络中低优先级节点数据包副本的存在，大幅度改善高优先级节点的性能。恰 当的选取时间因子可在大幅度提高高优先级节点性能的同时，一定程度上改善网络的总体性 能。当时间因子较大时，尽管高优先级节点性能的大幅度提高要以牺牲网络总体性能为代价， 但这也为某些应用场景提供了折衷的手段。