一种基于改进型图着色的移动通信网频率指配方法

摘要

本发明公开了一种基于改进型图着色的移动通信网频率指配方法，其改进之处在于，包括如下步骤：步骤1：指配需求分析；步骤2: 频率资源获取；步骤3: 兼容矩阵计算；步骤4：频率指配。本发明所公开的移动通信网频率指配方法，基于图着色算法运行速度快、准确率高的特点，算法主体结构采用图着色算法，并就图着色算法可能遇到的穷尽搜索导致的无解问题，利用禁忌搜索算法的思想，通过设置禁忌表来规避此缺陷，达到提升算法灵活性的目的。

说明书

技术领域

本发明涉及频率管理研究领域，尤其涉及一种基于改进型图着色的移动通 信网频率指配方法。

背景技术

随着无线通信技术的飞速发展，各种无线电业务对频谱资源的需求迅速增 长，在移动通信无线网络中有数以万计的小区，每个小区均包含数目不等的若 干频道，用于传输信令、话音和数据，这些频道都需要指配频率。一方面由于 无线电波传播空间的开放特性，每一发射天线发出的无线电波都可以传播到相 当广阔的空间范围；另一方面，各个小区为数众多的收、发信机在工作时间、 地点和频率上都可能相同或相近，所以如果对小区发射机指配的频率不当，就 必然会产生同频、邻频干扰，使通信质量变坏，系统容量降低。

发明内容

本发明所要解决的技术问题就是提供一种基于改进型图着色的移动通信网 频率指配方法。

本发明采用如下技术方案：

一种基于改进型图着色的移动通信网频率指配方法，其改进之处在于，包 括如下步骤：

步骤1：指配需求分析；

步骤2:频率资源获取；

步骤3:兼容矩阵计算；

步骤4：频率指配。

进一步的，所述的步骤1具体包括：

步骤11：提取移动通信系统无线网内的小区总数，假设移动通信系统无线 网内的小区总数为N；

步骤12：提取各小区所需的频道数目，各个小区所需的频道数： M₁,M₂,ΛΛ,M_N，设置频道需求向量，它可以表示为：

FD＝[M₁,M₂,L,M_i,L M_N]

其中m_i是代表第i小区所需的频道数，i＝1,2,ΛΛ,N，可由该小区所要承担 的业务容量和所要求的阻塞率确定。

步骤13：设置频道状态矩阵；

定义一个频道状态矩阵FSM来定量表示各小区各频道的状态：

$\mathrm{FSM}=\left(\begin{array}{cccc}{\mathrm{FS}}_{11}& {\mathrm{FS}}_{12}& \Lambda & {\mathrm{FS}}_{1M_m}\\ {\mathrm{FS}}_{21}& {\mathrm{FS}}_{22}& \Lambda & {\mathrm{FS}}_{2M_m}\\ \Lambda & \Lambda & \Lambda & \Lambda \\ {\mathrm{FS}}_{I1}& {\mathrm{FS}}_{I2}& \Lambda & {\mathrm{FS}}_{I{M}_m}\\ \Lambda & \Lambda & \Lambda & \Lambda \\ {\mathrm{FS}}_{N1}& {\mathrm{FS}}_{N2}& \Lambda & {\mathrm{FS}}_{N{M}_m}\end{array}\right)$

其中，FS_IJ代表第I小区的第J个频道的状态，取三种不同类型的值代表不 同频道的状态情况：

FSMatrix矩阵的第I行零的数目应该等于该行的相应小区所需频道数，其余 均为-1，除具有最大频道数的小区之外，其他小区都必须设立一些虚拟频道， 才能建立一个完整的频道状态矩阵，虚拟频道状态的取值均是-1，在频率指配 的过程中，当一个频道已分到频率之后，该频道的取值应该改变为非零的正整 数，即已分得的频率的序号。

进一步的，所述的步骤2具体包括：

步骤21，在授权频段内根据频率保护计划、频率管制计划等将保护频率、 禁用频率等去除；

步骤22，将各小区限制使用的频率去除，得到各小区基本可用频率集；

步骤23，将各小区的基本可用频率集和设备的工作频段取交集；

步骤24，基于频谱监测数据，各小区按地域去除频谱占用度高的频率和频 段；

