一種適用于帶狀區域的WSN節點覆蓋優化方法

郝占軍,侯姣姣,黨小超,曲南江

(1.西北師范大學 計算機科學與工程學院,蘭州 730070; 2.甘肅省物聯網工程研究中心,蘭州 730070)

0 概述

在無線傳感器網絡(Wireless Sensor Network,WSN)中,將多個傳感器節點有組織地部署在待監測區域內,這些節點協同有序進行信息監測并把收集到的信息周期性地發送至基站。然而傳感器節點通常需要部署在野外環境中,難以進行充電或替換,當電池電量不足時節點會失效或者由于非人為因素[1-2]節點遭到破壞時會嚴重影響網絡的運行。

在隧道、礦井、大型橋梁等帶狀區域中部署傳感器網絡時,由于其形態特殊,節點通常會被部署為狹長分布的狀態且需要將收集的數據定期發送至一側的基站,而實際應用中傳感器節點通信距離有限,因此需采用多跳的方式進行數據傳輸。此時,靠近基站區域的節點需要負責更多的轉發任務,因此靠近基站的網絡所轉發的數據量大幅增加,消耗能量也增多。但節點自身能量有限,容易過早耗盡能量從而導致節點死亡,并且使得基站周圍形成“網絡能量空洞”[3-4]。這些失效節點所收集的數據不能轉發至基站,網絡提前結束運行,但此時網絡中仍有大量能量未被使用,嚴重降低了網絡使用效率。傳統部署方法和路由協議在帶狀區域結構下有較大的局限性,因此需要考慮如何有效部署傳感器節點來解決能量空洞問題,在保證無線網絡實現有效覆蓋和連通的同時,均衡網絡能耗,延長網絡生命周期。

為均衡網絡能耗,研究人員提出了網絡分簇層次模型并針對線型區域網絡中的部署問題做了進一步的研究。文獻[5]根據簇頭節點的競爭范圍構造規模不同的簇及簇頭節點進行多跳通信來均衡簇頭節點的能量消耗。文獻[6]基于經典LEACH算法,在監測區域中將簇內節點數控制在一定范圍內,并合并規模極小的簇來均衡各分簇能量。文獻[7]提出簇頭競爭算法將網絡劃分為幾何尺寸不同的簇,并結合簇間路由來節約網絡能量。但上述方法的簇間路由均未考慮節點的部署情況,因此不適用于帶狀區域的網絡部署。文獻[8]提出一種DEBUC協議來均衡簇內和簇間能耗,采用簇頭競爭算法控制不同距離簇的大小,但不適用于距離較長的帶狀區域網絡。文獻[9]在線型無線傳感器網絡中采用等腰三角形劃分的方式,實現對區域的K重覆蓋,并對傳感器節點分組以均衡網絡整體能耗。文獻[10]針對礦井巷道環境提出一種分層路由協議,采用分簇的方式在數據轉發量較大的區域進行較大規模的簇劃分,但由于簇頭節點間距離的不同使得無線傳感器網絡能量的消耗速度達不到最優。本文提出一種以菱形分區方式劃分帶狀區域的節點部署方法,利用等距多跳傳輸降低網絡能耗,并在等距分簇后進一步計算得出各簇所需簇頭節點的數量,通過簇頭節點非均勻部署均衡帶狀區域的網絡能耗并延長網絡生命周期。

1 能量模型

1.1 傳感器節點能量模型

本文采用文獻[11]中的傳感器節點能量消耗模型,設置閾值d0(d0為常數,取值與節點應用環境有關),根據發送節點和接收節點之間的距離與d0的關系計算能耗,當兩者之間距離小于d0時,符合自由空間模型,發送節點消耗的能量與兩者之間距離的平方成正比;否則使用多路衰減模型,即與距離的4次方成正比。在數據傳輸過程中,發送節點的能耗ETx(l,d)主要是發送無線電路和放大器的能耗[12-13]。在節點間距為d時,傳送lbit信息的能耗為:

