Performance Characterization and Receiver Design for Random Temporal Multiple Access in Non-Coordinated Networks

Yin Lu＊,Jun Fang,Zhong Guo,J.Andrew Zhang

1 Jiangsu Key Laboratory of Wireless Communications,Nanjing University of Posts and Telecommunications,Nanjing 210003,China

2 Engineering Research Center of Health Service System Based on Ubiquitous Wireless Networks,Ministry of Education,

Nanjing University of Posts and Telecommunications,Nanjing 210003,China

3 Wuxi Longi Intelligent Technology Co.Ltd.,Wuxi 214400,China

4 University of Technology Sydney,Ultimo NSW 2007,Australia

Abstract: Random access is a well-known multiple access method for uncoordinated communication nodes.Existing work mainly focuses on optimizing iterative access protocols,assuming that packets are corrupted once they are collided,or that feedback is available and can be exploited.In practice,a packet may still be able to be recovered successfully even when collided with other packets.System design and performance analysis under such a situation,particularly when the details of collision are taken into consideration,are less known.In this paper,we provide a framework for analytically evaluating the actual detection performance in a random temporal multiple access system where nodes can only transmit.Explicit expressions are provided for collision probability and signal to interference and noise ratio (SINR) when different numbers of packets are collided.We then discuss and compare two receiver options for the AP,and provide detailed receiver design for the premium one.In particular,we propose a synchronization scheme which can largely reduce the preamble length.We also demonstrate that system performance could be a convex function of preamble length both analytically and via simulation,as well as the forward error correction(FEC) coding rate.

Keywords: random temporal multiple access;non-coordination networks; packet collision

I.INTRODUCTION

In quite a few wireless communication systems,nodes have very limited receiving functionality or even no receiver at all.Some of these systems are designed in this way to minimize circuit power consumption as they do not have internal power sources,such as passive radio frequency identification device(RFID) tags that use backscatter for signal transmission.Other systems,such as the emerging nano-sensors [1],are mainly used for collecting and forwarding information,and will be simpler to implement if receiving modules are completely removed from the sensor nodes.With the wide application of the Internet-of-Things technology [2]-[5],these transmit-only systems may become more popular.For example,the Sigfox IoT solution based on LoRa modulation improves the reliability of transmission by simply repeating the transmission several times without requiring coordination and acknowledgment from the gateway device.This essentially makes it unnecessary to have the reception function in the IoT node.For such systems without receiving functions,it is almost impossible to coordinate the transmission of different nodes using conventional multiple access schemes such as frequency- or time- division multiple access.Instead,a node is allowed to transmit by randomly picking up a timeslot,a frequency channel or a pseudo-random code.

In this paper,we provide a framework for analytically evaluating the actual detection performance in a random temporal multiple access system where nodes can only transmit.

Random access has been extensively studied [2]-[17].These works have studied various protocols to minimize the collision probability or maximize the overall throughput.However,to implement these protocols,feedback mechanisms are generally needed between nodes,and hence the receiving capability is required for nodes.In addition,these works typically consider the model that a packet is assumed to be corrupted once a collision,i.e.,the simultaneous transmission of more than one packet in the same resource slot,happens.However,it is still possible to recover a collided packet successfully in real systems.In this situation,thesignal to interference and noise ratio(SINR)is an equally important parameter to consider,to thecollision probability.The SINR characterizes how severe the desired signal is affected by the multi-user interference due to collisions,and it is closely related to signal modulation and multiple access schemes.In[9],the collision probability is investigated for massive IoT Networks with random access,which is modeled by the Poisson Point Process.Various random access protocols are analyzed and compared based on this model.

The feasibility of recovering collided packets for random access has been investigated in the literature,largely in the work on “capture effect” and “multi-packet reception” (MPR)[16]-[20].The capture effect is referred to that the strongest signals may be correctly decoded despite the collision.The termcapture probability,denoting the probability of the received SINR larger than a threshold,is often used to characterize the MPR performance.The closed-form expression of the capture probability is typically obtained via assuming a continuous distribution of the received SINR,where the details of the collision are ignored.

