Stochastic gradient optimization of importance sampling for theefficient simulation of digital communication systems

Importance sampling (IS) techniques offer the potential for large speed-up factors for bit error rate (BER) estimation using Monte Carlo (MC) simulation. To obtain these speed-up factors, the IS parameters specifying the simulation probability density function (PDF) must be carefully chosen. With the increased complexity in communication systems, analytical optimization of the IS parameters can be virtually impossible. We present a new IS optimization algorithm based on stochastic gradient techniques. The formulation of the stochastic gradient descent (SGD) algorithm is more general and system-independent than other existing IS methodologies, and its applicability is not restricted to a specific PDF or biasing scheme. The effectiveness of the SGD algorithm is demonstrated by two examples of communication systems where the IS techniques have not been applied before. The first example is a communication system with diversity combining, slow nonselective Rayleigh fading channel, and noncoherent envelope detection. The second example is a binary baseband communication system with a static linear channel and a recursive least square (RLS) linear equalizer in the presence of additive white Gaussian noise (AWGN)     

Quick simulation: a review of importance sampling techniques incommunications systems

Importance sampling (IS) is a simulation technique which aims to reduce the variance (or other cost function) of a given simulation estimator. In communication systems, this usually, but not always, means attempting to reduce the variance of the bit error rate (BER) estimator. By reducing the variance, IS estimators can achieve a given precision from shorter simulation runs; hence the term “quick simulation.” The idea behind IS is that certain values of the input random variables in a simulation have more impact on the parameter being estimated than others. If these “important” values are emphasized by sampling more frequently, then the estimator variance can be reduced. Hence, the basic methodology in IS is to choose a distribution which encourages the important values. This use of a “biased” distribution will, of course, result in a biased estimator if applied directly in the simulation. However, there is a simple procedure whereby the simulation outputs are weighted to correct for the use of the biased distribution, and this ensures that the new IS estimator is unbiased. Hence, the “art” of designing quick simulations via IS is entirely dependent on the choice of biased distribution. Over the last 50 years, IS techniques have flourished, but it is only in the last decade that coherent design methods have emerged. The outcome of these developments is that at the expense of increasing technical content, modern techniques can offer substantial run-time saving for a very broad range of problems. We present a comprehensive history and survey of IS methods. In addition, we offer a guide to the strengths and weaknesses of the techniques, and hence indicate which techniques are suitable for various types of communications systems. We stress that simple approaches can still yield useful savings, and so the simulation practitioner as well as the technical researcher should consider IS as a possible simulation tool     

Adaptive importance sampling for performance evaluation andparameter optimization of communication systems

We present new adaptive importance sampling techniques based on stochastic Newton recursions. Their applicability to the performance evaluation of communication systems is studied. Besides bit-error rate (BER) estimation, the techniques are used for system parameter optimization. Two system models that are analytically tractable are employed to demonstrate the validity of the techniques. As an application to situations that are analytically intractable and numerically intensive, the influence of crosstalk in a wavelength-division multiplexing (WDM) crossconnect is assessed. In order to consider a realistic system model, optimal setting of thresholds in the detector is carried out while estimating error rate performances. Resulting BER estimates indicate that the tolerable crosstalk levels are significantly higher than predicted in the literature. This finding has a strong impact on the design of WDM networks. Power penalties induced by the addition of channels can also be accurately predicted in short run-times     

Efficient and flexible location management techniques for wireless communication systems

We consider the problem of managing the information required to locate users in a wireless communication system, with a focus on designing and evaluating location management techniques that are efficient, scalable, and flexible. The three key contributions of this paper are: (1) a family of location management techniques, HiPER (for Hierarchical ProfilE Replication), that efficiently provide life‐long (non‐geographic) numbering with fast location lookup; (2) Pleiades, a scalable event‐driven wireless system simulator with realistic calling and mobility patterns derived from several months of real traffic traces; and (3) multi‐day simulations comparing our proposed location management techniques with current and previously proposed techniques on a realistic geographical and network topology. This revised version was published online in June 2006 with corrections to the Cover Date.     

Estimation variance bounds of importance sampling simulations indigital communication systems

In practical applications of importance sampling (IS) simulation, two basic problems are encountered, that of determining the estimation variance and that of evaluating the proper IS parameters needed in the simulations. The authors derive new upper and lower bounds on the estimation variance which are applicable to IS techniques. The upper bound is simple to evaluate and may be minimized by the proper selection of the IS parameter. Thus, lower and upper bounds on the improvement ratio of various IS techniques relative to the direct Monte Carlo simulation are also available. These bounds are shown to be useful and computationally simple to obtain. Based on the proposed technique, one can readily find practical suboptimum IS parameters. Numerical results indicate that these bounding techniques are useful for IS simulations of linear and nonlinear communication systems with intersymbol interference in which bit error rate and IS estimation variances cannot be obtained readily using prior techniques     

