基于應(yīng)急場(chǎng)景的自組織網(wǎng)絡(luò)機(jī)會(huì)路由算法

范曉軍,劉林峰,3,李思穎

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院,江蘇 南京 210023;2.江蘇省無(wú)線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室,江蘇 南京 210003;3.東南大學(xué) 計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室,江蘇 南京 211189)

基于應(yīng)急場(chǎng)景的自組織網(wǎng)絡(luò)機(jī)會(huì)路由算法

范曉軍1,2,劉林峰1,2,3,李思穎1

(1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院,江蘇 南京 210023;2.江蘇省無(wú)線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室,江蘇 南京 210003;3.東南大學(xué) 計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室,江蘇 南京 211189)

應(yīng)急場(chǎng)景是移動(dòng)自組織網(wǎng)絡(luò)的重要應(yīng)用場(chǎng)景，在該場(chǎng)景中難以保證節(jié)點(diǎn)能夠?qū)崟r(shí)通信，為了在高效轉(zhuǎn)發(fā)數(shù)據(jù)包的同時(shí)盡量減少網(wǎng)絡(luò)傳輸中的時(shí)延，提出了基于穩(wěn)定值的機(jī)會(huì)網(wǎng)絡(luò)路由算法，并在其中引入了穩(wěn)定因子的概念，將節(jié)點(diǎn)的移動(dòng)規(guī)律與其鄰居節(jié)點(diǎn)進(jìn)行關(guān)聯(lián)。對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)根據(jù)穩(wěn)定值進(jìn)行分類，穩(wěn)定性越好的節(jié)點(diǎn)轉(zhuǎn)發(fā)概率越高，更容易受到節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的青睞。此外，考慮到應(yīng)急場(chǎng)景的動(dòng)態(tài)性、復(fù)雜性，算法還會(huì)對(duì)節(jié)點(diǎn)的穩(wěn)定性進(jìn)行動(dòng)態(tài)更新。仿真結(jié)果表明，在不同的網(wǎng)絡(luò)規(guī)模下，逐漸增加網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量，相比于傳統(tǒng)的Epidemic、Direct Delivery以及Prophet路由算法，該算法的網(wǎng)絡(luò)開銷能接近較高水平，取得較高的消息送達(dá)成功率，降低平均網(wǎng)絡(luò)時(shí)延，適用于應(yīng)急場(chǎng)景。

移動(dòng)自組織網(wǎng)絡(luò)；機(jī)會(huì)路由算法；應(yīng)急場(chǎng)景；穩(wěn)定值

0 引 言

移動(dòng)自組織網(wǎng)絡(luò)(Ad Hoc網(wǎng)絡(luò))是由可移動(dòng)節(jié)點(diǎn)互聯(lián)組成的具有臨時(shí)性拓?fù)浣Y(jié)構(gòu)的自組織對(duì)等網(wǎng)絡(luò)系統(tǒng)。該網(wǎng)絡(luò)特點(diǎn)是節(jié)點(diǎn)之間的數(shù)據(jù)傳輸過(guò)程不需要存在完整的鏈路，也不用網(wǎng)絡(luò)提供中央控制單元和實(shí)體對(duì)等，通過(guò)節(jié)點(diǎn)的自組織形式形成通信域。在整個(gè)數(shù)據(jù)傳輸?shù)倪^(guò)程中，節(jié)點(diǎn)通過(guò)“攜帶-存儲(chǔ)-轉(zhuǎn)發(fā)”的方式將消息傳遞到下一跳節(jié)點(diǎn)[1]。根據(jù)這種特點(diǎn)，移動(dòng)自組織網(wǎng)絡(luò)通常能夠在惡劣條件下進(jìn)行網(wǎng)絡(luò)通信，可以適用于各種突發(fā)事件的應(yīng)急通信場(chǎng)合。

應(yīng)急場(chǎng)景是移動(dòng)自組織網(wǎng)絡(luò)的重要應(yīng)用場(chǎng)景之一，如地震、火災(zāi)等嚴(yán)重災(zāi)害發(fā)生過(guò)后，包括通信、電力等一系列基礎(chǔ)設(shè)施遭到破壞，依賴通信基礎(chǔ)設(shè)施的通信系統(tǒng)癱瘓都可能無(wú)法使用。此時(shí)，依靠身處應(yīng)急場(chǎng)景的個(gè)人或者可移動(dòng)的傳感器節(jié)點(diǎn)來(lái)進(jìn)行通信，進(jìn)而以這些節(jié)點(diǎn)組成具有臨時(shí)性的通信網(wǎng)絡(luò)將成為應(yīng)急場(chǎng)景中至關(guān)重要的通信技術(shù)。在應(yīng)急場(chǎng)景中，節(jié)點(diǎn)的運(yùn)動(dòng)規(guī)律很難把握，節(jié)點(diǎn)之間的通信成功率難以得到保證。因此，理清不同節(jié)點(diǎn)的移動(dòng)規(guī)律，及時(shí)準(zhǔn)確地傳遞消息意味著救援行動(dòng)會(huì)有更高的成功率。

