基于簇的無線傳感器網絡交會路由協議

楊 旭，王春佳2，李 莉

(1.云南機電職業技術學院 工業信息技術系，昆明 650203;2.云南師范大學 基礎教育集團，昆明 650092)

0 引言

無線傳感器網絡(WSN)由大量低成本、低功耗和智能傳感器節點以及一個或多個sink或基站(BS)組成[1-2]，這些節點體積小，可以執行許多重要功能，包括事件感知、信息處理和數據通信[3-4]，WSN已經廣泛應用與軍事應用和民用場景[5-6]，由于易于部署，擴展傳輸范圍和自組織等各種優點，WSN已經取代了傳統網絡。

WSN中傳感器節點成本低且能量有限，由于這種能量約束，有效的路由協議可以使得傳感器節點感測環境并生成有用的數據[7]。當用戶或sink想要數據時，將查詢發送到具有相關數據的傳感器節點，傳感器節點通過中間節點將生成的數據發送給用戶或sink。由于這些傳感器節點具有有限的功率，它們可以容易地耗盡其能量，因此為了增加網絡壽命并減少延遲，需要從源節點到sink數據的有效路由[8]。隨著WSN技術的深入，平衡網絡負載、延長網絡壽命和均衡網絡能量消耗已經成為WSN研究的重點。

WSN中的分層路由是一個非常重要的主題，在過去十年中一直吸引著研究者，典型的分層路由稱為簇的路由，其中網絡被分成多個簇，低功耗自適應集簇分層協議(Low-Energy Adaptive Clustering Hierarchy, LEACH)是一種典型的分層協議[9]，目前許多協議都是在LEACH協議上進行改進得到的[10]，如文獻[11]中提出的基于非均勻分簇的無線傳感器網絡分層路由協議，該協議以LEACH的分簇思想為基礎，通過分層機制及競爭機制選取簇首，使簇首節點分布更加合理，有效均衡節點的能量消耗。和文獻[12]中基于簇首移動的無線傳感器網絡路由算法，該協議創新點是將簇首設置為移動節點，通過一定規則確定簇首每輪所需移動到的最佳位置，實現節點能耗均衡。

最近關于WSN的研究有一部分為非典型分層路由，包括基于鏈的路由協議、基于樹的路由協議、基于網格的路由協議和基于區域的路由協議[13]?；趨^域的拓撲是一種最新結構，其中一些傳感器節點在特定區域中指定并充當高層節點。高層節點執行從普通節點的數據收集和到數據的數據傳輸任務，可以根據負載平衡要求調整區域的大小[14]。在基于區域的路由協議中，網絡在不同區域之間劃分，傳感器節點是由他們所屬的地區確定。LBDD是一種典型的基于區域的路由協議[15]，拓撲結構簡單，通信方式也很簡單，但是這種拓撲很容易導致能量消耗不平衡，此外，在大區域網絡中，線路或條帶上的泛濫將導致節點的大量能量消耗。與LBDD不同，Railroad協議和ring由協議[16]首先從會合區域獲取sink的位置信息，然后將數據發送到sink，但是兩種路由協議在大型網絡中導致過多的開銷，而預期數據傳輸延遲高于LBDD。

為了解決現有基于區域路由協議中能量不均衡、網絡壽命問題，本文提出一種基于簇的交會路由協議CRRP。在該協議中，整個傳感器網絡被劃分為若干交會區域，并且根據所駐留的區域對節點進行分類。在本文中，簇在分區區域內構建，然后根據節點程度進行簇頭選擇，簇頭具有sink位置的信息，只要sink的位置發生變化，sink就會通過網關節點將其更新的信息發送到最近的簇頭。為了找到sink的位置，常規節點將請求消息發送到其最近的骨干節點，并且該骨干節點將請求發送到簇頭。通過這種方式，常規節點了解了sink的位置，然后直接將數據發送到sink，當簇頭開始耗盡其能量時，重新進行新簇形成。本文協議會合區域劃分整個網絡區域并在傳感器節點之間分配網絡負載，可以增加網絡壽命。

1 CRRP協議

在所提路由協議中，網絡由若干傳感器節點組成，傳感器節點本質上是靜態的。網絡由交叉區域劃分，并在其中構建簇，sink將其更新的位置信息發送到交叉區域內的節點，并且源節點從它們獲取sink的當前位置并將數據發送到sink。

