|
算节点到簇首的平均距离为： 2 d M π pN − = ，依据本文的仿真环境， _ d≈ 17.8m。 由于节点距簇头可能非常近，在实际中，需要将k,j d 限定在一定的范围内： _ _ , , , 2 2 k j k j k j d d d d d others ⎧⎪ < =⎨⎪⎩ 135 综上，针对图2 中的两种簇的结构它们的网络通信能耗1( ) i f x 相同，簇2 具有更低的 2( ) i f x ，即适应度的值'( ) i f x 更小。 3、网络节点的平均剩余能量和簇头平均剩余能量之比 簇头集合的平均剩余能量体现了网络在本轮中簇头转发数据包的能力[6]，选择平均剩余 140 能量高的集合可以避免节点在当选簇头后无力转发网络的监测数据，造成本轮数据的丢失。 1 3( ) i n i j i j m i i e e f x n k = = ∈ Σ Σ (9) 上式中i k 为粒子i x 选出的簇头集合i m 中的簇头数量， j e 为簇头集合i m 中节点j 的剩余 能量。 基于以上各式，我们构造适应度函数1 2 3 '( ) ( ) ( ( ) ( )) i i i i f x = f x ×αf x +βf x ，适应度值 145 越小说明生成的簇越好。 其中第一项为节点平均传输损耗，第二项为节点簇内加权平均距离，第三项为簇头节点 的平均剩余能量；α 、β 分别为以上三项的加权因子，它们的取值均在[0,1]之间。通过调 节他们的相对大小可以使适应度函数侧重不同的方向。例如在初期可以选择α 值较大，使 形成的簇更为紧密些。后期可以选择β 植较大，以使网络能量消耗更低。'( ) i f x 值越小， 表明生成的簇越好，粒子i 150 x 所选择的簇头越有利于延长网络的生存时间。 确定适应值函数后依据NAPSO 算法的流程进行循环迭代，确定出的最优Pg 中的两个 变量即为最后的解即簇头的位置。但由于监测区域中的传感器节点是离散的，因此最优粒子 的位置不一定能与传感器节点准确对应起来，所以选取与最优粒子位置最近的节点作为最优 簇头。 155 Step3 优化簇的形成阶段。该阶段候选节点将优化后的簇首信息发布给非簇首节点，它 们只能在已经声明作为簇首的节点中选择自己的最佳簇首，即将要加入哪个簇，这一步直接 决定整个网络中簇的分布。LEACH 中节点根据自身通信代价最小原则[7-8]选择距离较近的簇 头加入其簇，不考虑簇头的能量，与基站距离等问题，可能增加簇头的负担，不利于簇的负 载平衡。为了使生成的簇更均匀且保证每个簇首负载均衡，本文引入了成簇适合因子F，非 160 簇头节点在计算当其加入不同簇的适合函数后，选择适合函数值最小的簇加入其中。 min_ 1 2 3 max_ max_ min_ ( , ) ( , j) 1 ( j, ) b o r( ) j j c b b o F i CH f d i CH f d CH bs d f e e CH d A d d E − − = × + × × + × − (10) 其中：(1) ( , ) j d i CH 是当前节点i 与簇头j 的距离； max_ c d =max{ ( , ) j d i CH } ； (2) ( , ) j d CH bs 是当前簇头j 到基站的距离， max_b d =max{ ( , ) j d CH bs }；(3) o e 和r e 分别是 簇头j 的初始能量和当前的剩余能量；(5) f1 ~f3 是成簇适合系数因子，通过它们来调整上式 165 各个部分的成簇代价比重。 Step4 稳定运行阶段。采用动态链的方式。当簇头节点接收到了所有成员节点的数据后， 簇头节点比较各自的权值大小动态成链，进行数据融合后通过簇间传输发送至基站。其中权 值大小受簇头节点剩余能量和到基站的距离两个因素制约。 4 仿真分析及性能评价 170 在MATLAB 仿真平台上，100 个传感器节点随机分布在200× 200 的正方形区域内， 分别对LEACH 算法以及LEACH-C 进行了性能比较。节点能量异构：10%节点的初始能量 为2J，90%节点的初始能量的为1J。簇头数的比例为0.05%，基站在(100,175)处。每次传送 的数据包为4000bit，所有节点一旦放置就不能再移动，网络中没有位置重复的节点，每个 传感器节点都有唯一的ID 标识。选取NAPSO 的各参数值：c1 =1.2，c2 =1.3，α =β = 0.5 ， 175 设置的最大迭代次数为1000 次。 图3 和图4 分别为LEACH 和本文算法执行到某一轮中的簇头分布以及成簇状况。由图 3 可以看出LEACH 算法存在簇头分布不合理、成簇不均匀的现象，左侧和右上方的簇最大， 大部分节点都聚集在此簇内，其它的簇离基站较远，且簇内节点也很少；图4 显示本文算法 产生的簇头均匀的分布在监测区域内，形成的簇大小相似。 0 50 100 150 200 0 50 100 150 200 基站 180 图3 LEACH 算法簇头分布 Fig.3 distribution of cluster-head in LEACH 0 50 100 150 200 0 50 100 150 200 基站 185 图4 NAPSO-CA 的簇头分布 Fig.4 distribution of cluster-head in NAPSO-CA 经过多次试验，比较了改进后的算法和原LEACH 和PSO-C，在图5 中，NAPSO-CA 从FND 和HNA 两方面都有了一定程度的改善，均优于其他2 种算法，有效延长了延长全 190 网的生存时间，达到了节能的目的。图6 进一步从生命周期上说明了NAPSO-CA 的特点， 其剩余节点数在LEACH 和PSO-C 的网络都死亡以后还能继续工作很长一段时间，很适合 应用在实际网络中。 2000 4000 6000 8000 10000 Time steps(rounds) LEACH PSO-C NAPSO-CA FND HNA 969 2405 1881 3568 8445 1648 图5 存活节点数比较 Fig.5 comparison 195 of the living nodes 0 2000 4000 6000 8000 10000 0 20 40 60 80 100 仿真时间（轮） 存活节点数（个） NAPSO-CA PSO-C LEACH 图6 基站固定在(100,175)处，网络生命周期的对比 Fig.6 with the base station located at (100,175), comparison of the lifetime of network 200 图7 可以看出，改进的算法在进行到5000 轮节点总剩余能耗还有约150J，而LEACH 和PSO-C 剩余能耗已完全耗尽，所以改进的算法能大幅的减少簇内能耗。与LEACH 和 PSO-C 相比，改进的算法由于在簇头选举时考虑了簇内的加权平均距离和网络平均能量损 耗等因素，通过减少网络的运行能耗节省了更多的剩余能量。说明改进的算法中网络各节点 205 的能耗均衡性良好。 0 1000 2000 3000 4000 5000 0 50 100 150 200 时间（轮） 网络剩余总能耗 LEACH PSO-C NAPSO-CA 图7 网络的剩余总能耗 Fig.7 total residual energy of entire network 210 5 结论 粒子群算法作为一种新的仿生优化算法，具有简单、有效、收敛快的特性，可以为能量、 处理、存储都有限的无线传感器网络所用。在对现有的基于粒子群优化的分簇路由算法的基 础上，提出了NAPSO-CA，避免了算法陷入局部最优的同时，也在一定程度上避免了簇间 重叠干扰和网络空洞的出现，从而达到了降低节点死亡速度，延长网络生存周期，能量均衡 215 高效的目的。 [参考文献] (References) [1] 沈波，张世永，钟亦平.无线传感器网络分簇路由协议[J].软件学报，2006，17(7)：1588-1600. [2] YE M,LI C F.CHEN G H,WU J.An energy-efficient clustering scheme in wireless sensor networks[R].New 220 York:Proc.of the IEEE Int'l Performance Computing and Communications Conf,2005. [3] Latiff N M,Tsimenidis C C,Sharif B S.Energy-aware Clustering for Wireless Sensor Networks Using Particle Swarm Optimization[C].Proc.of the 18th International Symposium on Personal,Indoor and Mobile Radio Communications.Athens,Greece:[s.n.],2007. [4] 朱丽莉，杨志鹏，袁华.粒子群优化算法分析及研究进展[J].计算机工程与应用，2007,43(5). 225 [5] 恩格尔伯里特(AndriceP.Engelbrecht). 计算群体智能基础(Fundamentals of Computational Swarm Intelligence)[M].译者：谭营.清华大学出版社，2009,10. [6] 梁英，于海斌，曾鹏.应用PSO 优化基于分簇的无线传感器网络路由协议[J].控制与决策，2006,21(4)： 453-456. [7] WANG X G,ZHANG X M,CHEN G L.An adaptive and distributed clustering Scheme for wireless sensor 230 networks[C].IEEE 2007 International Conference on Convergence Information Technology.San Francisco:IEEE Computer Society Press,2007:522-527. [8] LIU C M,LEE C H,WANG L C.Distributed Clustering Algorithms for Data-Gathering in Wireless Mobile Sensor Networks,Parallel and Distributed Computing[M].Academic Press,Inc.Orlando FL USA,2007:1187-1200. 学术论文网Tag：代写论文 代写代发论文 代发论文 职称论文发表 |
