The vehicle routing problem is a classical combinatorial optimization problem. This work is about a variant of the vehicle routing problem with dynamically changing orders and time windows. In real-world applications often the demands change during operation time. New orders occur and others are canceled. In this case new schedules need to be generated on-the-fly. Online optimization algorithms for dynamical vehicle routing address this problem but so far they do not consider time windows. Moreover, to match the scenarios found in real-world problems adaptations of benchmarks are required. In this paper, a practical problem is modeled based on the procedure of daily routing of a delivery company. New orders by customers are introduced dynamically during the working day and need to be integrated into the schedule. A multiple ant colony algorithm combined with powerful local search procedures is proposed to solve the dynamic vehicle routing problem with time windows. The performance is tested on a new benchmark based on simulations of a working day. The problems are taken from Solomon's benchmarks but a certain percentage of the orders are only revealed to the algorithm during operation time. Different versions of the MACS algorithm are tested and a high performing variant is identified. Finally, the algorithm is tested in situ: In a field study, the algorithm schedules a fleet of cars for a surveillance company. We compare the performance of the algorithm to that of the procedure used by the company and we summarize insights gained from the implementation of the real-world study. The results show that the multiple ant colony algorithm can get a much better solution on the academic benchmark problem and also can be integrated in a real-world environment.

We present the problem of estimating cortical connectivity between different regions of the cortex from scalp electroencephalographic (EEG) or magnetoencephalographic (MEG) data as system identification of a nonlinear state-space model. The state equation is based on a nonlinear multivariate autoregressive (MVAR) model with radial basis function (RBF) kernels. The RBF kernels capture the nonlinear dynamics of the cortical signals and provide a framework for measuring interactions between cortical regions of interest (ROIs) based on the definition of Granger causality. The observation equation relates the cortical signals associated with each ROI to the observed E/MEG data using a set of parsimonious spatial bases to represent spatially extended cortical sources. An expectation-maximization (EM) algorithm is derived to obtain maximum likelihood (ML) estimates of the nonlinear state-space model parameters directly from the observed data. We show that this integrated approach for measuring cortical connectivity performs significantly better than the conventional decoupled approach in which cortical signals are first estimated by solving the inverse problem followed by fitting a MVAR model.

Breast imaging via microwave tomography involves estimating the distribution of dielectric properties within the patient's breast on a discrete mesh. The number of unknowns in the discrete mesh can be very large for 3-D imaging, and this results in computational challenges. We propose a new approach where the discrete mesh is replaced with a relatively small number of smooth basis functions. The dimension of the tomography problem is reduced by estimating the coefficients of the basis functions instead of the dielectric properties at each element in the discrete mesh. The basis functions are constructed using knowledge of the location of the breast surface. The number of functions used in the basis can be varied to balance resolution and computational complexity. The reduced dimension of the inverse problem enables application of a computationally efficient, multiple-frequency inverse scattering algorithm in 3-D. The efficacy of the proposed approach is verified using two 3-D anatomically realistic numerical breast phantoms. It is shown for the case of single-frequency microwave tomography that the imaging accuracy is comparable to that obtained when the original discrete mesh is used, despite the reduction of the dimension of the inverse problem. Results are also shown for a multiple-frequency algorithm where it is computationally challenging to use the original discrete mesh.

A distributed scheduling approach to multi-user beamforming at a base-station (BS) is proposed. The scheme assumes the BS is equipped with multiple antennas and uses zero-forcing beamforming to schedule multiple users on the same time-frequency uplink/downlink channels. The optimal user set that the BS can schedule is the one that maximizes the sum-rate for the communication channel. The computational complexity of finding the optimal user set becomes intractable as the number of users exceeds 20-30. Sub-optimal schemes for maximizing the sum-rate generally require large control overhead. We propose an effective sum-rate performance metric that accounts for the control overhead required by the scheduling method. We also propose a user scheduling method that has both low complexity and low overhead. The complexity and overhead are reduced by adding one user at a time and distributing the computation of the scheduling problem across the users. Each user calculates the sum-rate that would result if they were added to the existing user set using their own channel and knowledge of the channels of existing users that is broadcast by the BS. The user with greatest sum-rate increase is scheduled. We use simulations to show that this approach can achieve significantly higher effective sum rates than previously proposed sub-optimal schemes. We also derive an approximate expression for the expected sum-rate with our distributed scheduling method and demonstrate its accuracy with simulations.

