冉崇善，車 育

(陜西科技大學(xué) 電氣與信息工程學(xué)院， 陜西 西安 710021)

?

·信息科學(xué)·

基于快速移動節(jié)點的Ad hoc網(wǎng)絡(luò)可信度模型及可信路由協(xié)議

冉崇善，車 育

(陜西科技大學(xué) 電氣與信息工程學(xué)院， 陜西 西安 710021)

由于目前廣泛應(yīng)用的路由協(xié)議大都是假設(shè)網(wǎng)絡(luò)中的節(jié)點是可以信任和相互協(xié)作的,對于安全的問題考慮不多,而網(wǎng)絡(luò)中某些節(jié)點很容易被俘獲而成為惡意節(jié)點,使得現(xiàn)有的路由協(xié)議變得十分脆弱，針對這一問題，提出了基于快速移動節(jié)點的可信度模型FATM,以及基于快速移動節(jié)點的可信路由協(xié)議FARP,通過網(wǎng)絡(luò)中的快速移動節(jié)點輔助一般節(jié)點進(jìn)行可信度的計算和更新,并在可信模型建立之后選擇可信度較高的路由進(jìn)行通信。最后采用OPNET對FATM模型進(jìn)行了仿真,仿真結(jié)果表明基于快速移動節(jié)點的可信度模型的安全性更高,并且節(jié)省了一般節(jié)點的能量和空間開銷,具有較好的網(wǎng)絡(luò)適應(yīng)性及可擴(kuò)展性。

自組織網(wǎng)絡(luò);可信度模型;可信路由協(xié)議;快速移動節(jié)點

無線自組織網(wǎng)絡(luò)[1]MANET(Mobile Ad hoc network)是由一系列具有無線通信能力的節(jié)點構(gòu)成,不需要依賴現(xiàn)有固定通信設(shè)施,能夠臨時迅速展開使用的一種網(wǎng)絡(luò)體系,網(wǎng)絡(luò)中的節(jié)點既是主機(jī),又具有路由功能,可以滿足緊急情況下通信的需要[2]。與傳統(tǒng)的網(wǎng)絡(luò)需要基礎(chǔ)的通信設(shè)施不同,自組織網(wǎng)絡(luò)沒有控制中心,也不依賴預(yù)設(shè)的基礎(chǔ)設(shè)施,所有的結(jié)點處于平等的地位,可以快速構(gòu)建起一個無線通信網(wǎng)絡(luò),而且任一結(jié)點的故障都不會影響整個網(wǎng)絡(luò)的運(yùn)行,所以自組織網(wǎng)絡(luò)具有很強(qiáng)的抗毀性。由于無線信道本身的脆弱性,自組織網(wǎng)絡(luò)容易遭到竊聽、入侵、拒絕服務(wù)等攻擊,而且相比傳統(tǒng)的無線網(wǎng)絡(luò),自組織網(wǎng)絡(luò)沒有固定基礎(chǔ)設(shè)施,這一弱點就更為突出[3]。

1 快速移動節(jié)點的可信度模型

自組織網(wǎng)絡(luò)的特殊性使得傳統(tǒng)的信任模型很難適應(yīng)其網(wǎng)絡(luò)環(huán)境,為了降低可信模型過程中的計算量和資源消耗,同時滿足可信模型的快速建立和擴(kuò)展能力,本節(jié)提出了基于快速移動節(jié)點的可信度模型FATM(Fast-moving nodes assisted trust model),并對其進(jìn)行詳細(xì)的分析。

1.1 FATM模型引入

本文依據(jù)“移動性有益”[4]這一觀點來進(jìn)行模型的設(shè)計,這一理論是由Grossglauser和David于2002年提出的。該觀點認(rèn)為如果能夠有效利用自組織網(wǎng)絡(luò)中節(jié)點的移動性,非但不會降低網(wǎng)絡(luò)性能,反而會對網(wǎng)絡(luò)產(chǎn)生有利的影響[5]。目前自組織網(wǎng)絡(luò)的可信度模型大多沒有充分考慮到節(jié)點的能耗問題,導(dǎo)致網(wǎng)絡(luò)開銷增大,且不能保證迭代的收斂性[6]，為了解決這些問題本文提出了基于快速移動節(jié)點的可信度模型FATM,該模型發(fā)揮了網(wǎng)絡(luò)中少數(shù)快速移動節(jié)點的作用,對模型的建立、更新等起到了良好的輔助,同時也降低了一般節(jié)點的能量消耗,提高了網(wǎng)絡(luò)性能。為方便表述,引入一般節(jié)點和快速移動節(jié)點概念。一般節(jié)點指那些在自組織網(wǎng)絡(luò)中計算能力和節(jié)點能量較弱的節(jié)點,同時移動速度較低;快速移動節(jié)點指那些在自組織網(wǎng)絡(luò)中移動速度較快,計算能力和節(jié)點能量充足的節(jié)點[7]。

