Reducing Sensor Requirements by Relaxing the Network Metric Dimension

1研究问题

度量维数是最少需要多少个传感器，使每个节点到这些传感器的距离向量各不相同；这样源到传感器的距离就能唯一确定源。问题在于它通常很大。作者问：如果只要求把"相距较远"的节点区分开，能省多少传感器？剩下的候选集合会有多大？

2定义

• 节点 u 对传感器集合 S 的识别向量：u 到 S 中每个传感器的最短路长度。
• k-放宽解析集：只要两个节点的识别向量相同，它们的距离就不超过 k。k=0 时就是普通解析集。
• k-放宽度量维数 MD_k：最小的 k-放宽解析集的大小。

3理论结果

• 树上奇偶相同：MD_{2r}(T) = MD_{2r+1}(T)。因为两片叶子之间的距离至少为 2，放宽 1 没有帮助。
• 树上可精确计算：MD_{2r}(T) 等于把所有叶子反复删去 r 次（"去茎"）后那棵树的普通度量维数，而树的度量维数有经典公式：叶子数减外部主节点数。
• 随机树：对临界 Galton–Watson 树，借助边缘子树分布给出 MD_{2r}/n 的大数定律极限，并列出不同 r 下的系数，放宽后系数明显下降。

4数值实验

一般图上计算放宽度量维数是 NP 难的，作者用贪心算法求上界，并证明它与最优值之比为 O(log n)。比较三个指标：传感器占节点比例、无法唯一识别的节点比例、最大等价类大小 α（即最坏情况下的候选集合大小）。

• 图：Barabási–Albert 树、Galton–Watson 树、配置模型、随机几何图，以及若干真实网络（合作者网络、哥本哈根通话与好友网络、酵母网络等）。
• BA 树上，k 从 0 放宽到 2，所需传感器大幅下降；无法唯一识别的节点比例从 0 升到约 60%，但最大等价类在 1000 个节点里不到 20 个。
• 真实网络上趋势相同：稍作放宽就大幅减少传感器，最大等价类始终很小（哥本哈根好友网络本来度量维数就低，是例外）。

5两步定位

1. 被动阶段：按 k-放宽解析集放置固定传感器，得到源所在的等价类。
2. 主动阶段：只在这个等价类里追加传感器，把源唯一确定。

总传感器数按最坏情况计：q*_k = 第一步传感器数 + 各等价类所需追加数的最大值。k=0 时等于度量维数；k 大于直径时第一步为空，又回到度量维数。中间存在一个 k 使总数最小，作者在随机图和真实网络上都观察到这个先降后升的形状。该策略要求源固定且信号持续，适合需要精确定位的场景。

6局限

• 完全确定性：没有随机传播，没有覆盖概率，候选集合以概率 1 包含源。
• 假设知道到传感器的绝对距离（即已知开始时间、时延确定）。
• 指标是最坏情况的最大等价类，不是期望集合大小。
• 一般图上只有贪心上界。

7作者代码讲解

仓库 mdreveton/metric-dimension-relaxed，提交 0c12b6a2。Python，依赖 igraph 与 rustworkx。本节为静态阅读，未运行。

贪心是怎么做的

1. 用 igraph 一次算出全图最短路距离矩阵。
2. 待区分集合 U：所有距离大于 k 的节点对。
3. 对每个节点 v，预先算出 S[v]：U 中到 v 距离相等、因而不能被 v 区分的节点对。
4. 每步选 |S[v] ∩ U| 最小的 v（等价于区分掉最多的剩余节点对），从 U 中删去它能区分的对，直到 U 为空。这是标准的集合覆盖贪心，所以有 O(log n) 的近似比。

两步定位的计算

先用上面的贪心放好第一步传感器，按识别向量分出等价类；再对每个等价类单独用同样的贪心求一个能区分类内所有节点的追加集合，取其中最大的追加数，加上第一步的数量，就是论文的 q*_k。所以第二步是"对每个类一次放好"，而不是看到结果再逐个追加。

代码与论文的关系

• 实现与正文描述一致；附录 D 的伪代码本次未逐行对照。
• U 有 O(n²) 个节点对，每个 S[v] 也可能有 O(n²) 个，内存最坏 O(n³)，适合千节点量级的图。
• 只处理无权图上的跳数距离，与论文假设一致。

8与你的方案（传感器部署 + 有效源集合）的关系

这篇确立了"用集合换传感器"的问题，但只在确定性框架下。你的方案可以表述为它的随机版本：时延随机时，"放宽"自然来自 α，而不是人为的距离阈值 k。阶段 1 可加一个基线：在零方差近似下用本文贪心选传感器，再交给随机模型做有效集合。