Analysis of Broadcast Strategies and Network Parameters in IEEE 802.11p VANETs using Simple Analytical Models

Analysis of Broadcast Strategies and Network Parameters in IEEE 802.11p VANETs using Simple Analytical Models

Younes Bouchaala and Oyunchimeg Shagdar

Institut Védecom 77, rue des Chantiers

78000 Versailles, France

Paul Muhlethaler

EVA team

Inria Paris Rocquencourt 78153 Le Chesnay Cédex

AbstractThis paper proposes and analyzes different broadcast strategies in IEEE 802.11p Vehicular Ad-hoc NETworks (VANETs). The first strategy is the default IEEE 802.11p strategy. Using a model derived from the Bianchi model, we provide the network performance in terms of throughput and success rate. The second strategy is to use an acknowledgment technique similar to the acknowledgment with point-to-point traffic. A node will send its broadcast packet as in the default case, but it requires an acknowledgment from a neighbor node. This node may be a random neighbor or may be selected according to precise rules. We analyze this second strategy in terms of throughput and success rate. Somewhat surprisingly, we show that this second strategy improves the delivery ratio of the transmitted packets but reduces the overall throughput. This means that if the CAM messages (Cooperative Awareness Messages) are broadcasted, the total number of packets actually delivered will be greater with the default strategy than with the improved strategy. We propose a third strategy which consists in using the default strategy for normal packets, but we add random redundant transmissions to ensure greater reliability for very important packets. We show that with this simple technique, not only do we obtain suitable reliability, but we also achieve larger global throughput than with the acknowledgment-oriented technique. Another contribution of this paper is to compute network performance in terms of throughput and success rate with respect to the network parameters and to analyze their impact on performances

Keywords: VANETs, broadcast, IEEE 802.11p access scheme carrier sense,back-off

1. INTRODUCTION

   IEEE 802.11p was proposed as the main communication protocol to offer Wireless Access in Vehicular Environments (WAVE) [1]. IEEE802.11p is required to support Intelligent Transportation Systems (ITS) applications by providing communication between vehicles (V2V), and between vehicles and roadside infrastructure (V2I). Nowadays, one of the main ITS applications expected by vehicle manufacturers is safety applications that rely on the broadcast principle. Therefore, a reliable broadcast scheme is necessary to ensure the reliable reception of critical messages such as priority Cooperative Awareness Messages (CAM) [2] and Decentralized Environmental Notification Messages (DENM) [3]. In the contention-based Medium Access Control (MAC)

   of IEEE802.11p, several studies have shown a correlation between an increase in the number of connected vehicles and increase in packet loss rate. Several approaches to improve the reliability of broadcasting have been proposed in the literature, as reported in Section II.

   This paper's main contribution is to propose and to analyze two broadcast strategies and to compare them with the default IEEE 802.11p broadcasting method [4],[5]. We propose a mathematical model derived from the Bianchi [6] model to analyze the network performances of the default broadcast service of the IEEE 802.11p protocol in terms of throughput and packet delivery ratio,

   The remainder of this paper is organized as follows. Section II briefly reviews related work; Section III describes the proposed system model and the analytical model. We propose three different broadcast techniques. Simulation results are reported in Section IV. Finally Section V concludes the paper.

