2011-STEPS - An Approach for Human Mobility Modeling


围着一个偏好地点打转,能不能同时靠近会议里的相遇和消息扩散?

论文名片|Anh Dung Nguyen、Patrick Sénac、Victor Ramiro、Michel Diaz,STEPS - An Approach for Human Mobility Modeling,J. Domingo-Pascual 等编,NETWORKING 2011, Part I,Lecture Notes in Computer Science 第 6640 卷,第 254–265 页,Springer,2011。DOI:10.1007/978-3-642-20757-0_20。STEPS 是 Spatio-TEmporal Parametric Stepping 的缩写,指时空参数步进。这是一个带解析讨论的人类移动模型,并用一场会议的蓝牙接触记录做模拟对照。

Infocom 2006 的记录有 98 个节点,持续 4 天,设备用蓝牙发现附近的人。表 1 给出的平均再次相遇间隔是 1.9 小时,平均一次接触是 6 分钟。同一会场里,可以既有几乎留在同一处的节点,也有在房间之间走动的节点。STEPS 用同一条规则覆盖这两类:每个节点有一个偏好地,离它越远越不容易被选中,这个程度由一个指数调节。调节之后,模拟的再次相遇间隔、接触时长,以及消息传到不同人数时的时延,再和这场记录的汇总曲线比较。

在作者配置的这场对照里,再次相遇间隔和接触时长的互补累积可以看起来接近这 98 个节点、4 天的记录;消息扩散时延的主体走势同向上升,右端两条线分开。小世界出现在模型自己的两类节点混合里,混合比例没有标出。人走多远、停多久,在这个模型里是事先写入的幂律。

先说结论

  • 选中距离 d 的概率是 P(D = d) = β / (1+d)^α,停留时间的概率是 P(T = t) = ω / t^τ。α 是吸引强度,τ 是时间偏好程度,β 和 ω 是归一化常数。α 大于 0 时节点更定域,等于 0 时正文称为对各区域均匀,小于 0 时偏好地变成排斥中心。实验图只比较等于 0 和大于 0,大于 0 的具体数值没有给出。
  • 马尔可夫链模拟中,α 等于 0 时,再次相遇间隔的互补累积在线性–对数坐标上被读成接近指数;α 大于 0 时,对数–对数坐标上被读成幂律,尾部再加快下降。这张图没有叠真实轨迹。
  • 和 Infocom 2006 对照的场地是 10×10 环面、120×120 平方米,无线电范围 10 米。作者认为再次相遇间隔和接触时长的互补累积与这条轨迹吻合,文中没有曲线距离或误差条。接触时长实验把 98 个节点设为 65、15、10、8 四组,对应四段区内暂停时间。这四组人数是模拟设置。
  • 传染式转发的平均时延随已收到消息的人数上升。STEPS 与 Infocom06 在中段一起上升,靠近右端时会议轨迹翘得更陡。另一组模拟里,归一化聚类系数和归一化最短时间距离都从靠近 1 降到靠近 0。论文说某个混合比例上会出现小世界,图上没有标出这个比例,也没有在会议记录上测量小世界。

均匀乱走,为什么留不下常去的地方?

移动自组网(mobile ad hoc network,MANET)和容迟网络(delay-tolerant network,DTN)里,早期常用随机路点、随机游走。下一步的参数多从均匀分布抽取,场地里没有常去之处,时间上也没有夜里更可能待在某一处的结构。Yoon 等人指出,这种均匀假设会把后续研究带离真实移动。

测量给出的是另一类汇总形状。González 等人和 Brockmann 等人报告,出行距离呈幂律。Chaintreau 等人讨论再次相遇间隔的幂律。Karagiannis 等人补充说,这条幂律大约维持到 12 小时,之后转为指数下降。约 12 小时来自他们引用的既有研究,本文没有在自己的图上拟合出一个截断时刻。

已有模型各自盖住一部分。工作日模型参数很多。SLAW 用幂律规定步长和停留,并让路径像在选近路;本文作者认为它没有表达对地点的时空偏好,也没有把路由性能和真实轨迹对照。社区模型让节点走向朋友更多的区域,接触时长与轨迹有差别,路由对照同样没有给出。时变社区模型用不同社区的跳跃概率表示空间偏好,用昼夜和星期表示时间偏好。后续比较指出,时空特征能对上的模型,路由时延仍可能明显偏离真实轨迹。

STEPS 把地点偏好收成少数参数,并要求模拟在转发时延上接受真实轨迹的检验。它使用的偏好依附(preferential attachment)只相对节点自己的偏好地计算:离这一个地点越远,越不容易被选中。连边数量不进入这个概率。

