趙學(xué)健 莊 毅 趙 潔 薛佟佟

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

1 引言

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

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

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

2 模型與假設(shè)

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

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

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

3 APCS算法

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

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

定義2 原始拓撲(GS)：所有節(jié)點均使用最大發(fā)射功率Rmax時得到的網(wǎng)絡(luò)拓撲。

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

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

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

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

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

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

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

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

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

(3)拓撲性質(zhì)分析

定理1 連通性：GAPCS連通當且僅當原始拓撲結(jié)構(gòu)圖GS為連通圖。

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

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

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

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

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

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

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

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

證明 采用反證法進行證明，假設(shè)存在邊(u, v)在GAPCS?λ2中但是不在GAPCS?λ1中。根據(jù)APCS算法可知，必然存在節(jié)點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)。

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

4 實驗分析

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

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

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

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

圖1 拓撲結(jié)構(gòu)圖

圖2 平均發(fā)射半徑分析圖

圖3 平均最小跳數(shù)分析圖

圖4 節(jié)點平均度分析圖

圖5 網(wǎng)絡(luò)生命周期分析圖

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

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

5 結(jié)束語

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

[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.