基于車(chē)輛運(yùn)行管理的多目標(biāo)化V2V數(shù)據(jù)傳遞優(yōu)化研究

尹 乾

（西安外事學(xué)院工學(xué)院，陜西 西安 710077）

引言

1 基于軌跡的多目標(biāo)優(yōu)化數(shù)據(jù)傳遞方法建模

1.1 傳輸延遲與網(wǎng)絡(luò)開(kāi)銷(xiāo)的關(guān)系

傳輸延遲是指信息傳輸過(guò)程中，由于傳輸經(jīng)過(guò)的距離遠(yuǎn)或者一些故障，或者網(wǎng)絡(luò)繁忙，導(dǎo)致傳輸并沒(méi)有準(zhǔn)時(shí)達(dá)到目的地情況。而要提高傳輸效率，就要求數(shù)據(jù)在局域網(wǎng)和廣域網(wǎng)之間傳輸時(shí)不進(jìn)行協(xié)議轉(zhuǎn)換，避免傳輸延遲和抖動(dòng)，因此會(huì)增加網(wǎng)絡(luò)開(kāi)銷(xiāo)。傳輸延遲和網(wǎng)絡(luò)開(kāi)銷(xiāo)對(duì)車(chē)輛自組織網(wǎng)絡(luò)數(shù)據(jù)傳遞都非常重要，但兩個(gè)指標(biāo)之間相互沖突，即一個(gè)指標(biāo)減少時(shí)會(huì)誘發(fā)引起另一個(gè)指標(biāo)增加。如果要兼顧兩個(gè)指標(biāo)，不能簡(jiǎn)單地最小化傳輸延時(shí)或者網(wǎng)絡(luò)開(kāi)銷(xiāo)，也不能按比例分割處理，要通過(guò)方案優(yōu)化來(lái)處理二者之間的關(guān)系，提高傳輸效率[3]。

1.2 交叉路口轉(zhuǎn)發(fā)決策

通過(guò)與交叉路口相連的各方向采取優(yōu)先級(jí)排列的方法進(jìn)行優(yōu)化決策，當(dāng)攜帶數(shù)據(jù)包的車(chē)輛到達(dá)交叉路口處，數(shù)據(jù)包攜帶者根據(jù)數(shù)據(jù)平臺(tái)測(cè)算的優(yōu)先級(jí)別進(jìn)行優(yōu)先級(jí)別的選擇，并實(shí)現(xiàn)自身狀態(tài)信息與數(shù)據(jù)平臺(tái)及周邊車(chē)輛終端之間的數(shù)據(jù)傳遞。預(yù)先計(jì)算好的最優(yōu)決策進(jìn)行下一步轉(zhuǎn)發(fā)方向選擇，它首先檢查自己傳輸范圍內(nèi)是否有向優(yōu)先級(jí)為1的方向（這個(gè)方向由道路段或交叉路口指明）行駛的車(chē)輛，如果有就轉(zhuǎn)發(fā)，若沒(méi)有，再檢查它自己是否向這個(gè)方向行駛，如果是，就不轉(zhuǎn)發(fā)數(shù)據(jù)包[4]。否則就認(rèn)為數(shù)據(jù)包無(wú)法向優(yōu)先級(jí)為1的方向轉(zhuǎn)發(fā)，那么攜帶數(shù)據(jù)包的車(chē)輛再檢查其通信范圍內(nèi)是否有向優(yōu)先級(jí)為2的方向行駛的車(chē)輛，其優(yōu)先級(jí)的決策，如圖1所示。依次類(lèi)推，數(shù)據(jù)包最終會(huì)根據(jù)當(dāng)前交通狀況，以最優(yōu)的選擇向數(shù)據(jù)平臺(tái)或周邊的數(shù)據(jù)包攜帶者車(chē)輛終端轉(zhuǎn)發(fā)信息。

圖1 交叉路口處具有優(yōu)先級(jí)的決策Figure.1 Decision with priority at intersection

