基于蟻群的無線傳感器網絡漏洞檢測技術研究

凌 春 孫文勝

(杭州電子科技大學通信工程學院 浙江 杭州 310018)

0 引 言

在過去的幾年，無線傳感器作為一個熱門話題被廣泛應用于各種領域，例如邊界檢測、環境檢測[1]和健康監控[2]等。大多數應用都需要網絡的完全覆蓋和持續連接，但傳感器是隨機投放并散列分布在網絡中，這種隨機部署[3]的傳感器覆蓋范圍有限，容易出現漏洞。除此之外，網絡節點是依賴電池供電且不可再生，能量消耗過快也會導致漏洞的出現。為了解決網絡漏洞問題，就要設計一種在網絡覆蓋范圍內能夠快速地檢測和定位漏洞的技術，這種設計可以通過識別漏洞邊界處的節點來實現。

文獻[4]提出了一種基于Voronoi圖的覆蓋漏洞邊界檢測算法，起始階段建立無線傳感器網絡的Voronoi圖，通過比較節點的監測范圍以及當前節點到Voronoi圖中頂點的長度來識別當前節點是否在網絡漏洞邊界上。文獻[5]提出了一種基于幾何計算的分布式算法，利用當前節點與相鄰的兩個鄰居節點之間形成的幾何三角和外接圓圓心的位置關系來判斷當前節點是否在漏洞邊界上，該算法計算復雜度較低，但限制了節點的監測范圍和通信距離，適用范圍較小。文獻[6]提出了一種基于圓搜索的分布式覆蓋漏洞檢測算法，該算法根據圓周覆蓋和鄰居節點的信息建立了一張關系表，用于記錄當前節點和鄰居節點之間的距離和象限信息。通過查詢關系表來定位網絡漏洞所在的位置。該算法僅需要查詢關系表即可獲得漏洞信息，減少了節點之間的通信次數，但由于需要記錄每個節點上的參數和圓弧信息，當節點個數較多時，執行時間較長效率低下。

為了解決現有的網絡漏洞定位技術的局限性，提出了基于蟻群算法[7]的漏洞檢測技術。蟻群的尋路特性能夠有效解決傳感器節點部署和路由優化的許多效率問題，能夠及時準確地識別漏洞邊界的節點。根據螞蟻的動態特性，從兩方面對傳統方法進行了優化：一方面是采用分布式技術[8]，節點之間只需少量數據通信；另一方面是蟻群算法會自動調整螞蟻的數量來檢測不同大小的漏洞。

1 網絡模型定義

為了對網絡覆蓋漏洞進行更好地檢測和定位，首先介紹節點的初始條件和漏洞模型。

根據文獻[9]的描述，假定將m個傳感器節點隨機部署在特定區域內進行監測，并且假定節點一旦放置就靜止不動。每個節點都有最大的監測半徑Rs和最大通信半徑Rc，通常設置Rc=2Rs。鄰居節點表示以當前節點為圓心，以Rc為半徑區域內的傳感器節點。

網絡模型如圖1所示，且具有如下規定：

(1) 漏洞的循環周期。由不重復的節點集合組{ni|i∈[1,m]}組成，其中ni+1是ni的鄰居節點，nm是n1的鄰居節點，且滿足i≠j，ni≠nj。

(2) 最小周期循環。環內部不再包含任何循環。

(3) 覆蓋漏洞。網絡中的一片連續區域且不被任何節點的監測范圍所覆蓋，圖1中的S1和S2即為網絡覆蓋漏洞。

(4) 漏洞弧段。節點S的監測范圍邊緣未被鄰居節點Sk(Sk∈S(Rs))所覆蓋的邊緣弧段。如圖1所示，節點n1的漏洞弧段為Arc(ab)和Arc(cd)(Arc表示弧段)。

(5) 標簽特征。網絡中的每個節點新增一個初始值為1的標簽特征，標簽特征的值永遠比當前節點的漏洞弧段個數多1。即圖1中，Arc(ab)和Arc(cd)是節點n1的兩個漏洞弧段，對應標簽特征L1=3。

圖1 覆蓋漏洞和漏洞弧段圖

為了檢測覆蓋漏洞所在的位置，應該先確認最小周期，并且最小周期必須是由節點的漏洞弧段組成。證明：假設最小循環周期至少包含一個非漏洞弧段Arc(ab)，這意味著節點n1在節點n6和n2之間還存在一個鄰居節點n′。該現象將會產生兩種情況：第一種，節點n6和n2其中一個或者兩個都是n′的鄰居節點，這意味著循環(n1,n2,…,n6)中存在另一個循環，這與規定(2)不符；第二種，節點n′僅是節點n1的鄰居節點，那么節點n1在循環順序中將出現兩次，這與規定(1)不符，也不組成最小循環周期。根據上述的兩種情況可知，漏洞弧段可用于識別拓撲中最小的周期，檢測覆蓋漏洞。

2 計算漏洞弧段

