无线多媒体传感器网络能量均衡的QoS路由算法*

杨 冰 ，邓曙光 ，文双春

(1.湖南大学 信息科学与工程学院,湖南 长沙 410082;2.湖南城市学院 通信与电子工程学院，湖南 益阳 413000)

无线多媒体传感器网络能量均衡的QoS路由算法*

杨 冰1,2，邓曙光2，文双春1

(1.湖南大学 信息科学与工程学院,湖南 长沙 410082;2.湖南城市学院 通信与电子工程学院，湖南 益阳 413000)

为保障能量受限的无线多媒体传感器网络(WMSNs)多服务质量(QoS)需求，提出了一种能量均衡的QoS路由 (EBQR) 算法。该算法通过蚁群优化将网络带宽、时延、丢包率和能量等因素作为目标函数，并根据函数值大小动态调整蚁群信息素的挥发系数和浓度增量，提供网络业务中满足不同QoS需求的最优路径。仿真结果表明：与AntWMSNs算法和ASAR算法相比，EBQR算法平均端到端时延降低了16 %，丢包率减少22 %，生命周期延长了近50 %，有效实现了网络中节点能耗的均衡性。

无线多媒体传感器网络； 能量均衡； 服务质量路由； 蚁群算法

0 引 言

随着传感器技术和无线通信技术的不断发展，无线传感器网络(wireless sensor networks，WSNs)以其自组织、低成本等特点被广泛应用于社会各种活动中[1，2]。监测环境日趋复杂多变，对监测数据的要求越来越高,为了实现细粒度、精准信息的监测，人们将具有音频、视频、图像等多媒体信息感知功能的新型传感器节点引入到传感器网络中[3，4]，由此催生了无线多媒体传感器网络(wireless multimedia sensor networks,WMSNs)。网络服务质量(quality of service,QoS)是网络提供给应用或用户服务性能的一种测量[5]。传统的QoS路由算法不能直接适用于WMSNs，因为它具有能量等资源有限和对QoS的要求比较高等特点。WMSNs的QoS要求，包括可用性、吞吐量、时延、时延抖动、丢包率、能耗等参数[6，7]。

针对WMSNs的特点，国内外对QoS路由问题开展了大量研究[8～10],这些研究主要集中在实时性、可靠性或能量约束等方面。例如:文献[8]提出了一种基于能量感知的可靠路由机制，充分考虑节点的剩余能量和路径的可靠性，选择相应的路径，从而提高可靠性和降低能耗；文献[9]提出了一种保证实时性的路由协议，通过考虑转播速率和剩余能量来降低平均时延和延长网络生命周期；文献[10]提出了角度区分服务的路由机制，根据实时和非实时数据进行相应处理，满足其需求并有效均衡能量消耗。此外，也有一些针对多QoS约束条件路由问题的研究,例如:通过综合考虑路径的带宽、时延、丢包率和能耗等方面之间的均衡问题，在满足这些需求的同时尽量减少网络能耗延长网络生命周期[11～13]。从如上所述的研究来看，在能量消耗方面，存在某些关键节点被频繁使用而过早死亡或为避开能量过低节点而导致总能耗增大等问题。文献[14]利用能量因数有效解决了最小化路由通信所消耗总能量和最大化网络生命周期的问题。本文基于能量因数这一思想，提出一种能量均衡的QoS路由(EBQR)算法，该算法既满足网络对带宽、时延、丢包率、时延抖动、能耗的QoS需求，同时又能均衡网络中节点的能耗，并有效降低数据传输的总能耗。

1 WMSNs中EBQR模型

WMSNs可抽象为一个赋权图G=(V,E)，其中，V为网络的中节点集合，V={v1,v2,…,vn}，E为网络中节点间通信的链路集，E={e1,e2,…,em}。对于任意链路e∈E，有e=(vi,vj)，vi∈V,vj∈V,i≠j。每条链路具有(bandwidth(eij)，delay(eij)，jitter(eij)，loss(eij))4个属性的QoS特征值，分别表示节点vi到节点vj的带宽、时延、时延抖动、丢包率。每个节点具有能量energy(vi)的特征。

