唐偉，郭偉

(電子科技大學(xué) 通信抗干擾技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室, 四川 成都 611731）

1 引言

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)（WSN, wireless sensor networks）通常由一組固定的傳感器節(jié)點(diǎn)和一組基站構(gòu)成[1]。傳感器節(jié)點(diǎn)負(fù)責(zé)收集區(qū)域內(nèi)的信息，并將這些信息封裝為數(shù)據(jù)報(bào)文，通過(guò)多跳的方式傳遞至基站。常見(jiàn)的應(yīng)用包括分布式壓縮[2,3]、目標(biāo)跟蹤[4,5]以及環(huán)境監(jiān)測(cè)[6,7]等。無(wú)線(xiàn)傳感器節(jié)點(diǎn)往往只配有不可再生的電池，能量極為有限，因此需要設(shè)計(jì)節(jié)能路由算法以最大化網(wǎng)絡(luò)生命期。而路由算法設(shè)計(jì)主要需要考慮以下幾個(gè)方面。首先，鄰近節(jié)點(diǎn)所收集的數(shù)據(jù)之間往往具有很強(qiáng)的相關(guān)性，通常采用數(shù)據(jù)聚合來(lái)消除數(shù)據(jù)中的冗余信息[8,9]。其次，網(wǎng)絡(luò)中可能存在多個(gè)基站，相比單一基站的情形更加復(fù)雜，基站間的數(shù)據(jù)流量的合理分配以及節(jié)點(diǎn)數(shù)據(jù)的路由路徑等都需要在算法設(shè)計(jì)中解決[10]。

由于數(shù)據(jù)聚合會(huì)改變網(wǎng)絡(luò)中的數(shù)據(jù)流量，因而路由協(xié)議的設(shè)計(jì)上必須要考慮數(shù)據(jù)流量的變化?，F(xiàn)有的數(shù)據(jù)聚合模型包括分布式壓縮模型[11]、局部Slepian-Wolf編碼模型[12]以及隨機(jī)場(chǎng)模型[13]等。例如，文獻(xiàn)[14]對(duì)分布式壓縮模型下的節(jié)能路由進(jìn)行了研究，證明了在此情況下網(wǎng)絡(luò)總體能耗的最優(yōu)化問(wèn)題中，壓縮算法與網(wǎng)絡(luò)的路由結(jié)構(gòu)可以分別獨(dú)立考慮。由于分布式壓縮模型中需要獲得全網(wǎng)的數(shù)據(jù)相關(guān)信息，難以實(shí)現(xiàn)。因此，文獻(xiàn)[12]考慮了局部壓縮算法，即節(jié)點(diǎn)只與鄰居進(jìn)行信息交換與數(shù)據(jù)壓縮的局部Slepian-Wolf編碼，并通過(guò)線(xiàn)性規(guī)劃的方法獲得網(wǎng)絡(luò)最小能耗路由算法。文獻(xiàn)[15]考慮了馬氏隨機(jī)場(chǎng)中的最小總能耗路由，并提出了一種基于最小生成樹(shù)的啟發(fā)式路由算法。文獻(xiàn)[16]研究了高斯隨機(jī)場(chǎng)中的最優(yōu)路由問(wèn)題，對(duì)比分析了最小跳數(shù)路由、最小能耗路由以及Chernoff路由的性能。

現(xiàn)有大部分路由算法以網(wǎng)絡(luò)總體能耗為目標(biāo)函數(shù)，難以準(zhǔn)確反映網(wǎng)絡(luò)的生命期；盡管有人提出了一些最大化網(wǎng)絡(luò)中節(jié)點(diǎn)最小生命期的路由算法，然而還很少有將節(jié)點(diǎn)功率控制、數(shù)據(jù)聚合以及多基站三者相結(jié)合的路由算法。為此，本文首先分析了多基站無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中最大網(wǎng)絡(luò)生命期路由問(wèn)題的NP-hard性質(zhì)，然后提出了一種基于生成森林的啟發(fā)式算法。為了設(shè)計(jì)分布式算法，本文采用了次梯度方法。最后，本文通過(guò)大量仿真實(shí)驗(yàn)驗(yàn)證了啟發(fā)式算法的性能，并表明所提出的分布式算法能夠有效地收斂。

