9512.net
甜梦文库
当前位置:首页 >> >>

80211无线网络中的冲突顺序解析算法


《计算机学报》2009 年 5 期

IEEE 802.11 无线网络中的冲突顺序解析算法
张棋飞 1), 孙宝林 1), 桂 超 1), 刘 威 2), 程文青 2), 杨宗凯 2)
1) 2)

(湖北经济学院计算机学院 武汉 430205)

(华中科技大学电子与信息工程系 武汉 430074)

摘 要 对分布式的基于竞争的 MAC 协议中的分组冲突进行合理的分类对于有效进行冲突解析起着关键作用.本文根 据冲突节点所处退避阶段的不同将冲突划分为两类:交叉冲突和同级冲突,并且通过分析和实验证明了网络中的交叉 冲突是普遍存在的.传统的退避算法并未考虑这两种冲突的不同特点,而是采用同样的方式进行处理,对系统性能造 成了一定影响.我们认为,对于不同的冲突类型应该予以区别对待,因此提出了冲突顺序解析算法 CSR (Collision Sequential Resolution).CSR 根据冲突发生的顺序,将冲突节点依次分布在一系列连续独立的基本窗口上,通过竞争窗 口的离散化消除了交叉冲突;同时,通过选择合适的基本窗口大小在分组延迟和同级冲突概率之间取得折衷.仿真实验 表明,同传统的退避算法相比,CSR 能够在冲突次数、吞吐量、延迟以及公平性方面提供全面的性能提升. 关键词 IEEE 802.11; 媒体接入控制; 交叉冲突; 同级冲突; 冲突顺序解析 中图法 中图法分类号 TP393

Collision Sequential Resolution Algorithm in IEEE 802.11 Wireless Networks
ZHANG Qi-Fei1), SUN Bao-Lin1), GUI Chao1), LIU Wei2), CHENG Wen-Qing2), YANG Zong-Kai2)
2)

(School of Computing, Hubei University of Economics, Wuhan, 430205) (Dept. of Electronics and Information Engineering, Huazhong University of Science and Technology, Wuhan, 430074) Collision classification is crucial for collision resolution in distributed contention-based MAC protocols. Based

1)

Abstract

on backoff stages the collided nodes stay, this paper classifies collisions into two categories: cross collision and intra collision and then proves by analysis that cross collision is pervasive in networks, which is verified later by simulation results. Traditional backoff algorithms did not discriminate between these two collisions and treated them alike, which damages the system performance. We think, however, the two collisions should be dealt with different policies and thus propose a novel backoff algorithm featuring Collision Sequential Resolution (CSR) to address the problem. CSR redistributes the collided nodes in a series of consecutive separated elementary windows according to their occurrence sequence to eliminate cross collision completely. The intra collision is resolved with an appropriate elementary window size to achieve a tradeoff between delay and intra collision probability. We have performed extensive simulations for collision times, throughput, delay and fairness to demonstrate that our CSR provides comprehensive improvement compared with traditional backoff algorithms. Keywords IEEE 802.11; medium access control; cross collision; intra collision; collision sequential resolution

______________________
基金项目:国家自然科学基金(No.60572049, No.60602029),湖北省自然科学基金(No.2007ABA062)以及中国博士后科学基金(No.20070410955). 基金项目 作者简介:张棋飞,男,1977 年生,博士,讲师,主要研究方向为无线自组织网络和无线传感器网络.E-mail:cheffly@gmail.com.孙宝林 孙宝林,男,1963 年生, 作者简介:张棋飞 孙宝林 博士,教授,主要研究方向为高性能网络技术及无线通信网络.桂 超,男,1965 年生,副教授,主要研究方向为无线自组织网络和无线传感器网络. 桂 程文青,女,1965 年生,博士,教授,博士生导师,主要研究方 刘 威,男,1977 年生,博士,副教授,主要研究方向为无线自组织网络和认知无线电技术.程文青 程文青 向为无线传感器网络.杨宗凯 杨宗凯,男,1963 年生,博士,教授,博士生导师,主要研究方向为下一代互联网和无线自组织网络. 杨宗凯 作者联系电话:张棋飞 13260511070 作者联系电话

MIMD(Multiplicative Increase Multiplicative Decrease)[6] 中 , 窗 口 减 小 速 度 更 快 , 每 次 发 送 成 功 后 都 将 CW 减

1

引言

