保证服务质量的无线传感网节能跨层路由算法

高良诚，　刘　杰，　李江华

(铜陵职业技术学院 信息工程系， 安徽 铜陵　244061)



保证服务质量的无线传感网节能跨层路由算法

高良诚，刘杰，李江华

(铜陵职业技术学院 信息工程系， 安徽 铜陵244061)

摘要：针对无线传感器网络保证服务质量的路由问题，提出一种区分服务和优先级保证的无线传感网跨层节能算法，该算法对网络服务分级，在蚁群算法的路径选择时综合考虑节点的剩余能量、负载和节点位置信息，同时选择切换概率小的信道。仿真实验表明，该算法在保证服务质量的前提下，增加了路由的有效性和鲁棒性，降低并均衡各节点能耗，时延、网络生存周期等指标均体现较好性能。

关键词：无线传感网； 服务质量； 节能； 跨层； 改进蚁群算法

0引言

中高速无线传感网络[1]作为物联网的重要基础设施，在智能农业、自然灾害预报、监控预警、复杂任务调度等领域得到广泛应用，用户需要一定服务质量保障，尤其是对时延有很高的要求。传感网络中传感器节点多使用电池供电，能量有限，路由算法的低能耗成为其重要性能要求，在路由算法设计时，如果只追求服务质量，不考虑能量消耗，将会造成部分节点由于能量过早耗尽而死亡，从而严重影响网络性能[2-3]。如何设计出在数据传输过程中能够满足传输时延、带宽、丢包率、传输吞吐量等服务要求的高效节能路由算法是当前重要研究课题[4-5]。

节点能耗与节点的距离平方成正比[6]，通常通过短距离多跳路由来降低能耗，但势必带来时延的增加，因此，时延等服务质量要求与节能存在矛盾。设计满足传输时延、带宽、丢包率、传输吞吐量等多个约束条件的QoS路由被证明是个TSP问题，一般采用启发式算法解决，国内外学者做了大量的研究工作，蚁群算法、博弈论、遗传算法、模拟退火算法等智能算法得到广泛应用[7-8]。文献[9]提出的 REAR (Real-time and Energy Aware QoS Routing)协议构造了一个成本函数,对路径的能耗和时延进行权衡,评估每条路径的成本，最终确定一条QoS路由，没有考虑中高速传感网需要针对不同业务提供不同的QoS保障。QRQIA[10]采用Q学习和改进蚁群算法解决自组织网络QoS路由问题，对节点运算能力要求较高。EEABR[11]路由路径的长度考虑节点的能量水平，达到节能和延长网络生存周期的目的，但没有充分考虑拥塞和负载问题。

文中提出一种无线传感网保证服务质量的节能跨层路由算法ECRGQ，对网络服务分级，在保障时延等服务质量要求的前提下，通过跨层路由设计，运用基于信道可用率算法解决MAC层时延问题,在路径选择时考虑下一节点的剩余能量、节点发送能量和下一节点负载，提高路由的有效性和鲁棒性。

1系统模型及问题描述

1.1网络模型

在无线传感网络中，节点一般由汇聚节点(sink)和若干传感器节点组成，网络模型可用图G=(V，E)表示，其中,V(G)={v1,v2,…，vn}表示传感器节点集合，E(G)={e1,e2,…,en}表示边的集合，对于任意一个边e∈E(G)，边的权值对应时延、带宽等QoS属性，网络具有以下性质：

1)sink节点和普通节点位置固定，普通节点均匀分布在监控区域内；

2)sink节点能量无限，普通传感器节点能量受限；

3)使用统一能量模型；

4)节点能够感知自己位置信息；

5)节点能根据通信距离的远近动态地调整发送功率；

6)节点休眠时，无线收发模块暂停工作，但监测模块正常工作。

1.2能量模型

无线传感网节点主要对数据进行接收、发送或转发，采用文献[6]的能量模型计算节点收发数据消耗的能量。

1)节点i向距离为d的节点j发送n字节数据的能量消耗为Eij(n,d)。

(1)

2)节点j接收n字节数据的能量消耗为

(2)

3)节点j向节点k转发n字节数据的能量消耗为Ejk(n,d)。

(3)

式中：Ew----无线收发电路收或发1bit数据时所消耗的能量；

εfs----当d

εmp----当d≥d0时发射放大器发送1bit数据所需要的能量;

d0----传输距离阈值，d0=Sqrt(εfs/εmp)。

可以看出，节点发送数据的能量消耗与距离的平方成正比。

1.3区分服务QoS路由

中高速无线传感网络的业务通常分为实时性业务和非实时性业务[12]，实时性业务具有时延敏感、吞吐量要求高等特点，非实时性业务具有对时延容忍、吞吐量要求不高等特点。

