基于QoS的無線傳感器網絡感知調度協議

姚道遠，王海林，張寶賢，劉海濤

（1. 中國科學院 上海微系統與信息技術研究所，上海 200050；2. 中國科學院 研究生院，北京100049）

1 引言

事件監測[1]是一類重要的無線傳感器網絡應用[2]，本文所面向的傳感網應用是突發事件檢測和匯報，傳感器節點的工作區域內人員很難進入，結合應用需求和傳感器節點具有電池容量有限和難以更換或充電等特點，事件檢測無線傳感器網絡存在兩大挑戰。首先，系統需要提供應用要求的事件檢測質量，即任何事件都需要在應用限定的較短時間內被檢測到；其次，為盡可能延長網絡生存時間，需提高協議的能量效率，減少節點能耗并考慮節點間能耗均衡。現有的大部分研究[3]集中于提供完全感知覆蓋（傳感器一直處在工作狀態），事件發生后能立刻被檢測到。但在實際應用中，大部分事件都會持續存在一段時間而不是瞬時消失[4]，類似事件包括火災、盜竊和污染等。事件的這種特性使得傳感器處于相對較低的感知任務占空比時仍可以滿足監測要求。本文將重點研究滿足應用指定的監測時延要求的節點級感知調度方法。

已有感知調度工作主要研究完全覆蓋問題[5,6]，即：在保證目標區域中任意點在任意時刻都被至少k（k≥1）個節點不間斷覆蓋的前提下，如何有效減少參與執行該任務的節點總數，但是不間斷覆蓋（或稱完全監測）將消耗大量的節點能量，因而能量利用效率不高。結合無線傳感器網絡的應用特性和要求，部分覆蓋通過周期性節點睡眠調度（包括感知部件和通信部件）將可以在網絡壽命和監測質量之間建立更良好的折衷關系，這是本文的主要研究對象。

目前國外有關局部覆蓋領域的研究中，文獻[7]提出了位置無關的分布式擴展網絡生存時間的節點調度協議，基本思想是將所有傳感器節點隨機歸類于k(k≥1)個不相交的節點子集，并按輪次調度。文獻[8]分析了平均事件監測時延，節點布設改為與實際更相符的泊松點過程。文獻[9]提出在監測和傳輸2個階段最小化監測時延的優化算法，既沒有探討全局監測時延，也沒有系統地分析節點間協同調度與監測時延之間的關系。文獻[10]提出了泊松點分布下的過監測問題，設計了節點間協同喚醒協議，但沒有給出時延的下界，也沒有探討平均監測時延、節點密度和調度機制之間的本質聯系。以上算法沒有討論自適應節點密度以滿足不同應用需求的問題，因此無法靈活調節任務占空比，以支持用戶動態可控的監測時延等服務質量。國內相關研究中，文獻[11]利用了鄰居節點信息減少工作節點數量，但并不是針對具有一定時延容忍度的事件監測應用。文獻[12]提出面向事件監測的基于柵格的感知調度方法，但要求節點獲得一定精度的位置信息，也不是針對滿足不同級別QoS應用需求的目標設計調度算法。

本文在分析點目標場景的事件監測時延的基礎上，設計了適用于大規模隨機布設場景的自適應分布式感知調度協議(ADSSP)，相比傳統的隨機調度協議，ADSSP能滿足全網范圍內動態可調的監測時延要求；通過對協議進行能耗均衡目標優化，相對延長了30%的網絡生存時間。仿真驗證了ADSSP協議的有效性。

2 理論分析

由于隨機布設方式下節點空間分布通常可以由泊松分布過程描述，本節將首先給出節點泊松分布場景下的平均監測時延的理論結果和證明，表 1給出了分析過程中用到的變量名和描述。

表1 變量表名的描述

定理 1 假設每個傳感器在區間[0,TC]的喚醒時刻隨機獨立分布，網絡中n個傳感器節點以泊松方式布設在區域 A=L×L的矩形區域內，令λ=/L2，則區域A中任意點的平均事件監測時延為

