李琳琪,楊新宇

(西安交通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系, 710049, 西安)

?

一種新型的半固定地理路由

李琳琪,楊新宇

(西安交通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系, 710049, 西安)

針對(duì)地理位置路由協(xié)議中逐跳決策造成的時(shí)延以及路由局部化問(wèn)題,提出了一種基于期望傳輸時(shí)間的半固定路由方法。該方法以虛擬鄰居節(jié)點(diǎn)集的方式擴(kuò)展節(jié)點(diǎn)傳輸半徑,以映射的方式選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)與虛擬鄰居節(jié)點(diǎn)的路由,減少了路由選擇時(shí)間,并以邊界節(jié)點(diǎn)集的方式解決網(wǎng)絡(luò)中的局部化問(wèn)題。半固定路由表形成時(shí),以期望傳輸時(shí)間作為衡量參數(shù),有效的對(duì)鏈路進(jìn)行了優(yōu)選,為數(shù)據(jù)傳輸提供了更優(yōu)的鏈路條件。該算法省略了中間節(jié)點(diǎn)的路由選擇時(shí)間,減少了協(xié)議轉(zhuǎn)換和嘗試尋路造成的時(shí)間開銷,使得網(wǎng)絡(luò)的延遲狀況得到了很大程度的改善。仿真結(jié)果表明,該算法可以有效應(yīng)對(duì)路由局部化問(wèn)題,降低時(shí)延,提升網(wǎng)絡(luò)性能。

期望傳輸時(shí)間;時(shí)延;半固定路由

傳統(tǒng)的基于位置的路由協(xié)議,通常在數(shù)據(jù)包到達(dá)某一節(jié)點(diǎn)后才決定下一跳的節(jié)點(diǎn),會(huì)造成數(shù)據(jù)傳輸實(shí)時(shí)性上的損失。在網(wǎng)絡(luò)存在空曠域的情況下,基于位置信息的貪婪路由方式會(huì)面臨局部化問(wèn)題,需要轉(zhuǎn)為其他路由方式,這種轉(zhuǎn)換也會(huì)造成數(shù)據(jù)傳輸?shù)难舆t。在救災(zāi)網(wǎng)絡(luò)中,受災(zāi)害破壞影響形成很多不可達(dá)區(qū)域,從而造成網(wǎng)絡(luò)拓?fù)渲写嬖谳^多的空曠域,數(shù)據(jù)傳輸延遲則更為明顯。另一方面,因?yàn)樨澙贩绞酵ǔＶ豢紤]跳數(shù)和距離而忽略鏈路質(zhì)量,鏈路的質(zhì)量往往受到環(huán)境等因素的影響,在較差的鏈路上傳遞消息,可能會(huì)導(dǎo)致消息被重復(fù)傳幾次才能成功,甚至可能傳輸失敗,這必然造成不小的延遲。為了解決這些問(wèn)題,研究人員提出很多方案,早期的例如文獻(xiàn)[1]中使用丟棄數(shù)據(jù)分組的方法;另一種方式是避免局部化,例如文獻(xiàn)[2]是標(biāo)記空曠域,提前轉(zhuǎn)發(fā);文獻(xiàn)[3]使用橢圓繞洞方法。在路徑的優(yōu)化方面,文獻(xiàn)[4]對(duì)數(shù)據(jù)敏感程度加以區(qū)分,使用不同路徑傳輸;文獻(xiàn)[5-6]是從時(shí)延角度出發(fā)的路由優(yōu)化的方法;文獻(xiàn)[7]依據(jù)期望傳輸次數(shù)和相對(duì)跳數(shù)來(lái)按照貪婪方式進(jìn)行路由;文獻(xiàn)[8]使用了基于蟻群算法的路由方式;文獻(xiàn)[9]利用社會(huì)感知模型提高成功率;文獻(xiàn)[10]利用交通信息對(duì)路由方式進(jìn)行優(yōu)化。

本文提出了基于期望傳輸時(shí)間(expected transmission time, ETT)的貪婪半固定路由方法(semi-permanent geographic routing algorithm, ESGR),將兩跳的鏈路以固定路由方式與虛擬鄰居節(jié)點(diǎn)集中的節(jié)點(diǎn)一一映射,省略了中間節(jié)點(diǎn)的路由選擇時(shí)間。算法以期望傳輸時(shí)間作為固定路由的優(yōu)選參考因素,通過(guò)使用優(yōu)選鏈路來(lái)降低重傳的概率,并以空曠域邊緣節(jié)點(diǎn)集合映射候選靜態(tài)路由的方式解決網(wǎng)絡(luò)局部化的問(wèn)題。通過(guò)以上方式減少了協(xié)議轉(zhuǎn)換和嘗試尋路造成的時(shí)間開銷,使得網(wǎng)絡(luò)的延遲狀況得到了改善。

1 協(xié)議設(shè)計(jì)

