第2期 陈珍焰，等：移动节点的L EACH改进型算法 ·141- 必要的.同时这些随机选取的聚类首领，可能在网络 1 LEACH协议缺陷 的边缘，成员与首领的距离较远，势必增加通信能量 1.1现有协议 的消耗 对于无线传感器网络，最简单的数据通信协议 2)聚类首领彼此不能相距太近，应较为均匀地 是直接通信(direct transmission),即节点收集数据 分布在网络中.在LEACH中.随机选取的聚类首 后直接与基站通信.当基站距离很远时，节点的通信 领可能相距太近，节点在接收成员的数据时，可能会 代价太大，将很快死亡 由于电磁波的互相干扰导致数据的重发，引起不必 LEACH51低功耗自适应聚类数据通信协议， 要的能量损耗 基本思想是减少与基站直接通信的节点数目，并通 2 BMSN协议运作流程 过数据聚合技术减少通信能量的损耗.LEACH分 为设置和稳定工作2个阶段.设置阶段随机选出若 无线传输中，发射功率的衰减随着传输距离的 千聚类首领(cluster head),聚类首领向所有节点广 增大而呈指数衰减.文献[3]提出了2种信道模型 播消息，其余节点依据接收信号的强弱加入就近的 自由空间(free space)模型和多路径衰减(multi- 聚类.稳定工作阶段节点持续采集监测的数据，并传 path fading)模型，当发送节点和接收节点之间的距 至聚类首领，聚类首领将所有成员的数据进行聚合 离d小于某个值do时，采用自由空间模型，发射功 后发送给远端的基站.每轮选取新的聚类首领，重复 率呈6衰减：否则采用多路径衰减模型，发射功率 2个阶段的工作，保证网络中能量的损耗分布在所 呈d6衰减. 有节点中.此外，聚类首领利用数据聚合技术将多个 针对L EACH算法存在的不足之处，本文提出 信号聚合为一个有效的信号，使得通信量大大降低， 了基于移动节点的L EACH改进型算法.在BMSN 也极大地减少了能量的消耗.与直接通信方式相比， 协议中，节点以半径r广播，r为聚类半径，其值小 L EACH的网络生命周期可延长4~8倍 于b/2,目的是为了保证聚类首领之间的距离限制 LEACH-C(L EACH-centralized)I]是集中式的 在山范围内.这样网络内成员与簇首、簇首与簇首 簇头产生算法，由基站负责挑选簇头.LEACH每轮 之间的通信都遵循自由空间模型.BMSN协议还保 产生的簇头没有确定的数量和位置，L EACH-C根 证簇首节点之间的距离大于r,减小聚类首领之间 据全局信息挑选簇头，有效解决L EACH的这一不 的通信干扰 足.每个节点把自身地理位置和当前能量报告给基 2.1簇首选举 站，基站根据所有节点的报告计算平均能量，当前能 节点A在满足E(节点现有能量)大于全体节 量低于平均能量的节点不能成为候选簇头.从剩余 点平均能量的基础上，以半径r广播，宣布自己参与 候选节点中选出合适数量和最优地理位置的簇头集 竞争簇首，发布candidate消息.节点等待一段时间 合是一个NP问题，基站根据所有成员节点到簇头 T,若未收到其他节点的candidate消息，表明A节 的距离平方和最小的原则，采用模拟退火(simula- 点覆盖半径内没有其他节点竞争簇首，A宣布自身 为簇首，并广播Head消息.若节点接收到其他节点 ted annealing)算法解决该NP问题.最后，基站把簇 的candidate消息，比较节点之间的aEr+ 头集合和簇的结构广播出去.LEACH-C效果优于 L EACH. ∑d(d表示r半径内其他节点与自身节点距 1.2问题描述 离，a和B是调整系数)，选择节点中该值较大者为 设计有效利用能量的路由协议的原则是使每轮 簇首.若A为簇首，簇首节点广播Head消息，非簇 数据收集的总能耗最小，同时保证能量的损耗匀分 首节点接收Head消息，发布cancel消息，取消自己 布在所有节点上.在传感器网络中基于聚类的通信 的candidate消息，不再参与簇首竞争.若A非簇 协议应满足以下几个目标四： 首，等待一段时间T,接收Head消息，发布cancel 1)网络中节点之间的通信，包括聚类成员与首 消息，不参与竞争簇首.其他节点若能接收到Head 领的通信、聚类首领之间的通信，应该遵循自由空间 消息，则不参与竞争，否则，重复上述步骤 模型，避免远距离传输的高能量衰减，因此聚类的大 循环结束后，簇首节点已定，节点在半径r内选 小应该限制在一定范围内.在LEACH协议中，成 择aEw+A∑f最大者，并向其发送join消息，加 为首领的节点在全网范围内广播消息，其功率衰减 入该簇；若节点不在已定簇首节点通信范围r内，将 遵循多路径衰减模型)，而所有其他节点接收此消 宣布自身为簇首，直接广播Head消息」 息也将损耗一定的能量.事实上，对于多数未成为此 2.2丛集观察 聚类成员的节点而言，接收此消息的能量信号是不 丛集观察阶段，主要的工作是观察已经分配好 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net1 L EAC H 协议缺陷 1. 1 现有协议 对于无线传感器网络 ,最简单的数据通信协议 是直接通信(direct transmission) ,即节点收集数据 后直接与基站通信. 当基站距离很远时 ,节点的通信 代价太大 ,将很快死亡. L EACH [425 ]低功耗自适应聚类数据通信协议 , 基本思想是减少与基站直接通信的节点数目 ,并通 过数据聚合技术减少通信能量的损耗. L EACH 分 为设置和稳定工作 2 个阶段. 设置阶段随机选出若 干聚类首领(cluster head) ,聚类首领向所有节点广 播消息 ,其余节点依据接收信号的强弱加入就近的 聚类. 稳定工作阶段节点持续采集监测的数据 ,并传 至聚类首领 ,聚类首领将所有成员的数据进行聚合 后发送给远端的基站. 每轮选取新的聚类首领 ,重复 2 个阶段的工作 ,保证网络中能量的损耗分布在所 有节点中. 此外 ,聚类首领利用数据聚合技术将多个 信号聚合为一个有效的信号 ,使得通信量大大降低 , 也极大地减少了能量的消耗. 与直接通信方式相比 , L EACH 的网络生命周期可延长 4～8 倍. L EACH2C(L EACH2centralized) [ 6 ]是集中式的 簇头产生算法 ,由基站负责挑选簇头. L EACH 每轮 产生的簇头没有确定的数量和位置 ,L EACH2C 根 据全局信息挑选簇头 ,有效解决 L EACH 的这一不 足. 每个节点把自身地理位置和当前能量报告给基 站 ,基站根据所有节点的报告计算平均能量 ,当前能 量低于平均能量的节点不能成为候选簇头. 从剩余 候选节点中选出合适数量和最优地理位置的簇头集 合是一个 N P 问题. 基站根据所有成员节点到簇头 的距离平方和最小的原则 ,采用模拟退火 (simula2 ted annealing) 算法解决该 N P 问题. 最后 ,基站把簇 头集合和簇的结构广播出去. L EACH2C 效果优于 L EACH. 1. 2 问题描述 设计有效利用能量的路由协议的原则是使每轮 数据收集的总能耗最小 ,同时保证能量的损耗匀分 布在所有节点上. 在传感器网络中基于聚类的通信 协议应满足以下几个目标[7 ] : 1) 网络中节点之间的通信 ,包括聚类成员与首 领的通信、聚类首领之间的通信 ,应该遵循自由空间 模型 ,避免远距离传输的高能量衰减 ,因此聚类的大 小应该限制在一定范围内. 在 L EACH 协议中 ,成 为首领的节点在全网范围内广播消息 ,其功率衰减 遵循多路径衰减模型[3 ] ,而所有其他节点接收此消 息也将损耗一定的能量. 事实上 ,对于多数未成为此 聚类成员的节点而言 ,接收此消息的能量信号是不 必要的. 同时这些随机选取的聚类首领 ,可能在网络 的边缘 ,成员与首领的距离较远 ,势必增加通信能量 的消耗. 2) 聚类首领彼此不能相距太近 ,应较为均匀地 分布在网络中. 在 L EACH 中 ,随机选取的聚类首 领可能相距太近 ,节点在接收成员的数据时 ,可能会 由于电磁波的互相干扰导致数据的重发 ,引起不必 要的能量损耗. 2 BMSN 协议运作流程 无线传输中 ,发射功率的衰减随着传输距离的 增大而呈指数衰减. 文献[ 3 ]提出了 2 种信道模型 : 自由空间 (free space) 模型和多路径衰减 ( multi2 pat h fading) 模型 ,当发送节点和接收节点之间的距 离 d 小于某个值 d0 时 ,采用自由空间模型 ,发射功 率呈 d 2 0 衰减 ;否则采用多路径衰减模型 ,发射功率 呈 d 4 0 衰减. 针对 L EACH 算法存在的不足之处 ,本文提出 了基于移动节点的 L EACH 改进型算法. 在 BMSN 协议中 ,节点以半径 r 广播 , r 为聚类半径 ,其值小 于 d0 / 2 ,目的是为了保证聚类首领之间的距离限制 在 d0 范围内. 这样网络内成员与簇首、簇首与簇首 之间的通信都遵循自由空间模型. BMSN 协议还保 证簇首节点之间的距离大于 r ,减小聚类首领之间 的通信干扰. 2. 1 簇首选举 节点 A 在满足 Ecur (节点现有能量) 大于全体节 点平均能量的基础上 ,以半径 r 广播 ,宣布自己参与 竞争簇首 ,发布 candidate 消息. 节点等待一段时间 T ,若未收到其他节点的 candidate 消息 ,表明 A 节 点覆盖半径内没有其他节点竞争簇首 , A 宣布自身 为簇首 ,并广播 Head 消息. 若节点接收到其他节点 的 candidate 消 息 , 比 较 节 点 之 间 的 αEcur + β/ ∑d 2 ( d 表示 r 半径内其他节点与自身节点距 离 ,α和β是调整系数) ,选择节点中该值较大者为 簇首. 若 A 为簇首 ,簇首节点广播 Head 消息 ,非簇 首节点接收 Head 消息 ,发布 cancel 消息 ,取消自己 的 candidate 消息 ,不再参与簇首竞争. 若 A 非簇 首 ,等待一段时间 T ,接收 Head 消息 ,发布 cancel 消息 ,不参与竞争簇首. 其他节点若能接收到 Head 消息 ,则不参与竞争 ,否则 ,重复上述步骤. 循环结束后 ,簇首节点已定 ,节点在半径 r 内选 择αEcur +β/ ∑d 2 最大者 ,并向其发送 join 消息 ,加 入该簇 ;若节点不在已定簇首节点通信范围 r 内 ,将 宣布自身为簇首 ,直接广播 Head 消息. 2. 2 丛集观察 丛集观察阶段 ,主要的工作是观察已经分配好 第 2 期 陈珍焰 ,等 :移动节点的 L EACH 改进型算法 · 141 ·