趙利輝，劉文怡，張　斌，譚秋林

(中北大學(xué) a.電子測(cè)試技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室;

b.儀器科學(xué)與動(dòng)態(tài)測(cè)試教育部重點(diǎn)實(shí)驗(yàn)室,山西 太原 030051)

?

無(wú)線傳感器網(wǎng)絡(luò)邊界節(jié)點(diǎn)識(shí)別研究進(jìn)展綜述

趙利輝a，b，劉文怡a，b，張斌a，譚秋林a，b

(中北大學(xué)a.電子測(cè)試技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室;

b.儀器科學(xué)與動(dòng)態(tài)測(cè)試教育部重點(diǎn)實(shí)驗(yàn)室,山西 太原 030051)

邊界節(jié)點(diǎn)的識(shí)別是無(wú)線傳感器網(wǎng)絡(luò)研究中的一個(gè)基本問(wèn)題，是識(shí)別覆蓋空洞的關(guān)鍵，也是優(yōu)化網(wǎng)絡(luò)覆蓋的基礎(chǔ)和數(shù)據(jù)可靠傳輸?shù)谋Ｕ?。在綜述邊界節(jié)點(diǎn)識(shí)別算法的基礎(chǔ)上，提出了基于節(jié)點(diǎn)可用信息和技術(shù)策略的算法分類方法，在歸納各類算法技術(shù)特點(diǎn)的基礎(chǔ)上對(duì)比分析了不同算法的優(yōu)點(diǎn)及存在的問(wèn)題，并對(duì)未來(lái)的研究方向進(jìn)行了總結(jié)與展望。

無(wú)線傳感器網(wǎng)絡(luò)；邊界節(jié)點(diǎn)；覆蓋空洞；綜述

無(wú)線傳感器網(wǎng)絡(luò)(WSN)是由大量成本低、體積小整合了傳感、無(wú)線通信、數(shù)據(jù)存儲(chǔ)和處理等單元的微型傳感器節(jié)點(diǎn)，以相互協(xié)作的方式構(gòu)成的一種無(wú)線多跳自組織型網(wǎng)絡(luò)。WSN可以通過(guò)飛機(jī)拋灑或炮射等方式部署于危險(xiǎn)區(qū)域中執(zhí)行各種監(jiān)測(cè)任務(wù)，在戰(zhàn)場(chǎng)監(jiān)測(cè)、環(huán)境監(jiān)測(cè)、結(jié)構(gòu)安全監(jiān)測(cè)、?；繁O(jiān)測(cè)、森林火災(zāi)預(yù)防和火山噴發(fā)等領(lǐng)域展現(xiàn)出了極大的潛在應(yīng)用價(jià)值，也成為當(dāng)前WSN研究中的熱點(diǎn)問(wèn)題。與傳統(tǒng)網(wǎng)絡(luò)相比，WSN的獨(dú)特性在于：1)WSN生存周期受節(jié)點(diǎn)能量的限制；2)節(jié)點(diǎn)的通信距離、存儲(chǔ)空間和計(jì)算能力受節(jié)點(diǎn)能量和結(jié)構(gòu)的限制；3)節(jié)點(diǎn)結(jié)構(gòu)、部署模式和應(yīng)用環(huán)境使其容易形成覆蓋空洞。而前面所提及的如戰(zhàn)場(chǎng)監(jiān)測(cè)等應(yīng)用都要求WSN有良好的網(wǎng)絡(luò)覆蓋和可靠的網(wǎng)絡(luò)服務(wù)質(zhì)量(QualityofService，QoS)，以便能對(duì)監(jiān)測(cè)區(qū)域進(jìn)行及時(shí)和有效的監(jiān)測(cè)。然而覆蓋空洞的出現(xiàn)嚴(yán)重影響網(wǎng)絡(luò)的QoS，其不僅導(dǎo)致WSN出現(xiàn)監(jiān)測(cè)盲區(qū)，還會(huì)引發(fā)數(shù)據(jù)融合故障，網(wǎng)絡(luò)負(fù)載失衡，加劇節(jié)點(diǎn)工作負(fù)荷等一系列衍生問(wèn)題，直接威脅了WSN的生命周期。

許多研究者為解決覆蓋空洞問(wèn)題進(jìn)行了不懈的努力，提出很多基于邊界節(jié)點(diǎn)識(shí)別的覆蓋空洞檢測(cè)識(shí)別算法，本文針對(duì)WSN邊界節(jié)點(diǎn)識(shí)別問(wèn)題的最新研究進(jìn)展進(jìn)行了綜述，根據(jù)不同研究方法所采用的節(jié)點(diǎn)信息類型和技術(shù)策略對(duì)算法進(jìn)行了分類、對(duì)比、分析和總結(jié)，對(duì)其存在的問(wèn)題、優(yōu)缺點(diǎn)進(jìn)行了歸納和總結(jié)，最后探討了未來(lái)研究的方向。

1　模型、定義與標(biāo)準(zhǔn)

為方便描述，本節(jié)給出文中涉及到的網(wǎng)絡(luò)模型、定義和評(píng)價(jià)標(biāo)準(zhǔn)。

1.1網(wǎng)絡(luò)模型

1.2定義

覆蓋空洞：本文的覆蓋空洞是指WSN監(jiān)測(cè)區(qū)域中不能被任一節(jié)點(diǎn)的傳感區(qū)域覆蓋的監(jiān)測(cè)盲區(qū)。

邊界節(jié)點(diǎn)：本文的邊界節(jié)點(diǎn)包含兩類，一類是位于WSN內(nèi)部且處于覆蓋空洞邊緣的節(jié)點(diǎn)，另一類則是指位于WSN最外層邊緣能夠標(biāo)識(shí)監(jiān)測(cè)區(qū)域輪廓的節(jié)點(diǎn)。

當(dāng)前節(jié)點(diǎn)：本文特指那些初始化完成準(zhǔn)備執(zhí)行邊界節(jié)點(diǎn)識(shí)別算法的節(jié)點(diǎn)，表示為S。

鄰居集：給定一個(gè)節(jié)點(diǎn)si，如果有節(jié)點(diǎn)sj滿足式(1)，則稱sj為si的k跳鄰居節(jié)點(diǎn)，所有k跳鄰居節(jié)點(diǎn)的集合稱為si的k跳鄰居集，表示為Nk(si)，1跳鄰居集也可表示為Nk(si)，di,j表示節(jié)點(diǎn)間的歐氏距離

(k-1)×rc≤di,j≤k×rc(k=1,2，3，…,n)

(1)

1.3算法評(píng)估標(biāo)準(zhǔn)

邊界節(jié)點(diǎn)是識(shí)別覆蓋空洞和優(yōu)化網(wǎng)絡(luò)覆蓋的關(guān)鍵問(wèn)題，也可以提升路由效率，確保數(shù)據(jù)聚合，延長(zhǎng)網(wǎng)絡(luò)生命周期。因而，合理的評(píng)估標(biāo)準(zhǔn)對(duì)于準(zhǔn)確評(píng)價(jià)邊界節(jié)點(diǎn)識(shí)別算法的性能至關(guān)重要。本文提出的評(píng)估標(biāo)準(zhǔn)如下：

