nbhkdz.com冰点文库

Analysis of An AIMD Based Collision Avoidance Protocol in Wireless Data Networks

Songlin Cai

Department of Electrical & Computer Engineering University of Massachusetts Amherst, MA 01003 Email: scai@ecs.umass.edu

Yong Liu

Department of Computer Science University of Massachusetts Amherst, MA 01003 Email: yongliu@cs.umass.edu

Weibo Gong

Department of Electrical & Computer Engineering University of Massachusetts Amherst, MA 01003 Email: gong@ecs.umass.edu

Abstract— Wireless networks have been deployed widely in recent years. The performance features such as fairness and ef?ciency of MAC protocols would affect that in upper layer. We propose two modi?cations to a MAC protocol proposed in [14], so that the new protocol could achieve AIMD on controlling each station’s throughput directly. We use stochastic linear difference equation to study the throughput of this protocol and we present a guideline for selecting additive and multiplicative parameters.

I. I NTRODUCTION Wireless ad hoc networks have the advantage that no ?xed communication infrastructure is needed. In recent years, wireless networks have been widely deployed. The communication between the stations in wireless networks relies on Medium Access Control (MAC) protocol. All stations in a wireless network have to compete for scarce resource such as the communication channels. Resolving this competition is critical to ensure the communication in the wireless networks. IEEE 802.11 de?nes a standard for MAC protocol. The intuition behind this protocol is that if there is a collision, the sender will decrease its sending rate; if there is a success, the sender will increase its sending rate. To achieve this goal, IEEE 802.11 introduces a carrier sense multiple access with collision avoidance mechanism (usually known as CSMA/CA). CSMA/CA uses a backoff timer CW to adjust the throughput of each node. The backoff timer starts with CWmin . The station will double CW upon collision until it reaches CWmax . If there is a success, the station will set CW to CWmin . There has been studies for interaction between MAC layer protocol and upper layer protocol. For example, [15] points out that without fairness in the MAC layer, the fairness mechanism in upper layer such as TCP would not be very effective. A lot of research has been

devoted to studying how to improve the MAC protocol [3] [12] [13]. For example, in order to achieve fairness, [3] introduces additional ?eld in the data packet to propagate the value of backoff timer so that the stations in the same region would share the same backoff timer. A Multiplicative Increase and Linear Decrease backoff algorithm is also introduced: the station increases its backoff timer by a multiplicative factor 1.5 upon collision, and decreases the timer by 1 upon success. In [13], the authors propose another backoff timer mechanism to address the fairness problem. They de?ne a fairness index. Each station has an estimation of its fairness over all the other stations. If the ratio of fairness is larger than a high threshold, the window size would double; if the ratio is below a low threshold, the window size would decrease by a half. If the ratio is in between these two thresholds, the window size will remain unchanged. It has been increasingly realized that modi?cation of MAC protocol is necessary to improve its performance. Additive Increase Multiplicative Decrease (AIMD) is implemented in network Transport layer to control the sending rates of competing sources. It has been shown in [7] that it ensures fairness and ef?ciency in a distributed environment. It looks promising to apply AIMD to control the sending rate in MAC protocol directly. In this paper, we analyze a protocol which uses AIMD to control each station’s throughput. The purpose of this paper is to provide some insights into the MAC protocol using AIMD. In section II, we present the protocol from [14]. We modify this protocol so that the new protocol would use AIMD to control the station’s throughput directly. In section III, we study the protocol by using stochastic linear difference equation [4] [9] and present a

