黃 干， 劉 濤， 蘇宇婷

(1.安徽工程大學(xué) 計(jì)算機(jī)應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室，安徽 蕪湖 241000； 2.東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163000)

基于優(yōu)化蟻群算法的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)信任模型*

黃 干1， 劉 濤1， 蘇宇婷2

(1.安徽工程大學(xué) 計(jì)算機(jī)應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室，安徽 蕪湖 241000； 2.東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163000)

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(WSNs)會(huì)受到很多因素的影響，包括無(wú)線(xiàn)鏈路干擾，缺乏物理保護(hù)等，使其對(duì)于惡意節(jié)點(diǎn)的攻擊顯得很脆弱，從而成為妥協(xié)節(jié)點(diǎn)。為了解決這些網(wǎng)絡(luò)安全問(wèn)題，提出一種基于優(yōu)化蟻群算法的信任模型。這個(gè)模型由信息素更新、路徑質(zhì)量評(píng)估、信任度評(píng)估和懲罰與獎(jiǎng)勵(lì)機(jī)制構(gòu)成。此外，為了提高全局信息素計(jì)算的準(zhǔn)確性，在計(jì)算全局信息素時(shí)引入了最優(yōu)解保留策略。仿真結(jié)果表明：該信任模型具有更高的性能和可靠性，更加適合WSNs。

無(wú)線(xiàn)傳感器網(wǎng)絡(luò); 優(yōu)化蟻群算法； 信任模型

0 引 言

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(WSNs)廣泛應(yīng)用于軍事、環(huán)境監(jiān)控、醫(yī)療監(jiān)護(hù)等領(lǐng)域中[1]。然而，隨著WSNs滲入的領(lǐng)域越來(lái)越多，安全問(wèn)題就顯得越來(lái)越突出[2]。近年來(lái)，許多研究者提出在WSNs中建立關(guān)于節(jié)點(diǎn)的信任模型。信任模型可以通過(guò)監(jiān)測(cè)網(wǎng)絡(luò)行為、最小化風(fēng)險(xiǎn)來(lái)提高整個(gè)網(wǎng)絡(luò)的性能。目前，圍繞著WSNs信任模型展開(kāi)了一系列的研究。文獻(xiàn)[3]提出了WSNs基于代理的信任模型(agency trust model,ATRM)。在A(yíng)TRM中，基于分散證書(shū)的信任模型通過(guò)代理模塊來(lái)監(jiān)測(cè)網(wǎng)絡(luò)行為。這種模型解決了不確定問(wèn)題，但是網(wǎng)絡(luò)中的節(jié)點(diǎn)仍有可能與惡意節(jié)點(diǎn)進(jìn)行交互。文獻(xiàn)[4]提出了WSNs基于信譽(yù)的信任模型(reputation trust model,RTRM)。在這個(gè)模型中，每個(gè)節(jié)點(diǎn)為網(wǎng)絡(luò)中的其它節(jié)點(diǎn)維持一個(gè)信譽(yù)值。網(wǎng)絡(luò)中的節(jié)點(diǎn)通過(guò)看門(mén)狗機(jī)制來(lái)監(jiān)測(cè)其它節(jié)點(diǎn)的行為，并基于時(shí)間為它們建立信譽(yù)值。然后，節(jié)點(diǎn)利用這些信譽(yù)值來(lái)評(píng)估其它節(jié)點(diǎn)的信任度，并預(yù)測(cè)這些節(jié)點(diǎn)的未來(lái)行為。文獻(xiàn)[5,6]提出基于節(jié)點(diǎn)行為和D-S證據(jù)理論的信任模型，它聯(lián)合了節(jié)點(diǎn)行為機(jī)制和更改的證據(jù)理論。文獻(xiàn)[7,8]提出WSNs基于任務(wù)分配的信任模型(task allocation trust model,TATRM)。該模型通過(guò)為每個(gè)節(jié)點(diǎn)分配一個(gè)任務(wù)或者標(biāo)準(zhǔn)來(lái)提高WSNs的吞吐量。文獻(xiàn)[9]提出WSNs基于生物學(xué)算法的信任模型(BTRM-WSNs)，而生物學(xué)算法使用的是蟻群算法。每個(gè)螞蟻通過(guò)在一些路徑上釋放信息素來(lái)幫助后續(xù)的螞蟻找到最優(yōu)路徑。

