一種無線傳感網(wǎng)中最優(yōu)傳輸路徑選擇的高效算法

葛麗芳

（福建工程學(xué)院 計(jì)算機(jī)與信息科學(xué)系，福建 福州 350108）

1 引言

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

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

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

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

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

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

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

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

2.2 求解算法

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

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

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

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

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

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

算法1給出了計(jì)算無線傳感網(wǎng)中具有最大容量子樹的算法的具體實(shí)現(xiàn).

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

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

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

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

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

3:IFv是葉節(jié)點(diǎn)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 算法時(shí)間復(fù)雜度分析

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

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

3 結(jié)論

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

〔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.