車(chē)輛自組織網(wǎng)絡(luò)中數(shù)據(jù)傳遞問(wèn)題可以很好地映射為馬爾可夫決策過(guò)程。其中數(shù)據(jù)包的位置為馬爾可夫決策過(guò)程中的狀態(tài)集，轉(zhuǎn)移概率可以通過(guò)對(duì)車(chē)輛軌跡的分析或通過(guò)道路交通統(tǒng)計(jì)得來(lái)[5]，如圖2所示。

1.3 馬爾可夫決策過(guò)程模型映射

圖2 交叉路口i處馬爾可夫決策過(guò)程模型Figure.2 Markov decision process model at interaction i

此外，選擇數(shù)據(jù)包將哪個(gè)方向傳遞即為馬爾可夫決策過(guò)程的動(dòng)作集，傳遞延遲和網(wǎng)絡(luò)開(kāi)銷(xiāo)都可以看作馬爾可夫決策過(guò)程中需要最小化的值。解馬爾可夫決策過(guò)程的目標(biāo)便是求出最優(yōu)決策，在本問(wèn)題中即是求出數(shù)據(jù)包傳遞過(guò)程中道路網(wǎng)的每個(gè)交叉路口的決策。

根據(jù)相應(yīng)的馬爾可夫決策過(guò)程模型，計(jì)算公式如下：

它的通用表示形式為：

一百多年前人們?cè)谝?guī)劃西克爾高地時(shí)就設(shè)定了一系列明文規(guī)定：“包括你能做什么和不能做什么”。他們相信“規(guī)則是秩序之母，是營(yíng)造和諧的關(guān)鍵，因此一切都應(yīng)該得到管理”，就連起床時(shí)間、窗簾顏色、男人頭發(fā)長(zhǎng)度等等，都需要得到管理。此外“還有一些潛規(guī)則”，比如每家房子的顏色都要遵從規(guī)劃者的意圖。這座被譽(yù)為“克利夫蘭山巔的彩虹”的城市，從一開(kāi)始就被規(guī)劃和建設(shè)成“山巔之城”。由此形成西克爾人“只有規(guī)劃才是最好”的價(jià)值觀、“一絲不茍”的追求目標(biāo)。里查德森太太家第一代移居者就非常贊賞這些規(guī)則，終生踐行、維護(hù)著它們，并且將之一代代傳承下來(lái)。

其中j為交叉路口i的某相鄰交叉路口，Ii為i的相鄰交叉路口集合。

1.4 轉(zhuǎn)移概率的推導(dǎo)

首先考慮這樣的情景：攜帶數(shù)據(jù)包的車(chē)輛到達(dá)交叉路口i，在采取策略的情況下數(shù)據(jù)包通過(guò)道路段eij被傳遞到交叉路口j，便表示當(dāng)前情境下數(shù)據(jù)包被向交叉路口j的方向轉(zhuǎn)發(fā)的概率[6]。很顯然，如果攜帶數(shù)據(jù)包的車(chē)輛遇到向 j方向行駛的車(chē)輛或者它自己向這個(gè)方向行駛，這個(gè)數(shù)據(jù)傳遞過(guò)程便能完成，但是前提是攜帶數(shù)據(jù)包的車(chē)輛沒(méi)有遇到駛向策略中比eij優(yōu)先級(jí)更高的道路段的車(chē)輛，并且它自己也不向優(yōu)先級(jí)更高的道路段上行駛。由此，定義三個(gè)概率事件：

A事件表示某一車(chē)輛在交叉路口i處沒(méi)有遇到駛向比道路段eij優(yōu)先級(jí)更高的道路段的車(chē)輛；

B事件表示某一車(chē)輛在交叉路口i處遇到駛向道路段eij上的車(chē)輛，并且車(chē)輛自己不駛向比道路段eij優(yōu)先級(jí)更高的道路段；

C事件表示某一車(chē)輛駛向道路段eij上的概率。

通過(guò)三個(gè)實(shí)踐的組合推導(dǎo)可以得到轉(zhuǎn)移概率公式如下：

2 多目標(biāo)數(shù)據(jù)傳遞求解策略

2.1 凸組合

凸組合的方法就是將兩個(gè)優(yōu)化目標(biāo)的值函數(shù)通過(guò)加權(quán)進(jìn)行合并，設(shè)定這個(gè)新的數(shù)據(jù)傳遞目標(biāo)為M，在決策π的情況下，交叉路口i處的這個(gè)目標(biāo)函數(shù)表示為：

