基于柵格的傳感網多移動Sink數據收集方案

楊 瑞，沙 超，卞 遙，朱毅凱，王汝傳

(1.南京郵電大學 計算機學院、軟件學院、網絡空間安全學院，江蘇 南京 210003；2.南京大學 網絡信息中心，江蘇 南京 210023)

0 引 言

在傳統無線傳感網(wireless sensor networks，WSNs)中，Sink周圍的節點不僅需要感知其所覆蓋的區域，還要負責全網的數據傳輸，故生命期較短，易形成能量空洞[1]。“能量空洞現象”指的是由于部分節點失效而導致網絡原有覆蓋區域缺失或數據無法送達Sink的現象[2]。Lian等[3]指出，分布在Sink一跳范圍內的節點更易過早地耗盡自身能量，而在此情況下，網絡約有90%的初始能量還未被使用。因此，如何均衡節點的通信能耗，從而延長網絡生命期，成為該領域研究者面對的首要問題[4-5]。

路由優化機制是緩解無線傳感網能量空洞現象的主要方法[6]，但卻未能從根本上解決靜態Sink附近的節點負載過重的問題。而引入移動Sink，不僅可均衡節點能耗，也縮短了數據上傳的距離，降低了全網通信開銷[7]并可有效延長網絡生命期[8]。文獻[9]提出了面向能耗均衡的傳感網單移動Sink數據收集方法，利用網絡完全覆蓋模型，確定了Sink的各遍歷點坐標，并由此構建了其定長移動數據收集軌跡。Khan等[10]則設計了一種基于柵格的數據傳播機制-VGDD(virtual grid based data dissemination)，將網絡劃分成若干規模一致的柵格，并在各柵格中根據節點到柵格中心的距離選出一個簇頭。

在數據收集過程中，Sink以固定速度在以矩形網絡內切橢圓為軌跡的線路上移動，而全網節點則通過其簇頭及若干中繼，將數據多跳上傳至Sink。由于Sink的位置不斷變化，故在VGDD中，每個節點需實時獲取Sink的坐標，并由此重建數據上傳路徑。文獻[11]提出了一種基于虛擬節點優先級的移動Sink路徑選擇優化算法，以滿足時延約束和最小化網絡整體能耗為優化目標展開設計；而在早期的工作中[12]，提出了一種基于虛擬區域的數據采集方法-VRDG(virtual region based data gathering)，將網絡劃分為若干個由三個數據收集單元組成的虛擬片區，并在各片區中根據節點剩余能量及其與區域中心的距離選出遍歷點。

移動Sink以恒定速度訪問各遍歷點，而片區內的節點則構建了基于“最大前進距離”的數據上傳路徑，有效提升了數據收集效率。文獻[13]提出了一種基于多移動Sink的高效數據收集協議-EPBM(efficient data collection protocol based on multiple Sinks)，將網絡分為4個面積相等的子域，根據各子域內節點的覆蓋率及死亡率依次確定子域內Sink的移動軌跡和運動狀態。在數據收集過程中，僅有簇頭向移動Sink上傳數據，從而延長了網絡的生命期。

在上述研究的基礎上，文中設計并實現了一種基于柵格的無線傳感網數據收集方案-GBDG(grid based data gathering)。多個移動Sink在各柵格間分布式地開展數據收集，并根據各鄰居柵格當前狀態(節點數據收集總量、是否有數據溢出、柵格內節點剩余能量等)決定下一個遍歷點。不僅確保了數據收集的公平性和節點能耗的均衡性，同時也有效降低了數據收集時延。

1 網絡模型

不失一般性，令網絡為一個M×M的矩形區域，N個不可移動的節點在網絡中隨機部署。除移動Sink外，所有節點的初始能量均為E0。同文獻[10]類似，將網絡劃分為若干面積相等的柵格，如圖1所示。柵格總數Cnum由N決定，見式1。

Cnum=?N/50」2

(1)

故各柵格的邊長Cl可表示為：

(2)

圖1 劃分柵格及確定逗留點

由文獻[14]可知，當Sink位于網絡的中心位置時，網絡的通信總能耗最小。故令每個柵格的中心位置為移動Sink的逗留點，命名為C。在圖1中，逗留點間的虛線是移動Sink可能的移動軌跡。在后續數據收集過程中，各移動Sink將以恒定速度沿此虛線在柵格間移動。

目前，仍普遍采用經典的Heinzelman模型[15]作為無線傳感網的通信能耗計算依據，如式3～5所示。

