基于改进蚁群算法的非均匀分簇自适应路由协议_陈辉.pdf
《基于改进蚁群算法的非均匀分簇自适应路由协议_陈辉.pdf》由会员分享,可在线阅读,更多相关《基于改进蚁群算法的非均匀分簇自适应路由协议_陈辉.pdf(10页珍藏版)》请在咨信网上搜索。
1、第 卷 第 期 年 月传 感 技 术 学 报 .项目来源:国家自然科学基金项目();安徽省教育厅重点教学研究项目()收稿日期:修改日期:,(,):,:;:基于改进蚁群算法的非均匀分簇自适应路由协议陈 辉,王 旭(安徽理工大学计算机科学与工程学院,安徽 淮南)摘 要:针对无线传感器网络中出现的节点能耗不均和热区问题,提出一种基于改进蚁群算法的非均匀分簇自适应路由协议。首先,根据节点与基站的相对距离和通信范围内节点密度选举出候选簇头,然后在候选簇头竞争半径范围内进行正式簇头的选取。其次,在节点入簇过程中,考虑共同边缘节点以及非均匀分簇网络特性,通过具有动态权重系数的代价函数形成合理的分簇结构;最后
2、,通过在蚁群算法中使用改进的动态转移策略和局部与全局相结合的信息素更新规则,同时引入动态信息素挥发系数以提高路由算法的寻优能力,并避免陷入局部最优。仿真结果表明:所提算法能够有效地均衡网络能耗、缓解基站附近的热区问题,从而提高网络生命周期与吞吐量。关键词:无线传感器网络;非均匀分簇;蚁群算法;路由协议中图分类号:文献标识码:文章编号:()无线传感器网络(,)现已广泛应用于目标区域监测、工业控制等诸多领域,在物联网技术的发展与应用中发挥了至关重要的作用。中节点通常以电池供电且能量无法补充,所有节点均需将收集到的数据发送至基站,这导致了基站附近存在网络数据传输热区问题。因此,如何提高路由算法的节能
3、性与负载均衡性成为了 领域学者们研究的热点。目前,国内外学者在经典路由算法的基础上进行了大量研究工作,文献将经典的分簇路由协议 的全局单跳路由改进为根据节点间的通信距离来确定单跳或多跳路由的方式,但未考虑到 协议中簇头选举具有一定的随机性。文献基于欧式距离对网络节点实现 聚类,再通过蚁群路由选择最优路径来降低能量开销,但忽略了 算法对初始聚类中心的敏感性。文献提出使用混合模拟退火和粒子群两种优化算法来选择初始聚类中心,但此类算法仅仅在聚类中心的选取上进行了调整,未改进网络的分簇结构。文献基于模糊逻辑聚类方法实现非均匀分簇,第 期陈 辉,王 旭:基于改进蚁群算法的非均匀分簇自适应路由协议 达到负
4、载均衡和能耗最小化的目标,但未考虑网络分簇过程中节点位置对网络性能的影响。文献提出将分布式算法和集中式算法相结合来优化簇首选举,同时将网络区域划分为内部和外部区域,将节点分配到每个扇区来降低簇间通信能耗,但未考虑到节点成簇过程对网络分簇结构的影响。对此,文献在节点成簇阶段提出了成簇评估函数来考虑普通节点与簇头节点的距离,同时加入了簇头节点的剩余能量,提高了分簇结构的合理性,但此类文献并未对路由过程进行动态规划。文献较早把蚁群算法应用到路由动态规划中,通过改进的概率转移公式以及设定信息素阈值进行路径选择,但该算法会导致节点间存在多余的网络能量开销和延迟。文献使用人工蜂群算法来优化初始聚类中心后,
5、在路由阶段引入了基尼系数来衡量网络分簇的能量均衡性,从而降低路径之间的能耗差距,但该算法寻找最优路径的能力较弱。文献使用蝴蝶优化算法来选举初始聚类中心,在蚁群路由算法中,加入距离、剩余能量以及节点密度来改进概率选择公式,提高了算法对最优路径的寻找能力。文献通过考虑节点的平均剩余能量和蚂蚁经过的跳数来设计蚁群算法中的信息素增量,提高了寻找较优路径的速度,但该算法在路由过程易陷入局部最优。文献通过考虑数据的传输距离、方向以及节点剩余能量来改进蚁群算法中的启发函数,通过考虑路径上节点的平均剩余能量来改进信息素增量,但该算法存在收敛速度较慢的问题。综上所述,对 路由算法的相关研究能够在一定程度上降低网
6、络能耗且延长网络生命周期,但仍存在簇头选取质量较低、未充分考虑节点入簇过程对网络结构的影响,同时在使用蚁群算法改进路由的过程中仍存在易陷入局部最优和收敛速度较慢的问题。因此,为均衡网络能耗和改善 网络的生存周期,提出了基于改进蚁群算法的非均匀分簇自适应路由协议(,)。该路由协议考虑全局范围内候选簇头的分布位置与数量,再通过自适应加权的目标函数提高正式簇头节点的质量;在入簇过程中,重点考虑了共同边缘节点与权重关系设计了代价函数,改善分簇效果;在路由选择过程中,采用了动态转移策略进行路径搜索,设计结合局部更新与全局最优路径更新的两种信息素更新方式来避免算法陷入局部最优,同时引入动态信息素挥发系数来
7、解决算法收敛速度较慢的问题,从而达到降低网络能耗,缓解基站附近热区问题的目的。系统模型 网络模型假设网络以随机部署的方式将 个传感器节点置于 的目标区域内,对网络模型做出以下设定:网络由 个传感器节点和位于目标区域外围的基站构成,节点通过随机部署的方式形成监测网络,基站能量与计算能力充足;网络内节点同构,地位平等,均具有唯一的节点标识;节点能够根据 模型获得周围节点信息和与基站的距离;节点能够根据通信距离调整传输功率。能耗模型 中节点能量消耗主要用于节点间的数据发送与接收,本文采用的无线通信能量消耗模型与文献相同。传感器发送 比特信息到距离为 的节点所需要的能耗计算公式如下:(,)()传感器接
8、收 比特信息的能耗计算公式如下:()式中:为传感器节点传输单位 信息的能耗,、分别为自由空间、多径衰落能耗模型下的电路损耗系数,距离阈值 。算法描述 簇头选举簇头选举质量直接影响网络数据传输的有效性和网络的寿命。现有路由算法在簇头选举阶段,存在选举后的簇头位置分布不均以及簇头节点质量不高等问题。算法簇头选举分为两个阶段,首先基于 协议簇头选举方法,在阈值公式中加入了节点相对距离和相对密度,以选举出分布与数量更为合理的候选簇头;之后在候选簇头的基础上,结合节点的竞争半径并考虑簇内通信距离和节点能量等因素来竞争正式簇头,实现最优簇头的选举。候选簇头选举候选簇头数目根据文献确定,最优候选簇头数为:(
9、)式中:为节点个数,为区域边长,为基站到网络中节点的平均距离。候选簇头节点选举的目的是为了在全局范围内传 感 技 术 学 报第 卷确定簇头节点的分布范围,提高正式簇头分布位置的合理性。因此,在候选簇头节点的阈值公式中加入了节点相对距离和节点相对密度因素,阈值计算如下:()()()|()式中:为网络中候选簇头节点所占的比例,为候选簇头节点选举的轮数,当候选簇头数达到最优簇头数时,停止候选簇头竞选,为节点的相对距离,为节点的相对密度,、为权重系数,且,为未当选候选簇头节点的集合。其中节点相对距离 和相对密度 的计算如下:(,)()()式中:、分别表为网络内节点与基站距离的最大值、最小值,(,)为节
10、点 与基站的距离,为节点 通信范围内邻居节点的数量,为节点的数量。通过在选举候选簇头阈值公式加入节点相对距离和节点相对密度因素后,当节点距离基站较远或节点附近邻居节点数较少时,计算出的阈值会较低,使得选举出的候选簇头分布呈现距离基站较近位置数量较多,距离基站较远位置数量较少,且候选簇头位于节点较为密集处。节点竞争半径候选簇头节点选举完成后,为提高正式簇头的质量以及改善网络分簇结构,对当前候选簇头节点设置一个合理的竞争半径,在候选簇头竞争半径内进行正式簇头的竞选,并根据竞争半径形成非均匀分簇网络结构,竞争半径计算公式如下:(,)|()式中:、分别为目标区域内传感器节点与基站的最小、最大距离,(,
11、)表示节点 与基站之间的距离。为控制取值范围的参数,为节点最大竞争半径。簇头选举 为保证簇头的分布与数量的合理性,采用在候选簇头节点的竞争范围内所有节点根据计算目标函数值来确定正式簇头,目标函数综合考虑节点剩余能量、节点平均距离以及节点密度三个指标。其中节点 的能量因子()计算如下:()()()()式中:()为节点的 的剩余能量,为节点 竞争半径内的邻居节点数量。距离因子()的计算如下:()()式中:为节点 所在候选簇头竞争范围内节点数,为节点、间的距离。综合考虑以上两个指标以及节点相对密度,构造正式簇头节点选举的目标函数:()()()()随着网络运行阶段的改变,节点的剩余能量逐渐下降,而能量
12、因子又是整个网络运行周期的决定性因素。因此,随着网络的运行,能量对网络运行的影响逐渐增大,对应在簇头轮换过程中,能量在目标函数所占的权重也应逐渐加大。通过动态权重系数调整目标函数,来缓解网络运行中期能量利用率下降和网络中节点失效速度加快的问题。能量权重系数采用与文献相同方式进行更新:|()式中:为节点 的初始能量,为节点 的剩余能量,表示节点 的相对剩余能量。随着网络运行时间的增加,节点与簇内平均节点能量下降,逐渐增大。距离因子与节点密度因子的权重系数计算如下:()网络运行阶段,为避免频繁进行簇头轮换导致能量浪费,簇头节点通过式()判断是否需要进行簇头轮换:()()()式中:()为当前簇头节点
13、的目标函数值,()为对应簇内普通节点的最大目标函数值,(,),用来控制簇头节点轮换的频率。若式()成立,则需要进行簇头节点的轮换,由当前簇头节点指定节点 成为下一轮簇头节点,并将簇内成员信息发送至下一任簇头节点。节点成簇簇头节点确定后,现有路由算法的成簇方式主第 期陈 辉,王 旭:基于改进蚁群算法的非均匀分簇自适应路由协议 要是普通节点加入最近的簇头节点,目的是缩短簇内通信距离,从而降低簇内通信能耗。但该策略会导致基站周围簇头节点的数据转发任务过多的同时,需要维护较多数量簇内节点的数据收集任务,不利于均衡网络能耗。为形成合理的非均匀分簇结构,路由协议采用计算代价函数值的方式确定普通节点的簇头,
14、对代价函数中影响因子的权重根据网络运行阶段的不同进行适当调整来改善分簇结构,使得靠近基站的簇规模较小,从而为转发其他簇头的信息预留能量。同时,增大距离基站较远簇的规模也能够降低较远位置信息传输的次数,减少网络能耗。为形成合理的非均匀分簇网络结构,本文路由算法在成簇阶段综合考虑能量因素、普通节点与簇头和基站的距离。代价函数设定如下式:(,)()式中:为节点 与簇头节点 的距离,为簇头节点 的剩余能量,为簇头节点 的竞争半径。首先,普通节点在入簇过程中考虑与簇头节点的距离,避免加入距离过远的簇头节点而增加通信能耗,因此 越大,代价越大。其次,簇头节点的剩余能量较低会导致该簇头节点将数据传递到基站存
15、在一定风险,从而降低网络工作效率,因此 越小,代价越大。图 共同边缘节点示意图定义处于两簇头节点之间且与两簇头节点、的距离满足,则节点 为两簇头节点、的共同边缘节点。共同边缘节点处于相邻簇的边缘位置,此时计算代价函数会因为节点到下一跳节点的距离以及下一跳节点的剩余能量差异较小,入簇时的选择具有一定的随机性。因此,为使共同边缘节点优先加入簇头竞争半径更大的簇内,在代价函数中加入了簇头节点的竞争半径,竞争半径越小,代价越大。共同边缘节点示意图如图 所示。随着网络运行轮数的增加,网络内簇头节点平均能量下降,入簇阶段逐渐加大簇头节点能量的权重,距离因子与节点竞争半径权重取相同值。代价函数中的权重系数计
16、算如下式:|()()改进的蚁群路由算法针对现有的蚁群算法在路由过程中仍存在簇间能耗不均、容易陷入局部最优的问题,在路由阶段采用了一种改进的蚁群路由算法,主要包括转移策略的确定、局部信息素更新、全局信息素更新和信息素挥发系数调整四个步骤。动态转移策略基于蚁群算法的路由协议中多数采用既定的状态转移概率函数,导致蚁群算法在路径选择的过程中全局搜索能力较弱,并且在路由初始阶段,依赖各路径间的信息素与局部启发函数并不能够在短时间内寻找到最优路径。为此采用了动态转移策略,通过设定阈值系数 来确定选择下一跳节点的策略。在寻径蚂蚁寻找中继节点的过程中,当前所在簇头节点产生一个随机数,根据随机数与阈值系数的比较
17、确定下一跳节点的选择策略,公式如下:()()()()()()()()()|()式中:为动态转移策略,()为概率转移函数,()为 时刻节点,之间的路径所含信息素浓度,()为 时刻节点,之间路径的局部启发函数,集合 为第 只蚂蚁可选的下一跳节点,、分别为信息素和启发函数的权重。在路由阶段,如果未考虑路径上节点的相对剩余能量会导致当前最优路径上的节点能量快速耗尽,节点提前死亡。在路由过程中,需要同时考虑当前节点与下一跳节点的距离以及下一跳节点到基站的距离,来保证数据高效地向基站方向传输。为有效均衡路径选择过程中的能量与距离因素,设计了新的局部启发函数,公式如下:(,)()传 感 技 术 学 报第 卷
18、式中:表示节点初始能量,表示网络内节点的平均能量,为下一跳节点 的剩余能量,、(,)分别表示节点、之间的距离和下一跳节点 与基站的距离。信息素更新蚁群路由算法中,首先初始化网络中各路径间的信息素浓度,寻径蚂蚁从源节点出发根据概率转移函数寻找最优路径到达基站并记录经过节点的信息,到达基站后由回退蚂蚁沿该条路径返回源节点完成一轮信息素的更新。为提高网络中各节点之间信息素浓度的合理性,提出新的信息素更新规则,在避免陷入局部最优的基础上,加快收敛速度。局部信息素更新寻径蚂蚁 在节点 上选择下一跳节点 后,立即对该路径上的信息素浓度进行局部更新,可以为同一轮后面的寻径蚂蚁提供一定的参考,局部信息素的更新
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 改进 算法 均匀 自适应 路由 协议 陈辉
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。