带有自组织中继终端的蜂窝网络的基于贪婪算法的自主资源块分配方案的系统和方法

本发明要求2013年7月25日提交的发明名称为“带有自组织中继终端 的蜂窝网络的基于贪婪算法的自主资源块分配方案的系统和方法”的第 61/858,480号美国临时专利申请案的在先申请优先权，该在先申请的内容以 引入的方式并入本文中。

技术领域

本发明涉及无线通信系统和方法，在特定的实施例中，涉及带有自组织 中继终端的蜂窝网络的基于贪婪算法的资源块自主分配方案的系统和方法。

背景技术

中继辅助网络通过将高衰减无线接口分成多个低衰减无线接口并且通过 扩展基站的覆盖范围来提高小区性能。下一代无线网络很可能会通过实现更 高密度的中继终端以及提供基础设施节点和非基础设施节点来进一步利用这 些益处，例如，移动设备通过设备到设备(简称D2D)或者机器到机器(简 称M2M)通信为其他移动设备充当中继终端的作用。

传统的中继辅助网络通常采用集中的资源分配方案，其中，基站为所述 中继终端和移动设备之间的通信分配资源。由于与基站和中继终端之间分配 信息通信相关联的开销和延时，在具有较多数量的中继的网络中这些集中资 源分配方案的效率较低。相应地，以分散的方式在中继终端自主提供资源对 降低中继链路上的开销和延时十分有益。

发明内容

通过本发明实施例描述的带有自组织中继终端的蜂窝网络的基于贪婪算 法的资源块自主分配方案的系统和方法，通常实现了技术优势。

根据一实施例，提供了一种为中继高效生成资源块(简称RB)分配序 列的方法。在该示例中，所述方法包括：获得多个图样来分配小区中的可用 RB；从所述多个图样中选择第一图样以及从多个循环移位选择一个循环移 位得到第一图样，循环移位元组。所述多个图样中剩余的图样包含在酉群中。 所述方法还包括：按照所述第一图样，循环移位元组，构建循环群。所述循 环群受所述第一图样，循环移位元组的有效RB对应的被占用的RB的约束。 所述方法还包括：在所述多个循环移位上对所述酉群中剩余的图样进行迭代 顺序选择以获得RB分配序列的次序。所述第一图样，循环移位元组按照 RB分配序列的次序指定第一RB分配序列。所述方法还包括：按照所述RB 分配序列的次序在每个所述中继终端中配置查询表。还提供了一种用于执行 该方法的装置。

根据另一实施例，提供了一种中继操作方法。在该示例中，所述方法包 括：接收查询表集合，所述查询表集合指定了为小区中的可用资源块(简称 RB)分布式分配的资源块分配序列的列表。所述查询表集合中的每个查询 表旨在分配不同数量的可用RB。所述方法还包括：确定在第一时间段已经 分配第一数量的可用RB；从所述查询表集合中确定用于分配所述第一数量 的可用RB的第一查询表；按照所述第一查询表指定的RB分配序列的次序 在所述第一时间段内向移动终端自主分配RB。还提供了一种用于执行该方 法的装置。

附图说明

为了更完整地理解本发明及其优点，现在参考下文结合附图进行的描述， 其中：

图1示出了一种无线通信网络的实施例的示意图；

图2示出了一种中继辅助网络的实施例的示意图；

图3A-3D示出了中继终端如何使用资源块分配序列进行资源分配的示 意图；

图4A-4B示出了一种RB分配序列列表计算方法的实施例的流程图；

图5A-5B示出了一种迭代顺序选择方法的实施例的流程图；

图6示出了一种进行迭代顺序选择来选取RB分配序列的算法的实施例 的流程图；

图7示出了展示中继终端的有效负载的流程图；

图8示出了一种选择资源块分配序列的贪婪算法的实施例的流程图；

图9示出了一种循环群的图形表示的实施例的示意图；

图10示出了一种循环群的图形表示的另一实施例的示意图；

图11示出了一种图形化贪婪算法的伪代码的实施例的示意图；

图12示出了仿真结果的曲线图；

图13示出了额外的仿真结果的曲线图；

图14示出了一种计算平台的实施例的示意图；

图15示出了一种通信设备的实施例的示意图。

除非另有指示，否则不同图中的对应标号和符号通常指代对应部分。绘 制各图是为了清楚地说明实施例的相关方面，因此未必是按比例绘制的。

具体实施方式

下文将详细论述实施例的制作和使用。然而，应了解，本发明提供可在 各种具体上下文中体现的许多适用的发明性概念。所论述的具体实施例仅仅 说明用以实施和使用本发明的具体方式，而不限制本发明的范围。

中继终端可以使用随机分配方案或者结构化分配方案来实现分布式资源 供应。随机分配方案通常比结构化分配方案简单得多，而结构化分配方案通 常可以在密集的网络环境中提供更好的干扰性能。一种结构化分配方案中使 用资源块(简称RB)分配序列在所述中继终端管理分布式资源分配。更具 体地说，在所述中继终端的查询表中存储RB分配序列列表，所述中继终端 在向移动终端分配RB时按顺序获取所述RB分配序列。下面是一个简单的 例子，解释了如何利用RB分配序列列表在具有4个可用RB(RB-1，RB-2， RB-3，以及RB-4)的网络进行资源分配。

在该示例中，RB分配序列列表存储在每个中继终端中，并包括如下RB 分配序列次序：{AS(i)＝<RB-1；RB-2；RB-3；RB-4>；AS(ii)＝<RB- 4；RB-3；RB-2；RB-1>；AS(iii)＝<RB-2；RB-3；RB-4；RB-1>；和AS (iv)＝<RB-4；RB-1；RB-2；RB-3>}。首先，第一移动终端向第一中继终 端请求两个RB，从而促使所述中继终端按照RB分配序列列表中的第一分 配序列(即，AS(i)＝<RB-1；RB-2；RB-3；RB-4>)给所述第一移动终 端分配RB-1和RB-2。然后，第二移动台向第二中继终端请求一个RB。所 述第二中继终端确定所述第一RB分配序列在使用中，并选择下一个可用的 RB分配序列(即，AS(ii))。所述第二中继终端接着按照AS(ii)即 <RB-4；RB-3；RB-2；RB-1>指定的序列，为所述第二移动台分配RB-4。

之后，第三移动台向第三中继终端请求单个RB，此时，所述第三中继 终端选择下一个可用的RB分配序列(即，AS(iii))，并按照AS(iii) 即<RB-2；RB-3；RB-4；RB-1>指定的序列，向所述第三移动台分配RB-2。 由于RB-2被所述第一中继终端分配给所述第一移动台，RB-2被所述第一移 动台占用，因此所述第三移动台和所述第一移动台各自的传输发生冲突。所 述第三无线终端感知到这一干扰，向第三移动终端重新分配RB-3，RB-3是 AS(iii)指定的下一个RB。因此，所有4个RB在只有一次冲突的情况下 被分配。

不同的RB分配序列列表提供不同程度的性能。实际上，对于给定的参 数集，可以通过穷尽搜索计算出最佳的RB分配序列。然而，例如，当可用 的RB数量增加或者减少时，所述参数集可能会改变，需要对更新后的RB 分配序列集进行计算。值得注意的是，穷尽搜索技术的计算复杂度较高，可 能会致使它们不适合大型和/或快速变化的网络。因此，需要一个高效且有 效的RB分配序列列表的计算方案。

本发明各方面提供了中继辅助网络中计算RB分配序列的迭代顺序选择 技术。实施例中的技术首先获取包含用于分配资源块的图样的酉群。其次， 基于选取的图样，循环移位元组，构建循环群的图形表示，然后将对应的图 样从所述酉群移出。之后，通过迭代顺序选择技术选择列表的剩余RB分配 序列。在每个迭代序列中迭代顺序选择技术可以在多个循环移位估计所述酉 群中剩余的图样。在每次迭代结束时，在所述列表中增加一个新的RB分配 序列。所述新的RB分配序列由在该迭代中与所述图形表示占用的资源块冲 突最少的图样，循环移位元组定义。更具体的是，对于所有循环移位，剩余 的图样按顺序进行估计(在一个给定的迭代中)直到(i)确定出产生零冲 突的图样，循环移位元组，或者(ii)所有的剩余图样已经在所有循环移位 进行了估计。在后一种情景中，产生最少冲突的图样，循环移位元组用于定 义所述新的RB分配序列。然后，将所述对应的图样从所述酉群中去除，准 备下一次迭代。

