用于反复确定移动设备-接入点关联关系以实现负载平衡的方法和设备

摘要

本发明的实施例涉及用于反复确定移动设备-接入点关联关系以实现负载平衡的方法和设备。在反复时间段期间，可基于无线局域网的负载平衡目标使移动设备与除其当前接入点之外的其他接入点相关联。

说明书

相关申请的交叉引用

本申请是申请日为2006年2月14日、申请号为200610004446.7的发明专利申请的分案申请。 

技术领域

本发明涉及通信技术领域。 

背景技术

无线局域网(WLAN)通常由许多移动设备(例如无线笔记本电脑等)构成。这些移动设备中的每一个与一个所谓的“接入点”(AP)相关联。AP充当一个管道，消息、信息、信令等可通过该管道被传送到或传送自移动设备。通常，存在比AP多得多的移动设备。例如，数十或数百移动设备与同一AP相关联这种情况并非罕见。 

但是，在任何给定时刻，一个AP可能与许多移动设备相关联，而另一个AP可能与少得多的移动设备相关联。比较而言，第一AP可以被视为被“拥塞”或过载，而后一AP可被视为相对未被拥塞的。理想情况下，希望使移动设备与WLAN中的AP相关联以使得没有一个AP被拥塞。在实践中，这是难以实现的。然而，已经开发出了负载平衡技术，这种技术尝试或多或少地减轻AP中的拥塞。 

虽然这些技术可以降低AP中的拥塞，但是它们可能具有降低移动设备和AP之间的传输速率的反作用。即，现有技术可能通过以下方式来减轻AP中的拥塞：使与另一AP相距很远的移动设备与该AP相关联。在这种情况下，虽然降低了AP的拥塞级别，但是因为移动设备与其相关联的AP相距很远，所以可能也降低了移动设备的传输 速率。 

因此，希望提供这样的WLAN负载平衡方法和设备，其考虑了AP和移动设备的拥塞级别和传输速率，以便使移动设备与接入点相关联。 

发明内容

我们已经意识到WLAN的负载平衡目标可通过反复确定移动设备-接入点关联关系来达到。 

在本发明的一个示例中，控制器可操作以用于：(a)在反复时间段期间根据从移动设备和当前相关联的接入点(AP)之间以及移动设备和另一AP之间的传输导出的传输速率生成传输速率比率；(b)在反复时间段期间根据对AP的拥塞测量结果生成拥塞级别比率；以及(c)在反复时间段期间根据传输速率和拥塞级别比率生成效率指数。 

如此生成的指数是对在反复时间段期间继续使移动设备与当前AP相关联、或者使移动设备与另一AP相关联以实现WLAN负载平衡目标的合意度的相对指示。 

附图简介

图1示出根据本发明的WLAN的简化图，该WLAN包括可以与AP相关联的移动设备，同时达到WLAN负载平衡的目标。 

具体实施方式

现参考图1，其中示出了WLAN1，它包括多个移动设备2、3。仅出于说明目的，移动设备群组2当前与指定为AP_u的接入点相关联，而单个移动设备3当前与指定为AP_v的另一接入点相关联。另外，移动设备x被示为设备群组2的一部分。为了接下来的说明，可以这么说：由于当前与接入点AP_u相关联的移动设备比与接入点AP_v相关联的移动设备多得多，所以与接入点AP_v相比，接入点AP_u是被拥塞或过载的。 

