基于混沌過濾機制的高速無線移動網(wǎng)絡(luò)路由算法的研究

田　祎

(商洛學(xué)院 經(jīng)濟與管理學(xué)院， 陜西 商洛　726000)

?

基于混沌過濾機制的高速無線移動網(wǎng)絡(luò)路由算法的研究

田祎

(商洛學(xué)院 經(jīng)濟與管理學(xué)院， 陜西 商洛726000)

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

網(wǎng)絡(luò)路由;性能干擾;混沌過濾;跳度效率機制;冗余洪泛

隨著各種高速通信終端的飛速發(fā)展,通過一定的組網(wǎng)技術(shù)組成一種高速無線移動網(wǎng)絡(luò)以實現(xiàn)數(shù)據(jù)在各種終端中的傳輸,成為一種高速發(fā)展的技術(shù)[1]。針對節(jié)點的有限特性以及高速拓?fù)涞牟环€(wěn)定性,人們往往通過一定的路由技術(shù)來實現(xiàn)對高速無線移動網(wǎng)絡(luò)的數(shù)據(jù)高效處理,實現(xiàn)數(shù)據(jù)信息的高效穩(wěn)定傳輸[2]。

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

對此,本文針對傳統(tǒng)研究過程中的局限因素,綜合考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及網(wǎng)絡(luò)運行狀況因素調(diào)整信息包轉(zhuǎn)發(fā)概率,最終實現(xiàn)對合適路由需求的較高概率調(diào)整轉(zhuǎn)發(fā),實現(xiàn)路徑傳輸?shù)淖顑?yōu)化,最終降低網(wǎng)絡(luò)傳輸開銷。最后,測試了本文算法的網(wǎng)絡(luò)性能。

1　基于混沌過濾機制的高速無線移動網(wǎng)絡(luò)路由算法

1.1網(wǎng)絡(luò)信息包轉(zhuǎn)發(fā)概率的計算

在高速無線移動互聯(lián)網(wǎng)的路由發(fā)行過程中,一般而言，節(jié)點在任意的網(wǎng)絡(luò)環(huán)境下對于路由請求信息包的轉(zhuǎn)發(fā)概率是按照相同節(jié)奏進(jìn)行轉(zhuǎn)發(fā)的[6]。倘若當(dāng)前網(wǎng)絡(luò)狀況不佳,出現(xiàn)嚴(yán)重的網(wǎng)絡(luò)擁塞現(xiàn)象,且某些節(jié)點因網(wǎng)絡(luò)擁塞而難以發(fā)揮效能的情況下,按照相同概率進(jìn)行信息包的轉(zhuǎn)發(fā)可能會造成更嚴(yán)重的網(wǎng)絡(luò)擁塞現(xiàn)象[7]。

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

Step 1按照負(fù)載程度對網(wǎng)絡(luò)節(jié)點進(jìn)行排序,以小概率傳輸?shù)截?fù)載程度較大的節(jié)點;

Step 2按照路徑跳數(shù)進(jìn)行第二次排序,按照跳數(shù)較少的路由承擔(dān)更大概率的信息包傳輸原則進(jìn)行傳輸;

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

根據(jù)上述步驟,信息包轉(zhuǎn)發(fā)概率計算過程如下:

1)首先根據(jù)當(dāng)前節(jié)點的狀況來計算RREQ信息包在某條路由上成功傳輸?shù)母怕蕄rec(q)。

節(jié)點的負(fù)載程度,可以根據(jù)一定周期內(nèi)到達(dá)該節(jié)點的RREQ信息包數(shù)量及排隊狀況而決定。在具體的某個時刻t0到達(dá)節(jié)點的信息包服從泊松分布,且分布指數(shù)為λ,整個信息包組的節(jié)點服務(wù)時間X服從相同的分布且信息包之間及信息包組之間處于互相獨立的狀態(tài)。因此整個信息流的期望程度NQ可由如下的公式?jīng)Q定:

(1)

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

(2)

