一種基于廣度優(yōu)先生成樹的無(wú)線傳感器網(wǎng)絡(luò)自保護(hù)算法

張文哲 李 鎣廣東工業(yè)大學(xué)

一種基于廣度優(yōu)先生成樹的無(wú)線傳感器網(wǎng)絡(luò)自保護(hù)算法

張文哲 李 鎣
廣東工業(yè)大學(xué)

從無(wú)線傳感器網(wǎng)絡(luò)中選取部分節(jié)點(diǎn)作為保護(hù)節(jié)點(diǎn)，為網(wǎng)絡(luò)提供保護(hù)稱為無(wú)線傳感器網(wǎng)絡(luò)的自保護(hù)。前人已經(jīng)證明自保護(hù)問(wèn)題是 NP- 完全問(wèn)題。提出一種基于廣度優(yōu)先生成樹的自保護(hù)算法，可以高效地分布式地選擇保護(hù)節(jié)點(diǎn)。我們首先為自保護(hù)問(wèn)題建模，其次提出了分布式的標(biāo)記過(guò)程，不同于前人工作的是，在保持較小保護(hù)節(jié)點(diǎn)集合的基礎(chǔ)上，我們還保持了保護(hù)節(jié)點(diǎn)的連通性，使得緊急消息到網(wǎng)關(guān)的平均匯報(bào)跳數(shù)最少，這一特點(diǎn)使得本文算法更加合理可行，從而提高了區(qū)域監(jiān)控應(yīng)用中傳感器網(wǎng)絡(luò)性能。仿真實(shí)驗(yàn)證明，本文算法可行性和有效性。

無(wú)線傳感器 自保護(hù)算法

1 無(wú)線傳感器網(wǎng)絡(luò)的自保護(hù)

1.1 傳感器網(wǎng)絡(luò)的輻射與暴露

在區(qū)域監(jiān)控應(yīng)用中，無(wú)線傳感器網(wǎng)絡(luò)通常被用來(lái)監(jiān)測(cè)入侵區(qū)域的任何目標(biāo) Target，這些目標(biāo)通常都是智能的，例如戰(zhàn)場(chǎng)上的敵人、商店的小偷以及公共安全場(chǎng)所的恐怖分子等。目標(biāo)不僅會(huì)發(fā)現(xiàn)布置的傳感器節(jié)點(diǎn)繞道入侵，而且會(huì)敵意破壞這些節(jié)點(diǎn)使之服務(wù)失效 Denial of Service。由此可見(jiàn)，我們有必要隱藏?zé)o線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)，使其能夠在敵對(duì)的環(huán)境下繼續(xù)工作，增強(qiáng)傳感器網(wǎng)絡(luò)的魯棒性。

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

針對(duì)電磁場(chǎng)暴露，我們重新考慮傳感器節(jié)點(diǎn)的組成與結(jié)構(gòu)，傳感器節(jié)點(diǎn)上能夠產(chǎn)生較大電磁場(chǎng)暴露的元器件，通常有兩個(gè)重要的組成部分：感知單元和通信單元。傳感器節(jié)點(diǎn)的感知方式有很多種，由于感知原理的不同，各種感知單元形成的電磁場(chǎng)強(qiáng)度各不相同。通常由于輻射強(qiáng)度與節(jié)點(diǎn)能耗成正比，節(jié)點(diǎn)在通信過(guò)程中的能耗是感知過(guò)程的十幾倍，因此通信時(shí)的電磁場(chǎng)暴露是傳感器節(jié)點(diǎn)暴露的關(guān)鍵因素。

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