本发明的其他方面允许中继终端针对不同数量的可用RB存储RB分配 序列集合，从而允许所述中继终端在不更新其查询表的情况下适应可用RB 数量的变化。更具体的是，不同的RB分配序列列表可以用于不同数量的可 用资源块，其中，所述序列在互不为子集的不同列表中。例如，“X”个可 用资源块的序列本质上不同于“X+1”个可用资源块的序列，因此，后一个 序列集需要单独计算而不能从前一个序列集推导出。每次重新分配可用资源 块的时候，在所述中继终端更新查询表可能会无效。为了避免这种情况，可 在所述中继终端中存储多个查询表，每个查询表为不同数量的可用RB指定 序列列表。所述中继终端可以，例如，通过广播信令，确定一段时间内有多 少可用的RB，然后为该段时间内动态资源分配选择对应的查询表。针对可 用RB数量的变化，所述中继终端可以动态地重选不同的查询表，例如，RB 重新分配到其他频带或从其他频带重新分配。下面对这些以及其他方面进行 了更加详细的描述。

图1示出了一种数据通信网络100。所述网络100包括具有覆盖范围 101的基站110、多个移动设备120和回程网络130。如图所示，所述基站 110建立了与所述移动设备120的上行(短划线)和/或下行(点线)连接， 用于将数据从所述移动设备120承载到所述基站110，反之亦然。在所述上/ 下行连接上承载的数据可包括所述移动设备120之间的通信数据，以及通过 所述回程网络130向/从远端(未显示)通信的数据。这里所使用的术语 “基站”指任何用于向网络提供无线接入的组件(或者组件的组合)，例如， 增强型基站(简称eNB)、宏小区、毫微微蜂窝基站、Wi-Fi接入点(简称 AP)或者其他支持无线的设备。基站可以按照一个或多个无线通信协议提 供无线接入，如，长期演进(简称LTE)、LTEadvanced(简称LTE-A)、 高速分组接入(简称HSPA)和WiFi802.11a/b/g/n/ac等。这里使用的术语 “移动设备”指任何能够和基站建立无线连接的组件(或组件的组合)，如， 用户设备(简称UE)、移动台(简称STA)和其他支持无线的设备。在一 些实施例中，所述网络100可以包括各种其他无线设备，如中继和低功率节 点等。

有些网络会使用中继来提升性能和/或扩展小区的覆盖范围。图2示出 了用于数据通信的中继辅助网络200。如图所示，所述中继辅助网络200包 括基站201、多个中继终端210、220、230、240和250以及多个移动设备 212-214、226、236-239和242-244。所述中继终端210、220、230、240和 250用于在所述基站201和所述移动设备212-214、226、236-239和242-244 之间中继信号。这里使用的术语“中继终端”指任何用于在基站和一个或多 个移动设备之间中继信号的支持无线的设备，如基础设施节点和无线终端。 基础设施节点包括网络基础设施的部分设备，例如，专用中继节点。无线终 端包括间接并入所述网络基础设施的设备，例如，移动设备用于执行设备到 设备(简称D2D)或者机器到机器(简称M2M)通信等。

在该示例中，所述中继终端210服务所述移动设备212和214，所述中 继终端220服务所述移动设备226，所述中继终端230服务所述移动设备 236、238和239，所述中继终端240服务所述移动设备242和244，所述中 继终端250是非活动的(如，处于空闲模式)。所述中继终端210、220、 230和240可以通过可用的资源块(简称RB)与所述移动设备212-214、 226、236-239和242-244进行通信。除非另有说明，术语“可用的资源块” 在此用于粗略地指代任何用于在无线接口承载数据的网络资源，包括时域、 频域、空域、码域或其组合所定义的资源。在该实施例中，可用的资源块对 应于正交频分复用(简称OFDM)网络中的时频资源。例如，资源块可以对 应于长期演进(简称LTE)无线帧的资源块。

当在相同的RB进行通信时，在同一小区的中继终端的无线信号可能会 也可能不会相互干扰，取决于对应的中继终端和/或这些终端服务的移动设 备的相对接近度。在该示例中，所述中继终端210、220和230紧邻在一起， 因此当在共同的RB上进行通信时，它们各自的无线信号会相互干扰。相反， 所述中继终端240和250距离所述中继终端210、220和230较远，所以当 在共同的RB上进行通信时，各组中继终端的无线信号不会相互干扰。

中继辅助网络200的可用RB由所述中继终端210、220和230按照RB 分配序列集合进行分配。图3A-3D示出了所述中继终端210、220和230如 何使用不同的RB分配序列将资源分配给所述移动设备212-214、226和236- 239的示例。如图3A所示，所述中继终端210、220和230(分别)使用RB 分配序列310、320和330将资源分配给所述移动设备212-214、226和236- 239。在该示例中，所移动设备请求单个RB。然而，在其他示例中，移动设 备可能请求多个RB。

图3B展示了所述中继终端210如何按照所述RB分配序列310将资源 块分配给所述移动设备212和214。如图所示，所述中继终端210按照所述 RB分配序列310指定的RB次序把RB-2分配给所述移动设备212，把RB-4 分配给所述移动设备214。被占用的RB显示在图形表示300上。图3C展示 了所述中继终端220如何按照所述RB分配序列320将RB-6分配给所述移 动设备226，图3D展示了所述中继终端230如何按照所述RB分配序列330 将RB-8、RB-9和RB-6(分别)分配给所述移动设备238、239和236。所 述RB-6被同时分配给了所述移动设备226和所述移动设备236，因此，这 两个设备各自的通信会相互干扰。这会促使所述中继终端220和230中的一 个或两个重新分配一个不同的资源块给它们对应的移动设备。例如，所述中 继终端220可以按照所述RB分配序列320指定的下一个资源块分配重新分 配RB-3给所述移动设备226。类似的，所述中继终端230可以按照所述RB 分配序列330重新分配RB给所述移动设备236直到没有冲突发生。

RB分配序列集合可以设计成适合于网络状况/参数。相应地，网络设备 (例如，基站和中央控制器等)可以用于在所述网络200的参数发生变化时 动态地更新所述RB分配序列集合，例如，当中继终端和/或可用的RB的数 量发生变化时。本发明各方面提供了按照迭代顺序选择技术高效计算RB分 配序列集合的方法的实施例。

图4A-4B示出了一种按照迭代顺序选择技术计算RB分配序列集合的方 法400的实施例，所述方法可以由网络设备执行。如图所示，所述方法400 开始于步骤410：所述网络设备生成用于分配可用RB的图样401的集合。 然后，所述方法400进入步骤420：所述网络设备生成图样以得到图样402 的酉群。接着，所述方法400进入步骤430：所述网络设备选择一个基础图 样。在该示例中，选择了图样P1。在其他示例中，可选择一个不同的图样。 之后，所述方法400进入步骤440：所述网络设备基于选择的所述基础图样、 循环移位和资源块的有效个数构建循环群480的图形表示。如图所示，所述 循环群480的图形表示根据所述基础图样指定的次序将所述可用的RB沿着 圆圈的周长放置。所述循环群480的图形表示受限于指示符481、482、484 和486对应的被占用的RB。所述被占用的RB由RB的有效个数和选择的所 述循环移位所确定，既应用于选择的所述基础图样也应用于所述基础图样算 法倒数。

在该示例中，RB的有效个数是2个，选择的所述循环移位为0。此外， 选择的所述基础图样(P₁)为<RB-1，RB-2，RB-4，RB-8，RB-5，RB-10， RB-9，RB-7，RB-3，RB-6>，选择的所述基础图样算法倒数(P₁^-1)为<RB- 6，RB-3，RB-7，RB-9，RB-10，RB-5，RB-8，RB-4，RB-2，RB-1>。相应 地，被占用的RB确定为P1的前两个RB(RB-2和RB-4)以及P₁^-1的前两 个RB(RB-1和RB-6)。

构建完所述循环群480的图形表示后，所述方法400进入步骤450：将 选择的所述基础图样P1移出所述酉群。在一些实施例中，所述酉群可以在 选择所述基础图样和形成所述循环群480的图形表示之后组成。在这些实施 例中，步骤450被省略了。然后，所述方法400进入步骤460：所述网络设 备增加选择的所述基础图样，循环移位元组对应的RB分配序列到RB分配 序列406的列表。在该实例中，所述第一RB分配序列由P₁和CS₀确定，所 述第二RB分配序列由P₁^-1和CS₀确定。之后，所述方法400进入步骤470： 所述网络设备对酉群中剩余图样进行迭代顺序选择以获得RB分配序列406 的列表中的剩余RB分配序列。