步骤25，将各小区可用频段按信道间隔离散化，并将频率以正整数编号， 指配过程及指配结果以频率序号进行处理，约束关系以具体频率进行计算，确 定各小区可用频率集。

进一步的，所述的步骤3具体包括：

步骤31，考虑各小区间干扰，确定各小区间约束关系，计算生成指配约束 值；

步骤32，考虑各小区特点，判断某个待指配小区内部的无干扰频率间隔， 确定小区内约束关系，生成指配约束值；

步骤33，综合小区内、小区间约束值，生成兼容矩阵，兼容矩阵为N*N；

频道兼容矩阵FCM形式如下：

$\mathrm{FCM}=\left(\begin{array}{ccccc}{\mathrm{FC}}_{11}& {\mathrm{FC}}_{12}& L& {\mathrm{FC}}_{1J}L& {\mathrm{FC}}_{1N}\\ {\mathrm{FC}}_{21}& {\mathrm{FC}}_{22}& L& {\mathrm{FC}}_{2J}L& {\mathrm{FC}}_{2N}\\ L& L& & ...& L\\ {\mathrm{FC}}_{I1}& {\mathrm{FC}}_{I2}& L& {\mathrm{FC}}_{\mathrm{IJ}}L& {\mathrm{FC}}_{\mathrm{IN}}\\ L& L& & L& L\\ {\mathrm{FC}}_{N1}& {\mathrm{FC}}_{N2}& L& {\mathrm{FC}}_{\mathrm{NJ}}L& {\mathrm{FC}}_{\mathrm{NN}}\end{array}\right)$

其中，FC_IJ表示第I个小区和第J个小区的频道约束值m_IJ；m_IJ的取值是通 过计算各小区频道兼容间隔确定的，具体为：

$\mathrm{FC}\_\mathrm{DD}=\left(\begin{array}{cccccc}|d_1\left(f\right)-d_1\left(q\right)|>m_{11}& |d_1\left(f\right)-d_2\left(q\right)|=0& ...& |d_1\left(f\right)-d_J\left(q\right)|>m_{1J}& ...& |d_1\left(f\right)-d_N\left(q\right)|>m_{1N}\\ |d_2\left(f\right)-d_1\left(q\right)|=0& |d_2\left(f\right)-d_2\left(q\right)|>m_{22}& ...& |d_2\left(f\right)-d_J\left(q\right)|>m_{2J}& ...& |d_2\left(f\right)-d_N\left(q\right)|>m_{2N}\\ ...& ...& ...& ...& & ...\\ |d_I\left(f\right)-d_1\left(q\right)|>m_{I1}& |d_I\left(f\right)-d_2\left(q\right)|>m_{I2}& ...& |d_I\left(f\right)-d_J\left(q\right)|>m_{\mathrm{IJ}}& ...& |d_I\left(f\right)-d_N\left(q\right)|>m_{\mathrm{IN}}\\ ...& ...& & ...& & ...\\ |d_N\left(f\right)-d_1\left(q\right)|>m_{N1}& |d_N\left(f\right)-d_2\left(q\right)|>m_{N2}& ...& |d_N\left(f\right)-d_J\left(q\right)|>m_{\mathrm{NJ}}& ...& |d_N\left(f\right)-d_N\left(q\right)|>m_{\mathrm{NN}}\end{array}\right)$

其中，各频道间|d₁(f)-d₁(q)|＞m₁₁表示小区1内部的各频道间隔应大于m₁₁， |d₁(f)-d_J(q)|＞m_1J表示保证小区1与小区J无干扰的最小频率间隔应大于m_1J， |d₁(f)-d₂(q)|＝0表示小区1与小区2可以分别使用其可用频率集的任意频率而不 产生干扰。

进一步的，所述的步骤31具体包括：

步骤311，判断某两个待指配小区间是否存在同频、邻频干扰；若是，则跳 转步骤312，否则跳转步骤313；

步骤312，计算各小区间无同频、邻频干扰的最小频率间隔，将该间隔设为 该两个小区间频率指配的约束值；

步骤313，将该两个小区间的指配约束值设为0；

步骤314，重复上述过程计算任两个小区间的指配约束值。

进一步的，所述的步骤4具体包括：

步骤41，对各小区的待指配频道进行难度排序；

定义FCM矩阵第I行的元素之总和

