周 靈，龍 灘，王建新

(1. 佛山科學(xué)技術(shù)學(xué)院 計算機系，廣東 佛山 528000；2. 中南大學(xué) 信息科學(xué)與工程學(xué)院, 湖南 長沙 410083)

無線多媒體傳感器網(wǎng)絡(luò)(Wireless Multimedia Sensor Networks, WMSNs)將信息量大、內(nèi)容豐富的圖像、音頻和視頻等多媒體信息引入到環(huán)境監(jiān)測活動中，實現(xiàn)了全方位、細粒度、精確的信息監(jiān)測。作為一個無線多跳多媒體通信網(wǎng)絡(luò)，由于多媒體數(shù)據(jù)傳輸量大，節(jié)能問題尤為突出，如何最小化能耗并延長網(wǎng)絡(luò)生存期是一個重要的挑戰(zhàn)。同時，多媒體通信網(wǎng)絡(luò)還具有很強的服務(wù)質(zhì)量(Quality of Server, QoS)控制要求，比如提供實時通信。最后，由于WMSNs獨特的音頻、視頻、圖像等多媒體數(shù)據(jù)流模型，其數(shù)據(jù)處理、網(wǎng)絡(luò)通信也比傳統(tǒng)的無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks, WSNs)有更高的要求[1-2]。

由于多媒體應(yīng)用數(shù)據(jù)服務(wù)種類眾多，本文只考慮有QoS控制要求的多媒體數(shù)據(jù)路由通信問題。對于這種類型的通信，其QoS控制路由算法必須保障：① 從WMSNs通信服務(wù)質(zhì)量方面考慮，要求路由具有QoS保障，典型的是滿足一定的時延要求的實時通信；② 從網(wǎng)絡(luò)資源管理和優(yōu)化的角度考慮，要求優(yōu)化網(wǎng)絡(luò)資源管理，主要是最小化網(wǎng)絡(luò)代價；典型的是最小化網(wǎng)絡(luò)能耗，最大化網(wǎng)絡(luò)生存期，延長監(jiān)測網(wǎng)絡(luò)的壽命。要同時對兩者進行優(yōu)化，即QoS控制的最小能耗路由問題。

本文引入一個優(yōu)秀的最小代價啟發(fā)式算法ADH(Average Distance Heuristic)[3]，將其擴展到時延受限的最小能耗實時路由領(lǐng)域，設(shè)計了一個時延約束的最小能耗實時路由算法LERTR(Least Energy Real-time Routing Algorithm)。該算法首先考慮數(shù)據(jù)融合路由樹的能量消耗最優(yōu)化；若某路徑時延超過約束條件，則啟動最小時延路徑計算，用最小時延路徑代替該路徑。最后通過仿真實驗與兩個典型的算法SPEED、Kemal進行了性能比較。

1 QoS路由與數(shù)據(jù)融合

定義1 WMSNs最小能耗路由問題：給定網(wǎng)絡(luò)G(V,E)、匯聚節(jié)點D和信號源結(jié)點集S，求解一棵覆蓋S∪D的生成樹T，使得樹T的能耗代價滿足式：

稱這個問題為WMSNs最小能耗路由問題。這個問題的解T為S∪G的最小能耗樹(Least-Energy Tree，簡稱LET)。

定義2 時延約束的WMSNs最小能耗路由問題：給定網(wǎng)絡(luò)G(V,E)、匯聚節(jié)點D、信號源結(jié)點集S和時延上限Δdelay，求解一棵覆蓋S∪D的生成樹T，使得樹T的能耗代價和時延滿足式：

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

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

稱這個問題為時延約束的WMSNs最小能耗路由問題。這個問題的解T為S∪D的時延約束最小能耗樹，即時延約束的Steiner樹。

根據(jù)WMSNs通信能耗模型可知[4]：Econsumption=βkd2，即能耗主要與兩個因素有關(guān)：無線通信距離d和數(shù)據(jù)傳輸量k?？梢岳镁W(wǎng)內(nèi)數(shù)據(jù)處理技術(shù)，即數(shù)據(jù)融合技術(shù)，進行網(wǎng)內(nèi)數(shù)據(jù)處理，去除冗余信息，從而有效地節(jié)省能量消耗，起到延長網(wǎng)絡(luò)壽命的作用[5-6]。

