一个基于遗传算法的车联网路边单元部署方法

一个基于遗传算法的车联网路边单元部署方法
【技术领域】
[0001] 本发明属于移动通讯技术领域，设计了一种基于遗传算法的车联网路边单元部署 方法。该方法区别于已有方法的特色在于，利用路边单元部署问题模型将路边单元部署问 题转化为搜索最优解问题，并利用遗传算法对路边单元部署问题进行优化求解。该方法能 够逐步逼近最优部署效益，以达到最大化路边单元部署效益的目标。
【背景技术】
[0002] 车辆自组织网络是传统移动自组织网络在交通道路上的应用，是一种特殊的移动 自组织网络。通过车辆与车辆（V2V)、车辆与路旁基础设施（V2I)等方法直接通信或多跳通 信，构建一个自组织的、动态的、分布式信息网络。车辆自组织网络中每一个节点代表一个 安装了无线通信技术的车辆，通过为行驶中的车辆提供信息服务，来提高交通效率、驾驶安 全性，减少交通事故发生率，最大化道路使用者的利益。
[0003] 车辆自组织网络主要由车载单元、路边单元和管理控制中心组成。当车辆进入到 路边节点的通信范围之内，它就能通过路边节点访问有线网络。另一方面，车辆也能经由其 它车辆经过多跳中继与路边单元通信。网络中的车辆节点与路边单元的连接状况决定了网 络的有效数据包传递率和连通持续时间。因此，路边单元的部署策略就成了增加网络容量 的关键因素。但是，在车辆自组织网络初期，路边单元部署花费高昂，因此需要在给定区域 最佳放置有限数量的路边单元以达到最优部署效益的目标。

【发明内容】