In this paper,we consider a simple random temporal multiple access (RTMA) protocol,characterize its performance by considering collision details,and investigate receiver designs enabling the use of short preamble for reduced collision,for completely non-coordinated nodes.The system consists of transmitter- only sensor nodes and an access point(AP) with only single packet reception capability.Different to many RTMA systems,we consider a RTMA network where all nodes use the same pseudo-random (PN) spreading code to encode data and send the PN-coded signal to the AP,which can largely simplify the node design and manufacture.Our major contributions in this paper are four folds.

·Firstly,different from existing work such as those reported in [9],we provide a framework for deriving explicit expressions for collision probability and SINR when an arbitrary number of packets collide.

·Secondly,we investigate and compare two receiver options at the AP,differentiating under the situation when packet collision happens.They are named asfirst come,first served(FCFS) andSwitch to the larger(STTL) schemes.The STTL scheme is shown to have better performance.The STTL scheme is the typical scheme studied in multi-packet reception literature such as those in [16],[17].Different from the existing work,we specifically consider the impact of collision on the performance of these two receiver options,and systematically compare the two options.

·Thirdly,we propose a novel and detailed receiver design for STTL,which does not require packet detection and can thus signif icantly reduce the length of the preamble.This is a brand new design that has never been reported before,to our best knowledge.Reduction of the preamble will not only reduce transmission power but also reduce collision probability and hence improve system perfor-mance.Optimization of receiver parameters is investigated both analytically and numerically.

·Finally,we demonstrate the design tradeoff in the length of preamble,length of pseudo-random spreading code,and coding rate in such RTMA systems and show that packet error rate could be a convex function of these parameters.

The rest of this paper is organized as follows.In Section II,after introducing the RTMA protocol,we derive analytical expressions for approximated collision probability and average SINR.In Section III-C,we investigate and compare FCFS and STTL,the two receiver options.In Section IV,we propose a detailed receiver design for STTL and evaluate the design tradeoff of the preamble and FEC coding in RTMA.Section V concludes this paper.

II.RANDOM TEMPORAL MULTIPLE ACCESS

2.1 The protocol

We consider a communication system where each of theMsensor nodes is transmitting one packet to the AP over a time window with a period equal toNsymbols.The length of every packet is fixed to beLsymbols.Each packet consists of a preamble of lengthLpand data payload of lengthLd.We will study the impact of direct sequence spread spectrum on the system performance,and hence assume a pseudo random (PN) spreading sequence (SS)is applied to the data payload.The length of the PN sequence isLs,and its power is normalized to 1.All nodes use the same preamble and spreading code for simplicity,and different nodes' data is separated via their unique addresses that can be embedded in,e.g.,the PHY header.The modulation is assumed to be BPSK.

Under the RTMA protocol,every node randomly chooses a starting time to continuously transmit its packet,which consists of a common preamble of lengthLp,the data payload of lengthLd,and the (L-Lp -Ld) cyclic redundancy check (CRC) samples.The starting time follows a uniform distribution between 0 andN-L+1.Note that such randomness can be achieved by using an internal timer plus event driven.Transmission can be activated with a random delay following a new measurement,without the carrier sensing and random backoff mechanism that is applied in conventional random access systems [12].A node can repeatedly transmit the same signal a few times to increase the probability of success reception.The required transmission time can be worked out for a given desired success probability according to the probability of successful reception as will be derived later.Acknowledgement of successful reception by the AP receiver,if needed,can also be achieved by using,e.g.,powering and sending simple message to a passive RFID circuit attached to the node.

Since the transmission time is not synchronized,there is no a formal definition of timeslot here.We letNc=N/Lbe the number of virtual timeslots,and for convenience,we assume thatNcis an integer.

2.2 Receiver options

For RTMA,we consider a receiver at AP which only picks up a packet at a time,without invoking complex parallel processing techniques to detect two or more overlapped packets simultaneously.Without loss of generality,let node 0 be the node of interest,and let nodes 1 tonbe those colliding with node 0.The general received signal of node 0,after applying dispreading operation,can be represented as