ESGR協(xié)議包含以下基本假設(shè):①算法不涉及位置服務(wù)部分,認(rèn)為所有節(jié)點(diǎn)都知道自身位置信息,源發(fā)節(jié)點(diǎn)也知道目的節(jié)點(diǎn)位置信息;②網(wǎng)絡(luò)的移動(dòng)性屬于中低速,節(jié)點(diǎn)的相對(duì)位置可以保持較長(zhǎng)的一段時(shí)間;③網(wǎng)絡(luò)拓?fù)浠诙S空間,網(wǎng)絡(luò)密度要求不高,可以存在空曠域,但是網(wǎng)絡(luò)應(yīng)是可連通的。因?yàn)樵撍惴ㄡ槍?duì)網(wǎng)絡(luò)延遲的改善,如果存在沒(méi)有可連接通路的情況,會(huì)影響算法性能尤其是延遲狀況的正常評(píng)估,因此,在設(shè)計(jì)網(wǎng)絡(luò)環(huán)境的時(shí)候,要求網(wǎng)絡(luò)是可連通的。

1.1 協(xié)議思想

ESGR協(xié)議是在貪婪轉(zhuǎn)發(fā)算法的基礎(chǔ)上,擴(kuò)展了節(jié)點(diǎn)的相對(duì)位置信息,利用節(jié)點(diǎn)移動(dòng)的局部性和移動(dòng)性不高的特點(diǎn),以分布式的方式在各個(gè)節(jié)點(diǎn)上保存了相應(yīng)的鄰居及兩跳鄰居節(jié)點(diǎn)的信息,建立虛擬鄰居節(jié)點(diǎn)集,并依據(jù)ETT對(duì)當(dāng)前節(jié)點(diǎn)到虛擬鄰居節(jié)點(diǎn)的鏈路進(jìn)行優(yōu)選。虛擬鄰居節(jié)點(diǎn)唯一對(duì)應(yīng)一條從當(dāng)前節(jié)點(diǎn)到自身的優(yōu)質(zhì)傳輸鏈路。數(shù)據(jù)包到達(dá)當(dāng)前節(jié)點(diǎn)后,通過(guò)貪婪規(guī)則在虛擬鄰居節(jié)點(diǎn)集中選擇下一跳轉(zhuǎn)發(fā)的節(jié)點(diǎn),數(shù)據(jù)通過(guò)映射的路由轉(zhuǎn)發(fā)。協(xié)議分為鄰居信息采集和數(shù)據(jù)傳輸過(guò)程兩部分。

協(xié)議采用信標(biāo)發(fā)送的機(jī)制,當(dāng)前節(jié)點(diǎn)周期性地向鄰居節(jié)點(diǎn)發(fā)送信標(biāo)信號(hào),該信號(hào)中包含節(jié)點(diǎn)及其所有鄰居節(jié)點(diǎn)信息,以及當(dāng)前節(jié)點(diǎn)到鄰居節(jié)點(diǎn)的鏈路ETT值,當(dāng)前節(jié)點(diǎn)根據(jù)所收到信標(biāo)形成虛擬鄰居節(jié)點(diǎn)集以及對(duì)應(yīng)的半固定路由集。

數(shù)據(jù)傳輸過(guò)程即協(xié)議對(duì)數(shù)據(jù)業(yè)務(wù)的傳輸處理過(guò)程。由源節(jié)點(diǎn)發(fā)出數(shù)據(jù)包,根據(jù)貪婪規(guī)則,在虛擬鄰居節(jié)點(diǎn)集中選定距離目的節(jié)點(diǎn)最近的節(jié)點(diǎn),從半固定路由表中映射對(duì)應(yīng)的路由后轉(zhuǎn)發(fā)。收到消息的中間節(jié)點(diǎn)檢查自身是否為目的節(jié)點(diǎn),以及所有鄰居節(jié)點(diǎn)中是否存在目的節(jié)點(diǎn)。若存在則直接發(fā)送數(shù)據(jù),否則繼續(xù)根據(jù)貪婪規(guī)則選擇距離目標(biāo)最近的節(jié)點(diǎn)和路由進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā),直至消息到達(dá)目的節(jié)點(diǎn)。

1.2 鄰居信息采集

鄰居信息采集是本協(xié)議的重要組成部分,信息采集過(guò)程通過(guò)周期性的信標(biāo)信號(hào)來(lái)完成,各個(gè)節(jié)點(diǎn)通過(guò)信標(biāo)信號(hào)中的發(fā)信節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)信息來(lái)完成自身信息的更新。關(guān)鍵問(wèn)題是虛擬鄰居節(jié)點(diǎn)集和半固定路由表的建立及空曠域引起的局部化問(wèn)題的處理方式。

為了更好地選擇節(jié)點(diǎn),降低因鏈路質(zhì)量帶來(lái)的時(shí)間開銷,算法中引入了期望傳輸時(shí)間(ETT)的概念。當(dāng)鏈路的ETT大于等于給定閾值T時(shí),認(rèn)為該鏈路質(zhì)量太差,不適合于實(shí)時(shí)傳輸,不建議采用該條鏈路。在發(fā)送信標(biāo)時(shí),信標(biāo)中除了自身信息外也攜帶鄰居節(jié)點(diǎn)信息及對(duì)應(yīng)的鏈路ETT值。