此外還需要保護(hù)傳感器節(jié)點(diǎn)，實(shí)時(shí)監(jiān)控節(jié)點(diǎn)的狀態(tài)。一旦有節(jié)點(diǎn)被破壞，其保護(hù)節(jié)點(diǎn)即刻發(fā)送緊急消息 “SOS” 至網(wǎng)關(guān)匯報(bào)情況。這一技術(shù)稱之為自保護(hù)（Self-protection），也即由傳感器節(jié)點(diǎn)自己保護(hù)自己。自保護(hù)的實(shí)現(xiàn)是選擇部分節(jié)點(diǎn)承擔(dān)保護(hù)任務(wù)，實(shí)時(shí)監(jiān)督其他節(jié)點(diǎn)的狀態(tài)。一旦有節(jié)點(diǎn)被毀或者失效，網(wǎng)關(guān)能夠收到緊急消息并采取進(jìn)一步措施。由于電池供電，傳感器節(jié)點(diǎn)常常由于電能耗盡而失效，可見(jiàn)自保護(hù)技術(shù)是傳感器網(wǎng)絡(luò)健康狀態(tài)自我監(jiān)視的好方法，在區(qū)域監(jiān)控應(yīng)用中同樣具有重要的研究意義。

1.2 問(wèn)題的提出

減少通信量可以降低傳感器節(jié)點(diǎn)的電磁場(chǎng)暴露。根據(jù)傳感器網(wǎng)絡(luò)的輻射要求，把傳感器節(jié)點(diǎn)分為兩類：隱藏節(jié)點(diǎn)和保護(hù)節(jié)點(diǎn)。僅感知少通信的節(jié)點(diǎn)稱為隱藏節(jié)點(diǎn)，而既感知又通信的節(jié)點(diǎn)成為保護(hù)節(jié)點(diǎn)，承擔(dān)保護(hù)任務(wù)，監(jiān)視隱藏節(jié)點(diǎn)的狀態(tài)。

那么傳感器網(wǎng)絡(luò)中，選擇哪些節(jié)點(diǎn)為隱藏節(jié)點(diǎn)，哪些節(jié)點(diǎn)又為保護(hù)節(jié)點(diǎn)呢？ 這是需要重點(diǎn)解決的問(wèn)題。此外，在區(qū)域監(jiān)控應(yīng)用中，我們還發(fā)現(xiàn)隱藏節(jié)點(diǎn)的選擇過(guò)程具有以下特點(diǎn)：

1） 布置在監(jiān)控區(qū)域邊緣的節(jié)點(diǎn)最容易暴露、被破壞，因此最需要被保護(hù)；

2） 隱藏節(jié)點(diǎn)的數(shù)量越多越好，但是所有隱藏節(jié)點(diǎn)都需要被保護(hù)。通常地，假設(shè)節(jié)點(diǎn)一跳可保護(hù)，即保護(hù)節(jié)點(diǎn)可以定期詢問(wèn)隱藏節(jié)點(diǎn)是否安好；

3） 保護(hù)節(jié)點(diǎn)必須連通至網(wǎng)關(guān)，而且向網(wǎng)關(guān)匯報(bào)的緊急消息平均跳數(shù)最少。

基于上述分析，我們提出的問(wèn)題是，從所有節(jié)點(diǎn)集合V中，找出最小連通子集V*，使得任意節(jié)點(diǎn)要么屬于V*，要么在V*節(jié)點(diǎn)的一跳范圍內(nèi)。如此所得的V*節(jié)點(diǎn)是保護(hù)節(jié)點(diǎn)集合，承擔(dān)保護(hù)任務(wù)，實(shí)時(shí)監(jiān)督其他節(jié)點(diǎn)的狀態(tài)，不可以休眠；V -V*是被保護(hù)節(jié)點(diǎn)，可以休眠以減少電磁場(chǎng)暴露。

由此可見(jiàn)，傳感器網(wǎng)絡(luò)的隱藏問(wèn)題可以歸納為這樣的數(shù)學(xué)問(wèn)題：求任意連通圖的最小連通支配集（Minimum Connect-ed Dominating Set，MCDS）。關(guān)于最小連通支配集問(wèn)題，有人已經(jīng)證明是 NP完全問(wèn)題，前人已有出色的研究工作如下。

1.3 研究現(xiàn)狀

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

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

2 自保護(hù)模型與網(wǎng)絡(luò)建模

2.1 k-跳可保護(hù)與p-自保護(hù)

