基于協作的無線傳感器網絡休眠調度算法

摘要：提出了一種新的保證覆蓋的休眠調度協議CPSBC。該協議基于一種協作感知模型（CSM），與傳統的圓盤感知模型和概率覆蓋模型的不同之處在于，CSM充分利用了多個傳感器節點的協作探測特性?；贑PSBC，對網絡覆蓋具有最小貢獻的，同時休眠后并不影響原始覆蓋的節點被調度進入休眠。理論證明和仿真試驗表明，CPSBC協議能夠以較少的能耗來保證原始網絡覆蓋率，從而達到較好的能量有效性。

關鍵詞：無線傳感器網絡；休眠調度；協作感知模型；覆蓋

中圖分類號：P393； TP212文獻標志碼：A

文章編號：1001－3695(2008)03－0677－04

0引言

無線傳感器網絡以其監測精度高、布設靈活性強、造價低廉等特點，在軍事偵察、工業控制、交通監管、環境監測等領域具有非常廣闊的應用前景[1]。在傳感器網絡中，傳感器節點一般采用電池供電且不可更換，因此，降低能量消耗、延長網絡壽命是網絡設計的主要目標之一。節點通信時的狀態分為發送、接收、空閑和休眠四種，其中休眠狀態時節點消耗的能量最少，且遠小于前三種狀態時的能耗[1]。此外，無線傳感器網絡中通常節點布設密集，如果讓所有節點都工作，則會在數據收集時存在高度相關和冗余，甚至在傳送數據時還會發生沖突。因此，無線傳感器網絡中必須解決的一個重要問題是休眠調度問題，即網絡中只需部分節點工作，其余節點都可休眠。

現有傳感器網絡在休眠時主要考慮兩方面的因素，即連通性和覆蓋性。文獻[2]指出，當傳感器節點的通信距離和感知距離滿足一定的比例關系時在保證覆蓋性的同時就能保證連通性。目前休眠調度算法大部分是研究如何利用圖論和計算幾何學中的方法來尋找冗余節點的集合。其中大多數是基于圓盤感知模型 [2~4]。在圓盤模型中，每一傳感器節點有一半徑為Rb的感知范圍，當某一目標出現在任意節點的感知范圍內，則認為該目標可被感知；否則認為不能被感知。PEAS[3]認為一個節點感知范圍內只要存在一個工作節點，該節點就成為冗余節點而不必激活，該方法考慮了覆蓋性，但它并不能保證休眠節點的感知范圍被其他工作節點完全覆蓋。在文獻[4]中， 如果節點Ni的感應范圍被所有鄰居節點的感應范圍組成的區域完全覆蓋，則Ni就是冗余節點。圓盤感知模型雖然簡單，但是它并沒有考慮到傳感器節點的感知能力隨距離衰減的特性，而該衰減特性對于無線電信號、聲音信號和地震波信號來講是比較合理的[5~7]。柳立峰等人[5]則提出了一種基于概率覆蓋模型的分布式密度控制算法，認為在實際應用環境中概率覆蓋模型能夠更準確地定義網絡覆蓋。雖然該算法能夠保證網絡的覆蓋率，但是所需的工作節點數較多、耗能較大。

基于以最小能耗來保證原始覆蓋，本文采用了一種協作感知模型。該模型是以概率覆蓋模型為基礎，同時考慮到多個節點協作探測特性。根據圓盤感知模型可知，當目標處在節點的感知半徑Rb之外則認為探測不到。實際上，當目標處在Rb之外時，傳感器節點并不是感知不到，只不過是探測貢獻隨著距離的衰減而變弱，圓盤模型中忽略了這部分相對較小但有效的探測貢獻。協作感知模型則充分利用了這部分有效的能量并對其進行聚合?；谠搮f作感知模型，本文提出了一種保證覆蓋的休眠調度算法(coveragepreserving selfscheduling based on CSM，CPSBC)，從兩個方面判斷節點是否是冗余節點：保證原始覆蓋；對網絡覆蓋具有最小貢獻的節點首先休眠。

1協作感知模型

任意傳感器節點s對于目標監控區域內的任一目標點P的探測貢獻量定義為該節點對該目標點的感知強度S(s，p)，在文獻[7，8]中都有定義。本文采用文獻[7]中的定義