證明 根據泊松分布的特征，覆蓋任一點P(P∈A)的節點數 XP滿足概率分布 Pr(XP=k)=λke-λ/k。

當XP≥1時，時間在第1個超幀周期內能被監測到的時延為DC=TC/(XP+1)。DC的期望值是

由于事件可能在第N個超幀周期后被監測到，N滿足概率分布Pr(N=i)=(1-ρ)iρ，其中ρ為第一個周期內被監測到的概率，則有ρ=1-Pr(XP=0)=1-e-λ。據此可以計算任一點的監測時延的期望值為

將E[DC]和Pr(N=i)代入上式并推導即可得到式(1)。定理1給出泊松分布場景下的平均事件監測延遲與全網平均節點密度的關系。

接下來介紹 ADSSP協議設計使用的相關結論是在點目標監測應用場景下推導獲得。

1) 結論1：如圖1所示的點目標監測應用中，陰影區域被K個傳感器覆蓋，每個傳感器喚醒時刻滿足 wi∈[0, TC]，則事件監測時延期望值E[D]≥TC/(2K)， 當 且 僅 當 di=wi+1-wi=TC/K(i=1,2,…,K-1)（不失一般性，假設 0≤wi≤wi+1≤TC(1≤i≤K-1)）時等號成立。

2) 結論2：假定點目標被K個傳感器覆蓋，最小平均時延要求為 DL，設 k=TC/(2DL)，系統參數μ=K/k，根據 μ的不同取值，可采用不同的調度策略以滿足應用需求，具體如下。

② 1≤μ＜2，所有節點按照結論1的方式調度，但每個周期的喚醒概率γQ=2/(μ+1)。

圖1 點目標監測圖

3 自適應分布式感知調度協議

大規模傳感器網絡通常以隨機拋射等方式將傳感器節點布設在事件監測區域內。事件區域Ω為全網范圍，每個節點的感知范圍相同，每個節點的感知覆蓋范圍均在Ω內，假設網絡中總節點數N，則全網范圍內平均有效覆蓋節點數為。現有研究中大規模隨機布設網絡大都以分簇方式組網，簇頭和成員分別承擔網絡管理和感知功能。本文主要考慮既可以實現全網范圍內大致相同的事件監測時延DL，又可以讓網絡滿足靈活可控的事件監測時延的要求，并且最大化網絡壽命。由于隨機布設會導致局部節點密度不一致，現有的隨機調度協議無法滿足應用需求，因此需要考慮的問題有：(A)傳感器節點如何獲取局部的節點密度? (B)如何在節點級設計統一的協議，針對節點密度不均衡的情況，在保障事件監測時延的前提下最小化節點感知能耗？(C)能否通過協議優化盡可能平衡全網范圍內的能量消耗，最大化網絡壽命？根據結論1給出的點目標的分析結果，本文提出一種自適應分布式感知調度協議，并針對全網范圍內能耗均衡的目標優化該協議。協議分3個階段，分別為鄰居信息收集階段、確定調度方式階段和值守階段。鄰居信息收集階段解決問題(A)，確定調度方式階段解決問題(B)和(C)。以下階段中節點在時間上以超幀TC周期性地執行相應操作。

1) 鄰居信息收集階段

網絡中所有傳感器節點通過互相廣播 HELLO幀獲得鄰居節點的基本信息(ID，與本節點的距離di)，建立各自的鄰居信息列表NIT。任一節點s獲得鄰居信息后，計算自身所在局部的有效節點數K。假設鄰居數為n，鄰居i與s的距離為di(i=1,…,n)，首先計算兩者的覆蓋相交區域面積RED( i)=，然后使用式(2)計算參數K。

該參數即可表示節點s所在的局部區域密度λ*。