Some improvements to conventional importance sampling techniques for coded systems using Viterbi decoding

Importance sampling has been used to reduce simulation run-time. It is known that the effects of importance sampling can be reduced by system memory (e.g. systems employing a Viterbi decoder). Modifications to conventional importance sampling which give improvements for simulated Viterbi decoding are presented.<>     

Statistical optimization of dynamic importance sampling parametersfor efficient simulation of communication networks

Importance sampling (IS) is a powerful method for reducing simulation run times when estimating the probabilities of rare events in communication systems using Monte Carlo simulation and is made feasible and effective for the simulation of networks of queues by regenerative techniques. However, using the most favorable IS settings very often makes the length of regeneration cycles infinite or impractically long. To address this problem, a methodology that uses IS dynamically within each regeneration cycle to drive the system back to the regeneration state after an accurate estimate has been obtained is discussed. A statistically based technique for optimizing IS parameter values for simulations of queueing systems, including complex systems with bursty arrival processes, is formulated. A deterministic variant of stochastic simulated annealing (SA), called mean field annealing (MFA), is used to minimize statistical estimates of the IS estimator variance. The technique is demonstrated by evaluating blocking probabilities     

Software-synchronized all-optical sampling for fiber communication systems

This paper describes a software-synchronized all-optical sampling system that presents synchronous eye diagrams and data patterns as well as calculates accurate Q values without requiring clock recovery. A synchronization algorithm is presented that calculates the offset frequency between the data bit rate and the sampling rate, and as a result, synchronous eye diagrams can be presented. The algorithm is shown to be robust toward poor signal quality and adds less than 100-fs timing drift to the eye diagrams. An extension of the software synchronization algorithm makes it possible to automatically find the pattern length of a periodic data pattern in a data signal. As a result, individual pulses can be investigated and detrimental effects present on the data signal can be identified. Noise averaging can also be applied. To measure accurate Q values without clock recovery, a high sampling rate is required in order to establish the noise statistics of the measured signal before any timing drift occurs. This paper presents a system with a 100-MHz sampling rate that measures accurate Q values at bit rates as high as 160 Gb/s. The high bandwidth of the optical sampling system also contributes to sampling more noise, which in turn results in lower Q values compared with conventional electrical sampling with a lower bandwidth. A theory that estimates the optically sampled Q values as a function of the sampling gate width is proposed and experimentally verified.     

Bias point selection in the importance sampling Monte Carlo simulation of systems

We consider the issue of whether it is better to bias the random variables at the input, at the output, or at some intermediate point of a system. We show that in a very general setting, the closer to the output that we can bias our system simulation variables, the better off we will be. We show that surprisingly, in some important special cases, the performance can be equal no matter where the bias point is selected. In the second part of the paper, we present a very general large deviation-type theorem on the variance rates of importance sampling estimators. We then use this theorem to consider, in a quantitative fashion, what the difference in the variance rates can be for input versus output formulations. We present several examples illustrating the developed theory.     

Adaptive importance sampling [digital communication]

Parametric adaptive importance sampling (IS) algorithms that adapt the IS density to the system of interest during the course of the simulation are discussed. This approach removes the burden of selecting the IS density from the system designer. The performance of two such algorithms is investigated for both linear and nonlinear systems operating in Gaussian noise. In addition, the algorithms are shown to converge to the optimum improved importance sampling density for the special case of a linear system with Gaussian noise     

A composite importance sampling technique for digital communicationsystem simulation

A new composite importance sampling technique is presented and investigated. An exact analysis is used to optimize the sample size saving and to investigate its robustness with respect to threshold settings. The composite technique offers a sample size savings of ~2.5 compared to the translation technique of D. Lu and K. Yao (1988) for memoryless systems. Applications as well as some questions for further research are discussed     

Efficient techniques for the simulation of computer communicationsnetworks

The statistical nature of Monte Carlo techniques presents significant computational problems in the simulation of computer communications networks. A variety of techniques has been developed over the years to improve the computational efficiency of simulation models of general queuing networks, some of which have been applied to communication networks. The authors review the status of efficiency-enhancing techniques as they relate to the simulation of computer communications networks, present some novel approaches, and suggest promising areas for future research     

Efficient location area planning for personal communication systems

