Distributed Consensus Cooperative Spectrum Sensing Method Based on Connected-Dominating-Set

认知无线电协作共识频谱感知分为两个阶段。第一阶段，次用户进行数据测量，次用户i的测量数据表示为Y_i。第二阶段，各次用户与邻居用户建立通信链路并进行信息交互，根据获得的数据计算各自的本地结果，此处理过程通过反复迭代进行。在起始时刻k=0，每个次用户i设置x_i(0)=Y_i作为本地状态变量的初始值。在时刻k=0, 1, 2, …, 根据实时网络拓扑，次用户邻居间交互它们的状态x(k)，各次用户计算并生成状态更新值x(k+1)，迭代重复执行直到所有个体的状态x(k)收敛到定值x^*。

在第一阶段，次用户在每一个时隙的开始测量主用户数据，这里主用户的先验知识未知。图 1为能量检测模块图。为方便采用能量检测频谱感知方法^[10]，使信号输入中心频率为f_s、带宽为W的带通滤波器，再通过求平方器件，然后关于时间区间T求积分。积分器输出Y是次用户接收到的能量，其分布情况依赖于主用户信号是否存在。频谱感知的目的就是在两个假设$ {\mathit{\mathcal{H}}_0} $和$ {\mathit{\mathcal{H}}_1} $间进行判决：

式中，x(t)是次用户接收到的信号；s(t)是主用户传输的信号；n(t)是加性高斯白噪声；h是信道的振幅增益。定义SNR为γ，积分器的输出Y作为判决统计量^[10]：

式中，χ_2TW²和χ_2TW²(2γ)分别代表中心和偏心卡方分布的随机数，各自具有2TW维自由度，后者的偏心参数为2γ。为了简化，假设时间带宽积TW为整数，用m表示。

在瑞利衰落信道条件下，增益h是随机量，SNR值γ服从指数分布。在此条件下，输出Y的分布依赖于SNR平均值γ。当主用户不存在时，Y依然服从χ_2TW²分布；当主用户出现时，Y可以表示为两个独立随机变量和的形式^[11]：

式中，Y_x服从χ_2TW²分布；Y_e是参数为2(γ+1) 的指数分布。经过T秒后，每个次用户i进行能量检测并得到测量数据$ {Y_i} \in {{\rm{\mathbb{R}}}^ + } $。

在第二阶段，次用户与邻居建立通信链路进行信息交互。为简化，次用户组成的网络可以表示成无向图G=(N, ℑ)^[12]，由节点集合N={i=1, 2, …, n}和边集合ℑ⊂N×N构成。每个边表示为无向对(i, j)，两节点单步连接。图G中的路径由节点序列$ {i_1}, {i_2}, \cdots, {i_l}(l \ge 2) $构成，那么$ ({i_m}, {i_{m + 1}}) \in \Im $对于所有1≤m≤l-1均成立。图G中任两个节点通过路径连通，称图G是连通图，本文所述的图指连通图。若$ (i, j) \in \Im $且i≠j，表示次用户j(节点j)和次用户i(节点i)是邻居。节点i的邻居表示为$ {N_i} = \{ j|(j, i) \in \Im \} \subset N $。N_i集合的节点数为|N_i|，称为节点i的度。

考虑协作频谱感知问题为共识问题，在达到共识以前次用户交互各自检测的输出结果信息。对于图G模型中的n个节点，对应分配状态变量x_i(i∈N)。x_i为共识变量，它本质上代表节点i的能量检测值。当它逐渐趋于稳定时，x_i收敛到共识固定值x^*，即：

式中，k=0, 1, 2, …是离散时间；而x_i(k)是节点i在k时刻的状态，它是由k-1时刻节点i和它的邻居状态值计算获得的状态更新值。协作频谱感知采用平均共识$ {x^ * } = {\rm{Ave}}(x) = (1/n)\sum\limits_{i = 1}^n {{x_i}(0)} $。

