技术领域

本发明属于软件技术、无线网络技术和数学建模方法在无线网络节点接入与 共享信道方面的应用，适用于包含基于IEEE 802.11标准的无线网络的各种便携 计算设备。

背景技术

在基于IEEE 802.11标准的无线网络中，节点的无线收发器使用工业科学医 疗无线频段即ISM频段，即Industrial，Scientific and Medical Band进行通信。由于 ISM频段是免执照即License-free的，因此，目前市场上出售的便携计算设备包括 便携电脑、智能手机、个人数字助理PDA即Personal Digital Assistant等，均配置 了Wi-fi接口即IEEE 802.11接口。

在无线网络中，由于无线信道的排它性，在任一时刻，如果网络中有多个节 点使用无线信道，就会相互产生干扰，导致数据包碰撞，造成节点之间无法传递 数据。鉴于此，IEEE 802.11标准引入了分布式协调功能DCF即Distributed Coordination Function，用于控制节点对信道的使用。DCF包含了二进制指数退 避算法BEB即Binary Exponential Backoff。

在本发明之前，相关的发明有：

2004年6月10日西安电子科技大学李建东等人申请了专利“无线局域网分布 式竞争控制退避方法”。该方法基于慢退避的思想，利用检测所得到的退避寄存器 的停止次数和初始化的退避时隙数得出时隙利用率的初始估计值，并对时隙利用 率的初始估计值进行平滑处理后，获得待发送数据帧的发送概率；再根据发送概率 自适应地调整节点的当前数据帧发送动作；最后，根据该数据帧是否发送或发送后 是否与其它节点的数据帧发生碰撞来选取发送后节点的竞争窗口，设置退避寄存 器的初始值，以确定节点再次发送数据帧的退避时隙数。

2007年9月18日，重庆邮电大学刘宴兵等人申请了“一种基于拥塞程度概率 P的无线竞争接入控制方法”，该方法基于节点执行退避基本思想，通过执行载波监 听机制，节点估计网络拥塞状态，根据信道忙的时隙数和退避过程经过的总时隙数 计算时隙利用率，并由此确定拥塞程度概率P，根据概率P值与节点随机数设置节点 的竞争窗口值，在节点每次发送成功后将以概率P判将竞争窗口是否变为最小值。 从而避免了不必要碰撞。信道发生碰撞时，将翻倍竞争窗口值直到达到最大值，并根 据竞争窗口确定退避计数器的值，以此控制网络数据的碰撞。

2007年12月5日，摩托罗拉公司伊萨姆.R.马赫卢夫等人申请了专利“在存在 周期性间歇干扰时保持无线通信性能的重传方案”，该发明可以建立缺省重传算法 和干扰重传算法。该缺省重传算法可以是在MAC层中实施的基于分布式协调功 能(DCF)的算法，该算法符合基于IEEE 802.11的标准。缺省传输算法的最小累积退 避时间可以小于干扰重传算法的最小累积退避时间。干扰重传算法的最小累积退 避时间可以大于PII的开启循环并且小于PII的开启和关闭循环的和(例如，对于微 波炉生成的PII，在～8.3MS和～16.7MS之间)。可以确定周期性间歇干扰是否存 在。如果这样，则可以自动地利用缺省重传算法用于无线数据传送。当存在PII时， 可以自动地利用干扰重传算法。

2010年11年19日，清华大学钟晓锋等人申请了“增强802.11分布式协调功 能性能的限制发送方法”。该专利提出一种增强802.11分布式协调功能性能的限 制发送方法，当网络站点数量大于预设值时，可根据网络站点数量动态调整限制概 率达到减小碰撞几率以增大站点接入概率，避免了基本接入机制的吞吐量开始下 降，平均分组时延急剧增加的缺陷，从而提升无线局域网802.11分布式协调功能的 性能。

