Sensitivity and Coding of Opportunistic ALOHA in Sensor Networks with Mobile Access

We consider a distributed medium access protocol, Opportunistic ALOHA, for reachback in sensor networks with mobile access points (AP). We briefly discuss some properties of the protocol, like throughput and transmission control for an orthogonal CDMA physical layer. We then consider the incorporation of necessary side information like location into the transmission control and numerically demonstrate the loss in throughput in the absence of such information. Through simulations, we discuss the robustness and sensitivity of the protocol under various modeling errors and propose strategies to allow for errors in estimation of some parameters without reduction in the throughput. For networks, where the sensors are allowed to collaborate, we consider three coding schemes for reliable transmission: spreading code independent, spreading code dependent transmission and coding across sensors. These schemes are compared in terms of achievable rates and random coding error exponents. The coding across sensors scheme has comparable achievable rates to the spreading code dependent scheme, but requires the additional transmission of sensor ID. However, the scheme does not require the mobile AP to send data through the beacon unlike the other two schemes. The use of these coding schemes to overcome sensitivity is demonstrated through simulations. Parvathinathan Venkitasubramaniam was born in India in 1981. He received his B.Tech. degree from the department of Electrical Engineering, Indian Institute of Technology, Madras in 2002. He joined the School of Electrical and Computer Engineering, Cornell University, Ithaca, NY, in 2002 and he is working toward his Ph.D. degree. He is a recipient of the 2004 Leonard G. Abraham Award (with S. Adireddy and L. Tong) from the IEEE Communications Society. His research interests include random-access protocols,sensor networks, and information theory. Srihari Adireddy was born in India in 1977. He received the B.Tech. degree from the Department of Electrical Engineering, Indian Institute of Technology, Madras, and M.S. and Ph. D. degrees from the School of Electrical and Computer Engineering, Cornell University, Ithaca, NY in 2001 and 2003 respectively. Currently, he is working at Silicon Laboratories, Austin, TX. He is a recipient of the 2004 Leonard G. Abraham Award (with P. Venkitasubramaniam and L. Tong) from the IEEE Communications Society. His research interests include signal processing, information theory, and random-access protocols. Lang Tong received the B.E. degree from Tsinghua University, Beijing, China, in 1985, and M.S. and Ph.D. degrees in electrical engineering in 1987 and 1990, respectively, from the University of Notre Dame, Notre Dame, Indiana. He was a Postdoctoral Research Affiliate at the Information Systems Laboratory, Stanford University in 1991. Currently, he is a Professor in the School of Electrical and Computer Engineering, Cornell University, Ithaca, New York. Dr. Tong received Young Investigator Award rom the Office of Naval Research in 1996, and the Outstanding Young Author Award from the IEEE Circuits and Systems Society in 1991, the 2004 IEEE Signal Processing Society Best Paper Award (with M. Dong), the 2004 Leonard G. Abraham Prize Paper Award from the IEEE Communications Society (with P. Venkitasubramaniam and S. Adireddy). His areas of interest include statistical signal processing, adaptive receiver design for communication systems, signal processing for communication networks, and information theory.     

Performance Analysis of Random Access Packet-Switched Code Division Multiple Access Systems

Analytical techniques for performance evaluation of synchronous random access packet switching in code division multiple access (CDMA) systems are presented. Steady-state throughput characteristics using several packet generation models are obtained. A number of example random access CDMA systems are compared in terms of their throughput versus offered traffic and utilization-delay characteristics. Numerical results indicate that appropriate use of multiaccess coding can provide utilization-delay characteristics superior to that of ALOHA. System stability is evaluated using a general finite user model, and the dynamic behavior of some example random access CDMA schemes is investigated.     

Multiple access in wireless digital networks

General principles for the design of a multiple-access system for large numbers of terminals transmitting to a single hub station are discussed. The importance of understanding the nature of the traffic to be carried by the network is emphasized. After some discussion of multiple access options for steady traffic and for slowly varying traffic, the use of random-access protocols for rapidly varying traffic is explained. Two general random-access protocols have been used in a variety of data networks, ALOHA and CDMA. Although these two techniques have different origins and are generally thought of as separate, they are in fact but different ways of looking at the same basic signals. The author shows that the use of multiple spreading codes in a CDMA network is not necessary in order to achieve multiple access capability. A single code can greatly reduce the complexity of a CDMA system. He introduces a spread-spectrum version of an ALOHA channel (spread ALOHA) which is equivalent to a CDMA channel with a common spreading code for all users. The equivalence the author demonstrates opens the door to a variety of techniques commonly used in ALOHA channels which can significantly increase both the throughput and the efficiency of the spread-spectrum channel     

