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.     

Biasing a differential pair in low-voltage analog circuits: a systematic approach

This paper deals with a systematic approach to the common mode and the differential mode biasing of a differential transistor pair. Four different variants will be shown, two of these variants show practical importance; a practical circuit of one of these variants turns out to be the traditional long-tailed pair. This variant is mainly suited, if the input signal operates at voltage level, whereas another variant has great advantages if operation at current level occurs. Besides, the latter variant turns out to be very favorable in circuits operating with a single low supply voltage. Two practical circuits based on this variant are given.     

Practical zero-knowledge proofs: Giving hints and using deficiencies

New zero-knowledge proofs are given for some number-theoretic problems. All of the problems are in NP, but the proofs given here are much more efficient than the previously known proofs. In addition, these proofs do not require the prover to be superpolynomial in power. A probabilistic polynomial-time prover with the appropriate trapdoor knowledge is sufficient. The proofs are perfect or statistical zero-knowledge in all cases except one.This research was supported in part by NSA Grant No. MDA904-88-H-2006.In this paper it will at times be convenient to think of the verifier as being named Vic, and the prover being named Peggy. Thus, he will refer to the verifier and she will refer to the prover.     

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.     

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.     

Economics of “design for test” to remain competitive in the 90s

This article emphasizes the criticality of maximizing value adders and minimizing the costs of design for test (DFT) in order to remain competitive in ASIC manufacturing in the 90s.     

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.     

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.     

Systems which possessg- andh- Representations

Examples are given concerning the range of applicability of recent representation results that provide a means of studying the input-output properties of nonlinear systems in terms of the familiar impulse-response concept, and which extend the concept of integral transformation to nonlinear maps. We show that such representations, which we call g- and h-representations, exist for important classes of systems governed by nonlinear integral equations. In particular, it is proved that a large class of maps that have Volterra series representations also have these representations.     

A reservation-based multicast (RBM) routing protocol for mobile networks: initial route construction phase

We propose a combined multicast routing, resource reservation and admission control protocol, termed Reservation-Based Multicast (RBM), that borrows the Rendezvous Point or Core concept from multicast routing algorithms proposed for the Internet, but which is intended for operation in mobile networks and routes hierarchically-encoded data streams based on user-specified fidelity requirements, real-time delivery thresholds and prevailing network bandwidth constraints. The protocol exhibits the fully distributed operation and receiver-initiated orientation of these proposed algorithms; but, unlike them, the protocol is tightly coupled to a class of underlying, distributed, unicast routing protocols thereby facilitating operation in a dynamic topology. This paper focuses on the initial route construction phase, assumed to occur during a static snapshot of the dynamic topology, and is therefore applicable to fixed networks as well, e.g. the Internet.This work was sponsored by the U.S. Navy and the American Society for Engineering Education under the U.S. Navy's Summer Faculty Research Program.Each application must specify a mechanism for ensuring that a processor is always aware of its associated entities. For example, in the current Internet architecture, a group membership protocol [2] serves a similar function of keeping routers informed of the membership their directly attached subnetworks.A processor can be viewed as either an IP router or an ATM switch.     

Analog Switches in Programmable Analog Devices: Quiescent Defective Behaviours

Analog Switches (AS) play an essential role in a large number of Mixed-Signal circuits. Depending on the use of AS, designers have optimised their topology to meet the needs of each specific switching function. Furthermore, the success of Field Programmable devices in the digital domain (FPGAs) has motivated some manufacturers to explore similar solutions to fast prototype in the Analog and Mixed Signal domains. In this work, we explore the defective behaviours of programmable AS under realistic catastrophic and parametric defects. A classification of the DC defective behaviours for bridging and open defects is presented. This classification shows that the simple fault model with faulty state of permanently transistor stuck-on or stuck-off is not sufficient to reflect the real behaviour of a defective switch. It has also been found that parametric defects such as threshold voltage variations are not DC testable, and would therefore require additional AC tests.     

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.     

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.     

The CAM-Brain Machine (CBM): Real Time Evolution and Update of a 75 Million Neuron FPGA-Based Artificial Brain