(3)

Er=Eelec

(4)

(5)

其中，εfs為自由空間模型的功率放大能耗；εamp為功率放大電路的放大系數；Et和Er分別為發送和接收1比特數據包的能耗；d為節點間距；d0為參考距離。

于是，在簇樹狀的無線傳感網中，任一節點Si的生命期Lnode(Si)可由式6求得。

Lnode(Si)=

(6)

其中，E(Si)為Si的剩余能量；k為節點單位時間內產生的數據量；sub(Si)為Si子孫節點的數目。

2 算法描述

2.1 柵格內數據上傳路徑的構建

在GBDG中，柵格內的節點將數據上傳至移動Sink的方式，是決定其數據收集效率的關鍵。在各柵格內，以C點為根，分別建立數據收集樹，如圖2所示。首先，將C點一跳通信范圍內的所有節點作為其直接子節點(由于Sink僅在C點開展數據收集，故這些直接子節點也就是Sub_Sink節點)，即數據收集樹的第一層節點，如圖2中的S1、S2、S3。

圖2 數據收集樹的構建

柵格中，當前位于第k層的節點，將其鄰居中尚不在樹中的節點作為樹的第k+1層節點。第k+1層的節點，分別將距離自己最近的一個第k層節點作為父節點(圖2中節點S7選擇了距離其更近的S2作為父節點，而非S3)，隨后，繼續找尋第k+2層節點，直至柵格內的所有節點都加入數據收集樹為止。

2.2 相鄰柵格間中繼節點的選擇

當數據收集樹構建完成后，處于各柵格中的Sink便移動至其逗留點C，作為樹的根節點，開始數據收集。GBDG規定，在網絡開始運行時，多個Sink隨機部署在網絡中，但不允許同一柵格中同時存在一個以上的Sink。當Sink完成當前柵格的數據收集后，將移動至其所在柵格的鄰居柵格，繼續開展數據收集。鄰居柵格是指與當前柵格有共同邊的柵格。然而，對于一個柵格，其鄰居柵格不止一個，且各柵格的狀態(如當前是否有節點數據溢出、是否有移動Sink正在該柵格收集數據、柵格內的節點產生的數據量多少等)也不完全相同。故Sink需根據各鄰居柵格的狀態來決定在下一時刻向哪個柵格移動。為方便將鄰居柵格的狀態信息發送給移動Sink，需要為每個柵格選一個簇頭，該簇頭為距離逗留點最近的節點。然而，由于相鄰柵格間兩個逗留點的直線距離大于節點通信半徑，故需要在Sink和其相鄰柵格的簇頭間找尋適量的中繼節點，發送柵格的狀態信息。這里以圖1中的柵格A0和A1為例來說明該過程。

1．對于柵格A0和A1的所有節點，若其通信范圍與連接柵格A0和A1逗留點的虛線相交，則被選為準中繼節點。

2．在柵格A0和A1中，離逗留點最近的準中繼節點被選為該柵格內的第1個中繼節點。

3．對于柵格A0中所選出的第i個中繼節點Si，若有準中繼節點同時滿足以下兩個條件，則其成為第i+1個中繼節點。

(1)該準中繼節點在Si的通信范圍內。

(2)該準中繼節點到柵格A1的逗留點的直線距離小于Si到該逗留點的直線距離。

若滿足上述條件的準中繼節點不止一個，則按照式7計算其各自p值。p值最小者即為第i+1個中繼節點。

p=d(Si,Si-1)×vd(Si)

(7)

其中，d(Si,Si-1)指的是Si到Si-1的距離；vd(Si)指的是節點Si到虛線的垂直距離，如圖3所示。

圖3 中繼節點的選擇

柵格A0和A1同時執行上述操作，若兩邊的中繼節點能互相通信時，中繼節點選擇完畢。而當有中繼節點死亡時，也將按此方式重新選擇中繼。

2.3 柵格狀態的設定與鄰居柵格的選擇

當中繼節點選出后，收集完數據的移動Sink便開始通過這些中繼向其鄰居柵格的簇頭發送查詢消息。收到查詢消息的簇頭，將其所在柵格的信息反饋給發出查詢的Sink。這些信息包括：

(1)該柵格內所有節點目前尚未上傳的數據總量；

(2)該柵格內是否有節點的緩存已經溢出；

(3)該柵格內是否有移動Sink；

(4)是否有其他移動Sink正準備向該柵格移動。

收到反饋的移動Sink根據以上信息確定鄰居柵格的狀態，具體方法為：