Exploiting decentralized channel state information for random access

We study the use of channel state information (CSI) for random access in fading channels. Traditionally, random access protocols have been designed by assuming simple models for the physical layer where all users are symmetric, and there is no notion of channel state. We introduce a reception model that takes into account the channel states of various users. Under the assumption that each user has access to its CSI, we propose a variant of Slotted ALOHA protocol for medium access control, where the transmission probability is allowed to be a function of the CSI. The function is called the transmission control. Assuming the finite user infinite buffer model we derive expressions for the maximum stable throughput of the system. We introduce the notion of asymptotic stable throughput (AST) that is the maximum stable throughput as the number of users goes to infinity. We consider two types of transmission control, namely, population-independent transmission control (PITC), where the transmission control is not a function of the size of the network and population-dependent transmission control (PDTC), where the transmission control is a function of the size of the network. We obtain expressions for the AST achievable with PITC. For PDTC, we introduce a particular transmission control that can potentially lead to significant gains in AST. For both PITC and PDTC, we show that the effect of transmission control is equivalent to changing the probability distribution of the channel state. The theory is then applied to code-division multiple-access (CDMA) networks with linear minimum mean-square error (LMMSE) receivers and matched filters (MF) to illustrate the effectiveness of using channel state. It is shown that through the use of channel state, with arbitrarily small power, it is possible to achieve an AST that is lower-bounded by the spreading gain of the network. This result has implications for the reachback problem in large sensor networks.     

Distributed rate adaptive packet access (DRAPA) for multicell wireless networks

Fueled by the explosive growth of the Internet, applications are demanding higher data rates and better services. Given the scarcity of radio resources, higher network capacities need to be achieved through more efficient use of the available bandwidth. Current cellular networks utilize frequency planning schemes that are optimized for circuit-switched applications, and thus is inherently problematic for future wireless packet networks with bursty, high peak-rate traffics. Random access schemes such as the ALOHA are seen as better solutions for packet networks. However, co-channel interference may significantly reduce the network throughput when the multicell load is heavy. In this paper, we propose a distributed rate adaptive packet access (DRAPA) scheme to combine the advantages of rate adaptation (in circuit-switched networks) and random access (in packet-switched networks). In particular, DRAPA allows terminal stations to transmit packets in random access fashion in the presence of brusty interference from neighboring cells. The packet code rate is adjusted according to interference level so that the retransmisson is controlled at an acceptable level. The DRAPA scheme subsumes two traditional schemes as the extreme cases, and has superior performance over the traditional schemes in terms of throughput and stability.     

Slotted ALOHA and code division multiple access techniques forland-mobile satellite personal communications

The throughput and delay characteristics of a land-mobile satellite channel are analyzed for both slotted ALOHA. And slotted direct-sequence CDMA (code division multiple access), using binary phase shift keying (BPSK) modulation and forward error correction coding (FEC). In the case of CDMA, the application of path diversity techniques-maximal ratio combining and selection diversity-is also taken into account. Packet success probabilities are derived for both slow and fast fading, in order to evaluate the throughput and delay. Numerical results are presented for arbitrary code lengths and for specific values of the number of resolvable paths. It is shown that CDMA can offer a substantial improvement over slotted ALOHA, especially when the chip time is less than the delay spread     

A spread slotted CDMA/ALOHA system with hybrid ARQ for satellitemultiple access