通常，如果移动设备x与接入点AP_u的距离比与接入点AP_v的距离近，则移动设备x和接入点AP_u之间的传输速率(简写为R_x，u)将会高于移动设备x和接入点AP_v之间的传输速率(简写为R_x，v)。如果是这样的话，则通常移动设备x会使其自己与接入点AP_u相关联。但是，这种关联关系可能会不利地影响WLAN1的整体负载平衡目标。此外，应当注意，虽然在给定时间段期间移动设备x和接入点AP_u之间的传输速率可能高于移动设备x和接入点AP_v之间的传输速率，但是即使移动设备x与AP_u相关联，它可能也无法从此传输速率优势中受益，这是因为AP_u被拥塞。换句话说，由于接入点AP_u与许多移动设备2相关联，因此相对而言，在移动设备x被给予利用其有利传输速率向接入点AP_u发送传输或接收来自接入点AP_u的传输之前，可能要经过较长的时间段。相反，移动设备x可能必须等待轮到它接收有利传输速率的益处。相反，即使移动设备x和接入点AP_v之间的传输速率低于移动设备x和接入点AP_u之间的传输速率，由于接入点AP_v的拥塞程度低于接入点AP_u，因此移动设备x可能立即被给予向接入点AP_v发送传输以及接收来自接入点AP_v的传输的权利。换句话说，移动设备x若要向接入点AP_v发送传输或接收来自接入点AP_v的传输可能不必等待很长时间。 

根据本发明的一个实施例，可能作为网络操作中心(NOC)的一部分的控制器10可操作以用于通过在考虑了AP_u和AP_v的拥塞级别以及移动设备(例如x)与两个接入点之间的传输速率之后控制一个或多个移动设备与接入点的关联关系，从而来执行负载平衡。 

为了简化以下对本发明的说明，以下描述最初将会集中于单个设备移动x和两个接入点AP_u和AP_v。但是，应当理解，本发明同样可应用于多个移动设备和多于两个接入点。 

根据本发明的一个实施例，控制器10可操作以用于在反复时间段T期间接收与来自移动设备x的传输速率R_x，v、R_x，u相关联的指示符，然后可操作以用于根据接收到的指示符生成传输速率比率R_x，v/R_x，u。再次，应当回想到每个指示符是基于移动设备x和接入点AP_u或AP_v之 一之间的传输速率的。除了传输速率比率外，控制器10还可操作以用于生成拥塞级别比率。 

拥塞级别比率是从对两个接入点AP_u和AP_v上的拥塞的测量导出的。以下，为了避免混淆，接入点AP_u可被称为“当前”AP，而接入点AP_v可被称为“潜在”、“其他”或“新”AP，前一称谓表明移动设备x当前与AP_u相关联，而后一称谓表明移动设备x未来可能变成与接入点AP_v相关联。 

接入点AP_u和AP_v的拥塞例如可分别由接入点中的每一个在反复时间段期间T之间测量，然后被发送到控制器10。 

在本发明的另一个实施例中，在生成传输速率比率和拥塞级别比率之后，控制器10还可操作以用于根据传输速率和拥塞级别比率生成效率指数I_x，u，v。 

在进行进一步的描述之前，如上所述，对于传输速率、拥塞级别的测量以及效率指数I_x，u，v的生成都是在反复的基础上重复进行的，即在每个T秒的反复期间(iteration)进行一次。此外，正如以下将说明的，关于是否将接入点的责任从当前AP转移到另一AP的判定也是在反复基础上执行的。即，这种功能是在第一反复时间段(例如10秒)期间执行的，然后在接下来的每个相继的时间段期间重复。 

还应当理解，标记I_x，u，v指示特定的关系。在本发明的一个实施例中，此标记(有时被本领域的技术人员称为三元组)指示给定移动设备x、其当前接入点AP_u以及它所可能被转移到的另一个接入点AP_v的效率指数。 

接下来，可以用以下等式确定效率指数I_x，u，v： 

I_x，u，v＝(R_x，v/R_x，u)[C_u/C_v]^β        (1) 

其中分数C_u/C_v是拥塞级别比率，参数β是指定网络操作者之类的给予拥塞级别比率与传输速率比率R_x，v/R_x，u相比的相对重要程度。当参数β被设置为等于1时，两个比率被给予相等的重要程度。但是，当参数β被设置为大于1的值时，则拥塞级别比率被给予了比传输速率比率R_x，v/R_x，u高的重要程度。 