wherehn´,n´∈[1,n]denote the channel gains and are complex i.i.d.Gaussian random variables with mean 0 and varianceσh2,xn´are i.i.d.random discrete variables with equal probability on 1 or -1,g0,n´is the despreading gain in the correlator output for usern´-th signal,andz0is AWGN with mean zero and varianceσz2.At the synchronized point for node 0 in the AP's receiver correlator output,g0,0=1.If then´ node's packet is aligned with node 0,theng0,n´=1; otherwise,g0,n´shall approach to zero withLsincreasing.For short code,we assume thathas a mean value of 1/

We study two single-packet receiver options for AP.These two schemes process a packet normally if it is not overlapped with any other packets,but they differ in the actions when packets are overlapped.

1)First Come,First Served(FCFS): For FCFS,the AP starts to process a packet A once it arrives,and it will not look at other packets arriving within the period of packet A.Hence any other packets arriving during this period will be discarded.

2)Switch to the Larger(STTL):For STTL,when packets are overlapped,the AP will always process a packet that has the largest channel magnitude.This means that the AP will shift to a new packet while it is processing an existing one if they are overlapped and the existing packet has lower channel magnitude than the new arrival.A method for implementing such a switching is proposed in Section IV.

III.PERFORMANCE CHARACTERIZATION

Our focus here is to characterize and evaluate the actual SINR and packet error rate (PER)performance for systems using the protocol,without considering its optimization.The protocol itself can be improved by,e.g.,parameter optimization and combining multiple rounds of transmissions,based on the results in this paper.

In this paper,we study thecollision probability,processing rate,SINRand packet error rate (PER) for specific number of collided packets,to characterize the performance of the RTMA protocol.Theprocessing rateis defined as the ratio between the number of packets,which are being processed by the receiver,and the total packetsM.The processing rate indicates how many packets will be processed by the AP on average,and depends on both the collision probability and the actual receiver scheme.

For analytical characterization,we will apply some model simplification.In the absence of network clock synchronization,transmission can be completely random,and different parts of a packet may be overlapped with different number of other packets.Hence it is very challenging,if not impossible,to derive the analytical expressions for such collision probability and SINR.Instead,we consider a simplified case where transmission is timeslot based and different nodes' timeslots are aligned.This corresponds to the case where each node has its own timer or there is an external trigger to synchronize nodes' timeslots.In this case,the model becomes thatMnodes randomly pick upMout ofNcchannels.Such an approximation will lead to slightly small collision probability compared to the fully random case.WhenNcis sufficiently large,the difference will be quite small.We will see later that the analytical results from this simplified model are well matched with those simulation results based on the original completely random model.

3.1 Non-collision probability

In this subsection,we derive Pr(m),the probability ofmnodes not being collided by any other nodes,using the simplified model ofMnodes sharingNcchannels.These probabilities can be used to calculate a lower-bound for the processing rate.The probability Pr(m) can be computed as follows.

1) Computec1(m),the number of possible combinations formnodes sharingNcchannels,which is given by

2) Computec2(m),the number of possible combinations for (M-m) nodes colliding with each other over the remainedNc-mchannels;

3) Obtain the probability Pr(m) as

Note that Pr(M-1)=0 because the situation that only 1 packet is collided will not happen.

The termc2(m) does not have a general and simple expression for differentm,and needs to be computed specifically for everym.This makes it intractable to obtain exact closedform performance expressions that involve very large number of nodes.Fortunately,whenNcis much larger thanM,which is required to achieve acceptable PER performance as to be seen later,Pr(m) decreases quickly withmdecreasing.Therefore,we generally only need the exactc2(m) expressions for several largermvalues.In particular,we have the following results form=M-6 toMby considering detailed cases of collisions

Note that in these equations,we first consider the cases how many nodes collide,and then consider how many combinations of the virtual timeslots in which these collisions could happen.Usec2(M-5) as an example.The first termaccounts for the combinations of timeslots when all 5 nodes collide together.In the second term,denotes the number of combinations of two timeslots for 2 and 3 nodes colliding within them.There are C52combinations for selecting 2 nodes out of 5.Since each 2-node combination could collide in one of the two virtual timeslots,eventually it becomes

