魏妮妮，宋 翌

（武漢生物工程學院計算機與信息工程系，湖北武漢 430415）

Ad Hoc中互詢式節(jié)點信用度計算模型

魏妮妮，宋 翌

（武漢生物工程學院計算機與信息工程系，湖北武漢 430415）

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

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

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

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

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

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

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

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

圖1 互詢式的節(jié)點的信用度計算模型

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

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

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

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

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

通過對節(jié)點的信任信息搜尋之后，節(jié)點獲得了某個節(jié)點的信用度信息，然后通過一種消息傳送機制在節(jié)點中交換彼此的信息。節(jié)點的信任度信息交換格式為

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表示一個節(jié)點向某個節(jié)點發(fā)出的信息是用于向其詢問與它關聯(lián)節(jié)點的信任度；MESSAGE＿RESPONSE表示發(fā)出的消息是一個節(jié)點對于某個節(jié)點信任度值進行咨詢的應答；MESSAGE＿BROCAST表示發(fā)出的消息是用于廣播節(jié)點信用度信息?！癗ODE＿ID”表示有惡意行為的節(jié)點或者想加入網(wǎng)絡進行通信的新節(jié)點的IP地址?！癛EU＿VAL”是具體的數(shù)值，用于表示節(jié)點信用度的大小，它存儲在每個節(jié)點信用度表中。

1.1.3 節(jié)點信任信息維護子模塊

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 仿真與性能分析

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

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

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

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

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

圖3 節(jié)點信任度值大小變化過程

3 結(jié)論

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

（References）

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

［2］杜君，李偉華，張克旺，等.無線自組織網(wǎng)絡高精準確度自私結(jié)點檢測機制［J］.西安交通大學學報，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］譚長庚，羅文燕，陳松喬，等.移動Ad Hoc網(wǎng)絡中節(jié)點合作性研究綜述［J］.計算機科學，2007，34（4）：24-27.

［6］張元，沈蘇彬.Ad Hoc網(wǎng)絡中信任管理模型的研究與設計［J］.西安郵電大學學報，2008，13（1）：86-90.

［7］陳刪刪，楊庚，張云昌，等.Ad Hoc網(wǎng)絡中一種基于救贖機制的信息模型［J］.南京郵電大學學報，2009，29（4）：20-25.

［8］孫麗艷.基于激勵機制的的認知無線電自私行為研究［J］.計算機技術與發(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

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

魏妮妮（1982—），女，遼寧營口，碩士，講師，主要研究領域為計算機網(wǎng)絡與通信.

E-mail：wnn19821024＠163.com