根据本发明，给定指数I_x，u，v的值是对在给定反复时间段期间继续使给定移动设备x与其当前相关联的接入点AP_u相关联、或者使移动设备x与另一接入点，即潜在接入点AP_v相关联的合意度的相对指示。按句话说，一般而言，指数I_x，u，v是对在给定反复时间段期间移动设备是否应当保持与其当前接入点相关联、或者是否应当被重新分配并且以另一接入点相关联以便符合WLAN1的负载平衡目标的相对指示。通过考虑给定反复时间段期间接入点的拥塞级别以及接入点和移动设备期间的传输速率，移动设备可以与给定接入点(即其当前接入点或潜在接入点)相关联，而不会危害整体网络吞吐量和WLAN的负载平衡目标。 

在本发明的另一个实施例中，当在给定反复时间段期间生成的指数I_x，u，v等于或大于阈值γ时，控制器10可以使移动设备x与潜在接入点AP_v相关联(即将移动设备x的关联关系从其当前接入点AP_u更改为潜在接入点AP_v)。即，网络操作者可以为每个指数I_x，u，v选择特定的阈值γ。 

例如，如果阈值γ被设置为2，则仅当生成的效率指数I_x，u，v等于2或更大时，移动设备的关联关系才会被从其当前接入点(例如AP_u)更改为另一接入点(例如AP_v)。 

应当理解，阈值γ的值是设计选择之一，并且对于不同WLAN或不同反复时间段可能是不同的。但是，一般而言，阈值γ的值应当被设置为等于1或更大。 

稍微回顾一下，之前提到过拥塞级别比率是基于接入点AP_u和AP_v处的拥塞级别的。在本发明的另一个实施例中，这些拥塞级别是基于反复时间段期间每个接入点AP_u或AP_v的下行链路分组流而不是上行链路流所经历的拥塞的。其根本原因是接入点要测量下行链路延迟相当容易，而接入点要测量上行链路延迟则相当困难。对于大多数情况，使用下行链路延迟是对整体延迟的良好近似，这是因为毕竟大多数信息都是在下行链路方向上传输的。此外，上行链路和下行链路方向上的拥塞级别之间有强正相关。对于给定接入点AP_w，标记Dw(t) 可用于指示这种测得的下行链路延迟。 

除了平均下行链路延迟，每个接入点处的拥塞级别还考虑了每个接入点的丢失概率(即下行链路分组将会由于拥塞而被接入点丢弃的概率)。反复时间段T期间AP_w的丢失概率可由值Lw(t)表示。 

另外，应当理解Dw(t)和Lw(t)都可在反复时间段T基于由AP处理的下行链路分组来测量。 

结合Dw(t)和Lw(t)，给定AP的拥塞可由以下等式表示： 

Cw(t)＝Dw(t)+αLw(t)                       (2) 

其中值α可用于适当调整在计算AP的拥塞级别时与延迟作用相比给予丢失概率的作用的权重(即重要程度)。 

根据等式(2)，Little的式子(本领域中已知)可用于进一步将平均延迟Dw(t)表示为： 

Dw(t)＝Qw(t)/Aw(t)               (3) 

其中Aw(t)表示反复时间段T期间，到达AP w的可能在下行链路信道上传输到一个或多个移动设备的分组的平均速率，Qw(t)是APw的队列中存在的下行链路分组的数目。 

到目前为止，以上论述主要集中于单个移动设备x和两个接入点AP_u和AP_v。但是，如上所述，本发明可应用于多个移动设备和接入点。在记住这一点的情况下，本发明提供了利用从多个移动设备和接入点导出的多个生成的效率指数的负载平衡方法和设备，其中每个指数是在每个反复时间段期间重复地重新计算和生成的。 

在每个反复时间段T期间，在多个指数中的每一个已被生成之后，控制器10可操作以用于确定生成的指数中的哪一个等于或超过阈值γ。对于每个其值等于或超过阈值γ的指数，在特定反复时间段T期间存在以下可能：将移动设备的关联关系从当前接入点转移或更改到另一潜在接入点(以下有时称为“转移”)。 