目前，關(guān)于移動(dòng)自組織網(wǎng)絡(luò)中對(duì)于數(shù)據(jù)傳輸有效性的研究已經(jīng)取得了一些成果。傳統(tǒng)的路由算法，主要沿著兩大基礎(chǔ)策略進(jìn)行：(1)基于冗余的路由算法，將消息通過(guò)復(fù)制拷貝擴(kuò)散到網(wǎng)絡(luò)中，形成多消息儲(chǔ)存的路由策略。具有代表性的是Epidemic算法[2]。(2)基于效用值的路由算法，通過(guò)效用值的計(jì)算為節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)提供參考，篩選一個(gè)或多個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)。Prophet算法[3]就是利用轉(zhuǎn)發(fā)概率這一指標(biāo)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)的指導(dǎo)。文中所提算法也屬于該類方法。

文中提出了一種應(yīng)用于特定緊急場(chǎng)景的路由算法(Routing Scheme for Emergency Scenarios,RSES)，通過(guò)節(jié)點(diǎn)穩(wěn)定值的計(jì)算來(lái)體現(xiàn)階段時(shí)間內(nèi)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)的概率值，以此概率值作為機(jī)會(huì)轉(zhuǎn)發(fā)的效用值，同時(shí)對(duì)節(jié)點(diǎn)的穩(wěn)定值進(jìn)行動(dòng)態(tài)更新。該算法旨在利用節(jié)點(diǎn)在應(yīng)急場(chǎng)景中的穩(wěn)定性，得到一個(gè)較為合理的轉(zhuǎn)發(fā)策略。

1 相關(guān)研究

傳統(tǒng)的路由算法，如極端的不泛洪Direct Delivery算法[4]，在任何情況下都是單副本傳輸，不會(huì)對(duì)數(shù)據(jù)包進(jìn)行復(fù)制，只有遇到目標(biāo)節(jié)點(diǎn)時(shí)才進(jìn)行數(shù)據(jù)包的交付，因此路由開銷最小，但是送達(dá)率和傳輸延遲較差。而與之相反，極端無(wú)限制的泛洪Epidemic算法是通過(guò)復(fù)制拷貝節(jié)點(diǎn)信息的方式，采用遇到節(jié)點(diǎn)就轉(zhuǎn)發(fā)的方法，所有相遇節(jié)點(diǎn)都會(huì)收到數(shù)據(jù)包。該算法能夠增加數(shù)據(jù)傳輸?shù)某晒β释瑫r(shí)減少傳輸延遲，但是轉(zhuǎn)發(fā)過(guò)程會(huì)產(chǎn)生大量副本，容易造成網(wǎng)絡(luò)傳輸?shù)膿砣６鳶pray and Wait算法則是一定策略下的泛洪，文獻(xiàn)[5-6]表明該算法在多數(shù)場(chǎng)景的應(yīng)用具有一定的效果，但是在鄰居節(jié)點(diǎn)的選擇過(guò)程中，依然存在著節(jié)點(diǎn)選擇不合理造成送達(dá)率不高和開銷大等問(wèn)題。Prophet算法是一種基于概率預(yù)測(cè)的算法。該算法通過(guò)統(tǒng)計(jì)節(jié)點(diǎn)與自己相遇的歷史信息，得到一個(gè)轉(zhuǎn)發(fā)概率的計(jì)算方式，通過(guò)計(jì)算轉(zhuǎn)發(fā)概率預(yù)測(cè)將來(lái)的移動(dòng)。該算法能夠提高信息傳遞的效率和成功率，但是在節(jié)點(diǎn)較多的情況，要經(jīng)過(guò)大量的計(jì)算才可能得到下一跳的節(jié)點(diǎn)，造成傳遞方式過(guò)于復(fù)雜的問(wèn)題。Inwhee Joe等在文獻(xiàn)[7]設(shè)定了一種特殊場(chǎng)景，場(chǎng)景中包括道路、巡邏警車、人員等節(jié)點(diǎn)遭受自然災(zāi)害都有不同程度的損傷，比較了傳統(tǒng)算法在普通場(chǎng)景和特殊場(chǎng)景下的表現(xiàn)，指出傳統(tǒng)的路由算法在特殊場(chǎng)景下各項(xiàng)路由指標(biāo)都有退化的現(xiàn)象，并不能完全適用于特殊場(chǎng)景。文獻(xiàn)[7]依據(jù)節(jié)點(diǎn)的速度來(lái)對(duì)消息進(jìn)行分類，在消息傳遞階段，只讓移動(dòng)速度快的節(jié)點(diǎn)進(jìn)行消息轉(zhuǎn)發(fā)，在降低能耗的同時(shí)，卻付出了增大時(shí)延的代價(jià)。

