CN104994508A - 一种认知无线mesh网络资源分配及路由方法 - Google Patents

Abstract

本发明公开了一种认知无线mesh网络资源分配及路由方法，在认知无线mesh网络中引入缓存机制，产生了多源单目的和单源多目的两种特殊的网络结构，为解决这两种结构下的动态路由和资源分配问题，在控制器中对信道、无线接口、功率和链路资源构建四维冲突图，再从这个冲突图中找出覆盖所有元组的一部分极大独立集，最后利用优化方法解出最大化满足用户的调度方案。

Description

一种认知无线mesh网络资源分配及路由方法

技术领域

本发明属于认知无线电网络领域，特别涉及认知无线mesh网络中对信道、无线接口、发射功率、链路四种资源的动态分配及路由方法。

背景技术

随着无线通信技术的发展，智能手机、平板电脑、智能家居等无线通信设备激增，人们对数据传输速率的要求不断提高，移动通信的数据速率已经从Kb级提升到Mb级，但即使如此也无法满足人们日益增长的带宽需求。与此同时，新的无线通信业务不断涌现，如无线局域网、车辆网络等，而可用频谱几乎分配殆尽，因此，认知无线电技术成了无线网络演进的关键技术。

另外，多媒体内容占Internet流量的比重越来越大，势必造成网络中充斥着大量多媒体内容的传输，而对认知无线电网络来讲，频谱的动态变化并不适宜重复传输大容量的多媒体数据。研究发现(参见文献：K.Wang，Z.Chen and H.Liu，Push-Based Wireless Converged Networks for Massive Multimedia Content Delivery[J]，Wireless Communications，IEEE Transactions on，2014，13(5)：2894-2905)，多媒体内容的请求频率呈现齐普夫定律，即少部分内容被频繁请求，有些内容却很少被请求，根据这一规律，将频繁被请求的内容缓存到认知无线电网络节点将大大降低带宽的需求。目前已经有人开始研究认知无线电网络中的缓存机制(J.Zhao，W.Gao，Y.Wang，G.Cao，Delay-constrained caching in cognitive radio networks[C]，INFOCOM，2014)，由于缓存的存在，会产生请求的数据在多个节点有备份和多个节点请求同样的数据两种特殊情况，这就形成了单源多目的和多源单目的两种特殊的网络结构，在这两种结构下的路由是一个新的挑战，传统的路由方式只适合静态或变化不是太频繁的网络环境，动态地分配资源以满足用户需求是一个急需解决的问题。

与传统网络不同，认知无线mesh网络的频谱是动态变化的，每个认知无线mesh节点的可用信道，可用无线接口，发射功率和路由路径也是随时间变化的，因而传统mesh网络中只对信道构建冲突图的方法并不适用于认知无线mesh网络，并且现有的解决方案都是树形的路由方式，即从源节点到目的节点只有固定一条或两条(另一条备用路径)路径。

发明内容

[发明目的]：本发明为了以动态的方式解决在认知无线电网络中引入了缓存机制后产生的资源分配及路由问题。

[技术方案]：本发明的目的是通过如下措施来达到的：

本发明采用集中式的控制方式，网络中存在一个集中式的控制器，负责收集认知无线 mesh网络中各个认知无线mesh节点的环境信息，这里的环境信息包括可用信道、可用无线接口、可调的发射功率和邻居节点。控制器与认知无线mesh节点之间通过公共控制信道传输信息，这种控制方式可通过无线SDN(软件定义网络)的框架来实现。

本发明重点考虑有多媒体内容缓存的场景，缓存的机制采取了简单的随机缓存，即哪个节点请求该多媒体内容，它就将其缓存，路径中间经过的节点只负责转发，不进行缓存，在控制器中有一个维护各个多媒体内容位置的映射表，在每次收到一组用户请求后(所有用户请求都会通过公共控制信道传给控制器)，首先会为每个请求查找内容映射表，重定向源和目的地址，有些请求可能会有多个源节点，有些请求可能请求的是相同目的节点的内容，需要控制器做出不同的处理。

结合缓存的特性，本发明提供了单源多目的和多源单目的两种网络结构下的资源分配算法。该算法是在控制器中实现的，包括三个相对独立的模块：四维冲突图构建模块、极大独立集生成模块和资源分配模块。

