CN105284079A - 一种csma-ca半窗方案的系统和方法 - Google Patents

Abstract

本实施例用于实现802.11网络或其他能够从中受益的合适的无线网络中的CSMA-CA半窗方案。所述半窗方案通过添加概率预测因子改进退避时间的计算方法。所述退避时间是站点(STA)访问无线传输介质的延迟时间的一部分。所述概率预测因子用于调整基于所述STA的介质访问概率计算所述退避时间的竞争窗口(CW)。所述STA将所述CW划分为至少2个半窗，然后根据窗口的信息增益选择其中一个半窗进行概率预测。所选的窗口用于为所述退避时间选择随机数。退避时间的计算方法得到改进之后，减少了STA之间访问所述介质的竞争。

Description

一种CSMA-CA半窗方案的系统和方法

本申请要求于2013年6月19日由ShengSun等递交的申请号为61/836,942、发明名称为“一种CSMA-CA半窗方案的系统和方法(SystemandMethodforCSMA-CAHalfWindowScheme)”的美国临时申请案的在先申请优先权，以及于2014年6月19日递交的申请号为14/309,521、发明名称为“一种CSMA-CA半窗方案的系统和方法(SystemandMethodforaCSMA-CAHalfWindowScheme)”的美国非临时申请案的在先申请优先权，该在先申请的内容以引入的方式并入本文。

技术领域

本发明涉及无线通信，并且在一些特定的实施例中，涉及一种载波侦听多址访问/冲突避免(CSMA-CA)半窗方案的系统和方法。

背景技术

当前用于IEEE802.11(WiFi)通信的CSMA-CA方案中，站点(STA)延迟一个确定的退避时间如数微秒(μsec)之后访问传输数据的介质。通过从预先确定的竞争窗口大小中选择随机数来计算所述退避时间。使用所述退避时间计算公式进行的吞吐量的马尔可夫链分析表明，在正常的网络条件(STA或者传输的密度满足要求)下，峰值吞吐量可以保持在总吞吐量的70％左右。根据检测所述STA与其他STA传输是否冲突并基于先前的成功或失败，增大或减小所述竞争窗口的大小。用于确定退避时间的方案得到改进之后，STA之间的冲突减少、总吞吐量增加，比如，对于STA或传输比较集中的情况效果显著。

发明内容

根据一实施例，一种用于无线通信网络中的站点进行载波侦听多址访问/冲突避免(CSMA-CA)的方法包括：采集与先前延迟访问用于传输数据的介质的尝试相关的信息。所述延迟包括根据竞争窗口确定的退避时间。所述方法还包括：根据所述信息，为所述竞争窗口的多个窗口区中的每个窗口区确定成功访问所述介质的概率值；根据为所选窗口区确定的成功概率值，从所述多个窗口区中选择所述窗口区。

根据另一实施例，一种用于无线通信网络中的站点进行CSMA-CA的方法包括：根据先前退避时间的数值，采集与先前延迟访问数据传输介质的尝试相关的数据集合，其中，所述退避时间的数值根据竞争窗口确定。所述方法还包括：将所述竞争窗口划分为第一半窗和第二半窗；根据所述数据集合，为所述第一半窗计算成功访问所述介质的第一概率值。根据所述数据集合，进一步为所述第二半窗计算成功访问所述介质的第二概率值。然后，根据所选第一半窗的第一成功概率值和所选第二半窗的第二成功概率值中的一个概率值，选择所述第一半窗和所述第二半窗中的一个半窗，用于生成确定退避时间的随机数。

根据又一实施例，一种支持CSMA-CA的通信设备包括：至少一个处理器，以及存储所述至少一个处理器执行的程序的非瞬时性计算机可读存储介质。所述程序包括用于执行以下操作的指令：采集与先前延迟访问用于传输数据的介质的尝试相关的信息，其中，所述延迟包括根据竞争窗口确定的退避时间。所述程序还包括用于执行以下操作的指令：根据所述信息，为所述竞争窗口的多个窗口区中的每个窗口区确定成功访问所述介质的概率值；根据为所选窗口区确定的成功概率值，从所述多个窗口区中选择所述窗口区。所述设备还用于根据所选窗口区确定新的退避时间。

