车载自组织网络中基于Q学习和电子地图的路由方法

技术领域

本发明属于通信技术领域，主要涉及车载自组织网络中的路由方法，可应用于城市环境道路下的车载自组织网络数据通信。

背景技术

车载自组织网络的路由协议，是指在车载自组织网络环境下，使得车辆之间能够进行数据通信的规则和方法。如何设计较好的路由协议，以保障数据包稳定且高效的传输，是车载自组织网络数据通信领域中的重要研究方向。

在解决车载自组织网络数据通信问题的技术领域中，常用方法有基于拓扑的路由方法、基于地理位置的路由方法和基于电子地图的路由方法。其中基于电子地图的路由方法不仅能获取汽车的位置和运动信息，还能获取道路分布信息，以此方法可以获得较高的数据传输性能。

在城市环境中，由于建筑物等影响的问题，Lochert C和Mauve M等人提出了基于道路拓扑的消息转发协议：GPCR(Geographic Routing in City Scenarios)，该方法利用电子地图获取城市中街道和路口的分布，并根据这些分布信息找出到达目的节点的最优路由路径。在数据包转发过程中通过贪婪策略进行转发，节点将数据包发送到交叉路口，并由处在交叉路口的车辆做下一步转发决策。数据包优先转发到交叉路口处的车辆，可以降低因节点高速移动造成链路易断而对数据传输效率产生的影响，并提高数据传输的稳定性。但该方法没有考虑路段上车流密度的影响，当所选择道路上的车辆稀少时，数据包容易丢失。

在城市环境中，车流密度对数据传输性能影响较大。为了解决上述GPCR方法中未考虑车流密度的问题，李长乐和赵春春等人提出了一种“车辆自组织网络中基于预测的交叉路口处的路由方法”的专利申请(申请号：201110098182.7，授权公告号：CN102137462B，授权公告日：2013.08.14)。该方法利用电子地图获取道路和交叉路口的分布信息，并利用GPS模块获取车辆节点的位置信息和车辆运动信息。根据上述获得的相关信息，计算道路上的车流密度，并预测下一个交叉路口的权值，车辆节点将数据包转发给权值较大交叉路口附近的车辆节点；然后通过贪婪策略，将数据包从交叉路口传递到离目的节点近的道路上的车辆，最后完成数据传输。此方法可以提高数据包的投递成功率，并降低传输时延。但是该方法由于未考虑车辆移动的实时性和动态性，因而所选择的路由路径并非是最优的，其数据传输性能未能达到最好。

发明内容

本发明的目的在于针对上述现有技术的不足，提出一种车载自组织网络中基于Q学习和电子地图的路由方法，以选择最优的路由路径，保障数据传输的高效性和稳定性。本发明可提高数据包的投递成功率，降低网络的传输时延，并减少路由控制开销。

本发明的技术方案是：首先，利用电子地图获取城市道路和交叉路口位置分布信息，并利用GPS模块获取车辆节点的位置和运动信息；其次，根据上述信息可计算得到道路上的车流密度，并采用Q学习方法，使得节点可动态地选择最优的路由路径；最后，车辆节点根据最优的路由路径，高效地完成数据传输。

其实现步骤如下：

(1)网络初始化，即将网络中每个节点的Q值表设置为0；

(2)网络中的所有节点开始周期性地广播发送问候HELLO数据包，获取节点的位置和运动信息，并结合电子地图确定节点的从属路口和相邻路口；

(3)根据节点的位置和运动信息，计算车流密度，并更新节点的Q值表：

3a)计算车流密度：

其中，ρ(s)为车辆节点s行驶路段上的车流密度；v_f是道路上车辆的最大行驶速度；为行驶路段上车辆的平均速度；

3b)利用Q学习方法，计算Q值表中的Q值大小：

Q_s(d,c)＝(1-ρ(s))×Q_s(d,c)+ρ(s)×{R+γmax_c'∈Γ(x)Q_x(d,c')}，

