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

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

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

?

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

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

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

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

無線多媒體傳感器網絡;路由算法;空洞預測;前向區域

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

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

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

1 系統模型

(1)

其中:

(2)

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

圖1 前向區域的定義

2 兩步前向區域空洞預測算法

2.1 算法設計

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

FTA(A)=⊙A∩⊙Sink

(3)

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

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

圖2 兩步前向區域空洞預測原理圖

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

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

(4)

圖2中點B、C就是一步前向驗證點。圖中豎向陰影區域和橫向陰影區域分別是一步前向驗證點B、C的兩步前向區域SFTA(Second time Forward Transmission Area)。其中節點B的兩步前向區域內具有節點D、E,而節點C的兩步前向區域內有沒節點,將兩步前向區域內具有節點的點稱為兩步前向驗證點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節點的所有兩步前向驗證點。

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

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

其中:

(7)

(8)

(9)

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

(10)

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

2.2 算法實現

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

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

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

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

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

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

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

圖4 TPGF選路結果

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

圖5 本文算法選路結果

3 仿真結果及分析

3.1 仿真環境設置

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

表1 仿真實驗中的參數設置

3.2 QoS性能實驗

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

De2e=k*(Dhop+Dotherfactors)

(11)

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

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

圖6 不同節點密度路徑上節點個數對比

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

表2 相比TPGF延遲優化百分率表

3.3 網絡性能實驗

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

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

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

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

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

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

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

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

4 結論

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

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

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

[3]李芳敏,方藝霖,李姮,等.無線多媒體傳感器網絡QoS區分服務路由機制[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]田樂,謝東亮,任彪,等.無線傳感器網絡貪婪轉發策略中的路由空洞問題[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]劉鐵流,巫詠群.基于能量優化的無線傳感器網絡分簇路由算法研究[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]尚鳳軍,任東海.無線傳感器網絡中分布式多跳路由算法算法研究[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-),男,遼寧朝陽人,教授,博士,主要研究方向為電力系統通信、無線傳感器網絡與物聯網;

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