Efficient medium access control in wireless networks has been a challenging task. While the IEEE 802.11 standard coordinates contention effectively, it severely limits the number of concurrent communications. This results in reduced throughput and efficiency. Recent research has focused on employing multiple antennas to increase throughput in a multipath environment by enabling multiple streams between a transmit-receive pair. In this paper we show that exploiting multiuser diversity to enable concurrent communications has certain advantages over multiple streaming. We propose a medium access control (MAC) protocol that uses adaptive interference cancellation with multiple antennas to increase network throughput and to provide better fairness, while requiring minimal change to the widely-deployed 802.11 MAC structure

In this paper we propose a joint reduced-state sequence detector (JRSSD) for a multiple-input multiple-output (MIMO) system. The proposed JRSSD incorporates the set-partitioning principle to obtain a reduced-state trellis and is the space-time extension of the RSSD proposed in for a single-input single-output (SISO) equalization problem. We show that two elements are essential in achieving the desired complexity and performance tradeoff for the proposed JRSSD algorithm: 1) a proper multisymbol set-partition and 2) an efficient space-time structure that effectively decouples the spatial and temporal processing. We propose a simple multisymbol uniform set-partition (USP) that retains certain geometric symmetry in the partitioned subsets. We also develop two suboptimal algorithms, namely the decorrelating (DC) and ordered successive (OS) algorithms, to decouple the spatial multisymbol detection problem inherent in the processing of parallel transitions, into single-symbol detection problems. The symmetry in USP, together with the DC or OS algorithm, guarantees efficient processing of parallel transitions and leads to a low-complexity JRSSD. Furthermore, numerical simulations show that the performance of JRSSD is near that of the more complex delayed decision feedback sequence estimator (DDFSE).

A medium access control (MAC) protocol for ad hoc networks of nodes with antenna arrays is presented. The antenna array is used for transmit and receive beamforming with the purpose of increasing spatial reuse by directing nulls at active transmitters and receivers in the neighborhood. In contrast to previous work with directional antennas, our approach is applicable to flat fading multipath channels, such as in indoor or in other rich scattering environments. The MAC protocol is designed to support the control information exchange needed to direct nulls toward other users involved in existing communication sessions. Knowledge of the channel coefficients between a transmitter or receiver and its neighbors is used to design transmit or receive beamformer weights that implement the requisite nulling. Simulations are used to demonstrate the improvements in throughput and transmit powers that are obtained in this approach relative to the conventional IEEE 802.11 MAC protocol.

Selective broadcast schemes for point-to-multiple point transmission of identical information to several selected users are studied for a code-division multiple-access wireless system. The channel states for all selected users are assumed known at both the transmitter and the receivers. The goal is to minimize total transmit power while satisfying minimum received signal-to-noise ratio (SNR) requirements. Three designs, namely, time-only, space-time and space-only, are investigated. In the time-only design no spatial diversity is available, and we solve the optimal transmit signature code by developing iterative least distance programming (ILDP) and linear programming (LP) algorithms. In the space-time design, transmit antennas are exploited in addition to the temporal dimension, and we show the ILDP algorithm is still applicable. The LP algorithm can also be adapted with the integration of space-time block codes, which we term the space-time block coding LP (STC-LP) algorithm. In the space-only design, only the spatial dimension is available and we study the optimization of the transmit antenna weights to satisfy the users' SNR requirements. We show that the STC-LP algorithm applies in this case. We also propose an iterative spatial diagonalization algorithm to explore the unique structure of the space-only problem.