該算法中有3個(gè)常規(guī)集合,第1個(gè)集合為鄰居節(jié)點(diǎn)集,該集合以當(dāng)前節(jié)點(diǎn)的所有一跳鄰居節(jié)點(diǎn)作為元素。這里假設(shè)當(dāng)前節(jié)點(diǎn)為S,S的鄰居集合為A,初始情況下A為空集,每當(dāng)S收到鄰居節(jié)點(diǎn)的信標(biāo),檢查當(dāng)前節(jié)點(diǎn)與該鄰居節(jié)點(diǎn)鏈路的ETT值,如該值小于閾值T,可將該鄰居節(jié)點(diǎn)作為一個(gè)元素添加到A中,否則丟棄該信標(biāo)。對(duì)于已經(jīng)在集合中的元素,在一段時(shí)間內(nèi),如沒(méi)收到該元素發(fā)來(lái)的信標(biāo),則表示該元素所標(biāo)識(shí)的節(jié)點(diǎn)已離開當(dāng)前節(jié)點(diǎn)的通信范圍,不再是其鄰居節(jié)點(diǎn),因此將該節(jié)點(diǎn)從集合中剔除,由此動(dòng)態(tài)地形成S的鄰居節(jié)點(diǎn)集A,稱其為S的基本集。

第2個(gè)集合是當(dāng)前節(jié)點(diǎn)兩跳距離的節(jié)點(diǎn)集合,即虛擬鄰居節(jié)點(diǎn)集。假設(shè)該集合為B,初始情況下B為空集,當(dāng)S收到鄰居節(jié)點(diǎn)的信標(biāo),將新收到的鄰居節(jié)點(diǎn)的基本集剔除S自身及其基本集的元素。計(jì)算鏈路期望,即從節(jié)點(diǎn)S出發(fā),經(jīng)過(guò)此鄰居節(jié)點(diǎn),到其所有基本集內(nèi)節(jié)點(diǎn)的鏈路的ETT值,如果該值小于閾值T,則忽略該節(jié)點(diǎn),反之將該節(jié)點(diǎn)加入虛擬鄰居節(jié)點(diǎn)集B中。對(duì)于已經(jīng)在集合中的元素,在一段時(shí)間內(nèi),如果沒(méi)有關(guān)于該元素更新信息的信標(biāo),則表示該元素所標(biāo)識(shí)的節(jié)點(diǎn)已經(jīng)不在當(dāng)前節(jié)點(diǎn)的兩跳范圍,不再是其鄰居節(jié)點(diǎn),因此將該節(jié)點(diǎn)從集合中剔除,最終形成虛擬鄰居節(jié)點(diǎn)集。

第3個(gè)集合是當(dāng)前節(jié)點(diǎn)到其虛擬鄰居節(jié)點(diǎn)的優(yōu)選鏈路集,也就是前面提到的半固定路由表,它的生成是與虛擬鄰居節(jié)點(diǎn)集同步的。假設(shè)這個(gè)集合為L(zhǎng),使得到達(dá)另一節(jié)點(diǎn)的多跳通路不止一條,同樣在本算法中,盡管只是兩跳的鏈路,因多個(gè)中間節(jié)點(diǎn)的存在,也會(huì)存在多種可能。算法依據(jù)ETT值對(duì)鏈路質(zhì)量進(jìn)行優(yōu)選,對(duì)于多條通過(guò)不同節(jié)點(diǎn)到達(dá)同一虛擬鄰居節(jié)點(diǎn)的鏈路,選擇ETT值最小的一條,將其路徑信息保存并加入優(yōu)選鏈路集。虛擬鄰居節(jié)點(diǎn)集B與優(yōu)選鏈路集L之間存在著一一映射關(guān)系,保證了在實(shí)際的數(shù)據(jù)傳輸過(guò)程中,根據(jù)貪婪算法選出虛擬鄰居節(jié)點(diǎn)后,對(duì)應(yīng)的優(yōu)質(zhì)鏈路也選定。

實(shí)際的網(wǎng)絡(luò)中空曠域是不可避免的,空曠域帶來(lái)的局部化問(wèn)題是基于位置的路由算法必須要面對(duì)的一個(gè)重要問(wèn)題。本算法中同樣采用了節(jié)點(diǎn)集映射鏈路的思想,針對(duì)空曠域,如果當(dāng)前節(jié)點(diǎn)發(fā)現(xiàn)周圍存在空曠域,則根據(jù)右手定理和左手定理同時(shí)進(jìn)行探測(cè)。由于空曠域的不確定性,考慮到網(wǎng)絡(luò)的移動(dòng)性和開銷,探測(cè)結(jié)束以鏈路不超過(guò)N跳以及鏈路終點(diǎn)(探測(cè)點(diǎn)自身)到達(dá)為止,每探測(cè)到一個(gè)邊界節(jié)點(diǎn),將該節(jié)點(diǎn)加入邊界節(jié)點(diǎn)集Bn,同時(shí)將到達(dá)該節(jié)點(diǎn)的鏈路保存于邊界鏈路集Ln中,如果集合中已有該節(jié)點(diǎn),則根據(jù)到該節(jié)點(diǎn)不同的鏈路對(duì)應(yīng)的不同ETT值選擇更優(yōu)的鏈路保存于邊界鏈路集中,同時(shí)剔除相應(yīng)的另一條鏈路,從而保證集合中的鏈?zhǔn)绞窍鄬?duì)更優(yōu)的選擇。

