多車(chē)隊(duì)隊(duì)間通信端到端時(shí)延最小化研究*

聶淑珍 李正權(quán)，2

（1.江南大學(xué)江蘇省模式識(shí)別與計(jì)算智能工程實(shí)驗(yàn)室 無(wú)錫 214122）

（2.東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室 南京 210096）

1 引言

車(chē)隊(duì)?wèi)?yīng)用是目前智能交通系統(tǒng)中最有前景的應(yīng) 用 之 一［1～2］，車(chē) 隊(duì) 內(nèi) 的 車(chē) 輛 通 過(guò)V2V（Vehi?cle-to-Vehicle）通信周期性地傳輸包含車(chē)輛速度和加速度等與車(chē)輛運(yùn)動(dòng)相關(guān)的數(shù)據(jù)包，使車(chē)隊(duì)中的各車(chē)輛保持恒定的速度和比較小的恒定車(chē)間距［3～5］。每個(gè)車(chē)隊(duì)包含一個(gè)頭部車(chē)輛，一個(gè)尾部車(chē)輛和多個(gè)成員車(chē)輛。頭部車(chē)輛是車(chē)隊(duì)中的第一輛車(chē)，控制著車(chē)隊(duì)的速度和行駛方向；尾部車(chē)輛是車(chē)隊(duì)中的最后一輛車(chē)；成員車(chē)輛處于車(chē)隊(duì)的中間位置。頭部車(chē)輛和尾部車(chē)輛被統(tǒng)稱(chēng)為骨干車(chē)輛［3］。相關(guān)研究表明，形成車(chē)隊(duì)可以促進(jìn)對(duì)車(chē)輛的管理，有效減少交通擁堵，節(jié)約能源并增強(qiáng)交通安全［4～6］。

當(dāng)車(chē)輛的數(shù)目較多時(shí)，為了方便管理，需將車(chē)輛劃分為一個(gè)包含多個(gè)子車(chē)隊(duì)的大車(chē)隊(duì)，稱(chēng)之為多車(chē)隊(duì)［7］。多車(chē)隊(duì)場(chǎng)景如圖1 所示。在多車(chē)隊(duì)中，各骨干車(chē)輛均配備了兩個(gè)收發(fā)器。一個(gè)用于隊(duì)內(nèi)通信，即骨干車(chē)輛與其所屬子車(chē)隊(duì)的成員車(chē)輛間的通信；另一個(gè)用于隊(duì)間通信，即骨干車(chē)輛與其他骨干車(chē)輛的通信。對(duì)于隊(duì)間通信，各骨干車(chē)輛采用的是IEEE 802.11 分布式協(xié)調(diào)功能（Distributed Coordina?tion Function，DCF）協(xié)議來(lái)接入控制信道，并通過(guò)多跳的方式與其他骨干車(chē)輛通信。因此，在這種情況下，隊(duì)間通信端到端時(shí)延會(huì)受各骨干車(chē)輛一跳時(shí)延的影響，而影響各骨干車(chē)輛的一跳時(shí)延的主要因素如下。

1）最小競(jìng)爭(zhēng)窗口。802.11 DCF 協(xié)議采用的是載波監(jiān)聽(tīng)多點(diǎn)接入/沖突避免（Carrier Sensing Medi?um Access/Collision Avoidance，CSMA/CA）機(jī)制訪問(wèn)信道，該機(jī)制采用了二進(jìn)制指數(shù)退避規(guī)則來(lái)減少碰撞，該標(biāo)準(zhǔn)下的最小競(jìng)爭(zhēng)窗口是64，造成各骨干車(chē)輛在退避過(guò)程中耗費(fèi)了大量時(shí)間。

2）直接相鄰的骨干車(chē)輛數(shù)目。多車(chē)隊(duì)隊(duì)間通信中各骨干車(chē)輛只能與其直接相鄰的骨干車(chē)輛通信，各骨干車(chē)輛的通信范圍內(nèi)競(jìng)爭(zhēng)信道資源的骨干車(chē)輛數(shù)目不同，造成各骨干車(chē)輛花費(fèi)在退避凍結(jié)上和重傳分組上的時(shí)間差別大［8～9］，各骨干車(chē)輛的一跳時(shí)延不均衡。

