PERFORMANCE OF TRANSMISSION STRATEGIES IN MULTIHOP PACKET RADIO NETWORKS by VICTOR J. K. WONG B.Sa(EE), University of Manitoba, 1989 M.A.Sc.(EE), University of British Columbia, 1991 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUffiEMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY 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 March 1995 © Victor J. K. Wong, 1995 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) Department of ELECTfZICAL tN6rlNE.ERiN6r The University of British Columbia Vancouver, Canada Date MAZCH 8 , I99S DE-6 (2/88) Abstract The problem of data communication in a multihop packet radio network (PRN) with a number of mobiles or randomly distributed stationary nodes using a slotted ALOHA channel access scheme is addressed. A multihop PRN is an extension of a single-hop PRN; in the latter system, a node can communicate directly with any other nodes. A multihop PRN is necessary if a node cannot reach another node due to transmit power constraints. In such a case, the node requires repeaters to forward packets on to the destination. If a network has a large number of nodes, employing spatial frequency reuse to achieve better spectrum is one of the advantages of a multihop PRN over a single-hop PRN. In multihop PRNs, a transmission strategy involves designing a routing algorithm and determining the transmission probability for each node in the network. Routing is one of the major problems in a multihop PRN. In this thesis, three new routing schemes, MAD, ARR, and MTP, are proposed. The performances of five transmission strategies based on the MFR, NFP, MAD, ARR, and MTP routing schemes with capture and fading are studied and compared. Results show that the transmission strategies based on the ARR and MTP routing schemes perform better than the other three transmission strategies. All five transmission strategies perform worse in the presence of Rayleigh fading; this is in contrast to contention-limited single-hop systems in which Rayleigh fading generally does not result in a poorer performance. A multiple receiver antenna system for a multihop PRN is proposed in which the nodes make use of multiple receiver antennas so as to provide diversity reception. The performances of the five transmission strategies based on the MFR, NFP, MAD, ARR, and MTP routing schemes in a Rayleigh fading environment are investigated. Results show ii that the performances of all five transmission strategies can be substantially improved by employing multiple antennas. The performance improvements of the transmission strategies arising from the use of directional transmitter antennas are also examined. It is found that the performances of all five transmission strategies can be improved by reducing the beamwidth of the antennas. i i i Table of Contents Abstract ii List of Figures vii Glossary xi Acknowledgement xiii 1 Introduction 1 2 Preliminaries 5 2.1 Slotted ALOHA 5 2.2 Channel Models 6 2.3 Capture Models 6 2.4 Interference Models 7 2.5 Antenna Patterns 9 2.6 Network Model 10 2.7 Performance Measure 11 2.8 Review of Related Works 13 3 Routing Schemes 17 3.1 Most Forward with Fixed Range (MFR) Scheme 19 3.2 Nearest with Forward Progress (NFP) Scheme 21 3.3 Minimal Angular Deviation (MAD) Scheme 22 3.4 Angular Deviation to Transmission Range Ratio (ARR) Scheme 24 3.5 Maximal Transmission Potential (MTP) Scheme 28 iv 4 Performance Evaluation of Transmission Strategies 30 4.1 Interference Model 1.2 31 4.1.1 Probability of Interference 31 4.1.1.1 Calculation of Pi(Eint\E+) 32 4.1.1.2 Calculation of FT (Eint\E-) 37 4.1.2 Throughput and Normalized Average Progress 40 4.2 Interference Model 2.1 42 4.3 Interference Model 2.2 44 4.3.1 Capture Probability 44 4.3.2 Throughput and Normalized Average Progress 49 4.4 Analytic and Simulation Results 51 4.4.1 Interference Model 1.2 52 4.4.2 Interference Model 2.1 53 4.4.3 Interference Model 2.2 54 4.4.4 Regular Structure Networks 56 5 Multiple Receiver Antenna Selection 65 5.1 Multiple Receiver Antenna System 65 5.2 Capture Probability 66 5.3 Throughput and Normalized Average Progress 68 5.4 Analytic and Simulation Results 69 V 6 Directional Transmitter Antennas 77 6.1 Directional Transmitter Antenna System 77 6.2 Capture Probability 78 6.3 Throughput and Normalized Average Progress 82 6.4 Analytic and Simulation Results 83 7 Conclusions 96 Bibliography 99 Appendices 105 A Partial Excluded Region 105 A.1 MFR 105 A.2 NFP 107 A.3 MAD 109 A.4 ARR 110 B Asymptotic Value of X>,#(r, 0) 117 C Outline of Simulation Program 120 vi List of Figures 2.1 Antenna radiation patterns, red function and sine function, with half-power beamwidth B\y = f 9 2.2 Illustration of the progress towards the destination with a successful transmission.. 12 3.1 Receiving node selection and excluded region for MFR 20 3.2 Receiving node selection and excluded region for NFP 22 3.3 Receiving node selection and excluded region for MAD 23 3.4 Receiving node selection and excluded region for ARR 25 3.5 Illustration for the derivation of frit) for ARR 26 3.6 Illustration for the derivation of /e|r(^l*) for ARR.. 27 4.1 Illustration of the calculation of Pr (EM | E+) for MFR 33 4.2 Illustration of the calculation of Pr (Eint | E+) for NFP 35 4.3 Illustration of the calculation of Pr (EM | E+) for MAD 36 4.4 Illustration of the calculation of Pr (Eint \ E+) for ARR 37 4.5 Illustration of the interference region for interference model 2.1 43 4.6 The uniform spatial and the bell-shaped spatial probability density functions fiufrm) of distance between Y and M with re = 0 and r<f = 10rmax 46 4.7 Comparison of normalized average progress for MFR, NFP, MAD, and ARR with interference model 1.2 58 4.8 Comparison of throughput for MFR, NFP, MAD, and ARR with interference model 1.2. Legend is the same as in Figure 4.7 58 4.9 Comparison of normalized average progress for MFR, NFP, MAD, ARR, and MTP with interference model 2.1 59 vii 4.10 Comparison of throughput for MFR, NFP, MAD, ARR, and MTP with interference model 2.1. Legend is the same as in Figure 4.9 59 4.11 Comparison of normalized average progress for MFR, NFP, MAD, ARR, and MTP with interference model 2.2 in a non-fading channel 60 4.12 Comparison of throughput for MFR, NFP, MAD, ARR, and MTP with interference model 2.2 in a non-fading channel. Legend is the same as in Figure 4.11 60 4.13 Comparison of normalized average progress for MFR, NFP, MAD, ARR, and MTP with interference model 2.2 in a Rayleigh fading channel. Legend is the same as in Figure 4.11 61 4.14 Comparison of throughput for MFR, NFP, MAD, ARR, and MTP with interference model 2.2 in a Rayleigh fading channel. Legend is the same as in Figure 4.11. . 61 4.15 Distribution of nodes in a square grid network 62 4.16 Distribution of nodes in a hexagonal grid network 62 4.17 Comparison of normalized average progress for MFR, NFP, MAD, ARR, and MTP with interference model 2.2 in a square grid network 63 4.18 Comparison of throughput for MFR, NFP, MAD, ARR, and MTP with interference model 2.2 in a square grid network. Legend is the same as in Figure 4.17 63 4.19 Comparison of normalized average progress for MFR, NFP, MAD, ARR, and MTP with interference model 2.2 in a hexagonal grid network. Legend is the same as in Figure 4.17 64 4.20 Comparison of throughput for MFR, NFP, MAD, ARR, and MTP with interference model 2.2 in a hexagonal grid network. Legend is the same as in Figure 4.17.. . 64 5.1 Normalized average progress for MFR with various iVr receiver antennas. Legend is the same as in Figure 5.2 72 5.2 Throughput for MFR with various Nr receiver antennas 72 5.3 Normalized average progress for NFP with various Nr receiver antennas. Legend is the same as in Figure 5.2 73 5.4 Throughput for NFP with various NT receiver antennas. Legend is the same as in Figure 5.2 73 V11I 5.5 Normalized average progress for MAD with various NT receiver antennas. Legend is the same as in Figure 5.2 74 5.6 Throughput for MAD with various Nr receiver antennas. Legend is the same as in Figure 5.2 74 5.7 Normalized average progress for ARR with various Nr receiver antennas. Legend is the same as in Figure 5.2 75 5.8 Throughput for ARR with various Nr receiver antennas. Legend is the same as in Figure 5.2 75 5.9 Normalized average progress for MTP with various Nr receiver antennas 76 5.10 Throughput for MTP with various Nr receiver antennas. Legend is the same as in Figure 5.9 76 6.1 Illustration of Y, a transmitting node M, AT s intended receiving node W, and M's destination U 79 6.2 Normalized average progress for MFR in a non-fading channel with red pattern and different values of Bw- Legend is the same as in Figure 6.5 86 6.3 Normalized average progress for MFR in a non-fading channel with sine pattern and different values of Bw- Legend is the same as in Figure 6.5 86 6.4 Normalized average progress for NFP in a non-fading channel with red pattern and different values of Bw- Legend is the same as in Figure 6.5 87 6.5 Normalized average progress for NFP in a non-fading channel with sine pattern and different values of Bw 87 6.6 Normalized average progress for MAD in a non-fading channel with red pattern and different values of Bw- Legend is the same as in Figure 6.5 88 6.7 Normalized average progress for MAD in a non-fading channel with sine pattern and different values of Bw- Legend is the same as in Figure 6.5 88 6.8 Normalized average progress for ARR in a non-fading channel with red pattern and different values of Bw- Legend is the same as in Figure 6.5 89 6.9 Normalized average progress for ARR in a non-fading channel with sine pattern and different values of Bw- Legend is the same as in Figure 6.5 89 IX 6.10 Normalized average progress for MTP in a non-fading channel with red pattern and different values of Bw- Legend is the same as in Figure 6.5 90 6.11 Normalized average progress for MTP in a non-fading channel with sine pattern and different values of Bw- Legend is the same as in Figure 6.5 90 6.12 Normalized average progress for MFR in a Rayleigh fading channel with red pattern and different values of Bw- Legend is the same as in Figure 6.15 91 6.13 Normalized average progress for MFR in a Rayleigh fading channel with sine pattern and different values of Bw- Legend is the same as in Figure 6.15 91 6.14 Normalized average progress for NFP in a Rayleigh fading channel with red pattern and different values of Bw- Legend is the same as in Figure 6.15 92 6.15 Normalized average progress for NFP in a Rayleigh fading channel with sine pattern and different values of Bw 92 6.16 Normalized average progress for MAD in a Rayleigh fading channel with red pattern and different values of Bw- Legend is the same as in Figure 6.15 93 6.17 Normalized average progress for MAD in a Rayleigh fading channel with sine pattern and different values of Bw- Legend is the same as in Figure 6.15 93 6.18 Normalized average progress for ARR in a Rayleigh fading channel with red pattern and different values of Bw- Legend is the same as in Figure 6.15 94 6.19 Normalized average progress for ARR in a Rayleigh fading channel with sine pattern and different values of Bw- Legend is the same as in Figure 6.15 94 6.20 Normalized average progress for MTP in a Rayleigh fading channel with red pattern and different values of Bw- Legend is the same as in Figure 6.5 95 6.21 Normalized average progress for MTP in a Rayleigh fading channel with sine pattern and different values of Bw- Legend is the same as in Figure 6.5 95 A.l Illustration of the partial excluded region for MFR 113 A.2 Illustration of the partial excluded region for NFP 114 A.3 Illustration of the partial excluded region for MAD 115 A.4 Illustration of the partial excluded region for ARR 116 X Glossary Acronyms ARR cdf GPS MAD MFR MVR NFP MTP pdf PRN rv Notations r.7 0,0 A Ae Ae(rc) Angular Deviation to Transmission Range Ratio Cumulative distribution function Global Positioning System Minimal Angular Deviation Most Forward with Fixed Range Most Forward with Variable Radius Nearest with Forward Progress Maximal Transmission Potential Probability density function Packet radio network Random variable Power loss factor received power Angle between XD and XY Average number of nodes per unit area Area of an excluded region Area of a partial excluded region within distance rc of node Y XI Bw Beamwidth of a directional antenna c Capture ratio D Node X's destination node Ef Event that a node finds a neighboring node in its forward direction Fr(7) Cumulative distribution function of V / r(7) Probability density function of T /R,e(r5 0) J° m t probability density function of R and 0 K A packet transmitted by node X to node Y onto node D N Connectivity, average number of nodes in a circular area of radius rmax Nr Number of receiver antennas at a node Pr (Ef) Probability of the event Ef pt Probability of a node being in transmission mode qi(r, 6) Capture probability of packet K by node Y given i interfering nodes Ryr Distance between node X and node Y - • rmax Maximium transmission range S Throughput X A transmitting node Y X's intended receiving node Z, z Progress of packet K towards node D "2 Average progress Zn Normalized average progress Xll Acknowledgement I would like to express sincere gratitude to my research supervisor, Dr. Cyril Leung, who has provided me with the research topic as well as many helpful suggestions and constant supervision. I would like to thank Dr. Victor Leung and Dr. Takis Mathiopoulos for reviewing the thesis. I would also like to thank Mr. William Cheung for his help in verifying some of the simulation results. Last but not least, I am very grateful to my parents for their support and encouragement throughout my student life. This research work was partially supported by a University of British Columbia graduate fellowship, a University of British Columbia Electrical Engineering Department "Top-Up" Scholarship, a British Columbia Telephone Company Graduate Scholarship, a Hughes Aircraft of Canada Limited Scholarship, and NSERC grant OGP0001731. xiii Chapter 1 Introduction Packet radio is a technology that extends the application of packet switching. Packet radio networks (PRNs) have evolved from the traditional networks of point-to-point communication lines to the networks of broadcasting on VHF/UHF radio channels [1]. PRNs permit mobile digital communication applications over a wide geographic area and provide a degree of flexibility in rapid deployment and reconfiguration which currently is not possible with fixed plant installations [2]. When the channel is occupied by bursty traffic from a large number of nodes, PRNs with random access schemes, such as ALOHA [3], slotted ALOHA [4], Carrier Sense Multiple Access (CSMA) [5], etc. offer efficient ways of using the multiple access channel. Although random access schemes can provide highly efficient use of a radio channel, they give rise to the possibility of a collision when several packets are transmitted at about the same time. If the packets are received with more or less the same powers, it is reasonable to assume that they will all be destroyed [3], [5], [6]. However, this assumption is somewhat pessimistic in a radio transmission environment. The performance improvement brought about by the fact that the transmitting nodes may be at different distances from the receiver (and hence their respective packets received with different power levels due to attenuation) has been discussed [4], [7]—[10]. This phenomenon has been referred to as the near-far or capture effect Another phenomenon in the radio environment is fading [11], [12]. Propagation of VHF/UHF radio waves in urban areas takes place mostly by diffraction or reflection by l Chapter 1. Introduction 2 obstacles in the vicinity of the node. Under certain conditions, it can be shown that the short-term amplitude of the received signal is well approximated by a Rayleigh distribution. The effects of Rayleigh fading in ALOHA systems have been studied in the literature [13H18]. So far, most of the published papers relating to PRNs address single-hop systems in which a node can communicate directly with all other nodes. Hence, no packet routing problem exists in single-hop PRNs. As a network becomes larger, a node may not be able to reach another node in one hop due to transmit power constraints. As the number of nodes increases, it may also be desirable to go to a multihop system which employs spatial frequency reuse to achieve better spectrum efficiency. In this event, a node will require repeaters to forward packets on to the destination. Such networks have been referred to as multihop PRNs [19], [20]. The key point in a multihop PRN is that different nodes can transmit with the same carrier frequency in different parts of the network, and more than one of these transmissions could be received successfully by their corresponding intended receiving nodes in the same time slot. In multihop PRNs, a transmission strategy involves designing a routing algorithm, determining the range rmax and the transmission probability for each node in the network. Routing is one of the major problems in multihop PRNs [2], [21]. Another important problem is the determination of rmax for each node in the network. A transmitting node X chooses one of the nodes, within distance rmax of X, as its intended receiving node. A multihop system starts to resemble a single-hop system as rmax increases. A larger rmax will increase the probability of finding a receiving node in the desired direction and contribute a larger progress towards the destination if the transmission is successful. However, it will also result in a higher probability of interfering with other transmissions. A smaller rmax can reduce the interference but will contribute a smaller Chapter 1. Introduction 3 progress towards the destination if the transmission is successful. This is the trade-off in choosing the optimal rmax in multihop PRNs. In this thesis, we study the performances of five transmission strategies in a multihop PRN with various interference models. The nodes are assumed to be randomly distributed in an infinitely large plane according to a two-dimensional Poisson distribution. Hence, the results obtained in this thesis can apply to a mobile network or a stationary network in which the nodes are randomly located. This thesis is organized as follows. In Chapter 2, a number of models and assumptions are discussed. The previous and related works in multihop PRNs are also summarized in this chapter. In Chapter 3, two previously proposed routing schemes, Most Forward with Fixed Range (MFR) [19], [20] and Nearest with Forward Progress (NFP) [22], are discussed. Three new routing schemes, Minimal Angular Deviation (MAD) [23], [24], Angular Deviation to Transmission Range Ratio (ARR) [23], [24], and Maximal Transmission Potential (MTP) are also proposed. In Chapter 4, the performances of the five transmission strategies based on the MFR, NFP, MAD, ARR, and MTP routing schemes are examined with a number of different interference models. The transmission strategies based on ARR and MTP are shown to generally have better performances than the other three transmission strategies. In Chapter 5, a multiple antenna system is proposed in which the nodes in the network make use of multiple receiver antennas so as to provide diversity reception. The performances of the five transmission strategies in a Rayleigh fading environment are examined. Results show that the performances of all five transmission strategies can be substantially improved by employing multiple antennas. In Chapter 6, we study the performance improvement of the transmission strategies Chapter 1. Introduction 4 brought about by using directional transmitter antennas with a more realistic model than those in [25] and [26]. Two antenna patterns, red function and sine function, are considered. Results show that the performances of all five transmission strategies can be improved by reducing the beamwidth of the antennas. The main contributions of the thesis are summarized in Chapter 7. A number of suggestions for further research are also outlined. Chapter 2 Preliminaries In this chapter, a number of models and assumptions which will be used in subsequent chapters are discussed. In Section 2.1, we described a slotted ALOHA system which is used in evaluating the performances of the transmission strategies throughout this thesis. Two channel models, a non-fading channel and a Rayleigh fading channel, are discussed in Section 2.2. Two capture models and various interference models are discussed in Sections 2.3 and 2.4, respectively. In Section 2.5, two antenna patterns, reel function and sine function, for the directional antennas considered in Chapter 6 are described. The network model for the multihop PRN and the performance measure used for the transmission strategies are described in Sections 2.6 and 2.7, respectively. The previous and related works are summarized in Section 2.8. 2.1 Slotted ALOHA In a pure ALOHA system [3], each node transmits as soon as a packet arrives. The node then waits for an acknowledgement from the receiver. If no acknowledgement arrives after some timeout interval, the node retransmits its packet after some random time interval. Since each node transmits its packet independently, there is a possibility that two or more packets will collide at the receiver. Packet synchronization is employed in a slotted ALOHA system in order to reduce the likelihood of a collision [4], Any node which has a packet ready to send will start transmitting only at the beginning of a slot. In this case, no partial collision can occur. 5 Chapter 2. Preliminaries 6 2.2 Channel Models Two types of channels are considered: non-fading and Rayleigh Fading. The non-fading channel is based on a flat terrestrial propagation model [27] in which the normalized received signal power T, hereafter referred to simply as the received power, at the receiver varies with the transmitter-to-receiver distance r as T(r) = 1 (2.1) where /5 is the power loss factor. For land mobile radio systems, a typical value of ^ is 4 [8], [9], [14] and we will use this value throughout this thesis. The fading channel model assumes that the received signal amplitude is Rayleigh. This results in the received signal power having an exponential distribution with a mean // given by (2.1), i.e., Ml) = -e-i. (2.2) 2.3 Capture Models Various conditions under which a data packet is assumed to be successfully received ("captured") have appeared in the literature [4], [8]-[10], [13]-[16], [28]-[36]. The following two capture models [4], [8]—[10], [13], [14], [16], [28] are commonly used. Suppose that node X transmits packet K to a receiving node Y in a given time slot and the received power at Y is 7<. Let the probability of successful reception of K by Y given a set of i interfering signals (excluding any transmission by Y) with received powers at Y {71, 72, • • • , 7,-} be denoted by pc (7*, 71, 72, • • • , 7i )• It is assumed that the received signal powers are more or less constant over a packet duration and that only the packet with the largest received power can be captured [4], [8]-[10], [13]-[16], [28]-[36]. Chapter 2. Preliminaries 1 Then the capture model in [4], [9], [16], and [28] corresponds to { 1, if 7< > c max { 71, 72, • • • , 7i } (2.3) 0, otherwise and the capture model in [8], [10], [13], and [14] corresponds to ( l , i f 7 t > c ( E 7 i ) „ , , Pc (ft, 7i> 72, • • • , 7») = < \ i=i / (2.4) v 0, otherwise. In (2.3) and (2.4), the parameter c is referred to as the capture ratio, and is greater than 1 for non-spread-spectrum systems. The actual value for c depends on the modulation and coding schemes used. For convenience, we will refer to conditions (2.3) and (2.4) as capture models 1 and 2, respectively. Even though capture model 1 is somewhat unrealistic and leads to optimistic results, its use often allows for simpler analytic derivations. 2.4 Interference Models Suppose node X transmits packet K to node Y. The reception of K by Y could be unsuccessful due to interference from other transmitting nodes. Let M be an interfering node which transmits in the same time slot as X transmits to Y. Four different models for the interference to Y by M are considered: Interference model 1.1: In this model, every transmitting node in the network has a fixed transmission range [19], [20]. Only the nodes within the transmission range can hear the transmission; other nodes cannot hear the transmission at all. Since the transmission range is fixed, Y will receive K successfully if and only if there is no interfering node within the fixed transmission range. The fixed transmission range assumption implies that every node transmits with the same constant power. However, this model suggests that the probability of successful reception Chapter 2. Preliminaries 8 of K by Y is independent of the distance between X and Y. Since this is unrealistic, we will not use this interference model. Interference model 1.2: Every transmitting node in the network adjusts its transmission power to be strong enough to reach its intended receiving node [22]. In this case, the distance between node X and its intended receiving node Y is defined as the transmission range of X. In this model, every transmitting node transmits with variable range and hence, the interference to other nodes can be reduced. Note that Y will receive K successfully if and only if Y is not within the transmission range of any interfering node. This interference model always yields a better performance than interference model 1.1 for a given set of nodes because the interference at Y is decreased by reducing the transmission ranges of the interfering nodes. Interference model 2.1: Every transmitting node transmits with constant power, and the non-fading or the Rayleigh fading channel model and capture model 1 are assumed [26]. In this model, Y will receive K successfully if the received power of K at Y exceeds the strongest interfering power at Y by a capture ratio c. Interference model 2.2: Every transmitting node transmits with constant power, and the non-fading or the Rayleigh fading channel model and capture model 2 are assumed [37]. In this model, 7 will receive K successfully if the received power of K at Y exceeds the total interfering power at Y by c. The only difference between interference models 2.1 and 2.2 is the capture model. Since capture model 2 is more realistic than capture model 1, the use of interference model 2.2 should lead to more realistic results. Chapter 2. Preliminaries 9 2.5 Antenna Patterns Two different antenna radiation patterns are considered. The first antenna pattern is a red function: f 1, -2f < <$> < \ m = \ (2.5) t 0, otherwise where g(-) is the normalized power gain, <f> is the orientation angle and Bw is the half-power beamwidth. This is the model of an ideal antenna. Although no real antenna pattern can be represented by a red function, the antenna pattern of (2.5) is considered for comparative purposes. The second antenna pattern is a sine function: g{4) = < ( 2.78 <j> \ I \~Bw~) (2.6) -n -37C/4 -nil -n/4 0 rc/4 TC/2 Orientation Angle § / • — ^ g; ~^C c '3 O <U £ o Pu •a Q N C3 O 55 1.0 1 0.5 n I _ -red sine / / / / / / / . - - 7 — w , J ' ' ' \ ' \ ' \ /' \ ' X / x / ^ 1 i \ \ \ \ \ \ \ \ \ V ^ . . - - r — - -« 3n/4 Jt Figure 2.1 Antenna radiation patterns, red function and sine function, with half-power beamwidth Bw = §. Chapter 2. Preliminaries 10 where g(-), </>, and Bw are as defined in (2.5). Some antenna patterns can be modelled approximately by a sine function [38]. Figure 2.1 shows the two antenna patterns with Bw = f • It is preferable that the gain fall off rapidly at the two half-power angles ± 4 p and remain as low as possible outside the main lobe. If a node transmits with such a directional antenna, the interference to nodes beyond the half-power beamwidth region will be substantially reduced. 2.6 Network Model The network model and assumptions are basically the same as those used in [19], [20], [22], and [24]. • Transmission protocol: slotted ALOHA. The slot duration is equal to the transmission time of a packet and the acknowledgement channel is noiseless. • Transmission probability: all nodes are assumed to have packets ready for transmission at all times (heavy traffic assumption). For every slot, each node is in transmission mode with probability pt and not in transmission mode with probability (1 — pt), where 0 < p* < 1. A node can transmit only if it is in transmission mode. • Spatial distribution of nodes: two-dimensional Poisson point process with average number of nodes per unit area equal to A. For a given region with area A, the probability p* that there are k nodes in the region is fc! and these nodes are uniformly distributed in the region. • Knowledge of node locations: each node is assumed to know the positions of those nodes within distance rmax of its location; they are said to be its neighbors (or neighboring Chapter 2. Preliminaries 11 nodes). The connectivity (average number of nodes within rmax) is denoted by N and is equal to X^r2max. Packet addressing: each transmitted packet contains the address of the receiving node. A node will discard a packet which is not intended for it. Direction of the destination: each node is assumed to know the direction of the destination. For every slot, the direction of the destination of a packet for each node is assumed to be uniformly distributed in [—TT, IT). • Transmitting-receiving capability: each node can either transmit or receive a packet, but cannot do both, in the same time slot. With the assumption of the spatial distribution of nodes, we can interpret the results in Sections 4.4.1 to 4.4.3, 5.4, and 6.4 as the performance for a mobile network or the average performance for a network in which the nodes are stationary, but whose locations are chosen at random. For a mobile network, the assumption that a node would know the locations of the other nodes may seem somewhat unrealistic. One possible approach is for each node to broadcast its location at regular time intervals. A node can determine its own location using a system such as Global Positioning System (GPS) [39] which can provide an accuracy of a location within 5 meters. The broadcast could be done using a pure ALOHA random access scheme over a land radio channel or a satellite channel. A node would send a location update whenever it moved beyond a certain distance from its last reported location. It should also periodically send a location update so as to inform the network that it is still active. In the land radio channel case, the location information is transmitted at high power. 2.7 Performance Measure For a single-hop PRN, a commonly used system performance measure is the throughput, Chapter 2. Preliminaries 12 defined as the average number of successful packet transmissions per time slot. In a multihop PRN, throughput is defined as the number of successful (one-hop) transmissions for a node per time slot. Since every node in a single-hop PRN can communicate directly with all other nodes in one hop, the throughput of the network also gives the end-to-end throughput. However, this is not the case in a multihop PRN and hence, the use of throughput as a system performance measure may not be appropriate. The end-to-end throughput of a transmission strategy in a multihop PRN appears to be difficult to obtain. A common performance measure for a multihop PRN transmission strategy is the normalized average progress, measured on a per slot basis, of a packet towards its destination [19], [20], [22]. In Figure 2.2, X transmits K to Y as the first step in forwarding K to the destination D. If the distance between X and D is much larger than rmax, the progress z can be approximated by rcosfl. Let the average progress be denoted by Z. The normalized average progress Zn is defined as Z\f\ where A is the average number of nodes per unit area. Since the Figure 2.2 Illustration of the progress towards the destination with a successful transmission. Chapter 2. Preliminaries 13 average distance between a node and the node nearest to it is -j*, the term \/X in Zn is a normalization factor. The normalized average progress is used as a dimensionless measure. For a given network model, interference model, and routing scheme, Zn depends on A and rmax only through the connectivity N = A7rr^ax. This is because for a fixed value of N, a change in A amounts merely to a rescaling of rmax. If |0| < f, we say that there is forward progress and that Y is in the forward direction of X. Otherwise, we say that Y is in the backward direction of X. 2.8 Review of Related Works Relatively few papers have dealt with multihop PRNs compared to the literature on single-hop PRNs. The previous works and results related to multihop PRNs with randomly distributed nodes are summarized in this chapter. The network models assumed in these papers are mostly the same as the model described in Section 2.6, and interference model 1.1, 1.2, or 2.1 is assumed. Routing and the determination of the transmission range for each node in the network are the two problems which have been studied in multihop PRNs. A number of papers have dealt with the selection of transmission ranges to optimize the system performance using slotted ALOHA. Kleinrock and Silvester [19] first proposed a routing algorithm Most Forward with Fixed Range (MFR) in which interference model 1.1 is assumed. In [19], a node transmits with a fixed range to another node which results in the most forward progress. If no forward progress is made, then the least backward progress is preferred. The goal of MFR is to minimize the number of hops needed for a packet to reach its destination. It is shown in [19] that a connectivity of 5.89 optimizes the normalized average progress Zn. Given the average number of nodes per unit area A, this allows the optimal transmission range to be determined. Later Takagi and Kleinrock [20] improved on this model and showed that the maximum Chapter 2. Preliminaries 14 value of Zn is 0.043 at a connectivity N = 7.7. This result is obtained by optimizing the probability pt of a node in a transmission mode. Hou and Li [22] provided a more precise analysis and concluded that 6.0 is a better estimate of the connectivity to optimize Zn. They also found that the maximum value of Zn is 0.047. In [22], transmissions resulting in backward progress are not allowed, and a more detailed investigation of the progress is done taking account of the fact that an interfering node cannot be located in a certain region. Although the disallowance of backward progress in MFR can improve Zn, the improvement is not large and becomes negligible as the connectivity increases. Hou and Li [22] modified MFR to Most Forward with Variable Radius (MVR), and introduced another routing scheme, Nearest with Forward Progress (NFP). In MVR and NFP, interference model 1.2 is assumed. MVR is similar to Hou and Li's MFR except that interference model 1.2 is used instead of interference model 1.1. In MVR, a transmitting node adjusts its transmission power to be just strong enough to reach the receiving node in forward direction. Thus, it tries to reduce interference to other packets while maintaining the goal of obtaining the largest progress possible if the transmission is successful. In NFP, a node transmits to the nearest neighbor which results in forward progress. The transmission range is also adjusted to be equal to the distance between the transmitter and the receiver. The goal here is to reduce conflict as much as possible. For MVR, the maximum value of Zn shown in [22] is 0.056 which occurs at iV = 6.0, and the maximum value of Zn for NFP is 0.055 at iV = 7.7. For MFR and MVR, Zn decreases as N increases whereas for NFP Zn tends to remain constant. Therefore, NFP has the best performance for N > 7. Yee and Shiao [40], [41] optimized the end-to-end throughput for a network of arbitrary topology with fixed node locations and interference model 1.1. In [40] and [41], the optimization problem is formulated as a non-linear programming problem and nodes are Chapter 2. Preliminaries 15 allowed to have different transmission probabilities. The end-to-end throughput of such an optimal routing scheme can be improved substantially over that of MFR for a network with a small number of nodes. The improvement is reduced as the number of nodes increases. Yee and Shiao [42] simplified the optimization problem to a linear programming problem for a subclass of PRNs considered in [40] and [41]. In [42], the nodes are restricted to transmit with the same probability. Hajek [43] used a different measure, efficiency, to study the network performance. The efficiency is the average progress divided by the area covered by the transmission. In [43], Hajek determined the optimal efficiency under the same assumptions made in [19]. He also showed that if a transmitting node can adjust its transmission power to be just strong enough to reach the receiving node, the optimal connectivity is about 3, and the optimal efficiency in this case results in an increase of 85% compared to the case of [19] in which the optimal connectivity is about 6. Chang and Chang [25] have studied the use of directional transmitter antennas with interference model 1.1 and showed that performance is substantially increased since interference is largely eliminated by reducing the beamwidth of a directional transmitter antenna. Zander [26] also studied the use of directional transmitter antennas but his work focuses on networks with high connectivity with interference model 2.1. Shacham and King [44] have proposed a scheme which uses several subchannels. They showed that there is little or no performance gain achieved by splitting a channel into multiple subchannels. Nelson and Kleinrock [45] studied the effect of capture under a different routing algorithm. In their model, a node forwards a packet to one of its neighboring nodes, in forward direction, with equal probability. Takagi and Kleinrock [20] investigated the capture effect on MFR. They showed that the normalized average progress in a system with Chapter 2. Preliminaries 16 perfect capture is about 36% better than that in the system without capture. Hou and Li [46] also investigated the capture effect on MFR. The capture model used in [20], [45], and [46] is somewhat similar to capture model 1 described in Section 2.3. Zander [26] studied the performance improvement using directional transmitter antennas with capture model 1. Chapter 3 Routing Schemes In this chapter, we describe two previously proposed routing schemes, Most Forward with Fixed Range (MFR) and Nearest with Forward Progress (NFP), and three new routing schemes, Minimal Angular Deviation (MAD), Angular Deviation to Transmission Range Ratio (ARR), and Maximal Transmission Potential (MTP), for a multihop PRN. Suppose node X wants to send a packet K to the destination node D. If D is out of range of X, X may need to send K to a neighboring node Y as a first step towards D. The choice of the receiving node Y in a routing scheme involves a trade-off: a larger distance between X and Y will tend to contribute a larger progress of K towards the destination if the transmission is successful. For interference model 1.2, a larger distance is equivalent to a larger transmission range and hence, more nodes will experience interference by the transmitting nodes. For interference models 2.1 and 2.2, a larger distance translates to a smaller average received signal power (at Y) for K. Therefore, a larger distance generally results in K becoming more vulnerable due to the interference by other transmitting nodes and hence, reducing the chance of a successful reception of K by Y. For all five routing schemes, if X cannot find a neighboring node in the forward direction, it refrains from transmitting. The joint probability density functions (pdf's) fR,e{r, 0) of the distance R between X and Y and the angle 0 between the destination direction of X and XY for the MFR, NFP, MAD, and ARR routing schemes are derived in Sections 3.1 to 3.4. These pdf s will be used in Chapters 4 to 6. Throughout this thesis, it is understood that R is in the range [0, rmax] and 0 is in the range [ - § , § ] . 17 Chapter 3. Routing Schemes 18 If X transmits to Y, there is a region in which no node can be located. We will refer to this as an excluded region. The area of the excluded region is required in the derivation of /iJ,©(r5 9), and the evaluation of the throughput and normalized average progress in Chapters 4 to 6. The excluded regions as defined here are slightly different from those in [22]. In [22], the portion of an excluded region beyond distance rmax from Y is not considered. For interference models 1.2 and 2.1, any transmitting node, excluding X and Y, beyond distance rc from Y does not interfere with Y. The values of rc for interference models 1.2 and 2.1 are i rmax and c?r, respectively. We refer to the portion of an excluded region within distance rc of Y as a partial excluded region. The area of a partial excluded region Ae(rc) depends not only on rc but also on r, 6, and the routing scheme. As rc increases, the area Ae(rc) becomes larger and finally equals to the area of the excluded region Ae as defined in this thesis. In any case, Ae(rc) = Ae for rc > 2rmax. The areas Ae(rc) for the MFR, NFP, MAD, and ARR routing schemes are given in Appendix A. Let Ef be the event that X can find a neighboring node in the forward direction and Pr (Ef) be the probability that the event Ef occurs. We have Pr (Ef) = 1 — Pr (No neighboring node in the forward direction) = 1 — exp ( —-A7rr, 2^lrrmax 1 - exp ( -!L\ . (3.1) Unless otherwise stated, all pdf s and cumulative distribution functions (cdf s) discussed in this chapter are conditioned on Ef. The conditioning is not shown explicitly in order to simplify the notation. Chapter 3. Routing Schemes 19 3.1 Most Forward with Fixed Range (MFR) Scheme In MFR [19], X transmits to the receiving node Y which results in the most forward progress (the largest value of r cos 6). If no node with forward progress is found, the node with the smallest backward progress is chosen. Hou and Li [22] modified MFR so as to allow only forward progress. In this routing scheme, a successful transmission results in the largest progress possible. However, a larger progress translates to a larger distance between X and Y; hence the chance of a successful reception by Y also decreases. Hou and Li referred to this routing scheme as MVR when it is associated with interference model 1.2. Hereafter, we will refer to this routing scheme as MFR regardless of the interference models assumed. The receiving node selection for MFR is shown in Figure 3.1. The area Ae of the excluded region, shown as shaded in Figure 3.1, is derived in [20], [22] as Ae = A2 = r2 ' max "" 'max . - . - 1 I Z \ C° " V r I V max / -if ' ' V max ; z Y rmax z ) Z \ll ^ ' 1~max y rmax (3.2) where z = r cos 6. Let Z be the random variable (rv) representing the progress, i.e., the projection of XY onto XD. The cdf Fz{z) of Z, for 0 < z < rmax, is Fz{z) = 1 - Pr (Z > z | Ef) = 1 — Pr (at least one node in Az \ Ef) 1 - exp(-AA») l - e x p ( - f ) exp(—XAZ) — exp (—Y) l - e x P ( - 4 ) (3.3) Chapter 3. Routing Schemes 20 Figure 3.1 Receiving node selection and excluded region for MFR. The pdf fz{z) of Z, for 0 < z < rmox , can then be written as _ 2\y/rmax - z2 exp(-AA z) JZ\Z) = : J—N\ 1 - exp ( - f ) Let L be the rv denoting the vertical distance from distributed outside the excluded (3.4) Y to XD. Since the nodes are uniformly region, the conditional pdf of L, given Z, is ' (3.5) fL\z(l\*) = w ' max for -y/rmax - z2 < I < yjrmax - z2. We can then obtain the joint pdf of Z and L as I - exp ( - V ) (3.6) Since Z — z = r cos 0 and L = I = r sin 6, we can obtain the joint pdf of R and 0 by a change from rectangular to polar co-ordinates [22] /ij,e(r, 0) = r - jvT • 1 - exp (--2-) (3.7) Chapter 3. Routing Schemes 21 3.2 Nearest with Forward Progress (NFP) Scheme In NFP [22], X transmits to its nearest neighbor 7 (with the smallest value of r) in the forward direction as shown in Figure 3.2. For interference models 2.1 and 2.2, the nearer 7 is to X, the larger is the received signal power at 7, and the less vulnerable 7 is to interference from other transmitting nodes; hence the probability of successful reception is improved. For interference model 1.2, the nearer 7 is to X, the less interference (smaller transmission range) is caused to other nodes; hence the overall probability of successful reception is improved. However, the resulting progress is small even if the transmission is successful. For NFP, the area Ae of the excluded region, shown as shaded in Figure 3.2, is [22] Ae = AT=l-r2v. (3.8) The cdf of R is FR(r) = Pr (R < r \ Ef) = Pr (at least one node in Ar \ Ef) - 1 ~ exp(-AAr) ~ l - e x p ( - f ) * C3'9) The pdf of R can then be written as , . . A?rr exp(-AAr) « ' ) " l - e x p ( - f ) ' ( 3 '1 0 ) Since the nodes are uniformly distributed, the conditional pdf of 0, given R, is /e|*(*|r) = \- (3-lD Hence, the joint pdf of R and 0 is [22] 1 - exp ( - f ) Note that this pdf is independent of 0. Chapter 3. Routing Schemes 22 Figure 3.2 Receiving node selection and excluded region for NFP. 3.3 Minimal Angular Deviation (MAD) Scheme In MAD, X transmits to the receiving node with the smallest absolute value of 0, the angle between the destination direction of X and the line joining X and its receiving node. For a given distance, r, between X and Y, minimizing 0 corresponds to maximizing progress. The selection of the receiving node for MAD is shown in Figure 3.3. For MAD, the area Ae of the excluded region, shown as shaded in Figure 3.3, is Ae = Ae 1*1 (3.13) From Figure 3.3, it follows that the cdf of | 6 | is given by F|0,(0) = Pr ( | e | <6\Ef) 1 - exp(-AAfl) 1 - exp ( - f ) * (3.14) Chapter 3. Routing Schemes 23 Figure 3.3 Receiving node selection and excluded region for MAD. By taking the derivative of (3.14), the pdf of | 0 | is obtained as f (ft\ - Xr-2 exp (-A Ae) / | e | ( * ) - A W i _ e x p ( _ f ) . (3.15) (3.16) Because of circular symmetry, we can write f (D\ - l \ J- e*p(-A>lg) Je(t') - •KXrmax- T~W\-2 1 - exp {-^) Since the nodes are uniformly distributed, the conditional pdf of R, given 0 , is proportional to r and is given by 2 r fn\e(r I 0) = (3.17) which is independent of 0 . The joint pdf of R and 0 for MAD can therefore be written as [23], [24] Xr exp(—XAg) fR,e(r, 0) = N\ • 1 ~ exp ( - # ) (3.18) Chapter 3. Routing Schemes 24 The pdf s /R,e(r, 9) for MFR, NFP, and MAD, given by (3.7), (3.12), and (3.18), respectively, appear similar; however, it is important to note that the areas Az, AT, and Ag of the excluded regions for the three routing are not the same. 3.4 Angular Deviation to IVansmission Range Ratio (ARR) Scheme In ARR, X transmits to the receiving node with the largest value of vr, and vT is defined as * = — . (3.19) r ARR is a combination of NFP and MAD in that it tries to minimize r and 6. As shown in Figure 3.4, the motivation in this scheme is for X to choose the receiving node Y whose pair (r, 6) results in the largest value of vT. For ARR, we introduce a r v T which is the reciprocal of vr defined in (3.19). Since T — t = £jj^ represents a circle in polar co-ordinates, it can easily be shown from Figures 3.4 and 3.5 that the locus of points corresponding to a fixed value, t, of T is a circle of radius | . If X is at the origin, the center of the circle is at ( | , 0). For T = t< rmax, the area Ae of the excluded region, shown as shaded in Figure 3.4, is Ae = At = T t2 • (3.20) For t > rmax (see Figure 3.5), •n 2 a + I (t cos <f>y Ae — A.% — rmax a t£ 7T 1 2 2 ~ a " 2 = rmax « + - I o ~ a ~ o s i n (2°0 Chapter 3. Routing Schemes 25 Figure 3.4 Receiving node selection and excluded region for ARR. where a = cos - 1 (l2f2-). The cdf of T is FT(t) = Pr (T < t | Ef) 1 - exp(-AA<) N\ ' 1 - exp ( - f ) (3.22) and the pdf of T is fr(t) = A At exp (—XAt) (3.23) 1 - exP ( - f ) where ^ is the derivative of At with respect to t. Using the uniform distribution property of the user spatial distribution, we can obtain the conditional pdf of 0 , given T = t. Let the area of the shaded region in Figure 3.6 be denoted by Atte. Then we have, A,,e ' [ { ) \0\ + iff-sin \9\ cos 6 Chapter 3. Routing Schemes 26 Figure 3.5 Illustration for the derivation of fr{t) for ARR. P 1 « _ l\e\ + - sm2\9\ ) (3.24) and the partial derivative of Atj can be obtained as ^ ^ - ± 1 ( 1 + 0 0 . * ) . (3.25) For t<rmax, 9 is in the range [—f, f ] and the integration of the partial derivative over such a range is / ( (3.26) We can obtain the conditional pdf of 0, given T = t <rmax, from (3.25) and then normalized by (3.26) as 1 + cos 20 /e|r(0 I *) = 7T (3.27) Chapter 3. Routing Schemes 27 / Lri^ii^ / \^«" /r/ 1 \ / J | %»1^ fet X\ t \ \ 2 l l^^ lpa tj — • Figure 3.6 Illustration for the derivation of /eirC^IO for ARR. For t>rmax, 0 is in the range [— •§, -a] or [a, f ] where a = cos * ( I n f £ ) . We have / ( • 5 tTT a ia8A''»J' iS = ± T T ( a : ' : * max V ^ Similarly, the conditional pdf of 0 , given T = t> rmax, can be obtained as t 2 ( l + cos 20) fe\T(0 11) = irt2 - 2t2a -2 rm a x 0 2 - r* The joint pdf of T and 0 can be obtained from (3.23), and (3.27) or (3.29) as / r , eM) = /e|r(«IO/T(*). (3.28) (3.29) (3.30) Finally the joint pdf of R and 0 for ARR can be derived from (3.30) by changing variable T to variable R using i? = Tcos0 , and is given by [23], [24] 1 / * e ( r , 9) = ^ /T ,e(i , 0) (3.31) Chapter 3. Routing Schemes 28 3.5 Maximal Transmission Potential (MTP) Scheme Ideally, X should choose the receiving node which yields the largest average progress in each time slot. Let ps be the probability of successful reception of K by Y given that X transmits to Y. The average progress ZK of K given that X transmits to Y is ZK = zps (3.32) where z = r cos 6 is the resulting progress if K is successfully received by Y. We can express ZK as ZK = zVscVx{EsJ), (3.33) where psc is the probability of successful reception of K by Y given that X transmits to Y and Y does not transmit, and Pr (ESJY) is the probability that Y does not transmit given that X transmits to Y. Simulation results show that the effect of the excluded region can be neglected in calculating Pr(jES)y). Results also show that the probability that any neighboring node of X does not transmit is typically close to Pr (-Es,y). Hence, maximizing ZK can be approximated by maximizing zpsc. The expressions of psc are implicitly shown in (4.26), (4.33), and (4.50), for interference models 1.2, 2.1, and 2.2, respectively. In MTP, X transmits to the receiving node Y with the largest transmission potential. The transmission potential vp of Y located at (r, 6) is defined as vp = zpsc (3.34) where p3c is an approximation of psc in which the effect of the excluded region is ignored. We choose the receiving node with the largest vv rather than the largest ZK because it is difficult to work with ZK-Chapter 3. Routing Schemes 29 For interference model 1.2, it is difficult to obtain a closed form expression for psc. For interference model 2.1 with the non-fading channel, it can be derived from (4.33) that psc = exp (-Nt) , (3.35) i where Nt is obtained from (4.31) by setting re to 0. If cf>r > rmax, where c is the capture ratio, Nt = Xitpt where r2 ' max ( l ~ \pn^j + (cK2 - r2max)(l -pn) (3.36) i If c?r < r SZ i maxi pn = exp ( — - ) . (3.37) Ajf- l Nt = \rcptc?r'l 1 - -pn 1. (3.38) For interference model 2.2, we can obtain psc from (4.53) by setting re to 0. For the non-fading case, psc = erfcI - yfcTt Kr2 ) , (3.39) where K = XtrptPx {Ef) and erfc(u) = - ^ J exp (—t2) dt is the complementary error function. For the Rayleigh fading case, from (4.57) we can obtain psc = exp j - | VCKT2 | . (3.40) Note that (3.39) and (3.40) are obtained assuming /?=4. They show that the receiving node chosen by X depends on /? and c. This is in contrast to the other four routing schemes discussed earlier in which the receiving node chosen does not depend on (3 or c. Chapter 4 Performance Evaluation of Transmission Strategies In this chapter, we analyze the throughput S and the normalized average progress Zn for the four transmission strategies based on the MFR, NFP, MAD, and ARR routing schemes in a multihop PRN as described in Section 2.6. Three interference models 1.2, 2.1, and 2.2 are considered. Simulation results are provided to validate the simplifying assumptions made in the analysis. Simulation results for the transmission strategy based on the MTP routing scheme with interference models 2.1 and 2.2 are also provided for comparison. Suppose node X transmits a packet K to a neighboring node Y. Let ESiy be the event that Y does not interfere with the transmission from X to Y. This event will occur if Y is not in transmission mode or if it is in transmission mode but cannot find a node, including X, in its forward direction. The probability that X is not in the forward direction of Y is | . We can thus write Pr(£s ,y) = (1 - p t ) + | [ l - P r ( £ / ) ] = 1 - JH + | exp ( - - ) (4.1) where pt is the probability that a node is in transmission mode. In (4.1), we have ignored the effect of the excluded region since it was found from simulation results that taking the excluded region into account yields only a slight change in Pr {ESty), especially for large values of connectivity N. In [22], Pr (ES,Y) is approximated by (1 - pt) and the difference from (4.1) can be substantial for small values of N. 30 Chapter 4. Performance Evaluation of Transmission Strategies 31 Let Es be the event that K is successfully received by Y, given that X transmits to Y. The throughput S, defined as the average number of successful transmissions per slot per node, can be expressed as Tjnax 2 S = pt Pr (Ef) J J Pr (E.) fR,e(r, 0) dO dr , (4.2) 0 "f where Pr (Ef) of X is given by (3.1), and /#,©(?•, 0) is defined in Chapter 3 for the MFR, NFP, MAD, and ARR routing schemes. The probability Pr (Es) is a function of R and 0, and it also depends on the interference model and routing scheme. The normalized average progress Zn can be obtained from (4.2) by multiplying the integrand by -v/Xrcos0, resulting in Tmax 2 Zn = Pt y/X Pr (Ef) f f Pr (Es) r cos 6 / ^ © ( r , 9) d6 dr . (4.3) o - f 4.1 Interference Model 1.2 In interference model 1.2, a receiving node Y is interfered with if it is within the transmission range of an interfering node. In such a case, Y cannot receive any packet successfully. Since the maximum transmission range is rmax, only neighbors of Y can interfere with Y. In Section 4.1.1, we analyze the probability of interference to Y by its neighboring nodes. The probability of interference is then used to obtain S and Zn in Section 4.1.2. The performance analysis of the transmission strategies based on the MFR and NFP routing schemes provided here is more accurate than that given in [22]. 4.1.1 Probability of Interference If the transmission from X to Y is to be successful, every neighbor of Y, excluding X, must not interfere with Y. In this section, we will examine the probability of interference Chapter 4. Performance Evaluation of Transmission Strategies 32 with Y by a neighbor of Y. Let node M be a neighbor of Y and £,„t be the event that M will interfere with Y given that M is in transmission mode. Let pint be the probability of this event which will occur if the transmission range of M is larger than the distance between M and Y. Let E+ and E- denote the events that Y is in M's forward and backward direction, respectively. Since Y is either in M's forward or backward direction with probability \, i.e., Pr(£+) = Pr(£_) = \, we have Pint = ?T(Eint | E+)Pv(E+) + Pv(Eint I £_)Pr(£_) = 1 Pr (Efct | £+) + 5 Pr (£;„« | £ - ) . (4.4) In the following, we assume that M is in transmission mode. Let Y be located at (r0, 90) in a polar coordinate plan centered at M. Let the transmission range of M be r< so that M will interfere with Y if r* > r0. 4.1.1.1 Calculation of Pr(£ t n l |£+) In calculating Pr(£,n f |£+) for MFR, NFP, MAD, and ARR, we ignore the effect of the excluded region and hence, Y is uniformly located in M's forward direction. The effect of the excluded region complicates the analysis, and simulation results show that it affects ?r(Eint\E+) by less than 5%, except for N < 2. In MFR, if Y is in M's forward direction, the calculation of the probability of interference is complicated. Consider nodes which are located in the shaded region with area As as shown in Figure 4.1(a), and let Q be the node in this region which produces the largest progress if the transmission from M to Q is successful. Denote the progress resulting from a successful transmission of M to Q by ZQ. Let A{ be the area of the shaded region shown in Figure 4.1(6). Note that all points in this shaded region have progress larger than ZQ. Then M will Chapter 4. Performance Evaluation of Transmission Strategies 33 Figure 4.1 Illustration of the calculation of Pr (Eini \ E+) for MFR. not interfere with Y if and only if there exists a node Q and no node exists in the region with area A{. As shown in Figure 4.1, Ai depends on the location of Q, but in any case it is larger than An and less than (An + 2Af,). For simplicity, we assume that where An = rl Ab = g S rmar COS COS —1 I z° - 1 Ai — An T A}) To max Z0 1 - Z0 - As - An where z0 = r0 cos 90 and A, = r20(e0 - i8in250V (4.5) (4.6) >, (4.7) (4.8) Assuming that Y is uniformly located in M's forward direction, the probability that Q is in the region with area As is [1 - exp (-A,4S)] and the probability that no node is in the region Chapter 4. Performance Evaluation of Transmission Strategies 34 with area Ai is exp (-XAi). We have for MFR [23] — Tmax ~2 Pr (Eint\E+) = If {1 - [1 - exp (-\A.)] exp {-XAi)} - d60 ^ - dr0 . (4.9) J J T rmai 0 _ | It might be mentioned that in [22], Pr (£t-„t|.E+) is assumed to be 1; this differs from (4.9) by more than 10% for most values of N. Simulation results show that the expression in (4.9) gives a fairly good approximation (less than 2% difference, except for N < 4) to the actual value of Pr(Eint\E+). In NFP, if Y is the nearest node to M in M's forward direction, M will transmit to Y and hence interfere with Y. In this case, there cannot be any node in the shaded region as shown in Figure 4.2, and the area of the shaded region is ^r^. If Y is not the nearest node to M in M's forward direction, M will transmit to the nearest node and not interfere with Y. The probability of no node, not counting X, being located in the shaded region is exp (—^pH. If there is a node other than X in the shaded region, then M will not interfere with Y; otherwise, M will not interfere with Y if and only if X is in the shaded region and hence, the presence of X will result in a decrease in Pr (Eint\E+). Since Y is the nearest neighboring node in the forward direction of X, the probability that X is located in the shaded region is less than \. From the simulation results, it was found that the presence of X decreases the value of ?T{Eint\E+) by about 25%. Using this value and assuming that Y is uniformly located in M's forward direction, we have for NFP [23], Tmax „ ?r{Eint\E+) = | / 1 ^ exp ( - ^ ) <*r0 o max Chapter 4. Performance Evaluation of Transmission Strategies 35 Figure 4.2 Illustration of the calculation of Pr (Eini \ E+) for NFP. In calculating Pr (£?,-„*\E+) in [22], the pdf of the transmission range of M is assumed to be the same as that of X. This assumption is valid only if the probability that no node is located in the shaded region, given by exp (—^"M, *s negligible. In MAD, if Y is in M's forward direction and there is no node is in the shaded region as shown in Figure 4.3, M will transmit to Y and hence interfere with Y. The area of the shaded region is T-^OI0O. If there are nodes in shaded region, M will choose the node with the smallest angle deviation from its destination direction. In this case, the simulation results indicate that the effect of the excluded region is negligible. Therefore, we can assume that the probability of interference averaged over all values of r0 is \ for any given value of 0O. The probability of at least one node, not counting X, being located in the shaded region is [l - exp (-Ar^ax |0O|) ] . We assume that the probability that X is located in the shaded region is « l and the probability of interference, given that only X is located in the shaded Chapter 4. Performance Evaluation of Transmission Strategies 36 Figure 4.3 Illustration of the calculation of Pr (Eint \ E+) for MAD. region, is \. Therefore, the probability of interference given that no node, except possibly for X, is located in the shaded region is ( l — I F ) • Hence, we have for MAD [23], — Vx{Eini \E+) = | J 1 1 [1 - exp(-A rLx^o)] + o = ~ J 1 + exp(-Ar4oa:0o) - ~ e x P ( - ^ r L x ^ o ) 1 1 - exP ( - f ) 1 - exp ( - f ) exp ( - f ) ~ 2 N N2 + 2N 1 , 1 e x P ( ~ f ) , 1 - exp ( - f ) 2 N 2N N2 (4.11) In ARR, if y is in Af s forward direction, the calculation of the probability of interference is also complicated. Since M chooses the receiving node with the largest value of vr, defined Chapter 4. Performance Evaluation of Transmission Strategies 37 / ^ \ ^ m a i A \ **w Y N <// \ w. \ x§|:5 i'.J I If Figure 4.4 Illustration of the calculation of Pr {Eini \ E+) for ARR. in (3.19), M m a y interfere with Y even though there are nodes in the shaded region as shown in Figure 4.4. Simulation results show that if there are nodes in the shaded region, the probabili ty that M wi l l interfere with Y is small. To simplify the analysis, we assume that M will interfere wi th Y if and only if there is no node in the shaded region. The area, AT, of the shaded region is given by f Ar = rl\e0\ + l [ * n - T ~ t - 1 r° V° . Ii Vo t* (4.12) The probabil i ty that no node is located in the shaded region is e x p ( - A AT). Assuming that Y is uniformly located in M ' s forward direction, we have for A R R [23], 7T Ymax 2* ?r(Eint\E+) = f I exV(-\AT)-d602p!-dr0. (4.13) J J ft rmax 0 0 4.1.1.2 Calculation of P r (£,-„<|£J_) As noted in Chapter 3 , if node X transmits to its receiving node Y, there is an excluded region in which n o node is located. For analyzing the performance of the transmission Chapter 4. Performance Evaluation of Transmission Strategies 38 strategies, we will make use of the area of the excluded region within the circle of radius fmax centered at Y. We refer to the excluded region within the circle as a partial excluded region and denote its area by Ae(rmax). The derivation of Ae(rmax) for both MAD and ARR is given in Appendix A and for MFR and NFP appears in [22]. If there were no excluded region, the pdf of the distance between M and Y would be •£*- for 0 < r0 < rmax. Since the excluded region exists near F, the pdf is smaller than 'max 412- for some small values of r0. In determining Pr(£ ini | E+), we did not consider the 'max excluded region for simplicity. In calculating Pr (£,-„* |£L), we model the distribution of the distance between M and Y as fRo(r0) = < 3 r 1 O r2 ? _ ° i r 2 > 0 < r0 < r e 2r 4 (4-14) T5 _ 1 ,2 5 re S ro S rmax 'max 4 « where re = J^Ae. This model assumes that the excluded region is represented by one quarter of the circle with radius re and centered at M. In the analysis in [22], it is assumed that M is uniformly distributed within the range of Y; this results in a pdf for R0 given by 2r0 fRo(r0) = T2-, 0 < r0 < rmax. (4.15) v ' max Simulation results suggest that use of (4.14) yields more accurate results than (4.15) when used in calculating Pr (£,-nt|£L). This is because (4.15) ignores the excluded region. In this case, the probability of M being located near Y becomes larger and hence, Pr (Eint\E-) is also larger. If Y is in the backward direction of M, Y will not be an intended receiving node of M. In most cases, X is also not an intended receiving node of M. The simulation results suggest that the pdf of the transmission range of M, fjit(rt), is the same as that of X, and we make such an assumption in calculating Pr (£,-„<|£L). For MFR, NFP, MAD or ARR we can write Tmax Tt Pr(Eint\E.) = Pr(£/ ) J f / *>„ ) dr0 fRt(rt) drt (4.16) 0 0 Chapter 4. Performance Evaluation of Transmission Strategies 39 For both MFR and ARR, using (4.14) and (4.16) yields [23] Vv{Eint\E.) l:&M~^\IIWr0fRt(n)dn rmax 4 r e I J J 0 0 + / I / 2r0dr0 + / -r0dr0 J fRt{rt)drt re \re 0 rmax 4re J L 0 Tmax + J (r2t - \rljfRt{rt)drt (4.17) where /Kt(rt) can be derived from (3.31) and (3.7) for MFR and ARR, respectively. For NFP, using (3.12), (4.14) and (4.16), we have [23] 1 - exp ( - # ) Vv{Eini | E.) rmax 4 e Axr, exp (--;-••) i j 2 r ' * » l - e x p ( - f ) *» 0 0 v / y '?"/"/ ?3 Wr,exp(-i£) 1 + / 1/ 2r°*°+/ 5r°*7 I -«P(-4) '. o exp r2 _ i r 2 2iV 'ma r 4 e ' •* 2iV - 1 + 4 7 -N 4rlaxJe*n~N2 (4.18) For MAD, using (3.17), (4.14) and (4.16), we have [23] Pv(Eint\E-) = 1 ~ exp ( - | ) r 2 / r 2 _ I r 2 \ moi V m u 4 e / re rt //§'.*. 2 r< dr( o o r max / r t + I I I 2r0dr0 + -r0dr0\2rt drt Chapter 4. Performance Evaluation of Transmission Strategies 40 - 1 ~ eXP ( ~ T ) ( I r4 _ I r 2 r 2 + I A (4l9) ' r2 (-2 _ I r 2 U 9 max A'e 'max f g ' e / • V * ' 1 ^ ' m m V max %7e J \ / 4.1.2 Throughput and Normalized Average Progress The approach used to obtain the throughput £ and the normalized average progress Zn is somewhat similar to that in [22]. Let ES,M be the event that neighbor M does not interfere with Y. This event will occur if M is not in transmission mode or it is in transmission mode but its transmission range is smaller than its distance from Y. Therefore, we have Pr (E3tM) = (1 - pi) + pt (1 - Pint) = 1 - PtPint (4.20) where pint is given by (4.4). Let Es be the event that the transmission from X to Y is successful, given that X transmits to Y, and E{ be the event that Y has i neighbors, not counting X. Then, we have ?v{Es | Ei) = ?T{ES!Y) [?T(ESIM)Y (4.21) for i = 0, 1, 2, • • •. The probability Pr (ES>Y) of Y not transmitting is given by (4.1). In (4.21), we have assumed that the events that nodes do not interfere with Y are independent Such an assumption greatly simplifies the analysis. It was also verified from simulation results that the assumption only affects the performance slightly. Let ^4/(rmar) be the area of the non-excluded region within distance rmax of Y, i.e., Aj(rmax) = " L - 4e(rmax) (4.22) Chapter 4. Performance Evaluation of Transmission Strategies 41 where Ae(rmax) is the area of the partial excluded region. The areas Ae(rmax) for the MFR, NFP, MAD, and ARR routing schemes are given in Appendix A. We can then write 7T Tmax *2 Pr (Ei) = J j Pr (Ei \ R, 0) /*,0(r, 0) dd dr , (4.23) o - f where Pr (Ei \R,S)= [ A A / ( r .m a* ) ] ' exp [ -A Mrmax)} (4.24) and /iz,e(r, 0) for the four routing schemes are given in Chapter 3. We then have oo Pv(Es) = Y,r*(Es\Ei)?T(Ei) t'=0 QQ Tmax 2 = Vv(Es,Y) J2 J j ^ -PtPintY *'=° 0 - £ [-AA^TWr)]' x l ^ "a* " exp [ - A M r m a x ) } fRte(r, B) dd dr = Pr (£s,y) j f exp [ -p f p;nt A A,(rmai) ] /fl,e(r, 0) dO dr. (4.25) 0 - f Using (4.2) and (4.25), we can express the throughput as S = pt Pr (Ef) Pr (Es) = pt Fv(Ef)Pr(Es,Y) w Tmax 2 j f exp[-ptpint\Al(rmax)]fR)Q(r,9)d0dr. (4.26) x 0 - f The normalized average progress can be obtained from (4.26) by multiplying the integrand by y/\rcos$, resulting in Zn = pt Chapter 4. Performance Evaluation of Transmission Strategies 42 Tmas 2 x / / ex.p[-ptpintXAi{rmax)]r cos 9 fR>Q(r, 0) dB dr. (4.27) 0 - f 4.2 Interference Model 2.1 If X transmits packet K to Y which is at a distance r from X, the transmission from any other node may result in unsuccessful reception of K by Y. Let the received power of K at Y be 7(. If the interference power at F by a transmitting node M exceeds ^ , then 7 will not receive /£" successfully. Assuming that the channel is non-fading, the received power of K at Y is given by (2.1) as \ . Let the distance between Y and M be rm; then M will interfere with Y if 4 - > -£%. If X transmits to Y and F does not transmit, Y will receive /iT successfully 1 if and only if there is no other node transmitting within distance ar of Y where a = c$. Such a region is referred to as an interference region; a node in this region, excluding X and Y, which transmits is referred to as an interfering node. Let Ai(rc) and Ae(rc) be the areas of the non-excluded and excluded parts of the interference region within the distance rc of Y. No nodes are located in the excluded region. The areas Ae(rc) for the MFR, NFP, MAD, and ARR routing schemes are given in Appendix A. Let the areas of the non-excluded part of the interference region within and beyond the distance r m o I from Y be A^ and A\2, as shown in Figure 4.5. If ar > rmax, we can show that Ah = Ai{rmax) = rliax* ~ Ac(rmax), (4.28) and A/2 = At(cxr) - Ai(rmax) Chapter 4. Performance Evaluation of Transmission Strategies 43 Ah-^< \ Y / \ 'max/ SP:«^c-:ffi flail w:y%(%&ggs& (J i ' • > v iMyHmfcCffi*-1-: H AM ctr \a Figure 4.5 Illustration of the interference region for interference model 2.1. = 7r(a 2 r 2 - r2max) - Ae(ar) + Ae(rmax) (4.29) If ar < rmax, A\ — 0 and we can write Ah = Ai{ar) = a r2 7r — Ae(ar). (4.30) The probability that Y is in the forward direction of its neighboring node is assumed to be \ as simulation results show that the effect of the excluded region is negligible in this case. If X is ignored and M is a neighbor of Y, the probability that M has at least one node in its forward direction is [l - I exp ( - y ) ] • If M is not a neighbor of 7, such a probability reduces to [l — exp (—y)]. Let Nt be the average number of interfering nodes, i.e., Nt = XptAh N 2 exp l"T + A pt Ah exp (-? (4.31) Chapter 4. Performance Evaluation of Transmission Strategies 44 The probability that there is no interfering node is exp (—Nt). Hence, the probability that the transmission from X to Y is successful, given that X transmits to Y, is Pr(£a) = Pr(£s,y) exp(-JVt), (4.32) where Pr {ES>Y) is given by (4.1). From (4.2) and (4.32), we can obtain the throughput as Tmax 2 S = ptPT{Ef) J J ?T(Es)fRjQ(r,9)d9dr 0 ~ £ ^max 2* = pt Pr (Ef) Pr (£ S i y) f j fRye{r, 0) exp (-Nt) dO dr. (4. 33) 0 —£ The normalized average progress can be obtained from (4.33) by multiplying the integrand by \/Arcos0, resulting in Tmax 2 Zn = PtV\ Pr {Ef) Pr (ES>Y) J J fR>e(r, 6) r cos 6 exp (-JV*) dd dr. (4.34) 0 - f 4.3 Interference Model 2.2 In this section, we derive the capture probability for both non-fading and Rayleigh fading channels with interference model 2.2 [47]. The capture probability is then used for evaluating the throughput and normalized average progress. 4.3.1 Capture Probability If X transmits K to Y which is at a distance r from X, the transmission from any other node will result in some interference to the reception of K by Y. Let g,-(r, 0) be the capture probability of K by Y given that R = r and 0 = 0, and that there are i transmitting nodes, Chapter 4. Performance Evaluation of Transmission Strategies 45 excluding X and Y. These transmitting nodes are referred to as the interfering nodes. Let M be an interfering node and Rm denote the distance between Y and M. We assume that the excluded region can be represented by a circle of radius re, centered at Y. Since the interfering nodes are uniformly distributed outside the excluded region, we assume the pdf of i?m to be fRm(rm) = - o — ^ 5 re < rm < rd, (4.35) where re = J^f-- The areas of the excluded region Ae for the MFR, NFP, MAD, and ARR routing schemes are given in Chapter 3. The pdf in (4.35), referred to as the uniform spatial pdf, is valid if r<f >> r (i.e., rj = lOr) because the interference to Y from nodes beyond distance r<j from Y will be negligible. Let Tm denote the received power at Y from a transmission by M. The pdf /rm(7m) of Vm can be obtained from (2.1) and (4.35). Let r„ be the sum of the interference powers from the i interfering nodes at Y. The pdf fy (in) of r„ is given by the i-fold convolution of frm(jm)- Let Tt be the received power of K at Y and /rt(7t) be the corresponding pdf. The capture probability can be written as qi(r, 0) = j J /rt(7t) /£J(7n) dln djt o o oo oo 0 cy„ We next derive qi for both non-fading and Rayleigh fading cases. In order to get a closed form expression of /p (7n) for the non-fading channel, we approximate the uniform spatial pdf by the following pdf: 2rm expf-x-sO fRm(rm) = />,< . re <rm < oo, (4.37) Chapter 4. Performance Evaluation of Transmission Strategies 46 0.25 <4 0.2 c o § 0.15 W3 I 0.1 :t •§ 0.05 \ - / ' " " " " - ^ y " ^ _ _ l 1 J L 1 1 J _ ..) . 1 _ . \ •c Uniform spatial Bell-shaped spatial \ \ X J 1 1 1 T ~ - | - « .1 1 L. 10 Distance, rm 15 20 Figure 4.6 The uniform spatial and the bell-shaped spatial probability density functions fRm(rm) of distance between Y and M with re = 0 and rd = I0rmax. where erfc(u) = -4- / exp (—t2)dt is the complementary error function. We refer to the pdf in (4.37) as the bell-shaped spatial pdf; it results from assuming a bell-shaped spatial traffic density [14]. As shown in Figure 4.6, such an approximation is quite accurate for rm < < r<j. Since the most significant interference powers to Y are generated from the interfering nodes with the small values of rm, the bell-shaped spatial pdf is a good approximation to the uniform spatial pdf for obtaining the sum of the interference powers at Y. The pdf of Tm can be obtained from (2.1) and (4.37) as jrmv7m) — Id e x p ( - « ) 27!erfc(WY L J 277 ) 0 < 7m < 7e (4.38) where 7e = -r and 74 = ^-. The pdf /p'n (7n) can be obtained using [48, equation (29.3.82)] Chapter 4. Performance Evaluation of Transmission Strategies Al and written as r(0 mtn) = 0 < 7n < 7e , 7e < In < ile, «7e < 7n-(4.39) no closed form expression, 1 0 , Since we do not have a closed form expression for f^ {in) when 7e <7n<*7e> the capture probability is also undetermined when the distance r between X and Y is smaller than c~*re (or the corresponding received power at Y is larger than cye). In such a case, we increase the value of j e in (4.39) to ~x which would result in a lower capture probability. However, the probability that R < c~*re is quite small so that this assumption leads to a good approximation for #(r , 9). The received power of K at Y is Tt = p- for a given distance r between X and Y. Since the received power is a constant for a given value r, the pdf of Tf is a Dirac-delta function. Using (4.36) and (4.39), we can obtain the capture probability for the non-fading channel as » V ^ e x P ( - ^ ? ) 27 I erfc G6D] jdfn (4.40) Letting C = 7« * in (4.40) yields [24], [47] 00 «(r, *) = / SU exp ( - ^ ^ ) erfc^^^/cFTJj Fp)T erfcf^TA/cTrJ d( (4.41) Chapter 4. Performance Evaluation of Transmission Strategies 48 For the Rayleigh fading channel, the average received power of Ft is ^ for a given value r. From (2.2), the pdf of Tt is /r«(7«) = r / ? e x P ( - ^ 7 < ) • From (4.36) and (4.42), we can write the capture probability as [49] 0 eyn oo = / exp [-cr1* 7„J /£J(7n) ^7n oo / exp ( - c r ^ 7 m J /rm(7m) ^7n (4.42) (4.43) where £{•} denotes the Laplace transform and /rm(7m) = / f (7«)- The pdf of Tm can be obtained from the pdf of Rm and (2.2) as oo fvm{lm) = / r j , e x p ( - r ^ 7 T O J / R m ( r T O ) d r m , (4.44) where fRm(rm) is as defined in (4.35). Using (4.43) and (4.44), the capture probability can be obtained as [24], [47] 1 0O oo J J ri exp [-(or? + r £ ) 7m] fRm(rm) dlm drr 0 0 oo f fRmirm) 1 i + cur drt, Chapter 4. Performance Evaluation of Transmission Strategies 49 Td I 2rm • { ' + <(£)' drT, 1 -yfcr2 tan - l \fcr2 — tan W^2)]} (4.45) Note that ?,(r, 0) depends on 0 since re = J^- and Ae depends on 6. 4.3.2 Throughput and Normalized Average Progress In the case where the uniform spatial pdf is used, let Ai be the area of the non-excluded region, where the nodes can be located, i.e., At = r\ 7T - Ae. (4.46) Let Nt be the average number of interfering nodes in the non-excluded region with area At, Le., Nt = \Aipt?v(Ef) (4.47) In (4.47), we have assumed that the probability that any node, excluding Y, has at least one node in its forward direction is Pr (Ef). This assumption is valid if the number of neighbors of X or Y is much smaller than the total number of nodes. For the case where the bell-shaped spatial pdf is used, we also use the same value of Nt for comparison. Let pi be the probability that there are i interfering nodes in a given time slot. Then Niexp(-Nt) Pi = (4.48) The probability that the transmission from X to Y is successful, given that X transmits to Y, is oo Pr (Es) = Pr (E.,Y) Y, Pi *(r' 6)' ( 4 - 4 9 > »'=o Chapter 4. Performance Evaluation of Transmission Strategies 50 where Pr (ESty) is given by (4.1). We can obtain the throughput from (4.2) and (4.49) as Tmax 2 S = pt?v(Ef) J J ?T(Es)fRtQ(r,e)d9dr 0 - S Tmax 2 = pt Pr (Ef) Pr (E.,Y) / / /A,e(r, 9) J T W g,(r, 0) dd dr. (4.50) )( % «=o 0 - £ The normalized average progress can be obtained from (4.50) by multiplying the integrand by V\ rcos$, resulting in 1*max 2 • max £ Q Q Zn = ptV\ Pr (Ef) Pr (EStY) I I /*,e(r, e) r c o s # E « <&(r> *) ^ * • (4-51> { % «=o 0 - f The summation in both (4.50) and (4.51) for the non-fading case can be obtained from (4.41) and (4.48) as oo E pi «fr') = £ i=0 »'=o >! (4.52) It is shown in Appendix B that if r,* —• oo, the summation can be reduced to £ p« 9«(r' ^ ) = exp ( K r S e r f c ( o ^ ^K r 2 ) ^4-53^ »=o ^ ' where /c = A7rptPr (Ef). For the Rayleigh fading case, the summation can be obtained from (4.45) and (4.48) as X>«(M) = E T\ I1 " A^rl t=0 t=0 v d e *»-' (jh) - *--* \ / c ' = exp< f -SMA) - - (*)1H> Chapter 4. Performance Evaluation of Transmission Strategies 51 From (4.47), we have Nt = A ( rj n - Ae ) pt Pr (Ef) . (4.55) If v& —* oo, we have lim -s r = /c. (4.56) rd-*oo rj — rf Hence, (4.54) can be reduced to J T Pl- fi(r, 0) = expi -Vc«r 2 | - tan"1 \Q^s) } ( 4 5 7 ) for ri —»• oo. 4.4 Analytic and Simulation Results In this section, the terms MFR, NFP, MAD, ARR, and MTP are used to refer to the transmission strategies based on the corresponding routing schemes. A number of simplifying assumptions are used in the analysis of the throughput S and normalized average progress Zn for MFR, NFP, MAD, and ARR with different interference models discussed in the previous sections of this chapter. In this section, the validity of these assumptions is verified by comparing the analytic results with those obtained from a Monte-Carlo simulation of the network model with interference models 1.2, 2.1, and 2.2. An optimal value of pt (obtained by searching in pt steps of 0.01) is chosen which maximizes Zn for a given routing scheme and a given connectivity N. It might be noted that the optimal pt value generally decreases with increasing N. Throughout this thesis, the 95% confidence intervals of the simulation results are within ±2% of the average values shown. In the figures to be presented, the analytic and simulation results are represented by curves and symbols, respectively. The simulation program is outlined in Appendix C. Chapter 4. Performance Evaluation of Transmission Strategies 52 In Sections 4.4.1 to 4.4.3, the nodes are assumed to be randomly distributed. Hence, the results in these sections can be interpreted as the performance for a mobile network or the average performance for a network in which the nodes are stationary, but their locations are chosen at random. In Section 4.4.4, we examine the performances of the five transmission strategies in two networks in which nodes are regularly located. 4.4.1 Interference Model 1.2 In this section, analytic and simulation results for MFR, NFP, MAD, and ARR with interference model 1.2 are given. Figure 4.7 shows Zn as a function of connectivity, JV, for the four transmission strategies; the Zn values are obtained using either (4.27) or simulation. The corresponding throughput curves are shown in Figure 4.8. For all four transmission strategies, the analytic and simulation results agree quite closely over the range of connectivity values considered. The greatest difference between the analytic and simulation results for Zn occurs at small values of N. For N>3, the difference for MAD is less than 2%, and for MFR, NFP, and ARR is less than 5%. For comparison, the analytic results provided in [22] for MFR and NFP are significantly smaller than the simulation results. For MFR, the difference is in the range of 10% to 30% depending on the value of N. The difference is larger for a smaller value of N. For NFP, the difference is about 10% for N > 3. From Figure 4.7, it can be seen that MAD always performs better than MFR, and that Zn of both strategies increases first and then decreases as N increases. The reason is that in MFR and MAD, the transmission range is not reduced with increasing traffic so that these two strategies do not cope well with the increasing interference which results from a larger value of N. For NFP and ARR, Zn increases and then stays fairly constant as N increases. This is because the transmission range in NFP and ARR decreases as N increases. The maximum value of Zn for MFR is Chapter 4. Performance Evaluation of Transmission Strategies 53 0.062 and occurs at N = 6. The maximum value of Zn for MAD occurs at JV = 7 and is 0.069, which is about 15% better than that for NFP. For MAD, Zn degrades for JV>7, and becomes worse than NFP for JV> 16. For NFP, Zn stays at the maximum value of 0.060 for N > 9. It can also be seen that ARR performs better than NFP by over 20% for N > 8. The improvement comes about mostly from those cases in which the node transmits to the second nearest neighbor (with a smaller value of 6). For ARR, Zn stays at about 0.073 for N> 11. Figure 4.8 shows the throughput curves for the four transmission strategies. Figure 4.8 is somewhat similar to Figure 4.7, and NFP has the largest throughput. The reason is that the transmission range in NFP is always the smallest among the four transmission strategies and hence, the interference is also the least for NFP. 4.4.2 Interference Model 2.1 In this section, the analytic and simulation results for MFR, NFP, MAD, and ARR with interference model 2.1 are given. The simulation results for MTP are also provided for comparison. The value of c = 4 is used [4], [14] for both analytic and simulation results. Figure 4.9 shows Zn as a function of N for the five transmission strategies as obtained using either (4.34) or simulation. The corresponding throughput curves are shown in Figure 4.10. For MFR, NFP, MAD, and ARR, the analytic and simulation results agree quite closely over the range of connectivity values considered. The greatest difference between the analytic and simulation results of Zn occurs at small values of N. For N>5, the difference between the analytic and simulation results for MFR, NFP, MAD, and ARR is less than 2%. Similar to the case of interference model 1.2, Figure 4.9 shows that MAD always performs better than MFR. The maximum value of Zn for MFR is 0.40 and occurs at N = 4. The maximum value of Zn for MAD also occurs at N = 4 and is 0.042. This is over 10% better than that for NFP, but the performance of MAD degrades Chapter 4. Performance Evaluation of Transmission Strategies 54 for N>5. For N > 12, MAD becomes worse than NFP. The reason is that in MAD the received power of K at Y does not increase with the increasing interference which results from a larger value of N. It can also be seen that ARR performs better than NFP by over 13%, and MTP performs better than ARR by about 10% for JV>6. For iV> 10, Zn stays at about 0.036, 0.041, and 0.045 for NFP, ARR, and MTP, respectively. Figure 4.10 shows the throughput curves for the five transmission strategies. Figure 4.10 is similar to Figure 4.8 in which NFP has the largest throughput. The reason is that the received power of K at Y in NFP is always the largest among the five transmission strategies and hence, the probability of capture is also the largest for NFP. 4.43 Interference Model 2.2 In this section, the analytic and simulation results for MFR, NFP, MAD, and ARR with interference model 2.2 are given. The simulation results for MTP are also provided for comparison. The value of r<j is assumed to be 10 rmax in the simulation. The simulation indicates that there is little difference in the results by increasing the value of rj beyond 10rmai. As in the previous section, the value of c = 4 is used. Figure 4.11 shows Zn as a function of N for the five transmission strategies in a non-fading channel as obtained using either (4.51) or simulation. The corresponding throughput curves are shown in Figure 4.12. For MFR, NFP, MAD, and ARR, the analytic and simulation results agree quite closely over the range of connectivity values considered. The greatest difference between the analytic and simulation results for Zn occurs at small values of N. For N >4, the difference is less than 2%. From Figure 4.11, it can be seen that Zn of both MFR and MAD decreases as N increases while the performance of NFP, ARR, and MTP does not change much. The reason is that in NFP, ARR, and MTP, the average received signal power increases (or the average distance between X and Y decreases) with Chapter 4. Performance Evaluation of Transmission Strategies 55 the increasing interference which results from a larger value of N. It can also be seen that ARR performs better than NFP by about 10%, and MTP performs better than ARR by about 13% for N > 3. MFR, MAD, and ARR have a maximum value of Zn at N = 3 and is about 0.032; for NFP, the maximum value also occurs at N — 3 and is about 0.029. The maximum value of Zn for MTP is about 0.034 and occurs at N = 4. Figure 4.11 shows that ARR is better than MFR, NFP, and MAD for N > 6, and MTP is the best among the five transmission strategies for all values of iV. As noted in Section 3.5, the receiving node Y chosen by X in MTP depends on /? and c. The values of p and c in the expression for psc in (3.39) were set to 4. In the actual system, /3 and c may be different from 4. The effect of this difference on the performance of MTP was studied by using /3 = 3, 4, and 5 and c = 1, 4, and 10. In all cases, the relative performance improvement of MTP over the other four transmission strategies was about the same. This conclusion was also found to hold for interference model 2.1. Figure 4.13 shows Zn for the five transmission strategies in a Rayleigh fading channel. The corresponding throughput curves are shown in Figure 4.14. Compared to the case of no fading, Zn of all five transmission strategies is lowered by about 5 to 11%, depending on the value of N. The throughput curves of these transmission strategies also decrease in the presence of Rayleigh fading. This is in contrast to a contention limited single-hop system in which fading does not generally result in a poorer performance [14], [15]. Simulation results also indicate that the use of (3.39) instead of (3.40) for psc in choosing the receiving node in MTP has little effect on the performance. The shapes of the Zn curves for a given transmission strategy are similar for interference models 1.2, 2.1, and 2.2. The relative performances of the transmission strategies are also about the same for the three interference models. Note that for a given transmission strategy Chapter 4. Performance Evaluation of Transmission Strategies 56 with a given value of N, Zn is largest for interference model 1.2 and smallest for interference model 2.2. The value of N which maximizes Zn decreases as we change from interference model 1.2 to 2.1 to 2.2. 4.4.4 Regular Structure Networks In the previous sections, we have examined the performance for MFR, NFP, MAD, ARR, and MTP in a randomly distributed network with different interference models. In this section, we examine the performance of the five transmission strategies in two regular structure networks with interference model 2.2 and no fading. Figures 4.15 and 4.16 show the distributions of nodes in a square grid network and a hexagonal grid network, respectively. The network assumptions are the same as those in Section 2.6, except that the nodes are now located according to some deterministic pattern. The results in this section are obtained by simulation. If X transmits packet K to Y, only a certain number of combinations of interfering nodes can cause unsuccessful packet reception by Y. The probability of successful reception by Y can be determined in a brute-force way by finding all such combinations. If the distance between X and Y is large, the number of such combinations becomes very large. Except for MFR and MAD with larger values of N, the simulation results were verified by this brute-force method. Figure 4.17 shows Zn of the five transmission strategies in a square grid network. The corresponding throughput curves are shown in Figure 4.18. The maximum value of Zn for MFR and MAD is about 0.038 at the lowest connectivity value of 5 corresponding to a node and its four nearest neighboring nodes. The value of Zn decreases as N increases. For NFP and ARR, Zn is independent of JV. The value of Zn remains at about 0.027 and 0.038 for NFP and ARR, respectively, and MTP performs the same as ARR. For NFP, X chooses one of the nearest neighboring nodes in the forward direction regardless of the resulting progress. For ARR and MTP, X Chapter 4. Performance Evaluation of Transmission Strategies 57 chooses the neighboring node in the forward direction with the smallest angle deviation from the destination direction. Since X always transmits to its nearest neighboring node in NFP, ARR, and MTP, the received power at the receiving node is the same and hence, the capture probability as well as the throughput is the same. The substantial improvement in Zn for ARR and MTP over NFP is due to the larger resulting progress. Figure 4.19 shows Zn for the five transmission strategies in a hexagonal grid network. The corresponding throughput curves are shown in Figure 4.20. The transmission strategies behave relatively the same in both regular structure networks. However, they perform better in the hexagonal grid network. This is because a transmitting node in the hexagonal grid network has more choices in selecting a receiving node at a given distance. The maximum value of Zn for MFR, MAD, ARR, and MTP is about 0.045, and for NFP is about 0.039. Chapter 4. Performance Evaluation of Transmission Strategies 58 0.08 N 8 0.06 o | 0.04 •a ID N 53 0.02 -£ —x----x x. x- ^ :: -•-- . 1 i • ' i ' i ' ' I I L _ l I • 10 15 Connectivity, Af 20 25 Figure 4.7 Comparison of normalized average progress for MFR, NFP, MAD, and ARR with interference model 1.2. 0.15 co 0.1 3 •2 O 0.05 j i u J i i i i 10 15 Connectivity, N 20 25 Figure 4.8 Comparison of throughput for MFR, NFP, MAD, and ARR with interference model 1.2. Legend is the same as in Figure 4.7. Chapter 4. Performance Evaluation of Transmission Strategies 59 0.05 N H 60 O 60 83 S3 -a a 0.03 -| 0.01 0.02 -Analytic Simulation MFR MFR o NFP NFP MAD MAD ARR ARR MTP Figure 4.9 MTP with 10 15 Connectivity, N Comparison of normalized average progress for MFR, NFP, MAD, ARR, and interference model 2.1. 0.12 0.1 03 *s 0.08 p 60 g 0.06 0.04 0.02 0 A X A : tfjkx ~~-A-^ _ A - / *V? V X -J \ \ a ^^<-x-1 \\°°oQa t \ X \ ^ - \ v^ V e-^ > 1 -i i _ i _ _ i — i — i — i — i — i — I _ . J D *-«. D - - 0 -i 1 — a ~-0-_ i , , o * — • • — i i 1 D I — * - — - i i i i 10 15 Connectivity, N 20 25 Figure 4.10 Comparison of throughput for MFR, NFP, MAD, ARR, and MTP with interference model 2.1. Legend is the same as in Figure 4.9. Chapter 4. Performance Evaluation of Transmission Strategies 60 N 0.03 -a 00 o <L> 00 CO s T3 (U N 0.02 •M 0.01 o Analytic Simulation MFR MFR NFP NFP MAD MAD ARR ARR MTP Connectivity, N Figure 4.11 Comparison of normalized average progress for MFR, NFP, MAD, ARR, and MTP with interference model 2.2 in a non-fading channel. CO •4-T 3 PH -C 00 p o 0.12 0.1 0.08 0.06 0.04 -0.02 °0 - £fc - /g v t \ \ D \ \ a a a a \ * V> v — ^ ^ ^ - ~ o -1 L_ . . 1 1 1 . 1 _ L 1 1 D D • ^ - ^ - o -. , , , ! , , D ' • $ , , 1 D 0— 1 1 — 1 [ < t 10 15 Connectivity, N 20 25 Figure 4.12 Comparison of throughput for MFR, NFP, MAD, ARR, and MTP with interference model 2.2 in a non-fading channel. Legend is the same as in Figure 4.11. Chapter 4. Performance Evaluation of Transmission Strategies 61 N 0.03 <D & O & 0.02 a M a 0.01 e3 o G D ° ° D • D D -X - -I I I 1 •«er--*-- - - A - -• D • X -D -A a ; \ - * « - . " " •0"- -—. • $ — _ - . < > 10 15 Connectivity, N 20 25 Figure 4.13 Comparison of normalized average progress for MFR, NFP, MAD, ARR, and MTP with interference model 2.2 in a Rayleigh fading channel. Legend is the same as in Figure 4.11. 0.12 0.1 co 0.08 3 •§b 0.06 3 O P 0.04 0.02 0 -/~\ - p W\ \ - fc^N 1 \ \ D D -' \ 0v \ V \ ^ v \ V V ^ o^*^ ^5— -1 , . _ l — 1 — 1 — 1 — 1 — 1 — 1 — 1 D --$•-D - * -D - - $ - - . 1 I I •5? a — < £ - - . i i 1 -~y-~ D - — 0 - — '--[ < 10 15 Connectivity, N 20 25 Figure 4.14 Comparison of throughput for MFR, NFP, MAD, ARR, and MTP with interference model 2.2 in a Rayleigh fading channel. Legend is the same as in Figure 4.11. Chapter 4. Performance Evaluation of Transmission Strategies 62 • • • • • • • • • • • • • • • • • • Figure 4.15 Distribution of nodes in a square grid network. • • • • • • • • • • • • • • • • • • • / ( \ • • • • s v__^ • • \ ) / • • • • • • • • • • • • • • • • • • • d. h-^ H Figure 4.16 Distribution of nodes in a hexagonal grid network. Chapter 4. Performance Evaluation of Transmission Strategies 63 0.05 N gf 0.04 g o o 0.03 8P > < 0.02 v N « 0.01 --~ 6 -----A MFR NFP MAD ARR MTP E) 0 8 o A 0 X D 1 1 L 1 1 1 B 4 O El A 0 O 1 1 1 B A 0 o __L _ ! H A 0 o . 1 , El A 8 _ i i i 10 20 Connectivity, N 30 40 Figure 4.17 Comparison of normalized average progress for MFR, NFP, MAD, ARR, and MTP with interference model 2.2 in a square grid network. 0.05 0.04 -^ 0.03 J * oo 3 O 0.02 -0.01 -6 8 B B BJ • H ' 0 : ° o ° o o 10 20 Connectivity, N 30 40 Figure 4.18 Comparison of throughput for MFR, NFP, MAD, ARR, and MTP with interference model 2.2 in a square grid network. Legend is the same as in Figure 4.17. Chapter 4. Performance Evaluation of Transmission Strategies 64 0.05 N? CO o v 0-03 a > < 0.02 «•* Nl <n o S5 0.01 ---_ -----a A 1 1 1 EI A 0 o _ 1 . _ 1 _ SI A 0 o 1 1 1 1_ B A 0 o I I I ! SI A 0 o 1 1 8 A 0 o 1 l _ J 1 — H A 0 o 1 1 1 1 1 10 20 30 40 Connectivity, N 50 60 Figure 4.19 Comparison of normalized average progress for MFR, NFP, MAD, ARR, and MTP with interference model 2.2 in a hexagonal grid network. Legend is the same as in Figure 4.17. on •4-T 3 O 0.05 0.04 0.03 0.02 -0.01 . ---1 a , , a 0 o • • H 0 o , 1 . , B 0 o i i 1 i B o o B 0 o 1 1 _ . J — 1 _ B 0 o 10 20 30 40 Connectivity, N 50 60 Figure 4.20 Comparison of throughput for MFR, NFP, MAD, ARR, and MTP with interference model 2.2 in a hexagonal grid network. Legend is the same as in Figure 4.17. Chapter 5 Multiple Receiver Antenna Selection In this chapter, we consider a multihop PRN in which each node has NT receiving antennas. A Rayleigh fading environment with interference model 2.2 is used in this study. In Section 5.1, a multiple receiver antenna system is described. The capture probability for the multiple receiver antenna system is derived in Section 5.2, and its performance is analyzed in Section 5.3. In Section 5.4, the analytic and simulation results of the four transmission strategies based on MFR, NFP, MAD, and ARR routing schemes are provided. Simulation results of the transmission strategy based on the MTP routing scheme are also provided. Results show that the performance of the five transmission strategies can be improved substantially if each node has NT > 1 antennas. 5.1 Multiple Receiver Antenna System We consider a multihop PRN in which nodes make use of NT receiver antennas so as to provide diversity reception [50]. It is assumed that each node has only one radio receiver and hence, a node can only decode the signal at one of the Nr antennas in a given time slot. If the Nr antennas are separated from one another by more than half a wave length, the received signal powers at the antennas are more or less uncorrelated [ 12] in a Rayleigh fading environment. The receiving node chooses which antenna signal to decode based on its knowledge of the signal power received at each of the Nr antennas. It acquires this knowledge by briefly monitoring the signal strengths at each antenna in turn at the beginning of each time slot. Ideally, the receiving node would want to choose the antenna which yields the largest normalized average progress Zn of the packets intended for it. Unfortunately such 65 Chapter 5. Multiple Receiver Antenna Selection 66 an optimal choice appears difficult to implement. Simulation results show that Zn increases and then decreases gradually (for MFR) or stays constant (for NFP) with the received power T at the receiving node. They also indicate that Pr ( r <7*), where 7* is the received power which yields the maximum Zn, is larger than 0.8 for all five transmission strategies. Hence, a scheme in which the receiving node decodes the signal from the antenna with the largest power is close to optimal in most cases. We will examine the performance gain from using such an antenna selection algorithm in Section 5.4. 5.2 Capture Probability Suppose X transmits packet K to Y with R — r and 0 = 0. As in Section 4.3.1, let qi(r, 6) be the capture probability of K by Y given that there are i interfering nodes. The capture probability will be used to analyze the performance of the transmission strategies in Section 5.3. The exact analysis of the capture probability of the transmission strategies in the multiple receiver antenna system described in the previous section is difficult In this section, we derive the capture probability of the multiple receiver antenna system assuming that Y decodes the signal from the antenna with the largest received power of K from X. This is in contrast to the proposed system in which Y decodes the antenna with the largest received power (not necessary the one with the largest received power of K). It is expected that such an assumption leads to optimistic results. The pdf of the received power, Tt, of K at each of the Nr antennas is given by (4.42). Let Ts be the largest received power among the received powers of K at the Nr antennas. The pdf of Ts is given by [51, Theorem 3.6] /r.(7.) = Nr[FTt{is)fr-1 fvXls) (5-1) Chapter 5. Multiple Receiver Antenna Selection 67 where FTM = 1 - exp (--fy (5.2) is the cdf of T< and fi = ^ . From (4.42), (5.1), and (5.2), the pdf of Ts can be written as , , x ^ r ( I s hAls) = — exp I l J V r - 1 E (-n- (* "') exp (5.3) Let the distance between Y and an interfering node M be denoted by #m . The excluded region with area Ae, modelled in the same way as in Section 4.3.1, is represented by a circle of radius re, where re = \/^-, centered at Y. Node M is uniformly distributed in the non-excluded region, and the pdf fRm(rm) of i?m is as defined in (4.35). Only the interfering nodes within distance r^, where rd»r, of Y are considered because the interference to Y from nodes beyond distance rj from Y is negligible. Let Tm denote the received power at Y from a transmission by M, and r n be the sum of the interference powers from the i interfering nodes at Y. The pdf f^ (in) of Tn is given by the i-fold convolution of /rm(7m). Similar to the case of iVr = 1 in (4.43), the capture probability for Nr > 1 can be written as oo oo «(r, 0) = J J tflbn) fT.(ls) d7s dln 0 C7„ Nr * J = 1 ^ ' 0 Cfn OO = E (-1)'+1 £ (N-:!) f «P (-i«''*) $(*)<* N r °° = E (-1)'"" f (*_"/) /exp (" j c r " 7 m ) /r"(7m) **• ,(5.4) Chapter 5. Multiple Receiver Antenna Selection 68 where /rm(7m) = /r„ (7») i s S iven b v C4-44)- Similar to (4.43), the last step in (5.4) is obtained by applying the Laplace transform. Using (4.44) and (5.4), the capture probability can be obtained as [50] 0 0 = E(-^f(t7)f/^¥V*. drr x tan' - ( \/Jcr2 ^—"G/jWl}'-y/fcr2 (5.5) Note that g,(r, 0) depends on 6 since re = J^f- and >le depends on 6. 5.3 Throughput and Normalized Average Progress Similar to the case of Nr = 1 in Section 4.3.2, the throughput for Nr > 1 can be expressed as Tmax 2 ' max z QO S = p, Pr ( £ , ) Pr (Ea>y) J J fR>e{r, 6) £ Pi «(r , *) <*» *", (5.6) 0 _ | where Pr (22/) is the probability of X finding a neighboring node in its forward direction as given by (3.1), Pr (ES>Y) is the probability of Y not transmitting as given by (4.1), and Chapter 5. Multiple Receiver Antenna Selection 69 pi is the probability of i interfering nodes in the non-excluded region as given by (4.48). The normalized average progress can be obtained from (5.6) by multiplying the integrand by \/\rcos0, resulting in Tmax 2 Zn = pt \/A Pr (Ef) Pr (E,lY) f I fR,e{r, e) r cos 0 ] T Pi flfo *) & dr. (5.7) o - f Similar to (4.54) for the case of Nr = 1, the summation in (5.6) and (5.7) can be simplified as 2^ Pi <n(r, 0) * z , (_1) J ,• _ i J exPJ " 1=0 7=1 J \ J / K rd ~ Tl X tan ->r. \A/Tcr2. tan "A^rOJ}' (5.8) where Nu as given by (4.47), is the average number of interfering nodes in the non-excluded region. If rj —> oo, (5.8) reduces to E « « ( r , 9) = f ) (- iy"+ 1 ^ P ' - 1 ) e x p j - V T ^ A ^ . P r ^ r 2 i=o i=i J \ J / I 7T 2 — tan —=_ „ \y/jcr* )]}' (5.9) 5.4 Analytic and Simulation Results In this section, the terms MFR, NFP, MAD, ARR, and MTP are used to refer to the transmission strategies based on the corresponding routing schemes. Similar to the case of Nr = 1 in Section 4.3.2, a number of simplifying assumptions are used in the analysis of the throughput S and normalized average progress Zn for MFR, NFP, MAD, and ARR. The validity of these assumptions is verified by comparing the analytic results with those obtained from a Monte-Carlo simulation of the model described in Section 2.6. Simulation Chapter 5. Multiple Receiver Antenna Selection 70 results for MTP are also provided for comparison. The value of r^ is assumed to be 10 rmax in the simulation. Based on the simulation results, it appears that there is little difference in the results by increasing the value of rj, beyond 10 rmax. As in Sections 4.4.2 and 4.4.3, the value of c=4 is used. An optimal value of pt (obtained by searching in pt steps of 0.01) is chosen which maximizes Zn for a given routing scheme and a given connectivity N. The optimal pt value generally decreases with increasing N. Figure 5.1 shows Zn as a function of N for MFR with different values of Nr as obtained using either (5.7) or simulation. The Zn values for NFP, MAD, ARR, and MTP are shown in Figures 5.3, 5.5, 5.7, and 5.9, respectively. The corresponding throughput curves are shown in Figures 5.2, 5.4, 5.6, 5.8, and 5.10. For MFR, NFP, MAD, and ARR, the analytic and simulation results for Nr < 2 agree quite closely over the range of connectivity values considered. The simulation results are always smaller than the corresponding analytic results because we assume that Y decodes the signal with the strongest received power of K among the NT antennas in obtaining the analytic results. However, Y actually decodes the signal from the antenna with the largest received power (of K and interference) in the simulation. Simulation results ran assuming that Y decodes the signal from the antenna with the largest received power of K agree well with the analytic results. The antenna with the largest received power is not necessarily the one with the largest received power of K. The chance that the former antenna coincides with the latter antenna becomes smaller as iVr increases. Hence, the difference between analytic and simulation results becomes larger as NT increases. The greatest difference for Zn occurs at small values of N. For the four transmission strategies with N>4, the differences are about 1%, 3%, and 7% for Nr = 1, 2, and 4, respectively. For all five transmission strategies, the simulation results show that S and Zn can be Chapter 5. Multiple Receiver Antenna Selection 71 improved by about 25%, and 40% if Nr is increased from 1 to 2, and 4, respectively. The results show that Zn for both MFR and MAD decreases as N increases while the performance of NFP, ARR, and MTP does not change much. The reason is that in NFP, ARR, and MTP the average received signal power increases (because the average distance between X and Y decreases) with the increasing interference which results from a larger value of N. It can also be seen that ARR has a better performance than MFR, NFP, and MAD for almost all values of N and Nr, and MTP performs better than ARR by about 10%. Chapter 5. Multiple Receiver Antenna Selection 72 0.05 N 8 0.04 <u i -00 £ » 0.03 > < 0.02 8 o 2 0.01 --/ / - / ~ ' , ' / -- ifo " u • -1 — 1 I — *s. N* 4* <>-! .« • > - . • ^ ' i - - <> ~ - - -°^©~^ A~~--- -_ 0 A "~~ ^ - & - _ , A - - - - - , _ 0 < ——&— ' - I 1 1 1 I I I 1 1 1 I I 1 I 1 1 1 1 1 1 1 1 10 15 Connectivity, N 20 25 Figure 5.1 Normalized average progress for MFR with various Nr receiver antennas. Legend is the same as in Figure 5.2. 0.15 •*-T a 00 3 O 0.1 0.05 -•f \ Av ^ i \A\o\ i i — . — i — i — i — i — i — i Analytic Nr- 1 Nr=2 Nr = A i Simulation Nr=\ o Nr = 2 A Nr = 4 0 l^^^~----~A --•^r-.-a — i — i — i — | — i — i — i — i — ° 0 5 10 15 Connectivity, N Figure 5.2 Throughput for MFR with various JVr receiver antennas. 20 25 Chapter 5. Multiple Receiver Antenna Selection 73 0.05 c N & 0.04 u M O 4,-0--0 ° ° o o o o o o o o o Figure 5.3 Normalized average progress is the same as in Figure 5.2. 10 15 Connectivity, N for NFP with various Nr receiver antennas. Legend 0.15 CO *s DO 3 O / S 0.05 10 15 u J Connectivity, N Figure 5.4 Throughput for NFP with various Nr receiver antennas. Legend is the same in Figure 5.2. 25 as Chapter 5. Multiple Receiver Antenna Selection 74 0.05 N U O o 0.03 i *f| 0.02 8 o S5 0.01 . • ^ • " • • ^ / : / o ° o o : - - ^ - / < > ' - - ^ , 0 0 A * ^ - i j : ^ — © ~ ^ ~ A ' ~ - - - * J ^ - ! ^ 10 15 Connectivity, N 20 25 Figure 5.5 Normalized average progress for MAD with various Nr receiver antennas. Legend is the same as in Figure 5.2. 0.15 CO a p< X! 00 3 O 0.1 0.05 O H -SEsa i i i • • i • i i -i i i , ,i 10 15 Connectivity, TV 20 25 Figure 5.6 Throughput for MAD with various Nr receiver antennas. Legend is the same as in Figure 5.2. Chapter 5. Multiple Receiver Antenna Selection 75 0.05 % 0.04 o o _ / 0 0 0 0 0 0 0 0 ' 0 ' - - - - — -•''' * A * iTi-n-0 A" 0 "A" J I I L. 10 15 Connectivity, N 20 25 Figure 5.7 Normalized average progress for ARR with various Nr receiver antennas. Legend is the same as in Figure 5.2. 0.15 03 0.1 -3 DO 13 O 0.05 - I D \ A w "v •f ^ V A ^A-?. ° ^ i . i—i _ l 1 1 1 1 1 0 u 0 A U 0 A U 0 A" O , , 1 0 < -""A" ~ U ( _ i i — i — i — 10 15 Connectivity, N 20 25 Figure 5.8 Throughput for ARR with various Nr receiver antennas. Legend is the same as in Figure 5.2. Chapter 5. Multiple Receiver Antenna Selection 76 0.05 N £ 0.04 v & o o 0.03 8P S3 U N 0.02 -o 55 0.01 -0 -I 0 ^ o o o o o o A A A A A A A A \ A - o o 0 0 ° o o o o . o ----Simulation \ Nr=l O 1 JV,= 2 A I Wr = 4 0 1 , , , , 1 , 0 A o 0 A o 1 0 A o 1 1 0 A o 1 1 1 0 < A , o < . 1 — 1 _ 1 . . . 1 _ 0 20 5 10 15 Connectivity, N Figure 5.9 Normalized average progress for MTP with various iVr receiver antennas. 25 0.15 o 0.05 -10 15 Connectivity, N 20 Figure 5.10 Throughput for MTP with various Nr receiver antennas. Legend is the same as in Figure 5.9. Chapter 6 Directional Transmitter Antennas In this chapter, we study the performance improvement resulting from the use of directional transmitter antennas by the nodes in a multihop PRN. Interference model 2.2 is used in this study. We also examine the effect of a non-ideal antenna pattern with and without Rayleigh fading. In Section 6.1, a directional transmitter antenna system is described. The capture probability for the directional transmitter antenna system is derived in Section 6.2, and its performance is analyzed in Section 6.3. In Section 6.4, the analytic and simulation results for the four transmission strategies based on the MFR, NFP, MAD, and ARR routing schemes are provided. Simulation results for the transmission strategy based on the MTP routing scheme are also provided. Results show that the performances of all five transmission strategies can be improved substantially if directional transmitter antennas are employed. 6.1 Directional Transmitter Antenna System Omnidirectional transmitter antennas are employed in conventional multihop PRNs [19], [20], [22]. As a consequence, a transmission causes the same amount of interference in all directions. Employing directional antennas in transmission can limit the interference to other nodes and hence improve system performance [25], [26]. In this chapter, we consider a multihop PRN in which nodes employ directional antennas in transmission and omnidirectional antennas in reception. In such a system, a transmitter always aims its directional antenna at the intended receiving node. The performance improvement brought about by the use of directional transmitter antennas is examined by using a more realistic 77 Chapter 6. Directional Transmitter Antennas 78 interference model than those in [25] and [26]. Interference model 1.1 is used in [25], and interference model 2.1 is assumed in [26]. In both papers, the antenna pattern is assumed to be a red function, and the transmission strategy based on the MFR routing scheme in a non-fading environment is examined. In this chapter, we examine the five transmission strategies based on the MFR, NFP, MAD, ARR, and MTP routing schemes with interference model 2.2. We also consider both red and sine function antenna patterns with and without Rayleigh fading. 6.2 Capture Probability In this section, we derive the capture probability for the Rayleigh fading case; the capture probability for the non-fading case appears to be difficult to obtain because there is no closed form expression for the pdf of the interference power at a receiving node. Suppose X transmits packet K to Y with R = r and 0 = 9. Let g,(r, 9) be the probability of K being captured by Y given that there are i interfering nodes. The capture probability derived in this section will be used to obtain the throughput S and normalized average progress Zn in Section 6.3. Let M be an interfering node and Rm denote the distance between Y and M. There is an excluded region with area Ae, described in Chapter 3, given that X transmits to Y. The excluded region, modelled in the same way as in Section 4.3.1, is represented by a circle of radius re, where re = J^*, centered at Y. Since the interference power to Y by M is negligible compared to the received power of K at Y if rm >> r, we only consider the nodes within distance rd, where rj » r, of Y. Node M is uniformly distributed in the non-excluded region, and the pdf of Rm is given by (4.35). Let U be the destination of the packet transmitted by M and 0 m be the angle between MU and MY. Since the destination Chapter 6. Directional Transmitter Antennas 79 M^ rm/ X^L ~~-J^L Y ^.W ^ . £ 7 Figure 6.1 Illustration of Y, a transmitting node M, M's intended receiving node W, and M's destination U. direction of M is uniformly distributed in [—7r, 7r), the pdf of 0 m is fem(Om) = ±-. (6.1) Based on the model of the non-excluded region assumed above, Rm and 0 m are independent Let $ be the angle between MY and MW where W is the intended receiving node of M. Figure (6.1) illustrates the angles 0 m and $, and the nodes Y, M, W, and U. In the following derivation of the pdf of $, we ignore the effects of the presence of X and the excluded region. For Rm > rmax, $ is uniformly distributed in [— 7r, TT) because Y cannot be the intended receiving node of M in this case. If Y is a neighbor of M and also in the forward direction of M, i.e., Rm < rmax and | 0 m | < f, the distribution of $ is no longer uniform because of the presence of Y. Let the probability that M transmits to Y be denoted by py. In such a case, the intended receiving node W is Y, and the angle $ = 0. Then we have pY = exp(-AA e ) m ) , (6.2) Chapter 6. Directional Transmitter Antennas 80 where Ae,m in (6.2) is the area of the excluded region due to the transmission from M to Y. The area Ae,m can be obtained from Ae by replacing r and 6 by rm and 9m, respectively. The area Ae is defined in Chapter 3 and Appendix A. The probability py can be interpreted as the probability that no node is located in the region with area Ae{rm, 6m). For i?m < rmax and | 0 m | < §, we model the pdf of $ as { PY, <f> - 0 m ^ , 0 < M < f (6.3) 2¥> f < W < * . Otherwise, the pdf of $ is assumed to be uniformly distributed in [— TT, 7T], i.e., /•(*) = 5 7 . (6-4) Z7T In [25] and [26], the pdf of $ is assumed to be uniformly distributed in [ — v, n) regardless of the values of Rm. Such an assumption decreases the probability of interference to Y and hence leads to optimistic results. Let Tm denote the received power at Y from a transmission by M. The pdf /rm(7m) of Tm can be obtained from (2.1), (4.35), and the pdf of $. We can then express /rm(7m) as Td * * 0 r fi ' 7m *.(*.) = / / / j-gj «P r e —w —7r x M<f>) fQm(em) fRm(rm) d<f> d9m drm . (6.5) where #(<£), defined in Section 2.5, is the antenna power gain at the orientation angle <f>. Let T„ be the sum of the interference powers from the i interfering nodes at Y. The pdf /pn (7n) of T„ is given by the i-fold convolution of frm(im)- The pdf /r t(7t) of the received power, Tt, of K at Y is given by (4.42). From (4.36), the capture probability can be written as OO CO qi(r,0) = J J jg(iH)frt(Tt)drn*rn 0 C7n Chapter 6. Directional Transmitter Antennas 81 oo oo / / frlti") r? exP (- r / ?Tt) dyt din 0 Cfn OO / exp {-cr? 7 n J / ^ ( 7 n ) d<yn oo (6.6) where /rm(7m) = / r (7«)- Similar to the omnidirectional antenna case in (4.43), the Laplace transform is used in obtaining the last step in (6.6). From (6.6) and (6.5), qi(r, 6) can be written as Td X X oo *(r, 0) = * ( * ) exp - cr^ + * ( * ) 7m r e —x —a- 0 x fo(4>) fam(9m) fjtm(rm) dim d<j> d$m dr. Td * * US T. —X —X r r m a r x 7r • / / / re —x —x M<f>) feJOm) fRm(rm) cg(<f>)4 + l M<f>) feJOm) (RjTrn) cg(<f>)£- + 1 d(f> dOm drm d<j) d0m drm + 1 Td X ; / / fRm(rm) 2* J J cg(<f>)£ + 1 Tmoi - X ' m Tmol X X U(<f>) feJOm) fRm(rm) { Tmax w fl / / / re —x —x cg{4)$- + l d<f>drm d(j) d6m drm + x r 2 - r 2 ' d ' max x T^ J r2 - r2 tan - l y/cg((j)) r2 — tan - l Vc^(^)r2 ^ V . (6.7) Chapter 6. Directional Transmitter Antennas 82 Note that qi(r, 0) depends on 0 since re = J^ and Ae depends on 0. If omnidirectional antennas are employed, i.e., g((f>) = 1, (6.7) is reduced to (4.45). 6.3 Throughput and Normalized Average Progress Similar to the case of omnidirectional antennas in Section 4.3.2, we can express the throughput as Tmax 2 QQ S = pt Pr (Ef) Pr (ESiY) J J fR,e(r, 0) £ Pi <fc(r, 0) d0 dr , (6.8) o - f «'=° where Pr (Ef) is the probability of X finding a neighboring node in its forward direction as given by (3.1), Pr (Esy) is the probability of Y not transmitting as given by (4.1), and Pi is the probability of i interfering nodes in the non-excluded region as given by (4.48). The normalized average progress can be obtained from (6.8) by multiplying the integrand by y/\ rcos0, resulting in Tmax 2 QQ Zn = pt y/\ Pr (Ef) Pr (ESjY) J J fR,e(r, e) rcosOj^ Pi qi(r, 0) dd dr. (6.9) o _ f *=° Since <#(r, 0) = [q\(r, 0)]% in (6.7), the summation in both (6.8) and (6.9) can be simplified as t'=0 = exp{-[ l - qi(r,0)]Nt} (6.10) where Nt, given by (4.47), is the average number of interfering nodes in the non-excluded region. In a system using directional antennas, the transmission potential vv for MTP is not the same as for the omnidirectional antennas case. In order to simplify vp for the Chapter 6. Directional Transmitter Antennas 83 case of directional antennas, we assume that the amount of interference at Y is reduced by a factor of ^f, where Bw is the half-power beamwidth, compared to the case of omnidirectional antennas. Hence, we can obtain vv by multiplying K in (3.39) and (3.40) for the omnidirectional case by ^~. 6.4 Analytic and Simulation Results In this section, the terms MFR, NFP, MAD, ARR, and MTP are used to refer to the transmission strategies based on the corresponding routing schemes. For the non-fading case, only simulation results are provided. For the Rayleigh fading case, simulation results as well as analytic results (simulation only for MTP) are provided for comparison. The simulation results obtained are based on the model described in Section 2.6. The value of rd is assumed to be 10rmax in the simulation because there is little difference in the results by increasing the value of rj beyond 10 rmax. As in Sections 4.4.2, 4.4.3, and 5.4, the value of c = 4 is used [4], [14], An optimal value of pt (obtained by searching in pt steps of 0.01) is chosen which maximizes the normalized average progress Zn for a given routing scheme and a given connectivity N. It might be noted that the optimal pt value generally decreases with increasing N. Figure 6.2 shows the simulation results of Zn as a function of TV for MFR in a non-fading channel. The results are for the red function antenna pattern with different values of beamwidth Bw- In Figure 6.2, Zn for the omnidirectional antennas case, labelled as "Omni", is also provided for comparison. Figure 6.3 shows the corresponding results for MFR with the sine function antenna pattern and different values of Bw- The Zn values for NFP, MAD, ARR, and MTP with the red function antenna pattern are shown in Figures 6.4, 6.6, 6.8, and 6.10, respectively. The corresponding results with the sine function antenna pattern are shown in Figures 6.5, 6.7, 6.9, and 6.11. For the Rayleigh fading case, the Chapter 6. Directional Transmitter Antennas 84 simulation results of Zn for the five transmission strategies with the two antenna patterns are shown in Figures 6.12 to 6.21. The analytic results for MFR, NFP, MAD, and ARR are also provided for comparison. Similar to the case of omnidirectional antenna, the performances of all five transmission strategies for the directional antenna cases decrease by about 10% in the presence of Rayleigh fading. For all five transmission strategies, Zn can be improved substantially by employing directional antennas with the rect function antenna pattern. The ratio of the maximum value of Zn for the Bw — § case to that of the omnidirectional antenna case is about 5.8, 2.7, 5.6, 3.7, and 5.4 for MFR, NFP, MAD, ARR, and MTP, respectively. MFR, MAD, and MTP show greater improvement on Zn than NFP and ARR. If the interference is small, a strong received signal power is not needed for capturing the packet. In this case, a receiving node with a larger progress (corresponding to a larger transmitter-to-receiver distance) is preferred. Thus MFR and MAD would be preferred over NFP and ARR. If the interference is large, NFP and ARR perform better than MFR and MAD. MTP has the best performance among the five transmission strategies because it can adapt to different interference levels. For the case of the sine function antenna pattern, The ratio of the maximum value of Zn for the Bw = f case to that of the omnidirectional antenna case is about 3.8, 2.5, 3.9, 3.3, and 3.8 for MFR, NFP, MAD, ARR, and MTP, respectively. The performance improvement for the five transmission strategies, especially for MFR, MAD, and MTP, is reduced. The effect of the side lobes of the sine function antenna pattern has a larger impact on MFR and MAD because the received signal power is smaller for MFR and MAD compared to that for NFP and ARR. In [25] and [26], the performance of MFR with the rect function antenna pattern was studied. In this section, we had provided the results for all five transmission strategies with Chapter 6. Directional Transmitter Antennas 85 the rect function and sine function antenna patterns. The performances of the transmission strategies were also examined with and without fading, and the interference model used is more realistic than those used in [25] and [26]. Our results as well as those in [25] and [26] show that a smaller value of Bw generally leads to a better performance. However, the sine function antenna pattern results in a substantial performance degradation relative to the rect function antenna pattern for MFR, MAD, and MTP. Chapter 6. Directional Transmitter Antennas 86 0.2 N* o £ g o.i i T3 V 1 0.05 I ----" ----A 9 o A O . D X o A O a X O A O | D X o A O D X o A O a D D x x x o o o A A A o O o 1 1 1 a X o A O D X o A O U . a X o A O - • D X o A O I l 1 a i X o A O <) 10 15 Connectivity, N 20 25 Figure 6.2 Normalized average progress for MFR in a non-fading channel with red pattern and different values of Bw- Legend is the same as in Figure 6.5. BO O 2 q N 0.2 0.15 0.1 I 0.05 o D • X X X x x D x X Q O O O O O O O O A A A A A A A O O O o ° o O o o A o D A o J . A O - J I I i _ 10 15 Connectivity, N A O A O I I I 20 25 Figure 6.3 Normalized average progress for MFR in a non-fading channel with sine pattern and different values of % . Legend is the same as in Figure 6.5. Chapter 6. Directional Transmitter Antennas 87 0.2 N X/i 8 0.15 oo o u <D "8 1 0.05 o S5 0.1 9 D D 5 9 5 5 • x x x ^ O O O O O O O A A A A A A A A o o o o o o o o o D x o A O D x o A O • x o A O X 10 15 Connectivity, N a X O A O 20 D x o A O 25 Figure 6.4 Nonnalized average progress for NFP in a non-fading channel with red pattern and different values of Bw- Legend is the same as in Figure 6.5. c N DO O H OH <D 60 2 ID <D 0.2 0.15 0.1 52 0.05 i-i o Simulation Omni Bw-% Bw — nP-Bw = ii/4 Bw = Jt/8 o A O x D 9? • D D a • f o o o o o o o o A A A A A A A A o o o o o o o o o • x A O a X O A O D x o A O D x o A O t i l l 10 15 Connectivity, N 20 a X O A O 1 1 1 1 1 I • i i i I | • • i 25 Figure 6.5 Normalized average progress for NFP in a non-fading channel with sine pattern and different values of Bw-Chapter 6. Directional Transmitter Antennas 88 0.2 | 0 - 1 5 O g 0.1 "8 .N "I 0.05 O ------A 1 ° 1 L_ D X O A A O O I l a X o A O 1 • X o A O — 1 _ D a o D x x x * X o o o o A A A A 0 O o o _1 L _1 J J D X o A O 1 1 D X o A O • D X o A O l 1 D X o A O 1 l 1 D 11 X o A O <> i _ i — i _ _ J . 10 15 Connectivity, N 20 25 Figure 6.6 Normalized average progress for MAD in a non-fading channel with red pattern and different values of B\y. Legend is the same as in Figure 6.5. 0.2 e o.i5 o 2 i. •8 N 0.1 g 0.05 I X X X X D g o o o o o o o o ^ A A A A A A A A o 0 0 o° o o o o i i i -L A O A O A O A O -1 I L_l_ 10 15 Connectivity, N 20 A O 25 Figure 6.7 Normalized average progress for MAD in a non-fading channel with stnc pattern and different values of Bw. Legend is the same as in Figure 6.5. Chapter 6. Directional Transmitter Antennas 89 0.2 N c/f Vi £ 0.15 o 6 0.1 .EH 1 0.05 I n • D D u n x x x • x x * D * o o o o o $ A A A A A A A A A o o o o o o o o o D x A O • x A O • x A O D x A O D x A O ! • • • • • • • 10 15 Connectivity, N 20 25 Figure 6.8 Normalized average progress for ARR in a non-fading channel with red pattern and different values of Bw- Legend is the same as in Figure 6.5. 0.2 N to I 0 - 1 5 g 60 0 i "8 . E H 13 a c o 55 0.1 0.05 5 n X X x X X X a < > o o o o o o o ^ A ^ A A A A A A o o o o o o o o o A o A o A o A O A O - l i— 10 15 Connectivity, N 20 25 Figure 6.9 Normalized average progress for ARR in a non-fading channel with sine pattern and different values of Bw. Legend is the same as in Figure 6.5. Chapter 6. Directional Transmitter Antennas 90 0.2 B 0.15 oo o & g 0.1 > < .a S 0.05 i ---_ -A i° i 1 9 o A O t D X o A O D X o A O | D X o A O D X o A O • X o A O D X o A O I D X o A O J. D X o A O i . D X o A O • D X o A O D X o A O , . 1 • 11 X o <> A o o 1 1 1 1 10 15 Connectivity, N 20 25 Figure 6.10 Normalized average progress for MTP in a non-fading channel with red pattern and different values of Bw- Legend is the same as in Figure 6.5. g bo o s D .a 0.2 0.15 0.1 S 0.05 -° x x x * * * x X X • * * 0 0 0 0 < > < > 0 ^ ^ ^ . A A A A A A A A A A A o o o o o o o o o o o o D A o A O I 10 15 Connectivity, N 20 25 Figure 6.11 Normalized average progress for MTP in a non-fading channel with sine pattern and different values of Bw • Legend is the same as in Figure 6.5. Chapter 6. Directional Transmitter Antennas 91 0.2 10 15 Connectivity, N 25 Figure 6.12 Normalized average progress for MFR in a Rayleigh fading channel with red pattern and different values of Bw- Legend is the same as in Figure 6.15. 0.2 g 0.15 o £ o 00 s T3 N 0.1 £2 0.05 & n^ a-n ° — Q— a— 0 . a - B -- - * TJ--X--X--M---X. X <^? ^ "O " ^ ^ -o-o -<> x .x -o~~o-—o *—--o -A—. -e— -A -e 10 15 Connectivity, N 20 25 Figure 6.13 Normalized average progress for MFR in a Rayleigh fading channel with sine pattern and different values of Bw- Legend is the same as in Figure 6.15. Chapter 6. Directional Transmitter Antennas 92 0.2 N g 0.15 § 0.1 .a 1 S, 0.05 •JB-S-s-5-? - S--? Q _ X JEL x y ^ * y ^ X "5 5i - - - - - —- - •» — ' 10 15 Connectivity, N Figure 6.14 Normalized average progress for NFP in a Rayleigh fading channel with red pattern and different values of Bw- Legend is the same as in Figure 6.15. 0.2 c N I 0 ' 1 5 0.1 -o 2 O I | 0.05 I Analytic Onuii r>w = ft Bw = n/2 Bw = n/4 Bw = nl% Simulation R Omni o | B^=n A B Bw = n/2 O 1 Bw = 7c/4 x 1 Bw = n/8 • 1 __a -a- B—a-e — Q B — Q B--x x • * • - -o — o — o -B - ° - X 10 15 Connectivity, N Figure 6.15 Normalized average progress for NFP in a Rayleigh fading channel with sine pattern and different values of Bw Chapter 6. Directional Transmitter Antennas 93 0.2 • 0" * - - • CK D-x_x__*_ _ _ . _ - _ . : *___ _ x ^ > . . f i — A " A " ; A - A - A - A - A *> 0. •O <> A. O O O--A--e-•-A-i i i 10 15 Connectivity, N 20 25 Figure 6.16 Normalized average progress for MAD in a Rayleigh fading channel with red pattern and different values of Bw. Legend is the same as in Figure 6.15. 0.2 N &°- 1 5 0.1 1 S 0.05 I -D-D -B D -B B S° ^a _ - - X - - * - - X - - X . *• X-. ' —IE X «• 10 15 Connectivity, N Figure 6.17 Normalized average progress for MAD in a Rayleigh fading channel with sine pattern and different values of Bw. Legend is the same as in Figure 6.15. Chapter 6. Directional Transmitter Antennas 94 0.2 N so g 0.15 o £ DO 2 ID "8 0.1 g 0.05 / a ^d a-cj-a — 0 o- a cr D' . . * * x . . X 1 ; -O. .<> ^ -<> -a--A--A--A—A—A—A O ' O O O O O O O — -A--e- -e-•A--e-10 15 Connectivity, N 20 25 Figure 6.18 Normalized average progress for ARR in a Rayleigh fading channel with red pattern and different values of Bw- Legend is the same as in Figure 6.15. 8 to o 00 e 1 1 o 0.2 0.15 0.1 0.05 --S-fi-cfQ ° D D D D D x^J - - 5 r -5T-x--X « x x x X • •£-$-<?-<?-<? ~sr<?-o—~o—-o—-o • 1> <> Connectivity, N Figure 6.19 Normalized average progress for ARR in a Rayleigh fading channel with sine pattern and different values of Bw- Legend is the same as in Figure 6.15. Chapter 6. Directional Transmitter Antennas 95 0.2 S 0.15 6 o.i i "8 1 0.05 I ---5 - o A •go a D x ; * A A O O • X o A O | D D X X o o A A O O • X o A O i D D x x o o A A O O 1 1 • X o A O 1 l • X o A O 1 D X o A O • • • X o A O 1 l 1 D 1 X o <> A O <) _ i — i _ i . . . j 10 15 Connectivity, N 20 25 Figure 6.20 Normalized average progress for MTP in a Rayleigh fading channel with red pattern and different values of Bw. Legend is the same as in Figure 6.5. N O <L> W > S3 > T3 0.2 0.15 0.1 | 0.05 o D n • X X X X a n o o o ^ o o o < > A A A A A A A A Q O O O O O O O O A o A o A O D A O _i l l i_ A O J I 1 L. 10 15 Connectivity, N 20 25 Figure 6.21 Normalized average progress for MTP in a Rayleigh fading channel with sine pattern and different values of Bw- Legend is the same as in Figure 6.5. Chapter 7 Conclusions The one-hop throughput S and the average normalized progress Zn of the five transmission strategies (based on two previously proposed routing schemes, MFR and NFP, and three new routing schemes, MAD, ARR, and MTP) in a multihop PRN, as described in Section 2.6, with different interference models were studied. The study in this thesis can apply to a multihop PRN with randomly distributed nodes which are mobile or stationary. For the three interference models considered in this thesis, the Zn of the five transmission strategies initially increases rapidly with the connectivity N. As N increases further, the performance of MFR and MAD degrades due to the increased interference from other transmitting nodes. However, the performance of NFP, ARR, and MTP does not degrade for larger values of N. The maximum value of Zn for the five transmission strategies (MTP with interference model 1.2 was not studied) occurs at the connectivity of 6 to 11, 4 to 5, and 3 to 4 for interference models 1.2, 2.1, and 2.2, respectively. In this thesis, a refinement of the analysis of MFR and NFP in [22] (carried out assuming interference model 1.2) was presented and shown to yield more accurate results. The difference between the analytic and simulation results for MFR, NFP, MAD, and ARR with the three interference models is less than 2% in most cases. Simulation results for MTP are also provided for comparison. Results show that ARR has a better performance than MFR, NFP, and MAD for almost all values of JV. They also show that MTP performs better than ARR by about 10%. It was found, using interference model 2.2, that all five transmission strategies perform worse in the presence of Rayleigh fading. This is in contrast 96 Chapter 7. Conclusions 97 to contention-limited single-hop systems in which Rayleigh fading generally does not result in poorer performance. The performance improvement of the five transmission strategies in a multiple receiver antenna (diversity) system in a Rayleigh fading environment was studied. In the proposed system, every node in the network has iVr receiver antennas. It was determined from simulation that a scheme in which nodes decode the antenna with the largest received power yields good performance. Results show that Zn of the five transmission strategies can be improved by about 25% if Nr is increased from 1 to 2. An approximate analysis was provided, and the results were found to agree well with simulation results for Nr < 2. The difference becomes larger as Nr increases because a simplification used in the analysis becomes less valid. For any given value of Nr, ARR has a larger Zn than MFR, NFP, and MAD for almost all values of N, and MTP again performs better than ARR by about 10%. The performance improvement brought about by using directional transmitter antennas for the five transmission strategies was also studied. In all five cases, Zn can be improved substantially by employing directional antennas with a rect function antenna pattern. The ratio of the maximum value of Zn for a beamwidth Bw = f case to that of the omnidirectional antenna case is about 5.8, 2.7, 5.6, 3.7, and 5.4 for MFR, NFP, MAD, ARR, and MTP, respectively. MFR, MAD, and MTP show greater improvement than NFP and ARR. This is because interference is the primary factor limiting the performance of MFR and MAD, and the interference is reduced as the beamwidth decreases. The performance improvement for the five transmission strategies, especially for MFR, MAD, and MTP, is reduced in the case of a sine function antenna pattern. The side lobes of the sine function antenna pattern have a larger impact on MFR, MAD, and MTP because the received signal power at the receiving node is smaller for them compared to that for NFP and ARR. Chapter 7. Conclusions 98 Among the topics which could be further investigated are: • To study multihop PRNs using other random access techniques such as CSMA. To find a routing scheme which yields the optimal normalized average progress under various interference models. • To analyze the end-to-end throughput of the transmission strategies. • To find a transmission strategy which yields the optimal end-to-end throughput under the more realistic interference models such as 2.1 and 2.2. Bibliography [1] R. Kahn, S. Gronemeyer, J. Burchfiel and R. Kunzelman, "Advances in Packet Radio Technology," IEEE Proceedings, vol. 66, pp. 1468-1496, Nov. 1978. [2] I. Gitman, R. Van Slyke and H. Frank, "Routing in Packet Switching Broadcast Radio Networks," IEEE Transactions on Communications, vol. COM-24, pp. 926-930, Aug. 1976. [3] N. Abramson, "The ALOHA System: Another Alternative for Computer Communications," Proceedings of the AFIPS Fall Joint Computer Conference, Montvale, NJ, USA., vol. 37, pp. 281-285, 1970. [4] L. Roberts, "ALOHA Packet System with and without Slots and Capture," Computer Communications Review, pp. 28—42, Apr. 1975. [5] L. Kleinrock and F. Tobagi, "Packet Switching in Radio Channels:Part I-Carrier Sense Multiple-Access Modes and Their Throughput-Delay Characteristics," IEEE Transactions on Communications, vol. COM-23, pp. 1400-1416, Dec. 1975. [6] L. Kleinrock and S. Lam, "Packet Switching in a Multiaccess Broadcast Channel: Performance Evaluation," IEEE Transactions on Communications, vol. COM-23, pp. 410-423, Apr. 1975. [7] L. Fratta and D. Sant, "Some Models of Packet Radio Networks with Capture," Proceedings of International Conference on Computer Communications, Atlanta, Georgia, U.SA, pp. 155-161, Oct. 1980. [8] C. Namislo, "Analysis of Mobile Radio Slotted ALOHA Networks," IEEE Transactions on Vehicular Technology, vol. VT-33, pp. 199-204, Aug. 1984. [9] D. Goodman and A. Saleh, "The Near/Far Effect in Local ALOHA Radio Communications," IEEE Transactions on Vehicular Technology, vol. VT-36, pp. 19-27, Feb. 1987. [10] C. Lau and C. Leung, "Capture Models for Mobile Packet Radio Networks," IEEE Transactions on Communications, vol. 40, pp. 917-925, May 1992. [11] R. Clarke, "A Statistical Theory of Mobile-Radio Reception," The Bell System Technical Journal, vol. 47, pp. 957-1000, July-Aug. 1968. 99 Bibliography 100 [12] W. Jakes, Microwave Mobile Communications. New York: J. Wiley, 1974. [13] F. Kuperus and J. Arnbak, "Packet Radio in a Rayleigh Channel," Electronics Letters, vol. 18, pp. 506-507, June 1982. [14] J. Arnbak and W. Blitterswijk, "Capacity of Slotted ALOHA in Rayleigh-Fading Channels," IEEE Journal on Selected Areas in Communications, vol. SAC-5, pp. 261-269, Feb. 1987. [15] I. Habbab, M. Kavehrad and C.-E. Sundberg, "ALOHA with Capture Over Slow and Fast Fading Radio Channels with Coding and Diversity," IEEE Journal on Selected Areas in Communications, vol. SAC-7, pp. 79-88, Jan. 1989. [16] E. Zainal and R. Garcia, "The Effects of Rayleigh Fading on Capture Phenomenon in ALOHA Channels," Proceedings of IEEE INFOCOM, San Francisco, California, U.SA., pp. 888-893, Mar. 1987. [17] T. Ha, "The Effect of Fading in Mobile ALOHA Radio Communications," Proceedings of IEEE Vehicular Technology Conference, San Francisco, California, U.SA., pp. 19-21, May 1989. [18] A. Sheikh, Y. Yao and X. Wu, "The Impact of Fast Fading on ALOHA System in ' the Mobile Environment," Proceedings of IEEE Vehicular Technology Conference, San Francisco, California, U.SA., pp. 804-808, May 1989. [19] L. Kleinrock and J. Silvester, "Optimum Transmission Radii for Packet Radio Networks or Why Six is a Magic Number," Proceedings of IEEE National Telecommunications Conference, Birmingham, Alabama, U.SA., pp. 4.3.1.-4.3.5, Dec. 1978. [20] H. Takagi and L. Kleinrock, "Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals," IEEE Transactions on Communications, vol. COM-32, pp. 246-257, Mar. 1984. [21] J. Westcott and J. Jubin, "A Distributed Routing Design for a Broadcast Environment," Proceedings of IEEE MILCOM, Boston, Massachusetts, U.SA., pp. 10.4.1-10.4.5, Oct. 1982. [22] T. Hou and V. Li, "Transmission Range Control in Multihop Packet Radio Networks," IEEE Transactions on Communications, vol. COM-34, pp. 38^44, Jan. 1986. [23] V. Wong and C. Leung, "Transmission Strategies in Multihop Mobile Packet Radio Networks," Canadian Conference on Electrical and Computer Engineering, Vancouver, Bibliography 101 B.C., Canada, pp. 1004-1008, Sept. 1993. [24] V. Wong and C. Leung, "Effect of Rayleigh Fading in a Multihop Mobile Packet Radio Network with Capture." IEEE Transactions on Vehicular Technology, to appear. [25] C. Chang and J. Chang, "Optimal Design Parameters in a Multihop Packet Radio Network Using Random Access Techniques," Proceedings of IEEE GLOBECOM, Atlanta, Georgia, USA., pp. 493-497, Nov. 1984. [26] J. Zander, "Slotted ALOHA Multihop Packet Radio Networks with Directional Antennas," Electronics Letters, vol. 26, pp. 2098-2100, Dec. 1990. [27] K. Bullington, "Radio Propagation for Vehicular Communications," IEEE Transactions on Vehicular Technology, vol. VT-26, pp. 295-308, Nov. 1977. [28] N. Abramson, "The Throughput of Packet Broadcasting Channels," IEEE Transactions on Communications, vol. COM-25, pp. 117-128, Jan. 1977. [29] J.-P. Linnartz and R. Prasad, "Near-Far Effect on Slotted ALOHA Channel with Shadowing and Capture," Proceedings of the 39th IEEE Vehicular Technology Conferenc e, San Francisco, California, USA., pp. 809-813, Apr. 1989. [30] I. Cidon, H. Kodesh and M. Sidi, "Erasure, Capture, and Random Power Level Selection in Multiple-Access Systems," IEEE Transactions on Communications, vol. COM-36, pp. 263-271, Mar. 1988. [31] Y. Onozato, J. Liu and S. Noguchi, "Stability of a Slotted ALOHA System with Capture Effect," IEEE Transactions on Vehicular Technology, vol. VT-38, pp. 31-38, Feb. 1989. [32] D. Lyons and P. Papantoni-Kazakos, "A Window Random Access Algorithm for Environments with Capture," IEEE Transactions on Communications, vol. COM-37, pp. 766-770, July 1989. [33] A. Shwartz and M. Sidi, "Erasure, Capture, and Noise Errors in Controlled Multiple-Access Networks," IEEE Transactions on Communications, vol. COM-37, pp. 1228— 1231, Nov. 1989. [34] C. Lau, MultiAntenna and Receiver Slotted ALOHA Packet Radio Systems with Capture. PhD thesis, Dept. Elec. Eng., UBC, Vancouver, B.C., Canada, May 1990. [35] J. Metzner, "On Improving Utilization in ALOHA Networks," IEEE Transactions on Communications, vol. COM-24, pp. 447-448, Apr. 1976. Bibliography 102 [36] C. Lau and C. Leung, "Performance of a Power Group Division Scheme for ALOHA System in a Finite Capture Environment," IEE Electronics Letters, vol. 24, pp. 915-916, July 1988. [37] E. Sousa and J. Silvester, "Optimum Transmission Ranges in a Direct-Sequence Spread-Spectrum Multihop Packet Radio Network," IEEE Journal on Selected Areas in Communications, vol. 8, pp. 762-771, June 1990. [38] W. Stutzman and G. Thiele, Antenna Theory Design. New York: J. Wiley, 1981. [39] M. Barnard, "The Global Positioning System," IEE Review, vol. 38, pp. 99-102, Mar. 1992. [40] J. Yee and F. Shiao, "On Calculating High Throughputs in Multi-Hop Slotted ALOHA Packet Radio Networks," Proceedings of IEEE INFOCOM, San Francisco, California, USA., pp. 382-388, June 1990. [41] F. Shiao and J. Yee, "On Determining the Transmission Range for Multi-Hop Slotted ALOHA Packet Radio Networks," Proceedings of IEEE MILCOM, Monterey, California, U.SA., pp. 35.5.1-35.5.5, Oct. 1990. [42] J. Yee and F. Shiao, "An Algorithm to Find Global Optimal Routing Assignments for a Class of PRNs," Proceedings of IEEE ICC, Denver, Colorado, U.SA., pp. 50.1.1-50.1.5, June 1991. [43] B. Hajek, "Adaptive Transmission Strategies and Routing in Mobile Radio Networks," Proceedings of Conference on Information Sciences and Systems, Baltimore, Maryland, USA., pp. 373-378, Mar. 1983. [44] N. Shacham and P. King, "The Performance of Multichannel, Multihop Packet Radio Networks," Proceedings of IEEE ICC, Toronto, Ontario, Canada, pp. 873-877, June 1986. [45] R. Nelson and L. Kleinrock, "The Spatial Capacity of a Slotted ALOHA Multihop Packet Radio Network with Capture," IEEE Transactions on Communications, vol. COM-32, pp. 684-694, June 1984. [46] T. Hou and V. Li, "Performance Analysis of Multihop Packet Radio Networks with Capture," Proceedings of IEEE ICC, Chicago, Illinois, U.SA., pp. 1311-1317, June 1985. Bibliography 103 [47] V. Wong and C. Leung, "Effect of Fading in a Multihop Packet Radio Network with Capture," IEEE TENCON '94 Conference, Singapore, pp. 702-707, Aug. 1994. [48] M. Abramowitz and I. Stegun, Handbook of Mathematical Functions. New York: Dover Publications, Inc., 1970. [49] C. van der Plas and J.-P. Linnartz, "Stability of Mobile Slotted ALOHA Network with Rayleigh Fading, Shadowing, and Near-Far Effect," IEEE Transactions on Vehicular Technology, vol. 39, pp. 359-366, Nov. 1990. [50] V. Wong and C. Leung, "Performance Improvement in a Multihop Packet Radio Network Using Multiple Antennas," IEEE GLOBECOM '94 Conference, San Francisco, California, U.SA., pp. 1701-1706, Nov. 1994. [51] R. Larsen and M. Marx, An Introduction to Mathematical Statistics and Its Applications. New Jersey: Prentice-Hall, 1981. [52] W. Lee, "Studies of Base-station Antenna Height Effects on Mobile Radio," IEEE Transactions on Vehicular Technology, vol. VT-29, pp. 252-260, May 1980. [53] F. Tobagi and L. Kleinrock, "Packet Switching in Radio Channels:Part U-The Hidden Terminal Problem in Carrier Sense Multiple-Access and the Busy-Tone Solution," IEEE Transactions on Communications, vol. COM-23, pp. 1417-1433, Dec. 1975. [54] R. Metcalfe and D. Boggs, "Ethernet: Distributed Packet Switching for Local Computer Networks," Communications of the ACM, vol. 19, pp. 395-404, July 1976. [55] J. Capetanakis, "Tree Algorithms for Packet Broadcast Channels," IEEE Transactions on Information Theory, vol. IT-25, pp. 505-515, Sept. 1979. [56] L. Kleinrock and S. Lam, "Packet Switching in a Multiaccess Broadcast Channel: Performance Evaluation," IEEE Transactions on Communications, vol. COM-23, pp. 410-423, Apr. 1975. [57] L. Kleinrock and F. Tobagi, "Packet Switching in Radio Channels:Part I-Carrier Sense Multiple-Access Modes and Their Throughput-Delay Characteristics," IEEE Transactions on Communications, vol. COM-23, pp. 1400-1416, Dec. 1975. [58] F. Tobagi, "Modeling and Performance Analysis of Multihop Packet Radio Networks," IEEE Proceedings, vol. 75, pp. 135-155, Jan. 1987. Bibliography 104 [59] L. Kleinrock and J. Silvester, "Spatial Reuse in Multihop Packet Radio Networks," IEEE Proceedings, vol. 75, pp. 156-167, Jan. 1987. [60] M. Abramowitz and I. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. New York: Dover Publications, Inc., 1970. [61] I. Gradshteyn and I. Ryzhik, Table of Integrals, Series, and Products. New York: Academic Press, 1980. [62] L. Couch II, Digital and Analog Communication. New York: MacMillian, 2nd ed., 1987. [63] A. Tanenbaum, Computer Networks. New Jersey: Prentice Hall, 2nd ed., 1989. [64] J.-P. Linnartz, R. Hekmat and R.-J. Venema, "Near-Far Effects in Land Mobile Random Access Networks with Narrow-Band Rayleigh Fading Channels," IEEE Transactions on Vehicular Technology, vol. 41, pp. 77-90, Feb. 1992. [65] J.-P. Linnartz, "Slotted ALOHA Land-Mobile Radio networks with Site Diversity," IEE Proceedings I, vol. 139, pp. 58-70, Feb. 1992. [66] W. Feller, An Introduction to Probability Theory and Its Applications, vol. 1. New York: J. Wiley, 3rd ed., 1968. Appendix A Partial Excluded Region If node X transmits to its receiving node Y, there is a region, referred to as an excluded region, in which no node can be located. The area of the excluded region depends on the distance r between X and Y, and the angle 8 between XY and the destination direction of X. We will refer to the part of the excluded region which is within the circle of radius rc (> r) centered at 7 as a partial excluded region. The values of rc for interference models 1.2, 2.1, and 2.2 are rmax, c^r, and oo, respectively. In Chapters 4, 5, and 6, the area Ae(rc) of the partial excluded region is needed in the performance analysis. In this appendix, we determine Ae(rc) for the MFR, NFP, MAD, and ARR routing schemes. Since the area of the partial excluded region is the same for ±0, we only consider 0 in the range of [0, | ]. A.1 MFR Figures A. 1(a) and (b) illustrate the partial excluded region for MFR. Let the distance between Wj and Y and the distance between W2 and Y be denoted by d\ and d<i, respectively. We have d\ = rmax sin a — r sin0, di = rmax sine* + r sin0, (A.l) where a = cos"1 (IS°s£). y 'max J Case 1: d2 < rc. In this case, the entire excluded region is within the distance rc from Y and Ae{rc) = Ae = r2maxa - - r2max sin 2a. (A.2) 105 Appendix A. Partial Excluded Region 106 Case 2: di > rc and d\ < rc. This case is illustrated in Figure A. 1(a). Denote the distance between Wj and W3 by h where We have h = 2 rv sin a + 9 8 = cos 1 i = s + e V + r2 _ ^ 2 r r c 7T " 2 ' (A.3) (A.4) and we can express Ae(rc) as Ae(rc) = Ai + A2 + A3, (A.5) where Ai A2 A3 - r 2 £ 2 c ? ' -d\ rc sin£, sin - 1 2 TV 2r r '1 -^2 4 r 2 ' ' mar (A.6) Case 3: d\ > rc. If r + rc > rmoa;, we have the case illustrated in Figure A. 1(b). Let the distance between W3 and W4 be denoted by / where / = 2 rc sin S. (A.7) Appendix A. Partial Excluded Region 107 The areas A\, Ai, and A3 are M = rli ) A2 = \r2c{28 - n - 0 , A* = r2 **» ' max + , : _ - i / ' "\ * \^rmax / ^rmax - 1 rc COS (5 - TT) , p 4r2 7 1' max (A.8) where 5 and £ are given in (A.4), and Ae(rc) = A\ + A2 + A$. (A.9) If r + rc < rmax, we have 7T Mrc) = K - (A.10) A.2 NFP Figures A.2(a) and (b) illustrate the partial excluded region for NFP. Let the distance between Wj and Y and the distance between W2 and Y be denoted by d\ and d2, respectively. We have <h = 2 r sin ( ! _ - ) , rf2 = 2 r sin ( - + -(A.11) Case 1: d2 < rc. In this case, the excluded region is a semi circle with radius r and the area of the region is Ae{rc) = Ae = -nr2. (A.12) Appendix A. Partial Excluded Region 108 Case 2: d\ < rc and d% > rc. This case is illustrated in Figure A.2(a) and we have 8 = a = 2 sii 7r — a £ = | - 0 - sin - 1 ( - cos0 ) . (A.13) A2 = l y s i n e , A4 = - r 2 a - -rrc c o s - , (A.14) and Ae(rc) = Ai + A2 + Az + A4 . (A.15) Case 3: d\ > rc. This case is illustrated in Figure A.2(b) and we have Al = r\8 - \r2c{( + i? _ sin (£ + t/>) ] , A% = r a — rrc cos —, (A.16) where a, 8, and £ are given in (A.13), and rj, = | + 0 - sin"1 f - cosflj . (A. 17) The area of the partial excluded region is Ae(rc) = Ai + A2. (A.18) Appendix A. Partial Excluded Region 109 A.3 M A D Figures A.3(a) and (b) illustrate the partial excluded region for MAD. Let the distance between Y and W be denoted by d where d = V^2 + rma* ~ 2 rrmax cos 20. (A.19) Case 1: d < rc. In this case, the entire excluded region is within the distance rc from Y and Ae(rc) = Ae = r2max9. (A.20) Case 2: d > rc and r + rc < rmax. This case is illustrated in Figure A.3 (a). We have 8 = 7T - 2 0 - sin (— sin 20 J (A.21) and the area of the partial excluded region is Mrc) = \ r\ (x - 8) + i r rc sin 5. (A.22) Case 3: d > rc and r + rc > rmaa;. This case is illustrated in Figure A.3(b). We have a = sin (-^— s in20) , \rmax J £ = cos"1 ( r + lc_ 7 Tmax ] , (A-23) 2rrc and A ^ I r w s i n , , ^2 = \rl(t-8), Appendix A. Partial Excluded Region 110 The area of the partial excluded region is given by Ae(rc) = Ax + A2 + A3. (A.25) A.4 ARR Figure A.4(a) and (b) illustrate the partial excluded region for ARR. Circle C\ has radius rmax and is centered at X. Circle C2 has radius rc and is centered at Y. Circle C3 has radius I and is centered at ( | , 0) where t = -^^. The distance between Y and W is d = yjr2 + r2max - 2 r rmax cos (6 + a) (A.26) where a = c o s - i (l22£) . (A.27) If t < rc, * a Ae(rc) = Ae = - t l . (A.28) 4 If t > rc, * ( - . ) = r? cos- ( * ) + I [ s i n - ( S ) - * / T " ( f ) (A.29) Case 2: * > rm0z and d < rc. If 6 + or < f and rc < f, as illustrated in Figure A.4(a), the area of the partial excluded region is Ae(rc) = \? + (rL, " f ) « - ~ ^ )/* = ^» Appendix A. Partial Excluded Region 111 where 8 = 2 c o s - 1 (*f). If 9 + a > § or rc > t, we have from (3.21) that Ae(rc) = - 1 ' -!• ( r ( 2 * \ rmax Lo [rmax - - J a - — y/t* (A.31) Case 3: t > rmax and d > rc. Let the three intersection points of the circles C\, Ci and C% be denoted by Jj, 32, and J3 as illustrated in Figure A.4(b). Let the distances between these intersection points be 51, 52, and 53. We can write Ae(rc) = A\ + A2 + A3 + A4 (A.32) where Ax = A2 = vi sin - 1 51 2rv s\ 2rr, Ar2 ^ ' mar A3 A4 • - 1 / 5 2 _£2_ 2rc 1 - 4r? ^(f)-f)/ > - * \ / 5 (5 - Si) (5 - 52) (5 - 53) (A.33) In (A.33), 5 = \ (51 + 52 -1- 53). Let (x,-, y t) be the rectangular co-ordinates for the intersection point / ; where i = 1,2,3. The terms s\, 52 and S3 can be calculated as follows. S2 S3 = y (xi - x2)2 + (yi - j ^ ) 2 , = V (x2 - £3)2 + {V2 - yz)2, = y(a;3 - *i) 2 + (2/3 - yi ) 2 . (A.34) Appendix A. Partial Excluded Region 112 The equations for C\, Ci and C% are 2 _, 2 2 x "r V — rmax ) (x — r cos 9) + (y —r sin 9) = r 2 , 2 t2 *• 7 ) +2 / 2 = J- (A-35) (• -ij The co-ordinates (a;,-, t/;) for £ = 1,2,3 are determined as follows. For / ; , we have xi = r2 ' max t ' 2/1 = rmaxJl - ~%. (A.36) For /2, we have r s - 2 ?/2 sin # X2 ~ 2cos0 1 / y2 = - f rs sin 9 - cosByjArl^ - r2 j , (A.37) where rs = 7(r2na2. - r2 + r 2 ) . For 7j, we have x3 = —°2 — y a\ ~~ 4 ai 03 2 01 (t - 2 r cosfl)s3 - r2c + r2 2/3 = 5 5 , (A.38) 2r cosy where ai = t2 - Art cos0 + 4 r 2 , a2 = 2 ( r 2 - r 2 ) ( t - 2r cos0) - 4 r 2 i s i n 2 0 , a3 = ( r 2 - r 2 ) 2 . (A.39) Appendix A. Partial Excluded Region 113 / i / dr f ' r '' \ d2 \ i i 2 / a /v 4 yv<. re ' / . . - " ^ 2 \As Jw3 ^ (b) Figure A.l Illustration of the partial excluded region for MFR. Appendix A. Partial Excluded Region 114 J?LS^~ I A'\ ex® mm V A T w2 YA> 1 | y / ^ ^ (b) Figure A.2 Illustration of the partial excluded region for NFP. Appendix A. Partial Excluded Region 115 s f ^ ^ c ^ ^ / l\ r iffl 1 \ \ v « jMBm* I \ \ ) ® | : \ ^^ •s \ ^4i^B i lk A3 \ lllllk y \ "* 1™P^P?P| ' •sHHf / 3 jfjr \ ^ ^ (b) Figure A.3 Illustration of the partial excluded region for MAD. Appendix A. Partial Excluded Region 116 (a) c, ' ^\nnax 1 /Vs£ A, «H| '='3rT / wm%7c \c, w, (b) Figure A.4 Illustration of the partial excluded region for ARR. Appendix B Asymptotic Value of ^2piqi(r, 0) oo In this appendix, we derive the asymptotic values of ]T) piqi(r, 6) as r<j —• oo for the case of non-fading in Section 4.3.2. For a random variable W with mean /z and variance a2 and for any e > 0, Chebyshev's inequality [66] states that PT(\W -fi\ > e) < ~ (B.l) which can be rewritten as 2 Pr ( |W - n\ < e) > 1 - ?j. (B.2) Let / be the number of interfering nodes. From (4.48), we have P r ( ; . 0 - H - »LS±m. (B.3) The mean and variance of / are equal to Nt. Applying Chebyshev's inequality, we have ?v(\I - Nt\ < aNt) > 1 - ^ 2 (B.4) for any a > 0. From (4.47), we have Nt = A(r^7T - Ae)pt?i{Ef). (B.5) If rd -» oo, lim - T = K (B.6) r<i—»oo r, where K = A7rptPr (Ef). 117 Appendix B. Asymptotic Value of Y^Pi<li{r, 9) 118 Let the value of a be set arbitrarily to Nt 3 . From (B.4), we can obtain that lim P r ( | / Td—*00 Nt\ < aNt) = lim Pr( \I - Nt \ < aNt) Nt—KX> > lim 1 5 — ? AT,—oo a2 Nf = 1. (B.7) Equation (B.7) states that as Nt —> oo, the probability that / is within aNt from its mean Nt approaches 1. The capture probability for the non-fading case is shown in (4.41) as e r f c ( ^ V c ^ ) *(r, 6) (B.8) oo where erfc(u) = -j-j exp [—t2)dt is the complementary error function. As r</ and Nt -^ oo, I will be in the range [(1 — a)iVt, (l+a)iV<] with probability close to 1. For ie [(1 — a)Nt, (1 + a)iVf ], the numerator in (B.8) can be simplified using (B.7) as lim erfcf —-TT^/CTT ) = lim erfc. rd->oo \ 2 r j / rrf-+oo \ 2r^ = erfc -v/cTTKr2 J . (B.9) If r<i —» oo, the denominator in (B.8) can be written as „2 lim Td—>00 erfc V2r; = lim Td—•OO = lim ra-+oo lim Td—»O0 - -OS?) l _ Hi (B.10) Appendix B. Asymptotic Value of Y2Pi<ti(r> &) 119 where erf (u) — -TJ / exp {-t2)dt is the error function. The last step of (B.IO) is obtained by o using the fact that lim erf (u) = ^j-. Note that for / in the range of [ (1 - a)Nt, (1 + a)Nt ], we have lim fd—»00 [ W j t = lim rd—>oo L ^ . Nt I Nt \ = lim exp (—KTg) exp(fe«;rg) = exp ( -* r e ) , -bNt (B.ll) where be[—a, a]. From (B.9) and (B.ll), we obtain the capture probability for rd -» oo as lim g,(r, 5) = exp ( K r\ ) erfc ( -y/citKr2 J. (B.12) rd-KX> ' \ 2 / Since g,(r, 0) is independent of i for (1 - a)Nt < i < (1 + a)A^, we have lim 2~^ pj ?j(r, 0) = exp (/erg) erfc f -yfcKKr2 J . (B.13) i=o > Appendix C Outline of Simulation Program In this appendix, we provide an outline of the program which was used to obtain the simulation results for a randomly distributed network. These results are described in Sections 4.4, 5.4, and 6.4. Suppose node X transmits packet K to node Y, and that only the nodes within distance r<j of X are considered in the simulation. The values of rj are set to 3rmax, [2 + ce}rmax, and 10rmai for interference models 1.2, 2.1, and 2.2, respectively. For interference models 1.2 and 2.1, any transmitting node beyond distance (xd — rmax) of X cannot interfere with Y, A node within such a distance will transmit if it is in transmission mode and it has a neighboring node in its forward direction. For interference model 2.2, there is little difference in the results when the value of rj is increased beyond 10rmax. For a given routing scheme and a given value of connectivity N = A7rr^ax, the steps of the simulation are described as follows. Step 1. Set the maximum progress accumulator acm and the probability, pt, of a node in transmission mode to zero. Set the total number of trials Ntr to a desired value. Step 2. Set the progress accumulator ac, the number, n*, of trials, and the number, nSJ of successful receptions of K by Y to zero. Step 3. Generate the number of nodes Nn according to a Poisson point process with average number of nodes per unit area equal to A for a given area of wrf. Step 4. Locate the Nn nodes uniformly in a circular area of radius rt with center C at the origin. This can be done by choosing the polar co-ordinates (rn, 6n) according to 120 Appendix C. Outline of Simulation Program 121 the following pdf s. fRn(rn) = ^r, (CI) rt and /e„(*«) = ^ - , (C2) where 0 <rn <rt and 0 < 0n < 2TT. Step 5. Choose a node X at random. If X is within distance rx, rx = rt — r^, of C, then go to Step 6; otherwise, go to Step 3. This is because an edge effect will occur if X is too far away from C. Step 6. Increment nt. If X is in transmission mode, it sends K to Y according to the routing scheme. Step 7. The event that Y receives K successfully depends on the interference model used. If Y receives K successfully, increment ns and accumulate the resulting progress z to ac. Step 8. If nt = Ntr, go to Step 9; otherwise, go to Step 3. Step 9. If ac > acm, replace acm by ac. Increment pt by a step of 0.01 and go to Step 2 until pt — 1. The pt value yields zmax is referred to as the optimal pt. The throughput S and the normalized average progress Zn can be determined by nt, ns, and acm as follows. S = j± (C.3) and *. = = = £ • (C4)
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Performance of transmission strategis in multihop packet...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Performance of transmission strategis in multihop packet radio networks Wong, Victor J. K. 1995
pdf
Page Metadata
Item Metadata
Title | Performance of transmission strategis in multihop packet radio networks |
Creator |
Wong, Victor J. K. |
Date Issued | 1995 |
Description | The problem of data communication in a multihop packet radio network (PRN) with a number of mobiles or randomly distributed stationary nodes using a slotted ALOHA channel access scheme is addressed. A multihop PRN is an extension of a single-hop PRN; in the latter system, a node can communicate directly with any other nodes. A multihop PRN is necessary if a node cannot reach another node due to transmit power constraints. In such a case, the node requires repeaters to forward packets on to the destination. If a network has a large number of nodes, employing spatial frequency reuse to achieve better spectrum is one of the advantages of a multihop PRN over a single-hop PRN. In multihop PRNs, a transmission strategy involves designing a routing algorithm and determining the transmission probability for each node in the network. Routing is one of the major problems in a multihop PRN. In this thesis, three new routing schemes, MAD, ARR, and MTP, are proposed. The performances of five transmission strategies based on the MFR, NFP, MAD, ARR, and MTP routing schemes with capture and fading are studied and compared. Results show that the transmission strategies based on the ARR and MTP routing schemes perform better than the other three transmission strategies. All five transmission strategies perform worse in the presence of Rayleigh fading; this is in contrast to contention-limited single-hop systems in which Rayleigh fading generally does not result in a poorer performance. A multiple receiver antenna system for a multihop PRN is proposed in which the nodes make use of multiple receiver antennas so as to provide diversity reception. The performances of the five transmission strategies based on the MFR, NFP, MAD, ARR, and MTP routing schemes in a Rayleigh fading environment are investigated. Results show that the performances of all five transmission strategies can be substantially improved by employing multiple antennas. The performance improvements of the transmission strategies arising from the use of directional transmitter antennas are also examined. It is found that the performances of all five transmission strategies can be improved by reducing the beamwidth of the antennas. |
Extent | 8689528 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-06-05 |
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.0065243 |
URI | http://hdl.handle.net/2429/8814 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 1995-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_1995-983671.pdf [ 8.29MB ]
- Metadata
- JSON: 831-1.0065243.json
- JSON-LD: 831-1.0065243-ld.json
- RDF/XML (Pretty): 831-1.0065243-rdf.xml
- RDF/JSON: 831-1.0065243-rdf.json
- Turtle: 831-1.0065243-turtle.txt
- N-Triples: 831-1.0065243-rdf-ntriples.txt
- Original Record: 831-1.0065243-source.json
- Full Text
- 831-1.0065243-fulltext.txt
- Citation
- 831-1.0065243.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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0065243/manifest