一种基于路网和QOS模型的车载网GPSR协议改进方法

摘要

本发明公开了一种基于路网和QOS模型的车载网GPSR协议改进方法，包括：S1、建立路网模型，源节点查询自身以及目的节点的坐标和所处路段属性；S2、若目的节点在通信范围内，则直接转发；否则启用贪婪转发模式；S3、转发过程中，计算得到QOS属性数据对通信链路的服务质量进行衡量，并生成候选转发节点列表；S4、若候选转发节点列表不为空，则继续贪婪转发；否则启用路由恢复策略中的携带转发机制；S5、当数据分组陷入局部最优路口时，启用周边恢复模式选择转发路段；S6、当数据分组跨过局部最优路口时，重复执行步骤S2‑S5，直到抵达目的节点。本发明提高了GPSR协议的链路质量，降低投递率受速度的影响，且低节点密度适应性较好。

说明书

技术领域

本发明涉及车载自组织网络通信技术领域，尤其涉及一种基于路网和QOS模型的车载网GPSR协议改进方法。

背景技术

车载自组织网络(Vehicular Ad-Hoc Network,VANET)通过车车、车路和车人之间的信息共享，实现智能交通协同控制。在未来智能交通体系中，无线技术发挥着至关重要的作用[2]。车辆移动速度等大量数据被聚合在一起，并被周期性地广播出去,服务于智能交通系统。车联网中需要进行远距离的数据传输，所以必须要考虑路由算法，延时短投递率高的路由协议才能及时接收安全信息和防止交通阻塞。

Ad-Hoc网络拓扑结构无中心，且常处于动态变化中，给数据传输路径的选择带来一定难度。此外，VANET又具有一定特殊性：车辆沿道路行驶，故移动轨迹存在一定规律；车辆速度不同，且分布不均匀；来自建筑物等路侧设备的干扰严重。

基于位置的VANET路由协议不需要维护整个网络的路由表，复杂度和存储开销较小。贪婪周边无状态路由(Greedy Perimeter Stateless Routing,GPSR)是一种最具代表性的基于位置的路由协议，许多协议都是以此为基础建立。但GPSR协议在城市VANET网络中易产生大量的路由空洞，性能及可靠性有所下降。

GPSR协议遇到路由空洞后采用周边恢复策略恢复路由，但需要通过RNG算法或GG算法进行网络拓扑图平面化，在城市交通环境下的车载自组网中，主要存在如下不足：

1)GPSR协议采用贪婪算法选取的转发节点有时接近通讯极限范围，信号干扰严重，链路质量不高，车辆的高速运动较容易造成链路断裂。

2)车载通信设备的信号因受到路侧树木或建筑物等阻碍，在街道之间形成天然的空洞，导致GPSR协议频繁地进入周边转发模式，影响了数据传送的高效性。

3)GPSR协议在节点稀疏时的适应性差，转发节点通信范围内无可用下跳节点时，数据无法转发而导致传送失败。

发明内容

本发明要解决的技术问题在于针对现有技术中GPSR协议在城市交通条件下链路质量低、投递率受速度影响大、低节点密度适应性差等缺陷，提供一种基于路网和QOS模型的车载网GPSR协议改进方法。

本发明解决其技术问题所采用的技术方案是：

本发明提供一种基于路网和QOS模型的车载网GPSR协议改进方法，该方法包括以下步骤：

S1、利用道路和路口位置信息建立路网模型，在路网模型中源节点通过位置服务查询自身以及目的节点的坐标和所处路段属性，记录至分组包头数据域中；

S2、若目的节点在通信范围内，则直接转发；否则启用贪婪转发模式，并确定转发方向，分组包头数据域转发模式设置为0，并更新分组转发方向；

S3、转发过程中，计算当前节点与其邻域节点之间的链路有效带宽和链路生存时间，进而计算得到QOS属性数据对通信链路的服务质量进行衡量，并生成候选转发节点列表；

