信道分配优化方法及信道分配优化设备

摘要

本发明提出了基于多次迭代的信道分配优化方法和信道分配优化设备。信道分配优化方法包括信道分配优化路径搜索阶段和信道切换阶段。在信道分配优化路径搜索阶段中，IBS通过多次迭代，与相邻基站协商以发现信道分配优化路径。仅在成功发现可行的信道分配优化路径后，IBS及其相邻基站启动信道切换过程，从而可以避免无用的信道切换。此外，为了避免在迭代过程中的不能及时收敛问题，预先设置迭代次数的阈值。一旦当前迭代次数＞该阈值，在当前信道上的信道分配优化路径搜索过程将停止，并转至其它信道以发现另一路径。

说明书

技术领域

本发明涉及信道分配优化方法及信道分配优化设备，具体而言，涉及通过基于多次迭代的信道切换过程实现的信道分配优化方法及信道分配优化设备。

背景技术

在频谱共享中，将无线信道采用适当的方式分配给不同的系统从而实现系统间更好的共存是至为重要的。一方面，需要给具有重叠覆盖区域的相邻系统分配以不同的信道，从而避免相邻系统间的共信道干扰。如图1所示，由于系统1和系统2彼此相邻，需要给系统1和系统2分配不同的信道，使得BS(基站)1与从属于BS1的SS(用户站)1之间的传输将不会对BS2与从属于BS2的SS2之间的通信链路产生干扰。另一方面，需要确保尽可能多的系统能够获得专有信道满足其传输需求。否则，未能成功获得专用传输信道的这些系统不得不与其它系统共享无线信道，甚至中止其当前的传输工作。显然，在这种情况下，频谱利用率将会降低，业务的QoS(业务质量)不能得到很好的保证；换言之，系统间不能实现有效的共存。

一般而言，在频谱共享中，不存在一个全局的中央控制器实现跨系统的无线资源管理。此外，在集中模式下实现跨系统的全局信道分配优化需要中央控制器收集/保持诸多信息，加之网络拓扑的动态变化将加重传播这些信息的负荷；因此，集中式的全局信道分配优化方式难以在实际网络建设中得到应用。在这种情况下，可选方式是在分布式模式下实现信道分配，其中每个系统自适应地选择其工作信道。

当前，IEEE 802.16h标准规定了一种信道分配优化的过程，以便为IBS(初始化基站)获得专用信道：首先，IBS尝试通过频谱感测过程发现空闲(无干扰)信道；如果IBS未能发现任何空闲信道，则应通过使其相邻基站的工作信道切换至其它空闲信道，即通过改变相邻系统的信道分布，从而腾出空闲信道作为自己的专有工作信道。

然而，IEEE 802.16h仅定义了单跳的信道分配优化机制，这意味着IBS仅要求其相邻基站切换工作信道来为其腾出空闲信道。如果IBS不能发现：在某个信道上所有相邻基站都具有一个备份空闲(backup idle)信道，则通过802.16h中定义的信道分配优化的过程IBS将无法获得一个空闲信道作为其专用信道。

图2示出了在获得空闲信道用于工作信道之前，IBS(BS5)及其相邻基站的初始信道分配示意图以及初始信道分配信息。如图2所示，IBS的初始信道分配信息包括每个信道上的相邻基站的ID，以及这些相邻基站的backup_idle信道等，其中BS1、BS2、BS4、BS6、BS7和BS8均是BS5的相邻基站，而BS 3和BS 9为是BS 5的相邻基站的相邻基站。假设有三个信道可以分配给各个基站，在此分别使用不同的阴影表示。

如图2所示，BS1和BS7均工作于信道1上。然而，由于BS7没有backup_idle信道，所以BS5不能请求BS7和BS1切换至其它信道以腾出信道1作为BS5的工作信道，尽管BS1具有信道3作为backup_idle信道。类似地，BS5不能请求在信道2或信道3上的相邻基站切换至其它信道以腾出信道2或信道3作为自己的工作信道，因为工作于信道2或信道3上的这些相邻基站并不都具备backup_idle信道。在这种情况下，如果采用802.16h中定义的信道分配优化机制的话，BS5必须中止其传输，或必须与其它相邻基站共享信道来传输业务报文。然而，如果当前的信道分配可以通过某种机制改变为图3中所示的信道分配情况，则BS5可以获得一个专用工作信道。显然，在这种情况下，与802.16h中定义的信道分配优化机制相比，此种新机制可以得到提高频谱效率，且能更有效地保证BS5的服务质量(QoS)。

因此，期望设计此种信道分配优化机制，以便于系统间更好的共存。

发明内容

本发明提出了一种基于多次迭代的分布式信道分配优化机制。

基本的信道分配优化过程分为两个阶段：信道分配优化路径搜索阶段和信道切换阶段。在信道分配优化路径搜索阶段中，IBS通过多次迭代，与其它基站协商以发现信道分配优化路径。在成功发现信道分配优化路径后，IBS及其它相邻基站启动信道切换过程，从而可以避免无用的信道切换。

