欢迎访问论文查重发表网站!
经济论文

负载均衡感知的无线传感器网络容错分簇算法

  【摘 要】 好的分簇算法能够有效减少网络能耗和提高网络可靠性,但是簇间负载的不均衡性和通信的不可靠性会 严重影响分簇算法的性能.针对这个问题,该文首先提出了一个负载均衡感知的无线传感器网络容错分簇算法.该 方法引入了遗传算法的随机两点交叉算子和随机单点变异算子,从而设计了一种以种群粒子优劣为依据的自适应 惯性权重调整策略,并提出了一种自适应的离散粒子群优化算法.算法设计同时考虑负载均衡和能量消耗两个优 化目标,给出一种基于自适应离散粒子群优化的簇首选举机制;其 次,为了保证网络上数据传输的可靠性,以 最 小 生成树为基础,提出了一种用于保证簇首二连通性的簇间连通算法,通过消除网络中的割点,以保证网络的二连通 性.仿真实验结果表明,该文提出算法在负载均衡和二连通性上有较好的性能,能有效减少了网络能耗,延 长 网 络 生命周期,并提高网络可靠性. 

关键词 无线传感器网络;分簇算法;负载均衡;粒子群优化;二连通性;物联网

  引 言 无线 传 感 器 网 络 (WirelessSensorNetwork, WSN)是由大量分布在空间中的传感器节点组成的 系统,WSN 不需要预先配置基础网络设施,能够实 现传感器节点在监测区域内收集信息,并自由地组 网通信,为 国 防 军 事、国 家 安 全、环 境 监 测、交 通 管 理、反恐抗灾以及一些应急通信应用提供了快捷的 网络部署和业务承载方案,具有广阔的应用前景[1] . 由于很难对所有传感器节点进行能量补充,因此需 要通过某种方式降低传感器节点的能量消耗,从而 延长网络的生命周期. 分簇算法是有效管理网络能耗以及改进整个网 络性能的 方 法 之 一[2-6] .分簇算法中包含簇首的选 举、簇首与基站之间的通信.现有的簇首选举机制针 对某个具体目标做出控制,难于在能耗有效性、负载 均衡性以及簇首数量之间做出较好的权衡.按照簇 首到基站的跳数,簇的结构一般可以分为单跳网络 和多跳网络.簇间单跳通信方式需要所有节点与簇 首进行直接通信,远距离通信会使簇首节点能量迅 速消耗掉,导致距离基站节点较远的簇首节点很快 死亡,从而降低了网络的连通性和减少了网络的生 存周期.而多跳通信方式,不需要簇首节点有直接与 基站节点通信的能力,避免了直接与基站节点通信 所耗费的大量能量,当然这样加大了靠近基站的簇 首能耗,但与单跳方式的远距离通信相比,多跳方式 可以相对减少网络中的能耗.本文采用多跳的通信 方式,基站通过簇首与基站之间构成的多跳网络收 集信息,因此有必要提供一定的方式,增强多跳网络 的传输可靠性.本文提出了一种负载均衡感知的无 线传感器网络容错分簇算法.算法中我们提出了一 种基 于 粒 子 群 优 化(ParticleSwarm Optimization, PSO)方法的自适应簇首选举机制,同时为了保证主 干网络的可靠性,提出了一种用于保证簇首二连通 性的簇间连通算法.实验结果表明了我们提出算法 在负载均衡性、能量有效利用以及网络容错性等方 面能取得较好的效果. 本文第2节介绍相关工作;第3节介绍本文协 议使用的网络传输模型;第4节给出相应的成簇算 法以及算法实现细节;第5节介绍基于本地最小生 成树(LocalMinimumSpanningTree,LMST)的簇 间二连通算法;第6节中描述实验测试环境,给出本 文算法的参数设置和实验结果以及结果比较分析; 最后给出结论以及下一步的研究方向. 2 相关工作 分簇算法通过将网络划分成若干较小的簇进行 管理,每个簇内都有一个簇首节点接收、融合成员节 点发送的数据之后再进行转发,较大限度地降低网 络中的数据通信量,减少了网络能耗,有效地延长了 网络寿命.文献[2]提出了著名的 LEACH 算法,该 算法采用分布式的簇首选举策略,网络中的传感器 节点以一定的概率竞选簇首.虽然 LEACH 可以在 一定程度上节约能量消耗和延长网络寿命,但是它缺 乏集中控制,无法保证选举出合适的簇首数量,也无 法保证选出的簇首均匀分布在整个网络.文献[3]针 对 LEACH 算法的缺陷进行改进,提出了LEACH-C 算法,算法根据基站获得的节点剩余能量信息事先 进行分簇,以确定合适的簇首数量.文献[4]结合功 率控制理论及算法,提出了一种易于实现、能动态适 应网络变化、能量有效的基于跨层优化策略的链路 稳定成簇算法.文献[5]中将分簇转化为携近似优化 目标的簇划分及簇首选取问题,并采取一种启发式 的分簇控制算法.文献[6]提出一种综合考虑节点及 其邻居节点能量的簇首选举算法,对较低剩余能量 的节点进行保护,虽然能有效减少网络中的能量消 耗,但是无法保证合适的簇首数量以及簇首的均匀 分布. 这些分簇算法虽然能够在一定程度上保证能量 的有效利用,但是各个簇的能量消耗不均衡的情况 还是存在的.与普通节点相比,如果簇首因为负责簇 内和簇间的大部分活动而消耗更多的能量,这样将 造成节点间负载不均衡,部分簇首因能耗消耗过快 而失效,从而影响了网络的寿命.因此,簇首选举时 如何考虑节点的剩余能量和平衡每个簇首的负载是 至关重要的.最近,许多研究人员都在研究分簇算法 中的负载均衡问题.文献[7]提出了 HEED 算法,在 簇首的选举时考虑了传感器节点当前的剩余能量, 该算法中已经考虑并部分实现了分簇的负载均衡, 但它无法解决相邻簇之间的不合理距离.同时采用 簇首与基站直接通信的方式,而传感器簇首节点距 基站较远,因此簇首直接与基站通信要消耗很大的 能量.DBCL算法[8]通过将每个簇首节点的成员数量 控制在合理范围内,克服了其它算法中普遍存在的各 簇节点数量不均衡的缺点.但算法采取随机的簇首选 举方 式,没有考虑到节点的剩余能量.ACHS[9]和EACHS[10]都是先 按 照 LEACH 算法 进 行 分 簇,然 后通过调整簇首在簇内的位置,分别从簇首到簇内 成员节点距离和簇内的成员数量两个方面考虑网络 的负载均衡.文献[11]通过建立相邻节点剩余能量 预测机制,将节点的剩余能量与选举簇首节点的概 率相关,同时通过多簇首的方法,能在一定程度上均 衡节点的能量消耗.由于采用随机概率的簇首选举 机制,LEACH、ACHS、EACHS和文献[11]的算法 都无法保证选举出适当的簇首节点,而且选举出的 簇首无法保证均匀分布在目标区域内,这样可能造 成更大的能量消耗,影响到负载均衡和网络的性能. 另外,簇的数量也影响网络的性能,数量过多或 过少都会引起性能下降,数量过多既不便于基站管 理,也会增多网络内的通信,增大通信消耗,而数量 过少,簇内成 员 节 点 数 目 过 多,增加簇首的管理难 度.为此,选出均匀分布在目标区域内、具有高效能 量的最优簇 首 集 合,是 一 个 NP-难问 题[12] .PSO 是 由 Kennedy和 Eberhart[13]提出 的 一 种 启 发 式 优 化 方法,已成功用于解决许多领域中的问题[14-17] .无线 传感器网络中节点部署、节点定位、能量有效分簇、 数据融合以及拓扑控制等问题都可抽象为相应的优 化问题,文献[18]很好地综述了 PSO 在上述领域的 具体 应 用 情 况.本 文 基 于 PSO 方 法,设 计 了 一 种 自适应的基于离散粒子群优化的簇首选举算法 (AdaptiveDiscreteParticleSwarm Optimization, ADPSO),在簇首选举时考虑节点的剩余能量和簇 的负载均衡.在 ADPSO 算法中,引入遗传算法中的 变异和交叉算子思想以克服过早收敛的现象,并设 计一种惯性权重的调整策略. 簇首与基站之间构建成的网络是分簇网络中的 主干网络,网络中的数据都是通过主干网络汇集到 基站,因此主干网络在分簇网络中是至关重要的.如 果只维护主干网络的一连通性能,虽然形成的网络 拓扑结构中存在冗余边较少,但一旦某个传感器节 点失效,就可能导致整个网络的分割,为此有必要维 护网络的多连通性.根据图论相关知识可知,一个没 有关节 点 的 网 络 图 是 一 个 二 连 通 的 网 络 图.由 于 WSN 的节点容 易 失 效,再加上无线信道存在不稳 定性,会使得一般的网络拓扑结构出现拓扑变化频 繁的情况.为了提高网络拓扑稳定性,需要考虑消除 节点失效对网络拓扑结构造成的相对不稳定影响. 构建二连通的网络拓扑结构可以在网络的低功耗和 容错性二者之间取得一种平衡.关于传感器网络二 连通问题的研究可分为两个方向:一是基于概率论 知识,研究网络中因为节点或者链路失效而导致网 络分割的概率,并得出相应的经验公式,用于指导网 络拓扑结构设计;二是利用图论的相关知识,构建二 连通的网络拓扑,使得当某个节点失效的情况下,剩 余网络仍然是连通的.文献[19]采用了最小生成树 (MinimumSpanningTree,MST)的算法设计思路, 使用贪心策略,分别设计了能够保持传感器网络一连 通和二连通的 CONNECT 和 BICONN 两种集中式 功率控制策略.Hajiahayi等人在文献[20]中介绍了 一种保持网络二连通性能的启发式算法2-UPVCS, 该算法首先需要计算整个网络的最小生成树,然后 通过添加边的方式来将一连通的最小生成树转换为 二连通的网络图.文献[21]中利 用 PSO 方法,通 过 尽量减少网络图中的关节点数量,保证网络的二连 通性. 本文借鉴文献[22]中提出的本地最小生成树构 建单 连 通 拓 扑 的 思 想,在 每 个 簇 首 节 点 运 行 Prim 算法,计算邻居图的最小生成树,然后据此确定自身 的发射功率.基站根据得到的簇首之间的拓扑结构 信息,运用广度优先搜索算法,计算出图中存在的割 点和割边,通过添加边的方式减少割点和割边,从而 确保网络的二连通性. 3 网络模型和能量消耗模型 3.1 网络模型 本文采用类似文献[2-3]中的传感器网络模型, 该模型具有以下性质. (1)所有传感器节点随机分布在边长为 M 的正 方形区域中; (2)基站是固定的、可维护的,有足够的能量; (3)所有传感器节点的能量是有限的,同 时 具 有自身的位置信息; (4)所有传感器节点都具有功率控制能力,可 以改变自己的传输功率; (5)所有传感器节点都可以处在簇首节点和普 通节点两种模式,而所处的模式是由基站来决定的, 每个节点具有足够的数据融合能力.

 成簇算法 WSN 分簇算 法 中,选择合适的簇数目和在簇 首选举时确保簇间的负载均衡都是至关重要的.另 外,由于簇首负责簇内和簇间的大部分事务,因此在 簇首选举时也应充分考虑剩余能量这一重要因素. 在本节中,我们将簇数目、节点剩余能量以及簇的负 载均衡等因素加入到簇首选举中,并设计了一种用 于簇首选举的自适应离散粒子群优化算法. 4.1 PSO方法 PSO 是一种从鸟群的社会行为中得到启发,利 用种群的思想来解决搜索问题的方法.种群中的个 体像鸟一样可以从自己的飞行经验中、与周围个体 的交流中获得的信息来调整自己的飞行速度和飞行 方向.在 PSO 中,粒子的位 置 代 表 被 优 化 空 间 在 搜 索空间中的潜在解,所有的粒子都有一个被优化的 函数决定的适应值,每个粒子还有一个速度决定他 们飞翔的方向和距离.每个粒子根据自身和周围粒 子的经验在搜索空间中调整自己的位置和速度.位 置和速度的更新方程如下所示: Vt+1 i =w×Vt i+c1r1(pBesti-Xt i)+c2r2(gBest-Xt i) (3) Xt+1 i =Xt i+Vt+1 i (4) 其中,Xi和Vi分别表示第i 个粒子的位置和速度,t 是迭代 次 数,pBesti是第i 个粒 子 的 最 优 值,gBest 表示种群的当前最优值,w 是惯性权值,c1和c2为认 知因子,反映了粒子对自身最优值以及种群全局最 优值的学习能力,r1和r2是在[0,1]范围内的两个随 机数,用于增 强 搜 索 的 随 机 性,通常使用一个常量 Vmax来限制粒子的速度,改善搜索结果. 4.2 ADPSO算法 PSO 最初被应用于连续空间的优化,然而文中 所涉及的簇首选举问题本身是一个离散优化问题, 需要将 PSO 在二进制空间进行扩展,构造一种离散 形式的 PSO 算法模型.现有文献主要有将速度作为 位置变化的概率、直接将连续 PSO 用于离散问题的 求解以及重新定义 PSO 操作算子3种策略,本文作 者所在的课题组为解决实际工程应用问题,一直跟 踪 PSO 的研究进展,并给出求解无线传感器网络任 务分配问题、超大规模集成电路电路划分以及布局 问题的有效离散 PSO[15-17] .借助前期的算法构造经 验并对照 PSO 的基本思想可以发现,可以利用二进 制编码方式表示簇首选举问题,以能量消耗和负载 均衡为优化目标,定义相应的适应度函数用于指导 演化过程已得到优化的选择结果,因此 PSO 方法可 以应用于簇首选举问题的求解. 4.2.1 编 码 PSO 对于编码的要求并不苛刻,但是为了有效 提高搜索效率和算法的性能,有必要采取一种好的 编码.而编码的选择主要考虑完备性、健全性和非冗 余性三个原则[17] . 定义1(完备性). 问题空间中的所有点(可行 解)都能成为粒子编码空间中点的表现型. 定义2(健 全 性). 编 码 空 间 中 的 每 一 个 粒 子 必须对应问题空间中的某一潜在解.

    结 论 针对分簇的负载均衡问题,本文同时考虑了负 载均衡和能量消耗,提出了一种基于 ADPSO 算法 的动态簇首选举机制,该选择机制能够较好地适应 网络的动态变化,保证选举出适合比例的簇首,并有 效地保证了能量消耗的均衡性,延长了网络的生命 周期.此 外,为保证数据传输的可靠性,通 过 对 LMST 算法的分析,提出了一种用于簇首与基站之 间的二连通算法,通过采取多跳通信方式有效地减 少了簇首与基站之间的通信能量消耗,实验结果表 明算法能够在一定程度上有效保证网络的二连通 性,具有较好的稳定性和较低的干扰性. 由于传感器节点和链路的传输质量受环境因素 的影响较大,从而会给分簇拓扑控制带来不确定性, 下一步重点展开的工作是考虑网络环境中节点移动 或者节点失效带来的拓扑结构变化所造成的影响及 其应对策略.

上一篇:没有了 下一篇:关于主体行为不确定性的科学技术探究
热门期刊