一种VANET中可提供长连接服务的路由选择方法

摘要

本发明公开一种VANET中可提供长连接服务的路由选择方法，依次包括路由发现、路由回复、路由建立和路由保持四个步骤。本发明中的源节点通过广播可以使得目的节点获取多个源节点到达目的节点的路由路径，目的节点在将这些路由路径回复给源节点的同时，在优先考虑路由跳数的情况下，基于节点间的运动模式相似度和距离等信息来筛选出具有最长网络服务时间的链路，源节点在收到目的节点的路由回复的同时便可获得最佳的路由发送路径而无需再次进行路由路径的筛选，简单快速有效。

说明书

技术领域

本发明涉及通信技术，具体涉及一种VANET中可提供长连接服务的路由选择方法。

背景技术

车联网是以车辆为基本信息单元，通过传感器技术、信息采集技术、数据传输和接收技术、自组网技术等将车辆的位置、速度和路线等信息传送至道路上的其他车辆、路边设施和互联网的巨大交互网络。车联网中车辆高速移动并且需要快速的移出当前所在网络或者加入一个新的网络，这些因素都将导致网络拓扑结构快速变化、路径寿命短。

目前，VANET下的路由协议主要分为基于拓扑、基于位置和基于地图三类，陆建胜等人在2014年4月的《科学技术与工程》中“基于节点梯度的车辆网络(VANET)路由算法”通过计算节点的梯度值来选择梯度值最大的节点作为下一跳的转发节点。在计算节点梯度值时，考虑到节点与目标节点的距离、节点的移动方向、节点的负荷以及节点的邻居节点数目等因素。尽管这一做法可以在很大程度上提高路由性能，但是该算法需要周期性广播节点自身的位置、处理负荷、邻居节点数目、移动速度和移动方向等信息，需要消耗较多的网络资源。每个节点都需要计算自身一跳内节点的梯度值，需要消耗大量的计算资源。并且计算节点梯度并未考虑到相邻节点的相对速度和加速度等因素，会导致路由路径断裂时间过快，无法满足需要较长时间的网络服务要求。

王佩雪等人在2014年9月的《科学技术与工程》中“VANETs中基于链路的可持续时间路由方案”通过源节点在发起路由发现的过程中，链路上的每个节点都将估算自己与上一跳节点间的链路可持续时间，目的节点将每条链路上的最小可持续时间看为整条链路的可持续时间，选择具有最大可持续时间的链路进行路由回复。尽管这一做法在某种程度上可以获取当前消息源节点到达目的节点的多条路由路径中可存在时间最长的一条路由路径，但该方法在路由发现时要求网络中路由广播覆盖范围内的所有节点使用GPS获取自身位置并花费大量的计算能力用于可持续时间的计算，增加了路由发现所需要的时间，节点间的路由发现 广播包中要包含节点的位置、速度、方向以及目的节点信息，这将照成广播包携带过多的信息，增大了广播开销。节点计算得到的可持续时间也仅为估算值，无法很好的衡量链路的实际可存在时间。

发明内容

发明目的：本发明的目的在于解决现有的VANET中由于拓扑频繁变化造成链路无法提供较长时间连接网络服务的问题，针对车联网中某些上层应用(如视频通话)需要较长时间连接的网络服务，提供一种VANET中可提供长连接服务的路由选择方法。

技术方案：本发明所述的一种VANET中可提供长连接服务的路由选择方法，依次包括路由发现、路由回复、路由建立和路由保持四个步骤，

(1)路由发现阶段包括以下两个步骤：

(11)源节点S需要将数据包发送到一个目的节点时，源节点S创建一个路由发现包RD，然后将RD数据包广播给所有的邻居节点；其中，路由发现包RD的首部包括有源节点S的网络地址和位置信息、目的节点的网络地址以及一个默认长度为12的空路由路径列表Seq；

(12)邻居节点收到RD数据包后，首先判断本节点是否为目的节点；如果是目的节点则转到(2)执行；否则根据<源节点网络地址，广播ID>判断是否属于重复接收，若重复接收，则丢弃该消息；如果本节点不是目的节点，则将本节点的网络地址添加入路由路径列表Seq中的第一个非空位置，再判断RD数据包首部中携带的路由列表是否已满，若已满则丢弃该数据包，未满则继续向自己的邻居节点广播该数据包；

