基于幾何方法的分布式無(wú)線傳感器網(wǎng)絡(luò)邊界節(jié)點(diǎn)識(shí)別算法研究*

趙利輝，楊秋翔

(中北大學(xué) 軟件學(xué)院，山西 太原 030051)

0 引 言

無(wú)線傳感器節(jié)點(diǎn)具有成本低、功耗小，能夠感知聲、光、震動(dòng)和輻射等多種事件的功能，并且能夠以無(wú)線通信的方式自組織形成多跳網(wǎng)絡(luò)[1]，由眾多無(wú)線傳感器節(jié)點(diǎn)構(gòu)成的多跳網(wǎng)絡(luò)稱為無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，簡(jiǎn)稱WSN). WSN在執(zhí)行惡劣環(huán)境下的目標(biāo)監(jiān)測(cè)任務(wù)方面展現(xiàn)出獨(dú)有的優(yōu)勢(shì)，例如在軍事領(lǐng)域的戰(zhàn)場(chǎng)態(tài)勢(shì)監(jiān)測(cè)、無(wú)人值守環(huán)境下的邊境越境監(jiān)測(cè)、建筑物結(jié)構(gòu)安全監(jiān)測(cè)、?；繁O(jiān)測(cè)等方面都發(fā)揮了重要作用.

大規(guī)模WSN通常基于機(jī)載平臺(tái)以拋灑方式進(jìn)行部署，在此過(guò)程中，極易遭受各種外力作用造成節(jié)點(diǎn)布撒不均勻、外力撞擊破壞和節(jié)點(diǎn)能量耗竭導(dǎo)致的節(jié)點(diǎn)失效，從而使WSN無(wú)法完整地感知整個(gè)監(jiān)測(cè)區(qū)域內(nèi)事件的發(fā)生，通常將目標(biāo)區(qū)域中無(wú)法由傳感器節(jié)點(diǎn)感知的監(jiān)測(cè)區(qū)域稱為網(wǎng)絡(luò)覆蓋空洞. WSN固有的特性使得覆蓋空洞的出現(xiàn)不可避免，一方面覆蓋空洞降低了WSN對(duì)目標(biāo)監(jiān)測(cè)區(qū)域的覆蓋能力，另一方面覆蓋空洞會(huì)引發(fā)WSN中監(jiān)測(cè)數(shù)據(jù)路由路障、導(dǎo)致節(jié)點(diǎn)負(fù)載不均衡等一系列問(wèn)題，甚至使更多節(jié)點(diǎn)失效形成更大規(guī)模的覆蓋空洞，從而嚴(yán)重影響整個(gè)網(wǎng)絡(luò)的生命周期和服務(wù)質(zhì)量.

由于WSN在軍事和民用領(lǐng)域不斷延伸的應(yīng)用趨勢(shì)和特定場(chǎng)景下的無(wú)可替代性，研究能夠長(zhǎng)時(shí)、穩(wěn)定和可靠地執(zhí)行值守任務(wù)的WSN成為該領(lǐng)域的重要問(wèn)題. 識(shí)別WSN中的邊界節(jié)點(diǎn)是研究覆蓋空洞的關(guān)鍵問(wèn)題，對(duì)其研究不僅可以深入刻畫(huà)覆蓋空洞的形狀、規(guī)模而且可以提高WSN數(shù)據(jù)路由效率，保障數(shù)據(jù)路由安全. 依據(jù)國(guó)內(nèi)外學(xué)者采用的邊界節(jié)點(diǎn)識(shí)別技術(shù)的不同，邊界節(jié)點(diǎn)識(shí)別算法可以歸類為： ① 基于幾何的邊界節(jié)點(diǎn)識(shí)別方法； ② 基于統(tǒng)計(jì)的邊界節(jié)點(diǎn)識(shí)別方法； ③ 基于網(wǎng)絡(luò)結(jié)構(gòu)拓?fù)涞倪吔绻?jié)點(diǎn)識(shí)別方法.

