基于活躍度和任務(wù)的目標(biāo)導(dǎo)向VANETs路由算法*

李文芳，董龍明，郝麗波，李宏策

（1.湖南機(jī)電職業(yè)技術(shù)學(xué)院，長(zhǎng)沙 410151；2.陸軍駐南京地區(qū)軍事代表室，南京 210000）

基于活躍度和任務(wù)的目標(biāo)導(dǎo)向VANETs路由算法*

李文芳1，董龍明2，郝麗波1，李宏策1

（1.湖南機(jī)電職業(yè)技術(shù)學(xué)院，長(zhǎng)沙 410151；2.陸軍駐南京地區(qū)軍事代表室，南京 210000）

針對(duì)車載自組織網(wǎng)絡(luò)（VANETs）中節(jié)點(diǎn)移動(dòng)速度快、節(jié)點(diǎn)任務(wù)分布不均、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不穩(wěn)定等特點(diǎn)，提出了一種基于節(jié)點(diǎn)活躍度和任務(wù)的目標(biāo)導(dǎo)向VANETs路由算法GATRA（goal-oriented routing algorithm based on activity and task）。該算法根據(jù)當(dāng)前運(yùn)動(dòng)節(jié)點(diǎn)的運(yùn)動(dòng)方向與目標(biāo)節(jié)點(diǎn)的關(guān)系，以及任務(wù)飽和程度，綜合考慮采用消息攜帶還是轉(zhuǎn)發(fā)策略，以節(jié)約傳輸平均時(shí)延。在選擇中繼節(jié)點(diǎn)時(shí)，綜合考慮鄰接節(jié)點(diǎn)的位置、運(yùn)動(dòng)速度和方向等影響因素，設(shè)計(jì)節(jié)點(diǎn)活躍度的計(jì)算方法，作為選擇中繼節(jié)點(diǎn)的策略，從而提高了消息傳輸?shù)某晒β?。仿真結(jié)果表明，與當(dāng)前典型的VANETs路由算法相比，GATRA算法在傳輸成功率和平均延遲時(shí)間上具有較大提升。

車載自組織網(wǎng)絡(luò)，目標(biāo)導(dǎo)向，活躍度，路由算法

0 引言

車 載 自 組 網(wǎng) （Vehicle Ad-Hoc Networks，VANETs）是移動(dòng)網(wǎng)絡(luò)領(lǐng)域一種新興的技術(shù)，主要面向日益龐大的汽車用戶群體，可以實(shí)現(xiàn)車與車、車與路邊基礎(chǔ)設(shè)施進(jìn)行通信，從而實(shí)現(xiàn)信息共享，有助于事故預(yù)警、交通信息查詢等多種應(yīng)用［1］。與傳統(tǒng)的網(wǎng)絡(luò)相比，VANETs具有節(jié)點(diǎn)移動(dòng)速度快、節(jié)點(diǎn)任務(wù)分布不均、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不穩(wěn)定等特點(diǎn)，因此，傳統(tǒng)的路由算法難以適用于VANETs。另外，由于VANETs應(yīng)用環(huán)境變化多端，車輛所承擔(dān)的任務(wù)和運(yùn)動(dòng)速度方向隨時(shí)間、地點(diǎn)變化而變化，從而導(dǎo)致車輛的分布密度和連通性呈機(jī)會(huì)性。VANETs這些新的特征給提供數(shù)據(jù)穩(wěn)定可靠保證的路由算法設(shè)計(jì)帶了極大挑戰(zhàn)。