图5A-5B示出了进行迭代顺序选择以获得RB分配序列406的列表中的 剩余RB分配序列的方法500。如图所示，所述方法500开始于步骤510： 网络设备选择一种图样进行估计。在该示例中，选择了图样(P₂)，其为酉 群中的下一个图样。在其他示例中，可以随机选择图样。接着，所述方法 500进入步骤520：所述网络设备按照多个可能的循环移位中的一个估计选 择的所述图样(P₂)。在该示例中，选择的所述图样(P₂)首先使用零移位 进行估计，如循环群581的图形表示所示。在其他示例中，用于对给定的图 样进行初始估计的循环移位可以随机选择。然后，所述方法500进入到步骤 530：所述设备确定是否有冲突发生。如果有冲突发生，则所述方法500进 入步骤540-550：所述设备确定是否对所有的循环移位都进行了估计，如果 不是，按照剩余的移位对所述选择的图样进行移位。如果所述设备确定所有 的循环移位都已针对选择的图样进行了估计，则所述方法500进入步骤560： 所述设备确定在当前迭代是否对所有的图样都进行了估计。如果没有，则所 述方法返回步骤510：选择另一个图样进行估计。如果酉群中所有剩余的图 样都已经在本次迭代中估计，则所述方法500进入步骤565：选择冲突最少 的图样，循环移位元组。一旦在步骤530(或步骤565)中确定出冲突为零 的图样，循环移位元组，所述方法500进入步骤570-580：将对应的图样移 出所述酉群，并将对应的RB分配序列添加到RB分配序列的列表中。

在图5A-5B描述的示例迭代中，在步骤530中，确定选择的图样，循环 移位元组(P₂，CS₀)在RB-6发生了冲突，如循环群581的图形表示所示。 相应地，所述图样P₂按照如循环群582的图形表示所示的循环移位(M)进 行移位并再次估计，此时，确定选择的所述图样，循环移位元组(P₂，CS_M) 没有发生冲突。因此，将与选择的所述图样，循环移位元组(P₂，CS_M)对 应的RB分配序列添加到RB分配序列的列表中，而所述图样P₂从酉群中移 出。此时，酉群(P₃…P_N)准备好在下一次迭代中进行估计。

图6示出了一种进行迭代顺序选择来获得RB分配序列的列表的算法的 实施例的流程图。该方法的步骤不言自明，在此不再重复。

值得注意的是，在高干扰下(如，有大量的中继终端)，可在多个时隙 加入资源从而增加虚拟资源的数量。这可以通过碰撞次数检测出来。当这一 数量大于一定的阈值时，可以看出因为冲突出现了更多的用户和更多的资源 浪费。因此，分配更多的RB来增加可用RB的数量是有益的。这可以通过 结合时间资源和频率资源并在一定的时隙(例如，LTE中的TTI)重复利用 这些资源来实现。例如，在LTE中10MHz频带有50个RB。通过合并两个 TTI中的RB可以将虚拟RB的数量提高至100个。

本发明的剩余部分大篇幅地对应于一篇学术论文发表前的版本，这部分 内容用于对本发明进行补充而非以任何方式限制本发明。终端中继预计为实 现未来的无线蜂窝网络中的机器到机器(简称M2M)通信提供有效的方法。 在缺少信道质量指示的情况下，对中继终端(简称RT)的有效利用需要一 个机制，利用这个机制所述RT能够以最少的冲突为潜在的大量M2M设备 分配可用的资源块(简称RB)。这需要在一个冗长的序列集合中优化RB 分配。一种分配序列的选择技术基于对乘法循环群生成的序列进行指数复杂 度的穷尽搜索。这一技术对RB数量有相对严格的约束，并且没有考虑使用 其他群运算产生的序列。本发明各方面使用群同构来消除对RB数量的限制 并表明具体的循环群生成的最佳分配序列在所有循环生成序列的集合中是全 局最优的。本发明各方面提供了用于在带有大量RT和RB的系统中的RB 分配序列的顺序选择的具有线性复杂度的贪婪算法。本发明各方面通过调用 循环群的图形表示提供了一种简化选择度量标准。数字结果显示贪婪算法生 成的序列的性能与穷尽搜索生成的序列的性能相当，但计算成本要低得多。

机器到机器(简称M2M)通信可以使未来很多重要的应用成为可能， 包括智能电网和智能运输系统。这些应用会涉及大量地理上分散的低功率 M2M设备之间的通信。利用当前可用的蜂窝基础设施能够使这些设备之间 的通信更加便捷。然而，这一结构有两个主要的缺点：首先，M2M设备的 传输功率可能不足以直接与基站(简称BS)通信；其次，预期的大量的 M2M设备同时与BS通信会造成严重的干扰。使用终端中继方案能够减轻这 些缺点，其中，非活动的无线用户终端通过中继相邻M2M设备的信号给BS 帮助它们完成通信。通过终端中继，每个小区的M2M设备组合成集群，每 个集群配有一个中继终端(简称RT)，中继终端作为该集群的簇头。每个 RT从其集群中的M2M设备汇聚数据并中继给BS。由于每个M2M设备只 与其邻近的RT通信，终端中继大大降低了和BS通信所需的传输功率。此 外，一个集群内的M2M设备的数量预计要比BS的整个服务区域的M2M设 备数量低。这降低了想要同时与BS进行通信的M2M设备的数量，因此减 少了BS上干扰。尽管有这些潜在的优点，M2M架构中的终端中继的有效实 现需要一个RT能够将可用的(时频)资源块(简称RB)分配给其所援助 的M2M设备的机制。

当瞬时的信道质量指示(简称CQI)可用时，所述RB可以由BS集中 分配也可以由RT分布式分配。然而，在实际中，获取这种信息会引起大量 的开销，并且会严重侵害通信可用的资源。这在RT和M2M设备移动或数 量较大时尤为明显，例如，中继辅助M2M通信系统。因此，为了获取终端 中继的潜在增益，有必要设计一种高效计算的方案，通过该方案可以对RB 盲目地且自主地进行分配，比如，不需要CQI，不需要集中协调。

在缺少CQI时，可以利用使用随机RB分配的自主RB分配方案。随机 接入方案例如包括ALOHA和分段ALOHA，其中无线设备在随机选取的 RB上传输数据。这些方案大大降低了集中协调和获取CQI所必需的开销， 但是，它们的结构中缺少连贯性导致了RB分配冲突，否则是可以避免的。 所述随机方案的这一缺点由于提出的建议而减轻，其中，所述RB分配序列 具有乘法循环群(简称MCG)结构。该结构可用于获取循环生成的RB分 配序列，然后进行穷尽搜索来选择将RT之间RB分配冲突次数最小化的序 列。尽管有这些优点，当RT数量增加时，在循环生成的序列上进行穷尽搜 索的成本几乎不可行。

本发明各方面能够用于支持M2M通信的分布式中继辅助蜂窝系统。在 该系统中，假定RT和BS都没有CQI。每个RT根据指定的循环生成的RB 分配序列在本地将RB分配给对它通信的M2M设备，即，不需要BS进行集 中协调。这些循环序列使用具有特定群运算的循环群的属性在RT中生成。 然而，一些群运算会限制系统RB的数量，如，乘法运算限制系统RB的数 量为质数减1。为了缓解这种限制，本发明各方面使用循环群的属性，即， 群同构，来显示循环生成的分配序列的性能不受底层的群运算的约束。该观 察的直接结果是搜索具体的循环群生成的序列集合得到的最佳分配序列在相 同数量元素的所有循环生成的序列的集合中是全局最优的。本发明实施例提 供了针对具有大量RT和RB的网络的RB分配序列设计的高效计算技术。 详细来说，本发明各方面形成了一种贪婪算法，利用该算法所述RB分配序 列高效地循环生成，依赖于循环群的结构和序列之间分配冲突次数的顺序估 计。由于提出的算法生成的分配序列是从不同的群生成元和循环移位获取的， 对设计序列的寻求简化为寻找引起最少分配冲突的群生成元和循环移位。在 提出的算法的每次迭代中，选择一对群生成元，这样这对生成元生成的序列 和之前选择的群生成元生成的序列之间的分配冲突的次数可以减到最少。然 后，所选择的群生成元按照它们的分配冲突次数以从小到大的顺序在查询表 中排列。为了进一步简化设计，本发明各方面引进了一种贪婪算法近似的选 择度量标准。详细来说，本发明各方面调用了循环群的图形表示来了解其结 构，并接着形成了群生成元和循环移位的图示选择度量标准。

数值结果显示提出的贪婪算法生成的序列的性能与穷尽搜索生成的序列 的性能相当，但计算成本要低得多。详细来说，提出的贪婪算法的计算复杂 度是线性的，而提出的穷尽算法的计算复杂度是成指数倍增的。另外，所提 出的贪婪算法在新的RT接入系统时，不需要活动的RT来更新它们的RB分 配序列。尤其，对具有一定数量的RB的网络，所述算法提供的查询表包含 对应循环群的所有生成元。当一个新的RT在任何给定的时刻进入该系统， 它会使用第一个未使用的群生成元来获得其RB分配序列。相对比，在新 RT进入系统时，穷尽搜索需要所有活动的RT来更新它们的分配序列。这篇 论文可以总结为以下几个要点：MCG结构将RB数量限制为质数减1的限 制减轻；循环群的属性用于显示对具体循环群生成的序列的集合进行穷尽搜 索足以保证所有循环生成的序列的集合的最优性；提出了贪婪算法，其RB 分配序列的性能与穷尽搜索生成的序列的性能相当，但计算复杂度要低得多； 通过调用循环群的图形表示形成了简化的图示序列选择度量标准。

