一種改進的無線傳感器網絡密度自適應冗余節點調度算法

何少尉

（浙江郵電職業技術學院，浙江 紹興 312366）

0 引 言

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

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

1 Ditian算法簡介

節點休眠調度方法是讓不需要工作的節點進入休眠狀態，在“偵聽”“休眠”模式之間不斷切換，使傳感器節點輪換工作。這樣可以增加網絡使用時間，提升節點能量效率。

傳感器節點處于休眠狀態時能量損耗最少。以某傳感器網絡中某個節點為例，該節點在一個周期內發送、接收、空閑和休眠狀態時的能耗對比如圖1所示。可以明顯看出，節點在休眠狀態時的功耗僅為空閑狀態的很小一部分，在覆蓋率和連通度不發生變化的前提下，可以通過提高節點進入休眠狀態的數量來實現能量的低消耗，用節點間相互的交替工作來減少網絡的能耗。節點休眠調度算法一般通過合理的資源調度算法，盡可能增加節點的休眠時間，減少節點的發送、接收和空閑時間。Ditian算法就是節點休眠調度算法的一種。

圖1 傳感器節點能量消耗情況

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

式中：(xu,yu)、(xv,yv)表示節點u、v的坐標。

如圖2所示，對于節點A而言，被周圍節點B覆蓋的區域為弧P1B1P2和弧P1A1P2相交的地方。由圖中幾何關系可知，節點間的重疊面積不易計算，而扇形P1B1P2的面積不難計算。為使計算簡單，只需計算扇形P1B1P2對應的圓心角∠P1AP2取值在[0,2π)中，即可認定該節點為冗余節點。

圖2 冗余節點判斷示意圖

因此，Ditian算法中，首先計算節點與基準軸的夾角，當該節點與周圍鄰居節點的角度在[0,2π)時，即認為該節點為冗余節點。

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

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

圖3 扇區覆蓋誤差示意圖

2 改進的密度自適應冗余節點調度算法

針對Ditian算法對探測區域內低密度不適用的情況，本文提出一種改進的密度自適應冗余節點調度算法，利用最少節點覆蓋全部檢測范圍，降低節點部署的數目。

2.1 密度自適應冗余節點調度算法

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

假定WSN中全部節點的功能結構均相同，通信和監測范圍均為圓形。令監測直徑為通信半徑的一半，利用定位系統確認出節點位置。算法的流程如下。

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

（2）獲取周圍節點數據，確立周圍節點表，將節點從近到遠排列。

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

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

（5）當Ni1∈φ，從近到遠檢查vi范圍內的周圍節點，推測此節點與周圍節點的覆蓋角。如圖4所示。

圖4 vi半徑內的鄰居節點

計算得知：

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

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

上述中覆蓋的角度為[α-β,α+β]，由于α-β＜0，所以覆蓋的角度是[0,α+β]∪[2π+(α-β),2π]。當節點vi全部檢測范圍內的周圍節點將覆蓋角全部覆蓋時，此時節點應判定為冗余節點。

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

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

節點vi對檢測范圍內周圍節點的覆蓋角沒有全部覆蓋，全部范圍內至多4個相交點，坐標位置亦可由上式得出。

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

（7）得出Ni3內部的節點vj覆蓋在vi中的圓弧。這時把vj當作坐標系，再由第（5）步得出vi的圓弧。

（8）節點vj將會檢查Ni內的節點，來判斷vi有沒有覆蓋vj。當Ni3內全部節點在vi內部的圓弧全都覆蓋，則判斷vi是全覆蓋節點。

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

2.2 算法流程圖

根據上述算法過程，可以得到密度自適應冗余節點的判定算法流程圖，如圖5所示。

圖5 密度自適應冗余節點調度算法流程圖

3 仿真結果與分析

3.1 仿真環境

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

3.2 實驗結果

3.2.1 節點總數與活躍節點數關系

節點總數與活躍節點數目關系如圖6所示，隨著系統中網絡節點密度的增加，Ditian算法和改進的算法所需要的活躍節點數量均上升。但與Ditian算法相比，改進的算法所需要的活躍節點數較少。這表明在同等的網絡節點密度時，改進的算法所需系統中活躍的節點數量較低，可有效降低系統中節點的能耗。

3.2.2 節點總數與節點壽命的關系

節點總數與系統壽命的關系如圖7所示。與Ditian算法相比，改進的算法網絡壽命顯著延長。此外，在Ditian算法下，系統中節點總數的變化對系統的網絡壽命影響不大，而改進的算法與節點總數呈現出正相關的關系，隨著網絡節點總數的增加，網絡壽命越長。

4 結 語

節點能耗對無線傳感器網絡的安全可靠運行有著非常重要的作用。節點在運行過程中，收發信息時的能量消耗最大，休眠時的能量消耗比較低。因此，通過對節點休眠來降低節點能耗，能有效延長WSN的生存時間。本文分析了Ditian算法存在的不足，提出了一個改進的密度自適應休眠調度算法，能在不同的環境變量下，合理選擇節點進行休眠，有效降低算法復雜度和節點冗余度。仿真結果顯示，改進后的算法有效降低節點的平均能耗，延長系統的生存時間。