凌 春 孫文勝

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

0 引 言

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

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

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

1 網(wǎng)絡(luò)模型定義

為了對網(wǎng)絡(luò)覆蓋漏洞進(jìn)行更好地檢測和定位，首先介紹節(jié)點的初始條件和漏洞模型。

根據(jù)文獻(xiàn)[9]的描述，假定將m個傳感器節(jié)點隨機(jī)部署在特定區(qū)域內(nèi)進(jìn)行監(jiān)測，并且假定節(jié)點一旦放置就靜止不動。每個節(jié)點都有最大的監(jiān)測半徑Rs和最大通信半徑Rc，通常設(shè)置Rc=2Rs。鄰居節(jié)點表示以當(dāng)前節(jié)點為圓心，以Rc為半徑區(qū)域內(nèi)的傳感器節(jié)點。

網(wǎng)絡(luò)模型如圖1所示，且具有如下規(guī)定：

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

(2) 最小周期循環(huán)。環(huán)內(nèi)部不再包含任何循環(huán)。

(3) 覆蓋漏洞。網(wǎng)絡(luò)中的一片連續(xù)區(qū)域且不被任何節(jié)點的監(jiān)測范圍所覆蓋，圖1中的S1和S2即為網(wǎng)絡(luò)覆蓋漏洞。

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

(5) 標(biāo)簽特征。網(wǎng)絡(luò)中的每個節(jié)點新增一個初始值為1的標(biāo)簽特征，標(biāo)簽特征的值永遠(yuǎn)比當(dāng)前節(jié)點的漏洞弧段個數(shù)多1。即圖1中，Arc(ab)和Arc(cd)是節(jié)點n1的兩個漏洞弧段，對應(yīng)標(biāo)簽特征L1=3。

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

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

2 計算漏洞弧段

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

(1)

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

(2)

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

(3)

(4)

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

3 定位最小循環(huán)的蟻群算法

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

(1) 每個節(jié)點自動監(jiān)測鄰居節(jié)點的變化，確定漏洞弧段并計算對應(yīng)的標(biāo)簽特征值。

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

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

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

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

3.1 改進(jìn)概率公式

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

(5)

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

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

3.2 改進(jìn)加權(quán)因子

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

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

(6)

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

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

3.3 改進(jìn)信息素和路徑選擇

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

(7)

式中：S代表閾值常量，Q是信息素增量，ρ是信息素?fù)]發(fā)系數(shù)。因為螞蟻大概率的選擇具有較大標(biāo)簽值的節(jié)點，所以更容易尋找到最小周期的節(jié)點。

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

3.4 蟻群算法檢測漏洞的優(yōu)勢

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

4 螞蟻最大數(shù)量預(yù)估

不同的網(wǎng)絡(luò)覆蓋漏洞是由不同的最小循環(huán)周期構(gòu)成，在相同的蟻群數(shù)量條件下，漏洞周長越長，蟻群算法定位所消耗的時間就越久。為了適應(yīng)大小不同的漏洞，文獻(xiàn)[13]提出了泊松分布來建立模型：

(8)

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

(9)

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

(10)

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

Ni=mi×P(xi)

(11)

N=N1+N2+…+Nn

(12)

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

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

(13)

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

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

(14)

若用M=∑mi表示網(wǎng)絡(luò)S中所有節(jié)點的總個數(shù)，可推測出N≤M×θmax。因此為了快速定位網(wǎng)絡(luò)表面S中的漏洞位置，可以啟用最大數(shù)量的螞蟻個數(shù)等于區(qū)域內(nèi)的節(jié)點總個數(shù)與最大扇區(qū)角度的乘積。

5 實驗分析

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

表1 模擬參數(shù)設(shè)置

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

圖2 螞蟻數(shù)量和漏洞數(shù)量的效率比

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

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

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

6 結(jié) 語

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