平码五不中公式规律
  • / 21
  • 下载费用:30 金币  

一种基于改进和声搜索算法的无线传感器网络路由方法.pdf

关 键 ?#21097;?/dt>
一种 基于 改进 和声 搜索 算法 无线 传感器 网络 路由 方法
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
摘要
申请专利号:

CN201410097200.3

申请日:

2014.03.17

公开号:

CN103916927A

公开日:

2014.07.09

当前法律状态:

授权

有效性:

有权

法?#19978;?#24773;: 授权|||实质审查的生效IPC(主分类):H04W 40/04申请日:20140317|||公开
IPC分类号: H04W40/04(2009.01)I; G06F17/10 主分类号: H04W40/04
申请人: 华中科技大学
发明人: 董燕; 曾冰
地址: 430074 湖北省武汉市洪山区珞喻路1037号
优?#28909;ǎ?/td>
专利代理机构: 华中科技大学专利中心 42201 代理人: ?#21495;?
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

CN201410097200.3

授权公告号:

103916927B||||||

法律状态公告日:

2017.06.13|||2014.08.06|||2014.07.09

法律状态类型:

授权|||实质审查的生效|||公开

摘要

本发明提出了一种基于改进和声搜索算法的无线传感器网络路由方法,包括以下步骤:Step1、初始化算法相关参数HMS、HMCR、PAR以及评价次数eval_Nomax;Step2、利用轮盘赌初始化和声记忆库HM;Step3、评价和声库中各和声路径的适应度;Step4、设置eval_No=0;Step5、设置i=0;Step6、产生候选和声;Step7、eval_No++,若eval_No<eval_Nomax,执行Step8;否则执行Step11;Step8、对和声库中的第i条和声Xi={s,x2,…xj,…,d},进行邻域搜索;Step9、eval_No++,若eval_No<eval_Nomax,执行Step10;否则执行Step11;Step10、i++,若i<HMS,执行Step6;否则执行Step5;Step11、记录和声记忆库中的最优和声路径。本发明的路由方法具有较高的能效,并且能够有效地延长整个网络的生命周期。

权利要求书

权利要求书
1.  一种基于改进和声搜索算法的无线传感器网络路由方法,包括以下步骤:
Step1、初始化相关参数HMS以及评价次数eval_Nomax;
Step2、利用轮盘赌初始化和声记忆库HM;
Step3、计算和声库中各和声(路径)的适应度f(π);
Step4、设置eval_No=0;
Step5、设置i=0;
Step6、产生候选和声并更新和声记忆库;
Step7、eval_No++,若eval_No<eval_Nomax,执行Step8;否则执行Step11;
Step8、对和声库中的第i条和声Xi={s,x2,…,xj,…,d}进行邻域搜索;
Step9、eval_No++,若eval_No<eval_Nomax,执行Step10;否则执行Step11;
Step10、i++,若i<HMS,执行Step6;否则执行Step5;
Step11、记录和声记忆库中的最优和声路径。

2.  根据权利要求1所述的方法,所述Step2中,节点i通信范围内的节点j的选择概率P(i,j)如下:
P(i,j)=Σk∈allowedi(hopk/hopmax+1/Ek)-(hopj/hopmax+1/Ej)(No(allowedi)-1)*Σk∈allowedi(hopk/hopmax+1/Ek)if(j∈allowedi),0otherwise.]]>
式中,hopj表示节点j的跳数,hopk表示节点k的跳数,hopmax表示所有节点中的跳数最大的节点的跳数,Ej表示节点j的剩余能量,Ek表示节点k的剩余能量,allowedi表示可以成为节点i的下一跳的节点集合,No(allowedi)表示集合allowedi的元素数量。

3.  根据权利要求1所述的方法,所述Step6中,所述候选和声,其中:
xj&LeftArrow;xrand(i),jif(P1<HMCR)&&Neib(xj-1){x1,j,x2,j,...,xHMS,j}&NotEqual;?,xj&Element;Neib(xj-1)otherwise.]]>
式中,s代表源节点编号,d代表汇聚节点编号,表示在节点的通信范围内节点的集合,{x1,j,x2,j,…,xHMS,j}表示和声库的第j列,P1为0到1之间的随机数,HMCR为选择概率,xrand(i),j表示在HM的第j列分量中随机选择一个分量,表示在节点的通信范围内随机选择一个节点。

