魏妮妮，宋 翌

（武漢生物工程學(xué)院計(jì)算機(jī)與信息工程系，湖北武漢 430415）

Ad Hoc中互詢式節(jié)點(diǎn)信用度計(jì)算模型

魏妮妮，宋 翌

（武漢生物工程學(xué)院計(jì)算機(jī)與信息工程系，湖北武漢 430415）

網(wǎng)絡(luò)中節(jié)點(diǎn)的信用度在有效預(yù)防自私節(jié)點(diǎn)與惡意節(jié)點(diǎn)對(duì)Ad Hoc網(wǎng)絡(luò)性能的破壞方面起著十分重要的作用。針對(duì)Ad Hoc網(wǎng)絡(luò)中自私節(jié)點(diǎn)的存在導(dǎo)致拒絕轉(zhuǎn)發(fā)數(shù)據(jù)、降低網(wǎng)絡(luò)的轉(zhuǎn)發(fā)性能的問(wèn)題，通過(guò)一種量化指標(biāo)加強(qiáng)對(duì)節(jié)點(diǎn)行為的監(jiān)控，提出了一種新的基于互詢式的節(jié)點(diǎn)信用度計(jì)算模型。研究了該模型的實(shí)現(xiàn)機(jī)理，并從網(wǎng)絡(luò)丟包率和節(jié)點(diǎn)信用度值變化等角度闡述了此模型的優(yōu)勢(shì)與可行性。使用NS2進(jìn)行仿真，計(jì)算模型能夠較精確地反映出節(jié)點(diǎn)的信任度，有效地制止節(jié)點(diǎn)惡意行為的發(fā)生。

信用度計(jì)算模型；Ad Hoc網(wǎng)絡(luò)；自私節(jié)點(diǎn)；互詢式

Ad Hoc網(wǎng)絡(luò)是一種非中心控制、節(jié)點(diǎn)可動(dòng)態(tài)變化的網(wǎng)絡(luò)環(huán)境。它具有自組織、自恢復(fù)的特點(diǎn)，在軍事、救災(zāi)等各種需要臨時(shí)建立通信網(wǎng)絡(luò)的場(chǎng)合有著廣泛的應(yīng)用［1-2］。

在Ad Hoc網(wǎng)絡(luò)中通過(guò)移動(dòng)節(jié)點(diǎn)間的相互協(xié)作保持互聯(lián)，但是在通信中有些節(jié)點(diǎn)為了保護(hù)自己有限的資源或者能量，可能對(duì)臨近節(jié)點(diǎn)要求轉(zhuǎn)發(fā)的數(shù)據(jù)包不進(jìn)行轉(zhuǎn)發(fā)，從而造成網(wǎng)絡(luò)中節(jié)點(diǎn)間很少合作［3］，這類節(jié)點(diǎn)稱之為自私節(jié)點(diǎn)。自私節(jié)點(diǎn)通過(guò)簡(jiǎn)單的不參與網(wǎng)絡(luò)操作而導(dǎo)致網(wǎng)絡(luò)的分割，使網(wǎng)絡(luò)的性能嚴(yán)重降低［4-5］。有些文獻(xiàn)［6-7］中曾經(jīng)對(duì)使用DSR路由協(xié)議時(shí)自私節(jié)點(diǎn)的惡意行為對(duì)于整個(gè)網(wǎng)絡(luò)的通信延遲和吞吐量所產(chǎn)生的影響進(jìn)行了仿真實(shí)驗(yàn)，研究結(jié)果表明：在整個(gè)網(wǎng)絡(luò)中即使自私節(jié)點(diǎn)的比例很小，也會(huì)使整個(gè)網(wǎng)絡(luò)的性能嚴(yán)重下降［8］。因此移動(dòng)Ad Hoc網(wǎng)絡(luò)安全中的很重要的一方面就是如何增強(qiáng)移動(dòng)Ad Hoc網(wǎng)絡(luò)節(jié)點(diǎn)間的協(xié)作性。