國(guó)內(nèi)外研究學(xué)者針對(duì)VANETs車輛節(jié)點(diǎn)這些動(dòng)態(tài)特性分別對(duì)路由策略進(jìn)行相關(guān)的研究，根據(jù)網(wǎng)絡(luò)特性可以分為5類路由算法：基于連通［2］、基于概率［3］、基于移動(dòng)預(yù)測(cè)［4］、基于固定設(shè)施［5］和基于地理位置［6-7］。基于連通路由是采用廣播的方式，通過節(jié)點(diǎn)廣播傳遞數(shù)據(jù)包，直至數(shù)據(jù)傳遞到目的地才停止廣播，該泛洪路由控制策略相對(duì)簡(jiǎn)單，易實(shí)現(xiàn)、操作性強(qiáng)，但是會(huì)增加網(wǎng)絡(luò)負(fù)擔(dān)，容易形成網(wǎng)絡(luò)廣播風(fēng)暴，網(wǎng)絡(luò)數(shù)據(jù)傳輸效率極低?；诟怕实穆酚伤惴ㄊ轻槍?duì)VANETs拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化，利用通信呈現(xiàn)機(jī)會(huì)性，結(jié)合概率統(tǒng)計(jì)理論，通過計(jì)算無線鏈接可用時(shí)間分布，建立網(wǎng)絡(luò)傳播模型，進(jìn)行數(shù)據(jù)傳輸。基于移動(dòng)預(yù)測(cè)是采集節(jié)點(diǎn)諸如速度、方向、加速度等運(yùn)動(dòng)特征，建立預(yù)測(cè)移動(dòng)模型，進(jìn)行數(shù)據(jù)傳輸?；诠潭ㄔO(shè)施是將路邊基礎(chǔ)設(shè)施作為通信的中繼節(jié)點(diǎn)，提供數(shù)據(jù)傳輸?shù)目煽啃??；诘乩砦恢寐酚墒歉鶕?jù)節(jié)點(diǎn)的位置信息，選擇不同策略進(jìn)行貪婪轉(zhuǎn)發(fā)和周邊轉(zhuǎn)發(fā)兩種模式，具有高效、低路由開銷和良好的可擴(kuò)展性。

在VANETs的路由協(xié)議中，基于位置信息的貪婪路由算法是目前最為普遍采用的方法，如：貪婪周邊無狀態(tài)路由GPSR（Greedy Perimeter Stateless Routing）［8］和貪婪周邊協(xié)調(diào)路由GPCR（Greedy Perimeter Coordinator Routing）［7］，選擇離目標(biāo)節(jié)點(diǎn)最近且距離自身最遠(yuǎn)的鄰居節(jié)點(diǎn)作為下一跳進(jìn)行路由轉(zhuǎn)發(fā)，這種方法的優(yōu)點(diǎn)是每一跳傳遞距離最遠(yuǎn)，能減少轉(zhuǎn)發(fā)的跳數(shù)，其缺點(diǎn)是沒有考慮轉(zhuǎn)發(fā)節(jié)點(diǎn)的狀態(tài)，如活躍度和承擔(dān)任務(wù)情況，可能導(dǎo)致數(shù)據(jù)包的丟失。

本文是在貪婪路由算法基礎(chǔ)上，在移動(dòng)節(jié)點(diǎn)上設(shè)置一定大小的緩沖區(qū)來存儲(chǔ)攜帶一定數(shù)量的數(shù)據(jù)，如果節(jié)點(diǎn)當(dāng)前任務(wù)不是很飽滿，且節(jié)點(diǎn)運(yùn)動(dòng)方向是與數(shù)據(jù)包目的地址一致，則采用攜帶策略，否則綜合考慮鄰接節(jié)點(diǎn)的位置、運(yùn)動(dòng)速度和方向等影響因素，設(shè)計(jì)節(jié)點(diǎn)活躍度的計(jì)算方法，作為選擇中繼節(jié)點(diǎn)的策略。這種方法能夠一方面有效減少數(shù)據(jù)傳輸?shù)闹修D(zhuǎn)跳數(shù)，節(jié)約傳輸時(shí)延；另一方面，傳輸和轉(zhuǎn)發(fā)是以目標(biāo)為導(dǎo)向，綜合節(jié)點(diǎn)承擔(dān)的任務(wù)情況，合理選擇存儲(chǔ)和轉(zhuǎn)發(fā)策略，保證消息傳輸?shù)某晒β省?/p>

1 基于活躍度和任務(wù)的目標(biāo)導(dǎo)向路由算法GATRA

基于活躍度和任務(wù)的目標(biāo)導(dǎo)向路由算法中，如何根據(jù)VANETs節(jié)點(diǎn)任務(wù)飽和程度選擇合適的數(shù)據(jù)傳輸策略，如何根據(jù)鄰居節(jié)點(diǎn)的活躍度選擇最優(yōu)的中轉(zhuǎn)節(jié)點(diǎn)，將數(shù)據(jù)從源節(jié)點(diǎn)傳輸?shù)侥繕?biāo)節(jié)點(diǎn)，是路由算法的關(guān)鍵?？梢粤炕硎緸槠渲校簂為當(dāng)前節(jié)點(diǎn)攜帶的消息個(gè)數(shù)，L為節(jié)點(diǎn)緩沖區(qū)的大小，τ∈[0，1]。τ取不同值時(shí)，可以描述節(jié)點(diǎn)承擔(dān)任務(wù)的繁重程度，從而采取不同的策略：

