無線傳感器網絡自適應功率控制策略

趙學健 莊 毅 趙 潔 薛佟佟

①(南京航空航天大學信息科學與技術學院 南京 210016)②(南京郵電大學通信與信息工程學院 南京 210003)

1 引言

無線傳感器網絡是由大量微型傳感器節點通過無線通信方式形成的一個多跳的自組織的網絡系統。由于其能量由電池提供并且難以得到補充，所以能量的高效利用是無線傳感器網絡的一個重要研究課題。迄今為止，人們已經在這方面做了大量的研究工作，拓撲控制便是最有效的策略之一[1]。

拓撲控制是指構造一個優化的拓撲結構，使網絡具有最優的能耗效率，并且保持網絡對所檢測區域的覆蓋[2]以及連通性，兼顧通信干擾、網絡延遲、魯棒性等其他性能。目前主要的拓撲控制策略可以分為3大類：基于節點功率控制的拓撲控制策略、層次型拓撲控制策略和基于啟發機制的拓撲控制策略[3]。在功率控制方面，已經提出了COMPOW[4]等統一功率分配算法，RNG[5]等基于臨近圖的功率控制算法，LMN/LMA[6]等基于節點度數的功率控制算法和XTC[7]等基于鄰節點信息交互的功率控制算法。但是，目前的功率控制算法或者需要節點的精確位置信息，或者鄰近節點信息交互量大，或者沒有考慮網絡的魯棒性，大部分算法只是針對網絡拓撲的某一方面進行了優化。更為嚴重的是，幾乎所有的拓撲控制算法都是為了獲得一個優化的目標拓撲，使網絡更加稀疏，節點發射半徑更加小，而沒有考慮在網絡的運行過程中，隨著網絡運行環境的變化以及節點能量的消耗如何保持網絡的連通性，使網絡能夠長時間正常工作。

基于上述分析，本文提出了一種適用于無線傳感器網絡的自適應功率控制策略APCS(Adaptive Power Control Strategy)，該策略是分布式的，只需要局部網絡信息，通過調整路徑損耗指數和功率控制參數可以獲得類似RNG[5]，GG[8]等性能極佳的目標拓撲，并能滿足實時性和容錯能力要求較高的應用場景。更重要的是，該算法允許節點在網絡運行過程中動態調整功率控制參數以保持網絡連通，從而延長網絡的生命周期。

2 模型與假設

(1)通信模型 在無線傳感器網絡中，通常采用對數距離路徑損耗模型對接收端信號強度進行預測。該模型是結合理論分析和對實地測量的實驗數據進行反向曲線擬合獲得的，可看作自由空間傳播模型和二徑傳播模型的推廣，公式如下：

式中，d表示發射節點和接收節點之間的距離，α表示路徑損耗指數，Pt表示發射功率，Pr(d)表示距離發射節點距離為d時接收到的信號強度。其中α的值取決于周圍的工作環境，其取值范圍介于1.6-6之間[9]。

(2)假設 (a)N個節點均勻分布在2維或者3維歐式空間內，節點一經布置后靜止不動。(b)所有節點間無線信道符合對數距離路徑損耗模型，因此節點發射功率和節點發射半徑是等價的兩個概念。(c)存在理想MAC協議對信道競爭以及信號沖突等進行處理，本文分析算法在理想狀態下的性能。

3 APCS算法

(1)相關定義 無線傳感器網絡用G=(V(G),E(G))表示，其中V(G)和E(G)分別表示節點集合和邊集合。節點u到節點v之間的有向邊用序偶(u, v)表示，dist(u, v)表示兩節點之間的歐式距離，所有節點具有相同的最大發射功率Rmax。

定義1 邊的權重(Wuv)：Wuv表示節點u發送單位字節數據到節點v的能量消耗，W(u, v)∝dist(u, v)α，其中α為路徑損耗指數。

定義2 原始拓撲(GS)：所有節點均使用最大發射功率Rmax時得到的網絡拓撲。

定義3 目標拓撲(GT)：使用某具體拓撲算法得到的拓撲結構，可用所采用的拓撲算法作為下標。

定義4 物理鄰居節點集合(PNS(u))：節點u的物理鄰居節點集合PNS(u)={v|dist(u, v)≤rmax,v ∈V(G)}。

