消息交给第一个遇见的人，为什么可能等得格外久？
论文名片｜Augustin Chaintreau、Pan Hui、Jon Crowcroft、Christophe Diot、Richard Gass、James Scott，Impact of Human Mobility on Opportunistic Forwarding Algorithms，IEEE Transactions on Mobile Computing，2007，6(6)：606–620。期刊正式版，2007 年 3 月 28 日在线发表，6 月刊出。DOI。
设想一条消息暂时接不上互联网。你的设备把消息传给迎面遇见的人，对方带着消息走，直到碰到收件人才交付。这种存储、携带、转发的方式，把人的移动变成了通信网络的一部分。问题是：见过一次的人，多久以后才会再见？
如果等候时间大多围绕一个温和的平均值波动，随缘找人接力或许够用；如果少数等待特别漫长，平均延迟就可能被长尾支配。这篇论文用八组接触记录指出，常见移动模型对漫长等待的估计可能过于乐观，再用更新过程模型解释这种差异怎样改变转发算法的保证。
先把四点发现放在前面：
- 在约 10 分钟至 1 天的范围，八组数据中的接触间隔尾部都下降缓慢，幂律可作近似或下界；这不等于完整时间范围都遵循同一幂律。
- 同一对设备两次接触之间的间隔，与消息在任意时刻到来后还要等多久，是两种分布。后者更容易落进长间隔。
- 在独立、同分布、无截断幂律的模型中，单副本两跳转发需要比“平均接触间隔有限”更强的条件，才能保证有限平均延迟。
- 多副本可以扩大模型中的可行区域，却无法自动消除所有重尾问题。真实网络是否如此，还取决于长时间截断、群体差异和接触相关性。
八组记录，测到的是同一种相遇吗？
论文测量的是接触间隔时间（intercontact time）：对固定的一对设备，从一次接触结束，到下次接触开始的等待。它不是一次接触持续多久，也不是某人离开一个人后多久碰到任何另一个人。
表 1 的实验概况有必要放在一起看，因为不同采集方式会改变我们对相遇的理解。
| 数据集 | 设备数 | 观测时长 | 扫描粒度 | 设备间接触的判断 |
|---|---|---|---|---|
| Cambridge | 12 | 3 天 | 120 秒 | iMote 蓝牙直接发现 |
| Hong Kong | 37 | 5 天 | 120 秒 | iMote 蓝牙直接发现 |
| INFOCOM | 41 | 4 天 | 120 秒 | iMote 蓝牙直接发现 |
| Toronto | 23 | 16 天 | 120 秒 | PDA 蓝牙直接发现 |
| UCSD | 273 | 77 天 | 120 秒 | 共享可见 Wi-Fi 接入点 |
| Dartmouth | 6,648 | 114 天 | 300 秒 | 共享 Wi-Fi 接入点 |
| MIT BT | 100 | 246 天 | 300 秒 | 手机蓝牙直接发现 |
| MIT GSM | 100 | 246 天 | 10 秒 | 共享 GSM 基站 |
这是原论文表 1 的具体记录长度；正文用数月概述部分实验。MIT 的两列来自同一项目的不同无线记录，不能加起来理解成 200 个互不重复的人。
前三组是作者参与开展的 iMote 实验。Cambridge 来自同一研究群体，Hong Kong 特意选择不属于同一工作或社交圈、彼此不认识的人，INFOCOM 来自会议参会者。扫描发现另一台实验 iMote 称为内部接触，发现其他蓝牙设备称为外部接触。外部设备数量也不同：Cambridge 记录 148 台、Hong Kong 1,840 台、INFOCOM 197 台。
共享接入点或基站只是潜在通信机会的代理。两个设备连着同一基站，未必在彼此的直连范围；没有接入点的地方也可能发生未记录的相遇。设备还可能被留在桌上。因此，八组数据的共同模式有价值，但不能把它们当作精度相同的面对面社交记录。
每对至少相遇两次的设备先各自生成间隔分布，再给不同设备对相同权重，合成聚合分布。这避免接触频繁的设备对仅凭记录数占据全部权重，也意味着图中的概率不是把所有人的全部间隔直接混在一起数出来的比例。
相遇很多次，也掩不住少数漫长等待
图 1｜固定两台设备，再次相遇需要等多久？
（a）Cambridge 内部接触、Hong Kong 外部接触和 Toronto 的聚合互补累积分布。横轴是等待时间，纵轴是间隔超过该时间的概率，双轴均取对数；细直线是尾指数 0.6 的幂律参照。
（b）INFOCOM 内部与外部接触。两条曲线在主要范围内接近，参照幂律尾指数为 0.35；一天附近之后出现明显偏离。
（c）UCSD、Dartmouth、MIT BT 和 MIT GSM。参照线尾指数为 0.2，不同技术对应的曲线高度和远端形状差异明显。来源：原论文 Fig. 1。
这里的互补累积分布（CCDF）回答“等候超过 t 的概率还有多少”。双对数图上缓慢下降的曲线意味着长等待不容易消失。作者在三组 iMote 实验中报告，约 17%–30% 的间隔超过一小时，约 3%–7% 超过一天；Toronto 中约 14% 超过一天、8% 超过一周；MIT 蓝牙记录中超过一天的间隔可达 60%。这些是不同数据集的统计，不能合成一种通用的人类相遇概率。
最可比较的区域是 10 分钟至 1 天。原文的谨慎说法是：这一范围的尾部可被幂律下界约束，在部分数据中幂律也是较好的近似。0.6、0.35、0.2 是图中参照下界的指数，不应写成八组数据分别得到的精确共同参数。
实验的两端都有观测限制：短于扫描周期的离开再返回可能漏掉，长于观测期的间隔无法完整看到；论文还排除了实验开始至首次接触、最后一次接触至实验结束的未闭合区间。因此，超长间隔的尾部不能仅凭这些有限记录定型。
幂律只是聚合造成的吗？
一个平均图形可能由许多不同的个体规律混合而成。论文因此同时做分布对照和逐设备对估计。
图 2｜幂律近似有多好，不同设备对有多大差异？
（a）INFOCOM 内部接触的分位数对照图。横轴为参数模型的分位数，纵轴为观测分位数，接近对角线表示对应分位数相近。指数、对数正态和幂律模型都匹配观测中位数，幂律在约 18 小时以内更贴近观测，一天以后也明显偏离。
（b）INFOCOM 的逐设备对尾指数估计，共 1,438 对，横轴为按中位数估计排序后的相对名次。实线来自中位数估计，竖区间是用目标时间范围内次序统计量得到的启发式上下界；为可读性仅绘部分竖区间。
（c）不同数据集的三种估计汇总。各组由左到右为下界估计、中位数估计、上界估计；粗部覆盖中间 50% 的设备对，细线覆盖中间 90%。这不是参数估计的置信区间。来源：原论文 Fig. 2。
在图 2a 的特定比较中，幂律优于所测试的指数与对数正态近似。但这并不是包含全部候选分布的严格模型选择，也没有证明幂律来自某个唯一的移动机制。作者明确把一天以上的额外参数模型留作后续工作。
图 2b 的中位数估计，对一半 INFOCOM 设备对落在 0.2–0.4。几乎所有上界估计低于 1，但仍有三对例外。Hong Kong 的记录更稀疏，上界估计在约 10% 的设备对中略高于 1。这既提醒我们关注群体差异，也提醒我们：有限样本下的启发式界限不是精确参数。
下一步理论把这些差异大幅简化，假设所有设备对共享同一个尾指数。经验分析为关注重尾提供理由，却没有验证这种同质化假设。
没看见明显自相关，就能把相遇当作独立吗？
图 3｜一段等待能否预测后面的等待？
（a）INFOCOM 各设备对间隔对数值的自相关，横轴为滞后阶数 k，纵轴为相关系数。设备对之间分散很大，平均值略偏负；粗箱和细线分别给出中间 50% 与 90% 的设备对范围。
（b）MIT GSM 的相同计算，结果更集中于零附近。两图均计算至滞后 50 阶。来源：原论文 Fig. 3。
这里先取间隔的对数，是为了减轻重尾和潜在无限方差对普通相关分析的影响。接近零的相关系数可以支持简化分析，却不能证明独立；图 3 检查的还是同一对设备的前后间隔，并未验证不同设备对之间独立。共处办公室、共同上下班等现实结构，正可能产生跨设备对的关联。
理论部分明确假设：同一设备对的间隔独立同分布，不同设备对的接触过程也独立，所有设备对同质。模型直接描述接触过程，不模拟地理位置与运动轨迹。
为什么平均相遇间隔有限，消息还可能等到均值失控？
论文假设离散时间中的间隔 X 满足 P(X ≥ t) = t 的负 α 次方，且没有上限。α 是尾指数，越小意味着长等待越常见。这个无截断假设将有限观测范围中的现象扩展为数学对象，是后面“无界”的前提。
真正到来的一条消息关心的是剩余接触间隔（remaining intercontact time）：从消息出现时刻到下一次相遇还要等多久。长间隔占据更多时间，随机到来的消息也更容易落进其中，这就是等待时间悖论。
当 α > 1，完整间隔的均值有限，模型能达到平稳状态；剩余等待的尾指数却变成 α − 1。若要剩余等待的均值也有限，还需要 α > 2，即完整间隔有有限二阶矩。论文用更新过程与 Smith 公式把这个关系写清：剩余等待的均值由二阶矩与一阶矩的比值控制，而非只由平均相遇频率控制。
论文比较的两跳转发，把消息交给首先遇见的设备；若对方不是目的设备，就由这个中继保存消息，直到直接遇见目的设备。中继不能再任意接力，因此一个运气不好的中继足以拖长最终等待。
定理 1 给出：α < 2 时，这种策略不能在长期运行中收敛到有限平均延迟；α > 2 时，在长接触条件下可以。短接触每次只能传一个数据单元，还必须限制生成流量、保证队列稳定；论文构造的方案可在每个源发送给唯一且不同的目的设备、速率低于 (N − 1)/(2E[X]) 的条件下取得有限平均延迟。时间单位是模型时隙，这不是现实网络的 Mbps 吞吐量保证。
这里的长接触指一次机会足以清空两台设备的队列，短接触指每次只能传一个单元，二者是通信能力的理想上下界。长接触也会失败的情形，说明问题不一定来自缓存堵塞；等待下一次遇见本身就足够困难。定理按 α < 2 与 α > 2 陈述，不能擅自把边界 α = 2 加进已给出的结论。
多发几份副本，能把长尾救回来吗？
复制让消息同时拥有多个见到目的设备的机会，但效果取决于模型所处区域。
| 模型尾指数 | 论文给出的延迟保证 | 需要保留的条件 |
|---|---|---|
| α > 2 | 单副本两跳可取得有限平均延迟 | 短接触另需流量及队列条件 |
| 1 < α < 2 | 选足够多的中继，可取得有限平均延迟 | 长接触、平稳、设备对独立；存在性构造要求 α > 1 + 1/m，且 N ≥ 2m |
| α ≤ 1 | 有限设备网络中，即便洪泛也无法取得长期有限平均延迟 | 无截断幂律和论文的更新过程假设 |
m 是参与接力的中继数，N 是网络设备数。多个独立等待取最小值，尾部下降更快：对应条件为 m(α − 1) > 1。需要足够设备数，是因为消息也得先把副本交到这些不同中继手里，不能只计算后半程。
“没有有限平均延迟”不表示每条消息都永远送不到，更不表示所有消息都很慢。它表示理想模型中，极少数过长等待足以使长期均值不受有限常数控制。定理 2 对 α ≤ 1 的结果在这个模型中甚至涵盖洪泛；它没有证明真实有日程、关系结构和基础设施的所有机会网络都无解。
实验常见 α < 1，而模型的坏消息又发生在这一侧，作者由此强调应警惕一天量级的等待。这个量级判断是从有限范围的重尾现象与理想理论联系得到的解释，不是八组数据中所有转发算法实际延迟都至少一天的实测下界。论文没有做一组现实转发算法的部署性能排名。
这项研究留下了什么判断方法？
评价机会网络时，只报告平均相遇频率不够。还需检查同一对设备的间隔尾部、消息到达时看到的剩余等待，以及复制和队列资源之间的取舍。用轻尾的随机移动模型得到的延迟保证，可能依赖真实数据不具备的二阶矩条件。
附录 A 给出更新过程、剩余等待和平稳性结论，附录 B 通过服务时刻队列、广义 Little 关系和随机游走条件处理队列期望，附录 C 构造短接触转发与多中继次序统计量的证明。它们巩固的是在明确假设下的数学保证，并未补上现实跨设备相关性、异质性、无线干扰和有限缓存的实测验证。
作者提出的出路也很具体：应用应能承受偶发长延迟；转发可以利用设备身份、历史相遇与社会结构；还可以加入特殊设备或部分基础设施，创造新的接触机会。这些方向值得研究，但本文尚未证明哪种方案在现实中一定最优。
一句话总结
消息交给第一个遇见的人，能否可靠地等到收件人，取决于等待分布的长尾和消息到来时看到的剩余时间；有限范围的重尾观测值得警惕，却必须与无截断理想模型的延迟定理分开理解。
核心来源
- 期刊原文与 DOI：数据表 1、图 1–3、定理 1–2、结论和附录 A–C。本文三张图均来自原论文对应完整图。
- 香港科技大学研究门户书目记录：核对期刊、卷期、页码与发表年份。
作者介绍
以下身份均按论文首页及文末作者简介的发表时期信息。
- Augustin Chaintreau：Thomson Research，研究机会网络、无线网络与覆盖网络的算法设计和分析。
- Pan Hui：剑桥大学计算机实验室系统研究组博士生，参与人携设备的机会通信研究。
- Jon Crowcroft：剑桥大学计算机实验室网络系统教授，研究网络系统与通信。
- Christophe Diot：Thomson Research 巴黎研究实验室，论文简介关注通信服务与平台。
- Richard Gass：Intel Research 匹兹堡研究工程师，研究机会通信、无线网络和车载自组网。
- James Scott：微软剑桥研究院研究人员，研究移动网络与普适计算。
延伸思考：比平均延迟更适合用户的承诺是什么？
以下是 AI 基于论文结果所作的延伸，不属于原论文结论。
如果用户只关心今晚之前能否收到消息，长期平均延迟就不够贴近问题。可以同时报告在 10 分钟、一小时、一天内送达的比例，以及为达到这些目标消耗的副本数、能量和缓存。这样即使分布有很长的尾巴，用户仍能理解某个期限内的服务可靠程度。
另一个实验可以把同一组真实接触记录分成两类仿真：保留完整时序，或打乱设备身份和时间关联但尽量保持间隔分布。如果两者期限送达率不同，就能检验只保留单对间隔分布是否丢掉了有用结构。长尾给出困难的轮廓，关系与日程可能决定哪些中继能真正绕开困难。