根据不同业务对QoS的不同要求，将业务分为A、B、C三种类型， A类为时延敏感且可靠性要求高的实时性业务，如预警等业务；B类为对带宽要求高的实时性业务，如视频监控等业务；C类为对时延、可靠性要求不高的业务，如信息查询、周期性数据收集等业务。优先级由高到低为：A>B>C。

区分服务路由的QoS参数指标主要包括：

1)最大时延Time-Delay，记作TDmax；

2)最小带宽BandWidth，记作BWmin；

3)最大丢包率Packet-Loss，记作PLmax。

定义1QoS路由路径费用函数式表示如下：

(4)

式(4)，费用函数与带宽成反比，而与时延、丢包率成正比。w1、w2和w3为比例系数，w1>1,w2>1,w3>1，其值可根据不同服务种类来确定，如A类业务，可设置w3=1, w1和w2为大于1的数，其值越大,则表明对路由的时延和可靠性要求越高。

因此，文中的节能QoS路由算法即为在满足上述QoS约束条件的前提下，寻找节能性能最优且Cost(P)值最小的路径。

2QoS节能跨层路由算法

2.1基于信道可用率的信道选择算法

无线传感网络是一种特殊的认知网络，节点可用频谱具有不确定性，信道切换难于避免，研究表明，20 MHz～3 GHz的频谱范围内，收发器的工作频段每改变10 MHz通常会带来10 ms的时延[13]。因此，对时延要求高的服务，在路径选择的同时，选择切换少的信道，进行跨层路由设计，可以大大提高网络时延性能[14]。PCLRP[15]通过信道感知算法减少信道时延，但算法对节点计算能力要求较高，不适合在传感网络中使用。

文中使用基于信道可用率的信道选择算法，统计节点历史信道可用率，并据此选择数据发送信道。节点维护信道可用率信息〈P1，P2，P3，…，Pi，…〉，Pi表示第i条信道的可用率，使用下式更新。

(5)

式中----发送数据前信道i的可用率;

k----正整数。

0

2.2改进蚁群算法

区分服务QoS路由是NP-Complete问题，可以使用蚁群算法解决。蚁群算法核心思想是蚂蚁根据路径转移概率值来选择路径，路径的信息素浓度高或路径启发函数值大，则路径转移概率大，该路径被选择的概率大，同时采用适当的策略对信息素进行更新，进而驱动蚂蚁选择最优路径。

文中算法在路径启发函数中把下一跳节点剩余能量、与sink节点距离等作为重要指标，并在信息素更新时引入下一节点负载信息和路径费用函数，找出最优路径。

2.2.1路径转移函数

(6)

式中：μij(t)----时刻t节点i与节点j之间的信息素浓度;

ηij(t)----时刻t路径启发函数，与节点能量状态、节点距离和下一节点到sink节点距离相关;

α----残留信息素启发因子，反映残留信息的重要性;

β----期望启发因子，反映路径选择参数的重要性;

tabuk----禁忌表，存储蚂蚁k当前所走过的节点。

定义2路径启发函数ηij与节点能耗比、节点间距离、节点与sink的距离等相关，公式表示如下:

(7)

式中：Ej-init----节点j初始能量;

Ej----节点j剩余能量;

di,sink----节点i到sink节点的距离;

dj,sink----节点j到sink节点的距离;

r----以sink节点为圆心的半径;

dij----节点i到节点j的距离;

λ1,λ2----能见度系数。

λ1和λ2可以平衡时延和能量消耗，对于A类服务，当节点距sink超过r时，则λ1可以设置较小值，从而提高算法的时延性能。

式(7)表明，路径启发函数与节点能耗比、节点间距离、下一节点与sink的距离等相关，节点消耗能量越少,节点间距离越短,下一节点与sink的距离越近，该节点被选择的概率越大。因而，最优路径上节点剩余能量更大，更有利能量均衡；当节点距sink超过r时，采用短距离多跳路由，消耗能量更小，从而提高路由的鲁棒性。

2.2.2信息素更新

当蚂蚁经过边E(i,j)时，需要更新其信息素。信息素更新规则是：经过蚂蚁数量越多，该路径最优可能越大，则路径上信息浓度越大，该路径被选择的概率越大。同时，为防止算法陷入局部最优，信息素按照一定比例挥发。

μij(t)为时刻t边E(i,j)的信息素浓度，其初始值为Q，信息素在时间间隔Δt内更新规则如下：

(8)

式中：δ----信息素挥发因子;

μij(t)----Δt时间内信息素的增量。

(9)

(10)

式中：Q----初始信息素；

Cost(k)----蚂蚁k从源节点到当前节点所经过路径的费用函数。

