何文秀，王宇翔，張 拓，徐瑞吉，方 丁

(1.浙江工業(yè)大學(xué)之江學(xué)院，浙江 紹興 312030；2.浙江工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)簡單來說，就是一種使用無線通信技術(shù)將若干各種種類的傳感器節(jié)點(diǎn)以一定的網(wǎng)絡(luò)結(jié)構(gòu)構(gòu)建起來的技術(shù)手段，能夠有效檢測穿越節(jié)點(diǎn)感知覆蓋區(qū)域的目標(biāo)。 這種技術(shù)可能應(yīng)用到的傳感器種類繁多，比如氣體傳感器、光敏傳感器、激光掃描儀、毫米波雷達(dá)以及立體視覺攝像機(jī)等，多種多樣的傳感器不僅是實(shí)現(xiàn)網(wǎng)絡(luò)構(gòu)建的前提條件，也使得這種技術(shù)的應(yīng)用領(lǐng)域十分廣泛[1-2]。 無線傳感器網(wǎng)絡(luò)中有一種重要的技術(shù)，是將傳感器節(jié)點(diǎn)沿著部署線部署，所有節(jié)點(diǎn)的感知覆蓋區(qū)域就像柵欄一樣劃分一塊區(qū)域，因而被形象地稱為柵欄覆蓋技術(shù)。 當(dāng)有目標(biāo)從一塊區(qū)域越過柵欄進(jìn)入到另一塊區(qū)域時，這道由傳感器節(jié)點(diǎn)構(gòu)成的柵欄就能感知到并且將該信息上傳[3-5]。 柵欄覆蓋技術(shù)被廣泛應(yīng)用于環(huán)境保護(hù)、生態(tài)檢測以及軍事保護(hù)等方面[6]。 而如何利用有限的有向傳感器節(jié)點(diǎn)實(shí)現(xiàn)無間隙的強(qiáng)柵欄構(gòu)建是目前柵欄覆蓋技術(shù)研究的難點(diǎn)和熱點(diǎn)[7-9]。

得益于眾多科研工作者對于該難點(diǎn)的持續(xù)研究，目前在柵欄覆蓋技術(shù)方面已有許多效果良好的解決方法供后來者參考。 在應(yīng)用全向傳感器節(jié)點(diǎn)實(shí)現(xiàn)柵欄覆蓋的研究中，Kumar 等[10]對弱k-柵欄覆蓋與強(qiáng)k-柵欄覆蓋兩個新名詞做出了定義，并且設(shè)計了一種用以判定節(jié)點(diǎn)覆蓋區(qū)域是否符合k-柵欄覆蓋的方法，還推導(dǎo)出在某種臨界情形下會出現(xiàn)弱k-柵欄覆蓋并給出了該情形的條件。 班冬松等[11]定義了1-BCMS 和1-GBMS 兩個最小移動和問題，并且設(shè)計出了一種網(wǎng)絡(luò)劃分模型，通過使用這種模型可以使1-BCMS 向1-GBMS 近似轉(zhuǎn)化，還設(shè)計了一種針對k-柵欄覆蓋問題的方法，該方法基于分治策略，極大地減少了在計算和通信方面的耗費(fèi)。Chen 等[12]設(shè)計了目標(biāo)柵欄覆蓋方法，由于這種方法可以同時檢測外部目標(biāo)向內(nèi)入侵柵欄和內(nèi)部目標(biāo)向外突破柵欄，因而適用于比較特殊的場景，比如監(jiān)獄等，降低了被入侵或突破的風(fēng)險，有較高的實(shí)用價值。

在無線傳感器網(wǎng)絡(luò)的實(shí)際應(yīng)用中，有些種類的傳感器節(jié)點(diǎn)只能夠感知周圍某個角度范圍內(nèi)的目標(biāo)，這些節(jié)點(diǎn)被統(tǒng)稱為有向傳感器節(jié)點(diǎn)，其感知范圍取決于感知角和感知半徑的大小。 事實(shí)上在一些特定的情形下，為了取得更好的柵欄構(gòu)建效果往往會選擇使用有向傳感器節(jié)點(diǎn)。 針對此類情況，也有許多科研工作者提出了自己的解決方案，Tao 等[13]利用有向傳感器節(jié)點(diǎn)能夠通過旋轉(zhuǎn)來調(diào)節(jié)方向的能力，設(shè)計了一種構(gòu)建強(qiáng)柵欄的方法，首先利用DBG方向柵欄圖獲取傳感器節(jié)點(diǎn)的最小需求數(shù)，然后根據(jù)盡可能減少旋轉(zhuǎn)角度總和的原則，就能夠以最低的旋轉(zhuǎn)能耗完成強(qiáng)柵欄的構(gòu)建。 由于有向傳感器節(jié)點(diǎn)的應(yīng)用給連接覆蓋(Connection Coverage，CoCo)問題帶來了新的挑戰(zhàn)，因此Han 等[14]對最小能量連接覆蓋問題進(jìn)行了研究，他們實(shí)驗(yàn)的網(wǎng)絡(luò)場景中既有有向特征又有全向特征，這兩種特征共有四種不同的組合，經(jīng)研究后給出了四種組合情況下的問題均為非確定性多項式難題的結(jié)論，同時提出了一種近似算法，旨在最小化傳感和連接的總能量耗費(fèi)。Khanjary 等[15]研究出了一種基于分布式自主學(xué)習(xí)方法在DBG 中獲取柵欄部署區(qū)域的部署線，然后在保證不重疊的前提下旋轉(zhuǎn)節(jié)點(diǎn)以改變其感知方向的方法，該方法的優(yōu)勢在于利用相同數(shù)量節(jié)點(diǎn)可以實(shí)現(xiàn)更高的柵欄構(gòu)建率。 范興剛等[16]從移動和轉(zhuǎn)動能耗相結(jié)合的角度來考慮有向柵欄的構(gòu)建問題，設(shè)計了一種稱為DBCNA 的分布式方法，主要改進(jìn)是可以控制相鄰有向傳感器節(jié)點(diǎn)的移動，使用該方法構(gòu)建柵欄，可以降低需要的傳感器節(jié)點(diǎn)數(shù)量和消耗的能量，雖然移動鄰居節(jié)點(diǎn)的方法較為簡單，無法做到最小化柵欄構(gòu)建的總能耗，但仍有非常大的參考價值。 Zhao 等[17]解決了具有節(jié)點(diǎn)移動能力的有向傳感器網(wǎng)絡(luò)的節(jié)能柵欄覆蓋問題，首先推導(dǎo)出了在二維矩形區(qū)域中遵循泊松點(diǎn)隨機(jī)放置的有向傳感器節(jié)點(diǎn)產(chǎn)生柵欄間隙的臨界條件，然后設(shè)計了一種節(jié)能柵欄修復(fù)算法，該算法的特點(diǎn)是通過最小化傳感器節(jié)點(diǎn)的移動距離來在一定程度上降低能耗，但無法最小化。 Chen 等[18]提出了一種CRA 強(qiáng)柵欄構(gòu)建方法，該方法通過對節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)操作以修復(fù)柵欄間隙，然而該方法忽略了節(jié)點(diǎn)的移動特性，因此部署時節(jié)點(diǎn)的利用率不能達(dá)到最大。 趙小敏等[19]提出的OMBR 柵欄間隙修復(fù)方法，則是一種通過Hungarian 算法移動節(jié)點(diǎn)來修復(fù)柵欄間隙的方法，該方法只使用了節(jié)點(diǎn)的移動特性，同樣不能最大化利用節(jié)點(diǎn)。

