一種改進(jìn)的無線傳感器網(wǎng)絡(luò)密度自適應(yīng)冗余節(jié)點(diǎn)調(diào)度算法

何少尉

（浙江郵電職業(yè)技術(shù)學(xué)院，浙江 紹興 312366）

0 引 言

無線傳感器是一種自帶能源并基于某種通信協(xié)議進(jìn)行通信，能夠?qū)崟r(shí)感知環(huán)境參數(shù)并傳輸至終端客戶的小體積傳感器[1]。無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）是基于無線通信技術(shù)將無線傳感器自由組織而成的分布式網(wǎng)絡(luò)，具有組網(wǎng)靈活、覆蓋廣泛、環(huán)境適應(yīng)性強(qiáng)等優(yōu)點(diǎn)，在軍事、環(huán)境監(jiān)測、醫(yī)療等眾多領(lǐng)域得到了廣泛應(yīng)用[2-3]。在WSN中，所有節(jié)點(diǎn)的組織都是隨機(jī)的，這會導(dǎo)致部署節(jié)點(diǎn)數(shù)量遠(yuǎn)遠(yuǎn)大于所需數(shù)量，導(dǎo)致某些節(jié)點(diǎn)的感知區(qū)域互相重疊。若網(wǎng)絡(luò)中所有節(jié)點(diǎn)同時(shí)運(yùn)行，節(jié)點(diǎn)之間存在許多重疊區(qū)域，這不僅損耗大量的能量，而且會增加數(shù)據(jù)沖突及其融合的復(fù)雜性[4]。此外，由于傳感器節(jié)點(diǎn)的能量均為受限狀態(tài)，當(dāng)網(wǎng)絡(luò)部署完畢后，節(jié)點(diǎn)的能量補(bǔ)充較為困難[5]。因此，降低節(jié)點(diǎn)的能耗，對于延長WSN的生存時(shí)間有著非常重要的價(jià)值[6]。節(jié)點(diǎn)休眠調(diào)度是WSN降低能耗、延長生存時(shí)間的有效途徑，其基本思想是利用WSN中節(jié)點(diǎn)的冗余性，使WSN中部分節(jié)點(diǎn)保持活躍，部分節(jié)點(diǎn)保持休眠，以充分提高節(jié)點(diǎn)的能源利用率，延長網(wǎng)絡(luò)的生存時(shí)間[7]。在節(jié)點(diǎn)休眠調(diào)度算法中，傳感器節(jié)點(diǎn)首先判斷自己是否為冗余節(jié)點(diǎn)，并根據(jù)判斷結(jié)果來決定自己何時(shí)進(jìn)入休眠狀態(tài)。因此，對節(jié)點(diǎn)休眠調(diào)度算法研究的主要目的是在確保整個(gè)網(wǎng)絡(luò)的覆蓋區(qū)域和連通性的同時(shí)，保持更多數(shù)量的節(jié)點(diǎn)處于休眠狀態(tài)。

目前，人們對節(jié)點(diǎn)休眠調(diào)度算法進(jìn)行了大量的研究。文獻(xiàn)[8]提出Ditian算法，利用各節(jié)點(diǎn)間的互相通信，判斷鄰居節(jié)點(diǎn)能否覆蓋其感知區(qū)域，并決定本節(jié)點(diǎn)是否休眠，以達(dá)到休眠的目的。文獻(xiàn)[9]提出基于數(shù)據(jù)相似度的節(jié)點(diǎn)休眠調(diào)度策略，能從冗余節(jié)點(diǎn)的不同聚類來篩選休眠節(jié)點(diǎn)。文獻(xiàn)[10]提出一種樹型協(xié)議，通過創(chuàng)建成對的節(jié)點(diǎn)，在節(jié)點(diǎn)間進(jìn)行休眠模式切換。文獻(xiàn)[11]提出一種與節(jié)點(diǎn)位置無關(guān)的節(jié)點(diǎn)休眠調(diào)度算法。文獻(xiàn)[12]提出一種基于動態(tài)能量感知的節(jié)點(diǎn)休眠調(diào)度算法。上述算法均從某個(gè)特定角度對WSN中節(jié)點(diǎn)的休眠調(diào)度進(jìn)行了研究，本文針對Ditian算法對WSN節(jié)點(diǎn)低密度狀態(tài)下效果不佳的不足，提出一種改進(jìn)的密度自適應(yīng)冗余節(jié)點(diǎn)調(diào)度算法。

1 Ditian算法簡介

節(jié)點(diǎn)休眠調(diào)度方法是讓不需要工作的節(jié)點(diǎn)進(jìn)入休眠狀態(tài)，在“偵聽”“休眠”模式之間不斷切換，使傳感器節(jié)點(diǎn)輪換工作。這樣可以增加網(wǎng)絡(luò)使用時(shí)間，提升節(jié)點(diǎn)能量效率。

