一種基于廣度優先生成樹的無線傳感器網絡自保護算法

張文哲 李 鎣廣東工業大學

一種基于廣度優先生成樹的無線傳感器網絡自保護算法

張文哲 李 鎣
廣東工業大學

從無線傳感器網絡中選取部分節點作為保護節點，為網絡提供保護稱為無線傳感器網絡的自保護。前人已經證明自保護問題是 NP- 完全問題。提出一種基于廣度優先生成樹的自保護算法，可以高效地分布式地選擇保護節點。我們首先為自保護問題建模，其次提出了分布式的標記過程，不同于前人工作的是，在保持較小保護節點集合的基礎上，我們還保持了保護節點的連通性，使得緊急消息到網關的平均匯報跳數最少，這一特點使得本文算法更加合理可行，從而提高了區域監控應用中傳感器網絡性能。仿真實驗證明，本文算法可行性和有效性。

無線傳感器 自保護算法

1 無線傳感器網絡的自保護

1.1 傳感器網絡的輻射與暴露

在區域監控應用中，無線傳感器網絡通常被用來監測入侵區域的任何目標 Target，這些目標通常都是智能的，例如戰場上的敵人、商店的小偷以及公共安全場所的恐怖分子等。目標不僅會發現布置的傳感器節點繞道入侵，而且會敵意破壞這些節點使之服務失效 Denial of Service。由此可見，我們有必要隱藏無線傳感器網絡的節點，使其能夠在敵對的環境下繼續工作，增強傳感器網絡的魯棒性。

傳感器節點被目標發現，通常由于兩種情形：一是節點體積形態龐大而被人看見；二是由于節點通信時形成的電磁場暴露。隨著電子技術的高速發展和元器件微型化，有更多的微型傳感器節點面世，如美國加州大學Berkeley 分校的 Smart-Dust 項目，正是致力于能夠懸浮在空氣中的傳感器節點制造。此外，形態偽裝同樣可以減少被目標通過視覺發現的可能性。因此，節點的微型化并不是難點，電磁場暴露才是傳感器節點被發現的主要原因。

針對電磁場暴露，我們重新考慮傳感器節點的組成與結構，傳感器節點上能夠產生較大電磁場暴露的元器件，通常有兩個重要的組成部分：感知單元和通信單元。傳感器節點的感知方式有很多種，由于感知原理的不同，各種感知單元形成的電磁場強度各不相同。通常由于輻射強度與節點能耗成正比，節點在通信過程中的能耗是感知過程的十幾倍，因此通信時的電磁場暴露是傳感器節點暴露的關鍵因素。

一種簡單而有效的減少節點暴露的方法是減少傳感器網絡的通信量，本文中稱之為隱藏技術。這就為面向區域監控的傳感器網絡設計提出了新的輻射要求：在維持傳感器網絡正常功能的前提下，減少節點發送的消息數量，使更多的節點保持休眠，避免暴露。此外，休眠節點依然面臨著危險，具有較強的脆弱性，容易遭受攻擊。在區域監控應用中，隱藏技術不僅能夠減少電磁暴露，使節點不被發現而免受破壞，增強了網絡的可靠性；而且能使智能目標誤闖被監控區域，大大增加了傳感器網絡監測目標的機率。

此外還需要保護傳感器節點，實時監控節點的狀態。一旦有節點被破壞，其保護節點即刻發送緊急消息 “SOS” 至網關匯報情況。這一技術稱之為自保護（Self-protection），也即由傳感器節點自己保護自己。自保護的實現是選擇部分節點承擔保護任務，實時監督其他節點的狀態。一旦有節點被毀或者失效，網關能夠收到緊急消息并采取進一步措施。由于電池供電，傳感器節點常常由于電能耗盡而失效，可見自保護技術是傳感器網絡健康狀態自我監視的好方法，在區域監控應用中同樣具有重要的研究意義。

1.2 問題的提出

