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

5796 软件学报 2025 年第 36 卷第 12 期

图 18 为各种路由算法在数据包不同的生存时间 (TTL) 条件下平均成功发包开销的仿真结果. 我们观察到平
均成功发包开销随着不同数据包生存时间 (TTL) 的增加而减小, 即以较少的数据包为开销完成不同的数据包传递.
图 18(a) 和图 18(b) 的对比也表明, HTD-IR 在平均成功发包开销上也能较好的适应车辆节点的传输半径 R 的
变化.
4.3 算法在线性能评估与实验验证
为了评估 HTD-IR 在线阶段的性能, 我们将 HTD-IR 与对比算法在计算时间复杂度和空间复杂度两个方面进
行了详细的对比分析, 以评估它们在不同网络规模下的执行性能. 其中表 1 和表 2 分别总结了各算法在计算时间
和空间上复杂度情况, 图 19 和图 20 分别展示了不同路由算法的执行时间和内存空间占用情况随着车辆数量和传
输范围变化的趋势.

表 1 各算法时间复杂度对比表 表 2 各算法空间复杂度对比表

路由算法 时间复杂度 路由算法 空间复杂度
t
t
HTD-IR O(|C |) HTD-IR O(32|VR |)
t
t
QGrid-M O(|VR |) QGrid-M O(27|VR |)
t
t
QGrid-G O(|VR |) QGrid-G O(18|VR |)
t
t
W-PAGPSR O(|VR |) W-PAGPSR O(23|VR |)

0.20 0.30
HTD-IR HTD-IR
QGrid-M QGrid-M
0.16 QGrid-G 0.25 QGrid-G
W-PAGPSR
W-PAGPSR
Execution time (ms) 0.12 Execution time (ms) 0.15
0.20
0.08
0.04 0.10
0.05
0 0
200 300 400 500 600 300 320 340 360 380 400
Number of vehicles Vehicle transmission range (m)
(a) 不同车辆数量下的算法执行时间 (R=360 m) (b) 不同车辆传输半径 R 下的算法执行时间
(车辆总数为 600)
图 19 车辆数量与传输半径 R 对算法执行时间的影响

0.010 0.010
HTD-IR HTD-IR
QGrid-M 0.008 QGrid-M
QGrid-G
QGrid-G
0.008
Resource occupancy (MB) 0.006 Resource occupancy (MB) 0.006
W-PAGPSR
W-PAGPSR
0.004
0.004
0.002

0 0.002 0
200 300 400 500 600 300 320 340 360 380 400
Number of vehicles Vehicle transmission range (m)
(a) 不同车辆数量下的算法内存资源占用 (R=360 m) (b) 不同车辆传输半径 R 下的算法内存资源占用
(车辆总数为 600)
图 20 车辆数量与传输半径 R 对算法内存资源占用的影响