1) 識(shí)別精度，是衡量算法性能的首要標(biāo)準(zhǔn)，也是識(shí)別覆蓋空洞的關(guān)鍵。識(shí)別精度常受網(wǎng)絡(luò)節(jié)點(diǎn)配置、節(jié)點(diǎn)可用信息和系統(tǒng)模型的限制。

2) 節(jié)點(diǎn)度，是評(píng)估算法優(yōu)劣的重要標(biāo)準(zhǔn)。其限定了算法的適用領(lǐng)域，直接影響了算法的識(shí)別精度和網(wǎng)絡(luò)部署成本。

3) 節(jié)點(diǎn)信息類型，不同的邊界節(jié)點(diǎn)識(shí)別方案對(duì)網(wǎng)絡(luò)資源的需求也不同，本文的節(jié)點(diǎn)信息類型包括網(wǎng)絡(luò)中節(jié)點(diǎn)的位置信息、節(jié)點(diǎn)度統(tǒng)計(jì)信息和拓?fù)浣Y(jié)構(gòu)信息等，是劃分算法類型的標(biāo)準(zhǔn)之一。

4) 能量有效性，是WSN中節(jié)點(diǎn)提供監(jiān)測(cè)、通信和數(shù)據(jù)傳輸?shù)确?wù)所消耗的能量。其直接關(guān)系到WSN的生存周期，是導(dǎo)致節(jié)點(diǎn)失效的直接原因和衡量算法優(yōu)劣的重要標(biāo)準(zhǔn)。

5) 通信開(kāi)銷，是指WSN的節(jié)點(diǎn)在數(shù)據(jù)收集、融合和消息傳遞過(guò)程中其無(wú)線通信模塊的能量消耗，本文的通信開(kāi)銷評(píng)估模型為文獻(xiàn)[1-2]所述模型。

6) 算法復(fù)雜度，是衡量算法優(yōu)劣的一個(gè)重要尺度，算法復(fù)雜度包括時(shí)間復(fù)雜度、消息復(fù)雜度和空間復(fù)雜度等。

7) “閉環(huán)”策略，即判斷當(dāng)前結(jié)點(diǎn)的鄰居節(jié)點(diǎn)能否構(gòu)造一個(gè)圍繞當(dāng)前結(jié)點(diǎn)的閉合環(huán)路來(lái)識(shí)別該節(jié)點(diǎn)是否為邊界節(jié)點(diǎn)的策略，如果“閉環(huán)”存在則節(jié)點(diǎn)為內(nèi)部節(jié)點(diǎn)，否則為邊界節(jié)點(diǎn)。是一種常用的邊界節(jié)點(diǎn)識(shí)別方法，也是本文劃分算法類型的標(biāo)準(zhǔn)之一。

8) 算法模型，是依據(jù)算法執(zhí)行過(guò)程中是否依賴一個(gè)或多個(gè)中心節(jié)點(diǎn)，將邊界節(jié)點(diǎn)識(shí)別方法分為集中式算法和分布式算法兩類。

2　邊界節(jié)點(diǎn)識(shí)別方案

邊界節(jié)點(diǎn)的檢測(cè)與識(shí)別是覆蓋空洞識(shí)別和修補(bǔ)的關(guān)鍵，也與網(wǎng)絡(luò)覆蓋、拓?fù)淇刂啤⒐?jié)能通信、路由協(xié)議設(shè)計(jì)、入侵檢測(cè)和目標(biāo)定位等應(yīng)用密切相關(guān)。為了全面認(rèn)識(shí)邊界節(jié)點(diǎn)識(shí)別問(wèn)題，總結(jié)當(dāng)前的研究成果，本文根據(jù)目前研究中采用的節(jié)點(diǎn)信息類型、算法模型和技術(shù)策略對(duì)邊界節(jié)點(diǎn)識(shí)別方案進(jìn)行了歸納、分析、對(duì)比和總結(jié)。

2.1邊界節(jié)點(diǎn)識(shí)別方法分類

根據(jù)研究中采用的節(jié)點(diǎn)信息的不同，可將邊界節(jié)點(diǎn)識(shí)別方法分為基于計(jì)算幾何、基于統(tǒng)計(jì)方法和基于拓?fù)浞椒ǖ倪吔绻?jié)點(diǎn)識(shí)別方法3類。根據(jù)算法模型的不同將邊界節(jié)點(diǎn)識(shí)別方法分為集中式算法和分布式算法。根據(jù)邊界節(jié)點(diǎn)識(shí)別算法是否采用“閉環(huán)”策略可將其分類為基于閉環(huán)的方法和基于非閉環(huán)的方法。圖 1給出了邊界節(jié)點(diǎn)的識(shí)別方法分類圖。

圖1　算法分類

2.2基于節(jié)點(diǎn)信息的邊界節(jié)點(diǎn)識(shí)別方法

2.2.1基于計(jì)算幾何的邊界節(jié)點(diǎn)識(shí)別算法

基于計(jì)算幾何方法的識(shí)別算法的共同特點(diǎn)是假設(shè)節(jié)點(diǎn)的位置(或距離)信息已知，利用典型的幾何工具分析節(jié)點(diǎn)間的幾何特性實(shí)現(xiàn)邊界節(jié)點(diǎn)的識(shí)別。其中的代表性算法包括：

1)周界搜索算法

Martincic等在文獻(xiàn)[3]中提出一種稱為“周界搜索”的分布式邊界節(jié)點(diǎn)識(shí)別算法，簡(jiǎn)稱為DPD(本文中周界是指節(jié)點(diǎn)傳感范圍的外圍邊界)。DPD是一種分布式算法(見(jiàn)圖2)，可被WSN中的任意一個(gè)節(jié)點(diǎn)自主執(zhí)行。假設(shè)節(jié)點(diǎn)正在執(zhí)行DPD，則DPD首先計(jì)算N(S)和N2(S)在以S為圓心的坐標(biāo)系中的絕對(duì)角并按絕對(duì)角升序排列所有鄰居節(jié)點(diǎn)，然后以絕對(duì)角最小的鄰居節(jié)點(diǎn)為起始節(jié)點(diǎn)利用深度搜索算法查找是否存在一個(gè)“閉環(huán)”能將節(jié)點(diǎn)包圍，如果這樣的“閉環(huán)”存在，則節(jié)點(diǎn)為內(nèi)部節(jié)點(diǎn)，否則為邊界節(jié)點(diǎn)。

圖2　DPD算法示意圖

Khedr等在文獻(xiàn)[4]中也提出了基于“周界搜索”的邊界節(jié)點(diǎn)識(shí)別算法，簡(jiǎn)稱為PD。與DPD不同的是其采用了Barycentric坐標(biāo)技術(shù)，且不需要計(jì)算每個(gè)鄰居節(jié)點(diǎn)相對(duì)于節(jié)點(diǎn)S的絕對(duì)角。PD將節(jié)點(diǎn)分布區(qū)域分為4類即4個(gè)不同的象區(qū)Qi(i=1,2,3,4)，然后通過(guò)檢測(cè)Qi之間的連通性判斷節(jié)點(diǎn)S是否為邊界節(jié)點(diǎn)，即：如果有兩個(gè)象區(qū)為空則S為邊界節(jié)點(diǎn)；如果3個(gè)或全部象區(qū)不為空則檢測(cè)象區(qū)間的連通性；如果各個(gè)象區(qū)相互連通，節(jié)點(diǎn)S為內(nèi)部節(jié)點(diǎn)，否則為邊界節(jié)點(diǎn)。