機(jī)會(huì)網(wǎng)絡(luò)摒棄了傳統(tǒng)自組織網(wǎng)需要在端到端建立路由的工作模式，利用節(jié)點(diǎn)移動(dòng)帶來(lái)相遇機(jī)會(huì)實(shí)現(xiàn)通信，不要求網(wǎng)絡(luò)全連通，可以看成是具有一般DTN網(wǎng)絡(luò)特征的無(wú)線自組網(wǎng)，更符合實(shí)際環(huán)境下的自主組網(wǎng)需求，近年來(lái)成為國(guó)際、國(guó)內(nèi)學(xué)術(shù)界關(guān)注的熱點(diǎn)[8]。目前，關(guān)于在應(yīng)急場(chǎng)景中機(jī)會(huì)網(wǎng)絡(luò)的研究取得了一些成果，一般通過(guò)建立適合于應(yīng)急場(chǎng)景的移動(dòng)模型來(lái)反映節(jié)點(diǎn)的移動(dòng)屬性，并研究如何在該移動(dòng)模型下，通過(guò)分析得出應(yīng)急場(chǎng)景節(jié)點(diǎn)的接觸規(guī)律，利用節(jié)點(diǎn)之間稀有的接觸機(jī)會(huì)為應(yīng)急場(chǎng)景通信創(chuàng)造更多的通信可能和提供更好的送達(dá)保證，是應(yīng)急場(chǎng)景機(jī)會(huì)轉(zhuǎn)發(fā)的一個(gè)重要研究方向。文獻(xiàn)[9]定義了PDM(Post-Disaster Mobility)模型來(lái)模擬應(yīng)急場(chǎng)景。該模型用來(lái)抽象應(yīng)急場(chǎng)景中人的移動(dòng)特征，認(rèn)為在應(yīng)急場(chǎng)景中節(jié)點(diǎn)的運(yùn)動(dòng)并不完全是隨機(jī)的，如救援人員會(huì)在救護(hù)站與受災(zāi)區(qū)頻繁往來(lái)，巡邏車會(huì)在主要街道來(lái)回巡邏，人員會(huì)在學(xué)校操場(chǎng)、廣場(chǎng)等空曠地方集合。與此類似，Aschenbruck N等在文獻(xiàn)[10-11]中也針對(duì)人類行為的特點(diǎn)提出了應(yīng)急場(chǎng)景下的移動(dòng)模型。文獻(xiàn)[10]提出了一個(gè)以地理社區(qū)為基礎(chǔ)的移動(dòng)模型來(lái)描述受災(zāi)者的運(yùn)動(dòng)模式，受災(zāi)者有更高的概率在他們的家庭社區(qū)內(nèi)隨機(jī)移動(dòng)，而在非家庭區(qū)域的社區(qū)內(nèi)移動(dòng)概率則較小，同時(shí)社區(qū)管理人員和救援人員會(huì)有一定的概率在社區(qū)之間移動(dòng)。這兩種假設(shè)有效地描繪了受災(zāi)者和社區(qū)管理人員、救援人員的應(yīng)急反應(yīng)運(yùn)動(dòng)模式。文獻(xiàn)[12]通過(guò)對(duì)目前現(xiàn)有的隨機(jī)移動(dòng)模型進(jìn)行統(tǒng)一化的形式描述，建立起包含所有隨機(jī)模型的新的隨機(jī)模型。該模型將節(jié)點(diǎn)移動(dòng)速度設(shè)定在一個(gè)速度區(qū)間(vmin,vmax)內(nèi)，通過(guò)擴(kuò)大速度取值范圍，擴(kuò)大節(jié)點(diǎn)移動(dòng)速度的多樣性，并采用速度取值范圍極差(VelocityValueIntervalRange,VVIR)這一指標(biāo)來(lái)進(jìn)行衡量，最后通過(guò)選取合適的速度多樣性來(lái)保證適當(dāng)?shù)耐ㄐ艜r(shí)間和通信次數(shù)以提高網(wǎng)絡(luò)性能。然而在應(yīng)急場(chǎng)景中，實(shí)際上節(jié)點(diǎn)移動(dòng)速度是完全隨機(jī)的，文獻(xiàn)[13]將速度限制在某個(gè)速度區(qū)間，通過(guò)調(diào)整節(jié)點(diǎn)運(yùn)動(dòng)速度達(dá)到較好的通信效果顯然并不適合于真實(shí)場(chǎng)景，并且作為通信中繼的節(jié)點(diǎn)并不一定具備人的移動(dòng)特征，因此文獻(xiàn)[9，12]用在此場(chǎng)景中會(huì)顯得比較局限。

