无线网络的网络干扰评估方法、动态信道分配方法和设备

摘要

本发明提出了一种无线网络中使用的网络干扰评估方法、动态信道分配方法和设备。该动态信道分配方法包括如下步骤：根据接收信号强度指示符(RSSI)、业务量信息和速率信息，计算每一对基本服务集(BSS)的一对虚拟延迟时间(VDT)，并根据所计算的VDT，评估当前信道分配下的总体网络干扰；建立无向图，使得每个BSS位于顶点，每对BSS之间各自的连线具有根据这对BSS的VDT对所获得的权重；对无向图着色，以获得新的信道分配方案以及该新信道分配方案下的优化最小总体网络干扰；将当前信道分配下的评估总体网络干扰和优化最小总体网络干扰之间的差值与预定阈值相比较；以及如果差值大于预定阈值，则根据该新信道分配方案改变基本服务集的信道分配。

说明书

技术领域

本发明涉及无线网络，如802.11 WLAN，更具体地，涉及无线网络中使用的网络干扰评估方法、动态信道分配方法和设备。

背景技术

诸如802.11 WLAN等的无线网络近年来享有空前的采用率。一般而言，网络包含若干小区，每个小区包括一个基站(BS)以及与之关联的许多移动站(STA)。STA的通信必须通过BS进行中继。在上下文中，以802.11WLAN为例来讨论问题细节，但是应当理解，本发明并不应局限于802.11WLAN的情况。在802.11 WLAN中，小区称作BSS(基本服务集)，BS称作接入点(AP)，信道是指分配给WLAN的无线频谱。802.11规范定义了固定数目的信道以供使用。例如，802.11b(2.412-2.462GHz)定义了11个信道。

这些网络中的基本问题是干扰。由于无线介质的广播特性，来自一个发送-接收对的传输影响其他发送-接收对的传输。从微观观点来看，干扰量与信号强度有关。当从节点v向节点u发送分组时，该分组能否被成功接收取决于接收方u接口上的SINR(信号干扰噪声比)以及发送方v的传输速率。于是，

$=\frac{G_{v,u}·P_v}{N_u\left[\mathrm{CH}\left(u\right)\right]+\underset{a\in V,a\notin \mathrm{AP}\left(u\right)}{\Sigma }I(a,u)}---\left(1\right)$

I(a，u)＝G_a，u·P_a·1_{{CH(a)＝CH(u)}}

在公式(1)中，N_u[CH(u)]是信道CH(u)的背景噪声。a是不同BSS中的另一发送方，P_v和P_a是来自发送方网络接口的原始功率水平。G_v，u和G_a，u是传播衰减因子，它们与路径环境有关，且非常难以利用数学模型来进行计算。当SINR变差时，发射节点需要降低PHY(物理)速率，以防止分组损坏。对于802.11 WLAN，PHY速率和SINR之间的关系如表1所示。

表1：SINR和PHY数据率表

从宏观观点来看，干扰与干扰方的业务量成比例，因为业务量越大，导致信号干扰持续时间越长。

在进行无线网络优化时，需要预测不同网络参数下的干扰。例如，如果希望找到网络的最佳信道分配，则需要预测不同信道分配下的干扰程度，并选择全局干扰最小的一种信道分配。干扰预测的准确度直接影响优化性能。在进行诸如功率控制和网络诊断等其他优化时具有类似要求。

当前的干扰估计极不准确。

现有的大多数工作，如参考文献[1]，基于无线传播的简要模型来定义干扰——干扰范围是通信范围的两倍。当接收方处于干扰方的干扰范围内时，它们之间的干扰为1。否则，干扰设为0。

参考文献[2]的作者提出了一种针对接入点的自动信道判决方法和自动信道分配系统。在该方案中，使用接入点之间的信号强度作为干扰量，这比参考文献[1]有所改进。

除了干扰信号强度之外，参考文献[3]的作者还考虑了干扰方的业务量负载。在该方案中，AP周期性切换到信道j，并在信道j上侦听Tms。然后，AP确定T_load和T_interference，并计算CS(j)和Cl(j)，它们分别是信道j中监控的负载和干扰能量。最后，AP确定具有最小(CS(j)+Cl(j))的信道j为最佳信道。

在参考文献[4]中，作者提出了站感知干扰度量——$W({\mathrm{ap}}_i,{\mathrm{ap}}_j)=\frac{{\mathrm{Num}}_{{\mathrm{ap}}_i}\left({\mathrm{ap}}_j\right)+{\mathrm{Num}}_{{\mathrm{ap}}_j}\left({\mathrm{ap}}_i\right)}{{\mathrm{Num}}_{{\mathrm{ap}}_i}+{\mathrm{Num}}_{{\mathrm{ap}}_j}},$其中，是APi的BSS中的STA数，是与APi相关联但是能够从APj听到信标的STA数；是APj的BSS中的STA数，是与APj相关联但是能够从APi听到信标的STA数。