1) 对于固定连通网络模型，网络拓扑不发生改变的情况

对于节点i，在k=0时，测量值Y_i表示为$ {x_i}(0) = {Y_i} \in {{\rm{\mathbb{R}}}^ + } $。各节点在离散时刻k=0, 1, 2, …的状态更新表示为^[3]：

其中，

式中，∆表示网络的最大自由度。最终分布式协作达成共识会收敛到值x^*。最后通过比较共识值x^*和预先定义的门限值λ，各节点i实现判决：

2) 对于随机网络模型，网络拓扑发生随机改变的情况

设图G=(N, ℑ)表示无链路错误情况下的最大通信链路集。考虑到随机链路错误，在时刻k用图$ G(k) = (N{\rm{, }}\Im (k)) \subseteq G $来描述随机网络。当k时刻节点j和i连通，则边$ (j, i) \in \Im (k) $，其中$ (j, i) \in \Im $。图G各链路错误相互独立，错误概率p∈(0, 1)，k时刻节点i的邻居$ {N_i}(k) = \{ j|(j, i) \in \Im (k)\} $，邻居节点数为|H_i|(k)=∅。随机网络中，每个节点按照如下规则进行状态更新：

式中，如果N_i(k)=∅，则$ {x_i}(k + 1) = {x_i}(k) $。当k→∞时，最终分布式协作达成共识，以概率1收敛到x^*[3]。

分布式协作共识虽然能够达到一致收敛，但没有借助拓扑结构提升共识速度。实际上可以采用全网络节点分布式协作，并在连通支配集上快速形成稳定共识，然后将结果分享给其他非支配集节点来提升网络共识状态的收敛速度，且最终一致收敛结果不变。

连通支配集由连通的支配节点构成，网络所有节点要么在当前连通支配集中，要么是连通支配集的邻居节点^[9]。如图 2所示，12个节点随机分布于长宽各为1的正方形区域，节点间的边用连线表示，图中黑色方块是连通支配集节点{6, 8, 9, 10, 11, 12}。连通支配集经过单步可以到达网络中的任意节点，故网络信息通过它可以高效传递。因此将文献[3]的方法与连通支配集相结合，可以借助网络拓扑结构，达到快速达成共识的效果。对于包含链路误差的随机网络模型，文献[9]提出了相应的更新和重算措施。

设$ G'{\rm{ = (}}N{\rm{', }}\Im '{\rm{)}} $为网络G的连通支配集，其节点集合$ N' \subset N $，边集合$ \Im ' \subset \Im $。支配集中节点i的邻居$ {N'_i} = \{ j|(j, i) \in \Im '\} \subset N' $。由于通过支配集G'及其邻居节点可以覆盖全网络，所以支配集状态收敛速度比整个网络状态收敛速度快。由于支配集先于网络收敛到稳定值，可以将支配集状态收敛的结果分享给网络邻居节点，各个节点再按式(7) 进行判决，进而完成网络分布协作频谱感知。

定理 1  无向连通图$ G{\rm{ = (}}N{\rm{, }}\Im {\rm{)}} $固定网络，采用式(5) 进行分布式协作状态更新，当k→∞时，对于任何初始状态$ {x_i}(0)(i \in N) $，最终各个节点逐渐达成共识，以概率1收敛到稳定状态值x^*。

证明：图G的拉普拉斯矩阵为$ \mathit{\boldsymbol{L}} = {({l_{i, j}})_{n \times n}} $，其中：

式(9) 表示矩阵L为半正定。进而，式(5) 的矢量形式为：

式中，P=I-εL。设P第i行j列的元素为p_{i, j}，x_i(k)是x(k)的第i行元素，易知ε的取值确保P是双随机矩阵(即其各行、各列值的和为1)，且各主对角线元素p_{i, i}＞0。

式(10) 描述了一个齐次马尔可夫链模型，P为网络各节点状态的一步转移概率矩阵。一步转移概率p_{i, j}只与节点i, j, k有关，与时刻k无关。设图G中节点i, j, k构成一个路径，且$ (i, j) \in \Im $，$ (j, k) \in \Im $，$ (i, k) \notin \Im $，即节点i通过节点j与节点k相连。则$ 0 < {p_{i, i}}, {p_{i, j}}, {p_{j, j}}, {p_{j, k}} < 1 $且p_{i, i}=0。容易得到二步状态转移为：

式中，P⁽²⁾代表二步转移概率矩阵，其第i行j列元素为：

另：

由于P各行、各列和为1，故对于P⁽²⁾各行、各列求和也为1，如下：

同时根据$ 0 < {p_{i, i}}, {p_{i, j}}, {p_{j, j}}, {p_{j, k}} < 1 $，参照式(14) 可推知n＞1步转移概率为：

且如果节点k与节点最短路径为l步，则$ {p_{i, k}}^{(l)} > 0 $。如果网络节点间最长的最短路径为l'步，则转移概率矩阵P^(l')的所有元素都大于0，同时P^(l')各行、各列值求和为1。由此可知，矩阵P^(l')符合马尔可夫链遍历定理要求，存在极限分布：