由于WSN中邊界節(jié)點(diǎn)的感知區(qū)域通常不能被其它節(jié)點(diǎn)的感知區(qū)域覆蓋，利用這一特性學(xué)者們研究出了基于幾何和網(wǎng)絡(luò)拓?fù)涞倪吔绻?jié)點(diǎn)識(shí)別算法. 不同的學(xué)者分別使用三角形環(huán)繞、多邊形環(huán)繞、通過(guò)抽取網(wǎng)絡(luò)的最大獨(dú)立集構(gòu)建節(jié)點(diǎn)的多層次閉合環(huán)繞多邊形的方式判斷WSN中的節(jié)點(diǎn)是否為邊界節(jié)點(diǎn).

Khedr等[2]提出一種通過(guò)搜索WSN中每個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)是否能形成閉合“周界”的算法來(lái)判斷節(jié)點(diǎn)是否為邊界節(jié)點(diǎn)，該算法簡(jiǎn)稱為PD算法. PD算法基于Barycentric坐標(biāo)技術(shù)，通過(guò)檢測(cè)分布于坐標(biāo)系四個(gè)象區(qū)之間待識(shí)別節(jié)點(diǎn)的鄰居節(jié)點(diǎn)之間的連通性判斷節(jié)點(diǎn)是否為邊界節(jié)點(diǎn). Simek[3]和Deogun[4]等利用WSN中節(jié)點(diǎn)的一跳或多跳鄰居是否能構(gòu)成閉合三角形并將其環(huán)繞在內(nèi)實(shí)現(xiàn)邊界節(jié)點(diǎn)的判別，兩種算法的區(qū)別在于Simek改進(jìn)了三角形構(gòu)建方法，加速了三角形構(gòu)建速度，也提高了識(shí)別的精度. Ma[5]則利用三角形外接圓特性實(shí)現(xiàn)了邊界節(jié)點(diǎn)識(shí)別算法. Massinissa Saoudi[6]等基于最小極角提出一種稱為D-LPCN的邊界節(jié)點(diǎn)識(shí)別算法. Khder[7]等通過(guò)改進(jìn)文獻(xiàn)[8]的算法提出一種通過(guò)計(jì)算節(jié)點(diǎn)鄰居感知區(qū)域交叉點(diǎn)的方式進(jìn)行邊界節(jié)點(diǎn)識(shí)別的算法. 通常情況下，邊界節(jié)點(diǎn)的度低于網(wǎng)絡(luò)中非邊界節(jié)點(diǎn)的度，F(xiàn)ekete[9]利用該特性提出一種“限制壓力中心”算法用于識(shí)別邊界節(jié)點(diǎn)，該算法僅適用于網(wǎng)絡(luò)密度大于100的情況，當(dāng)前應(yīng)用場(chǎng)景下的WSN很難達(dá)到如此高的節(jié)點(diǎn)密度. Wang等[10]利用最短路徑樹(shù)、割點(diǎn)對(duì)和最近公共祖先提出一種基于拓?fù)涞淖R(shí)別方法，該算法的優(yōu)點(diǎn)是網(wǎng)絡(luò)密度較小(≥7)的情況下也可以識(shí)別邊界節(jié)點(diǎn)，缺點(diǎn)是根節(jié)點(diǎn)選擇困難，識(shí)別過(guò)程多次使用泛洪算法導(dǎo)致節(jié)點(diǎn)能量消耗較大，且無(wú)法識(shí)別三角形覆蓋空洞. Sauth[11]和Khan[12]等分別利用改進(jìn)的“花”結(jié)構(gòu)的模式搜索和跳信息實(shí)現(xiàn)邊界節(jié)點(diǎn)的識(shí)別. 邊界節(jié)點(diǎn)的一個(gè)本質(zhì)特征是其不能與其鄰居節(jié)點(diǎn)構(gòu)成封閉的環(huán)狀網(wǎng)絡(luò)，也不能由其鄰居構(gòu)成封閉環(huán)狀網(wǎng)絡(luò)包圍，利用上述特征，F(xiàn)unke等提出了一種基于節(jié)點(diǎn)閉合輪廓識(shí)別的邊界節(jié)點(diǎn)識(shí)別算法，簡(jiǎn)稱DHD[13]. 上述算法共同的問(wèn)題是算法僅在網(wǎng)絡(luò)節(jié)點(diǎn)密度大于20的情況下才可使用，否則節(jié)點(diǎn)識(shí)別精度過(guò)低且不能識(shí)別較小空洞邊緣的節(jié)點(diǎn)，難以適應(yīng)稀疏網(wǎng)絡(luò)的需求.

