基于移動WSN 的分布式漏洞檢測與修復算法

尹 皓，王 軍

（1.蘇州科技大學 電子與信息工程學院，江蘇 蘇州 215009；2.中國科學院 長春光學精密機械與物理研究所，吉林 長春 130033）

0 引 言

無線傳感器網絡（Wireless Sensor Network, WSN）是由部署在目標區(qū)域的大量傳感器節(jié)點通過自組織的方式構成[1]。分布的節(jié)點能夠有效監(jiān)測周圍環(huán)境所發(fā)生的事件，并通過鄰居節(jié)點將收集到的數據匯總到用戶終端，以便進一步處理。但由于網絡內各節(jié)點能耗不均以及物理損壞等多種原因，導致某些節(jié)點意外死亡形成網絡監(jiān)測覆蓋漏洞[2]，因此對于傳感器網絡覆蓋漏洞的檢測與修復研究具有重要意義。

在移動WSN 中，本文設計一種分布式漏洞檢測與修復算法（Distributed Vulnerability Detection and Repair Algorithm, DVDR）。該算法使用網絡內已部署的移動節(jié)點來修復覆蓋漏洞。當網絡內任何一個節(jié)點檢測到與另一個節(jié)點通信中斷時，即可觸發(fā)漏洞檢測機制[3]，該機制通知故障附近節(jié)點收集關于漏洞的最新消息；之后每個節(jié)點轉發(fā)此信息，并根據自身可用能量和與鄰居距離獨立決定為漏洞恢復貢獻多少，同時保持現有的覆蓋和連通性[4]。仿真結果表明，DVDR 算法在覆蓋范圍、網絡能耗和連通性方面具有優(yōu)勢。

1 目標建模與假設

假設移動傳感器網絡區(qū)域為一個二維正方形區(qū)域，其中分布了n個移動節(jié)點用來監(jiān)測，部署時不存在獨立的節(jié)點或區(qū)域。將任意傳感器節(jié)點抽象為二維歐幾里得空間中的一個點，并且每個節(jié)點的感測范圍是以該點為中心的布爾圓盤來建模[5]。假設所有節(jié)點規(guī)格相同，其通信范圍是監(jiān)測范圍的2 倍，從而保證感知范圍重疊的任意2 個節(jié)點之間的連通性。

此外，每個節(jié)點都有一個唯一的標識號，監(jiān)測節(jié)點周期性地向各自鄰居發(fā)送感測數據，并將其匯總至網關節(jié)點。每個節(jié)點定期廣播心跳消息[6]，以證明其狀態(tài)正常。圖1 展示了每個節(jié)點及其標識號的初始部署，在通信范圍內的2 個節(jié)點由一條灰色虛線連接，代表其通信鏈路。

圖1 WSN 節(jié)點初始部署圖

假設所有節(jié)點都配備有GPS 定位模塊，知道自身所處位置，其中位置信息由笛卡爾坐標系中的xy坐標表示，鄰居節(jié)點位置是在部署后節(jié)點相互之間交換廣播信息后知曉，其中廣播信息包含節(jié)點ID 號、位置信息以及監(jiān)測數據等。

考慮到網絡內節(jié)點能量有限，必須盡量減少節(jié)點能耗，要做到這一點，算法還需協(xié)調好兩個主要的權衡問題：首先，算法必須最小化節(jié)點移動，并保證最大化覆蓋范圍；其次，必須盡量減少節(jié)點之間的通信，同時要保證節(jié)點移動過程中的合作。

2 分布式漏洞檢測與修復算法

2.1 DVDR 總體算法過程

DVDR 主要包括兩個階段：第一階段是漏洞檢測階段，鄰居檢測到一個死亡的節(jié)點，并估計其產生的漏洞大小和位置；第二階段是漏洞修復階段，所選節(jié)點計算恢復最大覆蓋所需的移動距離和方向，之后根據計算結果節(jié)點移動修復所檢測到的覆蓋漏洞。