此外，为了避免在迭代过程中不能及时收敛问题，预先设置迭代次数的阈值。一旦当前迭代次数＞该阈值，在当前信道上的信道分配优化路径搜索过程将停止，并转至其它信道以发现另一路径。

根据本发明的一方面，提供了一种通信系统中的信道分配优化方法，其中所述通信系统包括所述初始化基站、以及所述初始化基站的多级相邻基站。

在多级相邻基站中的当前级相邻基站处，所述方法包括步骤：接收来自上一级相邻基站的信道分配优化测试消息；确定是否存在在其上所有的下一级相邻基站均具有备份空闲(backup_idle)信道的信道；如果存在在其上所有的下一级相邻基站均具有备份空闲信道的信道，则向上一级相邻基站发送具有“可行”指示的信道分配优化应答消息；以及在从上一级相邻基站接收到信道切换请求消息时，请求在所述信道上工作的所有下一级相邻基站切换至其备份空闲信道；在从所有下一级相邻基站接收到具有“成功”指示的信道切换应答消息时，向上一级相邻基站发送具有“成功”指示的信道切换应答消息，并使当前级相邻基站工作于所述信道。

在当前级相邻基站处，所述方法还包括步骤：如果不存在在其上所有的下一级相邻基站均具有备份空闲信道的信道，则确定当前级相邻基站的级数是否超过了预定阈值；如果超过了预定阈值，则向上一级相邻基站发送具有“不可行”指示的信道分配优化应答消息；如果并未超过预定阈值，则根据工作在其上的下一级相邻基站的个数对各个信道进行分类；a)确定所述各个信道中是否仍然存在可供测试的信道；如果不存在可供测试的信道，则向上一级相邻基站发送具有“不可行”指示的信道分配优化应答消息；如果仍然存在可供测试的信道，则从所述可供测试的信道中选择具有最少个数的下一级相邻基站所工作的信道，作为当前级相邻基站的备选优化信道；以及向工作在所选信道上所有下一级相邻基站发送信道分配优化测试消息。

在当前级相邻基站处，所述方法还包括步骤：确定是否所有信道分配优化测试消息都获得了“可行”指示的信道分配优化应答消息；如果并非所有信道分配优化测试消息都获得了“可行”指示的信道分配优化应答消息，则回到a)；如果所有信道分配优化测试消息都获得了“可行”指示的信道分配优化应答消息，则向上一级相邻基站发送具有“可行”指示的信道分配优化应答消息；在从上一级相邻基站接收到信道切换请求消息时，请求在所选信道上工作的所有下一级相邻基站切换至其各自的备选优化信道或者备份空闲信道；在从所有下一级相邻基站接收到具有“成功”指示的信道切换应答消息时，向上一级相邻基站发送具有“成功”指示的信道切换应答消息，并使当前级相邻基站工作于所选信道。

在所述初始化基站处，所述方法包括步骤：在确定不存在空闲信道且不存在在其上工作的所有第一级相邻基站均具有备选空闲信道的信道的情况下，通过工作在其上的第一级相邻基站的个数对各个信道进行分类；确定所述各个信道中是否仍然存在可供测试的信道；如果仍然存在可供测试的信道，则从所述可供测试的信道中选择具有最少个数的第一级相邻基站的信道，作为所述初始化基站的备选优化信道；向工作在所选信道上所有第一级相邻基站发送信道分配优化测试消息。

在所述初始化基站处，所述方法还包括步骤：在从所有第一级相邻基站接收到具有“成功”指示的信道切换应答消息时，使初始化基站工作于其备选优化信道，所述备选优化信道为第一级相邻基站为初始化基站腾出的空闲信道。

优选地，所述初始化基站以及所述初始化基站的多级相邻基站均保存信道分配优化路径搜索结果的相关信息，以基于所述信息计算最优化的信道分配优化路径。

如果在任一级相邻基站处发生切换失败，则将以下各级已完成的切换恢复为原有状态，并向上一级相邻基站发送具有“失败”指示的信道切换应答消息。当将所述具有“失败”指示的信道切换应答消息逐级向上转发至所述初始化基站时，确定所述各个信道中是否仍然存在可供测试的信道；如果仍然存在可供测试的信道，则从所述可供测试的信道中选择具有最少个数的第一级相邻基站的信道，作为所述初始化基站的备选优化信道；向工作在所选信道上所有第一级相邻基站发送信道分配优化测试消息。

根据本发明的另一方面，提供了一种通信系统中的信道分配优化设备，其中所述通信系统包括所述初始化基站、以及所述初始化基站的多级相邻基站，在多级相邻基站中的当前级相邻基站处，所述信道分配优化设备包括：

信道分配优化路径搜索装置，被配置为：接收来自上一级相邻基站的信道分配优化测试消息；确定是否存在在其上所有的下一级相邻基站均具有备份空闲信道的信道；如果存在在其上所有的下一级相邻基站均具有备份空闲信道的信道，则向上一级相邻基站发送具有“可行”指示的信道分配优化应答消息；以及