2.2 帕累托最優(yōu)

解多目標(biāo)馬爾可夫決策過(guò)程還有另一種方法就是求出它的帕累托最優(yōu)決策集。對(duì)于車(chē)輛自組織網(wǎng)絡(luò)數(shù)據(jù)傳遞問(wèn)題，可以先利用求解多目標(biāo)馬爾可夫決策過(guò)程得到它的帕累托最優(yōu)決策集合，再根據(jù)一定的策略選取集合中的決策進(jìn)行數(shù)據(jù)包的轉(zhuǎn)發(fā)[8]。利用馬爾可夫決策過(guò)程優(yōu)化傳輸延遲和網(wǎng)絡(luò)開(kāi)銷(xiāo)這兩個(gè)指標(biāo)，使之最小化。

帕累托最優(yōu)是指資源分配的一種理想狀態(tài)。假定固有的一群人和可分配的資源，如果從一種分配狀態(tài)到另一種狀態(tài)的變化中，在沒(méi)有使任何人境況變壞的前提下，使得至少一個(gè)人變得更好，這就是帕累托改善。帕累托最優(yōu)的狀態(tài)就是不可能再有更多的帕累托改善的狀態(tài);換句話說(shuō)，不可能再改善某些人的境況，而不使任何其他人受損。在車(chē)輛自組織管理中，假設(shè)具有傳輸延遲和網(wǎng)絡(luò)開(kāi)銷(xiāo)兩個(gè)目標(biāo)要通過(guò)馬爾可夫決策過(guò)程最大化這兩個(gè)目標(biāo)的值。假設(shè)兩個(gè)目標(biāo)的值都大于0，兩個(gè)坐標(biāo)軸與凸曲線之間的每個(gè)點(diǎn)都對(duì)應(yīng)一個(gè)決策（連續(xù)情況，離散的情況相似），每個(gè)點(diǎn)都對(duì)應(yīng)兩個(gè)目標(biāo)的值，這兩個(gè)目標(biāo)值便是由相應(yīng)的決策計(jì)算得來(lái)。那么凸曲線上的所有點(diǎn)對(duì)應(yīng)的決策即為此多目標(biāo)馬爾可夫決策過(guò)程的帕累托最優(yōu)決策集合。這個(gè)曲線上所有點(diǎn)的特點(diǎn)即不會(huì)被集合中其他任何一個(gè)點(diǎn)所 dominate[9]。這里，dominate定義這樣描述：兩個(gè)l維值向量，滿(mǎn)足以下條件：

圖3 多目標(biāo)馬爾可夫決策過(guò)程的值曲線（兩個(gè)目標(biāo)）Figure.3 Value curve in multi-target Markov decision process (two targets)

2.3 數(shù)據(jù)傳遞以及錯(cuò)誤恢復(fù)

當(dāng)數(shù)據(jù)包到達(dá)目的交付路口時(shí)，目的車(chē)輛可能不在此位置，無(wú)法直接交付，主要考慮兩種情況。第一種是目地車(chē)輛比數(shù)據(jù)包先到達(dá)目的交叉路口 id。當(dāng)攜帶數(shù)據(jù)包的車(chē)輛到達(dá)id在其通信范圍內(nèi)沒(méi)有找到目的車(chē)輛，于是檢查時(shí)間戳，這時(shí)會(huì)發(fā)現(xiàn)目的車(chē)輛已經(jīng)駛過(guò)此處，這時(shí)數(shù)據(jù)包會(huì)被沿著目的車(chē)輛的軌跡的方向繼續(xù)轉(zhuǎn)發(fā)（不再使用之前計(jì)算出的策略），直至追上目的車(chē)輛交付成功或者到達(dá)TTL而被丟棄。第二種情況即數(shù)據(jù)包比目地車(chē)輛提前到達(dá)目的交叉路口 id。此情況下，數(shù)據(jù)包會(huì)被朝著目的車(chē)輛軌跡相反的方向繼續(xù)轉(zhuǎn)發(fā)直至與目的車(chē)輛相遇并交付或者達(dá)到網(wǎng)絡(luò)生存時(shí)間被丟棄。

