無(wú)線傳感網(wǎng)絡(luò)中轉(zhuǎn)發(fā)節(jié)點(diǎn)優(yōu)化的多跳路由

丁 凰，繆相林，王 梅，張 媛

（1. 西安交通大學(xué) 城市學(xué)院，西安 710018；2. 西安交通大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，西安 710049）

0 引言

隨著電子通信技術(shù)的發(fā)展，無(wú)線傳感網(wǎng)絡(luò)(wireless sensor networks， WSNs)已廣泛應(yīng)用于環(huán)境監(jiān)測(cè)[1-2]，如植物監(jiān)測(cè)、海洋環(huán)境勘察、災(zāi)難預(yù)測(cè)等。先利用WSNs 內(nèi)的節(jié)點(diǎn)感測(cè)環(huán)境數(shù)據(jù)，再將數(shù)據(jù)傳輸?shù)叫潘?，進(jìn)而實(shí)現(xiàn)對(duì)環(huán)境監(jiān)測(cè)的目的。

然而，由于WSNs 網(wǎng)絡(luò)結(jié)構(gòu)較大，數(shù)據(jù)須多跳路由才能到達(dá)信宿， 即需要多個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)才能將數(shù)據(jù)傳輸?shù)叫潘蓿@就需要有效的轉(zhuǎn)發(fā)機(jī)制。考慮到節(jié)點(diǎn)能量屬有限能量[3]， 一旦節(jié)點(diǎn)能量消耗盡，節(jié)點(diǎn)就無(wú)法工作。因此，在設(shè)計(jì)轉(zhuǎn)發(fā)機(jī)制時(shí)，必須考慮到節(jié)點(diǎn)的能耗問(wèn)題。

地理位置路由只須依據(jù)節(jié)點(diǎn)位置傳輸數(shù)據(jù)包，無(wú)須維護(hù)節(jié)點(diǎn)路由表，減少了節(jié)點(diǎn)系統(tǒng)開(kāi)銷(xiāo)，因此，地理位置路由受到廣泛關(guān)注[4]。但是，目前多數(shù)地理位置路由只考慮了2 維平面，并基于2 維平面的節(jié)點(diǎn)位置選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)。而真實(shí)的網(wǎng)絡(luò)，如水下 傳感網(wǎng)絡(luò)，節(jié)點(diǎn)是處于3 維平面的。

此外，由于采用貪婪轉(zhuǎn)發(fā)策略，地理位置路由還存在路由空洞問(wèn)題[5]。文獻(xiàn)[6]針對(duì)路由空洞問(wèn)題提出了解決方案，但它只在2 維平面有效，無(wú)法應(yīng)用于3 維平面[7]。

文獻(xiàn)[8]結(jié)合了貪婪轉(zhuǎn)發(fā)和角度轉(zhuǎn)發(fā)機(jī)制，提出 角 度 路 由 協(xié) 議(angular routing protocol， ARP)， 當(dāng)節(jié)點(diǎn)遭遇路由空洞時(shí)，就依據(jù)最小角度迂回?cái)?shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)。文獻(xiàn)[9]提出空洞處理路由(a void handing routing， AVHR)策略，其采用3 維貪婪角度機(jī)制傳輸數(shù)據(jù)包，并具有數(shù)據(jù)包跟蹤功能。文獻(xiàn)[10]針對(duì)3 維WSNs 提出實(shí)時(shí)的地理位置路由(real-time geographical routing， RTGR)，并引用自適應(yīng)數(shù)據(jù)轉(zhuǎn)發(fā)區(qū)域，致使只有在該區(qū)域內(nèi)的數(shù)據(jù)包才能被接收。

然而，這些協(xié)議沒(méi)有考慮到能耗問(wèn)題來(lái)選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)，仍是沿用貪婪轉(zhuǎn)發(fā)機(jī)制。為此，本文提出基于能效角度路由(energy efficient angle based routing， EEAR)，先依據(jù)角度信息選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)集，然后再依據(jù)距離和能量信息，選擇從轉(zhuǎn)發(fā)節(jié)點(diǎn)集中擇優(yōu)選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)。若遭遇路由空洞時(shí)，調(diào)整角度，擴(kuò)大選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)的區(qū)域。仿真結(jié)果表明，提出的EEAR 路由能有效地提高數(shù)據(jù)包傳遞率，減少能耗。

