采用虛擬網(wǎng)格的格頭連通的WSNs路由算法

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

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

0 引 言

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

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

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

1 網(wǎng)絡(luò)模型

每個(gè)節(jié)點(diǎn)利用自己的全球定位系統(tǒng)(global positioning

system,GPS)位置坐標(biāo)估計(jì)自己的GID。假定節(jié)點(diǎn)i的位置坐標(biāo)(X,Y)，則其GID可依式(1)計(jì)算

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

(1)

式中 (gi,gj)為網(wǎng)格編號(hào)。

圖1 網(wǎng)格模型

2 VGCR

VGCR利用虛擬網(wǎng)格傳輸數(shù)據(jù)。先在網(wǎng)格內(nèi)產(chǎn)生一個(gè)格頭(grid head, GH)，再?gòu)亩鄠€(gè)GH內(nèi)選擇部分GH組建數(shù)據(jù)傳輸路徑。如圖2所示。

圖2 數(shù)據(jù)傳輸示意

2.1 GH的選擇

最初，每個(gè)網(wǎng)格內(nèi)產(chǎn)生一個(gè)GH。每個(gè)節(jié)點(diǎn)隨機(jī)設(shè)置一個(gè)定時(shí)器[13]。最先定時(shí)完畢的節(jié)點(diǎn)成為GH，并向其他節(jié)點(diǎn)發(fā)出通告。收到這些通告的節(jié)點(diǎn)，就不參與路由。

此外，每個(gè)GH具有活動(dòng)和休眠2個(gè)模式。最初，在無(wú)線信道的預(yù)定時(shí)間間隔內(nèi)t，每個(gè)格頭先求gx和gy之和，然后判斷這個(gè)和是否為偶數(shù)，如果是偶數(shù)，則此GH進(jìn)入活動(dòng)模式(GH_MODE=1),反之，和為奇數(shù)的GH就進(jìn)入休眠狀態(tài)(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所示，每個(gè)網(wǎng)格內(nèi)有一個(gè)GH，并且只有部分GH為激活狀態(tài)。

圖3 格頭選擇示意

2.2 信宿檢測(cè)

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

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

圖4 產(chǎn)生LGH的信息交互過(guò)程

然后，LGH廣播Sink_Detection包。收到Sink_Detection包的GH就將LGH作為連通信宿路徑的下一跳節(jié)點(diǎn)。4個(gè)鄰近的GH再重播Sink_Detection，然后，再以同樣的方式選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。致使，所有活動(dòng)狀態(tài)的GH能夠共享連通信宿的路由路徑。

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

一旦傳感節(jié)點(diǎn)檢測(cè)到目標(biāo)事件，其即感測(cè)數(shù)據(jù)，然后成為源節(jié)點(diǎn)，并傳輸數(shù)據(jù)。首先，廣播META_DATA數(shù)據(jù)包。一旦接收META_DATA包，格頭就回復(fù)META_DATA_ACK包。如果回復(fù)META_DATA_ACK包的是LGH，則源節(jié)點(diǎn)就直接將感測(cè)數(shù)據(jù)傳輸至LGH；否則，將感測(cè)數(shù)據(jù)傳輸至第一個(gè)回復(fù)META_DATA_ACK的GH，再由GH選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，依次類推，直至數(shù)據(jù)包傳輸至信宿。

2.4 對(duì)信宿移動(dòng)的處理

由于信宿不斷移動(dòng)，需頻繁地更新LGH。因此，信宿通過(guò)周期地廣播Sink_Location包，告知自己的位置[16]。而當(dāng)前的LGH可能是處于活動(dòng)狀態(tài)或休眠狀態(tài)。因此，當(dāng)信宿收到的Beacon包不是來(lái)自當(dāng)前的LGH，說(shuō)明當(dāng)前的LGH是處于休眠狀態(tài)[17]。為此，信宿必須從當(dāng)前處于活動(dòng)狀態(tài)的GH中選擇一個(gè)GH作為L(zhǎng)GH。

據(jù)此，信宿向鄰近的GH發(fā)送ACK包，第一個(gè)接收此ACK包的GH宣稱自己為新的LGH。新的LGH再?gòu)V播Sink_Location包。鄰近的GH收到Sink_Location包后，就此發(fā)送節(jié)點(diǎn)(新的LGH)與原來(lái)的LGH進(jìn)行比較。如果不是同一個(gè)節(jié)點(diǎn)，就將新的LGH作為自己的下一跳節(jié)點(diǎn)，否則丟棄Sink_Location包。

