彭艷周, 高嘉呈, 程宙強, 呂俊達, 高德軍

(1. 三峽大學 防災減災湖北省重點實驗室,湖北 宜昌 443002; 2. 三峽大學 土木與建筑學院,湖北 宜昌 443002; 3. 國網(wǎng)湖北送變電工程有限公司,湖北 宜昌 443002)

關(guān)鍵字：滑坡監(jiān)測; 區(qū)域覆蓋; 無線傳感器網(wǎng)絡; 節(jié)點部署; 虛擬力算法

滑坡是一種廣泛分布且破壞性強的地質(zhì)災害,給人類社會造成了巨大的人員傷亡和經(jīng)濟損失。其造成的損失并不是完全無法規(guī)避的,只要采取有效的監(jiān)測手段,就有可能及時預測滑坡災害并做出應對措施。傳統(tǒng)的滑坡監(jiān)測主要是利用滑坡區(qū)域內(nèi)布置的各種傳感器進行測量,并通過有線傳輸將測量數(shù)據(jù)傳至現(xiàn)場的監(jiān)控端[1]。但傳統(tǒng)方法成本高、實時性差、易受空間等因素的制約,因此許多學者將無線傳感器網(wǎng)絡(wireless sensor network,WSN)技術(shù)應用到了滑坡監(jiān)測工作中[2-5]。在應用過程中,需要將網(wǎng)絡節(jié)點部署在滑坡地表,并且盡可能地覆蓋更多的監(jiān)測區(qū)域。合理的節(jié)點部署方案能夠顯著增加網(wǎng)絡的覆蓋率,提升網(wǎng)絡的監(jiān)測效果。目前,在滑坡監(jiān)測中部署節(jié)點時仍然以手動部署為主,在面對復雜的部署任務時費時費力且效果不佳,合適的自動算法能夠更為高效地解決節(jié)點部署的問題。

自WSN技術(shù)問世以來,許多學者就展開了其節(jié)點部署算法的研究,所提出的節(jié)點部署算法可分為四種類型:虛擬力方法[6]、幾何方法[7-9]、智能算法[10-12]和多種方法的混合算法[13-15]。其中,虛擬力方法計算量小、優(yōu)化效果明顯、適用范圍廣,不僅能夠用于WSN節(jié)點的部署,其分布式計算的特點還使其能用于移動無線傳感器網(wǎng)絡節(jié)點的自部署[6]。譚勵等[16]針對空中傳感器網(wǎng)絡的能耗與環(huán)境問題,提出了加權(quán)虛擬力算法以及相應的擴散模型。Rout等[17]研究了復雜環(huán)境下的節(jié)點部署問題,提出了一種在關(guān)注區(qū)域內(nèi)部存在障礙時使用的節(jié)點部署算法,該算法在原虛擬力算法的基礎上細化了障礙物對節(jié)點的虛擬力,優(yōu)化了節(jié)點對障礙物的規(guī)避。Sallam等[18]研究了各種節(jié)點數(shù)和節(jié)點覆蓋半徑情況下,如何為虛擬力算法設置合適的斥力和引力。Boufares等[19]基于虛擬力算法,提出了在三維傾斜平面上的移動傳感器節(jié)點部署方法,該方法可實現(xiàn)網(wǎng)絡在三維傾斜平面上的完全覆蓋,并保證網(wǎng)絡的連通性。Jiang等[20]針對水下移動傳感器網(wǎng)絡的節(jié)點部署問題,在虛擬力算法的基礎上,提出了RBVF算法和VFRBEC算法。張俏薇等[21]對虛擬力算法的步長系數(shù)進行了研究,提出了基于sigmoid函數(shù)的步長系數(shù)。滕志軍等[22]推導了虛擬力強度系數(shù)的計算方式,引入了節(jié)點密集度的概念,根據(jù)密集度來選擇最優(yōu)距離闕值。Sha等[23]提出了環(huán)形場的虛擬力算法,可以平衡各節(jié)點之間的工作負載,延長網(wǎng)絡壽命。Liu等[24]將空氣分子理論應用到虛擬力算法中,通過分子間的引力使節(jié)點集中在一定范圍內(nèi),基于節(jié)點的正六邊形分布設置了相鄰、次相鄰的零重力點,該方法能夠快速有效地修復覆蓋盲區(qū),并提升網(wǎng)絡覆蓋率。