傳感器節(jié)點(diǎn)處于休眠狀態(tài)時(shí)能量損耗最少。以某傳感器網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)為例，該節(jié)點(diǎn)在一個(gè)周期內(nèi)發(fā)送、接收、空閑和休眠狀態(tài)時(shí)的能耗對比如圖1所示?？梢悦黠@看出，節(jié)點(diǎn)在休眠狀態(tài)時(shí)的功耗僅為空閑狀態(tài)的很小一部分，在覆蓋率和連通度不發(fā)生變化的前提下，可以通過提高節(jié)點(diǎn)進(jìn)入休眠狀態(tài)的數(shù)量來實(shí)現(xiàn)能量的低消耗，用節(jié)點(diǎn)間相互的交替工作來減少網(wǎng)絡(luò)的能耗。節(jié)點(diǎn)休眠調(diào)度算法一般通過合理的資源調(diào)度算法，盡可能增加節(jié)點(diǎn)的休眠時(shí)間，減少節(jié)點(diǎn)的發(fā)送、接收和空閑時(shí)間。Ditian算法就是節(jié)點(diǎn)休眠調(diào)度算法的一種。

圖1 傳感器節(jié)點(diǎn)能量消耗情況

Ditian算法的前提是有一個(gè)節(jié)點(diǎn)被周圍節(jié)點(diǎn)全覆蓋。若存在節(jié)點(diǎn)v，與其鄰居節(jié)點(diǎn)u集合滿足N(v)={v|d(u,v)≤rs}，則稱節(jié)點(diǎn)v稱為冗余節(jié)點(diǎn)。式中，rs是門限距離，d(u,v)表示節(jié)點(diǎn)u到節(jié)點(diǎn)v的歐幾里得距離，可表示為

式中：(xu,yu)、(xv,yv)表示節(jié)點(diǎn)u、v的坐標(biāo)。

如圖2所示，對于節(jié)點(diǎn)A而言，被周圍節(jié)點(diǎn)B覆蓋的區(qū)域?yàn)榛1B1P2和弧P1A1P2相交的地方。由圖中幾何關(guān)系可知，節(jié)點(diǎn)間的重疊面積不易計(jì)算，而扇形P1B1P2的面積不難計(jì)算。為使計(jì)算簡單，只需計(jì)算扇形P1B1P2對應(yīng)的圓心角∠P1AP2取值在[0,2π)中，即可認(rèn)定該節(jié)點(diǎn)為冗余節(jié)點(diǎn)。

圖2 冗余節(jié)點(diǎn)判斷示意圖

因此，Ditian算法中，首先計(jì)算節(jié)點(diǎn)與基準(zhǔn)軸的夾角，當(dāng)該節(jié)點(diǎn)與周圍鄰居節(jié)點(diǎn)的角度在[0,2π)時(shí)，即認(rèn)為該節(jié)點(diǎn)為冗余節(jié)點(diǎn)。

式中：βui→v表示從集合N(v)中節(jié)點(diǎn)ui與節(jié)點(diǎn)v之間的夾角。

如圖3所示，節(jié)點(diǎn)A被節(jié)點(diǎn)B，C和D覆蓋，∠BAC+∠CAD+∠DAB=2π。按照Ditian算法，節(jié)點(diǎn)A不是冗余節(jié)點(diǎn)。對于節(jié)點(diǎn)A的錯(cuò)誤判斷，導(dǎo)致最終判斷出的冗余節(jié)點(diǎn)數(shù)目偏少。在Ditian算法中，節(jié)點(diǎn)在被覆蓋時(shí)，采用夾角判定。但Ditian算法具有一定的局限性，僅適用于半徑范圍內(nèi)的節(jié)點(diǎn)，只能得到比較小的冗余節(jié)點(diǎn)集合。因此，Ditian算法是節(jié)點(diǎn)密度較高的情況下的首選。而在節(jié)點(diǎn)密度較低的情況下，Ditian算法的效果將會受到嚴(yán)重影響。

圖3 扇區(qū)覆蓋誤差示意圖

2 改進(jìn)的密度自適應(yīng)冗余節(jié)點(diǎn)調(diào)度算法

針對Ditian算法對探測區(qū)域內(nèi)低密度不適用的情況，本文提出一種改進(jìn)的密度自適應(yīng)冗余節(jié)點(diǎn)調(diào)度算法，利用最少節(jié)點(diǎn)覆蓋全部檢測范圍，降低節(jié)點(diǎn)部署的數(shù)目。

2.1 密度自適應(yīng)冗余節(jié)點(diǎn)調(diào)度算法