发明内容

本发明的目的是使用对无线网络的实时测量来获得其射频特性并准确预测其在不同设置下运行时将如何表现，以及向各AP动态分配信道资源以实现最优的系统整体性能。

总而言之，现有方法仅考虑如下两个因素：干扰方和接收方之间的信号功率(下文称作“干扰信号”)、干扰方的业务量(下文称作“干扰业务量”)。然而，在提出的这些方法中并没有很好地考虑对干扰性能有直接影响的其他因素，这些因素有：

1.发送方和接收方之间的信号功率(下文称作“好信号”)；

2.接收方的业务量；

3.SINR速率表。

没有这些信息，干扰预测在某些情况下将失去准确性。例如：

1.对于两个接收方A和B，它们的干扰信号强度相同而接收方A比接收方B更靠近其发送方。实际上，接收方A的分组丢失远小于接收方B，这意味着接收方A受到的干扰程度小于接收方B。然而，现有方法不能揭示这种情况，因为与好信号无关。

2.即使接收方B受到了强干扰信号的影响，但是如果接收方B在此时并没有通信业务量，则对于接收方B实际上并无干扰影响。因为干扰是由分组传输冲突造成的。

3.当希望减小对接收方B的干扰时，对于其发送方，应该将发送功率增加多少？

本发明提出了一种干扰程度预测度量，以便更准确地预测网络性能。该度量是虚拟延迟时间，表示由于干扰而引起的虚拟增加传输时间。该度量合理地将如下四个重要的干扰相关因素结合到一个公式中：

1.发送方和接收方之间的信号强度；

2.干扰方和接收方之间的信号强度；

3.每一节点的业务量需求；

4.SINR-速率表。

根据本发明的第一方面，提供了一种无线网络中使用的动态信道分配方法，包括如下步骤：根据接收信号强度指示符、业务量信息和速率信息，计算每一对基本服务集的一对虚拟延迟时间，并根据所计算的虚拟延迟时间，评估当前信道分配下的总体网络干扰；建立无向图，使得每个基本服务集位于顶点，每对基本服务集之间各自的连线具有根据这对基本服务集的虚拟延迟时间对所获得的权重；对无向图着色，以获得新的信道分配方案以及该新信道分配方案下的优化最小总体网络干扰；将当前信道分配下的评估总体网络干扰和优化最小总体网络干扰之间的差值与预定阈值相比较；以及如果差值大于预定阈值，则根据该新信道分配方案改变基本服务集的信道分配。

优选地，利用半定规划松弛的可行方向技术进行着色。

优选地，权重等于基本服务集对的虚拟延迟时间对之和。

优选地，计算步骤包括如下子步骤：对于形成第一基本服务集的一组第一节点以及形成第二基本服务集的一组第二节点，使用对第一节点计算的正常传输时间以及延迟传输时间，计算每一第一节点在来自该组第二节点的干扰下的虚拟延迟时间；以及对该组第一节点的所有虚拟延迟时间求和，得到第一基本服务集在来自第二基本服务集的干扰下的虚拟延迟时间。

优选地，计算步骤还包括如下子步骤：使用业务量信息和速率信息，计算每一第一节点的正常传输时间；使用SINR-速率表，并根据接收信号强度指示符，映射出第一节点的降低传输速率；以及使用业务量信息、速率信息以及第一节点的映射降低传输速率，计算第一节点在来自该组第二节点的干扰下的延迟传输时间。

优选地，该组第一节点包括第一接入点以及通过第一接入点接入无线网络的一组第一终端，该组第二节点包括第二接入点以及通过第二接入点接入无线网络的一组第二终端。

优选地，按照在当前信道分配下各对基本服务集之间的所有干扰的总和，来评估当前信道分配下的总体网络干扰，其中，如果一对基本服务集在当前信道分配下使用同一信道，则这对基本服务集之间的干扰等于为这对基本服务集计算的虚拟延迟时间对之和；而如果一对基本服务集在当前信道分配下使用不同信道，则这对基本服务集之间的干扰等于零。

根据本发明的第二方面，提供了一种总体网络干扰评估方法，包括：根据接收信号强度指示符、业务量信息和速率信息，计算每一对基本服务集的一对虚拟延迟时间；以及根据当前信道分配，对各对基本服务集之间的所有干扰求和，求和结果用作总体网络干扰的评估，其中，一对基本服务集之间的干扰根据为这对基本服务集计算的虚拟延迟时间对得到。

优选地，计算步骤包括如下子步骤：对于形成第一基本服务集的一组第一节点以及形成第二基本服务集的一组第二节点，使用对第一节点计算的正常传输时间以及延迟传输时间，计算每一第一节点在来自该组第二节点的干扰下的虚拟延迟时间；以及对该组第一节点的所有虚拟延迟时间求和，得到第一基本服务集在来自第二基本服务集的干扰下的虚拟延迟时间。