Given the results above,we can approximate the average number of non-collided packets that arrive at the AP as

where the second term approximates the impact when more thanM-6 nodes collide.The valueMs/Mserves as the lower bound for the processing rate.

3.2 Average SINR

For a particular node,we can work out the mean SINR considering all cases when node 0 is collided by different number of packets.Using the model presented in Section III-C,the theoretical mean SINR for node 0 can be represented as

Fig.1.Illustration of approaching 1 for various Nc and M values.

Wheref(n) is the probability ofnnodes colliding with node 0,γ(n) is the instantaneous SINR when such collision happens,E[x]denotes the expectation ofx.Note that whenn=0,there is no collision and γ(0) becomes the SNR.

The probabilityf(n) can be computed as

The term E[γ(n)]can be computed according to the distribution of signal and interference links.Since different nodes use the same spreading code for preamble and data payload,we need to differentiate between the cases when packets from different nodes are fully aligned or not.The interference will be quite different between the two cases.Based on the length of the direct sequence,the probability of then´-th node aligning and non-aligning with node 0 can be approximated as 1/Lsand(Ls-1)/Ls.Therefore,we can obtain

By applying (6) and (7) to (5),the mean SINR γ can be calculated as

When the length of the transmission windowNis fixed,the productNcLscan be regarded as fixed.In this case,the longer direct sequence will cause smallerNcand more collision,but it can lead to higher spreading gain.The combined impact on the averaged SINR γ can be assessed below.

Let λ(n) be the denominator in (8),and leta=Lsncbe a constant.Then we can rewrite λ as

Equation (9) suggests that for anyn≥0,λ(n)is always a monotonically increasing function ofNc.

The mean SINR is closely linked to the BER and PER.It can also be used to guide the preamble and coding design,as will be shown later.

3.3 Performance of receivers

We define theprocessing rateas the ratio between the number of packets,which are being processed by the receiver without stopping to move to another packet during the processing,and the total packetsM.The processing rate indicates how many packets will be processed by the AP on average,and depends on both the collision probability and the receiver options.Together with the mean SINR,they determine the overall throughput performance of the proposed RTMA scheme and systems.

1)First Come,First Served(FCFS):For FCFS,the AP starts to process a packet A once it arrives,and it will not look at other packets arriving within the period of packet A.Hence any other packets arriving during this period will be discarded.

The mean SINR for FCFS γFCFScan be approximated by γ in (8) as the distribution of the processed signals is unchanged.

The processing rate is larger than the non-collision ratioMS/M,because one packet will still be processed among multiple collided packets.

2)Switch to the Larger(STTL):For STTL,when packets are overlapped,the AP will always process a packet that has the largest channel magnitude.This means that the AP will shift to a new packet when it is processing a first one,if the two packets are overlapped and the first packet has a lower channel magnitude than the new arrival.

Apparently,this will lead to a lower processing rate compared to FCFS.In the worst case,only one packet will be processed if all packets are mutually overlapped,even if they span a much longer period than the packet periodL.

However,STTL assures a higher mean SINR than γ in (8),which can lead to better BER.

3)Comparison of the Two Options: Comparing the SINR of the two receiver options,we can see that γSTTL＞γFCFSand FCFS has larger processing rate than STTL.Such two analytical relationships cannot tell us directly which option is better.Hence in this subsection,we refer to some simulation results to show that 1) the analytical processing rate and mean SINR results match the simulation results well,and 2) in terms of the overall throughput performance,STTL is better than FCFS.In these simulations,the arrival time of all the packets are assumed to be perfectly known,the modulation is BPSK,andLp=15,Ld=33.

Figure 2 shows how the numerical SINR for FCFS and STTL,and the analytical SINR from (8) vary withM/Nc.The simulation is conducted for a system with 10 nodes at an original SNR of 10dB.The simulated channel is Gaussian distributed with mean zero and variance 1.The figure validates the intuitive conclusion that STTL achieves better SINR than FCFS.It also indicates that the analytical SINR is a good approximation to the actual SINR for FCFS.

