Upper bounds and constructions of complete Asynchronous channel hopping systems

Asynchronous channel hopping (ACH) systems are widely used for the blind rendezvous among secondary users in cognitive radio networks without requirement for global synchronization and common control channels. We can view an ACH system with n channels as a set of sequences of a common period t on an alphabet of size n satisfying certain rotation closure properties. For any two distinct sequences u, v in an ACH system \(\mathcal {S}\), every l ∈{0,1,⋯ , t − 1} and any letter j in the alphabet, if there always exists i such that the i-th entries of u and L^l(v) are identical to j where L^l(v) denotes the cyclic shift of v by l, then we say that \(\mathcal {S}\) is a complete ACH system. Such a system can guarantee rendezvous between any two secondary users who share at least one common channel. It is well known that \(t\geqslant n^{2}\). When the equality holds, \(\mathcal {S}\) is called a perfect ACH system. By applying characters of cyclic groups, we obtain a new upper bound on the number of sequences in a perfect ACH system. Furthermore, when q is a prime power and n = q − 1, we present a construction of homogeneous complete ACH systems of period t = 2n² + o(n²).