9512.net

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

《计算机学报》2009 年 5 期

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

1) 2)

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

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

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

______________________

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

1

DIFS(Distributed Coordination Function Interframe Space)

BC值进行新一轮退避;若发送成功,则重设CW为 CWmin :

{

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

[3]

2

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 = 2i × CWmin (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 ) = (6)

j ∈ [0, 2i CWmin 1] 内,最大值为:
maxPrcr ( i ,i +1) (0) = 1 2 1 2 22i +1 CWmin (7)

maxPrcr ( i ,i +1) (2i CWmin 1) = (8)

2

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

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

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

CWi = CWi +1 = CWmax (9)

1) 2)

maxPrcr ( imax ,imax ) ( j ) = (2i CWmin j ) 2 (2i CWmin ) 2 (10)

2i CWmin j (11)

Prcr ( i , i +1) ( j ) ≤ Pr{BCi ∈ [ j , CWi 1]} × Pr{BCi +1 ∈ [0, CWi 1 j ]} (1)

k =0 i 1

DIFS DATA SIFS

(12)

3

Defer Access

ACK DIFS CW Backoff After Defer

3.2

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

Max _ Retrans _ Times , 节点将分组丢弃 ,
1

n [0, m 1] 上,可以得到分组冲突概率 Prm {冲突} 为:

[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,并据此设置其新

[CW0 + (CL 1) × EW , CW0 + CL × EW 1] , 从

ρ Sin =

k 2m n k + m 2m

(17)

ρ Int = ρi + ρ Sin =

(18)

PrDCF {成功发送} = Pr{在重叠区域成功发送}

×Pr{在独立区域成功发送}

=1 (m j ) (m j )!
2n + k (m j) 2m

(19)

[m j

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

×

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

[m + j

k (m + j )]! 2m

(20)

3.3

(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 )!

n nk (m 1) k Pr{k 个节点发生冲突} = mn
(a) n = 16

(23)

(c) n = 24 (b) n = 20

3.4

(d) n = 28
2

6

(a) k = 4

Pr{同级冲突} =

1 1 = sizeof (基本窗口) m

(24)

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)

(c) k = 12

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

7

4

4.1

SIFS DIFS Slot Interval Preamble Length Channel Bit Rate

CWmin CWmax CW0 EW Packet Size

2)

4.2

15]

,因此

8

4)

n

i =1 i =1 n

5)

[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

[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