背景:2007年,世界无线电通信大会在瑞士日内瓦开幕。大会主要研究在世界范围内使用无线电频率和满足全球频谱需求的问题;工业和信息化部总经济师王新哲在第一届中国无线电大会上强调,用好管好频谱资源,引导无线电产业实现高质量发展;2018年,第18届ITU(国际电信联盟)世界电信展在南非德班市开幕。面向未来5G商用,工信部副部长陈肇雄在致辞中提出三点倡议:一是推动频谱资源高效利用;二是推动产业协同发展,紧扣3GPP5G国际标准,加强全球产业链分工协作;三是推动技术广泛应用。无线电频谱是一种有限的自然资源,它广泛地应用于通信及其他一些领域中,随着计算机网络技术的飞速发展,网络信息的储存、处理和共享在人们的日常生活中扮演着日益重要的角色,公众移动通信承载的数据业务不断增长,所需的频谱带宽越来越大,传递网络信息的频谱资源的使用量也不断递增,电台的数量随之飞速增加,因此必然形成频率不够分配的局面。而频率短缺又限制了无线电业务的发展,但由于高频率无线电传播特性,目前人类对于3000GHz以上的频率还无法开发和利用,并且在一定区域、一定时间和一定条件下使用频率是有限的。所以,如何从技术上挖掘无线电频谱的潜力以及科学地管理和使用无线电频率成为频谱管理者们思考的问题。研究目的和意义:通过科学手段对频率资源进行规划和分配,一方面实现电台频率信号的规则分配,最大程度地减少干扰;另一方面从实际应用的角度,获得最优化的频率分配方案,满足用频需求。针对频道资源的管理问题,我们通过数学模型来模拟现实中无线电台的分布状况,可以将现实世界中的电台看作是图中的顶点,有限的频道信号数看成是L(2,1)-标号数。对电台进行频道信号的分配等价于对顶点进行L(2,1)-标号数的分配,通过对图模型的分析,我们要找出最少的L(2,1)-标号数。1992年,Griggs和Yeh[1]将频道分配问题转化为图的标号问题,并考虑了一般的情形——L(2,1)-标号问题,且猜想对任一个图G都满足λ(G)≤Δ2,与此同时,他们证明了对任意一个图G都满足λ(G)≤Δ2+2Δ。至今该猜想仍未完全解决,仅对一些特殊图类如弦图、直径为二的图、距离图、广义Petersen图等部分验证猜想的正确性。由于图的L(2,1)-标号的规则条件具有实际意义,所以我们研究的理论结果可以为实际管理频道分配问题提供理论基础。通过将理论结果应用于实际中无线电台的分布,我们可以节约实际中频谱资源的使用数量,获得优化频谱资源配置方案。研究方法:本文主要采取文献分析与数学模型分析方法。通过文献分析了解到国内外的研究现状与研究方法,选择合理的标号模型。在数学模型分析方法上我们主要选择了结构分析方法,这种方法是通过研究图的结构性质找出图中不可避免的子结构,再对这些子结构进行归纳证明。完成理论的研究后,我们研究了一些频率算法,如:穷举搜索算法、串行搜索算法、启发式搜索算法等,对这类算法的研究可以帮助我们检测所得实际的频率资源分配与理论结果是否具有良好的匹配性,以验证理论结果的优化性。结果:改进了理论结果,通过算法可以将实际问题应用于理论中。同时,验证了理论结果的优化性。(1)理论方面:2014年,Wang[2]证明了对于任意Halin图,图G的L(2,1)-标号数至多为A+7;如果Δ≥9时,图G的L(2,1)-标号数至多为Δ+2;如果Δ=3时,图G的L(2,1)-标号数至多为9。文献[2]中利用了文献[3]给出的三个经典的Halin图不可避免子结构,并且对三个不可避免子结构运用以归纳法加以证明。显然,预改进Halin图的L(2,1)-标号数上界,三个不可避免子结构已经不够用了,因此我们对Halin图的结构进行细致化分析,找出了更多的不可避免子结构。例如,当Δ=8时,我们构造了14个不可避免子结构,这些结构也可以为后续研究Halin图的其他染色问题提供研究思路。同时,我们得出了当Δ=8时,图G的L(2,1)-标号数至多为Δ+2,因此,证明了对于任意Halin图,图G的L(2,1)-标号数至多为Δ+6。(2)应用方面:根据实际生活中的需求情况,我们可以建立电台之间的干扰关系网络图,当距离比较近时干扰更加强烈,因此,需要给电台之间分配差值更大的频率信号,而距离较近时,对其的频率信号差值可以小点,这主要通过L(2,1)-标号的距离规则来限制,然后利用我们建立的标号算法,对该干扰关系网络图给出频率分配方案,结合理论可以得出较为优化的频率分配方案,如此可以将实际的问题通过算法来实现频谱资源的优化使用,同时验证了所得理论结果的优化性。