一种基于能量有效性的反应式路由算法的研究

王 雪，董 博

(1.辽宁大学信息化中心，辽宁 沈阳 110031； 2.辽宁大学创新创业学院，辽宁 沈阳 110031)

一种基于能量有效性的反应式路由算法的研究

王 雪1，董 博2

(1.辽宁大学信息化中心，辽宁 沈阳 110031； 2.辽宁大学创新创业学院，辽宁 沈阳 110031)

针对提高无线传感器网络的稳定性及其生存时间的问题，结合TEEN和DEEC方法，通过设置相关参数，提出了一种新的路由算法即改进的能量有效性算法EEER，并进行了仿真实验.结果表明，EEER算法可以延长网络的生存周期并提高网络的稳定性.

无线传感器网络；簇头；能量有效性；路由算法

无线传感器网络(WSN)近年来成为一个热门的研究课题，其主要原因在于这种网络可以广泛使用在工业、军事、人体健康和环境监测等多个领域.数据传感器可能以分散或者均匀的方式部署在基站周围进行数据采集.这种网络特点使得在设计传感器网络的时候需要考虑到多方面的因素，如电池容量、硬件资源、部署的随机性和动态不可靠环境等.近年来，无线传感器网络中的路由协议提出了很多算法，众多算法[1-3]对网络协议进行了多方面的设计，其中能量的节约作为其中一个重要的因素，得到了很大的关注.[4]W.B.Heinzelman等人[5]提出了用于无线传感器的算法LEACH，其主要思想是把节点进行分簇，从而形成传感器节点的集群.这样只在簇头节点Cluster Head(CH)执行到基站Base Station(BS)的数据进行传输，节约了能量.LEACH协议在由数据结构相同的节点组成的网络内能够很好地运行，而在异构的网络中，性能严重恶化.文献[6]提出了一种反应式路由协议，该路由协议把时间作为主要考虑因素.头结点CH的选择过程与LEACH的方案相同.CH的广播采用两种阈值，进行广播包的控制，这样不仅降低了数据包传输的数量也增加了网络的生存期.文献[7]提出DEEC(Distributed Energy Efficient Clustering)协议.DEEC也是一种聚类协议，它用于两级及多级异构网络.头结点CH的选举过程基于剩余的节点能量和网络的平均能量，具有较高初始化能量的结点成为头节点的概率较大.然而，DEEC对于异构网络的支持性不足，同时也不适合实时应用.

本文针对时间为关键因素的应用设计了一种协议，使其在同构和异构的网络中都具有较好的性能.

1 相关工作

在无线传感器网络中，根据应用模式的不同，将无线自组织网络分为主动型(proactive)协议和响应型(reactive)协议2种类型.主动型传感器网络协议通常持续监测周围的物质现象，并以恒定速率发送监测数据；而响应型路由协议及相关算法，只有在被观测变量及数据发生变化时才进行数据传送.因此，响应型传感器网络更适合在敏感时间的应用中.

1.1 TEEN算法

TEEN[8](Threshold Sensitive Energy Efficient Sensor Network Protocol)是第一个被提出的反应式路由算法，TEEN算法和LEACH算法的实现过程相类似，TEEN是响应型的算法，而LEACH属于主动型算法.在TEEN算法中定义了硬、软2个阈值，用来确定是否进行数据发送.当数据量第一次超过设定的硬阈值时，网络节点用新值作为硬阈值，并在下一个时间间隔内进行发送.如果节点收集的数据的变化幅度较大，并且大于软阈值的范围，则节点将会传送最新采集的数据，并且将它作为新的阈值.该算法通过调节阈值的大小，可以在监测精度和系统能耗之间取得合理的平衡，从而降低了传输数据的数量.

1.2 DEEC算法

DEEC[7]是一种主动型协议，用于两级或多级异构网络.具有较高的初始能量和较多的剩余能量的节点更容易被选为CH节点.

在两级异构网络中，存在两类节点.mN为高级节点，初始能量为E0(1+a)；(1-m)N为普通节点.E0是初始化能量，a和m为百分比类型的变量，用来控制节点是普通节点或者高级节点.网络中消耗能量的总和表示为

ETotal=N(1-m)E0+NmE0(1+a)=NE0(1+am).

(1)

所有多层次异构网络初始能量总和表示为

(2)

两级异构网络中普通节点成为头结点CH的概率为

(3)

扩展到多级异构网络中，CH的概率可以表示为

(4)

假设节点均匀分布在M×M区域内，则节点到CH节点间的距离为

(5)

头节点CH到基站BS的距离为

(6)

2 EEER算法描述

2.1 网络性能评估指标

本文定义了一系列相关性能参数用来对比算法的性能.