式(10)表明，蚂蚁下一跳节点负载越小，费用函数值越低，则边E(i,j)信息素增量越大，如果负载大于平均负载，则信息素增量为负。这样，费用低、负载小的路径对其他蚂蚁的吸引作用变大，被选择的概率变大。

2.2.3信息素扩散

2.3ECRGQ算法实现步骤

本算法中蚂蚁分为前向蚂蚁和反向蚂蚁，前向蚂蚁AREQ(Ant Request)包含蚂蚁ID、服务级别、源节点ID、目的节点ID、上一节点ID、蚂蚁禁忌表tabu等信息；反向蚂蚁AREP(Ant Reply)包含蚂蚁ID、源节点ID、目的节点ID、上一节点ID等信息；节点信息表包含蚂蚁ID、上一节点ID、下一节点ID、源节点ID、目的节点ID、邻居节点ID、邻居节点剩余能量、邻居节点可用信道、邻居节点负载、Cost值等信息。

算法步骤如下：

1)初始化网络，设定算法迭代次数NC和算法初始信息素Q；

2)初始化禁忌表tabu，将m只蚂蚁放置到源节点上，将源节点添加到蚂蚁禁忌表tabu中，源节点广播前向蚂蚁给每个邻居节点；

3)根据式(6)，每个前向蚂蚁选择路径转移概率大的邻居节点作为下一节点，并切换到下一节点信道可用率高的信道上，发送前向蚂蚁，更新节点信息表，以便发送数据包时选择可用率高的信道；

4)前向蚂蚁到达一个节点，即将该节点放到tabu中，并根据式(9)对经过路径进行信息素更新。同时更新节点信息表，在上一节点ID中填入前向蚂蚁ID值；

5)重复步骤3)、4)，直到蚂蚁到达目的节点或不满足QoS条件限制；

6)所有前向蚂蚁到达目的节点后，反向蚂蚁沿前向蚂蚁所经过的路径返回源节点，建立多条路径，如果蚂蚁服务级别为高，根据式(9)对经过路径进行信息素更新，并更新节点信息表，在下一节点ID中填入反向蚂蚁上一节点ID值；

7)重复步骤3)～6)直到迭代次数超过NC，保存满足QoS要求的Cost(P)值小的若干条路径，选择Cost(P)值最小的路径传输数据。

由于中高速传感器网络节点能量有限和链路的拥塞，如果节点剩余能量与初始能量比Ej/Ej-init<20%，或处于拥塞状态，继续使用该链路，则其节能性能和时延性能反而下降。文中采用冗余路径策略，当最优路径有节点满足Ej/Ej-init<20%且不属于A类服务，或处于拥塞状态时，使用次优路径，从而增强路由的鲁棒性。

3仿真与分析

采用NS2进行仿真，仿真环境500 m×500 m，随机分布100个节点，随机选择网络边缘节点为sink节点，节点最大传输范围为200 m，数据包大小为512 B，发包率为5～30 包/s，迭代次数NC为100，蚂蚁数量50。路由QoS约束条件为最大时延30 ms，最大丢包率20%，最小带宽2 Mb/s。设置参数Q=2，δ=0.8，γ=1.1，α=1，β=1.2，Vt=1，θ=90，节点初始能量为1 J。

网络中存在多种服务时，ECRGQ算法对A、B、C三类服务的保证情况如图1所示。

图1　不同优先级服务时延

从图1可以看出，针对三类服务，优先级高的服务具有更好的时延性能。

不同发包率下，ECRGQ算法、AODV算法和文献[11]算法的实时性服务时延如图2所示。

图2　不同负载下时延

从图2可以看出，随着发包率的增加，3种算法的时延均有所增加，ECRGQ算法时延明显低于AODV算法和文献[11]算法，这是因为ECRGQ算法区分服务，在路径选择时，考虑节点负载，从而避开拥塞节点，且路径选择的同时，基于信道可用率进行信道选择，减少了时延。

网络生存周期是指仿真实验开始到网络中5%节点死亡的时间，如图3所示。

从图3可以看出，随着发包率的增加，ECRGQ算法、AODV算法和文献[11]算法的网络生存周期均出现下降，但ECRGQ算法在路径转移时考虑下一节点的能量、下一节点的距离和下一节点离sink节点的距离，故网络生存周期下降趋势不明显，因而，ECRGQ算法有更好的节能性能。

图3　不同负载下网络生存周期

4结语

