劉 青李蘭蘭張德樹

(1.滁州職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，安徽 滁州 239000；2.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211106)

無線傳感網(wǎng)絡(luò)(Wireless Sensor Networks，WSNs)具有組織、部署快捷等優(yōu)勢[1-2]。目前，WSNs已在多個領(lǐng)域內(nèi)廣泛使用，如健康醫(yī)療，野外環(huán)境監(jiān)測。WSNs內(nèi)節(jié)點(diǎn)先感測環(huán)境數(shù)據(jù)，再將數(shù)據(jù)傳輸至信宿(Sink)，進(jìn)而實(shí)現(xiàn)對環(huán)境監(jiān)測的目的。

由于Sink需收集檢測區(qū)域內(nèi)所有數(shù)據(jù)，鄰近Sink的節(jié)點(diǎn)承擔(dān)了較多的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)。這就使得這些節(jié)點(diǎn)的能耗速度快于其他遠(yuǎn)離Sink的節(jié)點(diǎn)。學(xué)術(shù)界將這種情況稱為熱點(diǎn)問題[3]或者能量空洞問題[4-5]。熱點(diǎn)問題會導(dǎo)致網(wǎng)絡(luò)分割，降低了WSNs的性能。

基于移動Sink的路由是緩解熱點(diǎn)問題的可行辦法。通過Sink的移動，平衡網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的能耗，避免網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的能量消耗過快，進(jìn)而緩解熱點(diǎn)問題[6-7]。然而，由于Sink的位置是隨時間變化的，向節(jié)點(diǎn)通告Sink的位置需交互大量的消息，這增加了節(jié)點(diǎn)的能耗，以及數(shù)據(jù)傳輸時延。

將節(jié)點(diǎn)劃分為雙層的基于虛擬設(shè)備的層次路由可以有效地減少交互消息的開銷[8-9]。在層次路由中，無需向整個網(wǎng)絡(luò)泛洪Sink位置，只需向高層次的節(jié)點(diǎn)提供Sink位置。而當(dāng)?shù)蛯哟蔚墓?jié)點(diǎn)需要傳輸數(shù)據(jù)時，就向高層次節(jié)點(diǎn)索取Sink位置信息。高層次節(jié)點(diǎn)就為低層次節(jié)點(diǎn)扮演了Sink位置提供者的角色。此外，高層次節(jié)點(diǎn)有時也扮演數(shù)據(jù)轉(zhuǎn)發(fā)者的角色。因此，層次路由能夠緩解在網(wǎng)絡(luò)通告Sink位置信息的開銷以及降低數(shù)據(jù)傳輸時延。

為此，針對基于移動Sink的WSNs網(wǎng)絡(luò)，提出一種基于環(huán)形的層次路由協(xié)議(Ring-based Hierarchical Routing，RBHR)。RBHR路由先將網(wǎng)絡(luò)進(jìn)行環(huán)形分割，形成多個等間隔的環(huán)。然后，再選擇數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點(diǎn)，并由這些節(jié)點(diǎn)構(gòu)建環(huán)。最后，這些數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點(diǎn)利用角度路由策略向Sink傳輸數(shù)據(jù)。仿真結(jié)果表明，RBHR路由降低了能耗，并降低了數(shù)據(jù)包傳輸時延。

1 系統(tǒng)模型

在二維方形檢測區(qū)域?×?內(nèi)均勻地部署n個傳感節(jié)點(diǎn)和一個Sink。所有傳感節(jié)點(diǎn)是靜止的，不能移動。Sink遵照隨機(jī)點(diǎn)移動(Random Waypoint Mobility，RWM)模型移動。

每個傳感節(jié)點(diǎn)具有自己的唯一的ID號，令si表示第i個傳感節(jié)點(diǎn)。令(xi，yi)表示傳感節(jié)點(diǎn)si的位置。每個傳感節(jié)點(diǎn)具有固定的通信半徑R。此外，假定每個節(jié)點(diǎn)知曉檢測區(qū)域?×?的中心點(diǎn)位置。

令Ni表示節(jié)點(diǎn)si的一跳鄰居節(jié)點(diǎn)集，其定義如式(1)所示:

式中:R表示節(jié)點(diǎn)的通信半徑；d(si，sj)表示節(jié)點(diǎn)si與節(jié)點(diǎn)sj間的歐式距離。

1.1 能量消耗模型

