基于最优连通功率的无线传感器网络路由算法

刘丽军

湖南现代物流职业技术学院物流信息系，长沙410131

基于最优连通功率的无线传感器网络路由算法

刘丽军

湖南现代物流职业技术学院物流信息系，长沙410131

为了延长网络生存时间，保持节点的能耗平均衡，提出了一种最优连通功率的无线传感器网络路由算法。首先根据最优连通功率选择最优的邻居节点集合，然后根据节点剩余能量选择簇首，并采用自适应的簇间通信方式，最后在Matlab 2012工具箱进行仿真测试。实验结果表明，相对于当前经典路由算法，提出的最优连通功率路由算法解决了传感器节点耗能不均衡难题，提高了无线传感器节点的能量利用率。

最优连通功率；无线传感器网络；分簇路由；LEACH算法

1　引言

无线传感器网络（Wireless Sensor Networks，WSN）由一个由许多节点组成无线网络，节点能量、通信和计算能力有限，而且部署在难以到达的恶劣环境，节点能量无法补充且易被破坏，导致节点失效，这是制约节点路由和网络生存时间的关键［1］。因此如何设计能量高效的路由算法，提高节点能量利用率，具有十分重要的现实意义和应用价值［2］。

无线传感器网络路由算法吸引了国内外众多高校、科研院所的关注，它们提出许多无线传感器路由算法。路由算法主要包括平面和分簇路由算法两种，平面路由算法的全部传感器节点是平等的，通过自组织方式协同工作，没有管理节点，无法对通信资源进行优化管理，不适合应用于现代大规模传感器网络［3-4］。LEACH是最早提出的分簇路由算法，其通过周期性随机选举簇首均衡网络中的能耗，但是由于没有考虑传感器节点的剩余能量，簇首与Sink直接通信，簇首能耗不均衡，网络生命周期过短［5］。为此，在LEACH算法的基础上，文献［6］提出了负载均衡的路由算法，利用簇半径、簇间距和节点能量为参数进行簇首选举，能量较多节点成为簇首的概率大，但簇首与Sink采用多级跳方式通信，靠近Sink簇节点会提前死亡；文献［7］提出了基于能量和距离的集中式的分簇路由算法，但存在簇首分布不均等缺陷；文献［8］中提出一种基于双簇首的路由算法，把接收和融合的步骤分开，簇首选举开销小，但主簇首到副簇首的传输能耗较大；文献［9］提出了基于节点剩余能量的分簇路由算法，每个簇由一个簇首、若干个协同簇首和簇内节点组成，在保证数据传输率的同时提高了能量利用率。

针对当前经典无线传感器网络路由算法存在的一些难题，为了保证整个网络能量均衡性，提出了一种最优连通功率的无线传感器网络路由算法，并通过仿真实验测试算法的性能。

2　WSN模型及能耗模型

2.1WSN系统模型

在WSN的实际应用中，通常在监控区域随机撒下大量的节点，这些节点可以对目标的状态进行感知，并具有一定的计算能力，它们将收集的信息均融合到自己所在的簇头节点，而且簇头节点将其转发给你汇聚节点，具体如图1所示。为了简化问题，在进行网络路由算法设计过程中，进行一些假设：

（1）所有传感器节点均通过一个ID号对其进行识别，它们部署好后，一般是不能移动的，而且汇聚节点的能量可以是无限，可以不断被充的，而且计算能力比一般节点要强。

（2）除了汇聚节点，其他节点能量十分有限，而且不能进行相应的补充，任意一个节点都可以成为簇头节点，而且簇头节点也可以变为普通节点。

（3）所有普通节点的物理性能是相同，有一定的数据转发能力，而且节点的发射功能可以根据外界环境进行不断调整［10］。

图1　WSN的基本结构

2.2能量消耗模型

在节点的工作过程，其能量在不断地被消耗，而且传输功率与其传输距离是密切相关，是一种动态的指数衰减关系，无线通信模型如图2所示［6］。

图2　无线通信能耗模型

设节点间的距离阈值d0，其计算公式如下：

式中，εfs和εmp分别为两种模型中功率放大所消耗的能量；d0。

节点i要向节点j发送k bit的数据的能耗为：

节点j接收节点i发送的k bit数据，其能耗为：

式中，Eamp代表放大器消耗的能量；Eelec代表无线收发电路的能耗。

3　LEACH算法

3.1LEACH算法概述

LEACH算法是一种标准的分簇算法，后面的许多算法都是在它的基础上发展起来，其工作周期为轮，而且每一轮分为簇建立阶段和数据传输两个时间段。在簇建立阶段，首先节点产生个随机数，并其与事先设置好的阈值T（n）进行对比较，如果事先设置好的阈值，那么就可以认为该传感器节点就是簇头，T（n）设置具体如下：

式中，p为簇头节点百分比，r为工作轮数，G为最近r轮未当选簇头的节点。

LEACH算法的簇建立过程具体如图3所示。

