车联网中基于Q学习的地理位置路由协议*

刘静茹,朱 浩,章国安

(南通大学 信息科学技术学院,江苏 南通 226019)

0 引 言

车联网作为智能交通系统的重要组成部分,已经成为研究热点。车联网包括一个由大量车辆节点和基础设施组成的异构系统,车辆和基础设施之间的通信使车辆节点能够获取交通信息,从而有效地提高交通安全和运输效率[1]。为了在车联网中传递消息,分组必须通过多跳无线通信从源节点发送到目的节点,因此要用到路由功能来选择最佳下一跳。然而车辆的快速移动导致节点分布不均匀和通信链路断开,再加上网络结构受道路拓扑结构的影响,路由协议的设计变得十分困难。

根据参与通信的移动车辆节点数目,车联网中的路由协议主要分为单播路由、广播路由和多播/位置辅助路由[2]。单播路由技术是指从一个源节点经过多跳无线通信将分组发送到一个特定目的地的路由技术,本文主要研究单播路由。单播路由中比较常见的是基于拓扑的路由和基于地理位置的路由。基于拓扑的路由协议使用路由表存储有关路由路径的信息,到所有目的地的路由必须在通信之前建立,每个节点定期广播控制分组,以便与网络中的其他节点共享信息,并更新路由表[3]。基于地理位置的路由利用全球定位系统(Global Positioning System,GPS)技术,根据节点之间共享的位置信息转发分组,可以减少节点高移动性的影响,避免维护整个网络的路由表。文献[4-5]都将软件定义网络运用到车联网中,显示了集中控制的好处。其中文献[4]提出了一种车联网中结合移动性预测的集中式路由方案,由人工智能驱动的软件定义网络控制器辅助,基于移动性预测,可由路侧单元或基站估计网络拓扑频繁变化下每辆车请求的成功传输率和平均延迟;基于全局网络信息,SDN控制器为转换器计算最优路由路径。文献[6]提出的基于地理位置的贪婪周边无状态路由协议,总是选择距离目的地最近的邻居节点作为下一跳节点,这在车辆高速移动的情况下有很大难度。文献[7]提出了一种基于车辆位置分析的路由算法,根据预测的车辆轨迹做出传输决策,但是没有考虑到道路上现实因素的影响。文献[8-10]都注意到了十字路口交通信号灯引起的车辆聚集现象,例如,文献[8]根据街道中间区域的车辆分布和密度计算街道的连通性,提出了一个以街道为中心的基于街道连通性的交通灯感知路由协议。基于强化学习的算法可以优化车联网路由的不同服务质量参数,如端到端延时、分组投递率、开销等[11],如文献[12-14]都结合了强化学习算法进行路由。结合强化学习中的Q学习算法进行路由,不需要维护路由表,只需要建立一个Q值表,然后根据Q值表选择最优路由路径。文献[15-19]中采用了Q学习算法,其中,文献[15]提出了一种基于Q学习的分层路由协议,根据Q表选择下一个最优网格,跳过相邻车辆,将消息从源车辆发送到目的车辆;文献[17]中加入了RSU进行辅助,同时考虑到交通灯的影响,利用Q学习算法和贪婪转发算法进行路由。

车联网中车辆节点快速变化导致通信链路连接不稳定,同时网络会受到道路拓扑结构的影响。为了解决此问题,本文提出了一种改进的基于Q学习的地理位置路由协议(Geographic Location Routing Protocol Based on Q-learning,QGR)。该协议将不同的地理区域划分为网格,同时结合Q学习探索道路环境,是对QGrid[15]协议的改进,充分利用Q学习算法和网格的结合,可以找到最优下一跳网格和次优下一跳网格。该协议不仅提高了分组投递率,而且降低了传输延时,减少了通信跳数。

1 Q学习算法

Q学习是一种免模型的强化学习算法,它是基于马尔科夫决策过程的,可以用元组(S,A,P,R,γ)来表示,S代表状态空间的离散集合,A代表动作空间的离散集合,P代表状态转移概率,R代表即时奖励,γ代表折扣因子。机器是车联网中具有历史交通流信息的云服务器,也是Q学习中的学习者和决策者,通过不断地与环境交互以学习控制策略。

本文将不同网格的集合定义为状态空间S,动作空间A是下一跳网格的集合,整个车联网就是环境,机器根据奖励推断环境,奖励用来代表分组是否被发送到了目的地。机器观察到当前的环境状态st,然后选择一个动作at,采取该动作后,机器获得了一个奖励Rt,同时系统状态转变到下一个状态st+1。假设在消息发送的过程中,消息的目的地是固定的。如果消息发送到了目的地,奖励就是100,否则奖励就是0。

对于状态动作对(st,at),假定基于t个采样已估计出Q值函数为

(1)

式中:ri表示i步的奖励。则在得到第t+1个采样rt+1时,有

(2)

式中:rt+1表示t+1步的奖励,表达式为

(3)

Q′(st,at)=(1-α)×Q(st,at)+