上述科研工作者留下了許多針對無線傳感器網(wǎng)絡(luò)中的柵欄覆蓋問題行之有效的解決方案，但仍普遍存在節(jié)點(diǎn)利用率較低、柵欄構(gòu)建率不高等缺陷。針對這些問題，本文提出一種節(jié)點(diǎn)混合運(yùn)動的有向傳感器網(wǎng)絡(luò)強(qiáng)柵欄構(gòu)建方法(A strong barrier construction method for directional sensor networks with node hybrid movement，BCNHM)，該方法通過將傳感器節(jié)點(diǎn)分類為子?xùn)艡诠?jié)點(diǎn)和冗余節(jié)點(diǎn)，再利用冗余節(jié)點(diǎn)修復(fù)子?xùn)艡诠?jié)點(diǎn)之間的柵欄間隙，就可以使被部署節(jié)點(diǎn)得到更大程度的利用，同時在派遣冗余節(jié)點(diǎn)時加入了Hungarian 算法[20]對節(jié)點(diǎn)的派遣方式完成優(yōu)化，最小化冗余節(jié)點(diǎn)在移動中產(chǎn)生的能耗。 該方法在完成柵欄構(gòu)建工作的基礎(chǔ)上，在提升節(jié)點(diǎn)利用率和柵欄構(gòu)建率方面有良好的性能。

1 相關(guān)模型與假設(shè)

1.1 相關(guān)模型

有向傳感器通常采用的是〈P，R，α，β〉組成的四元組感知模型。

在圖1 所示的模型示意圖中，P(x，y)代表的是一個節(jié)點(diǎn)在平面直角坐標(biāo)系上的相對坐標(biāo)；由于節(jié)點(diǎn)的感知覆蓋范圍通常為扇形區(qū)域，因此用R代表覆蓋區(qū)域的半徑；α代表該節(jié)點(diǎn)感知方向與坐標(biāo)軸的夾角大小，取值范圍在0 與2π 之間；β表示的是該節(jié)點(diǎn)感知角的大小，β越大則該節(jié)點(diǎn)的感知范圍越廣，而當(dāng)β＝2π 時，該有向傳感器就變成了全向傳感器；MN代表的是扇形區(qū)域里最長的弦。

圖1 有向傳感器感知模型

1.2 相關(guān)假設(shè)

①傳感器網(wǎng)絡(luò)的所有節(jié)點(diǎn)均為同一種類且內(nèi)部構(gòu)造相同，都能夠進(jìn)行任意方向的位移和旋轉(zhuǎn)；

②所有節(jié)點(diǎn)都知道自己的坐標(biāo)P(x，y)和感知方向夾角α；

③所有節(jié)點(diǎn)每移動1 m 能耗均為Jm＝3.6 J，每轉(zhuǎn)動π 角度能耗均為Jr＝1.8 J[21-22]；

④所有節(jié)點(diǎn)在能量充足的情況下移動距離和旋轉(zhuǎn)角度不受限制；

⑤當(dāng)檢測目標(biāo)出現(xiàn)在節(jié)點(diǎn)感知區(qū)域之外時，無法檢測到；反之則必定能夠檢測到目標(biāo)。

2 子?xùn)艡跇?gòu)建

2.1 子?xùn)艡诓檎?/h3>

柵欄構(gòu)建首先需要沿著目標(biāo)柵欄的部署線，在長為L寬為W的矩形區(qū)域內(nèi)(通常L遠(yuǎn)大于W)部署傳感器節(jié)點(diǎn)，在這一過程中往往會出現(xiàn)節(jié)點(diǎn)受風(fēng)力、地形等環(huán)境因素影響而位置偏離的情況。 假設(shè)節(jié)點(diǎn)的個數(shù)為N，定義i、j為任意兩個不同節(jié)點(diǎn)的編號(0

一般當(dāng)兩個節(jié)點(diǎn)的感知區(qū)域存在交集時，認(rèn)為它們共同形成了一段子?xùn)艡凇?具體的判斷方法如下:首先計算兩個節(jié)點(diǎn)ni和nj感知區(qū)域邊界之間的歐式距離，然后獲取其中的最小值dis(ni，nj)作為感知區(qū)域間的距離。 若dis(ni，nj)＝0，認(rèn)為兩個區(qū)域存在交集；若dis(ni，nj)＞0，則認(rèn)為兩個區(qū)域不存在交集，即出現(xiàn)了柵欄間隙[23]。 這種子?xùn)艡诘呐袛喾椒ㄊ呛罄m(xù)步驟能夠?qū)崿F(xiàn)的基礎(chǔ)。