文中定義了基于應(yīng)急場(chǎng)景的移動(dòng)模型，認(rèn)為在應(yīng)急場(chǎng)景中巡邏車輛、救援人員的運(yùn)動(dòng)并不完全是隨機(jī)的，如巡邏車輛會(huì)在主要街道來(lái)回巡邏，救援人員會(huì)選擇最短路徑到達(dá)救援現(xiàn)場(chǎng)；而作為通信介質(zhì)的傳感器節(jié)點(diǎn)運(yùn)動(dòng)遵循隨機(jī)移動(dòng)模型，在速度區(qū)間(vmin,vmax)隨機(jī)運(yùn)動(dòng)。

2 基于穩(wěn)定值的轉(zhuǎn)發(fā)概率更新與機(jī)會(huì)轉(zhuǎn)發(fā)算法

首先介紹應(yīng)急場(chǎng)景通信網(wǎng)絡(luò)。在應(yīng)急場(chǎng)景中，每個(gè)救援人員的身上配備一個(gè)帶有通信功能的彈射裝置，在救援過(guò)程中自動(dòng)彈出一些小的傳感器節(jié)點(diǎn)，這些傳感器節(jié)點(diǎn)具有定位的輔助功能，在救援人員和外界指揮中心間組成一個(gè)多跳網(wǎng)絡(luò)[14]。該網(wǎng)絡(luò)的核心思想是將單跳通信鏈路轉(zhuǎn)換成基于中繼傳感器的多跳網(wǎng)絡(luò)，以此來(lái)消除極端環(huán)境給通信帶來(lái)的影響。

傳感器節(jié)點(diǎn)在穩(wěn)定環(huán)境下會(huì)保持原先的狀態(tài)，并可以維持通信網(wǎng)絡(luò)完整，但當(dāng)遇到諸如地震、火災(zāi)等惡劣環(huán)境時(shí)，節(jié)點(diǎn)會(huì)發(fā)生大幅度移動(dòng)，或者高溫使得節(jié)點(diǎn)損壞等都會(huì)使原先保持的通信網(wǎng)遭到破壞。為此，定義了2個(gè)概念：

(1)應(yīng)急場(chǎng)景中的節(jié)點(diǎn)集{Va,Vb,Vc…}。其中，既有救援人員、巡邏車輛組成的規(guī)律運(yùn)動(dòng)的節(jié)點(diǎn)集，也有傳感器節(jié)點(diǎn)這類隨機(jī)運(yùn)動(dòng)的節(jié)點(diǎn)。

(2)節(jié)點(diǎn)穩(wěn)定值(StabilityValue)。每個(gè)節(jié)點(diǎn)都保留著一段時(shí)間內(nèi)的穩(wěn)定值，用以表示這段時(shí)間內(nèi)同鄰居節(jié)點(diǎn)的關(guān)聯(lián)程度，并且穩(wěn)定值可能會(huì)隨著時(shí)間而發(fā)生改變。

文中提出算法的理論基礎(chǔ)，是考慮到應(yīng)急場(chǎng)景中不同節(jié)點(diǎn)的運(yùn)動(dòng)規(guī)律。救援人員的運(yùn)動(dòng)具有目的性，可在最短時(shí)間到達(dá)目標(biāo)地點(diǎn)；傳感器節(jié)點(diǎn)受環(huán)境影響表現(xiàn)出移動(dòng)不可預(yù)測(cè)性。假設(shè)源節(jié)點(diǎn)為Vs，在T0時(shí)刻產(chǎn)生一個(gè)發(fā)往目的節(jié)點(diǎn)Vd的消息，消息在傳輸過(guò)程中的有效生存期為Tsuv。算法思想表述為在T0+Tsuv時(shí)刻內(nèi)將消息發(fā)給受惡劣環(huán)境影響最小的節(jié)點(diǎn)，也就是對(duì)穩(wěn)定性較高的節(jié)點(diǎn)賦予較高的轉(zhuǎn)發(fā)概率，由此類節(jié)點(diǎn)盡可能轉(zhuǎn)發(fā)數(shù)據(jù)包，而不穩(wěn)定的節(jié)點(diǎn)則盡可能少地轉(zhuǎn)發(fā)數(shù)據(jù)包。該方式可以減少惡劣環(huán)境對(duì)路由轉(zhuǎn)發(fā)的影響，減少網(wǎng)絡(luò)中傳輸?shù)母北緮?shù)量，同時(shí)保證較高的送達(dá)率。

