基于兩步前向區(qū)域空洞預(yù)測的WMSNs路由算法

孫 毅,劉浩程,陸 俊,黃可心

(華北電力大學(xué)電氣與電子工程學(xué)院,北京 102206)

?

基于兩步前向區(qū)域空洞預(yù)測的WMSNs路由算法

孫 毅,劉浩程*,陸 俊,黃可心

(華北電力大學(xué)電氣與電子工程學(xué)院,北京 102206)

針對WMSN中的空洞問題,使用兩步前向區(qū)域進(jìn)行空洞的預(yù)測,并使用投影距離代替貪婪算法進(jìn)行選路,提出了TFAP(Two steps Forward Area Prediction)算法。仿真結(jié)果表明,TFAP算法改善了QoS延遲和網(wǎng)絡(luò)性能(兩步前向區(qū)域空洞預(yù)測有效進(jìn)行空洞優(yōu)化,投影距離也能優(yōu)化網(wǎng)絡(luò)性能)。

無線多媒體傳感器網(wǎng)絡(luò);路由算法;空洞預(yù)測;前向區(qū)域

無線多媒體傳感器網(wǎng)絡(luò)WMSNs(Wireless Multimedia Sensor Networks)[1],是由一種多媒體傳感器節(jié)點(diǎn)形成的自組織分布式無線網(wǎng)絡(luò),WMSNs作為傳感器網(wǎng)絡(luò)的高級形式,已成為一個嶄新的研究領(lǐng)域,同樣也伴隨著新的挑戰(zhàn)。QoS的需求是WMSNs區(qū)別于傳統(tǒng)WSNs的一個重要標(biāo)志,傳統(tǒng)WSNs通常以犧牲QoS以換取節(jié)點(diǎn)的能量使用最大化為目的,而WMSNs更多考慮的是實(shí)時性,可靠性,帶寬等服務(wù)質(zhì)量[2-3]。

WMSNs的路由協(xié)議以保障QoS為首要目標(biāo),同時考慮能量最優(yōu)策略。其中,SAR(Sequential Assignment Routing)協(xié)議[4]是第1個考慮QoS保障的WSNs路由協(xié)議,該算法首先反向建立多條路徑,再根據(jù)能量等參數(shù)選擇最優(yōu)路徑,缺點(diǎn)是節(jié)點(diǎn)中的大量冗余信息消耗了大量能量和代價,可拓展性差,在大規(guī)模的WMSNs中可能無法使用。SPEED協(xié)議[5]是一個基于地理位置信息的無狀態(tài)實(shí)時路由協(xié)議,該算法根據(jù)選擇速率大于中繼速率的鄰居節(jié)點(diǎn)來提供軟實(shí)時的QoS保障,缺點(diǎn)是沒有考慮MWSNs的網(wǎng)絡(luò)和節(jié)點(diǎn)的能量特性。

WMSNs的路由協(xié)議隨著定位算法的不斷演進(jìn),其中的地理位置路由得到廣泛應(yīng)用。TPGF(Two Phase Geographic Greedy Forwarding)[6]簡約高效,通過反向精簡大大減少了路徑節(jié)點(diǎn)數(shù),有效降低了延遲。但是在遇到空洞時采用標(biāo)記回退策略,具有一定隨意性,經(jīng)常出現(xiàn)長距離空洞繞行問題[7]。本文主要針對空洞問題和貪婪前進(jìn)提出TFAP算法,算法通過兩步前向區(qū)域進(jìn)行空洞的預(yù)測,進(jìn)行空洞避免,通過投影距離保證每一步前進(jìn)距離最遠(yuǎn)。減少了路徑節(jié)點(diǎn)個數(shù),降低了網(wǎng)絡(luò)時延,也在一定程度上優(yōu)化了網(wǎng)絡(luò)性能。

1 系統(tǒng)模型

(1)

其中:

(2)

由式(1)、式(2)可知,在傳輸范圍R超過門限值d0時,能量消耗將會快速增加,某些節(jié)點(diǎn)將會極快的消耗掉能量,縮短網(wǎng)絡(luò)的生命周期。本算法中限定節(jié)點(diǎn)的傳輸范圍R

圖1 前向區(qū)域的定義

2 兩步前向區(qū)域空洞預(yù)測算法

2.1 算法設(shè)計