定义1(稳定时长) 该时长表示网络中节点初始化完成，从网络开始运行时间t0直到某一个节点无法响应的时间tNodedied.即

(7)

(8)

TNLT=TInstability+TStability.

(9)

定义4(存活网络节点) 表示能够正常运行的网络节点数量.即

NAlive=NAll-NDied.

(10)

其中NDied表示节点剩余能量Ei=0的节点.有

(11)

2.2EEER算法

基于上述内容，本文提出EEER算法.算法用于改善在分组过程中的稳定性，适用于响应型同构或者异构传感器网络中运行.

步骤1ni表示对于节点si成为头结点的选举过程中所经过的轮数.在网络运行过程中，所有结点不可能具有相同的剩余能量.基于r轮结点si不同，剩余能量Ei(r)选取不同的ni.

步骤2 令pi=1/ni为经过ni轮成为CH结点的概率.当节点在一个周期内具有相同的能量时，pi=popt确保每轮的CH结点数量为poptN，这样能使得节点死亡的时间大致相同.

步骤4 当簇(子集)形成之后，CH结点发送2个阈值.分别为硬阈值δ及软阈值Υ.各传感器节点不断监控内部变量X值.如果其数值达到了δ即X≥δ，该节点触发数据发送过程，如图1所示.

(a)子集形成X<δ

(b)X≥δ触发发送过程

步骤5 当前值Cv表示第一次发生传输过程发生时变量数值.Cv被存储在称为感测节点中的一个内部变量Y中.从而减少了传输的数据量.如果Cv-Y≥Υ，再一次进行数据传输.

每个节点通过初始化能量和剩余能量选举出头结点CH，使得每个节点都归并到某一个簇中.在步骤3中，每轮选举过程中不需要知道所有结点的能量形成子集并选出CH结点.步骤4中，节点发现当X≥δ时，头节点CH汇集数据触发发送过程，并将当前X存储到变量Y中.最后的步骤5中，通过采用变化的差值大于阈值Υ时才进行传输的机制，进一步减少了传输的数据量.

2.3 算法分析

主动感知类路由的协议，通过感知节点的周围环境并定期传输数据.由于周期性传输数据会不断地消耗能量.因此，本文算法的主要目的是延长网络生存周期，增加吞吐量和降低能量消耗.与主动式路由协议相比，EEER被动式路由协议是依赖型的应用[9-10].其定期感测周围环境，但只有当到达阈值时才进行发送.

因此，在被动式路由协议中[11]，吞吐量的大小由其应用所决定.在反应式网络中吞吐量与网络的生命周期及网络的稳定时长成反比.如果传输量较小，网络的稳定时长和网络的生存周期会延长.通过设置的参数δ和参数Υ可以调节网络的生存周期.例如，如果当前值X频繁超过δ，那么数据传输过程也会频繁发生，网络的稳定时长就会很短.

3 实验与仿真

采用NS-3进行模拟.节点数量为100，随机部署在100 m×100 m的正方形区域.假设基站位于区域中心.为了评估EEER的性能，选取TEEN协议和DEEC协议进行对比.实验过程中所使用的参数如表1所示.

表1 仿真过程选用参数

3.1 实验过程

实验的实施过程分成两个阶段.第一阶段设置EEER参数δ=100和参数Υ=3，进行实验模拟，对比TEEN、DEEC与EEER的网络生存周期和传输到BS的数据包传输数量；第二阶段，改变实验参数δ=60和参数Υ=10，再次对比本协议同其他2种协议的相关性能参数.

3.2 实验结果

第一阶段网络的生存周期如图2所示，从图2中可以看出，TEEN协议第一个节点死亡之后，剩余节点经过很少的轮数之后相继死亡.这是由于所有成为CH节点具有的相同的概率.DEEC协议相对延长了持久度时长和网络生存的时间，主要原因是由于CH的选取过程以残余能量作为基础.含有较高的剩余能量节点具有成为CH更大的概率.

EEER的节点生存周期同其他2种协议相比，稳定时长分别延长了51.7%和46.6%.EEER采用硬阈值提高了网络稳定性和网络的生存周期，软阈值进一步减少了数据的传输次数，从而降低了传输到基站(BS)的传输数据包的数量，降低了能源消耗，延长了网络寿命(见图3).

图2 节点能量相同网络生存周期对比

图3 节点能量同构情况下发送到BS的数据包数

第二阶段对部分节点采用高能节点的设置，同时调整了EEER的参数，设置δ=60和Υ=10，结果见图4.在图4中用EEER2表示.由于部分高能节点的加入，3种协议的网络生存周期都有所增加.另外，我们采用更改参数方式，可以更加灵活地调整网络的生存周期与吞吐量之间的关系，从而适应多种不同的应用环境.

图4 节点能量异构网络生存周期对比

图5 节点能量异构情况下发送到BS的数据包数

