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

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

  引 言 无线 传 感 器 网 络 （ＷｉｒｅｌｅｓｓＳｅｎｓｏｒＮｅｔｗｏｒｋ， ＷＳＮ）是由大量分布在空间中的传感器节点组成的 系统，ＷＳＮ 不需要预先配置基础网络设施，能够实 现传感器节点在监测区域内收集信息，并自由地组 网通信，为 国 防 军 事、国 家 安 全、环 境 监 测、交 通 管 理、反恐抗灾以及一些应急通信应用提供了快捷的 网络部署和业务承载方案，具有广阔的应用前景［１］ ． 由于很难对所有传感器节点进行能量补充，因此需 要通过某种方式降低传感器节点的能量消耗，从而 延长网络的生命周期． 分簇算法是有效管理网络能耗以及改进整个网 络性能的 方 法 之 一［２－６］ ．分簇算法中包含簇首的选 举、簇首与基站之间的通信．现有的簇首选举机制针 对某个具体目标做出控制，难于在能耗有效性、负载 均衡性以及簇首数量之间做出较好的权衡．按照簇 首到基站的跳数，簇的结构一般可以分为单跳网络 和多跳网络．簇间单跳通信方式需要所有节点与簇 首进行直接通信，远距离通信会使簇首节点能量迅 速消耗掉，导致距离基站节点较远的簇首节点很快 死亡，从而降低了网络的连通性和减少了网络的生 存周期．而多跳通信方式，不需要簇首节点有直接与 基站节点通信的能力，避免了直接与基站节点通信 所耗费的大量能量，当然这样加大了靠近基站的簇 首能耗，但与单跳方式的远距离通信相比，多跳方式 可以相对减少网络中的能耗．本文采用多跳的通信 方式，基站通过簇首与基站之间构成的多跳网络收 集信息，因此有必要提供一定的方式，增强多跳网络 的传输可靠性．本文提出了一种负载均衡感知的无 线传感器网络容错分簇算法．算法中我们提出了一 种基 于 粒 子 群 优 化（ＰａｒｔｉｃｌｅＳｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ， ＰＳＯ）方法的自适应簇首选举机制，同时为了保证主 干网络的可靠性，提出了一种用于保证簇首二连通 性的簇间连通算法．实验结果表明了我们提出算法 在负载均衡性、能量有效利用以及网络容错性等方 面能取得较好的效果． 本文第２节介绍相关工作；第３节介绍本文协 议使用的网络传输模型；第４节给出相应的成簇算 法以及算法实现细节；第５节介绍基于本地最小生 成树（ＬｏｃａｌＭｉｎｉｍｕｍＳｐａｎｎｉｎｇＴｒｅｅ，ＬＭＳＴ）的簇 间二连通算法；第６节中描述实验测试环境，给出本 文算法的参数设置和实验结果以及结果比较分析； 最后给出结论以及下一步的研究方向． ２ 相关工作 分簇算法通过将网络划分成若干较小的簇进行 管理，每个簇内都有一个簇首节点接收、融合成员节 点发送的数据之后再进行转发，较大限度地降低网 络中的数据通信量，减少了网络能耗，有效地延长了 网络寿命．文献［２］提出了著名的 ＬＥＡＣＨ 算法，该 算法采用分布式的簇首选举策略，网络中的传感器 节点以一定的概率竞选簇首．虽然 ＬＥＡＣＨ 可以在 一定程度上节约能量消耗和延长网络寿命，但是它缺 乏集中控制，无法保证选举出合适的簇首数量，也无 法保证选出的簇首均匀分布在整个网络．文献［３］针 对 ＬＥＡＣＨ 算法的缺陷进行改进，提出了ＬＥＡＣＨ－Ｃ 算法，算法根据基站获得的节点剩余能量信息事先 进行分簇，以确定合适的簇首数量．文献［４］结合功 率控制理论及算法，提出了一种易于实现、能动态适 应网络变化、能量有效的基于跨层优化策略的链路 稳定成簇算法．文献［５］中将分簇转化为携近似优化 目标的簇划分及簇首选取问题，并采取一种启发式 的分簇控制算法．文献［６］提出一种综合考虑节点及 其邻居节点能量的簇首选举算法，对较低剩余能量 的节点进行保护，虽然能有效减少网络中的能量消 耗，但是无法保证合适的簇首数量以及簇首的均匀 分布． 这些分簇算法虽然能够在一定程度上保证能量 的有效利用，但是各个簇的能量消耗不均衡的情况 还是存在的．与普通节点相比，如果簇首因为负责簇 内和簇间的大部分活动而消耗更多的能量，这样将 造成节点间负载不均衡，部分簇首因能耗消耗过快 而失效，从而影响了网络的寿命．因此，簇首选举时 如何考虑节点的剩余能量和平衡每个簇首的负载是 至关重要的．最近，许多研究人员都在研究分簇算法 中的负载均衡问题．文献［７］提出了 ＨＥＥＤ 算法，在 簇首的选举时考虑了传感器节点当前的剩余能量， 该算法中已经考虑并部分实现了分簇的负载均衡， 但它无法解决相邻簇之间的不合理距离．同时采用 簇首与基站直接通信的方式，而传感器簇首节点距 基站较远，因此簇首直接与基站通信要消耗很大的 能量．ＤＢＣＬ算法［８］通过将每个簇首节点的成员数量 控制在合理范围内，克服了其它算法中普遍存在的各 簇节点数量不均衡的缺点．但算法采取随机的簇首选 举方 式，没有考虑到节点的剩余能量．ＡＣＨＳ［９］和ＥＡＣＨＳ［１０］都是先 按 照 ＬＥＡＣＨ 算法 进 行 分 簇，然 后通过调整簇首在簇内的位置，分别从簇首到簇内 成员节点距离和簇内的成员数量两个方面考虑网络 的负载均衡．文献［１１］通过建立相邻节点剩余能量 预测机制，将节点的剩余能量与选举簇首节点的概 率相关，同时通过多簇首的方法，能在一定程度上均 衡节点的能量消耗．由于采用随机概率的簇首选举 机制，ＬＥＡＣＨ、ＡＣＨＳ、ＥＡＣＨＳ和文献［１１］的算法 都无法保证选举出适当的簇首节点，而且选举出的 簇首无法保证均匀分布在目标区域内，这样可能造 成更大的能量消耗，影响到负载均衡和网络的性能． 另外，簇的数量也影响网络的性能，数量过多或 过少都会引起性能下降，数量过多既不便于基站管 理，也会增多网络内的通信，增大通信消耗，而数量 过少，簇内成 员 节 点 数 目 过 多，增加簇首的管理难 度．为此，选出均匀分布在目标区域内、具有高效能 量的最优簇 首 集 合，是 一 个 ＮＰ－难问 题［１２］ ．ＰＳＯ 是 由 Ｋｅｎｎｅｄｙ和 Ｅｂｅｒｈａｒｔ［１３］提出 的 一 种 启 发 式 优 化 方法，已成功用于解决许多领域中的问题［１４－１７］ ．无线 传感器网络中节点部署、节点定位、能量有效分簇、 数据融合以及拓扑控制等问题都可抽象为相应的优 化问题，文献［１８］很好地综述了 ＰＳＯ 在上述领域的 具体 应 用 情 况．本 文 基 于 ＰＳＯ 方 法，设 计 了 一 种 自适应的基于离散粒子群优化的簇首选举算法 （ＡｄａｐｔｉｖｅＤｉｓｃｒｅｔｅＰａｒｔｉｃｌｅＳｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ， ＡＤＰＳＯ），在簇首选举时考虑节点的剩余能量和簇 的负载均衡．在 ＡＤＰＳＯ 算法中，引入遗传算法中的 变异和交叉算子思想以克服过早收敛的现象，并设 计一种惯性权重的调整策略． 簇首与基站之间构建成的网络是分簇网络中的 主干网络，网络中的数据都是通过主干网络汇集到 基站，因此主干网络在分簇网络中是至关重要的．如 果只维护主干网络的一连通性能，虽然形成的网络 拓扑结构中存在冗余边较少，但一旦某个传感器节 点失效，就可能导致整个网络的分割，为此有必要维 护网络的多连通性．根据图论相关知识可知，一个没 有关节 点 的 网 络 图 是 一 个 二 连 通 的 网 络 图．由 于 ＷＳＮ 的节点容 易 失 效，再加上无线信道存在不稳 定性，会使得一般的网络拓扑结构出现拓扑变化频 繁的情况．为了提高网络拓扑稳定性，需要考虑消除 节点失效对网络拓扑结构造成的相对不稳定影响． 构建二连通的网络拓扑结构可以在网络的低功耗和 容错性二者之间取得一种平衡．关于传感器网络二 连通问题的研究可分为两个方向：一是基于概率论 知识，研究网络中因为节点或者链路失效而导致网 络分割的概率，并得出相应的经验公式，用于指导网 络拓扑结构设计；二是利用图论的相关知识，构建二 连通的网络拓扑，使得当某个节点失效的情况下，剩 余网络仍然是连通的．文献［１９］采用了最小生成树 （ＭｉｎｉｍｕｍＳｐａｎｎｉｎｇＴｒｅｅ，ＭＳＴ）的算法设计思路， 使用贪心策略，分别设计了能够保持传感器网络一连 通和二连通的 ＣＯＮＮＥＣＴ 和 ＢＩＣＯＮＮ 两种集中式 功率控制策略．Ｈａｊｉａｈａｙｉ等人在文献［２０］中介绍了 一种保持网络二连通性能的启发式算法２－ＵＰＶＣＳ， 该算法首先需要计算整个网络的最小生成树，然后 通过添加边的方式来将一连通的最小生成树转换为 二连通的网络图．文献［２１］中利 用 ＰＳＯ 方法，通 过 尽量减少网络图中的关节点数量，保证网络的二连 通性． 本文借鉴文献［２２］中提出的本地最小生成树构 建单 连 通 拓 扑 的 思 想，在 每 个 簇 首 节 点 运 行 Ｐｒｉｍ 算法，计算邻居图的最小生成树，然后据此确定自身 的发射功率．基站根据得到的簇首之间的拓扑结构 信息，运用广度优先搜索算法，计算出图中存在的割 点和割边，通过添加边的方式减少割点和割边，从而 确保网络的二连通性． ３ 网络模型和能量消耗模型 ３．１ 网络模型 本文采用类似文献［２－３］中的传感器网络模型， 该模型具有以下性质． （１）所有传感器节点随机分布在边长为 Ｍ 的正 方形区域中； （２）基站是固定的、可维护的，有足够的能量； （３）所有传感器节点的能量是有限的，同 时 具 有自身的位置信息； （４）所有传感器节点都具有功率控制能力，可 以改变自己的传输功率； （５）所有传感器节点都可以处在簇首节点和普 通节点两种模式，而所处的模式是由基站来决定的， 每个节点具有足够的数据融合能力．

 成簇算法 ＷＳＮ 分簇算 法 中，选择合适的簇数目和在簇 首选举时确保簇间的负载均衡都是至关重要的．另 外，由于簇首负责簇内和簇间的大部分事务，因此在 簇首选举时也应充分考虑剩余能量这一重要因素． 在本节中，我们将簇数目、节点剩余能量以及簇的负 载均衡等因素加入到簇首选举中，并设计了一种用 于簇首选举的自适应离散粒子群优化算法． ４．１ ＰＳＯ方法 ＰＳＯ 是一种从鸟群的社会行为中得到启发，利 用种群的思想来解决搜索问题的方法．种群中的个 体像鸟一样可以从自己的飞行经验中、与周围个体 的交流中获得的信息来调整自己的飞行速度和飞行 方向．在 ＰＳＯ 中，粒子的位 置 代 表 被 优 化 空 间 在 搜 索空间中的潜在解，所有的粒子都有一个被优化的 函数决定的适应值，每个粒子还有一个速度决定他 们飞翔的方向和距离．每个粒子根据自身和周围粒 子的经验在搜索空间中调整自己的位置和速度．位 置和速度的更新方程如下所示： Ｖｔ＋１ ｉ ＝ｗ×Ｖｔ ｉ＋ｃ１ｒ１（ｐＢｅｓｔｉ－Ｘｔ ｉ）＋ｃ２ｒ２（ｇＢｅｓｔ－Ｘｔ ｉ） （３） Ｘｔ＋１ ｉ ＝Ｘｔ ｉ＋Ｖｔ＋１ ｉ （４） 其中，Ｘｉ和Ｖｉ分别表示第ｉ 个粒子的位置和速度，ｔ 是迭代 次 数，ｐＢｅｓｔｉ是第ｉ 个粒 子 的 最 优 值，ｇＢｅｓｔ 表示种群的当前最优值，ｗ 是惯性权值，ｃ１和ｃ２为认 知因子，反映了粒子对自身最优值以及种群全局最 优值的学习能力，ｒ１和ｒ２是在［０，１］范围内的两个随 机数，用于增 强 搜 索 的 随 机 性，通常使用一个常量 Ｖｍａｘ来限制粒子的速度，改善搜索结果． ４．２ ＡＤＰＳＯ算法 ＰＳＯ 最初被应用于连续空间的优化，然而文中 所涉及的簇首选举问题本身是一个离散优化问题， 需要将 ＰＳＯ 在二进制空间进行扩展，构造一种离散 形式的 ＰＳＯ 算法模型．现有文献主要有将速度作为 位置变化的概率、直接将连续 ＰＳＯ 用于离散问题的 求解以及重新定义 ＰＳＯ 操作算子３种策略，本文作 者所在的课题组为解决实际工程应用问题，一直跟 踪 ＰＳＯ 的研究进展，并给出求解无线传感器网络任 务分配问题、超大规模集成电路电路划分以及布局 问题的有效离散 ＰＳＯ［１５－１７］ ．借助前期的算法构造经 验并对照 ＰＳＯ 的基本思想可以发现，可以利用二进 制编码方式表示簇首选举问题，以能量消耗和负载 均衡为优化目标，定义相应的适应度函数用于指导 演化过程已得到优化的选择结果，因此 ＰＳＯ 方法可 以应用于簇首选举问题的求解． ４．２．１ 编 码 ＰＳＯ 对于编码的要求并不苛刻，但是为了有效 提高搜索效率和算法的性能，有必要采取一种好的 编码．而编码的选择主要考虑完备性、健全性和非冗 余性三个原则［１７］ ． 定义１（完备性）． 问题空间中的所有点（可行 解）都能成为粒子编码空间中点的表现型． 定义２（健 全 性）． 编 码 空 间 中 的 每 一 个 粒 子 必须对应问题空间中的某一潜在解．

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