4.  根据权利要求3所述的方法,所述Step6中:
当随机数P1小于和声搜索算法的选择概率HMCR时,候选和声的下一跳从和声记忆 库中选择;否则,随机从当前节点的通信范围内选择未到达过的节点作为下一跳;
如果下一跳节点取自和声记忆库,则判断取是否需要调整:当随机数P2小于调整概率PAR时,对取自和声库中的音调进?#26800;?#25972;,随机从当前节点的通信范围内选择未到达过的节点替换掉被选择的节点作为下一跳,否则,保持被选择的节点做为下一跳;直到到达汇聚节点,其中,P2为0到1之间的随机数。

5.  根据权利要求4所述的方法,所述对取自和声库中的音调进?#26800;?#25972;具体为:
xj&LeftArrow;xj&Element;Neib(xj-1)if(P2<PAR),xjotheerwise.]]>

6.  根据权利要求1所述的方法,所述Step6包括:
Step6.1、计算候选和声的适应度值f(π);
Step6.2、将候选和声与HM中最差的和声进行比较,如果优于该最差和声,则将该最差和声替换出和声记忆库。

7.  根据权利要求1所述的方法,Step8中,通过随机选择路径中的节点,在被选节点的上一跳和下一跳的通信范围交集内随机选择一个未到达过的节点将被选节点替换,从而完成邻域搜索。

8.  根据权利要求1所述的方法,Step8具体包括:
Step8.1、计算邻域搜索得到的和声的适应度值f(π);
Step8.2、将邻域搜索得到的和声与进行邻域搜索之前的和声进行比较,如果优于之前的和声,则将之前的和声替换出和声记忆库。

9.  根据权利要求1所述的方法,其中,和声记忆库中的每条和声的首尾元素分别是源节点和汇聚节点,和声记忆库HM如下:
HM=X1X2&CenterDot;&CenterDot;&CenterDot;Xi&CenterDot;&CenterDot;&CenterDot;XHMS=s&CenterDot;&CenterDot;&CenterDot;x1,j&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;ds&CenterDot;&CenterDot;&CenterDot;x2,j&CenterDot;&CenterDot;&CenterDot;d&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;s&CenterDot;&CenterDot;&CenterDot;xi,j&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;d&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;s&CenterDot;&CenterDot;&CenterDot;xHMS,j&CenterDot;&CenterDot;&CenterDot;d]]>
式中,s代表源节点编号,d代表汇聚节点编号,xi,j表示其它传感器节点编号。

10.  根据权利要求1所述的方法,所述适应度函数模型为:
f(π)=2*(L-1)*Eelec*k+Eamp*k*Σi=1L-1di,i+12EMin*EAvg,]]>
式中,L为路径的长度,Eelec为传输和接受的单元能?#27169;珽amp为传输放大的单元能?#27169;?k为源节点发送的数据包大小,di,i+1表?#38236;趇个节点和第i+1个节点之间的距离,EMin表示路径中剩余能量最少的节点的剩余能量,EAvg表示路径中所有节点的平均剩余能量。

说明书