本文在總結(jié)近幾年WSN網(wǎng)絡(luò)覆蓋與邊界節(jié)點(diǎn)識(shí)別研究成果的基礎(chǔ)上，詳細(xì)分析了WSN網(wǎng)絡(luò)覆蓋空同的結(jié)構(gòu)特征，針對(duì)刻畫(huà)覆蓋空洞結(jié)構(gòu)的網(wǎng)絡(luò)邊界節(jié)點(diǎn)識(shí)別問(wèn)題進(jìn)行了深入的研究、分析和仿真驗(yàn)證. 為克服傳統(tǒng)識(shí)別方法中對(duì)網(wǎng)絡(luò)密度要求高、識(shí)別精度低的問(wèn)題提出一種基于幾何技術(shù)的邊界節(jié)點(diǎn)識(shí)別方法，該方法具有復(fù)雜度低、網(wǎng)絡(luò)密度要求低、識(shí)別精度高、泛化能力好的特點(diǎn)，同時(shí)本文也是對(duì)前期工作[14]的一次改進(jìn).

1 系統(tǒng)模型與定義

1.1 定義與符號(hào)

定義 1 邊界節(jié)點(diǎn)： 如圖 1 所示為一個(gè)WSN，網(wǎng)絡(luò)最外層節(jié)點(diǎn)11～15，17～26一起構(gòu)成了環(huán)繞監(jiān)測(cè)區(qū)域的外圍邊界，本文將上述節(jié)點(diǎn)稱為邊界節(jié)點(diǎn)，而節(jié)點(diǎn)1, 2, 3, 4, 5, 6, 7, 8和節(jié)點(diǎn)4, 5, 25, 26所環(huán)繞的陰影監(jiān)測(cè)區(qū)域由于沒(méi)有節(jié)點(diǎn)能夠感知覆蓋因而形成覆蓋空洞，這些環(huán)繞覆蓋空洞的節(jié)點(diǎn)本文也稱為邊界節(jié)點(diǎn).

定義 2 參考節(jié)點(diǎn)： WSN中執(zhí)行邊界節(jié)點(diǎn)識(shí)別算法的節(jié)點(diǎn)，如圖 2 中節(jié)點(diǎn)so.

定義 3 內(nèi)部節(jié)點(diǎn)： 無(wú)線傳感器網(wǎng)絡(luò)中除邊界節(jié)點(diǎn)之外的節(jié)點(diǎn)稱為內(nèi)部節(jié)點(diǎn).

圖 1 邊界節(jié)點(diǎn)、覆蓋空洞示意圖Fig.1 Illustration of boundary node and coverage hole

圖 2 定義說(shuō)明Fig.2 Illustration of definition

(1)

文中用到的其它符號(hào)如表 1 所示.

表 1 符號(hào)說(shuō)明表Tab.1 Symbol description

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

(2)

2 基于幾何方法的分布式邊界節(jié)點(diǎn)識(shí)別算法

識(shí)別邊界節(jié)點(diǎn)是檢測(cè)和修復(fù)無(wú)線傳感器網(wǎng)絡(luò)覆蓋空洞的關(guān)鍵問(wèn)題，已有方法存在的主要問(wèn)題是： ① 需要節(jié)點(diǎn)的精確節(jié)點(diǎn)位置信息，② 邊界節(jié)點(diǎn)正確識(shí)別率低，③ 識(shí)別過(guò)程能量消耗大. 針對(duì)上述問(wèn)題，本文提出一種自適應(yīng)的基于幾何技術(shù)的分布式無(wú)線傳感器網(wǎng)絡(luò)邊界節(jié)點(diǎn)識(shí)別算法(A distributed geometric scheme for detecting boundary nodes in the wireless sensor networks，簡(jiǎn)稱DGSD).

2.1 算法描述

DGSD算法可描述為：

輸入：G=(V,E)；

輸出： 邊界節(jié)點(diǎn)集；