半.EIED(Exponential Increase Exponential Decrease)[7]采 用一种通用的算法,当发送成功后用 CW rD 更新 CW;若 失败则用 CW rI 代替 CW.MIMLD(Multiplicative Increase Multiplicative/Linear Decrease)[8] 额 外 使 用 了 一 个 参 数 CWbasic 作为区分网络竞争程度的标准.当 CW > CWbasic 时,认为竞争较激烈,成功发送报文后将发送窗口减半;否 则 , 线 性 递 减 CW.LMILD(Linear/Multiplicative Increase Linear Decrease)[9]将发送失败节点的 CW 值增大为原来 的 mc 倍,同时,监听到冲突的其他节点将 CW 增大 lc.报文 发送成功后,所有节点的 CW 值都线性减小. 以上算法都是在检测到分组成功发送后就认为信 道竞争状况缓解,从而立刻减小竞争窗口值.由于节点一 次发送成功的偶然性很大,因此若在此时就减小竞争窗 口 大 小 , 有 可 能 会 引 起 进 一 步 的 冲 突 .GDCF(Gentle DCF)[10]算法规定:只有当节点连续成功发送若干个报文 后才将竞争窗口值减小一半.这种保守的窗口变化方式 更加温和,也更容易反映信道的真实竞争状况,尤其在竞 争节点数较多的情况下,GDCF 能够显著降低节点的冲 突概率,获得比 DCF 更高的吞吐量和更多的公平性. 当前的冲突解析机制只是利用退避过程的随机性 来规避冲突,通过竞争窗口范围的不同获取不同的BC值, 以此实现冲突的解析.尽管竞争窗口的调整策略各不相 同,但这些算法仍然无法完全避免分组冲突的发生. 下面以典型的IEEE 802.11协议为例,说明传统退避 算法存在的问题.如图 1所示,处于退避阶段i的三个节点 a,b和c在其竞争窗口 [0, CWi 1] 上随机分布,选取的BC值 分别为j,j,k.由于a和b选取了在同一时隙进行分组发送,所 以在时刻j引发分组冲突 . 于是 ,a和b进入退避阶段 (i+1), 并且在新的竞争窗口 [0,2CWi 1] 上重新选择BC值,确定 各自的发送时隙分别为l和k(用a’和b’分别表示 ). 碰巧此 时节点b’选取的发送时隙k已被处于退避阶段i的c节点提 前占用.于是,在k时刻,处于退避阶段i的c节点和处于退避 阶段 (i + 1) 的b’节点同时发送分组,造成新的分组冲突.不 难看出 , 这次冲突是发生在两个处于不同退避阶段的节 点之间的.也就是说,即使节点已经进行过退避(如b’节点), 仍然不能保证分组的正常发送.

媒体接入控制(Medium Access Control, MAC)协议 是无线局域网(Wireless Local Area Networks, WLANs)的 基础,主要负责解析节点间的竞争冲突,协调系统资源分 配,对网络的性能起着决定性作用.由于WLAN的分布式 特性,分组冲突不可避免.MAC协议通常采用退避算法 (Backoff)进行冲突解析.退避的目的是协调节点的信道 接入,在冲突发生时能够及时有效地进行恢复.退避机制 决定了节点在发送报文之前需要推迟的时间,以便在多 节点竞争接入同一信道时保证接入的有效性,达到合理 利用信道资源的目的.退避算法既要尽量降低各节点间 的冲突概率,又要避免因退避时间过长而降低信道利用 率,同时还要保证各节点公平地访问信道.在分布式环境 中,这些要求对算法的设计提出了挑战. 现有的退避算法主要是基于竞争窗口(Contention Window, CW) 机 制 . 以 IEEE 802.11 协 议 的 BEB(Binary Exponential Backoff)[1]算法为例,每个节点维护一个本地 竞争窗口值CW.需要进行退避时,节点在 [0, CW 1] 范围 内随机选取一个数,称为退避计数器BC(Backoff Counter). 每当信道空闲一个时隙,BC值减1. 倘若信道由闲变忙, 退 避 进 程 暂 时 挂 起 ,BC 值 被 冻 结 , 直 到 信 道 持 续 空 闲
DIFS(Distributed Coordination Function Interframe Space)

后才开始继续递减BC 值 . 一旦 BC = 0 , 节点开始发送分 组 . 如果发送失败 , 节点加倍 CW 值直至 CWmax , 重新选择
BC值进行新一轮退避;若发送成功,则重设CW为 CWmin :