引用文獻[10]中的幾何計算漏洞弧段。假定節點ni是nj的鄰居節點，ni和nj的坐標分別是(xi，yi)，(xj，yj)，ni到nj的直線距離是dij，則相對于節點ni節點nj的方向角αij如式(1)所示:

(1)

節點i被j覆蓋的弧段所對應的方向角度如式(2)所示:

(2)

式(2)中θij對應的弧段點(xk,yk)和(xk+1,yk+1)如式(3)和式(4)所示：

(3)

(4)

節點i根據上述公式獲取所有鄰居節點的覆蓋方向角的集合A={θij|j∈Vi}，集合A中的補集所對應的弧段即為尋找的漏洞弧段。

3 定位最小循環的蟻群算法

蟻群算法模擬螞蟻在真實環境中的覓食特征[11]，以分布式的方式直接或間接地進行信息交互。改進的設計主要是利用漏洞弧段信息來引導螞蟻的搜尋方向，從而定位出覆蓋漏洞的位置。具體設計思路如下:

(1) 每個節點自動監測鄰居節點的變化，確定漏洞弧段并計算對應的標簽特征值。

(2) 螞蟻由標簽值L>1的節點啟動以檢測最小周期。

(3) 螞蟻根據當前節點的標簽、節點上的信息素濃度和鄰居節點的距離來選擇下一跳節點，并對訪問過的節點釋放信息素。

(4) 尋找到的最小周期通常是信息素濃度較高的節點形成的環。

根據上述設計的思路，覆蓋漏洞的監測由傳感器自行啟動。當傳感器節點的鄰居信息變化時，每個節點根據漏洞弧段計算標簽特征值L。當標簽值L>1時，即該節點至少在一個漏洞的邊界上，就啟動一組螞蟻，這些螞蟻將從該節點出發進行巡視，直到返回該節點。

3.1 改進概率公式

蟻群算法搜尋過程是根據概率公式來選取下一跳節點，為了讓蟻群算法適用于漏洞定位。將概率公式[12]加以改進，如式(5)所示。

(5)

式中：τij是邊界(i,j)的信息素濃度，Lj是節點j標簽值，dij表示當前結點i到j的直線距離長度，α、γ和β分別是信息素、標簽值和兩節點直線距離的加權因子。Vi是節點i中未被螞蟻訪問過的鄰居節點的集合。

螞蟻根據鄰居節點的標簽值會優先選取最小循環周期上的節點，這意味著標簽值越大時，螞蟻選取該節點的可能性就越大。此外，當一個節點存在多個互不相交的漏洞弧段時，則可知道該節點是多個不同方向循環周期的公共節點。由于單位時間內螞蟻釋放的信息素量固定不變，經過多次迭代，大多數螞蟻都會選擇最小循環周期上的節點，因此最小周期上的節點的信息素濃度相對較高。

3.2 改進加權因子

信息素加權因子只影響算法收斂速度并不會改變最終結果值，為了增加初始階段算法的收斂速度，我們將α改進成式(6)所示。

α(t)=λ1(1+e-λ2t) 0≤t≤T

(6)

式中：參數λ1和λ2是常量，且λ1，λ2∈(0,1]，t表示搜尋時間，T表示最大搜尋時間。

式(6)表示在算法的初始階段，加權因子α的值較高，節點信息素的增量較大，算法收斂速度較快；隨著時間的推移，加權因子逐漸變小，算法的收斂速度也逐漸降低。

3.3 改進信息素和路徑選擇

為了避免螞蟻在尋路過程中陷入局部最優解，改進信息素的更新策略使其更符合覆蓋漏洞的定位。我們設置閾值限制信息素釋放量，同時固定單位時間內信息素的增量，具體如式(7)所示。

(7)

式中：S代表閾值常量，Q是信息素增量，ρ是信息素揮發系數。因為螞蟻大概率的選擇具有較大標簽值的節點，所以更容易尋找到最小周期的節點。

定位覆蓋漏洞過程中，螞蟻k自身維護一張列表Ak記錄訪問過的節點和對應的信息素量。等到所有螞蟻執行完畢之后，尋找信息素總量最多的Ak所形成的環就是最小周期環。

3.4 蟻群算法檢測漏洞的優勢

該算法擁有許多優點：(1) 因為算法是分布式算法，不需要在節點之間共享信息，所以不會因為交換開銷而過載。(2) 只要螞蟻進入網絡中，無論漏洞大小都會快速檢測所有的漏洞。(3) 它比現有方法更靈活，因為在發現最小周期過程中，蟻群算法是根據鄰居節點的信息素濃度、距離和標簽值來選擇下一跳節點。(4) 螞蟻的最大數量和迭代次數是不固定的，這使得算法在應用時更具靈活性。但是，可以通過模型估算出應該啟動的最大螞蟻數量來提高執行效率，具體在下一節描述。

4 螞蟻最大數量預估

不同的網絡覆蓋漏洞是由不同的最小循環周期構成，在相同的蟻群數量條件下，漏洞周長越長，蟻群算法定位所消耗的時間就越久。為了適應大小不同的漏洞，文獻[13]提出了泊松分布來建立模型：