1、四维冲突图构建模块。本模块利用在控制器中得到的全网拓扑图，对每个认知无线mesh节点拥有的无线接口、可用信道、功率等级和链路资源之间的冲突关系用图的结构存储在控制器中，以便其他模块调用，值得注意的是，这个冲突图是实时维护的，当无线环境发生变化时，冲突图也随之变化，具体的构建流程如下：

步骤1：根据控制器中网络拓扑图，对图中每条链路构建信道、功率、链路和无线接口的CPLR四元组，表示为(c，p，(i，j)，(s，t))，其中，认知无线mesh节点i和j形成链路(i，j)，c表示在链路(i，j)上的其中一条可用信道，p表示节点i选定的发射功率等级，s，t分别表示结点i和结点j处的可用无线接口，所有四元组的集合记为T＝{T₁，T₂，...，T_k}；

步骤2：对步骤1产生的四元组判断冲突关系，如果任意两个元组满足下列两个个条件之一，则认为这两个元组不能同时调度，他们之间就会产生一条边：

a)两个元组使用相同的信道，并且其中之一的链路处在另一个的干扰域内，

b)两个元组使用相同的无线接口；

步骤3：根据步骤2的判定关系，建立四维冲突图G(T，L)。

2、极大独立集生成模块。在一个无向图中找一个极大独立集已被证明是NP完全问题，本发明采用找出一部分极大独立集的方法，减少时间复杂度，具体步骤如下：

步骤1：计算最短路径，利用宽度优先搜索算法在全网拓扑图中找出所有用户请求集合中源和目的节点对之间的最短路径，注意到由于宽度优先搜索是不考虑边的权重的，最短路径意味着最小跳数，一对节点间可能存在多条最短路径，本发明将其记为不同的最短路径。冲突图中的每条边会计数经过它的最短路径条数，每增加一条，计数加1，最终每条边都会有一个计数值，记为E＝{E₁，E₂，...，E_n}，其中n为全网拓扑图中链路的数目；

步骤2：将元组降序排列，本发明考虑最短路径、信道容量和功率强度对一个元组(冲突图中的顶点)调度优先顺序的影响，提供了一个索引值ID来度量元组的优先级，例如第i个元组的计算方法为：

${\mathrm{ID}}_i=\mathrm{\α}\·\frac{E_i}{E_{\max }}+\mathrm{\β}\·\frac{b_{\mathrm{xy}}^c}{b_{\max }}+(1-\mathrm{\α}-\mathrm{\β})\·\frac{P_i}{P_{\max }}$

其中，α，β＞0，0＜α+β＜1，是两个指示各部分所占比重的大小，Ei、P_i分别表示i元组中链路计数值、(x，y)链路上c信道的信道容量和发射功率等级的取值，E_max、b_max、P_max分别表示所有元组链路计数值、信道容量和功率等级中的最大值。各个元组的索引值都计算出来后，将其从大到小降序排列；

步骤3：找出最优调度需要的极大独立集，从ID值最大的元组开始，找出与其独立的元组集合，然后按ID值依次找出包含此元组的极大独立集，记为I＝{I₁，I₂，...，I_M}，结束的条件是已找到的极大独立集包含了所有元组；

步骤4：检验积聚干扰条件，在四维冲突图中的干扰条件只是针对链路两两之间的关系，这也是协议干扰模型的不能使人信服的地方，实际网络的干扰是在物理层上检测信噪比的值来确定，为了使算法更符合实际环境，需要对得到的每个极大独立集检查积聚干扰冲突，判断的依据就是信干比SINR是否大于阈值ρ，如果小于ρ则需要将该节点从极大独立集中剔除，SINR的定义如下：

${\mathrm{SINR}}_j=\frac{G_{i,j}{P}_i}{{\mathrm{\Σ}}_{l=1,l\≠j}^m{G}_{i,j}{P}_l+n_j}$

其中有m-1个节点(除了j本身)在同一个信道上同时以功率(P1，…，P1，…Pm)发送数据，只有节点i是结点j的发送者，其余均为干扰，G_i，j表示链路(i，j)的信道增益，n_j表示在节点j处的加性高斯白噪声；

步骤5：循环步骤3和步骤4，直到所有元组都加入到某个极大独立集。

