基于光暈網絡模型的平衡負載的數據傳輸算法

馮小歐, 陳 婉, 袁培燕

(1.鄭州旅游職業學院 信息中心，河南 鄭州 450000；2.河南師范大學 計算機與信息工程學院，河南 新鄉 453007)

0 引 言

數據傳輸被認為是無線傳感網絡(wireless sensor networks，WSNs)最關鍵的技術之一。有效的數據傳輸算法能減少節點負載，平衡網絡開銷，進而延長網絡壽命[1]。然而，由于WSNs節點數量的巨大，設計有效數據傳輸算法成為存在挑戰。此外，傳感節點存在多項限制，如能量、數據處理能力和通信容量。這些限制影響了WSN的性能，如傳感節點間的通信連接、網絡覆蓋以及網絡壽命[1]。

WSNs中多數傳感節點是由電池供電，并沒有替換設備。同時，多數能量被消耗于數據通信過程。一旦節點能量耗盡，該節點就無法感測數據和傳輸數據，這也縮短了網絡壽命。因此，可通過減少總體數據包數保存能量，進而提高能量利用率。

據此，網絡開銷，即被傳輸到信宿的總體數據包數是以覆蓋限制為下限。基于此界限，每個數據包應以最小跳數的路徑傳輸數據包，進而減少數據包被傳輸的次數。然而，如果節點總是以最小跳數傳輸數據包，這會導致信宿節點附近的節點能耗過快，容易出現能量空洞[2-3]。因此，平衡所有節點負載，減少能耗，進而延長網絡壽命成為多跳WSNs的一項挑戰工作。

為此，本文提出基于光暈網絡模型的平衡負載的數據傳輸算法(coronas-based network model load balanced data gathering，CLBDG)算法。CLBDG算法先建立光暈網絡模型，然后基于覆蓋感知推導每個光暈的節點數及總的節點數，最后，依據再依據最大匹配算法，構建從數據源節點至信宿的最小跳數路徑。通過CLBDG算法，減少了傳輸路數以及產生的數據包數，進而平衡了網絡負載，延長了網絡壽命。

1 模 型

1.1 網絡模型

假定在2-D區域內部署了n個同構靜態節點，且傳輸范圍為T，感測范圍S。

定義1 給定一個傳感網絡，n個傳感節點集V=1,2,…,n和一個信宿節點分布于2-D區域。網絡拓撲可用圖論表示為GV,E,其中E為鏈路。如果節點i與j間的距離di,j小于T,即di,j≤T,則E=i,j|i,j∈V，并且則GV,E也稱為WSN的拓撲圖。

引論1 假定GV,E中的鏈路是雙向的，則G(V,E)是一個無向圖。

在CLBDG算法中，任何一個節點既可扮演成數據源節點(data originator)也可成為路由節點(router)，轉發數據包，它們的定義如下：

定義2 數據源節點先感測數據，然后轉發至信宿。將從感測數據至將數據轉發至信宿，稱為一輪，且標記為Tround。而路由節點僅接收數據包，然后再轉發。

定義3 一周由m輪構成，即Tcycle=m×Tround，并且Tcycle>>Tround，其中m為整數。

在CLBDG算法中，假定在每一周開始，從覆蓋區域的節點中選擇一些節點作為數據源節點，并由它們感測數據，而其它節點作為路由節點。在連續的周內，一個節點可能會改變它的角色，通過角色的輪活，均擔開銷，進而平衡能耗。

1.2 能量模型

每個傳感節點的初始能量為E。這些能量只能用于數據傳輸或接收。與文獻[4-7]的能量模型一樣，忽略節點感測和計算的能耗。例如，Mica2 motes[8]用于感測和計算的能耗僅占總能耗的6%。因此，本文只考慮節點傳輸和接收數據的能耗。

Rx=Eelec×

(1)

Tx=Rx+Eamp××Ta

(2)

其中，Eelec表示發射或接收電路的能耗。而Eamp則為發射放大器傳輸單元比特的能耗。而α為路徑衰落指數，且2≤α≤6。

由于本文以同構網絡為研究對象，所有傳感節點的傳輸范圍均為T，每個數據包的比特數均為。

2 CLBDG算法

2.1 基于覆蓋感知的節點數

首先，假定信宿節點部署于監測區域的中心，并將區域劃分為P個光暈C1,C2,…,CP-1,CP。每個光暈的寬度為R，且小于R≤T,如圖1所示。

圖1 光暈模型

相應的拓撲圖如圖2所示。所有節點部署于覆蓋區域，致使數據源節點產生數據，然后由路由節點轉發數據包，進而均擔路由開銷。

圖2 網絡拓撲

依圖1可知，光暈CP區域面積S(CP)

S(CP)=π(PR)2-π((P-1)R)2=πR2(2P-1)

(3)

S(CP-1)=π((P-1)R)2-π((P-2)R)2=πR2(2P-3)

(4)

因此，在光暈CP-1內需要的數據源節點數可表示為

(5)

因此，CP-1內的總的節點數NP-1，包括數據源節點和路由節點

(6)

對于任何光暈CK,且1≤K≤P,網絡內總的節點數可表示為

(7)

而貫穿所有光暈的總的數據源節點，可表示為MG

(8)

而每一輪轉發一個數據包的總的路由節點數MR

(9)

因此，所有光暈內的總的節點數等于M

(10)

從圖3可知，隨著光暈數的增加，路由節點的百分比快速增加，而數據源節點數的百分比逐漸下降。數據源節點數的下降限制了網絡內產生的數據包數，這提高了網絡壽命。這些數據也證實，光暈數越多的網絡，能量平衡越好。