以x軸為橫坐標(biāo)，y軸為縱坐標(biāo)在部署區(qū)域建立平面坐標(biāo)系，然后將傳感器節(jié)點(diǎn)沿著目標(biāo)部署線放置，由于受到外界環(huán)境的影響，節(jié)點(diǎn)位置會如圖2所示情形偏離x軸，這時將這些節(jié)點(diǎn)根據(jù)橫坐標(biāo)從小到大排列，獲得所有節(jié)點(diǎn)集合Set ＝{n1，n2，…，nN}，同樣用dis(ni，nj)代表任意兩個節(jié)點(diǎn)感知區(qū)域間的距離。 在完成上述的準(zhǔn)備工作后，就有了一種子?xùn)艡诘牟檎宜惴?從橫坐標(biāo)最小的兩節(jié)點(diǎn)n1和n2開始，先計算dis(n1，n2)，若dis(n1，n2)＝0，即兩個節(jié)點(diǎn)共同構(gòu)建了子?xùn)艡?，把這兩個節(jié)點(diǎn)添加到第一個子?xùn)艡诘募螧1內(nèi)(B1為Set 類型的集合，能自動丟棄重復(fù)元素)。 隨后對節(jié)點(diǎn)n2、n3和n4計算dis(n2，n3)和dis(n2，n4)，若dis(n2，n3)＞0 并且dis(n2，n4)＝0，則說明n2與n4共同構(gòu)建了子?xùn)艡诙鴑3則沒有參與構(gòu)建。 類似n3的節(jié)點(diǎn)被稱作冗余節(jié)點(diǎn)，需要添加到冗余節(jié)點(diǎn)集合Rs中，而節(jié)點(diǎn)n4則添加到集合B1內(nèi)；若dis(n2，n3)＝0 則僅需把n3添加到B1內(nèi)。 根據(jù)這樣的規(guī)則重復(fù)進(jìn)行距離計算與節(jié)點(diǎn)歸類，直到遇見圖2 中n4和n5對應(yīng)的情況，子?xùn)艡跓o法繼續(xù)延長說明已經(jīng)完成了一條子?xùn)艡诘牟檎?，即子?xùn)艡贐1＝{n1，n2，n4}，冗余節(jié)點(diǎn)集合Rs＝{n3}；接著從節(jié)點(diǎn)n5開始重復(fù)上述過程，開始下一條子?xùn)艡贐2的構(gòu)建，一直到區(qū)域內(nèi)的所有節(jié)點(diǎn)都被歸類到某個集合中，則算法結(jié)束。 表1 中介紹了算法的詳細(xì)步驟以及偽代碼。

圖2 子?xùn)艡诜侄螛?gòu)建圖

表1 子?xùn)艡跇?gòu)建算法表

7: Rs.add(ni+1，…，nmax(j)-1)；8: i←max(j)；9: else 10: t++；11: end if 12: i++；13:end for

2.2 子?xùn)艡陂g隙修復(fù)

如圖2 中的G1所示，在子?xùn)艡诔醪綐?gòu)建后，兩個子?xùn)艡陂g通常會存在間隙，這時候就需要考慮移動或轉(zhuǎn)動有向傳感器節(jié)點(diǎn)來拼接它們，而由1.2 小節(jié)中的假設(shè)③可知:節(jié)點(diǎn)移動單位距離所消耗的能量要遠(yuǎn)高于轉(zhuǎn)動單位角度消耗的能量。 因此在實(shí)際應(yīng)用中，為了減少在拼接過程中產(chǎn)生的能耗，就要優(yōu)先考慮通過轉(zhuǎn)動節(jié)點(diǎn)的方式實(shí)現(xiàn)拼接。 假設(shè)存在間隙的兩個節(jié)點(diǎn)編號分別為w、v，可以按照下述的流程完成拼接:

Step 1:(a)單獨(dú)在子?xùn)艡陂g隙左側(cè)進(jìn)行轉(zhuǎn)動操作。 以圖3(a)中nw為例，對它進(jìn)行轉(zhuǎn)動直至與nv的感知區(qū)域出現(xiàn)重疊，在兩個節(jié)點(diǎn)的感知區(qū)域有相交的情況下，可以得到nw的角度為θ＝[](θ指的是節(jié)點(diǎn)感知區(qū)域的下邊界PM 與x軸正方向形成的夾角)，又在和nw-1的感知區(qū)域相交的情況下，可以得到角度φ＝[]，則θ與φ的重疊區(qū)域的交角為ψ＝[]。 在交角ψ≠0 的情況下，只需依照式(2)所得的度數(shù)轉(zhuǎn)動，就能夠完成子?xùn)艡诘钠唇?，Δ? 時nw應(yīng)當(dāng)轉(zhuǎn)動至，否則轉(zhuǎn)動至x處。 若出現(xiàn)ψ＝0 的情況則跳轉(zhuǎn)至Step 1(b)。

在式(2)中，節(jié)點(diǎn)未轉(zhuǎn)動時感知區(qū)域的下邊界PM 與x軸正方向形成的夾角為(由圖1 可以得出)；其中代表θ和φ相交角度的上界；代表θ和φ相交角度的下界。

(b)單獨(dú)在子?xùn)艡陂g隙右側(cè)進(jìn)行轉(zhuǎn)動操作。 以圖3(b)中nv為例，對它進(jìn)行轉(zhuǎn)動直至與nw的感知區(qū)域出現(xiàn)重疊，在兩個節(jié)點(diǎn)的感知區(qū)域有相交的情況下，可以得到nv的角度為θ＝[]，又在和nv+1的感知區(qū)域相交的情況下，可以得到角度φ＝[]，則θ與φ的重疊區(qū)域的交角為ψ＝[]。 在交角ψ≠0 的情況下，只需依照式(2)所得的度數(shù)進(jìn)行轉(zhuǎn)動，就實(shí)現(xiàn)了子?xùn)艡诘钠唇樱ぃ? 時nv應(yīng)當(dāng)轉(zhuǎn)動至，否則轉(zhuǎn)動至處。 如果出現(xiàn)ψ＝0 的情況則算法轉(zhuǎn)到Step 2。