优选地，计算步骤还包括如下子步骤：使用业务量信息和速率信息，

计算每一第一节点的正常传输时间；使用SINR-速率表，并根据接收信号强度指示符，映射出第一节点的降低传输速率；以及使用业务量信息、速率信息以及第一节点的映射降低传输速率，计算第一节点在来自该组第二节点的干扰下的延迟传输时间。

优选地，该组第一节点包括第一接入点以及通过第一接入点接入无线网络的一组第一终端，该组第二节点包括第二接入点以及通过第二接入点接入无线网络的一组第二终端。

优选地，第一节点的正常传输时间Time_x^(Normal)如下计算：

${\mathrm{Time}}_x^{\left(\mathrm{Normal}\right)}=\frac{1}{{\mathrm{Rate}}_x}\times R_x$

其中，Rate_x表示第一终端或接入点在无干扰情况下的正常传输速率，R_x表示第一终端或接入点的归一化接收业务量负载。

优选地，对于第一终端，R_x通过将第一终端的接收业务量负载throughput^x(receiving)按照第一终端的正常传输速率Rate_x进行归一化而得到：

R_x＝throughput^x(receiving)/Rate_x。

优选地，对于第一接入点，R_x通过对该组第一终端的归一化发送业务量负载L_w求和而得到：

$R_x=\underset{w\in W}{\Sigma }{L}_w,$

其中，W表示该组第一终端，L_w通过将第一终端的发送业务量负载throughput^w(sending)按照第一终端的正常传输速率Rate_x进行归一化而得到：

L_w＝throughput^w(sending)/Rate_w。

优选地，第一终端的降低传输速率Rate_x^y通过使用SINR-速率表如下映射得到：

${\mathrm{Rate}}_x^y=\mathrm{Map}({\mathrm{RSSI}}_x^z-{\mathrm{RSSI}}_x^y)$

其中，根据RSSI_x^z-RSSI_x^y得到的值对应于SINR-速率表中的SINR栏，Rate_x^y的值对应于SINR-速率表中的速率栏，RSSI_x^z表示第一接入点与第一终端之间的接收信号强度指示符，RSSI_x^y表示一个第二节点与第一终端之间的接收信号强度指示符。

优选地，第一接入点的降低传输速率Rate_x^y通过使用SINR-速率表如下映射得到：

${\mathrm{Rate}}_x^y=\mathrm{Map}({\mathrm{RSSI}}_x-{\mathrm{RSSI}}_x^y)$

其中，根据RSSI_x-RSSI_x^y得到的值对应于SINR-速率表中的SINR栏，Rate_x^y的值对应于SINR-速率表中的速率栏，RSSI_x表示第一接入点的接收信号强度指示符，RSSI_x^y表示一个第二节点与第一终端之间的接收信号强度指示符。

优选地，第一接入点的接收信号强度指示符RSSI_x通过将该组第一终端与第一接入点之间的接收信号强度指示符RSSI_w^x按照该组第一终端的归一化发送业务量负载L_w进行加权后求和得到：

${\mathrm{RSSI}}_x=\underset{w\in W}{\Sigma }(L_w·{\mathrm{RSSI}}_x^w).$

优选地，第一节点在来自该组第二节点的干扰下的延迟传输时间Time_x，Y^{(Interference)}如下计算：

${\mathrm{Time}}_{x,Y}^{\left(\mathrm{Interference}\right)}=\frac{1}{\underset{y\in Y}{\Sigma }(L_y·{\mathrm{Rate}}_x^y)+(1-\underset{y\in Y}{\Sigma }{L}_y)·{\mathrm{Rate}}_x}\times R_x$

其中，Y表示该组第二节点，L_y表示一个第二节点的归一化发送业务量负载，且通过将该第二节点的发送业务量负载throughput^y(sending)按照该第二节点的正常传输速率Rate_y进行归一化而得到：

L_y＝throughput^y(sending)/Rate_y。

优选地，第一节点在来自该组第二节点的干扰下的虚拟延迟时间VDT(x，Y)如下计算：

$\mathrm{VDT}(x,Y)={\mathrm{Time}}_{x,Y}^{\left(\mathrm{Interference}\right)}-{\mathrm{Time}}_x^{\left(\mathrm{Normal}\right)}.$

优选地，如果一对基本服务集在当前信道分配下使用同一信道，则这对基本服务集之间的干扰等于为这对基本服务集计算的虚拟延迟时间对之和；而如果一对基本服务集在当前信道分配下使用不同信道，则这对基本服务集之间的干扰等于零。

