负载均衡的无线传感器节点重部署算法_孙环.pdf
《负载均衡的无线传感器节点重部署算法_孙环.pdf》由会员分享,可在线阅读,更多相关《负载均衡的无线传感器节点重部署算法_孙环.pdf(7页珍藏版)》请在咨信网上搜索。
1、基金项目:国家自然科学基金资助项目(61671165),桂林电子科技大学研究生教育创新计划资助项目(2018YJCX39)收稿日期:2021-05-17 修回日期:2021-05-24 第 40 卷 第 4 期计 算 机 仿 真2023 年 4 月 文章编号:1006-9348(2023)04-0386-06负载均衡的无线传感器节点重部署算法孙 环,陈宏滨(桂林电子科技大学信息与通信学院,广西 桂林 541004)摘要:近年来,节点部署优化问题引起了越来越多的研究者的关注。针对无线传感器网络节点部署中存在的网络负载不均衡问题,提出了一种无线传感器网络中负载均衡的节点重部署(Load Balan
2、ced Node Redeployment,LBNR)算法。算法在网络初始化之后,利用 K-means 算法进行分簇,引入冗余节点,对负载大的簇进行拆分,对负载小的簇进行簇成员节点调整。其中,在减小簇规模阶段,利用帝王蝶优化算法对冗余节点进行移动,以进行簇拆分;在增大簇规模阶段,采用邻近运动方式,进行簇成员调整。上述算法通过有效地移动节点,均衡了网络负载,提高了网络能量使用效率。而且与其它节点部署方案相比,研究提出的方案采集数据量明显增加,网络负载更均衡,传感器网络的生命周期显著延长。关键词:无线传感器网络;节点重部署;负载均衡;帝王蝶优化;冗余节点中图分类号:TP393 文献标识码:BLoa
3、d Balancing Node Redeployment Algorithm Based onMonarch Butterfly OptimizationSUN Huan,CHEN Hong-bin(School of Information and Communication,Guilin University of Electronic Technology,Guilin Guangxi 541004,China)ABSTRACT:In recent years,node deployment optimization has attracted more and more resear
4、chers attention.ALoad Balanced Node Redeployment(LBNR)algorithm for wireless sensor networks is proposed to solve the problemof network Load imbalance in Node deployment.After network initialization,this algorithm uses the K-means algo-rithm to divide clusters,introduces redundant nodes,splits the c
5、lusters with large load,and adjusts the cluster mem-ber nodes for the clusters with small load.In the stage of reducing the cluster size,the Monarch Butterfly optimizationalgorithm is used to move the redundant nodes to split the clusters.In the stage of increasing the cluster size,thecluster member
6、s are adjusted by the adjacent motion.By effectively moving nodes,the algorithm balances the networkload and improves the efficiency of network energy use.Moreover,compared with other node deployment schemes,the proposed scheme significantly increases the amount of data collected,the network load is
7、 more balanced,and thelife cycle of the sensor network is significantly prolonged.KEYWORDS:Wireless sensor network(WSN);Node redeployment;Load balancing;Monarch butterfly optimiza-tion;Redundant nodes1 引言无线传感器网络(Wireless Sensor Networks,WSN)是由传感器节点以无线通信的方式,在监测区域内形成的自组织网络1。至今,无线传感器网络在军事、智慧交通、健康医疗2,3等
8、方面越来越普及。通常情况下,大量的无线传感器节点随机部署在监测区域内,随着网络的运行,不可避免地产生网络负载不均衡问题。通过优化传感器节点的部署位置,可以有效地均衡网络负载,延长网络生命周期。近年来,许多学者对此问题进行了研究。由于传感器节点的可用资源有限,且在某些场景不能及时进行补充,因此需要对传感器节点的能量使用效率和部署进行优化。目前有许多研究者提出通过聚类技术均衡网络能耗,延长网络生命周期4,5。但当网络采用聚类技术之后,683在网络进行数据采集过程中,网络能耗和网络负载不均衡问题依然是延长网络生命周期的重要问题。文献6提出了一种新的基于能量感知的分层双层能源收集辅助的 WSNs 节点
9、部署方案。该方案考虑了节点:常规电池供电的传感器节点和具有能量采集辅助数据的中继节点。根据概率密度函数,研究了最小神经网络个数,以最小化网络能耗。文献7提出了一种有效的负载均衡数据采集方案,该方案通过选择一组中继节点,引入移动汇聚节点,优化汇聚节点的移动路径,平衡网络负载,延长网络生命周期。文献8根据提高无线传感器网络生命周期的两种主要技术:最优的传感器激活;基于压缩感知的有效数据采集和转发,提出了一种迭代解决能量平衡问题的替代方法,有效地均衡了网络能量。文献9提出了一种新颖的 WSNs 数据传输负载均衡策略,即基于超级链路的数据引流,充分利用硬件更强大、通信能力更强的超级节点,实现数据流量的
10、再分配。与传统的被动的晚期补救方法不同,这是一种积极的早期干预策略。但该策略对于基于部署的策略,通常在sink 周围部署额外的节点,以缓解 sink 周围节点的负载,没有考虑距离 sink 距离远的节点负载。为了解决 WSN 节点部署问题,近年来,有许多研究者采用智能优化算法来处理10。文献11通过利用粒子群优化算法有效地处理 WSN 节点部署优化问题,但粒子群优化算法迭代效率低,容易陷入局部最优值。在此基础上,文献12提出了一种全局优化的传感器节点部署策略,即基于蚁狮优化算法的无线传感器网络节点部署方案。首先该方案以传感器节点覆盖目标区域为目的,建立了相应的数学模型。然后将节点部署的优化问题
11、转化为求函数最大值的问题。最后利用蚁狮算法得到最佳节点部署位置。但上述文献未考虑网络的实际负载以及能量消耗情况,部署后的节点由于可使用的能量有限,会出现网络负载不均衡问题。针对上述网络负载不均衡问题,本文综合考虑了节点初始部署后的网络负载和能量消耗,提出了一种负载均衡的无线 传 感 器 网 络 节 点 重 部 署(LoadBalancedNodeRedeployment,LBNR)算法。该算法主要对负载大的簇进行拆分,负载小的簇进行簇成员节点移动。在网络完成初始化之后,利用 k-means 算法13对网络中所有节点进行分簇,引入冗余节点14,冗余节点一开始处于休眠状态,根据平均簇负载大小,判别
12、出重载簇和轻载簇,计算出最优簇头数,对传感器节点进行重部署。在减小簇规模阶段,利用帝王蝶优化算法15对冗余节点进行移动,以冗余节点为簇头,将规模大的簇进行拆分,增加簇的个数;在增大簇规模阶段,簇成员节点进行邻近运动,动态调整各簇规模。该算法最大限度地使簇负载均衡、能量均衡,延长网络生命周期。本文的主要贡献如下:1)本文在基于集群的数据收集过程中,研究了网络负载瓶颈问题,考虑到节点数据量的差异性,充分利用了初始随机部署过程中的冗余节点。2)为了解决网络负载不均衡问题,设计了一种负载均衡的传感器节点重部署算法,对网络的局部优化和全局优化进行平衡,高效能地移动冗余节点和簇内普通节点,实现簇负载与能量
13、相匹配。3)仿真结果验证了所提算法能有效地均衡网络负载,提高网络资源利用率,增大数据采集量。2 系统模型2.1 无线传感器网络模型如图 1 所示,无线传感器网络模型主要由汇聚(sink)节点、簇头、普通节点、冗余节点组成。其中,汇聚节点负责收集分析网络中的所有数据,普通节点进行感知数据,簇头节点负责收集、融合、转发簇内所有普通节点的数据,冗余节点初始时处于休眠状态。网络执行过程以网络工作轮数的形式进行,每一轮都包含数据的通信阶段。图 1 无线传感器网络模型无线传感器网络节点部署过程如下:首先,在规模为 LL 的正方形监测区域内,随机部署 N 个传感器节点,利用 k-means 算法进行分簇。然
14、后,普通节点将感知数据传输到自己所处簇的簇头处,簇头再进行数据融合和转发。最后,当簇的负载达到设定的阈值时,移动冗余节点进行簇拆分阶段,进而以冗余节点为簇头将原集群进行拆分,生成新的簇(此时簇数目1)。当网络中簇数达到最佳时,簇成员节点进行邻近运动,完成簇成员调整,从而实现网络负载均衡。为了更好地实现本文设计目标,本文中的节点位置信息都可以通过特殊方式获得。该网络的具体假设如下:1)每个节点都能通过全球定位系统(Global PositioningSystem,GPS)或其它一些特殊定位算法16知道自己的位置,相邻节点间可以互相通信,每个传感器节点有其唯一身份标识号(Identity Docu
15、ment,ID)。2)每个节点只被包含于一个簇中,且初始化时节点的属783性相同。3)所有簇头都以单跳方式向汇聚节点发送数据,簇内普通节点也以单跳方式向自己的簇头传输数据。4)汇聚节点位于网络中心,且没有能源限制。5)整个网络中的节点在初始部署后都是可移动的,并且簇与簇之间不存在信息的传递。2.2 能量消耗模型对于能量消耗程度的测量,使用一阶无线电模型17。假设通信距离为 d,比较发射机和接收机之间的距离与阈值d0的大小,分别采用自由空间信道和多路径衰减信道。例如,从发射节点距离为 d 的接收节点发送 m 比特数据时,所消耗的能量可以用公式表示为ETX(m,d)=mEelec+mfsd2,d
16、d0mEelec+mampd4,d d0(1)d0=fsamp其中,d0为距离阈值;Eelec是发送/接收 1 bit 数据的能量消耗;fs表示当 dd0时,自由空间中发送电路的放大系数,其值设为 12pJ/bit/m2;amp为当 d d0时,多径信道中发送电路的放大系数,其值设为 0.0012pJ/bit/m4节点在感知过程中消耗能量忽略不计。节点接收 m bit 数据所需能量损耗 ERX(m)为ERX(m)=m Eelec(2)节点移动所消耗的能量 Emove可表示为:Emove=e dx(3)式(3)中 e 为单位距离内节点移动能耗,dx为节点移动距离。3 问题描述本章针对无线传感器网
17、络负载不均衡问题,提出基于MBO 的负载均衡节点重部署的原因。首先,给出以下定义:定义 1 生命周期:当网络中死亡节点数目达到网络节点总数目的 40%时,表示该网络生命周期结束。定义 2 死亡率:死亡节点数目与节点数目 N 的比值。定义 3 传感器节点集合 S=S1,S2,SN,冗余节点的集合 R=R1,R2,Rx,且 RS。定义 4 邻居节点:节点 i 的邻居集定义为 N(i)=nS|de(i,j)Rc,ni,其中 de(i,j)为节点 i 与节点 j 之间的欧氏距离,Rs(i)为节点 i 的感知半径。因此,节点 i 为冗余节点的条件为:jN(i)Rs(j)Rs(i)。在无线传感器网络中,网
18、络进行初始部署之后,由于节点能量有限且难以进行补充或替换、每个节点产生的数据量不一致,网络负载可能随时间变化而变化,容易导致负载大的节点能量消耗过快提前死亡,影响网络数据采集,甚至导致网络瘫痪,无法正常运行。因此,本文对网络负载不均衡问题进行了研究,考虑了节点的实际负载情况,在帝王蝶优化算法的基础上,提出了一种负载均衡的无线传感器网络节点重部署算法。本文为了平衡各簇的负载,不仅使最大负载簇最小化,而且还研究了所有簇之间的负载分配。因此,本文的适应度函数可以根据簇负载的标准差来建立。簇负载的标准差可以表示为=1NCHNCHi=0LCi-?LC()2(4)标准差越小,适应度值越好。因此适应度函数可
19、以表示为Fit=1(5)其中,NCH为簇头数目,LCi为集群 Ci的负载,且 0i p 时xt+1i,k=xtr2,k(11)上式(10)中,rand 为服从均匀分布的随机数,t0为迁移周期;上式(11)中的 r2是从 NP2 中随机选择的。MBO 算法中通过调整迁移率 p 可以平衡迁移算子的方向。若 p 越大,则从 Land1 中选择更多帝王蝶,反之,则从Land2 中选择更多帝王蝶。2)蝶形调整算子对于帝王蝶 j 中的元素,如果随机生成的数字 rand 小于或等于 p,则可以将其更新为xt+1j,k=xtbest,k(12)其中,xbest是 Land1 和 Land2 中最好的帝王蝶。若
20、 rand p,则有xt+1j,k=xtr3,k(13)若 rand BAR,则xt+1j,k=xt+1j,k+(dxk-0.5)(14)dx=Levy(xtj)(15)=Smax/t2(16)其中,r3是从 NP2 中随机选择的帝王蝶,BAR 为蝶形调整率,Smax为一个帝王蝶个体一步移动的最大距离,为加权因子,在本文中 Smax取值为 1.0,BAR=5/12,迁移周期 t0=1.2,迁移率 p=5/12。4.2 邻近运动在本小节中,通过利用 MBO 算法移动冗余节点,以拆分负载大的簇,实现最小化最大簇负载。此外,为了所有簇之间的负载分配,当簇头数目达到最优时,利用邻近运动进行簇成员节点的
21、移动,以实现网络负载均衡。邻近运动如图 2所示,假设簇 D 是负载最小的簇,簇 B 是负载最大的簇,负载C 是第二大的簇,此时需要平衡簇 D 的负载。因节点的数据产生量在每次迭代中不同,故以节点 i 的实际负载、剩余能量和距离相邻簇的欧氏距离为判定标准,先从簇 B 中选择适合的成员节点移动到簇 C 中,然后再将簇 C 中选择符合条件的节点移动到簇 D。邻近运动有利于平衡各簇负载,减少移动能耗。在增大簇规模阶段,通过函数值动态调整成员节点,以平衡各簇负载,节点 i 的函数表达形式如下f=1vL+2er+3ditoh(17)其中,1,2,3分别为节点的实际负载、剩余能量以及节点间距离在函数所占的权
22、重因子,且 1+2+3=1。vL为节点i 当前的实际负载,er为节点 i 的剩余能量,ditoh为节点 i 到相邻簇簇头的欧氏距离。4.3 LBNR 算法步骤本章节为了提高网络数据收集率,引入了 k-means 聚类算法,但随着网络的运行,由于每个节点的数据产生量不同,图 2 邻近运动会出现负载瓶颈问题,需对网络节点进行重新部署。近年来,智能优化算法已广泛应用于无线传感器网络中,而 MBO算法作为有前景的智能优化算法之一,在节点部署优化问题上具有很大的潜力。利用其迁移算子,根据节点的实际负载,剩余能量以及具体位置,移动网络中的冗余节点,完成簇的拆分。此外,该算法结合本章节所提的邻近运动,能有效
- 配套讲稿:
如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。