基于扇形区域的无线传感器网络路由算法研究

鲁晓辉

（三门峡职业技术学院 信息传媒学院，河南 三门峡 472000）

基于扇形区域的无线传感器网络路由算法研究

鲁晓辉

（三门峡职业技术学院 信息传媒学院，河南 三门峡 472000）

基 于对经 典分 簇算法 LEACH 和 PEGASIS 的 研究，提出 一种 新的分 簇路 由算法 。 该算 法在 簇头 选 择机 制上 对 LEACH 算 法作 了 一定 的改 进，重点考 虑了 节 点剩余 能 量 等参数 ，有效 避 免 了低能 量 节 点 被选 为 簇 头 。 随 着 与 汇聚节点距离的增大，簇的规模也逐渐增大。同时，将网络划分为多个扇形区域，每一扇区内部节点间的数据传输采用多跳方式进行。 通过对算法验证，与 LEACH 算法、PEGASIS 算法比较，新算法对网络生存时间的延长明显。

路由算法；多跳通信；无线传感器网络；分簇

引言

无线传感器网络（Wireless Sensor Networks，简称 WSN）是采用大量传感器组成无线网络，目前被广泛应用于环境监控、医疗护理、目标跟踪等多个领域，主要功能包括采集监控区域信息，将信息进行处理并返回网络拥有者。受传感器构造与部署环境的限制，WSN 网络中各节点携带能量受到极大的限制 ，对 节 点 进 行能 量 补 充 也 存 在极 大 困 难[1]。 因 此 ，通过对协议的研究， 如何利用有限的能量资源，设计出能耗低、网络生命周期长的新路由算法，是目前传感器网络研究的主要方向。

无线传感器网络的路由协议分为平面路由协议和分层路由协议两种。由于通信损耗能量与传送的数据量和到达目标的距离的平方成正比,采用基于分层的路由算法与采用平面路由算法相比，前者具 有 更 好 的 适 应 性 和 节 能 性[2]， 在 分 层 路 由 算 法 中 ，比 较 具 有 代 表 性 的 有 LEACH 算 法[3-4]，PEGASIS 算法[5]等 。 在 LEACH 算 法 中,节 点 组 织 成 多 个 簇 ， 每 一个簇的簇头负责融合来自簇内不同成员产生的数据,并 转 发 给 汇 聚 节 点 （Sink）。 PEGASIS 算 法 针 对LEACH 算法进行了改进， 为节约能量每个节点仅与其相邻节点进行信息传递，对汇聚节点的信息传递仅由链首节点完成。 通过比较可知 LEACH 算法的分簇能够降低网络的延迟并提升效率，PEGASIS算法采用的多跳数据路由，主要的优势在于均衡不同节点的能量消耗，在传输的同时融合数据，减少传输的数据量。

笔者 将 LEACH 算法和 PEGASIS 算 法 的 优点有机结合在一起，提出了一种新的分簇路由算法。新算法的主要优点包括：（1） 减少网络开销；（2）平衡不同节点的能量消耗；（3）有效延长网络存在时间。

1 LEACH 算法和 PEGASIS 算法

1.1 LEACH 算法

LEACH 算法是目前应用较广泛的低功耗自适应算法。算法的核心是簇头节点的确定是随机选择的结果，随着每周期簇头节点的变化，将网络能量负载进行分配，最终达到降低能量消耗延长网络生命周期的目的。

LEACH 将每次簇头选择视为一轮， 在一轮开始的时候， 所有节点均随机 生成一个介于 0-1 的数，最终得到的数比阈值 T（n）小的，即为簇头。

其中，p 为预设的簇头百分比，r为当前的轮数，G 是最近 1／p 轮没有成为簇头的节点集合。 簇头的选择基本上可以确保每个节点成为簇头的概率相当，当簇头确定后，其余节点根据距离选择加入最近的簇头，并通过簇头传递信息。

1.2 PEGASIS 算法