在無(wú)線傳感器網(wǎng)絡(luò)中，自保護(hù)指的是由傳感器節(jié)點(diǎn)之間相互保護(hù)，怎樣選擇保護(hù)節(jié)點(diǎn)集合承擔(dān)保護(hù)任務(wù)成為問(wèn)題的關(guān)鍵。

保護(hù)措施可以通過(guò)多跳通信的方式來(lái)實(shí)現(xiàn)，所以可以通過(guò)通信的跳數(shù)（hops）來(lái)衡量保護(hù)的種類。如果認(rèn)為傳感器節(jié)點(diǎn)可以通過(guò) k 跳通信的方式保護(hù)其他節(jié)點(diǎn)，則稱之為 k-跳可保護(hù)。通常假設(shè)，傳感器節(jié)點(diǎn)是 1-跳可保護(hù)的，即傳感器節(jié)點(diǎn)可以通過(guò) 1 跳通信方式監(jiān)視鄰居的狀態(tài)是否完好。

此外，自保護(hù)問(wèn)題還可以通過(guò)保護(hù)節(jié)點(diǎn)的數(shù)量來(lái)衡量。p-自保護(hù)被定義為，在任何時(shí)刻，傳感器節(jié)點(diǎn)至少被p個(gè)其他傳感器節(jié)點(diǎn)所監(jiān)視。如果p取值為1，則認(rèn)為任何時(shí)刻傳感器節(jié)點(diǎn)至少被1個(gè)其它節(jié)點(diǎn)所保護(hù)，也即1-自保護(hù)。在本文中，為了簡(jiǎn)化問(wèn)題，更好地致力于求解傳感器網(wǎng)絡(luò)的隱藏方法，我們假設(shè)節(jié)點(diǎn)之間均是1-跳可保護(hù)的，而且算法目的只要求1-自保護(hù)。

此外，我們認(rèn)為任何傳感器節(jié)點(diǎn)都需要被保護(hù)，包括保護(hù)節(jié)點(diǎn)自身。但由于問(wèn)題的特點(diǎn)是所有保護(hù)節(jié)點(diǎn)均連通至網(wǎng)關(guān)，則任何保護(hù)節(jié)點(diǎn)均可與其它保護(hù)節(jié)點(diǎn) 1-跳通信，也即任何保護(hù)節(jié)點(diǎn)均可以被保護(hù)?；谝陨戏治隹梢?jiàn)，傳感器網(wǎng)絡(luò)隱藏問(wèn)題就可以簡(jiǎn)化為求解隱藏節(jié)點(diǎn)被 1-跳可保護(hù)與 1-自保護(hù)的問(wèn)題。

2.2 網(wǎng)絡(luò)建模

由于傳感器網(wǎng)絡(luò)離散分布的特性，節(jié)點(diǎn)的幾何布置狀況有多種布置方法，有如確定性布置和隨機(jī)布置。確定性節(jié)點(diǎn)布置是傳感器網(wǎng)絡(luò)的簡(jiǎn)易布置方法，研究?jī)?nèi)容較少。本文中我們重點(diǎn)考慮隨機(jī)布置的情況。假設(shè)節(jié)點(diǎn)的初始位置均一并相互獨(dú)立地分布在監(jiān)控區(qū)域內(nèi)，且構(gòu)成一個(gè)連通的無(wú)向圖。為了更好地描述本文算法，首先給出如下有關(guān)基本概念。

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

定義3。圖G的節(jié)點(diǎn)集SV為支配集，當(dāng)且僅當(dāng)節(jié)點(diǎn)集S 滿足以下條件：/p∈V 則p∈S 或p為S中的某個(gè)節(jié)點(diǎn)的鄰節(jié)點(diǎn)。S 中的節(jié)點(diǎn)稱為支配點(diǎn)（Dominator），圖G中不屬于S 的節(jié)點(diǎn)稱為被支配點(diǎn)（Dominatee）。

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

