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

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

20. end if
21. end if
3.2.3 算法在线性能分析
考虑到第 3.2.2 节提出的策略需要当前车辆在线计算下一跳转发中继, 其算法的实时响应至关重要. 因此, 为
了验证该在线中继选择策略的实际可行性, 我们对其计算时间复杂度和空间复杂度进行了如下具体分析.
(1) 计算时间复杂度
v A 的转发代价. 由公
对于当前车辆 v B , 当其收到待转发数据包时, 其需在候选邻居集合 C B 中计算各邻居节点
式 (20) 可知, 该代价函数包含 3 个核心维度: 位置代价 Place A 、链路生存性 Link A 以及后继可转发概率 F A .

这里, 对于 Place A , 由公式 (13) 可知, 其最高仅涉及二维空间单点对的欧氏距离计算和余弦相似度计算, 用到
Link A 和
的坐标位置和位置转移概率可直接通过邻居信息表查询得到, 其计算时间复杂度约为 O(1). 同理, 对于
F A , 如公式 (18) 和公式 (19) 所示, 其仅涉及简单的四则运算, 所以其计算复杂度亦为 O(1). 因此, 对于当前车辆 v B
来说, 每个邻居 v A 的转发代价计算复杂度约为 O(1).
然而, 由公式 (13) 可知, 当前车辆 v B 的候选邻居集合 C B 并不一定等于其传输范围内的邻居集合 VR . 其需按
t
B
t t , 则
照相应约束条件从 VR 中按优筛选候选邻居. 若存在任一邻居当前位于最优的下一路径上, 即 ∃v A ∈ VG
B best
C B = VG t , 我们仅需计算在 VG t 中各邻居节点的转发代价即可. 否则, 我们需要根据各邻居到下一路径的位置
best best
转移概率值 p A 进行筛选. 若存在 p A > 0, 此时 C B = {v A |p A > 0}; 否则, 我们才需计算所有邻居的转发代价. 因此, 在
本文提出的基于 Markov 预测的在线 V2V 传输机制中, 车辆在选择下一中继节点时, 对比的邻居节点数量要小于
|C B | ⩽ |VR |. 因此, 本文提出的在线 V2V
t
等于传输半径内邻居的数量, 即 B 转发策略的计算复杂度为 O(|C B |).
(2) 计算空间复杂度
对于当前车辆 v B , 在计算邻居的转发代价前需要查询邻居表以获取必要信息. 传统的基于位置的路由协议中,
车辆通过周期性地广播 HELLO 消息来共享自身信息, 并建立邻居表以维护单跳邻居的信息. 该表通常包括车辆
ID、位置 position 以及最近一次接收到信号的时间戳 time. 本文对邻居表的格式进行了修改, 除以上基本信息外,
t P neigh (下阶段前往当前所
新增了车辆的当前速度 u、行驶方向角 θ、邻居节点数量 |VR |, 以及位置转移概率向量
ID
在网格或与当前网格直接/对角线相邻的八邻域网格的概率) 等扩展信息, 以满足下一中继选择的要求.
修改后的邻居表结构如图 7 所示, 每个邻居条目占用 32 个字节, 邻居条目中各字段的大小参考 BSM 报文的
一些格式设置和 SAE J2735 标准 [38,39] . 其中, 新增的当前速度 u、行驶方向角 字段分别占用 2 字节. 考虑到面向
θ
的应用场景以及邻居数量对通信质量的影响, 设邻居节点数量字段占用 1 个字节. 由于 P neigh 需要存放到当前网格
和八领域网格的转移概率, 其需维护 9 个概率值, 每个概率值占用 1 个字节用 0–100 的整型数据表示, 共占用 9 个
字节. 由于扩展信息仅占用 14 字节, 符合 HELLO 包的扩展限制 [26] , 可以直接通过 HELLO 包完成信息的获取.

基本信息 扩展信息
0 3 13 17 19 21 22 31 (bytes)
t ID position time u θ VR ID t P neigh
|VR |
个
邻
居 …
条
目
图 7 邻居表

由算法 2 和上述计算时间复杂度分析可知, 当前车辆在计算下一转发中继时仅需通过对邻居表中邻居信息的
查找计算来选择最优转发中继, 并没有使用额外的数据结构. 因此, 在内存空间的占用上额外空间的占用约为 O(1),
总空间的占用主要受输入的邻居表大小的影响. 考虑到算法最多需要查询其传输半径内所有邻居的相关信息完成
|VR | 个邻居条目信息. 因此, 对于每个车辆节点来说, 执行在线 V2V 算法时其计
t
中继的计算, 邻居表最多需维护 B
t
算空间复杂度主要受邻居表的大小影响为 O(32|VR |).
B