基于ISOA的VANET自適應(yīng)數(shù)據(jù)傳輸算法*

陳秉試

(廈門海洋職業(yè)技術(shù)學(xué)院, 福建 廈門 361012)

基于ISOA的VANET自適應(yīng)數(shù)據(jù)傳輸算法*

陳秉試

(廈門海洋職業(yè)技術(shù)學(xué)院, 福建 廈門 361012)

針對(duì)基于802.11p的車載自組織網(wǎng)絡(luò)(VANET, Vehicular Ad hoc Network)的吞吐量最優(yōu)化問題，采用啟發(fā)式搜索優(yōu)化的思想，在數(shù)據(jù)傳輸方面提出了改進(jìn)的搜索者優(yōu)化算法(ISOA, Improved Seeker Optimization Algorithm)。該算法通過對(duì)節(jié)點(diǎn)發(fā)送概率的最優(yōu)化實(shí)現(xiàn)節(jié)點(diǎn)平均吞吐量的最大化；通過對(duì)吞吐量變化的檢測(cè)調(diào)整發(fā)送概率，實(shí)現(xiàn)對(duì)通信環(huán)境變化的自適應(yīng)性；通過對(duì)在VANET場(chǎng)景下傳統(tǒng)SOA的改進(jìn)，提高了搜索全局最優(yōu)解的成功率。仿真結(jié)果表明，ISOA較傳統(tǒng)算法在環(huán)境變化自適應(yīng)性方面更好，在收斂速度及準(zhǔn)確度等方面性能也更優(yōu)。

車載自組織網(wǎng)絡(luò) 改進(jìn)的搜索者優(yōu)化算法 自適應(yīng)數(shù)據(jù)傳輸算法

0 引 言

車載自組織網(wǎng)以車-車、車-路邊節(jié)點(diǎn)通信為主要模式，以自組織性為核心，并具有拓?fù)涓邉?dòng)態(tài)變化、節(jié)點(diǎn)運(yùn)動(dòng)受道路約束、能量不受限等特點(diǎn)受到關(guān)注，近年來逐漸成為研究熱點(diǎn)[1-2]。

2010年7月，IEEE802.11p修正案發(fā)布并成為VANET中經(jīng)典的MAC層標(biāo)準(zhǔn)。該標(biāo)準(zhǔn)的MAC層方案以IEEE802.11 DCF和IEEE802.11e EDCA為基礎(chǔ)，相關(guān)的性能已經(jīng)有學(xué)者進(jìn)行了研究[3-6]。網(wǎng)絡(luò)吞吐量是一個(gè)重要的性能指標(biāo)，可以通過對(duì)時(shí)隙占用的近似最優(yōu)化[5]或者對(duì)節(jié)點(diǎn)發(fā)送概率的最優(yōu)化[7]實(shí)現(xiàn)最大吞吐量。然而在VANET中，節(jié)點(diǎn)拓?fù)涓叨葎?dòng)態(tài)化，如何在低復(fù)雜度、低網(wǎng)絡(luò)開銷的情況下，讓節(jié)點(diǎn)自適應(yīng)地根據(jù)通信環(huán)境變化調(diào)整參數(shù)保持在最優(yōu)吞吐量已成為挑戰(zhàn)。

啟發(fā)式搜索優(yōu)化算法能很好地解決非線性、多峰目標(biāo)函數(shù)的最優(yōu)化問題，具有很強(qiáng)的實(shí)用性。其中，2007年提出的搜索者優(yōu)化算法(SOA, Seeker Optimization Algorithm)[7]在搜索全局最優(yōu)解方面具有良好的性能，已經(jīng)被應(yīng)用于電子、通信及自動(dòng)化等多個(gè)領(lǐng)域[8-10]，充分體現(xiàn)了該算法的競(jìng)爭(zhēng)力。

通過在VANET場(chǎng)景下對(duì)SOA的改進(jìn)，并應(yīng)用于吞吐量最優(yōu)化中，提出基于ISOA的數(shù)據(jù)傳輸算法。仿真結(jié)果表明，ISOA不僅能快速、高效地獲得全局最優(yōu)解，還能根據(jù)通信環(huán)境自適應(yīng)調(diào)整參量值，具有很強(qiáng)的實(shí)用價(jià)值。

