蔣 華，曾梅梅

(桂林電子科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣西 桂林541004)

0 引 言

無(wú)線傳感器網(wǎng)絡(luò)是物聯(lián)網(wǎng)中重要的末梢網(wǎng)之一，伴隨著物聯(lián)網(wǎng)的興起，使得無(wú)線傳感器網(wǎng)絡(luò)對(duì)安全、能量的需求被推向了更高的層次，促進(jìn)了人們對(duì)無(wú)線傳感器網(wǎng)絡(luò)的發(fā)展做進(jìn)一步深入地研究。

在無(wú)線傳感器網(wǎng)絡(luò)中，安全高效的路由協(xié)議應(yīng)該包括如下特性:1)降低配置差錯(cuò)的影響;2)減少網(wǎng)絡(luò)整體能耗;3)確保只有合法節(jié)點(diǎn)參與消息轉(zhuǎn)發(fā);4)防止攻擊者注入偽造的路由信息。由于無(wú)線傳感器網(wǎng)絡(luò)的種種特性，導(dǎo)致路由協(xié)議易于受到虛假路由信息攻擊、選擇性轉(zhuǎn)發(fā)攻擊、污水池攻擊、女巫攻擊、蠕蟲(chóng)洞攻擊、Hello 洪泛攻擊、假冒應(yīng)答攻擊及關(guān)鍵點(diǎn)攻擊等［1，2］。而基于密碼體系的傳統(tǒng)安全機(jī)制只能抵抗外部來(lái)源的攻擊，其設(shè)計(jì)思路與實(shí)現(xiàn)機(jī)制都無(wú)法解決開(kāi)放環(huán)境下節(jié)點(diǎn)被俘獲所帶來(lái)的內(nèi)部攻擊問(wèn)題［3～4］。已經(jīng)有大量的研究工作從各個(gè)角度來(lái)延長(zhǎng)網(wǎng)絡(luò)生命周期和提高網(wǎng)絡(luò)安全傳輸指數(shù)［5～6］。

在大規(guī)模的無(wú)線傳感器網(wǎng)絡(luò)中，根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，網(wǎng)絡(luò)中的路由協(xié)議分為平面型和層次型2 種協(xié)議，但在節(jié)點(diǎn)和Sink 節(jié)點(diǎn)之間通常采用多跳形式建立連接。典型的平面路由協(xié)議有 Flooding，Gossiping，Spin 路由、定向擴(kuò)散(directed diffusion)協(xié)議、謠傳路由、有序分配路由(SAR)和基于位置的 GEAR 路由協(xié)議等。其中，F(xiàn)looding［7］和 Gossiping［8］協(xié)議存在信息重疊和盲目使用資源問(wèn)題，且擴(kuò)展性差。文獻(xiàn)［9］通過(guò)發(fā)送元數(shù)據(jù)進(jìn)行協(xié)商來(lái)發(fā)送數(shù)據(jù)，但可靠性差，同時(shí)Sink 周?chē)墓?jié)點(diǎn)能量容易耗盡。無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)由于自身資源受限、所處環(huán)境惡劣等問(wèn)題，使得它容易被外界所俘獲，成為惡意節(jié)點(diǎn)的情況。而目前，現(xiàn)有路由協(xié)議的研究主要側(cè)重于如何提高節(jié)點(diǎn)能量利用率或網(wǎng)絡(luò)的可信度［4，10］，本文在平面型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的前提下，提出一種傳感器能量高效的安全路由(EESR)方案，該方案使網(wǎng)絡(luò)性能得到很大的提高。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

