車載傳感網中基于群特性的MaxProp路由協議改進

王雪麗 張琳娟 張 迪

1(內蒙古赤峰學院 內蒙古 赤峰 024000)2(國網河南省電力公司經濟技術研究院 河南 鄭州 450052)

車載傳感網中基于群特性的MaxProp路由協議改進

王雪麗1張琳娟2張 迪1

1(內蒙古赤峰學院 內蒙古 赤峰 024000)2(國網河南省電力公司經濟技術研究院 河南 鄭州 450052)

車載傳感網中信息傳輸面臨的主要難題是網絡間歇性連通和拓撲高度動態變化，以往常常采用機會轉發的思想設計路由協議來解決此難題。但現有的機會路由協議忽略了網絡中部分車輛節點具有群組移動的特點，從而導致協議在群組移動場景下的性能急劇下降。為此，通過對最大相遇概率路由進行改進，提出了一種基于群特性的MaxProp路由協議。該協議利用群組內成員節點之間極好的連通性，通過群內消息擴散，間接提高群內節點與群外節點之間的相遇概率，從而增加了消息轉發機會。并在ONE仿真平臺上，與其他幾種經典的機會路由協議相對比，改進后的MaxProp路由協議在消息傳輸成功率、網絡開銷比方面具有明顯提升。

車載傳感網 機會轉發 最大相遇概率路由 群組移動

0 引 言

目前，隨著我國工業與國民經濟的快速發展，城市道路上的車輛數目急劇增加，導致城市擁堵和環境問題變得日益嚴重。車載傳感器網絡VSNs(Vehicular Sensor Networks)是智能交通系統的重要組成部分[1-2]，主要由安裝在不同車輛內的無線傳感器節點自組織形成網絡，在保障行車安全[3]、城市道路監測[4-5]、提高行車效率[6]以及改善乘車質量[7]等方面具有廣泛的應用。在VSNs中，車載傳感器節點實時感知和采集行駛途中車輛自身和道路環境信息，并利用車輛專用無線通信技術將這些信息傳輸給所需用戶。

典型的車載傳感器網絡結構如圖1所示，攜帶無線傳感設備的車輛節點和路邊網關是核心成員[8]。車載無線傳感器節點能夠感知車輛內、外各種信息，如：車輛運行的內在狀態、汽車的位置、速度等車內信息，或涵蓋溫度、濕度、大氣指數的車外環境信息，以及行駛路途中交通流量、路面條件等信息。路邊網關，作為車輛用戶的無線訪問節點，具有比車載傳感節點更為強大的計算和存儲能力，在匯聚車輛傳感信息的同時，常以有線(光纖)或者寬帶無線技術接入Internet核心網，從而提供更穩定的數據傳輸通道。

圖1 車載傳感器網絡的組成

VSNs一般采用車輛間通信和車輛與路邊單元通信[9]兩種模式。車載傳感設備可選擇的無線通信技術有：Zigbee、Bluetooth、WIFI、DSRC[10-11]等。與傳統的無線傳感器網絡WSNs相比，車載傳感器網絡具有如下顯著特征：

(1) 節點資源無嚴格限制 在傳統的WSNs中，節點的計算、存儲和能量資源有限，促使眾多路由設計者將關注點集中在節能、消息隊列管理算法方面。相反，在VSNs中，車載傳感設備的硬件配置成本較高，同時也有能量補給，故節點資源無嚴格限制。

(2) 網絡拓撲高度動態變化 傳統的WSNs節點多數為靜態，很少考慮節點移動性問題。相反，在VSNs中，車輛節點具有高速移動性，導致網絡拓撲頻繁變化，使得傳統的WSNs、移動自組織網絡路由協議性能急劇下降。

(3) 網絡傳輸數據量更大 在節點數量上，二者均具有大規模部署特點。唯一不同的是VSNs傳輸的數據量大大增加了。因為VSNs中需要傳輸的信息，還包括車載攝像頭記錄的圖像、視頻流等多媒體數據。

(4) 網絡構成方式多樣化 VSNs在網絡體系結構上屬于混合型的網絡結構。在該網絡中，除了大量移動的車輛節點外，還包括部署在路邊的網關單元。一方面，移動的車輛節點通過Ad hoc方式自組織形成網絡；另一方面，車輛節點利用路邊網關接入核心網，實現推送數據或者查詢數據的功能。