本发明各方面提供了使用循环生成的序列进行自主RB分配的技术。提 供了支持M2M通信的中继辅助蜂窝网络的上行链路的自主RB分配方案。 RT是由活动的M2M设备根据观测到的信号强度选择的。RT无法获取CQI， 一旦被选取，根据其数据速率要求给所述M2M设备分配一个或多个RB。 为了保持自主性，使用可用的RB对应的条目，RB分配可以随机进行也可 以根据指定的分配序列进行。无论用哪种方法，都不需要与BS或其他RT 协作。这种自主性可能会导致一个RB同时分配给多个M2M设备的情况。 这种情况称为“碰撞”，可能导致干扰程度较高，并且会严重降低设备观测 到的信号的质量。随机方法无法提供性能保障，与之不同的是，使用指定的 序列可以有机会改善性能。尽管没有CQI，仍然可以通过恰当地选择RB分 配序列将碰撞发生次数最小化。可惜，在所有可能的序列优化RB分配是一 项艰难的任务，对于有N个RB和M个RT的网络，需要在$\left(\begin{array}{c}N!\\ M\end{array}\right)$个序列组合 中进行穷尽搜索。当RT数量较少时，如，M＝4，更为有效的方法是将穷尽 搜索限制在循环生成的序列中，即，所述序列中的单个元素生成的序列。

该序列例如可以是通常应用于跳频(简称FH)系统的伪噪声(简称PN) 序列。然而，对FH系统有益的PN序列是基于大大不同于RB分配的通信 情景中冲突的次数来选择的。详细来说，在FH系统中，无线设备在一个停 歇间隔占用一个特定的频隙，在该间隔后放弃该频隙；而在中继辅助的RB 分配中，无线设备在整个传输间隔保留其分配的RB。下面举例论述了与循 环RB分配序列生成有关的准备工作。

例1：设置群G，其中群运算(并列标记)定义如下：G具有关联性； 对所有(x,y)∈G×G，xy∈G；每个元素的倒数在G中。G的阶为其元素的数量。 循环RB分配序列由一种被称为循环群的特定种类的群生成，稍后会有定义。

例2：如果群G的全部元素能够通过重复应用G中一个元素的群运算生 成，则群G是循环的。这个元素称为群生成元。对于阶为N的循环群G，群 生成元的数量由欧拉函数给定。

例3：给定一个正整数N，欧拉函数φ(N)是和N互质的整数的集合的势； 即，φ(N)是{q<N|gcd(q,N)＝1}集合的势，其中gcd(q,N)是q和N的最大公约 数。

在例2中，对阶为N的群G的生成元中的一个重复应用群运算得出涵盖 G中所有元素的N条循环序列。因此，要研究针对带有N个RB的网络的循 环生成的序列，只要考虑生成这一序列的阶为N的循环群就够了。尤其是， 如果有不同的群生成元，每个RT能够生成一个涵盖网络所有可用的RB的 循环序列，对最优循环序列的寻求可以提炼为寻求最优生成元和群运算。循 环生成的序列可以通过所述MCG结构获得。通过考虑这些序列的循环移位 的版本使这些序列丰富。详细来说，应用循环移位s到一个序列，以s个槽 位循环地旋转其条目，其中s∈{0,...,N-1}。可以通过穷尽搜索选择群生成元 和循环移位来确保碰撞发生次数最低。尽管有最小化碰撞发生次数的优点， 所述MCG结构在全部循环生成的序列进行穷尽搜索会导致计算复杂化，从 而阻止其在有大量RT的系统中的使用。此外，把RB分配局限于MCG结构 生成的序列会限制系统的RB数量并限制所述MCG结构序列的最优化保证。 这些缺点会通过下面提出的技术来减轻。

循环生成的RB分配序列对MCG结构的限制有两个缺点：第一，RB的 数量N必须等于P-1，其中P为质数；第二，限制向阶为N＝P-1的MCG的 生成元中搜索最优群生成元。因此，在循环群生成元子集中进行的穷尽搜索 只能保证所述MCG结构中的最优性。

将对RB分配序列的搜索扩展到所有循环生成的序列的集合可以减轻这 些缺点。该扩展消除了RB数量的限制并且保证了穷尽搜索得到所有循环生 成序列的集合中的全局最优RB分配序列。该扩展的关键在于观测RB分配 序列的性能唯一依赖于序列结构而不是实际的实体且该结构不受所述群运算 的约束。后面的观测遵循循环群的一个基本属性，称为群同构，下面会有描 述。

群论中的基本结果显示存在将一个循环群的实体与另一个循环群的实体 以相同的阶进行映射的结构保护功能。所述功能称为群同构，下面是其正式 的定义：

例4：使G和成为同阶的两个循环群。同构一对一映射，遵 守群运算，即，若x,y∈G，则且F(xy)＝F(x)F(y)。

注意：尽管使用并列的方式表示G和的群运算，这些运算通常不同。

例4意指同构F能够看作是将G中的每个元素映射为中的元素的重新 标签功能。类似地，例2和例3意指有φ(N)个不同的循环序列，每个对应一 个不同的群生成元。要注意的是，虽然一个循环群的群生成元的集合依赖于 底层的群运算，该集合的势φ(N)不依赖于该运算。因此，限制对循环生成的 序列的关注将候选RB分配序列的数量由N！降低到φ(N)。φ(N)个序列的条目 还依赖于所述群运算，确定最佳运算表面上仍然是一项艰巨的任务。然而幸 运的是，确定哪个运算并不重要。证明上述结论的关键步骤可由以下引理推 知。

引理1：阶为N的任何循环群A_N与加法循环群(简称ACG)同构， (Z_N,+)＝{0,1,2,...,N-1}，与A_N底层的群运算无关。通过引理1和例4得出以 下定理：

定理1：针对阶为N的任何循环群G_N，存在同构F，因此G_N的底层的 群运算循环生成的序列的集合与Z_N的底层的加法群运算循环生成的序列的 集合同构。

可以表明该定理中的同构F可能不是唯一的，因此，当F改变时，G_N中 给定的循环生成的序列可以与Z_N中不同的循环生成的序列同构。然而，对 于任何循环群G_N，存在至少一个同构将所有其循环生成的序列的集合与Z_N中循环生成的序列的唯一集合进行映射。

在论述引理1对提出的RB分配技术的产生的启示之前，先以一个说明 性的例子来论证。

例5：考虑阶为N＝10的两个循环群G_N和Z_N，分别带有乘法和加法群运 算。从例3可知，两个群的循环生成的序列的数量为φ(10)＝4。首先，对于 所述MCG结构，循环生成的序列的集合可以通过以下等式获得： 其中，g_i为G_N中第i群生成元，s_i是为其 循环生成的序列分配的循环移位。为了方便描述，该实例中的所有循环移位 设为0。相应地，所述MCG，G₁₀，循环生成的序列的集合如下表所示：

类似地，所述MCG结构循环生成的序列的集合可以通过 获得，其中，g_i为Z_N中第i群生成元，s_i是为其循环生成的序列分配的循环移位。相应地，所述ACG结构Z₁₀循环生 成的序列的集合如下表所示：

鉴于以下同构映射函数：F:G₁₀→Z₁₀:F((g₁＝2)^k(modN+1))＝k(modN)，两 个群结构的元素可以如下表所示进行映射：

将该映射应用到所述MCG结构循环生成的序列的集合中得到所述ACG 结构生成的序列。要注意的是，所述序列到序列的映射不是唯一的，在任何 同构函数F下，所述ACG结构循环生成的序列的完整集合可从所述MCG结 构生成的序列获得。

为了说明定理1的含义，考虑一个使用循环生成RB分配序列的中继辅 助蜂窝网络。系统中RT发生碰撞的次数只依赖于所利用的序列中RB的相 对位置。这意味着改变序列中条目的标签不会影响碰撞发生的次数。此外， 定理1表明同阶的任意群结构G循环和加法循环群Z循环生成的序列的集合 同构。由于所述同构为一对一映射，所述序列条目的相对位置会被维持。也 就是说，所述阶为N的循环生成序列的集合会一直具有相同的结构，该结构 与底层的群运算无关。因此，在Z_N循环生成的序列的集合上进行穷尽搜索 保证了阶为N的所有循环生成序列的集合中的最优性。尽管有最优性保证， 针对大量RT进行穷尽搜索的计算成本过高。因此，贪婪算法大大降低了序 列选择过程所需的计算成本。

为了方便实际终端中继情景下的RB分配，提出了按顺序选择循环生成 的序列的高效贪婪算法。所述算法的性能与穷尽搜索的性能相当，但其计算 复杂度要低得多。这一属性使得所述贪婪算法适用于RT和RB数量较多的 系统中的实际应用。

