Predictive Caching Strategy for On-Demand Routing Protocols in Wireless Ad Hoc Networks

Route caching strategy is important in on-demand routing protocols in wireless ad hoc networks. While high routing overhead usually has a significant performance impact in low bandwidth wireless networks, a good route caching strategy can reduce routing overheads by making use of the available route information more efficiently. In this paper, we first study the effects of two cache schemes, link cache and path cache, on the performance of on-demand routing protocols through simulations based on the Dynamic Source Routing (DSR) protocol. Since the path cache DSR has been extensively studied, we focus in this paper on the link cache DSR in combination with timer-based stale link expiry mechanisms. The effects of different link lifetime values on the performance of routing protocol in terms of routing overhead, packet delivery ratio and packet latency are investigated. A caching strategy incorporating adaptive link timeout is then proposed, which aims at tracking the optimal link lifetime under various node mobility levels by adaptively adjusting the link lifetime based on the real link lifetime statistics. The performance of the proposed strategy is then compared with the conventional path cache DSR. The results show that without a timeout mechanism, a link cache scheme may suffer severe performance degradation due to the use of broken routes, while the proposed adaptive link cache strategy achieves significantly improved performance by reducing the routing overhead when the network traffic load is high.     

Systematic Width-and-Length Dependent CMOS Transistor Mismatch Characterization and Simulation

This paper presents a methodology for characterizing the random component of transistor mismatch in CMOS technologies. The methodology is based on the design of a special purpose chip which allows automatic characterization of arrays of NMOS and PMOS transistors of different sizes. Up to 30 different transistor sizes were implemented in the same chip, with varying transistors width W and length L. A simple strong inversion large signal transistor model is considered, and a new five parameters MOS mismatch model is introduced. The current mismatch between two identical transistors is characterized by the mismatch in their respective current gain factors /, V _TO threshold voltages , bulk threshold parameters , and two components for the mobility degradation parameter mismatch ₀ and _e. These two components modulate the mismatch contribution differently, depending on whether the transistors are biased in ohmic or in saturation region. Using this five parameter mismatch model, an extraordinary fit between experimental and computed mismatch is obtained, including minimum length (1 m) transistors for both ohmic and saturation regions. Standard deviations for these five parameters are obtained as well as their respective correlation coefficients, and are fitted to two dimensional surfaces f(W, L) so that their values can be predicted as a function of transistor sizes. These functions are used in an electrical circuit simulator (Hspice) to predict transistor mismatch. Measured and simulated data are in excellent agreement.     

On the design of feedback controllers to achieve prescribed initial value constraints

The problem of designing a stabilizing compensator for a control system to achieve prescribed initial value constraints ⁽ⁱ⁾(0⁺)=y_i is considered. Indeed, modulo certain technical conditions, such a compensator exists if and only if y_i=0;i= 0,1,...,rp +rt –2; whererp is the relative degree of the plant andrt is the relative degree of the system input. This theorem is derived and a complete parameterization of the set of compensators that achieve the prescribed design constraints is formulated.This research was supported in part by NSF Grant No. 921106.     

The Satchel system architecture: Mobile access to documents and services

Mobile professionals require access to documents and documentrelated services, such as printing, wherever they may be. They may also wish to give documents to colleagues electronically, as easily as with paper, facetoface, and with similar security characteristics. The Satchel system provides such capabilities in the form of a mobile browser, implemented on a device that professional people would be likely to carry anyway, such as a pager or mobile phone. Printing may be performed on any Satchelenabled printer, or any fax machine. Scanning, too, may be accomplished at any Satchelenabled scanner. Access rights to individual documents may be safely distributed, without regard to document formats. Access to document services is greatly simplified by the use of context sensitivity. The system has been extensively tested and evaluated. This paper describes the architecture of the Satchel system.     

Design of High-Performance Wavelets for Image Coding Using a Perceptual Time Domain Criterion

