突發事件下機會網絡節點移動模型研究

王霞,李旭宏，張偉，潘文文，徐濤

(1.棗莊學院信息科學與工程學院，山東棗莊　277160；2.南京大學計算機科學系,江蘇南京　210000)

?

突發事件下機會網絡節點移動模型研究

王霞1，2,李旭宏1，張偉1，潘文文1，徐濤1

(1.棗莊學院信息科學與工程學院，山東棗莊277160；2.南京大學計算機科學系,江蘇南京210000)

[摘要]針對地震、水災、強熱帶風暴等突發事件下固定網絡通信設施可能被摧毀而無法正常工作的情況，提出突發情況下機會網絡節點移動模型與相應路由算法.模擬實際的災后場景，分析各移動節點的移動特征，構建災后節點移動模型，并對節點之間的協作性進行研究，提出適合的鄰域協作路由算法，仿真結果說明基于鄰域的節點移動模型及路由算法適用于災后網絡通信.

[關鍵詞]機會網絡；節點移動模型；災后場景；移動特征；鄰域協作路由算法

0引言

地震、火災等災難性突發事件往往引起大規模的網絡中斷，這給災后的救援工作帶來了很大困難.而傳統的互聯網絡很難在短時期內正常恢復使用，機會網絡以其節點移動性和通信的隨機性等特點，適用于災后暫時性網絡通信.將機會網絡應用于災后暫時性通信系統的構建，將會給災后的救援工作帶來很大的幫助.

機會網絡是一種不需要源節點和目的節點存在完整鏈路，利用節點移動帶來的相遇機會實現通信的網絡.機會網絡應用于災后應急通信的關鍵是建立災后節點移動模型和構建相應路由算法.目前國內外都沒有建立針對災后應急通信的節點移動模型；機會網絡路由協議大多都處于研究之中.如何構建災后應急通信的節點移動模型，如何根據災后通信節點的移動特征，設計適合的路由算法使得各點利用有限的資源進行協作完成數據轉發是目前急需解決的兩大問題.

本文對災后場景中的節點分布進行模擬，對節點移動特征進行分析統計，研究出災后節點移動模型；并在現有路由協議的基礎上，對節點集進行區域劃分并實現基于鄰域的節點協作式路由算法.

1國內外研究現狀

目前，機會網絡主要應用于車載網絡、手持設備網絡、野生動物追蹤、偏遠地區網絡傳輸等領域，針對災后應急通信的研究目前還比較少.

節點移動模型研究是當前機會網絡理論研究的熱點之一.節點移動模型[1]描述了移動節點的移動模式，包括節點位置、節點移動速度、以及加速度等特征的變化.目前，針對機會網絡節點移動模型的研究主要包括以下幾種[2]：

(1)基于統計的實際移動模型：采用統計的方法收集實際環境中節點的運動軌跡，從而研究節點移動特征而生成的移動模型.MIT 的Reality Mining 項目[3]、UCSD 的Wireless Topology Discovery[4]、劍橋大學的Haggle 項目[5]都采用統計的方法對實際節點移動模式進行研究并生成了相應的機會網絡節點移動模型.

(2)獨立同分布的理論移動模型：目前存在3 個經典的獨立同分布移動模型---- Random Walk[6](RW)的原型是物理學中的布朗運動模型；Random Way Point[7](RWP) 是一種個體移動模型；Random Direction[8](RD)是一種更穩定的隨機模型，更加符合實際節點運動軌跡.

(3)基于社區的移動模型：文獻[9]通過分析發現，實際節點的移動具有社區特性.Musolesi 等人[10]提出了一種基于社區的移動模型；在此基礎上， Spyropoulos 等人[11]提出了時變的社區移動模型.

綜合國內外機會網絡節點移動模型的研究，具有如下特點：(1)由于機會網絡尚未大規模應用，對其實用性仍需考證；(2)很大程度上，節點移動模型和路由算法分離開研究，使得路由算法缺乏對具體場景的針對性.

本文將模擬實際場景中災后節點的移動變化，分析位置變化的特征，在社區移動模型的基礎之上根據災后場景下節點移動的特征對節點進行區域劃分，構建災后節點移動模型，并根據各移動節點的協作特征，研究出適合的節點鄰域協作路由算法.

2突發事件下機會網絡節點移動模型構建

根據對地震等災后通信場景進行模擬，我們發現，地震后網絡中斷，各個村子或社區的網絡成為一個個網絡孤島，很難連成一個完整的城市網絡.但根據統計分析，災后的通信節點仍具有社區性特征，只是各個社區間的移動節點發生了改變[12].

根據對真實場景進行模擬，搭建出基于區域的災后節點移動模型，模型具有以下特征：

(1)移動節點位置特征：移動節點具有區域聚集性，比如一個村落，或者一個社區，但同時又具有移動區域的局限性，因為災難的發生，移動幅度很小，或者幾乎沒有.但是根據災難發生后移動網絡的特征，一般在搜救的過程中，會出現頻繁出沒在各個區域的搜救節點，比如搜救飛機或者其他快速搜救工具帶來的移動節點，這一類移動節點大多具有基點的作用，但比基點具有快速移動性的特點，其活動范圍和活動頻率要活躍的多.