A central problem in personal communication systems is to optimize bandwidth usage, while providing Quality of Service (QoS) guarantees to mobile users. Network mobility management, and in particular, location management, consumes a significant portion of bandwidth, which is a necessary overhead for supporting mobile users. We focus our efforts on minimizing this overhead. Unlike previous works, we concentrate on optimizing existing schemes, and so the algorithms we present are easily incorporated into current networks. We present the first polynomial time approximation algorithms for minimum bandwidth location management. In planar graphs, our algorithm provably generates a solution that uses no more than a constant factor more bandwidth than the optimal solution. In general graphs, our algorithm provably generates a solution that uses just a factor O (log n) more bandwidth than optimal where n is the number of base stations in the network. We show that, in practice, our algorithm produces near-optimal results and outperforms other schemes that are described in the literature. For the important case of the line graph, we present a polynomial-time optimal algorithm. Finally, we illustrate that our algorithm can also be used for optimizing the handoff mechanism.     

Comparison of beamforming techniques for W-CDMA communication systems

Different beamforming techniques are employed in a wideband code-division multiple-access base station, and their uplink and downlink signal-to-interference-plus-noise ratio (SINR) performances are compared. It is found that the direction of arrival (DOA) method and the complex conjugate method have almost the same uplink SINR performance, but the complex conjugate method shifts the downlink main beam direction slightly due to the difference between the uplink and downlink carrier frequency. However, the degradation in the downlink mean SINR performance is less than 1 dB compared with that obtained by the DOA method. In the downlink, the SINR performances obtained by the single-beam method and multiple-beam beamforming technique are compared. It is found that the single-beam method has a poorer SINR performance in the low SINR region because it is more likely to suffer from deep fading. In the moderate or high SINR regions, the single-beam method has a much better SINR performance because it has a higher gain in the main path direction and a smaller angular coverage of the mainlobe, which results in a stronger signal level and smaller multiple-access interference at the mobile receiver.     

一种重要抽样仿真方法的研究及应用

介绍了蒙特-卡洛仿真原理,分析了改进型的蒙特-卡洛仿真即重要抽样(IS)的原理及其在通信中的应用,特别是在高速光纤通信的偏振模色散(PMD)仿真中的应用价值.实验证明,采用重要抽样的仿真方法可以得到大差分群时延(DGD)值的小概率事件,并且系统配置比用蒙特-卡洛的仿真方法简单得多.     

Efficient coding techniques for ADO-OFDM in IM/DD systems

Optical wireless communication (OWC) is an age-long technology, which is based on optical data transmission through free space, and it can be implemented in both indoor and outdoor applications. Asymmetrically clipped DC-biased optical orthogonal frequency division multiplexing (ADO-OFDM) is a modulation scheme that can be utilized in indoor OWC systems. It is based on transmitting DC-biased optical OFDM (DCO-OFDM) for even-frequency subcarriers and asymmetrically clipped optical OFDM (ACO-OFDM) for odd-frequency subcarriers. The ADO-OFDM exhibits better optical power performance than those of the conventional ACO-OFDM and DCO-OFDM. The main disadvantage of ADO-OFDM is the clipping noise, which mainly affects the even subcarriers. So, in this paper, convolutional and turbo coding techniques are investigated to improve the bit error rate performance of the ADO-OFDM over Additive white Gaussian noise and diffuse channels. Simulation results show that the proposed coded ADO-OFDM using convolutional and turbo coding techniques achieves significantly lower BERs compared to that of the uncoded ADO-OFDM. In addition, turbo-coded ADO-OFDM gives the best BER performance.     

Efficient dynamic authentication for mobile satellite communication systems without verification table

The mobile satellite system is an important wireless communication system widely used nowadays. The issue of protecting the transmission security in low‐earth‐orbit satellite networks thus becomes more and more critical. It is known that several authentication schemes for satellite communication systems have been proposed to deal with the issue. However, previous protocols either employ complicated public key computation or have to maintain a verification table. In this paper, the author will introduce a new dynamic authentication protocol for mobile satellite communication systems without using a verification table. The comparison results will also show that the proposed scheme has lower computational costs. Copyright © 2014 John Wiley & Sons, Ltd.     

An investigation of Gaussian tail and Rayleigh tail densityfunctions for importance sampling digital communication systemsimulation

The gains achieved by the use of importance sampling in communication system simulation are strongly influenced by the choice of the biased input noise distribution. The Rayleigh tail and the Gaussian tail distributions are investigated for use as biased distributions in importance sampling. The robustness of these schemes with respect to the estimate of the unknown error probability is examined. It is shown that the Gaussian tail distribution previously considered to be theoretically optimum is not optimum in this regard. Methods of generating the biased random variates are presented     

Adaptive importance sampling for fading channels

The authors present an adaptive importance sampling (AIS) technique for estimating the bit error rate of a communications system over a correlated Rayleigh channel. The technique reduces the computer simulation time significantly and simplifies the procedure of choosing an optimally-based density function of the channel fading process