馮小歐, 陳 婉, 袁培燕

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

0 引 言

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

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

據(jù)此，網(wǎng)絡開銷，即被傳輸?shù)叫潘薜目傮w數(shù)據(jù)包數(shù)是以覆蓋限制為下限?；诖私缦?，每個數(shù)據(jù)包應以最小跳數(shù)的路徑傳輸數(shù)據(jù)包，進而減少數(shù)據(jù)包被傳輸?shù)拇螖?shù)。然而，如果節(jié)點總是以最小跳數(shù)傳輸數(shù)據(jù)包，這會導致信宿節(jié)點附近的節(jié)點能耗過快，容易出現(xiàn)能量空洞[2-3]。因此，平衡所有節(jié)點負載，減少能耗，進而延長網(wǎng)絡壽命成為多跳WSNs的一項挑戰(zhàn)工作。

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

1 模 型

1.1 網(wǎng)絡模型

假定在2-D區(qū)域內(nèi)部署了n個同構靜態(tài)節(jié)點，且傳輸范圍為T，感測范圍S。

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

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

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

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

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

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

1.2 能量模型

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

Rx=Eelec×

(1)

Tx=Rx+Eamp××Ta

(2)

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

由于本文以同構網(wǎng)絡為研究對象，所有傳感節(jié)點的傳輸范圍均為T，每個數(shù)據(jù)包的比特數(shù)均為。

2 CLBDG算法

2.1 基于覆蓋感知的節(jié)點數(shù)

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

圖1 光暈模型

相應的拓撲圖如圖2所示。所有節(jié)點部署于覆蓋區(qū)域，致使數(shù)據(jù)源節(jié)點產(chǎn)生數(shù)據(jù)，然后由路由節(jié)點轉發(fā)數(shù)據(jù)包，進而均擔路由開銷。

圖2 網(wǎng)絡拓撲

依圖1可知，光暈CP區(qū)域面積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內(nèi)需要的數(shù)據(jù)源節(jié)點數(shù)可表示為

(5)

因此，CP-1內(nèi)的總的節(jié)點數(shù)NP-1，包括數(shù)據(jù)源節(jié)點和路由節(jié)點

(6)

對于任何光暈CK,且1≤K≤P,網(wǎng)絡內(nèi)總的節(jié)點數(shù)可表示為

(7)

而貫穿所有光暈的總的數(shù)據(jù)源節(jié)點，可表示為MG

(8)

而每一輪轉發(fā)一個數(shù)據(jù)包的總的路由節(jié)點數(shù)MR

(9)

因此，所有光暈內(nèi)的總的節(jié)點數(shù)等于M

(10)

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

圖3 路由和數(shù)據(jù)源節(jié)點的百分比隨光暈數(shù)變化曲線

2.2 基于隨機節(jié)點分布

2.2.1 數(shù)據(jù)源節(jié)點的選擇

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

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

2.2.2 路由節(jié)點的選擇

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

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

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

2.3 數(shù)據(jù)傳輸方式

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

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

圖4 數(shù)據(jù)傳輸

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

3 性能分析

3.1 真場景及性能評價指標

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

表1 仿真參數(shù)

3.2 數(shù)據(jù)分析

3.2.1 部署的節(jié)點數(shù)

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

圖5 部署的節(jié)點數(shù)

3.2.2 產(chǎn)生總數(shù)據(jù)包數(shù)

在同種情況下，網(wǎng)絡內(nèi)產(chǎn)生總數(shù)據(jù)包數(shù)越多，表明流量越大，網(wǎng)絡開銷越重，越不利于拓延網(wǎng)絡壽命。

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

圖6 產(chǎn)生總數(shù)據(jù)包數(shù)

3.2.3 網(wǎng)絡壽命

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

圖7 歸一化網(wǎng)絡壽命

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

4 結束語

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