Selective broadcast schemes for point-to-multiple point transmission of identical information are studied for a CDMA wireless system. The channel states for all selected users are assumed known at both the transmitter and the receivers. The goal is to find signaling schemes that satisfy the received SNR requirement at all desired users while minimizing total transmit power. We solve for the optimal transmit signature code and receive filters by developing Iterative Least Distance Programming (ILDP) and Linear Programming (LP) algorithms. We show that the optimal selective broadcast scheme is more power efficient than simple broadcast schemes and is robust against modest channel estimate delays.

A backscatter-based microwave imaging technique that compensates for frequency-dependent propagation effects is proposed for detecting early-stage breast cancer. An array of antennas is located near the surface of the breast and an ultrawideband pulse is transmitted sequentially from each antenna. The received backscattered signals are passed through a space-time beamformer that is designed to image backscattered signal energy as a function of location. As a consequence of the significant dielectric-properties contrast between normal and malignant tissue, locations corresponding to malignant tumors are associated with large energy levels in the image. The effectiveness of these algorithms is demonstrated using simulated backscattered signals obtained from an anatomically realistic MRI-derived computational electromagnetic breast model. Very small (2 mm) malignant tumors embedded within the complex fibroglandular structure of the breast are easily detected above the background clutter.

We propose a low complexity receiver structure for a multiple transmit antenna, multiple receive antenna (MIMO) system in the EDGE environment. In such a MIMO system, independent data streams are transmitted through different transmit antennas. In the proposed low complexity receiver structure, these data streams are separated and detected individually. The signal separation at the receiver is performed by the space-time interference cancellation filters. Each filter has a target data stream and intends to maximize the signal to interference and noise ratio (SINR) of that target data stream. Each filter is followed by a prefilter and a decision feedback sequence estimator (DFSE) which includes a feedback filter and a MAP sequence estimator. The maximum SINR (MSINR) interference cancellation comes in two flavors: blind and explicit methods. The blind MSINR method was first proposed in Liang et al. (1997) as a two-stage co-channel interference (CCI) suppression method with multiple receive antennas. We show that the blind MSINR method can be directly applied in the MIMO context and also derive another variation of the MSINR method, which we term the explicit MSINR method. While both methods achieve decent performance at low complexity, the explicit method utilizes the knowledge of all the training sequences and performs better than the blind method.

Optimal multi-antenna wide-band signaling schemes are derived for multipath channels assuming perfect channel state information at the transmitter. The scheme that minimizes the bit-error probability in the single-user case is a rank-one space-time beamformer which focuses the signal transmission in the direction of the most dominant channel mode. Several suboptimal variations are discussed for multiuser applications. The optimal signaling scheme given channel statistics at the transmitter is also derived. The optimal scheme in this case is a full-rank space-time beamformer that transmits on all channel modes. Analysis and simulation results are used to compare the schemes proposed in this paper. Finally, we discuss the optimal signaling scheme when a delayed version of the channel state is available at the transmitter. It is shown that in this case the optimal scheme is a rank-1 beamformer when the channel variations are sufficiently slow and is a full rank beamformer in a sufficiently fast fading channel.

We propose a decentralized space-time multiuser detection scheme based on the notion of canonical space-time coordinates (CSTCs) for representing the received signal. The CSTC representation provides a natural framework for decentralized multi-access interference (MAI) suppression in lower dimensional subspaces that results in complexity reduction relative to existing chip rate filtering schemes. The framework is based on a partitioning of the signal space into active and inactive CSTCs. The active CSTCs contain the signal of the desired user, facilitate maximal diversity exploitation and minimal complexity interference suppression. The inactive CSTCs only contain MAI and can be included progressively to attain a desired level of MAI suppression at the cost of increased complexity. We develop CSTC-based linear coherent multiuser detectors using the linearly constrained minimum variance (LCMV) criterion. We characterize the set of inactive coordinates and analyze the performance of the LCMV receiver as a function of the number of inactive CSTCs. Channel estimation and detector sensitivity to channel estimation errors are discussed. We demonstrate that the low-complexity adaptive receivers designed via the CSTC framework are more robust to channel estimation errors than existing chip-domain filtering schemes.