圖3 路由和數據源節點的百分比隨光暈數變化曲線

2.2 基于隨機節點分布

2.2.1 數據源節點的選擇

CLBDG算法引用[11,12]的覆蓋算法，通過選擇K個不相交連接子集cover，進而保證網絡覆蓋率，并且能保證每個不相交連接子集cover能覆蓋網絡。例如文獻[11]，先隨機選擇一些頭節點，然后每個頭節點圍繞著自己形成一個不相交連接集。在每次迭代時，一集內的所有節點選擇一跳鄰居，致使它們最化覆蓋，然后由它們將信息轉發至頭節點。然后，從所有的這些頭節點中，選擇一個最大覆蓋率的不相交連接子集cover，然后廣播。

CLBDG算法就將已選的子集cover表示數據源節點集，這些節點感測數據。而其它節點根據情況可作為路由節點。

2.2.2 路由節點的選擇

在最外層的光暈CP中，每個數據源節點從光暈CP-1中選擇唯一的路由節點。依次類推，處于光暈CK的數據源節點或路由節點就從圓心圓CK-1選擇唯一的路由節點，且2≤K≤P。從圖論角度，這個過程可看成最大匹配問題(maximum matching problem，MMP)。

若是確定性節點部署，對于CK內的每個節點都是完美匹配，并且在CK-1內存在唯一的路由節點。這也保證數據源節點產生的每個數據包能夠通過唯一的路由節點將數據包成功傳輸至信宿，使得網絡開銷達到平衡。

對于隨機非均勻的節點部署，這無法保證完美匹配。只能通過最大匹配算法，如果CK內的節點不能在CK-1找到路由節點(即匹配)，則它的數據包將丟失。

2.3 數據傳輸方式

如果在Ck內部署NK個節點，致使MG個數據源節點覆蓋光暈Ck，最終Ck內的每個源節點都能在Ck-1內找到唯一的路由節點，并通過此路由節點轉發數據包。在這種情況下，傳輸數據的開銷的平衡問題能得到有效地解決。

顯然，通過此策略，每個路由節點所消耗的能量為(Tx+Rx)，并且每個數據源節點只消耗Tx能量，并且數據包每次只依據最短路徑跳數到達信宿。數據傳輸如圖4所示。

圖4 數據傳輸

注意，在大型網絡內，由于總的數據源節點數小于總的路由節點，圖3可以證明。因此，大型網絡幾乎可以接近開銷平衡。此外，由上述分析可知，節點可以通過轉換角色，平衡能量消耗。

3 性能分析

3.1 真場景及性能評價指標

利用Matlab軟件建立仿真平臺。實驗仿真參數見表1。在性能分析過程中，選擇采用非均勻的節點分布的算法(distributed data gathering with graded node distribution，DGGND)[13]和采用均勻節點分布的算法(optimal data ga-thering paths and energy-balance mechanisms，ODGEB)[14]作為參照。每次實驗仿真獨立重復50次，并取平均值作為最終的實驗數據。

表1 仿真參數

3.2 數據分析

3.2.1 部署的節點數

圖5顯示了各算法部署的節點數隨光暈數的變化曲線。從圖可知，部署的節點數隨著光暈數增加而上升。而采用非均勻部署的DGGND算法的節點數最多，并且隨光暈呈指數增加。而CLBDG算法的節點數是依據式(10)計算，遠低于DGGND，但是略高于采用均勻部署的ODGEB算法。例如，當P=5時，CLBDG算法所部署的節點數比DGGND算法所部署的節點數降低近34%。

圖5 部署的節點數

3.2.2 產生總數據包數

在同種情況下，網絡內產生總數據包數越多，表明流量越大，網絡開銷越重，越不利于拓延網絡壽命。

圖6顯示各算法產生總數據包數隨光暈數的變化曲線。從圖6可知，P的增加，使DGGND算法產生的總數據包數迅速上升。例如，當P=5時，DGGND算法產生的數據包數是CLBDG算法的5.7倍。CLBDG算法通過降低數據包數，可有效地保存能量，進而提高網絡壽命。

圖6 產生總數據包數

3.2.3 網絡壽命

接下來分析各算法的網絡壽命。在本次實驗中，假定P=3，考查感測半徑對網絡壽命的影響。3個算法的歸一化網絡壽命如圖7所示。

圖7 歸一化網絡壽命

從圖7可知，CLBDG算法、DGGND和ODGEB算法的歸一化網絡壽命隨感測半徑增加呈增長趨勢。原因在于：感測半徑的增加有利于傳感節點感測環境數據。與DGGND算法相比，CLBDG算法的歸一化網絡壽命得到顯著提高。例如， 感測半徑為6、6.5時兩種情況下，歸一化網絡壽命分別為0.77和0.92，遠高于隨機DGGND算法。這些數據充分說明，CLBDG算法通過優化部署傳感節點，降低成本，減少覆蓋重疊區域，進而提高網絡壽命。

4 結束語

傳感節點的能效問題是無線傳感網絡的研究熱點。為此，提出基于光暈網絡模型的平衡負載的數據傳輸CLBDG算法。CLBDG算法通過控制傳輸數據包的次數，減少網絡流量，平衡負載，提高網絡壽命。CLBDG算法以信宿節點為中心建立光暈網絡模型，估算網絡內的節點數，依據光暈建立數據傳輸路徑。實驗數據表明，與同類算法相比，CLBDG算法的網絡壽命得到了有效提高。