基于区域划分的分层链树路由方法

摘要

本发明涉及一种基于区域划分的分层链树路由方法，包括：步骤1，将无线传器感网络划分为多个区域；步骤2，使每个所述区域单独成簇，并按照PEGASIS协议将所述簇内的节点通过遗传算法在相应的每个所述区域内形成第一链路；步骤3，按照能量最大化原则，在每个所述簇内选取簇头；步骤4，按照PEGASIS协议将所述簇头与Sink节点之间的通信链路通过遗传算法形成第二链路；步骤5，将所述第二链路改造成以Sink节点为中心的分层链树；步骤6，使节点数据沿着所述分层链树并通过数据融合传递给Sink节点，经过预定的通信时间后，跳转执行步骤1。本发明有效降低了LEACH算法中节点之间采用单跳方式导致的长距离通信所产生的能耗。

说明书

技术领域

本发明涉及无线路由技术领域，特别是涉及一种基于区域划分的分层链树路 由方法。

背景技术

无线传感器网络是一种特殊的无线通信，它是有许多节点通过无线自组织网 络的方式构成的，由于传感器节点的电源能量、计算能力和通信能力非常有限， 所以必须有一个好的路由协议以尽量延长网络的生存时间和网络性能。

LEACH协议是一种层次路由算法。普通节点为了避免距离过长而选择通过 簇头作为转接来就行通信，有效的减少了普通节点的能量消耗大大提高了网络的 稳定时间，延长了传感器网络的生存时间。但是LEACH协议存在着以下缺点， 具体如下：

LEACH的簇头选举是采用随机选举的方式，簇头的分布不均匀，导致部分 区域的节点与簇头的通信距离很大，增加了部分节点的通信耗能。

簇头采用单跳的方式直接和基站通信，不论两者之间的距离远近，当网络 规模很大的时候，通信的范围也很广，从而导致簇头消耗过多的能量导致节点过 早死亡。

簇内节点和簇头的通信也是采用单跳的方式通信，当网络规模很大的时候， 增加了簇头的能量负担同时也增加了节点的通信能耗。

发明内容

本发明的目的是提供一种基于区域划分的分层链树路由方法，以解决现有技 术中LEACH算法中节点之间采用单跳方式导致的长距离通信能耗高的问题。

为解决上述技术问题，作为本发明的一个方面，提供了一种基于区域划分的 分层链树路由方法，其特征在于，包括：步骤1，将无线传器感网络划分为多个 区域；步骤2，使每个所述区域单独成簇，并按照PEGASIS协议将所述簇内的 节点通过遗传算法在相应的每个所述区域内形成第一链路；步骤3，按照能量最 大化原则，在每个所述簇内选取簇头；步骤4，按照PEGASIS协议将所述簇头 与Sink节点之间的通信链路通过遗传算法形成第二链路；步骤5，将所述第二链 路改造成以Sink节点为中心的分层链树；步骤6，使节点数据沿着所述分层链树 并通过数据融合传递给Sink节点，经过预定的通信时间后，跳转执行步骤1。

进一步地，所述步骤1中的所述无线传感器网络为正方形，所述正方形的无 线传器感网络划分为16个所述区域。

进一步地，所述正方形的无线传器感网络划分为16个所述区域包括：将所 述正方形沿其对角线和中位线划分为八个区域；在所述正方形内划出一个同心的 内部正方形；所述内部正方形将所述八个区域划分为16个区域。

进一步地，所述步骤1还包括：通过调节所述内部正方形的边长改变簇头的 负载平衡因子。

进一步地，所述负载平衡因子LBF根据下式计算：

$\left[\mathrm{LBF}\right]=\frac{[\mathrm{head}\_\mathrm{num}]}{\underset{i=1}{\overset{\mathrm{head}\_\mathrm{num}}{\Sigma }}{(x_i-u)}^2}$

其中，head_num为簇头的个数，x_i为第i个簇包含的节点个数，u为本轮 簇平均包含的节点个数。