圖3 單個節(jié)點(diǎn)拼接子?xùn)艡趫D

Step 2:同時在子?xùn)艡陂g隙兩側(cè)進(jìn)行轉(zhuǎn)動操作。在Step 1 中，為了拼接子?xùn)艡冢惴▽?jié)點(diǎn)nw進(jìn)行旋轉(zhuǎn)操作，使其旋轉(zhuǎn)至處(Δ＞0)。 完成Step 1能夠有效縮短子?xùn)艡诘拈g隙長度，但不一定能完全消除間隙，此時將出現(xiàn)如圖4(b)所示的新柵欄間隙NewGi。 出現(xiàn)這種情況時，需要再次調(diào)用Step 1(b)，轉(zhuǎn)動NewGi右側(cè)的nv來嘗試完成拼接，若能達(dá)到如圖4(c)所示的情況，則拼接成功。 否則重新使nw轉(zhuǎn)動到，同時重復(fù)Step 1(b)中的方法再次嘗試，如仍不能完全消除柵欄間隙，則拼接失敗，算法轉(zhuǎn)到Step 3。

圖4 兩節(jié)點(diǎn)同時拼接子?xùn)艡趫D

Step 3:對間隙左側(cè)節(jié)點(diǎn)和右側(cè)子?xùn)艡谶M(jìn)行轉(zhuǎn)動操作。 首先，對間隙左側(cè)的節(jié)點(diǎn)調(diào)用Step 1(a)轉(zhuǎn)動，完成轉(zhuǎn)動有效減小了nw右側(cè)的間隙，形成了較短的新柵欄間隙。 然后，對間隙右側(cè)的節(jié)點(diǎn)調(diào)用Step 1(b)轉(zhuǎn)動。 經(jīng)過這一步，nv右側(cè)也與節(jié)點(diǎn)nw一樣形成了新的柵欄間隙，并且接下來的節(jié)點(diǎn)的情況均類似，所以逐個對nv與nv+1間以及所有后續(xù)節(jié)點(diǎn)間的新柵欄間隙調(diào)用Step 1(b)中的方法，如此重復(fù)至出現(xiàn)旋轉(zhuǎn)后節(jié)點(diǎn)右側(cè)沒有出現(xiàn)新柵欄間隙的情況，算法結(jié)束。 如果完成所有節(jié)點(diǎn)的遍歷，且節(jié)點(diǎn)右側(cè)仍存在柵欄間隙，則說明子?xùn)艡跓o法完全拼接，此時需要回滾操作，使初始狀態(tài)時位于該間隙右側(cè)的所有節(jié)點(diǎn)的朝向均復(fù)原，最后調(diào)用Step 1(b)使右側(cè)第一個節(jié)點(diǎn)nv轉(zhuǎn)動到處，以達(dá)到無法完全拼接的情況下最小化柵欄間隙長度的目的。

Step 4:對柵欄兩端與邊界的間隙進(jìn)行修復(fù)。 在經(jīng)過前面的步驟后，算法已經(jīng)完成了子?xùn)艡谥g的拼接，這一步需要修復(fù)如圖2 中Gt所示的間隙(t表示邊界間隙的編號)，由于邊界節(jié)點(diǎn)的感知方向發(fā)生了改變，導(dǎo)致與部署區(qū)域的邊界之間出現(xiàn)了間隙。這種間隙的修復(fù)方法也比較簡單，首先觀察柵欄第一個節(jié)點(diǎn)n1的感知區(qū)域有沒有觸及左邊界，若觸及說明并未出現(xiàn)邊界間隙，不作處理，若未觸及則調(diào)用Step 1(b)轉(zhuǎn)動節(jié)點(diǎn)以修補(bǔ)間隙。 接著同樣觀察柵欄最后一個節(jié)點(diǎn)nN的感知區(qū)域有沒有觸及右邊界，若觸及則不作處理，若未觸及則調(diào)用Step 1(a)轉(zhuǎn)動節(jié)點(diǎn)以修補(bǔ)。

3 柵欄間隙修復(fù)

子?xùn)艡谄唇佑袝r會出現(xiàn)只靠旋轉(zhuǎn)節(jié)點(diǎn)無法完全拼接的情況，此時柵欄間仍存在間隙，為解決該問題，同時提高節(jié)點(diǎn)利用率，選擇對冗余節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)及移動操作對待修復(fù)位置進(jìn)行修復(fù)。 然而怎樣確定待修復(fù)位置，以及如何派遣冗余節(jié)點(diǎn)至修復(fù)位置，這些問題有待解決。

3.1 尋找待修復(fù)位置

待修復(fù)位置指的是冗余節(jié)點(diǎn)需要派遣到的位置。 由1.2 小節(jié)中的假設(shè)③可知:有向傳感器節(jié)點(diǎn)的移動能耗比轉(zhuǎn)動能耗高。 因此要降低修復(fù)柵欄間隙能耗，就需要盡量降低冗余節(jié)點(diǎn)在移動上的能耗，優(yōu)先考慮旋轉(zhuǎn)節(jié)點(diǎn)進(jìn)行修復(fù)。 在整個柵欄間隙修復(fù)的過程中，感知角β 能影響節(jié)點(diǎn)的感知范圍，柵欄間隙長度dG則決定了需要修復(fù)的距離，兩者均會使待修復(fù)位置的尋找過程發(fā)生改變，而各種情形下β和dG均存在差異，下面將分別說明在各種情形下查找待修復(fù)位置的方式:

首先根據(jù)柵欄間隙長度dG的大小可以將尋找待修復(fù)位置的情形分為兩大類，0

(1)在0