1.3 數(shù)據(jù)傳輸過(guò)程

本協(xié)議的數(shù)據(jù)傳輸過(guò)程也采用了地理位置路由常用的貪婪方式,即選擇下一跳節(jié)點(diǎn)時(shí)的規(guī)則是選擇距離目的節(jié)點(diǎn)最近的節(jié)點(diǎn),選擇的范圍就是鄰居節(jié)點(diǎn)集,目的是盡量選出跳數(shù)最少的路由,并使用序列號(hào)機(jī)制防止在邊界轉(zhuǎn)發(fā)時(shí)產(chǎn)生路由環(huán)路。具體過(guò)程如下。

步驟1 源節(jié)點(diǎn)S發(fā)送數(shù)據(jù)包,首先檢查鄰居節(jié)點(diǎn)集中是否存在目的節(jié)點(diǎn),如果是,根據(jù)優(yōu)選鏈路集表選定路徑,直接將數(shù)據(jù)發(fā)往目的節(jié)點(diǎn),傳輸結(jié)束,否則選擇鄰居節(jié)點(diǎn)集中距離目的節(jié)點(diǎn)最近的節(jié)點(diǎn),并根據(jù)優(yōu)選鏈路集中對(duì)應(yīng)的路徑發(fā)送數(shù)據(jù)。

步驟2 中間節(jié)點(diǎn)接收到數(shù)據(jù)包后,檢查自身是否為目的節(jié)點(diǎn),以及鄰居節(jié)點(diǎn)集中是否存在目的節(jié)點(diǎn),如存在,根據(jù)優(yōu)選鏈路集選定路徑,直接將數(shù)據(jù)發(fā)往目的節(jié)點(diǎn),傳輸結(jié)束,否則轉(zhuǎn)至步驟3。

步驟3 檢查虛擬鄰居節(jié)點(diǎn)集。根據(jù)目的節(jié)點(diǎn)位置,在虛擬鄰居節(jié)點(diǎn)集中選擇距離目的節(jié)點(diǎn)最近的一個(gè)虛擬鄰居節(jié)點(diǎn),并檢查該節(jié)點(diǎn)是否在路由序列之中,如在則忽略該節(jié)點(diǎn)重新選擇,直到選出不在路由序列之中的的鄰居節(jié)點(diǎn)為止。若存在局部化的問(wèn)題,轉(zhuǎn)入步驟4,否則根據(jù)該節(jié)點(diǎn)映射在優(yōu)選鏈路集中的路由信息,進(jìn)行數(shù)據(jù)的傳輸。本步驟是中間節(jié)點(diǎn)在不存在局部化問(wèn)題時(shí)的業(yè)務(wù)處理方式。

步驟4 根據(jù)目的節(jié)點(diǎn)位置,在鄰居集中選擇距離目的節(jié)點(diǎn)最近的節(jié)點(diǎn),并檢查該節(jié)點(diǎn)是否在路由序列之中,如在則忽略該節(jié)點(diǎn)重新選擇,直到選出不在路由序列之中的的鄰居節(jié)點(diǎn)為止。若存在局部化的問(wèn)題,轉(zhuǎn)入步驟5,否則直接向該鄰居節(jié)點(diǎn)發(fā)送數(shù)據(jù),該節(jié)點(diǎn)收到數(shù)據(jù)包后,重復(fù)步驟2和步驟3直到數(shù)據(jù)到達(dá)目的節(jié)點(diǎn)為止。

步驟5 根據(jù)目的節(jié)點(diǎn)位置,在邊界節(jié)點(diǎn)集中進(jìn)行選擇,選擇該集合中距離目的節(jié)點(diǎn)最近的節(jié)點(diǎn),如果仍然沒(méi)有,則選擇邊界鏈路集中最長(zhǎng)的一條鏈路,檢查是否出現(xiàn)環(huán)路,當(dāng)出現(xiàn)閉環(huán)時(shí),丟棄該數(shù)據(jù)包,否則進(jìn)行傳輸,到達(dá)鏈路最末端后,重復(fù)步驟2和步驟3直到數(shù)據(jù)到達(dá)目的節(jié)點(diǎn)為止。

算法選擇由兩跳路由形成的固定路由表是因?yàn)槿绻x擇更多節(jié)點(diǎn)勢(shì)必造成數(shù)據(jù)鏈路越來(lái)越長(zhǎng),靈活性差,對(duì)節(jié)點(diǎn)移動(dòng)會(huì)更敏感,增加對(duì)網(wǎng)絡(luò)拓?fù)涞囊蕾囆?而且發(fā)送和接收節(jié)點(diǎn)相同的鏈路數(shù)目也會(huì)呈幾何級(jí)數(shù)增長(zhǎng),需要更大的計(jì)算開銷,信標(biāo)中所攜帶的內(nèi)容也會(huì)急劇增加,搶占帶寬,不僅浪費(fèi)資源,也會(huì)增加控制開銷,因此選擇有一個(gè)中間節(jié)點(diǎn)的兩跳鏈路為佳。

