基于混沌過濾機制的高速無線移動網絡路由算法的研究

田　祎

(商洛學院 經濟與管理學院， 陜西 商洛　726000)

?

基于混沌過濾機制的高速無線移動網絡路由算法的研究

田祎

(商洛學院 經濟與管理學院， 陜西 商洛726000)

為解決高速無線移動網絡路由發現過程中洪泛效應嚴重、數據干擾性能降低、難以實現數據鏈路的發現和維護等問題。提出一種新的基于混沌過濾機制的新路由算法,該算法根據網絡數據流量及數據結構的影響,根據相鄰信息及數據傳輸跳度因素來確定路由發現過程中數據發送效率,盡量減少數據冗余及損耗。仿真實驗表明,提出的新算法可以有效地降低洪泛效應及網絡數據傳輸質量,增加網絡穩定運行時間,具有一定的實際部署意義。

網絡路由;性能干擾;混沌過濾;跳度效率機制;冗余洪泛

隨著各種高速通信終端的飛速發展,通過一定的組網技術組成一種高速無線移動網絡以實現數據在各種終端中的傳輸,成為一種高速發展的技術[1]。針對節點的有限特性以及高速拓撲的不穩定性,人們往往通過一定的路由技術來實現對高速無線移動網絡的數據高效處理,實現數據信息的高效穩定傳輸[2]。

由于高速無線移動網絡中的數據高峰和低谷往往能以一定的概率出現,因此可以通過一定的手段將這種概率性壓力進行條件轉移,以便降低通信冗余及信息丟失。Ahlswede R[3]等提出一種網絡流言路由發現機制,通過發送隨機流言信息包,按概率實現路由發現。仿真實驗表明，該機制可以有效地降低低流量情況下的網絡路由能量控制開銷，但該算法在網絡流量極大時難以實現順利流程對接,導致高流量情況下的路由能量控制開銷反而會增大。Jamal.N.A[4]等驗證了在較低波出現概率的情況下,采用一定的路由請求包可以實現整個網絡近似100%的覆蓋。仿真實驗表明，在低拓撲變動因素下網絡路由缺失效應得到很大程度的改善。然而,該技術在拓撲結構高速變化時節點難以勻速發送路由請求包,導致RREQ請求難以及時得到回應。Nguyen D[5]針對節點分布不均勻的高速無線移動網絡,提出可以采取按概率覆蓋的模式。仿真表明，該算法在一定受限資源對不均勻分布節點的可實現全覆蓋，但該算法未考慮混沌擾動因素,導致該技術在節點數量迅速增加時,網絡冗余性能也會隨之提高。

對此,本文針對傳統研究過程中的局限因素,綜合考慮網絡拓撲結構及網絡運行狀況因素調整信息包轉發概率,最終實現對合適路由需求的較高概率調整轉發,實現路徑傳輸的最優化,最終降低網絡傳輸開銷。最后,測試了本文算法的網絡性能。

1　基于混沌過濾機制的高速無線移動網絡路由算法

1.1網絡信息包轉發概率的計算

在高速無線移動互聯網的路由發行過程中,一般而言，節點在任意的網絡環境下對于路由請求信息包的轉發概率是按照相同節奏進行轉發的[6]。倘若當前網絡狀況不佳,出現嚴重的網絡擁塞現象,且某些節點因網絡擁塞而難以發揮效能的情況下,按照相同概率進行信息包的轉發可能會造成更嚴重的網絡擁塞現象[7]。

由于針對任意一個網絡節點而言,其網絡擁塞程度可以依照節點擁塞、連續多跳節點狀況、信息傳輸跳數來確定[8]。故本文通過這種網絡擁塞程度來確保移動的RREQ信息包能夠準確地進行傳輸。詳細步驟如下所示:

Step 1按照負載程度對網絡節點進行排序,以小概率傳輸到負載程度較大的節點;

Step 2按照路徑跳數進行第二次排序,按照跳數較少的路由承擔更大概率的信息包傳輸原則進行傳輸;

Step 3進行完Step 1、Step 2 之后,繼續按照一定的周期T進行排序,直到信息包被全部傳輸,并搜尋到一條最佳路由。

