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.     

A scalable wireless virtual LAN

This paper presents a Wireless Virtual Local Area Network (WVLAN) to support mobility in IPoverATM local area networks. Mobility is handled by a joint ATMlayer handoff for connection rerouting and MAClayer handoff for location tracking, such that the effects of mobility are localized and transparent to the higherlayer protocols. Different functions, such as Address Resolution Protocol (ARP), mobile location, and ATM connection admission are combined to reduce protocol overhead and frontend delay for connectionless packet transmission in connectionoriented ATM networks. The proposed WVLAN, through the use of ATM technology, provides a scalable wireless virtual LAN solution for IP mobile hosts.     

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.     

Simulation‐based performance evaluation of routing protocols for mobile ad hoc networks

In this paper we evaluate several routing protocols for mobile, wireless, ad hoc networks via packetlevel simulations. The ad hoc networks are multihop wireless networks with dynamically changing network connectivity owing to mobility. The protocol suite includes several routing protocols specifically designed for ad hoc routing, as well as more traditional protocols, such as link state and distance vector, used for dynamic networks. Performance is evaluated with respect to fraction of packets delivered, endtoend delay, and routing load for a given traffic and mobility model. Both small (30 nodes) and medium sized (60 nodes) networks are used. It is observed that the new generation of ondemand routing protocols use much lower routing load, especially with small number of peertopeer conversations. However, the traditional link state and distance vector protocols provide, in general, better packet delivery and endtoend delay performance.     

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.     

Symmetry relations in multidimensional Fourier transform pairs

A relation between the types of symmetries that exist in signal and Fourier transform domain representations is derived for continuous as well as discrete domain signals. The symmetry is expressed by a set of parameters, and the relations derived in this paper will help to find the parameters of a symmetry in the signal or transform domain resulting from a given symmetry in the transform or signal domain respectively. A duality among the relations governing the conversion of the parameters of symmetry in the two domains is also brought to light. The application of the relations is illustrated by a number of two-dimensional examples.Notation R the set of real numbers - R ^m R × R × ... × R m-dimensional real vector space - continuous domain real vector - L {¦ – _i , i = 1,2,..., m} - m-dimensional frequency vector - W { – _i ,i=1,2,..., m} - m-dimensional normalized frequency vector - _P {¦ – _i , i=1,2,...,m} - g(ol) g (₁,₂,..., _m ) continuous domain signal - () ( _{1 2},..., _m )=G (j ₁,j ₂,..., j _m ) Fourier transform ofg (ol) - (A,b,,,) parameters ofT- symmetry - N the set of integers - N ^m N × N × ... × N m-dimensional integer vector spacem-dimensional lattice - h(n) h (n ₁,.,n _m ) discrete domain signal - H() Fourier transform ofh (n) - v ₁,v ₂,..., v_m m sample-direction and interval vectors - V (v ₁ v ₂ ...v _m ) sampling basis matrix - [x]^* complex conjugate ofx - detA determinant ofA - X {x¦ – x _i , i=1,2,..., m} - A ^–t [A ^–1] ^t ,t stands for transpose This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A-7739 to M. N. S. Swamy and in part by Tennessee Technological University under its Faculty Research support program to P. K. Rajan.     

Routing with multiple QoS requirements for supporting multimedia applications

Distributed multimedia applications usually require multiple QoS performance guarantees. However, in general, searching such a route in the network, to support multimedia applications, is known to be NPcomplete. In this paper, we propose a new heuristic QoS routing algorithm, called QoSR_DKS, for supporting multimedia applications in highspeed networks. QoSR_DKS is a modification of rulebased Fallback routing and Dijkstra algorithms. It can search a unicast route that would have enough network resources so that multiple QoS requirements (bandwidth, delay, and delay jitter) of the requested flow could be guaranteed. Its worst case computation time complexity is the same as that of the Dijkstra algorithm, i.e., O(V²), where V is the number of nodes in the network. Extensive simulations were done with various network sizes, upto 500 nodes networks, where each node uses Weighted Fair Queueing (WFQ) service discipline. Results show that QoSR_DKS is very efficient. It could always find the QoS satisfying route, whenever there exists one (success rate is optimal), and its average computation time is near to simple shortest path Dijkstra algorithm.     

Perspectives on Analytical Modeling of Small Geometry MOSFETs in SPICE for Low Voltage/Low Power CMOS Circuit Design

