一種基于元胞自動(dòng)機(jī)的無(wú)線傳感器網(wǎng)絡(luò)安全補(bǔ)丁分發(fā)算法

李 林

(天津商業(yè)大學(xué)信息工程學(xué)院，天津 300134)

0 引言

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSN)是由大量部署在監(jiān)測(cè)區(qū)域內(nèi)的廉價(jià)微型傳感器節(jié)點(diǎn)組成，通過(guò)無(wú)線網(wǎng)絡(luò)傳輸方式形成的一個(gè)多跳的自組織、自適應(yīng)的智能網(wǎng)絡(luò)系統(tǒng)[1]，其目的是合作地感知、收集并處理網(wǎng)絡(luò)覆蓋區(qū)域的信息，發(fā)送給管理者。WSN在各個(gè)領(lǐng)域有著廣泛的應(yīng)用[2]。病毒對(duì)無(wú)線傳感器網(wǎng)絡(luò)而言是一個(gè)嚴(yán)峻的安全問(wèn)題[3-4]。計(jì)算機(jī)網(wǎng)絡(luò)中通常采用給計(jì)算機(jī)系統(tǒng)打上安全補(bǔ)丁的算法來(lái)清除病毒，但是對(duì)于無(wú)線傳感器網(wǎng)絡(luò)，由于其部署量大，節(jié)點(diǎn)難以全部回收，必須考慮采用特殊的安全補(bǔ)丁分發(fā)算法來(lái)清除病毒。

1 模型描述

本文采用正方形網(wǎng)絡(luò)作為無(wú)線傳感器網(wǎng)絡(luò)模型[5]，改進(jìn)的二維元胞自動(dòng)機(jī)動(dòng)力學(xué)模型描述網(wǎng)絡(luò)中節(jié)點(diǎn)的狀態(tài)。

1.1 無(wú)線傳感器網(wǎng)絡(luò)模型

本文的無(wú)線傳感器網(wǎng)絡(luò)模型中，監(jiān)測(cè)區(qū)域?yàn)橐粋€(gè)正方形區(qū)域，其邊長(zhǎng)為l，在監(jiān)測(cè)區(qū)域內(nèi)包含節(jié)點(diǎn)個(gè)數(shù)為n，節(jié)點(diǎn)密度為ρ，隨機(jī)均勻分布在二維區(qū)域內(nèi)，節(jié)點(diǎn)信號(hào)最大發(fā)射距離為r，其可以在距離r內(nèi)進(jìn)行通信。這些節(jié)點(diǎn)負(fù)責(zé)感知和采集區(qū)域內(nèi)的數(shù)據(jù)并通過(guò)多跳的方式傳輸給基站。這些網(wǎng)絡(luò)節(jié)點(diǎn)初始狀態(tài)下被感染節(jié)點(diǎn)的比例為θ，節(jié)點(diǎn)成功接收安全補(bǔ)丁概率為α，安全補(bǔ)丁清除病毒的概率為β。

根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)在網(wǎng)絡(luò)中的不同狀態(tài)，網(wǎng)絡(luò)模型根據(jù)節(jié)點(diǎn)的特性劃分為以下3種狀態(tài)，如表1所示。

表1 節(jié)點(diǎn)狀態(tài)參數(shù)表

1.2 改進(jìn)的二維元胞自動(dòng)機(jī)模型

元胞自動(dòng)機(jī)是由有限個(gè)隨機(jī)分布的元胞對(duì)象組成的離散動(dòng)態(tài)系統(tǒng)[6]。每個(gè)元胞都有一個(gè)狀態(tài)，它在每一個(gè)時(shí)間步的狀態(tài)根據(jù)變化規(guī)則進(jìn)行變化。文中提出的元胞自動(dòng)機(jī)模型通過(guò)一個(gè)四元組來(lái)表示(C，S，N，F(xiàn))：C表示元胞空間；S表示元胞的狀態(tài)集；N表示元胞鄰域；F為元胞演化規(guī)則。二維元胞自動(dòng)機(jī)的安全補(bǔ)丁分發(fā)算法包括上述的4部分內(nèi)容，用式(1)表示：

CAS=(C，S，N，F(xiàn))

(1)

(1)元胞空間C：這里代表l×l個(gè)格子的二維網(wǎng)格，設(shè)每個(gè)單元最多只容納一個(gè)傳感器節(jié)點(diǎn)。節(jié)點(diǎn)在空間中的位置可以用二維網(wǎng)格中的水平坐標(biāo)i和垂直坐標(biāo)j表示；

C={(i,j)|1≤i≤l,1≤j≤l}

(2)