离偏好地越远,被选中的机会怎样下降?

场地是方形环面(torus),分成 N×N 个方格。上下边界相接,左右边界相接。两格距离用切比雪夫距离(Chebyshev distance):横向步数和纵向步数取较大值。每个节点有一个偏好区 Z₀。本文每人只绑一个偏好区。作者写明可以扩展成多个偏好区,也可以把区域理解成话题之类的逻辑位置;实验只做地理区域。群体移动写的是实现中支持,报告的实验没有使用。

下一次行走的距离服从

P(D = d) = β / (1+d)^α。

d 是离 Z₀ 的距离。分母用 1+d,是为了 d 为 0 时仍有定义。正文用“与距离成反比”描述直觉;真正进入计算的是 (1+d) 的 α 次方,α 不必等于 1。距离抽定后,在所有与 Z₀ 相距恰好这么远的区域中均匀抽一个,再在区内抽一个点,沿直线走去。速度抽自区间 [v_min, v_max],两个端点的数值没有给出。

在区域内的停留时间服从

P(T = t) = ω / t^τ。

停留期间,节点在当前区域内做随机路点(Random Waypoint)。因此模型里有两层时间:τ 控制在这个区域待多久;后文对照接触时长时,作者改用区域内随机路点自己的暂停时间。两层时间对应两次不同的设置。

α 分三段。大于 0 时近处权重大,偏好区是吸引中心。小于 0 时远处权重大,偏好区变成排斥中心;这一支只出现在定义里,后面的图没有使用。等于 0 时,(1+d) 的 0 次方等于 1,每个距离值的权重相同。正文同时写,此时节点以均匀概率走向任意区域。把 α 等于 0 代入单个区域的公式,得到 β/(8d):同一距离上有 8d 个区域,所以单个区域的概率仍随 d 下降。按距离值均分,和按每个区域均分,是两种概率。图 2 把 α 等于 0 用作再次相遇间隔接近指数的一档,没有给出当时的区域概率表。

距离 d 至少为 1 时,与偏好区相距 d 的区域有 8d 个。其中某一个被抽中的概率是

β / (8d (1+d)^α)。

图 1(b)的 5×5 环面可以数清:距离 1 有 8 格,距离 2 有 16 格,分别等于 8×1 和 8×2。加上偏好区本身,8+16+1 = 25,铺满整个 5×5。

完整原论文图1,含四个地点状态和5乘5距离网格

图 1|偏好地和距离,怎样变成一张可走的图?

(a)四个状态标为 A、B、C、D。图注举例为住宅、办公室、商店和其他地方,圆圈里只印了字母。箭头表示转移,每个状态还有回到自身的箭头,表示可以留在原地。
(b)5×5 环面。A 是偏好区,其余数字是到 A 的切比雪夫距离。A 位于中间一行的第二列。边界绕回之后,最远距离仍是 2;距离 1 有 8 格,距离 2 有 16 格。
来源:原论文 Fig. 1。

这张图只说明状态和距离如何编号。它没有人数、时间和与轨迹的误差。

吸引强度会把再次相遇从指数改成幂律吗?

区域之间的跳跃写成离散时间马尔可夫链(Markov chain),一个状态对应一个区域。下一步只依赖离自己偏好区的距离,不依赖现在站在哪一格,所以转移矩阵每一行都相同,平稳时各区域的概率就是这一行。人当前在商店还是在办公室,下一跳的概率表相同。模型因此可以直接写出平稳分布,同时没有沿当前方向继续走的惯性。

这一节把接触定义成两个人位于同一区域。若移动相互独立,某一时刻同区的概率等于各区域上两人概率的乘积之和。文中再把它写成同一组区域概率的平方和,并按距离环从 i = 0 加到 d_Max。平方和对应的是两人具有同一组区域概率。两人偏好区不同时,乘积和不会自动变成这个平方和。印刷的求和在 i = 0 处还要除以 8i;中心只有偏好区那一格,8d 数的是 d 至少为 1 的环。文中没有算出一个数值概率。

d_Max 印为 √N / 2 的向下取整。在这一节,N 是状态数,也就是区域个数。前面说场地分成 N×N 个区时,同一个字母 N 又被用作边长。若 10×10 共 100 个区域,并且公式中的 N 取 100,则 d_Max = ⌊√100 / 2⌋ = 5,等于该环面上切比雪夫距离的最大值。论文没有把 5 代回接触概率。

