一种基于遗传算法的无线传感网多目标优化路由方法

摘要

一种基于遗传算法的无线传感网多目标优化路由方法，该方法利用基站的存储空间充裕、能量充足和计算能力强的优势，采用全局搜索无线多媒体传感器网络多路径多目标优化路由的策略，在基于前向邻居概念的网络模型和多目标优化函数的基础上，设计特定的编码方案及选择、交叉、变异算子。本发明结构简单，引入了遗传算法和Pareto多目优化方法，设计特定的编码方案及选择、交叉、变异算子，最终实现优化求解，在全局范围内搜索WMSNs多路径多目标优化路由，提高了方法稳定性，在多路径多目标优化上可行、有效。

主权项

一种基于遗传算法的无线传感网多目标优化路由方法，其特征在于，包括以下步骤：(1)随机生成网络拓扑，初始化参数；基站收集网络初始信息，得到网络的各个节点的前向邻居矩阵A、可靠性性矩阵Re、时延矩阵De、能量矩阵E、时延抖动矩阵Jit和带宽矩阵SNR；(2)根据前向邻居矩阵A找源节点的代理源节点集NB和数目length_NB,初始化最优路径解集MM_Path＝Φ；初始化i＝1；(3)如果i≤length_NB,则执行(4),否则执行(13)；(4)置StartN＝NN(i)，生成父代种群father和子代种群child；置Counter＝1，初始化bestPath＝Φ；用节点ID号表示染色体中的基因，则一个染色体是由source节点到sink节点的路径上的节点ID号序列组成；每条染色体的第一个基因为source节点ID号，最后一个基因为sink节点ID号；每相邻的两个基因为WMSNs一条实际存在可相互通信的链路；假设网络的节点个数为n，source节点ID号为k＝1，sink节点ID号m＝n，则对应的染色体可表示为一个有序序列:＜1…i…j…n＞,1＜i,j＜n且i≠j；(5)如果Counter<λ，则执行(6)，否则执行Stepll，λ为迭代次数；(6)将种群father和child合群为farm，对farm的每个个体计算其适应度值，求Pareto最优解集，对最优解集i约束，得到本次迭代最优解集并保存在bestPath中；(7)对本代最优解集之外的个体解码、计算其适应度值，按照个体的适应度升序排列，根据排序号计算选择概率，计算轮盘赌选择区域，按轮盘赌选择方法选择个体；多路径多目标优化函数构造适应度函数为：${\mathrm{fit}}_i=\frac{1+d_{\max }-{\mathrm{del}}_i}{1+d_{\max }-d_{\min }}+\frac{1+{\mathrm{rel}}_i-r_{\max }}{1+r_{\max }-r_{\min }}+\frac{1+e_{\max }-e_i}{1+e_{\max }-e_{\min }}+\frac{1+{\mathrm{snr}}_i-s_{\min }}{1+s_{\max }-s_{\min }}+\frac{1+j_{\max }-{\mathrm{jit}}_i}{1+j_{\max }-j_{\min }}$其中，del_i、rel_i、e_i、snr_i、jit_i分别表示种群中第i个个体的网络时延、可靠性、剩余能量、传输速率、时延抖动大小；d_max和d_min分别表示种群中第i个个体的网络时延的最大值和最小值；r_max和r_min分别表示种群中第i个个体的可靠性的最大值和最小值；e_max和e_min分别表示种群中第i个个体的剩余能量的最大值和最小值；s_max和s_min分别表示种群中第i个个体的传输速率的最大值和最小值；j_max和j_min分别表示种群中第i个个体的时延抖动大小的最大值和最小值；根据个体是否满足时延约束和可靠性约束的情况，对其适应度值给以适当的奖惩，时延和可靠性的奖惩函数分别构造为:${\mathrm{qd}}_i=\frac{{(-1)}^k({\mathrm{del}}_i-dc)}{{(-1)}^k+{\mathrm{del}}_i-dc},\left\{\begin{array}{c}{\mathrm{del}}_i-dc\le 0,k=1;\\ {\mathrm{del}}_i-dc>0,k=2;\end{array}\right.{\mathrm{qr}}_i=\frac{{(-1)}^k({\mathrm{rel}}_i-rc)}{{(-1)}^k+{\mathrm{rel}}_i-rc},\left\{\begin{array}{c}{\mathrm{rel}}_i-rc\le 0,k=1;\\ {\mathrm{rel}}_i-rc>0,k=2;\end{array}\right.$其中dc,rc分别为时延和可靠性的约束值，如果满足约束，则qd_i和qr_i值为正，个体的适应值得到奖励，否则qd_i和qr_i值为负，个体的适应值得到惩罚；综上所述，可得个体适应度计算函数Fit(i):Fit(i)＝fit_i+qd_i+qr_i；(8)将最优解集和根据轮盘赌选择出种群初始规模大小的个体作为新一代种群f，保存副本为父代father；采用按个体适应度轮盘赌方法和Pareto Front两种选择方法相结合的选择策略；首先对每一代父种群和子种群采用Pareto Front选择多目标最优解集，将其保存在最优解集中，并选择其为下一代种群的部分个体；通过使用Pareto Front在父代、规模为2N的子代种群选择出来的最优解数小于初始化种群的规模N，通过设计选择概率函数和使用轮盘赌方法选择个体并补充到下一代中，以保证种群规模不变；在轮盘赌选择法中各个个体的选择概率和其适应度值成比例；设群体大小为n，其中个体i的适应度为f(i)，则个体i被选择的概率如公式所示；首先将种群中的个体按照个体的适应值升序排序，记录每个个体的排序号；然后将个体的排序号作为其适应值，即Fit(i)＝i，i为个体排序号；按照公式将选择概率转换为轮盘赌随机选择区域；(9)种群f根据交叉概率和变异概率分别进行单点交叉和变异生成新一代种群，保存副本记为child；(9.1)根据个体和种群的适应度设计交叉概率，用$P_c=\left\{\begin{array}{c}{p}_{c1},0.5(fi{t}_i+fi{t}_j)\le fi{t}_{over}\\ p_{c1}-\frac{(p_{c1}-p_{c2})\left(0.5\right({\mathrm{fit}}_i+{\mathrm{fit}}_j)-{\mathrm{fit}}_{over})}{{\mathrm{fit}}_{max}-{\mathrm{fit}}_{over}},others\end{array}\right.$表示；其中，p_c1和p_c2为常数且0＜p_c2＜p_c1＜1，fit_i和fit_j分别为随机选中的进行交叉的两个个体的适应度值，fit_over为当前种群的平均适应度值，fit_max为当前种群的最大个体适应度值；(9.2)生成新的链路，具体过程如下:a)随机产生一个变异基因位i作为变异点，除了i位之外，其它的基因位保持不变(i≠1且i≠n)；b)第i位基因变异为v_i‑1的前向邻居节点和v_i+1的后向邻居节点的交集中的某一节点，即第i位基因变异的范围为C＝F_i‑1∩B_i+1；如果C＝φ，则第i位基因不发生变异，否则按照变异概率P_m在集合C中随机选择某一元素进行替换；变异概率P_m表示为：$P_m=\{\begin{array}{c}{p}_{m1},fi{t}_i\le fi{t}_{over}\\ p_{m1}-\frac{(p_{m1}-p_{m2})({\mathrm{fit}}_i-{\mathrm{fit}}_{over})}{{\mathrm{fit}}_{max}-{\mathrm{fit}}_{over}}\end{array},others;$其中，p_m1和p_m2为常数，且0＜p_m2＜p_m1＜1，fit_i、fit_over和fit_max表示的意义同(9.1)；(10)设Counter'＝Counter+1，执行(5)；(11)从best Path中Pareto排序选择一条路径作为以当前虚拟点为起点的最优路径，并将其保存在MM_Path中，同时将该路径上的所有节点标记为不可用；(11.1)设source节点为v_i,置path＝＜1＞，置当前搜索节点v_i＝v₁；(11.2)判断当前搜索节点v_i，是否为sink节点，若是则执行(11.5)，否则执行(11.3)；(11.3)依据邻接矩阵A判断当前搜索节点v_i，的前向邻居节点集合F_i是否为空集，若是则执行回退操作，否则执行(11.4)；(11.4)将F_i的成员按照其距sink节点的距离d_jn(其中令d_nn＝1)降序排列得为F_i按照d_jn降序排列的顺序号；对做如下变换:其中w为常数，v_j∈F_i；计算F_i的成员成为下一跳转发节点的选择概率:其中D_i＝{d_jn|v_j∈F_I}，若v_j被选为下一跳节点，将v_j加入path中:path＝＜1…j＞；将v_j作为当前搜索节点v_i，执行(11.2)；(11.5)输出path；(12)令i＝i+1，执行(5)；(13)输出MM_Path。