基于能量控制的無(wú)線傳感網(wǎng)絡(luò)最優(yōu)化算法研究

鄔學(xué)軍，孟利民，華驚宇，周明華，周 凱

(1．浙江工業(yè)大學(xué)理學(xué)院，杭州310023;2．浙江省光纖通信技術(shù)重點(diǎn)研究實(shí)驗(yàn)室，杭州310032)

無(wú)線傳感器網(wǎng)絡(luò)是一種具有全新的信息獲取、信息處理與傳輸技術(shù)的通信網(wǎng)絡(luò)，通常包含大量的可自組織成多跳無(wú)線網(wǎng)絡(luò)的分布式傳感節(jié)點(diǎn)。無(wú)線傳感網(wǎng)絡(luò)具有組網(wǎng)快捷、靈活，且不受有線網(wǎng)絡(luò)約束的優(yōu)點(diǎn)，可用于緊急搜索、災(zāi)難救助、軍事、醫(yī)療等環(huán)境中，具有廣泛的應(yīng)用前景[1-2]。

降低能耗以延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間是無(wú)線傳感器網(wǎng)絡(luò)設(shè)計(jì)中的一個(gè)重要挑戰(zhàn)。在傳感器節(jié)點(diǎn)高密度部署的環(huán)境中，在保證網(wǎng)絡(luò)性能的前提下，將最少量的節(jié)點(diǎn)投入活躍工作狀態(tài)，而將其余節(jié)點(diǎn)投入低功耗的睡眠狀態(tài)，是一種節(jié)約系統(tǒng)能量的有效方法。如何計(jì)算同時(shí)滿足“覆蓋要求”和“連通性要求”的最小節(jié)點(diǎn)集合，是一個(gè)NP-hard問(wèn)題[3]。

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

1 網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋模型

在二維平面R2上，節(jié)點(diǎn)i的覆蓋范圍是以節(jié)點(diǎn)為圓心、半徑等于感知半徑Ri的一個(gè)圓形區(qū)域。本文使用布爾傳感模型來(lái)模擬傳感器網(wǎng)絡(luò)對(duì)監(jiān)測(cè)區(qū)域的感知能力。每一個(gè)傳感器節(jié)點(diǎn)有一個(gè)確定的監(jiān)測(cè)半徑R，并且可以接收半徑以內(nèi)的刺激信號(hào)[5-6]。如果一個(gè)目標(biāo)節(jié)點(diǎn)位于一個(gè)傳感器節(jié)點(diǎn)的監(jiān)測(cè)范圍內(nèi)，就稱為是被覆蓋。對(duì)于兩個(gè)分布位于坐標(biāo)Xi和Xj的傳感器節(jié)點(diǎn)，如果|Xi-Xj|≤R，則它們是相連的。

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

對(duì)每一個(gè)A'∈A，是一個(gè)服從參數(shù)為λ·μ(A)的泊松分布隨機(jī)變量。也就是說(shuō)，當(dāng) A1，···，An∈A各不相交時(shí)，隨機(jī)變量 N(A1)，···，N(An)是互相獨(dú)立的。對(duì)于一個(gè)泊松點(diǎn)過(guò)程，在μ(U)＞0和N(U)=k的假設(shè)下，這k個(gè)點(diǎn)式獨(dú)立的，而且服從在U上的均勻分布[5]。

將上述泊松點(diǎn)過(guò)程應(yīng)用于一個(gè)二維區(qū)域A，A的面積遠(yuǎn)大于單個(gè)傳感器節(jié)點(diǎn)覆蓋的面積，節(jié)點(diǎn)之間相互獨(dú)立且均勻分布，節(jié)點(diǎn)密度為λ，用N(A)表示區(qū)域中的傳感器數(shù)目，它是一個(gè)服從以λ‖A‖為參數(shù)的泊松分布的隨機(jī)變量，‖A‖表示區(qū)域的面積，可以得到[7]:

為了滿足指定的面積覆蓋率fa，可以解這個(gè)等式來(lái)確定需要的節(jié)點(diǎn)密度λ。

圖1 面積覆蓋率與節(jié)點(diǎn)概率關(guān)系圖

當(dāng)監(jiān)測(cè)半徑為10和 fa=95%時(shí)，可以解得λ(fa)=0．009 53，區(qū)域面積‖A‖ =10 000，所以至少需要95個(gè)傳感器節(jié)點(diǎn)。

