基于鄰居節點位置的無線傳感網休眠算法

賈明偉，吳 敏，沙 超,2，王汝傳,2

(1.南京郵電大學 計算機學院、軟件學院，江蘇 南京 210003；2.蘇州大學 江蘇省計算機信息處理技術重點實驗室，江蘇 蘇州 215006)

基于鄰居節點位置的無線傳感網休眠算法

賈明偉1，吳 敏1，沙 超1,2，王汝傳1,2

(1.南京郵電大學 計算機學院、軟件學院，江蘇 南京 210003；2.蘇州大學 江蘇省計算機信息處理技術重點實驗室，江蘇 蘇州 215006)

在無線傳感器網絡中，節點往往以隨機方式密集部署，從而易于產生大量冗余。文中在考慮網絡覆蓋率的前提下，提出了一種休眠調度算法。節點根據自己與鄰居節點的位置關系，計算鄰居節點對自己感知區域的覆蓋程度。若鄰居節點對自己的感知區域覆蓋度超過給定的閾值，則節點進入休眠狀態。仿真實驗證明了算法的有效性，通過關閉網絡中的冗余節點，節省了網絡能量，延長了整個網絡的生命周期；和同類算法相比較，算法檢測冗余節點的能力明顯優于同類算法，較大程度地減少了網絡中的冗余節點。

無線傳感器網絡；休眠；覆蓋冗余；鄰居節點位置

0 引 言

在無線傳感器網絡中，節點的部署方式有兩種：確定性部署和隨機性部署。針對一些價值比較昂貴的無線傳感器節點或者受限于特定的應用需求，無線節點多采用確定性部署;而針對一些價值比較低廉或者確定性部署無法完成的無線傳感器網絡環境，無線節點采用隨機性部署[1]。在隨機性部署的無線傳感器網絡中，為了保證節點完全覆蓋目標范圍，節點的密度往往很大,從而造成冗余[2-3]。判斷出這些冗余節點，并將其休眠既可以節省網絡的能量又能減少網絡中信道沖突發生的概率。

無線傳感器網絡一經部署，節點往往不能移動，節點的電池也不可以替換，所以能量問題一直是無線傳感器網絡研究的熱點。在滿足覆蓋率的前提下，讓一部分節點處于休眠狀態可以有效地節省網絡的總體能量，從而延長整個網絡的生命周期。

文中提出一種覆蓋冗余節點判別算法(SALN)。傳感器節點根據自己以及鄰居節點的位置計算自己被鄰居節點覆蓋的程度，當節點被鄰居節點的覆蓋度達到預定閾值時，節點判定自己為冗余節點，從而進入休眠狀態。

1 相關工作

當前的無線傳感器網絡休眠調度算法主要分為以下幾類:第一類是根據網絡的連通性判斷節點是否需要休眠，在不改變網絡連通性的前提下休眠冗余節點[4-5];第二類是基于距離的休眠調度算法，根據節點與簇頭節點的距離，為節點設置不同的休眠概率[4];第三類是根據網絡的覆蓋率判斷節點是否為冗余節點，在滿足一定覆蓋率的前提下，將部分節點休眠[6-11]。此外，還有根據實際的應用需求對節點進行輪轉休眠調度，從而延長網絡的生命周期。

在第一類休眠調度算法中，文獻[4]首先將網絡劃分為一個個網格，網絡中的節點可以和相鄰網格中的任意節點通信，其次讓網格中的節點輪轉工作，以節省網絡能量。文獻[5]將擁有相同鄰居的節點分在同一組中，在滿足網絡連通性的前提下，根據一定條件，將單獨的節點加到一個組中或自己形成一個組，每個組中選一個節點工作，其余休眠。這類算法以網絡的連通性作為判斷依據，從而決定一個節點是否休眠。文獻[6]是典型的第二類休眠調度算法，它將網絡分簇，簇中節點根據與簇頭的距離設置不同的休眠概率。在第三類休眠調度算法中，文獻[7]提出了一種分布式的休眠調度算法。算法的基本思想是：初始時，網絡中的每一個節點都是一個節點組，在保障覆蓋度的前提下，相鄰的節點組融合為一個節點組，直到節點組之間不能再融合，融合階段結束后，算法在每一個節點組中選出1～2個節點處于工作狀態，其余節點進入休眠狀態。文獻[8]提出一種輕量級部署調度算法，稱為LDAS。算法先設計一個節點被它的n個鄰居節點完全覆蓋的概率，然后計算一個節點被它的n個鄰居覆蓋的區域占自身監測區域的百分比，基于這兩個結果判斷節點是否應該休眠。文獻[9]在文獻[8]的基礎上，重點考慮了兩個問題：一是大量節點同時休眠產生感知盲區問題；二是節點是否處于網絡邊界問題。文獻[10]提出了一種面向異構無線傳感器網絡的節點休眠調度算法。首先根據鄰居節點之間的距離對鄰居節點進行分類，針對不同類型的鄰居節點，算出滿足覆蓋率條件下所需此種類型鄰居節點的最少個數，然后節點根據所有類型的鄰居傳感器節點的個數判斷是否休眠。第三類算法主要是判斷休眠一個節點后對網絡覆蓋率的影響，若一個節點休眠后對網絡覆蓋率無影響或影響很小，則判定為冗余。

