一種基于信任評(píng)估的連通支配集生成算法

黃慶東, 曹麗霞, 郭 歡, 袁潤(rùn)芝, 盧 茜

(西安郵電大學(xué) 通信與信息工程學(xué)院, 陜西 西安 710121)

無(wú)線自組織網(wǎng)絡(luò)是由大量帶有無(wú)線收發(fā)裝置的節(jié)點(diǎn)組成的多跳網(wǎng)絡(luò)，節(jié)點(diǎn)間通信不依靠基站、接入點(diǎn)等基礎(chǔ)設(shè)施，主要通過(guò)節(jié)點(diǎn)間的相互協(xié)作和自我組織快速構(gòu)建網(wǎng)絡(luò)并實(shí)現(xiàn)網(wǎng)絡(luò)通信，虛擬骨干網(wǎng)[1]的構(gòu)建在無(wú)線自組織網(wǎng)絡(luò)路由以及拓?fù)淇刂浦衅鹬陵P(guān)重要的作用。支配集是構(gòu)成骨干子網(wǎng)的節(jié)點(diǎn)集合，若支配集內(nèi)任意兩節(jié)點(diǎn)通過(guò)某路徑連通則稱為連通支配集(connected dominating set, CDS)，由連通支配集組成的虛擬骨干網(wǎng)可以有效管理網(wǎng)絡(luò)拓?fù)鋄2-3]，減少網(wǎng)絡(luò)信息的開(kāi)銷[4-5]。

基于功率選擇的連通支配集構(gòu)建算法[6]，以及考慮節(jié)點(diǎn)的覆蓋范圍和剩余能量構(gòu)建的支配集[7]，都是為了減少能量的消耗。文獻(xiàn)[8]考慮整個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)并對(duì)其進(jìn)行分簇，由簇頭節(jié)點(diǎn)組成連通支配集，不僅減少了支配集的規(guī)模還降低了網(wǎng)絡(luò)的信息開(kāi)銷。文獻(xiàn)[9]為得到最優(yōu)的連通支配集，在網(wǎng)絡(luò)中引入特征矢量中心性值對(duì)節(jié)點(diǎn)進(jìn)行編號(hào)，避免了節(jié)點(diǎn)縮減的隨機(jī)性，同時(shí)提出最大編號(hào)節(jié)點(diǎn)縮減規(guī)則，解決了在生成連通支配集時(shí)存在的完全NP難問(wèn)題。但是上述支配集構(gòu)建算法旨在縮減支配集的規(guī)模，節(jié)省能耗，均未考慮生成支配集時(shí)的網(wǎng)絡(luò)惡意節(jié)點(diǎn)攻擊問(wèn)題，而信任評(píng)估[10]作為抵抗節(jié)點(diǎn)攻擊的主要手段，可以有效避免無(wú)線自組織網(wǎng)絡(luò)受到惡意節(jié)點(diǎn)的攻擊[11]。為了去除惡意節(jié)點(diǎn)的虛假推薦信任，文獻(xiàn)[12]提出了一種不可信推薦信任檢測(cè)模型來(lái)過(guò)濾推薦值，對(duì)于可信推薦采用加權(quán)聚合的方式計(jì)算間接信任值，可以有效抵御誹謗、吹捧、隨機(jī)意見(jiàn)攻擊的影響。

信任評(píng)估是抵御網(wǎng)絡(luò)內(nèi)惡意節(jié)點(diǎn)攻擊的有效工具，基于此,文章在構(gòu)建連通支配集時(shí)引入間接信任評(píng)估機(jī)制來(lái)剔除支配集中存在的惡意節(jié)點(diǎn)，并對(duì)支配集的連通性進(jìn)行判定與維護(hù)得到可信連通支配集，然后縮減冗余支配節(jié)點(diǎn)，以此提高連通支配集的可靠性和有效性。

1 信任評(píng)估模型

無(wú)線自組織網(wǎng)絡(luò)中，節(jié)點(diǎn)的信任值被理解為該節(jié)點(diǎn)的可信程度，根據(jù)信任信息的來(lái)源將信任分為直接信任和推薦信任[13]。如圖1所示，節(jié)點(diǎn)i，j有直接的交互，i可通過(guò)監(jiān)測(cè)與j的直接交互經(jīng)驗(yàn)得出j的直接信任值Ti,j；而節(jié)點(diǎn)i，k沒(méi)有直接交互，i無(wú)法直接得出k的信任值，為增加信任評(píng)估的精確性需采用第三方節(jié)點(diǎn)j的推薦信任值Rj,k來(lái)評(píng)估節(jié)點(diǎn)k的信任值。