減少通信量可以降低傳感器節點的電磁場暴露。根據傳感器網絡的輻射要求，把傳感器節點分為兩類：隱藏節點和保護節點。僅感知少通信的節點稱為隱藏節點，而既感知又通信的節點成為保護節點，承擔保護任務，監視隱藏節點的狀態。

那么傳感器網絡中，選擇哪些節點為隱藏節點，哪些節點又為保護節點呢？ 這是需要重點解決的問題。此外，在區域監控應用中，我們還發現隱藏節點的選擇過程具有以下特點：

1） 布置在監控區域邊緣的節點最容易暴露、被破壞，因此最需要被保護；

2） 隱藏節點的數量越多越好，但是所有隱藏節點都需要被保護。通常地，假設節點一跳可保護，即保護節點可以定期詢問隱藏節點是否安好；

3） 保護節點必須連通至網關，而且向網關匯報的緊急消息平均跳數最少。

基于上述分析，我們提出的問題是，從所有節點集合V中，找出最小連通子集V*，使得任意節點要么屬于V*，要么在V*節點的一跳范圍內。如此所得的V*節點是保護節點集合，承擔保護任務，實時監督其他節點的狀態，不可以休眠；V -V*是被保護節點，可以休眠以減少電磁場暴露。

由此可見，傳感器網絡的隱藏問題可以歸納為這樣的數學問題：求任意連通圖的最小連通支配集（Minimum Connect-ed Dominating Set，MCDS）。關于最小連通支配集問題，有人已經證明是 NP完全問題，前人已有出色的研究工作如下。

1.3 研究現狀

無線傳感器網絡的自保護問題已經有很多文獻闡述了細致的工作。D。Wang在文獻中首次提出了無線傳感器網絡的自保護（Self-protection）問題，并給出了正式的定義：一個無線傳感器網絡被p-自保護，當且僅當任何時刻任何傳感器節點至少被p個活躍的節點監視到。文章證明了自保護問題是 NP完全問題，并給出了兩種求解方法：集中式的pIA（Pre-Scheduled Independent Activation）和 分 布 式 的 NC（Neighbour-hoodCooperative self-protection）。在pIA 算法中，每個傳感器節點需要預先設定一個計時器和概率 δ。當計時器過期時，節點以概率δ激活自己并重置計時器。計時器需要時間同步，概率δ則必須在布置傳感器節點之前，根據傳感器節點的密度而設定。由于絕大多數情況下傳感器節點都是隨機布置的，所以算法中這些設置和要求是不現實的。在 NC 算法中，節點無需密度信息即可協同地提供保護。但僅關注于自保護問題，不易于擴展到解決p-自保護問題的情形（p≥2），且沒有深入研究節點靜默和緊急消息的匯報要求。

修訂了無線傳感器網絡的p-自保護（k-selfpro-tection）問題的定義，針對p-自保護問題，給出了一種局部最優的集中式算法，并對稠密網絡可以生成多個保護集以輪流工作。集中式算法的基本思想是生成p個最大獨立集 MIS，這些 MIS 提供網絡的保護，每個 MIS 能夠單獨地保護網絡節點，這p個 MIS即可提供p保護。文章將p-自保護問題歸納為最小連通支配集MCDS 問題，然后給出了一種分布式近似算法。分布式算法是集中式算法的擴展，傳感器節點根據自己和鄰居的信息決定自己的狀態。同樣，沒有研究節點隱藏時的靜默要求。針對提出的自保護問題求解方法給出了一個反例，證明的方法并不能適應于任何網絡拓撲，在此基礎上給出了一種分布式的自保護問題求解方法，并證明能夠獲得常數近似比。傳感器網絡中p-自保護問題，給出了一種局部最優的自保護集合生成算法，并能適應p＞=2 的情形，但該方法所得的集合僅僅是局部最優，未必是全局最優解。

2 自保護模型與網絡建模

2.1 k-跳可保護與p-自保護

在無線傳感器網絡中，自保護指的是由傳感器節點之間相互保護，怎樣選擇保護節點集合承擔保護任務成為問題的關鍵。