(1)

接收節點的能耗ERx(l)主要是無線電路中用于數據傳輸的能耗Eelec。當接收lbit數據時,傳感器節點的能耗為:

ERx(l)=lEelec

(2)

其中,εfs和εamp分別表示接收節點和發送節點在不同距離區間范圍內,發送放大器傳送每比特數據所需的能量。

1.2 簇頭節點能量模型

本文中的數據通過簇頭節點進行多跳傳輸,其能耗包含接收簇內節點信息以及數據轉發兩部分。假設簇內m個節點中只有1個簇頭節點和(m-1)個簇內節點,在一次節點傳輸過程中的數據量簇頭節點為l,則簇頭節點接收簇內數據的能耗為:

ECH=(m-1)lEelec

(3)

簇頭節點在數據轉發時消耗的能量ECHtoCH中包含接收上一級簇頭節點數據的能耗ETx和轉發數據至下一級簇頭節點的能耗ERx兩部分,具體為:

ECHtoCH=ERx+ETx=

(4)

其中,dCHtoCH表示兩個簇頭節點的間距。

所有的簇頭節點分為兩類:第1類簇頭節點,負責簇內數據傳輸;第2類簇頭節點,充當中繼節點轉發其他簇數據[14]。第1類簇頭節點的能耗由接收簇中節點數據的能耗ECH和發送簇中數據的能耗ECHto組成,第2類簇頭節點的能耗由接收和轉發其他簇頭節點的數據能耗ECHtoCH和第1類簇頭節點的能耗組成,具體為:

(5)

其中,Ech代表簇頭節點能耗,ECHto根據式(1)計算得到。

2 節點部署方法與量化分析

在無線傳感器網絡中,通過節點部署對網絡結構進行優化設計是延長網絡實際應用壽命和擴大網絡可延展性[15-16]的重要方法之一,尤其在帶狀區域中,通過設計傳感器節點的部署結構能有效平衡網絡能量消耗不均勻引起的能量空洞問題,延長網絡生命周期。本節主要介紹了等距網絡分簇方法,以菱形劃分帶狀區域部署節點實現網絡覆蓋,并通過進一步計算驗證了簇頭節點的非均勻部署在延長網絡生命周期方面的有效性。

2.1 基于菱形劃分的節點部署方法

2.1.1 節點部署方法原理

針對帶狀區域的特殊結構,基于菱形劃分區域并固定部署傳感器節點,以等距分簇的方式來降低網絡在數據傳輸過程中的能量消耗。

定義1(基本監測區域) 基本監測區域(Basic monitoring Area,BA)是以菱形為基本單元劃分帶狀區域,在邊界菱形頂點處部署傳感器節點得到的帶狀監測區域如圖1所示,其中兩個節點只負責感知所在區域內的數據。

圖1 菱形區域模型

定義2(一般監測區域) 一般監測區域(General monitoring Area,GA)是指只考慮通過兩側傳感器節點的聯合感知能有效覆蓋的帶狀區域(如圖2所示),且由BA線性組合而成。

圖2 帶狀區域模型

定義3(簇) 簇可以劃分為多個菱形,包括簇頭節點和簇內節點兩部分。簇內節點負責感知數據,簇頭節點負責轉發數據,且簇頭節點初始部署在簇的中心位置。

定理1設兩個簇頭節點間的距離為di,基站與最遠簇頭節點間的距離為D,當d1=d2=…=dk=D/k時,網絡中傳輸lbit數據的能耗Ek取值最小。

證明根據能量模型,在網絡中傳輸lbit數據的能耗Ek為:

(6)