(2)元胞的狀態(tài)集S：包含兩個(gè)狀態(tài)集分別為SC和MAC。其中SC為節(jié)點(diǎn)的狀態(tài)，節(jié)點(diǎn)共有3個(gè)狀態(tài)：正常節(jié)點(diǎn)狀態(tài)、已感染狀態(tài)和獲得安全補(bǔ)丁后的免疫狀態(tài)。當(dāng)正常節(jié)點(diǎn)獲得安全補(bǔ)丁后直接進(jìn)入免疫狀態(tài)，已感染節(jié)點(diǎn)的病毒被清除后進(jìn)入免疫狀態(tài)[7]。具體如式(3)所示：

(3)

狀態(tài)集MAC考慮了無(wú)線傳感器網(wǎng)絡(luò)傳輸中的信道訪問(wèn)原則，分發(fā)補(bǔ)丁時(shí)采用CSMA/CA方式[8]：當(dāng)某節(jié)點(diǎn)監(jiān)聽(tīng)到信道忙碌后再隨機(jī)退避一段時(shí)間后進(jìn)行數(shù)據(jù)發(fā)送，當(dāng)一個(gè)節(jié)點(diǎn)在發(fā)送數(shù)據(jù)時(shí)其鄰域節(jié)點(diǎn)均不能發(fā)送，只有監(jiān)聽(tīng)到信道空閑后才會(huì)嘗試發(fā)送數(shù)據(jù)[9]。具體如式(4)所示；

(4)

(3)元胞鄰域：普通的摩爾型鄰域[10]如圖1所示，灰色部分為K節(jié)點(diǎn)的元胞鄰域，但由于單個(gè)傳感器節(jié)點(diǎn)的通信覆蓋為圓形，不能很好描述網(wǎng)絡(luò)的真實(shí)狀態(tài)[11]。文中的節(jié)點(diǎn)鄰域采用改進(jìn)的擴(kuò)展型摩爾鄰域，剔除了通信距離內(nèi)無(wú)法覆蓋的元胞，如圖2所示。每個(gè)傳感器節(jié)點(diǎn)最大的發(fā)射距離是r，因此任意節(jié)點(diǎn)Cij的鄰域?yàn)?/p>

(5)

圖1 元胞自動(dòng)機(jī)摩爾型鄰域

圖2 改進(jìn)型元胞自動(dòng)機(jī)摩爾型鄰域

在此模型中，只有屬于鄰域范圍內(nèi)的節(jié)點(diǎn)才可以相互通信。

(4)元胞狀態(tài)轉(zhuǎn)換函數(shù)。節(jié)點(diǎn)的狀態(tài)SCij在t時(shí)刻的狀態(tài)SCij(t)是由t-1時(shí)刻節(jié)點(diǎn)的狀態(tài)SCij(t-1)以及其鄰域節(jié)點(diǎn)的狀態(tài)集SNij共同決定的，其轉(zhuǎn)換函數(shù)可以由式(6)表示：

SCij(t)=F(SCij(t-1)，SNij(t-1))

(6)

若節(jié)點(diǎn)在t-1時(shí)刻是正常節(jié)點(diǎn)狀態(tài)，狀態(tài)轉(zhuǎn)換函數(shù)為

(7)

式中兩個(gè)函數(shù)的最大值為節(jié)點(diǎn)的狀態(tài)SCij。若這個(gè)健康節(jié)點(diǎn)鄰域有e個(gè)獲得安全補(bǔ)丁并在免疫狀態(tài)的節(jié)點(diǎn)發(fā)送安全補(bǔ)丁包，在這個(gè)時(shí)間間隔內(nèi)，有1-(1-α)e的幾率收到補(bǔ)丁包，當(dāng)信道處于空閑狀態(tài)，則節(jié)點(diǎn)進(jìn)入免疫狀態(tài)。其中，這個(gè)狀態(tài)轉(zhuǎn)化函數(shù)具體描述為

(8)

若節(jié)點(diǎn)在t-1時(shí)刻是已感染狀態(tài)。狀態(tài)轉(zhuǎn)換函數(shù)為

(9)

式中兩個(gè)函數(shù)的最大值為節(jié)點(diǎn)的狀態(tài)SCij。若這個(gè)節(jié)點(diǎn)鄰域有e個(gè)獲得安全補(bǔ)丁并在免疫狀態(tài)的節(jié)點(diǎn)發(fā)送安全補(bǔ)丁包，在這個(gè)時(shí)間間隔內(nèi)，有1-(1-α)e的幾率收到補(bǔ)丁包，當(dāng)信道處于空閑狀態(tài)，則節(jié)點(diǎn)成功接收到補(bǔ)丁包。每收到一個(gè)補(bǔ)丁包后，有β的概率進(jìn)入免疫狀態(tài)，則收到g個(gè)安全補(bǔ)丁包后治愈的幾率為(1-(1-α)e)(1-(1-β)g)，其中g(shù)≤e。這個(gè)狀態(tài)轉(zhuǎn)化函數(shù)具體描述為