This article introduces ATR's CAM-Brain Machine (CBM), an FPGA based piece of hardware which implements a genetic algorithm (GA) to evolve a cellular automata (CA) based neural network circuit module, of approximately 1,000 neurons, in about a second, i.e. a complete run of a GA, with 10,000 s of circuit growths and performance evaluations. Up to 65,000 of these modules, each of which is evolved with a humanly specified function, can be downloaded into a large RAM space, and interconnected according to humanly specified artificial brain architectures. This RAM, containing an artificial brain with up to 75 million neurons, is then updated by the CBM at a rate of 130 billion CA cells per second. Such speeds should enable real time control of robots and hopefully the birth of a new research field that we call brain building. The first such artificial brain, to be built by ATR starting in 2000, will be used to control the behaviors of a life sized robot kitten called Robokoneko.     

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.     

The Complex Bootstrap Algorithm for Blind Separation of QAM Multiuser CDMA Signals

The bootstrap separator for multiuser signals is principally composed of cancelers, each one using the output of the other cancelers to facilitate control of its adaptive weight. In fact, such a structure performs as a signal separator rather than an interference canceler. Since for its separation there is no need for a reference signal (as in LMS cancelers), it is sometimes justifiably called a Blind Separator. However, for its operation the bootstrap separator requires a signal distinguisher termed discriminator. The algorithm was used in the past in applications such as dually polarized satellite communications and microwave terrestrial links. It was particularly reported for multiuser CDMA signal separating, with the signum function as discriminator. Especially for QAM signals, complex presentation is important. Therefore, we will concentrate in this report on what we call the Complex Bootstrap Algorithm. It is an extension to the previously reported bootstrap structure of [5]. We will examine its performance and emphasize the hardware saving in its implementation, and the ease of using it in simulation.     

BlueStar: Enabling Efficient Integration Between Bluetooth WPANs and IEEE 802.11 WLANs

Bluetooth is a radio technology for Wireless Personal Area Networking (WPAN) operating in the 2.4 GHz ISM frequency band. So far, there has been little research on how Bluetooth-enabled devices can effectively and efficiently have uninterrupted access to wide area networks (WAN) such as the Internet. We introduce a novel architecture (BlueStar) whereby selected Bluetooth devices, called Bluetooth Wireless Gateways (BWGs), are also IEEE 802.11 enabled so that these BWGs could serve as egress/ingress points to/from the IEEE 802.11 wireless network. We propose mitigating interference between Bluetooth and IEEE 802.11, by employing a hybrid approach of adaptive frequency hopping (AFH) and Bluetooth carrier sense (BCS) of the channels. AFH labels channels as bad or good, and Bluetooth devices only access those channels in the good state, whereas BCS is used to avoid collision by sensing the channel prior to any transmission. By combining AFH and BCS, we drastically minimize the effect of the worst-case interference scenario wherein both a Bluetooth and an IEEE 802.11 interface are co-located in a single device. BlueStar enables Bluetooth devices, belonging to either a piconet or a scatternet, to access the WAN through the BWG without the need for any fixed Bluetooth access points, while utilizing widely deployed base of IEEE 802.11 networks. Moreover, we define the protocol stack employed by BlueStar as well as indicate how BWGs efficiently manage their capacity allocation through the different systems. We also mathematically derive an upper bound on the number BWGs needed in a Bluetooth scatternet so that uninterrupted access to all Bluetooth devices could be provided.     

Recursive estimation of two-dimensional processes with application to image processing

A low order quarter-plane-causal recursive model is presented to represent the class of 2-D stationary Gaussian processes with power spectra matrices factorable into a quarter-plane-causal and anti-causal parts. This model is used to develop a technique for obtaining optimal 2-D recursive estimators. The approach taken here is similar to Attasi's [8], with no commutability condition imposed on the model. Circumventing this condition allows the modeling of the 2-D processes to be achieved with fewer parameters, and enables one to find the solutions to the problems of blur and color noise which are inherent in most image degraded images. Some simulated examples illustrate these points.This research was supported in part by the U.S. Army Research Grant DAAG29-79-C-0054 and the National Science Foundation Grant ECS-8011911.     

Mobility Management for Hierarchical Wireless Networks

In this paper, we consider the mobility management in large, hierarchically organized multihop wireless networks. The examples of such networks range from battlefield networks, emergency disaster relief and law enforcement etc. We present a novel network addressing architecture to accommodate mobility using a Home Agent concept akin to mobile IP. We distinguish between the physical routing hierarchy (dictated by geographical relationships between nodes) and logical hierarchy of subnets in which the members move as a group (e.g., company, brigade, battalion in the battlefield). The performance of the mobility management scheme is investigated through simulation.