由此可見，雖然車載傳感節點在硬件性能上具有優勢，但鑒于網絡間歇性連通和拓撲結構頻繁動態變化的特點，使得VSNs中的信息傳輸仍面臨著諸多問題，尤其對路由協議設計提出了很大挑戰。針對上述問題，現有的車載傳感網的路由協議大多借鑒“機會轉發”策略[12]，即，節點在未遇到合適的消息中繼節點或通信范圍內無其他節點時，暫時存儲消息，等待時機選擇性轉發。

1 經典的機會路由協議

1.1 泛洪路由協議Epidemic

Epidemic最初由Duke University的Amin Vahdat 和David Becker在文獻[13]中提出，是一種基于復制的路由機制，主要用于解決類似與網絡非實時連接的節點傳輸數據包的問題。其設計目標是盡量提高數據包的傳輸成功率和減少發送時延，在一定的時間內或者跳數內，它通過復制、擴散數據包來達到上述目的，屬于泛洪式協議[14]。該協議工作時，每個節點都會維護一個矢量表SV來記錄自身節點緩沖區存儲的數據包。當兩個節點各自進入對方的通信范圍后，將交換彼此的SV。然后，節點將采用遍歷的方式比較對方和自己的SV，找到自己緩存區沒有的消息，并向對方發送接收對方數據包的請求，最后更新自己的SV。

如圖2所示，當節點A進入節點B的通信范圍時，主動向B傳輸SVA，B對SVB“取反”運算得到(SVB)′，并將(SVB)′與SVA作邏輯“與”運算，從而獲取B未存儲數據包的ID。然后，B向A請求傳輸這些數據包，A完成傳輸后，本次傳輸結束。以此類似，B也會將自己的數據包按照上述流程向其它節點擴散。這樣，隨著車輛節點間的相遇，數據包就會像傳染病一樣在網絡中擴散。為了限制網絡中數據包的拷貝數，研究人員設置了跳數限制，當達到規定的跳數上限值時，數據包將停止發送。

圖2 兩個節點基于Epidemic的通信流程

1.2 擴散與等待協議SprayandWait

SprayandWait是由USC的ThrasyvoulosSpyropoulos等在文獻[15]中提出的，其實質也是泛洪式路由協議，但它對數據包的擴散方式定義了新的規則。該協議的工作流程分為擴散和等待兩個階段。在擴散階段，每個消息將會產生L份拷貝，且這L份拷貝將會被分發到L個中間節點上。若消息在擴散階段未傳送到目的地節點，它將直接進入等待階段。在等待階段，攜帶有該消息拷貝的中間節點將采用單一拷貝的方式向目的地節點進行直接傳輸。消息分發的整體流程如圖3所示。

圖3 Spray and Wait協議消息分發圖

假設節點N1有數據包發送給目的節點N5，且設定拷貝上限為L份。在擴散階段初期(step1)，N1與無消息拷貝的N2相遇，此時N1將一半的消息拷貝(L1=L/2)分給N2，并保留一半消息拷貝(L2=L/2)。在擴散階段中期(step2),N1與N3相遇、N2與N4相遇，按照上述規則，N1將L2/2份消息拷貝分給N3,并保留L2/2份消息拷貝；N2將L1/2份消息拷貝分給N4,并保留L1/2份消息拷貝。該過程將持續到L份拷貝被分配完畢為止，若目的節點N5仍未收到消息，則消息進入等待階段(step3)。當節點N4在之后的某一時刻與節點N5相遇時，將消息拷貝傳遞給目的節點N5，此次消息傳輸結束，N4刪除自己緩存里的消息拷貝。

1.3 歷史相遇概率路由協議PROPHET

PROPHET是由AndersLindgren，AvriDoria等在文獻[16]中提出的路由協議。研究人員認為網絡中運動節點的移動規律可以通過概率統計的方式體現出來，故在該協議中定義一個“到達概率”參數P(a,b)∈(0,1)，用來表達節點a向節點b傳輸消息成功的概率統計。鑒于消息傳輸是一個動態的過程，該參數將有兩種更新方式：

(1) 在每次傳輸成功后更新，更新公式如式(1)所示：

(1)

(2) 若節點(a，b)在很長一段時間內沒有成功傳輸消息，則與它們有關的歷史統計概率將衰減：

(2)

其中：γ∈(0,1]是衰減系數。當對Pinit和γ參數修改時，可獲得協議不同的性能表現。

1.4 最大相遇概率路由協議MaxProp