2.1 穩(wěn)定值

穩(wěn)定值表示一段時(shí)間內(nèi)節(jié)點(diǎn)在通信網(wǎng)絡(luò)中的穩(wěn)定性。文中認(rèn)為節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的距離變化值越小，穩(wěn)定性越好。對(duì)于節(jié)點(diǎn)Vk，通過(guò)計(jì)算其與鄰居節(jié)點(diǎn)的距離變化值來(lái)確定穩(wěn)定性。

通過(guò)式(1)計(jì)算t時(shí)刻到t+1時(shí)刻節(jié)點(diǎn)Vk與節(jié)點(diǎn)Vk1之間的距離變化值。

(1)

選取節(jié)點(diǎn)Vk同鄰居節(jié)點(diǎn)距離變化值最小的Δmin值，通過(guò)式(2)計(jì)算距離變化方差。

(2)

其中，Δ(k,ki)表示節(jié)點(diǎn)Vk和鄰居節(jié)點(diǎn)之間的距離變化值。

(3)

其中，S(t)表示穩(wěn)定因子。

每個(gè)節(jié)點(diǎn)都維護(hù)著一張穩(wěn)定值效用表，該表格顯示了節(jié)點(diǎn)在固定時(shí)間內(nèi)的穩(wěn)定值大小，當(dāng)節(jié)點(diǎn)之間接觸時(shí)，會(huì)查詢對(duì)方的穩(wěn)定值，并且節(jié)點(diǎn)的穩(wěn)定值會(huì)隨著時(shí)間的變化而更新，更新公式如下：

(4)

其中，Spre(t)表示上一個(gè)t時(shí)刻節(jié)點(diǎn)的穩(wěn)定系數(shù)；k為自上次計(jì)算概率后經(jīng)過(guò)的時(shí)刻數(shù)。

從式(4)可以看出，如果節(jié)點(diǎn)同鄰居節(jié)點(diǎn)的偏離程度開始變大，則穩(wěn)定值變小(穩(wěn)定性變差)。

2.2 機(jī)會(huì)轉(zhuǎn)發(fā)策略

當(dāng)節(jié)點(diǎn)Vi攜帶消息準(zhǔn)備轉(zhuǎn)發(fā)時(shí)，如果檢測(cè)到周圍存在其他節(jié)點(diǎn)，則將待轉(zhuǎn)發(fā)消息廣播給通信半徑中的其他節(jié)點(diǎn)，其他節(jié)點(diǎn)收到消息后，更新轉(zhuǎn)發(fā)概率，穩(wěn)定性高的節(jié)點(diǎn)具有較高的轉(zhuǎn)發(fā)概率，更新轉(zhuǎn)發(fā)概率計(jì)算如式(5)所示：

P(Vi,Vk)=

{Ppre(Vi,Vk)+[1-Ppre(Vi,Vk)]Pi}(1-S(t))

(5)

其中，Ppre(Vi,Vk)表示節(jié)點(diǎn)Vi，Vk相遇之前的轉(zhuǎn)發(fā)概率；Pi表示[0,1]范圍內(nèi)的預(yù)設(shè)常量。

節(jié)點(diǎn)Vi搜集到通信半徑內(nèi)所有節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率，選擇概率較大的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，其中穩(wěn)定因子值越大則說(shuō)明這一時(shí)間段內(nèi)節(jié)點(diǎn)穩(wěn)定，作為中繼節(jié)點(diǎn)傳輸?shù)母怕示痛蟆?/p>

此外，轉(zhuǎn)發(fā)概率具有傳遞性，Vi與Vk經(jīng)常相遇，Vk與Vk1經(jīng)常相遇，那么節(jié)點(diǎn)Vk1可能是轉(zhuǎn)發(fā)消息到達(dá)節(jié)點(diǎn)Vi的良好中繼。計(jì)算方式如下：

P(Vi,Vk1)=Ppre(Vi,Vk1)+[1-Ppre(Vi,Vk1)]* P(Vi,Vk)P(Vk,Vk1)β

(6)

其中，傳遞系數(shù)β∈[0,1]是常量。

算法步驟如下：

(1)任意兩節(jié)點(diǎn)Vi和Vk進(jìn)入到彼此的通信半徑中建立連接；