為了防止上述自私節(jié)點(diǎn)轉(zhuǎn)發(fā)掉包的惡意行為發(fā)生，嚴(yán)重惡化網(wǎng)絡(luò)的性能，世界上有許多組織和個(gè)人對(duì)此問(wèn)題進(jìn)行了深入的研究?，F(xiàn)有的方法主要是對(duì)Ad Hoc網(wǎng)絡(luò)節(jié)點(diǎn)信用度的度量和對(duì)節(jié)點(diǎn)惡意行為的檢測(cè)，以及在此基礎(chǔ)上建立的模型，例如：Marti，Giuli，Lai，Baker提出的watchdog ＆pathrater模型［9］；Michiardi與Molva提出的collaborative reputation（CORE）機(jī)制［10］；Paul與westhoff提出的Context-Aware Detection機(jī)制等。上述這些方法的模型都是在強(qiáng)調(diào)結(jié)點(diǎn)某一時(shí)刻的行為狀況或者是在增大網(wǎng)絡(luò)負(fù)載的情況下有較好的效果，但是，在解決此類問(wèn)題的同時(shí)降低了網(wǎng)絡(luò)的安全性。

1 基于互詢式節(jié)點(diǎn)的信用度計(jì)算模型

本文中提出了一種基于互詢式的網(wǎng)絡(luò)節(jié)點(diǎn)信用度的計(jì)算模型。這個(gè)模型的思想是通過(guò)對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的歷史信用度和當(dāng)前信用度的綜合評(píng)價(jià)，得到此節(jié)點(diǎn)某一段時(shí)間內(nèi)的可信任度，從而可較精確地反映網(wǎng)絡(luò)中惡意行為的出現(xiàn)狀況。同時(shí)當(dāng)節(jié)點(diǎn)信用度低于設(shè)定的閥值后，采用廣播的方式對(duì)鄰接區(qū)的節(jié)點(diǎn)發(fā)出警告，孤立惡意結(jié)點(diǎn)，使得網(wǎng)絡(luò)能夠保證有較高的安全性。

互詢式節(jié)點(diǎn)信用度模型機(jī)制是通過(guò)在各個(gè)節(jié)點(diǎn)之間建立互詢機(jī)制，以及在各個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)上建立一個(gè)信任度管理模塊來(lái)構(gòu)成的（如圖1所示）。文中所涉及的節(jié)點(diǎn)鄰接區(qū)域?qū)Ｖ负痛私Y(jié)點(diǎn)只有一跳距離的節(jié)點(diǎn)。

圖1 互詢式的節(jié)點(diǎn)的信用度計(jì)算模型

1.1 節(jié)點(diǎn)信任度管理模塊

本模型中節(jié)點(diǎn)信任度管理模塊是由節(jié)點(diǎn)信任信息搜尋子模塊、節(jié)點(diǎn)信任度信息交換管理子模塊、節(jié)點(diǎn)信任信息維護(hù)子模塊和節(jié)點(diǎn)信任度信息的度量子模塊4個(gè)部分組成。

1.1.1 節(jié)點(diǎn)信任信息搜尋子模塊

節(jié)點(diǎn)信任信息的搜尋是初始化節(jié)點(diǎn)信任管理模塊的第一步。通常情況下，搜尋出節(jié)點(diǎn)的信任信息可以通過(guò)以下2種方式獲得：（1）直接搜尋方式。結(jié)點(diǎn)A利用自己的監(jiān)測(cè)子模塊直接對(duì)于某個(gè)節(jié)點(diǎn)B是否有惡意行為做出判斷。（2）互詢與通知方式。當(dāng)節(jié)點(diǎn)A想獲得另外一個(gè)節(jié)點(diǎn)B的信用度時(shí)，就會(huì)向B的鄰居節(jié)點(diǎn)發(fā)出詢問(wèn)，并等待這些節(jié)點(diǎn)的信用度回復(fù)。在收到回復(fù)后，利用一定的計(jì)算方法，對(duì)所詢問(wèn)節(jié)點(diǎn)的信用度進(jìn)行計(jì)算，當(dāng)發(fā)現(xiàn)所詢問(wèn)節(jié)點(diǎn)的信用度值數(shù)小于規(guī)定的閥值時(shí)，可向B點(diǎn)的鄰接節(jié)點(diǎn)以廣播的方式通知——B節(jié)點(diǎn)已不可信任。

