無線傳感網(wǎng)優(yōu)化生存時間的分布式功率控制*

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

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

無線傳感網(wǎng)是由很多具有感知、計(jì)算和通信能力的能量有限節(jié)點(diǎn)組成。目前，低成本的無線傳感網(wǎng)已經(jīng)應(yīng)用于很多現(xiàn)有和未來設(shè)想的領(lǐng)域，如智能電網(wǎng)、環(huán)境監(jiān)測，戰(zhàn)場監(jiān)視，醫(yī)療保健和智能家居等，越來越受到學(xué)術(shù)界和產(chǎn)業(yè)界的關(guān)注［1］。

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

為了延長網(wǎng)絡(luò)的生存時間，無線傳感網(wǎng)的很多算法采用各種傳輸策略(如路由，功率控制和調(diào)度等)。其中節(jié)點(diǎn)發(fā)送功率控制機(jī)制是無線傳感網(wǎng)的拓?fù)淇刂蒲芯糠较蛑唬?］，它主要是調(diào)節(jié)網(wǎng)絡(luò)中每個節(jié)點(diǎn)的發(fā)送功率，在滿足網(wǎng)絡(luò)連通度的前提下，均衡節(jié)點(diǎn)的單跳可達(dá)鄰居數(shù)目，剔除節(jié)點(diǎn)間不必要的通信鏈路，形成一個數(shù)據(jù)轉(zhuǎn)發(fā)的優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)，從而達(dá)到優(yōu)化生存時間的目的。

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

1 網(wǎng)絡(luò)模型建立

在算法中，假設(shè):

(1)Sink節(jié)點(diǎn)和所有普通節(jié)點(diǎn)是靜止的，位置固定不變，但是各節(jié)點(diǎn)不知道整個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息，只通過鄰居節(jié)點(diǎn)間相互通信獲得鄰居節(jié)點(diǎn)信息；

(2)普通節(jié)點(diǎn)具有相同的性能(如初始能量、能耗參數(shù)、最大發(fā)送功率、最小接收功率等)，而且節(jié)點(diǎn)發(fā)送功率是可調(diào)；

(3)網(wǎng)絡(luò)統(tǒng)一能量模型；

(4)所有普通節(jié)點(diǎn)都需要感知數(shù)據(jù)，并通過直接或多跳的方式把數(shù)據(jù)發(fā)送給Sink節(jié)點(diǎn)；

(5)每個普通節(jié)點(diǎn)能量受限，但Sink節(jié)點(diǎn)能量不受限制。

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

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

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

由于節(jié)點(diǎn)傳輸?shù)膸捹Y源有限，鏈路上的數(shù)據(jù)傳輸速度也是有限，即鏈路最大傳輸速率約束是:

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

假設(shè)節(jié)點(diǎn)i的生存時間是Ti，根據(jù)定義，網(wǎng)絡(luò)生存時間則為:

最大化生存時間問題的目標(biāo)就是求解Pi和Fij，使網(wǎng)絡(luò)的生存時間最大，即:

令q=1/Tnet(Pi，F(xiàn)ij)，假設(shè)節(jié)點(diǎn)i的初始能量是Ei，式(6)可轉(zhuǎn)換成min(q)。因此，功率控制的最優(yōu)網(wǎng)絡(luò)生存時間問題可以轉(zhuǎn)換成如下:

2 模型求解

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

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

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

根據(jù)模型(7)，假設(shè)所有節(jié)點(diǎn)的生存時間相同，網(wǎng)絡(luò)生存時間最大化問題可以轉(zhuǎn)換成每個節(jié)點(diǎn)生存時間qi的平方和最大化問題。此時如果節(jié)點(diǎn)qi值存在最小值，網(wǎng)絡(luò)生存時間q也存在最小值。即:

對模型中所有自變量(qi和Fij)，式(10)不是凸函數(shù)，因此需要引入所有節(jié)點(diǎn)數(shù)量發(fā)送速率Fij的二次正規(guī)化項(xiàng)，使得最優(yōu)化模型是嚴(yán)格凸的，這個優(yōu)化模型可以定義成:

根據(jù)上述，可得到如下模型:

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

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

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

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

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

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

2.2 DPCOL 算法實(shí)現(xiàn)

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

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

