MANET中多角色的分簇信任評(píng)估模型

陸小玲,仲 紅,林群峰,石潤(rùn)華

(安徽大學(xué)計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室,合肥230039)

MANET中多角色的分簇信任評(píng)估模型

陸小玲,仲 紅,林群峰,石潤(rùn)華

(安徽大學(xué)計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室,合肥230039)

針對(duì)現(xiàn)有信任評(píng)估模型中簇頭選擇標(biāo)準(zhǔn)單一、不同角色節(jié)點(diǎn)信任值難以分配與更新的問(wèn)題,提出一種多角色的信任評(píng)估模型。將節(jié)點(diǎn)分成簇頭、簇成員、網(wǎng)關(guān)和代理4種角色,引入節(jié)點(diǎn)信任值、移動(dòng)性、相關(guān)度等多影響因子作為簇頭、網(wǎng)關(guān)和代理的選擇標(biāo)準(zhǔn),采用新穎簇頭節(jié)點(diǎn)的信任值計(jì)算方式。在簇內(nèi)簇頭節(jié)點(diǎn)的信任值由代理節(jié)點(diǎn)監(jiān)督計(jì)算。在簇間利用由簇頭、代理以及網(wǎng)關(guān)節(jié)點(diǎn)形成簡(jiǎn)化網(wǎng)絡(luò),根據(jù)社會(huì)網(wǎng)中人際關(guān)系的特點(diǎn)分配不同關(guān)系節(jié)點(diǎn)的可信度。NS2仿真實(shí)驗(yàn)結(jié)果表明,該模型能有效檢測(cè)出惡意節(jié)點(diǎn)并將其隔離,保證網(wǎng)絡(luò)的安全性。

移動(dòng)自組織網(wǎng)絡(luò);信任模型;分簇;代理;多角色節(jié)點(diǎn);NS2仿真

1 概述

移動(dòng)自組織網(wǎng)(Mobile Ad hoc Network, MANET)是由一組無(wú)線移動(dòng)節(jié)點(diǎn)組成的多跳、不依賴任何固定基礎(chǔ)設(shè)施的臨時(shí)網(wǎng)絡(luò)[1],網(wǎng)絡(luò)節(jié)點(diǎn)具有資源受限、內(nèi)存小以及計(jì)算能力差等缺點(diǎn),節(jié)點(diǎn)必須通過(guò)相互協(xié)作進(jìn)行網(wǎng)絡(luò)互聯(lián)和通信。移動(dòng)Ad Hoc網(wǎng)更容易遭受拒絕服務(wù)、被動(dòng)竊聽(tīng)、信息失真等網(wǎng)絡(luò)攻擊。信任是網(wǎng)絡(luò)安全的前提,信任評(píng)估能很好地處理網(wǎng)絡(luò)中節(jié)點(diǎn)的自私行為以及惡意行為;建立節(jié)點(diǎn)間的信任關(guān)系,提高網(wǎng)絡(luò)的性能以及安全性,信任模型成為其中的關(guān)鍵問(wèn)題。最初的移動(dòng)Ad Hoc網(wǎng)的信任評(píng)估研究多數(shù)都集中在平面結(jié)構(gòu)網(wǎng)[2]。隨著MANETs中節(jié)點(diǎn)數(shù)量的不斷增加,網(wǎng)絡(luò)規(guī)模受到平面結(jié)構(gòu)可擴(kuò)充性差的限制,網(wǎng)絡(luò)規(guī)模不受限制、可擴(kuò)充性好的分簇結(jié)構(gòu)網(wǎng)引起重視。如何建立適合分簇結(jié)構(gòu)的信任模型成為研究熱點(diǎn)之一。

在移動(dòng)自組織網(wǎng)分簇結(jié)構(gòu)研究初期主要是對(duì)分簇算法的研究。文獻(xiàn)[3]利用節(jié)點(diǎn)能量、相關(guān)度、距離以及移動(dòng)性的多因素作為簇頭選擇標(biāo)準(zhǔn),提出了包含權(quán)重的分簇算法(Weighted Clustering Algorithm,WCA)。該算法綜合考慮網(wǎng)絡(luò)均衡及穩(wěn)定性,以建立相對(duì)穩(wěn)定、生命周期長(zhǎng)的簇結(jié)構(gòu)。文獻(xiàn)[4]改進(jìn)了WCA算法中簇頭選擇中相關(guān)度因子的計(jì)算方法,利用曼哈頓距離計(jì)算節(jié)點(diǎn)與鄰居之間的距離,降低了距離計(jì)算上的困難。但上述分簇算法均存在一種不合理的假設(shè),即認(rèn)為網(wǎng)絡(luò)中不存在惡意節(jié)點(diǎn),算法中沒(méi)有任何的安全機(jī)制。當(dāng)信任評(píng)估被引入到MANETs時(shí),也有學(xué)者將信任值加入到分簇算法中,文獻(xiàn)[5]引入客觀信任度作為選擇簇頭的標(biāo)準(zhǔn),能力越強(qiáng)、越穩(wěn)定的節(jié)點(diǎn)被選作簇頭的可能性越大,但對(duì)實(shí)際網(wǎng)絡(luò)中節(jié)點(diǎn)行為的可信性評(píng)估并未納入評(píng)估范圍。文獻(xiàn)[6]提出分簇MANETs下的安全路由機(jī)制,利用節(jié)點(diǎn)聲譽(yù)作為簇頭選擇的唯一標(biāo)準(zhǔn)并使用動(dòng)態(tài)信譽(yù)閾值選擇路由。目前,分簇結(jié)構(gòu)信任評(píng)估模型,多數(shù)以信任值作為簇頭選擇標(biāo)準(zhǔn),建立節(jié)點(diǎn)間信任關(guān)系。文獻(xiàn)[7]將鄰居節(jié)點(diǎn)中具有最高信任度的節(jié)點(diǎn)選作簇頭,簇頭為成員節(jié)點(diǎn)發(fā)布信任值證書(shū)。但是節(jié)點(diǎn)一旦成為簇頭,則管理整個(gè)簇內(nèi)節(jié)點(diǎn)的信任值,它同樣也向陌生節(jié)點(diǎn)發(fā)布信任證書(shū),造成了新加入節(jié)點(diǎn)信任值的不確定性;由于模型中沒(méi)有對(duì)簇頭節(jié)點(diǎn)的信任更新,容易出現(xiàn)簇頭節(jié)點(diǎn)惡意導(dǎo)致網(wǎng)絡(luò)癱瘓等嚴(yán)重后果。文獻(xiàn)[8]針對(duì)簇頭瓶頸問(wèn)題,提出了代理節(jié)點(diǎn)輪流充當(dāng)簇頭,達(dá)到負(fù)載均衡的效果。文獻(xiàn)[9]提出的模型,保護(hù)了數(shù)據(jù)包在網(wǎng)絡(luò)中安全可信的路由傳輸,當(dāng)節(jié)點(diǎn)被認(rèn)為是不可信時(shí),數(shù)據(jù)包不會(huì)從這些節(jié)點(diǎn)轉(zhuǎn)發(fā)。該模型只建立了鄰居間的信任關(guān)系,然而,由于節(jié)點(diǎn)收集到的信息具有不完整和不確定性,只依靠鄰居監(jiān)測(cè)機(jī)制來(lái)評(píng)估節(jié)點(diǎn)顯然不合理的。