如圖1所示，在網絡中間構造一些水平和垂直寬度的虛擬區域，其中心位于任意位置(u,v)。該虛擬結構將網絡劃分為四個部分：1)水平左hl;2)水平右hr;3)垂直向上vu;4)垂直底部vb。這個交叉區域充當交會區域，位于該會合區域內的傳感器節點被稱為骨干節點。在該交叉區域中，基于節點和最大公共鄰接節點來構造簇，每個簇由一個簇頭組成。這些簇頭負責將sink的位置發送到源節點，并根據sink的當前位置更新sink位置。該協議包括發現鄰居、形成交叉區域、簇的形成和簇頭創建，發現傳感器節點區域和最終數據傳輸。

圖1 交會區域和骨干節點的初始視圖

首先對WSN網絡模型進行假設：

1)部署后，所有傳感器節點都是靜止的。

2)Sink將改變其位置，即sink是移動的。

3)對于sink的計算能力，電池消耗和存儲器沒有限制。

4)傳感器節點的能量有限。

5)所有傳感器節點均勻。

6)為每個節點分配一個唯一的ID。

7)網絡拓撲在簇形成時不受影響。

本文協議的整體流程見圖2所示。

圖2 本文協議流程圖

1.1 鄰居發現和交會區域形成

在鄰居發現的第一階段，起始節點廣播鄰居發現(NBR_D)控制包，包含節點的ID，節點位置及其剩余能量水平。在接收到該包時，該節點鄰居表包含發送方節點的節點ID，其位置和剩余能量。如果表中已經存在發送方節點的條目，則接收方丟棄該包；如果先前沒有廣播，sink也廣播相同的包。在此階段結束時，所有節點都具有關于其一跳鄰居的信息。

算法1：鄰居發現。

Nb(x)任何節點x的鄰居集合，初始化為φ

Nbtable(x)：由節點x維持的鄰居表初始化為φ

Erx：節點x的能量

NBR_Dx：如果傳感器節點x發送數據包，則節點x的鄰居發現控制數據包設置為真，初始化為false

Locx：節點x的位置

NBR_D:if (idy?Nb(x)) then

Nb(x)=Nb(x)∪y；

用更新Nbtable(x)

if(NBR_Dx==false)then

NBR_Dx←true

1_rb(NBR_Dx,idx,Erx,Locx)；

?廣播NBR_D包

else 丟棄包

endif

else丟棄包

endif

對于交會區域的生成與構建，將其視為(Xmax,Ymax)，并將區域的寬度視為w。因此wx和wy可以確定條帶的水平和垂直范圍。

(1)

(2)

1.2 傳感器節點區域發現

傳感器節點使用它們的位置信息坐標(x,y)來確定它們所屬的區域。例如，駐留在第一分區和第八分區中的節點將從hr與目的地(x,v)通信。以相同的方式，第二和第三分區的傳感器節點可以從vu與目的地(u,y)等進行通信，其中(u,v)是網絡的中心。

算法2：節點區域發現。

θ=0,α=0

(u,v)：網絡的中心

(x,y)：節點的位置

令π=180°;C←(u,v)

?C定義了網絡的中心。

計算節點x與位置的新坐標(x-u,y-u)和(x,y)

(A,B)←(x-u,y-u)

if (A>0&&B>0)thenα←θ

具有位置(x,y)的節點屬于第1區域，可以從hr與目標位置進行通信(x,v)。

具有位置(x,y)的節點屬于第2區域，可以從vu與目標通信位置(u,y)。

end if

end if

if (A<0&&B>0) thenα←π-θ

具有位置(x,y)的節點屬于第3區域，可以從vu與目標位置通信(u,y)。

位置為(x,y)的節點屬于第4區域，可以從hl節點與目標位置通信(x,v)。

end if

end if

if (A<0&&B<0) thenα←π+θ

位置為(x,y)的節點屬于第5區域，可以從hl節點與目標位置通信(x,v)。

位置為(x,y)的節點屬于第6區域，可以通過vb與目標通信位置(u,y)。

end if

end if

if (A>0&&B<0) thenα←2π-θ

位置為(x,y)的節點屬于第7區域，可以通過vb與目標位置進行通信(u,y)。

位置為(x,y)的節點屬于第8區域，可以從hr與目標位置進行通信(x,v)。

end if

end if

1.3 簇的生成

通過以下步驟在集合區內建立簇：

1) 簇形成機制由具有最高節點度的節點i發起；

