THROUGHPUT PERFORMANCE OF TREE COLLISION RESOLUTION ALGORITHMS WITH CAPTURE By KENNETH K. L. WONG B. Eng. Electronic Engineering, University of Bradford, U.K., 1990 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF ELECTRICAL ENGINEERING We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA May 1994 © KENNETH K. L. WONG, 1994 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. (Signature) _ r— Department of Electrical Engineering The University of British Columbia Vancouver, Canada Date July 18, 1994 DE-6 (2/88) Abstract The effect of capture on tree algorithms in a slotted ALOHA broadcasting network is investigated. Two receiver models are considered: Feedback With Capture (FWC) and Feedback Without Capture (FWOC). In FWC, the receiver is able to distinguish between a success and capture slot, whereas in FWOC it is not. For each model, two collision resolution schemes are examined. The throughput performances of the four schemes using the discrete and continuous capture models are obtained and compared. In the discrete capture model, the transmitters are divided into groups. Only packets from transmitters in a more dominant group have a chance to be captured. The con-tinuous capture model is used to examine the throughput performance on the inbound (mobile-to-base station) channel in a packet radio system consisting of a central base sta-tion and a number of mobile user terminals. The use of a dynamic tree (DT) algorithm in a continuous capture environment is also investigated. Expressions for finding the average length of a collision resolution interval (CRI) for each scheme using the static binary tree are derived. These average lengths are used to determine the throughput. Numerical procedures are described which use the static binary tree results in the dynamic tree to estimate the throughput. Simulations are used to verify the maximum achievable throughput in DT which also give plots of the average packet delay against the arrival rate. n Table of Contents Abstract ii List of Tables vi List of Figures vii Acknowledgement xi 1 Introduct ion 1 1.1 Multiple Access Model 3 1.2 Tree Algorithm 5 1.3 Capture Effect 7 1.4 Organization of thesis 9 2 Discrete Capture Mode l 10 2.1 Implementation of the Static Binary Tree CRA 11 2.2 Feedback With Capture (FWC) 14 2.2.1 Analytical Results for 2-Group Infinite Capture Model 16 2.2.2 Maximal Average Throughput for Poisson Arrival Process . . . . 20 i i i 2.2.3 FWC: 2-Group Finite Capture Model 23 2.3 FWC 3-Group Infinite and Finite Capture Model 29 2.3.1 Analytical Results for 3-Group Infinite and Finite Capture Model 29 2.3.2 Throughput for 3-Group Capture Model 33 2.4 FWOC: 2-Group Capture Model 34 2.4.1 Wait For Partial Conflict Resolution 39 2.4.2 Send In the Next Slot 42 2.5 Throughput Comparison Of Different Schemes 47 3 Continuous Capture Model 49 3.1 Capture Model and Capture Probabilities . 50 3.2 FWC . 53 3.2.1 Scheme 1 53 3.2.2 Scheme 2 62 3.3 FWOC 66 3.3.1 Wait for Partial Collision Resolution 66 3.3.2 Send in the Next Slot 76 3.4 Comparing the Different Schemes for the Continuous Capture Model . . 85 4 O p t i m u m D y n a m i c Tree Algor i thm 88 4.1 Optimum Dynamic Tree Protocol 88 4.1.1 Poisson Arrival Process 89 iv 4.1.2 Optimum Dynamic Tree Algorithm 91 4.2 Throughput of the Optimum Dynamic Tree 92 4.2.1 FWC . 93 4.2.2 FWOC 97 4.3 Numerical Results 101 5 Conclusions 108 References 110 A p p e n d i x A Bounds for E[l] and E[P] 112 v List of Tables 2.1 Table showing the effect on n/Ln^ and maximum average throughput as n increases in the infinite capture model with optimum a = 0.41 and k = \n-a\ 25 2.2 FWC: Maximum average throughput of infinite and finite capture model. 27 2.3 Summary of the capture condition in a 3-Group capture model where X is some positive integer. 30 2.4 FWC: Maximum throughput of a 3-Group infinite and finite capture model. 34 2.5 FWOC: Maximum throughput of infinite and finite capture model. . . . 47 2.6 Maximum throughput performance of different schemes using discrete cap-ture models 48 3.1 Maximum throughput performance of different schemes using continuous capture models 86 4.1 Optimum root node degree obtained through ^, 91 4.2 Comparison of the throughput performance between the calculated and simulated results of different schemes using continuous capture Model 2.1 with the optimum dynamic tree protocol 107 vi List of Figures 1.1 Multiaccess Channel 2 1.2 Examples of Multiaccess Channels 4 1.3 Static Tree CRA 8 2.1 An example of using the Tree CRA to resolve a collision 13 2.2 Flow diagram of Tree CRA using a 2-Group capture model 15 2.3 FWC Scheme 1: Time-line diagram showing CRI of (a) 72)i , (b) 7 n j l , n > 3. 17 2.4 FWC Scheme 2: Time-line diagram showing CRI of (a) 72)i, (b) Ln>i, n > 3. 19 2.5 FWC Scheme 1: n/Lntk versus number of nodes from the DG (&), n — 48. 25 2.6 FWC Scheme 2: n/Lnyk versus number of nodes from the DG (k), n = 48. 26 2.7 FWC Scheme 1: Ln versus total number of nodes (n) up to n = 48. . . 26 2.8 FWC Scheme 2: Ln versus total number of nodes (n) up to n = 48. . . 27 2.9 FWC Scheme 1: 3-Group capture model, n/Ln^1,k2 versus &2 with k\ = 13, n = 48 35 2.10 FWC Scheme 2: 3-Group capture model, n/Lntkltk2 versus hi with k\ = 13, n = 48 35 2.11 FWC Scheme 1: 3-Group capture model, average CRI length Ln versus n. 36 vii 2.12 FWC Scheme 2: 3-Group capture model, average CRI length Ln versus n. 36 2.13 Examples of FWOC: "Wait for Partial Conflict Resolution" Scheme and "Send in the Next Slot" Scheme. 37 2.14 Flow Diagram of FWOC: Wait for Partial Conflict Resolution Scheme. . 38 2.15 FWOC Wait: n/L^ versus number of nodes from the DG (k), n = 48. 42 2.16 FWOC Wait: Ln versus total number of nodes (n) up to n = 48 43 2.17 Flow Diagram of FWOC: Send In the Next Slot Scheme 44 2.18 FWOC Send: njLTnh versus number of nodes from the DG (k), n = 48. 46 2.19 FWOC Send: Ln versus total number of nodes (n) up t o n = 48 46 3.1 Probability of successful qi versus the number of contending transmitter i. 52 3.2 Continuous Capture FWC Scheme 1: different cases of flipping outcomes. 55 3.3 Continuous Capture FWC Scheme 1: different cases of flipping outcomes. 56 3.4 Example for FWC Scheme 2: Continuous Capture Model 63 3.5 Average CRI length, L'n, versus n: Continuous Capture FWC Scheme 1. 64 3.6 Average CRI length, L'n, versus n: Continuous Capture FWC Scheme 2. 64 3.7 Maximal Throughput versus n: for Continuous Capture FWC Scheme 1. 65 3.8 Maximal Throughput versus n: for Continuous Capture FWC Scheme 2. 65 3.9 Average CRI length, L™, versus n: Continuous Capture FWOC "Wait for Partial Conflict Resolution" 83 3.10 Average CRI length, L*n, versus n: Continuous Capture FWOC "Send in the Next Slot" 84 vm 3.11 Maximal Throughput versus n: for Continuous Capture FWOC "Wait for Partial Conflict Resolution" 84 3.12 Maximal Throughput versus n: for Continuous Capture FWOC "Send in the Next Slot" . . . . . . . ' . 85 4.1 Example of a dynamic tree with KD = 2 i.e. 2KD = 4 subtrees 90 4.2 Flow diagram of dynamic tree for both schemes in FWC 94 4.3 Flow diagram of FWOC: Wait for Partial Conflict Resolution Scheme using DT 95 4.4 Flow diagram of FWOC: Send In the Next Slot Scheme using DT. . . . . 96 4.5 Example of the "Wait" scheme using dynamic tree with root node degree equals 4 97 4.6 Example of the "Send" scheme using dynamic tree with root node degree equals 4 98 4.7 FWC Scheme 1: Simulated average delay versus arrival rate 103 4.8 FWC Scheme 2: Simulated average delay versus arrival rate 103 4.9 FWOC "Wait" Scheme: Simulated average delay versus arrival rate. . . . 104 4.10 FWOC "Send" Scheme: Simulated average delay versus arrival rate. . . . 104 4.11 FWC Scheme 1: Calculated average CRI length, Ln, versus number of contending packets, n 105 4.12 FWC Scheme 2: Calculated average CRI length, Ln, versus number of contending packets, n 105 IX 4.13 FWOC "Wait" Scheme: Calculated average CRI length, L™, versus num-ber of contending packets, n 106 4.14 FWOC "Send" Scheme: Calculated average CRI length, X*, versus num-ber of contending packets, n. . . . . . . . . . . . . . . . . 106 A.l Mean square value of the number of slots used to resolve a collision between n packets, L^ , versus n for the 2-Group FWC with no capture 119 A.2 Mean square value of the number of slots used to resolve a collision between n packets, L^ , versus n for the 2-Group FWOC with no capture 120 A.3 Continuous Capture Model 2.1 FWC Scheme 1: Mean square value of the number of slots used to resolve a collision between n packets versus n, with different capture ratio, c 121 A.4 Continuous Capture Model 2.1 FWC Scheme 2: Mean square value of the number of slots used to resolve a collision between n packets versus n, with different capture ratio, c. . . . . . . . . 122 A.5 Continuous Capture Model 2.1 FWOC "Wait" Scheme: Mean square value of the number of slots used to resolve a collision between n packets versus n, with different capture ratio, c 123 A.6 Continuous Capture Model 2.1 FWOC "Send" Scheme: Mean square value of the number of slots used to resolve a collision between n packets versus n, with different capture ratio, c 124 x Acknowledgement I am cordially grateful to my research supervisor, Dr. Cyril Leung, who has been my mentor and has patiently guided me throughout my research with many helpful sugges-tions, advice and constant supervision as well as enlightening teaching. I would also like to thank my colleagues Paul Chan, Carson Lam and Victor Wong for their support and useful suggestions. Last but not least, I would like to thank my family and friends for their unlimited support. X I Chapter 1 Introduction The study of multiple-access (MA) communications began about 20 years ago in [1]. One of the first MA protocols to be developed was ALOHA [2]. Its main application is in the area of mobile packet radio, satellite and computer communications. Multiple-access refers to the shared use of a single communication channel by a number of users as shown in Fig. 1.1, where several transmitters transmit information through a multiaccess channel to a single receiver. Some common applications are illustrated in Fig. 1.2. The basic idea behind multiaccess communications is the sharing of a single channel by multiple users in order to achieve a more efficient utilization of channel resources; however, this sharing poses a problem because when several users try to simultaneously access the channel, a collision or conflict occurs. The messages involved in a collision may be destroyed and may need to be retransmitted. Collision resolution algorithms (CRAs) address this problem by allocating the channel among users according to a certain set of rules so as to reduce the chance of collision. There are basically 3 types of CRAs [1, 3, 4], namely 1) unslotted/slotted ALOHA [2], [5], 2) splitting/tree algorithm [6]—[11] and 3) carrier sensing multiple access (CSMA) [12]. According to [6], three properties that reflect the performance of a CRA in a multiple access channel are: 1 Chapter 1. Introduction 2 Transmitters Receiver Multiaccess Channel Figure 1.1: Multiaccess Channel 1. Average throughput: The ratio of the number of packets that are successfully transmitted in a very long time interval to the maximum number of packets that could have been transmitted with continuous transmission on the channel. 2. Average delay1: The ratio of the total delay experienced by the packets in a very long time interval to the number of packets in the interval. The delay is the time from the instant that a packet arrives at a source to the instant that it is successfully received. 3. Stability: The system is kth order stable if the first k moments of the delay of a randomly chosen packet are finite. 1 Since we are only dealing with a single packet from each user, the order in which packets are received is not critical. Chapter 1. Introduction 3 The ideal multiaccess system should have a high average throughput, small average delay and at least first order stability. 1.1 Mult iple Access Mode l The multiple access model used in [4], [6] and [7] are: 1. Slotted System: Each message/packet has the same length and takes exactly one time unit or a t ime slot to be transmitted. All transmitters are synchronized so that the reception of each packet starts at an integer time and ends before the next integer time. 2. Poisson Arrival Process: Packets arrive at the transmitters or nodes following the Poisson distribution with an overall rate A. Given independent arrival processes at the individual nodes, this assumption is reasonable. 3. Collision or Perfect Reception: When two or more packets are sent in the same time slot, a collision occurs and the receiver will be unable to decode or receive any message. When there is only one transmitter sending, the message is received perfectly without any error; this assumes that thermal noise and other channel impairments are negligible. 4. 0 , 1 , COL Immediate Feedback: At the end of each time slot, each transmitter learns via a perfect feedback channel whether there was 0 packet (idle), 1 packet (success) or more than one packet (collision) transmitted in that slot. Although the assumption of immediate feedback is not very practical especially in the case of satellite channels, it is pointed out in Chapter 1. Introduction 4 Satellite Ground Stations (a) Satellite multiaccess channel Primary Secondaries (b) Multidrop telephone line for primary node to poll secondary nodes computer terminals o o o o (c) Multitap bus e.g. in Local Area Network (LAN) Figure 1.2: Examples of Multiaccess Channels Chapter 1. Introduction 5 [1] and [4] that introducing the delayed feedback will only complicate the analysis with little benefit in understanding the working principles of the CRAs. 5. Retransmission of Collided Packets: Each packet involved in a collision must be retransmitted in some later slot; the retransmission of those a packet will continue according to the CRA until the packets are successfully received. A transmitter with a packet to be retransmitted is said to be backlogged [1]. 6. Infinite Set of Transmitters: The system has an infinite set of transmitters or nodes and each new packet ar-rives at a new transmitter. This assumption provides a worst case bound on the performance with a finite set of transmitters. 1.2 Tree Algor i thm In this thesis, we are only concerned with the Tree CRA which is well-known for its stability and higher throughput relative to the ALOHA protocol. The Tree CRA was first suggested by Capetanakis in [6], [7] and [8]. Since then much work has been done based on the idea [11, 13, 14]. The Tree CRA has been categorized as the blocked stack or blocked splitting algorithm in [3] and [1] respectively while [15] describes the unblocked splitting or stack algorithm. One characteristic of the Tree CRA is that during a CRI, all the newly arrived packets have to wait until that CRI is finished before they can be transmitted; that is why these packets are said to be blocked. As a result, the algorithm requires all transmitters to monitor the channel all the time and through the feedback history determine when a CRI ends. The algorithm keeps dividing collided packets into two groups until all packets involved in the initial collision are resolved (see Fig. 1.3). Chapter 1. Introduction 6 This type of tree is known as the static binary tree. As one can see, the pattern of division forms a tree-like structure and the root of the tree is where the initial collision occurs. The set of collided packets is divided into group '0 ' and group ' 1 ' with the transmitters in group '0 ' transmitting first; if there is still a collision, the group is further divided. Therefore nodes with more than one packet will always have two branches. From Fig. 1.3, subsets are formed according to which group nodes belong to after a division. There are a number of ways to divide the collided group e.g. by nipping a coin or by the arrival time of packets. In this thesis, we choose the coin flipping method to divide the collided packets. It should be noted that both Fig. 1.3(a) and Fig. 1.3(b) are the time-line diagrams corresponding to the same tree. The difference is that in Fig. 1.3(a) the process of transmission occurs in slot pairs right after each split as suggested in [6] , while in Fig. 1.3(b) transmissions are in the order of priority i.e. nodes in group '0 ' or with prefixes '0 ' will transmit first until they are successful before nodes with prefixes ' 1 ' can transmit. In other words, the way transmissions take place in Fig. 1.3(b) will take care of the left branch(es) of the tree first and then go to the right branch(es). As one can see, both Fig. 1.3(a) and Fig. 1.3(b) give the same number of CRI slots. Therefore, for ease of understanding the algorithm and the analysis, we will be using the approach in Fig. 1.3(b) to find the average CRI. In chapter 2, we will discuss the implementation of the static binary tree algorithm. The dynamic tree (DT) algorithm [6], [7] has been proposed as a way to improve performance. In DT, the root node may be divided into more than two groups depending on the feedback information; all other nodes remain binary tree structured. For ease in describing the tree CRA, some definitions have to be made [7]: Depth or Level of a node - the number of branches between the node and the root node. The root node is at depth zero. Chapter 1. Introduction 7 Degree of node - the number of branches that emanate from a node. 1.3 Capture Effect When two or more packets collide, there is still a chance that one of the packets will be successfully received by the receiver. This phenomenon is known as the capture effect and may be due to one packet being received at a much higher power level compared to the interference caused by the others. The difference in power level could be the result of terminals transmitting at different distances from the receiver e.g. mobile terminals scattered over an area around a base station. There are basically two type of capture models: 1. Group or Discrete Capture: where transmitters are divided into a number of differ-ent power groups. If there is a collision but only one packet is from the strongest power group, that packet will be captured. This type of capture has been studied using slotted ALOHA in [16, 17], the unblocked splitting algorithm in a slotted ALOHA broadcasting network [18] and the blocked splitting algorithm in [19]. 2. Continuous Capture: where packet transmissions are at the same power level. But the packets may be received at different power levels. A capture for transmitter k occurs if: r, > c £ r, (i.i) where i is the number of packets, Tj,j = 1,2, . . . , i is the received power of a transmitter or mobile j and c is the capture ratio. The probability of capture depends on the distribution of the received power from each transmitter as well as Chapter 1. Introduction 8 Group/Subset '0' = '0' Group/Subset ' 1 ' = '1 ' Collision = Col. Success = Sue. Col. '00* Col. '0' '01' Idle Sue. Sue. m Root node, Col. '10' Col. S ' 1 0 0 ' / Coi. d iCol. \ ' 1 1 ' , \ Sue. \'ior Sue. • . depth or level = depth or level = depth or level = depth or level = depth or level = 0 1 2 3 4 Sue. Sue. The corresponding time-line diagrams:: Sue. Sue. original Col. '0' '1 ' Col. Col \ 1 '00' *01'. '10' '11' Col. Idle; Col. Sue 1 1 1 \ .'100' *ioi: Col. Sue.; Sue. Sue. \ H 1 1 0 8 10 12 (a) Transmit in grouped pairs Time slots original '0' '00' '01' ' 1 ' '10' '100' '101 ' ' l l ' Col. Col. Col. Suc.Suc. Id le C o l C o l C o l Sue. Sue. S u c S u c 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 2 4 6 8 10 12 T i m e s l o t s (b) Rearranged so that one branch is Suc. before going to another branch Figure 1.3: Static Tree CRA Chapter 1. Introduction 9 the number of transmitters. This capture probability approach was used in [20] for the splitting algorithm. On the other hand, some more sophisticated and realistic continuous capture models are studied in [21] using slotted ALOHA. 1.4 Organization of thesis In this thesis, we will study the throughput performance of tree algorithms with the continuous capture model using both the static binary tree and the optimum dynamic tree protocols. The target is to improve the inbound channel throughput performance in a packet radio system. In chapter 2, existing 2-Group capture results will be extended to 3-Group capture and to a finite capture model. Then we will study the different schemes using Feedback With Capture (FWC) and Feedback Without Capture (FWOC) for the continuous capture model in chapter 3. Where possible, comparison with the group capture results are made. In chapter 4, the optimum dynamic tree algorithm using the continuous capture model is studied. The static binary tree results are incoporated to find the average CRI length which is then used to estimate the maximum achievable throughput. Simulation results giving plots of the average packet delay versus arrival rate are used to verify the calculated results. Finally, a conclusion and some future development suggestions are given in chapter 5. Chapter 2 Discrete Capture Model In this chapter, the discrete capture model based on using the Tree CRA [19] will be discussed. The idea behind the discrete capture model is to divide the transmitters within the network into a finite number of priority groups, e.g. 2-Group or 3-Group. It is assumed that a capture never occurs within the packets of the same group. Each packet carries its group identity number. With a slotted system, the following events may occur: 1. Idle slot: no transmitter transmits during the slot. The base station sends back a 0 feedback message to indicate this. 2. Success slot: exactly one packet transmits and the packet is successfully received. The base station sends back a 1 feedback message to indicate this. 3. Collision slot: two or more packets use the channel but no packets can be recon-structed at the receiver. All packets must be retransmitted at some later time. The base station sends back a COL feedback message to indicate this. 4. Capture slot: two or more packets use the channel and one of the packets is suc-cessfully decoded at the receiver. The base station sends back a CAPT feedback message to indicate this. The other packets have to be retransmitted later and are 10 Chapter 2. Discrete Capture Model 11 said to form a capture set after the capture slot. Note that since capture cannot occur within the same group, the remaining packets that form the capture set will have a different group identity number from that of the captured packet. Suppose that the transmitters are divided into M priority groups. A capture occurs when a collision involves only one higher priority group packet and any number of lower priority group packets. This capture criterion is called the discrete infinite capture be-cause a packet can withstand interference from an unlimited number of packets from the lower priority groups. The discrete finite capture model is a more realistic model because for a group i packet to be captured, only up to a certain number, Kij, of group j (j > i1) interfering packets can be tolerated. To incorporate the discrete capture model with the static binary Tree CRA, we need to understand the implementation of the CRA. 2.1 Implementat ion of the Stat ic Binary Tree C R A The rooted binary tree structure in Fig. 2.1(a) represents a particular pattern of idles, successes and collisions resulting from a sequence of splittings. S (at the root node) represents the set of packets in the original collision, i.e. the first slot of the CRI. Each node in the tree corresponds to a subset (perhaps empty) of backlogged packets. Nodes whose subsets contain two or more packets have two branches corresponding to the splitting of the subsets into two new subsets; nodes corresponding to subset with zero or one packets are leaf nodes of the tree. The transmission order of the packets corresponds to that of a stack. When a collision occurs, the subset involved is split and each resulting subset is pushed onto the stack (see Fig. 2.1(a)) (i.e. each stack element is a subset of nodes); then the subset at the xIt is assumed that the lower the group number of the packet, the higher is its priority. Chapter 2. Discrete Capture Model 12 head of the stack (i.e. the most recent subset pushed onto the stack) is removed from the stack and transmitted. Note that a node with backlogged packets can keep track of when to transmit by using a stack counter, SC, which indicates the position of the packet's current subset in the stack. Whenever a packet from a transmitter T is involved in a collision, T"s SC is set to 0 or 1 depending on the outcome of its flipping as follows. If T flips '0 ' its SC is set to 0 while if T flips ' 1 ' its SC is set to 1. A packet is transmitted when its counter is 0; if the counter is nonzero, it is incremented by 1 for each collision detected from the channel and decremented by 1 for each success or idle detected from the channel. This series of action is made possible by the immediate feedback assumption. By keeping track of its own SC, T should know when to transmit its backlogged packet. As the feedback messages play such an important role in the CRA, it is essential to know the kind of feedback information the system is capable of providing. Following [19], we consider two feedback models: 1. Feedback with capture (FWC) in which the receiver can tell the difference between a success slot and a capture slot. 2. Feedback without capture (FWOC) in which the receiver cannot distinguish be-tween a success and capture slot. In either case, it informs the transmitters that the slot was a success slot. It should be noted that results for these two feedback models appear in [19]. The results for FWC are reproduced in section 2.2 because the same approach will be used to extend the results to the 3-Group case as well as the discrete finite capture later in the chapter. Since in section 2.2.2, the average CRI length is used to find the maximum achievable system throughput, it is necessary to clearly define when a CRI starts and ends. For both FWC and FWOC, the CRI is the interval from an initial collision until Chapter 2. Discrete Capture Model 13 Group/Subset '0' Group/Subset ' 1 ' Collision = Col. = '0' = ' 1 ' Success = Sue. Root node. Original Col. Vi / Za\.m/ W/ Sue. • J '010 ' / Idle • J '0110/ / • J 1 s '1' •01. Idle ' Col. '011' ' Col. '0111' » Slot 1 2 3 4 5 6 7 8 9 XmitSet S '0' '00' •or '010' 'Oil' '0110' '0111' T Waiting Sets in Stack (SC) none (0) ' l ' ( l ) ' 0 r ( l ) , T ( 2 ) ' l ' ( l ) •011'(1),'1'(2) ' l ' ( l ) '0111'(1),'1'(2) " I ' d ) none (O) SP 0 1 2 1 2 1 2 1 0 Feedback Col. Col. Sue. Col. Idle Col. Sue. Sue. Idle (a) An example show ing the operation of the stack, SC and SP in the Tree CRA original '0' '00' '01' '010' '011' '0110' '0111' T Col. Col. Sue. Col. Idle Col. Sue. Sue. Idle H 1 1 1 1 1 1 1 l(T I Start of CRI End of CRI L CRI length = 9 slots (b) Corresponding time-line diagram showing the CRI Time slots Figure 2.1: An example of using the Tree CRA to resolve a collision. this collision is resolved, as shown in Fig. 2.1(b). Since a capture may or may not occur in the initial collision slot, a CRI can start with either a collision or capture slot. A CRI is said to be completed when a success or an idle slot occurs with no remaining elements (subsets) in the stack. Every transmitter in the system uses a stack pointer (SP) to monitor the end of a CRI. The SP is a global parameter used to indicate the number of elements in the stack with SP = 0 indicating an empty stack. In order to know the end of a CRI, all transmitters (not just those involved in a collision) update their SP2 . Before a CRI begins, the value of SP is zero. In FWC, regardless of the scheme used, the SP is 2Noted tha t SCs, on the other hand, are updated only by those t ransmit ters involved in a collision and may have different values. Chapter 2. Discrete Capture Model 14 incremented by 1 whenever there is a collision, decremented by 1 (if SP > 0) after each success or idle and remains unchanged for a capture. When the SP is decremented back to zero, a CRI is said to be completed. Depending on the scheme used in FWOC, the SP is updated with a different rule as discussed in section 2.4. 2.2 Feedback W i t h Capture ( F W C ) In section 1.1 assumption 4, we have the general 0,1,COL feedback situation. It has been shown in [22] that more feedback information can yield a better performance, e.g. if the receiver can distinguish between a capture slot and a success slot and send the respective CAPT and 1 (success) feedback. The reason is because a CAPT feedback means there is at least one more packet left in the capture set while the 1 (success) feedback indicates the last packet in a subset/branch of the tree has been transmitted. Fig. 2.2 shows a flow chart of the algorithm. Basically, as each transmitter keeps track of its stack counter (SC) and stack pointer (SP), it can determine when to transmit and when a CRI ends. Note that in this case, there are four possible feedback messages: idle (0), success (1), collision (COL) and capture (CAPT). The value of SC is not changed when a CAPT feedback is received. A new packet which arrives at a node N* during a CRI is not transmitted by N* until the end of that CRI. Two possible schemes to handle the packets in the capture set after a capture slot have been suggested in [19]. 1. In Scheme 1 the tree CRA is carried out after the capture slot. The packets in the capture set are split by flipping a coin with a certain bias. The bias depends on the group the transmitter belongs to. 2. In Scheme 2, the packets in the capture set are immediately retransmitted after the Chapter 2. Discrete Capture Model 15 <s--> TREE CRA: SPLIT INTO 2 GROUPS (0 & 1) PUSH GROUP 1 TO STACK AND SET THEIR SC = SC + 1 & ALL SP = SP + 1 CRI STARTS V GROUP 0 TX. SC = STACK COUNTER SP = STACK POINTER COL. = COLLISION SUC.=SUCCESS -<r NONZERO SC = SC - 1 NONZERO SP = SP-1 PACKETS WITH SC = 0 TX. CAPT NO MORE ELEMENTS ON STACK END CRI Figure 2.2: Flow diagram of Tree CRA using a 2-Group capture model. Chapter 2. Discrete Capture Model 16 capture slot. 2.2.1 Analyt ical Resul t s for 2-Group Infinite Capture Model In the 2-Group case, packets are divided into 2 groups: the dominant group (DG) and the non-dominant group (NDG). Let X be the total number of packets transmitted (involved in a collision) in the first slot of a CRI. Suppose Y (Y < X) of these packets belong to the DG. Let Z be the length (in slots) of the CRI. Note that X, Y and Z are random variables. The average number of slots needed to resolve a collision involving n nodes, of which k (k < n) belong to DG and n — k belong to NDG can be written as: Ln,k = E[Z/X = n,Y = k]. (2.1) Equation (2.1) is used to find the average CRI length to resolve a collision involving n packets. It can be shown [19] that this can be used to obtain the maximum achievable throughput of the system. When there is a collision between n, n > 2, NDG packets and none from the DG, i.e. k = 0, we need to split the packets. By letting PNDG be the probability of flipping '0 ' by a NDG node, we can write the probability that j of these n colliding packets flip '0' as: PnDGU)= U \P3NDG^-PNDGT-\ 0 < j < n. (2.2) As a result for n > 2, the average conditional CRI length if there are n users and no one is from the DG is: £n,0 = 1 + E P?D°ti) fo,0 + Ln-i,0] • (2-3) 3=0 Chapter 2. Discrete Capture Model 17 A is captured B flipped'!' B 1 idle OR 0 Time slots L 2 i l = 3 A is captured B flipped '0' B '0' A - DG packet B - NDG packet '0' - flipped '0' 1'-flipped '1' idle Time slots 1,2, = 3 (a) Scheme 1: Flip after capture A is captured A B'O' C O ' £ L n , l ( b ) L n , l = 1 Ln-1,0 Time slots B'O' CO' Jn-1,0 A - DG packet B AND C - NDG packets '0' - flipped '0' '1. '- flipped '1' Time slots Figure 2.3: FWC Scheme 1: Time-line diagram showing CRI of (a) L2,i, (b) Ln,i, n > 3. Rearranging, we have: Ln,o — 1 - PnNDG(n) - P»™>(0) We will make use of (2.4) to derive Ln>k. 2.2.1.1 S c h e m e 1 (2.4) To find the average conditional CRI length, Ln^, recursive relations can be estab-lished. Consider first the case for n — 2 and k = 1, i.e. there are two packets involved in a collision, one from the DG and another from the NDG. A capture will take place in Chapter 2. Discrete Capture Model 18 the first slot of the CRI and according to Scheme 1, the remaining nodes in the capture set (one in this case) will split again. As a result, another two extra slots will be used to resolve the collision (see Fig. 2.3(a)), so that L2,i = 3. (2.5) Next consider one packet from DG and n — 1 from NDG, n > 3. Again a capture occurs in the first slot of the CRI, and the remaining n — 1 NDG packets will need to be retransmitted. Since the initial slot is a capture slot, (see Fig. 2.3(b)), we have Ln,i = Ln-i,o n > 3. (2.6) Let PDG be the probability of flipping '0 ' by a transmitter from the DG. Then the probability that i of k colliding DG packets flip '0 ' is k^ pkD%) ; fDG{l-PDGr\ 0 < i < k. (2.7) The probability that exactly i of k packets from the DG and j of n — k packets from the NDG will flip '0 ' is QnMi) = P^TU)Pk>G(i)- (2-8) For 2 < k < n, the expected conditional CRI length is then given by k n—k Ln,k - 1 + ~^2^2 Qn,k(j,i)[Li+j,i + i/n_t-_j,fc_j]. (2.9) ;=o j=o Chapter 2. Discrete Capture Model 19 A is captured B does not flip Tx. again A - DG packet B - N D G packet '0' - flipped '0' T - flipped '1' 0 Time slots L 2 , - 2 (a) Scheme 2: L 2 1 = 2 A - DG packet B and C - NDG packets '0' - flipped '0' 1 ' - flipped '1' A is captured Nobody flips Both B and C tx. again, resulting in a collision 0 Time slots - X Jn,l slot wasted (b) Immediate transmission costs one extra slot for n > 2, Ljj 1 = 1 + L ^ J Q Figure 2.4: FWC Scheme 2: Time-line diagram showing CRI of (a) i/2,i, (b) Z/n?i, n > 3. from which we have, E k v^n—k v^A; sr^n—k -1 + Qntk(j,l)Li+jj + Qn,k(J'l)Ln-i-j,k-Ln,k — (i,j)^ (k,n-k) (*,i)/(o,o) 1 - <5n,*(0,0) - Qn,k(n-k,k) (2.10) Equations (2.4)-(2.10) together with the initial conditions Lo,o = -^ 1,0 = -^ 1,1 = 1) can be used to determine Ln<k recursively for FWC Scheme 1. Some numerical results are presented in section 2.2.3. Chapter 2. Discrete Capture Model 20 2.2.1.2 Scheme 2 In Scheme 2, all packets in a capture set are retransmitted immediately. If there is only one packet in the capture set, it will be successfully transmitted in only one slot instead of two as required in Scheme 1 (see Fig. 2.4(a)). As a result, £2,i = 2. (2.11) However, one slot is wasted (see Fig. 2.4(b)) if the capture set has more than one packet. We then have Ln,i = 1 + £n_i,o n > 3. (2.12) Using (2.2)-(2.4), (2.7)-(2.12) and the initial conditions L0,o = Llfl = L1A = 1, we can obtain Ln^ for FWC Scheme 2. 2.2.2 Maximal Average Throughput for Poisson Arrival Process We will now make use of the average conditional CRI length, Lntk, to find the average CRI length and the maximal average system throughput. Consider a Poisson arrival process. Let the arrival rates of the DG and NDG packets be XQG a n d XNDG respectively. Let the total arrival rate be Ax = XDG + ^NDG and the fraction of DG packets be ct = XDG IXT- Then the average CRI length given that n packets collided in the initial slot is L(:] = $ > n , * l a * ( l - i * ) " - f c (2.13) fc=o \ k i Chapter 2. Discrete Capture Model 21 where ak{\ — a)71 k = Pr{& out of n packets are in the DG}. To find the maximal average throughput, let L(i, a) be the random variable that denotes the length (in slots) of the iih CRI for a given ex. As stated in [23], the resulting Markov chain {L(i,a)} is ergodic whenever there exists N, e > 0 such that E[L(i + l,a) | L(i,a)=j] < (1 - e)j, V j > N. (2.14) For the Poisson arrival process, (2.14) becomes £ E[L(i + 1, a) | no. of arrivals in ith CRI = n) • ^ ^ {eXP ^Tj)} n~0 n! v^ M{\Tj)n{exp-{\Tj)} < ( l - e ) j , Vj > N. (2.15) From [19], a linear bound on the expectation is assumed to be 4 a ) < a(a)- n+ 6(a). (2.16) Substituting (2.16) into (2.15) we have iw . ) . , + K.)).'w'''»'-'w» = %).E(A"T<exr(Ar,)} + 0 1 ti t r\ IV • Tl=0 , v f (ATj)" {exp - (XTJ)} a(a) • ^ n = b(a) + a(a) • AT • j < ( l - e ) i , Vj > N. (2.17) Chapter 2. Discrete Capture Model 22 Dividing both sides of the inequality (2.17) by j , we have - ^ + a{o) • AT < 1 - e V j > N. In the limit as iV —* oo, we have AT < l/a(a) if e < 1. (2.18) We would like to maximize AT to obtain the maximum average system throughput, AT- The RHS of (2.18) is maximized by choosing a(a) to be as small as possible. In fact, the RHS of (2.16) as a function of n is a straight line with slope a(a) and y-intercept b(a). The way to do this is to calculate L^ using (2.13) for a fixed value of n as a function of a. Then a(a) can be calculated from (2.16). Finally, the inequality (2.18) is checked to see if the system is stable or not. It is also true that a first order stable system has a finite average delay. To simplify the notation, instead of L{i, a), we let /,• be the length of the ith CRI. From [6], the lower and upper bounds of the average delay, E[S], for the binary static tree with no capture are: E[S] < 1 . 0 5 - J - ! + 0.321 E[l\ 1 Ell2] 1 E® s rim + 2 - m (2'19) Chapter 2. Discrete Capture Model 23 E[l] and E[l2] are the steady state first and second moment of Zj. i.e. E[l] = l im^oo E[lk\ and E[l2] = liniit_+oo E[ll]. In Appendix A it is shown that E[l] and E[l2] are finite so that the system has a finite average delay. As a result, to find the maximal throughput of a system with n transmitters, we need to know the longest average CRI length for that system i.e. the average CRI length involving all n transmitters. This is a very useful and handy technique to find the maximum stable throughput and will be used throughout this thesis. 2.2.3 F W C : 2-Group Finite Capture Model In the above section, the capture model discussed is an infinite one; a DG packet which is involved in a collision with any number of NDG packets is captured. This assumption is somewhat unrealistic. Finite capture models have been studied for ALOHA systems [17]; we will now study the effect of finite capture on the tree CRA. The finite capture model assumes that capture occurs as long as the number of NDG packets does not exceed a threshold, K. If K is larger than the total number of users, we get back the infinite capture model. For the 2-Group finite capture model, equa-tions (2.4)-(2.10) are still valid; however, we have to replace (2.6) and (2.12) by (2.20). 3 < n < K + 1 : Scheme 1 : Lnt\ = Ln-i,o Scheme 2 : Ln^ = 1 + Ln_i i 0 . n > 3 and n > K -f 1 : For both Schemes 1 and 2 : Chapter 2. Discrete Capture Model 24 El y^ra —1 y ^ l y^n—1 (i,j)?(l,n-l) (ij)? (0,0) LnA ~ 1 - Qn,i(0,0) - QnA(n-1,1) (2.20) By letting PDG = PNDG = 0.5, Table 2.1 is obtained from the analytical results. It can be seen that as n increases, the value of njLn^ approaches the maximum average throughput. As a result, we choose n = 48 for all the calculations in this chapter to get an accurate result with a reasonable computation time. Fig. 2.5 and Fig. 2.6 show plots of njLn>k versus k, the number of DG packets for FWC Scheme 1 and 2 respectively. The maximum value of njLn^ gives an estimate of the throughput. Since k and n are analogous to XQQ a n d Ay, the optimum a then equals kjn. As a result, the average CRI length, and thus the maximum throughput can be found using (2.13), (2.16) and (2.18). Fig. 2.7 and Fig. 2.8 are the plots of average CRI length, L^\ The maximum throughput is given by the reciprocal of the slopes of the L)™> curve. Table 2.2 shows the throughput of the discrete infinite and finite capture model. Note that each plot in Fig. 2.7 and Fig. 2.8 is almost a straight line whose slope does not change much as n increases, indicating the maximum average throughput is expected to be the same with increasing n. Table 2.2 shows that the optimum value of a is smaller in Scheme 1 than in Scheme 2. Table 2.2 also suggests that for K > 4, the finite and infinite capture models have almost the same throughput. When all packets belong to the same group or K = 0, we have the no capture case. As a result, Lnfi — Ln>n = Ln^ — Ln. For scheme 2, when K equals 1 and 2, the maximum throughput achievable is even greater than the infinite capture model. This phenomenon was verified by simulation and Chapter 2. Discrete Capture Model 25 n 16 32 48 64 80 96 k = [n • a\ 6 13 19 26 32 39 n/Lnjk 0.435 0.427 0.424 0.422 0.422 0.421 Max. Avg. Throughput 0.414 0.417 0.417 0.417 0.417 0.418 Table 2.1: Table showing the effect on njLn^ and maximum average throughput as n increases in the infinite capture model with optimum a = 0.41 and k = \n • a\. K is the number of NDG packets tolerable for a capture in finite capture model i 0.35 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 k Figure 2.5: FWC Scheme 1: n/Ln,k versus number of nodes from the DG (k), n = 48. J I I I I I I I I I I I I I I l L J l__l_ i Chapter 2. Discrete Capture Model 26 I K is the number of NDG packets tolerable for a capture in finite capture model 0.45 0.4 0.35 (r 0.3 inite capture — K = 6 — —-E3 — K = 3 -K = 2 — K = l — •--•A---A— J I I I I L J L _ L 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 k Figure 2.6: FWC Scheme 2: n/Lntk versus number of nodes from the DG (k), n = 48. K is the number of NDG packets tolerable for a capture in finite capture model 0 0 I — I c* u 00 C3 >-H > < 140 130 120 110 100 90 80 70 60 50 40 30 20 10 0 Infinite capture, alpha=0.41 K = 6,alpha=0.41 K = 5, alpha=0.41 K = 4,alpha=0.41 K = 3, alpha=0.42 K = 2, alpha=0.44 K = 1, alpha=0.5 No capture, alpha=0 or 1 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 n Figure 2.7: FWC Scheme 1: Ln versus total number of nodes (n) up to n — 48. Chapter 2. Discrete Capture Model 27 is the number of NDG packets tolerable for a capture in finite capture model 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 n Figure 2.8: FWC Scheme 2: Ln versus total number of nodes (n) up to n = 48. K 0, i.e. no capture 1 2 3 4 5 6 oo, i.e. oo capture Scheme 1 Optimum Of 0 or 1 0.50 0.44 0.42 0.41 0.41 0.41 0.41 Maximum Average Throughput 0.344 0.394 0.410 0.415 0.416 0.4167 0.4168 0.4169 Scheme 2 Optimum a 0 or 1 0.50 0.51 0.52 0.52 0.52 0.52 0.52 Maximum Average Throughput 0.344 0.425 0.421 0.420 0.420 0.420 0.420 0.420 Table 2.2: FWC: Maximum average throughput of infinite and finite capture model. K 60 c u <D W) S-i > < Chapter 2. Discrete Capture Model 28 the explanation is as follows. When the probability of capture decreases due to the finite capture, splitting occurs more frequently; it turns out in Scheme 2 (when K = 1 or 2), the no capture case always results in a shorter average conditional CRI length (thus a shorter average CRI length) than the case when a capture occurs. This can be shown in the following example, where consider L34 for Scheme 2. From (2.20), we have Infinite Capture: £3,1 — 1 + 1/2,0 From (2.3), we note that -^ •2X1 — 5 . Therefore, £3,1 = 1 + 5 = 6. Finite Capture, K = 1: y>l v ^ 3 - l r ^ l v->3-l 2^i-o ^ j = 0 „ , . .s T , ^i=0 ^j-0 „ / • -\ r ( i , j ) ^ ( 1 , 3 - 1 ) (i,j) 7^(0,0) -^3,1 — 1 - Q3)i(0,0) - g 3 ) i ( 3 - i , i ) _ 1 + f + ¥ 6 8 = h\ = 5.67 < 6. Thus with finite capture the average conditional CRI length, I/34, is less than that of the infinite capture case! Chapter 2. Discrete Capture Model 29 2.3 F W C 3-Group Infinite and Finite Capture Mode l The 2-Group capture model is a simple case of the discrete capture model. In general, the idea can be extended to M-Group capture model and as M gets larger the throughput should also increase. The analytical procedure is basically the same but the complexity of the equations will grow linearly with M as suggested in [19]. To get an idea of how much improvement and how complex the problem becomes, we will look at the 3-Group infinite and finite capture model. 2.3.1 Analyt ical Resul t s for 3-Group Infinite and Finite Capture M ode l Again, we would like to find the average conditional CRI length. In this case, the nodes are divided into three groups: group 1 (the most dominant group), group 2 and group 3 (the least dominant group). Table 2.3 gives the capture conditions for the 3-Group capture model. K{j is the number of group j packets that a group i packet can withstand (i < j < M, M = 3 in this case). The value of K,-j varies according to the priority difference between i and j , so a group 1 packet can withstand more interfering packets from group 3 than from group 2 (i.e. Kl2 < K^)- In our analysis, we assume K\2 = K2Z and K13 = 2 • K\2. In our model, K12 is assumed to be independent3 of the number of group 3 packets, in the sense that even if there are no group 3 packets presented, a group 1 packet can still only withstand Ki2 group 2 packets for a capture to occur. Let n be the total number of packets involved in the initial collision and k1, k2 be the number of packets from group 1 (most dominant) and group 2 (second dominant group) respectively. Now, the modified equations and initial conditions to find the average 3In practice, the number of interfering packets that can be tolerated by a more dominant group packet depends on the total interference power experienced. [17] treats this matter in the ALOHA system. Chapter 2. Discrete Capture Model 30 No. of Group 1 packets (k\) > 1 = 1 = 0 = 0 = 0 = 0 No. of Group 2 packets (k2) X X < #12 > 1 = 1 = 0 '= 0 No. of Group 3 packets (£3) X X < K13 X X < #23 = 1 > 1 Captured Packet Id. no capture h no capture k2 h no capture Table 2.3: Summary of the capture condition in a 3-Group capture model where X is some positive integer. conditional CRI length are given below. GSl Lnflfi _ 1 + T?3 PrU)Ljfifi + EUPnU)Ln-3Pfi (2.21) 1 - P«3(n) - PnG3(0) Let PGI be the probability of flipping '0 ' by a group i (1 < i < 3 in the 3-Group model) transmitter. The respective probabilities that i of kx group 1 packets, j of k2 group 2 packets and k of n — k\ — k? group 3 packets flip '0 ' are: A?(0 pgti) ^n-fci-fc2(^) — h PGlCl-PGl)* 1 - ' , PUl - PG2)k^, PGsi1 -PG3 0 < i < h. 0 < j < h. \n—k\—k2 — k 0 < k < n — k\ — k2-(2.22) For poi = PG2 = PG3 = 0.5 and PDG = PNDG — 0.5, (2.21) is the same analogous to (2.4) in the sense that in both cases, all the packets are from the least dominant group Chapter 2. Discrete Capture Model 31 and with all the probability of flipping '0 ' equals 0.5, we have, therefore Ln,o,o = Ln<0. (2.23) The probability that exactly i of kx nodes from group 0 and j of k2 nodes from group 2 and k of n — k\ — k2 nodes from group 3 will flip '0 ' is QnMJ»(iJ, *) = P^kt-bWPgWPg1®. (2.24) As a result, for ki > 2, k2 > 1, n > 3 and fcx + &2 < n: *Jn,ki,k2 1 + A + B 1 - Qn,hM(°>0,0) - Qn,k1,k2(n-k1-k2,kl,k2) where E k\ ^^ &2 v^n — k\~k2 j'=0 2-^j=0 2^k=0 „ {' ' h\T (hj,k) J^ (h,k2,n- kx - k2) E k± v^&2 v^7i—&i — A?2 _ i=oL;=o^=o n (• • hM & — ltfn,ki,k2\^i J i ":)J-'n—i—j — k,ki—i,k2—j-(ij,k)^ (0,0,0) For n > 3 and &i = A;2 = A; > 2, we have: J->nfi,k2 — ^n,k\,0 (2.25) Chapter 2. Discrete Capture Model 32 E k y-»n—k y^fc y^n—fc i _L i=0 i=0 n t • -\ T _L i = 0 j=0 n t • -\ T 1 "t" ^ntk{J,'l)J-'i+jli -T ^n:k(J,l)-Lin-i-j,k-i (i,j) / (k,n-k) ( M ) ^ ( 0 , 0 ) For n > 3, 1 - Qn,k(0,0) - Qn,k{n- k,k) £2,1 ,0 -3 Scheme 1 i / 1 < # : 13 ^ 2 , 0 , 1 — < ^ 2 , 1 , 1 2 Scheme 2 [ (2.26) if 1 > 7^3 3 Scheme 1 if I < K13 2 Scheme 2 I (2.26) if 1 > #1 3 3 Scheme 1 if I < Ki3 2 Scheme 2 ( (2.25) if 1 > AT13 (2.26) (2.27) Ln,\,o — \ Ln-i,o,i Scheme 1 if n-1 < K 13 -1,0,0 Scheme 2 (2.26) i / n - 1 > iJT13 7/n,0,l L-n-1,0 ,0,0 Scheme 1 if n-1 < K-23 1 + Ln-1,0,0 Scheme 2 (2.26) if n-1 > K23. (2.28) For n > 3 , &2 > 2, Chapter 2. Discrete Capture Model 33 Ln-i,< 0,k2 Scheme 1 Ln,i,k2 — ) I 1 + Ln-ifltk2 Scheme 2 (2.25) otherwise. The initial conditions to start the recursion are: if &2 < K\2 and n — 1 — k2 < K 13 (2.29) A),0,0 — -^1,0,0 — -^1,1,0 — -^1,0,1 — 1- (2.30) Using (2.22)-(2.30), Lnikltk2 c a n be calculated. 2.3.2 Throughput for 3-Group Capture Mode l The method to determine the throughput is similar to the 2-Group situation. Assume a Poisson arrival process and n = 48. Let A^i, Ac2 and XQ3 be the arrival rates of group 1, group 2 and group 3 packets respectively. The total arrival rate is Ay — AGI+AG2+A<33. Let the fraction of group 1 and 2 packets be denoted by a and (3 respectively, i.e. A a = P = G\ Ay AG2 A, (2.31) Following (2.13), the average CRI length for the 3-Group model can be written as n n—ii ( „ \ L(«,f}) = y- y- L . j ' l = 0 t2 = 0 n V ?i / n — i\ V ^ a ' 1 / 9 , ' 2 ( l - a - / 9 ) n - , ' 1 - , ' 2 . (2.32) Chapter 2. Discrete Capture Model 34 K12 1 2 3 K13 2 4 6 I<23 1 2 3 oo capture Scheme 1 Optimum a 0.333 0.292 0.271 0.271 P 0.292 0.313 0.313 0.313 Maximum Average Throughput 0.443 0.465 0.470 0.471 Scheme 2 Optimum a 0.333 0.354 0.354 0.354 P 0.333 0.333 0.333 0.333 Maximum Average Throughput 0.474 0.469 0.469 0.469 Table 2.4: FWC: Maximum throughput of a 3-Group infinite and finite capture model. Since we are dealing with 3-Group capture, a 3-dimensional plot is needed to see what values of k\ (group 1 packets) and k2 (group 2 packets) give the maximum throughput. To produce a 2-dimensional plot, the number of packets from group 1 is fixed and nfLn^^ is plotted against k2. Fig. 2.9 and Fig. 2.10 shows the plots for Scheme 1 and 2 respectively. The optimum a and /? are found using the values of k\ and k2 that maximize n/Lntkltk2 plots and dividing them by n (a = &i/ra, /3 = k2/n). Fig. 2.11 and Fig. 2.12 are the corresponding average CRI lengths that yield the maximum throughputs using the optimum a and /3. From the average CRI length, the same technique from section 2.2.2 is used to find the maximum achievable throughput. The results are given in Table 2.4. 2.4 F W O C : 2-Group Capture Model In the FWOC case, the receiver cannot distinguish between a capture slot or a success slot. Therefore in FWOC, a success slot as well as a capture slot result in the same feedback, success (1). In FWC, SP is checked after each success (1) feedback and when SP = 0 it indicates the end of a CRI. However, with FWOC the main difficulty is to tell when the CRI ends since the success (1) feedback does not guarantee the last packet has been sent because it might be a capture slot which means there are more packets to be transmitted. To avoid the premature ending of the CRI, the SP is checked Chapter 2. Discrete Capture Model 35 K is the number of NDG packets tolerable for a capture in finite capture model 0.53 M 0.48 0.43 -0.38 Infinite capture K12 = K23 = 3,K13=6 A K12 = K23 = 2,K13 = 4 A K12 = K23 = 1,K13=2 A Figure 2.9: FWC Scheme 1: 3-Group capture model, n/Ln^^ versus ki with k\ — 13, n = 48. ' '. Kij is the number of group j packets that can be tolerated by group i for a capture to occur 0.48 0.43 0.38 Infinite capture K12 = K23 = 3, K23 = 6 K12 = K23 = 2,K13=4 K12 = K23 = 1,K13 = 2 J_ J . _L _|_ 0 10 25 ± 30 15 20 k2 Figure 2.10: FWC Scheme 2: 3-Group capture model, n/Lntkltk2 versus ki with &i n = 48. 35 = 13, Chapter 2. Discrete Capture Model 36 Kij is the number of group j packets that can be tolerated by group i for a capture to occur Oft a U a 3 140 r-130 \-120 j-110 j-100 |-90 |-80 f-70 h 60 t-Infinite capture K12 = K23 = 3,K13 = 6 A-K12 = K23 = 2,K13 = 4 A-K12 = K23 = 1,K13=2 A-J I I I I I I L 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 n Figure 2.11: FWC Scheme 1: 3-Group capture model, average CRI length Ln versus n. Kij is the number of group j packets that can be tolerated by group i for a capture to occur •B c ID 2 l-H > < 140 130 120 110 100 90 80 70 60 50 40 30 20 10 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 n Figure 2.12: FWC Scheme 2: 3-Group capture model, average CRI length Ln versus n. Chapter 2. Discrete Capture Model 37 '0' - Group '0', those flipped '0' T - Group T, those flipped T col = collision sue = success or capture A and D - DG packets B and C - NDG packets D i Hall D B idle col sue sue col sue sue Kr PCRI1 ^K- PCRI2 >K>I k-PCRI3 slots •0' A T A 1 1 D T B •r c V B •r c B C 11 B col sue sue col idle col sue idle K- PCRI1 - 3 * = - PCRI2 x> slots CRI -^ k- CRI PCRI3 >i FWOC: Wait for Partial Conflict Resolution FWOC: Send in The Next Slot Figure 2.13: Examples of FWOC: "Wait for Partial Conflict Resolution" Scheme and "Send in the Next Slot" Scheme. after an idle slot (0 feedback) and SP = 0 indicates the end of a CRI. From [19], there are two possible schemes to tackle this problem, namely, 1) Wait for Partial Conflict Resolution and 2) Send In the Next Slot. The working principles of these two schemes will be discussed to explain the derivations of the analytical results for the infinite capture model, then modifications will be made for the finite capture model. In FWOC, all SCs and SP are incremented by a collision (COL) feedback and decremented with idle (0) and success/capture (1) feedback. Note that only the nonzero SCs and SP are decremented. Since the retransmission of the packets in the capture set are different between the two schemes, so are the rules for setting the SCs for those packets as will be discussed in the following sections. Chapter 2. Discrete Capture Model -> TREE CRA SPLITIN0 2 GROUPS (0 & 1) PUSH THOSE IN GROUP 1 TO STACK SET THEIR SC = SC+1 & ALL SP = SP + 1 CRI STARTS SC = STACK COUNTER SP = STACK POINTER WF = WAIT FLAG COL. = COLLISION SUC. =SUCCESS WF=0 ^_ ENDCRI -> NONZERO SC = SC -1 NONZERO SP = SP - 1 TRANSMITTERS WITH BACKLOGGED PACKETS AND SC = 0 TX. V STARTS CRI IF NOT STARTED THERE IS A WAITING SET ALREADY SO PACKETS IN CAPTURE SET HAVE THEIR SC SET TOSPI.E. SC = SP /£ -> _4L SUC. OR CAPT. CAPTURE OCCURS FOR THE FIRST TIME (SINCE WF = 0) SO PACKETS IN CAPTURE SET WILL BE PUSHED TO THE BOTTOM OF STACK. THEREFORE SP = SP + 1, WF = 1 (DENOTES A WAITING SET EXISTS). CATPURE SET PACKETS SET THEIR SCTOSP, I.E.SC = SP Figure 2.14: Flow Diagram of FWOC: Wait for Partial Conflict Resolution Scheme. Chapter 2. Discrete Capture Model 39 2.4.1 Wait For Partial Conflict Resolut ion Fig. 2.14 shows the flow diagram of the Wait for Partial Conflict Resolution scheme. In this scheme, the CRI is divided into partial conflict resolution intervals (PCRI). The first PCRI ends when all the packets not involved in the initial collision, except those packets from capture sets that were involved in a capture in the first part, have been successfully transmitted. In another words, packets left in the capture set after a capture have to wait (forming a waiting set) until those that are not involved in the capture are transmitted. This point marks the end of the first PCRI. The second PCRI starts with all the packets from the capture set(s) and ends by the same rule that ends first PCRI. This rule applies to all the PCRIs that follow until there is a single idle slot to start a PCRI (empty PCRI) which marks the end of the whole CRI, see Fig. 2.13. If there is a collision within a PCRI, the packets will split according to the tree algorithm. A wait flag (WF) is required in all transmitters involved in a collision in order to know if a waiting set exists. W F = 0 indicates there is no waiting set present, therefore the stack pointer has to be incremented after a success/CAPT, SP = SP + 1, to house the waiting set; and transmitters that have packets in the capture set (which becomes the waiting set) are located to the bottom of the stack i.e. set their SC to SP (SC = SP), then W F is set to 1 to indicate the existence of a waiting set. When W F = 1, SP is not incremented after a success/CAPT and packets involved in the capture will join those in the waiting set by setting their SC to SP. Whenever SP = 0, W F is set to 0 to indicate no waiting set is presented. Other than checking the W F and the necessary update of SC and SP after each success/CAPT, all SCs and SP are incremented by 1 after each collision and decremented by 1 after each idle or success/CAPT (this takes place after the necessary updating of SC and SP according to the W F status.). Chapter 2. Discrete Capture Model 40 To find the average conditional CRI length for this scheme, we have to divide the CRI length into two parts. The first part is the interval needed to partially resolve the initial collision. The second part will be dedicated to resolve the NDG packets that waited because they had been involved in a capture. Let Z and W be the random variables that represent the lengths of these two parts respectively. We define the following conditional means with X and Y as defined in section 2.2.1: Ln,k = E[Z\X = n,Y = k). (2.33) Kk = E[W\X = n, y = k]. (2.34) The average conditional CRI length to resolve a collision with n packets of which k belong to the DG is, Ln,k = ^n,k + Ln>k. (2.35) With (2.5) and (2.6) replaced by (2.36), (2.2)-(2.4), (2.7)-(2.10) can be used to find Ln,k-Ln,i = 1, n > 1. (2.36) The reason why (2.36) holds is because when there is only one DG packet, it will be captured so the first part of the CRI is ended and the initial collision is said to be partially resolved. Note that (2.36) is only valid under the infinite capture model. The problem now lies in finding Lnj.- Let Pnkityi 0 ^ I ^ n — k,be the conditional probability that given n nodes of which k are from the DG transmit in the initial slot of Chapter 2. Discrete Capture Model 41 a CRI, exactly I NDG packets will be left after the first part of the CRI. That means / NDG packets have to wait to be transmitted in the second part of the CRI. The initial conditions of P ^ ( 0 a n (^ the w a y to calculate it is shown in [19]. It should be noted that in [19] no superscripts are used to distinguish the conditional probabilities for the different schemes. When all packets are from the same group, no capture will occur thus the collision is resolved in the first part of the CRI i.e. in Ln^ slots. Therefore no packet is left for the second part of the CRI resulting in an empty slot, so Lnjn = Lnfi = 1. Then Ln^ for n > k > 1 is calculated via Ln,k = PZk(0)Lo>o + E P ; ( I ) ( l + I,,o) (2.37) i=i since the conflict between I nodes from the NDG is resolved on the average of L^Q slots. The reason why for / ^ 0 we have to add 1 to L;?0 is because an extra idle slot is needed to tell the end of the CRI. So far, we have considered the infinite capture model i.e. for the 2-Group case the DG packet can withstand interference an unlimited number NDG packets. For the finite capture case, in which a DG packet can withstand interference from up to K NDG packets, (2.36) and equation (20c) in [19] become L*n,l — 1 n > 1 and n — 1 < K (2.10) n > \ andn > K. ^ l i ( n - l ) = 1 n > 1 and n — 1 < K (22a) in [19] n > 1 and n > K. (2.38) (2.39) Chapter 2. Discrete Capture Model 42 K is the number of NDG packets tolerable for a capture in finite capture model 0.38 i 0.33 I I J I I I I I I I I L J 1 I I I I L 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 k Figure 2.15: FWOC Wait: n/Llk versus number of nodes from the DG (k), n = 48. 0 n > 1 , I = n P^l) = <J0 n > 1 ,0 < / < n - 2, n - l < K (2.40) (22a) in [19] n > 1 ,0 < / < n - 2, n > K. With these changes, the average conditional CRI length for the finite capture model can be obtained using (2.35). Letting pDG = pNDG = 0.5 and n = 48, we obtain plots of n/Llk versus k (number of DG packets) and L^ (found using (2.13)) versus n in Fig. 2.15 and Fig. 2.16 respectively. The throughput results are given in Table 2.5. 2.4.2 S e n d In t h e N e x t Slot Fig. 2.17 shows the flow diagram of this scheme. Basically, as the name implies, all packets belonging to a capture set (i.e. packets remaining after a capture) will retransmit Chapter 2. Discrete Capture Model 43 K is the number of NDG packets tolerable for a capture in finite capture model 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 Figure 2.16: FWOC Wait: Ln versus total number of nodes (n) up to n = 48. in the next slot together with the packets that were supposed to be transmitted. For example in Fig. 2.13, packets in the capture set (B and C) join packet D (which flipped '1') and are transmitted in the next slot. Therefore the packets in the capture set will maintain their SC at zero (SC=0), so they can be retransmitted in the next slot. In this scheme, the rules for updating the SP are the same as those used to update the SC, keeping in mind that SP is a global parameter while each transmitter has its own SC. The CRI in this scheme also consists of PCRIs and other than the first PCRI. Each P C R I starts with packets that were involved in a capture at the last slot of the previous PCRI (see Fig. 2.13). An empty PCRI denotes the end of the CRI. Again, we can divide the CRI into two parts. The first part is to transmit all the DG packets and maybe some (or all) of the NDG packets. The second part is devoted to retransmit the NDG packets that were involved in a capture in the last slot of the first part. These packets are termed residual packets. Chapter 2. Discrete Capture Model -> TREE CRA SPLITIN0 2 GROUPS (0 & 1) PUSH THOSE IN GROUP 1 TO STACK SET THEIR SC = SC+1 & ALL SP = SP + 1 CRI STARTS SC = STACK COUNTER SP = STACK POINTER COL. = COLLISION SUC. =SUCCESS END CRI -> NONZERO SC = SC-1 NONZERO SP = SP -1 TRANSMITTERS WITH BACKLOGGED PACKETS AND SC = 0 TX. A STARTS CRI IF NOT STARTED SUC. OR CAPT. -> PACKETS IN THE CAPTURE SET KEEP THEIR SC = 0 SO THEY CAN BE RETRANSMITTED IN THE NEXT SLOT Figure 2.17: Flow Diagram of FWOC: Send In the Next Slot Scheme. Chapter 2. Discrete Capture Model 45 The same definitions, (2.33)-(2.35), will be used for the average conditional CRI length in this scheme. However, the way in which Ln^ is calculated is not the same as the "Wait" scheme and Pn,k(l)s has to be defined as KAi) Prob < I residual packets n nodes of which k are from the DG transmit at the first slot of a CRI The initial conditions for P^kO) a n d the calculation of Ln^ is shown in (24a)-(24c) from [19]. Similar modifications are made for the finite capture model, so that equations (24c) and (29) in [19] become Pn,i(n-1) = 1 n > 1 and n — 1 < K (26a) in [19] n > 1, n - 1 ^ 0 and n > K. (2.41) P:AI) 0 n > 1, / = n 0 n > l , 0 < / < r c - 2 , n-1 < K (26a) in [19] n > 1, 0 < I < n-2, n > K. (2.42) Ln,\ (2.43) With pDG obtained. 1 n > 1 and n — 1 < K (31a) in [19] n > 1 and n > K. PNDG = 0.5 and n = 48, the plots in Fig. 2.18 and Fig. 2.19 are Chapter 2. Discrete Capture Model 46 K is the number of NDG packets tolerable for a capture in finite capture model II K = 3 A H K = 2 A K = l A 0 3 3 I I I I I I I I I I I I I I L _ l I 1 I I 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 k Figure 2.18: FWOC Send: n/l£k versus number of nodes from the DG (&), n = 48. K is the number of NDG packets tolerable for a capture in finite capture model 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 n Figure 2.19: FWOC Send: Ln versus total number of nodes (n) up to n = 48. Chapter 2. Discrete Capture Model 47 K 0, i.e. no capture 1 2 3 4 5 6 oo, i.e. oo capture Wait Scheme Optimum a 0 or 1 0.50 0.479 0.479 0.479 0.479 0.479 0.479 Maximum Average throughput 0.342 0.373 0.375 0.375 0.375 0.375 0.375 0.375 Send Scheme Optimum a 0 or 1 0.646 0.646 0.646 0.646 0.646 0.646 0.625 Maximum Average throughput 0.342 0.378 0.386 0.389 0.390 0.391 0.392 0.393 Table 2.5: FWOC: Maximum throughput of infinite and finite capture model. Table 2.5 shows the maximum average throughput for FWOC. Also if there is no capture the average CRI length, Ln, of FWOC is one slot more than that of FWC owing to the extra slot used to distinguish the end of the CRT So in the no capture case, FWOC has a lower maximum average throughput than the FWC. 2.5 Throughput Comparison Of Different Schemes The comparison will be made to the basic tree algorithm with no capture which gives a throughput of 0.344 (see Table 2.2). In FWC, we notice that the finite capture affects Scheme 1 more than Scheme 2 and the latter has the maximum throughput with a higher a value. Besides, Scheme 2 in FWC has the maximum throughput with K = 1; this is due to the fact that flipping reduces the average conditional CRI slot. As for FWOC, the optimum a value does not vary much going from the finite capture to infinite capture in both schemes. The "Send in the next slot" scheme gives a better throughput and is more sensitive to the number of NDG packets (K) in the finite cap-ture model (see Table 2.5). The presence of more dominant group packets gives higher Chapter 2. Discrete Capture Model 48 Schemes 2-Group FWC Scheme 1 2-Group FWC Scheme 2 3-Group FWC Scheme 1 3-Group FWC Scheme 2 2-Group FWOC Wait 2-Group FWOC Send Max. Throuphput 0.4169 0.425 0.471 0.474 0.375 0.393 K oo capture 1 oo capture Kl2 = K23 = 1 K13 = 2 oo capture oo capture a 0.41 0.50 0.271 0.333 0.479 0.625 0 none none 0.313 0.333 none none % Gain 21.2 23.5 36.9 37.8 9.0 14.2 Table 2.6: Maximum throughput performance of different schemes using discrete capture models. throughput in "Send in the next slot" than "Wait for partial conflict resolution". Ta-ble 2.6 gives a summary of the maximum throughput of each scheme and the percentage improvement compared to the tree algorithm with no capture. K is the number of NDG packets tolerable for a capture to happen. From Table 2.6, Scheme 2 and "Send in the next slot" has a higher throughput than Scheme 1 and "Wait for partial conflict resolution" respectively. Also when the number of tolerable NDG packets reaches 4 or more, the results are almost the same as the infinite capture case. The 3-Group model does give a better throughput than the 2-Group, an increase of 13.2% for Scheme 1 and 11.1% for Scheme 2. The 3-Group capture model for FWOC has not been shown here because of its complexity but it is expected to give a similar kind of improvement over the 2-Group model. It can also been seen that FWC always gives a better throughput performance than the FWOC. Although the probability of flipping '0 ' (PDG, PNDG-, PG\I PG2I PG3) f ° r all the groups have been set to 0.5 (a fair coin), it can be optimized to achieve a higher throughput. As the main purpose of this thesis is to come up with an analytical result for finding the maximum average throughput, the optimization can be done as part of future work. Chapter 3 Continuous Capture Model When the number of priority groups in the discrete capture model is more than 2, the analytical results becomes more complex. Instead of dividing the transmitters into groups, we use the continuous capture model, where the capture of a packet depends on a capture probability. The capture probability is derived from the propagation model, spatial distribution of transmitters/mobiles and the capture models [21]. The continuous capture models from [21] will be used in the tree CRA with both FWC and FWOC. Let Z be the number of slots of a CRI excluding the initial collision or capture slot and X be the number of packets that are involved in the initial collision. Then the average CRI length (in slots) in a tree search with n packets involved in the initial collision (or capture) is, Ln = E[Z | X = n). (3.1) Let qn be the probability of capture when there are n packets involved in a collision and p be the probability of flipping a '0 ' by a transmitter and (1 — p) is the probability of flipping a ' 1 ' . The transmitters that flipped '0' transmit their packets (we call these group '0 ' packets) first. After all or some (in the case of FWOC) of the group '0 ' packets 49 Chapter 3. Continuous Capture Model 50 are resolved, the group ' 1 ' packets are then be transmit. We assume the transmitters do not know the number of packets in each slot. As a result, all transmitters have to monitor the channel feedbacks in order to determine when to transmit as well as to distinguish the end of a CRI. The method is described in section 2.1. The same schemes as in chapter 2 are considered here; all the corresponding flowcharts are still valid. 3.1 Capture Model and Capture Probabil i t ies Different capture models give different sets of capture probabilities, qn. For the mobile application, we need to consider the propagation model, capture effect and the spatial distribution of mobiles for different capture models. Detailed studies of these capture models appear in [21]; some useful results which will be used are summarized in this section. The normalized received signal power T is given by ! » = y, (3-2) where r is the distance between the transmitter and the receiver, f3 is the power loss factor and is commonly assumed to be 4 for flat terrestrial propagation. There are three capture conditions considered in [21]. The first two are Tt > cF3, j = l , 2 , - - - , 0 ^ t (3.3) and r, > c J2 r, (3.4) Chapter 3. Continuous Capture Model 51 where i is the number of on-air packets, r \ , k = 1,2, • • •, i is the received power of mobile k, and c is the capture ratio which depends on the modulation and coding schemes used. The third capture condition uses a probabilistic function of the test signal-to-interference ratio \P to determine whether a test packet will be successfully decoded (i.e. captured); *? is defined by * = £ - (3-5) * n where Fn = J2)=i j^t ^V For a given value of ^ , the probability that a test packet from mobile t is successfully decoded is * W ) = o, v < i (3.6) gty), 4> > i where g(ip) is a function which depends on the type of modulation and coding used. We will to refer condition (3.3) as capture model 1 and conditions (3.4) and (3.6) as capture models 2 and 2.1 respectively. Capture model 1 is the most optimistic among the three and model 2 is a special case of model 2.1 with <&(S\il>) = u(%j) — c) where u(ip) is the unit step function. The spatial distribution of the mobiles around the base station will affect the capture probabilities, qn. Two models of spatial distribution of mobiles are: 1) Uniform spatial traffic density and 2) Bell-shaped spatial traffic density. From [21], the capture probabilities for the model 1 with a uniform spatial traffic density are Model 1 using uniform spatial distribution: *?t, model 1 uniform — o ' ^ — ' ' ' \ " " / Chapter 3. Continuous Capture Model 52 c o -t-» &< V o OS o o 3 o l-l a ^5 O t-C 0* 1.2 1.1 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 §-0.1 0 Model 2.1, c = 10 —• Model 2.1, c = 4 -• Model 2.1, c = 2 A-Model l,c= 10 Model 1, c = 4 Model 1, c = 2 J I L J I L X _L 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 Number of Contending Packets Figure 3.1: Probability of successful qi versus the number of contending transmitter i. where a = c1^, and c is the capture factor. Note that in this case for n > 2, qn is independent of the number of contending packets, n and only depends on c. With Model 2.1 and a bell-shaped spatial density, we have: Qn, model 2.1 bell — 2n . 1 — a r c t a n ( -7T (l-l)/y/c (3.8) with asymptotic value l i m qn, model 2.1 bell TV-y/c (3.9) For both capture models, q0 = 0 and qx = 1. Fig. 3.1 shows plots of qn as a function of n for the two capture models. Chapter 3. Continuous Capture Model 53 3.2 F W C 3.2.1 Scheme 1 Since a CRI starts with a collision, a capture may occur in the initial collision slot. The average CRI length that resolves an initial collision involving n packets without taking into account the initial collision or capture slot is given by (3.1). Therefore, including the initial collision or capture slot, we have L'n = l + (l-qn)Ln + qnLn-U n > 2. (3.10) L'n is the true average CRI length (in slots) to resolve a collision between n colliding packets taking into account the initial collision or capture capture slot. In (3.10), the 1 is for the initial collision or capture slot, the second and third terms refer to the non-capture and the capture cases respectively. For FWC Scheme 1, all the packets will flip after a collision or a capture leading to Ln and I/„_i corresponding. The initial conditions are as follows: L0 = 1 Lx = 2 L'0 = 1 L[ = 1 qi = 1 qt = 0, V i < 0. (3.11) The reason for Li = 2 is because according to the tree search algorithm in Scheme Chapter 3. Continuous Capture Model 54 1 splitting will occur after a capture (see Fig. 2.3(a)), therefore it will take an average of two slots to transmit a packet after a capture. On the other hand, L[ = 1 because a single packet (which can be told from a capture in FWC) only takes one slot to transmit (or resolve) without actually going through a tree search. Fig. 3.2 and 3.3 show cases of the flipping outcomes for L2, L3 and L4 so that the general pattern of the of the scheme and thus the analytical result can be obtained. All different combinations of flipping cases have been shown in those figures, but capture has not been included in all those cases; in fact, capture only occurs to those packets that flipped ' 1 ' . However, if one interchanges the number of packets between the two split groups, cases for capture for those that flipped '0 ' can be seen. For example, Fig. 3.2(a) case 1 is when both packets flipped ' 1 ' and a capture occurs, while case 3 is when both packets flipped '0 ' and no capture occurs; by interchanging number of packets between the '0' and ' 1 ' group in these cases, case 1 will become packets flipped '0' with a capture and case 3 will be both packets flipped ' 1 ' with no capture. Now, we can begin the analysis and we will include both the capture and non-capture probabilities in all the cases in Fig. 3.2 and Fig.3.3. In the following analysis fox FWC, a collision refer to two or more packets transmitted in the same slot and no capture occurred. For n = 2, Case 1: No one flipped '0 ' prob. = \p°(l-p)2 L2 = L0 + (l+L1)q2 + (l + L2)(l-q2). L0 corresponds to the idle slot since no one in group '0 ' . (1 + L-i)q2 corresponds to a capture when group ' 1 ' packets transmit. Chapter 3. Continuous Capture Model 55 2 (col) number of packets in the group r / •O'Jf 0 A idle 1 2 cap4 0 1 L slots initial \^— col. slot "2 C a s e 1 - 2 (col) 2 (col) 2 (col) '0' 1 '1' 1 1 sue L l 1 sue L l slots K - i — X C a s e 2 (a ) C a s e s fo r L „ 0 ^ V o ' ° ' " G r o u p '0 ' , t h o s e flipped '0 ' ' 1 ' - G r o u p T , t h o s e flipped T V 2 T 0 2 col f "\ idle L0 c o l = c o l l i s i o n s u e = s u c c e s s c a p t = c a p t u r e slots 2 Case 3 3 (col) 3 (capt) idle cap* L0 1 I slots -X 1 sue ± 2 cap 1 sue K--3H K-L l ' L , slots -X » 3<c o 1) g.3(coi; 2 ( c o l ^ / \ ^ 1 3 ( c o O ^ / N ^ k-l ^ - ^ L , slots ->l idle ' ^ T ^ slots "0 ' C a s e 1 C a s e 2 C a s e 3 (b ) C a s e s fo r L „ C a s e 4 Figure 3.2: Continuous Capture FWC Scheme 1: different cases of flipping outcomes. Chapter 3. Continuous Capture Model 56 '0' - Group '0', those flipped '0' T - Group '1', those flipped T col = collision sue = success capt = capture number of packets in the group initial col. slot 4 (col) 4 (capt) '0' > 0 idle ± ca0l Lo 1 * T : •i* ^ •-4 Case 1 slots 4 (col) 3 (capt) 1 sue 1 c a p t Li 1 K i r -X slots K--SH Case 2 2 (col) - 4 (col) 3 (co l^ / \ ^ 1 • 4 (COl) 4(001)^/ N^o 1 KJ-t 2 capt -=>l 1 L, K-"4 Case 3 -3>i slots 1 Kc- LT*h i^-L4 Case 4 -X slots '0' 4 '1' 0 4 col I ^T7 idle - ^ L 0 ->l "4 Case 5 slots Cases for LA Figure 3.3: Continuous Capture FWC Scheme 1: different cases of flipping outcomes. Chapter 3. Continuous Capture Model 57 (1 + L2)(\ — q2) corresponds to a collision when group ' 1 ' packets transmit. Case 2: 1 flipped '0 ' prob. \ p\l-pf L2 = 1 + 1. Since there is one packet in each group, one slot is required for each group to transmit. Case 3: Both flipped '0 ' prob. = | \p2(l-p)° L2 = (1 + Li)q2 + (1 + L2){1 - q2) + L0. (1 + Li)q2 corresponds to a capture when group '0 ' packets transmit. (1 + L2){\ — q2) corresponds to a collision when group '0 ' packets transmit. L0 corresponds to the idle slot since no one in group ' 1 ' . Combining 3 cases: U p°(l - pf[L0 + (1 + Lx)q2 + (1 + L2){\ - q2)] \ + p\l-pY[l + l] + \ 2 / p2{\ - p)°[(l + Lx)q2 + (1 + L2)( l - q2) + L0]. (3.12) Chapter 3. Continuous Capture Model 58 The same reasoning is used to deduce the average CRI length in the following cases. For n = 3, Case 1: No one flipped '0' prob. = | | p°(l -pf L3 = L0 + (l+L2)q3 + (l + L3)(l-q3). Case 2: 1 flipped '0' ( 3 prob. = | p1(l — p)2 V 1 L3 = l + (l + L1)q2 + (l + L2)(l-q2). Case 3: 2 flipped '0' / 3 prob. — | p2(\ — p)1 V2 L3 = (l+L2)(l-q2) + (l+L1)q2 + l. Case 4: All flipped '0' prob. = | \p3(l-p)° L3 = (1 + L3)(l - q3) + (1 + L2)q3 + L0. Chapter 3. Continuous Capture Model Combining 4 cases: £ 3 = | I / ( I - P?[Lo + (1 + 72)<73 + (1 + 73)(1 - q3)] + I I P\l - P)2[l + (1 + i/l)?2 + (1 + i 2 ) ( l - <?2)] / + / ( l - p ) 1 [ ( l + 7 2 ) ( l - ? 2 ) + (1+7092 + 1] + \ / P3{1 - p)°[(l + 73)(1 - q3) + (1 + 72)<73 + 70]. For n = 4, Case 1: No one flipped '0' prob. \ 0) p°(l-p)4 7 4 = 7 0 + (1 + 73)<74 + (1 + 74)(1 - q4). Case 2: 1 flipped '0' prob. = J I p x ( l — p)3 7 4 = 1 + (1 + I2)?3 + (1 + ^3)(1 - ?3). Case 3: 2 flipped '0' prob. = I I p2(l — p)2 2 74 = ( 1 + 7 2 ) ( 1 - < ? 2 ) + ( 1 + 7 1 ) C ? 2 + (1 + 7 2 ) ( 1 - < ? 2 ) + (1 + 7 1 ) ( ? 2. Chapter 3. Continuous Capture Model Case 4: 3 flipped '0' prob. = | | p3(l — p)1 3 L4 = (l+L3)(l-q3) + (l+L2)q3 + l. Case 5: All flipped '0' prob. = | | p4(l — p)° 4 L4 = (1 4- U){\ - g4) + (1 + L3)q4 + L0. Combining 5 cases: U ( V° p°(l - pf[L0 + (1 + L3)q4 + (1 + L4)(l - qA)] + px(l - pf[l + (1 + I 2 ) 9 3 + (1 + L3){\ - q3)\ + I | P2(l - rf2[(l + L2){\ - q2) + (1 + Li)92 + (l + L 2 ) ( l - g 2 ) + (l + L1)92] + I | / ( I - P)a[(l + L3){\ - q3) + (1 + L2)q3 + 1] + / \ 4 p4(l - P)°[(l + L4)(l - ?4) + (1 + ^3)?4 + lo]. (3 From the pattern in equations (3.11 )-(3.14) we deduce a general result for Ln. Chapter 3. Continuous Capture Model Ll-n — / n p°(l - p)n[L0 + (1 + Ln_,)qn + (1 + Ln){\ - qn)] 0 1 n . + | | p2(l - p)n-2[(l + L2)(l - q2) + (1 + L1)q2 + (1 + Ln_2)(l - 9n_2) + (1 + Z,n_2_i)9n_2] n + \ | p3(l - p)n-3[(l + L3){\ - q3) + (1 + L2)q3 3 + (1 + Ln_3)(l - qn_3) + (1 + Ln_3_i)?„_3] + | " | p 1 " ( l - p ) B - < [ ( l + ^ ) ( l - f t ) + ( l+A-- i ) f t / + (1 + Ln_t-)(1 - ?„_,-) + (1+ L n—i—lJHn—i] n + | | ^ ( l - pfKl + L ^ i l - q^) + (1 + L ^ ^ q ^ + 1] n — 1 . ™ 1 + 1 Pn(i - P)°[(1 + ^n)(i - gn) + (l + i»- l )? n + L0]. (3 Rearranging the above equation, we can write Nl + N2 K = ST- <3 Chapter 3. Continuous Capture Model 62 where Nl = n-l / \ = 1 if i < 1 »=i \ z 1 if n — i < 1 # 2 £>1 = n n P ° ( l - P ) n + 0 / i n + (1 + !„_,-)(1 - qn-i) + (1 + In_ t-_i)?n-«] [L0 + (1 + I„_l)?„ + (1 - <?n)] p B ( l - p ) ° 77. 1 I 71 / ( i - p ) n + |pn(i-p)° LV o / V« ( l " ? n ) . (3.17) Using equations (3.10), (3.16) and (3.17), L'n, the true average CRI length for FWC Scheme 1 can be determined and using the technique in section 2.2.2 the maximal average achievable throughput for the Poisson arrival process can be obtained. 3.2.2 S c h e m e 2 As for FWC Scheme 2, one should keep in mind that for the continuous capture model there is no grouping, therefore a capture can happen right after another capture. As a result, in FWC Scheme 2, the capture set will just keep transmitting until a collision occurs and then flipping will start (Fig. 3.4). Again this means a slot will be wasted in the collision slot; however, if the capture probability is large this scheme will give a higher throughput and a lower CRI length than Scheme 1. The analysis is basically the same as for Scheme 1 with (3.16) and (3.17) still applicable, and (3.10) replaced by L'n = l + (1 - Qn)Ln + tfn^n-H n > 2. (3.18) Chapter 3. Continuous Capture Model 63 capt = capture col = collision sue = success number of packets in the beginning of that slot initial col. slot • > n capt n-1 n-2 n-3 n-4 capt capt capt col wasted one slot and then start to flip -9H I no flipping in these slots k--^ H • * ! slots Figure 3.4: Example for FWC Scheme 2: Continuous Capture Model. The explanation is, when a capture occurs with probability qn, one of the remaining n — \ packets in the capture set may still be captured, so (3.18) is a recursive equation like (3.10) but with L'n_1 instead of £„_i . The initial conditions in (3.11) still apply except L\ = 2 becomes L\ = 1 for Scheme 2. These two changes are due to the immediate retransmission feature of Scheme 2. For the numerical results, we choose p = 0.5 and n = 48 so that comparisons can be made between the discrete and continuous capture models. Fig. 3.5 and Fig. 3.6 are plots of average CRI length, L'n, of Scheme 1 and 2 versus the initial number, n, of contending packets/transmitters while Figures 3.7 and 3.8 are the corresponding maximal average throughput plots. The true average CRI length, L'n, in both Fig. 3.5 and Fig. 3.6 increases linearly with n. In fact, Fig. 3.5 and Fig. 3.6 are analogous to Fig. 2.7 and Fig. 2.8. As a result, the maximal average throughput is calculated through the reciprocal of the slope for each capture model. Chapter 3. Continuous Capture Model 64 43 W) p — I Pi u aj t-l > < 140 130 120 110 100 90 80 70 60 50 40 30 i-i 0 Model 2.1, c= 10 Model 2.1, c = 4 Model 2.1, c = 2 Model l , c = 10 Model 1, c = 4 Model 1, c = 2 No capture .,*&'•" . : • • • * l .&' .*&: J_J L_L I I 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 Number of Contending Packets Figure 3.5: Average CRI length, L'n, versus n: Continuous Capture FWC Scheme 1. •s 00 J 2 o oj > < 140 130 120 110 100 90 80 70 60 50 40 30 20 Model 2.1, c = 10 Model 2.1, c = 4 Model 2.1, c = 2 Model l , c = 10 Model 1, c = 4 Model 1, c = 2 No capture 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 Number of Contending Packets Figure 3.6: Average CRI length, L'n, versus n: Continuous Capture FWC Scheme 2. Chapter 3. Continuous Capture Model 65 3 P< W) 3 O e 1.3 1.2 1.1 1 0.9 0.8 0.7 Model 2.1, c = 10 Model 2.1, c = 4 Model 2.1, c = 2 Model l , c = 10 Model l ,c = 4 Model 1, c = 2 No capture 0.5 g * * * * * - - - - * " - " 0.4 1 * r_-_5--_-_-_5--_-L.-_--A " " « A " " " " " i 0.3 | 0.2 - S -E _ l L ' I I I J_ J I L J I I L 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 Number of Contending Packets Figure 3.7: Maximal Throughput versus n: for Continuous Capture FWC Scheme 1. +-> =3 & bD 3 O J3 <D x> cl > <U • l -H p*3 < cd a X cd IS 1.6 1.5 1.4 1.3 1.2 1.1 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 Model 2.1, c = 10 Model 2.1, c = 4 Model 2.1, c = 2 Model l , c = 10 Model 1, c = 4 Model l , c = 2 No capture ^ T g A A A ^ ^ A ^ r A - A — ^-A^A-A-AA--z!r—-—-tsr- .-^.-ii--^.-^--br^.-=--^.-^--. A A - - = - - = ^ • = - - = - - = - - ^ • = - • = • • = - - 1 L - B -I I I I I I I I I J I L J L 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 Number of Contending Packets Figure 3.8: Maximal Throughput versus n: for Continuous Capture FWC Scheme 2. Chapter 3. Continuous Capture Model 66 3.3 F W O C The two schemes described in section 2.4 are considered using the continuous capture model. The basic operations of the schemes are the same as described before. The two flowcharts (Fig. 2.14 and Fig. 2.17) describing the schemes are still applicable. However, the continuous capture model allows capture to occur in any PCRI since there are no grouping and capture is governed by the capture probability. 3.3.1 Wait for Partial Collision Resolut ion Let L™ be the average CRI length in a tree search to resolve a collision between n packets given that a capture did not occur in the initial collision slot. Let L™ be the true average CRI length to resolve a collision involving n packets taking the probability of capture in the initial collision into account. L™ includes the initial collision or capture slot as well as the extra idle slot for the end of the CRI while L™ does not (see the initial conditions in (3.30)). lz = r + 9 B ( Z « _ ! ) + (i - <z„)(i + O (3.19) The l c is to account for the initial collision or capture slot while the 1 in (1 + L™) is the extra slot needed to tell the end of the CRI. Also let P(j\i) be the conditional probability that j packets are left at the end of a PCRI given i packets are involved in the beginning and a capture did not capture occur in the first slot of that PCRI. Let L(j\i) be the corresponding average conditional PCRI length; then, K = E ( ^ H + P(i\n)(Lr - lj) (3.20) t'=0 Chapter 3. Continuous Capture Model 67 1 is subtracted from Lf to remove the extra idle slot which L™ is not supposed to include. In fact, we can eliminate the 1 from (3.19) and (3.20), L: = 1 + qn{LZ_x) + (1 - qn)L) n-\ £ (L(i\n) + P{i\n)lr) . (3.21) i=0 The objective is to find L™ and then the maximum average throughput. As one can see, L™ can be found recursively from L™_x and L™ while L(i\n) and P(i\n) are required to obtain L™. Therefore we need to derive L(i\n) and P(i\n). The initial conditions for P(j\i) and L(j\i) are: P(0|1) = 1 L(0|0) = 1 L(0|1) = 1 P(j\z) = L(j\i) = 0, if j > i. (3.22) Let us define lx to indicate x packets are left at the end of a PCRI. We now consider the following equation which shows all the possible combinations of events that contribute L n n • " -1 p°(l - p)n{qn(L0 + 1 + LZJ + (1 - qn) E P o + 1 + ll)P(k\n) + L(k\n)}} 0 / k=o Chapter 3. Continuous Capture Model 68 n + i \Pi(i-pr-i{qn-,(L1 + i + Lz_1_1) n - 1 - 1 + (i - <?„_!) E P i +1 + K)p(k\n -1) + L (*^ -1)]} fc=0 n + 1 | ^ ( 1 - ^ { ^ - 2 ( 2 + 7 ^ n - 2 - l + ft(l-5n-2) E [(2 + 7r fc+1)P(£ ; |n-2) + 7(A ; |n-2)] fc=o + (1 - ?2)gn-2 E t ( 2 + LTk+n_2jP(k\2) + L(k\2)] k=0 2 - l n - 2 - l + (1 - ft)(l - ?n-2) E E [(2 + 7rfc+j)-P(A;|2)P(j|n-2) fc=o i=o + L(&|2) • P(j\n - 2) + 7 ( j > - 2) • P(k\2)]} n + pi(i-pr-i{ftgB_,-(2+zrB_2) + ft(l - 9B_,-) nE1[(2 + Ll^_x )P(k\n -i) + L(k\n - i)} k=0 + (1 - qi)qn-i Ei(2 + LTk+n_,JP(k\z) + L(k\i)] k=o + (1 - ffi)(l - 9n-i) E "£ ' [ (2 + Lfk+.) • P(k\i)P(j\n - i) k=0 j=0 + L(j\n - i) • P(k\i) + L(k\2) • P(j\n - i)]} + 1 n \pn-1(i-P)1{qn-i(2 + LU n- 1 + (1 - qn-riZ \{2 + Ll)P{k\n - 1) + L(k\n - 1)]} fc=0 Chapter 3. Continuous Capture Model 69 n n - l + I Pn(l - P)°{?n(2 + LU + (1 - qn) EK21 + Ll)P{k\n) + L(*|n)]}. (3.23) Since L™ consists of PCRIs, it is important to distinguish the end of a PCRI and the number of packets left at the end of that PCRI. The rules that govern the end of PCRIs are stated in section 2.4.1. In general, if i out of n packets flipped '0 ' [i group '0 ' packets) and the remaining n — i flipped ' 1 ' (n — i group ' 1 ' packets), four possible events may take place when packets from these two groups are transmitted: 1. With probability qiqn-i, capture occurs in both group '0 ' and group ' 1 ' and results in the end of that PCRI with n — 2 packets left. 2. With probability </,(l — qn-i)i capture occurs in group '0 ' with a collision in group ' 1 ' . The group ' 1 ' packets will have to flip and the PCRI ends with k + (i — 1) packets, 0 < k < n — i — 1. The (i — 1) term is the number of packets left after the capture in the group '0 ' packets. 3. With probability (1 — qi)qn-i, a collision occurs in group '0 ' and a capture in group ' 1 ' . The groups '0 ' packets will have to flip and the PCRI ends with k + (n — i — 1) packets, 0 < k < i — 1. 4. With probability (1 — <7,)(1 — qn-i), a collision occurs in both group '0 ' and group ' 1 ' requiring packets in both groups to flip. As a result, the PCRI ends with k + j packets, 0 < k < i — 1 and 0 < j < n — i — 1. 1The constant 2 is to account for the two slots used each time a split takes place regardless of the events(capture, idle or collision) that may occur in these two slots. Chapter 3. Continuous Capture Model 70 All the cases are included in (3.23) so P(j\i) and L(j\i) can be derived. To find P(r\n) for r = n — 1, we can see from (3.23) that the only case for n — 1 packets to be left at the end of a PCRI (i.e. ln-\) is for a capture to occur (with probability qn) after all packets flipped '0 ' or ' 1 ' . If, on the other hand, all packets flipped '0 ' or ' 1 ' and there is no capture (with probability (1 — qn)), then all the packets will flip again which means the situation will be the same as started with two slots wasted. For the sake of convenience, we let p ° ( l - p ) » ( l - g n ) + pn(l-p)°(l-qn) n J which is the probability that all collided packets need to flip again because there is no capture. Then, for r = n — 1, i.e. n — r = 1 P(r\n) = | U L ° ( l -P)nqn+{ " \ pn(l - p)°qn + Y(n)-y + Y{nf-y + Y{nf • y + The above is the sum of an infinite geometric series so that P(r\n) — , r = n — 1 or n — r = 1. (3.24) 1 — Y (n) For 0 < r < n — 2 ov n — r > 1, Chapter 3. Continuous Capture Model 71 P(r\n) = P1(l-p)n'1q1qn-i-u(r) + 1 p\l-p)n-lqi{l-qn-,)P{r\n-\) 1 J + 1 H \p\l-p)n-2[q2qn-2-u(r) + q2{l-qn_2)P(r-(2-l)\n-2) + (l-q2)qn-2P(r-(n-2-l)\2)-+ (1 - q2)(l - qn_2) Y, P(k\2)P(r - k\n - 2)] fc=o / » ^ + p*'(l - p)n_*[ft?n-,- • «(r) + ft(l - ?n-,-)^(r - (* - l ) |n - 0 V * 7 + (1 - qi)qn-iP(r - (n - i - \)\i) + (1 - ft)(i - g»-0 E W ) ^ - *l" - 0] fc=o + / n ^ V " - 1 / / ^ ( l - p ) 1 ^ - ! ? ! • «(r) + (1 - g„_i)?iP(r - (1 - l ) | n - 1)] where u(r) = < 1 i f r = n - 2 0 otherwise. (3.25) (3.25) is analogous to y in (3.24) so an expression for P[r\n) can be found in a similar way, for n — r > 1 n-\ n P(r\n) = { £ I | Pl{l ~ p)n-%qn-i • «(r) + qt(\ - qn-i)P(r - (i - l ) |n - i) + (1 - qi)qn_iP(r - (n - i - l)\i) Chapter 3. Continuous Capture Model 72 1-1 + (1 - qi){\ - qn_i) J2 P(k\i)P(r - k\n - i) k=0 - ( l - y ( n ) ) . (3.26) To find L(r\n), we need to consider the 2 slots used (see footnote 1) and the average conditional PCRI lengths every time flipping takes place. Using a similar argument used in obtaining (3.24), L{r\n) with r = n — 1 is given by n L{r\n) = | \p°(l-p)n[qn(L0 + l) + (l-qn)(P(r\n)(Lo + l) + L(r\n))] ( + n n n pn(l - p)°[qn(L0 + 1) + (1 - qn)(P(r\n)(L0 + 1) + L(r\n))} p0(l-Pr[qn(2) + (l-qn)P(r\n)(2)] + 1 U \pn(l-p)0[qn(2) + (l-qn)P(r\n)(2)} n [1 - I I U \ P°(l - PT(l - 9n) + ^ I Pn(l - P)°(l - qn) Y{n) As a result, L(r\n), r = n — 1 becomes Chapter 3. Continuous Capture Model 73 L{r\n) l-Y(n)' (3.27) For 0 < r < n — 2 or n — r > 1, n L(r\n) = \p°(l-Pr[(l-qn)P(r\n)(2)} n \ + n + pn(l-p)°[(\-qn)P(r\n)(2)} Y(n) n n P ° ( 1 - J 0 » ( 1 - ? B ) + | \pn(l-p)°(l-q») 0 / I n L(r\n) + \ / P 1 ( l - p ) n - 1 { ? i ? n - i ( 2 ) - u ( r ) + 9 l ( l - qn-i)[P(r\n - 1)(2) + L(r - (1 - l ) | n - 1)]} n + 1 | / ( l - p r 2 { < M n - 2 ( 2 ) - u ( r ) + ? 2 ( l - ? n - 2 ) -[P(r - (2 - l ) |n - 2)(2) + Z(r - (2 - l ) | n - 2)] + (1 - ?2)?n-2 • [P(r - (n - 2 - 1)|2)(2) + L(r - (n - 2 - 1)|2)] + (1 - q2)(l - qn_2) • £ [ 2 • P(k\2)P(r - k\n - 2) k=0 + L(k\2) • P(r - k\n - 2) + L(r - k\n - 2) • P(k\2)}} Chapter 3. Continuous Capture Model 74 + n Al-pT-'iqiqn-iW'uir) + g»(i - qn-i) • [P(r - ( i - l ) | n - i)(2) + L(r - (i - l ) | n - i)] + (i - qi)qn-i • [P(r - ( n - i - 1)|0(2) + L(r-(n-i- l)\i)] + (1 - ft)(l - qn-i) £ [ 2 • P ( ^ ^ ) P ( r - fc|n - 0 fc=o + L(k\i) • P(r - k\n -i) + L(r - k\n - i) • P(k\i)]} n + 1 | p " - 1 ( l - p ) 1 K - 1 ? i ( 2 ) - u ( r ) n-1 + (1 -qn-i)qi • [P{r _ (i _ !)(„ _ 1 ) ( 2 ) + L(r - (1 - l ) |n - 1)]} where u(r) = 1 i f r = n - 2 0 otherwise. (3.28) The reason for the term [2• P(k\i)P(r — k\n — i) + L(k\i)• P(r — k\n — i)-\-L(r — k\n — %)• P(k\i)} can be modified to [2 + L(k\i)/P(k\i) + L(r - k\n - i)/P(r - k\n - i)]P(k\i)P(r -k\n — i) because L(k\i) and L{r — k\n — i) already include the respective conditional probabilities, P(k\i) and P{r — k\n — i). Rearranging (3.28), a general expression for L(r\n), n — r > 1 becomes Chapter 3. Continuous Capture Model 75 L(r\n) 7 1 - 1 E U \p\l-pT-i{qiqn-i{2)-<r) »'=i \ i + 9i(l - ?n-i) • [P(r - (i - l) |n - i)(2) + L(r - (i - l)|ra - i)] + (1 - 9«)?n-t • [P(r -(n-i- 1)10(2) + L(r - (n - i - \)\i)\ + (1 - qi)(l - qn_i) • £ [ 2 + L(k\i)/P(k\i) k=0 + L(r - k\n - i)/P(r - k\n - i)] • • P(k\i)P{r-k\n-i) + P°(I-PT + n n Pn(l-P)° [(l-qn)P(r\n)(2)} +(1-Y(n)). The initial conditions to start the recursion are: (3.29) Z™ = LI = L™ = 1 LX = 2 P(0|1) = P(0j0) = L(0\1) = 1 P{i\j) = 0, Vi > i, i > 0 £ * W ) = i »'=0 L(i\j) = 0ifP(i\j) = 0, Vi > j , i > 0. (3.30) Note that P(r|n) is required to find L{r\n) and L™ = 2 is to include the extra idle Chapter 3. Continuous Capture Model 76 slot at the end of CRI. Using (3.24)-(3.30) all the necessary terms for evaluating L™ in (3.21) can be obtained. 3.3.2 Send in the N e x t Slot We use the same definitions of average CRI length, conditional probability P(j\i) and corresponding average conditional CRI length L(j\i) as in 3.3.1. For the sake of clarity, the superscript for the average CRI length is changed from w to s to distinguish between the two schemes. Thus equations (3.21) and (3.30) are replaced by, L'n = 1 + ?„(£•_!) + (1 -qn)Lsn K = £ (£(»» + P{i\")li) • (3-31) t'=0 and 7s — Ts — Ts — 1 L{ = 2 P(0|1) = P(0|0) = L(0|1) = 1 P(i\j) = 0, V i > j , i > 0 E W ) = i L(i\j) = 0ifP(i\j) = 0, \/i > j , i > 0. (3.32) A similar approach to that used in section 3.3.1 is used to obtain the analytical result for the average CRI length. However, the way a PCRI starts and ends in the Chapter 3. Continuous Capture Model 77 "Send" scheme (section 2.4.2) is different from that in the "Wait" scheme (section 2.4.1). Therefore (3.23) is modified to Ts — n \ _ n _ 1 P°(l - PT{qn(L0 + 1 + LI J + (1 - qn) E P o + 1 + L'lk)P(k\n) + L(k\n)}} 0 J k=o n - 1 - 1 + (1 - ?n-i) E P i + 1 + Ll)P(k\n - 1) + L(k\n - 1)]} + | . \p2(l-p)n-2{q2qn-r(2 + Ll_2) + q2(l - qn^) " E 1 ^ + Ll)P(k\n - 1) + L(k\n - 1)] fc=o + (1 - 92) E[(2 + Ll_2+kjP(k\2) + i,(&|2)]^_2+fc A:=0 2-1 n-2+fc-l + ( 1 - ? 3 ) E E (l-9n-2+fc)[(2 + I/;)-P(fc|2)P(j|fc + n - 2 ) fc=0 i = 0 + L(fc|2) • P(j|fc + n - 2) + 7(j|& + n - 2) • P(&|2)]} + | " |p*(l-p)B-*{ft?n-i(2 + X?B_2) n - l - l + ft(l-?n-0 E [(2 + ZfJP(A:|fi-l) + L(fc|i»-l)] + (1 - ft) E[(2 + K^jPiklz) + L(k\i)]qn_i+k k=0 1 1 i-_l_JJ 1 1 + ( 1 - « ) E E (1 - 9»-.-+fc)[(2 + XJ) • P(Ar|t)i>0"l* + » - 0 k=o i=o Chapter 3. Continuous Capture Model 78 n \ + n - l + L(k\i) • P(j\k + n - i) + L(j\k + n - i) • P(k\i)}} pn-\l-pf{qn-xqn-,{2 + ll_2) n - l - l + ? „ - i ( l - g „ _ i ) E [(2 + Li)P(k\n-I)+ L(k\n-I)} k=0 n-l-l + ( l -?„_ i ) E [(2 + Ll)P(k\n-l) + L(k\n-l)]q1+k n - l - l 1 + f c - l + (1 - ?B_X) E E (! - ?i+*)[(2 + Z^) • P(k\n - l)P(j\k) k=o j = o + L(k\n - 1) • P(j\k) + L(j\k) • P(k\n - 1)]} \ + n pn(l-p)0{qnqn-i(2 + Ll_2) n-l-l + ? n ( l - ? n - i ) E [(2 + Ll)P(k\n-l) + L(k\n-l)] k=0 + (1 - ?») E [ ( 2 + LlJP(k\n) + L{k\n)]qk k-0 n-lk-1 + (1 - In) E E ( l - ?*)[(2 + ^ ) • P(^|n)P(i|fc) fc=o i=o + L ( % ) . P ( j | f c ) + JL(j |&)- JP(%)]} (3.33) From the general term that i out of n packets flipped '0' (i group '0' packets) and the remaining n — i flipped ' 1 ' (n — i group ' 1 ' packets), four possible events may take place when packets from these two groups transmit: 1. With probability qiqn_1, capture occurs in both group '0 ' and group ' 1 ' and results in the end of that PCRI with n — 2 packets left. 2. With probability ,^-(1 — qn-i), capture occurs in group '0 ' and the i — 1 packets Chapter 3. Continuous Capture Model 79 left after the capture joined the re — i packets in group ' 1 ' which then experiences a collision. The re — 1 packets in group ' 1 ' will flip and the PCRI ends with k packets, 0 < k < re — 1. 3. With probability (1 —qi)qn-i+k, a collision occurs in group '0 ' which requires flipping to partially resolve leaving behind k packets, 0 < k < i — 1. The k packets then joined the n — i group ' 1 ' packets and a capture occurs ending that PCRI with re — i -f k — 1 packets. 4. With probability (1 — <?,-)( 1 — qn-i), collision occurs in both group '0 ' and group ' 1 ' requiring packets in both groups to flip. As a result, the PCRI ends with j packets, where 0 < j < n — i -\- k — 1 and 0 < k < i — 1. A; is the number of packets left after the flipping (tree search) of the group '0 ' packets. It can be seen that unlike the "Wait for Partial Conflict Resolution" the events that take place when no packets flipped '0 ' and all packets flipped '0 ' are not the same. From (3.33) the event that gives rise to P(r|re), for r = re — 1 or re — r = 1, is P(r\n)=\ H \p0(l-p)n(qn + (l-qn)-P(r\n)). Rearranging we have, for r — n — 1, p0(i-p)nqn 0 P(r|re) = 1—f . (3.34) 1 - | H | p ° ( l - p ) n ( l - 9 n ) Chapter 3. Continuous Capture Model 80 Using the same approach that leads to (3.26), we can obtain, for 0 < r < n — 2 or n — r > 1, P(r\n) = < n \ P * ( l - p ) n " ' [ * ? n - i - « ( r ) + qi(l-qn-i)P(r\n-l) + (1 - %)P(r - (n - i - l) |i)?r+i + ^ ( 1 - qi)P(k\i){l - qn-i+k)P(r\n - i + k) k=0 - ( l - X ( n ) ) . (3.35) where u(r) and 1 if r = n — 2 0 otherwise X(n) = n \ In p°{\ - p)n(l - qn) + o / U \ pn(l - p)°(l - qn) if r = k = 0 and i = n n p°(l-p)n(l-qn) otherwise. (3.36) Equation (3.36) are established because when substituting r = k = 0 and i = n into (3.35) we have, Chapter 3. Continuous Capture Model 81 P(0\n) = n n \ p\l-pf[qnqn-x + qn(l-qn-i)P(0\n-l)} n + p'-(l - p)°[(l - qn)P(0\n)qo + (1 - qn)P(0\n)} n (1-X(n)) n n p'il-pflqnqn-i + g „ ( l - ? „ - i ) P ( 0 | n - l ) ] 1 - I H U ° ( l - p ) n ( l - g n ) - n | p " ( l - p ) ° ( l - ? n ) 90 = 0. Following the procedures used in finding the average conditional PCRI length in the "Wait for partial collision resolution" the average conditional PCRI for the "Send in the next slot" is given by: For r — n — 1 n p°(l-p)n(2)(qn + (l-qn)P(r\n)) L(r\n) = 1 - n \ 0 / pQ(\-p)n{\-qn) For 0 < r < n — 2 or n — r > 1, (3.37) L(r\n) = < \ y ( l - p ) n " ! { ^ n - i ( 2 ) - u ( r ) Chapter 3. Continuous Capture Model 82 + ft(l - 9n_!) • [P(r\n - 1)(2) + L(r|n - 1)] + (1 - ft)?r+i • [P(r - (n - i - 1)10(2) + L(r-(n-i- l)|i)] t'-i + (1 - ft) • E ( ! - gn-i+fc)[2 + L(k\i)/P(k\i) + L(r\n - i + k)/P(r\n - i + k)] • P(k\i)P(r\n-i + k)} n + | | p°(l - p)n[(l - qn)P{r\n)(2)] - ( l - X ( n ) ) . (3.38) (3.32) - (3.38) give all the terms needed in (3.31) to calculate the average CRI length. Note that in finding L(r\n), one first calculates L(n—l\n) then L(n—2\n), • • • until L(0\n). For example, L(0\2) 2 \ p°(l-Pn(l-q2)(2)P(0\2)} + I \p\l-p)1[(2)q1q1] + I \p2(l-p)°{q2qi(2) + (l-q2)qi[P(l\2)(2) + L(l\2)} + (1 - g2)(l - go)[2 + L(0|0)/P(0|0)]P(0|2)P(0|0)} Chapter 3. Continuous Capture Model 83 •4-J W) (U u DO ctf > < 140 130 120 110 100 90 80 70 60 50 40 30 20 h i-h 1-:-=_ L rJ uri Model2.1,c=10 A BT Model 2.1, c = 4 A y / Tl f 1 1 "7 1 ^ I* "^ Model z. l , c — z A CT^ rui Model 1, c — iu y f A*"/*'* Modell,c = 4 gS ..-.'•••'• „L i r i i i - i X ^ A. *."•" - " " * Model 1, c — Z >^ .' "A* A--No capture D ^y< A***'** *^ * "^ "^ ^ ^ .*.*-• -** -"•* J***"^ _ / ,A K ^ ^ > ^ i?c •••• •* ^^ ^s£± ^-— J * 2 • • * • ^ ^ ^ ^ " ^ ^ ~ — ;T . . * . ^ - ^ A ^ - ^ " ^ — - - ^ " ^ ^ • a ' » * £ < i 5 > - ^ ^U£^^ pc~_.'* <JP^>^""^ rrrETT-^-' ^ ^ ^ 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 f-0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 Number of Contending Packets Figure 3.9: Average CRI length, Z™, versus n: Continuous Capture FWOC "Wait for Partial Conflict Resolution". 1 -\ / / ( l - p ) 2 ( l - g 2 ) + ^ \ 2 J p 2 ( l - p ) ° ( l - < 7 2 ) • From the above example, we can see that X(l |2) is required in order to find L(0\2) with L(0|0) = 0, P(0|0) = 1 Figures 3.9 and 3.10 show plots of the average CRI length versus the of initial number of contending packets n for the "Wait" and "Send" scheme respectively. Again the maximal achievable throughput is calculated from the slope of the average CRI length plots. Fig. 3.11 and 3.12 are the corresponding plots of maximal throughput versus n. Chapter 3. Continuous Capture Model 84 J3 -4-> 60 J s U 0 0 «J > < 130 120 110 100 90 80 70 60 50 40 Model 2.1, c= 10 Model 2.1, c = 4 Model 2.1, c = 2 Model l , c = 10 Model 1, c = 4 Model 1, c = 2 No capture 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 Number of Contending Packets Figure 3.10: Average CRI length, LST t he Next Slot". versus n: Continuous Capture FWOC "Send in • * - * 3 OH 60 =J o f-t <D X> CS > <U J2 o < cfl fi • »—* cd s 1.6 1.5 1.4 1.3 1.2 1.1 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 Model 2.1, c= 10 A-Model2.1,c = 4 A-Model2.1,c = 2 A-Model l , c=10 Model l ,c = 4 Model 1, c = 2 No capture B -I I I I I I I I I I J I I L _L 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 Number of Contending Packets F igure 3.11: Maximal Throughput versus n: for Continuous Capture FWOC "Wait for Par t i a l Conflict Resolution". Chapter 3. Continuous Capture Model 85 OH 4=! 3 o 1-1 3 OS > ID - i -H 43 O 1.6 1.5 1.4 1.3 1.2 1.1 1 0.9 0.8 0.7 0.6 , 0.5 i 0.4 0.3 f 0.2 1 j-IA.AA A-AA-— 1 1 1 ~&— — g_ . 1 1 — A -1 - A -- g 1 1 Model 2.1, c= 10 Model 2.1, c = 4 Model 2.1, c = 2 Model l , c = 10 Model 1, c = 4 Model 1, c = 2 No capture --A * —B— - • i i i i i A A^ ^ , ™ M V ^ ™ , „ V ^ . . . . . 1 1 1 1 1 ------A-----1 1 "-"-"i I 1 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 Number of Contending Packets Figure 3.12: Maximal Throughput versus n: for Continuous Capture FWOC "Send in the Next Slot". 3.4 Comparing the Different Schemes for the Continuous Capture M o d e l The maximum average throughputs obtained in the continuous capture model do not require finding the optimum a and/or /3 values as in the discrete capture model since the capture is governed by the capture probabilities and no finite or infinite capture models are concerned. In order to make a fair comparison, we look at a system with 48 transmitters/users. According to section 2.2.2, we only need to find the average CRI length of resolving a collision of all 48 transmitters and then the throughput can be calculated. Table 3.4 summarizes the throughput and the percentage improvement in different schemes and capture models. The percentage improvement is relative to the no capture throughput i.e. 0.344. For FWC, the same capture model and capture ratio in Scheme 2 always produce a Chapter 3. Continuous Capture Model 86 Schemes FWC Scheme 1 FWC Scheme 2 FWOC Wait FWOC Send Capture ratio, c 2 4 10 2 4 10 2 4 10 2 4 10 Capture Model 1 Throughput 0.654 0.560 0.479 0.737 0.596 0.491 0.708 0.541 0.442 0.707 0.538 0.443 % Gain 90 63 39 114 73 43 106 57 28.5 106 56 29 Capture Model 2.1 Throughput 0.615 0.542 0.473 0.683 0.583 0.494 0.583 0.497 0.433 0.565 0.491 0.436 % Gain 79 58 37.5 98.5 69.5 44 69.5 44.5 26 64 42 27 Table 3.1: Maximum throughput performance of different schemes using continuous cap-ture models. higher throughput than Scheme 1. Also capture Model 1 (Uniform spatial distribution) with a higher capture probability gives rise to higher throughput than Model 2.1 (Bell spatial distribution). In FWOC, with the same capture ratio Model 1 always gives a higher capture prob-ability and thus a better throughput than Model 2.1. Owing to the immediate retrans-mission property of "Send in the Next Slot", the number of packets transmitted after a capture will be increased by the packets from the capture set. An increase in the number of packets a decrease in the probability of capture in capture Model 2.1. As a result, the "Wait for the Partial Conflict Resolution" has a higher throughput in most cases. How-ever, when the probability of capture decreases the "Send" scheme will have a slightly higher throughput than the "Wait" scheme; this is the case when the capture ratio is 10. If the capture probability is 1, a packet will be captured every time the capture set (in "Send" scheme) or the waiting set (in "Wait" scheme) is transmitted, and the newly formed capture or waiting set will transmit again resulting in another capture. This will Chapter 3. Continuous Capture Model 87 go on until all packets are resolved, so the throughput in this case is 1 for both schemes. Chapter 4 Optimum Dynamic Tree Algorithm Up to this point, we have discussed the basic binary static tree algorithm. A possible improvement is the use of a dynamic tree (DT) algorithm [6, 7, 8]. In this chapter, we study the effect of capture in the dynamic tree on maximum achievable throughput. 4.1 Opt imum D y n a m i c Tree Protocol The difference between the basic binary static tree and the optimum dynamic tree is that in the former protocol, only two branches emanate from each node throughout the entire tree, while in the latter protocol the tree is constrained to be binary everywhere except at the root node. The dynamic tree is designed to optimally choose the degree of the root node which minimizes the average number of slots needed to resolve a collision. In [8] the root node of the dynamic tree is (i) allowed to take on any degree to create the optimum tree, (ii) restricted to an even degree forming a slightly suboptimum tree which is easier to implement and analyze, and (hi) restricted to a power of two forming the suboptimum dynamic tree. 88 Chapter 4. Optimum Dynamic Tree Algorithm 89 In this thesis, we will consider the suboptimum dynamic tree as in (iii) which is relatively easy to implement. The implementation advantage arises from the observation that the variations in the root node degree may be realized in a single-binary-tree simply by varying the depth of the nodes where the algorithm originates. For example, a tree that has 2 ^ leaves (i.e. 2N nodes/transmitters) and whose root node degree is 2KD is equivalent to a binary tree algorithm that starts its search with the nodes of depth KB, see Fig. 4.1. The problem is to choose KJD SO that the average CRI length to resolve a collision is minimum. The choice depends on observations of the transmission process and the statistics of the arrival process1. Even though the optimum tree may vary from one CRI to another CRI, it is held fixed within a CRI, i.e. once the root node degree is determined, it stays the same throughout that CRI. 4.1.1 Poisson Arrival Process The Poisson source model assumes the existence of an infinite number of independent sources that collectively generate k packets per slot, where A; is a Poisson random variable with constant mean A. A source can have at most two packets, one that has undergone a collision and is in the process of being retransmitted and one that may have arrived since the collision of the first packet occurred. If a second packet arrives, it is not transmitted until after the first is successfully transmitted. Since the number of arrivals in any one slot is a Poisson random variable that is independent of the arrivals in any other slot, it follows that the only quantity from the transmission process that is needed to fully characterize the number of packets to be processed during the (i + l)th CRI is s,-, the number of slots used in the ith CRI. So, given lrThe Poisson arrival process is assumed in the thesis. Chapter 4. Optimum Dynamic Tree Algorithm 90 Dynamic Tree root node of degree 4 Static Binary Tree A dynamic tree with a root node degree of 4 is equivalent to a static binary tree that starts its search on level/depth 2. (since 22 = 4) root node of a static binary tree level/depth 2 Figure 4.1: Example of a dynamic tree with KD = 2 i.e. 2KD = 4 subtrees. Chapter 4. Optimum Dynamic Tree Algorithm 91 Ranges of Hi \ii < 3.4 3.4 < m < 6.8 6.8 < m < 13.6 13.6 < m < 27.2 27.2 < m < 54.4 54.4 < fii < 108.8 108.8 < ^ < 217.6 Optimum KD = 1 2 3 4 5 6 7 = KD Root node degree, 2 4 8 16 32 64 128 2Kv Table 4.1: Optimum root node degree obtained through Hi s,-, the number of packets to be processed in (i + 1) CRI is Poisson distributed with mean Hi = ^si, where A is the Poisson arrival rate. The dynamic tree here is binary everywhere except for the root node whose degree can take on values 2K° where KD is chosen to minimize the average CRI length. From [8] the optimum K^, Kr){Hi)-, a s a function of Hi w a s determined 1, for Hi < 3.40 (4.1) KD, for 3.40 • 2(A '"-2) < Hi < 3.40 • 2 ^ ~ 1 ) , KD > 1 As a result, in the Poisson arrival process, KoifJ-i) ( o r simply KD) is found through Hi and Table 4.1 shows the root node degree of the optimum tree corresponding to different values of Hi-4.1.2 O p t i m u m D y n a m i c Tree Algor i thm The optimum dynamic tree algorithm can be stated as follows: 1. Observe s,-, the previous CRI length. 2. Calculate Hi — ^si-KD(Hi) = < Chapter 4. Optimum Dynamic Tree Algorithm 92 3. Use fij to obtain Ku from (4.1). 4. Use the Kr> found in step 3 to form the optimum tree for resolving the contention in the next CRI. 4.2 Throughput of the O p t i m u m Dynamic Tree As the tree may vary from one CRI to another, care must be taken in finding the maximum achievable throughput. Monte-Carlo simulations will first be used to obtain plots of the average packet delay of each scheme as a function of the arrival rate. The maximum achievable throughput can then be estimated. We need to calculate the average CRI length of the DT so that the technique in section 2.2.2 can be applied to find the throughput. The optimum root node degree depends on the average number, /it,-, of packets arriving in the previous CRI. To find an approximation to the average CRI length for n collided packets, we set //,- = n to determine (using (4.1)) the root node degree, 2 D. This implies that the dynamic tree has 2K° branches and the search is equivalent to starting a binary static tree search at depth Kyy. The multinomial distribution [24] is used to cover all the possible combinations of allocating the n packets among the 2Kr> subtrees. Note that in this thesis, the term subtree is specifically referred to as the branches that emanate from the root node; therefore a root node of degree 2KD has 2RD subtrees, (e.g. in Fig. 4.1 from left to right is the l s < ,2n c*,3 r d and ith subtree.) Then the CRI length is found by summing the average CRI lengths of all those binary static subtrees which can be calculated using results in the previous chapter. Comparisons are then made between the simulated and calculated results. Detailed calculations of the average CRI length of different schemes are discussed in Chapter 4. Optimum Dynamic Tree Algorithm 93 the following sections. In terms of implementation, the only adjustment is for the stack to accommodate packets from all the subtrees. Figures 4.2 - 4.4 are the flowcharts of the FWC and FWOC using DT. 4.2.1 F W C Let the number of binary subtrees (i.e. the root node degree) that is obtained from (4.1) be nt = 2K°. In the two schemes used with FWC, all the packets allocated to a subtree have to be resolved before moving to the next subtree. For a certain number of collided packets, say n, to start a CRI, nt is determined and the average CRI length, Ln, for both Scheme 1 and 2 is given by summing the average CRI length of all the subtrees as follows n n—i\ n—(«'i+«2H H n t - 2 ) £" = £ E • • • £ -M- (U, + Li2 + --- + Lint_, + Ln.{il+...+int_l)) (4.2) where M = — : , ••— — - . p ' V i r - ^ - / - ^ ^ ' - 1 ' and Ps = - (4.3) and ik is the number of packets allocated to the kth subtree through flipping a fair coin with probability ps. Chapter 4. Optimum Dynamic Tree Algorithm f START J 94 v LEVL = 0 N0L=1 <-^_ PACKETS IN THE CORRESPONDING NODES (SUBTREES) SET THEIR SC = 0,1,2,...RND-1 ACCORDINGLY. SP = RND-l INDICATING THERE ARE RND-l NODES (SUBTREES) WAITING TO BE TX. THEN PACKETS WITH SC = 0 TX. <r -^ TREECRA SPLIT INTO 2 GROUPS (0 & 1) PUSH GROUP 1 TO STACK AND SET THEIR SC = SC + 1 &ALLSP = SP + 1 CRI STARTS V GROUP 0 TX. CAPT. SC = STACK COUNTER SP = STACK POINTER COL. = COLLISION SUC. = SUCCESS RND = ROOT NODE DEGREE OF DT • < r NONZERO SC = SC - 1 NONZERO SP = SP - 1 PACKETS WITH SC = 0 TX. END CRI Figure 4.2: Flow diagram of dynamic tree for both schemes in FWC. Chapter 4. Optimum Dynamic Tree Algorithm f START J 95 Ji S C = S P = O J , WF = O r^ PACKETS IN THE CORRESPONDING NODES (SUBTREES) SET THEIR SC = 0,1,2,...RND-1 ACCORDINGLY. SP = RND-l INDICATING THERE ARE RND-l NODES (SUBTREES) WAITING TO BE TX. THEN PACKETS WITH SC = 0 TX. SC = STACK COUNTER SP = STACK POINTER WF = WAIT FLAG COL. = COLLISION SUC. = SUCCESS RND = ROOT NODE DEGREE OF DT STARTS CRIIFNOT STARTED CAPTURE OCCURS FOR THE FIRST TIME (SINCE WF = 0) SO PACKETS IN CAPTURE SET WILL BE PUSHED TO THE BOTTOM OF STACK. THEREFORE SP = SP + 1. WF = 1 (DENOTES A WAITING SET EXISTS). CATPURE SET PACKETS SET THEIR SC TO SP, I.E. SC = SP Figure 4.3: Flow diagram of FWOC: Wait for Partial Conflict Resolution Scheme using DT. Chapter 4. Optimum Dynamic Tree Algorithm r START j Jt sc=o SP = 0 <r _y_ PACKETS IN THE CORRESPONDING NODES (SUBTREES) SET THEIR SC = 0,1,2,...RND-1 ACCORDINGLY. SP = RND-1 INDICATING THERE ARE RND-1 NODES (SUBTREES) WAITING TOBETX. THEN PACKETS WITH SC = 0 TX. TREE CRA: SPLIT INO 2 GROUPS (0&1) PUSH THOSE IN GROUP 1 TO STACK SET THEIR SC = SC + 1 & ALL SP = SP + 1 CRI STARTS SC = STACK COUNTER SP = STACK POINTER COL. - COLLISION SUC. = SUCCESS RND = ROOT NODE DEGREE OF DT NONZERO SC = SC-1 NONZERO SP = SP - 1 TRANSMITTERS WITH BACKLOGGED PACKETS AND SC = 0 TX. A V STARTS CRI IF NOT STARTED _UL SUC. OR CAPT. PACKETS IN THE CAPTURE SET KEEP THEIR SC = 0 SO THEY CAN BE RETRANSMITTED IN THE NEXT SLOT Figure 4.4: Flow diagram of FWOC: Send In the Next Slot Scheme using DT. Chapter 4. Optimum Dynamic Tree Algorithm 97 xl,x2,x3,x4 — number of packets left after each subtree search il,i2,i3,i4 — number of packets originally allocated to each subtree by flipping a fair coin Dynamic Tree il root node of degree 4 Binary Tree Search Using "Wait" Scheme Binary Tree Binary Tree Search Using Search Using "Wait" Scheme "Wait" Scheme 1st subtree Xl Static Binary Tree Using "Wait" Scheme Binary Tree Search Using "Wait" Scheme Figure 4.5: Example of the "Wait" scheme using dynamic tree with root node degree equals 4. 4.2.2 F W O C Unlike the FWC, in the FWOC there may be packets left at the end of each subtree because the feedback cannot distinguish between a success (no residual packets) and a capture (some residual packets). Therefore the idea is to apply the "Wait" and "Send" schemes to each of the binary trees, i.e. the residual packets from each subtree is carried forward to the next subtree see (Fig. 4.5 and Fig. 4.6). The conditional probabilities, P(j\i), and average conditional PCRI lengths, L(j\i), Chapter 4. Optimum Dynamic Tree Algorithm 98 xl,x2,x3,x4 — number of packets left after each subtree search il ,i2,i3,i4 — number of packets originally allocated to each subtree by flipping a fair coin sl,s2,s3,s4 — actual number of packets to start each subtree search Dynamic Tree 'si = il root node of degree 4 Binary Tree • Binary Tree Binary Tree Search Using . Search Using Search Using "Send" Scheme! "Send" Scheme "Send" Scheme 1st subtree xl Static Binary Tree Using "Send" Scheme Binary Tree Search Using "Send" Scheme 4th subtree Figure 4.6: Example of the "Send" scheme using dynamic tree with root node degree equals 4. as defined in section 3.3.1 for both "Wait" and "Send" schemes assume that there is no capture in the first slot of a PCRI (or subtree in this case). We need to incorporate the capture situation into those quantities in order to find the average CRI length for the dynamic tree. For all j < i, i > 0, j > 0 P'(j\z) = qi + (l-qi)-PU\i) ^ J = » - l (1 — qi) • P(j\i) otherwise (4.4) Chapter 4. Optimum Dynamic Tree Algorithm 99 (4.4) holds because the only case where gt- contributes to P'(j\i) is when a capture occurs in the first slot of a PCRI (or subtree) leaving i — 1 packets at the end. With probability P'(j'|z), either a capture or a collision may occur in the first slot of a PCRI (or subtree) which takes up 1 slot leading to the following modification on L(j\i), L'(j\i) = (1 - %) . L(i\j) + P'm-l. (4.5) The initial conditions of P'(j\i) and L'(j\i) are: P'(0|0) = 1 P'(0|1) = 1 L'(0|0) = 1 Z/(0|1) = 1. (4.6) As a result of (4.4) - (4.6), we can simplify equations (3.21) and (3.31) into, K = £ {L'(i\n) + P'(z\n)lr) . (4.7) n n-1 t'=0 Ts — T3 n - 1 K = E [L'{t\n) + P'(i\n)L°) . (4.8) t'=0 Chapter 4. Optimum Dynamic Tree Algorithm 100 P'(j\i) and L\j\i) simplify the form of the analytical results and help in finding the average CRI length of the optimum dynamic tree. Let ik be the number of packets allocated to the kth subtree by flipping a fair coin with probability ps (see (4.3)) and xk, 0 < X). < ik, be the number of packets left at the end of the kth subtree search (see Figures 4.5 and 4.6). Again let nt = 2KD be the root node degree of the DT. For "Wait for partial conflict resolution" the probability that X\ AND x2 AND . . . AND xnt packets left at the end of each subtree is P'(xi\i]) • • • P'(xnt-i\int--[)- P'(xnt\n — («i + - • • + «nt_i)) and let this probability be PpT. With probability P'(xk\ik), there will be Xk packets left (at the end of the kth subtree) after an average number of L'(xk\ik) slots. So for a particular value of PfiT the average number of slots used to resolve the collision is [L'{xl\i1)/P'(x1\i1) + Ll(x2\n-i1)/P'(x2\n-i1) + - • • + L'(xk\ik)/P'(xk\ik) + - • •+L'(xnt\n-(*i + *2 + - • • + int-i))/P'(xnt\n-(i1 + i2 + - • • + int-i)) + L™i+X2+.,.+Xnt]-P%T. The reason for L'{xk\ik)/P'(xk\ik) is because both P^T and L'{xk\ik) contain the probability P'(xk\ik), so the probability has to be divided from L'(xk\ik) before multiplied by P^r- ^Jx1+x2+-+xn is the average CRI needed to resolve all the waiting packets from the subtrees. Again using the multinomial distribution and summing over all the combinations of xk among nt subtrees, the average CRI length of "Wait" scheme using DT is given by n t- i summations nt summations ' ""—: : s ' *.—: : s n n—i\ «-(«'l+*2H l"«nt-2) n - 1 i 2 - l n-(ii+J2H h«nt-l)—1 K = EE--- E -M-E E--- E il=0 i2 = 0 i„ e_i=0 x\ =0^2=0 i „ ( = 0 [L'ixrlnj/P'ixM + L'(x2\n - h)/P\x2\n - h) • • • ••• + L'(xnt\n - (H + i2 + • • • + int-i))/P'(xnt\n - (z\ + i2 + • • • + int-i)) + ^ i + x j + . - . + x ^ ) ] " PDT-(4.9) Chapter 4. Optimum Dynamic Tree Algorithm 101 Using the same approach for "Send in the next slot", and with P^T — P'(xi\ii) • P'{x2\i2 + zi) • • • P'(xnt\xnt-.x + n — (H + ••• + int-i)), the average CRI length is nt-i summations nt summations , - v . . . „ , * . . s n n - i i n - ( « i + « 2 H h*Tit—2) x\ — \ i2+xi-l a;nt_i + n—(t'H Hn t - l ) - l K = E E - .E -M-E E ••• E il=0i2=0 i'nt-l=0 xi=0 X2=0 xnt=0 [// '(xi | i i)/P'(a:i | i i) + £'(z2|*2 + a ^ / ^ ' f o f o + a:2) + • • • • • • + ^ ' ( ^ k n t - i + n-(i1 + ••• + int-i))/P'(int\xnt-i +n-(i1 + --- + i n , - i ) ) + £ ; „ , ] • % • (4.10) Note that P $ T and L™l+X2+...+Xn in (4.9) are replaced by P£,T and Z*n in (4.10) and the upper limits of the nt summations are different. This is because the residual packets are carried from the previous subtree to the next in the "Send" scheme (see Fig. 4.6). 4.3 Numerical Results Capture Model 2.1 is considered and simulation2. The 99% confidence intervals as-sociated with the simulation results is within ± 3 % of the results shown when the arrival rate is low but increases to ±50% as the arrival rate approaches the maximum achievable throughput. Figures 4.7-4.10 are the simulated results of average delay versus the arrival rate for different schemes. Figures 4.11 - 4.14 are the plots of the calculated average CRI length (using equa-tions (4.2)-(4.10)) versus the number of contending packets, n for different schemes. Note that the minimum root node degree is 2, so LQ = Lx = LQ = L™ — Ls0 = L\ = 2. 2In the simulations a fair coin toss is used in the tree search in splitting the collided packets into group '0' and T . Chapter 4. Optimum Dynamic Tree Algorithm 102 One can observe that with no capture, the plots are almost straight lines. However, when the capture effect is included the system becomes more sensitive to the change of the root node degree resulting in the sudden slope change in parts of the curves. Nonetheless the plots still follow a linear straight line pattern as n increases. Consequently, the recip-rocal of the slopes from those lines can be used to estimate to the maximum achievable throughput. Since a Poisson source model is supposed to have an infinite number of users, the results should become more accurate and realistic as n —> oo. However, due to the lengthy computations involved, the average CRI length is found only up to a certain value of n. As a result, comparison between the simulated and calculated results in Table 4.2 indicates the calculated results yield somewhat higher throughput than the simulated results. The difference between the calculated and simulated values increases when only small values of n are used in the calculation. It should be noted that in Scheme 1 (FWC) when c = 2, the throughput from the static tree is higher than that from the DT. Intuitively, we can explain this result by considering the case when there are 2 packets in a subtree and a capture occurs; then according to Scheme 1, the remaining packet will flip resulting in a total of 3 slots to resolve the collision. Since the DT is like dividing the collided packets (from a binary static tree, see Fig. 4.1) into a number of subtrees, so if the above situation happens to a number of subtrees, the DT will have a lower throughput than the static tree. In our case, the simulation is more efficient3 than the calculation in obtaining the maximum achievable throughput. The simulation also gives the average packet delay. 3Consider the "Wait" scheme in FWOC, with a SPARC IPX workstation running a priority 17 background job, the simulation takes about 800 minutes of CPU time while the calculation needs about 30000 minutes to obtain the average CRI length of up to 16 collided packets. Chapter 4. Optimum Dynamic Tree Algorithm 103 «5 o &0 .s Q <L> 00 U 5 0.3 0.4 0.5 Poisson Arrival Rate 0.6 0.7 0.8 Figure 4.7: FWC Scheme 1: Simulated average delay versus arrival rate. oa -»-» O 0 0 c! T — H V Q <D 6fl F3 t j <U p* << 220 200 180 160 140 120 100 80 60 40 20 0 0.1 0.3 0.4 0.5 Poisson Arrival Rate Figure 4.8: FWC Scheme 2: Simulated average delay versus arrival rate. Chapter 4. Optimum Dynamic Tree Algorithm 104 .g >> in Q (U W) l-l < 0.2 0.3 0.4 0.5 Poisson Arrival Rate 0.6 0.7 0.8 Figure 4.9: FWOC "Wait" Scheme: Simulated average delay versus arrival rate. c • i—i >> P D BO «J > 0.2 0.3 0.4 0.5 Poisson Arrival Rate 0.6 0.7 0.8 Figure 4.10: FWOC "Send" Scheme: Simulated average delay versus arrival rate. Chapter 4. Optimum Dynamic Tree Algorithm 105 50 Xi •4-» 00 fl 2 u <u BO cd (-1 3 No capture c = 10 c = 4 c = 2 Lines for finding slope of curves _i_ 6 11 16 Number of Contending Packets, n 21 Figure 4.11: FWC Scheme 1: Calculated average CRI length, Ln, versus number of contending packets, n. 00 c 2 u BO > < 50 40 -30 20 -10 -No capture -c=10 -c = 4 -e = 2 -Lines for finding slope of curves - -J _ J ' ' I i L _ J i_ 6 11 16 Number of Contending Packets, n Figure 4.12: FWC Scheme 2: Calculated average CRI length, L„, versus number of contending packets, n. Chapter 4. Optimum Dynamic Tree Algorithm 106 50 e i—i U <u DO 3 No capture A-c = 1 0 c = 4 * -c = 2 B -Lines for finding slope of curves 6 11 16 Number of Contending Packets, n 21 Figure 4.13: FWOC "Wait" Scheme: Calculated average CRI length, L™, versus number of contending packets, n. s D DO t-c 50 No capture — c = 1 0 -c = 4 -c = 2 -Lines for finding slope of curves - -_i I I L. - B -6 11 16 21 Number of Contending Packets, n Figure 4.14: FWOC "Send" Scheme: Calculated average CRI length, Lsn, versus number of contending packets, n. Chapter 4. Optimum Dynamic Tree Algorithm 107 Schemes FWC Scheme 1 Capture ratio, c 2 4 10 No Capture FWC Scheme 2 2 4 10 No Capture FWOC Wait 2 4 10 No Capture FWOC Send 2 4 10 No Capture Throughput of DT Calculated n up to 19 19 19 19 21 21 21 21 16 16 16 21 13 13 13 21 Results 0.601 0.564 0.523 0.428 0.728 0.650 0.573 0.426 0.616 0.557 0.508 0.426 0.696 0.602 0.529 0.426 Simulated Results 0.600 0.56 0.52 0.420 0.720 0.630 0.560 0.420 0.600 0.540 0.500 0.420 0.670 0.590 0.520 0.420 Throughput of Static Tree Calculated Results (see Table 3.4) 0.615 0.542 0.473 0.344 0.683 0.583 0.494 0.344 0.583 0.497 0.433 0.342 0.565 0.491 0.436 0.342 Table 4.2: Comparison of the throughput performance between the calculated and simu-lated results of different schemes using continuous capture Model 2.1 with the optimum dynamic tree protocol Chapter 5 Conclusions The tree algorithm for multiple access communication has been studied with the capture effect and two different feedback models. In feedback with capture (FWC), the receiver can tell the difference between a capture slot and a success slot whereas in feedback without capture (FWOC) this distinction cannot be made. For each feedback model, two schemes were considered using a discrete capture model and a continuous capture model. Analytic expressions for finding the average CRI length to resolve a collisions between n packets have been derived in all cases and can be used to obtain the maximal achievable throughput. A finite discrete capture model in which a more dominant group packet is captured in spite of the interference from up to a certain number of less dominant group packets was studied. In both the 2-Group and 3-Group FWC, Scheme 2 has a slightly better throughput than Scheme 1. For the 2-Group FWOC, the "Send in the next slot" has a higher throughput than the "Wait for partial conflict resolution" by a bigger margin. Two continuous capture models [21], Model 1 and Model 2.1 that give explicit sets of capture probabilities, {qi}, are used to obtain the maximal achievable throughput. Model 1 is easier to analyze but tends to yield overly optimistic results. For Model 2.1 FWC, with a capture ratio, c, value of 10, the throughput is slightly better than that 108 Chapter 5. Conclusions 109 of the FWC 3-Group discrete capture model and about 40% higher than the no capture case. In FWC, Scheme 2 has a higher throughput than Scheme 1. As for FWOC, the "Wait for partial conflict resolution"is better than the "Send in the next slot" in terms of throughput; however, when the capture probability drops below a certain value, the "Send" scheme has a slightly higher throughput. The optimum dynamic tree (DT) [6, 7, 8] was examined on in the presence of capture. The DT generally improves the throughput performance in all the schemes except for Scheme 1 in FWC with c = 2 where the average CRI length of DT is longer than that of the static tree. Scheme 2 in FWC has the best throughput performance in both the static binary tree and optimum dynamic tree. As for FWOC, the "Wait for partial conflict resolution" is better with the static tree, while the "Send in the next slot" is more efficient with the optimum tree. Further work can be done in the following areas: 1. The effects of errors in the feedback channel could be studied. The use of different capture models that take into account presence of noise (e.g. in [25]) or fading could be considered. 2. Throughput should improve if one can make use of the feedback information and vary the tree within a CRI. As an example, one could adapt the technique proposed by Massey [11]. 3. Instead of the semi-graphical method used, it would be desirable to obtain analytic expressions for the maximal achievable throughput as well as the average packet delay especially in DT. References [1] R. Gallager, "A perspective on multiaccess channels," IEEE Trans, on Info. Theory, vol. IT-31, pp. 124-142, March 1985. [2] N. Abramson, "The ALOHA system-another alternative for computer communica-tions," in Proc. Fall Joint Comput Conf AFIPS Conference, Montvale, NJ, U.S.A., pp. 281-285, 1970. [3] B. Tsybakov, "Survey of USSR contributions to random multiple-access communi-cations," IEEE Trans, on Info. Theory, vol. IT-31, pp. 142-165, March 1985. [4] D. Bertsekas and R. Gallager, Data Networks. Prentice-Hall, Inc., 1987. [5] L. Roberts, "ALOHA packet system with and without slots and capture," Comput. Commun. Rev., pp. 28-42, April 1975. [6] J. Capetanakis, "Tree algorithms for packet broadcast channels," IEEE Trans, on Info. Theory, vol. IT-25, pp. 505-515, Sept. 1979. [7] J. Capetanakis, "Generalized TDMA: the multi-accessing tree protocol," IEEE Trans, on Commun., vol. COM-27, pp. 1476-1484, Oct. 1979. [8] J. Capetanakis, "The multiple access broadcast channel: protocol and capacity con-siderations," Tech. Rep. ESL-R-806, Mass. Inst, of Tech., Cambridge, MA, March 1978. [9] B. S. Tsybakov and V. A. Mikhailov, "Free synchronous packet access in a broadcast channel with feedback," Prob. Peredachi Inform. (USSR), vol. 14, pp. 32-59, Oct. 1978. [10] J. Hayes, "An adaptive technique for local distribution," IEEE Trans, on Commun., vol. COM-26, pp. 1178-1186, Aug. 1978. [11] J. L. Massey, "Collision resolution algorithms and random-access communications," Tech. Rep. UCLA-ENG-8016, Univ. of California, Los Angeles, April 1980. 110 References 111 [12] L. Kleinrock and F. A. Tobagi, "Packet switching in radio channels: Part 1: CSMA nodes and their throughput-delay characteristics," IEEE Trans, on Com-mun., vol. COM-23, pp. 1400-1416, Dec. 1975. [13] G. S. Evssev and N. G. Ermolaev, "Collision resolution performance evaluation for random access noisy channel," Probl. Peredachi Inform., vol. 18, pp. 101-105, Apr.-June 1982. [14] I. Kessler and M. Sidi, "Splitting algorithms in noisy channels with memory," IEEE Trans, on Info. Theory, vol. 35, pp. 1034-1043, Sept. 1989. [15] B. S. Tsybakov and N. D. Vvedenskaya, "Stack-algorithm for random multiple ac-cess," Probl. Peredachi Inform., vol. 16, pp. 80-94, July-Sept. 1980. [16] J. Metzner, "On improving utilization in ALOHA networks," IEEE Trans, on Com-mun., vol. COM-24, pp. 447-448, April 1976. [17] C. Lau and C. Leung, "Performance of a power group division scheme for ALOHA systems in a finite capture environment," Electronics Letters, vol. 24, pp. 915-916, 21st July 1988. [18] M. Sidi and I. Cidon, "Splitting protocols in presence of capture," IEEE Trans, on Info. Theory, vol. IT-31, pp. 295-301, March 1985. [19] I. Cidon and M. Sidi, "The effect of capture on collision-resolution algorithms," IEEE Trans, on Commun., vol. COM-33, pp. 317-324, April 1985. [20] I. Cidon, H. Kodesh, and M. Sidi, "Erasure, capture, and random power level selec-tion in multiple-access systems," IEEE Trans, on Commun., vol. COM-36, pp. 263-271, March 1988. [21] C. Lau and C. Leung, "Capture models for mobile packet radio networks," IEEE Trans, on Commun., vol. 40, pp. 917-925, May 1992. 22] N. Mehravari and T. Berger, "Poisson multiple-access contention with binary feed-back," IEEE Trans, on Info. Theory, vol. IT-30, pp. 745-751, Sept. 1984. 23] A. G. Pakes, "Some conditions of ergodicity and recurrence of Markov chains," Journal of Oper. Res. Society of America, vol. 17, pp. 1058-1061, 1969. 24] W. Feller, An Introduction to Probability Theory and Its Applications. Vol. I, John Wiley & Sons, Inc., 1968. 25] V. Wong, "Effects of capture, power loss factor, and variable transmit power level in multiple-access systems," 1991. M.A.Sc thesis, Dept. of Electrical Engineeing, University of British Columbia. A p p e n d i x A B o u n d s for E[l] and E[l2] In this Appendix, we will show that the steady state first and second moment of /& (where lk is the length of the kth CRI) are finite. In other words, E[l] = \\mE[U] < oo E[l2] = lim£[Z?] < oo. (A.l) i—>oo First to show that E[l] is finite we have from (2.14), E[L(i + l,a) | L(i,a)=j] < (1 - e)j, Vj > N or ^[/,-+iK-=i] < (l-e)j', Vj > N. (A.2) When j = tf + 1, £[/,-+1|/,- = (JV + l)] < (1 -e)(7V + l) 112 Appendix A. Bounds for E[l] and E[P] 113 and when j = N + 2, E[li+1\U = (N + 2)] < (l-e)(N + 2). 5ince ( l -e) (JV + l) < ( l -e ) ( JV + 2), it follows that, E[li+1\h = (N + l)} < E[k+1\li = (N + 2)]. With the same argument, we have E[li+1\li=j] < ( l - e ) iV , Vj < N. (A.3) Since CO E[U+i] = J2P(h=j)E[li+1\h = j}, (A.4) t'=0 where P{U = j) is probability that the length of the ith CRT is j i.e. /,- = j . Substituting (A.2) and (A.3) into (A.4) we have, Appendix A. Bounds for E[l] and E[P] 114 JV oo E[h+i] = EP(li=J)E[li+1\U=j]+ E P(U = J)E[li+i\U = j] j=Q j=N+l N oo < '£P(U=j)(l-e)-N+ E P(h=j)(l~e)-j 3=0 j=N+l oo oo < EP(U = J)(I - e) •N + E ^ = j)(i - 0 • J i=o i=o < (i _ e) . # + ( 1 - e) • £[/,-] £[Z,-+1] < ( l _ £ ) . J V + ( l -£) •£[ / , - ] . (A.5) Solving (A.5) recursively, we have E[h) < (i-e)N + (l-e)-E[l0] E[l2] < (1 - e)N + (1 - t) • E[h] < (1 - t)N + (1 - tfN + (1 - e)2 • £[Z0J E[l3] < (l-t)N + (l-e)-E[l2} < (1 - e)JV + (1 - e)2N + (1 - e)37V + (1 - e)3 • E[lQ\. As a result, we can write E[li+1] < (l~e)N + (l-e)2N + --- + (l-e)i+1N + (l-ey+1E[lo} }im E[li+1] < ( 1 ~ £ ) i V + l i m ( l - e ) ' + 1 ^ [ / 0 ] Since 0 < e < 1, so (1 — e) < 1 and therefore l i m ^ ^ l — e)*+1 = 0, so that Appendix A. Bounds for E[l] and E[P] 115 E[l] < — < oo. We next show that E[l2] is finite. Similar to (A.2) and (A.3), we let for t' > 0, E[L\i + l,a) | L(i,a)=j] < (1 - e');2 , V j > N, or Etf+1\li=j] < ( 1 -Oi 2 , Vj > N, E[tUi\U=J] < (l-m2, Vj < N. (A.6) With E[lU = EP(h=j)Etf+1\k=j], (A.7) 8=0 and substituting (A.6) into (A.7), we have N oo TV oo < T,nu = m~^)-N2+ E ^= j ) ( i -o - i 3 3=0 3=N+1 oo oo < E ^ = i)(i - 0 -^2 + E^C- =-?')(! - O • ia 3=0 3=0 < (1 - 6') • iV2 + (1 - e') • E[l}} mU\ < (l-e')-N* + (l-e')-Etf}. (A.8) Again by solving (A.8) recursively, we have Appendix A. Bounds for E[l] and E[l2} 116 E[l\] < (I - e')N2 + (I ~ e') • E[l20] E[lj] < (1 - e')N2 + (1 - e') • E[l\] < (1 - e')N2 + (1 - t'fN2 + (1 - e')2 • E[l2] E[ll] < (l~e')N2 + (l-e').E[l22] < (1 - e ')^2 + (1 - e ')2^2 + (1 - e ')3^2 + (1 - e')3 • E[l20] As a result, the steady state second moment of /; is E[l2] = l™E[l2+1] I—>oo < lim{(l - e ' )^2 + (1 - e ')2^2 + • • • + (1 - t'f^N2 + (1 - e'f+1^E[l20}} i—+oo (1 - e')N2 1 - ( I - , ' ) < oo. (A.9) For the Poisson arrival process, the LHS of (A.6) can be written as £ E[L2{i + 1, a) | no. of arrivals in ith CRI = n] • ( A ^ T {exp (ATj)} n=o n-^ r(a?^TJY{eXp-{\T])} < (1 - e')i2, Vj > TV where Appendix A. Bounds for E[l] and E[l2} L^f = E[L2(i + l,a)\no. of arrivals in ith CRI = n\. (A Assume a bound on L^ to be 4 " ) 2 < ( c(«) • n + d(a))2, c(a) > 0, d(a) > 0. (A Putting (A. l l ) into (A.10) we have 2^{c{a) • n + d(a)) j < (1 n=0 n-g ( c ( a ) ' • „ ' + 2c(a)i(a)n + < ) ( « ) ' ) ( A r j ) " { < ^ ~ ( A T J ' ) } < (1 £ c{af . ^WkM + £ 2c(a)<J(a)„ . (WW-(A T , ) } + E ^ ( A T , ) " { e x r ( A " ) } < c c(Cv)2(A^2 + A r i ) + 2 c H J ( a ) A r i + J (« ) 2 < (1 c(ayX2Tj2 + 2(c(a)d(a) + c(ay)XTj+d(ay < (1 2 2(C(a)d(q) + c(a) 2)A r <i(a)2 c(a) AT H : 1 ^— < (1 3 3 In the limit as N —> oo and V j > iV, we have 2;(o;)2A2r < A?, < AT < AT < (1 - t)2 (1 - e)2 x(a)2 ( 1 - 0 a; (a) 1 if e < 1. , , - ^ ^ - (A ;(a) Appendix A. Bounds for E[l] and E[P] 118 It can be seen that (A. 12) also produces a maximal achievable throughput value in a form similar to that from (2.18). Now one need to verify whether the maximal achievable throughput obtained from (2.18) satisfy (A.12) and so the bound in (A.11) holds. From (A. l l ) when n = 0, 4 ^ < d(a)\ and LQ is the mean of square of an idle slot which equals 1. Setting y(a) = 1 and c(a) = a(a) as obtained from (2.18), we can plot the RHS of (A. l l ) and the LHS of (A . l l ) (obtained from simulation1) as shown in in Figures A.l and A.2. These figures shown that the bound in (A. l l ) holds. Note that a(a) is obtained using the AT values from Table 2.2 and Table 2.5. Fig. A.l and Fig. A.2 shows that (A. l l ) holds meaning that the maximal achievable throughput can be found from the slope of the RHS of (2.16) at the same time yielding a first order stable system having a finite average delay. Figures A.3-A.6 are plots showing that the same argument and bound holds in the continuous capture model with the values of AT from Table 3.4. 2In the simulations a fair coin toss is used in the tree search in splitting the collided packets into group '0' and '1 ' . The 99% confidence intervals associated with the simulation results is less than ±4.5% of the results shown. Appendix A. Bounds for E[l] and E[P] 119 20000 19000 18000 17000 16000 15000 14000 13000 12000 11000 10000 9000 8000 7000 6000 5000 4000 3000 2000 -1000 0 FWC No Capture: By Simulation FWC No Capture: The Bound 0 12 16 20 24 28 32 36 40 44 48 No. of contending packets F igure A.l: Mean square value of the number of slots used to resolve a collision between n packets, L^2, versus n for the 2-Group FWC with no capture. Appendix A. Bounds for E[l] and E[P] 120 20000 19000 18000 17000 16000 15000 14000 13000 12000 11000 10000 9000 8000 7000 6000 5000 4000 3000 2000 1000 0 FWOC No Capture: By Simulation B FWOC No Capture: The Bound B -BSt 12 16 20 24 28 32 36 40 44 48 No. of contending packets Figure A.2: Mean square value of the number of slots used to resolve a collision between n packets, L^2, versus n for the 2-Group FWOC with no capture. Appendix A. Bounds for E[l] and E[P] 121 0 4 8 12 16 20 24 28 32 36 40 44 48 No. of Contending packets Figure A.3: Continuous Capture Model 2.1 FWC Scheme 1: Mean square value of the number of slots used to resolve a collision between n packets versus n, with different capture ratio, c. Appendix A. Bounds for E[l] and E[P] 122 G O C>5 o t/5 o Vi -4-» o C* O S-H 1 o 3 CO O 20000 19000 18000 17000 16000 15000 14000 13000 12000 11000 10000 9000 8000 7000 6000 5000 4000 3000 2000 1000 0 c = 10: By Simulation A c = 10: The Bound A c = 4: By Simulation B c = 4: The Bound B c = 2: By Simulation *-c = 2: The Bound x -No Capture: By Simulation No Capture: The Bound No. of Contending packets Figure A.4: Continuous Capture Model 2.1 FWC Scheme 2: Mean square value of the number of slots used to resolve a collision between n packets versus n, with different capture ratio, c. Appendix A. Bounds for E[l] and E[l2} 123 o 'o o u <D I - l «4H o 3 C o S3 cr OS 20000 19000 18000 17000 16000 15000 14000 13000 12000 11000 10000 9000 8000 7000 6000 5000 4000 3000 2000 1000 0 //' c = 10: By Simulation A c = 10: The Bound & c = 4: By Simulation B- -A T 1 T» 1 1—1 c —4: inersouna i_i c = 2: By Simulation x- -c — z. inersouna >*• j p , T> C" 1 *' MO capture: rsy oimulation \T P , T*l T» I INO capture, ine oouna J // /7 /? y2-S* y ^ c y* yy y% S ^£yy^ y^ yz&f^y-' ^* >* ^y^PZyt^* y^ y^*y^jr\ -***^"^ ^S^^&$yZ2z~it-' ^yy^^^sa^z?^^ & ^ * \ 1 1 / / // // // // / / // / / // /, A A A /' A // A // A Ay ; // /& y* yy' y* / ' ri^s y y y'' J&' yfy ^^^ r^s ^ ^ \y ^2*: 1 ^ *^">* •^S' 1 1 1 1 // fy // // A'-/ ' y? rS' y? &/ S? 0 y* yy y> yy 1 1 12 16 20 24 28 32 36 40 44 48 No. of Contending packets F igure A.5: Continuous Capture Model 2.1 FWOC "Wait" Scheme: Mean square value of t h e number of slots used to resolve a collision between n packets versus n, with different cap ture ratio, c. Appendix A. Bounds for E[l] and E[l2] 124 o •A o a & 'o tz> <U (-< VI o 1 a O (U & CO 20000 19000 18000 17000 16000 15000 14000 13000 12000 11000 10000 9000 8000 7000 6000 5000 4000 3000 2000 V-1000 h 0 0 // // c = 10: By Simulation A / / 1f\ T l T i l A / / c— IU: inerSouna A /. c = 4: By Simulation B // 1 Tii Tt mi i n // c — 4. inersounu u /' c = 2: By Simulation * // c — L\ ine Bound >*• // Vo Capture: By Simulation / ' No Capture: The Bound // A A // A c / / *v ./£ / > * / ^ /^ A' X' / j/X /* A SK yy yC' A yy / ' y$y / ^JF^r y y^JSZ^ yxc^^ y* ,,<> ^Z- ~^^> s? ^4r^^> ^ JSZ'' sS yi^jtkz^z^^^ y^ ^ ^ ^ ^ ^s ij-g<^3--3r=' ^s^^S&Zj^Z^ & ^ * \ 1 1 1 1 1 1 II II II II II / / / / fl 1 // // // yy // // yy yy yy 1 / ' // // // // / / / yy // // // y? yy yy yy y> 1 8 12 16 20 24 28 32 36 40 44 48 No. of Contending packets Figure A.6: Continuous Capture Model 2.1 FWOC "Send" Scheme: Mean square value of t he number of slots used to resolve a collision between n packets versus n, with different capture ratio, c.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Throughput performance of tree collision resolution...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Throughput performance of tree collision resolution algorithms with capture Wong, Kenneth K. L. 1994
pdf
Page Metadata
Item Metadata
Title | Throughput performance of tree collision resolution algorithms with capture |
Creator |
Wong, Kenneth K. L. |
Date Issued | 1994 |
Description | The effect of capture on tree algorithms in a slotted ALOHA broadcasting network is investigated. Two receiver models are considered: Feedback With Capture (FWC) and Feedback Without Capture (FWOC). In FWC, the receiver is able to distinguish between a success and capture slot, whereas in FWOC it is not. For each model, two collision resolution schemes are examined. The throughput performances of the four schemes using the discrete and continuous capture models are obtained and compared. In the discrete capture model, the transmitters are divided into groups. Only packets from transmitters in a more dominant group have a chance to be captured. The continuous capture model is used to examine the throughput performance on the inbound (mobile-to-base station) channel in a packet radio system consisting of a central base station and a number of mobile user terminals. The use of a dynamic tree (DT) algorithm in a continuous capture environment is also investigated. Expressions for finding the average length of a collision resolution interval (CRI) for each scheme using the static binary tree are derived. These average lengths are used to determine the throughput. Numerical procedures are described which use the static binary tree results in the dynamic tree to estimate the throughput. Simulations are used to verify the maximum achievable throughput in DT which also give plots of the average packet delay against the arrival rate. |
Extent | 3776771 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-03-06 |
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. |
DOI | 10.14288/1.0065242 |
URI | http://hdl.handle.net/2429/5606 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 1994-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1994-0659.pdf [ 3.6MB ]
- Metadata
- JSON: 831-1.0065242.json
- JSON-LD: 831-1.0065242-ld.json
- RDF/XML (Pretty): 831-1.0065242-rdf.xml
- RDF/JSON: 831-1.0065242-rdf.json
- Turtle: 831-1.0065242-turtle.txt
- N-Triples: 831-1.0065242-rdf-ntriples.txt
- Original Record: 831-1.0065242-source.json
- Full Text
- 831-1.0065242-fulltext.txt
- Citation
- 831-1.0065242.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-0065242/manifest