S4、若候选转发节点列表不为空，则依据分组包头数据域中的目的节点属性和分组转发方向继续贪婪转发；否则启用路由恢复策略中的携带转发机制；

S5、当数据分组陷入局部最优路口时，分组包头数据域转发模式设置为1，并启用周边恢复模式选择转发路段；

S6、当数据分组跨过局部最优路口时，重复执行步骤S2-S5，直到抵达目的节点。

进一步地，本发明的该方法中的贪婪转发模式具体为：

如果r_S＝r_D，其中r_S、r_D表示源节点S、目的节点D所处的路段属性，则采用欧氏距离贪婪算法直接向目的节点D转发数据分组；

如果||v(x,y)-i(x,y)||≤d，其中v(x,y)为车辆节点，i(x,y)为路口节点，d为设定的距离阈值，此时认为分组已传播到路口，执行路段选择决策；

如果r_S≠r_D，且存在公共邻接节点，分为两种情况：当公共邻接节点唯一时，选择该路口方向转发；当公共邻接节点不唯一时，分别计算源节点S到两个公共邻接点节点再到目的节点D的曼哈顿距离，选择距离最短的路口方向转发；

如果r_S≠r_D，且不存在公共邻接节点，则选择与目的节点欧式距离最近的路口节点进行转发；

转发至新的路段后，分组按欧式贪婪算法转发到下一路口位置，并重复路段决策直至目的节点所在路段。

进一步地，本发明的该方法中的周边恢复模式的具体为：

当数据分组进入周边恢复模式时，其分组包头数据域中的分组转发模式Md、进入周边转发的路口竖向I_P首先被更新；然后以邻居节点X与目的节点D的连线开始逆时针查询，选择遇到的第一条路段r_i为下一转发路段进行转发；

进入恢复模式后，包头数据域中的当前转发面的第一个路口属性I₀被更新，当重复传输到包含该路口的路段时，丢弃数据分组以避免路由循环。

进一步地，本发明的该方法中的携带转发机制具体为：

当候选转发节点列表CFN为空时，携带转发机制自动触发，即数据分组被缓存一定时间，直到新的邻居节点出现或者超时后被丢弃。

进一步地，本发明的该方法中生成候选转发节点列表的方法具体为：

各个节点通过发送与接收Hello信标生成邻居列表，计算节点与邻居列表中的节点组成的通信链路的QOS属性数据，QOS属性数据用于描述包括投递率、端到端时延、带宽的性能数据，进而生成候选转发节点列表，从而选择相对可靠的路径进行数据传送。

进一步地，本发明的Hello信标的描述具体为：

车辆节点周期性地将Hello信标广播至MAC地址，节点收到邻居发送的Hello信标后，从中获取邻居当前位置坐标、速度矢量、加速度矢量和所处路段属性等信息并更新至本地邻居表；Hello信标的TTL为1，帧格式为64个字节一个片段；帧类型和帧长度为第1片段，节点编号ID和所处路段ID为第2片段，节点位置坐标为第3片段，节点速度矢量为第4片段，节点加速度矢量为第5片段，所处路段第1节点坐标为第6片段，所处路段第2节点坐标为第7片段，所处路段形状为第8片段。

进一步地，本发明的分组包头数据域的描述具体为：

数据分组被发送前，在转发过程中用到的属性都被记录在分组包头数据域中；包括分组转发模式M_d、目的节点属性D_d、分组转发方向F_d、进入周边转发的路口属性I_P、当前转发面的第一个路口属性I₀；其中，贪婪转发模式时，I_P、I₀均置零。

进一步地，本发明的步骤S1中的所处路段属性记录在路网属性中，路网属性的描述具体为：

