知识卡片

普通读书笔记卡 · 3775.a

飞蜂窝干扰图映射频谱

理解等级:中级

飞蜂窝频谱分配可建成干扰图:顶点表示飞蜂窝,边表示两者会相互干扰;给顶点的颜色就是频谱带,因此相邻顶点不能同色。这个映射把无线干扰约束转成 [[相邻顶点必须异色]] 的图着色约束,再用禁忌搜索寻找可行的少频谱方案。它依赖干扰边建模准确,不能由图着色结果反证无线测量正确;密集部署的背景见 [[飞蜂窝补室内覆盖也加重干扰]]。

示例(补充教学示例,非书中数据):三座飞蜂窝两两干扰,图是三角形。至少需要 3 种颜色/频谱;若漏画其中一条干扰边,着色会误判只需 2 种。流程是先建图、给初始着色,再在邻域里禁忌搜索,输出分配方案;书中称可确定最少频谱数,但零冲突只说明当前 K 可行,见 [[零干扰不证明频谱数最少]]。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 1 4 . 3 . 1 算 法 主 要 思 想 及 流 程 · 查看原书依据

      首先,为飞蜂窝网络频谱分配问题建立无向图模型,顶点对应飞蜂窝,边连接相互干扰的飞蜂窝,将其转化成图着色模型,相互干扰的飞蜂窝之间不能共用同一频谱带,即相当于图着色中相邻顶点不能用同一种颜色着色。其次,从图着色问题的一个初始解出发,通过禁忌搜索,在其邻域内不断搜索寻优,得到问题的近似最优解。

    参考来源

    - 位置:《智能算法导论》第 137 项《1 4 . 3 . 1 算 法 主 要 思 想 及 流 程》(源文件:`_epub-src/EPUB/xhtml/chapter14_0006.xhtml`;图 14.2) - 结论依据:原文把飞蜂窝映为顶点、相互干扰映为边、频谱带映为颜色,并要求相邻顶点异色;图 14.2 为建图、初解、禁忌邻域搜索和输出方案。三角形三色是补充教学示例,非书中网络。 - 原始内容:首先,为飞蜂窝网络频谱分配问题建立无向图模型,顶点对应飞蜂窝,边连接相互干扰的飞蜂窝,将其转化成图着色模型,相互干扰的飞蜂窝之间不能共用同一频谱带,即相当于图着色中相邻顶点不能用同一种颜色着色。