節(jié)點(diǎn)的大部分能量用于發(fā)送數(shù)據(jù)和接收數(shù)據(jù)。因此，本文只考慮節(jié)點(diǎn)在執(zhí)行發(fā)送數(shù)據(jù)和接收數(shù)據(jù)這兩個動作所消耗的能量。引用文獻(xiàn)[10]相同的能量消耗模型，如圖1所示。

圖1 能量消耗模型

節(jié)點(diǎn)傳輸m比特?cái)?shù)據(jù)所消耗的能量ETx(m，d):

式中:Eelec表示發(fā)射電路處理1比特?cái)?shù)據(jù)所消耗的能量；εfs、εamp表示在自由空間信道模型、多徑衰落信道模型下功率放大電路處理1比特?cái)?shù)據(jù)所消耗的能量；d0表示判斷信道模型的距離閾值，其定義如式(3)所示:

節(jié)點(diǎn)接收m比特?cái)?shù)據(jù)所消耗的能量ERx(m):

2 RBHR路由

RBHR路由主要由三個階段構(gòu)成:區(qū)域分割，環(huán)上轉(zhuǎn)發(fā)節(jié)點(diǎn)(Forwarding Node on Ring，F(xiàn)NR)的選舉和數(shù)據(jù)傳輸三個階段構(gòu)成。

2.1 基于環(huán)的區(qū)域分割

將感測區(qū)域劃分為n個等間隔的同心環(huán)R1，R2，…，Rn，這n個環(huán)所對應(yīng)的半徑分別為r1，r2，…，rn。如圖2所示，圖中空心圓表示傳感節(jié)點(diǎn)；三個環(huán)R1，R2，R3以點(diǎn)C為圓心，分別以r1，r2，r3為半徑。

圖2 基于環(huán)的網(wǎng)絡(luò)分割示例

首先，依據(jù)方形的檢測區(qū)域的邊長?，估計(jì)最優(yōu)的環(huán)數(shù)n:

然后，依據(jù)式(5)計(jì)算第k個環(huán)的半徑rk:

2.2 環(huán)上轉(zhuǎn)發(fā)節(jié)點(diǎn)的選舉

確定了環(huán)數(shù)n和各個環(huán)的半徑(r1，r2，…，rn)后，Sink就在監(jiān)測區(qū)域內(nèi)廣播此信息infor_MSG，其包含[(r1，r2，…，rn)，(R1，R2，…，Rn)]。一旦收到infor_MSG消息，節(jié)點(diǎn)(假定節(jié)點(diǎn)si)計(jì)算其離檢測區(qū)域中心點(diǎn)的距離，再判斷此距離位于哪個環(huán)內(nèi)。對于n個環(huán)半徑，依據(jù)檢測是否滿足式(7)，若滿足，則意味著落在第k個環(huán)內(nèi)，并將節(jié)點(diǎn)si稱為屬于第k個環(huán)的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)。

式中:α＝R/2表示任意兩個圓環(huán)間的間隔。

如圖3所示，圖中黑色實(shí)心點(diǎn)表示候選轉(zhuǎn)發(fā)節(jié)點(diǎn)。依據(jù)式(7)，網(wǎng)絡(luò)的部分節(jié)點(diǎn)將被選舉為候選轉(zhuǎn)發(fā)節(jié)點(diǎn)。

圖3 候選轉(zhuǎn)發(fā)節(jié)點(diǎn)示例

構(gòu)選了候選轉(zhuǎn)發(fā)節(jié)點(diǎn)后，每個環(huán)上的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)再依據(jù)逆時針方向構(gòu)建環(huán)，將環(huán)上的節(jié)點(diǎn)稱為環(huán)上轉(zhuǎn)發(fā)節(jié)點(diǎn)(FNR)。具體的實(shí)現(xiàn)過程如下:

第一步:在每個環(huán)上先隨機(jī)選擇一個候選轉(zhuǎn)發(fā)節(jié)點(diǎn)，將其稱為構(gòu)環(huán)起點(diǎn)(Start)。

通過上述兩步，最終構(gòu)建環(huán)上的轉(zhuǎn)發(fā)節(jié)點(diǎn)。如圖4所示。圖中的黑色三角形表示構(gòu)環(huán)起點(diǎn)，采用逆時針，依據(jù)式(8)構(gòu)建一個閉合的環(huán)。

圖4 環(huán)上轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇

2.3 數(shù)據(jù)傳輸過程

2.3.1 數(shù)據(jù)收集節(jié)點(diǎn)

當(dāng)節(jié)點(diǎn)感測數(shù)據(jù)Data后，節(jié)點(diǎn)先將數(shù)據(jù)傳輸至離其最近FNR，然后由FNR再構(gòu)建連通Sink的路由，并利用此路由將數(shù)據(jù)Data傳輸至Sink。

為了讓傳感節(jié)點(diǎn)獲取周邊的FNR信息，每個FNR廣播通告消息Nb_Mes[Ri，ID，＾si(＾x，＾y)]，其包含了FNR所在環(huán)數(shù)，ID號以及位置。

節(jié)點(diǎn)可能收到來自多個FNRs傳輸?shù)腘b_Mes消息。在這種情況下，節(jié)點(diǎn)就計(jì)算離各FNRs的距離，并選擇離自己最近的FNR作為自己轉(zhuǎn)發(fā)數(shù)據(jù)的節(jié)點(diǎn)，將此FNR稱為節(jié)點(diǎn)的數(shù)據(jù)收集節(jié)點(diǎn)(Data Collecting Node，DCN)。每個節(jié)點(diǎn)就將自己的感測數(shù)據(jù)傳輸至自己的DCN。

2.3.2 Sink實(shí)時位置的分享

FNR收到數(shù)據(jù)后，需要將數(shù)據(jù)傳輸至Sink。由于Sink是移動的，F(xiàn)NR需知曉Sink的實(shí)時位置。為此，Sink將自己的位置以及在此位置的停留時間在網(wǎng)絡(luò)內(nèi)進(jìn)行通告，將此過程稱為Sink實(shí)時位置的分享。

考慮到Sink所有位置的不同，Sink采用不同的方向傳輸其位置消息Sink_Mes〈Sink(x，y)，pause time〉。依據(jù)Sink在環(huán)內(nèi)或者環(huán)外，將其位置分為三種情況:①Sink在所有環(huán)外，如圖5(a)所示；②Sink在所有環(huán)內(nèi)，如圖5(b)所示；③在任意兩個環(huán)之間，如圖5(c)所示。

圖5 移動Sink位置的分類

若Sink在所有環(huán)外，Sink就向區(qū)域中心點(diǎn)傳輸Sink_Mes；若Sink在所有環(huán)內(nèi)，Sink就向背離中心點(diǎn)傳輸Sink_Mes。若Sink在兩環(huán)之間，Sink就向區(qū)域中心點(diǎn)和背離中心點(diǎn)兩個方向傳輸Sink_Mes。如圖5所示。

FNDs收到Sink_Mes后，就從Sink_Mes中提取Sink位置，并將此位置與自己原來保存的Sink位置進(jìn)行匹配。如果兩個位置相同，就丟失此Sink_Mes。否則，F(xiàn)NDs就與鄰居節(jié)點(diǎn)分享Sink_Mes消息。

?

當(dāng)一個FND分別從逆時針和順時針兩方向所接收了同一個Sink_Mes時，F(xiàn)ND不再向鄰居節(jié)點(diǎn)傳輸Sink_Mes。此外，在傳輸Sink_Mes時，鄰近的傳感節(jié)點(diǎn)(非FND)也可能會收到Sink_Mes。由于傳感節(jié)點(diǎn)無需獲取Sink位置，傳感節(jié)點(diǎn)直接丟棄Sink_Mes。

算法1描述了分享Sink實(shí)時位置的流程。其中d(Sink(x，y)，C(xc，yc))表示Sink離中心點(diǎn)的位置。

2.3.3 FNDs向Sink傳輸數(shù)據(jù)

RBHR采用文獻(xiàn)[11]提出的基于角度路由傳輸數(shù)據(jù)。FNDs收到數(shù)據(jù)后，就從鄰居的FNDs節(jié)點(diǎn)中選擇與Sink具有最小角度的節(jié)點(diǎn)作為下一跳數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點(diǎn)，重復(fù)上述過程，直到數(shù)據(jù)傳輸至Sink。

