大規模無線傳感器網絡智能能量管理算法的研究

摘要:提出了一種基于規則推理的大規模無線傳感器網絡智能能量管理算法。該算法的核心思想是根據被監測實體以往情況以及當前狀態信息，通過基于規則的推理推測出下一個時間段內實體可能發生異常或者期待事件的區域，讓監測該區域的傳感器節點工作，監測其他區域的節點休眠，從而提高能量效率。最后通過模擬實驗對該算法進行了驗證。

關鍵詞:無線傳感器網絡; 能量管理; 基于規則的推理

中圖分類號:TP315文獻標志碼:A

文章編號:1001－3695(2008)02－0401－04

傳感器網絡[1]是由大量形體較小#65380;能源受限并且配置有計算和無線通信能力的傳感器節點組成的無結構網絡。它們通常散布在一定的地理區域內協同工作。傳感器網絡應用中，能源是制約網絡工作及性能的瓶頸。由于數目巨大#65380;分布范圍廣的傳感器節點不能補充能量，存在嚴重的能量約束[2]。高效使用節點的能量繼而延長網絡系統的生存期成為傳感器網絡設計的首要目標[3]。

1能耗的理論分析

傳感器節點通常由傳感模塊#65380;數據處理模塊和通信模塊組成，其能耗也為相應三個部分的能耗。其中，傳感能耗與具體的應用相關。計算能耗包括處理器和存儲器能耗兩個部分。傳感器節點需要對獲得的數據進行一定的預處理，計算能耗與傳感器節點的硬件設計#65380;計算模式密切相關。采用低能耗器件和在節點操作系統中融入能量感知方式是目前降低計算能耗的研究熱點。相比之下，通信能耗最大。Gregory分析得出，傳感器節點使用無線方式傳輸1 bit到100 m處遠所消耗的能量可供執行3 000行指令[4]。因此，通信能耗是能量管理研究的重點。

首先，從信息有效性的角度來分析無線傳感器網絡的能量效率問題。假設在一個時間段t內，一個無線傳感器網絡的sink節點共收到N個數據包，每個數據包的內容可以是一個傳感器節點報告的監測數據。其中有效信息(指需要網絡作出反應的信息)有N條;其他信息不會影響對實體的監測或影響實體采取的行動。

由式(8)可見，隨著冗余數據包的增加，能量的浪費并不是隨之線性增加，而是加速增加。因此減少冗余數據包的傳遞意義十分重大，而這也正是目前節能策略不完善之處。

2節能機制設計

基于規則推理的能量管理算法(rule－based energy management，RBEM)作用于應用層，它是基于層次型拓撲結構控制。無線傳感器網絡中的傳感器節點要分簇，分簇的算法與簇首的選取可以用現有的算法。分簇的目的是為了數據融合，減少通信量，提高數據質量。當然，如果整個網絡傳感器節點數目較少，也可以直接針對所有節點進行。

2.1若干概念定義