(2)路由回复阶段，目的节点收到RD数据包后，将自己的网络地址加入到RD数据包首部的Seq列表中的第一个非空位置，若目的节点为第一次收到来自该源节点的RD数据包，则该目的节点设置一个计时器，当计时器到时后，目的节点统计当前获取的所有来自该源节点的RD数据包；

(3)路由建立阶段，在路由路径的选择过程中，路由表中RR数据包最终使用的路由路径的优先级值在不断增加，当RR数据包到达源节点时，RR数据包首部的路由表中有一条路由路径的优先级最高，该路径即为通过对节点运动模式的相似度进行对比后得到的最优路径，源节点将按照RR数据包中记录的最优路由 路径进行数据传输；

(4)路由保持阶段，源节点若在一段时间内没有收到目的节点的消息接收确认，则认为当前使用的路由路径已经断开连接；此时源节点提取RR数据包首部中记录的其它路由路径，按照路由路径的优先级顺序通过这些路由路径使用发送路由确认RC数据包至目的节点，目的节点在收到RC数据包后按照原接收路径返回确认字符ACK数据包，源节点使用最先接收到的ACK数据包中记录的路由路径进行数据传输；若源节点在时间阀值t内未接收到来自目的节点的ACK数据包则认为当前记录的全部路径均失效，重新进行路由发现。

进一步的，所述步骤(2)中，

若计时器计时的这段时间内，目的节点只收到一个RD数据包，则直接将RD数据包首部记录的路由路径复制到路由回复RR数据包的首部，并添加目的节点的速度和位置信息在RR数据包的首部；然后RR数据包将沿着其首部记录的唯一路线转发至源节点；

若目的节点在计时器到时后收到m个RD数据包，取每个RD数据包中记录节点的个数记为此RD数据包携带的路由路径跳数；若跳数最小的路径比跳数次小的路径跳数差大于2(选择2作为比较标准，是因为优先考虑路由路径长度的缘故，其他数值亦可)，则将跳数最小的RD数据包中的记录路线复制到RR的首部中并发送；

若跳数最小的路径比跳数次小的路径跳数差小于或等于2，则将收到的m个RD数据包按照到时达时间顺序给予编号i，然后新建一个m行13列的路由表，将代表路由路径的优先级的第一列清0，再将RD数据包中包含的Seq列表中的路由路径从每行的第二位开始倒序拷贝入对应的行；最后目的节点将路由表拷贝至RR数据包的首部并添加自身当前的位置、速度信息和一个初始值为3的index指针变量；

其中，m>1，0<i<m+1；由于RD数据包中记录路径用的Seq列表长度为12，即认为路由路径长度超过12的路径为不可达路径，这里将路由表的列数取13是因为其中12列用于存放Seq列表中数据的拷贝，另外一列即第一列用于存放路由路径的优先级值，13可用列表Seq长度加一的值来代替；将指针变量的初始值设为3是因为，所有的路由路径为倒序拷贝入路由表的行中的，每行的第一列为优先级 位，第二列为目的节点自身的地址，第三列才是第一个可能出现不同值(即代表下一跳节点不唯一)的列。

进一步的，所述目的节点在生成RR数据包或其他节点(这里的其他节点泛指除了目的节点之外的所有网内节点，RR数据包只能由目的节点生成，由目的节点之外的节点转发)在接收到RR数据包后，在只考虑路由表优先级为最大值的行的情况下，对路由表的第index列的网络地址进行比较：若下一跳节点唯一，则将index值加1并保存后，将RR数据包发送至该唯一的下一跳节点；否则拥有RR数据包的节点生成请求相似度值RFS数据包，RFS数据包首部携带本节点的网络地址、速度、行驶方向、加速度和位置信息并发送至所有待选的下一跳节点，下一跳节点计算出相似度S值后，并将S值使用答复相似度值AFS数据包回复至拥有RR数据包的节点，拥有RR数据包的节点收到AFS数据包后，将路由表中所有下一跳节点为该具有最小的S值的节点的路由路径的优先级值加1，将index的值加一保存后发送RR数据包至最小的S值对应的下一跳节点。

上述下一跳节点计算得到S值的具体过程为：

