無線傳感網(wǎng)絡中基于環(huán)形的層次型路由協(xié)議*

劉 青李蘭蘭張德樹

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

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

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

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

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

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

1 系統(tǒng)模型

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

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

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

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

1.1 能量消耗模型

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

圖1 能量消耗模型

節(jié)點傳輸m比特數(shù)據(jù)所消耗的能量ETx(m，d):

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

節(jié)點接收m比特數(shù)據(jù)所消耗的能量ERx(m):

2 RBHR路由

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

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

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

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

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

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

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

確定了環(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é)點(假定節(jié)點si)計算其離檢測區(qū)域中心點的距離，再判斷此距離位于哪個環(huán)內(nèi)。對于n個環(huán)半徑，依據(jù)檢測是否滿足式(7)，若滿足，則意味著落在第k個環(huán)內(nèi)，并將節(jié)點si稱為屬于第k個環(huán)的候選轉(zhuǎn)發(fā)節(jié)點。

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

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

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

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

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

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

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

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

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

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

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

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

2.3.2 Sink實時位置的分享

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

考慮到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ū)域中心點傳輸Sink_Mes；若Sink在所有環(huán)內(nèi)，Sink就向背離中心點傳輸Sink_Mes。若Sink在兩環(huán)之間，Sink就向區(qū)域中心點和背離中心點兩個方向傳輸Sink_Mes。如圖5所示。

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

?

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

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

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

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

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

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

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

3 性能仿真

3.1 仿真參數(shù)

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

表1 仿真參數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結束語

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

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