圖1 信任關(guān)系

被評(píng)估節(jié)點(diǎn)k的第j(j=1,2,…,n)個(gè)推薦值的偏差因子dj可表示為[12]

(1)

其中median()為求中值函數(shù),根據(jù)dj由大到小的順序?qū)ν扑]信任值進(jìn)行排序。CR是AR對(duì)應(yīng)于排序后的推薦信任集，依據(jù)排序順序從推薦節(jié)點(diǎn)集逐次逐個(gè)選擇可疑節(jié)點(diǎn)，補(bǔ)充放入可疑節(jié)點(diǎn)集SR，這樣每次SR會(huì)增加一個(gè)節(jié)點(diǎn)，逐次對(duì)其計(jì)算相應(yīng)的平滑因子[12]

s=|M[d(CR)-d(CR-SR)]|,

(2)

式中d(CR)表示所有偏差因子之和，CR-SR表示除可疑集后CR內(nèi)剩余元素組成的集合，M表示剩余元素個(gè)數(shù)。

間接信任評(píng)估機(jī)制實(shí)現(xiàn)過(guò)程：利用式(1)計(jì)算每個(gè)推薦信任的偏差因子；根據(jù)偏差因子由大到小的順序?qū)R排序得到集合CR，并按序從推薦節(jié)點(diǎn)集中逐個(gè)選擇可疑節(jié)點(diǎn)，補(bǔ)充放入可疑集SR，利用式(2)計(jì)算每個(gè)可疑集對(duì)應(yīng)的平滑因子s；選擇s最大的最小可疑集為不可信推薦集。

節(jié)點(diǎn)i得到節(jié)點(diǎn)k的平均推薦信任為

(3)

式中n為推薦節(jié)點(diǎn)數(shù)量；節(jié)點(diǎn)i對(duì)節(jié)點(diǎn)k的間接信任值[14]

(4)

其中，N為n個(gè)推薦節(jié)點(diǎn)中可信推薦節(jié)點(diǎn)數(shù)量。

2 基于信任評(píng)估的可信連通支配集生成算法

將支配集概念引入Ad Hoc網(wǎng)絡(luò)中構(gòu)建虛擬骨干網(wǎng)，網(wǎng)絡(luò)中的節(jié)點(diǎn)屬于支配集，或者屬于支配集的單跳鄰居。針對(duì)無(wú)線自組織網(wǎng)絡(luò)的惡意支配節(jié)點(diǎn)攻擊問(wèn)題，引入間接信任評(píng)估方式對(duì)于惡意節(jié)點(diǎn)進(jìn)行檢測(cè)，構(gòu)建可信支配集，并對(duì)由惡意支配節(jié)點(diǎn)的剔除造成的CDS連通性破壞問(wèn)題引入可達(dá)矩陣[15]進(jìn)行判定與修護(hù)，保障其承擔(dān)虛擬骨干網(wǎng)的功能。

假設(shè)可信支配集包含m個(gè)支配節(jié)點(diǎn){v1,v2,…,vm}，定義可達(dá)矩陣P=(pij)m×m

(5)

A為可信支配節(jié)點(diǎn)生成的鄰接矩陣，Am表示鄰接矩陣A的m次冪矩陣，對(duì)冪矩陣求和

Q=A+A2+…+Am,

(6)

將矩陣Q內(nèi)非零元素全部換為1，零元素不變即可求得可達(dá)矩陣P。

假設(shè)無(wú)線自組織網(wǎng)絡(luò)內(nèi)各節(jié)點(diǎn)位置確定并保持穩(wěn)定的拓?fù)浣Y(jié)構(gòu)，每個(gè)節(jié)點(diǎn)具有唯一的節(jié)點(diǎn)編號(hào)且均可與其鄰居節(jié)點(diǎn)建立穩(wěn)定的通信鏈路，評(píng)估節(jié)點(diǎn)為可信節(jié)點(diǎn)，惡意節(jié)點(diǎn)在網(wǎng)絡(luò)內(nèi)不僅可與其鄰居節(jié)點(diǎn)交換信息，而且對(duì)被評(píng)估節(jié)點(diǎn)發(fā)起誹謗、吹捧等攻擊，影響虛擬骨干網(wǎng)的可靠性。預(yù)定義迭代周期為T(mén)，可信連通支配集構(gòu)建算法具體過(guò)程如下。

