用于估计无线网络中的冲突概率的方法和设备

摘要

一种用于估计无线网络内的分组冲突的方法包括：对于每个传输分组，所述网络的接入点(AP)记录统计量传输信息；所述AP基于该统计信息计算在该传输期间生成的时隙时间的总数n、推迟的总次数m以及不成功传输的总数Q；以及所述AP利用针对每个接入类别(AC)的统计量序列(m，n，Q)计算针对不成功分组的冲突概率p。

说明书

相关申请的交叉引用

本申请要求于2007年11月20日提交的美国临时申请No.60/989,278的优先权，该美国临时申请的整个主题通过引用结合于此。

技术领域

本发明通常涉及无线网络，并且更特别地涉及用于估计这种网络内的分组冲突的方法和设备。

背景技术

如在本领域内所公知的那样，无线局域网(WLAN)如今由于其易于部署以及WiFi接口卡的广泛使用而正变得越来越受欢迎。Wi-Fi联盟报告发现在2006年将生产120万个802.11芯片组。

与技术发展并行的是，在通信文献中出现了一阵分析研究。

实验结果和理论研究表明：无线网络可能进入由远非最优的介质利用所表征的饱和时段。更具体来说，在发生多分组丢失时，标准的速率适配机制会降低传输速率。然而，如果所述分组丢失是由于冲突而不是不良信道(这是对于所述速率适配机制的工作假设)所造成的，则控制器会引发更高的冲突概率，所述更高的冲突概率又会滚雪球般导致甚至更低的吞吐量。这种机制由用在来自Lucent的WLAN-II产品中的自动速率回退(ARF)算法所使用，所述自动速率回退(ARF)算法假设所有分组丢失都是由于不良信道所造成的。

这种使用情况促使我们分析并建立一种基于可用信息预测分组丢失原因(分组冲突或不良信道)的分组丢失检测机制。

近来已经提出了两种用以解决这个问题的机制。本发明的方法不同于将在下一段中描述的这两种机制。

Whitehouse等人[K.Whitehouse等人的“Exploiting the CaptureEffect for Collision Detection and Recovery(利用捕获效应来进行冲突检测及恢复)”，The 2^nd IEEE Workshop on Embedded Ne tworkedSensors(EmNetS-II)，2005年5月]假设可以由接收站(设备或接入点)正确地译解分组报头，并且因此可以基于分组终止来推断出是否有分组冲突或者过低的信噪比(SNR)。但是，这种情况在各种各样的有噪声的条件下可能无法发生，正如Yun等人[J.-H.Yun、S.-W.Seo的“Collision Detection based on Transmisión Time Informationin IEEE 802.11Wireless LAN(基于IEEE 802.11无线LAN中的传输时间信息的冲突检测)”，Proceedings of the 4^th Annual Inter.Conf.on Perv.Comp.Comm.Workshop(PERCOMW’06)，2006年]所表明的那样。相反，Yun等人提出了一种确定性方案，通过该确定性方案，参与站包括关于分组传输/接收的时间信息，所述时间信息可以被用来预测何时发生冲突。这种方法虽然非常精确，但是其缺陷在于要修改参与的无线站上的MAC实现方式。

发明内容

根据本发明，提供一种用于估计无线网络内的分组冲突的方法。所述方法包括：对于每个传输分组，所述网络的接入点(AP)记录关于信息传输的统计量；所述AP基于该统计信息计算在该传输期间生成的时隙时间(slot time)的总数n、推迟(deferral)的总次数m以及不成功传输的总数Q；以及所述AP利用针对每个接入类别(AC)的统计量序列(m，n，Q)计算针对不成功分组的冲突概率p。

因此，在本发明中，所述接入点只基于其芯片组或固件可得到的统计量来估计针对不成功分组传输的冲突概率。

在附图和下面的描述中阐述本发明的一个或更多实施例的细节。通过描述和附图以及通过权利要求书，本发明的其它特征、目的和优点将变得显而易见。

附图说明

图1是根据本发明工作的具有一个接入点(AP)和几个站(STA)的无线通信系统的基本服务集(BSS)拓扑；

图2是根据针对IEEE 802.11e无线通信标准的IEEE P802.11eD13.0(2005年1月)的时序图；

图3是根据本发明的用在图1的系统中的方法的流程图；并且

图4是用于理解本发明的时序图；以及

图5是被用于执行一种对分组通信量进行控制或成形的方法的状态机。

各图中的相同的附图标记表示相同的要素。

具体实施方式

现在参照图1，示出了基本服务集(BSS)拓扑。