3 測(cè)試與評(píng)估

3.1 實(shí)驗(yàn)設(shè)定

為了使實(shí)驗(yàn)結(jié)果更為真實(shí)，使用真實(shí)的車(chē)輛軌跡數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。目前，有三個(gè)一線城市公開(kāi)了的車(chē)輛軌跡數(shù)據(jù)集：SUVnet數(shù)據(jù)集、Geolife數(shù)據(jù)集、車(chē)輛GPS軌跡數(shù)據(jù)集等，其中規(guī)模最大的公開(kāi)數(shù)據(jù)集是SUVnet數(shù)據(jù)集，其中包括近5 000輛不同類(lèi)型的車(chē)輛，包括出租車(chē)、公交車(chē)、社會(huì)車(chē)輛，其運(yùn)行軌跡數(shù)據(jù)連續(xù)一個(gè)多月。

原始數(shù)據(jù)逐條記錄了某時(shí)刻對(duì)應(yīng)車(chē)輛的位置、運(yùn)行狀態(tài)等信息。記錄中每一列分別表示為：記錄 ID標(biāo)識(shí)、車(chē)輛當(dāng)前位置所在經(jīng)度、車(chē)輛當(dāng)前位置所在緯度、車(chē)輛速度、角度，記錄時(shí)間的六列為年、月、日、時(shí)、分、秒，最后兩列分別為擴(kuò)展?fàn)顟B(tài)和保留字段。此外，如果單獨(dú)以車(chē)輛為單位來(lái)看，數(shù)據(jù)大約以每 30 s記錄一次。選取了某市中心區(qū)域的 12.6 km×12.9 km的區(qū)域作為我們的實(shí)驗(yàn)區(qū)域，如圖4所示。我們選取了此區(qū)域中的主次干道和比鄰的比較寬的道路，制作了區(qū)域的路網(wǎng)圖，標(biāo)注出各交叉路口的信息，將路網(wǎng)與交叉路口信息以數(shù)據(jù)格式存儲(chǔ)在電子地圖中，作為實(shí)驗(yàn)研究區(qū)域，如圖4所示。

圖4 實(shí)驗(yàn)區(qū)域Figure.4 Text area

結(jié)合算法將道路環(huán)境建模稱(chēng)為有向圖即路網(wǎng)圖，并將數(shù)據(jù)集中的數(shù)據(jù)映射到路網(wǎng)圖上。將無(wú)線通信的范圍假設(shè)為半徑相等的圓，其半徑設(shè)定為200m。選取了某區(qū)域中的3996輛不同類(lèi)型的車(chē)輛進(jìn)行實(shí)驗(yàn)，區(qū)域中最大的車(chē)輛密度處為93.9輛/千米。此外，不考慮周?chē)ㄖ铩⒕G化帶等環(huán)境對(duì)無(wú)線傳輸?shù)挠绊憽?/p>

3.2 實(shí)驗(yàn)結(jié)果和分析

3.2.1 凸組合評(píng)估

凸組合是一類(lèi)特殊的線性組合，是若干個(gè)點(diǎn)的某種特定意義下的非負(fù)線性組合?；谲?chē)輛自組織網(wǎng)絡(luò)中車(chē)輛軌跡的多目標(biāo)化數(shù)據(jù)傳遞特性與凸組合非付線性的類(lèi)似性，現(xiàn)決定選用凸組合法去評(píng)價(jià)數(shù)據(jù)傳遞中多個(gè)目標(biāo)傳遞的不穩(wěn)定性。凸組合法求解多目標(biāo)的馬爾可夫決策過(guò)程，一般是先分析各目標(biāo)的關(guān)系，指定凸組合參數(shù)，或者利用不同的凸組合參數(shù)值分別求解，通過(guò)比較獲得最佳效果。設(shè)定不同的凸組合參數(shù)α的值，選擇不同類(lèi)型、一定數(shù)量的車(chē)輛進(jìn)行實(shí)驗(yàn)，其實(shí)驗(yàn)結(jié)果如圖5所示，圖5中的（a）、（b）、（c）分別為V2V數(shù)據(jù)傳遞中α的值變化對(duì)交付率、網(wǎng)絡(luò)開(kāi)銷(xiāo)、數(shù)據(jù)傳輸效率的影響。由圖5可以看出，當(dāng)α的值取0.9時(shí)，對(duì)應(yīng)交付率高、網(wǎng)絡(luò)開(kāi)銷(xiāo)較低、傳輸效率大，綜合評(píng)價(jià)效果最優(yōu)。

