Optimizing Delay in Sequential Change Detection on Ad Hoc Wireless Sensor Networks

We consider the classical problem of sequential detection of change in a distribution (from hypothesis 0 to hypothesis 1), where the fusion centre receives vectors of periodic measurements, with the measurements being i.i.d. over time and across the vector components, under each of the two hypotheses. In our problem, the sensor devices ("motes") that generate the measurements constitute an ad hoc wireless network. The motes contend using a random access protocol (such as CSMA/CA) to transmit their measurement packets to the fusion centre. The fusion centre waits for vectors of measurements to accumulate before taking decisions. We formulate the optimal detection problem, taking into account the network delay experienced by the vectors of measurements, and find that, under periodic sampling, the detection delay decouples into network delay and decision delay. We obtain a lower bound on the network delay, and propose a censoring scheme, where lagging sensors drop their delayed observations in order to mitigate network delay. We show that this scheme can achieve the lower bound. This approach is explored via simulation. We also use numerical evaluation and simulation to study issues such as: the optimal sampling rate for a given number of sensors, and the optimal number of sensors for a given measurement rate

Distributed load adaptive scheduling for throughput and delay guarantees in fading wireless LANs

We consider a problem of providing mean delay and average throughput guarantees in random access fading wireless channels using CSMA/CA algorithm. This problem becomes much more challenging when the scheduling is distributed as is the case in a typical local area wireless network. We model the CSMA network using a novel queueing network based approach. The optimal throughput per device and throughput optimal policy in an M device network is obtained. We provide a simple contention control algorithm that adapts the attempt probability based on the network load and obtain bounds for the packet transmission delay. The information we make use of is the number of devices in the network and the queue length (delayed) at each device. The proposed algorithms stay within the requirements of the IEEE 802.11 standard.

Voltage and Temperature-Aware SSTA Using Neural Network Delay Model

With the emergence of voltage scaling as one of the most powerful power reduction techniques, it has been important to support voltage scalable statistical static timing analysis (SSTA) in deep submicrometer process nodes. In this paper, we propose a single delay model of logic gate using neural network which comprehensively captures process, voltage, and temperature variation along with input slew and output load. The number of simulation programs with integrated circuit emphasis (SPICE) required to create this model over a large voltage and temperature range is found to be modest and 4x less than that required for a conventional table-based approach with comparable accuracy. We show how the model can be used to derive sensitivities required for linear SSTA for an arbitrary voltage and temperature. Our experimentation on ISCAS 85 benchmarks across a voltage range of 0.9-1.1V shows that the average error in mean delay is less than 1.08% and average error in standard deviation is less than 2.85%. The errors in predicting the 99% and 1% probability point are 1.31% and 1%, respectively, with respect to SPICE. The two potential applications of voltage-aware SSTA have been presented, i.e., one for improving the accuracy of timing analysis by considering instance-specific voltage drops in power grids and the other for determining optimum supply voltage for target yield for dynamic voltage scaling applications.

Modeling of the Effects of Process Variations on Circuit Delay at 65nm

A novel methodology for modeling the effects of process variations on circuit delay performance is proposed by relating the variations in process parameters to variations in delay metric of a complex digital circuit. The delay of a 2-input NAND gate with 65nm gate length transistors is extensively characterized by mixed-mode simulations which is then used as a library element. The variation in saturation current Ionat the device level, and the variation in rising/falling edge stage delay for the NAND gate at the circuit level, are taken as performance metrics. A 4-bit x 4-bit Wallace tree multiplier circuit is used as a representative combinational circuit to demonstrate the proposed methodology. The variation in the multiplier delay is characterized, to obtain delay distributions, by an extensive Monte Carlo analysis. An analytical model based on CV/I metric is proposed, to extend this methodology for a generic technology library with a variety of library elements.

Stability of control systems with time delay