An orthogonal decomposition of a general wideband space-time multipath channel is derived assuming antenna arrays at both the transmitter and receiver. This decomposition provides a framework for efficiently managing the available space-time channel dimensions using channel state information at the transmitter and receiver. Signaling and receiver designs for high-throughput applications are derived using this decomposition. For a fixed-throughput system, we investigate a power allocation scheme that minimizes the effective bit-error rate. In addition, a strategy to maximize the average throughput is discussed.

A spread-spectrum spatio-temporal signaling scheme based on electric field polarization is proposed. The information symbol is transmitted via two perpendicular transverse electric field components, each with a unique signature sequence. At the receiver, all three electric field components are measured. It is demonstrated that polarization signaling provides another degree of freedom for increasing spatial diversity to improve the performance of the wireless link.

The time scale over which a channel is observed determines whether a deterministic or statistical characterization is appropriate. We show that the channel estimation algorithm of Tsatsanis and Xu (see Proc. 31st Conf. Inform. Sci. Systems (CISS) John Hopkins Univ., Baltitmore, MD, p.724-29, 1997) and the acquisition algorithm of Sayeed and Aazhang (see Proc. 91st Conf. Inform. Sci. Systems (CISS) Princeton, NJ, 1998) share a common MMSE formulation. They differ only in the assumption of the channel characterization. From this observation we develop a new blind MMSE interference resistant algorithm for both timing acquisition and channel estimation that is applicable to both deterministic and statistical channel models. Simulations illustrate the effectiveness of the new method.

A canonical space-time characterization of mobile wireless channels is introduced in terms of a fixed basis that is independent of the true channel parameters The basis captures the essential degrees of freedom in the received signal using discrete multipath delays, Doppler shifts, and directions of arrival (DOA). The canonical representation provides a robust representation of the propagation dynamics and eliminates the need for estimating delay, Doppler and DOA parameters of different multipaths, Furthermore, it furnishes a natural framework for designing low-complexity space-time receivers. Single-user receivers based on the canonical channel representation are developed and analyzed, It is demonstrated that the resulting canonical space-time receivers deliver near-optimal performance at substantially reduced complexity compared to existing designs.

We propose a canonical space-time receiver structure for wireless communications based on front-end processing with respect to a fixed basis that is independent of the true channel parameters. The basis is dictated by a canonical characterization of channel propagation dynamics in terms of discrete multipath delays, Doppler shifts, and directions of arrival that capture the essential degrees of freedom in the received signal. In addition to dramatically reducing the number of channel parameters to be estimated, performance analysis demonstrates that canonical space-time receivers can deliver optimal performance at substantially reduced complexity compared to existing designs.

A design framework for space-time multiuser detectors is introduced based on the notion of canonical space-time coordinates (CSTC). The CSTC system employs a fixed set of basis signals which eliminates the need for estimating direction of arrivals (DOAs) and delays of the channel, thereby allowing significant reduction in receiver complexity. The proposed framework is based on a hybrid structure for multiuser detection which combines the power of centralized processing and the flexibility of decentralized reception. In the first stage, a subset of users whose spreading codes are assumed known are suppressed in a centralized fashion. The remaining interference is suppressed via the second stage in an adaptive decentralized mode. The hybrid scheme offers a flexible design framework by offering lower complexity compared to fully centralized receivers and improved adaptive performance compared to fully decentralized schemes.

A deterministic approach to blind nonlinear channel equalization and identification is presented. This approach applies to nonlinear channels that can be approximately linearized by finite memory, finite order Volterra filters. Both the Volterra equalizers and the linearized channels are identified. This method also applies to blind identification of linear IIR channels. General conditions for existence and uniqueness are discussed and numerical examples are given.

A distributed algorithm for MIMO adaptive filtering is introduced. This algorithm distributes the adaptive computation over a set of linearly connected computational modules. Each module transmits data to and receives data from its nearest neighbor. A back-propagation LMS based algorithm is presented for adapting the parameters in each module. The performance surface is explored to identify upper bounds on each parameter and guidelines for choosing the LMS algorithm step sizes. An example illustrates the application of the algorithm.

