李炳圻，梅中輝

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

作為智能交通系統(tǒng)(intelligent transport system，ITS)的重要組成部分，車載自組織網(wǎng)絡(luò)(vehicular ad-hoc network，VANET)，一種由車載單元(on-board unit，OBU)組成的移動(dòng)自組織網(wǎng)絡(luò)(mobile ad-hoc network，MANET)正在快速發(fā)展。在VANET中，OBU通過單跳或多跳無(wú)線通信實(shí)現(xiàn)車輛間通信(vehicle to vehicle，V2V)，路邊單元(roadside unit，RSU)通過向OBU收發(fā)數(shù)據(jù)實(shí)現(xiàn)車路間通信(vehicle to infrastructure，V2I)，同時(shí)RSU通過光纖相互連接并接入骨干網(wǎng)絡(luò)(Internet，4G)實(shí)現(xiàn)整個(gè)交通系統(tǒng)與外界網(wǎng)絡(luò)的信息交互[1]。

目前，普遍通過MANET路由協(xié)議實(shí)現(xiàn)車載單元間的物理連接，但帶來的可靠性和擴(kuò)展性問題仍未找到有效的解決辦法。為了提高路由的可靠性和擴(kuò)展性，在MANET成簇算法的基礎(chǔ)上，一系列針對(duì)VANET高速移動(dòng)場(chǎng)景的成簇算法被提出[2]。研究表明一個(gè)穩(wěn)定且可靠的成簇算法可以有效節(jié)省路由開銷，部分算法還能作為交通事故或擁塞檢測(cè)的基礎(chǔ)，為智能交通系統(tǒng)提供數(shù)據(jù)支持[3-4]。

文中探討并提出了針對(duì)VANET的成簇算法SQ-WCA，該算法在幾種經(jīng)典成簇算法的基礎(chǔ)上，考慮了城市環(huán)境中成簇的穩(wěn)定性(stability)條件和節(jié)點(diǎn)間通信的服務(wù)質(zhì)量(quality)，并對(duì)其進(jìn)行了仿真。

1 經(jīng)典的成簇算法

車載自組織網(wǎng)絡(luò)(VANET)的基本框架從移動(dòng)自組織網(wǎng)絡(luò)(MANET)發(fā)展而來，現(xiàn)有的框架結(jié)構(gòu)主要包括兩種：平面(flat)結(jié)構(gòu)和分級(jí)(hierarchical)結(jié)構(gòu)。平面結(jié)構(gòu)在復(fù)雜網(wǎng)絡(luò)中很難實(shí)現(xiàn)，因?yàn)槁酚砷_銷限制了其網(wǎng)絡(luò)規(guī)模的擴(kuò)充。分級(jí)結(jié)構(gòu)則可以有效降低路由開銷，提高網(wǎng)絡(luò)的可擴(kuò)充性，從而降低網(wǎng)絡(luò)管理和同步的難度[5]。如圖1所示，在分級(jí)結(jié)構(gòu)中，成簇算法需要實(shí)現(xiàn)將所有節(jié)點(diǎn)劃分成簇的目標(biāo)。每個(gè)生成的簇包含唯一的簇頭節(jié)點(diǎn)(cluster header，CH)和多個(gè)成員節(jié)點(diǎn)(cluster member，CM)，部分處于邊緣位置的成員節(jié)點(diǎn)同時(shí)承擔(dān)著網(wǎng)關(guān)節(jié)點(diǎn)的工作[6]。

圖1 分級(jí)結(jié)構(gòu)

1.1 最小ID算法

