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 问题描述本章针对无线传感器网络负载不均衡问题,提出基于MBO 的负载均衡节点重部署的原因。首先,给出以下定义:定义 1 生命周期:当网络中死亡节点数目达到网络节点总数目的 40%时,表示该网络生命周期结束。定义 2 死亡率:死亡节点数目与节点数目 N 的比值。定义 3 传感器节点集合 S=S1,S2,SN,冗余节点的集合 R=R1,R2,Rx,且 RS。定义 4 邻居节点:节点 i 的邻居集定义为 N(i)=nS|de(i,