2011年3月29日，华北电力大学唐良瑞等人申请了专利“基于网络负载预测 的无线竞争接入控制退避方法”。该方法基于站点执行退避思想，首先基于模糊理 论建立网络负载状况预测值与数据包发生碰撞可能性的隶属度函数；然后通过多 次数据发送时计算退避计数器冻结次数与初始值之比得到反映网络负载状况的参 数序列，并根据参数序列，利用数学预测方法得出下次数据发送时的网络负载状况 预测值；最后将预测值代入隶属度函数，得出时隙选择方案的控制参数，确定竞争窗 口范围。

之前，国内外学者对IEEE 802.11标准所提出的二进制指数退避算法的数学 建模方法，是利用意大利学者G.bianchi在2000年提出的二维马尔可夫链方法进 行建模，参考文献1：G.Bianchi，“Performance analysis of the IEEE 802.11 distributed coordination function，”IEEE Journal on Selected Areas in Communications，vol.18，no.3.pp.535-547，2000；即G.Bianchi，“IEEE 802.11分 布协调功能”，IEEE摘选通信领域期刊，第18卷，第3期，第535-547页，2000 年，以下称这种模型为Bianchi模型。G.Bianchi以时间t表示当前的时隙，引入 两个随机过程s(t)和b(t)分别表示节点当前所处于的退避阶段和所取得的退避值。 也就是说，以s(t)＝i表示节点处于第i个退避阶段，即节点的竞争窗口长度被扩大 了i次，i＝0，1，...，m，其中，m是加倍竞争窗口长度次数的最大值，满足L_m＝CW_max+1. 同时，b(t)＝j表示节点所取的退避值为j，j＝0，1，...，L_i-1.Bianchi模型的状态转移图 如图1所示。在图1中，p为节点发送数据包碰撞的概率；圆弧表示概率被几个 状态均等瓜分，例如，图1第一行(1-p)/L₀表示转到状态(0，0)，(0，1)，...，(0，L₀-1)的 概率均为(1-p)/L₀，其余类推。图中圆圈表示状态，圆圈内的数对(i，j)表示节点 处于状态s(t)＝i且b(t)＝j.以b_i，j表示在稳态时节点处于状态(i，j)的概率，利用状态 转移图1，G.Bianchi得出了^[2]：

且

$b_{0,0}=\frac{2(1-2p)(1-p)}{(1-2p)(L_0+1)+{\mathrm{pL}}_0(1-{\left(2p\right)}^m)}---\left(2\right)$

显然，在式(1)中取i＝0，可得：

其中

$a\≡(1-p)/L_0{\mathrm{\Σ}}_{j=0}^m{b}_{j,0}---\left(4\right)$

这样，依式(3)可得：

$b_{\mathrm{0,0}}>b_{\mathrm{0,1}}>b_{\mathrm{0,2}}>\mathrm{\Λ}>b_{0,L_0-1}.---\left(5\right)$

式(5)说明：当节点在第0退避阶段时，节点取小退避值的概率大于它取大退 避值的概率。类似地，在节点处于其它退避阶段i(i＝1，2，...，m)时，由式(3)同样 可以导出相同的结论。但是，IEEE 802.11标准的二进制退避算法规定：节点在每 一个退避阶段，同一个竞争窗口中的时隙总是被节点以相等的概率随机选取，也 就是说，在同一个退避阶段的退避值是被等概率选取的。由此可见，Bianchi模型 与IEEE 802.11标准的二进制退避算法不匹配。

发明内容

为了克服已有无线网络节点在通信时退避值不能被等概率选取、降低无线信 道的利用率、减少网络的吞吐量的不足，本发明提供一种使得通信时退避值被等 概率选取、增加无线信道的利用率、增加网络的吞吐量的IEEE 802.11无线网络 节点的竞争窗口平均长度的数学建模方法。

本发明解决其技术问题所采用的技术方案是：