2 協(xié)議分析

2.1 ESGR協(xié)議正確性分析

協(xié)議采用基于地理位置的貪婪轉(zhuǎn)發(fā)規(guī)則,數(shù)據(jù)包的傳輸是趨向目的節(jié)點(diǎn)的方向進(jìn)行,每一次數(shù)據(jù)轉(zhuǎn)發(fā)都更接近目的節(jié)點(diǎn),同時(shí)更遠(yuǎn)離源節(jié)點(diǎn),位置的物理位移決定了消息傳遞的單向性,從而防止了路由環(huán)路的產(chǎn)生。對(duì)于空曠域的處理過(guò)程中,通過(guò)規(guī)定最長(zhǎng)鏈路跳數(shù)以及序列號(hào)機(jī)制,保證通過(guò)邊界傳輸時(shí)不會(huì)產(chǎn)生路由環(huán)路。保證協(xié)議正確性的另一個(gè)條件是可以找到到達(dá)目的節(jié)點(diǎn)的路徑,保證數(shù)據(jù)成功到達(dá)目的節(jié)點(diǎn)。這個(gè)條件可以從網(wǎng)絡(luò)存在空曠域和不存在空曠域兩種場(chǎng)景分析。

網(wǎng)絡(luò)中不存在空曠域時(shí),因?yàn)榫W(wǎng)絡(luò)是可連通的,又因?yàn)猷従庸?jié)點(diǎn)與路由是一一映射關(guān)系,所以對(duì)任意i,如果目的節(jié)點(diǎn)D∈Ai∪Bi,則存在li為節(jié)點(diǎn)i到目的節(jié)點(diǎn)的路徑。如果D?Ai∪Bi則存在n(n∈A∪B),使得dn

網(wǎng)絡(luò)中存在空曠域時(shí),可以分成目的節(jié)點(diǎn)在空曠域內(nèi)、目的節(jié)點(diǎn)在空曠域邊界上以及目的節(jié)點(diǎn)在空曠域外這3種情況。

根據(jù)網(wǎng)絡(luò)連通性,對(duì)任意i、j(i,j∈Bn),存在l使得節(jié)點(diǎn)i和節(jié)點(diǎn)j連通,即邊界上任意兩個(gè)節(jié)點(diǎn)之間都是可達(dá)的。Bn為空曠域的所有邊界節(jié)點(diǎn)集。

目的節(jié)點(diǎn)在空曠域內(nèi),這種情況下目的節(jié)點(diǎn)是不可達(dá)的,遇到這種情況只能放棄傳輸,或等節(jié)點(diǎn)移動(dòng)出空曠域后再進(jìn)行傳輸。因協(xié)議的前提是網(wǎng)絡(luò)是可連通的,所以這種情況暫不做考慮。目的節(jié)點(diǎn)在空曠域的邊界上時(shí),對(duì)任意i(i∈Bn),存在li。目的節(jié)點(diǎn)在空曠域之外時(shí),當(dāng)節(jié)點(diǎn)i遭遇局部化問(wèn)題時(shí),存在n(n∈Bn),使得dn

由此可見(jiàn),在所有場(chǎng)景下,協(xié)議成功找到傳輸路徑的條件也可滿足,從而保證了協(xié)議的正確性。

2.2 ESGR協(xié)議開銷分析

與傳統(tǒng)的GPSR協(xié)議類似,本協(xié)議也采用了簡(jiǎn)單的信標(biāo)發(fā)送機(jī)制,即利用網(wǎng)絡(luò)的廣播特性,周期性的向鄰居節(jié)點(diǎn)發(fā)送信標(biāo)信號(hào)。為了降低多個(gè)鄰居節(jié)點(diǎn)發(fā)送信標(biāo)信號(hào)的沖突概率,發(fā)射間隔使用隨機(jī)選取的方式。信標(biāo)攜帶的內(nèi)容不僅只是簡(jiǎn)單的鄰居信息,而是包含了鄰居的鄰居節(jié)點(diǎn)信息以及之間鏈路的ETT值。增加了數(shù)據(jù)包的信息量,開銷必然有所增大,但因協(xié)議僅僅依賴兩跳范圍內(nèi)的節(jié)點(diǎn)信息,而不是所有節(jié)點(diǎn)的相關(guān)信息,信標(biāo)發(fā)送的范圍集中在兩跳范圍內(nèi),局部性的信標(biāo)使得控制信息開銷不會(huì)隨著網(wǎng)絡(luò)規(guī)模增加呈幾何式的增長(zhǎng),而是保持基本不變,不會(huì)造成全網(wǎng)的數(shù)據(jù)激增。基于位置的轉(zhuǎn)發(fā)方式,分布式的路由設(shè)計(jì),使得協(xié)議對(duì)網(wǎng)絡(luò)規(guī)模不敏感,保證了路由協(xié)議良好的可擴(kuò)展性。本算法中,節(jié)點(diǎn)與路由是一一映射的關(guān)系,選定轉(zhuǎn)發(fā)節(jié)點(diǎn)后,相應(yīng)的路由也對(duì)應(yīng)出來(lái),無(wú)需發(fā)起路由探索,節(jié)點(diǎn)選擇的時(shí)間復(fù)雜度為O(n),其中n為虛擬鄰居節(jié)點(diǎn)數(shù)。

