Page 404 - 《软件学报》2025年第12期

李洁 等: 历史交通数据驱动的 VANET 智能路由算法 5785

Q 值的动作, 步骤 12, 13 根据公式 Q 值; 重复步
1−ε 的概率选择当前具有最大 (5) 计算折扣因子 γ t 并更新相应的
骤 4–14, 直至 Q-table 收敛或达到预定迭代次数; 步骤 15 将此目标网格的奖励还原为 0, 进行下一目标网格的
处理.
算法 1. 改进的 Q-learning 算法.

输入: G, A, R, ε, α, δ;
输出: 三维 Q-table.
1. 初始化 Q 矩阵和 R 矩阵为零矩阵;
2. for all D y ∈ G do
3. R[D y ] = φ;
4. for episode = 1 to M do
5. 选择一个网格作为初始网格;
6. 生成一个随机数 r ∈ (0,1);
7. if r ⩽ ε then
8. 随机选择一个网格;
9. else
Q-value 的网格;
10. 选择具有最大
11. end if
12. 根据公式 (5) 计算 γ t ;
13. 根据公式 (4) 来更新 Q-value;
14. end for
15. R[D y ] = 0;
16. end for

为了更有效地引导数据包转发, 我们将目标网格作为索引项, 利用 Q-table 生成转发表并共享给网络中所有的
车辆. 转发表中记录了从当前网格到目标网格应选择的下一最优网格 G , 即下一路径.
best
3.2 基于 Markov 预测的在线 V2V 传输机制
面向 VANET 的数据采集业务需求, 在基础设施稀疏且车辆高速动态的环境下, 如何实现高效、可靠的数据
传输至关重要. 为了进一步提高数据转发效率, 提出了基于 Markov 预测的在线 V2V 传输机制. 该机制旨在通过算
法 1 得到的转发路径上选择合适的中继车辆, 实现数据包的高效转发. 这里, 考虑到除了车辆节点的位置会影响路
由性能外, 其他因素, 如节点之间链路生存性和路由空洞等, 也对路由性能起着较大的影响. 我们在选择中继车辆
时综合考虑以上因素, 以确保数据的高效可靠传输. 与此同时, 考虑到在线机制的性能要求, 对算法的计算时间复
杂度和空间占用情况进行了分析.
3.2.1 路由性能的影响因素
(1) 车辆位置的影响
由于数据转发方向已定, 这里我们首先将车辆当前所处的位置和下一阶段可能出现的位置与数据包转发路径
的关系作为参考, 计算车辆基于位置的代价. 对此, 本文引入了 Markov 预测方法来对车辆的位置进行预测.
首先每个车辆节点, 可利用条件概率根据其历史轨迹信息计算下一时刻移动到各个网格的概率, 生成位置转
P. 如公式 (10) 所示, 对于每个车辆, 我们可以通过公式 G i 到下一网
移概率矩阵 (9) 计算车辆在时刻 t 从当前网格
格 G j 的位置转移概率 P , 从而得到 P.
ij
t
t
t
t+1
t
t+1
t+1
P(G → G ) = P(G |G ) = P(G G )/P(G ) = P (9)
i j j i i j i ij