本文組織如下。第2節(jié)介紹系統(tǒng)模型。第3節(jié)給出最大生命期問(wèn)題，并證明其N(xiāo)P-hard性質(zhì)。第4節(jié)提出基于最小生成森林的啟發(fā)式路由算法。第5節(jié)設(shè)計(jì)網(wǎng)絡(luò)最大化生命期問(wèn)題的分布式算法。第6節(jié)是仿真實(shí)驗(yàn)及結(jié)果分析。第7節(jié)是結(jié)束語(yǔ)。

2 系統(tǒng)模型

考慮一個(gè)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)，其中節(jié)點(diǎn)之間通過(guò)雙向無(wú)線(xiàn)鏈路通信，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)與至少一個(gè)基站連通。網(wǎng)絡(luò)可以被抽象為一個(gè)無(wú)向圖G(V?,E)，其中V?表示網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)和基站的集合，E表示鏈路的集合。記網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)集合為V，基站集合為S，則記節(jié)點(diǎn)i∈V的鄰居集合為傳感器節(jié)點(diǎn)初始能量為 Ei（單位是Joule），基站沒(méi)有能耗限制。每個(gè)傳感器節(jié)點(diǎn)i∈V連續(xù)或周期性地向基站報(bào)告所收集到的數(shù)據(jù)，且數(shù)據(jù)產(chǎn)生率為 Ri。其中，只要任意一個(gè)基站收集到數(shù)據(jù)，該數(shù)據(jù)就算被成功接收。由于無(wú)線(xiàn)傳感器網(wǎng)絡(luò)具有很強(qiáng)的面向應(yīng)用性，本文假定網(wǎng)絡(luò)鏈路具有足夠帶寬傳輸數(shù)據(jù)。對(duì)于無(wú)線(xiàn)信道中的沖突、干擾等，可以通過(guò)物理層和鏈路層技術(shù)進(jìn)行抑制，目前已有大量文獻(xiàn)對(duì)此進(jìn)行研究，而本文重點(diǎn)研究該類(lèi)網(wǎng)絡(luò)中的路由問(wèn)題。

3 最大生命期路由問(wèn)題

記網(wǎng)絡(luò)中通過(guò)鏈路(i,j)∈E的網(wǎng)絡(luò)流為fij。由于采用了數(shù)據(jù)聚合，網(wǎng)絡(luò)中的數(shù)據(jù)可以被分為2類(lèi)：節(jié)點(diǎn)自身收集的原始數(shù)據(jù)以及去除了冗余信息的聚合數(shù)據(jù)。因此，網(wǎng)絡(luò)流可以被表示為

根據(jù)式(1)和式(2)，對(duì)于網(wǎng)絡(luò)中的任意傳感器節(jié)點(diǎn)i∈V，其能量消耗速率可以被表示為

由此，定義節(jié)點(diǎn)的歸一化能量消耗率 ωi（f）于是，節(jié)點(diǎn)i在對(duì)應(yīng)的網(wǎng)絡(luò)流 f下的生命期可以被表示為。定義網(wǎng)絡(luò)生命期為第一個(gè)因?yàn)槟芰亢谋M而死亡的節(jié)點(diǎn)的生命期[18]。由于該定義下網(wǎng)絡(luò)的生命期往往是其他定義下網(wǎng)絡(luò)生命期的下界，例如網(wǎng)絡(luò)分裂時(shí)的生命期、網(wǎng)絡(luò)失去功能時(shí)的生命期等等，因此在研究上具有重要意義。通過(guò)定義知于是可以得到定義網(wǎng)絡(luò)歸一化的能量消耗率為，于是有最大化Tnet（f），等價(jià)于最小化

minimize Ω