(1)當柵格中有節點緩存溢出時，將此柵格標記為黑色；

(2)當柵格中有節點所緩存的數據量大于dv時，將其標記為灰色，否則，將其標記為白色。dv的計算見式8。

(8)

其中，U為該柵格內所有節點組成的集合；cache(Si)為節點Si所能存儲數據量的最大值；v為Sink的移動速度。

于是，移動Sink將根據當前鄰居柵格狀態，來決定下一次移往的柵格。

(1)定義所有鄰居柵格組成的集合為Une，所有黑色狀態的鄰居柵格組成的集合為Bne，所有灰色狀態的鄰居柵格組成的集合為Gne，所有白色狀態的鄰居柵格組成的集合為Wne。

(2)若鄰居柵格中存在其他Sink或已有其他移動Sink正在向其移動時，則該鄰居柵格不作為目標柵格的考量。設這樣的柵格組成的集合為Nne。

(3)令target=Bne∩(Une-Nne)，若size(target)>0，轉步驟6。

(4)令target=Gne∩(Une-Nne)，若size(target)>0，轉步驟6。

(5)令target=Wne∩(Une-Nne)。

(6)若size(target)=1，則集合target內所包含的那個柵格作為Sink的下一個移動柵格；否則，對于集合target內每一個柵格Aj，計算其Pj值，Pj值最大的柵格作為下一個移動柵格。

(9)

其中，size(target)表示集合target中元素的個數；Ti表示當前時間與節點i上次傳輸數據給Sink的時間差；ds(i)表示節點i當前緩存的數據量。

3 實驗結果與分析

為了驗證GBDG的性能，分別在網絡生命期、平均通信能耗、數據收集延遲、數據傳輸成功率等方面與VRDG、VGDD進行比較。如無特殊說明，網內節點總數和節點通信半徑，將分別設為200個和20 m，網絡規模為200 m×200 m，移動Sink的移動速度為5 m/s。

圖4是三種算法在數據收集延遲方面的性能對比。這里將數據收集延遲定義為移動Sink完成一輪數據收集的時間。在VRDG中，Sink的移動軌跡是固定的，由所有片區的簇頭連接而成。移動Sink需遍歷完所有簇頭，才能完成一次數據收集，故其數據收集延遲要高于GBDG。而在VGDD中，Sink的移動軌跡是矩形的內切橢圓，其長度同樣是定值，故其數據收集延遲僅與網絡規模有關。在該實驗中，網絡邊長為200 m，因此，VGDD的移動軌跡長度長于GBDG，即其數據收集延遲高于GBDG。此外，由于GBDG利用了多個移動Sink開展數據收集，且每個柵格在一輪數據收集過程中，最多只會被一個Sink訪問，從而大大降低了數據收集節點等待上傳的時間。

圖4 數據收集延遲

圖5是數據傳輸成功率的實驗結果。

圖5 數據傳輸成功率

與GBDG相比，VGDD在數據傳輸成功率方面具備一定優勢。因為其片區中的簇頭無需長時間緩存數據，只要確定了移動Sink的位置，柵格便可通過網絡內的其他簇頭，建立到達移動Sink的多跳數據上傳路徑。然而，這樣將增大網絡的通信開銷。而在VRDG中，片區數量較多，且Sink必須按序移動至各片區開展數據收集，易造成部分節點因等待Sink的時間過長而產生緩存溢出。因此，其數據傳輸成功率較低。

圖6是三種算法的網絡生命期對比。

圖6 網絡生命期

GBDG由于采用了多個移動Sink開展數據收集，且充分考慮了鄰居柵格的狀態，故其能耗均衡性較好，網絡生命期最長。此外，與VGDD和VRDG不同，GBDG的網絡生命期并非隨節點的通信半徑的增大而降低。這是由于隨著節點通信半徑的增大，GBDG中與移動Sink直接通信的節點數量也隨之增加，使得每個節點的子孫節點的數量減少，各節點的平均負載也因此降低，從而延長了網絡生命期。

4 結束語

利用多個移動Sink分布式地在各柵格間開展數據收集。重點實現了基于不同柵格狀態的多Sink移動方案的設計。不僅提升了無線傳感網的數據收集效率，也有效降低了延遲，延長了網絡生命期。

然而，在實際應用中，移動Sink自身的能量和存儲空間并非無限。如何在該約束下，進一步優化多Sink的移動路徑以及更好地實現多Sink間的協同，將是下一步的研究方向。