基于能量控制的無線傳感網絡最優化算法研究

鄔學軍，孟利民，華驚宇，周明華，周 凱

(1．浙江工業大學理學院，杭州310023;2．浙江省光纖通信技術重點研究實驗室，杭州310032)

無線傳感器網絡是一種具有全新的信息獲取、信息處理與傳輸技術的通信網絡，通常包含大量的可自組織成多跳無線網絡的分布式傳感節點。無線傳感網絡具有組網快捷、靈活，且不受有線網絡約束的優點，可用于緊急搜索、災難救助、軍事、醫療等環境中，具有廣泛的應用前景[1-2]。

降低能耗以延長網絡生存時間是無線傳感器網絡設計中的一個重要挑戰。在傳感器節點高密度部署的環境中，在保證網絡性能的前提下，將最少量的節點投入活躍工作狀態，而將其余節點投入低功耗的睡眠狀態，是一種節約系統能量的有效方法。如何計算同時滿足“覆蓋要求”和“連通性要求”的最小節點集合，是一個NP-hard問題[3]。

密度控制是實現上述目的的重要而有效的手段。所謂密度控制，就是在不犧牲系統性能的前提下，將一部分節點投入低功耗的睡眠狀態，只保留部分節點作為活躍工作節點。這樣，可以降低網絡中活躍節點的密度、降低感知數據的冗余性以及減少無線通信沖突和干擾，從而降低整個系統的能量消耗[3]。密度控制可以有效地延長無線傳感器網絡的生存時間。為保持網絡原有性能，密度控制必須滿足以下兩個條件:(1)保證目標區域的完全覆蓋;(2)保證通信網絡的連通性，即所有工作節點組成的通信網絡必須仍然是連通的[4]。

1 網絡節點覆蓋模型

在二維平面R2上，節點i的覆蓋范圍是以節點為圓心、半徑等于感知半徑Ri的一個圓形區域。本文使用布爾傳感模型來模擬傳感器網絡對監測區域的感知能力。每一個傳感器節點有一個確定的監測半徑R，并且可以接收半徑以內的刺激信號[5-6]。如果一個目標節點位于一個傳感器節點的監測范圍內，就稱為是被覆蓋。對于兩個分布位于坐標Xi和Xj的傳感器節點，如果|Xi-Xj|≤R，則它們是相連的。

假設節點的部署服從泊松點過程，U∈Rn是n維空間的一個子集，A是U的一個非空子族，假定每一個元素A'∈A有容量μ(A)。更進一步，假設大量的“點”分散在U上。本文實際關注的是某個A'∈A的那些點數，這個量表示為N(A)。強度為λ＞0的泊松點過程具有如下性質:

對每一個A'∈A，是一個服從參數為λ·μ(A)的泊松分布隨機變量。也就是說，當 A1，···，An∈A各不相交時，隨機變量 N(A1)，···，N(An)是互相獨立的。對于一個泊松點過程，在μ(U)＞0和N(U)=k的假設下，這k個點式獨立的，而且服從在U上的均勻分布[5]。

將上述泊松點過程應用于一個二維區域A，A的面積遠大于單個傳感器節點覆蓋的面積，節點之間相互獨立且均勻分布，節點密度為λ，用N(A)表示區域中的傳感器數目，它是一個服從以λ‖A‖為參數的泊松分布的隨機變量，‖A‖表示區域的面積，可以得到[7]:

為了滿足指定的面積覆蓋率fa，可以解這個等式來確定需要的節點密度λ。

圖1 面積覆蓋率與節點概率關系圖

當監測半徑為10和 fa=95%時，可以解得λ(fa)=0．009 53，區域面積‖A‖ =10 000，所以至少需要95個傳感器節點。

2 能量控制的網絡優化算法

2．1 網絡生成樹模型