根據應用要求的全網范圍內平均事件監測的時延DL，計算得到系統參數k =TC/(2DL)和μ=K/k。每個節點計算各自的參數μ(相鄰節點的μ值可能不同，但差別不大)，根據μ值所在的區間，有3種情況，分別為 0＜μ＜1，1≤μ＜2 和 μ≥2，對應節點從稀疏分布到密集分布的不同情形。該階段一般持續數個超幀周期，隨后節點進入確定調度方式階段。

2) 確定調度方式階段

該階段所有已確定協議參數μ的節點在τ(τ＞1，協議參數)個超幀周期內重復執行算法1，確定節點在值守階段執行監測的工作參數向量(η, w)，并確定值守階段各超幀周期的喚醒概率γQ，最后進入值守階段。以下給出算法1的具體內容并做詳細闡述。

算法1 參數(η, w)確定算法

① Input: NIT； // 鄰居表，鄰居節點的ID、間距di、序號ηi和喚醒時刻wiμ //節點的局部密度，通過計算K值后得到

② Output: (η, w)

③ if(0＜μ＜1 || 1≤μ＜2)

④ η? Null；

⑤ else if(μ≥2)

⑦ η?ηmin，其中 ηmin= argmin{num(j)},0≤j≤

⑧ endif

⑨ 查詢NIT，對鄰居節點si(要求ηi==η或ηi==Null)中已初定的喚醒時刻

遞增排序得到〈w1,w2,…,wn〉,其中 w1≤w2≤…≤wn，n≥0；

⑩ if(w當前未定) //當前節點調度時刻未定

? if(n==0)

? w? TC/2；

? else

? 變量 wn+1? w1+TC；

? 計算 di? wi+1-wi, i=1,…,n；

? dmax?max{di, i=1,…,n}，并確定對應區間〈wx, wy〉；

? 初定喚醒時刻w?(wx+ wy)/2；

? endif

? else

? REPEAT

21 變量 wn+1? w1+TC；

22 計算 di? wi+1-wi, i=1,…,n；

24 假設 w 未定，重復步驟? ～ ?)計算w，變量w*?w；

25 以w*為當前喚醒時刻，重復步驟21 ～23 ，計算均方差 σ，變量 σ1?σ；

26 if (σ1-σ2＞th)

27 更新 w ? w*；

28 else

29 BREAK； //滿足程序終止條件，循環結束

30 endif

31 until(τ-1幀的迭代計算執行完畢)

32 endif

33 廣播DEWU幀；

34 end

首先給出偽代碼中的部分變量說明。

num(j)：指鄰居節點中，按照參數η對鄰居節點分集（共個集合），第j個集合的元素個數，其中0≤j≤-1。

算法1中確定參數η的步驟③～⑧執行1個幀周期，傳感器通過隨機退避機制廣播包含ID、η和w值的DEWU幀，減少信號沖突。退避方式是節點根據自身計算得到的μ值，計算廣播調度時刻更新幀DEWU的退避時間，選擇區間[0, μBOmax]，BOmax為協議參數，并設置退避定時器。μ值最大的節點最先確定自身的參數η=0, w=TC/2，并廣播DEWU幀。節點接收到鄰居的 DEWU后，將信息添加到鄰居列表NIT。當μ≥2時，節點將選擇0～-1序號的節點個數按照從大到小排序，選擇節點個數最小的序號，其他情形η =null。確定參數w的步驟執行時間為 τ(τ＞1)個幀，每個幀的開始時刻，節點如果偵測到信道空閑，則計算并決定是否更新當前調度時刻w，在第1個幀內，喚醒時刻未定，通過步驟?～?計算得到，并得到初步確定。接下來的τ-1幀內，重復步驟21～30，不斷調整自身的喚醒時刻w，計算均方差的公式如下：

根據協議參數μ的取值，確定喚醒概率γQ的取值。

1≤μ＜2，根據結論 2，節點的喚醒概率 γQ=2/(μ+1)；

μ≥2，節點在確定的喚醒周期內以概率 γQ=1喚醒工作；