2. RELATED WORK

   The fundamental Medium Access Control (MAC) technique of the IEEE 802.11 based Wireless Local Area Networks (WLANs) is known as the Distributed Coordination Function (DCF). DCF is a Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) scheme that assumes all packet losses within a WLAN are due to packet collision. To avoid to packet losses, DCF triggers a binary slotted exponential backoff procedure. In the contention-based MAC used in IEEE 802.11, as well as the amendment IEEE 802.11p, packet loss greatly depends on the channel contention, therefore, many studies have been carried out in the literature to evaluate the system throughput for WLANs as well as for Wireless Access in Vehicular Environments. In his performance Analysis of the IEEE 802.11 DCF, Bianchi [6] provided an analytical model to evaluate the throughput performance of both basic access and Request To Send/Clear To Send (RTS/CTS) access mechanisms as well as a combination of the two assuming a finite number of terminals and ideal channel conditions. Bianchi demonstrated the accuracy of his model for predicting the system throughput.

   Unfortunately, most IEEE 802.11 DCF performance evaluation studies proposed in the literature cover the unicast transmission mode. There do, however exist a few studies

   related to the IEEE 802.11 protocol in broadcast mode. Hafeez et al.[7] have proposed an analytical study in which they model each terminal as one two-dimensional Markov chain to calculate the probability of successful transmissions of the periodic status messages (CAM), as well as the priority messages (DENM). They show that their model gives accurate results when estimating the recommended throughput level of IEEE 802.11p for each category of messages. Ghahramani et al.[8] start from the assumption that the number of contending vehicles in VANETs varies, enabling them to model the dynamicity of the contending terminals and to add more accuracy to the existing methodology of IEEE 802.11p MAC broadcast mode evaluation. The study in

   [5] proposes a simple analysis of IEEE 802.11 in broadcast

   occurs with a probability of 1-(1-)M. Thus, the mean duration between two slots will be

   (1-(1-)M) T+ (1-)M .

   This duration is called the duration of a pseudo slot. It is also possible to compute the throughput t of the system

   (1 (1 )M )T

   t (1 (1 )M )T (1 )M

   The successful throughput is ts is given by

   mode. In this paper we re-use the results of [5] and we adapt and exploit them in the context of VANETs. Since we also propose to use reliable broadcast, we will use and adapt the

   M (1 )M 1T

   ts (1 (1 )M )T (1 )M

   (1)

   study of the point-to-point mode as our broadcast transmissions will require acknowledgment.