其中，Q_s(d,c)表示当前节点s通过下一相邻路口c转发数据包到目的节点d的Q值；ρ(s)表示当前节点s所处路段的车流密度，并作为公式的学习率；γ表示折扣率，取值为γ＝0.7；节点x为当前节点s的邻居，Γ(x)表示x可选择的相邻路口集合，R表示奖励值；

3c)计算最大Q值集合MaxQ：

其中，MaxQ_j表示节点j的最大Q值集合，d_n表示不同的目的节点，c表示j的一个相邻路口，maxQ_j(d_n,c)表示节点j通过路口c发送数据包到目的节点d_n的最大Q值，表示maxQ_j(d_n,c)的最近更新时间；

3d)将最大Q值集合MaxQ加入到问候HELLO数据包中；

(4)根据步骤(2)中节点的路口信息，判断当前节点与邻居节点是否属于同一路口：若是，则当前节点根据最大Q值集合MaxQ，同步更新自身的Q值表；否则，当前节点按照步骤(3)重新计算Q值，并更新自身的Q值表；

(5)源节点查询自身的Q值表，判断其邻居节点中是否有目的节点：若有，则源节点向目的节点发送数据包；否则，源节点生成路由请求包RREQ，并将最大Q值集合MaxQ加入到路由请求包RREQ中；

(6)网络中的中间节点接收到路由请求包RREQ后，根据路由请求包RREQ中的Q值信息更新节点自身的Q值表，并继续广播该路由请求包RREQ；

(7)判断目的节点是否接收到路由请求包RREQ：若是，则目的节点生成路由回复包RREP，将自身最大Q值集合MaxQ添加到路由回复包中，并反向回传给源节点，执行步骤(8)；否则，返回步骤(6)；

(8)网络中的中间节点接收路由回复包RREP后，根据路由回复包RREP中的信息更新节点自身的Q值表，并通过查询Q值表以及结合步骤(2)中通过电子地图所获取的交叉路口信息，选择最优交叉路口，再通过贪婪策略完成数据包在当前路口到下一最优路口的转发；

(9)判断源节点是否接收到路由回复包RREP：若是，则表明路由路径建立完成，源节点根据Q值表信息向目的节点发送数据包；否则，返回步骤(8)。

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

1)本发明由于利用电子地图获取城市环境中道路和路口的位置分布，路由路径采用“路口到路口”方法建立，使得通信路径非常稳定，克服了因节点拓扑结构频繁变化而造成的数据包丢失的问题。

2)本发明由于计算了路段的车流密度，通过车流密度评估该路段的连通质量，选择连通质量较优的路段转发数据包，降低了网络传输时延。

3)本发明由于采用了Q学习方法，基于Q学习设计路由方法可以动态地适应各路段车流密度变化，能实时获取最优的路由路径，并获得较好的数据传输性能。

附图说明

图1是本发明的实现流程图；

图2是本发明中节点维护Q值表的示意图；

图3是本发明中采用贪婪策略进行数据包转发的示意图；

图4是仿真实验中的城市环境道路示意图。

具体实施方式

下面结合附图对本发明的实例和效果做进一步的描述。

参照图1，本发明的具体实施步骤如下：

步骤1，对网络进行初始化。

网络中的每个网络节点都维护一个Q值表，Q值表中主要属性包括：邻居节点，相邻路口和节点到相邻路口的Q值；

初始化时，将网络中每个节点的Q值表设置为0。

步骤2，广播发送问候数据包并获取节点运动信息和路口信息。

2a)网络中的所有节点开始周期性地广播发送问候HELLO数据包；通过GPS模块获取车辆节点的位置和运动信息，并存入问候HELLO数据包中；

2b)通过电子地图获取道路和路口分布信息，并结合节点位置信息确定节点的从属路口和相邻路口，即将离当前节点最近的路口作为该节点的从属路口，将节点最近路口的下一个路口作为该节点的相邻路口。

