Ad Hoc车载自组网路由协议精讲第4篇：Chain-Branch-Leaf路由协议设计案例精讲

摘要

本文将带你深入了解Chain-Branch-Leaf（CBL）路由协议的设计理念与工作机制，帮助你掌握一种典型的车载自组网路由协议。你将学到CBL协议的三层组织结构、链路形成与维护算法、消息格式与状态机设计、CBL-OLSR实现方案等核心知识。

学习目标

阅读完本文后，你将能够：

理解CBL设计理念：掌握协议设计的目标和动机
掌握三层结构：理解链（Chain）、支（Branch）、叶（Leaf）的组织机制
学习工作流程：了解CBL协议的初始化、形成、维护和路由过程
掌握实现方案：理解CBL-OLSR的实现细节和优化策略
分析协议性能：认识CBL协议的优势和适用场景

引言：一个实际的车载路由协议

在前三篇文章中，我们学习了Ad Hoc路由协议的基本原理和车载环境的特殊挑战。现在，让我们通过一个完整的协议设计案例，将这些理论应用于实际。

Chain-Branch-Leaf（CBL）协议是专门为车载网络设计的路由协议，其核心思想是利用道路网络的结构特点，将车辆组织成三层分层的网络结构。这种结构既考虑了车辆的地理位置，又考虑了道路的拓扑关系，能够在高密度场景下实现高效的数据传输。

51学通信提示：CBL协议的设计体现了”因地制宜”的思想。它不试图在所有场景下都表现最优，而是针对车载环境的特点进行专门优化，在特定场景下（如城市道路网络）表现出色。

一、CBL协议的设计理念

1.1 设计目标与动机

CBL协议的设计源于对车载网络特点的深入分析和对现有协议局限性的认识。

车载网络的特点分析：

道路约束：车辆沿着道路移动，不能任意穿越
移动可预测：移动方向受道路限制，有一定可预测性
密度变化大：同一道路不同时段密度差异大
集群效应：同一方向的车辆自然形成集群

现有协议的局限性：

平面协议（如AODV）：可扩展性差，高密度时开销大
通用地理路由（如GPSR）：未充分利用道路结构
传统集群协议：集群边界固定，不适合动态场景

flowchart TD
    subgraph DesignMotivation["CBL设计动机"]
        direction TB

        subgraph Problems["现有协议问题"]
            P1["平面协议<br/>可扩展性差"]
            P2["地理路由<br/>未利用道路结构"]
            P3["固定集群<br/>不适合动态场景"]
        end

        subgraph Characteristics["车载网络特点"]
            C1["道路约束移动"]
            C2["移动可预测"]
            C3["密度变化大"]
            C4["自然集群效应"]
        end

        Problems --> Gap["设计缺口"]
        Characteristics --> Gap

        Gap --> Solution["CBL设计思路<br/>利用道路结构<br/>动态集群形成<br/>分层路由"]
    end

    style Problems fill:#ffebee,stroke:#c62828
    style Characteristics fill:#e8f5e9,stroke:#2e7d32
    style Gap fill:#fff9c4,stroke:#f57f17,stroke-width:3px
    style Solution fill:#e1f5fe,stroke:#0277bd,stroke-width:2px
    style DesignMotivation fill:#f3e5f5,stroke:#4a148c,stroke-width:3px

图表讲解：这张图展示了CBL协议设计的动机。左侧列出了现有协议的主要问题：平面协议可扩展性差，在高密度场景下控制开销过大；地理路由协议没有充分利用道路结构信息；固定集群协议无法适应车载网络的动态特性。右侧列出了车载网络的特点：道路约束移动、移动可预测、密度变化大、自然集群效应。这些特点和问题之间存在设计缺口，CBL协议的设计思路就是利用道路结构和车辆的集群效应，设计动态集群形成机制和分层路由结构。

1.2 设计原则

CBL协议遵循以下核心设计原则：

1. 道路感知原则

组织结构反映道路拓扑
路由决策考虑道路约束
利用地图信息优化决策

2. 动态形成原则

集群根据实际车辆位置动态形成
不依赖固定的集群边界
快速适应车辆移动

3. 分层管理原则

三层结构：链-支-叶
不同层级不同职责
降低管理复杂度

4. 本地化原则

决策基于本地信息
最小化全局信息需求
提高响应速度

1.3 核心概念定义

CBL协议定义了三个核心概念，对应网络的三层结构：

链（Chain）

沿同一条道路同向行驶的车辆序列
是CBL结构的基础层
负责主干数据传输

支（Branch）

从链分出，进入支路的车辆
是CBL结构的中间层
连接链和叶

叶（Leaf）

支路末端或集群边缘的车辆
是CBL结构的顶层
数据的源或宿

flowchart TD
    subgraph CBLHierarchy["CBL三层结构"]
        direction TB

        ChainLevel["链层<br/>主干道车辆<br/>负责主干传输"]
        BranchLevel["支层<br/>支路车辆<br/>连接链和叶"]
        LeafLevel["叶层<br/>末端车辆<br/>数据的源/宿"]

        ChainLevel --> C1["车辆C1"]
        ChainLevel --> C2["车辆C2"]
        ChainLevel --> C3["车辆C3"]

        BranchLevel --> B1["车辆B1<br/>来自C1"]
        BranchLevel --> B2["车辆B2<br/>来自C2"]
        BranchLevel --> B3["车辆B3<br/>来自C3"]

        LeafLevel --> L1["车辆L1<br/>B1的下游"]
        LeafLevel --> L2["车辆L2<br/>B2的下游"]
        LeafLevel --> L3["车辆L3<br/>B3的下游"]

        C1 -.->|分出| B1
        C2 -.->|分出| B2
        C3 -.->|分出| B3

        B1 --> L1
        B2 --> L2
        B3 --> L3
    end

    style ChainLevel fill:#e8f5e9,stroke:#2e7d32,stroke-width:2px
    style BranchLevel fill:#fff9c4,stroke:#f57f17,stroke-width:2px
    style LeafLevel fill:#e1f5fe,stroke:#0277bd,stroke-width:2px
    style CBLHierarchy fill:#f3e5f5,stroke:#4a148c,stroke-width:3px

