呂林濤，胡雷雷，楊宇祥，譚 芳

(西安理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，西安 7 10048)

基于LEACH協(xié)議的安全節(jié)能路由算法研究

呂林濤，胡雷雷，楊宇祥，譚 芳

(西安理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，西安 7 10048)

針對(duì)現(xiàn)有及經(jīng)典自適應(yīng)分簇路由協(xié)議LEACH存在網(wǎng)絡(luò)生存周期短和節(jié)點(diǎn)可靠性低的問(wèn)題，提出一種安全的低能耗分簇路由協(xié)議S-LEACH。采用多角度信任模型，即從節(jié)點(diǎn)數(shù)據(jù)、通信帶寬和剩余能量3個(gè)方面對(duì)待檢測(cè)網(wǎng)絡(luò)內(nèi)各節(jié)點(diǎn)進(jìn)行信任度評(píng)估，建立信任值集合并對(duì)照節(jié)點(diǎn)信任度閾值進(jìn)行簇頭安全選舉，用螢火蟲(chóng)算法模擬實(shí)現(xiàn)成員節(jié)點(diǎn)聚簇，以單跳或多跳方式與基站節(jié)點(diǎn)通信的方法降低由于通信距離較遠(yuǎn)而帶來(lái)的額外能耗。實(shí)驗(yàn)結(jié)果表明，與LEACH協(xié)議相比，S-LEACH協(xié)議可延長(zhǎng)4倍以上的網(wǎng)絡(luò)生存周期，且與以數(shù)據(jù)信任度為評(píng)測(cè)標(biāo)準(zhǔn)的BTSR協(xié)議相比，S-LEACH協(xié)議可將網(wǎng)絡(luò)內(nèi)非信任節(jié)點(diǎn)檢測(cè)率提高2.3%。

無(wú)線傳感器網(wǎng)絡(luò)；節(jié)點(diǎn)信譽(yù)度；螢火蟲(chóng)算法；分簇；安全；分簇路由

1 概述

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks, WSN)由部署在監(jiān)測(cè)區(qū)域內(nèi)大量的廉價(jià)微型傳感器節(jié)點(diǎn)組成，通過(guò)無(wú)線通信方式形成一個(gè)多跳的自組織網(wǎng)絡(luò)系統(tǒng)[1]。由于無(wú)線傳感器網(wǎng)絡(luò)具有不依賴于任何預(yù)設(shè)網(wǎng)絡(luò)設(shè)施等特點(diǎn)，更是作為物聯(lián)網(wǎng)底層的重要技術(shù)形式[2]，使其在戰(zhàn)場(chǎng)定位[3]、生理數(shù)據(jù)采集[4]、智能交通[5]和海洋探測(cè)[6]等許多領(lǐng)域都有著廣泛的應(yīng)用前景，在國(guó)內(nèi)外備受關(guān)注。

WSN節(jié)點(diǎn)具有雙重身份，既要完成感應(yīng)和處理任務(wù)，又要完成路由功能。WSN中的節(jié)點(diǎn)隨機(jī)分布且數(shù)量眾多，而其能量是由容量有限的電池供電，常部署在無(wú)人維護(hù)、不可控制的環(huán)境中，更換不易，且現(xiàn)有路由協(xié)議[7]在設(shè)計(jì)時(shí)并沒(méi)有考慮安全因素；隨著WSN的飛速發(fā)展和廣泛的應(yīng)用，為了抑制網(wǎng)絡(luò)中的惡意行為，提高節(jié)點(diǎn)和服務(wù)的可靠性，降低節(jié)點(diǎn)能耗的路由算法成為國(guó)內(nèi)外研究的熱點(diǎn)。因此，本文提出一種基于螢火蟲(chóng)算法與信任模型相結(jié)合的安全的低功耗簇路由算法——S-LEACH協(xié)議。

2 S-LEACH協(xié)議的組成框架

針對(duì)LEACH協(xié)議的弱點(diǎn)，為了進(jìn)一步優(yōu)化其節(jié)能并融入安全機(jī)制，依托輕量級(jí)的節(jié)點(diǎn)信譽(yù)度安全模型，借鑒螢火蟲(chóng)算法的生物聚集性和多跳路由原理的優(yōu)勢(shì)，結(jié)合WSN低能耗安全的要求，分別對(duì)LEACH協(xié)議的簇頭選舉算法、成員節(jié)點(diǎn)入簇算法以及簇頭與base節(jié)點(diǎn)之間的路由算法進(jìn)行改進(jìn)。將信譽(yù)度引子和熒光引子相結(jié)合，一方面，避免了螢火蟲(chóng)算法的局部早熟；另一方面，將輕量的安全模型與路由進(jìn)行綁定，兼容各自的特點(diǎn)，從而構(gòu)建出一種更加優(yōu)越的S-LEACH大廈，如圖1所示。

