弹性光网络中基于图着色理论的资源分配算法

传统的波分复用网络采用固定栅格,已无法满足网络需求。提出一种改进的基于图着色理论的路由选择频谱分配(GT-RSA)算法。首先,使用前k条最短路径算法确定备选路由集合,根据各备选路由集合建立备选路由关系图;然后,使用图着色理论的混合整数线性规划模型进行选路,根据分支定界的饱和度最大优先算法得到优解,同时完成频谱的路由着色分区分配;最后,采用分区前后适配(PAR-FLF)算法对业务完成频谱资源的分配。仿真结果表明:GT-RSA算法具有更低的频谱资源消耗、阻塞率以及更高的平均链路连续率。

基于图着色理论的阵列天线校正方法

由于受环境变化影响,大规模平面相控阵天线收发通道的幅相一致性会发生偏移,常常需要标校才能保证其正常工作,但目前阵列天线收发通道数量较多,校正过程复杂,而且费时费力。基于图着色理论提出一种阵列天线快速校正方法,将校正时隙分配转化为图论中的着色问题,通过最小化时隙着色提高每个校正时隙的复用率,以降低阵列通道校准次数,达到缩短全阵列校正时间目的。仿真表明,对正六边形、正方形和正三角形平面阵列,分别最多仅需要8个、9个和16个时隙就可完成全阵列校正。

并行环境下基于图着色理论的空间数据部署

在面向计算部署到数据节点端执行的分布式并行环境下,提出一种基于图着色理论的适用于矢量空间数据的部署方法,将空间数据粒度的部署问题转化为图顶点着色的过程,提高了任意空间区域的信息查询效率.给出基于图着色理论的数据部署方法,并通过节点的任务量进一步改进算法,使得该算法可实现海量空间数据粒度的离散化部署,提高了空间数据检索和查询的并行化程度,充分利用了并行计算资源.

干扰环境下基于图着色理论的动态频谱分配算法

针对目前无线通信系统抗干扰能力不强、资源利用率较低等问题,首先根据不同的业务优先级,建立了一种具有分层架构的动态频谱分配模型。然后,基于图着色理论,提出了一种动态业务需求条件下的频谱分配算法。该算法既能保证优先级高的通信链路优先分配信道,也能保证系统具有一定的均衡性。仿真结果表明,与固定频谱分配算法和传统动态频谱分配算法相比,该算法能够有效提升系统的抗干扰能力、均衡性和满意度,并可获得更高的吞吐量。

基于图着色理论的短波无线接入网动态频谱分配方法

针对现有短波无线接入网频谱分配采用固定式分配方法,难以满足使用智能跳频技术新要求的问题,分析智能跳频短波无线接入网的频谱需求,将短波无线接入网用户频谱分配问题转化为基于图着色理论的短波无线接入网动态频谱分配模型,并提出可用于智能跳频短波无线接入网的动态频谱分配算法。将使用此算法的智能跳频与使用固定式频谱分配方法的定频通信相比,仿真结果表明,该算法明显提高了短波无线接入网的子网可通性及网络吞吐量,并能降低互扰率,有效支撑智能跳频技术在短波无线接入网中的应用,同时快速、高效、准确地完成对可用频谱的分配。

基于图着色理论的多飞艇多载荷协同对地观测和数据传输调度模型与算法

临近空间平台是一类新兴的空间平台,可用于局部区域的对地观测.本文针对飞艇的特性和用户需求的复杂性,设计了多飞艇多载荷协同对地观测和数据传输体系,考虑常规观测任务的调度,以及应急观测任务的重调度.基于图着色理论(graph coloring theory,GCT),构建多飞艇多载荷协同对地观测和数据传输调度模型.将多飞艇协同对地观测与数据传输任务、任务间的冲突、以及飞艇和地面站分别映射为无向图中的点、边和颜色,从而将问题构建为图着色问题(graph coloring problem,GCP),最大化完成任务总收益的优化目标转换为GCP中最大化着色点收益.提出一种文化基因算法(memetic algorithm,MA),设计基于收益改进的禁忌搜索(Tabu search,TS)算子更新染色体,和对父代染色体中最大收益的连续基因进行遗传的交叉策略.数值实验结果表明,针对不同规模的算例,相较于TS和ILOG CPLEX,MA能够在合理时间内获得更满意的解.

