李玉貞 ，張麗麗

（河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，江蘇 南京 211100）

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

然而城市的路況相對(duì)于高速環(huán)境要復(fù)雜的多,一般情況下一個(gè)城市的經(jīng)濟(jì)文化比較集中在一個(gè)或幾個(gè)區(qū)域，因此這會(huì)造成在某些區(qū)域車流量極大，而在某些區(qū)域車流量嚴(yán)重缺少。這種狀況會(huì)直接導(dǎo)致連同性不好的問(wèn)題。而解決車載網(wǎng)的連通性有很多途徑，例如：廣播技術(shù)，時(shí)延容忍網(wǎng)絡(luò)等。我們這里通過(guò)對(duì)APs的合理布局來(lái)解決這個(gè)問(wèn)題。

文獻(xiàn)[2]提出了一種通過(guò)AP平均容量最大化從而使AP數(shù)目最小化的算法。文獻(xiàn)[3]提出種基于分析車流量和相對(duì)車流量?jī)?yōu)化的AP布局算法。文獻(xiàn)[4]提出了一種通過(guò)利用路邊?？寇囕v來(lái)最小化AP數(shù)目的算法。但是上述研究的方法都比較復(fù)雜，而本文提出了一種城市VANET環(huán)境下的AP布局方法。通過(guò)一定的數(shù)學(xué)分析得出得出一定范圍內(nèi)連通所需的AP數(shù)目。并給出了VANETs中AP布局問(wèn)題的數(shù)學(xué)描述，并提出了一種基于車流量的粒子群算法(Particle swarnl optmization，PSO)求解。該方法工作量小，速度較快。

1 相關(guān)工作

1.1 一定車流量下區(qū)域達(dá)到全連通AP布局分析

在車載自組網(wǎng)中（此刻默認(rèn)車輛與AP的通信范圍同為R），已經(jīng)有文獻(xiàn)[5]證明在一定區(qū)域間分布的車輛數(shù)為泊松分布，車輛之間的間隔為指數(shù)分布。則在一定區(qū)域內(nèi)得車輛數(shù)目n的概率為：

其中μ為單位長(zhǎng)度上車輛數(shù)，到達(dá)的車輛在一定區(qū)域的分布是均勻的，L為區(qū)域的長(zhǎng)度。利用全概率的公式，因此由文獻(xiàn)[6～8]可以得到:

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

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

1.2 網(wǎng)絡(luò)模型

將VANETs空間模型抽象為圖G=G(y，E)的無(wú)向圖，在圖中車輛沿著邊從一個(gè)端點(diǎn)移動(dòng)到另外一個(gè)端點(diǎn)。式中：端集y是岔路口集合，邊集E是街道的集合。在該無(wú)向圖中，車輛沿著邊從一個(gè)端點(diǎn)移動(dòng)到另外一個(gè)端點(diǎn)。假定服務(wù)節(jié)點(diǎn)僅部署在街道上。這樣的假設(shè)是合理的，因?yàn)榈缆愤叺恼系K物對(duì)分布在街道上的服務(wù)節(jié)點(diǎn)和車輛節(jié)點(diǎn)之間的通信影響最小假定AP僅部署在街道上。VANETs中AP覆蓋問(wèn)題要保證網(wǎng)絡(luò)擴(kuò)展覆蓋概率大于設(shè)定的值，同時(shí)AP個(gè)數(shù)最小A={a1,a2,…,an}為AP的集合。VANETs中AP部署問(wèn)題就是在網(wǎng)絡(luò)中分布n個(gè)AP滿足擴(kuò)展覆蓋要求的情況下，最小化n。

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

2.1 粒子群算法簡(jiǎn)介

粒子群算法，也稱粒子群優(yōu)化算法（Particle Swarm Optimization），縮寫為 PSO[9]，PSO 算法是從隨機(jī)解出發(fā)，通過(guò)迭代尋找最優(yōu)解，它也是通過(guò)適應(yīng)度來(lái)評(píng)價(jià)解的品質(zhì)，通過(guò)追隨當(dāng)前搜索到的最優(yōu)值來(lái)尋找全局最優(yōu)。這種算法以其實(shí)現(xiàn)容易、精度高、收斂快等優(yōu)點(diǎn)引起了學(xué)術(shù)界的重視，并且在解決實(shí)際問(wèn)題中展示了其優(yōu)越性。

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

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