步驟1根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，初始標(biāo)記支配節(jié)點(diǎn)[16]，依據(jù)網(wǎng)絡(luò)通信鏈路關(guān)系得到鄰接矩陣。

步驟2選擇網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)作為評(píng)估節(jié)點(diǎn)，評(píng)估節(jié)點(diǎn)的非鄰居節(jié)點(diǎn)依次作為被評(píng)估節(jié)點(diǎn)，利用鄰接矩陣尋找評(píng)估節(jié)點(diǎn)和被評(píng)估節(jié)點(diǎn)的共同鄰居作為推薦節(jié)點(diǎn)。

步驟3每一時(shí)刻t=1,2,…,T，評(píng)估節(jié)點(diǎn)收集到推薦節(jié)點(diǎn)對(duì)被評(píng)估節(jié)點(diǎn)的推薦信任集AR，及評(píng)估節(jié)點(diǎn)對(duì)于推薦節(jié)點(diǎn)的直接信任集BT，利用推薦信任檢測(cè)模型檢測(cè)出不可信節(jié)點(diǎn)，保留可信節(jié)點(diǎn)，并按式(3)和式(4)求被評(píng)估節(jié)點(diǎn)的平均推薦信任值和間接信任值。

步驟4判斷是否所有節(jié)點(diǎn)都經(jīng)過(guò)檢測(cè)，若是則檢測(cè)結(jié)束；否則重新從剩余節(jié)點(diǎn)內(nèi)選擇一個(gè)評(píng)估節(jié)點(diǎn)，對(duì)其非鄰居節(jié)點(diǎn)進(jìn)行評(píng)估，重復(fù)步驟3，直到所有的節(jié)點(diǎn)都經(jīng)過(guò)檢測(cè)為止，剔除檢測(cè)出的惡意支配節(jié)點(diǎn)得到可信支配集。

步驟5利用式(5)和式(6)計(jì)算可達(dá)矩陣P，判斷可信支配集的連通性。若可達(dá)矩陣P內(nèi)元素全為非零元素，則可信支配集連通，保存此可信支配集；若可達(dá)矩陣P內(nèi)存在零元素，則可信支配集不連通，執(zhí)行下一步。

步驟6若可信支配集不連通，尋找可信非支配節(jié)點(diǎn)中間接信任值最高的節(jié)點(diǎn)加入網(wǎng)絡(luò)，驗(yàn)證可信支配集連通性。若連通則將此節(jié)點(diǎn)加入可信支配集，選擇結(jié)束；若不連通，則重新選擇間接信任值次高的可信非支配節(jié)點(diǎn)加入可信支配集繼續(xù)判斷其連通性，以此類推直到可信支配集連通。

步驟7若一個(gè)可信非支配節(jié)點(diǎn)加入可信支配集仍然無(wú)法連通，那就需要選擇多個(gè)可信非支配節(jié)點(diǎn)加入，將間接信任值最高的可信非支配節(jié)點(diǎn)作為第一個(gè)新加入的支配節(jié)點(diǎn)，重復(fù)步驟6繼續(xù)選擇下一個(gè)可信非支配節(jié)點(diǎn)并驗(yàn)證其連通性，直到可信支配集連通。

步驟8對(duì)于可信連通支配集中存在的冗余支配節(jié)點(diǎn)，利用縮減規(guī)則[16]進(jìn)行縮減得出最小的可信連通支配集。

無(wú)線自組織網(wǎng)絡(luò)中可信支配集的構(gòu)建，保證了由連通支配集組成的虛擬骨干網(wǎng)的可靠性，使支配節(jié)點(diǎn)間的數(shù)據(jù)傳輸更加可靠安全，而且是完全分布式計(jì)算方法，方便在全網(wǎng)絡(luò)實(shí)施。

3 仿真結(jié)果及分析

