基于车流量和粒子群算法的无线接入点布局

李玉贞 ，张丽丽

（河海大学 计算机与信息学院，江苏 南京 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．