此外，針對無線傳感器網絡的區域覆蓋問題，Tian等[12]提出基于節點狀態調度的分布式覆蓋算法；Zhang等[13]提出分布式節點密度控制算法，根據節點鄰居和自己的位置信息計算相互的覆蓋關系；Y.Xu等[14]采用整數序列編碼的遺傳算法，找出網絡的一個最小覆蓋子集；M.Cardei等[15]用整數規劃調節傳感半徑，用貪心算法找到K個覆蓋子集；H.Chen等[16]把網絡劃分為網格，并用貪心算法找最小的覆蓋子集。

綜合上述各類休眠調度算法，文中選取第三類基于覆蓋率的休眠調度算法作為研究點，重點關注休眠節點對網絡覆蓋率的影響。受文獻[8,10]的思想啟發，文中提出一種以鄰居節點位置及間距來判斷是否冗余的方法。在滿足指定覆蓋率的前提下，最大化休眠網絡中的冗余節點。

2 網絡模型及相關定義

2.1 網絡模型

(1)為了滿足連通性和覆蓋率，節點以隨機方式密集部署。

(2)節點的通信距離和感知距離相同。感知范圍是以節點所在位置為圓心、感知距離為半徑的圓。

(3)節點自帶定位功能，暫時不考慮節點的定位問題。

(4)節點的能量受限，且一經部署不能移動，不能替換電池。

2.2 相關定義

(1)鄰居節點。

網絡中節點i的鄰居集合定義為:

(1)

其中：ix為節點i的x坐標；iy為節點i的y坐標；R為傳感器節點的最大感知距離。

(2)覆蓋重疊區域。

假設網絡中節點i有一個鄰居節點j，兩個節點的感知覆蓋區域所形成的圓(以下簡稱感知圓)相交于P和Q兩點，以節點i的感知圓的兩條半徑以及圓上的一段弧組成的扇形區域稱作節點j對節點i的覆蓋重疊區域，如圖1中陰影部分所示。

(3)覆蓋重疊區域圓心角。

節點j對節點i的覆蓋重疊圓心角即為圖1中的α角，其大小可由式(2)給出：

(2)

其中：r為兩個節點之間的距離；R為節點感知圓的半徑。

(4)覆蓋區間。

假設節點的感知圓上的每一個點擁有一個弧度值，定義過圓心平行于Y軸與圓周相交的點的弧度值為0弧度，圓上其他點的弧度值按圓周上的逆時針方向依次增大。節點j在節點i上的覆蓋區間定義為[q,p]，其中q為Q點的弧度值，p為P點的弧度值，Q、P為兩感知圓的交點。

(5)節點的被覆蓋率。

節點i的所有鄰居節點覆蓋區間的集合定義為：

(3)

舉例說明，如圖1所示，節點i有三個鄰居節點，分別為節點j、h、g，節點j、h、g對節點i的覆蓋重疊區域圓心角分別為α、β、γ，相應的覆蓋區間分別為[q,p]、[e,f]、[c,d]。節點i的所有鄰居節點的覆蓋區間的并集為：

(4)

從圖1可以看出，節點i的鄰居節點的覆蓋重疊區域占據了節點i感知區域的絕大部分。可簡單認為只有銳角∠EiP(i為節點i的感知圓的圓心)所對應扇形區域未被節點i的鄰居節點覆蓋，其余部分全部被其鄰居節點覆蓋(實際上，節點i的未覆蓋區域面積要小于∠EiP所對應扇形區域的面積)。此時節點i的被覆蓋率為：

(5)

圖1 節點被覆蓋率計算

3 方法實現及分析

3.1 SALN算法實現

SALN算法分為三個階段：節點初始化階段、內部計算階段和休眠調度階段。

步驟1：節點初始化階段。

傳感器節點部署完成之后，每個節點向外界發送自己的坐標位置，同時監聽鄰居節點發送來的數據包，數據包包含鄰居節點的x坐標和y坐標。