一种IEEE 802.11无线网络节点的竞争窗口平均长度的数学建模方法，对于 网络节点所处的退避阶段i，将状态(i，0)，(i，1)，...，(i，L_i-1)合并为一个状态S_i，其 中，L_i是节点处于退避阶段i时的竞争窗口长度，符号(i，j)表示节点处于退避阶段 i且它的退避值是j，同时，称(i，0)，(i，1)，...，(i，L_i-1)为状态S_i的子状态，网络节 点在这些子状态的概率相等，以b_i，j表示节点处于退避阶段i且它的退避值是j的 概率，以Q_i表示网络节点处于状态S_i的概率，则

$Q_i\≡\mathrm{Pr}\left\{S_i\right\}={\mathrm{\Σ}}_{j=0}^{L_i-1}{b}_{i,j}---\left(6\right)$

b_i，j＝Q_i/L_i，i＝0，1，Λ，m，j＝0，1，Λ，L_i-1    (7)

其中，m是加倍竞争窗口长度次数的最大值；

以p为节点发送数据包碰撞的概率，以P{S_j|S_i}表示网络节点从状态S_i转移到状 态S_j的一步转移概率，所有状态转移情况概括为式(8).

式(8)的第一行表示网络节点在成功发送一个数据包之后成功接收到接收节点 的确认包，这时所述网络节点的竞争窗口长度被复位为初始值即恢复到退避状态 S₀，此时网络节点处于第0个退避阶段；式(8)的第二行表示网络节点发送数据包 失败，它需要重传数据包，从而导致它的竞争窗口长度被加倍，这时所述网络节 点从状态S_k转移到状态S_k+1，即从第k个退避阶段转移到第k+1个退避阶段；式 (8)的第三行反映了网络节点在竞争窗口长度已经为最大值即节点处于第m个退 避阶段的情况下，网络节点发送数据包再次失败，它需要重传数据包；

利用马尔可夫链的特性，得出以下方程组：

由式(9)，推导得到：

这样，由式(7)，得：

其中，i＝0，1，Λ，m.利用L_i＝2ⁱL₀，得到：

于是，由式(10)得到节点的平均竞争窗口长度：

$L_{\mathrm{avg}}\≡\underset{i=0}{\overset{m}{\mathrm{\Σ}}}{L}_i{Q}_i=L_0\underset{i=0}{\overset{m}{\mathrm{\Σ}}}{2}^i{Q}_i$

$=L_0\underset{i=0}{\overset{m-1}{\mathrm{\Σ}}}{2}^i(1-p)p^i+L_0{2}^m{p}^m---\left(13\right)$

上述式(12)的概率符合IEEE 802.11标准的二进制退避算法规定：所述网络节 点在每一个退避阶段，退避值总是被等概率选择。

本发明的技术构思为：在IEEE 802.11的二进制指数退避算法中，引入了“竞 争窗口”的概念。竞争窗口是分隔成多个时隙的一段时间，竞争窗口所包含的时隙 个数称为“竞争窗口长度”，其值为W+1，其中，W∈[CW_min，CW_max]称为竞争窗口 参数，在IEEE 802.11标准中窗口参数被初始化为CW_min^[1]。IEEE 802.11标准的 DCF规定：当一个节点有数据包要发送时，先监听信道，若信道连续空闲时间长 度达到分布式帧间隔DIFS即Distributed Inter-Frame Space，这个节点就发送数据 包，并等待接收方的确认数据包即ACK数据包。如果在规定的时间间隔内发送 节点未能收到接收节点的ACK包，发送节点就执行二进制指数退避算法：在集 合{0，1，...，W}中随机选择一个退避值k，并设置其退避时间为k个时隙。如果k＝0， 则这个节点立即发送数据包；否则，每隔一个时隙监听信道是否空闲。一旦监听 到信道空闲，退避值减去1；在退避值达到0时，这个节点就将数据包发送出去。 如果数据包发送不成功，即在数据包发送出去之后未能在事先约定的时间内收到 来自接收节点的ACK数据包，则发送节点的竞争窗口长度加倍，并重启上述二 进制指数退避算法。在W的值达到CW_max后，竞争窗口的长度不再加倍，但仍然 需要重复上述退避过程。一旦节点发送数据包成功，则W恢复到初始值CW_min。