每個節點在網絡中的地位都是相等的，換言之，每個節點都需知道全網的拓撲結構，與此同時，由于節點間頻繁的交換路由信息，廣播數據可能大量占用網絡帶寬，并影響節點的發送能力，致使整個網絡陷入癱瘓，并消耗大量能量。為解決該問題，一種方法是構建虛擬骨干網，虛擬骨干網的作用類似于有線網絡的核心網，可以實現網絡數據的交換和路由功能，如果我們將路由數據包強制在網絡的一小部分節點上，則由于全局擴散導致的協議開銷將會顯著減少。另一方面，不在虛擬骨干網上的節點可以進入休眠狀態，但可以隨時蘇醒，并向虛擬骨干網中的節點發送信息[8-9]。

考慮問題中的無向連通圖G，一個虛擬骨干網對應于圖G中的一個連通支配集。一個支配集滿足以下條件:圖中的每個節點不是屬于支配集就是和支配集中的節點直接相鄰。連通支配集是支配集中的點所構成的連通子圖。

本文使用一種基于最小生成樹的貪婪策略來求解連通支配集。為了最終得到的生成樹有更多的葉子節點，也就是說讓最后的生成樹中有更多的度為1的節點。若生成樹有n個節點，這連通這棵樹的邊為(n-1)條，度之和恒為2(n-1)。因此，在圖G中，應該選擇度盡量大的節點來逐步構造這顆生成樹。然而，僅考慮節點的度來選擇節點，對于最后的連通性考慮是不利的。所以本文使用的算法應用如下策略[10-11]:

(1)對圖G中的每條邊賦權值，邊的權值等于該邊連接的兩個相鄰節點的度之和。

(2)從任一節點出發，使用最小生成樹算法來求解圖G的最大生成樹T(即具有最大權值的生成樹)，在具體實現中取權值的負值，應用Prim算法。

(3)去掉最大生成樹T中度為1的節點，剩下的節點即構成我們所求的連通支配集。

為了分析算法性能，本文構建了一個100×100的傳感網絡，網絡中散落著120個節點。使用上述算法，可以構造的最小生成樹如圖2所示。

圖2 網絡最小生成樹算法示意圖

可以發現，除去此生成樹的葉節點后，剩余構成連通支配集的節點如下:3、4、5、7、8、10、12、13、14、15、16、17、18、22、27、30、32、33、35、36、37、39、41、45、47、50、52、53、54、57、59、60、61、64、65、66、69、70、73、75、76、78、79、80、81、87、89、93、95、97、98、99、100、102、104、105、107、110。

在通信模型中，讓連通支配集中的點持續工作，讓其余點進入休眠狀態。這些休眠的點可以隨時蘇醒，向虛擬骨干網發送信息。這樣最大程度地節省了電力，并減小了骨干網中路由信息的交換，保證了網絡的暢通。當一個骨干網之外的節點需與另一個節點通信時，我們的策略是讓它和目標節點分別與一個相鄰的連通支配集中的節點通信，接著在連通支配集中找到它們之間的通路。

2．2 算法性能分析

對算法性能進行分析:(1)算法的無偏性。由于從任意節點出發，都可以得到最優的最大生成樹，因此無論哪個節點開始構建生成樹，最終得到的連通支配集都不會有偏差。(2)對圖中度較大的節點，則根據對邊賦權值的規則，與它相接的邊都有較大權值，這樣這些邊被選中的概率就較大，這會導致在一個度較大的節點周圍選中較多的邊，從而這個節點消耗較多的度，這會使得最終形成的生成樹會有更多的度為1的葉子節點。(3)對于圖中度較小的節點，根據對邊賦權值的規則，與它相連的邊的權值相對于與它的鄰接點相連的邊的權值要小，因此與它相連的邊被選中多條的概率就較小，因此它也就可能在最終的生成樹中成為一個葉子節點。(4)對于最大生成樹的求解來說，存在一種不好的情況，即在生成最大生成樹的過程中，若多條備選邊的權值相等時，則會存在多棵權值相等的最大生成樹。這對我們利用最大生成樹來求解連通支配集是不利的。因此，當在生成最大生成樹的過程中，若備選邊的權值相等時，算法選取依附于當前生成樹中度最大的節點的邊，這樣可以避免一些極端情況的出現[12]。

