基于最小Spanning樹的中繼節(jié)點(diǎn)部署算法*

沈俊鑫， 南金秀， 張經(jīng)陽

(1.昆明理工大學(xué) 管理與經(jīng)濟(jì)學(xué)院，云南 昆明 650093; 2.欽州學(xué)院 經(jīng)濟(jì)管理學(xué)院，廣西 欽州 535001)

0 引 言

隨著環(huán)保概念日益深入，綠色通信已受到廣泛關(guān)注。從環(huán)境資源采集能量成為解決無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)[1,2]的能量受限問題的有效方案，如電磁波、太陽能、風(fēng)能等[3,4]。因此，在WSNs中補(bǔ)充具有能量采集的中繼節(jié)點(diǎn)(relay nodes,RNs)，進(jìn)而彌補(bǔ)能量消耗殆盡的節(jié)點(diǎn)在WSNs空缺，提高網(wǎng)絡(luò)覆蓋率,目的是確保網(wǎng)絡(luò)連通率，并使RNs數(shù)目最小，降低成本。本文考慮了周期性數(shù)據(jù)流，即每個(gè)節(jié)點(diǎn)周期向基站傳輸數(shù)據(jù)流。同時(shí)，節(jié)點(diǎn)具有綠色能量采集能力。由于節(jié)點(diǎn)自身硬件、位置的不同，其能量采集率不同。

本文針對(duì)能量采集率不同的節(jié)點(diǎn)，提出了基于最小Spanning樹的中繼節(jié)點(diǎn)部署算法(minimum spanning tree-based deploying relay nodes,MST-DRN)算法，其目的在于以最少的RNs數(shù)，滿足網(wǎng)絡(luò)連通率，并保證數(shù)據(jù)傳輸成功率。MST-DRN算法基于節(jié)點(diǎn)的能量采集容量，計(jì)算每個(gè)節(jié)點(diǎn)的權(quán)值，再計(jì)算邊權(quán)值，然后依據(jù)邊權(quán)值，并利用Kruskal算法構(gòu)成最小Spanning樹(minimum spanning tree,MST)。最后，檢測MST的非葉節(jié)點(diǎn)的能量是否滿足數(shù)據(jù)流的傳輸要求:若不滿足，則成為低能量節(jié)點(diǎn)(nodes with low energy capacity,Ns-LEC)。Ns-LEC需要RNs的協(xié)助，從而保證網(wǎng)絡(luò)連通。實(shí)驗(yàn)數(shù)據(jù)表明:提出的MST-DRN算法能夠以最小的RNs節(jié)點(diǎn)維持網(wǎng)絡(luò)連通，降低了成本，也提高了數(shù)據(jù)包的傳輸成功率。

1 網(wǎng)絡(luò)模型及約束條件

1.1 網(wǎng)絡(luò)模型

考慮無向圖G=(V,E),V表示頂點(diǎn)集,E表示邊。假定鏈路雙向，如果兩節(jié)點(diǎn)在彼此通信范圍內(nèi)，則這兩個(gè)節(jié)點(diǎn)存在一條邊。因此，假定圖G=(V,E)連通[5]。

此外，考慮周期流量，即每個(gè)節(jié)點(diǎn)周期向基站發(fā)送感測數(shù)據(jù)。假定每個(gè)節(jié)點(diǎn)的感測數(shù)據(jù)的格式是預(yù)知的。同時(shí)，假定賦予節(jié)點(diǎn)不同能量采集容量。同時(shí)，保證最小容量值也足夠大，能夠維持一個(gè)節(jié)點(diǎn)運(yùn)行感測任務(wù)和處理自身流量的能量。同時(shí)，假定傳感節(jié)點(diǎn)已部署于感測區(qū)域，網(wǎng)絡(luò)拓?fù)鋱D，并作為模型的輸入。在感測區(qū)域內(nèi)部署RNs節(jié)點(diǎn)最終提高Ns-LEC能夠轉(zhuǎn)發(fā)數(shù)據(jù)流。為此，將RNs放置于Ns-LEC的臨近區(qū)域，輔助轉(zhuǎn)發(fā)數(shù)據(jù)包。

1.2 數(shù)據(jù)流量模型

每個(gè)傳感節(jié)點(diǎn)周期向基站傳輸其所感測的數(shù)據(jù)。假定γi表示節(jié)點(diǎn)i的支葉節(jié)點(diǎn)數(shù)，即節(jié)點(diǎn)i是根節(jié)點(diǎn)，而γi為子節(jié)點(diǎn)數(shù)和孫子節(jié)點(diǎn)。引用Ci表示直系子節(jié)點(diǎn)數(shù)[6,7]。

每輪抽樣時(shí)期T,節(jié)點(diǎn)產(chǎn)生λbit數(shù)據(jù)。因此，傳感節(jié)點(diǎn)(假定節(jié)點(diǎn)i)所能接收的數(shù)據(jù)流為