图3　簇建立阶段流程图

数据传输阶段，首先将该阶段分为多个时隙，每一个节点在自己的时隙内将数据转发到所在的簇头节点，然后簇头节点对数据进行融合，消除其中的冗余数据，最后转发给汇聚节点。

3.2LEACH算法存在缺陷

LEACH算法在无线传感器网络路由协议中占有非常重要的地位，其路由扩展性好，但LEACH算法存在以下一些缺陷：

（1）LEACH算法中簇头选举机制不完善。簇头的选举由阈值决定，具有随机性，簇头节点分布不均匀，各簇结构规模具有差异，簇头节点能耗分配不均。

（2）LEACH算法簇头选举未考虑节点能量，低能量簇头节点一旦失效，则会出现通信盲区，不利于延长整个网络的生存周期。

（3）LEACH算法簇头选举机制未考虑簇头分布，导致通信能量浪费。

（4）LEACH算法虽具有一定的容错机制，但其容错机制有限，只能解决相对简单问题。

4　提出的路由算法

4.1相关定义

根据文献［11］，传感器节点k的最优连通功率为：

式中，Popt（i）和Nopt分别表示最优邻居节点数和最优邻居节点数。

对于节点k的任意一个邻居节点j，如果节点j满足式（6），则称节点j为节点k的最优邻居节点。

式中，Topt（i）为节点k的所有的最优邻居节点集合。

对于任意节点i，当网络稳定且连通时，则有：

式中，Dopt（k）为节点k的连通度。

4.2路由算法设计

4.2.1最优邻居节点选择阶段

（1）网络中任意节点k，经过随机退避时间段后，节点i以最大功率对外广播HELLO-1消息，接收到消息的节点i，计算节点k到自己的最优发射功率，在一段时间过后，节点i将得到其最大邻居节点的集合Tmax（k）。

（2）如果Tmax（k）为空，那么表示节点k为孤立节点，不然在Tmax（k）中选择最优邻居节点，并计算节点的最优连通功率Poc（k）。

（3）得到节点k的最优连通功率Poc（k）后，现次邻居节点发送HELLO-2消息，节点i收到消息后，如果Popt（k）≥Popt（i），那么以其最优连通功率Poc（i）向节点k发送ACK-2确认消息，不然节点i将该消息丢弃。经过一段时间以后，可以获得节点k的连通度Dopt（k）和及相应连通节点。

（4）如果网络中存在节点k，Dopt（k）=0，那么就表示该节点为孤立节点，否则，在Topt（k）中取得可调最优邻居节点的集合

4.2.2稳定成簇阶段

在一个基于连通功率的成簇算法中，一个簇由簇首及最优邻居节点组成，因此，对于具有N个节点的无线传感网络，最理想的簇首个数为：

那么，网络中节点i成为簇首的概率为：

为了使高剩余能量的节点成为簇头节点概率增加，那么节点成为簇首的概率计算公式为：

式中，Ei_current为节点i当前的剩余能量；Ei_current为节点i的最大能量。

4.2.3簇间通信

为了均衡各簇头节点的能量，数据传输采用单跳和多跳混合的路由方式，设定阈值d0，当节点i到sink的距离d小于d0时，采用单跳方式将数据传送给sink，当d大于d0时，则采用多跳将数据传送给sink，具体如图4所示。

图4　簇间的通信方式

5　仿真实验

5.1仿真参数

为了测试本文算法的性能，在Intel 4核心2.65 GHz的CPU、4 GB RAM，采用MATLAB 2012工具箱进行仿真实验，仿真参数具体如表1所示。选择当前经典的路由算法［12-13］进行性能对比分析，采用网络平均能耗和网络生存时间、数据传输时延、传输分组丢失率、等评价指标对算法性能进行评价。

表1　实验参数

5.2结果与分析

5.2.1传输延迟比较

不同网络规模下，所有路由算法的数据延迟变化曲线如图5所示。从图5可知，随无线传感器节点数增加，所有路由算法的传输延迟差异越来越明显，而相对于其他路由算法，最优连通功率的路由的数据传输延迟大幅度变小，这主要是由于对于最优连通功率的路由，本文算法可以避免选择节点传输性能比较差的邻居传感器节点，加快了数据转发时间，提高了数据转发的效率，数据转发的可靠性更高。

图5　不同算法的数据传输延迟变化曲线

5.2.2丢包率比较

不同节点规模件下，所有路由算法的数据丢包率如图6所示。从图6可以看出，随着传感器节点数的增加，全部路由算法的数据丢包率增加，在相同条件下，本文算法的数据丢包率较小，而且变化幅度相对较小，对比结果表明，本文算法可以动态调整无线传感器数据转发路由，解决传统路由算法路径中节点选择的不足，建立质量更优的节点转发数据路径，提高了数据传输的成功率，而且具有比较明显的优势。

图6　不同算法的丢包率变化曲线

5.2.3网络剩余能量比较

