基于應急場景的自組織網絡機會路由算法

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

(1.南京郵電大學 計算機學院,江蘇 南京 210023;2.江蘇省無線傳感網高技術研究重點實驗室,江蘇 南京 210003;3.東南大學 計算機網絡和信息集成教育部重點實驗室,江蘇 南京 211189)

基于應急場景的自組織網絡機會路由算法

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

(1.南京郵電大學 計算機學院,江蘇 南京 210023;2.江蘇省無線傳感網高技術研究重點實驗室,江蘇 南京 210003;3.東南大學 計算機網絡和信息集成教育部重點實驗室,江蘇 南京 211189)

應急場景是移動自組織網絡的重要應用場景，在該場景中難以保證節點能夠實時通信，為了在高效轉發數據包的同時盡量減少網絡傳輸中的時延，提出了基于穩定值的機會網絡路由算法，并在其中引入了穩定因子的概念，將節點的移動規律與其鄰居節點進行關聯。對網絡中的節點根據穩定值進行分類，穩定性越好的節點轉發概率越高，更容易受到節點轉發消息的青睞。此外，考慮到應急場景的動態性、復雜性，算法還會對節點的穩定性進行動態更新。仿真結果表明，在不同的網絡規模下，逐漸增加網絡中的節點數量，相比于傳統的Epidemic、Direct Delivery以及Prophet路由算法，該算法的網絡開銷能接近較高水平，取得較高的消息送達成功率，降低平均網絡時延，適用于應急場景。

移動自組織網絡；機會路由算法；應急場景；穩定值

0 引 言

移動自組織網絡(Ad Hoc網絡)是由可移動節點互聯組成的具有臨時性拓撲結構的自組織對等網絡系統。該網絡特點是節點之間的數據傳輸過程不需要存在完整的鏈路，也不用網絡提供中央控制單元和實體對等，通過節點的自組織形式形成通信域。在整個數據傳輸的過程中，節點通過“攜帶-存儲-轉發”的方式將消息傳遞到下一跳節點[1]。根據這種特點，移動自組織網絡通常能夠在惡劣條件下進行網絡通信，可以適用于各種突發事件的應急通信場合。

應急場景是移動自組織網絡的重要應用場景之一，如地震、火災等嚴重災害發生過后，包括通信、電力等一系列基礎設施遭到破壞，依賴通信基礎設施的通信系統癱瘓都可能無法使用。此時，依靠身處應急場景的個人或者可移動的傳感器節點來進行通信，進而以這些節點組成具有臨時性的通信網絡將成為應急場景中至關重要的通信技術。在應急場景中，節點的運動規律很難把握，節點之間的通信成功率難以得到保證。因此，理清不同節點的移動規律，及時準確地傳遞消息意味著救援行動會有更高的成功率。

目前，關于移動自組織網絡中對于數據傳輸有效性的研究已經取得了一些成果。傳統的路由算法，主要沿著兩大基礎策略進行：(1)基于冗余的路由算法，將消息通過復制拷貝擴散到網絡中，形成多消息儲存的路由策略。具有代表性的是Epidemic算法[2]。(2)基于效用值的路由算法，通過效用值的計算為節點轉發數據提供參考，篩選一個或多個轉發節點。Prophet算法[3]就是利用轉發概率這一指標進行數據轉發的指導。文中所提算法也屬于該類方法。

文中提出了一種應用于特定緊急場景的路由算法(Routing Scheme for Emergency Scenarios,RSES)，通過節點穩定值的計算來體現階段時間內作為轉發節點的概率值，以此概率值作為機會轉發的效用值，同時對節點的穩定值進行動態更新。該算法旨在利用節點在應急場景中的穩定性，得到一個較為合理的轉發策略。

1 相關研究

