一種基于車載網(wǎng)的樹(shù)形多播路由協(xié)議

龐國(guó)彬,譚 龍,李瀚博,秦琦冰

(黑龍江大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，哈爾濱 150080)

?

一種基于車載網(wǎng)的樹(shù)形多播路由協(xié)議

龐國(guó)彬,譚 龍*,李瀚博,秦琦冰

(黑龍江大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，哈爾濱 150080)

車載網(wǎng)中車輛的高速移動(dòng)導(dǎo)致鏈路的生命期短，為了提高數(shù)據(jù)包的投遞率，設(shè)計(jì)了一種基于分簇和多播樹(shù)的地理多播路由協(xié)議。該協(xié)議將整個(gè)車載網(wǎng)中的車輛進(jìn)行分簇，以多個(gè)車輛組成的簇為數(shù)據(jù)包中轉(zhuǎn)站，簇內(nèi)車輛協(xié)同轉(zhuǎn)發(fā)一個(gè)數(shù)據(jù)包，數(shù)據(jù)包再由一個(gè)簇轉(zhuǎn)發(fā)到另一個(gè)簇，最后到達(dá)目的區(qū)域。由于簇的穩(wěn)定性，這個(gè)數(shù)據(jù)包投遞成功的概率將顯著增加。通過(guò)仿真實(shí)驗(yàn)與現(xiàn)有協(xié)議進(jìn)行比較，驗(yàn)證了該協(xié)議具有更高的數(shù)據(jù)包投遞率。

車載網(wǎng)；地理多播；分簇；多播樹(shù)

車載網(wǎng)(vehicular ad-hoc networks，VANETs)被認(rèn)為是很有發(fā)展前景的一項(xiàng)新技術(shù)，特別是在交通安全、車輛調(diào)度和商業(yè)應(yīng)用上[1]。作為智能交通系統(tǒng)(Intelligent Transportation Systems，ITS)的重要組成部分，車載網(wǎng)不僅用來(lái)向司機(jī)提供潛在的交通擁堵信息以增加出行的便利性，還用來(lái)向后邊的車輛傳播緊急的信息以避免連環(huán)相撞事故的發(fā)生。為了實(shí)現(xiàn)這個(gè)前景，美國(guó)聯(lián)邦通信委員會(huì)(Federal Communications Commission，F(xiàn)CC)為專用短程通信技術(shù)(dedicated short range communications，DSRC)分配了75 MHz的無(wú)線頻段。并且，IEEE正在制定車輛間通信的標(biāo)準(zhǔn)[2]。車載網(wǎng)中的通信分為汽車到汽車 (vehicle-to-vehicle，V2V)，或者稱為汽車之間(inter-vehicle communication，IVC)，以及汽車與基礎(chǔ)設(shè)施之間(vehicle-to-infrastructure，V2I)[3]。由于越來(lái)越多的車輛具備了車與車之間的通信能力，大規(guī)模的車載網(wǎng)將在不久的將來(lái)成為可能。

雖然以上這些應(yīng)用可以通過(guò)現(xiàn)有的許多無(wú)線設(shè)施(例如3 G或者4 G)來(lái)實(shí)現(xiàn)，但它們的花費(fèi)較高，并且當(dāng)有自然災(zāi)害發(fā)生時(shí)，一旦基礎(chǔ)設(shè)施被摧毀，它們將不可用。因此，車載網(wǎng)的存在是有價(jià)值的，對(duì)車載網(wǎng)的研究是必要的[4]。

當(dāng)有交通事故發(fā)生時(shí)，事故地點(diǎn)所在的路段可能發(fā)生擁堵，交通調(diào)度中心有必要向事故地點(diǎn)周圍的車輛發(fā)送事故信息以及可能即將到來(lái)的擁堵警告。這就牽涉到一個(gè)節(jié)點(diǎn)向特定區(qū)域內(nèi)的多個(gè)目的節(jié)點(diǎn)發(fā)送信息，也就是所謂的地理多播[5]。