3）隱藏終端的數(shù)目。多車(chē)隊(duì)中各骨干車(chē)輛的隱藏終端數(shù)目受該骨干車(chē)輛所處位置的影響，隱藏終端數(shù)目不同，其發(fā)送分組時(shí)沖突的概率就不同，花費(fèi)在重傳分組上的時(shí)間也就不同［9～10］。各骨干車(chē)輛的一跳時(shí)延不均衡。

車(chē)輛間的安全相關(guān)信息需要被迅速交付，以便在遇到緊急事件時(shí)車(chē)輛能夠及時(shí)接收到信息并采取相應(yīng)措施，增強(qiáng)道路安全［11］。而多車(chē)隊(duì)的所有骨干車(chē)輛均使用IEEE 802.11 DCF標(biāo)準(zhǔn)下的最小競(jìng)爭(zhēng)窗口，且各骨干車(chē)輛直接相鄰骨干車(chē)輛和隱藏終端數(shù)目不等，造成各骨干車(chē)輛的一跳時(shí)延偏大且不均衡，重要信息可能在某一個(gè)骨干車(chē)輛上耽擱較多時(shí)間而無(wú)法迅速交付給其他骨干車(chē)輛，故整個(gè)車(chē)隊(duì)的端到端時(shí)延偏大。因此，本文提出一種降低多車(chē)隊(duì)通信的端到端時(shí)延的信道接入方式，該方式結(jié)合智能算法尋找適合各骨干車(chē)輛節(jié)點(diǎn)的最小競(jìng)爭(zhēng)窗口，降低并平衡各骨干車(chē)輛的一跳時(shí)延，實(shí)現(xiàn)多車(chē)隊(duì)隊(duì)間通信的端到端時(shí)延最小化。仿真結(jié)果表明，與使用標(biāo)準(zhǔn)競(jìng)爭(zhēng)窗口下的端到端時(shí)延相比，本文提出的信道接入方式下在骨干車(chē)輛數(shù)為8 時(shí)，端到端時(shí)延降低約11%，端到端吞吐量增加約5%。且隨著多車(chē)隊(duì)中骨干車(chē)輛數(shù)目的增加，端到端時(shí)延和端到端吞吐量能得到顯著改善。

2 系統(tǒng)模型

在多車(chē)隊(duì)場(chǎng)景中，每個(gè)子車(chē)隊(duì)的骨干車(chē)輛（頭部車(chē)輛和尾部車(chē)輛）通過(guò)隊(duì)間通信周期性地發(fā)送與車(chē)輛運(yùn)動(dòng)相關(guān)的信息，子車(chē)隊(duì)中的骨干車(chē)輛再通過(guò)隊(duì)內(nèi)通信將這些信息發(fā)送給它車(chē)隊(duì)內(nèi)的成員車(chē)輛，以保持車(chē)隊(duì)在道路上的隊(duì)形。本文主要研究隊(duì)間通信。在隊(duì)間通信中，用n 標(biāo)記多車(chē)隊(duì)中子車(chē)隊(duì)的個(gè)數(shù)，那么，多車(chē)隊(duì)里共有2n 個(gè)骨干車(chē)輛，用1，2，…，2n-1，2n 標(biāo)記這些骨干車(chē)輛，骨干車(chē)輛使用隊(duì)間通信專(zhuān)用的收發(fā)器通過(guò)多跳通信技術(shù)與其他骨干車(chē)輛通信。此外，為了保持兩個(gè)連續(xù)車(chē)隊(duì)的聯(lián)系和保證兩個(gè)連續(xù)車(chē)隊(duì)車(chē)輛的安全，骨干車(chē)輛只能與其直接相鄰的前后兩個(gè)骨干車(chē)輛通信［7］。記a為骨干車(chē)輛向前一個(gè)骨干車(chē)輛發(fā)送分組的概率，1-a 為該骨干車(chē)輛向后一個(gè)骨干車(chē)輛發(fā)送分組的概率。

圖1 多車(chē)隊(duì)隊(duì)間通信場(chǎng)景