(1)

節(jié)點(diǎn)i將傳輸?shù)臄?shù)據(jù)流為Tri=λ(γi+1)。

1.3 能量模型

考慮無存儲(chǔ)的簡單能量模型，即本周期所采集的能量立即在下一個(gè)周期使用。假定hi是節(jié)點(diǎn)i的能量采集率。不同節(jié)點(diǎn)具有不同的能量采集率。設(shè)有不同的能量資源[8，9]，如太陽能、風(fēng)能。但太陽能是不可控能量，無太陽照射的區(qū)域，節(jié)點(diǎn)無法收集能量，就無法保證網(wǎng)絡(luò)連通，降低網(wǎng)絡(luò)性能。為此，引用可控能量，即考慮無線能量采集系統(tǒng)。每個(gè)節(jié)點(diǎn)通過從基站(base station,BS)的無線信號(hào)進(jìn)行充電。文獻(xiàn)[10,11]已證實(shí)了無線功率傳輸?shù)目刹僮餍浴Ｍ瑫r(shí)，BS引用Beamforming技術(shù)形成尖利能量束，并傳遞至能量采集節(jié)點(diǎn),利于能量轉(zhuǎn)換效率。

此外，基站采用不同于數(shù)據(jù)傳輸帶寬的帶寬傳輸能量。如果能量傳輸和數(shù)據(jù)傳輸?shù)膸捪嗤赡軙?huì)產(chǎn)生干擾。

假定節(jié)點(diǎn)i所采集的能量表示為Ehi，其定義為

Ehi=ηhiPt(di)-βξiT

(2)

令Ep為在每一周期內(nèi)執(zhí)行感測、計(jì)算任務(wù)時(shí)所消耗的能量，Et,Er分別為傳輸或接收1 bit所消耗的能量,節(jié)點(diǎn)i所消耗的總能量Ei=ReciEr+TriEt+Ep。

因此，節(jié)點(diǎn)生存條件就是：所消耗的能量小于所采集的能量,即hiT≥Ei,?i∈S。

2 MST-DRN算法

MST-DRN算法依據(jù)邊權(quán)值構(gòu)建Spanning樹后。計(jì)算樹的非葉節(jié)點(diǎn)是否滿足節(jié)點(diǎn)生存條件:如果不滿足，在其附近部署RNs節(jié)點(diǎn)。即通過最小Spanning樹尋找Ns-LEC，實(shí)現(xiàn)既保證網(wǎng)絡(luò)連通，又使Ns-LEC的數(shù)目最小化。整個(gè)流程如圖1所示。

圖1 MST-DRN模型的執(zhí)行流程

2.1 節(jié)點(diǎn)權(quán)值和邊權(quán)值

通過VWG便可產(chǎn)生邊權(quán)值圖(edge weighted graph,EWG)。每條邊權(quán)值等于兩頂點(diǎn)權(quán)值和,即Wu,v=wu+wv,如圖2，節(jié)點(diǎn)5的能量采集容量h5=20,經(jīng)計(jì)算可知，hmax=30,節(jié)點(diǎn)5的樹值w5=0.33。由圖3計(jì)算知，節(jié)點(diǎn)5，9的邊權(quán)值為0.49(即0.33+0.16)。

圖2 具有節(jié)點(diǎn)權(quán)值的網(wǎng)絡(luò)拓?fù)鋱D

圖3 MST-DRN模型的執(zhí)行流程

2.2 最小Spanning樹

在構(gòu)成了基于邊權(quán)值的網(wǎng)絡(luò)拓?fù)鋱D后，再引用基于Kruskal的多項(xiàng)時(shí)間算法，就形成MST。節(jié)點(diǎn)總是選擇具有最小權(quán)值的邊傳輸數(shù)據(jù)。生成MST的框圖如圖4所示。以通信圖(V,E)、基站和矢量h(能量采集容量)為輸入。輸出則為以基站為根的MST,即(V,ε,B)。其中ε表示MST中的節(jié)點(diǎn)集。

圖4 基于Kruskal的MST

仍以圖3為例，節(jié)點(diǎn)5參與3條邊，其中與節(jié)點(diǎn)2所構(gòu)成的邊的權(quán)值最小，因此，節(jié)點(diǎn)5就向節(jié)點(diǎn)2傳輸數(shù)據(jù)。最終，形成的數(shù)據(jù)傳輸有向圖，即最小spaning樹，如圖5。

圖5 最小spanning樹

2.3 基于MST的Ns-LEC搜索法

依據(jù)MST，并搜索Ns-LEC節(jié)點(diǎn)。搜索過程的偽代碼如下。其中R表示Ns-LEC節(jié)點(diǎn)集。R初始為空集。

1)輸入：(V,E,B,h),MST

