几何覆盖无冲突着色问题

论文摘要

在这篇文章中,我们研究了无线通信网络中的在线频率分配问题。无线通信网络通常将整个覆盖区域划分为很多小区,每个小区通过一个基站与小区内的移动用户进行无线信号的通讯。当一个通讯请求出现在某小区时,无线通信系统必须立即为其分配一个频率。为了避免干扰,同一小区内或者在两个相邻小区内的通话不能被分配同一个频率。我们的目标是使用最少的频率来满足所有的通话。为实现无冲突频率分配,我们用超图无冲突着色模型来解决这个问题。本文我们研究无冲突着色问题的一般性模型,并给出一个具体的解决无冲突着色问题的一般性算法框架。我们证明,对于简单的几何覆盖,该算法能够给出一个无冲突着色。在模型中的几何区域是单位圆的情况下,我们将平面划分为单位蜂窝,我们证明,使用7组不同的颜色(频率)可以使得任意两个不同的蜂窝之间的通讯不会发生干扰。对于静态模型,我们的算法直接应用这个通用框架,使用O(logn)种颜色,保证无冲突着色。而之前的算法需要将平面上的点转换到高维空间,才能使用这样一类的一般性算法。对于动态模型,我们研究单位圆动态邻接图的性质,证明对于圆心位于同一个蜂窝中的的顶点构成的动态邻接图可以12着色。并进一步应用于算法框架,得到一个用O(logn)种颜色的无冲突着色。针对平面任意圆覆盖的情形,若对于每一个圆最多与其他k个圆相交,解决无冲突着色问题需要O(log~3k)。我们对于平面分割的方法可以使得,在单位圆的条件下,若任意区域最多被k个不同单位圆覆盖,无冲突着色只需要O(logk)中颜色。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 移动通讯频率分配问题
• 1.2 无冲突着色问题
• 1.3 相关问题及研究结果
• 1.3.1 已知结果
• 1.3.2 我们的贡献
• 1.4 本文的结构
• 第二章 几何覆盖与组合布局
• 2.1 幅度与布局
• 2.2 组合布局无冲突着色问题
• 2.2.1 无冲突着色对偶问题
• 2.2.2 原-对偶问题的等价性条件
• 第三章 无冲突着色算法框架
• 3.1 幅度空间最小超图
• 3.2 算法框架
• 3.3 平面中对于任意圆覆盖的点无冲突着色问题
• 3.4 无冲突着色算法框架的应用
• 第四章 单位圆覆盖静态模型
• 4.1 单位圆覆盖静态组合布局
• 4.2 单位蜂窝中单位圆覆盖无冲突着色
• 4.2.1 单位蜂窝中单位圆组合布局一般性质
• 4.3 单位蜂窝单位圆覆盖静态无冲突着色
• 第五章 单位圆覆盖动态模型
• 5.1 单位圆覆盖动态组合布局
• 5.2 单位蜂窝单位圆覆盖动态无冲突着色
• 5.3 算法时间复杂度
• 第六章 全平面单位圆覆盖无冲突着色
• 6.1 平面分割
• 6.2 全平面无冲突着色
• 6.3 单位圆无冲突着色问题下界
• 第七章 结论与展望
• 7.1 本文总结
• 7.2 进一步研究
• 参考文献
• 参与的科研项目与发表的论文
• 致谢