同区概率记为 p_contact。再次相遇间隔(inter-contact time)在解析里是离散时刻:第 t 个时刻才再次同区的概率为 (1 − p_contact)^(t−1) 乘以 p_contact,也就是成功概率为 p_contact 的几何分布。它的连续对应物是指数分布。作者写明,这只适合 α 等于 0、吸引还没有在节点之间造成相关的情形。α 不等于 0 时,他们预期相关会带来幂律,并说明一般闭合公式仍是进行中的工作。图 2 用这条链的模拟来看形状差别。

完整原论文图2,比较吸引强度为0和大于0时的再次相遇间隔

图 2|吸引强度为 0 和大于 0 时,再次相遇间隔的尾巴一样吗?

(a)α = 0。主图横轴 t 从 10^0 到 10^4,纵轴是互补累积 P(x>t),从 10^0 到 10^−2,两轴都取对数。曲线在左侧靠近 1,靠近 10^4 才下降。内图横轴改为线性,刻度到 7000,纵轴仍取对数。正文把线性–对数图上的直线读成指数分布。
(b)α 大于 0,数值未给出。主图纵轴延伸到 10^−4,横轴同样到 10^4。对数–对数坐标上曲线跨多个数量级下降,右端掉得更快。内图横轴线性,刻度到 3500。正文把主图的直线段读成幂律,把尾部读成指数截断。
来源:原论文 Fig. 2。

图 2 的横轴没有标注秒或步,也没有误差带。它比较的是两种 α 下的模拟形状。

98 个节点、4 天的会议记录,对上了哪些曲线?

再次相遇间隔是同一对节点前后两次相遇之间的时间。接触时长(contact time)是一次相遇持续多久。互补累积画的是 P(x>t),也就是时长超过 t 的比例。作者先用 Chaintreau 等人整理的一组轨迹显示这个形状,再把 STEPS 配到其中的 Infocom 2006。

表 1 只汇总这一条轨迹。

项目 数值
节点数 98
时长 4 天
技术 蓝牙
平均再次相遇间隔 1.9 小时
平均接触时长 6 分钟

1.9 小时和 6 分钟的分母是轨迹中的接触样本。论文没有给出接触次数或节点对数目,得不出每人每天相遇几次。

模拟场地是 10×10 环面,边长 120 米,用来模仿会场房间。120 米分成 10 格,每格边长 12 米。无线电范围设为 10 米。解析部分的接触是“同一区域”,这里的接触是“10 米以内”。一格 12 米,同区的两个人可以远于 10 米,相邻区域里的人也可以近于 10 米。

图 3(a)并列四条轨迹。图 3(b)只叠 STEPS 和 Infocom06。Intel、Cambridge 和 Infocom05 的节点数,本文没有另给。

完整原论文图3,真实轨迹与STEPS的再次相遇间隔互补累积

图 3|真实轨迹的再次相遇间隔长什么样,STEPS 跟的是哪一条?

(a)汇总互补累积,图例为 Intel、Cambridge、Infocom06、Infocom05。主图横轴 t 从 10^0 到 10^6,纵轴 P(x>t) 从 10^0 到 10^−6。四条线都从左侧靠近 1 向右下降,彼此分开。内图横轴线性,标到 3.5×10^5,纵轴取 10^0、10^−2、10^−4 和 10^−6。坐标没有写时间单位。4 天等于 345600 秒;若 t 以秒计,内图上界与轨迹时长同量级。
(b)蓝圈为 STEPS,绿线为 Infocom06。主图横轴从 10^2 到 10^6,纵轴同样到 10^−6。两条线在对数坐标上一起下降。内图横轴也标到 3.5×10^5。作者据此认为模拟与 Infocom06 吻合。图上没有误差条,正文没有给出两线距离。
来源:原论文 Fig. 3。

配出图 3(b)时使用的 α、τ 和速度范围没有列出。

接触时长还要处理人与人的差别:有的接触很长,有的只是短暂照面。作者按平均接触时长把 Infocom06 的节点排序,同时画归一化接触时长和受欢迎程度。这里的受欢迎程度是邻居节点总数,是整段轨迹上的汇总量。

图 4(a)里,接触时长那条线随排名上升,所以横轴左侧对应更短的接触,右侧对应更长的接触。邻居数那条线在 0 到 1 之间剧烈跳动,没有一条平滑的上升或下降。作者从这个排序读出:越受欢迎的节点,每次接触越短。文中没有相关系数。横轴画到 100,节点数是 98。