{

CWi = min(2i CWmin , CWmax ) 发生冲突 CW0 = CWmin 发送成功

其中,i代表节点所处的退避阶段[2],取决于节点自最近一 次成功发送以来所遭遇的冲突次数. BEB 算法虽然简单,但却存在一个弊端:由于节点在 发送成功以后立刻将竞争窗口值设为最小,使得该节点 有可能再次接入信道,从而阻塞其他节点,降低了公平性. 于 是 , 提 出 了 MILD(Multiplicative Increase and Linear Decrease)
[3]

算法.在 MILD 中,每当节点发送成功以后,竞

争窗口并不直接重设为最小值 CWmin ,而是递减 α ,直至 达到 CWmin .在每次分组发送失败后都将竞争窗口值增 大 β 倍( α 和 β 分别设为 1 和 1.5).MILD 采用了竞争窗 口拷贝机制,在提高公平性的同时也带来了额外的开销, 甚至会导致竞争窗口值迁移问题[4]. 基于竞争窗口机制的退避算法考虑的都是如何改 变竞争窗口的变化规则,以反映信道的当前竞争状况. SD(Slow CW Decrease)[5]算法在成功发送一个报文后将 节 点 的 竞 争 窗 口 减 小 为 原 来 的 δ 倍 (δ = 0.9) . 而 在

图 1 传统退避算法冲突解析示意图

2

这种由于退避效果不好产生的冲突不仅导致冲突解 析过程失败,更会对其他节点的正常发送造成干扰.如上 例中,由于节点b’的介入,使得本来应该成功发送的c节点 也发生冲突. 通过进一步的分析我们发现:在以上退避过程中,节 点b所经历的两次冲突性质是不一样的.第一次冲突发生 在两个处于同一退避阶段的节点之间,而第二次冲突则 是发生在两个处于不同退避阶段的节点之间.于是,我们 可以根据冲突节点所处退避阶段的不同将冲突划分成两 类:交叉冲突(Cross Collision)和同级冲突(Intra Collision). 所谓交叉冲突,是指产生冲突的节点处于不同的退避阶 段;而在同级冲突中,冲突节点都处于同一退避阶段.如图
1 中,a和b之间的冲突是同级冲突,而b’和c之间的冲突则

Pr{BCi ∈ [ j , CWi 1]} =

CWi 1 j + 1 CWi 1 + 1 CWi 1 j + 1 2CWi 1 + 1

(2)

Pr{BCi +1 ∈ [0, CWi 1 j ]} =

(3)

其中,竞争窗口大小 CWi 满足:
CWi = 2i × CWmin (4)

联立方程(1)~(4),得到:
Prcr ( i , i +1) ( j ) ≤ (CWi j ) 2 (2i CWmin j ) 2 = 2 2CWi 2 2 2i +1 CWmin (2i CWmin j ) 2 2 22i +1 CWmin (5)

显然,最大交叉冲突概率函数 maxPrcr ( i ,i +1) ( j ) 满足:
maxPrcr ( i , i +1) ( j ) = (6)

这 是 一 个 单 调 递 减 函 数 , 在 其 取 值 范 围
j ∈ [0, 2i CWmin 1] 内,最大值为:
maxPrcr ( i ,i +1) (0) = 1 2 1 2 22i +1 CWmin (7)

为交叉冲突. 我们认为,对冲突性质进行有效的区分对于完成冲 突解析具有重要意义.下面,我们将基于冲突划分标准对 IEEE 802.11无线网络中的冲突解析算法进行研究.我们 将在第二节中分析网络中交叉冲突发生概率的大小,从 而揭示其重要性;第三节根据冲突划分标准,提出冲突顺 序解析算法CSR (Collision Sequential Resolution);仿真结 果在第四节中给出,最后一部分对全文进行总结.

最小值为:
maxPrcr ( i ,i +1) (2i CWmin 1) = (8)

2

交叉冲突概率分析

IEEE 802.11 DCF 协议[11]规定:在每次发送失败后, 节点加倍自己的竞争窗口,重新选择 BC 值进行退避.假 定 节 点 当 前 处 于 退 避 阶 段 i, 竞 争 窗 口 大 小 为
CWi (0 ≤ i ≤ imax , CWmin ≤ CWi ≤ CWmax ) . 倘 若 在 第
图 2 两个连续退避阶段之间的最大交叉冲突概率

j (0 ≤ j ≤ CWi 1) 个时隙发生冲突 , 节点进入退避阶段

(i + 1) ,同时加倍自己的竞争窗口,如图 1 所示.退避阶段 (i + 1) 的竞争窗口为 [0,2CWi 1] , 图中的阴影部分表示

图 2 示出了在两个连续退避阶段 i 和(i+1)之间冲突 时隙与最大交叉冲突概率之间的关系.从图中容易看出: 冲突发生得越早,引发交叉冲突的概率越大. 尤其当退避阶段i达到其上限值 imax 时,有
CWi = CWi +1 = CWmax (9)

两个退避窗口的交集. 为了便于分析 , 我们首先只考虑两个连续的退避阶 段:i 和(i+1).在这两个连续的退避阶段之间发生交叉冲突 的必要条件满足:
1) 2)

处于退避阶段(i+1)的节点选取的 BC 值位于重 叠区域内,即 BCi +1 ∈ [0, CWi 1 j ] ; 在退避阶段 i,仍然有节点的 BC 值处于交集之 中,即 BCi ∈ [ j , CWi 1] .

此时,最大交叉冲突概率函数满足:
maxPrcr ( imax ,imax ) ( j ) = (2i CWmin j ) 2 (2i CWmin ) 2 (10)

由此可见,当满足条件:
2i CWmin j (11)

因此,在两个连续的退避阶段 i 和(i+1)之间发生交叉 冲突的概率 Prcr ( i , i +1) ( j ) 满足:
Prcr ( i , i +1) ( j ) ≤ Pr{BCi ∈ [ j , CWi 1]} × Pr{BCi +1 ∈ [0, CWi 1 j ]} (1)

交叉冲突概率甚至可以无穷逼近 1. 虽然我们推导了在两个连续退避阶段之间发生交叉 冲突概率的最大值, 但是应该强调的是:交叉冲突不仅仅 发生在两个连续的退避阶段之间. 只要节点的退避窗口 3

由于退避计数器值在竞争窗口上均匀分布,所以有:

存在着交集,就有可能引发交叉冲突.所以对当前处于某 一退避阶段 i 的节点来讲,它的交叉冲突概率应为: Prcr ( i ) ( j ) = ∑ Prcr ( k ,i ) ( j )
k =0 i 1

程中信道由闲变忙,则退避进程挂起,直到信道再次连续 空闲 DIFS 后继续递减计数器值.在收到发送方发来的数 据分组后,接收节点经过 SIFS(Short Interframe Space)后 回送一个确认分组 ACK(Acknowledgement).如果发送节 点没有及时收到 ACK,表明传输失败,于是增大竞争窗口, 重新选择退避计数器值进行新一轮退避.
DIFS DATA SIFS

(12)

显然,有 Prcr ( i ) ( j ) ≥ Prcr (i 1,i ) ( j ) 可见,交叉冲突是网络中的一类重要冲突. (13)

3