本文提出將帶狀區域劃分為多個菱形后根據定理1所證結果等距分簇并部署傳感器節點。假設基站部署在帶狀區域的左側,將距離基站最遠的簇定義為第一個簇,其簇頭節點為一級簇頭節點,根據與基站距離的變化依次為二級簇頭節點、三級簇頭節點、……、靠近基站最近的k級簇頭節點,令整個帶狀區域具有分簇層次結構,且這k個簇頭節點將距離D依次劃分為d1,d2,…,dk。在這些簇頭節點中,一級簇頭節點產生的數據需經過剩余簇頭節點的多跳轉發,中間第i級簇頭需要接收i-1級簇頭節點所轉發的數據,同時需要向i+1級簇頭節點轉發數據。

2.1.2 節點部署方法描述

基于菱形劃分的節點部署方法具體步驟如下:

步驟1初始化長為a、寬為b的帶狀區域。

步驟3網絡等距分簇,根據定理1可得,當d1=d2=…=dk=D/k時,網絡中傳輸lbit數據的能耗Ek取值最小,因此對帶狀區域進行等距分簇。計算最佳分簇間距dopt和分簇后簇的最佳數目n,根據菱形大小得出簇內菱形個數。

步驟5在帶狀區域邊界菱形頂點處部署簇內節點,在菱形對角線上線性部署簇頭節點,網絡工作初期選擇中心位置作為簇頭節點的初始位置,將其余簇頭節點設為休眠狀態。

步驟6在網絡運行過程中,當簇頭節點的能量低于可進行工作的最小值時,選擇簇內的休眠簇頭節點作為新的簇頭節點進行替換,并廣播新簇頭節點的位置信息,代替失效節點繼續工作。

2.2 節點部署的量化分析

上文利用等距分簇降低網絡能耗的節點部署方法,本節主要通過計算并分析帶狀區域網絡部署時的分簇個數和各簇內的最優簇頭節點數量,實現監測區域的有效覆蓋。

2.2.1 最佳分簇間距分析

(7)

圖3 帶狀區域節點覆蓋效果

當簇內節點A、B、C、D處部署的節點感知半徑r=AG時,感知區域正好可以相交于菱形位于帶狀區域內的頂點G、I、F處,依此類推,即可對帶狀區域實現網絡覆蓋。證畢。

根據定理2求出帶狀區域可劃分的菱形個數為:

(8)

結合定理1,簇頭節點將菱形劃分后的帶狀區域等距劃分為相等的簇。對式(6)的能耗公式進行求導得到:

(9)

令E′k=0,可得最佳分簇間距dopt為:

(10)

在得到分簇結果后,網絡中簇的最佳數目為:

(11)

在計算確定了網絡監測區域的分簇個數和具體的菱形劃分個數后部署傳感器節點,在帶狀區域邊界交匯的菱形頂點處部署簇內節點,在菱形對角線上部署簇頭節點,并將簇頭節點有選擇地放在每個等間隔簇區間的幾何中心上。

2.2.2 簇頭節點數量的優化分析

為進一步均衡網絡能耗,下文將分析并優化各簇內簇頭節點的數量。在帶狀區域網絡中簇頭節點的數據轉發量受到其與基站距離的影響,如果一個簇中只有一個簇頭節點,各簇內簇頭節點的能量消耗不均,靠近基站的簇中簇頭節點無法長時間轉發大量數據。因此,在靠近基站的簇內部署更多數量的簇頭節點,會延長網絡工作時間。

依據式(4)的能量模型,可計算簇i的能量消耗速度為:

(12)

簇i中耗盡所有簇頭節點能量所需的時間為:

(13)

其中,Ni為簇i中的簇頭節點數目,Einit為簇頭節點初始狀態下所具有的能量,E0為可進行工作的能量最小值。

令各簇能量耗盡的時間相等,即Ti=Ti-1,則有:

(14)

化簡式(14)得到:

(15)

(16)

遞推式(16)得到:

(17)

化簡式(17)得到:

(18)

(19)

(20)

由式(20)可得越靠近基站的簇,i值越大,簇頭節點的數量越多,如圖4所示。在計算出不同簇內簇頭節點的數目后,將這些簇頭節點線性部署在各自的簇內。