根据针对IEEE 802.11e无线通信标准的IEEE P802.11e D13.0(2005年1月)，在图2中示出了DCF信道接入的时序。

如在这样的I EEE标准中所描述的那样，各帧之间的时间间隔被称作IFS。站(STA)通过在指定间隔内使用载波感测功能来确定介质处于空闲。定义四种或五种不同的IFS来提供针对接入所述无线介质的优先级水平；除了AIFS之外，从最短到最长按顺序列出所述IFS。因此，如图2中所示：

SIFS是短帧间间距；

PIFS是点协调功能(PCF)间距；

DIFS是分布式协调功能间距；

AIFS是(由QoS设施使用的)仲裁帧间间距；以及

EIFS是扩展帧间间距。

所述不同的IFS独立于STA比特率。所述IFS定时被定义为介质上的时间间隙，并且除了AIFS之外的那些IFS对于每个PHY(物理层)是固定的(即使在有多速率能力的PHY中也是如此)。所述IFS值由所述PHY根据属性确定。

对于每次成功的帧接收，接收站通过发送确认(ACK)帧立即进行确认。所述ACK帧在短的IFS(SIFS)之后被发送，所述短的IFS短于所述DIFS。其它站在所述DIFS空闲时间之后恢复所述退避过程。由于所述数据帧与ACK帧之间的SIFS间隔，所述ACK帧传输受到保护从而免遭其它站的争用。如果在数据传输之后没有接收到ACK帧，则在另一随机退避之后重传该帧。

在内部，对于每个传输分组，假设所述接入点(AP)记录几项信息。作为本发明的方法的实施例的实例，假设报告以下统计量：

-从于接口队列中取得所述分组的时刻开始到所述分组传输结束为止的总传输时间T

-信道在传输期间繁忙的总时间T_busy

-由于介质上的其它传输而导致的倒计数推迟的次数m

-重试次数R

-成功传输标志：b(如果最近一次传输成功则为0，如果不成功则为1)。

基于这些统计量(或者任何其它类似的参数)，所述AP可以计算以下各项：

·在该传输期间生成的时隙时间的总数n

·推迟的总次数m

·不成功传输的总数Q。

例如，基于前面的统计量列表，可以如下计算(m，n，Q)：

m＝m

n＝(T-T_busy-mT_AIFS)/T_σ(1)

Q＝R+b

其中，T_AIFS是仲裁帧间间距(AIFS)时间，而T_σ是时隙时间。

在给定针对每个接入类别(AC)的统计量序列(m，n，Q)的情况下，所述AP接下来实施所描述的估计器，以便在公式(A.2)中计算针对不成功分组的冲突概率p。

一旦已获得了这样的估计之后，就可以进一步估计：

随后，由在与本申请同日提交的标题为“Method and Apparatus toInspect Wireless Traffic and Mitigate Packet Elimination forWireless Saturation Avoidance(用于检查无线通信量并且缓解针对避免无线饱和的分组消除的方法和设备)”的共同待决的专利申请中所描述的适配机制来使用所述概率p(或概率集合Prob[在Q次不成功传输中发生d次冲突])，该共同待决的专利申请被转让给与本申请相同的受让人并且被标识为代理人案卷号2008P12142US01，其整个主题通过引用结合于此。但是在这里应当注意到，在所述共同待决的专利申请中提到的s(t)等同于下文中所提到的p(t)，并且此外等同于基于p如下计算的

$\bar{p}(t+W)=(1-{\alpha }_s)\bar{p}\left(t\right)+{\alpha }_s·p(t+W)$

假设输入数据是索引为k的序列(m_k，n_k，Q_k)_k，其中k为1到f，f是如下所述在其间取得所述统计量的间隔数目。

参照图4，考虑经过压缩的时间t’＝t-T_busy(t)-m(t)T_AIFS。其中，T_busy(t)表示到时间t为止的所述信道繁忙的持续时间，而m(t)表示到时间t为止的推迟次数。基本上，t’随着时隙时间T_σ的递增而增大。

现在所述过程做出以下假设。假设空中分组传输在所述经过修改的时间t’内作为具有速率λ的泊松到达过程而发生：

在当前的分组传输期间，所述介质由于其它传输而繁忙M＝m+D次，其中0≤D≤Q。因此，M是取得以下Q+1个可能值之一的随机变量：{m，m+1，...，m+Q}。

M代表这里的泊松过程在T_idle-mT_AIFS的时间期间的到达次数，其中T_idle＝t-T_busy(t)。

随后写出在给定参数s和λ的情况下得到该数据(m，n，Q)的似然性，从而得到下式：