最小ID(lowest-id，LID)算法[7]是由Grela和Tsai提出的成簇算法。該算法參照節(jié)點(diǎn)的空間位置或者物理地址(medium access control，MAC)，為所有節(jié)點(diǎn)分配唯一的ID標(biāo)識(shí)。區(qū)域中的節(jié)點(diǎn)周期性地接收來自鄰居節(jié)點(diǎn)發(fā)送的HELLO數(shù)據(jù)包，并記錄在自己的鄰居節(jié)點(diǎn)列表中，默認(rèn)最小ID標(biāo)識(shí)對(duì)應(yīng)的節(jié)點(diǎn)為CH節(jié)點(diǎn)，該節(jié)點(diǎn)的單跳鄰居節(jié)點(diǎn)為該簇的CM節(jié)點(diǎn)。最小ID算法計(jì)算簡(jiǎn)單、實(shí)現(xiàn)方便、更新周期長(zhǎng)、維護(hù)開銷小，網(wǎng)絡(luò)吞吐量高于最高節(jié)點(diǎn)度(highest-degree，HD)算法[8]。但該算法忽略了節(jié)點(diǎn)的移動(dòng)性和負(fù)載平衡問題，不適用于高速移動(dòng)的場(chǎng)景。

1.2 最小相對(duì)移動(dòng)算法

最小相對(duì)移動(dòng)(MOBIC)算法[9]是由Basu和Khan提出的一種計(jì)算節(jié)點(diǎn)移動(dòng)差異性的成簇算法。該算法依據(jù)式1對(duì)X節(jié)點(diǎn)接收到的鄰居節(jié)點(diǎn)Y兩次傳輸信號(hào)的強(qiáng)度作差，估計(jì)兩節(jié)點(diǎn)之間的移動(dòng)差異性，再依據(jù)式2計(jì)算節(jié)點(diǎn)Y與所有鄰居節(jié)點(diǎn)的移動(dòng)差異性的方差。通過比較方差的大小選擇相對(duì)周圍鄰居節(jié)點(diǎn)有著較低移動(dòng)差異性的節(jié)點(diǎn)作為CH節(jié)點(diǎn)，降低CH節(jié)點(diǎn)發(fā)生變化的次數(shù)。MOBIC算法相對(duì)簡(jiǎn)單，對(duì)成簇的穩(wěn)定性條件作了改進(jìn)，但不適用于節(jié)點(diǎn)速度和方向快速變化的場(chǎng)景。

(1)

(2)

1.3 加權(quán)成簇算法

加權(quán)成簇算法(weighted clustering algorithm，WCA)[10]是由Chatterjee和Das提出的一種按需加權(quán)的成簇算法。該算法同時(shí)考慮了多個(gè)影響成簇的因素，其中包括移動(dòng)性、節(jié)點(diǎn)密度和節(jié)點(diǎn)能量。算法會(huì)根據(jù)不同需求，依據(jù)式3調(diào)節(jié)加權(quán)系數(shù)w，對(duì)多個(gè)優(yōu)化目標(biāo)進(jìn)行均衡。WCA算法復(fù)雜度較高，且成簇和維護(hù)的開銷較大，同樣不適用于高速移動(dòng)場(chǎng)景。

Wv=w1Δv+w2Mv+w3Dv+w4Pv

(3)