圖1　基于區域的移動節點模型

(2)節點移動數學模型的構建：通過對節點位置特征和移動特征進行研究，對移動節點劃分區域，建立了基于區域的移動節點數學模型，因為區域間的節點移動僅限于小范圍內移動，所以提出了鄰域的概念，并且根據節點往來的頻繁度提出親密鄰域的概念，其中在搜救的過程中，一般會出現頻繁出現在各個區域的搜救節點，稱之為活躍節點.節點移動數學模型的構建主要涉及到節點、區域、鄰域、親密鄰域、活躍節點集、親密使者集等幾個概念以及其表示方法.具體模型如圖1所示.

節點的表示：所有移動節點MB={節點ID,目前所屬區域BZID，來自區域OZID,一定時間間隔內曾去過的區域PZID集}.

區域的表示：區域是以若干個節點為核心組成的鄰接網絡連通區域，區域以三元組Z={區域ID，{節點集ZN}，{拓撲表}}表示，其中，拓撲表包含節點協作路由表項：ZT={目的區域，鄰域集，親密使者集ZBS，生存周期T}，拓撲表告訴我們要到達目的區域，經過哪些鄰域，通過那些親密使者完成了信息轉發.

鄰域的定義：有一定節點數直接往返的兩個區域成為鄰域.

親密鄰域的定義：有一定節點數頻繁往返的兩個區域成為親密鄰域.

親密使者集：在兩個親密鄰域內頻繁往返的節點，包括活躍節點和其他親密使者節點.

(3)節點移動模型的描述：

區域邊界的確定：區域的確定以文獻[13]中社區的邊界定義為基礎，以村莊或者生活社區為基礎區域邊界.在特殊災難情況下，比如森林火災等，以地域為邊界.區域邊界的確定有移動節點自行搜索完成，采用觸發更新式原則進行區域內部節點集的更新.

節點屬性描述：在一個時間點，每一個節點的從屬區域只有一個，這個從屬區域可能隨時改變，節點屬性包含以下內容：

節點ID：本節點的標識符.

目前所屬區域BZID：用以標識本節點目前的位置.

來自區域OZID：用以標識本節點最近的來源ID.

一定時間間隔內曾去過的區域ID集：這個集合包含在一定時間間隔內，本節點曾到過的區域的區域ID，用以標識本節點的活躍程度.一定時間間隔內曾去過的區域由一個二元組{區域ID，頻繁度PD}構成，頻繁度屬性PD的值表示在一定時間間隔內本節點到這個區域的次數，根據災后通信的特點，這個時間間隔一般定義為12-24小時，在這段時間間隔內PD值大于等于3就說明，這個區域與節點從屬區域為親密鄰域，且此節點為二者之間的親密使者.各概念之間關系如圖2所示.

圖2　節點移動模型各概念之間關系圖

3鄰域協作路由算法研究

基于鄰居的路由算法在國內以后不少研究成果[14-16].本文在節點移動數學模型和已有路由算法的基礎上，提出了基于鄰域協作的路由算法，具體內容如下：

(1)區域的節點集和拓撲結構的更新：節點定期探尋其通信范圍內其他節點位置，并根據洪泛的方法迅速建立區域的邊界，確定區域內容的節點集合；節點不停搜索鄰近新節點，如有新節點加入，觸發更新區域邊界和節點集，從而完成區域的邊界界定和拓撲結構的定期更新.具體流程如圖3所示.

圖3　區域邊界與拓撲表更新過程

圖4　基于鄰域的協作路由算法流程

(2)路由算法的改進：在文獻[17-18]的路由算法基礎上進行算法改進，親密鄰域之間通過與親密使者的相遇進行通信；一般鄰域之間擴大副本的轉發范圍，轉發給有限個(一般是三個)親密使者，通過親密鄰域加大到達目的節點的幾率.每個數據包具有一定的生存周期，告訴每個親密使者數據包的生存時間，一般以跳數(即所經過區域的個數)表示，超過10個區域，就會將此數據包丟棄，以免浪費網絡資源.具體算法流程如圖4所示.

4實驗平臺構建和算法驗證

針對具有活躍節點和沒有活躍節點的兩種節點移動模型，進行.

借助C++語言對域內和域間路由算法進行實現，并在Matlab上實現對算法性能的展現.

(1)具有活躍節點的機會網絡節點移動模型下，平均90%的數據包可以通過活躍節點輾轉轉發到目的區域的目的節點，這一成功率隨著網絡范圍的擴大而不斷減小，如表1所示.

表1　模型一不同實驗參數下數據包轉發成功率

(2)在模擬災后通信狀況下不具有活躍節點的機會網絡節點移動模型下，成功率明顯降低，因為本身節點的移動范圍有限，具有親密特性的鄰域明顯減少，從而轉發成功率也明顯降低，在定義每個區域的親密鄰域個數為3，親密使者活躍基本活躍在相鄰兩個鄰域之間的前提下，數據包轉發成功率如表2所示.