${\mathrm{DD}}_I=\underset{J=1}{\overset{M}{\Sigma }}{\mathrm{FC}}_{\mathrm{IJ}},I=\mathrm{1,2},\mathrm{\Lambda \Lambda },M$

作为第I小区频道的频率分配难度系数；

步骤42，按难度递减顺序对各频道指配频率，各频道的选频策略为选择最 大复用频率或选择最低可用频率；

步骤43，判断当前指配频道是否发生阻塞，若是，则将违约值记录在禁忌 表，若否，则跳转至步骤44；

步骤44，判断各频道是否完成指配，若是，则跳转至步骤45，若否，则跳 转至42；

步骤45，判断是否存在阻塞频道，若是，则跳转至步骤46，若否，则完成 指配过程；

步骤46，阻塞频道指配。

进一步的，所述的步骤46具体包括：

步骤461，对阻塞频道的相关频道进行难度排序；

步骤462，按难度递减顺序对难度最大的相关频道进行频率调整，调整的策 略为将可用频率集中所有后备频率依次计算，选择违约值最小的频率进行调整；

步骤463，判断所做调整是否满足约束关系；若是，跳转至466将满足约束 关系的频率指配给阻塞频道，完成阻塞频道频率指配；若否，跳转至464将违 约值记录在禁忌表；

步骤464，将该频段指配频率的违约值记录在禁忌表；

步骤465，判断相关频道数量是否为0，若否，则跳转至步骤462进行下一 个相关频道进行频率调整；若否，则将最小违约值对应的频率指配给该频道和 阻塞频道；

步骤466，将满足约束关系的频率指配给阻塞频道；

步骤467，将最小违约值对应的频率指配给阻塞频道，完成频率指配。

本发明的有益效果在于：

本发明所公开的移动通信网频率指配方法，基于图着色算法运行速度快、 准确率高的特点，算法主体结构采用图着色算法，并就图着色算法可能遇到的 穷尽搜索导致的无解问题，利用禁忌搜索算法的思想，通过设置禁忌表来规避 此缺陷，达到提升算法灵活性的目的，经验证，该改进型图着色频率指配算法 可高效快速完成移动通信网频率指配，消解移动通信无线网络各小区间及小区 内的用频冲突，保障各小区有序用频，可为移动通信无线网络的频率规划提供 较好的技术支撑。通过对整个无线网内各个小区指配恰当的频率，使得众多的 收、发信机彼此兼容，各种相互干扰减少到可容许的范围，使千千万万的用户 与网络内的各种通信设备连接在一起，组成一个有序、有效的移动通信网。

附图说明

图1为本发明所公开的移动通信网频率指配方法的流程图；

图2为本发明所公开的移动通信网频率指配方法步骤1的流程图；

图3为本发明所公开的移动通信网频率指配方法步骤2的流程图；

图4为本发明所公开的移动通信网频率指配方法步骤3的流程图；

图5为本发明所公开的移动通信网频率指配方法步骤31的流程图；

图6为本发明所公开的移动通信网频率指配方法步骤4的流程图；

图7为本发明所公开的移动通信网频率指配方法步骤46的流程图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合实施例， 对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以 解释本发明，并不用于限定本发明。

实施例1，假设某地移动通信无线蜂窝网小区容量和信道规划数据如下：

假设移动通信系统无线网内的小区总数为：N＝36；

频道需求向量FD为：

FD＝[3,6,4,5,2,1,4,3,1,6,3,4,5,3,3,1,5,1,2,6, 4,5,2,1,4,2,1,6,3,4,5,3,3,1,6,1]；

如图1所示，本实施例所公开的基于改进型图着色的移动通信网频率指配 方法，包括如下步骤：

步骤1：指配需求分析；

步骤2:频率资源获取；

步骤3:兼容矩阵计算；

步骤4：频率指配。

如图2所示，步骤1具体包括：

步骤11：提取移动通信系统无线网内的小区总数；

假设移动通信系统无线网内的小区总数为N；

步骤12：提取各小区所需的频道数目，设置频道需求向量；