依據(jù)式4計(jì)算節(jié)點(diǎn)v的節(jié)點(diǎn)度dv，其中dist(v,v')表示節(jié)點(diǎn)v和v'之間的歐氏距離，txrange表示節(jié)點(diǎn)的最大傳輸距離，Δv表示節(jié)點(diǎn)度dv與節(jié)點(diǎn)度的期望值δ差的絕對(duì)值。再依據(jù)式5計(jì)算節(jié)點(diǎn)v與所有鄰居節(jié)點(diǎn)的距離之和Dv。最后依據(jù)式6估算時(shí)間T內(nèi)節(jié)點(diǎn)v的平均速度Mv，其中(xt,yt)和(xt-1,yt-1)分別表示節(jié)點(diǎn)v在t和t-1時(shí)刻的位置。此外，式3中的Pv表示節(jié)點(diǎn)v作為CH節(jié)點(diǎn)持續(xù)的時(shí)間。

(4)

(5)

(6)

2 SQ-WCA成簇算法

2.1 假設(shè)條件

(1)假設(shè)所有的車輛節(jié)點(diǎn)可以通過全球定位系統(tǒng)(global positioning system，GPS)獲取自己實(shí)時(shí)的位置、速度和方向。

(2)假設(shè)所有的車輛節(jié)點(diǎn)均配備有全向天線，可以實(shí)現(xiàn)節(jié)點(diǎn)間的雙向鏈路通信，最大傳輸距離為固定值R。

(3)假設(shè)所有的車輛節(jié)點(diǎn)的發(fā)射功率為固定值Pt且節(jié)點(diǎn)的接收功率可以獲取和記錄。

2.2 準(zhǔn)備階段

首先對(duì)VANET網(wǎng)絡(luò)進(jìn)行初始化，將所有的節(jié)點(diǎn)設(shè)置為普通節(jié)點(diǎn)，這些節(jié)點(diǎn)向通信范圍內(nèi)的其他節(jié)點(diǎn)周期性地廣播HELLO數(shù)據(jù)包。HELLO數(shù)據(jù)包記錄了該節(jié)點(diǎn)自身的ID、位置、速度、方向以及權(quán)重值W等信息。所有節(jié)點(diǎn)在接收到鄰居節(jié)點(diǎn)發(fā)送的HELLO數(shù)據(jù)包的同時(shí)，將發(fā)送數(shù)據(jù)包的節(jié)點(diǎn)ID記錄到自己的鄰居列表(neighbor list，NL)之中[11]。

(7)

(8)

首先，節(jié)點(diǎn)i利用式8計(jì)算它與鄰居列表中的節(jié)點(diǎn)j的運(yùn)動(dòng)方向夾角θi,j，如果滿足θi,j≥π/4這個(gè)條件，則文中認(rèn)為這兩個(gè)節(jié)點(diǎn)的運(yùn)動(dòng)方向不同。如果同時(shí)節(jié)點(diǎn)j的速度絕對(duì)值大于60 km/h，則節(jié)點(diǎn)i自動(dòng)將節(jié)點(diǎn)j從鄰居列表中剔除。通過這個(gè)步驟可以剔除鄰居列表中高速移動(dòng)的不同向節(jié)點(diǎn)，處于低速或者靜止?fàn)顟B(tài)的車輛節(jié)點(diǎn)對(duì)運(yùn)動(dòng)方向不敏感，則保留在鄰居列表中。鄰居列表中的節(jié)點(diǎn)個(gè)數(shù)用ni表示。

在IEEE802.11p協(xié)議中，不斷廣播重復(fù)的消息會(huì)造成嚴(yán)重的數(shù)據(jù)碰撞并導(dǎo)致過高的信道接入延時(shí)[12]。針對(duì)這個(gè)問題，一旦出現(xiàn)車輛節(jié)點(diǎn)密度過大、簇內(nèi)節(jié)點(diǎn)過多的情況時(shí)，可以修改上述的速度條件的閾值，減少對(duì)應(yīng)的鄰居列表中的節(jié)點(diǎn)個(gè)數(shù)，從而降低信道接入時(shí)延。

2.3 簇的生成

選擇合適的簇頭節(jié)點(diǎn)可以提高成簇算法的穩(wěn)定性。文中根據(jù)式9得到的權(quán)重值Wi表示節(jié)點(diǎn)i作為簇頭節(jié)點(diǎn)的能力。

Wi=w1Di+w2Vi+w3Ci

(9)

其中，Di表示節(jié)點(diǎn)i的距離因子；Vi表示節(jié)點(diǎn)i的速度因子；Ci表示節(jié)點(diǎn)i的信道因子；w1,w2,w3是加權(quán)系數(shù)，且滿足w1+w2+w3=1。

2.3.1 距離因子

根據(jù)式10計(jì)算節(jié)點(diǎn)i與鄰居節(jié)點(diǎn)j的距離權(quán)重值d_weight(i,j)。

(10)

(11)

2.3.2 速度因子

根據(jù)式12計(jì)算節(jié)點(diǎn)i與鄰居節(jié)點(diǎn)j的速度權(quán)重值v_weight(i,j)，用來度量?jī)晒?jié)點(diǎn)的移動(dòng)相似度。首先計(jì)算兩個(gè)節(jié)點(diǎn)速度大小的差值并取絕對(duì)值，然后利用最大行駛速度vmax對(duì)其進(jìn)行歸一化。對(duì)于運(yùn)動(dòng)方向相同的節(jié)點(diǎn)，速度權(quán)重值越小，節(jié)點(diǎn)的移動(dòng)相似度越高，成簇也就越穩(wěn)定。對(duì)于運(yùn)動(dòng)方向不同的節(jié)點(diǎn)，因?yàn)樘幱诘退倩蛘哽o止?fàn)顟B(tài)，不會(huì)對(duì)成簇的結(jié)構(gòu)穩(wěn)定性造成太大影響。與式11類似，根據(jù)式13得到了速度因子Vi。