根據(jù)文獻(xiàn)[10]提出分簇網(wǎng)絡(luò)的安全框架,網(wǎng)絡(luò)中節(jié)點(diǎn)分為簇頭節(jié)點(diǎn)(CH)、網(wǎng)關(guān)節(jié)點(diǎn)(GW)和簇成員節(jié)點(diǎn)(CM),其中簇頭節(jié)點(diǎn)管理整個(gè)簇并通過(guò)網(wǎng)關(guān)節(jié)點(diǎn)實(shí)現(xiàn)簇間通信。簇頭節(jié)點(diǎn)承擔(dān)網(wǎng)絡(luò)中大多通信工作,網(wǎng)關(guān)節(jié)點(diǎn)對(duì)簇間通信極為重要,因此必須根據(jù)節(jié)點(diǎn)不同角色,來(lái)建立MANETs信任模型?；诖?本文提出一個(gè)新的評(píng)估模型,在分簇時(shí)考慮節(jié)點(diǎn)的信任值、相對(duì)移動(dòng)性等多方面因素,選擇合適的簇頭節(jié)點(diǎn),提高簇的安全性和穩(wěn)定性。利用信任值和穩(wěn)定性因素選擇網(wǎng)關(guān)節(jié)點(diǎn)。利用代理節(jié)點(diǎn),減少簇頭節(jié)點(diǎn)出現(xiàn)故障時(shí)生成新簇的代價(jià)。通過(guò)簇頭評(píng)估簇內(nèi)成員的信任值,代理節(jié)點(diǎn)監(jiān)督和計(jì)算簇頭在簇內(nèi)的信任值,減少信任評(píng)估的規(guī)模,節(jié)約計(jì)算開(kāi)銷,并根據(jù)簇頭、代理、網(wǎng)關(guān)節(jié)點(diǎn)形成的簡(jiǎn)化網(wǎng)絡(luò),建立簇頭間的動(dòng)態(tài)信任。

2 預(yù)備知識(shí)

2.1 信任的定義

定義1(信任) 節(jié)點(diǎn)i對(duì)j的信任是指在不斷交互中,節(jié)點(diǎn)i根據(jù)與j的歷史交互經(jīng)驗(yàn)和它人推薦形成的、對(duì)節(jié)點(diǎn)j能否按照自己意愿提供特定服務(wù)的質(zhì)量的度量[11]。

節(jié)點(diǎn)i對(duì)j的信任分為直接信任和推薦信任,圖1給出了信任評(píng)估過(guò)程。直接信任是指節(jié)點(diǎn)i根據(jù)與節(jié)點(diǎn)j直接歷史交互經(jīng)驗(yàn),形成的對(duì)j的評(píng)價(jià)信任值;推薦信任是指節(jié)點(diǎn)i根據(jù)其他節(jié)點(diǎn)對(duì)j的推薦值,形成的對(duì)節(jié)點(diǎn)j的評(píng)價(jià)。

圖1 信任評(píng)估過(guò)程

2.2 直接信任

在模糊關(guān)系理論[12]中,當(dāng)節(jié)點(diǎn)i認(rèn)為節(jié)點(diǎn)j可信或者不可信時(shí),i與j之間就存在一種信任關(guān)系;如果i的判斷來(lái)源于與j的直接交互經(jīng)驗(yàn),那么這種關(guān)系就為直接信任關(guān)系。E為所有節(jié)點(diǎn)的集合,DT為E×E上的模糊集,其隸屬度函數(shù)為:

即為節(jié)點(diǎn)i對(duì)j的直接信任度,它的值取決于i與j的直接歷史交互經(jīng)驗(yàn)。如果在過(guò)去一段時(shí)間內(nèi)i與j有多次成功交互,只有較少次數(shù)的失敗交互,那么節(jié)點(diǎn)i對(duì)j的信任度就高,反之則較低。

假設(shè)在過(guò)去一段時(shí)間,i認(rèn)為與j有p次成功交互,有q次失敗交互,模糊直接信任關(guān)系隸屬函數(shù)定義為:

隨著新的交互的發(fā)生,成功或失敗的次數(shù)會(huì)發(fā)生變化,信任值也會(huì)發(fā)生變化,這體現(xiàn)了信任的動(dòng)態(tài)性。式(1)給出利用模糊關(guān)系理論計(jì)算信任值的方法,但當(dāng)交互次數(shù)太少時(shí),式(1)得出的可信度可能會(huì)發(fā)生錯(cuò)誤。如單憑一次交互是否成功就決定是否信任對(duì)方是不合理的,因?yàn)橐淮谓换ゾ哂幸欢ǖ呐既恍?而信任度需要考察一段時(shí)間內(nèi)與對(duì)方交互的情況綜合評(píng)價(jià)得到。為此,將式(1)定義的隸屬度函數(shù)進(jìn)行修改,得到式(2):

其中,d1為交互次數(shù)閾值,d1＞0;避免由于交互次數(shù)過(guò)少而形成判斷的不準(zhǔn)確性,同時(shí)每個(gè)節(jié)點(diǎn)的交互次數(shù)閾值可以不同,由節(jié)點(diǎn)自行設(shè)定。