各个小区所需的频道数：M₁,M₂,ΛΛ,M_N，其中M_i为第i个小区所需的频道 数；设整个无线网络所有小区所需频道的总数，即无线网内频道总数为L，则我 们可知，所以以上数据应是来源于移动通信系统的业务容量预测与规 划。由于蜂窝小区所处的地理环境不同，各小区所要求的话务量是不一样的。 所以各小区所要求的频道数是不相等的。定义频道需求向量FD来表达各小区所 需的频道数，它可以表示为：

FD＝[M₁,M₂,L,M_i,L M_N]

其中M_i是代表第i小区所需的频道数，i＝1,2,ΛΛ,N，可由该小区所要承担 的业务容量和所要求的阻塞率确定。

步骤13：设置频道状态矩阵；

定义一个频道状态矩阵FSM来定量表示各小区各频道的状态。在基于图着 色算法的指配过程中，可供指配的频率资源在减少，已获得频率的频道在增加。 频道状态矩阵可以数学形式表达这种动态的过程。

定义频道状态矩阵FSM为：

$\mathrm{FSM}=\left(\begin{array}{cccc}{\mathrm{FS}}_{11}& {\mathrm{FS}}_{12}& \Lambda & {\mathrm{FS}}_{1M_m}\\ {\mathrm{FS}}_{21}& {\mathrm{FS}}_{22}& \Lambda & {\mathrm{FS}}_{2M_m}\\ \Lambda & \Lambda & \Lambda & \Lambda \\ {\mathrm{FS}}_{I1}& {\mathrm{FS}}_{I2}& \Lambda & {\mathrm{FS}}_{I{M}_m}\\ \Lambda & \Lambda & \Lambda & \Lambda \\ {\mathrm{FS}}_{N1}& {\mathrm{FS}}_{N2}& \Lambda & {\mathrm{FS}}_{N{M}_m}\end{array}\right)$

其中，FSM矩阵的元素FS_IJ代表第I小区的第J个频道的状态，频道的状态 可以取三种不同类型的值代表不同的情况：

FSM矩阵的第I行零的数目应该等于该行的相应小区所需频道数，其余均 为-1。除具有最大频道数的小区之外，其他小区都必须设立一些虚拟频道，才 能建立一个完整的频道状态矩阵，虚拟频道状态的取值均是-1。在频率指配的 过程中，当一个频道已分到频率之后，该频道的取值应该改变为非零的正整数， 即已分得的频率的序号。

如图3所示，所述步骤2具体包括：

频率资源获取是在授权的频段内，综合考虑频谱管理政策、频率保护信息、 频率管制信息、监测数据等对频谱资源进行预先处理，剔除不可用的频谱资源， 提高频谱资源利用效率。信息的来源包括：上级部门授权频率、频谱政策信息、 频谱监测信息、设备工作频段等。分析过程如下：

步骤21，在授权频段内根据频率保护计划、频率管制计划等将保护频率、 禁用频率等去除；

步骤22，将各小区限制使用的频率去除，得到各小区基本可用频率集；

步骤23，将各小区的基本可用频率集和设备的工作频段取交集；

步骤24，基于频谱监测数据，各小区按地域去除频谱占用度高的频率和频 段；

步骤25，将各小区可用频段按信道间隔离散化，并将频率以正整数编号， 指配过程及指配结果以频率序号进行处理，约束关系以具体频率进行计算，确 定各小区可用频率集。

如图4所示，对步骤3兼容矩阵的各元素，由是否同一小区、邻小区、非 相邻小区，是否可同频复用以及其它限制条件给出，也可由干扰计算的结果确 定。具体叙述如下：

步骤31，考虑各小区间干扰，确定各小区间约束关系，计算生成指配约束 值；

步骤32，考虑各小区特点，判断某个待指配小区内部的无干扰频率间隔， 确定小区内约束关系，生成指配约束值；

步骤33，综合小区内、小区间约束值，生成兼容矩阵，N×N；

频道兼容矩阵FCM形式如下：

$\mathrm{FCM}=\left(\begin{array}{ccccc}{\mathrm{FC}}_{11}& {\mathrm{FC}}_{12}& L& {\mathrm{FC}}_{1J}L& {\mathrm{FC}}_{1N}\\ {\mathrm{FC}}_{21}& {\mathrm{FC}}_{22}& L& {\mathrm{FC}}_{2J}L& {\mathrm{FC}}_{2N}\\ L& L& & ...& L\\ {\mathrm{FC}}_{I1}& {\mathrm{FC}}_{I2}& L& {\mathrm{FC}}_{\mathrm{IJ}}L& {\mathrm{FC}}_{\mathrm{IN}}\\ L& L& & L& L\\ {\mathrm{FC}}_{N1}& {\mathrm{FC}}_{N2}& L& {\mathrm{FC}}_{\mathrm{NJ}}L& {\mathrm{FC}}_{\mathrm{NN}}\end{array}\right)$