节点接收到RFS数据包后，获得RFS数据包首部携带上一跳节点的位置坐标(x_i,y_i)、速度v_i、加速度a_i和行驶方向θ_i，并获取节点自身的位置坐标(x，y)、速度v、加速度a和行驶方向θ，假设所有节点的有效通信半径相同并取节点的有效通信半径为R；

由位置坐标计算出两个节点间距离为

若cos(θ-θ_i)<0，即认为两节点行驶方向相反，则

$S=(\frac{2|D-\frac{R}{2}|}{R}+\frac{|v-v_i|}{v_{\lim }}+1+\frac{\cos (\theta -{\theta }_i)+1}{2})/4,$

若cos(θ-θ_i)>＝0，即认为两节点行驶方向相同，则

$S=(\frac{2|D-\frac{R}{2}|}{R}+\frac{|v-v_i|}{v_{\lim }}+\frac{|a-a_i|}{a_{\lim }}+\frac{\cos (\theta -{\theta }_i)+1}{2})/4,$

其中，v_lim、a_lim为一个值为正的门限值，不同的门限值可以调整相对速度和相对加速度对于S值得权重。

进一步的，步骤(2)中若有多个待选的下一跳节点即下一跳节点不唯一时， 分别计算上一跳节点与下一跳节点的相似度值，选择具有最小相似度值的节点作为路由回复数据包的下一跳转发节点。

有益效果：与现有技术相比，本发明具有以下优点：

(1)本发明中的源节点通过广播可以使得目的节点获取多个源节点到达目的节点的路由路径，目的节点在将这些路由路径回复给源节点的同时，在优先考虑路由跳数的情况下，使用基于节点间的运动模式相似度和距离等信息来筛选出具有最长网络服务时间的链路，源节点在收到目的节点的路由回复的同时便可获得最佳的路由发送路径而无需再次进行路由路径的筛选，简单快速有效；

(2)本发明在路由回复阶段而不是在路由发现阶段进行路径筛选，可以避免网络内被RD数据包广播覆盖范围内的所有节点花费大量计算能力用于路径筛选，仅由可用路由路径上的公用节点进行路径筛选即可；

(3)本发明用节点间的运动模式的相似度来评估节点在未来一段时间内可持续通信时间更为准确，因为车辆往往会和周边与自身运动模式相似的车辆在一段时间后依旧保持着邻居关系。

附图说明

图1为本发明中路由发现阶段的流程图；

图2为本发明中路由回复阶段的流程图；

图3为本发明中路由路径选择的流程图。

具体实施方式

下面对本发明技术方案进行详细说明，但是本发明的保护范围不局限于所述实施例。

如图1和图2所示，本发明的本发明所述的一种VANET中可提供长连接服务的路由选择方法，依次包括路由发现、路由回复、路由建立和路由保持四个步骤，

(1)路由发现阶段包括以下两个步骤：

(11)源节点S需要将数据包发送到一个目的节点时，源节点S创建一个路由发现包RD，然后将RD数据包广播给所有的邻居节点；其中，路由发现包RD的首部包括有源节点S的网络地址和位置信息、目的节点的网络地址以及一个默认长度为12的空路有路径列表Seq；

(12)邻居节点收到RD数据包后，首先判断本节点是否为目的节点；如 果是目的节点则转到(2)执行；否则根据<源节点网络地址，广播ID>判断是否属于重复接收，若重复接收，则丢弃该消息；如果本节点不是目的节点，则将本节点的网络地址添加入路由路径列表Seq中的第一个非空位置，再判断RD数据包首部中携带的路由列表是否已满，若已满则丢弃该数据包，未满则继续向自己的邻居节点广播该数据包。

(2)路由回复阶段，目的节点收到RD数据包后，将自己的网络地址加入到RD数据包首部的Seq列表中的第一个非空位置，若目的节点为第一次收到来自该源节点的RD数据包，则该目的节点设置一个计时器，当计时器到时后，目的节点统计当前获取的所有来自该源节点的RD数据包；

若计时器计时的这段时间内，目的接点只收到一个RD数据包，则直接将RD数据包首部记录的路由路径复制到路由回复RR数据包的首部，并添加目的节点的速度和位置信息在RR数据包的首部；然后RR数据包将沿着其首部记录的唯一路线转发至源节点；