當(dāng)τ∈[0.8，1]時(shí)，節(jié)點(diǎn)承擔(dān)通信任務(wù)很重，一旦有鄰居節(jié)點(diǎn)就需要將攜帶的消息轉(zhuǎn)發(fā)出去；

當(dāng)τ∈[0.5，0.8]時(shí)，節(jié)點(diǎn)承擔(dān)通信任務(wù)適中，有方向一致的鄰居時(shí)將攜帶的消息轉(zhuǎn)發(fā)出去，同時(shí)可以接受方向一致的中轉(zhuǎn)消息；

當(dāng)τ∈[0，0.5]時(shí)，節(jié)點(diǎn)承擔(dān)通信任務(wù)很少，可以存儲(chǔ)待發(fā)消息和接受其他節(jié)點(diǎn)的消息。

車載移動(dòng)節(jié)點(diǎn)通過環(huán)境預(yù)測(cè)和傳輸日志可以對(duì)目標(biāo)的位置和運(yùn)動(dòng)速度進(jìn)行預(yù)測(cè)，判斷目標(biāo)的方位，并與當(dāng)前位置和運(yùn)動(dòng)速度進(jìn)行對(duì)比，對(duì)目標(biāo)導(dǎo)向路由算法進(jìn)行量化，使數(shù)據(jù)朝目標(biāo)方向進(jìn)行傳輸。

可以根據(jù) Δxsd和的值判斷目標(biāo)節(jié)點(diǎn)與節(jié)點(diǎn)的將來距離情況。節(jié)點(diǎn)在x軸方向上距離和速度表示含義如下，節(jié)點(diǎn)在y軸方向上距離和速度同x軸方向。

當(dāng) Δxsd＞0 時(shí)：

1.1 攜帶-中轉(zhuǎn)策略

車載自組網(wǎng)中，為了保證消息可靠傳輸，車載移動(dòng)節(jié)點(diǎn)設(shè)置一定的緩沖區(qū)，用來暫時(shí)存儲(chǔ)待發(fā)或接受的數(shù)據(jù)。當(dāng)周圍環(huán)境有合適的相鄰節(jié)點(diǎn)時(shí)，發(fā)送這些數(shù)據(jù)，可以節(jié)點(diǎn)處在孤立的環(huán)境或者周圍節(jié)點(diǎn)通信任務(wù)過重?zé)o法中轉(zhuǎn)數(shù)據(jù)時(shí)，保證數(shù)據(jù)不丟失。攜帶-中轉(zhuǎn)策略除了考慮結(jié)點(diǎn)周圍環(huán)境因素外，還需要考慮消息目的地址與節(jié)點(diǎn)運(yùn)動(dòng)方向的關(guān)系，當(dāng)運(yùn)動(dòng)方向與目標(biāo)一致時(shí)，可以攜帶該消息，可以確保減少消息中轉(zhuǎn)的頻次，減少節(jié)點(diǎn)間傳輸?shù)难舆t，同時(shí)減少了中轉(zhuǎn)過程消息丟失的可能性，提高了消息投遞成功率。

定義1任務(wù)Task刻畫了節(jié)點(diǎn)攜帶消息的多少，

當(dāng) Δxsd＜0 時(shí)：

定義2目標(biāo)導(dǎo)向Goal刻畫了當(dāng)前節(jié)點(diǎn)距離目標(biāo)節(jié)點(diǎn)的程度，使用公式如果g∈[-1，0]表示節(jié)點(diǎn)在整體效果上距離目標(biāo)節(jié)點(diǎn)越來越近；如果g∈[0，1]表示節(jié)點(diǎn)在整體效果上距離目標(biāo)節(jié)點(diǎn)越來越遠(yuǎn)。

根據(jù)本節(jié)點(diǎn)和鄰居節(jié)點(diǎn)的任務(wù)因子和目標(biāo)導(dǎo)向因子值，節(jié)點(diǎn)可以決策采用消息攜帶策略還是中轉(zhuǎn)策略，流程圖如圖1所示。

1.2 中轉(zhuǎn)節(jié)點(diǎn)選擇策略

中轉(zhuǎn)節(jié)點(diǎn)的選擇不但可以影響消息是否能傳輸成功，同時(shí)還能影響路由算法的效率。因此，選擇合適的中轉(zhuǎn)節(jié)點(diǎn)在路由算法中尤其重要。節(jié)點(diǎn)在選擇鄰居節(jié)點(diǎn)中轉(zhuǎn)消息時(shí)，當(dāng)出現(xiàn)多個(gè)鄰居節(jié)點(diǎn)可供選擇時(shí)，需要一個(gè)合理的中轉(zhuǎn)節(jié)點(diǎn)選擇策略，選擇最合適的節(jié)點(diǎn)數(shù)據(jù)傳輸，考慮的因素有：鄰居節(jié)點(diǎn)的任務(wù)因子和目標(biāo)導(dǎo)向因子。