步驟1： 收集節(jié)點(diǎn)的一跳和二跳鄰居信息，該過(guò)程通過(guò)構(gòu)建節(jié)點(diǎn)的無(wú)向連通圖G=(V,E)，由節(jié)點(diǎn)向其鄰居節(jié)點(diǎn)發(fā)送Hello報(bào)文收集和維護(hù)其鄰居信息表.

步驟2： 參考節(jié)點(diǎn)根據(jù)定義2構(gòu)建LCCS.

步驟3： 參考節(jié)點(diǎn)利用LCCS和公式(1)收集其一跳和二跳鄰居節(jié)點(diǎn)，并計(jì)算相應(yīng)的絕對(duì)角.

步驟4： 參考節(jié)點(diǎn)以絕對(duì)角升序規(guī)則排序其鄰居節(jié)點(diǎn).

步驟5： 如果節(jié)點(diǎn)存在絕對(duì)角相同的鄰居節(jié)點(diǎn)，則保留其鄰居表中距離其最近的鄰居節(jié)點(diǎn).

步驟7： 輸出邊界節(jié)點(diǎn)集.

2.2 算法理論分析

定理1 如果一個(gè)節(jié)點(diǎn)滿足條件deg(so)≤2，則該節(jié)點(diǎn)必為邊界節(jié)點(diǎn).

(3)

(4)

(5)

引理1 給定參考節(jié)點(diǎn)so，對(duì)于so的一跳和二跳鄰居集合{sk|sk(k=1,…,n)}，如果節(jié)點(diǎn)so滿足下列任意條件，則該節(jié)點(diǎn)為無(wú)線傳感器網(wǎng)絡(luò)中的一個(gè)邊界節(jié)點(diǎn)：

1) max(∠abs(sk))≤π,

2) min(∠abs(sk))>π,

圖 3 定理1證明示意圖Fig.3 Diagram of the demonstration of theorem 1

圖 4 推論 1 證明示意圖Fig.4 Diagram of the demonstration of lemma 1

引理2 給定參考節(jié)點(diǎn)，假設(shè)的感知區(qū)域邊界能被他的鄰居節(jié)點(diǎn)完全覆蓋，但其鄰居節(jié)點(diǎn)之間不能形成一個(gè)閉合環(huán)路，則該節(jié)點(diǎn)為邊界節(jié)點(diǎn).

證明如圖 5 所示，雖然B(so)能夠由其鄰居節(jié)點(diǎn)集{s1,s2,…,s8}完全覆蓋，由于d(so,s8)>Rc和d(s1,s8)>Rc，因而so無(wú)法計(jì)算其是否被鄰居節(jié)點(diǎn)覆蓋而判斷為邊界節(jié)點(diǎn). 證畢.

圖 5 推論 2 證明示意圖Fig.5 Diagram of the demonstration of lemma 2

3 仿真實(shí)驗(yàn)與性能評(píng)估

本文基于Windows 10和MATLAB 2016b進(jìn)行了實(shí)驗(yàn)仿真，實(shí)驗(yàn)首先在文獻(xiàn)[3]提供的數(shù)據(jù)集中進(jìn)行了驗(yàn)證，同時(shí)還通過(guò)多種自建場(chǎng)景下的仿真數(shù)據(jù)對(duì)DGSD算法性能進(jìn)行了評(píng)估，實(shí)驗(yàn)評(píng)估的指標(biāo)包括： 節(jié)點(diǎn)正確識(shí)別率(為便于公式表述記為succ)、節(jié)點(diǎn)錯(cuò)誤識(shí)別率(為便于公式表述記為false)，其計(jì)算方法分別如式(6)和(7)所示.

(6)

false=

(7)

式中：R(nodes)表示仿真實(shí)驗(yàn)中實(shí)際檢測(cè)到的邊界節(jié)點(diǎn)；P(nodes)表示Simek數(shù)據(jù)集中提供的標(biāo)準(zhǔn)邊界節(jié)點(diǎn)集.

3.1 檢測(cè)率比較