利用Matlab2014a軟件對(duì)于改進(jìn)算法進(jìn)行仿真驗(yàn)證。假設(shè)在1×1的單位區(qū)域中隨機(jī)布署12個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，節(jié)點(diǎn)的身份地位均相同且節(jié)點(diǎn)間的歸一化通信距離為0.6，兩節(jié)點(diǎn)之間連線表示存在通信鏈路即在互相的通信范圍內(nèi)，網(wǎng)絡(luò)節(jié)點(diǎn)按照出現(xiàn)的先后順序進(jìn)行編號(hào)1～12。網(wǎng)絡(luò)中隨機(jī)設(shè)置一定數(shù)量的惡意節(jié)點(diǎn)，分別在誹謗攻擊、吹捧攻擊、隨機(jī)意見(jiàn)攻擊3種攻擊類型下對(duì)于惡意支配節(jié)點(diǎn)進(jìn)行檢測(cè)。

以圖2所示的網(wǎng)絡(luò)模型為例，網(wǎng)絡(luò)中惡意攻擊節(jié)點(diǎn)為{7,10}，用“★”符表示；初始標(biāo)記的支配節(jié)點(diǎn)為{1,2,3,4,5,6,8,10,11,12}，用“○”符表示；文獻(xiàn)[16]未加信任評(píng)估時(shí)網(wǎng)絡(luò)生成的連通支配集為{10,11,12}，用“□”符表示，惡意節(jié)點(diǎn){10}為支配節(jié)點(diǎn)，影響連通支配集的可靠性。

圖2 原連通支配集生成圖

可信支配集算法構(gòu)建過(guò)程如表1所示。表1中評(píng)估節(jié)點(diǎn)為2，被評(píng)估節(jié)點(diǎn)為7時(shí)，因?yàn)閮晒?jié)點(diǎn)無(wú)法直接交互，因此使用間接信任評(píng)估模型對(duì)于被評(píng)估節(jié)點(diǎn)進(jìn)行評(píng)估，推薦節(jié)點(diǎn)為{1,4,10,11}且對(duì)應(yīng)的推薦信任集和推薦者的可信集分別為

AR={0.47,0.485,0.282,0.425}，
BT={0.265,0.45,0.53,0.49}，

評(píng)估時(shí)首先利用式(1)計(jì)算每個(gè)推薦節(jié)點(diǎn)的偏差因子d，根據(jù)d由大到小的順序?qū)τ谕扑]信任值進(jìn)行排序得到

CR={0.282,0.485,0.47,0.425}，

排序后的推薦節(jié)點(diǎn)為{10,4,1,11}；其次按照CR排序順序依次選定可疑集合SR，每個(gè)可疑集合利用式(2)計(jì)算其平滑因子s，可疑集合

SR={0.282}

對(duì)應(yīng)的平滑因子最大(s=0.1551)，所以此可疑集合對(duì)應(yīng)的推薦節(jié)點(diǎn){10}為不可信節(jié)點(diǎn)，可信節(jié)點(diǎn)為{4,1,11}，以此類推將所有節(jié)點(diǎn)經(jīng)過(guò)信任評(píng)估。惡意支配節(jié)點(diǎn){10}從支配集中剔除掉，得到可信支配集{1,2,3,4,5,6,8,11,12}；利用可達(dá)矩陣判斷其連通性并修護(hù)，對(duì)可信連通支配集中的冗余支配節(jié)點(diǎn)縮減得到最小可信連通支配集為{8,11,12}，如圖3所示，“○”符表示網(wǎng)絡(luò)中初始標(biāo)記的支配節(jié)點(diǎn)為{1,2,3,4,5,6,8,10,11,12}；最小可信連通支配集為{8,11,12}，用“□”符表示。改進(jìn)算法在生成可信支配集時(shí)將惡意支配節(jié)點(diǎn)從初始標(biāo)記的支配節(jié)點(diǎn)集中剔除掉，選擇可信支配節(jié)點(diǎn)構(gòu)建連通支配集，從而使所生成的連通支配集更加可靠。

表1 可信支配集構(gòu)建算法描述

圖3 可信連通支配集生成圖

由于網(wǎng)絡(luò)拓?fù)潆S機(jī)生成，結(jié)果具有一定的偶然性，因此基于蒙特卡羅思想，獨(dú)立進(jìn)行100次實(shí)驗(yàn)，將其對(duì)應(yīng)的平均值作為節(jié)點(diǎn)的間接信任值和平均推薦信任值并在不同攻擊類型下與節(jié)點(diǎn)的實(shí)際信任值進(jìn)行對(duì)比分析，以此驗(yàn)證信任模型對(duì)于惡意節(jié)點(diǎn)檢測(cè)的有效性。

