paper_5 第一节引言

第 1 节引言

首先回顾了 DS、CDS 和 MinCDS 的定义。CDS 在 WSN 中可以作为虚拟骨干，用于缓解广播风暴问题。
已有 CDS 研究通常假设网络拓扑和节点状态是固定且预先已知的，
但移动无线网络中节点会受到信号强度、电池电量、环境干扰等因素影响，导致节点状态和网络结构具有随机性。
因此，随机优化方法适合用于建模该类网络。

已有工作 Fukunaga 研究了 robust CDS，其中节点状态 hidden，需要通过 probing 获得 active/inactive 信息。
并在 active 节点组成的图中构造 CDS，同时最小化 probing cost。
但该工作假设任意节点集合成为 active 集合的概率已知，模型较一般且复杂。
本文则假设概率分布作用在单个节点上，即每个节点有独立的 active 概率 p(v)，从而研究独立节点状态下的 stochastic CDS 问题。

价值1 说明研究背景

已有 CDS 研究主要集中在确定图上的 MinCDS / MinWCDS，而随机场景下的 CDS 研究相对较少。Fukunaga 虽然研究了 robust MinWCDS，但其方法依赖 NWPST 问题，且模型较复杂。Adaptive SCDS 论文进一步考虑独立节点状态下的 stochastic CDS，为随机节点状态下的虚拟骨干构造提供了基础。

价值2 容错切入

已有工作已经做了：
$$
\text{stochastic CDS}
$$
但想做：
$$
\text{stochastic fault-tolerant CDS}
$$
也就是在随机节点状态和探测代价模型下，进一步要求骨干具有容错性。

例如：
$$
G[C] \text{ 是 2-connected}
$$
这在这一段 Related Works 里还没有被解决。

换句话说，找到一个空白：

随机 CDS 有研究，容错 CDS 有研究，但随机探测场景下的容错 CDS 还可以继续做。

笔记

Related Works 主要回顾了两类工作。第一类是确定图上的 MinCDS 和 MinWCDS。MinCDS 是经典 NP-hard 问题，已有许多基于最大度 Δ 或节点数 n 的近似算法；MinWCDS 更加困难，也有相关近似结果。单位圆盘图上的 CDS 问题也被广泛研究，因为其适合建模无线传感器网络。

第二类是随机优化中的自适应算法。Fukunaga 研究了 robust MinWCDS，其中节点状态 hidden，需要通过 probe 获得 active/inactive 信息，并考虑 full feedback 和 local feedback 两种模型。但该算法依赖 NWPST 问题的近似算法，而一般图上的 NWPST 尚无已知非平凡近似算法。本文在此基础上采用更具体的独立节点概率模型，为 stochastic CDS 设计自适应近似算法。

逻辑链：

$$
\text{确定图 CDS}
\rightarrow
\text{随机节点状态}
\rightarrow
\text{自适应探测}
\rightarrow
\text{stochastic CDS}
$$
而后面的研究链条应该是：
$$
\text{stochastic CDS}
\rightarrow
\text{fault-tolerant stochastic CDS}
\rightarrow
\text{Adaptive 2-connected CDS}
$$

B Our contribution

这里的 profit 大概是什么？

作者说：

selection criterion is based on maximizing profit, evaluated using real-time weights.

也就是说，每轮选节点时，不是随便选，而是根据当前状态计算一个“收益”。

虽然严格定义后面才给，但可以先理解成：

探测这个节点能带来多少好处。

可能包括：

能支配多少尚未支配的节点；
能连接多少已有 active 分量；
探测成功概率有多高；
对当前构造 CDS 有多大帮助。

这和后面想做的“概率感知路径增强”非常接近。

后续做容错时，也可以自定义 profit，例如：
$$
profit(P)=\frac{\text{容错增强收益}\times\text{路径成功概率}}{\text{探测代价}}
$$

与后续容错方向的联系

随机 MinCDS 的两个核心特点：

第一，目标是 minimize probing cost

希望在构造容错 CDS 的同时控制探测代价。

也就是：
$$
\min probing\ cost
$$
或者同时观察：

probing cost；
final backbone size；
success rate；
robustness。

第二，解是 policy

做容错时，也不该设计成简单的离线算法：

先知道所有 active 节点，再跑 2-CDS。
不是 adaptive 。

而应设计成：

根据已探测到的 active 节点和当前骨干结构，动态选择下一条增强路径或下一个探测节点。

才符合论文场景。

笔记

Our Contribution 部分指出，stochastic MinCDS 与 deterministic MinCDS 的关键区别在于：确定性 CDS 目标通常是最小化 CDS 节点数，而随机 CDS 的目标是最小化 probing cost。由于节点状态未知，算法不需要探测全图所有节点，而是围绕包含 root 的 active 连通分量及其邻近节点逐步探测。

此外，stochastic CDS 的解本质上不是一个固定节点集合，而是一种 policy，即根据当前已探测信息决定下一步探测哪个节点。本文提出一个基于贪心思想的自适应算法，每轮在当前已选 active 节点 2-hop 范围内选择收益最大的节点进行探测，并给出了期望意义下的近似比。

关键

随机 CDS 的核心不是“选哪些节点”，而是“在信息不完整的情况下，按什么策略探测节点”。

对应的方向就是：

随机容错 CDS 的核心不是直接构造一个 2-CDS，而是在节点状态未知时，按什么策略探测节点，逐步构造一个具有容错能力的 CDS。