能量高效的WSN分簇路由协议研究

杜佳轩　杨军

摘要：传统分簇路由协议存在簇首节点的能耗分布不均匀，簇首节点与基站之间数据传输未采用最短路径传送，数据传输效率低使得网络能耗较高及网络生存期短问题。针对这些问题提出一种基于剩余能量和簇首最佳距离的分布式分簇路由算法EDAC。由基站根据剩余能量选择候选簇头，被选择簇头之间的距离要求在最佳簇首分布距离内，利用蚁群优化算法在各簇头之间找到一条最短路径多跳传输数据。Matlab仿真结果表明，EDAC协议比LEACH协议在网络生存期上延长了20%。

关键词：无线传感器网络；剩余能量；最佳簇首分布；蚁群算法

中图分类号：TP393.1 文献标识码：A 文章编号：1009-3044（2016）18-0025-02

Research of Clustering Routing Protocol based on Energy Efficient Wireless Sensor Network

DU Jia-xuan1，YANG Jun

（1.School of Mathematics and Computer， NingXia University，Yinchuan 750021，China； 2.Network Administration Center， NingXia University，Yinchuan 750021，China）

Abstract：Traditional cluster-based routing protocols do not perform so well in network energy consumption and lifetime when the network is large，because energy consumption among cluster-heads are not uniform，the route between BS and cluster-heads may be not the shortest，the low data transmission efficiency.To solve these problems， based on residual energy and the best distance of the cluster head proposed a distributed clustering routing protocols EDAC. The base station selects a candidate cluster head based on the residual energy ， to be selected cluster head should within the best cluster head distribution optimum distance， using AC algorithm find the shortest path between each cluster head so that multihop transmission data. The simulation with MATLAB shows that the EDAC outperforms LEACH nearly 20% in the network lifetime.

Key words： WSNs；Residual Energy；Best Cluster Head Distribution；AC

1 引言

无线传感器网络WSNs[1]（Wireless Sensor Networks）是数目较大且具有计算能力和处理能力小型传感器节点通过有限的能量供应进行数据采集的自组织网络。在有限的能量供应下，传感器节点将采集的感知数据通过某种协议传送至基站，在这一过程中能量的有效利用是延长无线传感器网络生存时间的关键。学者们针对WSNs中能量有效利用问题提出了很多新颖的想法，其中分簇思想由于在实际应用中得到了良好的效果从而引起了学者们的广泛关注。LEACH（Low energy adaptive clustering hierarchy）[2]协议采取随机性的选择簇头把能量的消耗分布在无线传感器网络内的所有节点上。HEED[3]（Hybrid energy efficient distributed clustering）是基于混合能量和通信代价的特定概率公式选择簇头，剩余能量较高和低通信代价的节点才可以当选簇头，但是该协议不保证最优的簇头数和网络连通性.

通过对以上文献总结得出，已经存在的算法都存在簇首分布不合理，簇间通信耗能较高，分簇不均匀等问题。本文充分考虑了以上各算法的不足之处，主要针对各算法中簇头分布不均匀，簇间数据传输能耗较大的问题，提出一种综合节点剩余能量又考虑簇头分布、簇内单跳簇间多跳分簇路由协议。

2 网络模型和问题描述

本文采用的无线电能耗模型，发送端的能量主要消耗在无线电发送元件和功率放大器，接收端的能量主要消耗在无线电发送元件，实验采用自由空间（功耗损失）多径衰减（功耗损失）信道模型，主要与发送端和接收端之间的距离有关。

传感器节点发送l-bit数据耗能：

（1）

传感器节点接受1-bit数据耗能：

（2）

上式中，是发射电路元件功耗，为接收电路功耗，取决于数字编码，过滤和信号扩散方式。l是传送的数据包的大小，d发送端和接收端之间的距离，和为放大器功耗，取决于接收者的距离和误码率。，为距离门限，根据数据发送者和接受者之间的距离，选择自由空间信道模型或者多径衰减信道模型。

3 改进协议设计

改进协议充分考虑了节点的剩余能量，与LEACH协议一致，本文也才用“轮”的概念。协议的没轮分簇的建立和稳定数据传输两阶段。在簇建立过程中，我们首先由基站指定簇头，由于初始能量相同，在以后的轮中我们根据节点的剩余能量选择候选簇头，候选簇头如果在簇首最佳距离之间，则候选簇头成为正式簇头，并广播已当选簇头的消息，根据信号的质量非簇头就近入簇。本文利用基于能耗的最优簇头数公式来计算控制簇头数量。在数据传送阶段，我们利用蚁群优化算法在簇头之间找出一条最短的数据传送路径，有效的减少网络开销。算法使用的变量如下：节点剩余能量：ND_R_Energy，节点平均剩余能量：ND_Ave_R_Energy，簇头数目：k。