guideline for the selection of additive and multiplicative parameters in AIMD mechanism. Finally we conclude this paper in section IV. II. A MAC P ROTOCOL WITH AIMD: CSMA/CA2 In [14], the authors present a MAC protocol which uses AIMD mechanism to control station’s throughput. The protocol is based on CSMA/CA, and is called CSMA/CA2. Fig. 1 is a diagram of CSMA/CA. If a station wants to send its data, it would ?rst sense whether the channel is free or not. If the channel is busy, the backoff timer would freeze. If the channel is free, the backoff timer would count down. Once the backoff timer reaches zero, the station sends its data, and after a short interval (SIFS), an ACK from the receiver is expected if the transmission is successful. The sender changes its backoff timer according to whether it gets the ACK or not. A. CSMA/CA2 vs CSMA/CA The backoff timer in CSMA/CA is used to avoid collision. However, the nondeterministic status of the channel would make the regulation of ef?ciency and fairness dif?cult. In order to separate contention resolution from collision avoidance, CSMA/CA2 [14] introduces gapping to control the throughput. Fig. 2 shows how CSMA/CA2 works. Before each data transmission, there is a gapping. CSMA/CA2 controls the throughput by adjusting the length of the gapping. The difference between CSMA/CA2 and CSMA/CA lies in the following two factors [14]: (1)CSMA/CA uses timer with binary exponential backoff mechanism to control the sending rate. CSMA/CA2 uses gapping to control the throughput. The progress of the gapping interval duration would not be suspended when the channel is busy, while the backoff timer in CSMA/CA would freeze when channel is busy. (2) In CSMA/CA2, the gapping is followed by an ideal CSMA/CA process, therefore, if the gapping ends at the middle of other station’s transmission, the station would do the carrier sensing to avoid the collision. In Fig. 2, the backoff timer in the ideal CSMA/CA process uses a small ?xed contention window size CW to avoid synchronization between senders. B. Additive CSMA/CA2 Increase Multiplicative Decrease in

DIFS Backoff DATA

SIFS ACK

Fig. 1.

CSMA/CA MAC Protocol

Gapping

Gapping

Station i

IDEAL CSMA/CA

IDEAL CSMA/CA

Fig. 2.

Simpli?ed Diagram of CSMA/CA2 MAC Protocol

Ri (tn ) to be the normalized throughput of station i during its n-th transmission starting at tn . CSMA/CA2 calculates the normalized sending rate as follows: Ri (tn ) = Bi (tn ) , Bi (tn ) + Gi (tn )

(1)

and applies AIMD to the normalized sending rate in the following way: ? When at time tn+1 , the station senses that transmission is successful, it increases the sending rate Ri (tn ) by a constant αi , i.e

Ri (tn+1 ) = Ri (tn ) + αi

?

When at time tn+1 , the station senses that transmission fails, it sets the new sending rate to be (1 ? βi ) of Ri (tn ), therefore,

Ri (tn+1 ) = Ri (tn )(1 ? βi )

C. CSMA/CA2+: Modi?cation to CSMA/CA2 In this paper, we propose to modify CSMA/CA2 in two aspects: (1) we rede?ne the normalized sending rate so that it would re?ect the instant throughput; (2) we point out unfairness in CSMA/CA2 and apply AIMD to rate control in a way different from CSMA/CA2. We use CSMA/CA2+ to represent this updated protocol. 1) Rede?ne Sending Rate: We rede?ne the sending rate Ri (tn ) to re?ect the real throughput. In Fig. 3, the duration of one transmission of station i consists of a gapping, carrier sensing period, data transmission from station i, and data transmission from other station during backoff timer countdown of station i. Since CSMA/CA2 preserves a backoff timer with a small ?xed window size CW, other stations’ timer might count down to zero before station i’s timer, therefore, before station i sends 2

CSMA/CA2 de?nes Bi (tn ) to be the sum of DIFS, backoff Timer countdown, data packet, SIFS and ACK packet, Gi (tn ) to be the length of gapping interval,

Gi Carrier Sense Station i Gapping t1 t2 DIFS Timer t3 Carrier Sense

Li

DIFS t4

Timer t5

Data Transmission

Station j

Gapping

DIFS

Timer

Data Transmission

Gapping

Station k

Data Transmission

Gapping

Fig. 3.

One Transmission from Station i in CSMA/CA2