式(5)表示問(wèn)題的目標(biāo)是最小化網(wǎng)絡(luò)歸一化能量消耗率Ω，即最大化網(wǎng)絡(luò)生命期 Tnet。第1項(xiàng)約束表示離開(kāi)節(jié)點(diǎn) i的原始數(shù)據(jù)網(wǎng)絡(luò)流必須等于節(jié)點(diǎn)i自身產(chǎn)生的原始數(shù)據(jù)率。第2項(xiàng)約束表示離開(kāi)節(jié)點(diǎn) i的聚合數(shù)據(jù)網(wǎng)絡(luò)流必須等于來(lái)自其他節(jié)點(diǎn)的原始數(shù)據(jù)壓縮所得的聚合數(shù)據(jù)率與來(lái)自其他節(jié)點(diǎn)的聚合數(shù)據(jù)網(wǎng)絡(luò)流之和。第3項(xiàng)約束表示網(wǎng)絡(luò)中各節(jié)點(diǎn)的歸一化能量消耗率都不超過(guò)網(wǎng)絡(luò)的歸一化能量消耗率Ω。第四項(xiàng)約束表示所有網(wǎng)絡(luò)流的選擇數(shù)量之和為網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)的數(shù)目。第1、第2及第4項(xiàng)約束一起，表明了網(wǎng)絡(luò)中的聚合數(shù)據(jù)網(wǎng)絡(luò)流構(gòu)成一棵沒(méi)有環(huán)路的生成樹(shù)[19]，即節(jié)點(diǎn) i向且只向一個(gè)鄰居節(jié)點(diǎn)輸出聚合數(shù)據(jù)網(wǎng)絡(luò)流，聚合數(shù)據(jù)網(wǎng)絡(luò)流最終匯集到基站。下面的定理給出了問(wèn)題的NP-hard性質(zhì)。

定理 1網(wǎng)絡(luò)最大生命期路由問(wèn)題是一個(gè)NP-hard問(wèn)題。

證明考查經(jīng)典的集覆蓋問(wèn)題（set cover problem），該類(lèi)問(wèn)題已經(jīng)被證明為一類(lèi)NP-hard問(wèn)題[20]。問(wèn)題描述如下：對(duì)于集合 F及其子集的集合其中，以及一個(gè)正整數(shù)K，找到元素個(gè)數(shù)為K集合使得

首先，將集覆蓋問(wèn)題映射為一個(gè)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)。如圖1所示，網(wǎng)絡(luò)中有+ 2個(gè)傳感器節(jié)點(diǎn)，分別對(duì)應(yīng)于集合 F中的元素為其子集的集合C中的元素為，以及兩個(gè)瓶頸節(jié)點(diǎn) b1,b2；同時(shí)還有S個(gè)基站對(duì)于任意的當(dāng) ai∈cj時(shí)，網(wǎng)絡(luò)中對(duì)應(yīng)地存在一條鏈路(ai, cj)；每個(gè) cj與 b1,b2間都存在一條鏈路；且 b1,b2與每個(gè)基站間都存在一條鏈路。每個(gè)傳感器節(jié)點(diǎn)的數(shù)據(jù)產(chǎn)生率都是 1bit/s，每條鏈路的能量開(kāi)銷(xiāo)都是 1J/bit，各鏈路的數(shù)據(jù)相關(guān)性指標(biāo)都是ρ＜0.5。傳感器節(jié)點(diǎn)a1,a2,… ,aF的初始能量為1J， cj的初始能量為b1的初始能量為b2的初始能量是，基站的初始能量足夠大。顯然，網(wǎng)絡(luò)可以在多項(xiàng)式時(shí)間內(nèi)通過(guò)一個(gè)集覆蓋問(wèn)題來(lái)構(gòu)建。

圖1 集覆蓋問(wèn)題向網(wǎng)絡(luò)最大生命期問(wèn)題的轉(zhuǎn)化