根據上述步驟,信息包轉發概率計算過程如下:

1)首先根據當前節點的狀況來計算RREQ信息包在某條路由上成功傳輸的概率prec(q)。

節點的負載程度,可以根據一定周期內到達該節點的RREQ信息包數量及排隊狀況而決定。在具體的某個時刻t0到達節點的信息包服從泊松分布,且分布指數為λ,整個信息包組的節點服務時間X服從相同的分布且信息包之間及信息包組之間處于互相獨立的狀態。因此整個信息流的期望程度NQ可由如下的公式決定:

(1)

其中E[X2]為泊松分布的二階矩[9],E[X]為泊松分布的期望首先進行網絡狀況比對,如果網絡狀況較好,RREQ信息包對應的路由成功傳輸概率prec(q)很高;如果整個網絡狀況較差,導致節點處于擁塞狀態的話,則經過節點進行RREQ信息包傳輸過程將不順利,即:

(2)

其中phigh為接近1的常數;plow處于0～1之間,隨著網絡狀況的下降而處于動態下降的狀況。

2)根據路徑跳數及節點信息來確保RREQ的轉發概率。

首先，節點依據路徑跳數及剩余的路由傳輸跳數h′來確定轉發概率preq,保證RREQ信息包必定能夠以prec(q)來傳輸到目的節點。

由于preq的魯棒性很強，因此在經過若干h′依然可以保持一定程度的可接受誤差,即

(preq)h′=preq(q)。

(3)

其中h′為當前跳數h的函數,該函數由如下的表達式所決定:

(4)

其中，β為整個路由發現過程中的最大跳數,h可以由RREQ信息包中的數據報文解析得到。

設當前節點為Nc，其上一跳節點為Np,下一跳節點為Nnest,整個網絡中處于Np及Nnest交叉覆蓋的節點個數為m。則當前節點Nc對信息包的轉發概率pturn由下式決定:

(1-pturn)m=1-preq。

(5)

在高速無線移動中設通信節點的通信半徑為r,則整個交叉覆蓋區域的面積大小由下式決定:

(6)

經簡化,式(6)可寫為

s=4πr2。

(7)

結合式(5)可得當前節點Nc對信息包的轉發概率pturn為

(8)

(9)

據式(8)，(9)可知當前節點在整個周期T內的整個成功轉發概率p為

(10)

prec(q)滿足:

(11)

1.2算法流程

根據當前節點Nc對信息包的轉發概率pturn的計算來實現對信息包的處理,具體處理信息包的流程如下所示:

Step 1首先進行路由發現,若沒有成功進行路由發現時才進行RREQ信息包的分發。

Step 2中間節點進行RREQ信息包的確認工作,一旦收到信息包,轉Step 3;反之,繼續進行Step 1。

Step 3當僅當該節點是第一次確認信息包時,且當前路由表中存在一條可用鏈路,則進行信息反饋信息包RREP的發送,否,則轉Step 4。

Step 4Step 失敗之后,確認該節點的ID并計算該節點的pturn和prec(q)。一旦當前節點沒有進行轉發則進行信息包分組,當僅當周圍節點的剩余跳數較小時候才進行信息分組轉發,并轉Step 5。

Step 5當前節點在下個時刻收到過相同RREQ信息包,則直接丟棄,轉Step 6,反之,繼續轉向Step 4。

Step 6當僅當收到相異RREQ信息包,則向前一節點發送RREQ信息包進行反饋,并轉Step 7。

Step 7當經過一個周期之后,如果當前節點依然沒有發現一條可用路由,則可能出現隨機路由斷開的問題。此時繼續進行Step 1 開始,直到能夠發現一條可用路由為止。

詳細流程圖如圖1所示。

圖1　算法流程圖Fig.1　Algorithm flow chart

2　仿真實驗

2.1仿真環境設置

為評估本文提出的算法性能,仿真實驗中使用NS-2仿真平臺對DSR[10]，AG_DSR[11]算法與本文算法進行仿真對比。實驗仿真參數如表1所示。