3.1 簇的建立

在簇头选举开始时，第一轮簇头由基站指派。第二轮开始时每个簇统计簇内节点的剩余能量信息，每个节点将自己的剩余能量发送给簇头，各簇头节点计算平均剩余能量，并且将计算所得结果传送至基站，由基站计算整个网络的平均剩余能量。基站广播带有平均剩余能量的消息，如果簇头的剩余能量大于平均剩余能量则继续当选簇头，否则进行下一轮分簇。与由于簇头的产生是均匀分布在网络范围内的，从第三轮开始，在一个簇头的管理范围之内，我们采取集中式簇头选举方式在每个簇范围内选举簇头，建立新的簇。如果没有被任何簇加入，则自己发送广播消息成为簇头。具体算法步骤如下：

1）大于平均能量的传感器节点放入集合A，并由大到小排序，即；

2）被当做是第一个簇首，加入集合B中；

3）建立集合D，D是簇头间距最佳距离范围的集合。计算候选簇头与的距离，并与集合D进行比较，距离在集合D内，则为簇首，加入簇首集合B中。否则，为普通节点；继续计算下一个候选节点，继续判断，直到产生第二个簇首；

4）同理，在选择第m（m>2）个簇头时。必须保证它与前m-1个簇头的距离都在D内。

5）如果簇头数达到计算得到的最优簇头数k，我们就停止本轮选举过程。

6）通过以上的步骤我们可以得到集合，此后每个簇头节点管理簇成员节点。

7）如果需要重新分簇，我们主要考虑节点的剩余能量，簇成员节点之间计算簇头竞争概率，概率最大者成为簇头，并广播自己成为簇头消息，其他节点根据最小接收能量就近入簇，如果没有被任何簇加入，则自己发送广播消息成为簇头。簇头选举概率由公式（8）给出

（8）

3.2 稳定数据传输阶段

分别将簇头和基站的坐标放入矩阵和中，利用蚁群优化算法（AC）算法在簇头和基站之间找到一条可行的最短路径进行数据传输[4]。为了避免数据传输集中于同一路径，过早的消耗完此路径上距离Sink节点较近节点的能量从而导致该节点失效，我们采取下面办法：

程序流程

1）初始化：簇首和基站的总个数、簇首和基站坐标、AC算法的相关参数；

2）基站运行AC算法，得到一条最优路径并且记录离Sink节点最近（n/4）节点的编号，计算这些节点的ND_R_Energy；

3）如果ND_R_Energy小于ND_Ave_R_Energy，将此节点加入AC算法的禁忌表，标记为暂时不可传输节点。否则进入第四步；

4）基站计算分析所得路径是否可行，程序结束，节点开始数据传送。否则，转到第2步。

当一轮数据传输结束后，重新进入簇的建立阶段，进行下一轮簇重构，直至能量耗尽。

4 仿真结果分析

4.1 仿真实验环境

本实验采用Matlab软件进行仿真分析，我们主要对LEACH协议及改进的EDAC协议进行了模拟，从网络的死亡节点对比情况来进行性能分析。实际仿真参数相同如下表1所示。

4.2 性能分析

我们分别运行LEACH协议，EDAC协议10次，网络中平均死亡节点（总结点-存活节点）对比情况如图7所示，由对比可知EDAC协议第一个死亡节点出现要晚于LEACH协议（LEACH协议第一个节点死亡轮数是762，EDAC第一个节点死亡轮数为1050）。在死亡节点为80%时，LEACH协议运行了大约1200轮，而EDAC协议已经运行了1500轮，从而EDAC协议使网络生存期延长了20%。实验表明，EDAC协议有效延长了网络中第一个死亡节点出现的时间，而且在网络有效的情况下，改进算法明显延长了网络的生命周期，最终有效提高了网络的性能。

参考文献：

[1] Rashid B， Rehmani MH. Applications of wireless sensor networks for urban areas： A survey[J]. Journal of Network and Computer Applications， 2016， 60： 192-219.

[2] Arora VK， Sharma V， Sachdeva M. A Survey on LEACH and others Routing Protocols in Wireless Sensor Network[J]. Optik - International Journal for Light and Electron Optics.

[3] Chand S， Singh S， Kumar B. Heterogeneous HEED Protocol for Wireless Sensor Networks[J]. Wireless Personal Communications， 2014， 77 （3）： 2117-2139.

[4] 缪聪聪， 陈庆奎， 曹剑炜 等. 基于蚁群的无线传感器网络能量均衡非均匀分簇路由算法[J]. 计算机应用， 2013，（12）： 3410-3414.