冲突顺序解析算法 CSR
Defer Access

ACK DIFS CW Backoff After Defer

传统的退避算法并没有区分交叉冲突和同级冲突, 而是采用同一种方式进行处理.特别地,IEEE 802.11 协议 通过单纯增加竞争窗口的大小来避免冲突.尽管该策略 可以有效解析同级冲突,但却引入了额外的空闲时隙,增 加了分组延迟.而且,由于退避算法的随机性,只要节点的 竞争窗口之间存在着交集,就有可能引发交叉冲突.尤其 当竞争窗口到达最大值 CWmax 后,交叉冲突的概率甚至 可以无穷逼近 1. 我们认为:对于这两种不同类型的冲突应该采取不 同的解析策略.同交叉冲突相比,同级冲突的解析策略比 较简单,仅仅通过扩大竞争窗口值就可以有效降低冲突 概率.然而,至今却还没有提出一个针对交叉冲突的有效 解决方案. 实际上,交叉冲突和同级冲突间存在着某种程度的 联系.交叉冲突的存在,不仅造成自身冲突解析过程的失 败,更有可能影响原本应该成功发送的节点,带来新的冲 突.可以试想,如果网络中没有交叉冲突,而是仅仅存在同 级冲突,则从概率的角度分析,也就意味着系统中发生过 的冲突都得到了良好解析.基于此,我们提出一个冲突顺 序解析算法 CSR.CSR 采用了一种冲突的顺序转化机制, 从解析交叉冲突入手,实现从交叉冲突到同级冲突的有 效转化,最终使得系统收敛到一个无冲突的状态.

图 3 IEEE 802.11 DCF 基本接入模式示意图

3.2

算法实现

我们从交叉冲突的定义中受到启发:节点只有处于 相互独立的竞争窗口中才能够完全消除重叠区域,从而 从根本上杜绝交叉冲突,使得网络中只有同级冲突存在, 实现了冲突的有效转化.CSR 算法就是基于以上思想而 提出.CSR 严格按照冲突发生的时间顺序为冲突节点动 态分配独立的竞争窗口,以此消除交叉冲突;同时,通过选 择适当的窗口值大小来减少同级冲突概率,保证分组延 迟.CSR 将节点的竞争窗口划分为一个初始竞争窗口
CW0 和 若干个 动态 分配的 基 本窗口 EW (Elementary

Window).系统初始化时,节点均匀分布在初始竞争窗口 上.一旦发生冲突,根据冲突发生的顺序,将冲突节点依次 分布在连续独立的基本窗口上,通过分布窗口的离散化 消除交叉冲突;同时设置合适的基本窗口大小,在同级冲 突概率和时延之间取得权衡. 为了消除交叉冲突,我们定义竞争级别(Contention Level, CL)为竞争区域上发生的信道接入次数,利用 CL 来指导基本窗口的动态分配.事实上, CL 可以看成是信 道竞争状态的一种表征. CSR 算法实现如下: 1) 所有节点监测信道.在信道连续空闲 DIFS 后, 如果再空闲一个时隙,节点将其退避计数器值 减 1.一旦计数器到达 0,节点马上发送分组.倘 若信道由闲变忙,退避进程挂起直到信道再次 空闲 DIFS 后继续递减退避计数器值. 2) 一旦监测到忙状态(不管是传输状态还是冲突 状态),表明信道上有分组发送,于是所有节点 都将 CL 值加 1: CL = CL + 1 侦测到忙状态 3) 节点完成数据分组发送后,如果在规定时间内

3.1

IEEE 802.11 DCF

我们基于 IEEE 802.11 DCF 协议实现 CSR 算法.图 3 是 DCF 基本接入模式示意图. 根据信道上是否有分组发送,DCF 将信道分为空闲 状态与忙状态,而忙状态可以根据分组发送的结果进一 步区分成传输状态和冲突状态.节点在发送数据之前首 先侦测信道状态.如果信道忙,节点从当前竞争窗口上随 机选取退避计数器值,以时隙为单位进行退避.只要信道 连续空闲 DIFS 后,每空闲一个时隙,节点递减计数器值. 一旦计数器递减到 0,节点开始发送数据.如果在退避过 4

没有收到接收方发来的确认信息,则认为发生 了分组冲突 ,于是检查其重传次数: 如果重传次数超过了最大门限值
Max _ Retrans _ Times , 节点将分组丢弃 ,
1

产生冲突.假定共有 n 个节点均匀分布在竞争窗口
n [0, m 1] 上,可以得到分组冲突概率 Prm {冲突} 为:

并且重设竞争窗口为 [0, CW0 1] ,同时保 留 CL 值以便继续指导后续的窗口分配; 如果没有超过重传门限,节点重新设置其 新的竞争窗口为:
[CW0 + (CL 1) × EW , CW0 + CL × EW 1]

n>m 1 n Prm {冲突} = m! 1 m n [m n]! n ≤ m
我们定义节点的分布密度 ρ 为:

(14)

ρ=

n m

(15)

ρ 于是得到分组发送成功的概率 Prm {成功} 满足:

这样,冲突节点将会在当前竞争窗口末端 的一个基本窗口上随机分布,从而实现了 退避空间的独立性,避免了交叉冲突.
4)

ρ >1 0 ρ Prm {成功} = m! m ρ m (m ρ m)! 0 < ρ ≤ 1

(16)

