一种远距离分布式载波检测无线网络退避时隙长度优化方法

摘要

本发明公开了一种远距离分布式载波检测无线网络退避时隙长度优化方法。该方法首先确定节点间距离分布函数。然后采用二维离散马尔可夫链对远距离条件下分布式载波检测无线网络节点退避过程进行建模，根据非空一步状态转移概率得出分布式载波检测无线网络退避阶段的稳态概率分布，并利用稳态概率归一化条件求出节点的发送概率。进而根据网络节点在一个时隙中平均成功传输的数据比特数及时隙的平均长度，计算网络饱和吞吐量。最后通过数值搜索法确定不同网络规模条件下退避时隙长度的最优取值。无线网络仿真环境EXata中的仿真实验证明了该方法的有效性。

说明书

技术领域

本发明属于无线网络领域，特别涉及远距离分布式载波检测无线网络退避 时隙长度优化方法。

背景技术

随着无线局域网(Wireless Local Area Networks)的普及和应用，IEEE 802.11 标准受到人们的广泛关注。IEEE 802.11标准采用分布式接入功能(DCF)作为 媒质接入控制协议。DCF协议采用载波检测多路访问冲突避免(CSMA/CA)机 制和二进制指数退避(BEB)算法避免冲突。IEEE 802.11DCF协议最初被应用 于实现短距离接入的无线局域网，而近年来，该协议已被逐渐应用于一些远距 离组网的场景。例如，在地广人稀的贫困地区，IEEE 802.11DCF协议被用于 构建远距离无线通信网络，以低廉的成本解决远距离数据传输。

二进制指数退避算法(BEB)是保证分布式接入协议性能的关键。根据BEB 算法，节点发送数据包之前，首先监听信道持续空闲DIFS时长，然后在区间[0， W-1]内随机选择一个整数b(t)作为退避计数器初始值，并在b(t)δ的时间内继续 监听信道，其中W为当前退避窗口长度，δ为一个单位时隙长度。退避计数器 值减小到0，即退避定时器超时后，节点发送数据包。如果节点在退避时间内侦 听信道变忙，则节点保存当前退避计数器的剩余值，并在下一次重新侦听信道 持续空闲DIFS时长后，继续从该剩余值开始继续退避。如果节点发送数据包成 功，则节点保持当前退避窗口不变，而如果节点发送数据包失败，节点则把当 前W的值扩大一倍，并在重发数据包之前，在新的退避窗口中重新选择退避计 数器的初始值，W的取值范围为(CW_min，CW_max)。节点多次重传数据包失败，并 将该数据包丢弃后，节点将W的值设置为最小值。

在远距离条件下，研究DCF协议性能，提高网络饱和吞吐量具有重要意义。 由于BEB算法是DCF协议性能的关键，因而研究人员已针对BEB算法开展了 大量的研究工作。现有的研究工作都假定单位时隙长度δ的取值不小于节点的 最大传播时延，因而数据包冲突仅发生在多个节点在同一个时隙内完成退避的 条件下。只要多个节点不在同一个时隙完成退避，则不会发生冲突。然而，在 远距离的应用场景中，节点最大传播时延远大于短距离的应用场景(假定节点 最大传输距离为150公里，则最大传播时延为0.5毫秒)。如果仍然将单位时隙 长度δ的取值设置为不小于节点的最大传播时延，则退避等待将导致极大的开 销，严重影响网络总平均吞吐量。因此，寻找最优的退避时隙长度成为了提高 远距离分布式载波检测无线网络性能的关键问题，本发明的内容即围绕该问题 展开。

发明内容

本发明的目的是针对远距离分布式载波检测无线网络，提出一种退避时隙 长度优化方法，从而获得最大的网络饱和吞吐量性能。为了实现该目的，本发 明所采用的步骤是：

步骤1：确定节点之间距离的分布函数。

步骤2：采用离散马尔可夫链对远距离环境下网络中节点退避过程进行建 模，节点在离散马尔可夫链中的状态用二维随机变量{s(t)，b(t)}表示；其中，s(t) 表示节点退避阶段；b(t)表示节点当前退避计数器的剩余值；根据节点状态之间 的转移关系得出离散马尔可夫链非空一步状态转移概率。