STEPS 的接触时长主要由区域内随机路点的暂停时间决定。作者把 98 个节点分成四组,给每组一段暂停,用来制造大量短接触和少数很长的接触。

活动性 区内随机路点暂停时间(秒) 节点数
很高 [0, 60] 65
高 [60, 900] 15
低 [900, 3600] 10
很低 [3600, 43200] 8

四组人数之和为 65+15+10+8 = 98,与表 1 的节点数相同。60 秒等于 1 分钟,900 秒等于 15 分钟,3600 秒等于 1 小时,43200 秒等于 12 小时。这里的 12 小时是最低活动组暂停区间的上界。前面引用的“幂律大约到 12 小时”来自另一篇文献。四组人数在模拟前设定,区间在 60、900 和 3600 秒处相接,论文没有说明端点归入哪一组。

完整原论文图4,接触时长、受欢迎程度以及与轨迹的互补累积对照

图 4|接触时长和受欢迎程度放在一起时,模拟跟得上轨迹吗?

(a)横轴是按平均接触时长排序的节点,刻度 0 到 100;纵轴是归一化值,0 到 1。蓝圈为接触时长,左低右高,右端靠近 1。绿方为邻居数,在纵轴的大部分范围内来回跳动。作者把该图读成受欢迎程度越高、单次接触越短。图中没有拟合直线或相关系数。
(b)接触时长的互补累积。蓝圈为 STEPS,绿线为 Infocom06。主图横轴 t 从 10^0 到 10^5,纵轴从 10^0 到 10^−6。两条线一起下降,蓝线多处略高于绿线。内图横轴线性,标到 4.5×10^4。作者认为这组暂停能以高准确度跟上轨迹。正文没有给出误差。
来源:原论文 Fig. 4。

图 4(b)的接近依赖这四组暂停。它不表示公式里的 τ 已经由数据估计出来。

汇总曲线接近之后,消息传到更多人要多久?

只复现相遇间隔的形状,放到转发上仍可能得到另一套时间。作者在 STEPS 和 Infocom06 两种移动输入上比较同一种传染式转发(epidemic routing)的平均时延:消息已经传到若干个节点时,用了多少秒。比较的目的是看移动模型会不会把时延带离这条轨迹。

完整原论文图5,STEPS与Infocom06的转发时延

图 5|消息传到不同人数时,模拟时延还跟着会议轨迹走吗?

单幅图。横轴是已经收到消息的节点数,刻度 0 到 100;轨迹有 98 个节点。纵轴是时延,单位秒,对数坐标,从 10^0 到 10^5。蓝圈为 Infocom06,绿方为 STEPS。两条线都随横轴上升。中段绿线位于蓝线之上;靠近右端时蓝线翘起,绿线仍较平。正文说 STEPS 反映出真实轨迹上的转发性能。图中没有逐点秒数,右端两条线分开。
来源:原论文 Fig. 5。

中段的共同上升说明时延的走向可以放在同一张图上对照。右端两条线分开,传到最后一批节点的时间留有差距。论文没有报告这个差距是多少秒,也没有做统计检验。

加入走得更远的节点之后,动态图会变成小世界吗?

静态图里的小世界(small-world)指聚类高、最短路径短。作者把这两个量改到边会随时间变化的图上,并写明因篇幅只保留主要定义。

在时间窗 w 内,节点 i 的时序聚类系数是邻居之间实际出现的连接,除以这些邻居两两之间可能的连接。正式式子中,分子是各邻居 j 与 i 的邻居集交集大小之和的 2 倍,分母是邻居数乘以邻居数减 1。时间窗的长度没有数值。

i 与 j 的最短路径沿用了这个名字,量出来的是最早连通时刻:从计时起点起,两人第一次直接相遇,或经由不同时刻的一串接触而连通。单位是时间。图 6 使用这个时刻和聚类系数归一化后的值,归一化基准没有写成公式。

实验在 STEPS 内部放两类节点。一类 α 较小,走得远;一类 α 较大,更定域。两类 α 和节点总数都没有给出。横轴是高移动节点数与高定域节点数之比,从 0 到 1。全体都很定域时聚类高;逐步加入走得远的节点后,看聚类是否仍高、时间距离是否已经变短。

完整原论文图6,高移动节点比例与归一化聚类、最短时间距离

图 6|高移动节点相对于高定域节点的比例变化时,聚类和时间距离怎样一起变?