城市交通道路网用无向图G(I,R)表示，其中节点集合I＝{i₁,i₂,…,i_n}表示路网中所有的路口，边集合R＝{r₁,r₂,…,r_n}表示路网中所有的可行驶路段，路段定义为两个路口之间的道路；路口属性包括路口编号、路口横坐标、路口纵坐标，路段属性包括路段编号、路段第1节点编号、路段第2节点编号、路段形状，路段形状用分段直线端点坐标表示。

进一步地，本发明的QOS属性数据的描述具体为：

将QoS路由问题定义为：给定网络G₁(V,E)，始发节点为S，寻找下一跳转发节点X，使得B_(S,X)≥B_min,LET_(S,X)≥LET_min，式中B_min和LET_min分别为链路有效带宽和链路生存时间的约束值，最终到达目的节点D；

其中，节点S和X之间的有效带宽计算公式为：

B_(S,X)＝W·log₂(1+SINR_SX)

通信链路生存时间t_SX计算公式为：

其中，B_(S,X)、SINR_SX、t_SX、Δv_SX、Δa_SX分别为始发节点和转发节点之间的有效带宽、信噪比、通信链路时间、速度差和加速度差，W为信号带宽，d₀为初始距离差。

本发明产生的有益效果是：本发明的基于路网和QOS模型的车载网GPSR协议改进方法，充分利用了道路位置信息，并考虑到链路的服务质量，选取更稳定的路径进行传送，获得了更高的分组投递率、更低的平均端到端延时和更低的平均端到端跳数，且对车速变化抵抗性更强。

附图说明

下面将结合附图及实施例对本发明作进一步说明，附图中：

图1为本发明实施例的总流程示意图；

图2为本发明实施例的携带转发机制流程示意图；

图3为本发明实施例的周边恢复模式流程示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。

如图1所示，本发明实施例的基于路网和QOS模型的车载网GPSR协议改进方法，包括以下步骤：

S1、利用道路和路口位置信息建立路网模型，在路网模型中源节点通过位置服务查询自身以及目的节点的坐标和所处路段属性，记录至分组包头数据域中；

S2、若目的节点在通信范围内，则直接转发；否则启用贪婪转发模式，并确定转发方向，分组包头数据域转发模式设置为0，并更新分组转发方向；

S3、转发过程中，计算当前节点与其邻域节点之间的链路有效带宽和链路生存时间，进而计算得到QOS属性数据对通信链路的服务质量进行衡量，并生成候选转发节点列表；

S4、若候选转发节点列表不为空，则依据分组包头数据域中的目的节点属性和分组转发方向继续贪婪转发；否则启用路由恢复策略中的携带转发机制；

S5、当数据分组陷入局部最优路口时，分组包头数据域转发模式设置为1，并启用周边恢复模式选择转发路段；

S6、当数据分组跨过局部最优路口时，重复执行步骤S2-S5，直到抵达目的节点。

该方法中的贪婪转发模式具体为：

如果r_S＝r_D，其中r_S、r_D表示源节点S、目的节点D所处的路段属性，则采用欧氏距离贪婪算法直接向目的节点D转发数据分组；

如果||v(x,y)-i(x,y)||≤d，其中v(x,y)为车辆节点，i(x,y)为路口节点，d为设定的距离阈值，此时认为分组已传播到路口，执行路段选择决策；

如果r_S≠r_D，且存在公共邻接节点，分为两种情况：当公共邻接节点唯一时，选择该路口方向转发；当公共邻接节点不唯一时，分别计算源节点S到两个公共邻接点节点再到目的节点D的曼哈顿距离，选择距离最短的路口方向转发；

如果r_S≠r_D，且不存在公共邻接节点，则选择与目的节点欧式距离最近的路口节点进行转发；

转发至新的路段后，分组按欧式贪婪算法转发到下一路口位置，并重复路段决策直至目的节点所在路段。

该方法中的周边恢复模式的具体为：

当数据分组进入周边恢复模式时，其分组包头数据域中的分组转发模式M_d、进入周边转发的路口竖向I_P首先被更新；然后以邻居节点X与目的节点D的连线开始逆时针查询，选择遇到的第一条路段r_i为下一转发路段进行转发；