定義5。若p為圖G=（V，E）中的任意節(jié)點(diǎn)，即p∈V，稱p在圖G中的相鄰節(jié)點(diǎn)的個(gè)數(shù)為p的度數(shù)，記為 D（p）。

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

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

定義 8。在圖G=（V，E）的生成子圖T是一棵廣度優(yōu)先生成樹，一個(gè)節(jié)點(diǎn)子樹的根節(jié)點(diǎn)稱為孩子節(jié)點(diǎn)，含有相同孩子節(jié)點(diǎn)的節(jié)點(diǎn)稱為父節(jié)點(diǎn)，具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)稱為兄弟節(jié)點(diǎn)。

3 基于BFS 的自保護(hù)算法

3.1 前提假設(shè)

隨機(jī)布置的傳感器網(wǎng)絡(luò)構(gòu)成一個(gè)簡(jiǎn)單無(wú)向圖，為了研究問(wèn)題的方便，我們?nèi)缦录僭O(shè)：

1）網(wǎng)絡(luò)拓?fù)涫沁B通的。因?yàn)閷?duì)于不連通的傳感器網(wǎng)絡(luò)來(lái)說(shuō)，節(jié)點(diǎn)的感知信息不能夠傳回至網(wǎng)關(guān)，必然是失效的節(jié)點(diǎn)，更多的隱藏與保護(hù)措施也無(wú)意義；

2）每個(gè)節(jié)點(diǎn)標(biāo)識(shí)了各自唯一的 ID，并通過(guò) 1 跳通信獲知其鄰居信息。每個(gè)節(jié)點(diǎn)維護(hù)自己的鄰居節(jié)點(diǎn)信息表，包括節(jié)點(diǎn)ID 號(hào)、層次和狀態(tài)信息；

3）網(wǎng)絡(luò)中節(jié)點(diǎn)可以分層，用層數(shù)表示：0，1，2…，網(wǎng)關(guān)層數(shù)為 0，以此類推。

基于以上假設(shè)，我們就可以構(gòu)建隱藏算法。

3.2 節(jié)點(diǎn)狀態(tài)與分類

根據(jù)節(jié)點(diǎn)的工作模式，傳感器節(jié)點(diǎn)分為兩種類型：隱藏節(jié)點(diǎn)和保護(hù)節(jié)點(diǎn)。本文將節(jié)點(diǎn)狀態(tài)相應(yīng)地定義為被支配狀態(tài)和支配狀態(tài)。

保護(hù)節(jié)點(diǎn)處于支配狀態(tài)，為其他節(jié)點(diǎn)提供保護(hù)；處于被支配狀態(tài)的節(jié)點(diǎn)是隱藏節(jié)點(diǎn)，被支配節(jié)點(diǎn)保護(hù)?？紤]到網(wǎng)絡(luò)的初始狀態(tài)，沒(méi)有生成任何保護(hù)節(jié)點(diǎn)和隱藏節(jié)點(diǎn)，所有節(jié)點(diǎn)都處于初始狀態(tài)，因此，傳感器節(jié)點(diǎn)有三種狀態(tài)，分別是初始狀態(tài)、被支配狀態(tài)和支配狀態(tài)，處于以上狀態(tài)的節(jié)點(diǎn)分別定義為初始節(jié)點(diǎn)primal、被支配節(jié)點(diǎn) dominatee 和支配節(jié)點(diǎn)dominator。

3.3 消息設(shè)計(jì)

為了實(shí)現(xiàn)分布式隱藏節(jié)點(diǎn)選擇算法，各節(jié)點(diǎn)需要溝通各自的狀態(tài)并協(xié)商。為此，我們?cè)O(shè)計(jì)了專門的消息，用于通告各自的狀態(tài)。這一消息在 1-跳范圍內(nèi)獲知，即消息接受者只接收，不轉(zhuǎn)發(fā)。如此設(shè)計(jì)，大大降低了消息廣播的數(shù)量，而且有效防止了消息洪泛的現(xiàn)象。