从上述过程可以看出：初始时，竞争窗口参数为CW_min，含有CW_min+1个不 同的退避值0，1，...，CW_min，对应于CW_min+1个不同的时隙。以L₀表示初始竞争 窗口长度，则L₀＝CW_min+1；把节点在第1，2，...，m次加倍竞争窗口之后的竞争窗 口长度依次记为L₁，L₂，...，L_m，其中m是加倍竞争窗口长度次数的最大值，即 L_m＝CW_max+1.显然，L_i＝2ⁱL₀，i＝1，2，...，m.一般来说，竞争窗口参数的取值与物 理层PHY即Physical Layer有关，例如，对于FHSS即Frequency Hopping Spread Spectrum物理层，CW_min＝15且CW_max＝1023^[1]，这时竞争窗口长度的最小值与最 大值分别为16与1024，即L₀＝16，L_m＝1024；而对于IR即Infrared物理层，CW_min＝63且CW_max＝1023^[1]，这时竞争窗口长度的最小值L₀＝64，最大值L_m＝1024。换 言之，对于FHSS物理层，竞争窗口最大加倍次数m＝6，而对于IR物理层，m＝5.

节点在每次发送数据包之后，不管发送数据包是否成功，发送节点均需要利 用二进制指数退避算法设置竞争窗口长度，然后取一个退避值。因此，二进制指 数退避算法对信道的利用率、数据包传递时延、系统的吞吐率等指标有着重要的 影响。由于不同的节点的信道状况是不同的，其发送数据包碰撞的概率也不同， IEEE 802.11标准未能考虑这些状况，网络中所有节点每当数据包发送成功均将竞 争窗口参数复位为初始值CW_min，即竞争窗口长度复位为初始值CW_min+1，这会 降低网络的吞吐率等性能指标。因此，有必要对IEEE 802.11标准的二进制指数 退避算法进行建模与分析，得出节点的平均竞争窗口长度，进而确定最优的竞争 窗口长度复位值。此乃本发明的主要动机所在。

本发明主要针对IEEE 802.11标准所提出的二进制指数退避算法，运用马尔 可夫链，对它进行数学建模，得出节点在利用二进制指数退避算法接入无线信道 时，“节点所需扩大竞争窗口长度次数”和“节点所取得的退避值”这两个随机变量 的联合概率分布，并由此得出节点竞争窗口长度的平均值。然后，利用所求得的 指标对IEEE 802.11标准的二进制指数退避算法进行改进，使得节点在发送数据 包成功之后，可以将其竞争窗口长度复位到一个合理的值。

本发明主要针对IEEE 802.11标准的二进制指数退避算法，运用马尔可夫链 进行数学建模，得出在利用这种算法共享无线信道时，网络中节点扩大竞争窗口 长度的次数与所取得的退避值的联合概率分布，并由此得出节点的平均竞争窗口 长度、平均退避值等指标，使网络节点可以根据这个指标设置一个竞争窗口长度 的合理初始值。所提出的数学建模方法可以用于控制基于IEEE 802.11标准的无 线网络的节点对信道的竞争与共享，可以提高信道的利用率进而提高整个网络的 吞吐率；可广泛应用于内置IEEE 802.11接口的各种移动计算设备。

由于基于IEEE 802.11标准的无线网络使用免执照即License-free的工业科学 医疗频段ISM即Industrial，Scientific and Medical频段进行通信，目前，市场上出 售的包括便携电脑、智能手机等设备均配置了Wi-fi接口即IEEE 802.11接口，因 此，本发明有广阔的应用前景。

本发明的有益效果主要表现在：通信时退避值被等概率选取、增加无线信道 的利用率、增加网络的吞吐量。

附图说明

图1为意大利学者G.Bianchi的二维马尔可夫链状态转移图；

图2为本发明的一维马尔可夫链状态转移图。

具体实施方式

下面结合附图对本发明作进一步描述。