定義3 數(shù)據(jù)融合(Data Aggregation or Data Fusion)：指在數(shù)據(jù)采集、處理、傳輸過程中，將多份數(shù)據(jù)進行合并從而得到更有效、更符合需求的數(shù)據(jù)處理策略。

在WMSNs中，路由主要是眾多的多媒體傳感器節(jié)點對匯聚節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)以及管理節(jié)點對監(jiān)測區(qū)域眾多傳感器節(jié)點的數(shù)據(jù)查詢，其特點是多對一(nto 1)或者一對多(1 ton)的通信。因此，其QoS路由的本質(zhì)是構(gòu)造一棵以匯聚節(jié)點為根的數(shù)據(jù)轉(zhuǎn)發(fā)樹。如果和傳統(tǒng)數(shù)據(jù)路由的一對多(1 ton)特性相比較，容易發(fā)現(xiàn)，基于數(shù)據(jù)融合的數(shù)據(jù)轉(zhuǎn)發(fā)樹是一棵反向組播樹。因此，QoS路由的目的主要是進行數(shù)據(jù)融合樹的構(gòu)建，即反向組播樹的構(gòu)建。

2 LERTR算法設(shè)計

文獻[3]對最小代價樹算法作了客觀的評價。經(jīng)典的三個算法是KMB算法、MPH算法、ADH算法。KMB算法是由Kou等人提出的求解Steiner樹算法，其復(fù)雜度為O(m×n2)，在DCLC問題研究中，最早被擴展為解決DCLC問題的著名KPP算法； MPH算法復(fù)雜度是O(mn2)，但通常情況下生成樹的費用要小于KMB生成樹的費用；已經(jīng)被擴展為DCMPH算法來解決DCLC問題。ADH是一個經(jīng)典的求解Steiner樹問題的啟發(fā)式算法，具有很好的代價性能，其計算復(fù)雜度為O(n3)。

LERTR算法的基本思想：先利用ADH算法低代價的特性，計算一棵低代價的路由樹T；若T不滿足時延約束Δ，則通過Dijkstra最短路徑樹算法，以時延作為測度計算最小時延路徑樹TDelay，并通過合并最小時延路徑，得到一棵滿足特定時延約束的低代價路由樹。由于合并路徑時樹可能出現(xiàn)環(huán)路，引入了消環(huán)過程。和近期同類算法相比，LERTR算法偏重于提高算法的代價性能，同時滿足較嚴格的時延約束，因而具有較好的QoS控制性能[7-8]。

具體地，其算法過程描述如下：

步驟1：運用Dijkstra 最短路徑樹算法，以D為根計算到所有信息源結(jié)點m的最小時延樹TDelay，判斷是否存在滿足時延Δ的樹，若delay(·)>Δ，退出。

步驟2：置T的初始集合為屬于S集合的分離節(jié)點集，k=m。

步驟3：計算f(v) = min{d(v,Vi)+d(v,Vj)|Vi,Vj為任意兩棵分離的樹的節(jié)點集}，對于v∈V，若f(v)最小，則通過v將Ti和Tj連接起來，其連接路徑為P(v,Vi)和P(v,Vj)。

步驟4：修改集合T和節(jié)點集，k=k-1。

步驟5：重復(fù)步驟3、4，直到k= 1，完成ADH樹的計算。

步驟6：判斷時延約束。對?n∈S，若delay(·)>Δ，將路徑Path(n,G)∈TDelay加入T；若形成環(huán)路，啟用消環(huán)過程，改變其父結(jié)點。

步驟7：重復(fù)步驟6，直到全部目的結(jié)點都滿足時延約束。

算法偽代碼描述如下：

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為信號源節(jié)點隊列

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中到匯聚節(jié)點D的最小時延路徑}

11)If there exists a loop then removing Loop

12)End If-else

13)End for

14)ReturnT

3 仿真實驗