信道切换装置，被配置为：在从上一级相邻基站接收到信道切换请求消息时，请求在所选信道上工作的所有下一级相邻基站切换至其各自的备选优化信道或者其备份空闲信道；在从所有下一级相邻基站接收到具有“成功”指示的信道切换应答消息时，向上一级相邻基站发送具有“成功”指示的信道切换应答消息，并将当前级相邻基站的工作信道切换至所选信道。

在当前级相邻基站处，信道分配优化路径搜索装置还被配置为：如果不存在在其上所有的下一级相邻基站均具有备份空闲信道的信道，则确定当前级相邻基站的级数是否超过了预定阈值；如果超过了预定阈值，则向上一级相邻基站发送具有“不可行”指示的信道分配优化应答消息；如果并未超过预定阈值，则通过工作在其上的下一级相邻基站的个数对各个信道进行分类；a)确定所述各个信道中是否仍然存在可供测试的信道；如果不存在可供测试的信道，则向上一级相邻基站发送具有“不可行”指示的信道分配优化应答消息；如果仍然存在可供测试的信道，则从所述可供测试的信道中选择具有最少个数的下一级相邻基站的信道，作为当前级相邻基站的备选优化信道；以及向工作在所选信道上所有下一级相邻基站发送信道分配优化测试消息。

在当前级相邻基站处，信道分配优化路径搜索装置还被配置为：确定是否所有信道分配优化测试消息都获得了“可行”指示的信道分配优化应答消息；如果并非所有信道分配优化测试消息都获得了“可行”指示的信道分配优化应答消息，则回到a)；如果所有信道分配优化测试消息都获得了“可行”指示的信道分配优化应答消息，则向上一级相邻基站发送具有“可行”指示的信道分配优化应答消息。

在所述初始化基站处，所述信道分配优化设备包括：信道分配优化路径搜索装置，被配置为：在确定不存在空闲专用信道且不存在在其上工作的所有第一级相邻基站均具有备选空闲信道的信道的情况下，通过工作在其上的第一级相邻基站的个数对各个信道进行分类；确定所述各个信道中是否仍然存在可供测试的信道；如果仍然存在可供测试的信道，则从所述可供测试的信道中选择具有最少个数的第一级相邻基站的信道，作为所述初始化基站的备选优化信道；向工作在所选信道上所有第一级相邻基站发送信道分配优化测试消息。

在所述初始化基站处，所述信道分配优化设备包括：信道切换装置，被配置为：

如果所有发往第一级相邻基站的信道分配优化测试消息都获得了“可行”指示的信道分配优化应答消息，则向相应的第一级相邻基站发送信道切换请求消息时，请求在所选信道上工作的所有下一级相邻基站切换至其各自的备选优化信道或者其备份空闲信道。在从所有第一级相邻基站接收到具有“成功”指示的信道切换应答消息时，将所述初始化基站的工作信道切换至其备选优化信道，所述备选优化信道为第一级相邻基站为初始化基站腾出的空闲信道。

优选地，所述信道分配优化设备还包括：装置，用于保存所述初始化基站以及所述初始化基站的多级相邻基站处的信道分配优化路径搜索结果的相关信息；以及装置，用于基于所述信息计算最优化的信道分配优化路径。

所述信道切换设备被配置为：如果在任一级相邻基站处发生切换失败，则将以下各级已完成的切换恢复为原有状态，并向上一级相邻基站发送具有“失败”指示的信道切换应答消息。

当在所述初始化基站处，信道切换设备接收到具有“失败”指示的信道切换应答消息时，所述信道分配优化路径搜索装置被配置为：确定所述各个信道中是否仍然存在可供测试的信道；如果仍然存在可供测试的信道，则从所述可供测试的信道中选择具有最少个数的第一级相邻基站的信道，作为所述初始化基站的备选优化信道；向工作在所选信道上所有第一级相邻基站发送信道分配优化测试消息。

附图说明

图1示出了多系统共存情形下的一般网络场景，在此场景下为提高频频效率需要执行优化信道分配机制；

图2示出了在获得空闲信道作为其专有工作信道之前，IBS(BS5)及其相邻基站的初始信道分配示意图以及初始信道分配信息；

图3示出了基于图2所示的初始场景的、根据本发明实现的信道分配优化示例；

图4示出了根据本发明的基于多次迭代的信道分配优化过程；

图5示出了根据本发明的多次迭代的信道分配优化机制初始化基站IBS所执行的方法流程；

图6示出了根据本发明的多次迭代的信道分配优化机制第k级相邻基站NB(k)所执行的方法流程；以及

图7示出了根据本发明实施例的信道分配优化设备。

具体实施方式

为了实现优化信道分配，本发明提出了一种基于多次迭代信道切换过程的分布式解决方案。即，IBS可以通过一次迭代过程来改变相邻基站的信道分配、或者二次迭代过程来改变相邻基站的相邻基站的信道分配...直至达到最大迭代次数，以腾出空闲信道作为其专有工作信道。

可以将基本的信道分配优化过程分为两个阶段：信道分配优化路径搜索阶段和信道切换阶段。在信道分配优化路径搜索阶段中，IBS与其它基站协商以发现信道分配优化路径，即，哪些基站需要将它们的当前工作信道切换至哪个信道以腾出空闲信道。在信道切换阶段，信道分配优化路径上的每个基站依次将当前工作信道切换至在信道分配优化路径搜索阶段中确定的可能信道。