①在0<β<2arcsin(dG/2R)的情形下，使用邊覆蓋的方式查找待修復(fù)位置。 如圖5(a)所示，邊覆蓋需要對待修復(fù)的柵欄間隙進(jìn)行建模，首先找到柵欄間隙兩側(cè)節(jié)點(diǎn)感知區(qū)域的最短連線ST，可知ST 的長度就是dG，然后設(shè)連線中點(diǎn)為圓心O，以半徑r＝R-dG/2 作圓C，此時延長連線ST可以得到與圓C的兩個交點(diǎn)P1、P2，這兩個點(diǎn)就是要找的待修復(fù)位置，可以根據(jù)實(shí)際情況派遣冗余節(jié)點(diǎn)至其中一個位置進(jìn)行柵欄間隙修復(fù)。 下面選擇P1證明冗余節(jié)點(diǎn)在該點(diǎn)可以實(shí)現(xiàn)修復(fù):已知冗余節(jié)點(diǎn)的感知區(qū)域半徑為R，而P1與間隙右側(cè)節(jié)點(diǎn)的最短歐式距離d(P1，T)也為R，顯然R≥dG，因此當(dāng)冗余節(jié)點(diǎn)被派遣到P1處，且進(jìn)行旋轉(zhuǎn)操作必定能實(shí)現(xiàn)對柵欄間隙G的邊覆蓋，達(dá)到修復(fù)的效果。

②在2arcsin(dG/2R)≤β<2π 的情形下，可以使用邊覆蓋或弧覆蓋的方式查找待修復(fù)位置。 如圖5(b)所示，同樣對柵欄間隙進(jìn)行建模，首先找到柵欄間隙兩側(cè)節(jié)點(diǎn)感知區(qū)域的最短連線ST，然后分別以連線端點(diǎn)S、T為圓心，R為半徑作圓，可以得到兩個圓的交點(diǎn)P3、P4，這兩個點(diǎn)就是要找的待修復(fù)位置。 下面選擇P3證明冗余節(jié)點(diǎn)在該點(diǎn)可以實(shí)現(xiàn)修復(fù):根據(jù)冗余節(jié)點(diǎn)感知區(qū)域的扇形模型，可以得出其中弦的長度最大值MN＝2Rsin(β/2)，由前提條件2arcsin(dG/2R)≤β變形可得2Rsin(β/2)≥dG，即MN≥dG，這正是實(shí)現(xiàn)弧覆蓋需要滿足的條件。 因此當(dāng)冗余節(jié)點(diǎn)被派遣到P3處，且進(jìn)行旋轉(zhuǎn)操作必定能實(shí)現(xiàn)對柵欄間隙G的弧覆蓋。 除了弧覆蓋，情形①的邊覆蓋也同樣適用于這種情形，所以可以根據(jù)情形①同樣得到P1和P2，共計四個待修復(fù)位置可以達(dá)到修復(fù)的效果。

圖5 待修復(fù)位置圖

(2)在R

①在0<β<π/3 的情形下，僅靠移動一個冗余節(jié)點(diǎn)無法完成修復(fù)。 在這種條件下，可知柵欄間隙的長度dG大于冗余節(jié)點(diǎn)感知區(qū)域半徑R，因此單個冗余節(jié)點(diǎn)的感知區(qū)域無法覆蓋柵欄間隙。

②在π/3≤β<π 的情形下，若dG＞2Rsin(β/2)，則與①同理，同樣無法依靠移動一個冗余節(jié)點(diǎn)完成修復(fù)。 若dG≤2Rsin(β/2)，則可如圖5(c)所示的方式實(shí)現(xiàn)對柵欄間隙的弧覆蓋，首先使用弧覆蓋的方法可以查找到待修復(fù)位置P1、P2，同樣舉P1為例:通過條件dG≤2Rsin(β/2)計算可得弦MN的長度，顯然此時MN長于柵欄間隙ST，而且MN的長度會隨著β的增大而增大，所以必定能實(shí)現(xiàn)對柵欄間隙的弧覆蓋，達(dá)到修復(fù)的效果。

③在π≤β<2π 的情形下，同樣可以派遣單個冗余節(jié)點(diǎn)實(shí)現(xiàn)弧覆蓋。 在π≤β<2π 的條件下，冗余節(jié)點(diǎn)感知區(qū)域的最大弦顯然是直徑，即MN＝2R，而已知dG≤2R，因此可以通過弧覆蓋的方法查找到待修復(fù)位置P1、P2來實(shí)現(xiàn)柵欄間隙的修復(fù)。

由上述各類情形可以看出，在單個冗余節(jié)點(diǎn)能夠?qū)崿F(xiàn)柵欄間隙修復(fù)的情形中，可以查找到的待修復(fù)位置往往有多個，在圖5(b)的情形中能夠查找到四個待修復(fù)位置均可以用來修復(fù)柵欄間隙。 然而待派遣的冗余節(jié)點(diǎn)的位置到每個待修復(fù)位置的距離各不相同，導(dǎo)致派遣到不同待修復(fù)位置消耗的能量也有差異，因此還需要做出選擇。 為了降低所有冗余節(jié)點(diǎn)在完成移動派遣后最終消耗的能量總值，應(yīng)當(dāng)選取與待派遣的冗余節(jié)點(diǎn)距離最短的待修復(fù)位置。

3.2 Hungarian 算法派遣冗余節(jié)點(diǎn)

在完成待修復(fù)位置的定位之后，就要進(jìn)行冗余節(jié)點(diǎn)的派遣，為了在提高傳感器節(jié)點(diǎn)利用率的同時盡可能減少派遣過程中產(chǎn)生的能耗代價，本文在派遣冗余節(jié)點(diǎn)時使用了Hungarian 算法，力求消耗最少的能量實(shí)現(xiàn)移動派遣。 Hungarian 算法的核心思想是以派遣冗余節(jié)點(diǎn)的距離代價為元素來構(gòu)建代價矩陣，最終實(shí)現(xiàn)冗余節(jié)點(diǎn)和待修復(fù)位置的最佳匹配。