在本发明的另一实施例中，一旦指数已被生成，控制器10就可操作以用于创建与生成的指数相关联的各种所谓的“转移候选者”的表，其中每个转移候选者可由三元组x，u，v表示，其中，正如之前那样， x是移动设备，u是x当前与之相关联的接入点，v是在某个稍后的时间段T期间x可能被切换到的接入点。 

根据本发明的一个实施例，这种表中的转移候选者可以按降序列出，以使得那些具有较大指数I_x，u，v的转移候选者被排序在那些具有小指数的之前。 

在创建这样的有序指数列表之后，控制器10可操作以用于选择最高指数及其相关联的转移候选者，以便确定转移是否有正当理由。在对第一被选指数做出这种判定之后，控制器10可操作以用于重复的选择下一个等级最高的指数及其转移候选者等。对下一指数的选择继续下去，直到选择了排序后的顺序中的每个指数，或者直到符合另一约束(以下论述)。 

指数I_x，u，v和转移候选者的这种有序表为控制器10(从而为网络操作者)赋予了确定转移的优先级的能力：即那些最不利地影响WLAN的整体负载平衡目标的移动设备-接入点关联关系可最先被处理。 

但是，在控制器10可以执行与被选指数及其转移候选者相关联的转移之前，本发明可能要求控制器10确保存在或已满足其他条件。即，在执行将移动设备从一个接入点转移到另一个之前的每个反复时间段期间，控制器10可操作以用于验证某些其他约束不禁止这样的转移。 

一个这种对于转移的约束被用于避免所谓的“拥塞振荡”。 

一般而言，拥塞振荡发生在一个接入点上的负载被转移到另一接入点而只是导致了另一接入点的拥塞之时。然后，作为响应，另一接入点可能将同一负载转移回原始接入点，此时原始接入点可能尝试再次将负载转移回另一接入点，从而产生了循环。为了防止这种递归循环或振荡模式，本发明的发明人开发了附加特征，这些附加特征可被控制器10用来确定在给定反复时间段期间在选择指数后进行转移是否适当。 

在本发明的一个实施例中，为了防止这种振荡，本发明规定：倘若在当前反复时间段期间，转移出当前接入点AP_u的转移的总数未超 过接入点AP_u上的负载的第一可允许百分比(例如10％)，并且转移进潜在接入点AP_v的转移的总数未超过接入点AP_v上的负载的第二可允许百分比(例如10％)，则控制器10可操作以用于完成转移。在本发明的另一个实施例中，仅当符合两个规定时，才能发生从AP_u到AP_v的转移。 

虽然在以上给出的示例中使用了相同的百分比，但应当理解百分比可以相同也可以不相同。 

如果在给定反复时间段期间，控制器10确定任一个百分比被超过，则控制器10还可操作以用于停止尝试进行转移出接入点AP_u的和转移进接入点AP_v的新转移。通过以这种方式防止转移出接入点AP_u的转移和转移进接入点AP_v的转移，可避免拥塞振荡。 

但是，应当注意，虽然这些规定影响了转移出接入点AP_u的转移或转移进接入点AP_v的转移，但它们不影响转移进接入点AP_u的转移或转移出接入点AP_v的转移，即这种转移仍将继续。 

但是，存在这种情况，即AP负载考虑受到的关注可能低于其他更重要的问题。为了进一步详细描述，有时网络操作者可能意识到特定移动设备负责接入点的负载中的大部分，这在某些情况下导致接入点的拥塞。例如，可能发生以下情况：在给定反复时间段期间，移动设备x负责当前接入点AP_u处理的负载的25％。如果是这样的话，则几乎不可能在不违反例如以上所述的负载约束的情况下更改移动设备x与之相关的接入点。 

意识到这一点，本发明提供了这样一种诸如控制器10的控制器：其可操作以允许在反复时间段期间移动设备x将其关联关系从其当前接入点AP_u更改到接入点AP_v，只要这种转移是第一次转移出AP_u的转移。 