(2)檢查節(jié)點(diǎn)Vi和節(jié)點(diǎn)Vk的穩(wěn)定值，用式(4)進(jìn)行更新，轉(zhuǎn)入步驟(3)；

(3)節(jié)點(diǎn)Vi和節(jié)點(diǎn)Vk交換彼此的信息，包括穩(wěn)定值和轉(zhuǎn)發(fā)概率值以及各自節(jié)點(diǎn)同其他節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率，交換之前檢查穩(wěn)定值是否更新，更新則轉(zhuǎn)入步驟(4)，沒(méi)更新轉(zhuǎn)回步驟(2)；

(4)根據(jù)式(5)重新計(jì)算節(jié)點(diǎn)Vi和節(jié)點(diǎn)Vk之間的轉(zhuǎn)發(fā)概率，并利用式(6)計(jì)算節(jié)點(diǎn)Vi與節(jié)點(diǎn)Vk1之間的轉(zhuǎn)發(fā)概率；

(5)節(jié)點(diǎn)Vi攜帶發(fā)往目標(biāo)節(jié)點(diǎn)的數(shù)據(jù)包M，如果節(jié)點(diǎn)Vk沒(méi)有數(shù)據(jù)包M并且節(jié)點(diǎn)Vk的轉(zhuǎn)發(fā)概率比其余節(jié)點(diǎn)大，則將數(shù)據(jù)包M從節(jié)點(diǎn)Vi發(fā)往節(jié)點(diǎn)Vk。

3 實(shí)驗(yàn)?zāi)M及性能分析

利用3個(gè)指標(biāo)(消息送達(dá)率、路由開銷比和傳輸延時(shí))對(duì)提出的RSES算法有效性進(jìn)行驗(yàn)證。

消息送達(dá)率：在整個(gè)仿真期間傳遞成功的數(shù)據(jù)包總數(shù)(Ndelivered)與需要傳遞的數(shù)據(jù)包總數(shù)(Ncreated)的比值。

傳輸延時(shí)：是從源節(jié)點(diǎn)發(fā)送一個(gè)數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)所需要的時(shí)間。傳輸延時(shí)越小，說(shuō)明路由算法的傳輸效率越高。

3.1 仿真參數(shù)設(shè)置

采用機(jī)會(huì)網(wǎng)絡(luò)仿真平臺(tái)(Opportunistic Networking Environment，ONE)[15]進(jìn)行測(cè)試，模擬了基于Helsinki市的應(yīng)急場(chǎng)景，如圖1所示。

圖1 基于Helsinki市的仿真場(chǎng)景

與路由算法Epidemic、Direct Delivery算法以及Prophet算法進(jìn)行比較，具體設(shè)置見表1。

同時(shí)，為了體現(xiàn)應(yīng)急場(chǎng)景的特點(diǎn)，設(shè)定5%的節(jié)點(diǎn)受不良環(huán)境影響而損壞(包括巡邏車輛、救援人員組成的節(jié)點(diǎn)和傳感器節(jié)點(diǎn))。其中巡邏車輛由于道路的坍塌損壞不能移動(dòng)，救援人員的通信設(shè)備受到強(qiáng)干擾喪失通信功能，損壞的傳感器節(jié)點(diǎn)其中1/2能移動(dòng)但不能通信，1/2的傳感器節(jié)點(diǎn)既不能移動(dòng)也不能通信，特別說(shuō)明的是傳感器節(jié)點(diǎn)的運(yùn)動(dòng)是完全隨機(jī)的，即隨機(jī)的速度、方向和暫停時(shí)間，具體設(shè)置見表2。

表1 仿真參數(shù)設(shè)置

表2 節(jié)點(diǎn)設(shè)置

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

在表1的場(chǎng)景下，設(shè)計(jì)了不同網(wǎng)絡(luò)規(guī)模場(chǎng)景，改變網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目，依次考察三種算法性能的變化。仿真結(jié)果如圖2～4所示。

圖2 消息送達(dá)率與節(jié)點(diǎn)之間的關(guān)系

圖3 路由開銷比與節(jié)點(diǎn)數(shù)之間的關(guān)系