然后，考慮使得網(wǎng)絡(luò)生命期最大的網(wǎng)絡(luò)流。對(duì)應(yīng)于集覆蓋問(wèn)題的一個(gè)最優(yōu)解令其中各元素所對(duì)應(yīng)的節(jié)點(diǎn)將其原始數(shù)據(jù)和聚合數(shù)據(jù)都傳遞至 b1，而余下的C中元素所對(duì)應(yīng)的節(jié)點(diǎn)將其原始數(shù)據(jù)和聚合數(shù)據(jù)都傳遞至 b2。于是，瓶頸節(jié)點(diǎn) b1需要傳遞來(lái)自和）的聚合數(shù)據(jù)及其自身的原始數(shù)據(jù)，故其能量消耗率為；而瓶頸節(jié)點(diǎn)b2需要傳遞來(lái)自節(jié)點(diǎn)的聚合數(shù)據(jù)及其自身的原始數(shù)據(jù)，故其能量消耗率為。因而網(wǎng)絡(luò)恰好能夠存活1s。同時(shí)，這也是網(wǎng)絡(luò)的最大生命期。因?yàn)槠款i節(jié)點(diǎn) b1和 b2總共需要傳遞(bit/s)的數(shù)據(jù)流量，而總能量恰好為生命期不超過(guò)1s。由此，求解該類(lèi)問(wèn)題的NP-hard性質(zhì)得證。

根據(jù)定理 1，該類(lèi)網(wǎng)絡(luò)中的最大生命期問(wèn)題是難以直接進(jìn)行求解的。為此，在下面2節(jié)中，本文提出一種啟發(fā)式路由算法來(lái)獲取問(wèn)題的近似解。

4 基于最小生成森林的路由算法

為了在多基站無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中實(shí)現(xiàn)最小生成森林，本文采用了偽樹(shù)根（pseudo root）方法[21]。如圖2所示，其中圓點(diǎn)表示傳感器節(jié)點(diǎn)，五角形表示基站，而中央的多刺形表示偽樹(shù)根。偽樹(shù)根與各基站通過(guò)偽鏈路（pseudo link）相連，且偽鏈路開(kāi)銷(xiāo)為 0。認(rèn)為數(shù)據(jù)全部匯集到偽樹(shù)根，而每條實(shí)際鏈路上的開(kāi)銷(xiāo)為鏈路兩端節(jié)點(diǎn)傳輸單位比特?cái)?shù)據(jù)所需的總功率，即

圖2 多基站無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中的最小生成森林

對(duì)網(wǎng)絡(luò)中的每個(gè)傳感器節(jié)點(diǎn)iV∈，記該節(jié)點(diǎn)在生成樹(shù)中的父節(jié)點(diǎn)為pi，節(jié)點(diǎn)i的全部聚合數(shù)據(jù)都轉(zhuǎn)發(fā)給pi。于是，網(wǎng)絡(luò)流y與網(wǎng)絡(luò)流x存在如下關(guān)系

注意式(7)中，對(duì)于生成樹(shù)中的葉節(jié)點(diǎn)（不是任何節(jié)點(diǎn)父節(jié)點(diǎn)的節(jié)點(diǎn)）l，有 y是，通過(guò)遞推，網(wǎng)絡(luò)流y可以被網(wǎng)絡(luò)流x唯一確定，因而節(jié)點(diǎn)的能耗也可以用x表示。注意到x與y呈線(xiàn)性關(guān)系，即對(duì)于每條網(wǎng)絡(luò)流 yij都存在一組系數(shù)ζ（ij）使得。因而，有

于是，基于生成樹(shù)的多基站最大生命期路由問(wèn)題可以被表示為如下線(xiàn)性規(guī)劃問(wèn)題

由于無(wú)線(xiàn)傳感器網(wǎng)絡(luò)是一類(lèi)分布式網(wǎng)絡(luò)，通常要求路由算法具有分布式性質(zhì)。為此，本文采用投影次梯度方法[22]來(lái)解決。

5 網(wǎng)絡(luò)最大化生命期問(wèn)題的分布式算法