PEGASIS 算法的核心思想 是利用贪婪算 法 生成一条由所有节点组成的单链，节点仅与相邻节点传递消息，每个节点完成两个工作：第一，接收上一节点的信息；第二，将信息与自身数据融合，将融合后的信息发送到下一节点，直至到达簇头，最终由簇头将信息传递给汇聚节点，采用此算法各节点的负载较为均衡。

2 新算法的提出

本文结合两个算法的优点，提出改进算法，新算法通过构建大小不同的簇来均衡网络中节点的能量消耗，即靠近汇聚节点的簇半径相对较小，随着与汇聚节点距离的增加，簇半径也相应增加。这样，距汇聚点近的簇头能够保留更多的能量用于簇间的数据的转发[5]。 由于 PEGASIS 在选择最近的节点时会自动排除已经在链路中出现过的节点，这样必将导致中继节点的距离变大，所以相邻节点间的长链就不可避免，最终导致能量消耗增大，为了避免这种情况，本文算法将目标区域划分为多个扇形区域，簇头节点只与本区域内的其他簇头节点形成多跳路由，这样可以有效降低节点间链路的长度，减少能量消耗。

2.1 新算法描述

在改进的新算法中，以基站为顶点，将目标区域划分成 n 个扇形区域， 扇形区域的编号从 1-n，每个区域内节点的 ID 和所属的扇形区域的编号有关，例如：在扇形区域 1 内的所有节点编号均为 n1,扇形区域 2 内的所有节点编号均为 n2， 依次类推，第 n 个扇形区域的节点编号为 nn, 用一张 TABLE表来记录节点的 ID 信息。

（1）簇头选择的准备工作：

本算法的簇头选择机制在 LEACH 算法簇头选择机制的基础上增加节点剩余能量的判定，主要目的在于避免低能节点被选为簇头。首先需要计 算 阈 值 T(n)[4],若 节 点 的 随 机 生 成 数 大 于 T （n）则直接淘汰，其余节点被确定为候选簇头，等待进行继续筛选。

其 中 ，Ecurrent 代 表 节 点 剩 余 能 量 ；Eaverage代表节点平均剩余能量， 其余参数与 LEACH 算法相同。

（2）簇头的确定与簇的形成

候选簇头确定后，将通过竞争机制确定该轮的簇头,首先，确定候选簇头到汇聚节点的近似距离。具体做法是由汇聚节点通过给定功率发送广播信号 ， 各 候 选 簇 头 根 据 接 收 信 号 的 强 度 估 算 出 距 离[5]，计为 dsi。

第二，将近似距离带入公式（3）计算每个候选节点的簇半径 Ri。

其 中 ，dmax与 dmin分 别 代 表 候 选 簇 头 距 离 汇 聚 节点的最远与最近距离,R0为预设的最大簇半径,C 为控制参数。

以此公式计算得到的簇半径将以汇聚点为圆心向外逐渐扩大，最终结果是在汇聚点附近形成范围较小包含节点较少的小型簇，而在聚会据点较远区域形成范围较大包含节点数目较多的大型簇。这样距离汇聚点越近，簇头能够保留越多的能量用于簇间的数据转发，从而可以延长网络的寿命。

第三，确定簇半径后，各候选簇头向自身半径Ri范围发送竞争申请，申请应包含自身能量剩余信息。 如区域能仍有其余候选节点，则能量剩余较多的成为簇头，如区域内无其他候选节点，则直接成为簇头，并广播簇头确认信息。 簇头确定后，其余节点按照最近原则加入最近的簇。最终形成如图1所示的结构。

图1 簇结构图

（3）簇内通信与簇间通信

簇内所有节点收集与处理的信息直接通过簇头向外发送，簇内通信由簇头为每个成员节点分配通信时隙，并存储在 TDMA 时隙表 中，以确保簇内通信的稳定性。

