1.一种面向应急通信的WMN网关部署与信道分配联合优化方法,其特征在于:包括如下步骤,步骤一:进行网络全覆盖式的网关部署并生成转发树;
步骤二:寻找所述转发树中各个链路的链路干扰范围,获得链路干扰集;
步骤三:根据所述转发树,计算链路所承受负载流量;
步骤四:根据链路的干扰集合和链路所承受负载流量,获得各个链路的冲突量,依据各个链路的冲突量,获得网络总链路冲突量;
步骤五:建立网络总链路冲突量数学模型,采用差分进化算法从所述数学模型中得到网络总链路冲突量最小化的信道分配方式;
步骤一中,所述转发树的生成包括如下步骤:
a1):初始化网络场景、网络节点、通信半径RT和节点路径长度,所述节点路径长度即为普通路由节点到网关节点之间的通信跳数R;
a2):随机选择候选节点作为网关并标记;
a3):根据候选节点N、通信半径RT以及通信跳数R的参数约束,通过贪心算法对节点进行扫描;
a4):选择在候选节点N通信跳数R跳范围内的邻居节点作为下一个候选节点添加入转发树并进行标记;
a5):设置运行次数,所述运行次数至少为1次,根据设置运行次数重复步骤a1)至a4),从中选择具有最小网关节点数量的拓扑图。
2.根据权利要求1所述的面向应急通信的WMN网关部署与信道分配联合优化方法,其特征在于:步骤二中,所述链路干扰集为在任意链路的冲突域范围内使用相同信道的干扰链路集合;所述链路干扰集的获取方法包括如下步骤:b1):将网络拓扑图用N*N的二维矩阵A表示,并设定N1(e(i,j),e(u,v))表示链路e(i,j)与链路e(u,v)为相邻关系,N2表示过渡矩阵以及N3(e(i,j),e(u,v))表示链路e(i,j)与链路e(u,v)是两条不相同的链路且链路e(i,j)与链路e(u,v)这两条链路经过两跳相邻的节点;
所述二维矩阵A的数学表示,
其中,vi,vj为网络节点,d(vi,vj)为vi,vj两个网络节点之间的距离;
所述N1(e(i,j),e(u,v))的数学表示为:所述N3(e(i,j),e(u,v))的数学表示为:N3=N2×N2;
b2):根据定N1(e(i,j),e(u,v))和N3(e(i,j),e(u,v))定义链路冲突域CDu,v,CDu,v={e(i,j)|e(i,j)∈Eand N1(e(i,j),e(u,v))=1andN3(e(i,j),e(u,v))=1} (4)b3):将链路冲突域CDu,v内分配了相同信道的链路作为集合构成链路干扰集,设定 表示链路(u,v)之间分配了相同信道c的干扰链路集合,则链路干扰集的数学表示为:其中,u,v,i,j表示网络节点的编号,c为信道, 表示链路(i,j)之间分配了相同的信道c。
3.根据权利要求1所述的面向应急通信的WMN网关部署与信道分配联合优化方法,其特征在于:步骤三中,链路所承受负载流量的计算为根据所述转发树和各个链路自身所携带负载量,得到各个链路上所承受负载流量,所述各个链路自身所携带负载量满足WMN中流量的聚集性,所述WMN中流量的聚集性为各个链路上所承受负载量包括自身产生的负载和所转发负载之和。
4.根据权利要求2所述的面向应急通信的WMN网关部署与信道分配联合优化方法,其特征在于:步骤四中所述链路冲突量为:在链路冲突域范围内,两条并发传输的链路上每条链路中的流量负载对链路之间相互干扰的程度,所述网络总链路冲突量为各个链路冲突量的总和;设定链路冲突量为 网络总链路冲突量为 则:其中, 表示链路(i,j)之间分配相同信道c的干扰链路集合,ti.j表示链路(i,j)上的负载流量,CDu,v为链路冲突域。
5.根据权利要求4所述的面向应急通信的WMN网关部署与信道分配联合优化方法,其特征在于:步骤五中,所述网络总链路冲突量数学模型为混合整数非线性问题模型,在所述数学模型中设定优化目标为约束条件为:
其中,
yi,j表示节点vi是否是节点vj的父节点;ai,j表示节点vi与节点vj之间是否存在链路;xj为网关节点; 为中间变量,表示节点vu的流量是否经过链路(vi,vj); 表示链路ei,j是否分配了相同的信道c;K是网络中可用正交信道的总数,M是每个路由节点上可用无线接口的数量,并且M≤K;R为通信跳数;C表示负载量;
公式(9)表示节点vi选择节点vj为网关的前提条件是两节点之间必须存在链路;
公式(10)表示非网关节点只能和一个网关节点相连;
公式(11)确保所有普通路由节点与网关节点之间的通信跳数不超过上限;
公式(12)确保每个节点vj同时分配的信道数不能小于该节点配置的射频端口数量的限制;
公式(13)保证了任意链路最多只能分配一个信道;
公式(14)表示了每个节点所能承受的负载流量不能超过其负载量C;
公式(15)为任意特定数据流(s,d)通过信道c流经链路(m,n),须满足的流量守恒定律;
公式(16)为决策变量。
6.根据权利要求5所述的面向应急通信的WMN网关部署与信道分配联合优化方法,其特征在于:步骤五中,采用差分进化算法从所述数学模型中得到网络总链路冲突量最小化的信道分配方式包括如下步骤:c1):初始化算法参数,所述算法参数包括网络参数、种群规模和迭代数;
c2):选择满足全覆盖网关节点,根据链路冲突域和链路所承受负载对链路进行信道编码;
c3):生成初始化种群作为算法寻优的起始个体;
c4):采用自适应变异策略对个体进行变异操作;
c5):针对变异个体进行越界修复;
c6):保留c5)中的变异个体作为后代进行交叉操作;
c7):根据概率选择合适个体进行下一代进化
c8):判断算法是否满足收敛,若不满足则更新种群并转入c4),若满足,则转入c9);
c9):得到所述优化目标 的优化方式,并进行网关部署和信道分配。
7.根据权利要求6所述的面向应急通信的WMN网关部署与信道分配联合优化方法,其特征在于:步骤c2)中的信道编码采用以网络节点为索引,以十进制整数矩阵形式的基因结构为编码方式建立网络连接与信道编码之间的映射,所述信道编码为种群混合编码,所述种群混合编码包括混合流量负载和信道分配。
8.根据权利要求6所述的面向应急通信的WMN网关部署与信道分配联合优化方法,其特征在于:步骤c4)中的变异策略采用DE/best/2算子进行变异,变异规则为:其中,F=1and r1,r2,r3,r4∈{1,2,..,NP},best≠r1≠r2≠r3≠r4,为每一代的随机个体,Xbest为当代最优个体,F为缩略因子,Vi为变异之后的新个体。
9.根据权利要求8所述的面向应急通信的WMN网关部署与信道分配联合优化方法,其特征在于:步骤c6)中所述交叉采用的策略为步骤c7)中概率选择采用的策略为 其中,CR表示交叉操作中被用来交叉序列的选取范围,Ui是下一代的个体,f(Ui)是下一代个体适应度值,Xi是当代个体,f(Xi)表是当代个体的适应度值。