5.1 投影次梯度方法

對(duì)于n維向量 x ∈ ?n，考慮如下最優(yōu)化問(wèn)題minimize subject to

其中，f是嚴(yán)格凸函數(shù)，ig是凸函數(shù)，jh是仿射函數(shù)，而Z是n?中的有界凸多面體。目標(biāo)函數(shù)對(duì)應(yīng)的拉格朗日函數(shù)為

對(duì)于n?+∈λ，定義

x?（λ, μ ） 是唯一的。 d （λ, μ ）在（λ*, μ*） 處的一組次梯度可以表示為。于

投影次梯度方法是一種迭代方法，且將迭代得到的拉格朗日乘數(shù)投影到定義域[23]。設(shè)初始的拉格朗日乘數(shù)為（λ(1), μ(1)）。在第 k ≥ 1步中，對(duì)拉格朗日乘數(shù)做如下更新

其中，()kα 是迭代步長(zhǎng)。滿(mǎn)足下列條件時(shí)

迭代算法收斂于 d （λ, μ ）的最大值。若強(qiáng)對(duì)偶性質(zhì)成立，則序列收斂于原始問(wèn)題的最優(yōu)解[24]。

5.2 分布式算法

為了應(yīng)用次梯度方法，需要將問(wèn)題(9)中的目標(biāo)函數(shù)轉(zhuǎn)化為一個(gè)嚴(yán)格凸函數(shù)。為此，可以用目標(biāo)函數(shù)Ω2替換原來(lái)的目標(biāo)函數(shù)Ω，并引入二次協(xié)調(diào)項(xiàng)其中β是一個(gè)足夠小的正實(shí)數(shù)。于是，得到如下最優(yōu)化問(wèn)題

minimize subject to

式(17)的拉格朗日函數(shù)為

其中，()kijξ是式(8)中ijx的系數(shù)。于是得到如下序列

對(duì)偶函數(shù) d （λ, μ ）在（λ(k), μ(k)）處的次梯度為

從上述可以得出問(wèn)題的分布式算法。首先，通過(guò)分布式 Bellman-Ford[20]算法獲得網(wǎng)絡(luò)的最小生成森林，算法復(fù)雜度為 O (d|E | )，其中d是網(wǎng)絡(luò)的直徑。然后，由葉節(jié)點(diǎn)開(kāi)始，根據(jù)式(7)遞推得到聚合數(shù)據(jù)流與原始數(shù)據(jù)流之間的相關(guān)系數(shù) ζ（ij），于是得到式(8)中對(duì)應(yīng)于 wk(x)中 xij的系數(shù)。此步驟的復(fù)雜度為然后根據(jù)式(20)和式(21)計(jì)算對(duì)偶問(wèn)題的次梯度，并更新拉格朗日乘數(shù)。其中，式(20)的復(fù)雜度為式(21)的復(fù)雜度為重復(fù)迭代步驟，直到對(duì)偶問(wèn)題的目標(biāo)函數(shù)下降的相對(duì)幅度低于一個(gè)足夠小的門(mén)限。算法中只涉及到初等代數(shù)運(yùn)算，實(shí)現(xiàn)復(fù)雜度較低。

6 仿真實(shí)驗(yàn)

6.1 仿真場(chǎng)景

仿真采用MATLAB數(shù)學(xué)工具實(shí)現(xiàn)。50～120個(gè)節(jié)點(diǎn)與1～5個(gè)基站隨機(jī)分布在100m×100m范圍的矩形區(qū)域中。節(jié)點(diǎn)初始能量為 1kJ，數(shù)據(jù)產(chǎn)生率都是 1kbit/s，發(fā)射機(jī)功率增益路徑損耗系數(shù)η=2，電路驅(qū)動(dòng)功耗數(shù)據(jù)相關(guān)系數(shù)α的取值范圍為 0 .001～0.01 /m2。分布式算法中，懲罰系數(shù)β=0.1。對(duì)每個(gè)網(wǎng)絡(luò)規(guī)模，產(chǎn)生 20個(gè)隨機(jī)生成的網(wǎng)絡(luò)拓?fù)洌宜窘Y(jié)果都是各個(gè)場(chǎng)景結(jié)果的平均值。