An active noise controller utilizing a transform domain recursive LMS (RLMS) infinite impulse response (IIR) filter is presented in this paper. The new filter, termed the TRLMS adaptive filter, mitigates the filter instability problems that often exist with controllers based on direct form IIR filters by directly constraining the adaptation of the filter's frequency response. A filtered-U adaptive algorithm for the TRLMS filter structure is derived. Two different implementations of the constrained TRLMS filter are discussed. The first represents the adaptive filter in terms of its transform domain weights. They are directly adapted by the filtered-U TRLMS adaptive algorithm. The second implementation represents the filter in terms of its original time domain weights. These are updated by the filtered-U RLMS algorithm and subsequently projected onto an adaptation subspace at each iteration. Extensions of these algorithms that enforce soft constraints on the filter response are also presented. The stability of the constrained TRLMS adaptive filter is investigated utilizing two different transformations.

Low rank estimators for higher order statistics are considered. Rank reduction methods offer a general principle for trading estimator bias for reduced estimator variance. The bias-variance tradeoff is analyzed for low rank estimators of higher order statistics using a tensor product formulation for the moments and cumulants. In general the low rank estimators have a larger bias and smaller variance than the corresponding full rank estimator. Often a tremendous reduction in variance is obtained in exchange for a slight increase in bias. This makes the low rank estimators extremely useful for signal processing algorithms based on sample estimates of the higher order statistics. The low rank estimators also offer considerable reductions in the computational complexity of such algorithms.

In active noise control (ANC) on air duct/fan systems it is desirable to achieve noise cancellation using the shortest possible duct length. A barrier to this goal is the presence of air turbulence at the duct input due to the fan driving the system. Turbulent pressure fluctuations contaminate measurement of the acoustic noise in the duct, resulting in degraded noise cancellation performance. We investigate the use of adaptive array processing techniques to suppress the effects of turbulence. Based upon the spatial correlation and temporal spectral characteristics of turbulence, we propose a hybrid generalized sidelobe canceller (GSC) which is constrained to adapt only in the frequency range where both acoustic noise and turbulent noise contribute correlated components to the multivariate input covariance. The effectiveness of this method is demonstrated using actual experimental data.

The robustness of a subspace generalized likelihood ratio test (GLRT) detector to signal mismatch is addressed for data conforming to the generalized multivariate analysis of the variance model. This model assumes a deterministic signal of known form in the presence of unknown, colored, Gaussian noise. The subspace GLRT compresses data into a lower-dimensional subspace prior to detection. It is shown that a subspace GLRT reduces the performance loss due to mismatch relative to that of a non-subspace detector.

To reduce the number of parameters in the Volterra filter a tensor product basis approximation is considered. The approximation can be implemented much more efficiently than the original Volterra filter. In addition, because the design methods are based on partial characterization of the Volterra filter, the approximations are also useful in reducing the complexity of identification and modelling problems. Useful bounds are obtained on the approximation error.

Signal detection using the generalized likelihood ratio test is examined for data obtained from an arbitrary array of vector sensors. Vector sensors are sensing devices that simultaneously measure all six time-dependent, electromagnetic field quantities at a point in space. A signal model is developed for a point narrowband source with unknown amplitude. The maximum likelihood estimator for the signal amplitude is derived in the presence of colored multivariate Gaussian noise. The detection test statistic and its probabilities of false alarm and detection are obtained in closed form. A non-adaptive transformation is derived that compresses a high dimensional detection problem into a two-dimensional detection problem with no signal loss.>

One of the major drawbacks of Volterra filters is the large number of parameters associated with such structures. In this paper, it is shown how the Volterra filter can be constrained to yield parsimonious filter structures that are adequately flexible for a large class of filtering problems. Frequency domain constraints on the Volterra kernel are one example. Constrained Volterra filters are also developed for filtering inputs with low rank covariance matrices. The performance of the constrained Volterra filter is studied theoretically and with simulation.>