(12)

(13)

2.3.3 信道因子

(14)

(15)

周期更新鄰居列表，節(jié)點(diǎn)i對(duì)鄰居列表中的節(jié)點(diǎn)進(jìn)行遍歷分析：

(1)節(jié)點(diǎn)i的鄰居列表中不存在CH節(jié)點(diǎn)，則節(jié)點(diǎn)i自動(dòng)比較自身權(quán)重值Wi和鄰居列表中所有節(jié)點(diǎn)的權(quán)重值W，若Wi小于任意節(jié)點(diǎn)的W值，節(jié)點(diǎn)i就默認(rèn)為CH節(jié)點(diǎn)。

(2)節(jié)點(diǎn)i的鄰居列表中只有一個(gè)CH節(jié)點(diǎn)，則節(jié)點(diǎn)i自動(dòng)發(fā)送一個(gè)包含自身ID的Cluster_JOIN包給該CH節(jié)點(diǎn)，并成為它的CM節(jié)點(diǎn)。

(3)節(jié)點(diǎn)i的鄰居列表中有不止一個(gè)簇頭，則節(jié)點(diǎn)i自動(dòng)選擇擁有最小W值的節(jié)點(diǎn)作為CH節(jié)點(diǎn)，發(fā)送Cluster_JOIN包給該節(jié)點(diǎn)并且加入該簇。

(4)節(jié)點(diǎn)i成為CH節(jié)點(diǎn)的同時(shí)會(huì)廣播一個(gè)包含自身ID和Wi值的Cluster_INVITE包給自己的鄰居節(jié)點(diǎn)。

(5)鄰居列表中的其他節(jié)點(diǎn)收到Cluster_INVITE包，若節(jié)點(diǎn)i發(fā)送的Cluster_INVITE包中的Wi值比該節(jié)點(diǎn)收到的其他Cluster_INVITE包小，則回復(fù)給節(jié)點(diǎn)i—個(gè)Cluster_JOIN包。

2.4 簇的維護(hù)

(1)簇生成后，CH節(jié)點(diǎn)擁有所在簇的簇信息、CM節(jié)點(diǎn)信息以及相鄰簇的CH節(jié)點(diǎn)信息，CM節(jié)點(diǎn)擁有所在簇的相關(guān)信息及CH節(jié)點(diǎn)信息。CH節(jié)點(diǎn)開始周期性廣播Cluster_LEAD包，Cluster_LEAD包中不僅包含了CH節(jié)點(diǎn)的信息，還包含鄰居列表中擁有最小權(quán)重W的次優(yōu)節(jié)點(diǎn)的信息。

(2)當(dāng)CH節(jié)點(diǎn)停止工作并需更換CH節(jié)點(diǎn)時(shí)，次優(yōu)節(jié)點(diǎn)成為臨時(shí)簇頭，并且同一個(gè)簇的其他CM節(jié)點(diǎn)發(fā)送Cluster_LEAVE包，接著各節(jié)點(diǎn)檢查在自己通信范圍內(nèi)的其他節(jié)點(diǎn)，更新鄰居列表，重復(fù)簇的生成步驟。如果不在任何節(jié)點(diǎn)通信范圍內(nèi)，則該節(jié)點(diǎn)自動(dòng)成為CH節(jié)點(diǎn)直到收到其他節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包。

3 仿真結(jié)果與分析

通過NS2仿真平臺(tái)[13]對(duì)LID、MOBIC、SQ-WCA算法進(jìn)行仿真，主要分析城市環(huán)境中車輛節(jié)點(diǎn)的速度、節(jié)點(diǎn)的個(gè)數(shù)對(duì)算法性能的影響，主要是從成簇的穩(wěn)定性和端到端時(shí)延這兩個(gè)方面分析算法的性能，具體的參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)