基于图着色模型飞机智能化排班算法的研究

飞机排班问题关系到航空公司的系统运作,作用十分重要。通过对飞机排班问题的分析,把飞机分配问题转化为图着色,应用图着色理论,建立了飞机分配问题的图着色模型,引入时间片算法确定了航班使用飞机的时间冲突集合,根据"先到先服务"的原则给出了飞机分配的顶点序列着色算法。用一个具体的算例,验证了飞机智能化排班比现有航空公司调度员人工排班更先进、更实用、更加节省资源,使资源配置更加合理。

一种基于图N重着色理论的信道冲突模型

无线网络的信道分配问题是网络规划的重点,而信道冲突模型是信道分配的基础。通过对信道冲突模型的分析,可以估计该网络信道分配问题的规模,并得出理想条件下信道分配的结果。针对当前的信道冲突模型无法完整描述多射频多信道网络信道冲突情况的问题,提出图N重着色理论,以及基于图N重着色理论的信道冲突模型,并在图论运算基础上给出了模型建立和求解的方法。理论分析与仿真结果表明,该模型可完整描述多射频网络的信道冲突情况,突出了多个射频接口间的信道冲突问题,并将信道分配问题抽象为图N重着色问题,进而转化为一般的图着色问题,以便于信道分配问题的分析和求解。

基于图论的认知无线网络频谱动态分配

在认知无线电网络中,图论与量子遗传算法相结合的频谱分配策略能够提高频谱利用率,但存在早熟和收敛精度不够等缺点。为了解决该问题而实现算法的优化,对图着色理论的频谱分配模型进行数学建模,并针对该模型提出了改进的量子遗传算法。首先,通过使用小生境技术初始化种群,使种群分布更加广泛、算法的收敛度更高;其次,根据进化代数对量子旋转角进行实时动态调整,对染色体进行阈值变异,防止个体陷入早熟,跳出局部解;然后,对干扰约束条件进行重新设计,有效地避免盲目性,提高了网络的公平性和网络效益。仿真结果表明,所提算法有效地提高了频谱利用率,极大地增强了网络系统的性能。

基于并行计算的多副本空间数据离散布局策略

根据空间数据的特点及其关系,提出一个负载均衡的空间矢量数据布局目标,并结合特定环境,采用基于图着色理论的空间数据布局算法及多副本的数据安全机制,提高了空间数据部署在并行环境下,数据节点上任务的执行效率和数据安全性.实验结果表明,该布局方法能实现数据的均衡布局,兼顾了并行计算的效率和安全性,适应并行计算下更多的查询应用.

基于智能跳频的短波无线接入网动态频谱分配算法

针对现有短波无线接入网的固定式频谱分配方法难以满足使用智能跳频技术新要求的问题,分析智能跳频短波无线接入网的通信需求,提出智能跳频短波无线接入网的动态频谱分配策略及算法。首先将各机动用户和接入基站看作一子网;然后将对各子网的频谱分配建模为基于图着色理论的智能跳频短波无线接入网频谱分配模型;最后结合通信需求提出分配策略和算法,完成频谱分配并进行了仿真分析。结果表明,这些频谱分配策略及算法以不同的目标进行频谱分配,能够有效支撑智能跳频技术在短波无线接入网中的应用,与固定式频谱分配方法的定频通信相比,在网络效益、子网满意度、网络公平性、网络支持用户数和频谱利用率等方面均有明显提升,同时能有效降低互扰率。

四色定理的三代证明

四色猜想是图论中的一个重要问题。它从猜想到定理历经三代证明:1976年阿佩尔和哈肯的计算机辅助证明、1994年西缪尔等人的修正、2005年贡蒂埃的形式证明。每一代证明都有其特点和不足。本文对这三代证明进行了简单的评述,说明由一个经验来源的问题如何逐步得到解决并在发展过程中形成诸多新的数学分支。它的重要性不在于结果本身而是从它的证明中可学到的潜在道理。本文提出数学证明的一个方面,即用有限驾驭无穷,同时在四色定理的证明史中表明简化永远是数学方法的灵魂。