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

黃 干， 劉 濤， 蘇宇婷

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

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

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

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

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

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

0 引 言

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

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

1 蟻群算法

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

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

2.1 信息素的更新

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

(1)

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

對于ACA來說，信息素更新分為局部信息素更新和全局信息素更新。每只螞蟻每經(jīng)過一條邊時就會進行一次局部信息素更新。當(dāng)螞蟻從節(jié)點i轉(zhuǎn)到節(jié)點j，邊ij上信息素的更新為

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

(2)

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

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

(3)

(4)

(5)

(6)

2.2 路徑質(zhì)量評估

每次螞蟻進行一次迭代返回到源節(jié)點時，自己會記住自己所走過的路徑。之后，源節(jié)點會評估這個螞蟻走過的路徑的質(zhì)量。特別是螞蟻會保持自己走過的路徑上的節(jié)列表和路徑上的信息素值。路徑質(zhì)量的計算如下

(7)

2.3 信任度評估

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

(8)

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

2.4 獎勵與懲罰機制

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

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

(9)

(10)

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

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

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

(11)

3 實驗結(jié)果與分析

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

3.1 TRMSim-WSNs

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

圖1 仿真出的WSNs

3.2 準(zhǔn)確率

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

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

3.3 平均路徑長度

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

3.4 能量消耗

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

4 結(jié)束語

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

圖3 平均路徑長度對比

圖4 能量消耗對比

[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

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

TP 309.2

A

1000—9787(2015)03—0054—04

黃 干(1990-)，男，安徽滁州人，碩士研究生，主要研究方向為計算機網(wǎng)絡(luò)與信息安全。