1.1.2 節(jié)點(diǎn)信任度信息交換管理子模塊

通過(guò)對(duì)節(jié)點(diǎn)的信任信息搜尋之后，節(jié)點(diǎn)獲得了某個(gè)節(jié)點(diǎn)的信用度信息，然后通過(guò)一種消息傳送機(jī)制在節(jié)點(diǎn)中交換彼此的信息。節(jié)點(diǎn)的信任度信息交換格式為

M E S S A G E＿T Y P E N O D E＿I D R E U＿V A L

其中的“MESSAGE＿TYPE”代表交換信息的類型。本文將交換的消息分為3類：MESSAGE＿QUE、MESSAGE＿RESPONSE和MESSAGE＿BROCAST。MESSAGE＿QUE表示一個(gè)節(jié)點(diǎn)向某個(gè)節(jié)點(diǎn)發(fā)出的信息是用于向其詢問(wèn)與它關(guān)聯(lián)節(jié)點(diǎn)的信任度；MESSAGE＿RESPONSE表示發(fā)出的消息是一個(gè)節(jié)點(diǎn)對(duì)于某個(gè)節(jié)點(diǎn)信任度值進(jìn)行咨詢的應(yīng)答；MESSAGE＿BROCAST表示發(fā)出的消息是用于廣播節(jié)點(diǎn)信用度信息?！癗ODE＿ID”表示有惡意行為的節(jié)點(diǎn)或者想加入網(wǎng)絡(luò)進(jìn)行通信的新節(jié)點(diǎn)的IP地址。“REU＿VAL”是具體的數(shù)值，用于表示節(jié)點(diǎn)信用度的大小，它存儲(chǔ)在每個(gè)節(jié)點(diǎn)信用度表中。

1.1.3 節(jié)點(diǎn)信任信息維護(hù)子模塊

在此機(jī)制中我們?yōu)槊總€(gè)節(jié)點(diǎn)建立了一張用于存儲(chǔ)信用度值的表。節(jié)點(diǎn)信用度值存儲(chǔ)格式為

N O D E＿I D R E U＿V A L

通過(guò)對(duì)節(jié)點(diǎn)信息進(jìn)行監(jiān)測(cè)、搜集和交換后可以獲得周圍鄰接節(jié)點(diǎn)的信用度值，并采用下述互詢模式下的信用度計(jì)算機(jī)制對(duì)搜集到的信息進(jìn)行綜合的評(píng)價(jià)和定量，然后儲(chǔ)存在節(jié)點(diǎn)信用度表中。節(jié)點(diǎn)的信任信息維護(hù)功能就是使表內(nèi)的數(shù)值與節(jié)點(diǎn)的信用度變化后的值保持一致。

1.1.4 節(jié)點(diǎn)信任度信息度量子模塊

在此機(jī)制中，對(duì)節(jié)點(diǎn)信用度的度量采用一個(gè)［0，1］之間的數(shù)值?！?”表示節(jié)點(diǎn)完全不可信任，“1”表示節(jié)點(diǎn)是完全可信的。數(shù)字越小，表明此節(jié)點(diǎn)的信用度越低，反之表明越高。當(dāng)網(wǎng)絡(luò)初始化時(shí)節(jié)點(diǎn)的信用度值都為1，表明節(jié)點(diǎn)都是可信的，隨著時(shí)間的推移，節(jié)點(diǎn)的信任值開(kāi)始發(fā)生變化。

1.2 節(jié)點(diǎn)信任度監(jiān)測(cè)模塊

節(jié)點(diǎn)信任度監(jiān)測(cè)模塊主要負(fù)責(zé)對(duì)鄰接點(diǎn)的行為進(jìn)行監(jiān)視檢測(cè)，它是以互詢式的節(jié)點(diǎn)信用度計(jì)算機(jī)制為運(yùn)行基礎(chǔ)。在Ad Hoc網(wǎng)絡(luò)中由于采用的是對(duì)稱和混合接受的工作模式，任意節(jié)點(diǎn)都可以對(duì)其鄰居節(jié)點(diǎn)的工作過(guò)程進(jìn)行監(jiān)聽(tīng)，為此可檢測(cè)出其鄰居節(jié)點(diǎn)是否為自私節(jié)點(diǎn)，并將監(jiān)聽(tīng)結(jié)果返回給節(jié)點(diǎn)信任信息維護(hù)子模塊，以此來(lái)更新節(jié)點(diǎn)信用度值。

