第9卷第5期 智能系统学报 Vol.9 No.5 2014年10月 CAAI Transactions on Intelligent Systems 0ct.2014 D0l:10.3969/j.issn.1673-4785.201301035 能量均衡多跳分簇路由算法 叶润，王缓缓 (1.电子科技大学自动化工程学院，四川成都611731：2.黄河科技学院信息工程学院，河南郑州450099) 摘要：ZigBee无线传感器网络的生存寿命与节点的能耗直接相关。为了延长网络的寿命，通常采用分簇路由方法。 通过集中成簇管理以及分布簇头竞争的能量均衡多跳分簇路由算法EBMHC(energy balance multi--hop clustering rou- ting algorithm),在一个周期内，使得网络空闲节点休眠，簇头节点担任多条传输、数据融合以及路由维护的功能，以 充分有效利用网络能量。分层管理方式可以缓解网络节点能耗不均衡问题。通过仿真表明，EBMHC算法优于 LEACH和SEP算法，使网络能耗更均衡，延长了网络生存周期。 关键词：ZigBee:WSN;分簇；能量均衡：多跳；路由算法 中图分类号：TP393.04文献标志码：A文章编号：1673-4785(2014)05-0608-05 中文引用格式：叶润，王缓缓.能量均衡多跳分簇路由算法[J].智能系统学报，2014,9(5)：608-612. 英文引用格式：YERun,WANG Huanhuan.WSN energy balance multi-.hop clustering routing algorithm[J].CAAI Transactions on Intelligent Systems,2014,9(5):608-612. WSN energy balance multi-hop clustering routing algorithm YE Run',WANG Huanhuan? (1.College of Automation Engineering,University of Electronic Science and Technology of China,Chengdu 611731,China;2.Col- lege of Information Engineering,Huanghe Science Technology College,Zhengzhou 450099,China) Abstract:The lifetime of ZigBee wireless sensor network is directly related to energy consumption of nodes.In order to extend the life of the network,the clustering routing methods are used.The improved clustering routing algo- rithm-EBMHC(energy balance multi-hop clustering routing algorithm),which adopts centralized rotation-cluste- ring method and distributed competition method of cluster head.This makes the network's idle nodes sleep and cluster head node work acting as multiple transmission.It also has data fusion and routing maintenance in a single cycle,so as to make full and effective use of network energy.Hierarchical management can solve imbalance of net- work node energy consumption.The simulation shows that EBMHC algorithm outperforms LEACH and SEP,making the network energy consumption more balanced and prolonging the network lifetime. Keywords:ZigBee;WSN;clustering;energy balance;multi-hop;routing algorithm ZigBee无线传感器网络[6]由一定数量的无线 多实际工程中，ZigBee节点处于侦听状态，能量利用 模块组成，这些模块一般随机地分布在被监控的区 效率很低，因此设计一种能量均衡有效的路由通信 域，且通常都采用电池供电方式。对于大规模网络 机制对延长网络的生存周期和提高网络稳定性是非 来说，一般不对“死亡”节点进行电池更换。在很 常必要的。 多层分簇路由算法[]可以在保证网络稳定 收稿日期：2013-01-22 性基础上，一定程度减少网络节点能耗，延长网络生 基金项目：河南省教育厅自然科学研究计划资助项目(12B510020):郑 存周期。诸类算法比较经典的分簇算法有文献 州市科技计划资助项目(20120410). 通信作者：叶润.E-mail:810015795@qq.com. [14,19-20]中提出的LEACH算法，该算法是一种
第 ９ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．９ №．５ ２０１４ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１４ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１３０１０３５ 能量均衡多跳分簇路由算法 叶润１ ， 王缓缓２ （１．电子科技大学 自动化工程学院，四川 成都 ６１１７３１；２．黄河科技学院 信息工程学院，河南 郑州 ４５００９９） 摘 要：ＺｉｇＢｅｅ 无线传感器网络的生存寿命与节点的能耗直接相关。 为了延长网络的寿命，通常采用分簇路由方法。 通过集中成簇管理以及分布簇头竞争的能量均衡多跳分簇路由算法 ＥＢＭＨＣ（ｅｎｅｒｇｙ ｂａｌａｎｃｅ ｍｕｌｔｉ－ｈｏｐ ｃｌｕｓｔｅｒｉｎｇ ｒｏｕ⁃ ｔｉｎｇ ａｌｇｏｒｉｔｈｍ），在一个周期内，使得网络空闲节点休眠，簇头节点担任多条传输、数据融合以及路由维护的功能，以 充分有效利用网络能量。 分层管理方式可以缓解网络节点能耗不均衡问题。 通过仿真表明，ＥＢＭＨＣ 算法优于 ＬＥＡＣＨ 和 ＳＥＰ 算法，使网络能耗更均衡，延长了网络生存周期。 关键词：ＺｉｇＢｅｅ；ＷＳＮ；分簇；能量均衡；多跳；路由算法 中图分类号： ＴＰ３９３．０４ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１４）０５⁃０６０８⁃０５ 中文引用格式：叶润， 王缓缓． 能量均衡多跳分簇路由算法［Ｊ］． 智能系统学报， ２０１４， ９（５）： ６０８⁃６１２． 英文引用格式：ＹＥ Ｒｕｎ， ＷＡＮＧ Ｈｕａｎｈｕａｎ． ＷＳＮ ｅｎｅｒｇｙ ｂａｌａｎｃｅ ｍｕｌｔｉ⁃ｈｏｐ ｃｌｕｓｔｅｒｉｎｇ ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍ［ Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１４， ９（５）： ６０８⁃６１２． ＷＳＮ ｅｎｅｒｇｙ ｂａｌａｎｃｅ ｍｕｌｔｉ⁃ｈｏｐ ｃｌｕｓｔｅｒｉｎｇ ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍ ＹＥ Ｒｕｎ １ ， ＷＡＮＧ Ｈｕａｎｈｕａｎ ２ （１． Ｃｏｌｌｅｇｅ ｏｆ Ａｕｔｏｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｅｌｅｃｔｒｏｎｉｃ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ ｏｆ Ｃｈｉｎａ， Ｃｈｅｎｇｄｕ ６１１７３１， Ｃｈｉｎａ； ２． Ｃｏｌ⁃ ｌｅｇｅ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｈｕａｎｇｈｅ Ｓｃｉｅｎｃｅ ＆ Ｔｅｃｈｎｏｌｏｇｙ Ｃｏｌｌｅｇｅ， Ｚｈｅｎｇｚｈｏｕ ４５００９９， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｌｉｆｅｔｉｍｅ ｏｆ ＺｉｇＢｅｅ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ ｉｓ ｄｉｒｅｃｔｌｙ ｒｅｌａｔｅｄ ｔｏ ｅｎｅｒｇｙ ｃｏｎｓｕｍｐｔｉｏｎ ｏｆ ｎｏｄｅｓ． Ｉｎ ｏｒｄｅｒ ｔｏ ｅｘｔｅｎｄ ｔｈｅ ｌｉｆｅ ｏｆ ｔｈｅ ｎｅｔｗｏｒｋ， ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｒｏｕｔｉｎｇ ｍｅｔｈｏｄｓ ａｒｅ ｕｓｅｄ． Ｔｈｅ ｉｍｐｒｏｖｅｄ ｃｌｕｓｔｅｒｉｎｇ ｒｏｕｔｉｎｇ ａｌｇｏ⁃ ｒｉｔｈｍ⁃ＥＢＭＨＣ （ｅｎｅｒｇｙ ｂａｌａｎｃｅ ｍｕｌｔｉ－ｈｏｐ ｃｌｕｓｔｅｒｉｎｇ ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍ）， ｗｈｉｃｈ ａｄｏｐｔｓ ｃｅｎｔｒａｌｉｚｅｄ ｒｏｔａｔｉｏｎ－ｃｌｕｓｔｅ⁃ ｒｉｎｇ ｍｅｔｈｏｄ ａｎｄ ｄｉｓｔｒｉｂｕｔｅｄ ｃｏｍｐｅｔｉｔｉｏｎ ｍｅｔｈｏｄ ｏｆ ｃｌｕｓｔｅｒ ｈｅａｄ． Ｔｈｉｓ ｍａｋｅｓ ｔｈｅ ｎｅｔｗｏｒｋ’ ｓ ｉｄｌｅ ｎｏｄｅｓ ｓｌｅｅｐ ａｎｄ ｃｌｕｓｔｅｒ ｈｅａｄ ｎｏｄｅ ｗｏｒｋ ａｃｔｉｎｇ ａｓ ｍｕｌｔｉｐｌｅ ｔｒａｎｓｍｉｓｓｉｏｎ． Ｉｔ ａｌｓｏ ｈａｓ ｄａｔａ ｆｕｓｉｏｎ ａｎｄ ｒｏｕｔｉｎｇ ｍａｉｎｔｅｎａｎｃｅ ｉｎ ａ ｓｉｎｇｌｅ ｃｙｃｌｅ， ｓｏ ａｓ ｔｏ ｍａｋｅ ｆｕｌｌ ａｎｄ ｅｆｆｅｃｔｉｖｅ ｕｓｅ ｏｆ ｎｅｔｗｏｒｋ ｅｎｅｒｇｙ． Ｈｉｅｒａｒｃｈｉｃａｌ ｍａｎａｇｅｍｅｎｔ ｃａｎ ｓｏｌｖｅ ｉｍｂａｌａｎｃｅ ｏｆ ｎｅｔ⁃ ｗｏｒｋ ｎｏｄｅ ｅｎｅｒｇｙ ｃｏｎｓｕｍｐｔｉｏｎ． Ｔｈｅ ｓｉｍｕｌａｔｉｏｎ ｓｈｏｗｓ ｔｈａｔ ＥＢＭＨＣ ａｌｇｏｒｉｔｈｍ ｏｕｔｐｅｒｆｏｒｍｓ ＬＥＡＣＨ ａｎｄ ＳＥＰ， ｍａｋｉｎｇ ｔｈｅ ｎｅｔｗｏｒｋ ｅｎｅｒｇｙ ｃｏｎｓｕｍｐｔｉｏｎ ｍｏｒｅ ｂａｌａｎｃｅｄ ａｎｄ ｐｒｏｌｏｎｇｉｎｇ ｔｈｅ ｎｅｔｗｏｒｋ ｌｉｆｅｔｉｍｅ． Ｋｅｙｗｏｒｄｓ：ＺｉｇＢｅｅ； ＷＳＮ； ｃｌｕｓｔｅｒｉｎｇ； ｅｎｅｒｇｙ ｂａｌａｎｃｅ； ｍｕｌｔｉ⁃ｈｏｐ； ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍ 收稿日期：２０１３⁃０１⁃２２． 基金项目：河南省教育厅自然科学研究计划资助项目（ １２Ｂ５１００２０）；郑 州市科技计划资助项目（２０１２０４１０）． 通信作者：叶润．Ｅ⁃ｍａｉｌ：８１００１５７９５＠ ｑｑ．ｃｏｍ． ＺｉｇＢｅｅ 无线传感器网络［１⁃ ６ ］ 由一定数量的无线 模块组成，这些模块一般随机地分布在被监控的区 域，且通常都采用电池供电方式。 对于大规模网络 来说，一般不对“死亡”节点进行电池更换［３］ 。 在很 多实际工程中，ＺｉｇＢｅｅ 节点处于侦听状态，能量利用 效率很低，因此设计一种能量均衡有效的路由通信 机制对延长网络的生存周期和提高网络稳定性是非 常必要的。 多层分簇路由算法［ ７ ⁃ １３ ］ 可以在保证网络稳定 性基础上，一定程度减少网络节点能耗，延长网络生 存周期。 诸类算法比较经典的分簇算法有文献 ［１４，１９⁃２０］ 中提出的 ＬＥＡＣＨ 算法，该算法是一种
第5期 叶润，等：能量均衡多跳分簇路由算法 ·609. 自适应分簇算法，它周期动态地形成簇。HEED5] 示。分簇阶段类似于GAF算法里对虚拟单元格的 算法是对LEACH算法随机生成不均匀簇头的一种 划分，如图2所示。 优化。SEPti6]算法是对LEACH算法竞选簇头的一 分簇阶段 种改进，文献[17]中提出的GAF算法是一种基于地 理位置的分簇算法。文献[7,18]采用了固定分区 的方法进行区域分簇。 能量均衡多跳分簇路由算法(EBMHC)的基本 、簇路由 、竞争簇头 思想为：虚拟单元格划分为集中式划分，生存簇头阶 图1 EBMHR算法执行过程 段为分布式方式，同时采用动态路由方式和轮转的 Fig.1 EBMHR algorithm execution process 方式实现数据的多跳传输和能量均衡。通过仿真结 果表明，EBMHC算法均衡了网络节点能量，且没有 影响网络数据传输，延长了网络生存寿命。 4050 404 406 403 1 能量均衡多跳分簇路由算法 303 302 407 203 202 402 在簇结构中，簇首不仅要收集簇内节点采集的 304 30N 408 数据，而且还负责数据融合、转发，路由生成与维护。 204 102 101 201 1404 簇头的这些功能决定了其必须处于高负荷工作状 0 409 205 103104 208 416 态，这就使得网络能量分布不平衡。 1305 308 LEACH算法在一定程度上实现了网络能量均 206 207 410 415 衡的目的，但随机簇头生成方式存在簇头分布不均 306 307 411 414 匀的问题。HEED算法是对LEACH算法的改进，其 412 13 考虑了簇内的通信开销，使得全网能量更均衡，但在 生产簇头方式上采取迭代算法，这就加大了成簇的 开销。GAF算法的思想是根据地理信息将网络划 图2 EBMHR算法分簇示意 分为网格，网络节点能量均衡性差。SEP算法在 Fig.2 EBMHR algorithm clustering diagram LEACH算法的基础上，对不同剩余能量的节点采 EBMHR的分簇思想以基站为中心的圆形区域 用不同的选举概率，但簇头分布不均匀的问题并没 建立极坐标系，然后进行环形分层，最后将每层的环 有得到改进。 等分。论文根据以上思想，且考虑算法的复杂度，确 本文提出一种ZigBee无线传感器网络能量均 定第一层环四等分，第2和第3层环分布8等分，第 衡多跳分簇路由算法(EBMHC),EBMHC算法在分 4、5层环16等分，5层以外每增加2层环，等分数是 簇阶段引入随机轮转日角，避免某个扇区内节点数 新增较小环数的4倍。论文中传感器节点随机布 量过多，在竞争簇头阶段，引入能量因子，使剩余能 置，为了生成的簇头节点功耗相当，划分的每个簇面 量较多的节点优先成为簇头：簇路由阶段，采取数据 积应接近。 融合方式，簇头节点将同类数据进行融合处理，从而 设r。=0,基站到第一层环距离设为11，则通过 实现无线传感器网络能耗均衡。 式(I)可计算基站到第n层环的距离rn。 1.1网络模型假设 1 对ZigBee无线传感器网络模型作出如下假设： 4nm(。2-12) 1I)ZigBee无线传感器网络中每个节点最初能 (n=2,4,6,…) 量相等，且传感器节点具有相同的硬件平台： 4n-10(.2-13 ,2=1 2)传感器节点相对于基站的极坐标且放置后 4 位置不变： (n=3,5,7,…) (1) 3)基站位于中心，不考虑基站的能耗，传感器 由式(1)可得出每层到基站的距离： 节点随机放置在圆形区域中。 .=√m2+-1(n=2,4,6,… 1.2算法描述 EBMHC算法执行过程分为每个周期3个阶段： .=n-10n+17(n=3,5,7,…) 分簇阶段、簇头竞争阶段和簇路由阶段。如图1所 (2) 记每层的距离宽度为Ln,显然L1=rl,则可得出：
自适应分簇算法，它周期动态地形成簇。 ＨＥＥＤ ［ １５ ］ 算法是对 ＬＥＡＣＨ 算法随机生成不均匀簇头的一种 优化。 ＳＥＰ ［ １６ ］算法是对 ＬＥＡＣＨ 算法竞选簇头的一 种改进，文献［１７］中提出的 ＧＡＦ 算法是一种基于地 理位置的分簇算法。 文献［７，１８］ 采用了固定分区 的方法进行区域分簇。 能量均衡多跳分簇路由算法（ＥＢＭＨＣ）的基本 思想为：虚拟单元格划分为集中式划分，生存簇头阶 段为分布式方式，同时采用动态路由方式和轮转的 方式实现数据的多跳传输和能量均衡。 通过仿真结 果表明，ＥＢＭＨＣ 算法均衡了网络节点能量，且没有 影响网络数据传输，延长了网络生存寿命。 １ 能量均衡多跳分簇路由算法 在簇结构中，簇首不仅要收集簇内节点采集的 数据，而且还负责数据融合、转发，路由生成与维护。 簇头的这些功能决定了其必须处于高负荷工作状 态，这就使得网络能量分布不平衡。 ＬＥＡＣＨ 算法在一定程度上实现了网络能量均 衡的目的，但随机簇头生成方式存在簇头分布不均 匀的问题。 ＨＥＥＤ 算法是对 ＬＥＡＣＨ 算法的改进，其 考虑了簇内的通信开销，使得全网能量更均衡，但在 生产簇头方式上采取迭代算法，这就加大了成簇的 开销。 ＧＡＦ 算法的思想是根据地理信息将网络划 分为网格，网络节点能量均衡性差。 ＳＥＰ 算法在 ＬＥＡＣＨ 算法的基础上， 对不同剩余能量的节点采 用不同的选举概率，但簇头分布不均匀的问题并没 有得到改进。 本文提出一种 ＺｉｇＢｅｅ 无线传感器网络能量均 衡多跳分簇路由算法（ＥＢＭＨＣ），ＥＢＭＨＣ 算法在分 簇阶段引入随机轮转 θ 角，避免某个扇区内节点数 量过多，在竞争簇头阶段，引入能量因子，使剩余能 量较多的节点优先成为簇头；簇路由阶段，采取数据 融合方式，簇头节点将同类数据进行融合处理，从而 实现无线传感器网络能耗均衡。 １．１ 网络模型假设 对 ＺｉｇＢｅｅ 无线传感器网络模型作出如下假设： １）ＺｉｇＢｅｅ 无线传感器网络中每个节点最初能 量相等，且传感器节点具有相同的硬件平台； ２）传感器节点相对于基站的极坐标且放置后 位置不变； ３）基站位于中心，不考虑基站的能耗，传感器 节点随机放置在圆形区域中。 １．２ 算法描述 ＥＢＭＨＣ 算法执行过程分为每个周期 ３ 个阶段： 分簇阶段、簇头竞争阶段和簇路由阶段。 如图 １ 所 示。 分簇阶段类似于 ＧＡＦ 算法里对虚拟单元格的 划分，如图 ２ 所示。 图 １ ＥＢＭＨＲ 算法执行过程 Ｆｉｇ．１ ＥＢＭＨＲ ａｌｇｏｒｉｔｈｍ ｅｘｅｃｕｔｉｏｎ ｐｒｏｃｅｓｓ 图 ２ ＥＢＭＨＲ 算法分簇示意 Ｆｉｇ．２ ＥＢＭＨＲ ａｌｇｏｒｉｔｈｍ ｃｌｕｓｔｅｒｉｎｇ ｄｉａｇｒａｍ ＥＢＭＨＲ 的分簇思想以基站为中心的圆形区域 建立极坐标系，然后进行环形分层，最后将每层的环 等分。 论文根据以上思想，且考虑算法的复杂度，确 定第一层环四等分，第 ２ 和第 ３ 层环分布 ８ 等分，第 ４、５ 层环 １６ 等分，５ 层以外每增加 ２ 层环，等分数是 新增较小环数的 ４ 倍。 论文中传感器节点随机布 置，为了生成的簇头节点功耗相当，划分的每个簇面 积应接近。 设 ｒ０ ＝ ０，基站到第一层环距离设为 ｒ１ ，则通过 式（１）可计算基站到第 ｎ 层环的距离 ｒｎ 。 １ ４ πｒ１ ２ ＝ １ ４ｎ π（ｒｎ ２ － ｒｎ－１ ２ ） （ｎ ＝ ２，４，６，…） １ ４ πｒ１ ２ ＝ １ ４（ｎ － １） π（ｒｎ ２ － ｒｎ－１ ２ ） ì î í ï ï ï ï ï ï （ｎ ＝ ３，５，７，…） （１） 由式（１）可得出每层到基站的距离： ｒｎ ＝ ｎｒ１ ２ ＋ ｒｎ－１ ２ （ｎ ＝ ２，４，６，…） ｒｎ ＝ （ｎ － １）ｒ１ ２ ＋ ｒｎ－１ ２ （ｎ ＝ ３，５，７，…） { （２） 记每层的距离宽度为 Ｌｎ，显然 Ｌ１ ＝ ｒ１，则可得出： 第 ５ 期 叶润，等：能量均衡多跳分簇路由算法 ·６０９·
·610 智能系统学报 第9卷 L.=t。-r-1=Vm12+rm-17 首次成簇轮转角设置为0=0°，区域内每个节 (n=2,4,6,…) 点设置的极坐标计算出簇号。记节点i的极坐标为 (0,d:),极坐标中的0：为节点i与x轴正方向的夹 Ln=7。-1=√(n-1)n1+-17-- 角，d,为基站与节点i的距离，则节点i的簇号CD (n=3,5,7,…） 可由式(3)计算： 100nm+2n(0-8)(100n+1)T+2n(0:-8) T （Tm-1<d:≤Tm,n=1,2,4,6,…) CID (3) 100nm+2(n-1)(0:-0)(100n+1)T+2(n-1)(0:-8) (rm-1<d≤Tn,n=3,5,7,…) 记其中式(3)中的“(]”为取整求最大，0为轮 入工作模式： 转角，首次不进行轮转，0=0。节点极坐标（π/3， 5)簇头负责扇内数据收集、融合及向基站转发： 2r1)通过式(3)计算CD=302,即第三层环第二扇 6)基站广播轮转帧，以告知网络所有节点进行 区。倘若CID/100=0,CID=CD+节点扇区。 周期轮转。 “外右定则”：扇区的4个边界分别记为扇内 图3是通过Matlab进行仿真的分簇结果图，图 边、扇外边、扇左与扇右，扇内外边为弧线，扇左右为 中星点为普通节点，圆圈为簇头，基站位于圆心，由 直线，扇内边长度小于扇外边，以基站为中心往外， 五角星表示。 确定扇左与扇右：处于扇边上的节点，位于扇外边与 60r 扇右上的节点被划分到本扇区。 40 每个轮转周期由基站控制，并广播告知网络内节 点，轮转角θ在(0，元/8)中随机选取，轮转的目的可以保 30 证每个扇区内节点数量接近且扇内总能量相当。 簇头竞争阶段通过扇区的划分，通过式(3)》 0 每个节点可计算出一个CD,为了避免簇头能量消 20 耗过快而“死亡”且考虑算法复杂度，论文采用竞争 方式来选择簇头，以节点剩余能量作为簇头竞争的 -40 主要因素，以达到能量均衡的目的。EBMHC算法 -60 簇头竞争方法为 -60-40-200204060 距离m 1)扇内每个节点设置休眠时间Tad,Tm由式 图3 EBMHR算法分簇示意 (4)得到： Fig.3 EBMHR algorithm clustering diagram T-(B,-E) (4) 簇路由阶段簇头负责扇内节点数据融合发送 以及簇头之间路由。论文利用文献[1,3]中提到的 式(4)中E,为节点当前剩余能量，参数t。为参考时 AODVir算法，通过AODVir算法来完成网络路由的 间，参数E为参考能量，参数E大小小于节点截止 形成与维护，本文不再对AODVir算法进行详述。 工作能量。自动唤醒的节点在等待一个随机的时间 间隔内，如果没有接收到扇内簇头的广播帧，则该节 2 仿真及分析 点自动转变为候选簇头，执行2)，如果接收到扇内 2.1能量消耗模型 簇头广播帧，则执行4)； ZigBee无线传感器网络采用文献[14-17]中提 2)候选簇头向扇内广播簇头声明帧，避免扇内 到的自由空间模型与多径衰减模型，参数k为发送 节点变成候选簇头，在候选簇头声明期间如果接收 的比特个数，射频发送能耗可由下式得到： 扇内其他候选簇头的声明帧，则两个簇头都比较节 点能量，优势节点自动从候选簇头升级为簇头，执行 k×Ee+k×Ee×dP,d<do E(k,d)= 3),劣势节点降级为普通节点，并执行4)； k×Eae+k×em×,d≥d 3)簇头节点以Ta为周期向扇内节点广播声明 射频接收能耗可由式(5)得到： 帧，并执行5)： E(k)=k×En (5) 4)普通节点更新簇头信息及路由，以通过簇头 处理器数据融合能耗由式(6)进行计算：式中：E 转发数据，并执行1)，休眠期间可通过事件中断进 表示发端电路运算和处理每个比特能耗；E:表示融
Ｌｎ ＝ ｒｎ － ｒｎ－１ ＝ ｎｒ１ ２ ＋ ｒｎ－１ ２ － ｒｎ－１ （ｎ ＝ ２，４，６，…） Ｌｎ ＝ ｒｎ － ｒｎ－１ ＝ （ｎ － １）ｒ１ ２ ＋ ｒｎ－１ ２ － ｒｎ－１ （ｎ ＝ ３，５，７，…） ì î í ï ï ï ï ï ï 首次成簇轮转角设置为q ＝ ０ °，区域内每个节 点设置的极坐标计算出簇号。 记节点 ｉ 的极坐标为 （ qｉ，ｄｉ），极坐标中的qｉ为节点 ｉ 与 ｘ 轴正方向的夹 角，ｄｉ为基站与节点 ｉ 的距离， 则节点 ｉ 的簇号 ＣＩＤ 可由式（３）计算： ＣＩＤ ＝ （ １００ｎπ ＋ ２ｎ（θｉ － θ） π ， （１００ｎ ＋ １）π ＋ ２ｎ（θｉ － θ） π ］ （ｒｎ－１ ＜ ｄｉ ≤ ｒｎ ，ｎ ＝ １，２，４，６，…） （ １００ｎπ ＋ ２（ｎ － １）（θｉ － θ） π ， （１００ｎ ＋ １）π ＋ ２（ｎ － １）（θｉ － θ） π ］ （ｒｎ－１ ＜ ｄｉ ≤ ｒｎ ，ｎ ＝ ３，５，７，…） ì î í ï ï ï ï ï ï ï ï （３） 记其中式（３）中的“（ ］ ”为取整求最大，q为轮 转角，首次不进行轮转， q ＝ ０。 节点极坐标（ p ／ ３， ２ｒ１ ）通过式（３）计算 ＣＩＤ ＝ ３０２，即第三层环第二扇 区。 倘若 ＣＩＤ／ １００ ＝ ０，ＣＩＤ＝ＣＩＤ＋节点扇区。 “外右定则”：扇区的 ４ 个边界分别记为扇内 边、扇外边、扇左与扇右，扇内外边为弧线，扇左右为 直线，扇内边长度小于扇外边，以基站为中心往外， 确定扇左与扇右；处于扇边上的节点，位于扇外边与 扇右上的节点被划分到本扇区。 每个轮转周期由基站控制，并广播告知网络内节 点，轮转角q在（０，p／ ８）中随机选取，轮转的目的可以保 证每个扇区内节点数量接近且扇内总能量相当。 簇头竞争阶段 通过扇区的划分，通过式（３） 每个节点可计算出一个 ＣＩＤ，为了避免簇头能量消 耗过快而“死亡”且考虑算法复杂度，论文采用竞争 方式来选择簇头，以节点剩余能量作为簇头竞争的 主要因素，以达到能量均衡的目的。 ＥＢＭＨＣ 算法 簇头竞争方法为 １）扇内每个节点设置休眠时间 Ｔｒａｎｄ ，Ｔ ｒａｎｄ由式 （４）得到： Ｔｒａｎｄ ＝ ｔ ０ （Ｅｒ － Ｅｃ） ２ （４） 式（４）中 Ｅｒ为节点当前剩余能量，参数 ｔ ０为参考时 间，参数 Ｅｃ为参考能量，参数 Ｅｃ大小小于节点截止 工作能量。 自动唤醒的节点在等待一个随机的时间 间隔内，如果没有接收到扇内簇头的广播帧，则该节 点自动转变为候选簇头，执行 ２），如果接收到扇内 簇头广播帧，则执行 ４）； ２）候选簇头向扇内广播簇头声明帧，避免扇内 节点变成候选簇头，在候选簇头声明期间如果接收 扇内其他候选簇头的声明帧，则两个簇头都比较节 点能量，优势节点自动从候选簇头升级为簇头，执行 ３），劣势节点降级为普通节点，并执行 ４）； ３）簇头节点以 Ｔｃｉｄ为周期向扇内节点广播声明 帧，并执行 ５）； ４）普通节点更新簇头信息及路由，以通过簇头 转发数据，并执行 １），休眠期间可通过事件中断进 入工作模式； ５）簇头负责扇内数据收集、融合及向基站转发； ６）基站广播轮转帧，以告知网络所有节点进行 周期轮转。 图 ３ 是通过 Ｍａｔｌａｂ 进行仿真的分簇结果图，图 中星点为普通节点，圆圈为簇头，基站位于圆心，由 五角星表示。 图 ３ ＥＢＭＨＲ 算法分簇示意 Ｆｉｇ．３ ＥＢＭＨＲ ａｌｇｏｒｉｔｈｍ ｃｌｕｓｔｅｒｉｎｇ ｄｉａｇｒａｍ 簇路由阶段 簇头负责扇内节点数据融合发送 以及簇头之间路由。 论文利用文献［１，３］中提到的 ＡＯＤＶｊｒ 算法，通过 ＡＯＤＶｊｒ 算法来完成网络路由的 形成与维护，本文不再对 ＡＯＤＶｊｒ 算法进行详述。 ２ 仿真及分析 ２．１ 能量消耗模型 ＺｉｇＢｅｅ 无线传感器网络采用文献［１４⁃１７］中提 到的自由空间模型与多径衰减模型，参数 ｋ 为发送 的比特个数，射频发送能耗可由下式得到： Ｅｔｘ（ｋ，ｄ） ＝ ｋ × Ｅｅｌｅｃ ＋ ｋ × εｆｓ × ｄ ２ ，ｄ ＜ ｄ０ ｋ × Ｅｅｌｅｃ ＋ ｋ × εｍｐ × ｄ ４ ，ｄ ≥ ｄ０ { 射频接收能耗可由式（５）得到： Ｅｒｘ（ｋ） ＝ ｋ × Ｅｅｌｅｃ （５） 处理器数据融合能耗由式（６）进行计算：式中：Ｅｅｌｅｃ 表示发端电路运算和处理每个比特能耗；ＥＤＡ表示融 ·６１０· 智 能 系 统 学 报 第 ９ 卷
第5期 叶润，等：能量均衡多跳分簇路由算法 .611- 合每个比特数据的能耗；Es和ε分别为自由空间模 型和多径衰减模型系数；d。为自由空间和多径衰减 100 …LEACH 传播模型的门限距离，d。可由下式计算： 00 -SEP ----EBMHC-3 d。= 8 EBMHC-6 若实际发送距离d<d。时，传输能耗采用自由空间模 型：若实际发送距离d≥d时，传输能耗采用多径衰 减模型。 2.2仿真参数 0 10 考虑EBMHC算法环数的不同而对仿真结果的 0 影响，论文分别将EBMHC网络划分3环(EBMHC 0510152025303540x10 3)和6环(EBMHC-6)2种，并同SEP、LEACH算法 生存时间/轮 进行性能比较，为了便于比较，EBMHC的参数同 图4网络生存周期对比 LEACH算法和SEP算法参数一致，利用Mtalab在 Fig.4 Network lifetime contrast 区域面积为10m的网络中随机生成数量为100的 图5为基站接收的总数据包数量的比较，EBM 普通节点，生成后节点位置在仿真期间不变。EBM- HC-3的数量为13748个，EBMHC-6的数量为 HC的其他Matlab仿真参数如表1所示。 14152个，SEP的数量为13748个，LEACH的数量 表1仿真参数 为13620个，EBMHC-3和EBMHC-6的总数据包数 Table 1 EBMHC Simulation parameters 量分别比SEP提高了1.58%和2.69%，分别比 名称 数值 LEACH提高了2.44%和3.55%。通过基站接收总 网络面积/m2 104 数据包个数比较，EBMHC网络性能更好。 通过以上仿真结果可知，EBMHC网络对于节 节点数/个 100 点数量不是太多的情况下，划分的环数不易过多：但 Ed,EE x/n bit" 50 EBMHC网络环数也不能太少，环数太少必然导致 节点初始能量E/J 0.5 扇区以及簇头太少，最终使得信道拥塞，包接收率 es/p·bit1·m2 10 (PRR)过低。实际应用中，可以通过调节第一层环 Eau/l·bit' 5 宽度，的来调节网络的环数，以达到网络性能最佳。 ep/pW·bit·m2 0.0013 ×10 15 2.3仿真结果及分析 论文通过网络生成周期与基站接收总数据包数 量两个参数进行性能对比，在实际应用中，个别节点 10 的损坏不会对网络产生太大冲击，但网络生成周期 也不以网络内最后一个节点能量耗尽为基准，而是 以网络内一部分节点死亡以及基站数据的大量减少 5 …LEACH ----SEP 为准，所以网络能耗均衡很重要，达到真正的延长网 -EBMHC-3 ·EBMHC-6 络生存周期。本来以网络内首次出现能量耗完节点 ×101 的轮数为比较依据。 0.51.01.52.02.53.03.54.0 生存时间/轮 图4的网络生成周期仿真结果显示，EBMHC-3 同SEP、LEACH2个算法比较，EBMHC-3延长了网 图5基站收到的数据对比 络寿命，SEP在第1042轮首次出现节点能量耗完， Fig.5 Comparison of the data received by the base station LEACH在第957轮首次出现节点能量耗完，而EB- 3 结束语 MHC-3首次‘死亡’节点出现在第1244轮，相比 SEP算法，网络寿命增加了19.39%，比LEACH寿命 本文以延长ZigBee无线传感器网络寿命为目 增加了29.98%。但EBMHC-6的优势不明显，因为 的，通过对相关协议的研究，提出了EBMHC算法， 对于100个节点的小网络，环数过多，扇区数量越大 EBMHC算法利用网络区域划分虚拟扇区进行成 能量消耗越快。 簇，且采用集中成簇和分布式簇头竞争的方式，以节
合每个比特数据的能耗；eｆｓ和eｍｐ分别为自由空间模 型和多径衰减模型系数；ｄ０为自由空间和多径衰减 传播模型的门限距离，ｄ０可由下式计算： ｄ０ ＝ εｆ ｓ εｍｐ 若实际发送距离 ｄ＜ｄ０时，传输能耗采用自由空间模 型；若实际发送距离 ｄ≥ｄ０时，传输能耗采用多径衰 减模型。 ２．２ 仿真参数 考虑 ＥＢＭＨＣ 算法环数的不同而对仿真结果的 影响，论文分别将 ＥＢＭＨＣ 网络划分 ３ 环（ＥＢＭＨＣ⁃ ３）和 ６ 环（ＥＢＭＨＣ⁃６） ２ 种，并同 ＳＥＰ、ＬＥＡＣＨ 算法 进行性能比较，为了便于比较，ＥＢＭＨＣ 的参数同 ＬＥＡＣＨ 算法和 ＳＥＰ 算法参数一致，利用 Ｍｔａｌａｂ 在 区域面积为 １０ ４ｍ ２的网络中随机生成数量为 １００ 的 普通节点，生成后节点位置在仿真期间不变。 ＥＢＭ⁃ ＨＣ 的其他 Ｍａｔｌａｂ 仿真参数如表 １ 所示。 表 １ 仿真参数 Ｔａｂｌｅ １ ＥＢＭＨＣ Ｓｉｍｕｌａｔｉｏｎ ｐａｒａｍｅｔｅｒｓ 名称 数值 网络面积／ ｍ ２ １０ ４ 节点数／ 个 １００ Ｅ ｅｌｅｃ，Ｅｒｘ ，Ｅｔ ｘ ／ ｎＪ·ｂｉｔ －１ ５０ 节点初始能量 Ｅ ０ ／ Ｊ ０．５ eｆｓ ／ ｐＪ·ｂｉｔ －１·ｍ －２ １０ ＥＤＡ ／ ｎＪ·ｂｉｔ －１ ５ eｍｐ ／ ｐＪ·ｂｉｔ －１·ｍ －２ ０．００１３ ２．３ 仿真结果及分析 论文通过网络生成周期与基站接收总数据包数 量两个参数进行性能对比，在实际应用中，个别节点 的损坏不会对网络产生太大冲击，但网络生成周期 也不以网络内最后一个节点能量耗尽为基准，而是 以网络内一部分节点死亡以及基站数据的大量减少 为准，所以网络能耗均衡很重要，达到真正的延长网 络生存周期。 本来以网络内首次出现能量耗完节点 的轮数为比较依据。 图 ４ 的网络生成周期仿真结果显示，ＥＢＭＨＣ⁃３ 同 ＳＥＰ、ＬＥＡＣＨ ２ 个算法比较，ＥＢＭＨＣ⁃３ 延长了网 络寿命，ＳＥＰ 在第 １ ０４２ 轮首次出现节点能量耗完， ＬＥＡＣＨ 在第 ９５７ 轮首次出现节点能量耗完， 而 ＥＢ⁃ ＭＨＣ⁃３ 首次‘死亡’ 节点出现在第 １ ２４４ 轮，相比 ＳＥＰ 算法，网络寿命增加了 １９．３９％，比 ＬＥＡＣＨ 寿命 增加了 ２９．９８％。 但 ＥＢＭＨＣ⁃６ 的优势不明显，因为 对于 １００ 个节点的小网络，环数过多，扇区数量越大 能量消耗越快。 图 ４ 网络生存周期对比 Ｆｉｇ．４ Ｎｅｔｗｏｒｋ ｌｉｆｅｔｉｍｅ ｃｏｎｔｒａｓｔ 图 ５ 为基站接收的总数据包数量的比较，ＥＢＭ⁃ ＨＣ⁃３ 的 数 量 为 １３ ７４８ 个， ＥＢＭＨＣ⁃６ 的 数 量 为 １４ １５２个，ＳＥＰ 的数量为 １３ ７４８ 个，ＬＥＡＣＨ 的数量 为 １３ ６２０ 个，ＥＢＭＨＣ⁃３ 和 ＥＢＭＨＣ⁃６ 的总数据包数 量分别 比 ＳＥＰ 提 高 了 １． ５８％ 和 ２． ６９％， 分 别 比 ＬＥＡＣＨ 提高了 ２．４４％和 ３．５５％。 通过基站接收总 数据包个数比较，ＥＢＭＨＣ 网络性能更好。 通过以上仿真结果可知，ＥＢＭＨＣ 网络对于节 点数量不是太多的情况下，划分的环数不易过多；但 ＥＢＭＨＣ 网络环数也不能太少，环数太少必然导致 扇区以及簇头太少，最终使得信道拥塞，包接收率 （ＰＲＲ）过低。 实际应用中，可以通过调节第一层环 宽度 ｒ１的来调节网络的环数，以达到网络性能最佳。 图 ５ 基站收到的数据对比 Ｆｉｇ．５ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｈｅ ｄａｔａ ｒｅｃｅｉｖｅｄ ｂｙ ｔｈｅ ｂａｓｅ ｓｔａｔｉｏｎ ３ 结束语 本文以延长 ＺｉｇＢｅｅ 无线传感器网络寿命为目 的，通过对相关协议的研究，提出了 ＥＢＭＨＣ 算法， ＥＢＭＨＣ 算法利用网络区域划分虚拟扇区进行成 簇，且采用集中成簇和分布式簇头竞争的方式，以节 第 ５ 期 叶润，等：能量均衡多跳分簇路由算法 ·６１１·
.612. 智能系统学报 第9卷 点节点剩余能量为簇头竞争参考因素，有效均衡网 罗，2007,29(12)：3006-3010. 络节点能量。最后的仿真结果表明，EBMHC算法 [12]蒋畅江，石为人.能量均衡的无线传感器网络非均匀分 与SEP、LEACH两种算法相比，EBMHC算法不仅延 簇路由协议[J].软件学报，2012,23(5)：1222-1232. 长了网络寿命，而且没有影响网络的稳定性。 JIANG Changjiang,SHI Weiren.Energy-balanced unequal clustering routing protocol for wireless sensor networks[J]. 参考文献： Journal of Software,2012,23(5):1222-1232. [13]孟中楼，王殊，赵峰，等.分簇式无线传感器网络睡眠调 [1]李文仲，段朝玉.ZigBee2006无线网络与无线定位实战 度机制研究[J].微电子学与计算机，2009,26(7)：9. [M].北京：北京航空航天大学出版社，2008：26-27. 16. [2]毕开春.国外物联网透视[M].北京：电子工业出版社， MENG Zhonglou,WANG Shu,ZHAO Feng,et al.Re- 2012:10-19. search on sleeping scheduling in clustered wireless sensor [3]孙利民，李建中.无线传感器网络[M].北京：清华大学 networks[J].Microelectronics and Computer,2009,26 出版社，2005：89-108 (7):9-16. [4]AKYILDIZ I F,WEILIAN S,SANKARASUBRAMANIAM [14]HEINZELMAN W,CHANDRAKASAN A,BALAKRISH- Y.A survey on sensor networks[J].IEEE Communications NAN H.An application-specific protocol architecture for Magazine,2002,40(8):102-114. wireless micro-sensor networks[J].IEEE Transactions on [5]NI L M,LIU Y H,ZHU Y M.China's national research Wireless Communications,2002,1(4):660-670. project on wireless sensor networks J].IEEE Wireless [15]YOUNIS O,FAHMY S.Distributed clustering in ad-hoc Communications,2007,14(6):78-83. sensor networks:a hybrid energy-efficient approach[C]/ [6]SUNIL J,PRABHAT R.A survey:topology control for Proc 13%Joint Conf on IEEE Computer and Communica- wireless sensor networks[C]//Proceedings of IEEE Inter- tions Societies.Chicago,USA,2004:629-640. national Conference on Signal Processing Communications [16]SMARAGDAKIS G,MATTA I,BESTAVROS A.SEP:a and Networking.Chennai,India,2008:422-427. stable election protocol for clustered heterogeneous wireless [7]毕晓伟，郭文超，冯文江.WSN中能量有效分簇多跳路由 sensor networks[C]//Proc of Int'I Workshop on SANPA. 算法[J].电路与系统学报，2011,16(2)：13-18. Boston,USA,2004:146-173. BI Xiaowei,GUO Wenchao,FENG Wenjiang.Energy-effi- [17]XU Y,HEIDEMANN J,ESTRIN D.Geography informed cient clustering multi-hop routing algorithm for wireless sen- energy conservation for ad-hoc routing[C]//Proc 7h An- sor networksJ.Journal of Circuits and Systems,2011,16 nual Int'I Conf on Mobile Computing and Networking. (2):13-18. Rome,taly,2001:70-84. [8]任东海，尚凤军，王寅.一种基于时间延迟机制的无线传 [18]XIANG M,SHI W R,JIANG C J.et al.Energy efficient 感器网络分簇算法[J].传感技术学报，2009,22(11)： clustering algorithm for maximizing lifetime of wireless sen- 1645-1649 sor networks[J].AEU-Int'1 Journal of Electronic and REN Donghai,SHANG Fengjun,WANG Yin.A clustering Communication,2010,64(4):289-298. hierarchy arithmetic based on time delay for wireless sensor [19]WANG A,HEINZELMAN W,CHANDRAKASAN A.En- networks[J].Journal of Transduction Technology,2009,22 ergy-scalable protocols for battery-operated microsensor (11):1645-1649. networks[C]//Proc 1999 IEEE Workshop Signal Process- [9]雷磊，薛小龙，周进华，等实现节点负载均衡的无线传感 ing Systems.Taipei,China,1999:483-492. 器网络能量高效分簇方法[J].应用科学学报，2010,28 20]DENG J,HAN Y,HEINZELMAN W,et al.Balanced-en- (3):551-560. ergy sleep scheduling scheme for high-density cluster-based LEI Lei,XUE Xiaolong,ZHOU Jinhua,et al.Load balan- sensor networks [J].Computer Communications,2005, cing energy efficient clustering for wireless sensor networks 28(14):1631-1642 J].Journal of Applied Sciences,2010,28(3):551-560. 作者简介： [10]张荣博，曹建福.利用蚁群优化的非均匀分簇无线传感 叶润，男，1986年生，硕士研究生，主 器网络路由算法[J].西安交通大学学报，2010,44(6)： 要研究方向为无线传感器网络。 33-38. ZHANG Rongbo,CAO Jianfu.Uneven clustering routing algorithm for wireless sensor networks based on ant colony optimization[J].Journal of Xi'an Jiaotong University, 2010,44(6):33-38. [11]郭彬，李喆无线传感器网络中基于剩余能量的联合选 举动态成簇路由算法[J].电子与信息学报，2007,29 王缓缓，女，1979年生，讲师， (12)：3006-3010. 主要研究方向为无线传感器网络。 GUO Bin,LI Zhe.United voting dynamic cluster routing algorithm based on residual-energy in wireless sensor net- works[J].Joumal of Electronics Information Technolo-
点节点剩余能量为簇头竞争参考因素，有效均衡网 络节点能量。 最后的仿真结果表明，ＥＢＭＨＣ 算法 与 ＳＥＰ、ＬＥＡＣＨ 两种算法相比，ＥＢＭＨＣ 算法不仅延 长了网络寿命，而且没有影响网络的稳定性。 参考文献： ［１］李文仲， 段朝玉． ＺｉｇＢｅｅ２００６ 无线网络与无线定位实战 ［Ｍ］． 北京： 北京航空航天大学出版社， ２００８： ２６⁃２７． ［２］毕开春．国外物联网透视［Ｍ］．北京：电子工业出版社， ２０１２： １０⁃１９． ［３］孙利民，李建中． 无线传感器网络［Ｍ］． 北京：清华大学 出版社， ２００５： ８９⁃１０８． ［４］ＡＫＹＩＬＤＩＺ Ｉ Ｆ， ＷＥＩＬＩＡＮ Ｓ， ＳＡＮＫＡＲＡＳＵＢＲＡＭＡＮＩＡＭ Ｙ． Ａ ｓｕｒｖｅｙ ｏｎ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［ Ｊ］． ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｍａｇａｚｉｎｅ， ２００２， ４０（８）： １０２⁃１１４． ［５］ＮＩ Ｌ Ｍ， ＬＩＵ Ｙ Ｈ， ＺＨＵ Ｙ Ｍ． Ｃｈｉｎａ’ ｓ ｎａｔｉｏｎａｌ ｒｅｓｅａｒｃｈ ｐｒｏｊｅｃｔ ｏｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ［ Ｊ］． ＩＥＥＥ Ｗｉｒｅｌｅｓｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， ２００７， １４（６）： ７８⁃８３． ［ ６］ ＳＵＮＩＬ Ｊ， ＰＲＡＢＨＡＴ Ｒ． Ａ ｓｕｒｖｅｙ： ｔｏｐｏｌｏｇｙ ｃｏｎｔｒｏｌ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｉｎｔｅｒ⁃ ｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ａｎｄ Ｎｅｔｗｏｒｋｉｎｇ． Ｃｈｅｎｎａｉ， Ｉｎｄｉａ， ２００８： ４２２⁃４２７． ［７］毕晓伟，郭文超，冯文江． ＷＳＮ 中能量有效分簇多跳路由 算法［Ｊ］． 电路与系统学报，２０１１，１６（２）： １３⁃１８． ＢＩ Ｘｉａｏｗｅｉ， ＧＵＯ Ｗｅｎｃｈａｏ， ＦＥＮＧ Ｗｅｎｊｉａｎｇ． Ｅｎｅｒｇｙ⁃ｅｆｆｉ⁃ ｃｉｅｎｔ ｃｌｕｓｔｅｒｉｎｇ ｍｕｌｔｉ⁃ｈｏｐ ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎ⁃ ｓｏｒ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｉｒｃｕｉｔｓ ａｎｄ Ｓｙｓｔｅｍｓ， ２０１１，１６ （２）： １３⁃１８． ［８］任东海，尚凤军，王寅． 一种基于时间延迟机制的无线传 感器网络分簇算法［ Ｊ］． 传感技术学报，２００９， ２２（ １１）： １６４５⁃１６４９． ＲＥＮ Ｄｏｎｇｈａｉ， ＳＨＡＮＧ Ｆｅｎｇｊｕｎ， ＷＡＮＧ Ｙｉｎ． Ａ ｃｌｕｓｔｅｒｉｎｇ ｈｉｅｒａｒｃｈｙ ａｒｉｔｈｍｅｔｉｃ ｂａｓｅｄ ｏｎ ｔｉｍｅ ｄｅｌａｙ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｔｒａｎｓｄｕｃｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ， ２００９， ２２ （１１）： １６４５⁃１６４９． ［９］雷磊，薛小龙，周进华，等．实现节点负载均衡的无线传感 器网络能量高效分簇方法［ Ｊ］．应用科学学报，２０１０， ２８ （３）： ５５１⁃５６０． ＬＥＩ Ｌｅｉ， ＸＵＥ Ｘｉａｏｌｏｎｇ， ＺＨＯＵ Ｊｉｎｈｕａ， ｅｔ ａｌ． Ｌｏａｄ ｂａｌａｎ⁃ ｃｉｎｇ ｅｎｅｒｇｙ ｅｆｆｉｃｉｅｎｔ ｃｌｕｓｔｅｒｉｎｇ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ａｐｐｌｉｅｄ Ｓｃｉｅｎｃｅｓ， ２０１０， ２８（３）： ５５１⁃５６０． ［１０］张荣博，曹建福．利用蚁群优化的非均匀分簇无线传感 器网络路由算法［Ｊ］．西安交通大学学报，２０１０， ４４（６）： ３３⁃３８． ＺＨＡＮＧ Ｒｏｎｇｂｏ， ＣＡＯ Ｊｉａｎｆｕ． Ｕｎｅｖｅｎ ｃｌｕｓｔｅｒｉｎｇ ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｂａｓｅｄ ｏｎ ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｘｉ ＇ ａｎ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ， ２０１０， ４４（６）： ３３⁃３８． ［１１］郭彬，李喆．无线传感器网络中基于剩余能量的联合选 举动态成簇路由算法［ Ｊ］．电子与信息学报，２００７， ２９ （１２）： ３００６⁃３０１０． ＧＵＯ Ｂｉｎ， ＬＩ Ｚｈｅ． Ｕｎｉｔｅｄ ｖｏｔｉｎｇ ｄｙｎａｍｉｃ ｃｌｕｓｔｅｒ ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｒｅｓｉｄｕａｌ⁃ｅｎｅｒｇｙ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔ⁃ ｗｏｒｋｓ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ ＆ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏ⁃ ｇｙ， ２００７， ２９（１２）： ３００６⁃３０１０． ［１２］蒋畅江，石为人．能量均衡的无线传感器网络非均匀分 簇路由协议［Ｊ］．软件学报，２０１２， ２３（５）： １２２２⁃１２３２． ＪＩＡＮＧ Ｃｈａｎｇｊｉａｎｇ， ＳＨＩ Ｗｅｉｒｅｎ． Ｅｎｅｒｇｙ⁃ｂａｌａｎｃｅｄ ｕｎｅｑｕａｌ ｃｌｕｓｔｅｒｉｎｇ ｒｏｕｔｉｎｇ ｐｒｏｔｏｃｏｌ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｓｏｆｔｗａｒｅ， ２０１２， ２３（５）： １２２２⁃１２３２． ［１３］孟中楼，王殊，赵峰，等．分簇式无线传感器网络睡眠调 度机制研究［ Ｊ］．微电子学与计算机，２００９， ２６（ ７）： ９⁃ １６． ＭＥＮＧ Ｚｈｏｎｇｌｏｕ， ＷＡＮＧ Ｓｈｕ， ＺＨＡＯ Ｆｅｎｇ， ｅｔ ａｌ． Ｒｅ⁃ ｓｅａｒｃｈ ｏｎ ｓｌｅｅｐｉｎｇ ｓｃｈｅｄｕｌｉｎｇ ｉｎ ｃｌｕｓｔｅｒｅｄ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［ Ｊ］． Ｍｉｃｒｏｅｌｅｃｔｒｏｎｉｃｓ ａｎｄ Ｃｏｍｐｕｔｅｒ， ２００９， ２６ （７）： ９⁃１６． ［１４］ ＨＥＩＮＺＥＬＭＡＮ Ｗ， ＣＨＡＮＤＲＡＫＡＳＡＮ Ａ， ＢＡＬＡＫＲＩＳＨ⁃ ＮＡＮ Ｈ． Ａｎ ａｐｐｌｉｃａｔｉｏｎ⁃ｓｐｅｃｉｆｉｃ ｐｒｏｔｏｃｏｌ ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ ｗｉｒｅｌｅｓｓ ｍｉｃｒｏ⁃ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｗｉｒｅｌｅｓｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， ２００２， １（４）： ６６０⁃６７０． ［１５］ ＹＯＵＮＩＳ Ｏ， ＦＡＨＭＹ Ｓ． Ｄｉｓｔｒｉｂｕｔｅｄ ｃｌｕｓｔｅｒｉｎｇ ｉｎ ａｄ⁃ｈｏｃ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ： ａ ｈｙｂｒｉｄ ｅｎｅｒｇｙ⁃ｅｆｆｉｃｉｅｎｔ ａｐｐｒｏａｃｈ［Ｃ］ ／ ／ Ｐｒｏｃ １３ ｔｈ Ｊｏｉｎｔ Ｃｏｎｆ ｏｎ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｍｍｕｎｉｃａ⁃ ｔｉｏｎｓ Ｓｏｃｉｅｔｉｅｓ． Ｃｈｉｃａｇｏ， ＵＳＡ， ２００４： ６２９⁃６４０． ［１６］ ＳＭＡＲＡＧＤＡＫＩＳ Ｇ， ＭＡＴＴＡ Ｉ， ＢＥＳＴＡＶＲＯＳ Ａ． ＳＥＰ： ａ ｓｔａｂｌｅ ｅｌｅｃｔｉｏｎ ｐｒｏｔｏｃｏｌ ｆｏｒ ｃｌｕｓｔｅｒｅｄ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｃ］ ／ ／ Ｐｒｏｃ ｏｆ Ｉｎｔ’ｌ Ｗｏｒｋｓｈｏｐ ｏｎ ＳＡＮＰＡ． Ｂｏｓｔｏｎ， ＵＳＡ， ２００４： １４６⁃１７３． ［１７］ＸＵ Ｙ， ＨＥＩＤＥＭＡＮＮ Ｊ， ＥＳＴＲＩＮ Ｄ． Ｇｅｏｇｒａｐｈｙ ｉｎｆｏｒｍｅｄ ｅｎｅｒｇｙ ｃｏｎｓｅｒｖａｔｉｏｎ ｆｏｒ ａｄ⁃ｈｏｃ ｒｏｕｔｉｎｇ［Ｃ］ ／ ／ Ｐｒｏｃ ７ ｔｈ Ａｎ⁃ ｎｕａｌ Ｉｎｔ ’ ｌ Ｃｏｎｆ ｏｎ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ｎｅｔｗｏｒｋｉｎｇ． Ｒｏｍｅ， Ｉｔａｌｙ， ２００１： ７０⁃８４． ［１８］ＸＩＡＮＧ Ｍ， ＳＨＩ Ｗ Ｒ， ＪＩＡＮＧ Ｃ Ｊ， ｅｔ ａｌ． Ｅｎｅｒｇｙ ｅｆｆｉｃｉｅｎｔ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍａｘｉｍｉｚｉｎｇ ｌｉｆｅｔｉｍｅ ｏｆ ｗｉｒｅｌｅｓｓ ｓｅｎ⁃ ｓｏｒ ｎｅｔｗｏｒｋｓ ［ Ｊ］． ＡＥＵ⁃Ｉｎｔ ＇ ｌ Ｊｏｕｒｎａｌ ｏｆ Ｅｌｅｃｔｒｏｎｉｃ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ， ２０１０， ６４（４）： ２８９⁃２９８． ［１９］ＷＡＮＧ Ａ， ＨＥＩＮＺＥＬＭＡＮ Ｗ， ＣＨＡＮＤＲＡＫＡＳＡＮ Ａ． Ｅｎ⁃ ｅｒｇｙ⁃ｓｃａｌａｂｌｅ ｐｒｏｔｏｃｏｌｓ ｆｏｒ ｂａｔｔｅｒｙ⁃ｏｐｅｒａｔｅｄ ｍｉｃｒｏｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ［Ｃ］ ／ ／ Ｐｒｏｃ １９９９ ＩＥＥＥ Ｗｏｒｋｓｈｏｐ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓ⁃ ｉｎｇ Ｓｙｓｔｅｍｓ． Ｔａｉｐｅｉ， Ｃｈｉｎａ， １９９９： ４８３⁃４９２． ［２０］ＤＥＮＧ Ｊ， ＨＡＮ Ｙ， ＨＥＩＮＺＥＬＭＡＮ Ｗ， ｅｔ ａｌ． Ｂａｌａｎｃｅｄ⁃ｅｎ⁃ ｅｒｇｙ ｓｌｅｅｐ ｓｃｈｅｄｕｌｉｎｇ ｓｃｈｅｍｅ ｆｏｒ ｈｉｇｈ⁃ｄｅｎｓｉｔｙ ｃｌｕｓｔｅｒ⁃ｂａｓｅｄ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ［ Ｊ］． Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， ２００５， ２８（１４）： １６３１⁃１６４２． 作者简介： 叶润，男，１９８６ 年生，硕士研究生，主 要研究方向为无线传感器网络。 王缓缓，女，１９７９ 年生，讲师， 主要研究方向为无线传感器网络。 ·６１２· 智 能 系 统 学 报 第 ９ 卷