6.2 網(wǎng)絡(luò)規(guī)模的影響

圖3所示為網(wǎng)絡(luò)生命期與網(wǎng)絡(luò)規(guī)模之間的關(guān)系。其中，數(shù)據(jù)相關(guān)系數(shù) α = 0 .05 /m2。從圖3中可以看到，隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量的增加，網(wǎng)絡(luò)生命期也逐漸增加。隨著基站數(shù)量的增加，網(wǎng)絡(luò)生命期逐漸增加。同時(shí)，隨著基站數(shù)量的增多，新加入基站對(duì)網(wǎng)絡(luò)生命期的提升幅度逐漸減少。這是因?yàn)楣?jié)點(diǎn)數(shù)量的增加，引起節(jié)點(diǎn)間距的縮短，有利于發(fā)射功率的降低以及數(shù)據(jù)相關(guān)性的提升，同時(shí)路由算法能夠有效地均衡節(jié)點(diǎn)數(shù)據(jù)流量負(fù)載，這些有利因素超過(guò)了網(wǎng)絡(luò)原始數(shù)據(jù)率增加所帶來(lái)的能耗增加，因而使得網(wǎng)絡(luò)生命期增加。而在網(wǎng)絡(luò)中引入新的基站，能夠減少節(jié)點(diǎn)與基站間的距離，減輕原生成森林上的數(shù)據(jù)流量，降低節(jié)點(diǎn)負(fù)載，提高網(wǎng)絡(luò)生命期。隨著基站數(shù)量的增大，新加入的基站只能影響鄰近基站的生成樹(shù)，對(duì)網(wǎng)絡(luò)的影響逐漸變小，因而對(duì)網(wǎng)絡(luò)生命期的提升效果逐漸減弱。

圖3 網(wǎng)絡(luò)生命期與網(wǎng)絡(luò)規(guī)模的關(guān)系

網(wǎng)絡(luò)平均能耗率與網(wǎng)絡(luò)規(guī)模的關(guān)系如圖 4所示。其中，網(wǎng)絡(luò)平均能耗率。隨著網(wǎng)絡(luò)規(guī)模的增加，節(jié)點(diǎn)平均能耗率呈下降趨勢(shì)。隨著基站的增加，網(wǎng)絡(luò)平均能耗率也逐漸降低。而當(dāng)基站數(shù)量增多時(shí)，新加入基站對(duì)網(wǎng)絡(luò)平均能耗率的降低程度也減少。同樣的變化規(guī)律也能夠從圖 5所示的網(wǎng)絡(luò)聚合數(shù)據(jù)率與網(wǎng)絡(luò)規(guī)模的變化曲線(xiàn)上體現(xiàn)。

圖4 網(wǎng)絡(luò)平均能耗率與網(wǎng)絡(luò)規(guī)模的關(guān)系

圖5 網(wǎng)絡(luò)聚合數(shù)據(jù)率與網(wǎng)絡(luò)規(guī)模的關(guān)系

6.3 數(shù)據(jù)相關(guān)性的影響

