Consistent Channel Hopping Algorithms for Rendezvous Search
Yi‐Chia Cheng, Yiwei Liu, Cheng‐Shang Chang · 2025
This paper presents a theoretical framework for consistent channel hopping algorithms to address the multi-channel rendezvous problem (MRP) in wireless networks. We define consistency in channel selection functions as the ability to maintain selection when channels are removed, as long as the selected channel remains available. Key contributions include: (i) showing that all consistent functions are equivalent to selecting the smallest indexed channel through channel relabeling; (ii ) characterizing rendezvous time slots using a fictitious user whose channel set is the union of both users' sets; (iii) deriving a tight Maximum Time-to-Rendezvous (MTTR) bound with one-cycle permutations; and (iv) proving that the Expected Time-to-Rendezvous (ETTR) is the inverse of the Jaccard index using random permutations. We also show that certain state-of-the-art locality-sensitive hashing (LSH) algorithms are consistent and generated by one-cycle permutations. To reduce computational complexity, we propose the modulo algorithm, which uses the modulo operation to generate channel hopping sequences. Simulations confirm that the modulo algorithm achieves competitive ETTR performance compared to LSH-based algorithms.