(10)

若節(jié)點(diǎn)在t-1時(shí)刻已經(jīng)處在免疫狀態(tài),則狀態(tài)轉(zhuǎn)換函數(shù)為

(11)

節(jié)點(diǎn)維持此狀態(tài)不變，僅向外繼續(xù)分發(fā)安全補(bǔ)丁。

2 基于元胞自動(dòng)機(jī)的安全補(bǔ)丁分發(fā)算法

基于二維元胞自動(dòng)機(jī)的安全補(bǔ)丁分發(fā)算法中，不同節(jié)點(diǎn)的工作方式為以下步驟：

2.1 初始節(jié)點(diǎn)

(1)l×l正方形區(qū)域內(nèi)，在已知被感染的無(wú)線傳感器網(wǎng)絡(luò)中選取一個(gè)或若干個(gè)節(jié)點(diǎn)采取人工燒寫(xiě)程序的方式打上安全補(bǔ)丁，無(wú)論節(jié)點(diǎn)之前是什么狀態(tài)，均進(jìn)入已打上安全補(bǔ)丁的對(duì)病毒免疫狀態(tài)。然后采用二維元胞自動(dòng)機(jī)的方式向外分發(fā)安全補(bǔ)丁。

(2)處在免疫狀態(tài)的節(jié)點(diǎn)計(jì)算通過(guò)式(1)計(jì)算自己的狀態(tài)。

節(jié)點(diǎn)在獲得安全補(bǔ)丁后其狀態(tài)為SCij=2，向處在本節(jié)點(diǎn)的元胞鄰域內(nèi)的節(jié)點(diǎn)分發(fā)安全補(bǔ)丁，與鄰域內(nèi)的節(jié)點(diǎn)進(jìn)行通信，節(jié)點(diǎn)的鄰域?yàn)楦倪M(jìn)的擴(kuò)展型摩爾型鄰域，由式(5)計(jì)算。

2.2 病毒感染狀態(tài)節(jié)點(diǎn)

已感染病毒狀態(tài)的節(jié)點(diǎn)通過(guò)式(9)計(jì)算自己的下一時(shí)刻狀態(tài)。首先探測(cè)鄰域內(nèi)的信道狀態(tài)，若信道空閑，則接收鄰域內(nèi)這些節(jié)點(diǎn)發(fā)送的補(bǔ)丁包。若這個(gè)節(jié)點(diǎn)鄰域有e個(gè)獲得安全補(bǔ)丁并在免疫狀態(tài)的節(jié)點(diǎn)發(fā)送安全補(bǔ)丁包，在這個(gè)時(shí)間間隔內(nèi)，有1-(1-α)e的幾率收到補(bǔ)丁包。每收到一個(gè)補(bǔ)丁包后，有β的概率進(jìn)入免疫狀態(tài)，則收到g個(gè)安全補(bǔ)丁包后治愈的幾率為(1-(1-α)e)(1-(1-β)g)，其中g(shù)≤e。節(jié)點(diǎn)若被治愈則進(jìn)入2.1中(2)步驟，節(jié)點(diǎn)若未被治愈，則重復(fù)本步驟。

2.3 正常工作節(jié)點(diǎn)

正常工作節(jié)點(diǎn)通過(guò)式(7)來(lái)計(jì)算自己下一時(shí)刻狀態(tài)。首先探測(cè)鄰域內(nèi)的信道狀態(tài)，若信道空閑，則接收鄰域內(nèi)這些節(jié)點(diǎn)發(fā)送的補(bǔ)丁包。若這個(gè)節(jié)點(diǎn)鄰域有e個(gè)獲得安全補(bǔ)丁并在免疫狀態(tài)的節(jié)點(diǎn)發(fā)送安全補(bǔ)丁包，在這個(gè)時(shí)間間隔內(nèi)，有1-(1-α)e的幾率收到補(bǔ)丁包。收到補(bǔ)丁包后，正常節(jié)點(diǎn)進(jìn)行安全升級(jí)，免疫病毒侵害，隨后進(jìn)入2.1中(2)步驟。若未收到補(bǔ)丁包則重復(fù)此步驟。

令V(t)表示在t時(shí)刻已被病毒感染的狀態(tài)傳感器節(jié)點(diǎn)的數(shù)量占比，R(t)表示在t時(shí)刻處于能正常工作但未打上安全補(bǔ)丁狀態(tài)的傳感器節(jié)點(diǎn)的數(shù)量占比，M(t)表示在t時(shí)刻已打上安全補(bǔ)丁對(duì)病毒免疫狀態(tài)的傳感器節(jié)點(diǎn)的數(shù)量占比，由式(12)表示：