[0004] 本发明提出了一种基于遗传算法的车联网路边单元部署方法，目的在于最大化路 边单元部署效益。
[0005] 本发明所采用的技术方案是按照以下步骤进行：
[0006] 步骤1.建立路网模型
[0007] 假定路网用路网模型G(v，E)表示，交叉路口集V代表所有交叉路口的集合，路段 集E代表所有路段的集合。同时路网模型G(V，E)将某个路段e表示为6(\，\，4匕)，其 中vh为路段e的起点，vt为路段e的终点，ft为路段e的路线函数，fw为路段e的权重函 数。若路网中需要部署n个路边单元，每个路边单元的覆盖直径为d，综合考虑各项因素作 为权重，则每个路边单元的部署效益为路边单元所有覆盖路段的权重线积分。假设P为能 够满足目标的集合，现在要解决的问题可描述为：找到P的子集1^使其尽可能满足部署效 益最大化的目标。
[0008] 步骤2.建立效益模型
[0009] 假设路网G(V，E)中部署的第j个路边单元的全覆盖路段的集合为+，部分覆盖路 段的集合为Sj，j= 1，2,…，n，n个路边单元的全覆盖路段的集合t/ = ，部分覆盖路 段的集合^ = ，则部署的第j个路边单元的部署效益N表示如下：
[0010]⑴
[0011] 其中j= 1，2,…，n，me，j=enoj,符号Oj为部署的第j个路边单元的覆盖区域， 即my为路段e在路网中部署的第j个路边单元的覆盖区域内的部分。
[0012] 路网部署总效益匕表示如下：
[0013]
⑵
[0014] 其中札=en0,符号0为路网中所有路边单元的覆盖区域，即为路段e在路 网中所有路边单元的覆盖区域内的部分。
[0015] 由部署效益函数知，我们的目标是使得部署效益值尽可能地大，来达到路边单元 部署效益最优的目标。因此将路网模型和效益模型共同构成路边单元部署问题模型，通过 路边单元部署问题模型将路边单元部署问题转化为搜索最优解问题。
[0016] 步骤3.利用遗传算法对路边单元部署问题进行优化求解
[0017] 遗传算法是一种新近发展起来的搜索最优解方法，它模拟生命进化机制，从任意 一个初始种群出发，通过随机选择、交叉和变异操作，产生一群新的更适应环境的个体使群 体进化到搜索空间中越来越好的区域。这样一代代不断繁殖、进化，最后收敛到一群最适应 环境的个体上，求得问题的最优解。因此我们设计了一种遗传算法，来对所建立的搜索最优 解问题进行求解。下面基于步骤1和步骤2建立的路边单元部署问题模型介绍算法步骤。
[0018] 算法步骤：
[0019] 步骤1设置相关参数及个体编码
[0020] 步骤2种群初始化 [0021 ] 步骤3个体适应值计算
[0022] 步骤4对群体进行交叉、变异操作，生成中间群体
[0023] 步骤5计算中间群体个体适应值
[0024] 步骤6利用锦标赛选择法选择子代群体
[0025] 步骤7计算群体当前一代最坏个体和最好个体，以及到目前为止的最好个体
[0026] 步骤8将当前一代最坏个体用目前为止最好个体替代
[0027] 步骤9判断是否满足算法终止条件
[0028] 步骤10停止进化，输出结果
[0029] 本发明给出一种基于遗传算法的车联网路边单元部署方法。首先建立路网模型， 然后确立效益模型，路网模型和效益模型共同构成路边单元部署问题模型，将路边单元部 署问题转化为搜索最优解问题。最后利用遗传算法对路边单元部署问题进行优化求解，从 而达到最大化部署效益的目的。
【附图说明】
[0030] 图1是本发明方法的流程示意图。
[0031] 图2是本发明方法的一种实施例的程序流程图。
[0032] 图3是本发明方法的结果示意图。
[0033] 具体实施方法
[0034] 下面结合附图对本发明的实施方式进行详细说明。本实施例以本发明技术方案为 前提进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下 述的实施例。
[0035] 下面给出基于遗传算法的车联网路边单元部署方法，如图1所示，按如下步骤进 行路边单元部署：
[0036] 步骤1.建立路网模型
[0037] 假定路网用路网模型G(V，E)表示，交叉路口集V代表所有交叉路口的集合，路段 集E代表所有路段的集合。同时路网模型G(V，E)将某个路段e表示为6(\，\，4匕)，其 中vh为路段e的起点，vt为路段e的终点，ft为路段e的路线函数，fw为路段e的权重函 数。若路网中需要部署n个路边单元，每个路边单元的覆盖直径为d，综合考虑各项因素作 为权重，则每个路边单元的部署效益为路边单元所有覆盖路段的权重线积分。假设P为能 够满足目标的集合，现在要解决的问题可描述为：找到P的子集1^使其尽可能满足部署效 益最大化的目标。
[0038] 步骤2.建立效益模型。
[0039] 假设路网G(V，E)中部署的第j个路边单元的全覆盖路段的集合为+，部分覆盖路 段的集合为Sj，j= 1，2,…，n，n个路边单元的全覆盖路段的集合U= ，部分覆盖路 段的集合*5 = ，则部署的第j个路边单元的部署效益h表示如下：
[0040]
⑴
[0041]其中j= 1，2,…，en〇』，符号〇』为部署的第j个路边单元的覆盖区域， 即my为路段e在路网中部署的第j个路边单元的覆盖区域内的部分。
[0042] 路网部署总效益反表示如下：
[0043]
⑵
[0044] 其中札=en0,符号0为路网中所有路边单元的覆盖区域，即为路段e在路 网中所有路边单元的覆盖区域内的部分。
[0045] 由部署效益函数知，我们的目标是使得部署效益值尽可能地大，来达到路边单元 部署效益最优的目标。因此将路网模型和效益模型共同构成路边单元部署问题模型，通过 路边单元部署问题模型将路边单元部署问题转化为搜索最优解问题。
[0046] 步骤3.利用遗传算法对路边单元部署问题进行优化求解
[0047] 下面具体介绍个体的编码方法、个体优劣的评价方法以及进化策略等。
[0048] 3. 1 :个体编码方法
[0049] 设P是待求问题的候选解，下面给出P的编码方法。
[0050] 假设路网中需要部署k个路边单元，每个路边单元在路网中的位置信息为 P(X，y)，分别将x和y转换为对应的二进制数据（aa2, ? ??，an)和（0 0 2, ? ? ?，0 n)， 可得到一个长为2n的（0-1)串（aa2，…，an,0 02,…，0n)，则k个路边单元构成 一个长度为k*2n的（0-1)串yy2,? ? ?，yk*2n。可以看出，（0-1)串yy2,? ? ?，y找加和 子集P是--对应的关系。因此，我们可以使用长度为k*2n的（0-1)串ypy2,. ..，ykH<2n 来表示个体P。这样表示，为遗传操作的顺利实施奠定了基础。
[0051] 3. 2:种群初始化
[0052] 随机生成m个长为k*2n的（0-1)字符串，分别记为？1汁2，...，？111。每个字符串是 一个个体，m个个体组成一个初始种群。
[0053] 3. 3:设定适应度函数
[0054] 因为路边单元的部署效益越大部署效果越好，所以可以用路网部署总效益匕作为 适应度值。
[0055] 3. 4 :进化策略
[0056]由于每个个体都是一个（0, 1)字符串，可以采用传统的进化算子对个体实施遗传 操作。本文算法中，个体交叉算子为一点交叉，变异算子为一点变异，选择算子采用锦标赛 选择法。
[0057] 3. 5:算法步骤
[0058] 下面结合图2对本实施例的路边单元部署方法进行详细的说明，具体包括以下步 骤：
[0059] S301、设置相关参数
[0060] 初始化种群规模、最大迭代次数、交叉概率和变异概率等参数。
[0061] S302、种群初始化
[0062] 随机生成包含若干个体的初始种群A，进化代数i= 1。
[0063]S303、个体适应值计算
[0064] 按照步骤3. 3计算初始种群适应度值。个体适应值越大，说明该个体越接近最优 解，被遗传到下一代的概率也就越大。
[0065]S304、对群体进行遗传操作
[0066] 对个体实施交叉和变异操作，生成中间群体；i=i+1。
[0067] S305、计算中间群体适应值
[0068] 对第i代种群％，按照步骤3. 3和3. 4计算每个个体的适应值。
[0069]S306、利用锦标赛选择法选择子代群体
[0070] 基于锦标赛的选择操作的具体过程如下。
[0071 ] ①将m个父代个体组成的种群P和P经过一次交叉和变异运算后产生的m个子代 个体组成的种群P'合并在一起，组成一个共含有2m个个体的集合，记为I。
[0072] ②对给个个体XiGI，从I中随机选择q个个体，并将q个个体的适应度函数值 Fj(jG1，2, . . .，q)与适应度函数值相比较，计算出这q个个体中适应度函数值比xi 的适应度差的个体的数目Wi，并把Wi作为x得分。
[0073] ③在所有的2m个个体都经过比较过程后，按每个个体的得分进行排序，选择m个 具有最高得分的个体作为下一代种群。
[0074] S307、计算群体当前一代最坏个体和最好个体，以及到目前为止的最好个体
[0075]S308、将当前一代最坏个体用目前为止最好个体替代
[0076] S309、判断是否满足算法终止条件
[0077] 算法的终止条件是，连续进化若干代后没有出现更优个体，或者种群进化代数超 过设定的最大迭代次数，输出结果，算法结束；否则，转步骤S304。
[0078]实施例的结果示意图如图3所示。从图3中可以看出，随着迭代次数的增加，路边 单元部署效益的值不断得到优化。通过本发明方法可以得到路边单元部署效益的近似最优 值。
【主权项】
1. 一种基于遗传算法的车联网路边单元部署方法，其特征在于如下步骤： 步骤1 :建立路网模型 将某个路段e表示为e (vh，vt，ft，fw)，其中Vh为路段e的起点，V t为路段e的终点，f t 为路段e的路线函数，fw为路段e的权重函数； 步骤2 :建立效益模型 将路网部署总效益匕表示如下：其中符号U为η个路边单元的全覆盖路段的集合，符号S为其部分覆盖路段的集合，符 号札为路段e在路网中所有路边单元的覆盖区域内的部分； 步骤3 :利用遗传算法对路边单元部署问题进行优化求解 步骤3-1 :个体编码方法 设P是待求问题的候选解；假设路网中需要部署k个路边单元，每个路边单元在路 网中的位置信息为P(x，y)，分别将X和y转换为对应的二进制数据U1, α2，...，αη) 和（β!，β2，···，βη)，得到一个长为2η 的（0-1)串（Ci1, α2，···，αη, β1; β2，···，βη)， 则k个路边单元构成一个长度为k*2n的（0-1)串γ ^ γ 2,...，γ kH<2n; (0-1)串 Y i，Y 2,. . .，Y ^和子集P是--对应的关系；使用长度为k*2n的（0-1)串 Y 1，Y 2, · · ·，丫 k?H2n来表示个体 P ; 步骤3-2 :种群初始化 随机生成m个长为k*2n的（0-1)字符串，分别记为PpP2,...，Pm;每个字符串是一个个 体，m个个体组成一个初始种群； 步骤3-3 :设定适应度函数 路边单元的部署效益越大部署效果越好，用路网部署总效益匕作为适应度值； 步骤3_4 :进化策略 由于每个个体都是一个（〇，1)字符串，采用进化算子对个体实施遗传操作；个体交叉 算子为一点交叉，变异算子为一点变异，选择算子采用锦标赛选择法； 步骤3-5 :基于前面提出的个体编码及评估值计算策略，使用遗传算法来求解的步骤 如下： (1) 设置相关参数及个体编码 初始化种群规模、最大迭代次数、交叉概率和变异概率等参数，按照步骤3-1给出的方 法对个体进行编码； (2) 种群初始化 随机生成包含若干个体的初始种群M1，进化代数i = 1 ; (3) 个体适应度值计算 按照步骤3-3计算初始种群适应度值；个体适应值越大，说明该个体越接近最优解，被 遗传到下一代的概率也就越大； (4) 对群体进行遗传操作 对个体实施交叉和变异操作，生成中间群体；i = i+Ι ; (5) 计算子代个体适应值 对第i代种群Mi,按照步骤3-3计算每个个体的适应值； (6) 利用锦标赛选择法选择子代群体 (7) 计算群体当前一代最坏个体和最好个体，以及到目前为止的最好个体 (8) 将当前一代最坏个体用目前为止最好个体替代 (9) 判断是否满足算法终止条件 算法的终止条件是，连续进化若干代后没有出现更优个体，或者种群进化代数超过设 定的最大迭代次数，转步骤（10);否则，转步骤（4); (10) 停止进化，输出结果。
【专利摘要】本发明公开了一种基于遗传算法的车联网路边单元部署方法，目的在于最大化路边单元的部署效益。首先建立路网模型，该路网模型能够描述曲线路段。然后综合考虑各项因素作为权重确立部署效益函数，建立效益模型。路网模型和效益模型共同组成路边单元部署问题模型，将路边单元部署问题转化为搜索最优解问题。最后利用遗传算法对搜索最优解问题进行优化求解。该方法能够找到多个路边单元部署问题的近似最优位置，使其逼近最优部署效益的目标。
【IPC分类】H04L29/08, H04L12/24
【公开号】CN104883388
【申请号】CN201510182396
【发明人】高振国, 朱涵, 陈炳才, 姚念民, 卢志茂, 谭国真, 曲殿阁, 余超
【申请人】大连理工大学
【公开日】2015年9月2日
【申请日】2015年4月17日