在使用Hungarian 算法前首先要對冗余節(jié)點(diǎn)的個數(shù)進(jìn)行判斷，若冗余節(jié)點(diǎn)的個數(shù)m少于柵欄間隙的數(shù)量n，則認(rèn)為無法完成柵欄間隙的修復(fù)任務(wù)；若m＝n，則可以直接構(gòu)建式(3)中的代價矩陣，其中dij(0≤i≤m，0≤j≤n)代表第i個冗余節(jié)點(diǎn)Rsi到第j個柵欄間隙的待修復(fù)位置Pj的最短距離；當(dāng)m＞n時比較特殊，由于Hungarian 算法要求匹配雙方數(shù)目一致，為了將其用在這種情形下，就需要將待修復(fù)位置的數(shù)量補(bǔ)足，具體操作為增設(shè)m-n個到冗余節(jié)點(diǎn)距離為0 的虛擬待修復(fù)位置，然后可以構(gòu)建代價矩陣。

完成代價矩陣構(gòu)建后需要使用Hungarian 算法對其進(jìn)行優(yōu)化處理，最終得到的最低Cost 就對應(yīng)著最佳的派遣方式，可以使冗余節(jié)點(diǎn)在派遣過程中的移動能耗最小。 具體處理步驟以圖6 情形為例進(jìn)行說明:

圖6 Hungarian 算法派遣冗余節(jié)點(diǎn)修復(fù)間隙圖

①由于柵欄間隙的數(shù)量n＝1，因此最終的待修復(fù)位置為Pi(Pi∈{})，其中i為該柵欄間隙的編號；又因冗余節(jié)點(diǎn)的個數(shù)m＝2，所以需要增設(shè)1個虛擬的待修復(fù)位置。 根據(jù)式(3)最終得到式(4)所示的代價矩陣，因?yàn)樘摂M待修復(fù)位置與冗余節(jié)點(diǎn)距離為0，因此代價矩陣第二列均為0。

②每一行的所有矩陣元素減去該行的最小值，每一列的所有矩陣元素也減去該列的最小值，得到式(5)所示代價矩陣。

③用最少的行列覆蓋代價矩陣中所有的0，此處使用第二行與第二列即可覆蓋所有的0，因此行列數(shù)為2，與矩陣大小相等，達(dá)到最佳匹配，算法停止。

④根據(jù)代價矩陣(5)中0 的位置為第一行第二列與第二行第一列可知(每列只選擇一個0)，應(yīng)當(dāng)將Rs1派遣至虛擬待修復(fù)位置，Rs2派遣至，對應(yīng)的最佳匹配的代價為d2i。

由于派遣冗余節(jié)點(diǎn)只是將節(jié)點(diǎn)移動到了待修復(fù)位置，不改變節(jié)點(diǎn)的感知方向，因此派遣后節(jié)點(diǎn)并不一定成功修復(fù)了柵欄間隙。 這時還需要對節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)操作以達(dá)到修復(fù)的目的。

4 仿真實(shí)驗(yàn)

為了驗(yàn)證算法的有效性，在i7 處理器，8G 內(nèi)存的PC 機(jī)上利用MATLAB R2013a 軟件進(jìn)行仿真實(shí)驗(yàn)。 仿真實(shí)驗(yàn)中的部署區(qū)域?yàn)殚L1 000 m，寬200 m的矩形區(qū)域，將有向傳感器節(jié)點(diǎn)在部署區(qū)域內(nèi)沿著目標(biāo)柵欄部署線進(jìn)行部署，其中節(jié)點(diǎn)的感知區(qū)域半徑R＝45m，感知角β＝π/3，部署時節(jié)點(diǎn)感知方向隨機(jī)。 將32 個節(jié)點(diǎn)以0 為均值，25 為方差的高斯分布部署于目標(biāo)區(qū)域內(nèi)，如圖7 所示。 部署后使用子?xùn)艡跇?gòu)建方法將初期隨機(jī)部署的節(jié)點(diǎn)進(jìn)行子?xùn)艡诘臉?gòu)建及拼接，如圖8 所示。 子?xùn)艡谕瓿善唇雍笕源嬖陂g隙，則進(jìn)行柵欄間隙修復(fù)，如圖9 所示。

圖7 節(jié)點(diǎn)隨機(jī)部署圖

圖8 子?xùn)艡谄唇訄D

圖9 柵欄間隙修復(fù)圖

仿真實(shí)驗(yàn)將以柵欄間隙數(shù)量、節(jié)點(diǎn)利用率、柵欄構(gòu)建率以及網(wǎng)絡(luò)總能耗四個方面為性能指標(biāo)對本文所述的BCNHM 柵欄構(gòu)建方法進(jìn)行性能驗(yàn)證與評價。 仿真實(shí)驗(yàn)還與CRA 強(qiáng)柵欄構(gòu)建方法以及OMBR 柵欄間隙修復(fù)方法進(jìn)行了對比實(shí)驗(yàn)，其中CRA 是一種通過轉(zhuǎn)動節(jié)點(diǎn)感知方向來完成柵欄構(gòu)建的方法，而OMBR 則是一種通過Hungarian 算法移動節(jié)點(diǎn)來修復(fù)柵欄間隙的方法，這兩種方法均可以提高柵欄的構(gòu)建率，并且在一定程度上代表了有向傳感器節(jié)點(diǎn)的兩類柵欄構(gòu)建方法，因此選作對比方法。

4.1 節(jié)點(diǎn)部署數(shù)量影響

理論上來說，部署區(qū)域內(nèi)有向傳感器節(jié)點(diǎn)的數(shù)量大小是柵欄構(gòu)建率的關(guān)鍵影響因素之一。 在有限的部署區(qū)域內(nèi)，部署的節(jié)點(diǎn)個數(shù)越多，柵欄的構(gòu)建率也就越高，而構(gòu)建率的提高使耗費(fèi)在移動和旋轉(zhuǎn)上的能量減少，從而使網(wǎng)絡(luò)的總能耗降低。 由于節(jié)點(diǎn)在實(shí)際部署過程中產(chǎn)生偏移的標(biāo)準(zhǔn)差通常為5，因此設(shè)置σx＝σy＝5，同時在實(shí)際場景中常見的有向傳感器節(jié)點(diǎn)的感知角為π/3，故選其作為仿真節(jié)點(diǎn)的感知角進(jìn)行仿真實(shí)驗(yàn)，在保證獨(dú)立性的前提下進(jìn)行100 次同樣的實(shí)驗(yàn)，然后取結(jié)果均值繪制成如圖10、11 的折線圖，便于后續(xù)的實(shí)驗(yàn)分析。