随时间的变化，整个网络总剩余能量变化曲线如图7所示。在图7中，曲线斜率越大表示网络能耗速度越快，斜率越小表示网络能耗速度越小，从图7可以看出，本文算法的网络能耗速度要慢于对比算法的网络能耗速度，并且网络剩余能量曲线始终处于对比算法的上方，说明在相同的时刻，本文算法的剩余能量始终大于对比算法的网络剩余能量，对比结果表明，本文算法更能有效地节约节点的能量。

图7　几种路由算法的总剩余能量变化曲线

5.2.4网络生存时间对比

网络生存时间是评价一个路由算法的重要标准之一，网络生存时间仿真曲线如8所示。从图8可知，相对于对比路由算法，本文算法有效延长了网络生存时间，每一个死亡节点时间大幅度迟延，在相同工作轮数，节点死亡比例相对较少。

图8　不同算法的网络生存时间对比

6　结束语

为了保证无线传感器网络能耗平衡，提出了一种基于最优连通功率的无线传感器路由算法，首先根据最优连通功率选择最优的邻居节点集合，然后根据节点剩余能量选择簇首，并采用自适应的簇间通信方式，最后在Matlab 2012工具箱进行仿真测试。结果表明，最优连通功率的路由算法加快了数据传输速度，大幅度减少了数据转发丢包率，提高了节点的能量利用率，网络生存周期得到了进一步的延长，具有广泛的应用前景。

［1］任丰原，黄海宁，林闯.无线传感器网络［J］.软件学报，2003，14（7）.

［2］Kim Hyunsook.Cluster head selection scheme for minimizing the changes of the cluster members considering mobilityinmobilewirelesssensornetworks［C］//2013 15th International Conference on IEEE，2013：285-289.

［3］吴振华，尹志军.基于优化簇半径的WSNs分均匀分簇路由［J］.计算机工程与设计，2010，31（15）：3374-3378.

［4］李辉，李腊元，李方云.一种基于低能量的双簇首WSN路由算法［J］.武汉理工大学学报，2009，33（3）：450-453.

［5］邹虹，彭国龙.一种基于LEACH改进的均匀分簇路由算法［J］电视技术，2013，37（3）：133-140.

［6］陈炳才，么华卓，杨明川，等.一种基于LEACH协议改进的簇间多跳路由协议［J］.传感技术学报，2014（3）：373-377.

［7］胡钢，谢冬梅，吴元忠.无线传感器网络路由协议LEACH的研究与改进［J］.传感技术学报，2007，20（6）：1391-1396.

［8］李方敏，徐文君，刘新华，等.无线传感器/执行器网络中能量有效的实时分簇路由协议［J］.计算机研究与发展，2008，45（1）：26-33.

［9］李方敏，徐文君，刘新华.无线传感器网络功率控制技术［J］.软件学报，2008，19（3）：716-732.

［10］刘新华，李方敏，方艺霖，等.一种基于链路级功率控制的分簇路由算法［J］.计算机科学，2012，39（9）：64-70.

［11］李方敏，刘新华，旷海兰.基于最优连通功率的无线传感器网络稳定成簇算法［J］.通信学报，2008，30（3）：75-83.

［12］柏荡，石为人，高鹏，等.无线传感器网络跳数优化非均衡路由算法［J］.计算机工程与应用，2012，48（32）：60-64.

［13］刘述钢，刘宏立，詹杰，等.无线传感网络中能耗均衡的混合通信算法研究［J］.通信学报，2009，31（1）：12-17.

［14］仲元昌，宋扬.大规模无线传感器网络自适应节能路由算法［J］.计算机工程与应用，2013，49（1）：89-93.

［15］于凯，谢志军，金光，等.基于功率控制的无线传感器网络MAC协议研究［J］.传感技术学报，2013，26（9）：1297-1302.

Routing algorithm in wireless sensor network based on optimal connectivity power.

LIU Lijun

Department of Logistics Information，Hunan Vocational College of Modern Logistics，Changsha 410131，China

In order to prolong the life time of the network and ensure energy balance of the wireless sensor network，a novel routing algorithm of wireless sensor network based on optimal connectivity power is proposed in this paper to solve the deficiencies of LEACH algorithm.Firstly，the optimal neighbor set are chosen according to the optimal connectivity power，and then cluster head is selected according to the node residual energy and communication mode of inter cluster adaptively，finally the performance is test by simulation experiments on Matlab 2012.The simulation results show that the proposed algorithm has solved the node energy imbalance problem and improved the energy utilization of the network.

optimal connectivity power；wireless sensor networks；clustering routing；LEACH algorithm

A

TP391

10.3778/j.issn.1002-8331.1408-0100

湖南省教育厅科学研究项目（No.14C0811）。

刘丽军（1983—），讲师，主要研究方向：计算机网络、物联网技术与应用。

2014-08-21

2014-10-14

1002-8331（2015）22-0119-05