如圖6所示，s1為數(shù)據(jù)源節(jié)點(diǎn)。s1先將數(shù)據(jù)Data傳輸至離其最近的FND(B1)。收到數(shù)據(jù)Data后，B1需要選擇下一跳節(jié)點(diǎn)。由于B1有兩個鄰居節(jié)點(diǎn)(B2和B3)，B1就利用基于角度路由策略分別計(jì)算角∠B2CS和角∠B3CS。其中C表示中心點(diǎn)位置；S表示Sink(數(shù)據(jù)包的目的節(jié)點(diǎn))。

圖6 數(shù)據(jù)傳輸示例

由于∠B3CS小于∠B2CS，B1選擇B3作為下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。即B1將數(shù)據(jù)Data傳輸至B3。重復(fù)上述過程，最終，將數(shù)據(jù)傳輸至Sink。

3 性能仿真

3.1 仿真參數(shù)

利用MATLAB軟件建立仿真平臺，分析RBHR路由性能。在400 m×400 m方形區(qū)域內(nèi)均勻部署100至300個節(jié)點(diǎn)。Sink依據(jù)RWM模型移動，移動速度3 km/h~15 km/h。具體的仿真參數(shù)如表1所示。

表1 仿真參數(shù)

為了更好地分析RBHR路由的性能，選擇文獻(xiàn)[12]提出的RRP路由和文獻(xiàn)[13]提出的GCRP路由作為參照，并分析它們的能耗性能和數(shù)據(jù)傳輸性能。

3.2 節(jié)點(diǎn)數(shù)對能耗和數(shù)據(jù)傳輸性能的影響

本次實(shí)驗(yàn)分析節(jié)點(diǎn)數(shù)對RBHR路由、RRP和GCRP算法的能耗和數(shù)據(jù)傳輸性能的影響。Sink的平均移動速度為9 km/h。

首先，分析節(jié)點(diǎn)數(shù)對總體的能耗影響，如圖7所示。從圖可知，總體能耗隨節(jié)點(diǎn)數(shù)的增加而上升。這主要是因?yàn)?節(jié)點(diǎn)數(shù)越多，產(chǎn)生的數(shù)據(jù)包越多，加大了傳感節(jié)點(diǎn)和FND傳輸數(shù)據(jù)任務(wù)，這就增加了它們的能耗。

圖7 總體能耗隨節(jié)點(diǎn)數(shù)的變化

相比于RBHR路由，RRP路由消耗了更多的能耗。原因在于:RRP路由在傳輸數(shù)據(jù)前需要獲取Sink位置信息，這加大了通信開銷；而RBHR路由中，傳感節(jié)點(diǎn)無需獲取Sink位置，只有FND節(jié)點(diǎn)需要獲取Sink位置。FNDs節(jié)點(diǎn)收集了數(shù)據(jù)后，再依據(jù)角度路由向Sink傳輸數(shù)據(jù)。

此外，與RBHR路由相類似，GCRP路由是沿著循環(huán)鏈傳輸數(shù)據(jù)。然而，由于Sink在外圍移動，使不位于邊界上的節(jié)點(diǎn)需要消耗更多能量傳輸數(shù)據(jù)。

接下來，分析節(jié)點(diǎn)數(shù)對傳輸數(shù)據(jù)包的平均時延的影響，如圖8所示。平均時延是指將數(shù)據(jù)包從源節(jié)點(diǎn)傳輸至Sink所消耗的平均時延。傳輸數(shù)據(jù)的路徑，跳數(shù)以及參與路由的節(jié)點(diǎn)數(shù)對平均時延均有影響。

圖8 節(jié)點(diǎn)數(shù)對傳輸數(shù)據(jù)包的平均時延的影響

從圖8可知，節(jié)點(diǎn)數(shù)的增加使平均時延呈上升趨勢。原因在于:節(jié)點(diǎn)數(shù)越多，源節(jié)點(diǎn)連通于Sink的跳數(shù)也隨之增加。相比于RRP路由，RBHR路由減少了傳輸數(shù)據(jù)包的平均時延。這歸功于:RBHR路由依據(jù)角度決策路由，縮短了數(shù)據(jù)傳輸路徑。而在RRP路由中，每個源節(jié)點(diǎn)采用貪婪策略構(gòu)建路由。這增加了數(shù)據(jù)傳輸時延。

數(shù)據(jù)包傳遞率也是衡量路由的數(shù)據(jù)傳輸性能的重要指標(biāo)。圖9給出了數(shù)據(jù)包傳遞率隨節(jié)點(diǎn)數(shù)的變化情況。從圖可知，節(jié)點(diǎn)數(shù)的增加使數(shù)據(jù)包傳遞率呈下降趨勢。原因在于:節(jié)點(diǎn)數(shù)的增加，增加了網(wǎng)絡(luò)擁塞的概率，降低了數(shù)據(jù)包傳遞率。

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