如圖1所示是A節(jié)點(diǎn)的前向區(qū)域示意圖。A為傳感器節(jié)點(diǎn),Sink節(jié)點(diǎn)是最終目的節(jié)點(diǎn)。A節(jié)點(diǎn)的前向區(qū)域定義是:以A節(jié)點(diǎn)為圓心,A節(jié)點(diǎn)的通信距離R為半徑的圓⊙A與以Sink節(jié)點(diǎn)為圓心,A節(jié)點(diǎn)到Sink節(jié)點(diǎn)的距離d(A,Sink)為半徑的圓的相交部分的集合。A節(jié)點(diǎn)的前向區(qū)域FTA(Forward Transmission Area)表示為:

FTA(A)=⊙A∩⊙Sink

(3)

其中⊙A,⊙Sink分別表示以A和以Sink為圓心的圓。

如圖2所示,A節(jié)點(diǎn)的一步前向區(qū)域?yàn)閳D中空白區(qū)域,一步前向區(qū)域內(nèi)的點(diǎn)稱為一步前向驗(yàn)證點(diǎn)FTN(First Test Nodes):

圖2 兩步前向區(qū)域空洞預(yù)測原理圖

圖3 幾何投影距離計算原理圖

FTN(A)={N(x)∈FTA(A)}

(4)

圖2中點(diǎn)B、C就是一步前向驗(yàn)證點(diǎn)。圖中豎向陰影區(qū)域和橫向陰影區(qū)域分別是一步前向驗(yàn)證點(diǎn)B、C的兩步前向區(qū)域SFTA(Second time Forward Transmission Area)。其中節(jié)點(diǎn)B的兩步前向區(qū)域內(nèi)具有節(jié)點(diǎn)D、E,而節(jié)點(diǎn)C的兩步前向區(qū)域內(nèi)有沒節(jié)點(diǎn),將兩步前向區(qū)域內(nèi)具有節(jié)點(diǎn)的點(diǎn)稱為兩步前向驗(yàn)證點(diǎn)STN(Second Test Nodes):

STN(A)={N(x)∈FTA(A)∩SFTA(N)≠?}

(5)

本文算法在兩次前向驗(yàn)證點(diǎn)中選取幾何投影距離PD(Projection Distance)最大的點(diǎn)作為下一跳,即:

Next_node=max(PDi=i1,…in)

(6)

其中i1,i2,…,in表示A節(jié)點(diǎn)的所有兩步前向驗(yàn)證點(diǎn)。

如圖3所示,是幾何投影距離計算原理圖。

其中A點(diǎn)坐標(biāo)為(xi,yi),B點(diǎn)坐標(biāo)為(xj,yj),Sink點(diǎn)坐標(biāo)為(0,0)。

其中:

(7)

(8)

(9)

將式(5)～式(7)代入可推導(dǎo)得出B節(jié)點(diǎn)的投影距離坐標(biāo)表示為:

(10)

使用投影距離來選擇下一跳,保證了每一次選路時,選擇的這一跳都朝Sink節(jié)點(diǎn)前進(jìn)了最大的距離,能最快到達(dá)Sink節(jié)點(diǎn)。

2.2 算法實(shí)現(xiàn)

本文算法基于地理位置信息,具有良好的擴(kuò)展性,適合于大規(guī)模網(wǎng)絡(luò)。本文算法可以對空洞進(jìn)行預(yù)測并對路徑進(jìn)行優(yōu)化,盡可能減少跳數(shù),并采用投影距離保證每一跳朝Sink節(jié)點(diǎn)的前進(jìn)距離都是最大的。具體算法描述如下:

①判斷Sink節(jié)點(diǎn)是否在一跳可達(dá)的范圍內(nèi),如果Sink節(jié)點(diǎn)一跳可達(dá),則建路成功,直接跳到步驟⑥,否則到下一步。

②計算該節(jié)點(diǎn)的一步前向區(qū)域FTA(A),通過式(4)確定一步前向驗(yàn)證點(diǎn)FTN(A)。

③計算一步前向驗(yàn)證點(diǎn)的兩步前向區(qū)域SFTA(N),通過式(5)確定兩步前向驗(yàn)證點(diǎn)STN(A)。

④對每個兩步前向驗(yàn)證點(diǎn)STN(A)通過式(10)計算其投影距離。

⑤在兩步前向驗(yàn)證點(diǎn)STN(A)中選取投影距離最大的點(diǎn)作為下一跳。執(zhí)行步驟①。

