第3卷第2期 智能系统学报 Vol.3 Na 2 2008年4月 CAAI Transactions on Intelligent Systems Apr.2008 移动节点的LEACH改进型算法 陈珍焰，刘贵喜 (西安电子科技大学自动控制系，陕西西安710071) 摘要：L EACH(low-energy adaptive clustering hierarchy)是一种有效延长网络生命周期的通信协议，其组网过程中 存在聚类大小范围不定和簇间干扰现象，针对该问题，提出基于移动节点的LEACH改进型算法.节点以一定半径 广播成簇消息限定聚类大小，减少簇首通信干扰.针对网络运作一段时间后出现能量过低或者不平衡的聚类，加入 移动式感测节点，移动至聚类担任簇首，延长网络生存时间.实验结果与分析表明新方法远好于L EACH. 关键词：无线传感器网络；丛集：移动节点：网络生存时间 中图分类号：TP393文献标识码：A文章编号：1673-4785(2008)02-014005 An improved LEACHalgorithm based on mobile sensor nodes CHEN Zhemyan,LIU Gui-xi (Department of Automation,Xidian University,Xi'an 710071,China) Abstract:The low-energy adaptive clustering hierarchy (L EACH)is an energy-efficient protocol that maxi- mizes network lifetime,but its cluster range is unstable and there can be disturbances between clusters in the network setup process.This paper presents an improved L EACH algorithm based on mobile cluster heads.With the algorithm,sensor nodes broadcast cluster updates and confine cluster range to a set radius so as to reduce disturbances between cluster heads.As clusters lose energy or become unbalanced after a period of network operation,mobile sensors are added to clusters and promoted to cluster head in order to prolong the network survival time.Experimental results and analysis indicated that the performance of the new method is far better than basic L EACH. Keywords wireless sensor network;clusters;mobile nodes;network life time 无线传感器网络由大量无处不在的、具有通信与 的寿命成为设计上需要考虑的关键因素之一，当前主 计算能力的微小传感器节点构成的智能自治测控网络 要从拓扑控制MAC层协议路由机制选择数据融合 系统，是能根据环境自主完成指定任务的智能系统山 等方面实现无线传感器网络节能，从而延长网络的生 WSN是涉及微传感器与微机械通信、自动控制、人工 存周期。 智能等多学科的综合性学科，在军事工业控制、空间、 本文从通信协议的角度出发，在LEACH(low-en 海洋探索等领域有着广阔的应用前景！.机器人设计 ergy adaptive clustering hierarchy)网络基础上，提出了 中，应用无线传感器网络可以实现移动目标的定位以 一种基于移动节点的LEACH改进型算法(the ad- 及跟踪等；借助于航天器布撒的传感器节点，无线传感 vanced algorithm of leach based on mobile sensor node, 器网络可以实现对星球表面大范围、长时期、近距离的 BMSN),特点是在网络中加入移动式感测节点，且具有 监测和探索：利用水下传感器网络进行海洋物理研究、 较高能量，簇首的选举机制保证无线传感器网络通信 灾难预防以及对水下军事目标的监测、定位、跟踪.无 遵循自由空间模型).在网络出现能量过低的丛集时， 线传感器网络分布在人不便进入或不能进入的区域， 移动节点移动至丛集最优簇首位置，选举自身担任簇 节点的能量无法得到补充，使得如何延长传感器网络 首，延长网络的生存周期仿真结果表明新算法具有良 好的性能 收稿日期：2007-1022. 基金项目：武器装备预研基金资助项目(9140A17080407DZ0101) 通讯作者：陈珍焰.Email:zhychen21@l63.com 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 3 卷第 2 期 智 能 系 统 学 报 Vol. 3 №. 2 2008 年 4 月 CAA I Transactions on Intelligent Systems Apr. 2008 移动节点的 L EACH 改进型算法 陈珍焰 ,刘贵喜 (西安电子科技大学 自动控制系 ,陕西 西安 710071) 摘 要 :L EACH (low2energy adaptive clustering hierarchy) 是一种有效延长网络生命周期的通信协议 ,其组网过程中 存在聚类大小范围不定和簇间干扰现象. 针对该问题 ,提出基于移动节点的 L EACH 改进型算法. 节点以一定半径 广播成簇消息限定聚类大小 ,减少簇首通信干扰. 针对网络运作一段时间后出现能量过低或者不平衡的聚类 ,加入 移动式感测节点 ,移动至聚类担任簇首 ,延长网络生存时间. 实验结果与分析表明新方法远好于 L EACH. 关键词 :无线传感器网络 ;丛集 ;移动节点 ;网络生存时间 中图分类号 : TP393 文献标识码 :A 文章编号 :167324785 (2008) 0220140205 An improved LEACHalgorithm based on mobile sensor nodes CH EN Zhen2yan , L IU Gui2xi (Department of Automation , Xidian University , Xi’an 710071 , China) Abstract :The low2energy adaptive clustering hierarchy (L EACH) is an energy2efficient protocol t hat maxi2 mizes network lifetime , but its cluster range is unstable and t here can be dist urbances between clusters in t he network set up process. This paper presents an improved L EACH algorit hm based on mobile cluster heads. With t he algorit hm , sensor nodes broadcast cluster updates and confine cluster range to a set radius so as to reduce dist urbances between cluster heads. As clusters lose energy or become unbalanced after a period of network operation , mobile sensors are added to clusters and p romoted to cluster head in order to prolong t he network survival time. Experimental results and analysis indicated t hat the performance of t he new met hod is far better than basic L EACH. Keywords :wireless sensor network ; clusters; mobile nodes ; network life time 收稿日期 :2007210222. 基金项目 :武器装备预研基金资助项目(9140A17080407DZ0101) . 通讯作者 :陈珍焰. E2mail :zhychen21 @163. com. 无线传感器网络由大量无处不在的、具有通信与 计算能力的微小传感器节点构成的智能自治测控网络 系统 ,是能根据环境自主完成指定任务的智能系统[1] . WSN 是涉及微传感器与微机械、通信、自动控制、人工 智能等多学科的综合性学科 ,在军事、工业控制、空间、 海洋探索等领域有着广阔的应用前景[2] . 机器人设计 中 ,应用无线传感器网络可以实现移动目标的定位以 及跟踪等;借助于航天器布撒的传感器节点 ,无线传感 器网络可以实现对星球表面大范围、长时期、近距离的 监测和探索;利用水下传感器网络进行海洋物理研究、 灾难预防以及对水下军事目标的监测、定位、跟踪. 无 线传感器网络分布在人不便进入或不能进入的区域 , 节点的能量无法得到补充 ,使得如何延长传感器网络 的寿命成为设计上需要考虑的关键因素之一. 当前主 要从拓扑控制、MAC 层协议、路由机制选择、数据融合 等方面实现无线传感器网络节能 ,从而延长网络的生 存周期. 本文从通信协议的角度出发 ,在 LEACH(low2en2 ergy adaptive clustering hierarchy)网络基础上 ,提出了 一种基于移动节点的 LEACH 改进型算法 (the ad2 vanced algorithm of leach based on mobile sensor node , BMSN) ,特点是在网络中加入移动式感测节点 ,且具有 较高能量.簇首的选举机制保证无线传感器网络通信 遵循自由空间模型[3] . 在网络出现能量过低的丛集时 , 移动节点移动至丛集最优簇首位置 ,选举自身担任簇 首 ,延长网络的生存周期. 仿真结果表明新算法具有良 好的性能
第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.net
1 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 ·
·142- 智能系统学报 第3卷 的丛集，对各丛集内的节点做能量分析，判断各个丛 前n个丛集，n为移动节点数目，透过排列组合分 集是否需要移动节点的支持.此阶段制订2个丛集 析，移动节点与需求支持丛集一对一分配，寻找出节 的判断条件，条件1：丛集不平衡；条件2：丛集头能 点总移动距离最短的组合 量过低 最后，在支持分配结束后接着进行丛集调整，分 条件1，丛集不平衡的判断如式(1)： 配到支持的丛集支持移动式感测节点为新的丛集 Eaum Num, 头，旧丛集头则转换为一般丛集成员，移动式传感器 1) Eelusteraverage<Etotahaverag 设定阶段结束」 式中：E品usteraerag表示丛集i内，全部非移动式节点 2.4数据通信 的平均能量；m表示丛集i内，非移动式节点能量 在数据通信阶段，进行控制信息的发布以及真 小于品ser average的节点数目；Fiotalaverag表示环境中 正的丛集运作，接着恢复LEACH运作，进行下列 全部非移动式节点的平均能量；Num为可调整的 工作：1)感测节点将数据传送至所属的丛集头；2)丛 参数Num习). 集头节点接收并聚集数据；3)丛集头传送数据至基 条件2，丛集头能量过低的判断如式2)： 地台.各丛集中节点传送数据至丛集头，皆利用 Ehead current<刀来Ehead need (2) TDMA1的排程，分配各个节点属于自己的传送时 式中：品td表示丛集i的簇头负责在此回合接收 槽，避免产生数据碰撞，而各个丛集之间也都使用各 丛集内成员传送的数据以及将数据聚集并传送至基 自的扩展码(spreading code),避免丛集之间的信号 地台所需要的最少能量！ 影响 curret表示丛集i的丛集头能量】 3 仿真结果 n:可调整的参数(n习). 当丛集的状况符合上述两条件之一时，则认定 仿真分析结果主要是比较BMSN与LEACH、 此丛集需要支持，并且将此丛集列入被支持丛集的 LEAC什C,分析网络的运行时间以及移动节点的利用 优先权排序.当条件2成立的时候，丛集头节点的能 状况.利用Matlab进行仿真比较，参数设定如表1 量可能己经达到担任丛集头所需消耗之高额能量的 表1参数设定值 临界值，因此将视为最高优先支持的丛集，此状况在 Table 1 Parameter define 网络运作的后半段将越趋明显.而条件一成立时，只 动 数 value 是表示在此回合中的某个丛集有部分节点能量较低 网络区域大小 400MB X400MB 所造成丛集成员能量不平衡状况，因此条件一视为 次优先支持的丛集，此状况在网络运作时间内皆可 基站位置坐标 (200,200) 能发生 节点总数 200 2.3移动节点设定 分簇个数 J 在确定需要支持的丛集之后，移动节点设定阶段 节点初始化能量/J 1.0 主要进行3个工作：)计算需要支持丛集的虚拟丛集 头位置：2)判断及分配移动节点，3)新丛集调整 传送包大小/bit 2000 首先，根据各个需要支持丛集的信息，设定支持 数据聚合能耗 5nl/(bit·message) 丛集所分配给移动节点的支持位置.基站收集丛集 Num 节点总数的一半 内节点信息，计算出最优簇首位置，并通知移动节点 100 移动至该位置，即为移动节点移动的距离.在移动节 点能量满足担任簇头消耗能量基础上，确保需要支 模拟在400MBX400MB的环境中，均匀部署 持的丛集消耗的总能量最小.接着，将移动节点分配 200个感测节点（包含数个移动节点）.并且定义环 给需要支持的丛集，分为2种状况： 境中的一般感测节点的死亡数目到达150的时候， 状况1：移动节点数目需要支持的丛集数目 网络终止.一般感测节点能量以1.0J均匀分配.移 状况2：移动节点数目<需要支持的丛集数目. 动节点能量参考文献[9]，假设其能量约17000J 当状况1，通过排列组合分析，移动感测节点与 (可移动距离约15000m).在丛集数目上，分割为5 需求支持丛集一对一分配，寻找出节点总移动距离 个丛集，并且丛集头在数据融合的消耗能量为5/ 最短的组合 (bit·message1).Num为式(1)中丛集不平衡条件 当状况2，由于移动节点数目不足以支持全部 之参数，？为式(2)中丛集头能量过低条件之参数 丛集，根据被支持丛集的优先权排序，选择排序中的 仿真场景分2种情况：casel,移动节点数目小 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.enki.net
的丛集 ,对各丛集内的节点做能量分析 ,判断各个丛 集是否需要移动节点的支持. 此阶段制订 2 个丛集 的判断条件 ,条件 1 :丛集不平衡 ;条件 2 :丛集头能 量过低. 条件 1 ,丛集不平衡的判断如式(1) : E i num > Num , E i cluster2average < Etotal2average . (1) 式中 : E i cluster2average表示丛集 i 内 , 全部非移动式节点 的平均能量; E i num表示丛集 i 内 ,非移动式节点能量 小于 E i cluster2average 的节点数目; Etotal2average 表示环境中 全部非移动式节点的平均能量; Num 为可调整的 参数(Num ≥1) . 条件 2 ,丛集头能量过低的判断如式(2) : E i head2current <η3 E i head2need (2) 式中 : E i head2need表示丛集 i 的簇头负责在此回合接收 丛集内成员传送的数据以及将数据聚集并传送至基 地台所需要的最少能量. E i head2current表示丛集 i 的丛集头能量. η:可调整的参数(η≥1) . 当丛集的状况符合上述两条件之一时 ,则认定 此丛集需要支持 ,并且将此丛集列入被支持丛集的 优先权排序. 当条件 2 成立的时候 ,丛集头节点的能 量可能已经达到担任丛集头所需消耗之高额能量的 临界值 ,因此将视为最高优先支持的丛集 ,此状况在 网络运作的后半段将越趋明显. 而条件一成立时 ,只 是表示在此回合中的某个丛集有部分节点能量较低 所造成丛集成员能量不平衡状况 ,因此条件一视为 次优先支持的丛集 ,此状况在网络运作时间内皆可 能发生. 2. 3 移动节点设定 在确定需要支持的丛集之后,移动节点设定阶段 主要进行 3 个工作:1) 计算需要支持丛集的虚拟丛集 头位置;2)判断及分配移动节点;3)新丛集调整. 首先 ,根据各个需要支持丛集的信息 ,设定支持 丛集所分配给移动节点的支持位置. 基站收集丛集 内节点信息 ,计算出最优簇首位置 ,并通知移动节点 移动至该位置 ,即为移动节点移动的距离. 在移动节 点能量满足担任簇头消耗能量基础上 ,确保需要支 持的丛集消耗的总能量最小. 接着 ,将移动节点分配 给需要支持的丛集 ,分为 2 种状况 : 状况 1 :移动节点数目需要支持的丛集数目. 状况 2 :移动节点数目 < 需要支持的丛集数目. 当状况 1 ,通过排列组合分析 ,移动感测节点与 需求支持丛集一对一分配 ,寻找出节点总移动距离 最短的组合. 当状况 2 ,由于移动节点数目不足以支持全部 丛集 ,根据被支持丛集的优先权排序 ,选择排序中的 前 n 个丛集 , n 为移动节点数目 , 透过排列组合分 析 ,移动节点与需求支持丛集一对一分配 ,寻找出节 点总移动距离最短的组合. 最后 ,在支持分配结束后接着进行丛集调整 ,分 配到支持的丛集支持移动式感测节点为新的丛集 头 ,旧丛集头则转换为一般丛集成员 ,移动式传感器 设定阶段结束. 2. 4 数据通信 在数据通信阶段 ,进行控制信息的发布以及真 正的丛集运作 ,接着恢复 L EACH 运作 ,进行下列 工作 :1) 感测节点将数据传送至所属的丛集头 ;2) 丛 集头节点接收并聚集数据 ;3) 丛集头传送数据至基 地台. 各丛集中节点传送数据至丛集头 ,皆利用 TDMA [8 ]的排程 ,分配各个节点属于自己的传送时 槽 ,避免产生数据碰撞 ,而各个丛集之间也都使用各 自的扩展码(spreading code) ,避免丛集之间的信号 影响. 3 仿真结果 仿真分析结果主要是比较 BMSN 与 LEACH、 LEACH2C,分析网络的运行时间以及移动节点的利用 状况.利用 Matlab 进行仿真比较 ,参数设定如表 1. 表 1 参数设定值 Table 1 Parameter define 参 数 value 网络区域大小 400MB ×400MB 基站位置坐标 (200 ,200) 节点总数 200 分簇个数 5 节点初始化能量 / J 1. 0 传送包大小 / bit 2 000 数据聚合能耗 5nJ/ (bit ·message - 1 ) Num 节点总数的一半 η 100 模拟在 400MB ×400MB 的环境中 ,均匀部署 200 个感测节点 (包含数个移动节点) . 并且定义环 境中的一般感测节点的死亡数目到达 150 的时候 , 网络终止. 一般感测节点能量以 1. 0 J 均匀分配. 移 动节点能量参考文献[ 9 ] ,假设其能量约 17 000 J (可移动距离约 15 000 m) . 在丛集数目上 ,分割为 5 个丛集 ,并且丛集头在数据融合的消耗能量为 5nJ/ (bit ·message - 1 ) . Num 为式(1) 中丛集不平衡条件 之参数 ;η为式(2) 中丛集头能量过低条件之参数. 仿真场景分 2 种情况 : case1 ,移动节点数目小 · 241 · 智 能 系 统 学 报 第 3 卷
第2期 陈珍焰，等：移动节点的L EACH改进型算法 ·143· 于簇数；case2,移动节点数目大于簇数 LEACH的6倍多，相对L EACH-C提高近120%. 分析原因可能是移动节点的数目过多，对于每一个 表2case1case2条件表 丛集而言，都可以分配到移动节点的支持，从而大幅 Table 2 Condition casel~case2 延长网络的生命期.图4可知移动式感测节点在网 case 条件 络生命期结束时仍未耗尽能量，原因是各移动节点 1 高能量移动节点个数=2 所需要负责支持的涵盖范围相对缩小，因此各移动 2 高能量移动节点个数=8 节点在支持上所需要移动的距离也非常的短，所以 才会造成能量剩余许多的情况， 图1为case1在拥有2个移动（高能量）节点的 10 环境下，采用L EACH L EACH-C BMSN的运作时 4.01 --LEACH 间关系图.图2为移动节点的剩余能量与运作时间 #35 -·-LEACH-C 3.0 --BMSN 的关系可以看出，BMSN协议的网络整体运作时 2.5 间大约是LEACH的2.6倍，比LEACH-C提高了 2.0 将近9%，主要原因是移动节点可以依照所设定的 1.5 1.0 条件来进行支持丛集的动作，在LEACH-C方法 05 中，由于高能量节点没有移动的弹性空间，所以高能 0 20 406080100120140 量节点只能被动地等待自己在丛集头选择阶段被选 死广节点个数 为丛集头，因此由图2中可看出LEACH-C中移动 图3Case2网络生存周期 节点的能量下降幅度相当微小，根本无法充分地被 Fig.3 Case2 network survival time 利用，因此网络受到高能量节点的帮助相当的少， 1610 ×10 --LEACH 16 1.4 --LEACH-C 1.2 --BMSN 12 1.0 10 0.8 8 0.6 6 0.4 4 --LEACH-C --BMSN 0.2 2 20 406080100120140 20406080100120140 死亡节点个数 死广节点个数 图1 Casel网络生存周期 图4Case2移动节点剩余能量 Fig.I Casel network survival time Fig.4 Case2 mobile sensor residual energy 10 8 4 结束语 16 14 本文提出基于移动节点的LEACH改进型算 感 10 法，引入新的簇首选举机制确保聚类的大小限制在 一定范围内，减少簇首节点之间的干扰.并且在网络 6 --LEACH-C 中加入移动节点，虽然增加了一定的成本，但透过布 --BMSN 置少数具有高能量的移动节点，并且将移动节点的 20406080100120140 能量平衡地散布在运作周期内，确实提升了整个网 死亡节点个数 络的运作时间.在移动节点数目较多的环境中，在不 图2 casel移动节点剩余能量 会太早耗尽移动节点能量的前提下，可放宽支持丛 Fig.2 Casel mobile sensor residual energy 集的条件参数，让丛集可以尽量得到移动节点的支 图3为case2在拥有8个移动（高能量）节点的 持，对于延长网络时间有进一步的提高」 环境下，采用L EACH L EACH-C BMSN的运作时 参考文献： 间关系图.图4为移动节点的剩余能量与运作时间 的关系.可以看出BMSN协议的网络生存时间是 [1]于海斌，曾鹏.智能无线传感器网络系统[M].北京：科 学出版社，2006. 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net
于簇数 ;case2 ,移动节点数目大于簇数. 表 2 case1～case2 条件表 Table 2 Condition case1～case2 case 条件 1 高能量移动节点个数 = 2 2 高能量移动节点个数 = 8 图 1 为 case1 在拥有 2 个移动 (高能量) 节点的 环境下 ,采用 L EACH、L EACH2C、BMSN 的运作时 间关系图. 图 2 为移动节点的剩余能量与运作时间 的关系. 可以看出 ,BMSN 协议的网络整体运作时 间大约是 L EACH 的 2. 6 倍 ,比 L EACH2C 提高了 将近 9 % ,主要原因是移动节点可以依照所设定的 条件来进行支持丛集的动作. 在 L EACH2C 方法 中 ,由于高能量节点没有移动的弹性空间 ,所以高能 量节点只能被动地等待自己在丛集头选择阶段被选 为丛集头 ,因此由图 2 中可看出 L EACH2C 中移动 节点的能量下降幅度相当微小 ,根本无法充分地被 利用 ,因此网络受到高能量节点的帮助相当的少. 图 3 为 case2 在拥有 8 个移动 (高能量) 节点的 环境下 ,采用 L EACH、L EACH2C、BMSN 的运作时 间关系图. 图 4 为移动节点的剩余能量与运作时间 的关系. 可以看出 BMSN 协议的网络生存时间是 L EACH 的 6 倍多 ,相对 L EACH2C 提高近 120 %. 分析原因可能是移动节点的数目过多 ,对于每一个 丛集而言 ,都可以分配到移动节点的支持 ,从而大幅 延长网络的生命期. 图 4 可知移动式感测节点在网 络生命期结束时仍未耗尽能量 ,原因是各移动节点 所需要负责支持的涵盖范围相对缩小 ,因此各移动 节点在支持上所需要移动的距离也非常的短 ,所以 才会造成能量剩余许多的情况. 4 结束语 本文提出基于移动节点的 L EACH 改进型算 法 ,引入新的簇首选举机制确保聚类的大小限制在 一定范围内 ,减少簇首节点之间的干扰. 并且在网络 中加入移动节点 ,虽然增加了一定的成本 ,但透过布 置少数具有高能量的移动节点 ,并且将移动节点的 能量平衡地散布在运作周期内 ,确实提升了整个网 络的运作时间. 在移动节点数目较多的环境中 ,在不 会太早耗尽移动节点能量的前提下 ,可放宽支持丛 集的条件参数 ,让丛集可以尽量得到移动节点的支 持 ,对于延长网络时间有进一步的提高. 参考文献 : [1 ]于海斌 ,曾 鹏. 智能无线传感器网络系统[ M ]. 北京 :科 学出版社 , 2006. 第 2 期 陈珍焰 ,等 :移动节点的 L EACH 改进型算法 · 341 ·
·144· 智能系统学报 第3卷 [2]BOU HAFS F,MERABTI M,MOKHTAR H.Mobile [8]孙利民，李建中，陈渝，等.无线传感器网络[M],北京： event monitoring protocol for wireless sensor networks 清华大学出版社，2004. [C]//21 International Conference on Advanced Infor- [9]SIBLEY G T,RAHIMI M H,SUKHATME G S. mation Networking and Applications,[S.1.]2007:864- Robomote:a tiny mobile robot platform for large-scale 869. sensor networks [C]//IEEE International Conference on [3]RAPPAPORT T.Wireless communications:principles Robotics and Automation.Washington,DC,2002:1143- and practice M].Beijing:Publishing House of Elec- 1148. tronics Industry,2004. 作者简介： [4]HEINZELMAN W,CHANDRAKASAN A P,BAL- 陈珍焰，男，1983年生，硕士研究生，主 AKRISHNAN H.Energy-efficient communication proto- 要研究方向为无线传感器网络、智能信息 col for wireless microsensor network [C]//Proceedings 控制 of 33rd Annual Hawaii International Conference on Sys tem Sciences Maui:IEEE Computer Society,2000: 3005-3014. [5]HEINZELMAN W,CHANDRAKASAN A P,BAL- 刘贵喜，男，1966生，教授，博士，主要研 A KRISHNAN H.An application specific protocol archi- 究方向为目标探测识别与跟踪滤波、多传感 tecture for wireless microsensor networks [J ]IEEE 器信息融合、图像处理.先后主持或参加30 Transactions on Wireless Communications,2002,1(4): 多项科研项目，曾获国家科技进步三等奖一 660670. 项、机电部科技进步二等奖一项、国防发明 [6]HEINZEL MAN W.Applicatiom specific protocol archi- 专利一项、国家实用新型专利一项，发表论 tecture for wireless networks [D].Boston:Massachu- 文70余篇。 setts Institute of Technology,2000. [7]YANG,Haiming SIKDAR B.Optimal cluster head se- lection in the L EACH architecture [C]//IEEE Interna- tional Performance Computing and Communications Con- ference.[S.l.]2007:93-100. International Symposium on Intelligent Unmanned Systems 2008 2008智能无人系统国际研讨会 The international symposium on intelligent unmanned system 2008 is jointly organized by Nanjing U- niversity of Aeronautics and Astronautics,Konkuk University,and Institute Teknologi Bandung.The joint-event is the 4th conference,extending from International Conference on Emerging System Technolo- gy (ICEST)in 2005,International Conference on Technology Fusion (ICTF)in 2006,both held in Seoul, and International Conference on Intelligent Unmanned Systems (ICIUS)in 2007 hosted in Bali.In 2008, NUAA hosts the ISIUS 2008 as a joint conference with ISNIT 2008 focusing on both theory and application primarily covering the topics on intelligent unmanned/robotic systems and biomimtic technologies.The ob- jective of ISIUS 08 is to bring together researchers and engineers interested in the recent developments in unmanned systems.It will provide an international forum to present and discuss the state-of-the-art intelli- gent unmanned systems.We are pleased to invite you to submit papers and attend ISIUS 08. The ISIUS 08 will be co-located with the International Symposium on Nature-Inspired Technology 2008 Papers should be written in English and describe original work.Submitted papers will be either re- viewed or published (after acceptance).Upon acceptance,at least one of the authors of the paper must reg- ister for the conference in order for the paper to be included in the proceedings Selected outstanding papers will be published in SCI/EI cited journals such as Chinese Science Bulletin(SCI cited),Progress in Natural Science(SCI cited),and Journal of Bionic Engineering(EI cited). 会议网站：http/ibss.naa.edu.cn/main.htm 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
[2 ]BOU HAFS F , MERABTI M , MO KH TAR H. Mobile event monitoring protocol for wireless sensor networks [ C ]/ / 21 st International Conference on Advanced Infor2 mation Networking and Applications , [ S. l. ]. 2007 :8642 869. [3 ] RAPPAPORT T. Wireless communications: principles and practice [ M ]. Beijing : Publishing House of Elec2 tronics Industry , 2004. [ 4 ] HEINZELMAN W , CHANDRA KASAN A P , BAL2 A KRISHNAN H. Energy2efficient communication proto2 col for wireless microsensor network [ C]/ / Proceedings of 33rd Annual Hawaii International Conference on Sys2 tem Sciences . Maui : IEEE Computer Society , 2000 : 300523014. [ 5 ] HEINZELMAN W , CHANDRA KASAN A P , BAL2 A KRISHNAN H. An application2specific protocol archi2 tecture for wireless microsensor networks [J ]. IEEE Transactions on Wireless Communications , 2002 , 1 (4) : 6602670. [6 ] HEINZELMAN W. Application2specific protocol archi2 tecture for wireless networks [ D ]. Boston : Massachu2 setts Institute of Technology , 2000. [7 ] YAN G, Haiming SIKDAR B. Optimal cluster head se2 lection in the L EACH architecture [ C]/ / IEEE Interna2 tional Performance Computing and Communications Con2 ference. [ S. l. ]2007 :932100. [8 ]孙利民 ,李建中 ,陈 渝 ,等. 无线传感器网络[ M ]. 北京 : 清华大学出版社 ,2004. [ 9 ] SIBL EY G T , RA HIMI M H , SU KHA TME G S. Robomote : a tiny mobile robot platform for large2scale sensor networks [C]/ / IEEE International Conference on Robotics and Automation. Washington ,DC , 2002 : 11432 1148. 作者简介 : 陈珍焰 ,男 ,1983 年生 ,硕士研究生 ,主 要研究方向为无线传感器网络、智能信息 控制. 刘贵喜 ,男 ,1966 生 ,教授 ,博士 ,主要研 究方向为目标探测识别与跟踪滤波、多传感 器信息融合、图像处理. 先后主持或参加 30 多项科研项目 ,曾获国家科技进步三等奖一 项、机电部科技进步二等奖一项、国防发明 专利一项、国家实用新型专利一项 ,发表论 文 70 余篇. International Symposium on Intelligent Unmanned Systems 2008 2008 智能无人系统国际研讨会 The international sympo sium on intelligent unmanned system 2008 is jointly organized by Nanjing U2 niversity of Aeronautics and Astronautics , Konkuk University , and Instit ute Teknologi Bandung. The joint2event is t he 4t h conference , extending from International Conference on Emerging System Technolo2 gy (ICEST) in 2005 , International Conference on Technology Fusion (ICTF) in 2006 , bot h held in Seoul , and International Conference on Intelligent Unmanned Systems (ICIUS) in 2007 hosted in Bali. In 2008 , NUAA ho sts t he ISIUS 2008 as a joint conference wit h ISNIT 2008 focusing on both t heory and application primarily covering the topics on intelligent unmanned/ robotic systems and biomimtic technologies. The ob2 jective of ISIUS 08 is to bring toget her researchers and engineers interested in t he recent developments in unmanned systems. It will provide an international forum to present and discuss the state2of2t he2art intelli2 gent unmanned systems. We are pleased to invite you to submit papers and attend ISIUS 08. The ISIUS 08 will be co2located wit h the International Symposium on Nat ure2Inspired Technology 2008 Papers should be written in English and describe original work. Submitted papers will be eit her re2 viewed or p ublished (after acceptance) . Upon acceptance , at least one of the aut hors of the paper must reg2 ister for the conference in order for t he paper to be included in t he proceedings Selected outstanding papers will be p ublished in SCI/ EI cited journals such as Chinese Science Bulletin (SCI cited) , Progress in Nat ural Science (SCI cited) , and Journal of Bionic Engineering ( EI cited) . 会议网站 :http :/ / ibss.nuaa. edu. cn/ main. htm · 441 · 智 能 系 统 学 报 第 3 卷