保護措施可以通過多跳通信的方式來實現，所以可以通過通信的跳數（hops）來衡量保護的種類。如果認為傳感器節點可以通過 k 跳通信的方式保護其他節點，則稱之為 k-跳可保護。通常假設，傳感器節點是 1-跳可保護的，即傳感器節點可以通過 1 跳通信方式監視鄰居的狀態是否完好。

此外，自保護問題還可以通過保護節點的數量來衡量。p-自保護被定義為，在任何時刻，傳感器節點至少被p個其他傳感器節點所監視。如果p取值為1，則認為任何時刻傳感器節點至少被1個其它節點所保護，也即1-自保護。在本文中，為了簡化問題，更好地致力于求解傳感器網絡的隱藏方法，我們假設節點之間均是1-跳可保護的，而且算法目的只要求1-自保護。

此外，我們認為任何傳感器節點都需要被保護，包括保護節點自身。但由于問題的特點是所有保護節點均連通至網關，則任何保護節點均可與其它保護節點 1-跳通信，也即任何保護節點均可以被保護。基于以上分析可見，傳感器網絡隱藏問題就可以簡化為求解隱藏節點被 1-跳可保護與 1-自保護的問題。

2.2 網絡建模

由于傳感器網絡離散分布的特性，節點的幾何布置狀況有多種布置方法，有如確定性布置和隨機布置。確定性節點布置是傳感器網絡的簡易布置方法，研究內容較少。本文中我們重點考慮隨機布置的情況。假設節點的初始位置均一并相互獨立地分布在監控區域內，且構成一個連通的無向圖。為了更好地描述本文算法，首先給出如下有關基本概念。

定義1。設圖G=（V，E），稱G為簡單連通無向圖，當且僅當圖G滿足以下兩個條件：①G為無自圈的、連通的無向圖；②G中任意兩個節點之間最多有一條邊。定義2。若p、q 為圖G=（V，E）中的任意兩個節點，即p、q∈V，若存在G中的一條邊連接節點p、q，則稱節點p和節點 q 相鄰 Neighbor。

定義3。圖G的節點集SV為支配集，當且僅當節點集S 滿足以下條件：/p∈V 則p∈S 或p為S中的某個節點的鄰節點。S 中的節點稱為支配點（Dominator），圖G中不屬于S 的節點稱為被支配點（Dominatee）。

定義4。給定一個圖G=（V，E），圖G的節點集SV為滿足如下條件的節點集合：由S導出的子圖是連通圖，且S是圖G的一個支配集；則稱S為連通支配集。若S為滿足上述條件的最小節點集合，則稱為最小連通支配集，記為 MCDS（G）。

定義5。若p為圖G=（V，E）中的任意節點，即p∈V，稱p在圖G中的相鄰節點的個數為p的度數，記為 D（p）。

定義6。若圖G=（V，E）的生成子圖T是一棵樹，則稱該樹T為G的生成樹（Spanning Tree）。

定義7。在圖G的所有生成樹中，從樹根開始的廣度優先遍歷得到的生成樹，稱為G的廣度優先生成樹（Breadth-FirstSpanning Tree，BFS）。

定義 8。在圖G=（V，E）的生成子圖T是一棵廣度優先生成樹，一個節點子樹的根節點稱為孩子節點，含有相同孩子節點的節點稱為父節點，具有相同父節點的節點稱為兄弟節點。

3 基于BFS 的自保護算法

3.1 前提假設

隨機布置的傳感器網絡構成一個簡單無向圖，為了研究問題的方便，我們如下假設：

1）網絡拓撲是連通的。因為對于不連通的傳感器網絡來說，節點的感知信息不能夠傳回至網關，必然是失效的節點，更多的隱藏與保護措施也無意義；

2）每個節點標識了各自唯一的 ID，并通過 1 跳通信獲知其鄰居信息。每個節點維護自己的鄰居節點信息表，包括節點ID 號、層次和狀態信息；