圖4 簇頭節點非均勻部署效果

因此,在菱形劃分的基礎上對帶狀區域進行簇劃分,確定等距分簇的最佳間距,計算得出每個簇內的最優簇頭節點數量,將簇頭節點在菱形對角線上進行線性部署。網絡工作初期選擇中心位置作為簇頭節點的初始位置并將其余簇頭節點設為休眠狀態,當簇頭節點的能量低于可供節點工作的最小值時更換簇頭節點的位置。

2.3 網絡能耗分析

在帶狀區域網絡數據的發送和接收過程中,能耗主要由簇頭節點產生,為有效降低和平衡網絡能耗,本文在等距分簇的基礎上,進一步在不同簇內部署非均勻數目的節點,并與簇頭節點均勻部署方法進行對比,同時對分別采用兩種方法的網絡生命周期進行分析[17]。

根據本文能量模型,距離基站最遠的簇頭節點在接收和轉發簇內節點數據的過程中會產生能耗,其進行一次數據接收并轉發的總能耗為:

(21)

由于第i個簇頭節點為中繼節點,負責中繼轉發數據,因此在簇i中進行一次數據傳輸的能耗為:

Ei=(m-1)lEelec+(i-1)lEelec+

(22)

由式(22)可得在靠近基站的簇n中進行一次數據傳輸的能耗為:

En=(m-1)lEelec+(n-1)lEelec+

(23)

令各簇能量耗盡的時間相等,計算各個簇內非均勻的節點數目可知,整個帶狀區域網絡的生命周期等同于第n個簇內簇頭節點的生命周期,即:

(24)

在采用各簇內均勻部署簇頭節點的部署方法時,每個簇內簇頭節點的個數為N/n,靠近基站的簇數據傳輸量會直接影響網絡的生命周期。在該簇中簇頭節點接收數據的能耗為:

ETx=(m-1)lEelec+(n-1)lEelec

(25)

簇頭節點轉發所有數據的能耗為:

ERx=nl(Eelec+εfsdn2)

(26)

當均勻部署簇頭節點時,簇n的總能耗En2為:

En2=ERx+ETx

(27)

由此可得網絡生命周期為:

(28)

定理3在帶狀區域無線傳感器網絡等間距分簇的情況下,根據簇與基站的關系,簇頭節點非均勻部署時網絡生命周期大于簇頭節點均勻部署時的網絡生命周期。

證明根據式(23)和式(27)可得,在等距部署時,均勻和非均勻部署條件下靠近基站的簇內簇頭節點進行數據傳輸的能量消耗相同,即:

En1=En2

(29)

(30)

由式(24)得到非均勻部署簇頭節點時的網絡生命周期Tnon-uniform為:

(31)

(32)

由此得到Tnon-uniform>Tuniform,證畢。

由定理3的證明得出本文提出的簇頭節點非均勻部署方法相比簇頭節點均勻部署方法更能延長網絡生命周期,提高網絡利用率。

3 實驗設置與結果分析

3.1 實驗環境與參數設置

為驗證本文方法的有效性,在Matlab2016a中進行仿真實驗,在具有理想MAC協議的假設前提下,忽略數據轉發中的丟包問題[18]。仿真基本參數設置如表1所示。

表1 仿真參數設置

3.2 結果分析

本文主要是針對帶狀區域提出的節點部署方法,將帶狀區域網絡劃分為規模相同的簇,簇頭節點分布在一條直線上,根據簇與基站間的距離非均勻部署簇頭節點。

3.2.1 等距分簇方法性能分析