其中，FC_IJ表示第I个小区和第J个小区的频道约束值m_IJ；

m_IJ的取值是通过计算各小区频道兼容间隔确定的，具体表示如下；

$\mathrm{FC}\_\mathrm{DD}=\left(\begin{array}{cccccc}|d_1\left(f\right)-d_1\left(q\right)|>m_{11}& |d_1\left(f\right)-d_2\left(q\right)|=0& ...& |d_1\left(f\right)-d_J\left(q\right)|>m_{1J}& ...& |d_1\left(f\right)-d_N\left(q\right)|>m_{1N}\\ |d_2\left(f\right)-d_1\left(q\right)|=0& |d_2\left(f\right)-d_2\left(q\right)|>m_{22}& ...& |d_2\left(f\right)-d_J\left(q\right)|>m_{2J}& ...& |d_2\left(f\right)-d_N\left(q\right)|>m_{2N}\\ ...& ...& ...& ...& & ...\\ |d_I\left(f\right)-d_1\left(q\right)|>m_{I1}& |d_I\left(f\right)-d_2\left(q\right)|>m_{I2}& ...& |d_I\left(f\right)-d_J\left(q\right)|>m_{\mathrm{IJ}}& ...& |d_I\left(f\right)-d_N\left(q\right)|>m_{\mathrm{IN}}\\ ...& ...& & ...& & ...\\ |d_N\left(f\right)-d_1\left(q\right)|>m_{N1}& |d_N\left(f\right)-d_2\left(q\right)|>m_{N2}& ...& |d_N\left(f\right)-d_J\left(q\right)|>m_{\mathrm{NJ}}& ...& |d_N\left(f\right)-d_N\left(q\right)|>m_{\mathrm{NN}}\end{array}\right)$

其中，各频道间|d₁(f)-d₁(q)|＞m₁₁表示小区1内部的各频道间隔应大于m₁₁， |d₁(f)-d_J(q)|＞m_1J表示保证小区1与小区J无干扰的最小频率间隔应大于m_1J， |d₁(f)-d₂(q)|＝0表示小区1与小区2可以分别使用其可用频率集的任意频率而不 产生干扰，其余类似，不再一一叙述。

如图5所示，步骤31具体叙述如下：

步骤311，判断某两个待指配小区间是否存在同频、邻频干扰；若是，则跳 转步骤312，否则跳转步骤313；

步骤312，计算各小区间无同频、邻频干扰的最小频率间隔，将该间隔设为 该两个小区间频率指配的约束值；

步骤313，将该两个小区间的指配约束值设为0；

步骤314，重复上述过程计算任两个小区间的指配约束值；

如图6所示，所述的步骤4具体叙述如下：

基于图着色的频率指配算法的主体思想是将被指配对象按难度排序，然后 按难度从高到低进行频率指配。但是，在指配过程中可能会发生因找不到与已 指配频道或原有频率无干扰的可用频率，将导致算法无解，此情况被称之为该 频道发生阻塞。为了提升算法的适应性，通过引入禁忌搜索算法的禁忌表来对 算法进行改进，找到与阻塞频道有约束关系的相关频道，将阻塞的频道及其对 应各相关频率约束值放入禁忌表，并对相关频道按难度从高到低排序，约束关 系越复杂难度越大。然后先对难度最大的相关频道进行频率调整，调整后再对 阻塞频道指配频率，并判断其是否满足约束条件，如果没有干扰则将结果输出 即完成指配过程，否则记录该频率的违约值，再对禁忌表中频道相关的下一个 频道进行频率调整，以此类推直至找到无干扰的频率。如果所有相关频道都进 行了调整也没有找到合适的频率，就将违约值最小的频率指配给阻塞频道。

步骤41，对各小区的待指配频道进行难度排序；