我們?cè)O(shè)計(jì)了兩種消息：1。分層消息 Layer Message用于通告自己的節(jié)點(diǎn)層次，消息結(jié)構(gòu)定義為 Layer（n，i）：表示節(jié)點(diǎn)n 處于第 i 層；2。狀態(tài)消息 State Message用于通告自己的節(jié)點(diǎn)狀態(tài)，有三種：Dominating（n）：表示節(jié)點(diǎn) n 處于支配狀態(tài)，為支配節(jié)點(diǎn)；Dominated（n）：表示節(jié)點(diǎn) n 處于已被支配狀態(tài)，為已被支配節(jié)點(diǎn)；Undominated（n）：表示節(jié)點(diǎn) n 處于未被支配狀態(tài)，為未被支配節(jié)點(diǎn)。

3.4 節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換策略

節(jié)點(diǎn)的狀態(tài)有三種，處于不同狀態(tài)節(jié)點(diǎn)也有三種，分別是初始節(jié)點(diǎn)、被支配節(jié)點(diǎn)、和支配節(jié)點(diǎn)。每當(dāng)收到不同的消息，節(jié)點(diǎn)狀態(tài)都要做出相應(yīng)的變化。初始狀態(tài)的節(jié)點(diǎn)收到任何消息都將轉(zhuǎn)換為被支配狀態(tài)，被支配狀態(tài)的節(jié)點(diǎn)收到被支配請(qǐng)求后，轉(zhuǎn)換為支配狀態(tài)；當(dāng)支配狀態(tài)的節(jié)點(diǎn)得知被支配節(jié)點(diǎn)包圍時(shí)，轉(zhuǎn)換為被支配節(jié)點(diǎn)。

節(jié)點(diǎn)在狀態(tài)轉(zhuǎn)換的過(guò)程中，還需要把這一狀態(tài)變化通告周圍鄰居。因此需要發(fā)送自己狀態(tài)消息。對(duì)于處于不同狀態(tài)的節(jié)點(diǎn)，每當(dāng)收到不同的消息，都將自己標(biāo)記為其他的狀態(tài)，同時(shí)發(fā)送新的消息表明自己的狀態(tài)。

3.5 基于 BFS 的 MCDS 問(wèn)題求解

3.5.1 BFS 樹構(gòu)造階段

由 Gateway 發(fā)起，通過(guò) Flooding 或受限的 Flooding 算法構(gòu)造一個(gè)以 Gateway 為根的生成樹。經(jīng)過(guò)該過(guò)程后，生成了一棵以 Gateway 為根的廣度優(yōu)先生成樹 BFS，其中每個(gè)節(jié)點(diǎn)都將知道自己的父節(jié)點(diǎn)和孩子節(jié)點(diǎn)，并將節(jié)點(diǎn) ID 信息記入自己的父子關(guān)系表。

3.5.2 層次生成階段

從 Gateway 開始進(jìn)行分層過(guò)程，其層次記為 0，并發(fā)送LM消息（Layer Message，其中包含節(jié)點(diǎn) ID 和其層次）。收到LM的節(jié)點(diǎn)如果發(fā)現(xiàn)是由其父節(jié)點(diǎn)發(fā)出的，則該節(jié)點(diǎn)的層次記為父節(jié)點(diǎn)的層次加 1，然后發(fā)送自己的 LM 消息。同時(shí)，每個(gè)節(jié)點(diǎn)也記錄其鄰接點(diǎn)的層次信息，記入鄰居信息表。直至所有節(jié)點(diǎn)完成分層。

3.5.3 節(jié)點(diǎn)標(biāo)記階段

初始化網(wǎng)絡(luò)中所有節(jié)點(diǎn)（Gateway 除外）為初始狀態(tài)。由Gateway 發(fā)起標(biāo)記過(guò)程：首先標(biāo)記自身為支配狀態(tài)，其次發(fā)送DM 消息，也即 “發(fā)送支配 DM” ，（包含 ID 和其支配狀態(tài)）。根據(jù)上文提出的節(jié)點(diǎn)-消息-動(dòng)作策略，所有節(jié)點(diǎn)都將按照如下規(guī)則進(jìn)行標(biāo)記：

