# Fast and Robust Asynchronous Rendezvous Scheme for Cognitive Radio Networks
## 4 Proposed Channel-Hopping Scheme
### FRARS for Symmetric System
As the value of \(k\) increases, the upper bound of TTR decreases until the value of \(k\) is equal to \(M-1\), where \(TTR\leq M\). For \(k=M\), only \(M-1\) ending slots in the reversed repetition part are overlapped with a receiving CH sequence. Hence, rendezvous can occur in the next \(M\) permutation part of the second period, i.e., \(TTR\leq 2M-1\). For \(k=M+1\), only \(M-2\) ending slots in the reversed repetition part are overlapped, thus the next \(M\) permutation part of the second period is included in TTR, i.e., \(TTR\leq 2M-2\). The upper bound of TTR decreases until the maximum value of \(k=2M-2\). Therefore, given \(M\) available channels, the upper bound of TTR can be expressed as:  
\[MTTR= \begin{cases}M&\text{ for }k=0\\ 2M-1-(k\text{ mod }M)&\text{ for }1\leq k\leq 2M-2\end{cases}  \tag{2}\]  
Consequently, the upper bound of MTTR in FRARS is 2N-1. **Theorem 2**. : _Given \(M\) available channels, \(ETTR\) of FRARS is not greater than \(\frac{3}{4}M+\frac{1}{4M}\)._  
Proof. : For \(k=0\), since the random permutation part is totally overlapped with a receiving CH sequence, rendezvous can happen in each time slot within the permutation part with probability \(1/M\), i.e., ETTR is \(1\frac{1}{M}+2\frac{1}{M}+3\frac{1}{M}+...+M\frac{1}{M}=\frac{M+1}{2}\). For \(k=1\), rendezvous can happen in the beginning \(M-1\) time slots of the receiving CH sequence \((v_{0},v_{1},...,v_{M-2})\) with probability \(1/M\) and one more rendezvous is possible in the last time slot of the reversed repetition part \((u_{2M-2}=v_{2M-3})\) with probability \(1/M\), i.e., ETTR is \(\frac{1}{M}\frac{(M-1)M}{2}+\frac{1}{M}(2M-2)\). For \(k=2\), in a similar way, \(M-2\) time slots \((v_{0},v_{1},...,v_{M-3})\) and two time slots \((v_{2M-5},v_{2M-4})\) are possible rendezvous slots with probability \(1/M\), i.e., ETTR is \(\frac{1}{M}\frac{(M-2)(M-1)}{2}+\frac{1}{M}(2M-3+2M-4)\). Therefore, I can derive a generalized form of ETTR \(0\leq k\leq M-1\) as follows:  
\[ETTR=\frac{(M-k)(M-(k-1))}{2M}+\frac{\sum_{i=1}^{k}(2M-(k+i))}{M}. \tag{3}\]  
Figure 5: Illustration of FRARS when the number of available channels is 3. For \(k=M\), rendezvous can happen in the overlapped \(M-1\) ending slots in the reversed repetition part with probability \(1/M\), and one more rendezvous is possible in the next \(M\) permutation slots of the second period with probability \(1/M^{2}\), i.e., ETTR is \(\frac{1}{M}\frac{(2M-(k+1))(2M-k)}{2}+\frac{\sum_{i=0}^{M-1}(2M-k+i)}{M^{2}}\). For \(k=M+1\), in a similar way, rendezvous can happen in \(M-2\) ending slots with probability \(1/M\) and two channels can rendezvous in the next \(M\) permutation slots with probability \(1/M^{2}\). Therefore, a generalized form of EETR for \(M\leq k\leq 2M-2\) can be expressed as:  
\[ETTR=\frac{(2M-(k+1))(2M-k)}{2M}+\frac{\sum_{i=0}^{M-1}(2M-k+i)}{M^{2}}\times( k-M+1). \tag{4}\]  
To find an upper bound of ETTR, I rearrange Equations (3) and (4) as follows:  
\[ETTR= \begin{cases}-\frac{k^{2}}{M}+(1-\frac{1}{M})k+\frac{M+1}{2},&0\leq k\leq M -1\\ -\frac{k^{2}}{2M}+(\frac{3}{2}-\frac{1}{M})k-(\frac{M^{2}-4M+1}{2M}),&M\leq k \leq 2M-2\end{cases}  \tag{5}\]  
Since the second derivative of (5) is negative, the value of \(k\) for which the first derivative of (5) with respect to \(k\) is equal to zero corresponds to a maximum value of ETRR, i.e., the maximum value of ETTR for \(0\leq k\leq M-1\) is \(\frac{3}{4}M+\frac{1}{4M}\) when \(k=\frac{M-1}{2}\), and the maximum value of ETTR for \(M\leq k\leq 2M-2\) is \(\frac{5}{8}M+\frac{1}{2}\) when \(k=\frac{3M-2}{2}\). Since I assume that the value of \(k\) is a positive integer value as depicted in Figure 4, the maximum value of ETTR for \(0\leq k\leq M-1\) is equal to or greater than the maximum value of ETTR for \(M\leq k\leq 2M-2\). Consequently, the upper bound of ETTR in FRARS is \(\frac{3}{4}M+\frac{1}{4M}\).