假設某一節(jié)點已經故障死亡并導致了如圖2 所示的覆蓋漏洞，當任意節(jié)點出現故障時，其鄰居節(jié)點都會檢測到這個丟失的節(jié)點，這是由于該節(jié)點沒有在固定的周期內傳輸廣播信息；此后故障節(jié)點附近的鄰居節(jié)點會將自己標記為故障鄰居，并啟動覆蓋漏洞修復過程，在此期間這些故障鄰居們估計覆蓋漏洞的大小和位置，并計算自己與周圍鄰居的交點。對于覆蓋漏洞，本文只關注包圍漏洞未覆蓋的交點（Uncovered Intersection Point, UIP）。UIP 主要表示2 個節(jié)點感測范圍內的交叉點，同時不被任何其他節(jié)點的感測范圍覆蓋。

圖2 覆蓋漏洞示意圖

修復過程中，需要明確哪些節(jié)點應該參與修復，并對于選定的節(jié)點計算其新的位置，以便在保持連通性和最小化能量開銷的情況下同時修復覆蓋漏洞。

2.2 查找UIP 集合

在查找UIP 集合階段，所有的UIP 將被分成成對的點，稱為一個UIP 集合，同一個集合中的點屬于同一個覆蓋漏洞。假設各節(jié)點知道自己的位置和鄰居的位置，也知道自己與鄰居的感知范圍，則其能夠找到自己與鄰居的感知范圍交點。由于每個節(jié)點的感知半徑固定，因而可以很容易地計算節(jié)點感知范圍交集。

計算完所有交點后，將其標記為覆蓋或者未覆蓋交點。一個節(jié)點是否被覆蓋取決于該點是否位于已知鄰居節(jié)點的半徑內[7]，可以通過以下不等式來檢查：

式中：(xp,yp)是交叉點的二維坐標；(xc,yc)是當前被檢查的鄰居坐標；rs表示當前鄰居的感測范圍，即固定值，對于所有節(jié)點都相等。

UIP 正確配對圖如圖3 所示。將找到的所有UIP 交點分成唯一的對，其中每對只屬于一個覆蓋漏洞；再創(chuàng)建一組線段，將當前節(jié)點與其所有鄰居連接起來，即圖3 中的虛線部分；圖3 中實線表示連接一對UIP。為成對UIP 的每個組合創(chuàng)建單獨線段，當任意虛線與實線不相交時，則認為找到了UIP 的正確配對。

圖3 UIP 正確配對圖

圖4 展示出了會被算法拒絕的UIP 集合配對，線段相交表示分配給集合的交點不屬于同一個覆蓋漏洞。

圖4 UIP 錯誤配對圖

2.3 根據UIP 集合檢測漏洞

當故障節(jié)點的鄰居檢測到故障時，它們會觸發(fā)漏洞檢測過程的開始，并將這些節(jié)點標識為啟動節(jié)點。對于任意給定的節(jié)點，如果只找到一個UIP 集合，那么這個集合與漏洞相鄰；如果存在一組以上的UIP 集合，那么UIP 屬于兩個不同的漏洞，并且節(jié)點必須找出哪一組UIP 與最初檢測到的故障節(jié)點導致的漏洞相關。

如果當前節(jié)點是啟動節(jié)點，則UIP 集合即為包含故障節(jié)點半徑內的點集合；若故障節(jié)點半徑內沒有點，那么最靠近故障節(jié)點的點集合就是UIP 集合。一旦選擇了一組相關的UIP，該節(jié)點就會傳輸一個廣播信息包，其中包含它的ID、鄰居ID、它們各自坐標以及標識哪些節(jié)點參與了UIP 集合。為了保證漏洞附近的所有節(jié)點都能接收到該信息，采用的轉發(fā)方案[8]如下：如果接收該信息包的節(jié)點是啟動節(jié)點，那么它只轉發(fā)該消息；如果它為非啟動節(jié)點，那么這會作為其成為覆蓋漏洞鄰居節(jié)點的通知。之后非啟動節(jié)點計算自己的UIP 集合，并執(zhí)行相同的消息轉發(fā)，直到漏洞附近沒有新的非啟動節(jié)點為止。對于非啟動節(jié)點，其UIP 集合僅僅只是來自通知鄰居的點的集合。圖5 展示了覆蓋漏洞是如何被相關UIP 集合正確識別的。

圖5 UIP 集合識別覆蓋漏洞圖

2.4 尋找補洞候選節(jié)點

在移動WSN 中，默認覆蓋漏洞周圍的所有節(jié)點都是漏洞修復的候選對象，但是，對于其是否參與修復，必須滿足特定要求。最適合移動的節(jié)點是僅與當前覆蓋漏洞相鄰的節(jié)點，若這些節(jié)點相鄰了不止一個覆蓋漏洞，則必須驗證其是否被允許移動。

