随着无线通信业务的飞速发展,有限的频率资源与日益增多的用户需求之间矛盾越来越突出,无线网络频率分配问题研究如何为无线网络节点进行优化的频率资源分配,使得整个无线网络使用最少的通信带宽,是解决这一矛盾最重要的手段之一,也是国内外学术界和工业界共同关注的基础科学问题之一。为了提高接收信号的信噪比,要求网络中距离越近的发射天线之间使用的频率差越大,我们可以将无线网络频率分配问题转化为如下的图标号问题：将每个天线用无向图的顶点表示,在有可能发生干扰的顶点之间用边连接,相邻顶点不能使用同一个频率即不能使用同样的颜色,这样频率分配问题就转化为了图着色问题；更进一步,把每个频点用一个数字来表示,要求每个天线分配的频率与临近天线分配的频率满足某种约束条件,频率分配问题就转化成图的标号问题。本论文针对频率资源不足和基站之间距离较小等情况下的频率资源配置问题,研究所对应的图标号问题和网格图的标号问题,取得了一些有价值的理论和仿真结果。论文的主要研究成果和创新点如下：1.松弛条件下的频率分配问题研究在频率资源紧缺的情况下,很难得到一种满足所有约束条件的最优频率分配方案,有必要在牺牲部分通信质量(即允许部分节点不完全满足约束条件)前提条件下,寻找一种尽可能多的满足约束条件下的频率分配方案,我们称为松弛条件下的频率分配问题,采用松弛的图标号模型进行频率分配,使不满足约束条件的节点个数最少。本论文针对该问题的贡献为：①本论文通过构造两个特殊的3-正则图,对Lin等人提出的松弛条件下无线通信网络最小跨度(带宽)与对应图最大度之间函数关系的猜想,给出了这两个猜想的反例并予以数学证明,证明该猜想不成立；②利用8-正则网格图为部分频率分配问题建模,采用计算机搜索和数学证明相结合的方式,研究并分析了在8-正则网格图中最小频率跨度与松弛条件的关系,给出了各种松弛条件下的频率优化分配方案；③提出了一个新的回溯算法,计算得到了松弛条件下二维和三维平衡超立方体图的频率优化分配方案。最后仿真结果验证了最小跨度与松弛条件的关系和8-正则网格图中得到的结论是一致的。2.距离4约束条件下的频率分配问题研究在某些无线网络中,节点之间的距离可能会非常接近,我们不但需要考虑相邻节点(距离1)和稍远一点节点(距离2)之间的干扰问题,还需要考虑更远节点之间的干扰问题。如果在干扰图中,最短路径长度不超过n的两个节点之间才有可能发生干扰,我们把这种约束条件下的频率分配问题称之为距离n约束条件下的频率分配问题。本论文利用距离4图标号模型来求解网络中节点之间的距离不超过4的约束条件下的频率分配问题,具体的贡献包括：①针对距离4标号问题的求解计算复杂度高的问题,提出了一种基于布尔变量的具有不等式约束的可满足性问题模型,并通过计算机搜索与数学证明的方式,求解了若干网格图的距离4约束下的最小频率跨度;②针对部分圈图的距离4约束的最小频率跨度未知,提出了一种基于辅助图的动态算法,得到了任意长度的圈图的距离4标号数；⑨针对图形为路、圈、以及若干棱柱形网格图的距离4标号数未知情况,本论文结合了数学理论证明和挖掘约束条件,建立了距离4约束的Pseudo-Boolean SAT模型,并提出了搜索算法求解它们的距离4标号数；同时利用图的贪心标号算法,从理论上给出了任意一个图的距离4标号数的上界与图的最大度的关系,并给出了棱柱形和环绕网格图的距离4标号数的上界。最后,通过实际仿真验证了上述算法的计算复杂度性能。3.基于图同构的标号图分类研究在基于图标号的无线网络频率分配问题中,频率分配算法的某些性能指标(如最大频率复用次数、最小同频复用距离等)与图的结构和节点位置关系密切相关,本论文将多个结构相同的标号图定义为等价类,提出了一种同构标号图搜索算法,获得网格标号图的分类结果；通过统计标号分类数与总标号数的比例,分析讨论了图的对称性。论文证明了部分图形具有特定的分类数,并给出了标号图分类结果,仿真结果也验证了同一类标号图对应的频率分配结果具有某些相似的性能特征。