祁育仙, 李国勇
(太原理工大学 信息工程学院,山西 太原 030024)
计算与测试
混合WSNs中基于多目标优化的覆盖控制算法*
祁育仙, 李国勇
(太原理工大学 信息工程学院,山西 太原 030024)
摘要:针对无线传感器网络(WSNs)随机部署产生的区域覆盖率低、节点利用率差和能量不均衡的问题,引入移动传感器节点,将快速非支配排序遗传算法Ⅱ(NSGA-Ⅱ)运用到混合无线传感器网络覆盖控制部署并进行改进,采用分层编码策略,引入删除算子避免早熟,自适应改变交叉、变异概率提高局部搜索能力,获得较优解集后基于决策者信息偏好选择最优目标。仿真实验结果表明:有效解决了WSNs覆盖控制问题,可以在网络覆盖率最大化的同时,节点利用率较大且能耗系数较低,延长网络寿命。
关键词:无线传感器网络; 覆盖; 多目标优化; 算子
0引言
无线传感器网络(wireless sensor networks,WSNs)是一种全新的信息获取和处理的方式,广泛应用于军事、环境保护、农业和医疗等其他领域。在条件恶劣的情况下,由飞行器随机部署网络节点,会产生高密度节点和覆盖空洞,影响网络服务质量,又由于WSNs中每个节点电池能量有限、难以补充,因此,在覆盖率最大化的同时延长网络生命周期是WSNs面临的重要难题。文献[1]将免疫优化引入粒子群算法,维持了种群多样性,但是没有考虑能耗均衡对网络性能的影响。文献[2]综合考虑了网络覆盖率、节点利用率和能耗均衡对网络性能的影响,利用混沌运动的遍历性提高了算法的全局搜索能力,但是其目标函数采用加权算法,决策者很难做出取舍与平衡。文献[3]建立了最大化网络覆盖率、最大化节点休眠率和最小化网络工作能耗的传感器网络寿命多目标优化模型,提出基于非支配排序遗传算法(nondominated sorting genetic algorithm Ⅱ,NSGA—Ⅱ)的网络覆盖解决方案,可以获得更有效的网络覆盖率和更少的网络能量消耗,但是其WSNs中需随机布设大量的静态节点,成本相应增加。
本文采用固定节点和移动节点相结合的方式组成混合WSNs,利用少量移动节点的移动性满足覆盖质量,将NSGA—Ⅱ进行改进用于混合WSNs覆盖优化。
1WSNs覆盖问题描述
1.1问题建模
M个移动传感器节点和N个固定传感器节点构成节点集S(S={s1,s2,…,si,…,sM+N})由飞行器随机部署在监测区域D的二维矩形平面。研究的问题是:1)尽可能发现固定传感器冗余节点使其进入休眠状态,使得网络在连通的前提下使用尽可能少的节点下获得最大的覆盖率;2)求得各个移动传感器节点的运动规划,使得最小的运动代价获得网络覆盖质量的最大提升;3)使得网络能耗尽量均衡,延长网络生命周期。
在不影响问题本质的前提下,做出如下假设:1)已知固定节点的精确位置信息;所有传感器均为同一结构,感知半径为Rs,通信半径为Rc,且Rc=2Rs;2)每个节点具有工作、休眠和侦测三种状态;3)将区域D离散化为m×n个像素点;4)所有移动传感器节点可准确移动到指定位置。
1.2节点感知模型
目前,在WSNs研究中广泛使用的是二元感知模型和概率感知模型,本文使用更符合实际应用的概率感知模型。传感器节点si(xi,yi)对监测区域中任意一点p(xp,yp)感知概率为[4]
(1)
式中d(si,p)为节点si(xi,yi)到p点的欧氏距离
式中λ,β为传感器节点检测质量的衰减系数;Re(0 由式(1)可以得出所有节点在p点的联合监测概率为 (2) 若p点被有效感知,且区域内任意一点被有效感知的概率阈值为Cth,则其必须满足Cp(S,p)′≥Cth。 为了简化运算,本文将p点的覆盖率定义为 (3) 1.3WSNs覆盖目标 定义子集S′⊂S,根据问题模型可得出覆盖目标为: 目标1:覆盖率Pcov(S′)最大,即 (4) 目标2:子集S′中工作节点数最少,即 maxf2=1-|S′|/|S|. (5) 其中,|S′|为工作节点总数;|S|为WSNs中部署的传感器节点总数。 目标3:子集S′构成的WSNs中能耗系数最小,即 (6) 其中,Ei为节点i的剩余能耗。 WSNs覆盖目标可以归结为满足网络全连通条件(即对于工作状态的任意传感器节点si(xi,xj),在其通信范围内至少存在一个传感器节点sj(xj,yj))的多目标优化问题,即 max[f1,f2,f3] s.t.∀i∈[1,N+M],∃j∈[1,N+M],且i≠j, (7) 2混合WSNs覆盖优化算法 WSNs覆盖优化问题是个典型的多目标优化问题,多个目标间存在冲突,就所有目标而言,不存在一个唯一的最大值或最小值。相反地,存在多个最优解,这些解是所有冲突目标之间的折中结果。 目前的多目标优化算法很多,但是带精英策略的快速NSGA—Ⅱ算法是应用最为广泛的一种[5~7],但是其种群迭代过程会陷入局部最优解,为了获取优秀的Pareto最优解,提高搜索能力,防止陷入局部最优解,本文对NSGA—Ⅱ算法加以改进应用到WSNs覆盖优化问题,并采用基于决策者信息偏好选择最优解。 2.1种群编码 2.2交叉与变异策略的自适应 SGA中交叉概率Pc和变异概率Pm是不变的,导致后期搜索迟钝,进化停滞,自适应控制可以有效地改善后期收敛速度,在进化过程中自适应的改变Pc,Pm的大小,将进化过程分为渐进和突变两个不同的阶段:渐进阶段强交叉、弱变异,扩大整体搜索范围,突变阶段弱交叉、强变异,使优良基因结构得以保存,且防止陷入局部最优,自适应调节公式为[8] 式中f为两个交叉个体适应度值的较大值;f ′为变异个体的适应度值;favg,fmax和fmin分别为当前种群所有个体的平均适应度值、最大适应度值和最小适应度值;Pc min和Pc max分别为交叉概率的最小值和最大值;Pm min和Pm max分别为变异概率的最小值和最大值。 2.3遗传算子改进 删除算子:种群繁殖过程中,计算适值之后对个体进行排序,在排序的同时引入删除算子,将种群中相同的个体删除,避免高适值个体占领种群引起早熟[9]。 交叉算子:前一部分为移动节点集,采用部分映射交叉,后一部分为所有节点工作状态,为二进制编码,采用单点交叉。 变异算子:前一部分采取随机选取两个点,将其对换位置。后一部分采用基本位变异的方法。 2.4种群更新过程 改进后的NSGA-Ⅱ种群更新过程如图1所示。 图1 种群更新过程Fig 1 Update process of populations 2.5最优个体的选取 根据多目标遗传算法将得到多组Pareto解集,实际应用中,必须在解集中选取一组解当做最优WSNs节点部署方案。本文将非劣前端中的个体采用式(8)的加权法得出集合中各个体的适应度值,选取适应度值最大的个体作为最优的部署方案 maxf=w1f1+w2f2+w3f3. (8) 其中,w1+w2+w3=1,三个加权系数的选取依据设计者的选择偏好来定。 3实验结果与分析 3.1实验环境与参数设置 参数设置为:区域D为50 m×50 m,N为100,M为20,感知半径为Rs=9 m,通信半径为Rc=18 m,容错感知半径为Re=5 m,λ=0.5,β=0.5,感知概率门限Cth=0.7,初始种群规模为50,最大迭代次数为200,Pc max=0.45,Pc min=0.25,Pm max=0.04,Pm min=0.02,w1=0.6,w2=0.25,w3=0.15。 3.2算法有效性与稳定性 首先,检验算法的可行性,由参数设定,得出WSNs覆盖优化结果如图2所示。 图2 WSNs覆盖优化结果Fig 2 Optimization results of WSNs coverage 由图2可知,经过本文算法优化后,由节点覆盖率、节点休眠率以及能耗系数组成的三维坐标均匀分布,且优化后覆盖率增加明显,节点休眠率也明显增大,能耗系数也相应的减小。 为检验算法的稳定性,将算法执行10次,其覆盖率如图3所示。 图中数字表示工作节点数,通过算法优化,可以使WSNs覆盖率均可以达到97 %以上,且使得网络中的冗余节点均处于休眠状态,延长网络寿命。 图3 优化前后覆盖率对比Fig 3 Coverage rate comparison before and after optimization 3.3与NSGA—Ⅱ算法进行比较 为进一步验证算法的性能,将本文算法与原始NSGA—Ⅱ算法进行比较分析,得出如图4所示性能对比曲线。 图4 性能对比曲线Fig 4 Performance comparison curves 由图4可知,在工作节点数相同的情况下,本文算法可以获得更高的覆盖率,延长网络寿命。 进一步,将本文算法与NSGA—Ⅱ每一种群迭代更新后的能耗系数平均值做比较,如图5所示。可得出,本文算法对于混合WSNs覆盖可以更好地降低能耗系数,延长网络寿命。 图5 能耗系数迭代过程Fig 5 Iterative process of energy consumption coefficient 4结束语 本文对混合WSNs覆盖问题进行分析,由其是典型的多目标优化问题,将NSGA—Ⅱ算法并进行改进用于WSNs的覆盖优化,使用分层编码策略,引入删除算子,自适应调整交叉、变异概率,得到Pareto最优解集采用决策者信息偏好来选择最优解,通过实验仿真显示:该算法可以用于混合WSNs覆盖控制,改进后的算法较NSGA—Ⅱ可以防止陷入局部最优解,在工作节点数相同的情况下,改进后的算法可以得到更高的覆盖率,增大节点利用率,且能耗系数较低,延长网络寿命。 参考文献: [1]Mo Yuanbin,Liu Jizhong,Wang Baolei,et al.A novel swarm in- telligence algorithm and its application in solving wireless sensor networks coverage problems[J].Journal of Networks,2012,7(12):2037-2042. [2]兰慎,彭刚.基于改进鱼群算法的无线传感器网络覆盖优化[J].计算机仿真,2013,30(9):252-255. [3]贾杰,陈剑,常桂然,等.基于节点协同覆盖的传感器网络寿命最大化模型[J].控制与决策, 2009,24(8):1181-1186. [4]黄月,吴成东,张云洲,等.混合无线传感器网络覆盖空洞修复策略[J].江南大学学报:自然科学版,2012,11(4):418-422. [5]孔维键,丁进良,柴天佑.高维多目标进化算法研究综述[J].控制与决策,2010,25(3):321-326. [6]Segupta Soumyadip,Das Swagatam,Nasir M D,et al.Multi-objective node deployment in WSNs:In search of an optimal trade-off among coverage,lifetime,energy consumption, and connectivity[J].Engineering Applications of Artificial Intelligence,2013,26:405-415. [7]Segupta S,Das S,Vasilakos A V,et al.An evolutionary multi-objective sleep-scheduling scheme for differentiated coverage in wireless sensor networks [J].Applications and Reviews,2012,42(6):1093-1102. [8]包北方,杨育,李雷霆,等.产品定制协同开发任务分配多目标化[J].计算机集成制造系统,2014,20(4):740-746. [9]李满林,杜雷,闻英友,等.多目标遗传算法在移动网络规划中的应用[J].控制与决策, 2003,18(4):441-444. Coverage control algorithm for hybrid WSNs based on multi-objective optimization* QI Yu-xian, LI Guo-yong (College of Information Engineering,Taiyuan University of Technology,Taiyuan 030024,China) Abstract:Aiming at problem of low coverage rate, poor utilization rate of node and energy imbalance caused by random deployment of wireless sensor networks(WSNs),introduce mobile sensor nodes,use and modify NSGA-Ⅱ to hybrid WSNs coverage control deployment.Use hierarchical coding strategies,introduce delete operator to avoid early-maturing,adjust crossover and mutation probability adaptively to improve local search ability,choose the optimal target based on decision makers’ information preference,after obtaining optimal solution sets.Simulation experimental result show that this algorithm is an effective solution for coverage control problem,having higher nodes usage and lower energy consumption coefficient,prolong network lifetime,while maximizing network coverage rate and extend network lifetime. Key words:wireless sensor networks(WSNs); coverage; multi-objective optimization; operator DOI:10.13873/J.1000—9787(2016)02—0136—04 收稿日期:2015—03—25 *基金项目:国家自然科学基金资助项目(51075291) 中图分类号:TP 212 文献标识码:A 文章编号:1000—9787(2016)02—0136—04 作者简介: 祁育仙(1989-),女,山西太原人,硕士,主要从事预测控制、智能控制理论及应用等研究。 李国勇,通讯作者,E—mail:tygdlgy@163.com。