最后，考慮到由于能量的減少，節點的覆蓋范圍會減小。本節計算了在不同的覆蓋半徑下所得的連通支配集節點數。其中的臨界值分別是9．22，9．49，9．55，9．99。當覆蓋半徑小于 9．22 時，節點119不被其它任何節點覆蓋。鑒于此，我們提出隨節點覆蓋半徑而改變的連通支配集節點數策略:當電量充足，即覆蓋半徑為10時，使用上述CDS。當節點的覆蓋半徑在臨界值處變化時，重新計算CDS，得到新的虛擬骨干網，直至某些節點無法被覆蓋到，此時整個網絡的監測能力也將變化。

圖3 通信半徑對于連通支配集數量的影響

2．3 能量控制仿真

為了對比說明網絡能量控制算法的意義，本文引入網絡節點能量消耗模型。傳感器節點之間是靠無線電進行通信，發送數據包消耗能量包括發射電路耗能、放大電路耗能兩部分，接收數據只有接收電路消耗能量。

發送者和接收者之間的距離d，則發送者消耗能量ETx(l)計算公式為和接收者消耗能量ERx(l)計算公式如下:

其中Eelec表示發射電路和接收電路的能耗，l表示發送數據包包含的比特數，d表示傳輸距離，εamp和εfs是常數。

本文構建了一個100×100的傳感網絡，網絡中散落著120個節點，每個節點的最初能量為“1”。對比是否使用最小生成樹算法，網絡節點平均能量變化如圖4所示。

圖4 網絡節點平均能量變化趨勢圖

3 結束語

本文首先使用基于泊松點過程的布爾傳感模型確定了覆蓋率與單位面積內傳感器節點密度的函數關系，進而求得區域內節點總數，然后利用基于Prim算法的貪婪策略，找到具有最大權值的生成樹，構造一個求最小連通支配集的近似解。最后，進一步分析了連通支配集中節點個數與覆蓋半徑的關系。

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

[2]鄭四海，李臘元．Ad Hoc網絡QoS多徑路由協議的研究[J]．武漢理工大學學報(交通科學與工程版)，2008，32(3):450-453．

[3]鄭祖全．無線自組網技術實用教程[M]．北京:清華大學出版社，2004．

[4]于宏毅．無線移動自組織網[M]．北京:人民郵電出版社，2005．

[5]Garcia-Luna-Aceves J，Roy S．On-Demand Loop-Free Routing with Link Vectors(OLIVE)[J]．IEEE Journal on Selected Areas in Communications，2005，23(3):533-546．

[6]WU X X，Bhargava B．AO2P:Ad Hoc On-Demand Position-Based Private Routing Protocol[J]．IEEE Transactions on Mobile Computing，2005，4(4):335-348．

[7]Anastasi G，Conti M，Gregori E，et al．An Energy-Aware Multimedia Streaming Protocol for Mobile Users[J]．Journal of Pervasive Computing and Communications，2006，1(4):42-50．

[8]薛小平，李欣，張思東．基于路由生存時間的 Ad Hoc Qos路由[J]．北京交通大學學報(自然科學版)，2007，31(2):23-28．

[9]文凱，郭偉，黃廣杰．無線Ad hoc網絡中基于節點位置的功率控制算法[J]．電子與信息學報，2009，31(1):201-205．

[10]Nabar R U，B?lcskei H，Kneubühler F W．Fading Ralay Channels:Performance Limits and Space-Time Signal Design[J]．IEEE journal on Selected Areas in Communications，2004，22(6):1099-1109．

[11]袁培燕，李臘元．移動模型對Ad hoc網絡路由協議能耗的影響[J]．計算機工程，2007，33(11):123-125．

[12]王敏強，鄭寶玉．一種新的應用于Ad Hoc網絡的能量感知路由協議[J]．南京郵電學院學報，2005，25(1):13-17．