连通子图算法在gsm通信网络中的应用

连通子图算法在gsm通信网络中的应用

0规划频率分配在无线通信网络中，每个噪声点都应该占用频点，网络上的总频率点有限，因此频率恢复是必要的。即2个相距一定距离的小区，其载波可以配置相同的频点，前提是2个小区相距足够远，其覆盖区域不能有太大的重叠部分。在GSM网络的频率规划规程中，一条最重要的原则就是尽可能地增大小区间的复用距离，规避小区间的同频干扰和邻频干扰。对于GSM网络，在制定频率分配方案时，要考虑到不同区域对于频点的不同需求。如商业区和闹市区的频点需求量较大，而偏远郊区的频点需求量相对较小。因此，在分配频率方案之前，需要对全网的频点需求作全面调查和评估，得到各个区域的频率紧张程度。1相关小区簇的网络模型相关小区簇就是有可能产生相互干扰的一个小区集合。相关小区簇中存在一个中心小区，集合中的其他任何一个小区都会和中心小区产生干扰，但是中心小区之外的其他小区之间也有可能会产生相互干扰。这样，就形成了如图1所示的相关小区簇的概念，整个GSM网络可以用相关小区簇的集合来表示。图1中，虚线的连线表示小区间具有相互干扰关系（有相互干扰关系的小区间会出现连线），相关小区簇的中心小区和簇中其他小区都存在干扰连线，而簇中的非中心小区间并非一定存在干扰连线。整个GSM网络可以分解成一个个相关小区簇，簇中的小区是存在干扰关系的，而不同簇之间的小区是不存在干扰关系的，因此不同簇的小区之间可以进行同频复用。在同一个簇中，并非每个小区对都存在干扰关系，因此并不是簇中所有的小区都不能同频。需要找到一个方法，计算簇中所有干扰小区对不能同频的情况下，该簇需要的最少频点数。2小区簇的连通子图在一个相关小区簇中，如果把每个小区的载波数全部相加起来，并令其为N，那么如果分配N个频点给相关小区簇，该簇是肯定不会出现同频现象的（暂不考虑邻频干扰）。但实际上，N大于相关小区簇的最小频点需求。例如图1中的相关小区簇2，除了中心小区外，另外3个小区为F、G和H。其中F和G有干扰连线，G和H有干扰连线，但是F和H之间是没有干扰关系的，换言之，F和H小区间是不存在干扰的，可以进行频率复用。因此，该小区簇所需的频点数并非是所有小区的载波数和，而是：根据拓扑学和图论的知识，可以把相关小区簇看作一个连通无向简“图”，簇中的小区是“图”的顶点，小区间的干扰连线是图的“边”。连通子图的定义为：在一个图中，总存在一个它的子图，子图中的任意2个顶点之间都存在1条边，此子图叫做连通子图。相关小区簇所需的最小频点数实际就是簇中所有“连通子图”的载波和的最大值。把图1中的相关小区簇1映射成一张“图”，顶点小区的载波配置数看作每条边的“度”。因此，评估小区簇所需的最小频点数的问题转化为一个求具有最大“度”的“连通子图”问题（见图2）。根据连通图的定义，可以看出图2中除中心小区（中心小区和任意其他小区都连通，可最后统计）外，存在子图1(ABE）、子图2(AB）、子图3(BE）、子图4(AE）、子图5(AC）、子图6(CD）、子图7(DE）等连通子图。因此相关小区簇1所需的最低频点数为3连接数据算法的实现3.1所有边的两端构成的集合设连通无向简图G=<V,E>，V={1,2,3，...，n}，n>1,|E|=e。定理：设G=<V,E>是连通无向简图，|V|>1，则b）记E中所有边的端点构成的集合为V1，则V1=V。证明：a）假设E中有2条边的2端点都相同，由于G是无向图，故这2条边为平行边，这与G是简图相矛盾。b）显然V1是V的子集。∵G是连通图，又|V|>1，故G中无孤立结点。∴对于任意的v∈V,v必定是E中某条边的端点，故v∈V1。∴V是V1的子集，∴V1=V，证毕。由定理知道，结点集V及图G完全可由无序偶组成的边集E确定，因此只需给计算机输入边集E即可，E用有2e个元素的一维数组来表示。3.2节点集v和相邻接收矩阵a的集合通过边集E求出结点集V及这个无孤立结点的简单无向图G的邻接矩阵A。3.3邻接矩阵判断通过邻接矩阵A来验证该简单无向图G是否连通。若不连通，提醒用户此为不连图，并且要求用户重新输入边集E。下面介绍如何通过简单无向图G的邻接矩阵A来判断图G是否连通。将邻接矩阵视为关系矩阵，利用关系中的闭包运算：记r(A）为A的自反闭包，t(A）为A的传递闭包，则rt(A）为简单无向图G的连通矩阵，即矩阵rt(A）中i行j列元素为1，当且仅当图G中结点i与j之间存在一条路相连（连通）。因此得出结论：简单无向图G连通的充分必要条件是矩阵rt(A）中所有元素皆为1。3.4关系矩阵生成此时矩阵rt(A）已肯定是一个连通无向简图的邻接矩阵了，下面求它的所有的连通子图。首先要找出小区关系簇中各个小区之间的干扰关系，然后以小区为顶点，以干扰关系为边，构建无向简图。图2可以用一个二维关系矩阵来描述。当2个小区有干扰关系时，矩阵中的相应值为1，当2个小区无干扰关系时，矩阵中相应值为0。关系矩阵既可以通过网络后台的NCS检测数据来获得小区间的干扰关系，也可以通过路测数据、切换数据等来获得。算法中，假设图中所有边数为1的连通子图为S1，所有边数为i的连通子图为Si。图2就是一个具有6个顶点和11条边的图，因此，图2中具有1条边的连通子图共有11个。a）求S1：所有边数为1的连通子图共有e个，即每条边及其2端顶点构成的连通子图。S1可以通过关系矩阵获得。以下从Si出发求Si+1，这里1≤i≤e-1。b）如果i<e-1，则从Si出发求Si+1的过程如下：对于每个边数为i的连通子图Gi，运行以下程序。Forj=1tok/*k是图中所有顶点的个数，对于每个顶点进行判断c）搜索结束条件：对i条边的连通子图进行向下i+1条边的搜索，如果对每个i条边的连通子图都搜索完毕后，没有发现任何一个i+1条边的连通子图，则整个搜索过程结束。d）载波需求数的确定：根据之前得到的各个连通子图，分别计算其对应的载波数总和，最后求出最大的载波数，并选出相应的连通子图。4从连通子图上进行优化连通子图算法在GSM网络的规划、优化和扩容等多方面都有较大的应用前景，具体体现在频点资源评估、网络覆盖优化和载波调整等方面。在GSM网络进行大型频率重新规划之前，可利用连通子图算法对网络的频点需求做出较精确的评估。首先可根据地理形态或者功能类型将目标区域分成不同的子区域，再分别统计各个子区域中不同小区簇对频点的需求，可根据各区域频点需求的平均情况得到区域的频率需求情况。一般来说，对于GSM网络而言，900MHz频段可用频点数为95个，1800MHz频段可用频点数为100个，如果考虑备用频点各有10个，则可以认为900和1800MHz频段的可用频点数分别为85个和90个。因此，所需频点数大于可用频点数的小区簇就是频率规划时的难点和重点所在，需要重点关注。对于平均频点需求数远远大于现有可用频点的区域，则需要通过打断连通子图的方法来减少频点的需求数，使之保持在可用频点总数之内。这样，才能保证频率规划的结果能够较好地避免频率间干扰。打断小区簇连通子图的方法如图3所示，可通过调整个别小区的覆盖距离，打断某条边，把连通子图变小。图3是图2中最大的连通子图，从图3中可以看出，如果AE这条边被打断的话，那么该图就变成了AB1和BE12个连通子图。显然，把一个大的连通子图分拆成更小的连通子图，非常有利于频率规划。打断AE这条边，使A和E小区中的用户不能检测到较强的E和A小区的信号。实现这种拆分的有效方法通常是通过调整A和E小区的覆盖区域，尽量减少覆盖区域的大范围重叠，以减小A和E小区之间互相干扰的概率，其前提是不能影响小区间的正常切换。如果一个连通小区簇，其频点需求数大于可用频点总数，而且簇中小区的覆盖关系比较复杂，任意打断某条“边”可能会带来切换、重选方面的问题。在这种情况下，无法通过拆分连通簇来解决问题，需要通过其他手段。针对GSM网络双频段的现状，可以考虑通过话务均衡和载波调整来解决部分问题。假设一个连通簇A，其中900MHz频段的频点需求已经超标，而1800MHz频段的载波需求较低，那么可以通过相关网优手段使话务从900M小区流入1800M小区，适当增加1800M小区的载波，减少900M小区的载波。连通子图算法还可用于指导密集小区簇的网络扩容。假设A小区扩容需要4个载波，但是A小区连通簇所有的频点数已经超过了可用频点总数。在这种情况下，无论分配给A小区哪4个频点，都不可避免地造成频率间的干扰。这种情况下的解决方法，就是打断A小区所在的连通簇，把它分拆成更小的连通簇。连通子图算法还可用于指导网络的覆盖优化。网络建设一直注重网络容量和质量的统一，在总的频率资源一定的情况下，载波容量越大的连通簇，其产生频率干扰的概率越大，网络质量可能越差。因此，需要进行一些覆盖优化，来调和网络容量和质量的矛盾。通过频率评估，找出网络中的超大连通簇，并把大的连通簇投射在电子地图上，分析连通簇的大小、分布、载波配置等特性，然后给出可行性较好的分拆方案，可以达到不减容量而改善质量的效果。例如，用算法进行编程，对深圳某区域的频点需求进行评估，得出的结果如表1所示。根据得到的该区域的结果，找到相对载波需求数较大且覆盖区域较广（或频点需求大于可用频点总数）的小区连通簇。由于6个小区具有两两干扰的关系，且总的载波配置较高，影响了网络扩容和网络质量，因此有必要进行覆盖优化。手段就是将该小区簇进行分拆，变成更小的连通簇。根据地理位置，打断白云m3和洲际m2之间的关系，并不会影响小区间的切换，且达到了拆分连通簇的目的。根据实际工程参数，确定通过增加洲际m3的天线下倾角（3°），使其有效覆盖距离由1.2km减少为700m，拆除了白云m3和洲际m2的干扰关系。该项措施通过进行覆盖优化，在不影响容量的情况下，有效拆分了连通小区簇，解决了频点紧张、干扰复杂的问题，实际效果显著。5gsbd目标本文把图论中的连通子图算法运用于GSM网络的频率资源评估，得出网络中的连通小区簇，并根