2)在初始節點的單跳鄰居中，找出節點p，具有最大的公共鄰接。如果有多個節點，則考慮ID最低的節點；

3)節點i和p的一個跳鄰居中常見的節點屬于包括i和p的一個簇，節點i將被視為簇頭(CH)；

4)具有最節點度的剩余節點i(發起節點)的一跳鄰居為簇的形成開始相同的進程，并聲明自己為CH。

簇生成偽代碼見算法3。

算法3:簇的生成：

N：網絡中節點的總數

(Vi,Ei)：節點i的連通矩陣

?Vi包含節點i和它的單跳鄰中

?Ei包含Vi中節點之間的雙向邊

i：發起節點

S(i)：節點i的鄰居集

L(i)：L(i)包含節點i的一個跳過鄰居節點

C(i)：簇中元素集合，最初為空

N_C(i)：不在簇中的節點集

i=maxargjdegree(Nj) ?j是任意節點

S(i)={j,(i,j)∈Ei},C(i)={i}While (L(i)≠φ)

發現p∈L(i)與最大|l(i)∩l(p)|

C(i)←[Ci∪{p}∪{j,{j,p}}∈Ei]

N_Ci←[Vi?Ci]

Endwhile

i=maxargidegree(N_Ci)

CH←i

對節點i重復步驟2

簇形成過程如圖3所示，假設節點1具有最大的節點度，因此啟動了簇的形成過程。節點(2, 3, 4, 5, 6)是相鄰的節點。根據算法3，節點3應該是節點p，因為它與節點1的公共鄰域最大。所以節點(1, 2, 3, 4, 5)必須在一個簇中，節點1應該是CH。

圖3 簇形成技術

在本文協議中，簇頭重選與新的簇形成一起發生，步驟為：

1)當任何簇頭節點i開始耗盡其能量時，按照算法1得到簇內具有最大公共鄰接的節點；

2)節點將聲明為新的簇頭，并按照算法3生成新的簇。

1.4 移動sink管理

在協議匯聚節點的這個階段，節點通過網關節點將其位置通知給簇頭節點，集合點區域內的所有簇頭都有關于sink位置的信息。當sink移動時，將Beacon包廣播到其鄰居之后，sink選擇其鄰居之一將其位置信息中繼到集合區域內最近的簇頭之一。sink借助傳感器節點區域發現機制或借助位置因子(LF)轉發數據。

令節點i想要從鄰居節點Nb(i)中選擇其中一個鄰居節點，Eri是其剩余能量，LF(i)定義節點i的每個相鄰節點的位置因子。具有坐標(xk,yk)的k∈Nb(i)具有殘余能量Erk，并且節點k距離目的地的Eucledian距離是Dk。

(3)

那么kth鄰居的LF(k)可以計算為:

(4)

(5)

next_nodei=max(LF(i))

(6)

其中:next_nodei是由節點i選擇的相鄰節點。

算法4:移動sink管理：

Loc_sinkx：任何節點x都存儲sink位置信息

B_x：如果任何標記為主干節點的節點x為真，初始化為false

sink_loc：sink的位置

Beacon：l_rf(BeaconReply,idx,Erx,idsink)；

?將BeaconReply包單播到sink

使用主干節點作為算法2中的骨干節點發送位置sink，匯聚節點轉發位置使用位置因子將包發送到節點z；

l_rf(Location,idsink,sink_loc,next_nodez)；

?位置包被單排到選定位置節點z。

節點y或sink向節點x發送以下數據包。

Lacation：

if (idx==next_nodey)then

if (Loc_sinkx≠sink_loc) then

Loc_sinkx←sink_loc

if (B_x==true) then

x將sink信息發送給它的CH。

else 選擇距離目標最近的節點z。

endif

else

丟棄包；

end if

else

丟棄包；

end if

一旦到達骨干節點的sink位置信息，就發送到其簇頭，然后該簇頭以相同的方式將其發送到其相鄰的簇頭，現在所有簇頭具有關于sink的新位置的信息。

1.5 sink位置恢復

Sink的位置信息在簇頭的幫助下到達常規節點，當常規節點想要傳輸數據時，它應該知道從集合區域內的簇頭獲得新sink的位置。它通過使用位置因子選擇相鄰節點來發送Locreq的包，并且該相鄰節點將請求包轉發到其最近的骨干節點。 一旦到達骨干節點，骨干節點就會將其轉發到其簇頭，簇頭已經有了新的sink的位置信息，因此簇頭將sink位置信息轉發到常規傳感器節點，如算法5所示。