Figure 3 demonstrates the processing rates for FCFS and STTL,as well as the analytical non-collision probability given byMS/M,whereMSis calculated from (4).The figure shows that the analytical result provides a good approximation for the processing rates of both FCFS and STTL.

Finally,figure 4 plots the PER performance for these two receivers.STTL consistently shows better PER than FCFS,which indicates that switching to a larger signal improves the overall detection performance although it may miss more packets than FCFS.

IV.DETAILED RECEIVER DESIGN FOR STTL

Fig.2.Measured SINR in the simulation and analytical SINR from (8) for different ratios of M/Nc,where M = 10 and 1/10σz2= dB.

Fig.3.Measured processing rates in the simulation and analytical Ms/M for different M/Nc,where M = 10.

For RTMA,the probability of collision and hence the system performance are closely re-lated to the packet length.This has a direct impact on the preamble design and the choice of modulation and coding schemes.For example,in conventional design,to achieve better packet synchronization at the receiver of AP,the longer preamble is preferred; and lower coding rate could also lead to better coding gain and system performance.However,in RTMA,longer packets can cause more collision,and hence such designs may lead to worse performance.We hence propose a special receiver which allows the use of short preambles and also investigate such tradeoffs in Section IV.

We study detailed receiver design for STTL and propose a packet structure suitable for its implementation in this section.

Fig.4.PER for FCFS and STTL versus SNR (1/σz2),where M = 10.

Fig.5.Receiver block diagram for STTL.

In a typical receiver,the synchronization module includes both packet detection and fine timing functions.Conventional receivers need to know whether a packet is arriving before invoking the fine timing module.Packet detection typically uses energy or autocorrelation detectors,such as the one proposed in [21].To achieve good autocorrelation performance,the preamble is required to be long.Unfortunately,for the RTMA protocol,longer preambles can significantly increase the collision probability.The auto-correlation detector is also very likely to fail for overlapped packets.

For STTL,we propose a receiver where such packet detection module can be avoided.Figure 5 shows the detailed block diagram for this proposed receiver.The blocks outlined in black show the main components of the receiver,similar to a conventional receiver,except for the lack of a packet detection module.The receiver uses the fine timing module and the auxiliary modules plotted in blue to control the output of a decoded packet,which consists of both data payload and CRC samples.The CRC check function (not shown in the figure)in the MAC layer will then determine whether this is a correctly recovered packet.

The fine timing module is based on cross-correlating the received signal with the template signal.The absolute value of the cross-correlation output at timem,|rm|,is compared with a stored valuermax.If |rm|＞rmax,it means this is possibly the start of a new packet with larger signal power.Then the currentrmaxis updated withc|rm|,wherecis a scalar slightly larger than 1,e.g.,c=1.2,to prevent frequent switching due to small fluctuation.At the same time,the pointer of the output buffer of length (L-Lp) is reset to 1.The channel estimation module uses the value ofrmfor channel estimation,and the equalization module starts to work on the next samples using the estimated channel.Alternatively,if |rm|≤rmax,the receiver will assume the new sample is part of the current packet and continue the processing of the current packet.It will also increase the buffer pointer by 1,such that the decoded bit for the current sample will be written to the next position in the buffer.Once the buffer is full,the processed packet will be exported to MAC layer for CRC check,and the receiver will resetp=1 andrmax=0.This processing flow well matches the STTL principal.

Such a scheme allows the preamble design to be focused on the cross-correlation property,which typically leads to much lower missed and false detection probabilities,compared to packet detection.

4.1 Preamble Length

Extending the signal model in (1) to represent a column vector ofLpreceived samples,we get

Given the locally known template signal xt=xp,where xpdenotes the preamble,themth output of cross-correlator,as a function ofn,is given by

where the superscriptHdenotes conjugate transpose.

When y corresponds to the received preamble,rm(n) becomes

When xtis not aligned with the preamble,the correlation output η(n) can be regarded as a random variable with mean zero and variance

To achieve good timing performance,|ρ(n)|needs to be larger than |η(n)| with a high probability.The average probability of |ρ(n)|＞|η(n)|can be represented as