1 VANET吞吐量分析

1.1 VANET場(chǎng)景設(shè)定

將網(wǎng)絡(luò)分簇可提高資源的復(fù)用性并減少競(jìng)爭(zhēng)，因此假設(shè)討論的VANET為已分簇的情況，即預(yù)先已將車輛分組。為增強(qiáng)簇的穩(wěn)定性，假定簇內(nèi)均為同向行駛的車輛?？傮w場(chǎng)景示意圖及基本參數(shù)設(shè)置如圖1所示。

圖1 場(chǎng)景示意圖及基本參數(shù)設(shè)置

1.2 吞吐量分析

在802.11 DCF給定的訪問模式下k為常數(shù)，但用戶數(shù)n的獲取是個(gè)難題，通?？梢岳霉?jié)點(diǎn)之間交互信息或者理論上的近似解決[5]。節(jié)點(diǎn)之間通過信息交互可獲得周邊節(jié)點(diǎn)分布，從而獲知n值，但這將增大網(wǎng)絡(luò)開銷。為了削減交互開銷，可以通過其他參量的檢測(cè)間接感知n的變化，文獻(xiàn)[5]定義了“時(shí)隙利用率”，通過公式的近似推導(dǎo)發(fā)現(xiàn)該參量與節(jié)點(diǎn)數(shù)無關(guān)，并且是可檢測(cè)，每個(gè)節(jié)點(diǎn)通過調(diào)整發(fā)送概率使時(shí)隙利用率達(dá)到最佳，從而達(dá)到最優(yōu)吞吐量。由于近似條件的約束，該方案在n較大時(shí)才會(huì)有較好的近似度，而n較小時(shí)會(huì)有誤差。

然而更棘手的問題在于，現(xiàn)實(shí)場(chǎng)景中由于物理層機(jī)制、信道衰減、多用戶干擾及環(huán)境噪聲干擾、多普勒頻移等因素的不同，即使相同的n也會(huì)有不同的最佳吞吐量。這些影響因素具有很強(qiáng)的隨機(jī)性，并且常常難以用數(shù)學(xué)模型準(zhǔn)確描述。因此，在不同的并且難以數(shù)學(xué)建模的通信環(huán)境下，如何讓節(jié)點(diǎn)將發(fā)送概率τ自適應(yīng)地調(diào)整到最佳值成為關(guān)鍵。

2 基于ISOA的吞吐量最優(yōu)化

SOA是以并行搜索以及迭代更新的方式收斂于全局最優(yōu)，與目前主流的啟發(fā)式算法類似，采用的是“嘗試”的思想，適用于多維、非線性全局最優(yōu)化問題[8-10]。在目標(biāo)函數(shù)構(gòu)成的空間中，SOA構(gòu)造K個(gè)種群，每個(gè)種群擁有P個(gè)搜索者，而每個(gè)搜索者含有D個(gè)變量，變量個(gè)數(shù)即為待優(yōu)化的參量的個(gè)數(shù)。根據(jù)文獻(xiàn)[8]中公式確定第G代中第i個(gè)搜索者的第j維的搜索步長(zhǎng)aij及搜索方向di(G)從而遞推出下一代搜索者位置，直到滿足收斂條件或者達(dá)到最大迭代次數(shù)。

ISOA以SOA為基礎(chǔ)，有3個(gè)關(guān)鍵階段：①利用SOA生成候選發(fā)送概率集合{τd,i}(i=1,2,…,KP)；②檢測(cè)τd,i對(duì)應(yīng)的吞吐量Sd,i是否為最佳值；③ 附加搜索空間再次搜索最優(yōu)解以緩解局部收斂現(xiàn)象。以上三個(gè)階段不斷循環(huán)迭代直到收斂于全局最優(yōu)值Sd,max后即可獲得對(duì)應(yīng)的最佳發(fā)送概率τopt。下面將闡述具體過程，主要目標(biāo)是：①實(shí)現(xiàn)對(duì)通信環(huán)境的自適應(yīng)性；② 解決SOA局部收斂問題。

總體流程如圖2所示。

圖2 ISOA流程

2.1 生成搜索空間

