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

沈俊鑫， 南金秀， 張經(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é)點(relay nodes,RNs)，進(jìn)而彌補(bǔ)能量消耗殆盡的節(jié)點在WSNs空缺，提高網(wǎng)絡(luò)覆蓋率,目的是確保網(wǎng)絡(luò)連通率，并使RNs數(shù)目最小，降低成本。本文考慮了周期性數(shù)據(jù)流，即每個節(jié)點周期向基站傳輸數(shù)據(jù)流。同時，節(jié)點具有綠色能量采集能力。由于節(jié)點自身硬件、位置的不同，其能量采集率不同。

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

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

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

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

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

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

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

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

(1)

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

1.3 能量模型

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

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

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

Ehi=ηhiPt(di)-βξiT

(2)

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

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

2 MST-DRN算法

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

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

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

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

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

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

2.2 最小Spanning樹

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

圖4 基于Kruskal的MST

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

圖5 最小spanning樹

2.3 基于MST的Ns-LEC搜索法

依據(jù)MST，并搜索Ns-LEC節(jié)點。搜索過程的偽代碼如下。其中R表示Ns-LEC節(jié)點集。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

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

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

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

3 性能仿真

3.1 仿真參數(shù)

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

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

3.2 性能分析

節(jié)點數(shù)對成本的影響,實驗數(shù)據(jù)如圖6所示。

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

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

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

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

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

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

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

4 結(jié) 論

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