時(shí)間開銷為數(shù)據(jù)包傳輸所花費(fèi)的時(shí)間

D=Ds+Dt

(1)

式中:Ds為路由選擇時(shí)間;Dt為數(shù)據(jù)傳輸時(shí)間。

從以上分析可以看到,基于ETT對(duì)鏈路的優(yōu)化選擇,使用映射代替逐跳計(jì)算,ESGR在時(shí)延控制方面的優(yōu)勢(shì)還是比較明顯的。網(wǎng)絡(luò)的吞吐量期望與ETT成反比,因此算法對(duì)網(wǎng)絡(luò)的吞吐量提升也有較好的效果。

3 仿真實(shí)驗(yàn)

3.1 環(huán)境與參數(shù)設(shè)置

實(shí)驗(yàn)仿真環(huán)境為OPNET10.0,網(wǎng)絡(luò)范圍為2 200 m×2 200 m,移動(dòng)節(jié)點(diǎn)200個(gè),移動(dòng)模型為Waypoint,最大移動(dòng)速度為30 m/s。手工設(shè)置一個(gè)空曠域,大小為100 m×200 m。

3.2 實(shí)驗(yàn)結(jié)果及分析

圖1給出了在不同節(jié)點(diǎn)運(yùn)行速度下的丟包率,反映了隨著節(jié)點(diǎn)運(yùn)動(dòng)速度的提升,協(xié)議性能的變化,體現(xiàn)的是吞吐量的變化。如圖所示,在節(jié)點(diǎn)基本靜止時(shí),各個(gè)協(xié)議的丟包率都比較低,隨著節(jié)點(diǎn)移動(dòng)速度逐漸增加,出現(xiàn)分化。當(dāng)節(jié)點(diǎn)的運(yùn)動(dòng)速度到30 m/s后,丟包率分化更為明顯,GPSR與ESGR協(xié)議的丟包率相對(duì)變化較小,這是因?yàn)閰f(xié)議的路由過(guò)程只涉及局部的節(jié)點(diǎn)信息,合理的信標(biāo)發(fā)送周期可以及時(shí)準(zhǔn)確地提供所需路由信息。ESGR協(xié)議的丟包率高于GPSR協(xié)議,這是由于ESGR協(xié)議采用了兩跳路由,且在空曠域的時(shí)候,長(zhǎng)路徑更多一些,因而比GPSR協(xié)議對(duì)節(jié)點(diǎn)移動(dòng)速度更加敏感。HAIR協(xié)議因其機(jī)制原因,丟包率更高一些,而TAR協(xié)議因考慮了拓?fù)湟蛩?對(duì)節(jié)點(diǎn)位置的準(zhǔn)確性要求更高,隨著節(jié)點(diǎn)速度提升,丟包率增加比較明顯。

圖1 平均丟包率與節(jié)點(diǎn)速度的關(guān)系

圖2對(duì)比了各個(gè)協(xié)議在不同節(jié)點(diǎn)移動(dòng)速率的情況下的端到端時(shí)延?？梢钥吹?節(jié)點(diǎn)靜止的情況下,ESGR的時(shí)延相對(duì)較小,比GPSR低大約42%,而且隨著節(jié)點(diǎn)的速率的增加,這種低時(shí)延的優(yōu)勢(shì)一直得到保持。TAR因在將拓?fù)湟蛩乜紤]進(jìn)空曠域的處理上,因此時(shí)延也相對(duì)較低。隨著節(jié)點(diǎn)移動(dòng)速度增加,TAR因其對(duì)拓?fù)涞囊蕾?使得其端到端時(shí)延明顯增加,而其他3個(gè)協(xié)議的變化較小。相比GPSR,ESGR的端到端時(shí)延增加的趨勢(shì)更快一些,但仍比GPSR低20%左右,可見(jiàn)ESGR在時(shí)延上的優(yōu)勢(shì)是相當(dāng)顯著的。

圖2 端到端時(shí)延與節(jié)點(diǎn)速度的關(guān)系

圖3對(duì)比了數(shù)據(jù)包從源節(jié)點(diǎn)到目的節(jié)點(diǎn)傳輸?shù)钠骄鴶?shù)。靜止?fàn)顟B(tài)下,TAR最優(yōu),ESGR的平均跳數(shù)比GPSR略高,這是因?yàn)镋SGR選取質(zhì)量更優(yōu)的鏈路,在物理上比GPSR所走的路徑距離更長(zhǎng)。隨著節(jié)點(diǎn)速度的提升,TAR的優(yōu)勢(shì)降低,其他3個(gè)協(xié)議的平均跳數(shù)增幅都不大,說(shuō)明這3個(gè)局部化的協(xié)議在低網(wǎng)絡(luò)拓?fù)渥儞Q的情況下,都能較好運(yùn)行。在具體的實(shí)驗(yàn)過(guò)程中發(fā)現(xiàn),除了因?yàn)檫x取優(yōu)質(zhì)鏈路造成跳數(shù)值增加外,實(shí)際在處理空曠域時(shí),因?yàn)榫植炕膯?wèn)題,當(dāng)節(jié)點(diǎn)的邊界節(jié)點(diǎn)集中仍沒(méi)有可選節(jié)點(diǎn),即仍然面臨局部化問(wèn)題時(shí),會(huì)選擇最遠(yuǎn)的節(jié)點(diǎn)。這樣的處理方式并不完美,在一些特殊的拓?fù)淝闆r下,會(huì)造成路徑的迂回,從而造成跳數(shù)值增加,但是此缺陷可以被更好的路徑質(zhì)量和更低的時(shí)延所彌補(bǔ),因而不會(huì)對(duì)協(xié)議性能造成太大的影響。

