周 灵，龙 滩，王建新

(1. 佛山科学技术学院 计算机系，广东 佛山 528000；2. 中南大学 信息科学与工程学院, 湖南 长沙 410083)

无线多媒体传感器网络(Wireless Multimedia Sensor Networks, WMSNs)将信息量大、内容丰富的图像、音频和视频等多媒体信息引入到环境监测活动中，实现了全方位、细粒度、精确的信息监测。作为一个无线多跳多媒体通信网络，由于多媒体数据传输量大，节能问题尤为突出，如何最小化能耗并延长网络生存期是一个重要的挑战。同时，多媒体通信网络还具有很强的服务质量(Quality of Server, QoS)控制要求，比如提供实时通信。最后，由于WMSNs独特的音频、视频、图像等多媒体数据流模型，其数据处理、网络通信也比传统的无线传感器网络(Wireless Sensor Networks, WSNs)有更高的要求[1-2]。

由于多媒体应用数据服务种类众多，本文只考虑有QoS控制要求的多媒体数据路由通信问题。对于这种类型的通信，其QoS控制路由算法必须保障：① 从WMSNs通信服务质量方面考虑，要求路由具有QoS保障，典型的是满足一定的时延要求的实时通信；② 从网络资源管理和优化的角度考虑，要求优化网络资源管理，主要是最小化网络代价；典型的是最小化网络能耗，最大化网络生存期，延长监测网络的寿命。要同时对两者进行优化，即QoS控制的最小能耗路由问题。

本文引入一个优秀的最小代价启发式算法ADH(Average Distance Heuristic)[3]，将其扩展到时延受限的最小能耗实时路由领域，设计了一个时延约束的最小能耗实时路由算法LERTR(Least Energy Real-time Routing Algorithm)。该算法首先考虑数据融合路由树的能量消耗最优化；若某路径时延超过约束条件，则启动最小时延路径计算，用最小时延路径代替该路径。最后通过仿真实验与两个典型的算法SPEED、Kemal进行了性能比较。

1 QoS路由与数据融合

定义1 WMSNs最小能耗路由问题：给定网络G(V,E)、汇聚节点D和信号源结点集S，求解一棵覆盖S∪D的生成树T，使得树T的能耗代价满足式：

称这个问题为WMSNs最小能耗路由问题。这个问题的解T为S∪G的最小能耗树(Least-Energy Tree，简称LET)。

定义2 时延约束的WMSNs最小能耗路由问题：给定网络G(V,E)、汇聚节点D、信号源结点集S和时延上限Δdelay，求解一棵覆盖S∪D的生成树T，使得树T的能耗代价和时延满足式：

s.t.Delay(P(s,v))≤ΔDelay

(∀v∈D,P(s,v)∈T)

称这个问题为时延约束的WMSNs最小能耗路由问题。这个问题的解T为S∪D的时延约束最小能耗树，即时延约束的Steiner树。

根据WMSNs通信能耗模型可知[4]：Econsumption=βkd2，即能耗主要与两个因素有关：无线通信距离d和数据传输量k。可以利用网内数据处理技术，即数据融合技术，进行网内数据处理，去除冗余信息，从而有效地节省能量消耗，起到延长网络寿命的作用[5-6]。

定义3 数据融合(Data Aggregation or Data Fusion)：指在数据采集、处理、传输过程中，将多份数据进行合并从而得到更有效、更符合需求的数据处理策略。

在WMSNs中，路由主要是众多的多媒体传感器节点对汇聚节点的数据转发以及管理节点对监测区域众多传感器节点的数据查询，其特点是多对一(nto 1)或者一对多(1 ton)的通信。因此，其QoS路由的本质是构造一棵以汇聚节点为根的数据转发树。如果和传统数据路由的一对多(1 ton)特性相比较，容易发现，基于数据融合的数据转发树是一棵反向组播树。因此，QoS路由的目的主要是进行数据融合树的构建，即反向组播树的构建。

2 LERTR算法设计

文献[3]对最小代价树算法作了客观的评价。经典的三个算法是KMB算法、MPH算法、ADH算法。KMB算法是由Kou等人提出的求解Steiner树算法，其复杂度为O(m×n2)，在DCLC问题研究中，最早被扩展为解决DCLC问题的著名KPP算法； MPH算法复杂度是O(mn2)，但通常情况下生成树的费用要小于KMB生成树的费用；已经被扩展为DCMPH算法来解决DCLC问题。ADH是一个经典的求解Steiner树问题的启发式算法，具有很好的代价性能，其计算复杂度为O(n3)。

LERTR算法的基本思想：先利用ADH算法低代价的特性，计算一棵低代价的路由树T；若T不满足时延约束Δ，则通过Dijkstra最短路径树算法，以时延作为测度计算最小时延路径树TDelay，并通过合并最小时延路径，得到一棵满足特定时延约束的低代价路由树。由于合并路径时树可能出现环路，引入了消环过程。和近期同类算法相比，LERTR算法偏重于提高算法的代价性能，同时满足较严格的时延约束，因而具有较好的QoS控制性能[7-8]。

具体地，其算法过程描述如下：

步骤1：运用Dijkstra 最短路径树算法，以D为根计算到所有信息源结点m的最小时延树TDelay，判断是否存在满足时延Δ的树，若delay(·)>Δ，退出。

步骤2：置T的初始集合为属于S集合的分离节点集，k=m。

步骤3：计算f(v) = min{d(v,Vi)+d(v,Vj)|Vi,Vj为任意两棵分离的树的节点集}，对于v∈V，若f(v)最小，则通过v将Ti和Tj连接起来，其连接路径为P(v,Vi)和P(v,Vj)。

步骤4：修改集合T和节点集，k=k-1。