若目的节点在计时器到时后收到m个RD数据包，取每个RD数据包中记录节点的个数记为此RD数据包携带的路由路径跳数；若跳数最小的路径比跳数次小的路径跳数差大于2，则将跳数最小的RD数据包中的记录路线复制到RR的首部中并发送；

若跳数最小的路径比跳数次小的路径跳数差小于或等于2，则将收到的m个RD数据包按照到时达时间顺序给予编号i，然后新建一个m行13列的路由表，将代表路由路径的优先级的第一列清0，再将RD数据包中包含的Seq列表中的路由路径从每行的第二位开始倒序拷贝入对应的行；最后目的节点将路由表拷贝至RR数据包的首部并添加自身当前的位置、速度信息和一个初始值为3的index指针变量；其中，m>1，0<i<m+1。

上述目的节点在生成RR数据包或其他节点在接收到RR数据包后，在只考虑路由表优先级为最大值的行的情况下，对路由表的第index列的网络地址进行比较：若下一跳节点唯一，则将index值加1并保存后，将RR数据包发送至该唯一的下一跳节点；否则拥有RR数据包的节点生成请求相似度值RFS数据包，RFS数据包首部携带本节点的网络地址、速度、行驶方向、加速度和位置信息并发送至所有待选的下一跳节点，下一跳节点计算出S值后，并将S值使用答复相似度值AFS 数据包回复至拥有RR数据包的节点，拥有RR数据包的节点收到AFS数据包后，将路由表中所有下一跳节点为该具有最小的S值的节点的路由路径的优先级值加1，将index的值加一保存后发送RR数据包至最小的S值对应的下一跳节点。

上述下一跳节点计算得到S值的具体过程为：

节点接收到RFS数据包后，获得RFS数据包首部携带上一跳节点的位置坐标(x_i,y_i)、速度v_i、加速度a_i和行驶方向θ_i，并获取节点自身的位置坐标(x，y)、速度v、加速度a和行驶方向θ；

由位置坐标计算出两个节点间距离为

若cos(θ-θ_i)<0，即认为两节点行驶方向相反，则

$S=(\frac{2|D-\frac{R}{2}|}{R}+\frac{|v-v_i|}{v_{\lim }}+1+\frac{\cos (\theta -{\theta }_i)+1}{2})/4,$

若cos(θ-θ_i)>＝0，即认为两节点行驶方向相同，则

$S=(\frac{2|D-\frac{R}{2}|}{R}+\frac{|v-v_i|}{v_{\lim }}+\frac{|a-a_i|}{a_{\lim }}+\frac{\cos (\theta -{\theta }_i)+1}{2})/4,$

其中，v_lim、a_lim为一个值为正的门限值，不同的门限值可以调整相对速度和相对加速度对于S值得权重。

(3)路由建立阶段，在路由路径的选择过程中，路由表中RR数据包最终使用的路由路径的优先级值在不断增加，当RR数据包到达源节点时，RR数据包首部的路由表中有一条路由路径的优先级最高，该路径即为通过对节点运动模式的相似度进行对比后得到的最优路径，源节点将按照RR数据包中记录的最优路由路径进行数据传输。

(4)路由保持阶段，源节点若在一段时间内没有收到目的节点的消息接收确认，则认为当前使用的路由路径已经断开连接；此时源节点提取RR数据包首部中记录的其它路由路径，按照路由路径的优先级顺序通过这些路由路径使用发送路由确认RC数据包至目的节点，目的节点在收到RC数据包后按照原接收路径返回确认字符ACK数据包，源节点使用最先接收到的ACK数据包中记录的路由路径进行数据传输；若源节点在时间阀值t内未接收到来自目的节点的ACK数据 包则认为当前记录的全部路径均失效，重新进行路由发现。

实施例：

如图3所示，节点A为消息的源节点，节点D为消息的目的节点，节点B和节点C为网络中的其他节点。其中节点A和节点B、C可直接通信，节点D也可与节点B、C直接通信，但节点A与节点D不可直接通信，节点B与节点C不可直接通信。假设节点A、B、C、D的网络地址分别为192.168.1.2、192.168.1.3、192.168.1.4、192.168.1.5。

