基于車流量和粒子群算法的無線接入點布局

李玉貞 ，張麗麗

（河海大學 計算機與信息學院，江蘇 南京 211100）

在近幾十年來，隨著無線通信技術的發展，車載網（Vehicular Ad Hoc networks,VANET）由新興智能交通研究的分支成為無線網絡研究的一個重要的領域。車載自組網(VANET)是一種自組織、結構開放的車輛間通信網絡，是一種特殊的MANET(mobile ad hoc networks，移動自組網)，可以適應不斷變化的網絡拓撲結構，為道路車輛之間、車輛與路邊固定接入點之間提供通信[1]。車輛的高速移動以及街道障礙物阻擋等原因，導致VANETs分割現象更加嚴重。VANETs中接入點（Access point，AP）部署問題非常重要。AP的合理部署可以提高用戶感知度，同時能夠提供接入Internet等服務，好的AP部署可以為網絡用戶提供更好的服務。

然而城市的路況相對于高速環境要復雜的多,一般情況下一個城市的經濟文化比較集中在一個或幾個區域，因此這會造成在某些區域車流量極大，而在某些區域車流量嚴重缺少。這種狀況會直接導致連同性不好的問題。而解決車載網的連通性有很多途徑，例如：廣播技術，時延容忍網絡等。我們這里通過對APs的合理布局來解決這個問題。

文獻[2]提出了一種通過AP平均容量最大化從而使AP數目最小化的算法。文獻[3]提出種基于分析車流量和相對車流量優化的AP布局算法。文獻[4]提出了一種通過利用路邊停靠車輛來最小化AP數目的算法。但是上述研究的方法都比較復雜，而本文提出了一種城市VANET環境下的AP布局方法。通過一定的數學分析得出得出一定范圍內連通所需的AP數目。并給出了VANETs中AP布局問題的數學描述，并提出了一種基于車流量的粒子群算法(Particle swarnl optmization，PSO)求解。該方法工作量小，速度較快。

1 相關工作

1.1 一定車流量下區域達到全連通AP布局分析

在車載自組網中（此刻默認車輛與AP的通信范圍同為R），已經有文獻[5]證明在一定區域間分布的車輛數為泊松分布，車輛之間的間隔為指數分布。則在一定區域內得車輛數目n的概率為：

其中μ為單位長度上車輛數，到達的車輛在一定區域的分布是均勻的，L為區域的長度。利用全概率的公式，因此由文獻[6～8]可以得到:

式中「y」表示對y上取整，u(x)為階躍函數。仿真和分析結果的對比驗證了公式（2）的正確性，如圖（1）可求出相應的Lth。即表示達到覆蓋率P，每隔Lth就要有一個部署一個 AP 。

圖1 L-P 仿真分析圖Fig. 1 Simulation analysis of L-P

1.2 網絡模型

將VANETs空間模型抽象為圖G=G(y，E)的無向圖，在圖中車輛沿著邊從一個端點移動到另外一個端點。式中：端集y是岔路口集合，邊集E是街道的集合。在該無向圖中，車輛沿著邊從一個端點移動到另外一個端點。假定服務節點僅部署在街道上。這樣的假設是合理的，因為道路邊的障礙物對分布在街道上的服務節點和車輛節點之間的通信影響最小假定AP僅部署在街道上。VANETs中AP覆蓋問題要保證網絡擴展覆蓋概率大于設定的值，同時AP個數最小A={a1,a2,…,an}為AP的集合。VANETs中AP部署問題就是在網絡中分布n個AP滿足擴展覆蓋要求的情況下，最小化n。

2 基于(POS)的AP布局方案

2.1 粒子群算法簡介

粒子群算法，也稱粒子群優化算法（Particle Swarm Optimization），縮寫為 PSO[9]，PSO 算法是從隨機解出發，通過迭代尋找最優解，它也是通過適應度來評價解的品質，通過追隨當前搜索到的最優值來尋找全局最優。這種算法以其實現容易、精度高、收斂快等優點引起了學術界的重視，并且在解決實際問題中展示了其優越性。

假設在Q維目標搜索空間中，z個粒子組成粒子群，其中第i個粒子表示一個Z維的向量Xi=[Xi1, Xi2,…,XiQ]T，i=1,2,…,z,每個粒子的位置就是一個潛在解，根據適應值的大小衡量置的優劣。第i個粒子的飛翔速度也是一個Q維的向量，記為Vi=[Vi1, Vi2,…,ViD]TPSO算法根據當前的位置和速度，按照公式(4)和(5)更新每個粒子的速度和位置。

2.2 基于(POS)的AP布局具體方案

1)粒子編碼

由于需要利用粒子群算法，因此需要對問題的解即AP的位置進行編碼。由文章的第二部分可知，要全面覆蓋VANETs，網絡中至少需要AP的個數為：

其中||ek||表示街道的物理長度，「x」表示對上取整，在本文中將每個粒子定義為g，則對粒子進行如下編碼，每個粒子為Q維變量，每個變量由兩個分變量x，y表示一個AP的位置，所以實際上每個解是一個2Q維的變量，適應速度也用相似的編碼。

2)適應值函數

適應值函數反應了要優化的問題，在本文中主要考慮AP的個數和覆蓋率，AP的個數應最小化，覆蓋率最大。則適應函數如下：

