# Fast and Robust Asynchronous Rendezvous Scheme for Cognitive Radio Networks
## 4 Proposed Channel-Hopping Scheme
### FRARS for Symmetric System  
In the considered system, time is divided into equal slots and slots are numbered from 0. The length of a slot is assumed to be the minimum time required for any two nodes to discover each other and exchange the necessary information. Figure 4 describes my system model structure that represents \(k\) slots difference asynchronous rendezvous scenario. The length of a node's CH sequence period is assumed to be \(2M-1\) as will be addressed in the following. Thus, \(u=\{u_{0},u_{1},...,u_{i},...,u_{2M-2}\}\) is a CH sequence, where \(u_{i}\in[1,M]\) represents the channel index in the \(i\)th time slot of sequence \(u\). Please note that the CH sequence changes every period. If I mark a slot number as \(I\) and two CH sequences (\(u\) and \(v\)) are given as shown in Figure 4, I say that node A and B rendezvous in the \(i\)th time slot on channel \(c\) when \(u_{\{i=I\ mod\ 2M-1\}}=v_{\{j=(I-k)\ mod\ 2M-1\}}=c\), where \(c\in[1,M]\). In order words, any two nodes can rendezvous even though the misalignment distance of their starting slots is \(k\), which is referred to as \(k\)-shift rendezvous [23]. In my proposed scheme, if an SU has data to transmit, it follows the transmit CH sequence; otherwise it follows the receive CH sequence, i.e., the sender and receiver have different CH sequences. In every round of the sending CH sequence, a random permutation of the available channels is used in the first \(M\) time slots, and the reverse order of that random permutation excluding the last channel will be added in the next \(M-1\) time slots. Let the first part of \(M\) time slots and the next part of \(M-1\) time slots denote _permutation part_ and _reversed repetition part_, respectively. If I denote the permutation part with \(R=\{r_{0},r_{1},...,r_{i},...,r_{M-1}\}\), where \(r_{i}\in[1,M]\), the sending CH sequence will be expressed as:  
\[u_{i}= \begin{cases}r_{i}&\text{for}\quad 0\leq i\leq M-1\\ r_{2M-2-i}&\text{for}\quad M\leq i\leq 2M-2\end{cases}  \tag{1}\]  
The receiving CH sequence selects one random channel among \(M\) available channels and then stays on that channel for one round. Figure 5 illustrates an example of a rendezvous in FRARS when \(M\) is 3. The transmit CH sequence represents three rounds and the receive CH sequence represents two rounds with \(k\) slots difference from the sender, i.e., there is \(k\) slots time difference between the sender and receiver. The shaded slots in the transmit CH sequence represents the permutation parts, and the rest of time slots represents the reversed repetition parts. For example, the sender visits channels 2 and 1 at slot numbers 3 and 4, which are in reverse order of slot numbers 0 and 1. Similarly the channel indexes in the slots numbered 5 and 6 are reused in slot numbers 8 and 9, while the receiving CH sequence randomly chose channel 1 in the first period and channel 3 in the second period. The shaded time slot of the received CH sequence refers to the rendezvous. Figure 4: System model structure. **Theorem 1**. : _Given \(M\) available channels, FRARS guarantees \(k\)-shift rendezvous for all \(k(=0,1,...,2M-2)\) so that any pair of sender and receiver must rendezvous within \(2M-1\) slots._  
Proof. : For \(k=0\), the random permutation part \((u_{0},u_{1},...,u_{M-1})\) in a sending CH sequence is totally overlapped with a receiving CH sequence, i.e., \(TTR\leq M\). For \(k=1\), the first time slot of the permutation part is not overlapped with a receiving CH sequence, but the channel index \(u_{0}\) is reused in the last time slot of the reversed repetition part \((u_{0}=u_{2M-2})\). Therefore, the sender and receiver CH sequences \(u\) and \(v\) rendezvous in the worst case on channel \(c\) when \(u_{2M-2}=v_{2M-3}=c\), where \(c\in[1,M]\), i.e., \(TTR\leq 2M-2\). For \(k=2\), in a similar way, the sender and receiver CH sequences \(u\) and \(v\) rendezvous in the worst case on channel \(c\) when \(u_{2M-2}=v_{2M-4}=c\), where \(c\in[1,M]\). That is, \(TTR\leq 2M-3\).