在WSN中，若某節(jié)點(diǎn)檢測的范圍內(nèi)節(jié)點(diǎn)數(shù)目過多，即節(jié)點(diǎn)密度過大，僅需較少的周圍節(jié)點(diǎn)就能判斷出覆蓋節(jié)點(diǎn)。相反，若節(jié)點(diǎn)的密度過小，則需要檢查節(jié)點(diǎn)監(jiān)測范圍外的周圍節(jié)點(diǎn)。故節(jié)點(diǎn)的密度大小和分布方式對于WSN內(nèi)節(jié)點(diǎn)的調(diào)度有著重要價(jià)值。本文提出一種改進(jìn)的密度自適應(yīng)冗余節(jié)點(diǎn)調(diào)度算法，可以依據(jù)不同的節(jié)點(diǎn)密度自適應(yīng)冗余節(jié)點(diǎn)調(diào)度算法。此算法能夠有效地降低檢測范圍外的節(jié)點(diǎn)個(gè)數(shù)，并根據(jù)節(jié)點(diǎn)密度執(zhí)行節(jié)點(diǎn)休眠。

假定WSN中全部節(jié)點(diǎn)的功能結(jié)構(gòu)均相同，通信和監(jiān)測范圍均為圓形。令監(jiān)測直徑為通信半徑的一半，利用定位系統(tǒng)確認(rèn)出節(jié)點(diǎn)位置。算法的流程如下。

（1）系統(tǒng)初始化，節(jié)點(diǎn)vi傳送位置、能量信息給其周圍節(jié)點(diǎn)Ni={vj|d(vi,vj)＜2rs,vj＜Ni}。

（2）獲取周圍節(jié)點(diǎn)數(shù)據(jù)，確立周圍節(jié)點(diǎn)表，將節(jié)點(diǎn)從近到遠(yuǎn)排列。

（3）把周圍節(jié)點(diǎn)表上的節(jié)點(diǎn)分類：Ni1={vi1|d(vi1,vj)＜2rs,vi1＜Ni}，Ni2={vi2|d(vi2,vj)＜2rs,vi2＜Ni}。

（4）STEP4：當(dāng)Ni1∈?，即節(jié)點(diǎn)vi監(jiān)測的范圍內(nèi)沒有周圍節(jié)點(diǎn)，則判斷不可以覆蓋此節(jié)點(diǎn)，算法結(jié)束。如果節(jié)點(diǎn)監(jiān)測的范圍C(v)內(nèi)沒有周圍節(jié)點(diǎn)，由于圓心很難被覆蓋，所以C(v)不能全部被覆蓋。

（5）當(dāng)Ni1∈φ，從近到遠(yuǎn)檢查vi范圍內(nèi)的周圍節(jié)點(diǎn)，推測此節(jié)點(diǎn)與周圍節(jié)點(diǎn)的覆蓋角。如圖4所示。

圖4 vi半徑內(nèi)的鄰居節(jié)點(diǎn)

計(jì)算得知：

式中：α是vj、vi與X軸之間的夾角，(xvj,yvj)是vj的坐標(biāo)，(xvi,yvi)是vi的坐標(biāo)。

式中：β是vj、vi與B之間的夾角，dvi→vj是vi到vj的距離，rs是節(jié)點(diǎn)覆蓋圓的半徑。

上述中覆蓋的角度為[α-β,α+β]，由于α-β＜0，所以覆蓋的角度是[0,α+β]∪[2π+(α-β),2π]。當(dāng)節(jié)點(diǎn)vi全部檢測范圍內(nèi)的周圍節(jié)點(diǎn)將覆蓋角全部覆蓋時(shí)，此時(shí)節(jié)點(diǎn)應(yīng)判定為冗余節(jié)點(diǎn)。

（6）當(dāng)節(jié)點(diǎn)vi對檢測范圍的周圍節(jié)點(diǎn)的覆蓋角沒有全部覆蓋，只需算出節(jié)點(diǎn)Ni1與vi的相交點(diǎn)B、C，如圖4所示，可以通過下面公式得出B、C的位置：

式中：rs是節(jié)點(diǎn)覆蓋圓的半徑，α是vj、vi與X軸之間的夾角，β是vj、vi與B之間的夾角。

節(jié)點(diǎn)vi對檢測范圍內(nèi)周圍節(jié)點(diǎn)的覆蓋角沒有全部覆蓋，全部范圍內(nèi)至多4個(gè)相交點(diǎn)，坐標(biāo)位置亦可由上式得出。

式中：rs是節(jié)點(diǎn)覆蓋圓的半徑，d(vj,B)是vj與B之間的距離，d(vj,C)是vj與C之間的距離。