上文概括性地描述了本发明实施例的特征，以便更好地理解后文对于本发明的具体描述。本发明实施例的附加特征和优势将在后文中描述，构成本发明权利要求的主题。本领域技术人员应当理解，所公开的概念和特定实施例易被用作修改或设计其他实现与本发明相同的目的的结构或过程的基础。本领域的技术人员还应当意识到，这种等同构造不脱离所附权利要求书所阐述的本发明的精神和范围。

附图说明

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

图1示出了一种空闲信道评估(CCA)方案；

图2示出了一种载波侦听多址接入访问/冲突避免(CSMA-CA)方案；

图3示出了本发明实施例提供的一种半窗方案决策树；

图4示出了本发明实施例提供的一种半窗方案；

图5为可以用于实现各种实施例的处理系统的图。

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

具体实施方式

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

图1示出了例如用于STA访问介质的当前IEEE802.11空闲信道评估(CCA)方案。本文中的STA可以为任意用户无线设备或接入点(AP)。例如，STA包括智能手机、平板电脑、便携式电脑以及台式电脑。AP为允许其他STA接入WiFi等无线网络的任意设备。在访问所述介质以发送数据之前，STA(或AP)等待一个帧间间隔(IFS)时间。在等待所述IFS时间之后，所述STA进一步将其数据传输延迟一个退避时间(例如，单位为μsec)，以保证延迟时间足够用以避免与其他传输(来自其他STA的传输)的冲突。在数据传输之后，所述STA也可以等待一个IFS时间再接收确认(Ack)信号。

在当前IEEE802.11CSMA-CA方案中，通过(STA)在0和预先确定的竞争窗口(CW)大小之间随机选择一个数(整数)，再将该数乘以预定义的(最小)时隙(例如，单位为μsec)计算访问所述介质所需的退避时间。所述CW的大小限制在预定义的最小CW(CWmin)和预定义的最大CW(CWmax)之间。进一步地，根据所述CSMA-CA方案，基于访问所述介质时的冲突检测来增大或减小所述CW的大小。例如，在先前访问所述介质失败的情况下，将所述CW的大小加倍；或者，在没有发生冲突的情况下，将所述CW的大小重置为最小值CWmin。图2示出了CSMA-CA算法。

802.11站点(STA)使用下面的标准等式计算所述退避时间：Back-offTime＝Random(0,CW)xSlottime，其中，CW限制在CWmin和CWmax之间；Random()是随机函数生成器；Slottime是预定义的时隙。所述算法可以表述如下：

在[CWmin,CWmax]之间选择随机等待时间；

CCA:

if(Idle)

Back-offTime＝Back-offTime-1；

if(Back-offTime＝0),send；

if(collision)

CW＝2xCW；

elseBack-offTime＝0andsend；

elseBack-offTime＝Back-offTime-1；

else

CW＝CW.

本文提供的实施例用于实现802.11网络或其他能够从中受益的合适的无线网络中的CSMA-CA半窗方案。所述半窗方案用于通过添加概率预测因子改进所述退避时间的计算方法。基于所述STA的介质访问概率，使用概率预测因子调整所述CW。在所述半窗方案中，所述STA基于概率预测的信息增益(G)建立决策树。所述决策树将所述CW划分为2个半窗，所述STA再从所述半窗中选出一个半窗，选择其中的随机数作为所述退避时间。具体描述如下：所述2个半窗为左半窗(CWmin≤X≤CWhalf)和右半窗(CWhalf≤X≤CWmax)，其中CWhalf＝(CWmax–CWmin)/2，且X为所述从2个半窗中选择的数。所述半窗方案极大地提高了总吞吐量。在另一些实施例中，将所述CW划分为超过2个半窗从而选择随机数作为所述退避时间。