在一次成功的分组传输后(数据分组传输加上
ACK 传输),节点将 CL 值加 1,并据此设置其新

考虑一个典型的 IEEE 802.11 退避场景,如图 1 所示. 假定在退避阶段 i 共有 n (n < m) 个节点均匀分布在窗口 [0, m 1] 上.在第 j 个时隙,共有 k (k ∈ [2, min(n, 2m 2n)]) 个节点同时发送分组,产生冲突.于是这 k 个节点全部进 入退避阶段 (i + 1) 并且在新的竞争窗口 [0,2m 1] 上重新 分布.此时,对于处于退避阶段 (i + 1) 的节点来讲,其分布 密度不再是均匀的.新的竞争窗口也因此被分成两个区 域 : 重 叠 区 域 (Intersection Area) 以 及 独 立 区 域 (Single Area).这两个区域的分布密度分别为:

的竞争窗口为:
[CW0 + (CL 1) × EW , CW0 + CL × EW 1] , 从

而使得该节点完全独占第 CL 个基本窗口,保障 了其后续传输都是在无干扰的情况下进行 . 同 时, 由于这一系列基本窗口是连续排列的, 节点 需要经过一个周期的等待后才能够再次接入信 道, 从而为其他节点提供了接入机会, 保障了算 法的公平性. 图 4 描述了 CSR 算法.图中的虚线箭头表示节点的 重新分布.假设节点 1 和 2 同时发送数据,产生一次冲突. 此时, 网络中的 CL = 1 , 这两个节点在紧接初始竞争窗口 后的基本窗口 1 上重新分布.如果节点 3 发送成功,它设置 CL = 2 , 并将自己的分布范围设为紧接初始竞争窗口后 的第 2 个基本窗口.由于节点 3 独占了该窗口,保障了它的 后续传输都能够在无干扰的情况下进行.通过这种方式, 实现了退避窗口的不相交特性,完全消除了交叉冲突. 同 时, 算法使得发送成功的节点需要经过一轮的等待后才 能够再次接入信道,以此获得更多的公平性.

ρ Sin =

k 2m n k + m 2m

(17)

ρ Int = ρi + ρ Sin =

(18)

其中, ρi 是退避阶段 i 的原始分布密度, ρ Sin 和 ρ Int 分别代 表退避阶段 (i + 1) 在独立区域以及重叠区域上的分布密 度.因此,对 DCF 协议而言,在新窗口上成功发送分组的概 率满足:
PrDCF {成功发送} = Pr{在重叠区域成功发送}

×Pr{在独立区域成功发送}
函数 PrDCF ( j ) 满足: PrDCF ( j ) = 1 PrDCF {成功发送}
=1 (m j ) (m j )!
2n + k (m j) 2m

(19)

联立方程(16)~(19),我们得到 DCF 协议的冲突概率

[m j

2n + k ( m j )]! 2m

×
图 4 冲突顺序解析算法示意图

(m + j )! (m + j )
k (m + j) 2m

[m + j

k (m + j )]! 2m

(20)

3.3

冲突概率比较

对 CSR 算法而言,它将 k 个冲突节点均匀地分布在 一个完全独立的基本窗口上 ,避免了交叉冲突, 此时只有 同级冲突存在.假设 CW0 = EW = m 可以推出 CSR 算法的冲突概率函数 PrCSR ( j ) 为:

如果两个或多个节点选择在同一时隙发送分组 , 则

(21)

1

我们假设信道是无差错的,所有的分组丢失都由冲突造成

5

PrCSR ( j ) = 1 (m j )
×

(m j )!
(m j) n m

[m j

n (m j )]! m
(22)

m! mk (m k )!

我们固定窗口大小 m 以及冲突节点数 k,仅仅改变竞 争节点总数 n,得到两种退避算法的冲突概率比较结果如 图 5 所示.节点的增多势必加剧信道竞争,导致更高的冲 突概率.然而在活跃节点数目相同的条件下,CSR 算法的 冲突概率始终低于 DCF. 图 6 显示了冲突节点数目对冲突概率的影响规 律.CSR 算法避免了交叉冲突,网络中只有同级冲突存在. 在这种情况下,冲突节点数越多,发生同级冲突的概率也 就越大.所以同 DCF 协议相比,CSR 算法的冲突概率下降 相对缓慢.然而,k 个节点在同一时刻发生冲突的概率满 足:
n nk (m 1) k Pr{k 个节点发生冲突} = mn
(a) n = 16

(23)

图 7 给出了冲突发生概率与冲突节点数之间的关系. 可以看出,随着冲突节点数的增多,冲突发生概率急剧下 降并趋于 0.也就是说,多个节点同时发送分组导致冲突 的概率是很小的.根据实际推断原理[12]:概率很小的事件 在一次试验中实际上几乎是不发生的.因此我们完全可 以忽略在 CSR 算法中多节点同时冲突对系统性能造成 的影响. 在以上分析中,我们考虑的仅仅是一次状态转换过 程中冲突概率的变化.事实上,经过多轮退避后,CSR 算 法能够将节点依次顺序分布在时间轴上,通过竞争窗口 的离散化消除交叉冲突,同时保障成功节点的后续传输. 而 IEEE 802.11 DCF 却不得不面对接连不断的交叉冲突. 可以想象,在这种情况下,CSR 算法的冲突解析性能更 好.
(c) n = 24 (b) n = 20