This paper presents a new biorthogonal linear-phase wavelet design for image compression. Instead of calculating the prototype filters as spectral factors of a half-band filter, the design is based on the direct optimization of the lowpass analysis filter using an objective function directly related to a perceptual criterion for image compression. This function is defined as the product of the theoretical coding gain and an index called the peak-to-peak ratio, which was shown to have high correlation with perceptual quality. A distinctive feature of the proposed technique is a procedure by which, given a good starting filter, good filters of longer lengths are generated. The results are excellent, showing a clear improvement in perceptual image quality. Also, we devised a criterion for constraining the coefficients of the filters in order to design wavelets with minimum ringing.     

Synthesis of arbitrary digital transfer functions using allpass-based structures derived via LBR two-pair extraction procedure

The implementation of a digital filter transfer function with all transmission zeros on the unit circle is developed via the synthesis of an appropriate allpass function. The synthesis procedure is based on the LBR-extraction approach. The resulting structure is in the form of a doubly terminated cascade of lossless (LBR) two-pairs, with each two-pair realizing a single real or a pair of complex transmission zeros. The Concepts of complete and partial 1 removals, and 1 shifting are introduced and utilized during the synthesis process. The resulting structures have several properties in common with the Gray and Markel lattice filters, but do not require tap coefficients for numerator realization. The building blocks used in this paper are similar to those in certain wave-digital filters and orthogonal filters.Work supported in part by NSF Grant Number ECS 82-18310 and in part by NSF Grant Number ECS-8508017.     

A unified partitioning and scheduling scheme for mapping multi-stage regular iterative algorithms onto processor arrays

This paper addresses the partitioning and scheduling problems in mapping multi-stage regular iterative algorithms onto fixed size distributed memory processor arrays. We first propose a versatile partitioning model which provides a unified framework to integrate various partitioning schemes such as locally sequential globally parallel, locally parallel globally sequential and multi-projection. To alleviate the run time data migration overhead—a crucial problem to the mapping of multi-stage algorithms, we further relax the widely adopted atomic partitioning constraint in our model such that a more flexible partitioning scheme can be achieved. Based on this unified partitioning model, a novel hierarchical scheduling scheme which applies separate schedules at different processor hierarchies is then developed. The scheduling problem is then formulated into a set of ILP problem and solved by the existing software package for optimal solutions. Examples indicate that our partitioning model is a superset of the existing schemes and the proposed hierarchical scheduling scheme can outperform the conventional one-level linear schedule.     

Quality Determination for Gate Delay Fault Tests Considering Three-State Elements

Most industrial digital circuits contain three-state elements besides pure logic gates. This paper presents a gate delay fault simulator for combinational circuits that can handle three-state elements like bus drivers, transmission gates and pulled busses. The well known delay faults--slow-to-rise and slow-to-fall--are considered as well as delayed transitions from isolating signal state high impedance to binary states 0 and 1 and vice versa. The presented parallel delay fault simulator distinguishes between non-robust, robust and hazard free tests and determines the quality of a test. Experimental results for ISCAS85/89 benchmark circuits are presented as well as results for industrial circuits containing three-state elements.     

Performance evaluation of optimum combining and maximal ratio combining in the presence of co‐channel interference and channel correlation for wireless communication systems

Antenna diversity is an important technique to combat fading and reduce cochannel interference (CCI). In this paper, we present an analytical approach to derive bit error rate (BER) for Optimum Combining (OC) and Maximal Ratio Combining (MRC) in the presence of CCI. The paper has two parts. In the first part, the analysis of BER for OC with two cochannel interferers and MRC with an arbitrary number of interferers is presented for Marray antenna systems under the assumption that the channels of users are independent of each other. In the second part, the analysis of BER for OC and MRC in the presence of one dominant cochannel interferer is presented for dual antenna systems by assuming that the channels of the desired user or cochannel interferer are correlated. For DPSK signal, an exact BER expression is derived. The work presented here also yields an upper bound for BPSK or QAM signal based on the results of Foschini and Salz (1983).     