its data, there could be data transmission from stations other than station i. Fig 3 shows one transmission from station i. It consists of the following events: (1)At time t1 , station i’s gapping ends. At that time, station k is sending data, therefore, station i has to wait. (2) At time t2 , station j ’s gapping ends. Also because station k is sending data, station k waits. (3)After station k ?nishes its transmission, station i and j both start backoff timer countdown. (4) The timer of station j reaches zero earlier than that of station i. So station j sends its data. At the same, station i has its timer frozen. (5)After station j ?nishes its transmission, the timer of station i starts to count down and reaches zero. Station i sends its data. Fig 3 shows that the duration of one transmission of station i not only includes the gapping, the transmission from station i, but also includes the transmission from other stations. This is due to two reasons: (1)The gapping ends in the middle of other station’s transmission; (2)Other station’s timer reaches zero earlier than station i. The normalized sending rate de?ned in equation (1) does not include the time of the transmission from other stations, therefore it does not re?ect the actual throughput. We rede?ne Ri as follows:

Ri (tn ) = Bi (tn ) . Li (tn )

the same AIMD parameters (α and β ) start at different sending rates. It might lead to unfair scenario that one station occupies the whole channel, while the other starves for it. We study the sending rate of two stations at two consecutive collisions. We de?ne R1,1 , R2,1 to represent the sending rates of two stations after ?rst collision, use R2,1 , R2,2 to represent the sending rates after second collision time. We assume during these two collisions, the sending rates of these two stations vary little. We de?ne T the time between this two consecutive collisions, then statistically station 1 would have T ? R1,1 /(R1,1 + R2,1 ) transmissions, while station 2 would have T ? R2,1 /(R1,1 + R2,1 ) transmissions. To simplify the notation, we use k to represent T /(R1,1 + R2,1 ). Then, the transmissions from one station consists of k ? R1,1 ? 1 successes and 1 collision, while the other consists of k ? R2,1 ? 1 successes and 1 collision, then,

R1,2 ? (R1,1 + (kR1,1 ? 1) ? α) ? (1 ? β) R2,2 ? (R2,1 + (kR2,1 ? 1) ? α) ? (1 ? β)

Therefore we have

R1,1 [1 + kα ? R1,2 = R2,2 R2,1 [1 + kα ?

α R1,1 ] α R2,1 ]

(2)

Li (tn ) is the duration of n-th transmission of station i, which includes the gapping Gi , the data transmission Wi from stations other than station i, the data transmission Bi from station i, i.e, Li (tn ) = Gi (tn ) + Wi (tn ) + Bi (tn )

R1,2 If R1,1 > R2,1 , then R2,2 > R1,1 . This means if the R2,1 stations start at different sending rate, CSMA/CA2 would favor the station with higher sending rate. 3) CSMA/CA2+: Updated Algorithm for CSMA/CA2: We use AIMD to control the station’s throughput in equation (2) directly: each station keeps increasing its sending rate by a constant rate αi unless there is a collision; if there is a collision, the sending rate would decrease by a multiplicative factor βi . One diagram of this mechanism is shown in Fig 4. ? If the n-th transmission of station i is successful, the sending rate for n + 1-th transmission will be:

Ri (tn+1 ) = Ri (tn ) + αi ? (tn+1 ? tn ).

?

(4)

If there is a collision during n-th transmission, the sending rate for n + 1-th transmission will be:

Ri (tn+1 ) = (Ri (tn )+αi ?(tn+1 ?tn ))?(1?βi ). (5)

(3)

Now we have the instant throughput Ri (tn ). We will use AIMD to control this instant throughput directly. 2) Fairness Issue: We point out in this section that fairness in CSMA/CA2 needs improvement. The AIMD scheme de?ned in CSMA/CA2 would not be able to ensure the fairness when two competing stations with 3

With Ri (tn+1 ) calculated from equation (4) and (5), packet size Bi (tn+1 ), estimated Wi (tn+1 ) and equation (3), we would be able to change the gapping interval Gi (tn+1 ) at tn+1 as follows

Gi (tn+1 ) = Li (tn+1 ) ? Wi (tn+1 ) ? Bi (tn+1 ),

B Sender i

B

B

Collision Successful

? R(t n + 2 )

α ? (t n+ 2 ? t n+1 )

R (t n +1 )

? β ? R(t n + 2 )