2.3 含權(quán)分簇算法

分簇網(wǎng)絡(luò)中節(jié)點(diǎn)之間的關(guān)系不同于平面結(jié)構(gòu)網(wǎng)絡(luò),網(wǎng)絡(luò)被劃分為多個(gè)簇,根據(jù)職責(zé)不同,節(jié)點(diǎn)被分為簇頭(CH)、網(wǎng)關(guān)節(jié)點(diǎn)(GW)和簇成員(CM)。GW位于2個(gè)簇的范圍內(nèi),負(fù)責(zé)2個(gè)簇之間的通信, CM通過(guò)CH節(jié)點(diǎn)和簇外節(jié)點(diǎn)通信,簇內(nèi)節(jié)點(diǎn)之間可以相互通信。簇頭作為一個(gè)簇的管理者、核心成員,擁有更大的能力和權(quán)限,同時(shí)為了簇結(jié)構(gòu)的穩(wěn)定性,簇頭節(jié)點(diǎn)的移動(dòng)性應(yīng)相對(duì)較小。合理的分簇算法有助于網(wǎng)絡(luò)的穩(wěn)定與安全。

文獻(xiàn)[3]提出的WCA分簇算法,采用最優(yōu)簇大小、電量、距離和運(yùn)動(dòng)性4個(gè)因素作為決定權(quán)值Wv的參數(shù)。

其中,Δv為簇頭理想可管理節(jié)點(diǎn)數(shù),即最優(yōu)簇大小與節(jié)點(diǎn)鄰居數(shù)之差;Dv為節(jié)點(diǎn)與其所有鄰居直接的物理距離總和;Mv為節(jié)點(diǎn)相對(duì)其鄰居節(jié)點(diǎn)的移動(dòng)速度;Pv為節(jié)點(diǎn)的電池電量。w1,w2,w3,w4為權(quán)重因子,協(xié)調(diào)各部分的比例關(guān)系,滿足w1+w2+w3+w4=1,全局范圍內(nèi)權(quán)值較小的節(jié)點(diǎn)被選作簇頭節(jié)點(diǎn)。

3 分簇結(jié)構(gòu)下多角色的信任評(píng)估模型

在分簇移動(dòng)自組織網(wǎng),簇頭和網(wǎng)關(guān)節(jié)點(diǎn)一旦出現(xiàn)問(wèn)題將導(dǎo)致網(wǎng)絡(luò)性能下降,甚至造成全網(wǎng)癱瘓。因此,在簇生成階段和維護(hù)過(guò)程中,需加強(qiáng)對(duì)簇頭和網(wǎng)關(guān)節(jié)點(diǎn)的安全監(jiān)督,以確保網(wǎng)絡(luò)的安全穩(wěn)定。本文模型優(yōu)化了對(duì)簇頭和網(wǎng)關(guān)的選取標(biāo)準(zhǔn),主要分成以下3個(gè)階段:簇生成階段,信任管理與更新階段,簇管理與維護(hù)階段。為了便于理解,先簡(jiǎn)單介紹文中標(biāo)號(hào)的含義。

節(jié)點(diǎn)信任值:T(下標(biāo)來(lái)區(qū)分不同節(jié)點(diǎn)的信任),如Ti表示節(jié)點(diǎn)在簇內(nèi)的信任,THi表示簇頭Hi的信任值,TGW表示網(wǎng)關(guān)節(jié)點(diǎn)的信任。

節(jié)點(diǎn)間的信任值:TR,如TRij表示簇成員節(jié)點(diǎn)間的信任值,TRH,i表示簇頭對(duì)成員的信任值,TRHi,Hj表示簇頭Hi對(duì)Hj的信任值。

3.1 簇生成階段

節(jié)點(diǎn)的信任值越高,說(shuō)明節(jié)點(diǎn)越安全,更適合被選作簇頭,將信任值作為簇頭選擇標(biāo)準(zhǔn)之一。同時(shí)為保障生成的簇結(jié)構(gòu)的穩(wěn)定性,引入WCA分簇算法中的節(jié)點(diǎn)相關(guān)度、移動(dòng)性、鄰居節(jié)點(diǎn)距離因素。本文假定節(jié)點(diǎn)初始能量一樣,綜合考慮上述信任值、相關(guān)度、移動(dòng)性和距離4個(gè)因素,每個(gè)節(jié)點(diǎn)計(jì)算得到一個(gè)權(quán)值W,利用權(quán)值的比較,選擇權(quán)值最大的節(jié)點(diǎn)作為簇頭。定義節(jié)點(diǎn)i權(quán)值的計(jì)算式如下:

其中,λ為各影響因子權(quán)重,λ1+λ2+λ3+λ4=1;Ti表示節(jié)點(diǎn)i的信任值,是節(jié)點(diǎn)i的所有一跳鄰居節(jié)點(diǎn)對(duì)i的總體評(píng)價(jià)。在成簇過(guò)程中,Ti是維護(hù)簇的可靠性的重要標(biāo)準(zhǔn),根據(jù)鄰居推薦機(jī)制,綜合計(jì)算出i在簇內(nèi)的信任值如式(5)所示:

其中,neighbors(i)為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)集合;n為其鄰居節(jié)點(diǎn)的個(gè)數(shù);dtki為節(jié)點(diǎn)k對(duì)i的直接信任。

根據(jù)上述簇頭選擇標(biāo)準(zhǔn),網(wǎng)絡(luò)中將生成多個(gè)簇,每個(gè)簇都有一個(gè)簇頭,簇頭管理簇內(nèi)節(jié)點(diǎn)的信任值,并為節(jié)點(diǎn)頒發(fā)信任值證書(shū)記為T(mén)RH,i。在簇結(jié)構(gòu)形成的初級(jí)階段,由于網(wǎng)絡(luò)中有限的交互經(jīng)驗(yàn),本文采用在簇頭競(jìng)爭(zhēng)時(shí)節(jié)點(diǎn)的Ti值作為i所在簇簇頭對(duì)i頒布的證書(shū)中的初始信任值。

