论文标题
在多通道无线网络中反对自适应对手的竞争广播
Broadcasting Competitively against Adaptive Adversary in Multi-channel Radio Networks
论文作者
论文摘要
无线网络中的广播很容易受到对抗性干扰的影响。为了阻止这种行为，提出了\ emph {资源竞争分析}。在此框架中，在一个频道上发送，聆听或干扰一次，插槽花费一个单位的能量。对手可以采用任意策略来破坏交流，但能源预算有限$ t $。另一方面，诚实的节点的目的是在仅花费$ o（t）$的同时完成广播。以前的工作已在包含$ n $节点的$ c $ - 通讯网络中，对于大$ t $值，每个节点可以在$ \ tilde {o}（t/c）$ time中接收消息，而仅花费$ \ tilde {o}（o}（o}）（\ sqrt {t/n}）$ energy。但是，这些多通道算法仅适用于$ n $和$ c $的某些值，并且只能容忍忽略的对手。 在这项工作中，从资源竞争力的角度来看，我们为在多渠道无线电网络中广播提供了新的上限和下限。我们的算法适用于任意$ n，c $值，需要最少的先验知识，并且可以容忍强大的自适应对手。更具体地说，在我们的算法中，对于大$ t $值，每个节点的运行时为$ O（t/c）$，每个节点的能量成本为$ \ tilde {o}（\ sqrt {t/n}）$。我们还与算法结果相辅相成，并证明了我们算法的时间复杂性和能量复杂性是最佳或近乎最佳的（在多golog因子内）。我们的技术贡献在于使用“流行广播”来实现时间效率和资源竞争力，并在分析中采用耦合技术来处理对手的适应性。在下边界，我们首先在多通道设置中为1-1通信提供新的能量复杂性下限，然后应用模拟和还原参数以获得所需的结果。
Broadcasting in wireless networks is vulnerable to adversarial jamming. To thwart such behavior, \emph{resource competitive analysis} is proposed. In this framework, sending, listening, or jamming on one channel for one time slot costs one unit of energy. The adversary can employ arbitrary strategy to disrupt communication, but has a limited energy budget $T$. The honest nodes, on the other hand, aim to accomplish broadcast while spending only $o(T)$. Previous work has shown, in a $C$-channels network containing $n$ nodes, for large $T$ values, each node can receive the message in $\tilde{O}(T/C)$ time, while spending only $\tilde{O}(\sqrt{T/n})$ energy. However, these multi-channel algorithms only work for certain values of $n$ and $C$, and can only tolerate an oblivious adversary. In this work, we provide new upper and lower bounds for broadcasting in multi-channel radio networks, from the perspective of resource competitiveness. Our algorithms work for arbitrary $n,C$ values, require minimal prior knowledge, and can tolerate a powerful adaptive adversary. More specifically, in our algorithms, for large $T$ values, each node's runtime is $O(T/C)$, and each node's energy cost is $\tilde{O}(\sqrt{T/n})$. We also complement algorithmic results with lower bounds, proving both the time complexity and the energy complexity of our algorithms are optimal or near-optimal (within a poly-log factor). Our technical contributions lie in using "epidemic broadcast" to achieve time efficiency and resource competitiveness, and employing coupling techniques in the analysis to handle the adaptivity of the adversary. At the lower bound side, we first derive a new energy complexity lower bound for 1-to-1 communication in the multi-channel setting, and then apply simulation and reduction arguments to obtain the desired result.
