基于數(shù)據(jù)融合的WMSNs最小能耗實(shí)時(shí)路由算法*

周 靈，龍 灘，王建新

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

無線多媒體傳感器網(wǎng)絡(luò)(Wireless Multimedia Sensor Networks, WMSNs)將信息量大、內(nèi)容豐富的圖像、音頻和視頻等多媒體信息引入到環(huán)境監(jiān)測(cè)活動(dòng)中，實(shí)現(xiàn)了全方位、細(xì)粒度、精確的信息監(jiān)測(cè)。作為一個(gè)無線多跳多媒體通信網(wǎng)絡(luò)，由于多媒體數(shù)據(jù)傳輸量大，節(jié)能問題尤為突出，如何最小化能耗并延長(zhǎng)網(wǎng)絡(luò)生存期是一個(gè)重要的挑戰(zhàn)。同時(shí)，多媒體通信網(wǎng)絡(luò)還具有很強(qiáng)的服務(wù)質(zhì)量(Quality of Server, QoS)控制要求，比如提供實(shí)時(shí)通信。最后，由于WMSNs獨(dú)特的音頻、視頻、圖像等多媒體數(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ù)路由通信問題。對(duì)于這種類型的通信，其QoS控制路由算法必須保障：① 從WMSNs通信服務(wù)質(zhì)量方面考慮，要求路由具有QoS保障，典型的是滿足一定的時(shí)延要求的實(shí)時(shí)通信；② 從網(wǎng)絡(luò)資源管理和優(yōu)化的角度考慮，要求優(yōu)化網(wǎng)絡(luò)資源管理，主要是最小化網(wǎng)絡(luò)代價(jià)；典型的是最小化網(wǎng)絡(luò)能耗，最大化網(wǎng)絡(luò)生存期，延長(zhǎng)監(jiān)測(cè)網(wǎng)絡(luò)的壽命。要同時(shí)對(duì)兩者進(jìn)行優(yōu)化，即QoS控制的最小能耗路由問題。

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

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

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

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

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

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

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

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

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

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

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

2 LERTR算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

算法偽代碼描述如下：

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為信號(hào)源節(jié)點(diǎn)隊(duì)列

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

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

6)For eachmiinQ

7)If 信號(hào)源mi到樹T時(shí)延小于Δthen

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

9)Else

10)T←T∪{mi在樹TDelay中到匯聚節(jié)點(diǎn)D的最小時(shí)延路徑}

11)If there exists a loop then removing Loop

12)End If-else

13)End for

14)ReturnT

3 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

4 總 結(jié)

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

參考文獻(xiàn)：

[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ìn)展[J]. 軟件學(xué)報(bào), 2006, 17(9): 2013-2028.

[3] 余燕平, 仇佩亮. 一種改進(jìn)的Steiner樹算法[J]. 通信學(xué)報(bào), 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é)報(bào), 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é)報(bào):自然科學(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.