步驟2：節點內部計算階段。

當通信完成之后，節點為每一個鄰居節點保存一個坐標值。節點根據鄰居節點的坐標值和自身的坐標值計算各個鄰居節點的覆蓋區間。計算完成后，節點將這些覆蓋區間進行合并，并計算出節點被鄰居節點的覆蓋率。關于覆蓋區間的計算，舉例說明如下。如圖1所示，若計算節點j在節點i上的覆蓋區間，首先計算C點的弧度值。當節點i的x坐標值大于節點j的x坐標值時，c=β；當節點i的x坐標值小于等于節點j的x坐標值時，c=360-β。公式如下：

(6)

(7)

節點j在節點i上的覆蓋區間為[q,p](p、q均在0～360之間)。q和p的值由式(8)和式(9)給出。

(8)

(9)

步驟3:節點休眠調度階段。

節點根據計算得出的被覆蓋率，同給定的閾值θ(0～1之間)相比較，從而確定自己是否為冗余節點。如果節點的被覆蓋率大于θ，節點可以進入休眠狀態；否則，正常工作。θ的值通常根據在網絡實際運行時用戶所要求的覆蓋率進行設置。

3.2 時間復雜度分析

由SALN算法的實現過程可知，節點判斷自己是否冗余所費時長主要和節點的鄰居節點數量有關。若網絡中節點的平均鄰居數量為nnei，則SALN的時間復雜度為O(nnei)，由于節點的鄰居節點個數必定小于節點總數n，故時間復雜度為O(n)。

4 仿真實驗與分析

4.1 實驗設置

用Matlab+Java進行仿真實驗，通過改變網絡規模、節點的被覆蓋率閾值，從而觀察網絡休眠節點的數量、網絡的總體覆蓋率。由于節點部署的方式為隨機性部署，故每次的實驗結果不唯一。以下實驗數據均是在同一實驗參數條件下，重復10次的平均值。

4.2 算法自身對比實驗

當在網絡中撒播250個感知半徑為10 m的節點時，增大網絡規模，在不同的閾值下，網絡達到休眠條件的節點數量如圖2所示。

圖2 不同條件下節點休眠個數對比

從圖中可以看出,網絡規模越大，滿足休眠條件的節點數量就越少。因為網絡規模越大，節點之間的平均距離就越大，節點的平均鄰居數就越少，平均被覆蓋率越小，從而造成休眠節點數減少。在同一網絡規模下，被覆蓋率閾值設置越大，休眠的節點數量也越少。因為被覆蓋率閾值越高，滿足覆蓋率閾值條件的節點數就越少。

在150 m×150 m的區域內隨機撒播250個和200個感知半徑為10 m的節點時，網絡初始化時的覆蓋情況如圖3(a)和(c)所示，圖中灰色的區域為節點的感知區域，空白區域為未被節點覆蓋的區域。圖3(b)和(d)為節點調用完算法后網絡的覆蓋情況。

從對比圖可以直觀且明顯地看出，調用算法后網絡中冗余節點的數量大大減少了。

表1為在150 m×150 m的區域內隨機撒播250個節點，當節點設置不同的被覆蓋率閾值時，網絡的總體覆蓋率的變化情況，此時網絡未運行算法時的覆蓋率為93.9%。

圖3 算法運行前后直觀對比圖

節點被覆蓋率算法運行后覆蓋率/%320/36093.39330/36093.62340/36093.9350/36093.9360/36093.9

從表1可以看出,當節點的被覆蓋閾值設置為340/350、350/360時網絡的總體覆蓋率并無影響。此時滿足休眠條件的節點個數分別為70以及53，休眠節點占總節點數的比值分別為28.0%和21.2%，也就是說在不改變網絡原始覆蓋率的前提下，執行算法后，可以減少網絡中21.2%～28.0%的冗余節點。即使節點的被覆蓋率設置為320/360，相比較未調用算法時，網絡的總體覆蓋率也只下降了0.61個百分點而已，而此時，休眠節點的占比可達到28.0%，由此可以看出文中算法的實用性和高效性。

表2為隨機撒播250個以及300個節點時，網絡的總體覆蓋率隨網絡規模的變化情況。