其中：d為傳感器與目標之間的距離；α和β為與傳感器物理特性有關的類型參數， 且β為衰減因子。由于存在干擾和噪聲的關系，當節點和目標之間的距離超出一個有效的范圍時，認為節點的感知信號淹沒在噪聲中難以識別可以忽略不計。定義Rc為協作感知模型中傳感器節點有效的感知半徑。如果一個目標點P位于N個傳感器節點共同的有效感知區域內，則這N個節點對于該目標的感知強度可以線性疊加，其和定義為該目標點P的協作感知強度

定義 1探測靈敏強度Psense定義為某一門限強度。當節點協作感知強度大于該門限強度時目標可被探測。

對于同構網絡而言，無論何種感知模型都應該有相同的探測靈敏強度值。在圓盤感知模型中，由于有效探測范圍為Rb，當目標處于Rb之外時，則認為其感知強度為零，探測不到目標點。因此，探測靈敏強度應該為

Psense=1/(1+αRb)β(3)

2理論基礎

假設傳感器節點均勻、獨立分布在平面監控區域A中，并且A的面積遠遠大于單個節點的覆蓋面積。文獻[9]中已經證明，基于圓盤感知模型下，當單個節點的感知半徑為Rb時，傳感器節點以節點密度λ均勻獨立地分布在監控區域A內時，其網絡覆蓋率（network coverage， NC）為NCDISK=1-e-λπRb2。這是因為對于監控區域中的任意一點P，它沒有被任意一個傳感器節點覆蓋的概率為1-πRb2/‖A‖。其中‖A‖為監控區域A的面積。因為節點均勻分布在監控區域A中，落在該監控區域中的傳感器節點個數N是一個泊松隨機變量[9]，且E(N)=λ‖A‖，則任意點P沒有被所有N個傳感器節點覆蓋的概率為（1-πRb2/‖A‖）N。當‖A‖→∞時，有

NCDISK=1-E[{1-πRb2/‖A‖}N]=1-e-(πRb2/‖A‖)E(N)=1-e-λπRb2(5)

那么，基于協作感知模型的網絡覆蓋率又是多少，與基于圓盤感知模型的關系又是如何？針對該問題，通過定理1給出并證明了節點均勻分布時的結論。

定理1節點均勻分布時，為了保證相同的網絡覆蓋率，基于協作感知模型部署所需的節點密

度不大于基于圓盤感知模型的節點密度。

證明:首先推導出基于協作感知模型的網絡覆蓋率，在此基礎上得到定理1的結論。

基于文獻[10]相同的假設，設λ1和λ2分別表示基于圓盤和CSM下布設所需的節點密度。在協作感知模型下，以A、B、C和D分別表示事件：任意點P被覆蓋；以點P為中心、Rb為半徑范圍內至少存在一個傳感器節點；以點P為中心、Rb為半徑范圍內無傳感器節點，但半徑大于Rb且小于Rc的環狀區域內至少存在一個傳感器節點；以點P為中心Rc為半徑范圍內無傳感器節點。

即為了保證相同的網絡覆蓋率，基于協作感知模型所需的節點密度不大于基于圓盤感知模型的情況。證畢。

根據定理1可知，為了保證相同的網絡覆蓋率，基于協作感知模型下所需的工作節點數要遠遠小于圓盤模型的。因此，研究基于此模型的休眠調度算法是有意義的。

3CPSBC密度控制算法

CPSBC 是一種基于協作感知模型的分布式密度控制算法，其中冗余節點的判別是算法的關鍵。CPSBC休眠規則包括

兩個方面：首先檢查節點是否滿足保證覆蓋規則（coverage preserved rule，CPR）；其次計算節點對網絡覆蓋率的貢獻（sensing contribution， SC）大小。

3．1保證覆蓋規則

保證覆蓋規則即保證節點休眠不能降低網絡原有的覆蓋率。那么網絡覆蓋率又該如何計算呢？基于覆蓋點的定義（定義2）可以導出網絡覆蓋率。顯然，整個監控區域的網絡覆蓋率應該為所有工作節點覆蓋區域的并集與整個網絡檢測區域的比例關系。由于該網絡覆蓋率很難計算，也很難使用，在此引入了柵格覆蓋的概念[2，5]，從而把計算整個監控區域中覆蓋面積的問題轉換為計算監控區域中覆蓋子區域個數的問題。

NC=Scovered/Stotal=Mcovered×Sgrid/（M×Sgrid）=Mcovered/M=Mi=1covered(pi)/M

(15)

其中：pi為柵格子區域的中心點；M為柵格子區域的個數；Mcovered為被覆蓋的柵格數。