说明书一种基于改进和声搜索算法的无线传感器网络路由方法
技术领域
本发明属于无线传感器网络技术领域,具体涉及一种改进和声搜索算法的路由方法。
背景技术
无线传感器网络(Wireless Sensor Network,WSN)与传统的因特网以及最近?#25913;?#21457;展?#35813;?#30340;无线自组网(MobileAd Hoc Network)都有着很大程度上的不同。在传统的因特网和Ad Hoc网络中,每个网络节点通常情况下是一台个人电脑或者移动设备,用户使用因特网和Ad Hoc网主要是用来获取网络共享信息,所以不管?#19988;?#29305;网还是AdHoc网络,路由协议设计的目的主要是为了提高服务质量,而不必考虑用户消耗多少能量。无线传感网络则不同,无线传感网络是在检测区域(通常情况下环境十分恶劣或者人无法到达)内散播大量的微型传感器节点,这些传感节点并没有固定的ID,而是通过自组织的方式组成一个传感器网络。无线传感器网络一经?#36866;潰?#20415;获得了社会各界的青睐,应用在军事,医疗,环境等各个领域。
路由算法在无线传感器网络中发挥着重要作用,它对各节点的能耗、整个网络的生命周期以及通信质?#31185;?#30528;关键性的作用。因此,路由算法的研究受到越来越多的关注。由于传感器网络具有能量受限、资源受限、拓?#31169;?#26500;变化频繁等特点,因此,传统的路由机制不能适应无线传感网络,必须设计与之相应的路由算法。
至今,用于无线传感器网络的路由协议主要包括:平面路由协议(Flooding协议、SPIN协议、MTE协议、Directed Diffusion协议)、层次路由协议(LEACH协议)、基于位置信息的路由协议(GAF协议、GEAR协议)以及基于数据流和QoS的路由协议。
目前,基于智能优化算法的路由方法在无线传感器网络技术领域也有了一些应用,主要是基于蚁群算法(Ant Colony Optimization,ACO)的路由方法和基于蜂群算法(Bee Colony Optimization,BCO)的路由方法。
无线传感网络路由协议的研究已经逐渐成为热点,路由协议的研究从简单到复杂,从以数据为中心到高质量要求,并向着智能化方向发展,如何建立高效、自适应的传感路由算法成为当前研究的一个热点。
和声搜索算法是2001年韩国学者Geem等人提出的一种新颖的智能优化算法。算法模拟了音乐演奏中?#36136;?#20204;凭借自己的记忆,通过反复调整乐队中各乐器的音调,最终达到一个美妙的和声状态的过程。和声搜索算法有很强的全局搜索能力,易于收敛到全局 最优解,其流程图如图1所示,执行步骤如?#28388;?#31034;:
Step1:初始化算法相关参数。
初始化HMS(和声记忆库的大小,即种群容量大小)、HMCR(选择概率)、PAR(调整概率)、BW(调整带宽)、评价次数eval_Nomax。
Step2:和声记忆库(Harmony Memory,HM)初始化。
HM=X1X2&CenterDot;&CenterDot;&CenterDot;XHMS=x1,1x1,2&CenterDot;&CenterDot;&CenterDot;x1,nx2,1x2,2&CenterDot;&CenterDot;&CenterDot;x2,n&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;xHMS,1xHMS,2&CenterDot;&CenterDot;&CenterDot;xHMS,n---(1)]]>
在此步骤中,式(1)所示的HM通过在内产生一组随机数来初始化,其中1≤i≤n。从而根据式(2)得到第j个解向量的第i个变量值:
xij=xiL+Random(0,1)×(xiU-xiL)---(2)]]>
上式中,j=1,2,…,HMS,Random(0,1)是0到1之间的随机数。
Step3:计算和声库中各和声的适应度。
Step4:设置eval_No=0。
Step5:即?#25628;?#22863;候选和声。
Step5.1:在此步骤中,一个新的和声向量由三个规则产生:
①记忆选择;
②随机选择;
③音高调整。
产生一个候选和声被称之为即?#25628;?#22863;,先通过规则①和②确定是记忆选择还是随机选择,具体如?#28388;?#31034;:
xj&LeftArrow;xran(d)jijf(P1<HMCR)xj&Element;Ωjotherwise.---(3)]]>
式中,P1为0到1之间的随机数,xrand(i),j表示在HM的第j列分量中随机选择一个分量,Ωj表?#38236;趈个分量的定义域。
Step5.2:每个经过记忆选择得到的音调将被进一步检验决定是否需要音高调整,此操作使用PAR参数,音高调整决策如?#28388;?#31034;:
xj&LeftArrow;xj&PlusMinus;Random(0,1)×BWif(P2<PAR),xjotherwise.---(4)]]>
式中,P2为0到1之间的随机数。
Step5.3:计算候选和声的适应度值f(π);
Step5.4:更新HM。
依据目标函数值,如果候选和声向量优于HM中最差的向量,则新向量取代HM中最差的和声向量,否则不操作。
Step6:检查是否停止迭代。
eval_No++,若eval_No<eval_Nomax,执行Step5;否则执行Step7。
Step7:记录和声库中的最优解。
然而,传统的和声搜索算法不能直接用于无线传感器网络路由。
发明内容
鉴于此,本发明的目的在于提出一种基于改进和声搜索算法的无线传感器网络路由方法,通过对路径适应度模型进行改进,使得该协议在能效以及延长整个无线传感器网络寿命方面具有极大的优越性。
本发明采用以下技术方案以实现上述发明目的:
一种基于改进和声搜索算法的无线传感器网络路由方法,包括以下步骤:
Step1、初始化算法相关参数HMS、HMCR、PAR以及评价次数eval_Nomax;
Step2、利用轮盘赌初始化和声记忆库HM;
Step3、计算和声库中各和声(路径)的适应度;
Step4、设置eval_No=0;
Step5、设置i=0;
Step6、产生候选和声并更新和声记忆库;
Step7、eval_No++,若eval_No<eval_Nomax,执行Step8;否则执行Step11;
Step8、对和声库中的第i条和声Xi={s,x2,…,xj,…,d}进行邻域搜索;
Step9、eval_No++,若eval_No<eval_Nomax,执行Step10;否则执行Step11;
Step10、i++,若i<HMS,执行Step6;否则执行Step5;
Step11、记录和声记忆库中的最优和声(路径)。
与现有技术相比,本发明具有以下有益效果:路由算法具有较高的能效,并且能延长整个网络的生命周期。本发明的技术效果还将在具体实施方式的阐述中得到进一步体现。
附图说明
图1为传统HS算法流程图;
图2为本发明实施例中改进的和声搜索算法求解WSN最优路径的流程图;
图3为本发明实施例中改进和声搜索算法的候选路径生成流程图;
图4为本发明实施例中改进和声搜索算法的路径邻域搜索流程图;
图5为本发明实施例中和声库初始化示意图;
图6为本发明实施例中候选和声生成示意图;
图7为本发明实施例中路径邻域搜索示意图;
图8为本发明实施例中随机生成100个节点的WSN场景;
图9为本发明实施例的改进和声搜索算法(IHS)与蚁群算法平均适应度的收敛情况对?#21462;?
具体实施方式
为使本发明的目的、技术方案和优点更加清楚,下面将参考附图并结合实例来详细说明本发明。
本发明针对无线传感器网络路由的特点,对传统和声搜索算法进行改进,改进和声搜索算法进行WSN路由的流程图如图2所示,具体包括以下内容:
(1)和声记忆库的初始化
在传统和声搜索算法中,和声记忆库中的每条和声必须要求维数相同,如式(1)所示。在本发明实施例中,和声记忆库中的每条和声是通过轮盘赌产生的,它们的维数可以不相同,每条和声的首尾元素分别是源节点和汇聚节点,HM如式(5)所示。
HM=X1X2&CenterDot;&CenterDot;&CenterDot;Xi&CenterDot;&CenterDot;&CenterDot;XHMS=s&CenterDot;&CenterDot;&CenterDot;x1,j&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;ds&CenterDot;&CenterDot;&CenterDot;x2,j&CenterDot;&CenterDot;&CenterDot;d&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;s&CenterDot;&CenterDot;&CenterDot;xi,j&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;d&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;&CenterDot;s&CenterDot;&CenterDot;&CenterDot;xHMS,j&CenterDot;&CenterDot;&CenterDot;d---(5)]]>
式中,s代表源节点编号,d代表汇聚节点编号,xi,j表示其它传感器节点编号。
由上式可以看出,和声库中的各和声的长度(?#27425;?#25968;)可能不相同。
(2)候选和声的产生
候选和声的产生如图3所示,其中:
xj&LeftArrow;xrand(i),jif(P1<HMCR)&&Neib(xj-1){x1,j,x2,j,...,xHMS,j}&NotEqual;?,xj&Element;Neib(xj-1)otherwise.---(6)]]>
式中,表示在节点的通信范围内节点的集合,{x1,j,x2,j,…,xHMS,j}表示和声库的第j列,P1为0到1之间的随机数,xrand(i),j表示在HM的第j列分量中随机选择一个分量,表示在节点的通信范围内随机选择一个节点。
当随机数P1小于和声搜索算法的选择概率HMCR时,候选和声的下一跳从和声记忆库中选择;否则,随机从当前节点的通信范围内选择未到达过的节点作为下一跳。
如果下一跳节点取自和声记忆库,则需要判断其是否需要调整:当随机数P2小于调整概率PAR时,对取自和声库中的音调进?#26800;?#25972;,随机从当前节点的通信范围内选择未 到达过的节点替换掉被选择的节点作为下一跳,否则,保持被选择的节点做为下一跳。如果下一跳节点仅取自当前节点的通讯范围,与和声库无关,则无需调整。?#28304;?#31867;推,直到到达汇聚节点。
其中,对候选和声中取自和声库中的音调进行的调整如下:
xj&LeftArrow;xj&Element;Neib(xj-1)if(P2<PAR),xjotheerwise.---(7)]]>
式中,P2为0到1之间的随机数。
(3)邻域搜索
如图4所示,对和声库中的第i条和声Xi={s,x2,…,xj,…,d}进行邻域搜索,数学模型如下:
xj&LeftArrow;xj&Element;(Neib(xj-1)Neib(xj+1))if(Neib(xj-1)Neib(xj+1)&NotEqual;?),xjotherwise.---(8)]]>
该领域搜索方法能显著提高算法的收敛速度。
(4)路径的适应度函数模型
本发明实施例中,无线传感器网络路由的路径适应度函数模型如式(9)所示,使用该模型能使路由算法有较高的能效,并且能延长整个网络的生命周期,特别是针对各节点初始总能量不相同的情况。
f(π)=2*(L-1)*Eelec*k+Eamp*k*Σi=1L-1di,i+12EMin*EAvg---(9)]]>
式中,分子为无线电能耗模型,分母为路径中节点的剩余能量指标。L为路径的长度,Eelec为传输和接受的单元能?#27169;?#21462;值为50nJ/bit,Eamp为传输放大的单元能?#27169;?#21462;值为100pJ/(bit*m2),k为源节点发送的数据包大小,di,i+1表?#38236;趇个节点和第i+1个节点之间的距离,EMin表示路径中剩余能量最少的节点的剩余能量,EAvg表示路径中所有节点的平均剩余能量。
具体而言,本发明实施例的方法包括以下步骤:
Step1、初始化算法相关参数HMS、HMCR、PAR以及评价次数eval_Nomax。
Step2、利用轮盘赌初始化和声记忆库HM。
利用轮盘赌初始化和声记忆库时,节点i通信范围内的节点j的选择概率P(i,j)如?#28388;?#31034;:
P(i,j)=Σk&Element;allowedi(hopk/hopmax+1/Ek)-(hopj/hopmax+1/Ej)(No(allowedi)-1)*Σk&Element;allowedi(hopk/hopmax+1/Ek)if(j&Element;allowedi),0otherwise.---(10)]]>
式中,hopj表示节点j的跳数,hopk表示节点k的跳数,hopmax表示所有节点中的跳数最大的节点的跳数,Ej表示节点j的剩余能量,Ek表示节点k的剩余能量,allowedi表示可以成为节点i的下一跳的节点集合,No(allowedi)表示集合allowedi的元素数量。
通过该选择概率,可以使初始路径以较大的概率选择靠近汇聚节点并且剩余能量较多的节点,和声记忆库的初始化示意图如图5所示。
Step3、计算和声库中各和声(路径)的适应度f(π)。
Step4、设置eval_No=0。
Step5、设置i=0。
Step6、产生候选和声并更新和声记忆库。
候选和声的生成示意图如图6所示,从图6可以看出,候选和声的第一个节点为源节点,选择下一跳时,r1<HMCR,并且r2>PAR,因此,算法随机从和声库的第二列选择源节点通信范围内的节点(这里的示例选择节点31)做为下一跳;选择第三个节点时,r1>HMCR,因此,算法随机从节点31的通信范围内选择一个没有到达过的节点(这里的示例选择33)做为下一跳;?#26469;?#31867;推,可以得到候选和声如图6所示。
Step6.1、计算候选和声的适应度值f(π);
Step6.2、将候选和声与HM中最差的和声进行比较,如果优于该最差和声,则将该最差和声替换出和声记忆库。
Step7、eval_No++,若eval_No<eval_Nomax,执行Step8;否则执行Step11。
Step8、对和声库中的第i条和声Xi={s,x2,…,xj,…,d}进行邻域搜索。
邻域搜索示意图如图7所示,通过随机选择路径中的节点,在被选节点的上一跳和下一跳的通信范围交集内随机选择一个未到达过的节点将被选节点替换,从而完成邻域搜索。对于图中的路径,选择了第71个节点进行邻域搜索,从图中可以看出,节点71的上一跳节点33和下一跳节点80的通信范围交集中包括节点63、64、65、71、82,因此,算法随机从中选择一个节点(这里的示例选择节点63)替代节点71完成邻域搜索。
Step8.1、计算邻域搜索得到的和声的适应度值f(π)。
Step8.2、将邻域搜索得到的和声与进行邻域搜索之前的和声进行比较,如果优于之前的和声,则将之前的和声替换出和声记忆库。
Step9、eval_No++,若eval_No<eval_Nomax,执行Step10;否则执行Step11。
Step10、i++,若i<HMS,执行Step6;否则执行Step5。
Step11、记录和声记忆库中的最优和声(路径)。
本发明的效果可以通过以?#36335;?#30495;实验和比较进一步验证:
选取图8所示的WSN场景,将本发明中的改进和声搜索算法(IHS)与蚁群算法(ACO)进行比较。编程语言为C++,计算机配置为:intel I7-3610QM处理器、8GB内存、2GB独显、windows764位操作系统的?#22987;潛镜?#33041;。场景中各节点的横坐标和纵坐标分别如表1和表2所示,各节点的初始总能量如表3所示。
表1WSN各节点的横坐标
NoX轴坐标NoX轴坐标NoX轴坐标NoX轴坐标NoX轴坐标11038.06369921288.4861554193.88056261108.57070781332.1414752470.015997221070.806875421000.75877262350.73565482434.1614403796.02294023663.76497843684.10891463260.47248783877.4995864760.39498824141.22877044130.02869564581.33525484927.1956655451.99894325950.243855451032.18068565918.53607385757.365042673.15748526700.4440534680.002362661014.10482586510.7607227268.72079727551.8713454770.39419867807.03844387697.026192818.31038128200.71590548810.72084768360.427584881050.6486019506.4714692940.23336549370.54831369322.96472889181.47763110830.16084630232.45138950500.48734970772.97746190657.99549211225.38303131402.77661851847.99588771958.54169791746.17012212586.07711432674.1728795254.363618721060.10349192676.35432213180.533438331083.70973353900.19572973100.01349593335.76977914316.65965134178.97901854785.70519874543.69362894407.49545215615.10214335760.68684855499.78426175119.20077295164.82500816825.980727361004.31020256617.93801876276.03343196880.46734217936.45729837518.06624457450.61291377978.14922997560.71738518191.84707238150.59988158200.69871578172.27611998374.31778319467.88909539850.39458759610.97665879103.61320799815.72644820966.26669040500.090378601025.53781980599.772413100236.224196
表2WSN各节点的纵坐标
NoY轴坐标NoY轴坐标NoY轴坐标NoY轴坐标NoY轴坐标1881.51426921199.33239841321.10526261426.254537811010.4747192900.139546221069.79199542700.61291962424.62907282650.2991093899.92088423801.70761743358.62070663412.72979283946.8408834410.73208524200.40075544125.72956864433.35073784450.8596895385.64646025911.14285145978.11691065682.60600585677.851248666.06706026900.85777346740.034856661063.60513686185.1540717913.267222271000.79188147801.88203967226.18258887995.0575498482.81271228680.13567148805.29855668343.50078988788.639293
9614.03210829595.27888949910.79842969288.81526889871.88171310721.78793430100.73350850460.71238970303.12805590115.568055111000.45584631501.79173651101.35646171186.41699991770.73448012560.21586632580.01401852374.8518077220.03396092496.31248913775.61961933111.45328553863.58455673525.22215493111.02979214650.65116834486.84347354133.82587274267.78859494212.91374115952.03254435545.07340055339.55510975945.64430995350.25258016465.95168136150.193973561047.64238276521.87226596250.71296817126.03131837693.61235657750.81690277982.08218397791.56435818166.5251703850.08470358272.840217781065.78551198830.83704819253.99947139350.30944159710.14658779646.61687999615.34893620780.70114440531.9497806090.65676180179.078778100583.095624
表3WSN各节点的初始能量(单位:J)
No初始能量No初始能量No初始能量No初始能量No初始能量1189.09921100.38141151.73561119.72481155.0742129.25822153.19742102.07262199.35982140.5933164.16523187.91843179.55363159.13383146.9134156.90524192.09644161.19964182.57484124.8125145.43925141.02645125.34365157.61985194.0466152.18126100.42146101.68566185.37986147.0327147.10827181.94847128.18467126.37487147.5818170.32728173.42448146.52268131.69088192.7379166.27729195.27949154.79669177.45689190.84710162.81030177.53250119.76170165.13390123.87511126.44731127.32351166.58871146.88391108.46612106.64132118.31152117.69872158.25192156.35913110.29133184.16153189.34973131.39193199.63414143.95334140.44054150.17274108.93994183.13915127.23535149.32155138.17975179.27295120.12716120.25236121.89456119.30676127.66296114.15417175.65537159.42357120.71077149.40697164.48318166.97338172.44258191.47978198.21298124.05519187.79339132.49659176.26379115.29399140.37320189.00140177.22160114.59480106.696100176.168
蚁群算法的节点选择概率pk(r,s)如?#28388;?#31034;:
pk(r,s)=[T(r,s)]α[E(s)]βΣu&NotElement;Mk[T(r,u)]α[E(u)]βif(s&NotElement;Mk),0otherwise.---(11)]]>
式中,T(r,s)是路径(r,s)上的信息素,E(s)是节点s的剩余能量,Mk是蚂蚁k的禁忌表。
信息素更新模型如?#28388;?#31034;:
ΔTk=1(2-EMink/EAvgk)*Fdk---(12)]]>
式中,EMink为第k条路径中剩余能量最少的节点的能量,EAvgk为第k条路径中节点的平均剩余能量,Fdk为第k条路径的节点数量。
该信息素更新模?#22270;?#32771;虑了能效也考虑了整个网络的生命周期,对于蚁群算法,所得的效果较好。
对于图8所示的WSN场景,改进和声搜索算法和蚁群算法的相关参数设置如表4所示,表中,两种算法的算法参数均为近优值;路径的适应度函数模型如式(9)所示。
表4两种算法的相关参数设置