根据本发明的第三方面，提供了一种无线网络中使用的动态信道分配设备，包括：虚拟延迟时间计算装置，用于根据接收信号强度指示符、业务量信息和速率信息，计算每一对基本服务集的一对虚拟延迟时间；总体网络干扰计算装置，用于根据虚拟延迟时间计算装置所计算的虚拟延迟时间，评估当前信道分配下的总体网络干扰；图产生器，用于建立无向图，使得每个基本服务集位于顶点，每对基本服务集之间各自的连线具有根据这对基本服务集的虚拟延迟时间对所获得的权重；图着色单元，用于对图产生器所生成的无向图着色，以获得新的信道分配方案以及该新信道分配方案下的优化最小总体网络干扰；比较器，用于将当前信道分配下的评估总体网络干扰和优化最小总体网络干扰之间的差值与预定阈值相比较；以及控制器，如果差值大于预定阈值，则根据该新信道分配方案改变基本服务集的信道分配。

优选地，图着色单元利用半定规划松弛的可行方向技术进行着色。

优选地，权重等于基本服务集对的虚拟延迟时间对之和。

优选地，一组第一节点形成第一基本服务集，一组第二节点形成第二基本服务集，且虚拟延迟时间计算装置包括：节点虚拟延迟时间计算装置，用于使用对第一节点计算的正常传输时间以及延迟传输时间，计算每一第一节点在来自该组第二节点的干扰下的虚拟延迟时间；以及加法器，用于对该组第一节点的所有虚拟延迟时间求和，得到第一基本服务集在来自第二基本服务集的干扰下的虚拟延迟时间。

优选地，虚拟延迟时间计算装置还包括：正常传输时间计算装置，用于使用业务量信息和速率信息，计算每一第一节点的正常传输时间；降低传输速率映射器，用于使用SINR-速率表，并根据接收信号强度指示符，映射出第一节点的降低传输速率；以及延迟传输时间计算装置，用于使用业务量信息、速率信息以及第一节点的映射降低传输速率，计算第一节点在来自该组第二节点的干扰下的延迟传输时间。

优选地，该组第一节点包括第一接入点以及通过第一接入点接入无线网络的一组第一终端，该组第二节点包括第二接入点以及通过第二接入点接入无线网络的一组第二终端。

优选地，总体网络干扰计算装置按照在当前信道分配下各对基本服务集之间的所有干扰的总和，来评估当前信道分配下的总体网络干扰，其中如果一对基本服务集在当前信道分配下使用同一信道，则这对基本服务集之间的干扰等于为这对基本服务集计算的虚拟延迟时间对之和；而如果一对基本服务集在当前信道分配下使用不同信道，则这对基本服务集之间的干扰等于零。

根据本发明的第四方面，提供了一种总体网络干扰评估设备，包括：虚拟延迟时间计算装置，根据接收信号强度指示符、业务量信息和速率信息，计算每一对基本服务集的一对虚拟延迟时间；以及总体网络干扰评估装置，用于根据当前信道分配，对各对基本服务集之间的所有干扰求和，求和结果用作总体网络干扰的评估，其中，一对基本服务集之间的干扰根据为这对基本服务集计算的虚拟延迟时间对得到。

优选地，一组第一节点形成第一基本服务集，一组第二节点形成第二基本服务集，且虚拟延迟时间计算装置包括：节点虚拟延迟时间计算装置，用于使用对第一节点计算的正常传输时间以及延迟传输时间，计算每一第一节点在来自该组第二节点的干扰下的虚拟延迟时间；以及加法器，用于对该组第一节点的所有虚拟延迟时间求和，得到第一基本服务集在来自第二基本服务集的干扰下的虚拟延迟时间。

优选地，虚拟延迟时间计算装置还包括：正常传输时间计算装置，用于使用业务量信息和速率信息，计算每一第一节点的正常传输时间；降低传输速率映射器，用于使用SINR-速率表，并根据接收信号强度指示符，映射出第一节点的降低传输速率；以及延迟传输时间计算装置，用于使用业务量信息、速率信息以及第一节点的映射降低传输速率，计算第一节点在来自该组第二节点的干扰下的延迟传输时间。

优选地，该组第一节点包括第一接入点以及通过第一接入点接入无线网络的一组第一终端，该组第二节点包括第二接入点以及通过第二接入点接入无线网络的一组第二终端。

优选地，如果一对基本服务集在当前信道分配下使用同一信道，则这对基本服务集之间的干扰等于为这对基本服务集计算的虚拟延迟时间对之和；而如果一对基本服务集在当前信道分配下使用不同信道，则这对基本服务集之间的干扰等于零。

总而言之，本发明如下工作：

1.SINR-速率表目前是公知常识。该表取决于无线网络的类型，如WiFi、Wimax等。例如，在本发明的实施方式中使用WiFi网络，该表如以上表1所示。

