基于ISOA的VANET自適應數據傳輸算法*

陳秉試

(廈門海洋職業技術學院, 福建 廈門 361012)

基于ISOA的VANET自適應數據傳輸算法*

陳秉試

(廈門海洋職業技術學院, 福建 廈門 361012)

針對基于802.11p的車載自組織網絡(VANET, Vehicular Ad hoc Network)的吞吐量最優化問題，采用啟發式搜索優化的思想，在數據傳輸方面提出了改進的搜索者優化算法(ISOA, Improved Seeker Optimization Algorithm)。該算法通過對節點發送概率的最優化實現節點平均吞吐量的最大化；通過對吞吐量變化的檢測調整發送概率，實現對通信環境變化的自適應性；通過對在VANET場景下傳統SOA的改進，提高了搜索全局最優解的成功率。仿真結果表明，ISOA較傳統算法在環境變化自適應性方面更好，在收斂速度及準確度等方面性能也更優。

車載自組織網絡 改進的搜索者優化算法 自適應數據傳輸算法

0 引 言

車載自組織網以車-車、車-路邊節點通信為主要模式，以自組織性為核心，并具有拓撲高動態變化、節點運動受道路約束、能量不受限等特點受到關注，近年來逐漸成為研究熱點[1-2]。

2010年7月，IEEE802.11p修正案發布并成為VANET中經典的MAC層標準。該標準的MAC層方案以IEEE802.11 DCF和IEEE802.11e EDCA為基礎，相關的性能已經有學者進行了研究[3-6]。網絡吞吐量是一個重要的性能指標，可以通過對時隙占用的近似最優化[5]或者對節點發送概率的最優化[7]實現最大吞吐量。然而在VANET中，節點拓撲高度動態化，如何在低復雜度、低網絡開銷的情況下，讓節點自適應地根據通信環境變化調整參數保持在最優吞吐量已成為挑戰。

啟發式搜索優化算法能很好地解決非線性、多峰目標函數的最優化問題，具有很強的實用性。其中，2007年提出的搜索者優化算法(SOA, Seeker Optimization Algorithm)[7]在搜索全局最優解方面具有良好的性能，已經被應用于電子、通信及自動化等多個領域[8-10]，充分體現了該算法的競爭力。

通過在VANET場景下對SOA的改進，并應用于吞吐量最優化中，提出基于ISOA的數據傳輸算法。仿真結果表明，ISOA不僅能快速、高效地獲得全局最優解，還能根據通信環境自適應調整參量值，具有很強的實用價值。

1 VANET吞吐量分析

1.1 VANET場景設定

將網絡分簇可提高資源的復用性并減少競爭，因此假設討論的VANET為已分簇的情況，即預先已將車輛分組。為增強簇的穩定性，假定簇內均為同向行駛的車輛。總體場景示意圖及基本參數設置如圖1所示。

圖1 場景示意圖及基本參數設置

1.2 吞吐量分析

在802.11 DCF給定的訪問模式下k為常數，但用戶數n的獲取是個難題，通常可以利用節點之間交互信息或者理論上的近似解決[5]。節點之間通過信息交互可獲得周邊節點分布，從而獲知n值，但這將增大網絡開銷。為了削減交互開銷，可以通過其他參量的檢測間接感知n的變化，文獻[5]定義了“時隙利用率”，通過公式的近似推導發現該參量與節點數無關，并且是可檢測，每個節點通過調整發送概率使時隙利用率達到最佳，從而達到最優吞吐量。由于近似條件的約束，該方案在n較大時才會有較好的近似度，而n較小時會有誤差。

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

2 基于ISOA的吞吐量最優化

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

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

總體流程如圖2所示。

圖2 ISOA流程

2.1 生成搜索空間

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

2.2 設定收斂條件

需要說明的是，車輛節點自身運動速度固然快，但是同向道路上車輛間相對速度較小，除非遇到岔路口或快速超車等情況，一般而言在城市環境下簇內相對拓撲關系可維持在幾秒到幾十秒，而在相對封閉的高速公路上拓撲持續時間會更長，因此毫秒級的吞吐量檢測持續時間是可接受的。節點通過周期地檢測吞吐量變化自適應地調整發送概率，這將從根本上實現對通信環境變化的自適應，而不需要節點間交互信息，也不需要對通信環境進行建模，該方法簡單易行且具有實用性。