傳統的路由算法，如極端的不泛洪Direct Delivery算法[4]，在任何情況下都是單副本傳輸，不會對數據包進行復制，只有遇到目標節點時才進行數據包的交付，因此路由開銷最小，但是送達率和傳輸延遲較差。而與之相反，極端無限制的泛洪Epidemic算法是通過復制拷貝節點信息的方式，采用遇到節點就轉發的方法，所有相遇節點都會收到數據包。該算法能夠增加數據傳輸的成功率同時減少傳輸延遲，但是轉發過程會產生大量副本，容易造成網絡傳輸的擁塞。而Spray and Wait算法則是一定策略下的泛洪，文獻[5-6]表明該算法在多數場景的應用具有一定的效果，但是在鄰居節點的選擇過程中，依然存在著節點選擇不合理造成送達率不高和開銷大等問題。Prophet算法是一種基于概率預測的算法。該算法通過統計節點與自己相遇的歷史信息，得到一個轉發概率的計算方式，通過計算轉發概率預測將來的移動。該算法能夠提高信息傳遞的效率和成功率，但是在節點較多的情況，要經過大量的計算才可能得到下一跳的節點，造成傳遞方式過于復雜的問題。Inwhee Joe等在文獻[7]設定了一種特殊場景，場景中包括道路、巡邏警車、人員等節點遭受自然災害都有不同程度的損傷，比較了傳統算法在普通場景和特殊場景下的表現，指出傳統的路由算法在特殊場景下各項路由指標都有退化的現象，并不能完全適用于特殊場景。文獻[7]依據節點的速度來對消息進行分類，在消息傳遞階段，只讓移動速度快的節點進行消息轉發，在降低能耗的同時，卻付出了增大時延的代價。

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

文中定義了基于應急場景的移動模型，認為在應急場景中巡邏車輛、救援人員的運動并不完全是隨機的，如巡邏車輛會在主要街道來回巡邏，救援人員會選擇最短路徑到達救援現場；而作為通信介質的傳感器節點運動遵循隨機移動模型，在速度區間(vmin,vmax)隨機運動。

2 基于穩定值的轉發概率更新與機會轉發算法

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

傳感器節點在穩定環境下會保持原先的狀態，并可以維持通信網絡完整，但當遇到諸如地震、火災等惡劣環境時，節點會發生大幅度移動，或者高溫使得節點損壞等都會使原先保持的通信網遭到破壞。為此，定義了2個概念：

(1)應急場景中的節點集{Va,Vb,Vc…}。其中，既有救援人員、巡邏車輛組成的規律運動的節點集，也有傳感器節點這類隨機運動的節點。

(2)節點穩定值(StabilityValue)。每個節點都保留著一段時間內的穩定值，用以表示這段時間內同鄰居節點的關聯程度，并且穩定值可能會隨著時間而發生改變。

文中提出算法的理論基礎，是考慮到應急場景中不同節點的運動規律。救援人員的運動具有目的性，可在最短時間到達目標地點；傳感器節點受環境影響表現出移動不可預測性。假設源節點為Vs，在T0時刻產生一個發往目的節點Vd的消息，消息在傳輸過程中的有效生存期為Tsuv。算法思想表述為在T0+Tsuv時刻內將消息發給受惡劣環境影響最小的節點，也就是對穩定性較高的節點賦予較高的轉發概率，由此類節點盡可能轉發數據包，而不穩定的節點則盡可能少地轉發數據包。該方式可以減少惡劣環境對路由轉發的影響，減少網絡中傳輸的副本數量，同時保證較高的送達率。

2.1 穩定值

穩定值表示一段時間內節點在通信網絡中的穩定性。文中認為節點與鄰居節點的距離變化值越小，穩定性越好。對于節點Vk，通過計算其與鄰居節點的距離變化值來確定穩定性。

通過式(1)計算t時刻到t+1時刻節點Vk與節點Vk1之間的距離變化值。

(1)

選取節點Vk同鄰居節點距離變化值最小的Δmin值，通過式(2)計算距離變化方差。

(2)

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

(3)

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