2.无线网络中的每个节点周期性地执行测量处理。在处理中，节点测量如下信息：从其关联接入点(或者，在其他类型无线网络中为基站)到其自身的信号强度；从其相邻小区中的其他节点到其自身的信号强度；其相邻小区中其他节点的业务量；以及其自身的业务量。

3.利用这些信息，节点能够计算其受到的干扰程度(虚拟延迟时间)。

4.接入点(或基站)可以收集每个节点的信息，从而能够计算该小区受到的干扰程度。

下面列出了本发明的有益效果：

1.由实际测量驱动干扰程度预测，从而避免了简化有关无线信号传播特性的假设。

2.可以更准确地揭示不同设置下运行的网络性能。

3.本发明不需要在MAC层进行改变，并可以通过简单的软件升级来实现。提出的建议与现有网络标准如802.11是后向兼容的。

附图说明

根据如下结合附图对本发明非限制性实施例的详细描述，本发明的上述以及其他目的、特征和优点将更加清楚，附图中：

图1示出了本发明可以应用的简单示例；

图2示出了存在多个干扰方的另一示例；

图3A示出了本发明的动态信道分配方法的流程图；

图3B示出了图3A中VDT计算步骤的详情；

图4A示出了本发明的动态信道分配设备的示意图；以及

图4B示出了图4A中VDT计算装置的详情。

具体实施方式

下文将根据附图描述本发明。在如下描述中，一些具体的实施例仅仅是为了描述的目的，它们不过是本发明的例子，而不应理解为对本发明的限制。尽管可能模糊对于本发明的理解，但是省略了常规结构或构造。

图1中示出了本发明应用的一种简单情况。在AP1的小区中，AP1正向节点A发送业务量。在AP2的小区中，节点B同时在向AP2发送业务量。当两个小区使用相同信道时，节点B是接收方——节点A的干扰方。

表2中列出了为评估从节点B到节点A的干扰程度，节点A需要收集的参数。

表2：接收方要收集的参数

在表2中，RSSI表示接收信号强度指示符，所有商用无线卡均报告RSSI，可以用于估计信号强度。例如，在Atheros卡中，RSSI以的形式报告，其中S表示进入信号的强度，I表示相同信道中的干扰能量，n表示“噪声本底”(通常为约-95dbm)。

为了表示干扰程度，对于干扰度量的选择是该问题的关键。这决定了如何将参数结合在一起。例如，在现有方法中，干扰信号强度或者干扰信号强度与干扰业务量之和用作干扰度量。在本发明中，提出了一种新的度量——虚拟延迟时间(VDT)。该度量是基于如下事实提出的：发送方可以降低其传输速率以防止分组丢失，代价是相同分组的传输时间必定比无干扰情况下要长。因此，额外的时间成本可用于评估干扰程度。

$\mathrm{VDT}(x,y)={\mathrm{Time}}_{x,y}^{\left(\mathrm{Interference}\right)}-{\mathrm{Time}}_x^{\left(\mathrm{Normal}\right)}---\left(2\right)$

在公式(2)中，Time_x^(Normal)是节点x在无干扰情况下的正常传输时间，Time_x，y^{(Interference)}是节点x在来自节点y的干扰下的延迟传输时间。它们都是通过表2中列出的参数进行计算的。

对于存在一个接收方和一个干扰方的简单情况(图1)，则

${\mathrm{Time}}_x^{\left(\mathrm{Normal}\right)}=\frac{1}{{\mathrm{Rate}}_x}\times R_x---\left(3\right)$

${\mathrm{Time}}_{x,y}^{\left(\mathrm{Interference}\right)}=\frac{1}{L_y·{\mathrm{Rate}}_x^y+(1-L_y)·{\mathrm{Rate}}_x}\times R_x---\left(4\right)$

其中，Rate_x^y是节点x在节点y干扰下的降低传输速率，可以如下计算：

${\mathrm{Rate}}_x^y=\mathrm{Map}({\mathrm{RSSI}}_x^z-{\mathrm{RSSI}}_x^y)---\left(5\right)$

其中，函数Map(.)是根据SINR-速率表(例如，上述针对802.11网络的表1)从SINR到传输速率的映射函数。在此，节点z是节点x的发送方，而节点y是节点x的干扰方。根据RSSI_x^z-RSSI_x^y得到的值对应于表1中的SINR栏。Rate_x^y的值对应于表1中的PHY速率栏。