更进一步，步骤3中计算一部分极大独立集，按照如下方法得到：

步骤2.1：初始化覆盖集F＝T，独立集的集合t为按照ID降序顺序选取的元组，S＜t＞中每个独立集都包含元组t；

步骤2.2：在元组降序排列的序列中选取一个元组q，判断其是否有非邻接点，即在冲突图中没有直接边相连，如果没有则把q放入S＜t＞集合中，并将q从覆盖集F＝T/q中删去，否则下一步；

步骤2.3：遍历q的每个非邻接点，如果能加入S＜t＞中，即q与S＜t＞的某个独立集能合成更大的独立集，那么将q加入此独立集，否则下一步；

步骤2.4：将q和t组成新的独立集{q，t}放入S＜t＞中，并将q，t从覆盖集F＝T/{q，t}中删去，执行下一步；

步骤2.5：判断F是否为空，如果不为空执行步骤2.2，否则执行下一步；

步骤2.6：判断得到的S＝{S＜t1＞，S＜t2＞，...，S＜tm＞}中所有独立集是否为极大独立集，如果不是，增加元组使其达到极大，否则结束。

3、资源分配模块。通过合理地调度极大独立集生成模块产生的极大独立集，最大化满足用户的需求，并且尽可能的少占用带，定义f_r(i，j)为请求r经过链路(i，j)的流，具体步骤如下：

步骤1：根据控制器中收到的用户请求，查找内容映射表，对其源和目的地址重定向，如果是多源单目的或单源单目的结构则执行步骤2，如果是单源多目的结构则执行步骤3；

步骤2：多源单目的结构，在此结构下多个源节点分别将请求数据的不同部分传给请求者，本发明采用了构造虚拟源节点的方法(如果是单源单目的，虚拟源节点就是实际源节点)，从虚拟源节点到各个源节点的信道容量不受限制，据此得到了以下形式化表达：

$\begin{array}{cc}\mathrm{Maximize}& \underset{k=1}{\overset{\left|R\right|}{\mathrm{\Σ}}}{\mathrm{\λ}}_r\end{array}$

$\begin{array}{cc}S.t.:& {\mathrm{\Σ}}_{i=\mathrm{VS}\left(r\right),j=S\left(r\right)}{f}_r(i,j)={\mathrm{\λ}}_k{b}_r,\∀r\∈R\end{array}---\left(1\right)$

${\mathrm{\Σ}}_{(i,j)\∈L}{f}_r(i,j)={\mathrm{\Σ}}_{(j,q)\∈L}{f}_r(j,q),\∀r\∈\mathrm{R\; and\; j}\≠\mathrm{VS}\left(r\right),D\left(r\right)---\left(2\right)$

${\mathrm{\Σ}}_{(i,j)\∈L}{f}_r(i,j)\≤b_{\mathrm{ij}},\∀r\∈R---\left(3\right)$

$f_r(i,j)\≥0,\∀r\∈\mathrm{R\; and}(i,j)\∈L---\left(4\right)$

${\mathrm{\Σ}}_{j=\mathrm{VS}\left(r\right)}{f}_r(i,j)=0,\∀r\∈\mathrm{R\; and}(i,j)\∈L---\left(5\right)$

${\mathrm{\Σ}}_{i=D\left(r\right)}{f}_r(i,j)=0,\∀r\∈\mathrm{R\; and}(i,j)\∈L---\left(6\right)$

$0\≤{\mathrm{\λ}}_k\≤1,\∀k\∈(1,|R\left|\right)---\left(7\right)$

${\mathrm{\Σ}}_{m=1}^M{\mathrm{\α}}_m\≤1---\left(8\right)$

$b_{\mathrm{ij}}={\mathrm{\Σ}}_{m=1}^M{\mathrm{\α}}_m{w}_{\mathrm{ij}}^c\left(I_m\right)---\left(9\right)$