所述半窗方案的基础是，在选择退避时间时，通过选择合适的具有较大成功概率的CW大小(发生冲突的可能性较小)来调整或者调谐所述随机函数生成器Random()。基于概率函数(p)调整所述CW。通过每个半窗的熵(E)的差分信息增益(G)计算所述函数p。首先通过历史信息S＝{(r1,st1)；(r2,st2)；(r3,st3)…；(rn,stn)}训练所述STA，其中，r为基于Random()随机生成的实数(0到1之间)，st表示访问所述介质的布尔状态(成功或者失败)。在所述训练阶段之后，所述STA计算每个半窗的增益并基于所述增益选择合适的半窗。所述STA可以重复该过程，例如，在每次访问所述介质时重复该过程。

所述CSMA-CA半窗方案利用所述无冲突访问介质成功/失败的历史信息，以通过将所述随机函数生成器调谐为2个半窗来预测下一个访问CW。所述训练阶段处理所述历史信息以求得每个半窗的成功概率，并且下一个半窗阶段调整所述CW，以便基于所述概率选择随机数作为所述退避时间。所述方案利用熵计算以及信息增益等式，并相应地生成所述2个半窗的决策树。所述决策树为所述STA中运行的状态，所述STA基于所述历史信息计算所述信息增益和熵，然后确定选择哪个半窗。

在训练阶段，所述STA采集自己的历史窗口信息集合S{(r,st)}，其中，r为随机生成的实数；st表示成功(记为+)或者失败(记为-)的布尔状态。例如，S可以为{(199,-)；(83,+)；(156,+)；(136,-)；(251,+)；(177,+)；(103,+)；(206,-)；(58,-)；(130,+)；(226,-)；(62,+)；(152,+)；(242,+)}。在所述S中有14个样本，其中有9次访问所述介质的先前尝试为成功(+)，5次失败(-)，记为(9+,5-)，因此，计算所述熵得到E(9+,5-)＝-9/14log₂(9/14)-5/14log₂(5/14)＝0.94。除了所述指数函数(log₂)，还可以使用其他任意合适的函数计算所述熵，比如通过任意合适的硬件(芯片)或软件的实现方式计算所述熵。合适的实现方式可以基于成本、功率要求、计算速度、准确性或者其他系统设计条件而确定。

然后，在半窗阶段，所述STA基于所得到的信息增益建立决策树，其中，所述信息增益是基于上面获得的所述熵计算得到的。所述信息增益可以通过以下公式得到：在上面S＝(9+,5-)的例子中，左半窗S(31≤X≤112)＝[6+，2-]得到熵为E＝0.811；右半窗S(112<X≤255)＝[3+，3-]得到熵为E＝1，其中，CWmin＝31，CWhalf＝112，CWmax＝225。因此，S(31≤X≤112)的增益＝0.94-(8/14)0.811；S(112＜X≤255)的增益＝0.94-(6/14)1＝0.4286。如图3所示，对这2个集合的计算形成了所述决策树的2个分支。由于S(31≤X≤112)的增益>S(112＜X≤255)的增益，因此，所述STA选择Random(31≤X≤112)来获得所述退避时间的随机数。

图4示出了包括以上所描述的定时阶段和半窗阶段的半窗算法的实施例。在图中，左半窗(或者半窗)记为(＜0.5)，右半窗记为(＞0.5)。计数器用于确定生成所述决策树的时间。设置计数器时间以确保采集足够多的访问所述介质成功/失败结果的历史样本，使概率预测具有充分的准确性，从而保证合理选择半窗。

通过修改所述802.11CSMA-CA过程使其包括以下用于计算所述退避时间的公式，可以得到改进后的CSMA-CA半窗方案：