We propose and investigate a new type of satellite multiple access protocol that combines the characteristics of the spread slotted (SS)-ALOHA protocol, code division multiple access (CDMA), and the hybrid automatic repeat request (ARQ) error controlling and retransmission scheme, in order to increase the throughput by reducing the number of retransmissions and to keep the bit error rate (BER) of the satellite link low when the channel experiences heavy traffic. The main feature of our proposed system is the utilization of two different fields in the analysis of the satellite multiple access problem. Since the hub now possesses the forward error correction (FEC) capability to correct errors that appear after the CDMA despreading of the packets, the satellite does not need to ask so often for the retransmission of erroneous packets and will ask for retransmission only when the FEC error correcting capability is exceeded. This paper also presents the adaptive optimization of the balance between the CDMA processing gain and FEC coding gain in order to obtain a better throughput for the SS-CDMA/ALOHA with hybrid ARQ protocol for satellite multiple access. The optimization is made with the constraint of keeping the bandwidth of the transmitted packets constant during all times. According to this, the effective throughput of the protocol (information bits over total transmitted bits ratio) is improved by adaptively changing the CDMA and FEC codes used in the transmission. This adaptive optimization is done by observing the channel status or load and increasing or decreasing both coding schemes' gains. Computer simulations show the performance of the proposed multiple access scheme     

On the throughput, capacity, and stability regions of random multiple access

This paper studies finite-terminal random multiple access over the standard multipacket reception (MPR) channel. We characterize the relations among the throughput region of random multiple access, the capacity region of multiple access without code synchronization, and the stability region of ALOHA protocol. In the first part of the paper, we show that if the MPR channel is standard, the throughput region of random multiple access is coordinate convex. We then study the information capacity region of multiple access without code synchronization and feedback. Inner and outer bounds to the capacity region are derived. We show that both the inner and the outer bounds converge asymptotically to the throughput region. In the second part of the paper, we study the stability region of finite-terminal ALOHA multiple access. For a class of packet arrival distributions, we demonstrate that the stationary distribution of the queues possesses positive and strong positive correlation properties, which consequently yield an outer bound to the stability region. We also show the major challenge in obtaining the closure of the stability region is due to the lack of sensitivity analysis results with respect to the transmission probabilities. Particularly, if a conjectured "sensitivity monotonicity" property held for the stationary distribution of the queues, then equivalence between the closure of the stability region and the throughput region follows as a direct consequence, irrespective of the packet arrival distributions.     

A novel random wireless packet multiple access method using CDMA

Random packet CDMA, a novel packet-based multiple access scheme for connectionless, uncoordinated random channel access is proposed. Random packet CDMA, or RP-CDMA, utilizes a novel packet format which consists of a short header and a data portion. Each header is spread with a unique spreading code which is identical for all users and packets, while the data portion of each packet is spread by a randomly chosen spreading sequence. The receiver operates in two stages: header detection and data detection. For header detection a conventional spread spectrum receiver is sufficient. Headers are spread with a large enough processing gain to allow detection even in severe interference. The data portion is decoded with a sophisticated receiver, such as a multiuser detector, which allows for successful decoding of overlapping active packets. It is shown that the RP-CDMA system is detector capability limited and that it can significantly outperform spread ALOHA systems whose performance is limited by the channel collision mechanism. RP-CDMA also experiences a much smaller packet retransmission rate than conventional or spread ALOHA, and provides better spectral efficiencies.     

Quasi-synchronous code-division multiple access with high-ordermodulation

Code-division multiple access (CDMA) is a multiplexing technique where a number of users simultaneously access a transmission channel by modulating and spreading their signals with preassigned codewords. This paper studies the performance of CDMA signals with orthogonal (Walsh-Hadamard) codewords and synchronization errors smaller than the chip time. Two high-order modulation techniques, M-level quadrature amplitude modulation (M-QAM) and M-level phase-shift keying (M-PSK) are compared with respect to bit-error rate (BER). The results are especially important for the return channel of cable TV networks and summarized as follows: 1) Synchronization errors between transmitters lead to interference noise, whereas synchronization errors between the transmitter and the receiver lead to a decreased amplitude of the received user signal. Both effects have significant impact on the system performance. 2) Closed expressions are obtained for the BER of a CDMA signal with M-PSK and M-QAM with a given maximum synchronization error. 3) The higher the modulation order, the more sensitive the system gets for synchronization errors. 4) The BER is highly dependent on the assigned codewords out of the Walsh-Hadamard code set. 5) The BER performance of M-QAM outperforms that of M-PSK     

Random access with large propagation delay

