butterfly

当前阶段 & 局限 1234567目标： 把当前普通 CDS 骨干 C 增强成 2-connected CDS。核心策略： 每一轮找一条候选增强路径； 路径成功后，把路径中间节点加入 C； 反复执行，直到 G[C] 变成 2-connected。 准确一点应该说： 当前策略不是“直接选择一条新增节点数最少的路径并必然使用”，而是“按新增节点数从小到大依次尝试候选路径，第一条 probe 成功的路径被采用”。 这个区别很重要。因为最短路径可能包含 inactive 节点，probe 失败后算法会继续尝试下一条候选路径。 当前多轮增强策略 augment_until_2_connected() 外层做的是： 12345while G[C] 还不是 2-connected: 计算当前割点和 leaf blocks 执行一轮路径增强 成功后更新 C 重新检查 G[C] 如果某轮失败，或者达到最大轮数，就停止。 所以这不是一次性把所有 leaf blocks 都修完，而是： 每轮只成功加入一条路径，然后重新计算当前骨干结构。 ...

一、工作内容 概括： 搭建了路径版本的基础工程，并完成了从“随机图生成 → 初始 CDS 构造 → 骨干割点分析 → leaf block 识别 → 候选增强路径生成”的完整流程。 可以做到： 123456781. 生成随机无线传感网图2. 随机确定节点 active / inactive 状态3. 筛选 root 所在活跃连通分量是 2-connected 的测试场景4. 构造一个普通 CDS 作为初始骨干 C5. 检查 C 是否是 CDS、是否 2-connected6. 找出 G[C] 中的割点7. 找出 G[C] 中的 leaf block8. 对每个 leaf block 生成候选增强路径 目前已经跑出了合理结果： 1234root 活跃分量是 2-connected初始 C 是 CDS初始 C 不是 2-connected候选增强路径成功生成 这说明路径版本的前半部分已经打通了。 二、改动文件 主要涉及这几个文件： 1234567adaptive_FT_path/├─ config.py├─ graph_model.py├─ connectivity_check...