圖3 平均跳數(shù)與節(jié)點(diǎn)速度的關(guān)系

通過(guò)以上仿真實(shí)驗(yàn)可以看到,在節(jié)點(diǎn)速度變大、網(wǎng)絡(luò)動(dòng)態(tài)性增加的情況下,ESGR協(xié)議無(wú)論是在丟包率還是端到端時(shí)延方面都表現(xiàn)出較好的性能,尤其是在降低時(shí)延方面效果顯著,具有很高的魯棒性,更能滿足網(wǎng)絡(luò)對(duì)實(shí)時(shí)數(shù)據(jù)傳輸?shù)男枨蟆?/p>

4 結(jié) 論

ESGR協(xié)議利用節(jié)點(diǎn)移動(dòng)的局部性和相對(duì)穩(wěn)定性,以映射的方式選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)與虛擬鄰居節(jié)點(diǎn)的路由,減少了路由選擇時(shí)間,以虛擬的方式擴(kuò)展了節(jié)點(diǎn)傳輸半徑,并以邊界節(jié)點(diǎn)集的方式解決網(wǎng)絡(luò)中的局部化問(wèn)題,在形成半固定路由表時(shí),以ETT作為衡量參數(shù),對(duì)鏈路進(jìn)行了有效的優(yōu)選,為數(shù)據(jù)傳輸提供了更優(yōu)的鏈路選擇,從而達(dá)到降低網(wǎng)絡(luò)時(shí)延、提升網(wǎng)絡(luò)性能的目的。仿真結(jié)果表明,ESGR協(xié)議相比目前的方法在時(shí)延控制等方面有20%以上的顯著提升,更能適應(yīng)存在空曠域的網(wǎng)絡(luò)情況,滿足網(wǎng)絡(luò)的實(shí)時(shí)性需求。

[1] STOJMENOVIC I, LIN X. GEDIR: loop-free location based routing in wireless networks [C]∥Proceedings of the 1999 International Conference on Parallel and Distributed Computing and Systems. Cambridge, MA, USA: ACTA Press, 1999: 1025-1028.

[2] CADGER F, CURRAN K, SANTOS J, et al. A survey of geographical routing in wireless ad hoc networks [J]. IEEE Communications Surveys and Tutorials, 2013, 15(2): 621-653.

[3] YU Fucai, PARK S, TIAN Ye, et al. Efficient hole detour scheme for geographic routing in wireless sensor networks [C]∥Proceedings of the 2008 IEEE Vehicular Technology Conference. Piscataway, NJ, USA: IEEE, 2008: 153-157.

[4] 梁慶偉, 姚道遠(yuǎn), 鞏思亮. 一種保障時(shí)延能量高效的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議 [J]. 西安交通大學(xué)學(xué)報(bào), 2012, 46(6): 48-52. LIANG Qingwei, YAO Daoyuan, GONG Siliang. A delay-guaranteed energy-efficient wireless sensor network routing protocol [J]. Journal of Xi’an Jiaotong University, 2012, 46(6): 48-52.

[5] LEE J H. A new routing scheme to reduce traffic in large scale mobile ad hoc networks through selective on-demand method [J]. Wireless Networks, 2014, 20(5): 1067-1083.

[6] ALSAQOUR R, ABDELHAQ M, SAEED R, et al. Dynamic packet beaconing for GPSR mobile ad hoc position-based routing protocol using fuzzy logic [J]. Journal of Network and Computer Applications, 2015, 47: 32-46.