車載網(wǎng)的很多路由協(xié)議是從移動(dòng)自組網(wǎng)絡(luò)(mobile ad hoc networks，MANETs)的路由協(xié)議演變過(guò)來(lái)的。文獻(xiàn)[6]提出的AODV協(xié)議是傳統(tǒng)的基于拓?fù)涞腗ANET路由協(xié)議，考慮到有限的帶寬和拓?fù)涞念l繁變化，該協(xié)議采用反應(yīng)式的路由策略，當(dāng)有數(shù)據(jù)需要發(fā)送時(shí)才啟動(dòng)路由發(fā)現(xiàn)過(guò)程。文獻(xiàn)[7]提出的AODV-PNT協(xié)議是在AODV協(xié)議的基礎(chǔ)上做了改進(jìn)而應(yīng)用于車載網(wǎng)，主要的改進(jìn)有兩點(diǎn)：①路由判據(jù)的改進(jìn)并計(jì)算路由的總權(quán)值;②預(yù)測(cè)節(jié)點(diǎn)將來(lái)的路由總權(quán)值并計(jì)算出一個(gè)穩(wěn)定閾值以選擇適合的中繼節(jié)點(diǎn)。由于車輛普遍都配備有GPS，這意味著車輛可以獲取自己的位置信息，將位置信息融入路由策略，將極大地方便數(shù)據(jù)的轉(zhuǎn)發(fā)。文獻(xiàn)[8]提出的GPSR協(xié)議就是通過(guò)目的節(jié)點(diǎn)和路由節(jié)點(diǎn)的位置比較來(lái)做出轉(zhuǎn)發(fā)決定，該協(xié)議只使用當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的位置信息就可以實(shí)現(xiàn)數(shù)據(jù)的貪心轉(zhuǎn)發(fā)，數(shù)據(jù)轉(zhuǎn)發(fā)前不需要建立從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的完整的路徑，所需的信息少，因此可以稱為無(wú)狀態(tài)的。文獻(xiàn)[9]對(duì)GPSR進(jìn)行了修改，通過(guò)挖掘相對(duì)運(yùn)動(dòng)信息來(lái)改進(jìn)轉(zhuǎn)發(fā)決策。文獻(xiàn)[10]提出了一種分簇算法，它考慮到了車輛的移動(dòng)速度快但移動(dòng)受道路限制的情況，極大地改善了簇的穩(wěn)定性。文獻(xiàn)[11]提出了一種地理多播路由策略，通過(guò)建立多播樹(shù)而使數(shù)據(jù)可靠地傳輸。

基于拓?fù)涞穆酚呻m然增加了反應(yīng)式，但控制開(kāi)銷仍然大?；谖恢玫穆酚?，在采用貪心策略的情況下容易出現(xiàn)局部最優(yōu)而不是全局最優(yōu)的情況。通過(guò)建立多播樹(shù)來(lái)實(shí)現(xiàn)地理多播也存在控制開(kāi)銷大的問(wèn)題。

本文在前人的基礎(chǔ)上提出了一種基于分簇和多播樹(shù)的地理多播路由協(xié)議。該協(xié)議在對(duì)網(wǎng)絡(luò)進(jìn)行分簇的情況下首先建立鄰居簇，再以簇為單位構(gòu)建整棵多播樹(shù)，使得數(shù)據(jù)包可沿著多播樹(shù)轉(zhuǎn)發(fā)到目的區(qū)域，并且控制開(kāi)銷相對(duì)較小。

1 樹(shù)形多播路由協(xié)議

在車載網(wǎng)中，車輛的高速移動(dòng)，導(dǎo)致鏈路的生命期短。如果以單個(gè)車輛做為數(shù)據(jù)的中轉(zhuǎn)站，數(shù)據(jù)包是否能夠投遞成功將令人擔(dān)憂。換一種思路，如果以多個(gè)車輛組成的簇為中轉(zhuǎn)站，簇內(nèi)車輛協(xié)同轉(zhuǎn)發(fā)一個(gè)數(shù)據(jù)包，數(shù)據(jù)包再由一個(gè)簇轉(zhuǎn)發(fā)到另一個(gè)簇，最后到達(dá)目的車輛。由于簇的穩(wěn)定性，這個(gè)數(shù)據(jù)包投遞成功的概率將顯著增加?；谝陨系南敕?，筆者設(shè)計(jì)了下面的路由協(xié)議。

1.1 網(wǎng)絡(luò)模型

本文涉及的車載網(wǎng)由多個(gè)移動(dòng)車輛作為節(jié)點(diǎn)構(gòu)成，每一輛車配備有GPS定位及電子地圖，網(wǎng)絡(luò)模型可以用圖G(V，E)表示，圖中的節(jié)點(diǎn)是車輛，如果兩個(gè)節(jié)點(diǎn)u和v之間的距離小于或等于直接通信距離，那么兩個(gè)節(jié)點(diǎn)之間就有一條邊(u，v)。

