采用虛擬網格的格頭連通的WSNs路由算法

丁 凰， 繆相林， 周建龍， 何緋娟

(1.西安交通大學城市學院,計算機系,陜西 西安 710018；2.西安交通大學 計算機學院,陜西 西安 710049)

0 引 言

無線傳感器網絡(wireless sensor networks,WSNs)為分布式網絡[1]，其由多個微型具有感測能量的傳感節點組成。通過這些傳感節點感測環境數據，如溫度、濕度等，然后將這些感測數據傳輸至信宿。 然而這些傳感節點存在如電池能量和數據處理能力受限等不足[2～3]。由于傳感節點經常部署于惡劣環境，給傳感節點替換電池成為不可能。因此，充分利用電池的有限能量是WSNs必需解決的問題。

由于傳輸數據消耗了傳感節點的大部分能量，可利用有效的路由算法平衡節點間能耗，進而保存節點能量。目前，研究人員已提出多類的路由，如基于簇類路由[4]、網格路由[5～7]、區域路由[8～10]等。這些協議能夠降低節點能耗速度，但其在選擇路由時，并沒有充分考慮到信宿的移動性，同時也并沒有充分利用節點的休眠機制[11，12]。

本文提出基于虛擬網格的格頭連通路由(virtual grid head-based grid head connected routing,VGCR)。先將網絡劃分為虛擬網格，并在每個網格內產生一個節點作為格頭，由格頭組建數據包傳輸路徑。此外，每個格頭設有休眠和活動兩種狀態。VGCR路由考慮到信宿的移動問題，引用信宿局部格頭概念。實驗數據表明，提出的VGCR路由有效地保存能量，并提高了數據傳輸率。

1 網絡模型

每個節點利用自己的全球定位系統(global positioning

system,GPS)位置坐標估計自己的GID。假定節點i的位置坐標(X,Y)，則其GID可依式(1)計算

GID(X,Y)={(gi,gj)|gi=[X/l],gj=[Y/l]

(1)

式中 (gi,gj)為網格編號。

圖1 網格模型

2 VGCR

VGCR利用虛擬網格傳輸數據。先在網格內產生一個格頭(grid head, GH)，再從多個GH內選擇部分GH組建數據傳輸路徑。如圖2所示。

圖2 數據傳輸示意

2.1 GH的選擇

最初，每個網格內產生一個GH。每個節點隨機設置一個定時器[13]。最先定時完畢的節點成為GH，并向其他節點發出通告。收到這些通告的節點，就不參與路由。

此外，每個GH具有活動和休眠2個模式。最初，在無線信道的預定時間間隔內t，每個格頭先求gx和gy之和，然后判斷這個和是否為偶數，如果是偶數，則此GH進入活動模式(GH_MODE=1),反之，和為奇數的GH就進入休眠狀態(GH_MODE=0)。模式切換算法的偽代碼如下:

Mode Setting of GH

gridx:xco-ordinate of the grid of the GH

gridy:yco-ordinate of the grid of the GH

GH_MoDe:A GH node operation either active(1)

or sleep mode(0)

t:timer associated with each GH for mode change

for(each GH)

if ((gridx+gridy)mod 2==0)

GH_MODE←1

else

GH_MODE←0

end if

end for

如圖3所示，每個網格內有一個GH，并且只有部分GH為激活狀態。

圖3 格頭選擇示意

2.2 信宿檢測

在WSNs中，節點一旦感測到數據，即向信宿傳輸數據。由于信宿是移動的，節點需要檢測信宿的位置[14，15]。信宿周期地廣播Sink_Location包，其包含了自己的gx和gy。一旦接收到Sink_Location包，GH就向信宿回復Beacon包，其也包含GH的gx和gy。信宿接收Beacon包后，即檢測并判斷它們是否在同一個網格內，如果在同一個網格內，信宿即向格頭傳輸ACK消息。

一旦收到ACK，GH即將自己作為連通信宿的下一跳節點，并成為信宿局部GH(local gh,LGH)。一旦選舉了LGH，信宿就丟掉來自鄰近GH所發送的Beacon消息。產生LGH的信息交互過程如圖4所示。

圖4 產生LGH的信息交互過程

然后，LGH廣播Sink_Detection包。收到Sink_Detection包的GH就將LGH作為連通信宿路徑的下一跳節點。4個鄰近的GH再重播Sink_Detection，然后，再以同樣的方式選擇下一跳轉發節點。致使，所有活動狀態的GH能夠共享連通信宿的路由路徑。

2.3 數據傳輸

一旦傳感節點檢測到目標事件，其即感測數據，然后成為源節點，并傳輸數據。首先，廣播META_DATA數據包。一旦接收META_DATA包，格頭就回復META_DATA_ACK包。如果回復META_DATA_ACK包的是LGH，則源節點就直接將感測數據傳輸至LGH；否則，將感測數據傳輸至第一個回復META_DATA_ACK的GH，再由GH選擇下一跳轉發節點，依次類推，直至數據包傳輸至信宿。

2.4 對信宿移動的處理

由于信宿不斷移動，需頻繁地更新LGH。因此，信宿通過周期地廣播Sink_Location包，告知自己的位置[16]。而當前的LGH可能是處于活動狀態或休眠狀態。因此，當信宿收到的Beacon包不是來自當前的LGH，說明當前的LGH是處于休眠狀態[17]。為此，信宿必須從當前處于活動狀態的GH中選擇一個GH作為LGH。

據此，信宿向鄰近的GH發送ACK包，第一個接收此ACK包的GH宣稱自己為新的LGH。新的LGH再廣播Sink_Location包。鄰近的GH收到Sink_Location包后，就此發送節點(新的LGH)與原來的LGH進行比較。如果不是同一個節點，就將新的LGH作為自己的下一跳節點，否則丟棄Sink_Location包。

2.5 GH模式的切換

最初，VGCR算法是利用所有虛擬網格數之和的奇偶性決定此GH的模式(活動或休眠)。當執行一段時間(t)后，就必須依據信宿的位置進行模式切換。通過切換GH模式，平衡網絡能耗。

經一段時間后，每個GH判斷自己是否在當前LGH的鄰近網格內。如果不在，則表明信宿已遠離自己，此階段可以進入休眠狀態。如果在的話，自己就需進入活動狀態。

對于第iGHGHi,如果滿足式(2)，則進入活動狀態，否則就進入休眠狀態

if((GHi→gx==x-1&&GHi→gy==y-1)‖

(GHi→gx==x-1&&GHi→gy==y+1)‖

(GHi→gx==x+1&&GHi→gy==y+1))‖

(GHi→gx==x1+1&&GHi→gy==y-1))