The dangers of simplistic delay models

The identification of sensitizable paths and the determination of path delays play key roles in many delay fault testing schemes. In this paper we examine a range of gate delay models with respect to their impact on identifying both sensitizable paths and maximum circuit delays in combinational logic circuits. We provide recommendations on the minimum acceptable model for identifying critical paths, and a minimum acceptable model for determining maximum circuit delays. In particular, we recommend against the use of delay models which fail to distinguish between rise and fall delays. Such models, including the commonly-used unit-delay model, are shown to significantly misrepresent circuit delay behaviour, particularly with respect to critical paths and long false paths.This research is supported by the Natural Sciences and Engineering Research Council of Canada.     

Building video‐on‐demand servers

We have designed and implemented a controllable software architecture for a VideoonDemand (VOD) server. With the proposed software architecture, many system design issues can be investigated. For example, we studied several disk striping schemes in the storage subsystem and examined the impact of the disk striping schemes on the utilization of system resources. In the processing component, we observed that additional concurrent video streams can be supported by using efficient memory interleaving. Buffering with a large memory space in the processing subsystem is a common technique to alleviate the latency variance of accessing different system components. By employing userlevel control and scheduling, the variance can be decreased thereby reducing the resulting buffer space needed for each video stream. In the network subsystem, we adopted a serverdriven approach for investigating MPEG2 video delivery over Asynchronous Transfer Mode (ATM) networks. The VOD server controls the pace of video transmission and reduces the complexity of the client. Since the client has limited buffer space (due to cost considerations), we have reduced the buffer requirement by regulating the transmission based on timing information embedded in the MPEG2 streams. Our research and experimental results are based on a VOD server which is currently under construction. The prototype server is based on an SGI sharedmemory multiprocessor with a mass storage system consisting of RAID3 disk arrays. Using 30 RAID3 disk arrays, preliminary experimental results show that the prototype server can potentially support more than 360 highquality video streams with careful design and coordination of the different system components.     

Time‐varying modeling of a nonstationary signal

In this paper, a method for modeling a nonstationary signal using timevarying parameters by considering that the signal is generated by a linear, timevarying (LTV) system with a stationary white noise input is presented. This method is based on the Wold–Cramer (WC) representation of a nonstationary signal. Because the relationship between the generalized transfer function of an LTV system and the timevarying coefficients of the difference equation of a discretetime system is not addressed so far in the literature, therefore, in this paper a solution to this problem is proposed. A simple relationship between the system generalized transfer function and the timevarying parameters of the system is derived, then an MLS algorithm is developed to solve for the system timevarying parameters. Computer simulation illustrating the effectiveness of our algorithm is presented.     

Recursive identification algorithms

Mechanisms for adapting models, filters, decisions, regulators, and so on to changing properties of a system or a signal are of fundamental importance in many modern signal processing and control algorithms. This contribution describes a basic foundation for developing and analyzing such algorithms. Special attention is paid to the rationale behind the different algorithms, thus distinguishing between optimal algorithms and ad hoc algorithms. We also outline the basic approaches to performance analysis of adaptive algorithms.     

A necessary and sufficient condition for right coprime factorization of nonlinear feedback systems

In this short note, we establish a simple, yet precise, necessary and sufficient condition for the right coprime factorization of a nonlinear feedback control system. As a consequence, we also obtain similar conditions for the stable right coprime factorizations of the nonlinear feedback control system.     

Immittance-type tabular stability test for 2-D LSI systems based on a zero location test for 1-D complex polynomials

