基于节点传输能力的车载散发聚焦路由协议方法

摘要

本发明提出一种基于节点传输能力的散发聚焦路由协议方法，包括多副本散发阶段和单副本聚焦阶段。多副本散发阶段是指当节点拥有某个消息的多个副本时，通过散发消息副本到网络中寻找可能的路径，本方法通过对车辆速度、相遇节点的变化率和剩余缓存大小等因素来衡量节点对消息的传输能力，根据传输能力大小成比例地分配消息散发任务；单副本聚焦阶段是指当节点拥有某个消息的一个副本时，允许节点将唯一消息副本转发给传输能力比自身更高的中集节点，以节点传输能力作为比较条件控制消息的转发。本方法设计缓存管理策略，是采用投递消息确认机制来及时清除冗余消息，结合消息剩余生存时间和可复制副本数为消息分配优先级来确定消息的发送顺序。

说明书

技术领域

本发明涉及车载自组织路由协议车载自组织网络和机会网络技术领域，尤其涉及一种基于节点传输能力的车载散发聚焦路由协议方法。

背景技术

车载自组织网络(Vehicular Ad-hoc Network，VANET)作为目前移动自组织网络最具有前景的领域之一，其技术发展对构建智能交通系统具有重要的意义。而路由协议作为网络互连和数据交换的关键技术，在一定程度上决定了整个车载自组织网络的性能。由于车载自组织网络具有节点移动快、拓扑变化频繁、端到端路径无法保证等特点，造成了传统自组织网络路由协议在车载场景中难以发挥作用。而机会网络是一种不需要信源节点和目标节点之间存在完整的通信链路，而是依靠节点移动创造出的机遇机会，以“存储-携带-转发”机制实现通信的自组织网络，其具有的“容迟容断”特点能很好地满足车载自组织网络的应用需求。间歇性连通的车载网络可视为机会网络的延伸，传统的机会网络消息转发算法对车载网络路由协议设计具有重要的参考价值。

路由协议是机会网络研究的热点问题，也是各种组网技术应当解决的首要问题之一。城市环境下夜晚车辆稀疏，节点要找到更合适的下一跳节点十分困难，此时的VANET可以看成是一种特殊的机会网络，单纯的基于拓扑或基于地理位置的路由协议难以发挥作用。为了提高消息的投递成功率，使用机会网络路由策略不失为一种可行的选择，当然这需要上层的应用能够容忍一定的中断和延时。

传统机会网络路由中基于复制的路由协议的典型代表是Vahdat等人提出的Epidemic协议。协议规定每个节点维护一个消息概要向量(Summary Vector，SV)，SV包含了节点存储的消息信息。当两个节点相遇时，首先交换各自的SV，通过对比自身的SV和对方的SV来确定自己缓存中没有而对方携带的消息，然后向对方发送请求信息，双方仅仅传送对方没有的消息。经过足够的交换后，每一个非孤立的节点都将收到数据，整个过程如同传染病或病毒扩散一样。Epidemic协议理论上能最大化投递成功率，但是大量的消息副本会造成竞争和拥塞。

Prophet协议使用节点之间的传送预测概率和概率的传递性来决定一个节点是否转发消息副本，节点间的交互分为预测概率更新和消息交互两个部分。Prophet协议采用概率大小作为限制条件，减少了Epidemic协议的盲目性，但是并没有严格限制网络中的消息副本数量，容易产生负担过重的关键节点。

为了减少网络资源的大量消耗，Spyropoulos等人提出Spray and Wait协议来限制路由开销。该协议在Spray阶段与Epidemic类似，将消息副本散布到网络中，但是限制了副本数量的上限。当网络中已经存在规定数量的副本后则进入Wait阶段。在Wait阶段则不再复制消息，消息副本的数量不会增加，而是由携带消息副本的节点完成直接递交(Direct Delivery)。大量的实验表明，Spray and Wait协议的开销显著小于Epidemic协议，并且平均延迟小，投递成功率高，可以适应不同规模的网络，目前有许多路由协议是由Spray and Wait协议扩展而来。