of β . Let Ri,n represent the sending rate prior to n-th collision of station i. Let {Ti,n }+∞ n=?∞ be a particular realization of the collision process for station i, and interval of the collision Si,n = Ti,n+1 ? Ti,n . The dynamic behavior of the sending rate could be modelled by the following linear difference equation,

Ri,n+1 = (1 ? β) ? Ri,n + α ? Si,n

α ? (t n +1 ? t n )

R(t n + 2 ) R(t n ) t n +1 ? t n

(6)

Because 1 ? β < 1, E[Si,n ] < ∞ and we assume the arrival of collision is stationary, according to the result from [1] [4] [9], for arbitrary sending rate Ri,n , it will converge almost sure to the stationary solution:

∞ ? Ri,n

Fig. 4.

Diagram of MAC protocol

=α

k=0

(1 ? β)k Si,n?1?k .

where Li (tn+1 ) can be calculated from equation (2), and make the throughput work in AIMD mode. If the calculated gaping Gi (t) is less than zero, Gi (t) would be set to zero. Note that Wi (t) might vary a lot for different transmissions, we introduce an estimation of Wi (tn+1 ) by

W i (tn+1 ) = δ ? W i (tn ) + (1 ? δ) ? Wi (tn ),

Now we de?ne λi to be the collision rate for station i, then λi = 1/E[Si,n ]. We turn to calculate E[Ri (t)], by using the inversion formula as follows [2],

E[Ri (t)] = λi E 0 [

Ti,1 0

Ri (t)dt]

(7)

We have

E[Ri (t)] = λi E 0 [

0 Ti,1 0 ? ((1 ? β)Ri,n + αt)dt]

where δ is the parameter to average W i (t), and 0 < δ < 1. We let δ to be 0.9 in our study. III. M ODEL OF CSMA/CA2+ In the following study, we assume all the stations are within the communication range of other stations in the wireless network, and we do not consider the hidden/exposed terminal problem. We focus on studying a homogenous system with the same parameters: α, β and data packet size B . We use m to denote the total number of stations. We assume all m stations are active all the time, i.e, they keep sending data. In this section, we use stochastic linear difference equation to study the expectation of the throughput. After that, we present a guideline for selecting the parameters of additive and multiplicative factor of AIMD. Finally, we present the simulation result and discussion. A. Stochastic CSMA/CA2+ Linear Difference Equation for

? = λi E [(1 ? β)Ri,n Si,0 + ∞

α 2 S ] 2 i,0

λi α 2 E[Si,0 ] 2 k=0 (8) Now we assume the collision process for station i is a Poisson process with arrival rate λi . For Poisson process, 2 we have E[Si,0 ] = 2/λ2 and E[Sk ] = 1/λi therefore i = λi α (1 ? β)k+1 E[Si,0 Si,k+1 ] +

∞

E[Ri (t)] = λi α

k=0

(1 ? β)k+1

1 λi α 2 α + = 2 λ2 λi β λ2 i i (9)

Stochastic Linear Difference Equation has been used to model TCP/IP behavior [1]. In this subsection, we use the stochastic linear difference equation to study CSMA/CA2+. The sending rate Ri (t) of station i keeps increasing by rate α unless there is a collision. If there is a collision, the sending rate would decrease by a multiplicative factor 4

The same result could be derived from Poisson driven stochastic differential equation [5] [11]. For a wireless system, when the channel capacity, time slot, packet size are ?xed, the station’s sending rate Ri (t) and the goodput η of the channel are determined by α and β . We simulate CSMA/CA2+ with the parameters from Table II. In our simulation, we ?x β to be 0.1, and study the throughput when α changes. Fig 5 shows the average throughput and goodput of each station when α changes. Note that in Fig 5, for different number of stations, the range of α varies. To achieve certain performance, different numbers of competing stations would need different α. In the next section, we provide a heuristic method to infer parameter α for CSMA/CA2+.