3）網絡中節點可以分層，用層數表示：0，1，2…，網關層數為 0，以此類推。

基于以上假設，我們就可以構建隱藏算法。

3.2 節點狀態與分類

根據節點的工作模式，傳感器節點分為兩種類型：隱藏節點和保護節點。本文將節點狀態相應地定義為被支配狀態和支配狀態。

保護節點處于支配狀態，為其他節點提供保護；處于被支配狀態的節點是隱藏節點，被支配節點保護。考慮到網絡的初始狀態，沒有生成任何保護節點和隱藏節點，所有節點都處于初始狀態，因此，傳感器節點有三種狀態，分別是初始狀態、被支配狀態和支配狀態，處于以上狀態的節點分別定義為初始節點primal、被支配節點 dominatee 和支配節點dominator。

3.3 消息設計

為了實現分布式隱藏節點選擇算法，各節點需要溝通各自的狀態并協商。為此，我們設計了專門的消息，用于通告各自的狀態。這一消息在 1-跳范圍內獲知，即消息接受者只接收，不轉發。如此設計，大大降低了消息廣播的數量，而且有效防止了消息洪泛的現象。

我們設計了兩種消息：1。分層消息 Layer Message用于通告自己的節點層次，消息結構定義為 Layer（n，i）：表示節點n 處于第 i 層；2。狀態消息 State Message用于通告自己的節點狀態，有三種：Dominating（n）：表示節點 n 處于支配狀態，為支配節點；Dominated（n）：表示節點 n 處于已被支配狀態，為已被支配節點；Undominated（n）：表示節點 n 處于未被支配狀態，為未被支配節點。

3.4 節點狀態轉換策略

節點的狀態有三種，處于不同狀態節點也有三種，分別是初始節點、被支配節點、和支配節點。每當收到不同的消息，節點狀態都要做出相應的變化。初始狀態的節點收到任何消息都將轉換為被支配狀態，被支配狀態的節點收到被支配請求后，轉換為支配狀態；當支配狀態的節點得知被支配節點包圍時，轉換為被支配節點。

節點在狀態轉換的過程中，還需要把這一狀態變化通告周圍鄰居。因此需要發送自己狀態消息。對于處于不同狀態的節點，每當收到不同的消息，都將自己標記為其他的狀態，同時發送新的消息表明自己的狀態。

3.5 基于 BFS 的 MCDS 問題求解

3.5.1 BFS 樹構造階段

由 Gateway 發起，通過 Flooding 或受限的 Flooding 算法構造一個以 Gateway 為根的生成樹。經過該過程后，生成了一棵以 Gateway 為根的廣度優先生成樹 BFS，其中每個節點都將知道自己的父節點和孩子節點，并將節點 ID 信息記入自己的父子關系表。

3.5.2 層次生成階段

從 Gateway 開始進行分層過程，其層次記為 0，并發送LM消息（Layer Message，其中包含節點 ID 和其層次）。收到LM的節點如果發現是由其父節點發出的，則該節點的層次記為父節點的層次加 1，然后發送自己的 LM 消息。同時，每個節點也記錄其鄰接點的層次信息，記入鄰居信息表。直至所有節點完成分層。

3.5.3 節點標記階段

初始化網絡中所有節點（Gateway 除外）為初始狀態。由Gateway 發起標記過程：首先標記自身為支配狀態，其次發送DM 消息，也即 “發送支配 DM” ，（包含 ID 和其支配狀態）。根據上文提出的節點-消息-動作策略，所有節點都將按照如下規則進行標記：

（a）如果處于初始狀態的節點收到支配 DM，則標記自身為被支配狀態，并廣播已被支配 DM；

（b）如果處于初始狀態的節點收到已被支配 DM，則標記自身為被支配狀態，并廣播未被支配 DM；

（c）如果處于初始狀態的節點收到未被支配 DM，則標記自身為被支配狀態，并廣播未被支配 DM；