然而文獻(xiàn)[9]所提出的信任模型存在著復(fù)雜度高、信任度計(jì)算不準(zhǔn)確等問(wèn)題，本文在文獻(xiàn)[9]的基礎(chǔ)上，提出一種基于優(yōu)化蟻群算法的信任模型,它與文獻(xiàn)[9]的信任模型相比，做出了很大的改進(jìn)。首先，它通過(guò)信息素更新、路徑質(zhì)量評(píng)估、信任度評(píng)估來(lái)得到節(jié)點(diǎn)的信任度，再通過(guò)懲罰與獎(jiǎng)勵(lì)機(jī)制來(lái)動(dòng)態(tài)更新信任度，這使得信任模型的評(píng)估更加全面、準(zhǔn)確。其次它通過(guò)最優(yōu)解保留策略來(lái)更新全局信息素，這提高了全局信息素計(jì)算的準(zhǔn)確性。

1 蟻群算法

蟻群算法(ant colony algorithm,ACA)是一種基于群體的模擬進(jìn)化算法，它是受自然界中真實(shí)蟻群的集體覓食行為的啟發(fā)而發(fā)展起來(lái)的，它屬于隨機(jī)搜索算法的一種[10]。在這個(gè)算法里[11]，它把研究活動(dòng)分配給稱(chēng)為“螞蟻”的代理。事實(shí)上，對(duì)于真實(shí)螞蟻活動(dòng)的研究給了動(dòng)物行為學(xué)家很大的啟發(fā)。研究的問(wèn)題之一就是如何尋找到一條從它們的蟻巢到食物源頭的最短路徑。據(jù)發(fā)現(xiàn)，它們是通過(guò)媒介來(lái)進(jìn)行個(gè)體之間的信息交流，并決定往哪走。在媒介之中，就包括信息素。一個(gè)移動(dòng)的螞蟻會(huì)在路徑上留下不同量的信息素，從而給路徑做上標(biāo)記。當(dāng)一個(gè)單獨(dú)的螞蟻隨機(jī)移動(dòng)時(shí)，它就會(huì)偵測(cè)到之前螞蟻留下的信息素，并選擇向信息素量高的路徑移動(dòng)。這種集體行為是自催化行為的一種形式。這個(gè)過(guò)程是一種正反饋過(guò)程，當(dāng)一條路徑被螞蟻選擇次數(shù)的越多，它被后面的螞蟻選擇的概率就越高。ACA具有很多優(yōu)點(diǎn)[12]，包括并行性、通用性、魯棒性。

2 基于優(yōu)化ACA的WSNs信任模型

2.1 信息素的更新

定義1 信息素的值用來(lái)代表節(jié)點(diǎn)之間的信任程度，在t時(shí)刻節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的連接邊上的信息素量用τij(t)來(lái)表示[13]。在初始時(shí)刻，將m只螞蟻放到n個(gè)初始節(jié)點(diǎn)上，同時(shí)，將每只螞蟻的禁忌表tabuk的第一個(gè)元素設(shè)為它們所在的初始節(jié)點(diǎn)上。此時(shí)各路徑上的信息素量相等，設(shè)τij(0)=C(C為一個(gè)較小的常數(shù))。

(1)

其中，Jk(i)={1,2,…,n}-tabuk表示螞蟻k的能選擇的下一個(gè)節(jié)點(diǎn)的集合。螞蟻k經(jīng)過(guò)一個(gè)節(jié)點(diǎn)，就會(huì)把節(jié)點(diǎn)加入到tabuk中。

對(duì)于A(yíng)CA來(lái)說(shuō)，信息素更新分為局部信息素更新和全局信息素更新。每只螞蟻每經(jīng)過(guò)一條邊時(shí)就會(huì)進(jìn)行一次局部信息素更新。當(dāng)螞蟻從節(jié)點(diǎn)i轉(zhuǎn)到節(jié)點(diǎn)j，邊ij上信息素的更新為

τij(t+1)=(1-ρ)τij(t)+ρτ0,

