一种CWMN中基于动态规划的分布式路由方法

摘要

本发明公开一种认知无线Mesh网络中分布式的路由与频谱分配方法，其目标是构造的路径具有高可靠度、低端到端延迟。主要包括如下步骤：1、计算所有CR-Mesh节点的状态信息，以及其可用信道的效用值；2、计算CR-Mesh网关节点到所有CR-Mesh路由器和终端节点的层次；3、计算所有CR-Mesh节点的父亲节点和儿子节点的集合；4、计算所有节点与其儿子节点之间的无线链路预分配某信道之后的权值；5、基于动态规划分布式的构建从源点到目的节点的高可靠、低延迟的路由路径，6、给构造的路由路径中的所有无线链路分配信道。应用本发明，解决了认知无线Mesh网络中以高可靠、低延迟为目标的分布式路由路径构建与频谱分配问题，能达到降低端到端延迟和提高路径稳定度的目的。

主权项

认知无线Mesh网络中以高可靠与低延迟为目标基于DP的分布式路由路径构造与频谱分配方法，其特征在于，包括以下步骤：步骤1：计算所有CR‑Mesh节点的状态信息，以及其可用信道的效用值，步骤2：计算CR‑Mesh网关节点到所有CR‑Mesh路由器节点和CR‑Mesh终端节点的层次，步骤3：计算所有CR‑Mesh节点的父亲节点的集合和儿子节点的集合，步骤4：计算所有节点与其儿子节点之间的无线链路预分配某信道之后的权值，步骤5：基于动态规划(Dynamic Programming,DP)策略采用分布式方式构建从源点到目的节点的高可靠、低延迟的路由路径，步骤6：给构造的路由路径中的所有无线链路分配信道，步骤1中计算所有CR‑Mesh节点的状态信息，以及其可用信道的效用值的步骤为：S1‑1所有CR‑Mesh节点对其感知的信道集合K_i，计算其所有可用信道的使用特性，包括信道的使用概率P^k(v_i)和稳定度S^k(v_i)，即计算使用概率P^k(v_i)的计算原理是：P^k(v_i)表示节点v_i感知的信道k被授权PU使用的概率，节点v_i从t₁＝1开始统计信道k是否被授权PU使用，每次使用固定检测时间周期T，α^k(t_j)＝1表示信道k被授权PU使用，α^k(t_j)＝0表示信道k没有被授权PU使用，w表示到目前为止，节点v_i已经检测了w个时间周期，表示w个时间周期中，信道k被授权PU使用的次数；稳定度S^k(v_i)的计算原理是：S^k(v_i)表示节点v_i感知的信道k由“空闲”状态变成“使用”状态的次数占总检测时间周期的比例，ε^k(t_j,t_j+1)表示信道k从t_j到t_j+1，是否由α^k(t_j)＝0变成α^k(t_j+1)＝1，即信道k是否由“空闲”状态变成“使用” 状态，ε^k(t_j,t_j+1)＝1表示信道k由“空闲”状态变成“使用”状态，其他情况，由“空闲”变“空闲”状态，“使用”变“空闲”状态，“使用”变“使用”状态，都记ε^k(t_j,t_j+1)＝0，其中(令α^k(t₀)＝0)，β^k(t_w)表示t_w个检测时间周期中信道k由“空闲”状态变成“使用”状态的总次数，S1‑2所有节点通过公共控制通道(CCC)向其相邻节点发送感知的可用信道集合K_i，以及各可用信道使用特性值，包括信道的使用概率P^k(v_i)和稳定度S^k(v_i)，即发送K_i，以及发送一个三元组Sat^k＝(k,P^k(v_i),S^k(v_i))，其中，v_i节点的相邻节点表示v_i通信距离范围之内的节点，不同于ⅳ)中求解的v_i的邻居节点，S1‑3所有节点计算其与相邻节点的相同可用信道集合，以及各相同可用信道的使用特性，K(v_i,v_j)表示节点v_i和节点v_j相同可用信道集合，即节点v_i和节点v_j相同可用信道k的使用概率Pn^k(v_i,v_j)，和相同可用信道k的稳定度Sn^k(v_i,v_j)，分别取节点v_i和节点v_j的使用概率P^k(v_i)和P^k(v_j)的最大值，和稳定度S^k(v_i)和S^k(v_j)的最小值，即Pn^k(v_i,v_j)＝Max{P^k(v_i),P^k(v_j)}，Sn^k(v_i,v_j)＝Min{S^k(v_i),S^k(v_i)}，S1‑4所有节点计算其邻居节点集合N(v_i)，即N(v_i)＝{v_j|v_j∈V&&d(v_i,v_j)≤T_R&&K(v_i,v_j)≠φ}，其中d(v_i,v_j)≤T_R表示节点v_i和节点v_j之间的物理距离小于通信距离，K(v_i,v_j)≠φ表示节点v_i和节点v_j之间至少存在一个相同的可用信道，步骤2中计算CR‑Mesh网关节点到所有CR‑Mesh路由器节点和CR‑Mesh终端节点的层次的步骤为：对于CR‑Mesh网关、路由器和终端节点，其处理流程是不一样的，下面分别说明其包含的步骤：CR‑Mesh网关节点，其处理流程如下：S2‑1对所有CR‑Mesh网关节点L(g_j,g_j)＝0，表示所有的网关节点都设置为0层；S2‑2对所有CR‑Mesh网关节点通过公共控制通道(CCC)广播一个消息BCM(g_i,level)，其中level＝0表示网关g_j的层为0；CR‑Mesh路由器节点，其处理流程如下：S3‑1对所有CR‑Mesh路由器节点初始化L(g_j,v_i)，L(g_j,v_i)表示相对于网关g_j来说，节点v_i所处的层次，初始化所有网关节点到节点v_i的层次为无穷大，即L(g_j,v_i)＝∞，S3‑2对所有CR‑Mesh路由器节点当收到一个BCM(g_j,level)的消息时，判断L(g_j,v_i)是否大于level+1，如果L(g_j,v_i)>level+1，则L(g_j,v_i)＝level+1，否则，不改变L(g_j,v_i)；S3‑3对所有CR‑Mesh路由器节点广播一个消息BCM(g_j,level)，其中level＝L(g_j,v_i)；CR‑Mesh终端节点，其处理流程如下：S4‑1对所有CR‑Mesh终端节点初始化L(g_j,v_i)，L(g_j,v_i)表示相对于网关g_j来说，节点v_i所处的层次，初始化所有网关节点到节点v_i的层次为无穷大，即L(g_j,v_i)＝∞，S4‑2对所有CR‑Mesh终端节点当收到一个BCM(g_j,level)的消息时，判断L(g_j,v_i)是否大于level+1，如果L(g_j,v_i)>level+1，则L(g_j,v_i)＝level+1，否则，不改变L(g_j,v_i)；步骤3中计算所有CR‑Mesh节点的父亲节点的集合和儿子节点的集合的步骤为：S5‑1对所有CR‑Mesh节点针对每个网关节点使用公 共控制通道(CCC)广播一个消息BLM(g_j,v_i,level)给其所有的邻居节点集合N(v_i)中的所有节点，共广播|VG|个BLM(g_j,v_i,level)消息，g_j∈VG，消息BLM(g_j,v_i,level)表示从网关节点g_j到节点v_i的层次为level，其中level＝L(g_j,v_i)，为之前计算的相对于网关g_j来说，节点v_i所处的层次；S5‑2对所有CR‑Mesh节点当收到一个BLM(g_j,v_i,level)消息时，比较L(g_j,v_q)与BLM消息中的level值之间的关系，如果L(g_j,v_q)＝level‑1，则pre(g_j,v_q)＝pre(g_j,v_q)∪v_i，pre(g_j,v_q)表示相对于网关g_j来说，节点v_q的父亲节点集合，如果L(g_j,v_q)＝level+1，则chi(g_j,v_q)＝chi(g_j,v_q)∪v_i，chh(g_j,v_q)表示相对于网关g_j来说，节点v_q的儿子节点集合；步骤4中计算所有节点与其儿子节点之间的无线链路预分配某信道之后的权值的过程为：对所有CR‑Mesh节点计算无线链路(v_i,v_q)预分配信道k之后的权值f^k(v_i,v_q)，其中v_q是v_i相对于网关节点来说，v_i节点的儿子节点，即v_q∈chi(g_j,v_i)，由于f^k(v_i,v_q)的值与网关节点g_j无关，因此f^k(v_i,v_q)的计算公式中不予标明网关节点，f^k(v_i,v_q)的计算公式为：其中，Pn^k(v_i,v_j)与Sn^k(v_i,v_j)分别表示节点v_i和节点v_j之间相同可用信道k的使用概率和稳定度，Dy^k表示信道k的延迟，表示当前网络环境中，所有信道的最大延迟，Dy^k除以的目的是为了将延迟归一化，权值函数f^k(v_i,v_q)包含了高的路径可靠度，低的端到端延迟的目标，表示可靠度，表示延迟，由于f^k(v_i,v_q)的值越小越好，因此在f^k(v_i,v_q) 中，对可靠度取倒数，对无线业务构造的路由路径，要想获得高可靠度、低延迟的路由路径,需要尽量使得路径经过的每一条无线链路具有高可靠度、低的端到端延迟，步骤5中基于动态规划(Dynamic Programming,DP)策略采用分布式方式构建从源点到目的节点的高可靠、低延迟的路由路径的步骤为：ζ_p＝(g_p,c_p)为无线业务，其中g_p表示CR‑Mesh网关节点，即为源点，c_p表示CR‑Mesh终端节点，即为目的节点，对于CR‑Mesh网关、路由器和终端节点，其工作流程是不一样的，下面分别说明其包含的步骤：CR‑Mesh终端节点，其处理流程如下：S6‑1计算终端节点c_p到自己使用信道k的路径最小权值总和，即dp^*(c_p,c_p,k)，其计算公式为：dp^*(c_p,c_p,k)＝0S6‑2对终端节点c_p的每一个父亲节点构造并发送一个PCM(g_p,c_p,v_i,c_p)消息，含义是：当网关节点是g_p，终端节点是c_p的情况下，终端节点c_p发送给v_i的控制消息，其中PCM(g_p,c_p,v_i,c_p).Dy表示c_p到c_p的路径最小权值总和，PCM(g_p,c_p,v_i,c_p).Ch表示c_p到其儿子节点所使用的信道，PCM(g_p,c_p,v_i,c_p).Cn表示dp^*(c_p,c_p,k)取最小值时，与v_i相连的儿子节点，其值分别是：PCM(g_p,c_p,v_i,c_p).Dy＝0，表示最小权值总和为0，PCM(g_p,c_p,v_i,c_p).Ch＝0，由于c_p没有儿子节点，即表示没有给其分配信道，PCM(g_p,c_p,v_i,c_p).Cn＝φ，表示c_p节点没有儿子节点；CR‑Mesh路由器节点，其处理流程如下：S7‑1当路由器节点v_i接收到其儿子节点v_j的PCM(g_p,v_j,v_i,c_p)消息的时候，对节点v_i的每一个可用信道计算节点v_i与其儿子节点v_j之间的无线链路分配信道k的情况下，路由器节点v_i到终端节点c_p的路径最小权值总和，即dp^*(v_i,c_p,k)，其计算公式为：其中，f^k(v_i,v_j)表示无线链路预分配信道k之 后的权值，表示相对于网关g_p，v_i的所有儿子节点，dp^*(v_j,c_p,k')表示v_j到c_p的最小权值总和，其中k'表示v_j到其儿子节点使用的信道，即k'＝PCM(g_p,v_j,v_i,c_p).Ch，的含义为：对于寻找最小的f^k(v_i,v_j)+dp^*(v_j,c_p,k')值；S7‑2对路由器节点v_i的每一个可用信道计算dp^*(v_i,c_p,k)取最小值时v_i的儿子节点以及与其儿子节点使用信道k'^*，其计算公式为：S7‑3对路由器节点v_i的每一个可用信道保存一个三元组CNV(ch,nd,ch')，其中ch表示信道，nd表示计算dp^*(v_i,c_p,k)取最小值时v_i的儿子节点，ch'表示nd节点到其儿子节点使用的信道，ch＝k，ch'＝k'^*；S7‑4对路由器节点v_i的每一个可用信道构造一个PCM(g_p,v_i,v_q,c_p)消息，给v_i的每一个父亲节点发送一个PCM(g_p,v_i,v_q,c_p)消息，PCM(g_p,v_i,v_q,c_p)的含义是：当网关节点是g_p，终端节点是c_p的情况下，节点v_i发送给v_q的控制消息，其中PCM(g_p,v_i,v_q,c_p).Dy表示v_i到c_p的路径权值总和，PCM(g_p,v_i,v_q,c_p).Ch表示v_i到其儿子节点所使用的信道，PCM(g_p,v_i,v_q,c_p).Cn表示dp^*(v_i,c_p,k)取最小值时，与v_i相连的儿子节点，其值分别是：表示v_i经过其儿子节点到终端节点是c_p的权值总和，PCM(g_p,v_i,v_q,c_p).Ch＝k，表示v_i与其儿子节点之间的无线链路分配的信道，表示dp^*(v_i,c_p,k)取最小值时，与v_i相连的儿子节点；CR‑Mesh网关节点，其处理流程如下：S8‑1当网关节点g_p接收到其儿子节点v_i的PCM(g_p,v_i,g_p,c_p)消息的时候，网关节点g_p计算其到终端节点c_p的路径最小权值总和，即dp(g_p,c_p)，其计算公式为：其中，f^k(g_p,v_i)表示无线链路预分配信道k之后的权值，表示相对于网关g_p，g_p的所有儿子节点，dp^*(v_i,c_p,k')表示v_i到其儿子节点使用信道k'的情况下，v_i到c_p的路径权值总和，式(5)的含义为：对于寻找最小的f^k(g_p,v_i)+dp^*(v_i,c_p,k')值；S8‑2计算dp(g_p,c_p)的路径中与g_p相连接的节点无线链路分配的信道以及与其儿子节点使用信道k'^*，其计算公式为：其中，表示dp(g_p,c_p)取得最小值时选择的g_p的儿子节点，k^*表示dp(g_p,c_p)取得最小值时无线链路选择使用的信道，k'^*表示dp(g_p,c_p)取得最小值时，到其儿子节点使用信道，arg Min(dp(g_p,c_p))表示计算dp(g_p,c_p)取得最小值时选择的g_p的儿子节点，以及g_p与儿子节点之间使用的信道，步骤6中给构造的路由路径中的所有无线链路分配信道的步骤为：S9‑1网关节点g_p根据公式获得取得最优值的儿子节点g_p与其儿子节点使用的信道k^*，以及到其儿子节点使用信道，即S9‑2网关节点g_p给节点儿子节点发送一个控制消息其中表示到其儿子节点使用信道，其中S9‑3路由器节点v_i收到其父亲节点v_q∈pre(g_p,v_i)的CCM(v_q,v_i)消息之后，在本地的三元组CNV(ch,nd,ch')中寻找与消息中的CCM(v_q,v_i).Ch相等的三元组， 即CNV(ch^*,nd^*,ch'^*)＝arg 1{CCM(v_q,v_i).Ch＝＝CNV(ch,nd,ch').ch}；S9‑4节点v_i到其儿子节点nd^*之间的无线链路分配信道ch^*，即x(ζ_p,v_i,nd^*)＝ch^*，路由器节点v_i给其儿子节点nd^*发送一个控制消息CCM(v_i,nd^*)，其中CCM(v_i,nd^*).Ch表示nd^*到其儿子节点使用信道，CCM(v_i,nd^*).Ch＝ch'^*。