认知无线电(cognitive radio，CR)被认为是一种可以提供频谱效率的颠覆性技术创新，广泛应用于军事、环境以及交通等各个领域。随着各种无线通信技术(如WiFi、蓝牙等)的兴起，ISM频段变得日益拥挤，现有的固定频谱分配方式必然会引起严重的频谱稀缺问题^[1]。伴随认知无线网络的发展，利用动态频谱接入技术的认知无线传感网(cognitive radio sensor network，CRSN)得到广泛重视和发展，它允许次用户(SU)利用动态频谱访问(DSA)技术使用分配给主用户(PU)的空闲频谱。

在认知无线传感网中，当作为SU的传感器节点与其他节点之间进行控制信息交换和频谱管理等操作时，节点间以分布式的形式，根据系统时钟自动切换到同一频谱，建立通信链路以实现通信的过程被称为信道会合或信道相遇(channel rendezvous)。Rendezvous问题的研究对于CRSN中传感器节点的通信起到了重要作用，在IEEE 802.22中的MAC层协议虽然能够根据网络环境的动态变化合理利用频谱，但没有涉及到Rendezvous机制的研究。

目前，控制信息的传输大多采用集中式控制方法^[2-3]或公共控制信道(common control channel，CCC)^[4-5]。这些机制可以较好完成控制信息的处理，但是，当网络动态变化时极易造成公共控制信道缺失或瓶颈，难以适应网络动态变化，且极易受到攻击^[6-7]。而Rendezvous机制不需要公共控制信道，也不需要目标节点感知信道集，可以更好适应网络动态变化，因此Rendezvous在实际应用中得到了广泛关注。

信道跳频(channel hopping，CH)技术是Rendezvous最具代表性的技术之一^[8-9], 通过使用信道跳频技术，CRSN的每个用户在其可感知信道集中进行信道跳频，以便与其潜在的邻居进行Rendezvous。然而现有的Rendezvous有以下不足：1)不能提供的有保证的Rendezvous(guaranteed rendezvous); 2)只适用于时钟同步模型；3)无法适用于非对称模型；4)不适用于多用户和多跳系统。如ETCH算法^[8]、较早的随机生成序列算法和时钟模块算法^[10-11]均只能在对称模型下达到Rendezvous，而AMRCC算法尽管在仿真实验中得到较好结果，但由于AMRCC算法是随机的，因此理论分析中非对称模型下无法达到有保证的Rendezvous^[12]。部分现有算法可以在对称和非对称模型下均达到有保证的Rendezvous，例如JS算法^[9]，但该算法在非对称模型下MTTR较大。

本文主要针对于CRSN中两用户提出一种新的Blind Rendezvous跳频算法，将节点状态按照发送状态和接收状态设置不同跳频序列，并引入信道使用概率设计逻辑信道和物理信道之间映射关系达到Full Rendezvous，较好达到了降低MTTR的目的。主要完成了以下研究问题：1)一种可以同时适用于对称模型和非对称模型的新的Rendezvous跳频算法，并且满足Rendezvous的有效执行(guaranteed rendezvous)；2)适用于成对用户的Rendezvous算法；3)针对最大相遇时间(maximum time-to-rendezvous，MTTR)的相关分析和证明；4)实验比较算法的优劣。

1 系统模型

本文主要讨论两个用户间的Rendezvous，假设在同一CRSN中，其中传感器节点i用S_i表示，作为SU存在，每个节点均装有半双工无线电以感知其可用的授权频谱。授权频谱被划分为M(M≥1)个正交的非重叠信道，且这些信道下标独立且唯一，信道集合C={C₁, C₂, …, C_M}。G_{x, y}定义为节点S_x和节点S_y的公共感知信道集合，即$ G = \left| {\bigcap\limits_{i - 1}^k {{c_i}} } \right|$。

当节点i处于发送状态下，信道x的发送概率记为Ps_i(x)(1≤x≤M)，满足：

$ P{s_i}\left( 1 \right) + P{s_i}\left( 2 \right) + P{s_i}\left( 3 \right) + \cdots + P{s_i}\left( x \right) = 1 $

(1)

当节点j处于接收状态下，信道y的接收概率为Pr_j(y)(1≤y≤M)，满足：