(2)

式中ρ為路徑上信息素的蒸發(fā)因子，它能夠使路徑“忘記”不好的狀況，從而避免路徑陷入次優(yōu)化的情況。τ0為路徑上的信息素的初始值。局部信息素更新的作用是當(dāng)螞蟻發(fā)現(xiàn)已選的邊的信息素值減少時(shí)，它就會(huì)進(jìn)而去選擇沒(méi)有選擇過(guò)的邊。

每次迭代完成后，會(huì)對(duì)所有螞蟻所發(fā)現(xiàn)的最優(yōu)路徑進(jìn)行全局信息素更新。這個(gè)更新需要發(fā)送額外的螞蟻來(lái)對(duì)最優(yōu)路徑進(jìn)行計(jì)算。最優(yōu)路徑ij的全局信息素更新為

(3)

(4)

(5)

(6)

2.2 路徑質(zhì)量評(píng)估

每次螞蟻進(jìn)行一次迭代返回到源節(jié)點(diǎn)時(shí)，自己會(huì)記住自己所走過(guò)的路徑。之后，源節(jié)點(diǎn)會(huì)評(píng)估這個(gè)螞蟻?zhàn)哌^(guò)的路徑的質(zhì)量。特別是螞蟻會(huì)保持自己走過(guò)的路徑上的節(jié)列表和路徑上的信息素值。路徑質(zhì)量的計(jì)算如下

(7)

2.3 信任度評(píng)估

在網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)會(huì)為其所有鄰居節(jié)點(diǎn)維持一個(gè)信息素值的集合，它決定了螞蟻選擇哪條路徑。然而，信息素值常常又會(huì)與信任度值混淆，為了區(qū)分兩者，用Ti表示節(jié)點(diǎn)i的信任度。信任度的計(jì)算如下

(8)

式中I(i)為與節(jié)點(diǎn)i有的關(guān)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都會(huì)維持一個(gè)鄰居節(jié)點(diǎn)的信任度表。

2.4 獎(jiǎng)勵(lì)與懲罰機(jī)制

一旦源節(jié)點(diǎn)知道了最好的路徑，就會(huì)對(duì)這個(gè)路徑收到的服務(wù)進(jìn)行評(píng)估[14]。源節(jié)點(diǎn)會(huì)對(duì)這些服務(wù)給出一個(gè)滿(mǎn)意度S,當(dāng)滿(mǎn)意值S低于懲罰閾值PunTh∈[0,1]時(shí)，τij為

τij=(τij-ρ)S(1-dfij)，

(9)

(10)

式中dfij為連接節(jié)點(diǎn)i和節(jié)點(diǎn)j之間路徑的距離因子，Lk為螞蟻k發(fā)現(xiàn)的路徑長(zhǎng)度，dij為i和j之間的距離。

當(dāng)滿(mǎn)意值S不小于懲罰閾值PunTh時(shí)，τij為

τij=τij-ρ(1-S)dfij.

(11)

3 實(shí)驗(yàn)結(jié)果與分析

為了對(duì)所提出的模型的性能和可靠性進(jìn)行評(píng)估，本文通過(guò)三組仿真實(shí)驗(yàn)來(lái)把它與BTRM-WSNs模型進(jìn)行對(duì)比。第一組實(shí)驗(yàn)是比較兩個(gè)模型搜索可信節(jié)點(diǎn)的準(zhǔn)確性，第二組實(shí)驗(yàn)是比較兩個(gè)模型找到可信節(jié)點(diǎn)所需的平均路徑長(zhǎng)度，第三組實(shí)驗(yàn)是比較兩個(gè)模型的總的能量消耗。

3.1 TRMSim-WSNs

TRMSim-WSNs是一個(gè)WSNs基于Java的信任模型仿真器，它提供一個(gè)很方便的方式來(lái)測(cè)試信任模型[15]。本文在仿真信任模型時(shí)，設(shè)置參數(shù)如下：客戶(hù)節(jié)點(diǎn)為15 %，中繼服務(wù)器節(jié)點(diǎn)為5 %，節(jié)點(diǎn)射頻通信距離為10 m，傳感器節(jié)點(diǎn)的最大、最小個(gè)數(shù)為100，網(wǎng)絡(luò)數(shù)目為400，執(zhí)行數(shù)為100。然后，仿真器就會(huì)基于這些參數(shù)隨機(jī)生成一個(gè)WSNs。注意， 85 %的節(jié)點(diǎn)是提供服務(wù)的服務(wù)器節(jié)點(diǎn)。圖1為用TRMSim-WSNs仿真出的WSNs。