骨干車(chē)輛均采用IEEE 802.11 DCF協(xié)議來(lái)訪問(wèn)控制信道，該協(xié)議采用CSMA/CA 機(jī)制［12～13］。當(dāng)骨干車(chē)輛有分組要發(fā)送時(shí)，它會(huì)在等待分布式幀間間隔（Distributed Inter-Frame Spacing，DIFS）的時(shí)間后，隨機(jī)從［0，Wk-1］里選擇一個(gè)整數(shù)作為退避計(jì)數(shù)器的初始值，這里k 表示該分組重傳的次數(shù)，Wk是數(shù)據(jù)包被第k 次重傳時(shí)的最小競(jìng)爭(zhēng)窗口大小。若信道被檢測(cè)為空閑，則退避計(jì)數(shù)器的值減1；否則，退避計(jì)數(shù)器的值被凍結(jié)，直到信道再次被檢測(cè)為空閑且在DIFS 時(shí)間段內(nèi)連續(xù)空閑。若退避計(jì)數(shù)器的值遞減到0，骨干車(chē)輛將占用信道傳輸該分組。若骨干車(chē)輛在傳輸分組完成后的短幀間間隔（Short Inter-Frame Spacing，SIFS）周期后沒(méi)有收到確認(rèn)信息，它將從［0，WK+1-1］中隨機(jī)選取一個(gè)整數(shù)值作為退避計(jì)數(shù)器的初始值并開(kāi)始新的退避過(guò)程，這里，WK+1=2 Wk。若重傳次數(shù)達(dá)到最大重傳限制次數(shù)，骨干車(chē)輛將丟棄該分組［14～15］。

3 算法介紹

本節(jié)主要介紹最小化隊(duì)間通信端到端時(shí)延的智能算法。算法分為初始化過(guò)程，迭代尋優(yōu)過(guò)程，最優(yōu)解判定過(guò)程三部分。

3.1 初始化過(guò)程

首先確定m 個(gè)初始化的2n 維隨機(jī)解，即m 個(gè)最小競(jìng)爭(zhēng)窗口組合，每一個(gè)組合里的各值對(duì)應(yīng)多車(chē)隊(duì)中骨干車(chē)輛1，2，…，2n-1，2n 的最小競(jìng)爭(zhēng)窗口值，這些整數(shù)值均從［1，64］里隨機(jī)選取。

3.2 迭代尋優(yōu)過(guò)程

在迭代尋優(yōu)過(guò)程中，m 個(gè)最小競(jìng)爭(zhēng)窗口組合的值被迭代更新，在每次迭代中，都有一個(gè)使得目標(biāo)函數(shù)值最大的最小競(jìng)爭(zhēng)窗口組合。記第t 次迭代中，使目標(biāo)函數(shù)最大的最小競(jìng)爭(zhēng)窗口組合為gbest（t）。

第一次迭代時(shí)，輸入為初始化的m個(gè)最小競(jìng)爭(zhēng)窗口組合，仿真實(shí)驗(yàn)根據(jù)式（1）計(jì)算出使用組合對(duì)應(yīng)的最小競(jìng)爭(zhēng)窗口時(shí)各自的一跳時(shí)延。

其中，Tij(t)表示第t 次迭代下使用第j 個(gè)競(jìng)爭(zhēng)窗口組合時(shí)，第i個(gè)車(chē)輛發(fā)送分組所消耗的總時(shí)間；xij(t)為此時(shí)第i個(gè)骨干車(chē)輛成功發(fā)送的總分組數(shù)；Dij(t)為第i個(gè)車(chē)輛成功發(fā)送一個(gè)分組的平均一跳時(shí)延。

找出其中使得目標(biāo)函數(shù)值最大的組合gbest（t）。目標(biāo)函數(shù)由式（2）給出，該目標(biāo)函數(shù)衡量各骨干車(chē)輛的一跳時(shí)延與Davg的接近程度，Davg為各骨干車(chē)輛實(shí)際可取得的平均最小一跳時(shí)延。目標(biāo)函數(shù)值越大，各骨干車(chē)輛總體的一跳時(shí)延越接近Davg，隊(duì)間通信的端到端時(shí)延就越小。其中，CWj(t)為第t次迭代時(shí)第j個(gè)最小競(jìng)爭(zhēng)窗口組合，f(CWj(t))為第t 次迭代使用第j 個(gè)最小競(jìng)爭(zhēng)窗口組合時(shí)的目標(biāo)函數(shù)值。

第t次迭代的最小競(jìng)爭(zhēng)窗口組合按上一次迭代（第t次迭代）中的最小競(jìng)爭(zhēng)窗口組合按以下步驟更新。