图表讲解：这张图展示了CBL的三层结构。链层由主干道上的车辆C1、C2、C3组成，它们沿同一方向行驶，形成链结构。支层由从链分出的车辆组成，B1从C1分出进入支路，B2从C2分出，B3从C3分出。叶层是支路末端的车辆，L1是B1的下游车辆，L2是B2的下游车辆，L3是B3的下游车辆。这种结构自然地反映了道路网络的层次关系，数据可以在层内和层间高效传输。

二、CBL组织结构的形成机制

2.1 角色定义与转换

CBL协议中，每辆车可以扮演不同的角色，角色之间可以动态转换。

角色类型：

角色	英文	定义	职责
链头	Chain Head	链的第一个车辆	代表链，负责上行通信
链成员	Chain Member	链的中间车辆	转发数据
支头	Branch Head	支的第一个车辆	代表支，连接链和支
支成员	Branch Member	支的中间车辆	转发数据
叶节点	Leaf	集群末端车辆	数据源/宿

角色转换条件：

stateDiagram-v2
    [*] --> Unassigned: 节点启动

    Unassigned --> ChainHead: 形成新链<br/>或成为链首车
    Unassigned --> ChainMember: 加入现有链
    Unassigned --> BranchHead: 进入支路<br/>形成新支
    Unassigned --> Leaf: 处于集群边缘

    ChainHead --> ChainMember: 链向前延伸<br/>有新的前车
    ChainMember --> ChainHead: 原链头离开<br/>成为新链头
    ChainMember --> BranchHead: 转向进入支路
    ChainMember --> Leaf: 落后于前车<br/>超过距离阈值

    BranchHead --> BranchMember: 支向前延伸<br/>有新的前车
    BranchMember --> BranchHead: 原支头离开
    BranchMember --> Leaf: 落后于前车<br/>超过距离阈值

    Leaf --> ChainMember: 接近前方车辆<br/>加入链
    Leaf --> BranchMember: 接近前方车辆<br/>加入支

    ChainHead --> [*]: 离开网络
    ChainMember --> [*]: 离开网络
    BranchHead --> [*]: 离开网络
    BranchMember --> [*]: 离开网络
    Leaf --> [*]: 离开网络

图表讲解：这个状态图展示了CBL协议中车辆角色的转换过程。节点启动后处于未分配状态，根据位置和移动方向可以成为链头、链成员、支头或叶节点。角色之间可以动态转换：链头如果前方出现新的车辆（链向前延伸），则转为链成员；链成员如果原链头离开，可以成为新的链头；链成员如果转向进入支路，可以成为支头；如果与前方车辆距离过大，可以转为叶节点。这种动态转换机制确保CBL结构能够快速适应车辆移动和道路变化。

2.2 链形成算法

链是CBL结构的基础，形成算法需要考虑车辆的位置、速度和方向。

输入信息：

车辆自身的位置、速度、方向
邻居车辆的位置、速度、方向
电子地图信息（道路拓扑）

形成步骤：

flowchart TD
    subgraph ChainFormation["链形成算法"]
        direction TB

        Start["车辆启动"] --> Discover["发现邻居<br/>接收Hello消息"]

        Discover --> Classify{"邻居分类"}

        Classify -->|同向<br/>同道路| SameDirection["同向邻居集合"]
        Classify -->|其他| OtherNeighbors["其他邻居"]

        SameDirection --> Sort["按位置排序<br/>从前到后"]

        Sort --> CheckFront{"有前车?"}

        CheckFront -->|是| JoinChain["加入链<br/>成为链成员"]
        CheckFront -->|否| CreateChain["创建新链<br/>成为链头"]

        JoinChain --> RoleMember["角色: 链成员<br/>职责: 转发数据"]
        CreateChain --> RoleHead["角色: 链头<br/>职责: 代表链"]

        RoleMember --> Maintain["维护链状态<br/>监测前车距离"]
        RoleHead --> Maintain

        Maintain --> CheckDistance{"与前车距离?"}

        CheckDistance -->|&lt;阈值| Normal["正常<br/>保持当前角色"]
        CheckDistance -->|&gt;阈值| Recheck{"前方有新车?"}

        Recheck -->|是| JoinChain
        Recheck -->|否| BecomeLeaf["转为叶节点"]
    end

    style Start fill:#e8f5e9,stroke:#2e7d32,stroke-width:2px
    style JoinChain fill:#fff9c4,stroke:#f57f17,stroke-width:2px
    style CreateChain fill:#ffebee,stroke:#c62828,stroke-width:2px
    style RoleMember fill:#e1f5fe,stroke:#0277bd
    style RoleHead fill:#fff9c4,stroke:#f57f17
    style BecomeLeaf fill:#e0f2f1,stroke:#00695c
    style ChainFormation fill:#f3e5f5,stroke:#4a148c,stroke-width:3px

图表讲解：这张图展示了链形成的详细算法流程。车辆启动后首先发现邻居，通过Hello消息获取邻居的位置、速度和方向信息。然后将邻居分类，筛选出同向、同道路的邻居。对这些邻居按位置排序后，检查前方是否有车辆。如果有前车，则加入现有链成为链成员；如果没有前车，则创建新链成为链头。在维护阶段，持续监测与前车的距离。如果距离在阈值内，保持当前角色；如果距离超过阈值，检查前方是否有新的车辆可以加入链，如果有则加入，如果没有则转为叶节点。

关键参数：

距离阈值：决定车辆是否属于同一链（通常100-200米）
方向差异阈值：角度差异超过一定值认为不同向（通常15-30度）
速度差异阈值：速度差异过大时考虑分离（可变参数）

2.3 支形成算法

支是从链分出的结构，通常对应道路的分支或转弯。