Huang等在文獻(xiàn)[5]中提出一種基于節(jié)點(diǎn)傳感區(qū)域周界覆蓋掃描的算法用于檢測(cè)WSN中節(jié)點(diǎn)的覆蓋問(wèn)題。陳和孫等[6]在PD和文獻(xiàn)[5]的基礎(chǔ)上提出一種“高效的邊緣檢測(cè)算法”，簡(jiǎn)稱EBD。EBD首先以S為圓心生成笛卡爾坐標(biāo)系，并判斷處于該坐標(biāo)系中的N(S)是否能將?C(S)完全覆蓋，如果可以，則S為內(nèi)部節(jié)點(diǎn)，否則為邊界節(jié)點(diǎn)。執(zhí)行過(guò)程中，如果N(S)僅處于以S為圓心的笛卡爾坐標(biāo)系的兩個(gè)象區(qū)中，則S為邊界節(jié)點(diǎn)，如圖3a所示；否則計(jì)算節(jié)點(diǎn)S與各鄰居節(jié)點(diǎn)的傳感區(qū)域的交點(diǎn)確認(rèn)其?C(S)的覆蓋情況，如果其能被鄰居節(jié)點(diǎn)的傳感區(qū)域完全覆蓋，S為內(nèi)部節(jié)點(diǎn)，如圖3b所示。

圖3　PD、EBD周界掃描算法原理

優(yōu)點(diǎn)：基于周界搜索的算法簡(jiǎn)單高效，可應(yīng)用于各種規(guī)模的網(wǎng)絡(luò)，節(jié)點(diǎn)正確識(shí)別率高、錯(cuò)誤率和漏檢率低；仿真結(jié)果表明算法通信開(kāi)銷小，能量消耗少；在節(jié)點(diǎn)位置較精確的情況下，算法魯棒性好，擴(kuò)展性好，如Huang等的算法已擴(kuò)展到三維領(lǐng)域。

缺點(diǎn)：需配置定位或測(cè)距設(shè)備，錨節(jié)點(diǎn)能量消耗高，上述算法均沒(méi)有評(píng)估同質(zhì)節(jié)點(diǎn)網(wǎng)絡(luò)中錨節(jié)點(diǎn)因素的影響和環(huán)境干擾帶來(lái)的位置誤差的影響。

2)三角形搜索算法

三角形搜索算法是對(duì)Deogun提出的好鄰居搜索算法[7](ChooseGoodNeighbor，CGN)及其改進(jìn)算法的總稱，CGN是一種分布式算法，可以被WSN網(wǎng)絡(luò)中任意一個(gè)節(jié)點(diǎn)執(zhí)行。CGN同周界搜索算法一樣采用“閉環(huán)”的思想，差異體現(xiàn)在：1)CGN的“閉環(huán)”是三角形而其他周界搜索算法是多邊形結(jié)構(gòu)；2)CGN通過(guò)利用海倫公式(式(2))分別計(jì)算圖4a中△ABC，△ABP，△ACP和△BCP的面積，然后通過(guò)檢測(cè)他們之間是否符合式(3)判定節(jié)點(diǎn)是否為邊界節(jié)點(diǎn)，而周界搜索算法則是通過(guò)檢測(cè)被檢測(cè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)能否構(gòu)成一個(gè)“閉環(huán)”來(lái)檢測(cè)該節(jié)點(diǎn)是否為邊界節(jié)點(diǎn)。如圖4b所示，CGN在判斷節(jié)點(diǎn)P是否為邊界節(jié)點(diǎn)時(shí)首先選擇節(jié)點(diǎn)P的最近鄰居做為三角形頂點(diǎn)A，然后以dP,A為半徑搜索頂點(diǎn)B，B需滿足條件：1)B∈N(P)；2)B∈N(A)；3)在所有節(jié)點(diǎn)A的一跳鄰居節(jié)點(diǎn)中距離dA,B最大。然后以條件min(|dA,C-dB,C|∧dP,C)選擇頂點(diǎn)C，以符合條件min(dA,D-dB,C|)，max(dD,C)和dD,C>dD,P∧dD,C>dP,C的節(jié)點(diǎn)為D，在構(gòu)成的三角形中，如果P位于△ABC或△ABD內(nèi)，則P為內(nèi)部節(jié)點(diǎn)，否則為邊界節(jié)點(diǎn)。

圖4　三角形搜索算法示意圖

為了簡(jiǎn)化CGN構(gòu)建三角形的過(guò)程，Simek等在文獻(xiàn)[8]提出一種BRC算法，該方法與CGN的差異在于三角形頂點(diǎn)C的選擇過(guò)程，即BRC將P的一跳鄰居除頂點(diǎn)A和B以外的節(jié)點(diǎn)作為一個(gè)集合CSet，如圖4c所示，CSet={C1,C2,…,C10}，如果CSet中的任一節(jié)點(diǎn)能夠和節(jié)點(diǎn)A與B構(gòu)成的△ABC滿足式(3),則節(jié)點(diǎn)P為內(nèi)部節(jié)點(diǎn)，否則為邊界節(jié)點(diǎn)

(2)

S△ABC=S△ABP+S△BCP+S△ACP

(3)

優(yōu)點(diǎn)：在周界搜索算法的基礎(chǔ)上，CGN和BRC簡(jiǎn)化了“閉環(huán)”的構(gòu)造，節(jié)點(diǎn)自我識(shí)別過(guò)程所需信息少且精確。

缺點(diǎn)：仿真結(jié)果表明，節(jié)點(diǎn)位置不規(guī)則的情況下并不能構(gòu)建如圖 4a所示的規(guī)則三角形，尤其在三角形為鈍角且其相對(duì)的邊長(zhǎng)較大的情況下該算法常常失效。

3) 三角形特性搜索算法

Ma等在文獻(xiàn)[9]中基于節(jié)點(diǎn)間的三角形幾何特性提出一種分布式邊界節(jié)點(diǎn)識(shí)別算法，簡(jiǎn)稱為CDCH。其具體執(zhí)行過(guò)程為：

(1)令N=N(S)∪N2(S)，其中表示一跳和二跳鄰居的合集。

(2)計(jì)算中每個(gè)節(jié)點(diǎn)在以S為圓心的笛卡爾坐標(biāo)系中的絕對(duì)角并升序排列。

(3)抽取中的一對(duì)相鄰節(jié)點(diǎn)A和B與S組成三角形△SAB，并計(jì)算△SAB外接圓的半徑。

(4)如果△SAB及R滿足任意下述條件則S為邊界節(jié)點(diǎn)：

①A，B∈N(S),△SAB為鈍角三角形且R≤Rs；

②A，B∈N2(S),△SAB為銳角三角形且R>Rs；

③A,B∈N2(S)且∠ASB≥90°；

④如果A∈N(S)∧B∈N2(S)或相反情況，△SAB為銳角三角形且R>Rs；

⑤如果A∈N(S)∧B∈N2(S)或相反情況且∠ASB≥90°；