按照柵格劃分的辦法，節點只需判定當其休眠時，根據式（4）判斷其覆蓋區域的柵格中心點是否仍然是覆蓋點。當所有柵格的中心點仍然是覆蓋點時，該節點選擇休眠就不會影響整個網絡覆蓋率，從而滿足CPR。顯然，柵格劃分得越小，基于柵格算出的網絡覆蓋率就與原始網絡覆蓋率越接近。但實際上，柵格子區域不能劃分得無限小，因為子區域越小，柵格數越多，計算復雜度也會隨之增加。針對這一問題，筆者提出了一種方法[11]，根據測量精度的要求，通過蒙特卡羅試驗來確定最優柵格的大小。

3．2探測貢獻的計算

一個節點的探測貢獻（SC）是該節點對網絡覆蓋貢獻的一種度量。若節點s對網絡覆蓋貢獻越大，則SC(s)就越大。任意傳感器節點s對于其監控區域中任意柵格點pi的探測貢獻可定義為

SC(s，pi)=S(s，pi)/CSI(pi)=S(s，pi)/jS(j，pi)(16)

式（16）即為該傳感器節點s對點pi的感知強度與該點pi的總協作感知強度之比。顯然節點s對網絡覆蓋的SC(s)即為該節點s對其有效覆蓋區域中所有柵格中心點的覆蓋貢獻之和，即

SC(s)=iSC(s，pi)=i[S(s，pi)/CSI(pi)]=i[S(s，pi)/jS(j，pi)](17)

因為一個節點的有效范圍為Rc，式（17）中的傳感器節點j與柵格中心點pi之間的最大距離為Rc，而柵格中心點pi與傳感器節點s之間的最大距離也為Rc，所以傳感器節點j與s之間的最大范圍為2Rc。本文假設節點可獲取各自的位置信息，而相鄰2Rc的節點位置信息可通過互發消息獲取。根據相鄰2Rc的節點位置信息，每個節點均可以計算出各自的SC值。

3．3算法描述

CPSBC協議是一個分布式的密度控制算法。該協議將網絡工作時間劃分成輪，每輪開始時選舉工作節點，關閉冗余節點，結束時所有節點恢復初始狀態，等待下一輪開始時重新進行調度。每個節點s均維護一個鄰居節點表、CPR(s)和SC(s)值。在任何時間，傳感器節點都是處于休眠、工作和發現三個狀態之一。每輪開始時所有節點都是處于發現狀態，根據各自的CPR和SC值來決定是進入工作狀態或是休眠狀態，并且維持該狀態直到下一輪開始時重新進行調度。文獻[4]為了避免出現覆蓋盲區，CPSBC采取了一種隨機退避算法用來避免某一區域內所有節點都同時選擇休眠，從而造成該區域不被覆蓋。具體分布式算法如下：

a）在作休眠決策之前，節點等待一段隨機時間Td。

b）等待定時器到時，所有節點根據當前處于激活狀態的鄰居節點信息，及時更新其覆蓋有效區域內的柵格中心點的協作覆蓋強度值CSI(pi)，從而根據式（15）和（17）來計算節點當前狀態的CPR和SC值。

c）鄰居節點的CPR和SC值可以通過互發消息來獲取。對任意節點檢查其是否符合休眠規則，即如果其CPR值為1，并且其SC值若在所有滿足CPR規則的鄰居節點中最小時，該節點符合休眠規則可以選擇休眠。

d）一旦節點選擇休眠，就發送一則狀態廣播消息通知鄰居節點，使所有鄰居節點將該節點從其鄰居列表中刪除，從而使得具有更長退避時延的節點不會考慮這些剛決定休眠節點的信息。

4仿真及性能分析

本文采用與文獻[10]相同的無線能量模型。式（18）為發射k bit比特數據耗損的能量，由發射電路耗損和功率放大耗損兩部分構成。功率放大耗損根據發送者和接收者之間的距離分別采用自由空間模型和多路徑衰減模型。Eelec為發射電路的耗損能量；Efs和Emp分別表示兩種信道模型下功率放大所需能量。式（19）為接收k bit數據的能量耗損，僅由電路耗損引起。

ETx=k×Eelec+k×Efsd2d＜d

k×Eelec+k×Empd2d≥d (18)

ERx=k×Eelec(19)