Random access to a packet broadcast channel with large propagation delay is investigated. A protocol is presented that combines slotted ALOHA random access with the use of forward-error-correction (FEC) across transmitted packets. Expressions for the throughput, delay, and drift of this protocol are derived. Numerical studies and asymptotic analyses of the drift indicate that the protocol has a maximum throughput of e^-1 and exhibits bistability and saturation behavior similar to that of slotted ALOHA with immediate feedback. However, unlike ALOHA, bistability and saturation in the code protocol can be eliminated with the proper choice of protocol parameters without increasing the packet delay. It is further shown that, when compared to slotted ALOHA, the code protocol typically achieves a higher throughput and lower delay at system equilibrium with no loss in maximum throughput     

Effect of Acknowledgment Traffic on the Performance of Slotted ALOHA-Code Division Multiple Access Systems

Use of code division multiple access (CDMA) in conjunction with slotted ALOHA improves throughput, since some of the "collided" packets can be retrieved, although at the expense of enlarged bandwidth. In view of the feasibility of recovery of packets, such schemes are attractive to carry receiver-to-transmitter acknowledgment (ACK) traffic also. The presence of ACK traffic is known to significantly reduce the throughput of slotted ALOHA channels. In this correspondence, the impact of such ACK traffic on the performance of slotted ALOHACDMA schemes is examined in detail for both finite and infinite terminal population.     

Spread spectrum multiple access for mobile meteor burstcommunications

The paper considers the application of a direct sequence code division multiple access (CDMA) scheme to a mobile meteor burst communication network. It is shown that a CDMA scheme solves the significant multiple-access problem caused by low channel diversity when remote station nodes are closely spaced. The CDMA scheme is shown to provide low waiting times and high throughput for networks of many thousands of nodes. A comparison of the CDMA scheme to a random frequency division multiple access scheme is provided where the offered traffic load, network size, system bandwidth, and interference levels are varied     

Performance analysis of DS-CDMA with slotted ALOHA random access for packet PCNs

In this paper, we present a discrete time Markov chain based analytical framework for the study of Direct-Sequence Code-Division-Multiple-Access (DS-CDMA) with slotted ALOHA random access protocols (DS-CDMA-S-ALOHA) for packet Personal Communications Networks (PCNs). It incorporates both the random access and the random errors associated with DS-CDMA-S-ALOHA protocols into a unified framework. The key feature is that it distinguishes between the two stages in the transmission process, namely the access stage and the reception stage, which characterize the random access and the random errors associated with DS-CDMA-S-ALOHA protocols respectively. Two DS-CDMA-S-ALOHA protocols are presented and analyzed. The performance of the protocols and the effects of the design parameters, namely the packet retransmission probability and the forward error correction code rate of the Bose-Chaudhuri-Hocquenghem (BCH) block codes are evaluated numerically and compared with a bandwidth equivalent conventional multi-channel slotted ALOHA system. The results show that, by proper design, the DS-CDMA-S-ALOHA protocols can double the throughput with respect to that of a bandwidth equivalent conventional multi-channel slotted ALOHA system.     

Throughput of unslotted direct-sequence spread-spectrummultiple-access channels with block FEC coding

An analysis of unslotted random-access direct-sequence spread-spectrum multiple-access (DS/SSMA) channels with block forward error correction (FEC) coding is presented. Extending a methodology that was introduced in an earlier paper on unslotted packet code-division multiple access (CDMA) without coding, a procedure for calculating the error probability of an L-bit packet in the variable message length, FEC-coded, DS/SSMA environment is described. This procedure is then used in conjunction with appropriate flow equilibrium traffic models to compute channel throughput. Using BCH block coding as an example, the analytical model is exercised to obtain throughput versus channel traffic curves over a range of code rates, leading to an assessment of maximum achievable throughput and the associated optimum FEC code rate. The results show that the use of block FEC coding provides a significant improvement in the bandwidth-normalized channel throughput (utilization), approaching values competitive with those for comparable narrowband ALOHA channels     

Frequency-hop transmission for satellite packet switching and terrestrial packet radio networks

The performance of frequency-hop transmission in a packet communication network is analyzed. Satellite multiple-access broadcast channels for packet switching and terrestrial packet radio networks are the primary examples of the type of network considered. An analysis of the effects of multiple-access interference in frequency-hop radio networks is presented. New measures of "local" performance are defined and evaluated for networks of this type, and new concepts that are important in the design of these networks are introduced. In particular, error probabilities and local throughput are evaluated for a frequency-hop radio network which incorporates the standard slotted and unslotted ALOHA channel-access protocols, asynchronous frequency hopping, and Reed-Solomon error-control coding. The performance of frequency-hop multiple access with error-control coding is compared with the performance of conventional ALOHA random access using narrow-band radios.     