從表中可以看出，并非網絡規模越小，部署的密度越大，節點調用算法后網絡的總體覆蓋率就越大。當網絡的規模過小，密度過大時，節點調用完算法后，網絡的總體覆蓋率反而會下降。造成這種現象的原因是若網絡中的節點很密集，滿足被覆蓋率閾值的節點占比過高，從而大量的傳感器節點進入休眠狀態，使網絡總體覆蓋率降低。一種解決辦法是：為網絡中的節點設置一個休眠優先級。當節點在網絡中依次休眠時，節點計算覆蓋區間時就不會再考慮已休眠的節點，從而不會出現這種現象。當撒播250個節點，網絡規模為100 m×150 m時，總體覆蓋率出現最大值。此時的網絡密度為100 m2內有1.67個節點。同時，當撒播300個節點，網絡規模為150 m×150 m時,網絡總體覆蓋率達到最大值。此時的節點密度為100 m2內有1.33個節點。算法實際投入運行時，網絡的節點密度應在1.33～1.67之間，這樣監測區域才能達到最優覆蓋。

表2 不同網絡密度下算法執行后的覆蓋率 %

4.3 SALN算法同其他算法的對比實驗

下圖為在不同實驗條件設置下，SALN算法和Random算法、GBS算法、NDBS算法的對比實驗圖，得到不同網絡覆蓋率以及撒播不同節點數目對節點關閉率(休眠節點數占總節點數的比值)的影響。其中，Random算法是在保證特定網絡覆蓋率的情況下，隨機性休眠網絡中的節點。GBS算法是首先將網絡劃分為網格，針對每個網格中的節點，在保證覆蓋率的前提下，隨機休眠節點。在NDBS算法中，節點根據鄰居節點的數量和指定的網絡覆蓋率判斷自己是否是冗余節點，是否休眠[8]。

圖4為在100 m×100 m的網絡中撒播500個半徑為10 m的節點時，節點關閉率隨著網絡覆蓋率的變化情況。當網絡的實際覆蓋率在0.5～0.9[8]之間變化時，網絡中節點關閉率呈下降趨勢。由圖4也可以看出，指定的網絡覆蓋率越高，滿足關閉條件的節點數量也就越少。同時，在相同的網絡覆蓋率條件下，SALN算法的節點關閉率明顯高于其他三種算法。

圖4 不同覆蓋率下節點關閉率的變化情況

圖5是在100 m×100 m的網絡中撒播不同數量的節點時，四種算法的節點關閉率的變化趨勢圖。此時節點的半徑為10 m，網絡覆蓋率為0.8。當在網絡中的撒播節點數量越多時，滿足關閉條件的節點數量也就越多。從圖5中也可以看出，當網絡中節點的數目增加時，四種算法的節點關閉率均呈現上升狀態。同時，在相同的節點數目下，SALN算法的節點關閉率要高于其他三種算法。

圖5 不同節點數目下節點關閉率的變化情況

由圖4、5可以看出，無論是改變網絡的覆蓋率還是在網絡中撒播不同的節點數量，文中提出的SALN算法在四種關閉冗余節點的算法中有明顯優勢。

5 結束語

文中提出了一種基于鄰居節點位置的覆蓋冗余判別算法。節點只需知道網絡中鄰居節點的位置，即可判斷自己是否冗余，減少了網絡中的額外通信量，節省了網絡能量消耗。仿真實驗從網絡規模、休眠節點數、被覆蓋閾值等方面對SALN算法進行了驗證和分析，計算出了網絡部署時的最優部署值區間；同時從網絡覆蓋率和撒播不同數量節點將該算法同其他算法進行了比較，驗證了該算法的關閉冗余節點能力。

在下一步工作中，將優化文中提出的算法，以防止網絡中大量節點同時進入休眠狀態?？紤]經過計算后滿足休眠條件的節點，在其鄰居節點休眠后不再滿足休眠條件這種特殊情況的出現。同時，考慮加入節點的輪轉工作。

[1] 馬祖長,孫怡寧,梅 濤.無線傳感器網絡綜述[J].通信學報,2004,25(4):114-124.

[2] 徐朋豪,馮玉光,奚文駿,等.基于ZigBee的無線溫濕度采集系統研究[J].國外電子測量技術,2013,32(1):33-36.

[3] 石 欣,冉啟可,范 敏,等.無線傳感器網絡動態加權DV-Distance算法[J].儀器儀表學報,2013,34(9):1975-1981.

[4] Zebbane B.Energy-efficient protocol based sleep-scheduling for wireless sensor networks[C]//Proceedings of 2012 international conference on complex systems.[s.l.]:[s.n.],2012:407-412.

[5] Zebbane B.Enhancing the sensor network lifetime by topologycontrolandsleep-scheduling[C]//Proceedingsofinternationalconferenceonsmartcommunicationsinnetworktechnologies.[s.l.]:IEEE,2013.

[6]SinghB,LobiyalDK.Energypreservingsleepschedulingforcluster-basedwirelesssensornetworks[C]//Procofsixthinternationalconferenceoncontemporarycomputing.[s.l.]:IEEE,2013:97-101.