網(wǎng)關(guān)節(jié)點(diǎn)處于2個(gè)簇內(nèi),為了維持簇結(jié)構(gòu)之間的穩(wěn)定可靠通信,需要合理選擇網(wǎng)關(guān)節(jié)點(diǎn);它的穩(wěn)定性和可信度成為考量重點(diǎn)。網(wǎng)關(guān)節(jié)點(diǎn)與兩簇頭間通信能耗主要與距離相關(guān)。選取策略:處于2個(gè)簇之內(nèi)的節(jié)點(diǎn)成為備選的網(wǎng)關(guān)節(jié)點(diǎn),若2個(gè)簇之間只有一個(gè)備選GW節(jié)點(diǎn),那么該節(jié)點(diǎn)成為網(wǎng)關(guān)節(jié)點(diǎn);若2個(gè)簇之間有多個(gè)備選GW節(jié)點(diǎn),則根據(jù)如式(6)評(píng)估節(jié)點(diǎn):

其中,TGW為2個(gè)簇頭節(jié)點(diǎn)對(duì)備選網(wǎng)關(guān)節(jié)點(diǎn)的平均信任值;DGW為備選網(wǎng)關(guān)節(jié)點(diǎn)與2個(gè)簇頭的距離總和;MGW為網(wǎng)關(guān)節(jié)點(diǎn)相對(duì)2個(gè)簇頭節(jié)點(diǎn)的平均速度。

算法1給出簇的生成過(guò)程,其生成的簇結(jié)構(gòu)如圖2所示。

算法1簇生成算法

(1)節(jié)點(diǎn)初始化

1)時(shí)間t內(nèi),每個(gè)節(jié)點(diǎn)向其鄰居發(fā)送一定數(shù)量的數(shù)據(jù)包;

2)根據(jù)對(duì)鄰居的監(jiān)測(cè),利用式(2)形成對(duì)其鄰居節(jié)點(diǎn)的直接信任dtij;

3)根據(jù)式(5)計(jì)算節(jié)點(diǎn)在其鄰居范圍內(nèi)的綜合信任值;

4)根據(jù)式(4)計(jì)算節(jié)點(diǎn)權(quán)值W。

(2)簇結(jié)構(gòu)建立

1)鄰居范圍內(nèi)選擇W值最大的節(jié)點(diǎn)成為簇頭CH;

2)根據(jù)式(6)計(jì)算備選網(wǎng)關(guān)節(jié)點(diǎn)的權(quán)值WGW,并選擇WGW最大的成為網(wǎng)關(guān)GW;

3)簇結(jié)構(gòu)生成,并在簇成員中選取權(quán)值W最大的節(jié)點(diǎn)為代理節(jié)點(diǎn)。

圖2 算法1生成的簇結(jié)構(gòu)

3.2 信任管理與更新

根據(jù)分簇結(jié)構(gòu)網(wǎng)絡(luò)特點(diǎn),信任評(píng)估主要分成2個(gè)部分:簇內(nèi)節(jié)點(diǎn)信任值的計(jì)算和簇間信任的傳遞與融合。簇頭管理簇中所有節(jié)點(diǎn)的信任值,并在每一次信任更新時(shí)為節(jié)點(diǎn)頒發(fā)新的信任證書(shū),確保信任信息的時(shí)效性。其中,根據(jù)節(jié)點(diǎn)的重要性,在簇內(nèi)的信任評(píng)估分為簇頭(CH)、簇成員(CM)和網(wǎng)關(guān)節(jié)點(diǎn)(GW)的信任計(jì)算。簇間信任主要是各簇頭間的信任評(píng)估。

3.2.1 簇內(nèi)信任

分簇結(jié)構(gòu)的特點(diǎn)是網(wǎng)絡(luò)中節(jié)點(diǎn)的地位不平等,根據(jù)節(jié)點(diǎn)職責(zé)不同,區(qū)別對(duì)待不同節(jié)點(diǎn)的信任計(jì)算。簇內(nèi)信任計(jì)算包括簇成員間的信任計(jì)算,網(wǎng)關(guān)節(jié)點(diǎn)的信任計(jì)算,以及簇頭信任值的計(jì)算。

簇成員信任計(jì)算:同一個(gè)簇中任意2個(gè)節(jié)點(diǎn)間的信任關(guān)系,i,j在同一個(gè)簇中,Sij為節(jié)點(diǎn)i與j之間交互成功的次數(shù),Fij為i與j之間交互失敗的次數(shù),算法2給出i對(duì)j的信任值計(jì)算

算法2簇成員i對(duì)j的信任計(jì)算

輸入Sij,Fij,TRH,j

輸出TRij

(1)根據(jù)式(2)計(jì)算i對(duì)j的直接信任值;

(2)利用簇頭節(jié)點(diǎn)對(duì)j的信任值TRH,j作為推薦信任;

(3)根據(jù)式(7)綜合計(jì)算則節(jié)點(diǎn)i對(duì)j的信任值:

其中,d2為節(jié)點(diǎn)信任閾值,若TRH,j＜d2則α=0,表示節(jié)點(diǎn)為惡意節(jié)點(diǎn),否則α=1;β為節(jié)點(diǎn)信任直接交互的程度。

網(wǎng)關(guān)節(jié)點(diǎn)信任計(jì)算:若節(jié)點(diǎn)j為網(wǎng)關(guān)節(jié)點(diǎn),它處于2個(gè)簇頭的通信范圍之內(nèi),則簇頭對(duì)j的信任值計(jì)算為式(8):

其中,TRH1,GW為簇1對(duì)j的信任值。

簇頭信任計(jì)算:簇頭是否可信影響整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)的穩(wěn)定與安全。對(duì)于簇頭的信任計(jì)算尤為重要。本文簇頭節(jié)點(diǎn)的信任值由代理節(jié)點(diǎn)計(jì)算并存儲(chǔ)。簇成員根據(jù)自己與簇頭的交互經(jīng)驗(yàn)形成對(duì)簇頭的評(píng)價(jià),并將評(píng)價(jià)推薦給代理節(jié)點(diǎn),形成一跳范圍內(nèi)的推薦網(wǎng)絡(luò),推薦權(quán)重為簇頭節(jié)點(diǎn)為簇內(nèi)頒發(fā)的信任值證書(shū)中的信任值,當(dāng)信任值低于一定閾值的節(jié)點(diǎn)進(jìn)行推薦,其推薦不被采納。簇頭Hi的信任值THi為:

