第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,则可得出：自适应分簇算法，它周期动态地形成簇。 ＨＥＥＤ ［ １５ ］ 算法是对 ＬＥＡＣＨ 算法随机生成不均匀簇头的一种 优化。 ＳＥＰ ［ １６ ］算法是对 ＬＥＡＣＨ 算法竞选簇头的一 种改进，文献［１７］中提出的 ＧＡＦ 算法是一种基于地 理位置的分簇算法。 文献［７，１８］ 采用了固定分区 的方法进行区域分簇。 能量均衡多跳分簇路由算法（ＥＢＭＨＣ）的基本 思想为：虚拟单元格划分为集中式划分，生存簇头阶 段为分布式方式，同时采用动态路由方式和轮转的 方式实现数据的多跳传输和能量均衡。 通过仿真结 果表明，ＥＢＭＨＣ 算法均衡了网络节点能量，且没有 影响网络数据传输，延长了网络生存寿命。 １ 能量均衡多跳分簇路由算法 在簇结构中，簇首不仅要收集簇内节点采集的 数据，而且还负责数据融合、转发，路由生成与维护。 簇头的这些功能决定了其必须处于高负荷工作状 态，这就使得网络能量分布不平衡。 ＬＥＡＣＨ 算法在一定程度上实现了网络能量均 衡的目的，但随机簇头生成方式存在簇头分布不均 匀的问题。 ＨＥＥＤ 算法是对 ＬＥＡＣＨ 算法的改进，其 考虑了簇内的通信开销，使得全网能量更均衡，但在 生产簇头方式上采取迭代算法，这就加大了成簇的 开销。 ＧＡＦ 算法的思想是根据地理信息将网络划 分为网格，网络节点能量均衡性差。 ＳＥＰ 算法在 ＬＥＡＣＨ 算法的基础上， 对不同剩余能量的节点采 用不同的选举概率，但簇头分布不均匀的问题并没 有得到改进。 本文提出一种 ＺｉｇＢｅｅ 无线传感器网络能量均 衡多跳分簇路由算法（ＥＢＭＨＣ），ＥＢＭＨＣ 算法在分 簇阶段引入随机轮转 θ 角，避免某个扇区内节点数 量过多，在竞争簇头阶段，引入能量因子，使剩余能 量较多的节点优先成为簇头；簇路由阶段，采取数据 融合方式，簇头节点将同类数据进行融合处理，从而 实现无线传感器网络能耗均衡。 １．１ 网络模型假设 对 ＺｉｇＢｅｅ 无线传感器网络模型作出如下假设： １）ＺｉｇＢｅｅ 无线传感器网络中每个节点最初能 量相等，且传感器节点具有相同的硬件平台； ２）传感器节点相对于基站的极坐标且放置后 位置不变； ３）基站位于中心，不考虑基站的能耗，传感器 节点随机放置在圆形区域中。 １．２ 算法描述 ＥＢＭＨＣ 算法执行过程分为每个周期 ３ 个阶段： 分簇阶段、簇头竞争阶段和簇路由阶段。 如图 １ 所 示。 分簇阶段类似于 ＧＡＦ 算法里对虚拟单元格的 划分，如图 ２ 所示。 图 １ ＥＢＭＨＲ 算法执行过程 Ｆｉｇ．１ ＥＢＭＨＲ ａｌｇｏｒｉｔｈｍ ｅｘｅｃｕｔｉｏｎ ｐｒｏｃｅｓｓ 图 ２ ＥＢＭＨＲ 算法分簇示意 Ｆｉｇ．２ ＥＢＭＨＲ ａｌｇｏｒｉｔｈｍ ｃｌｕｓｔｅｒｉｎｇ ｄｉａｇｒａｍ ＥＢＭＨＲ 的分簇思想以基站为中心的圆形区域 建立极坐标系，然后进行环形分层，最后将每层的环 等分。 论文根据以上思想，且考虑算法的复杂度，确 定第一层环四等分，第 ２ 和第 ３ 层环分布 ８ 等分，第 ４、５ 层环 １６ 等分，５ 层以外每增加 ２ 层环，等分数是 新增较小环数的 ４ 倍。 论文中传感器节点随机布 置，为了生成的簇头节点功耗相当，划分的每个簇面 积应接近。 设 ｒ０ ＝ ０，基站到第一层环距离设为 ｒ１ ，则通过 式（１）可计算基站到第 ｎ 层环的距离 ｒｎ 。 １ ４ πｒ１ ２ ＝ １ ４ｎ π（ｒｎ ２ － ｒｎ－１ ２ ） （ｎ ＝ ２，４，６，…） １ ４ πｒ１ ２ ＝ １ ４（ｎ － １） π（ｒｎ ２ － ｒｎ－１ ２ ） ì î í ï ï ï ï ï ï （ｎ ＝ ３，５，７，…） （１） 由式（１）可得出每层到基站的距离： ｒｎ ＝ ｎｒ１ ２ ＋ ｒｎ－１ ２ （ｎ ＝ ２，４，６，…） ｒｎ ＝ （ｎ － １）ｒ１ ２ ＋ ｒｎ－１ ２ （ｎ ＝ ３，５，７，…） { （２） 记每层的距离宽度为 Ｌｎ，显然 Ｌ１ ＝ ｒ１，则可得出： 第 ５ 期 叶润，等：能量均衡多跳分簇路由算法 ·６０９·