圖5 V2V數(shù)據(jù)傳遞中α值的變化對(duì)交付率、網(wǎng)絡(luò)開(kāi)銷(xiāo)及數(shù)據(jù)傳輸效率的影響Figure.5 Impact of αchange on delivery rate, network overhead and data transmission efficiency in data transmission

由于V2V的數(shù)據(jù)傳遞方法具有通用性，很方便地可以把V2V的數(shù)據(jù)傳遞方法轉(zhuǎn)化為V2I和I2V的方法，OVDF法對(duì)于優(yōu)化傳輸延遲的V2I較佳。為了進(jìn)一步論證α值對(duì)交付率、網(wǎng)絡(luò)開(kāi)銷(xiāo)、數(shù)據(jù)傳輸效率的影響確定性，現(xiàn)將TMOD F法與OVDF法進(jìn)行比較試驗(yàn)。

實(shí)驗(yàn)中，設(shè)定目的節(jié)點(diǎn)即AP的數(shù)目為3個(gè)，按照OVDF的方案，數(shù)據(jù)包被傳遞到3個(gè)AP中的任何一個(gè)便視為交付成功。將TMODF法也作此設(shè)定，且不使用任何額外的基礎(chǔ)設(shè)施來(lái)輔助數(shù)據(jù)傳遞，只要求數(shù)據(jù)包攜帶者車(chē)輛終端之間進(jìn)行數(shù)據(jù)傳遞。兩種方法均將α的值設(shè)定為0.9，觀測(cè)α的值對(duì)交付率、網(wǎng)絡(luò)開(kāi)銷(xiāo)、數(shù)據(jù)傳遞效率等要素的影響。

通過(guò)實(shí)驗(yàn)看出，目的節(jié)點(diǎn)的移動(dòng)性會(huì)給數(shù)據(jù)傳輸帶來(lái)更大的不確定性，在相同的車(chē)輛密度下，TMODF法獲取的交付率比OVDF法獲取的交付率高，TMODF法對(duì)于V2I的交付率比對(duì)V2V的交付率高。TMODF法隨著車(chē)輛密度的不斷提高，有更多的車(chē)輛節(jié)點(diǎn)能夠作為中繼節(jié)點(diǎn)協(xié)助數(shù)據(jù)傳遞，交付率也是不斷提高，這是由于當(dāng)網(wǎng)絡(luò)中的車(chē)輛數(shù)目增加時(shí)，有更多車(chē)輛節(jié)點(diǎn)可以作為中繼節(jié)點(diǎn)對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)發(fā)。OVDF法只對(duì)傳輸延遲進(jìn)行了優(yōu)化，對(duì)網(wǎng)絡(luò)開(kāi)銷(xiāo)考慮前充分。若同時(shí)考慮傳輸延遲和網(wǎng)絡(luò)開(kāi)銷(xiāo)，OVDF法在傳輸延遲方面的優(yōu)化效果要高于本研究中的多目標(biāo)方案，但是，數(shù)據(jù)傳遞的效率也要考慮其對(duì)交付率、網(wǎng)絡(luò)開(kāi)銷(xiāo)等指標(biāo)的影響。

3.2.2 帕累托最優(yōu)評(píng)估