应注意，信道分配优化路径搜索的方向与实际信道切换的方向相反。即，信道分配优化路径搜索的方向是：IBS→IBS的相邻基站→IBS的相邻基站的相邻基站→...；然而，信道切换的方向是：...→IBS的相邻基站的相邻基站→IBS的相邻基站→IBS。

还应注意，在信道分配优化路径搜索阶段中，每个基站应保存信道分配优化路径搜索结果的相关信息。因而在将来执行信道分配优化路径搜索时，系统可以利用所保存的信道分配优化路径信息来迅速发现信道分配优化路径。此外，一些距离-矢量算法(如Bellman-Ford算法)可以用于计算信道分配优化的最优路径(可采用最小信道切换次数作为度量标准)，以便为IBS腾出空闲信道。

令NB(1)表示IBS的相邻基站(一级相邻基站)；令NB(2)表示IBS的相邻基站的相邻基站，即，NB(1)的相邻基站(为论述方便，这里称之IBS的二级相邻基站)；...；令NB(k)表示NB(k-1)的相邻基站(IBS的k级相邻基站)。令NB(1)-ChX表示工作在信道X上的一级相邻基站；令NB(1)-ChX-1表示工作在信道X上的一级相邻基站1；令NB(2)-ChX表示工作在信道X上的二级相邻基站；...；令NB(k)-ChX表示工作在信道X上的k级相邻基站。

根据IEEE 802.16h标准所规定的信道分配优化方案，如果IBS通过侦听可以发现某个空闲信道，则可以直接选择空闲信道作为其专用工作信道。如果没有发现任何空闲信道，则IBS确定是否存在这样的信道：在该信道上所有NB(1)均具有backup_idle信道。如果存在(假设该信道是信道X)，则IBS向每个NB(1)-ChX发送“信道切换请求”消息，请求将每个NB(1)-ChX切换至其backup_idle信道。如果接收到该“信道切换请求”消息，则每个NB(1)-ChX将切换至其backup_idle信道，然后IBS可以获得信道X作为其专用工作信道。如果不存在这样的信道，IBS将不得不与其他系统共享信道或者暂停其业务报文的发送。

然而，根据本发明，在不存在在其上的所有NB(1)均具有backup_idle信道的信道的情况下，可以采用基于多次迭代的信道分配优化过程来为IBS腾出空闲信道。以下结合图4，对根据本发明的基于多次迭代的信道分配优化过程进行描述。

1)IBS根据在各个信道上工作的NB(1)的数目对这些信道进行分类，并选择具有最小数目的NB(1)的信道(记为信道X)。

2)IBS向每个NB(1)-ChX发送“信道分配优化测试”消息。在接收到该“信道分配优化测试”消息后，每个NB(1)-ChX确定是否存在在其上的所有NB(2)均具有backup_idle信道的信道。

3)如果NB(1)-ChX发现存在这种在其上的所有NB(2)均具有backup_idle信道的信道(记为信道Y)，则该NB(1)-ChX向IBS发送具有“可行”标记的“信道分配优化应答”消息。

例如，NB(1)-ChX-1可以发现这种信道：在此信道上的所有相邻基站可以通过切换他们当前的工作信道至backup_idle信道，从而为NB(1)-ChX-1腾出空闲信道。在此情况下，NB(1)-ChX-1将向IBS发送具有“可行”标记的“信道分配优化应答”消息。

4)如果没有发现这种信道，则NB(1)-ChX将进一步请求其相邻基站分别采用该信道分配优化路径搜索过程。如果NB(1)-ChX的相邻基站成功地发现了能够为NB(1)-ChX空出信道的优化路径，则NB(1)-ChX向IBS发送具有“可行”标记的“信道分配优化应答”消息；否则将向IBS发送具有“不可行”标记的“信道分配优化应答”消息。

5)在从NB(k-1)-ChM接收到“信道分配优化测试”消息之后，每个相邻基站(例如，NB(k)-ChN)执行与NB(1)-ChX类似的操作以发现优化路径。通过该路径，可以为NB(k-1)-ChM空出信道N。此外，为了避免将会无尽地执行该迭代过程(即，收敛问题)，预先设置迭代次数的阈值。因而在信道分配优化路径搜索阶段，如果NB(k)发现迭代次数＞该阈值，则将不再请求其相邻下一级基站启动信道分配优化路径搜索过程。在这种情况下，将向NB(k-1)-ChM发送具有“不可行”标记的“信道分配优化应答”消息。

6)NB(1)-ChX应保留关于信道分配优化路径搜索结果的信息，包括信道切换次数、发送路径搜索请求的基站ID、期望切换至的信道等。

7)如果IBS接收到所有具有“可行”标记的“信道分配优化应答”消息，则成功地发现了一条可行的信道分配优化路径。通过该路径上基站的信道切换操作，可以为IBS腾出一条空闲信道，因此IBS将转入信道切换阶段。