定義3 活躍度Activity刻畫了節(jié)點(diǎn)相對(duì)目標(biāo)節(jié)點(diǎn)的活躍程度，包括接受數(shù)據(jù)傳輸?shù)哪芰瓦\(yùn)動(dòng)特性，描述了節(jié)點(diǎn)將消息傳輸?shù)侥繕?biāo)節(jié)點(diǎn)的容易程度，可以量化表示為其中：τ為節(jié)點(diǎn)的任務(wù)因子，g為節(jié)點(diǎn)的目標(biāo)導(dǎo)向因子，ε為權(quán)重因子。

圖1 攜帶-中轉(zhuǎn)策略流程圖

1.3 算法描述

綜上分析，本文提出的GATRA路由算法具體描述如下：

①節(jié)點(diǎn)首先根據(jù)發(fā)送消息預(yù)測(cè)目的節(jié)點(diǎn)的位置、運(yùn)動(dòng)特性，如果能夠直接發(fā)送目的節(jié)點(diǎn)，則發(fā)送該消息到目的節(jié)點(diǎn)，從緩沖區(qū)刪除該消息，該輪詢結(jié)束；否則，結(jié)合自身的緩沖區(qū)情況、位置、運(yùn)動(dòng)特性，求得任務(wù)因子和目標(biāo)導(dǎo)向因子。

②根據(jù)任務(wù)因子的值和感知的鄰居節(jié)點(diǎn)情況，決策采用中轉(zhuǎn)還是攜帶策略，如果是攜帶策略，存儲(chǔ)該消息，繼續(xù)運(yùn)動(dòng)等待下一輪詢；否則，進(jìn)入③。

③當(dāng)時(shí)采用中轉(zhuǎn)策略，收集相鄰節(jié)點(diǎn)的當(dāng)前任務(wù)因子和位置運(yùn)動(dòng)特性，求得相鄰節(jié)點(diǎn)的活躍度，選擇活躍度最大的節(jié)點(diǎn)作為中繼節(jié)點(diǎn)，轉(zhuǎn)發(fā)給消息。該算法偽代碼描述如下：

2 仿真實(shí)驗(yàn)及結(jié)果分析

本文采用基于Java的DTN仿真工具ONE（Opportunistic Network Environment）［9］進(jìn)行仿真實(shí)驗(yàn)。仿真環(huán)境區(qū)域面積為：15 000 m×15 000 m，整個(gè)網(wǎng)絡(luò)由50個(gè)～200個(gè)移動(dòng)節(jié)點(diǎn)組成，節(jié)點(diǎn)的速度區(qū)間為：0 m/s～50 m/s，相當(dāng)于汽車等交通工具的速度，節(jié)點(diǎn)的通信半徑為：0 m～250 m，傳輸消息大小為：100 KB～500 KB，權(quán)重因子 ε=0.2。

圖2 平均端到端時(shí)延比較

從圖2中可以看出：當(dāng)節(jié)點(diǎn)個(gè)數(shù)增加時(shí)，3種協(xié)議平均端到端時(shí)延變化的比較。當(dāng)節(jié)點(diǎn)個(gè)數(shù)增多時(shí)，連通性更好，平均時(shí)延在減少，由于GATRA路由算法采用目標(biāo)導(dǎo)向的路由算法，在選擇路由策略時(shí)盡量向目標(biāo)運(yùn)動(dòng)方向的節(jié)點(diǎn)傳遞節(jié)點(diǎn)。圖3顯示了數(shù)據(jù)成功遞交率在不同節(jié)點(diǎn)數(shù)的情況比較，相比之下，可以看出：GATRA路由算法數(shù)據(jù)投送成功率在85%之上，由于GATRA路由算法針對(duì)不同情況采取不同的中轉(zhuǎn)-攜帶策略，減少了消息的丟失，提高了消息的遞交成功率。

圖3 數(shù)據(jù)成功投遞率比較

3 結(jié)論