QoS路由选择是在图G=(V,E)中寻找到一条从源节点到目的节点满足QoS约束条件的路径P=(vs,…,vd),约束关系如下：

1)条件1:带宽约束

BP=min{bandwidth(eij)}≥Bmin,∀vi,vj∈P,

(1)

式中Bmin为路径上要求的最小带宽。

2)条件2:时延约束

DP=∑delay(eij)≤Dmax, ∀vi,vj∈P,

(2)

式中Dmax为路径上要求的最大时延和。

3)条件3:时延抖动约束

JP=∑jitter(eij)≤Jmax,∀vi,vj∈P,

(3)

式中Jmax为路径上要求的最大时延抖动和。

4)条件4:时延抖动约束

LP=1-∏(1-loss(eij))≤Lmax,∀vi,vj∈P,

(4)

式中Lmax为路径上允许的最大丢包率。

5)条件5:能量约束

EnP=energy(vi)≥Enmin,∀vi∈P,

(5)

式中Enmin为路径上每个节点要求的最小能量。

6)条件6:目标函数

(6)

式中α,β,γ,δ,φ分别为带宽、时延、时延抖动、丢包率和能量的比重系数，α+β+γ+δ+φ=1，EF为能量因数

(7)

式中IE为节点的初始能量，M为量化级。

本文的目标是在满足条件1～条件5的情况下使得F值最小。

2 EBQR算法描述

蚁群算法[15～17]是一种模拟蚂蚁群体觅食行为的仿生优化算法，采用正反馈并行催化机制，具有较强的鲁棒性、优良的分布式计算机功能以及易于与其他启发算法结合等优点，在诸多领域已得到广泛应用。WMSNs中信息的动态性、随机性、异步性等特点与蚁群算法中的蚂蚁移动非常相似，因此，利用蚁群算法来解决WMSNs中的复杂问题具有重要意义。本文根据目标函数值的大小动态调整信息素挥发系数和信息素浓度增量，寻找满足QoS约束条件的最佳路由。

WMSNs中的每个节点都执行同样的路由选择算法，从源节点向目的节点周期性地发送蚂蚁，并根据QoS需求找到满足条件的路径。

步骤1：初始化参数，产生前向蚂蚁。

步骤2：当前向蚂蚁到达节点i时，先判断该节点是中间节点还是目的节点，同时判断是否满足QoS约束指标中的条件。若为中间节点且满足QoS约束指标，则按式(8)选择转移概率大的邻居节点j作为蚂蚁移动的下一个节点，重复步骤(2)

(8)

(9)

若为中间节点且不满足QoS约束指标，则执行步骤(3)，若为目的节点，则执行步骤(4)。

步骤3：停止转发前向蚂蚁，在节点i处产生一个后向蚂蚁，按式(10)更新前向蚂蚁所走过路径上的信息素

τij(t+1)=(1-ρ1)τij(t).

(10)

重复执行步骤(3)，直到到达源节点，执行步骤(5)。

步骤4：当前向蚂蚁到达目的节点时，判断是否满足QoS约束指标，并按式(6)计算目标函数F，丢弃前向蚂蚁并产生后向蚂蚁，根据目标函数值F的大小按式(11)或式(13)更新前向蚂蚁所走路径上的信息素浓度，直到到达源节点

τij(t+1)=(1-ρ0)τij(t)+Δτij(t),

(11)

Δτij(t)=Q1/F.

(12)

当目标函数F的最小值在连续n次的迭代过程中均无变化时

τij(t+1)=(1-ρ2)τij(t)+Δτij(t),

(13)

Δτij(t)+Q2/F.

(14)

步骤5：当源节点收到返回的后向蚂蚁，信息素被更新，同时丢弃该蚂蚁。转到步骤(2)反复执行直到到达设定的迭代次数，算法终止，输出目标函数值最小的路径。

3 仿真与分析