⑥按照TPGF的精簡原則,從源節(jié)點(diǎn)到Sink節(jié)點(diǎn)進(jìn)行精簡,剔除路徑中可能出現(xiàn)的環(huán)路,并將剔除的節(jié)點(diǎn)進(jìn)行初始化,標(biāo)記為可用節(jié)點(diǎn)。

圖4 TPGF選路結(jié)果

如圖4和圖5所示,分別為節(jié)點(diǎn)個數(shù)n=150時,TPGF和本文算法遇到一個空洞時建立的路徑圖。如圖4,TPGF在A點(diǎn)進(jìn)行選路時,根據(jù)貪婪算法選擇了B點(diǎn)作為下一跳節(jié)點(diǎn),B節(jié)點(diǎn)的鄰居節(jié)點(diǎn)內(nèi)沒有比B節(jié)點(diǎn)離Sink節(jié)點(diǎn)更近的節(jié)點(diǎn),也就是在B節(jié)點(diǎn)遇到了空洞。根據(jù)TPGF選路原則,將在B節(jié)點(diǎn)進(jìn)行邊緣轉(zhuǎn)發(fā),選取了D節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)。如圖5,本文算法在A節(jié)點(diǎn)進(jìn)行選路時,判定A節(jié)點(diǎn)的一步前向區(qū)域內(nèi)有B、C兩個節(jié)點(diǎn),B、C節(jié)點(diǎn)是一步驗(yàn)證點(diǎn)。分別對B、C節(jié)點(diǎn)的兩步前向區(qū)域內(nèi)是否有節(jié)點(diǎn)進(jìn)行判定,B節(jié)點(diǎn)的兩步前向區(qū)域內(nèi)不具有節(jié)點(diǎn),也就是在B節(jié)點(diǎn)會遇到空洞。而C節(jié)點(diǎn)的兩步前向區(qū)域內(nèi)具有節(jié)點(diǎn),也就是在C節(jié)點(diǎn)不會遇到空洞。根據(jù)本文算法,在A節(jié)點(diǎn)選路時,已知道選B節(jié)點(diǎn)作為下一跳時會遇到空洞,因此把C節(jié)點(diǎn)作為A節(jié)點(diǎn)的下一跳。從圖中可以知道,本文算法有效地避開了空洞區(qū)域,減少了節(jié)點(diǎn)個數(shù)。

圖5 本文算法選路結(jié)果

3 仿真結(jié)果及分析

3.1 仿真環(huán)境設(shè)置

本文使用了MATLAB7.1對TPGF及本文算法分別進(jìn)行了仿真。仿真設(shè)置在600m×400m的范圍內(nèi),目的節(jié)點(diǎn)位置在(0,0)處,源節(jié)點(diǎn)為拓?fù)溆疑戏骄嚯x目的節(jié)點(diǎn)的最遠(yuǎn)節(jié)點(diǎn),能量參數(shù)采用文獻(xiàn)[5]、[10]的能量模型進(jìn)行能量統(tǒng)計,仿真環(huán)境參數(shù)如表1。

表1 仿真實(shí)驗(yàn)中的參數(shù)設(shè)置

3.2 QoS性能實(shí)驗(yàn)

本文采用同文獻(xiàn)[5,10]中相同的時延統(tǒng)計原理進(jìn)行統(tǒng)計,時延:

De2e=k*(Dhop+Dotherfactors)

(11)

其中k表示路徑節(jié)點(diǎn)個數(shù),Dhop表示節(jié)點(diǎn)間傳輸時的延時,Dotherfactors表示MAC層和隊列的時延,Dhop+Dotherfactors為一定值,取20ms。可知,該條路徑的延遲與路徑節(jié)點(diǎn)個數(shù)成正比,也就是說路徑節(jié)點(diǎn)個數(shù)的統(tǒng)計也就顯示了路徑延遲的對比。

如圖6所示,在區(qū)域內(nèi)節(jié)點(diǎn)個數(shù)n=150、155、160、165、170、175、180、185、190、195、200時,遇到一個空洞,本文算法與TPGF路徑節(jié)點(diǎn)個數(shù)對比,也是建立的路徑的延遲對比。

圖6 不同節(jié)點(diǎn)密度路徑上節(jié)點(diǎn)個數(shù)對比