步骤3：根据节点非空一步状态转移概率以及稳态概率分布归一化条件求出 节点发送概率及条件冲突概率。

步骤4：根据网络节点在一个时隙中平均成功传输的数据比特数及时隙的平 均长度，计算网络饱和吞吐量。

步骤5：利用数值搜索法求得网络饱和吞吐量最大时对应的最优时隙长度。

本发明提出的远距离分布式载波检测无线网络退避时隙长度优化方法已经 在EXata 3.1网络仿真环境中实现。节点在单跳传输范围内随机运动；网络中随 机建立10条业务流；信道带宽为256Kbit/s；网络层采用静态路由，传输层采用 UDP协议；仿真时间为300s。

附图3给出了本发明提出的退避过程的原理框图。附图4和附图5给出了 在10条业务流，节点传输范围分别为300km和800km情况下，通过改变退避 时隙长度得到的条件冲突概率和网络饱和吞吐量的仿真值与本发明得到的计算 值的对比。仿真值与计算值的一致性说明了本发明在不同网络条件下，确定退 避时隙长度最优取值方法的有效性。

附图说明

图1是节点分布示意图；

图2是二维马尔可夫链退避模型状态转移图；

图3是本发明提出的退避过程原理框图；

图4是条件冲突概率理论值与仿真值对比图；

图5是饱和吞吐量理论值与仿真值对比图；

具体实施方式

下面结合附图和实施例对本发明作进一步详细描述。

本发明提出的远距离分布式载波检测无线网络退避时隙长度优化方法已经 在无线网络仿真环境EXata 3.1中实现，并通过仿真结果证明了该方法的有效性。 下面给出本发明的具体实施步骤：

步骤1：确定节点之间距离的分布函数。

假设网络中各节点在单跳范围内随机分布，如附图1所示，圆O的半径R 为传输距离的一半，所有节点在圆O内随机分布。节点A、B是圆O内任意两 个节点，节点A、B到圆心O的距离分别记作a，b。节点A、B之间的距离为 d。OA与OB间夹角为θ。由余弦定理得

$d=\sqrt{a^2+b^2-2\mathrm{ab}\cos \theta }.---\left(1\right)$

任意两节点间距离的分布函数可以表示为

$\left(\begin{array}{c}{F}_d\left(d\right)=P\{D\le d\}=P\{\sqrt{a^2+b^2-2\mathrm{ab}\cos \theta }\le d\}\\ =\underset{\sqrt{a^2+b^2-2\mathrm{ab}\cos \theta }\le d}{\int \int \int }{f}_{\theta ,a,b}(\theta ,a,b)\mathrm{d\theta dadb}.\end{array}\right)---\left(2\right)$

由于变量a，b，θ是相互独立的，故式(2)可改写为

$F_d\left(d\right)=\underset{\sqrt{a^2+b^2-2\mathrm{ab}\cos \theta }\le d}{\int \int \int }{f}_{\theta }\left(\theta \right)f_a\left(a\right)f_b\left(b\right)\mathrm{d\theta dadb}.---\left(3\right)$

θ的概率密度函数为

$f_{\theta }\left(\theta \right)=\frac{1}{\pi }.---\left(4\right)$

a的分布函数为

$F_a\left(a\right)=P\{d\le a\}=\frac{\frac{4}{3}\pi a^2}{\frac{4}{3}\pi R^2}=\frac{a^2}{R^2},---\left(5\right)$

因此a的概率密度函数可以表示为

$f_a\left(a\right)=\frac{2a}{R^2}.---\left(6\right)$

同样，b的概率密度函数可以表示为

$f_b\left(b\right)=\frac{2b}{R^2}.---\left(7\right)$

式(2)中限定条件

$\sqrt{a^2+b^2-2\mathrm{ab}\cos \theta }\le d,---\left(8\right)$

可改写为

$\cos \theta \ge \frac{a^2+b^2-d^2}{2\mathrm{ab}}.---\left(9\right)$

我们用k表示式(3)中最内层θ积分的和

$k=\underset{\cos \theta \ge \frac{a^2+b^2-d^2}{2\mathrm{ab}}}{\int }{f}_{\theta }\left(\theta \right)\mathrm{d\theta }.---\left(10\right)$