(4)

Q表存储了状态动作对的Q值Q(st,at),该值代表了在当前状态st下采取动作at所期望得到的奖励。每执行一步策略就更新一次值函数估计,得到Q学习的训练公式为

Q(st,at)←(1-α)×Q(st,at)+

(5)

2 基于Q学习的地理位置路由协议与应用

2.1 基于Q学习的地理位置路由协议

本文提出了一种基于Q学习的地理位置路由协议,将选定的地理位置区域划分成36个大小一致的网格。区域中的车辆定期向数据中心发送GPS数据报告,具体的信息包括车辆的ID、经度、纬度、时间戳、移动速度、行驶方向和当前的状态。车辆的历史轨迹具有很强的规律性,因此,根据历史交通流信息训练Q学习算法。QGR协议由两部分组成:宏观方面,根据Q值决定最优/次优下一跳网格;微观方面,确定所选网格的特定车辆。计算出车辆从当前网格向不同方向的邻居网格移动的Q值,每辆车存储Q学习的Q值表,然后通过查询Q值表选择最优下一跳网格。在选定的下一跳网格中,选择距离目的地最近的车辆,当最优下一跳网格中没有邻居车辆时,选择次优下一跳网格中的车辆。该协议的目的是将消息从源车辆所在的网格以高概率发送到目的地。本文将不同的网格定义为状态,学习状态的数量将会大大减少,Q学习的Q值表将在整个周期中使用,节省了大量的系统资源和时间。机器采取的动作是将分组从一个网格发送到另一个网格,当目的地在邻居网格,奖励就是100,否则初始奖励就是0。本协议中,折扣因子是一个动态参数,取决于网格中的车辆数量和网格到目的地的距离。用M代表网格总数,n(gi)表示网格gi中记录的车辆数量,计算出所有网格中车辆数量的平均数为

(6)

这里用一个分段函数来描述折扣因子的变化,定义为

(7)

式中:β是权重因子,其范围是β∈[0,1];NP是车辆数量的影响因子,定义如式(8)所示;DP是到目的地距离的影响因子,定义如式(9)所示。

(8)

(9)

(10)

式(8)中的μ是一个常数值;式(9)中的distc是当前网格距离目的网格的距离,distn是下一跳网格距离目的网格的距离。在通信的开始,机器对于整个环境一无所知,Q表中的所有元素都被初始化为0。利用Q学习方法获得Q值表,Q值代替元组中的状态转移概率,将Q值表存储在每辆车中,然后根据该表传递消息。

在QGR中,车辆不需要维护路由表,它们只根据Q学习的Q值表发送消息,即当前车辆选择具有最大Q值的最优下一跳网格,并在最优网格中选择距离目的地最近的车辆,如果最优网格中没有车辆,就选择具有第二大Q值的次优网格作为下一跳网格。Q值表包含与不同目的网格对应的最佳下一跳网格,因此在给定任意一个目的网格时,都可以根据Q值找到对应的转发路径。

用vt代表当前的车辆节点,消息传递流程如图1所示,当选择下一跳车辆时有四种类型:

图1 消息传递流程

1)如果目的节点在当前节点通信范围内,将消息直接传递给目的节点;

2)如果目的节点不在当前节点通信范围内,从Q表中寻找最优下一跳网格,在选定的最优下一跳网格中寻找传递消息的下一跳车辆,应选择vt通信范围内距离目的节点最近的车辆;

3)如果最优下一跳网格中没有邻居车辆,从Q表中寻找次优下一跳网格,在选定的次优下一跳网格中寻找传递消息的下一跳车辆,应选择vt通信范围内距离目的节点最近的车辆;

4)如果次优下一跳网格中没有邻居车辆,则考虑vt邻居车辆中距离目的节点最近的车辆为下一跳车辆(可以为本身)。

2.2 应用举例

实例场景如图2所示,将地理区域划分为36个网格,源车辆S位于第17个网格中,目的车辆D位于第20个网格中。目的车辆不在源车辆的通信范围内,根据Q表找到最优下一跳网格22,网格22中没有邻居车辆,找到次优下一跳网格16,且网格16中有多个邻居车辆,选择距离目的地最近的邻居车辆作为中继;网格16的最优下一跳网格中没有邻居车辆,则选择次优下一跳网格15,于是选择网格15中的车辆作为下一跳;网格15的最优下一跳网格是21,选择网格21中的车辆作为中继;目的车辆位于网格21的中继车辆的通信范围内,所以最后一跳直接将分组传递给目的车辆。

图2 实例场景示意

3 性能评估

3.1 仿真环境和参数

