無線傳感網優化生存時間的分布式功率控制*

陳友榮，劉半藤，程菊花，俞 立

(1.浙江樹人大學信息科技學院，杭州 310015；2.浙江工業大學信息工程學院，杭州 310032)

無線傳感網是由很多具有感知、計算和通信能力的能量有限節點組成。目前，低成本的無線傳感網已經應用于很多現有和未來設想的領域，如智能電網、環境監測，戰場監視，醫療保健和智能家居等，越來越受到學術界和產業界的關注［1］。

網絡生存時間是無線傳感網最重要的指標之一，但是研究者沒有對網絡生存時間進行統一定義。對于一個節點能量耗盡就會影響整個無線傳感網的正常應用，網絡生存時間可以定義為網絡開始運行到網絡中第1個節點能量耗盡的這一段時間［2］，也可以定義為網絡運行到網絡中第1個節點數據不能達到Sink節點時的這一段時間。對于其它一些應用，網絡生存時間可以定義為網絡開始運行到一部分節點(如半數節點)失效的這一時間段。在無線傳感網中，由于節點大多采用電池供電，其能量有限，一旦節點能量耗盡，該節點就會失效，這將影響到網絡的運行，甚至導致網絡出現分裂而縮短網絡生存時間。因此，無線傳感網的各個算法都需要從節能出發，最大限度地延長整個網絡的生存時間。

為了延長網絡的生存時間，無線傳感網的很多算法采用各種傳輸策略(如路由，功率控制和調度等)。其中節點發送功率控制機制是無線傳感網的拓撲控制研究方向之一［3］，它主要是調節網絡中每個節點的發送功率，在滿足網絡連通度的前提下，均衡節點的單跳可達鄰居數目，剔除節點間不必要的通信鏈路，形成一個數據轉發的優化網絡結構，從而達到優化生存時間的目的。

目前，優化生存時間的算法研究已取得一些成果。文獻［4－6］分別研究所有節點靜止，Sink節點移動時的無線傳感網和無線視頻傳感網的生存時間最大化問題。用分布式的線性規劃公式表示路由問題，并采用對偶分解和次梯度方法求解最優路由方案，最大限度提高網絡生存時間。但是這些算法都假設已知所有節點的發送功率或通信距離，沒有考慮功率控制問題。然而很多無線傳感網的應用具有高密集性，在相對擁擠的網絡中，眾多鄰居節點加劇了許多無線網絡的特有問題，調整節點的發送功率可以有效的提高網絡生存時間。很多學者提出很多功 率 控 制 算 法 如 VRTPC［7］，PCAP［8］，LMA and LMN［9］，CBTC［10］等.文獻［11］提出一種新的功率控制算法。該算法采用近鄰算法評估網絡的密度和計算相應的最優發送功率。每個節點根據最優發送功率發送數據。該算法雖然提高了網絡生存時間，但是它是集中式算法而且只適用于節點均勻分布的網絡。因此，綜合一些學者的觀點，結合功率控制和最大化生存時間問題提出無線傳感網優化生存時間的分布式功率控制算法(DPCOL，Distributed Power Control for Optimizing Lifetime in Wireless Sensor Networks)。該方法建立生存時間最大化網絡模型，通過分布式發送功率迭代和次梯度方法求解該模型，獲得當前拓撲結構下的網絡生存時間、節點轉發概率和發送功率的局部最優值。該算法能有效平衡節點能耗和鄰居節點數量，延長網絡生存時間。

1 網絡模型建立

在算法中，假設:

(1)Sink節點和所有普通節點是靜止的，位置固定不變，但是各節點不知道整個網絡拓撲結構信息，只通過鄰居節點間相互通信獲得鄰居節點信息；

(2)普通節點具有相同的性能(如初始能量、能耗參數、最大發送功率、最小接收功率等)，而且節點發送功率是可調；

(3)網絡統一能量模型；

(4)所有普通節點都需要感知數據，并通過直接或多跳的方式把數據發送給Sink節點；

(5)每個普通節點能量受限，但Sink節點能量不受限制。

以G(V，L)表示一個功率控制的無線傳感網，其中，V是由網絡節點所組成的非空集合，|V|是網絡中節點的數量，L是網絡中無線鏈路(也稱為邊)的集合。由于每個節點的發送功率不一，存在節點i接收到節點j的數據，但其數據發送不到節點j的情況，因此G是一個有向連通圖。如果節點i能發送數據到節點j，則稱節點j是節點i的發送鄰居節點。如果節點i能接收到節點j的數據，則稱節點j是節點i的接收鄰居節點。以鏈路L(i，j)表示節點i到節點j的鏈路。Nt(i)表示節點i所有發送鄰居節點的集合。Nr(i)表示節點i所有接收鄰居節點的集合。用網絡連接矩陣A表示節點間的關系，其中矩陣A中的元素定義為:

