This chapter will discuss about CSMA/CA and TDMA frame format in general, and as well as the throughput comparison between CSMA/CA and TDMA. IEEE 802.11 standard offers three different physical layer implementations; each of them corresponds to a kind of technology that has been commonly used to implement WLAN systems. The MAC layer is exactly the same for each implementation, which defines the exact operation of the Carrier sense multiple accesses with collision avoidance CSMA/CA protocol. It is popular because of its simplicity and robustness. It does not require much infrastructure support (I. Rhee, 2005). Collision can happen in any two hop neighbors. RTS/CTS can alleviate the hidden terminal problem, but it incurs high overhead and does not perform well with respect to intensive contention high-volume traffic (A. Woo, 2001) (J. Polastre, 2004). This chapter is intended to be a reference. There is only so much life any author can breathe into framing details, no matter how much effort is expended to make the details interesting. The research in (I. Rhee, 2005) proposed Z-MAC, a novel way to combine CSMA and TDMA together. It can adapt to the level of contention in the network. When the contention level is low, it behaves like CSMA; while the contention level is high, it uses a TDMA hint to enhance contention resolution. However, all the nodes have to constantly perform low power listening in all time slots to check incoming data. Because of the features of mixing contention-based scheme and timing slotted schedule, this constant-listening issue seems a challenging problem in nature for all hybrid CSMA/TDMA scenarios.
3.2. Carrier Sense Multiple Access with Collision Avoidance CSMA/CA
The important idea that we prefer to use is CSMA/CA as in IEEE802.11a protocol. Basically a CSMA consists on this process: The station that wants to send data must first sense the medium, whether it is free, then it sends the data, but if it is busy, then the transmission is postponed to a next time (a backoff algorithm is used to retransmit the data). When CSMA working with CA (Collision Avoidance) protocol is more complex if the medium is busy the process is the same, but when the medium is free the station does not transmit immediately. In this case, the station will be able to transmit the data if the medium is free during a specific time (which is called DIFS: Distributed Inter Frame Space). The receiver will then acknowledge the received data. If the sender does not receive an acknowledgment to retransmit the data until it receives an acknowledgment or prevent its spread after a certain number of retransmissions (IEEE 802.11, 2007).
IEEE802.11 protocol shows how CSMA works in detail (IEEE Std 802.11, 1999). We cannot apply exactly the ideas explained before due to the following reason: in CSMA/CA the transmitter of the data is the one that needs to sense the medium before sending its information, in our case the receiver is the one which needs to do that. As we simplify the process, if there are more than one client want to receive data from same unicast service, therefore, it must send a small packet to the transmitter to communicate with its address and the interest in the service, the client will sense the medium first while is empty, and then will send the packet together with its address. But, if the medium is busy then the client has to wait until the medium it will be free and then it may send the packet. And also if there are more than one client is interested in the same service and the service is not able to consumed by different clients at the same time, then we must defined the total size of the data each service. We should realise that probably the provider will need more than one packet to send all the information about the service. We have to define (if we want to avoid having to implement a fragmentation mechanism) the number of packets necessary to consume each unicast service. Then, when one client A has just finished consuming the service the client B is able to begin consuming it. When defining the size of each data service (which will probably be bigger than the size of packets generated by the application layer), we created a kind of continuity between frames. This means that if a client is unable to consume the service in a frame, it will continue to receive packets in the next service timeslot.
3.3. TDMA FRAME FORMAT
3.3.1 Data frames
From the IEEE 802.11 protocol we got information about the definition of the MAC frames and about characteristics of the physical layer. The IEEE 802.11 standard establishes the general format of a MAC frame which consists of three fields: the MAC header, the body and the Frame Check Sequence (FCS). The header (as we can see in Figure 3.1) is divided into several fields. The existence of all of those fields depends on the type of the MAC frame.
Frame Duration/ Address 1 Address 2 Address 3 Sequence Address 4 Qos Frame FCS
Control ID Control Control Body Octos: 2 2 6 6 6 2 6 2 0-23-1-24 4
MAC Header
Figure 3.1: Fields of a MAC frame. The Figure is defined in (IEEE Std 802.11, 1999). It can appreciate the three fields, the MAC header, the frame body and the FCS.
The smallest MAC frame is defined by the Frame control, Duration/ID, Address 1 (which belong to the header) and the FCS (IEEE Std 802.11, 1999). If we pay attention to the frame control field we will see that it has the following fields as shown in Figure 3.2:
Protocol Type Subtype To DS From DS More Retry PWT Mgt More Data Protected Order
Version Frag Frame B0 B1 B2 B3 B4 B7 B8 B9 B10 B11 B12 B13 B14 15
Bits: 2 2 4 1 1 1 1 1 1 1 1
Figure 3.2: Fields of the frame control. The figure is field included in the MAC header (Zhihui Chen, 2004).
3.3.2 Management Frames
The field type allows the definition of three types of MAC frames: management, data and control frames. In (IEEE Std 802.11, 1999) different subtypes of each type of frame are defined. We need to know which type of MAC frame we need to use for sending the information in each channel: CCH and SCH. As explained at the previous chapter, the service channel will be used to send application data and the control channel to announce WAVE services. For this reason we decided that in SCH we will transmit data frames (subtype data) and in CCH we will transmit management frames (subtype beacon). Further details of the frame formats are defined in (IEEE Std 802.11, 1999).
From the standard IEEE 1609.4 we got the idea about how to define the mechanisms or services used to support MAC Service Data Unit (MSDU) delivery and to manage channel coordination. Those services constitute an extension of the functions introduced in protocol IEEE 802.11 and are basically necessary to enable multi-channel coordination (IEEE Std 1609.4-2006). Those services are:
Channel routing: This service controls the routing of data packets from the Logic Link Control (LLC) to the MAC. The process will be different depending on the data we want to route: WAVE Short Message Protocol (WSMP) data or IP data.
User priority: Once an MSDU arrives at the MAC layer and the channel routing process has been done, the User Priority (UP) is used to handle MSDUs with different priority. The Enhanced Distributed Channel Access (EDCA) functionality is used. This user priority is necessary to support a variety of safety and non-safety applications.
We should point out that the goal of having the EDCA functionality is to handle the access to the medium when CSMA/CA is used, because each user receives a different priority in the access to the medium. In our case this module should be adapted to the TDMA scheme, which means there is no priority between users, but a priority between different data flow corresponding to different applications in the provider side.
Channel coordination: This service is implemented to support data exchanges between one or more devices, which are not able of simultaneously monitor the CCH and exchanging data on SCHs. This service requires a synchronization procedure defined in (IEEE Std 802.11, 1999).
MSDU data transfer: this service is in charge of sending the data which belong to the CCH or to the SCH.
Figure 3.3: Architecture of MAC layer in WAVE devices
As we can see in Figure 3.3 the MAC and PHY layers include management entities (called MAC Layer Management Entity, MLME, and Physical Layer Management Entity, PLME, respectively). These management entities provide the layer management service interfaces through which layer management functions may be invoked (IEEE Std 1609.4-2006). The WAVE Management Entity (WME) is a layer-independent entity which would typically perform such functions on behalf of general system management entities and would implement standard management protocols.
If we want to implement our protocol correctly, we should define both protocol planes and all the processes which communicate both planes, the only problem is nowadays the management plane is not implemented in the Network Simulator, which means there are a lot of work to do. Finally we opted to do only changes related to the data plane. Although the scope of this thesis is to define a MAC protocol we will probably have to deal with the physical layer. Basically we need to set up correctly the parameters which define the physical layer in C2X communications. Those parameters are the modulation, the bandwidth (or data rate), the definition of the transmission time and the sensitivity of the receiver.
3.3.2.1 The Structure of Management Frames
802.11 management frames share the structure that shown in Figure 3.4. The MAC header is the same in all management frames; it does not depend on the frame subtype. Management frames use information elements, little chunks of data with a numerical label, to communicate information to other systems.
Frame Duration/ Address 1 Address 2 Address 3 Sequence Address 4 Qos Frame FCS
Control ID Control Control Body Octos: 2 2 6 6 6 2 6 2 0-23-1-24 4
MAC Header
Figure 3.4 Generic management frame
Address fields
As with all other frames, the first address field is used for the frame's destination address. Some management frames are used to maintain properties within a single BSS. To limit the effect of broadcast and multicast management frames, stations are required to inspect the BSSID after receiving a management frame, though not all implementations perform BSSID filtering. Only broadcast and multicast frames from the BSSID that a station is currently associated with are passed to MAC management layers. The one exception to this rule is Beacon frames, which are used to announce the existence of an 802.11 network.
BSSIDs are assigned in the familiar manner. Access points use the MAC address of the wireless network interface as the BSSID. Mobile stations adopt the BSSID of the access point they are currently associated with. Stations in an IBSS use the randomly generated BSSID from the BSS creation. One exception to the rule: frames sent by the mobile station seeking a specific network may use the BSSID of the network they are seeking, or they may use the broadcast BSSID to find all networks in the vicinity.
Frame body
Management frames are quite flexible. Most of the data contained in the frame body uses fixed-length fields called fixed fields and variable-length fields called information elements. Information elements are blobs of data of varying size. Each data blob is tagged with a type number and a size, and it is understood that an information element of a certain type has its data field interpreted in a certain way. New information elements can be defined by newer revisions to the 802.11 specification; implementations that predate the revisions can ignore newer elements. Old implementations depend on backward-compatible hardware and frequently can't join networks based on the newer standards. Fortunately, new options usually can be easily turned off for compatibility.
This section presents the fixed fields and information elements as building blocks and shows how the building blocks are assembled into management frames. 802.11 mandate the order in which information elements appear, but not all elements are mandatory. This section shows all the frame building blocks in the specified order, and the discussion of each subtype notes which elements are rare and which are mutually exclusive.
Types of Management Frames
Frame Beacon
Beacon frames announce the existence of a network and are an important part of many network maintenance tasks. They are transmitted at regular intervals to allow mobile stations to find and identify a network, as well as match parameters for joining the network. In an infrastructure network, the access point is responsible for transmitting Beacon frames. The area in which Beacon frames appear defines the basic service area. All communication in an infrastructure network is done through an access point, so stations on the network must be close enough to hear the Beacons.
Figure 3.5 shows most the fields that can be used in a Beacon frame in the order in which they appear. Not all of the elements are present in all Beacons. Optional fields are present only when there is a reason for them to be used. The FH and DS Parameter Sets are used only when the underlying physical layer is based on frequency hopping or direct-sequence techniques. Only one physical layer can be in use at any point, so the FH and DS Parameter Sets are mutually exclusive.
The CF Parameter Set is used only in frames generated by access points that support the PCF, which is optional. The TIM element is used only in Beacons generated by access points, because only access points perform frame buffering. If the Country-specific frequency hopping extensions were to be present, they would follow the Country information element. Frequency hopping networks are much less common now, though, so we omit the frequency hopping extensions for simplicity. Likewise, the IBSS DFS element occur between the Quiet and TPC Report elements, were it to appear.
MAC Header
Frame Duration/ Address 1 Address 2 Address 3 Sequence Address 4 Qos Frame FCS
Control ID Control Control Body Octos: 2 2 6 6 6 2 6 2 0-23-1-24 4
Timestamp beacon capability SSID FH DS CF IBSS
Interval info parameter parameter parameter parameter TIM
Set Set Set Set Octos: 8 2 2 variable 7 2 8 4 variable
Mandatory Optional
Figure 3.5 Beacon frame
Probe Request
Mobile stations use Probe Request frames to scan an area for existing 802.11 networks. The format of the Probe Request frame is shown in Figure 3.6. All fields are mandatory.
Frame Duration/ Address 1 Address 2 Address 3 Sequence Address 4 Qos Frame FCS
Control ID Control Control Body Octos: 2 2 6 6 6 2 6 2 variable 4
MAC Header Frame body
Figure 3.6 Probe Request frame
A Probe Request frame contains two fields: the SSID and the rates supported by the mobile station. Stations that receive Probe Requests use the information to determine whether the mobile station can join the network. To make a happy union, the mobile station must support all the data rates required by the network and must want to join the network identified by the SSID. This may be set to the SSID of a specific network or set to join any compatible network. Drivers that allow cards to join any network use the broadcast SSID in Probe Requests.
3.3.3 Inter Frame Spaces
The standard defines four type of inter frame spaces, which are use to provide different priorities:
SIFS, which stands for (Short Inter Frame Space), is used to separate transmission belonging to a single dialog (e.g. Fragment - Ack), and is the minimum inter frame space, and there is always at most one single station to transmit at this given time, hence having priority over all other station. This value is a fixed value per PHY and is calculated in such a way that the transmitting station will be able to switch back to receive mode and be capable of decoding the incoming packet on the 802.11 FH PHY this value is set to 28 microsecond.
PIFS, (Point coordinator Inter Frame Space), is used by the access point or point coordinator, as called in this case, to gain access to the medium before any other station. This value is SIFS plus a slot time (defined in the following paragraph), i.e. 78 microsecond.
DIFS, (Distributed Inter Frame Space), is the inter frame space used for a station willing to start a new transmission, which is calculated as PIFS plus one slot time, i.e. 128 microseconds.
EIFS, (Extended Inter Frame Space), which is a longer IFS used by a station that has received a packet that could not understand, this is needed to prevent the station (who could not understand the duration information for the virtual carrier sense) from colliding with a future Packet belonging to the current dialog.
3.3.3.1 Exponential Backoff Algorithm
Backoff is a well known method to resolve contention between different stations willing to access the medium; the method requires each station to choose a random number (n) between 0 and given number, and wait for this number of slots before accessing the medium, always checking whether a different station has accessed the medium before.
The slot time is defined in each a way that a station will always be capable of determining of the station has accessed the medium at the beginning of the previous slot.
This reduces the collision probability by half.
Exponential Backoff means that each time the station choose a slot and happens to collide, it will increase the maximum number of the random selection exponentially.
The 802.11 standard defines an Exponential Backoff Algorithm that must be executed in the following cases:
When the station senses the medium before the first transmission of a packet, and the medium is busy.
After each retransmission.
After a successful transmission.
The only case when the mechanism is not used is when the station decides to transmit a new packet and the medium has been free for more than DIFS.
THROUGHPUT COMPARISON OF CSMA/CA AND TDMA
(Chang, 2009) has studied the different multiple accesses of CSMA/CA and CSMA/CATDMA, the throughput analytical model for each multiple access is constructed in the following sections.
3.4.1 Throughput for CSMA/CA
To derive the system throughput for CSMA/CA, they assume that the superframe (SF) is just made by the beacon and the contention access period (CAP), but there is no channel time allocation period (CTAP). Then, all frame transmissions are only performed in the CAP based on CSMA/CA.
At a certain time in a piconet consisting of M devices, on average N devices tend to transmit frames. During a CAP, assume that a device transmits a frame with the probability of γN. Time in the CAP is discredited into slots, and all devices are synchronized to operate in slotted time. The frame transmission of the contending devices causes the wireless channel to be idle, success or collision. Idle happens that none of devices transmits the frame; success happens that just one device transmits the frame, and collision happens that multiple devices transmit the frame at the same time. The probability of collision, denoted by pN, is derived from the Bernoulli process.
(3.1)
Upon the random backoff procedure in CSMA/CA, the frame transmission probability of a device, γN, can be derived from the average number of transmissions made by a device during the average backoff time for the device to successfully transmit a frame where N devices are contending with the channel. Then, γN can be derived by
(3.2)
Where E [D] is the average backoff time for a device to successfully transmit a frame when there are N channel contending devices, and E [A] is the average number of transmission attempts made by the device during E [D]. According to the exponential backoff procedure, E [D] can be derived as follows.
(3.3)
Where W is the minimum backoff window size, m' is the maximum backoff stage, and m is the retransmission limit. During the period of E [D], furthermore, the average number of transmission attempts made by a device, E [A], can also be modeled as a truncated geometric random variable as follows.
(3.4)
E [D] and E [A] are determined from pN . γN is a function of pN; further, by substituting (3) and (4) in (2), and from (1) and (2), pN and γN can be obtained. To derive successful frame transmission in the CAP, now the authors investigate the channel status that can be either idle or busy. The channel is idle only when there is no frame transmission, or sensed busy because of collisions or successful frame transmissions. In a given length of the CAP per SF, TCAP, the average number of busy slots, nbs, can be expressed as
(3.5)
Where nis is the average number of idle slots, Tis and Tbs are the duration of an idle slot and a busy slot, respectively. Tis is given as SIFS(2.5us)+pCCADetectTime(5us) and Tbs is given as TFRM + SIFS(2.5us) + TACK + Backoff-IFS(7.5us) for using Imm-ACK or TFRM+Backoff-IFS(7.5us) for No-ACK, where TFRM is the length of the data frame and TACK is the length of the ACK frame. Since the channel is idle only when all requesting devices are in the backoff stage, nis can be approximated as the average backoff time a device experiences as derived in (3).
When a channel is busy, which implies that at least one device is transmitting in a given slot, two events may occur. The first event is a collision resulting from multiple simultaneous transmissions, and the second event is a successful transmission when only one device transmits in that slot.
N-nsuc
N-1
N-2
N
……………
Figure.3.7 Process of frame service during CAP in TDMA
The probability of successful transmission in a busy slot, ps, and the probability of collision in a busy slot, pc, are derived as
(3.6)
Where n is the average number of devices contending the channel in a busy slot, which is
Since the two events of collision and success are independent of each other, the average number of busy slots that contribute to successful transmissions, nsuc, can be considered as a binomial random variable, which can be derived as
(3.7)
The system throughput operated on CSMA/CA, denoted by SC/C, can be derived by the total payloads (except the preamble and the header from the frame) of the successfully transmitted frames during a SF. Thus,
(3.8)
Where B is the payload for a frame, Lsf is the length of SF consisting of the beacon and the CAP, and TB is the length of the beacon.
Throughput for TDMA
Contrary to data transmission on the CAP in CSMA/CA, data transmission in TDMA is mainly performed at the CTAs based on TDMA. In TDMA, the system throughput depends on the number of allocated CTAs since data transmission is mainly performed during the CTAs. Before deriving the number of allocated CTAs, it is particularly necessary to consider command transmission during the CAP. At a certain time in a piconet consisting of M devices, assume that i CTAs, denoted by CTAi are allocated by 2i devices with the assumption of each device not allowing multiple communication links. In CTAi, 2i devices of source and destination are active, while M − 2i devices are idle in the piconet.
At the beginning of the CAP in CTAi, on average N = (M − i) ・ Preq devices send CTA request commands to the PNC, where Preq is the probability of transmitting a frame by each device. Note that iPreq active devices may send CTA request commands in order to release the allocated CTAs due to the end of communication, while (M−2i)Preq idle devices may send CTA request commands in order to allocate the new CTAs to start communication. In order to derive the number of successful frame transmissions, nsuc, during the CAP, the average number of busy slots, nbs derived in (5), is used. Note that during the given CAP one request is served and the remaining N −1 requests are continued to reach N -nsuc as shown in Figure 3.7. Tis and Tbs are described previously, while nis can be presented by
(3.9)
Where is the average collision probability the contending devices experience during TCAP, From N requests being continued to reach N −nsuc, the average collision probability of can be derived by the collision probability derived in (1) for each step of [N,N − 1, ...,N − nsuc + 1] as follows.
(3.10)
Similarly (6), given the channel is busy, the probability of successful CTA request transmission in a busy slot, , and the probability of CTA request collision in a busy slot, , are derived as
(3.11)
Where is the average number of devices contending the channel in a busy slot and is the average transmission probability during the process in [N,N −1, ...,N −nsuc+1]. and are given as
The average number of success busy slots, nsuc, that is similar to (7), can be derived by
(3.12)
As previously mentioned, since the channel time requests are sent from the active devices for CTA release as well as from the idle devices for CTA allocation, both nsuc and ncol are caused by the iPreq active devices and (M −2i)Preq idle devices at CTAi. To study the system throughput, the authors derive and which denote the number of idle devices with success slots and the number of idle devices with collision slots, respectively, as follows.
(3.13)
Parameters for throughput analysis also shown in table 3.1
Table 3.1 parameters for throughput analysis and comparison
Parameters
CSMA/CA
TDMA
Number of devices in a piconet (M)
1-20
Channel time request/
release probability (Preq)
1
Number of frames per CTA (k)
N/A
10, 30
Frame payload (B)
1KBytes ~ 1MBytes
Data rate (R)
1.620Gbps (BPSK/RS)
3.240Gbps (QPSK/RS)
SIFS
2.25us
MIFS
0.5us
Length of beacon (TB)
49.4us
Length of ACK (TACK)
17.8us
Length of frame (TFRM)
Preamble (1.185us) + Header (0.44us)
+ Payload (B/R)
The expected allocating CTAs for communication per SF, NCTAi, are given as
(3.14)
Since the throughput of the piconet is achieved by data transmission in the allocated CTAs within a SF, then the system throughput at the given time for TDMA, denoted by SC/Ti , is given as
(3.15)
Where k is the number of transmitting frames per CTA, B is the payload of the frame and Lsfi is the superframe length consisting of the beacon (TB), the CAP (TCAP ) and NCTAi (TCTAi ). For a long term period, the system throughput operated on TDMA is the average throughput on the allocated CTAs being from 0 to M/2. Thus,
(3.16)
CHAPTER SUMMARY
In this chapter we discussed about CSMA/CA and TDMA frame format in general. And we have studied different performance parameters of the CSMA/CA protocol. IEEE 802.11 standard offers three different physical layer implementations; each of them corresponds to a kind of technology that has been commonly used to implement WLAN systems. The MAC layer is exactly the same for each implementation, which defines the exact operation of the CSMA/CA protocol. And also this chapter is intended to be a reference. There is only so much life any author can breathe into framing details, no matter how much effort is expended to make the details interesting. And also this chapter studied the system throughput of the different wireless multiple access methods of CSMA/CA and hybrid CSMA/CA and TDMA. However the next chapter, chapter four provides the details of implementation and design of Wi-Fi based TDMA protocol and components with compressive on different parts of the simulation. And also discusses the main ideas that we used later to develop our TDMA protocol in NS2.