下文将结合图1描述关于如何计算VDT(A，B)的示意性示例。假设：节点A是接收方，节点B是干扰方；Rate_A＝24Mbps，Rate_B＝36Mbps，throughput^A(receiving)＝12Mbps，throughput^B(sending)＝9Mbps；${\mathrm{RSSI}}_A^{\mathrm{AP}1}=24\mathrm{dbm},$${\mathrm{RSSI}}_A^B=10\mathrm{dbm}$。因此，根据表2中的定义，L_B＝0.25且R_A＝0.5。根据公式(3)，${\mathrm{Time}}_x^{\left(\mathrm{Normal}\right)}=\frac{1}{24\mathrm{Mbps}}\times 0.5=20.83\mathrm{ns}$。根据公式(5)和表1，由于14dbm大于6.99dbm且小于23dbm，${\mathrm{Rate}}_A^B=\mathrm{Map}\left(14\mathrm{dbm}\right)=11\mathrm{Mbps}$。因此，参照公式(4)，${\mathrm{Time}}_{x,y}^{\left(\mathrm{Interference}\right)}=\frac{1}{0.25·11\mathrm{Mbps}+0.75·24\mathrm{Mbps}}\times 0.5=24.10\mathrm{ns}$。结果，VDT(x，y)＝24.10ns-20.83ns＝3.27ns。

对于图2所示的存在多个干扰方的情况，仍然利用公式(3)来计算Time_x^(Normal)。

利用如下公式(6)来计算Time_x，Y^{(Interference)}。设Y是干扰集(Y＝{B，C，..N})，

${\mathrm{Time}}_{x,Y}^{\left(\mathrm{Interference}\right)}=\frac{1}{\underset{y\in Y}{\Sigma }(L_y·{\mathrm{Rate}}_x^y)+(1-\underset{y\in Y}{\Sigma }{L}_y)·{\mathrm{Rate}}_x}\times R_x---\left(6\right)$

其中，Rate_x^y根据公式(5)得到。

因此，在多个干扰方的情况下，公式(2)所示出的虚拟延迟时间(VDT)可写为：

$\mathrm{VDT}(x,Y)={\mathrm{Time}}_{x,Y}^{\left(\mathrm{Interference}\right)}-{\mathrm{Time}}_x^{\left(\mathrm{Normal}\right)}---\left(2^{,}\right)$

对于AP是接收方的情况，公式(5)中AP的好信号不同于站的好信号，因为AP的接收业务量来自多个发送方。假设X是与AP相关联的所有站的集合，得到如下公式：$\underset{x\in X}{\Sigma }{L}_x=R_{\mathrm{AP}}$。在本发明中，利用如下公式(7)来估计AP的好信号：

${\mathrm{RSSI}}_{\mathrm{AP}}=\underset{x\in X}{\Sigma }(L_x·{\mathrm{RSSI}}_{\mathrm{AP}}^x)---\left(7\right)$

如果希望计算整个BSS X的干扰，该干扰就等于该BSS中每个节点的VDT之和。即，

${\mathrm{VDT}}_X^Y=\underset{x\in X}{\Sigma }\mathrm{VDT}(x,Y)---\left(8\right)$

VDT(x，Y)可以利用公式(2)-(6)以及(2’)计算。

现在，讨论如何使用VDT来解决WLAN中的动态信道分配问题。将无线网络建模为一般无向图，具有顶点集V＝{1，2，L，n}，这些顶点表示网络中的n个BSS。网络中有K个正交信道，设为集合κ＝{1，2，L，K}。信道分配可以表示为如下问题：计算函数F：V→κ以最小化总体网络干扰其中BSS X和BSS Y之间的干扰I(X，Y)如下定义：

$I(X,Y)=\left(\begin{array}{cc}{\mathrm{VDT}}_X^Y+{\mathrm{VDT}}_Y^X& F\left(X\right)=F\left(Y\right)\\ 0& F\left(X\right)\ne F\left(Y\right)\end{array}\right)---\left(9\right)$

其中，F(X)＝F(Y)表示BSS X和BSS Y正使用同一信道，而F(X)≠F(Y)表示BSS Y正使用不同信道。

已知对于该问题的优化是NP难题。在本发明中，使用集中式方法来解决该问题。对于小规模(n≤12且K≤3)，可以使用穷举搜索来实现最佳分配。对于大规模情况，使用半定规划松弛的可行方向技术(SDP)来获得近似结果。SDP一般被认为是最小k划分(MkP)问题，这可被视为信道分配的等价问题。MkP方法的详情可参照参考文献[5]，为了简化描述且避免不必要地模糊本发明的主题，在此省略该方法的详细描述。

图3A示出了本发明的动态信道分配方法的流程图。

