A channel access protocol for embedding CSMA on spread-spectrum packet radio networks
Descrição do Produto
A CHANNEL ACCESS PROTOCOL FOR EMBEDDING CSMA ON SPREAD-SPECTRUM PACKET RADIO NETWORKS D.P. Gerakoulis? T.N. Saadawi,2 and D.L. Schilling 2
Lihat lebih banyak...
1 Center of Excellence
In Information Systems Tennessee State University Nashville, TN 37203
2 .Electrical Eng. Dept. City College of New York 10031 New York, NY
ABSTRACT The application of CSMA in spread-spectrum (s-s) packet radio network, using the technique of having the receiver based code unique to each terminal is proposed and studied. The technique is realized by two protocols, namely the R-baselCSMA and the R -base ICSMA -BT code which are presented and analyzed. In the analysis we have assumed a single hop network, asynchronous transmission, Poisson arrivals and exponentially disributed packet lengths. We also have considered the delay capture properties of s-s waveforms. The network is modeled as a continuous time, two component state Markov chain. The R-baselCSMA-BT code protocol has also been examined under zero propagation delay since it becomes collision free in this case. Finally throughput versus the traffic rate characteristics have been obtained for both proto- cols with several number of users and at different propagation delays.
INTRODUCTION The idea of incorporating spread spectrum techniques in random multiple access schemes for packet radio networks has been utilized in order to decrease the vulnerabilty under multiuser interference and jammimg, and to achieve higher throughput. Random access techniques, such as ALOHA and CSMA have been extensively used in packed radio networks because these techniques tend to become more efficient as the user population becomes larger and the traffic statistics become bursty. Also they require shorter access delays and the user connectivity requirement becomes richer and more dynamic. However, ALOHA and CSMA degrade rapidly as the traffic intensity increases. In spread spectrum communications on the other hand, the signal is encoded by a pseudorandom code. At the receiver the same code must be used in synchronization with the transmitter to recover the data. Such a spread spectrum system provides code division multiple access (CDMA) with antijamming, low probability of intercept, multipath interference reduction etc. The use of a CDMA Protocol achieves multiple simultaneous transmissions by assigning different codes to each transmitted signal from a set of codes with low cross correlation function or by using the same code but with sufficient offset of any two transmissions.
In a given packet radio network with overlapping broadcast regions each terminal has a uniquely assigned spreading code which can be used either to encode the message that will transmit or to anticipate a reception encoded by its code. If the terminal uses its code to transmit a message the receiver would be overly complex since it must monitor all existing codes in order to decode the received message. If the assigned code is used to anticipate a receiving message then an increased interference will result among all transmissions addressed to the same receiver. Therefore we seek an optimum policy in utilizing the assigned codes which will keep the interference minimum and the tasks of the receiver manageable. The policy or the protocol must specify which code the terminal should monitor while idle and which code should use for transmission. Now we examine two of the most common protocols found in the literature -.
(i) Receiver-based protocol A unique code is allocated to each terminal which it will monitor while is idle (receiving code). Any terminal with a packet to transmit encodes the message in the destination’s terminal code (receiving code) and transmits it, while the receiver recognizing its code will decode the message. Multiple transmissions to the same receiver will result in receiving the first message (capturing it) and rejecting any other that overlaps. Davies and gronemeyer  have analyzed such a scheme with centralized receiver where any collision or loss of a packet is resolved with ALOHA type random access. The drawback of this scheme is that any packet transmitted during the reception of the first one will be lost.
(ii) Receiver-Transmitter (R-T) base protocol This protocol has been proposed by Susa-Silvester in  and used by Su-Li in . The R-T protocol is as follows: To each terminal i is assigned two unique spreading codes, the receiving code Ri and the transmitting code T i . Any terminal with a packet to send encodes the addressing portion of the packet in the receiving code of the destination terminal j, R j , and the following portion of the packet (data, see fig 1) in the transmitter’s code T i . The receiving code R,. Upon reception of a packet it detects its address and notes the source address, then switches to the transmitter’s Ti to receive the data.
6.8.1. CH2538-7/88/0000-0199$1 .OO
0 1988 IEEE
R-T protocol reduces the probabiliity of interference which can take place only during the addressing portion of the packet and among the terminals transmitting to the same receiver j under the same code RI. Collided packets may be retransmitted after random delay (ALOHA). The drawback of R-T protocol is that each terminal will be too complex to implement in terms of the required hardware and is not suitable for broadcasting. Various other protocols have been proposed that utilize transmitting codes, such as common-transmitter protocol given in  etc. In this paper we propose and analyze a protocol that has the simplicity of the receiver's based protocol which also reduces the interference to the level of R-Tprotocol. This will be achieved by using carrier sense multiple access (CSMA) which gives US the ability to Sense the channel before transmission and thus avoids collisions or loss of the packets as in ALOHA access.
2.NElWORK MODEL We consider N identical terminals distributed over a geographical area, where any terminal can transmit to any other in the network directly (in one hop), and with equal probability (uniform traffic matrix). At any time a terminal may transmit or receive but cannot receive and transmit at the same time. We also assume asynchronous transmission (unslotted channel time). The proposed protocol, named R-baselCSMA, is a receiver-based protocol where the contention among the terminals transmitting to the same receiver can be resolved using nonpersistent CSMA (see ref. ). More specificidly R -boselCSMA protocol operates as follows: A unique spreading code R has been allocated to each terminal (receiving code). All RI codes are pseudoorthongal, 1 I j s N. Any terminal j while idle constantly monitors its code R I . Every ter minal with a packet to transmit to terminal j encodes the message using code RI and then senses the channel in code R,. If the channel is sensed busy, then the terminal schedules the retransmission of the packet to some later time according to the retransmition delay distribution. At this new point in time it senses the channel in code R, and repeats the algorithm, The packet structure considered is shown in fig 1. According to the R-baselCSMA protocol two or more packets may arrive at the same receiver only if they have been transmitted within an interval equal to the propagation delay time ( T d ) from the momment of the first arrival (r,). This time interval is "vulnerable" because one or more arrivals in it will cause a "collison".(see fig 2) However, when using the R-buselCSMA protocol, the PN code will act only to the first signal received. The assumption here is that relative delays between packet arrivals are sufficient i,e., several chips have elapsed, so that the receiver has the capability to choose the first signal and reject the others. Specifically any packet will be considered reliably
captured if it arrives at least T, sec (capture time) before any other. The capture time T, can be as small as few chips in a direct sequence PN code (say 10-80 p e c for a given channel), while the propagation delay can be in the order of 100-200 pcc if the terminals are within a radious of 30-60 km from each other i.e., T, < T d . In addition we assume that the number of simultaneous transmissions is always below a threshold supported by the assigned processing gain. The system performance will degrade drastically if the above threshold is exceeded. Hence we assume that the effects of a captured packet lost in subsequent interference is negligible.
3. ANALYSIS The R-baselCSMA protocol can be modeled as a continous time Markov chain. In defining the states of the system we divide the set of N terminals into Idle and Busy ones. Busy terminals are also divided into Pairs and Singles as shown in fig 3. A Pair is made of a transmitter and a receiver communicating successfully, while a Single is considered to be any terminal transmitting unsuccessfully. Unsuccessful transmission occurs when the received packet is either uncaptured or lost. A lost packet is the one which transmitted either to an already transmitting terminal or after a captured packed in the interval T ~ T,, - (see fig 4). Any terminal with a packet which cannot be transmitted, because a busy channel is sensed, is said to be "Blocked". A blocked terminal is considered idle because it is still able to receive while not transmitting. Hence the state of the network is defined to be the two components vector (np, ns), where np is the number of pairs and n, is the number of single terminals at any given instant. The number of idle terminals ni at state (np, n,) can be found from 2np + n, + ni = N (1) The traffic model adopted here is a Poisson arrival process with parameter h packets per sec, per terminal and the packet length is exponentially dismbuted with mean up, (The packet length is considered exponentially distributed because it will greatly simplify our analysis). Based on the asynchronous transmission considered above with Poisson arrivals the probability that more than one arrival occurs at the same instant is zero. Therefore the possible transitions from state (np, n s ) , are only to the four neighbouring states, (np. ns-l), &-I, ns), (np, n,+l), and (np+l, ns).
The probability of having k arrivals in T sec is Pr [x=k] = e- XT
(2) k! for k=0,1,2, ... , that implies the probability density function of the interarrival time T is exponentially distributed f ( ~=) e-'T. The probability that the interarrival time is greater than the capture time T, is the capture probility P,. Hence Tc
P, = Pr [oT,] = 1-
If (T)d.r = 0
The transitions (n, ,ns)+(np-l,ns) and (np ,ns)+(np ,n,-l) occur with rates n,p and nap respectively. Fig.5 shows all transitions rates for the case Td=Tc. (The states at the boundaries do not have all possible transitions) The number of possible states of the network (np,nS), with N terminals, can easily be calculated from the number of possible values of n,, for any given value of np . That is W , S N - 2 n p or N-2np+l values of n, for each n while np taking value o ~ ~ I L Nn/ u~s ~the . n u m g r M of states is
The Markov model considered assumes exponential distribution of the propagation delay Td and capture time T,. However because the nornalized delay over the average packet length a is very small (lo4 e a e 10-3, it is justifiable to consider the values Of Tc and Td Constants. Fig 5 shows the general case of the state transition diagram. The transition (np ,n,)+(n,+l,n,) takes place at the rate hniPr[n,+np+l] where
The first term in equation ( 5 ) is the capture probability that (ni-l) other idle terminals may transmit to the same receiver, with probability [ ( n i - l ) / ( ~ - l ) ] . The last term in ( 5 ) is the probability that the receiving terminal remains idle during the propagation time delay Td. The transition rate (np,n,) + (n,,nS+1) is h i P r [n,+n,+l]. The Pr [n,+n,+l] includes all possible cases of collision or loss of a transmitted packet. These can be described as follows: (i) When the packet has been transmitted to another transmitting terminal, then it will be lost. This event has probability of occurance [(n,+n,)/(N-l)l , if the transmission is not blocked. If however another terminal (single) is already transmitting (unsuccessfully), to a particular transmitter i, any new transmission to i will be blocked, since code Ri will be sensed busy. Hence the actual probability of occurance of this event will be [ ( n , + n , ) / ( ~ - l ) ] ( l - ~ ~ , ) , where PB, represents the probability that any transmission to a transmitting terminal is blocked. pB1..hasbeen shown to take values o