$P{r_j}\left( 1 \right) + P{r_j}\left( 2 \right) + P{r_j}\left( 3 \right) + \cdots + P{r_j}\left( y \right) = 1 $

(2)

本文SRP算法同时满足对称模型、非对称模型、时钟同步模型和时钟异步模型：

1) 对称模型：CRSN中所有用户感知信道集完全相同，即：M_r=M_S。M_S为发送状态下节点感知信道数目，M_r为接收状态下节点感知信道数目。

2) 非对称模型：CRSN中不同用户感知信道集不完全相同，即：M_r≠M_S且G_{R, S}≠0。Ux和Uy的公共感知信道集合。

3) 时钟同步模型：在CRSN中，所有用户开始跳频初始时间相同。本文假设时间被划分为长度相等的时间片。

4) 时钟异步模型：在分布式CRSN网络中，每个用户都可以在不同的时刻启动跳频序列，且该时刻是完全随机的，无法做到时钟同步。

相遇时间(time-to-rendezvous，TTR)是指用户达到Rendezvous所需要的时间片，是评估Rendezvous算法好坏的最重要的指标。由于跳频时间开始随机，所以TTR一般是不确定的。因此最大时间MTTR(maximum time-to-rendezvous)和平均时间ATTR(average time-to-rendezvous)是衡量SRP算法好坏的重要指标。

Rendezvous信道全覆盖(full Rendezvous)是指在感知信道集中的任意信道均可达到Rendezvous，本文将通过设置发送、接收概率阈值，调整逻辑跳频序列，避免某一信道使用频率过高的情况，有助于增强网络稳定性。

本文的重点工作是在满足Rendezvous的有效执行、Full Rendezvous的基础上，满足对称模型、非对称模型、时钟同步模型和时钟异步模型，并尽可能降低MTTR。

2 基于发送接收概率SRP算法 2.1 基本思想

CRSN中传感器节点的分为两种状态：发送状态和接收状态，传感器节点分别在发送状态和接收状态下，维护2个信道跳频序列，基于收发概率SRP(sender-receiver-probability)算法(如下的算法1~4)来选择信道。通过调整步长生成循环的逻辑跳频序列，并根据在发送状态和接收状态下相应信道的使用概率Ps_i(x)和Pr_j(y)将逻辑信道映射到对应的物理信道，实现Rendezvous，降低MTTR。

节点根据其当前不同状态分别生成发送状态的和接收状态的逻辑跳频序列，序列长度由P决定，P是不小于信道M的最小质数^[13]，跳频步长L是[0, P-1]的整数，针对节点发送状态和接收状态将进行不同的处理。

1) 节点发送状态

当节点处于发送状态时，算法1用于构造发送方逻辑跳频序列，每P_s个时间片步长L改变一次，由P_s-1递减至0，每个循环将会持续P_s²个时间片长度，前P_s(P_s-1)个时间片用于跳频，最后P_s个时间片将一直停留在逻辑信道1用于补偿，保证在每个循环内至少达到一次Rendezvous。

发送状态逻辑跳频序列进一步通过发送概率控制算法(算法2)映射到对应的物理信道，节点使用物理信道进行实际的通信。首先，传感器节点根据发送状态下各信道使用概率进行排序，并将按照逻辑信道顺序映射到当前发送概率由高到低的物理信道。每当用户在某信道成功达到Rendezvous一次，其对应发送参数Ps_i(x)加1/U_s，U_s是发送状态下信道使用的总次数，其他信道发送参数减1/U_s，反之亦然。当感知信道集中信道最大发送概率大于阈值λ，则将逻辑信道1切换至序号最大的逻辑信道，其余不变，以保证感知信道集中各信道使用概率均衡，增强网络稳定性，达到Full Rendezvous要求。

算法1  发送方逻辑序列构造算法(the sender logic sequence construction)

INPUT：M_s

OUTPUT: channel Cs[i]

P_s=the smallest prime number not less than M_s;

  for L=P_s-1 to 0 do

    for n=0 to P_s-1 do //每P个时间片步长减少一次

      Cs_i=[(t×L)%P_s-L]%P_s+1;

    End

  End

2) 节点接收状态