本文提出的算法在一定程度上提高了网络的生存周期，同时由于协议采用软硬2种阈值，增加了协议的灵活程度.通过减少硬阈值δ，EEER的稳定时长和网络寿命发生明显变化.稳定期和网络的生命周期降低.减少了2个阈值的EEER协议与DEEC的差异也在减小.同时硬阈值也影响了网络的生存周期.如果传输数据包的数量增加，网络的生命周期会随之减小，同样数据包的数量减少，网络的生存周期会随之增加(见图5).

4 结束语

本文提出了基于能量有效性的反应式路由算法EEER，该算法与TEEN和DEEC相结合，同时设置了相关的参数对原有的算法加以改进.通过实验可以看出，本文算法继承了先前算法的优点，并且比原有算法TEEN和DEEC延长了网络生存周期，具有更好的实用性.

[1] YAO YANJUN，QING CAO，ATHANASIOS V. VASILAKOS: An energy-efficient，delay-aware，and lifetime-balancing data collection protocol for heterogeneous wireless sensor networks[J]. Networking IEEE/ACM Transactions on，2015，23(6):810-823.

[2] HEINZELMAN WENDI B.，ANANTHA P. CHANDRAKASAN，HARI BALAKRISHNAN. An application-specific protocol architecture for wireless microsensor networks[J]. Wireless Communications IEEE Transactions on，2002，1(4): 660-670.

[3] SINGH M P，GORE M M. A new energy-efficient clustering protocol for wireless sensor networks[C]// Intelligent Sensors，Sensor Networks and Information Processing Conference，2005. Proceedings of the 2005 International Conference on，Hatfield：IEEE，2006:25-30.

[4] CHELLATHURAI，A. SAMUEL，E. GEORGE DHARMA PRAKASH RA. A strategic review of routing protocols for mobile ad hoc networks[J]. International Journal of Engineering Trends & Technology，2014，10(8):390-395.

[5] HABIBI，JALAL，ALI GHRAYEB，AMIR G. AGHDAM. Energy-efficient cooperative routing in wireless sensor networks: a mixed-integer optimization framework and explicit solution[J]. IEEE Transactions on Communications，2013，61(8):3424-3437.

[6] MANJESHWAR A，DHARMA P. TEEN:A routing protocol for enhanced efficiency in wireless sensor networks[C]//Proceedings International Parallel & Distributed Processing Symposium，San Francisco：IEEE，2001:2009-2015.

[7] LIU JINGJING，YANJUN HU. A balanced and energy-efficient clustering algorithm for heterogeneous wireless sensor networks[C]// Wireless Communications and Signal Processing (WCSP)，2014 Sixth International Conference on，Hefei：IEEE，2014:1-6.

[8] TYAGI S S，CHAUHAN R K. Performance analysis of proactive and reactive routing protocols for ad hoc networks[J]. International Journal of Computer Applications，2010，1(14):27-30.

[9] ALMURIB H A F，KUMAR T N，LOMBARDI F. Scalable application-dependent diagnosisof interconnects of SRAM-based FPGAs[J]. IEEE Transactions on Computers，2014，63(63):1540-1550.

[10] 吴鹏悦，季薇. 基于能量有效性和时间有效性的联合优化绿色通信算法[J]. 计算机应用，2014，34(7):1969-1973.

[11] 黄廷辉，伊凯，崔更申，等. 基于非均匀分簇的无线传感器网络分层路由协议[J]. 计算机应用，2016，36(1):66-71.

(责任编辑：石绍庆)

Aresearchbasedonenergyefficientreactivealgorithmforwirelesssensornetworking

WANG Xue1，DONG Bo2

(1 Information Technology Center，Liaoning University，Shenyang 110031，China; 2.School of Innovation and Entrepreneurship，Liaoning University，Shenyang 110031，China)

In order to improve the stability and lifetime of wireless sensor network，using the combination of TEEN and DEEC by setting the relevant parameters，this paper proposed a new routing algorithm named EEER algorithm which improved energy efficiency，and the simulation results show that the EEER algorithm can prolong the network lifetime and improve the stability of the network.

WSN；cluster head；energy efficient；routing algorithm

1000-1832(2017)03-0068-05

10.16163/j.cnki.22-1123/n.2017.03.015

2016-12-30

国家自然科学基金资助项目(61502090)；辽宁省教育厅科技项目(LYB201620);国家档案局科技项目(2016-X-25)；辽宁省档案局科技项目(L-2016-R-6，L-2017-R-7).

王雪(1981—)，女，实验师，主要从事数据挖掘、无线传感器网络、信息化应用研究；董博(1981—)，男，副教授，主要从事人工智能、数据挖掘、电子商务研究.

TP 393 [学科代码] 520·10

A