其中，约束(1)表明从虚拟节点VS(r)到r的真实源节点S(r)的流量之和为带宽需求与某一百分比λ_k的乘积，这里的百分比表示当网络不能提供足够带宽时，每个实际得到的带宽是请求带宽的百分比，目标函数就是使所有请求的百分比之和最大化，即最大程度满足所有用户。约束(2)表明请求r经过的流除了虚拟源和目的节点外中间节点的入流等于出流，(1)和(2)可以保证到目的节点的带宽之和等于虚拟源节点出来的带宽。约束(3)和(9)表明任何一段链路上的流之和不能超过信道容量，由于极大独立集是分时调度的，每个极大独立集分到的时间比例是α_m，共有M个极大独立集参与请求r的调度，因而平均信道容量为每个极大独立集中信道容量与相应时间比例的乘积的总和。约束(4)(5)(6)(7)(8)表明流的取值为非负，从虚拟源节点入和目的结点出的流都为0，根据以上优化的解就可以得到具体的资源分配和路由方案；

步骤3：单源多目的结构，这种结构就是传统网络中的多播结构，与传统构建多播树的方式不同，本发明采用动态调度策略，且以网络流的形式分配带宽，所以产生的路由拓扑是 图的结构，而非多播树，为了减少带宽的浪费，需要找出多个流共用的链路，例如某一链路由两条请求相同内容的流经过，那么其中部分内容是可以共用的，完全不用重复传输同样的内容，带宽就可以节省下来，据此，本发明设计了如下算法来减少不必要的带宽分配：

步骤3.1：用多源单目的中的优化算法分别计算从源节点到各自目的节点的带宽和资源分配；

步骤3.2：找出所有共用的链路，以分配带宽极大者为参照，按内容比值确定带宽分配。例如有甲乙丙三个请求经过(i，j)链路，带宽需求分别为9Mbp，8Mbps和20Mbps，而在(i，j)链路上分别分配了3Mbp，4Mbps和5Mbps，也就是占带宽需求的1/3，1/2和1/4，以丙为参照(因为丙在此链路上分配的带宽最大)，乙仍需分配的带宽为(1/2-1/4)*8Mbps＝2Mbps，由于丙1/3＜1/2，所以无需分配带宽；

步骤3.3：得到多播路由的带宽分配方案。

根据以上分配方案，可以大大减少带宽的分配，并且路由拓扑是动态分配的图结构而不是多播树，提高了网络的利用率，同时最大化满足了用户的需求。

[有益效果]：本发明的有益效果是：(1)传统网络要优化多种资源形成的是一个NP难问题，解法往往复杂度很高，本发明将冲突图的构建和资源优化划分为独立维护的模块，并行执行，在空间上对一个复杂的问题进行了分解，更适合实际系统中运行；(2)本发明考虑在认知无线mesh网络中引入缓存机制，更加适应动态变化的环境，减少了用户请求时间；(3)优化方法得到的资源分配方案是分时调度的方案，给不同的极大独立集分配了不同长度的时间片，提升了资源的利用率。

附图说明

图1为实际场景中无线mesh节点资源分布举例；

图2为针对实际场景构建的四维冲突图；

图3为多源单目的网络结构；

图4为单源多目的网络结构。

具体实施方式

以下结合附图和具体实例对本发明做具体的介绍。

网络建立起来后，控制器中四维冲突图构建模块就开始工作，如图3所示，网络中有的三个节点，节点A有一条可用信道c₁，可调功率为L₁、L₂两个等级，无线接口仅有一个h₁；节点B有两条可用信道c₁、c₂，可调功率为L₁，有两个无线接口h₁、h₂；节点C有两条可用信道c₁、c₂，可调功率为L₁，也仅有一个无线接口h₁。图中有三条链路(A，C)、(B，A)、(B，C)，其中(A，C)虚线表示只有节点A的发射功率为较大值L₂时才能与节点C通信。根据这些信息，控制器中会构建四维的拓扑图：

步骤1：根据控制器中网络拓扑图，对图中每条链路构建信道、功率、链路和无线接口的CPLR四元组，根据图3可构建7个CPLR元组，分别(c₁，L₁，(B，A)，(h₁，h₁))、(c₁，L₁，(B，C)，(h₁，h₁))、(c₁，L₂，(A，C)，(h₁，h₁))、(c₁，L₁，(B，C)，(h₂，h₁))、(c₁，L₁，(B，A)，(h₂，h₁))、(c₂，L₁，(B，C)，(h₁，h₁))、(c₂，L₁，(B，C)，(h₂，h₁))，从左往右分别记为T₁，T₂，...，T₇；