8)如果IBS从某个相邻基站接收到任何具有“不可行”标记的“信道分配优化应答”消息(IBS对其发送了请求)，或者在等待预定时间之后仍未收到某个“信道分配优化测试”消息的应答信息，表明不能通过信道切换过程将腾出当前所测试的信道为IBS所用。因此，IBS将尝试在其他信道上进行类似的信道分配优化过程。即，IBS将选择所剩下的具有最小数目的NB(1)的可能信道，继续执行步骤2)、3)、4)、5)、6)、7)以发现优化路径。

9)如果测试了所有信道，并未发现优化信道，则IBS通过信道分配优化过程不能成功地获得一个空闲信道用于其专用工作信道。在这种情况下，IBS必须中止其传输，或者必须与其它相邻基站共享信道实现报文传输。

假设通过a次迭代过程，可以为IBS空出空闲信道。即，NB(a)是优化路径的终点。在信道切换阶段，优化路径上的每个基站根据在信道分配优化路径搜索阶段确定的切换方式，依次将当前信道切换至所选信道。

1)IBS在通过优化路径确定的给定信道上向相邻基站(即，NB(1))发送“信道切换请求”消息，然后该信道上的每个NB(1)在通过优化路径确定的给定信道上向其相邻基站(NB(2))进行转发，...，直至优化路径上的每个NB(a)都接收到该“信道切换请求”消息。假设优化路径上的这些NB(a)在信道Z上工作。

2)每个NB(a)-ChZ尝试将其工作信道从信道Z切换至其backup_idle信道。在将工作信道切换至其backup_idle信道之后，每个NB(a)-ChZ通过向NB(a-1)发送具有“成功”标记的“信道切换应答”信息来确认“信道切换请求”消息。

3)在接收到所有具有“成功”标记的“信道切换应答”信息之后，NB(a-1)将其工作信道切换至信道Z，然后NB(a-1)向NB(a-2)发送“信道切换应答”信息，...。

4)在从NB(1)接收到所有具有“成功”标记的“信道切换应答”信息之后，IBS成功地通过多次迭代信道切换过程获得了作为其专用工作信道的空闲信道。

下面结合图5，对在根据本发明的多次迭代的信道分配优化机制中IBS所执行的方法流程进行细述。

如图5所示，在步骤501中，如果存在在其上的所有NB(1)均具有backup_idle信道的信道，则在步骤503中请求在该信道上工作的NB(1)切换至它们的backup_idle信道，以使IBS获得空闲信道作为其专用工作信道(步骤523)。

否则，IBS将进入步骤505，确定是否测试了所有信道。如果存在尚未被测试的信道，IBS将在步骤507中选择具有最小个数的NB(1)所工作的一级工作信道(记为信道X)作为一级测试信道，即IBS的备选优化信道。

在步骤509中，IBS向每个NB(1)-ChX发送“信道分配优化测试”消息。在接收到该“信道分配优化测试”消息后，每个

NB(1)-ChX确定是否存在在其上的所有NB(2)均具有backup_idle信道的信道。

如果NB(1)-ChX发现存在这种在其上的所有NB(2)均具有backup_idle信道的信道，则该NB(1)-ChX向IBS发送具有“可行”指示的“信道分配优化应答”消息。否则，如果没有发现这种信道，则NB(1)-ChX将进一步请求其相邻基站(NB(2))分别执行信道分配优化路径搜索过程；在此基础上，NB(2)有可能再进一步请求其下一级的相邻基站(NB(3))分别执行信道分配优化路径搜索过程；由此逐级向下迭代地执行上述信道分配优化路径搜索过程。

在步骤511，当IBS向每个NB(1)-ChX发送的“信道分配优化测试”消息均接收到具有“可行”指示的“信道分配优化应答”消息，表明已经成功地发现了一条信道分配优化路径为IBS腾出空闲信道作为其工作信道，转入步骤513。

否则，如果任何一个NB(1)-ChX向IBS发送了具有“不可行”指示的“信道分配优化应答”消息，或者在等待预定时间之后仍未收到某个“信道分配优化测试”消息的应答信息，则返回步骤505。IBS在确定本地信道列表中除已测试过的信道X之外仍存在剩余信道的情况下，再次执行步骤507-511，以发现信道分配优化路径。

在步骤513中，IBS保存已发现的信道分配优化路径信息，包括信道切换次数、发送路径搜索请求的基站ID、期望切换至的目的信道等。

在步骤515，IBS向优化路径所确定的信道(假设为信道X)上工作的一级相邻基站(即，NB(1)-CHX)发送“信道切换请求”消息；并进入步骤517等待各个NB(1)-CHX对此消息的回应。

如果所有的“信道切换请求”消息均获得具有“成功”指示的应答，表明通过多次迭代切换过程已经成功地为IBS腾出一个空闲信道作为其专用工作信道X。在此情况下，IBS驻留在信道X上，开始报文传输(步骤519)。

如果已经在步骤505中测试了所有信道，并未发现任何可行的信道分配优化路径，即不能通过多次迭代切换过程为IBS腾出一个空闲信道(步骤506)。在这种情况下，IBS必须中止其传输，或者必须与其它相邻基站共享信道实现报文传输。