(2)

式中x=LGH→gx,y=LGH→gy。以圖5為例，位于LGH的鄰近4個網格內的GH需要保持活動狀態。

圖5 GH模式切換示例

3 性能仿真與分析

3.1 仿真環境

利用Castalia軟件器建立仿真平臺?？紤]的網絡區域，傳感節點數為200個。信宿移動速度在5，10，15，20，25 m/s變化。信宿依據高斯移動模型移動。節點的初始能量為10 J。仿真時間為120 s。每次實驗獨立仿真100次，取平均值作為最終實驗數據。 為了更好地分析VGCR協議性能，選擇EAGER路由[18]作為比較，并重點考查網絡壽命、數據包傳遞率、端到端傳輸時延和平均能耗的性能,仿真結果如圖6。

3.2 網絡壽命

本文用活動節點數表征網絡壽命。在同一個時間點，活動節點數越多，說明網絡壽命越長，實驗數據如圖6(a)所示?？芍?，VGCR協議的活動節點數優于EAGER協議。這主要是因為：VGCR協議利用部分格頭傳輸數據，并實時地切換GH模式，通過休眠，保存傳感節點能量。此外，可知，隨著仿真時間的推移，VGCR協議在活動節點數的優勢更為明顯。例如:當仿真時間為100 s時，VGCR協議的活動節點數近200，EAGER協議的活動節點數近196。而當仿真時間到達300 s時，VGCR協議的活動節點數達到195，而EAGER協議的活動節點數減少至185。

3.3 數據包傳遞率

兩個協議的數據包傳遞率隨信宿移動速度的變化情況，如圖6(b)所示，其中數據包傳遞率表示信宿成功接收的數據包占總的數據包的比例。

可知，數據包傳遞率隨信宿移動速度的增加而下降。原因在于：信宿移動越快，信宿的網格和LGH也變化越快，這增加了源節點至信宿的跳數，必然降低了數據包傳遞率。與EAGER協議相比，提出的VGCR協議的數據包傳遞率得到一定的提高。

3.4 端到端傳輸時延

端到端傳輸時延是指數據包從源節點至信實宿接收時的時間，實驗數據如圖6(c)所示。

圖6 仿真結果

可知，端到端傳輸時延隨信宿移動速度的增加而下降。原因在于：信宿快速移動，增加了其尋找最短路徑的概率，必然降低了端到端傳輸時延。然而，當移動速度逐漸增加后，端到端傳輸時延的下降也逐漸變緩。

4 結 論

針對WSNs的節點能效問題，提出基于虛擬網格的GH連通路由VGCR。將網絡劃分為多個網格，并且每個網格產生一個GH，最后由GH構建數據傳輸的通路。而GH由活動和休眠兩種狀態，且可自適應地切換，進而保存了GH的能量。同時，VGCR規定只有GH參與路由，使得只有網絡內的部分節點參與了路由。通過這種機制，緩解網絡能耗。實驗數據表明：提出的VGCR路由提高了能量利用率，延長了網絡壽命。