基于粒子群优化的非均匀分簇路由算法
摘要:为了解决无线传感器网络分簇路由算法中存在的“热区”问题和簇头选取问题，设计了一种自适应粒子群优化的非均匀分簇路由算法。首先通过候选节点与汇聚节点之间的距离计算竞争半径并构造出大小不等的多个簇，然后根据簇规模引入优化的粒子群算法，评价节点剩余能量和节点之间的距离等因素选取最终簇头，以剩余能量较多的簇头作为下一跳，形成以汇聚节点为根节点的多跳路由。仿真结果表明，与leach算法和eeuc算法相比，所
提算法网络生存期分别延长了34%和16%,平均能量消耗分别减少了22%和12%，有效地减少了网络节点的能量消耗。
关键词:无线传感器网络；非均匀分簇路由算法；粒子群优化算法；能量消耗；生存期
中图分类号: tp393.07 文献标志码:a
abstract: to deal with the “hot area” problem and cluster heads selection in clustering routing algorithm of wireless sensor network (wsn), the paper designed an uneven clustering routing algorithm based on adaptive particle swarm optimization (pso). firstly, according to the distance between candidate nodes and sink node, the competitive radius was calculated and clusters of various sizes were constructed. then this paper introduced the pso according to the cluster size. the pso was used to select the final cluster heads by
evaluating factors such as residual energy of nodes and distance between nodes. the cluster heads with more residual energy were chosen as the next hop to form multi-top route in which the sink node is the root. the simulation results show that compared with other two similar algorithms, leach and eucc, the proposed algorithm extends 34% and 16% of survival time of network separately, reduces 22% and 12% of average energy consumption respectively, and effectively decreases the network nodes energy consumption.
key words: wireless sensor network (wsn); uneven clustering routing algorithm; particle swarm optimization (pso) algorithm; energy consumption; survival time
0 引言
无线传感器网络(wireless sensor network, wsn)是由部署在监测区域内的大量微型传感器节点形成的一种自组织网络［1］。由于传感节点通过自带电池供电且难以更新，因此，设计出一种能够高效地利用节点的能量且延长网络生存期的路由算法成为无线传感
器网络路由研究的首要目标［2-3］。
经典的低能量自适应分簇路由算法(low-energy adaptive clustering hierarch, leach)［4］每个周期由分簇和数据传输两个阶段构成，但是簇头以随机概率选取且簇头与汇聚节点单跳通
信，容易造成簇头能量耗尽过早死亡。文献［5-7］引入了粒子群优化（particle swarm optimization, pso）算法优化簇头选举，但簇头与汇聚节点单跳通信的方式仍然会造成簇头节点能量的快
速消耗。文献［8-10］在簇头与汇聚节点之间采取多跳的通信方式，有利于节约簇头能量。但是，崔莉等［11］认为距离汇聚节点较近的簇头须转发大量其他簇头发送的数据而消耗过多能量，形成“热区”。针对文献［11］的问题，李成法等提出了非均匀分簇(energy-efficient uneven clustering, eeuc)算法［12］，构造不同规模的簇来改善多跳路由的“热区”问题。但是当簇规模较大时，簇头选取不当更容易造成距离其较远的簇成员节点能量快速地消耗。
针对这些算法存在的不足，本文提出了一种自适应粒子群优化的非均匀分簇路由算法，用以缓解“热区”问题并延长簇内节点的生存期。采用与eeuc算法相同的成簇方案，不同的是本文根据节点与簇头的距离来判断簇规模大小，并在规模较大的簇中使用自适应粒子群优化算法重新选举簇头，当最终簇头选取完成后，以剩余能量较多的簇头作为下一跳，形成以汇聚节点为根节点的多跳路由。
1 pso算法
pso 算法是通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法。假设在d维搜索空间中，群体规模为n，群体中每个粒子i（1≤i≤n）有如下属性：
在d维空间，第t步迭代时的位置表示为向量x i(t)=(x i1 ,x i2 ,…,x id )，飞行速度为v i(t)=(v i1 ,v i2 ,…,v id )。粒子i经历过的最好位置为p i=(p i1 ,p i2 ,…,p id )，在整个群体中，所有粒子经历的最好位置为p g=(p g1 ,p g2 ,…,p gd )。每个粒子根据式(1)和式(2)来更新自身的位置和速度：
x id (t)=x id (t－1)+v id (t)(1)
v id (t)=wv id (t－1)+c 1r 1(p id －x id (t－1))+ c 2r 2(p gd －x id (t－1))(2)
其中：w为惯性权重；c 1和c 2为学习因子；r 1和r 2为区间［0,1］内的随机数。
2 基于pso的非均匀分簇算法
为了延长簇内节点的生存期并缓解由于簇头转发大量数据而消耗过多能量形成的“热区”问题，本文提出了一种基于pso的非均匀分簇路由算法。本算法包括三个阶段，分别为解决“热区”问题的非均匀分簇阶段、减少簇内节点能量消耗的pso优化簇头选取阶段及多跳通信阶段。
2.1 非均匀分簇阶段
为了构造不同规模的簇，首先需要选出候选节点并计算其竞争半径。在网络初始化时，每个传感节点生成一个随机数μ(0<μ<1)，预先设置普通节点成为候选节点的概率为t。如果μ r c=(1－cd max －d(s i,ds)d max －d min )r 0 c(3) 其中:c为控制r c取值范围的参数，且c∈［0,1］；d max 和d min 分别表示全网节点到汇聚节点距离的最大值和最小值；d(s i,ds)表示候选节点s i到汇聚节点的距离；r 0 c为竞争半径的最大值。候选节点s i以r 0 c为半径广播消息，消息的主要内容为节点 id ，竞争半径r c以及自身当前的剩余能量。每个候选节点根据收到的广播消息，构建其邻候选节点集s ch 。若候选节点s i的邻候选节点集表示为s is ch ，则s is ch ={s j︱s j为候选节点，且d(s i,s j)< max (s ir c,s jr c)}。然后在各邻候选节点集中选取剩余能量最多的节点作为初始簇头。假设s i已当选为初始簇头，规定其竞争半径r c内所有候选节点均不能成为初始簇头。最后，非候选节点被唤醒，初始簇头向全网广播簇头消息，其他节点选择通信代价最小的初始簇头加入，完成簇的建立。 第37卷第4期河北工业大学学报2008年8月V ol.37No.4JOURNAL OF HEBEI UNIVERSITY OF TECHNOLOGY August2008 文章编号：1008-2373(2008)04-0055-05 改进的粒子群优化算法 宋洁，董永峰，侯向丹，杨彦卿 （河北工业大学计算机科学与软件学院，天津300401） 摘要粒子群优化算法是一种基于群体的自适应搜索优化算法，存在后期收敛慢、搜索精度低、容易陷入局部极 小等缺点，为此提出了一种改进的粒子群优化算法，从初始解和搜索精度两个方面进行了改进，提高了算法的计 算精度，改善了算法收敛性，很大程度上避免了算法陷入局部极小．对经典函数测试计算，验证了算法的有效性． 关键词粒子群优化算法；均匀化；变量搜索；初始解；搜索精度 中图分类号TP391文献标识码A A Modified Particle Swarm Optimization Algorithm SONG Jie,DONG Yong-feng,HOU Xiang-dan,Y ANG Yan-qing (School of Computer Science and Engineering,Hebei University of Technology,Tianjin300401,China) Abstract Particle Swarm Optimization Algorithm is a kind of auto-adapted search optimization based on community. But the standard particle swarm optimization is used resulting in slow after convergence,low search precision and easily leading to local minimum.A new Particle Swarm Optimization algorithm is proposed to improve from the initial solution and the search precision.The obtained results showed the algorithm computation precision and the astringency are im- proved,and local minimum is avoided.The experimental results of classic functions show that the improved PSO is ef- ficient and feasible. Key words PSO；average；variable search；initial solution；search accuracy 0引言 粒子群优化（Particle Swarm Optimization，PSO）算法是一种基于群体的随机优化技术，最早在1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart[1]共同提出，基本思想源于对鸟群觅食行为的研究．PSO将每个可能产生的解都表述为群中的一个微粒，每个微粒都具有自己的位置向量和速度向量，和一个由目标函数决定的适应度，通过类似梯度下降算法使各粒子向适应度函数值最高的方向群游．该算法控制参数少、程序相对简单，因此在应用领域表现出了很大的优越性．由于PSO算法容易理解、易于实现，所以PSO算法发展很快．目前，多种PSO改进算法已广泛应用于函数优化、神经网络训练、模式识别、模糊系统控制以及其他的应用领域． 许多学者对PSO算法进行研究，发现其容易出现早熟、最优解附近收敛慢等现象，并提出了一些改进方案，例如自适应PSO算法、混合PSO算法、杂交PSO算法等[2-4]．因此，本文从初始解和收敛精度两个角度出发对PSO算法进行了改进，提高了算法的计算精度，有效的改善了算法的优化性能． 1基本PSO算法 PSO算法是一种基于群体的随机优化技术，基本思想源于对鸟群觅食行为的研究．通过对鸟群飞行时经常会突然改变方向、散开、聚集，但整体总保持一致性，个体与个体间鸟群好像在一个中心的控制 收稿日期：2008-04-17 基金项目：河北省自然科学基金（F2006000109） 作者简介：宋洁（1967-），女（汉族），副教授． 安康学院 学年论文（设计） 题目_____________________________________________ 学生姓名_______________ 学号_____________________________ 所在院（系）_______________________________________ 专业班级__________________________________________________ 指导教师_____________________________________________ 年月曰 基于粒子群优化算法的图像分割 （作者：） （） 指导教师： 【摘要】本文通过对粒子群优化算法的研究，采用Java编程，设计出一套用于图像分割的系统。 基于粒子群优化算法的图像分割系统，可以将一幅给定的图像进行分割，然后将分割结果保存。图像分割的目的是将感兴趣的区域从图像中分割出来，从而为计算机视觉的后续处理提供依据。图像分割的方法有多种，阈值法因其实现简单而成为一种有效的图像分割方法。而粒子群优化（PSO）算法是一类随机全局优化技术，它通过粒子间的相互作用发现复杂搜索空间中的最优区域缩短寻找阈值的时间。因此，基于粒子群优化算法的图像分割以粒子群优化算法为寻优工具，建立具有自适应和鲁棒性的分割方法。从而可以在最短的时间内，准确地确定分割阈值。 关键词：粒子群优化（PSO，图像分割，阈值法，鲁棒性 Abstract T his paper based on the particle swarm optimizati on algorithm, desig ns a set of system for image segme ntati on using Java program min g. Image segme ntati on system based on particle swarm optimizati on algorithm, the image can be a given segmentation, and then the segmentation results would be saved. Image segmentation is the purpose of the interested area from the image, thus providing the basis for the subsequent processing of computer vision. There are many methods of image segmentation, threshold method since its simple realization, becomes a kind of effective method in image segmentation. Particle swarm optimization （PSO） algorithm is a stochastic global optimization technique; it finds optimal regions of complex search spaces for threshold time shorte ned through the in teractio n betwee n particles. Therefore, particle swarm optimization algorithm of image segmentation based on particle swarm optimization algorithm based on optimizati on tools; establish segme ntati on method with adaptive and robust. Therefore, it is possible for us in the shortest possible time to accurately determ ine the segme ntati on threshold. Key word s: PSO, image segmentation, threshold method, robust. 1引言 1.1研究的背景和意义 技术的不断向前发展，人们越来越多地利用计算机来获取和处理视觉图像信息。据统计，人类 基于粒子群优化的非均匀分簇路由算法 摘要:为了解决无线传感器网络分簇路由算法中存在的“热区”问题和簇头选取问题，设计了一种自适应粒子群优化的非均匀分簇路由算法。首先通过候选节点与汇聚节点之间的距离计算竞争半径并构造出大小不等的多个簇，然后根据簇规模引入优化的粒子群算法，评价节点剩余能量和节点之间的距离等因素选取最终簇头，以剩余能量较多的簇头作为下一跳，形成以汇聚节点为根节点的多跳路由。仿真结果表明，与leach算法和eeuc算法相比，所 提算法网络生存期分别延长了34%和16%,平均能量消耗分别减少了22%和12%，有效地减少了网络节点的能量消耗。 关键词:无线传感器网络；非均匀分簇路由算法；粒子群优化算法；能量消耗；生存期 中图分类号: tp393.07 文献标志码:a abstract: to deal with the “hot area” problem and cluster heads selection in clustering routing algorithm of wireless sensor network (wsn), the paper designed an uneven clustering routing algorithm based on adaptive particle swarm optimization (pso). firstly, according to the distance between candidate nodes and sink node, the competitive radius was calculated and clusters of various sizes were constructed. then this paper introduced the pso according to the cluster size. the pso was used to select the final cluster heads by 基于最小生成树的非均匀分簇路由算法 摘要:发现现有的针对非均匀分簇路由算法没有充分考虑簇首 与基站之间最优路径选择,而导致传输路径上的能量消耗不均衡的问题。为了更好地均衡传输路径上节点能量的消耗,提出了基于最小生成树的非均匀分簇的路由算法。该算法利用节点剩余能量和节点到基站的距离选举簇首,然后通过建立最小生成树搜寻最优传输路径,这样可以减少传输路径上的能量消耗,有效地解决能耗不均 衡问题。理论分析和实验结果均表明,该算法无论在存活节点个数还是在能量消耗上都明显优于eeuc算法和ebca。 关键词: 簇首;非均匀分簇;不均衡;剩余能量;最小生成树 uneven clustering routing algorithm based on minimum spanning tree zhang ming cai*, xue an rong, wang wei ( school of computer science and telecommunication engineering, jiangsu university, zhenjiang jiangsu 212013, china ) abstract: the existing uneven clustering routing algorithms do not consider the optimal path selection between cluster heads and base station, which leads to unbalanced energy consumption. in order to balance energy consumption of transmission paths, this paper proposed an uneven clustering routing algorithm based on minimum spanning tree. the algorithm utilized residual energy of nodes and the distance between nodes and base station to select cluster heads, and then generated minimum spanning tree to search the optimal transmission paths, which reduced energy consumption on the transmission paths and effectively solved unbalanced energy consumption. the theoretical analysis and experimental results show that the algorithm is better than the existing energy efficient uneven clustering (eeuc) and energy balancing clustering algorithm (ebca) in terms of the number of live nodes and energy consumption. key words: cluster head; uneven clustering; unbalanced; residual energy; minimum spanning tree 0 引言 无线传感器网络(wireless sensor network, wsn)作为新兴的网 收稿日期:2009-12-13 基金项目:国家自然科学基金资助项目(60674021) 作者简介:卢 峰(1982-),男,辽宁抚顺人,东北大学博士研究生;高立群(1949-),男,辽宁沈阳人,东北大学教授,博士生导师 第32卷第9期2011年9月东北大学学报(自然科学版)Journal of Northeastern U niversity(Natural Science)Vol 32,No.9Sep.2011 基于改进粒子群算法的优化策略 卢 峰,高立群 (东北大学信息科学与工程学院,辽宁沈阳 110819) 摘 要:为提高传统粒子群算法的搜索速度和搜索精度,提出了一种改进的自适应粒子群优化算法 将正则变化函数和慢变函数引入传统位置更新和速度更新公式当中,形成两种新的更新机制:搜索算子和开发算子 在算法运行的初始阶段,种群中大部分个体将按照搜索算子进行更新,搜索算子将有助于种群遍历整个解空间;随着迭代次数的增加,按照搜索算子进行更新的个体将逐渐减少,而按照开发算子进行更新的个体将逐渐增多,开发算子将有效地克服陷入局部最优解的问题 通过典型测试函数的仿真实验,新算法在加快收敛速度同时,提高了算法的全局搜索能力 关 键 词:进化算法;粒子群算法;全局优化;慢变函数;自适应 中图分类号:T G 273 文献标志码:A 文章编号:1005 3026(2011)09 01221 04 Novel Optimization Mechanism Based on Improved Particle Swarm Optimization L U Feng ,GAO L i qun (School of Information Science &Engineering,Northeaster n U niv ersity,Shenyang 110819,China.Corresponding author :LU F eng,E mail:feng.lu.lf @g https://www.doczj.com/doc/0318145018.html,) Abstract :To accelerate searching speed and optimization accuracy of traditional PSO,an improved particle swarm optimization (PSO )algorithm w as presented.Regularly vary ing function and slow ly varying function were introduced in the position and velocity update formula.New mechanisms such as explorative operator and exploitative operator are formulated.At the beginning,most elements will be updated by explorative operator in the entire search space sufficiently.Within the iterations,more and more particles w ill be handled by ex ploitative operator,which are useful to overcome the deceptions of multiple local optima.It can be seen from the simulation results of the standard benchm ark test functions that the proposed algorithm not only accelerates the convergence process,but also improves g lobal optim ization ability. Key words:evolutionary algorithms;particle sw arm optimization;global optimization;slow ly v arying function;self adaptive 20世纪90年代初,产生了模拟自然生物群体行为的优化方法,被称为群智能优化方法 Dorigo 等人通过模拟蚂蚁的寻径行为,提出了蚁群优化算法(ant colony optimization)[1] ;Eberhart 等人基于对鸟群、鱼群的模拟,提出了粒子群优化算法(particle sw arm optim ization )[2] 作为一种群智能优化方法的代表,粒子群算法通过个体间的协作来寻找最优解,每个个体都被赋予一个随机速度并在整个解空间中搜索,通 过个体之间的合作与竞争来实现个体进化 由于粒子群优化算法运算简单,易于实现,具有良好的解决非线性、不可微和多峰值复杂优化问题的能力,已被广泛应用于科学和工程实际领域[3-5] 但是,粒子群优化算法是根据全体粒子和自身的搜索经验向着最优解的方向进化,在进化后期收敛速度将变得缓慢,同时算法在收敛到一定精度时,容易陷入停滞,无法继续进化更新,因此,存在早熟和陷入局部极值点的现象 对于函数f=x*sin(x)*cos(2*x)-2*x*sin(3*x)，求其在区间[0,20]上该函数的最大值。 ?初始化种群 已知位置限制[0,20],由于一维问题较为简单，因此可以取初始种群N 为50，迭代次数为100,当然空间维数d 也就是1。 位置和速度的初始化即在位置和速度限制内随机生成一个N×d 的矩阵，对于此题，位置初始化也就是在0~20内随机生成一个50×1的数据矩阵，而对于速度则不用考虑约束，一般直接在0~1内随机生成一个50×1的数据矩阵。 此处的位置约束也可以理解为位置限制，而速度限制是保证粒子步长不超限制的，一般设置速度限制为[-1,1]。 粒子群的另一个特点就是记录每个个体的历史最优和种群的历史最优，因此而二者对应的最优位置和最优值也需要初始化。其中每个个体的历史最优位置可以先初始化为当前位置,而种群的历史最优位置则可初始化为原点。对于最优值，如果求最大值则初始化为负无穷，相反地初始化为正无穷。 每次搜寻都需要将当前的适应度和最优解同历史的记录值进行对比，如果超过历史最优值，则更新个体和种群的历史最优位置和最优解。 ?速度与位置的更新 速度和位置更新是粒子群算法的核心，其原理表达式和更新方式如下: 每次更新完速度和位置都需要考虑速度和位置的限制，需要将其限制在规定范围内，此处仅举出一个常规方法，即将超约束的数据约束到边界（当位置或者速度超出初始化限制时，将其拉回靠近的边界处）。当然，你不用担心他会停住不动，因为每个粒子还有惯性和其他两个参数的影响。 代码如下： clc;clear;close all; %% 初始化种群 f= @(x)x .* sin(x) .* cos(2 * x) - 2 * x .* sin(3 * x); % 函数表达式figure(1);ezplot(f,[0,0.01,20]); N = 50; % 初始种群个数 d = 1; % 空间维数 ger = 100; % 最大迭代次数 limit = [0, 20]; % 设置位置参数限制 vlimit = [-1, 1]; % 设置速度限制 w = 0.8; % 惯性权重 c1 = 0.5; % 自我学习因子 c2 = 0.5; % 群体学习因子 for i = 1:d 粒子群算法解决函数优化问题 1、群智能算法研究背景 粒子群优化算法（Particle Swarm Optimization，PSO）是由Kennedy 和Eberhart 在研究鸟类和鱼类的群体行为基础上于1995 年提出的一种群智能算法，其思想来源于人工生命和演化计算理论，模仿鸟群飞行觅食行为，通过鸟集体协作使群体达到优。 PSO算法作为一种新的群智能算法，可用于解决大量非线性、不可微和多峰值的复杂函数优化问题，并已广泛应用于科学和工程领域，如函数优化、神经网络训练、经济调度、模式识别与分类、结构设计、电磁场和任务调度等工程优化问题等。 PSO算法从提出到进一步发展，仅仅经历了十几年的时间，算法的理论基础还很薄弱，自身也存在着收敛速度慢和早熟的缺陷。如何加快粒子群算法的收敛速度和避免出现早熟收敛，一直是大多数研究者关注的重点。因此，对粒子群算法的分析改进不仅具有理论意义，而且具有一定的实际应用价值。 2、国内外研究现状 对PSO算法中惯性权重的改进：Poli等人在速度更新公式中引入惯性权重来更好的控制收敛和探索，形成了当前的标准PSO算法。 研究人员进行了大量的研究工作，先后提出了线性递减权值( LDIW)策略、模糊惯性权值( FIW) 策略和随机惯性权值( RIW) 策略。其中，FIW 策略需要专家知识建立模糊规则，实现难度较大，RIW 策略被用于求解动态系统，LDIW策略相对简单且收敛速度快， 任子晖，王坚于2009 年，又提出了基于聚焦距离变化率的自适应惯性权重PSO算法。 郑春颖和郑全弟等人，提出了基于试探的变步长自适应粒子群算 法。这些改进的PSO算法既保持了搜索速度快的特点, 又提高了全局搜索的能力。 对PSO算法的行为和收敛性的分析：1999 年采用代数方法对几种典型PSO算法的运行轨迹进行了分析，给出了保证收敛的参数选择范围。在收敛性方面Fransvan den Bergh引用Solis和Wets关于随机性算法的收敛准则，证明了标准PSO算法不能收敛于全局优解，甚至于局部优解；证明了保证收敛的PSO算法能够收敛于局部优解，而不能保证收敛于全局优解。 国内的学者：2006 年，刘洪波和王秀坤等人对粒子群优化算法的收敛性进行分析，指出它在满足收敛性的前提下种群多样性趋于减小，粒子将会因速度降低而失去继续搜索可行解的能力，提出混沌粒子群优化算法。 2008 年，黄翀鹏和熊伟丽等人分析惯性权值因子大小对PSO算法收敛性所带来的影响，对粒子群算法进行了改进。2009 年，高浩和冷文浩等人，分析了速度因子对微粒群算法影响，提出了一种基于Gaussian 变异全局收敛的粒子群算法。并证明了它能以概率 1 收敛到全局优解。 2010 年，为提高粒子群算法的收敛性,提出了基于动力系统的稳定性理论，对惯性权重粒子群模型的收敛性进行了分析，提出了使得在算法模型群模型收敛条件下的惯性权重和加速系数的参数约束关系，使算法在收敛性方面具有显著优越性。在PSO算法中嵌入别的算法的思想和技术。 1997年，李兵和蒋慰孙提出混沌优化方法； 1998年，Angeline在PSO算法中引入遗传算法中的选择算子，该算法虽然加快了算法的收敛速度，但同时也使算法陷入局部优的概率大增，特别是在优化Griewank 基准函数的优值时得到的结果不理想； 2004 年，高鹰和谢胜利将混沌寻优思想引入到粒子群优化算法中，首先对当前群体中的优粒子进行混沌寻优, 再用混沌寻优的结果随机替换群体中的一个粒子，这样提出另一种混沌粒子群优化算法。 ———————————— 作者简介作者简介：：李 辉(1976－)，男，副教授，主研方向：无线传感器网络；刘书吉，硕士研究生。 收稿日期收稿日期：：2013-03-04 修回日期修回日期：：2013-04-18 E-mail ：li20042007@https://www.doczj.com/doc/0318145018.html, 基于节点度和距离的WSN 分簇路由算法 李 辉，刘书吉 (河南理工大学电气工程与自动化学院，河南 焦作454000) 摘 要：针对无线传感器网络(WSN)中节点的负载均衡问题，提出一种基于节点度和距离的WSN 非均匀分簇路由算法。该算法在首轮成簇时采用了定时机制的簇头竞争方案，定时的长短取决于节点本身的节点度和距离基站的距离，且节点根据不同的竞争半径形成不同的簇。在首轮成簇结束后，簇的结构不再发生变化，而簇头的轮换则根据簇内节点的剩余能量和距离本簇质心的通信代价在簇内进行动态轮换。采用簇间多跳路由，根据节点的剩余能量、距离基站的距离、节点间通信代价和节点的转发热度来选择中继节点。仿真结果表明，该算法的网络生命周期与LEACH 协议相比延长了2倍以上，与EEUC 协议相比延长了13.97%，且均衡了网络的能量消耗。 关键词关键词：：无线传感器网络；非均匀分簇；节点度；距离；转发热度；动态轮换 Clustering Routing Algorithm Based on Node Degree and Distance for Wireless Sensor Networks LI Hui, LIU Shu-ji (School of Electrical Engineering and Automation, Henan Polytechnic University, Jiaozuo 454000, China) 【Abstract 】Aiming at the problem of unnecessary energy consumption caused by periodic clustering and the load balance problem in the Wireless Sensor Networks(WSN), an Unequal Clustering routing algorithm based on node Degree and Distance for WSN(UCDD) is proposed. UCDD algorithm adopts the time competitive mechanism in the first round of clustering. The length of time depends on the nodes’ node degree and the distance from the base station, and different clusters are formed according to the different radius of competition. After the first round, the clusters’ structure does not change any more. Cluster head dynamically choose next cluster head according to the residual energy and the communication costs. Inter-cluster multihop routing is used in UCDD algorithm, and the relay node is selected according to node residual energy, distance from the base station, communication cost of nodes and relay hot. Simulation results show that the algorithm can prolong the networks lifetime by more than two times compared with LEACH protocol and by 13.97% compared with EEUC protocol. Besides, it balances the energy dissipation of the networks. 【Key words 】Wireless Sensor Networks(WSN); unequal clustering; node degree; distance; relay heat; dynamic rotation DOI: 10.3969/j.issn.1000-3428.2014.03.023 计 算 机 工 程 Computer Engineering 第40卷 第3期 V ol.40 No.3 2014年3月 March 2014 ·移动互联与通信技术移动互联与通信技术·· 文章编号文章编号：：1000-3428(2014)03-0113-07 文献标识码文献标识码：：A 中图分类号中图分类号：：TP391 1 概述 无线传感器网络(Wireless Sensor Networks, WSN)是继互联网之后的又一个对人类生活产生重大影响的IT 技术[1]。由于传感器节点的能量受限，因此基于分层的路由协议备受关注。基于概率的低功耗自适应分簇协议(Low-energy Adaptive Clustering Hierarchy, LEACH)[2]是最早的分簇路由协议，几乎贯穿了后来发展的大多数分簇协议。该协议通过等概率随机循环地选择簇头以此来将整个网络的能量负载平均分配到每个传感器节点上，从而达到降低网络能量耗费、延长网络生命周期的目的[3]。LEACH 协议成簇时簇首选择方法简单，易于实现。但是，LEACH 协议的缺点也非常明显：(1)在簇头选择时没有考虑能量因素，无论节点 的剩余能量多少都有可能成为簇头，从而加速了低能量节点的死亡；(2)簇头分布不均；(3)在数据传输时采用了单跳模式数据传输，当传输相同的数据时距离基站远的簇头的节点能耗较快。文献[4]的HEED 算法在簇头选择时依据主参数能量和次参数簇内通信代价，其分簇速度更快，并且产生的簇头分布比较均匀、网络的拓扑结构也更加合理。但是在成簇时通信开销大。文献[5]提出的最小ID 分簇算法，方法简单易行。但是在成簇时需要相互交换ID 号，带来很大的能量开销，并且选择的簇头分布不太均匀。文献[6]提出的集中式分簇算法(LEACH-C)，每轮结束时将能量信息和位置信息发送给基站，由基站来选择簇头。虽然解决了簇头分布不均问题，但是每轮都要发送能量和位置信息浪费了大量的能量。文献[7]提出的基于竞争的非均匀分簇 Computer Engineering and Applications 计算机工程与应用 2016，52（7）1引言无线传感器网络（Wireless Sensor Networks ，WSN ）是由部署在检测区域内的大量集数据采集、处理及通信功能于一体的微型传感器节点组成的无线网络[1]。WSN 不需要固定基础设施的支持，具有自组织、动态拓扑、快速展开等特点，被广泛应用于军事国防、工业监控、智能家居、精细农业等领域[2-4]。然而，一般情况下，传感器节点计算、存储、通信能力以及能量都十分有限，这使得传统的网络路由协议不能适用于WSN [5]。因此，研究和设计满足无线传感器网络特殊性能要求的通信路由协议一直是WSN 迫切需要解决的问题之一。现有的路由协议主要分为平面路由协议[6]和分簇路由协议[7]。分簇路由协议具有能量利用高效、可扩展性好、数据融合简单等特点，已成为WSN 重点研究的路由技术。 LEACH [7]协议是最早提出的也是最为经典的无线传感器网络分簇路由协议，后来的很多分簇路由协议都是在它的基础上发展而来的，例如HEED 协议、UCS 协议、EEUC 协议等。尽管这些协议都有效地均衡了节点的能量损耗，但同时也存在一定的不足。例如，LEACH 协议簇首选择的随机性，容易造成簇首分布不均匀，簇首采用单跳的方式直接与基站进行通信，加速了远离基站的节点的死亡速度；HEED [8]协议克服了LEACH 协议簇首选择的随机性，在簇首选择时考虑到节点的剩余能量和簇内通信代价，但在建簇时消息迭代次数比较多，由此带来的通信开销也比较大；UCS [9]协议采用簇首与基站多跳通信的方式来降低簇首节点的单跳通信能耗一种能量高效的非均匀分簇算法 张长森，邢娟，赵尚卿 ZHANG Changsen,XING Juan,ZHAO Shangqing 河南理工大学计算机科学与技术学院，河南焦作454000 School of Computer Science and Technology,Henan Polytechnic University,Jiaozuo,Henan 454000,China ZHANG Changsen,XING Juan,ZHAO Shangqing.Energy-efficient uneven clustering https://www.doczj.com/doc/0318145018.html,puter Engi-neering and Applications,2016,52（7）：106-109. Abstract ：In order to address the issue of the energy consumption unbalance in wireless sensor networks,an energy-efficient uneven clustering algorithm is proposed.The new algorithm adopts cluster head election strategy based on the residual energy of nodes,and a cluster head employs the thought of unequal clustering to build a cluster.When building the inter-cluster routing tree,cluster heads take into consideration the adjacent cluster heads ’residual energy,the number of cluster members,the relative distance to itself and the relative distance to base station.Simulation results show the algo-rithm can effectively balance the network energy consumption and prolong the lifetime of the network. Key words ：wireless sensor networks;energy-efficient;uneven clustering;inter-cluster routing tree 摘要：针对无线传感器网络中的能量消耗不均衡问题，提出一种能量高效的非均匀分簇算法——EUCA 。算法采取基于节点剩余能量的簇首选举策略，簇首采用非均匀分簇的思想来构建大小不等的簇，在构建簇间路由树时，综合考虑了邻近簇首的剩余能量、簇成员数目、相对自身的距离和相对基站的距离，以此来均衡簇首能量损耗。仿真结果表明，该算法有效均衡了网络能量损耗，延长了网络的生存周期。 关键词：无线传感器网络；能量高效；非均匀分簇；簇间路由树 文献标志码：A 中图分类号：TP393doi ：10.3778/j.issn.1002-8331.1405-0123 基金项目：国家自然科学基金（No.51174263）；教育部博士点基金（No.20124116120004）；河南省教育厅科学技术研究重点项目 （No.12B510011，No.12A520022）；河南理工大学博士基金（No.B2013-036）。 作者简介：张长森（1969—），男，博士，教授，主要研究方向：矿井监控与通信、无线传感器网络；邢娟（1987—），女，硕士研究生，研 究领域为无线传感器网络，E-mail ：zsxjbtxl@https://www.doczj.com/doc/0318145018.html, ；赵尚卿（1988—），男，硕士研究生，研究领域为无线协作通信。 收稿日期：2014-05-12修回日期：2014-07-04文章编号：1002-8331（2016）07-0106-04 CNKI 网络优先出版：2014-12-11,https://www.doczj.com/doc/0318145018.html,/kcms/detail/11.2127.TP.20141211.1522.015.html 106 基于粒子群优化的非均匀分簇路由算法摘要:为了解决无线传感器网络分簇路由算法中存在的“热区”问题和簇头选取问题，设计了一种自适应粒子群优化的非均匀分簇路由算法。首先通过候选节点与汇聚节点之间的距离计算竞争半径并构造出大小不等的多个簇，然后根据簇规模引入优化的粒子群算法，评价节点剩余能量和节点之间的距离等因素选取最终簇头，以剩余能量较多的簇头作为下一跳，形成以汇聚节点为根节点的多跳路由。仿真结果表明，与leach算法和eeuc算法相比，所 提算法网络生存期分别延长了34%和16%,平均能量消耗分别减少了22%和12%，有效地减少了网络节点的能量消耗。 关键词:无线传感器网络；非均匀分簇路由算法；粒子群优化 算法；能量消耗；生存期 中图分类号: 文献标志码:a abstract: to deal with the “hot area” problem and cluster heads selection in clustering routing algorithm of wireless sensor network (wsn), the paper designed an uneven clustering routing algorithm based on adaptive particle swarm optimization (pso). firstly, according to the distance between candidate nodes and sink node, the competitive radius was calculated and clusters of various sizes were constructed. then this paper introduced the pso according to the cluster size. the pso was used to select the final cluster heads by 基于粒子群优化算法的神经网络在农药定量构效关系建模中的应用 张丽平 俞欢军3 陈德钊 胡上序 (浙江大学化工系,杭州310027) 摘 要 神经网络模型能有效模拟非线性输入输出关系,但其常规训练算法为BP 或其它梯度算法,导致训练时间较长且易陷入局部极小点。本实验探讨用粒子群优化算法训练神经网络,并应用到苯乙酰胺类农药的定量构效关系建模中,对未知化合物的活性进行预测来指导新药的设计和合成。仿真结果表明,粒子群优化算法训练的神经网络不仅收敛速度明显加快,而且其预报精度也得到了较大的提高。关键词 粒子群优化算法,神经网络,定量构效关系 2004201204收稿;2004207225接受 本文系国家自然科学基金资助项目(N o.20276063) 1 引 言 药物定量构效关系(QS AR )是研究药物生理活性和药物分子结构参数间的量变规律并建立相应的 数学模型,进而研究药物的作用机理,从而用于预测未知化合物的生物活性,探讨药物的作用机理,指导新药的设计和合成,在药物和农药的研究与设计中已经显示出广阔的应用前景1。以往QS AR 的建模方法大多基于统计原理,局限于线性模型,只进行简单的非线性处理,由此所建立的模型很难契合实际构效关系,并且其处理过程都比较繁琐2。神经网络通过学习将构效关系知识隐式分布在网络之中,适用于高度非线性体系。 在药物QS AR 中采用神经网络(NN )始于20世纪80年代末3,此后得到迅速的发展,目前已发展为除多重线性回归和多元数据分析之外的第3种方法4。通常多层前传网络采用BP 算法,通过误差反传,按梯度下降的方向调整权值。其缺点是可能陷入局部极小点,且对高维输入收敛速度非常缓慢。 粒子群优化算法(particle swarm optimization ,PS O )是K ennedy 等5源于对鸟群、鱼群和人类社会行为的研究而发展的一种新的进化型寻优技术。PS O 已成为进化寻优算法研究的热点,其最主要特点是简单、收敛速度快,且所需领域知识少。本实验拟将该方法初始化前传神经网络为苯乙酰胺类农药建立良好适用的QS AR 模型。 2 苯乙酰胺类农药的Q SAR 问题 苯乙酰胺类化合物是除草农药,其除草活性与其分子结构密切相关。所有的N 2(12甲基212苯乙基)苯乙酰胺都可用相应的羧酸酰胺通过霍夫曼反应生成。N 2(12甲基212苯乙基)苯乙酰胺的基本结构式为 : 其中X 为Me 、F 、Cl 、OMe 、CF 3和Br 等,Y 为Me 、Cl 、F 和Br 等,由不同的X 和Y 取代基可构成不同的化合物。常用以下7个理化参数描述化合物的分子组成和结构:log P 、log 2P (疏水性参数及其平方项)、 σ(电性效应参数)、E s (T aft 立体参数)、MR (摩尔折射度),1χ、2 χ(分子连接性指数)。于是这类化合物的QS AR 就转化为上述理化参数与除草活性间的关系。为研究这种关系,选用具有代表性的50个化合物, 他们的活性值取自文献1,见表1。 第32卷2004年12月分析化学(FE NXI H UAX UE ) 研究报告Chinese Journal of Analytical Chemistry 第12期1590～1594改进的粒子群优化算法
基于粒子群优化算法的图像分割
基于粒子群优化的非均匀分簇路由算法【精品文档】(完整版)
最小生成树非均匀分簇路由算法
基于改进粒子群算法的优化策略
基于MATLAB的粒子群优化算法的应用示例
粒子群算法解决函数优化问题
基于节点度和距离的WSN分簇路由算法
一种能量高效的非均匀分簇算法
基于粒子群优化非均匀分簇路由算法
基于粒子群优化算法的神经网络在
相关主题
文本预览