圖 6是網(wǎng)絡(luò)生命期與數(shù)據(jù)相關(guān)性的關(guān)系曲線(xiàn)圖。其中，網(wǎng)絡(luò)規(guī)模為100個(gè)節(jié)點(diǎn)。不難發(fā)現(xiàn)，當(dāng)數(shù)據(jù)相關(guān)系數(shù)增加時(shí)，數(shù)據(jù)相關(guān)性逐漸降低，網(wǎng)絡(luò)中的數(shù)據(jù)流量變大，節(jié)點(diǎn)能耗增加，網(wǎng)絡(luò)生命期如圖中所示呈下降趨勢(shì)。由于節(jié)點(diǎn)被分布到以各基站為根的生成樹(shù)上，當(dāng)基站數(shù)量增加時(shí)，生成樹(shù)數(shù)目增加，單棵樹(shù)上的節(jié)點(diǎn)數(shù)量減少，所承載的數(shù)據(jù)流量減少，節(jié)點(diǎn)能耗降低，因此網(wǎng)絡(luò)生命期也增大。當(dāng)基站數(shù)量變多時(shí)，新加入的基站只能影響越來(lái)越少的已有生成樹(shù)，對(duì)網(wǎng)絡(luò)生命期的提高效果降低。這些變化規(guī)律從圖7的網(wǎng)絡(luò)平均能耗率與數(shù)據(jù)相關(guān)性的關(guān)系以及圖 8的網(wǎng)絡(luò)聚合數(shù)據(jù)率與數(shù)據(jù)相關(guān)性的關(guān)系中都有明顯的印證。

圖6 網(wǎng)絡(luò)生命期與數(shù)據(jù)相關(guān)性的關(guān)系

圖7 網(wǎng)絡(luò)平均能耗率與數(shù)據(jù)相關(guān)性的關(guān)系

圖8 網(wǎng)絡(luò)聚合數(shù)據(jù)率與數(shù)據(jù)相關(guān)性的關(guān)系

6.4 分布式算法的收斂性能

圖9 表示的是120個(gè)節(jié)點(diǎn)的一個(gè)場(chǎng)景下，分布式算法的迭代收斂曲線(xiàn)。其中，歸一化的網(wǎng)絡(luò)生命期是通過(guò)式(20)迭代所得網(wǎng)絡(luò)生命期Ω的中間過(guò)程值與式(9)的最優(yōu)解的比值。從圖中可以看到，算法在2 000次迭代內(nèi)可以收斂到最優(yōu)值的110%，在3 300次迭代內(nèi)能夠收斂到最優(yōu)值的105%。而且算法最終能夠相當(dāng)準(zhǔn)確地收斂到最優(yōu)值。表1中是不同網(wǎng)絡(luò)規(guī)模下分布式算法的收斂性的數(shù)據(jù)。

圖9 分布式算法的收斂性質(zhì)

表1 不同網(wǎng)絡(luò)規(guī)模下分布式算法的收斂性能

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

本文對(duì)多基站無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中的最大生命期路由算法進(jìn)行了研究。本文首先證明了該類(lèi)路由問(wèn)題的NP-hard性質(zhì)，然后提出了一種基于生成森林的啟發(fā)式路由算法，之后根據(jù)次梯度方法設(shè)計(jì)了分布式路由算法。本文通過(guò)大量的仿真實(shí)驗(yàn)對(duì)啟發(fā)式算法的性能進(jìn)行了分析，并表明所提分布式算法具有較好的收斂性能。

[1] AKYILDIZ I F, WEILIAN S, SANKARASUBRAMANIAM Y, et al.A survey on sensor networks[J]. IEEE Communications Magazine,2002, 40(8)∶ 102-114.

[2] YANG Y, KRISHNAMACHARI B, PRASANNA V K. Data gathering with tunable compression in sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2008, 19(2)∶ 276-287.

[3] SONG L, KALOGERAKI V, GUNOPULOS D, et al. Online information compression in sensor networks[A]. IEEE International Conference on Communications (ICC’06)[C]. Istanbul, Turkey, 2006. 3371-3376.

[4] SONGHWAI O, SCHENATO L, CHEN P, et al. Tracking and coordination of multiple agents using sensor networks∶ system design, algorithms and experiments[J]. Proceedings of the IEEE, 2007, 95(1)∶ 234-254.

[5] LIANG S, DIMITRIOS H. A Cross-layer architecture of wireless sensor networks for target tracking[J]. IEEE/ACM Transactions on Networking, 2007, 15(1)∶ 145-158.

[6] AYSAL T C, BARNER K E. Blind decentralized estimation for bandwidth constrained wireless sensor networks[J]. IEEE Transactions on Wireless Communications, 2008, 7(5)∶ 1466-1471.