1.2 FATM模型設(shè)計

在FATM模型中,一般節(jié)點和快速移動節(jié)點的任務(wù)有所區(qū)別。一般節(jié)點主要完成對鄰居行為的監(jiān)聽,局部可信值的計算、儲存,以及數(shù)據(jù)包的轉(zhuǎn)發(fā)策略等。而快速移動節(jié)點主要負(fù)責(zé)全局可信值的收集、計算、更新等工作。

1.2.1 一般節(jié)點 FATM模型中的一般節(jié)點完成的工作主要是:監(jiān)聽鄰居信息,計算、儲存局部可信值,與快速移動節(jié)點進(jìn)行信息交互。圖1為一般節(jié)點的狀態(tài)轉(zhuǎn)移圖。

圖1 FATM模型的一般節(jié)點狀態(tài)轉(zhuǎn)移圖Fig.1 FATM general node state transition diagram of the model

1) 監(jiān)聽鄰居信息

每個一般節(jié)點在信任值的初始化完成后都將處于Idle狀態(tài),定時對鄰居發(fā)送的數(shù)據(jù)包進(jìn)行監(jiān)聽,判斷鄰居是否存在未轉(zhuǎn)發(fā)數(shù)據(jù)包、或是惡意篡改的行為,通過Update狀態(tài)來對鄰居消息進(jìn)行更新。監(jiān)聽鄰居信息的報文結(jié)構(gòu)如圖2所示。

圖2 鄰居信息報文Fig.2 Neighbor information message

節(jié)點通過監(jiān)聽來判斷鄰居是否轉(zhuǎn)發(fā)了自己的數(shù)據(jù)包,而由于鄰居轉(zhuǎn)發(fā)數(shù)據(jù)包的目的地址不是本節(jié)點,本節(jié)點的MAC層在收到數(shù)據(jù)包后會自動將包丟棄,因此需要對MAC協(xié)議進(jìn)行修改。節(jié)點在發(fā)送給鄰居數(shù)據(jù)包后,設(shè)置兩個時間閾值t1和t2,t1為正常情況下鄰居轉(zhuǎn)發(fā)數(shù)據(jù)包的時間,t2為網(wǎng)絡(luò)延遲非常大時鄰居轉(zhuǎn)發(fā)數(shù)據(jù)包的時間上限,t1

2) 與快速移動節(jié)點進(jìn)行可信值交互

每個一般節(jié)點維護(hù)一張信任列表Trust[N],其中記錄了對網(wǎng)絡(luò)中其他節(jié)點的信任值(范圍為0～1的實數(shù)),當(dāng)一般節(jié)點檢測到其周圍存在快速移動節(jié)點時,其有限狀態(tài)機(jī)進(jìn)入FN狀態(tài),將自己監(jiān)聽到的局部信息發(fā)送給快速移動節(jié)點,同時從快速移動節(jié)點接受網(wǎng)絡(luò)的全局信息。由于一般節(jié)點自身不進(jìn)行全局可信值的計算,因此這樣的交互過程,就使得一般節(jié)點以較小的計算量來獲得全局性的節(jié)點可信值[9]。

1.2.2 快速移動節(jié)點FATM模型中的快速移動節(jié)點狀態(tài)轉(zhuǎn)移圖如圖3所示。

圖3 FATM模型中快速移動節(jié)點的狀態(tài)轉(zhuǎn)移圖Fig.3 Fast moving nodes in the FATM model of the state transition diagram

快速移動節(jié)點在網(wǎng)絡(luò)的移動過程中,周期性地接受來自一般節(jié)點的鄰居監(jiān)視信息,收集一般節(jié)點報告信息構(gòu)成全局性的信息,并將網(wǎng)絡(luò)中節(jié)點的全局可信值及時更新到一般節(jié)點,使其能夠了解最新的全局信息。由于在網(wǎng)絡(luò)規(guī)模較大時,一般節(jié)點很難了解到與其相距較遠(yuǎn)節(jié)點的可信值,因此,快速移動節(jié)點在網(wǎng)絡(luò)中的移動使其可以迅速將全局可信值發(fā)送到一般節(jié)點。而一般節(jié)點在接收到來自快速移動節(jié)點的全局可信信息時,通過下式來更新自己的信任列表Trust[N][10]

T=α*TD+(1-α)*TI，

(1)