為了模擬更加真實(shí)的城市環(huán)境，驗(yàn)證算法在城市環(huán)境中的性能，文中采用的是SUMO仿真平臺(tái)生成的曼哈頓模型。SUMO是德國(guó)宇航中心開發(fā)的交通仿真軟件，可以用來描述和構(gòu)建交通路網(wǎng)、管理信號(hào)燈、分配車輛節(jié)點(diǎn)的行駛路徑和速度。

圖2 簇頭持續(xù)時(shí)間隨節(jié)點(diǎn)速度變化曲線

圖2給出了不同算法的簇頭節(jié)點(diǎn)持續(xù)時(shí)間隨節(jié)點(diǎn)速度變化的情況?？梢钥闯觯魉惴ù仡^持續(xù)時(shí)間均隨節(jié)點(diǎn)速度的提高而變短，因?yàn)樗俣仍酱螅W(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)變化越頻繁。簇頭持續(xù)時(shí)間減少會(huì)導(dǎo)致鏈路頻繁斷開，ad-hoc網(wǎng)絡(luò)的連通性變差，算法的穩(wěn)定性降低。在相同的節(jié)點(diǎn)速度下，SQ-WCA算法的簇頭持續(xù)時(shí)間最長(zhǎng)，因?yàn)榕cLID和MOBIC相比，SQ-WCA在選擇簇頭時(shí)不僅考慮了節(jié)點(diǎn)的位置和速度，還考慮了節(jié)點(diǎn)方向和信道質(zhì)量，使得生成的簇更加穩(wěn)定。

圖3表明各算法平均簇頭變化次數(shù)隨節(jié)點(diǎn)速度變化的關(guān)系。如圖所示，三種算法對(duì)應(yīng)的平均簇頭變化次數(shù)均隨節(jié)點(diǎn)速度的提高而增加，這是因?yàn)槠骄仡^變化次數(shù)和前面的簇頭持續(xù)時(shí)間成反比。SQ-WCA算法對(duì)應(yīng)的平均簇頭變化次數(shù)最小，再次驗(yàn)證了該算法在穩(wěn)定性上的優(yōu)越性。

圖4給出了三種算法端到端時(shí)延隨節(jié)點(diǎn)數(shù)目變化的情況?？梢钥闯?，交通流量的密度會(huì)影響車輛節(jié)點(diǎn)的端到端時(shí)延。城市環(huán)境會(huì)導(dǎo)致部分節(jié)點(diǎn)信道訪問長(zhǎng)時(shí)間的延遲。具有更好信道質(zhì)量的簇頭節(jié)點(diǎn)可以增加數(shù)據(jù)包傳輸?shù)挠行r(shí)間，降低端到端時(shí)延。當(dāng)節(jié)點(diǎn)的最大速度設(shè)置為 60 km/h時(shí)，SQ-WCA算法與LID算法和MOBIC算法相比，端到端的時(shí)延分別降低了22.4%和30.7%左右。降低端到端時(shí)延實(shí)現(xiàn)了對(duì)通信服務(wù)質(zhì)量的提升，為事故救援和自然災(zāi)害信息的及時(shí)傳達(dá)提供保障。

圖3 平均簇頭變化次數(shù)隨節(jié)點(diǎn)速度變化曲線

圖4 端到端時(shí)延隨節(jié)點(diǎn)數(shù)目變化曲線

4 結(jié)束語(yǔ)

VANET網(wǎng)絡(luò)在城市交通中的應(yīng)用能夠提高道路交通的安全性及高效性，同時(shí)能夠緩解蜂窩移動(dòng)網(wǎng)絡(luò)的壓力，具有很高的商業(yè)應(yīng)用前景。文中提出的算法SQ-WCA充分考慮了節(jié)點(diǎn)的位置、速度和方向?qū)Τ纱胤€(wěn)定性的影響，同時(shí)考慮了節(jié)點(diǎn)間通信的服務(wù)質(zhì)量。通過仿真對(duì)比驗(yàn)證了該算法在穩(wěn)定性和可靠性上的優(yōu)越性，并且具有相對(duì)較低的端到端傳輸時(shí)延。