從上述的已有研究來看,現(xiàn)有研究多是在規(guī)則的二維理想平面或三維全空間中部署節(jié)點,可用于廠房、森林、水下等應用場景。但以上算法并不適用于在滑坡地表部署WSN節(jié)點。在滑坡監(jiān)測工作中,節(jié)點只能被部署在滑坡區(qū)域的地表。這些地表通常是具有不規(guī)則起伏的三維曲面,且其邊界的形狀較為復雜。然而,已有的二維平面的部署算法難以適應復雜的邊界形狀,監(jiān)測區(qū)域的地表坡度還會導致節(jié)點之間出現(xiàn)覆蓋盲區(qū),而三維全空間的部署方法顯然不適用,因為WSN節(jié)點無法被部署在被監(jiān)測區(qū)域的空中或是地底。

針對以上問題,本文以傳統(tǒng)虛擬力算法為基礎進行改進,提出一種適用于滑坡監(jiān)測中節(jié)點部署的虛擬力算法(virtual force algorithm for the node deployment in landslide monitoring, LMVFA),在不同部署區(qū)域(多種形狀的二維平面、三個三維曲面)進行了節(jié)點的模擬部署,驗證了該算法在復雜的滑坡區(qū)域中部署WSN節(jié)點的有效性。

1 問題與假設

1.1 地形起伏與邊界問題

在滑坡區(qū)域進行節(jié)點部署時,監(jiān)測區(qū)域的地形起伏和邊界問題是不容忽視的。如果忽視滑坡坡度,直接按照平面進行節(jié)點的部署,會導致節(jié)點之間出現(xiàn)覆蓋盲區(qū),見圖1。

圖1 覆蓋盲區(qū)示意圖Fig.1 Schematic diagram of uncovered area

在實際應用中,通常僅需要對指定的監(jiān)測區(qū)域進行覆蓋,如果不考慮邊界問題,會導致大量節(jié)點被部署到監(jiān)測區(qū)域之外,無法發(fā)揮作用。

1.2 系統(tǒng)模型

假設滑坡地表面是一個三維曲面,在單個節(jié)點的覆蓋范圍內(nèi),地表的變化幅度不明顯?；卤O(jiān)測區(qū)域即為節(jié)點部署算法的關(guān)注區(qū)域(region of interest,ROI),其邊界由若干邊界點所確定,見圖2。

圖2 滑坡監(jiān)測中節(jié)點部署的ROIFig.2 ROI of node deployment in landslide monitoring

節(jié)點覆蓋區(qū)域的計算是一個困難的連續(xù)性問題,文獻[19]證明了可以將其轉(zhuǎn)換為離散性問題進行計算。將ROI離散化為若干個網(wǎng)格,以每個網(wǎng)格的中心點代表該網(wǎng)格區(qū)域,網(wǎng)格尺寸越小,計算精度越高。則ROI可以被表示為若干個網(wǎng)格中心點的集合{p1(x1,y1,z1),p2(x2,y2,z2) , ……},ROI上任意兩點之間的歐式距離dij為:

(1)

本文采用二元感知模型(binary sensor model,BSM)進行節(jié)點覆蓋的判定,并假設每個節(jié)點均具有球形的感知范圍,當網(wǎng)格中心點p與節(jié)點ni的距離d(ni,p)小于等于節(jié)點的覆蓋半徑R時,該網(wǎng)格區(qū)域的事件被節(jié)點檢測到的概率為1,否則檢測到的概率為0,見式(2)。

(2)

若節(jié)點ni與節(jié)點nj之間的距離小于等于節(jié)點的通信半徑C,則兩節(jié)點之間視為連通,見式(3)。節(jié)點的通信半徑C需滿足C≥2R。

(3)

2 改進的虛擬力算法LMVFA

在虛擬力算法中,節(jié)點會受到各種虛擬力的作用,在虛擬力合力影響下,不斷調(diào)整自身位置,使節(jié)點分布均勻,提升網(wǎng)絡的覆蓋率。

傳統(tǒng)虛擬力算法中,多是以理想平面矩形為部署區(qū)域,以滑坡監(jiān)測中的監(jiān)測區(qū)域為部署區(qū)域時,由于地形起伏和邊界形狀,虛擬力平衡狀態(tài)并不是網(wǎng)絡覆蓋率最高的狀態(tài)。針對此問題,本文對虛擬力的計算方法進行了改良,進一步提升了網(wǎng)絡的覆蓋率。