⑥△SAB外接圓圓心不能被任何節(jié)點(diǎn)的傳感區(qū)域覆蓋。雖然CDCH算法需要分析多種三角形特性，但其一個(gè)明顯的優(yōu)點(diǎn)是解決了多邊形“閉環(huán)”不能識(shí)別三角形覆蓋空洞的問(wèn)題。

此外，Li等基于Delaunay三角形[10]的空?qǐng)A特性在文獻(xiàn)[11]提出一種邊界節(jié)點(diǎn)識(shí)別算法，簡(jiǎn)稱為CHB。該算法一個(gè)顯著的優(yōu)點(diǎn)是無(wú)須像CDCH一樣需要枚舉三角形外接圓的各種特性，能夠以一種統(tǒng)一且容易的模式識(shí)別出邊界節(jié)點(diǎn)，而且能夠識(shí)別出位于三角形覆蓋空洞邊緣的節(jié)點(diǎn)。

優(yōu)點(diǎn)：算法充分發(fā)掘了三角形的幾何特性，相比其他算法，CDCH和CHB能識(shí)別出位于三角形覆蓋空洞的邊界節(jié)點(diǎn)，解決了其他算法無(wú)法識(shí)別三角形覆蓋空洞的問(wèn)題，提高了識(shí)別精度。

缺點(diǎn)：要求節(jié)點(diǎn)位置信息或距離信息，需要為節(jié)點(diǎn)配置定位或距離測(cè)量裝置如GPS等；WSN部署成本高，節(jié)點(diǎn)體積大，易受環(huán)境因素干擾，且上述算法均沒(méi)有評(píng)估地形干擾、定位或測(cè)量誤差對(duì)識(shí)別精度的影響；配置定位裝置的節(jié)點(diǎn)能量消耗大，影響其生存周期。

2.2.2基于統(tǒng)計(jì)的方法

Fekete在文獻(xiàn)[12]中利用處于WSN邊緣節(jié)點(diǎn)的平均連通度低于網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)的平均連通度的特點(diǎn),提出一種基于節(jié)點(diǎn)連通度統(tǒng)計(jì)信息的邊界節(jié)點(diǎn)識(shí)別方法，簡(jiǎn)稱NTR。該方法通過(guò)經(jīng)驗(yàn)值預(yù)設(shè)一個(gè)節(jié)點(diǎn)度閾值α，節(jié)點(diǎn)度大于α的節(jié)點(diǎn)為內(nèi)部節(jié)點(diǎn)，否則為邊界節(jié)點(diǎn)。此后，F(xiàn)ekete等又在文獻(xiàn)[13]中提出一種稱為“限制壓力中心”的算法，簡(jiǎn)稱為RSC算法，其數(shù)學(xué)模型為式(4)。RSC通過(guò)統(tǒng)計(jì)在WSN內(nèi)各節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最短路徑經(jīng)過(guò)節(jié)點(diǎn)v的次數(shù)獲得節(jié)點(diǎn)v的限制壓力度，而整個(gè)網(wǎng)絡(luò)的限制壓力度閾值獲取方法和節(jié)點(diǎn)的判別方法與NTR相同

(4)

式中：σst(v)表示W(wǎng)SN中經(jīng)過(guò)節(jié)點(diǎn)v的最短路徑。

優(yōu)點(diǎn)：不依賴節(jié)點(diǎn)的位置信息，因而無(wú)需裝配定位裝置；降低了部署成本，不受環(huán)境因素干擾。

缺點(diǎn)：該算法要求極高的網(wǎng)絡(luò)密度，要求網(wǎng)絡(luò)節(jié)點(diǎn)平均連通度達(dá)到100或以上；在稀疏網(wǎng)絡(luò)中不具可行性，識(shí)別效果極差。

2.2.3基于拓?fù)涞姆椒?/p>

基于拓?fù)涞倪吔绻?jié)點(diǎn)識(shí)別方法也被稱為基于連接信息的邊界節(jié)點(diǎn)識(shí)別方法，其優(yōu)點(diǎn)是不依賴節(jié)點(diǎn)位置信息，對(duì)節(jié)點(diǎn)平均連通度要求低，這使其在稀疏網(wǎng)絡(luò)中也能取得較高的識(shí)別精度[14]。因而該方法在許多應(yīng)用尤其是易受環(huán)境干擾的應(yīng)用中贏得了廣泛的關(guān)注。

1)基于輪廓的邊界節(jié)點(diǎn)識(shí)別方法

Funke等認(rèn)為WSN可以按節(jié)點(diǎn)位置劃分為層層環(huán)繞的輪廓，如圖5a所示，而邊界節(jié)點(diǎn)顯然不會(huì)存在于一個(gè)閉合的輪廓上，基于這種思想,Funke等設(shè)計(jì)了一種基于輪廓構(gòu)建的邊界節(jié)點(diǎn)識(shí)別算法簡(jiǎn)稱為DHD[15]。DHD在構(gòu)建輪廓時(shí)首先選擇WSN的最大獨(dú)立集節(jié)點(diǎn)作為種子節(jié)點(diǎn)集合，然后選取最大獨(dú)立集中的每一個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn)(如圖5所示)，并收集該節(jié)點(diǎn)的各跳鄰居信息，并為不同跳的鄰居節(jié)點(diǎn)構(gòu)建環(huán)繞種子節(jié)點(diǎn)的輪廓，如果輪廓是閉合的則該層輪廓上不存在邊界節(jié)點(diǎn)，否則該層輪廓的兩個(gè)端點(diǎn)即為邊界節(jié)點(diǎn)，如圖5b中的節(jié)點(diǎn)v3和v4。

圖5　DHD邊界節(jié)點(diǎn)識(shí)別方法示意圖

優(yōu)點(diǎn)：不依賴節(jié)點(diǎn)位置信息，在大型網(wǎng)絡(luò)中的識(shí)別結(jié)果較優(yōu)。

缺點(diǎn)：該算法是一種集中和分布式融合的算法，在同質(zhì)網(wǎng)絡(luò)中會(huì)由于種子節(jié)點(diǎn)能量消耗大而引起其失效導(dǎo)致覆蓋空洞的產(chǎn)生且通信開(kāi)銷大；每一個(gè)種子節(jié)點(diǎn)都要建立數(shù)量不等的分層輪廓，因而識(shí)別過(guò)程時(shí)間消耗過(guò)大；魯棒性差，稀疏和稠密部署的網(wǎng)絡(luò)中識(shí)別錯(cuò)誤率都比較高且在不同網(wǎng)絡(luò)環(huán)境下識(shí)別精度變化起伏大；無(wú)法識(shí)別三角形等較小的覆蓋空洞。

2) 改進(jìn)的輪廓檢測(cè)算法