節(jié)點(diǎn)的鄰居節(jié)點(diǎn)指的是該節(jié)點(diǎn)一跳范圍內(nèi)的所有節(jié)點(diǎn)。鄰居節(jié)點(diǎn)之間定期交換信息，建立鄰居信息表，交換的信息包括節(jié)點(diǎn)標(biāo)識(shí)VID，節(jié)點(diǎn)的位置，節(jié)點(diǎn)所在的簇的標(biāo)識(shí)CID和節(jié)點(diǎn)的權(quán)值W(也就是節(jié)點(diǎn)成為簇頭的適合性)。

一個(gè)簇指的是以簇頭為中心，簇頭一跳范圍內(nèi)的所有節(jié)點(diǎn)，簇頭是簇內(nèi)W值最大的節(jié)點(diǎn)。簇的組建過(guò)程如下：一個(gè)節(jié)點(diǎn)新加入網(wǎng)絡(luò)時(shí)，通過(guò)與鄰居節(jié)點(diǎn)交換信息，這個(gè)節(jié)點(diǎn)會(huì)得到所有鄰居節(jié)點(diǎn)的W值，同時(shí)自己也會(huì)計(jì)算出一個(gè)W值。如果自己的W值比其他所有W值都大，節(jié)點(diǎn)就會(huì)選擇自己為簇頭。如果存在某個(gè)W值比自己和其他的都大，節(jié)點(diǎn)就會(huì)加入這個(gè)W 值對(duì)應(yīng)節(jié)點(diǎn)為簇頭的簇。同時(shí)，在簇的移動(dòng)過(guò)程中，如果兩個(gè)簇頭節(jié)點(diǎn)之間的最小距離ICmin小于直接通信距離，其中W值較小的簇頭就會(huì)放棄成為簇頭節(jié)點(diǎn)，也就是說(shuō)兩個(gè)簇會(huì)進(jìn)行合并。如果簇頭離開(kāi)了自己所在的簇，剩下的節(jié)點(diǎn)會(huì)重新確定一個(gè)簇頭。新選出的簇頭原先就是簇內(nèi)成員的話，CID不需要改變。但新選出的簇頭如若不是原簇內(nèi)成員，CID就需要更改。簇的邊緣節(jié)點(diǎn)很不穩(wěn)定，一個(gè)時(shí)刻可能有節(jié)點(diǎn)離開(kāi)這個(gè)簇，也有可能有新的節(jié)點(diǎn)加入這個(gè)簇，但整個(gè)簇作為數(shù)據(jù)的中轉(zhuǎn)站具有較好的穩(wěn)定性。本文的網(wǎng)絡(luò)模型見(jiàn)圖1。

圖1 網(wǎng)絡(luò)模型圖Fig.1 Network model graph

1.2 鄰居簇的建立

鄰居簇的概念與鄰居節(jié)點(diǎn)的概念類似，一個(gè)簇的鄰居簇指的是能與這個(gè)簇直接通信的所有簇。如圖1所示，假如A和B、C、S都可以直接通信，則B、C、S就是A的鄰居簇。

為了建立鄰居簇表，簇頭廣播跳數(shù)限制為2的鄰居簇請(qǐng)求NCREQ(neighbor clusters request)信息。簇內(nèi)節(jié)點(diǎn)在收到這個(gè)信息后，繼續(xù)進(jìn)行廣播。簇內(nèi)的邊緣節(jié)點(diǎn)在收到簇頭的廣播后，能將這個(gè)信息廣播到離簇最遠(yuǎn)的地方。廣播得越遠(yuǎn)就越有可能獲得更多的鄰居簇，這對(duì)路由的建立和數(shù)據(jù)的轉(zhuǎn)發(fā)都是有好處的。如果某個(gè)鄰居簇的簇頭收到了這個(gè)NCREQ，它會(huì)立即發(fā)送一個(gè)鄰居簇應(yīng)答NCREP(neighbor clusters reply)，并將發(fā)送NCREQ簇的CID和簇頭位置加入自己的鄰居簇表。同時(shí)，這個(gè)簇頭會(huì)在簇內(nèi)廣播新獲得的鄰居簇，目的是為了使整個(gè)簇的鄰居簇表同步。如果不是簇頭收到NCREQ，而是非簇頭節(jié)點(diǎn)收到NCREQ，收到NCREQ的節(jié)點(diǎn)會(huì)立即發(fā)送一個(gè)NCREP，并單播一個(gè)信息給簇頭節(jié)點(diǎn)，告訴簇頭自己收到了NCREQ。簇頭在收到這個(gè)消息以后所做的處理與自己收到NCREQ的過(guò)程類似，只是不再發(fā)送NCREP，因?yàn)橐呀?jīng)有簇內(nèi)節(jié)點(diǎn)進(jìn)行了應(yīng)答。