触发条件：

车辆偏离当前道路方向（转弯）
道路分叉，车辆进入支路
车辆主动选择形成支（如为了服务支路上的车辆）

形成步骤：

sequenceDiagram
    autonumber
    participant Car as 车辆A
    participant ChainHead as 链头CH
    participant Ahead as 前方车辆

    Note over Car,Ahead: 车辆A在链中正常行驶

    Car->>Car: 检测到方向变化<br/>接近交叉口

    Car->>ChainHead: 发送支形成请求<br/>包含: 位置、方向、支路ID

    ChainHead->>ChainHead: 处理请求<br/>更新CBL结构

    ChainHead->>Car: 支形成确认<br/>分配: 支ID、角色

    Car->>Car: 转变为支头<br/>创建支结构

    Car->>Ahead: 发送支公告<br/>通知后续车辆

    Note over Car,Ahead: 支结构建立完成

图表讲解：这个序列图展示了支形成的交互过程。车辆A在链中正常行驶时检测到方向变化（如接近交叉口需要转弯），向链头发送支形成请求，包含位置、方向和支路ID信息。链头处理请求并更新CBL结构，然后向车辆A发送确认，分配支ID和角色。车辆A转变为支头并创建支结构，同时向前方车辆发送支公告。整个过程确保其他车辆了解结构变化，可以相应调整自己的角色。

支的特殊考虑：

支的方向性：支有明确的方向，从链向外的方向为正向
支的命名：支用支路ID标识，支路ID可以从地图获取
支的长度：支的长度不受严格限制，但过长的支可能需要子支

2.4 叶节点的识别

叶节点是CBL结构的边缘节点，通常是数据的源或宿。

叶节点的类型：

自然叶节点
- 支路末端的车辆
- 后方无其他车辆
孤立叶节点
- 与前方车辆距离超过阈值
- 临时孤立状态
主动叶节点
- 选择作为叶节点的车辆
- 通常是数据源（如传感器车辆）

flowchart TD
    subgraph LeafIdentification["叶节点识别"]
        direction TB

        Check["车辆状态检查"] --> Conditions{"满足条件?"}

        Conditions -->|后方无车<br/>超过500米| Leaf1["自然叶节点<br/>稳定状态"]
        Conditions -->|与前车距离<br/>&gt;阈值| Leaf2["孤立叶节点<br/>临时状态"]
        Conditions -->|有数据发送<br/>选择为叶| Leaf3["主动叶节点<br/>应用驱动"]

        Leaf1 --> Maintain1["持续监测<br/>等待后方车辆"]
        Leaf2 --> Monitor["监控前车距离<br/>尝试重新加入"]
        Leaf3 --> Maintain2["保持叶角色<br/>直到数据发送完成"]

        Monitor --> Recover{"前车接近?"}
        Recover -->|是| Rejoin["重新加入链或支"]
        Recover -->|否| Leaf2
    end

    style Check fill:#e8f5e9,stroke:#2e7d32,stroke-width:2px
    style Leaf1 fill:#e1f5fe,stroke:#0277bd,stroke-width:2px
    style Leaf2 fill:#fff9c4,stroke:#f57f17,stroke-width:2px
    style Leaf3 fill:#ffebee,stroke:#c62828,stroke-width:2px
    style LeafIdentification fill:#f3e5f5,stroke:#4a148c,stroke-width:3px

图表讲解：这张图展示了叶节点的识别和处理流程。车辆持续检查自身状态，如果满足叶节点条件之一，则转变为相应的叶节点类型。自然叶节点是稳定状态，车辆等待后方车辆接近。孤立叶节点是临时状态，车辆监控前车距离，尝试重新加入链或支。主动叶节点由应用驱动，车辆选择作为叶节点以便发送数据，保持该角色直到数据发送完成。这种灵活的叶节点识别机制可以适应不同的应用需求。

三、CBL协议的工作机制

3.1 消息类型与格式

CBL协议定义了几种关键消息类型：

3.1.1 Hello消息

Hello消息用于邻居发现和状态维护。

消息内容：

节点ID
当前角色（链头/链成员/支头/支成员/叶）
位置信息（经度、纬度）
移动信息（速度、方向）
链ID（如果属于链）
支ID（如果属于支）
序列号

flowchart LR
    subgraph HelloMsg["Hello消息结构"]
        direction TB

        Header["消息头<br/>类型: Hello<br/>长度: 可变<br/>序列号: SN"]

        Body["消息体"]
        Body --> NodeID["节点ID<br/>4字节"]
        Body --> Role["当前角色<br/>1字节"]
        Body --> Position["位置信息<br/>经度: 4字节<br/>纬度: 4字节"]
        Body --> Movement["移动信息<br/>速度: 2字节<br/>方向: 2字节"]
        Body --> ChainInfo["链信息<br/>链ID: 4字节<br/>链内位置: 2字节"]
        Body --> BranchInfo["支信息<br/>支ID: 4字节<br/>支内位置: 2字节"]
    end

    style Header fill:#e8f5e9,stroke:#2e7d32,stroke-width:2px
    style Body fill:#fff9c4,stroke:#f57f17,stroke-width:2px
    style HelloMsg fill:#e1f5fe,stroke:#0277bd,stroke-width:3px

图表讲解：这张图展示了Hello消息的详细结构。消息头包含消息类型、长度和序列号。消息体包含节点ID、当前角色、位置信息、移动信息、链信息和支信息。位置信息使用经纬度表示，移动信息包含速度和方向，链信息包含链ID和节点在链中的位置，支信息包含支ID和节点在支中的位置。这些信息使得接收节点可以全面了解发送节点的状态，便于做出正确的CBL决策。

3.1.2 链管理消息

链管理消息用于链的建立和维护。

消息类型：

链形成请求：请求形成新链
链形成响应：响应链形成请求
链加入请求：请求加入现有链
链加入响应：响应链加入请求
链离开通知：通知离开链

3.1.3 支管理消息

