自适应占空比无线传感器网络上的多跳广播研究

### 自适应占空比无线传感器网络上的多跳广播研究 在多跳无线传感器网络中，广播是一项关键操作，但面临着诸多挑战，如广播延迟和冗余传输等问题。本文将深入探讨相关的解决方案，包括不同的广播方法、网络模型以及一种名为Hybrid - cast的协议，并对其性能进行分析。 #### 1. 现有广播方法分析 - **基于能量优化树的方法**：一些研究构建能量最优树以减少泛洪延迟和冗余度。为解决决策冲突，构建了减少泛洪的发送者集合来缓解隐藏终端问题，在同一发送者集合内，使用基于链路质量的退避方法来解决和确定同时转发操作的优先级。不过，纯机会主义泛洪的主要问题是传输时间方面的开销。 - **同步或占空比感知方法** - 有研究提出集中式算法，将多跳广播问题数学建模为时间覆盖图中的最短路径问题，还提出了两种类似的分布式算法。但该工作简化了完整MAC协议所需的许多方面，可能不适用于实际实现，且假设了占空比感知，由于时钟漂移需要定期时间同步，在异步无线传感器网络中使用困难。 - RBS提出了一种用于占空比传感器网络的广播服务，显示了其在减少广播次数和能量成本方面的有效性。然而，这些基于同步的工作都假设通常有多个邻居同时可用于接收发送者发送的多播/泛洪消息，这在低占空比异步网络中并不成立。 - **异步解决方案** - B - MAC可以像支持单播一样支持单跳广播，因为在整个睡眠周期内发送前导码使所有发送节点的邻居有机会检测到前导码并保持清醒以接收数据包。 - X - MAC显著提高了B - MAC的单播性能，但未明确讨论广播支持，由于发送者必须不断触发邻居唤醒，因此在广播方面不太有前景。 - ADB通过有效传递每个广播的进度信息，避免了B - MAC和X - MAC面临的问题。它允许节点在无需再到达更多邻居时立即进入睡眠状态。ADB设计为与不会长时间占用介质的单播MAC集成，以最小化转发广播前的延迟。它根据链路质量调整向邻居传递广播数据包的努力，而不是在整个占空比周期内发送或等待邻居唤醒。但ADB属于单播替代方法，需要对现有MAC协议进行重大修改以支持广播。 #### 2. 网络模型和假设 - **网络模型**：将多跳无线传感器网络建模为有向图G(V, E)，其中V是节点集，E是边集。若节点vj在节点vi的传输范围内，则边(vi, vj)在E中，假设链路是双向的。这里的“连通性”是指在我们的上下文中，拓扑连通的网络可能并非随时都连通，但所有节点可在有限时间内通过底层MAC协议从一个节点到达。定义节点ni的一跳邻域为N(i)。 - **时间假设**：时间轴安排为连续的短时间槽，所有时间槽具有相同的持续时间Ts，每个节点ni每Li个时间槽采用周期性唤醒调度。唤醒调度可以是每Li个槽一次，也可以基于仲裁调度（如循环仲裁系统或网格仲裁系统）。Li称为节点ni的周期长度，假设在唤醒槽开始时发送信标消息，当节点要传输消息时，会等待直到从邻居接收到信标。 - **其他假设** - 节点之间没有时间同步，即两个节点的时间槽不一定对齐。 - 打开和关闭无线电的开销与长时间槽（50ms - 500ms）相比可忽略不计。 - 网络中只有一个汇聚节点，但解决方案可轻松扩展到多个汇聚节点的场景。 #### 3. 异构唤醒调度 - **低占空比调度**：节点每ni（ni为整数）个时间槽唤醒一个槽。例如，接收器1的调度为[1, 0, 0]，接收器2的调度为[1, 0, 0, 0]，它们的唤醒槽并不总是重叠。 - **仲裁占空比调度**：唤醒调度遵循仲裁系统设计。在基于仲裁的占空比中，两个相邻节点通过仲裁的非空交集属性，可在有限时间槽内至少相互听到一次。本文选择循环仲裁系统，但其工作也可应用于其他仲裁系统。相关定义如下： - 设n表示周期长度，U = {0, · · ·, n - 1}。仲裁系统Q是U的非空子集的超集，每个子集称为一个仲裁，满足交集属性：∀G, H ∈ Q : G ∩ H ≠ ∅。若∀G, H ∈ Q, i ∈ {0, 1, ...n - 1} : G ∩ (H + i) ≠ ∅，其中H + i = {(x + i) mod n : x ∈ H}，则称Q具有旋转封闭属性。 - 循环仲裁系统（cqs）满足旋转封闭属性，记为C(A, n)，其中A是一个仲裁，n是周期长度。例如，cqs {{1, 2, 4}, {2, 3, 5} · · ·, {7, 1, 3}}可记为C({1, 2, 4}, 7)，符合C({1, 2, 4}, 7)的唤醒调度为[1, 1, 0, 1, 0, 0, 0]及其旋转。对于两个不同的循环仲裁系统C(A1, n1)和C(A2, n2)，若分别从它们中选取的两个仲裁即使在时钟漂移的情况下也有非空交集，则可用于无线传感器网络的异构唤醒调度。 #### 4. 问题陈述 定义广播延迟为广播开始到每个节点接收到广播消息的时间，广播次数为所有节点进行广播以确保整个网络接收到消息的次数。目标是设计一种广播调度，既能缩短广播延迟，又能减少向整个网络泛洪消息的广播次数。Hybrid - cast协议是该问题的一种启发式解决方案。 #### 5. Hybrid - cast协议概述 - **唤醒等