在節(jié)點(diǎn)識(shí)別率對(duì)比實(shí)驗(yàn)中，本文首先利用文獻(xiàn)[3]中提供的數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)仿真和比較，其數(shù)據(jù)環(huán)境為： ① 節(jié)點(diǎn)規(guī)模分別為50, 100和400，② 節(jié)點(diǎn)密度為8到26，節(jié)點(diǎn)密度間隔為2，③ 節(jié)點(diǎn)通信半徑為20～35 m，間隔為5 m. 由于基于統(tǒng)計(jì)的識(shí)別方法要求節(jié)點(diǎn)密度過(guò)大，因而本文選取提供數(shù)據(jù)集的文獻(xiàn)[3]和基于拓?fù)浞椒ǖ奈墨I(xiàn)[13]中的算法作為本文實(shí)驗(yàn)的對(duì)比對(duì)象，圖 6 和圖 7 分別給出了節(jié)點(diǎn)規(guī)模為400，節(jié)點(diǎn)密度為8～26的場(chǎng)景下三種算法的正確識(shí)別率和錯(cuò)誤識(shí)別率對(duì)比圖，顯然可以看出，DGSD除在節(jié)點(diǎn)密度為8時(shí)正確檢測(cè)率低于Funke提出的算法，在其余場(chǎng)景下的識(shí)別精度均優(yōu)于其它對(duì)比算法，其平均正確識(shí)別率穩(wěn)定在92%以上，平均錯(cuò)誤識(shí)別率低于6%，而Simek算法識(shí)別精度較低的原因在于基于三角形的判斷，在極端情況下會(huì)引起數(shù)值計(jì)算誤差和三角形誤差引起的構(gòu)建不全面導(dǎo)致檢測(cè)失敗. 從對(duì)比結(jié)果來(lái)看，DGSD算法較其它算法在不同的網(wǎng)絡(luò)節(jié)點(diǎn)密度和節(jié)點(diǎn)通信半徑下均表現(xiàn)出較好的魯棒性和更強(qiáng)的泛化能力. 同時(shí)，三種算法也呈現(xiàn)出一個(gè)共同的特征，即隨著節(jié)點(diǎn)密度的增大邊界節(jié)點(diǎn)的正確識(shí)別率也不斷增大，這主要是由于隨著節(jié)點(diǎn)密度的增加，網(wǎng)絡(luò)覆蓋能力增大，從拓?fù)溥B接和角度計(jì)算方面精確度都得到了提高，因而節(jié)點(diǎn)正確識(shí)別率也得到提高.

圖 6 正確檢測(cè)率對(duì)比圖Fig.6 Comparison of precision ratio

圖 7 誤檢率對(duì)比圖Fig.7 Comparison of fallout ratios

3.2 大規(guī)模覆蓋空洞實(shí)驗(yàn)

為進(jìn)一步驗(yàn)證DGSD的泛化能力，隨機(jī)部署了2 000個(gè)節(jié)點(diǎn)到一個(gè)的監(jiān)測(cè)區(qū)域，區(qū)域中含有一個(gè)五角星形覆蓋空洞，Simek、DGSD和Funke三種算法的檢測(cè)結(jié)果分別如圖 8～圖 10 所示，三種算法在該場(chǎng)景下檢測(cè)到的邊界節(jié)點(diǎn)分別為972, 531和1 247個(gè)，由上述圖中顯然可看出，DSGD檢測(cè)到的邊界節(jié)點(diǎn)數(shù)目少于Simek和Funke算法檢出的邊界節(jié)點(diǎn)，然而這些檢出的邊界節(jié)點(diǎn)已經(jīng)能夠清晰地刻畫(huà)網(wǎng)絡(luò)邊界和覆蓋空洞的邊緣區(qū)域.

圖 8 邊界節(jié)點(diǎn)為972的BRC檢測(cè)結(jié)果Fig.8 BRC result of 972 boundary nodes

圖 9 邊界節(jié)點(diǎn)為531的DGSD檢測(cè)結(jié)果Fig.9 DGSD result of 531 boundary nodes

圖 10 邊界節(jié)點(diǎn)為1 247的Funke檢測(cè)結(jié)果Fig.10 Funke result of 1 247 boundary nodes

3.3 能耗比較