假設(shè)n 個(gè)傳感器節(jié)點(diǎn)隨機(jī)均勻分布在一個(gè)正方形區(qū)域A 內(nèi)，傳感器節(jié)點(diǎn)在部署之后就不再移動(dòng);惟一的中繼節(jié)點(diǎn)部署在區(qū)域A 以外的一個(gè)固定位置，并且部署后網(wǎng)絡(luò)無(wú)需人為維護(hù);網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在組網(wǎng)后相對(duì)穩(wěn)定，移動(dòng)性比較小;所有節(jié)點(diǎn)都是同構(gòu)的，具備相同的初始能量和數(shù)據(jù)融合的功能，且都有一個(gè)唯一的標(biāo)識(shí)((ID);節(jié)點(diǎn)不需要GPS 裝備，也不用通過(guò)測(cè)量的方法知道其具體位置;無(wú)線發(fā)射功率是可控，即節(jié)點(diǎn)可以根據(jù)距離來(lái)調(diào)整發(fā)射功率的大小。

1.2 無(wú)線能量模型［11］

無(wú)線能量模型，是指發(fā)射功率的衰減隨著傳輸距離的增大而呈指數(shù)衰減。當(dāng)發(fā)送和接收節(jié)點(diǎn)之間的距離在d ＜d0時(shí)，采用自由空間模型，發(fā)射功率呈d2衰減;否則，采用多路徑衰減模型，發(fā)射功率呈d4衰減。

1.3 無(wú)線傳輸能量模型［12］

無(wú)線傳輸能量模型如式(1)和式(2)所示

其中，式(1)表示發(fā)射k bit 數(shù)據(jù)損耗的能量，由發(fā)射電路損耗和功率放大損耗兩部分構(gòu)成，Eelec為無(wú)線通信模塊接收或發(fā)送單位比特?cái)?shù)據(jù)電路所消耗能量，εfs，εamp分別為發(fā)射放大器在2 種信道模型下傳送每比特?cái)?shù)據(jù)所消耗的能量，d0為某一距離值;式(2)表示接收k bit數(shù)據(jù)的能量損耗，該值僅由電路損耗引起。同時(shí)，假設(shè)無(wú)線信道對(duì)稱(chēng)傳輸，即從節(jié)點(diǎn) u 傳送消息到 v 消耗的能量等于從v 傳送同樣的消息到 u 所消耗的能量。

1.4 信任模型

為了減少信任值較低的節(jié)點(diǎn)成為網(wǎng)絡(luò)傳輸路徑，并且排除網(wǎng)絡(luò)中的惡意節(jié)點(diǎn)，本文針對(duì)文獻(xiàn)［13］中提出的可信度評(píng)價(jià)機(jī)制做一定的改進(jìn)

其中，ET為節(jié)點(diǎn)的總能量;VIb為由入侵檢測(cè)系統(tǒng)列出的惡意節(jié)點(diǎn)表，1 為好節(jié)點(diǎn)，0 為惡意節(jié)點(diǎn);VIr為主動(dòng)觀測(cè)值，由節(jié)點(diǎn)對(duì)鄰居節(jié)點(diǎn)進(jìn)行主動(dòng)監(jiān)控來(lái)獲得的;VSr為間接觀測(cè)值，通過(guò)與其他節(jié)點(diǎn)交換信息獲得的經(jīng)驗(yàn)值;f1，f2，f3可以根據(jù)網(wǎng)絡(luò)具體要求來(lái)設(shè)不同的值，假設(shè):f1+f2+f3=1，并進(jìn)行歸一化。

2 算法思想

本文在不考慮空間差異的情況下，將無(wú)線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)抽象成圖的頂點(diǎn)，網(wǎng)絡(luò)節(jié)點(diǎn)之間的通信關(guān)系抽象成圖中頂點(diǎn)與頂點(diǎn)之間的連邊，那么，無(wú)線傳感器網(wǎng)絡(luò)可表示為圖G=(V，E)，其中，V 表示傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的集合，E表示網(wǎng)絡(luò)中節(jié)點(diǎn)與節(jié)點(diǎn)之間的通信關(guān)系。本文提出的方案將數(shù)據(jù)包在節(jié)點(diǎn)間傳輸所需的能量大小和可信任度值作為邊的權(quán)值，運(yùn)用Prim 算法和Kruskal 算法來(lái)解決Gossiping算法存在的問(wèn)題。