相比于RRP路由和GCRP路由，RBHR路由的數(shù)據(jù)包傳遞率隨節(jié)點(diǎn)數(shù)的增加下降緩慢。在RBHR路由中，利用FNDs向Sink傳輸數(shù)據(jù)。FNDs只占節(jié)點(diǎn)數(shù)一部分。只有這些FNDs需要獲取Sink位置，減少了網(wǎng)絡(luò)負(fù)擔(dān)，降低了網(wǎng)絡(luò)擁塞概率。

3.3 Sink的移動速度對能耗和數(shù)據(jù)傳輸性能的影響

本次實(shí)驗(yàn)分析Sink移動速度對能耗和數(shù)據(jù)傳輸性能的影響。節(jié)點(diǎn)為200個，Sink的移動速度從3 km/h至15 km/h變化。

首先，分析Sink移動速度對網(wǎng)絡(luò)總體能耗的影響，如圖10所示。從圖可知Sink移動速度的增加，增加了網(wǎng)絡(luò)總體能耗。原因在于:Sink移動速度越快，更新位置的頻率越快，這增加了網(wǎng)絡(luò)總體能耗。此外，Sink的快速移動，也增加了路由斷裂的概率。一旦路由斷裂，需要重新構(gòu)建路由，這也增加了網(wǎng)絡(luò)的能耗。

圖10 總體能耗隨Sink的移動速度的變化情況

在RBHR路由，GCRP路由和RRP路由中，RRP路由的能耗最高。原因在于:RRP路由采用單一環(huán)結(jié)構(gòu)傳輸數(shù)據(jù)，源節(jié)點(diǎn)需獲取Sink位置，這增加了節(jié)點(diǎn)能耗。而RBHR路由利用基于角度構(gòu)建路由，減少了需要獲取Sink位置的節(jié)點(diǎn)數(shù)，降低了網(wǎng)絡(luò)開銷。

接下來，分析Sink移動速度對傳輸數(shù)據(jù)包的平均時延的影響，如圖11所示。從圖可知，Sink移動速度的增加，提升了傳輸數(shù)據(jù)包的平均時延。Sink移動速度越快，更新Sink位置的頻率越高，開銷越大，網(wǎng)絡(luò)擁塞概率越高。此外，移動速度越快，加速路由斷裂的概率，增加傳輸數(shù)據(jù)包的平均時延。

圖11 傳輸數(shù)據(jù)包平均時延隨Sink移動速度的變化情況

相比于RRP路由和GCRP路由，RBHR路由具有較低的平均時延性能。原因在于:RBHR路由通過FNDs構(gòu)建環(huán)，并利用角度策略縮短了數(shù)據(jù)包傳輸路徑，縮短了傳輸時延。

最后，分析Sink移動速度對數(shù)據(jù)包傳遞率的影響，如圖12所示。Sink移動速度越大，Sink將在較短的時間內(nèi)穿越較大的網(wǎng)絡(luò)空間，這可能縮短了Sink收集數(shù)據(jù)的時間。從圖可知，相比于GCRP和RRP路由，提出的RBHR路由的數(shù)據(jù)包傳遞率得到較大提高，并且控制了其隨Sink移動速度的增加而降低的速度。

圖12 數(shù)據(jù)包傳遞率隨Sink移動速度的變化情況

4 結(jié)束語

針對基于移動Sink的WSNs中的熱點(diǎn)問題，提出基于環(huán)形的層次路由協(xié)議RBHR。RBHR通過限制更新Sink位置的節(jié)點(diǎn)數(shù)，降低開銷，同時采用基于角度路由策略向Sink傳輸數(shù)據(jù)，縮短了數(shù)據(jù)傳輸路徑。仿真結(jié)果表明，提出的RBHR路由有效地降低了能耗，并減少了數(shù)據(jù)傳輸時延。

本文只考慮了一個Sink場景。后期，將進(jìn)一步優(yōu)化路由策略，并考慮多個Sink協(xié)作收集網(wǎng)絡(luò)內(nèi)的數(shù)據(jù)的場景。這將是未來的研究內(nèi)容。