2.1 節(jié)點間虛擬力

節(jié)點間虛擬力能夠根據(jù)節(jié)點間的距離調(diào)節(jié)節(jié)點的移動方向與移動步長,使相鄰節(jié)點不會過于接近造成覆蓋區(qū)域的大量重疊。以兩節(jié)點在三維空間中的歐式距離計算虛擬力,能夠更好地根據(jù)滑坡區(qū)域的地形起伏來調(diào)整節(jié)點間距離。

由于節(jié)點只能部署在滑坡地表,在根據(jù)節(jié)點所受虛擬力更新節(jié)點位置時與三維全空間的虛擬力方法有所不同,需忽略節(jié)點在重力方向的移動,使得所有節(jié)點僅在水平方向上的X軸與Y軸方向進行移動,節(jié)點的Z軸坐標由其所處位置的地表高程所決定,因此,在計算節(jié)點受到的虛擬力時無需計算其在Z軸上的分量。

在傳統(tǒng)虛擬力算法中,節(jié)點間虛擬力通常包含引力與斥力。本文僅考慮節(jié)點間的斥力與邊界對節(jié)點的斥力,而不考慮引力。一方面,可以避免引力破壞最佳的平衡狀態(tài),降低網(wǎng)絡的覆蓋率。另一方面,滑坡監(jiān)測中通常要求網(wǎng)絡具有較高的覆蓋率,投入的節(jié)點數(shù)量較多,即使沒有節(jié)點間引力也不容易出現(xiàn)網(wǎng)絡連通性問題,模擬結(jié)果也證實了這一點。

對于任意節(jié)點i和j,只要節(jié)點間距離dij小于距離闕值du,兩節(jié)點間就會產(chǎn)生斥力。節(jié)點i的受到的來自其他節(jié)點的虛擬力的合力Fpi= (Fpix,Fpiy),見式(4)。

(4)

圖3 距離闕值Fig.3 Distance threshold

2.2 邊界對節(jié)點的虛擬力

在實際應用中,部署區(qū)域的邊界問題通常是不容忽視的,因為僅需要覆蓋指定的監(jiān)測區(qū)域,區(qū)域外的覆蓋是無效的。然而,許多已有研究中并沒有充分考慮邊界問題,對邊界的討論也多是針對簡單的二維平面矩形。文獻[25]所用的勢力場方法可以適用于各種復雜形狀邊界,但不能最大化網(wǎng)絡覆蓋率,節(jié)點與邊界之間存在較多的覆蓋盲區(qū)。文獻[17]提出的避障虛擬力算法在ROI為矩形時表現(xiàn)良好,在ROI為多邊形時存在一些問題:單個節(jié)點覆蓋范圍內(nèi)存在多段邊界且內(nèi)角較大時,其邊界虛擬力合力的大小偏大,導致節(jié)點與邊界之間存在較大的覆蓋盲區(qū);在內(nèi)角較小處邊界虛擬力過小,靠近邊界的節(jié)點可能會被其他節(jié)點直接排斥到ROI以外;對于凹多邊形,其直接計算節(jié)點至邊界距離的方法也不適用。

針對滑坡監(jiān)測中常見的ROI邊界形狀,本文提出的邊界虛擬力計算方法為如下。

1) 搜索所有ROI邊界外圍的網(wǎng)格,將搜索得到的所有網(wǎng)格的中心點構(gòu)成的集合稱為E,見圖4(a)。

圖4 邊界對節(jié)點的虛擬力Fig.4 Virtual force of boundary to node

2) 對于節(jié)點i,搜尋E中所有與節(jié)點i的距離小于闕值db的點{e1,e2, …},根據(jù)式(5)計算其對節(jié)點的虛擬力Fei= (Feix,Feiy),見圖4(b)。邊界虛擬力的距離闕值db的取值是基于虛擬力平衡狀態(tài)下,網(wǎng)絡覆蓋率最高來確定的,當du=2R時距離闕值db=R。

(5)

式中dei指ROI邊界外圍網(wǎng)格中心點到節(jié)點i的距離。

3) 邊界對節(jié)點i的虛擬力的方向,即為{e1,e2, …}對節(jié)點i的虛擬力合力的方向。以{e1,e2, …}對節(jié)點i的虛擬力中的最大值max{|Fe|},作為邊界對節(jié)點i的虛擬力大小。節(jié)點i受到的來自邊界的虛擬力Fbi= (Fbix,Fbiy)為:

(6)

2.3 更新節(jié)點位置

節(jié)點i受到的虛擬力合力Fi在X軸和Y軸上的分量為:

(7)

隨機生成的初始節(jié)點位置可能會出現(xiàn)節(jié)點間非常接近的情況,根據(jù)式(4),節(jié)點間的斥力會非常大。節(jié)點在每次迭代中的移動距離與其所受到的虛擬力有關(guān),過大的斥力可能導致節(jié)點在一次移動中直接移動到邊界之外,影響計算結(jié)果。因此將節(jié)點所受虛擬力的最大值限制為Flimit。對于節(jié)點i,其受到的虛擬力合力Fi為:

(8)

在虛擬力合力的作用下將節(jié)點i從原位置(xn-1,yn-1,zn-1)更新到新位置(xn,yn,zn),其中zn是由ROI的地形決定的:

(9)

式中α是步長系數(shù),算法在逼近最優(yōu)解后,不可避免地存在震蕩現(xiàn)象,引入線性遞減函數(shù)α作為步長系數(shù)可以顯著改善這一點,使得節(jié)點隨迭代次數(shù)的增加而逐步逼近最優(yōu)解的位置,α的計算方式見式(10)。其中nmax為最大迭代次數(shù),ns為開始遞減時的迭代次數(shù),本文取ns=nmax/2,使得節(jié)點在前期能夠迅速擴散,加快收斂速度,后期逐漸減小移動步長,使節(jié)點向最優(yōu)解位置不斷逼近。

(10)

2.4 算法偽代碼

綜上所述,本文對傳統(tǒng)虛擬力算法進行了改良,提出了應用于滑坡地形的改良虛擬力算法LMVFA,以滑坡區(qū)域進行節(jié)點部署時,該算法可以更好地提升網(wǎng)絡的覆蓋率。算法實現(xiàn)的偽代碼如下。

輸入:ROI,邊界點集E,節(jié)點數(shù)量M,覆蓋半徑R,通訊半徑C,距離闕值du與db,虛擬力強度系數(shù)cp,最大虛擬力Flimit,最大迭代次數(shù)nmax,節(jié)點初始位置Xs

輸出:節(jié)點部署位置X,網(wǎng)絡覆蓋率,網(wǎng)絡連通性,節(jié)點歷史位置Xh

1: for n = 1 :nmax

2: //計算節(jié)點所受虛擬力

3: fori = 1 : M

4: 根據(jù)式(4)～(8)計算Fi

5: end

6: //更新節(jié)點位置

7: fori = 1 : M

8: 根據(jù)式(9)、(10)計算Xi

9: end

10: Xh[n] = X // 保存節(jié)點歷史位置

11: end

12:根據(jù)式(2)、(3)計算網(wǎng)絡的覆蓋率與連通性

3 算例驗證

本文在MATLAB環(huán)境下實現(xiàn)了上述算法,在多種監(jiān)測區(qū)域下進行了節(jié)點部署,同時使用避障虛擬力算法(obstacle avoidance virtual force algorithm, OAVFA)[17]與虛擬分子力算法(virtual molecular force algorithm,VMFA)[24]作為對比,以驗證本文提出的LMVFA的性能。

節(jié)點的初始位置是隨機生成的,每次計算結(jié)果都有可能不同。因此,在計算時會重復計算100次并從中選出最優(yōu)解,以盡可能地消除隨機初始位置帶來的不利影響。

3.1 二維形狀

為了驗證LMVFA在各種邊界形狀下的性能,考慮到ROI可能出現(xiàn)的各種內(nèi)角情況,使用了正三角形(TRI)、矩形(REC)、正六邊形(HEX)、正十字形(COS)、V形(V)、C形(C)等多種二維平面形狀作為ROI進行節(jié)點部署,見圖5,所有部署區(qū)域的面積近似相等。算法的參數(shù)見表1。

圖5 作為ROI的二維形狀Fig.5 2D shape as ROI

表1 算法的參數(shù)(二維形狀)