節(jié)點(diǎn)在收到NCREP以后，會(huì)將這個(gè)NCREP發(fā)送給簇頭。簇頭發(fā)送的NCREQ得到了回應(yīng)，簇頭就把發(fā)送NCREP簇的CID和簇頭位置加入自己的鄰居簇表。同時(shí)，這個(gè)簇頭也在簇內(nèi)廣播新獲得的鄰居簇，使整個(gè)簇的鄰居簇表同步。

經(jīng)過(guò)上述過(guò)程，一個(gè)簇與它的鄰居簇建立了聯(lián)系，它的鄰居簇表增加了一項(xiàng)。當(dāng)然，在這個(gè)過(guò)程中如果這個(gè)簇有多個(gè)鄰居簇，那它將與所有的鄰居簇取得聯(lián)系，使自己的鄰居簇表?xiàng)l目增加若干。而且，這個(gè)過(guò)程在簇與簇之間是周期進(jìn)行的，以保證各自的鄰居表都是最新的。

1.3 多播樹(shù)的建立

地理多播的方式有兩種：①基于洪泛的方式;②基于多播樹(shù)的方式。洪泛的方式通信的數(shù)據(jù)量大，多播樹(shù)的方式由于節(jié)點(diǎn)高速的移動(dòng)性，使樹(shù)的構(gòu)建和維護(hù)較困難。由于本文對(duì)節(jié)點(diǎn)進(jìn)行了分簇，并建立了鄰居簇表，這使多播樹(shù)的構(gòu)建和維護(hù)變得簡(jiǎn)單。因此，采用基于多播樹(shù)的方式進(jìn)行地理多播。

當(dāng)源節(jié)點(diǎn)需要向一個(gè)確定地理區(qū)域內(nèi)的所有節(jié)點(diǎn)多播一個(gè)消息時(shí)，這個(gè)區(qū)域?yàn)槎嗖^(qū)域MR(multicast region)，這個(gè)區(qū)域內(nèi)的所有節(jié)點(diǎn)構(gòu)成一個(gè)多播組。多播區(qū)域可被指定為圓形或多邊形，這里指定為圓形。源節(jié)點(diǎn)向多播區(qū)域發(fā)送消息的時(shí)候，還會(huì)指定一個(gè)轉(zhuǎn)發(fā)區(qū)域FZ(forwarding zone)。轉(zhuǎn)發(fā)區(qū)域包含了源節(jié)點(diǎn)和多播區(qū)域，以及參與數(shù)據(jù)轉(zhuǎn)發(fā)的中間節(jié)點(diǎn)。只有位于轉(zhuǎn)發(fā)區(qū)域內(nèi)的節(jié)點(diǎn)收到源節(jié)點(diǎn)發(fā)來(lái)的消息才會(huì)轉(zhuǎn)發(fā)，而位于轉(zhuǎn)發(fā)區(qū)域外的節(jié)點(diǎn)收到源節(jié)點(diǎn)發(fā)來(lái)的消息將會(huì)把這個(gè)消息丟棄。轉(zhuǎn)發(fā)區(qū)域也可指定為多種形狀，這里指定為長(zhǎng)方形，即指定長(zhǎng)方形的4個(gè)頂點(diǎn)坐標(biāo)。多播區(qū)域和轉(zhuǎn)發(fā)區(qū)域見(jiàn)圖2。

圖2 樹(shù)形多播路由示意圖Fig.2 Sketch map of the tree multicast routing protocol graph