為了驗證算法性能的優越性，基于ns－2對基于協作感知的密度控制算法（CPSBC）、基于圓盤感知模型的密度控制算法（DISK）[4]和基于概率覆蓋模型的密度控制算法（PROB）[5]分別進行了仿真。仿真的網絡環境和參數設置為：節點隨機分布在50 m×50 m的平面正方形區域，匯聚節點的坐標為(0，0)；不失一般性，傳感器的類型參數設為α=0．1和β=4[5，7]，Psense=0．2。所有傳感器均將數據發往匯聚節點，每輪數據收集的次數設為5次，數據包長度為100 Byte。與能量相關參數設為：所有節點的初始能量相等為2 J；Eelec、Efs和Emp分別設為50 nJ/bit、10 nJ/bit/m2、0.001 3 pJ/bit/m4。為了使結果更加準確，每種節點密度都取10次場景，每種場景試驗都分別進行5次，試驗數據最后取平均。度量的性能指標為網絡覆蓋率、經過一輪調度后休眠的節點個數、網絡壽命。

仿真場景1在節點部署總數為60、80、100和120這四種不同的網絡密度下分別比較三種休眠調度機制。圖1比較了三種休眠調度密度控制下的網絡覆蓋率。從圖中可以看出， CPSBC和PROB的網絡覆蓋率大于DISK。這說明圓盤感知模型是一種對網絡覆蓋的粗略描述，因此基于這種模型的休眠調度無法保證足夠的網絡覆蓋。圖2為三種密度控制下一輪產生的休眠節點數。從圖中可以看出，DISK的休眠節點數較PROB要多一些，但是仍然小于CPSBC。這是因為協作感知充分利用了多點協作探測特性，為了保證網絡覆蓋，只需要少部分節點參與工作即可。

仿真場景2部署100個節點，分別仿真三種機制下的網絡壽命。網絡壽命定義為從網絡啟動到d%節點死亡所持續的時間，以輪（rounds）來表示。假設網絡初始的節點數為100，結果如圖3所示。從圖中可以看出，由于圓盤感知模型的密度控制算法產生的休眠節點數略多(圖2)，它的能量消耗略低于概率覆蓋模型，但這種能耗的降低是以犧牲網絡覆蓋為代價的?；趨f作感知模型的網絡壽命最長，同時又能夠保證足夠的網絡覆蓋率。

5結束語

本文提出了一種基于協作感知模型的保證覆蓋的傳感器網絡密度控制算法。算法根據節點是否滿足保證覆蓋規則和是否對網絡覆蓋具有最小貢獻兩個方面來判斷節點是否可以休眠。理論分析和仿真試驗證明，與基于傳統的圓盤感知模型和概率覆蓋模型的密度控制算法相比，CPSBC協議提高了網絡壽命，保證了網絡覆蓋率。

參考文獻：

［1］孫利民，李中建，陳渝，等.無線傳感器網絡[M].北京：清華大學出版社，2005.

[2]ZHANG Honghai， HOU J C.Maintaining sensing coverage and connectivity in large sensor networks，UIUCDCSR20032351[R].Illinois:University of Iuinois at Urbana Champaign UIUC Computer Science，2003.

[3]YE Fan，ZHANG G，LU Songwu，et al.Peas:a robust energy conserving protocol for longlived sensor networks[C]//Proc of International Conference on Distribute Computer Science.2003.

[4]TIAN D，GEORGANAS N D.A coveragepreserving node scheduling scheme for large wireless sensor networks[C]//Proc of the 1st ACM International Workshop on Wireless Sensor Networks and Applications.2002:32－41.

[5]柳立峰，鄒仕洪，張雷，等.基于概率覆蓋模型的無線傳感器網絡密度控制算法[J].北京郵電大學學報，2005，28(4):1417.

[6]HUANG Chifu，TSENG Y.The coverage problem in a wireless sensor network[C]//Proc of ACM WSNA.San Diego：ACM，2003:115121.

[7]LU Jun，SUDA T.Coverageaware selfscheduling in sensor networks[C]//Proc of IEEE CCW 2003.California: IEEE， 2003:117123.

[8]MEGUERDICHIAN S，KOUSHANFAR F，QU Gang，et al.Exposure in wireless Ad hoc sensor networks[C]//Proc of ACM MOBICOM.2001:139150.

[9]LIU Benyuan，TOWSLEY D.A study on the coverage of largescale sensor networks[C]//Proc of the 1st IEEE International Conference on Mobile Ad hoc and Sensor Systems.2004.

[10]HEINZELMAN W R.An applicationspecific protocol architecture for wireless microsensor networks[J].IEEE Trans on Wireless Communications，2002，1(4): 660－670.

[11]YANG Baiwei，YU Hongyi， LI Hong，et al.A coveragepreserving density control algorithm based on cooperation in wireless sensor networks[C]//Proc of International Conference on WiCOM.Wuhan:[s.n.]，2006:1－4.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”