$P(m,n,Q|s,\lambda )=\underset{d=0}{\overset{Q}{\Sigma }}\left(\begin{array}{c}Q\\ d\end{array}\right)s^d{(1-s)}^{Q-d}\mathrm{Prob}(D=d|\lambda )$

其中剩余的概率代表恰好有d次冲突(从而是m+d次到达)的概率。(在给定泊松过程假设的情况下)可以如下表达该概率：

$\mathrm{Prob}(D=d|\lambda )=\frac{{\left(\mathrm{\lambda n}{T}_{\sigma }\right)}^{m+d}}{(m+d)!}{e}^{-\mathrm{\lambda n}{T}_{\sigma }}$

把这两个公式合在一起并且表示Λ＝λT_σ，就可以获得：

$P(m,n,Q|s,\Lambda )=\underset{d=0}{\overset{Q}{\Sigma }}\left(\begin{array}{c}Q\\ d\end{array}\right)s^d{(1-s)}^{Q-d}\frac{{\left(\mathrm{\Lambda n}\right)}^{m+d}}{(m+d)!}{e}^{-\mathrm{\Lambda n}}$

在该似然性中可以把s和Λ这两个参数进一步相关。可以观测到s代表在下一个时隙时间内发生除了自身的传输之外的分组传输的概率。这意味着s＝1-e^-Λ或者Λ＝-log(1-s)。在给定各时间间隔的观测序列(m_k，n_k，Q_k)_k情况下，可以获得：

冲突概率p的最大似然性估计器(MLE)变为：

在图3中的流程图中示出了这个过程。因此，在步骤100，所述接入点(AP)对于每个传输分组记录以下统计量传输信息：

(例如：

-从于接口队列中取得所述分组的时刻开始到所述分组传输结束为止的总传输时间T

-信道在传输期间繁忙的总时间T_busy

-由于介质上的其它传输而导致的倒计数推迟的次数m

-重试次数R

成功传输标志：b(如果最近一次传输成功则为0，如果不成功则为1))。

接下来，在步骤200，所述AP基于该统计信息计算以下各项：

·在该传输期间生成的时隙时间的总数n

·推迟的总次数m

·不成功传输的总数Q。

接下来在步骤300，所述AP确定是否已经获得了足够的统计量；如果没有，则所述过程返回到步骤100。如果已经获得了足够的统计量，则在给定针对每个接入类别(AC)的统计量序列(m，n，Q)的情况下，所述AP在步骤400根据上面的等式A.2计算针对不成功分组的冲突概率s。因此，所述针对不成功分组的冲突概率s提供了关于分组拥塞程度的度量。

在确定了由所述针对不成功分组的冲突概率s表征的拥塞程度之后，使用对分组通信量进行控制或成形的方法(在这里被称作缓解策略)。

如果所述拥塞程度大于在步骤400所确定的阈值(图1)，则所述方法对当前分组通信量中的一些进行调节，以便减轻潜在的问题(步骤500)，这里在与本申请同日提交的标题为“Method and Apparatusto Inspect Wireless Traffic and Mitigate Packet Elimination forWireless Saturation Avoidance(用于检查无线通信量并且缓解针对避免无线饱和的分组消除的方法和设备)”的共同待决的专利申请中描述了对分组通信量进行控制或成形(步骤600)，该共同待决的专利申请被转让给与本申请相同的受让人，并且被标识为代理人案卷号2008P12142US01，其整个主题通过引用结合于此。

如在这样的共同待决的专利申请中所描述的那样，一种缓解策略定义根据拥塞程度要采取的动作。上面描述了一种基于与阈值进行比较的简单方法。一旦估计出拥塞程度，就可以实施更加复杂的控制机制。例如可以实施状态机(在下面被称作WiSAT)，其中利用与在前的计算状态相结合的多个阈值，以便确定所述缓解策略，即将在图5中所示的WiSAT状态机的每个状态下采取的动作。

针对WiSAT(无线饱和)的状态机

可以利用有限状态机来对更加复杂的饱和检测器进行建模。与如之前利用瞬时特征值来判断饱和不同，所述判断和将要采取的动作还与在前的状态(或者在前的测量)有关。所述状态机被称作WiSAT状态机：

现在参照图5，WiSAT机的状态与多个因素有关。

·估计：分别有p、其中p是分组拥塞的度量

·参数，例如α_STATE(用于根据状态p计算的平滑率)

针对分类器和经过平滑的分类器的特定统计量/阈值/间隔输出图5：具有状态STATE＝0/1/2的WiSAT状态机。条件Cij引导从状态i到状态j的过渡。

更精确地说，下面的组成部分对于定义所述状态机和所述状态机的逻辑来说是需要的：