（d）如果處于被支配狀態的節點收到所有孩子節點發送的未被支配 DM，則標記自身為支配狀態，并廣播支配 DM；（e）如果處于支配狀態的節點收到其非孩子的所有鄰居節點的支配DM，則標記自身為被支配狀態，并廣播已被支配DM。

4 實驗結果與分析

為了切實評價本文提出的自保護算法，驗證 BFS-basedMCDS算法的可行性，本文采用 NS2（Network Simulator）進行了仿真實驗。

首先，保護節點承擔保護其他節點的任務，不允許休眠，加快了對電能的消耗，容易導致電能耗盡而失效。因此保護節點越少 MCDS 算法越好，保護節點集的大小是評價隱藏算法的重要指標。為此我們在監控區域為 500×500 unit2 的二維矩形平面上，布置 N 個傳感器節點，設置節點通信半徑為110 unit，通過仿真實驗考察保護節點數目所占的比例。圖中 X 軸表示布置的節點數目，Y 軸表示通過 BFS-based MCDS 算法求得的保護節點比例 N R（Node R atio），其中 N R =支配節點數/網絡節點總數。從圖中可以看出，在不同節點密度下的BFS-based MCDS 算法的性能。

當節點總數少、節點密度小時，保護節點比例 N R 較大；隨著布置節點數的增多，保護節點比例 N R 越來越低。也即BFS-based MCDS 算法在稠密的網絡中能夠選擇相對較少的支配節點集，更具有優越性。這一現象可以這樣解釋：由于節點稀疏時，在通信半徑不變的情況下網絡連通度較小，很少有節點能夠被其他節點保護而隱藏；當節點密度增大時網絡中有更多地節點可以被保護而隱藏，導致保護節點比例 N R 下降。可以預測：在通信半徑不變的情況下，隨著節點密度增加，選擇的支配節點數目將趨于飽和。

其次，在區域監控應用中，傳感器網絡監控的對象是智能目標。盡管采用了隱藏技術使得部分傳感器節點保持靜默狀態，但靜默節點依然有被發現并敵意破壞的可能性。一旦隱藏節點被破壞，其保護節點應當及時生成緊急消息并匯報網關，這是區域監控應用中重要的設計要求。本文提出的基于廣度優先生成樹算法就是在充分考慮這一點的基礎上而設計的。

為了進一步衡量本文算法關于緊急消息 SOS 匯報的及時性，我們提出用平均匯報跳數作為指標，并做了如下仿真實驗。在監控區域為500×500 unit2 的二維矩形平面上，布置 N個傳感器節點，設置節點通信半徑為110 unit，通過仿真實驗考察緊急消息的平均匯報跳數，每個值都是重復獨立試驗節點隨機布置50次后求得的平均值。在不同節點密度下的 BFS-based MCDS 算法的 ASH 性能。當節點總數少、節點密度比較小時，平均匯報跳數很小；隨著布置節點數的增多，平均匯報跳數逐漸增大。但是增加的趨勢越來越緩和，可以預見，當節點數目趨于飽和時，平均增加跳數 ASH也將趨于某一極大值。

5 小結

本文研究了傳感器網絡的自保護算法，即在保證網絡正常監測功能的前提下，選擇部分節點作為保護節點的方法。首先我們提出了問題— — —如何選擇靜默節點集合，使得所有靜默節點都能被其他節點保護；其次，將問題歸納為基于廣度優先生成樹的最小連通支配集；針對這一數學問題，我們設計并實現了一種三階段的節點標記方法，求得最小連通支配集。進一步推導了最小連通支配集就是我們所要選擇保護節點集合，其余節點均是隱藏節點。仿真實驗證實了本文方法的可行性和有效性。

由于電池供電的特點，傳感器節點長時間執行保護容易導致電能耗盡而失效。一種延長傳感器網絡生命期的常見做法是休眠。那么在傳感器網絡自保護技術中，可以考慮生成多組MCDS 結果，實行節點輪換休眠，即是較好的選擇。這些都是未來努力的方向。