Spray and Wait路由协议虽然通过限制最大消息副本数减少了消息传递过程中的开销，但是同时也存在着一些不足之处。

在节点状态无差别的情况下，Spray and Wait协议采用二分散发方式具有最快的消息扩散速度，但是若应用在车载机会网络中，缺乏对网络信息和节点传输能力的有效利用，只是简单地将消息转发给相遇的新节点，具有明显的盲目性和随机性。

Spray and Wait在进入等待阶段时，携带消息的节点采用直接交付的方式，尽管这样限制了消息的转发次数，但却错失了将消息转发给比自身更加合适的中继节点的机会，导致消息投递成功率降低，消息延迟增大。

Spray and Wait采用了“存储-携带-转发”的机制，但是缺乏合适的缓存管理策略。无论是源节点或携带消息的中继节点在遇到目的节点递交消息后，其他节点并不清楚该消息已经投递成功，保存在缓存中的消息只有在TTL到期或者缓存已被填满的情况下才被节点丢弃。在节点的存储空间有限的情况下，可能会使缓存的有效利用率降低，当缓存空间不足时失去接收消息的机会。

如何在上述Spray and Wait协议基础上，改进其无差别二分散发方式、突破等待阶段只能直接交付消息的限制以及采取更合理的缓存管理策略，成为该协议扩展的要点。

发明内容

针对上述Spray and Wait路由协议的不足之处，本发明在Spray and Wait路由协议的基础上提出一种基于车辆节点传输能力的散发聚焦(Transmission Capability Based Spray and Focus Routing，TC-SaF)路由协议。TC-SaF路由协议分为多副本散发阶段和单副本聚焦阶段，TC-SaF引入了一个传输能力函数，综合考虑了车辆节点的移动速度、缓存空间和相遇节点变化率，在散发阶段，相较于Spray and Wait无差别二分散发，本协议为传输能力更高的节点分配更多的副本，在聚焦阶段以车辆节点传输能力作为比较条件控制消息的转发。TC-SaF路由协议还采用了相应的缓存管理策略降低消息副本的冗余程度，合理利用缓存资源。

本发明通过以下技术方案实现，包括如下步骤：

一种基于节点传输能力的车载散发聚焦路由协议方法，其特征在于，包含以下步骤：

步骤1：节点相遇阶段；每个车辆节点维护一个历史相遇节点集合，当遇到一个新节点时，将该新节点的ID和相遇时间加入历史相遇节点集合中，如果两节点在短时间内再次相遇，则更新相遇时间，如果车辆节点在指定时间长度内未与该节点相遇，则将对应记录从集合中删除；车辆节点周期性地对比当前周期起始时刻与当前时刻的集合，计算相遇节点的变化率；

步骤2：连接建立阶段；当节点N_i确定与另一个节点N_j建立连接后，节点首先将已投递消息概要向量DMSV和消息摘要向量MSV发送给对方；节点N_j收到N_i发给自己的DMSV后，根据其信息更新自己维护的DMSV，同时删除自己缓存中的已被成功投递的消息；根据N_i发送的MSV与自己的MSV做逻辑与运算，判断哪些消息是节点N_i携带而自身没有的，N_j将这些信息和自己的DMSV封装在Request消息中发给节点N_i，向节点N_i请求消息发送；

步骤3：Request消息处理阶段；节点N_i收到Request消息后，向节点N_j逐一发送请求的消息，包含以下几种情况的处理：

d)如果节点N_j是消息m的目的节点，节点N_i将消息发送给节点N_j，然后将其从自己的缓存中删除，同时更新DMSV；

e)如果节点N_j不是消息m的目的节点，同时消息m当前的副本数大于1，则执行步骤4散发阶段的操作；

f)如果节点N_j不是消息m的目的节点，同时消息m当前副本数等于1，则执行步骤5聚焦阶段的操作；

步骤4：消息副本散发阶段；节点N_i计算自己和对方节点的综合传输能力，再根据综合传输能力计算需要散发和保留的副本数，将消息m副本发送给节点N_j，同时修改自己携带的消息m的副本数，按优先级重新加入缓存中；