(8)

式中：λ>0，X是服從參數為λ的泊松分布，記作X～P(λ)。根據式(8)，假設漏洞出現在網絡表面S中。其中S可以被分成n個不相交的扇區S(θi)，且滿足i∈{1,2,…，n}，θ1+θ2+…+θn=360°。根據式(8)設計漏洞出現在扇區S(θi)上的概率：

(9)

對式(9)進行積分，求出在θi和θi+1之間的漏洞出現的概率：

(10)

根據式(10)，我們首先查詢在扇區S(θi)中存在的節點個數mi，然后由式(11)和(12)分別得到預估扇形S(θi)區域內需要的螞蟻數量Ni和螞蟻的總數量N。

Ni=mi×P(xi)

(11)

N=N1+N2+…+Nn

(12)

若假設θi+1-θi≤θmax，那么根據式(11)和式(12)可以推測出螞蟻最大數量不等式：

N≤∑P(xi)·mi·θmax

(13)

又因為P(Xi)≤1恒成立，則式(13)可以變成如下不等式：

N≤∑mi·θmax=θmax∑mi

(14)

若用M=∑mi表示網絡S中所有節點的總個數，可推測出N≤M×θmax。因此為了快速定位網絡表面S中的漏洞位置，可以啟用最大數量的螞蟻個數等于區域內的節點總個數與最大扇區角度的乘積。

5 實驗分析

仿真環境采用MATLAB軟件模擬評估所提出算法的性能。模擬參數如表1所示，將200個初始條件都相同的節點放置在100×200 m的網絡范圍內，每個節點的通信范圍Rc=20 m。為了評估提出的算法,人為地在網絡區域內部均勻分布覆蓋漏洞，記錄創建的漏洞的邊界節點位置。設置信息素增量Q=2，權重因子β和γ為常量0.2，閾值S=88，揮發系數ρ=0.5、λ1=1、λ2=0.2。

表1 模擬參數設置

圖2顯示了迭代次數為10，不同螞蟻數量和不同數量的覆蓋漏洞檢測效率百分比關系圖?？v坐標表示定位到的漏洞邊界節點數量占總漏洞邊界節點數量的比例。這個比例實際上是用來判斷漏洞檢測效率高低。圖2利用漏洞總個數分別為4、6、8和10的數量做比較，可以發現當網絡中存在6個漏洞且螞蟻的起始數量為20只的時候，效率卻只有33.3%。但隨著螞蟻數量的增加，效率逐漸提高，直到螞蟻數量達到55只時，效率達到了100%。事實上，當節點發送的螞蟻數量越多時，網絡節點被訪問的數量就越多，這樣就會發現更多的邊界節點并標記信息素。此外，從圖中可知，當螞蟻數量相同時，漏洞數量越少，檢測效率就越高。例如，只需要50只螞蟻就可以在總漏洞數為4的網絡中達到100%的效率。而對于漏洞總數為10的網絡卻需要近90只螞蟻才可以達到100%的定位效率。上述現象可知，網絡中的漏洞總數越多，則需要更多的螞蟻來有效發現邊界節點的數量。

圖2 螞蟻數量和漏洞數量的效率比

圖3表示在螞蟻數量相同的情況下，不同漏洞數量的迭代次數和檢測效率關系圖。迭代指的是每個漏洞弧段節點重新啟動一組螞蟻執行所提出算法的次數。如圖所示，隨著迭代次數逐漸增加，漏洞邊界上節點被檢測數量也隨之增加，檢測效率也隨之增加。但當螞蟻數量一樣時，網絡范圍內的漏洞數量越少，探測效率越高。這是因為當螞蟻數量相同時，網絡中的漏洞數量越多，則檢測所有漏洞所需的時間就越長，所以效率也就越低。

圖4表示在漏洞總個數為6和迭代次數為10的情況下，不同數量的螞蟻和不同大小的漏洞與檢測效率的關系。如圖所示，檢測效率隨著螞蟻數量的增加而增加，當邊界節點個數為4時，只需要25只螞蟻即可定位到所有漏洞，當漏洞邊界節點個數為12時，需要60只螞蟻才可以精確定位所有漏洞。由此可知，在相同的時間內，漏洞邊界上的節點個數越多，則需要更多的螞蟻來完成檢測。

圖4 螞蟻數量和漏洞邊界長度的效率比

6 結 語

本文采用通信方式，結合蟻群優化技術，針對無線傳感器網絡覆蓋漏洞的問題做了一些研究：(1) 引入標簽特征記錄未被鄰居節點覆蓋的弧段數量；(2) 節點通過判斷標簽特征自發啟動一組螞蟻；(3) 利用螞蟻的尋路特性獲取漏洞邊界的節點信息；(4) 利用泊松分布預估最大蟻群數量。實驗結果證明：提出的算法能夠以較低的復雜度高效精準地實現覆蓋漏洞的定位。對于未來工作，可以利用本文設計的方法來開發解決無線傳感器網絡覆蓋漏洞的問題。