圖1 仿真出的WSNs

3.2 準(zhǔn)確率

信任模型的準(zhǔn)確率是用來(lái)評(píng)估信任模型的可靠性和安全性，它是用信任模型成功地選擇可信傳感器節(jié)點(diǎn)的次數(shù)比上總的處理次數(shù)。一個(gè)好的信任模型必須要能對(duì)惡意節(jié)點(diǎn)的攻擊有很好的控制。圖2 把BTRM-WSNs的準(zhǔn)確性與本文所提出的信任模型的準(zhǔn)確性進(jìn)行了對(duì)比。從圖中可以看出：當(dāng)惡意節(jié)點(diǎn)比例少于50 %時(shí)，兩個(gè)信任模型在找到可信節(jié)點(diǎn)的準(zhǔn)確性上相差不大。但當(dāng)惡意比例高于50%時(shí)，所提出的模型能夠比BTRM-WSNs提供更高的準(zhǔn)確性和安全性。

圖2 準(zhǔn)確率對(duì)比

3.3 平均路徑長(zhǎng)度

平均路徑長(zhǎng)度是源節(jié)點(diǎn)找到最可信的傳感器節(jié)點(diǎn)的平均跳數(shù)。對(duì)于一個(gè)信任模型，平均路徑長(zhǎng)度越短，這個(gè)信任模型在找尋可信傳感器節(jié)點(diǎn)上具有很好的性能。首先，更少的中間節(jié)點(diǎn)意味著更高的安全性和更少的能量消耗。其次，更短的路徑意味源節(jié)點(diǎn)可以更容易地找到可信服務(wù)節(jié)點(diǎn)，服務(wù)節(jié)點(diǎn)可以很快地給源節(jié)點(diǎn)提供服務(wù)。圖3是兩個(gè)信任模型在平均路徑長(zhǎng)度上的對(duì)比。如圖所示，本文所提出的模型可以更加容易地找到可信節(jié)點(diǎn)，表現(xiàn)出比BTRM-WSNs更好的性能。

3.4 能量消耗

WSNs是一個(gè)能量有限的網(wǎng)絡(luò)，所以,設(shè)計(jì)一個(gè)適合WSNs的信任模型必須減少能量消耗，這樣在保證網(wǎng)絡(luò)安全性的同時(shí)也能延長(zhǎng)網(wǎng)絡(luò)的生命周期。WSNs的能量消耗包括源節(jié)點(diǎn)發(fā)送信息所消耗的能量、惡意節(jié)點(diǎn)提供惡意服務(wù)所消耗的能量和在網(wǎng)絡(luò)中搜索可信節(jié)點(diǎn)所消耗的能量。圖4是兩個(gè)信任模型在能量消耗上的比較。如圖所示，所提出的信任模型在能量消耗上比BTRM-WSNs更低，更加適合WSNs。

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

本文提出一種在WSNs環(huán)境下基于優(yōu)化過(guò)的ACA的信任模型，這個(gè)信任模型可以準(zhǔn)確、全面地計(jì)算出節(jié)點(diǎn)信任度并動(dòng)態(tài)更新信任度，此外，該模型在計(jì)算全局信息素時(shí)更加準(zhǔn)確。仿真結(jié)果表明:與 BTRM-WSNs相比，本文所提出的信任模型找到可信節(jié)點(diǎn)的準(zhǔn)確率更高，找到可信節(jié)點(diǎn)所需的跳數(shù)更少。此外，該模型比BTRM-WSNs消耗更少的能量，更加適合WSNs。本文下一步的工作將繼續(xù)改進(jìn)該信任模型，使得它具有更高的性能和可靠性。

圖3 平均路徑長(zhǎng)度對(duì)比

圖4 能量消耗對(duì)比