(12)

式中V(t)+R(t)+M(t)=1。

經(jīng)過(guò)一段時(shí)間，節(jié)點(diǎn)采用本文提出的一種基于元胞自動(dòng)機(jī)的安全補(bǔ)丁分發(fā)算法將安全補(bǔ)丁分發(fā)完畢。

3 仿真

實(shí)驗(yàn)網(wǎng)絡(luò)環(huán)境設(shè)置如下：監(jiān)測(cè)區(qū)域?yàn)橐粋€(gè)正方形區(qū)域，其邊長(zhǎng)l=200 m，在監(jiān)測(cè)區(qū)域內(nèi)包含節(jié)點(diǎn)個(gè)數(shù)為n，節(jié)點(diǎn)密度為ρ，節(jié)點(diǎn)的通信距離為r，網(wǎng)絡(luò)中初始被感染節(jié)點(diǎn)的比例為θ，節(jié)點(diǎn)成功接收安全補(bǔ)丁概率為α，安全補(bǔ)丁清除病毒的概率為β，每輪單位時(shí)間內(nèi)進(jìn)行10次通信。

在實(shí)驗(yàn)中，研究在無(wú)線傳感器的不同參數(shù)下安全補(bǔ)丁分發(fā)效果，初始值節(jié)點(diǎn)個(gè)數(shù)n=20 000，節(jié)點(diǎn)密度為ρ=0.5，通信距離r=10 m，初始被感染比例θ=0.4，節(jié)點(diǎn)成功接收安全補(bǔ)丁概率α=0.8，安全補(bǔ)丁清除病毒的概率為β=0.6時(shí)，將坐標(biāo)為(100,100)節(jié)點(diǎn)打上安全補(bǔ)丁后的V(t)、R(t)、M(t)的曲線如圖3所示。實(shí)驗(yàn)表明在第23輪后所有節(jié)點(diǎn)均已打上安全補(bǔ)丁，本文提出的算法非常高效。

圖3 初始參數(shù)下補(bǔ)丁分發(fā)演化特性曲線

文中研究在安全補(bǔ)丁清除病毒能力較差時(shí)的補(bǔ)丁分發(fā)效果，取β=0.2。圖4表示不同的β取值下的V(t)曲線，圖5表示不同取值下的M(t)曲線。該實(shí)驗(yàn)表明：當(dāng)清除能力較差(β=0.2)時(shí)，該算法仍能在第30輪將所有節(jié)點(diǎn)打上補(bǔ)丁。

圖4 不同β的V(t)曲線

圖5 不同β的M(t)曲線

文中研究網(wǎng)絡(luò)中初始被感染節(jié)點(diǎn)的比例較高時(shí)補(bǔ)丁分發(fā)效果，取θ=0.8。圖6表示不同的θ取值下的V(t)曲線，圖7表示不同取值下的M(t)曲線。該實(shí)驗(yàn)表明：當(dāng)感染節(jié)點(diǎn)在初始被感染節(jié)點(diǎn)補(bǔ)丁較高，80%節(jié)點(diǎn)都受病毒感染時(shí)，該算法可以在第25輪將所有節(jié)點(diǎn)打上補(bǔ)丁。

圖6 不同θ的V(t)曲線

圖7 不同θ的M(t)的曲線

文中研究在不同坐標(biāo)位置初始節(jié)點(diǎn)的分發(fā)效果，分別從(100,100)，(50,50)和(10,10)位置開(kāi)始分發(fā)安全補(bǔ)丁，圖8表示不同位置取值下的M(t)曲線。實(shí)驗(yàn)表明：越靠近區(qū)域中心，節(jié)點(diǎn)分發(fā)補(bǔ)丁的速度越快。但此算法在區(qū)域邊緣(10,10)的位置仍能在36輪將補(bǔ)丁分發(fā)完畢，證明此算法選擇區(qū)域中任何節(jié)點(diǎn)作為初始節(jié)點(diǎn)分發(fā)安全補(bǔ)丁，最終均能快速將補(bǔ)丁分發(fā)完畢。

圖8 不同位置初始分發(fā)節(jié)點(diǎn)的M(t)曲線

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

本文提出了一種基于元胞自動(dòng)機(jī)的無(wú)線傳感器網(wǎng)絡(luò)安全補(bǔ)丁分發(fā)算法，克服了節(jié)點(diǎn)安全補(bǔ)丁難以分發(fā)的問(wèn)題。文中給出了改進(jìn)的二維元胞自動(dòng)機(jī)安全補(bǔ)丁分發(fā)模型以及分發(fā)算法的步驟，仿真說(shuō)明了該算法可以高效快速地將安全補(bǔ)丁分發(fā)完畢。