为验证本文所提算法的有效性，建立仿真环境进行验证分析。假设在200 m×200 m的区域里随机部署100个无线传感器节点(包括Sink节点)，Sink的位置固定于(0,0)m，该节点的能量不受限制(在处理过程中忽略该点的能量消耗问题)。设定其他节点的初始能量为15 J，发送数据和接收数据能耗为50 nJ/bit，通信半径为70 m，网络带宽为[1,10]Mbps之间的随机数，链路之间的时延为[10,20] ms之间的随机数，链路之间的丢包率为[0,0.045]之间的随机数。同时假设QoS需求为Bmin=2 Mbps，Dmax=100 ms，Lmax=0.15，Enmin=0.2 J，取α=0.1，β=0.4，γ=0，δ=0.4，φ=0.1。

在上述环境下，对本文提出的EBQR算法和文献[12,13]的算法进行仿真，分别从平均传输时延、平均丢包率、平均能量消耗以及网络生命周期4个方面进行性能比较。其中，平均传输时延为不同测试时间段源节点传送有效数据包到汇聚节点所用的平均时间。丢包率为源节点传送有效数据包到汇聚节点丢失数据包的数量所占发送数据包的比率。平均能量消耗为每个测量时刻源节点发送一个有效数据包到汇聚节点所消耗能量的平均值。网络生命周期为网络中第一个节点能量消耗到小于最小能量时所用的时间。

经仿真测试，平均传输时延、平均丢包率和平均能量消耗分别如图1～图3所示，3种算法的网络生命周期比较如表1所示。与AntWMSNs算法和ASAR算法相比，由于EBQR算法的目标函数中考虑了带宽、时延、丢包率和能耗，在中间节点的转移概率选择时也考虑这些因素，并根据每次所得的目标函数值产生不同的挥发系数；同时，通过选取具有较高能量节点为通信节点，并选取整体能耗较小的路径为传输路径。由此寻找到的路径性能值更好，传输数据时延、丢包率和能耗小。而ASAR算法在目标函数中虽考虑了带宽、时延、丢包和能耗因素，但每个周期里所寻找的路径很容易集中经过某个节点，从而导致该节点能量快速消耗殆尽。AntWMSNs算法在路径选择时通过比较节点的剩余能量，选择剩余能量较大的节点作为下跳节点，但目标函数中丢包率和时延使用的是固定值，故寻找到的路径时延和丢包率仍相对较大，测试结果证实了这点。由图可知，EBQR算法的平均时延比ASAR算法低16.48 %，比AntWMSNs算法低18.89 %。EBQR算法的丢包率比ASAR算法和AntWMSN算法分别低23.22 %，22.83 %。EBQR算法的能耗比ASAR算法和AntWMSNs算法分别少1.912 5×10-4J,2.833 8×10-4J。EBQR算法的生命周期比ASAR算法和AntWMSNs算法分别延长了59 %和42.08 %。

图1 平均传输时延Fig 1 Average transmission delay

图2 平均丢包率Fig 2 Average packet loss rate

图3 平均能量消耗Fig 3 Average energy consumption

算法本文算法ASAR算法AntWMSNs算法网络生命周期(s)1175739827

4 结 论

在能量资源受限的WMSNs中，为满足不同业务需求并充分考虑能量的高效使用，本文提出了一种EBQR算法。该算法将网络带宽、时延、丢包率和能量等因素作为目标函数，利用蚁群根据目标函数值的大小来动态调整信息素的挥发系数和信息素浓度增量，查找满足不同QoS需求业务的最优路径。仿真表明：与AntWMSNs算法和ASAR算法相比，EBQR算法平均端到端时延降低了16 %，丢包率减少22 %，生命周期延长了近50 %，有效实现了网络中节点能耗的均衡性。

[1] 陈志泊,徐孝成.一种改进的基于跳数的无线传感器网络路由算法[J].计算机科学,2013,40(4):83-85,114.

[2] Wang L,Ye W,Wang H,et al.Optimal node placement of industrial wireless sensor networks based onadaptive mutation probabi-lity binary particle swarm optimization algorithm[J].Computer Science and Information Systems,2012,9(4):1553-1576.