式(1)中,TD表示節(jié)點對目標(biāo)節(jié)點的直接信任值,TI表示節(jié)點接收來自快速移動節(jié)點的全局可信值。TI的計算由快速移動節(jié)點完成

(2)

式(2)中,TI(s,d)為節(jié)點s對d的推薦信任值,TD(s,i)為節(jié)點s對i的直接信任值,adj(s)為節(jié)點s的鄰居。當(dāng)TD為空,即節(jié)點不了解目標(biāo)節(jié)點的信任值時,直接將目標(biāo)節(jié)點的全局可信值TI作為對其的信任值。

1.2.3 模型分析FATM模型本質(zhì)上屬于混合式可信度模型,既通過節(jié)點的鄰居監(jiān)視機(jī)制來獲取局部性的可信值,又使用在網(wǎng)絡(luò)中快速移動的節(jié)點來將局部信息全局化。對一般節(jié)點的計算能力和能量要求較低,而且無須配備其他額外的功能。與其他可信度模型相比而言,FATM的一般節(jié)點在算法復(fù)雜度上與基于局部推薦的模型相當(dāng),而由于快速移動節(jié)點的作用,能夠得到節(jié)點在全局性的可信值。因此,FATM模型的實用性更好。

2 快速移動節(jié)點的可信路由協(xié)議

在自組織網(wǎng)絡(luò)中的節(jié)點相互之間建立了信任關(guān)系之后,節(jié)點在進(jìn)行相互通信時對網(wǎng)絡(luò)中的其他個體有了一個明確的認(rèn)識,節(jié)點行為也不再漫無目的,而受到可信度模型的約束。節(jié)點對其他節(jié)點的信任值,就成為其在通信過程中路由選擇的一個關(guān)鍵因素。為降低節(jié)點路由過程中的計算量及能量消耗,本節(jié)對DSDV路由協(xié)議進(jìn)行了改進(jìn),提出了基于快速移動節(jié)點的可信路由協(xié)議FARP(Fast-movingnodesAssistedRoutingProtocol)。

2.1 FARP協(xié)議

節(jié)點在建立了可信模型之后,如何在發(fā)送數(shù)據(jù)時進(jìn)行路由的選擇就成為下一個問題。傳統(tǒng)的安全路由協(xié)議是通過節(jié)點之間進(jìn)行加密認(rèn)證等身份信任的機(jī)制來保證通信的安全。而本文在FATM可信度模型的基礎(chǔ)上,選擇高可信度的路徑進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā),將高可信度的鄰居作為下一跳的轉(zhuǎn)發(fā)節(jié)點,從根本上避開了網(wǎng)絡(luò)中可信值較低的懶惰節(jié)點及惡意節(jié)點。

2.1.1 尋找最大可信路由的算法 在節(jié)點vi需要向目標(biāo)節(jié)點vj發(fā)送數(shù)據(jù)包時,為了選擇出可信值最高的通信路徑,FARP協(xié)議對dijkstra算法[11]進(jìn)行修改,dijkstra算法描述了節(jié)點如何選擇到目標(biāo)節(jié)點的最短路徑,類似地,FARP協(xié)議需要節(jié)點選擇出到目標(biāo)節(jié)點可信值最大的路徑。修改后的尋找可信值最大的路徑算法過程如下:

1)定義集合S存放已經(jīng)找到可信值最大路徑的節(jié)點,集合T存放目前尚未找到可信值最大路徑的節(jié)點,即滿足T=V-S。將S初始化為空集。從vi出發(fā)到網(wǎng)絡(luò)中其他節(jié)點vm最大可信初值為

D[m]=μ(vi,vm)，其中vm∈V。

2)選擇vn,使得D[m]=max{D[m]|vm∈V-S}，則vn就是當(dāng)前求得的一條從vi出發(fā)最大可信值的節(jié)點。令S=S∪{vn}。

3)修改從vi出發(fā)到集合V-S中任一節(jié)點vk的最大可信值。如果滿足D[n]*μ(vn,vk)>D[k]，則修改D[k]為D[k]=D[n]*μ(vn,vk)。

4)重復(fù)步驟(2)和(3),直到集合S包含網(wǎng)絡(luò)中所有節(jié)點,就可計算出節(jié)點vi到vj的最大可信值及最大可信路徑。

2.1.2FARP協(xié)議的工作過程 根據(jù)上一節(jié)對尋找最大可信路由算法的介紹,可知其時間及空間復(fù)雜度都較大,且由于源節(jié)點并不知道鄰居節(jié)點對其他節(jié)點的信任值,因此,一般節(jié)點無法對最大可信路由進(jìn)行計算。針對這一問題,本節(jié)采用一般節(jié)點向FN詢問的方法,具體工作過程如下:

1) 源節(jié)點在進(jìn)行數(shù)據(jù)發(fā)送時,首先查詢其周圍是否存在快速移動節(jié)點。

2) 如果周圍有快速移動節(jié)點,則向其發(fā)送可信路由的請求;如果沒有,則轉(zhuǎn)入步驟(5)。

3) 快速移動節(jié)點經(jīng)過計算后,將最大可信路徑發(fā)送給一般節(jié)點。

4) 一般節(jié)點根據(jù)最大可信路徑,進(jìn)行數(shù)據(jù)包的發(fā)送。轉(zhuǎn)入步驟(7)。

5) 節(jié)點在一個設(shè)定的時間閾值t內(nèi)繼續(xù)探測周圍是否有FN到來,如果出現(xiàn)FN,則轉(zhuǎn)入步驟(2),否則轉(zhuǎn)入步驟(6)。

6) 時間t內(nèi)仍然沒有快速移動節(jié)點出現(xiàn),則節(jié)點在其路由中選擇可信值最大的節(jié)點進(jìn)行轉(zhuǎn)發(fā)。

7) 節(jié)點發(fā)送數(shù)據(jù)包完成。

2.2 FARP協(xié)議的分析

在FARP協(xié)議中,一般節(jié)點進(jìn)行數(shù)據(jù)發(fā)送時,需要向FN發(fā)出最大可信路由請求。而由于此時一般節(jié)點周圍可能并不存在快速移動節(jié)點,因此一般節(jié)點的可信路由查詢過程需要一定的時間,由于節(jié)點與FN相鄰,固一般節(jié)點發(fā)送可信路由請求及接收快速移動節(jié)點的最大可信路由信息的時間相對較小。而FN較強(qiáng)的計算能力,使其計算最大路由的時間也相對較小。因此,節(jié)點周圍出現(xiàn)FN的時間,占據(jù)了可信路由查詢時間的主要部分?？梢哉J(rèn)為,節(jié)點在發(fā)送數(shù)據(jù)包時,一旦等到其周圍出現(xiàn)FN,則可以立即得到經(jīng)過FN計算的最大可信路由。

3 FATM與DSDV的仿真與分析

本節(jié)對FARP與傳統(tǒng)的預(yù)先式路由協(xié)議DSDV的路由性能進(jìn)行了仿真對比,研究了兩種協(xié)議的分組投遞率情況。仿真采用RWP作為節(jié)點的移動模型,默認(rèn)的網(wǎng)絡(luò)場景大小A*A為1000m*1000m,一般節(jié)點數(shù)N為100個,通信半徑r為50m,最大移動速度v為5m/s,快速移動節(jié)點個數(shù)M為20個,通信半徑R為100m,固定移動速度u為50m/s,惡意節(jié)點個數(shù)E占據(jù)一般節(jié)點的5%,仿真時間為600s。

路由協(xié)議的分組投遞率為目的節(jié)點收到的數(shù)據(jù)包個數(shù)與源節(jié)點發(fā)送的數(shù)據(jù)包個數(shù)之比。這個參數(shù)反映了網(wǎng)絡(luò)的吞吐量,表明了協(xié)議在不同網(wǎng)絡(luò)環(huán)境下的可用性及有效性。

3.1 惡意節(jié)點數(shù)目不同時候的分組投遞率

圖4為網(wǎng)絡(luò)中惡意節(jié)點數(shù)目變化時,FARP協(xié)議與DSDV協(xié)議的分組投遞率?？梢钥闯?在惡意節(jié)點數(shù)目增加時,DSDV協(xié)議的分組投遞率有明顯的下降,而FARP協(xié)議的分組投遞率的下降相對較小。這是由于,DSDV協(xié)議僅維護(hù)一個下一跳鄰居,而在惡意節(jié)點多的時候,其下一跳鄰居是惡意節(jié)點的概率會增大,使節(jié)點的數(shù)據(jù)包不能得到發(fā)送,從而造成分組投遞率的下降。而FARP協(xié)議的一般節(jié)點通過快速移動節(jié)點的輔助,能夠主動選擇最大可信路由進(jìn)行通信,從而避開了惡意節(jié)點,使得分組投遞率能夠保持在相對較高的水平。

圖4 惡意節(jié)點個數(shù)不同時的分組投遞率Fig.4 The packet delivery rate of different malicious nodes

3.2 一般節(jié)點通信半徑不同時候的分組投遞率

