李 林

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

0 引言

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

1 模型描述

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

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

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

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

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

1.2 改進的二維元胞自動機模型

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

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

(1)

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

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

(2)

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

(3)

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

(4)

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

(5)

圖1 元胞自動機摩爾型鄰域

圖2 改進型元胞自動機摩爾型鄰域

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

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

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

(6)

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

(7)

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

(8)

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

(9)

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

(10)

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

(11)

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

2 基于元胞自動機的安全補丁分發(fā)算法

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

2.1 初始節(jié)點

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

(2)處在免疫狀態(tài)的節(jié)點計算通過式(1)計算自己的狀態(tài)。

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

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

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

2.3 正常工作節(jié)點

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

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

(12)

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

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

3 仿真

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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