本文針對(duì)車載自組織網(wǎng)絡(luò)節(jié)點(diǎn)移動(dòng)速度快、節(jié)點(diǎn)任務(wù)分布不均、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不穩(wěn)定等特點(diǎn)，提出了一種基于活躍度和任務(wù)的目標(biāo)導(dǎo)向VANETs路由算法。充分考慮了節(jié)點(diǎn)的活躍度和當(dāng)前數(shù)據(jù)傳輸任務(wù)情況，選擇任務(wù)不是很飽滿、運(yùn)動(dòng)方向與目標(biāo)移動(dòng)方向一致并活躍度高的節(jié)點(diǎn)攜帶或中轉(zhuǎn)數(shù)據(jù)，保證了路由策略的最優(yōu)化。通過仿真實(shí)驗(yàn)驗(yàn)證：該算法在數(shù)據(jù)傳輸中具有較高的數(shù)據(jù)遞交成功率和較少的時(shí)延。各種實(shí)際應(yīng)用場(chǎng)景的車載自組網(wǎng)路由優(yōu)化算法是將來下一步研究重點(diǎn)。

［1］PERKINGS C E，ROYER E M.Ad-Hoc on-demand distance vector routing［C］//Proc of IEEE Workshop on Mobile Computing Systems and Applications （WMCSA），2011：90-100.

［2］LI X，CUTHBERT L.On-demand node-disjoint multipath routing in wireless Ad-Hoc network［C］//Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks，LCN’04，Washington DC，USA，IEEE Computer Society，2004：419-420.

［3］JIANG H，GUO H，CHEN L.Reliable and efficient alarm message routing in vanet［C］//Proceeding of the 2008 International Conference on Distributed Computing Systems Workshops，ICDCSW’08，Washington DC，USA，IEEE Computer Society，2008：186-191.

［4］ABEDI O，F(xiàn)ATHY M，TAGHILOO J.Enhancing AODV routing protocol using mobility parameters in vanet［C］//Proceedings of the 2008 IEEE/ACS International Conference Society，2008：229-235.

［5］HE R，RUTAGEMWA H，SHEN X.Differentiated reliable routing in hybrid vehicular Ad-Hoc networks［C］//IEEE International Conference on Communications （ICC），2008：2353-2358.

［6］KARP B，KUNG H T.GPSR：Greedy perimeter stateless routing for wireless networks［C］//Proc.of 6th Annual International Conference on Mobile Computing and Networking，2000：243-254.

［7］DALY E，HAAHR M.Social network analysis for routing in disconnected delay-tolerant MANETs ［C］//Proceddings of ACM Mobi-Hoc，2007：32-40.

［8］LOCHERT C，MAUVE M，F(xiàn)USSLER H，et al.Geographic routing in city scenarios［J］.ACM SIGMOBLE Mobile Computing and Communications Review，2005，9（1）：69-72.

［9］KARP B，KUNG T H.GPSR：Greedy perimeter stateless routing for wireless networks［C］//Proceeding of the 6th Annual International Conference on Mobile Computing and Networking （MOBICOM’00），Boston，MA，USA，ACM，2000：243-254.

［10］KERANEN A，OTT J，KARKKAINEN T.The ONE simulator for DTN protocol evaluation［C］//SIMUTools’09：Proceedings of the 2nd International Conference on Simulation Tools and Techniques，New York，NY，USA，2009.

Activity and Task Based Goal-oriented Routing Algorithm in VANETs

LI Wen-fang1，DONG Long-ming2，HAO Li-bo1，LI Hong-ce1
（1.Hunan Mechanical and Electrical Polytechnic，Changsha 410151，China；2.Nanjing Military Representative Office of PLA Army，Nanjing 210000，China）

Nodes move rapidly and their tasks are unevenly distributed，the topology of network is instable in the vehicular ad-hoc networks.A goal-oriented routing algorithm （GATRA）is proposed based on activity and task.The algorithm chooses the carrying or forwarding of the messages，according to the saturation level of its task and the relationship between the movement direction of the current node and the target node.It can save mean delay time.When selecting a relay node，the computation of the node activity is designed as selection policy of the relay node，according to the impact factors such as the location，velocity and direction of the adjacent nodes.Hence，it can improve the success rate of message transmission.In the end，the simulation results show that compared with other typical routing algorithms，GATRA can performs better on transmission rate and mean delay time.

vehicle Ad-Hoc networks，goal-oriented，activity，routing algorithm

TP316.4

A

10.3969/j.issn.1002-0640.2017.07.026

1002-0640（2017）07-0119-05

2016-05-05

2016-06-07

湖南省教育廳高等學(xué)?？茖W(xué)研究項(xiàng)目（15C0491）

李文芳（1982- ），女，山西繁峙人，碩士，講師。研究方向：自動(dòng)控制與應(yīng)用、高職教育。