对于典型的退避时间计算使用back-offTimeReg＝Rand(0,CW)*Slottime(未做改进)；对于选择左半窗(半窗)的情况，使用back-offTimeHwL＝Random(CWmin,CWhalf)*Slottime；对于选择右半窗(半窗)的情况，使用back-offTimeHwH＝Random(CWhalf,CWmax)*Slottime)。

在上面的实施例中，所述竞争窗口划分为2个半窗以建立具有2个分支的决策树。在另一些实施例中，所述竞争窗口可以划分为任意适当数量的更小的窗口以建立具有超过2个分支的决策树。例如，所述竞争窗口可以划分为4个窗口：(CWmin≤X＜CW(1/4)，CW(1/4)＜X≤CW(1/2)，CW(1/2)＜X＝CW(3/4)，CW(3/4)＜X≤CWmax)，其中，CW(1/4)＝(CWmax-CWmin)/4，CW(1/2)＝(CWmax-CWmin)/2，且CW(3/4)＝(CWmax-CWmin)x3/4。还可以是其他数量的窗口，比如，3、5、6、7、8或其他数量。在又一些实施例中，这些窗口可以划分成不相等的时隙，其中，一些窗口可以大于或小于其他窗口。在这些实施例的任一实施例中，根据窗口的数量及其大小计算熵和信息增益。

图5为可用于实施各种实施例的处理系统500的方框图。处理系统500可以为STA或其他网络设备的一部分。特定装置可利用所有所示的组件或所述组件的仅一子集，且装置之间的集成程度可能不同。此外，设备可以包括部件的多个实例，例如多个处理单元、处理器、存储器、发射器、接收器等。处理系统500可以包括配备一个或多个输入/输出设备，例如扬声器、麦克风、鼠标、触摸屏、按键、键盘、打印机、显示器等的处理单元501。处理单元501可包括中央处理器(CPU)510、存储器520、大容量存储设备530、视频适配器540，以及连接到总线的I/O接口560。所述总线可以为任何类型的若干总线架构中的一个或多个，包括存储总线或者存储控制器、外设总线等等。

所述CPU510可包括任何类型的电子数据处理器。存储器520可包括任意类型的系统存储器，例如静态随机存取存储器(SRAM)、动态随机存取存储器(DRAM)、同步DRAM(SDRAM)、只读存储器(ROM)或其组合等等。在实施例中，存储器520可包括在开机时使用的ROM以及在执行程序时使用的存储程序和数据的DRAM。在实施例中，存储器520是非瞬时的。大容量存储器设备530可包括任意类型的存储设备，其用于存储数据、程序和其它信息，并使这些数据、程序和其它信息通过总线访问。大容量存储器设备530可包括如下项中的一种或多种：固态磁盘、硬盘驱动器、磁盘驱动器、光盘驱动器等等。

视频适配器540以及I/O接口560提供接口以将外部输入以及输出装置耦合到处理单元上。如图所示，输入输出设备的示例包括耦合至视频适配器540的显示器590和耦合至I/O接口570的鼠标/键盘/打印机560的任意组合。其它设备可以耦合至处理单元501，可以利用附加的或更少的接口卡。举例来说，串行接口卡(未图示)可以用于为打印机提供串行接口。

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

虽然本发明中已提供若干实施例，但应理解，在不脱离本发明的精神或范围的情况下，本发明所公开的系统和方法可以以许多其他特定形式来体现。本发明的实例应被视为说明性而非限制性的，且本发明并不限于本文本所给出的细节。例如，各种元件或部件可以在另一系统中组合或合并，或者某些特征可以省略或不实施。

此外，在不脱离本发明的范围的情况下，各种实施例中描述和说明为离散或单独的技术、系统、子系统和方法可以与其它系统、模块、技术或方法进行组合或合并。展示或论述为彼此耦合或直接耦合或通信的其它项也可以采用电方式、机械方式或其它方式通过某一接口、设备或中间部件间接地耦合或通信。其他变化、替代和改变的示例可以由本领域的技术人员在不脱离本文精神和所公开的范围的情况下确定。