3.4

基本窗口大小

一个合格的退避算法应该能够同时解析两种不同类 型的冲突.我们知道,CSR 算法消除了交叉冲突,网络中只 有同级冲突存在,并且在 CSR 的调度之下,同级冲突主要 发生在基本窗口上2.如果至少两个节点同时发送分组则 会引发冲突.考虑到方程(23):多个节点同时冲突的概率 可以忽略不计,因此此处我们仅仅考虑两个节点发生冲 突时的情况,于是得到同级冲突概率满足:
(d) n = 28
2

图 5 DCF 和 CSR 冲突概率比较.m=64,k=2,n 改变 发生在初始竞争窗口上的同级冲突相对来说很少,可以忽略

6

(a) k = 4

图 7 冲突节点数目对冲突发生概率的影响。m=64,k=20

Pr{同级冲突} =

1 1 = sizeof (基本窗口) m

(24)

此处 m 代表基本窗口大小.由此可见,基本窗口越大,发生 同级冲突的概率越小. 同时,空闲时隙的数学期望 E (TIdle ) 可以表示为:
E (TIdle ) = ∑ i × Pr{BC = i}
i =0 m 1

(b) k = 8

2 (m i ) m 1 1 2 m 1 = ∑i × 2 = 2 ∑ ( m i )i m m i =1 i=0

(25)

图 8 描述了空闲时隙的数学期望与基本窗口大小之 间的关系.它是一个单调递增函数,基本窗口越大,平均 空闲时间越长. 对比方程(24)和(25)我们知道,基本窗口的长度同时 控制着空闲时隙的开销以及同级冲突的概率,而二者又 是互相矛盾的,因此需要进行权衡, 选择一个合适的窗口 大小.

(c) k = 12

图 8 空闲时隙数学期望与基本窗口大小的关系

(d) k = 16 图 6 DCF 和 CSR 冲突概率比较.m=64,n=20,k 改变

7

4

性能评估

4.1

仿真模型

我们利用 ns-2[13]进行仿真实验,比较 CSR,GDCF 和 IEEE 802.11 DCF 协议的性能.仿真基于 DSSS 规范,实验 参数如表 1 所示.
表 1 实验参数 参 数 值 10 sec 50 sec 20 sec 144 bit 2 Mbps 参 数 值 32 2048 32 16 1024 Byte 图 9 平均冲突次数比较结果

SIFS DIFS Slot Interval Preamble Length Channel Bit Rate

CWmin CWmax CW0 EW Packet Size

2)

吞吐量

图 10 描述了算法的归一化吞吐量 [16] 比较结果.对 DCF 协议而言,冲突概率随着节点数目的增多逐渐增大, 最终造成吞吐量的下降.GDCF 则通过一种比较平缓的 方式改变节点的竞争窗口,更加客观地反映网络的当前 竞争状况,从而能够获得一定的性能提升.而 CSR 算法则 通过竞争窗口的离散化完全消除了网络中占主导地位的 交叉冲突,从而提高了分组成功发送的概率,增大了系统 吞吐量.

实验模拟 WLAN 环境,只设一个目的节点,即 AP.源 节点随机分布在一个100m × 100m 区域内,节点传输半径 为150m .系统具有饱和的流量,采用基于 CBR 的 UDP 数 据流进行通信.

4.2

结果和分析

由于分组传输失败对吞吐量和延迟有较大影响[14], 因此我们需要考察算法对分组冲突的解析能力,可以通 过衡量网络中的分组冲突次数得到体现.另外,吞吐量、 延 迟和公平性是考量退避算法性能的主要指标[4, 察了基本窗口尺寸对 CSR 算法性能的影响. 1) 平均冲突次数 我们定义平均冲突次数(Average Collision Times, ACT)为通信过程中单位时间内发生的分组冲突次数.实 际上,ACT 可以反映算法的冲突解析效率.我们改变网络 中的活跃节点数,记录分组冲突次数,结果如图 9 所示.随 着竞争节点数目的增加,信道竞争状况加剧,导致冲突次 数的增加.从图中可以看出,CSR 的冲突次数是三个算法 中最少的.这是因为 CSR 通过严格的分时策略完全消除 了交叉冲突,同时保障了成功节点的后续传输.可以想象, 在没有新节点加入的情况下,在 CSR 算法的调度下,系统 最终会收敛到一个稳定状态.此时,节点依次顺序接入信 道,网络中没有任何冲突发生.因此,图中 DCF 曲线和 CSR 曲线之间的差值就代表了网络中的交叉冲突次数.显然, 同同级冲突相比,网络中的交叉冲突更加普遍. 3)
图 10 归一化吞吐量比较结果
15]

,因此

拟从以上几个方面对三个算法进行综合评估.此外,还考

分组延迟

从图 11 可以看出,随着节点数目的增加,CSR 算法延 迟增加的幅度最小.DCF 频繁的冲突使得节点的空闲等 待时间增多,GDCF 则由于窗口变化方式比较保守,对分 组延迟也有一定影响.在 CSR 中,虽然竞争窗口以基本窗 口大小为步长逐步增加,但同时分组的冲突概率也大大 降低,因此可以获得更低的分组延迟.

8

