一种认知无线Mesh网络中的组播路由及频谱分配方法

摘要

本发明公开一种认知无线Mesh中的组播路由及频谱分配方法，首先将静止的CR-Mesh路由器组成的认知无线Mesh网络建模为一个无向多重图，然后采取遗传算法求取路径延迟的最大值最小的信道分配方案，包括初始化；基于最短路径算法计算个体适应度函数值；执行选择、交叉和变异操作；产生下一代种群；达到遗传代数，输出最优解决方案多个步骤。应用本发明，解决了认知无线Mesh网络中单源节点的组播路由及频谱分配问题，并且可以实现源节点到所有组播目的节点的路径延迟的最大值最小，有效提高网络性能。

主权项

1.一种认知无线Mesh网络中的组播路由及频谱分配方法，其特征在于，首先将静止的CR-Mesh路由器组成的认知无线Mesh网络建模为一个无向多重图G=(V,E,D)，其中V表示CR-Mesh路由器的集合，E表示链接两个能相互通信的CR-Mesh路由器的无线链路的集合，D表示两个CR-Mesh路由器节点间无线链路的传输延迟的集合，d_i表示某一信道i的传输延迟，每个节点v_i∈V都有一个感知的可用信道集合K_i，所有节点采用半双工方式工作；K={1,2,...k}={1,2,3,4,5,6}表示总的可用信道的集合，Ψ_i,j表示节点v_i和节点v_j相同的可用信道集合，S表示组播源节点，R={r₁,r₂,...r_m}表示组播目的节点集合；G'=(V',E',D')表示由G导出的简单连通图，其中，V'=V，G'中任意两个节点只具有一条可用无线链路；T=(V_T,E_T)表示组播树，P_T(S,r_i)表示组播树T中一条从S到某一目的节点r_i的路径，d_L表示组播树T中无线链路L上的延迟，Delay(P_T(S,r_i))表示组播树T中从源节点S到目的节点r_i的路径延迟，即然后采取遗传算法求取路径延迟的最大值最小的信道分配方案，GEN表示遗传代数，步骤如下：1）初始化遗传代数计数器g=0；2）初始化种群，首先设定染色体的编码表示方式，使用长度为n的7进制串表示一个染色体，代表着一个信道分配方案，其中n=|E'|=23，E'表示图G导出的简单连通图G'的边数，给组播树T中n条边从1到n进行编号，编码表示为X=x₁x₂…x_n，x_i∈{0}∪K，i∈{1,2,…,n}，在染色体中，如果x_i=0，表示组播树中编号为i的边没有分配任何信道，该条边表示的无线链路上的延迟将为无穷大，如果x_i=k，k∈K，则说明编号为i的边分配的信道为k；种群中的染色体总数为N，种群中染色体j表示为C_j=c₁(j)c₂(j)…c_n(j)，c_i(j)∈{0}∪K，i∈{1,2,…,n}，j∈{1,2,…,N}，初始化种群包含如下步骤：ⅰ）初始化染色体计数器j=0；ⅱ）染色体C_j初始化为空，j∈{1,2,…,N}；ⅲ）初始化染色体C_j的边计数器i=0；ⅳ）初始化染色体C_j的c_i(j)边的信道，设定染色体C_j的第i条边连接的两个节点为v_a和v_b，则初始化c_i(j)为属于Ψ_a,b集合中任一个值，如果Ψ_a,b=Φ，则c_i(j)=0，即连接节点v_a和v_b的第i条边不分配任何信道；ⅴ）边计数器加1，表示初始化下一条边分配的信道；ⅵ）判断i与n的大小，确定是否已经初始化所有的边，若是，转步骤ⅶ；否则，转步骤ⅳ；ⅶ）染色体计数器加1，表示初始化下一个染色体；ⅷ）判断j与N的大小，确定是否已经初始化所有的染色体，若是，结束；否则，转步骤ⅱ；3)基于最短路径算法计算个体适应度值即适应度函数值：基于最短路径算法求解源节点S到目的节点集合R的组播树，无线链路的延迟记为边的权值，求源节点S到目的节点集合R中所有目的节点的最短路径，源节点S到组播树中所有目的节点的路径延迟的最大值的倒数作为适应度函数的值；染色体C_j基于最短路径算法求得的对应的组播树记为T(j)，组播树T(j)中所有到目的节点的路径延迟的最大值记为：$\mathrm{MD}\left(C_j\right)=\underset{r_i\in R}{\mathrm{Max}}\left\{\mathrm{Delay}\left(P_{T\left(j\right)}(S,r_i)\right)\right\}j\in \{1,2,...N\};$染色体C_j的适应度函数值计算公式为：F(C_j)=1/MD(C_j)；4）选择操作：根据步骤3）中适应度函数计算出的染色体的适应值，采用择优策略，将个体适应度值最高的个体直接保留到子代种群中，再根据各染色体的个体适应度值，按下式计算出相对适应值：其中，p(C_j)为该染色体的选择概率，F(C_j)表示染色体j的个体适应度值，N为群体规模，群体规模数即染色体数；5）交叉操作：ⅰ）随机选择两个染色体C_i和C_j；ⅱ）判断两个染色体C_i和C_j是否不同，若是，则转步骤ⅲ，否则，转步骤ⅰ；ⅲ）随机选择一个中间节点v_a作为交叉点，v_a为一个到达组播目的节点集合中所有目的节点必经的中间节点v_a；ⅳ）组播目的节点计数器k=0；ⅴ）将染色体C_i中到达目的节点r_k的子路径与染色体C_j中到达目的节点r_k的子路径交叉；ⅵ）目的节点计数器k加1，交叉到达下一个目的节点的子路径；ⅶ）判断是否已经操作完到达所有目的节点的路径，若是，结束，否则，转步骤ⅴ；6）变异操作：ⅰ）随机选择染色体C_j进行变异操作；ⅱ）随机选择染色体C_j中的第i条边进行变异操作；ⅲ）对第i条边随机产生一个新的信道NewC，信道NewC必须是与第i条边连接的两个节点v_a和v_b都具有的信道；ⅳ）判断NewC是否与c_i(j)不等，若是，结束，否则，转步骤ⅱ；7）产生下一代种群；8）遗传代数计数器加1，进行下一代的遗传操作；9）判断遗传代数是否大于GEN，若是，转步骤10，否则，转步骤3；10）输出最优方案：将具有最大适应度值的染色体作为最优方案，在该染色体中，从源节点到所有目的节点的路径延迟的最大值比其他染色体中从源节点到所有目的节点的路径延迟的最大值小。