SPARROW:基于平面分隔器的城市车载物联网可靠性约束路由
《Computer Communications》:SPARROW: Planar Separator–Based Reliability-Constrained Routing for Urban Vehicular IoT Networks
【字体:
大
中
小
】
时间:2026年09月30日
来源:Computer Communications 4.2
编辑推荐:
**摘要**
城市车联网(Urban VANETs)运行于受道路约束的拓扑结构中,其路由决策主要取决于交叉路口、交通动态和快速变化的连接状态。现有的车联网路由协议主要依赖局部启发式策略或基于交通状况的优化方案,这些方案往往缺乏可扩展性保证,产生显著的控制开销,并且在动态条件
**摘要**
城市车联网(Urban VANETs)运行于受道路约束的拓扑结构中,其路由决策主要取决于交叉路口、交通动态和快速变化的连接状态。现有的车联网路由协议主要依赖局部启发式策略或基于交通状况的优化方案,这些方案往往缺乏可扩展性保证,产生显著的控制开销,并且在动态条件下无法提供足够的可靠性保障。本文提出了SPARROW(基于分隔符的平面锚定路由,Separator-based Planar Anchor Routing for Roadway Overlays),这是一种将城市道路网络建模为平面交叉路口图并采用基于分隔符的层次分解方法以实现可扩展且可靠路由的路由协议。SPARROW采用两级设计,包括:(i)在压缩后的区域图上进行可靠性约束的走廊选择,以及(ii)沿道路段和交叉路口进行自适应的局部转发。我们提供了关于路由正确性、端到端可靠性、有界控制平面开销以及接近最优路径成本的正式保证。特别地,我们证明了路由状态随网络规模呈近似线性增长,更新保持局部化,且转发决策的计算复杂度很低。大量基于SUMO和NS-3的仿真结果表明,SPARROW在广泛的交通密度范围内始终优于代表性先进路由协议。在密集城市场景(250 veh/km2)中,SPARROW的分组投递率达到0.897,平均延迟为65 ms,同时保持了稳定的控制开销和较低的延迟波动。这些结果表明,将平面图结构直接嵌入路由设计可为城市车联网提供一种具有原则性和可扩展性的方法。
**引言**
城市车联网(VANETs)和车载物联网(V-IoT)系统构成了新兴智慧城市服务的通信骨干,包括协作感知、交通信号协调、紧急消息传播和大规模城市感知(Watfa, 2010; Watfa & Yaghi, 2010)。与通用移动自组织网络不同,城市车联网运行于高度受限的道路拓扑结构中,其中交叉路口、交通信号灯和障碍物主导了连接模式。因此,路由性能主要受交叉路口选择、道路段可用性和竞争动态的支配,而非欧几里得距离。这使得经典的贪婪地理路由在密集网格环境中不够稳定,且在稀疏或分区场景下不可靠(Boussoufa-Lahlah et al., 2018)。
因此,大量研究工作转向了基于交叉路口和道路感知的路由方案,在这些方案中,数据包沿着选定的道路段和交叉口转发,而非完全依赖贪婪的邻居选择。轻量级基于交叉路口的流量感知路由(LITAR)通过为交叉路口上的出站道路段打分来降低测量开销并提高投递率(Darwish & Abu Bakar, 2016)。连接感知方法如CISRP进一步集成了车辆可用性以缓解稀疏城市环境中的链路中断问题(Venkatramana et al., 2018)。骨干和基于网格的设计,例如延迟感知基于网格的地理路由(DGGR),通过在转发平面中施加结构来提高鲁棒性,特别是在混合稀疏-密集条件下(Chen et al., 2019)。更近期的协议,如MIS-CP,通过选择多个候选交叉路口绕过城市空洞来显式应对连接空洞问题(Zhou et al., 2021),而Geo-CAP则纳入了跨层链路动态性以更好地适应竞争和信道波动(Alzamzami & Mahgoub, 2021)。
尽管取得了上述进展,仍存在三个根本性局限:
- 首先,大多数基于交叉路口的协议依赖启发式或局部决策规则,未能利用城市道路网络的全局结构特性。城市道路图众所周知是平面或近平面图,交叉复杂度低,但这种结构很少被用来限制路由状态、更新成本或可扩展性。
- 其次,集成更丰富流量或链路信息的方法往往产生显著的控制开销或需要频繁的更新,这削弱了在密集部署中的可扩展性(Boussoufa-Lahlah et al., 2018; Darwish & Abu Bakar, 2016)。
- 第三,近期的基于仿生或学习辅助的交叉路口选择方案——例如城市车联网中基于蚁群的路由——虽然展示了实证改进,但通常缺乏对稳定性、收敛性或最坏情况开销的正式保证,在网络条件快速变化时尤其如此(Azzoug et al., 2024; Lee et al., 2024)。
从实用角度来看,城市车载物联网应用日益要求可预测的可靠性和低延迟,而非仅仅追求平均性能。安全消息、协作感知更新和实时交通控制都需要在拥塞、移动性突发和部分断连条件下仍保持可靠的路由机制。在局部最优间振荡、泛洪过多控制流量或在密度变化时崩溃的协议不适用于此类部署(Jeong et al., 2021)。从研究角度来看,(i)为平面图和分隔符提供强保证的图论成果与(ii)在移动性、干扰和不完整信息下运行的实用车联网路由协议之间存在着明显的差距。虽然平面图分隔符众所周知可以在静态图中产生紧凑表示和有界更新成本,但作为城市车载路由协议级设计原则的潜力尚未在文献中得到系统性探索。本文通过提出SPARROW(基于分隔符的平面锚定路由,Separator-based Planar Anchor Routing for Roadway Overlays)来弥合这些差距。这是一种显式将平面图论嵌入基于交叉路口的车联网路由设计中的路由协议。SPARROW将城市地图建模为平面交叉路口图,并应用基于分隔符的分解来构建具有紧凑边界摘要的区域层次结构。路由决策分两个阶段执行:在压缩后的区域图上进行可靠性约束的路径选择,随后进行适应即时链路和交通状况的局部交叉路口转发。通过将全局推理限制在分隔符边界上并将细粒度自适应委托给局部决策,SPARROW在可扩展性、自适应性和可靠性之间实现了原则性的平衡。
从更广阔的视角来看,现有的城市车联网路由协议可分为几个主要类别。贪婪地理路由协议(如GPSR和GPCR)依赖局部转发决策和边界恢复机制,但在城市网格环境中存在不稳定和迂回问题。基于交叉路口和流量感知的路由方案(包括LITAR、CISRP和DGGR)通过纳入道路拓扑和交通密度改进了性能,但仍主要依赖启发式方法,缺乏在动态条件下对可扩展性和可靠性的保证。连接空洞感知和多交叉路口选择协议(如MIS-CP)试图通过探索多个候选交叉口来缓解稀疏网络问题,但往往会增加复杂度和开销且缺乏正式界限。更近期的跨层和仿生路由方法(包括Geo-CAP和基于蚁群的方法)利用链路动态和自适应优化来提高性能,但通常依赖频繁的控制更新且缺乏对收敛性、稳定性或最坏情况行为的理论保证。
与这些方法不同,SPARROW通过引入一种基于平面图论的结构感知路由范式来挑战所有四个类别,其中路由决策受基于分隔符的层次结构和显式可靠性预算的约束。这使得SPARROW能够同时实现可扩展性、有界控制开销和可证明的可靠性保证——这些能力在当前先进协议中基本未被解决。本文的主要贡献有三方面:
1. **图论协议架构**:我们引入了一种基于分隔符的路由框架,利用城市道路网络的平面结构来限制路由状态和控制平面更新。
2. **可靠性约束的交叉路口路由**:我们将城市路由公式化为区域图上的约束最短路径问题,从而实现显式的端到端可靠性保证,而非启发式的尽力转发。
3. **城市规模的协议级验证**:通过大量基于真实城市移动性的分组级仿真,我们展示了与先进交叉路口感知路由协议相比,在分组投递率、延迟和延迟尾部行为方面的一致增益。
尽管城市车联网路由取得了显著进展,但现有方法在提供可扩展、可靠且有理论依据的路由决策方面仍存在根本性局限。首先,大多数基于交叉路口和流量感知的协议依赖局部启发式或短期测量,未能利用城市道路网络的全局结构特性,特别是其近平面拓扑。因此,路由状态和更新成本随网络规模不可预测地增长,限制了城市级部署的可扩展性。其次,虽然几种协议纳入了更丰富的度量指标如交通密度、链路质量或跨层信息,但这些增强往往引入了大量的控制开销和不稳定性,特别是在动态交通条件下。第三,新兴的仿生和学习辅助路由方案虽然展示了改进的实证性能,但缺乏对可靠性、收敛性和最坏情况行为的正式保证,使其不适用于安全关键的车载物联网应用。更根本的是,图论进展(如平面分隔符理论)与实用车联网路由协议设计之间仍存在明显脱节,现有协议很少利用这些结构特性来实现有界复杂度或可证明的性能。这些局限共同凸显了需要一种同时具备结构感知、可靠性约束和理论依据的路由框架,这也是SPARROW设计的动机所在。
本文其余部分组织如下:第2节回顾城市车联网路由的相关工作并指出本研究解决的未解决问题;第3节介绍系统模型和形式化问题描述;第4节详述SPARROW协议设计和算法;第5节提供可扩展性和正确性的理论分析;第6节描述仿真框架,第7节进行性能评估;第8节讨论结果并与现有文献进行比较;第9节总结全文并提出更广泛影响和未来研究方向。
---
**相关工作总结**
城市车联网路由已经历了若干不同的研究阶段,每个阶段都针对道路受限移动性、间歇性连接和无线竞争带来的特定挑战。本节回顾最相关的文献,并将所提出的SPARROW协议置于现有工作的背景下,突出已取得的成就、仍未解决的问题,以及为什么需要基于图论分隔符的方法。
---
**系统模型与问题描述**
本节形式化SPARROW所解决的城市车联网/物联网路由问题。我们首先定义基于图的系统模型,然后陈述假设条件,接着提出一个可靠性约束的优化问题,为协议设计提供依据。
---
**算法与协议设计**
本节详细介绍SPARROW路由协议。我们首先描述整体架构,然后是基于分隔符的数据结构,接着是路由工作流程、恢复机制,最后是正式的伪代码规范。该设计严格遵循上一节的问题描述,并将其转化为适用于车联网/物联网部署的分布式分组级协议。
---
**理论分析**
本节对SPARROW进行形式化分析,重点关注正确性、可靠性可行性、可扩展性和计算复杂度。结果证明SPARROW不仅在实证上有效,而且在理论上有据可依,弥补了先前城市车联网路由协议的一个重要缺陷。
---
**仿真框架**
本节描述用于评估SPARROW的实验方法。目标是确保可复现性、真实性和与先进城市车联网路由协议的公平比较。该框架密切遵循近期研究采用的最佳实践。
---
**结果与性能评估**
本节详细评估SPARROW在真实城市条件下的表现。我们分析了可靠性、延迟、开销、路径效率、尾部行为和控制平面稳定性,并将SPARROW与代表性先进协议进行比较。
---
**讨论**
本节综合所有实验结果,明确将其映射到现有文献中,并将SPARROW置于更广泛的车联网和物联网路由研究领域之中。讨论围绕先前确定的关键研究差距展开,并解释了SPARROW如何在实证和理论方面推动该领域进展。
---
**结论、更广泛影响与未来工作**
本文提出了SPARROW,一种面向城市车联网和车载物联网网络的图论路由协议,它显式利用了城市道路图的平面结构。通过将城市环境建模为平面交叉路口图,并在路由架构中嵌入基于分隔符的层次分解,SPARROW弥合了理论图论保证与实用车联网协议设计之间长期存在的鸿沟。通过可靠性约束的路由公式化和一个……
---
**数据可用性声明**
本研究期间生成和分析的所有数据均可在合理请求下从通讯作者处获得。用于模型和数据可视化的代码也可分享。
**稿件准备过程中生成式人工智能及AI辅助技术的声明**
在撰写本文过程中,作者使用了Elicit、Perplexity、ChatGPT、ResearchRabbit和Scopus AI来识别研究空白、总结研究文章,并结合先前已发表的工作重新表述本文结果。在使用这些工具/服务后,作者对内容进行了审核和编辑,并对所发表文章的内容承担全部责任。
**利益冲突声明**
? 作者声明不存在可能影响本论文工作的已知竞争性财务利益或个人关系。
**Mohamed K. Watfa**
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号