當(dāng)源節(jié)點(diǎn)需要向一個(gè)多播區(qū)域發(fā)送數(shù)據(jù)時(shí)，路由發(fā)現(xiàn)過(guò)程便會(huì)啟動(dòng)。源節(jié)點(diǎn)向自己所在簇的簇頭發(fā)送一個(gè)多播區(qū)域路由請(qǐng)求MRREQ(multicast region request)信息，這個(gè)信息包含了源節(jié)點(diǎn)的節(jié)點(diǎn)標(biāo)識(shí)VID、當(dāng)前節(jié)點(diǎn)VID(對(duì)于源節(jié)點(diǎn)而言，當(dāng)前節(jié)點(diǎn)VID和源節(jié)點(diǎn)VID是一樣的。)、下一跳節(jié)點(diǎn)VID、源節(jié)點(diǎn)所在簇的標(biāo)識(shí)CID、當(dāng)前節(jié)點(diǎn)所在簇的CID、下一簇的CID(此時(shí)為NULL)、多播樹(shù)路由序列號(hào)SS、多播區(qū)域的圓心和半徑、轉(zhuǎn)發(fā)區(qū)域的4個(gè)頂點(diǎn)坐標(biāo)。簇頭節(jié)點(diǎn)在收到這個(gè)MRREQ以后，修改當(dāng)前節(jié)點(diǎn)VID，準(zhǔn)備將它發(fā)送給自己所有的鄰居簇。簇頭節(jié)點(diǎn)從自己的簇內(nèi)節(jié)點(diǎn)中選擇幾個(gè)節(jié)點(diǎn)，有多少個(gè)鄰居簇就選擇幾個(gè)節(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)分別是到達(dá)對(duì)應(yīng)鄰居簇最近的節(jié)點(diǎn)。簇頭將MRREQ進(jìn)行復(fù)制，并把對(duì)應(yīng)鄰居簇的CID填入為NULL的下一簇的CID，再發(fā)送給剛選出的節(jié)點(diǎn)。節(jié)點(diǎn)一旦收到MRREQ，就會(huì)把它轉(zhuǎn)發(fā)到對(duì)應(yīng)的鄰居簇。鄰居簇內(nèi)的節(jié)點(diǎn)在收到MRREQ后，先判斷自己是否處于轉(zhuǎn)發(fā)區(qū)域內(nèi)，如果不是則丟棄該MRREQ，如果是則將它轉(zhuǎn)發(fā)給自己所在簇的簇頭節(jié)點(diǎn)。接下來(lái)，簇頭節(jié)點(diǎn)在收到這個(gè)MRREQ后會(huì)重復(fù)上一個(gè)簇的簇頭所做的工作，從而使MRREQ以簇間洪泛的方式向前轉(zhuǎn)發(fā)，直到到達(dá)多播區(qū)域?yàn)橹埂６嗖^(qū)域內(nèi)的某個(gè)節(jié)點(diǎn)在收到一個(gè)MRREQ后會(huì)立即發(fā)送一個(gè)多播區(qū)域路由應(yīng)答MRREP(multicast region reply)信息，MRREP會(huì)沿著MRREQ來(lái)時(shí)經(jīng)過(guò)的簇逆向到達(dá)源節(jié)點(diǎn)。MRREP經(jīng)過(guò)的簇的簇頭在簇內(nèi)廣播路由序列號(hào)SS，也就是使簇內(nèi)的所有節(jié)點(diǎn)都加入這棵多播樹(shù)。同時(shí)，MRREQ會(huì)在多播區(qū)域內(nèi)繼續(xù)洪泛，與在轉(zhuǎn)發(fā)區(qū)域內(nèi)不同的是收到MRREQ的節(jié)點(diǎn)會(huì)立刻進(jìn)行應(yīng)答，應(yīng)答的目的節(jié)點(diǎn)不再是源節(jié)點(diǎn)而是發(fā)送MRREQ的上一跳節(jié)點(diǎn)。如果一個(gè)簇第二次收到相同的MRREQ，將不予理睬。這樣，在轉(zhuǎn)發(fā)區(qū)域和多播區(qū)域內(nèi)就形成了一棵多播樹(shù)，見(jiàn)圖2紅色線條。

1.4 數(shù)據(jù)的轉(zhuǎn)發(fā)過(guò)程