針對(duì)DHD算法存在的缺點(diǎn)，Chu和Ssu改進(jìn)了“輪廓”的構(gòu)建過(guò)程，同時(shí)基于單純復(fù)形理論提出一種分布式的邊界節(jié)點(diǎn)識(shí)別算法簡(jiǎn)稱為DBD[16]。如圖6a所示，S為待執(zhí)行DBD的節(jié)點(diǎn)，虛線框內(nèi)節(jié)點(diǎn)為S的2跳節(jié)點(diǎn)，DBD判斷節(jié)點(diǎn)S是否為邊界節(jié)點(diǎn)的過(guò)程是：選取節(jié)點(diǎn)t作為起始節(jié)點(diǎn)開(kāi)始構(gòu)建S的2跳“輪廓”，圖中不同形狀的節(jié)點(diǎn)分別代表節(jié)點(diǎn)t的不同跳鄰居，t節(jié)點(diǎn)依次在其不同跳鄰居中選取距其跳距離最近的節(jié)點(diǎn)，如圖6b所示，連接這些節(jié)點(diǎn)如圖6c所示，顯然節(jié)點(diǎn)S的輪廓不閉合，因而節(jié)點(diǎn)S為邊界節(jié)點(diǎn)。如果此時(shí)假設(shè)節(jié)點(diǎn)S的“輪廓”是閉合的，則DBD開(kāi)始對(duì)該“輪廓”區(qū)域進(jìn)行分解，根據(jù)單純復(fù)形理論，三角面是最小不可分割的面，如果“輪廓”區(qū)域能夠完全分解為由2跳和1跳鄰居節(jié)點(diǎn)構(gòu)成的三角面，則該節(jié)點(diǎn)是內(nèi)部節(jié)點(diǎn)，否則為邊界節(jié)點(diǎn)。

優(yōu)點(diǎn)：同DHD相比，該算法僅需被檢測(cè)節(jié)點(diǎn)的3跳鄰居信息，大幅度減少了通信開(kāi)銷；優(yōu)化了“輪廓”的構(gòu)建過(guò)程；完全分布式的算法設(shè)計(jì)可以使WSN中的每個(gè)節(jié)點(diǎn)都可以自主判斷是否為邊界節(jié)點(diǎn)。

缺點(diǎn)：“輪廓”三角面分解過(guò)程復(fù)雜度較高；無(wú)法識(shí)別三角形等較小的覆蓋空洞；特定環(huán)境下錯(cuò)誤識(shí)別率高。

圖6　DBD邊界節(jié)點(diǎn)識(shí)別方法示意圖

3) 基于割點(diǎn)和最近公共祖先的算法

Wang等在文獻(xiàn)[14]中提出一種基于拓?fù)涞倪吔缱R(shí)別算法簡(jiǎn)稱為BRT?；谧疃搪窂綐?、割點(diǎn)對(duì)和最近公共祖先思想，能夠直接識(shí)別覆蓋空洞和網(wǎng)絡(luò)外層邊界。具體過(guò)程是：BRT首先選取網(wǎng)絡(luò)中任意一節(jié)點(diǎn)(位于網(wǎng)絡(luò)邊緣的節(jié)點(diǎn)優(yōu)先)作為根節(jié)點(diǎn),利用泛洪算法生成網(wǎng)絡(luò)的最短路徑樹T。接著，在T中尋找具有最近公共祖先的割點(diǎn)對(duì)，如圖 7所示，節(jié)點(diǎn)p和q是具有共同公共祖先r的割點(diǎn)對(duì)，其中dp,r和dq,r需大于指定閾值δ，以p到r，q到r的路徑和邊pq構(gòu)成一個(gè)粗糙內(nèi)部邊界R，并通過(guò)不斷尋找p到r，q到r中間節(jié)點(diǎn)間的最短路徑對(duì)R進(jìn)行“修剪”獲得精確的覆蓋空洞邊界，最后通過(guò)尋找距離R最遠(yuǎn)的“極值”點(diǎn)作為WSN的外層邊界節(jié)點(diǎn)。

圖7　BRT算法示意圖

優(yōu)點(diǎn)：算法在節(jié)點(diǎn)平均連通度較低(≥7)的情況下也取得了較好的識(shí)別精度；能夠較精確地識(shí)別WSN覆蓋空洞和外層邊界，并能識(shí)別凹、凸和多孔的覆蓋空洞。

缺點(diǎn)：根節(jié)點(diǎn)的選取對(duì)識(shí)別結(jié)果影響較大；無(wú)法識(shí)別三角形等較小的覆蓋空洞；泛洪算法的大量使用加重了整個(gè)網(wǎng)絡(luò)的通信開(kāi)銷，增加了節(jié)點(diǎn)的能量消耗，影響了網(wǎng)絡(luò)的生命周期。

4) 結(jié)構(gòu)搜索法

Kr?ller在文獻(xiàn)[17]中利用QUDG模型提出一種稱為DBR的算法，DBR算法通過(guò)搜索WSN中的模式即“flower”結(jié)構(gòu)來(lái)識(shí)別內(nèi)部節(jié)點(diǎn)，通過(guò)不斷擴(kuò)張內(nèi)部節(jié)點(diǎn)從而達(dá)到識(shí)別邊界節(jié)點(diǎn)的目的。需要注意的是,DBR要求網(wǎng)絡(luò)平均節(jié)點(diǎn)度要大于20，這是“flower”結(jié)構(gòu)存在的必要條件。為克服DBR對(duì)節(jié)點(diǎn)連通度要求高的問(wèn)題，Sauth等在文獻(xiàn)[18]中改進(jìn)了“模式”的結(jié)構(gòu)，新的算法簡(jiǎn)稱為OBR，然而由于“模式”的限制，在稀疏網(wǎng)絡(luò)中仍存在較高的錯(cuò)誤率和漏檢率。

優(yōu)點(diǎn)：該算法不需要考慮節(jié)點(diǎn)部署模型和位置信息。

缺點(diǎn)：該算法節(jié)點(diǎn)連通度要求高；無(wú)法識(shí)別三角形等較小的覆蓋空洞；不適用于稀疏和小規(guī)模網(wǎng)絡(luò)。

5) 基于跳信息的邊界節(jié)點(diǎn)識(shí)別方法

在所述及的基于拓?fù)浞椒ǖ倪吔绻?jié)點(diǎn)識(shí)別算法中，通信開(kāi)銷過(guò)大是一個(gè)普遍存在的問(wèn)題，針對(duì)該問(wèn)題Khan等提出一種基于節(jié)點(diǎn)之間跳距離的邊界節(jié)點(diǎn)識(shí)別算法簡(jiǎn)稱為HBH[19]，通過(guò)該算法WSN中的每一個(gè)節(jié)點(diǎn)都能自主判斷是否為邊界節(jié)點(diǎn)。該算法仍然采用了“閉環(huán)”思想作為節(jié)點(diǎn)判別自己是否為邊界節(jié)點(diǎn)的依據(jù)。區(qū)別在于其“閉環(huán)”路徑的構(gòu)造方法通信量小。HBH構(gòu)建“閉環(huán)”路徑的具體方法是，以被檢測(cè)節(jié)點(diǎn)的任意一個(gè)2跳鄰居節(jié)點(diǎn)作為起始節(jié)點(diǎn)，如圖 8所示，通過(guò)按序持續(xù)搜索“擴(kuò)展節(jié)點(diǎn)”避免了大量的廣播帶來(lái)的通信代價(jià)過(guò)高的問(wèn)題降低了網(wǎng)絡(luò)的通信成本，延長(zhǎng)了網(wǎng)絡(luò)生命周期。

優(yōu)點(diǎn)：該算法為分布式算法，WSN中每個(gè)節(jié)點(diǎn)能自動(dòng)識(shí)別自己是否為邊界節(jié)點(diǎn)；相比其他拓?fù)渌惴?，在鄰居信息收集和“閉環(huán)”路徑構(gòu)建過(guò)程都減少了通信開(kāi)銷。