以下结合图6，对在根据本发明的多次迭代的信道分配优化机制中第k级相邻基站NB(k)所执行的相关流程进行描述。为论述方便，这里假设NB(k)正工作在O信道上。

首先，在步骤601中，NB(k)-CHO接收到来自NB(k-1)-CHM的“信道分配优化测试”消息。

然后在步骤603中，对所有NB(k+1)按照工作信道进行分组，将在同一工作信道上的NB(k+1)归为一组。

在步骤605中，确定是否存在在其上所有的NB(k+1)均具有backup_idle信道的信道。

如果存在这样的信道(假设为信道R)，则进入步骤606，NB(k)-CHO向NB(k-1)-CHM发送具有“可行”指示的“信道分配优化应答”消息。

在步骤6061中，当NB(k)-CHO接收到来自NB(k-1)-CHM的信道切换请求消息时，进入步骤6062，请求在信道R上工作的NB(k+1)-CHR切换至它们的backup_idle信道，以便能够为NB(k)-CHO腾出信道R。

在步骤6063中，NB(k)-CHO向NB(k-1)-CHM发送具有“成功”指示的“信道切换应答”消息，并在步骤6064中切换至信道R进行工作。

在步骤605中确定不存在在其上所有的NB(k+1)均具有backup_idle信道的信道的情况下，进入步骤607，在此确定迭代次数k是否超过了预定阈值。值得一提的是，迭代阈值的设定是为了避免出现无尽地执行迭代过程(即，收敛问题)。

因而在信道分配优化路径搜索过程中，如果第k级相邻基站NB(k)发现迭代次数k＞该阈值，则进入步骤608，将不再请求其相邻基站NB(k+1)启动信道分配优化路径搜索过程，NB(k)-CHO将向其上级相邻基站NB(k-1)发送具有“不可行”指示的“信道分配优化应答”消息。如果迭代次数k没有超过阈值，则进入步骤609。

在步骤609中，NB(k)-CHO将工作在各个信道上的NB(k+1)按照工作信道进行分组，其中相同信道上工作的NB(k+1)设定为一组。在步骤613中，NB(k)-CHO选择具有最小个数的NB(k+1)的信道作为(k+1)级测试信道，也即NB(k)的备选优化信道(假设为S)。在步骤615中，NB(k)-CHO向每个NB(k+1)-CHS发送“信道分配优化测试”消息。如果在步骤617中，向每个NB(k+1)-CHS发送的“信道分配优化测试”消息均接收到了具有“可行”指示的应答，则在步骤619中，NB(k)-CHO向NB(k-1)-CHM发送具有“可行”指示的“信道分配优化应答”消息。

如果在步骤617中，NB(k)-CHO接收到任何一个具有“不可行”指示的“信道分配优化应答”消息，或者在等待一定时间之后仍未收到某个“信道分配优化测试”消息的应答信息，则返回步骤611，继续在除信道S之外的信道(即，剩余信道)中选择在其上具有最少NB(k+1)的信道作为新的(k+1)级测试信道，继续针对在k级测试信道上工作的NB(k)执行步骤613-617。

如果测试了所有信道，仍未发现了可以腾出k级工作信道的信道分配优化路径，则转入步骤612，向NB(k-1)-CHM发送具有“不可行”指示的“信道分配优化应答”消息。

在步骤621中，NB(k)保存已发现的信道分配优化路径信息，包括信道切换次数、发送路径搜索请求的基站ID、所切换至的所选信道等。

步骤623-629描述了NB(k)在信道切换阶段所执行的过程。假设通过信道分配优化路径搜索过程确定NB(k-1)-CHM、NB(k)-CHO、NB(k+1)-CHS在该路径上。当在步骤623中NB(k)-CHO从NB(k-1)-CHM接收到信道切换请求消息时，执行步骤625。在步骤625中，NB(k)-CHO请求NB(k+1)-CHS通过信道切换腾出信道S，并进入步骤627等待NB(k+1)-CHS对信道切换请求消息的回应。如果NB(k)-CHO从每个NB(k+1)-CHS都收到“成功”指示的信道切换应答消息，表明信道S已被其相邻基站腾出。因此，NB(k)-CHO将在步骤629中，NB(k)向NB(k-1)发送具有“成功”指示的信道切换应答消息；并在步骤631，将信道切换至S，进行报文传送工作。

应注意，在该信道切换过程中，如果在任一级相邻基站处发生切换失败，则应将以下各级已完成的切换恢复为原有状态，并将具有“失败”指示的信道切换应答消息逐级转发直至IBS；IBS将针对剩余信道重新执行信道分配优化路径搜索过程。

在信道分配优化路径搜索过程中，IBS和各级相邻基站将保存本次信道分配优化路径搜索结果的相关信息，以便在将来执行信道分配优化路径搜索时，可以使用所保存的信道分配优化路径信息来迅速发现信道分配优化路径。。

表1中示出基站(假设为基站c)所保存的信道分配优化路径信息的示例。