其中,N為接納推薦的推薦節(jié)點(diǎn)的數(shù)目。當(dāng)簇頭信任值低于閾值時(shí),利用代理節(jié)點(diǎn)成為新的簇頭,管理整個(gè)簇,并選擇出新的代理節(jié)點(diǎn)。

3.2.2 簇間信任

簇間主要通過(guò)簇頭和網(wǎng)關(guān)來(lái)進(jìn)行通信,而相對(duì)簇間通信,簇內(nèi)通信更加頻繁,僅依靠簇頭間的交互信息不能準(zhǔn)確反映節(jié)點(diǎn)行為,所以本文將代理節(jié)點(diǎn)加入到簇頭與網(wǎng)關(guān)形成的網(wǎng)絡(luò)當(dāng)中,代理節(jié)點(diǎn)作為評(píng)估其所在簇簇頭節(jié)點(diǎn)時(shí)的信任推薦節(jié)點(diǎn)。整個(gè)網(wǎng)絡(luò)拓?fù)浜?jiǎn)化成由簇頭、網(wǎng)關(guān)和代理節(jié)點(diǎn)形成的網(wǎng)絡(luò),如圖3所示。

圖3 簇間信任評(píng)估簡(jiǎn)化模型

建立簇頭與簇頭間的信任關(guān)系,不僅需要直接信任,推薦信任證據(jù)將是計(jì)算其信任值的重要來(lái)源,推薦權(quán)重即推薦可信度(推薦節(jié)點(diǎn)提供信息的可信程度)成為關(guān)鍵問(wèn)題。在社會(huì)網(wǎng)絡(luò)中[13],人們往往根據(jù)與推薦者關(guān)系的親疏程度或者是否有過(guò)交互來(lái)衡量彼此推薦的可信度。借助社會(huì)網(wǎng),根據(jù)是否與主體S交互,可將推薦節(jié)點(diǎn)R細(xì)分為朋友節(jié)點(diǎn)和陌生節(jié)點(diǎn)。網(wǎng)絡(luò)中存在一種沒(méi)有與S直接交互,但是與S朋友節(jié)點(diǎn)有過(guò)交互的節(jié)點(diǎn),稱為偽朋友節(jié)點(diǎn);在陌生節(jié)點(diǎn)中,除了S的偽朋友節(jié)點(diǎn)之外的所有節(jié)點(diǎn)稱為純陌生節(jié)點(diǎn)。本文將整個(gè)推薦信息分成4類,分別是朋友節(jié)點(diǎn)、偽朋友節(jié)點(diǎn)、陌生節(jié)點(diǎn)的推薦以及被評(píng)估節(jié)點(diǎn)簇內(nèi)代理節(jié)點(diǎn)的推薦。推薦節(jié)點(diǎn)的個(gè)數(shù)為NR=NRf+NRpf+NRs。不同推薦節(jié)點(diǎn)與S之間形成不同的推薦網(wǎng)絡(luò),推薦可信度不一樣,以下已建立簇頭Hi對(duì)Hj的信任為例:

(1)朋友節(jié)點(diǎn)的推薦RF

對(duì)于朋友節(jié)點(diǎn)的推薦,利用對(duì)朋友節(jié)點(diǎn)的信任值作為推薦權(quán)重,則:

其中,p∈NRf是Hi的朋友節(jié)點(diǎn);DTip大于推薦閾值的推薦信息被接受。

(2)偽朋友節(jié)點(diǎn)的推薦RP

由于偽朋友節(jié)點(diǎn)可以通過(guò)朋友節(jié)點(diǎn)形成推薦網(wǎng)絡(luò),而對(duì)于源節(jié)點(diǎn)來(lái)說(shuō),離源節(jié)點(diǎn)越近的節(jié)點(diǎn)息更可靠,同時(shí),節(jié)點(diǎn)總是認(rèn)為與自己相似的節(jié)點(diǎn)更值得相信。以下給出定義:

定義2(節(jié)點(diǎn)相似度) 節(jié)點(diǎn)相似度指節(jié)點(diǎn)i,j對(duì)目標(biāo)節(jié)點(diǎn)評(píng)價(jià)的相似程度,記為Slr(i,j)。

定義3(節(jié)點(diǎn)層次) 節(jié)點(diǎn)層次指對(duì)于任意節(jié)點(diǎn)p,源節(jié)點(diǎn)s到p的最短距離Ds,稱為節(jié)點(diǎn)的層次,記為L(zhǎng)p=Ds。

節(jié)點(diǎn)相似度的計(jì)算:節(jié)點(diǎn)i,j對(duì)節(jié)點(diǎn)集set(i,j)中的節(jié)點(diǎn)有過(guò)交互,即有對(duì)其有評(píng)價(jià)值,則它們的評(píng)價(jià)差異度Diff為:

節(jié)點(diǎn)i,j的相似度為:

距離相關(guān)的推薦權(quán)重:

從s到推薦節(jié)點(diǎn)r的路徑上,節(jié)點(diǎn)s1對(duì)其后繼節(jié)點(diǎn)succ的直接信任值,則偽朋友節(jié)點(diǎn)的推薦可信度由式(12)、式(13)綜合得出為:

求出所有偽朋友節(jié)點(diǎn)推薦信任的總推薦信任值RP,利用式(14)可以計(jì)算偽朋友節(jié)點(diǎn)的推薦為:

其中,k∈NRpf是節(jié)點(diǎn)Hi的偽朋友節(jié)點(diǎn);RPij表示Hi偽朋友節(jié)點(diǎn)對(duì)目標(biāo)節(jié)點(diǎn)Hj的推薦信任值。

(3)陌生節(jié)點(diǎn)的推薦RS