支管理消息用于支的建立和维护。

消息类型：

支形成请求：请求形成新支
支形成响应：响应支形成请求
支加入请求：请求加入现有支
支加入响应：响应支加入请求
支离开通知：通知离开支

3.1.4 数据消息

数据消息承载应用数据。

特点：

使用CBL结构路由
包含源和目的信息
可以是单播、组播或广播

3.2 路由机制

CBL协议使用分层路由机制，充分利用结构信息。

3.2.1 链内路由

在同一链内，数据沿链方向流动。

规则：

前向数据：从链头向链尾传输
后向数据：从链尾向链头传输
跳数限制：通常不超过链长度

flowchart TD
    subgraph IntraChainRouting["链内路由"]
        direction TB

        Chain["链: CH - C1 - C2 - C3 - C4 - CF"]

        CH["链头CH"]
        C1["成员C1"]
        C2["成员C2"]
        C3["成员C3"]
        C4["成员C4"]
        CF["链尾CF"]

        CH --> C1 --> C2 --> C3 --> C4 --> CF

        Path1["前向路由<br/>CH → C1 → C2 → C3 → C4 → CF"]
        Path2["后向路由<br/>CF → C4 → C3 → C2 → C1 → CH"]

        CH -.->|数据流向| Path1
        CF -.->|数据流向| Path2
    end

    style CH fill:#ffebee,stroke:#c62828,stroke-width:2px
    style CF fill:#e8f5e9,stroke:#2e7d32,stroke-width:2px
    style C1 fill:#e1f5fe,stroke:#0277bd
    style C2 fill:#e1f5fe,stroke:#0277bd
    style C3 fill:#e1f5fe,stroke:#0277bd
    style C4 fill:#e1f5fe,stroke:#0277bd
    style Path1 fill:#fff9c4,stroke:#f57f17,stroke-width:2px
    style Path2 fill:#fff9c4,stroke:#f57f17,stroke-width:2px
    style IntraChainRouting fill:#f3e5f5,stroke:#4a148c,stroke-width:3px

图表讲解：这张图展示了链内路由的两个方向。前向路由从链头CH向链尾CF传输数据，依次经过成员C1、C2、C3、C4。后向路由从链尾CF向链头CH传输数据，依次经过成员C4、C3、C2、C1。这种简单的路由机制充分利用了链的线性结构，数据沿链方向流动，每个节点只需要知道前后邻居即可，不需要复杂的路由表。

3.2.2 链间路由

不同链之间的数据传输需要通过支连接。

规则：

找到源链和目的链的连接点
通过支连接两个链
可能需要多跳（链-支-链-支-链）

flowchart TD
    subgraph InterChainRouting["链间路由"]
        direction TB

        Chain1["链1: CH1 - C1 - C2"]
        Chain2["链2: CH2 - C3 - C4"]
        Chain3["链3: CH3 - C5 - C6"]

        Branch1["支1: 从C2分出"]
        Branch2["支2: 连接到C3"]

        C2 --> B1["支头BH1"]
        B1 --> B1_1["支成员"]
        B1_1 --> B1_2["支成员"]
        B1_2 --> BH2["支头BH2"]
        BH2 --> C3

        Route1["路由: CH1 → C1 → C2 → BH1 → ... → BH2 → C3 → CH2"]

        CH1["链头1"] --> C1 --> C2
        CH2["链头2"] --> C3 --> C4
        CH3["链头3"] --> C5 --> C6

        style Chain1 fill:#e8f5e9,stroke:#2e7d32
        style Chain2 fill:#fff9c4,stroke:#f57f17
        style Chain3 fill:#e1f5fe,stroke:#0277bd
        style Branch1 fill:#f3e5f5,stroke:#6a1b9a
        style Branch2 fill:#f3e5f5,stroke:#6a1b9a
        style Route1 fill:#ffebee,stroke:#c62828,stroke-width:2px
        style InterChainRouting fill:#e0f2f1,stroke:#00695c,stroke-width:3px

图表讲解：这张图展示了链间路由的示例。有三个链：链1（CH1-C1-C2）、链2（CH2-C3-C4）、链3（CH3-C5-C6）。从链1到链2的连接通过支1和支2实现。C2是链1的成员，从C2分出支1，支头是BH1。支1经过中间成员到达BH2，BH2连接到链2的C3。整个路由路径是CH1→C1→C2→BH1→…→BH2→C3→CH2。这种链-支-链的结构可以灵活地连接不同道路上的车辆，形成覆盖广泛的路由网络。

3.2.3 到叶节点的路由

叶节点是数据的最终目的地，路由需要到达具体的叶节点。

策略：

找到叶节点所属的链或支
路由到该链或支的连接点
沿链或支到达叶节点

3.3 维护机制

CBL结构需要持续维护以应对车辆移动。

3.3.1 周期性维护

Hello消息交换：

周期性发送Hello消息
更新邻居信息
检测节点离开

角色检查：

定期检查角色是否仍然合适
必要时发起角色转换

3.3.2 事件驱动维护

触发事件：

新邻居到达
现有邻居离开
角色变化
道路变化（如通过交叉口）

响应动作：

更新本地CBL状态
发送相应的管理消息
通知受影响的节点