步骤5：消息聚焦阶段；节点N_i计算自己和对方节点的综合传输能力，再判断消息转发条件是否满足，如果满足，则向节点N_j转发消息，否则不予转发；

步骤6：消息接收阶段；节点N_j逐一接收节点N_i发送过来的消息，如果收到的消息的目的节点是本身，则直接对消息进行处理并进行消息投递确认，不再将其放入缓存；否则在将消息放入缓存之前执行拥塞检测，包含以下两种情况的处理：

c)缓存充足，节点N_j遍历缓存，计算消息的优先级，并将消息插入队列中的合适位置；

d)缓存不足，节点N_j比较消息和缓存队尾消息的优先级；如果队尾消息优先级大于新到来的消息m，则直接丢弃消息m；如果队尾消息优先级较低，则丢弃队尾消息，重复执行b)步骤直至缓存充足，执行a)步骤。

相遇节点变化率用以衡量节点活跃度，反映了节点在一定的时间间隔内其周围节点的变化情况。优选的，步骤1中车辆节点和新节点的相遇节点变化率可通过下式计算得到：

$H_i=\frac{\left|H_{T_2}\cup H_{T_1}\right|-\left|H_{T_2}\cap H_{T_1}\right|}{\Delta T}$

其中为节点N_i在T₁时刻的相遇节点集合，为T₂时刻的相遇节点集合，以ΔT＝T₁-T₂作为更新周期。

优选的，已投递消息向量DMSV和消息概要向量MSV被封装在Request消息中进行交互，其中DMSV保存的是自身节点获知的已投递成功消息的概要信息向量，MSV保存的是存在自身节点缓存中的消息的概要信息向量。

优选的，每个节点引入一个综合传输能力函数，步骤4和步骤5所用到的节点综合传输能力是根据相遇时两节点的状态信息计算得到的，每个节点的综合传输能力考虑以下因素：相对传输能力值、针对各个要素的考量的调整因子；根据节点的相对传输能力和调整因子，可由下面两式分别计算得到两个节点的综合传输能力值：

$\left(\begin{array}{c}{C}_i={\omega }_i{U}_i\\ C_j={\omega }_j{U}_j\end{array}\right)$

其中ω为调整因子，U为相对传输能力值。

优选的，两个相遇节点N_i和N_j的相对传输能力计算考虑两个节点的速度大小、剩余缓存大小和相遇节点变化率三个影响因素，由下面两式计算可得节点N_i和N_j的相对传输能力值：

$U_i=\alpha \times \frac{V_i}{V_i+V_j}+\beta \times \frac{B_i}{B_i+B_j}+\gamma \times \frac{H_i}{H_i+H_j}$

$U_j=\alpha \times \frac{V_j}{V_i+V_j}+\beta \times \frac{B_j}{B_i+B_j}+\gamma \times \frac{H_j}{H_i+H_j}$

其中，V为节点行驶速度大小，B为剩余缓存大小，H为相遇节点变化率，而α、β和γ分别为针对节点移动速度、剩余缓存大小和相遇节点变化率预设的加权系数并且α+β+γ＝1。

优选的，在计算节点综合传输能力时，引入一个调整因子ω，即考虑缓存资源的可用等级，根据缓存可用等级对传输能力的计算进行相应的衰减，调整因子的计算方式如下：

ω＝(1+λ)^-d

其中λ是固定调整值，根据实际情况选取，在TC-SaF协议中设λ＝1，d是缓存资源的可用等级；

实际应用中可用等级按照不同的门限值进行划分：

可用等级剩余缓存范围缓存情况0B≥th2缓存充足，可以正常使用1th1≤B<th2缓存紧张，应当适当减少消息的接收20<B<th1缓存即将溢出

由于缓存可用等级的取值为非负的整数，上式保证了调整因子ω的取值范围为(0,1]；

或调整因子根据下式获得：