源節(jié)點(diǎn)在收到MRREQ后，認(rèn)為整棵多播樹(shù)已經(jīng)建好，就開(kāi)始發(fā)送數(shù)據(jù)。數(shù)據(jù)將沿著整棵多播樹(shù)傳播，具體的過(guò)程如下：源節(jié)點(diǎn)把數(shù)據(jù)包發(fā)送給自己所在簇的簇頭，簇頭收到數(shù)據(jù)包以后從簇內(nèi)成員中選擇一個(gè)離多播樹(shù)的下一個(gè)簇最近的節(jié)點(diǎn)，把數(shù)據(jù)包轉(zhuǎn)發(fā)給它。這個(gè)節(jié)點(diǎn)收到數(shù)據(jù)包以后，將它發(fā)送到多播樹(shù)的下一個(gè)簇。下一個(gè)簇的節(jié)點(diǎn)在收到數(shù)據(jù)以后，再把它發(fā)送給自己所在簇的簇頭。經(jīng)過(guò)這樣的循環(huán)往復(fù)，數(shù)據(jù)包會(huì)到達(dá)多播區(qū)域。數(shù)據(jù)包在多播區(qū)域內(nèi)的傳播與在轉(zhuǎn)發(fā)區(qū)域內(nèi)的傳播大體類似，只有3點(diǎn)不同：①多播區(qū)域內(nèi)的簇會(huì)將數(shù)據(jù)包緩存一段時(shí)間再轉(zhuǎn)發(fā)，這是為了避免先收到數(shù)據(jù)包而后收到MRREQ的情況，也是為了避免收到數(shù)據(jù)包時(shí)多播樹(shù)還沒(méi)建完;②每個(gè)簇收到幾個(gè)MRREP，就會(huì)向幾個(gè)簇發(fā)送數(shù)據(jù)包，這對(duì)應(yīng)樹(shù)分枝的情況;③簇頭會(huì)在簇內(nèi)廣播收到的數(shù)據(jù)包，使簇內(nèi)每個(gè)成員都可收到。通過(guò)上述步驟，數(shù)據(jù)先轉(zhuǎn)發(fā)到多播區(qū)域，再轉(zhuǎn)發(fā)到區(qū)域內(nèi)的每個(gè)節(jié)點(diǎn)，整個(gè)多播任務(wù)得以完成。

根據(jù)以上描述，車載網(wǎng)中節(jié)點(diǎn)v運(yùn)行下面的算法：

樹(shù)形多播路由算法：Tree-Multicast-Routing

1 call Clustering //調(diào)用分簇算法

2 if(v is cluster head)

3 call Neighbor-Clusters-Build

4 if(v wants to send multicast message)

5 call Multicast-Tree-Build

6 call Data-Transfer

分簇算法：Clustering

1 compute a W

2 exchange W with neighbors

3 if(v is not cluster head)

4 if(W of v is the largest )

5 resign(u)//請(qǐng)求原來(lái)的簇頭u放棄簇頭地位

6 elect(v)//選自己為簇頭

7 else join(u)//節(jié)點(diǎn)v加入簇頭為u的簇

8 else if(distance to another cluster head<=ICmin and W of v is the largest )

9 resign(u)

鄰居表的建立算法：Neighbor-Clusters-Build

1 broadcast NCREQ

2 if(receive a NCREP)

3 add CID of sender of NCREP and its cluster head position into neighbor-clusters-table

4 else if(receive a NCREQ)

5 add CID of sender of NCREQ and its cluster head position into neighbor-clusters-table

6 send a NCREP

多播樹(shù)的建立算法：Multicast-Tree-Build

1 if(v is source node)

2 send MRREQ to cluster head

3 if(receive a MRREP)

4 return ok

5 if(v is a cluster head and within FZ)

6 send the MRREQ to nodes which are the nearest to its neighbor clusters

7 if(v is a ordinary node and within FZ)

8 if(receive a MRREQ from its cluster head)

9 transfer MRREQ to neighbor cluster

10 else transfer MRREQ to its cluster head

11 if(v is a ordinary node and within MR)

12 if(receive a MRREQ from the cluster within FZ)

13 send a MRREP to the source

14 else send a MRREP to the node from which receive the MRREQ

15 if(receive a MRREP)

16 transfer MRREP to the last hop of MRREQ

數(shù)據(jù)轉(zhuǎn)發(fā)算法：Data-Transfer

1 if(v is source node)

2 send data packet to cluster head

3 if(v is a cluster head)

4 send the data packet to the node which is the nearest to the next cluster

5 if(v is within MR)

6 broadcast the data packet to its member

5 if(v is a ordinary node)

6 transfer the data packet to the next cluster

2 仿真實(shí)驗(yàn)與分析