圖2顯示了當(dāng)節(jié)點(diǎn)數(shù)目增加時(shí)算法送達(dá)率之間的比較。可以看出，三種傳統(tǒng)算法的送達(dá)率始終低于RSES算法，主要原因是隨著節(jié)點(diǎn)數(shù)目的增加，Epidemic算法以及Prophet算法會(huì)引起整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)相遇次數(shù)的急劇增加，從而增加了傳遞的消息次數(shù)，造成整個(gè)網(wǎng)絡(luò)的擁塞。在緩存區(qū)有限的條件下，這兩種機(jī)制會(huì)在緩存滿時(shí)丟棄一些數(shù)據(jù)包，進(jìn)而影響了送達(dá)率。Epidemic算法會(huì)對(duì)遇到的每一個(gè)節(jié)點(diǎn)都進(jìn)行消息轉(zhuǎn)發(fā)，節(jié)點(diǎn)越多，需要轉(zhuǎn)發(fā)的次數(shù)也就越多，從而導(dǎo)致的網(wǎng)絡(luò)開銷也急劇增長(zhǎng)。結(jié)合圖3，Direct Delivery算法只對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行消息轉(zhuǎn)發(fā)，雖然網(wǎng)絡(luò)開銷基本可以忽略，但送達(dá)率較低。而RSES算法可以有效控制副本的數(shù)量，在傳輸之前考慮鄰居節(jié)點(diǎn)的穩(wěn)定性，只對(duì)穩(wěn)定性好、轉(zhuǎn)發(fā)概率大的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，大大減少了副本數(shù)量，在節(jié)點(diǎn)逐漸增多的情況下，能始終保持送達(dá)率上的優(yōu)勢(shì)。相較于Prophet算法，RSES算法在交換歷史信息的同時(shí)考慮到節(jié)點(diǎn)的穩(wěn)定性，穩(wěn)定性越高反映受到惡劣環(huán)境的影響越小，對(duì)這種節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，可以避免復(fù)制消息的盲目性，從而降低了路由開銷。

圖4 傳輸時(shí)延與節(jié)點(diǎn)數(shù)之間的關(guān)系

從圖4中可以看出，DirectDelivery算法的平均時(shí)延隨著節(jié)點(diǎn)數(shù)目的增加而延長(zhǎng)，原因是DirectDelivery算法只對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，當(dāng)節(jié)點(diǎn)數(shù)目增加時(shí)，尋找目標(biāo)節(jié)點(diǎn)也就越耗時(shí)。此外，三種算法的平均時(shí)延隨著節(jié)點(diǎn)數(shù)目的增加都有所縮短，這是因?yàn)楣?jié)點(diǎn)數(shù)目增加后，網(wǎng)絡(luò)中的副本數(shù)量隨之增加，和目的節(jié)點(diǎn)的相遇機(jī)會(huì)也隨之增加，所以消息轉(zhuǎn)發(fā)的平均時(shí)延會(huì)降低。同Prophet算法相比，在擁有更高的送達(dá)率的前提下，RSES算法的平均時(shí)延和Prophet算法相仿，雖然網(wǎng)絡(luò)中的副本數(shù)量少于Epidemic算法和Prophet算法，但是正確的轉(zhuǎn)發(fā)方向往往會(huì)對(duì)成功轉(zhuǎn)發(fā)起到很大作用。RSES路由算法考慮到了應(yīng)急場(chǎng)景的節(jié)點(diǎn)特點(diǎn)，在惡劣環(huán)境下，移動(dòng)路線相對(duì)穩(wěn)定的節(jié)點(diǎn)比隨機(jī)移動(dòng)、受環(huán)境干擾的節(jié)點(diǎn)更容易將消息送至目的節(jié)點(diǎn)，這也驗(yàn)證了RSES算法考慮的選擇穩(wěn)定性高節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)的方式。

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

分析了應(yīng)急場(chǎng)景的特點(diǎn)，充分利用節(jié)點(diǎn)運(yùn)動(dòng)的歷史信息，結(jié)合應(yīng)急場(chǎng)景節(jié)點(diǎn)特點(diǎn)，提出一種基于分組的路由策略—RSES。對(duì)穩(wěn)定性高、受惡劣環(huán)境影響小的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，避免復(fù)制消息的盲目性。仿真結(jié)果表明，RSES算法可以在保持較高送達(dá)率的同時(shí)有效減少網(wǎng)絡(luò)中的副本數(shù)量，降低路由開銷，適用于能量稀缺的應(yīng)急場(chǎng)景。

文中僅對(duì)救援人員、傳感器節(jié)點(diǎn)的移動(dòng)特點(diǎn)進(jìn)行了簡(jiǎn)要的仿真分析，今后的移動(dòng)模型設(shè)計(jì)將從受災(zāi)者以及救援人員的角度出發(fā)，設(shè)置更多的參數(shù)準(zhǔn)確地歸納人類的移動(dòng)特征，構(gòu)造特定場(chǎng)合的移動(dòng)模型，使模型與現(xiàn)實(shí)場(chǎng)景具有高度的匹配性。

[1] 熊永平,孫利民,牛建偉.機(jī)會(huì)網(wǎng)絡(luò)[J].軟件學(xué)報(bào),2009,20(1):124-137.