步骤5：重复步骤3、4，直到k= 1，完成ADH树的计算。

步骤6：判断时延约束。对∀n∈S，若delay(·)>Δ，将路径Path(n,G)∈TDelay加入T；若形成环路，启用消环过程，改变其父结点。

步骤7：重复步骤6，直到全部目的结点都满足时延约束。

算法伪代码描述如下：

Input:G(V,E, Cost, Delay),D,S,Δ

Output: A delay-constrained Steiner treeT

DCMPH(Graph,G,S,D,Δ)

1)TDelay← Dijkstra(G,D,S,Δ)

2)If Delay(TDelay) >Δthen return Null

3)Q←S/*Q为信号源节点队列

4)T←D/* 初始化路由树T

5) Computing the routing treeTby ADH algorithm for all the nodei∈Q

6)For eachmiinQ

7)If 信号源mi到树T时延小于Δthen

8)T←T∪{mi到在树T中的低能耗路径}

9)Else

10)T←T∪{mi在树TDelay中到汇聚节点D的最小时延路径}

11)If there exists a loop then removing Loop

12)End If-else

13)End for

14)ReturnT

3 仿真实验

根据无线传感器网络随机仿真模型来验证LERTR算法的正确性和有效性[9-10]。无线结点分布在100 m×100 m的矩形区域随机产生网络拓扑图，无线节点通信半径假定为R=12 m。时延上限设为较小的值0.04 s和0.06 s，与实际情况比较接近。仿真时进行数据融合，在每个无线链路上传送单位数据量大小的数据包。具体的仿真参数见表1。

实验时，每个数据测量点对10个随机网络拓扑进行测试，每个网络测量100次，共计1 000次，取其平均值作为测量值；同时，与两个典型的算法SPEED[11]、Kemal[4]进行能耗代价及时延性能比较。

表1 仿真参数表 Table 1 The simulation parameters

实验一：测量生成树能耗代价和网络规模的关系。保持信号源节点20个不变，网络结点规模数由100个开始，每次增加50个，结果如图1所示，其中图1 (a) 、(b)分别为Δ=0.06 s和Δ=0.04 s时的仿真结果图。可见，LERTR生成树与SPEED、Kemal相比均有更好的代价性能，这得益于ADH是一个优秀的低代价树生成算法。实验数据曲线变化缓慢，网络规模对生成树代价影响不大。当时延约束由0.06 s变为0.04 s时，LERTR算法与SPEED、Kemal算法相比，代价差异性显著增大；LERTR算法相对Kemal算法性能更好。

图1 能耗代价和网络规模关系图Fig.1 The relation of energy consumption and network node number

实验二：测量生成树能耗代价和信号源节点数目的关系。固定网络规模200个结点不变，信号源节点由20到80，每次增加10个。实验结果如图2所示，其中图2 (a) 、(b)分别为Δ=0.06 s和Δ=0.04 s时的仿真结果图。仿真结果表明：随着信号源结点的增加，能耗代价快速增加，可见能耗代价主要与信号源节点数目相关。仿真结果的能耗分析及时延分析同实验一。

图2 能耗代价和信号源节点数目关系图Fig.2 The relation of energy consumption and source node number

4 总 结

针对WMSNs，基于数据融合在ADH算法基础上设计了LERTR算法，用于构造最小能耗实时路由通信树。该算法首先使用ADH生成一棵最小能耗树；若时延不能满足特定的实时要求，则通过合并最小时延路径来产生一个满足时延约束的最小能耗树。仿真实验表明：LERTR算法生成的路由树在保障时延要求的情况下，具有很好的能耗代价性能。根据LERTR算法求解最小能耗实时路由问题，能高效地取得这个NP-Complete问题的较优解。

参考文献：

[1] IAN F A, TOMMASO M, KAUSHIK R C. A survey on wireless multimedia sensor networks[J]. Computer Networks, 2007, 51(4): 921-960.

[2] 马华东, 陶 丹. 多媒体传感器网络及其研究进展[J]. 软件学报, 2006, 17(9): 2013-2028.

[3] 余燕平, 仇佩亮. 一种改进的Steiner树算法[J]. 通信学报, 2002, 23(11): 35-40.

[4] KEMAL A, YOUNIS M. An energy-aware QoS routing protocol for wireless sensor networks[C]∥ Proceeding of International Conference on Distributed Computing Systems, IEEE Computer Society, 2003: 710-718.

[5] EDUARDO F N, ANTONIO A F L, ALEJANDRO C F. Information fusion for wireless sensor networks: methods, models, and classifications[J]. ACM Computing Surveys, 2007, 39(3):1-55.

[6] 周灵, 王建新. 无线多媒体传感器网络服务质量控制路由协议研究[J]. 电子学报, 2011, 39(1): 149-156.

[7] LIANG W, LIU Y. Online data gathering for maximizing network lifetime in sensor networks[J]. IEEE Transactions on Mobile Computing, 2007, 6 (1): 2 -11.

[8] 汪华斌, 罗中良. 基于功率控制AODV路由协议研究[J]. 中山大学学报:自然科学版, 2011, 50(5): 59-63.

[9] PETER K K L, HSU W J, YI P. Performance evaluation of efficient and reliable routing protocols for fixed-power sensor networks[J]. IEEE Transaction on Wireless Communications, 2009, 8(5): 328-2335.

[10] MIN C, VICTOR C M L, MAO S W, et al. Directional geographical routing for real-time video communications in wireless sensor networks[J]. Computer Communications, 2007, 30(17): 3368-3383.

[11] TIAN H, JOHN A, LU C, et al. SPEED: A stateless protocol for real-time communication in sensor networks[C]∥ Proceeding of International Conference on Distributed Computing System, IEEE Computer Society, 2003: 204-223.