1. 节点版本 每一轮算法只考虑“选哪个节点 $v$ 去 probe”。 也就是说，候选对象是单个节点： $$ v $$ 然后给每个候选节点计算： $$ NW_S(v),\quad NC_S(v),\quad FT_S(v) $$ 最后根据评分选择一个节点 probe。 节点版本的算法形式更接近原论文 Algorithm 1。 2. 定义 $LB_S(v)$ 令 $$ C $$ 为当前黑色骨干节点集合，即当前已经被 probe 且 active 的节点集合。 考虑： $$ G[C] $$ 的 leaf blocks。定义： $$ LB_S(v)={B: B\text{ 是 }G[C]\text{ 的 leaf block，且 }v\text{ 邻接 }B\text{ 中某个节点}} $$ 也就是说，$LB_S(v)$ 表示： 节点 $v$ 能接触到多少个不同 leaf block。 3. $FT_S(v)$ 相关定义 $$ FT_S(v)=\max{|LB_S(v)|-1,0} $$ $LB_S(v)$ ≥ 2 时，才考虑有收益。 其中： $$ LB_S(v)={B:...

先给结论： Claim 1 是把算法探测次数 转化为 所有节点的总 charge。 Claim 2 是把这些 charge 和最优策略 $O$ 联系起来，证明每个最优节点 $v$ 的闭邻域里，charge 总量不会太大。 1. Claim 2 要证明什么？ Claim 2 的结论是： $$ \sum_{u\in N_G[v]}E[cw(u)] \leq \frac{1}{p(v)}H(\Delta-1)+1+\frac{1}{\delta} $$ 其中： $v\in O$：$v$ 是最优策略 probe 的节点； $N_G[v]$：节点 $v$ 在原图中的闭邻域，包括 $v$ 自己和它的邻居； $cw(u)$：节点 $u$ 收到的 charge； $p(v)$：节点 $v$ active 的概率； $\delta$：全图节点最小 active 概率； $\Delta$：图最大度； $H(\Delta-1)$：调和数。 这句话翻译后就是： 对最优策略中的任意一个节点 $v$，算法在 $v$ 的闭邻域里产生的总 charge 是有上界的，最多大约是 $$ \frac{1}...

Claim 1 它想证明： $$ E[|S|]=\sum_{u\in V}E[cw(u)] $$ 也就是： 算法的期望探测次数 = 所有节点收到的期望 charge 总和。 这个结论一旦成立，后面可以不直接分析 $|S|$，而是转去分析所有节点收到的 charge。 所以 Claim 1 的作用就是：把 probing cost 转化成 charge 分析。 1. 先看左边：$E[|S|]$ Algorithm 1 中： $$ S $$ 表示被算法主动 probe 的节点集合。 所以： $$ |S| $$ 就是算法主动探测的节点数量。 而每 probe 一个节点，probing cost 是 1。 因此： $$ |S| $$ 就是算法的总 probing cost(探测代价)。 由于节点状态随机，所以 $|S|$ 也是随机变量！。 因此定理要分析的是： $$ E[|S|] $$ 也就是算法的期望探测次数。 2. 再看右边：$\sum_{u\in V}E[cw(u)]$ ？ 这里： $$ cw(u) $$ 表示节点 $u$ 收到的 charge 数量。 注意，charg...

analysis 为什么 Algorithm 1 的探测次数，在期望意义下不会比最优策略差太多？ “收费 charging method”是作者用来证明近似比的一种数学分析技巧。 先导： 费用不是现实中的钱，也不是 probing cost 本身，而是一种“记账工具”。作者把算法每次 probe 节点的代价，按照规则记到一些被揭示的节点身上，最后通过统计每个节点最多被记几次，来证明总探测代价有上界。 定理 5 到底想证明什么？ 定理 5 要证明： $$ E[|S|]\leq \left( \frac{1}{\delta}(H(\Delta-1)+1)+1 \right)|O| $$ 这里： $S$：Algorithm 1 探测过的节点集合； $|S|$：算法的 probing cost； $O$：最优策略探测过的节点集合； $|O|$：最优策略的 probing cost； $\delta$：节点最小 active 概率； $\Delta$：图最大度。 所以定理 5 的意思是： 本文算法的期望探测次数，不会超过最优策略探测次数的 $$ \frac{1}{\delt...

引理 3 12345678910论文将 Algorithm 1 的探测节点集合与最优策略在 full realization ϕ 下探测的节点集合 O 进行比较。需要注意的是，在 stochastic CDS 中，最优策略探测的节点集合 O 不一定等于最终 CDS，因为部分探测节点可能只是为了揭示状态信息，尤其是为了确认 root 所在 active 连通分量的边界。Lemma 3 是一个技术引理，用于估计找到第一个 active 节点所需的期望探测次数。设有相互独立事件 I_1,...,I_n，事件 I_i 发生概率为 p_i，且 p=min p_i。若 X 表示第一个发生事件的下标，则 E[X]≤1/p。直观上，如果每次尝试成功概率至少为 p，那么第一次成功之前的期望尝试次数不超过 1/p。该引理后续用于说明在节点 active 概率至少为 δ 的情况下，找到一个 active 节点所需的期望探测次数至多为 1/δ。 与容错关系 这段引理未来也可能能用到容错扩展里。 比如后面要找一条增强路径 $P$，路径上的中间节点状态未知。 如果需要探测一批候选节点或候选路径中的节点，那么...

主要证明 Lemma 2 的前半部分。证明了两个关键点： 算法终止时，黑色 + 灰色节点构成了 root 所在的 active 连通区域 $H$； 黑色节点集合 $A_S$ 支配这个区域 $H$； 证明 黑色节点集合 $A_S$ 自身是连通的。 最终目的是得到：$ A_S \text{ 是 } H \text{ 的 CDS} $ 也就是： $A_S$ 支配 $H$； $G[A_S]$ 连通。 注意这里输出的 $S$，但真正起作用的是 $S$ 中的 active/black 节点，也就是 $A_S$。理解时可以把输出骨干看成黑色节点集合。 √ 1. $H_\varphi$ 这里定义： $$ H_\varphi $$ 表示 $$ G[A_\varphi] $$ 中包含 root $r$ 的连通分量。 因为在随机场景下，所有 active 节点构成的子图： $$ G[A_\varphi] $$ 不一定连通。 比如有些 active 节点可能分布在另一个孤立区域中，和 root 所在区域没有 active 路径连接。 所以算法目标不是控制所有 active 节点，而是控制： ...

A 预备知识 联系 这一节给了出后面问题定义的模板。 原论文的 MinSCDS 是： 在节点状态未知的情况下，通过 probe 构造包含 root $r$ 的 CDS，目标是最小化 probing cost。 后续可以扩展成： 在节点状态未知的情况下，通过 probe 构造包含 root $r$ 的 2-connected CDS，目标是最小化 probing cost，同时保证一定容错性。 要注意的研究切口 原论文的探测目标是找普通 CDS，最终要求： $$ N[C]=A_\varphi $$ 或者至少支配 root 所在 active 连通分量，并且： $$ G[C]\text{ connected} $$ 但是容错版要求更强： $$ G[C]\text{ 2-connected} $$ 这会导致一个新问题： 原算法每轮只在 2-hop 范围内贪心扩展，是否足以构造 2-connected CDS？ 大概率不够。 因为 2 连通需要消除割点，需要考虑叶块、增强路径、备份连接。 这就是可以在后面提出改进算法的地方。 1234567891011Preliminarie...

第 1 节 引言 123456789首先回顾了 DS、CDS 和 MinCDS 的定义。CDS 在 WSN 中可以作为虚拟骨干，用于缓解广播风暴问题。已有 CDS 研究通常假设网络拓扑和节点状态是固定且预先已知的，但移动无线网络中节点会受到信号强度、电池电量、环境干扰等因素影响，导致节点状态和网络结构具有随机性。因此，随机优化方法适合用于建模该类网络。已有工作 Fukunaga 研究了 robust CDS，其中节点状态 hidden，需要通过 probing 获得 active/inactive 信息。并在 active 节点组成的图中构造 CDS，同时最小化 probing cost。但该工作假设任意节点集合成为 active 集合的概率已知，模型较一般且复杂。本文则假设概率分布作用在单个节点上，即每个节点有独立的 active 概率 p(v)，从而研究独立节点状态下的 stochastic CDS 问题。 A Related Works 价值1 说明研究背景 已有 CDS 研究主要集中在确定图上的 MinCDS / MinWCDS，而随机场景下的 CDS 研究相对较少。...