当节点处于接收状态时，每P_r个时间片步长L改变一次，由0递增至P_r-1，每个循环将会持续P_r²个时间片长度，前P_r个时间片保持现有信道不变，处于等待状态，以增加Rendezvous成功概率，接下来P_r(P_r-1)个时间片用于跳频。生成的接收状态逻辑跳频序列通过接收概率控制(算法4)，根据接收状态下各信道使用概率进行排序，并将按照逻辑信道顺序映射到当前发送概率由高到低的物理信道，进行接收。

算法2  发送方物理信道映射算法(the sender physical channel mapping)

INPUT: Ps_i[x]，Cs_i[x], U_s

//Cs_i[x]是用户i在发送状态下感知信道集合, U_s是CRSN中用户数量

//输入各信道发送状态概率集、逻辑信道序列和信道使用总次数

OUTPUT: sender physical CH list S_i(x)

sort Ps_i[x]

for (x=0;x < P; x++)

   if Ps_i(x)^max≤λ //最大发送概率≤阈值

      S_i(x)← Cs_i[x]//逻辑信道映射到物理信道

      Else

         S_i(max)==S_i(1)

         //将逻辑信道1切换至序号最大信道

      S_i(x) ←Cs_i[x]

         //逻辑信道按概率大小映射到对应物理信道

      Ps_i(x)=Ps_i(x)+1/U_s

         //物理信道发送概率相应增加

      Ps_i(k)=Ps_i(k)-$\frac{1}{{{U_s}}}$；

      //其他信道发送概率相应减少

   END

算法3  接收方逻辑序列构造算法(the receiver logic sequence construction)

INPUT：M_r OUTPUT: channel Cr[i]

P_r=the smallest prime number not less than M_r;

for L=0 to P_r-1 do

   for n=0 to P_r-1 do //P个时间片步长增加一次

      Cr_i=[(t×L)%P_r-L]%P_r+1;

   End

 End

算法4  接收方物理信道映射算法(the receiver physical channel mapping)

INPUT: Pr_j[y], Cr_j[y], U_r

//Cr_j[y]是用户j接收状态下感知信道集合, U_r是接收状态下信道使用的总次数

//各信道接收状态概率集、逻辑信道序列和信道使用总次数

OUTPUT: receiver physical CH list  R_j(y)

sort Pr_j[y]     //排序

for (y=0;y < P; y++)

   if Pr_j(y)^max≤λ//最大接收概率小于等于阈值

      R_j(y)← Cr_j[y] //逻辑信道按概率大小映射到对应物理信道

   Else

   R_j(y)← Cr_j[y]//逻辑信道按概率大小映射到对应物理信道

   Pr_j(y)=Pr_j(y)+1/U_r//物理信道发送概率增加

   R_j(max)=R_j(1)//逻辑信道1切换至序号最大信道

   Other channels Pr_j(k)=Pr_j(k)-1/U_r

End

信道成功达到Rendezvous一次，对应发送参数Pr_j(y)加1/U_r，U_r接收状态下信道使用的总次数，其他信道发送参数减1/U_r，反之亦然。当感知信道集中信道最大发送概率大于阈值λ，则将逻辑信道1切换至序号最大的逻辑信道，其余不变，以保证感知信道集中各信道使用概率均衡，增强网络稳定性，达到Full Rendezvous要求。假设M_S=M_r=3，P_s和P_r均为不小于3的最小质数，即P_s=P_r=3，则发送方和接收方均为每T=9个时间片重复一次。图 1表示根据算法1、算法3生成的发送方和接收方的逻辑调频序列(2 1 3 3 1 2 1 1 1)、(1 1 1 3 1 2 2 1 3)，灰色部分表示在时间片1的位置双方达到Rendezvous。生成的逻辑跳频序列将根据算法2和算法4分别映射到当前所处状态下对应的物理信道，逻辑信道和物理信道对应关系将后续部分进行说明。

2.2 相关证明与分析

本节将分别对SRP算法在对称模型下以及非对称模型下的时钟同步、时钟异步的MTTR和ATTR进行理论分析。

定理1  对于成对节点i，j，有信道x和y，1≤x≤M_s，1≤y≤M_r，节点i与节点j通信过程中，Ps_i(x)表示节点i处于发送状态下信道x的使用概率，Pr_j(y)表示节点j处于接收状态下信道y的概率，Ps_i(x)^max表示节点i处于发送状态下使用概率最大的信道，Pr_j(y)^max表示节点j处于接收状态下使用概率最大的信道。若Ps_i(x)^max=Ps_q，Pr_j(y)^max= Pr_w，则有q=w。