进入恢复模式后，包头数据域中的当前转发面的第一个路口属性I₀被更新，当重复传输到包含该路口的路段时，丢弃数据分组以避免路由循环。

该方法中的携带转发机制具体为：

当候选转发节点列表CFN为空时，携带转发机制自动触发，即数据分组被缓存一定时间，直到新的邻居节点出现或者超时后被丢弃。

该方法中生成候选转发节点列表的方法具体为：

各个节点通过发送与接收Hello信标生成邻居列表，计算节点与邻居列表中的节点组成的通信链路的QOS属性数据，QOS属性数据用于描述包括投递率、端到端时延、带宽的性能数据，进而生成候选转发节点列表，从而选择相对可靠的路径进行数据传送。

Hello信标的描述具体为：

车辆节点周期性地将Hello信标广播至MAC地址，节点收到邻居发送的Hello信标后，从中获取邻居当前位置坐标、速度矢量、加速度矢量和所处路段属性等信息并更新至本地邻居表；Hello信标的TTL为1，帧格式为64个字节一个片段；帧类型和帧长度为第1片段，节点编号ID和所处路段ID为第2片段，节点位置坐标为第3片段，节点速度矢量为第4片段，节点加速度矢量为第5片段，所处路段第1节点坐标为第6片段，所处路段第2节点坐标为第7片段，所处路段形状为第8片段。

分组包头数据域的描述具体为：

数据分组被发送前，在转发过程中用到的属性都被记录在分组包头数据域中；包括分组转发模式M_d、目的节点属性D_d、分组转发方向F_d、进入周边转发的路口属性I_P、当前转发面的第一个路口属性I₀；其中，贪婪转发模式时，I_P、I₀均置零。

所处路段属性记录在路网属性中，路网属性的描述具体为：

城市交通道路网用无向图G(I,R)表示，其中节点集合I＝{i₁,i₂,…,i_n}表示路网中所有的路口，边集合R＝{r₁,r₂,…,r_n}表示路网中所有的可行驶路段，路段定义为两个路口之间的道路；路口属性包括路口编号、路口横坐标、路口纵坐标，路段属性包括路段编号、路段第1节点编号、路段第2节点编号、路段形状，路段形状用分段直线端点坐标表示。

在本发明的另一个具体实施例中：

城市交通道路网用无向图G(I,R)表示，其中节点集合I＝{i₁,i₂,…,i_n}表示路网中所有的路口，边集合R＝{r₁,r₂,…,r_n}表示路网中所有的可行驶路段，路段定义为两个路口之间的道路。

图1给出了基于路网和QOS属性的车载网GPSR协议改进方法的流程。

如图1所示，本发明实施例提供的基于路网和QOS属性的车载网GPSR协议改进方法，包括以下步骤：

S1：S通过位置服务查询D的坐标以及所处路段属性，记录至数据分组包头数据域D_d。

如表1所示，路网模型路段属性包括路段编号、路段第1节点编号、路段第2节点编号、路段形状，路段形状用分段直线端点坐标表示。

表1路网模型路段属性表

路段属性名属性描述RoadID路段编号FirstIntersectionID路段第1节点编号SecondIntersectionID路段第2节点编号RoadShape路段形状，用分段直线端点位置表示

如表2所示，路口属性包括路口编号、路口横坐标、路口纵坐标。数据分组被发送前，在转发过程中用到的属性都被记录在包头数据域中。

表2路网模型路口属性表

路口属性名属性描述IntersectionID路口编号IntersectionX路口横坐标IntersectionY路口纵坐标

如表3所示，数据域包括分组转发模式M_d、目的节点属性D_d、分组转发方向F_d、进入周边转发的路口属性I_P、当前转发面的第一个路口属性I₀。其中，贪婪转发模式时，I_P、I₀均置零。