flowchart TD
    subgraph EventDrivenMaintenance["事件驱动维护"]
        direction TB

        Event["检测到事件"] --> Classify{"事件类型"}

        Classify -->|新邻居| HandleNew["处理新邻居<br/>评估是否加入链/支"]
        Classify -->|邻居离开| HandleLeave["处理邻居离开<br/>更新结构"]
        Classify -->|方向变化| HandleTurn["处理转向<br/>可能形成支"]
        Classify -->|距离变化| HandleDist["处理距离变化<br/>可能角色转换"]

        HandleNew --> Update1["更新本地状态"]
        HandleLeave --> Update2["更新本地状态"]
        HandleTurn --> Update3["更新本地状态"]
        HandleDist --> Update4["更新本地状态"]

        Update1 --> Notify{"需要通知?"}
        Update2 --> Notify
        Update3 --> Notify
        Update4 --> Notify

        Notify -->|是| SendMsg["发送管理消息"]
        Notify -->|否| Done["处理完成"]

        SendMsg --> Done
    end

    style Event fill:#e8f5e9,stroke:#2e7d32,stroke-width:2px
    style HandleNew fill:#fff9c4,stroke:#f57f17
    style HandleLeave fill:#ffebee,stroke:#c62828
    style HandleTurn fill:#e1f5fe,stroke:#0277bd
    style HandleDist fill:#e0f2f1,stroke:#00695c
    style SendMsg fill:#f3e5f5,stroke:#4a148c
    style EventDrivenMaintenance fill:#e0f2f1,stroke:#00695c,stroke-width:3px

图表讲解：这张图展示了事件驱动维护的流程。当检测到事件时，首先分类事件类型，然后调用相应的处理函数。新邻居到达时评估是否加入链或支；邻居离开时更新结构；方向变化时可能形成支；距离变化时可能需要角色转换。处理完成后更新本地状态，判断是否需要通知其他节点。如果需要通知，则发送相应的管理消息。这种事件驱动的维护机制可以快速响应网络变化，保持CBL结构的准确性和时效性。

四、CBL-OLSR实现方案

4.1 OLSR协议基础

OLSR（优化链路状态路由）是经典的表驱动路由协议。

核心机制：

多点中继（MPR）：选择部分节点转发广播消息
链路感知：只感知对称链路
拓扑控制（TC）消息：周期性广播拓扑信息

优势：

路由发现快
适合持续通信
控制消息相对较少

挑战：

在高密度场景下开销仍然较大
未考虑道路约束

4.2 CBL与OLSR的结合

CBL-OLSR将CBL的结构化思想融入OLSR协议。

结合策略：

结构感知的MPR选择
- 在CBL结构内选择MPR
- 优先选择链头和支头
- 减少冗余转发
分层拓扑控制
- 链内TC消息
- 链间聚合消息
- 降低全局开销
路由表优化
- 链内路由直接使用结构信息
- 链间路由使用聚合信息
- 减小路由表大小

flowchart TD
    subgraph CBLOLSR["CBL-OLSR架构"]
        direction TB

        subgraph CBLLayer["CBL层"]
            CBL1["链1<br/>CH1-C1-C2"]
            CBL2["链2<br/>CH2-C3-C4"]
            CBL3["支1<br/>BH1-B1-B2"]

            CBL1 --> CBL3
            CBL3 --> CBL2
        end

        subgraph OLSRLayer["OLSR层"]
            MPR["MPR选择<br/>结构感知"]
            TC["拓扑控制<br/>分层广播"]
            Route["路由表<br/>结构优化"]
        end

        subgraph Integration["集成机制"]
            I1["CBL结构<br/>指导MPR选择"]
            I2["CBL层次<br/>指导TC聚合"]
            I3["CBL信息<br/>优化路由表"]
        end

        CBLLayer --> Integration
        OLSRLayer --> Integration

        I1 --> MPR
        I2 --> TC
        I3 --> Route
    end

    style CBLLayer fill:#e8f5e9,stroke:#2e7d32
    style OLSRLayer fill:#fff9c4,stroke:#f57f17
    style Integration fill:#e1f5fe,stroke:#0277bd,stroke-width:3px
    style CBLOLSR fill:#f3e5f5,stroke:#4a148c,stroke-width:3px

图表讲解：这张图展示了CBL-OLSR的集成架构。底部是CBL层，定义了网络的链和支结构。中间是OLSR层，包含MPR选择、拓扑控制和路由表功能。顶部是集成机制，将CBL的结构信息融入OLSR。CBL结构指导MPR的选择，优先选择关键节点（如链头、支头）。CBL的层次结构指导拓扑控制消息的聚合，链内使用详细消息，链间使用聚合消息。CBL信息还优化路由表，链内路由直接使用结构信息而不需要路由发现。这种集成充分利用了CBL和OLSR的优势，实现高效的路由。

4.3 实现细节

4.3.1 数据结构扩展

CBL-OLSR节点需要维护的信息：

classDiagram
    class CBLOLSRNode {
        +NodeID ID
        +Position position
        +CBLRole role
        +ChainInfo chainInfo
        +BranchInfo branchInfo
        +NeighborTable neighbors
        +MPRSet mprSet
        +RoutingTable routes
        +updateCBLRole()
        +selectMPR()
        +generateTC()
        +updateRoutes()
    }

    class ChainInfo {
        +ChainID chainID
        +NodePosition posInChain
        +ChainHeadID headID
        +ChainTailID tailID
    }

    class BranchInfo {
        +BranchID branchID
        +NodePosition posInBranch
        +BranchHeadID headID
        +ParentChainID parentChain
    }

    class NeighborEntry {
        +NodeID neighborID
        +CBLRole role
        +LinkStatus status
        +LastSeenTime time
    }

    CBLOLSRNode --> ChainInfo
    CBLOLSRNode --> BranchInfo
    CBLOLSRNode --> NeighborEntry

图表讲解：这个类图展示了CBL-OLSR节点的数据结构。每个节点有ID、位置、CBL角色、链信息、支信息、邻居表、MPR集合和路由表。链信息包含链ID、节点在链中的位置、链头ID和链尾ID。支信息包含支ID、节点在支中的位置、支头ID和父链ID。邻居表记录每个邻居的ID、角色、链路状态和最后见到的时间。这些数据结构支持CBL-OLSR协议的完整功能。

4.3.2 MPR选择算法

传统OLSR MPR选择：

选择能覆盖所有两跳邻居的最小节点集
不考虑网络结构

CBL-OLSR MPR选择：

优先选择链头和支头
在同一链内选择连续节点
减少跨结构的MPR选择