The present state of the art in analytical MOSFET modeling for SPICE circuit simulation is reviewed, with emphasis on the circuit design usage of these models. It is noted that the model formulation represents an upper limit of what is possible from any type of model, but that good parameter extraction is required to most closely approach that limit. The individual model types presently in common use are examined, with discussion of the behavior of each model, its strengths and weaknesses, its applicability to certain types of circuits, and criteria that a circuit design consumer can employ to judge a model before using it for circuit design. Some related issues, such as node charge and gate capacitance modeling, charge conservation, and statistical simulation of process variations, are also evaluated. Finally, new trends, directions, and requirements of MOSFET modeling for circuit simulation are considered.     

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.     

Dynamic capacity allocation and hybrid multiplexing techniques for ATM wireless LANs

We consider digital wireless multimedia LANs and timevarying traffic rates. To deal effectively with the dynamics of the timevarying traffic rates, a Traffic Monitoring Algorithm (TMA) is deployed to dynamically allocate channel capacities to the heterogeneous traffics. The TMA is implemented as a higher level protocol that dictates the capacity boundaries within two distinct framed transmission techniques: a Framed Time DomainBased (FTDB) technique and a Framed CDMA (FCDMA) technique. The performance of the TMA in the presence of the FTDB technique is compared to its performance in the presence of the FCDMA technique for some traffic scenarios. The performance metrics used for the TMAFTDB and TMAFCDMA combinations are channel capacity utilization factors, traffic rejection rates, and traffic delays. It is found that the TMAFTDB is superior to the TMAFCDMA when the speed of the transmission links is relatively low and the lengths of the transmitted messages are relatively short. As the speed of the transmission links and the length of the transmitted messages increase, the TMAFCDMA eventually outperforms the TMAFTDB.     

An adaptive algorithm for optimizing the packet size used in wireless ARQ protocols

We develop an algorithm that allows an ARQ protocol to dynamically optimize the packet size based on estimates of the channel biterrorrate. Our algorithm is particularly useful for wireless and satellite channels where the biterrorrates tend to be relatively high and time variable. Our algorithm uses the acknowledgment history to make estimates of the channel biterrorrate, based on which the optimal packet size can be chosen. We develop a Markov chain model for the analysis of the system, under static channel conditions, and show that the algorithm can achieve close to optimal performance using a history of just 10,000 bits. We also use the Gilbert–Elliott twostate Markov channel to model dynamic channel conditions. We show, through simulation, that the algorithm performs well even under rapidly changing channel conditions. Finally, we discuss a maximum likelihood approach for choosing the packet size, which performs almost optimally but is much easier to implement.     

On the structure of the privacy hierarchy

An N argument function f(x ₁,...,x _N ) is called t-private if a protocol for computing f exists so that no coalition of at most t parties can infer any additional information from the execution, other than the value of the function. The motivation of this work is to understand what levels of privacy are attainable. So far, only two levels of privacy are known for N argument functions which are defined over finite domains: functions that are N-private and functions that are (N – 1)/2-private but not N/2-private.In this work we show that the privacy hierarchy for N-argument functions which are defined over finite domains, has exactly (N + 1)/2 levels. We prove this by constructing, for any N/2 t N – 2, an N-argument function which is t-private but not (t + 1)-private.This research was supported by US-Israel Binational Science Foundation Grant 88-00282.     

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.     

Throughput performance of distributed applications in switched networks in presence of end‐system bottlenecks

The steady state throughput performance of distributed applications deployed in switched networks in presence of endsystem bottlenecks is studied in this paper. The effect of various limitations at an endsystem is modelled as an equivalent transmission capacity limitation. A class of distributed applications is characterised by a static traffic distribution matrix that determines the communication between various components of the application. It is found that uniqueness of steady state throughputs depends only on the traffic distribution matrix and that some applications (e.g., broadcast applications) can yield nonunique values for the steady state component throughputs. For a given switch capacity, with traffic distribution that yield fair unique throughputs, the tradeoff between the endsystem capacity and the number of application components is brought out. With a proposed distributed rate control, it has been illustrated that it is possible to have unique solution for certain traffic distributions which is otherwise impossible. Also, by proper selection of rate control parameters, various throughput performance objectives can be realised.     

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.     

Adaptive multicast routing in multirate loss networks