每個節點都維護著一張穩定值效用表，該表格顯示了節點在固定時間內的穩定值大小，當節點之間接觸時，會查詢對方的穩定值，并且節點的穩定值會隨著時間的變化而更新，更新公式如下：

(4)

其中，Spre(t)表示上一個t時刻節點的穩定系數；k為自上次計算概率后經過的時刻數。

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

2.2 機會轉發策略

當節點Vi攜帶消息準備轉發時，如果檢測到周圍存在其他節點，則將待轉發消息廣播給通信半徑中的其他節點，其他節點收到消息后，更新轉發概率，穩定性高的節點具有較高的轉發概率，更新轉發概率計算如式(5)所示：

P(Vi,Vk)=

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

(5)

其中，Ppre(Vi,Vk)表示節點Vi，Vk相遇之前的轉發概率；Pi表示[0,1]范圍內的預設常量。

節點Vi搜集到通信半徑內所有節點的轉發概率，選擇概率較大的節點進行數據轉發，其中穩定因子值越大則說明這一時間段內節點穩定，作為中繼節點傳輸的概率就大。

此外，轉發概率具有傳遞性，Vi與Vk經常相遇，Vk與Vk1經常相遇，那么節點Vk1可能是轉發消息到達節點Vi的良好中繼。計算方式如下：

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

(6)

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

算法步驟如下：

(1)任意兩節點Vi和Vk進入到彼此的通信半徑中建立連接；

(2)檢查節點Vi和節點Vk的穩定值，用式(4)進行更新，轉入步驟(3)；

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

(4)根據式(5)重新計算節點Vi和節點Vk之間的轉發概率，并利用式(6)計算節點Vi與節點Vk1之間的轉發概率；

(5)節點Vi攜帶發往目標節點的數據包M，如果節點Vk沒有數據包M并且節點Vk的轉發概率比其余節點大，則將數據包M從節點Vi發往節點Vk。

3 實驗模擬及性能分析

利用3個指標(消息送達率、路由開銷比和傳輸延時)對提出的RSES算法有效性進行驗證。

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

傳輸延時：是從源節點發送一個數據包到達目的節點所需要的時間。傳輸延時越小，說明路由算法的傳輸效率越高。

3.1 仿真參數設置

采用機會網絡仿真平臺(Opportunistic Networking Environment，ONE)[15]進行測試，模擬了基于Helsinki市的應急場景，如圖1所示。

圖1 基于Helsinki市的仿真場景

與路由算法Epidemic、Direct Delivery算法以及Prophet算法進行比較，具體設置見表1。

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

表1 仿真參數設置

表2 節點設置

3.2 實驗結果和性能分析

在表1的場景下，設計了不同網絡規模場景，改變網絡中的節點數目，依次考察三種算法性能的變化。仿真結果如圖2～4所示。

圖2 消息送達率與節點之間的關系

圖3 路由開銷比與節點數之間的關系

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

圖4 傳輸時延與節點數之間的關系

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

4 結束語

分析了應急場景的特點，充分利用節點運動的歷史信息，結合應急場景節點特點，提出一種基于分組的路由策略—RSES。對穩定性高、受惡劣環境影響小的節點進行數據轉發，避免復制消息的盲目性。仿真結果表明，RSES算法可以在保持較高送達率的同時有效減少網絡中的副本數量，降低路由開銷，適用于能量稀缺的應急場景。

文中僅對救援人員、傳感器節點的移動特點進行了簡要的仿真分析，今后的移動模型設計將從受災者以及救援人員的角度出發，設置更多的參數準確地歸納人類的移動特征，構造特定場合的移動模型，使模型與現實場景具有高度的匹配性。

[1] 熊永平,孫利民,牛建偉.機會網絡[J].軟件學報,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] 謝之恒.“面包屑”消防傳感系統-火災救援中的可靠聯絡器[J].中國信息界,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

時間：2017-02-17

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

范曉軍(1992-)，男，碩士，研究方向為機會網絡；劉林峰，博士，副教授，研究方向為機會網絡。

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