3. SYSTEM MODEL

   We use models which are very close to the Bianchi model [6]. In these models M is the number of vehicles in the network within the same carrier sense range; is the packet arrival rate in a station assumed to be Poisson and the duration of a packet is denoted by T.

   The other parameters are related to the IEEE 802.11p protocol. These parameters are: the duration of a mini-slot , and the number of back-off slots W. should be greater than the sensing delay of the Carrier Sense Multiple Access (CSMA) scheme of the IEEE 802.11p protocol. In usual implementations, is of the same order as the sensing delay of CSMA. W is the greatest back-off window that a node can select. In practice, W is set to the maximum duration of the back-off. When IEEE 802.11 uses an acknowledgment to enhance the transmission success rate, another parameter n is required in order to fix the maximum number of retransmissions before a packet is discarded.

   All the models derived from the Bianchi model assume that the channel can be modeled as a succession of slots. Each slot

   s is also the probability of successful transmission for a randomly transmitted packet.

   Thus, the performance of the network is completely defined if we can compute . The models derived from [6] are Markovian models whose states are the value of the back-off counter. When there are retransmissions, the value of the back-off counter is complemented by the number of previous transmissions. The transitions in these models are simple. When the station is in the idle state, the transmission to a back-off state (between 0 and W) is random with the probability of 1/(W+1). When the station is in back-off in the state 1 k+1 W, the transition is towards state k with the probability of pe=(1-)M, this means that there is no transmission. With probability 1- pe the station with back-off counter k+1 remains in the same state. When the back-off counter reaches 0, the state transmission rate to the idle state is 1.

   1. Pure broadcast

      We first consider a model without retransmission, which represents the default operation mode of IEEE 802.11p. In the model with no retransmission [5] the resolution of the steady-state of the Markov chain leads to the following equation:

      may be a mini-slot (of duration ) or a slot of duration T.

      1 W

      1

      The mini-slots are used to represent the time intervals during which the channel is idle. There is no activity during these intervals and thus the nodes which are in back-off mode just decrement their back-off counters. When the back-off counter reaches zero, the node transmits its packet. The slot of duration T corresponds to the transmission of a packet. This transmission will succeed if only one node transmits in this

      b0 q 1 2(1 )M .

      with:

      q 1 e ((1(1 )M )T (1 )M )

      (2)

      (3)

      slot as there will be a collision if several nodes transmit simultaneously.

      The models derived from [6] all introduce the node transmission rate at the beginning of a slot. If no node transmits, this occurs with a probability of (1-)M thus the current slot will be a mini-slot of duration . If at least one node is transmitting, the current slot will of duration T, which

      where b0 denotes the probability that the node has a pending packet whose back-off is 0. q denotes the probability of at least one packet arriving during a pseudo-slot. A pseudo slot is a slot of duration equal to the mean duration of a slot on the channel, i.e. weighted by the probability of an idle slot plus and (3) we obtain the following fix-point equation in :

      1

      1 W

      1

      transmissions for these packets. These packets are randomly

      1 e ((1(1 )M )T (1 )M )

      2(1 )M

      (4)

      re-transmitted n-1 times, thus, in total, a packet will be

      which can be easily solved numerically. If is known via (4) then the successful throughput can be easily computed using (1).

   2. Broadcast with acknowledgment request

   We will also discuss a model with retransmission. The protocol is still broadcast but we will assume that a node requests an acknowledgment from, for example, a random neighbor. If the acknowledgment is sent, the node will

   transmitted n times. We assume that the number of additional packets due to these retransmissions is negligible and so the station transmission probability is . given by (4). The probability of successful transmission for a normal packet is ts which is computed by (1). The probability of successful transmission for a packet with n retransmissions is

   s

   1 (1 t )n .

   I / E(I)= l

   transmit another packet. If not, the packet is transmitted again and the collision window is doubled. The collision window reaches 2n W after n collision. If a packet reaches n+1

   collisions, the packet is dropped. Thus even if the

   transmission remains in broadcast mode, the protocol

   operates as in unicast mode with an acknowledgment. We can apply the model derived in [9]. In the model with retransmission (up to n retransmissions) the resolution of the steady-state of the Markov chain leads to the following equation:

   nb lanes

   b

   2(1 2Pcol )q

   0 q[(W 1)(1 2P

   ) WP

   (1 (2P

   )n ] 2(1 q)(1 P

   )(1 2P )

   with

   col coll coll col col

   (5)

   Fig. 1. Number of vehicles in the carrier sense range of a transmitter

   D. Parameters of vehicular networks

   We assume that the vehicles are randomly located on nb

   lanes. In one lane, the mean distance between two vehicles is

   Pcoll

   1 (1 )n 1 (n 1)

   (1 )n2.

   (6)

   1. We denote by cs the carrier sense, when a node transmits at distance up to cs from the current node the channel is

      If we use (3) and (5) in (6) we obtain a fix-point equation in

      The probability of successful transmission for a packet actually sent is:

      1 (1 t )n .

      sensed busy, see Figure 1. For a distance larger than cs, the channel is sensed idle. Thus, given cs, nb and l we can compute the number of vehicles M within the same carrier sense area.

      s

      It is possible to compute the network performance with a similar algorithm. A node still requests an acknowledgment

      M 2 cs nb .

      l

      (8)

      from, for example, a random neighbor but if there is no acknowledgment, the packet is simply retransmitted without any change to the collision window. This is done up to n times, after which the packet is discarded. In such a case, (5) is simply changed into the following equation:

      We assume that each vehicle periodically sends messages,

      and even if it is not completely true, we assume that the traffic is Poisson with a mean rate corresponding to the synchronous traffic. The value of M can be used in (3), (4),

      (5) and (7) to compute . In this paper we assume that the M

      nodes which are within carrier sense range of the current

      b0,0

      2q

      (7)

      node are those which can create a collision with this node if

      1 Pcol q(W 1) 2(1 q)(1 Pcol )

      The proof of this equation is given in the appendix. As q and

      Pcol depends on , we obtain a fix-point equation in

      C. Broadcast with n random retransmissions

      To improve the probability of successful transmission for a small number of dedicated packets, we propose using random

      the current node and another node within this area transmit nearly simultaneously. In this paper we also assume that the transmission from the current node is local for instance the transmission is for the neighbor vehicles so that hidden collisions from nodes outside the carrier sense range are not possible. Thus collisions can only occur when transmissions are simultaneous.

      we express the carrier sense in meters but it can also be expressed in Watts or in decibel

      for instance the transmission is for the neighbor vehicles

4. SIMULATION RESULTS

   We use the following figures =10, =77 bits. The packet size, including the overhead, is T=3998 bits and the data rate is 6 Mbps. We use (if not otherwise defined) l=25 m for the mean distance between two vehicles on a lane. We vary the carrier sense range cs from 300 m to 1400 m.

   1. Effect of the carrier range and the transmission strategy

      Fig. 2. Percentage of transmitted packets successfully received

      In this section we vary cs and we study the different transmission strategies.

      In Figure 2, we present the percentage of success for each broadcast strategy for a transmitted packet. This means that for a transmitted packet we compute the probability that this packet is successfully received. We observe that the acknowledgment procedure has a significant impact on the success rate, especially when the network load is very high.

      In Figure 3 we present the percentage of successfully transmitted packets. This is the ratio of the number of successfully received packets dividd by the number of generated packets. In this ratio we include the loss due to collision and the loss due to the limitation of the total bandwidth. We observe that the techniques using acknowledgments produce a smaller percentage of received packets. This is because managing retransmissions in the techniques using acknowledgments consumes more bandwidth than the other schemes. In Figure 4 we compare techniques using acknowledgments with and without using the binary exponential back-off. We observe that the percentage of successfully transmitted packets is higher with the binary exponential back-off. This is because this back-off reduces congestion. Without binary exponential back-off, the model does not compute any stable equilibrium for cs 1128 if W=16 , for cs 1179 if W=32 and for cs 1304 if W=64. Actually, we have the same phenomenon with the binary exponential back-off but de-stabilization occurs with larger values of cs. The binary exponential back-off helps reduce congestion when the load increases.

      Fig. 3. Percentage of transmitted packets successfully received versus carrier sense range.

      Fig. 4. Percentage of transmitted packets successfully received versus carrier sense range.

      When we have a target for the percentage of successfully transmitted packets, Figures 3 and 4 can be used to compute the convenient carrier sense range to reach this goal. For instance, if we must satisfy a percentage of successful transmissions greater than 0.95, then we must use a carrier sense range smaller than 800 m.

      Figure 5 shows the effect of the maximum number of retransmissions on the percentage of successfully transmitted packets. We observe that when n increases, the percentage of successfully transmitted packets also increases, but above a small threshold (n=4) the gain obtained with larger values of n becomes small. Above n=8 there is nearly no advantage in increasing n.

      Fig. 5. Percentage of transmitted packets successfully received versus carrier sense range for various values of n

   2. Effect of the distance between the vehicles

      Fig. 6. Percentage of transmitted packets versus distance between vehicles

      In this section, we vary the distance l between the vehicles and we use a simple transmission strategy with a constant back-off window of 32. We consider the following figures cs

      = 300, 600, 900 or 1200 m for the carrier sense range.

      In Figure 6 we observe that for nb=6 and nb=8 the percentage of successfully transmitted packets is low when cs=900, 1200

      1. Figure 6. can also be used to find the suitable network parameters to ensure given performance thresholds.

   3. Effect of the number of lanes

   In this section, we vary the number of lanes nb. We use a simple transmission strategy with a constant back-off window of 32. We consider the following figures cs = 300, 600, 900 and 1200m for the carrier sense range. In Figure 7, we observe that, for nb=6 and nb=8, the percentage of successfully transmitted packets is low when cs=900, 1200 m.

   Fig. 7. Percentage of transmitted packets versus the number of lanes

5. CONCLUSION

In this paper, we have shown that simple models allow network performance of IEEE 802.11p to be obtained. Thus if we can estimate the important parameters of a VANET: packet generation rate, packet length, distance between vehicles, number of lanes, carrier sense range, we can easily evaluate the success rate of a random transmission. We have studied various transmission techniques with and without acknowledgments.

We have shown that using acknowledgments incurs overhead which degrades the overall performance of the network in terms of packets successfully transmitted while it improves the success rate of actually transmitted packets. A feasible solution could be to use the simple scheme without any acknowledgment but a few blind transmissions of the same packet could be performed when this packet contains very important information. We would obtain the same effect as with a transmission with an acknowledgment request.

APPENDIX

We prove (7). The proof is an adaptation of [9]. We use the same notation and use the same transmission state diagram represented in Figure 8. The only modification in [9] is in Wi; we have 1 i n, Wi W instead of Wi = 2i W.

bi,k denotes the stationary probability that a node waits for a transmission with a back-off counter k[1,W-1] for the i th transmission (there have been i-1 previous unsuccessful transmission attempts).

Instead of m used in [9] we use n and instead of Peq we use Pcoll i.e m n

and Peq Pcoll.

(1-q) (1-P )

col

1-q

For i=0 we have:

I W 1

W 1W k

q

q(1-P )/W

col

b0,k

k 1

W

k 1

b0,0

W 1 b

q/W

2 0,0

0,0

1 0,1 1

P /W

1

0,W-1

For i [1,n-1]we have:

col

W 1

W 1W k

bi ,k

k 1

k 1

W Pcol bi1,0

P /W

col

W 1 2

Pcol bi1,0

W 1 b Pi

1

i,0 i,1

1

P /W

col

i,W-1

Retransmission i

2

For i=n we have:

0,0

col

P /W

col

W 1

b

W 1 W k

P

(b

• b )

  k 1

  n,k

  k 1 W

  col n1,0

  n,0

  1 1 1

  W 1 P (b

• b )

m,0 m,1

P /W

m,W-1

P /W

2 col n1,0 n,0

n1

col

col

W 1 b Pn Pcol

Retransmission n

2 0,0 col

1P

Fig. 8. State diagram of the back-off scheme with retransmission but with a constant back-off window (no binary exponential back-off)

We still have for 1 i n-1

W 1

bn,k

k 1

W 1 b Pn

0,0 col

2 1 Pcol

col

b Pi b

and b

Pn

1 P

col

We also have:

i,0

col

0,0

n,0

col

n

bi,0

b0,0

1 P

We also have:

i0

col

n

bI (1 q)(1 Pcol )bi,0 (1 q)bI

i0

After a few simplifications, the normalization condition gives the following fundamental equation:

(1 q)(1 Pcol ) n b

b 1 q .

n Wi 1

q i 0

i,0 0,0 q

1 b b

For k[1,W], the other values of bi,k satisfy the following

i0 k 0

b0,0

i,k I

n1 Pn

1 2(1 q)

equations:

[W ( Pi

coll ) ]

2 coll

1 P 1 P q

b0,0

i 0

n1

col col

Pn 1 2(1 q)

[W ( Pi

coll ) ]

2

b W k (q(1 P )n b

• qb ) W k b

coll

i 0

1 Pcol 1 Pcol q

0,k W

col i ,0

k 0

I W 0,0

b0,0 [ W

1 2(1 q)]

bi,k

W k W

Pcol bi1,0 for i [1,n-1]

Thus

b

2 1 Pcol

1 Pcol q

2q

b W k P (b

• b )

0,0

1 Pcol

q(W 1) 2(1 q)(1 Pcol )

n,k

W col n1,0

n,0

and we remark that the computation does not depend on the maximum number of retransmissions n.

REFERENCES

1. Task Group p. IEEE 802.11p, Wireless Access in Vehicular Environments (WAVE) Draft Standard, 2007

2. ETSI EN 302 637-2, Intelligent Transport Systems (ITS) Vehicular Communications – Basic Set of Applications – Part 2 : Specification of Cooperative Awareness Basic Service, History, vol. 1, pp. 144, 2014.

3. ETSI EN 302 637-3, Intelligent Transport Systems (ITS); VehicularCommunications; Basic Set of Applications; Part 3: Specifications of Decentralized Environmental Notification Basic Service, vol. 2, pp. 173, 2014.

4. C. Xu and Z. Yang, Non-saturated throughput analysis of IEEE

   <>802.11 ad hoc networks, IEICE – Trans. Inf. Syst., vol E89-D, No. 5, pp. 16761678, May 2006.

   [Online]. Available http://dx.doi.org/10.1093/ietisy/e89-d.5.1676

5. J.-P. Wang, M. Abolhasan, D. R. Franklin, and F. Safaei, Characterising the behaviour of IEEE 802.11 broadcast transmissions

   in ad hoc wireless LANs, in Communications, 2009. ICC09. IEEE International Conference on. IEEE, 2009, pp. 15.

6. G. Bianchi, Performance analysis of the IEEE 802.11 distributed coordination function, IEEE Journal of Selected Areas in Communications., vol. 18, no. 3, pp. 535547,

7. K. A. Hafeez, L. Zhao, B. N.-W. Ma, and J. W. Mark, Performance analysis and enhancement of the DSRC for vanets safety applications. IEEE T. Vehicular Technology, vol. 62, no. 7, pp. 3069 3083, 2013.

8. S. Ghahramani and A. Hemmatyar, A new hybrid model for performance evaluation of ieee 802.11p broadcast mode in vehicular ad hoc networks: A numerical analysis, in Connected Vehicles and Expo (ICCVE), 2013 International Conference on, Dec 2013, pp. 719725.

9. F. Daneshgaran, M. Laddomada, F. Mesiti, and M. Mondin, Unsaturated throughput analysis of IEEE 802.11 in presence of non ideal transmission channel and capture effects, CoRR, vol. abs/0710.5235, 2007.