在數據傳輸過程中，采用Friss自由空間模型計算發送功率和通信距離的關系［12］，公式如下:

以Fij表示節點i發送給節點j的數據發送速率，以Si表示節點i感知的數據速率，F(i)表示節點i所要發送的總數據速率，則F(i)由Si以及從鄰居節點接收到的數據組成，即鏈路流量平衡等式是:

由于節點傳輸的帶寬資源有限，鏈路上的數據傳輸速度也是有限，即鏈路最大傳輸速率約束是:

其中，Rmax表示鏈路的最大傳輸速率。

假設節點i的生存時間是Ti，根據定義，網絡生存時間則為:

最大化生存時間問題的目標就是求解Pi和Fij，使網絡的生存時間最大，即:

令q=1/Tnet(Pi，Fij)，假設節點i的初始能量是Ei，式(6)可轉換成min(q)。因此，功率控制的最優網絡生存時間問題可以轉換成如下:

2 模型求解

由于約束條件(8)中存在非線性項FijPi，最優模型(7)是一個非線性問題，不能采用次梯度算法。如果發送功率已知，最優模型能通過次梯度算法求解。因此可以結合確定發送功率的遺傳算法和次梯度算法求解網絡生存時間，但是它是集中式算法，而且涉及到太多變量，計算量大且收斂速度慢。因此采用分布式發送功率迭代和次梯度算法求解。節點隨機選擇可選集合中的發送功率，并利用次梯度算法分布式求解當前發送功率下的生存時間，完成迭代后獲得網絡生存時間的局部最優方案。

2.1 已知發送功率的分布式次梯度算法

假設已經確定每個節點的發送功率，節點收集周圍鄰居節點的信息，并采用分布式次梯度算法求解生存時間最大化模型(7)得到節點生存時間和鄰居節點速率［4－6］，其主要算法如下。

根據模型(7)，假設所有節點的生存時間相同，網絡生存時間最大化問題可以轉換成每個節點生存時間qi的平方和最大化問題。此時如果節點qi值存在最小值，網絡生存時間q也存在最小值。即:

對模型中所有自變量(qi和Fij)，式(10)不是凸函數，因此需要引入所有節點數量發送速率Fij的二次正規化項，使得最優化模型是嚴格凸的，這個優化模型可以定義成:

根據上述，可得到如下模型:

采用次梯度方法求解最優模型(14)，其拉格朗日方程如式(15)

拉格朗日對偶函數G(λ，ν，μ，η)是已知自變量qi，Fij的函數L(qi，Fij，λ，ν，μ，η)最小值，即可以表示為:

針對式(14)的最優模型，可以轉換成拉格朗日對偶問題:

拉格朗日對偶問題的目標函數是凹可微函數，可以使用次梯度方法來解決。

如果在第k次迭代的步長θ(k)(k＞0)滿足非可求和遞減規律，隨著迭代的增加，式(14)的解收斂到最優解。即:

使用次梯度，第k+1的迭代時的對偶變量由以下公式更新:

2.2 DPCOL 算法實現

為了指導節點有針對性選擇其發送功率，減少選擇的復雜性，在DPCOL算法運算前需要確定節點的可選發送功率集合，只選擇該集合中的功率作為當前發送功率。集合具體建立方法如下:網絡剛開始時，每個發送節點為建立發送功率集合，依次從最低發送功率到最大發送功率遞增發送hello數據包。當鄰居節點第一次接收到該節點的數據包，則以最大發送功率反饋一個自身信息數據包(包內含有該節點ID信息，hello數據包的ID等)。發送節點接收到鄰居數據包后，獲知與該鄰居節點通信所需要的最小功率，添加到發送功率集合中。

當節點完成發送功率集合的建立后，隨機選擇集合中的發送功率，利用次梯度算法迭代計算節點迭代過程中的最優生存時間。為了保證網絡所有節點都能找到一條到Sink節點的路徑，發送功率選擇時需保證網絡的連通性。在運行次梯度算法時，節點需要鄰居節點的相關參數信息(具體包括Fji，λj，μj，ηji，νji，其中j∈Nr(i))，因此節點需不時向其鄰居節點發送包含其參數信息的最新預測數據包。鄰居節點接收預測數據包后，更新內部相關信息。

網絡中節點獲知可選發送功率集合P，初始化以下各個參數:節點初始能量Ei，節點感知速率Si，能耗常數Eelec，放大數據信號能耗因子εfs，鏈路最大傳輸速率Rmax，Friss自由空間模型中參數Gt，Gr，D，b，Pr，拉格朗日因子(λ，ν，μ，η)0等。完成初始化后，節點執行DPCOL算法計算當前拓撲結構下的網絡生存時間局部最優值，每個節點的發送功率和鏈路的轉發概率。其具體的算法實現如下:

步驟1:網絡開始時，節點建立可選發送功率集合，并初始化算法中的各個參數；

步驟2:網絡節點隨機選擇發送功率集合中的功率。為保證網絡的連通性，節點采用數據包查詢的方式，保證選擇該功率時，至少有一條到Sink節點的路徑，否則重新選擇其他的發送功率；

步驟3:確定發送功率后，運行次梯度算法，求解該發送功率下節點的最大生存時間。

步驟4:記錄局部最優方案時的節點生存時間，節點發送功率和數據轉發概率。當發送功率選擇迭代次數大于M，迭代停止，跳到步驟5，否則跳到步驟2，此時重新選擇發送功率并初始化相關的參數。

步驟5:結束該算法。此后，節點根據預先設置的協議和計算后的鄰居節點轉發概率發送數據。

其具體的節點偽代碼如下:

算法:優化網絡生存時間，得到每個節點的局部最優發送功率。

目標:解決式(10)定義的網絡模型，約束條件式(2)～式(5)，式(9)，式(11)～式(12)。

輸入:相關常數Ei，Eelec，εfs，Si，Rmax，Gt，Gr，D，b，Pr，節點可選發送集合P，(λ，ν，μ，η)0，發送功率選擇迭代次數M，次梯度迭代次數K

分析DPCOL算法的時間復雜性。如上述偽代碼所示，考慮到該算法是分布式算法，每個節點都參與網絡生存時間的運算，時間復雜度與網絡節點數量無關。其時間復雜度主要有發送功率集合建立和網絡生存時間計算兩部分組成。前者的時間復雜度由發送功率的遞增幅度Δp和節點最大發送功率有關，即Θ(Pmax/Δp)。后者的時間復雜度涉及到M次發送功率的迭代選擇和K次次梯度算法的迭代，它的時間復雜度是Θ(MK)。于是總時間復雜度是Θ(Pmax/Δp+MK)。因此DPCOL算法需要一定的迭代時間收斂，而且只有當網絡中數據通信所消耗的能量要遠遠大于最優方案計算所消耗的能量時，DPCOL算法才能較好的工作。

3 仿真實現和分析

3.1 仿真參數

僅考慮無線通信能耗，不考慮路由建立和維護時能耗、分組出錯、超時重發所消耗的能量，也不考慮數據計算等能耗。如仿真試驗參數表1所示，在仿真試驗過程中，選擇500 m×500 m網絡仿真區域，在該區域中隨機分布無線傳感節點，計算DPCOL算法下的網絡生存時間，并與固定發送功率的次梯度算法比較。

表1 仿真試驗參數

3.2 仿真結果和分析

在DPCOL算法中，首先研究分布式次梯度算法的收斂性問題。在仿真區域內隨機分布30個節點，所有節點均采用固定發送功率0.37 W/bit，運行次梯度算法獲得最優網絡生存時間。圖1是網絡生存時間和其中3個節點生存時間的比較圖。如圖1所示，在次梯度算法中無論節點生存時間初始值如何變化，隨著迭代次數的增加都能收斂到最優網絡生存時間。所有節點運行到最后，其生存時間都趨向于網絡最優生存時間。因此，分布式次梯度算法是收斂的。

圖1 網絡和節點生存時間的比較圖

圖2是200次發送功率選擇迭代時30個節點的生存時間曲線圖。如圖2所示，虛線是每一輪迭代時節點重新選擇發送功率情況下的網絡生存時間，因為節點發送功率是在可選發送功率集合中隨機選擇，所以經過次梯度計算的網絡生存時間是曲線變化。實線是前m輪迭代過程中生成的最大生存時間。雖然經過M輪迭代生成的最大網絡生存時間可能不是整個網絡的全局最大值，但是它是局部最優值，在有限的迭代計算中可以明顯降低算法的復雜度，提高網絡生存時間。

圖2 200次發送功率選擇迭代的生存時間曲線圖

圖3 網絡生存時間比較圖

圖3是針對每個給定的節點數，分別比較固定發送功率0.37 W/bit的次梯度算法和DPCOL算法的網絡生存時間。如圖3所示，選擇固定發送功率的次梯度算法時，隨著節點數量的增加，因為網絡中所有節點都在感知和發送數據，所以節點接收和發送的數據量也隨之增加。節點發送功率不變，其能耗也隨之增加，網絡生存時間減少。但是采用DPCOL算法以后，網絡的生存時間比前者明顯提高。尤其當節點數量到達70個以后，網絡中節點數量多，DPCOL算法選擇較小的發送功率，這明顯提高了整個網絡的生存時間。之后隨著節點數量的增加，網絡中節點發送數據量也明顯增加，這一定程度上提高了網絡節點的能耗，降低了網絡生存時間。總之，DPCOL算法能提高網絡生存時間。