輸出：R:The set of nodes for which to add the RNs

2)R←?

3)Calculate the vertices weights

4)?i∈V,calculatewi

5)(V,ε,B)=MST(E,V,W′)

6)?i∈V,calculateξiin the resulted tree(V,ε,B)

7)ifξi≠0 then

8)calculateEi=0

9)if the constrained represented is not satisfied forithen

10)R=R∪{i}

11)end if

12)end if

可知，首先計(jì)算每個(gè)節(jié)點(diǎn)的權(quán)值wi。再計(jì)算每條邊的權(quán)值Wu,v，并構(gòu)成邊權(quán)值矩陣W。再利用Kruskal構(gòu)成MST樹，如步驟(5)所示。

再依據(jù)MST樹，計(jì)算每個(gè)節(jié)點(diǎn)(假定節(jié)點(diǎn)i)的支葉節(jié)點(diǎn)數(shù)(γi)。如果節(jié)點(diǎn)i不是支葉節(jié)點(diǎn)，即γi≠0，就利用節(jié)點(diǎn)生存條件判斷節(jié)點(diǎn)是否為Ns-LEC節(jié)點(diǎn);如果是，則將其加入R，即R=R∪i。其中|R|表示需要部署RNs的節(jié)點(diǎn)數(shù)，|R|越少，成本越低。

依據(jù)R部署RNS節(jié)點(diǎn)，并由RNS負(fù)責(zé)轉(zhuǎn)發(fā)數(shù)據(jù)包，從而延緩Ns-LEC節(jié)點(diǎn)的能量下降，進(jìn)而保證網(wǎng)絡(luò)連通，提高WSNs的應(yīng)用性能。

3 性能仿真

3.1 仿真參數(shù)

引用NS 3[13]網(wǎng)絡(luò)仿真器建立仿真平臺(tái)。考慮N個(gè)隨機(jī)在分布于100 m×100 m區(qū)域。每次仿真時(shí)，從N個(gè)節(jié)點(diǎn)中隨機(jī)選擇1個(gè)節(jié)點(diǎn)作為基站，其他節(jié)點(diǎn)周期產(chǎn)生數(shù)據(jù)包傳輸至基站。數(shù)據(jù)包大小32 B，節(jié)點(diǎn)初始能量為Einit=10 J。

為了更好地分析MST-DRN協(xié)議性能，引用最小中繼算法(minimum relay algorithm,MRA)[14]、基于整數(shù)線性規(guī)劃(integer linear programming,ILP)推導(dǎo)的成本下限[2]作為參照，并進(jìn)行性能比較。主要分析部署RNs的節(jié)點(diǎn)數(shù)，即成本。成本越低，性能越好。

3.2 性能分析

節(jié)點(diǎn)數(shù)對(duì)成本的影響,實(shí)驗(yàn)數(shù)據(jù)如圖6所示。

圖6 成本隨節(jié)點(diǎn)數(shù)的變化曲線

可知，成本隨節(jié)點(diǎn)數(shù)的增加而呈上升趨勢，原因在于：節(jié)點(diǎn)數(shù)越多，能量低的節(jié)點(diǎn)越多。與MRA相比，提出的MST-DRN算法的成本下降，并且隨節(jié)點(diǎn)數(shù)的增加，下降趨勢越明顯。但與LB-ILP相比，MST-DRN的成本仍具有較大的下降空間。

圖7為成本隨網(wǎng)絡(luò)密度的變化情況。其中網(wǎng)絡(luò)密度是指每個(gè)頂點(diǎn)的平均邊數(shù)。

圖7 成本隨網(wǎng)絡(luò)密度的變化曲線

可知，成本隨網(wǎng)絡(luò)密度的增加而下降，原因在于：網(wǎng)絡(luò)密度越大，節(jié)點(diǎn)擁有的數(shù)據(jù)傳輸支路越多，低能量的節(jié)點(diǎn)越少，相應(yīng)的成本越低。在整個(gè)網(wǎng)絡(luò)密度變化區(qū)間，MST-DRN的成本均低于MBA。與圖6類似，仍與LBILP的成本存在差異。

數(shù)據(jù)包傳遞的性能，如圖8所示可知，通過建立最小MST樹，構(gòu)成數(shù)據(jù)傳輸?shù)淖罴崖窂剑行У亟档土藬?shù)據(jù)包傳輸時(shí)延。此外，通過部署RNs，提高網(wǎng)絡(luò)連通率，也有利于數(shù)據(jù)傳輸效率。

圖8 數(shù)據(jù)包傳遞率隨節(jié)點(diǎn)數(shù)的變化情況

4 結(jié) 論

實(shí)驗(yàn)數(shù)據(jù)表明，提出的MST-DRN算法能以最小成本維持網(wǎng)絡(luò)連通率，并提高了數(shù)據(jù)包傳輸成功率。