Claims (24)

1.一种用于无线通信网络中的站点进行载波侦听多址访问/冲突避免(CSMA-CA)的方法，其特征在于，所述方法包括：

采集与先前延迟访问用于传输数据的介质的尝试相关的信息，其中，所述延迟包括根据竞争窗口确定的退避时间；

根据所述采集的信息，为所述竞争窗口的多个窗口区中的每个窗口区确定成功访问所述介质的概率值；

根据为所选窗口区确定的成功概率值，从所述多个窗口区中选择所述窗口区。

2.根据权利要求1所述的方法，其特征在于，所述选择步骤包括选择具有最大成功概率值的窗口区。

3.根据权利要求1所述的方法，其特征在于，还包括：根据所选具有较大成功概率值的窗口区确定新的退避时间。

4.根据权利要求3所述的方法，其特征在于，根据所选窗口区确定所述新的退避时间，包括：通过随机函数生成器，从所选窗口区中生成所述新的退避时间的数值。

5.根据权利要求1所述的方法，其特征在于，还包括：

执行空闲信道评估(CCA)过程以访问所述介质，其中，所述CCA过程包括：等待一个帧间间隔(IFS)时间以及所述退避时间之后，在所述介质上传输所述数据；

每执行一次所述CCA过程，增加已完成CCA步骤的计数器的值；

采集所述信息各自的样本。

6.根据权利要求4所述的方法，其特征在于，还包括：

重复所述CCA过程，增加所述计数器的值，并采集所述信息各自的样本直到所述计数器的值达到预定义的最大值；

当所述计数器的值达到所述预定义的最大值时，启动所述为所述多个窗口区中的每个窗口区确定成功概率值。

7.根据权利要求1所述的方法，其特征在于，根据所述信息，为所述竞争窗口的多个窗口区中的每个窗口区确定成功访问所述介质的概率值，包括：

根据所述信息，为每一个所述窗口区确定熵；

根据所述熵，为每一个所述窗口区确定信息增益。

8.根据权利要求1所述的方法，其特征在于，所述竞争窗口的大小限制在预定义的最小竞争窗口和预定义的最大竞争窗口之间。

9.根据权利要求8所述的方法，其特征在于，所述窗口区为两个半窗区，包括左半窗和右半窗，其中，所述左半窗的大小限制在所述预定义的最小竞争窗口和所述竞争窗口大小的一半之间；所述右半窗的大小限制在所述竞争窗口大小的一半和所述预定义的最大竞争窗口之间。

10.根据权利要求1所述的方法，其特征在于，所述信息排列在包含多个数值对的集合中，其中，每个所述数值对包括指示对应的无冲突访问所述介质的先前尝试成功或失败的布尔状态，以及用于确定所述对应的先前尝试的退避时间的在0到1之间生成的随机数。

11.一种用于无线通信网络中的站点进行载波侦听多址访问/冲突避免(CSMA-CA)的方法，其特征在于，所述方法包括：

根据先前退避时间的数值，采集与先前延迟访问数据传输介质的尝试相关的数据集合，其中，所述退避时间的数值根据竞争窗口确定；

将所述竞争窗口划分为第一半窗和第二半窗；

根据所述数据集合，为所述第一半窗计算成功访问所述介质的第一概率值；

根据所述数据集合，为所述第二半窗计算成功访问所述介质的第二概率值；

根据所选第一半窗的第一成功概率值和所选第二半窗的第二成功概率值中的一个概率值，选择所述第一半窗和所述第二半窗中的一个半窗；

从所述第一半窗和第二半窗选出的一个半窗中生成用于确定退避时间的随机数。