基于以上对原理的描述，参考图3A来描述根据本发明的动态信道分配方法。在步骤S305中，从AP和终端获得RSSI、业务量信息和速率信息。在步骤S310中，根据RSSI、业务量信息和速率信息，计算每一对基本服务集(AP)的一对虚拟延迟时间。具体地，参照以上公式(2)-(8)和(2’)以及SINR-速率表(例如，上述表1)来计算虚拟延迟时间。在步骤S312中，根据步骤S310中得到的虚拟延迟时间，评估当前信道分配下的总体网络干扰。具体地，可以按照当前信道分配下各对基本服务集之间的所有干扰的总和，来评估当前信道分配下的总体网络干扰，其中，如果一对基本服务集在当前信道分配下正使用同一信道，则这对基本服务集之间的干扰等于步骤S310中得到的这对基本服务集的虚拟延迟时间对之和，而如果一对基本服务集在当前信道分配下正使用不同信道，则这对基本服务集之间的干扰等于0。在步骤S315中，建立无向图，使得每个基本服务集(AP)位于顶点，每对基本服务集(AP)之间各自的连线具有与步骤S310中得到的这对基本服务集(AP)的虚拟延迟时间对之和相等的权重。在步骤S320中，对无向图进行着色，例如，可以通过半定规划松弛的可行方向技术来进行着色，以获得新的信道分配方案以及该新信道分配方案下的优化最小总体网络干扰。在步骤S325中，将分别在步骤S312和S320中得到的评估总体网络干扰和优化最小总体网络干扰之间的差值(干扰改进量)与预定阈值相比较。如果差值大于阈值(步骤S325中“是”)，这意味着总体系统性能将大大改善，则在步骤S330中根据新的信道分配方案来改变基本服务集(AP)的信道分配。否则，如果差值不大于阈值(步骤S325中“否”)，这意味看总体系统性能不会得到较大改善，则保持基本服务集(AP)的信道分配不变。本发明的动态信道分配方法将继续监视系统(或者周期性，或者利用某些触发机制)。

图3B示出了步骤S310中VDT计算的详情。在步骤S3100中，使用业务量信息和速率信息，根据公式(3)计算节点x(属于一个BSS：集合X)的正常传输时间Time_x^(Normal)。在步骤S3102中，使用SINR-速率表(例如，上述表1)，并根据每一节点与节点x之间的RSSI信息，映射出节点x的降低传输速率Rate_x^y。在步骤S3104中，使用业务量信息、速率信息以及在步骤S3102中对节点x映射得到的降低传输速率Rate_x^y，根据公式(6)计算节点x在来自干扰集Y(另一BSS)的干扰下的延迟传输时间Time_x，Y^{(Interference)}。在步骤S3106中，使用分别在步骤S3100和S3104中计算得到的节点x的正常传输时间Time_x^(Normal)以及延迟传输时间Time_x，Y^{(Interference)}，根据公式(2’)计算节点x在来自干扰集Y的干扰下的虚拟延迟时间VDT(x，Y)。在步骤S3108中，确定是否对属于集合X的所有节点x都获得了虚拟延迟时间VDT(x，Y)，即，是否对属于集合X的所有节点x都进行了处理。如果是(步骤S3108中“是”)，则进入到步骤S3110，其中一个BSS集合X在来自另一BSS集合Y的干扰下的虚拟延迟传输时间VDT_X^Y根据公式(8)如下计算：属于集合X的所有节点x的虚拟延迟时间VDT(x，Y)之和。如果尚未获得属于集合X的所有节点x的虚拟延迟时间VDT(x，Y)(步骤S3108中“否”)，则选择属于集合X的另一节点x，并且处理返回步骤S3100和S3102。

类似地，对于属于另一BSS集合Y的每一节点y和干扰集X，执行上述步骤S3100-S3110，以获得另一BSS集合Y在来自一个BSS集合X的干扰下的虚拟延迟传输时间VDT_Y^X。

因此，对于每一对BSS集合X和Y，得到了一对虚拟延迟传输时间VDT_X^Y和VDT_Y^X。

图4A示出了本发明的动态信道分配设备的示意图。

如图4A所示，本发明的动态信道分配设备400包括：检测器410，用于从AP和终端检测RSSI、业务量信息和速率信息；虚拟延迟时间(VDT)计算装置420，用于根据检测器410检测到的RSSI、业务量信息和速率信息，计算每一对基本服务集(AP)的一对虚拟延迟时间，其中参照以上公式(2)-(8)和(2’)以及SINR-速率表(例如，上述表1)来计算虚拟延迟时间；总体网络干扰计算装置425，用于根据VDT计算装置420计算的虚拟延迟时间，评估当前信道分配下的总体网络干扰，其中可以按照当前信道分配下各对基本服务集之间的所有干扰的总和，来评估当前信道分配下的总体网络干扰，其中，如果一对基本服务集在当前信道分配下正使用同一信道，则这对基本服务集之间的干扰等于VDT计算装置420计算的这对基本服务集的虚拟延迟时间对之和，而如果一对基本服务集在当前信道分配下正使用不同信道，则这对基本服务集之间的干扰等于0；图产生器430，用于建立无向图，使得每个基本服务集(AP)位于顶点，每对基本服务集(AP)之间各自的连线具有与VDT计算装置420计算的这对基本服务集(AP)的虚拟延迟时间对之和相等的权重；图着色单元440，用于对图产生器430建立的无向图进行着色，例如通过半定规划松弛的可行方向技术(SDP)来进行着色，以获得新的信道分配方案以及该新信道分配方案下的优化最小总体网络干扰；比较器450，用于将分别由总体网络干扰计算装置425和SDP求解装置440得到的评估总体网络干扰和优化最小总体网络干扰之间的差值(干扰改进量)与预定阈值相比较；控制器460，用于在比较器450的比较结果表明差值大于阈值(这意味着总体系统性能将大大改善)时根据新的信道分配方案来改变基本服务集(AP)的信道分配。否则，如果比较器的比较结果表明差值不大于阈值，这意味着总体系统性能不会得到较大改善，则控制器460保持基本服务集(AP)的信道分配不变。本发明的动态信道分配设备400将继续监视系统(或者周期性，或者利用某些触发机制)。