步骤2：对步骤1产生的四元组判断冲突关系，如果任意两个元组满足下列两个个条件之一，则认为这两个元组不能同时调度，他们之间就会产生一条边：

a)两个元组使用相同的信道，并且其中之一的链路处在另一个的干扰域内，

b)两个元组使用相同的无线接口；

根据以上两个条件，可以找出T₁和T₇，T₅和T₆是没有冲突的。

步骤3：根据步骤2的判定关系，建立四维冲突图G(T，L)，如图4所示，除了T₁和T₇，T₅和T₆，其余节点间均两两相连。

得到了四维冲突图后，接下来就要找出这个冲突图中的极大独立集，计算步骤如下：

步骤1：计算最短路径，利用宽度优先搜索算法在全网拓扑图中找出所有用户请求集合中源和目的节点对之间的最短路径，如果控制器收到请求B→A和A→C，由于案例中拓扑很小，最短路径就是(B，A)和(A，C)，因而每条链路的计数值为E_BA＝1，E_AC＝1，E_BC＝0；

步骤2：将元组降序排列，假设图3中的L1＝5dBm，L2＝10dBm，信道容量 比例系数α＝0.5，β＝0.3，根据步骤1可得E₁＝1，E₂＝0，E₃＝1，E₄＝0，E₅＝1，E₆＝0，E₇＝0，由此可计算案例中各个元组的索引值为ID₁＝0.73，ID₂＝0.25，ID₃＝0.84，ID₄＝0.25，ID₅＝0.73，ID₆＝0.23，ID₇＝0.23。所以排序的结果为T₃→T₁→T₅→T₂→T₄→T₆→T₇，这里将ID值相等的元组按元组编号先后排序；

步骤3：找出最优调度需要的极大独立集，从ID值最大的元组开始，找出与其独立的元组集合，然后按ID值依次找出包含此元组的极大独立集，结束的条件是已找到的极大独立集包含了所有元组，详细步骤如下：

步骤2.1：初始化覆盖集F＝{T₁，T₂，...，T₇}，独立集的集合t为按照ID降序顺序选取的元组，S＜t＞中每个独立集都包含元组t；

步骤2.2：在元组降序排列的序列中选取一个元组T₃，其没有非邻接点，即在冲突图中S＜T₃＞＝{{T₃}}，F＝{T₁，T₂，，T₄，T₅，T₆，T₇}，取下一个元组T₁，其有非邻接点T₇，执行下一步；

步骤2.3：遍历T₁的每个非邻接点，因为此时S＜T₁＞为空，所以下一步；

步骤2.4：将T₁和T₇组成新的独立集{T₁，T₇}放入S＜T₁＞＝{{T₁，T₇}}，F＝{T₂，，T₄，T₅，T₆}；

步骤2.5：判断F不为空，执行步骤2.2，选取元组T₅，其存在非邻接点T₆，将{T₅，T₆} 放入S＜T₅＞＝{{T₅，T₆}}，F＝{T₂，，T₄}，F仍不为0，继续取元组T₂，其没有非邻接点，放入S＜T₂＞＝{{T₂}}，F＝{T₄}，继续取元组T₄，也没有非邻接点，放入S＜T₄＞＝{{T₄}}，F为空，下一步；

步骤2.6：得到的S＜T₃＞＝{{T₃}}，S＜T₁＞＝{{T₁，T₇}}，S＜T₅＞＝{{T₅，T₆}}，S＜T₂＞＝{{T₂}}都为极大独立集，结束；

步骤4：检验积聚干扰条件，经检验，上诉最大独立集中没有同信道的元组，因而一定满足条件；

步骤5：循环步骤3和步骤4，直到所有元组都加入到某个极大独立集。

从得到的极大独立集可以看出，只有T₁和T₇，T₅和T₆可以同时调度，其物理意义为节点B用h₁与节点A通信，同时用h₂与节点C通信，另一种情况是，节点B用h₂与节点A通信，同时用h₁与节点C通信。

由于本发明重点考虑的是缓存影响下的多源单目的和单源多目的两种路由模式，控制器在一个调度周期内收到一组用户请求，查找内容分布映射表，对它们的源和目的地址进行重定向，根据源和目的地址情况确定资源分配方法(如果为单播，直接用多源单目的中的优化方法)。