定義1狀態是一組傳感器節點(簇首節點的集合)在某一個時刻監測到的實體數據。狀態直接關系到推理規則，為提高推理效率，需要控制狀態的數目。因此可以先對監測到的每組數據進行標準化(如整數化#65380;向某個集合進行映射等)，然后再將其作為一個狀態。

RBEM算法將狀態分為一般狀態和警戒狀態兩類。一般狀態是指該狀態所表現的實體情況為正常情況，人們不必關注也不必采取應對措施，如病人在正常情況下各個傳感器節點監測到的數值就是一般狀態。警戒狀態是指引起人們注意并需要采取行動的狀態。這兩種狀態的標記可以由系統自動完成:系統根據程序接收到數據后的反應情況(如是否啟動了某項應急措施等)判斷狀態類型，或者用戶通過應用程序直接標記狀態類型。

定義2關鍵節點是指一般狀態向某警戒狀態轉變時數值發生劇烈變化的節點。所謂劇烈，可以人工定義閾值，如超過原值的50%。每個一般狀態在向某個警戒狀態轉變時，會有幾個關鍵節點。一個一般狀態可能會向幾個警戒狀態轉變，把對應所有關鍵節點集合起來，形成一個此一般狀態對應的關鍵節點集。對于一個警戒狀態，它的關鍵節點集合可以人為指定，也可以由系統將所有簇首節點列為關鍵節點集。注意，關鍵節點并不一定是指某個具體的節點，它很可能只是指某個簇的簇首，而簇首節點通常會輪換變化。

定義3狀態取樣時間。根據實際情況，定義一個合適的時間長度。每隔這個時間長度，所有簇首節點工作一次，采集該次的相關狀態，即狀態取樣。

定義4能量均衡最佳路徑。從sink節點到各個簇首節點有一條能量均衡最佳路徑，該路徑上所有節點使用次數的和最小。

2.2RBEM算法描述

RBEM算法的核心思想是:進入一般狀態后，只讓關鍵節點集工作，其他節點休眠。通常，讓非關鍵節點休眠，表示非關鍵節點(這些節點都是簇首)所代表的簇徹底休眠;讓關鍵節點集工作，是指關鍵節點所代表的簇工作。其算法流程如圖1所示。

兩次狀態取樣之間的節點工作方式是只有該狀態對應的關鍵節點集工作，非關鍵節點休眠。關鍵節點工作時，不必開啟通信模塊，可以讓通信模塊休息，而只讓傳感和計算模塊工作。如果某個關鍵節點監測到了數據的劇變(可能是這個關鍵節點所代表的簇中的非簇首節點監測到了劇變，則先將信息傳遞給這個簇首節點)，則喚醒沿途其他骨干節點，將這個信息傳遞給sink節點。

狀態判斷是關鍵問題，狀態的識別判斷要由推理機完成。推理機的規則庫中存放大量的規則。規則的左側是該狀態的數據值，推理機將采樣獲得的狀態數據與規則庫中規則的左側進行匹配;規則的右側是該狀態的關鍵節點集合，如果一個狀態是已知狀態，推理機將會找出與之匹配的規則，得出它的關鍵節點集。如果取樣獲得的狀態經過推理后沒有被匹配，那么它是一個新發現的狀態。首先要確定這個狀態是一般狀態還是警戒狀態。如果是一般狀態，要向規則庫中增添一條與之對應的規則:規則左側是該狀態的數值;規則右側的關鍵節點集合可以暫時設定為空，或人為指定一些關鍵節點。如果新狀態是警戒狀態，要將這個狀態的數據與上一個狀態比較，將數據劇變的節點增加為上一個狀態的關鍵節點，修改上一個狀態對應規則的右側。同時，在規則庫中還要增添一條與這個注意狀態對應的規則，規則的右側可以暫時設定所有節點為關鍵節點，或者人為指定一些關鍵節點。

RBEM算法需要一個初始化階段，其主要任務為搜集狀態，確定關鍵節點集。初始化需要一段時間，這段時間長度人為定義。這段時間里，推理機不斷發現新的狀態#65380;產生新的規則，推理機具有自動學習功能。在初始化時間里，可以讓所有節點都不休眠，以便窮盡所有狀態。

2.3網絡連通性控制

前文已經討論過，應用層的能量管理方案不能保證無線傳感器網絡連通性。下面介紹一個與RBEM算法配套的連通性控制方案。該連通性控制方案主要考慮兩個問題:在應用層準許某些節點休眠后，通過連通性控制保證無線傳感器網絡暢通;讓各個節點能量消耗盡量均勻，避免單點能耗過大而出現sinkhole現象。

連通性控制方案的設計思想如下:各個簇首節點通過分布式路由層協議給sink節點一張可達性表，即節點之間是否可以單跳直接通信。實際這張表是由各個節點互相發送hello報文，測試與周圍節點是否可通信;在每個節點內生成一個局部表，再將各個節點的表進行一系列轉發，匯聚到sink節點，由sink節點進行綜合生成。在sink節點中，記錄著每個節點(該簇首節點代表的簇)的使用次數。在進行過一次采樣推理之后，某節點若不能休息，則使用次數加1。

從sink節點到各個簇首節點有一條能量均衡最佳路徑，該路徑上所有節點使用次數的和最小。沿著能量均衡最佳路徑向sink節點傳遞數據，可以避免經過已使用很多次的節點，從而避免形成空洞。選擇能量均衡最佳路徑的具體算法是著名的Dijkstra最短路徑算法。它先生成一張由簇首節點組成的圖，兩個節點若一跳可達則在它們之間存在弧，這里把每個弧的弧頭節點使用次數作為該弧的權值;然后可以用Dijkstra算法求出每個簇首節點到sink節點的能量均衡最佳路徑。

在每次狀態取樣后，或者傳感器節點位置發生變化，或者某個簇發生簇首輪換時，要重新計算每個簇首節點到sink節點的能量均衡最佳路徑。

每次狀態取樣判斷后會獲得一些關鍵節點。在這些關鍵節點到網關的最佳路徑上，如果某個節點應當休眠，則它不能休眠，但是它所代表的簇內的其他節點仍然可以休眠。當關鍵節點有劇變數據需要傳輸時，它的通信單元需要開通以傳遞數據，從而保障網絡連通性。

3結果分析與模擬試驗

下面通過理論分析方法來對RBEM方案的某些方面進行評價。

1)單位時間總能耗設時間t為RBEM算法的狀態采樣周期，下面比較一下STEM和RBEM算法在時間t內的平均總能耗。無線傳感器網絡最大的能量消耗在通信上，故忽略傳感能耗#65380;計算能耗。設N為簇首節點的個數，設p為每個簇首節點在一個時間單位內監測到數據劇變的概率，那么一個簇首節點在時間t內向sink節點發送信息的條數為p×t。假設從簇首節點到sink節點發送每條消息需要耗能e個能量單位(這里忽略了當網絡中傳遞的信息較多時由于擁塞導致能耗增加)，那么在時間t內，如果這個網絡應用STEM算法，它總共能耗為