缺點(diǎn)：在稀疏網(wǎng)絡(luò)中存在錯(cuò)誤節(jié)點(diǎn)識(shí)別率高的問(wèn)題；無(wú)法識(shí)別三角形等較小的覆蓋空洞；沒(méi)有給出明確的覆蓋空洞節(jié)點(diǎn)聚類方法。

圖8　HBH算法示意圖

本節(jié)基于節(jié)點(diǎn)的可用信息對(duì)當(dāng)前主要的邊界節(jié)點(diǎn)

識(shí)別算法進(jìn)行了分類、總結(jié)和對(duì)比，結(jié)果如表1所示。從中可以看出各類算法都有各自的優(yōu)點(diǎn)，但也存在一些亟待改進(jìn)的地方。基于計(jì)算幾何的方法雖然識(shí)別精度高,算法設(shè)計(jì)簡(jiǎn)單，但是由于要求配置定位設(shè)備，不僅加大了部署成本,而且增加了能量消耗。基于統(tǒng)計(jì)的識(shí)別方法不需要節(jié)點(diǎn)知道其位置信息，但是要求節(jié)點(diǎn)部署必須服從一定的概率分布模型，這提高了部署的難度，而且其極高的節(jié)點(diǎn)連通度要求也限制了其實(shí)際應(yīng)用范圍。基于拓?fù)涞姆椒ú恍枰?jié)點(diǎn)位置信息，而且在較低節(jié)點(diǎn)連通度環(huán)境下也取得了很好的識(shí)別結(jié)果，但其問(wèn)題是通信開(kāi)銷過(guò)大。

表1邊界節(jié)點(diǎn)識(shí)別方法對(duì)比分析

檢測(cè)方法核心思想優(yōu)點(diǎn)缺點(diǎn)涉及文獻(xiàn)計(jì)算幾何方法WSN每個(gè)節(jié)點(diǎn)都知道其位置信息,利用節(jié)點(diǎn)間的幾何特性識(shí)別WSN中的邊界節(jié)點(diǎn)1)識(shí)別方法簡(jiǎn)單,計(jì)算容易2)僅需1跳鄰居即可識(shí)別1)需配備GPS等定位裝置,部署成本高2)容易受環(huán)境干擾3)能量消耗大[3-4,6-9,11]統(tǒng)計(jì)方法假定WSN中的節(jié)點(diǎn)服從某種概率分布,且WSN內(nèi)部節(jié)點(diǎn)的節(jié)點(diǎn)度明顯高于邊界節(jié)點(diǎn)1)不需要配備GPS2)不需要節(jié)點(diǎn)位置信息1)節(jié)點(diǎn)連通度要求高2)節(jié)點(diǎn)必須服從統(tǒng)一概率分布3)要求網(wǎng)絡(luò)密度大[12-13]拓?fù)浞椒ɡ霉?jié)點(diǎn)之間的連接信息和網(wǎng)絡(luò)拓?fù)涮匦詫?shí)現(xiàn)邊界節(jié)點(diǎn)的識(shí)別1)不需要假設(shè)節(jié)點(diǎn)服從某種概率分布2)不需要節(jié)點(diǎn)位置信息3)節(jié)點(diǎn)度要求低1)通信開(kāi)銷大2)稀疏網(wǎng)絡(luò)識(shí)別精度低3)至少需要2跳鄰居[14-19]

2.3基于計(jì)算模型的分類方法

2.3.1集中式邊界節(jié)點(diǎn)識(shí)別算法

集中式算法是指邊界節(jié)點(diǎn)識(shí)別算法的執(zhí)行主要依賴于一個(gè)或多個(gè)具有核心功能的節(jié)點(diǎn)，除這些核心節(jié)點(diǎn)外網(wǎng)絡(luò)中的其他節(jié)點(diǎn)不能判斷自己是否為邊界節(jié)點(diǎn)。文獻(xiàn)[15]中，網(wǎng)絡(luò)中的節(jié)點(diǎn)并不能獨(dú)立判斷自己是否為邊界節(jié)點(diǎn)，而是依賴于網(wǎng)絡(luò)的最大獨(dú)立集成員節(jié)點(diǎn)。此外，Grist和Muhammed在文獻(xiàn)[20]中也提出一種基于代數(shù)拓?fù)淇臻g理論的集中式邊界節(jié)點(diǎn)識(shí)別算法，但是其復(fù)雜度過(guò)高。

優(yōu)點(diǎn)：集中式能夠優(yōu)化網(wǎng)絡(luò)的全局設(shè)計(jì)，使協(xié)議設(shè)計(jì)最優(yōu)化。

缺點(diǎn)：由于WSN特殊的結(jié)構(gòu)屬性，其有限的存儲(chǔ)和數(shù)據(jù)處理能力并不適合數(shù)據(jù)的集中收集和處理，尤其是在介質(zhì)均勻的WSN；由于集中式算法過(guò)于依賴中心節(jié)點(diǎn)，當(dāng)中心節(jié)點(diǎn)出現(xiàn)故障時(shí)很容易導(dǎo)致整個(gè)網(wǎng)絡(luò)功能的中斷和失效；集中式算法需要將數(shù)據(jù)聚合到中心節(jié)點(diǎn)執(zhí)行，因而會(huì)增大通信開(kāi)銷，導(dǎo)致節(jié)點(diǎn)能量消耗增大，進(jìn)而影響整個(gè)網(wǎng)絡(luò)的生存周期。

2.3.2分布式算法

分布式邊界節(jié)點(diǎn)識(shí)別算法是指WSN中的多個(gè)節(jié)點(diǎn)通過(guò)相互協(xié)作實(shí)現(xiàn)邊界節(jié)點(diǎn)的檢測(cè)與識(shí)別，通常表現(xiàn)為WSN中的每一個(gè)節(jié)點(diǎn)通過(guò)收集其跳鄰居信息，然后通過(guò)基于計(jì)算幾何、統(tǒng)計(jì)或拓?fù)涞确椒z測(cè)自己是否為邊界節(jié)點(diǎn)。如文獻(xiàn)[3-4，6-9，11-14，16-19]中提出的算法都屬于分布式算法。

優(yōu)點(diǎn)：分布式算法可以依賴WSN的局部信息實(shí)現(xiàn)邊界節(jié)點(diǎn)的識(shí)別，網(wǎng)絡(luò)中部分節(jié)點(diǎn)失效不會(huì)影響整個(gè)網(wǎng)絡(luò)的功能。

缺點(diǎn)：相較集中式算法，分布式算法設(shè)計(jì)要復(fù)雜。

2.4基于“閉環(huán)” 的分類方法

結(jié)合前文所述，“閉環(huán)”策略是邊界節(jié)點(diǎn)識(shí)別算法中使用頻率極高的技術(shù)，本文據(jù)此將邊界節(jié)點(diǎn)識(shí)別算法分為基于“閉環(huán)”的邊界節(jié)點(diǎn)識(shí)別算法，如文獻(xiàn)[3-4，6-8，15-16，19]和非“閉環(huán)”的邊界節(jié)點(diǎn)識(shí)別算法，如文獻(xiàn)[9，11-14，17-18，20]。