為得到等距分簇規模與網絡存活節點數目及網絡剩余能量的關系,在Matlab中仿真1 200 m×30 m的帶狀區域,簇內節點的感知半徑為20 m,分別設置3種實驗場景:場景1中簇間距d1為80 m,分簇個數n1為15,其小于最佳分簇個數;場景2中簇間距d2為60 m,分簇個數n2為20,其接近最佳分簇個數;場景3中簇間距d3為48 m,分簇個數n3為25,其大于最佳分簇個數。在仿真時,由式(20)計算簇頭節點個數。

分析網絡運行時的能耗情況,是評價節點部署方法的重要手段。圖5表示在以上3種不同分簇場景中,帶狀區域內網絡存活節點數目與網絡工作時間的關系,可以看出隨著網絡工作時間的延長,存活節點數目不斷減少。圖6表示網絡剩余能量與網絡工作時間的關系,網絡剩余能量隨著時間的增長處于持續減少的狀態。從圖5曲線變化情況來看,網絡運行至100輪時,3種實驗場景中存活的節點數目幾乎相同,這時網絡消耗的總能量為最少狀態。從100輪開始,在場景1中節點數目開始減少,以緩慢趨勢減小到網絡工作時間為500輪后,節點數目急劇下降,在670輪時網絡結束工作。在場景3中,在工作時間為400輪時網絡節點出現消耗并從700輪開始節點數目減少幅度加大,網絡總體工作時間大于場景1下的網絡工作時間。與場景1和場景3中的情況相比,在場景2中網絡節點出現消耗的時間延后至650輪,當場景1和場景3中網絡結束運行時,此場景中仍有大部分節點在繼續工作,且網絡工作時間幾乎延長至1 000輪,遠遠大于場景1和場景3下的網絡工作時間。結合圖6曲線進行分析,在場景2中網絡剩余能量高于其他兩種場景,代表了在初始能量相同的狀況下,在場景2中的網絡能量消耗最小,有效節約了網絡總體能量且延長了網絡工作時間。實驗結果表明:當1 200 m×30 m的帶狀區域分為20個大小相等的簇且間距取60 m時得到最優覆蓋結果,可以有效降低整個帶狀區域網絡的能量消耗。

圖5 網絡存活節點數隨網絡工作時間的變化情況

圖6 網絡剩余能量隨網絡工作時間的變化情況

3.2.2 簇頭節點部署方法性能分析

網絡生命周期和網絡剩余能量是評價網絡性能的重要指標[19]。為驗證簇頭節點非均勻部署方法的性能優勢,選取長度為600 m、900 m、1 200 m、1 500 m、1 800 m、2 100 m、2 400 m,寬度為30 m的帶狀區域進行仿真實驗。圖7為不同帶狀區域長度內簇頭節點數目在均勻和非均勻部署兩種情況下的生命周期對比結果。圖8為在實驗進行500輪后,不同帶狀區域長度下兩種部署方法的剩余能量百分比。

圖7 網絡生命周期隨帶狀區域長度的變化情況

圖8 網絡剩余能量隨帶狀區域長度的變化情況

從圖7可以看出,當簇頭節點非均勻部署時,網絡生命周期明顯更長。在不同長度的帶狀區域中,轉發數據所需消耗的能量與簇頭節點到基站的距離有關。通過簇頭節點的計算公式可以得出,非均勻部署簇頭節點時,靠近基站的第一個簇內簇頭節點的數目最多,因此當各簇內簇頭節點數目均勻且相等時,容易出現網絡負載不均的問題從而影響網絡整體的生命周期。該問題在帶狀區域長度為1 800 m時最為明顯,非均勻部署的生命周期是均勻部署生命周期的1.8倍。采用非均勻部署方法時通過計算在越靠近基站的簇內部署更多的簇頭節點,令各簇內能量耗盡時間保持一致,從而有效延長網絡生命周期。從圖8可以看出,在實驗進行500輪后不同部署方法下的網絡剩余能量百分比,當不同長度的帶狀區域中簇頭節點數目非均勻部署時,各個簇的能量消耗速度較均衡,網絡剩余能量百分比的變化穩定保持在20%左右。當簇頭節點數目均勻部署時,由于簇頭節點轉發數據所需消耗的能量不均,更容易使網絡提前結束,減少網絡工作時間,并且有較多的剩余能量。隨著帶狀區域長度的變化,非均勻部署方法在網絡能耗均衡方面的優勢越來越明顯,并且網絡剩余能量較為穩定,明顯優于均勻部署方法。因此,本文采用簇頭節點非均勻部署方法更為合理。