定義5 虛擬鄰居節點集合(LNS(u))：節點u的虛擬鄰居節點集合PNS(u)={v|dist(u, v)≤ru, v ∈V(G)}，其中ru表示節點u的發射半徑。

定義6 中繼區(DR)：當節點u和節點v之間的通信需要通過節點w進行中轉時，稱節點w為中繼節點，滿足中繼節點w位置條件約束的區域稱為中繼區。

(2)算法描述 APCS算法是基于相關鄰近圖思想提出的一種自適應功率控制策略，主要包括以下步驟：

(a)鄰居排序：各節點使用最大發射功率Rmax廣播一個HELLO消息，消息包含各節點ID。因此，節點u可以收到所有鄰居節點的HELLO消息，并且將節點ID加入到物理鄰居節點集合PNS(u)中。然后，節點u對其PNS(u)中所有的鄰居節點計算一個反映鏈路質量的偏序?u。在?u中，如果節點w在節點v的前面，記作w?uv，則說明節點u與w之間的鏈路質量比節點u與v之間的鏈路質量好。所謂的鏈路質量可以指鏈路的通信代價、通信延遲等，本文指鏈路的通信能耗。

(b)鏈路選擇：節點u向其鄰居廣播自己的偏序?u，同時接收鄰居節點建立的?。節點u按鏈路質量遞增的順序遍歷?u，對于u的鄰居節點v，如果在?u中存在節點w滿足條件：w?uv，w?vu，并且使得不等式Wuw+Wvw＜λWuv(W∝dα)成立，其中α為路徑損耗指數，λ為功率控制參數，則節點u和節點v之間不存在鏈路，即v?LNS(u)；否則在節點u和節點v之間建立一條鏈路，即v∈LNS(u)。

(c)功率選擇：節點u選擇合適的發射功率使得其發射半徑恰好能夠覆蓋LNS(u)中所有節點，即節點u發射半徑為ru≥dist(u, w)，w∈LNS(u)，并且對于?v∈LNS(u)，有dist(u, v)≤dist(u, w)。

(d)動態功率調整：為網絡中所有節點設定定時器T，當定時器觸發時，判斷節點度(邏輯鄰居節點集合中元素個數)是否減小，如果減小進行功率動態調整，否則繼續正常工作。功率動態調整策略如下：節點進入退避狀態，啟動一個退避計時器，退避時間t?T，當計時達到退避時間后結束退避狀態。在節點處于退避狀態時，如果收到其它節點的CONNECT消息，則將該節點加入LNS(u)，否則該節點將按步長0.1減小功率控制參數，從而調整節點發射功率，直到節點邏輯鄰居節點集合增大或者λ達到最小值為止。最后，節點向新加入鄰居節點發送CONNECT消息。

(3)拓撲性質分析

定理1 連通性：GAPCS連通當且僅當原始拓撲結構圖GS為連通圖。

證明 對于連通性，使用反證法容易得證，不再贅述。

定理2 對稱性：GM?XTC滿足對稱性，即節點u在節點v的邏輯鄰居節點集LNSv中，當且僅當節點v也在節點u的邏輯鄰居節點集LNSu中時。

證明 首先利用反證法證明充分性，假設1：v∈LNSu；假設2：u∈LNSv。由假設2，根據APCS算法可知存在節點w滿足條件：w?vu, w?uv,且Wuw+Wvw＜λWuv。由該條件，根據APCS算法，可得結論：v∈，這與假設1矛盾，充分性得證。必要性同理可證。

定理3 平面性： 當λ=1時，GAPCS滿足平面性，即GAPCS中不含有兩條相交的邊。

證明 利用反證法證明，假設GAPCS中有兩條邊(u, v)和(w, x)相交，則在矩形uvwx中至少有一個角大于等于π/2，不妨設頂點為u的角∠wux≥π/2,則有dist(uw)＜dist(wx),dist(ux)＜dist(wx)并且Wuw+Wux≤Wwx,根據APCS算法有x∈，與假設邊(w, x)在圖GAPCS中矛盾，定理3得證。