单幅图。横轴和纵轴都从 0 到 1。图例第一条是归一化聚类系数,图中 clustering 印成了 clutering,画成蓝线;第二条是归一化最短路径长度,画成红线。左端两条线都靠近 1,右端都落到 0 附近,中间蓝线高于红线。正文说两个极端之间的某个比例上聚类高而最短路径低,因此提示动态图中存在小世界。图上没有标出这个比例,也没有未归一化的原始值。
来源:原论文 Fig. 6。

这是模型人口内部的模拟,没有使用 Infocom06。两条线从左到右一起下降。作者的用词是提示存在。

这些结果能用到哪一步

在有限环面、每人一个偏好区的设定下,α 把均匀选择和定域选择分成了两类再次相遇间隔。在 120 米见方、10 米无线电、98 个节点和 4 天的会议蓝牙记录上,作者配置的模拟可以使再次相遇间隔和接触时长的互补累积看起来接近轨迹,转发时延的主体走势也可以放在同一张图里。

距离幂律和停留幂律是模型的输入。本文没有把它们拟合到手机或纸币那些更大尺度的测量上,也没有单独画出模拟步长相对真实步长的图。Infocom 对照中的 α、τ 和速度没有公布。解析接触是同区,模拟接触是 10 米。接触时长的接近还依赖 65、15、10、8 这四组暂停。图 2 至图 6 没有误差条或拟合优度。小世界实验的时间窗、两类 α 和混合比例没有数值。

120 米、4 天、蓝牙接触,是这篇文章的场景。这个尺度上的区域偏好,对应的是会场房间之间的移动。

一句话总结

一个偏好地加上可调的距离幂律,可以在 98 个节点、4 天、120 米见方的会议蓝牙记录上,把再次相遇间隔、接触时长和消息扩散时延的主体形状模拟到作者认为接近的程度;小世界只在模型自己的混合人口里被提示,混合比例没有给出。

核心来源

Nguyen, A. D., Sénac, P., Ramiro, V., & Diaz, M. (2011). STEPS - An Approach for Human Mobility Modeling. In J. Domingo-Pascual et al. (Eds.), NETWORKING 2011, Part I (Lecture Notes in Computer Science, Vol. 6640, pp. 254–265). Springer. https://doi.org/10.1007/978-3-642-20757-0_20

文中作为背景引用的距离幂律、再次相遇间隔、SLAW、社区模型、时变社区和小世界,只用来说明本文要补上的缺口。图 2 至图 6 的坐标范围、表 1 和两组人数以这篇会议论文为准。

作者介绍

  • Anh Dung Nguyen:论文署名为法国图卢兹 ISAE/图卢兹大学与 LAAS/CNRS,邮箱在 isae.fr。其个人主页写明,2009–2013 年在图卢兹大学攻读计算机博士,导师为 Patrick Sénac 与 Michel Diaz,工作涉及动态网络、机会网络和移动建模,并列出本文。
  • Patrick Sénac:论文署名为 ISAE/图卢兹大学与 LAAS/CNRS。Nguyen 的个人主页称他为博士阶段导师。
  • Victor Ramiro:论文署名为智利圣地亚哥 NIC Chile Research Labs。本文没有更细的职务说明。
  • Michel Diaz:论文署名为 LAAS/CNRS,邮箱在 laas.fr。Nguyen 的个人主页称他为另一位博士导师。ISTE 的作者介绍称他为 CNRS 研究主任,工作地点在图卢兹 LAAS。

延伸思考

以下是 AI 基于论文结果所作的延伸,不属于原论文结论。

120 米见方、10 米蓝牙和 4 天会议,对上的是设备接触的汇总分布。把同一个 α 拿去估计一座城市里从家到工作地的距离,中间还隔着区域大小、观测手段和时间长度。会场里的偏好区,和通勤模型里的居住地、就业地,分析单位不同。

图 5 把两种问法分开了。若问传到大约一半节点时两条时延是否同向上升,中段可以当作粗对照。若问传到几乎所有设备还要多久,右端蓝线已经翘起,论文没有给出这个差是多少秒。用“曲线大体相似”筛选转发方案时,最后那一批节点会先被平均掉。

接触时长能靠近轨迹,伴随的设置是 65 个节点(分母为表 1 的 98)落在 0 到 60 秒的暂停里,8 个节点可以暂停到 43200 秒。地点偏好相同、暂停习惯只有一种的人群,接触时长还会不会像图 4(b),本文没有这组对照。图 6 也没有给出可操作的混合比例,不能据此决定一场会议里安排多少人长时间在房间之间走动。

本文报告的是 98 个节点的汇总曲线和模拟。这些分布本身不提供还原某人房间序列的步骤。


文章作者: 猴猴猴
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 猴猴猴 !
  目录