評(píng)估陌生節(jié)點(diǎn)與源節(jié)點(diǎn)的相似度,只有高度相似節(jié)點(diǎn)的推薦才被接受,在實(shí)際的網(wǎng)絡(luò)環(huán)境中,為s提供推薦的R節(jié)點(diǎn)可能很多,不予限制地將所有推薦值加以考慮,在造成計(jì)算負(fù)擔(dān)的同時(shí)也極大地減小了推薦的效用,因此需要對(duì)推薦節(jié)點(diǎn)的規(guī)模加以控制。設(shè)置相似度閾值,控制陌生節(jié)點(diǎn)推薦數(shù)量,而且陌生節(jié)點(diǎn)的推薦可信度要低于偽朋友節(jié)點(diǎn)。利用推薦可信度加權(quán)平均計(jì)算出所有陌生節(jié)點(diǎn)對(duì)目標(biāo)節(jié)點(diǎn)Hj的推薦信任值RSij。

(4)代理節(jié)點(diǎn)的推薦

在對(duì)某一個(gè)簇頭節(jié)點(diǎn)進(jìn)行信任評(píng)估時(shí),同時(shí)要考慮代理節(jié)點(diǎn)對(duì)其的推薦,即簇內(nèi)節(jié)點(diǎn)對(duì)簇頭的評(píng)價(jià)值TH。若代理節(jié)點(diǎn)不參與推薦,則被認(rèn)為是不合作節(jié)點(diǎn),其所在簇頭可以使其簇成員重新選擇代理節(jié)點(diǎn)。源節(jié)點(diǎn)對(duì)于代理節(jié)點(diǎn)的推薦信任度為其信任度證書(shū)中的信任值。

簇頭Hi對(duì)Hj的信任,綜合上述4個(gè)方面的推薦信息、以及Hi與目標(biāo)節(jié)點(diǎn)Hj交互之后形成的直接信任得I對(duì)J的綜合評(píng)價(jià)TRHi,Hj:

其中,θ為不同推薦信息權(quán)值,θ1+θ2+θ3+θ4=1,若計(jì)算出的值過(guò)低,則可以向疑似不可信簇內(nèi)的代理節(jié)點(diǎn)發(fā)出重新計(jì)算簇頭信任值的要求,以共同維護(hù)簇的安全性。關(guān)于θ值的分配,根據(jù)社會(huì)網(wǎng)人際關(guān)系特點(diǎn)可知,θ1＞θ2＞θ3,θ4表示簇內(nèi)推薦權(quán)重,為了降低簇內(nèi)共謀提升簇頭節(jié)點(diǎn)信任帶來(lái)的影響,可適當(dāng)調(diào)整θ4的值。

3.3 簇的管理與維護(hù)

簇的管理包括簇節(jié)點(diǎn)的加入和退出。對(duì)于新節(jié)點(diǎn)N的加入,在分簇網(wǎng)絡(luò)中有2種情況:(1)N第一次加入網(wǎng)絡(luò),利用鄰居節(jié)點(diǎn)監(jiān)督,根據(jù)3.1節(jié)的式(5)計(jì)算出信任值,作為N的初始信任值;(2)N從簇1移動(dòng)到簇2,它在簇1中的表現(xiàn)即簇頭1為其頒布的信任證書(shū)中值為T(mén)1,N,作為簇頭1向新簇頭2的推薦信任值,推薦權(quán)重為新簇頭2對(duì)舊簇頭1的信任值,從而計(jì)算出N在簇2中的初始信任值,節(jié)省了前期觀察時(shí)間。2種情況中,若計(jì)算出節(jié)點(diǎn)的信任值低于一個(gè)閾值,采用不予以加入簇的處理方式。

簇的維護(hù)主要是對(duì)簇頭節(jié)點(diǎn)的維護(hù)。簇頭節(jié)點(diǎn)是一個(gè)簇的核心節(jié)點(diǎn),是尋找路由的關(guān)鍵。當(dāng)簇頭故障或不可信時(shí),需將簇頭節(jié)點(diǎn)隔離出網(wǎng)絡(luò),重新選擇簇頭。本文利用代理節(jié)點(diǎn)取代簇頭成為新的簇頭節(jié)點(diǎn),避免重新成簇的開(kāi)銷;然后新的簇頭節(jié)點(diǎn)根據(jù)式(3)選擇出一個(gè)可靠代理節(jié)點(diǎn),減少簇維護(hù)開(kāi)銷。

4 仿真實(shí)驗(yàn)與分析

目前對(duì)于信任模型的評(píng)價(jià)標(biāo)準(zhǔn)依然不明確,基本思想是將信任模型應(yīng)用到具體的路由協(xié)議[14]中,通過(guò)網(wǎng)絡(luò)的性能分析得到模型的可行性評(píng)估。所以本文利用NS2模擬實(shí)現(xiàn)了文獻(xiàn)[9]中基于信任分簇的路由協(xié)議CBTRP以及CBRP分簇路由協(xié)議。并將本文的信任模型(記為MRCTM)應(yīng)用到CBRP路由協(xié)議當(dāng)中,來(lái)評(píng)估模型的性能。CBRP中相鄰節(jié)點(diǎn)中ID最小的節(jié)點(diǎn)作為簇首,其一跳鄰居成為該簇首所在簇成員節(jié)點(diǎn),后續(xù)對(duì)于分簇算法的改進(jìn)大多數(shù)都是改進(jìn)CBRP中簇首選擇策略,CBRP具有代表性意義。CBTRP是在WCA的基礎(chǔ)上,定義了簇頭的信任閾值作為選擇標(biāo)準(zhǔn)之一,與本文模型有相似之處。本文中設(shè)置參數(shù)如表1所示,主要從數(shù)據(jù)包轉(zhuǎn)發(fā)率(PDR)的情況來(lái)分析本文模型的正確性及有效性。

表1 實(shí)驗(yàn)?zāi)M參數(shù)設(shè)置

圖4是仿真實(shí)驗(yàn)的NAM動(dòng)畫(huà)演示圖,圖中一共有20個(gè)節(jié)點(diǎn),此時(shí)節(jié)點(diǎn)6正向其鄰居節(jié)點(diǎn)發(fā)送數(shù)據(jù)包。在實(shí)驗(yàn)中,通過(guò)改變節(jié)點(diǎn)行為(設(shè)置惡意行為)來(lái)檢測(cè)模型的動(dòng)態(tài)適應(yīng)能力。

圖4 nam動(dòng)畫(huà)演示圖