優(yōu)點(diǎn)：基于“閉環(huán)”的算法設(shè)計(jì)簡(jiǎn)單、復(fù)雜度低，尤其基于幾何結(jié)構(gòu)的“閉環(huán)”算法僅需1跳鄰居節(jié)點(diǎn)即可識(shí)別被檢測(cè)節(jié)點(diǎn)是否為邊界節(jié)點(diǎn)，在不同的應(yīng)用場(chǎng)景中均取得較好的識(shí)別效果。

缺點(diǎn)：基于“閉環(huán)”的邊界節(jié)點(diǎn)識(shí)別算法雖然設(shè)計(jì)簡(jiǎn)單，但在實(shí)際實(shí)施中也面臨巨大的挑戰(zhàn)，尤其是基于拓?fù)浞椒ǖ摹伴]環(huán)”算法，特定條件下是一個(gè)完全NP難問(wèn)題，如圖9a和圖9b所示，節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)和構(gòu)成了一個(gè)“閉環(huán)”，但算法由于極難區(qū)分圖9a和圖9b兩種情況而將識(shí)別為內(nèi)部節(jié)點(diǎn)，造成錯(cuò)誤識(shí)別。

圖9　閉環(huán)錯(cuò)誤識(shí)別原理圖

3　邊界節(jié)點(diǎn)識(shí)別算法比較及存在的問(wèn)題分析

3.1邊界節(jié)點(diǎn)識(shí)別算法比較

表2從識(shí)別精度、節(jié)點(diǎn)度、算法模型、節(jié)點(diǎn)信息、能量有效性、通信開(kāi)銷、復(fù)雜度、傳感和通信模型及是否采用閉環(huán)策略9個(gè)維度對(duì)本文綜述的算法進(jìn)行了對(duì)比和總結(jié)，從中可以全面認(rèn)識(shí)當(dāng)前主要算法的差異和特點(diǎn)。

3.2存在的問(wèn)題

雖然學(xué)者們針對(duì)不同的應(yīng)用場(chǎng)景提出多種類型的邊界節(jié)點(diǎn)識(shí)別算法，但通過(guò)前文的分析可以發(fā)現(xiàn)其仍然存在以下問(wèn)題，亟待解決。

1)傳感和通信模型對(duì)邊界節(jié)點(diǎn)識(shí)別的影響。本文所述的邊界節(jié)點(diǎn)識(shí)別算法中，傳感和通信模型基本遵循圓盤覆蓋模型，然而實(shí)際應(yīng)用中WSN節(jié)點(diǎn)受其應(yīng)用環(huán)境(如地形阻擋)的影響，其傳感和通信模型很難服從理想的圓盤模型，雖然文獻(xiàn)[14]強(qiáng)調(diào)不需要完全服從圓盤模型，但其并未作出具體驗(yàn)證和評(píng)估。因而，這是未來(lái)研究中一個(gè)必須面對(duì)的問(wèn)題。

表2邊界節(jié)點(diǎn)識(shí)別算法比較

算法識(shí)別精度節(jié)點(diǎn)度算法模型節(jié)點(diǎn)信息類型能量有效性通信開(kāi)銷復(fù)雜度傳感和通信模型閉環(huán)策略DPDHighLowDistributedGeographicalMediumLowLowUDGYESPDHighLowDistributedGeographicalLowLowLowUDGYESEBDHighLowDistributedGeographicalLowLowLowUDGYESCGNHighLowDistributedGeographicalMediumLowLowUDGYESBRCHighLowDistributedGeographicalMediumLowLowUDGYESCDCHHighLowDistributedGeographicalMediumLowLowUDGNOCHBHighLowDistributedGeographicalMediumLowLowUDGNONTRLowStrongDistributedStatisticalMediumHighLowUDGNORSCLowStrongDistributedStatisticalMediumHighLowUDGNODHDHighMediumCentralizedTopologicalMediumMediumLowUDGYESDBDHighMediumDistributedTopologicalMediumMediumLowUDGYESBRTHighLowDistributedTopologicalLowHighMediumNon-UDGNODBRMediumHighDistributedTopologicalLowHighHighQUDGNOOBRMediumMediumDistributedTopologicalLowHighHighd-QUDGNOHBHHighMediumDistributedTopologicalLowLowMediumUDGYESCHDMediumMediumCentralizedTopologicalLowHighHighUDGNO

2)應(yīng)用領(lǐng)域問(wèn)題。目前邊界節(jié)點(diǎn)識(shí)別的研究中，WSN部署環(huán)境主要假設(shè)為一個(gè)在二維平面環(huán)境，然而WSN已被大量應(yīng)用于建筑物、水下和地下等三維環(huán)境中，針對(duì)三維環(huán)境的邊界節(jié)點(diǎn)識(shí)別技術(shù)目前研究較少，僅在文獻(xiàn)[21]等極少數(shù)文獻(xiàn)中針對(duì)該問(wèn)題進(jìn)行了討論，因而三維環(huán)境中的邊界節(jié)點(diǎn)識(shí)別是一個(gè)必須解決的問(wèn)題。

3)動(dòng)態(tài)拓?fù)浜鸵苿?dòng)性問(wèn)題。綜述的文獻(xiàn)中，大多是基于節(jié)點(diǎn)靜止的環(huán)境進(jìn)行算法設(shè)計(jì)的，然而實(shí)際的無(wú)線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是一個(gè)動(dòng)態(tài)變化的過(guò)程，這是由其結(jié)構(gòu)特性決定的，同時(shí)為了彌補(bǔ)WSN隨機(jī)部署的缺陷在一些應(yīng)用中通常采用移動(dòng)節(jié)點(diǎn)對(duì)WSN中覆蓋空洞進(jìn)行修補(bǔ)，然而在目前的文獻(xiàn)中大多數(shù)沒(méi)有對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的動(dòng)態(tài)變化進(jìn)行考慮和優(yōu)化設(shè)計(jì)，這也是實(shí)際應(yīng)用必須解決的一個(gè)主要問(wèn)題。

4)基于邊界節(jié)點(diǎn)識(shí)別的覆蓋空洞識(shí)別和修補(bǔ)技術(shù)。邊界節(jié)點(diǎn)一個(gè)主要的應(yīng)用是為覆蓋空洞的識(shí)別提供支撐，然而綜述的文獻(xiàn)中除文獻(xiàn)[14]外，其他文獻(xiàn)均未給出明確的覆蓋空洞識(shí)別算法。而且在一個(gè)大型WSN中可能存在多個(gè)覆蓋空洞，因而如何識(shí)別復(fù)雜環(huán)境下的覆蓋空洞并對(duì)其進(jìn)行修補(bǔ)是一個(gè)亟待解決的問(wèn)題。

4　小結(jié)

本文綜述了無(wú)線傳感器網(wǎng)絡(luò)邊界節(jié)點(diǎn)識(shí)別技術(shù)的研究現(xiàn)狀，通過(guò)節(jié)點(diǎn)識(shí)別過(guò)程中采用的節(jié)點(diǎn)可用信息、算法模型和技術(shù)策略對(duì)當(dāng)前主要的研究方法進(jìn)行了分類，并描述了各算法的技術(shù)路線和適用范圍，對(duì)各算法的優(yōu)、缺點(diǎn)進(jìn)行了對(duì)比、分析和總結(jié)。最后，本文對(duì)當(dāng)前該領(lǐng)域亟待解決的問(wèn)題進(jìn)行了探討，對(duì)未來(lái)的研究方向進(jìn)行了展望。