12.根据权利要求11所述的方法，其特征在于，所述选择步骤包括选择所述第一半窗和第二半窗中具有较大成功概率值的一个半窗。

13.根据权利要求11所述的方法，其特征在于，在半窗方案阶段之前的定时阶段采集所述数据集合，其中，在所述半窗方案阶段计算所述第一概率值和所述第二概率值。

14.根据权利要求13所述的方法，其特征在于，在所述定时阶段期间，还包括：

初始化计数器；

执行空闲信道评估(CCA)过程的多个实例以访问所述数据传输介质，其中，所述CCA过程包括：等待一个帧间间隔(IFS)时间以及先前确定的退避时间之后，在所述介质上传输数据；

在完成所述CCA过程的实例中的每个实例时，增加所述计数器的值；

每完成所述CCA过程的实例中的一个实例时，向所述数据集合中添加一对数值；

当所述计数器达到预定义的最大值时，启动所述半窗方案阶段。

15.根据权利要求13所述的方法，其特征在于，计算所述第一概率值包括根据所述数据集合，为所述第一半窗计算熵以及对应的信息增益；计算所述第二概率值包括根据所述数据集合，为所述第二半窗计算熵以及对应的信息增益。

16.根据权利要求15所述的方法，其特征在于，在所述半窗方案阶段期间，还包括：

为所述数据集合计算熵，其中，所述第一半窗和所述第二半窗中的每个半窗的熵和信息增益与所述数据集合的熵一致；

建立一个决策树，其中，根节点包括所述数据集合和所述数据集合的熵，左叶节点包括所述第一半窗的熵和信息增益，右叶节点包括所述第二半窗的熵和信息增益。

17.根据权利要求11所述的方法，其特征在于，所述无线通信网络为IEEE802.11网络，且所述站点为所述IEEE802.11网络中的WiFi设备或者接入点(AP)。

18.一种支持载波侦听多址接入访问/冲突避免(CSMA-CA)的通信设备，其特征在于，所述通信设备包括：

至少一个处理器；

存储所述至少一个处理器执行的程序的非瞬时性计算机可读存储介质，所述程序包括用于执行以下操作的指令：

采集与先前延迟访问用于传输数据的介质的尝试相关的信息，其中，所述延迟包括根据竞争窗口确定的退避时间；

根据所述信息，为所述竞争窗口的多个窗口区中的每个窗口区确定成功访问所述介质的概率值；

根据为所选窗口区确定的成功概率值，从所述多个窗口区中选择所述窗口区；

根据所选窗口区确定新的退避时间。

19.根据权利要求18所述的通信设备，其特征在于，所述选择所述窗口区的指令包括选择具有最大成功概率值的窗口区的指令。

20.根据权利要求18所述的通信设备，其特征在于，所述根据所选的窗口区确定所述新的退避时间的指令包括通过随机函数生成器，从所选窗口区中生成所述新的退避时间的数值的指令。

21.根据权利要求18所述的通信设备，其特征在于，所述程序还包括用于执行以下操作的指令：

执行空闲信道评估(CCA)过程以访问所述介质，其中，所述CCA过程包括：等待一个帧间间隔(IFS)时间以及所述退避时间之后，在所述介质上传输所述数据；

每执行一次所述CCA过程，增加已完成CCA步骤的计数器的值；

采集所述信息各自的样本。

22.根据权利要求21所述的通信设备，其特征在于，所述程序还包括用于执行以下操作的指令：

重复所述CCA过程，增加所述计数器的值，并采集所述信息各自的样本直到所述计数器的值达到预定义的最大值；

当所述计数器的值达到所述预定义的最大值时，启动所述为所述窗口区中每个窗口区确定概率值。

23.根据权利要求18所述的通信设备，其特征在于，所述通信设备为WiFi站点。

24.根据权利要求18所述的通信设备，其特征在于，所述通信设备为IEEE802.11网络中的接入点(AP)。