路由发现：源节点A创建一个路由发现数据包RD，将该RR数据包广播给所有的邻居节点。邻居节点B和节点C在接收到该RR数据包后，首先判断本节点是否为目的节点，再判断是否为重复接收，若重复接收，则丢弃该消息；节点B和节点C在判断后得知自己不是目的节点并且未重复接收，则将自己的网络地址添加入路由路径列表Seq中的第一个非空位置，由于此时路由路径未满，则继续向自己的邻居节点广播该RD数据包。

路由回复：假设目的节点D先接收到来自于节点C的RD数据包，则设置一个计时器，计时器到时后节点D共收到来自于节点C和节点D的两条RD数据包，则生成如表1所示的路由表，

表1

优先级 目的节点地址 其他节点地址 源节点地址 0 192.168.1.5 192.168.1.3 192.168.1.2 0 192.168.1.5 192.168.1.4 192.168.1.2

将上述路由表携带于RR数据包的首部，并准备将RR数据包通过该路由表中的某条路径发送至源节点。节点D通过比较得知在第三列中的网络地址不相同，即路由回复过程中下一跳节点不唯一，则节点D分别向节点B和节点C发送RFS数据包。

假设节点B、C、D的速度分别为12m/s、9m/s、10m/s，加速度分别为2m/s²、0.5s²、1m/s²,位置分别为(100，300)、(100，100)、(200，200)，行驶方向θ均为0，节点有效通信距离R为200m，门限值v_lim、a_lim分别为10m/s和5m/s²。

节点B在接收到节点D发送的RFS数据包后，由于cos(θ-θ_i)>＝0，即认为 两节点行驶方向相同，则

$\left(\begin{array}{c}S1=(\frac{2|D-\frac{R}{2}}{R}+\frac{|v-v_i|}{v_{\lim }}+\frac{|a-a_i|}{a_{\lim }}+\frac{\cos (\theta -{\theta }_i)+1}{2})/4\\ =(\frac{2|100\sqrt{2}-100|}{200}+\frac{|12-10|}{10}+\frac{|2-1|}{5}+\frac{\cos (0-0)+1}{2})/4\\ =0.4525\end{array}\right)$

节点B将计算得到的S1值存入AFS数据包中并发送至节点D。

节点C在接收到节点D发送的RFS数据包后，由于cos(θ-θ_i)>＝0，即认为两节点行驶方向相同，则

$\left(\begin{array}{c}S2=(\frac{2|D-\frac{R}{2}}{R}+\frac{|v-v_i|}{v_{\lim }}+\frac{|a-a_i|}{a_{\lim }}+\frac{\cos (\theta -{\theta }_i)+1}{2})/4\\ =(\frac{2|100\sqrt{2}-100|}{200}+\frac{|9-10|}{10}+\frac{|0.5-1|}{5}+\frac{\cos (0-0)+1}{2})/4\\ =0.4025\end{array}\right)$

节点C将计算得到的S2值存入AFS数据包中并发送至节点D。

若取更大的v_lim、a_lim值，则S值会相对应的变小。取更小的v_lim、a_lim值，则S值会相应的变大。取合适的v_lim、a_lim值可以平衡速度差值和加速度差值对于S值的影响。

节点D在得到节点B、D之间的相似度值S1以及节点C、D之间的相似度值S2后，比较S1和S2值可知S2值最小，即代表节点C和节点D的运动模式相似度最高，则节点D将RR数据包中的路由表更新为表2，

表2

优先级 目的节点地址 其他节点地址 源节点地址 0 192.168.1.5 192.168.1.3 192.168.1.2 1 192.168.1.5 192.168.1.4 192.168.1.2

并将RR数据包通过节点C发送至节点A。

路由建立：源节点A在收到该RR数据包后，由于A->C->D这条路由路径具有最高的优先级，则使用该路由路径进行数据转发。

路由保持：若节点A在一段时间内没有收到来自节点D的消息接收确认，则认为当前使用的路由路径已经断开连接；此时节点A按照表2中的路由路径的优先级顺序发送RC数据包至节点D，即现使用A->C->D这条路径发送RC数据包，再使用A->B->D这条路径发送RC数据包。节点A使用最先接收到的ACK数据包中记录的路由路劲进行数据传输；若节点A在时间阀值t内未接收到来自节点D的ACK数据包则认为当前记录的全部路由路径均失效，需要重新进行路由发现。

通过上述实施例的过程以及结果可以看出，应用本发明中的路由选择方法，能够节省大量路径筛选时间，简单快速精准。