1 EEAR 路由

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

假定網(wǎng)絡(luò)由n 個(gè)同構(gòu)的傳感節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)擁有自己和信宿的3 維位置信息。網(wǎng)絡(luò)的3 維空間的拓?fù)湫畔橐阎畔?，每個(gè)節(jié)點(diǎn)的傳輸半徑為R，最初給每個(gè)節(jié)點(diǎn)設(shè)定1 個(gè)初始的錐角α ，并利用錐角α 選擇向信宿傳輸數(shù)據(jù)包的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。

當(dāng)源節(jié)點(diǎn)需要傳輸數(shù)據(jù)包時(shí)，先設(shè)置數(shù)據(jù)包的首部，包括發(fā)送節(jié)點(diǎn)標(biāo)識(shí)符(identifier， ID)，發(fā)送節(jié)點(diǎn)坐標(biāo)、錐角α 和數(shù)據(jù)包壽命。由于每個(gè)節(jié)點(diǎn)均知道信宿的位置信息，數(shù)據(jù)包首部無(wú)需嵌入信宿位置信息。

每個(gè)節(jié)點(diǎn)維持2 個(gè)隊(duì)列：已發(fā)的隊(duì)列(resend queue， RQ)和 已 傳 輸 的 隊(duì) 列(transmitted queue， TQ)。RQ 表示源節(jié)點(diǎn)已傳輸且下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)還未轉(zhuǎn)發(fā)的數(shù)據(jù)包[11]，TQ 表示源節(jié)點(diǎn)已傳輸且下一跳轉(zhuǎn)發(fā)也成功轉(zhuǎn)發(fā)的數(shù)據(jù)包。每個(gè)節(jié)點(diǎn)周期地更新RQ 和TQ。

當(dāng)節(jié)點(diǎn)發(fā)送了1 個(gè)數(shù)據(jù)包Data，最初節(jié)點(diǎn)就保存它的復(fù)本，并將復(fù)本保存于RQ。若節(jié)點(diǎn)監(jiān)聽(tīng)到下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)已轉(zhuǎn)發(fā)了Data，就將Data 從RQ中刪除，并將Data 加入TQ。

1.2 初始錐角α

初始錐角α 對(duì)選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)有重要影響，須慎重計(jì)算。如果所有節(jié)點(diǎn)的錐形傳輸區(qū)域等于整個(gè)區(qū)域，錐角包含1 個(gè)節(jié)點(diǎn)，則網(wǎng)絡(luò)的整個(gè)錐形體積cV 為

令V 表示整個(gè)網(wǎng)絡(luò)區(qū)域的體積，m 表示可選擇的節(jié)點(diǎn)數(shù)。由于所有節(jié)點(diǎn)的錐形區(qū)域等于整個(gè)網(wǎng)絡(luò)的區(qū)域，因此， mV = nVc。據(jù)此得出初始錐角α 的計(jì)算公式為

1.3 候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集

假定節(jié)點(diǎn)i 為源節(jié)點(diǎn)，其需要傳輸它的數(shù)據(jù)包為Datai。最初，節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播Datai，一旦鄰居節(jié)點(diǎn) j ∈ Ni收到數(shù)據(jù)包Datai，鄰居節(jié)點(diǎn)j 就從Datai的首部提取源節(jié)點(diǎn)的位置信息。再計(jì)算轉(zhuǎn)發(fā)角度

圖1 計(jì)算轉(zhuǎn)發(fā)角示意圖

鄰居節(jié)點(diǎn)j 一旦計(jì)算了轉(zhuǎn)發(fā)角 jθ ，就將 jθ 與錐角α 進(jìn)行比較。若 jθ 小于α ，鄰居節(jié)點(diǎn)j 就可加入候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集 iψ ，即

1.4 下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)