本文所討論的節(jié)點(diǎn)惡意行為是指由于節(jié)點(diǎn)能源問(wèn)題而發(fā)生的丟包與拒絕服務(wù)。節(jié)點(diǎn)信用度值的大小是通過(guò)上述模塊內(nèi)部的計(jì)算機(jī)制來(lái)實(shí)現(xiàn)的。

設(shè)節(jié)點(diǎn)a在某個(gè)時(shí)間t內(nèi)向結(jié)點(diǎn)b發(fā)出了n個(gè)數(shù)據(jù)包，而b成功轉(zhuǎn)發(fā)了m個(gè)，那么節(jié)點(diǎn)b對(duì)于節(jié)點(diǎn)a的信用度R（a，b）則采用以下公式計(jì)算

假設(shè)節(jié)點(diǎn)a和b在Ad Hoc網(wǎng)內(nèi)第一次相遇，通過(guò)初始設(shè)置，2個(gè)節(jié)點(diǎn)a，b的信任管理機(jī)制均進(jìn)入工作狀態(tài)。初始狀態(tài)下，2個(gè)節(jié)點(diǎn)之間開(kāi)始通信，此時(shí)2個(gè)節(jié)點(diǎn)信用度值都設(shè)定為1。

在某個(gè)時(shí)刻t內(nèi)，節(jié)點(diǎn)a通過(guò)自己的監(jiān)測(cè)模塊發(fā)現(xiàn)了節(jié)點(diǎn)b的惡意行為，于是需要更新自己信用度表內(nèi)對(duì)于節(jié)點(diǎn)b信用度的數(shù)據(jù)。我們?cè)谟?jì)算節(jié)點(diǎn)b信用度的同時(shí)，一定要考慮節(jié)點(diǎn)b的歷史記錄與現(xiàn)在所獲值的大小，這樣才能對(duì)節(jié)點(diǎn)b的信用度給出客觀、準(zhǔn)確的評(píng)價(jià)。為此節(jié)點(diǎn)b對(duì)于節(jié)點(diǎn)a的信用度R（a，b）用公式（2）來(lái)描述

在公式（2）中，A表示權(quán)值系數(shù)，它是0到1之間的一個(gè)數(shù)值。Rold（a，b）是節(jié)點(diǎn)b相對(duì)于節(jié)點(diǎn)a的歷史信用度值。而Rcur（a，b）則是通過(guò)公式（1）計(jì)算出的節(jié)點(diǎn)b新的信用度值，將兩者按照A的比例調(diào)整求和，可以較客觀地得到節(jié)點(diǎn)b對(duì)于節(jié)點(diǎn)a的可信任度。

當(dāng)節(jié)點(diǎn)a與節(jié)點(diǎn)b通信一段時(shí)間后，有一個(gè)新節(jié)點(diǎn)c加入了Ad Hoc網(wǎng)絡(luò)進(jìn)行通信，那么此時(shí)節(jié)點(diǎn)b的節(jié)點(diǎn)信用度如何得到并保持更新呢？通過(guò)前面所述的互詢機(jī)制，可知，一旦發(fā)現(xiàn)節(jié)點(diǎn)b出現(xiàn)惡意行為，則節(jié)點(diǎn)a在監(jiān)測(cè)到此惡意行為的前提下，將重新計(jì)算的節(jié)點(diǎn)b當(dāng)前信用度值，并向其鄰接區(qū)域的節(jié)點(diǎn)以消息機(jī)制進(jìn)行廣播，節(jié)點(diǎn)c接收到這個(gè)值，再按照下面的公式對(duì)節(jié)點(diǎn)b的信用度值重新進(jìn)行更新估算。