算法5:sink位置恢復。

CH：具有sink位置

CHid：簇頭的id

Bx：如果任何節點是骨干節點，則為真

sink_Loc：Sink的位置

next_nodex：任何下一個節點都由任何節點x選擇轉發該數據包

reversex：簇頭x選擇節點將sink的位置發送到請求的節點

Locreq節點從節點y∈Nbr(x)接收數據包

Locreq:if (idx==next_nodey) then

reversex←idy；

if (Bx==true)

Bx將Locreq轉發給它的CH。

lr(Locreply,CHid,sink_locreversex)；

?響應請求的節點。

else

?節點x使用位置因子選擇next_nodex

lr(Locreq,idx,next_nodex)；

endif

else

丟棄包

endif

最后進行數據傳輸，在從骨干節點傳感器節點獲得有關sink位置的信息之后，借助于相鄰節點將數據轉發到sink。傳感器節點借助于位置因子，基于剩余能量和距離sink的最小距離來選擇相鄰節點。在接收數據時，相鄰節點使用相同的技術將其轉發到其鄰居，重復相同的過程直到數據到達sink。

2 仿真結果分析

為驗證本文CRRP協議有效性，將本文算法與現有其他算法進行比較，仿真實驗環境為MATLAB R2013b，基于表1中所示的參數來執行仿真實驗。

表1 仿真實驗參數

傳感器節點發送控制包以構建會聚區域并管理匯聚移動性，圖4中給出了不同協議的具有不同sink速度的控制包的平均能耗。將本文協議與現有其他協議進行比較，包括Rendezvous路由協議[17]，LBDD路由協議，Railroad路由協議和Ring路由協議。

圖4 控制數據包開銷

如圖所示，與其他協議相比，本文協議的控制包開銷非常少，少于其他協議，這是因為本文協議中，會合區域與源或sink之間的平均距離小于其他協議，且在本文協議中只有部分高層節點(即簇頭)參與到發送sink位置到源節點的主要任務中，而源節點通過建立有效的路由將數據發送到sink，這種方法將有助于降低能耗。而在LBDD中，內聯節點存儲來自源節點的數據，當該內聯節點收到查詢時，它會將數據發送到sink，這會導致控制數據包開銷增加。在RailRoad路由協議中，站點處的元數據存儲過程和從站點檢索sink位置的過程需要控制包交換。在Ring路由協議中，所有環節點都存儲sink的位置，隨著網絡操作的進行，它需要交換控制包來修復環，因此環長度增加，導致更多的能量消耗。Rendezvous路由協議在交會區域內保持樹來發送數據，控制包需要根據sink位置來設置鏈路。隨著速度的增加，導致控制數據包開銷增加。各種協議的每個節點的總能量消耗如圖5所示。

圖5 平均能耗

可以觀察到，由于更大的控制包開銷，LBDD的能量消耗最高，其存儲來自源節點的數據，并在會合區域中淹沒sink的查詢，隨著sink速度的增加，LBDD的能量消耗近似線性增長。Rendezvous協議不需要sink位置，但是平均路徑長度高于RailRoad協議，Ring路由協議總能量根據sink速度而增加。本文協議中，源和sink之間的平均距離幾乎與RailRoad和Ring路由協議相同，由于較少的控制包開銷，使得本文所提協議能耗少于現有其他協議。

每個節點的能量消耗和傳感器節點之間的不平衡負載影響網絡壽命，在圖6中給出了不同協議之間的網絡壽命性能，可以看出本文協議的網絡壽命大于其他協議的網絡壽命，原因是本文協議消耗更少的控制包，平衡傳感器節點之間的負載，并遵循用于數據傳輸的最佳路由。

圖6 網絡壽命

3 結論

在本文中，提出了一種基于簇的會合路由協議CRRP，其中在會合區域內構建簇以實現可擴展性并維持網絡負載，當傳感器節點想要將數據傳輸到sink時，從該會合區域獲取sink的位置信息，然后將數據發送到sink。所有骨干節點都不參與sink位置檢測，只有簇頭參與到發送sink位置到源節點的主要任務中，能夠使得WSN降低能耗和延長網絡壽命。將本文協議與現有LBDD協議、Ring Routing協議、RailRoad和Rendezvous協議進行比較，仿真實驗表明，本文協議在能耗和網絡壽命性能方面優于其他現有協議，表明本文方法的可行性與有效性。