flowchart TD
    subgraph MPRSelection["CBL-OLSR MPR选择"]
        direction TB

        Start["开始选择MPR"] --> GetOneHop["获取一跳邻居集合"]

        GetOneHop --> GetTwoHop["获取两跳邻居集合"]

        GetTwoHop --> Classify{"邻居分类"}

        Classify --> Heads["链头和支头<br/>优先级1"]
        Classify --> ChainMembers["链成员<br/>优先级2"]
        Classify --> Others["其他节点<br/>优先级3"]

        Heads --> Select1["优先选择<br/>覆盖两跳邻居"]
        ChainMembers --> Select2["补充选择<br/>覆盖剩余"]
        Others --> Select3["最后选择<br/>必要节点"]

        Select1 --> Check1{"覆盖全部?"}
        Select2 --> Check2{"覆盖全部?"}
        Select3 --> Check3{"覆盖全部?"}

        Check1 -->|是| Done["选择完成"]
        Check1 -->|否| Select2

        Check2 -->|是| Done
        Check2 -->|否| Select3

        Check3 --> Done
    end

    style Start fill:#e8f5e9,stroke:#2e7d32,stroke-width:2px
    style Heads fill:#ffebee,stroke:#c62828,stroke-width:2px
    style ChainMembers fill:#fff9c4,stroke:#f57f17,stroke-width:2px
    style Others fill:#e1f5fe,stroke:#0277bd,stroke-width:2px
    style Done fill:#c8e6c9,stroke:#2e7d32
    style MPRSelection fill:#f3e5f5,stroke:#4a148c,stroke-width:3px

图表讲解：这张图展示了CBL-OLSR的MPR选择算法。首先获取一跳和两跳邻居集合，然后将邻居分类为链头/支头（最高优先级）、链成员（中等优先级）和其他节点（低优先级）。优先选择链头和支头作为MPR，如果它们不能覆盖全部两跳邻居，则补充选择链成员。如果仍然不能覆盖，最后选择其他节点。这种结构感知的MPR选择可以优化转发节点集，减少冗余转发。

4.3.3 拓扑控制（TC）消息生成

传统OLSR TC消息：

每个节点周期性广播
包含所有邻居信息
开销随网络规模增长

CBL-OLSR TC消息：

链头聚合链内信息
支头聚合支内信息
减少消息数量和大小

TC消息生成策略：

详细TC：链头广播链内所有成员
聚合TC：链间只广播链摘要
增量TC：只广播变化部分

4.4 性能优化

CBL-OLSR在多个方面优化性能：

4.4.1 控制开销优化

优化方法：

结构感知的MPR减少转发
分层TC减少广播
自适应更新频率

效果：

控制开销降低30-50%
在高密度场景下优势明显

4.4.2 路由发现延迟优化

优化方法：

链内路由无需发现
使用结构信息快速决策
预测性路由建立

效果：

链内路由延迟接近零
跨链路由延迟降低50%

4.4.3 可靠性优化

优化方法：

多路径支持
快速故障检测
本地修复机制

效果：

数据投递率提高
路由恢复时间缩短

五、CBL协议的性能分析

5.1 仿真环境

仿真工具：OPNET Modeler、NS-3

场景设置：

高速公路场景：多车道、单向
城市场景：网格道路、交叉口
车辆密度：50-500辆车
移动速度：60-120 km/h

5.2 性能指标

指标	CBL-OLSR	纯OLSR	改进
控制开销	低	高	-40%
路由发现延迟	低	中	-50%
数据投递率	高	高	持平
端到端时延	低	中	-30%
可扩展性	优秀	良好	支持更大规模

5.3 适用场景

CBL协议最适合的场景：

高密度城市道路
- 车辆密度高
- 道路结构复杂
- 需要高效组织
高速公路车队
- 车辆自然形成链
- 相对移动缓慢
- 适合链结构
交叉口区域
- 多条道路交汇
- 支结构自然形成
- 需要灵活路由

不适合的场景：

稀疏乡村道路
- 车辆太少
- 难以形成稳定结构
- 地理路由更合适
高移动随机场景
- 移动不遵循道路
- 结构频繁破坏
- 按需路由更合适

核心概念总结

概念	定义	应用场景	关键参数
链（Chain）	同向道路上的车辆序列	主干道传输	距离阈值、方向阈值
支（Branch）	从链分出的支路车辆	道路分支、转弯	支路ID、分叉点
叶（Leaf）	集群末端车辆	数据源/宿	隔离距离
链头	链的第一个车辆	代表链、上行通信	负责链管理
支头	支的第一个车辆	连接链和支	负责支管理
MPR	多点中继节点	广播转发	覆盖两跳邻居

常见问题解答

Q1：CBL协议如何处理车辆在交叉口的多方向选择？

答：交叉口是CBL协议需要特别处理的关键场景，因为车辆可能选择不同方向，导致CBL结构发生变化。CBL协议通过一系列机制处理这种情况。

当车辆接近交叉口时，首先会检测到方向变化的可能性。通过GPS获取的移动方向和电子地图的道路信息，车辆可以预测即将进入哪条支路。在进入支路前，车辆会向当前链的链头发送支形成请求，包含计划进入的支路ID、位置和时间信息。链头收到请求后，会更新CBL结构，将该车辆标记为即将离开，并准备形成新的支。

一旦车辆实际转向进入支路，它就转变为支头角色，开始形成支结构。车辆会向后方车辆发送支公告消息，通知它们支的形成。后方车辆可以选择继续沿原链前进，或者跟随转向进入支。这种灵活的选择机制适应不同的交通场景。

对于多条支路的情况，每个支路独立形成和管理。CBL协议支持从同一条链分出多个支，每个支有自己的支头和支ID。链头维护所有支的信息，可以协调不同支之间的通信。

在某些复杂交叉口（如五岔路口），CBL协议可能形成嵌套的支结构。例如，主支上可能还有子支，形成链-支-子支的三层结构。这种嵌套结构可以处理任意复杂的道路网络，但也会增加管理复杂度。