圖1 S-LEACH協(xié)議模型

Step3 base節(jié)點(diǎn)將收集到的成員節(jié)點(diǎn)信息進(jìn)行匯總，根據(jù)式(3)求出能量閾值，再由式(4)判斷其是否成為簇首節(jié)點(diǎn)，并將簇頭信息廣播給成員節(jié)點(diǎn)，成員節(jié)點(diǎn)依據(jù)螢火蟲(chóng)算法[9]，以熒光素值li( t)，如式(5)為參考標(biāo)準(zhǔn)，決定是否加入該簇，從而確定簇頭。隨著輪數(shù)的變化，重復(fù)以上步驟：

3 S-LEACH路由協(xié)議算法

在S-LEACH協(xié)議模型的基礎(chǔ)上，對(duì)LEACH協(xié)議的簇頭選舉、成員節(jié)點(diǎn)入簇和簇頭與base節(jié)點(diǎn)之間通信算法進(jìn)行優(yōu)化和改進(jìn)。首先建立信任值集合，然后據(jù)此集合選舉簇頭、保證成員節(jié)點(diǎn)安全入簇，最后基于此集優(yōu)化簇間通信算法。

3.1 節(jié)點(diǎn)信譽(yù)值集合的確立

與傳統(tǒng)的Ad H oc網(wǎng)絡(luò)相比，WSN傳感器節(jié)點(diǎn)的能量有限，不能通過(guò)如基于門限的密鑰認(rèn)證機(jī)制和基于自組織密鑰認(rèn)證機(jī)制這2種復(fù)雜的身份認(rèn)證機(jī)制，WSN的安全信任模型的引入對(duì)克服節(jié)點(diǎn)數(shù)據(jù)的不安全性帶來(lái)了福音。一種基于多角度的信任模型[8]為：

其中，w1，w2，w3分別是數(shù)據(jù)、帶寬和剩余能量可信度的權(quán)重；Tdata，Tbandwidth 和Tenerge分別為數(shù)據(jù)、帶寬和剩余能量的信譽(yù)度。

基于該模型可得每個(gè)節(jié)點(diǎn)在第r輪節(jié)點(diǎn)i的信譽(yù)值集合S( i).trust，如下所示：

3.2 簇頭節(jié)點(diǎn)的選取及成簇的改進(jìn)

由于LEACH算法以一定的隨機(jī)概率得到閾值，作為簇頭選取的依據(jù)存在安全隱患，且base(基站)節(jié)點(diǎn)的位置確定可根據(jù)需求對(duì)其進(jìn)行更換，因此在S-LEACH首先假定base節(jié)點(diǎn)能量無(wú)限，具體實(shí)現(xiàn)如下：

Step1 在奇數(shù)輪時(shí)，base節(jié)點(diǎn)廣播聚簇信息給網(wǎng)內(nèi)成員節(jié)點(diǎn)。在偶數(shù)輪時(shí)，按照LEACH協(xié)議選取本輪次的簇首節(jié)點(diǎn)。

Step2 成員節(jié)點(diǎn)接收廣播信息，并發(fā)布自身信息給base節(jié)點(diǎn)，該信息包括該節(jié)點(diǎn)剩余能量和該節(jié)點(diǎn)的信譽(yù)度值。

其中，f( r)為能量閾值；r為輪數(shù)；min(S( j).iE)為第i個(gè)簇的成員節(jié)點(diǎn)j的能量。

其中，α為熒光值調(diào)節(jié)因子，即第 i個(gè)節(jié)點(diǎn)到頭結(jié)點(diǎn)距離與到base節(jié)點(diǎn)距離的比值。該比值越大，熒光值越大，成員節(jié)點(diǎn)越向該簇頭靠近。

3.3 簇間路由的改進(jìn)

由于LEACH協(xié)議使用單跳方式與基站節(jié)點(diǎn)進(jìn)行通信，有可能使節(jié)點(diǎn)快速衰亡，但簇頭節(jié)點(diǎn)距基站節(jié)點(diǎn)較遠(yuǎn)時(shí)S-LEACH將采取簇間多跳多條方式。具體實(shí)現(xiàn)如下：

Step2 base節(jié)點(diǎn)按式(6)，將大于節(jié)點(diǎn)通信距離do的簇頭i，參考β按照Dijkstra算法(迪杰斯特拉算法)在簇頭集內(nèi)尋找下一跳的轉(zhuǎn)發(fā)路由節(jié)點(diǎn)與base節(jié)點(diǎn)進(jìn)行通信，并根據(jù)式(7)記錄第p跳簇頭節(jié)點(diǎn)i的下一轉(zhuǎn)發(fā)簇頭節(jié)點(diǎn)