圖5顯示了惡意節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)投遞率的影響,其中節(jié)點(diǎn)數(shù)為50,惡意節(jié)點(diǎn)比率為0～40%,節(jié)點(diǎn)的最大移動(dòng)速度設(shè)置為10 m/s。圖中說(shuō)明本文的MRCTM比CBRP有更高的數(shù)據(jù)包投遞率,同時(shí)2個(gè)個(gè)模型的數(shù)據(jù)包投遞率均隨著惡意節(jié)點(diǎn)的增多而降低,但是MRCTM比CBRP降低的速率要小,這是因?yàn)镸RCTM有信任機(jī)制檢測(cè)惡意節(jié)點(diǎn),并在路由中將惡意節(jié)點(diǎn)隔離出網(wǎng)絡(luò)。CBTRP在收集信任時(shí)只考慮鄰居節(jié)信息,在惡意節(jié)點(diǎn)信任的衰減方面相對(duì)MRCTM較慢,模型存在評(píng)估的片面性,對(duì)于諸如搖擺攻擊的節(jié)點(diǎn)很容易被認(rèn)為是可信的,所以,從圖中可以看出,MRCTM比CBTRP更能有效檢測(cè)惡意節(jié)點(diǎn),保持很好的網(wǎng)絡(luò)性能。

圖5 惡意節(jié)點(diǎn)對(duì)PDR的影響

傳統(tǒng)的CBRP以及CBTRP具有簇頭節(jié)點(diǎn)失效的瓶頸問(wèn)題,導(dǎo)致網(wǎng)絡(luò)的不穩(wěn)定,而本文提出的在每個(gè)簇內(nèi)選擇出一個(gè)可靠穩(wěn)定的代理節(jié)點(diǎn)作為備選節(jié)點(diǎn),同時(shí)提出的信任機(jī)制可以有效檢測(cè)出惡意節(jié)點(diǎn)。當(dāng)簇頭節(jié)點(diǎn)失效時(shí)能很好的保證網(wǎng)絡(luò)的穩(wěn)定性,避免在簇頭失效期間數(shù)據(jù)包的丟失現(xiàn)象。圖6顯示了在節(jié)點(diǎn)數(shù)增加時(shí)網(wǎng)絡(luò)數(shù)據(jù)包投遞率的變化,本文的代理節(jié)點(diǎn)模型比CBRP、CBTRP有更高的數(shù)據(jù)包投遞率。

圖6 網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)PDR的影響

在移動(dòng)自組網(wǎng)網(wǎng)中,移動(dòng)性是其最重要的特點(diǎn),所以本文實(shí)現(xiàn)比較不同節(jié)點(diǎn)移動(dòng)速度下網(wǎng)絡(luò)的性能。圖7分別是節(jié)點(diǎn)最大移動(dòng)速度為0,10 m/s,20 m/s時(shí)網(wǎng)絡(luò)的數(shù)據(jù)包投遞率,可以看出MRCTM在節(jié)點(diǎn)最大移動(dòng)速度為10 m/s時(shí)具有最好的效果,而在速度為0 m/s時(shí)效果最差,這是因?yàn)榇藭r(shí)網(wǎng)絡(luò)是靜止的,節(jié)點(diǎn)的鄰居不會(huì)變化,如果一個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)都是惡意節(jié)點(diǎn)的情況,數(shù)據(jù)包投遞率就會(huì)降低。當(dāng)節(jié)點(diǎn)是移動(dòng)的情況,找到不包含惡意節(jié)點(diǎn)的路由的可能性比較大,數(shù)據(jù)包成功投遞轉(zhuǎn)發(fā)的概率比較大。

圖7 節(jié)點(diǎn)移動(dòng)速度對(duì)PDR的影響

而當(dāng)節(jié)點(diǎn)移動(dòng)速度過(guò)大時(shí),節(jié)點(diǎn)間建立的路由極不穩(wěn)定,容易出現(xiàn)丟包現(xiàn)象。所以,網(wǎng)絡(luò)投遞率在節(jié)點(diǎn)速度為10 m/s時(shí)表現(xiàn)最好。

為了檢驗(yàn)本文模型能有效檢測(cè)出惡意節(jié)點(diǎn),在50個(gè)節(jié)點(diǎn)中隨機(jī)選擇3個(gè)節(jié)點(diǎn)作為待評(píng)估節(jié)點(diǎn),一個(gè)為簇頭節(jié)點(diǎn),另外2個(gè)為簇成員節(jié)點(diǎn),并在某8 s時(shí)設(shè)置其中一個(gè)簇成員節(jié)點(diǎn)為惡意節(jié)點(diǎn),開(kāi)始丟棄數(shù)據(jù)包,在20 s時(shí)使節(jié)點(diǎn)行為正常,查看節(jié)點(diǎn)的信任值變化。從圖8中的曲線可以看出,在模擬的初始階段3個(gè)節(jié)點(diǎn)由于正常行為,節(jié)點(diǎn)的信任值均保持較高的水平,但隨著設(shè)置節(jié)點(diǎn)惡意行為開(kāi)始,惡意節(jié)點(diǎn)信任值產(chǎn)生了迅速的下降,并在節(jié)點(diǎn)恢復(fù)正常時(shí)得到一定的升高。這體現(xiàn)模型的動(dòng)態(tài)性,能準(zhǔn)確檢測(cè)出節(jié)點(diǎn)的惡意行為。

圖8 不同節(jié)點(diǎn)的信任值變化

另外為了體現(xiàn)模型的可行性,分析了成簇的開(kāi)銷,圖9的曲線表示了隨著惡意節(jié)點(diǎn)增加,網(wǎng)絡(luò)中簇結(jié)構(gòu)的開(kāi)銷情況(包括簇頭的選舉以及成簇過(guò)程的開(kāi)銷),其中節(jié)點(diǎn)數(shù)為50。從圖中可以看出本文的MRCTM在隨著惡意節(jié)點(diǎn)增加的情況下,簇的控制開(kāi)銷增加并不多。

圖9 簇結(jié)構(gòu)開(kāi)銷

5 結(jié)束語(yǔ)