2.5 GH模式的切換

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

經(jīng)一段時(shí)間后，每個(gè)GH判斷自己是否在當(dāng)前LGH的鄰近網(wǎng)格內(nèi)。如果不在，則表明信宿已遠(yuǎn)離自己，此階段可以進(jìn)入休眠狀態(tài)。如果在的話，自己就需進(jìn)入活動(dòng)狀態(tài)。

對(duì)于第iGHGHi,如果滿足式(2)，則進(jìn)入活動(dòng)狀態(tài)，否則就進(jìn)入休眠狀態(tài)

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個(gè)網(wǎng)格內(nèi)的GH需要保持活動(dòng)狀態(tài)。

圖5 GH模式切換示例

3 性能仿真與分析

3.1 仿真環(huán)境

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

3.2 網(wǎng)絡(luò)壽命

本文用活動(dòng)節(jié)點(diǎn)數(shù)表征網(wǎng)絡(luò)壽命。在同一個(gè)時(shí)間點(diǎn)，活動(dòng)節(jié)點(diǎn)數(shù)越多，說(shuō)明網(wǎng)絡(luò)壽命越長(zhǎng)，實(shí)驗(yàn)數(shù)據(jù)如圖6(a)所示?？芍?，VGCR協(xié)議的活動(dòng)節(jié)點(diǎn)數(shù)優(yōu)于EAGER協(xié)議。這主要是因?yàn)椋篤GCR協(xié)議利用部分格頭傳輸數(shù)據(jù)，并實(shí)時(shí)地切換GH模式，通過(guò)休眠，保存?zhèn)鞲泄?jié)點(diǎn)能量。此外，可知，隨著仿真時(shí)間的推移，VGCR協(xié)議在活動(dòng)節(jié)點(diǎn)數(shù)的優(yōu)勢(shì)更為明顯。例如:當(dāng)仿真時(shí)間為100 s時(shí)，VGCR協(xié)議的活動(dòng)節(jié)點(diǎn)數(shù)近200，EAGER協(xié)議的活動(dòng)節(jié)點(diǎn)數(shù)近196。而當(dāng)仿真時(shí)間到達(dá)300 s時(shí)，VGCR協(xié)議的活動(dòng)節(jié)點(diǎn)數(shù)達(dá)到195，而EAGER協(xié)議的活動(dòng)節(jié)點(diǎn)數(shù)減少至185。

3.3 數(shù)據(jù)包傳遞率

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

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

3.4 端到端傳輸時(shí)延

端到端傳輸時(shí)延是指數(shù)據(jù)包從源節(jié)點(diǎn)至信實(shí)宿接收時(shí)的時(shí)間，實(shí)驗(yàn)數(shù)據(jù)如圖6(c)所示。

圖6 仿真結(jié)果

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

4 結(jié) 論

針對(duì)WSNs的節(jié)點(diǎn)能效問(wèn)題，提出基于虛擬網(wǎng)格的GH連通路由VGCR。將網(wǎng)絡(luò)劃分為多個(gè)網(wǎng)格，并且每個(gè)網(wǎng)格產(chǎn)生一個(gè)GH，最后由GH構(gòu)建數(shù)據(jù)傳輸?shù)耐?。而GH由活動(dòng)和休眠兩種狀態(tài)，且可自適應(yīng)地切換，進(jìn)而保存了GH的能量。同時(shí)，VGCR規(guī)定只有GH參與路由，使得只有網(wǎng)絡(luò)內(nèi)的部分節(jié)點(diǎn)參與了路由。通過(guò)這種機(jī)制，緩解網(wǎng)絡(luò)能耗。實(shí)驗(yàn)數(shù)據(jù)表明：提出的VGCR路由提高了能量利用率，延長(zhǎng)了網(wǎng)絡(luò)壽命。