如果候選節(jié)點只是1 個漏洞的鄰居，那么其能夠移動；若候選節(jié)點是2 個漏洞的鄰居，應該計算它的覆蓋增益來決定其是否移動；若候選節(jié)點是2 個及以上漏洞的一部分，則其被禁止移動，這是由于通過移動修復1 個漏洞會加劇其他漏洞覆蓋范圍。

對于任何與2 個漏洞相鄰的節(jié)點，它將有2 組UIP集合，其中只有一個集合會被標記為與當前覆蓋漏洞相關。UIP 集是由2 個節(jié)點組成，這2 個點限定了相同的覆蓋范圍。如圖6 所示，DVDR 算法正在尋找候選節(jié)點修復H1漏洞，其中UIP 集{P1,P2}是相關集，屬于H1；而{P3,P4}是不相關集，屬于H2。

圖6 UIP 集之間距離比較圖

若非相關UIP 集距離d34小于相關UIP 集距離d12，這表明在相關漏洞H1的方向上移動會提供凈覆蓋增益；若d34小于閾值距離dth，則該節(jié)點允許移動。但需要注意，對于這類節(jié)點本質上總會遺漏另一個漏洞，但大多數時候，移動節(jié)點獲得的覆蓋率比失去的多，所以這是一種可以接受的權衡[9]，并且節(jié)點移動的距離不會超過其通信距離。因此，WSN 內不會中斷路由或連接。

2.5 節(jié)點移動距離與方向

當選擇一個節(jié)點進行漏洞修復時，節(jié)點需要知道它將移動的確切位置，可以通過計算移動距離和方向來完成。節(jié)點移動之前，首先找到當前節(jié)點被覆蓋的交叉點（Covered Intersection Point, CIP），CIP 是位于第3 個節(jié)點的感測范圍內的2 個節(jié)點的感知范圍的交叉點，因此當前節(jié)點必須找到包含在其自身半徑內的所有交點，這些點用來指示該節(jié)點可移動多遠，且不會影響覆蓋范圍和網絡連通性。

根據廣播信息包，每個節(jié)點都知道自己和鄰居的位置，因此，當前節(jié)點只需找到其鄰居之間的所有交點，然后使用2.2 節(jié)中不等式（1）檢查交點是否位于自己半徑內，并將位于半徑之外的交點丟棄，剩余的交點則為當前節(jié)點的CIP 交點。若當前節(jié)點半徑內沒有CIP 交點，則節(jié)點可能是孤立的，也可能與其鄰居感應半徑不重疊。這兩種情況都意味著當前節(jié)點的任何移動都會加劇現有的覆蓋漏洞。所以若未檢測到CIP 交點，則當前節(jié)點不能移動。在確定移動距離之前，需要知道移動的確切方向。

由于漏洞檢測階段已經完成，當前節(jié)點已知其哪個UIP 集是相關的，對于運動方向，首先需要計算連接相關集合的2 個UIP 的線段中點[10]，坐標標記為(xmid,ymid)；之后從當前節(jié)點的位置(xnode,ynode)開始，指向中點(xmid,ymid)的單位向量就是其方向向量，其計算公式如下所示：

通常vdir的方向就是節(jié)點修復漏洞應該移動的方向，但是若當前節(jié)點中心到2 個UIP 的角度大于180°，此時節(jié)點會向相反方向移動，遠離覆蓋漏洞，如圖7a）所示。為了糾正這種情形，使用線段交點來檢查這種情況，如果當前節(jié)點每個鄰居都用一條線段連接到它，這些線段中的任何一條與相交，則vdir必須取相反方向移動（即乘以-1）。正確移動方向vdir如圖7b）所示，其中不與鄰居連接到當前節(jié)點的任何線段相交。

圖7 方向向量正確與錯誤示意圖

最后計算當前節(jié)點的最大允許移動距離。計算每個CIP 到與vdir方向相反的節(jié)點邊緣的歐幾里得距離，并設定dmov為移動距離，其移動距離與方向偽代碼如下所示：

Input：相關UIP 集合，鄰居節(jié)點列表

Output：移動距離dmov，方向向量vdir

1. 計算CIP 交點

2. if（No of CIP < 1）then