表1　仿真參數表

仿真實驗中,為驗證本文方案的有效性,實驗重點從移動節點個數、網絡內節點個數以及節點初始能量大小這3個變量,與DSR，AG_DSR算法在網絡數據分組投遞率、網絡平均正常運行時間及平均能量消耗這3個指標上進行對比。

2.2仿真結果與分析

2.2.1移動節點個數對分組投遞效率的影響從圖2中可以看到,隨著網絡中節點個數的不斷增加,采用DSR及AG_DSR算法的分組投遞效率呈現下降趨勢,特別是AG_DSR呈現加速下降的趨勢。而本文算法所對應的分組投遞效率的下降程度與DSR及AG_DSR相比要低。這是因為隨著網絡中節點個數不斷增加,網絡節點的擁塞程度也不斷增加[12-13],而本文提出的算法能夠依據網絡中節點擁塞情況動態的維護路由,特別是在擁塞程度較大時可以有效地維護路由不至于沒有收到RREQ信息包而發生斷裂,因此減少了擁塞程度較高時網絡信息丟失的現象,從而提高了分組投遞率。

圖2　網絡節點密度對網絡分組投遞率的影響Fig.2　Effect of network node density on the network packet deliverg rate

2.2.2移動節點個數對網絡穩定運行時間的影響從圖3、圖4中可以看到,隨著網絡中移動節點個數的不斷增加,采用DSR及AG_DSR算法的網絡穩定運行時間呈現下降趨勢。這是由于在網絡中移動節點不斷增加的情況下,網絡拓撲結構的變化也十分頻繁,這直接導致網絡中各個移動節點在傳輸數據包時的丟包率也隨之上升,導致網絡難以正常的運行。而本文算法通過控制轉發概率,特別是可以動態依據概率來選擇最佳的下一跳節點進行數據傳輸,因此大大降低了網絡丟包現象,從而提高了網絡正常運行時間。

圖3　高節點密度對網絡平均正常運行時間的影響Fig.3　Effect of high node density on the arerage network uptime

圖4　低節點密度對網絡平均正常運行時間的影響Fig.4　Effect of low node density on the arerage network uptime

2.2.3節點初始能量對網絡平均正常運行時間的影響從圖5中可以看到,隨著節點初始能量的不斷增加。采用DSR及AG_DSR算法時網絡平均正常運行時間并未得到較好的改善。這是由于隨著節點初始能量的不斷增加,移動節點數據傳輸效能在節點移動頻繁時候呈現不斷下降的趨勢,導致網絡的正常運行受到不必要的干擾。本文算法充分考慮了拓撲結構劇烈變動時導致的數據報文難以解析的現狀,在擁塞嚴重時大大增強數據鏈路維護報文的準確性能,因此改善了鏈路質量,從而大大增強了網絡正常運行的穩定性。

圖5　節點初始能量對網絡平均正常運行時間的影響Fig.5　Effect of node initial energy on the arerage network uptime

圖6　周期T取值對網絡分組投遞率的影響Fig.6　Effect of period T value on the network packet delivery rate

2.2.4周期T取值對網絡分組投遞率的影響從圖6可以看到,隨著周期T的不斷增加,本文算法與對照組算法均呈現網絡分組投遞上升的情況,這是由于隨著周期T的不斷增加,可用于投遞數據的時間也隨之增加,因而提高了網絡分組投遞率。然而本文算法的網絡分組投遞率始終高于對照組算法,這是由于本文算法能夠依照網絡節點擁塞情況維護路由,降低了擁塞發生的概率。而對照組算法均采用簡單投遞方式,因而一旦發生擁塞,即導致網絡分組投遞率出現下降的現象。

3　結　語

由于高速無線移動網絡往往采取洪泛類的路由發現機制,導致采取了優化條件之下依然容易造成嚴重的數據擁塞現象,導致網絡性能出現較大程度的下降[14-15]。本文提出一種新的基于混沌過濾機制的新路由算法,該算法根據網絡數據流量及數據結構的影響,根據相鄰信息及數據傳輸跳度因素來確定路由發現過程中數據發送效率,盡量減少數據冗余及損耗。仿真實驗也表明與傳統的DSR及AG_DSR算法相比,本文提出的算法有較強的優越性,具有一定的實際部署價值。