2.1 改進(jìn)后的Prim 算法和Kruskal 算法

Prim 算法和Kruskal 算法是生成最小生成樹(shù)的經(jīng)典算法，其中，Prim 算法適用于稀疏圖，Kruskal 算法適用于稠密圖。本文采用最小生成樹(shù)的思想來(lái)構(gòu)造出無(wú)線傳感器網(wǎng)絡(luò)中的最優(yōu)路由路徑，針對(duì)文獻(xiàn)［14］的最小生成樹(shù)算法改進(jìn)如下:

假設(shè)V 為圖中頂點(diǎn)的集合，E 為圖中邊的集合，RE 為最優(yōu)路由路徑中的邊的集合，則改進(jìn)后的Prim 和Kruskal算法通過(guò)以下步驟可以得到最優(yōu)路由路徑:

1)改進(jìn)后的Prim 算法的基本步驟

a.初始化:U ={u0}，RE ={}，其中，u0表示為中繼節(jié)點(diǎn);此步驟設(shè)立一個(gè)只有節(jié)點(diǎn)u0的節(jié)點(diǎn)集U 和一個(gè)空的邊集RE 作為最小生成樹(shù)的初始形態(tài)，在隨后的算法執(zhí)行中，這個(gè)形態(tài)會(huì)不斷地發(fā)生變化，直到得到最小生成樹(shù)為止;

b.如果V－U={}，則輸出最優(yōu)路由路徑R，并結(jié)束算法;

c.在所有兩棲邊中找一條權(quán)最小的邊(u，v)(若候選兩棲邊中的最小邊不止一條，可任選一條;如果(u，v)=0 值時(shí)，把節(jié)點(diǎn)v 移出V－U 集合，繼續(xù)下一步的比較)，將邊(u，v)加入到邊集RE 中，并將頂點(diǎn)v 并入集合U 中;

d.由于新頂點(diǎn)加入，U 的狀態(tài)發(fā)生變化，需要對(duì)U 與V－U 之間的兩棲邊進(jìn)行調(diào)整;

e.轉(zhuǎn)步驟(2)。

2)改進(jìn)后的Kruskal 算法的基本步驟

a.初始化:RV={v0，v1，……，vn－1}，RE ={}表示路由;其中，RV 表示一個(gè)只含有n 頂點(diǎn)，而邊集為空的子圖。

b.如果E={}，則輸出最優(yōu)路由路徑R，并結(jié)束算法;

c.在有序的E(G)邊表序列中，從當(dāng)前位置向后尋找滿足此條件權(quán)值最小的邊(u，v):使得u 在一個(gè)連通分量上，v在另一個(gè)連圖分量上，即(u，v)是滿足此條件權(quán)值最小的邊，將其加入到RE 中，合并u 與v 所在2 個(gè)連通分量為一個(gè)連通分量，更新E 集合;如果E{(u，v)=0}，則移出邊(u，v)。

d.轉(zhuǎn)步驟(2)。

2.2 最優(yōu)路由路徑

本算法分為構(gòu)建最優(yōu)路由路徑和穩(wěn)定工作階段2 個(gè)部分組成。每一輪通過(guò)在中繼節(jié)點(diǎn)設(shè)置一個(gè)時(shí)間戳，來(lái)對(duì)網(wǎng)絡(luò)最優(yōu)路由路徑進(jìn)行實(shí)時(shí)更新。為減少頻繁構(gòu)建最優(yōu)路由路徑產(chǎn)生的能量損耗，所以，穩(wěn)定工作階段的時(shí)間要足夠長(zhǎng)。

