第 4 周 弹性自组网与动态拓扑

HopCone、异步状态与可执行链路

石守谦

2027 春季 · 资料核对至 2026-10-15

通信如何影响协作

• 数据包沿哪条路径到达？
• 节点掌握的位置有多旧？
• 模型怎样处理迟到和失联？

连接W2消息格式约定和W3无线基础。此处关注数据包到达目的节点，不等于完成救援任务。后续学习模型必须使用本周提供的可达性、时延与状态年龄，而不是绕过网络。

无人机自组织网络

• Ad Hoc：节点直接组网
• Mesh：多跳转发形成网状连接
• FANET：节点运动快，链路持续变化

避免宣称所有Mesh都无基础设施，或者所有FANET都更难。困难取决于速度、遮挡、流量和硬件。要解释某一场景的新挑战，需要给出状态失效的机制和尺度。

链路需要分别验证两个方向

每个方向分别收集链路证据，并设置有效期限。

每个方向分别收集链路证据，并设置有效期限。

解释功率、天线朝向和干扰都可能造成不对称。HopCone通过对方心跳消息的接收集合等信息确认双向关系。一次历史成功也不能保证当前必然成功，所以状态需要过期管理。

三类路由方法

方法	维护的信息
主动路由	持续更新路由表
按需路由	有任务时寻找路径
地理路由	根据位置选择下一跳

AODV可作reactive例子，OLSR作proactive例子。不能说一种机制在所有条件下控制开销最低。保持目的位置获取的成本显式，是后面比较的核心。

定位之后还需要通信

• GNSS 提供本机的位置与时间
• 其他节点的位置需要接收和保存
• 位置记录应附带生成时间与来源

gpsr · MobiCom 2000；dream · MobiCom 1998

用W2身份与坐标字段复习。目的位置可以来自独立服务或分布式传播，不应把“位置服务”误写为必然中心化。HopCone试图消除的是独立的查询边界。

来源与阅读边界： - GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. MobiCom 2000. https://www.icir.org/bkarp/gpsr/gpsr.html 核验深度：原作者页面/论文。使用边界：不能把2D planar recovery直接套到3D。 - A Distance Routing Effect Algorithm for Mobility (DREAM). MobiCom 1998. https://www.comp.nus.edu.sg/~bleong/geographic/related/basagni98dream.pdf 核验深度：论文。使用边界：HopCone 不声称这些概念本身新颖。

GPSR：根据位置选择下一跳

• 优先转发给更接近目的地的邻居
• 没有更近的邻居时，进入恢复过程
• 三维飞行场景需要重新检验恢复条件

gpsr · MobiCom 2000

GPSR是MobiCom2000，不是SIGCOMM。这里的表格是教学合成数据，旨在分开geometry和connectivity。Greedy失败并不等于全图没有路径，后续会出现local minimum。

来源与阅读边界： - GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. MobiCom 2000. https://www.icir.org/bkarp/gpsr/gpsr.html 核验深度：原作者页面/论文。使用边界：不能把2D planar recovery直接套到3D。

DREAM：按距离与运动更新位置

• 节点运动会使位置记录逐渐失准
• 远近节点可以采用不同更新频率
• 更新策略需要兼顾误差与通信开销

dream · MobiCom 1998

不要把“所有节点传播位置”或“远端允许粗略信息”包装成全新思想。教师可让学生对照原文，识别概念继承与具体系统机制。新颖性需要逐项比较。

来源与阅读边界： - A Distance Routing Effect Algorithm for Mobility (DREAM). MobiCom 1998. https://www.comp.nus.edu.sg/~bleong/geographic/related/basagni98dream.pdf 核验深度：论文。使用边界：HopCone 不声称这些概念本身新颖。

信息年龄：记录距离现在有多久

$$\Delta(t)=t-u(t)$$

• $u(t)$：当前记录的生成时刻
• 接收时间相同，记录的新旧仍可能不同
• 排队也会增加信息年龄

aoi · INFOCOM 2012

本课采用简化AoI定义帮助分析。若relay重写时间戳，旧信息会伪装成新信息。AoI不是准确度，也不等于端到端数据包时延，这三个指标要分别记录。

来源与阅读边界： - Real-time status: How often should one update?. INFOCOM 2012. https://www.iiitd.edu.in/~skkaul/Papers/Infocom2012.pdf 核验深度：官方摘要或作者项目说明；未宣称全文精读。使用边界：及时更新需要同时考虑排队；吞吐量不能独立解释新鲜度。