在密集型網(wǎng)絡(luò)區(qū)域內(nèi)[12]，轉(zhuǎn)發(fā)節(jié)點(diǎn)集 iψ 內(nèi)可能有多個(gè)節(jié)點(diǎn)，若 iψ 存在多個(gè)節(jié)點(diǎn)，就再?gòu)闹袚駜?yōu)轉(zhuǎn)發(fā)節(jié)點(diǎn)。

為了更好地選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)，EEAR 路由考慮節(jié)點(diǎn)能量和距離信息，從轉(zhuǎn)發(fā)節(jié)點(diǎn)集 iψ 中產(chǎn)生1 個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)，并由此節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。令 jW 表示節(jié)點(diǎn)j 融合了剩余能量和距離信息的權(quán)重，其定義為

計(jì)算 iψ 內(nèi)的節(jié)點(diǎn)權(quán)重值后，再依權(quán)重設(shè)置定時(shí)器。權(quán)重值越大，定時(shí)時(shí)間越短。一旦定時(shí)完畢，且未監(jiān)聽(tīng)到節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包，就立即轉(zhuǎn)發(fā)數(shù)據(jù)包。令 jT 表示節(jié)點(diǎn)j 的定時(shí)時(shí)間，即

圖2 轉(zhuǎn)發(fā)數(shù)據(jù)流程

1.5 路由空洞的處理

在節(jié)點(diǎn)稀疏環(huán)境，可能會(huì)出現(xiàn) iψ 內(nèi)沒(méi)有節(jié)點(diǎn)，即 iψ φ= ，這說(shuō)明源節(jié)點(diǎn)i 遭遇路由空洞，在這種情況下，就調(diào)整錐角α ，調(diào)整的步長(zhǎng)為 1α ，即α = α0+ α1， α0為初始錐角，如圖3 所示。 每次調(diào)整后，判斷 iψ 內(nèi)是否為空。若為空，繼續(xù)調(diào)整。

圖3 初始錐角α 的調(diào)整

2 實(shí)驗(yàn)與結(jié)果分析

2.1 仿真實(shí)驗(yàn)環(huán)境

為了更好地分析EEAR 路由性能，利用面向?qū)ο蟮哪K化離散事件仿真工具(objective modular network testbed in C++，OMNET++)軟件建立仿真實(shí)驗(yàn)平臺(tái)[13]，OMNET++可以用來(lái)仿真任何離散事件系統(tǒng)。圖4 顯示了OMNET++運(yùn)行的內(nèi)部結(jié)構(gòu)，主要由用戶接口、模型元件庫(kù)、仿真模型等組成，其中仿真模型包含一些常用的網(wǎng)絡(luò)協(xié)議、通信模型。

圖4 OMNET++運(yùn)行內(nèi)部結(jié)構(gòu)

在300 m × 300 m × 300 m區(qū) 域 隨 機(jī) 部 署 100～ 500 個(gè)節(jié)點(diǎn)和1 個(gè)信宿， 其中信宿位于區(qū)域中心，8 個(gè)源節(jié)點(diǎn)位于網(wǎng)絡(luò)區(qū)域的8 個(gè)角落。所有節(jié)點(diǎn)的初始能量為5 J。引用IEEE 802.11 標(biāo)準(zhǔn)作為介質(zhì)訪問(wèn)控制(medium access control， MAC)協(xié)議。具體的仿真參數(shù)如表1 所示。

表1 仿真參數(shù)

選擇RTGR、AVHR 作為參照，并與EEAR 路由進(jìn)行性能對(duì)比分析，主要分析數(shù)據(jù)包傳遞率、剩余能量和流量。每次實(shí)驗(yàn)獨(dú)立重復(fù)10 次，取平均值作為最終的實(shí)驗(yàn)數(shù)據(jù)。

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

網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)數(shù)對(duì)數(shù)據(jù)包傳遞率的影響，如圖5所示。其中數(shù)據(jù)包傳遞率等于信宿成功接收的數(shù)據(jù)包數(shù)與源節(jié)點(diǎn)總共傳輸?shù)臄?shù)據(jù)包之比。數(shù)據(jù)包傳遞率越高，數(shù)據(jù)傳輸效率就越高，性能越好。

