馮小歐, 陳 婉, 袁培燕

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

0 引 言

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

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

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

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

1 模 型

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

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

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

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

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

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

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

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

1.2 能量模型

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

Rx=Eelec×

(1)

Tx=Rx+Eamp××Ta

(2)

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

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

2 CLBDG算法

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

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

圖1 光暈?zāi)Ｐ?/p>

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

圖2 網(wǎng)絡(luò)拓?fù)?/p>

依圖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é)點(diǎn)數(shù)可表示為

(5)

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

(6)

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

(7)

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

(8)

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

(9)

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

(10)

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

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

2.2 基于隨機(jī)節(jié)點(diǎn)分布

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

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

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

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

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

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

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

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

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

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

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

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

3 性能分析

3.1 真場景及性能評價指標(biāo)

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

表1 仿真參數(shù)

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

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

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

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

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

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

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

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

3.2.3 網(wǎng)絡(luò)壽命

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

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

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

4 結(jié)束語

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