（a）如果處于初始狀態(tài)的節(jié)點(diǎn)收到支配 DM，則標(biāo)記自身為被支配狀態(tài)，并廣播已被支配 DM；

（b）如果處于初始狀態(tài)的節(jié)點(diǎn)收到已被支配 DM，則標(biāo)記自身為被支配狀態(tài)，并廣播未被支配 DM；

（c）如果處于初始狀態(tài)的節(jié)點(diǎn)收到未被支配 DM，則標(biāo)記自身為被支配狀態(tài)，并廣播未被支配 DM；

（d）如果處于被支配狀態(tài)的節(jié)點(diǎn)收到所有孩子節(jié)點(diǎn)發(fā)送的未被支配 DM，則標(biāo)記自身為支配狀態(tài)，并廣播支配 DM；（e）如果處于支配狀態(tài)的節(jié)點(diǎn)收到其非孩子的所有鄰居節(jié)點(diǎn)的支配DM，則標(biāo)記自身為被支配狀態(tài)，并廣播已被支配DM。

4 實(shí)驗(yàn)結(jié)果與分析

為了切實(shí)評(píng)價(jià)本文提出的自保護(hù)算法，驗(yàn)證 BFS-basedMCDS算法的可行性，本文采用 NS2（Network Simulator）進(jìn)行了仿真實(shí)驗(yàn)。

首先，保護(hù)節(jié)點(diǎn)承擔(dān)保護(hù)其他節(jié)點(diǎn)的任務(wù)，不允許休眠，加快了對(duì)電能的消耗，容易導(dǎo)致電能耗盡而失效。因此保護(hù)節(jié)點(diǎn)越少 MCDS 算法越好，保護(hù)節(jié)點(diǎn)集的大小是評(píng)價(jià)隱藏算法的重要指標(biāo)。為此我們?cè)诒O(jiān)控區(qū)域?yàn)?500×500 unit2 的二維矩形平面上，布置 N 個(gè)傳感器節(jié)點(diǎn)，設(shè)置節(jié)點(diǎn)通信半徑為110 unit，通過(guò)仿真實(shí)驗(yàn)考察保護(hù)節(jié)點(diǎn)數(shù)目所占的比例。圖中 X 軸表示布置的節(jié)點(diǎn)數(shù)目，Y 軸表示通過(guò) BFS-based MCDS 算法求得的保護(hù)節(jié)點(diǎn)比例 N R（Node R atio），其中 N R =支配節(jié)點(diǎn)數(shù)/網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)。從圖中可以看出，在不同節(jié)點(diǎn)密度下的BFS-based MCDS 算法的性能。

當(dāng)節(jié)點(diǎn)總數(shù)少、節(jié)點(diǎn)密度小時(shí)，保護(hù)節(jié)點(diǎn)比例 N R 較大；隨著布置節(jié)點(diǎn)數(shù)的增多，保護(hù)節(jié)點(diǎn)比例 N R 越來(lái)越低。也即BFS-based MCDS 算法在稠密的網(wǎng)絡(luò)中能夠選擇相對(duì)較少的支配節(jié)點(diǎn)集，更具有優(yōu)越性。這一現(xiàn)象可以這樣解釋：由于節(jié)點(diǎn)稀疏時(shí)，在通信半徑不變的情況下網(wǎng)絡(luò)連通度較小，很少有節(jié)點(diǎn)能夠被其他節(jié)點(diǎn)保護(hù)而隱藏；當(dāng)節(jié)點(diǎn)密度增大時(shí)網(wǎng)絡(luò)中有更多地節(jié)點(diǎn)可以被保護(hù)而隱藏，導(dǎo)致保護(hù)節(jié)點(diǎn)比例 N R 下降?？梢灶A(yù)測(cè)：在通信半徑不變的情況下，隨著節(jié)點(diǎn)密度增加，選擇的支配節(jié)點(diǎn)數(shù)目將趨于飽和。

