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

（1.江南大學(xué)江蘇省模式識別與計算智能工程實驗室 無錫 214122）

（2.東南大學(xué)移動通信國家重點實驗室 南京 210096）

1 引言

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

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

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

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

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

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

2 系統(tǒng)模型

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

圖1 多車隊隊間通信場景

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

3 算法介紹

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

3.1 初始化過程

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

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

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

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

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

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

第t次迭代的最小競爭窗口組合按上一次迭代（第t次迭代）中的最小競爭窗口組合按以下步驟更新。

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

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

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

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

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

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

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

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

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

算法1.最小化隊間通信端到端時延智能算法

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

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

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

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

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

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

5 結(jié)語

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