证明  设发送方信道使用概率为Ps_i(1), Ps_i(2), Ps_i(3), …, Ps_i(x), 接收方信道使用概率为Pr_j(1), Pr_j(2), Pr_j(3), …, Pr_j(y)，Ps_i(x)^max=Ps_i(q)，Pr_j(y)^max=Pr_j(w)(q≤x, w≤y)时，q≠w，则发送方与接收方不在同一信道上Rendezvous，不符原则，因此必有q=w。证毕。

对于成对节点，发送概率最大的信道与接收概率最大信道必然相同，同理，发送概率的信道排序与接收概率信道排序必然相等。由此可得，发送方使用概率最大信道与接收方使用概率最大信道相同。

定理2  Cs_i(x_t)表示t时刻发送方逻辑信道，假设发送方逻辑序列为Cs_i(x_t)，Cs_i(x_t+1)，Cs_i(x_t+2), …, Cs_i(x_t+z)(z≥P²)，子序列Cs_i(x_k)，Cs_i(x_k+1)，…, Cs_i(x_k+P+1)(1≤K≤t)必然有Cs_i(x_k+f)=Cs_i(1)(1≤f≤P_s)。

证明  设t=nP_s+1，(0≤n≤P_s-1), 则L=P_s-n+1，可得：Cs_i(x_t)={[(nP_s+1)*(P_s-n-1)] %P_s-(P_s-n-1)}%P_s+1，化简后：Cs_i(x_t)=Cs_i(1)。可得t=1, P_s+1, …, nP_s+1(0≤n≤P_s-1)时均有Cs_i(x_k+f)=Cs_i(1)，因此Cs_i(x_t)，Cs_i(x_t+1)，Cs_i(x_t+2), …, Cs_i(x_t+z)(z≥P²)的子序列Cs_i(x_k)，Cs_i(x_k+1)，…, Cs_i(x_k+P+1)(1≤K≤t)必然有Cs_i(x_k+f)=Cs_i(1)(1≤f≤P_s)。即发送方逻辑序列中任意一段长度为P_s的发送方子序列必然有逻辑信道1。证毕。

结论1  在对称模型下，即M_r=M_s=G_r，s，SRP算法的MTTR≤P_s

证明  当发送方和接收方满足时钟同步模型时，即M_r=M_s=G_r，s，则P_r=P_s。由定理2可知，发送方任意一段长度为P_s的子序列必然有逻辑信道1，根据算法3，接收方第0到P_s时间片内均在信道1等待，因此接收方从任意时间片开始进行跳频，必然在P_s个时间片内与发送方在逻辑信道1上完成Rendezvous，即MTTR≤P_s。

当发送方和接收方满足时钟异步模型时，发送方和接收方开始跳频时间片初始位置不同，同理可得MTTR≤P_s。证毕。

假设在时钟同步模型下，M_r=M_s=G_{r, s}=3，则有P_r=P_s=3，发送方和接收方初始时间片均为0，由算法1和算法3可得发送方和接收方逻辑跳频序列，其MTTR情况如图 2所示。

假设Ps_i(1)=20%，Ps_i(2)=30%，Ps_i(3)=50%，Pr_i(1)=10%，Pr_i(2)=20%，Pr_i(3)=70%，由定理1可知，成对节点发送方和接收方各信道使用概率排序相同，根据算法2和算法4，图 2中生成的对应物理信道如图 3所示，发放和收方在信道3相遇。

结论2  在非对称模型中，即M_r≠M_S≠G_r，s，MTTR≤P_s²

证明  当M_r > M_S, 即P_r > P_S，由定理2可知，发送方逻辑序列中任意一段长度为P_s的子序列必然有逻辑信道1。因此在接收方处于等待阶段的P_r各时间片内一定达到Rendezvous，即MTTR≤P_s²。

当M_r < M_S, 最坏情况为发送方和接收方在同一时间片开始跳频，但为达到Rendezvous，直到发送方补偿处达到Rendezvous，但最坏情况是在发送方补偿的P_s个时间片中的最后一个时间片处达到Rendezvous，即MTTR≤P_s²。

