葛麗芳

（福建工程學院 計算機與信息科學系，福建 福州 350108）

1 引言

隨著無線傳感技術的發(fā)展和不同應用場景的需求，支持多媒體數據傳輸的無線傳感器網絡具有重要的作用.隨著網絡規(guī)模的擴大，數據流量的急劇增加，由于無線傳感網節(jié)點計算、存儲資源有限，而且部分節(jié)點采用電池供電，大量的數據傳輸導致節(jié)點能耗過大，使無線傳感網的性能乃至正常工作壽命急劇降低.因此，如何在無線傳感器網絡中動態(tài)選擇高效的傳輸路徑對平衡網絡資源，延長網絡壽命具有非常重要的意義.

支持多媒體數據傳輸的無線傳感網通常由具有處理能力、存儲能力與無線通信能力的多媒體傳感器節(jié)點構成,其通過集成于節(jié)點上的多媒體傳感器協(xié)作地感知外部環(huán)境,將圖像、音頻、視頻等多媒體信息傳輸給終端用戶.在應用過程中，流媒體數據對網絡服務質量（QoS，如帶寬、時延、丟包率等）有嚴格的要求.為了保障網絡的生存時間，需要平衡網絡負載，選擇具有較高能量的節(jié)點傳輸.同時，為了保障傳輸質量和時延，需要對傳輸路徑進行跳數限制.

在建模過程中，無線傳感網通常被模擬為由眾多頂點和連接各個頂點的邊組成的圖，其中頂點表示為無線傳感器節(jié)點，而邊則是連接各個傳感器節(jié)點之間的無線信道.某條傳輸路徑中的可用資源可以近似地計算為無線傳感器網絡負載的倒數，即鏈路長度/數據流量.無線傳感器網絡中最優(yōu)傳輸路徑的發(fā)現、選擇和收斂性分析方法和相關算法近年來受到研究人員的廣泛關注[1].當前無線傳感器網絡中，用于海量數據傳輸的路由協(xié)議主要是基于QoS感知路由協(xié)議[2].早期QoS感知的路由算法僅僅考慮單個QoS參數要求，如僅僅是網絡傳輸的實時性，或數據傳輸的可靠性等[3].SAR路由協(xié)議[4]是無線傳感器網絡中第一個QoS感知多路徑路由選擇算法，其在選擇路由時不僅會考慮每條鏈路的端到端時延，還可以計算路徑的能耗以及數據包優(yōu)先級，但路由算法非常復雜，需要維護多個樹結構，同時其算法的時間復雜度較高，因此并不適合拓撲變化頻繁的無線傳感器網絡[5].本文研究的目標是提出一種具有多項式時間復雜度的高效算法能夠準確快速地找到無線傳感器網絡中具有最優(yōu)傳輸路徑（即具有最小負載的傳輸路徑）.

2 無線傳感網中最優(yōu)傳輸路徑求解算法

2.1 無線傳感網中最優(yōu)傳輸路徑問題

定義1 無線傳感網中傳輸路徑的容量（負載的倒數）定義為：C=L/N，其中N為該路徑中(包括上行和下行的)數據流量，L為鏈路的長度（跳數）.

定義2 無線傳感網定義為：具有n個節(jié)點的無向圖G=，其中V是頂點的集合，代表所有無線傳感器節(jié)點，E是邊的集合，代表所有連接頂點的信道，對于每條邊e∈E攜帶有一個屬性向量(N,L).為了計算方便，選擇傳感網的某個節(jié)點r，以此為根節(jié)點得到根為r的生成樹Tr作為傳輸路徑的計算空間[5].

定義3 無線傳感網中最優(yōu)傳輸路徑選擇問題定義為：計算生成樹Tr中的一個子樹滿足鏈路長度范圍：Lmin≤∑e∈ELe≤Lmax和容量∑e∈ELe/∑e∈ENe在所有子樹中為最大.

2.2 求解算法

本文求解最優(yōu)傳輸路徑算法采用動態(tài)規(guī)劃[6]技術實現，其的特點是借助優(yōu)化子結構T'[7]簡化搜索過程.

引理1 假設T'為T中具有最大容量的子樹，r'為T'的根節(jié)點，令 childT’(r’)={v1,v2,…vq}(childT(r’))，對于 1≤i≤q則每個子樹T'vi即是Tvi的最大容量子樹.

證明 用反證法，對于1≤i≤q，假設存在另外一個根節(jié)點為 vj的子樹 T"滿足∑v∈V(T'vj)<∑v∈V(T")，則有 T'-T'vj+T"是另外一個以r'為根節(jié)點的子樹且其容量大于T'，這和題設矛盾，命題得證.

對于樹中的非葉節(jié)點v，設其有子節(jié)點v1,v2,…vdeg(v)，其中deg(v)為節(jié)點v的子節(jié)點數目，設Ψyv[x]為以v1,v2,…vy為根節(jié)點的子樹中具有最大容量的子樹，其鏈路總長度為x，設Ωv[x]為以v為根節(jié)點的樹Tv的子樹中具有最大容量的子樹，其鏈路總長度為x.