B. Selection of α and β The sending rate Ri (t) would increase with a ?xed rate α when there is no collision. The α which ?ts for small number of stations might not be suitable for large number of stations. For example, large number of stations would have long period for one transmission, then the increased part of the sending rate would be very large so that the calculated gapping would be negative and the real gapping has to be set to zero. In this case, AIMD mechanism is not in effect. Therefore, we need to adjust α for different number of competing stations. On the other hand, the multiplicative factor would decrease the sending rate and increase gapping. This part will always play role as long as there is a collision, no matter how many stations there are. In the following study, we ?x β to be 0.1. For a homogeneous system with goodput η of the channel, we can approximate the expectation of collision for a transmission of station i as η . (10) 1? m j=1 Rj Dividing expectation of collision by the duration Li (t) of one transmission in equation (2), we can approximate the collision rate λi during steady state as follows:

(1 ? λi =

TABLE I IEEE 802.11 MAC P ROTOCOL C APACITY (AVERAGE PACKET S IZE 100 SLOTS ) m 100 50 10 Capacity 0.33392 0.4658 0.71355

TABLE II PARAMETERS Channel capacity Time slot Packet size β 2Mbps 25?s 2.5 ms 0.1

(11) B Substitute equation (11) into equation (9), we have

β(1 ? α=

m j=1

η E[Rj (t)] )E[Ri (t)]

(12) B Now we focus on studying how to select parameter α. To achieve certain performance, we need to choose a suitable α for different numbers of stations. We give a heuristic way to select α: (1) set η to the expected goodput of the whole channel, (2) assume the system is a little bit over the channel capacity, and set m E[Rj (t)] to j=1 be a constant larger than 1, (3) assume each station in this homogeneous system has the same throughput. We would be able to get an estimation of α from equation (12), when packet size B and β are given. With all the other parameters in Table II, we set m j=1 E[Rj (t)] equal to 1.2 and get an estimation of α to achieve the capacity in 802.11 shown in Table I [6] for different number of stations m. We list the calculated α in Table III. We simulate CSMA/CA2+ with parameters in Table II and α from Table III. We choose a station randomly, and plot its average throughput, instant throughput and 5

m j=1

η 2 E[Rj (t)]) )E [Ri (t)]

successful throughput in Fig. 6. Fig. 6 (a) (b) and (c) show one sample for 100, 50 and 10 stations respectively. We list the average throughput and successful throughput in Table III. The simulation shows that the throughput achieved from CSMA/CA2+ is better than that from 802.11. This also veri?es the parameters selected by heuristic method ?t for different numbers of stations. To achieve certain performance for CSMA/CA2+, α and β have to be adjusted according to the number of competing stations. We will study how to estimate the number of competing stations under CSMA/CA2+ protocol. Finally, we mention that [8] provides a Kalman ?lter estimation of the number of competing terminals in IEEE 802.11 network. IV. C ONCLUSION In this paper, we improve CSMA/CA2 proposed in [14] in two aspects. We rede?ne the normalized sending rate to re?ect the station’s instant throughput. We point out the way CSMA/CA2 applies AIMD could not guarantee the fairness for each station. Based on CSMA/CA2, we propose our new algorithm CSMA/CA2+ and apply AIMD mechanism to controlling the instant sending rate of each station. We use stochastic linear difference equation to study the improved protocol CSMA/CA2+. We present a heuristic method to select the parameters

TABLE III T HROUGHPUT OF E ACH S TATION FROM S IMULATION m 100 50 10 α 0.004157 0.014096 0.233496 Average Thru. (CSMA/CA2+) 0.0139 0.0263 0.1196 Goodput (CSMA/CA2+) 0.0068 0.0138 0.0794 Goodput (802.11) 0.0033 0.0093 0.0713

0.03

100 Stations

Average Throughput Goodput

50 Stations

0.04 Average Throughput Goodput 0.035

10 Stations

0.15 Average Throughput Goodput

0.025 0.03

0.1

0.02

throughput

throughput

0.02

0.015

0.015 0.01 0.01

throughput

0.05 0

0 0.01

0.025

0.005

0.005

0

0.001

0.002

0.003

0.004

0.005

α

0.006

0.007

0.008

0.009

0.01

0

α

0.02

0.03

0

0.1

0.2

0.3

α

(a) 100 stations (α : 0.0001?0.01)

(b) 50 stations (α : 0.001 ? 0.03) Fig. 5. Throughput with Different α