圖5為一般節(jié)點通信半徑不同時DSDV與FARP的分組投遞率。由圖4可見,隨著一般節(jié)點通信半徑的增加,DSDV和FARP協(xié)議的分組投遞率都有不同程度的增加。這是由于一般節(jié)點通信半徑越大,其能夠發(fā)送和接受數(shù)據(jù)包的距離越遠(yuǎn)。而FARP協(xié)議中一般節(jié)點通信半徑的增加,還使其與FN進(jìn)行可信值交互的范圍增大,能夠從FN獲得最大可信路由的幾率也增加,因此FARP協(xié)議的分組投遞率更高。

圖5 一般節(jié)點通信半徑不同時的分組投遞率Fig.5 The packet delivery rate of different general node communication radius

4 結(jié) 語

本文對基于快速移動節(jié)點的可信度模型FATM以及基于快速移動節(jié)點的可信路由協(xié)議FARP進(jìn)行了分析,并采用OPNET進(jìn)行計算機(jī)仿真實驗,將本文提出的可信路由協(xié)議與DSDV協(xié)議進(jìn)行了仿真對比。仿真結(jié)果表明,基于快速移動節(jié)點的信任模型和路由協(xié)議具有更高的安全性,并且能夠節(jié)省節(jié)點的能量消耗和空間開銷。

[1] BROWN K, VAIDYA H. Location-aided routing (LAR) in mobile Ad hoc networks[C]∥Dallas:Proceeding 4th ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom′98), 1998:66-75.

[2] BUCHEGGER S, MOLVA R. Nodes bearing grudges:Towards routing security,fairness,and robustness in mobile ad hoe networks[C]∥Los Angeles:10th Euromicro Workshop on Parallel,Distributed and Network-based Processing, 2002.

[3] PAPADIMITRATOS P, HAAS Z. Secure routing for mobile Ad hoc networks[C]∥San Antonio:Proceedings of the SCS communication Networks and Distributed Systems Modeling and Simulation Conference, 2002: 27-31.

[4] GROSSGLAUSER M, HALL D. Mobility increases the capacity of ad hoc wireless networks[J]. IEEE/ACM Transactions on Networking, August 2002, 10(4):477-486.

[5] LEINER M, ROBERT R, SASTRY R. Goals and challenges of the DARPA gloMo program[J]. IEEE Personal Communications, 1996,3(6):34-43.

[6] 宋雪呂,陸建德.基于組群的P2P系統(tǒng)中的信譽(yù)機(jī)制[J].微機(jī)發(fā)展,2005,15(11):11-13.

[7] SERGIO M, GIULI J. Mitigating routing misbehavior in mobile Ad hoc networks[C]∥Boston:Proceedings of 6th International Conference on Mobile Computing and Networking (MobiCom), 2000: 145-149.

[8] DAVID L. Transmission range control in multihop packet radio networks. communications[J]. IEEE Transactions on Communications, Jan 1986, 34(1):38-44.

[9] KEVIN L.E-learning markets and providers.some issues and prospects[J].Education Training,2001,43(4):233-239.

[10] LEBRON H. Transmission range control in multihop packet radio networks. communications[J]. IEEE Transactions on Communications, 1996, 34(1):38-44.

[11] BASAGNI S. A distance routing effect algorithm for mobility [C]∥Dallas: Proceeding 4th ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom′98), 1998:76-84.

(編 輯曹大剛)

Research on fasting-moving node assisted trust model and routing protocol in mobile Ad hoc networks

RAN Chong-shan, CHE Yu

(College of Electric & Information Engineering, Shaanxi University of Science & Technology, Xi′an 710021， China)

Current widely used routing protocols mostly assume the nodes in the network are cooperative and trustful, however, some nodes can easily be captured and become malicious node, making the routing protocols become weak, to design a secure routing protocol has become a serious problem. To solve this problem, This paper presents the reliability of FATM model based on fast moving nodes, and FARP based on trusted routing protocol, calculating and updating aided general node credibility by fast moving nodes in the network, and choosing high reliability communication routing after trusted model. Finally, OPNET is used in the simulation of the FATM model, the simulation results show that the security of the trust model based on fast moving nodes and trusted routing is higher, and saves energy and space than that on general nodes, and has better network adaptability and scalability.

Ad hoc; trust model; trust protocol; fast-moving nodes

2014-04-11

國家自然科學(xué)基金青年科學(xué)基金資助項目(61202019)

冉崇善，男，陜西富平人，陜西科技大學(xué)教授，從事分布式系統(tǒng)與計算機(jī)網(wǎng)絡(luò)、智能信息處理等研究。

TP319

：ADOI：10.16152/j.cnki.xdxbzr.2015-02-008