一種基于元胞自動機的無線傳感器網絡安全補丁分發算法

李 林

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

0 引言

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

1 模型描述

本文采用正方形網絡作為無線傳感器網絡模型[5]，改進的二維元胞自動機動力學模型描述網絡中節點的狀態。

1.1 無線傳感器網絡模型

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

根據網絡中節點在網絡中的不同狀態，網絡模型根據節點的特性劃分為以下3種狀態，如表1所示。

表1 節點狀態參數表

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

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

CAS=(C，S，N，F)

(1)

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

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

(2)

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

(3)

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

(4)

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

(5)

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

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

在此模型中，只有屬于鄰域范圍內的節點才可以相互通信。

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

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

(6)

若節點在t-1時刻是正常節點狀態，狀態轉換函數為

(7)

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

(8)

若節點在t-1時刻是已感染狀態。狀態轉換函數為

(9)

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

(10)

若節點在t-1時刻已經處在免疫狀態,則狀態轉換函數為

(11)

節點維持此狀態不變，僅向外繼續分發安全補丁。

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

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

2.1 初始節點

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

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

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

2.2 病毒感染狀態節點

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

2.3 正常工作節點

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

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

(12)

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

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

3 仿真

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

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

圖3 初始參數下補丁分發演化特性曲線

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

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

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

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

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

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

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

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

4 結束語

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