A new algebraic test is developed to determine whether or not a two-variable (2-D) characteristic polynomial of a recursive linear shift invariant (LSI, discrete-time) system is stable (i.e., it does not vanish in the closed exterior of the unit bi-circle). The method is based on the original form of a unit-circle zero location test for one variable (1-D) polynomials with complex coefficients proposed by the author. The test requires the construction of a table, in the form of a sequence of centrosymmetric matrices or 2-D polynomials, that is obtained using a certain three-term recursion, and examination of the zero location with respect to the unit circle of a few associated 1-D polynomials. The minimal set necessary and sufficient conditions for 2-D stability involves one 1-D polynomial whose zeros must reside inside the unit circle (which may be examined before the table is constructed), and one symmetric 1-D polynomial (which becomes available after completing the table) that is required not to have zeros on the unit circle. A larger set of intermediate necessary conditions for stability (which may be examined during the table's construction) are also given. The test compares favorably with Jury's recently improved 2-D stability test in terms of complexity and munerical stability.     

Noise considerations for mixed‐signal RF IC transceivers

This paper discusses design tradeoffs for mixedsignal radio frequency integrated circuit (RF IC) transceivers for wireless applications in terms of noise, signal power, receiver linearity, and gain. During air wave transmission, the signal is corrupted by channel noise, adjacent interfering users, image signals, and multipath fading. Furthermore, the receiver corrupts the incoming signal due to RF circuit nonlinearity (intermodulation), electronic device noise, and digital switching noise. This tutorial paper gives an overview of the design tradeoffs needed to minimize RF noise in an integrated wireless transceiver. Fundamental device noise and the coupling of switching noise from digital circuits to sensitive analog sections and their impact on RF circuits such as frequency synthesizers are examined. Methods to minimize mixedsignal noise coupling and to model substrate noise effects are presented.     

Distance of a complex coefficient stable polynomial from the boundary of the stability set

In this paper, the distance in the 1 2p norm from a complex coefficient polynomial to the border of its Hurwitz region is analyzed. Simplified expressions for 2p=1, 2, are also obtained.This work was supported in part by Comisión Investigaciones Cientificas de la Provincia de Buenos Aires (CIC) and Comisión Nacional de Investigaciones Cientificas y Técnicas (CONICET).     

β-bit serial/parallel multipliers

A generalized -bit least-significant-digit (LSD) first, serial/parallel multiplier architecture is presented with 1n wheren is the operand size. The multiplier processes both the serial input operand and the double precision product -bits per clock cycle in an LSD first, synchronous fashion. The complete two's complement double precision product requires 2n/ clock cycles. This generalized architecture creates a continuum of multipliers between traditional bit-serial/parallel multipliers (=1) and fully-parallel multipliers (=n). -bit serial/parallel multipliers allow anoptimized integrated circuit arithmetic to be designed based on a particular application's area, power, throughput, latency, and numerical precision constraints.This project was pratically funded by the UCSD-NSF I/UCR Center on Ultra-High Speed Intergrated Circuits and Systems.     

Mobile ATM buffer capacity analysis

This paper extends a stochastic theory for buffer fill distribution for multiple on and off sources to a mobile environment. Queue fill distribution is described by a set of differential equations assuming sources alternate asynchronously between exponentially distributed periods in on and off states. This paper includes the probabilities that mobile sources have links to a given queue. The sources represent mobile user nodes, and the queue represents the capacity of a switch. This paper presents a method of analysis which uses mobile parameters such as speed, call rates per unit area, cell area, and call duration and determines queue fill distribution at the ATM cell level. The analytic results are compared with simulation results.This paper is partially funded by ARPA contract number J-FBI-94-223.The Mathematica code for this paper can be found on http://www.tisl.ukans.edu/sbush.     

Gaussian radial basis functions and inner product spaces

An approximation result is given concerning Gaussian radial basis functions in a general inner product space. Applications are described concerning the classification of the elements of disjoint sets of signals, and also the approximation of continuous real functions defined on all of ⁿ using radial basis function (RBF) networks. More specifically, it is shown that an important large class of classification problems involving signals can be solved using a structure consisting of only a generalized RBF network followed by a quantizer. It is also shown that Gaussian radial basis functions defined on ⁿ can uniformly approximate arbitrarily well over all of ⁿ any continuous real functionalf on ⁿ that meets the condition that |f(x)|0 as x.