[7] HUANG Pei, WANG Chen, XIAO Li. Improving end-to-end routing performance of greedy forwarding in sensor networks [J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 23(3): 556-563.

[8] SINGH G, KUMAR N, VERMA A K. OANTALG: an orientation based ant colony algorithm for mobile Ad Hoc networks [J]. Wireless Personal Communications, 2014, 77(3): 1859-1884.

[9] 陳家旭, 唐亞哲, 胡成臣, 等. 延遲容忍網(wǎng)絡(luò)中基于地點(diǎn)偏好的社會(huì)感知多播路由協(xié)議設(shè)計(jì) [J]. 西安交通大學(xué)學(xué)報(bào), 2014, 48(6): 13-18. CHEN Jiaxu, TANG Yazhe, HU Chengchen, et al. Design of a social aware multicast routing protocol based on location preference in delay tolerant networks [J]. Journal of Xi’an Jiaotong University, 2014, 48(6): 13-18.

[10]TIAN Rui, ZHANG Baoxian, ZHENG Jun. A new distributed routing protocol using partial traffic information for vehicular ad hoc networks [J]. Wireless Networks, 2014, 20(6): 1627-1637.

[本刊相關(guān)文獻(xiàn)鏈接]

李季碧,鄧科,任智,等.機(jī)會(huì)網(wǎng)絡(luò)中高效低時(shí)延多擺渡節(jié)點(diǎn)路由算法.2015,49(4):91-97.[doi:10.7652/xjtuxb2015040 15]

李季碧,李賓,任智,等.自適應(yīng)動(dòng)態(tài)功率控制的機(jī)會(huì)網(wǎng)絡(luò)節(jié)能高效路由算法.2014,48(12):49-56.[doi:10.7652/xjtuxb 201412008]

戴慧珺,曲樺,趙季紅.利用非精確參數(shù)的移動(dòng)互聯(lián)網(wǎng)業(yè)務(wù)感知多目標(biāo)優(yōu)化QoS路由算法.2014,48(2):86-92.[doi:10.7652/xjtuxb201402015]

陳家旭,唐亞哲,寧京宣,等.移動(dòng)自組網(wǎng)中節(jié)點(diǎn)興趣導(dǎo)向的人類運(yùn)動(dòng)模型.2013,47(12):110-115.[doi:10.7652/xjtuxb 201312019]

汪志偉,曹建福,鄭輯光.一種面向分簇?zé)o線傳感器網(wǎng)絡(luò)的多信道跨層協(xié)議.2013,47(6):61-67.[doi:10.7652/xjtuxb 201306011]

李琳琪,楊新宇,劉蔚.高動(dòng)態(tài)網(wǎng)絡(luò)的自決策式地理機(jī)會(huì)主義路由.2013,47(2):7-13.[doi:10.7652/xjtuxb201302002]

高昂,李增智,趙季中.用于無(wú)線自組織網(wǎng)絡(luò)的屬性加密算法.2012,46(8):33-36.[doi:10.7652/xjtuxb201208006]

梁慶偉,姚道遠(yuǎn),鞏思亮.一種保障時(shí)延能量高效的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議.2012,46(6):48-52.[doi:10.7652/xjtuxb 201206009]

陳衡,錢德沛,伍衛(wèi)國(guó),等.傳感器網(wǎng)絡(luò)基于鄰居信息量化的能量平衡路由.2012,46(4):1-6.[doi:10.7652/xjtuxb2012 04001]

何暉,王換招,李昊,等.增強(qiáng)Ad Hoc網(wǎng)絡(luò)穩(wěn)定性的移動(dòng)問(wèn)題解決策略.2011,45(4):6-11.[doi:10.7652/xjtuxb201104 002]

鄭博,黃國(guó)策,張衡陽(yáng),等.甚高頻航空自組網(wǎng)的組網(wǎng)概率及連通性研究.2011,45(8):24-29.[doi:10.7652/xjtuxb201108 005]

杜君,李偉華,張克旺,等.無(wú)線自組織網(wǎng)絡(luò)高準(zhǔn)確度自私節(jié)點(diǎn)檢測(cè)機(jī)制.2010,44(8):25-29.[doi:10.7652/xjtuxb201008 006]

張榮博,曹建福.利用蟻群優(yōu)化的非均勻分簇?zé)o線傳感器網(wǎng)絡(luò)路由算法.2010,44(6):33-38.[doi:10.7652/xjtuxb201006 007]

仝杰,錢德沛,劉軼,等.針對(duì)事件驅(qū)動(dòng)型傳感器網(wǎng)絡(luò)的多路徑編碼路由協(xié)議.2010,44(6):39-45.[doi:10.7652/xjtuxb 201006008]

(編輯 武紅江)

A Novel Semi-Permanent Geographic Routing

LI Linqi,YANG Xinyu

(Department of Computer Science and Technology, Xi’an Jiaotong University, Xi’an 710049, China)

An ETT(expected transmission time)-based semi-permanent geographic routing algorithm (ESGR) is proposed to solve the localization problem and time delay caused by hop by hop route. The algorithm first establishes a set of virtual neighbor nodes, then chooses the forwarding node using a greedy method and maps links from the semi-permanent route table. ESGR maps boundary node set to boundary link set and the localization problem is solved. This saves time of protocol switching and path searching. Once the semi-permanent routing table is formulated, the ETT is used as a measure to optimize the links, so that a better link condition for data transmission is provided. Simulation results show that ESGR effectively deals with the localization problem, reduces the delay and improves the network performance.

expected transmission time; delay; semi-permanent routing

2015-09-07。

李琳琪(1977—),男,博士生;楊新宇(通信作者),男,教授,博士生導(dǎo)師。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61502381);中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(xjj2015065);中國(guó)博士后科學(xué)基金資助項(xiàng)目(2015M570836)。

時(shí)間:2016-01-07

10.7652/xjtuxb201602002

TP393

A

0253-987X(2016)02-0007-06

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20160107.1309.010.html