一种资源分配方法及装置的制造方法
一种资源分配方法及装置的制造方法
【技术领域】
[0001] 本发明涉及无线通信领域，尤其涉及一种资源分配方法及装置。
【背景技术】
[0002] 在PCI(化ysicalCellIdentity,物理小区ID)规划中，要为每个小区分配一个 物理ID号。LTE(LongTermEvolution,长期演进）中有编号为0至503总共504个PCI 编号，可W为504个小区不重复地分配，如果小区个数大于504,则需要基于一定的准则对 该些PCI编号重复使用。PCI关系到CRS(Cel]_-specificReferenceSi即al,小区专属参 考信号）在LTE系统的一个子峽中所占频率资源的位置，两个PCI虽然不相等，但是如果该 两个PCI模3 (即PCI编号对3取模的结果值，其结果值范围限于集合{0, 1，2})相等，则对 应的两个小区的CRS信号就会处在相同的时间频率资源位置上，并且如果两个小区的天线 方向图存在公共覆盖的交叠区域，则该两个小区的CRS信道就会相互产生干扰，称之为模3 冲突。
[000引 PCI规划所要解决的核也问题就是；为网络中的所有小区恰当的分配PCI编号，最 终在网络中尽最大可能为所有位于不同基站且天线方向图存在公共交叠覆盖区域的小区 对(两个小区)，分配模3不等的PCI,该样两个小区的公共交叠覆盖区域的CRS信号之间就 不会相互干扰。
[0004]目前，业界利用遗传算法寻找PCI规划的最优分配结果。用遗传算法进行PCI规 划的流程一般是：
[0005] 第一步：定义一个代价函数，表征天线主瓣方向的对齐程度，对齐程度越强，代价 函数值越高。W下图1至图3表示天线主瓣对齐程度，其中，图1表示天线主瓣最为对齐 的情况，直观描述为两个天线主瓣的角平分线在同一直线上，此种情况代价函数值最高，在 PCI规划时，对该两个小区应该分配模3不同的PCI编号；图2是两个小区天线主瓣没有 正对齐，但是指向同一侧，存在部分公共覆盖交叠区域，代价函数值相对于图1的情况小一 些；图3同样是两个小区的天线主瓣方向没有正对齐的情况，两者是指向异侧，仍然存在部 分公共交叠覆盖区域，代价函数值相对图1也要小一些；
[0006] 第二步：确定问题的规模，设置染色体序列，再使用遗传算法寻找最优分配结果。 假设有N个基站，每个基站有3个小区，则对所有基站分配PCI编号的全部排列组合数为护 种，遗传算法通过确定种群规模、种群个数，W及选择运算中的选择比例、交叉运算中的交 叉概率、变异运算中的变异概率等输入参数，对染色体序列进行变异交叉等运算，从该护种 排列中寻找到全局代价值最小的PCI分配染色体序列。遗传算法的流程如图4所示。
[0007] 遗传算法应用于PCI规划时会存在W下较为显著的问题；当待规划的基站数量很 多时遗传算法寻优速度非常慢。比如，对于3184个基站的情况，要大约17个小时才能找到 一个分配结果，如果有5000个基站，使用遗传算法进行PCI规划的时间还会更长。
【发明内容】
[000引本发明实施例提供了一种资源分配方法及装置，用w快速进行资源分配。
[0009] 本发明实施例提供的资源分配方法，包括：
[0010] 将N个目标对象的资源分配标识的初始值作为一行元素放入第一队列，并设置所 述N个目标对象的资源分配标识初始值对应的全局代价值为初始代价值，其中，一个目标 对象的一个资源分配标识用于标识该目标对象的所有可能的资源分配方案中的一种，所述 第一队列为MlXN的队列，N为队列的列数，N的取值为目标对象的数量，Ml为队列的行数， Ml取值为队列的长度；
[0011] 对所述第一队列执行遍历流程，所述遍历流程包括分别对所述N个目标对象中的 每个目标对象遍历所有的资源分配标识；
[0012] 所述遍历流程完成后，根据所述第一队列尾部一行元素确定第一资源分配优选方 案，所述第一资源分配优选方案中包含N个目标对象的资源分配标识，根据所述第一资源 分配优选方案为所述N个目标对象进行资源分配；
[0013] 其中，所述遍历流程中，针对第i个目标对象执行W下操作，1《i《N，所述第i 个目标对象为尚未分配资源的目标对象：
[0014]W队列尾部Q行元素为基础对第i个目标对象的所有资源分配标识进行遍历，得 到QiXQ行元素，所述QiXQ行元素中的每一行元素包含N个目标对象的资源分配标识，所 述di为第i个目标对象的所有资源分配标识的数量，Q为正整数；
[0015] 将所述diXQ行元素放入队列，计算所述ciiXQ行元素中每一行对应的全局代价 值；
[0016] 根据每一行元素对应的全局代价值对所有行元素进行排序，使每一行元素对应的 全局代价值按照从队列头部到尾部的顺序依次降低。
[0017] 本发明实施例提供的资源分配装置，包括：
[0018] 初始化单元，用于将N个目标对象的资源分配标识的初始值作为一行元素放入第 一队列，并设置所述N个目标对象的资源分配标识初始值对应的全局代价值为初始代价 值；其中，一个目标对象的一个资源分配标识用于标识该目标对象的所有可能的资源分配 方案中的一种，所述第一队列为M1XN的队列，N为队列的列数，N的取值为目标对象的数 量，Ml为队列的行数，Ml取值为队列的长度；
[0019] 第一搜索单元，用于对所述第一队列执行遍历流程，所述遍历流程包括分别对所 述N个目标对象中的每个目标对象遍历所有的资源分配标识；
[0020] 分配单元，用于在所述第一搜索单元完成所述遍历流程后，根据所述第一队列尾 部一行元素确定第一资源分配优选方案，所述第一资源分配优选方案中包含N个目标对象 的资源分配标识，根据所述第一资源分配优选方案为所述N个目标对象进行资源分配；
[0021] 其中，所述遍历流程中，所述第一搜索单元针对第i个目标对象执行W下操作， 1《i《N，所述第i个目标对象为尚未分配资源的目标对象：
[0022] W队列尾部Q行元素为基础对第i个目标对象的所有资源分配标识进行遍历，得 到QiXQ行元素，所述QiXQ行元素中的每一行元素包含N个目标对象的资源分配标识，所 述di为第i个目标对象的所有资源分配标识的数量，Q为正整数；
[0023] 将所述diXQ行元素放入队列，计算所述ciiXQ行元素中每一行对应的全局代价 值；
[0024] 根据每一行元素对应的全局代价值对所有行元素进行排序，使每一行元素对应的 全局代价值按照从队列头部到尾部的顺序依次降低。
[0025] 本发明的上述实施例中，由于在资源分配的过程中，分别对N个目标对象中的每 个目标对象遍历所有的资源分配标识(一个资源分配标识用于表示一种资源分配选择的可 能性)，并在遍历过程中，根据全局代价值对N个目标对象的遍历结果进行排序，从而找到当 前的较优分配结果，然后W该较优分配结果为基础对下一个目标对象的资源分配标识进行 遍历，W此类推，最终找到最优资源分配结果。由于每次对一个目标对象的资源分配情况进 行遍历，都是根据上一次遍历得到的较优分配结果为基础进行的，即，并不是遍历N个目标 对象的所有的资源分配可能性，而是遍历其中的一部分，目的是每遍历一次就朝最分配结 果逼近一次，从而可W快速寻找到资源分配的最优分配结果。
【附图说明】
[0026]为了更清楚地说明本发明实施例中的技术方案，下面将对实施例描述中所需要使 用的附图作简要介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本 领域的普通技术人员来讲，在不付出创造性劳动性的前提下，还可W根据该些附图获得其 他的附图。
[0027] 图1为天线主瓣正对齐的示意图；
[0028] 图2为天线主瓣同侧部分对齐的示意图；
[0029] 图3为天线主瓣异侧部分对齐的示意图；
[0030] 图4为现有技术中遗传算法流程示意图；
[0031] 图5本发明实施例中的天线方向图代价定义示意图；
[0032] 图6为天线方向图完全不对齐的示意图；
[0033] 图7为本发明实施例中的资源分配流程示意图；
[0034] 图8为图7中的步骤20的实现流程示意图；
[00巧]图9为本发明实施例中队列初始化示意图；
[0036] 图10为遍历0号基站对应的各种PCI组合的可能性的示意图；
[0037] 图11为遍历1号基站对应的各种PCI组合的可能性的示意图；
[0038] 图12为图11排序后的队列示意图；
[0039] 图13为遍历2号基站对应的各种PCI组合的可能行的示意图；
[0040] 图14A、图14B分别为本发明实施例提供的验证流程示意图；
[0041] 图15为本发明实施例中验证流程的初始化示意图；
[0042] 图16为基于图15的对0号基站的遍历不;意图；
[0043] 图17为对图16所示的遍历结果进行排序的示意图；
[0044] 图18为本发明实施例中逐位遍历的示意图；
[0045] 图19为本发明实施例中二进制遍历树的结构示意图；
[0046] 图20A、图20B、图20C、图20D分别为本发明实施例中的资源分配装置的结构示意 图。
【具体实施方式】
[0047] 本发明实施例可应用于为小区分配PCI的场景中，还可应用于其他资源（比如时 间资源、频率资源、空间资源、编码域资源(扰码）等）分配或资源规划场景中，比如，为小区 分配频点，或者为小区分配扰码等等。其中，对于被分配的资源的各种分配方案，本发明实 施例中用"资源分配标识"进行区分，对于资源分配的对象，本发明实施例中用"目标对象" 来表示。比如，在为小区分配PCI的场景中，一个"目标对象"即为一个基站(实际为一个基 站下的所有小区)，一个"目标对象"的"资源分配标识"代表一个基站下的所有小区的所有 可能的PCI排列组合中的一种；再比如，在为小区分配频点的场景中，一个"目标对象"即为 一个小区，一个"目标对象"的"资源分配标识"代表一个小区的所有可分配的频点中的一 个。
[0048] 本发明实施例提供的资源分配流程利用计算机数据结构中的队列结构对队列 中的元素进行遍历的过程来实现。该里所说的"队列"是指多元素集合，比如先进先出 (First-In-First-Out，FIFO)的线性表，也可W是数组（Array)或其他类似数据结构。
[0049] W下实施例中均使用队列来实现资源分配过程，队列的长度用行数来表示，每一 行称为一个元素，每行元素均为长度为N的序列，N为目标对象的数量，即，队列的列数为N。 另外，本发明实施例中约定，只允许在队列尾部(称为rear)进行元素插入操作（即入队操 作)，在头部(称为化ont)进行元素删除操作（即出队操作)。
[0050] 所谓遍历（Traversal),是指沿着某条搜索路线，依次对树形结构中的每个节点均 做一次且仅做一次访问。访问节点所做的操作依赖于具体的应用问题，比如在本发明实施 例所适用的资源分配场景中，对于遍历结果需要进行入队、计算代价值等操作。
[0051] 1、代价定义
[0052] 利用队列进行资源分配的过程，即为利用队列对各种可能的资源分配方案进行遍 历，并根据资源分配的代价值寻找各种可能的资源分配方案中的最优分配结果或近似最优 分配结果的过程。资源分配的代价值越低，则对应的资源分配方案越接近最优。
[005引 WPCI分配为例，假设有N个基站，编号为0, 1，…N-1，对于第i个基站有Ki个小 区，第i个基站中所有小区可W分配PCI的全部排列组合数为di个，则对网络内全部N个 基站分配PCI的所有组合数为
其中，n为连乘运算符号。
[0054] 队列中的每一行元素对应一个全局代价值。全局代价值的计算公式可由公式（1) 给出：
[00巧]
[0056]其中，GlobalCost表示全局代价值；M是所有具有公共交叠覆盖区域的小区对； Ui是PCI分配因子，如果天线方向图具有公共覆盖交叠区域的第i个小区对中两个小区 分配的是模3相同的PCI编号，则《 1=1，表示该两个小区的CRS信号之间存在相互干扰， 如果第i个小区对中两个小区分配的是模3不同的PCI编号，则《 1=0,表示该两个小区 CRS信号之间不存在相互干扰；PairCellCosti表示第i个小区对中两个小区之间的代价， PairCellCosti〉0 (化irCellCost与《取值与否无关，只与两个小区的天线方向图存在公 共交叠覆盖区域的大小有关)。一个小区对中两个小区间的代价的定义随后给出。
[0057] PCI规划的目的是使GlobalCost尽量小，如果所有的ui均为0,则GlobalCost=0， 即整个网络中所有小区都没有PCI编号模3冲突的情况，但是一般情况是并不可能所有的 ?i为0,因为有可能存在超过3个小区的情形具有公共覆盖交叠区域，该样就不可避免的 存在PCI编号模3相等的天线方向图具有公共交叠覆盖区域的小区对，利用搜索算法搜索 到的PCI分配方案的最优结果应该是使得尽量多的且较大的化irCellCosti对应的（〇1=0。
[0058] -个小区对中两个小区之间的代价一般是指，如果将该两个小区的PCI编号模3 相等，贝ij需要为该两个小区的CRS信号的SINR(Si即altoInte;rferenceNoiseRatio,信 干噪比）的恶化付出的代价，该种代价值可W根据实测数据，也可W根据天线方向图的地理 方位计算。
[0059] 从实测数据角度来考虑，两个小区之间会存在一个切换带区域，通过计算机静态 系统仿真可将规划区域进行栅格化处理(栅格就是边长为20米或其他长度数值的正方形 区域)，两个小区的切换带中包含的栅格数目就可W表示该两个小区构成的小区对所对应 的代价值。
[0060] 从天线方向图地理方位角度来考虑，主要是从几何的角度看两个天线方向图公共 覆盖区域面积的大小，即从视觉角度定义图1至图3情形所对应的代价。本发明实施例给 出了一种优选方式：将小区天线方向图主瓣的角平分线作为天线方向图的方向向量，长度 为单位1，则两个小区天线方向角对齐程度的代价可W由两个单位长度的方向向量端点的 欧氏距离的远近表示，如图5中的端点A和端点B之间的欧氏距离即为小区1和小区2的 成对小区的代价值，表示为：
[0061]
[0062] 根据公式（2)，如果两个小区天线方向图如图1所示的正对齐，则 PairCellCost=4,如果两个小区的天线方向图如图6所示正好相反，即完全不对齐，此时两 个天线方向图的单位方向向量距离最远，PairCellCost=0。
[0063] 2、资源分配过程
[0064] 下面W目标对象数量为N、利用列数为N的队列进行资源分配为例，结合图7描述 资源分配流程。
[0065] 参见图7,为本发明实施例提供的资源分配流程100的示意图，该流程可包括：
[0066] 步骤10 ;将N个目标对象的资源分配标识的初始值作为一行元素放入第一队列， 该初始值表征N个目标对象尚未分配资源，在资源分配的后续流程中资源分配标识初始值 将被具体资源分配方案对应的资源分配标识值替换掉。步骤10中，还设置所述N个目标对 象的资源分配标识对应的全局代价值为初始代价值，本实施例中优选地将初始代价值设置 为0,表示尚未进行资源分配。该第一队列为M1XN的队列，Ml为队列的行数也即队列长 度，N为队列的列数。
[0067] 步骤20 ;对所述第一队列执行遍历流程，所述遍历流程包括：分别对所述N个目标 对象中的每个目标对象遍历所有的资源分配标识。
[0068] 步骤30 ;所述遍历流程完成后，根据所述第一队列尾部一行元素确定第一资源分 配优选方案，所述第一资源分配优选方案中包含N个目标对象的资源分配标识，根据所述 第一资源分配优选方案为所述N个目标对象进行资源分配。
[0069] 针对步骤20的实现过程，图8示出了一种优选实现方式。在图8所示的流程200 中，按照从第一个目标对象到最后一个目标对象的顺序，依次对N个目标对象中的每个目 标对象遍历所有的资源分配标识。在依次对所述N个目标对象中的每个目标对象遍历所有 的资源分配标识的过程中，针对每个目标对象执行基本相同的操作，W针对第i(l《i《N) 个目标对象(该目标对象尚未分配资源)为例，执行W下操作；W队列尾部Q(Q> 1)行元素 为基础对第i个目标对象的所有资源分配标识进行遍历，得到diXQ行元素，所述QiXQ行 元素中的每一行元素包含N个目标对象的资源分配标识，所述di为第i个目标对象的所有 资源分配标识的数量(步骤23 );将所述QiXQ行元素放入队列的尾部，计算所述QiXQ行元 素中每一行对应的全局代价值(步骤24);根据队列中的每一行元素对应的全局代价值对队 列中的所有行元素进行排序，使队列中每一行元素对应的全局代价值按照从队列的头部到 尾部的顺序依次降低(步骤25)。其中，全局代价值的大小表明对应的资源分配方案距离最 优资源分配方案的远近程度，全局代价值越小，则对应的资源分配方案越接近最优。
[0070] 在步骤20中，在针对第i(1《i《N)个目标对象遍历该目标对象的所有的资源 分配标识时，可队列当前尾部的一行或多行元素为基础进行遍历。
[0071] 在W队列当前尾部的一行元素为基础进行遍历时（即此时Q=0,保持该行元素中 除第i个目标对象W外的N-1个目标对象对应的资源分配标识不变，即遍历得到的Qi行元 素中，第i个目标对象的资源分配标识各不相同，而其他目标对象的资源分配标识均保持 不变。通过该种方式，在对第i个目标对象的资源分配标识进行遍历时，W第i-1个目标对 象的遍历结果中代价值最小的一行元素为基础进行，即每次遍历W上一次遍历得到的最优 分配结果为基础进行，最优分配结果总是在队列尾部，从而可W快速逼近最优分配结果。
[0072] 考虑到每次资源分配遍历过程中，队列尾部的元素只是暂时性的最优分配结果， 由于资源尚未分配完毕，并不表示其就是最终的最优分配结果，因此每次仅选取队列尾部 一行元素为基础进行遍历，则对代价值次小或者次次小的其他行元素来说不公平，即有可 能导致寻找到的最终结果不一定是最优分配结果。即使遍历结果中的最优分配结果仅有一 个，也会出现类似问题。为了尽量使最终结果逼近最优分配结果，对第i个目标对象的资源 分配标识进行遍历时，可第i-1个目标对象（即前一个目标对象）的遍历结果中的多个 较优的分配结果为基础进行遍历。
[0073] 在W第一队列当前尾部的Q行元素为基础进行遍历时（即此时Q〉l)，可W针对其 中的每行元素按照如上方式进行遍历，即；针对每行元素，保持该行元素中除第i个目标对 象W外的N-1个目标对象对应的资源分配标识不变，即遍历得到的Qi行元素中，第i个目 标对象的资源分配标识各不相同，而其他目标对象的资源分配标识均保持不变。通过该种 方式，在对第i个目标对象的资源分配标识进行遍历时，W前一次遍历得到的多个较优的 分配结果为基础进行，从而可W-方面快速逼近最优分配结果，另一方面尽量保证最终寻 找到的分配结果为最优分配结果。
[0074] 考虑到如果该Q行元素中至少有两行元素满足如下条件；前一个被遍历的目标对 象巧日第i-1个目标对象）对应的资源分配标识相同，则会导致重复遍历。针对该种情况， 优选地，可针对满足上述条件的两行或两行W上元素，取其中代价值最小（即最靠近队列尾 部）的一行元素作为基础，对第i个目标对象的所有的资源分配标识进行遍历。
[007引通过流程100可W看出，由于在资源分配的过程中，利用队列结构依次对N个目标 对象中的每个目标对象遍历所有的资源分配标识(一个资源分配标识用于表示一种资源分 配方案)，并在遍历过程中，根据全局代价值对N个目标对象的遍历结果进行排序，从而找到 当前的较优分配结果，然后W该较优分配结果为基础对下一个目标对象的资源分配标识进 行遍历，W此类推，最终找到资源分配的最优分配结果。由于每次对一个目标对象的资源分 配情况进行遍历，都是根据上一次遍历得到的较优分配结果为基础进行的，即，并不是遍历 所有可能的资源分配方案，而是遍历其中的一部分，目的是每遍历一次就朝最优分配结果 逼近一次，从而可W快速寻找到资源分配的最优分配结果或近似最优分配结果。
[0076] 图8所示的流程200是按照目标对象的编号从小到大的顺序对目标对象进行遍历 的，事实上，目标对象的遍历顺序不止该种情况，还可W从大到小，或者约定的其他顺序，只 要保证可W遍历到所有的目标对象即可。
[0077] 考虑到如果目标对象或待分配资源的数量较多，则有可能在步骤20的执行过程 中，第一队列已满或队列溢出，本发明实施例针对该种情况还提供了W下解决方案：当第一 队列已满或队列溢出时，从第一队列的头部开始顺序移除P(P> 1)行元素，即，将P行元 素出队。P值可预先设置，P值的大小可根据目标对象或待分配资源的数量W及系统处理性 能等因素进行设置。
[0078] 优选地，为了尽可能得到最优分配结果，本发明实施例还提供了W下优选方案：
[0079] 当第一队列已满或队列溢出时，将从第一队列出队的P行元素放入第二队列，分 别对第一队列和第二队列执行步骤20的流程。相应的，在步骤30中，比较第一队列尾部一 行元素的全局代价值和第二队列尾部一行元素的全局代价值，根据两者中全局代价值最小 的元素确定第一资源分配优选方案，根据所述第一资源分配优选方案为所述N个目标对象 进行资源分配。第二队列的尺寸与第一队列相同，即第二队列的行数和列数分别与第一队 列的行数和列数相同。
[0080] 在上述优选方案中，如果第一队列元素再次发生溢出，则可从第一队列的头部开 始顺序删除P1 (P1>1)行元素。同理，如果第二队列元素发生溢出，则可从第二队列的头 部开始顺序删除P2 (P2 > 1)行元素。P1和P2可相等也可不相等，具体取值大小可预先设 置。
[0081] 为了更清楚地对流程100进行说明，下面W为N个基站下覆盖的小区分配PCI为 例，描述流程100的具体实现过程。
[0082] 在步骤10中，进行队列的初始化操作。创建一个M1XN的队列a,其中，N为队列 a的列数，取值为基站的数量，Ml为队列的行数，也即队列a的长度。将N个基站中每个基 站对应的资源分配标识初始化为-1，表示N个基站均未被分配PCI，将每个基站对应的资源 分配标识的初始值作为一行元素入队，将该行元素对应的初始全局代价值设置为0。该队列 a可W理解为一个MlXN的二维数组，每次进入队列a的都是一个1XN的向量，是队列a的 元素，横坐标为基站的编号，纵坐标为资源分配标识，一个资源分配标识代表一个基站的一 种PCI组合。为了便于理解，图9示出了一个N=5,即5个基站的例子。
[008引在步骤20中，从编号为0的基站开始，依次遍历每个基站的所有PCI组合的编号， 直到编号为4的基站分配好PCI组合的编号为止。
[0084] 首先，对编号为0的基站（即第一个基站）的所有可能分配的PCI排列组合进行遍 历，即对0号基站可能分配的PCI的q。种可能进行遍历，并且遍历过后产生的新元素入队。 为了便于理解，图10给出了N=5,可分配PCI数量为3 (PCI=0, 1，2)，也=6的情况，即0号基 站有3个小区，共有6种PCI分配的可能性的遍历结果，该6种PCI分配的可能性包括：
[00财第一种可能性（PCI组合的编号等于0);小区1的PCI=0,小区2的PCI=1，小区3 的PCI=2 ;
[00 8引第二种可能性（PCI组合的编号等于1);小区1的PCI=0,小区2的PCI=2,小区3 的PCI=1 ;
[0087] 第H种可能性（PCI组合的编号等于2);小区1的PCI=1，小区2的PCI=0,小区3 的PCI=2 ;
[008引第四种可能性（PCI组合的编号等于3);小区1的PCI=1，小区2的PCI=2,小区3 的PCI=0 ;
[0089] 第五种可能性（PCI组合的编号等于4);小区1的PCI=2,小区2的PCI=0,小区3 的PCI=1 ;
[0090] 第六种可能性（PCI组合的编号等于5);小区1的PCI=2,小区2的PCI=1，小区3 的PCI=0。
[0091] 此时只给0号基站的小区分配了PCI,而其他基站还没有分配，所W对于该6种排 列组合，各个行元素对应的全局代价值仍旧为0。
[0092] 然后，对1号基站的所有ql种可能分配的PCI组合情况进行遍历，遍历产生的新 元素入队。为了便于理解，图11给出了N=5, 9。=屯=6的情形。
[0093] 此时队列a中已经有两个或两个W上基站的小区分配了PCI,可W计算出全局代 价值，即已经分配了PCI的基站参与全局代价的计算，分配了PCI的小区，如果构成成对邻 区关系，即存在化irCellCost值。如果该两个小区分配了模3相同的PCI编号，则该小区 对对应的《=1，如果分配了模3不同的PCI编号，则该小区对对应的《=0。图11的C。~Q 表示对1号基站遍历得到的6行元素对应的全局代价值。全局代价的计算方法同前所述， 在此不再重复。
[0094] 然后，根据全局代价值对队列a中的所有行元素进行排序，排序后的队列a从头部 到尾部，各元素对应的全局代价值依次减小。由于队列头部的5行元素的全局代价值仍旧 为初始代价，即为0,所W队列头部元素通过排序有可能排到队列尾部，排列后的一个可能 情形如图12所示。
[0095] 接下来对编号为2的基站的各种PCI分配情况进行遍历，遍历产生的新元素入队， 新入队的元素的全局代价值为Ce~。1，然后按照全局代价值对队列a中的所有元素进行排 序。为了便于理解，图13给出了N=5,听屯=屯=6的情形，即共有5个基站，基站0、基站1和 基站2都是有3个小区，共有3个PCI可供分配（PCI=0,1，2)，所W每个基站有6种PCI分 配的可能性。
[0096] 按照前述方式，依次对编号为3的基站W及编号为4的基站进行遍历。当对编号 为4的基站遍历完成之后，队列尾部的元素为全局代价值最小的元素，将该元素出队。
[0097] 在步骤20的流程中，如果还未遍历到最后一个基站，但是队列a已满或者溢出，贝U 可将一部分元素（比如P行元素，P> 1)出队。此后继续执行遍历过程，直至最后一个基站 被遍历。优选地，将P行元素出队后，保留在第一队列中的元素行数（M1-P)至少大于1，保 留的元素行数越多，得到的分配结果越接近最优分配结果，可根据此原则来确定P的取值。
[009引优选地，当队列已满或者溢出时，将P行元素出队后，将该将P行元素放入队列b中。然后，分别对该两个队列执行步骤20的过程，直到该两个队列最终将全局代价值最小 的元素出队。相应的，在步骤30中，取该两个队列最终出队的元素中全局代价值最小的元 素，根据该元素为相应基站的小区分配PCI。
[0099]上述实例中，需要配置的相关参数包括：队列a的长度为Ml，队列a中元素个数超 过Ml后出队元素个数为P。根据仿真测试经验，假设基站个数是N，则队列a的长度M1=30N 至IJ50N之间。队列a满了或者有溢出时，假设此时队列中的元素个数为U个，则出队的元素 个数P=U-M1+1，即队列a内保留元素的个数比队列长度少一个即可，因为一次不能删除太 多备选元素，W最大可能性保证最优分配结果不被删除出队。
[0100] 3、验证流程
[0101] 由于上述资源分配流程中，并未像极大似然算法那样对所有可能的资源分配方案 进行一一遍历，所W并不能完全保证得到的结果是全局最优分配结果。为了尽量使最终得 到的资源分配方案逼近全局最优分配结果，本发明实施例优选地还提供了根据上述资源分 配流程得到的资源分配优选方案进行进一步验证的流程。目P，在确定出上述第一资源分配 优选方案之后，还可进一步根据该第一资源分配优选方案执行验证流程。相应的，在进行资 源分配时，根据验证流程的验证结果为所述N个目标对象进行资源分配。
[0102] 参见图14A，为本发明实施例提供的验证流程300示意图，如图所示，该流程主要 包括：
[0103] 步骤40;将通过流程100或其优选方案得到的第一资源分配优选方案（即最优分 配结果)中的N个目标对象的资源分配标识作为一行元素放入M2 XN的第H队列，将第一变 量（图中示为MinCost)的取值设置为第一资源分配优选方案对应的全局代价值，然后转入 步骤41。其中，M2为队列的行数，取值为所述第H队列的长度。
[0104] 步骤41 ;对所述第H队列执行遍历流程(该遍历流程的具体实现过程同前所述， 比如可参照遍历流程200)。比如，从第1个目标对象开始，W队列尾部的一行或多行元素为 基础遍历目标对象的所有资源分配标识，直到第N个目标对象为止。遍历流程执行完成后， 即对N个目标对象的资源分配标识遍历完成，此时转入步骤42。
[0105] 进一步地，在步骤41的执行过程中，若满足结束条件，则将所述第H队列尾部一 行元素作为验证结果出队，并结束验证流程300。
[0106] 步骤42;判断所述第H队列尾部一行元素对应的全局代价值是否小于所述第一 变量（图中示为MinCost)的取值，若是，则转入步骤43,否则转入步骤44。
[0107] 步骤43 ;将所述第一变量（图中示为MinCost)设置为所述第H队列尾部一行元素 对应的全局代价值，然后转入步骤41 ;
[0108] 步骤44 ;对所述第H队列尾部一行元素中的每个目标对象遍历所有的资源分配 标识，并在遍历完成所有目标对象的资源分配标识后，将遍历结果放入所述第H队列，计算 当前入队的每一行元素对应的全局代价值，根据所述第H队列中的每行元素对应的全局代 价值对所述第H队列中的所有行元素进行排序，使所述第H队列中每一行元素对应的全局 代价值按照从所述第H队列的头部到尾部的顺序依次降低，然后转入步骤41。
[0109] 进一步地，在步骤44的执行过程中，若满足结束条件，则将所述第H队列尾部一 行元素作为验证结果出队，并结束验证流程300。
[0110] 优选地，为了减少运算开销、提高运算效率，步骤41完成之后在转入步骤42之前， 可只保留第H队列尾部一行元素，将其余行元素出队。
[0111] 优选地，当步骤41或步骤44的执行过程中，第H队列已满或溢出时，保留第H队 列尾部一行元素，将其余行元素出队后，继续执行后续流程。该优选方案的流程可参见图 14B所示的流程400,相关步骤的具体实现可参见流程300,在此不再重复。
[0112] 上述流程300和流程400中的所述结束条件可W是；当前运算次数达到最大运算 次数。可W将从第一个到第N个目标对象的完整遍历过程定义为一次运算，也可W将对一 个目标对象的完整遍历过程定义为一次运算，本发明实施例对此不做限制。另外，结束条件 的定义也不仅W运算次数为依据，比如还可运算时间为依据或者多种因素相结合来考 虑，本发明实施例对此也不做限制。
[0113] 为了更清楚地对流程300进行说明，下面继续W上述为5个基站的小区分配PCI 的场景为例，描述流程300的具体实现过程。
[0114] 当利用队列a或者利用队列a和队列b执行遍历流程后，得到最终分配结果记为 找〇，X。…Xn_i}，其中，XiG{0, 1，…屯-1}，1=0, 1，…N-1，即第i个基站分配到的PCI的组合 编号的索引为Xi，该最终分配结果的全局代价为C。。
[0115] 在步骤40中，将该最终分配结果进入队列C。设置一个指针，该指针指向当前 待遍历的基站，设置并初始化一个变量MinCost=C。。为了方便理解，图15给出了N=5， q〇=qi=...94=6,XiG{0, 1，2, 3, 4, 5}，i=0, 1，…，4的情形，目P共有5个基站，每个基站有3个 小区，每个基站有6种分配PCI的排列组合数，通过执行流程100后得到的最终分配结果为 {3,5,2,0,4}。
[0116] 在步骤41中，首先对编号为0的基站的所有PCI排列组合情况进行遍历，遍历产 生的新元素入队，并计算该些新元素的全局代价值。由于编号为0的基站遍历完毕后，将 指针指向编号为1的基站。为方便理解，图16给出了继图15W后的遍历结果，其中，N=5， q〇=qi=...94=6,X;G{0, 1，2, 3, 4, 5}，i=0, 1，…，4,入队的新元素代价分别为C〇~C日。按照 全局代价值从大到小排序，针对图16,排序过后的可能情形如图17所示。
[0117] W此类推，通过步骤41，从编号为0的基站开始到编号为4的基站为止，对各基站 的PCI排列组合情况进行遍历。在当前指针指向编号为4的基站，并且完成对该基站的各 种PCI排列组合情况的遍历后，保留队列C中队尾一行的元素在队列中，将其他元素出队， 并且将指针指向编号为0的基站，然后转入步骤42。
[011引如果在步骤41的执行过程中，队列C已满或者已经溢出，则保留队列C中队尾一 行的元素在队列中，将其他元素出队，并且将指针指向编号为0的基站，然后转入步骤42。
[0119] 如果队列C中当前保留的元素的全局代价值〈MinCost，则在步骤43中，更新 MinCost为队列C中当前保留的元素的全局代价值，然后转入步骤41。
[0120] 如果队列C中当前保留的元素的全局代价值〉MinCost,则在步骤44中，对队列 C中保留的元素进行逐位遍历，逐位遍历产生的新元素入队。为了便于理解，图18给出了N=5，q〇=qi=…q4=6，XiG{0, 1，2, 3, 4, 5}，i=0, 1，…，4,队列C内保留的元素是（3, 3, 2, 0, 4} 的情形时，逐位遍历的结果。逐位遍历完成后，仍旧要根据全局代价值的大小对各行元素进 行排序，排序的原则同前所述，排序结果该里不再图示。此时指针仍指向编号为0的基站。 [012。 在上述各步骤中，如果当前运算次数达到最大运算次数，则保留队列C中当前尾 部一行元素，将其余元素出队，后续将W队列C中所保留的元素为该5个基站的小区分配的 最终PCI。
[0122] 上述实例中，需要配置的相关参数包括：队列C的长度M2。根据仿真测试经验，假 设基站个数是N，则队列C的长度M2=10N即可。检测流程的最大运算次数V，一般设置为 V=30N到50N即可。
[0123] 4、效果分析和适用范围
[0124] 本发明实施例提供的资源分配最优分配结果或近似最优分配结果的搜索遍历算 法的实质可描述为：
[0125]W二进制情形为例，假如所需遍历的二进制序列长度为4(该里可W理解为有4个 基站，每个基站有两种PCI排列组合的可能性)，则按照如图19所示的树形结构就可W在第 四级中将0000~1111的16种排列组合全部遍历出。本发明实施例提供的算法的实际内 涵就是在类似的树形结构上沿着某一个路径搜索最优解，如果方向不对的话，跳跃到树形 结构中的另一个节点继续搜索，即，在树形结构图中跳跃搜索。"跳跃"表示在队列中遍历一 种情况后按照全局代价值大小排序，如果队列尾部元素在排序前后发生改变，则就相当于 在树形结构中跳跃到另一个节点进行下一步的搜索。
[012引图19只是W二进制为例，即4个基站，每个基站有两种PCI排列组合情形（即每个 节点有2个分支）为例描述。不失一般性 ，针对一个长度为N的序列找。，X。…，XwJ，对于 Xi可能取值的个数为di，则可W构造一个每个节点分叉个数不同的树形结构。
[0127] 可W看出，本发明实施例综合了遗传算法中对部分次优解的保留（reservation) 的优点W及遍历树结构（图19)特点，但并不是遍历所有的可能性，而是只遍历其中的一部 分，目的是每遍历一次，就要朝最优解逼近一次，从而快速寻找最优解，而遗传算法并不能 保证每进化一次就能进化出比上一代更好的种群。
[012引 由此可见，发明实施例相对于遗传算法具有W下优点：
[0129] (1)运算速度快。在一定的运行环境下，对于3184个基站的情形，遗传算法需要大 约13~15个小时的时间复杂度去寻找最优分配结果，而本发明实施例需要约17分钟即可 寻找到最优分配结果，而且总体代价不高于遗传算法；
[0130] (2)得到的最终分配结果稳定。遗传算法每次运算到的结果很大概率都不相同，由 于是一种基于概率的搜索最优分配结果的过程，所W每次的分配结果都与当时选取他的概 率有关导致分配结果不稳定，而且不确定是否是最优分配结果，而本发明实施例每次得到 的分配结果都是相对固定的；
[0131] (3)搜索到的最小代价值不高于遗传算法的最小代价值。由于像遗传算法搜索到 的最小代价基本每次都不同，而本发明实施例搜索到的最小代价值都是相对固定的，并且 经过测试可W验证本发明实施例搜索到的最终分配结果的代价值不高于使用遗传算法搜 索到的最终分配结果的代价值。
[0132] 如前所述，本发明实施例提供的资源分配方案可适用于多种资源的分配场景。比 女口，在GSM(GlobalSystemforMobileCommunications,全球移动通信系统）频点分配 过程中，假设有N个待分配频点的小区，编号为0,…，N-1，M个可供分配的频点，编号为 f〇,…，fi-i并且N〉M，则频率重用不可避免。对于小区0至小区M-1，可W将片~山按顺序 分配，从小区M开始频率重化则对于小区M，M+1，…，N-1来说，每个小区至多都有M种频 点选择，遍历该M种情形，使该M个新元素进入队列计算代价值，然后按照代价值排序，一直 保持队尾的元素是全局代价值最小的，遍历树结构是每个节点产生M个分支。频点分配W 小区为单位。TD-SCDMA (Time Division-Sync虹onous Code Division Multiple Access, 时分同步码分多址)系统的频点分配过程的模型类似于GSM系统的频点分配模型，该里不再 费述。
[0133] 再比如，在TD-SCDMA系统的扰码分配过程中，假设有N个待分配扰码的小区，编号 为0,…，N-1，M个可供分配的扰码（M)，编号为S。，…，Sm_i，并且N〉M，则扰码重用不可避免。 对于小区0至小区M-1，可W将S。，…，Sm_i按顺序分配给小区，从小区M开始扰码重用，则从 小区M，M+1，…，N-1来说每个小区至多都有M种扰码选择，遍历该M种情形，使该M个新 元素进入队列计算代价值，然后按照代价值进行排序，一直保持队尾的元素是全局代价值 最小的，遍历树结构是每个节点产生M个分支。TD-SCDMA的扰码分配是W小区为单位进行 的。
[0134] 本发明实施例提供的上述各流程均可由软件编程方式实现。图20A~图20D分别 描述了由软件编程方式实现的资源分配装置的结构。
[0135] 如图20A所示，本发明实施例提供的资源分配装置可包括：
[0136] 初始化单元50,用于将N个目标对象的资源分配标识的初始值作为一行元素放入 第一队列，并设置所述N个目标对象的资源分配标识初始值对应的全局代价值为初始代价 值；其中，一个目标对象的一个资源分配标识用于标识该目标对象的所有可能的资源分配 方案中的一种，所述第一队列为M1XN的队列，N为队列的列数，N的取值为目标对象的数 量，Ml为队列的行数，Ml取值为队列的长度；
[0137] 第一搜索单元51，用于对所述第一队列执行遍历流程，所述遍历流程包括分别对 所述N个目标对象中的每个目标对象遍历所有的资源分配标识；
[013引分配单元52,用于在所述第一搜索单元完成所述遍历流程后，根据所述第一队列 尾部一行元素确定第一资源分配优选方案，所述第一资源分配优选方案中包含N个目标对 象的资源分配标识，根据所述第一资源分配优选方案为所述N个目标对象进行资源分配；
[0139] 其中，所述遍历流程中，第一搜索单元51针对第i个目标对象执行W下操作， 1《i《N，所述第i个目标对象为尚未分配资源的目标对象：
[0140] W队列尾部Q行元素为基础对第i个目标对象的所有资源分配标识进行遍历，得 到QiXQ行元素，所述QiXQ行元素中的每一行元素包含N个目标对象的资源分配标识，所 述为第i个目标对象的所有资源分配标识的数量，Q为正整数；
[0141] 将所述diXQ行元素放入队列，计算所述diXQ行元素中每一行对应的全局代价 值；
[0142] 根据每一行元素对应的全局代价值对所有行元素进行排序，使每一行元素对应的 全局代价值按照从队列头部到尾部的顺序依次降低。
[0143] 进一步地，本发明实施例提供的资源分配装置还可包括第二搜索单元53,如图 20B所示。第一搜索单元51还用于：若所述第一队列元素溢出，则从所述第一队列的尾部 开始将P行元素移至第二队列，P> 1，并在将所述P行移至所述第二队列后，继续执行所 述遍历流程。其中，第二队列的尺寸与第一队列相同，即第二队列的行数和列数分别与第一 队列的行数和列数相同。第二搜索单元53用于对所述第二队列执行所述遍历流程。相应 的，分配单元52在确定第一资源分配优选方案时，比较所述第一队列尾部一行元素的全局 代价值和所述第二队列尾部一行元素的全局代价值，根据两者中全局代价值最小的元素确 定第一资源分配优选方案。
[0144] 进一步地，图20B所述的装置中，第一搜索单元51还用于：若所述第一队列元素再 次溢出，则从所述第一队列的头部开始顺序删除至少一行元素；第二搜索单元53还用于： 若所述第二队列元素已溢出，则从所述第一队列的头部开始顺序删除至少一行元素。
[0145] 进一步地，图20A所述的装置中还可包括第H搜索单元54,如图20C所示；或者， 图20B所述的装置中还可包括第H搜索单元54,如图20D所示。
[0146] 图20C或图20D所示的装置中，第H搜索单元54,用于在分配单元52确定出第一 资源分配优选方案之后，根据所述第一资源分配优选方案执行验证流程，并在所述验证流 程结束后指示分配单元52根据所述验证流程的验证结果为所述N个目标对象进行资源分 配，所述验证结果中包含N个目标对象进行资源分配标识。其中，所述验证流程，包括：
[0147] 步骤a;将所述第一资源分配优选方案中的N个目标对象的资源分配标识作为一 行元素放入M2XN的第H队列，将第一变量的取值设置为所述第一资源分配优选方案对应 的全局代价值，然后转入步骤b;其中，M2为队列的行数，取值为所述第H队列的长度；
[014引步骤b;对所述第H队列执行所述遍历流程，然后转入步骤C;其中，当满足结束条 件时将所述第H队列尾部一行元素作为验证结果出队，并结束所述验证流程；
[0149] 步骤C;判断所述第H队列尾部一行元素对应的全局代价值是否小于所述第一变 量的取值，若是，则转入步骤d，否则转入步骤e;
[0150] 步骤d ;将所述第一变量设置为所述第H队列尾部一行元素对应的全局代价值， 然后转入步骤b;
[0151] 步骤e;对所述第H队列尾部一行元素中的每个目标对象遍历所有的资源分配标 识，并在遍历完成所有目标对象的资源分配标识后，将遍历结果放入所述第H队列，计算当 前入队的每一行元素对应的全局代价值，根据所述第H队列中的每行元素对应的全局代价 值对所述第H队列中的所有行元素进行排序，使所述第H队列中每一行元素对应的全局代 价值按照从所述第H队列的头部到尾部的顺序依次降低，然后转入步骤b;其中，当满足结 束条件时将所述第H队列尾部一行元素作为验证结果出队，并结束所述验证流程。
[0152] 进一步地，第H搜索单元54还用于：在所述步骤b完成之后在转入所述步骤C之 前，保留所述第H队列尾部一行元素，将其余行元素从所述第H队列移除。
[0153] 优选地，上述各装置中，所述目标对象为基站，所述资源分配标识为物理小区标识 PCI分配组合的编号，一个基站的所有小区的每种PCI分配组合使用唯一的编号进行标识， 所述为N个目标对象进行资源分配是指为N个基站分配PCI;或者，所述目标对象为小区， 所述资源分配标识为小区频点分配组合的编号，所述为N个目标对象进行资源分配是指为 N个小区分配小区频点；或者，所述目标对象为小区，所述资源分配标识为小区扰码分配组 合的编号，所述为N个目标对象进行资源分配是指为N个小区分配扰码。
[0154] 优选地，在所述目标对象为基站、所述资源分配标识为PCI组合的编号的情况下， 所述全局代价值可W根据前述公式（1)计算得到。
[0155] 综上所述，本发明的上述实施例中，由于在资源分配的过程中，分别对N个目标对 象中的每个目标对象遍历所有的资源分配标识(一个资源分配标识用于表示一种资源分配 选择的可能性)，并在遍历过程中，根据全局代价值对N个目标对象的遍历结果进行排序，从 而找到当前的较优分配结果，然后W该较优分配结果为基础对下一个目标对象的资源分配 标识进行遍历，W此类推，最终找到最优资源分配结果。由于每次对一个目标对象的资源分 配情况进行遍历，都是根据上一次遍历得到的较优分配结果为基础进行的，即，并不是遍历 N个目标对象的所有的资源分配可能性，而是遍历其中的一部分，目的是每遍历一次就朝最 分配结果逼近一次，从而可W快速寻找到资源分配的最优分配结果。
[0156] 本发明是参照根据本发明实施例的方法、设备（系统)、和计算机程序产品的流程 图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一 流程和/或方框、W及流程图和/或方框图中的流程和/或方框的结合。可提供该些计算 机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理 器，使得通过该计算机或其他可编程数据处理设备的处理器执行的指令可实现流程图中的 一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
[0157] 该些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备W特 定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指 令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或 多个方框中指定的功能。
[0158] 该些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计 算机或其他可编程设备上执行一系列操作步骤W产生计算机实现的处理，从而在计算机或 其他可编程设备上执行的指令提供用于实现在流程图的一个流程或多个流程和/或方框 图的一个方框或多个方框中指定的功能的步骤。
[0159] 尽管已描述了本发明的优选实施例，但本领域内的技术人员一旦得知了基本创造 性概念，则可对该些实施例作出另外的变更和修改。所W，所附权利要求意欲解释为包括优 选实施例W及落入本发明范围的所有变更和修改。
[0160] 显然，本领域的技术人员可W对本发明进行各种改动和变型而不脱离本发明的精 神和范围。该样，倘若本发明的该些修改和变型属于本发明权利要求及其等同技术的范围 之内，则本发明也意图包含该些改动和变型在内。
【主权项】
1. 一种资源分配方法，其特征在于，包括： 将N个目标对象的资源分配标识的初始值作为一行元素放入第一队列，并设置所述N 个目标对象的资源分 配标识初始值对应的全局代价值为初始代价值，其中，一个目标对象 的一个资源分配标识用于标识该目标对象的所有可能的资源分配方案中的一种，所述第一 队列为MlXN的队列，N为队列的列数，N的取值为目标对象的数量，Ml为队列的行数，Ml 取值为队列的长度； 对所述第一队列执行遍历流程，所述遍历流程包括分别对所述N个目标对象中的每个 目标对象遍历所有的资源分配标识； 所述遍历流程完成后，根据所述第一队列尾部一行元素确定第一资源分配优选方案， 所述第一资源分配优选方案中包含N个目标对象的资源分配标识，根据所述第一资源分配 优选方案为所述N个目标对象进行资源分配； 其中，所述遍历流程中，针对第i个目标对象执行以下操作，I < i < N，所述第i个目 标对象为尚未分配资源的目标对象： 以队列尾部Q行元素为基础对第i个目标对象的所有资源分配标识进行遍历，得到 IX Q行元素，所述IX Q行元素中的每一行元素包含N个目标对象的资源分配标识，所述 Qi为第i个目标对象的所有资源分配标识的数量，Q为正整数； 将所述Qi X Q行元素放入队列，计算所述Qi X Q行元素中每一行对应的全局代价值； 根据每一行元素对应的全局代价值对所有行元素进行排序，使每一行元素对应的全局 代价值按照从队列头部到尾部的顺序依次降低。2. 如权利要求1所述的方法，其特征在于，所述方法还包括： 若所述第一队列元素溢出，则从所述第一队列的尾部开始将P行元素移至第二队列， 分别对所述第一队列和所述第二队列执行所述遍历流程，所述第二队列的行数和列数与所 述第一队列相同，P彡1; 所述根据所述第一队列尾部一行元素确定第一资源分配优选方案，包括： 比较所述第一队列尾部一行元素的全局代价值和所述第二队列尾部一行元素的全局 代价值，根据两者中全局代价值最小的元素确定第一资源分配优选方案。3. 如权利要求2所述的方法，其特征在于，所述方法还包括： 若所述第一队列元素再次溢出，则从所述第一队列的头部开始顺序删除至少一行元 素；和/或， 若所述第二队列元素溢出，则从所述第二队列的头部开始顺序删除至少一行元素。4. 如权利要求1-3中任一项所述的方法，其特征在于，确定出第一资源分配优选方案 之后，还包括：根据所述第一资源分配优选方案执行验证流程； 所述根据第一资源分配优选方案为所述N个目标对象进行资源分配，包括：根据所述 验证流程的验证结果为所述N个目标对象进行资源分配，所述验证结果中包含N个目标对 象进行资源分配标识； 所述验证流程，包括： 步骤a :将所述第一资源分配优选方案中的N个目标对象的资源分配标识作为一行元 素放入M2XN的第三队列，将第一变量的取值设置为所述第一资源分配优选方案对应的全 局代价值，然后转入步骤b ;其中，M2为队列的行数，取值为所述第三队列的长度； 步骤b :对所述第三队列执行所述遍历流程，然后转入步骤C ;其中，当满足结束条件时 将所述第三队列尾部一行元素作为验证结果出队，并结束所述验证流程； 步骤C :判断所述第三队列尾部一行元素对应的全局代价值是否小于所述第一变量的 取值，若是，则转入步骤d，否则转入步骤e ; 步骤d :将所述第一变量设置为所述第三队列尾部一行元素对应的全局代价值，然后 转入步骤b ; 步骤e :对所述第三队列尾部一行元素中的每个目标对象遍历所有的资源分配标识， 并在遍历完成所有目标对象的资源分配标识后，将遍历结果放入所述第三队列，计算当前 入队的每一行元素对应的全局代价值，根据所述第三队列中的每行元素对应的全局代价值 对所述第三队列中的所有行元素进行排序，使所述第三队列中每一行元素对应的全局代价 值按照从所述第三队列的头部到尾部的顺序依次降低，然后转入步骤b ;其中，当满足结束 条件时将所述第三队列尾部一行元素作为验证结果出队，并结束所述验证流程。5. 如权利要求4所述的方法，其特征在于，所述方法还包括： 所述步骤b完成之后在转入所述步骤c之前，保留所述第三队列尾部一行元素，将其余 行元素从所述第三队列移除。6. 如权利要求1-3中任一项所述的方法，其特征在于，所述目标对象为基站，所述资源 分配标识为物理小区标识PCI分配组合的编号，一个基站的所有小区的每种PCI分配组合 使用唯一的编号进行标识，所述为N个目标对象进行资源分配是指为N个基站分配PCI ;或 者 所述目标对象为小区，所述资源分配标识为小区频点分配组合的编号，所述为N个目 标对象进行资源分配是指为N个小区分配小区频点；或者 所述目标对象为小区，所述资源分配标识为小区扰码分配组合的编号，所述为N个目 标对象进行资源分配是指为N个小区分配扰码。7. 如权利要求6所述的方法，其特征在于，在所述目标对象为基站、所述资源分配标识 为PCI组合的编号的情况下，所述全局代价值根据以下公式计算得到：其中，GlobalCost为全局代价值计算结果；m为天线方向图具有公共交叠覆盖区域的 小区对数量；PairCellC0Sti为第i个小区对的代价值，所述第i个小区对中的两个小区的 天线方向图具有公共覆盖交叠区域，i为正整数；ω i为PCI分配因子，若所述第i个小区对 中两个小区被分配的是模3相同的？(：1，则Coi=I,若所述第i个小区对中两个小区被分配 的是模3不相同的PCI，则ω「0。8. -种资源分配装置，其特征在于，包括： 初始化单元，用于将N个目标对象的资源分配标识的初始值作为一行元素放入第一队 列，并设置所述N个目标对象的资源分配标识初始值对应的全局代价值为初始代价值；其 中，一个目标对象的一个资源分配标识用于标识该目标对象的所有可能的资源分配方案中 的一种，所述第一队列为MlXN的队列，N为队列的列数，N的取值为目标对象的数量，Ml为 队列的行数，Ml取值为队列的长度； 第一搜索单元，用于对所述第一队列执行遍历流程，所述遍历流程包括分别对所述N 个目标对象中的每个目标对象遍历所有的资源分配标识； 分配单元，用于在所述第一搜索单元完成所述遍历流程后，根据所述第一队列尾部一 行元素确定第一资源分配优选方案，所述第一资源分配优选方案中包含N个目标对象的资 源分配标识，根据所述第一资源分配优选方案为所述N个目标对象进行资源分配； 其中，所述遍历流程中，所述第一搜索单元针对第i个目标对象执行以下操作， I < i < N，所述第i个目标对象为尚未分配资源的目标对象： 以队列尾部Q行元素为基础对第i个目标对象的所有资源分配标识进行遍历，得到 % X Q行元素，所述IX Q行元素中的每一行元素包含N个目标对象的资源分配标识，所述 Qi为第i个目标对象的所有资源分配标识的数量，Q为正整数； 将所述Qi X Q行元素放入队列，计算所述Qi X Q行元素中每一行对应的全局代价值； 根据每一行元素对应的全局代价值对所有行元素进行排序，使每一行元素对应的全局 代价值按照从队列头部到尾部的顺序依次降低。9. 如权利要求8所述的装置，其特征在于，还包括第二搜索单元； 所述第一搜索单元还用于：若所述第一队列元素溢出，则从所述第一队列的尾部开始 将P行元素移至第二队列，并在将所述P行移至所述第二队列后，继续执行所述遍历流程， 所述第二队列的行数和列数与所述第一队列相同，P > 1 ; 所述第二搜索单元，用于对所述第二队列执行所述遍历流程； 所述分配单元具体用于，比较所述第一队列尾部一行元素的全局代价值和所述第二队 列尾部一行元素的全局代价值，根据两者中全局代价值最小的元素确定第一资源分配优选 方案。10. 如权利要求9所述的装置，其特征在于，所述第一搜索单元还用于：若所述第一队 列元素再次溢出，则从所述第一队列的头部开始顺序删除至少一行元素； 所述第二搜索单元还用于：若所述第二队列元素已溢出，则从所述第二队列的头部开 始顺序删除至少一行元素。11. 如权利要求8-10中任一项所述的装置，其特征在于，还包括： 第三搜索单元，用于在所述分配单元确定出第一资源分配优选方案之后，根据所述第 一资源分配优选方案执行验证流程，并在所述验证流程结束后指示所述分配单元根据所述 验证流程的验证结果为所述N个目标对象进行资源分配，所述验证结果中包含N个目标对 象进行资源分配标识； 所述验证流程，包括： 步骤a :将所述第一资源分配优选方案中的N个目标对象的资源分配标识作为一行元 素放入M2 XN的第三队列，将第一变量的取值设置为所述第一资源分配优选方案对应的全 局代价值，然后转入步骤b ;其中，M2为队列的行数，取值为所述第三队列的长度； 步骤b :对所述第三队列执行所述遍历流程，然后转入步骤c ;其中，当满足结束条件时 将所述第三队列尾部一行元素作为验证结果出队，并结束所述验证流程； 步骤c :判断所述第三队列尾部一行元素对应的全局代价值是否小于所述第一变量的 取值，若是，则转入步骤d，否则转入步骤e ; 步骤d :将所述第一变量设置为所述第三队列尾部一行元素对应的全局代价值，然后 转入步骤b ; 步骤e :对所述第三队列尾部一行元素中的每个目标对象遍历所有的资源分配标识， 并在遍历完成所有目标对象的资源分配标识后，将遍历结果放入所述第三队列，计算当前 入队的每一行元素对应的全局代价值，根据所述第三队列中的每行元素对应的全局代价值 对所述第三队列中的所有行元素进行排序，使所述第三队列中每一行元素对应的全局代价 值按照从所述第三队列的头部到尾部的顺序依次降低，然后转入步骤b ;其中，当满足结束 条件时将所述第三队列尾部一行元素作为验证结果出队，并结束所述验证流程。12. 如权利要求11所述的装置，其特征在于，所述第三搜索单元还用于：在所述步骤b 完成之后在转入所述步骤c之前，保留所述第三队列尾部一行元素，将其余行元素从所述 第三队列移除。13. 如权利要求8-10中任一项所述的装置，其特征在于，所述目标对象为基站，所述资 源分配标识为物理小区标识PCI分配组合的编号，一个基站的所有小区的每种PCI分配组 合使用唯一的编号进行标识，所述为N个目标对象进行资源分配是指为N个基站分配PCI ; 或者 所述目标对象为小区，所述资源分配标识为小区频点分配组合的编号，所述为N个目 标对象进行资源分配是指为N个小区分配小区频点；或者 所述目标对象为小区，所述资源分配标识为小区扰码分配组合的编号，所述为N个目 标对象进行资源分配是指为N个小区分配扰码。14. 如权利要求13所述的装置，其特征在于，在所述目标对象为基站、所述资源分配标 识为PCI组合的编号的情况下，所述全局代价值根据以下公式计算得到：其中，GlobalCost为全局代价值计算结果；m为天线方向图具有公共交叠覆盖区域的 小区对数量；PairCellC0Sti为第i个小区对的代价值，所述第i个小区对中的两个小区的 天线方向图具有公共覆盖交叠区域，i为正整数；ω i为PCI分配因子，若所述第i个小区对 中两个小区被分配的是模3相同的？(：1，则Coi=I,若所述第i个小区对中两个小区被分配 的是模3不相同的PCI，则ω「Ο。
【专利摘要】本发明公开了一种资源分配方法及装置。本发明在资源分配的过程中，分别对N个目标对象中的每个目标对象遍历所有的资源分配标识（一个资源分配标识表示一种资源分配选择的可能性），并在遍历过程中，根据全局代价值对遍历结果进行排序，从而找到当前的较优分配结果，然后以该较优分配结果为基础对下一个目标对象的资源分配标识进行遍历，以此类推，最终找到最优资源分配结果。由于每次对一个目标对象的资源分配情况进行遍历，都是根据上一次遍历到的较优分配结果为基础进行的，即，并不是遍历N个目标对象的所有的资源分配可能性，而是遍历其中的一部分，目的是每遍历一次就朝最优分配结果逼近一次，从而可以快速寻找到资源分配的最优分配结果。
【IPC分类】H04W72/04
【公开号】CN104902573
【申请号】CN201410083500
【发明人】杨星
【申请人】电信科学技术研究院
【公开日】2015年9月9日
【申请日】2014年3月7日
【技术领域】
[0001] 本发明涉及无线通信领域，尤其涉及一种资源分配方法及装置。
【背景技术】
[0002] 在PCI(化ysicalCellIdentity,物理小区ID)规划中，要为每个小区分配一个 物理ID号。LTE(LongTermEvolution,长期演进）中有编号为0至503总共504个PCI 编号，可W为504个小区不重复地分配，如果小区个数大于504,则需要基于一定的准则对 该些PCI编号重复使用。PCI关系到CRS(Cel]_-specificReferenceSi即al,小区专属参 考信号）在LTE系统的一个子峽中所占频率资源的位置，两个PCI虽然不相等，但是如果该 两个PCI模3 (即PCI编号对3取模的结果值，其结果值范围限于集合{0, 1，2})相等，则对 应的两个小区的CRS信号就会处在相同的时间频率资源位置上，并且如果两个小区的天线 方向图存在公共覆盖的交叠区域，则该两个小区的CRS信道就会相互产生干扰，称之为模3 冲突。
[000引 PCI规划所要解决的核也问题就是；为网络中的所有小区恰当的分配PCI编号，最 终在网络中尽最大可能为所有位于不同基站且天线方向图存在公共交叠覆盖区域的小区 对(两个小区)，分配模3不等的PCI,该样两个小区的公共交叠覆盖区域的CRS信号之间就 不会相互干扰。
[0004]目前，业界利用遗传算法寻找PCI规划的最优分配结果。用遗传算法进行PCI规 划的流程一般是：
[0005] 第一步：定义一个代价函数，表征天线主瓣方向的对齐程度，对齐程度越强，代价 函数值越高。W下图1至图3表示天线主瓣对齐程度，其中，图1表示天线主瓣最为对齐 的情况，直观描述为两个天线主瓣的角平分线在同一直线上，此种情况代价函数值最高，在 PCI规划时，对该两个小区应该分配模3不同的PCI编号；图2是两个小区天线主瓣没有 正对齐，但是指向同一侧，存在部分公共覆盖交叠区域，代价函数值相对于图1的情况小一 些；图3同样是两个小区的天线主瓣方向没有正对齐的情况，两者是指向异侧，仍然存在部 分公共交叠覆盖区域，代价函数值相对图1也要小一些；
[0006] 第二步：确定问题的规模，设置染色体序列，再使用遗传算法寻找最优分配结果。 假设有N个基站，每个基站有3个小区，则对所有基站分配PCI编号的全部排列组合数为护 种，遗传算法通过确定种群规模、种群个数，W及选择运算中的选择比例、交叉运算中的交 叉概率、变异运算中的变异概率等输入参数，对染色体序列进行变异交叉等运算，从该护种 排列中寻找到全局代价值最小的PCI分配染色体序列。遗传算法的流程如图4所示。
[0007] 遗传算法应用于PCI规划时会存在W下较为显著的问题；当待规划的基站数量很 多时遗传算法寻优速度非常慢。比如，对于3184个基站的情况，要大约17个小时才能找到 一个分配结果，如果有5000个基站，使用遗传算法进行PCI规划的时间还会更长。
【发明内容】
[000引本发明实施例提供了一种资源分配方法及装置，用w快速进行资源分配。
[0009] 本发明实施例提供的资源分配方法，包括：
[0010] 将N个目标对象的资源分配标识的初始值作为一行元素放入第一队列，并设置所 述N个目标对象的资源分配标识初始值对应的全局代价值为初始代价值，其中，一个目标 对象的一个资源分配标识用于标识该目标对象的所有可能的资源分配方案中的一种，所述 第一队列为MlXN的队列，N为队列的列数，N的取值为目标对象的数量，Ml为队列的行数， Ml取值为队列的长度；
[0011] 对所述第一队列执行遍历流程，所述遍历流程包括分别对所述N个目标对象中的 每个目标对象遍历所有的资源分配标识；
[0012] 所述遍历流程完成后，根据所述第一队列尾部一行元素确定第一资源分配优选方 案，所述第一资源分配优选方案中包含N个目标对象的资源分配标识，根据所述第一资源 分配优选方案为所述N个目标对象进行资源分配；
[0013] 其中，所述遍历流程中，针对第i个目标对象执行W下操作，1《i《N，所述第i 个目标对象为尚未分配资源的目标对象：
[0014]W队列尾部Q行元素为基础对第i个目标对象的所有资源分配标识进行遍历，得 到QiXQ行元素，所述QiXQ行元素中的每一行元素包含N个目标对象的资源分配标识，所 述di为第i个目标对象的所有资源分配标识的数量，Q为正整数；
[0015] 将所述diXQ行元素放入队列，计算所述ciiXQ行元素中每一行对应的全局代价 值；
[0016] 根据每一行元素对应的全局代价值对所有行元素进行排序，使每一行元素对应的 全局代价值按照从队列头部到尾部的顺序依次降低。
[0017] 本发明实施例提供的资源分配装置，包括：
[0018] 初始化单元，用于将N个目标对象的资源分配标识的初始值作为一行元素放入第 一队列，并设置所述N个目标对象的资源分配标识初始值对应的全局代价值为初始代价 值；其中，一个目标对象的一个资源分配标识用于标识该目标对象的所有可能的资源分配 方案中的一种，所述第一队列为M1XN的队列，N为队列的列数，N的取值为目标对象的数 量，Ml为队列的行数，Ml取值为队列的长度；
[0019] 第一搜索单元，用于对所述第一队列执行遍历流程，所述遍历流程包括分别对所 述N个目标对象中的每个目标对象遍历所有的资源分配标识；
[0020] 分配单元，用于在所述第一搜索单元完成所述遍历流程后，根据所述第一队列尾 部一行元素确定第一资源分配优选方案，所述第一资源分配优选方案中包含N个目标对象 的资源分配标识，根据所述第一资源分配优选方案为所述N个目标对象进行资源分配；
[0021] 其中，所述遍历流程中，所述第一搜索单元针对第i个目标对象执行W下操作， 1《i《N，所述第i个目标对象为尚未分配资源的目标对象：
[0022] W队列尾部Q行元素为基础对第i个目标对象的所有资源分配标识进行遍历，得 到QiXQ行元素，所述QiXQ行元素中的每一行元素包含N个目标对象的资源分配标识，所 述di为第i个目标对象的所有资源分配标识的数量，Q为正整数；
[0023] 将所述diXQ行元素放入队列，计算所述ciiXQ行元素中每一行对应的全局代价 值；
[0024] 根据每一行元素对应的全局代价值对所有行元素进行排序，使每一行元素对应的 全局代价值按照从队列头部到尾部的顺序依次降低。
[0025] 本发明的上述实施例中，由于在资源分配的过程中，分别对N个目标对象中的每 个目标对象遍历所有的资源分配标识(一个资源分配标识用于表示一种资源分配选择的可 能性)，并在遍历过程中，根据全局代价值对N个目标对象的遍历结果进行排序，从而找到当 前的较优分配结果，然后W该较优分配结果为基础对下一个目标对象的资源分配标识进行 遍历，W此类推，最终找到最优资源分配结果。由于每次对一个目标对象的资源分配情况进 行遍历，都是根据上一次遍历得到的较优分配结果为基础进行的，即，并不是遍历N个目标 对象的所有的资源分配可能性，而是遍历其中的一部分，目的是每遍历一次就朝最分配结 果逼近一次，从而可W快速寻找到资源分配的最优分配结果。
【附图说明】
[0026]为了更清楚地说明本发明实施例中的技术方案，下面将对实施例描述中所需要使 用的附图作简要介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本 领域的普通技术人员来讲，在不付出创造性劳动性的前提下，还可W根据该些附图获得其 他的附图。
[0027] 图1为天线主瓣正对齐的示意图；
[0028] 图2为天线主瓣同侧部分对齐的示意图；
[0029] 图3为天线主瓣异侧部分对齐的示意图；
[0030] 图4为现有技术中遗传算法流程示意图；
[0031] 图5本发明实施例中的天线方向图代价定义示意图；
[0032] 图6为天线方向图完全不对齐的示意图；
[0033] 图7为本发明实施例中的资源分配流程示意图；
[0034] 图8为图7中的步骤20的实现流程示意图；
[00巧]图9为本发明实施例中队列初始化示意图；
[0036] 图10为遍历0号基站对应的各种PCI组合的可能性的示意图；
[0037] 图11为遍历1号基站对应的各种PCI组合的可能性的示意图；
[0038] 图12为图11排序后的队列示意图；
[0039] 图13为遍历2号基站对应的各种PCI组合的可能行的示意图；
[0040] 图14A、图14B分别为本发明实施例提供的验证流程示意图；
[0041] 图15为本发明实施例中验证流程的初始化示意图；
[0042] 图16为基于图15的对0号基站的遍历不;意图；
[0043] 图17为对图16所示的遍历结果进行排序的示意图；
[0044] 图18为本发明实施例中逐位遍历的示意图；
[0045] 图19为本发明实施例中二进制遍历树的结构示意图；
[0046] 图20A、图20B、图20C、图20D分别为本发明实施例中的资源分配装置的结构示意 图。
【具体实施方式】
[0047] 本发明实施例可应用于为小区分配PCI的场景中，还可应用于其他资源（比如时 间资源、频率资源、空间资源、编码域资源(扰码）等）分配或资源规划场景中，比如，为小区 分配频点，或者为小区分配扰码等等。其中，对于被分配的资源的各种分配方案，本发明实 施例中用"资源分配标识"进行区分，对于资源分配的对象，本发明实施例中用"目标对象" 来表示。比如，在为小区分配PCI的场景中，一个"目标对象"即为一个基站(实际为一个基 站下的所有小区)，一个"目标对象"的"资源分配标识"代表一个基站下的所有小区的所有 可能的PCI排列组合中的一种；再比如，在为小区分配频点的场景中，一个"目标对象"即为 一个小区，一个"目标对象"的"资源分配标识"代表一个小区的所有可分配的频点中的一 个。
[0048] 本发明实施例提供的资源分配流程利用计算机数据结构中的队列结构对队列 中的元素进行遍历的过程来实现。该里所说的"队列"是指多元素集合，比如先进先出 (First-In-First-Out，FIFO)的线性表，也可W是数组（Array)或其他类似数据结构。
[0049] W下实施例中均使用队列来实现资源分配过程，队列的长度用行数来表示，每一 行称为一个元素，每行元素均为长度为N的序列，N为目标对象的数量，即，队列的列数为N。 另外，本发明实施例中约定，只允许在队列尾部(称为rear)进行元素插入操作（即入队操 作)，在头部(称为化ont)进行元素删除操作（即出队操作)。
[0050] 所谓遍历（Traversal),是指沿着某条搜索路线，依次对树形结构中的每个节点均 做一次且仅做一次访问。访问节点所做的操作依赖于具体的应用问题，比如在本发明实施 例所适用的资源分配场景中，对于遍历结果需要进行入队、计算代价值等操作。
[0051] 1、代价定义
[0052] 利用队列进行资源分配的过程，即为利用队列对各种可能的资源分配方案进行遍 历，并根据资源分配的代价值寻找各种可能的资源分配方案中的最优分配结果或近似最优 分配结果的过程。资源分配的代价值越低，则对应的资源分配方案越接近最优。
[005引 WPCI分配为例，假设有N个基站，编号为0, 1，…N-1，对于第i个基站有Ki个小 区，第i个基站中所有小区可W分配PCI的全部排列组合数为di个，则对网络内全部N个 基站分配PCI的所有组合数为
其中，n为连乘运算符号。
[0054] 队列中的每一行元素对应一个全局代价值。全局代价值的计算公式可由公式（1) 给出：
[00巧]
[0056]其中，GlobalCost表示全局代价值；M是所有具有公共交叠覆盖区域的小区对； Ui是PCI分配因子，如果天线方向图具有公共覆盖交叠区域的第i个小区对中两个小区 分配的是模3相同的PCI编号，则《 1=1，表示该两个小区的CRS信号之间存在相互干扰， 如果第i个小区对中两个小区分配的是模3不同的PCI编号，则《 1=0,表示该两个小区 CRS信号之间不存在相互干扰；PairCellCosti表示第i个小区对中两个小区之间的代价， PairCellCosti〉0 (化irCellCost与《取值与否无关，只与两个小区的天线方向图存在公 共交叠覆盖区域的大小有关)。一个小区对中两个小区间的代价的定义随后给出。
[0057] PCI规划的目的是使GlobalCost尽量小，如果所有的ui均为0,则GlobalCost=0， 即整个网络中所有小区都没有PCI编号模3冲突的情况，但是一般情况是并不可能所有的 ?i为0,因为有可能存在超过3个小区的情形具有公共覆盖交叠区域，该样就不可避免的 存在PCI编号模3相等的天线方向图具有公共交叠覆盖区域的小区对，利用搜索算法搜索 到的PCI分配方案的最优结果应该是使得尽量多的且较大的化irCellCosti对应的（〇1=0。
[0058] -个小区对中两个小区之间的代价一般是指，如果将该两个小区的PCI编号模3 相等，贝ij需要为该两个小区的CRS信号的SINR(Si即altoInte;rferenceNoiseRatio,信 干噪比）的恶化付出的代价，该种代价值可W根据实测数据，也可W根据天线方向图的地理 方位计算。
[0059] 从实测数据角度来考虑，两个小区之间会存在一个切换带区域，通过计算机静态 系统仿真可将规划区域进行栅格化处理(栅格就是边长为20米或其他长度数值的正方形 区域)，两个小区的切换带中包含的栅格数目就可W表示该两个小区构成的小区对所对应 的代价值。
[0060] 从天线方向图地理方位角度来考虑，主要是从几何的角度看两个天线方向图公共 覆盖区域面积的大小，即从视觉角度定义图1至图3情形所对应的代价。本发明实施例给 出了一种优选方式：将小区天线方向图主瓣的角平分线作为天线方向图的方向向量，长度 为单位1，则两个小区天线方向角对齐程度的代价可W由两个单位长度的方向向量端点的 欧氏距离的远近表示，如图5中的端点A和端点B之间的欧氏距离即为小区1和小区2的 成对小区的代价值，表示为：
[0061]
[0062] 根据公式（2)，如果两个小区天线方向图如图1所示的正对齐，则 PairCellCost=4,如果两个小区的天线方向图如图6所示正好相反，即完全不对齐，此时两 个天线方向图的单位方向向量距离最远，PairCellCost=0。
[0063] 2、资源分配过程
[0064] 下面W目标对象数量为N、利用列数为N的队列进行资源分配为例，结合图7描述 资源分配流程。
[0065] 参见图7,为本发明实施例提供的资源分配流程100的示意图，该流程可包括：
[0066] 步骤10 ;将N个目标对象的资源分配标识的初始值作为一行元素放入第一队列， 该初始值表征N个目标对象尚未分配资源，在资源分配的后续流程中资源分配标识初始值 将被具体资源分配方案对应的资源分配标识值替换掉。步骤10中，还设置所述N个目标对 象的资源分配标识对应的全局代价值为初始代价值，本实施例中优选地将初始代价值设置 为0,表示尚未进行资源分配。该第一队列为M1XN的队列，Ml为队列的行数也即队列长 度，N为队列的列数。
[0067] 步骤20 ;对所述第一队列执行遍历流程，所述遍历流程包括：分别对所述N个目标 对象中的每个目标对象遍历所有的资源分配标识。
[0068] 步骤30 ;所述遍历流程完成后，根据所述第一队列尾部一行元素确定第一资源分 配优选方案，所述第一资源分配优选方案中包含N个目标对象的资源分配标识，根据所述 第一资源分配优选方案为所述N个目标对象进行资源分配。
[0069] 针对步骤20的实现过程，图8示出了一种优选实现方式。在图8所示的流程200 中，按照从第一个目标对象到最后一个目标对象的顺序，依次对N个目标对象中的每个目 标对象遍历所有的资源分配标识。在依次对所述N个目标对象中的每个目标对象遍历所有 的资源分配标识的过程中，针对每个目标对象执行基本相同的操作，W针对第i(l《i《N) 个目标对象(该目标对象尚未分配资源)为例，执行W下操作；W队列尾部Q(Q> 1)行元素 为基础对第i个目标对象的所有资源分配标识进行遍历，得到diXQ行元素，所述QiXQ行 元素中的每一行元素包含N个目标对象的资源分配标识，所述di为第i个目标对象的所有 资源分配标识的数量(步骤23 );将所述QiXQ行元素放入队列的尾部，计算所述QiXQ行元 素中每一行对应的全局代价值(步骤24);根据队列中的每一行元素对应的全局代价值对队 列中的所有行元素进行排序，使队列中每一行元素对应的全局代价值按照从队列的头部到 尾部的顺序依次降低(步骤25)。其中，全局代价值的大小表明对应的资源分配方案距离最 优资源分配方案的远近程度，全局代价值越小，则对应的资源分配方案越接近最优。
[0070] 在步骤20中，在针对第i(1《i《N)个目标对象遍历该目标对象的所有的资源 分配标识时，可队列当前尾部的一行或多行元素为基础进行遍历。
[0071] 在W队列当前尾部的一行元素为基础进行遍历时（即此时Q=0,保持该行元素中 除第i个目标对象W外的N-1个目标对象对应的资源分配标识不变，即遍历得到的Qi行元 素中，第i个目标对象的资源分配标识各不相同，而其他目标对象的资源分配标识均保持 不变。通过该种方式，在对第i个目标对象的资源分配标识进行遍历时，W第i-1个目标对 象的遍历结果中代价值最小的一行元素为基础进行，即每次遍历W上一次遍历得到的最优 分配结果为基础进行，最优分配结果总是在队列尾部，从而可W快速逼近最优分配结果。
[0072] 考虑到每次资源分配遍历过程中，队列尾部的元素只是暂时性的最优分配结果， 由于资源尚未分配完毕，并不表示其就是最终的最优分配结果，因此每次仅选取队列尾部 一行元素为基础进行遍历，则对代价值次小或者次次小的其他行元素来说不公平，即有可 能导致寻找到的最终结果不一定是最优分配结果。即使遍历结果中的最优分配结果仅有一 个，也会出现类似问题。为了尽量使最终结果逼近最优分配结果，对第i个目标对象的资源 分配标识进行遍历时，可第i-1个目标对象（即前一个目标对象）的遍历结果中的多个 较优的分配结果为基础进行遍历。
[0073] 在W第一队列当前尾部的Q行元素为基础进行遍历时（即此时Q〉l)，可W针对其 中的每行元素按照如上方式进行遍历，即；针对每行元素，保持该行元素中除第i个目标对 象W外的N-1个目标对象对应的资源分配标识不变，即遍历得到的Qi行元素中，第i个目 标对象的资源分配标识各不相同，而其他目标对象的资源分配标识均保持不变。通过该种 方式，在对第i个目标对象的资源分配标识进行遍历时，W前一次遍历得到的多个较优的 分配结果为基础进行，从而可W-方面快速逼近最优分配结果，另一方面尽量保证最终寻 找到的分配结果为最优分配结果。
[0074] 考虑到如果该Q行元素中至少有两行元素满足如下条件；前一个被遍历的目标对 象巧日第i-1个目标对象）对应的资源分配标识相同，则会导致重复遍历。针对该种情况， 优选地，可针对满足上述条件的两行或两行W上元素，取其中代价值最小（即最靠近队列尾 部）的一行元素作为基础，对第i个目标对象的所有的资源分配标识进行遍历。
[007引通过流程100可W看出，由于在资源分配的过程中，利用队列结构依次对N个目标 对象中的每个目标对象遍历所有的资源分配标识(一个资源分配标识用于表示一种资源分 配方案)，并在遍历过程中，根据全局代价值对N个目标对象的遍历结果进行排序，从而找到 当前的较优分配结果，然后W该较优分配结果为基础对下一个目标对象的资源分配标识进 行遍历，W此类推，最终找到资源分配的最优分配结果。由于每次对一个目标对象的资源分 配情况进行遍历，都是根据上一次遍历得到的较优分配结果为基础进行的，即，并不是遍历 所有可能的资源分配方案，而是遍历其中的一部分，目的是每遍历一次就朝最优分配结果 逼近一次，从而可W快速寻找到资源分配的最优分配结果或近似最优分配结果。
[0076] 图8所示的流程200是按照目标对象的编号从小到大的顺序对目标对象进行遍历 的，事实上，目标对象的遍历顺序不止该种情况，还可W从大到小，或者约定的其他顺序，只 要保证可W遍历到所有的目标对象即可。
[0077] 考虑到如果目标对象或待分配资源的数量较多，则有可能在步骤20的执行过程 中，第一队列已满或队列溢出，本发明实施例针对该种情况还提供了W下解决方案：当第一 队列已满或队列溢出时，从第一队列的头部开始顺序移除P(P> 1)行元素，即，将P行元 素出队。P值可预先设置，P值的大小可根据目标对象或待分配资源的数量W及系统处理性 能等因素进行设置。
[0078] 优选地，为了尽可能得到最优分配结果，本发明实施例还提供了W下优选方案：
[0079] 当第一队列已满或队列溢出时，将从第一队列出队的P行元素放入第二队列，分 别对第一队列和第二队列执行步骤20的流程。相应的，在步骤30中，比较第一队列尾部一 行元素的全局代价值和第二队列尾部一行元素的全局代价值，根据两者中全局代价值最小 的元素确定第一资源分配优选方案，根据所述第一资源分配优选方案为所述N个目标对象 进行资源分配。第二队列的尺寸与第一队列相同，即第二队列的行数和列数分别与第一队 列的行数和列数相同。
[0080] 在上述优选方案中，如果第一队列元素再次发生溢出，则可从第一队列的头部开 始顺序删除P1 (P1>1)行元素。同理，如果第二队列元素发生溢出，则可从第二队列的头 部开始顺序删除P2 (P2 > 1)行元素。P1和P2可相等也可不相等，具体取值大小可预先设 置。
[0081] 为了更清楚地对流程100进行说明，下面W为N个基站下覆盖的小区分配PCI为 例，描述流程100的具体实现过程。
[0082] 在步骤10中，进行队列的初始化操作。创建一个M1XN的队列a,其中，N为队列 a的列数，取值为基站的数量，Ml为队列的行数，也即队列a的长度。将N个基站中每个基 站对应的资源分配标识初始化为-1，表示N个基站均未被分配PCI，将每个基站对应的资源 分配标识的初始值作为一行元素入队，将该行元素对应的初始全局代价值设置为0。该队列 a可W理解为一个MlXN的二维数组，每次进入队列a的都是一个1XN的向量，是队列a的 元素，横坐标为基站的编号，纵坐标为资源分配标识，一个资源分配标识代表一个基站的一 种PCI组合。为了便于理解，图9示出了一个N=5,即5个基站的例子。
[008引在步骤20中，从编号为0的基站开始，依次遍历每个基站的所有PCI组合的编号， 直到编号为4的基站分配好PCI组合的编号为止。
[0084] 首先，对编号为0的基站（即第一个基站）的所有可能分配的PCI排列组合进行遍 历，即对0号基站可能分配的PCI的q。种可能进行遍历，并且遍历过后产生的新元素入队。 为了便于理解，图10给出了N=5,可分配PCI数量为3 (PCI=0, 1，2)，也=6的情况，即0号基 站有3个小区，共有6种PCI分配的可能性的遍历结果，该6种PCI分配的可能性包括：
[00财第一种可能性（PCI组合的编号等于0);小区1的PCI=0,小区2的PCI=1，小区3 的PCI=2 ;
[00 8引第二种可能性（PCI组合的编号等于1);小区1的PCI=0,小区2的PCI=2,小区3 的PCI=1 ;
[0087] 第H种可能性（PCI组合的编号等于2);小区1的PCI=1，小区2的PCI=0,小区3 的PCI=2 ;
[008引第四种可能性（PCI组合的编号等于3);小区1的PCI=1，小区2的PCI=2,小区3 的PCI=0 ;
[0089] 第五种可能性（PCI组合的编号等于4);小区1的PCI=2,小区2的PCI=0,小区3 的PCI=1 ;
[0090] 第六种可能性（PCI组合的编号等于5);小区1的PCI=2,小区2的PCI=1，小区3 的PCI=0。
[0091] 此时只给0号基站的小区分配了PCI,而其他基站还没有分配，所W对于该6种排 列组合，各个行元素对应的全局代价值仍旧为0。
[0092] 然后，对1号基站的所有ql种可能分配的PCI组合情况进行遍历，遍历产生的新 元素入队。为了便于理解，图11给出了N=5, 9。=屯=6的情形。
[0093] 此时队列a中已经有两个或两个W上基站的小区分配了PCI,可W计算出全局代 价值，即已经分配了PCI的基站参与全局代价的计算，分配了PCI的小区，如果构成成对邻 区关系，即存在化irCellCost值。如果该两个小区分配了模3相同的PCI编号，则该小区 对对应的《=1，如果分配了模3不同的PCI编号，则该小区对对应的《=0。图11的C。~Q 表示对1号基站遍历得到的6行元素对应的全局代价值。全局代价的计算方法同前所述， 在此不再重复。
[0094] 然后，根据全局代价值对队列a中的所有行元素进行排序，排序后的队列a从头部 到尾部，各元素对应的全局代价值依次减小。由于队列头部的5行元素的全局代价值仍旧 为初始代价，即为0,所W队列头部元素通过排序有可能排到队列尾部，排列后的一个可能 情形如图12所示。
[0095] 接下来对编号为2的基站的各种PCI分配情况进行遍历，遍历产生的新元素入队， 新入队的元素的全局代价值为Ce~。1，然后按照全局代价值对队列a中的所有元素进行排 序。为了便于理解，图13给出了N=5,听屯=屯=6的情形，即共有5个基站，基站0、基站1和 基站2都是有3个小区，共有3个PCI可供分配（PCI=0,1，2)，所W每个基站有6种PCI分 配的可能性。
[0096] 按照前述方式，依次对编号为3的基站W及编号为4的基站进行遍历。当对编号 为4的基站遍历完成之后，队列尾部的元素为全局代价值最小的元素，将该元素出队。
[0097] 在步骤20的流程中，如果还未遍历到最后一个基站，但是队列a已满或者溢出，贝U 可将一部分元素（比如P行元素，P> 1)出队。此后继续执行遍历过程，直至最后一个基站 被遍历。优选地，将P行元素出队后，保留在第一队列中的元素行数（M1-P)至少大于1，保 留的元素行数越多，得到的分配结果越接近最优分配结果，可根据此原则来确定P的取值。
[009引优选地，当队列已满或者溢出时，将P行元素出队后，将该将P行元素放入队列b中。然后，分别对该两个队列执行步骤20的过程，直到该两个队列最终将全局代价值最小 的元素出队。相应的，在步骤30中，取该两个队列最终出队的元素中全局代价值最小的元 素，根据该元素为相应基站的小区分配PCI。
[0099]上述实例中，需要配置的相关参数包括：队列a的长度为Ml，队列a中元素个数超 过Ml后出队元素个数为P。根据仿真测试经验，假设基站个数是N，则队列a的长度M1=30N 至IJ50N之间。队列a满了或者有溢出时，假设此时队列中的元素个数为U个，则出队的元素 个数P=U-M1+1，即队列a内保留元素的个数比队列长度少一个即可，因为一次不能删除太 多备选元素，W最大可能性保证最优分配结果不被删除出队。
[0100] 3、验证流程
[0101] 由于上述资源分配流程中，并未像极大似然算法那样对所有可能的资源分配方案 进行一一遍历，所W并不能完全保证得到的结果是全局最优分配结果。为了尽量使最终得 到的资源分配方案逼近全局最优分配结果，本发明实施例优选地还提供了根据上述资源分 配流程得到的资源分配优选方案进行进一步验证的流程。目P，在确定出上述第一资源分配 优选方案之后，还可进一步根据该第一资源分配优选方案执行验证流程。相应的，在进行资 源分配时，根据验证流程的验证结果为所述N个目标对象进行资源分配。
[0102] 参见图14A，为本发明实施例提供的验证流程300示意图，如图所示，该流程主要 包括：
[0103] 步骤40;将通过流程100或其优选方案得到的第一资源分配优选方案（即最优分 配结果)中的N个目标对象的资源分配标识作为一行元素放入M2 XN的第H队列，将第一变 量（图中示为MinCost)的取值设置为第一资源分配优选方案对应的全局代价值，然后转入 步骤41。其中，M2为队列的行数，取值为所述第H队列的长度。
[0104] 步骤41 ;对所述第H队列执行遍历流程(该遍历流程的具体实现过程同前所述， 比如可参照遍历流程200)。比如，从第1个目标对象开始，W队列尾部的一行或多行元素为 基础遍历目标对象的所有资源分配标识，直到第N个目标对象为止。遍历流程执行完成后， 即对N个目标对象的资源分配标识遍历完成，此时转入步骤42。
[0105] 进一步地，在步骤41的执行过程中，若满足结束条件，则将所述第H队列尾部一 行元素作为验证结果出队，并结束验证流程300。
[0106] 步骤42;判断所述第H队列尾部一行元素对应的全局代价值是否小于所述第一 变量（图中示为MinCost)的取值，若是，则转入步骤43,否则转入步骤44。
[0107] 步骤43 ;将所述第一变量（图中示为MinCost)设置为所述第H队列尾部一行元素 对应的全局代价值，然后转入步骤41 ;
[0108] 步骤44 ;对所述第H队列尾部一行元素中的每个目标对象遍历所有的资源分配 标识，并在遍历完成所有目标对象的资源分配标识后，将遍历结果放入所述第H队列，计算 当前入队的每一行元素对应的全局代价值，根据所述第H队列中的每行元素对应的全局代 价值对所述第H队列中的所有行元素进行排序，使所述第H队列中每一行元素对应的全局 代价值按照从所述第H队列的头部到尾部的顺序依次降低，然后转入步骤41。
[0109] 进一步地，在步骤44的执行过程中，若满足结束条件，则将所述第H队列尾部一 行元素作为验证结果出队，并结束验证流程300。
[0110] 优选地，为了减少运算开销、提高运算效率，步骤41完成之后在转入步骤42之前， 可只保留第H队列尾部一行元素，将其余行元素出队。
[0111] 优选地，当步骤41或步骤44的执行过程中，第H队列已满或溢出时，保留第H队 列尾部一行元素，将其余行元素出队后，继续执行后续流程。该优选方案的流程可参见图 14B所示的流程400,相关步骤的具体实现可参见流程300,在此不再重复。
[0112] 上述流程300和流程400中的所述结束条件可W是；当前运算次数达到最大运算 次数。可W将从第一个到第N个目标对象的完整遍历过程定义为一次运算，也可W将对一 个目标对象的完整遍历过程定义为一次运算，本发明实施例对此不做限制。另外，结束条件 的定义也不仅W运算次数为依据，比如还可运算时间为依据或者多种因素相结合来考 虑，本发明实施例对此也不做限制。
[0113] 为了更清楚地对流程300进行说明，下面继续W上述为5个基站的小区分配PCI 的场景为例，描述流程300的具体实现过程。
[0114] 当利用队列a或者利用队列a和队列b执行遍历流程后，得到最终分配结果记为 找〇，X。…Xn_i}，其中，XiG{0, 1，…屯-1}，1=0, 1，…N-1，即第i个基站分配到的PCI的组合 编号的索引为Xi，该最终分配结果的全局代价为C。。
[0115] 在步骤40中，将该最终分配结果进入队列C。设置一个指针，该指针指向当前 待遍历的基站，设置并初始化一个变量MinCost=C。。为了方便理解，图15给出了N=5， q〇=qi=...94=6,XiG{0, 1，2, 3, 4, 5}，i=0, 1，…，4的情形，目P共有5个基站，每个基站有3个 小区，每个基站有6种分配PCI的排列组合数，通过执行流程100后得到的最终分配结果为 {3,5,2,0,4}。
[0116] 在步骤41中，首先对编号为0的基站的所有PCI排列组合情况进行遍历，遍历产 生的新元素入队，并计算该些新元素的全局代价值。由于编号为0的基站遍历完毕后，将 指针指向编号为1的基站。为方便理解，图16给出了继图15W后的遍历结果，其中，N=5， q〇=qi=...94=6,X;G{0, 1，2, 3, 4, 5}，i=0, 1，…，4,入队的新元素代价分别为C〇~C日。按照 全局代价值从大到小排序，针对图16,排序过后的可能情形如图17所示。
[0117] W此类推，通过步骤41，从编号为0的基站开始到编号为4的基站为止，对各基站 的PCI排列组合情况进行遍历。在当前指针指向编号为4的基站，并且完成对该基站的各 种PCI排列组合情况的遍历后，保留队列C中队尾一行的元素在队列中，将其他元素出队， 并且将指针指向编号为0的基站，然后转入步骤42。
[011引如果在步骤41的执行过程中，队列C已满或者已经溢出，则保留队列C中队尾一 行的元素在队列中，将其他元素出队，并且将指针指向编号为0的基站，然后转入步骤42。
[0119] 如果队列C中当前保留的元素的全局代价值〈MinCost，则在步骤43中，更新 MinCost为队列C中当前保留的元素的全局代价值，然后转入步骤41。
[0120] 如果队列C中当前保留的元素的全局代价值〉MinCost,则在步骤44中，对队列 C中保留的元素进行逐位遍历，逐位遍历产生的新元素入队。为了便于理解，图18给出了N=5，q〇=qi=…q4=6，XiG{0, 1，2, 3, 4, 5}，i=0, 1，…，4,队列C内保留的元素是（3, 3, 2, 0, 4} 的情形时，逐位遍历的结果。逐位遍历完成后，仍旧要根据全局代价值的大小对各行元素进 行排序，排序的原则同前所述，排序结果该里不再图示。此时指针仍指向编号为0的基站。 [012。 在上述各步骤中，如果当前运算次数达到最大运算次数，则保留队列C中当前尾 部一行元素，将其余元素出队，后续将W队列C中所保留的元素为该5个基站的小区分配的 最终PCI。
[0122] 上述实例中，需要配置的相关参数包括：队列C的长度M2。根据仿真测试经验，假 设基站个数是N，则队列C的长度M2=10N即可。检测流程的最大运算次数V，一般设置为 V=30N到50N即可。
[0123] 4、效果分析和适用范围
[0124] 本发明实施例提供的资源分配最优分配结果或近似最优分配结果的搜索遍历算 法的实质可描述为：
[0125]W二进制情形为例，假如所需遍历的二进制序列长度为4(该里可W理解为有4个 基站，每个基站有两种PCI排列组合的可能性)，则按照如图19所示的树形结构就可W在第 四级中将0000~1111的16种排列组合全部遍历出。本发明实施例提供的算法的实际内 涵就是在类似的树形结构上沿着某一个路径搜索最优解，如果方向不对的话，跳跃到树形 结构中的另一个节点继续搜索，即，在树形结构图中跳跃搜索。"跳跃"表示在队列中遍历一 种情况后按照全局代价值大小排序，如果队列尾部元素在排序前后发生改变，则就相当于 在树形结构中跳跃到另一个节点进行下一步的搜索。
[012引图19只是W二进制为例，即4个基站，每个基站有两种PCI排列组合情形（即每个 节点有2个分支）为例描述。不失一般性 ，针对一个长度为N的序列找。，X。…，XwJ，对于 Xi可能取值的个数为di，则可W构造一个每个节点分叉个数不同的树形结构。
[0127] 可W看出，本发明实施例综合了遗传算法中对部分次优解的保留（reservation) 的优点W及遍历树结构（图19)特点，但并不是遍历所有的可能性，而是只遍历其中的一部 分，目的是每遍历一次，就要朝最优解逼近一次，从而快速寻找最优解，而遗传算法并不能 保证每进化一次就能进化出比上一代更好的种群。
[012引 由此可见，发明实施例相对于遗传算法具有W下优点：
[0129] (1)运算速度快。在一定的运行环境下，对于3184个基站的情形，遗传算法需要大 约13~15个小时的时间复杂度去寻找最优分配结果，而本发明实施例需要约17分钟即可 寻找到最优分配结果，而且总体代价不高于遗传算法；
[0130] (2)得到的最终分配结果稳定。遗传算法每次运算到的结果很大概率都不相同，由 于是一种基于概率的搜索最优分配结果的过程，所W每次的分配结果都与当时选取他的概 率有关导致分配结果不稳定，而且不确定是否是最优分配结果，而本发明实施例每次得到 的分配结果都是相对固定的；
[0131] (3)搜索到的最小代价值不高于遗传算法的最小代价值。由于像遗传算法搜索到 的最小代价基本每次都不同，而本发明实施例搜索到的最小代价值都是相对固定的，并且 经过测试可W验证本发明实施例搜索到的最终分配结果的代价值不高于使用遗传算法搜 索到的最终分配结果的代价值。
[0132] 如前所述，本发明实施例提供的资源分配方案可适用于多种资源的分配场景。比 女口，在GSM(GlobalSystemforMobileCommunications,全球移动通信系统）频点分配 过程中，假设有N个待分配频点的小区，编号为0,…，N-1，M个可供分配的频点，编号为 f〇,…，fi-i并且N〉M，则频率重用不可避免。对于小区0至小区M-1，可W将片~山按顺序 分配，从小区M开始频率重化则对于小区M，M+1，…，N-1来说，每个小区至多都有M种频 点选择，遍历该M种情形，使该M个新元素进入队列计算代价值，然后按照代价值排序，一直 保持队尾的元素是全局代价值最小的，遍历树结构是每个节点产生M个分支。频点分配W 小区为单位。TD-SCDMA (Time Division-Sync虹onous Code Division Multiple Access, 时分同步码分多址)系统的频点分配过程的模型类似于GSM系统的频点分配模型，该里不再 费述。
[0133] 再比如，在TD-SCDMA系统的扰码分配过程中，假设有N个待分配扰码的小区，编号 为0,…，N-1，M个可供分配的扰码（M)，编号为S。，…，Sm_i，并且N〉M，则扰码重用不可避免。 对于小区0至小区M-1，可W将S。，…，Sm_i按顺序分配给小区，从小区M开始扰码重用，则从 小区M，M+1，…，N-1来说每个小区至多都有M种扰码选择，遍历该M种情形，使该M个新 元素进入队列计算代价值，然后按照代价值进行排序，一直保持队尾的元素是全局代价值 最小的，遍历树结构是每个节点产生M个分支。TD-SCDMA的扰码分配是W小区为单位进行 的。
[0134] 本发明实施例提供的上述各流程均可由软件编程方式实现。图20A~图20D分别 描述了由软件编程方式实现的资源分配装置的结构。
[0135] 如图20A所示，本发明实施例提供的资源分配装置可包括：
[0136] 初始化单元50,用于将N个目标对象的资源分配标识的初始值作为一行元素放入 第一队列，并设置所述N个目标对象的资源分配标识初始值对应的全局代价值为初始代价 值；其中，一个目标对象的一个资源分配标识用于标识该目标对象的所有可能的资源分配 方案中的一种，所述第一队列为M1XN的队列，N为队列的列数，N的取值为目标对象的数 量，Ml为队列的行数，Ml取值为队列的长度；
[0137] 第一搜索单元51，用于对所述第一队列执行遍历流程，所述遍历流程包括分别对 所述N个目标对象中的每个目标对象遍历所有的资源分配标识；
[013引分配单元52,用于在所述第一搜索单元完成所述遍历流程后，根据所述第一队列 尾部一行元素确定第一资源分配优选方案，所述第一资源分配优选方案中包含N个目标对 象的资源分配标识，根据所述第一资源分配优选方案为所述N个目标对象进行资源分配；
[0139] 其中，所述遍历流程中，第一搜索单元51针对第i个目标对象执行W下操作， 1《i《N，所述第i个目标对象为尚未分配资源的目标对象：
[0140] W队列尾部Q行元素为基础对第i个目标对象的所有资源分配标识进行遍历，得 到QiXQ行元素，所述QiXQ行元素中的每一行元素包含N个目标对象的资源分配标识，所 述为第i个目标对象的所有资源分配标识的数量，Q为正整数；
[0141] 将所述diXQ行元素放入队列，计算所述diXQ行元素中每一行对应的全局代价 值；
[0142] 根据每一行元素对应的全局代价值对所有行元素进行排序，使每一行元素对应的 全局代价值按照从队列头部到尾部的顺序依次降低。
[0143] 进一步地，本发明实施例提供的资源分配装置还可包括第二搜索单元53,如图 20B所示。第一搜索单元51还用于：若所述第一队列元素溢出，则从所述第一队列的尾部 开始将P行元素移至第二队列，P> 1，并在将所述P行移至所述第二队列后，继续执行所 述遍历流程。其中，第二队列的尺寸与第一队列相同，即第二队列的行数和列数分别与第一 队列的行数和列数相同。第二搜索单元53用于对所述第二队列执行所述遍历流程。相应 的，分配单元52在确定第一资源分配优选方案时，比较所述第一队列尾部一行元素的全局 代价值和所述第二队列尾部一行元素的全局代价值，根据两者中全局代价值最小的元素确 定第一资源分配优选方案。
[0144] 进一步地，图20B所述的装置中，第一搜索单元51还用于：若所述第一队列元素再 次溢出，则从所述第一队列的头部开始顺序删除至少一行元素；第二搜索单元53还用于： 若所述第二队列元素已溢出，则从所述第一队列的头部开始顺序删除至少一行元素。
[0145] 进一步地，图20A所述的装置中还可包括第H搜索单元54,如图20C所示；或者， 图20B所述的装置中还可包括第H搜索单元54,如图20D所示。
[0146] 图20C或图20D所示的装置中，第H搜索单元54,用于在分配单元52确定出第一 资源分配优选方案之后，根据所述第一资源分配优选方案执行验证流程，并在所述验证流 程结束后指示分配单元52根据所述验证流程的验证结果为所述N个目标对象进行资源分 配，所述验证结果中包含N个目标对象进行资源分配标识。其中，所述验证流程，包括：
[0147] 步骤a;将所述第一资源分配优选方案中的N个目标对象的资源分配标识作为一 行元素放入M2XN的第H队列，将第一变量的取值设置为所述第一资源分配优选方案对应 的全局代价值，然后转入步骤b;其中，M2为队列的行数，取值为所述第H队列的长度；
[014引步骤b;对所述第H队列执行所述遍历流程，然后转入步骤C;其中，当满足结束条 件时将所述第H队列尾部一行元素作为验证结果出队，并结束所述验证流程；
[0149] 步骤C;判断所述第H队列尾部一行元素对应的全局代价值是否小于所述第一变 量的取值，若是，则转入步骤d，否则转入步骤e;
[0150] 步骤d ;将所述第一变量设置为所述第H队列尾部一行元素对应的全局代价值， 然后转入步骤b;
[0151] 步骤e;对所述第H队列尾部一行元素中的每个目标对象遍历所有的资源分配标 识，并在遍历完成所有目标对象的资源分配标识后，将遍历结果放入所述第H队列，计算当 前入队的每一行元素对应的全局代价值，根据所述第H队列中的每行元素对应的全局代价 值对所述第H队列中的所有行元素进行排序，使所述第H队列中每一行元素对应的全局代 价值按照从所述第H队列的头部到尾部的顺序依次降低，然后转入步骤b;其中，当满足结 束条件时将所述第H队列尾部一行元素作为验证结果出队，并结束所述验证流程。
[0152] 进一步地，第H搜索单元54还用于：在所述步骤b完成之后在转入所述步骤C之 前，保留所述第H队列尾部一行元素，将其余行元素从所述第H队列移除。
[0153] 优选地，上述各装置中，所述目标对象为基站，所述资源分配标识为物理小区标识 PCI分配组合的编号，一个基站的所有小区的每种PCI分配组合使用唯一的编号进行标识， 所述为N个目标对象进行资源分配是指为N个基站分配PCI;或者，所述目标对象为小区， 所述资源分配标识为小区频点分配组合的编号，所述为N个目标对象进行资源分配是指为 N个小区分配小区频点；或者，所述目标对象为小区，所述资源分配标识为小区扰码分配组 合的编号，所述为N个目标对象进行资源分配是指为N个小区分配扰码。
[0154] 优选地，在所述目标对象为基站、所述资源分配标识为PCI组合的编号的情况下， 所述全局代价值可W根据前述公式（1)计算得到。
[0155] 综上所述，本发明的上述实施例中，由于在资源分配的过程中，分别对N个目标对 象中的每个目标对象遍历所有的资源分配标识(一个资源分配标识用于表示一种资源分配 选择的可能性)，并在遍历过程中，根据全局代价值对N个目标对象的遍历结果进行排序，从 而找到当前的较优分配结果，然后W该较优分配结果为基础对下一个目标对象的资源分配 标识进行遍历，W此类推，最终找到最优资源分配结果。由于每次对一个目标对象的资源分 配情况进行遍历，都是根据上一次遍历得到的较优分配结果为基础进行的，即，并不是遍历 N个目标对象的所有的资源分配可能性，而是遍历其中的一部分，目的是每遍历一次就朝最 分配结果逼近一次，从而可W快速寻找到资源分配的最优分配结果。
[0156] 本发明是参照根据本发明实施例的方法、设备（系统)、和计算机程序产品的流程 图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一 流程和/或方框、W及流程图和/或方框图中的流程和/或方框的结合。可提供该些计算 机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理 器，使得通过该计算机或其他可编程数据处理设备的处理器执行的指令可实现流程图中的 一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
[0157] 该些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备W特 定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指 令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或 多个方框中指定的功能。
[0158] 该些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计 算机或其他可编程设备上执行一系列操作步骤W产生计算机实现的处理，从而在计算机或 其他可编程设备上执行的指令提供用于实现在流程图的一个流程或多个流程和/或方框 图的一个方框或多个方框中指定的功能的步骤。
[0159] 尽管已描述了本发明的优选实施例，但本领域内的技术人员一旦得知了基本创造 性概念，则可对该些实施例作出另外的变更和修改。所W，所附权利要求意欲解释为包括优 选实施例W及落入本发明范围的所有变更和修改。
[0160] 显然，本领域的技术人员可W对本发明进行各种改动和变型而不脱离本发明的精 神和范围。该样，倘若本发明的该些修改和变型属于本发明权利要求及其等同技术的范围 之内，则本发明也意图包含该些改动和变型在内。
【主权项】
1. 一种资源分配方法，其特征在于，包括： 将N个目标对象的资源分配标识的初始值作为一行元素放入第一队列，并设置所述N 个目标对象的资源分 配标识初始值对应的全局代价值为初始代价值，其中，一个目标对象 的一个资源分配标识用于标识该目标对象的所有可能的资源分配方案中的一种，所述第一 队列为MlXN的队列，N为队列的列数，N的取值为目标对象的数量，Ml为队列的行数，Ml 取值为队列的长度； 对所述第一队列执行遍历流程，所述遍历流程包括分别对所述N个目标对象中的每个 目标对象遍历所有的资源分配标识； 所述遍历流程完成后，根据所述第一队列尾部一行元素确定第一资源分配优选方案， 所述第一资源分配优选方案中包含N个目标对象的资源分配标识，根据所述第一资源分配 优选方案为所述N个目标对象进行资源分配； 其中，所述遍历流程中，针对第i个目标对象执行以下操作，I < i < N，所述第i个目 标对象为尚未分配资源的目标对象： 以队列尾部Q行元素为基础对第i个目标对象的所有资源分配标识进行遍历，得到 IX Q行元素，所述IX Q行元素中的每一行元素包含N个目标对象的资源分配标识，所述 Qi为第i个目标对象的所有资源分配标识的数量，Q为正整数； 将所述Qi X Q行元素放入队列，计算所述Qi X Q行元素中每一行对应的全局代价值； 根据每一行元素对应的全局代价值对所有行元素进行排序，使每一行元素对应的全局 代价值按照从队列头部到尾部的顺序依次降低。2. 如权利要求1所述的方法，其特征在于，所述方法还包括： 若所述第一队列元素溢出，则从所述第一队列的尾部开始将P行元素移至第二队列， 分别对所述第一队列和所述第二队列执行所述遍历流程，所述第二队列的行数和列数与所 述第一队列相同，P彡1; 所述根据所述第一队列尾部一行元素确定第一资源分配优选方案，包括： 比较所述第一队列尾部一行元素的全局代价值和所述第二队列尾部一行元素的全局 代价值，根据两者中全局代价值最小的元素确定第一资源分配优选方案。3. 如权利要求2所述的方法，其特征在于，所述方法还包括： 若所述第一队列元素再次溢出，则从所述第一队列的头部开始顺序删除至少一行元 素；和/或， 若所述第二队列元素溢出，则从所述第二队列的头部开始顺序删除至少一行元素。4. 如权利要求1-3中任一项所述的方法，其特征在于，确定出第一资源分配优选方案 之后，还包括：根据所述第一资源分配优选方案执行验证流程； 所述根据第一资源分配优选方案为所述N个目标对象进行资源分配，包括：根据所述 验证流程的验证结果为所述N个目标对象进行资源分配，所述验证结果中包含N个目标对 象进行资源分配标识； 所述验证流程，包括： 步骤a :将所述第一资源分配优选方案中的N个目标对象的资源分配标识作为一行元 素放入M2XN的第三队列，将第一变量的取值设置为所述第一资源分配优选方案对应的全 局代价值，然后转入步骤b ;其中，M2为队列的行数，取值为所述第三队列的长度； 步骤b :对所述第三队列执行所述遍历流程，然后转入步骤C ;其中，当满足结束条件时 将所述第三队列尾部一行元素作为验证结果出队，并结束所述验证流程； 步骤C :判断所述第三队列尾部一行元素对应的全局代价值是否小于所述第一变量的 取值，若是，则转入步骤d，否则转入步骤e ; 步骤d :将所述第一变量设置为所述第三队列尾部一行元素对应的全局代价值，然后 转入步骤b ; 步骤e :对所述第三队列尾部一行元素中的每个目标对象遍历所有的资源分配标识， 并在遍历完成所有目标对象的资源分配标识后，将遍历结果放入所述第三队列，计算当前 入队的每一行元素对应的全局代价值，根据所述第三队列中的每行元素对应的全局代价值 对所述第三队列中的所有行元素进行排序，使所述第三队列中每一行元素对应的全局代价 值按照从所述第三队列的头部到尾部的顺序依次降低，然后转入步骤b ;其中，当满足结束 条件时将所述第三队列尾部一行元素作为验证结果出队，并结束所述验证流程。5. 如权利要求4所述的方法，其特征在于，所述方法还包括： 所述步骤b完成之后在转入所述步骤c之前，保留所述第三队列尾部一行元素，将其余 行元素从所述第三队列移除。6. 如权利要求1-3中任一项所述的方法，其特征在于，所述目标对象为基站，所述资源 分配标识为物理小区标识PCI分配组合的编号，一个基站的所有小区的每种PCI分配组合 使用唯一的编号进行标识，所述为N个目标对象进行资源分配是指为N个基站分配PCI ;或 者 所述目标对象为小区，所述资源分配标识为小区频点分配组合的编号，所述为N个目 标对象进行资源分配是指为N个小区分配小区频点；或者 所述目标对象为小区，所述资源分配标识为小区扰码分配组合的编号，所述为N个目 标对象进行资源分配是指为N个小区分配扰码。7. 如权利要求6所述的方法，其特征在于，在所述目标对象为基站、所述资源分配标识 为PCI组合的编号的情况下，所述全局代价值根据以下公式计算得到：其中，GlobalCost为全局代价值计算结果；m为天线方向图具有公共交叠覆盖区域的 小区对数量；PairCellC0Sti为第i个小区对的代价值，所述第i个小区对中的两个小区的 天线方向图具有公共覆盖交叠区域，i为正整数；ω i为PCI分配因子，若所述第i个小区对 中两个小区被分配的是模3相同的？(：1，则Coi=I,若所述第i个小区对中两个小区被分配 的是模3不相同的PCI，则ω「0。8. -种资源分配装置，其特征在于，包括： 初始化单元，用于将N个目标对象的资源分配标识的初始值作为一行元素放入第一队 列，并设置所述N个目标对象的资源分配标识初始值对应的全局代价值为初始代价值；其 中，一个目标对象的一个资源分配标识用于标识该目标对象的所有可能的资源分配方案中 的一种，所述第一队列为MlXN的队列，N为队列的列数，N的取值为目标对象的数量，Ml为 队列的行数，Ml取值为队列的长度； 第一搜索单元，用于对所述第一队列执行遍历流程，所述遍历流程包括分别对所述N 个目标对象中的每个目标对象遍历所有的资源分配标识； 分配单元，用于在所述第一搜索单元完成所述遍历流程后，根据所述第一队列尾部一 行元素确定第一资源分配优选方案，所述第一资源分配优选方案中包含N个目标对象的资 源分配标识，根据所述第一资源分配优选方案为所述N个目标对象进行资源分配； 其中，所述遍历流程中，所述第一搜索单元针对第i个目标对象执行以下操作， I < i < N，所述第i个目标对象为尚未分配资源的目标对象： 以队列尾部Q行元素为基础对第i个目标对象的所有资源分配标识进行遍历，得到 % X Q行元素，所述IX Q行元素中的每一行元素包含N个目标对象的资源分配标识，所述 Qi为第i个目标对象的所有资源分配标识的数量，Q为正整数； 将所述Qi X Q行元素放入队列，计算所述Qi X Q行元素中每一行对应的全局代价值； 根据每一行元素对应的全局代价值对所有行元素进行排序，使每一行元素对应的全局 代价值按照从队列头部到尾部的顺序依次降低。9. 如权利要求8所述的装置，其特征在于，还包括第二搜索单元； 所述第一搜索单元还用于：若所述第一队列元素溢出，则从所述第一队列的尾部开始 将P行元素移至第二队列，并在将所述P行移至所述第二队列后，继续执行所述遍历流程， 所述第二队列的行数和列数与所述第一队列相同，P > 1 ; 所述第二搜索单元，用于对所述第二队列执行所述遍历流程； 所述分配单元具体用于，比较所述第一队列尾部一行元素的全局代价值和所述第二队 列尾部一行元素的全局代价值，根据两者中全局代价值最小的元素确定第一资源分配优选 方案。10. 如权利要求9所述的装置，其特征在于，所述第一搜索单元还用于：若所述第一队 列元素再次溢出，则从所述第一队列的头部开始顺序删除至少一行元素； 所述第二搜索单元还用于：若所述第二队列元素已溢出，则从所述第二队列的头部开 始顺序删除至少一行元素。11. 如权利要求8-10中任一项所述的装置，其特征在于，还包括： 第三搜索单元，用于在所述分配单元确定出第一资源分配优选方案之后，根据所述第 一资源分配优选方案执行验证流程，并在所述验证流程结束后指示所述分配单元根据所述 验证流程的验证结果为所述N个目标对象进行资源分配，所述验证结果中包含N个目标对 象进行资源分配标识； 所述验证流程，包括： 步骤a :将所述第一资源分配优选方案中的N个目标对象的资源分配标识作为一行元 素放入M2 XN的第三队列，将第一变量的取值设置为所述第一资源分配优选方案对应的全 局代价值，然后转入步骤b ;其中，M2为队列的行数，取值为所述第三队列的长度； 步骤b :对所述第三队列执行所述遍历流程，然后转入步骤c ;其中，当满足结束条件时 将所述第三队列尾部一行元素作为验证结果出队，并结束所述验证流程； 步骤c :判断所述第三队列尾部一行元素对应的全局代价值是否小于所述第一变量的 取值，若是，则转入步骤d，否则转入步骤e ; 步骤d :将所述第一变量设置为所述第三队列尾部一行元素对应的全局代价值，然后 转入步骤b ; 步骤e :对所述第三队列尾部一行元素中的每个目标对象遍历所有的资源分配标识， 并在遍历完成所有目标对象的资源分配标识后，将遍历结果放入所述第三队列，计算当前 入队的每一行元素对应的全局代价值，根据所述第三队列中的每行元素对应的全局代价值 对所述第三队列中的所有行元素进行排序，使所述第三队列中每一行元素对应的全局代价 值按照从所述第三队列的头部到尾部的顺序依次降低，然后转入步骤b ;其中，当满足结束 条件时将所述第三队列尾部一行元素作为验证结果出队，并结束所述验证流程。12. 如权利要求11所述的装置，其特征在于，所述第三搜索单元还用于：在所述步骤b 完成之后在转入所述步骤c之前，保留所述第三队列尾部一行元素，将其余行元素从所述 第三队列移除。13. 如权利要求8-10中任一项所述的装置，其特征在于，所述目标对象为基站，所述资 源分配标识为物理小区标识PCI分配组合的编号，一个基站的所有小区的每种PCI分配组 合使用唯一的编号进行标识，所述为N个目标对象进行资源分配是指为N个基站分配PCI ; 或者 所述目标对象为小区，所述资源分配标识为小区频点分配组合的编号，所述为N个目 标对象进行资源分配是指为N个小区分配小区频点；或者 所述目标对象为小区，所述资源分配标识为小区扰码分配组合的编号，所述为N个目 标对象进行资源分配是指为N个小区分配扰码。14. 如权利要求13所述的装置，其特征在于，在所述目标对象为基站、所述资源分配标 识为PCI组合的编号的情况下，所述全局代价值根据以下公式计算得到：其中，GlobalCost为全局代价值计算结果；m为天线方向图具有公共交叠覆盖区域的 小区对数量；PairCellC0Sti为第i个小区对的代价值，所述第i个小区对中的两个小区的 天线方向图具有公共覆盖交叠区域，i为正整数；ω i为PCI分配因子，若所述第i个小区对 中两个小区被分配的是模3相同的？(：1，则Coi=I,若所述第i个小区对中两个小区被分配 的是模3不相同的PCI，则ω「Ο。
【专利摘要】本发明公开了一种资源分配方法及装置。本发明在资源分配的过程中，分别对N个目标对象中的每个目标对象遍历所有的资源分配标识（一个资源分配标识表示一种资源分配选择的可能性），并在遍历过程中，根据全局代价值对遍历结果进行排序，从而找到当前的较优分配结果，然后以该较优分配结果为基础对下一个目标对象的资源分配标识进行遍历，以此类推，最终找到最优资源分配结果。由于每次对一个目标对象的资源分配情况进行遍历，都是根据上一次遍历到的较优分配结果为基础进行的，即，并不是遍历N个目标对象的所有的资源分配可能性，而是遍历其中的一部分，目的是每遍历一次就朝最优分配结果逼近一次，从而可以快速寻找到资源分配的最优分配结果。
【IPC分类】H04W72/04
【公开号】CN104902573
【申请号】CN201410083500
【发明人】杨星
【申请人】电信科学技术研究院
【公开日】2015年9月9日
【申请日】2014年3月7日
最新回复(0)