51学通信站长爱卫生指出，交叉口处的CBL结构变化是最容易出现问题的时刻。协议设计需要特别关注这个场景的鲁棒性，包括处理转向失败、支路拥堵、车辆改变主意等情况。实际部署时，建议在仿真环境中充分测试各种交叉口场景。

Q2：CBL协议在车辆密度变化大的场景下如何适应？

答：车辆密度的大幅变化是车载网络的常见情况，CBL协议通过多种机制适应这种变化。

在低密度场景下，车辆之间距离较远，可能无法形成完整的链。此时CBL协议会自动调整参数，增加距离阈值，使车辆可以形成更松散的链。即使无法形成链，车辆仍然可以作为孤立叶节点运行，使用地理路由或其他备用路由方式。当密度进一步降低到网络可能分区时，CBL协议会检测到分区状态，启动存储转发机制，将数据缓存直到遇到其他车辆。

在高密度场景下，车辆之间距离很近，链可能变得很长。此时CBL协议需要考虑链的分割，避免单条链过长导致管理困难。协议会自动将长链分割为多个较短的链，每个链有自己的链头。这种分割基于距离阈值和车辆数量阈值，确保每条链的规模在可控范围内。

当密度动态变化时，CBL协议通过持续监测和角色转换适应。例如，当一辆车与前车的距离增加超过阈值时，它可能从链成员转为叶节点。反之，当叶节点接近前方车辆时，它可以重新加入链。这种动态调整使CBL结构始终与实际车辆分布匹配。

CBL协议还采用自适应的Hello消息频率。在密度高、变化快的场景下，增加Hello频率以快速跟踪变化；在密度低、变化慢的场景下，降低Hello频率以节省能量和带宽。这种自适应机制在保证结构准确性的同时优化资源使用。

在极端的密度变化（如从拥堵到畅通的快速变化）时，CBL协议可能需要触发重新组织。车辆会暂时进入过渡状态，等待结构稳定后再确定最终角色。这种短暂的过渡状态是必要的，可以避免频繁的角色变化导致的不稳定。

Q3：CBL-OLSR相比纯OLSR有哪些具体改进？实际性能提升多少？

答：CBL-OLSR将CBL的结构化思想融入OLSR协议，在多个方面进行了改进，实际仿真和测试显示性能提升显著。

最显著的改进是控制开销的降低。纯OLSR中，每个节点周期性广播拓扑控制（TC）消息，消息大小与邻居数成正比。在500辆车的高密度场景下，这会产生巨大的控制流量。CBL-OLSR通过结构感知的MPR选择和分层TC广播，将控制开销降低约40%。在链内，只有链头广播详细的TC消息；在链间，使用聚合的摘要信息。这种分层广播大幅减少了冗余信息。

路由发现延迟是另一个重要改进。纯OLSR需要等待TC消息泛洪全网才能建立路由，延迟较高。CBL-OLSR利用结构信息，链内路由几乎零延迟（直接沿链转发），跨链路由的延迟也降低约50%。对于安全应用这种对延迟敏感的场景，这种改进至关重要。

可扩展性的提升在大规模网络中尤为明显。纯OLSR的控制开销随网络规模平方增长，限制了可支持的网络大小。CBL-OLSR的开销增长较慢，因为结构化组织减少了不必要的全局信息交换。仿真显示，CBL-OLSR可以支持1000+车辆的网络，而纯OLSR在500车辆时性能就开始下降。

在数据投递率方面，CBL-OLSR与纯OLSR相当，都接近100%。这表明结构化组织没有损害数据传输的可靠性。在端到端时延方面，CBL-OLSR降低约30%，这是因为更优化的路径选择和更少的中间跳数。

实际测试还显示，CBL-OLSR在能耗效率上有改进。虽然车载设备能量充足不是主要约束，但减少不必要的通信仍然有价值。CBL-OLSR通过减少冗余转发和降低控制消息频率，使能耗降低约25%。

需要指出的是，CBL-OLSR的改进是场景依赖的。在道路结构清晰、车辆密度适中的场景下，改进最为明显。在车辆稀少或道路结构简单的场景下，CBL-OLSR的优势减弱，纯OLSR或更简单的协议可能更合适。

Q4：CBL协议如何处理链路断开和路由失效？

答：链路断开和路由失效是移动自组网的固有问题，CBL协议设计了专门的机制快速检测和恢复。

快速检测是快速恢复的前提。CBL协议使用多重检测机制：Hello消息超时检测、链路层ACK反馈、信号强度监测。当任何一种机制指示链路问题时，立即触发恢复流程。特别是在高速移动场景下，信号强度的快速下降是链路即将断开的早期预警，CBL协议可以在链路实际断开前采取行动。

本地修复是首选策略。当检测到链路断开时，首先尝试本地寻找替代路径。在CBL结构中，这可能意味着寻找同一链内的其他前车，或者通过相邻的支绕过断点。本地修复速度快，通常在几十毫秒内完成，对应用的影响最小。

如果本地修复失败，CBL协议会触发结构重组。这涉及重新评估车辆的角色，可能形成新的链或支。例如，如果链头离开，第二个车辆自动成为新的链头；如果链中间断开，形成两个独立的链。结构重组可能涉及多个车辆的角色变化，需要协调完成。

对于正在传输的数据，CBL协议提供了缓存机制。当路由失效时，数据包被临时缓存，等待新路由建立。缓存有大小限制和时间限制，超时的数据包会被丢弃。这种机制可以减少数据丢失，特别是在路由快速切换的场景下。

在严重情况下，如网络分区，CBL协议会启动存储转发模式。车辆将数据存储在本地，等待遇到其他车辆时转发。这种模式虽然延迟很高，但在完全隔离的场景下是唯一的选择。对于安全告警等关键数据，即使延迟高也比完全不传输好。