Step3 base節(jié)點(diǎn)廣播通知簇頭i的下一跳節(jié)點(diǎn)的信息S( i)next。

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

本文采用文獻(xiàn)[10]中的無(wú)線電能量模型，并且無(wú)線發(fā)射模型可以根據(jù)節(jié)點(diǎn)間距離控制發(fā)射功率的大小或者自動(dòng)關(guān)閉以避免收到不需要的數(shù)據(jù)，仿真工具采用Matlab實(shí)驗(yàn)平臺(tái)，實(shí)驗(yàn)環(huán)境參數(shù)如表1所示。

表1 仿真環(huán)境參數(shù)

將100個(gè)節(jié)點(diǎn)隨機(jī)散播在100 m×100 m的區(qū)域內(nèi)，如圖2所示。

圖2 初始節(jié)點(diǎn)場(chǎng)景

為了驗(yàn)證S-LEACH協(xié)議較LEACH協(xié)議的優(yōu)越性，分析協(xié)議的穩(wěn)定性，即簇頭分布，主要從2個(gè)標(biāo)準(zhǔn)進(jìn)行評(píng)測(cè)：簇頭數(shù)量方差和簇頭分布的均勻度，其中，簇頭分布的均勻度為最小簇直徑和與最大簇直徑之比。通過(guò)表2的對(duì)比發(fā)現(xiàn)，通過(guò)螢火蟲(chóng)算法改進(jìn)的聚簇算法使該協(xié)議更穩(wěn)定。

表2 協(xié)議穩(wěn)定性對(duì)比

為了進(jìn)一步驗(yàn)證S-LEACH協(xié)議在網(wǎng)絡(luò)生存周期的優(yōu)勢(shì)。以網(wǎng)絡(luò)中存活節(jié)點(diǎn)的個(gè)數(shù)為參考標(biāo)準(zhǔn)，實(shí)驗(yàn)發(fā)現(xiàn)，在初始能量異構(gòu)環(huán)境中，LEACH協(xié)議有可能在第一輪衰亡，因?yàn)槠潆S機(jī)選取簇頭節(jié)點(diǎn)。平均第一節(jié)點(diǎn)衰亡集中在16輪左右，而S-LEACH協(xié)議可達(dá)166輪左右。由此可見(jiàn)，S-LEACH 協(xié)議較LEACH協(xié)議對(duì)延長(zhǎng)網(wǎng)絡(luò)生命周期延長(zhǎng)了4倍左右，通過(guò)10輪的仿真統(tǒng)計(jì)分析對(duì)比見(jiàn)表3，其中，F(xiàn)ND代表第一個(gè)節(jié)點(diǎn)死亡時(shí)間、HND代表一半節(jié)點(diǎn)死亡時(shí)間、LND代表最后一個(gè)節(jié)點(diǎn)死亡時(shí)間。

表3 LE ACH協(xié)議與S-LEACH協(xié)議對(duì)比 輪

為了驗(yàn)證S-LEACH協(xié)議安全性，令w1=50、w2=30、w3=20，以不信任節(jié)點(diǎn)的檢測(cè)概率為參考。將其與BTSR[9]的路由協(xié)議進(jìn)行比較，如圖3所示。

圖3 S-LEACH與BTSR協(xié)議的安全性對(duì)比

由圖3可知，隨著非信任節(jié)點(diǎn)的比例增加，非信任節(jié)點(diǎn)的相似度提高，非信任檢測(cè)率降低。特別是當(dāng)非信任節(jié)點(diǎn)的比例超過(guò)0.4時(shí)，S-LEACH協(xié)議的檢測(cè)率較BTSR協(xié)議平均提高了2.3%。

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

隨著WSN技術(shù)的飛速發(fā)展和應(yīng)用不斷拓展，傳感器節(jié)點(diǎn)的能效和數(shù)據(jù)傳輸安全性已成為亟待解決的問(wèn)題而日益顯露出來(lái)，即便WSN已經(jīng)接納了傳統(tǒng)網(wǎng)絡(luò)相關(guān)的協(xié)議，但因其自身局限性限制，使其在多跳網(wǎng)絡(luò)環(huán)境下很難保證網(wǎng)絡(luò)安全運(yùn)行，因此本文將重點(diǎn)研究安全的節(jié)能策略，提出一種安全的低能耗分簇路由協(xié)議。

目前WSN分簇路由協(xié)議的研究還不夠成熟，安全與節(jié)能的矛盾還沒(méi)有得到完全解決，現(xiàn)有的分簇路由協(xié)議需要不斷地改進(jìn)和提高。今后可以考慮將安全節(jié)能的WSN分簇路由協(xié)議應(yīng)用于物聯(lián)網(wǎng)[11]和分布式WSN[12]。