3.2.3 節點覆蓋方法性能分析

為進一步驗證本文節點覆蓋方法在帶狀區域內的能量有效性,從存活節點數目、網絡總能耗兩方面與EDNU、EECS方法進行比較。為盡可能考慮實際應用情況,選取1 500 m×30 m的帶狀區域進行仿真,結果如圖9和圖10所示。

圖9 網絡存活節點數對比

圖10 網絡總能耗對比

圖9和圖10分別比較了在3種方法下網絡工作時間變化和節點存活數目、網絡總能耗的關系,可以看出在帶狀區域網絡中,本文方法與其他兩種方法相比更有優勢。從圖9可以看出,在分別使用3種方法時,網絡開始運行至工作時間為400輪時,存活節點數目保持不變。從網絡工作時間為400輪開始,EECS方法下的網絡存活節點數目開始減少,在500輪～630輪減少幅度加大,當網絡工作時間最長運行至800輪時,大部分節點已經死亡,網絡結束工作[20]。EDNU方法在網絡時間為540輪時存活節點數目發生變化,網絡工作時間持續到900輪結束。而在本文方法中,節點數目的變化曲線更加平緩且網絡工作時間更長,其中存活節點數目開始減少的時間發生在620輪時,當網絡工作時間超過900輪時,網絡仍有較多的存活節點,直至網絡運行時間為1 000輪時才結束運行。本文方法與EDNU方法都是針對網絡能耗不均衡且容易出現網絡空洞問題提出的改進方法,兩者都采用等距分簇和簇間多跳方式,但本文方法中網絡工作時間相對EDNU方法顯著延長。結合圖10曲線分析可知,隨著工作時間的增加和節點數目的減少,網絡能量一直處于消耗狀態,但在3種方法中,本文方法保證了最少的網絡總能耗和更長的網絡運行時間,性能優于其他兩種方法。

圖11比較了在網絡工作時間不斷增加時3種方法的網絡數據傳輸時延。可以看出,本文方法的數據傳輸時延明顯較小。在EECS方法中數據傳輸時延范圍為0.6 s～0.8 s,EDNU方法保持在0.4 s左右,而本文方法數據傳輸時延始終保持在0.2 s以內,加快了帶狀區域中網絡的數據傳輸速度,與其他兩種方法相比更具優勢。圖12統計了3種方法在6次仿真實驗中的網絡數據傳輸成功率,可以看出本文方法的數據傳輸成功率明顯高于其他兩種方法。將6次實驗結果進行對比分析可知,使用本文方法時數據傳輸成功率最高達到97%,最低為94%,EDNU方法的數據傳輸成功率為90%～93%,而使用EECS方法時的傳輸成功率低于88%。因此,在帶狀區域中本文方法在數據傳輸方面更具穩定性與可靠性。

圖11 網絡數據傳輸時延對比

圖12 網絡數據傳輸成功率對比

4 結束語

本文提出一種以菱形分區方式劃分帶狀區域的WSN節點覆蓋方法,通過等距分簇后在菱形固定位置部署傳感器節點,實現對帶狀區域的網絡覆蓋。根據簇頭節點與基站的距離計算不同簇內的簇頭節點數量,從而盡可能均衡網絡負載并提高網絡利用率。理論分析與實驗結果表明,本文節點覆蓋方法能有效提高網絡生命周期。后續將研究WSN節點部署方法中的覆蓋冗余問題,進一步均衡網絡能耗并延長網絡生命周期。