表3路由协议数据分组包头数据域格式表

车辆节点周期性地将Hello信标广播至MAC地址，节点收到邻居发送的Hello信标后，从中获取邻居当前位置坐标、速度矢量、加速度矢量和所处路段属性等信息并更新至本地邻居表。如表4所示，Hello信标的TTL为1，帧格式为64个字节一个片段。帧类型和帧长度为第1片段，节点编号ID和所处路段ID为第2片段，节点位置坐标为第3片段，节点速度矢量为第4片段，节点加速度矢量为第5片段，所处路段第1节点坐标为第6片段，所处路段第2节点坐标为第7片段，所处路段形状为第8片段。

表4路由协议Hello信标格式表

S2：如果在通信范围内，则直接转发；否则启用贪婪转发模式，并确定转发方向，同时包头数据域M_d置零，更新F_d。

如果r_S＝r_D，其中r_S、r_D表示S、D所处路段属性，则采用欧氏距离贪婪算法直接向D转发数据分组；

如果||v(x,y)-i(x,y)||≤d，其中v(x,y)为车辆节点，i(x,y)为路口节点，d为设定的距离阈值，此时认为分组已传播到路口，执行路段选择决策；

如果r_S≠r_D，且存在公共邻接节点，分为两种情况：当公共邻接节点唯一时，选择该路口方向转发；当公共邻接节点不唯一时，分别计算S到两个节点再到D的曼哈顿距离(按路段的形状属性计算不规则路段)，选择距离最短的路口方向转发；

如果r_S≠r_D，且不存在公共邻接节点，则选择与目的节点欧式距离最近的路口节点进行转发。

转发至新的路段后，分组按欧式贪婪算法转发到下一路口位置，并重复路段决策直至目的节点所在路段。

S3：转发过程中当前节点计算与其邻居节点X间的B和LET，生成候选转发节点列表CFN。

将QoS路由问题定义为：给定网络G₁(V,E)，始发节点为S，寻找下一跳转发节点X，使得B_(S,X)≥B_min,LET_(S,X)≥LET_min，式中B_min和LET_min分别为链路有效带宽和链路生存时间的约束值，最终到达目的节点D；

其中，节点S和X之间的有效带宽计算公式为：

B_(S,X)＝W·log₂(1+SINR_SX)

通信链路生存时间t_SX计算公式为：

其中，B_(S,X)、SINR_SX、t_SX、Δv_SX、Δa_SX分别为始发节点和转发节点之间的有效带宽、信噪比、通信链路时间、速度差和加速度差，W为信号带宽，d₀为初始距离差。

根据QoS评估与各邻居节点之间的通信链路质量，并将满足限制条件的节点生成列表CFN。

S4:若CFN≠Φ，则依据分组包头数据域中的D_d、F_d继续贪婪转发；否则启用路由恢复策略中的携带转发机制。

当CFN为空时，携带转发机制自动触发。即数据分组被缓存一定时间，直到新的邻居节点出现或者超时后被丢弃。该策略为QoS服务中的分组投递率需求提供尽力而为服务，不能保证满足时延需求。

S5:当分组陷入路口局部最优时，M_d置1并启用周边恢复模式选择转发路段。

当数据分组进入周边恢复模式时，其包头数据域中的Md、I_P首先被更新。然后以X与D的连线开始逆时针查询，选择遇到的第一条路段r_i为下一转发路段进行转发。与传统右手法则的区别在于，将逆时针寻找点变成了寻找G中的边。

进入恢复模式后，包头数据域中I₀被更新，当重复传输到包含该路口的路段时，丢弃数据分组以避免路由循环。

S6:当数据分组跨过局部最优路口后，重复步骤S2～S5，直至抵达目的节点D。

应当理解的是，对本领域普通技术人员来说，可以根据上述说明加以改进或变换，而所有这些改进和变换都应属于本发明所附权利要求的保护范围。