[3] 周 灵,王建新.无线多媒体传感器网络路由协议研究[J].电子学报,2011,39(11):149-156.

[4] 孙 岩,马华东.无线多媒体传感器网络QoS保障问题[J].电子学报,2008,36(7):1412-1420.

[5] 段文轩.无线多媒体传感器网络服务质量的研究[D].泉州:华侨大学,2012:1-4.

[6] Cobo Luis,Quintero Alejandro,Pierre Samuel.Ant-based routing for wireless multimedia sensor networks using multiple QoS me-trics[J].Computer Networks, 2010, 54(17): 2991-3010.

[7] Kandris Dionisis,Tsagkaropoulos Michail,Politis Ilias,et al.Energy efficient and perceived QoS aware video routing over wireless multimedia sensor networks[J].Ad Hoc Networks,2011,9(4):591-607.

[8] 李 雪,贺昱曜,武奇生.一种WMSNs能量感知QoS路由机制设计[J].计算机工程与应用,2011,47(18):76-79.

[9] 黄 曼,程良伦.一种QoS保证的WMSNs实时路由协议[J].传感器技术学报,2011,24(9):1341-1346.

[10] 李方敏,方艺霖,李 姮,等.无线多媒体传感器网络QoS区分服务路由机制[J].电子学报,2010,38(10):2322-2328.

[11] 孙 岩,马华东,刘 亮.一种基于蚁群优化的多媒体传感器网络服务感知路由算法[J].电子学报,2007,35(4):705-711.

[12] 谢 慧,吴晓平,张用宇,等.多媒体传感器网络中基于ACO的QoS路由协议[J].海军工程大学学报,2009,21(6):15-19.

[13] Yu Xiaohua,Luo Jiaxing,Huang Jinwen.An ant colony optimization-based QoS routing algorithm for wireless multimedia sensor networks[C]∥Int’l Conf on Communication Software and Networks(ICCSN),2011:37-41.

[14] 胡耀锋,张建明,王新胜,等.能量感知的无线传感器网络多路径路由研究[J].计算机工程与设计,2009,30(21):4811- 4814,4827.

[15] 吴华锋,陈信强,毛奇凰,等.基于自然选择策略的蚁群算法求解TSP问题[J].通信学报,2013,34(4):165-170.

[16] 周明秀,程 科,汪正霞.动态路径规划中的改进蚁群算法[J].计算机科学,2013,40(1):314-316.

[17] 高 曼,刘以安,张 强.优化蚁群算法在反舰导弹航路规划中的应用[J].计算机应用,2012,32(9):2530-2533,2541.

Energy-balanced QoS routing algorithms for WMSNs*

YANG Bing1,2, DENG Shu-guang2, WEN Shuang-chun1

(1.College of Information Science and Engineering,Hunan University,Changsha 410082,China;2.School of Communication and Electronic Engineering,Hunan City University,Yiyang 413000,China)

To guarantee demand of energy-constrained wireless multimedia sensor networks(WMSNs)multi-QoS,a kind of energy-balanced QoS routing(EBQR)algorithm is proposed.The algorithm through ant colony optimization to make the network bandwidth,time delay,packet loss rate and energy as objective function,and according to function value size dynamically adjust volatility coefficient and density increments of ant colony information element,provide the optimal path to meet different QoS needs in network businesses.Simulation results show that, compare with the AntWMSNs algorithm and the ASAR algorithm,average end-to-end time delay of EBQR algorithm is reduced 16 %,the packet loss rate is reduced 22 %,the life cycle lengthened nearly 50 %,effectively realize equilibrium of node energy consumption in the network.

wireless multimedia sensor networks(WMSNs); energy-balanced; quality of serivce(QoS) routing; ant colony algorithm

2013—08—15

湖南省科技计划资助项目(2012FJ3025)； 湖南省教育厅科研基金资助项目(12C0585)

TP 212

A

1000—9787(2014)04—0122—03

杨 冰(1981-)，女，湖南益阳人，硕士研究生，讲师，研究方向为车域自组网和无线传感器网络理论与优化。