用模糊匈牙利算法解决广义指派问题文献综述
2020-04-14 17:23:41
近年来,随着车辆网络业务以及相关软件的发展,专用短距离通信(DSRC)频段不足以承载车载网络中增加的无线业务需求。美国联邦通信委员会发布的用于认知访问的大型电视频谱(即电视白色空间频谱)将用于给车载网络提供额外的带宽,面向TVWS的新的信道分配方案已经成了我们要追求的目标。车辆的高速移动、复杂的网络环境等因素导致车载网络中车辆的通信性能较差,尤其随着车辆数目的增加,车辆之间的竞争和干扰越来越严重,为了满足车辆的通信性能需求,需要设计更加有效的通信性能需求,需要设计更加有效的信道分配机制。
认知无线电技术通过感知、分析、决策等方式检测和管理空闲频谱,在不干扰主要用户通信的情况下,认知用户根据一定的规则机会式地利用时间空间上的可用频谱,从而提高频谱利用率。将认知无线电技术引入车载自组网中,车辆可以机会地接入TVWS信道,是解决频谱资源紧张的有效办法。我们需要在此基础上利用有限的频谱资源满足车载网络的通信效率和服务质量要求,而如何为认知车载用户分配可用频谱资源是能否有效提高频谱利用率的关键问题。
本次设计以最大化网络吞吐量为目标对认知车载网络进行建模,提出最大化系统收益的问题。经过化简之后,系统收益最大化问题可以理解为广义指派问题,经过分析后采用模糊匈牙利解决系统问题,实现信道分配。
传统的指派问题(Assignment Problem简称AP)是这样的:有n项工作欲安排n个人去做,每个人安排且仅安排一项工作,已知地i个人做第j项工作的效益为Cij(i,j=1,2,3……n),试确定使效益最大的最优指派。AP要求工作数与人数相等,它可用著名的匈牙利算法来求解,根据企业管理决策的需要,提出来了一个更广义的指派决策问题(Generalized Assignment Problem简称GAP),并分别给出了不同的求解方法。GAP可叙述如下:有n项工作欲安排m(mgt;n)个人去做,每个人安排且仅安排一项工作,而每项工作可由一个或多个人共同去做,已知第i个人做第j项工作的效益为Cij(i=1,2,3…m;j=1,2,3…n),由此可得到分配问题效益矩阵,然后可将问题转化到研究矩阵上来。由匈牙利算法的原理知求指派问题的最优解就是在n阶系数方阵中找到n个这样的元素:它们分布在方阵的不同行不同列上,并且这些元素之和为最小,而要使这些元素之和为最小,就要使其中的每一个元素尽可能地小,最好这些元素都是其所在行和列上的最小元素,而指派问题的最优解又有这样的性质:如果从分配问题效率矩阵[Cij]的一行(列)各元素中分别减去该行(列)的最小元素,得到新的矩阵[Bij]为效率矩阵,得到的最优解和原效率矩阵[Cij]求得的最优解相同,由于新矩阵[Bij]中每行、每列的最小元素均为“0”,因此,求原指派问题的最优解就转化为在新矩阵[Bij]找到n个分布在不同行不同列上的0元素,这些独立0元素就是新矩阵[Bij]的最优解,找到矩阵的最优解也就找到原矩阵的最优解。而在实际问题中m与n常常不相等,而且还要考虑特定条件下的模糊相对隶属度,要通过Cij来求解,之后解得其对应的扩展效益矩阵,即可用匈牙利算法求解最优解。
本次设计的主要目标是设计新的车载网络信道分配方案。车辆作为认知用户需要在不影响主用户使用的情况下机会的使用TVWS空闲频谱,传统的分配方案无法满足这一要求。针对这一情况,我们设计了以模糊匈牙利算法为基础的信道分配策略,以最大化网络吞吐量为目标,实现车辆在TVWS上的信道分配。
随着无线通信技术的迅猛发展,当前可分配的频谱资源变得越来越紧张,特别在无线局域网、个域网等技术的大规模应用下,各种无线业务对频谱资源的分配需求也随之增加,美国联邦通信委员会在十多年前已将5.9 GHz专用短距离通信(DSRC)频段划分给车载通信。然后,IEEE车载环境中的IEEE无线接入标准栈(例如,IEEE 802.11p和IEEE 1609.4)被提出来支持DSRC频带中的车辆通信。 然而,理论分析和仿真结果都表明DSRC频带不足以提供可靠的安全消息传输。此外,它表明DSRC频段的非安全使用必须在高峰时段严格限制,以保证可靠传输安全信息。例如,如果在安全应用中必须保证95%的传输可靠性,那么只有10%的DSRC带宽留给中等流量密度的非安全应用。更重要的是,由于越来越多的车辆以及越来越多的无线车辆应用,比如避撞,安全警告,远程车辆诊断,文件下载,网页浏览和视频流等,频谱稀缺问题变得越来越严重。过去几年的频谱利用率测量表明,在不同时间和空间的未使用和未被充分使用的许可频段数量明显,某些频段异常拥挤,而有些频段大部分处于闲置状态。于是人们提出了认知无线电的概念:CR作为一种具有频谱感知能力的智能化无线电,它能自动感知周围的电磁环境,寻找“频谱空穴”,并通过通信协议和算法将通信双方的信号参数调整到最佳状态。根据美国联邦通信委员会(FCC)的资料,使用指配频谱的时间和地理变化范围为15#12316;85%。因此,授权频段现在已经由FCC等监管机构开放,供未授权用户或次级用户(SU)机会使用,以提高可用频段的利用效率[6-10]。 SU通过使用认知无线电(CR)技术使用授权频段。 CR是一种新兴技术,它通过利用机会频谱接入来利用未充分利用的频谱资源,而不会拦截频谱的某些部分的合法或主要用户(PU),从而改善频谱使用并减轻频谱缺乏。在CR网络中,开放频谱使用的一个主要挑战是频谱分配,即通过分配算法,使得认知用户在不影响授权用户的前提下动态使用授权频谱,实现对不可再生频谱资源的有效利用,在解决频谱稀缺的同时,提高频谱利用率。
一种缓解频谱稀缺问题的潜在方法是将一些非安全数据业务从DSRC频段卸载到FCC授权的无牌电视白空间(TVWS)频段,用于认知接入。 在车载网络中使用TVWS频带的一个主要挑战是设计能够应对TVWS信道的时空变化的高效信道分配机制。 然而,由于缺乏认知无线电能力,基于竞争的IEEE 802.11p媒体访问控制(MAC)方案不适用于认知车载网络(CVN)。一些方法如基于RoF-DAS的车载网络信道分配算法逐步应用,它能改善车辆密度较大的情况下车辆用户的通信性能,本文则使用模糊匈牙利算法来解决认知车载网络的信道分配问题。
2. 研究的基本内容与方案
{title}