圖10(a)反映的是柵欄間隙個數(shù)隨著部署區(qū)域內(nèi)節(jié)點(diǎn)數(shù)量變化的關(guān)系。 實(shí)驗(yàn)結(jié)果表明隨著節(jié)點(diǎn)數(shù)量的增加，構(gòu)建柵欄時出現(xiàn)的間隙將減少。 當(dāng)部署的節(jié)點(diǎn)數(shù)量相同時，本文的BCNHM 算法形成的間隙數(shù)量最少，隨后是OMBR 算法與CRA 算法，最多的是沒有對節(jié)點(diǎn)進(jìn)行轉(zhuǎn)動和移動操作的原始柵欄(Original)。 這是因?yàn)镺MBR 算法和CRA 分別只利用了節(jié)點(diǎn)的移動能力和轉(zhuǎn)動能力，因此在構(gòu)建柵欄時仍然有間隙存在，而BCNHM 算法同時對節(jié)點(diǎn)的兩種能力加以利用。 當(dāng)僅依靠節(jié)點(diǎn)旋轉(zhuǎn)無法將柵欄間隙完全修復(fù)時，算法就會派遣最近的冗余節(jié)點(diǎn)至待修復(fù)位置對柵欄進(jìn)行修復(fù)。 因此完成相同的柵欄構(gòu)建工作，BCNHM 算法需要使用的有向傳感器節(jié)點(diǎn)個數(shù)更少。

圖10(b)反映的是節(jié)點(diǎn)利用率隨著節(jié)點(diǎn)數(shù)量變化的關(guān)系。 當(dāng)節(jié)點(diǎn)數(shù)量在區(qū)間[30，35)時，BCNHM的節(jié)點(diǎn)利用率為100%，因?yàn)榇藭r的節(jié)點(diǎn)數(shù)量少于或者剛好達(dá)到構(gòu)建一條柵欄所需的節(jié)點(diǎn)數(shù)量，而BCNHM 算法充分利用了部署區(qū)域內(nèi)的冗余節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)數(shù)量在區(qū)間[35，50]時，節(jié)點(diǎn)的利用率隨著節(jié)點(diǎn)數(shù)量的增多而緩慢降低，由于構(gòu)建柵欄所需的節(jié)點(diǎn)數(shù)量只在一定的范圍內(nèi)波動，因此隨著節(jié)點(diǎn)增多冗余節(jié)點(diǎn)也會相應(yīng)增多，從而出現(xiàn)節(jié)點(diǎn)利用率逐漸降低的情況。 當(dāng)節(jié)點(diǎn)數(shù)量相同時，BCNHM 的節(jié)點(diǎn)利用率最高，OMBR 次之，CRA 和Original 的利用率相同且較低。

圖10 節(jié)點(diǎn)數(shù)量對柵欄構(gòu)建影響圖

圖10(c)反映的是柵欄構(gòu)建率隨節(jié)點(diǎn)數(shù)量變化的關(guān)系。 四種算法的柵欄構(gòu)建率都會隨著節(jié)點(diǎn)數(shù)量的增多而逐漸提高，不過提高的速率有所差異。 其中BCNHM 的柵欄構(gòu)建率提高得最快，OMBR 算法次之，隨后是CRA 算法，Original 算法提高得最慢。并且，在相同節(jié)點(diǎn)數(shù)量的前提下，BCNHM 的柵欄構(gòu)建率要遠(yuǎn)高于其余幾種算法。 OMBR 算法與CRA算法通過對節(jié)點(diǎn)進(jìn)行移動或旋轉(zhuǎn)操作來進(jìn)行柵欄構(gòu)建，所以效果要好于Original，而BCNHM 算法充分利用節(jié)點(diǎn)的轉(zhuǎn)動和移動能力進(jìn)行柵欄構(gòu)建，所以構(gòu)建效果是最好的，達(dá)成百分百的柵欄構(gòu)建率，即構(gòu)建一道強(qiáng)柵欄只需要部署35 個傳感器節(jié)點(diǎn)。

圖10(d)反映的是網(wǎng)絡(luò)總能耗隨著節(jié)點(diǎn)數(shù)量變化的關(guān)系。 由于CRA 沒有考慮節(jié)點(diǎn)的移動能力，作為實(shí)驗(yàn)對比沒有意義，因此選用被廣泛用于節(jié)點(diǎn)派遣問題的Greedy 算法[24]進(jìn)行對比實(shí)驗(yàn)；由于節(jié)點(diǎn)通信消耗的能量遠(yuǎn)低于節(jié)點(diǎn)轉(zhuǎn)動或者移動時的能耗，本實(shí)驗(yàn)忽略節(jié)點(diǎn)通信時的能耗，其中能耗模型如假設(shè)③所示。 通過實(shí)驗(yàn)結(jié)果可以看出，在相同節(jié)點(diǎn)數(shù)量的前提下，BCNHM 與OMBR 的節(jié)點(diǎn)能耗比Greedy 算法低，這是因?yàn)镚reedy 通過派遣距離間隙最近的節(jié)點(diǎn)進(jìn)行間隙修復(fù)，會陷入局部最優(yōu)，而BCNHM和OMBR 均采用Hungarian 算法派遣冗余節(jié)點(diǎn)，對全局最優(yōu)進(jìn)行考慮，此時節(jié)點(diǎn)的移動距離總和更短，因此消耗的能量更低；而BCNHM 相對于OMBR 將一部分移動操作轉(zhuǎn)化為了能耗更低的轉(zhuǎn)動操作，耗能更少；Original 沒有對節(jié)點(diǎn)進(jìn)行操作，因此沒有能量消耗。