節(jié)點(diǎn)能量的消耗是影響網(wǎng)絡(luò)生命周期的關(guān)鍵指標(biāo)，在能量消耗仿真實(shí)驗(yàn)中，節(jié)點(diǎn)能量消耗模型如式(8)和(9)所示，參數(shù)意義與文獻(xiàn)[15-16]相同，網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量、密度和通信半徑等參數(shù)設(shè)置與正確檢測(cè)率比較實(shí)驗(yàn)相同.圖 11 給出了Simek、DGSD和Funke三種算法在上述實(shí)驗(yàn)條件下節(jié)點(diǎn)的能耗對(duì)比，由圖 11 可以得出一個(gè)明顯的結(jié)論即網(wǎng)絡(luò)中節(jié)點(diǎn)執(zhí)行邊界節(jié)點(diǎn)識(shí)別所消耗的總體能量隨著網(wǎng)絡(luò)節(jié)點(diǎn)密度的增加而增大，原因是節(jié)點(diǎn)密度增大導(dǎo)致節(jié)點(diǎn)需要接收和處理的報(bào)文增多，由能耗模型可知這需要消耗節(jié)點(diǎn)更多的能量，同時(shí)也可以看出在所有對(duì)比實(shí)驗(yàn)中DGSD算法的能量消耗顯著低于其它對(duì)比算法，這主要是由于Simek算法在每次三角形構(gòu)建過(guò)程中都需要重復(fù)計(jì)算其全部二跳鄰居信息，而Funke算法則在最大獨(dú)立集的拓?fù)浒l(fā)現(xiàn)過(guò)程和以最大獨(dú)立集中每節(jié)點(diǎn)搜尋以其為圓心的多層閉合環(huán)路過(guò)程中消耗了大量能量.

(8)

ERx=L×Eelec.

(9)

圖 11 DGSD、Simek和Funke節(jié)點(diǎn)能量消耗對(duì)比圖Fig.11 Comparison of energy dissipation of DGSD, Simek and Funke

3.4 算法復(fù)雜度分析

DGSD算法可以分解為： 收集節(jié)點(diǎn)鄰居信息，計(jì)算節(jié)點(diǎn)絕對(duì)角，節(jié)點(diǎn)排序和邊界節(jié)點(diǎn)識(shí)別四個(gè)過(guò)程，上述過(guò)程的算法復(fù)雜度分別為O(n+m)，O(n)，O(nlog(n))和O(kn)，這里，n=|V|，m=|E|，k表示平均節(jié)點(diǎn)度，因而DGSD算法的總體復(fù)雜度為O((2+log(n)+k)n+m)，Simek算法和Funke算法在鄰居信息搜集極端具有相同的復(fù)雜度，在邊界節(jié)點(diǎn)識(shí)別階段其總體復(fù)雜度分別為O(3(k-1)n)和O(|I|n)，這里I表示網(wǎng)絡(luò)的最大獨(dú)立集，綜合鄰居信息收集兩者的總體復(fù)雜度分別為O((3k-2)n+m)和O(|I|n+m)，在具體網(wǎng)絡(luò)中可以得出DGSD算法復(fù)雜度低于其它對(duì)比算法.

4 結(jié) 論

針對(duì)大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)部署不均勻和節(jié)點(diǎn)失效引起的覆蓋空洞問(wèn)題，提出一種基于幾何方法的分布式邊界節(jié)點(diǎn)識(shí)別算法，該方法利用節(jié)點(diǎn)的絕對(duì)角特征，實(shí)現(xiàn)了邊界節(jié)點(diǎn)的自動(dòng)識(shí)別. 大量仿真實(shí)驗(yàn)結(jié)果表明： 同現(xiàn)有算法相比，該算法在不同網(wǎng)絡(luò)規(guī)模和密度場(chǎng)景下都能穩(wěn)定、高精度、低能耗地識(shí)別網(wǎng)絡(luò)種的邊界節(jié)點(diǎn)，這說(shuō)明DGSD魯棒性高、泛化性好，同時(shí)其算法復(fù)雜度較現(xiàn)有算法也較低，能夠適應(yīng)不同規(guī)模和密度的網(wǎng)絡(luò)環(huán)境.