当发送方和接收方满足时钟异步模型时，发送方和接收方开始跳频时间片初始位置不同，同理可得MTTR≤P_s²。证毕。

下面将针对这2种情况分别示例说明：

1) 针对M_r>M_S情况，假设在时钟同步模型下，M_r=5，M_S=3，由此可得P_r=5，P_s=3，发送方和接收方初始时间片均为0，由算法1和算法3可得发送方和接收方逻辑跳频序列，其MTTR情况如图 4所示。

进一步，关于物理信道映射问题，假设Ps_i(1)= 20%，Ps_i(2)=50%，Ps_i(3)=30%，Pr_i(1)=10%，Pr_i(2)=60%，Pr_i(3)=20%，Pr_i(4)=4%，Pr_i(5)= 6%，由定理1可知，成对节点发送方和接收方各信道使用概率排序相同，根据算法2和算法4，图 4中生成的对应物理信道如图 5所示

2) 针对M_r < M_S情况，假设在时钟同步模型下，M_r=3，M_S=5，由此可得P_r=3，P_s=5.，发送方和接收方初始时间片均为0，由算法1和算法3可得发送方和接收方逻辑跳频序列，其MTTR情况如图 6所示。

进一步，关于物理信道映射问题，假设Ps_i(1)= 10%，Ps_i(2)=20%，Ps_i(3)=60%，Ps_i(4)=4%，Ps_i(5)=6%，Pr_i(1)=20%，Pr_i(2)=30%，Pr_i(3)=50%，由定理1可知，成对节点发送方和接收方各信道使用概率排序相同，根据算法2和算法4，图 4中生成的对应物理信道如图 7所示。

由上述例子可知，在对称模型中，最坏情况下MTTR为P_s²，由此可见算法的有效性。

3 实验

为了验证SRP算法的有效性，本文用Matlab 2017实现了该算法，并给出了仿真结果。将SRP算法和最近提出的3种代表性算法，即JS^[9]、ACH^[14]、SR-JW^[15]，进行了比较。在仿真过程中，充分考虑了对称模型和非对称模型下的成对用户场景。对称模型下，每个用户的感知信道集完全相同，非对称模型下，随机生成每个用户的可用信道，并将u表s示为可用信道的比例，即每个用户平均有u×M个可用信道，在非对称模型下u是一个从0.1到1随机生成的十进制数。

为了模拟时钟异步环境，所有用户均随机启动跳频序列。由于JS、AHW、SR-JW均采用的时隙同步技术^[16]，允许多个分组在一个时间片传输，本文将JS^]、AHW的一次时隙同步技术的持续时间设为2T。根据IEEE 802.22，T等于10 ms^[17]。因此，这3种算法中的每一个时隙的持续时间为20 ms。此外，由于SR-JW一个时间片长度为10 ms，采用将SR-JW的一个时间片扩展到2T以建立相同的仿真环境。在不损失通用性的情况下，通过1 000次蒙特卡罗模拟得到了ATTR实验结果的平均值。

对称模型下两用户MTTR和ATTR如图 8(a)图 8(b)所示，由图可知对称模型下SRP算法的MTTR和ATTR均优于JS、ACH算法，远远小于AHW算法。非对称模型下成对用户MTTR和ATTR如图 8(c)、图 8(d)所示，由图可知非对称模型下SRP算法的MTTR和ATTR均较优于ACH算法，远远小于AHW和JS算法。

4 结论

1) 该算法在信道集合对称、非对称模型，时钟同步、异步模型均实现了Rendezvous的有效执行；

2) 通过对比实验分析，SRP算法在信道集对称和非对称模型下的MTTR、ATTR均有明显的优化；

3) 通过引入信道使用概率，有效保证节点感知信道集中每一信道均具有Rendezvous可能性，解决了Rendezvous信道的整体均衡使用问题(Full Rendezvous)，增强了网络的适应性。

综上所述，SRP算法有效解决CRSN中公共控制信道瓶颈问题，对提高动态网络稳定性和传输效率有重要意义。未来我们将对该方法进行进一步讨论，从成对用户扩展到多用户，在多源多跳Rendezvous问题上进一步进行研究，为认知无线传感器网络跨层传输提供新的思路。