2.3 解決局部收斂

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

3 仿真及分析

表1 DCF參數設定

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

3.1 收斂速度及準確度

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

(a) ISOA

(b) SOA

假定收斂值與真值誤差在1 b/s之內時認為收斂成功，由圖3可以直觀地看出，ISOA在100b/s以上的部分比SOA稀疏的多，這就說明ISOA的收斂成功率更高。定量上，在105次的重復實驗中，SOA成功收斂的次數為63 019次，收斂準確度為63.019%；而ISOA成功收斂的次數為99 941次，收斂準確度為99.941%，這主要因為ISOA增加了附加搜索過程，從而大大改善了準確度。這一優勢在圖4中也可以看出。SOA有36 981次實驗迭代數達到最大迭代次數1 800，而成功收斂的情況下迭代次數一般遠小于該值，這意味著每一次實驗SOA都有36.981%的概率在盡最大努力后也無法準確收斂。但需要說明的是，ISOA是以增加迭代次數為代價換取準確度的提升。從圖4的數據統計中發現，在成功收斂的情況下，SOA平均迭代次數為141.710 024次，而ISOA也取收斂速度最快的前63 019個實驗結果求得的均值為158.245 883，增幅為11.67%。當TSd=5 ms時大約相當于多耗費58 ms，這段時間對于VANET而言節點間相對拓撲幾乎不變，因此這少量的迭代次數增幅換取大幅度的準確度提升是值得的。

3.2 對通信環境變化的自適應性

通信環境復雜多變，固定的數學模型通常只能擬合部分特殊場景，啟發式算法卻能有很好的自適應性。保持參與競爭的仿真節點數為10，考慮環境變化及干擾時，最佳吞吐量不總保持在1.759 2 Mb/s，一般會更差且為時變值。為了模擬該場景，假設仿真時間為500個TSd，最佳吞吐量初始狀態為理論最佳值1.759 2 Mb/s，第250個TSd時衰減為1 Mb/s，將分別仿真ISOA、SOA的性能。

如圖5所示，當節點數不變但通信環境改變導致最佳吞吐量變化時，ISOA及SOA都能很好地做出自適應地調整，使吞吐量維持在當前最優值。顯然，只由節點數n決定最佳發送概率的傳統算法[7]不能實現這種自適應性。

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

圖5 ISOA及SOA的自適應性

如圖6所示，當ΔTSC較小時，ISOA及SOA的準確度都不高，這是因為兩種算法都需要一定的迭代次數以收斂到最優解，若環境變化過于頻繁，允許的迭代次數不足將導致收斂準確度降低。隨著ΔTSC增大，兩種算法的性能都有所提升，這說明允許迭代次數越充足對收斂性能越有利，但ISOA的準確度明顯優于SOA，這得益于ISOA采用抗局部收斂措施。當ΔTSC>1 300時收斂準確度趨于穩定，實際情況中，VANET節點拓撲及通信環境一般在幾秒內變化不大，已位于收斂準確度穩定區域，可見ISOA具有很強的實用性。

圖6 不同ΔTSC下，ISOA及SOA的收斂準確度

4 結 語

在基于IEEE 802.11p的分簇VANET環境下，提出基于ISOA的數據傳輸算法實現吞吐量的最優化。該算法在傳統SOA的基礎上引入了附加搜索空間的方法，在增加少量迭代次數的情況下大幅提升收斂準確度。在通信環境自適應性方面，ISOA可自發調整參數值以使節點保持在最優吞吐量，并且性能優于SOA，較傳統算法更具有絕對優勢。仿真結果表明，在VANET環境的特征下，ISOA有很強的實用價值。

[1] 徐婷，王新紅，王平. 車聯網中基于多優先級的自適應動態路由協議[J]. 通信技術，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網絡中一種新的認證方法[J]. 通信技術，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] 張本宏，陸陽，吳其林等. 有限負載下IEEE802.11DCF機制時延分析[J].電子測量與儀器學報，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].軟件學報，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 吞吐量和公平性的自適應優化算法[J]． 電子與信息學報，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高速車路通信環境研究[J]. 儀器儀表學報，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—)，男，講師，主要研究方向為通信與信息系統。

10.3969/j.issn.1002-0802.2015.03.009

2014-10-11；

2015-01-20