$\omega =\underset{i=1}{\overset{N}{\Pi }}{(1+{\lambda }_i)}^{-d_i}={(1+{\lambda }_1)}^{-d_1}{(1+{\lambda }_2)}^{-d_2}...{(1+{\lambda }_N)}^{-d_N}$

其中λ_i为第i个因素的固定调整值，d_i为对应第i个因素的重要性等级。

优选的，步骤4中消息副本散发阶段，散发和保留的副本数可由下式计算得到：

L_i＝L_cur-L_j

其中L_cur为节点N_i当前持有副本数，C_i为节点N_i综合传输能力值，C_j为节点N_j综合传输能力值，L_i为节点N_i保留副本数，L_j为散发给节点N_j的副本数。

优选的，步骤5的消息转发条件由两节点综合传输能力和两车辆节点的行驶方向两个因素决定，计算两个节点N_i和N_j的行驶方向可由下式得到：

${\theta }_i={\tan }^{-1}\frac{y_i}{x_i},{\theta }_j={\tan }^{-1}\frac{y_j}{x_j}$

其中，(x_i,y_i)和(x_j,y_j)分别为两个节点的速度向量在X轴和Y轴上的坐标，θ_i、θ_j分别表示节点N_i、节点N_j的行驶方向，并能够得到两个节点的相遇角度φ_i,j：

${\phi }_{i,j}=\left(\begin{array}{ccc}\left|{\theta }_i-{\theta }_j\right|,& if& \left(\right|{\theta }_i-{\theta }_j|\le \pi )\\ 2\pi -\left|{\theta }_i-{\theta }_j\right|,& if& \left(\right|{\theta }_i-{\theta }_j|>\pi )\end{array}\right)$

是否转发的判断条件如下式：

(φ_i,j＜π/2)∩(C_j＞C_i+C_th)

如果以上条件为真，则转发；其中，,、C_i为节点N_i的综合传输能力值，C_j为节点N_j的综合能力传输值，C_th是预设的门限值，目的是提高转发条件。

优选的，步骤6目的节点的消息投递确认采用主动式消息投递确认机制，即主动分发ACK信息；每个节点维护一个已投递成功消息向量DMSV，每当有以此节点作为目的节点的消息投递成功后，向该表中添加已经投递成功的消息ID，两个节点相遇时除了发送Hello和Echo消息外，还需要进行DMSV的交互；节点在获得对方的DMSV后，根据其中包含的信息对自己维护的已投递成功消息记录表进行更新，与此同时，令自己的缓存中存在相同ID的消息则将其删除。

优选的，每个节点的缓存管理由消息优先级分配机制决定；缓存中的消息m有当前生存时间TTL_cur与初始生存时间TTL_init，那么具有L_cur个副本的消息m不能被成功投递的概率可以表示为：

$P_n={(1-\frac{{\mathrm{TTL}}_{cur}}{{\mathrm{TTL}}_{init}})}^{L_{cur}}$

定义消息m的优先级别的计算方法如下：

$P_m=1-P_n=1-{(1-\frac{{\mathrm{TTL}}_{cur}}{{\mathrm{TTL}}_{init}})}^{L_{cur}}$

在该机制中，消息当前的生存时间TTL_cur越长，可复制的副本数L_cur越多，此概率值越高，节点将优先发送和缓存该消息。

与现有技术相比，本发明的优点如下：

(1)本发明描述的多副本散发阶段和单副本聚焦转发阶段结合了单副本和多副本两种策略，可以看做是在网络开销和性能方面的一种权衡(Trade-off)。本发明借鉴了Spray and Wait协议的思想，通过设置固定的可复制消息副本数，使得消息不会无限制地泛洪，即提高了投递成功率，又避免节点增多时出现严重的拥塞现象。

(2)本发明描述的副本散发和副本转发考虑了节点的传输能力，选择具有较多通信机会和缓存空间充足的节点来承担较多的复制散发任务，克服了Spray and Wait的盲目性，均衡了节点的负载，不至于造成消息副本过快地在传输能力较差的节点间散发完毕，使得消息扩散不够充足而降低投递成功率并增大时延。同时基于传输能力的聚焦阶段可以使消息的单一副本从能力较差的节点转移到能力更高的节点，有助于延长消息的生存时间。