图8中,五角星表示的节点为源节点,倒三角表示的节点为汇聚节点。两种算法的运行结果比较如图9所示,横轴表?#38236;?#20195;次数,纵轴表示50次独立运行后每代种群的平均适应度均值。
从图9可以看出,IHS算法的效果要明显好于ACO算法的效果,IHS算法得到的路径更节能,并且路径中节点的剩余能量更多。
IHS算法所得的最优路径适应度为8.88593e-006,路?#31471;?#28040;耗的能量为0.136J,路径的跳数为15,对应的最优路径为:6→44→18→21→69→68→5→50→64→92→35→99→10→65→20→88。
ACO算法所得的最优路径适应度为9.27144e-006,路?#31471;?#28040;耗的能量为0.143J,路径的跳数为17,对应的最优路径为:6→38→30→93→21→69→68→5→50→64→92→35 →99→10→65→20→42→88。
由上可见,IHS算法所得的最优路径较ACO算法所得的最优路径能节省4.9%的能量,并且能减少11.8%的跳数,传输时延更小。
以上证明了IHS算法在指定源节点的情况下,能比ACO算法?#19994;?#26356;好的路径。为了比较两种算法在整个网络生命周期的表现情况,利用两种算法分别对图8所示的WSN场景进行路由循环,各节点的初始总能量如表3所示,相关参数设置如表5所示,分别记录下第一个节点死亡所经历的周期数,结果如表6所示。
表5两种算法的相关参数设置

表6两种算法在WSN生命周期的比较

从表6可以看出,与利用ACO算法路由相比,利用IHS算法进行路由能使整个WSN的生命周期延长40.8%。因此,IHS算法优于ACO算法。
以上所述仅为本发明的较佳实施例而已,并不用以限制本发明,凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等,均应包含在本发明的保护范围之内。

关于本文
本文标题:一种基于改进和声搜索算法的无线传感器网络路由方法.pdf
链接地址:http://www.pqiex.tw/p-6115647.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
平码五不中公式规律 爱彩乐陕西十一选五官网 江西多乐彩今天开奖号 山西11选5中奖规则及奖金 澳洲幸运10全天计划群 双色球开奖历史 北京11选5通三 石家庄中彩票 河南十一选五加奖 澳洲幸运10是哪里开奖 广西十一选五基本走势图