然后，从效果上而言，如果控制器10选择一个指数并且该指数指示应当发生转移，则控制器10可操作以允许在特定反复时间段期间这种转移继续，而不论转移中涉及的当前和潜在接入点上的负载如何，只要这种变化代表第一次转移出当前接入点的转移。 

除了考虑反复时间段T期间接入点上的负载以及转移数目以外，本发明的发明人还意识到网络操作者可能要求对转移施加其他约束。 

例如，如果接入点，例如接入点AP_u未被拥塞，则可能不需要将任何移动设备转移出这种接入点。如果发生这种情况，则控制器10可判定首先不将代表这种情况的指数转移候选者放在转移候选者表中；从效果上而言将此指数I_x，u，v设置为等于0。 

类似地，本发明的发明人意识到其他网络操作者可能希望在给定反复时间段T期间只更改“活动(active)”移动设备的AP关联关系。例如，网络操作者可能在特定反复时间段期间移动设备的所谓的分组到达速率大于特定接入点(例如接入点AP_u)处的总分组到达速率的特定百分比时，认为移动设备是活动的。例如，如果与移动设备x相关联的到达速率等于或大于接入点AP_u处的总分组到达速率的至少2％，则移动设备x可被视为活动接入点。 

因此，考虑到这一点，本发明提供了这样一种诸如控制器10的控制器，其可操作以在特定反复时间段T期间测量下行链路到达速率。此下行链路到达速率与移动设备x和当前接入点AP_u相关联。如果测得的到达速率不至少是当前接入点AP_u的总到达速率的某个百分比，则控制器10可操作以用于也拒绝将与这种情况相关联的转移候选者添加到表中。 

应当理解，在给定反复时间段T期间，控制器10按降序从合格指数集合(即超过阈值γ的那些)中选择每个指数及其相关联的转移候选者，并且在进行这种选择时，在考虑到上述约束中的某些或全部之后，确定与被选指数相关联的转移是否适当。 

一旦控制器10到达给定表的末端(即最后的转移候选者集合)，则不会再启动转移。反之，现在将使用任何所指示的转移(即转移设备-接入点关联关系)。 

在下一反复时间段结束时，控制器10可再次构建指数及其相关联的转移候选者的表，并且启动任何所指示的转移。 

在本发明的另一个实施例中，以上提到的反复时间段T可以与所 谓的“运行时间”时间段相关联。利用此运行时间技术，如何执行本发明的一个示例如下。 

在运行时间段期间，控制器10可允许移动设备x保持与当前接入点AP_u相关联。在此运行时间结束时，控制器10可操作以接收分别来自移动设备x和接入点AP_u和AP_v的传输速率和拥塞级别的指示符。在此运行时间期满之前，控制器10还可操作以基于生成的传输速率和拥塞级别比率确定效率指数I_x，u，v。此外，控制器10可操作以用于在判定是否执行转移之前应用上述约束中的一个或多个。如果这种转移是被允许的，则在运行时间结束时，控制器10可操作以用于将移动设备x的AP关联关系从其当前接入点AP_u更改为新的接入点AP_v。然后，控制器10可重复刚刚描述的过程。 

应当理解，控制器10、移动设备x以及接入点AP_u和AP_v的功能和特征可由软件、固件、硬件或三者的某种组合来执行。如果是软件或固件，则一个或多个可编程存储器设备可用于存储一个或多个程序，而这一个或多个程序又可以执行或控制控制器10、移动设备x和/或接入点AP_u和AP_v的功能和特征。 

本发明的技术可联合一个或多个附加技术一起使用，以按照负载平衡目标的规定而不只是信噪比目标的规定来实际更改移动设备内的设置，例如“强制”移动设备变成与特定接入点相关联。一个这种技术在共同未决的美国专利申请No.11/026,904中描述，这里通过引用将其包含进来，就像在这里对其进行了完整阐述一样。 

上述论述利用某些示例给出了对本发明的简要描述。但是，应当理解，本发明的真实范围由所附权利要求书所确定。