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

沈俊鑫， 南金秀， 張經陽

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

0 引 言

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

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

1 網絡模型及約束條件

1.1 網絡模型

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

此外，考慮周期流量，即每個節點周期向基站發送感測數據。假定每個節點的感測數據的格式是預知的。同時，假定賦予節點不同能量采集容量。同時，保證最小容量值也足夠大，能夠維持一個節點運行感測任務和處理自身流量的能量。同時，假定傳感節點已部署于感測區域，網絡拓撲圖，并作為模型的輸入。在感測區域內部署RNs節點最終提高Ns-LEC能夠轉發數據流。為此，將RNs放置于Ns-LEC的臨近區域，輔助轉發數據包。

1.2 數據流量模型

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

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

(1)

節點i將傳輸的數據流為Tri=λ(γi+1)。

1.3 能量模型

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

此外，基站采用不同于數據傳輸帶寬的帶寬傳輸能量。如果能量傳輸和數據傳輸的帶寬相同，可能會產生干擾。

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

Ehi=ηhiPt(di)-βξiT

(2)

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

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

2 MST-DRN算法

MST-DRN算法依據邊權值構建Spanning樹后。計算樹的非葉節點是否滿足節點生存條件:如果不滿足，在其附近部署RNs節點。即通過最小Spanning樹尋找Ns-LEC，實現既保證網絡連通，又使Ns-LEC的數目最小化。整個流程如圖1所示。

圖1 MST-DRN模型的執行流程

2.1 節點權值和邊權值

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

圖2 具有節點權值的網絡拓撲圖

圖3 MST-DRN模型的執行流程

2.2 最小Spanning樹

在構成了基于邊權值的網絡拓撲圖后，再引用基于Kruskal的多項時間算法，就形成MST。節點總是選擇具有最小權值的邊傳輸數據。生成MST的框圖如圖4所示。以通信圖(V,E)、基站和矢量h(能量采集容量)為輸入。輸出則為以基站為根的MST,即(V,ε,B)。其中ε表示MST中的節點集。

圖4 基于Kruskal的MST

仍以圖3為例，節點5參與3條邊，其中與節點2所構成的邊的權值最小，因此，節點5就向節點2傳輸數據。最終，形成的數據傳輸有向圖，即最小spaning樹，如圖5。

圖5 最小spanning樹

2.3 基于MST的Ns-LEC搜索法

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

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

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

依據R部署RNS節點，并由RNS負責轉發數據包，從而延緩Ns-LEC節點的能量下降，進而保證網絡連通，提高WSNs的應用性能。

3 性能仿真

3.1 仿真參數

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

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

3.2 性能分析

節點數對成本的影響,實驗數據如圖6所示。

圖6 成本隨節點數的變化曲線

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

圖7為成本隨網絡密度的變化情況。其中網絡密度是指每個頂點的平均邊數。

圖7 成本隨網絡密度的變化曲線

可知，成本隨網絡密度的增加而下降，原因在于：網絡密度越大，節點擁有的數據傳輸支路越多，低能量的節點越少，相應的成本越低。在整個網絡密度變化區間，MST-DRN的成本均低于MBA。與圖6類似，仍與LBILP的成本存在差異。

數據包傳遞的性能，如圖8所示可知，通過建立最小MST樹，構成數據傳輸的最佳路徑，有效地降低了數據包傳輸時延。此外，通過部署RNs，提高網絡連通率，也有利于數據傳輸效率。

圖8 數據包傳遞率隨節點數的變化情況

4 結 論

實驗數據表明，提出的MST-DRN算法能以最小成本維持網絡連通率，并提高了數據包傳輸成功率。