（7）得出Ni3內(nèi)部的節(jié)點(diǎn)vj覆蓋在vi中的圓弧。這時(shí)把vj當(dāng)作坐標(biāo)系，再由第（5）步得出vi的圓弧。

（8）節(jié)點(diǎn)vj將會檢查Ni內(nèi)的節(jié)點(diǎn)，來判斷vi有沒有覆蓋vj。當(dāng)Ni3內(nèi)全部節(jié)點(diǎn)在vi內(nèi)部的圓弧全都覆蓋，則判斷vi是全覆蓋節(jié)點(diǎn)。

（9）全部判斷為全覆蓋節(jié)點(diǎn)會向周圍節(jié)點(diǎn)遞送休眠信號，在此過程中，可能會導(dǎo)致一些地區(qū)不能覆蓋，所以需要在任一全覆蓋節(jié)點(diǎn)設(shè)置一段延遲，當(dāng)在延遲時(shí)沒有接收到休眠信號，就會執(zhí)行休眠操作；當(dāng)在延遲時(shí)收到休眠信號，則會去除此節(jié)點(diǎn)，然后再次檢測周圍節(jié)點(diǎn)是否被全部覆蓋。

2.2 算法流程圖

根據(jù)上述算法過程，可以得到密度自適應(yīng)冗余節(jié)點(diǎn)的判定算法流程圖，如圖5所示。

圖5 密度自適應(yīng)冗余節(jié)點(diǎn)調(diào)度算法流程圖

3 仿真結(jié)果與分析

3.1 仿真環(huán)境

本節(jié)利用Matlab軟件來實(shí)現(xiàn)仿真。假設(shè)N個(gè)節(jié)點(diǎn)均勻存在于一個(gè)面積為100 m×100 m的正方形內(nèi)，L取100，N分別取100、200、300、400、500、600、700、800和900九個(gè)值。假設(shè)單個(gè)節(jié)點(diǎn)的監(jiān)測范圍是直徑為20 m的圓，通信半徑與探測直徑一致，即20 m。

3.2 實(shí)驗(yàn)結(jié)果

3.2.1 節(jié)點(diǎn)總數(shù)與活躍節(jié)點(diǎn)數(shù)關(guān)系

節(jié)點(diǎn)總數(shù)與活躍節(jié)點(diǎn)數(shù)目關(guān)系如圖6所示，隨著系統(tǒng)中網(wǎng)絡(luò)節(jié)點(diǎn)密度的增加，Ditian算法和改進(jìn)的算法所需要的活躍節(jié)點(diǎn)數(shù)量均上升。但與Ditian算法相比，改進(jìn)的算法所需要的活躍節(jié)點(diǎn)數(shù)較少。這表明在同等的網(wǎng)絡(luò)節(jié)點(diǎn)密度時(shí)，改進(jìn)的算法所需系統(tǒng)中活躍的節(jié)點(diǎn)數(shù)量較低，可有效降低系統(tǒng)中節(jié)點(diǎn)的能耗。

3.2.2 節(jié)點(diǎn)總數(shù)與節(jié)點(diǎn)壽命的關(guān)系

節(jié)點(diǎn)總數(shù)與系統(tǒng)壽命的關(guān)系如圖7所示。與Ditian算法相比，改進(jìn)的算法網(wǎng)絡(luò)壽命顯著延長。此外，在Ditian算法下，系統(tǒng)中節(jié)點(diǎn)總數(shù)的變化對系統(tǒng)的網(wǎng)絡(luò)壽命影響不大，而改進(jìn)的算法與節(jié)點(diǎn)總數(shù)呈現(xiàn)出正相關(guān)的關(guān)系，隨著網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的增加，網(wǎng)絡(luò)壽命越長。

4 結(jié) 語

節(jié)點(diǎn)能耗對無線傳感器網(wǎng)絡(luò)的安全可靠運(yùn)行有著非常重要的作用。節(jié)點(diǎn)在運(yùn)行過程中，收發(fā)信息時(shí)的能量消耗最大，休眠時(shí)的能量消耗比較低。因此，通過對節(jié)點(diǎn)休眠來降低節(jié)點(diǎn)能耗，能有效延長WSN的生存時(shí)間。本文分析了Ditian算法存在的不足，提出了一個(gè)改進(jìn)的密度自適應(yīng)休眠調(diào)度算法，能在不同的環(huán)境變量下，合理選擇節(jié)點(diǎn)進(jìn)行休眠，有效降低算法復(fù)雜度和節(jié)點(diǎn)冗余度。仿真結(jié)果顯示，改進(jìn)后的算法有效降低節(jié)點(diǎn)的平均能耗，延長系統(tǒng)的生存時(shí)間。