1)粒子編碼

由于需要利用粒子群算法，因此需要對(duì)問(wèn)題的解即AP的位置進(jìn)行編碼。由文章的第二部分可知，要全面覆蓋VANETs，網(wǎng)絡(luò)中至少需要AP的個(gè)數(shù)為：

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

2)適應(yīng)值函數(shù)

適應(yīng)值函數(shù)反應(yīng)了要優(yōu)化的問(wèn)題，在本文中主要考慮AP的個(gè)數(shù)和覆蓋率，AP的個(gè)數(shù)應(yīng)最小化，覆蓋率最大。則適應(yīng)函數(shù)如下：

在式（7）中σ表示覆蓋率，Am表示第i個(gè)AP覆蓋的街道，表示被覆蓋街道的長(zhǎng)度，||e||表示為L(zhǎng),k為有效AP數(shù)，T1,T2為可調(diào)參數(shù)。

3)初始化粒子

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

4)AP的修正

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

5)算法流程

算法流程如圖2。

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

3 仿真實(shí)驗(yàn)與分析

為了驗(yàn)證粒子群算法在AP布局中的應(yīng)用，我們?cè)贛atlab環(huán)境下實(shí)現(xiàn)了基于粒子群算法的AP布局，在仿真時(shí)設(shè)定參數(shù)T1=100，T2=1，粒子數(shù)為120，仿真的網(wǎng)絡(luò)場(chǎng)景，是由4條街道組成的街區(qū)，由圖3可知Lth=1200 m；每條街道長(zhǎng)度為4 000 m，因?yàn)槊織l街道的寬度相對(duì)于網(wǎng)絡(luò)場(chǎng)景可忽略不計(jì)，所以圖中沒(méi)有表示街道的寬度。圖3中實(shí)心圓表示的AP無(wú)線信號(hào)直接覆蓋區(qū)域，以Lth為半徑的虛線圓為滿足網(wǎng)絡(luò)擴(kuò)展覆蓋概率P。圖3表示網(wǎng)絡(luò)場(chǎng)景和最優(yōu)AP部署。最A(yù)P部署中有4個(gè)節(jié)點(diǎn)部署在岔路口區(qū)域，4個(gè)節(jié)點(diǎn)部署在每條街道的中間點(diǎn)上，表1給出了本文算法求得的最優(yōu)解。圖4是本文算法求得的最優(yōu)解AP布局情況。

由圖5～7可以看出算法在很短的時(shí)間內(nèi)搜索到了最優(yōu)解。因?yàn)楸疚脑O(shè)計(jì)的適應(yīng)值函數(shù)同時(shí)考慮了網(wǎng)絡(luò)覆蓋率和AP數(shù)，在適應(yīng)值一直上升的趨勢(shì)下，覆蓋率并不是單調(diào)的?？梢钥吹剑阉鞒跗诰W(wǎng)絡(luò)中需要的節(jié)點(diǎn)數(shù)目比較多，覆蓋率為1，隨著搜索的進(jìn)行，可看出需要的AP數(shù)減少，覆蓋率經(jīng)過(guò)一定的震蕩之后又回到了1。

圖3 網(wǎng)絡(luò)場(chǎng)景及AP布局Fig. 3 Network scenarios and AP layout

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

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

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

圖7 迭代次數(shù)-適應(yīng)值曲線Fig. 7 Number of Iterations - adaptive value curve

4 結(jié) 論

文中是針對(duì)城市環(huán)境的VANETs的AP布局問(wèn)題的研究，提出了基于車流量和粒子群算法的基礎(chǔ)上提出的解決方案，根據(jù)相應(yīng)的仿真，可以看出該算法是能在保證較高覆蓋率的情況下實(shí)現(xiàn)AP的數(shù)目最小的布局方案，同時(shí)在尋優(yōu)過(guò)程中具有較快的收斂速度和較好的收斂性，因此達(dá)到了研究的目的。

[1] 王昭然，謝顯中，趙鼎新.車載自組網(wǎng)絡(luò)的關(guān)鍵技術(shù)[J].電信科學(xué),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．