进一步地，在所述步骤2中，只有当所述第一链路内的任何一个节点死亡 后才重新构造新的第一链路。

进一步地，在所述步骤2或5中的所述遗传算法的适应度函数fit为：

fit＝(1-(len-minlen)/(maxlen-minlen+0.001)))²

其中，len代表按当前序列形成链路的总长度，minlen代表这一代种群所有 链路的长度最短的链路长度，maxlen代表这一代种群所有链路中长度最长的链 路的长度。

进一步地，在所述步骤5中，在所述第二链路上，按照所述第二链路的顺序 依次对簇头与簇头之间、以及簇头与Sink节点之间这两种通信方式的能耗进行 分析，如果簇头与上级簇头通信的能耗小于簇头直接与Sink节点的通信的耗能， 则该簇头维持原始通信路由；反之，则该簇头与Sink直接通信，从而降低消耗 能量。

由于本发明在各区域中选取能量最大的节点当选簇头，避免了LEACH协议 中由于随机选择簇头而导致整个网络的能量不均衡。进一步地，通过建立簇内节 点和簇头，簇头和Sink的多跳通信链路的方式，有效降低了LEACH算法中节 点之间采用单跳方式导致的长距离通信所产生的能耗。

附图说明

图1是网络区域划分图；

图2是各簇成链拓扑图；

图3是簇头成链拓扑图；

图4是簇头成链改造后的拓扑图；

图5是网络的生命周期对比；

图6是网络节点剩余能量；

图7是簇头个数对比图。

具体实施方式

以下对本发明的实施例进行详细说明，但是本发明可以由权利要求限定和覆 盖的多种不同方式实施。

基于背景技术中的描述，为了改善LEACH算法存在的上述不足，本发明提 出了基于区域划分的分层链树的路由方法。

本发明把无线传感器网络分成若干区域，在各个区域中通过遗传算法形成一 条最优的第一链路，并按照剩余能量最大的原则在链路上选取簇头，并在簇头和 Sink节点（基站）之间在形成第二链路。然后，考虑通信耗能对第二链路的前提 下对第二链路进行改造，从而构建整个分层链树。

请参考图1至图4，本发明提供了一种基于区域划分的分层链树路由方法， 包括：

步骤1，请参考图1，将无线传器感网络划分为多个区域。

步骤2，请参考图2，使每个所述区域单独成簇，并按照PEGASIS协议将所 述簇内的节点通过遗传算法在相应的每个所述区域内形成第一链路。在图2中， ○代表普通节点，＋代表高级节点，﹡代表簇头，区域中心坐标原点代表Sink。

步骤3，请参考图2，按照能量最大化原则，在每个所述簇内选取簇头。具 体地说，记录下节点的剩余能量，在每个簇内链路上按照剩余能量最大的原则选 取簇头。

步骤4，请参考图3，按照PEGASIS协议将所述簇头与Sink节点之间的通 信链路通过遗传算法形成第二链路。例如，可以采用与步骤2中相同的遗传算法。

步骤5，请参考图4，将所述第二链路改造成以Sink节点为中心的分层链树。 特别地，改造的原则是降低能量消耗。优选地，分层链树为树簇式多跳通信链路。

步骤6，使节点数据沿着所述分层链树并通过数据融合传递给Sink节点， 经过预定的通信时间后，跳转执行步骤1，从而进入新的一轮。特别地，节点数 据按照形成的分层链树路由将数据沿着链树经过数据融合通过簇头最后传送给 Sink，经过一段时间通信，网络进入新的一轮。

由于本发明在各区域中选取能量最大的节点当选簇头，避免了LEACH协议 中由于随机选择簇头而导致整个网络的能量不均衡。进一步地，通过建立簇内节 点和簇头，簇头和Sink的多跳通信链路的方式，有效降低了LEACH算法中节 点之间采用单跳方式导致的长距离通信所产生的能耗。