圖6顯示了以多種二維形狀作為ROI時,分別使用LMVFA、OAVFA和VMFA部署網(wǎng)絡的覆蓋率。在各種二維形狀中部署節(jié)點時,LMVFA部署的網(wǎng)絡在覆蓋率上均優(yōu)于其他2種算法,尤其是在十字形區(qū)域中,由于該區(qū)域的邊界形狀存在多個大于90°的內(nèi)角,且內(nèi)角處的邊界作用力所影響的區(qū)域較為集中,在此情況下,LMVFA對邊界虛擬力計算方法的改良表現(xiàn)出更為明顯的優(yōu)勢,因此在網(wǎng)絡的整體覆蓋率上相差更大。

圖6 二維形狀中不同算法的網(wǎng)絡覆蓋率Fig.6 Network coverage of different algorithms in 2D shape

3.2 滑坡區(qū)域

為了驗證LMVFA在各種滑坡區(qū)域中的性能,選取了3個滑坡區(qū)域[26-28]作為ROI進行了計算,滑坡區(qū)域的地形與邊界見圖7,算法的參數(shù)見表2。作為ROI的3個滑坡區(qū)域在邊界形狀、坡度、面積上都有一定差異,能更好地反映算法在各種滑坡區(qū)域中的性能。

圖7 滑坡區(qū)域的地形示意圖Fig.7 Topographic map for landslide area

表2 算法的參數(shù)(滑坡區(qū)域)

3個滑坡區(qū)域的面積相差較大,而滑坡監(jiān)測中通常要求網(wǎng)絡具有較高的覆蓋率,因此在3個滑坡區(qū)域中投放了不同數(shù)量的節(jié)點。其中,滑坡區(qū)域C由于面積較大,且整體形狀較為狹長,在最大迭代次數(shù)為1 000無法完全達成虛擬力平衡狀態(tài),因此將其最大迭代次數(shù)增加到2 000。在實際應用中,可以通過調(diào)整虛擬力強度系數(shù)cp來加快虛擬力的平衡過程,此處為了便于將LMVFA與其他兩種算法進行比較,僅增加了最大迭代次數(shù)nmax。

圖8顯示了以3個滑坡區(qū)域作為ROI時,分別使用LMVFA、OAVFA和VMFA所部署網(wǎng)絡的覆蓋率?？梢钥闯?LMVFA部署的網(wǎng)絡在覆蓋率上均優(yōu)于其他2種算法。

圖9顯示了分別使用3種算法時,網(wǎng)絡的覆蓋率隨迭代次數(shù)的變化情況。初期OAVFA的網(wǎng)絡覆蓋率增長得更快,但很快就陷入節(jié)點震蕩狀態(tài)。LMVFA和VMFA的覆蓋率則隨著迭代次數(shù)的增加穩(wěn)步增長。

圖8 滑坡區(qū)域中不同算法的網(wǎng)絡覆蓋率Fig.8 Network coverage of different algorithms in landslide region

圖9 網(wǎng)絡覆蓋率隨迭代次數(shù)的變化Fig.9 Change of network coverage with the number of iterations

滑坡區(qū)域的俯視圖與LMVFA所部署網(wǎng)絡中各節(jié)點間的連通路徑見圖10。從總體上來看,網(wǎng)絡中沒有孤立的節(jié)點,且大多數(shù)的節(jié)點均具有多條連接路徑,在實際應用中能較好地應對單一節(jié)點的突發(fā)故障,而不至于造成大量節(jié)點的失聯(lián),可以說明LMVFA部署的網(wǎng)絡具有較好的連通性。

4 結(jié) 語

圖10 網(wǎng)絡的連通性Fig.10 Network connectivity

本文對滑坡區(qū)域中部署WSN節(jié)點的方法進行了研究,提出一種改良的虛擬力算法——LMVFA。該算法以網(wǎng)絡覆蓋率為優(yōu)化目標,能夠完成各種滑坡監(jiān)測區(qū)域的節(jié)點部署任務。在多種形狀的二維平面區(qū)域和三個不同的三維曲面區(qū)域(滑坡監(jiān)測區(qū)域的地表)中進行WSN節(jié)點的模擬部署,計算結(jié)果表明,在網(wǎng)絡覆蓋率方面,LMVFA優(yōu)于已有的虛擬力算法OAVFA與VMFA。

本文提出的算法僅適用于單個節(jié)點的覆蓋范圍內(nèi)地形起伏相對平緩的情況,無法檢測到局部陡峭地形對節(jié)點間信號傳輸?shù)淖钃酢Ｒ虼?在后續(xù)研究中需要進一步探討適用于陡峭地形的節(jié)點部署方法。