难度排序是指利用频道兼容矩阵的约束关系值将每个频道的频率指配难度 定量地表达出来，频道兼容矩阵元素FC_IJ的取值，当它取较大值时，可供该频道 (第I频道)选择的频率资源就比较少；当它取较小值时，可供它选择的频率资 源就会多一些。所以定义FCM矩阵第I行的元素之总和

${\mathrm{DD}}_I=\underset{J=1}{\overset{M}{\Sigma }}{\mathrm{FC}}_{\mathrm{IJ}},I=\mathrm{1,2},\mathrm{\Lambda \Lambda },M$

作为第I小区频道的频率分配难度系数，很显然，DD_I越大，对第I小区频 道指配频率就越困难，反之也然。

步骤42，按难度递减顺序对各频道指配频率；

在指配过程中，按照频道排序难度递减，先难后易，把频率指配难度大的 频道排在前面先指配频率；反之，排在后边，后指配频率。

各频道的选频策略为：一种是选择最大复用频率，另一种是选择最低可用 频率。这两条准则的根本目的就是最大程度的保留剩余频率，且使用优质频率 (最低可用频率)。

步骤43，判断当前指配频道是否发生阻塞，若是，则将违约值记录在禁忌 表，若否，则跳转至步骤44；

步骤44，判断各频道是否完成指配，若是，则跳转至步骤45，若否，则跳 转至42；

步骤45，判断是否存在阻塞频道，若是，则跳转至步骤46，若否，则完成 指配过程；

步骤46，阻塞频道指配。

如图7所示，所述的步骤46具体包括：

步骤461，对阻塞频道的相关频道进行难度排序；

步骤462，按难度递减顺序对难度最大的相关频道进行频率调整；

调整的策略为将可用频率集中所有后备频率依次计算，选择违约值最小的 频率进行调整。

步骤463，判断所做调整是否满足约束关系；若是，跳转至D66将满足约 束关系的频率指配给阻塞频道，完成阻塞频道频率指配；若否，跳转至D64将 违约值记录在禁忌表；

步骤464，将该频段指配频率的违约值记录在禁忌表；

步骤465，判断相关频道数量是否为0，若否，则跳转至步骤D62进行下一 个相关频道进行频率调整；若否，则将最小违约值对应的频率指配给该频道和 阻塞频道；

步骤466，将满足约束关系的频率指配给阻塞频道；

步骤467，将最小违约值对应的频率指配给阻塞频道，完成频率指配。

表1给出了本专利所述算法对一个蜂窝网内各个小区指配频率的结果，指 配的结果表示为分别以小区序号和需求数/频道序号为序的频率指配表，该表 中，站号是代表无线网络内基站的编号，频率是指已分得的频率的序号。该网 由43个基站组成，120个频道，有的小区要求指配一个频率，有的则要求三个 频率或六个频率等。总共只用了17个已知可供指配频率就实现了全网的频率指 配，频率复用效率很高。由表中频率指配的结果，我们可以看出，同一小区内 的频率之间至少具有3个频道间隔，相邻小区的频率之间至少具有2个频道间 隔，频率复用距离之内非相同小区和非相邻小区的频率之间至少具有1个频道 间隔，确保了无线网络内部无线信道之间的干扰得到有效控制。

表1无线网络频率指配结果

站号 需求数/频率 站号 需求数/频率 站号 需求数/频率 1 3/89；111；79 21 5/85；79；111；104；89 31 4/104；85；97；111 2 6/91；102；87；76；97；84 22 3/107；102；91 32 2/82；104 3 4/111；94；102；109 23 3/94；82；76 33 1/76 4 5/104；85；91；100；107 24 1/87 34 6/99；91；87；79；94；102 5 2/79；87 25 5/102；79；107；99；84 35 3/94；82；76 6 1/89 26 1/82 36 4/97；85；104；107 7 4/85；99；109；76 27 2/91；76 37 5/79；89；111；84；76 8 3/82；102；94 28 6/102；111；99；85；94；79 38 3/99；109；87 9 1/87 29 4/89；109；79；107 39 3/91；82；102

10 6/87；91；111；102；94；99 30 5/102；99；84；111；104 40 1/97 11 3/109；91；85 31 2/82；76 41 6/82；87；94；107；79；104 12 4/76；102；82；107 32 1/87 42 1/111