一种基于人工鱼群算法的车联网路侧单元优化部署方法

摘要

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

主权项

一种基于人工鱼群算法的车联网路侧单元部署方法，其特征在于如下步骤：步骤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：构造个体每条人工鱼可作为一个可行解组成鱼群；可行解F表示如下：假设路网中需要部署n个路侧单元，每个路侧单元在路网中的位置信息为f(x,y)，则n个路侧单元构成一个位置序列F(f₁(x,y),f₂(x,y),...,f_n(x,y))；位置序列F(f₁(x,y),f₂(x,y),...,f_n(x,y))和可行解F是一一对应的关系；每个可行解由两部分组成，即鱼的位置和适应度值；则第i条人工鱼个体结构表示为：人工鱼的位置编码结构表示为：Fish(i).Location[]＝F(f₁(x,y),f₂(x,y),...,f_n(x,y))             (3)步骤3.2：鱼群初始化随机生成m个位置序列F(f₁(x,y),f₂(x,y),...,f_n(x,y))，并初始化对应的适应度值，组成m个人工鱼，分别记为F₁,F₂,...,F_m；每个F是一个个体，m个个体组成一个初始鱼群；步骤3.3：计算适应度值因为路侧单元的部署效益越大部署效果越好，所以可以用式(1)路网部署总效益B_n作为适应度值；因此，人工鱼的适应度值可以记为：Fish(i).fitness＝B_n             (4)步骤3.4：位置更改尝试聚群算子：在当前鱼(X_i,Y_i)可见范围内进行搜索，得到鱼的聚群中心X_center和聚群中心的适应度值Y_center；如果满足Y_center＞Y_i且Y_center/n_f＜δ*Y_i(δ＜1)，其中n_f为感知范围内的人工鱼个数，表明伙伴中心有很多食物且不拥挤，则按照(5)式向着该中心位置方向前进一步；$X_{\mathrm{next}}=X_i+\mathrm{rand}\left(\right)*\mathrm{step}*\frac{X_{\mathrm{center}}-X_i}{\left|\right|X_{\mathrm{center}}-X_i\left|\right|}---\left(5\right)$尝试追尾算子：在当前鱼(X_i,Y_i)可见范围内对每条鱼进行搜索，并找到适应度值最高的鱼(X_max,Y_max)；如果Y_max＞Y_i，以X_max为中心搜索其感知范围内的人工鱼，数目为n_f，并且满足Y_max＞Y_i且Y_max/n_f＜δ*Y_i(δ＜1)，则表明该位置较优且其周围不太拥挤，按照(6)式向着适应度值最大的伙伴X_max的方向前进一步；$X_{\mathrm{next}}=X_i+\mathrm{rand}\left(\right)*\mathrm{step}*\frac{X_{\max }-X_i}{\left|\right|X_{\max }-X_i\left|\right|}---\left(6\right)$比较两种行为结果，选择适应度值最高的结果作为真实移动的结果；如果聚群算子和追尾算子都未能成功，则执行觅食算子：在可见范围内随意找一个位置，公式为X_j＝X_i+rand()*visual，并计算其适应度值；如果该处适应度值大于当前鱼的适应度值，则向该处移动；如果在达到最大尝试次数前未能成功执行觅食算子，则执行随机算子；步骤3.5：算法步骤基于前面提出的构造个体方法及评估·值计算策略，使用人工鱼群算法来求解的步骤如下：(1)设置相关参数初始化人工鱼个数、移动步长、可见范围、拥挤度因子、觅食算子尝试次数及最大迭代次数；(2)鱼群初始化随机生成包含若干个体的初始鱼群M₁，迭代次数i＝1；(3)个体适应度值计算按照步骤3.3计算初始鱼群适应度值；个体适应度值越大，说明该个体越接近最优解；(4)循环每条人工鱼，进行位置更改；对当前鱼分别尝试执行聚群算子和追尾算子，比较两种行为结果，选择适应度值最高的结果作为真实移动的结果；否则，执行觅食算子；(5)计算新位置的适应度值并更新最优解；对第i代鱼群M_i，按照步骤3.3计算每个人工鱼的适应度值；(6)更新迭代次数(7)判断是否满足算法终止条件算法的终止条件是，鱼群进化代数超过设定的最大迭代次数，转步骤(8)；否则，转步骤(4)；(8)输出最优解。