MaxProp[17]是在PROPHET協議的基礎上發展而來，不僅重新定義了更新公式，而且利用一些額外機制來提高消息的傳輸成功概率，并降低傳輸時延。其本質也是一種基于概率統計的路由協議[18]。類似的，基于相遇概率的路由算法在文獻[19]中也有提到。

在MaxProp協議中，最為重要的是利用節點過去的相遇信息，估算每個信息到達目的地節點的開銷，然后利用這些開銷值對節點存儲的消息進行排序，最后優先轉發那些最有可能到達目的地節點的消息。同時，為保證那些新產生的消息能夠得到傳輸，提出了一些相關方法來修正上述的排序算法，因此本文將該協議作為詳細說明和改進的對象。

MaxProp協議中，將根據攜帶消息的節點與其它節點的歷史相遇關系來選擇轉發節點，而不是簡單的“先進先出”(FIFO)原則。如圖4所示，MaxProp協議的核心是消息調度機制，存儲消息的緩存被分為兩個部分。跳數小于門限值t的消息，其優先級將高于跳數大于門限值t的消息；若消息所經過的跳數小于門限值，則會根據跳數來對消息進行排序，跳數愈大，優先級愈低；若消息所經過的跳數大于門限值，則會根據消息估算的開銷進行排序，開銷值愈低，優先級愈高。門限值和消息傳輸開銷的計算方法如下：

圖4 MaxProp消息調度機制示意圖

(1) 門限值t(跳數)

其值等于在消息緩存中包含第p個字節的消息(數據包)所經過的跳數。而p的值由式(3)決定。

(3)

其中，x是每次傳輸機會到來時傳輸的平均字節數，b是消息緩存的大小。

(2) 消息傳輸開銷

其估算值基于節點相遇的歷史記錄信息表。具體步驟為：

if (i第一次與其它任意節點j相遇，j∈s){

}

if(與節點k相遇){

//相遇節點對應概率加α

for(j∈s){

}

}//非第一次相遇，此時概率序列的和為1+α，歸一化處理

Step2 如果消息m位于節點i0，目的節點為ij，則節點i0將會利用Dijkstra算法計算出一條開銷最小的路徑p(i0,i1,i2,…,ij)，且消息m的開銷值如式(4)所示。

(4)

MaxProp協議根據車輛節點的移動規律和鏈路狀態信息，對緩存中的消息進行分類和排序，優先傳輸最大可能到達目的節點或網絡中新產生的消息。但該算法并不適用群組移動場景,即，將消息傳輸成功概率與節點相遇概率完全等同這一本質問題，需要對其進行進一步的優化和改進。

2 基于群特性的MaxProp協議改進

車輛群組是車載傳感網絡中大量OBU車輛節點的邏輯集合，在智慧交通網中有著廣泛的應用場景，如組隊行駛的物流運輸群組、城市公交車群組、出租車群組等。鑒于車輛群組的目的地或行駛路線的相似性，以及車隊管理的需要，網絡中車輛群組節點具有群移動的特性。但現有的車輛機會路由協議常常忽略了該特點，導致協議在群組移動場景下的性能下降。本文針對MaxProp協議進行了改進，提出了一種基于群特性的MaxProp協議。

圖5 群組外節點與群組內節點相遇示意圖

if (節點i或j中，有且僅有一個屬于某一群組){

使用HashMap做路由映射;

按著HashMap取出群組內成員;

更新所有群組的所有相遇概率統計;

計算消息開銷;

}

else{

只更新相遇兩節點的相遇概率統計;

使用Dijkstra計算消息開銷;

}

第一，利用群組內的節點之間良好的連通性，將其它群組內節點也列入了開銷較小的備選節點之內。這樣，外部節點，如節點M，在使用Dijkstra算法尋找路徑時，也會將這些組內其它節點考慮在內。其結果是，可利用的節點將會變多，且該節點與群組內的成員節點之間的路徑開銷將會減少，經過或到達這些節點的消息排序將會上升。

第二，由于在軟件實現的時候，節點增加了群組屬性，所以按照這樣的更新方式，可以認為更新的是節點與“整個”群組相遇的概率統計。

3 實驗仿真

最后，本文在網絡仿真平臺ONE[20]下，對改進后的MaxProp路由協議進行性能測試，并與原協議和其它幾種經典的機會路由協議進行對比。實驗場景設置如下：導入矩形區域大小的地圖文件后，所有車輛節點被分為兩組，并限制在地圖中的道路上移動。具體地，組1內的15個成員節點均采用群組移動模型行駛[21]，組2內的30個成員節點沒有群移動特性，均采用基于地圖文件的最短路徑移動模型行駛。