[7] 石冠雄.節點休眠調度仿真系統及優化算法[D].天津:天津大學,2012.

[8]WuK,GaoY,LiFL,etal.Lightweightdeployment-awareschedulingforwirelesssensornetworks[J].MobileNetworksandApplications,2005,10(6):837-852.

[9] 溫 濤,張冬青,郭 權,等.無線傳感器網絡冗余節點休眠調度算法[J].通信學報,2014,35(10):67-80.

[10] 孫力娟,魏 靜,郭 劍,等.面向異構無線傳感器網絡的節點調度算法[J].電子學報,2014,42(10):1907-1912.

[11] 韓志杰,吳志斌,王汝傳,等.新的無線傳感器網絡覆蓋控制算法[J].通信學報,2011,32(10):174-184.

[12]TianD,GeorganasND.Acoverage-preservingnodeschedulingschemeforlargewirelesssensornetworks[C]//ProcoffirstACMinternationalworkshoponwirelesssensornetworksandapplications.NewYork:ACMPress,2002:32-41.

[13]ZhangH,HouJC.Maintainingschemecoverageandconnectivityinlargesensornetworks[C]//ProcofNSFinternationalworkshopontheoreticalandalgorithmicaspectsofsensor,adhocwireless,andpeer-to-peernetworks.Chicago,USA:[s.n.],2004.

[14]XuY,YaoX.AGAapproachtotheoptimalplacementofsensorsinwirelesssensornetworkswithobstaclesandpreferences[C]//ProcofIEEEconsumercommunicationsandnetworkingconference.LasVegas,NV,USA:IEEE,2006:127-131.

[15]CardeiM,WuJ,LuM,etal.Maximumnetworklifetimeinwirelesssensornetworkswithadjustablesensingranges[C]//ProceedingsoftheIEEEinternationalconferenceonwirelessandmobilecomputingnetworkingandcommunications.[s.l.]:IEEE,2005:438-445.

[16]ChenH,WuH,TzengNF.Grid-basedapproachforworkingnodeselectioninwirelesssensornetworks[C]//ProcofIEEEinternationalconferenceoncommunications.[s.l.]:IEEE,2004:3673-3678.

A Sleeping Algorithm for Wireless Sensor Network Based on Location of Neighbors

JIA Ming-wei1,WU Min1,SHA Chao1,2,WANG Ru-chuan1,2

(1.Computer and Software College,Nanjing University of Posts and Telecommunications, Nanjing 210003,China; 2.Key Laboratory for Computer Information Processing Technology of Jiangsu Province，Soochow University, Suzhou 215006,China)

In Wireless Sensor Networks (WSNs),nodes are densely deployed,which may increase a number of redundant nodes.Considering the network’s coverage,a type of sleeping scheduling algorithm is proposed about coverage redundancy.Each node calculates the coverage rate of its sensing area according to the locations of its neighbors nodes.If the coverage rate is beyond the threshold,the node goes into sleeping mode while other sensor nodes remain active.Simulation experiment shows the effectiveness of the algorithm.By sleeping redundant nodes in the network,network energy is saved and network life is prolonged.Moreover,compared with other algorithms,the ability of the algorithm to detect redundant nodes is much better.The number of redundant nodes is greatly reduced in the network.

wireless sensor networks;sleeping scheduling;coverage redundancy;location of neighbors

2015-07-20

2015-10-23

時間：2016-03-22

國家自然科學基金資助項目(61202355)；高等學校博士學科點專項科研基金(20123223120006)；中國博士后基金(2013M531394)；江蘇省自然科學基金(BK2012436)；江蘇省博士后基金(0801019C)；江蘇省高校自然科學基礎研究項目(14KJB520029)；江蘇省計算機信息處理技術重點實驗室開放課題(KJS1327)

賈明偉(1991-)，男，碩士研究生，研究方向為無線傳感器網絡數據收集、覆蓋等；吳 敏，副教授，碩士生導師，研究方向為海量數據管理,網絡安全技術,密鑰管理和認證以及物聯網在智能家居、醫療健康護理等方面的應用技術等；沙 超，副教授，碩士生導師，研究方向為WSN的數據融合技術、智能定位算法、QoS路由機制以及覆蓋調度技術等；王汝傳，教授，博士生導師，研究方向為基于通信網絡的計算機軟件技術、網絡安全技術、信息網絡應用技術等。

http://www.cnki.net/kcms/detail/61.1450.TP.20160322.1522.090.html

TP301.6

A

1673-629X(2016)04-0056-05

10.3969/j.issn.1673-629X.2016.04.012