(c) 10 stations (α : 0.01 ? 0.29)

100 Stations

0.05 Average Throughput Instant Throughput Goodput 0.04 0.05

50 Stations

Average Throughput Instant Throughput Goodput

10 Stations

0.25 Average Throughput Instant Throughput Goodput

0.04

0.2

0.02

throughput

throughput

throughput

0.03

0.03

0.15

0.02

0.1

0.01

0.01

0.05

0 200

220

240

260

280

300

320

340

360

380

400

0 200

220

240

260

280

300

320

340

360

380

400

0 200

220

240

260

280

300

320

340

360

380

400

time (sec)

time (sec)

time (sec)

(a) 100 stations (α = 0.0041) Fig. 6.

(b) 50 stations(α = 0.014) Throughput with α from Table III

(c) 10 stations (α = 0.23)

for CSMA/CA2+. In the coming study, we will focus on analysis of the collision process of CSMA/CA2+, and study of using different AIMD parameters to differentiate services in one wireless network. R EFERENCES

[1] E. Altman, K. Avrachenkov, and C. Barakat, “A Stochastic Model of TCP/IP with Stationary Random Losses,” ACM SIGCOMM, 2000. [2] F. Baccelli and P. Bremaud, “Elements of Queueing Theory: Palm-Martingale Calculus and Stochastic Recurrences”, Springer-Verlag, 1994 [3] V. Bharghavan, A. Demers, S. Shenker, and L. Zhang, “MACAW: A Media Access Protocol for Wireless LANs,” ACM SIGCOMM, 1994 [4] A. Brandt, “The stochastic equation Yn+1 = An Yn + Bn with stationary coef?cients,” Adv. Appl. Prob., Vol 18, 1986 [5] R. Brockett, W. Gong and Y. Guo “Stochastic Analysis for Fluid Queueing Systems,” Proceedings of 38th Conference on Decision and Control, 1999 [6] F. Cali, M. Conti and E. Gregori, “Dynamic Tuning of the IEEE 802.11 Protocol to Achieve a Theoretical Throughput Limit,” IEEE/ACM Transations on Networking, Vol 8, Issue 6, Dec. 2000

[7] D. Chiu and R. Jain “Analysis of the Increase and Decrease Algorithms for Congestion Avoidance in Computer Networks,” Computer Networks and ISDN Systems, 17 (1989) [8] G. Bianchi and I. Tinnirello, “Kalman Filter Estimation of the Number of Competing Terminals in an IEEE 802.11 Network,” IEEE INFOCOM, 2003 [9] P. Glasserman and D.D. Yao, “Stochastic vector difference equations with stationary coef?cients,”, J. Appl. Prob., Vol 32, 1995 [10] IEEE, “IEEE std 802.11–Wireless LAN media access control (MAC) and physical layer (PHY) speci?cations,” 1997. [11] V. Misra, W. Gong, D. Towsley, “Fluid-based Analysis of a Network of AQM Routers Supoorting TCP Flows with an Application to RED,” ACM SIGCOMM, 2000 [12] T. Ozugur, M. Naghshineh, P. Kermani, and J.A. Copeland, “Fair Media Access for Wireless LANs,” Proc. of IEEE GLOBECOM, 1999 [13] Y. Wang, and B. Bensaou, “Achieving Fairness in IEEE 802.11 DFWMAC with Variable Packet Lengths,” Proc. of IEEE GLOBECOM, 2001. [14] Q. Xue, W. Gong and A. Ganz, “Next Generation MAC Protocol for Multimedia Wireless Networks: CSMA/CA2”, submitted for publication, Jan, 2003 [15] S. Xu, T. Saadawi, “Revealing the Problems with 802.11 Medium Access Control Protocol in Multi-hop Wireless ad hoc Networks,” IEEE Computer Networks, 2002(38) page 531-548.

6

赞助商链接

(Additive Increase Multiplicative Decrease)*AIMD* 应用...*Collision* *Avoidance*)CA 拥塞避免(congestion *avoidance*...*Protocol*)LCP 链路状态,数据库(link-state *database*...