當N=100，q=0.5，e=1，t=10時，兩種算法在時間T內的能耗與p的關系如圖2所示。從圖中可以看出，當p的值較小時，STEM算法耗能較小;但是隨著p的增大，RBEM算法明顯顯示出節能的優勢。這說明:對于偶然性較強的應用場景(如草原火災監測)，STEM算法比較適合;對于數據經常有規律變化的場景，RBEM比較合適。

下面再討論一下q的關系。固定p的值，當p=0.25，N=100，t=10，e=1時，這兩種方案在時間t內的能耗如圖3所示。從圖中可以看出，當q較小，即RBEM算法僅讓很少的簇首節點工作時，RBEM比較節能;但是當q增大時，RBEM的能量消耗會逐漸超過STEM。因此它的核心目的之一是在保障檢測率的基礎上盡量減小q。

下面再討論一下RBEM算法的單位時間能量總消耗與采樣周期t的關系。令N=100， q=0.5，p=0.25，e=1，則這兩種算法的單位時間總能耗與t的關系如圖4所示。從圖中可以看出，t很小時，STEM算法要比RBEM算法優秀很多。t越大RBEM算法的節能效果就越好。所以RBEM算法的另一個核心目標就是在保障檢測率的基礎上盡可能延長采樣周期。

采用MATLAB作為算法驗證的工具。結合中間件試驗床實現的場景，本文在驗證算法時采用了醫療護理的實例。監測對象情況為:病人患病后經手術治療，監測該病人在術后第三天的生理狀況;從零時，至次日零時進行監測。該病人28歲，男，身體健康狀況良好，呼吸性竇性心律不齊，吸氣時心率加快，呼氣時心率變緩。

模擬實現過程為:同時監測該病人的有兩組傳感器節點，每組包含監測心率#65380;體溫#65380;呼吸#65380;血壓的傳感器;每組中每個監測內容由兩個傳感器監測。這兩組傳感器硬件完全一樣。現對一組使用STEM算法，對另一組使用RBEM算法，將監測數據#65380;能量消耗數據記錄下來，然后用MATLAB畫圖比較。

節點的狀態直接影響節點的能源消耗。休眠的節點越多，整個網絡的能耗就相對越低，因此也就越節能，但同時也會帶來網絡覆蓋率的變化。圖5是對于一個監測病人身體狀況的無線傳感器網絡應用STEM與RBEM算法的能量消耗結果。如圖所示，由于病人心率變化較大，應用STEM算法的組經常會監測到數據劇變，并且每次都會向網關報告;應用RBEM算法的組，經過一段時間后會發現心率變化與呼吸有關，不必每次監測到心率變化都向網關報告，因此能量消耗比STEM低。

4結束語

RBEM方案的一個潛在問題是對檢測率的影響，讓一部分節點休眠很可能會降低檢測率。解決這一問題可以從以下幾個方面入手:從場景的選擇方面進行研究，任何方案都不能適用于所有場景，通過理論分析或模擬仿真選擇出最適合IEM的場景，并歸納出這些場景的共性;從推理規則方面入手，除了推理機制自動發現的規則外，可以人工加入一些規則，從而保障關鍵區域的檢測率;與其他控制覆蓋度#65380;檢測率的方案結合，可以設定不同層面方案的優先級別，優先保障某具體場景下網絡最期望達到的特性。

在智能推理方面，如何在較短時間內讓推理機發現所有狀態#65380;生成對應規則，這是一個需要解決的問題。另外，推理機的效率#65380;與推理機的交互方式方面還有很多需要改進之處。

參考文獻:

[1]AKYILDIZ I F， SU W， SANKARASUBRAMANIAM Y， et al. Wireless sensor networks: a survey[J]. Computer Networks， 2002，38(4):393－422.

[2]PERING T， BURD T， BRODERSEN R. Dynamic voltage scaling and the design of a low－power microprocessor system[C]//Proc of Power Driven Micro－architecture Workshop. 1998.

[3]SINHA A， CHANDRAKASAN A. Dynamic power management in wireless sensor networks[J]. IEEE Design Test of Computers， 2001，8(2):62－74.

[4]KUBISCH M， KARL H， WOLISZ A， et al. Distributed algorithm for transmission power control in wireless sensor networks[C]//Proc of IEEE Wireless Communications and Networking Conference. 2003:16－20.

[5]LI Ning， HOU J C. Topology control in heterogeneous wireless networks: problems and solutions[C]//Proc of the 13th Joint Conf on IEEE Computer and Communications Societies. Hong Kong:[s.n.]， 2004.

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