在式（7）中σ表示覆蓋率，Am表示第i個AP覆蓋的街道，表示被覆蓋街道的長度，||e||表示為L,k為有效AP數，T1,T2為可調參數。

3)初始化粒子

假設城市環境的區域范圍為(0，0)，(x，0)，(0，Y)，(x，Y)4個點組成的矩形區域。每個粒子中的每個AP在該矩形內隨機產生。隨機產生的粒子，網絡覆蓋率非常低。為了提高算法搜索解的速度，按照一定的比例β(0＜β＜1)產生隨機的解，按比例1-β產生可以全部擴展覆蓋網絡的粒子。就是在道路口上放置N個AP，其中第一個AP點的位置距離岔路口的距離為d，d在 0-Lth之間隨機分布，其余N個AP依次相距2Lth距離。

4)AP的修正

飛行后的粒子表示的AP可能離開了街道，或者走出限定的場景或者街道此處有障礙物不適合放置AP。若AP離開街道，但沒有走出限定的場景或者有障礙物不適合放置AP，這個時候可以使用AP的修正算法進行位置修正。當前服務節點的位置為(x，y)，在街道上找到一個AP(x，y)最近的AP 替換(x，y)。若AP走出了限定的場景或者在障礙物處，則AP為無效AP，需要重新放置。

5)算法流程

算法流程如圖2。

圖2 算法流程圖Fig. 2 Flow chart of PSO algorithm

3 仿真實驗與分析

為了驗證粒子群算法在AP布局中的應用，我們在Matlab環境下實現了基于粒子群算法的AP布局，在仿真時設定參數T1=100，T2=1，粒子數為120，仿真的網絡場景，是由4條街道組成的街區，由圖3可知Lth=1200 m；每條街道長度為4 000 m，因為每條街道的寬度相對于網絡場景可忽略不計，所以圖中沒有表示街道的寬度。圖3中實心圓表示的AP無線信號直接覆蓋區域，以Lth為半徑的虛線圓為滿足網絡擴展覆蓋概率P。圖3表示網絡場景和最優AP部署。最AP部署中有4個節點部署在岔路口區域，4個節點部署在每條街道的中間點上，表1給出了本文算法求得的最優解。圖4是本文算法求得的最優解AP布局情況。

由圖5～7可以看出算法在很短的時間內搜索到了最優解。因為本文設計的適應值函數同時考慮了網絡覆蓋率和AP數，在適應值一直上升的趨勢下，覆蓋率并不是單調的。可以看到，搜索初期網絡中需要的節點數目比較多，覆蓋率為1，隨著搜索的進行，可看出需要的AP數減少，覆蓋率經過一定的震蕩之后又回到了1。

圖3 網絡場景及AP布局Fig. 3 Network scenarios and AP layout

圖4 粒子群算法的AP布局Fig. 4 AP layout of PSO algorithm

圖5 迭代次數 -覆蓋率曲線Fig. 5 Number of Iterations - coverage rate curve

圖6 迭代次數-AP數曲線Fig. 6 Number of Iterations - AP number curve

圖7 迭代次數-適應值曲線Fig. 7 Number of Iterations - adaptive value curve

4 結 論

文中是針對城市環境的VANETs的AP布局問題的研究，提出了基于車流量和粒子群算法的基礎上提出的解決方案，根據相應的仿真，可以看出該算法是能在保證較高覆蓋率的情況下實現AP的數目最小的布局方案，同時在尋優過程中具有較快的收斂速度和較好的收斂性，因此達到了研究的目的。

[1] 王昭然，謝顯中，趙鼎新.車載自組網絡的關鍵技術[J].電信科學,2011,27(1):44-51.WANG Zhao-ran,XIE Xian-zhong,ZHAO Ding-xin.Key Technology of vehicular AD hoc network [J].Telecommunications Science 2011,27(1):44-51.

[2] Fiore M,Barcelo-Ordinas J.M.Cooperative downloading urban vehicular networks[J].IEEE MASS,2009:20-29.

[3] LI Pan,HUANG Xiao-xia,FANG Yu-guang et al Optimal placement of gatewaysin vehicular networks[J].IEEE Vehicular Technology Society,2007(19):3421-3430.

[4] Liu N,LIU Ming,CHEN Gui-hai,et al The sharing at roadside:vehicular content distribution using parked vehicles[J].INFOCOM,2012 Proceedings IEEE,2012:2641-2645.

[5] Desai M,Manjunath D.On the connectivity in finite AdHoc networks[J].IEEE Conunnn Lett,2002,6(10):437—439．

[6] Gore A D.Comments on“On the connectivity in finite Ad Hoc networks”[J].IEEE Commun Lett,2006,10(2):88-90．

[7] Gore A D.Correction to Comments on “On the connectivity in finite Ad Hoc networks”[J].IEEE Commun Lett.2006.10(5):359．

[8] Yousefi s,Altman E,El-Azouzi R,et a1.Analytical model for connectivity in vehicular Ad Hoc networks[J].IEEE Tram Veh Technol,2008,57(6):3341— 3356．

[9] Kennedy J,Eberhart R.Particle swarnl optimization[C]//IEEE International Conference On Neural Networks,Perth,WA,Australia:IEEE,1995:1942-1948．