圖5 數(shù)據(jù)包傳遞率

從圖5 可知，當(dāng)節(jié)點(diǎn)數(shù)為100 時(shí)，數(shù)據(jù)包傳遞率越低。原因在于：100 個(gè)節(jié)點(diǎn)無(wú)法形成連通網(wǎng)絡(luò)，網(wǎng)絡(luò)處于斷裂狀態(tài)，只有極少的數(shù)據(jù)包能夠成功傳輸至信宿。

隨著節(jié)點(diǎn)數(shù)的增加，數(shù)據(jù)包傳遞率快速上升，當(dāng)節(jié)點(diǎn)數(shù)增加至300 時(shí)，EEAR 路由的數(shù)據(jù)包傳遞率達(dá)到100%。但是，RTGR 和AVHR 路由的數(shù)據(jù)包并沒(méi)有達(dá)到100%。這也說(shuō)明，EEAR 路由的數(shù)據(jù)包傳遞率的性能優(yōu)于RTGR 和AVHR 路由。

2.3 能耗

用節(jié)點(diǎn)平均剩余能量率作為表征網(wǎng)絡(luò)能耗的性能指標(biāo)，節(jié)點(diǎn)平均剩余能量率等于節(jié)點(diǎn)的剩余能量與初始能量之比的平均值。節(jié)點(diǎn)平均剩余能量率越高，網(wǎng)絡(luò)壽命越長(zhǎng)，而傳輸數(shù)據(jù)和接收數(shù)據(jù)消耗了節(jié)點(diǎn)大部分能量。

圖6 顯示了3 個(gè)路由的節(jié)點(diǎn)平均剩余能量率。

圖6 節(jié)點(diǎn)平均剩余能量率

從圖6 可知，EEAR 和AVHR 路由消耗了更少的能量，而RTGR 路由能量消耗速度過(guò)快，原因在于：RTGR 路由產(chǎn)生了太多冗余數(shù)據(jù)包，而EEAR路由通過(guò)選擇最優(yōu)的下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)，減少路由重傳次數(shù)，降低節(jié)點(diǎn)的能耗。

2.4 流量

流量是指在仿真過(guò)程中所傳輸?shù)目偟臄?shù)據(jù)包數(shù)。因?yàn)閿?shù)據(jù)包產(chǎn)生率是固定的(每個(gè)源節(jié)點(diǎn)每秒產(chǎn)生2 個(gè)數(shù)據(jù)包)，所以網(wǎng)絡(luò)內(nèi)所傳輸?shù)目偟臄?shù)據(jù)包數(shù)是固定的。流量越大，表明路由開(kāi)銷(xiāo)越大，冗余數(shù)據(jù)包數(shù)越多，路由性能越差。

圖7 顯示了EEAR、RTGR 和AVHR 路由的流量。

圖7 流量隨節(jié)點(diǎn)數(shù)變化情況

從圖7 可知，RTGR 路由的流量最高，且隨節(jié)點(diǎn)數(shù)的增加呈線性上升，原因在于：RTGR 路由引用角度廣播，增加了數(shù)據(jù)包的傳輸次數(shù)，而EEAR路由和AVHR 路由的流量隨節(jié)點(diǎn)數(shù)增加而保持緩慢的增加。

3 結(jié)束語(yǔ)

本文針對(duì)3 維WSNs 的路由問(wèn)題展開(kāi)分析，并提出能效角度路由EEAR。EEAR 路由先依據(jù)信宿位置計(jì)算角度，再根據(jù)角度選擇一部分節(jié)點(diǎn)作為候選轉(zhuǎn)發(fā)節(jié)點(diǎn)，最后利用節(jié)點(diǎn)的剩余能量和距離信息計(jì)算節(jié)點(diǎn)的權(quán)重，并依據(jù)節(jié)點(diǎn)權(quán)重?fù)駜?yōu)選擇下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。仿真結(jié)果表明，提出的EEAR路由能有效提高數(shù)據(jù)包傳遞率，并能控制能耗。