網(wǎng)絡(luò)中節(jié)點(diǎn)獲知可選發(fā)送功率集合P，初始化以下各個參數(shù):節(jié)點(diǎn)初始能量Ei，節(jié)點(diǎn)感知速率Si，能耗常數(shù)Eelec，放大數(shù)據(jù)信號能耗因子εfs，鏈路最大傳輸速率Rmax，F(xiàn)riss自由空間模型中參數(shù)Gt，Gr，D，b，Pr，拉格朗日因子(λ，ν，μ，η)0等。完成初始化后，節(jié)點(diǎn)執(zhí)行DPCOL算法計(jì)算當(dāng)前拓?fù)浣Y(jié)構(gòu)下的網(wǎng)絡(luò)生存時間局部最優(yōu)值，每個節(jié)點(diǎn)的發(fā)送功率和鏈路的轉(zhuǎn)發(fā)概率。其具體的算法實(shí)現(xiàn)如下:

步驟1:網(wǎng)絡(luò)開始時，節(jié)點(diǎn)建立可選發(fā)送功率集合，并初始化算法中的各個參數(shù)；

步驟2:網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)選擇發(fā)送功率集合中的功率。為保證網(wǎng)絡(luò)的連通性，節(jié)點(diǎn)采用數(shù)據(jù)包查詢的方式，保證選擇該功率時，至少有一條到Sink節(jié)點(diǎn)的路徑，否則重新選擇其他的發(fā)送功率；

步驟3:確定發(fā)送功率后，運(yùn)行次梯度算法，求解該發(fā)送功率下節(jié)點(diǎn)的最大生存時間。

步驟4:記錄局部最優(yōu)方案時的節(jié)點(diǎn)生存時間，節(jié)點(diǎn)發(fā)送功率和數(shù)據(jù)轉(zhuǎn)發(fā)概率。當(dāng)發(fā)送功率選擇迭代次數(shù)大于M，迭代停止，跳到步驟5，否則跳到步驟2，此時重新選擇發(fā)送功率并初始化相關(guān)的參數(shù)。

步驟5:結(jié)束該算法。此后，節(jié)點(diǎn)根據(jù)預(yù)先設(shè)置的協(xié)議和計(jì)算后的鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)概率發(fā)送數(shù)據(jù)。

其具體的節(jié)點(diǎn)偽代碼如下:

算法:優(yōu)化網(wǎng)絡(luò)生存時間，得到每個節(jié)點(diǎn)的局部最優(yōu)發(fā)送功率。

目標(biāo):解決式(10)定義的網(wǎng)絡(luò)模型，約束條件式(2)～式(5)，式(9)，式(11)～式(12)。

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

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

3 仿真實(shí)現(xiàn)和分析

3.1 仿真參數(shù)

僅考慮無線通信能耗，不考慮路由建立和維護(hù)時能耗、分組出錯、超時重發(fā)所消耗的能量，也不考慮數(shù)據(jù)計(jì)算等能耗。如仿真試驗(yàn)參數(shù)表1所示，在仿真試驗(yàn)過程中，選擇500 m×500 m網(wǎng)絡(luò)仿真區(qū)域，在該區(qū)域中隨機(jī)分布無線傳感節(jié)點(diǎn)，計(jì)算DPCOL算法下的網(wǎng)絡(luò)生存時間，并與固定發(fā)送功率的次梯度算法比較。

表1 仿真試驗(yàn)參數(shù)

3.2 仿真結(jié)果和分析

在DPCOL算法中，首先研究分布式次梯度算法的收斂性問題。在仿真區(qū)域內(nèi)隨機(jī)分布30個節(jié)點(diǎn)，所有節(jié)點(diǎn)均采用固定發(fā)送功率0.37 W/bit，運(yùn)行次梯度算法獲得最優(yōu)網(wǎng)絡(luò)生存時間。圖1是網(wǎng)絡(luò)生存時間和其中3個節(jié)點(diǎn)生存時間的比較圖。如圖1所示，在次梯度算法中無論節(jié)點(diǎn)生存時間初始值如何變化，隨著迭代次數(shù)的增加都能收斂到最優(yōu)網(wǎng)絡(luò)生存時間。所有節(jié)點(diǎn)運(yùn)行到最后，其生存時間都趨向于網(wǎng)絡(luò)最優(yōu)生存時間。因此，分布式次梯度算法是收斂的。

圖1 網(wǎng)絡(luò)和節(jié)點(diǎn)生存時間的比較圖

圖2是200次發(fā)送功率選擇迭代時30個節(jié)點(diǎn)的生存時間曲線圖。如圖2所示，虛線是每一輪迭代時節(jié)點(diǎn)重新選擇發(fā)送功率情況下的網(wǎng)絡(luò)生存時間，因?yàn)楣?jié)點(diǎn)發(fā)送功率是在可選發(fā)送功率集合中隨機(jī)選擇，所以經(jīng)過次梯度計(jì)算的網(wǎng)絡(luò)生存時間是曲線變化。實(shí)線是前m輪迭代過程中生成的最大生存時間。雖然經(jīng)過M輪迭代生成的最大網(wǎng)絡(luò)生存時間可能不是整個網(wǎng)絡(luò)的全局最大值，但是它是局部最優(yōu)值，在有限的迭代計(jì)算中可以明顯降低算法的復(fù)雜度，提高網(wǎng)絡(luò)生存時間。

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