有效减少同级冲突,因此随着基本窗口尺寸的增大,冲突 次数逐渐减小,如图 13 所示.由于 CSR 能够有效解析分组 冲突,因此就算采取最小的基本窗口大小 2,平均冲突次 数仍然在可以接受的范围内;同时,增大的窗口引入了更 多的分组延迟,且不同大小窗口引入的延迟相差较大(如 图 14 所示),所以在这种综合作用下,从图 15 中可以看出, 系统的吞吐量随着窗口的增大而减少. 因此,在应用 CSR 算法时,可以忽略不同基本窗口大 小带来的冲突次数差异,选取较小的基本窗口尺寸以获 得较小的分组延迟和较高的系统吞吐量.

图 11 分组延迟比较结果

4)

公平指数
n

公平指数(Fairness Index, FI) [17]定义如下: FI = (∑ Ti φi ) 2 n × ∑ (Ti φi ) 2
i =1 i =1 n

其中,n 表示数据流数目, Ti 代表流 i 的吞吐量, φi 是流 i 的权重(假设所有节点权重相同).显然 FI ≤ 1 ,且 FI 越趋 近于 1,公平性越好. 从图 12 中可以清楚看到:CSR 算法的公平性最好. 随 着 节 点 数 目 的 增 多 ,CSR 的 FI 曲 线 基 本 维 持 不 变,GDCF 和 DCF 的曲线均有一定跌落.这是由于在 CSR 算法的调度下,各竞争节点依次顺序接入信道,节点每次 发送后,不管发送成功与否,都需等待一轮周期过后才能 再次接入信道,从而为其他节点提供了接入机会,保障了 公平性.
图 13 基本窗口大小对 CSR 算法冲突次数的影响

图 14 基本窗口大小对 CSR 算法分组延迟的影响

图 12 公平性比较结果

5)

基本窗口大小对算法性能的影响

正如前面提到,基本窗口的大小对 CSR 算法的性能 有着重要影响,它同时决定着同级冲突的概率和分组延 迟的大小.我们选择 40 个节点进行实验,通过改变基本窗 口的大小观察协议性能的变化. 由于 CSR 中只存在同级冲突,而大的窗口范围能够 9
图 15 基本窗口大小对 CSR 算法吞吐量的影响

[7]

Nah-Oak Song, Byung-Jae Kwak, Jabin Song and Leonard E. Miller. Enhancement of ieee 802.11 distributed coordination function with exponential increase exponential decrease

5

结论

本文提出了分布式的基于竞争的 MAC 协议中的冲 突划分标准,根据冲突节点所处退避阶段的不同,将冲突 分为交叉冲突和同级冲突.随后,通过理论分析以及仿真 实验证明:网络中的交叉冲突是普遍存在的.传统的退避 算法并没有区分这两种不同类型的冲突,而是采用相同 的方式进行处理,对系统性能造成了一定影响.我们认为, 对于不同的冲突类型应该予以区别对待,因此提出了冲 突顺序解析算法 CSR.CSR 采用冲突顺序转化机制,根据 冲突发生的时间顺序为冲突节点动态分配独立的竞争窗 口,从而实现了退避空间的离散化,消除了交叉冲突,使得 系统中只有同级冲突存在,实现了从交叉冲突到同级冲 突的有效转化;同时,通过设置适合的基本窗口大小,在同 级冲突概率和分组延迟之间取得折衷.仿真实验表明,同 传统退避算法相比,CSR 算法在冲突次数,吞吐量,延迟以 及公平性方面均有较大提升.
[9] [8]

backoff algorithm//Proceedings of the IEEE VTC, Orlando, Florida, USA, 2003:2775-2778. Qixiang Pang, Soung C. Liew, Jack Y. B. Lee and Victor C. M. Leung. Performance evaluation of an adaptive backoff scheme for wlan. Wireless Communications and Mobile Computing, 2004,4:867-879. Jing Deng, Pramod K. Varshney and Zygmunt J. Haas. A new backoff algorithm for the ieee 802.11 distributed coordination function//Proceedings of the Communication Networks and Distributed Systems Modeling and Simulation, San Diego, USA, 2004. [10] Chonggang Wang, Bo Li and Lemin Li. A new collision resolution mechanism to enhance the performance of IEEE 802.11 dcf. IEEE Transactions on Vehicular Technology. 2004, 53(4):1235-1246. [11] LAN MAN Standards Committee of the IEEE Computer Society. Wireless lan medium access control (mac) and physical layer (phy) specifications. The Institute of Electrical


[1]







and Electronic Engineers, 1999. [12] Sheng Zhou, Xie Shi-Qian and Pan Cheng-Yi. Probability

Byung-Jae Kwak, Nah-Oak Song and Leonard E. Miller. Performance analysis of exponential backoff. IEEE/ACM Transactions on Networking, 2005,13(2):343-355.

theory and statistics. Beijing: High Education Press, 1989 (in Chinese). (盛骤, 谢式千, 潘承毅. 概率论与数理统计. 北京: 高等 教育出版社, 1989) [13] Kevin Fall, Kannan Varadhan. The ns manual. UC Berkeley, LBL, USC/ISI, and Xerox PARC, 2002. [14] Yongkang Xiao, Xiuming Shan and Yong Ren. Game theory models for ieee 802.11 dcf in wireless ad hoc networks. IEEE Radio Communications, 2005:S22-S26. [15] Yawen Barowski, Saad Biaz and Prathima Agrawal. Towards the performance analysis of ieee 802.11 in multi-hop ad-hoc networks//Proceedings of the IEEE WCNC, New Orleans, USA, 2005: 100-106. [16] Xue Yang and Nitin H. Vaidya. Explicit and implicit pipelining for wireless medium access control//Proceedings of the IEEE VTC, Orlando, Florida, USA, 2003: 1427-1431. [17] Raj Jain, Arjan Durresi and Gojko Babic. Throughput fairness index: an explanation. ATM Forum, 1999.