更新越频繁，信息一定越新吗

• 更新过多可能增加排队
• 到达时已经过期的记录仍占用资源
• 同时测量生成频率、排队时延与信息年龄

aoi · INFOCOM 2012

Kaul等的INFOCOM 2012工作研究状态更新频率与信息年龄的关系。这里采用其研究问题，不复述具体排队模型的最优参数。课堂比较低频、适中频率和拥塞频率下的年龄曲线，强调增加发送频率的收益取决于服务能力。

来源与阅读边界： - Real-time status: How often should one update?. INFOCOM 2012. https://www.iiitd.edu.in/~skkaul/Papers/Infocom2012.pdf 核验深度：官方摘要或作者项目说明；未宣称全文精读。使用边界：及时更新需要同时考虑排队；吞吐量不能独立解释新鲜度。

位置记录过期会带来多大误差

$$e\approx v\Delta$$

速度为 $15\,\mathrm{m/s}$，信息年龄为 $2\,\mathrm{s}$：

位置偏差可达约 $30\,\mathrm{m}$。

这是匀速近似；转弯和定位误差需另行考虑。

这是由速度上界得到的粗略位移界，不是FANET经验定律。恒速预测后剩余误差取决于转弯、加速度和模型误差。没有已知速度界时不能把它用作保证。

逐跳重新查询目的位置

• 源节点先用本地记录确定转发方向
• 中继节点查询自己的目的位置记录
• 中继可能掌握更新记录，也可能没有

本表只展示一个有利事件序列。节点靠近目的地时不一定拥有更近期记录，例如断网、更新丢失或路径绕行。因此后续必须讨论counterflow的适用条件。

交互：目的位置记录有多旧

请学生切换固定坐标与逐跳记录模式，并增加一次更新中断。记录表用相同转发时刻计算年龄，显示逐跳再解析的机会和中断反例。此演示是确定性教学数据，不是网络仿真结果。

HopCone 的研究问题

在持续运动的网络中，利用沿途节点的本地位置记录，改善地理转发。

• 心跳传播位置更新
• 每一跳重新查询目的位置
• 结合链路判断与局部恢复

团队研究 · HopCone 当前源码与图表，2026-10-15 核对

明确in-band是复用已有控制消息承载位置记录，不等于零开销。位置表仍有存储与传播成本，也不保证网络分区时目的可达。避免把架构机会写成每跳必然变新。

内部来源：archive/paper-hopcone/submissions/infocom2027/main.tex、last-plot-data.json 与 figures/。本轮未独立重跑路由仿真，不将稿件结果扩大为普适性能结论。

HopCone：位置更新沿网络传播

HopCone稿件中的移动拓扑示意

团队原图 · HopCone 当前源码与图表，2026-10-15 核对

指出图中的几何关系是用于解释counterflow，不能单凭图上的距离断言链路一定存在。要求学生分别指出记录传播方向和数据转发方向。

内部来源：archive/paper-hopcone/submissions/infocom2027/main.tex、last-plot-data.json 与 figures/。本轮未独立重跑路由仿真，不将稿件结果扩大为普适性能结论。

逆向信息传播的机会

• 目的节点的信息可能从前方传来
• 中继因此可能获得较新的位置记录
• 传播方向和时序决定收益，不能预设逐跳变新

本页是对机制条件的分析。counterflow提供设计动机，不是单调新鲜度定理。让学生把W2乱序例子加入多跳传播，寻找更近却更旧的节点。

为位置记录保留必要的历史

• 来源与序号：识别重复记录
• 生成时间：比较记录新旧
• 历史窗口：支持预测与链路判断

根据当前main.tex的协议描述，两种窗口服务不同预测目标。本机刚收到的精确记录可能还没有发给下游，若用同一窗口进行抑制，可能错误高估下游已经知道的状态。

预测误差触发位置更新

• 先根据已有状态预测当前位置
• 误差超过阈值时发送更新
• 阈值决定误差水平与发送频率

eta是配置阈值，不意味着全体节点误差都不超过eta。传播丢失、等待和预测不一致都会影响接收端。当前源码的等间隔预测需要注意实际筛选和丢包后时间间隔的差异。

选择哪些节点继续转发

• 判断更新是否已经传播到邻域
• 优先保留能够扩大覆盖的转发
• 同时检查重复包、失效记录与转发开销