ISOA的核心思想是在最優(yōu)解可能存在的取值范圍內(nèi)篩選，因此首先需要估計(jì)待優(yōu)化變量τ取值范圍，即生成搜索空間。該取值范圍理論上應(yīng)為[0,1]，但由于所討論的問題的用戶數(shù)最少為2，則對(duì)應(yīng)最大的τopt=1/(2k)。另外，τ=0表示節(jié)點(diǎn)不發(fā)送數(shù)據(jù)，也不具有討論價(jià)值，因此最終取值范圍可縮小為(0,1/(2k)]，然后在該搜索空間中隨機(jī)生成KP個(gè)第1代的搜索者。需要說明的是，實(shí)際中節(jié)點(diǎn)對(duì)發(fā)送概率的調(diào)整可通過對(duì)節(jié)點(diǎn)接入信道請(qǐng)求依照概率過濾的方法實(shí)現(xiàn)[5]。

2.2 設(shè)定收斂條件

需要說明的是，車輛節(jié)點(diǎn)自身運(yùn)動(dòng)速度固然快，但是同向道路上車輛間相對(duì)速度較小，除非遇到岔路口或快速超車等情況，一般而言在城市環(huán)境下簇內(nèi)相對(duì)拓?fù)潢P(guān)系可維持在幾秒到幾十秒，而在相對(duì)封閉的高速公路上拓?fù)涑掷m(xù)時(shí)間會(huì)更長(zhǎng)，因此毫秒級(jí)的吞吐量檢測(cè)持續(xù)時(shí)間是可接受的。節(jié)點(diǎn)通過周期地檢測(cè)吞吐量變化自適應(yīng)地調(diào)整發(fā)送概率，這將從根本上實(shí)現(xiàn)對(duì)通信環(huán)境變化的自適應(yīng)，而不需要節(jié)點(diǎn)間交互信息，也不需要對(duì)通信環(huán)境進(jìn)行建模，該方法簡(jiǎn)單易行且具有實(shí)用性。

2.3 解決局部收斂

傳統(tǒng)的SOA機(jī)制會(huì)出現(xiàn)一定概率的早熟現(xiàn)象，即收斂于局部最優(yōu)解。出現(xiàn)這種情況時(shí)，節(jié)點(diǎn)以為已經(jīng)達(dá)到最優(yōu)吞吐量，而不再調(diào)整τd,i。ISOA在節(jié)點(diǎn)收斂后引入階段③解決該問題。關(guān)鍵環(huán)節(jié)是當(dāng)節(jié)點(diǎn)收斂后并不停止搜索，而是在收斂后附加一個(gè)小范圍搜索空間再次搜索，即在收斂點(diǎn)附近一定范圍內(nèi)搜索，若有更優(yōu)解則說明之前收斂于局部節(jié)點(diǎn)，否則認(rèn)為已獲得全局最優(yōu)解。假設(shè)節(jié)點(diǎn)已收斂于發(fā)送概率τopt,pre，定義附加搜索空間的半徑為Δτ=α·τopt,pre，其中α為附加因子，則附加的搜索空間為[τopt,pre-Δτ,τopt,pre+Δτ]，若在該空間內(nèi)再次利用SOA搜索后得到的結(jié)果τopt,now等于τopt,pre則認(rèn)為得到全局最優(yōu)。有兩點(diǎn)需要說明：①理論上，在附加搜索空間搜索后仍有可能導(dǎo)致局部收斂，但實(shí)驗(yàn)表明出現(xiàn)這種情況的概率很??；②該方法是以增加一定迭代次數(shù)為代價(jià)換取更高的全局收斂準(zhǔn)確度，但由于附加空間一般不大，因此新一輪搜索的收斂速度很快，新增的迭代次數(shù)并不多，從而高效地解決了SOA收斂于局部最優(yōu)解的問題。

3 仿真及分析

表1 DCF參數(shù)設(shè)定

再次，還需要設(shè)定ISOA相關(guān)參數(shù)。一部分是沿用傳統(tǒng)SOA中的參數(shù)，則設(shè)定成典型值[8-9]：子種群數(shù)K=3，子種群內(nèi)搜索者個(gè)數(shù)P=4，步長(zhǎng)最小及最大隸屬度分別為μmin=0.011 1及μmax=0.98。另一部分為根據(jù)實(shí)際需要重新設(shè)定的SOA參數(shù)以及新增參數(shù)：只需要對(duì)τ優(yōu)化，則D=1；根據(jù)實(shí)驗(yàn)經(jīng)驗(yàn)值設(shè)定最大迭代次數(shù)1 800，附加因子α=5%，吞吐量容錯(cuò)誤差ΔS=1 b/s，吞吐量檢測(cè)周期為TSd=5 ms。下面將從收斂性及自適應(yīng)性等角度分析ISOA的性能。