如图3所示，为多源单目的结构，构建一个逻辑上的虚拟源节点，虚拟源节点的下一跳为各个真实源节点，且这些链路信道容量不受限，据此得到了类似单播的模型，然后根据以下优化方法求得资源分配解决方案。

$\begin{array}{cc}\mathrm{Maximize}& \underset{k=1}{\overset{\left|R\right|}{\mathrm{\Σ}}}{\mathrm{\λ}}_r\end{array}$

$\begin{array}{cc}S.t.:& {\mathrm{\Σ}}_{i=\mathrm{VS}\left(r\right),j=S\left(r\right)}{f}_r(i,j)={\mathrm{\λ}}_k{b}_r,\∀r\∈R\end{array}---\left(1\right)$

${\mathrm{\Σ}}_{(i,j)\∈L}{f}_r(i,j)={\mathrm{\Σ}}_{(j,q)\∈L}{f}_r(j,q),\∀r\∈\mathrm{R\; and\; j}\≠\mathrm{VS}\left(r\right),D\left(r\right)---\left(2\right)$

${\mathrm{\Σ}}_{(i,j)\∈L}{f}_r(i,j)\≤b_{\mathrm{ij}},\∀r\∈R---\left(3\right)$

$f_r(i,j)\≥0,\∀r\∈\mathrm{R\; and}(i,j)\∈L---\left(4\right)$

${\mathrm{\Σ}}_{j=\mathrm{VS}\left(r\right)}{f}_r(i,j)=0,\∀r\∈\mathrm{R\; and}(i,j)\∈L---\left(5\right)$

${\mathrm{\Σ}}_{i=D\left(r\right)}{f}_r(i,j)=0,\∀r\∈\mathrm{R\; and}(i,j)\∈L---\left(6\right)$

$0\≤{\mathrm{\λ}}_k\≤1,\∀k\∈(1,|R\left|\right)---\left(7\right)$

${\mathrm{\Σ}}_{m=1}^M{\mathrm{\α}}_m\≤1---\left(8\right)$

$b_{\mathrm{ij}}={\mathrm{\Σ}}_{m=1}^M{\mathrm{\α}}_m{w}_{\mathrm{ij}}^c\left(I_m\right)---\left(9\right)$

如图4所示为单源多目的结构，图中D1、D2、D3向S请求相同的内容，带宽需求分别为9Mbp、8Mbps和20Mbps，第一步是分别用多源单目的中的优化方法计算出S到D1、D2、D3的路径，其中(A，B)是三者共同经过的，分别分配了3Mbp、4Mbps和5Mbps，也就是占 带宽需求的1/3、1/2和1/4，D3在此链路上分配的带宽最大，因此它的速率必须保证，而D2、D3的内容已经有D1提前传输到B节点了，因此D2仍需分配的带宽为(1/2-1/4)*8Mbps＝2Mbps，而由于D3的内容已经全部由速率更快的D2帮其传输了(1/3＜1/2)，所以无需分配带宽。按照这样的计算方法，把全部共用链路找出，并重新分配，能减少大量带宽分配。

Claims (6)

1.一种认知无线mesh网络资源分配及路由方法，其特征在于，在认知无线mesh网络中引入缓存机制后产生了多源单目的和单源多目的两种特殊结构，用集中式控制的方式提供了三个相对独立的模块：四维冲突图构建模块、极大独立集生成模块和资源分配模块，最大化满足了用户需求。

2.根据权利要求1所述的认知无线mesh网络资源分配及路由方法，其特征在于，四维冲突图构建步骤为：

步骤1：根据控制器中网络拓扑图，对图中每条链路构建信道、功率、链路和无线接口的CPLR四元组，表示为(c，p，(i，j)，(s，t))，其中，认知无线mesh节点i和j形成链路(i，j)，c表示在链路(i，j)上的其中一条可用信道，p表示节点i选定的发射功率等级，s，t分别表示结点i和结点j处的可用无线接口，所有四元组的集合记为T＝{T₁，T₂，...，T_k}；

步骤2：对步骤1产生的四元组判断冲突关系，如果任意两个元组满足下列两个个条件之一，则认为这两个元组不能同时调度，他们之间就会产生一条边：a)两个元组使用相同的信道，并且其中之一的链路处在另一个的干扰域内，b)两个元组使用相同的无线接口；