基于城市道路进行仿真,实验域的大小为3 000 m×3 000 m,主要仿真参数如表1所示。不同的车辆上传GPS数据的时间是不一样的,当它们同时在彼此的通信范围内,也可能不会同时上传GPS数据,这会导致GPS数据集中实际相邻的车辆断开连接。因此,使用时间间隔ΔT来表示实际的GPS数据上传时间。如果一个时间间隔内,有两辆车在对方的通信范围内,则认为这两辆车在此期间相遇,时间间隔越大,邻居车辆越多。时间间隔的选择会极大地影响网络拓扑结构,这关系到路由性能的好坏。网格长度与无线通信半径相关联,在本协议中也是一个重要参数:一方面,如果网格长度过小,Q学习中的状态数(即网格数)就会增多,到目的地的跳数也会增加;另一方面,如果网格长度过大,相邻车辆可能与携带消息的车辆位于同一网格中。因此要选择一个合适的网格长度,本协议的网格长度设为500 m。考虑到传输范围的问题,通信半径设置为500 m。TTL是生存时间值,指定了分组被丢弃之前允许通过的最大网段数量。TTL的作用是避免分组在网络中的无限循环和收发,节省网络资源。每条消息都有TTL次转发机会,如果经过一轮循环后,消息没有传递成功,则TTL减1;如果TTL=0时消息还没有传递成功,则该消息将会被丢弃,并向发送者发送非成功传递信号。因此,TTL越大,会有更多的消息被传递成功。

表1 仿真参数

将本文的路由协议与GPSR[5]和QGrid[14]进行比较,用于评估路由协议性能的指标如下:

1)分组投递率:在仿真时间内,目的节点成功接收分组的总数量与源节点发送分组的总数量之比。

2)平均延时:一个分组从源节点被转发到目的节点所需要的平均时间。

3)平均跳数:一个分组从源节点到目的节点,在路由路径上经过的平均节点数。

3.2 仿真结果与分析

图3～5显示了时间间隔的选择对路由协议性能的影响。在相同的TTL下,从图3中可以看出,时间间隔越大,分组投递率越高;从图4中可以看出,时间间隔越大,传输延时越小;从图5中可以看出,时间间隔越大,通信跳数越多。所以,增加时间间隔可以提高分组投递率、降低传输延时,但同时也会增加转发的跳数。这是因为当时间间隔增加的时候,邻居车辆的数量就会增加。将该协议和另外两种基于地理位置的路由协议在ΔT=10 s和ΔT=20 s的情况下进行了比较,分别评估三种路由协议的性能,其他实验参数如表1所示。GPSR只选择邻近的节点进行转发,没有考虑到整个区域的网络状况。QGrid在选择下一跳网格时,只考虑选择了最优网格,而且在Q学习算法中只考虑了下一跳网格中的车辆数目。而本文的QGR算法对前面两种算法进行了改进,选择下一跳网格时,不仅仅考虑了网格中的车辆数量,还考虑了网格中车辆距离目的地的距离,当最优下一跳网格中没有车辆时,考虑选择次优下一跳网格中的车辆,充分利用了网格的特点和优势。

图3 QGR协议在不同时间间隔下的分组投递率

图4 QGR协议在不同时间间隔下的延时

图5 QGR协议在不同时间间隔下的跳数

图6～8中设置参数ΔT=10 s。从图6中可以看出,QGR的分组投递率高于QGrid和GPSR,而且三种协议的分组投递率随着TTL的增加而增加。这是因为TTL越大,会有更多的消息被传递成功。图7中GPSR的延时明显较高,当TTL较小时,QGrid和QGR的曲线几乎重合,但是当TTL较大的时候,QGR的延时就小于QGrid的延时。图8表示一个仿真周期的平均跳数随着TTL的增加而增加,GPSR的跳数最多,QGR和QGrid的跳数比较相近,本文的QGR路由协议具有最小的跳数。

图6 ΔT=10 s的情况下三种协议的分组投递率

图7 ΔT=10 s的情况下三种协议的延时

图8 ΔT=10 s的情况下三种协议的跳数

图9～11中设置参数ΔT=20 s。图9表示的是三种路由协议的分组投递率的对比,可见在每一个TTL值下,本文的QGR协议都具有最高的分组投递率,而另外两种协议的分组投递率比较相近,且都低于本文的协议。图10显示的是三种协议的平均延时的对比,可以看出本文的QGR协议具有最低的延时。图11表明,相对于另外两种路由协议,QGR用了最少的跳数进行消息传递。因此,可以发现,本文的QGR协议具有最高的分组投递率,而且拥有最小的延时和最小的跳数。

图9 ΔT=20 s的情况下三种协议的分组投递率

图10 ΔT=20 s的情况下三种协议的延时

图11 ΔT=20 s的情况下三种协议的跳数

4 结 论

本文提出了一种基于Q学习的地理位置路由协议。该协议将地理区域划分成大小一致的网格,在给定目的地的情况下计算出车辆从当前网格向不同方向的邻居网格移动的Q值,每辆车存储Q学习的Q值表,通过查询Q值表选择最优下一跳网格,在选定的下一跳网格中选择距离目的地最近的邻居车辆,当最优下一跳网格中没有车辆时选择次优下一跳网格中的车辆。仿真结果表明,该协议能够提高分组投递率,降低传输延时,并且减少通信跳数。