如圖6所示，在ONE仿真平臺下，節點比較密集的區域就是群組移動的節點，組編號為t，組成員之間的距離d設定為100m。協議運行時，消息的產生間隔為25～35s，通信范圍r分別為{150,170,190,220,240}。發送節點設定為群組移動節點，目的節點設為群組外節點。

由于現實生活中，常常遇到高架道路的上層車流密度較高，但速度不快，形成了群組移動模式；而下層道路車速高，車流量少，沒有群組移動特征的情況。為此，本實驗環境設置兼顧了高架道路的應用場景，可模擬上層車輛與下層車輛之間的通信，更具有實際意義。在上述實驗環境下，本文主要選擇消息傳輸成功率、網絡開銷比兩個參數，作為路由協議性能的評估指標。實驗結果分別如圖7和圖8所示。

圖7 傳輸成功率與通信范圍

圖8 網絡中的開銷比與通信范圍

圖8給出了網絡中的開銷比與節點通信范圍的關系變化曲線(其中，開銷比=網絡中傳輸的消息總數/傳輸成功的消息總數)。由圖8可知，除SprayandWait協議外，改進后的MaxProp路由協議占用網絡開銷比最少。因為改進后的MaxProp路由協議，利用車輛節點的群移動性選擇轉發節點，消息傳輸目的性更強，從而降低了整體網絡開銷。而Epidemic路由協議在傳輸數據包時比較盲目，需要占用更多的網絡資源；其它協議僅僅采用了一些計算路徑的算法，只能降低一部分不必要的消息傳輸開銷。SprayandWait協議在消息擴散后，直接進入等待狀態，網絡開銷極少(開銷比在4左右，其它協議均大于100)。

綜上所述，經過改進后的MaxProp協議在群組移動模型下能獲得較高的消息傳輸成功率，并通過較低的網絡開銷完成消息傳輸，修正了原協議在群組移動模型下的不完善之處，改進了其主要性能。

4 結 語

針對車載傳感網中節點的群組移動特性，本文提出了一種基于群特性的MaxProp改進路由協議。該協議利用群組內成員節點之間極好的連通性，通過群內消息擴散，間接提高群內節點與群外節點之間的相遇概率，從而增加了消息轉發機會。最后，借助網絡仿真平臺ONE，將基于群特性的MaxProp路由協議，與原協議和其他幾種經典的機會路由協議進行對比，實驗結果表明，改進后的MaxProp路由協議能通過較低的網絡傳輸開銷，獲得較高的消息傳輸成功率，進而彌補了原有協議在群組移動應用場景下的不足。

[1]PottySP,JoseS.Decisionfusioninvehicularsensornetworksforintelligenttrafficmanagement[C]//InternationalConferenceonControl,Instrumentation,CommunicationandComputationalTechnologies.IEEE,2014:394-401.

[2]DimitrakopoulosG,BravosG,NikolaidouM,etal.Proactive,knowledge-basedintelligenttransportationsystembasedonvehicularsensornetworks[J].IetIntelligentTransportSystems,2013,7(4):454-463.

[3]ChenLW,PengYH,TsengYC.AnInfrastructure-lessFrameworkforPreventingRear-EndCollisionsbyVehicularSensorNetworks[J].IEEECommunicationsLetters,2011,15(3):358-360.

[4]MednisA,ElstsA,SelavoL.Embeddedsolutionforroadconditionmonitoringusingvehicularsensornetworks[C]//InternationalConferenceonApplicationofInformationandCommunicationTechnologies.IEEE,2012:1-5.

[5]ReshiAA,ShafiS,KumaravelA.VehNode:WirelessSensorNetworkplatformforautomobilepollutioncontrol[C]//IEEEConferenceonInformation&CommunicationTechnologies,2013:963-966.

[6]ZhangL,GaoD,FohCH,etal.ASurveyofAbnormalTrafficInformationDetectionandTransmissionMechanismsinVSNs[J].InternationalJournalofDistributedSensorNetworks,2014,10(2014):1-13.

[7] 李蓉,宋飛,張琳娟.基于VANET叫車系統的路由算法研究[J].計算機應用與軟件,2015,32(5):153-156.

[8] 李旭.車載傳感器網絡的應用及關鍵技術研究[D].上海:上海交通大學,2009.

