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

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

?

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

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

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

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

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

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

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

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

1 系統(tǒng)模型

(1)

其中:

(2)

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

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

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

2.1 算法設計

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

FTA(A)=⊙A∩⊙Sink

(3)

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

如圖2所示,A節(jié)點的一步前向區(qū)域為圖中空白區(qū)域,一步前向區(qū)域內的點稱為一步前向驗證點FTN(First Test Nodes):

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

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

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

(4)

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

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

(5)

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

Next_node=max(PDi=i1,…in)

(6)

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

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

其中A點坐標為(xi,yi),B點坐標為(xj,yj),Sink點坐標為(0,0)。

其中:

(7)

(8)

(9)

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

(10)

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

2.2 算法實現(xiàn)

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

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

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

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

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

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

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

圖4 TPGF選路結果

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

圖5 本文算法選路結果

3 仿真結果及分析

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

本文使用了MATLAB7.1對TPGF及本文算法分別進行了仿真。仿真設置在600m×400m的范圍內,目的節(jié)點位置在(0,0)處,源節(jié)點為拓撲右上方距離目的節(jié)點的最遠節(jié)點,能量參數(shù)采用文獻[5]、[10]的能量模型進行能量統(tǒng)計,仿真環(huán)境參數(shù)如表1。

表1 仿真實驗中的參數(shù)設置

3.2 QoS性能實驗

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

De2e=k*(Dhop+Dotherfactors)

(11)

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

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

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

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

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

3.3 網(wǎng)絡性能實驗

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

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

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

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

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

圖9 隨機運行20次的空洞解決效率圖

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

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

4 結論

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

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

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

[3]李芳敏,方藝霖,李姮,等.無線多媒體傳感器網(wǎng)絡QoS區(qū)分服務路由機制[J].電子學報,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)絡貪婪轉發(fā)策略中的路由空洞問題[J].電子與信息學報,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)絡分簇路由算法研究[J].傳感技術學報,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)絡中分布式多跳路由算法算法研究[J].傳感技術學報,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-),男,遼寧朝陽人,教授,博士,主要研究方向為電力系統(tǒng)通信、無線傳感器網(wǎng)絡與物聯(lián)網(wǎng);

劉浩程(1991-),男,湖南岳陽人,碩士研究生,主要研究方向為無線傳感器網(wǎng)絡和物聯(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