劉 云,顧 群
(1.南通大學(xué)杏林學(xué)院,江蘇啟東 226236;2.南通大學(xué),江蘇南通 226019)
在2003 年召開(kāi)的汽車(chē)通信標(biāo)準(zhǔn)化會(huì)議上,一個(gè)全新的概念——車(chē)載Ad hoc 網(wǎng)絡(luò)(Vehicular Ad hoc Networks,簡(jiǎn)稱(chēng)VANETs)應(yīng)運(yùn)而生。VANETs 技術(shù)在這個(gè)新興領(lǐng)域的相關(guān)研究稱(chēng)為車(chē)聯(lián)網(wǎng)技術(shù),路由協(xié)議作為車(chē)聯(lián)網(wǎng)技術(shù)中的關(guān)鍵技術(shù)得到了國(guó)內(nèi)外研究人員的廣泛關(guān)注。國(guó)外對(duì)VANETs 的相關(guān)研究開(kāi)始比較早,文獻(xiàn)[1] 改進(jìn)了VANETs 路由協(xié)議中獲得相鄰位置的方法,研究了一種自適應(yīng)更新策略。文獻(xiàn)[2]介紹了一種預(yù)測(cè)地理路由協(xié)議(PGRP),每輛車(chē)根據(jù)車(chē)輛的方向和角度為其鄰居賦予重量。文獻(xiàn)[3]介紹了一種在VANETs 城市場(chǎng)景中進(jìn)行路由協(xié)議可靠仿真的方法。2004 年以后,我國(guó)各高校和研究機(jī)構(gòu)開(kāi)始對(duì)VANETs 及其關(guān)鍵技術(shù)展開(kāi)研究。文獻(xiàn)[4]引入粒子群算法對(duì)VANET 網(wǎng)絡(luò)的GPSR 路由協(xié)議進(jìn)行改進(jìn)。文獻(xiàn)[5]分析了車(chē)載自組織網(wǎng)絡(luò)中GPSR 路由算法存在的缺陷,提出了改進(jìn)措施。文獻(xiàn)[6]分別對(duì)通信半徑相同情況下和通信半徑不同情況下的GPSR 路由協(xié)議進(jìn)行了改進(jìn),提高了服務(wù)質(zhì)量。
源結(jié)點(diǎn)在轉(zhuǎn)發(fā)data 數(shù)據(jù)包前,首先判斷是否存在最靠近目的地的下一跳鄰結(jié)點(diǎn)。遍歷鄰居列表,如果源結(jié)點(diǎn)可以查找到距離目的地結(jié)點(diǎn)最近的下一跳結(jié)點(diǎn),則選擇貪婪轉(zhuǎn)發(fā)策略對(duì)數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā),如圖1 所示,圖中結(jié)點(diǎn)S要向結(jié)點(diǎn)D發(fā)送數(shù)據(jù)包,以結(jié)點(diǎn)S為圓心的圓內(nèi)所有結(jié)點(diǎn)是結(jié)點(diǎn)S的下一跳鄰結(jié)點(diǎn),通過(guò)計(jì)算可知下一跳結(jié)點(diǎn)K距目的結(jié)點(diǎn)D最近。
圖1 貪婪轉(zhuǎn)發(fā)情況
若源結(jié)點(diǎn)遍歷完鄰居結(jié)點(diǎn)列表后無(wú)法找到距離目的地結(jié)點(diǎn)最近的下一跳結(jié)點(diǎn),則調(diào)用修正轉(zhuǎn)發(fā)算法。如圖2 所示,結(jié)點(diǎn)X在進(jìn)行貪婪轉(zhuǎn)發(fā)時(shí),結(jié)點(diǎn)W和結(jié)點(diǎn)Y到達(dá)目的結(jié)點(diǎn)D的距離都比結(jié)點(diǎn)X到結(jié)點(diǎn)D遠(yuǎn),不符合貪婪轉(zhuǎn)發(fā)規(guī)則,無(wú)法確定轉(zhuǎn)發(fā)數(shù)據(jù)包的下一跳結(jié)點(diǎn),此時(shí)需要調(diào)用修正策略進(jìn)行data 包轉(zhuǎn)發(fā)。
圖2 修正轉(zhuǎn)發(fā)情況
綜合考慮下一跳結(jié)點(diǎn)與目的地之間的距離和下一跳結(jié)點(diǎn)的信任值,選擇具有最大權(quán)重的下一跳結(jié)點(diǎn)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。結(jié)點(diǎn)的權(quán)重根據(jù)其與目的地的距離和結(jié)點(diǎn)信任值計(jì)算。
基于地理位置和結(jié)點(diǎn)信任值的路由算法在傳輸數(shù)據(jù)時(shí),首先要通過(guò)信標(biāo)廣播獲得目的地結(jié)點(diǎn)的地理位置和鄰居結(jié)點(diǎn)的地理位置,然后結(jié)點(diǎn)根據(jù)收集到的地理位置信息選擇調(diào)用轉(zhuǎn)發(fā)算法進(jìn)行數(shù)據(jù)包轉(zhuǎn)發(fā)。目的地結(jié)點(diǎn)定期廣播(sink)包,每個(gè)結(jié)點(diǎn)在收到sink 包后更新自己的目的地列表。當(dāng)結(jié)點(diǎn)要發(fā)送數(shù)據(jù)時(shí),就會(huì)去自己的目的地列表里進(jìn)行查找目標(biāo)結(jié)點(diǎn)的地理位置。源結(jié)點(diǎn)通過(guò)信標(biāo)(beacon)包的周期性互傳可以得知其一跳通信范圍內(nèi)所有鄰居結(jié)點(diǎn)的位置信息,每個(gè)結(jié)點(diǎn)在收到beacon 包后更新自己鄰居結(jié)點(diǎn)信息。若一個(gè)結(jié)點(diǎn)在一定的時(shí)間間隔內(nèi)(本方案將此時(shí)間設(shè)為常量DEFAULT_GPSR_TIMEOUT)沒(méi)有接收到某一個(gè)鄰居結(jié)點(diǎn)的beacon 包信息,則結(jié)點(diǎn)會(huì)認(rèn)為該鄰居結(jié)點(diǎn)已經(jīng)移出了結(jié)點(diǎn)的通信范圍,把該鄰居結(jié)點(diǎn)的信息從鄰居列表中刪除。由于車(chē)輛結(jié)點(diǎn)始終處于高速運(yùn)動(dòng)中,在進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)網(wǎng)絡(luò)拓?fù)渲朽従雨P(guān)系不穩(wěn)定,這可能導(dǎo)致下一跳結(jié)點(diǎn)在收到發(fā)送結(jié)點(diǎn)發(fā)來(lái)的數(shù)據(jù)包之前先離開(kāi)傳輸范圍,所以需要對(duì)未來(lái)鄰居結(jié)點(diǎn)的位置進(jìn)行預(yù)測(cè)。假設(shè)存在一個(gè)最大允許距離λ×ds,d,當(dāng)ds,b≤λ×ds,d時(shí),下一跳在接收到發(fā)送結(jié)點(diǎn)發(fā)來(lái)的數(shù)據(jù)包之前一般不會(huì)超出其所在的傳輸范圍。其中,ds,b表示發(fā)送結(jié)點(diǎn)s(xs,ys)和下一跳結(jié)點(diǎn)B(xb,yb)之間的距離,ds,b計(jì)算公式如式(1)所示
式中:ds,b表示發(fā)送結(jié)點(diǎn)s(xs,ys)和目的結(jié)點(diǎn)D(xd,yd)之間的距離,ds,d計(jì)算公式如式(2)所示
λ 為常量。遍歷鄰居結(jié)點(diǎn)列表,將鄰居結(jié)點(diǎn)列表中處于最大允許范圍內(nèi)的所有結(jié)點(diǎn)放入下一跳允許結(jié)點(diǎn)列表。
在進(jìn)行data 數(shù)據(jù)包轉(zhuǎn)發(fā)時(shí),路由算法使用兩種轉(zhuǎn)發(fā)策略,貪婪轉(zhuǎn)發(fā)策略和修正轉(zhuǎn)發(fā)策略。轉(zhuǎn)發(fā)的具體過(guò)程如下。
Step1:判斷當(dāng)前結(jié)點(diǎn)是否是目的地結(jié)點(diǎn),若不是則轉(zhuǎn)step2,否則算法終止。
Step2:判斷是否存在最靠近目的地的下一跳鄰結(jié)點(diǎn),若存在則轉(zhuǎn)step3 進(jìn)入,否則轉(zhuǎn)step4。
Step3:在自己的下一跳允許列表中尋找信任值最大的結(jié)點(diǎn)作為數(shù)據(jù)轉(zhuǎn)發(fā)的下一跳結(jié)點(diǎn),下一跳結(jié)點(diǎn)接收到數(shù)據(jù)包后,轉(zhuǎn)step1。
Step4:在自己的鄰居列表中尋找具有最大權(quán)重的結(jié)點(diǎn)作為數(shù)據(jù)轉(zhuǎn)發(fā)的下一跳結(jié)點(diǎn),下一跳結(jié)點(diǎn)接收到數(shù)據(jù)包后,轉(zhuǎn)step1。結(jié)點(diǎn)的權(quán)重根據(jù)其與目的地的距離和結(jié)點(diǎn)信任值計(jì)算。當(dāng)這2 個(gè)因子結(jié)合時(shí),這2 個(gè)因子的權(quán)重由w1和w2表示,且w1+w2=1。權(quán)重計(jì)算公式如式(3)所示
式中:dk,d表示下一跳k(xk,yk)和目的地D(xd,yd)之間的距離,dk,d計(jì)算公式如式(4)所示
tv表示下一跳結(jié)點(diǎn)的信任值信息。間隔一定時(shí)間后,源結(jié)點(diǎn)再次發(fā)送data 數(shù)據(jù)包,重復(fù)上述步驟。
本文設(shè)計(jì)了一個(gè)基于地理位置和車(chē)輛信任值的車(chē)聯(lián)網(wǎng)絡(luò)路由算法,當(dāng)存在最靠近目的地的鄰居結(jié)點(diǎn)時(shí),選擇貪婪轉(zhuǎn)發(fā),否則使用修正轉(zhuǎn)發(fā)。為了研究路由算法的可行性及算法性能,使用OMNeT++仿真工具、SUMO交通仿真器和veins 框架搭建仿真環(huán)境,并對(duì)得出的結(jié)果進(jìn)行分析。其中,OMNeT++控制網(wǎng)絡(luò)模擬,SUMO 模擬實(shí)際交通場(chǎng)景,veins 協(xié)調(diào)OMNeT++和SUMO 一起工作。模擬的區(qū)域?yàn)? 000 m×5 000 m,SUMO 交通仿真器對(duì)實(shí)驗(yàn)仿真場(chǎng)景的細(xì)節(jié)描述包括:道路、車(chē)輛數(shù)量、車(chē)輛行駛規(guī)則等。
車(chē)聯(lián)網(wǎng)絡(luò)路由算法的性能指標(biāo)主要包括:平均端到端時(shí)延和丟包率,這2 個(gè)性能指標(biāo)可以反映路由算法在網(wǎng)絡(luò)中的性能。其定義如下。
平均端到端時(shí)延:源結(jié)點(diǎn)到目的結(jié)點(diǎn)的傳輸時(shí)延總和與成功接收的數(shù)據(jù)包數(shù)量之和的比值,這個(gè)性能指標(biāo)反映路由有效性。
丟包率:丟失的數(shù)據(jù)包數(shù)量之和與發(fā)送的數(shù)據(jù)包數(shù)量之和的比值,這個(gè)性能指標(biāo)反映路由可靠性。
3.3.1 仿真設(shè)計(jì)
仿真結(jié)果包括矢量仿真結(jié)果、標(biāo)量仿真結(jié)果、唯一的運(yùn)行ID 和屬性。輸出的矢量仿真結(jié)果是時(shí)間序列數(shù)據(jù),可以用來(lái)記錄任何對(duì)獲得模型在仿真期間運(yùn)行的具體情況有幫助的數(shù)據(jù)。在omnetpp.ini 文件中加入語(yǔ)句“**.vector-recording = true”,啟用矢量記錄。標(biāo)量結(jié)果記錄在recordScalar()函數(shù)調(diào)用中,這種調(diào)用通常在finish 模塊中完成,若要啟用標(biāo)量記錄則需在omnetpp.ini 文件中加入語(yǔ)句“**.scalar-recording =true”。
運(yùn)行仿真程序,仿真結(jié)束后在results 文件夾下會(huì)保存新生成的結(jié)果文件*.sca 和*.vec。雙擊打開(kāi)*.sca文件或*.vec 文件會(huì)生成一個(gè)*.anf 分析文件,如圖3所示。接下來(lái)就是對(duì)*.anf 文件獲得的數(shù)據(jù)進(jìn)行分析,得到當(dāng)前rou.xml 文件描述情景下路由算法的端到端時(shí)延和丟包率。
圖3 *.anf 分析文件
3.3.2 車(chē)輛結(jié)點(diǎn)數(shù)量對(duì)算法性能的影響
仿真參數(shù)配置:設(shè)置仿真區(qū)域?yàn)? 000 m×5 000 m,數(shù)據(jù)鏈路(MAC)層采用IEEE 802.11p 協(xié)議,數(shù)據(jù)流配置為車(chē)載通信仿真框架(Veins)生成的data 數(shù)據(jù)流,每間隔5 s 開(kāi)始發(fā)送一次data 數(shù)據(jù)包,基于實(shí)際拓?fù)鋱D的車(chē)輛運(yùn)動(dòng)場(chǎng)景由SUMO 生成,仿真過(guò)程中依次隨機(jī)放入15、20、25、30、35、40 個(gè)結(jié)點(diǎn)進(jìn)行仿真,設(shè)置結(jié)點(diǎn)的最大速度為14 m/s(50.4 km/h),配置仿真時(shí)間為2 000 s。在網(wǎng)絡(luò)內(nèi)車(chē)輛結(jié)點(diǎn)最大速度相同的情況下,車(chē)輛結(jié)點(diǎn)數(shù)目不同,對(duì)每一種情況進(jìn)行多次實(shí)驗(yàn),最后取多次實(shí)驗(yàn)結(jié)果的平均值。
圖4 是車(chē)輛結(jié)點(diǎn)數(shù)目不同的情況下路由算法的平均端到端時(shí)延對(duì)比圖。從圖4 中可以發(fā)現(xiàn)隨著車(chē)輛結(jié)點(diǎn)數(shù)目的增加,平均端到端時(shí)延逐漸減小。這是因?yàn)殡S著網(wǎng)絡(luò)內(nèi)車(chē)輛結(jié)點(diǎn)數(shù)量的增加,結(jié)點(diǎn)的鄰居結(jié)點(diǎn)數(shù)量同時(shí)增多,結(jié)點(diǎn)之間的鄰居關(guān)系的穩(wěn)定性顯著提高,通信鏈路穩(wěn)定性增強(qiáng),平均端到端時(shí)延自然就下降了。
圖4 數(shù)目不同時(shí)端到端時(shí)延的對(duì)比圖
圖5 是車(chē)輛結(jié)點(diǎn)數(shù)目不同的情況下路由算法的丟包率對(duì)比圖。從圖5 中可以發(fā)現(xiàn),當(dāng)前實(shí)驗(yàn)仿真的各個(gè)場(chǎng)景下路由算法的丟包率均為0,這證明此路由算法是可行且可靠的。理想情況下,隨著車(chē)輛結(jié)點(diǎn)數(shù)量的增加,路由算法的丟包率應(yīng)下降。而圖5 中路由算法的丟包率始終為0,這是因?yàn)镾UMO 使用交通“流”方式“編寫(xiě)”車(chē)流文件,車(chē)輛結(jié)點(diǎn)密度一直很高,路由算法較容易找到下一跳轉(zhuǎn)發(fā)結(jié)點(diǎn)。
圖5 數(shù)目不同丟包率的對(duì)比圖
3.3.3 車(chē)輛結(jié)點(diǎn)最大速度對(duì)算法性能的影響
仿真參數(shù)配置:設(shè)置仿真區(qū)域?yàn)? 000 m×5 000 m,MAC 層采用IEEE 802.11p 協(xié)議,數(shù)據(jù)流配置為Veins 生成的data 數(shù)據(jù)流,每間隔5 s 開(kāi)始發(fā)送一次data 數(shù)據(jù)包,基于實(shí)際拓?fù)鋱D的車(chē)輛運(yùn)動(dòng)場(chǎng)景由SUMO生成,仿真實(shí)驗(yàn)中結(jié)點(diǎn)的最大速度依次設(shè)置為4m/s(14.4 km/h)、9 m/s(32.4 km/h)、14 m/s(50.4 km/h)、19 m/s(68.4 km/h)、24 m/s(86.4 km/h)、29 m/s(104.4 km/h),結(jié)點(diǎn)的數(shù)量為25,仿真時(shí)間設(shè)置為2 000 s。在網(wǎng)絡(luò)中車(chē)輛結(jié)點(diǎn)數(shù)量相同的情況下,車(chē)輛結(jié)點(diǎn)最大速度不同,對(duì)每一種情況進(jìn)行多次實(shí)驗(yàn),最后取多次實(shí)驗(yàn)結(jié)果的平均值。
圖6 是車(chē)輛結(jié)點(diǎn)最大速度不同的情況下路由算法的平均端到端時(shí)延。從圖6 中可以看出,隨著網(wǎng)絡(luò)內(nèi)車(chē)輛結(jié)點(diǎn)最大速度不斷提高,路由算法的平均端到端時(shí)延不斷增大。這是因?yàn)?,隨著網(wǎng)絡(luò)內(nèi)結(jié)點(diǎn)速度的變大,結(jié)點(diǎn)之間的地理位置關(guān)系變化更加頻繁,導(dǎo)致鄰居關(guān)系不穩(wěn)定,造成平均時(shí)延增加。
圖6 最大速度不同時(shí)端到端時(shí)延對(duì)比圖
圖7 是車(chē)輛結(jié)點(diǎn)最大速度不同的情況下路由算法的丟包率。從圖7 中可以看出,當(dāng)前實(shí)驗(yàn)仿真場(chǎng)景下的路由算法丟包率均為0。理想情況下,隨著結(jié)點(diǎn)速度的增大,路由算法丟包率應(yīng)上升。而圖7 中,路由算法始終為0,這是因?yàn)楫?dāng)前仿真場(chǎng)景下,使用flow 定義的車(chē)流中車(chē)輛結(jié)點(diǎn)始終“聚集”在一起,鄰居關(guān)系相對(duì)穩(wěn)定,網(wǎng)絡(luò)通信鏈路穩(wěn)定性較好。
圖7 最大速度不同時(shí)丟包率對(duì)比圖
本文設(shè)計(jì)了一個(gè)基于地理位置和結(jié)點(diǎn)信任值的路由算法,路由算法在傳輸數(shù)據(jù)時(shí),首先要通過(guò)信標(biāo)廣播獲得目的地結(jié)點(diǎn)的地理位置信息和鄰居結(jié)點(diǎn)的地理位置信息,然后結(jié)點(diǎn)按照收集到的地理位置信息調(diào)用貪婪轉(zhuǎn)發(fā)策略和修正轉(zhuǎn)發(fā)策略兩種路由轉(zhuǎn)發(fā)算法進(jìn)行數(shù)據(jù)包轉(zhuǎn)發(fā)。使用SUMO、OMNeT++、veins 搭建車(chē)聯(lián)網(wǎng)仿真環(huán)境,在veins 框架中編寫(xiě)并編譯本文提出的路由算法,通過(guò)實(shí)驗(yàn)仿真獲得特定情境下路由算法的平均端到端時(shí)延和丟包率。仿真結(jié)果表明,路由算法是有效可行的,且車(chē)輛結(jié)點(diǎn)數(shù)量和車(chē)輛結(jié)點(diǎn)最大速度對(duì)路由算法性能有影響。