步骤3：根据步骤2的判定关系，建立四维冲突图G(T，L)。

3.根据权利要求1所述的认知无线mesh网络资源分配及路由方法，其特征在于，极大独立集生成模块的步骤为：

步骤1：计算最短路径，利用宽度优先搜索算法在全网拓扑图中找出所有用户请求集合中源和目的节点对之间的最短路径，注意到由于宽度优先搜索是不考虑边的权重的，最短路径意味着最小跳数，一对节点间可能存在多条最短路径，本发明将其记为不同的最短路径。冲突图中的每条边会计数经过它的最短路径条数，每增加一条，计数加1，最终每条边都会有一个计数值，记为E＝{E₁，E₂，...，E_n}，其中n为全网拓扑图中链路的数目；

步骤2：将元组降序排列，本发明考虑最短路径、信道容量和功率强度对一个元组(冲突图中的顶点)调度优先顺序的影响，提供了一个索引值ID来度量元组的优先级，例如第i个元组的计算方法为：

${\mathrm{ID}}_i=\mathrm{\α}\·\frac{E_i}{E_{\max }}+\mathrm{\β}\·\frac{b_{\mathrm{xy}}^c}{b_{\max }}+(1-\mathrm{\α}-\mathrm{\β})\·\frac{P_i}{P_{\max }}$

其中，α，β＞0，0＜α+β＜1，是两个指示各部分所占比重的大小，E_i、P_i分别表示i元组中链路计数值、(x，y)链路上c信道的信道容量和发射功率等级的取值，E_max、b_max、P_max分别表示所有元组链路计数值、信道容量和功率等级中的最大值。各个元组的索引值都计算出来后，将其从大到小降序排列；

步骤3：找出最优调度需要的极大独立集，从ID值最大的元组开始，找出与其独立的元组集合，然后按ID值依次找出包含此元组的极大独立集，记为I＝{I₁，I₂，...，I_M}，结束的条件是已找到的极大独立集包含了所有元组；

步骤4：检验积聚干扰条件，在四维冲突图中的干扰条件只是针对链路两两之间的关系，这也是协议干扰模型的不能使人信服的地方，实际网络的干扰是在物理层上检测信噪比的值来确定，为了使算法更符合实际环境，需要对得到的每个极大独立集检查积聚干扰冲突，判断的依据就是信干比SINR是否大于阈值ρ，如果小于ρ则需要将该节点从极大独立集中剔除，SINR的定义如下：

${\mathrm{SINR}}_j=\frac{G_{i,j}{P}_i}{{\mathrm{\Σ}}_{l=1,l\≠j}^m{G}_{i,j}{P}_l+n_j}$

其中有m-1个节点(除了j本身)在同一个信道上同时以功率(P1，…，P1，…Pm)发送数据，只有节点i是结点j的发送者，其余均为干扰，G_i，j表示链路(i，j)的信道增益，n_j表示在节点j处的加性高斯白噪声；

步骤5：循环步骤3和步骤4，直到所有元组都加入到某个极大独立集。

4.根据权利要求3所述的极大独立集生成方法，其特征在于，所述步骤3计算方法为：

步骤2.1：初始化覆盖集F＝T，独立集的集合t为按照ID降序顺序选取的元组，S<t>中每个独立集都包含元组t；

步骤2.2：在元组降序排列的序列中选取一个元组q，判断其是否有非邻接点，即在冲突图中没有直接边相连，如果没有则把q放入S<t>集合中，并将q从覆盖集F＝T/q中删去，否则下一步；

步骤2.3：遍历q的每个非邻接点，如果能加入S<t>中，即q与S<t>的某个独立集能合成更大的独立集，那么将q加入此独立集，否则下一步；

步骤2.4：将q和t组成新的独立集{q，t}放入S<t>中，并将q，t从覆盖集F＝T/{q，t}中删去，执行下一步；

步骤2.5：判断F是否为空，如果不为空执行步骤2.2，否则执行下一步；

步骤2.6：判断得到的S＝{S<t1>，S<t2>，...，S<tm>}中所有独立集是否为极大独立集，如果不是，增加元组使其达到极大，否则结束。

5.根据权利要求1所述的认知无线mesh网络资源分配及路由方法，其特征在于，多源单目的结构中带宽和资源分配优化方法为：