其中phigh為接近1的常數(shù);plow處于0～1之間,隨著網(wǎng)絡(luò)狀況的下降而處于動態(tài)下降的狀況。

2)根據(jù)路徑跳數(shù)及節(jié)點信息來確保RREQ的轉(zhuǎn)發(fā)概率。

首先，節(jié)點依據(jù)路徑跳數(shù)及剩余的路由傳輸跳數(shù)h′來確定轉(zhuǎn)發(fā)概率preq,保證RREQ信息包必定能夠以prec(q)來傳輸?shù)侥康墓?jié)點。

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

(preq)h′=preq(q)。

(3)

其中h′為當(dāng)前跳數(shù)h的函數(shù),該函數(shù)由如下的表達(dá)式所決定:

(4)

其中，β為整個路由發(fā)現(xiàn)過程中的最大跳數(shù),h可以由RREQ信息包中的數(shù)據(jù)報文解析得到。

設(shè)當(dāng)前節(jié)點為Nc，其上一跳節(jié)點為Np,下一跳節(jié)點為Nnest,整個網(wǎng)絡(luò)中處于Np及Nnest交叉覆蓋的節(jié)點個數(shù)為m。則當(dāng)前節(jié)點Nc對信息包的轉(zhuǎn)發(fā)概率pturn由下式?jīng)Q定:

(1-pturn)m=1-preq。

(5)

在高速無線移動中設(shè)通信節(jié)點的通信半徑為r,則整個交叉覆蓋區(qū)域的面積大小由下式?jīng)Q定:

(6)

經(jīng)簡化,式(6)可寫為

s=4πr2。

(7)

結(jié)合式(5)可得當(dāng)前節(jié)點Nc對信息包的轉(zhuǎn)發(fā)概率pturn為

(8)

(9)

據(jù)式(8)，(9)可知當(dāng)前節(jié)點在整個周期T內(nèi)的整個成功轉(zhuǎn)發(fā)概率p為

(10)

prec(q)滿足:

(11)

1.2算法流程

根據(jù)當(dāng)前節(jié)點Nc對信息包的轉(zhuǎn)發(fā)概率pturn的計算來實現(xiàn)對信息包的處理,具體處理信息包的流程如下所示:

Step 1首先進(jìn)行路由發(fā)現(xiàn),若沒有成功進(jìn)行路由發(fā)現(xiàn)時才進(jìn)行RREQ信息包的分發(fā)。

Step 2中間節(jié)點進(jìn)行RREQ信息包的確認(rèn)工作,一旦收到信息包,轉(zhuǎn)Step 3;反之,繼續(xù)進(jìn)行Step 1。

Step 3當(dāng)僅當(dāng)該節(jié)點是第一次確認(rèn)信息包時,且當(dāng)前路由表中存在一條可用鏈路,則進(jìn)行信息反饋信息包RREP的發(fā)送,否,則轉(zhuǎn)Step 4。

Step 4Step 失敗之后,確認(rèn)該節(jié)點的ID并計算該節(jié)點的pturn和prec(q)。一旦當(dāng)前節(jié)點沒有進(jìn)行轉(zhuǎn)發(fā)則進(jìn)行信息包分組,當(dāng)僅當(dāng)周圍節(jié)點的剩余跳數(shù)較小時候才進(jìn)行信息分組轉(zhuǎn)發(fā),并轉(zhuǎn)Step 5。

Step 5當(dāng)前節(jié)點在下個時刻收到過相同RREQ信息包,則直接丟棄,轉(zhuǎn)Step 6,反之,繼續(xù)轉(zhuǎn)向Step 4。

Step 6當(dāng)僅當(dāng)收到相異RREQ信息包,則向前一節(jié)點發(fā)送RREQ信息包進(jìn)行反饋,并轉(zhuǎn)Step 7。

Step 7當(dāng)經(jīng)過一個周期之后,如果當(dāng)前節(jié)點依然沒有發(fā)現(xiàn)一條可用路由,則可能出現(xiàn)隨機路由斷開的問題。此時繼續(xù)進(jìn)行Step 1 開始,直到能夠發(fā)現(xiàn)一條可用路由為止。

