基于离散粒子群的单跳路由分簇协议

基于离散粒子群的单跳路由分簇协议

0基于快速收敛离散粒子群的分布式分簇路由粒子群算法优化（pso）是基于团队智能的自适应优化算法。它具有快速收敛性能，可以根据不同的优化目标提出相应的解决方案。无线传感器网络（无线传感器网络）通常用于一些特殊环境。在节点能量受到限制时，集群路径协议是延长网络寿命的有效方法之一。如果节点的剩余能量随着网络的运行而减少，则会动态、快速、有效地找到一组最佳节点作为集群的长度。这是一个以这些节点为中心的节点分割和节点规划问题。这是一个非常困难的问题。现在，在集群分割过程中，大多数集群算法采用竞争模式，从集群第一开始竞争，并消耗一定的能量（如leach、lech-e、heed、eec等）。在文献中，基于leach预测簇的排序是最好的集群之一。然而，对于数据收集节点（基地矩阵，bs）通常定义在监控区域外，集群负责人负责收集、融合和传输来自集群的信息。当任意选择一组节点作为集群时，很容易使远离bs的节点尽快死亡。即使考虑到节点的剩余能量竞争簇的头，如lech、heed、eec等，也不能解释相同输出能量的节点有相同可能性成为集群的原因。要考虑节点1时的能耗消耗率的大小。本文将以延长网络寿命和均衡节点能耗为目标,在定义包含邻居节点信息的粒子适应度函数的基础上,提出一种基于快速收敛离散粒子群(DPSO)优化簇首选择过程的分布式分簇路由协议,该协议采用选举方式产生簇首,无簇首竞争能量消耗,可以较好地避免簇首选择的随机性和均衡网络节点的能量消耗,极大地延长网络寿命;同时,惯性权重随机性的增加和k-收敛准则有利于提高网络寿命与收敛代数的比.1算法的基本思想通常,对一m个粒子的种群,在D维空间的粒子i位置为Xi=(xi1,xi2,…,xiD),粒子搜索至当前代个体最优解为Pi=(pi1,pi2,…,piD),当前代种群的全局最优解为Gi=(gi1,gi2,…,giD),粒子移动速度为Vi=(vi1,vi2,…,viD)(vid∈[Vmin,Vmax]),则广义PSO模型的速度-位移公式如下:V(t+1)i=W(t)×V(t)i+c1R1×(Pi−X(t)i)+c2R2×(Gi−X(t)i)(1)X(t+1)i=Q(X(t)i+V(t+1)i)(2)Vi(t+1)=W(t)×Vi(t)+c1R1×(Ρi-Xi(t))+c2R2×(Gi-Xi(t))(1)Xi(t+1)=Q(Xi(t)+Vi(t+1))(2)(1)和(2)式中t和t+1分别表示当前代和下一代.定义Xic为粒子连续位置向量,则函数Q(Xic)为粒子位置映射函数,对连续问题函数为原来位置与位移的线性叠加,对离散问题则根据具体问题进行非线性变换.式中R1,R2为取值范围内的D维随机数向量;学习因子c1,c2用来调节个体最优解和全局最优解的对粒子下一代的影响,惯性权重W(t)用来控制当前代粒子速度对下一代的影响,其选择方式有:①约束方式(CFA,constrictionfactorapproach),该方式适用于Pi和Gi固定的问题求解.②线性方式(IWLA,inertiaweightlinearapproach),惯性权重取值如下:W(t)j=wmax−wmax−wminImaxiiter(3)Wj(t)=wmax-wmax-wminΙmaxiiter(3)式中Imax为终止迭代次数.随着迭代次数iiter的增加,W(t)如由wmax减小为wmin,即起始粗粒度搜索全局最优,逐渐过渡到细粒度的最优解查找,该方式与求解问题无关.③随机方式(IWRA,inertiaweightrandomapproach),惯性权重确定如下:W(t)=wI+(1−w)R3(4)W(t)=wΙ+(1-w)R3(4)式中I为D维全1向量,R3为取值范围内的随机数D维向量,w为取值范围内的随机数,通常为0.5,学习因子c1,c2取值为1.494.收敛准则:通常,迭代的结束以算法不能找到更优解为准则,而在实现时,需要在每次迭代循环中判断是否要结束.在避免早熟和收敛速度采取折衷措施,在迭代过程中目标函数F(z(g))满足下面条件:F(z(g))−F(z(g−k))≤ε(5)F(z(g))-F(z(g-k))≤ε(5)则算法终止.其中ε>0,g为当前迭代代数,k为迭代间隔.对本文的离散问题,目标函数为粒子的适应度,由于问题的动态变化,无法预知是否达到最优解,因此,算法迭代终止准则有:一种是在规定的终止代数Niter间内不能找到更优解,即全部粒子收敛于一点,简称全收敛(Allconvergence,All-C),显然,该准则收敛速度较慢;另一种是连续k代未有更优解,简称k-收敛(k-convergence,k-C).2dpso分簇路由协议对某一区域范围内的M个传感器节点,构造一m(m≤M)个粒子的种群,定义位置映射函数为Q(Xic)={Xnd|min(∥Xnd−Xic∥),1≤n≤M}(6)Q(Xic)={Xnd|min(∥Xnd-Xic∥),1≤n≤Μ}(6)(6)式表示与Xic欧氏距离最小离散节点粒子位置Xnd作为新的位置.本文的适应度函数充分考虑某区域范围内节点粒子的剩余能量和预测能耗等因素.首先,定义粒子n的能量富裕指数为f1(n)=ε¯r−Er(n)ΔEˆr(n)(7)f1(n)=ε¯r-Er(n)ΔE^r(n)(7)式中,Er(n)为粒子剩余能量,ε¯rε¯r为区域内所有粒子剩余能量均值,ΔEˆE^r(n)为粒子的预测能耗;显然,该值越小,表示该粒子的能量富裕程度越高.其次,定义粒子预测能耗消耗率为f2(n)=ΔEˆr(n)Er(n)(8)f2(n)=ΔE^r(n)Er(n)(8)fz(n)值越小,表示该粒子节点负荷越轻.若定义粒子预测能耗消耗率与粒子群预测能耗消耗率均值的比率为f3(n),则该值越小,表示相对于粒子群中的其他粒子负荷较轻.同理,若定义预测能耗消耗率在区域内所有粒子预测能耗消耗率均值的比率为f4(n),该值越小,表示相对于区域中其它粒子负荷较轻.据此,本文的粒子n适应度函数定义为fFit(Xnd)=∑j=14αjfj(n),∑j=14αj=1,αj∈(9)fFit(Xnd)=∑j=14αjfj(n),∑j=14αj=1,αj∈(9)显然,系数α1～α4决定了4种分量对适应值的贡献比例.粒子越富裕,负荷越轻,其适应值就越小,越有可能成为簇首.本文的DPSO分簇算法就是寻找最小适应值粒子担任簇首,即min{fFit(Xnd)}.基于分簇的WSN路由协议分为分簇、簇内时隙分配、簇内数据传输、簇间(包括至BS)数据传输几个阶段.DPSO分簇路由协议的主要任务是在分簇阶段完成簇首的选举.在分簇阶段随机选择一组节点执行DPSO算法,执行该算法的节点称为DPSO代理,由代理选举产生出适应值最小的节点担任簇首.若代理有Nb个邻居节点,种群规模数m为min{Nb/3,mmax},mmax为最大种群规模,终止代数为Niter,则算法流程如图1所示.本文的路由协议考虑如下能耗:数据包在收发机中处理能耗、数据包的发送能耗,数据包的数据融合能耗,并假设:①监测区域内所有节点同质,初始能量相同,可以通过信号强度计算节点间的距离;②节点的通信功率可调;③BS和节点位置信息已知,BS位置固定且远离监测区域,BS能量足够大,网络已经同步.基于DPSO的分簇路由协议如下:1打造分簇形成子阶段节点n根据式(10)计算r“轮”是否成为DPSO代理的门限T(n,r)Th1(n,r)={PN/Na,PN/Na<11,PN/Na≥1(10)Τh1(n,r)={ΡΝ/Νa,ΡΝ/Νa<11,ΡΝ/Νa≥1(10)式中P为簇首比例因子,N为传感器节点数,Na为非死亡传感器节点数.选择一随机数p(0≤p≤1),若p<Th1(n,r),该节点当选为代理,进入选举簇首子阶段2).当p≥Th1(n,r)时,若在DPSO最大演化时间TDPSO内监听到选择簇首消息Candidate_Sel_Req或声明成为簇首消息Clusterhead_Msg,则进入分簇形成子阶段;否则,调整代理门限Th1(n,r)为Th2(n,r,i)Th2(n,r,i)={2iP,2iP<11,2iP≥1(11)Τh2(n,r,i)={2iΡ,2iΡ<11,2iΡ≥1(11)式中i为在该阶段的循环迭代次数,继续循环执行1).2获得本地节点代理节点执行DPSO算法终止后,选举产生节点Id为簇首,若为本地节点,则对外发送Clusterhead_Msg后成为簇首;若非本地节点,则发送Candidate_Sel_Req;进入分簇形成子阶段3).3dpso代理与引领性基于信号发送阶段在该子阶段,节点在不同状态时对收到消息的处理如下:①状态不为簇首时收到己方的Candidate_Sel_Req,则发送消息Clusterhead_Msg成为簇首,等待其他节点加入该簇,继续循环执行3);②状态不为簇首时收到Clusterhead_Msg,则根据信号强弱对选择距离最近簇首发送加入簇请求消息Join_Req_Msg,等待簇首确认消息Join_Ack_Msg;若收到Join_Ack_Msg,节点成为普通节,进入发送监测数据阶段,否则,继续等待.③状态为簇首在收到所有请求加入簇消息Join_Req_Msg后,发送Join_Ack_Msg完成该簇内节点的时隙分配,进入TDMA工作的监测数据的发送阶段.协议后续阶段与LEACH协议结构类似,这里不再赘述.在簇首选举期间,即在DPSO代理产生和选举簇首2个子阶段的发送簇首选择或声明消息的通信开销介于PN与N之间;而时间开销最大为Niter[log2(1/P)],因此,其复杂度为O(1),在不影响DPSO最佳搜索结果和收敛速度情况下,降低Niter可降低算法的时间开销.为评价惯性权重对DPSO的收敛速度和网络寿命LFND影响,定义评价指标:网络寿命与平均收敛代数比为Φ=LFNDIc(12)Φ=LFΝDΙc(12)式中Ic为在LFND内DPSO算法的平均收敛代数.显然,LFND越大,Ic越小,则算法的性价比Φ越高.3多经传播能耗3.1网络节点能耗均匀性分析DPSO惯性权重采用IWRA,Niter=100,mmax=20,w=0.5,c1=c2=1.494,α1=0.6,α2=0.1,α3=α4=0.15,收敛准则为All-C,图2给出了场景S1的3种协议的节点死亡数与工作轮数的关系曲线,可以看到:基于CDPSO算法较LEACH和LEACH-E延长了LFND达91.7%和53.3%,并且在LFND轮之后其余网络节点在较短的工作轮之后失效,能量利用特性较好.图3给出了相应的每一轮中非死亡节点平均剩余能量与均方差曲线,结果表明:在LFND轮内,LEACH、LEACH-E算法的节点剩余能量均方差近似于线性增加,而CDPSO算法的剩余能量均方差维持在一个较小的范围,因此DPSOCA的网络节点能耗均匀性较好.3.2全收敛准则的lfnd分析在Niter=100,c1=c2=1.494,α1=0.6,α2=0.1,α3=α4=0.15,mmax=20时,对IWRA方式,w由0.1增加至0.9,算法收敛准则分别为:全收敛(All-C),k-收敛(k=10,3),场景S1和S2的Φ如图4所示,结果表明:①w从0.1增至0.9时,惯性权重随机性降低,LFND有少许增加,而CDPSO收敛代数快速上升反而使得Φ有所下降;②在其他参数设置相同条件下,全收敛准则的收敛代数明显大于k-收敛的收敛代数,而其LFND较为稳定变化很小,如S1在3种终止准则的LFND统计值为(1739.5±1.7)All-C,(1740.2±1.6)10-C和(1737.7±1.2)3-C,S2在3种终止准则的LFND统计值为(710.1±2.0)All-C,(692.9±1.5)10-C和(684.4±4.3)3-C,说明k-C准则的Φ性能明显优于All-C准则;③在k-C准则下,减小k有利于提高Φ,且在高节点浓