所述贪婪算法的实现依赖于群生成元和循环移位的配对，使得它们循环 生成的序列顺序相反。在所述贪婪算法的每次迭代中，选择一对群生成元和 相关的循环移位。这意味着所述算法可以在次迭代中穷尽所有可能的 群生成元对。

配对完所述群生成元后，在所述算法的第一次迭代中，随机选择一对以 及循环移位s＝0作为所述算法的初始基础。在剩余的次迭代中，每次 所述算法利用一对群生成元和相关的循环移位来扩大基础。详细来说，在第 r次迭代中，选择剩余的个群生成元对中的一对以及一个特定的 循环移位。在迭代中的选择技巧将在下文详细论述。然后，将选择的所述群 生成元对和其循环移位根据它们被选取的顺序列在查询表中。对于带有M个 RT的系统，第一M/2群生成元对和循环移位循环生成的表中的M个序列用 于分配RB。

这里配对方法基于在两个中继情况下发现最优生成元。此时，对最优循 环生成序列的寻求可以提炼为寻求顺序相反的两个分配序列。详细来说，当 所述两个序列用于进行自主RB分配时，只要WT的数量小于可用RB的数 量，就不会有碰撞发生。由于每个循环序列由群生成元和循环移位生成，需 要找到生成相反序列的两个群生成元和它们相关的循环移位。对于任何群生 成元g和循环移位s，存在唯一生成序列相同但顺序相反的倒数(g^-1,s^-1)，其 中，g^-1为g的模块化算法倒数，满足：gg^-1≡e(modN+1),(3)，其中e为群 单位元，N为所述群的阶。能够很容易发现g和g^-1生成的序列顺序相反。因 此，分配给g^-1表示为s_-¹的循环移位必须要和分配给g的循环移位方向相反。 所述循环移位可以表示为s^-1＝N-s-1。例如，对于阶为N＝10的MCG，(1) 中的公式得到如下序列，所述序列为所述两个中继情况下的最优序列。

分配序列顺序选择：将S设为包含已经选择的算法基础的集合，U为包 含待选择的群生成元对的集合。首先，S为空，U包含个群生成元对。 在第一次迭代中，所述贪婪算法随机从U选择一对群生成元(g,g^-1)和循环移 位s，并移动(g,g^-1,s,s^-1)至S。不失一般性，s可以设置为0，s^-1设为N-1。 在随后的次迭代中的每一次中，所述算法针对所有可能的循环移位 s∈{0,...,N-1}检查剩余的每个群生成元对，即，还未在S中的群生成元对。 详细来说，所述算法在所有可能的循环移位估计每个剩余群生成元对生成的 序列和S中单独群生成元对生成的序列之间的成对碰撞次数。要注意的是， 对于能够适应统一和非统一WT分布的算法，选择所述群生成元对和循环移 位的度量标准一定不能依赖于RT的瞬间负载。因此，在估计一个群生成元 对的成对碰撞次数时，所述算法考虑所述RT上的系统负载的所有可能的分 布。

由于(g,g^-1,s,s^-1)生成的两个序列方向相反，可以表明这两个序列与S中 每个群生成元对和循环移位生成的序列引发的成对碰撞的次数相同。因此， 只要估计正在检查的一个群生成元对得到的序列和通过S中单独对得到的序 列之间的成对碰撞次数就可以了。这类似于设置3个RT，其中2个RT从S 处分配一个对，第三个RT从检查的对中分配一个群生成元。为了估计成对 碰撞次数，N×N的负载矩阵X_i与第i个RT相关，假设有群生成元g_i和循环 移位s_i。详细来说，X_i的行和列指数分别代表RB和第i个RT的负载水平。 详细来说，X_i的第(l₁,l₂)个条目表示第i个RT的负载水平为l₂时RBl₁的二 元状态。当该条目负载有l₂个WT时，若第i个RT分配RBl₁，则所述条目 被设置为等于1。类似的，当该条目负载有l₂个WT时，若第i个RT没有分 配RBl₁，则所述条目被设置为等于0。使用这种记号法，X_i的第(l₁,l₂)个条 目可以写成：

其中，为了详细阐述，假设群生成元和循环 移位对(g_i,s_i)和(g_j,s_j)针对第i和第j个RT分别得到分配序列(1,3,2,4)和 (3,2,4,1)。对应的负载矩阵X_i和X_j为$X_i=\left(\begin{array}{cccc}1& 1& 1& 1\\ 0& 0& 1& 1\\ 0& 1& 1& 1\\ 0& 0& 0& 1\end{array}\right)$和$X_j=\left(\begin{array}{cccc}0& 0& 0& 1\\ 0& 1& 1& 1\\ 1& 1& 1& 1\\ 0& 0& 1& 1\end{array}\right)---\left(4\right).$

当第i和第j个RT分别由l₁和l₂个WT负载时，X_i的第l₁列和X_j的第l₂列的内积等于碰撞的次数。该乘积由成对碰撞矩阵H_i,j的第(l₁,l₂)个条目给定， 其中，在显示{H_i,j}矩阵如何用于估计在满载的系统中所 有可能的负载组合上的成对碰撞的总次数之前，首先区分系统负载和每个中 继上分配的RB实际数量是有帮助的。因为RT引发的碰撞次数导致了所述 RT尝试分配的RB数量的增加。详细来说，当一个RB发生碰撞，例如， 所述RT本来第二个尝试分配于是放弃并分配其分配序列中的下 一个RB。因此，每个RT尝试分配的RB的实际数量可能大于其负载。为了 方便描述，考虑一个例子，其中，2个RT和其RB分配序列如下：

假设每个RT负载为k＝2WT。针对这一设置的碰撞总次数为1，这一次 碰撞发生在RB4。然而，在实际分配中，一旦检测到碰撞，第一个分配RB 4的RT保留RB4，而其他RT分配其分配序列中的下一个RB。在该举例中， 假设RT1第二个分配RB4，RT1放弃RB4并分配RB7给它的第二个WT。 此时，RB7发生又一次碰撞，该设置的实际碰撞总次数变为2。随后，RT1 和2的有效负载分别变为：k_{1,eff}＝2和k_{2,eff}＝3。幸运的是，这些有效负载可 以通过成对碰撞矩阵(5)进行估计。详细来说，考虑一种设置，其中，有 3个RT，2个RT2和RT3使用顺序相反的序列，即，一个群生成元对生成 的序列，而RT1使用不同的对中的群生成元生成的序列。如果2个RT2和 RT3在RT1之前第一个分配它们的RB，则k_{2,eff}＝k₂，k_{3,eff}＝k₃，k_{1,eff}可以 按照如下所述以迭代的方式进行估计。

图7示出了RT的有效负载的流程图。现在显示出所述{H_i,j}矩阵和RT 的有效负载如何用于估计在满载的系统中所有可能的负载组合上的成对碰撞 的总次数。为此，考虑一个满载的系统，即，系统负载有N个WT。将所述 接受检查的群生成元和其相关的循环移位表示为(g_i,s_i)，并将对应的负载矩 阵表示为X_i。类似的，将S中的所述群生成元对和其相关的循环移位表示为 并将对应的负载矩阵表示为X_j和在这种记号法中，用 于指示对应的负载矩阵。通过这些负载矩阵，(g_i,s_i)和 的序列之间所有可能的负载组合的成对碰撞总次数可以表示 为：$V_{i,j}=\underset{(k_1,k_2,k_3)\in Y}{\Sigma }{H}_{i,j}(k_{\{1,eff\}},k_2)+{\bar{H}}_{i,j}(k_{\{1,eff\}},k_3),---\left(6\right),$其中，k_m为RTm的负载， k_{1,eff}为RT1的有效负载，可以通过图7所示的技术进行估计， $Y\left\{(k_1,k_2,k_3)\right|{\Sigma }_{m=1}^3{k}_m=N,k_m\in N\},$H_i,j在(5)和${\bar{H}}_{i,j}{X}_i^T{\bar{X}}_j$中定义。通过(6)， (g_i,s_i)生成的序列和每个群生成元对与S中的循环移位生成的序列之间的成 对碰撞总次数可以表示为$I_i=\underset{(g_j,g_j^{-1},s_j,s_j^{-1})\in S}{\Sigma }{V}_{i,j}---\left(7\right).$

估计{I_i}之后，得到最小成对碰撞总次数I_i的群生成元对和相关的循环移 位扩大了所述算法基础S。所述算法继续迭代直到S包含所有个群生成 元对且|U|＝0。然后，将选择的所述群生成元对和其循环移位根据它们包含 在S中的顺序列在查询表中。要注意的是，顺序只依赖于成对碰撞次数，而 不依赖系统中RT的数量。这意味着对于RT少于φ(N)个的系统，所述贪婪 算法只要运行一次得到循环生成的序列的查询表就行了。因此，与穷尽搜索 方案相比，当WT切换到中继模式时，当前活动的RT不需要更新它们的分 配序列。图8示出了执行贪婪算法技术的流程图。