本文在帶有STRAW模塊的Jist/SWANS上進(jìn)行仿真，Jist/SWANS和ns-2一樣也是專門(mén)用于移動(dòng)自組網(wǎng)絡(luò)的仿真，并且采用Java來(lái)實(shí)現(xiàn)。在某些方面增強(qiáng)了仿真設(shè)置，把路由協(xié)議做成一個(gè)新的路由模塊。同時(shí)，為了使Jist/SWANS/STRAW能滿足仿真要求，同時(shí)對(duì)它做了很多修改。

2.1 仿真設(shè)置

STRAW默認(rèn)使用真實(shí)的道路地圖，公路的長(zhǎng)度為10 km，每個(gè)方向有3個(gè)車道，車輛允許的最大速度為120 km/h，如果車輛前方的車流速度慢，車輛會(huì)改變車道。在仿真開(kāi)始之前，把n個(gè)車輛按照一定的間隔放置到公路上。在跟車模型下，所有的車輛都試圖以最大的速度行駛。仿真參數(shù)的設(shè)置見(jiàn)表1，其中括號(hào)內(nèi)的是默認(rèn)值，一次只改變一個(gè)值，而其他的保持默認(rèn)值。

表1 仿真參數(shù)

Table 1 Simulation parameters

參數(shù)值車輛密度/(輛·km-1)10,45,(272),545通信范圍/m100,150,(200),250多播區(qū)域半徑/km0.5,(1.5),2.5,3.5

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

此部分主要呈現(xiàn)改變車流密度和多播區(qū)域大小后的實(shí)驗(yàn)結(jié)果，主要的評(píng)估標(biāo)準(zhǔn)是時(shí)延和數(shù)據(jù)包投遞率，所有的實(shí)驗(yàn)數(shù)據(jù)都取的是15次仿真結(jié)果的平均值。

2.2.1 不同車流密度

實(shí)驗(yàn)結(jié)果表明，路由協(xié)議在所有的場(chǎng)景下的數(shù)據(jù)包投遞率幾乎為100%，只有在車輛密度極其低的情況下(低于10輛車/km)，數(shù)據(jù)包有時(shí)到不了多播區(qū)域，見(jiàn)圖3。在此情況下，車輛間的平均距離大于100 m，這意味著一旦MRREQ和MRREP信息丟失，一部分多播樹(shù)就建立不起來(lái)。但這種情況不是只有在路由協(xié)議里才會(huì)出現(xiàn)，其他所有的路由協(xié)議在如此低的車輛密度中都會(huì)出現(xiàn)這個(gè)問(wèn)題。而且由于信號(hào)衰減的存在，短距離的多跳比長(zhǎng)距離的一跳要好。

數(shù)據(jù)包傳輸?shù)臅r(shí)延因場(chǎng)景而不同，但都會(huì)隨著車輛密度的增大而出現(xiàn)不同程度的增大。車輛密度大，在簇的形成過(guò)程和鄰居表的建立過(guò)程中，MAC層數(shù)據(jù)包的碰撞概率會(huì)增加，退避時(shí)間會(huì)增大，最后表現(xiàn)出來(lái)就是傳輸時(shí)延的增大。

2.2.2 不同多播區(qū)域大小

傳輸時(shí)延會(huì)隨著多播區(qū)域的增大而增大，原因是更大的區(qū)域意味著需要更多的跳數(shù)，見(jiàn)圖4。但值得慶幸的是多播區(qū)域的半徑大到3.5 km，傳輸時(shí)延≤600 ms，而且數(shù)據(jù)包投遞率也幾乎是100%。

圖3 基于車輛密度的時(shí)延對(duì)比圖Fig.3 Time dalay comparison diagram based on vehicle density

圖4 基于不同多播區(qū)域大小的時(shí)延對(duì)比圖Fig.4 Time delay comparison diagram based on different multicast areas

4 結(jié) 論

本文提出了一種基于分簇和多播樹(shù)的地理多播路由協(xié)議，主要是利用簇的穩(wěn)定性來(lái)實(shí)現(xiàn)數(shù)據(jù)的可靠轉(zhuǎn)發(fā)。雖然分簇和建樹(shù)需要花費(fèi)一定的時(shí)間，但為后續(xù)數(shù)據(jù)包的轉(zhuǎn)發(fā)減少了開(kāi)銷。仿真實(shí)驗(yàn)表明該協(xié)議具有更高的數(shù)據(jù)包投遞率和較低的時(shí)延。