1）使用輪盤(pán)選擇法根據(jù)本次迭代的最小競(jìng)爭(zhēng)窗口組合更新下一次迭代的最小競(jìng)爭(zhēng)窗口組合，在該方法中，各個(gè)最小競(jìng)爭(zhēng)窗口組合被選擇的概率與其對(duì)應(yīng)的目標(biāo)函數(shù)值成正比，即目標(biāo)函數(shù)值越大，該競(jìng)爭(zhēng)窗口組合被選擇的概率越大。選擇概率和相應(yīng)的累積概率如式（3）和式（4）所示。

其中，P(CWj(t))為第t 次迭代第j 個(gè)最小競(jìng)爭(zhēng)窗口組合被選擇的概率，qj(t)為第t 次迭代前j 個(gè)最小競(jìng)爭(zhēng)窗口組合被選擇的累加概率。

2）將第一步得到的組合根據(jù)式（5）計(jì)算，產(chǎn)生新的組合。

其中CWij(t)、CWi(j+1)(t)分別為第t 次迭代時(shí)第j 個(gè)組合和第j+1 個(gè)組合中的第i 個(gè)骨干車(chē)輛的最小競(jìng)爭(zhēng)窗口值，CWij(t+1)、CWi(j+1)(t+1)分別為經(jīng)過(guò)此步驟得到的最小競(jìng)爭(zhēng)窗口值，a1、a2 為［-0.25，1.25］之間的可變隨機(jī)數(shù)。

3）在經(jīng)過(guò)上述步驟之后，以一定的概率隨機(jī)改變各最小競(jìng)爭(zhēng)窗口組合中某一個(gè)骨干車(chē)輛的最小競(jìng)爭(zhēng)窗口值。

3.3 最優(yōu)解判定子過(guò)程

第t次迭代時(shí)，通過(guò)仿真實(shí)驗(yàn)和式（2）計(jì)算出m個(gè)目標(biāo)函數(shù)值和gbest（t），若f（gbest（t））大于指定的精度值或迭代次數(shù)達(dá)到上限，則迭代結(jié)束，gbest（t）即為使得多車(chē)隊(duì)隊(duì)間通信端到端時(shí)延最小化的最小競(jìng)爭(zhēng)窗口組合；否則，按迭代尋優(yōu)過(guò)程的三個(gè)子步驟繼續(xù)更新第t+1次迭代的m個(gè)最小競(jìng)爭(zhēng)窗口組合。尋找最小化隊(duì)間通信端到端時(shí)延最優(yōu)競(jìng)爭(zhēng)窗口組合的智能算法偽代碼見(jiàn)算法1。

4 仿真結(jié)果及其分析

本節(jié)主要比較多車(chē)隊(duì)各骨干車(chē)輛使用IEEE 802.11 DCF 機(jī)制定義的標(biāo)準(zhǔn)競(jìng)爭(zhēng)窗口大小下與本文算法尋找的最小競(jìng)爭(zhēng)窗口下的發(fā)送概率，一跳時(shí)延，端到端時(shí)延和端到端吞吐量。仿真場(chǎng)景如第三節(jié)描述，表1 給出了實(shí)驗(yàn)中使用的參數(shù)。其中CWmin為IEEE 802.11 DCF 機(jī)制中定義的標(biāo)準(zhǔn)最小競(jìng)爭(zhēng)窗口大小［11～12］，E［L］為每個(gè)分組的大小，s 為每個(gè)時(shí)隙占用時(shí)間，M為DCF機(jī)制中定義的最大重傳次數(shù)，R 為信道比特率，pe為由信道引起的傳輸錯(cuò)誤概率，m為迭代時(shí)最小競(jìng)爭(zhēng)窗口組合總個(gè)數(shù)，Im為最大迭代次數(shù)。

算法1.最小化隊(duì)間通信端到端時(shí)延智能算法

按照q從本次迭代的組合里選擇