不同節(jié)點(diǎn)個數(shù)延遲優(yōu)化百分比如表2所示,由表可知平均時延減低了9.2%。在遇到一個空洞時,本文算法相較于TPGF可以有效減少平均傳輸時延,更加滿足無線多媒體傳感網(wǎng)對于QoS的需求。

表2 相比TPGF延遲優(yōu)化百分率表

3.3 網(wǎng)絡(luò)性能實(shí)驗(yàn)

本文以第1個節(jié)點(diǎn)死亡時終止發(fā)送數(shù)據(jù)包,統(tǒng)計了網(wǎng)絡(luò)的初始能量和剩余能量以及能量消耗。在節(jié)點(diǎn)個數(shù)n=150時,沒有遇到空洞時的能量消耗如圖7所示。橫坐標(biāo)表示從源節(jié)點(diǎn)到Sink節(jié)點(diǎn)發(fā)送數(shù)據(jù)包的輪數(shù),縱坐標(biāo)表示路徑上節(jié)點(diǎn)的剩余總能量。

圖7 n=150時沒有空洞的能量消耗圖

兩種算法都在160輪左右出現(xiàn)第1個死亡節(jié)點(diǎn),原因是在建路時,兩種算法在建路時都使用了同一個節(jié)點(diǎn),而該節(jié)點(diǎn)能量消耗最快,成為了第1個死亡節(jié)點(diǎn)。在本文算法中,第1個節(jié)點(diǎn)出現(xiàn)死亡時網(wǎng)絡(luò)余能量為4.32J,而TPGF第1個節(jié)點(diǎn)出現(xiàn)死亡時網(wǎng)絡(luò)剩余能量為5.21J。計算可得本文算法能量利用率為77.3%,而TPGF能量利用率為72.6%。可知在沒有遇到空洞的情況下,本文使用前向投影距離來選擇下一跳也能夠在一定程度上提高能量利用率。

如圖8所示,橫坐標(biāo)表示從源節(jié)點(diǎn)到Sink節(jié)點(diǎn)發(fā)送數(shù)據(jù)包的輪數(shù),縱坐標(biāo)表示路徑上節(jié)點(diǎn)的總能量。TPGF在第150輪時出現(xiàn)第1個死亡節(jié)點(diǎn),而本文算法在第160才出現(xiàn)第1個死亡節(jié)點(diǎn)。原因是TPGF的路徑中的第1個死亡節(jié)點(diǎn)處于空洞邊緣,相距鄰居節(jié)點(diǎn)距離較遠(yuǎn),能量消耗最快。在本文算法中該節(jié)點(diǎn)在建路過程中沒有被選擇,也在某些情況下提高了網(wǎng)絡(luò)的生命周期。

圖8 n=150時有一個空洞時能量消耗圖

圖9 隨機(jī)運(yùn)行20次的空洞解決效率圖

為了分析本文算法的有效性,選擇了150～200個節(jié)點(diǎn)分別進(jìn)行了20次隨機(jī)運(yùn)行,分別改進(jìn)了6、3、5、3、4,1次空洞。隨著節(jié)點(diǎn)個數(shù)的增加,由于空洞幾率變小,進(jìn)行空洞預(yù)測并避免的次數(shù)也相應(yīng)成減少趨勢。本文算法完全解決了一共出現(xiàn)的22個空洞,解決效率100%。

TPGF算法需要掌握鄰節(jié)點(diǎn)的位置信息,鄰節(jié)點(diǎn)之間需要發(fā)送信息告知對方自己的位置,這一過程消息復(fù)雜度大約為O(n),在進(jìn)行反向精簡時,需要再次進(jìn)行鄰節(jié)點(diǎn)信息交互,這一過程消息復(fù)雜度大約為O(n),TPGF的算法復(fù)雜度大約為O(2n)。進(jìn)行兩步空洞預(yù)測需要進(jìn)行多一次的地理信息交互過程,把自己的鄰居節(jié)點(diǎn)位置告訴自己的鄰居,該過程消息的復(fù)雜度為O(2n)。反向精簡過程消息復(fù)雜度大約為O(n),因此,本文算法復(fù)雜度大約為O(3n)。本文算法對比TPGF算法復(fù)雜度大概增加了50%,但是結(jié)合本文算法的有效性和對能量的優(yōu)化情況,本文算法還是有一定的可取之處的。

4 結(jié)論