[1] Yick J,Mukherjee B,Ghosal D.Wireless sensor networks sur-vey[J].Computer Networks,2008,52(12):2292-2330.

[2] Bojkovic Z S,Bakmaz B M,Bakmaz M R.Security issues in wireless sensor networks[J].International Journal of Communications,2008,2(1):106-115.

[3] Chen H,Wu H,Hu J,et al.Agent-based trust management model for wireless sensor networks[C]∥International Conference on Multimedia and Ubiquitous Engineering,MUE 2008,IEEE,2008:150-154.

[4] Alzaid H,Alfaraj M,Ries S,et al.Reputation-based trust systems for wireless sensor networks:A comprehensive review[M]∥Berlin Heidelberg:Springer,2013:66-82.

[5] Feng R,Xu X,Zhou X,et al.A trust evaluation algorithm for wireless sensor networks based on node behaviors and DS evidence theory[J].Sensors,2011,11(2):1345-1360.

[6] Feng R,Che S,Wang X,et al.Trust management scheme based on DS evidence theory for wireless sensor networks[J].International Journal of Distributed Sensor Networks,2013,13(2):25-34.

[7] Misra S,Vaish A.Reputation-based role assignment for role-based

access control in wireless sensor networks[J].Computer Communications,2011,34(3):281-294.

[8] Srinivasan A,Teitelbaum J,Wu J.DRBTS:Distributed reputation-based beacon trust system[C]∥2nd IEEE International Sympo-sium on Dependable,Autonomic and Secure Computing,IEEE,2006:277-283.

[9] Yu H,Shen Z,Miao C,et al.A survey of trust and reputation management systems in wireless communications[J].Proceedings of the IEEE,2010,98(10):1755-1772.

[10] Liao T,Stützle T,Montes de Oca M A,et al.A unified ant colony optimization algorithm for continuous optimization[J].European Journal of Operational Research,2014,234(3):597-609.

[11] Dorigo M,Gambardella L M.Ant colony system:A cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.

[12] Dorigo M,Blum C.Ant colony optimization theory:A survey[J].Theoretical Computer Science,2005,344(2):243-278.

[13] Han G,Jiang J,Shu L,et al.Management and applications of trust in wireless sensor networks:A survey[J].Journal of Computer and System Sciences,2014,80(3):602-617.

[14] Mármol F G,Pérez G M.Providing trust in wireless sensor networks using a bio-inspired technique[J].Telecommunication Systems,2011,46(2):163-180.

[15] Mármol F G,Pérez G M.Trust and reputation models compari-son[J].Internet Research,2011,21(2):138-153.

Trust model for WSNs based on optimized ant colony algorithm*

HUANG Gan1, LIU Tao1, SU Yu-ting2

(1.Key Laboratory of Computer Application Technology,Anhui Polytechnic University, Wuhu 241000,China; 2.School of Computer and Information Technology, Northeast Petroleum University,Daqing 163000,China)

Wireless sensor networks(WSNs)may be influenced by many factors,including interference of wireless links and lack of physical protection,which makes the sensor nodes vulnerable to a variety of attacks launched by malicious nodes and become compromised nodes.In order to address these network security problems,a trust model based on optimized ant colony algorithm is proposed.This model is composed of pheromone update,path quality assessment,trust evaluation and punishment and reward mechanism.In addition,in order to enhance the accuracy of the global pheromone calculation, when global pheromone is calculating,the optimal solution retention strategy is introduced into the trust model.The simulation result show that the trust model has higher performance and reliability and it is more suitable for WSNs.

wireless sensor networks(WSNs); optimized ant colony algorithm; trust model

10.13873/J.1000—9787(2015)03—0054—04

2014—12—30

國(guó)家自然科學(xué)基金資助項(xiàng)目(61300170)；安徽省教育廳重點(diǎn)資助項(xiàng)目( KJ2013A040)；安徽省自然科學(xué)基金資助項(xiàng)目(1308085MF88)；安徽工程大學(xué)青年基金資助項(xiàng)目(2013YQ28，2012YQ31)

TP 309.2

A

1000—9787(2015)03—0054—04

黃 干(1990-)，男，安徽滁州人，碩士研究生，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與信息安全。