所述贪婪算法的计算复杂度：要估计所述贪婪算法的计算复杂度，需要 注意的是只有加法运算会导致对(6)中的V_i,j和(7)中的I_i进行估计的计算 成本。对(6)中的每个成对碰撞矩阵H_i,j进行估计所需的加法的数量以N³为界限，并且由于所述贪婪算法的每次迭代考虑3个RT的设置，由此断定 Y的势等于100％负载(即，K＝N个WT)可以分割为3个有序的部分的途 径的数量，其中K是3个RT的总负载。这个数字由给定。因此，在 所有可能的循环移位s∈{0,...,N-1}计算选择的群生成元i和S中每个群生成对 之间的成对碰撞次数所需的加法运算的数量可以以 $2N^4+2N\left(\begin{array}{c}N-1\\ 2\end{array}\right)=2N^4+N^3-3N^2+2N=O\left(N^4\right)---\left(8\right)$为界限。

由于群生成元对的数量由给定，在次迭代中的每次迭代中， 两个集合U和S中的每个中的群生成元对的数量可以以为界限。因此， 所述贪婪算法获得循环序列所需的加法运算的数量可以以 $(2N^4+N^3-3N^2+2N){(\frac{\phi \left(N\right)}{2}-1)}^3---\left(9\right)$为界限。

从(9)能够看出所提出的贪婪算法的计算复杂度为N的多项式。详细 来说，由于φ(N)<N，所述贪婪算法的计算复杂度以O(N⁷)为界限。相比之 下，所述穷尽搜索的复杂度以$\frac{1}{2}M(M-1)N^M\left(N^2\right(N-1)+\left(\begin{array}{c}N-1\\ H-1\end{array}\right))$为界限。

比较(9)和(10)可以看出所述穷尽搜索的计算复杂度为RT数量的指 数M，而所述贪婪算法的复杂度不受M的约束。

图示度量标准：本发明各方面提供了一种高效贪婪算法，与穷尽搜索相 比，该贪婪算法可以以明显较低的计算复杂度获得RB分配序列。详细来说， 在每次迭代中，所述算法按顺序选择(7)中使成对碰撞总次数最小化的群 生成元对和其相关的循环移位。然而，对分配序列的细心检查揭示了位于每 个序列开头的RB，也称为有效RB，是使系统招致碰撞的最主要的推动者。 这是因为即使在系统负载较轻的情景中，这些RB仍然会由RT分配给对它 们通信的WT。因此，为了降低碰撞发生的次数，应该选择所述循环生成的 序列，这样每个序列的有效RB是唯一的。为了实现这一目标，本发明各方 面提出一种贪婪算法的近似度量标准，该贪婪算法使用了所述RB分配序列 的顺序选择中循环群的图形表示。详细来说，在配对所述群生成元之后，每 对的循环生成序列用于生成唯一一个连接所有群元素的图样。随后，对每对 生成的所述图样中的有效RB的集合进行标记，即，每对(g,g^-1,s,s^-1)循环生 成的序列的开头部分的元素。根据上面描述的贪婪算法的相同步骤，将S设 为包含已选择的算法基础的集合，U为包含待选择的群生成元对的集合。首 先，S为空，U包含个群生成元对。在第一次迭代中，所述贪婪算法随 机从U选择一对群生成元(g,g^-1)和循环移位s＝0，并移动(g,g^-1,s,s^-1)至S。在 随后的次迭代中的每一次中，所述算法针对所有可能的循环移位 s∈{0,...,N-1}检查剩余的每个群生成元对，即，还未在S中的群生成元对。 详细来说，为每个群生成元对生成一个唯一的图样并估计每个图样的有效 RB和S中群生成元对生成的RB之间发生的碰撞次数。然后，得到最小碰撞 发生次数的图样对应的群生成元对和循环移位扩大了所述集合S。

循环群的图形表示：根据图论，循环群的图形表示为一个连接群中所有 元素的圆，其中群元素位于圆的周长上。这个圆可以从任何群生成元对，即， 群生成元和其逆元，所生成的序列构建。每个剩余序列以及剩余群生成元对 生成的序列通过连接图9所示的所有群元素的唯一图样构成所述循环图。

图9示出了阶为10的MCG的图形表示。所述循环群有两对群生成元。 一对用圆表示，另一对用内部图样表示。

通过在对应的循环生成的序列上应用循环移位，每个图样可以按顺时针 或逆时针方向旋转。要注意的是，循环群的图形表示是唯一的且只依赖于所 述循环群的阶。也就是说，所述图形表示不依赖于构建圆所选用的群生成元 对。利用该图形表示，所提出的图形贪婪算法按顺序选择图样，从而将有效 RB之间的碰撞次数降到最低。下面详细描述所述贪婪算法顺序选择。

图示序列选择度量标准：配对所述群生成元和循环移位后，在第一次迭 代中，随机选择一对并添加到算法基础集合S中。使用循环生成的序列构建 所述循环群的图形表示，即，连接所有RB的圆。标记这两个循环生成的序 列中的有效RB。要注意的是RB对碰撞发生的平均次数的贡献随着其在序 列中的位置相应减小。详细来说，所述序列中的第一个RB对碰撞发生的平 均次数的贡献最大，而最后一个RB的贡献最小。因此，当使用图形估计序 列时，只考虑序列i中前A_i个RB。所述集合A_i称为有效RB的集合。在随后 次迭代中的每一次，所述算法随机选择U中的一个群生成元对，构建 其图样并标记其有效的RB。通过循环移位旋转所述图样，从而使其有效RB 和S中群生成元对构建的图样的有效RB之间的碰撞次数降到最低。对U中群 生成元对生成的所有图样重复该相同的流程。估计完U中每个图样招致的碰 撞次数后，获得有效RB之间最小碰撞次数的图样对应的群生成元对和相关 的循环移位扩大所述算法基础S。所述算法继续进行迭代，直到然后，将选择的所述群生成元对和其循环移位根据它们包含在S中的顺序列 在查询表中。在图示的度量标准的一个例子中，对所有的i考虑所述MCG G₁₀并假设A_i＝2。这种循环群有两对群生成元，其循环生成的序列显示在下 表中：

标记了有效RB的两对的对应图样如图9所示。由于所述图样的有效 RB之间存在冲突，所述内部图样按照循环移位s＝1顺时针旋转。最后产生 的图样如图10所示。旋转过后，两个图样的有效RB之间不再有碰撞发生。

图10示出了所述图形贪婪算法的伪代码。改变初始基础对图示的度量 标准的影响：如上文所述，配对完所述群生成元之后，在第一次迭代中，所 述贪婪算法通过U中的任意对增大集合S。尽管为所述初始基础选择一个不 同的群生成元对会改变群生成元对添加到S中的顺序，但不会影响所选序列 的有效RB之间的碰撞发生次数。为了对此说明，要注意的是循环群的图形 表示是唯一的且只依赖所述群的阶。因此，即使选择了不同的初始基础，U 中的剩余对仍然会生成一样唯一的图样。由于图示贪婪算法的度量标准只依 赖于所述图样中的有效RB之间发生碰撞的次数，选择图样的顺序不会改变。 其次，选择的所述群生成元对招致的总碰撞次数也不会改变。因此，改变初 始基础不会影响所述图形度量标准。

所述图形贪婪算法的计算复杂度：为了估计提出的所述图形贪婪算法相 关的计算复杂度，需要注意的是，只有加法运算会造成估计每对有效RB之 间的碰撞发生次数的计算成本。详细来说，对于有N个RB的系统来说，估 计两对生成的序列的有效RB之间的碰撞次数所需的加法运算的数量以2N 为界限。由于每个序列要在所有可能的循环移位s∈1,...,N进行估计，估计每 个循环生成的序列在所有可能的循环移位关联的复杂度可以以2N²为界限。 由于群生成元对的数量由给定，在次迭代中的每次迭代中，两 个集合U和S中的每个中的群生成元对的数量可以以为界限。因此， 所述贪婪算法获得循环序列所需的加法运算的数量可以以 $\left(2N^2\right){(\frac{\phi \left(N\right)}{2}-1)}^2\le 2N^4---\left(11\right)$为界限。

从(9)可以看出提出的所述贪婪算法的计算复杂度是N的多项式，且 大大低于等式(9)和(10)给出的分析度量标准和穷尽搜索的计算复杂度。

在终端中继情景中，RT的移动性和大量个数在获取CQI时需要大量开 销。因此，蜂窝网络用户容量下降。另一方面，盲目资源分配需要一个计算 成本过高的过程，以在庞大的分配序列的集合上进行RB分配优化。本发明 各方面提出一种按顺序选择各个RT采用的RB分配序列的贪婪算法。尽管 是次最优的，提出的所述算法具有和通过穷尽搜索发现的最优序列性能相当， 但其计算成本却大大降低了。此外，本发明通过群同构表明了搜索所述 ACG结构循环生成的序列的集合得到的最优分配序列是相同顺序下所有循 环生成的序列的集合中是全局最优的。[98]到[101]包含的对群同构的验证与 本发明无关，因此可以省略。