参照图2，一种IEEE 802.11无线网络节点的竞争窗口平均长度的数学建模方 法，对于节点所处的退避阶段i，本发明将状态(i，0)，(i，1)，...，(i，L_i-1)合并为一个 状态S_i，其中，L_i是节点处于退避阶段i时的竞争窗口长度，符号(i，j)表示节点处 于退避阶段i且它的退避值是j，同时，称(i，0)，(i，1)，...，(i，L_i-1)为状态S_i的子状 态，节点在这些子状态的概率相等。以b_i，j表示节点处于退避阶段i且它的退避值 是j的概率，以Q_i表示节点处于状态S_i的概率，则

$Q_i\≡\mathrm{Pr}\left\{S_i\right\}={\mathrm{\Σ}}_{j=0}^{L_i-1}{b}_{i,j}---\left(6\right)$

b_i，j＝Q_i/L_i，i＝0，1，Λ，m，j＝0，1，Λ，L_i-1    (7)

其中，m是加倍竞争窗口长度次数的最大值；

节点的状态转移图如图2所示，图中，方框表示状态S₀，S₁，...，S_m，方框内的圆 圈表示相应状态的子状态。以p为节点发送数据包碰撞的概率，以P{S_j|S_i}表示节 点从状态S_i转移到状态S_j的一步转移概率，则图2中所有状态转移情况可以概括 为式(8).

式(8)的第一行表示节点在成功发送一个数据包之后成功接收到接收节点的确 认包，这时这个节点的竞争窗口长度被复位为初始值即恢复到退避状态S₀，此时 节点处于第0个退避阶段；式(8)的第二行表示节点发送数据包失败，它需要重传 数据包，从而导致它的竞争窗口长度被加倍，这时这个节点从状态S_k转移到状态 S_k+1，即从第k个退避阶段转移到第k+1个退避阶段；式(8)的第三行反映了节点 在竞争窗口长度已经为最大值即节点处于第m个退避阶段的情况下，节点发送数 据包再次失败，它需要重传数据包，此时，因它的竞争窗口长度不再被加倍这一 情况。利用马尔可夫链的特性，从状态转移图2，可以得出以下方程组：

由式(9)，可以推得：

这样，由式(7)，得：

其中，i＝0，1，Λ，m.利用L_i＝2ⁱL₀，得到：

于是，由式(10)得到节点的平均竞争窗口长度

$L_{\mathrm{avg}}\≡\underset{i=0}{\overset{m}{\mathrm{\Σ}}}{L}_i{Q}_i=L_0\underset{i=0}{\overset{m}{\mathrm{\Σ}}}{2}^i{Q}_i$

$=L_0\underset{i=0}{\overset{m-1}{\mathrm{\Σ}}}{2}^i(1-p)p^i+L_0{2}^m{p}^m---\left(13\right)$

值得说明的是，式(12)的概率符合IEEE 802.11标准的二进制退避算法规定： 节点在每一个退避阶段，其退避值总是被等概率选择。

此处，以一个配置了IEEE 802.11无线网卡的便携计算机为例进行说明。通 过本发明数学建模方法所获得的IEEE 802.11标准的二进制退避算法的一些指标 将用于下述算法中，根据这个算法所编制的程序嵌入在便携计算机的无线网卡内。

在无线网卡中，设置两个内存变量TotalTransmissionNum和TotalFailNum， 分别用于统计所发送的数据包的总个数以及发送不成功的次数。

这台便携计算机在加入到IEEE 802.11网络之后，根据所使用的物理层，设 置其初始竞争窗口长度为L＝CW_min+1，并确定最大退避次数m，且m满足 2^mL＝CW_max+1。其中，CW_min和CW_max与具体的物理层密切相关：对于FHSS物理 层，取CW_min＝15，CW_max＝1023；对于DSSS物理层，取CW_min＝31，CW_max＝1023； 而对于IR物理层，取CW_min＝63，CW_max＝1023；对于OFDM即Orthogonal Frequency Division Multiplexing物理层，取CW_min＝15，CW_max＝1023^[1]。然后， 执行二进制指数退避算法：在集合{0，1，...，L-1}中随机选择一个退避值，并设置 其退避时间为k个时隙，即k*aSlotTime.此处，aSlotTime是一个时隙的时间长度， 它也是与物理层密切相关。对于FHSS物理层，取aSlotTime＝50微秒；对于DSSS 物理层，取aSlotTime＝20微秒；对于IR物理层，取aSlotTime＝8微秒；对于OFDM 物理层，取aSlotTime＝9，13或21微秒’，参照文献2：LAN MAN Standards Committee of the IEEE Computer Society，“IEEE 802.11 Standard-wireless LAN medium access control and physical layer specifications，”2007，即IEEE计算机学 会局域网城域网标准委员会，“IEEE 802.11标准--无线局域网络介质接入控 制与物理层规范”，2007年。