如何實(shí)現(xiàn)車輛密度較低時(shí)數(shù)據(jù)包的可靠轉(zhuǎn)發(fā)和在更真實(shí)的條件下驗(yàn)證協(xié)議有待研究。

[1] Vahdat-Nejad H,Ramazani A,Mohammadi T,et al.A survey on context-aware vehicular network applications[J].Vehicular Communications,2016,3:43-57.

[2] Zhao J,Cao G.VADD: Vehicle-Assisted Data Delivery in Vehicular Ad Hoc Networks[C]// INFOCOM 2006.25th IEEE International Conference on Computer Communications.Proceedings.IEEE,2010:1-12.

[3] 沈虎,王曉東,周興銘,等.一種基于鏈路感知的VANET路由協(xié)議[J].軟件學(xué)報(bào),2011(22):157-164.

[4] 陳貴海,龔海剛,王曉敏,等.基于分布式實(shí)時(shí)信息的車載網(wǎng)絡(luò)路由協(xié)議[J].軟件學(xué)報(bào),2011,22(3):466-480.

[5] Ko Y B,Vaidya N F.Geocasting in mobile ad hoc networks: location-based multicast algorithms[C]// IEEE Workshop on Mobile Computer Systems and Applications.IEEE Computer Society,1999:101.

[6] Perkins C,Belding-Royer E,Das S.Ad hoc On-Demand Distance Vector (AODV)Routing[M].RFC Editor,2000.

[7] Shen X,Wu Y,Xu Z,et al.AODV-PNT: An improved version of AODV routing protocol with predicting node trend in VANET[C]// Advanced Infocomm Technology (ICAIT),2014 IEEE 7th International Conference on.IEEE,2015:91-97.

[8] Karp B,Kung H T.GPSR: greedy perimeter stateless routing for wireless networks[C]// International Conference on Mobile Computing and NETWORKING.ACM,2005:243-254.

[9] Granelli F,Boato G,Kliazovich D,et al.Enhanced GPSR Routing in Multi-Hop Vehicular Communications through Movement Awareness[J].IEEE Communications Letters,2007,11(10):781-783.

[10] Blum J,Eskandarian A,Hoffman L.Mobility management in IVC networks[C]// Intelligent Vehicles Symposium,2003.Proceedings.IEEE.IEEE,2003:150-155.

[11] Kihl M,Sichitiu M,Ekeroth T,et al.Reliable Geographical Multicast Routing in Vehicular Ad-Hoc Networks[C]// International Conference on Wired/wireless Internet Communications.2007:315-325.

A tree multicast routing protocol in VANET

PANG Guo-Bin,TAN Long*,LI Han-Bo,QIN Qi-Bing

(CollegeofComputerScienceandTechnology,HeilongjiangUniversity,Harbin150080)

The high speed of mobile vehicles in vehicular ad-hoc networks leads to a short life span link between two vehicles.In order to improve the packet delivery rate,a geocast routing protocol is proposed based on cluster and tree.This protocol divides vehicles in vehicular ad-hoc networks into clusters.A cluster which consists of several vehicles becomes a data packet transfer station.Vehicles in a cluster coordinate with each other to forward a packet.Then packets are forwarded from one cluster to another cluster and finally reach the destination region.Due to the stability of the cluster,the packet delivery rate will be increased significantly.Compared with existing agreements now through simulation experiment,this protocol shows a higher packet delivery ratio.

VANET (vehicular ad-hoc network); geocast; cluster; multicast tree

10.13524/j.2095-008x.2016.04.061

2016-08-01

國(guó)家自然科學(xué)基金面上項(xiàng)目(81273649);黑龍江省自然科學(xué)基金面上項(xiàng)目(F201434);黑龍江大學(xué)研究生創(chuàng)新科研項(xiàng)目重點(diǎn)項(xiàng)目(YJSCX2016-018HLJU)

龐國(guó)彬(1989-)，男，四川瀘州人，碩士研究生，研究方向：車載網(wǎng),E-mail:767035979@qq.com；*通訊作者：譚 龍(1971-)，男，黑龍江哈爾濱人，副教授，碩士研究生導(dǎo)師，研究方向：傳感器網(wǎng)絡(luò)、數(shù)據(jù)挖掘，E-mail:tanlong@hlju.edu.cn。

TN929.5

A

2095-008X(2016)04-0075-07