0＜μ＜1，節點每個周期的喚醒概率γQ=1，由結論2知節點每個周期內喚醒次，喚醒時刻可表示為。其中wi(0)取算法1獲得的參數w。假設調度時刻排序后下一個鄰居節點的喚醒時刻為 wj(0)，根據 di=wj(0)-wi(0)，計算得到：

綜上，節點需要維護調度參數(η, w)，但在1≤μ＜2和 0＜μ＜1這 2種情況下，節點在每個周期均喚醒工作，η無意義，此時設置η=null。不同密度分布情形下，各節點確定調度參數(η, w)的方法如算法1偽代碼所示。接下來所有節點進入值守階段，在確定的調度周期和調度時刻內，以確定的喚醒概率γQ工作。

3) 能耗均衡優化

在保證平均監測時延滿足應用需求的前提下可通過基于剩余能量動態調整感知占空比對協議進行全網能耗均衡優化，為此引入剩余能量加權因子ω。

其中，Einit為初始能量，Ethr為感知能量門限，Eres為當前節點剩余能量，α(α≥2的整數)為協議參數。當 Eres=Einit時，ω=1；當 Eres=Ethr時，ω=0；其他0＜ω＜1。

各節點計算得到自身加權因子 ω*和獲得鄰居加權因子ωi，1≤i≤n，計算平均加權因子。

更新式(2)，各節點計算本地的有效覆蓋節點數K。

4) 協議復雜度分析

協議的復雜度主要由算法1決定，各節點獨立執行算法1，接收鄰居信息并執行排序操作，因此協議的復雜度為O(dlgd)，其中d為最大鄰居節點數。

4 仿真驗證

4.1 仿真場景

網絡通過分簇方式管理，假設簇間保持時間同步，各簇內傳感器節點獨立工作互不干擾，因此可以通過仿真考慮單個簇的協議性能表征全網性能。在圖2所示的K個節點隨機布設場景中，各傳感器節點的覆蓋半徑為 rs，節點 1為負責網絡管理的Sink節點（或簇頭節點），事件發生的范圍是以節點1所在的位置為圓心，以re為半徑的圓。仿真平臺為QualNet-v4.0，在QualNet中設置物理層采用802.15.4-PHY協議，雙徑模型，理想無衰落信道；MAC層采用802.15.4-MAC協議。其他仿真參數見表2。

圖2 隨機布設場景(K=22)

表2 仿真參數

4.2 仿真結果

以下仿真性能包括監測時延均值和方差，其中均值計算方法在之前已有敘述，監測時延方差V[D]的統計方式見式(8)。

其中，Di為節點 i的監測時延，為所有的節點的平均監測時延。接下來介紹隨機調度協議：網絡拓撲建立后，傳感器節點在每個幀[0, TC)內隨機選擇自身調度時刻 w，節點每個幀喚醒一次，執行感知任務，監測到事件后，將數據上傳到簇頭或Sink節點。

圖3比較了ADSSP協議與最優調度算法的平均延遲的性能。仿真中通過保持rs不變，調整節點分布密度以改變 K值。由圖 3可以看出，ADSSP協議在不同密度分布情況下都能獲得接近理論最優的監測性能。

圖3 ADSSP協議的事件監測時延性能

圖4為ADSSP協議根據應用調整任務占空比后獲得的監測時延均值和方差的性能，且與點目標平均監測時延下界進行對比。橫坐標為 K(K=DL/2TC，DL為監測時延應用需求)；ADSSP_E[D]為ADSSP協議的監測時延均值；點目標為點目標時的監測時延下界；ADSSP_V[D]為ADSSP協議的監測時延方差。由圖4可以看出，ADSSP協議能通過靈活改變協議參數K以滿足不同的應用需求。

圖4 ADSSP協議監測時延平均值和方差

圖5為ADSSP協議和隨機調度協議在同一布設場景下的性能對比。仿真中通過調節覆蓋半徑rs，改變網絡平均有效覆蓋節點數K ，獲得對應的監測時延均值和方差。從圖5可知，ADSSP協議的監測時延和方差均比對應的隨機調度協議小。