这台便携计算机在竞争无线信道时，遵守IEEE 802.11标准的分布式协调功 能DCF。它的无线网卡每发送一个数据包，均按以下算法进行：

步骤1.监听信道。如果信道连续空闲时间长度达到分布式帧间隔DIFS＝ aSIFSTime+2*aSlotTime^[1]，则把数据包发送到无线信道，置TotalTransmissionNum ＝TotalTransmissionNum+1，转到步骤3；否则，转到步骤2。其中，aSIFSTime表 示短帧间间隔SIFS即Short Inter-frame Space，它的取值与物理层紧密相关：对 于FHSS物理层，取aSIFSTime＝28微秒；对于DSSS物理层，取aSIFSTime＝10 微秒；对于IR物理层，取aSIFSTime＝10微秒；对于OFDM物理层，取 aSIFSTime＝16，32或者64微秒。

步骤2.每隔一个时隙即每隔aSlotTime时间监听信道，如果监听到信道空闲， 退避值减去1。

步骤3.如果退避值不为0，转到步骤2。把数据包发送到无线信道，置 TotalTransmissionNum＝TotalTransmissionNum+1。

步骤4.设置“确认定时器”的值为ACKTimeout，其中，ACKTimeout＝ aSIFSTime+aSlotTime+aPHY-RX-START-Delay。ACKTimeout值由物理层决定： 对于FHSS物理层，aSIFSTime，aSlotTime，aPHY-RX-START-Delay分别取28， 50，128微秒，这时ACKTimeout＝206微秒；对于DSSS物理层，aSIFSTime， aSlotTime，aPHY-RX-START-Delay分别取10，20，192微秒，这时ACKTimeout ＝222微秒；对于IR物理层，aSIFSTime，aSlotTime，aPHY-RX-START-Delay分 别取10，8，57微秒，这时ACKTimeout＝75微秒；对于OFDM物理层，aSIFSTime， aSlotTime，aPHY-RX-START-Delay可分别取16，9，25微秒，或者32，13，49 微秒，或者64，21，97微秒，这时ACKTimeout＝50，104，或者182微秒。如 果在“确认定时器”时间耗完之前，无线网卡收到ACK数据包，则转到步骤5；否 则，置TotalFailNum＝TotalFailNum+1，转到步骤6。

步骤5.计算概率p＝TotalTransmissionNum/TotalFailNum，按照式(13)计算平 均竞争窗口长度L_avg，按下式设置竞争窗口的复位值：

其中，表示不小于x的最大整数，如转到步骤8。

步骤6.如果L＜CW_max+1，则将其竞争窗口长度加倍，即设置L：＝2L.

步骤7.执行二进制指数退避算法：在集合{0，1，...，L-1}中随机选择一个新的 退避值k，设置其退避时间为k*aSlotTime.转到步骤1。

步骤8.结束。

上述算法可以用在基于IEEE 802.11标准的无线网络的接口卡控制程序中， 使其与其它节点共享并利用无线信道，且可以增加无线信道的利用率，增加网络 的吞吐率。由于当前绝大部分便携计算设备如便携电脑、智能手机、个人数字助 理等均配置了Wi-fi即IEEE 802.11接口卡，因此，本发明可以应用在这些设备， 以及其它支持IEEE 802.11标准的DCF的设备中。