4.2 節(jié)點(diǎn)感知角影響

分析節(jié)點(diǎn)感知角對柵欄構(gòu)建的影響，同樣設(shè)置σx＝σy＝5，同時設(shè)置節(jié)點(diǎn)數(shù)量N＝40(經(jīng)實(shí)驗(yàn)驗(yàn)證該節(jié)點(diǎn)數(shù)量下便于分析不同算法的差異)。 實(shí)驗(yàn)結(jié)果如圖11 所示。

圖11 節(jié)點(diǎn)感知角對柵欄構(gòu)建影響圖

圖11(a)反映的是柵欄間隙數(shù)量隨著節(jié)點(diǎn)感知角變化的關(guān)系。 實(shí)驗(yàn)結(jié)果表明，隨著節(jié)點(diǎn)感知角的增大，間隙數(shù)量逐漸減少，因?yàn)楫?dāng)感知角增大時節(jié)點(diǎn)感知范圍增大，有較多間隙隨著節(jié)點(diǎn)感知范圍增大而被覆蓋，因此間隙數(shù)量減少。 當(dāng)感知角相同時，由于BCNHM 算法充分利用冗余節(jié)點(diǎn)進(jìn)行間隙修復(fù)，構(gòu)建的柵欄間隙數(shù)量少于其他幾種算法。

圖11(b)反映的是節(jié)點(diǎn)利用率隨著節(jié)點(diǎn)感知角變化的關(guān)系。 從實(shí)驗(yàn)數(shù)據(jù)可以看出，節(jié)點(diǎn)利用率隨著節(jié)點(diǎn)感知角變大而降低，這是由于感知角增大使感知區(qū)域變大，降低了構(gòu)建柵欄需求的節(jié)點(diǎn)數(shù)量，從而增加了冗余節(jié)點(diǎn)的數(shù)量，降低了節(jié)點(diǎn)利用率。 當(dāng)節(jié)點(diǎn)的感知角在區(qū)間[20°，40°]時，僅靠N＝40 的節(jié)點(diǎn)數(shù)量無法通過單一操作完成子?xùn)艡诘钠唇?，僅有BCNHM 算法可以派遣所有的冗余節(jié)點(diǎn)進(jìn)行間隙的修復(fù)，因此節(jié)點(diǎn)的利用率可達(dá)100%。 在感知角相同時，BCNHM 利用率最高，OMBR 對冗余節(jié)點(diǎn)的利用不充分，節(jié)點(diǎn)利用率次之，CRA 未利用冗余節(jié)點(diǎn)，因此節(jié)點(diǎn)利用率與Original 相同且最低。

圖11(c)反映的是柵欄構(gòu)建率隨著節(jié)點(diǎn)感知角變化的關(guān)系。 實(shí)驗(yàn)結(jié)果表明，四種算法的柵欄構(gòu)建率均與節(jié)點(diǎn)感知角成正相關(guān)關(guān)系。 而在相同節(jié)點(diǎn)感知角的前提下，BCNHM 算法的柵欄構(gòu)建率和柵欄構(gòu)建率的提升速率均高于其余幾種算法，OMBR 與CRA 算法分別需要感知角增大到140°與160°時，柵欄構(gòu)建率才能提升至100%，而BCNHM 算法只需要節(jié)點(diǎn)感知角增大到60°左右，就可以實(shí)現(xiàn)100%的構(gòu)建率。

圖11(d)反映的是網(wǎng)絡(luò)總能耗隨著節(jié)點(diǎn)感知角變化的關(guān)系。 當(dāng)感知角在[20°，68°)時網(wǎng)絡(luò)總能耗隨著角度增大迅速下降，而當(dāng)感知角在[68°，180°]區(qū)間內(nèi)，網(wǎng)絡(luò)總能耗緩慢降低。 這是因?yàn)楣?jié)點(diǎn)感知角小于68°時僅通過旋轉(zhuǎn)節(jié)點(diǎn)不能完成柵欄構(gòu)建，此時派遣冗余節(jié)點(diǎn)進(jìn)行修復(fù)需要消耗大量能量，且隨著感知角增大，此時柵欄出現(xiàn)的間隙迅速減少，因此出現(xiàn)了網(wǎng)絡(luò)總能耗快速下降的趨勢。 當(dāng)感知角大于68°時此時只需轉(zhuǎn)動節(jié)點(diǎn)即可完成柵欄拼接，因此耗能低。

5 總結(jié)

現(xiàn)有的有向傳感器網(wǎng)絡(luò)柵欄構(gòu)建方法普遍存在著節(jié)點(diǎn)利用率不高，柵欄構(gòu)建率低的問題，本文針對這些問題，設(shè)計了一種節(jié)點(diǎn)混合運(yùn)動的有向傳感器網(wǎng)絡(luò)強(qiáng)柵欄構(gòu)建方法BCNHM。 BCNHM 利用轉(zhuǎn)動有向傳感器節(jié)點(diǎn)的方法初步形成子?xùn)艡冢瑫r較好地利用了冗余節(jié)點(diǎn)的移動和轉(zhuǎn)動來完成柵欄間隙的修復(fù)，從而達(dá)到構(gòu)建強(qiáng)柵欄的目的。 將該方法與目前性能較好的強(qiáng)柵欄構(gòu)建方法CRA 和柵欄間隙修復(fù)方法OMBR 進(jìn)行仿真對比實(shí)驗(yàn)，證明了BCNHM 在提高節(jié)點(diǎn)利用率和柵欄構(gòu)建率方面擁有更好的性能。 在未來的研究中，準(zhǔn)備繼續(xù)對強(qiáng)柵欄的構(gòu)建方法進(jìn)行探究，比如有向傳感器的K-柵欄覆蓋方法。 未來也考慮將該算法實(shí)際應(yīng)用于化工廠等高危場所的環(huán)境安全監(jiān)測與報警系統(tǒng)中，進(jìn)行實(shí)地的實(shí)驗(yàn)驗(yàn)證。