誹謗攻擊節(jié)點(diǎn)故意推薦較低的信任值給評(píng)估節(jié)點(diǎn)，降低被評(píng)估節(jié)點(diǎn)信任值。如圖4所示，可看出惡意節(jié)點(diǎn)存在時(shí)，被評(píng)估節(jié)點(diǎn)的平均推薦信任值低于其間接信任值和實(shí)際信任值；加入信任評(píng)估模型后濾除了惡意節(jié)點(diǎn)的推薦值，對(duì)于可信推薦值進(jìn)行聚合的間接信任與被評(píng)估節(jié)點(diǎn)的實(shí)際信任值近乎相等；而對(duì)于節(jié)點(diǎn)11評(píng)估時(shí)，因推薦節(jié)點(diǎn)中無(wú)惡意節(jié)點(diǎn)，所以間接信任、平均推薦信任都接近于實(shí)際信任值。

吹捧攻擊節(jié)點(diǎn)故意夸大被評(píng)估節(jié)點(diǎn)的信任值。如圖5所示，惡意節(jié)點(diǎn)存在時(shí)，被評(píng)估節(jié)點(diǎn)的平均推薦信任值高于節(jié)點(diǎn)聚合的間接信任值與實(shí)際信任值；而經(jīng)過(guò)信任檢測(cè)后由于濾除了惡意節(jié)點(diǎn)對(duì)于被評(píng)估節(jié)點(diǎn)的影響，得到的間接信任值與實(shí)際信任值近乎相等；而對(duì)節(jié)點(diǎn)11評(píng)估時(shí)，因?yàn)橥扑]節(jié)點(diǎn)內(nèi)沒(méi)有惡意節(jié)點(diǎn)，所以其實(shí)際信任值、平均推薦信任以及間接信任值幾乎相等。

圖4 誹謗攻擊時(shí)節(jié)點(diǎn)信任值

圖5 吹捧攻擊時(shí)節(jié)點(diǎn)信任值

隨機(jī)意見(jiàn)攻擊是以上兩種攻擊方式的合謀攻擊。如圖6所示，每個(gè)節(jié)點(diǎn)都經(jīng)過(guò)了信任評(píng)估，由于惡意節(jié)點(diǎn)的隨機(jī)意見(jiàn)攻擊，被評(píng)估節(jié)點(diǎn)的平均推薦信任值相對(duì)于間接信任值和實(shí)際信任值出現(xiàn)上下波動(dòng)；但是經(jīng)過(guò)信任評(píng)估后剔除了惡意節(jié)點(diǎn)的影響，聚合的間接信任值接近于節(jié)點(diǎn)的實(shí)際信任值；對(duì)于節(jié)點(diǎn){6,7}進(jìn)行評(píng)估時(shí)，由于推薦節(jié)點(diǎn)內(nèi)無(wú)惡意攻擊節(jié)點(diǎn)，所以得到的平均推薦信任、間接信任、實(shí)際信任值三者幾乎相等。

圖6 隨機(jī)意見(jiàn)攻擊時(shí)節(jié)點(diǎn)信任值

4 結(jié)語(yǔ)

通過(guò)分析無(wú)線自組織網(wǎng)絡(luò)中節(jié)點(diǎn)的信任評(píng)估機(jī)制，在構(gòu)建連通支配集時(shí)，結(jié)合節(jié)點(diǎn)信任評(píng)估提出了可信連通支配集的構(gòu)建方法。利用信任檢測(cè)模型對(duì)網(wǎng)絡(luò)中的惡意支配節(jié)點(diǎn)進(jìn)行篩選并剔除，由此導(dǎo)致的可信支配集不連通問(wèn)題采用選取可信節(jié)點(diǎn)加入的方式使可信支配集連通，其次對(duì)于可信連通支配集中的冗余支配節(jié)點(diǎn)進(jìn)行縮減得到最小可信連通支配集。仿真結(jié)果表明，改進(jìn)算法比原支配集算法，提升了虛擬骨干網(wǎng)的可靠性，且在抵抗誹謗、吹捧、隨機(jī)意見(jiàn)攻擊方面表現(xiàn)出良好的性能。