其次，在區(qū)域監(jiān)控應(yīng)用中，傳感器網(wǎng)絡(luò)監(jiān)控的對(duì)象是智能目標(biāo)。盡管采用了隱藏技術(shù)使得部分傳感器節(jié)點(diǎn)保持靜默狀態(tài)，但靜默節(jié)點(diǎn)依然有被發(fā)現(xiàn)并敵意破壞的可能性。一旦隱藏節(jié)點(diǎn)被破壞，其保護(hù)節(jié)點(diǎn)應(yīng)當(dāng)及時(shí)生成緊急消息并匯報(bào)網(wǎng)關(guān)，這是區(qū)域監(jiān)控應(yīng)用中重要的設(shè)計(jì)要求。本文提出的基于廣度優(yōu)先生成樹算法就是在充分考慮這一點(diǎn)的基礎(chǔ)上而設(shè)計(jì)的。

為了進(jìn)一步衡量本文算法關(guān)于緊急消息 SOS 匯報(bào)的及時(shí)性，我們提出用平均匯報(bào)跳數(shù)作為指標(biāo)，并做了如下仿真實(shí)驗(yàn)。在監(jiān)控區(qū)域?yàn)?00×500 unit2 的二維矩形平面上，布置 N個(gè)傳感器節(jié)點(diǎn)，設(shè)置節(jié)點(diǎn)通信半徑為110 unit，通過(guò)仿真實(shí)驗(yàn)考察緊急消息的平均匯報(bào)跳數(shù)，每個(gè)值都是重復(fù)獨(dú)立試驗(yàn)節(jié)點(diǎn)隨機(jī)布置50次后求得的平均值。在不同節(jié)點(diǎn)密度下的 BFS-based MCDS 算法的 ASH 性能。當(dāng)節(jié)點(diǎn)總數(shù)少、節(jié)點(diǎn)密度比較小時(shí)，平均匯報(bào)跳數(shù)很?。浑S著布置節(jié)點(diǎn)數(shù)的增多，平均匯報(bào)跳數(shù)逐漸增大。但是增加的趨勢(shì)越來(lái)越緩和，可以預(yù)見(jiàn)，當(dāng)節(jié)點(diǎn)數(shù)目趨于飽和時(shí)，平均增加跳數(shù) ASH也將趨于某一極大值。

5 小結(jié)

本文研究了傳感器網(wǎng)絡(luò)的自保護(hù)算法，即在保證網(wǎng)絡(luò)正常監(jiān)測(cè)功能的前提下，選擇部分節(jié)點(diǎn)作為保護(hù)節(jié)點(diǎn)的方法。首先我們提出了問(wèn)題— — —如何選擇靜默節(jié)點(diǎn)集合，使得所有靜默節(jié)點(diǎn)都能被其他節(jié)點(diǎn)保護(hù)；其次，將問(wèn)題歸納為基于廣度優(yōu)先生成樹的最小連通支配集；針對(duì)這一數(shù)學(xué)問(wèn)題，我們?cè)O(shè)計(jì)并實(shí)現(xiàn)了一種三階段的節(jié)點(diǎn)標(biāo)記方法，求得最小連通支配集。進(jìn)一步推導(dǎo)了最小連通支配集就是我們所要選擇保護(hù)節(jié)點(diǎn)集合，其余節(jié)點(diǎn)均是隱藏節(jié)點(diǎn)。仿真實(shí)驗(yàn)證實(shí)了本文方法的可行性和有效性。

由于電池供電的特點(diǎn)，傳感器節(jié)點(diǎn)長(zhǎng)時(shí)間執(zhí)行保護(hù)容易導(dǎo)致電能耗盡而失效。一種延長(zhǎng)傳感器網(wǎng)絡(luò)生命期的常見(jiàn)做法是休眠。那么在傳感器網(wǎng)絡(luò)自保護(hù)技術(shù)中，可以考慮生成多組MCDS 結(jié)果，實(shí)行節(jié)點(diǎn)輪換休眠，即是較好的選擇。這些都是未來(lái)努力的方向。