表2　模型二不同實驗參數下數據包轉發成功率

5結語

本文將機會網絡應用于災后應急通信，提出一種新型的節點移動模型---基于鄰域的節點移動模型；并通過對現有路由算法進行改進，提出適合于災后移動節點通信的基于鄰域的協作路由算法，以提高到達目的節點的成功率.

參考文獻

[1]徐鑫鑫,王玲,張衡陽.無線移動Ad hoc網絡移動模型研究[J].計算機應用研究,2009, 26(3):804-808.

[2]熊永平,孫利民,牛建偉,等.機會網絡[J].Journal of Software, 2009, 20(1):124-137.

[3]Eagle N, Pentland A.Reality mining: sensing complex social systems [J].Personal Ubiquitous Computing.2006, 10(4):255-268.

[4]UCSD. Wireless topology discovery project, 2004,http://sysnet.ucsd.edu/wtd/wtd.html.

[5]Diot C. Haggle project. 2004,http://www.haggleproject.org.

[6]Broch J, Maltz DA, Johnson DB, Hu Y, Jetcheva J. A performance comparison of multi-hop wireless ad hoc network routing protocols[J].MobiCom’98. 1998:85-97.

[7]CAMP T, BOLENG J, DAVIES V. A survey of mobility models for ad hoc network research [J]. Wireless Communications and Mobile Computing, 2002, 2(5):483-502.

[8]ROYER EM, MELLIAR-SMITH PM, MOSER LE. An analyisis of the optimum node density ofr ad hoc mobile network [J]. Proc of IEEE International Conference on Communications. 2001:857-861.

[9]Pan H, Chaintreau A, Scott J, Gass R, Crowcroft J, Diot C. Pocket switched networks and human mobility in conference environments[J]. In: Proc. of the 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking. Philadelphia: ACM. 2005: 244-251.

[10]Musolesi M, Mascolo C. A community based mobility model for ad hoc network research [J]. In: Proc. of the 2nd Int’l Workshop on Multi-Hop Ad Hoc Networks: From Theory to Reality. New York: ACM.2006:31-38.

[11]Spyropoulos T, Psounis K, Raghavendra CS. Performance analysis of mobility-assisted routing [J]. In: Proc. of the 7th ACM Int’l Symp. on Mobile Ad Hoc Networking and Computing. 2006:49-60.

[12]孫踐知,韓忠明,陳丹,等.災難場景下基于分組策略的機會網絡路由算法[J].計算機工程，2011, 37(23):79-83.

[13]牛建偉,周興,劉燕,等.一種基于社區機會網絡的消息傳輸算法[J].計算機研究與發展，2009, 46(12):2068-2075.

[14]郭陸.基于動態社會關系的機會路由研究[J].計算機應用與軟件，2013, 30(11):180-183.

[15]劉亞翔,高媛,喬晉龍,等.機會社會網絡中基于社區的消息傳輸算法[J].計算機應用，2013, 33(5):1212-1216.

[16]吳大鵬,向小華,王汝言,等.節點歸屬性動態估計的機會網絡社區檢測策略[J].計算機工程與設計，2012, 33(10):3673-3677.

[17]李東生,楊志義,郭斌,等.基于機會網絡的社會性活動組織研究[J].計算機科學，2013, 40(2):35-39.

[18]周強,應晶,吳明暉. 基于特征分類的機會網絡多因素預測路由[J]. 浙江大學學報(工學版),2010, 44(3):413-418.

[責任編輯：呂海玲]

A Scheme of Opportunistic Networks Nodes Mobile Model on Emergency

WANG Xia1,2,LI Xu-hong1,ZHANG Wei1,PAN Wen-wen1,XU Tao1

(1.College of Information, Zaozhuang University, Zaozhuang 277160,China;2. Departiment of Computer, Nanjing University, Nanjing 210000,China)

Abstract：Disasters result in network communication was destroyed. The characteristics of survivability, Self-organization and mobility made the opportunistic networks apply to network communication after disaster. Neighbour-based nodes mobile model and message transmission scheme are proposed which utilizes frequent moving of nodes among the neighbour areas to dispatch the message. Simulation results show that this scheme can balance well the trade off between delivery ration and resource consumption in opportunistic network.

Key words：opportunistic networks; nodes mobile model; scenes of devastation; mobile characteristic; neighbours-based routing algorithm

[中圖分類號]TP393.03

[文獻標識碼]A

[文章編號]1004-7077(2016)02-0103-06

[作者簡介]王霞(1978-)，女，山東棗莊人，棗莊學院信息科學與工程學院講師，工學碩士，南京大學計算機科學系2015級在讀博士研究生，主要從事無線網絡、RFID射頻識別系統的研究.

[基金項目]山東省高等學校科技計劃項目(項目編號：J12LN53).

[收稿日期]2016-01-17