[9]FernandezJA,BorriesK,ChengL,etal.Performanceofthe802.11pPhysicalLayerinVehicle-to-VehicleEnvironments[J].IEEETransactionsonVehicularTechnology,2012,61(1):3-14.

[10]BazziA,MasiniBM,ZanellaA,etal.Vehicle-to-vehicleandvehicle-to-roadsidemulti-hopcommunicationsforvehicularsensornetworks:Simulationsandfieldtrial[C]//IEEEInternationalConferenceonCommunicationsWorkshops.IEEE,2013:515-520.

[11]FriesenM,JacobR,GrestoniP,etal.VehicularTrafficMonitoringUsingBluetoothScanningOveraWirelessSensorNetwork[J].CanadianJournalofElectrical&ComputerEngineering,2014,37(3):135-144.

[12]ZhangL,GaoD,ZhangS.Areliableandlightweightopportunisticroutingprotocolforinter-regiondatagatheringinVSNs[C]//WirelessandOpticalCommunicationConference,2013:399-404.

[13]VahdatA,BeckerD.Epidemicroutingforpartiallyconnectedadhocnetworks[R].TechnicalReportCS-2000-6,DepartmentofComputerScience,DukeUniversity,2000.

[14]LimKW,JungWS,KoYB.Multi-HopDataDisseminationwithReplicasinVehicularSensorNetworks[C]//VehicularTechnologyConference,2008.VTCSpring2008.IEEE.IEEE,2008:3062-3066.

[15]SpyropoulosT,PsounisK,RaghavendraCS.Sprayandwait:anefficientroutingschemeforintermittentlyconnectedmobilenetworks[C]//ACMSIGCOMMWorkshoponDelay-TolerantNETWORKING.ACM,2005:252-259.

[16]LindgrenA,DoriaA,SchelenO.MobiHocPoster:Probabilisticroutingprotocolinintermittentlyconnectednetworks[J].ACMSIGMOBILEMobileComputingandCommunicationsReview,2003,7(3):19-20.

[17]BurgessJ,GallagherB,JensenD.MaxProp:RoutingforVehicle-BasedDisruption-TolerantNetworks[C]//Proceedings-IEEEINFOCOM,2006,6:1-11.

[18] Tong H,Wu X,Zheng J.A destination information based probabilistic routing protocol for vehicular sensor networks[C]//IEEE International Conference on Communications.IEEE,2013:1419-1423.

[19] Wang N,Sun Z,Cruickshank H.A Reliable and Efficient Encounter-Based Routing Framework for Delay/Disruption Tolerant Networks[J].IEEE Journal of Sensors,2015,15(7):4004-4018.

[20] Keranen A,Ott J,Karkkainen T.The ONE simulator for DTN protocol evaluation[C]//International Conference on Simulation TOOLS and Techniques for Communications,Networks and Systems,Simutools 2009,Rome,Italy,March,2009.

[21] 彭輝,沈林成.一種Ad Hoc網絡群組移動模型[J].軟件學報,2008,19(11):2999-3010.

IMPROVEMENT OF MAXPROP ROUTING PROTOCOL BASED ON
GROUP FEATURES IN VSNS

Wang Xueli1Zhang Linjuan2Zhang Di1

1(ChifengUniversity,Chifeng024000,InnerMongolia,China)2(StateGridHenanEconomicResearchInstitute,Zhengzhou450052,Henan,China)

The main problem of information transmission in VSNs is intermittent network connectivity and highly dynamic topology. In the past we often used the idea of forwarding the design of routing protocols to solve this problem. However, the existing opportunistic routing protocol ignores the features of some nodes in the network with group mobility, which leads to a sharp decrease of the performance of the protocol in the group moving scene. To solve this problem, a MaxProp routing protocol based on group features is proposed by improving the maximum probability of encounter. This protocol increases the message forwarding opportunities by increasing the probability of encounter between the nodes in the group and the external nodes indirectly through the inter-group message diffusion by using the excellent connectivity among the members of the group. In the ONE simulation platform, compared with other several classical opportunistic routing protocols, the improved MaxProp routing protocol has a significant improvement in message transmission success rate and network overhead ratio.

Vehicular sensor networks Opportunistic forwarding MaxProp routing Group mobility

2016-05-26。內蒙古自治區自然科學基金項目(2013MS0916)。王雪麗，講師，主研領域：物聯網。張琳娟，博士。張迪，講師。

TP3

A

10.3969/j.issn.1000-386x.2017.05.044