理論上講，不管是用凸組合法，還是帕累托最優(yōu)法，其研究對(duì)象及其試驗(yàn)區(qū)域是一樣的。在凸組合法中α的值可以有無(wú)窮多個(gè)，從無(wú)窮多個(gè)方案中選出最優(yōu)的，而帕累托最優(yōu)法卻無(wú)法實(shí)現(xiàn)這樣條件的選擇。此外，利用帕累托最優(yōu)法求解多目標(biāo)馬爾可夫決策方案，其需求空間較大。在利用帕累托最優(yōu)法求解過(guò)程中，每次迭代選取帕累托最優(yōu)決策集合，距離均值最近的點(diǎn)以及對(duì)應(yīng)的決策予以保留，并參與下次迭代計(jì)算。每輪迭代時(shí)帕累托最優(yōu)策略的數(shù)量均呈指數(shù)型增長(zhǎng)。此外在每輪迭代還保留帕累托最優(yōu)決策集合中傳輸延遲最小的點(diǎn)和網(wǎng)絡(luò)開(kāi)銷(xiāo)最小的點(diǎn)。

在傳遞時(shí)選擇使用折衷的策略進(jìn)行V2V數(shù)據(jù)傳遞分析，并與凸組合中α值為0.9時(shí)進(jìn)行比較。將多目標(biāo)馬爾可夫決策過(guò)程利用帕累托最優(yōu)法與凸組合法在交付率、延遲時(shí)間、網(wǎng)絡(luò)開(kāi)銷(xiāo)、數(shù)據(jù)傳輸效率等要素進(jìn)行比較。同時(shí)，針對(duì)研究的車(chē)輛，對(duì)帕累托最優(yōu)方案中保留的三個(gè)策略在各數(shù)據(jù)傳遞指標(biāo)上進(jìn)行比較，見(jiàn)表1。

表1 車(chē)輛數(shù)目固定的情況下三種策略的各指標(biāo)比較Table.1 Comparison of indicators of three strategies when vehicle number is fixed

由表1可以看出：折衷策略相比其他兩個(gè)方案在交付率和數(shù)據(jù)傳遞效率上都取得了較好的效果。另外，側(cè)重于優(yōu)化傳輸延遲所取得的效果明顯優(yōu)于側(cè)重于優(yōu)化網(wǎng)絡(luò)開(kāi)銷(xiāo)效果。

4 結(jié)論

本文通過(guò)在設(shè)定試驗(yàn)區(qū)域內(nèi)，將車(chē)輛自組織網(wǎng)絡(luò)數(shù)據(jù)傳遞問(wèn)題建模，選定不同類(lèi)型的試驗(yàn)車(chē)輛并采集分析車(chē)輛歷史軌跡、統(tǒng)計(jì)道路交通運(yùn)行狀況等手段，挖掘多目標(biāo)馬爾可夫決策過(guò)程參數(shù)，求得數(shù)據(jù)傳遞的最優(yōu)解，利用最優(yōu)解來(lái)指導(dǎo)真實(shí)的數(shù)據(jù)傳遞過(guò)程。此外，還設(shè)定了錯(cuò)誤恢復(fù)過(guò)程對(duì)預(yù)測(cè)目的交叉路口的錯(cuò)誤進(jìn)行恢復(fù)，提高了數(shù)據(jù)交付率。最后，利用數(shù)據(jù)集驗(yàn)證了多目標(biāo)優(yōu)化數(shù)據(jù)傳遞方法TMODF的有效性。本文作為項(xiàng)目研究課題的一部分，在試驗(yàn)條件的界定、選取研究對(duì)象的代表性等方面難免以偏概全。另外，隨著Alios操作系統(tǒng)、阿里云Link、5G網(wǎng)絡(luò)、北斗導(dǎo)航系統(tǒng)(BeiDou Navigation Satellite System，BDS)、GPS、電子地圖、實(shí)時(shí)道路數(shù)據(jù)、車(chē)輛運(yùn)行軌跡等技術(shù)平臺(tái)被廣泛應(yīng)用于車(chē)輛自組織網(wǎng)絡(luò)中，以及無(wú)人駕駛汽車(chē)的推廣應(yīng)用，優(yōu)化傳輸延遲、網(wǎng)絡(luò)開(kāi)銷(xiāo)、交付率等車(chē)輛自組織網(wǎng)絡(luò)參數(shù)，已成為數(shù)據(jù)傳遞中不可或缺的重要指標(biāo)，這些指標(biāo)的優(yōu)化情況，將直接影響未來(lái)智能交通技術(shù)的應(yīng)用與推廣。