通過(guò)公式（3）可知：只要一個(gè)節(jié)點(diǎn)a能夠監(jiān)測(cè)出另外一個(gè)節(jié)點(diǎn)b的惡意行為，就可以按照公式（3）對(duì)此節(jié)點(diǎn)的信用度值進(jìn)行廣播。當(dāng)節(jié)點(diǎn)b的信用度值小于系統(tǒng)設(shè)定的門限值，它的鄰居節(jié)點(diǎn)就都能夠發(fā)現(xiàn)這種惡意行為，從而采取一定的措施來(lái)確保網(wǎng)絡(luò)通信的暢通。

由上述可知：對(duì)于Ad Hoc網(wǎng)絡(luò)內(nèi)的所有節(jié)點(diǎn)都可按照上述機(jī)制通過(guò)互詢與更新方式來(lái)完成對(duì)各個(gè)節(jié)點(diǎn)信用度值的計(jì)算，從而達(dá)到對(duì)網(wǎng)絡(luò)內(nèi)部自私節(jié)點(diǎn)惡意行為的有效監(jiān)測(cè)。

2 仿真與性能分析

為了驗(yàn)證基于互詢式的節(jié)點(diǎn)信用度計(jì)算機(jī)制的有效性，我們采用NS2進(jìn)行了仿真測(cè)試，仿真環(huán)境構(gòu)造如下：在一個(gè)1 000m×500m的矩形區(qū)域內(nèi)均勻分布隨機(jī)產(chǎn)生的22個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有64PAC大小的緩沖區(qū)，300s的暫停時(shí)間，惡意節(jié)點(diǎn)的產(chǎn)生按照馬爾可夫鏈機(jī)制隨即產(chǎn)生5個(gè)，掉包率控制在1%～8%。在實(shí)驗(yàn)中主要從網(wǎng)絡(luò)掉包率、節(jié)點(diǎn)信用值變化2個(gè)角度來(lái)驗(yàn)證本文提出機(jī)制的有效性。

圖2顯示了在設(shè)定時(shí)間內(nèi)一個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)掉包率的狀態(tài)。在0～140s時(shí)間段以及240～400s時(shí)間段有掉包現(xiàn)象出現(xiàn)，即有自私節(jié)點(diǎn)行為發(fā)生，而140～240s時(shí)間段表示無(wú)掉包現(xiàn)象，即表示沒(méi)有自私節(jié)點(diǎn)的行為發(fā)生。

圖2 一個(gè)節(jié)點(diǎn)在一段時(shí)間內(nèi)的掉包情況

圖3則表示在這段時(shí)間內(nèi)節(jié)點(diǎn)信用度值的變化。在0～140s時(shí)間段內(nèi)有自私節(jié)點(diǎn)行為發(fā)生，節(jié)點(diǎn)的信用度值逐漸減小到0.25左右，而在140～240s時(shí)間段內(nèi)無(wú)自私節(jié)點(diǎn)行為出現(xiàn)，節(jié)點(diǎn)的信用度值產(chǎn)生了上升的趨勢(shì)。當(dāng)然，在網(wǎng)絡(luò)中節(jié)點(diǎn)間進(jìn)行通信也會(huì)存在正常的堵塞和掉包現(xiàn)象，所以從圖3中可以看出節(jié)點(diǎn)信用度值沒(méi)有恢復(fù)為1。

由圖2和圖3分析可以證明本文提出的基于互詢式的節(jié)點(diǎn)信用度的計(jì)算方法能夠準(zhǔn)確有效地反映網(wǎng)絡(luò)中自私節(jié)點(diǎn)惡意行為的出現(xiàn)，以及其對(duì)網(wǎng)絡(luò)性能的影響。

圖3 節(jié)點(diǎn)信任度值大小變化過(guò)程

3 結(jié)論

本文所提出的基于互詢式的節(jié)點(diǎn)信用度計(jì)算方法的優(yōu)勢(shì)在于：能夠比較準(zhǔn)確地反映出節(jié)點(diǎn)的信任度；采用的互詢機(jī)制能夠有效地遏制某些惡意節(jié)點(diǎn)對(duì)信用度的偽造和欺騙及對(duì)網(wǎng)絡(luò)所造成的傷害；某節(jié)點(diǎn)的鄰居節(jié)點(diǎn)可以及時(shí)得到該節(jié)點(diǎn)的信用度值變化的信息的反饋，所以，當(dāng)該點(diǎn)的信用度值過(guò)低時(shí)，可以很快地完成對(duì)此惡意點(diǎn)的孤立，有效地保持網(wǎng)絡(luò)通信的暢通；基于分布式的計(jì)算方法大大減輕了節(jié)點(diǎn)的負(fù)擔(dān)，因此增強(qiáng)了整個(gè)網(wǎng)絡(luò)的安全性。