[1] 王 殊, 閻毓杰, 胡富平, 等. 無(wú)線傳感器網(wǎng)絡(luò)的理論及應(yīng)用[M]. 北京: 北京航空航天大學(xué)出版社, 2007.

[2] 劉 強(qiáng), 黃小紅, 冷甦鵬. 一種面向物聯(lián)網(wǎng)的無(wú)線傳感器網(wǎng)絡(luò)優(yōu)化部署策略[J]. 中國(guó)通信, 2011, 8(8): 111-120.

[3] Viani F, Rocca P, Oliveri G, et al. Location, T racking, an d Imaging of Targets in W ireless Sensor Net works: An Invited Review[EB/OL]. (2011-09-10). http://onlinelibrary.wiley.com/ doi/10.1029/2010RS004561/abstract.

[4] Emeka E, Abraham O F. A Survey of Sys tem Architecture Requirements for Helth Care-based Wireless Sensor Networks[J]. Sensors, 2011, 11(5): 4875-4898.

[5] Ferna ndo L, Antonio-Javier G, Felipe G, et al. A Comprehensive Approach to WSN-based ITS Application: A Survey[J]. Sensors, 2011, 11(11): 10220-10265.

[6] Cristina A, Pedro S, Andres I, et al. Wireless Sensor Networks for Ocean ographic Monitoring: A Systematic Revie w[J]. Sensors, 2010, 10(7): 6948-6968.

[7] 王 朔, 賈翔宇, 林 強(qiáng). 基于可信度的無(wú)線傳感器網(wǎng)絡(luò)安全路由算法[J]. 通信學(xué)報(bào), 2008, 299(11): 105-112.

[8] 江自兵, 周鳴爭(zhēng), 梁祥君, 等. 一種基于節(jié)點(diǎn)信譽(yù)度的無(wú)線傳感器網(wǎng)絡(luò)信任模型[J]. 安徽工程大學(xué)學(xué)報(bào), 20 11, 26(1): 58-61.

[9] Lewis S, Cratsley C. Flash Signal Evolution, Mate Choice, and Predation in Fireflies[J]. Annual Review of Entomology, 2008, 2008, (53): 293-321.

[10] 朱 程, 周鳴爭(zhēng), 許金生. B TSR: 一種基于行為可信的安全數(shù)據(jù)融合與路由算法[J]. 計(jì)算機(jī)應(yīng)用, 2 008, 11(28): 2820-2824.

[11] 錢志鴻, 王義君. 面向物聯(lián)網(wǎng)的無(wú)線傳感器網(wǎng)絡(luò)綜述[J].電子與信息學(xué)報(bào), 2013, 35(1): 215-226.

[12] 豐寧寧, 王成華. 一種基于分布式協(xié)作的WSN定位方法[J].計(jì)算機(jī)技術(shù)與發(fā)展, 2012, 22(5): 60-63.

編輯 任吉慧

Research on Safe Energy Saving Routing Algorithm Based on LEACH Protocol

LV Lin-tao, HU Lei-lei, YANG Yu-xiang, TAN Fang

(School of Computing Science and Engineering, Xi’an University of Technology, Xi’an 710048, China)

This paper presents a safe and low energy consumption clustering routing protocol S-LEACH to solve existing and classical adaptive routing protocol LEACH in the net work survival period and the deficiency of the security. It evaluates each node of the detected environment based on trust model from three aspe cts of node data, communication bandwidth and residual energy. It sets up the node credibility collection to select the head according to threshold value, and uses the firefly algorithm to simulator clusterin g. The base station node communicates with multiple hops routing algorithms to reduce the additional energy consumption. Experimental results show that S-LEACH’s life cycle in the network prolongs more than four times compared with LEACH and is increased by 2.3% compared with BTSR protocol in the untrusted node detection.

Wireless Sensor Networks(WSN); node credibility; firefly algorithm; clustering; security; clustering routing

10.3969/j.issn.1000-3428.2014.05.013

國(guó)家自然科學(xué)基金資助項(xiàng)目(61273271)；中國(guó)博士后科學(xué)基金資助項(xiàng)目(20110491674)；陜西省教育廳科學(xué)研究計(jì)劃基金資助項(xiàng)目(12JK0928)。

呂林濤(1955－)，男，教授、碩士，主研方向：網(wǎng)絡(luò)與信息安全，數(shù)據(jù)挖掘，無(wú)線傳感器網(wǎng)絡(luò)；胡雷雷，碩士；楊宇祥，副教授；譚 芳，講師、碩士。

2013-01-09

2013-05-10E-mail：hulei19860503@163.com

1000-3428(2014)05-0059-03

A

TP393.08