Multiple packet reception in wireless ad hoc networks using polynomial phase-modulating sequences

Multiple packet reception in wireless ad hoc networks using polynomial phase-modulating sequences
of 18
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
  IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 51, NO. 8, AUGUST 2003 2093 Multiple Packet Reception in Wireless  Ad Hoc Networks Using PolynomialPhase-Modulating Sequences Aldo G. Orozco-Lugo  , Member, IEEE  , M. Mauricio Lara  , Member, IEEE  , Desmond C. McLernon  , Member, IEEE  ,and Hugo J. Muro-Lemus  Abstract— This paper proposes a blindinterference cancellationalgorithm that is able to provide multiple packet reception capa-bility for asynchronous random access wireless mobile  ad hoc  net-works. The algorithm exploits the fact that the baseband signal ex-hibits cyclostationarity properties, which are induced at the trans-mittersbymeansofmodulatingthesymbolswithpolynomialphasesequences. This modulation does not expand the bandwidth andcan be considered as a “color code” that can be used to distinguishone transmission from the others (i.e., packets from other users).Theproposed techniquedoesnotrequire knowledgeofthestartingtimeoftransmissionofthedesiredsignalandcanalsobeappliedtotime-dispersive multipath channels. In addition, a practical way of assigning the color codes via the use of a common codebook knowntoallnodesisproposed,andtheimpactonlocalthroughputofsuchaschemeisanalyzed.Simulationresultsillustratetheexcellentper-formance of the proposed approach.  Index Terms— Blind space-time processing, medium access con-trol, multipacket reception, polynomial phase signals, random ac-cess. I. I NTRODUCTION W ECONSIDERmultiplepacketreception(MPR)inasyn-chronous random access wireless mobile  ad hoc  net-works (MANETs). A MANET can be defined as a wireless net-work consisting of a collection of mobile nodes that have thecapability of interconnection without the support of fixed in-frastructure or central control. A key issue in random accessnetworks is the decrease of throughput due to collisions arisingfromuncoordinatedtransmitters.Inrandomaccesswirelessnet-works, this problem is further accentuated due to the charac-teristics of the medium. Wireless transmission gives rise to theso-called hidden/exposed terminal problem [1]. This problemlimits the efficacy of carrier sensing with collision detectionprotocols that are so useful in random access wired networks[2]. Recently, some approaches have been proposed to tacklethe problem of collisions in  ad hoc  networks. One method isto use extra signaling to alleviate the hidden/exposed terminal Manuscript received September 16, 2002; revised March 31, 2003. The asso-ciateeditorcoordinatingthereviewofthispaperandapprovingitforpublicationwas Dr. Alfred O. Hero, III.A. G. Orozco-Lugo, M. M. Lara, and H. J. Muro-Lemus are with CIN-VESTAV-IPN, Sección de Comunicaciones, México City, México (;; C. McLernon is with the Institute of Integrated Information Systems,School of Electronic and Electrical Engineering, University of Leeds, LeedsLS2 9JT, U.K. (e-mail: Object Identifier 10.1109/TSP.2003.814472 problem [1]. Another approach that has its roots in powerfulsignal processing techniques, is to give each node the capabilityof receiving multiple packets simultaneously [3]. This is in con-trasttotraditionalmediumaccesscontrol(MAC),whereitisas-sumed that all packets are destroyed if a collision occurs. UsingMPR, the transmissions are not as restrained as with traditionalmedium access protocols, which is a fact that could allow an in-crease in throughput [4]. Although both MAC and source sepa-ration methods based on signal processing are mature fields of research, their interaction offers significant improvement possi-bilities for random access wireless networks that the scientificcommunity is just starting to explore.MPR can be achieved, provided some form of diversity isavailable [4], and can be obtained using antenna arrays (pos-sible at both transmitter and receiver) that allow the system toexploit the spatial separation (space diversity) of the differentusers. A thorough study on the impact of using antenna arraysin MANETs can be found in [5]. A special form of MPR [6]is found in the capture phenomena (power diversity) that occurswhenastrongusercanbesuccessfullyreceivedevenwhenacol-lision occurs, provided the ratio between the combined powersof the interference and that of the strongest user is below a cer-tain threshold [7]. Spread spectrum code division multiple ac-cess(codediversity[CDMA])isanotherformofdiversityusefulto resolve collisions and achieve multiple packet reception [6],[8]. Network-assisted diversity [9] in the form of selective re-transmissions is also possible (temporal diversity).In this paper, we propose a new algorithm that provides mul-tiple packet reception capability in wireless asynchronous  ad hoc  networks. We use a modulation induced cyclostationarity(MIC) approach similar to those used in [10]–[14], but in ourcase, the baseband data sequence is modulated by a polynomialphase sequence (PPS). This can be viewed as introducing a wa-termark in the desired signal [15]–[17] or as a color code [3].Although we use a MIC approach, the interference cancellationalgorithm that we propose does not rely on cyclostationary sta-tistics, but rather, we exploit the strong structural property im-posed on the transmitted signal by the PPS sequence. In thissense, the proposed method posses some similarity to the ap-proaches in [18] and [19] (in these cases, the exploitation of thediscrete nature of the input). It turns out that the exploitationof the structural property results in an algorithm that performsbetter than those that take advantage of the induced cyclosta-tionarity using cyclic statistics. In the case of non time-disper-sive channels, our proposed approach imposes the same signal 1053-587X/03$17.00 © 2003 IEEE  2094 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 51, NO. 8, AUGUST 2003 model (in the frequency shift case) as in [20]–[22]. It is worthpointing out that in [20]–[22], cyclostationarity is induced byfrequency shifting the r.f. carrier by a small amount. However,the same statistical properties can be obtained by processing atbaseband [10]–[14], thus avoiding any increase in bandwidth.Previous work in the area of source separation applied to theMPR problem can be found in [3], [9], and [23]. In [9], separa-tion is achieved by a special retransmission protocol where allthe terminals involved in a collision (say ) are obliged to re-transmit in exactly ( ) future slots, while all other termi-nals remain silent. This way, and provided the channel charac-teristics sufficiently change from slot to slot, a ( ) mixingmatrixcanbeconstructed(exploitingtemporaldiversity)thatcanbe inverted to recover the desired transmissions. Although thisschemeisveryappealing(nothroughputpenalty), itcanonlybeapplied in synchronous centrally controlled networks. In [23],a semi-blind approach that exploits the differences between thepropagationchannelsofthedistinctusersinvolvedinacollisionis proposed (thus making implicit use of spatial diversity). Thismethod extracts the collided packets sequentially, starting withthosehavingpropagationchannelsoflowerdispersion.Althoughthe method is effective and allows reduction of the amount of trainingrequired,itcanonlybeappliedinsynchronousnetworks.The work in [3] uses, like the method proposed here, modula-tion induced cyclostationarity. However, in the former case, theauthors modulate the transmitted signals by special sequencesthat induce instantaneous power variations. Unknown to the au-thors in [3], this idea was first presented in [24] and [25], whereitwasshownthattheknownmodulusalgorithmcouldbeusedtoachieveglobalseparationofsourcesprovidedthemodulatingse-quencesfulfilledcertainconditions.However,[24]and[25]wereapplied tocentrally controllednonrandomaccess spacedivisionmultipleaccess(SDMA)systems,whereas[3]appliestorandomaccess adhoc systems.Theadvantageoftheapproachin[3]overthe ones in [9] and [23] is that it can be applied in asynchronous ad hoc  networks. However, the method requires knowledge of the timing of the desired signal. The advantage of the method tobe presented here is the fact that we do not require this timing,making the proposed approach fully asynchronous. Another ad-vantage is that the PPS modulating sequences that we use heredo not vary the power of the transmitted signal, thus imposingno penalty in bit error rate (BER) incurred at the receiver due tomodulus variations, unlike the approach in [3].This paper is organized as follows. Section II introduces thesystem model. The network structure and the reception modelare clearly outlined. The modulation operation and the randomaccess mechanism are also explained. Section III derives theconditions on the parameters of the polynomial phase modu-lating sequences that allow the removal of both random accessinterference (RAI) and intersymbol interference (ISI) simulta-neously. Section IV presents the source separation algorithm,whereas Section V deals with the synchronization mechanism.Section VI introduces a scheme for assigning color codes tousers and presents a simplified analysis intended to investigatethe impact of the codebook size on local throughput. Some sim-ulations illustrating the interference cancellation capability of the method are presented in Section VII. Finally, conclusionsare given in Section VIII. Fig. 1. Typical setup in a MANET. II. S YSTEM  M ODEL  A. Network Architecture The network model we will use here corresponds to a typicalsituation in wireless MANETs with random access. A key as-sumption in a wireless  ad hoc  network is that, at a given time,there can be at most (perhaps some tens) transmitters thatare able to communicate with a given receiver (say ) [26], asshown in Fig. 1. (This is so because mobile nodes will prob-ably have short range due to power limitations.) This character-isticmaybeconciselyexpressedbyaconnectionmatrix (dim.)withelements representingthevalueoftheconnectioncoefficient between transmitter node and receiver node andbeing the number of nodes in the network. Every coefficientcan be either zero or one, depending on whether the trans-mission from node is, respectively, received below or above asignal-to-noise ratio (SNR) threshold at node . Note that in aMANET, the value of could be very large (even thousands ormillions),andinthiscase, willbesparse(only elementsof column willbeequalto1).Moreover,duetothehighlymobilecharacteristicsofthenodes, willbetimevarying.Besides,be-cause of the sparse nature of , multi-hop communication musttake place if any two nodes out of the reach of each other wishtomake contact.Notealsothateventhoughtherearepotentiallytransmissions that can be received at node at a given time(those inside the “cloud” in Fig. 1), only a subset, let us say ,may be active (those with pointing arrows).  B. Packet Reception Model The reception model used in this paper is a good approxima-tion toa situationthat couldpossibly be present in apractical  ad hoc  network. We will use Fig. 2 as an aid to better understandthe reception model that follows. The arriving packets comingfrom different users are totally asynchronous (both at symboland packet levels), and they all have a fixed length, which isknown to the receiver and equal to symbols, and the symbolrate is assumed the same for all users. The receiver will processthe packets in a block by block or window by window fashion.The width of each window will be equal to symbols.Once a transmitter sends a packet, it has to wait at least the in-terval of one receiver observation window between the end of thecurrentpacketandthebeginningofthenextone.Inthisway,it is assured that the receiver will not see more than one packet  OROZCO-LUGO  et al. : MULTIPLE PACKET RECEPTION IN WIRELESS  AD HOC   NETWORKS 2095 Fig. 2. Packet reception model.Fig. 3. Analysis windows. fromeachactivetransmitterinagivenobservationwindow.Dueto the asynchronous assumption for the arrivals, packets canstart at arbitrary times with respect to the beginning of the re-ceiverobservationwindow.Infact,packetscanevenstartbeforethe observation window begins or can finish after the observa-tion window ends, as can be clearly seen in Fig. 2. Therefore,if the receiver does not want to disregard any complete packet,the observation window should be displaced in such a way thatthe overlapping between consecutive observation windows is atleastonepacketlength.Notethatiftheoverlappingbetweenad- jacent observation windows is exactly one packet length, a spe-cific packet will be completely observed either in the current,previous,ornextwindow.Asanexample,considerFig.3,wherepackets 3 and 5 are completely observed in the current window,packet 1 is completely observed in the previous window, andlikewise for packet 4, but for the next observation window. Onthe other hand, if the overlapping between adjacent windowsis greater than one packet length, then a specific packet couldbe completely observed in more than one observation window.Finally, if the overlapping between adjacent observation win-dows is less than one packet length, then it is possible that thepacket could not be completely observed in any observationwindow and then could be potentially lost. For a given lengthof the observation window, the greater the overlapping betweenwindows, the more processing that is needed per time intervalsince the observation window advances slower. So, from nowon, we will consider that the overlapping between adjacent ob-servation windows is equal to one packet length—a choice thatminimizes the computational burden and, at the same time, al-lows the receiver to see all the packets complete in some obser-vation window.In this paper, we do not require the strong assumption of being synchronized to the starting time of the desired packetas in [3]. We will show later that using the proposed scheme,this timing can be obtained after interference mitigation. How-ever, not knowing the starting time of the desired transmissionintroduces a penalty either on throughput or on computationalburden, as will be seen later. In order to be able to implementmutipacketreceptioncapabilities atthereceiver,we propose theuse of a set of polynomial phase sequences in the modulationprocess. Each time a packet is sent, a sequence from the set ischosen at random (with equal probability), and it is used as awatermark or color code to distinguish the different users at thereceiver. C. Modulation Using Polynomial Phase Sequences Considerthediscrete-timebasebandone-waydigitalcommu-nications link between a transmitting nodeand a given receiver, as shown in Fig. 4 (from now on, we dropthe -index since we focus on a particular receiver, and there-fore, ). We assume that the transmitter uses one an-tenna and the receiver has antennas forming an antenna array(weexploitspatialdiversityfortheseparationbutcodediversitycould also be employed). From Fig. 4, isthe transmitted signal, where is the information sequence(assumed to be real valued), and isa polynomial phase modulating sequence [27], where andare design parameters to be chosen later and used as color codesto distinguish users. We have used quadratic PPSs as modu-lating sequences for the following reasons. First, we know fromthe works in [20]–[22] that complex exponential sequences areuseful to induce cyclostationarystatisticsatthe transmittersthatcan be exploited at the receiver to separate multiple transmis-sions in the non time-dispersive channel case. In addition, from[28]–[30], we know that discrete-time complex chirp sequencesare useful to induce cyclostationarity on thetransmitted signal that can be exploited at the receiver to cancelISI in the single-user time-dispersive channel case. Therefore, asomehow natural extension is a combination of these two caseswith the intuition that the resulting signal structure will be suf-ficient to cancel both the RAI produced by multiple transmis-sions and the ISI that could result if every transmitted signaltravels through a time-dispersive channel. As it will be clearlater, this structure for is indeed useful for allowing usto remove both the RAI and ISI. However, one might wonderwhether a PPS of higher degree would be a better choice. Theanswer is that it is quite possible to have some advantages, butthe main drawback is that there will be more free parameters toselect (one for each power of ), and the conditions they shouldfulfill will necessarily be more complicated. Therefore, in thispaper, we will simply focus on the quadratic PPS previously de-scribed. Note that although is a real sequence, the trans-mitted signal is complex valued. A quadrature amplitudemodulator is then used to generate the transmitted signal, anda quadrature receiver is also assumed. The generation of thebaseband continuous-time transmitted signal can be car-ried out, as shown in Fig. 5, where each element of the dis-crete-time signal is applied to the pulse shaping circuitonce every symbol period . It is important to notice that the  OROZCO-LUGO  et al. : MULTIPLE PACKET RECEPTION IN WIRELESS  AD HOC   NETWORKS 2097 Notethatin(7),weareusingthesamenotationforthereceivedsignal as in (1), although the signal is now formed by thecontribution from multiple users. However, the specific natureof (single or multiple transmitters) should be clear fromthe context. Equation (7) can be rewritten in matrix notation as(8)where (dim.) and . Thevalueofthechanneldispersion istakentobetheonewiththegreatestdispersionfromallpossiblechannelresponsesresultingfrom the combinations between all pairs of transmitter-receiverantennas. An upper bound for the value of is all that themethod to be proposed requires for operation. It does not needthe knowledge of the channel model orders of any individuallink nor the number of links. Note that in a multiple user sce-nario, it is not easy to obtain this information [13]; therefore,methods relying on this knowledge (or relying on estimation of the model orders, which is difficult) are inherently weak. It canbe seen from (8) that apart from ISI, RAI also exists.To separate the signal coming from transmitter , the receiveruses a linear space-time fractionally spaced equalizer (STFSE), whose coefficients are optimized to recover the desiredtransmission. The filtered signal is calculated as in (2) by(9)Now, substituting from (8) into (9), we have(10)where [length ] is theoverall response of channel plus equalizer for the userat the symbol rate. The task is then to Fig. 6. Discrete-time input series. select such that possesses only one element differentfrom zero at an appropriate position, whereashas all elements equal to zero (at least in the noiseless case).If this goal is achieved for the recovery of all transmissions, then ISI and RAI will both vanish at everytransmission, and the receiver possesses MPR capability. Notethat for the recovery of each transmitted signal, there are atmost valid solutions, each one corresponding toa different equalization delay.Thus, the problem posed in this paper can be concisely statedas follows: Given a set of discrete-time input series (theobservations at the antennas oversampled times each—seeFig. 6), and the knowledge of the codebook of color codes (pa-rameters ),obtainasetof (codebooksize)discrete-timeoutput series each one corresponding to one virtual channel(made available by using a different color code). Figs. 6 and7 better illustrate the objective. Note that the output time-seriesassociated with a given color code ( will be the same forall transmitters as explained next)could contain a completely orpartially observed transmitted packet or just noise.... ... ... ... ... ... ...... ... ... ... ... ... ........................... ... ... ... ... ... ...(6)
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!