CBL协议还支持多路径传输作为提高可靠性的手段。对于关键数据，可以同时沿多条路径发送，即使某条路径失效，其他路径仍然可以送达。这种冗余传输会增加开销，但对于关键应用是值得的。

51学通信认为，链路断开处理的核心是快速检测和快速恢复。CBL协议通过结构化的组织，使恢复更加有针对性，不需要全局重新发现路由，这是相比平面协议的优势。

Q5：CBL协议如何与地图数据和GPS系统集成？

答：地图数据和GPS系统是CBL协议的重要组成部分，协议设计了专门的接口和机制利用这些信息。

GPS系统提供实时位置信息，是CBL协议的基础输入。CBL协议通过标准接口（如NMEA 0183）获取GPS数据，包括经纬度、速度、航向、时间戳等。这些信息经过校验和滤波处理后，用于邻居发现、角色判断、路由决策。GPS数据的准确性直接影响CBL结构的正确性，因此协议设计了异常检测机制，识别并处理错误的GPS数据。

地图数据提供道路拓扑信息，是CBL协议组织结构的基础。CBL协议支持多种地图格式（如OpenStreetMap、HERE Maps），通过地图API查询道路信息。关键的查询包括：当前位置所在道路、道路方向、道路连接关系、交叉口信息等。这些信息用于判断车辆是否在同一条路上、是否有支路形成、如何命名支等。

地图数据的精度和更新频率影响CBL协议的性能。高精度的地图（如厘米级精度）可以更准确地判断车辆位置关系，但数据量大、查询慢。CBL协议通常使用几米精度的地图，在精度和性能之间取得平衡。地图数据需要定期更新，以反映道路变化（如新修道路、道路改道）。

GPS和地图数据的融合是CBL协议的关键能力。GPS提供车辆的实际位置，地图提供道路的约束信息，两者结合可以准确判断车辆在道路网络中的位置。CBL协议使用地图匹配算法，将GPS坐标映射到具体道路上。这个过程处理GPS误差（如GPS漂移）和道路歧义（如在多层道路上）。

对于没有GPS或GPS信号弱的场景（如隧道、室内停车场），CBL协议设计了降级模式。可以使用其他定位方式（如基站定位、惯性导航），或者退化为纯拓扑协议，不依赖精确位置信息。这种降级模式虽然性能下降，但可以保证基本功能。

CBL协议还支持预测性定位，利用车辆的速度和方向预测未来位置。这对于提前准备路由切换、优化转发决策很有价值。预测基于运动学模型，结合地图的道路约束，可以在未来几秒内准确预测车辆位置。

在实际部署中，CBL协议需要与车载信息系统的其他组件集成。例如，与导航系统共享地图数据，与车况监控系统共享车辆状态，与安全应用共享CBL结构信息。这种集成需要标准化的接口和数据格式，CBL协议采用通用的数据交换格式（如JSON、Protocol Buffers）便于集成。

51学通信站长爱卫生指出，GPS和地图系统的可靠性直接影响CBL协议的实用性。在实际部署中，需要考虑GPS欺骗、地图错误等异常情况，设计鲁棒的处理机制。同时，也需要平衡精度与性能，避免过度依赖高精度数据导致系统复杂度过高。

总结

本文深入介绍了Chain-Branch-Leaf路由协议的设计案例。我们学习了CBL协议的设计理念和动机、三层组织结构的形成机制、消息格式与状态机、路由与维护机制、CBL-OLSR实现方案，以及性能分析。

CBL协议是车载路由协议设计的优秀案例，它充分利用道路网络的结构特点，通过动态分层组织实现高效的数据传输。理解CBL协议的设计思想，对于掌握车载路由协议的设计方法具有重要价值。

下篇预告

下一篇我们将深入探讨车载网络建模与仿真技术，带你了解无线电波传播模型、车辆移动性模型、主流仿真工具对比、802.11p协议栈建模等核心技术，为协议性能评估打下坚实基础。

本文由”51学通信”（公众号：51学通信，站长：爱卫生）原创分享。如需深入交流或获取更多通信技术资料，欢迎添加微信：gprshome201101。

51学通信

探索

04-Chain-Branch-Leaf路由协议设计案例精讲

Ad Hoc车载自组网路由协议精讲 第4篇：Chain-Branch-Leaf路由协议设计案例精讲

摘要

学习目标

引言：一个实际的车载路由协议

一、CBL协议的设计理念

1.1 设计目标与动机

1.2 设计原则

1.3 核心概念定义

二、CBL组织结构的形成机制

2.1 角色定义与转换

2.2 链形成算法

2.3 支形成算法

2.4 叶节点的识别

三、CBL协议的工作机制

3.1 消息类型与格式

3.1.1 Hello消息

3.1.2 链管理消息

3.1.3 支管理消息

3.1.4 数据消息

3.2 路由机制

3.2.1 链内路由

3.2.2 链间路由

3.2.3 到叶节点的路由

3.3 维护机制

3.3.1 周期性维护

3.3.2 事件驱动维护

四、CBL-OLSR实现方案

4.1 OLSR协议基础

4.2 CBL与OLSR的结合

4.3 实现细节

4.3.1 数据结构扩展

4.3.2 MPR选择算法

4.3.3 拓扑控制（TC）消息生成

4.4 性能优化

4.4.1 控制开销优化

4.4.2 路由发现延迟优化

4.4.3 可靠性优化

五、CBL协议的性能分析

5.1 仿真环境

5.2 性能指标

5.3 适用场景

核心概念总结

常见问题解答

Q1：CBL协议如何处理车辆在交叉口的多方向选择？

Q2：CBL协议在车辆密度变化大的场景下如何适应？

Q3：CBL-OLSR相比纯OLSR有哪些具体改进？实际性能提升多少？

Q4：CBL协议如何处理链路断开和路由失效？

Q5：CBL协议如何与地图数据和GPS系统集成？

总结

下篇预告

关系图谱

目录

Ad Hoc车载自组网路由协议精讲第4篇：Chain-Branch-Leaf路由协议设计案例精讲