在区域划分的基础上，每个区域单独成簇，通过按照PEGASIS成链的思想， 采用遗传算法将在各区域中的节点形成第一链路，选取能量最大的节点当选簇 头，避免了LEACH协议中由于随机选择簇头而导致整个网络的能量不均衡。进 一步地，簇头选举结束之后，簇头与Sink之间通信链路也按照PEGASIS的思想， 通过遗传算法使簇头和Sink形成第二链路，并在考虑到降低通信能耗的前提下， 将第二链路进行改造，从而形成以Sink为中心的树簇式多跳通信链路。这种分 层成链的方式，降低了LEACH算法中节点之间采用单跳方式导致的长距离通信 所产生的能耗。

优选地，所述步骤1中的所述无线传感器网络为正方形，所述正方形的无 线传器感网络划分为16个所述区域。例如，正方形的大小为200m*200m。

优选地，所述正方形的无线传器感网络划分为16个所述区域包括：将所述 正方形沿其对角线和中位线（即通过正方形的几何中心，且与正方形的相邻两边 分别对应的两条正交线）划分为八个区域；在所述正方形内划出一个同心的内部 正方形；所述内部正方形将所述八个区域划分为16个区域。

优选地，所述步骤1还包括：通过调节所述内部正方形的边长改变簇头的 负载平衡因子。

优选地，所述负载平衡因子LBF根据下式计算：

$\left[\mathrm{LBF}\right]=\frac{[\mathrm{head}\_\mathrm{num}]}{\underset{i=1}{\overset{\mathrm{head}\_\mathrm{num}}{\Sigma }}{(x_i-u)}^2}$

其中，

head_num为簇头的个数，x_i为第i个簇包含的节点个数，u为本轮簇平均 包含的节点个数。

优选地，在所述步骤2中，只有当所述第一链路内的任何一个节点死亡后 才重新构造新的第一链路。

优选地，在所述步骤2或5中的所述遗传算法的适应度函数fit为：

fit＝(1-(len-minlen)/(maxlen-minlen+0.001)))²

其中，len代表按当前序列形成链路的总长度，minlen代表这一代种群所有 链路的长度最短的链路长度，maxlen代表这一代种群所有链路中长度最长的链 路的长度。

优选地，在所述步骤5中，在所述第二链路上，按照所述第二链路的顺序依 次对簇头与簇头之间、以及簇头与Sink节点之间这两种通信方式的能耗进行分 析，如果簇头与上级簇头通信的能耗小于簇头直接与Sink节点的通信的耗能， 则该簇头维持原始通信路由；反之，则该簇头与Sink直接通信，从而降低消耗 能量。

在一个实施例中，按下以方式改造第二链路：

（1）链路上簇头与Sink直接通信，整个网络的能耗E₁为：

E₁＝E_εlεc+ε_fs·d₁²+E_DA

（2）链路上簇头与簇头通信，整个网络的能耗E₂为：

E₂＝E_elec+ε_fs·d₂²+E_DA+E_elec+E_DA

（3）当E₁≤E₂时簇头选择与sink直接通信从而改变链路，而当E₁＞E₂时该 簇头依旧保持原始通信路由，与上级簇头通信。

以上各式中：E_elec是接收或发送一比特所消耗的能量；E_DA是每处理一比特 的数据所消耗的能量，由传感器的硬件所决定的，一般只有E_elec的十分之一；ε_fx是一个取决于传感器所用的传输放大器模型的量。d₁为链路上的随机一个簇头直 接与Sink相连的距离，d₂是链路上的随机一个簇头与其链路上的上级簇头的距 离。

通过MATLAB仿真分析，请参考图5至图7，本发明在延长网络的稳定期 和能耗均衡方面比LEACH协议有了明显的提高，改善了大规模无线传感器网络 能量异构环境下的LEACH路由协议中簇头选举和节点单跳机制的不足。

以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域 的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内， 所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。