英语原文共 9 页
多通道认知车载网络中有效的信道分配
摘要:最近的研究表明，分配给车载网的专用短程通信(DSRC)频段不足以承载车辆系统新兴应用所产生的无线通信负载。通过FCC释放用于认知访问的大频带频谱，一种很有前景的带宽扩展的可能性出现了。车载网络中所谓的电视白空间(TVWS)接入的主要挑战之一是针对车辆的高移动性和TVWS的时空变化设计高效的信道分配机制。本文以全系统吞吐量最大化为目标，研究了多通道认知车载网络的信道分配问题。证明了该问题是一个NP-hard组合优化问题，给出了两种求解方法。首先提出了一种基于线性规划的概率多项式时间(1-1/e)近似算法。接下来，我们证明了我们的目标函数可以写成一个子模集函数，在此基础上，我们开发了一个具有更优时间复杂度的确定性多项式时间常数因子近似算法。最后，通过算例验证了算法的有效性。
Ⅰ.引言
最近的研究表明，分配给车载网络的DSRC频段不太能满足车载网络[1][2]中新兴无线应用的带宽需求。如何设计有效的信道分配机制，以应对高车辆移动性和TVWS的时空变化，是TVWS在车辆网络中应用面临的挑战之一。然而，基于CSMA/CA原理设计的车载网络IEEE 802.11p，由于缺乏认知无线电能力，不适用于认知无线电网络(CRNs)。
CRNs中的信道分配问题在文献中得到了广泛的研究。大量的工作采用离散时间马尔可夫链和信道分配对主用户(PU)活动进行建模。在[3]中，二级用户(SU)的频谱感知和访问过程被建模为部分可观测的马尔可夫决策过程(POMDP)。在此模型的基础上，提出了优化策略和次优化策略，以确定感知和访问哪个信道，从而最大限度地提高系统吞吐量。
类似地，主通道的可用性在[4]中被建模为一个交替更新过程。然而，这些模型只适用于静态crn。由于TVWS具有较高的车辆移动性和时空变异性，需要同时利用统计和瞬时信道可用性信息的新型低时间复杂度信道分配机制。
为了使单跳crn的长期系统吞吐量达到最大，研究了[5]中联合速率控制和信道分配问题。该工作已扩展到解决多跳crn的相同问题，以最大限度地提高SU的吞吐量，同时稳定[6]中的crn。然而，这些方法侧重于最大化系统的长期吞吐量，不能满足车辆的短期吞吐量最大化需求。此外，它们假定每个SU与一个统一的固定优先级相关联，而车辆的优先级则随其包的优先级而变化。在车辆网络中，由于相关应用的实时性要求，短期吞吐量最大化需求显得尤为重要。因此，长期效用最大化算法不适用于车辆网络。
本文提出了一种多通道认知车辆网络的有效信道分配框架。相对于已有的工作，我们研究了以车辆短期效用最大化为目标的信道分配问题。我们也考虑了高的车辆流动性、TVWS的时空变化以及由PU施加的碰撞概率约束。更具体地说，我们考虑一个TDMA模型，在每个调度周期的开始，将可用的信道分配给车辆，以应对快速变化的车辆位置。根据车辆的分组优先级和分组大小、每个TVWS信道的预计剩余空闲时间以及每个信道的碰撞概率约束进行分配。
我们工作的理论贡献是三倍的。首先，通过对TVWS中车辆网络信道分配的短期效用最大化问题的研究，证明了该问题是NP-hard问题，并将其归结为广义分配问题。第二，我们建议一种基于线性规划的概率多项式时间(1 - 1/e)近似算法。第三，证明了目标函数可以写成子模集函数，并在此基础上提出了一种具有较好的时间复杂度的确定性多项式时间常数因子逼近算法。
本文的其余部分组织如下：第二部分描述了系统模型和问题的求解；在第三部分，我们提出了基于线性规划的方法，并分析了其性能和时间复杂度；然后，我们的目标函数被证明是一个子模集函数，并在第四节中给出了一个确定的多项式时间算法；我们在第五节中给出了仿真结果；在第六节中总结了我们的工作。
Ⅱ.系统模型和问题的制定
我们考虑一个由N辆车组成的认知车辆网络。我们假设网络中有M个可用的TVWS频道。在车载网络中，分组按优先级递减分为四个访问类别:AC[0]hellip;AC[3]。因此，在我们的模型中，我们关联每个优先级类AC[i]，权重Ai服从Ai gt;Aj,forall;ilt; j。在我们的模型中,我们假设路边通道监控(rcm)不断感觉和估计使用模式的所有可用TVWS频道。时间被划分为长度为T的等调度周期，在每个调度周期的开始，RCM还负责为车辆分配信道。T的值由特定车辆网络的特性和要求决定。
利用随机变量tj对TVWS占用率进行建模，tj定义为PU返回信道j前的剩余时间。我们假设RCM知道tj的概率密度函数(PDF) fj(tj)和累积分布函数(CDF) fj(tj)。由于对于RCM来说，PU的确切行为是未知的，所以在一个信道上调度的车辆传输可能会与PU传输发生冲突，且概率为非零。然而，在我们的模型中，我们假设cpu可以容忍一定的碰撞概率，即造成的碰撞概率安排车辆通道j不得超过由PU网络确定的系统参数gamma;j。在此冲突概率约束下，RCM可以计算出每个信道上允许的最大调度时间周期，用Tr j表示。则碰撞概率Pcoll计算如下:
通过求解式(1)可以计算出最大调度时间Tr j，因此，信道j上允许的最大调度时间为min{Tr j, T}。
在我们的模型中，我们假设车辆在PU返回之前的传输是成功的，并且所有剩余的数据包都被认为丢失了(一个可能的原因是脓的高传输功率使车辆的发射机无法工作)。车辆将尝试在以下循环中传输丢失的数据包。让Li为当前周期i趋向于传输的数据包数量。注意，Li不一定是车辆i的实
际分组队列长度，例如，Li可以是当前周期中我希望传输的紧急安全相关分组车辆的数量。我们不跟踪每个车辆的包队列长度，而是假设Li值包含在车辆向RCM发出的请求消息中。然后，RCM通过以下公式确定车辆i在j通道上所需的传输时间:
其中Rj为车辆在j通道上的传输速率，设xij为信道分配变量，即如果车辆i调度在通道j上，则xij = 1，否则xij = 0。我们使用Uij来表示期望的加权吞吐量，即当前调度周期中车辆i在j通道上的效用:
注意，当i =1时，令 ，因此
我们的通道分配模型如图1所示。
图1.通道分配模型
我们的目标是通过在可用的TVWS频道上调度不相交的车辆集，最大化所有车辆的总加权吞吐量 。由于一个信道上可以调度多个车辆，根据式(2)，车辆的期望吞吐量受提前调度车辆的影响，因此，车辆在一个信道上的传输顺序将影响这些车辆的总加权吞吐量。引理1指出，优先顺序传输最大化了信道上的总加权吞吐量。
引理1：给定一组要在通道上调度的车辆，优先级较高的车辆必须比优先级较低的车辆调度得更早，以便使总权重最大化，而相同优先级车辆的传输顺序不影响总加权吞吐量。
证明：首先，我们证明了对于同一信道上调度的任意两辆车v1、v2，从两辆车的总加权吞吐量来看，调度优先级更高的车辆比调度其他车辆更有价值。设A1和A2的优先级权重A1 gt; A2，t1、 t2为它们的预定传输时间。假设时间持续时间(0,t0)分配给其他车辆，因此两辆车辆的第一个发射机在t0处开始发射。令U1 - 2为它们的总效用，当将v1排在v2之前时，U2 - 1为逆序的总效用。设u1j1和u2j1为v1排在v2之前时两辆车的预期吞吐量，U1j2和U 2j2为v2排在v1之前时两辆车的预期吞吐量。根据式(2)，分别计算式(3)和式(4)中的U1 - 2和U2 - 1:
然后比较U1 - 2和U2 - 1的值，由U1 - 2减去U2 - 1，得到式(5):
从A1 gt; A2开始，我们现在比较两个积分部分，它们具有相同的积分函数和相同的区间长度t1。因为Fj(tj)是CDF，所以它是不递减的。由于第一个积分区间的起点较大，即t0 t2 gt; t0，有。因此，我们有U1 - 2ge;U2 - 1，这证明了引理1的第一部分。此外，如果两辆车具有相同的优先级，即由式(5)可以直接得出U1 - 2 = U2 - 1，证明引理1的第二部分。
在我们的模型中,车辆被排序并更名为{v1,v2,hellip;vN}，A1ge;A2hellip;ge;AN，Lige;Lj,forall;ile;j当Ai = Aj。这意味着高优先级车辆排在低优先级车辆之前，具有相同优先级的车辆按其Li值的递减顺序排序。
现在我们的渠道分配问题可以表述为:
在这项工作中，我们根据车辆的优先级和Li值来安排车辆，而不是根据车辆队列的长期演化。因此，我们的方法适用于高度移动的车辆网络，在这种网络中，消息生存期很短，如果消息没有在最后期限前传输，则从队列中删除消息。此外，我们的方法只需要每个调度周期中N辆车的Ai和Li值，即使在高移动性的情况下也可以很容易地得到。
定理1：信道分配问题(6)为NP-hard。
证明：将问题(6)简化为广义分配问题(GAP)，证明了该定理。GAP是将不同的项目集分配给受箱容量限制的箱子，以最大化总利润，其中大小sij和利润pij都是常量指标。GAP已被证明是NP-hard[7]。在问题(6)中，我们考虑Pr{tj lt; T} = 0的情况。这是我们的问题的一个简化版本，在调度周期开始后，cpu总是至少返回T时间，即TVWs总是可用的。在这种情况下，问题(6)简化为以下问题:
这个约简问题是一个缺口，其中T是所有箱子的容量，tij是箱子j中第i项的大小，是将第i项分配给箱子j的利润，这个映射证明了问题(6)是NP-hard。
Ⅲ.解决方案1:线性规划算法
问题(6)的一般形式比GAP难很多，因为GAP中的利润值pij是固定的。而(6)中每辆车的效用函数与其他车辆耦合。这里的“耦合”是指预期的车辆的吞吐量受预先安排的车辆的影响。然而，对于分配给通道的一组给定车辆，通道上每辆车辆的效用(即由于吞吐量最大化传输顺序规则(见引理1)，GAP中的“利润”是固定的。
根据这一观察，我们的基于线性规划(LP)的算法工作如下。我们首先为初始信道分配问题构造一个等价整数规划(IP)问题，即，为每个通道j恰好选择一组车辆Sj，使所有通道上的总效用最大化。令Xj(Sj)isin;{0,1}表示表示分配给j信道的车辆集合的决策变量，将约束条件放宽为Xj(Sj)isin;[0,1]，得到LP问题。然而，这个LP问题有指数数量的变量，因为指数数量的车辆可能组分配到一个通道。虽然LP问题不能在多项式时间内求解，但对偶问题的处理可以在不损失性能的前提下减少其变量的数量。对偶问题虽然具有指数约束数，但[8]中证明了利用与分离oracle相关联的椭球体算法可以在多项式时间内求解。当用椭球算法迭代求解对偶问题时，保证在每次迭代中得到原LP问题最多一个可行变量。由于椭球体算法被证明是在多项式迭代中终止的，因此可以得到最多的多项式变量数。这些变量足以解决原始问题，没有性能损失[9]。这样，原始LP问题就变成了一个新的多项式多变量LP问题，可以在强多项式时间[10]下求解。在求解LP问题后，得到一个分数解{Xj(Sj)}。然后，我们提出一种四舍五入算法，将分数解四舍五入为一个近似因子大于或等于(1 - 1/e)的整数解。由于LP问题的最优解是IP问题最优解的上界，因此我们保证至少能得到IP最优解的(1 - 1/e)。LP算法的具体步骤如下。
A.规划LP问题
设Gj (Sj)为将车辆集合Sj分配给信道j的效用，Ij为将车辆集合所有可行分配给信道j的效用。问题(6)可以重新表述为如下的一个LP问题:
其中Gj(Sj)可以计算为:
第一个约束意味着每个车辆最多只能在一个通道上调度，第二个约束意味着只能在一个通道上调度一组车辆。
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