In this paper, we study two versions of the multicast routing problem in multirate loss networks: complete and partial. In the complete version of the multicast routing problem, the identities of all destination nodes are available to the multicast routing algorithm at once. Conversely, in the partial version of the multicast problem, the identities of the destination nodes are revealed to the routing algorithm one by one. Although the complete version of the multicast routing problem, also known as the Steiner tree problem, has been well studied in the literature, less attention has been paid for the definition of link costs and evaluating the performance of multicast routing algorithm from the network revenue point of view. Therefore, in this paper, we first propose two approaches, namely, the Markov Decision Processbased (MDPbased) and Least Loaded Routingbased (LLRbased) approaches, for defining link costs. Several heuristic multicast routing algorithms are then proposed for both fully connected networks and sparsely connected networks. We have also proposed a new performance metric, referred to as fractional reward loss, for evaluating the performance of multicast routing algorithms. Our simulation results indicate that algorithms based on partial destination information yield worse performance than those based on complete information. We also found that, for fully connected networks, algorithms that use LLRbased link costs yield very competitive performance as compared to those that use MDP approach. However, for sparsely connected networks, LLRbased algorithms yield significantly worse performance as compared to the MDPbased algorithms.     

Stabilization of third-order, single-stage Sigma-Delta modulators

The issue of stability of higher-order, single-stage Sigma-Delta () modulators is addressed using a method from nonlinear system theory. As a result, theoretical bounds for the quantizer input of the modulators are derived. A new method for stabilizing the modulators is then presented. It uses the quantizer input bound for possible instability detection. Upon detection of such a state, the highest-order integrator is cut off, effectively reducing the order of the modulator, and thus resulting in a stable system. The method is easily implemented and results in a very good signal-to-noise ratio (SNR) and fast return to normal operation compared to other stabilization methods.Financial support from General Secretariat for Research and Technology of Greece under contract PENED 95/1729.     

Linear phase FIR approximation of magnitude response |1/ω| for maximal flatness at an arbitrary frequency ω0, 0<ω0<π*

In many signal processing situations, the desired (ideal) magnitude response of the filter is a rational function: (a digital integrator). The requirements of a linear phase response and guaranteed stable performance limit the design to a finite impulse response (FIR) structure. In many applications we require the FIR filter to yield a highly accurate magnitude response for a narrow band of frequencies with maximal flatness at an arbitrary frequency ₀ in the spectrum (0, ). No techniques for meeting such requirements with respect to approximation of are known in the literature. This paper suggests a design by which the linear phase magnitude response can be approximated by an FIR configuration giving a maximally flat (in the Butterworth sense) response at an arbitrary frequency ₀, 0<₀<^*. A technique to compute exact weights for the design has also been given.     

Characterization of subthreshold MOS mismatch in transistors for VLSI systems

MOS transistor mismatch is revisited in the context of subthreshold operation and VLSI systems. We report experimental measurements from large transistor arrays with device sizes typical for digital and analog VLSI systems (areas between 9 and 400µm²). These are fabricated at different production qualified facilities in 40-nm gate oxide,n-well andp-well, mask lithography processes. Within the small area of our test-strips (3 mm²), transistor mismatch can be classified into four categories: random variations, edge, striation, and gradient effects. The edge effect manifests itself as a dependence of the transistor current on its position with reference to the surrounding structures. Contrary to what was previously believed, edge effects extend beyond the outer most devices in the array. The striation effect exhibits itself as a position-dependent variation in transistor current following a sinusoidal oscillation in space of slowly varying frequency. The gradient effect is also a position-dependent spatial variation but of much lower frequency. When systematic effects are removed from the data, the random variations follow an inverse linear dependence on the square root of transistor area.     

A class of mobile motion prediction algorithms for wireless mobile computing and communications

This paper describes a class of novel mobile motion prediction algorithms for supporting global mobile data accessing. Traditionally, mobility and routing management includes functions to passively keep track of the location of the users/terminals and to maintain connections to the terminals belonging to the system. To maintain uninterrupted high-quality service for distributed applications, it is important that a mobile system be more intelligent and can anticipate the change of the location of its user. We propose an aggressive mobility and routing management scheme, called predictive mobility management. A class of mobile motion prediction algorithms predicts the future location of a mobile user according to the user's movement history, i.e., previous movement patterns. By combining this scheme with mobility agent functions, the service and user routing data are actually pre-connected and pre-assigned at the locations to which the user is moving. Thus, the user can immediately receive service or data with virtually the same efficiency as at the previous location, i.e., without encountering a large data structure handover delay before service or data is available.