To find the approximate stability limit on the forward gain in control systems with small time delay, this note suggests approximating the exponential in the characteristic equation by the first few terms of its series and using the Routh–Hurwitz criterion. This approximation avoids all the time-consuming graphical work and gives a somewhat pessimistic maximum bound for the gain constant.

Time delay to firing of a triggered vacuum gap with barium titanate in trigger gap

The time delay to the firing of a triggered vacuum gap (t.v.g.) containing barium titanate in the trigger gap is investigated as a function of the main gap voltage, main gap length, trigger pulse duration, trigger current and trigger voltage. The time delay decreases steadily with increasing trigger current and trigger voltage until it reaches saturation. The effect of varying the main gap length and voltage on the time delay is not strong. Before `conditioning�¿ the t.v.g. two groups of time delays, long (>100�¿s) and short (<10�¿s), are simultaneously observed when a large number of trials are conducted. After conditioning, only the group of short time delays are present. This is attributed to the marked reduction of the resistance of the trigger gap across the surface of the solid dielectric resulting directly from the conditioning effect.

Low-Delay, High-Rate Nonsquare Complex Orthogonal Designs

The maximal rate of a nonsquare complex orthogonal design for transmit antennas is 1/2 + 1/n if is even and 1/2 + 1/n+1 if is odd and the codes have been constructed for all by Liang (2003) and Lu et al. (2005) to achieve this rate. A lower bound on the decoding delay of maximal-rate complex orthogonal designs has been obtained by Adams et al. (2007) and it is observed that Liang's construction achieves the bound on delay for equal to 1 and 3 modulo 4 while Lu et al.'s construction achieves the bound for n = 0, 1, 3 mod 4. For n = 2 mod 4, Adams et al. (2010) have shown that the minimal decoding delay is twice the lower bound, in which case, both Liang's and Lu et al.'s construction achieve the minimum decoding delay. For large value of, it is observed that the rate is close to half and the decoding delay is very large. A class of rate-1/2 codes with low decoding delay for all has been constructed by Tarokh et al. (1999). In this paper, another class of rate-1/2 codes is constructed for all in which case the decoding delay is half the decoding delay of the rate-1/2 codes given by Tarokh et al. This is achieved by giving first a general construction of square real orthogonal designs which includes as special cases the well-known constructions of Adams, Lax, and Phillips and the construction of Geramita and Pullman, and then making use of it to obtain the desired rate-1/2 codes. For the case of nine transmit antennas, the proposed rate-1/2 code is shown to be of minimal delay. The proposed construction results in designs with zero entries which may have high peak-to-average power ratio and it is shown that by appropriate postmultiplication, a design with no zero entry can be obtained with no change in the code parameters.

Delay Optimal Event Detection on Ad Hoc Wireless Sensor Networks

We consider a small extent sensor network for event detection, in which nodes periodically take samples and then contend over a random access network to transmit their measurement packets to the fusion center. We consider two procedures at the fusion center for processing the measurements. The Bayesian setting, is assumed, that is, the fusion center has a prior distribution on the change time. In the first procedure, the decision algorithm at the fusion center is network-oblivious and makes a decision only when a complete vector of measurements taken at a sampling instant is available. In the second procedure, the decision algorithm at the fusion center is network-aware and processes measurements as they arrive, but in a time-causal order. In this case, the decision statistic depends on the network delays, whereas in the network-oblivious case, the decision statistic does not. This yields a Bayesian change-detection problem with a trade-off between the random network delay and the decision delay that is, a higher sampling rate reduces the decision delay but increases the random access delay. Under periodic sampling, in the network-oblivious case, the structure of the optimal stopping rule is the same as that without the network, and the optimal change detection delay decouples into the network delay and the optimal decision delay without the network. In the network-aware case, the optimal stopping problem is analyzed as a partially observable Markov decision process, in which the states of the queues and delays in the network need to be maintained. A sufficient decision statistic is the network state and the posterior probability of change having occurred, given the measurements received and the state of the network. The optimal regimes are studied using simulation.

An Accurate Fractional Period Delay Generation System

An all-digital technique is proposed for generating an accurate delay irrespective of the inaccuracies of a controllable delay line. A subsampling technique-based delay measurement unit (DMU) capable of measuring delays accurately for the full period range is used as the feedback element to build accurate fractional period delays based on input digital control bits. The proposed delay generation system periodically measures and corrects the error and maintains it at the minimum value without requiring any special calibration phase. Up to 40x improvement in accuracy is demonstrated for a commercial programmable delay generator chip. The time-precision trade-off feature of the DMU is utilized to reduce the locking time. Loop dynamics are adjusted to stabilize the delay after the minimum error is achieved, thus avoiding additional jitter. Measurement results from a high-end oscilloscope also validate the effectiveness of the proposed system in improving accuracy.

Frequency domain turbo equalization for MIMO-CPSC systems with large delay spreads

In this paper, we consider low-complexity turbo equalization for multiple-input multiple-output (MIMO) cyclic prefixed single carrier (CPSC) systems in MIMO inter-symbol interference (ISI) channels characterized by large delay spreads. A low-complexity graph based equalization is carried out in the frequency domain. Because of the reduction in correlation among the noise samples that happens for large frame sizes and delay spreads in frequency domain processing, improved performance compared to time domain processing is shown to be achieved. This improved performance is attractive for equalization in severely delay spread ISI channels like ultrawideband channels and underwater acoustic channels.

Design and analysis of integrated optic waveguide delay line for beamforming applications

This paper presents a new approach for Optical Beam steering using 1-D linear arrays of curved wave guides as delay line. The basic structure for generating delay is the curved/bent waveguide and hence its Analytical modelling involves evaluation of mode profiles, propagation constants and losses become important. This was done by solving the dispersion equation of a bent waveguide with specific refractive index profiles. The phase shifts due to S-bends are obtained and results are compared with theoretical values. Simulations in 2-D are done using BPM and Matlab.

Design of S bend waveguides for delay line applications in integrated optics

A novel scheme for generation of phase using optical delay lines is proposed. The design of the optical components in the circuit which includes the S bend waveguides and straight waveguide couplers are very important for integrated optics. Beam propagation Method and MatLab is employed for the design.

Queueing delay - error probability tradeoff for point-to-point channels with fixed length block codes

We study the tradeoff between the average error probability and the average queueing delay of messages which randomly arrive to the transmitter of a point-to-point discrete memoryless channel that uses variable rate fixed codeword length random coding. Bounds to the exponential decay rate of the average error probability with average queueing delay in the regime of large average delay are obtained. Upper and lower bounds to the optimal average delay for a given average error probability constraint are presented. We then formulate a constrained Markov decision problem for characterizing the rate of transmission as a function of queue size given an average error probability constraint. Using a Lagrange multiplier the constrained Markov decision problem is then converted to a problem of minimizing the average cost for a Markov decision problem. A simple heuristic policy is proposed which approximately achieves the optimal average cost.

Optimal forwarding in delay tolerant networks with multiple destinations

We study the trade-off between delivery delay and energy consumption in a delay tolerant network in which a message (or a file) has to be delivered to each of several destinations by epidemic relaying. In addition to the destinations, there are several other nodes in the network that can assist in relaying the message. We first assume that, at every instant, all the nodes know the number of relays carrying the packet and the number of destinations that have received the packet. We formulate the problem as a controlled continuous time Markov chain and derive the optimal closed loop control (i.e., forwarding policy). However, in practice, the intermittent connectivity in the network implies that the nodes may not have the required perfect knowledge of the system state. To address this issue, we obtain an ODE (i.e., fluid) approximation for the optimally controlled Markov chain. This fluid approximation also yields an asymptotically optimal open loop policy. Finally, we evaluate the performance of the deterministic policy over finite networks. Numerical results show that this policy performs close to the optimal closed loop policy.