2 能量控制的網(wǎng)絡(luò)優(yōu)化算法

2．1 網(wǎng)絡(luò)生成樹(shù)模型

每個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的地位都是相等的，換言之，每個(gè)節(jié)點(diǎn)都需知道全網(wǎng)的拓?fù)浣Y(jié)構(gòu)，與此同時(shí)，由于節(jié)點(diǎn)間頻繁的交換路由信息，廣播數(shù)據(jù)可能大量占用網(wǎng)絡(luò)帶寬，并影響節(jié)點(diǎn)的發(fā)送能力，致使整個(gè)網(wǎng)絡(luò)陷入癱瘓，并消耗大量能量。為解決該問(wèn)題，一種方法是構(gòu)建虛擬骨干網(wǎng)，虛擬骨干網(wǎng)的作用類(lèi)似于有線網(wǎng)絡(luò)的核心網(wǎng)，可以實(shí)現(xiàn)網(wǎng)絡(luò)數(shù)據(jù)的交換和路由功能，如果我們將路由數(shù)據(jù)包強(qiáng)制在網(wǎng)絡(luò)的一小部分節(jié)點(diǎn)上，則由于全局?jǐn)U散導(dǎo)致的協(xié)議開(kāi)銷(xiāo)將會(huì)顯著減少。另一方面，不在虛擬骨干網(wǎng)上的節(jié)點(diǎn)可以進(jìn)入休眠狀態(tài)，但可以隨時(shí)蘇醒，并向虛擬骨干網(wǎng)中的節(jié)點(diǎn)發(fā)送信息[8-9]。

考慮問(wèn)題中的無(wú)向連通圖G，一個(gè)虛擬骨干網(wǎng)對(duì)應(yīng)于圖G中的一個(gè)連通支配集。一個(gè)支配集滿足以下條件:圖中的每個(gè)節(jié)點(diǎn)不是屬于支配集就是和支配集中的節(jié)點(diǎn)直接相鄰。連通支配集是支配集中的點(diǎn)所構(gòu)成的連通子圖。

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

(1)對(duì)圖G中的每條邊賦權(quán)值，邊的權(quán)值等于該邊連接的兩個(gè)相鄰節(jié)點(diǎn)的度之和。

(2)從任一節(jié)點(diǎn)出發(fā)，使用最小生成樹(shù)算法來(lái)求解圖G的最大生成樹(shù)T(即具有最大權(quán)值的生成樹(shù))，在具體實(shí)現(xiàn)中取權(quán)值的負(fù)值，應(yīng)用Prim算法。

(3)去掉最大生成樹(shù)T中度為1的節(jié)點(diǎn)，剩下的節(jié)點(diǎn)即構(gòu)成我們所求的連通支配集。

為了分析算法性能，本文構(gòu)建了一個(gè)100×100的傳感網(wǎng)絡(luò)，網(wǎng)絡(luò)中散落著120個(gè)節(jié)點(diǎn)。使用上述算法，可以構(gòu)造的最小生成樹(shù)如圖2所示。

圖2 網(wǎng)絡(luò)最小生成樹(shù)算法示意圖

可以發(fā)現(xiàn)，除去此生成樹(shù)的葉節(jié)點(diǎn)后，剩余構(gòu)成連通支配集的節(jié)點(diǎn)如下: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。

在通信模型中，讓連通支配集中的點(diǎn)持續(xù)工作，讓其余點(diǎn)進(jìn)入休眠狀態(tài)。這些休眠的點(diǎn)可以隨時(shí)蘇醒，向虛擬骨干網(wǎng)發(fā)送信息。這樣最大程度地節(jié)省了電力，并減小了骨干網(wǎng)中路由信息的交換，保證了網(wǎng)絡(luò)的暢通。當(dāng)一個(gè)骨干網(wǎng)之外的節(jié)點(diǎn)需與另一個(gè)節(jié)點(diǎn)通信時(shí)，我們的策略是讓它和目標(biāo)節(jié)點(diǎn)分別與一個(gè)相鄰的連通支配集中的節(jié)點(diǎn)通信，接著在連通支配集中找到它們之間的通路。

2．2 算法性能分析