本文提出移動(dòng)自組織網(wǎng)下符合分簇結(jié)構(gòu)特性的信任評(píng)估模型,研究分簇結(jié)構(gòu)節(jié)點(diǎn)信任值難以分配和更新的問(wèn)題,將網(wǎng)絡(luò)節(jié)點(diǎn)分成簇頭、簇成員、網(wǎng)關(guān)以及代理節(jié)點(diǎn),引入節(jié)點(diǎn)信任值、移動(dòng)性、相關(guān)度、距離等因子作為選擇不同角色節(jié)點(diǎn)的標(biāo)準(zhǔn)。根據(jù)節(jié)點(diǎn)不同角色,分配不同的信任值計(jì)算方式,利用社會(huì)網(wǎng)絡(luò)的朋友關(guān)系特點(diǎn),建立信任傳遞和融合規(guī)則。本文通過(guò)NS2實(shí)驗(yàn)仿真,驗(yàn)證了提出模型的正確性及有效性。下一步工作是將本文的信任評(píng)估算法應(yīng)用到實(shí)際自組織網(wǎng)中,討論相關(guān)參數(shù)的取值,研究更加實(shí)用的分簇移動(dòng)自組織網(wǎng)的信任模型。

[1] 易 平,蔣嶷川,張世永,等.移動(dòng)Ad Hoc網(wǎng)絡(luò)安全綜述[J].電子學(xué)報(bào),2005,33(5):893-899.

[2] Aravindh S,Vinoth R S,Vijayan R.A Trust Based Approach for Detection and Isolation of Malicious Nodes in MANET[J].International Journal of Engineering Science&Technology,2013,5(2):193-199.

[3] Chatterjee M,Das S K,Turgut D.WCA:A Weighted Clustering Algorithm for Mobile Ad Hoc Networks[J]. Cluster Computing,2002,5(2):193-204.

[4] Thirumurugan S,Raj E.W-PAC:An Efficient Weighted Partitioning Around Cluster Head Mechanism for Ad Hoc Network[C]//Proceedings of the 2nd International Conference on Computational Science,Engineering and Information Technology.[S.1.]:ACM Press,2012: 182-188.

[5] 張 強(qiáng),胡光明,陳海濤,等.MANET基于客觀信任度建模的分簇算法與分析[J].通信學(xué)報(bào),2009,30(2): 12-21.

[6] Yu Y,Guo L,Wang X,et al.Routing Security Scheme Based on Reputation Evaluation in Hierarchical Ad Hoc Networks[J].Computer Networks,2010,54(9): 1460-1469.

[7] Jin S,ParkC,ChoiD,etal.Cluster-basedTrust Evaluation SchemeinanAdHocNetwork[J]. Electronics and Telecommunications Research Institute Journal,2005,27(4):465-468.

[8] Yassein M B,Hijazi N.Improvement on Cluster Based Routing Protocol by Using Vice Cluster Head[C]// Proceedings of the 4th International Conference on Next Generation Mobile Applications,Services and Technologies.[S.1.]:IEEE Press,2010:137-141.

[9] Safa H,Artail H,Tabet D.A Cluster-based Trust-aware Routing Protocol for Mobile Ad Hoc Networks[J]. Wireless Networks,2010,16(4):969-984.

[10] Bechler M,Hof H J,Kraft D,et al.A Cluster-based Security Architecture for Ad Hoc Networks[C]// Proceedings of INFOCOM’04.[S.1.]:IEEE Press, 2004:2393-2403.

[11] 李永軍,代亞非.對(duì)等網(wǎng)絡(luò)信任機(jī)制研究[J].計(jì)算機(jī)學(xué)報(bào),2010,33(3):390-405.

[12] 沈昌祥,張煥國(guó),王懷民,等.可信計(jì)算的研究與發(fā)展[J].中國(guó)科學(xué):信息科學(xué),2010,40(2):139-166.

[13] 甘早斌,丁 倩,李 開(kāi),等.基于聲譽(yù)的多維度信任計(jì)算算法[J].軟件學(xué)報(bào),2011,22(10):2401-2411.

[14] 孫 蘇,仲 紅,石潤(rùn)華,等.基于信任評(píng)估的Ad Hoc網(wǎng)絡(luò)安全路由協(xié)議[J].計(jì)算機(jī)工程,2012,38(20): 76-80.

編輯 索書(shū)志

Multi-role Clustering Trust Evaluation Model in MANET

LU Xiaoling,ZHONG Hong,LIN Qunfeng,SHI Runhua
(Key Laboratory of Intelligent Computing&Signal Processing,Ministry of Education,Anhui University,Hefei 230039,China)

With the development of Mobile Ad hoc Network(MANET),the study of trust evaluation in clustering structure becomes more popular nowadays.Most existing models use single criterion for head node selection,and have difficulties with assigning and updating trust value of the different roles.This paper proposes a new multi-role trust evaluation model.The node has four roles:cluster head,cluster members,gateways and agent.Thus,to compute the trust of cluster head,a new way comes out by using trust value,mobility and correlation degree of node as selecting criteria of cluster heads,gateways and agent.Inside each cluster,the trust of cluster head is computed by the agent node,for the trust between the clusters,a simplified network,which consists of cluster heads,gateways and agents,according to the characteristics of the social network relationships,assigns credit to different nodes,the agent’s recommends is taken into calculating the trust.NS2 simulation results show that the model can effectively detect and isolate the malicious nodes, thus ensure the security of the network.

Mobile Ad hoc Network(MANET);trust model;clustering;agent;multi-role node;NS2 simulation

陸小玲,仲 紅,林群峰,等.MANET中多角色的分簇信任評(píng)估模型[J].計(jì)算機(jī)工程, 2015,41(2):100-106.

英文引用格式:Lu Xiaoling,Zhong Hong,Lin Qunfeng,et al.Multi-role Clustering Trust Evaluation Model in MANET[J].Computer Engineering,2015,41(2):100-106.

1000-3428(2015)02-0100-07

:A

:TP309

10.3969/j.issn.1000-3428.2015.02.020

國(guó)家自然科學(xué)基金資助項(xiàng)目(61173188,61173187);安徽大學(xué)“211”工程基金資助項(xiàng)目(02303402)。

陸小玲(1989-),女,碩士研究生,主研方向:網(wǎng)絡(luò)與信息安全;仲 紅,教授、博士生導(dǎo)師;林群峰,碩士研究生;石潤(rùn)華,教授、博士。

2014-02-24

:2014-04-14E-mail:jalice610@163.com