图4B示出了VDT计算装置420的详情。VDT计算装置420包括正常传输时间计算装置4210、降低传输速率映射器4220、延迟传输时间计算装置4230、节点VDT计算装置4240、控制器4250和加法器4260。

正常传输时间计算装置4210使用业务量信息和速率信息，根据公式(3)计算节点x(属于一个BSS：集合X)的正常传输时间Time_x^(Normal)。

降低传输速率映射器4220使用SINR-速率表(例如，上述表1)，并根据每一节点与节点x之间的RSSI信息，映射出节点x的降低传输速率Rate_x^y。

延迟传输时间计算装置4230使用业务量信息、速率信息以及降低传输速率映射器4220映射得到的节点x的降低传输速率Rate_x^y，根据公式(6)计算节点x在来自干扰集Y(另一BSS)的干扰下的延迟传输时间Time_x，Y^{(Interference)}。

节点VDT计算装置4240使用分别由正常传输时间计算装置4210和延迟传输时间计算装置4230计算得到的节点x的正常传输时间Time_x^(Narmal)以及延迟传输时间Time_x，Y^{(Inferference)}，根据公式(2’)计算节点x在来自干扰集Y的干扰下的虚拟延迟时间VDT(x，Y)。

控制器4250确定是否对属于集合X的所有节点x都获得了虚拟延迟时间VDT(x，Y)，即，是否对属于集合X的所有节点x都进行了处理。

如果控制器4250确定对属于集合X的所有节点x都获得了虚拟延迟时间VDT(x，Y)，则控制器4250将由节点VDT计算装置4240计算的属于集合X的所有节点x的虚拟延迟时间VDT(x，Y)传送到加法器4260，并且加法器4260根据公式(8)如下计算一个BSS集合X在来自另一BSS集合Y的干扰下的虚拟延迟传输时间VDT_X^Y：属于集合X的所有节点x的虚拟延迟时间VDT(x，Y)之和。

如果控制器4250确定尚未获得属于集合X的所有节点x的虚拟延迟时间VDT(x，Y)，则控制器4250选择属于集合X的另一节点x，并且调用正常传输时间计算装置4210、降低传输速率映射器4220、延迟传输时间计算装置4230和节点VDT计算装置4240，以计算属于集合X的新选择节点x在来自干扰集Y的干扰下的虚拟延迟时间VDT(x，Y)。

类似地，对于属于另一BSS集合Y的每一节点y和干扰集X，正常传输时间计算装置4210、降低传输速率映射器4220、延迟传输时间计算装置4230、节点VDT计算装置4240、控制器4250和加法器4260执行相同处理，以获得另一BSS集合Y在来自一个BSS集合X的干扰下的虚拟延迟传输时间VDT_Y^X。

因此，对于每一对BSS集合X和Y，通过VDT计算装置420得到了一对虚拟延迟传输时间VDT_X^Y和VDT_Y^X。

前面的描述只是给出了本发明的优选实施例，而决不是要限制本发明。因此，在本发明的精神和原理内做出的任何修改、替换、改进等都应包括在本发明的范围内。

参考文献列表

[1]Colin McDiarmid and Bruce Reed，“Channel Assignment And WeightedColoring”，2000.

[2]JP 2006-054849，YAMANE KOJI，“Method Of Automatic Channel DesignDecision And Automatic Channel Allocation System For Access Point”

[3]US 7,110,374 B2，R.Malhotra，P.Busch，Lucent Tech Inc.”Wireless LAN withDynamic Channel”

[4]Arunesh Mishra，Suman Banerjee，and William Arbaugh，“Weighted ColoringBased Channel Assignment For WLANs”，Mobile Computer CommunicationsReview(MC2R)，Vol.9，no.3，2005.

[5]A.Frieze and M.Jerrum.Improved approximation algorithms for MAX k-CUTand MAX BISECTION.Algoritmica，18，1997.