圖5 ADSSP和隨機調度協議的監測時延均值和方差對比

圖6和圖7為根據節點剩余能量對ADSSP協議進行優化與未優化時的節點生存時間和平均監測時延對比圖。綜合圖6和圖7，優化的協議能獲得更為均衡的能耗速度和更長的節點生存時間(前 5個節點平均生存時間延長17.9%)；平均監測時延僅增加5%。

圖6 ADSSP協議優化前后網絡生存時間對比

圖7 ADSSP協議優化前后平均監測時延對比

圖8為隨機調度協議和優化后的ADSSP協議在滿足相同全網平均監測時延的前提下(E[D]=15.85ms)節點生存時間。仿真中協議參數k=4，仿真統計次數為100次。本文考慮以前5個死亡節點的平均生存時間為網絡的生存時間，優化后的 ADSSP協議相對于隨機調度協議延長了30.5%的生存時間。

圖8 不同協議導致的網絡生存時間對比

5 結束語

為滿足大規模隨機部署情況下傳感器網絡對事件監測時延的不同要求和盡可能延長網絡生存時間，本文設計了自適應分布式感知調度協議，仿真結果表明 ADSSP可以提供全網范圍內可調的感知質量保證，并延長了網絡生存時間。

[1] BRENNAN S, MIELKE A, TORNEY D. Radioactive source detection by sensor networks[J]. IEEE Transactions on Nuclear Science, 2005,52(3):813-819.

[2] YICK J, MUKHERJEE B, GHOSAL D. Wireless sensor network survey[J]. Journal of Computer Networks, 2008, 52(12): 2292-2330.

[3] LUO H M, WANG H Z. A precise coverage control protocol with limited communication in wireless sensor networks[A]. IEEE International Symposium on Embedded Computing[C]. 2008. 149-154.

[4] DUTTA P, GRIMMER M, ARORA A. Design of a wireless sensor network platform for detecting rare, random, and ephemeral events[A].IEEE IPSN’05[C]. California, USA, 2005.497-502.

[5] YEN L H, CHENG Y M. Range-based sleep scheduling (RBSS) for wireless sensor networks[J]. Journal of Wireless Personal Communications, 2009, 48(3):411-423.

[6] LIU J X, GU N J, and HE S. An energy-aware coverage based node scheduling scheme for wireless sensor networks[A]. ICYCS[C].Zhangjiajie, China ,2008.462-468.

[7] LIU C, WU K, KING V. Randomized coverage-preserving scheduling schemes for wireless sensor networks[A]. IFIP Networking 2005[C].Waterloo Ontario, Canada, 2005.1-10.

[8] JIANG J, LIU C, WU G F. On location-free node scheduling scheme for random wireless sensor networks[A]. ICESS[C]. Xi’an,China,2005.484-493.

[9] CAO Q, ABDELZAHER T, HE T. Towards optimal sleep scheduling in sensor networks for rare-event detection[A]. IPSN[C]. Los Angeles,USA, 2005.1-8.

[10] ZHU Y M, LIONEL M N. Probabilistic wakeup: adaptive duty cycling for energy efficient event detection[A]. MSWiM[C]. Greece,2007.360-367.

[11] 石高濤, 廖明宏. 大規模傳感器網絡隨機睡眠調度節能機制[J]. 計算機研究與發展, 2006, 43(4): 579-585.SHI G T, LIAO M H. Random sleep scheduling energy efficient scheme for large wireless sensor networks[J]. Journal of Computer Research and Development, 2006, 43(4): 579-585.

[12] 胡湘華, 楊學軍. 面向事件監測的無線傳感網感知調度[J]. 軟件學報, 2008, 19(9): 2413-2421.HU X H, YANG X J. Sensing scheduling algorithm of wireless sensor networks for event detection applications[J]. Journal of Software, 2008,19(9):2413-2421.