3.1 收斂速度及準(zhǔn)確度

對(duì)于啟發(fā)式算法而言，收斂速度越快、收斂到全局最優(yōu)解的準(zhǔn)確度越高，則算法性能越好。收斂速度可以迭代次數(shù)衡量，收斂準(zhǔn)確度則可以總實(shí)驗(yàn)次數(shù)中，收斂到全局最優(yōu)解的次數(shù)所占的比例表征。假設(shè)參與競(jìng)爭(zhēng)的仿真節(jié)點(diǎn)數(shù)為10，不考慮其他環(huán)境變化及干擾的理想情況下，根據(jù)表1參數(shù)可計(jì)算出最佳發(fā)送概率為0.044 98，對(duì)應(yīng)的最佳吞吐量為1.759 2 Mb/s。由于實(shí)際中吞吐量是檢測(cè)參量，并且與發(fā)送概率一一對(duì)應(yīng)，因此以吞吐量為仿真量檢驗(yàn)算法性能。啟發(fā)式算法具有一定隨機(jī)性，實(shí)驗(yàn)中重復(fù)仿真105次(實(shí)驗(yàn)發(fā)現(xiàn)大于105次的重復(fù)仿真的結(jié)果與之相同)并統(tǒng)計(jì)的收斂誤差及迭代次數(shù)分別如圖3和圖4所示。

(a) ISOA

(b) SOA

假定收斂值與真值誤差在1 b/s之內(nèi)時(shí)認(rèn)為收斂成功，由圖3可以直觀地看出，ISOA在100b/s以上的部分比SOA稀疏的多，這就說明ISOA的收斂成功率更高。定量上，在105次的重復(fù)實(shí)驗(yàn)中，SOA成功收斂的次數(shù)為63 019次，收斂準(zhǔn)確度為63.019%；而ISOA成功收斂的次數(shù)為99 941次，收斂準(zhǔn)確度為99.941%，這主要因?yàn)镮SOA增加了附加搜索過程，從而大大改善了準(zhǔn)確度。這一優(yōu)勢(shì)在圖4中也可以看出。SOA有36 981次實(shí)驗(yàn)迭代數(shù)達(dá)到最大迭代次數(shù)1 800，而成功收斂的情況下迭代次數(shù)一般遠(yuǎn)小于該值，這意味著每一次實(shí)驗(yàn)SOA都有36.981%的概率在盡最大努力后也無法準(zhǔn)確收斂。但需要說明的是，ISOA是以增加迭代次數(shù)為代價(jià)換取準(zhǔn)確度的提升。從圖4的數(shù)據(jù)統(tǒng)計(jì)中發(fā)現(xiàn)，在成功收斂的情況下，SOA平均迭代次數(shù)為141.710 024次，而ISOA也取收斂速度最快的前63 019個(gè)實(shí)驗(yàn)結(jié)果求得的均值為158.245 883，增幅為11.67%。當(dāng)TSd=5 ms時(shí)大約相當(dāng)于多耗費(fèi)58 ms，這段時(shí)間對(duì)于VANET而言節(jié)點(diǎn)間相對(duì)拓?fù)鋷缀醪蛔儯虼诉@少量的迭代次數(shù)增幅換取大幅度的準(zhǔn)確度提升是值得的。

3.2 對(duì)通信環(huán)境變化的自適應(yīng)性

通信環(huán)境復(fù)雜多變，固定的數(shù)學(xué)模型通常只能擬合部分特殊場(chǎng)景，啟發(fā)式算法卻能有很好的自適應(yīng)性。保持參與競(jìng)爭(zhēng)的仿真節(jié)點(diǎn)數(shù)為10，考慮環(huán)境變化及干擾時(shí)，最佳吞吐量不總保持在1.759 2 Mb/s，一般會(huì)更差且為時(shí)變值。為了模擬該場(chǎng)景，假設(shè)仿真時(shí)間為500個(gè)TSd，最佳吞吐量初始狀態(tài)為理論最佳值1.759 2 Mb/s，第250個(gè)TSd時(shí)衰減為1 Mb/s，將分別仿真ISOA、SOA的性能。