簇间通信以多跳的形式进行，簇头节点将收集到的成员节点信息进行融合后，发送给其上行簇头节点。上行簇头节点确认需要满足三个条件。

第一，上行节点与下行节点均为簇头节点且必须在同一区域，即在 TABLE 表中表明，两个节点在同一扇区，具有相同的 ID 头。

第二，上行节点到汇聚源的距离要小于下行节点 ， 即 上 行 节 点 Sj与 下 行 节 点 Si需 满 足 公 式（4）。

dsj＞dsi（4）

第 三 ，对 于 节 点 Si,在 相 同 扇 区 内 ，满 足 公 式 （4）的所有簇头节点中，Sj距离其最近。

每个簇头均拥有且只有一个上行节点，形成节点链，链条的最终指向汇聚节点。 每个节点直接将数据传递到其上行节点，最终汇聚节点得到各节点的融合数据，并进行处理。

3 新算法的仿真与验证

对于新算法性能指标的评价， 采用与 LEACH算法、PEGASIS 算法对比的形式进行， 各项环境配置如下表所示， 利用 Matlab 仿真工具进行仿真实验,仿真结果如下。

仿真参数表

图 2 显示了 LEACH 算法，PEGASIS 算法 和 本文改进的新算法（图中用本文算法代表）出现第一个死亡节点时的通信轮数。图3是在不同的通信轮数下，三种算法存活节点个数的仿真结果。 对结果进行分析， 对比算法的首节点死亡时间分别在 264轮和 447 轮左右， 节点 100%死亡时的轮数分别在625 和 700 附近。 本文的算法出现第一个死亡节点在 522 轮左右，节点全部死亡在 714 轮左右。 本文算 法 的 通 信 轮 数 明 显 高 于 LEACH， 稍 高 于PEGASIS。 综合以上仿真结果，新算法在生存时间的提升上有较大改善。

图2 网络中第一个节点死亡的通信轮数

图3 节点存活数目图

4 结束语

提出了一种新的分簇路由算法，新算法以基站为顶点，将目标区域划分成多个扇形区域。采用不等簇结构来成簇，簇的覆大小随着距离基站的远近不同而改变，簇内节点将自身信息发送给簇头节点，在簇头节点进行融合处理。簇头节点与本扇形区域内的其他簇头节点形成多跳通信路径将数据传给汇聚节点，这样能够有效避免信息传递中长链的形成，降低能量消耗，减少传输延迟。本文是在网络数据传输可以进行数据融合的基础上，设计了一种有效的路由算法来降低能耗，优化网络生存时间，但对于簇头节点进行数据处理的具体方法并没有涉及，下一步工作重点是进一步提升簇头节点数据融合的效率。

[1]李 建 中 ，李 金 宝 ， 石 胜 飞.传 感 器 网 络 及 其 数 据 管 理 的 概念 、 问 题 与 进 展[J].软 件 学 报 ，2003,14（10）：1717-1727.

[2]张 源 .一 种 基 于 LEACH 协 议 的 节 能 型 分 簇 路 由 算 法[J].计算机与现代化，2009（12）：133-136.

[3]解 荧 ， 韩 阳 龙 ， 赵 刚 等.伪 三 维 的 地 理 位 置 无 线 传 感 器 网 络路 由 算 法[J].计 算 机 工 程 与 应 用 ，2013（22） ：63-67.

[4]HeinzelmanW R,Chandrakasan A P,Balakrishnan H. Anapp lication-specific protocol architecture for wireless microsensor networks [J].IEEE Transactions on W irelessCommunications(S1536-1276),2002,1(4):660-670.

[5]米奕萍,高媛.基于蚁群优化的 WSN 能耗均衡链状路由协议[J].计 算 机 测 量 与 控 制.2012，20（02）：490-493.

（责任编辑 梁红艳）

TP393

：B

：1671-9123（2014）03-0114-03

2014-05-10

鲁晓辉（1980-），男，河南三门峡人，三门峡职业技术学院信息传媒学院讲师。