1)無(wú)線傳感器網(wǎng)絡(luò)是以數(shù)據(jù)為中心的路由機(jī)制，它有2 種方法用于信息分發(fā):Sink 節(jié)點(diǎn)廣播消息;傳感器節(jié)點(diǎn)廣播所獲取的消息，等待Sink 節(jié)點(diǎn)的查詢(xún)消息，所以，本文采用由網(wǎng)絡(luò)中任一節(jié)點(diǎn)廣播發(fā)送用于發(fā)現(xiàn)鄰居節(jié)點(diǎn)請(qǐng)求報(bào)文，請(qǐng)求報(bào)文信息中攜帶發(fā)送節(jié)點(diǎn)的節(jié)點(diǎn)信息(ID)和節(jié)點(diǎn)對(duì)發(fā)送節(jié)點(diǎn)的E 值(順序標(biāo)注)。

2)隨著請(qǐng)求報(bào)文在網(wǎng)絡(luò)中的傳播，根據(jù)無(wú)線傳感器的特性，最后請(qǐng)求報(bào)文信息都會(huì)匯聚到Sink 節(jié)點(diǎn)，通過(guò)請(qǐng)求報(bào)文中信息，Sink 節(jié)點(diǎn)能夠獲悉到整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和邊權(quán)值。

3)中繼節(jié)點(diǎn)在收到廣播路徑上的信息后，構(gòu)造成一個(gè)N×N 的矩陣，因?yàn)闊o(wú)向圖是對(duì)稱(chēng)陣，為了減少中繼節(jié)點(diǎn)的存儲(chǔ)，采用了稀疏三元組來(lái)存儲(chǔ)。

4)在中繼節(jié)點(diǎn)通過(guò)采用改進(jìn)后的 Prim 算法或者Kruskal 算法實(shí)現(xiàn)生成一個(gè)最優(yōu)路由路徑。

5)Sink 節(jié)點(diǎn)根據(jù)最優(yōu)路徑發(fā)出查詢(xún)信息時(shí)，然后由感知數(shù)據(jù)沿查詢(xún)消息的反向路徑向Sink 節(jié)點(diǎn)傳送，父節(jié)點(diǎn)利用數(shù)據(jù)融合對(duì)數(shù)據(jù)進(jìn)行處理，來(lái)減少數(shù)據(jù)通信量，如圖1、圖2所示。

圖1 算法思想示意圖(無(wú)惡意節(jié)點(diǎn)情況)Fig 1 Diagram of the algorithm idea(withouth malicious node)

3 模擬與分析

本文在NS2 環(huán)境下采用C + + 語(yǔ)言編碼實(shí)現(xiàn)來(lái)仿真的。傳感器網(wǎng)絡(luò)模型的主要參數(shù)如下:100 個(gè)節(jié)點(diǎn)平均分布在100 m×100 m 地域范圍A 內(nèi)，Sink 節(jié)點(diǎn)在傳感器區(qū)域A外任意位置，每個(gè)節(jié)點(diǎn)的初始能量ET=0.5 J，中繼節(jié)點(diǎn)采用改進(jìn)后的Prim 算法進(jìn)行生成最優(yōu)路由路徑。為了測(cè)試該算法的性能，將其與Gossiping 進(jìn)行比較。圖3 為初始能量相同時(shí)不同協(xié)議的網(wǎng)絡(luò)生命周期。從圖中可以看到:此算法比Gossiping 的生命周期提高了將近7 倍(以最后一個(gè)節(jié)點(diǎn)死亡為標(biāo)準(zhǔn))。圖4 為無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)丟包率隨惡意節(jié)點(diǎn)的變化情況。為了簡(jiǎn)化實(shí)驗(yàn)，本實(shí)驗(yàn)通過(guò)人為的設(shè)置惡意結(jié)點(diǎn)，通過(guò)圖4 可以看出:在不同惡意節(jié)點(diǎn)數(shù)目，相比Gossiping 協(xié)議，本文方法的網(wǎng)絡(luò)丟包率普遍降低了，丟包率平均降低了大約22%。