The performance of subspace adaptive detection is examined for the generalized likelihood ratio detector of E.J. Kelly (1986) and Kelly and K.M. Forsythe (1989). The probability of false alarm (PFA) is independent of the subspace transformation, and depends only upon subspace dimension. The probability of detection depends upon the subspace transformation through a non-adaptive signal-to-noise ratio (SNR) parameter. Subspace processing results in an SNR loss that tends to decrease performance and a gain in statistical stability that tends to increase performance. It is shown that the statistical stability effect dominates the SNR loss for short data records and subspace detectors. A method for designing the subspace transformation to minimize the SNR loss is proposed and illustrated via simulations.>

The problem of adaptive beamforming in a coherent interference environment is addressed. A partially adaptive beamformer is proposed to present desired signal cancellation. The mean squared error at the beamformer output is shown to consist of a signal cancellation term associated with the presence of interferers coherent with the desired signal and an interference cancellation term. Both terms are functions of the degrees of freedom employed in the partially adaptive beamformer. Hence, the authors propose choosing the degrees of freedom to minimize the average mean squared error over a likely set of interference scenarios. An approximate solution to this optimization problem is described. Simulations are provided to illustrate the effectiveness of this approach.>

The modeling of the behavior of the external ear with a beamformer is proposed. The output of a beamformer is a weighted combination of the data received at any array of spatially distributed sensors. The beamformer weights and array geometry determine its spatial and temporal filtering characteristics. A least squares procedure for choosing the weights so the beamformer response approximates the measured response of the external ear is described. The effectiveness of this model is demonstrated by designing a beamformer of several hundred weights which duplicates and interpolates the measured external ear response of a cat over broad ranges of frequency and direction.>

A statistical analysis of the adaptive convergence behavior of linearly constrained beamformers is given assuming the sample covariance estimator is used to estimate the covariance matrix. The sensor data is assumed to be Gaussian distributed and independent from snapshot to snapshot. The mean squared error in the absence of the desired signal is shown to be a multiple of a chi-squared random variable. The presence of the desired signal results in an excess mean squared error which is Beta distributed and depends only on the signal power, number of snapshots, and number of adaptive degrees of freedom. The average excess mean squared error is directly proportional to the signal power and number of adaptive degrees of freedom and inversely proportional to the number of snapshots. These results provide clear motivation for partially adaptive beamforming.>

The problem of estimating the power received at an array of sensors as a function of direction for broadband environments is addressed. A multiple-window-based processing scheme is proposed to reduce the variance of the power estimates. The windows are data dependent, and are derived from a linearly constrained minimum variance (LCMV) criterion. Expressions are derived for the bias and variance of the multiple-window-based estimator assuming the array data covariance is estimated by the sample covariance matrix. Comparison of multiple window estimator variance to the single window LCMV estimator variance indicates that variance reduction is guaranteed and is bounded by the number of windows used. Simulations verify the analytical results and show that the multiple window method has about the same bias as the single window LCMV estimator. The variance reduction factor, pf, is observed to be in the range, 1/r>

The mean-squared error between the desired and actual response is constrained, resulting in a quadratic constraint on the weights. The constraint is purposely chosen to permit signal distortion with the goal of achieving improved interference cancellation, motivating the term 'soft constrained' beamforming. The soft constrained minimum variance (SCMV) philosophy represents a trade of bias (signal distortion) for reduced variance (interference power). A key result is a proof guaranteeing that under ideal conditions the signal-to-noise ratio (SNR) is a nondecreasing function of the bound on the mean squared response error. This implies that by allowing the signal distortion to increase the beamformer can provide much better interference cancellation, such that the SNR improves or remains constant. The potential SNR improvement resulting from the use of soft constraints is greatest for systems operating at broad bandwidths.>

A technique for designing partially adaptive beamformers by minimization of output interference power was previously derived using a rather complicated approximation. The author presents an alternate derivation which clearly illustrates the nature of the approximation. A block diagram explicitly shows the modified partially adaptive system implied by the design procedure. This interpretation facilitates understanding of the limitations imposed by the approximation and suggests an improved design method.>

Broadband partially adaptive beamformers are designed by determining a transformation which maps the fully adaptive weight space into a partially adaptive weight space so that the output interference power is minimized over a set of assumed interference scenarios. An analytic technique for designing the transformation is derived using an approximation to simplify the problem. Simulations illustrate the utility of the approach.