對(duì)算法性能進(jìn)行分析:(1)算法的無(wú)偏性。由于從任意節(jié)點(diǎn)出發(fā)，都可以得到最優(yōu)的最大生成樹(shù)，因此無(wú)論哪個(gè)節(jié)點(diǎn)開(kāi)始構(gòu)建生成樹(shù)，最終得到的連通支配集都不會(huì)有偏差。(2)對(duì)圖中度較大的節(jié)點(diǎn)，則根據(jù)對(duì)邊賦權(quán)值的規(guī)則，與它相接的邊都有較大權(quán)值，這樣這些邊被選中的概率就較大，這會(huì)導(dǎo)致在一個(gè)度較大的節(jié)點(diǎn)周?chē)x中較多的邊，從而這個(gè)節(jié)點(diǎn)消耗較多的度，這會(huì)使得最終形成的生成樹(shù)會(huì)有更多的度為1的葉子節(jié)點(diǎn)。(3)對(duì)于圖中度較小的節(jié)點(diǎn)，根據(jù)對(duì)邊賦權(quán)值的規(guī)則，與它相連的邊的權(quán)值相對(duì)于與它的鄰接點(diǎn)相連的邊的權(quán)值要小，因此與它相連的邊被選中多條的概率就較小，因此它也就可能在最終的生成樹(shù)中成為一個(gè)葉子節(jié)點(diǎn)。(4)對(duì)于最大生成樹(shù)的求解來(lái)說(shuō)，存在一種不好的情況，即在生成最大生成樹(shù)的過(guò)程中，若多條備選邊的權(quán)值相等時(shí)，則會(huì)存在多棵權(quán)值相等的最大生成樹(shù)。這對(duì)我們利用最大生成樹(shù)來(lái)求解連通支配集是不利的。因此，當(dāng)在生成最大生成樹(shù)的過(guò)程中，若備選邊的權(quán)值相等時(shí)，算法選取依附于當(dāng)前生成樹(shù)中度最大的節(jié)點(diǎn)的邊，這樣可以避免一些極端情況的出現(xiàn)[12]。

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

圖3 通信半徑對(duì)于連通支配集數(shù)量的影響

2．3 能量控制仿真

為了對(duì)比說(shuō)明網(wǎng)絡(luò)能量控制算法的意義，本文引入網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗模型。傳感器節(jié)點(diǎn)之間是靠無(wú)線電進(jìn)行通信，發(fā)送數(shù)據(jù)包消耗能量包括發(fā)射電路耗能、放大電路耗能兩部分，接收數(shù)據(jù)只有接收電路消耗能量。

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

其中Eelec表示發(fā)射電路和接收電路的能耗，l表示發(fā)送數(shù)據(jù)包包含的比特?cái)?shù)，d表示傳輸距離，εamp和εfs是常數(shù)。

本文構(gòu)建了一個(gè)100×100的傳感網(wǎng)絡(luò)，網(wǎng)絡(luò)中散落著120個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的最初能量為“1”。對(duì)比是否使用最小生成樹(shù)算法，網(wǎng)絡(luò)節(jié)點(diǎn)平均能量變化如圖4所示。

圖4 網(wǎng)絡(luò)節(jié)點(diǎn)平均能量變化趨勢(shì)圖

3 結(jié)束語(yǔ)

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

[1]孫利民，李建中，陳渝，等．無(wú)線傳感器網(wǎng)絡(luò)[M]．清華大學(xué)出版社，2005．

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

[3]鄭祖全．無(wú)線自組網(wǎng)技術(shù)實(shí)用教程[M]．北京:清華大學(xué)出版社，2004．

[4]于宏毅．無(wú)線移動(dòng)自組織網(wǎng)[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]薛小平，李欣，張思東．基于路由生存時(shí)間的 Ad Hoc Qos路由[J]．北京交通大學(xué)學(xué)報(bào)(自然科學(xué)版)，2007，31(2):23-28．

[9]文凱，郭偉，黃廣杰．無(wú)線Ad hoc網(wǎng)絡(luò)中基于節(jié)點(diǎn)位置的功率控制算法[J]．電子與信息學(xué)報(bào)，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]袁培燕，李臘元．移動(dòng)模型對(duì)Ad hoc網(wǎng)絡(luò)路由協(xié)議能耗的影響[J]．計(jì)算機(jī)工程，2007，33(11):123-125．

[12]王敏強(qiáng)，鄭寶玉．一種新的應(yīng)用于Ad Hoc網(wǎng)絡(luò)的能量感知路由協(xié)議[J]．南京郵電學(xué)院學(xué)報(bào)，2005，25(1):13-17．