如圖5所示，當(dāng)節(jié)點(diǎn)數(shù)不變但通信環(huán)境改變導(dǎo)致最佳吞吐量變化時(shí)，ISOA及SOA都能很好地做出自適應(yīng)地調(diào)整，使吞吐量維持在當(dāng)前最優(yōu)值。顯然，只由節(jié)點(diǎn)數(shù)n決定最佳發(fā)送概率的傳統(tǒng)算法[7]不能實(shí)現(xiàn)這種自適應(yīng)性。

值得注意的是，由于啟發(fā)式算法收斂過程需要一定時(shí)間，并且迭代次數(shù)具有一定隨機(jī)性，因此通信環(huán)境變化越頻繁、變化時(shí)間間隔越短，對(duì)算法性能的挑戰(zhàn)越大。為了比對(duì)ISOA及SOA在不同環(huán)境變化頻度下自適應(yīng)性能，定義環(huán)境變化周期ΔTSC，即假定最佳吞吐量真值每間隔ΔTSC隨機(jī)變化一次，保持仿真時(shí)間為2 000個(gè)TSd，分別取不同的ΔTSC觀測(cè)收斂準(zhǔn)確度(為了分析方便，設(shè)ΔTSC為TSd的整數(shù)倍)。

圖5 ISOA及SOA的自適應(yīng)性

如圖6所示，當(dāng)ΔTSC較小時(shí)，ISOA及SOA的準(zhǔn)確度都不高，這是因?yàn)閮煞N算法都需要一定的迭代次數(shù)以收斂到最優(yōu)解，若環(huán)境變化過于頻繁，允許的迭代次數(shù)不足將導(dǎo)致收斂準(zhǔn)確度降低。隨著ΔTSC增大，兩種算法的性能都有所提升，這說明允許迭代次數(shù)越充足對(duì)收斂性能越有利，但I(xiàn)SOA的準(zhǔn)確度明顯優(yōu)于SOA，這得益于ISOA采用抗局部收斂措施。當(dāng)ΔTSC>1 300時(shí)收斂準(zhǔn)確度趨于穩(wěn)定，實(shí)際情況中，VANET節(jié)點(diǎn)拓?fù)浼巴ㄐ怒h(huán)境一般在幾秒內(nèi)變化不大，已位于收斂準(zhǔn)確度穩(wěn)定區(qū)域，可見ISOA具有很強(qiáng)的實(shí)用性。

圖6 不同ΔTSC下，ISOA及SOA的收斂準(zhǔn)確度

4 結(jié) 語

在基于IEEE 802.11p的分簇VANET環(huán)境下，提出基于ISOA的數(shù)據(jù)傳輸算法實(shí)現(xiàn)吞吐量的最優(yōu)化。該算法在傳統(tǒng)SOA的基礎(chǔ)上引入了附加搜索空間的方法，在增加少量迭代次數(shù)的情況下大幅提升收斂準(zhǔn)確度。在通信環(huán)境自適應(yīng)性方面，ISOA可自發(fā)調(diào)整參數(shù)值以使節(jié)點(diǎn)保持在最優(yōu)吞吐量，并且性能優(yōu)于SOA，較傳統(tǒng)算法更具有絕對(duì)優(yōu)勢(shì)。仿真結(jié)果表明，在VANET環(huán)境的特征下，ISOA有很強(qiáng)的實(shí)用價(jià)值。

[1] 徐婷，王新紅，王平. 車聯(lián)網(wǎng)中基于多優(yōu)先級(jí)的自適應(yīng)動(dòng)態(tài)路由協(xié)議[J]. 通信技術(shù)，2014，47(02)：163-166. XU ting,WANG Xin-long,WANG Ping. Multi-Priority Dynamic Adaptive Routing Protocol for VANET[J]. Communications Technology，2014，47(02)：163-166.

[2] 彭好佑，馮文龍. VANET網(wǎng)絡(luò)中一種新的認(rèn)證方法[J]. 通信技術(shù)，2012，45(03)：46-48. PENG Hao-you, FENG Wen-long. A Novel Authentication Method in VANET Network[J]. Communications Technology，2012，45(03)：46-48.