考虑阶为N的两个有限循环群(G_N,*)＝{1,...,N}和(Z_N,+)＝{0,...,N-1}。设 g₁和g₂为所述循环群G_N的两个不同的群生成元。设F为同构函数 $\{F:G_N\to Z_N:F\left(g_1^k\right(\mathrm{mod}N+1)=k(\mathrm{mod}N)\}.$然而，由于所有循环群与Z_N同构， 参照引理1：存在至少一个对G_N和Z_N的元素进行映射的同构函数。由例4 可知，存在两个群生成元其中，z₁＝F(g₁)且z₂＝F(g₂)。目标在 于表明g₁和g₂循环生成的序列与z₁和z₂生成的序列同构。

对于循环群G₁，将(1)应用于所述群生成元g₁和g₂获得循环生成的序 列$S_1=\left(g_1^1\right(\mathrm{mod}N+1),g_1^2(\mathrm{mod}N+1),...,g_1^N(\mathrm{mod}N+1\left)\right),---\left(12\right)$和 $S_2=\left(g_2^1\right(\mathrm{mod}N+1),g_2^2(\mathrm{mod}N+1),...,g_2^N(\mathrm{mod}N+1\left)\right)---\left(13\right).$

应用所述同构F于(12)的元素中得到S₁＝(1,2,...,0)(14)。假定G_N的任何一个群生成元生成的序列涵盖整数1到N的整个序列，则存在整数 1≤q≤N，从而$g_2=g_1^q(\mathrm{mod}N+1).$由于${\left(g_1^q\right(\mathrm{mod}N+1\left)\right)}^m(\mathrm{mod}N+1)=g_1^{mq}(\mathrm{mod}N+1),$将代入(13)得到： $S_2=\left(g_1^q\right(\mathrm{mod}N+1),g_1^{2q}(\mathrm{mod}N+1),...,g_1^{Nq}(\mathrm{mod}N+1\left)\right)---\left(15\right).$和(14)类似，应 用同构函数F于(15)得到：S₂＝(q(modN),2q(modN),...,Nq(modN))(16)。

应用F于g₁和g₂得到Z_N中对应的群生成元z₁和z₂，即， z₁＝F(g₁(modN+1))＝1,(17)； $z_2=F\left(g_2\right(\mathrm{mod}N+1\left)\right)=F\left(g_1^q\right(\mathrm{mod}N+1\left)\right)=q\left(\mathrm{mod}N\right)---\left(18\right).$对于加法循环群Z_N， 应用(2)于所述群生成元z₁和z₂得到循环序列S₃和S₄， S₃＝(z₁(modN),2z₁(modN),...,Nz₁(modN)),(19)； S₄＝(z₂(modN),2z₂(modN),...,Nz₂(modN))(20)。将(17)和(18)代入(19) 和(20)得到S₃＝(1,2,...,0)(21)；S₄＝(q(modN),2q(modN),...,Nq(modN)) (22)。从(12)、(13)、(21)和(22)能够看出所述循环群G_N生成 的序列S₁和S₂与所述加法循环群Z_N生成的序列S₃和S₄同构。

至于具有CQI的蜂窝网络的动态资源分配，建议使用动态部分频率重用， 其中，基于用户反馈来更新每个部分分配的资源集从而降低干扰[11]。

至于不具有CQI的蜂窝网络的动态资源分配，在缺少CQI和集中协调 的情况下建议对资源进行随机分配[4]。

至于带有自组织中继终端的蜂窝网络的动态资源分配，建议采用基于乘 法循环群结构循环生成的序列的中继辅助蜂窝网络的自主RB分配方案。假 设中继终端(简称RT)之间没有协作，基站或者RT中不存在CQI[5]。

上述前两种分类解决的不是同一个问题。详细来说，这些方案旨在用于 无辅助的蜂窝网络。但是，它们可将每个中继视为小区从而延展到中继辅助 蜂窝网络。此外，上述第二类考虑了非结构化随机分配序列。

至于带有自组织中继终端的蜂窝网络的RB分配，非活动的无线终端作 为RT将其他用户的信号中继给基站。RT之间没有协作。假设BS或RT上 不存在CQI。RT根据分配序列为对它们通信的WT分配资源。由于缺少 CQI，干扰的测量依据碰撞的发生来进行。碰撞是指一个RB被同时分配给 多个无线终端的事件。

对于有N个RB的系统来说，存在N！个序列，对于大数值的N来说这 是一个非常大的数字。一个序列生成元只能生成这些序列的一个子集。所述 序列的子集被称为循环生成的序列。N个元素序列中的每一个由具有N个元 素的循环群的群生成元生成。

每个循环生成的序列涵盖系统中所有可用的RB。这使得每个中继可以 获得所有可用的RB并使所述网络适应不均匀用户分布。循环生成的分配序 列的选择对系统中的碰撞次数和干扰有重大影响。

一实施例提供了一种带有自组织中继终端的蜂窝网络的基于贪婪算法的 高效自主资源块分配方案。实施例中的RB分配方案进行以下一个或多个操 作。不需要BS的集中协调。允许每个中继终端获得所有RB。使用单个序 列生成元可轻易生成的分配序列。不需要BS和RT上有CQI。选择不受RT 数量约束的分配序列集合。详细来说，在新的RT进入所述系统时，不应该 影响其相邻的RT所使用的序列。高效地选择分配序列减少碰撞发生的可能 性。要注意的是，如果分配所有RB，那么碰撞无法避免。具有线性计算复 杂度(不像穷尽搜索，其复杂度成指数倍增)，因此可以用于有大量RB的 系统。[110-113]已经覆盖在[65-73]，应该删除以避免重复。

一实施例提供了一种中继终端要使用的选择循环生成的RB分配序列的 贪婪算法。所述算法按顺序选择所述循环生成的RB分配序列。所述选择过 程在系统启动前离线时进行。所述算法以循环群的图形表示为基础。所述算 法的计算复杂度大大低于穷尽搜索的计算复杂度。因此，所述算法适用于有 大量RT和WT的实际系统。选择的所述循环生成的序列不受系统中活动的 RT数量的约束。

在所述基于贪婪算法的循环分配算法中，度量标准为所有系统负载比例 (0％-100％)下的所有可能的负载组合中的平均碰撞次数。该度量标准允许 所述方案容适应不均匀用户分布。位于每个序列开头的RB对平均碰撞发生 次数的贡献最大。主要目的在于将导致最大碰撞发生次数的RB有序地分开。

下面通过简单的举例来加以说明。系统中有N＝10个RB和最有效的元 素，选择对所述平均碰撞次数贡献最大的RB作为每个序列的前两个元素。

在一个示例性基于贪婪算法的循环分配算法中，群生成元成对进行分离。 任意选择一对群生成元并添加到算法基础的空集S中。将循环图构建成连接 一个群生成元对生成的序列的所有元素的圆。元素1和6以及元素2和4分 别是所述两个群生成元生成的序列的前两个元素。

任意选择另外一对，构建其群生成元中的一个生成的图样。估计选择的 所述群生成元对生成的序列的前两个元素与所述集合S中群生成元对生成的 元素之间的总冲突(图中共同节点)。元素8和9指选择的所述生成元对中 的一个生成的序列的前两个元素。

通过循环移位旋转所述内部图样，估计这一设置中冲突的总次数。对所 有循环移位重复该同一过程。最小冲突次数以及其循环移位与选择的群生成 元对相关联。因此，任意选择另一对，依据冲突发生的次数在所有可能的循 环移位对其性能进行估计。通过循环移位旋转所述内部图样。

在估计完所有可用的群生成元对的性能后，将产生冲突次数最少的群生 成元对移到选择的群生成元对集合S。下面的迭代开始于更新后的集合S， 在每次迭代中，增加一个群生成元对到S。重复同一过程直到穷尽所有的群 生成元对。然后，所述中继终端将集合S用作选择循环生成的序列的查询表。 中继终端以其存储在所述集合S中的顺序选择其他RT没有使用的循环生成 的序列。

下面是所述算法的伪代码：

把循环移位s＝0的群生成元对移至算法基础的集合S

对每次迭代

对所有未在S的对

对所有可能的循环移位

通过使用当前循环移位和选择的群生成元对中的一个群生成元生成循环 分配序列

估计所述生成的序列中第一预定数量的元素和S中存储的群生成元和循 环移位生成的元素之间的冲突次数

结束

将最小碰撞次数以及其对应的循环移位与所述群生成元对关联

结束

把产生最小碰撞次数的群生成元对添加到算法基础集合S

结束

实施例中的基于贪婪算法的RB分配序列选择方案按顺序选择循环生成 的RB分配序列。所述算法的计算复杂度成线性增长，而不像穷尽搜索的复 杂度成指数倍增。因此，所述算法适用于实际中有大量RB和WT的系统。 所述循环生成的序列集合S不受系统中中继终端(简称RT)的数量的约束。 因此，所述算法只可以在系统启动前离线时进行。在系统中增加额外的RT 不影响当前RT选择的循环生成的序列，从这种意义上说，所述贪婪算法选 择的序列集合是累积的。

实施例中基于贪婪算法的循环分配提供了比随机分配更好的性能，随机 分配无法提供性能保证。实施例中的循环贪婪算法分配不需要有CQI。使用 的循环生成的序列对任何中继终端能够使用的RB的数量没有限制，且不需 要RT之间的协作。实施例中的循环贪婪算法分配的计算复杂度远远低于穷 尽算法的计算复杂度。因此，适用于任意数量的RT和RB。所述贪婪算法 选择的序列集合是累积的，在新的RT进入网络时不需要活动的RT去更新 它们的序列。

图12和13示出了仿真结果，展示了不同系统负载程度下在所有可能的 系统相关负载的负载组合中的平均碰撞次数。

实施例中的基于贪婪算法的序列选择方案适用于任意数量的RT和WT。 实施例中的方案不需要有CQI也不需要RT之间的任何协作。因此，该算法 降低了网络中的信令开销。仿真结果显示实施例中的基于贪婪算法的方案提 供了与穷尽搜索相当的性能同时计算复杂度却低得多。所述算法获得的序列 的累积集合使得所述方案对RT数量随时间变化的实际系统来说非常有吸引 力。本实施例可以在无线网络和设备中实现，如机器到机器通信系统、终端 中继等。

Y.Fouad,R.Gohary和H.Yanikomeroglu发表的名称为“AnEfficient Greedy-BasedAutonomousResourceBlockAssignmentSchemeforCellular NetworkswithSelf-OrganizingRelayingTerminals”的附属文档以引入的方式 并入本文。

图14是一种用于实现本发明设备和方法的处理系统的框图。特定装置 可利用所有所示的组件或所述组件的仅一子集，且装置之间的集成程度可能 不同。此外，设备可以包括部件的多个实例，例如多个处理单元、处理器、 存储器、发射器、接收器等。处理系统可以包括配备一个或多个输入/输出 设备，例如扬声器、麦克风、鼠标、触摸屏、按键、键盘、打印机、显示器 等的处理单元。处理单元可以包括中央处理器(简称CPU)、存储器、大容 量存储器设备、视频适配器以及连接至总线的I/O接口。

总线可以是任意类型的若干总线架构中的一个或多个，包括存储总线或 存储控制器、外设总线、视频总线等等。所述CPU可包括任何类型的电子 数据处理器。存储器可包括任意类型的系统存储器，例如静态随机存取存储 器(简称SRAM)、动态随机存取存储器(简称DRAM)、同步DRAM (简称SDRAM)、只读存储器(简称ROM)或其组合等等。在实施例中， 存储器可包括在开机时使用的ROM以及在执行程序时使用的存储程序和数 据的DRAM。

大容量存储器设备可包括任意类型的存储设备，其用于存储数据、程序 和其它信息，并使这些数据、程序和其它信息通过总线访问。大容量存储器 设备可包括如下项中的一种或多种：固态磁盘、硬盘驱动器、磁盘驱动器、 光盘驱动器等等。

所述视频适配器和I/O接口提供了将外部输入和输出设备耦合到所述处 理单元的接口。如图所示，示例性输入、输出设备包括与所述视频适配器耦 合的显示器以及和I/O接口耦合的鼠标/键盘/打印机。其他设备可以与所述 处理单元耦合，可以使用额外的或者更少的接口卡。例如，可使用如通用串 行总线(简称USB)(未示出)等串行接口将接口提供给打印机。

所述处理单元还包括一个或多个网络接口，其中，所述网络接口包括有 线链路，如，以太网电缆，和/或无线链路以接入节点或不同的网络。所述 网络接口允许所述处理单元通过网络与远端单元通信。例如，所述网络接口 可能通过一个或多个发射机/发射天线和一个或多个接收机/接收天线提供无 线通信。在一个实施例中，处理单元耦合到局域网或广域网上以用于数据处 理以及与远端设备通信，所述远端设备例如其它处理单元、因特网、远程存 储设施或其他。

图15示出了一种通信设备1500的实施例的框图，所述通信设备可以等 同于上述一个或多个设备(如，UE和NB等)。所述通信设备1500可包括 处理器1504、存储器1506、蜂窝接口1510、补充接口1512和回程接口 1514，可以(或可以不)如图15所示分布。所述处理器1504可以是任何能 够进行计算和/或其它处理相关任务的组件，所述存储器1506可以是任何能 够为所述处理器1504存储程序和/或指令的组件。所述蜂窝接口1510可以是 任何允许所述通信设备1500通过蜂窝信号进行通信的组件或组件的集合， 并且可以用于通过蜂窝网络的蜂窝连接接收和/或传输信息。所述补充接口 1512可以是任何允许所述通信设备1500通过补充协议进行数据通信或信息 控制的组件或组件的集合。例如，所述补充接口1512可以是用于按照无线 保真(简称Wi-Fi)或蓝牙协议进行通信的非蜂窝无线接口。或者，所述补 充接口1512可以是有线接口。所述回程接口1514，可选地，可以包含在所 述通信设备1500中，可包括任何允许所述通信设备1500通过回程网络与其 他设备通信的组件或组件的集合。

尽管进行了详细的描述，但应理解，可在不脱离由所附权利要求书界定 的本发明的精神和范围的情况下，对本文做出各种改变、替代和更改。此外， 本发明的范围不希望限于本文中所描述的特定实施例，所属领域的一般技术 人员将从本发明中容易了解到，过程、机器、制造工艺、物质成分、构件、 方法或步骤(包括目前存在的或以后将开发的)可执行与本文所述对应实施 例大致相同的功能或实现与本文所述对应实施例大致相同的效果。相应地， 所附权利要求范围包括这些流程，机器，制造，物质组分，构件，方法，及 步骤。

以下参考与本申请的主题相关。每个参考文件以全文引入的方式并入本 文中。

·[1]T.C.-Y.Ng和W.Yu，“Jointoptimizationofrelaystrategiesandre- sourceallocationsincooperativecellularnetworks”IEEEJ.Select.Areas Commun，第25卷，328-339页，2007年2月

·[2]T.Wang,G.B.Giannakis和R.Wang，“Smartregenerativerelaysfor link-adaptivecooperativecommunications”IEEETrans，Commun，第56卷， 2008年11月

·[3]W.Rhee和J.Cioffi，“IncreaseincapacityofmultiuserOFDMsystem usingdynamicsubchannelallocation”Proc.IEEEVehic.Tech.Conf.(VTC)， (VTC)，(东京)，2000年5月

·[4]C.Koutsimanis和G.Fodor，“Adynamicresourceallocationscheme forguaranteedbitrateservicesinOFDMAnetworks”Proc.IEEEInt.Conf. Commun.(ICC)，(北京)，2008

·[5]Y.M.Fouad,R.H.Gohary和H.Yanikomeroglu，“Anautonomousre- sourceblockassignmentschemeforofdma-basedrelay-assistedcellularnetworks” IEEETrans.WirelessCommun，第11卷，637–647页，2012年2月

·[6]Z.Kostic和N.Sollenberger，“Performanceandimplementationof dynamicfrequencyhoppinginlimited-bandwidthcellularsystems”IEEETrans. WirelessCommun，第1卷，28–36页，2002年1月

·[7]P.Popovski,H.Yomo,S.Aprili和R.Prasad“Frequencyrolling:Aco- operativefrequencyhoppingformutuallyinterferingWPANS”，Proc.ACMInt. Symp.MobileAdHocNtwk.Computing(MOBIHOC)，(东京)，2004年5 月

·[8]W.W.Adams和L.J.Goldstein，IntroductiontoNumberTheory，New Jersey：Prentice-Hall，Inc.，1976

·[9]S.Roman，FundamentalsofGroupTheory：AnAdvancedApproach. Boston：Springer，2011

·[10]J.A.Gallian，ContemporaryAbstractAlgebra，Boston：Houghton Mifflin，1998

·[11]A.L.Stolyar和H.Viswanathan，Self-OrganizingDynamicFractional FrequencyReuseinOFDMASystems，INFOCOM，IEEE，691-699页(2008)

虽然已参考说明性实施例描述了本发明，但此描述并不意图限制本发明。 所属领域的技术人员在参考该描述后，将会明白说明性实施例的各种修改和 组合，以及本发明其他实施例。因此，所附权利要求书意图涵盖任何此类修 改或实施例。