圖2 給出了當(dāng)多車(chē)隊(duì)中骨干車(chē)輛總數(shù)為8（2n=8）時(shí)，各骨干車(chē)輛使用本文算法得到的最小競(jìng)爭(zhēng)窗口下和使用標(biāo)準(zhǔn)競(jìng)爭(zhēng)窗口下的發(fā)送概率，一跳時(shí)延，端到端時(shí)延和端到端吞吐量。從圖中可以看出，各骨干車(chē)輛均使用標(biāo)準(zhǔn)最小競(jìng)爭(zhēng)窗口時(shí)，其發(fā)送概率不均衡且普遍偏低，而使用本文算法得到的最小競(jìng)爭(zhēng)窗口后，各骨干車(chē)輛的發(fā)送概率約提高了40%。使用標(biāo)準(zhǔn)最小競(jìng)爭(zhēng)窗口時(shí)，各骨干車(chē)輛直接相鄰的骨干車(chē)輛個(gè)數(shù)不等，隱藏終端個(gè)數(shù)不等，造成各骨干車(chē)輛一跳時(shí)延波動(dòng)較大。第1 個(gè)骨干車(chē)輛和第7 個(gè)骨干車(chē)輛的單跳時(shí)延約為2.4ms，而第3、4個(gè)骨干車(chē)輛和第5、6個(gè)骨干車(chē)輛的單跳時(shí)延在4.5ms左右。當(dāng)使用本文算法得到的最小競(jìng)爭(zhēng)窗口后，各骨干車(chē)輛由于采用的競(jìng)爭(zhēng)窗口比標(biāo)準(zhǔn)競(jìng)爭(zhēng)窗口小，且能根據(jù)車(chē)輛位置動(dòng)態(tài)調(diào)整，故其一跳時(shí)延均可維持在3.3ms 低時(shí)延水平，骨干車(chē)輛1 到骨干車(chē)輛8 的端到端時(shí)延降低至24ms，比標(biāo)準(zhǔn)下的端到端時(shí)延減少約11%。此外，從圖中還可觀察到，使用本文算法后，骨干車(chē)輛1 到骨干車(chē)輛8 的端到端吞吐量約為4.2Mbp/s，比標(biāo)準(zhǔn)情況下的端到端吞吐量提高約5%。

表1 仿真參數(shù)列表

圖3 比較了當(dāng)多車(chē)隊(duì)中骨干車(chē)輛數(shù)目為20（2n=20）時(shí)，使用本文算法得到的最小競(jìng)爭(zhēng)窗口下和使用標(biāo)準(zhǔn)最小競(jìng)爭(zhēng)窗口時(shí)隊(duì)間通信的各骨干車(chē)輛的發(fā)送概率，一跳時(shí)延，端到端時(shí)延，端到端吞吐量。從圖中可以看出，使用算法優(yōu)化后的最小競(jìng)爭(zhēng)窗口下的發(fā)送概率普遍比標(biāo)準(zhǔn)情況下的發(fā)送概率高，各骨干車(chē)輛的一跳時(shí)延能維持在3.5ms 左右，第1 個(gè)骨干車(chē)輛到其它各骨干車(chē)輛的端到端時(shí)延，端到端吞吐量隨著骨干車(chē)輛索引數(shù)的增加而線性增加。與使用標(biāo)準(zhǔn)最小競(jìng)爭(zhēng)窗口下端到端時(shí)延相比，本文算法端到端時(shí)延減少了約13%，端到端吞吐量增加了約10%。

圖2 骨干車(chē)輛數(shù)目為20時(shí)隊(duì)間通信性能

圖3 骨干車(chē)輛數(shù)目為20時(shí)隊(duì)間通信性能

5 結(jié)語(yǔ)

為解決多車(chē)隊(duì)隊(duì)間通信端到端時(shí)延較大的問(wèn)題，本文結(jié)合智能算法根據(jù)多車(chē)隊(duì)內(nèi)骨干車(chē)輛數(shù)目動(dòng)態(tài)調(diào)整各骨干車(chē)輛的最小競(jìng)爭(zhēng)窗口，使各骨干車(chē)輛的一跳時(shí)延維持在較低的水平線上，實(shí)現(xiàn)隊(duì)間通信端到端時(shí)延的最小化。仿真結(jié)果表明，通過(guò)使用本文算法得到的最小競(jìng)爭(zhēng)窗口，各骨干車(chē)輛的一跳時(shí)延能維持在低水平線上，且與使用標(biāo)準(zhǔn)最小競(jìng)爭(zhēng)窗口的各指標(biāo)相比，本文算法的發(fā)送概率提高了約40%，端到端時(shí)延降低了11%，且隨著多車(chē)隊(duì)中骨干車(chē)輛數(shù)目的增加，端到端時(shí)延和端到端吞吐量得到顯著改善。