（References）

［1］卿林，詹永照，祖寶明，等.Ad Hoc網(wǎng)絡(luò)中一種有效的（t，n）門限密鑰管理方案［J］.計(jì)算機(jī)工程，2007（21）：136-139.

［2］杜君，李偉華，張克旺，等.無(wú)線自組織網(wǎng)絡(luò)高精準(zhǔn)確度自私結(jié)點(diǎn)檢測(cè)機(jī)制［J］.西安交通大學(xué)學(xué)報(bào)，2010，44（8）：25-29.

［3］YONG WEI WANG，GIRUKA V C，SINGHAL M.A fair distributed Solution for selfish nodes problem in wireless ad hoc networks［C］.∥Proceedings of third international conference，ADHOCNOW 2009，Vancouver，Canada，2009：211-224.

［4］HANG SU，XI HANG.Modeling throughput gain of network coding in multi-channel multi-radio wireless ad hoc networks［J］.IEEE Journal on selected areas in communications，2009，27（5）：593-605.

［5］譚長(zhǎng)庚，羅文燕，陳松喬，等.移動(dòng)Ad Hoc網(wǎng)絡(luò)中節(jié)點(diǎn)合作性研究綜述［J］.計(jì)算機(jī)科學(xué)，2007，34（4）：24-27.

［6］張?jiān)?，沈蘇彬.Ad Hoc網(wǎng)絡(luò)中信任管理模型的研究與設(shè)計(jì)［J］.西安郵電大學(xué)學(xué)報(bào)，2008，13（1）：86-90.

［7］陳刪刪，楊庚，張?jiān)撇?Ad Hoc網(wǎng)絡(luò)中一種基于救贖機(jī)制的信息模型［J］.南京郵電大學(xué)學(xué)報(bào)，2009，29（4）：20-25.

［8］孫麗艷.基于激勵(lì)機(jī)制的的認(rèn)知無(wú)線電自私行為研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2009，19（10）：170-173.

［9］MARTI S，GIULI T，LAI K，et al.Mitigating routing misbehavior in mobile ad hoc networks［C］.∥Proceedings of MOBICOM 2000.New York，USA，ACM press，2000：255-265.

［10］BUTTYAN L，HUBAUX J P.Stimulating cooperation in selforganizing mobile ad hoc networks［J］.ACM／Kluwer Mobile Networks and Applications，2007，8（5）：579-592.

A reputation model of node computation based on exchange inquiry scheme in Ad Hoc networks

Wei Nini，Song Yi
（Department of Computer Science ＆Information Engineering，Wuhan Bioengineering Institute，Wuhan 430415，China）

The reputations of the network nodes play an important role in the Ad Hoc networks which could effectively prevent malicious nodes and selfish nodes to bring destruction of the network performance.Aiming at solving the problems that existing of selfish nodes caused can refuse to forward data pack，thereby reducing the forwarding performance of the networks for Ad Hoc networks，by using aquantitative indicator to strengthen the monitoring of the nodes behavior，proposed a new mechanism which was a node reputation computation model based on exchange inquiry.This paper studies the implementation mechanism of the model，and then from the dropping quota packs of the networks and the change of the node reputations，describes the advantages and feasibility of this model.Simulation with the NS2is used.The simulation results show that the computation model proposed can reflect the reputation of the nodes more exactly，so they can stop the occurrence validly about the malicious behavior of the nodes.

reputation model；Ad Hoc network；selfish node；exchange inquiry

TP393

A

1002-4956（2013）03-0096-03

2012-06-22

湖北省自然科學(xué)基金（2011CD297）；新世紀(jì)優(yōu)秀人才支持計(jì)劃（NCET-08-0806）；武漢市教育局科研項(xiàng)目（2009k100）

魏妮妮（1982—），女，遼寧營(yíng)口，碩士，講師，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與通信.

E-mail：wnn19821024＠163.com