定理4 還原性：如果網絡中沒有3個節點在同一條長為Rmax的線段上，則當λ=0.5時，GAPCS即為GS。

證明 根據前面分析可知，如果Wuw+Wvw=0.5Wuv，則節點w必然位于邊(u, v)的中點。由于網絡中沒有3個節點在同一條長為Rmax的線段上，所以對于網絡中任意節點對(u, v)，不存在節點w滿足Wuw+Wvw≤0.5Wuv。因此，對于網絡中任意節點u，(u)=?，即GAPCS=GS，定理4得證。

定理5 稀疏性：當APCS算法采用相同的路徑損耗指數α時，如果功率控制參數λ1＜λ2，則E(GAPCS?λ2)?E(GAPCS?λ1)。

證明 采用反證法進行證明，假設存在邊(u, v)在GAPCS?λ2中但是不在GAPCS?λ1中。根據APCS算法可知，必然存在節點w 滿足：w?vu∧w?uv ∧Wuw+Wvw≤λ1Wuv并且w?vu∧w?uv∧Wuw+Wvw＞λ2Wuv，可得λ1＞λ2，與定理中條件λ1＜λ2矛盾，定理5得證。

推論1 E(GRNG)?E(GAPCS)。

證明 由RNG算法和APCS算法可知，DR?APCS＜DR?RNG，因此如果邊(u, v)∈E(GRNG)，必有(u, v)∈E(GAPCS)，推論1得證。

推論2 當λ=1，α＞2時，有E(GAPCS)?E(GGG)；當λ=1，α=2時，有E(GAPCS)=E(GGG)；當λ=1，α＜2時，有E(GAPCS)?E(GGG)。

證明 由GG算法和APCS算法可知，當λ=1，α=2時，DR?APCS=DR?GG，因此E(GAPCS)=E(GGG)；當λ=1，α＞2時，DR?APCS＞DR?GG，有E(GAPCS)?E(GGG)；當λ=1，α＜2時，DR?APCS＜DR?GG，有E(GAPCS)?E(GGG)。推論2得證。

推論3 當α=2時，有E(GAPCS)?E(GGG)。

證明 由前面分析可知，功率控制參數λ∈[21?α,1)。由GG算法和APCS算法可知，當α=2，λ＜1時，DR?APCS＜DR?GG，同理E(GAPCS)?E(GGG)得證。

4 實驗分析

本文使用仿真工具OMNET++實現了RNG算法、GG算法以及APCS算法，進而分析了路徑損耗指數α以及功率控制參數λ對APCS算法所構造網絡拓撲性能的影響，并與RNG算法與GG算法所得網絡拓撲的性能進行了比較。仿真中將70個節點(ID編號：0～69)隨機散布在800 m×500 m的矩形區域中，設節點最大發射功率為0.32 W，對應最大發射半徑Rmax為200 m。對于相同的仿真參數設置，運行仿真實驗20次，以下分析數據均為20次實驗數據平均值。

原始拓撲GS以及各拓撲算法所得目標拓撲如圖1所示，該圖直觀地描述并驗證了APCS算法的相關拓撲性質，如連通性、對稱性、還原性、平面性與稀疏性及其3個推論都在上圖中得到了很好的體現。

圖2描述了RNG算法，GG算法以及APCS算法在取不同的路徑衰減指數和功率控制參數情況下，網絡中節點的平均發射半徑。由于較小的發射半徑能夠降低節點的能耗，減少網絡中的信號沖突，增大網絡容量，因此減小節點的發射半徑是拓撲算法追求的一個主要目標之一。由圖2可以看出，APCS算法在路徑衰減指數為6，功率控制參數為1時，可以得到跟RNG算法近似的平均發射半徑。

圖3描述了RNG算法，GG算法以及APCS算法在取不同的路徑衰減指數和功率控制參數情況下，網絡中節點到匯聚節點的平均跳數。由于網絡中數據的發送延遲通常跟節點至匯聚節點路徑上的跳數成正比，因此減小平均最小跳數有利于降低延遲。由圖3可以看出，當路徑衰減指數和功率控制參數減小時，節點平均最小跳數也在減小。也就是說，APCS算法可以通過調整路徑衰減指數和功率控制參數來滿足對數據實時性要求較高的應用場景。