圖3 初始能量相同時(shí)不同協(xié)議的網(wǎng)絡(luò)生命周期Fig 3 The network life cycle of different protocols with the same initial energy

圖4 無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)丟包率隨惡意節(jié)點(diǎn)的變化情況Fig 4 Loss packet rate of WSNs node changes with variation of malicious nodes

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

本文提出了一種EESR 協(xié)議，通過(guò)傳感器中的任一節(jié)點(diǎn)進(jìn)行廣播請(qǐng)求報(bào)文，對(duì)路徑信息進(jìn)行標(biāo)識(shí)，Sink 節(jié)點(diǎn)根據(jù)路徑信息，獲取到網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的全部信息，根據(jù)改進(jìn)后的Prim 或者Kruskal 算法得出一個(gè)最優(yōu)路由路徑，最后由Sink節(jié)點(diǎn)發(fā)出查詢(xún)信息，感知數(shù)據(jù)沿查詢(xún)消息的反向路徑向Sink 節(jié)點(diǎn)傳送。該算法僅適用于平面型的網(wǎng)絡(luò)拓?fù)淝闆r下。

［1］ Kifayat K，Merabti M，Shi Q.Security in wireless sensor networks［Z］.Handbook of Information and Communication Security，Berlin:Springer，2010:513 － 552.

［2］ Sen Jaydip.A survey on wireless sensor network security［J］.International Journal of Communication Networks and Information Security(IJCNIS)，2009，2:55 － 78.

［3］ Boukerch A，Xu L，El－khatib K.Trust－based security for wireless Ad Hoc and sensor networks［J］.Computer Communications，2007，30:2413 － 2427.

［4］ 吳銀鋒，周 翔，馮仁劍，等.基于節(jié)點(diǎn)信任值的無(wú)線傳感器網(wǎng)絡(luò)安全路由［J］.儀器儀表學(xué)報(bào)，2012(1):221 －227.

［5］ Kan Baoqiang，Cai Li，Zhu Hongsong，et al.Accurate energy model for WSNs node and its optimal design［J］.Journal of Systems Engineering and Electronics，2008(3):427 －433.

［6］ 胡向東，魏琴芳，唐 慧.物聯(lián)網(wǎng)中數(shù)據(jù)融合的信譽(yù)度模型與仿真［J］.儀器儀表學(xué)報(bào)，2010，31(11 ):2636 －2640.

［7］ Hedetniemi S，Liestman A.A survey of Gossiping and broadcasting in communtication networks［J］.Networks，1998，18(4):319 －349.

［8］ Sinha K，Ghose S，Srimani P K.Fast deterministic broadcast and gossiping algorithms for mobile［J］.Journal of Parallel and Distributed Compputing，2008，68，922 － ，938.

［9］ Kulik J，Heinzelman Wendi ，Balakrishnan H.Negotiation－based protocols for disseminating information in wireless sensor networks［J］.Wireless Networks，2002，8:169 － 185.

［10］ 李訓(xùn)光，顏 聽(tīng)，李臘元.一種基于可視角度能量高效的路由算法［J］.微計(jì)算機(jī)信息，2009，25(3):216 －314.

［11］ Rappaport T.Wireless communications:Principles and practice［M］.New Jersey:Prentice Hall Inc，1996.

［12］ Heinzelman W R，Chandrakasan A，Bala Krishnan H.An application specific protocol architecture for wireless microsensor networks［J］.IEEE Trans on Wireless Communications，2002，1(4):660 －670.

［13］ 章 靜，許 力，徐道煒.自組網(wǎng)中基于可信度評(píng)價(jià)的安全分簇策略［J］.計(jì)算機(jī)應(yīng)用，2007，10(27):2426 －2429.

［14］ Levin M S H，Zamkovoy A.A multicriteria steiner tree with the cost of Steiner vertices［J］.Jouranl of Communications Technology and Electronics，2011，56(12):1527 － 1542.