本文針對WMSNs中的路由空洞問題,采取兩步前向區(qū)域進(jìn)行空洞預(yù)測,盡最大可能避免了在空洞區(qū)域的繞行,并且采用投影距離代替貪婪算法保證了每一跳前進(jìn)距離的最大。通過MATLAB仿真表明,本文算法能有效避免遇到空洞,減少了路徑節(jié)點(diǎn)個數(shù),降低了時延,在增加了一定開銷的情況下,在能量利用率和網(wǎng)絡(luò)生命周期上有一定改善。

[1]李芳敏,李姮,劉新華.無線多媒體傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)及QoS保障機(jī)制[J].計算機(jī)科學(xué),2009,36(6):19-25.

[2]周靈,王建新.無線多媒體傳感器網(wǎng)絡(luò)路由協(xié)議研究[J].電子學(xué)報,2011,39(1):149-156.

[3]李芳敏,方藝霖,李姮,等.無線多媒體傳感器網(wǎng)絡(luò)QoS區(qū)分服務(wù)路由機(jī)制[J].電子學(xué)報,2010,38(10):2322-2327.

[4]Sohrabi K,Gao J,Ailawadhi V,et al.Protocols for Self-Organization of a Wireless Sensor Network[J].IEEE Personal Communications,2000,7(5):16-27.

[5]He T,Stankovic J A,Chenyang Lu,et al.SPEED:A Stateless Protoco l for Real Time Communication in Sensor Networks[C]//Proceeding of International Conference on Distributed Computing Systems.Washington:IEEE Computer Society,2003:204-223.

[6]Lei S,Yan Zhang,Yang L T,et al.Geographic Routing in Wireless Multimedia Senor Networks[C]//Proceedings of the Second International Conference on Future Generation Communication and Networking.New York:IEEE Communication Society,2008:68-73.

[7]田樂,謝東亮,任彪,等.無線傳感器網(wǎng)絡(luò)貪婪轉(zhuǎn)發(fā)策略中的路由空洞問題[J].電子與信息學(xué)報,2007,29(12):2996-3000.

[8]Heinzelman W B,Chandrakasan A P,Balakrishnan H.An Application Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Trans on Wireless Communications,2002,1(4):660-670.

[9]劉鐵流,巫詠群.基于能量優(yōu)化的無線傳感器網(wǎng)絡(luò)分簇路由算法研究[J].傳感技術(shù)學(xué)報,2011,24(5):107-114.

[10]Zhang L,Manfred Hanswirht,Lei Shu,et al.Multi Priority Multi Path Selection for Video Streaming in Wireless Multimedia Sensor Networks[J].Lecture Notes in Computer Science on Ubiquitous Intelligence and Computing,2008,5061:439-452.

[11]Zhang Degan,Li Guang,Zheng Ke et al.An Energy-Balanced Routing Method Based on Forward-Aware Factor for Wireless Sensor Networks[J].IEEE Trans on Industrial Informatics,2014,10(1)765-773.

[12]尚鳳軍,任東海.無線傳感器網(wǎng)絡(luò)中分布式多跳路由算法算法研究[J].傳感技術(shù)學(xué)報,2012,25(4)67-74.

A Routing Algorithm Based on Two Steps Forward Area Prediction for Holes in Multimedia Wireless Senor Networks

SUNYi,LIUHaocheng*,LUJun,HUANGKexin

(College of Electrical and Electronic Engineering,North China Electric Power University,Beijing 102206,China)

The problem of holes in the WMSNs have appeared in the perimeters,two steps forward area has been used to predict holes,and projector distance has been used instead of greedy algorithm.Two steps Forward Area Prediction(TFAP)has been present.The simulation results show that TFAP algorithm has improved quality of service and network performance.Two steps forward area prediction has optimized holes effectively and projector distance can also optimize network performance.

MWSN;routing algorithm;holes prediction;forward transmission area

孫 毅(1972-),男,遼寧朝陽人,教授,博士,主要研究方向?yàn)殡娏ο到y(tǒng)通信、無線傳感器網(wǎng)絡(luò)與物聯(lián)網(wǎng);

劉浩程(1991-),男,湖南岳陽人,碩士研究生,主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)和物聯(lián)網(wǎng),382021953@qq.com。

2014-05-31 修改日期:2014-11-11

C:6150P

10.3969/j.issn.1004-1699.2015.01.023

TP301.6

A

1004-1699(2015)01-0132-05