[2]

Giuseppe Bianchi. Performance analysis of the ieee 802.11 distributed coordination function. IEEE Journal on Selected Areas in Communications, 2000, 18(3):535-547.

[3]

Vaduvur Bharghavan, Alan Demers, Scott Shenker and Lixia Zhang. MACAW: a media access protocol for wireless LAN's//Proceedings of the ACM SIGCOMM, London, 1994:212-225.

[4]

Zygmunt J. Haas, Jing Deng. On optimizing the backoff interval for random access schemes. IEEE Transactions on Communications, 2003,51(12):2081-2090

[5]

Imad Aad, Qiang Ni, Chadi Barakat and Thierry Turletti. Enhancing ieee 802. 11 of mac the 4th in congested on

environments//Proceedings

Workshop

Applications and Services in Wireless Networks, Boston, USA, 2004: 82-91. [6] Haitao Wu, Shiduan Cheng, Yong Peng, Keping Long and Jian Ma. IEEE 802.11 distributed coordiation function (dcf): analysis and enhancement//Proceedings of the IEEE ICC, New York, USA, 2002: 605-609.

10

Background
This work is supported by the National Natural Science Foundation of China under grants No. 60572049 and No. 60602029; the NSF of Hubei Province of China under grant No. 2007ABA062 and the Postdoctoral Science Foundation of China under grant No. 20070410955. The IEEE 802.11 protocol has become the collisions into two categories and then proposes Collision Sequential Resolution to resolve the two collisions with different policies. The extensive simulation results show that our CSR algorithm consistently excels traditional MAC protocols in terms of collision times, throughput, delay and fairness. Moreover, the CSR algorithm can be realized based on the IEEE 802.11 DCF with no significant modifications required. It is a novel exploring for collision resolution in IEEE 802.11 wireless networks and can be used to resolve medium access problems in wireless ad hoc networks and sensor networks.

predominant technology for wireless local area networks, which can be a major reference to access mode research on wireless ad hoc networks. One of the key components of IEEE 802.11 is the Medium Access Control (MAC) protocol that primarily determines its performance. The work in this paper investigates collision resolution issues of IEEE 802.11 networks and then proposes a collision classification criterion. It classifies the

ZHANG Qi-Fei, born in 1977, Ph. D., lecturer. His main research

LIU Wei, born in 1977, Ph. D., associate professor. His main research interests include wireless ad hoc networks and cognitive radio networks.

interests include wireless ad hoc networks networks. and wireless sensor

CHENG Wen-Qing, born in 1965, Ph. D., professor and Ph. D. supervisor. Her main research interests include

SUN Bao-Lin, born in 1963, Ph. D., professor. His main research interests include high-performance computer networks and wireless

wireless sensor networks.

YANG Zong-Kai, born in 1963, Ph. D., professor and Ph. D. supervisor. His main research interests include NGI and wireless ad hoc networks.

communication networks.

GUI Chao, born in 1965, associate professor. His main research interests include wireless ad hoc networks and wireless sensor networks.

11


赞助商链接

更多相关文章:
无线网络安全及解决方案探讨
无线网络安全及解决方案探讨 摘要: 无线网络是通过...在 802.11a、80211.b 和 802.11g 中均有使用。...由于 RC4(1988RSA 运算法则)加密算法本身的缺点,使...
无线网络三层实验 三层
(算法、程序、步骤和 方法) AC 代码为: [V200R...80211bgn //当进行到这一步时,需要输入 Y 或 N...现无线局域网的配置,使得局域网内的无线终端可以通过...
11s mesh网络HWMP详解
11s mesh网络HWMP详解_IT/计算机_专业资料。11s mesh网络中的HWMP 混合无线路由算法解析,以及metric计算方法和mac80211中相应实现代码位置。...
无线网络设计与分析
本文在分析无线局域网 主流应用技术的演进历程,技术...现在已经有了 802.11,802.11a,80211b 802.11g ...沿用类似与以太网技术中的冲突检测的载 波监听多址...
无线网络25
无线局域网的安全漏洞和安全隐患问题进行了分析;...快速重置密钥 快速重置密钥使用IEEE80211X的周期性...初始化向量的 具体产生办法以减少初始化向量的冲突。...
无线网络二层实验
无线网络二层实验_计算机硬件及网络_IT/计算机_专业...(算法、程序、步骤和 方法) 配置思路 (1)配置接入...80211bgn wmm-profile name wmm-1 quit ap 0 ...
mac80211分析
openwrt mac80211 无线驱动分析 文档名称 文档密级 ...rc80211*(速率控制算法) ? rx.c(帧接收路径代码)...netif_receive_skb 网络。 ? 如果是管理帧/...
家庭无线局域网的组建与应用
基础结构网络:在基础结构网络中,具有无线接口卡的...网领域第一个在国际上被认可的协议一一 80211 协议...不需要手动设置 IP 地址,也避免出现 IP 地址冲突。...
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图