圖3 網(wǎng)絡(luò)生存時間比較圖

圖3是針對每個給定的節(jié)點(diǎn)數(shù)，分別比較固定發(fā)送功率0.37 W/bit的次梯度算法和DPCOL算法的網(wǎng)絡(luò)生存時間。如圖3所示，選擇固定發(fā)送功率的次梯度算法時，隨著節(jié)點(diǎn)數(shù)量的增加，因?yàn)榫W(wǎng)絡(luò)中所有節(jié)點(diǎn)都在感知和發(fā)送數(shù)據(jù)，所以節(jié)點(diǎn)接收和發(fā)送的數(shù)據(jù)量也隨之增加。節(jié)點(diǎn)發(fā)送功率不變，其能耗也隨之增加，網(wǎng)絡(luò)生存時間減少。但是采用DPCOL算法以后，網(wǎng)絡(luò)的生存時間比前者明顯提高。尤其當(dāng)節(jié)點(diǎn)數(shù)量到達(dá)70個以后，網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量多，DPCOL算法選擇較小的發(fā)送功率，這明顯提高了整個網(wǎng)絡(luò)的生存時間。之后隨著節(jié)點(diǎn)數(shù)量的增加，網(wǎng)絡(luò)中節(jié)點(diǎn)發(fā)送數(shù)據(jù)量也明顯增加，這一定程度上提高了網(wǎng)絡(luò)節(jié)點(diǎn)的能耗，降低了網(wǎng)絡(luò)生存時間?？傊?，DPCOL算法能提高網(wǎng)絡(luò)生存時間。

圖4是500 m×500 m區(qū)域內(nèi)DPCOL算法的20個節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)概率圖。圖中節(jié)點(diǎn)間鏈路的粗細(xì)代表路徑選擇概率值。如圖4所示，因?yàn)楹芏喙?jié)點(diǎn)周圍有主要發(fā)送鄰居節(jié)點(diǎn)和1個～2個次要發(fā)送鄰居節(jié)點(diǎn)。多個發(fā)送鄰居節(jié)點(diǎn)選擇和對應(yīng)轉(zhuǎn)發(fā)概率的引導(dǎo)，可以有效平衡網(wǎng)絡(luò)節(jié)點(diǎn)能耗，提高網(wǎng)絡(luò)的生存時間。

圖4 20個節(jié)點(diǎn)時的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

根據(jù)圖4的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，很多節(jié)點(diǎn)周圍有多個鄰居節(jié)點(diǎn)，能選擇多個路徑發(fā)送數(shù)據(jù)，從而平衡節(jié)點(diǎn)能耗。但也不是擁有越多鄰居節(jié)點(diǎn)越好。分析不同節(jié)點(diǎn)數(shù)量的DPCOL算法和固定發(fā)送功率0.37 W/bit次梯度算法的鄰居節(jié)點(diǎn)數(shù)量。令Ci表示節(jié)點(diǎn)i的度值(節(jié)點(diǎn)i所有接收鄰居節(jié)點(diǎn)的數(shù)量)。則它的數(shù)學(xué)期望和方差是:

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

圖5 度值方差比較圖

4 總結(jié)

本文首先建立節(jié)點(diǎn)發(fā)送功率變化下的網(wǎng)絡(luò)最大化生存時間模型。其次，采用已知發(fā)送功率的次梯度算法求解最大化生存時間模型。接著，提出DPCOL算法的實(shí)現(xiàn)。節(jié)點(diǎn)隨機(jī)選擇可選集合內(nèi)的發(fā)送功率，并通過次梯度算法分布式計(jì)算節(jié)點(diǎn)生存時間，即網(wǎng)絡(luò)生存時間。最后，仿真比較和分析DPCOL算法的收斂性，網(wǎng)絡(luò)生存時間，拓?fù)浣Y(jié)構(gòu)和度值方差。

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

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

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

［3］文凱，郭偉，黃廣杰.無線Ad hoc網(wǎng)絡(luò)中的隨機(jī)功率控制［J］.電子學(xué)報，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網(wǎng)絡(luò)中基于節(jié)點(diǎn)位置的功率控制算法［J］.電子與信息學(xué)報，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］陳友榮，俞立，董齊芬，等.基于近鄰算法的無線傳感器網(wǎng)絡(luò)功率控制［J］.浙江大學(xué)學(xué)報(工學(xué)版)，2010，44(7):1321－1326.

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