Performance Evaluation of ECMA-368 Medium Access Control Protocol for UWB Ad-hoc Networks by Nasim Arianpoo B . S c , Electrical Engineering, University of Tehran, Iran, 2005 A THESIS S U B M I T T E D IN P A R T I A L F U L F I L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F Master of Applied Science in The Faculty of Graduate Studies (Electrical and Computer Engineering) The University of British Columbia September 2007 © Nasim Arianpoo 2007 Abst rac t Ultra Wideband (UWB) is an emerging technology for high rate, short range wireless com-munications. Its unique features such as low power operation, robustness to multi-path fading, and accurate positioning capabilities makes UWB a good platform for wireless personal area networks (WPANs). One of the recent UWB standards standardized by the European Computer Manufacturers Association (ECMA) International is the E C M A -368, which defines the physical (PHY) and media access control (MAC) layers for high rate WPANs. The M A C protocol in ECMA-368 has a superframe structure. Each su-perframe is divided into three different time periods. The beacon period is used for control purposes. The distributed reserved protocol (DRP) period allows devices to re-serve bandwidth for data transmission. The P C A (prioritized contention access) period supports contention-based access between different traffic classes. In this thesis, we propose an analytical model to evaluate the performance of the ECMA-368 M A C protocol. We assume that packets follow the Markovian Arrival Process (MAP) and various service times can be modeled by different phase type distributions (PHYs). We apply the Matrix Geometric Method (MGM) technique and model the system as a M A P / P H Y / 1 queueing system. We derive the probability mass function ii Abstract (pmf) for the number of the packets in the queue, as well as the cumulative distribution function (CDF) for the waiting time of the packets in the queue. The correctness of our proposed analytical model is validated via simulations. We create the ECMA-368 module by using the OPNET simulator. Analytical and simulation results are presented under different scenarios. iii Table of Contents Abstract ii Table of Contents iv List of Figures viii List of Tables x List of Acronyms xi List of Symbols xv Acknowledgements xx 1 Introduction 1 1.1 Contributions 2 1.2 Structure of this report 2 2 Background and Related Work 4 2.1 U W B 4 iv Table'of Contents 2.1.1 Different Access Methods 5 Single Band UWB 5 Multi-band Orthogonal Frequency Division Multiplexing (MB-OFDM) 6 2.2 ECMA-368 Standard 6 2.2.1 Physical layer of ECMA-368 7 2.2.2 Superframe 7 Beacon Period 8 Data Period 9 2.3 Information Element (IE) 10 2.3.1 MAC Layer and Physical Layer Information Exchange 10 Prioritized Contention Access (PCA) 12 Distributed Reserved Protocol (DRP) 13 2.3.2 Inter Frame Spacing 14 2.3.3 ACK Policies 15 2.3.4 Network Allocation Vector (NAV) 16 2.3.5 Transmission Opportunity (TXOP) 16 2.4 Phase Type Distribution (PH) 18 2.5 Markovian Arrival Process (MAP) 20 2.6 Matrix Geometric Method (MGM) 22 2.7 Related Work 26 Table of Contents Proposed Models for M A C Layer 26 Models Based on M G M 32 2.8 Summary 34 3 Analytical Model 35 3.1 ECMA-368 35 3.2 System Model 36 3.3 Waiting Time Distribution 41 3.3.1 DRP Queue 41 3.3.2 P C A Queue 43 3.4 Summary 48 4 Performance Evaluation 49 4.1 System Parameters 49 4.2 Simulation Setup 52 4.3 Results and Discussion 54 4.3.1 Distributed Reserved Protocol (DRP) 54 4.3.2 Prioritized Contention Access (PCA) 57 4.3.3 Increasing the Length of the Superframe 58 4.3.4 Effect on Varying the Arrival Traffic 61 4.4 Summary 66 5 Conclusions and Future Work 67 Table of Contents 5.1 Thesis Summary 67 5.2 Future Work 69 Bibliography 70 List of Figures 2.1 Spectrum division in the physical layer of ECMA-368 7 2.2 Structure of a superframe [1] 8 2.3 State diagram of a two-phase MAP. 21 4.1 Probability mass function of the number of the DRP packets in the system. 55 4.2 Cumulative distribution function of the waiting time of the DRP packets. 56 4.3 Probability mass function of the number of P C A packets in a tagged node 57 4.4 Cumulative distribution function of the P C A packets waiting time. . . . 58 4.5 Probability mass function of the number of DRP packets in a tagged node (there are 40 time slots in each superframe) 59 4.6 Cumulative distribution function of the P C A packets waiting time with 40 time slots 60 4.7 Aggregate throughput of P C A traffic versus arrival traffic for different number of nodes in the network 61 4.8 Medium access delay of P C A traffic versus arrival traffic for different num-ber of nodes in the network 62 viii List of Figures 4.9 Individual throughput of DRP traffic versus arrival traffic for different number of nodes in the network 63 4.10 Aggregate throughput of DRP traffic versus arrival traffic for different number of nodes in the network 64 4.11 Medium access delay of DRP packets versus arrival traffic for different number of nodes in the network 65 ix List of Tables 2.1 Different access categories [2] 12 2.2 User Priority to access category mapping 13 2.3 Some of the M A C layer parameters [2] 15 4.1 Parameters of the simulator 53 x List of Acronyms AIFS Arbitrary Inter Frame Spacing A C Access Category A C K Acknowledgment B K Background B E Best Effort B P S K Binary Phase Shift Keying B - A C K Block Acknowledgment C C A Channel Clearance Assessment C T A Channel Allocation Time Access C T S Clear To Send C S M A / C A Carrier Sense Mult iple Access and Collision Avoidance C A P Contention Access Period List of Acronyms C D F Cumulative Distribution Function C R C Cyclic Redundancy Check D R P Distributed Reserved Protocol D S - U W B Direct Sequence Ul t ra Wide Band DS Direct Sequence E C M A European Computer Manufacturers Association F I F O First In First Out F C S Frame Checksum Geo Geometric G General G T S Guaranteed Time Slot I E E E Institute of Electrical and Electronics Engineers IFS Inter Frame Spacing Imm-Ack Immediate Acknowledgment M A C Medium Access Control M A C A Medium Access Code Assignment List of Acronyms M A S Medium Access Slot M IFS Minimum Inter Frame Spacing M A P Markovian Arrival Process M Markovian M A C A Multiple Access Code Assignment M A P Markovian Arrival Process M G M Matr ix Geometric Method M T S Management Time Slot N A V Network Allocation Vector N o - A C K No Acknowledgment P A M Pulse Amplitude Modulation P C A Priorit ized Contention Access P H Phase Type Distribution P N C Piconet Coordinator pmf Probabil ity mass function P P M Pulse Position Modulation List of Acronyms P S K Phase Shift Keying QoS Quality of Service RTS Request To Send R E S Response SIFS Short Inter Frame Spacing T H - U W B Time Hopping Ul t ra Wide Band T X O P Transmission Opportunity T H S Time Hopping Sequence U W B Ult ra Wide Band VI Video V O Voice W P A N Wireless Personal Area Network xiv List of Symbols <g> Kronecker product (a, T) Phase type representation for the arrival process. AQRP Probability transition matrix for the group of states in which there is an increase by one in the number of the DRP packets. A®RP Probability transition matrix for the group of states in which there is no change in the number of the DRP packets. A^RP Probability transition matrix for the group of states in which there is a decrease by one in the number of the DRP packets. A P C A Probability transition matrix for the group of states in which there is an increase by one in the number of the P C A packets. A P C A Probability transition matrix for the group of states in which there is no change in the number of the P C A packets. A P C A Probability transition matrix for the group of states in which there is a decrease by one in the number of the P C A packets. xv List of Symbols (/?, S) Phase type representation for the service time distribution. B Probability transition matrix for the initial states in which there is no change in the number of the D R P packets. NB Maximum number of the time slots within the beacon period. C Probability transition matrix for the initial states in which there is an increase by one in the number of the D R P packets. A _ Group of states in which the server is within the beacon period. A T Group of states in which the server is within the D R P period. A c Group of states in which the server is within the P C A period. Dio Probability generator matrix of no D R P packet arrival to the system. D\\ Probability generator matrix of one D R P packet arrival to the system. D2o Probability generator matrix of no P C A packet arrival to the system. D21 Probability generator matrix of one P C A packet arrival to the system. xvi List 'of Symbols E Probability transition matrix for the initial states in which there is a decrease by one in the number of the DRP packets. i Number of the DRP packets in the system. / Identity matrix / A matrix that can be defined using / j Number of the P C A packets in the system ki Phase of arrival for DRP packets ki Phase of arrival for P C A packets I Number of the DRP time slots Mb/s Mega bits per second MAP/PHY/l A queueing system that has an inter-arrival time distribu-tion of a M A P and a service time with P H Y distribution and one server. N8 Number of the bit iterations in TH-UWB NC Number of the time intervals in a chip NQ Maximum number of the time slots within the P C A period NT Maximum number of the time slots within the DRP period xvii List of Symbols P Probability transition matrix Q Probability transition matrix r Number of the beacon time slots Tf Length of the Ns intervals u Number of the P C A time slots Wa Probability of waiting more than a time slots Xi Steady state probability of having i packets in the system xfu Steady state probability of having i packets in the system during the P C A period in time slot number u. xju Steady state probability of having i packets in the system during the DRP period in time slot number u. xfu Steady state probability of having i packets in the system during the beacon period in time slot number u. XDRP Transition probability matrix including changes to the P C A packets during the P C A period when the outer counter is the DRP queue. XPCA Transition probability matrix including changes to the DRP packets during the P C A period when the outer counter is xviii List of Symbols the P C A queue. Y Transition probability matrix including changes to the P C A queue during the beacon period and DRP period when the outer counter is the DRP queue. Y Transition probability matrix showing changes to the DRP queue when the outer counter is the P C A queue. Yk Transition probability matrix including changes to the DRP queue during DRP period when the outer counter is the P C A queue. zfu Steady state probability of finding i packets in front of a tagged packet during the beacon period. zj Steady state probability of finding i packets in front of a tagged packet during, the DRP period. zfu Steady state probability of finding i packets in front of a tagged packet during the P C A period. Zj Steady state probability of seeing j packets in front of a tagged packet. xix Acknowledgements First, I would like to thank my supervisor Professor Vincent Wong for his invaluable guidance. Not only has he taught me a great deal technically but also I have found his other lessons especially in time management as an engineer equally important. His commitment have shaped my perspective and I would like to express my most gratitude for his support throughout these two years. I would also like to thank Professor A . Al fa for his great technical support and hospi-tality during my visit to University of Manitoba. I really feel indebted for what I learnt from him and his publications. I would also like to thank Professor Victor Leung and Professor Sathish Gopalakrish-nan for serving on my dissertation committee. I would like to thank N S E R C to support this project financially. One of great things of working with Professor Wong is having talented students as your group-mate. I would like to thank Yuxia L in for his great knowledge of coding and his patient in answering my endless questions. Thanks to A l i Soltanzadeh, Enrique Stevens-Navarro, Amir Hamed Mohsenian-Rad, Shahab Moradi, and Mani Malekesmaeili for being so kind to me during this period. xx Acknowledgements Hard periods make good friends as remarkable. Thanks to Elham for her support. To A l i for putting up with me in every single minute, without him surviving to the end of this way was not possible. A t last, I would like to dedicate this thesis to my beloved family. To mom and dad, for your patience and unwavering support. I feel so lucky to have you as my parents. Your unconditional love and willingness to do anything for your children is beyond remarkable. I am so thankful to both of you. To Nastaran, thank you for all of your understanding and supports throughout my life. You are more than a sister to me. xxi Chapter 1 Introduction The Ul t ra Wideband (UWB) technology, which allows data to be transmitted via short duration pulses with very high instantaneous bandwidth, is an emerging technology for short range wireless communications in wireless personal area networks (WPANs) . The U W B systems can support either high data rate transmission (above 100 Mbps) or low data rate transmission. The low data rate option is standardized within the I E E E 802.15.4a standard [1]. The high data rate option was originally part of I E E E 802.15.3a task group. The group was disbanded due to disputes between industry groups. The high rate option was standardized by the European Computer Manufacturers Associa-tion ( E C M A ) International as the ECMA-368 standard [1]. The ECMA-368 standard defines the physical (PHY) and media access control (MAC) layers for high rate W P A N s . The M A C protocol in ECMA-368 has a superframe struc-ture. Each superframe is divided into three different time periods. The beacon period is used for control purposes. The distributed reserved protocol (DRP) period allows devices to reserve bandwidth for data transmission. The P C A (prioritized contention access) pe-riod supports contention-based access between different traffic classes. In this thesis, we focus on evaluating the performance of the ECMA-368 M A C protocol. 1 Chapter f. Introduction 1.1 Contributions The contributions of this thesis are as follows: • We propose a M A P / P H Y / 1 queueing system to evaluate the performance of the ECMA-368 M A C protocol. The model considers various input parameters including the packet arrival rates under the P C A and DRP periods, packet collision due to channel contention, the number of devices in the system, and the buffer size for the packets waiting in the queue. • By using the Matrix Geometric Method (MGM), we derive the number of packets in the system and the cumulative distribution function of the waiting time of the packets in the system. • We validate the correctness of our analytical model via simulations. We create the ECMA-368 M A C module by using the OPNET simulator. Analytical and simulation results are presented under different scenarios. Overall, this thesis provides a comprehensive investigation and analysis of the E C M A -368 M A C protocol performance in UWB-based ad hoc networks. 1.2 Structure of this report This report is organized as follows: In Chapter 2, we first summarize the physical prop-erties of the UWB technology and the ECMA-368 M A C protocol. We then describe the Chapter 1. Introduction some of the related work on UWB-based M A C protocols. In Chapter 3, we describe the proposed analytical model and the M G M , which is used to solve the Markov chain for the analytical model. In Chapter 4, results from the analytical model and validation of the model with simulation results are presented. Chapter 5 summarizes the main contributions and conclusions, and indicates possible future work. 3 Chapter 2 Background and Related Work In this chapter, we first give an overview on the physical layer of the existing UWB standards and then describe the wireless standard of ECMA-368 for both physical layer and M A C layer. We use Markov chains and the Matrix Geometric Method (MGM) to model the ECMA-368 M A C in Chapter 3; hence we give a brief description of both Markov chain and M G M in this chapter. At the end, we discuss different M A C models proposed for UWB-based ad-hoc networks. 2.1 U W B UWB is a term indicating the wide band signals that satisfy the following definition [3]: "The bandwidth of the system should be greater than 500 GHz or 20% more than the center frequency". Common methods used for the modulation of UWB-based systems are: Pulse Position Modulation (PPM), Pulse Amplitude Modulation (PAM), Binary Phase Shift Keying Modulation (BPSK). In P P M , for transmitting 0, the impulse starts at the beginning of the chip time. To transmit 1, the signal has with a delay from the start of the chip time. In P A M , the amplitude of the signal is used to transmit bits. Implementing m-level P A M is also possible. In PSK, different phases are used to transmit 4 Chapter 2. Background and Related Work bits. For example, for 0, we use a zero degree phase. For 1, we use a 180 degrees shift in phase of the signal to transmit the bit. 2.1.1 Different Access Methods There are two main access methods used in the UWB based systems: single access and multi-band access. Single Band U W B The single band systems use both time-hopping spread spectrum impulse radio (TH-UWB) and direct sequence spread spectrum impulse radio (DS-UWB). In TH-UWB, the transmission time of the pulses are determined from a pseudo random sequence. In DS-UWB, each flow uses a pseudo random sequence to spread information bits across the band. Time-Hopping (TH): In TH-UWB, the transmitter spreads a bit over iV s intervals, each with a' time length of Tf; therefore the data transmission rate is j p j r . The assigned pseudo random code determines the position of the pulse within each interval. Direct Sequence (DS): In DS-UWB, the transmitter spreads a bit over one interval with time length Tf. To spread the data, the transmitter uses a pseudo random spreading code with length Ns and chip duration Tc [4] [5]. 5 Chapter 2. Background and Related Work Multi-band Orthogonal Frequency Division Multiplexing (MB-OFDM) In M B - O F D M , the spectrum is divided into sub-bands using orthogonal frequency divi-sion multiplexing (OFDM). In M B - O F D M , the spectrum between 3.1 GHz to 10.6 GHz is divided into 14 bands, each with a 528 MHz bandwidth. Information is transmitted using O F D M and frequency hopping patterns are used for channelization. In each band, there are 122 sub-carriers; 100 sub-carriers are allocated for data, 12 sub-carriers as pilot which are used in channel estimation, and 10 sub-carriers as the guard interval that provides sufficient time for switching between different channels. One of the main advantages of M B - O F D M is its capability for coexistence with other standards via the use of channelization. For example, in an area where an 802.11a network is present, the second group band can be avoided for coexistence. Another advantage of channelization is robustness against the multi-path fading. Since the idea of dividing the channel into smaller portions reduces the amount of Inter-Symbol Interference (ISI) within each band. 2.2 E C M A - 3 6 8 Standard The physical layer of ECMA-368 is based on UWB technology. The spectrum is spread between 3.1 - 10.6 GHz, and it can support data rates up to 480 Mb/s [1]. A brief de-scription of the physical layer and M A C layer of ECMA-368 are provided in the following sections. 6 Chapter 2. Background and Related Work i B a n d * l B o n d #2 B a n d • 3 B a n d * 4 B a n d * 5 B o n d . tb B a n d #7 B a n d #8 B o n d #9 B o n d #10 B o n d #11 B a n d #12 B o n d »13 B a n d #14 / i ' / \ J ' i 4 i " / ' i ' f 3432 M H z 3<)fto M H z 4 4 8 8 M H z 5016 M H z 5544 M H z 6072 M H z 6 6 0 0 M H z 71 a s M H z 7656 M H z 8184 M H z 8712 M H z 9 2 4 0 M H z 9768 M H z 10296 M H z Figure 2.1: Spectrum division in the physical layer of ECMA-368. 2.2.1 Physical layer of ECMA-368 In the ECMA-368 standard, the channel is divided into 14 bands. Each band is 528 MHz. The first 12 bands are divided into 4 groups, each of which contains 3 bands. The fifth group consists of 2 bands. This standard suggests M B - O F D M for data transmission. Figure 2.1 shows the channel division for the physical layer of ECMA-368. The data rates supported by the standard are: 53.3 Mb/s, 80 Mb/s, 106.7 Mb/s, 160 Mb/s, 200 Mb/s, 320 Mb/s, 400 Mb/s, 480 Mb/s. The physical layer uses forward error correction (FEC) to correct the received data. 2.2.2 Superframe Another feature of ECMA-368 is communication by means of a superframe. Time is divided into fixed periods of 65 ms called a superframe. The superframe is divided into smaller time slots. There are 256 time slots within each superframe. Transmission takes place at the begining of each time slot. Each superframe consists of two parts: beacon and data. The structure of a superframe is presented in the Figure 2.2. 7 Chapter 2. Background and Related Work Beacon Period Start Time / k- Superframe (fjxed,65 ms) Beacon Period (Variable) — i Data Period (Variable) Data Data -77 Data \ 1 / Beacon Slots (Fixed Length) Medium Access Slots (Fixed Length) Figure 2.2: Structure of a superframe [1] Beacon Period Information in the beacon period can be heard by all the nodes within a group. Thus, all nodes are aware of each other. The nodes can negotiate for the reservation of the channel during this period. Nodes can inform other nodes that they are ready to receive data during a specific time slot or announce when they are going to hibernate. Each superframe starts with a number of beacon slots. The number of beacon slots varies but is limited to mBeaconSlotLength (maximum number of beacon slots). Each active device transmits beacon signals during the beacon period and can hear other nodes' beacon signals as well. Transmitting a beacon signal takes place at the beginning of a beacon time slot and lasts for a specific amount of time so that there is always a guard time between two beacon signals. A device interprets beacon slot number x as empty if, during the previous superframes, beacon slot number x is not sensed as occupied. Otherwise, the tagged beacon slot is interpreted as being occupied. 8 Chapter 2. Background and Related Work During the beacon period, each device can announce its own beacon slot number and also the beacon slots that were occupied by other active devices in the previous superframe. When a device wants to join a network, it listens to the channel for a superframe time length. If it does not hear any beacon signals, it will initiate its own superframe. Otherwise, it will transmit a beacon signal a few time slots after the last occupied beacon time slot. If a device detects a collision in its beacon slot, it transmits another beacon signal immediately after the last occupied beacon slot. If a device does not receive any beacon signal from its neighbors, it will use device information from the previous superframe. The device deletes information about its neighbors if this situation remains for several superframes. In case of receiving the Beacon Period Occupied Information Element (BPOIE) show-ing that there is no change in the mapping of the beacon period for several superframes and the existence of an empty beacon slot between the previous beacon slot and the tagged device beacon slot, a device can move its beacon slot and reduce the beacon period length. Data Period During the data period, each node tries to send data packets according to the specification in the ECMA-368 standard. We will discuss this operation in detail in Section 2.2.5. 9 Chapter 2. Background and Related Work 2.3 Information Element (IE) Each device in the network can be identified by others through of beacon signals. Since there is no infrastructure, data communication occurs by means of Information Elements (IE). Different structures of IEs have different usage. For instance, an IE to make a reservation is different from an IE to announce that a node is going to hibernate. IEs can be included in the beacon frames. An IE which is located in the beacon frame belongs to that superframe and not the previous superframes. Each device can ask for the IE of another device directly with a probe command frame in its beacon slot. 2 .3 .1 M A C L a y e r a n d P h y s i c a l L a y e r I n f o r m a t i o n E x c h a n g e The M A C layer in ECMA-368 makes some assumptions about what it can obtain from the physical layer. Some of the assumptions are: • Exchanging data packets with the physical layer. • Error correction in header and Forward Error Correction (FEC) are provided by the physical layer. The F E C is a convolutional code with code rates of 1/2, 1/3, 5/8, 3/4. • Recognizing whether the channel is busy or idle. Alfa et al. [6] say that "The start of a valid O F D M transmission at a receiver level equal to or greater than the minimum sensitivity for a 53.3 Mb/s transmission (-80.8 dBm) shall cause Clear Channel Assessment (CCA) to indicate that the channel is busy with a probability 10 Chapter 2. Background and Related Work of 90%." • Time stamp in case of supporting M A C range measurement (the range that devices can hear each other). • Packet ordering. In single frame transmission, the M A C has complete control. In burst transmission mode, M A C controls the first frame and the physical layer handles of the other frames in the batch. The services provided by the M A C layer are as follows: • Communication between devices within the network. • Access to the channel with two methods: Distributed Reserved Protocol (DRP), and Prioritized Contention Access (PCA). • Synchronization between devices. • Mobility and interference control. • Power management. • Security by means of encryption and authentication. • Localization facilities. Two adjacent networks can join and create a larger network called an extended beacon group. To create an extended beacon group, both groups should synchronize with each 11 Chapter 2. Background and Related Work User Priority AC Designation 1 A C - B K Background 2 A C - B K Background 0 A C - B E Best Effort 3 A C - B E Best Effort 4 AC-VI Video 5 AC-VI Video 6 AC-VO Voice 7 AC-VO Voice Table 2 . 1 : Different access categories [2] other. In the case of joining two groups, the M A C layer handles the situations that may cause conflict in beacon transmission. Even when there is no extended beacon group, each device remains silent during the beacon slot of other devices. Prioritized Contention Access (PCA) During the P C A period, all active nodes within the network that have packets to send try to access the channel using the Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA) . The access technique during the P C A is similar to 802.lie [5]. Eight different Access Categories (ACs) are supported in ECMA-368 (Table 2-2). Service differentiation is supported by means of different backoff intervals and different Arbitrary Inter Frame Arrival (AIFS). For the AC with higher priority, the backoff counter chooses a smaller interval for the backoff. Therefore, the countdown process finishes sooner when compared to an AC with lower priority. Another way is to use smaller 12 Chapter 2. Background and Related Work Reservation Type Designation Hard T ime slot is exclusively reserved for the D R P . Soft T i m e slot is reserved for the D R P , but it can be used for P C A if the D R P job completed before the end of D R P period. Private T i m e slot is reserved for the private data communication between two nodes. Al i en T ime slot is reserved wi th respect to the beacon signals of the adjacent network. P C A N o reservation Table 2.2: User Priority to access category mapping AIFS for the AC with higher priority in order to increase its probability of accessing the channel. Distributed Reserved Protocol (DRP) The DRP period provides contention-free access to the channel for the active nodes within the network. This feature in ECMA-368 is especially suitable for real-time services such as video streaming applications, which are sensitive to delay. During the beacon period, each node announces time slots for the DRP access. There are different types of reservation. When a device wants to send data over reserved time slots, the first step is to request the intended time slots. Negotiation takes place during the beacon period. Each node within the network can hear the beacon signals by other nodes. Therefore, a node can determine the empty time slots from the beacon signals of other nodes. The request for reservation is sent during the beacon slot and the destination (or destinations in case of multicast) replies during the current superframe or the next superframe. If the destination responds during the current superframe, it can answer either in-band or out-13 Chapter 2. Background and Related Work band. The former means that the destination answers during the data period within the current reserved slots. The latter means that the destination answers during the beacon period of the current superframe. Based on the different kinds of reservation stated in Table 2.2, negotiation on reserved time slots can be different. For instance, in case of hard reservation, other nodes cannot negotiate on the reserved time slot. If a soft reservation is used, then other nodes can negotiate on the reserved time slots of the current superframe. In other words, if the data transmission ends before the end of the DRP, the remaining time slots can be used for a different type of reservation or even for the PCA. If a frame sends an Availability IE indicating that it is not available during a specific Medium Access Slot (MAS), other devices cannot use that tagged MAS for PCA. 2.3.2 Inter Frame Spacing There are three different Inter Frame Spacing (IFS) supported in ECMA-368: Minimum Inter Frame Spacing (MIFS) When a node transmits data in batch, there is a Minimum Inter Frame Spacing between each two data frames. Short Inter Frame Spacing (SIFS) After completion of each data frame transmis-sion, another frame cannot be sent before the SIFS. Arbitrary Inter Frame Spacing (AIFS) When a device wants to transmit a frame, it has to wait for AIFS after sensing that the channel is idle and then start trans-14 Chapter 2. Background and Related Work M A C Parameters Value mAIFS[AC-BK] 512 pus rriAIFS [AC-BE] 512 us mAIFS[AC-VI] 1024 pis mAIFS[AC-VO] 256 JJLS Table 2.3: Some of the M A C layer parameters [2]. mission. If the device is performing a backoff, then the countdown process starts or resumes after the channel is sensed idle for AIFS. The time length of SIFS, MIFS, and AIFS are listed in the Table 2.3. 2.3.3 A C K Policies Immediate A C K (Imm-ACK) An A C K frame is sent according to a packet arrival if in the M A C header of the transmitted frame the A C K policy is set to Imm-ACK. This policy is used for every unicast transmission. No-ACK If the sender indicates the No-Ack policy in its M A C header, the destination does not send an A C K after receiving the frame. The sender continues to transmit data frames regardless of whether the previous transmission was successful or not. Block A C K Recipient transmits an A C K frame after receiving a specific amount of data frames from the transmitter. After receiving the specific amount of data frames determined by the destination according to its buffer capacity, the destination sends an A C K indicating the frames that have been received successfully. The sender can 15 Chapter 2. Background and Related Work retransmit corrupted frames again. 2.3.4 Network Allocation Vector (NAV) A device that transmits during the P C A period keeps track of the time that its neighbors occupy the channel in a vector called the Network Allocation Vector (NAV). Each device updates the duration of using the channel in its M A C header. Therefore, other devices can update the NAV values according to the duration in the M A C header. The channel is sensed as busy by the M A C layer in two ways: • The physical layer indicates that the channel is busy using CCA. • The amount in NAV is not equal to zero. 2.3.5 Transmission Opportunity (TXOP) In ECMA-368, each AC has its own AIFS [AC]. After a device senses channel idle for AIFS [AC] time length, it starts competing for the channel to gain a transmission oppor-tunity (TXOP). The maximum amount of time a device can use a channel when it gains access to the channel is called TXOP. A device obtains a T X O P when: • It has some frames to transmit. • The backoff counter reaches zero for that AC. • The channel is empty for AIFS [AC]. 16 Chapter 2. Background and Related Work • Higher priority traffic classes do not have packets to transmit. When a device wins a TXOP, it can transmit only within that TXOP. If it has more packets to send, it has to obtain another TXOP. After obtaining a TXOP, the device goes through the following steps [1]: • The T X O P owner transmits the first data frame at the beginning of the TXOP. • After transmitting the first data frame with No-ACK or Block-ACK policy, the T X O P owner waits for SIFS or MIFS to send the next data frame. • The recipient sends an Imm-ACK or B - A C K or Request To Send (RTS) with a SIFS delay after receiving a frame with Imm-ACK or Block-ACK policy or Clear To Send (CTS) frame. • The T X O P owner sends the next frame with a SIFS delay after a CTS or a frame with Imm-ACK or Block-ACK policy • If a destination receives a frame with the correct Header CheckSum (HCS) but incorrect Frame CheckSum (FCS), retransmission of the frame is optional for the T X O P owner. In the following section, we will go through the mathematical background needed to develop our model. 17 Chapter 2. Background and Related Work 2.4 Phase Type Distr ibution (PH) Consider a Markov chain of n transient states and one absorbing state. The time to absorption is a random variable with a P H distribution. A P H distribution can be represented by (a, T) [7], where a is the initial probabilities of the transient states and T is the matrix of probability transitions of the transient states. Al l the characteristics of a distribution can be defined with these two matrices. The probability transition matrix P is as follows: [ T Tn 1 (2.1) P = T0 0 1 where To is the column vector of transition probabilities to the absorbing state. T 0 is defined as follows: T 0 = 1 - Tl (2.2) where 1 is a column vector with all entries equal to one and it has the same dimension of T. Many distributions can be interpreted as a P H distribution in the discrete time domain. For instance, the exponential distribution with parameter A can be represented by a PH distribution of one phase. The matrices (cx,T) are as follows: T=[X], , (2.3) a = [l], As another example, assume an Erlang distribution, which is commonly used in modeling communication systems, with a shape parameter k and a rate parameter A. The P H 18 Chapter 2. Background and Related Work representation of the Erlang distribution T is a k x k matrix as follows (assume k = 4): T = a A A 0 0 0 A A 0 0 0 A A 0 0 0 A 1 0 0 0 (2-4) (2.5) The use of a P H distribution simplifies computations. Consider the situation when a sys-tem is allowed to buffer an infinite number of packets, the probability transition matrix defined for a Markov chain has an infinite dimension. Finding the steady state probabili-ties for that system is not trivial. However, by using the PH distribution and the Matrix Geometric Method (MGM), many parameters of the system such as the length of the queue and the waiting time distribution can be determined. Almost every distribution can be transformed to a PH distribution [7]. In a geometric distribution, for example, every trial has a success probability of p and a failure probabil-ity of q = 1 — p, it can be represented as a P H distribution with one phase. The matrices a and T are as follows: a=[l], T0 = [!-<?]. (2.6) (2.7) (2.8) A deterministic distribution with n transient phases can be represented as a PH distri-19 Chapter 2. Background and Related Work bution: a 0 I 0 0 T a>i a2 ... an (2.9) (2.10) where / is an identity matrix. This way of representing P H distribution is useful to model a fixed time visit of the server to a queue, or a deterministic service type. 2.5 Markovian Ar r iva l Process ( M A P ) In discrete Markovian Arrival Process, the arrivals are governed by an underlying m-state Markov chain having probability <Xy and a;, 1 < i, j < m, with a transition from state i to state j without an arrival, and having probability Ay, 1 < i,j < m, with a transition from state i to j with an arrival. DQ = where a,- can be calculated as follows: An A12 A21 A22 -Oil O12 o2\ -c*2 (2.11) (2.12) a (2.13) Our arrival process is described by a Markovian arrival process (MAP) represented by 20 Chapter 2. Background and Related Work Figure 2.3: State diagram of a two-phase M A P . four matrices n x n matrices Dw, Dn, D 2 n , and D2i. The elements (Dw)ij and (-Dn)y represent transitions from state i to j with no arrival and one arrival, respectively, at the D R P queue and (Z?2o)ij a n d {D2i)ij represent transitions from state i to j with no arrival and one arrival, respectively, at the P C A queue. The matrix D = D\o + Dn + A20 + D21 is stochastic. Let TT be defined as the solution to TT = TTD, TTI, then Ai = TTDU^ and A 2 = TTD2I1 are the respective arrival rates to the D R P and P C A queues. 21 Chapter 2. Background and Related Work 2.6 M a t r i x Geometric Method ( M G M ) Consider a M A P / P H / 1 system. The probability transition matrix P of the system is a Quasi Birth Death process (QBD) and is defined as follows: B C P = E A\ A0 A2 Ai A0 (2.14) where A2, A\, A0, B, C,and E are matrix blocks which are determined according to the characteristics of the system such as the arrival process, service time distribution, and the scenario that we are implementing for the system. The number of rows is equal to number of packets in the system (i.e, having a buffer with size L means that number of rows is equal to L). As an example, consider a Geo/Geo/ l / /^ queueing system where packets arrive in the system according to a geometric distribution with probability of pa and qa = 1 — pa. The server has a service rate of ps according to a geometric distribution and the maximum amount of packets in the system is equal to K. The transition probability matrix P for 22 Chapter 2. Background and Related Work this system is as follows: P = Pa QaPs QaQs + PaPs PaQs QaPs QaQs + PaPs PaQs (2.15) QaPs QaQs + PaPs The number of rows is equal to K + 1. The block matrices B, C, E, A2, A\, and A0 are as follows: B=[qa], C=\pa], E=[qaPs], (2.16) A2 = [qaPs], Ai = [qaqs+PaPs}, Ao = \paqs], where A2 represents the probability of decrease in number of packets in the system, Ai represents the probability of no change in the number of packets in the system, and AQ represents an increase in the number of the packets in the system. The matrix B is the probability matrix of zero packets in the system. Matrix C is the probability of having an increase in the number of the packets in the system given that there is no packet in the system [6]. Initially, we assume that all the above matrices are known. Once the steady state probabilities of the Markov chain have been determined, other system parameters such 23 Chapter 2. Background and Related Work as the number of packets in the system and the waiting time distribution can also be calculated [8]. One way to find the steady state probabilities of an infinite size Markov chain is to use the M G M . The concept of M G M is to use smaller matrix blocks such as A0, A\, and A2 instead of manipulating the matrix P for calculation. Although the matrices AQ, Ai, A2 may be large, their dimensions are much smaller than the matrix P. The matrix A = Ax + A2 + A0 is a stochastic matrix. The Markov chain can be solved by M G M if: uA2l < ITA01, (2-17) where ir is the steady state probability of matrix A and is calculated from: n = nA, TT1 = 1. (2-18) If the stability condition in (2.17) is satisfied, then the nonnegative matrix R can be calculated as follows: R = A0 + RA1 + R2A2. (2.19) The matrix R has a spectral radius less than one [6] [7] [8]. The spectral radius of a matrix is defined as the largest eigenvalue of that matrix. To ensure that the system is stable, there is another matrix G that can be calculated as follows: G = A2 + AlG + A2G2. (2.20) The matrix G is stochastic if the system is stable. From M G M , we know that [6] [7]: Xi+i = ^ i ? = xxR\ i = l ,2 , . . . ( 2 - 2 1 ) 24 Chapter 2. Background and Related Work B[R] = (2.22) where Xj denotes the steady state probability vector of having i packets in the system. To determine x i , we have to form another matrix B[R], which is a function of the matrix R. r B C E A1 + RA2 Let assume [yn y i ] be the eigenvector of B[R] corresponding to the eigenvalue of 1. yn and yi are the row vectors with the same dimension as B and E, respectively. Since B[R) is a stochastic matrix, it has an eigenvalue equal to one. X i and xn can be calculated as follows: x 0 = J T V O , (2.23) xi = y V i , (2.24) y = y 0 i + y i ( / - J R ) - 1 i , (2.25) We can find other steady state probabilities from equation (2.22). The x* vectors are the steady state probabilities matrix P. Using matrix B[R], we find a shorter form of vector X j , because is the steady state probability vector of matrix P and has the same dimension as matrix P. Using B[R] we estimate a smaller size matrix for P, so the Xj that we find from B[R] has a smaller size compared to the actual steady state probability vectors obtained from matrix P directly. 25 Chapter 2. Background and Related Work 2.7 Related Work In this section, we describe some related work on M A C protocols in UWB-based systems. We first describe the proposed models and algorithms for the U W B system. Then, we describe the models that use M G M to model the communication systems. Proposed Models for MAC Layer The long acquisition time in high-rate UWB can affect the performance of the M A C layer because of the high overhead it poses on the network. Lu et al. [9], propose a M A C protocol that sends packets in a batch or burst traffic instead of sending each packet individually. They showed an improvement in the performance of the M A C layer. Lu et al. [10] proposed a M / G / l / K queueing system. The arrival traffic has a Poisson distribution with rate A and for the service time distribution is calculated based on the enhancement of the M A C layer proposed earlier in [9]. For a network of N nodes, a queueing system with A'' queues in each node was considered [9]. Packets are assumed to be from one access category, so there is no priority class in the system and packets are classified according to their destination address. Therefore, there are N — 1 queues and one queue for buffering broadcast packets. Merz et al. [11] proposed a new model for UWB M A C that adjusts the rate according to the interference level. In the conventional method, when a node transmits, other nodes within the exclusion region stay silent. Using a smaller exclusion region can increase the opportunity of transmitting simultaneously. 26 Chapter 2. Background and Related Work Merz et al. [11] focused on the rate adjustment according to a peer-to-peer conversa-tion between sender and receiver. Assume that RQ > Ri > R2 > • • • > RN are the set of rates that channel coding can provide. To increase the rate, the sender can decrease the redundancy and form a rate subset which has rates higher than the main set. When a node wants to transmit, it attaches a Cyclic Redundancy Check (CRC) with the lowest rate, RN, to the packet and sends it to the receiver. If the receiver is capable of decoding the packet, it estimates the highest rate, Ri, that it can receive and decode the data and put it in the A C K packet that it sends back to the sender with rate RN- The sender de-codes the A C K packet and adjusts the transmission rate to R{i+2) where Ri > RN- When the sender times out on a specific packet, it decreases the rate to the min(2 x Ri, RN)-Another improvement suggested in [11] is to use private M A C peer-to-peer instead of using a large exclusive region. Due to the fact that UWB physical layer cannot imple-ment the C S M A / C A , the idea of using a private peer-to-peer coordination can solve the problem. In the proposed method, each pair of nodes has a private TH-sequence. There is a common TH-sequence that all nodes can hear it. The sender transmits the Request (REQ) with the public TH-sequence of the channel with rate RN- The receiver transmits the Response (RES) including the estimated rate, Ri, with the private TH-sequence. If another node wants to send to the same receiver, it sends a REQ and waits for a RES. If it does not receive any RES within a fixed time, it waits for the idle signal from the receiver. Simulation results indicate that the proposed model is better than some other protocols that are based on power control or exclusion-based protocols. 27 Chapter 2. Background and Related Work In [12], Shen et al. summarized the features of the UWB-based M A C on three different aspects: multiple access, overhead reduction, and resource allocation. They started from the differences between the M A C in an UWB-based system and 802.11. One of the main differences is the exclusive region. In the UWB-based system, the exclusive region is only around the receiver and not the sender. In 802.11, it is both around the sender and receiver. That is, the exclusive region is mutual, meaning that each node that can hear a communication will remain silent. In [12], Shen et al. classified the code assignment for both Direct Sequence (DS) and Time Hopping Sequence (THS) as follows: • Receiver-based code: each node is assigned a unique receiving code. Therefore each node only needs to listen for the traffic that used its code. When different senders try to send to a specific receiver, collision will occur. • Common code: all the transmissions are assigned a common code. The address information is included in the packet header, so each node can determine whether it is the intended recipient. • Transmitter-based code: each node is assigned a unique transmitting code. The advantage of this code is that several transmitters can transmit simultaneously. There is another way of combining these code to get a better result: M A C A stands for multiple access code assignment. In M A C A / C T , each node is assigned a sending code, and a common code is assigned to RTS/CTS. In M A C A / R T , each node is assigned a sending code and a receiving code. The RTS is sent with the receiving code while the 28 Chapter 2. Background and Related Work CTS and data are sent with the sending code. The other way for the multiple access to the channel is the interference mitigation method. It is normally done in the physical layer. In the overhead reduction part, Shen et al. described two reasons that cause the overhead in the system. One of them is the Imm-Ack and the other one is the long acquisition time. Imm-Ack can increase the amount of overhead in the system, so instead of using the Imm-Ack, Block-Ack can solve the problem. The second cause of overhead is the long acquisition time. A good way to reduce the amount of overhead caused by the acquisition time is to enlarge the packet size by putting the data packets in one batch. Although having large packet size may cause a large packetization delay, there is a compromise between the delay and the overhead. Another way to decrease the acquisition time is to maintain the link after the transmission has ended. In this way, the control packets can be sent when the channel is idle. The disadvantage of this method is the power waste and also an increase in the interference due to the longer transmission time. From the resource allocation point of view, Shen et al. [12] discussed three aspects: power allocation, rate allocation, and cross layer design. They emphasised on the fact that in case of transmission the sender should transmit with maximum power. Since controlling the power is not enough to eliminate the interference, rate control is another suggested way to decrease the level of interference. The cross layer design based on the positioning which is one of the features of the UWB helps some simplification in M A C 29 Chapter 2. Background and Related Work design. In [13], Chu et al. proposed a new algorithm for rate and power allocation. In classic power and rate allocation approach, each new call regardless of the QoS receive the minimum rate and maximum power and call admission is based on the existing links. In the proposed adaptive algorithm, the power and rate allocation are based on the existing links and also the estimation of the future requests for QoS. Tarchi et al. in [14] focus their research on the 802.15.3a and improving the per-formance of the M A C layer for multimedia traffic. In 802.15.3a, a Piconet Coordinator (PNC) controls the timing of the network. Communication between nodes is based on the superframe structure. Each superframe start with a beacon period and then Contention Access Period (CAP) followed by a Channel Allocation Time Access (CTA). During the CAP, all the nodes use C S M A / C A to access to the channel. The superframe length is not fixed and varies with the length of the C A P and CTA. Each node in the piconet updates its status including its ID number and the amount of traffic it has during the beacon period. Therefore, PNC is aware of the existing traffic in the network and it can use this information to allocate time slots during the CTA. There are two different time allocations during the CTA: Guaranteed Time Slot (GTS) and Management Time Slot (MTS). During GTS, some time slots are reserved for specific peers. During the MTS, the complete duration is reserved until the end of the communication on a certain link. In the conventional way of the time allocation, the PNC first allocates all the GTS and then allocates time for the MTS. In the proposed allocation algorithm, the PNC allocates 30 Chapter 2. Background and Related Work MTS according to the traffic in each node. The performance results show improvement in throughput and the delay that each pair of nodes experience during the peer to peer data communication. In [15], Radunovic et al. proposed a scheduling scheme for M A C with power man-agement. Performance metrics are derived and simulations are presented. In [16], Liu et al. proposed two algorithms to enhance the performance of the M A C layer. The first algorithm is called the proportional allocation algorithm. The flows which do not inter-fere with each other are placed in one group. A time slot is allocated to each group, so each group at least has one time slot. Since the flows in one group can transmit simul-taneously, each flow at least has an allocated time slot. The second algorithm is called the repeating allocation algorithm. In the repeating allocation algorithm, the number of time slots allocated to each flow denoted by 0/. When we want to assign a time slot to a flow, we first randomly choose a flow with minimal </>/. Then, we make group with adding flows that do not conflict with the first flow. Numerical results show improvement in M A C performance. In [17], Mishra et al. proposed a Cross Layer Design (CLD) algorithm for the back-off process to improve the performance of 802.15.4 M A C . In the proposed algorithm, the back-off stage will be drawn randomly from a set of disjoint intervals. Performance evaluation shows that the CLD-802.15.4 throughput is 69% higher than the basic 802.15.4 and 154% higher in terms of energy efficiency. In [18], Merz et al. studied the effect of rate adaptation, power adoption, mutual 31 Chapter 2. Background and Related Work exclusion, power saving modes and interference mitigation. To study the effect of energy, Merz et al. proposed a quanta vector to present the usage of energy. The results from the studies show that the energy consumption and rate efficiency are not affected with power control. The findings in [18] is consistent with the work in [9] and [10]. Models Based on M G M In [19], Fallahi et al. modeled the M A C layer of the network as a queuing system of M A P / P H / 1 . The traffic arrives at each node according to a MAP. The service time distribution is a PH distribution. The proposed Markov chain in [19] is different from [20]. The state space proposed in [19] is divided into two parts. States which the server is in vacation and states which the server is in active mode. Each state keeps track of the number of packets in the system, arrival phase, service phase and the vacation phase. To find the probability transition matrix, they used M G M . In [19], Fallah et al. determined the energy saving factor of each node using the steady state probabilities of states that are in vacation. According to the infrastructure-less nature of the ad hoc network, saving energy to keep nodes alive is an important issue for the network in [19]. Fallah et al. evaluated the performance of the system based on three aspects: the cumulative distribution function of the waiting time distribution, the probability mass function of the number of packets in the queue and the energy saving factor of the network. In [21], [22], [23], [24] and [6], comprehensive explanation on the M G M and queuing theory implemented for systems especially wireless systems and also the mathematical 32 Chapter 2. Background and Related Work methods to solve the Markov chain can be found. In [25], Alfa et al. solved an infinite Markov chain with M G M and showed that this method is useful for the case that there exist one embedded Markov parameter in the system. In [26], assuming a finite number of packets can be stored in each buffer, Long et al. used a modified version for M G M , to find the steady state probabilities. The work in [25] and [26] do not consider the priority classes for the packets in the system. In [24], Alfa presented a proposal to handle the cases in which there are queues of different priority classes which is the case in the communication systems and QoS terms. In [26], Long et al. solved a M A P / P H / 1 system with two priority classes with M G M ; then calculated the steady state probability of the system and the waiting time distribution of the queues as well. In [2], Alfa showed that almost every queueing system can be represented as a vacation model. He introduced different vacation models such as time limited server, random time limited, gated server, and number of limited server. Elaborating on M G M is not possible without considering the contribution of Kro-necker product. In mathematics, the Kronecker product, <g>, is an operator between two arbitrary matrices that results in a block matrix. For instance, assume matrices A and B are as follows: an 012 A = , (2.26) a 2 i a<ii 33 Chapter 2. Background and Related Work B = bu b 12 (2.27) ^21 ^22 The matrix A® B, the Kronecker product of A and B is: A®B = anB auB a,2\B a^B (2.28) 2.8 Summary In this chapter, we first introduced the characteristics of the UWB, and then we focused on ECMA-368 as one of the standards that use UWB in its physical layer. The M A C layer of ECMA-368 was summarized. Another issue discussed in this chapter was the Matrix Geometric Method (MGM) as an efficient way to solve infinite Markov chains. Then we discussed related works to our purpose model including literature on modeling wireless standards or literatures focused on solving Markov chains using M G M and also literature on specific characteristic of UWB. In Chapter 3, we are going to elaborate our proposed model for ECMA-368 based on the background knowledge provided in this chapter. 34 Chapter 3 Analytical Model In this chapter, we propose an analytical model for ECMA-368. First, we elaborate on the state definition of the system. We then describe the probability transition matrices of the proposed model and how they can be extracted. At the end, the system parameters such as the waiting time distribution and the probability of the number of packets in the system are determined. 3.1 E C M A - 3 6 8 According to the ECMA-368 standard [1], communication between different nodes in an ad hoc network take place within a superframe. Each superframe is divided into two parts: beacon and data. A time slot is dedicated to each node within the network. During each time slot within the beacon period, nodes exchange the control information. During the data part, nodes transmit data packets. Data exchange can be in two different ways: Distributed Reserved Protocol (DRP) and Prioritized Contention Access (PCA). During the DRP period, bandwidth reservation is based on Time Division Multiple Access (TDMA). Then, the service distribution can be modeled as a deterministic distribution. During the P C A period, data exchange is based on random access. Therefore, a simple 35 Chapter 3. .-'Analytical Model way to model this part is to use the geometric distribution. 3.2 System Model We assume a M A P / P H Y / 1 system where the arrival process follows a M A P distribution, and the service time follows a P H Y distribution. The server has three different modes of service. The first mode is the beacon period during which no data packets are being transmitted. The server can be considered idle in this mode. The second mode is the DRP part, in which each node has allocated one time slot for data transmission. The service time for this mode can be modeled as deterministic service. The third mode of the server is the P C A with geometric distribution. The state space of the system can be defined as: AB = {i,j,k1,k2,r), (3.1) - T = (i,j,h,hJ), (3-2) A c = (i, j,k1,k2,u); (3.3) where i is the number of the packets in the DRP queue, j is the number of packets in the P C A queue; k\ and k2 are the phase of arrival for the DRP and P C A queue, respectively, since there are two separate queues for DR.P and PCA; r is the number of time slots that the server is in idle mode; I is the number of time slots that the server has spent in the 36 Chapter 3. Analytical Model DRP mode, and u is the number of time slots that server has spent in the PCA mode. The vector A_ denotes the states when the server is idle or in the beacon period. The vector AT denotes the states when the server visits the DRP queue, and the vector Ac denotes the states when the server visits the PCA queue. The deterministic service in discrete time can be represented as a phase type distri-bution with the number of phases equal to the number of time slots that the server visits the queue of that specific mode. For instance, a deterministic service with four phases can be shown as follows: S = (3 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 (3.4) (3.5) where S is the transition probability matrix and (3 is the initial state probability [6]. We follow the conventional notation [21], [22], [23] and use (T, a) for the arrival distribution and (S, (3) for the service distribution. The probability matrix of the system when the DRP queue is the main queue can be 37 Chapter 3. 'Analytical Model represented as Q B D : yDRP gDRP QDRP jrjDRP j^DRP ADRP ADRP ADRP ADRP •^-2 7 1 1 ^ 0 (3.6) In (3.6), the matrix blocks A2RP, AfRP, AQRP are probability matrices representing the decrease in the number of packets in the D R P queue by one, no change in the number of packets, and an increase in the number of packets by one, respectively. Matr ix B D R P is the initial probability matrix representing no change in the number of D R P packets. Matr ix CDRP is the initial probability matrix for the states with an increase in the number of D R P packets and matrix E D R P is the initial probability matrix for a decrease by one in the number of D R P packets. The number of rows depends on the buffer size of the node. We assume that for D R P , the number of packets is infinite. For the P C A queue, there is a buffer limit of M packets in the system. 38 Chapter 3. Analytical Model Matrix blocks AgRP, Aj)RP, and A%RP are defined as follows: i +1 0 D , i ® V 0 D n ® Y 0 D n ® Y 0 D u ® y 0 D n g y o D „ g r K - 1 K D „ ® / 0 Dxl®XL 0 (3.7) t + 1 0 D l 0 ® Y 0 D 1 0 ® V 0 D 1 0 ® Y 0 D10®Y 0 D 1 1 ® V ' 0 D i o ® ^ 0 D J Q ® X K - 1 K D10®XL 0 (3.8) 39 Chapter 3. [Analytical Model 0 0 i + 1 0 0 0 0 o o 1 0 ®y (3.9) K - 1 K where XDRP and Y are as follows: X DRP D20 ® S D 2 0 ® I £ > 2 0 ® ( S ° < 3 ) D 2 i ® (S°0) + D 2 0 ® S D 2 j ® S 0 0 0 O 2 0 ® ( S ° / 3 ) D 2 i ® (S°0) + £ > 2 0 ® S + D 2 1 ® S J (3.10) (3.11) where Dw and /Jn are the probability generating matrices of no arrival and one arrival to the DRP queue, respectively. £_n and £_i are the probability generating matrices of no arrival and one arrival to the P C A queue, respectively. / is the identity matrix and / is defined as follows: 1 = V (3.12) 0 0T Each of the matrix blocks, ADRP, AfRP and AgRP, is divided into three parts. The first part belongs to the beacon period, the second part to the DRP period, and the third part to the P C A period. 40 Chapter 3. Analytical Model 3.3 Wait ing Time Distr ibution To determine the distribution of the waiting time of the system for each queue, we need to find the embedded Markov chain. The Markov chain that we implement for the system is based on a scenario from an observer to the system. When we want to calculate the waiting time distribution, we need to find the state of the system from the point of view of a packet that arrives at the system. That is the reason why we need to modify the embedded Markov chain. After the embedded Markov chain has been calculated, the steady state probability of the new chain can be determined. 3.3.1 DRP Queue Let zfu denote the steady state probability vector that there are i packets ahead of a tagged packet arriving at the system in time slot u during the beacon period. t°. = l^NcDU' U = 1 , (3.13) x ^ ^ n , u = 2,3,...,NB where x ? u _ 1 is the probability vector of having i packets of DRP type at the end of the contention P C A period. Nc is the maximum number of time slots that the server can spend in the contention period. A/_ is the maximum number of time slots within the beacon period. Let z[u denote the steady state probability vector that there are i packets in front of a tagged packet arriving at the system in time slot u during the DRP 41 Chapter 3. ^Analytical Model period * f j V H A l , u=l z T u — ( x t i A i , u>2, u + k , (3-14) x f u - i A i , u>2, u = k where k is the number of time slots that a specific node transmits during the DRP period. Let z f u denote the steady state probability vector that there are i packets in front of a tagged packet arriving at the system in time slot u during the P C A period. " = 1 (3.15) 5? . i D n , u = 2,3,...,Nc where NT is the maximum number of time slots within the DRP period. From the above steady state probabilities, we can calculate the waiting time distri-bution of the DRP packets. Let Zj = [zf zj zf] be the steady state probability vector of finding j packets in front of a tagged packet arriving at the system, and each of zf, i j , i f is partitioned as V*Tiod = [if0riod zf;iod... z ] f " o d . . . ] . Each period corresponds to either beacon, PCA, or DRP modes. Then, Z j + l — ^jPembeddedi j = 0, 1,2, (3.16) where Pembedded is the transition probability matrix of the embedded Markov chain that can be obtained from the transition probability matrix P in the DRP case and Q in the P C A case. The embedded Markov chain transition matrix can be obtained by replacing the D20 and Dw with 0, and D2i and Du with 1 in P and Q, respectively. The waiting 42 Chapter 3. 'Analytical Model time distribution can be obtained from: (3.17) where WT is the probability of waiting more than r time slots in the DRP queue. 3.3.2 PCA Queue We obtain the steady state probability of the system from the transition matrix P which is a QBD based on the changes to the DRP queue. Therefore, when we want to find the waiting time distribution of the P C A or the inner queue in the Markov chain, we have to find the probability transition matrix corresponding with changes to P C A queue. The process of finding the probability transition matrix for the P C A queue is the same as that for the DRP queue. If we assume the transition probability matrix of P C A is Q, then Q has the following format as a QBD: gPCA QPCA FJPCA A?CA A P C A A PCA APCA A PCA f\2 ^1 ^0 Q = APCA (3.18) A P C A APCA the matrix blocks APCA, AfCA, APCA ave probability matrices corresponding the decrease in the number of packets in the P C A queue by one, no change in the number of packets, and an increase in the number of packets by one, respectively. Matrix BPCA is the initial 43 Chapter 3. "Analytical Model probability matrix denoting no change in the number of PCA packets. Matrix CPCA is the initial probability matrix for the states with an increase in the number of DRP packets and matrix EPCA is the initial probability matrix for a decrease by one in the number of PCA packets. APCA 0 D 2 i ® Y o D 2 I ® V 0 D2i®Y 0 Yk 0 £> 2i ® Y £>21 ® / o Z 3 2 1 ® s ® y 0 (3.19) where Yk is the probability of decreasing by one for the DRP queue and can be calculated as follows: r £ 2 0 0 Yk = (3.20) 0 D2i 44 Chapter 3. 'Analytical Model APCA = 0 D20 <8> Y 0 D20 ® Y 0 D20®Y 0 D20 ® Y D20 ® I where F is as follows: 0 £> 2 0 ® YK' 0 D20®Y F = [ D 2 Q ® S + D21®{S°f3)}, 0 F ®Y o F ® y 0 (3.21) (3.22) Here, and y are defined as follows : Do, 0 y 1^ 20 D2l 0 £>21 -D 2o ^21 £>20 (3.23) (3.24) 45 Chapter 3. -Analytical Model The block matrix of APCA can be calculated as: A PCA 0 0 0 0 0 0 0 0 0 D20 ® Y , (3.25) 0 D2Q <g> (S°p) ® Y 0 After forming the probability transition matrix for the system based on the changes to the P C A queue, we can find the embedded Markov chain according to the number of packets in the line from an arriving packet point of view. It is enough to find the steady state probability of the number of the packets in the P C A queue that a tagged packet sees as it arrives at the system [7]. Let z?u denote the steady state probability vector of finding j packets of P C A type 4 6 Chapter 3. ^Analytical Model in front of a tagged packet arrives at the system in time slot u during the beacon period. 3 f u = < "•" • (3-26) \ j \ JVc D21, u=l x ^ I ^ , ^ = 2 , 3 , . . . , ^ s where JV S and i V c are the number of beacon period time slots and P C A period time slots, respectively. Let z,Ju denote the steady state probability vector of finding j packets of the P C A type in front of a tagged packet that arrives in time slot u during the D R P period. zj,u = S . I3-2") [Hf^Diu u = 2,3,...,NT where NT is the number of time slots of the D R P period. Let z f u denote the steady state probability vector of finding j packets of P C A type in front of a tagged packet that arrives in time slot u during the P C A period. XLV T A>I , u=l -lu =\ (3-28) *£„_i(£>2i ® S) + Sf?+XtU_^D2l <g> (S°0)), u = 2,3,...,NT Now that we have the steady state probability vector, we can form the vector Zj and calculate all the other Zj vectors using equation (3.16). The difference is that the em-bedded matrix P should be replaced by the embedded matrix Q. As a reminder, to find Qembedded, we have to replace D2o with 0 and D21 with 1. Using equation (3.17), the waiting time distribution for the P C A packets can be derived. 47 Chapter 3. Analytical Model 3.4 Summary In this chapter, we proposed an analytical model to evaluate the performance of the ECMA-368 M A C protocol. The system is modeled as a M A P / P H Y / 1 queue. We derived the steady state probabilities of the system. Based on that, we obtained the steady state probability of the number of the packets in the queue as well as the waiting time distribution. 48 C h a p t e r 4 P e r f o r m a n c e E v a l u a t i o n In this chapter, we present the results of the analytical model proposed in Chapter 3 and validate the results with the simulation model. We evaluate the performance of the system under different traffic loads and various lengths of the superframe. 4.1 System Parameters In this chapter, we aim to show the efficiency and effectiveness of our model in terms of predicting the QoS metrics. Our proposed analytical model is capable of deriving the probability mass function (pmf) of the number of the packets in each queue in a tagged node and the cumulative distribution function (CDF) of the waiting time that each packet in a specific queue (e.g., DRP or PCA) experiences. The proposed analytical model is a M A P / P H / 1 queueing system. The packet inter-arrival time distribution is a MAP. We assume that the packet inter-arrival time follows an exponential distribution with a mean of 0.01 per time slot for DRP packets and 0.2 per time slot for P C A packets. Each time slot is 256 u.s. Since most distributions can be described as a P H distribution, the exponential dis-tribution can be represented as a P H distribution of (T, a) with one phase. The matrices 49 Chapter 4. Performance Evaluation a and T are as follows: « = [1], T = [A], T can also be determined if the generating matrix D is given. As an example, suppose the probability generating matrix D = D0 + D \ , where the matrices D\ and D0 are the probability generating matrix of one packet arrival and no packet arrival, respectively. T and a which are the PH distribution of the above M A P can be determined from the matrices D\ and DQ as follows [6]: T = D0, (4-1) T°a = Df. A PH distribution is a specific form of a MAP. The inter-arrival time distribution of our proposed model for the DRP packets is as follows: DW = [0.99], A i = [0.01]. The inter-arrival time of the P C A packets is assumed to follow an exponential distribu-tion. The P H representation of the inter-arrival time for the P C A packets is as follows: 0 2 0 = [0.8], D2i = [0.2], All the probabilities are on a per time slot basis. The service time distribution for the proposed model is PH. In our model, there are two types of service. The service provided during the DRP period is deterministic. The service provided during the P C A period 50 Chapter 4. Performance Evaluation has a PH distribution, which is equivalent to the 802.lie M A C . In [19], a two-phase P H distribution is proposed for the 802.11 service time distribution, with representation of (S,(3) for the service time distribution during the contention period of 802.11. The work in [19] assumed a constant probability of p for collision during the contention period and denoted the minimum and maximum size of the contention window by CWmin and CWmax, respectively. The proposed P H distribution (S,fi) in [19] is as follows: S = (4.2) 1 - Pr(BC = 1) Pr(BC = 1) p 0 where Pr(BC = 1) is the probability of backoff window expiration and can be obtained as: ^ = l ) = g ^ + ^ £ - , (4.3, where m = log 2 ( c ^ m g a ; ) and p is the probability of collision. The two phases in [19] which are assumed for the service time distribution of 802.11 are backoff and transmission. Using the same approach as in [19] to describe the service time distribution of the P C A in ECMA-368 may increase the matrix sizes in the analytical model and increase the overhead in computation. Thus, we choose to apply an exponential random access for the P C A service time distribution in our analytical model. The exponential distribution which we used in the simulation has a rate of 0.2. The P H representation of the service time is: S =[0.2], 0 = [1]-51 Chapter 4. Performance Evaluation Our proposed model is node-wise which means that the statistics we present in this chapter is per node basis. We assume an infinite buffer size for the DRP packets and a buffer size of M for the P C A packets. 4.2 Simulation Setup We use OPNET version 11.5 as the simulator to compare the results between the an-alytical model and the simulation model. In implementing our simulator, we try to be consistent to the ECMA-368 M A C standard. We simulate two arrival streams with pre-defined arrival probability to a node. There are two queues in each node. The node processes the packets of each queue based on the First In First Out (FIFO) order. Nodes are randomly located in an office area and each tagged node has 4 nodes as its neighbors. We assume a single hop network in which two nodes can communicate directly with each other. During the DRP period, there is no collision and each node transmits according to a predetermined schedule by its M A C layer. During the P C A period, if two nodes transmit at the same time, then there will be a collision. Otherwise, transmission is suc-cessful. For the two queues in a node, decision is made based on the policies in the M A C layer of ECMA-368. A scheduled transmission for the DRP queue and a contention-based transmission for the P C A queue. The arrival process to each node is independent of the service process and also in-dependent from each other. We used two independent generators to generate the DRP and P C A packets according to a predefined inter-arrival time distribution. We assume 52 Chapter 4. Performance Evaluation Simulation Parameters Value Data rate 480 Mb/s Modulation BPSK Number of nodes 5 DRP packet size 0.122 Mb P C A packet size 32000 Kb Number of time slots in a superframe 30 Number of time slots in the beacon period 5 Number of time slots in the DRP period 5 Number of time slots in the P C A period 20 Number of time slots in the beacon period 5 Duration of a time slot 256 JJLS Buffer size for the P C A packets 0.8 Mb Average packet arrival rate (PCA)-Poisson 3125 Packets/sec Average packet arrival rate (DRP)-Poisson 36 Packets/sec Table 4.1: Parameters of the simulator non-batch arrivals. Therefore, at most one packet is generated at each time slot of length 256 lis. We assume that if an arrival event and a service completion event occur at the same time, then the service time completion will occur first followed by the arrival event. The parameters of the simulator is shown in Table 4.1. 53 Chapter 4. Performance Evaluation 4.3 Results and Discussion In this section, we present the analytical results and compare them with the simulation results to validate the correctness of our model. 4.3.1 D i s t r i b u t e d Reserved P r o t o c o l ( D R P ) Figure 4.1 shows the analytical and simulation results of the probability mass function of the number of the packets in the DRP queue. The DRP period provides the opportunity for nodes to reserve the channel time. Packets with reserved time slots during DRP do not experience long waiting time in the queue. The analytical and simulation results show that the number of DRP packets in the system is negligible. Each packet can access the channel almost at once if it requests a reserved time slot during the beacon period. Simulation results show a higher probability of having no packets in the system. The reason for this discrepancy is that, to obtain the simulation results, we extract the information from the simulator and use M A T L A B to derive the statistical features of the data. To obtain the number of packets in the system, we track the time that a packet arrives and the time that a packet leaves the system. The packet size we used in our simulation is 0.122 Mb. We choose the packet size in such a way as to ensure that the transmission of a packet will end before the end of a time slot. A packet with the above size and transmission rate of 480 Mb/s will require 200 /is in the system to be transmitted completely, which is slightly smaller than the length of each time slot within the superframe. In the analytical model, each packet transmission time will last the 54 Chapter 4. Performance Evaluation 0.8 0.7 0.6 o • a u § 0.5 (£• CA cd S 0.4 1 0.3 I fi 0.2 0.1 0 0 1 2 3 4 Number of packets Figure 4 .1: Probability mass function of the number of the D R P packets in the system. complete time slot duration. Therefore, the system wil l track the packet in the system for a longer amount of time (since in simulation the size of a packet is 0.122M6, but in the analytical model, the size of each packet is exactly the same as the time slot; thus ratio of the two packet sizes is 1.28 which corresponds to the increased tracking duration) and that's the reason why we obtain a higher probability for no packets in the system from the simulation results. For instance, the probability of having no packets in the system in the simulation results is greater than the analytical predictions by a factor of 1.2. The analytical results show a higher probability in having one or more packets in the system comparing to the simulation results, since each packet in the simulation will leave the system slightly sooner than in the analytical model. Another system parameter that we can obtain from our analytical model is the C D F 55 1 Analytical Results I Simulation Results Chapter 4. Performance Evaluation 1.1 0.9 a 0.8 T3 u 0.7 0.6 0.5 0.4 s s / J / / / 1 1 1 J 1 / / / / / / / ' / / / / J • Analytical Results 0 0.01 0.02 0.03 Delay (sec) 0.04 0.05 0.06 F igure 4.2: Cumulative distribution function of the waiting time of the DRP packets. of the waiting time for the packets in the DRP queue. Since our analytical model is discrete-time, it can provide information every superframe. Figure 4.2 shows the CDF of the waiting time of the packets in the DRP queue from both simulation and analytical models. The waiting time defined in our analytical model is equal to the time during which a packet from higher layer is placed in the M A C layer queue and the time that the packet is sent. Since we assume an ideal channel and a no-ACK policy, the transmission is successful when a packet is sent. Figure 4.2 shows that packets in the simulation experience less delay comparing to the analytical model. The reason for this phenomenon is that each packet in the simulator leaves the system sooner than the packet experiences in the analytical model and also due to the fact that the probability of having packets in the system is smaller in the simulation. As a result, the access delay is slightly smaller 56 Chapter 4. Performance Evaluation Number of packets Figure 4.3: Probability mass function of the number of P C A packets in a tagged node than the analytical model. 4.3.2 Prioritized Contention Access (PCA) From equations (3.1), (3.2) and (3.3), the Markov chain states are defined in a way that can track the number of both D R P and P C A packets in a tagged node. Therefore, from the steady state probabilities of the proposed Markov chain, we can obtain the number of the P C A packets in a tagged node. Figure 4.3 shows the pmf of the number of the P C A packets in a tagged node. Results from the analytical model and the simulation are consistent, which show the accuracy of the proposed analytical model. There are only a slight differences between simulation data and the analytical predictions. The reason is that in simulation, the transmission of each packet may finish before the end of a specific 57 Chapter 4. Performance Evaluation 5 •a 0.4 -I 5 0.2 a o Analytical Results Simulation Results 0 0 0.01 0.02 0.03 Delay (sec) 0.04 0.05 0.06 Figure 4.4: Cumulative distribution function of the P C A packets waiting time. time slot. Other nodes can sense that the channel is idle and wait for SIFS amount of time and start transmitting the next packet one time slot sooner than anticipated in comparison to the analytical model. 4.3.3 Increasing the Length of the Superframe One parameter which can affect the amount of delay that each packet experiences in a tagged node is the length of the superframe. In ECMA-368 standard [1], the length of superframe is fixed. There are 256 time slots in each superframe. In our proposed model we use 30 time slots in each superframe in order to reduce the complexity of calculations. Increasing the amount of time slots in a superframe when the number of nodes in the network is fixed will increase the P C A period. We expect a higher probability of havng more packets in the system and a lower probability of having no packets in the system 58 Chapter 4, Performance Evaluation Analytical Results Simulation Results 1 2 3 4 Number of packets Figure 4.5: Probability mass function of the number of D R P packets in a tagged node (there are 40 time slots in each superframe). comparing to the previous results. Figure 4.5 shows the analytical and simulation results when there are 40 time slots in each superframe. The C D F of the waiting time of the D R P packets depicted in Figure 4.6 shows that increasing the size of the superframe results in an increase of the waiting time of the D R P packets in the system. Since the D R P period does not change and only the P C A period has increased, the period of time in which the D R P packets do nothing but waiting for the next D R P period increases. This increase leads to the increase in probability of the waiting time. Therefore, a decrease in the slope of the C D F of the waiting time of the D R P packets. 59 Chapter 4. Performance Evaluation Figure 4.6: Cumulative distribution function of the P C A packets waiting time with 40 time slots. 60 Chapter 4. Performance Evaluation 160 Arrival traffic (packets/sec) Figure 4.7: Aggregate throughput of P C A traffic versus arrival traffic for different num-ber of nodes in the network. 4.3.4 Effect on Varying the Arrival Traffic In this section, we study the effect of changes in the arrival traffic of the network. Figure 4.7 shows the aggregate throughput versus the arrival traffic. As the number of the P C A packets which arrive at each node increases, the throughput increases. The throughput improvement continues until the network reaches its saturation condition. When the network is saturated, an increase of the traffic not only cannot increase the throughput but may also cause in a decrement in throughput to some extend. Figure 4.7 shows an increase in the number of nodes in the network can increase the aggregate throughput. The reason behind this increment is that when the number of the nodes increases, there is an increase in the arrival traffic of the network. The throughput depicted in Figure 61 Chapter 4. Performance Evaluation 0 T , , . 1 100 200 300 400 500 600 Arrival traffic (packets/sec) Figure 4.8: Medium access delay of P C A traffic versus arrival traffic for different number of nodes in the network. 4.7 is the aggregate throughput of the network. To find the individual throughput of the network, the amount depicted in Figure 4.7 should be divided by the number of nodes within the network. As the arrival traffic increases, the average amount of time that each packet should wait increases as well. Figure 4.8 shows the changes to the medium access delay due to the changes in the arrival traffic. In case of 15 nodes in the network, due to the increasing amount of collisions, the waiting time increases drastically. If the number of nodes within the network increases, the medium access delay will increase. The reason behind this increment is that there are higher number of nodes competing to obtain the channel. Therefore, on average each node should wait a longer time to obtain a TXOP. Results from Figure 4.9 show that when the number of arriving packets to the network 62 Chapter 4. Performance Evaluation 1.8 1.6 1 .4 £? 1.2 J 13 i •a ^ 0 . 8 0.6 0.4 f' Maximum individual throughput - *— 5 nodes -0— 8 nodes -o- 10 nodes -6— 15 nodes 10 12 14 Arrival traffic (packets/sec) 16 18 Figure 4.9: Individual throughput of DRP traffic versus arrival traffic for different num-ber of nodes in the network. is small, the throughput of the DRP is equal to the arrival rate. The reason behind this behavior is that when the arrival traffic is light, there are some superframes that the DRP time slots remain empty and there is no packet to send. Therefore, the amount of throughput follows the traffic rate. As the traffic rate increases, and the network reaches to the saturation, the throughput remains constant. Since each node has a share of jig in each superframe (which means 1.875 Mb/s in each superframe). We expect a constant throughput after the network reaches its saturation point. Figure 4.10 shows the aggregate throughput of the network. The DRP period guarantees QoS in a sense of timing and maintains the QoS as the network load increases. 63 Chapter 4. Performance Evaluation 10 12 14 Arrival traffic (packets/sec) Figure 4.10: Aggregate throughput of DRP traffic versus arrival traffic for different number of nodes in the network. Figure 4.11 shows the impact of the changes in the arrival traffic of the DRP packets V on the delay performance of the network. When the arrival traffic is small, packets experience negligible delay. As the traffic increases, the delay increases as well. Networks with larger number of nodes experience higher delay because of having a longer beacon period that postpone the first transmission time. Upon a moderate increase in the arrival traffic of the DRP packets, the performance of the system in terms of delay will degrade slightly. If we continue to increase the arrival traffic, then the delay performance of the system will degrade drastically due to the long queueing delay. 64 Chapter 4. Performance Evaluation 4 6 8 10 12 14 16 18 Arrival traffic (packets/sec) Figure 4.11: Medium access delay of DRP packets versus arrival traffic for different number of nodes in the network 65 Chapter 4. Performance Evaluation 4.4 Summary In this chapter, we presented the pmf and cdf results from the analytical model and compare them with the simulation results from the OPNET software. The results validate the correctness of the our proposed analytical model. Our model can capture some of essential features in the ECMA-368 standard. We also presented the results under different arrival rates for DRP and P C A packets. 66 C h a p t e r 5 C o n c l u s i o n s a n d F u t u r e W o r k In the following sections, we summarize our thesis and suggest the opportunities for future work and investigation. 5.1 Thesis Summary Throughout the presented thesis, we proposed a MAP/PH/l queueing system for E C M A -368. There are two queues in the system: Distributed Reserved Protocol (DRP) and Prioritized Contention Access (PCA). The M A C layer which is assumed as the server in the queueing system provides service to both queues based on the structure of a super-frame. The server provides two different type of services to the queues. According to the ECMA-368 standard, during the DRP period, nodes that reserved the time slots have a guaranteed access to the channel. Therefore, the service time in the DRP queue can be modeled as deterministic. On the other hand, the service provided during the P C A period is contention-based. In the proposed model, we assume a random P H distribution for the service provided during the P C A period. Our contributions are as follows: • We proposed a M A P / P H / l queueing system as an analytical model which is con-67 Chapter 5. Conclusions and Future Work sistent with the features of the ECMA-368 M A C protocol. We considered two independent arrival streams to provide different classes of service for the DRP and P C A packets. We elaborate two different models for the P C A and DRP packets to obtain more precise results. • We developed a mathematical framework for the proposed analytical model. The mathematical framework takes into account the arrival rates of the DRP and P C A packets, the probability of the collision during the P C A period, the number of nodes within the network, and the buffer size of the P C A packets waiting in the queue. • Based on the proposed model and the mathematical framework, we used M G M to find the parameters of the system such as the probability mass function (pmf) of the number of the DRP and P C A packets and the cumulative distribution function (CDF) of the waiting time of the DRP and P C A packets in the system. We continued the thesis with a brief discussion on the effect of the number of nodes in the network on the throughput and delay performance of the system. • We demonstrated that increasing number of nodes in the network will increase the throughput of the network for both DRP and P C A until the system meets the saturation condition. • We demonstrated that increasing number of the nodes degrade the delay perfor-mance of the system. 68 Chapter 5. Conclusions and Future Work 5.2 Future Work In this thesis, we proposed a model for a superframe based wireless ad hoc network. There are various extensions that can be considered. Some of them include: • Modeling 802.15.3a: According to [5], nodes communicate by means of super-frame. The difference between 802.15.3a standard and ECMA-368 is the fact that the length of the superframe is not fixed in 802.15.3a. Therefore instead of having probability transition matrix, P, with a fixed length, the size of P changes in each superframe. • Modeling the variable DRP period using M G M : Our current model is based on the assumption that the DRP period is placed at the beginning of the data period right after the beacon period. According to the standard, the DRP can happen anywhere during the data period. This fact can be implemented by using a random PH distribution that can model random DRP intervals with variable length. • Modeling the priority classes using M G M : According to the standard, E C M A -368 provides different classes of service. Using M G M , we can model the multi-class system. 69 B i b l i o g r a p h y [1] "ECMA-368 : High rate ultra wideband P H Y and M A C standard," Dec. 2005. [2] A . S. Al fa, "Vacation models in discrete time," Queueing Systems, vol. 44, pp. 5-30, Aug. 2003. [3] G. Aiello and G. Rogerson, "Ultra-wideband wireless systems," IEEE Microwave Magazine, vol. 4, pp. 36-47, June 2003. [4] X . G u and L. Taylor, "Ultra-wideband and its capabilities," British Telecom Tech-nology Journal, vol. 21, no. 3, July 2003. [5] " I E E E P802.15 working group for Wireless Personal Area Networks (WPANs) I E E E P802.15-03/268r3: Mult i-band O F D M physical layer proposal for I E E E 802.15 task group 3a," March 2004. [6] A . Al fa, "Discrete time queues and matrix-analytic methods," TOP, vol. 10, no. 2, pp. 147-185, Dec. 2002. [7] M . F. Neuts, Matrix Geometric Solution in Stochastic Models. The John Hopkins University press, 1981. 70 Bibliography [8] G. Latouche and V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling. American Statistical Association and Society for Industrial and Applied Mathematics, Jan. 1999. [9] K. Lu, D. Wu, and Q. Y . Fang, "Performance analysis of a burst-frame-based M A C protocol for ultra-wideband ad hoc networks," in Proc. IEEE International Confer-ence on Communications (ICC), Seoul, Korea, May 2005, pp. 2937-2941. [10] K . Lu, J. Wang, D. Wu, and Y . Fang, "Performance of a burst-frame-based C S M A / C A protocol for high data rate ultra-wideband networks: Analysis and enhancement," in Proc. of the Srd International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks (QShine), Waterloo, Ontario, Canada, Aug. 2006. [11] R. Merz, J. Yves, L. Boudec, J. Widmer, and B. Radunovic, A Rate-Adaptive MAC Protocol for Low-Power Ultra-Wide Band Ad-Hoc Networks. Springer Berlin / Heidelberg, 2004, ch. Ad-Hoc, Mobile, and Wireless Networks, pp. 306-311. [12] X . Shen, W. Zhuang, H. Jiang, and J. Cai, "Medium access control in ultra-wideband wireless networks," IEEE Transactions on Vehicular Technology, vol. 54, pp. 1663 -1677, Sept. 2005. [13] Y . Chu and A. Ganz, "Adaptive M A C protocol for QoS support in UWB-based wireless networks," in Proc. IEEE International Conference on Communications (ICC), Istanbul, Turkey, June 2006. 71 Bibliography [14] D. Tarchi, R. Fantacci, and G. Izzo, "Multimedia traffic management in IEEE 802.15.3a wireless personal area networks," in Proc. IEEE International Confer-ence on Communications (ICC), Istanbul, Turkey, 2006. [15] B. Radunovic and J. Y . L. Boudec, "Optimal power control, scheduling, and routing in UWB networks," IEEE Journal in Selected Areas in Communications, vol. 22, pp. 1252- 1270, Sept. 2004. [16] K. Liu, L. Cai, and X . Shen, "Performance enhancement of medium access control for UWB WPAN," in Proc. IEEE Globecom'06, San Francisco, CA, Nov. 2006. [17] A. Mishra and P. Papadimitratos, "A cross layer design of IEEE 802.15.4 M A C protocol," in Proc. IEEE Globecom'06, San Francisco, CA, Nov. 2006. [18] R. Merz, A. E. Fawal, J. Y . Boudec, B. Radunovic, and J. Widmer, "The optimal M A C layer for low-power UWB is non-coordinated," in IEEE International Sympo-sium on Circuits and Systems (ISCAS), Island of Kos, Greece, May 2006. [19] A. Fallahi, E. Hossain, and A. S. Alfa, "QoS and energy trade off in distributed energy-limited mesh/relay networks: A queuing analysis," IEEE Transaction Par-allel Distribution System, vol. 17, no. 6, pp. 576-592, June 2006. [20] G. Bianchi, "Performance analysis of the IEEE 802.11 distributed coordination func-tion," IEEE Journal on Selected Areas in Communications, vol. 18, pp. 535-547, March 2000. 72 Bibliography [21] N. Akar, N. Oguz, and K. Sohraby, " A novel computational method for solving finite Q B D processes," Communication in Statistic, Statistic Model, March 2000. [22] A . Al fa, B. L iu , and Q. He, "Discrete-time analysis of M A P / P H / l multiclass general preemptive priority queue," Naval Research Logistics, vol. 50, pp. 662-683, Dec. 2003. [23] A . Al fa, " A discrete M A P / P H / l queue with vacations and exhaustive time-limited service," Operations Research Letters, vol. 18, pp. 31-40, Aug. 1995. [24] A . S. Al fa, "Matrix-geometric solution of discrete time M A P / P H / l priority queue," Naval Research Logistics, vol. 45, no. 1, pp. 23-50, Dec. 1998. [25] A . S. A l fa and W. L i , "Matrix-geometric analysis of the discrete time G I / G / 1 sys-tem," Stochastic models, vol. 17, pp. 541-554, Nov. 2001. [26] L. B. Long, E. Hossain, and A . S. Al fa, "Queuing analysis for radio link level schedul-ing in a multi-rate T D M A wireless network," in Proc. IEEE Globecom'04, Dallas, T X , Dec. 2004. 73
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Performance evaluation of ECMA-368 medium access control...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Performance evaluation of ECMA-368 medium access control protocol for UWB ad-hoc networks Arianpoo, Nasim 2007
pdf
Page Metadata
Item Metadata
Title | Performance evaluation of ECMA-368 medium access control protocol for UWB ad-hoc networks |
Creator |
Arianpoo, Nasim |
Publisher | University of British Columbia |
Date Issued | 2007 |
Description | Ultra Wideband (UWB) is an emerging technology for high rate, short range wireless communications. Its unique features such as low power operation, robustness to multi-path fading, and accurate positioning capabilities makes UWB a good platform for wireless personal area networks (WPANs). One of the recent UWB standards standardized by the European Computer Manufacturers Association (ECMA) International is the ECMA- 368, which defines the physical (PHY) and media access control (MAC) layers for high rate WPANs. The MAC protocol in ECMA-368 has a superframe structure. Each superframe is divided into three different time periods. The beacon period is used for control purposes. The distributed reserved protocol (DRP) period allows devices to reserve bandwidth for data transmission. The PCA (prioritized contention access) period supports contention-based access between different traffic classes. In this thesis, we propose an analytical model to evaluate the performance of the ECMA-368 MAC protocol. We assume that packets follow the Markovian Arrival Process (MAP) and various service times can be modeled by different phase type distributions (PHYs). We apply the Matrix Geometric Method (MGM) technique and model the system as a MAP/PHY/1 queueing system. We derive the probability mass function (pmf) for the number of the packets in the queue, as well as the cumulative distribution function (CDF) for the waiting time of the packets in the queue. The correctness of our proposed analytical model is validated via simulations. We create the ECMA-368 module by using the OPNET simulator. Analytical and simulation results are presented under different scenarios |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-02-18 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
IsShownAt | 10.14288/1.0052086 |
URI | http://hdl.handle.net/2429/31545 |
Degree |
Master of Applied Science - MASc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2007-0312.pdf [ 3.65MB ]
- Metadata
- JSON: 831-1.0052086.json
- JSON-LD: 831-1.0052086-ld.json
- RDF/XML (Pretty): 831-1.0052086-rdf.xml
- RDF/JSON: 831-1.0052086-rdf.json
- Turtle: 831-1.0052086-turtle.txt
- N-Triples: 831-1.0052086-rdf-ntriples.txt
- Original Record: 831-1.0052086-source.json
- Full Text
- 831-1.0052086-fulltext.txt
- Citation
- 831-1.0052086.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0052086/manifest