用集合覆盖的直觉解释，不要求学生求精确最小集合。当前稿件使用greedy近似。被选为位置传播relay不意味着每个数据包都应该经它转发。

单帧容量与网络总开销

• 单帧上限约束一次能装多少记录
• 总开销还取决于发送次数与中继次数
• 应同时记录字节数、重传与信道占用时间

这一边界对解释bounded serialization非常关键。短帧可能改善竞争或减少一次碰撞损失，但附加帧头也可能增加。不能将每帧上限误当成每轮或每秒全网控制流量上限。

稿件数据：心跳携带的位置记录数量

HopCone 心跳消息记录数量的稿件曲线

内部研究证据 · HopCone 当前源码与图表，2026-10-15 核对

让学生先读横纵轴和消融设置，再讨论曲线能支持什么。该图支持特定设置下记录量分布的比较，不能单独证明总空口开销或任务性能。原始重复运行日志未在本轮独立复核。

内部来源：archive/paper-hopcone/submissions/infocom2027/main.tex、last-plot-data.json 与 figures/。本轮未独立重跑路由仿真，不将稿件结果扩大为普适性能结论。

链路资格与滞回机制

• 根据近期证据判断邻居是否可用
• 建立与撤销连接采用不同阈值
• 减少临界状态下的反复切换

延续W3的链路波动。阈值和timeout存在权衡：太保守会错失可用链路，太宽松会保留失效邻居。让学生设计一个短时衰落与真实离开的对照。

地理转发遇到局部极小值

• 当前节点找不到更接近目的地的邻居
• 位置误差、遮挡或拓扑空洞均可能导致失败
• 恢复过程需要记录尝试过的路径

gpsr · MobiCom 2000

区分目的坐标错误、几何局部极小值与网络分区。它们可能表现为相同的“没有下一跳”，但需要不同诊断。二维图中的保证不能直接外推到三维动态有向图。

来源与阅读边界： - GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. MobiCom 2000. https://www.icir.org/bkarp/gpsr/gpsr.html 核验深度：原作者页面/论文。使用边界：不能把2D planar recovery直接套到3D。

将恢复状态限制在当前数据包内

• 为当前包记录绕行与尝试信息
• 设置跳数和尝试次数上限
• 避免旧恢复状态长期影响后续数据包

解释packet-local与持久全局恢复结构的区别。这里不宣称任意动态图上保证投递。课程项目应记录恢复次数、回退和最终失败原因，而不是只看成功率。

HopCone：转发与异步状态更新

HopCone稿件中的位置传播与逐跳转发

团队原图 · HopCone 当前源码与图表，2026-10-15 核对

按图逐步指出断链造成的版本差异。数据包经过的时间可能远短于心跳消息周期，因此不能把每次转发都理解成等待一轮状态更新。此图来自当前团队稿件。

内部来源：archive/paper-hopcone/submissions/infocom2027/main.tex、last-plot-data.json 与 figures/。本轮未独立重跑路由仿真，不将稿件结果扩大为普适性能结论。

团队测量：从链路观测校准模型

HopCone硬件与测量区域

内部研究证据 · HopCone 当前源码与图表，2026-10-15 核对

当前main.tex给出路径损耗指数2.202等参数。课堂重点是测量怎样限制仿真，而不是把这些参数当通用空中信道规律。完整测量原始日志和校准复核不属于本轮课件制作范围。

内部来源：archive/paper-hopcone/submissions/infocom2027/main.tex、last-plot-data.json 与 figures/。本轮未独立重跑路由仿真，不将稿件结果扩大为普适性能结论。

稿件数据：节点规模与投递率

HopCone可扩展性实验PDR曲线

内部研究证据 · HopCone 当前源码与图表，2026-10-15 核对

数字已与last-plot-data.json核对。旧plan称没有结果，但当前main.tex及plot-data已更新。不能将曲线扩大为“优于所有FANET算法”，也不表示本轮独立重跑了仿真。请学生寻找baseline位置服务和参数公平性问题。

内部来源：archive/paper-hopcone/submissions/infocom2027/main.tex、last-plot-data.json 与 figures/。本轮未独立重跑路由仿真，不将稿件结果扩大为普适性能结论。

FERMI：用观测校准无线传播预测

• 联合传播建模与自主数据采集
• 为候选链路提供环境相关的预测
• 仍需用实际投递、排队与干扰验证

