多通道单跳无线网络的可扩展唤醒

### 多通道单跳无线网络的可扩展唤醒 #### 1. 引言 在无线通信领域，多通道单跳无线网络是一种重要的网络拓扑。传统上，通常假设一个站点在同一时间最多连接一个通道进行传输或监听。而现在考虑一种更强的模型，即一个站点可以同时且独立地使用所有可用通道，部分用于传输，部分用于监听。不过，这些通道不具备冲突检测功能，这使得该模型比具有载波感知能力的多通道模型要弱。 该算法的核心问题是唤醒网络。初始时，所有站点处于休眠状态，但连接并监听所有通道。部分站点会自发激活，并希望整个网络被激活和同步。在任何通道上的第一次成功传输就足以实现这一目标。 使用以下参数来描述多通道网络： - \(n\)：表示站点的数量。 - \(b\)：表示共享通道的数量。 - \(k\)：最多有 \(k\) 个站点会在任意时间自发激活，目标是唤醒网络。站点知道 \(n\) 和 \(b\)，但 \(k\) 是一个未知参数，仅用于描述给定唤醒算法的可扩展性。 #### 2. 研究成果 - **确定性算法**： - 一般情况下，提出的确定性算法能在 \(O(k \log_{1/b} k \log n)\) 轮内唤醒网络。 - 当通道数量足够多时（\(b > \lg(128b \lg n)\)），另一个确定性唤醒算法能在 \(O(\frac{k}{b} \log n \log(b \log n))\) 时间内唤醒网络。同时证明了任何确定性算法所需的时间下限为 \(\Omega(\frac{k}{b} \log \frac{n}{k})\) 轮。从这个下限来看，时间性能为 \(O(\frac{k}{b} \log n \log(b \log n))\) 的算法与最优时间的差距最多为 \(\log n \log b\) 倍。 - **随机算法**：对于任意未知的 \(0 < \epsilon < 1\)，随机算法能在 \(O(k^{1/b} \ln \frac{1}{\epsilon})\) 轮内以至少 \(1 - \epsilon\) 的概率唤醒网络。 - **干扰模型**：考虑一种干扰模型，其中每个通道在任何一轮中都可能被干扰，从而阻止成功传输，这种情况以已知的参数概率 \(p\) 独立发生在所有通道和轮次中。针对该模型，给出的确定性算法能在 \(O(\log^{-1}(1/p)k \log n \log_{1/b} k)\) 时间内以至少 \(1 - \frac{1}{poly(n)}\) 的概率唤醒网络。 #### 3. 技术预备知识 多通道单跳无线网络模型的定义如下： - 有 \(n\) 个节点连接到 \(b\) 个频率的频谱上，“站点”和“节点”这两个术语可互换使用，所有站点的集合用 \(V\) 表示。 - 每个频率确定一个多址通道，这 \(b\) 个通道同时且独立运行。所有站点始终监听所有通道，并从每个通道获得相同的反馈。一个站点可以在任何时间在任何一组通道上进行传输，并分别且同时从每个通道获得相应的反馈。 ##### 通道语义 - **成功接收**：当一个站点成功接收到在某个通道上传输的消息时，称该站点听到了该消息。 - **通道静默**：当没有站点在某个通道上传输时，该通道处于静默状态。 - **冲突发生**：当多个站点在一个通道上传输，且它们的传输发生重叠时，称该通道在重叠时间内发生了冲突。 ##### 传输同步 所有通道上的传输是同步的，即算法的执行被划分为等长的轮次，每个传输都发生在某个轮次中。每个站点都有自己的私有时钟，以轮次为单位计时，所有通道的轮次开始和结束时间相同。消息的传输时间被缩放为一轮，两个传输在时间上重叠当且仅当它们在同一轮中进行。 ##### 自发激活与网络唤醒 - **自发激活**：初始时，所有站点处于被动状态，不执行任何通信算法，也不在任何通道上传输消息，但会一直监听所有通道。在某个时间点，部分站点会自发激活，之后变为活跃状态。被动站点可能在第一次激活轮次之后继续自发激活，特定站点激活的时间场景称为激活模式。 - **网络唤醒**：一个激活的站点在激活轮次将其私有时钟重置为零。当一个站点变为活跃时，它从其私有时钟的第一轮开始执行算法，目标是唤醒整个网络。当某个活跃站点在某个通道上作为该轮中唯一的传输站点进行传输时，网络唤醒的目标就实现了。这一刻可理解为所有被动站点接收到唤醒信号，并开始执行预定的通信算法，同时也可用于同步本地时钟。 唤醒算法的性能通过从第一次自发激活到网络上第一次听到消息的轮数来衡量。 #### 4. 定义总结 - **全局时间**：时间步指的是外部观察者测量的时间，称为全局时间。某个站点第一次自发激活的轮次成为全局时间的第一个时间步。站点 \(u\) 自发激活的时间步用 \(\sigma_u\) 表示，到时间步 \(t\) 时活跃的站点集合用 \(W(t)\) 表示。 - **传输数组**：设 \(\ell\) 为正整数参数，形式为 \(T (u, \beta, j)\) 的数组 \(T\)（其中 \(u \in V\) 是站点，\(1 \leq \beta \leq b\) 是通道，\(0 \leq j \leq \ell\) 是整数），当每个条目为 0 或 1 时，它是一个传输数组。\(\ell = \ell(T)\) 称为数组 \(T\) 的长度，传输数组 \(T\) 的条目称为传输位，\(j\) 是传输位 \(T (u, \beta