一个基于粒子群算法的车联网路侧单元部署方法

摘要

本发明提出了一种基于粒子群算法的车联网路侧单元部署方法，目的在于在给定路网范围内、给定路侧单元数量的情况下，确定能使部署效益近似最优的路侧单元部署方案。本发明首先建立路网模型，该路网模型能够描述曲线路段。然后根据路网中的各路段的车辆密度、所处区域特性、车道数等综合确定路段的权重密度，把路侧单元集合的无线覆盖范围之内的所有路段的加权权重之和作为路侧单元集合的覆盖效益，建立效益模型。路网模型和效益模型共同组成路侧单元部署问题模型，将路侧单元部署问题转化为搜索最优解问题。最后利用粒子群算法对搜索最优解问题进行优化求解。该方法能够逐步逼近最优部署效益，以尽量最优化路侧单元的部署效益。

主权项

一种基于粒子群算法的车联网路侧单元部署方法，其特征在于如下步骤：步骤1：建立路网模型：将某个路段e表示为e(v_h,v_t,f_t,f_w)，其中v_h为路段e的起点，v_t为路段e的终点，f_t为路段e的路线函数，f_w为路段e的权重函数；步骤2：建立效益模型：将路网部署总效益B_n表示如下：$B_n=\underset{e\in U}{\Sigma }\underset{e}{\int }{f}_{w,e}(x,y)\mathrm{ds}+\underset{M_e\in S}{\Sigma }\underset{M_e}{\int }{f}_{w,e}(x,y)\mathrm{ds}---\left(1\right)$其中符号U为n个路侧单元的全覆盖路段的集合，符号S为其部分覆盖路段的集合，符号M_e为路段e在路网中所有路侧单元的覆盖区域内的部分；步骤3：利用粒子群算法对路侧单元部署问题进行优化求解；步骤如下：步骤3.1：构造个体在粒子群算法求解路边单元部署问题中，每个粒子p作为一个可行解组成粒子群P；构造给出粒子p：假设路网中需要部署n个路侧单元，每个路侧单元在路网中的位置信息为l(x,y)，则n个路侧单元构成一个位置序列L(l₁(x,y),l₂(x,y),...,l_n(x,y))；可以看出，位置序列L(l₁(x,y),l₂(x,y),...,l_n(x,y))和可行解p是一一对应的关系；又因为每个可行解由三部分组成，即粒子的位置、速度和适应度值；则粒子i结构表示为：particle(i)＝{      location[],      velocity[]，                   (2)      fitness}粒子的位置编码结构表示为：particle(i).location[]＝L(l₁(x,y),l₂(x,y),...,l_n(x,y))          (3)粒子的速度编码结构表示为：particle(i).velocity[]＝V(v₁(x,y),v₂(x,y),...,v_n(x,y))           (4)步骤3.2：初始化粒子群随机生成m个位置序列L(l₁(x,y),l₂(x,y),...,l_n(x,y))和速度序列V(v₁(x,y),v₂(x,y),...,v_n(x,y))，并初始化对应的适应度值，组成m个粒子，分别记为P₁,P₂,...,P_m；每个P是一个粒子，m个粒子组成一个粒子群；步骤3.3：设定适应度函数用式(1)路网部署总效益B_n作为适应度值；粒子的适应度值记为：particle(i).fitness＝B_n   (5)步骤3.4：更新自身最优算子和全局最优算子自身最优算子p_id记录每个粒子到目前为止自己所经历过的最优解，通过自身所经历的最优解来不断调整自身的位置；全局最优算子p_gd记录整个粒子群经历过的最好位置，通过此位置来更新自身位置，使得更新的解向着全局最优解的方向靠近；步骤3.5：更新粒子位置和速度当自身最优解和全局最优解都找到后，每个粒子更具公式(6)和公式(7)来更新自己的速度和位置；v_id(t+1)＝ωv_id(t)+η₁rand()(p_id‑l_id(t))+η₂rand()(p_gd‑l_id(t))        (6)l_id(t+1)＝l_id(t)+v_id(t+1)                (7)式中v_id(t+1)表示第i个粒子在t+1次迭代中的速度，ω为惯性权重，η₁、η₂为加速常数，rand()为0～1之间的随机数；另外，为使粒子速度不至过大，我们设置了速度上限v_max，即当v_id(t+1)＞v_max时，v_id(t+1)＝v_max；v_id(t+1)＜‑v_max时，v_id(t+1)＝‑v_max；步骤3.6：基于前面提出的个体构造方法及评估值计算策略，使用粒子群算法来求解的步骤如下：(1)设置相关参数初始化粒子群规模、最大迭代次数、惯性权重、加速常数；(2)初始化粒子群随机生成包含若干粒子的粒子群M₁，进化代数i＝1；(3)计算粒子群适应度值按照步骤3.3计算初始粒子群适应度值；粒子适应值越大，说明该粒子越接近最优解；(4)更新自身最优算子和全局最优算子(5)更新粒子位置和速度(6)计算新位置的粒子群适应度值(7)更新新位置的粒子群自身最优算子和全局最优算子(8)判断是否满足算法终止条件算法的终止条件是粒子群进化代数超过设定的最大迭代次数，转步骤(8)；否则，转步骤(5)；(9)停止进化，输出结果。