fermi · RSS 2025

官方摘要支持混合传播模型与自主采样机制。不要复述未核验数值。与HopCone相比，它回答不同层面的问题：信号场的建模与采样，而不是目的位置的逐跳解析。

来源与阅读边界： - FERMI: Flexible Radio Mapping with a Hybrid Propagation Model and Scalable Autonomous Data Collection. RSS 2025. https://www.roboticsproceedings.org/rss21/p095.html 核验深度：官方摘要已核对；Link端PDF下载超时。使用边界：传播预测需要真实链路检验。

运动规划中的连通性

• RSS 2025：同时考虑信息采集与连通性
• RSS 2026：研究时间窗口内的网络重连
• 轨迹层面的连通性仍需经过数据包实验检验

connectivity · RSS 2025；timeconnect · RSS 2026

ergodic可用“访问区域的时间分配与信息需求相匹配”作直觉说明，不推导最优控制。边界是通信时延与packet-level结果仍需进一步核算。两篇研究不应和路由PDR在不同基准上直接比数字。

来源与阅读边界： - A Probabilistic Measure of Multi-Robot Connectivity and Ergodic Optimal Control. RSS 2025. https://www.roboticsproceedings.org/rss21/p100.html 核验深度：官方摘要已核对；Link端PDF下载超时。使用边界：trajectory 连通度不等于数据包传输成功。 - Time-Aggregated Connectivity Maintenance for Multi-Robot Networks. RSS 2026. https://www.roboticsproceedings.org/rss22/p043.html 核验深度：官方摘要已核对；Link端PDF下载超时。使用边界：CBF 保证受模型与可行性假设限制，不等于无线投递保证。

网络层向模型提供哪些信息

• 消息：来源、生成时间、接收时间
• 链路：方向、质量、有效期限
• 资源：可用预算、排队状态、预计代价

接口是课程建议而不是HopCone既有实现保证。不得让上层读取未来链路或真实目的坐标作为特征。学习与网络共同优化的第一步，是准确表达可用信息边界。

研究设想：让模型显式感知网络状态

网络现象	输入与结构	验证方法
消息过期	时间与不确定性	改变时延分布
链路不对称	有向候选集合	分别改变两个方向
信道拥塞	队列与剩余预算	逐渐增加负载

schednet · ICLR 2019 · aoi · INFOCOM 2012

网络状态进入模型不是增加字段就能产生收益。先以固定任务头为基线，逐项加入时间、方向与队列信息，保持实际发送预算相同。消融应区分模型输入收益和调度器直接拒绝超预算消息的收益。训练采用真实轨迹或明确的信道模型。

来源与阅读边界： - Learning to Schedule Communication in Multi-agent Reinforcement Learning. ICLR 2019. https://openreview.net/pdf?id=HUAnBToP_a 核验深度：官方摘要或作者项目说明；未宣称全文精读。使用边界：学习调度需另行接入真实无线队列与信道竞争。 - Real-time status: How often should one update?. INFOCOM 2012. https://www.iiitd.edu.in/~skkaul/Papers/Infocom2012.pdf 核验深度：官方摘要或作者项目说明；未宣称全文精读。使用边界：及时更新需要同时考虑排队；吞吐量不能独立解释新鲜度。

路由实验怎样保证可比

• 使用相同轨迹、业务负载与无线参数
• 同时报送投递率、时延与总通信开销
• 分别改变规模、运动速度与位置更新策略

强调oracle目的位置不该和真实分布式位置解析混在一起，而不计任何代价。相同seed的成对运行有利于减少场景差异；具体重复次数依据预算和方差选择。

课堂练习：设置更新阈值

速度为 $10\,\mathrm{m/s}$，允许位置误差为 $5\,\mathrm{m}$。

• 匀速近似下，记录最多可用多久？
• 转弯时，这个估计可能怎样失效？
• 你会补充哪项测量？

预期失败：一次关键更新丢失后持续平稳运动，后续innovation很小，接收端长时间得不到修补。学生需要解释其发送端预测历史和接收端状态差异。repair也要计入总预算。

将网络状态带入协作模型

• 路由决定消息能否到达
• 时间戳决定消息是否仍然适用
• 下一讲：让不同节点的信息能够比较与融合

让学生用自己的话区分测量年龄、数据包时延和预测误差。如果三者仍混淆，先回到手算页，不急于引入神经模型。