步骤1：根据控制器中收到的用户请求，查找内容映射表，对其源和目的地址重定向，如果是多源单目的或单源单目的结构则执行步骤2，如果是单源多目的结构则执行步骤3；

步骤2：多源单目的结构，在此结构下多个源节点分别将请求数据的不同部分传给请求者，本发明采用了构造虚拟源节点的方法(如果是单源单目的，虚拟源节点就是实际源节点)，从虚拟源节点到各个源节点的信道容量不受限制，据此得到了以下形式化表达：

$\begin{array}{cc}\mathrm{Maximize}& \underset{k=1}{\overset{\left|R\right|}{\mathrm{\&Sigma;}}}{\mathrm{\&lambda;}}_r\end{array}$

$S.t.:{\mathrm{\&Sigma;}}_{i=\mathrm{VS}\left(r\right),j=S\left(r\right)}{f}_r(i,j)={\mathrm{\&lambda;}}_k{b}_r,\&ForAll;r\&Element;R---\left(1\right)$

${\mathrm{\&Sigma;}}_{(i,j)\&Element;L}{f}_r(i,j)={\mathrm{\&Sigma;}}_{(i,q)\&Element;L}{f}_r(j,q),\&ForAll;r\&Element;\mathrm{Randj}\&NotEqual;\mathrm{VS}\left(r\right),D\left(r\right)---\left(2\right)$

${\mathrm{\&Sigma;}}_{(i,j)\&Element;L}{f}_r(i,j)\&le;b_{\mathrm{ij}},\&ForAll;r\&Element;R---\left(3\right)$

$f_r(i,j)\&GreaterEqual;0,\&ForAll;r\&Element;\mathrm{Rand}(i,j)\&Element;L---\left(4\right)$

${\mathrm{\&Sigma;}}_{j=\mathrm{VS}\left(r\right)}{f}_r(i,j)=0,\&ForAll;r\&Element;\mathrm{Rand}(i,j)\&Element;L---\left(5\right)$

${\mathrm{\&Sigma;}}_{i=D\left(r\right)}{f}_r(i,j)=0,\&ForAll;r\&Element;\mathrm{Rand}(i,j)\&Element;L---\left(6\right)$

$0\&le;{\mathrm{\&lambda;}}_k\&le;1,\&ForAll;k\&Element;(1,|R\left|\right)---\left(7\right)$

${\mathrm{\&Sigma;}}_{m=1}^M{\mathrm{\&alpha;}}_m\&le;1---\left(8\right)$

$b_{\mathrm{ij}}={\mathrm{\&Sigma;}}_{m=1}^M{\mathrm{\&alpha;}}_m{w}_{\mathrm{ij}}^c\left(I_m\right)---\left(9\right)$

其中，约束(1)表明从虚拟节点VS(r)到r的真实源节点S(r)的流量之和为带宽需求与某一百分比λ_k的乘积，这里的百分比表示当网络不能提供足够带宽时，每个实际得到的带宽是请求带宽的百分比，目标函数就是使所有请求的百分比之和最大化，即最大程度满足所有用户。约束(2)表明请求r经过的流除了虚拟源和目的节点外中间节点的入流等于出流，(1)和(2)可以保证到目的节点的带宽之和等于虚拟源节点出来的带宽。约束(3)和(9)表明任何一段链路上的流之和不能超过信道容量，由于极大独立集是分时调度的，每个极大独立集分到的时间比例是α_m，共有M个极大独立集参与请求r的调度，因而平均信道容量为每个极大独立集中信道容量与相应时间比例的乘积的总和。约束(4)(5)(6)(7)(8)表明流的取值为非负，从虚拟源节点入和目的结点出的流都为0，根据以上优化的解就可以得到具体的资源分配和路由方案；

步骤3：单源多目的结构资源分配和路由方案。

6.根据权利要求5所述的单源多目的结构资源分配及路由方法，其特征在于，所述步骤3方法为：

步骤3.1：用多源单目的中的优化算法分别计算从源节点到各自目的节点的带宽和资源分配；

步骤3.2：找出所有共用的链路，以分配带宽最大者为参照，按内容比值确定带宽分配。

步骤3.3：得到多播路由的带宽分配方案。