由无向图G可知P是对称矩阵，故而k步转移概率矩阵P(k)也是对称矩阵，且各行、各列和为1。因此可以推出$ {p_1} = {p_2} = \cdots = {p_n} = 1/n $，有：

不同于文献[3]中的算法，这里各节点按照连通支配集分享的收敛值进行判决，进而有效地利用拓扑资源提升算法性能。连通支配集收敛值作为全网络的收敛值分享给周围非支配集的邻居节点，最后根据式(7) 进行判决。

随机网络节点间的链路$ (i, j) \in \Im $以概率p∈(0, 1) 失败，各个链路相互独立。k时刻的随机网络图表示为$ G(k) = (N{\rm{, }}\Im (k)) $。图G(k)的支配集为$ G{\rm{'}}(k) = {\rm{(}}N{\rm{'}}(k){\rm{, }}\Im {\rm{'}}(k){\rm{)}} $，其中N'(k)和$ \Im {\rm{'}}(k) $分别为支配集的节点集合和边集合，文献[9]介绍了支配集节点的更新和重新计算过程。

定理 2  无向随机连通图$ G(k) = (N{\rm{, }}\Im (k)) $，节点间链路$ (i, j) \in \Im $以概率p∈(0, 1) 失败，各个链路相互独立，用式(8) 进行分布式协作状态更新。当k→∞时，对初始状态$ {x_i}(0)(i \in N) $，最终各节点达成共识，以概率1收敛到稳定状态值x^*。

证明：随机图G(k)的拉普拉斯随机矩阵$ \mathit{\boldsymbol{L}}(k) = {({l_{i, j}}(k))_{n \times n}} $，其中：

由式(19) 可知矩阵L(k)是半正定的随机矩阵。进而，式(8) 的矢量的形式为：

式中，$ \mathit{\boldsymbol{P}}(k) = \mathit{\boldsymbol{I}} - \varepsilon \mathit{\boldsymbol{L}}(k) $，设p_{i, j}(k)表示P(k)第i行j列元素，x_i(k)是x(k)的第i行元素。易知ε的取值确保了P(k)是双随机矩阵形式的随机过程(即其各行、各列和为1)；且保证了其主对角线元素p_{i, j}(k)＞0。

由于图G各节点间链路失败与否是独立同分布的，所以P(k)是一个随机过程。进而体现随机链路连接情况的P(k)统计特性不随时间改变而改变，所以P(k)是严平稳随机过程。P(k)在各个时刻的期望相等，可表示为双随机常数矩阵$ {\mathit{\boldsymbol{P}}_\mu }{\rm{ = E[}}\mathit{\boldsymbol{P}}(k)] $。P(k)的各元素p_{i, j}(k)的期望为：

且P(k)在各时刻k=1, 2, …时独立同分布，根据大数定律，当k→∞时，P(k)的时间平均以概率1等于统计平均P_μ，即P(k)的均值具有各态历经性。

由此可知，当k→∞时，随机图G(k)的平均一步转移概率P(k)为P_μ以概率1成立。进而当k→∞时，随机图G(k)的状态转移可以表示成固定图G以一步转移概率P_μ进行状态转移的齐次马尔可夫链。参照定理1不难得出，此马尔可夫链是遍历的，结合P_μ的双随机性，各个节点逐渐达成共识，以概率1收敛到稳定状态值x^*。这说明当k→∞时，随机图G(k)逐步到达状态x^*以概率1成立，也即证明了可达性。再参照式(17) 所示其各个元素值$ {p_1} = {p_2} = \cdots = {p_n} = 1/n $，并结合一步转移概率P(k)的双随机性，可知此状态值x^*不再随P(k)的变化而发生改变，即证明了稳定性。因此，当k→∞时各节点以概率1收敛到状态值x^*。

按照固定无向网络模型类似的方法，随机支配集G'(k)其状态更新收敛速度会比整个网络收敛速度快，提前收敛到x^*。因此，这里用支配集G'(k)收敛值x^*分享给周围非支配集的邻居节点，网络各节点再参照式(7) 进行判决。

假设所有次用户处于独立同分布、空间不相关的瑞利衰落信道环境。当主用户存在时，次用户的能量检测器输出Y服从卡方分布；当主用户不在时，次用户的能量检测器输出Y为两个独立随机变量的和，如式(3)。假设次用户接收的信号SNR平均值γ均为3 dB，实验中直接构造数据Y。每个次用户在选定的中心频率f_s和带宽W下，以时间带宽积TW为检测本地能量值Y_i。设初始能量矢量X(0)，其中X(0) 的第i行元素x_i(0)。设$ \varepsilon = 1/\Delta - 0.01 $，支配集中含有4个节点。固定无向网络实验结果如图 3所示。由图可见分布式计算结果最终收敛到x^*，全网络收敛迭代需要接近20次，而支配集节点不到10次，支配集收敛速度更快。图 4为随机无向网络实验收敛情况，节点间连接关系失败概率p=0.2，$ \varepsilon = 1/\Delta - 0.01 $，图 4b支配集中含有3个节点。可知随机网络分布式计算结果最终收敛到x^*，全网络收敛迭代需要25次左右，而支配集节点只需约15次，支配集收敛速度明显快于全网络收敛速度。支配集的计算量相当于一轮协作共识的计算时间。因为支配集不仅为当前分布共识算法服务，它可作为网络的一个基本配置，为其他算法和功能服务。所以获取支配集付出的运算量可以不考虑。因此新方法收敛速度明显快于全网络节点收敛速度，信息交互量更少、运算时间明显降低，能够以更好的实时性、更低的能耗达到原算法相同的检测性能。

本文研究了无向网络中无中心分布式共识策略认知无线电频谱感知方法，对固定网络和随机网络中分布式感知收敛性进行了全新的推证，并将原有算法与支配集特性结合，利用支配集收敛结果能够更快获得收敛值，可将收敛分享给其他非支配集节点实现各个节点的判决。支配集与分布式算法结合使用体现了拓扑未知的分布式算法向拓扑可知分布式计算的过渡和迈进，这使得分布式算法与网络实际拓扑能够更好的匹配，算法性能得到更好的优化。当采用支配集与分布式结合的算法后，网络中其他节点通过支配集节点连接传输网络节点采集的信息，同时节点可以分享支配集的共识结果；另外因为支配集与其邻居节点覆盖了整个网络所有节点，所以可以避免信息的冗余传输、信道的资源浪费，同时可以节约能耗、提升信息的传递效率和分布式计算的收敛速度。