基于图着色和三维匹配的车联网资源分配算法_许耀华.pdf

第 卷第期 年月系统工程与电子技术 文章编号：（）网址：收稿日期：；修回日期：；网络优先出版日期：。网络优先出版地址：基金项目：安徽省高校协同创新项目（）资助课题通讯作者引用格式：许耀华，王慧平，王贵竹，等基于图着色和三维匹配的车联网资源分配算法系统工程与电子技术，（）：，（）：基于图着色和三维匹配的车联网资源分配算法许耀华，王慧平，王贵竹，朱成龙，丁梦琴，蒋芳，王翊（安徽大学集成电路学院，安徽 合肥 ）摘要：车联网通信通过多个车辆对车辆（，）链路复用同一车辆对基础设施（，）链路的资源来缓解频谱短缺问题，但频谱复用会导致 通信服务质量下降，因此降低系统干扰、提高系统容量成为研究热点。提出一种基于图着色和三维匹配的车联网资源分配算法，首先用图着色法对 链路分簇，然后求解 链路和 链路的发射功率，最后通过三维匹配算法对 链路、簇和资源块进行信道资源的优化分配，从而降低使用同一资源的链路之间的干扰。理论分析及仿真结果表明，所提方法提高了 链路总和速率，并在相对较少的迭代次数下收敛到次优解。关键词：资源分配；频谱复用；图着色；三维匹配中图分类号：文献标志码：，（，）：（）（），：；引言近年来，互联网和蜂窝通信技术在智能交通系统中的应用越来越广泛，多数车辆都配备了传感器，可以根据服务类型的不同将数据传输到其他车辆或基础设施。在车辆密集地区，为了能在短时间内建立稳定可靠的连接，车辆对频谱资源的需求越来越大，但频谱资源是有限的，故需要对车联网中的频谱资源进行合理分配。在频谱资源分配的底层模式下，车辆对一切（，）用户可以通过资源分配复用蜂窝用户（，）的频谱。但由于同时接入，用户不可避免地会对 造成同频干扰，故需要对频谱资源进行合理管理，使 用户在保 系统工程与电子技术第 卷证 服务质量的前提下接入授权频谱。因此，如何利用资源分配来降低干扰是车联网中一个亟需解决的问题。在现有的车联网资源分配研究中，文献 的解决方案是对基站进行无线资源管理，无线资源管理在基站的介质访问控制层执行，并在时域中为 和 用户分配频谱资源，以此来最小化 和 用户之间发生冲突的概率，并提高频谱效率和网络吞吐量；文献 提出一种基于地理的频谱资源调度方案，车辆根据其位置和在道路上的排序来自主选择频谱资源，其目标是通过协调车辆之间的子信道选择来降低数据包的冲突，所提方案显著改善了由于数据包冲突而导致的数据丢失问题；文献 研究了 和 用户在未授权频谱上的共存问题；文献 考虑了 和 用户的一对一复用，在此复用模式下，用户对 造成的干扰较低，但是频谱利用率不高；在文献 中，单个 的频谱资源可以同时被多个 用户复用，此时的频谱利用率较高，但仅仅考虑了 和 用户之间的信道匹配，并未考虑到 、用户以及资源块（，）这三者之间的信道分配；文献 考虑到了车辆对基础设施（，）链路、车辆对车辆（，）链路以及 这三者之间的信道分配，该文献将互干扰严重的 链路划分成簇并通过三维匹配算法进行了无线资源匹配，从而获得了网络吞吐量最大的资源分配方案。但该方案在 簇划分过程中，对簇内首条 链路的选择是随机的，这导致 簇划分不稳定，严重影响分配方案的最终结果。将图着色法用于分簇问题在文献 中已经被证明是可用的，使用图着色法进行 链路分簇可以解决上述问题。本文在文献 的研究基础上提出一种基于图着色和三维匹配的车联网资源分配算法，建立以最大化 链路总和速率、保障 服务质量要求为目标的分配优化问题。所提算法利用图着色法对 链路进行分簇，并使用三维匹配算法进行信道分配，在保证 链路服务质量和 链路接入率相对平衡的前提下提升了 链路总和速率，并使系统在迭代次数相对较少的情况下收敛到最优。系统模型考虑一个支持设备到设备（，）的车联网通信场景，其中存在辆进行 通信的车辆和对以 通信形式进行本地数据交换的 通信链路，如图所示。为了简化系统，假设所有的车辆在同一时间只能进行 通信或 通信。将 链路集表示为，链路集表示为，其中。假设频谱资源被分成个，表示为，且。为了提高频谱利用率，分配给 链路的上行资源被 链路正交复用，且多个 链路可以同时复用同一 链路的频谱资源。为了控制干扰，每个 链路只能正交占用一个 。图系统模型 车辆的快速移动使得系统模型中的小尺度衰落参数发生变化，如果将小尺度衰落参数传送给基站，会造成信息开销增大和时延增加，故在高速移动场景中捕捉瞬时的信道状态信息是不切实际的。本文假定基站能够获得变化缓慢的大尺度衰落参数和小尺度衰落参数的统计特性。假设第辆 通信车辆通过第个 和基站进行通信的信道增益，为，（）式中：，是具有单位均值指数分布的小尺度衰落参数；是信道损耗常量；，是第辆 通信车辆与基站之间的距离；是衰落系数；，是标准差为且服从对数标准的阴影衰落随机变量。信道损耗常量、阴影衰落随机变量以及距离和衰落系数都是大尺度衰落参数，可以等效记作，。类似地，可以定义信道增益如表所示。表信道增益符号表 符号含义，第辆 通信车辆通过第个 和基站进行通信的信道增益，第条 链路发射端通过第个 与基站进行通信的信道增益，第辆 通信车辆通过第个 与第条 链路接收端进行通信的信道增益第条 链路通过第个 进行通信的信道增益，第 条 链路发射端通过第个 与第条 链路接收端之间的信道增益因此，通过第个 进行通信的第条 链路在基站处的信干噪比和通过第个 进行通信的第条 链路在其接收端的信干噪比如下式所示：，（）第期许耀华等：基于图着色和三维匹配的车联网资源分配算法 ，（）式中：是噪声功率；、分别表示第个 上 链路和 链路的发射功率。定义，为二值变量，分别表示第个 是否分配给第条 链路和第条 链路，则有：，第个 分配给第条 链路，其他（），第个 分配给第条 链路，其他（）问题建模给定一组可用 ，以 链路的总和速率最大化为目标，同时保证 链路的最低通信服务质量和 链路的可靠性，将车辆通信问题建模为一个优化问题：，（）（），（），（），（），（），（），（），（），（）约束式（）中的是 链路的信干噪比阈值，其保证了 链路的可靠性；式（）表示单个 只能被 链路正交复用；式（）、式（）分别表示单个 链路和 链路能且只能复用一个；式（）式（）是功率控制约束式；式（）表示频谱复用规则。观察式（）及其约束式可以发现，目标函数既包含整数约束，也包含非线性约束，使用二分法进行求解。首先，将优化问题分解为传输功率优化和信道分配两个子问题，然后对两个子问题进行逐步求解。其中传输功率优化包含 分簇及功率控制。基于图着色和三维匹配的资源分配算法基于图着色和三维匹配的资源分配算法由个步骤实现。第步，链路分簇；第步，功率控制；第步，三维匹配算法。具体流程如图所示。通过构建干扰图来表示通信链路之间的干扰。首先，通过干扰图得到链路之间的干扰情况，利用图着色法对 链路进行分簇，得到 链路簇集；其次，对 链路和 链路进行功率控制，得到相对较佳的发射功率；最后，利用三维匹配算法解决 链路、链路簇集、三者之间的信道分配问题。图算法流程图 链路分簇本文算法通过 链路之间的干扰构建干扰图（，），顶点集包括每个 链路（每个 链路代表一个顶点，顶点位置位于 链路连接发射端和接收端的中点），。（）表示使用相同频谱资源时图中顶点之间的干扰边矩阵，表示为的矩阵，（），；，其中，表示第条 链路和第条 链路之间存在不可忽略的干扰且两顶点之间存在相连的边。在这种情况下，是的邻居，并将、分别加入和的邻居集 、中。由于强干扰，同一 不能分配给两个相邻的通信链路。这类似于顶点着色问题，其中由同一条边连接的两顶点不能着相同颜色。因此，当一组顶点被涂上相同颜色时，表示允许使用相同的。干扰图的建立步骤初始化干扰图，随机放置条 链路；步骤当 发射端车辆受到 接收端车辆的强干扰并且不能正常通信时，建立干扰边，。当两 链路之间的信干噪比小于 链路正常通信的阈值时，在两顶点之间建立干扰边，并将链路间干扰设置为该边权重。设，为顶点的饱和度，饱和度越小，表示可染色的颜色越多，反之越少。.对的分簇按照上述方法，可以将 链路间的干扰关系映射为干扰图，基于此，可以将 链路分为若干个不相交的簇。本文采用图着色法对 链路进行分簇。具体算法如算法所示。算法基于图着色的分簇算法：初始化：根据第 节构建干扰图，并计算每个顶点的饱和度；：顶点着色 存在未被染色的顶点 ：顶点的饱和 度，的值最大 系统工程与电子技术第 卷 由以上两步得到 链路分簇结果，将划分到同一簇的 链路看作一个整体，不同簇间复用不同的频谱资源，故不在同一簇的 链路之间将不会产生干扰。功率控制为了实现更高的 链路总和速率以及保证 链路的服务质量，需要合理控制 链路及 链路的发射功率。假设分配给第条 链路的频谱资源被第个 链路簇集复用，故目标函数式（）变为由式（）组成的方程组：，（），（）（），（）式（）化简得到 ，（），（）假设所有 链路都满足信道要求，将式（）取等号得到 ，（），（）取 并结合式（）对 链路的最大发射功率要求，得到 链路发射功率最优解为 ，（），（）将集合中的 链路数量记作。注意到问题中有个变量，包括个 链路发射功率和个 链路发射功率，且问题中的约束式有个。假设同一簇中的 链路发射功率相同，即，结合式（）可推导出 链路簇集中 链路的发射功率最优解为 （），（）式中：是一个的实数矩阵，存储个 链路发射功率，（，）是一个的矩阵，表示使用相同 进行通信的第条 链路与 链路簇集中的条 链路之间的信道增益。信道分配经过以上两步分析，问题就转化为了一个三维匹配问题，见图。图中总共有种 链路簇集的复用模式，通过构建均匀超图 来实现信道分配。与一般图不同的是，均匀超图中任一条边连接的顶点数都为。超图（，）有两个属性，分别是顶点集和边集，其中边的权重为（，），（，），其中，是第个 链路簇集复用通过第个 进行通信的第条 链路的速率，目标是寻找一种分配使得式（）的 链路总和速率最大化。图三维匹配图 在上述 链路簇集的加权三维匹配算法求解过程中，构建三维均匀超图的时间复杂度为（），加权三维匹配算法的时间复杂度为（）。此外，基于着色的 链路分簇的时间复杂度为（）。因此，本文所提 算 法 的 总 的 时 间 复 杂 度 为（），其中为迭代次数。此外，基于迭代的频谱分配算法的时间复杂度为（），文献 所提算法的时间复杂度为（）。仿真结果及分析 实验条件和仿真设置本文利用 仿真平台对上述提出的基于图着色和三维匹配的资源分配算法进行仿真。仿真环境根据第三代 合 作 伙 伴 计 划（，）组织的 设置。具体参数见表。仿真针对图所示的公路场景，假设车辆的到达服从泊松分布，车辆之间的平均距离为 倍车速。信道模型为基于 信道模型建立的 和 信道模型，基站位于蜂窝区域的中心，来进行消息的接收和发送。第期许耀华等：基于图着色和三维匹配的车联网资源分配算法 表仿真参数 参数取值载波频率 带宽 蜂窝半径 基站公路距离 车道宽度 基站天线增益 汽车天线增益 基站接收噪声指数 汽车接收噪声指数 链路数量 链路数量 链路信干噪比阈值 链路最大传输功率 链路最大传输功率 噪声功率 仿真结果及分析基于表的参数设置进行仿真，本文将基于图着色和三维匹配的资源分配算法与基于迭代的频谱分配算法、文献 中基于三维匹配的随机频谱分配算法进行对比，关注 链路总和速率、链路接入率等性能指标，对比不同发射功率、车辆速度、链路数量和迭代次数下的 链路总和速率。图展示了活跃 链路数量对 链路总和速率的影响。从图中可以看到，随着 链路数量的增加，种算法的 链路总和速率都会降低。这是因为，随着 链路的增加，复用相同链路资源的 链路数量增加，这将对 链路产生更多干扰，进一步降低了 链路的接收信干噪比。此外，从容量曲线的陡峭斜率可以看出，对比算法对 链路的增加非常敏感，而基于图着色和三维匹配的资源分配算法的容量曲线斜率相对平缓。分析原因可知，在这些情况下，链路对 链路产生的干扰非常严重，并且 链路总和速率受到很大影响，从而性能降低。而在 链路数量较多时，本文所提算法通过牺牲 链路的接入率换取信干噪比允许范围内 链路的可靠性，对 链路总和速率的