式(10)可进一步推导为

$k=\left(\begin{array}{cc}0,& \frac{a^2+b^2-d^2}{2\mathrm{ab}}\ge 1\\ \frac{\arccos \frac{a^2+b^2-d^2}{2\mathrm{ab}}}{\pi },& -1<\frac{a^2+b^2-d^2}{2\mathrm{ab}}<1\\ 1.& \frac{a^2+b^2-d^2}{2\mathrm{ab}}\le -1\end{array}\right)---\left(11\right)$

由式(3)和式(11)可得任意两节点间距离分布函数为

$F_d\left(d\right)={\int }_0^R{\int }_0^{R}k{f}_a\left(a\right)f_b\left(b\right)\mathrm{dadb}.---\left(12\right)$

将式(6)，(7)，(11)代入式(12)中，可得到节点间距离分布函数F_d(d)的具体表达 式。

步骤2：采用离散马尔可夫链对远距离环境下网络节点退避过程进行建模。

假设在理想信道条件下，网络中有n个节点，每个节点都处在其他节点的 传输范围内。对于任意一个给定节点A，针对其退避过程，可构建如附图2所 示的二维离散马尔可夫链模型。m表示节点最大退避阶段，定义竞争窗口W＝W₀， 节点在i退避阶段的退避窗口值为

W_i＝min(2ⁱ(CW_min+1)-1，CW_max)i∈[0，m]         (13)

网络中节点的任一状态可用二维随机变量{s(t)，b(t)}表示。其中，s(t)表示节 点退避阶段；b(t)表示节点当前退避计数器的剩余值。用P(i|j)表示节点从状态j 转移到状态i的一步状态转移概率，则附图2所示的离散马尔可夫链非空一步状 态转移概率可以表示为：

$\left(\begin{array}{ccc}P\{i,j|i,j+1\}=1& i\in [0,m]& j\in [0,W_i-2]\\ P\{i,j|i,0\}=\frac{1-p}{W_0}& i\in [0,m]& j\in [0,W_0-1]\\ P\{i,j|i-\mathrm{1,0}\}=\frac{p}{W_i}& i\in [1,m]& j\in [0,W_i-1]\\ P\{0,j|m,0\}=\frac{1}{W_0}& j\in [0,W_0-1].& \end{array}\right)---\left(14\right)$

上述方程组中，第一个方程表示在每个时隙开始时，节点退避计数器值减小1。 第二个方程表示节点数据包成功传输后，进入退避阶段0，在区间[0，W₀-1]内随 机选择一个整数j作为退避计数器初始值；第三个方程表示当节点在第i-1个退 避阶段数据包传输失败后，节点进入第i个退避阶段，并在区间[0，W_i-1]内随机 选择一个整数j作为退避计数器初始值。第四个方程表示节点在m退避阶段发 送数据包后，无论数据包是否传输成功，节点进入0退避阶段，并在区间[0， W₀-1]内随机选择一个整数j作为退避计数器初始值。

步骤3：确定节点发送概率τ及条件冲突概率p。

用b_i，j表示马尔可夫链的稳态概率分布，即b_i，j＝lim_t→∞P{s(t)＝i，b(t)＝j}，i∈[0， m]，j∈[0，W_i-1]，由分析模型易得

b_i-1，0·p＝b_i，0→b_i，0＝pⁱb_0，0，i∈[1，m]         (15)

$b_{i,k}=\frac{W_i-k}{W_i}{b}_{i,0},i\in [0,m]k\in [0,W_i-1]---\left(16\right)$

由式(15)和(16)可知，对于节点所处的任意一个状态b_i，k都可表示为b_0，0和冲突概 率p的函数关系式，由归一化条件

$\underset{i=0}{\overset{m}{\Sigma }}\underset{k=0}{\overset{W_i-1}{\Sigma }}{b}_{i,k}=1---\left(17\right)$

可得

$b_{\mathrm{0,0}}=\frac{1-2p}{(1/2-2^m{p}^{m+1})(W+1)}---\left(18\right)$

某时刻节点X的退避计数器值为j的概率记作l_X，j，则