步骤3，计算车流密度并更新Q值表。

3a)根据节点的位置、运动信息和道路信息，计算车流密度：

其中，ρ(s)为节点s行驶路段上的车流密度，v_f是车辆的最大行驶速度，实验中设置v_f为30m/s；为路段上车辆的平均速度，其计算公式如下：

其中，v_s表示节点s的速度，v₁,v₂...v_m表示节点s所在路段上各邻居节点的速度，m表示节点s所在路段的邻居节点数量；

3b)利用Q学习方法，计算Q值表中的Q值大小：

Q_s(d,c)＝(1-ρ(s))×Q_s(d,c)+ρ(s)×{R+γmax_c'∈Γ(x)Q_x(d,c')}，

其中，Q_s(d,c)表示当前节点s通过下一相邻路口c转发数据包到目的节点d的Q值；ρ(s)表示当前节点s所处路段的车流密度，并作为公式的学习率；γ表示折扣率，取值为γ＝0.7；节点x为当前节点s的邻居，Γ(x)表示x可选择的相邻路口集合；R表示奖励值，其计算公式如下：

其中，d＝x表示邻居节点x为目的节点；

3c)计算最大Q值集合MaxQ：

其中，MaxQ_j表示节点j的最大Q值集合，d_n表示不同的目的节点，c表示j的一个相邻路口，maxQ_j(d_n,c)表示节点j通过路口c发送数据包到目的节点d_n的最大Q值，表示maxQ_j(d_n,c)的最近更新时间；

3d)将最大Q值集合MaxQ加入到问候HELLO数据包中。

步骤4，节点接收问候HELLO数据包并周期性维护Q值表。

节点周期性接收问候HELLO数据包后，根据步骤(2)中节点的路口信息，判断当前节点与邻居节点是否属于同一路口：

若是，则当前节点根据最大Q值集合MaxQ，同步更新自身的Q值表；

否则，当前节点按照步骤(3)中的方法重新计算Q值，并更新自身的Q值表。

步骤5，源节点生成路由请求包RREQ。

源节点查询自身的Q值表，判断其邻居节点中是否有目的节点或者到目的节点的Q值信息：

若有，则源节点向目的节点发送数据包；

否则，源节点生成路由请求包RREQ，同时将最大Q值集合MaxQ加入到路由请求包RREQ中。

步骤6，中间节点接收的路由请求包RREQ并更新Q值表。

网络中的中间节点接收到路由请求包RREQ后，根据路由请求包RREQ中的信息更新节点的Q值表；节点维护更新Q值表的过程，如图2所示；节点继续广播该路由请求包RREQ。

步骤7，目的节点发送路由回复数据包RREP。

通过查询接收到路由请求包RREQ信息，判断当前节点是否为目的节点：

则目的节点生成路由回复包RREP，将自身最大Q值集合MaxQ添加到路由回复包中，并反向回传给源节点，执行步骤(8)；

否则，返回步骤(6)。

步骤8，中间节点转发路由回复包RREP。

网络中的中间节点接收路由回复包RREP后，根据路由回复包RREP中的信息更新节点自身的Q值表，并通过查询Q值表以及结合步骤(2)中利用电子地图所获取的交叉路口信息，选择最优交叉路口，再通过贪婪策略完成数据包在当前路口到下一最优路口的转发；通过贪婪策略转发数据包的过程，如图3所示；

步骤9，建立路由路径，完成数据传输。

通过查询路由回复包RREP信息，判断路由回复包RREP是否到达源节点：

若是，则表明路由路径建立完成，源节点根据Q值表中的信息，查询下一最优路口的位置；车辆节点在道路上时，通过贪婪策略将数据包传递到该最优路口附近的车辆；最后通过不断地选择最优路口和贪婪转发的过程，完成数据传输；

否则，返回步骤(8)，继续转发路由回复包RREP。