From (13),we can see that longer preamble may not always lead to larger Pr(ρ＞η).This is because Pr(|ρ(n)|＞|η(n)|) andf(n) change in the reverse direction with respect toLp.At the same time,longer preamble causes more collision to data payload.Hence longer preamble may not lead to lower PER,either.

Fig.6.The length of preamble versus Pr(ρ＞η) for fixed parameters N = 4800,Ld= 32 and SNR=10dB.

Fig.7.The length of preamble versus PER for fixed parameters N = 4800 and Ld= 32.

Assume that both ρ(n) and η(n) are Gaussian distributed.In figure 6,we plot the analytical results from (13) and compare it with simulation results.The length of the transmission window is fixed as 4800 samples throughout this paper,unless stated otherwise.The figure shows a good match between the analytical and simulation results when the preamble is longer than 16.Hence the analytical result can be used for determining the preamble length for a given probability of successful detection.Inaccuracy at shorter preamble is likely due to the inaccuracy of Gaussian assumption of ρ(n)and η(n) in this case.

Fig.8.Variation of missed detection rate versus SNR for different length of PN codes,Preamble length is 16 for solid curves and 24 for dashed curves.N = 9200 and Ld = 44.

Fig.9.BER for detected packets (dashed curves) and total transmitted packets(solid curves).Spreading codes with different lengths are used for encoding the information bits.Length of preamble is fixed to 16,N= 9200,M = 10,and Ld = 44.

Figure 7 demonstrates how PER is affected by the different length of preambles.It can be seen that there exists an optimal preamble length for a givenNandLd.

Figure 8 presents the missed detection rate (MDR) for different PN code length(CodeLen) and different preamble lengths at different SNRs.The MDR is defined as the ratio between the missed packets by the proposed cross-correlation based processing and the total packets.The values ofM/Ncfor CodeLen=1,2,4,8 are approximately 0.07,0.12,0.21 and 0.4078.With preamble length increasing from 16 to 24,the MDR is reduced since the increased gain is larger than the multiuser interference due to increased collision.With the length of the PN code increasing,more collisions happen,and hence the MDR increases too.It can also be observed that to have a practically working system with a low MDR,using smallerM/Nc,larger SNR or longer preamble could both could all be potential solutions.

In figure 9,we plot the BER separately for the detected packets and for the total transmitted packets assuming that the detection of all received bits in a packet is wrong if it is not detected.PN spreading codes with different lengths of 1,2,4 and 8 are tested.The time window is fixed to beN=9200.As expected,longer PN codes lead to lower BER for successfully detected packets thanks to improved multiuser suppression capability.However,longer packets cause more collision,leading to higher missed detection ratio,as being demonstrated in figure 8.Hence,shorter spreading codes lead to lower overall BER when considering the bit errors due to missed packets.

4.2 FEC Coding and its Impact

Similar to that the PER is a convex function of the preamble length,PER can also be a convex function of the FEC coding rate,and lower coding rate does not necessarily lead to better performance for a fixedNand information rate.Codes with lower rate have better error correction probably,but they also lead to more coded bits and hence increase collision.Such effects can also be analyzed using the SINR formulation in Section III-B.Here we only show some simulation results to demonstrate the effects.

In figure 10,the PER obtained for coded and uncoded systems are plotted.An 11/15 BCH coding scheme is applied.The figure shows that with increasing number of nodes,the gap between coded and uncoded systems is reduced because the coding gain is counteracted by increased multi-user interference due to the collision.Coding gain is more prominent at lower SNR.

V.CONCLUSIONS

We have provided a framework for analysing the collision probability and SINR when different number of packets collide in a random temporal multiple access system.We show that the provided analytical results are well matched with simulation results.Two receivers,applying either the first come,first serve or keeping the larger principle,are investigated.It is shown that the latter,which switches to process a new packet with larger power when packet collision happens,always achieves better PER performance.Detailed designs for this better receiver option are investigated.Optimization of the preamble is studied both analytically and by simulation.It is shown that the PER is a convex function of the preamble length for a fixed access window,and so is the FEC coding rate.

Fig.10.PER for coded (dashed curves) and uncoded (solid curves) systems with fixed parameters N = 4800 and Ld = 32.