In this paper, we consider contention resolution on a multiple-access communication channel. In this problem, a set of nodes arrive over time, each with a message it intends to send. In each time slot, each node may attempt to broadcast its message or remain idle. If a single node broadcasts in a slot, the message is received by all nodes; otherwise, if multiple nodes broadcast simultaneously, a collision occurs and none succeeds. If collision detection is available, nodes can differentiate collision and silence (i.e., no node broadcasts). Performance of contention resolution algorithms is often measured by throughput---the number of successful transmissions within a period of time; whereas robustness is often measured by jamming resistance---a jammed slot always generates a collision. Previous work has shown, with collision detection, optimal constant throughput can be attained, even if a constant fraction of all slots are jammed. The situation when collision detection is not available, however, remains unclear.

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.

Broadcasting in wireless networks is vulnerable to adversarial jamming. To thwart such behavior, researchers have proposed resource competitive analysis. 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, each node can receive the message in roughly O(T/C) time, while spending only roughly [EQUATION] energy. However, these algorithms only work for C = O(n), and can only tolerate an oblivious adversary. We improve the result by considering an adaptive adversary and arbitrary values of n and C. In our algorithms, for large T values, each node's runtime is O(T/C), and each node's energy cost is [EQUATION]. The time complexity is asymptotically optimal, while the energy complexity is near optimal in some cases. We use "epidemic broadcast" with proper working probabilities to achieve time efficiency and resource competitiveness, and leverage coupling arguments in the analysis to handle the adaptivity of the adversary.

Consider a single-hop, multi-channel, synchronous radio network in which a source node needs to disseminate a message to all other $n-1$ nodes. An adversary called Eve, which captures environmental noise and potentially malicious interference, aims to disrupt this process via jamming. Assume sending, listening, or jamming on one channel for one time slot costs unit energy. The question is, if Eve spends T units of energy on jamming, can we devise broadcast algorithms in which each node's cost is o(T) Previous results show such resource competitive algorithms do exist in the single-channel setting: each node can receive the message within ~O(T+n) time slots while spending only ~O(√T/n+1) energy. In this paper, we show that when Eve is oblivious, the existence of multiple channels allows even faster message dissemination, while preserving resource competitiveness. Specifically, we have identified an efficient "epidemic broadcast" scheme in the multi-channel setting that is robust against jamming. Extending this scheme leads to a randomized algorithm called MultiCast which uses n/2 channels, and accomplishes broadcast in ~O(T/n+1) time slots while costing each node only ~O(√T/n+1) energy. When the value of n is unknown, we further propose MultiCastAdv, in which each node's running time is ~O(T/(n1-2α)+n2α), and each node's cost is ~O(√T/ (n1-2α) +n2α). Here, 0<α<1/4 is a tunable parameter affecting the constant hiding behind the big-O notation. To handle the issue of limited channel availability, we have also devised variants for both MultiCast and MultiCastAdv that can work in networks in which only C channels are available, for any C≥1. These variants remain to be resource competitive, and have (near) optimal time complexity in many cases.