詳細(xì)流程圖如圖1所示。

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

2　仿真實驗

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

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

表1　仿真參數(shù)表

仿真實驗中,為驗證本文方案的有效性,實驗重點從移動節(jié)點個數(shù)、網(wǎng)絡(luò)內(nèi)節(jié)點個數(shù)以及節(jié)點初始能量大小這3個變量,與DSR，AG_DSR算法在網(wǎng)絡(luò)數(shù)據(jù)分組投遞率、網(wǎng)絡(luò)平均正常運行時間及平均能量消耗這3個指標(biāo)上進(jìn)行對比。

2.2仿真結(jié)果與分析

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

圖2　網(wǎng)絡(luò)節(jié)點密度對網(wǎng)絡(luò)分組投遞率的影響Fig.2　Effect of network node density on the network packet deliverg rate

2.2.2移動節(jié)點個數(shù)對網(wǎng)絡(luò)穩(wěn)定運行時間的影響從圖3、圖4中可以看到,隨著網(wǎng)絡(luò)中移動節(jié)點個數(shù)的不斷增加,采用DSR及AG_DSR算法的網(wǎng)絡(luò)穩(wěn)定運行時間呈現(xiàn)下降趨勢。這是由于在網(wǎng)絡(luò)中移動節(jié)點不斷增加的情況下,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化也十分頻繁,這直接導(dǎo)致網(wǎng)絡(luò)中各個移動節(jié)點在傳輸數(shù)據(jù)包時的丟包率也隨之上升,導(dǎo)致網(wǎng)絡(luò)難以正常的運行。而本文算法通過控制轉(zhuǎn)發(fā)概率,特別是可以動態(tài)依據(jù)概率來選擇最佳的下一跳節(jié)點進(jìn)行數(shù)據(jù)傳輸,因此大大降低了網(wǎng)絡(luò)丟包現(xiàn)象,從而提高了網(wǎng)絡(luò)正常運行時間。

圖3　高節(jié)點密度對網(wǎng)絡(luò)平均正常運行時間的影響Fig.3　Effect of high node density on the arerage network uptime

圖4　低節(jié)點密度對網(wǎng)絡(luò)平均正常運行時間的影響Fig.4　Effect of low node density on the arerage network uptime

2.2.3節(jié)點初始能量對網(wǎng)絡(luò)平均正常運行時間的影響從圖5中可以看到,隨著節(jié)點初始能量的不斷增加。采用DSR及AG_DSR算法時網(wǎng)絡(luò)平均正常運行時間并未得到較好的改善。這是由于隨著節(jié)點初始能量的不斷增加,移動節(jié)點數(shù)據(jù)傳輸效能在節(jié)點移動頻繁時候呈現(xiàn)不斷下降的趨勢,導(dǎo)致網(wǎng)絡(luò)的正常運行受到不必要的干擾。本文算法充分考慮了拓?fù)浣Y(jié)構(gòu)劇烈變動時導(dǎo)致的數(shù)據(jù)報文難以解析的現(xiàn)狀,在擁塞嚴(yán)重時大大增強數(shù)據(jù)鏈路維護(hù)報文的準(zhǔn)確性能,因此改善了鏈路質(zhì)量,從而大大增強了網(wǎng)絡(luò)正常運行的穩(wěn)定性。

圖5　節(jié)點初始能量對網(wǎng)絡(luò)平均正常運行時間的影響Fig.5　Effect of node initial energy on the arerage network uptime

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

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

3　結(jié)　語

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

[1]羅守山,楊文川,蕭薔.基于矢量安全傳輸評估的模型及研究[J]. 北京郵電大學(xué)學(xué)報,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] 楊林, 鄭剛. 無線多跳網(wǎng)中具有網(wǎng)絡(luò)編碼意識的機會路由協(xié)議 [J].清華大學(xué)學(xué)報(自然科學(xué)版), 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

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

田祎，男，陜西商南人，從事計算機應(yīng)用技術(shù)研究。

TP393

A

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