[2] Becker V D.Epidemic routing for partially connected ad hoc networks[R].Durham,NC:Duke University,2000.

[3] Lindgren A,Doria A,Schelén O.Probabilistic routing in intermittently connected networks[J].ACM SIGMOBILE Mobile Computing and Communications Review,2003,7(3):19-20.

[4] Grossglauser M,Tse D N C.Mobility increases the capacity of ad hoc wireless networks[J].IEEE/ACM Transactions on Networking,2002,10(4):477-486.

[5] Spyropoulos T,Psounis K,Raghavendra C S.Spray and wait:an efficient routing scheme for intermittently connected mobile networks[C]//Proceedings of the ACM SIGCOMM workshop on delay-tolerant networking.[s.l.]:ACM Press,2005:252-259.

[6] Becchetti L,Clementi A,Pasquale F,et al.Flooding time in opportunistic networks under power law and exponential inter-contact times[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(9):2297-2306.

[7] Joe I,Kim S B.A message priority routing protocol for delay tolerant networks (DTN) in disaster areas[J].Future Generation Information Technology,2010,4:727-737.

[8] Conti M,Kumar M.Opportunities in opportunistic computing[J].Computer,2010,43(1):42-50.

[9] Uddin M Y S,Ahmadi H,Abdelzaher T,et al.A low-energy,multi-copy inter-contact routing protocol for disaster response networks[C]//IEEE communications society conference on sensor.[s.l.]:IEEE,2009.

[10] Aschenbruck N, Gerhards-Padilla E, Martini P.Modeling mobility in disaster area scenarios[J].Performance Evaluation,2009,66(12):773-790.

[11] Aschenbruck N,Frank M,Martini P,et al.Human mobility in manet disaster area simulation-a realistic approach[C]//IEEE international conference on local computer networks.[s.l.]:IEEE,2004:668-675.

[12] Wang Xiaoming,Lin Yaguang,Zhang Shanshan,et al.A social activity and physical contact based routing algorithm in mobile opportunistic networks for emergency response of sudden disasters[J].Enterprise Information Systems,2015,3(2):1-30.

[13] Lin Yaguang,Wang Xiaoming,Zhang Lichen,et al.The impact of node velocity diversity on mobile opportunistic network performance[J].Journal of Network and Computer Applications,2015,55:47-58.

[14] 謝之恒.“面包屑”消防傳感系統(tǒng)-火災(zāi)救援中的可靠聯(lián)絡(luò)器[J].中國(guó)信息界,2014(4):68-71.

[15] Keranen A.Opportunistic network environment simulator[R].Helsinki:Helsinki University of Technology,2008.

An Opportunistic Routing Algorithm Based on Emergency Scenario in Ad Hoc Networks

FAN Xiao-jun1,2,LIU Lin-feng1,2,3,LI Si-ying1

(1.School of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210023,China;2.Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks,Nanjing 210003,China;3.Laboratory of Computer Network and Information Integration of Ministry of Education,Southeast University,Nanjing 211189,China)

Emergency scenario is an important application scenario of Ad Hoc Networks.In this scenario,it is difficult for nodes to ensure the communication.It becomes one of the goals that forwarding data packet efficiently while minimizing the transmission delay.A new opportunistic routing algorithm based on stability value is proposed,introduction of the concept of stable factor in it that the movements of nodes are associated with their neighbors.The node which has better stability is prone to receive the data packet.Moreover,with regard to the dynamics and complexity of the emergency scenario,the algorithm will dynamically update the stability of the nodes.According to simulation results,compared with the traditional routing algorithm like Epidemic,Direct Delivery,Prophet,the proposed algorithm suitable for emergency scenario can reduce the overhead and improve the delivery ratio in different network scales.

Ad Hoc networks;opportunistic routing algorithm;emergency scenario;stability value

2016-04-14

2016-08-10

時(shí)間：2017-02-17

國(guó)家自然科學(xué)基金資助項(xiàng)目(61373139,61373137,61300239,71301081);中國(guó)博士后科學(xué)基金(2014M560379,2015T80484)；江蘇省自然科學(xué)基金(BK2012833)

范曉軍(1992-)，男，碩士，研究方向?yàn)闄C(jī)會(huì)網(wǎng)絡(luò)；劉林峰，博士，副教授，研究方向?yàn)闄C(jī)會(huì)網(wǎng)絡(luò)。

http://www.cnki.net/kcms/detail/61.1450.TP.20170217.1623.016.html

TP301.6

A

1673-629X(2017)03-0006-06

10.3969/j.issn.1673-629X.2017.03.002