Analyzing split channel medium access control schemes

In this work, we analyze and evaluate the maximum achievable throughput of split-channel MAC schemes that are based on the RTS/CTS (ready-to-send/clear-to-send) dialogue and that rely on pure ALOHA or on p-persistent carrier sensing multiple access (CSMA) contention resolution techniques. Our results show that, when radio propagation delays are negligible and when the pure ALOHA mechanism is used, then for a network with relatively large number of nodes, the maximum achievable throughput of the split-channel MAC schemes is lower than that of the corresponding single-channel MAC schemes. When the split-channel MAC schemes employ the p-persistent CSMA mechanism, then they out-perform the corresponding single-channel schemes when the maximum end-to-end propagation delays are at least 25% of the transmission time of the control packets on the single shared channel.     

A rural messaging network using spread ALOHA access with VSAT satellite terminals

This paper underlines the characteristics of a proposed mesh network for messaging applications in C-band using spread ALOHA protocol. A simulation program has been developed for studying the behaviour of large networks employing ALOHA access or its variants. It is a simulation for a large population network consisting of thin traffic small messaging terminals (SMTs), and models an infinite user population which employs fixed length data packets. The program is general and allows for the study of either the mesh or the star connected networks. Certain variations of the classical ALOHA schemes, such as slotted ALOHA (with user selectable slot length) and spread ALOHA, have been studied for network operation. In the case of spread ALOHA access, the program can be run with Barker, pseudorandom, Ping Fai Li or any other spreading sequence. The results of the simulation have confirmed the utility of spread ALOHA as an access protocol for MESCOMNET. It has identified an operating point on the throughput-traffic curve at which spread advantage is available for power reduction of SMTs.     

Performance Analysis of Space-Time Coded CDMA System Over Nakagami Fading Channels with Perfect and Imperfect CSI

In this paper, the performance of multiuser CDMA systems with different space time code schemes is investigated over Nakagami fading channel. Low-complexity multiuser receiver schemes are developed for space-time coded CDMA systems with perfect and imperfect channel state information (CSI). The schemes can make full use of the complex orthogonality of space-time coding to obtain the linear decoding complexity, and thus simplify the exponential decoding complexity of the existing scheme greatly. Moreover, it can achieve almost the same performance as the existing scheme. Based on the bit error rate (BER) analysis of the systems, the theoretical calculation expressions of average BER are derived in detail for both perfect CSI and imperfect CSI, respectively. As a result, tight closed-form BER expressions are obtained for space-time coded CDMA with orthogonal spreading code, and approximate closed-form BER expressions are attained for space-time coded CDMA with quasi-orthogonal spreading code. Computer simulation for BER shows that the theoretical analysis and simulation are in good agreement. The results show that the space-time coded CDMA systems have BER performance degradation for imperfect CSI.     

A multi-layer collision resolution multiple access protocol for wireless networks

In mobile communication networks operating in unreliable physical transmission, random access protocol with the collision resolution (CR) scheme is more attractive than the ALOHA family including carrier sense multiple access (CSMA) [IEEE Networks (September 1994) 50–64], due to likely failure on the channel sensing. Being a member of CR family schemes, a protocol known as non-preemptive priority multiple access (NPMA) is utilized in a new high-speed wireless local area network, HIPERLAN, standardized by European Telecommunication Standard Institute (ETSI). A conceptually three-layer CR multiple access protocol generalized from NPMA, supporting single type of traffic, is thus presented and analyzed in this paper. The CR capability of such a protocol (and hence NPMA) is proved to be significant by numerical substantiation that additional collision detection schemes are dispensable; also its throughput/delay performance is excellent when the proportion of the transmission phase to a channel access cycle is large enough (i.e., the winner of contention should transmit all of its packets successively). On the other hand, the simulated performance of NPMA serving integrated traffic is not fully satisfactory, primarily due to its distributed control mode and distinguishing traffic types only by the prioritization process.