圖1 拓撲結構圖

圖2 平均發射半徑分析圖

圖3 平均最小跳數分析圖

圖4 節點平均度分析圖

圖5 網絡生命周期分析圖

圖4描述了RNG算法，GG算法以及APCS算法在取不同的路徑衰減指數和功率控制參數情況下，網絡中節點的平均度。我們知道在一個k-頂點連通的網絡中，任意k-1個節點失效網絡仍能保持連通并發送數據，該網絡的容錯能力為k-1。k-頂點連通指網絡中節點的最小度為k，節點的平均度為k不能保證網絡是k-連通的。但是，節點的平均度在一定程度上也能反映網絡的容錯能力。由圖4可以看出，當路徑衰減指數和功率控制參數取值分別為6，1和2，1時，APCS算法節點的平均度分別與RNG算法和GG算法節點的平均度相當，并且當路徑衰減指數和功率控制參數逐漸減小時，節點平均度逐漸增大，即網絡具有更好的容錯能力和魯棒性。

仿真圖5描述了RNG算法，GG算法和APCS算法(α=2,λ=1)網絡生命周期的變化情況。由圖5可以看出，APCS算法由于采用了動態功率調整策略大大延長了網絡的生命周期，并且當網絡節點密度越大時，效果越明顯。

5 結束語

本文提出了一種適用于無線傳感器網絡的自適應功率控制策略APCS，該策略通過調整路徑損耗指數和功率控制參數來對網絡的拓撲結構進行控制，使網絡拓撲更好地適應網絡的工作環境并滿足不同的應用需求。另外，APCS算法通過對局部節點進行動態功率調整，保證網絡的連通性，延長網絡的生命周期。本文證明了該算法的相關拓撲性質，并通過對仿真實驗數據的分析得出：(1)APCS算法路徑衰減指數為6，功率控制參數為1時可以獲得與RNG算法近似的目標拓撲，該拓撲中節點具有極小的發射半徑，網絡特別稀疏，減少了網絡中的信號沖突，增大了網絡容量；(2)APCS算法可以調整路徑衰減指數和功率控制參數來滿足對數據實時性和網絡容錯能力要求較高的應用場景。(3)APCS算法在和RNG、GG算法具有相同的目標拓撲情況下，由于采用了動態功率調整策略，大大延長了網絡的生命周期，增強了網絡的魯棒性。

[1] Anastasi G, Conti M, Francesco M D, and Passarella A.Energy conservation in wireless sensor networks: A survey. Ad hoc Networks, 2009, 7(3): 537-568.

[2] Ghosh A and Das S K. Coverage and connectivity issues in wireless sensor networks: A survey. Pervasive and Mobile Computing, 2008, 4(3): 303-334.

[3] Younis M and Akkaya K. Strategies and techniques for node placement in wireless sensor networks: A survey. Ad hoc Networks, 2008, 6(4): 621-655.

[4] Narayanaswamy S, Kawadia V, Sreenivas R S, and Kumar P R. Power control in ad-hoc networks: Theory, architecture,algorithm and implementation of the COMPOW protocol.Proc. of the European Wireless Conf. Florence, 2002:156-162.

[5] Li N and Hou J C. Topology control in heterogeneous wireless networks: Problems and solutions. Proc. of the IEEE Conf.on Computer Communications (INFOCOM). New York:IEEE Press, 2004: 232-243.

[6] Kubisch M, Karl H, Wolisz A, Zhong L C, and Rabaey J.Distributed algorithms for transmission power control in wireless sensor networks. Proc. of the IEEE Wireless Communications and Networking Conf. (WCNC). New York:IEEE Press, 2003: 16-20.

[7] Wattenhofer R and Zollinger A. XTC: A practical topology control algorithm for ad-hoc networks. Proc. of the Int’l Parallel and Distributed Processing Symp (IPDPS), New Mexico: IEEE Press, 2004: 216-223.

[8] Gabriel K R and Sokal R R. A new statistical approach to geographic variation analysis. Systematic Zoology, 1969，18(3): 259-278.

[9] Santi, P. Topology Control in Wireless Ad hoc and Sensor Networks. Chichester, UK, John Wiley & Sons, Ltd, 2005:15-16.