表1信道分配优化路径信息的内容

应注意，“总信道切换次数”是信道分配优化路径上的基站腾出空闲信道所执行的信道切换次数的和。例如，如表1所示，如果基站a想要改变相邻基站的信道分配，以获得信道y作为其工作信道，则这些基站(包括其相邻基站，其相邻基站的相邻基站，...)需要进行总数为6次的信道切换。

如果将“总信道切换次数”被视为距离矢量，一些距离-矢量算法(如Bellman-Ford算法)可以用于计算最优化路径。这里，最优化路径表示为以最小信道切换次数腾出空闲信道的信道分配优化路径。基于距离-矢量算法计算最优化路径，不需要在相邻基站中频繁地交换信道分配优化路径信息。

当将来执行信道分配优化路径搜索时，基站可以优先使用信息表中已保存的信道分配优化路径信息来发现信道分配优化路径；如果不能依据这些信息成功发现一条可行的信道分配优化路径，基站将要求其下一级基站启动信道分配优化路径搜索过程。显然，基于先验的信息表信息，将大大加快信道分配优化路径搜索所耗时间，并节省相应用于传输“信道分配优化测试”和“信道分配优化应答”消息所耗的资源。

下面以图2所示的场景为例，说明如何实现图3所示的信道分配优化。

由于IBS(BS5)无法发现在其上的所有NB(1)均具有backup_idle信道的这种信道，因而需要采用基于多次迭代的信道分配优化过程为其腾出空闲信道。

1)IBS通过在信道上工作的NB(1)的数目对这些信道进行分类，并选择仅有一个相邻基站(BS6)在其上工作的信道3。

2)IBS向BS6发送“信道分配优化测试”消息。接收到该“信道分配优化测试”消息后，BS6确定是否存在在其上的所有NB(2)均具有backup_idle信道的信道。

3)BS6发现只有一个NB(2)(即BS3)在信道1上，且已知BS3可以通过切换至信道2为BS6腾出信道1。

4)BS6向IBS发送具有“可行”指示的“信道分配优化应答”消息。

5)当IBS从BS6接收到具有“可行”指示的“信道分配优化应答”消息时，IBS成功地搜索到腾出空闲信道以供其专用的优化信道。用于信道切换的路径是：

a)BS3从信道1切换至信道2；

b)BS6从信道3切换至信道1；

c)BS5切换至信道3。

在信道切换过程中，BS3、BS6和BS5根据信道切换路径依次切换至所选信道。最后，信道3被腾出，且由IBS(BS5)使用作为其专用工作信道。

图7示出了根据本发明的分布在包括IBS和IBS的多级相邻基站中的信道分配优化设备700。

在多级相邻基站中的当前级相邻基站NB(k)处，信道分配优化设备700包括：信道分配优化路径搜索装置701，用于接收来自上一级相邻基站NB(k-1)的信道分配优化测试消息；确定是否存在在其上所有的下一级相邻基站NB(k+1)均具有备份空闲信道的信道；如果存在在其上所有的下一级相邻基站NB(k+1)均具有备份空闲信道的信道，则向上一级相邻基站NB(k-1)发送具有“可行”指示的信道分配优化应答消息；以及信道切换装置703，用于在从上一级相邻基站NB(k-1)接收到信道切换请求消息时，请求在所述信道上工作的所有下一级相邻基站NB(k+1)切换至其备份空闲信道；在从所有下一级相邻基站NB(k+1)接收到具有“成功”指示的信道切换应答消息时，向上一级相邻基站NB(k-1)发送具有“成功”指示的信道切换应答消息，并将当前级相邻基站NB(k)的工作信道切换至所述信道。

如果不存在在其上所有的下一级相邻基站NB(k+1)均具有备份空闲信道的信道，则信道分配优化路径搜索装置701确定当前级相邻基站NB(k)的级数k是否超过了预定阈值。如果超过了预定阈值，则信道分配优化路径搜索装置701向上一级相邻基站NB(k-1)发送具有“不可行”指示的信道分配优化应答消息；如果并未超过预定阈值，则信道分配优化路径搜索装置701通过工作在各个信道上的下一级相邻基站NB(k+1)的个数对各个信道进行分类；然后确定所述各个信道中是否仍然存在可供测试的信道；如果不存在可供测试的信道，则信道分配优化路径搜索装置701向上一级相邻基站NB(k-1)发送具有“不可行”指示的信道分配优化应答消息。如果仍然存在可供测试的信道，则信道分配优化路径搜索装置701从所述可供测试的信道中选择具有最少个数的下一级相邻基站NB(k+1)的信道，作为当前级基站NB(k)的备选优化信道，并向工作在所选信道上所有下一级相邻基站NB(k+1)发送信道分配优化测试消息。