3. returndmov=?

4. end if

5. 計算相關UIP 集的中點

6. 計算方向向量vdir

7. if（從相鄰節(jié)點到當前節(jié)點的任何線段與相關的UIP 線段相交）then

8.vdir=-vdir

9. end if

10. for 每個CIP do

2.6 對節(jié)點進行移動分級

若所有可能移動的候選節(jié)點都試圖修復漏洞，那么當每個節(jié)點都匯聚到覆蓋漏洞上時，它們的感知覆蓋面積肯定會有大量重疊，在增加網絡能耗的情形下，會降低網絡覆蓋率，因此需要限制節(jié)點移動，以降低能耗并提高覆蓋范圍。

本文設計一種節(jié)點移動分級系統(tǒng)，分級較高的節(jié)點移動最大距離，而分級較低的節(jié)點需要相應調整其移動距離。由于在2.3 節(jié)中設定覆蓋范圍內的所有節(jié)點之間共享了相關UIP 信息，因此進行分級計算的每個單獨節(jié)點值都相同，并且節(jié)點可以在不進行任何進一步溝通的情形下就分級排名達成共識。

DVDR 算法使用一個名為“合格性（eligibility）”的變量查看哪些節(jié)點在移動中具有最高優(yōu)先級。分級排名取決于兩個標準：估計移動距離和弧長。移動距離是指節(jié)點在不失去當前鄰居連接的情況下可以移動的距離；弧長是指節(jié)點的覆蓋周長中比鄰居當前覆蓋漏洞的部分，可以找到當前節(jié)點的相關UIP 集之間距離來估計它[11]。這兩個標準決定了一個節(jié)點通過移動可以獲得多少覆蓋率。

eligibility 的計算公式如下：

式中：larc為估計的弧長；dmov為標準化最大移動距離；α是調整系數，用來權衡哪個參數對優(yōu)先級影響更大，其值由文獻[10]參考得到。

當所有節(jié)點eligibility 都已計算完畢，它們將按降序排列。如果多個節(jié)點具有相同的eligibility，令具有最低標識號的節(jié)點具有更高優(yōu)先級，這是為了減少通信能耗，使得節(jié)點能夠快速進行移動修復。圖8 所示為節(jié)點通過eligibility 計算后如何進行漏洞修復的過程。

圖8 覆蓋漏洞修復后的WSN

3 仿真結果與性能分析

3.1 仿真實驗設置

在本節(jié)實驗中，使用Matlab 仿真軟件對提出的DVDR 算法進行驗證，并將其與最遠鄰居干預算法（Farthest Neighbor Intervention Algorithm, FNIA）和中心簡單移動算法（Center Simple Moving Algorithm, CSMA）這兩種經典算法進行比較。

在網絡內部署90 個可移動傳感器節(jié)點，每個節(jié)點最大感知半徑為15 m，最大通信半徑為30 m，令所有傳感器節(jié)點以分布式方式隨機分布在一個300 m×300 m的二維區(qū)域內，并設置以下指標類衡量算法性能：

1）覆蓋率：由一個或多個傳感器節(jié)點監(jiān)測的傳感器網絡覆蓋比例。

2）節(jié)點移動次數：響應檢測到覆蓋漏洞后的節(jié)點移動次數。

3）移動距離：對覆蓋漏洞做出響應的所有節(jié)點移動總距離。

4）累計能耗：節(jié)點移動與通信消耗的總能量。

5）分區(qū)數量：分區(qū)是一組相互連接但與網絡其余部分隔離的節(jié)點，大規(guī)模節(jié)點故障后，分區(qū)是不可避免的。

6）隔離節(jié)點數量：隔離節(jié)點是分區(qū)的一種特殊情況，整個分區(qū)由一個節(jié)點組成。不能通信的孤立節(jié)點對網絡沒有作用。

3.2 覆蓋率分析

為了驗證在多個節(jié)點發(fā)生故障后，不同算法對于覆蓋率的修復情況，本文比較了三種算法在網絡覆蓋率修復方面的性能，并且為了突出覆蓋算法的優(yōu)勢，在其中加入了不使用修復算法的覆蓋率變化曲線。其覆蓋率變化曲線如圖9 所示。

圖9 多種算法覆蓋率比較結果