根據(jù)無線傳感器網(wǎng)絡(luò)隨機仿真模型來驗證LERTR算法的正確性和有效性[9-10]。無線結(jié)點分布在100 m×100 m的矩形區(qū)域隨機產(chǎn)生網(wǎng)絡(luò)拓撲圖，無線節(jié)點通信半徑假定為R=12 m。時延上限設(shè)為較小的值0.04 s和0.06 s，與實際情況比較接近。仿真時進行數(shù)據(jù)融合，在每個無線鏈路上傳送單位數(shù)據(jù)量大小的數(shù)據(jù)包。具體的仿真參數(shù)見表1。

實驗時，每個數(shù)據(jù)測量點對10個隨機網(wǎng)絡(luò)拓撲進行測試，每個網(wǎng)絡(luò)測量100次，共計1 000次，取其平均值作為測量值；同時，與兩個典型的算法SPEED[11]、Kemal[4]進行能耗代價及時延性能比較。

表1 仿真參數(shù)表 Table 1 The simulation parameters

實驗一：測量生成樹能耗代價和網(wǎng)絡(luò)規(guī)模的關(guān)系。保持信號源節(jié)點20個不變，網(wǎng)絡(luò)結(jié)點規(guī)模數(shù)由100個開始，每次增加50個，結(jié)果如圖1所示，其中圖1 (a) 、(b)分別為Δ=0.06 s和Δ=0.04 s時的仿真結(jié)果圖。可見，LERTR生成樹與SPEED、Kemal相比均有更好的代價性能，這得益于ADH是一個優(yōu)秀的低代價樹生成算法。實驗數(shù)據(jù)曲線變化緩慢，網(wǎng)絡(luò)規(guī)模對生成樹代價影響不大。當時延約束由0.06 s變?yōu)?.04 s時，LERTR算法與SPEED、Kemal算法相比，代價差異性顯著增大；LERTR算法相對Kemal算法性能更好。

圖1 能耗代價和網(wǎng)絡(luò)規(guī)模關(guān)系圖Fig.1 The relation of energy consumption and network node number

實驗二：測量生成樹能耗代價和信號源節(jié)點數(shù)目的關(guān)系。固定網(wǎng)絡(luò)規(guī)模200個結(jié)點不變，信號源節(jié)點由20到80，每次增加10個。實驗結(jié)果如圖2所示，其中圖2 (a) 、(b)分別為Δ=0.06 s和Δ=0.04 s時的仿真結(jié)果圖。仿真結(jié)果表明：隨著信號源結(jié)點的增加，能耗代價快速增加，可見能耗代價主要與信號源節(jié)點數(shù)目相關(guān)。仿真結(jié)果的能耗分析及時延分析同實驗一。

圖2 能耗代價和信號源節(jié)點數(shù)目關(guān)系圖Fig.2 The relation of energy consumption and source node number

4 總 結(jié)

針對WMSNs，基于數(shù)據(jù)融合在ADH算法基礎(chǔ)上設(shè)計了LERTR算法，用于構(gòu)造最小能耗實時路由通信樹。該算法首先使用ADH生成一棵最小能耗樹；若時延不能滿足特定的實時要求，則通過合并最小時延路徑來產(chǎn)生一個滿足時延約束的最小能耗樹。仿真實驗表明：LERTR算法生成的路由樹在保障時延要求的情況下，具有很好的能耗代價性能。根據(jù)LERTR算法求解最小能耗實時路由問題，能高效地取得這個NP-Complete問題的較優(yōu)解。

參考文獻：

[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] 馬華東, 陶 丹. 多媒體傳感器網(wǎng)絡(luò)及其研究進展[J]. 軟件學(xué)報, 2006, 17(9): 2013-2028.

[3] 余燕平, 仇佩亮. 一種改進的Steiner樹算法[J]. 通信學(xué)報, 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] 周靈, 王建新. 無線多媒體傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量控制路由協(xié)議研究[J]. 電子學(xué)報, 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路由協(xié)議研究[J]. 中山大學(xué)學(xué)報:自然科學(xué)版, 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.