本发明的效果可以通过以下实验验证：

1.仿真条件

1.1)实验场景设置

本实验仿真场景范围设置为2000m*2000m，车辆个数分别为50、100、150、200、250和300个。场景仿真时间为200秒，节点的最大速度为30m/s，平均速度为20m/s，暂停概率为0.3，最大的停止时间为10s。仿真的城市环境道路中有40条道路，20个交叉路口，仿真示意图如图4所示。

1.2)仿真软件参数设置

利用NS2和VanetMobiSim作为本实验的仿真软件。仿真软件参数设置如表1所示：

表1仿真参数设置

2.实验性能评价指标

本实验性能评价指标为投递成功率、平均端到端的时延和路由控制开销，各指标定义如下：

投递成功率表示网络中源节点发出的数据包成功投递到目的节点的比率，反映了网络中数据传输路径的可靠性，计算公式如下所示：

其中，SPN为源节点发出的数据包总数，RPN为目的节点接收的数据包总数。投递成功率PDR越高，表明网络中路由路径的越稳定。

平均端到端时延是衡量车载网络性能的重要指标，反映网络是否顺畅，计算方法如下所示：

其中，N表示网络中节点接收到的数据包总数，RT_i表示目的节点收到第i个数据包的时间，ST_i表示源节点发出第i个数据包的时间。平均端到端时延AEED越低，表明网络中的通信链路连通性越好。

路由控制开销反映的是建立的路由是否可靠，也能反映路由建立的代价大小，计算方法如下所示：

其中，RCN表示网络中路由控制包的数量，RPN表示网络中节点接收到数据包的总数量。路由控制开销NRL越低，表明路由建立的代价越小。

3.实验内容与结果

在实验中，将本发明提出的车载自组织网络中基于Q学习和电子地图的路由方法，与现有技术基于距离向量的路由方法AODV方法和基于城市环境的地理路由方法GPCR方法作对比。并根据实验结果从投递成功率、平均端到端时延和路由控制开销三个评价指标进行比较。

仿真1，利用上述1的仿真条件设置，用本发明与上述两种现有技术AODV方法和GPCR方法，进行投递成功率的比较实验，实验数据如表2所示。

表2三种方法的投递成功率

从表2可见，本发明的投递成功率要高于现有技术AODV方法和GPCR方法。这是由于现有技术中节点的拓扑结构容易发生变化，导致通信链路容易断开，造成数据包丢失，而本发明选择“路口到路口”形式的路由路径，通信链路比较稳定。同时，本发明方法采用Q学习方法，能动态选择车流密度较高的路段，避开车辆稀少的路段，保证了数据包传输的高效性，从而提高了投递成功率。

仿真2，利用上述1的仿真条件设置，用本发明与上述两种现有技术AODV方法和GPCR方法，进行平均端到端时延的比较实验，实验数据如表3所示。

表3三种方法的平均端到端时延

从表3可见，本发明的平均端到端时延要低于现有技术AODV方法和GPCR方法。这是由于现有技术中，当节点比较稀疏时，网络中的拓扑结构容易发生变化，导致通信链路容易断开，造成数据包传输时延增加。而本发明方法采用Q学习方法，能动态选择车流密度较高的路段，路由路径的有效时间更长，保证了数据包在路段内传输的稳定性，从而降低了数据包的传输时延。

仿真3，利用上述1的仿真条件设置，用本发明与上述两种现有技术AODV方法和GPCR方法，进行路由控制开销的比较实验，实验数据如表4所示。

表4三种方法的路由控制开销

从表4可见，本发明的路由控制开销要低于现有技术AODV方法和GPCR方法。这是由于现有技术中，当通信链路容易断开时，需要大量的路由控制包来对链路进行修复，使得网络的路由控制开销增大。而本发明选择“路口到路口”形式的路由路径，通信链路比较稳定，使得用来维护链路的路由控制包的数量减少，从而降低了网络的路由控制开销。