由圖9 可知，所有算法開始都是在100%覆蓋率的網絡中運行，隨著故障節(jié)點個數增加，沒有使用覆蓋漏洞修復算法的網絡監(jiān)測覆蓋迅速惡化，而其他三種算法開始時性能較為相似。但是，CSMA 算法需要密集部署，隨著節(jié)點故障數增多，其覆蓋率修復性能快速下降，事實上，當剩余節(jié)點很少時，CSMA 算法的修復嘗試會變得有害，其性能甚至比沒有修復算法的網絡還要糟糕。DVDR 算法和FNIA 算法性能較為相似，本文算法在覆蓋漏洞檢測與計算方面更為精確，所以算法在覆蓋率修復表現上更為突出。

3.3 網絡能耗分析

圖10 所示為DVDR、FNIA 和CSMA 這三種算法在節(jié)點數量一定時WSN 內能量消耗情況，其中橫軸代表故障節(jié)點數，縱軸為網絡內節(jié)點累計能量消耗。

圖10 移動過程中消耗的總能量

圖10 中，CSMA 算法使用虛擬的方向來確定節(jié)點應該移動到的位置，但其沒有考慮節(jié)點能耗，以致于CSMA 中所有節(jié)點都被吸引至覆蓋漏洞附近，若漏洞較大，其會消耗很多能量。如圖10 中所示，當多個節(jié)點發(fā)生故障時，CSMA 能量累計消耗最大。

FNIA 算法在選擇節(jié)點移動時會考慮其能量影響，它總是選擇那些具有較高能量儲備的節(jié)點。但是由于其只使用一個替換節(jié)點來修復覆蓋漏洞，所以該替換節(jié)點必須移動較遠距離；隨著故障節(jié)點增多，FNIA 算法會發(fā)生每個替換節(jié)點的移動，從而留下另一個覆蓋漏洞。這種級聯(lián)方式選擇替換節(jié)點的措施，故障節(jié)點越多其能耗越高。本文DVDR 算法只允許故障節(jié)點鄰居作為替換節(jié)點，這就極大地限制了替換節(jié)點移動距離引起的節(jié)點能耗，并且這種決策也并不影響網絡覆蓋漏洞修復性能。

3.4 連通性分析

在三種覆蓋漏洞修復算法中，DVDR 保持了最穩(wěn)定的連通性能，因為它確保了任何移動節(jié)點都不會出現中斷通信連接的狀況；而FNIA 和CSMA 算法并未考慮連通性因素。

圖11 所示為三種算法的連通性比較結果。從圖11可以看出，在20 個節(jié)點故障之后，CSMA 算法的連接數急劇增加。從圖9 中可以看到，其覆蓋范圍同時快速減少，這是由于當可用節(jié)點數減少時，其覆蓋漏洞變得極大，幸存節(jié)點無法處理；加上沒有檢測機制，漏洞吸引力導致節(jié)點聚集在漏洞中心，從而增加了連通性并減少了覆蓋。

圖11 算法連通性比較結果

如圖11 所示，FNIA 算法注重最大化覆蓋范圍，但其沒有考慮節(jié)點連通性因素。若允許節(jié)點獲得更大覆蓋范圍，它們可能中斷現有的連接，這也是FNIA 算法的連通性比無修復算法更差的原因。另一方面，DVDR 算法在最大化覆蓋范圍的基礎上加入了節(jié)點連通性因素，不允許其中斷現有連接，因此它在這兩種權衡之間最為合適。

4 結 語

本文針對移動無線傳感器網絡覆蓋漏洞邊界搜尋不準確、漏洞修復能耗過高的問題，提出一種低能耗和高覆蓋率的分布式漏洞檢測與修復算法。該算法只需要距離漏洞一跳的鄰居節(jié)點來進行檢測與修復工作，進而恢復網絡覆蓋范圍與連通性，這使得其可以應用在大型網絡。仿真實驗中，將本文算法與FNIA 和CSMA 算法進行比較，在給定相同部署與相同故障節(jié)點數量下，DVDR 算法在網絡覆蓋率、累計能耗和節(jié)點連通性等方面具有顯著提高。

在后續(xù)研究中，算法會在更貼近實際情況的三維空間中進行實驗驗證，并且考慮監(jiān)測區(qū)域內外界噪聲以及通信延時等因素對實際漏洞修復的影響，以達到更適用的覆蓋漏洞修復效果。