提出一种无线传感网保证服务质量的节能跨层路由算法ECRGQ，对网络服务分级，在保障时延等服务质量要求的前提下，通过基于信道可用率算法解决MAC层时延问题,进行路由设计，对蚁群算法进行改进，在路径选择的将下一节点的剩余能量与初始能量比、节点发送能量、下一点负载和下一节点到sink节点距离作为状态转移概率和信息素更新的依据，并综合考虑链路的费用，在满足QoS需求的前提下，增加了算法的有效性和鲁棒性。仿真实验表明，该算法能够区分服务优先级，且时延、网络生存周期等性能指标比AODV算法和文献[11]算法更具优越性。

参考文献：

[1]Liu Hongtao, Cheng Lianglun. Priority-based service differentiation scheme for medium and high rate sensor networks[C]//2nd International Conference on Communication Software and Networks. Singapore: ICCSN,2010:392-395.

[2]Kim K.H, Shin K G. On accurate and asymmetry-Aware measurement of link quality in wireless mesh networks[J]. IEEE/ACM Transactions on Networking (TON),2009,17(4):1172-1185.

[3]Gulatimk， Kumar K. QoS routing protocols for mobile ad hoc networks：a survey[J]. International Journal of Wireless and Mobile Computing，2012,5(2)：107-118.

[4]Leelar, Thanulek Shmin, Selvakumars. Multi-constraint QoS unicast routing using genetic algorithm(MURU-GA)[J]. Applied Soft Computing,2011,11(2):1753-1761.

[5]张玺栋，康桂霞，张平，等.基于博弈的大规模无线传感器网络分簇算法[J].电子与信息学报,2011,33(10)：2516-2520.

[6]Sim K M， Sun W H. Ant colony optimization for routing and load balancing：survey and new directions[J]. IEEE Transactions on Systems，Man，and Cybermetics，Part A：Systems and Humans，2003，33(5)：560-572.

[7]Muhammad Saleem, Gianni A, Di Caro, et al. Swarm intelligence based routing protocol for wireless sensor networks:survery and future directions[J]. Information Sciences,2011,181(20):4597-4624.

[8]万博，卢昱，陈立云，等.基于改进蚁群算法的拥塞规避QoS路由算法[J].计算机工程,2011,37(20)：49-51.

[9]Lan Y, Wenjing W, Fuxiang G. A real-time and energy aware QoS routing protocol for multimedia wireless sensor networks[C]//World Congress on Intelligent Control and Automation(WCICA)，2008:3321-3326.

[10]高良诚．移动自组织网络Q学习和改进蚁群的QoS路由算法研究[J]．吉林大学学报:理学版，2015，53(3)：483-488.

[11]Camil O T, Careto C, Sil VA J, et al. An ennergy-efficient ant base rounting algorithm for wireless sensor networks[C]//ANTS 2009-Fifth International Workshop on Ant Colony Optymization and Swarm Intelligence，2009:49-59.

[12]蔡文郁.高数据率WSN节能策略与QoS机制研究[D].杭州:浙江大学,2007.

[13]TCI 8067 Spectrum Processor Data Specification[S/OL].(2009-06-08)[2015-12-14]. http://www.tcibr.com/ PDFs/8067webs.pdf.

[14]Kyasanur P， Vaidya N H． Protocol design challenges for multihop dynamic spectrum access networks[C]//2005 1st IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks． Bal-timore，MD，USA，2011：645-648.

[15]高良诚，刘杰．基于信道可用性的认知无线网络跨层路由协议[J]．安徽师范大学学报：自然科学版，2014，37(2)：134-138.

Energy saving cross-layer routing algorithm for guaranteeing QoS in wireless sensor Network

GAO Liangcheng,LIU Jie,LI Jianghua

(Department of Information Engineering， Tongling Vocational and Technical College， Tongling 244061， China)

Abstract：For the routing problems of guaranteeing QoS in Wireless Sensor Network(WSN), an energy saving cross-layer routing algorithm based on differentiated services and priority is put forward, in which the services are classified and then the residual energy, load and position of nodes are taken into account for path selection of ant colony algorithm. At same time，the channel with a lower switching probability is chosen. Simulation results show that the algorithm can improve the robustness of routing, reduce and balance energy consumption and is with optimal features such as low delay and long network lifespan under the conditions of premised guaranteed QoS.

Key words：Wireless Sensor Network(WSN)； Quality of Service(QoS)； energy saving； cross-layer； improved ant colony algorithm.

中图分类号：TP 393

文献标志码：A

文章编号：1674-1374(2016)01-0063-06

DOI:10.15923/j.cnki.cn22-1382/t.2016.1.13

作者简介：高良诚(1971-)，男，汉族，安徽枞阳人，铜陵职业技术学院副教授，硕士，主要从事认知无线网络和人工智能方向研究,E-mail:glc912@126.com.

基金项目：安徽省高校省级自然科学研究重点项目(KJ2016A713); 安徽省质量工程项目(2013tszy061)

收稿日期：2015-12-14