$l_{X,j}=\underset{i=\max (0,\mathrm{ceil}\left({\log }_2\frac{j+2}{W+1}\right))}{\overset{m}{\Sigma }}{b}_{i,j}---\left(19\right)$

其中cei1()表示对括号中数向上取整。

式(19)中，当j值取0时，l_X，0表示节点X在任意一个时隙发送数据包的概 率，记作τ。p表示条件冲突概率，其大小与网络中节点数量，节点间距离以及 时隙长度有关，其值可以表示为

p＝1-(1-ζ)^n-1           (20)

其中ζ表示任意一个其他节点与发送节点冲突的概率

$\xi =\underset{j=0}{\overset{W_m-1}{\Sigma }}{l}_{X,j}P(d\ge \mathrm{j\sigma c})=\underset{j=0}{\overset{W_m-1}{\Sigma }}{l}_{X,j}(1-F_d\left(\mathrm{j\sigma c}\right))---\left(21\right)$

根据式(19)，式(20)及式(21)可解得条件冲突概率p，将p值代入式(19)可计算 得到节点发送概率τ。

步骤4：确定分布式载波检测无线网络饱和吞吐量。

假设网络节点数量为n，网络饱和吞吐量S定义为单位时间内网络中节点成 功传输数据比特数

$S=\frac{\mathrm{n\tau }(1-p)E\left[P\right]}{E\left[\sigma \right]}---\left(22\right)$

在任一时隙网络中节点成功传输一个数据包概率为nτ(1-p)，包的平均长度为 E[P]，因此，在任一时隙，网络中节点平均成功传输的数据包比特数为 nτ(1-p)E[P]。E[σ]表示平均时隙长度。考虑到在任意一个时隙，对于一个给定节 点A可能处于以下任意一种状态：信道始终保持空闲；数据包成功传输引起的 信道变忙；给定节点A作为发送节点时与其他发送节点发生冲突引起的信道变 忙；给定节点A作为非发送节点时其他节点间发生冲突引起的信道变忙。因此， 平均时隙长度E[σ]可以表示为

E[σ]＝(1-P_tr)δ+nτ(1-p)T_s+(P_tr-P_trP_s)(τpT_c1+(1-τp)T_c2)       (23)

其中

δ表示信道空闲时节点的时隙长度，

P_tr＝1-(1-τ)ⁿ             (24)

表示在任意一个时隙，至少有一个节点传输数据包的概率，

$P_s=\frac{\mathrm{n\tau }(1-p)}{1-{(1-\tau )}^n}---\left(25\right)$

表示在至少有一个节点传输数据包的条件下，数据包能够成功被接收的概率，

T_s＝E[P]+2×PLCP+SIFS+DIFS+ACK+2×E[t_d]        (26)

为节点成功传输一个数据包所花费的时间，E[t_d]为平均传播时延，

T_c1＝E[P]+PLCP+ACKTimeout+DIFS         (27)

为给定节点A作为发送节点时与其他发送节点发生冲突的情况下，A检测到的 冲突持续时间，

T_c2＝E[P]+PLCP+DIFS        (28)

为给定节点A作为非发送节点时其他节点间发生冲突的情况下，A检测到的冲 突持续时间。

因此，网络饱和吞吐量S可以表示为

$S=\frac{\mathrm{n\tau }(1-p)E\left[P\right]}{(1-P_{\mathrm{tr}})\delta +\mathrm{n\tau }(1-p)T_s+(P_{\mathrm{tr}}-P_{\mathrm{tr}}{P}_s)(\mathrm{\tau p}{T}_{c1}+(1-\mathrm{\tau p})T_{c2})}.---\left(29\right)$

步骤5：确定分布式载波检测无线网络退避时隙长度的最优取值。

根据步骤4中确定的网络饱和吞吐量S，本发明通过数值搜索法确定给定网 络规模条件下分布式网络时隙长度的最优取值。具体方法为：将分布式网络时 隙长度的取值从最小值1开始递增，依次分别计算出相应的网络饱和吞吐量S(δ) 的值，δ＝1，2，3......。若S(δ)的取值满足

S(δ+1)-S(δ)＜0          (30)

则δ即为当前网络规模条件下分布式网络时隙长度的最优取值。

本发明申请书中未作详细描述的内容属于本领域专业技术人员公知的现有 技术。