根據引理1，對于T中的葉節(jié)點v，如果x=Lv則有Ωv[x]=Nv否則Ωv[x]=Null，對于具有deg(v)個子節(jié)點的非葉節(jié)點v有

同時為了構建最大容量子樹，需要建立一個緩存來記錄遍歷過程的中間信息：

算法1給出了計算無線傳感網中具有最大容量子樹的算法的具體實現.

算法1最大容量路徑計算MCP(T,r,Lmin,Lmax)

輸入：n節(jié)點路網生成樹T，路徑長度范圍區(qū)間[Lmin,Lmax].

輸出：路徑P滿足路徑長度范圍：Lmin≤∑e∈ELe≤Lmax和路徑容量∑e∈ELe/∑e∈ENe在所有路徑中最大.

1: 計算所有節(jié)點v∈V(T)的深度dep(v)

2:FOR每個節(jié)點v按照其深度降序DO

3:IFv是葉節(jié)點THEN

4: Ωv[Lv]←Nv

5:ELSE

6: FORy←1 TO deg(v)DO

7: FOR x←0v TO Lmax-Lv DO

IF y==1 THEN

10: ELSE

13: END IF

14: END FOR

15: END FOR

16:FOR x←Lvv TO Lmax DO

18: END FOR

19:END IF

20:END FOR

21:x←x-Lv;m←deg(v)

22:P←v

23:WHILE x>0 DO

25:IF L<>0THEN

26: x←x-Lv-Lpar(v)

27:END IF

28:m←m-1

29:END WHILE

30:RETURN P

2.3 算法時間復雜度分析

定理1 具有n個節(jié)點的無線傳感網生成樹中限長(Lmin≤∑e∈ELe≤Lmax)最大容量路徑算法可以在)時間復雜度內實現.

證明 在給定最大傳輸容量生成樹的基礎上，所有節(jié)點的深度可以通過廣度優(yōu)先算法以O(n)的時間計算出.根據引理1和引理2以及算法1中的行2-20可知，所有節(jié)點的元素]以及的計算可以在)的時間復雜度內實現.具有最大傳輸容量的子樹也可以在O(n)的時間內計算出來，所以命題得證.

3 結論

無線傳感網中最大容量鏈路的發(fā)現和選擇能夠在解決大量數據的高效傳輸問題.由于支持多媒體數據傳輸的無線傳感網中數據流量的急劇增加，節(jié)點計算、存儲資源受限，而且部分節(jié)點采用電池供電，難以在高速數據通信中維持較長時間的正常工作.因此，如何在無線傳感器網絡中動態(tài)選擇高效的傳輸路徑對平衡網絡資源，延長網絡壽命具有非常重要的意義.本文針對無線傳感網中的限長最優(yōu)傳輸路徑的求解問題提出一種更優(yōu)的算法.該算法能以多項式時間)找到限長的最優(yōu)傳輸路徑，并給出了算法的時間復雜度分析和證明.

〔1〕Shafiullah GM,Gyasi-Agyei A,Wolfs PJ.A survey of energy-efficient and QoS-aware routing protocols for wireless sensor networks.In:Proc.of the Int’l Conf.on Telecommunicatios and Networking/Int’l Conf.on Industrial Electronics,Technology and Automation.Univ Bridgeport:IEEE,2008.352-357.[doi:10.1007/978-1-4020-8737-0_63].

〔2〕Sohrabi K,Gao J,Ailawadhi V,Pottie GJ.Protocols for self-organization of a wireless sensor network.IEEE Personal Communications,2000,7(5):16?27.[doi:10.1109/98.878532].

〔3〕Tian H,Stankovic JA,Lu CY,Abdelzaher T.SPEED:A stateless protocol for real-time communication in sensor networks.In:Proc.of the 23rd Int’l Conf.on Distributed Computing Systems Workshops.Providence:IEEE Computer Society,2002.46?55.[doi:10.1109/ICDCS.2003.1203451].

〔4〕Felemban E,Lee CG,Ekici E.MMSPEED:Multipath multi-SPEED protocol for QoS guarantee of reliability and timeliness in wireless sensor networks.IEEE Trans.on Mobile Computing,2006,5(6):738?754.[doi:10.1109/TMC.2006.79].

〔5〕Man Lung Yiu,Dimitris Papadias,Nikos Mamoulis,Yufei Tao:Reverse Nearest Neighbors in Large Graphs[J].IEEE Transaction on Knowledge and Data Engineering,2006,18(4):540-553.

〔6〕Su HH,Lu CL,Tang CY,An improved algorithm for finding a length-constrained maximum-density subtree in a tree[J].Information Process Letters,2008,109:161–164.

〔7〕Lin RR,Kuo WH,Chao KM,Finding a length-constrained maximum-density path in a tree[J].Journal of Combination Optimization,2005,9(2):147–156.