基于能量均衡的WSNs固定分区路由算法.pdf

2 0 1 4年 第3 3卷 第 1 1 期 传感器与微系统 T r a n s d u ce r a n d Mi cr o s y s t e m T e ch n o l o g ie s 1 2 1 DOI 1 0 1 3 8 7 3 J 1 0 0 0 9 7 8 7 2 0 1 4 1 1 0 1 2 1 0 4 基 于能量 均衡 的 WS Ns固定分 区路 由算法 李秋 峦 詹 国华 李志华 杭州师范大学 信 息科学与3 程学院 浙江 杭 州 3 1 1 1 2 1 摘要 针对 L E A C H协议簇间通信能耗和控制开销过大 以及簇首数量波动大 簇首分布不均匀等问题 提出一种基于能量均衡的固定分区路由算法 结合多跳算法进行非均匀分簇 在降低簇间通信能耗的同 时避免了 热区 问题 采用固定分区策略 限制了簇首节点出现的范围与数量 引入簇首能量 自检机 制 降低了网络的控制开销 同时利用节点能量和位置信息 选取最优节点成为簇首 仿真实验结果表 明 该算法在网络的总体能耗 负载均衡和生命周期方面都有较好的表现 关键词 无线传感器网络 能量均衡 固定分区 L E A C H 中图分类号 T P 3 9 3 文献标识码 A 文章编 号 1 0 0 0 9 7 8 7 2 0 1 4 1 1 01 2 1 04 Fix e d pa r t it io n r o u t in g a lg o r it h m f o r W S Ns b a s e d 0 n e n e r g y b a la n ce L I Q iu lu a n Z H A N G u o h u a L I Z h i h u a C o ll e g e o f I n f o r ma t io n S ci e n ce a n d E n g in e e r in g Ha n g z h o u N o r ma l Un iv e r s i t y Ha n g z h o u 3 1 1 1 2 1 C h in a Ab s t r a ct I n v ie w o f t h e d e fi cie n cy s u ch a s h u g e e n e r g y c o n s u mp t io n f o r in t r a clu s t e r co mmu n ica t io n t o o mu ch co n t r o llin g e x pe ns e s a s we ll a s v o la t ile a mo u n t a n d u n bMa n ce d d is t r ib u t io n o f clu s t e r h e a d s o f L EACH pr o t o co l a fi x e d pa it io n r o u t in g a lg o ri t hm ba s e d o n e n e r gy b a la n ce is p r o po s e d Co mbine d wit h mu hi h o p a lg o ri t h m t o ca r r y o u t u ne v e n clus t e ri n g s t r a t e gy in t r a clu s t e r co mmu nica t io n e n e r gy co n s u mpt io n is e f f e ct ive ly r e du ce d wit ho ut t h e pr o ble m o f t h e r ma l r e g io n By e mplo y ing t h e ide a o f fi x e d pa r t it io n r a ng e a nd a mo un t o f clus t e r h e a ds n o d e a r e s ig n ifi ca n t ly r e s t r ict e d I n a d d it io n s e lf e x a min a t io n me ch a n is m o f clu s t e r h e a d s e n e r g y is p r o p o s e d t o r e d u ce co n t r o llin g e x pe n s e s Me a n wh ile e ne r g y a n d g e o g r a p hic lo ca t io ns in f o r ma t io n o f no d e a r e f u lly t a ke n in t o a cco un t in ch o o s in g o p t ima l no d e t o b e co me clus t e r h e a d s S imu la t io n r e s ult s d e mo ns t r a t e t ha t t his a lg o r it hm ha s o u t s t a n d in g p e r f o rm a n ce s in o v e r a ll e n e r gy co n s u mp t io n lo a d b a la n ce a n d lif e t ime o f n e t w o r k Ke y w o r d s w ir e le s s s e n s o r n e t w o r k s WS N s e n e r gy b a l a n ce fix e d p a r t i t i o n L E A C H 0 引 言 随着无线传感器网络 w i r e le s s s e n s o r n e t w o r k s WS N s 被越发广泛地应用到军事 环境监测 医疗救护等领域 作 为其关键技术之一的路由算法也开始成为人们关注 的焦 点 WS N s 能量有限 故低能耗与负载均衡是其路由算法 设计的首要 目标 分簇路由可以提高能量利用率 均衡 网络负载 是一种有效的 WS N s拓扑管理方式 其主要 思想是选择部分节点作为簇首 簇 内成员将数据发送给簇 首 簇首将数据融合后发送给信宿 H e i n z e l ma n W等人提 出的 L E A C H 协 议 1 o w e n e r gy a d a p t iv e cl u s t e r in g h i e r a r ch y 是早期的一种专为 WS N s 设计的经典协议 其中定义 了 轮 r o u n d 的概念 并创建了时分多址时刻表以记录 收稿 日期 2 0 1 4 0 3 1 2 基金项 目 国家 自然科学基金资助项 目 6 1 0 0 1 1 7 0 成员节点的数据传输时隙 继承 L E A C H协议分簇思想的改进协议有很多 D E E C d i s t r i b u t e d e n e r gy e ffi ci e n t clu s t e rin g 算法对簇间通信算法 进行了优化 但未解决簇首数量波动大和分布不均匀的问 题 邓仲芬等人 提出 的 E U C R e n e r gy e ffi ci e n t u n i f o rm t r e e cl u s t e r in g r o u t in g 协议 均匀了簇首 分布 但未 考虑 网络 的控制开销 J 李成法等人提出的 E E U C e n e r gy e ffi cie n t u n e v e n cl u s t e r 算法基于地理位置对网络进行规模不等的 分簇 J 平衡了不同位置节点的能耗 但没有对相关参数 进行优化取值 本文在 L E A C H算法的基础上 提出一种基于能量均 衡的固定 分 区路 由算法 fix e d p a r t it io n r o u t in g a l g o rit h m b a s e d o n e n e r gyb a la n ce F R A E B 通过计算最优簇半径进 1 2 2 传 感 器 与 微 系 统 第 3 3卷 行非均匀分簇以避免 热区 问题 采用 固定分区策略 限制簇首的范围与数量 引入簇首能量自检机制 避免过大 的控制开销 同时充分利用节点剩余能量和位置信息 选取 最优节点成为簇首 1 F R A E B流程 本算法包括模型假设 网络划分 分区成簇 簇首轮换 数据传输五部分 算法流程如图1所示 l 苎 壁 兰 塞 坌 堕 l 臣鲴 匹 一 磊 一 l 图 1 F RAEB流 程 图 Fig 1 Fl ow ch a r t o f FRAEB 在本算法中 首先对网络结构作出假设 确定网络能耗 模型 然后计算最优簇半径以解决 热区 问题 同时采用 固定分区策略 限制簇首的范围与数量 在簇首轮换阶段引 入簇首能量自检机制 并将节点能量与位置对簇首选举的 影 响进 行量化 得 到簇首 竞争力 计算 公式 下 面将对 各部 分 逐一 详述 2 模型假设 2 1 网络 模 型 本文对 WS N s 结构作如下假设 1 信宿节点计算与存储能力较强 能量不受限 2 所有传感器节点结构相同 具有一定的计算和存储 能力 能量受限且初始能量相同 可以感知 自身能量和位置 信息 发射功率可调 3 不考虑环境因素对网络拓扑结构的影响 2 2能耗 模 型 本 文采 用常见的一阶能耗 模型 如 图 2所示 一 了 图 2一阶能耗模 型 F ig 2 The fi r s t o r d e r e n e r g y c o n s u m p t io n m o d e l 该模型的通信能耗计算公式如下所示 r 后 E l s d a k d 1 k E l s d 4 d d E k E I k 2 其中 E k d 为向距离 d m的节点发送 k b it 数据的 能耗 E k 为节点接收 k b i t 数据的能耗 E 为节点发送 电路和接收电路处理单位数据的能耗 分别为 自由 空间模型和多径衰落模型中放大单位数据并传输单位距离 所需的能量 可统一用E 表示 d 为距离门限值 若传 输距离 d比距离门限值小 则采用 自由空间模型 放大能量 消耗与 d 呈正比 否则 采用多径衰落模型 能耗与 呈正 比 此外 融合单位数据的能耗为 E 3网络划 分 在 F R A E B中 首先计 算最 优簇 半径 对 网络 进行 非均 匀划分 为之后的分区成簇做准备 当所有节点都部 署完 毕后 信宿 向监测 区域 广播 消息 收集节点位置信息 并由此创建和维护一个传感器节点信 息表 记录节点标识 位置信息及活跃状态 之后信宿计算 出监测区域面积 并据此将其分为 层 离信宿最近的为第 层 最远的为第 1层 F R A E B网络结构图如图3所示 圈 3 FRAEB 嘲 络 结构 Fig 3 Ne t wo r k s t r u c t ur e o f FRAEB 计算簇半径是为 了平衡不 同簇层 能耗 所 以 簇 半径 的 计算应从能量消耗角度出发 根据通信能耗计算公式和 E 可计算 出各层簇在一轮数据收集过程中消耗 的能量 E i 本文假设簇首将各成员上传 的 k b it 数据融合成 k b i t 的数据包转发给中继簇首 而中继簇首只负责转发此数 据包 如图 3所示 若已知各层簇半径 则可得各层簇个数 N i f 等 一 1 ri 其 中 M 为监测区域边长 并 由此 得各层 的成 员节点个 数 i N o c s 4 式 中 为网络节 点总数 各 层簇 的能 耗来 自 4个方 面 成员节点发送数据的能耗 E i 簇首接收并融合簇内 数据的能耗 E i 簇首接收上级簇首的能耗 E i 和 簇首将数据转发给内层簇首的能耗 E i 由通信能耗 筒 萄 萄 一 第 ll 期 李秋峦 等 基于能量均衡的 WS N s固定分区路由算法 1 2 3 公式得 E 一凹 i E 一曲 i E l s E d 删 叫 i 5 式中E 为成员节点到簇首距离平方 的期望值 文 献 8 已求出其值为 2 k 又结合式 3 式 4 可得 伽 i 计算公式 E C H k E 山 6 同样 根据通信能耗公式 得到 E 腿 i 算式 E D i Ji E l i E 如 明 i N i 7 簇首接收外层数据能耗 E i 算式 5 i k E l N i 1 2 8 式中i 1时 E i O E i 的算式如下 E i r E l q C n t r r 1 N i i 1 1 1 lk E N L 一1 i 9 式中h为最内层簇首到信宿 的距离 文中令两层簇首间 的距离约等于两层半径之和 最 内层簇首到信宿距离约等 于 与 之和 至此可求出各簇层总能耗 E o d i 其值涉 及的变量只有各层簇半径 当各层总能耗相等时 各层 簇半径为最佳簇半径 故可根据各层总能耗之间的关系 以 及各层半径之和与网络边长 的关系列出方程组 鹰 i 1 1 I 1 n L 0 l a l i E i 1 l L 1 解此方程组即可求得各层最佳簇半径 4 分区成簇 F R A E B采用固定分区策略 其分区成簇的具体过程分 为初始簇首选举和簇的建立 2个步骤 4 1 簇首选举 计算出各层簇半径后 信宿将监测区域进行分层 并将 各层划分成大小相等的区块 允许每层有个别 区块大小不 同 由于各节点初始能量相同 信宿在各分区选择离中心 最近的节点做为初始簇首 4 2 簇的建立 信宿选出簇首后 为各节点选择一个最近的簇首加入 并创建一个簇信息表 包含簇标识 簇首信息和成员信息 其中簇首信息包含 自身标识 位置及能量 而成员信息还包 含 自身数据传输时隙 之后信宿将簇信息广播到监测区域 传感器节点查询 自身所属簇并判断是否为簇首 若是 则需要创建并维护一 个成员节点信息表和一个数据传输超时定时器 否则 只需 要记录对应的簇首 之后簇首和使用第一时隙的成员节点 切换到正常通信状态 其他成员节点切换到休眠状态 5 簇 首轮换 不同于周期性簇首选举 F R A E B中仅当簇首的剩余能 量低于阈值 E 时重新进行簇首选举 该过程充分考虑了节 点的能量与位置 具体机制如下 当前簇首感知 自身能量信息 若低于阈值 E 则判定 自身失效 并选取剩余能量大于 E 的节点作为候选簇首集 合 若集合为空 则调整 E 并重复上述步骤 E 调整机制 由公式 1 1 表 示 f C 0 E0 i O E i 1 1 C E i 1 i 1 2 式中E i 为第 i次阈值调整后的能量阈值 E 0 为能 量阈值的初始值 为节点初始能量 c 为迭代因子 当 前簇首计算出活跃节点的中心位置 并选取距离中心位置 较近且剩余能量较多的节点为新簇首 将节点位置和能量 2个因素对簇首选举 的影响进行量化 得到簇首竞争力计 算公式 f k 尸 i c E n i E n 1 2 式中P i 为候选簇首 i的竞争力量化值 d 为候选簇首 与簇中心的最远距离 d 为候选簇首 i与簇 中心 的距离 E i 为候选簇首 i的剩余能量 E 和 E 代表其中的最 大值与最小值 cl c 分别为候选簇首的位置和能量在簇首 竞争力计算公式中的权重 要求 c c 的取值范围都为 0 1 且求和为 1 在选举结束后 若当前簇首当选 则该簇开始工作 否 则 当前簇首广播新簇首消息 并与新簇首完成角色交换 之后该簇开始工作 6 数据传输 6 1 簇 内通信 在簇内通信阶段 F R A E B除 了采用 L E A C H协议 的休 眠机制外 还令成员节点根据与簇首的距离来降低发射功 率 成员节点将能量信息加在发送数据中 使簇首更新成员 节点信息 引入数据传输超时定时器 供簇首判定成员节点 是否死亡 6 2簇 间通信 F R A E B在簇间通信阶段采用了多跳思想 并结合自身 特点加以改善 分簇阶段 节点根据所属簇标识计算下一跳 簇层 簇首轮换阶段 新簇首调整发射功率以覆盖将 自身作 为下一跳簇首的所有簇 这些簇的簇首收到新簇首消息后 1 2 4 传 感 器 与 微 系 统 第 3 3卷 查看新簇首所属簇是否属于下一跳簇集合 若是 则更改该 集合相应项 并重新计算最短距离 选择下一跳簇首 7 算法仿真 本文 采 用 Ma t l a b对 F R A E B 算 法 进 行 仿 真 并 与 L E A C H和 D E E C做 比较 5 0 0个 节点 均匀 部署 在 2 5 0 m x 2 5 0 m的正方形区域内 信宿节点坐标为 1 2 5 3 0 0 m 控 制包 长度 和 D A T A包 长度 分别 为 2 5 b y t e s 和 5 0 0 b y t e s 网 络环境仿真参数如表 1所示 表 1 仿真环境参数表 Ta b 1 Pa r a me t e r s o f s imu la t io n e n v ir o n m e n t 参 数 取 值 参 数 取 值 E k c n J b it 5 O Ed 8 n J b it 5 p J b i t m 1 0 E o J 0 5 O mp p J b it m 0 0 0 1 3 3 d m 8 7 C O 1 2 0 5 首先分析网络的整体能耗 3种协议下的网络整体能 耗曲线如图 4所示 耀 遐 轮数 图 4 各协议的 网络整体能量消耗 F ig 4 Ne t wo r k o v e r a ll e n e r g y co ns u mp t io n of v a r io us p r o t o co ls 从图中可见 使用 F R A E B的网络其能耗曲线位于最下 方 即经历相同轮数 的情况下能耗最小 接下来分析簇首 能耗方差 以判断簇首能耗是否均衡 取簇首节点能耗的 最大值和最小值 按照方差公式进行计算 连续随机抽取 l0轮样本 得出3种协议的簇首能耗方差曲线如图5所示 3 5 3 0 宝 2 5 j 1 j 2 0 盏 0 5 0 抽 样 次 数 图 5各协议 的簇首能耗方差 Fig 5 En e r g y c o n s u m p t io n v a r ia nce o f clu s t e r he a d o f v a r io u s pr o t o c o ls 图5显示了使用 F R A E B的网络中簇首能耗方差最小 且没有明显的波动 表 明该 算法 可 以较 好地 均衡 网络 中不 同区域的能量消耗 节点能耗均衡是延长 网络生命周期 最 主要的因素 各协议生命周期曲线如图6所示 图6表明 相比使用其他两种的网络 使用 F R AE B的网 络所经历的轮数最多 表明其生命周期最长 很大程度上 5 0 0 450 藿 招 2 5 0 2 00 藻 1 5 0 1 00 5O 0 3 00 4 00 5 00 6 00 7 00 8 00 9 00 1 U UU 轮数 图6各协议的网络生命周期 Fig 6 Ne t wo r k lif e ti me s o f v a r io u s p r o t o co ls 这得益于 F R A E B基于能耗均衡而设计的特点 8 结束语 本文在详细分析以往分簇路由协议的基础上 创新地 将固定分区思想与非均匀分簇思想进行融合 并结合 以往 协议的优点 提出了一种 F R A E B 仿真结果表明 F R A E B 有效降低了网络总体能耗 同时均衡了网络节点负载 使网 络生命周期得到了较好的延长 参考文献 1 O l u t a y o B Ha n h L Au d r e y M A s u r v e y o n cl u s t e rin g a l g o r i t h m f o r w i r e l e s s s e n s o r n e t w o r k s C P r o ce e d i n g s o f t h e 1 3 t h I n t e r n a t io n a l C o n f e r e n ce o n Ne t wo r k b a s e d I n f o r ma t io n S y s t e m I EEE Co mp u t e r S o cie t y 2 0 1 0 3 5 8 3 6 4 2 李 洪兵 熊庆宇 石为人 无线传感 器网络非均匀 等级分簇 拓 扑结构研究 J 计算机科学 2 0 1 3 4 0 2 4 9 5 2 7 7 3 H e i n z e l ma n W C h a n d r a k a s a n A B al a k r i s h m a n H E n e r g y e f f i ci e n t co m m u n ica t io n p r o t o co l fo r w i r e l e s s s e n s o r n e t w o r k s C P r o c e e d in g s o f Ha wa ii I n t e r n a t io n a l Co n f e r