[1]SMARAGDAKISG，MATTAI，BESTAVROSA.SEP：astableelectionprotocolforclusteredheterogeneouswirelesssensornetworks[EB/OL].[2016-01-10].https://www.researchgate.net/publication/228885310_SEP_A_Stable_Election_Protocol_for_Clustered_Heterogeneous_Wireless_Sensor_Networks.

[2]HEINZELMANWB，CHANDRAKASANAP，BALAKRISHNANH.Anapplication-specificprotocolarchitectureforwirelessmicrosensornetworks[J].IEEEtransactionsonwirelesscommunications，2002，1(4)：660-670.

[3]MARTINCICF，SCHWIEBERTL.Distributedperimeterdetectioninwirelesssensornetworks[EB/OL].[2016-1-10].http://newslab.cs.wayne.edu/perimeter.pdf.

[4]KHEDRAM，OSAMYW，AGRAWALDP.Perimeterdiscoveryinwirelesssensornetworks[J].Journalofparallelanddistributedcomputing，2009，69(11)：922-929.

[5]HUANGCF，TSENGYC.Thecoverageprobleminawirelesssensornetwork[J].Mobilenetworksandapplications，2005，10(4)：519-528.

[6]陳成濤，孫燕. 高效的無(wú)線傳感器網(wǎng)絡(luò)邊緣檢測(cè)算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2011，32(9)：2984-2988.

[7]DEOGUNJS，DASS，HAMZAHS，etal.Analgorithmforboundarydiscoveryinwirelesssensornetworks[C]//InHighPerformanceComputing-HiPC2005.[S.l.]：SpringerBerlinHeidelberg，2005：343-352.

[8]SIMEKM，MORAVEKP，KOMOSNYD，etal.Distributedrecognitionofreferencenodesforwirelesssensornetworklocalization[J].Radioengineering，2012，21(1)：89-98.

[9]MAHC，KUMARSP，CHENYW.Computationalgeometrybaseddistributedcoverageholedetectionprotocolforthewirelesssensornetworks[J].Journalofnetworkandcomputerapplications，2011，34(5)：1743-1756.

[10]LIXY，CALINESCUG，WANPJ，etal.Localizeddelaunaytriangulationwithapplicationinadhocwirelessnetworks[J].IEEEtransactionsonparallelanddistributedsystems，2003，14(10)：1035-1047.

[11]LIW，ZHANGW.Coverageholeandboundarynodesdetectioninwirelesssensornetworks[J].Journalofnetworkandcomputerapplications，2015，48：35-43.

[12]FEKETESP，KROLLERA，PFISTERERD，etal.Neighborhood-basedtopologyrecognitioninsensornetworks[C]//AlgorithmicAspectsofWirelessSensorNetworks. [S.l.]：Springer，2004：123-136.

[13]FEKETESP，KAUFMANNM，KROLLERA，etal.Anewapproachforboundaryrecognitioningeometricsensornetworks[C]//Proc. 17thCanadianConferenceonComputationalGeometry. [S.l.]：arXiv，2005：82-85.

[14]WANGY，GAOJ，MITCHELLJS.Boundaryrecognitioninsensornetworksbytopologicalmethods[C]//Proc. 12thAnnualInternationalConferenceonMobileComputingandNetworking. [S.l.]：ACM，2006：122-133.

[15]FUNKES.Topologicalholedetectioninwirelesssensornetworksanditsapplications[C]//Proc. 2005JointWorkshoponFoundationsofMobileComputing.NewYork，NY，USA：ACM，2005：44-53.

[16]CHUWC，SSUKF.Location-freeboundarydetectioninmobilewirelesssensornetworkswithadistributedapproach[J].Computernetworks，2014，70(10)：96-112.

[17]KR?LLERA，F(xiàn)EKETESP，PFISTERERD，etal.Deterministicboundaryrecognitionandtopologyextractionforlargesensornetworks[C]//Proc.SeventeenthAnnualACM-SIAMSymposiumonDiscreteAlgorithm. [S.l.]：SocietyforIndustrialandAppliedMathematics，2006：1000-1009.

[18]SAUKHO，SAUTERR，GAUGERM，etal.Onboundaryrecognitionwithoutlocationinformationinwirelesssensornetworks[J].ACMtransactionsonsensornetworks(TOSN)，2010，6(3)：1-35.

[19]KHANIM，JABEURN，ZEADALLYS，etal.Hop-basedapproachforholesandboundarydetectioninwirelesssensornetworks[J].IETwirelesssensorsystems，2012，2(4)：328-337.

[20]GHRISTR，MUHAMMADA.Coverageandhole-detectioninsensornetworksviahomology[C]//Proc. 4thinternationalsymposiumonInformationprocessinginsensornetworks. [S.l.]：IEEE，2005：254-260.

[21]ZHOUH，WUH，JINM.Arobustboundarydetectionalgorithmbasedonconnectivityonlyfor3Dwirelesssensornetworks[C]//Proc.INFOCOM.[S.l.]：IEEE，2012：1602-1610.

趙利輝(1979— )，博士生，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)；

劉文怡(1970— )，教授，博士生導(dǎo)師，主要研究方向?yàn)闇y(cè)試測(cè)量技術(shù)及儀器、無(wú)線傳感器等；

張斌(1979— )，博士生，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)；

譚秋林(1979— )，教授，博士生導(dǎo)師，主要研究方向?yàn)榧t外氣體傳感技術(shù)、惡劣環(huán)境下無(wú)線無(wú)源傳感技術(shù)。

責(zé)任編輯：許盈

Surveyonboundarynoderecognitioninwirelesssensornetwork

ZHAOLihuia,b,LIUWenyia,b,ZHANGBina,TANQiulina,b

(a. National Key Laboratory for Electronic Measurement Technology；b. Key Laboratory of Instrumentation Science & Dynamic Measurement of Ministry of Education, North University of China, Taiyuan 030051, China)

Identifyingboundarynodesisfundamentalintheresearchofwirelesssensornetworks.Itplaysacriticalroleinidentifyingcoverageholes,laysafoundationforoptimizingnetworkcoverageandguaranteesdatatransmission.Inthispaper,thestatequoofthealgorithmsofidentifyingboundarynodesarereviewed,methodsofcategorizingthealgorithmsbasedontheavailableinformationofnodesandtherelevantstrategiesoftechnologyarepresented,andtheadvantagesanddisadvantagesofthedifferentalgorithmsarecomparativelyanalyzed.Furthermore,theupcomingworkisproposed.

wirelesssensornetworks;boundarynode;coverageholes;survey

TN915

ADOI：10.16280/j.videoe.2016.08.012

國(guó)家自然科學(xué)基金項(xiàng)目(51275491)；國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目(61471324)

2016-02-25

文獻(xiàn)引用格式：趙利輝，劉文怡，張斌，等. 無(wú)線傳感器網(wǎng)絡(luò)邊界節(jié)點(diǎn)識(shí)別研究進(jìn)展綜述[J].電視技術(shù)，2016，40(8)：62-70.

ZHAOLH，LIUWY，ZHANGB，etal.Surveyonboundarynoderecognitioninwirelesssensornetwork[J].Videoengineering，2016，40(8)：62-70.