[7] MAY W, AKSOY D. Relative accuracy based location estimation in wireless ad hoc sensor networks[A]. IEEE International Conference on Communications (ICC’07)[C]. Glasgow, Scotland, 2007. 3244-3250.

[8] CHONG L, KUI W, JIAN P. An energy-efficient data collection framework for wireless sensor networks by exploiting spatiotemporal correlation[J]. IEEE Transactions on Parallel and Distributed Systems,2007, 18(7)∶ 1010-1023.

[9] VURAN M C, AKYILDIZ I F. Spatial correlation-based collaborative medium access control in wireless sensor networks[J]. IEEE/ACM Transactions on Networking, 2006, 14(2)∶ 316-329.

[10] HAN B, SIMON G. Fair capacity sharing among multiple sinks in wireless sensor networks[A]. IEEE Internatonal Conference on Mobile Adhoc and Sensor Systems (MASS’07)[C]. Pisa, Italy, 2007. 1-9.

[11] CRISTESCU R, BEFERULL-LOZANO B, VETTERLI M, et al.Network correlated data gathering with explicit communication∶NP-completeness and algorithms[J]. IEEE/ACM Transactions on Networking, 2006, 14(1)∶ 41-54.

[12] YUEN K, LIANG B, LI B. A distributed framework for correlated data gathering in sensor networks[J]. IEEE Transactions on Vehicular Technology, 2008, 57(1)∶ 578-593.

[13] VURAN M C, AKAN O B. Spatio-temporal characteristics of point and field sources in wireless sensor networks[A]. IEEE International Conference on Communications (ICC’06)[C]. Istanbul, Turkey, 2006.234-239.

[14] SEUNG JUN B, GUSTAVO DE V, XUN S. Minimizing energy consumption in large-scale sensor networks through distributed data compression and hierarchical aggregation[J]. IEEE Journal on Selected Areas in Communications, 2004, 22(6)∶ 1130-1140.

[15] ANANDKUMAR A, LANG T, SWAMI A, et al. Minimum cost data aggregation with localized processing for statistical inference[A]. The 27th IEEE Conference on Computer Communications (INFOCOM’08)[C]. Phoenix, AZ, USA, 2008. 780-788.

[16] YOUNGCHUL S, SASWAT M, LANG T, et al. Cooperative routing for distributed detection in large sensor networks[J]. IEEE Journal on Selected Areas in Communications, 2007, 25(2)∶ 471-483.

[17] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications, 2002,1(4)∶ 660-670.

[18] YAN W, FAHMY S, SHROFF N B. On the construction of a maximum-lifetime data gathering tree in sensor networks∶ NP-completeness and approximation algorithm[A]. The 27th IEEE Conference on Computer Communications (INFOCOM’08)[C]. Phoenix, AZ, USA,2008. 356-360.

[19] BAVISH B. Formulations and algorithms for the capacitated minimal directed tree problem[J]. Journal of the ACM, 1983, 30∶ 118-132.

[20] CORMEN T H, LEISERSON C, RIVEST R L, et al. Introduction to Algorithms[M]. Cambridge, MA∶ MIT Press, 2001.

[21] LIN F Y S, YEAN-FU W. Multi-sink data aggregation routing and scheduling with dynamic radii in WSNs[J]. IEEE Communications Letters, 2006, 10(10)∶ 692-694.

[22] MADAN R, LALL S. Distributed algorithms for maximum lifetime routing in wireless sensor networks[J]. IEEE Transactions on Wireless Communications, 2006, 5(8)∶ 2185-2193.

[23] KIM S, AHN H. Convergence of a generalized subgradient method for nondifferentiable convex optimization[J]. Mathematical Programming,1991, 50(1-3)∶75-80.

[24] LUENBERGER D, YE Y. Linear and Nonlinear Programming[M]. 3rd edition. New York∶ Springer-Verlag, 2008.