在当前级相邻基站NB(k)处，信道分配优化路径搜索装置701还确定是否所有信道分配优化测试消息都获得了“可行”指示的信道分配优化应答消息；如果并非所有信道分配优化测试消息都获得了“可行”指示的信道分配优化应答消息，则重复执行步骤：确定所述各个信道中是否仍然存在可供测试的信道；如果不存在可供测试的信道，则向上一级相邻基站NB(k-1)发送具有“不可行”指示的信道分配优化应答消息；如果仍然存在可供测试的信道，则从所述可供测试的信道中选择具有最少个数的下一级相邻基站NB(k+1)的信道，作为当前级相邻基站NB(k)的备选优化信道；以及向工作在所选信道上所有下一级相邻基站NB(k+1)发送信道分配优化测试消息。

如果所有信道分配优化测试消息都获得了“可行”指示的信道分配优化应答消息，则信道分配优化路径搜索装置701向上一级相邻基站NB(k-1)发送具有“可行”指示的信道分配优化应答消息。

在当前级相邻基站NB(k)处，路径切换装置703在从上一级相邻基站NB(k-1)接收到信道切换请求消息时，请求在所选信道上工作的所有下一级相邻基站NB(k+1)切换至其各自的备选优化信道或者其备份空闲信道。在从所有下一级相邻基站NB(k+1)接收到具有“成功”指示的信道切换应答消息时，向上一级相邻基站NB(k-1)发送具有“成功”指示的信道切换应答消息，并将当前的工作信道切换至所选信道。

信道切换设备703还被配置为：如果在任一级相邻基站处发生切换失败，则将以下各级已完成的切换恢复为原有状态，并向上一级相邻基站发送具有“失败”指示的信道切换应答消息。

在IBS处，信道分配优化设备700中的信道分配优化路径搜索装置701可以被配置为：在确定不存在空闲专用信道且不存在在其上工作的所有第一级相邻基站NB(1)均具有备选空闲信道的信道的情况下，通过工作在其上的第一级相邻基站NB(1)的个数对各个信道进行分类；确定所述各个信道中是否仍然存在可供测试的信道；如果仍然存在可供测试的信道，则从所述可供测试的信道中选择具有最少个数的第一级相邻基站NB(1)的信道，作为IBS的备选优化信道；向工作在所选信道上所有第一级相邻基站NB(1)发送信道分配优化测试消息。信道分配优化设备700中的信道切换装置703被配置为：如果所有发往第一级相邻基站NB(1)的信道分配优化测试消息都获得了“可行”指示的信道分配优化应答消息，则向相应的第一级相邻基站NB(1)发送信道切换请求消息时，请求在所选信道上工作的所有下一级相邻基站切换至其各自的备选优化信道或者其备份空闲信道。

在从所有第一级相邻基站NB(1)接收到具有“成功”指示的信道切换应答消息时，将IBS的工作信道切换至其备选优化信道，所述备选优化信道为第一级相邻基站NB(1)为初始化基站腾出的空闲信道。

当在IBS处，信道切换设备703接收到具有“失败”指示的信道切换应答消息时，信道分配优化路径搜索装置701被配置为：确定所述各个信道中是否仍然存在可供测试的信道；如果仍然存在可供测试的信道，则从所述可供测试的信道中选择具有最少个数的第一级相邻基站NB(1)的信道，作为IBS的备选优化信道；向工作在所选信道上所有第一级相邻基站NB(1)发送信道分配优化测试消息。

信道分配优化设备700还可以包括：用于保存所述初始化基站以及所述初始化基站的多级相邻基站处的信道分配优化路径搜索结果的相关信息的装置(未示出)；以及用于基于所述信息计算最优化的信道分配优化路径的装置(未示出)。

本发明提出了一种基于多次迭代的分布式信道分配优化机制。

基本的信道分配优化过程分为两个阶段：信道分配优化路径搜索阶段和信道切换阶段。在信道分配优化路径搜索阶段中，IBS通过多次迭代，与相邻基站协商以发现信道分配优化路径。在成功发现信道分配优化路径后，IBS及其相邻基站启动信道切换过程，从而可以避免无效的信道切换。

此外，为了避免迭代不能及时收敛问题，预先设置迭代次数的阈值。一旦当前迭代次数＞该阈值，在当前信道上的信道分配优化路径搜索过程将停止，并转至其它信道以发现另一路径。

此外，为了减少在搜索信道分配优化路径的所耗时间，每个基站都保存信道分配优化路径搜索结果的相关信息。基于该信息，可以使用距离-矢量算法(如Bellman-Ford算法)计算最优化的信道分配优化路径(具有最小的信道切换次数)。

很明显，，与在802.16h中定义的传统的单跳信道分配机制相比，本发明的技术方案通过多个信道切换过程可以实现更优化的信道分配。如果IBS不能发现任何在其上的所有相邻基站均具有backup_idle信道的信道，则802.16h中定义的信道分配优化的过程无法腾出空闲信道为IBS所用。但是，根据本发明的技术方案可以增加IBS获得专用信道的机会，提高频谱利用率，并为共存系统提供了更好的QoS，从而可以实现更好的多系统共存。

尽管以上已经结合本发明的优选实施例示出了本发明，但是本领域的技术人员将会理解，在不脱离本发明的精神和范围的情况下，可以对本发明进行各种修改、替换和改变。因此，本发明不应由上述实施例来限定，而应由所附权利要求及其等价物来限定。