当前状态STATE(STATE＝0代表NonSAT，或者说非饱和；1代表PreSAT或者说预饱和，并且2代表SAT或者说饱和)

条件C_ij(i，j＝0，1，2)以下面的格式定义各状态之间的过渡：

$C_{\mathrm{ij}}=\left(p\left(t\right)o_{\mathrm{ij}}{\delta }_{\mathrm{ij}}\right)r_{\mathrm{ij}}\left(\bar{p}\left(t\right){\tilde{o}}_{\mathrm{ij}}{\tilde{\delta }}_{\mathrm{ij}}\right)$

其中：

p(t)、是所述冲突概率及其平滑值的WiSAT估计o_ij、是分别针对p、的关系参数≤和＞δ_ij、是分别针对p、的阈值参数

r_ij是逻辑关系运算符AND (“与”)、OR(“或”)的其中之一

实例(应当注意到，未指定的条件被定义成使得来自一个状态的所有离开过渡概率相加得1并且互斥。条件C_ij(i，j＝0，1，2)被如下实施：(为了标记简单起见重命名对应于上面的一般名称的5个参数δ₀＝δ₀₁、)

有限状态机(FSM)状态过度规则实例

缓解

缓解策略代表在所述WiSAT状态机的每个状态下将要采取的动作。

·NonSAT-将不采取动作。

·PreSAT-根据下面的算法之一，可以采取的动作包括队列长度改变或者丢弃(语音)分组，或者更一般来说是丢弃给定接入类别的分组。

·SAT-动作可以更加激烈，涉及许可控制与丢弃给定接入类别(即语音)的分组的组合。

算法：对丢弃率N采取动作

参数：

最大和最小丢弃率N₀、N_SAT

临界阈值

输出：N

其中，N＝-1意味着没有分组被丢弃；另外，对于N＞＝0则意味着丢弃每N个相继分组当中的一个分组；例如N_SAT＝2。

应当注意到：如果发生饱和，则可以继续向前采取在PreSAT状态下所采取的最近的动作，直到由条件C21/C20命令改变状态为止。

其它算法：对MAC队列长度L采取动作

除了上面的方案1之外，还可以使用其它算法方案来实现类似的效果：

方案2：设计虚拟队列长度L。当所述虚拟队列全满时，任何呼入分组都将被丢弃

方案3：对于每个客户端，丢弃其每第(m+1)个分组；

方案4：对于每个客户端，如果同一客户端的R个分组已经在所述队列中，则丢弃呼入分组

举例来说，方案2提出集中于控制所述MAC队列长度：

参数：

最大/最小MAC队列长度L₀、L_min

临界阈值γ

输出：L

3、WiSAT参数的概要

为了实现所述状态机，推荐WiSAT的参数化实现方式，以便能够调谐两种类型的参数：

状态的实现方式

状态存储器及管理s

状态平滑率α₀、α₁、α₂

s(t)，在这里由给定时间t的冲突概率p(t)来替换在这里由来替换N(t)以及用于计算N的参数：N_o、N_SAT、β₂、γ每次状态过渡(i，j)的过渡实现方式

o_ij、是分别针对p(t)、的关系参数≤和＞

δ_ij、是分别针对p(t)、的阈值参数

r_ij是逻辑关系运算符AND(“与”)、OR(“或”)

举例来说，利用下面的参数对于之前的实例状态机已执行了WiSAT的仿真和缓解策略(但是仅仅利用仿真的缓解决策，而没有真正在控制环路中进行干预以丢弃任何分组)：

在这里，所述分类器公式简单地由在诸如10个100毫秒的读数的时间段内(即在1秒的窗口内)规则地估计的所述冲突概率和经过平滑的冲突概率给出，并且将所述概率与适当的阈值进行比较或者采用在饱和逻辑中(如由所述WiSAT状态机所描述的那样)。

WiSAT分类器能够每100毫秒进行一次判断：因此针对WiSATS和给出判断的窗口(时间步)W是100毫秒

针对不同状态的的WiSAT计算：α＝α₀＝α₁＝α₂＝0.1；

在该实例中给出的状态过渡条件(逻辑)Cij(i，j＝0，1，2)

在该实例中给出的针对所述状态过渡的分类器距离(WiSAT函数)参数δ₀、ε具有以下值：

δ₀＝0.2、

N个算法参数N₀＝45、N_SAT＝2、β₂＝430、ε＝0.6。

已经描述了本发明的多个实施例。但是应当理解的是，在不偏离本发明的精神和范围的情况下可以做出许多修改。相应地，其它实施例在下列权利要求书的范围之内。