[3] 張本宏，陸陽，吳其林等. 有限負(fù)載下IEEE802.11DCF機(jī)制時(shí)延分析[J].電子測(cè)量與儀器學(xué)報(bào)，2011,25(02):176-180. ZHANG Ben-hong, LU Yang, WU Qi-lin，et al. Delay Analysis for IEEE 802.11 DCF Mechanism in Finite Load[J]. Journal of Electronic Measurement and Instrument, 2011, 25(02): 176-180.

[4] 毛建兵，毛玉明，冷甦鵬等.支持QoS的IEEE802.11EDCA性能研究[J].軟件學(xué)報(bào)，2010,21(04):750-770. MAO Jian-bin，MAO Yu-ming，LENG Su-peng． Research of the QoS-Supporting IEEE 802.11 EDCA Performance[J]． Journal of Software，2010，21(04): 750-770． (in Chinese)

[5] 毛建兵，毛玉明，冷甦鵬． 一種提高IEEE 802. 11 吞吐量和公平性的自適應(yīng)優(yōu)化算法[J]． 電子與信息學(xué)報(bào)，2009，31( 11): 2731-2737．

MAO Jian-bin，MAO Yu-ming，LENG Su-peng． An Adaptive Optimization Scheme for IEEE 802. 11 to Improve Throughput and Fairness Performance[J]． Journal of Electronics & Information Technology，2009，31(11): 2731-2737． (in Chinese)

[6] 張和生，張明洋，孫偉. 基于IEEE802.11p高速車路通信環(huán)境研究[J]. 儀器儀表學(xué)報(bào)，2013，34(05): 1181-1187. ZHANG He-sheng, ZHANG Ming-yang, SUN Wei. Research on Vehicle to Infrastructure High Speed Communication based on IEEE 802.11p [J]. Chinese Journal of Scientific Instrument，2013，34(05):1181-1187.

[7] Binachi G. PerformanceAnalysis of the IEEE 802.11 Distributed Coordination Function[J]. IEEE Journal on Selected Areas in Communications, 2000, 18(3): 535-547.

[8] DAI Chao-hua, ZHU Yun-fang and CHEN Wei-rong. Seeker Optimization Algorithm [C]//2006 International Conference on Computational Intelligence and Security, Guangzhou, 2006. Berlin, Germany:Springer-Verlag, 2007:167-176.

[9] DAI Chao-hua, ZHU Yun-fang and CHEN Wei-rong. Seeker Optimization Algorithm for Digital IIR Filter Design [J]. IEEE Transactions on Industrial Electronics, 2010, 57(5): 1710-1718.

[10] Saha, S.K., Kar, R. and Mandal, D. et al. Seeker Optimisation Algorithm: Application to the Design of Linear Phase Finite Impulse Response Filter [J]. IET Signal Processing, 2012, 6(8): 763-771.

CHEN Bing-shi(1978-), male, lecturer, mainly engaged in communication and information system.

VANET Adaptive Data Transmission Algorithm based on ISOA

CHEN Bing-shi

(Xiamen Ocean Vocational College,Xiamen Fujian 361012,China)

Aiming at the throughput optimization of VANET (Vehicular Ad hoc Network) based on 802.11p, the idea of heuristic-searching optimization is adopted and ISOA (Improved Seeker Optimization Algorithm) proposed in data transmission. By optimizing the transmission probability, this algorithm maximizes the average throughput of each node, and data transmission probability is adjusted automatically by detecting the variation of throughput, thus to achieve self-adaption in accordance with the change of communication environment. Traditional SOA in VANET scene is modified so as to improve the success rate for searching the global optimal solution. Simulation results show that ISOA is more adaptable to the change of communication environment than traditional algorithm and enjoys superiority in the aspect of convergence rate and accuracy.

VANET; ISOA; adaptive data transmission algorithm

date:2014-10-11；Revised date：2015-01-20

TN929.52

A

1002-0802(2015)03-0289-06

陳秉試(1978—)，男，講師，主要研究方向?yàn)橥ㄐ排c信息系統(tǒng)。

10.3969/j.issn.1002-0802.2015.03.009

2014-10-11；

2015-01-20