圖4是500 m×500 m區域內DPCOL算法的20個節點轉發數據概率圖。圖中節點間鏈路的粗細代表路徑選擇概率值。如圖4所示，因為很多節點周圍有主要發送鄰居節點和1個～2個次要發送鄰居節點。多個發送鄰居節點選擇和對應轉發概率的引導，可以有效平衡網絡節點能耗，提高網絡的生存時間。

圖4 20個節點時的網絡拓撲結構圖

根據圖4的網絡拓撲結構圖，很多節點周圍有多個鄰居節點，能選擇多個路徑發送數據，從而平衡節點能耗。但也不是擁有越多鄰居節點越好。分析不同節點數量的DPCOL算法和固定發送功率0.37 W/bit次梯度算法的鄰居節點數量。令Ci表示節點i的度值(節點i所有接收鄰居節點的數量)。則它的數學期望和方差是:

網絡度值方差代表網絡各節點度值的偏離度。方差小則代表網絡節點度值偏差小，每個節點鄰居節點數量相差不大。如下圖5所示，網絡中采用DPCOL算法的度值方差基本上是固定功率的次梯度算法度值方差的1/3。很明顯，DPCOL算法選擇合適的發送功率，平衡網絡節點的鄰居節點數量，從而提高網絡的生存時間。

圖5 度值方差比較圖

4 總結

本文首先建立節點發送功率變化下的網絡最大化生存時間模型。其次，采用已知發送功率的次梯度算法求解最大化生存時間模型。接著，提出DPCOL算法的實現。節點隨機選擇可選集合內的發送功率，并通過次梯度算法分布式計算節點生存時間，即網絡生存時間。最后，仿真比較和分析DPCOL算法的收斂性，網絡生存時間，拓撲結構和度值方差。

DPCOL算法雖然定義了可選發送功率集合，一定程序上降低了發送功率選擇的復雜度。但是還需要迭代選擇發送功率和計算此發送功率下的最大化生存時間，所得結果在迭代循環過程中是最優的，但不一定是全局最優值。網絡中可能存在其它更優的發送功率方案。因此，接下來的工作是如何分布式選擇節點發送功率，從而能得到并證明所計算的網絡生存時間是全局最優值。

［1］董齊芬，俞立，陳友榮，等.移動無線傳感網中的迭代蒙特卡羅定位算法研究［J］.傳感技術學報，2010，23(12):1803－1809.

［2］朱藝華，楊晨曦，吳萬登，等.無線傳感器網絡權衡生存時間與數據分組跳數的分流路由算法［J］.傳感技術學報，2009，22(2):273－279.

［3］文凱，郭偉，黃廣杰.無線Ad hoc網絡中的隨機功率控制［J］.電子學報，2008.7，36(7):1304－1308.

［4］Madan R，Lall S.Distributed Algorithms for Maximum Lifetime Routing in Wireless Sensor Network［J］.IEEE Transactions on Wireless Communications，2006，5(8):2185－2193.

［5］Gatzianas M A，Georgiadis L G.A Distributed Algorithm for Maximum Lifetime Routing in Sensor Networks with Mobile Sink［J］.IEEE Transactions on Wireless Communications，2007，7(3):984－994.

［6］He Y F，Lee I，Guan L.Distributed Algorithms for Network Lifetime Maximization in Wireless Visual Sensor Networks［J］.IEEE Transactions on Circuits and System for Video Technology，2009，19(5):704－718.

［7］Gomez J，Campbell A T.Variable-Range Transmission Power Control in Wireless Ad Hoc Networks［J］.IEEE Transactions on Mobile Computing，2007，6(1):87－99.

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

［9］Kubisch M，Karl H，Wolisz A，et al.Distributed Algorithms for Transmission Power Control in Wireless Sensor Networks［C］//Proceedings of IEEE Wireless Communications and Networking Conference.New Orleans:IEEE，2003:132－137.

［10］Li L，Halpern J Y，Bahl P，et al.A Cone-Based Distributed Topology Control Algorithm for Wireless Multi-Hop Networks［J］.IEEE/ACM Transactions on Networking，2005，13(2005):147－159.

［11］陳友榮，俞立，董齊芬，等.基于近鄰算法的無線傳感器網絡功率控制［J］.浙江大學學報(工學版)，2010，44(7):1321－1326.

［12］WendiB H.Application-Specific ProtocolArchitectures for Wireless Networks［D］.Boston:Massachusetts Institute of Technology，2000.