[1]羅守山,楊文川,蕭薔.基于矢量安全傳輸評估的模型及研究[J]. 北京郵電大學學報,2013,31(3):5-9.

[2]EKMAN F, KERANEN A, KARVO J, et al. Working day movement model[C]//Proceedings of the 1st ACM SIGMOBILE workshop on Mobility models. ACM, 2008: 33-40.

[3]AHLSWEDE R, CAI N, LI S Y R, et al. Network information flow[J]. IEEE Trans. on Information Theory, 2014, 46(4): 1204-1216.

[4]JAMAL N A, AHNED E K. Routing techniques in wireless sensor networks:a survey[J].IEEE Wireless Communication, 2014, 11(6):87-89.

[5]NGUYEN D, TRAN T, NGUYEN T. Wireless broadcast using network coding [J]. IEEE Trans. on Vehicular Technology, 2009, 58(2): 914-925.

[6]LUO H,YE F,CHENG J. Two-tier Data Dissemination in Large-scale Wireless Sensor Networks[J].Wireless Networks, 2011, 11(2):161-175.

[7]HEINZELLNAN W B,CHANDRAKASAN A P,Balakrishnan. An Application Specific Protocol Architecture for Wireless Nerworks[J].IEEE Transactions on Wireless Communications, 2012(4):660-670.

[8]CJEM A,KUMAR S,LAI T H. Local barrier coverage in wireless sensor nerworks[J].IEEE Transactions on Mobile Computing, 2012,10(4):491-504.

[9]AMMARI H M,DAS S K.A study of K-coverage and measures of connectivity in wireless sensor networks[J].IEEE Transactions on Computers,2011,59(2):258-267.

[10] WANG L, GENG X. A Community-driven Hierarchical Message Transmission Scheme in Opportunistic Networks[J]. Smart Computing Review, 2011(1): 85-94.

[11] JOLLIFFE D, TRAN T, NGUYEN T. Data mining network coding [J].IEEE Trans. on Vehicular Technology, 2009, 58(2): 914-925.

[12] LEE W.A data mining framework for constructing features and models for instrusion detection systems[D].New York:New York Computer Science Department of Columbia University,2012: 33-76.

[13] 楊林, 鄭剛. 無線多跳網中具有網絡編碼意識的機會路由協議 [J].清華大學學報(自然科學版), 2010, 50(10): 1713-1717.

[14] CHI K K, JIANG X H, YE B L. Efficient network coding-based loss recovery for reliable multicast in wireless networks [J].IEICE Trans. on Communication, 2010, 93 (4): 971-981.

[15] YANG Z, ZHANG Q, WANG R. On storage dynamics of space delay/disruption tolerant network node [J].Wireless Networks, 2014, 20(8): 2529-2541.

(編輯亢小玉)

A chaotic filtering mechanism based high speed wireless mobile network routing algorithm

TIAN Yi

(Faculty of Economics and Management, Shangluo University, Shangluo 726000， China)

In order to solve the problem of flooding effect in the process of high speed wireless mobile network route discovery, the data interference performance is reduced, and it is difficult to realize the discovery and maintenance of data link. In this paper, a new routing algorithm based on chaotic filtering mechanism is proposed, which is based on the influence of network data traffic and data structure. The data transmission efficiency is determined by the factor of adjacent information and data transmission. The simulation results show that the new algorithm can effectively reduce the flooding effect and the quality of network data transmission, and has a certain practical significance.

network routing; performance jamming; chaotic filtering; jumping efficiency mechanism; redundant flooding

2015-11-05

陜西省自然科學基金資助項目(2015JM6347)；商洛學院服務地方專項基金資助項目(15SKY-FWDF003)；商洛學院教改基金資助項目(15JYJX135)

田祎，男，陜西商南人，從事計算機應用技術研究。

TP393

A

10.16152/j.cnki.xdxbzr.2016-04-011