(3)本发明描述的缓存管理策略基于消息优先级设置机制。使用生存时间和可复制副本数计算出消息优先级，对消息进行合理的调度，丢弃过期和优先级低的消息，避免出现消息未充分扩散却无法获得资源的现象。

(4)相比Spray and Wait，更适合车辆节点差异化的实际车载自组织网络。

附图说明

图1为本发明协议流程图。

图2为本发明缓存管理流程图。

图3为缓存消息队列图。

具体实施方式

附图仅用于示例性说明，不能理解为对本专利的限制，以下将结合附图对本发明做进一步的描述。

一种基于节点传输能力的车载散发聚焦路由协议方法，包括以下步骤：

步骤1：每个车辆节点维护一个历史相遇节点集合，当遇到一个新节点时，该节点的ID和相遇时间加入集合中，如果两节点在短时间内再次相遇，则更新相遇时间，如果长时间未与该节点相遇，则将对应记录从集合中删除。节点周期性地对比当前周期起始时刻与当前时刻的集合，计算相遇节点的变化率。此外，每个节点同时记录自身的行驶速度大小和剩余缓存大小等信息。

步骤2：当节点N_i确定与另一个节点N_j建立连接后，节点首先将已投递消息概要向量DMSV和消息摘要向量MSV发送给对方。

步骤3：节点N_j收到N_i发给自己的DMSV后，根据DMSV中的信息更新自己维护的已投递消息记录表，同时删除自己缓存中的已被成功传输到目的节点的消息；根据N_i发送的MSV与自己的MSV做逻辑与运算，判断哪些消息是节点N_i携带而自身没有的，N_j将这些信息和自己的DMSV封装在Request消息中发给节点N_i，向节点N_i请求消息发送。

步骤4：节点N_i收到Request消息后，向节点N_j逐一发送请求的消息，包含以下几种情况的处理：

a)如果N_j是消息m的目的节点，N_i将消息发送给N_j，然后将其从自己的缓存中删除，同时更新DMSV；

b)如果N_j不是消息m的目的节点，同时消息m当前的副本数大于1，则执行散发阶段的操作，计算自己和对方节点的综合传输能力，再根据综合传输能力值计算需要散发和保留的副本数，将消息m副本发送给节点N_j，同时修改自己携带的消息m的副本数，按优先级重新加入缓存中；

c)如果N_j不是消息m的目的节点，同时消息m当前副本数等于1，则执行聚焦阶段的操作，计算自己和对方节点的综合传输能力，再判断消息聚焦转发条件能否满足，如果满足，则向N_j转发消息，否则不予转发；

步骤5：节点N_j逐一接收N_i发送过来的消息，在将每一个消息放入缓存之前执行拥塞检测，包含以下两种情况的处理：

a)缓存充足，节点N_j遍历缓存，根据消息优先级机制计算消息的优先级，并将消息插入队列中的合适位置。

b)缓存不足，节点N_j比较消息和缓存队尾消息的优先级。如果队尾消息优先级大于新到来的消息m，则直接丢弃消息m；如果队尾消息优先级较低，则丢弃队尾消息，重复执行b)步骤直至缓存充足，执行a)步骤。

步骤6：节点N_j接收到以自己为目的节点的消息后，更新DMSV。

步骤7：节点N_i和N_j完成消息的传输，各自等待与其它节点的下一次相遇。发明的有益性

本发明提出的TC-SaF协议分利用了可获取的节点相关信息并充分考虑了资源的受限性，通过综合传输能力来使消息副本在网络中的复制和转发更具有针对性，在投递成功率和平均投递延迟方面取得了一定的改善效果。采用主动式消息投递确认机制较好地解决了消息成功投递后消息其他副本仍存在于网络其他节点的问题，使用消息优先级分配机制的缓存管理策略很好地控制了网络拥塞的问题，且对优先消息的优先散发投递一定程度上提高了消息投递的成功率。