A study on channel allocation for data dissemination in mobile computing environments

This paper studies channel allocation methods for data dissemination through broadcast and ondemand channels. Analytical models and cost formulae for exclusive broadcast channels and exclusive ondemand channels are provided. Based on the models, we further derive cost models for dynamic channel allocation methods and propose a channel adaptation algorithm for optimizing system performance. The channel adaptation algorithm can be executed in O(n) time, where n is the number of data items in the database. Performance evaluation shows that the channel allocation algorithm produces optimal channel allocation which significantly improves the system performance under various parameter settings.     

Some properties of order-Statistics filters

LetX ₁,X ₂,... be a stationary sequence of random variables with Pr{X _t, x}=F(x),t=1, 2,... Also let _i ^n,(t) ,i=1,...,n, denote the ith order statistic (OS) in the moving sample (X _t–N ,...,X _t,...,X _t+N) of odd sizen=2N+1. ThenY _t=a _i X _i ^n(t) with a _i=1 is an order-statistics filter. In practicea _i0,i=1,...,n. Fort>N, the sequence {Y _t} is also stationary. IfX ₁ X ₂, ... are independent, the autocorrelation function (r)=corr(Y _t,Y _t+r) is zero forr >n – 1 and forr n – 1 can be evaluated directly in terms of the means, variances, and covariances of the OS in random samples of sizen +r fromF(x).In special cases several authors have observed that the spectral density functionf() of {Y _t} is initially decreasing for > 0. This result is made more precise and shown to hold generally under white noise. The effect of outliers (impulses) is also discussed.This research was supported by the U.S. Army Research Office.     

β-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.     

Input-output systems whose transmission operators furnish nearly best approximations to a given map

Let {S(A):A A}, whereA is a subset of an infinite-dimensional normed linear spaceL, be a class of general nonlinear input-output systems that are governed by operator equations relating the input, state, and output, all of which are in extended spaces. IfQ is a given operator from a specified set ¯D _i, of inputs into the space of outputs ¯H ₀, the problem we consider is to find, for a given >0, a parameterA A such that the transmission operatorR(A ) ofS(A ) furnishes a nearly best (or -best) approximation toQ from allR(A),A A. Here the distance betweenQ andR(A) is defined as the supremum of distances betweenQz andR(A)z taken over allz ¯D _i. In Theorems 2 through 5 we show that ifS(A) is normal (Definition 2),A satisfies some mild requirement andL contains a fundamental sequence, then establishingA A reduces to minimizing a certain continuous functional on a compact subset ofR ⁿ, and thus can be carried out by conventional methods. The applications of results are illustrated by the example of a model-matching problem for a nonlinear system, and of optimal tracking.     

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.     

Construction of Time-Relaxed c-Broadcast Networks

C-broadcasting is an information dissemination task where a message, originated at any node in a network, is transmitted to all other nodes with the restriction that each node having the message can transmit it to almost c neighbors simultaneously. If the transmission time of the message is set to be one time unit, a minimal c-broadcast network (c-MBN) is a communication network in which c-broadcasting from any node can be accomplished in log _c+1 n time units, where n is the number of nodes and log _c+1 n is the fastest possible broadcast time. If networks are sparse, additional time units may be required to perform c-broadcasting. A time-relaxed c-broadcast network, denoted as (t,c)-RBN, is a network where c-broadcasting from any node can be completed in log _c+1 n+t time units. In this paper, a network compounding algorithm is proposed to construct large sparse (t,c)-RBNs by linking multiple copies of a time-relaxed network of small size using the structure of another time-relaxed network. Computational results are presented to show the effectiveness of the proposed algorithm.     

A distributed link scheduling algorithm for CDMA packet radio networks

A distributed algorithm for the conflict-free channel allocation in CDMA (code division multiple access) networks is presented. Dynamic adjustment to topological changes is also considered. Though the schedules produced by our algorithm are not optimal with respect to link schedule length, the algorithm is simple and practical. The link schedule length minimization problem is NP-complete. Here the length of a link schedule is the number of time slots it uses. The algorithm guarantees a bound 2 — 1 time slots on the TDMA cycle length, where is the maximum degree of a station (i.e., maximum number of stations that a station can reach by radio links) in the network. The message complexity of a station isO().     

Identification of Trapping Effects and Ion Neutralization at the Insulator/Semiconductor Interface of MIS Structures from Dynamic Current–Voltage Characteristics of Ion Depolarization

The manifestations of ion traps, ion neutralization, and minority carrier generation at the insulator/semiconductor interface (hereafter, interface for brevity) in MIS structures are judged from isothermal dependences of ion depolarization current J and high-frequency capacitance C _s of the depletion layer in the semiconductor on gate potential V _g and the rate of potential change _v = dV _g/dt = const. In the general case, even for a single type of mobile ions in the insulator, the dynamic current–voltage characteristics (CVCs) may exhibit three current peaks. The transfer of some nonlocalized (free) ions at the interface through the insulator, depletion of ion traps, and decomposition of neutral ion–electron associates are responsible for the peaks. The sequence and number (down to one) of the peaks depend on the activation energies of the associated processes, value of _v, and energy of activation of minority carrier generation. Depending on these parameters, the peaks may appear, disappear, or merge into a broad peak, which may erroneously be identified as a result of the depletion of ion traps that have an energy spectrum. In other words, the CVC with a single peak does not necessarily mean that there exist several types of mobile ions. From the J, C _s = f(T, V _g, n ₀, _v) families, one can discriminate between purely ionic and electronic phenomena and identify free, neutralized, and/or trapped ions present at the interface (here, T is the temperature and n ₀ is the initial total surface concentration of particles (ions) and neutral associates at the interface).     

Permissively structured transfinite electrical networks

Transfinite electrical networks of ranks larger than 1 have previously been defined by arbitrarily joining together various infinite extremities through transfinite nodes that are independent of the networks' resistance values. Thus, some or all of those transfinite nodes may remain ineffective in transmitting current through infinity. In this paper, transfinite nodes are defined in terms of the paths that permit currents to reach infinity. This is accomplished by defining a suitable metricd ^v on the node setN _S ^v of eachv-sectionS ^v, av-section being a maximal subnetwork whose nodes are connected by two-ended paths of ranks no larger thanv. Upon taking the completion ofN _S ^v under that metricd ^v, we identify those extremities (now calledv-terminals) that are accessible to current flows. These are used to define transfinite nodes that combine such extremities. The construction is recursive and is carried out through all the natural number ranks, and then through the first arrow rank and the first limit-ordinal rank . The recursion can be carried still further. All this provides a more natural development of transfinite networks and indeed simplifies the theory of electrical behavior for such networks.This work was partially supported by the National Science Foundation under Grant MIP-9423732.     

Geometric properties of nonlinear networks containing capacitor-only cutsets and/or inductor-only loops. Part I: Conservation laws

This paper is the first in a two part sequence which studies nonlinear networks, containing capacitor-only cutsets and/or inductor-only loops from the geometric coordinate-free point of view of differentiable manifolds. Given such a nonlinear networkN, with °₀ equal to the sum of the number of independent capacitor-only cutsets and the number of independent inductor-only loops, we establish the following: (i) circuit theoretic sufficient conditions to guarantee that the set ⁰, of equilibrium points is a ₀-dimensional submanifold of the state space ofN; (ii) circuit theoretic sufficient conditions for the condition thatN has ₀ independent conservation laws and hence that through each point of the state space ofN, there passes a codimension ₀ invariant submanifold ^* of the network dynamics; (iii) circuit theoretic sufficient conditions to guarantee that the manifolds ^* and ⁰ intersect transversely.This work was supported by the Natural Sciences and Engineering Research Council of Canada, under Grant Number A7113, and by scholarships from the Natural Sciences and Engineering Research Council of Canada and the Ontario Provincial Government.     

On the convergence rate ofs-numbers of compact Hankel operators

It is well known that the sequence ofs-numbers {s_n},n=0, 1,..., of a compact operator, and particularly a compact Hankel operator =[h _j+k –1], converges monotonically to zero. Since the (n + 1)sts-number s_n measures the error ofL (¦z¦=1) approximation, modulo an additive H function, by nth degree proper rational functions whose poles are restricted to ¦z¦ < 1, it is very important to study how fast {s _n } converges to zero. It is not difficult to see that ifh _n =O(n ^–), for some > 1, thens _n =O(n ^–). In this paper we construct, for any given sequence _n 0, a compact Hankel operator such thats _{n n} for alln.The research of C. K. Chui was supported by the SDIO/IST managed by the U.S. Army under Contract No. DAAL-03-87-K-0025, and by the NSF under Grant No. DMS-8901345. X. Li's research was supported by the SDIO/IST managed by the U.S. Army under Contract No. DAAL-03-87-K-0025. The research of J. D. Ward was supported by the NSF under Grant No. DMS-8901345.     

Performance of cellular packet CDMA in an integrated voice/data network

This paper presents a simulation-based study of cellular packet CDMA systems operating in an integrated voice/data traffic scenario. Spread-spectrum CDMA provides a suitable framework for resource-shared packet transport capable of combining isochronous (voice, ISDN) and bursty data services. In this work, a general network model for cellular packet CDMA with mixed voice/data traffic is described and used to evaluate the capacity/performance impact of several key system parameters. First, the effect of spreading factor (N) and forward error correction (FEC) rate are studied, confirming earlier work indicating a weak dependence onN and a well-defined optimum code rate in the range of 0.5–0.7 (with BCH coding). Next, the effect of propagation loss coefficient () on network capacity is investigated over a range of possible assumptions for, including both constant and distance-dependent models. The results show that system capacity depends strongly on, varying by as much as a factor of 2 over the range of parameters considered. For a given distance-dependent assumption, performance results are also obtained for different cell sizes in order to understand the overall spatial reuse efficiency achievable in different cellular and microcellular scenarios. This is followed by an investigation of traffic source model effects: first the capacity improvement from voice activity detection VAD) is presented, showing the expected 21 gains. Results for varying proportions of voice and data traffic intensities indicate that the operating efficiency does not change significantly as the proportion of bursty data relative to voice is varied.     

Efficient,perfect polynomial random number generators

Let N be a positive integer and let P [x] be a polynomial that is nonlinear on the set _N of integers modulo N. If, by choosing x at random in an initial segment of _N , P(x) (mod N) appears to be uniformly distributed in _N to any polynomial-time observer, then it is possible to construct very efficient pseudorandom number generators that pass any polynomial-time statistical test. We analyse this generator from two points of view. A complexity theoretic analysis relates the perfectness of the generator to the security of the RSA-scheme. A statistical analysis proves that the least-significant bits of P(x) (mod N) are statistically random.This research was performed while C. P. Schnorr was visiting the Department of Computer Science of the University of Chicago, who also supported his research. A U.S. patent, based on this work, has been granted.     

On the robustness of stability for uncertain large-scale systems subjected to multiple time delays

The robustness problem of stability for large-scale uncertain systems with a class of multiple time delays is addressed in this paper. By applying the complex Lyapunov stability theorem, the matrix measure techniques, and norm inequalities, a new approach for solving a general case of the above problem is proposed. Several robust stability conditions, delay-dependent or delay-independent, are derived to guarantee the asymptotic stability and exponential stability of the uncertain large-scale time-delay systems. Moreover, these obtained results can also be applied to the stabilization design.Notation real number field - complex number field - x x=(x ₁,x ₂,...,x _n ) ^T R ⁿ - x ^T transpose of vectorx - x* complex conjugate transpose of vectorx - Re(·) real part of (·) - x norm of vectorx; x=(x*x)^1/2 - A ^T transpose of matrixA - A* complex conjugate transpose of matrixA - ¯(·) maximal absolute value of eigenvalue of matrixA - (A) matrix measure of matrixA; (A)=¯((A + A*)/2) - A induced norm of matrix A; A=[¯(A*A)]^1/2 - ¦a_ij ¦ absolute value of element a_ij - ¦ A¦ {¦a_ij¦} for matrix A={a_ij} - A >B a_ij > b_ij for alli andj where A={a_ij} andB={b_ij} - z complex number - ¯z complex conjugate ofz Supported by National Science Council, Taiwan, Republic of China, Grant NSC83-0404-E006-001.     

Bit-level systolic arrays for modular multiplication

This paper presents bit-level cellular arrays implementing Blakley's algorithm for multiplication of twon-bit integers modulo anothern-bit integer. The semi-systolic version uses 3n(n+3) single-bit carry save adders and 2n copies of 3-bit carry look-ahead logic, and computes a pair of binary numbers (C, S) in 3n clock cycles such thatC+S[0, 2N). The carry look-ahead logic is used to estimate the sign of the partial product, which is needed during the reduction process. The final result in the correct range [0,N) can easily be obtained by computingC+S andC+S–N, and selecting the latter if it is positive; otherwise, the former is selected. We construct a localized process dependence graph of this algorithm, and introduce a systolic array containing 3nw simple adder cells. The latency of the systolic array is 6n+w–2, wherew=n/2. The systolic version does not require broadcast and can be used to efficiently compute several modular multiplications in a pipelined fashion, producing a result in every clock cycle.     

Order selection statistical test for nonstationary AR models

A new statistical test for selecting the order of a nonstationary AR modelyk is presented based on the predictive least-squares principle. This test is of the same order as the accumulated cost function _n = _k=1 ⁿ ( _k ^* – _k )²;i.e., ^* wherey _k ^* is the predictive least-square estimate. It is constructed to show how many times the integrated AR processy _k is differenced in order to obtain a stationary AR process given that the exact order of the process is unknown.     

Deterministic tests for detecting singleV-coupling faults in RAMs

We consider the problem of detecting singleV-coupling faults (as defined by Nair, Thatte, and Abraham) inn×1 random-access memories (RAMs). First we derive a lower bound of 2 ^V–2 nlog₂ n+(2 ^V +3)n on the length of any test that detects all singleV-coupling faults, for 2V47 andn=2 ^e wheree{8,...,34}. In the derivation we make use of a family of binary codes which we call (n, )-exhaustive codes. We then describe a procedure which, given any (n, V–1)-exhaustive code, constructs a test that detects all singleV-coupling faults, fornV>2. Following this approach, optimal (n,1)- and (n, 2)-exhaustive codes are used to construct S2CTEST and S3CTEST, which are efficient tests of length 10n and 4nlog₂ n+18n that detect all single 2- and 3-coupling faults, respectively. S3CTEST is roughly five times shorter, for current RAM capacities, than Papachristou and Sahgal's test of length 24n[log₂ n]+n. Codes generated according to Tang and Chen are used similarly to construct S4CTEST and S5CTEST, which are tests of approximate length 8.6n(log₂ n)^1.585 and 9.6n(log₂ n)^2.322 that detect all single 4- and 5-coupling faults, respectively. S5CTEST has the interesting property of being able to detect all single physical neighborhood pattern-sensitive faults without requiring the mapping from logical cell addresses to physical cell locations. S5CTEST also detects the scrambled pattern-sensitive fault recently proposed by Franklin and Saluja; moreover, the new test is approximately fourteen times shorter (for 1 and 4 Mbit RAMs) than the test they describe.This work was supported by operating grants from the Central Research Fund of the University of Alberta and the Natural Sciences and Engineering Research Council of Canada under grant OGP0105567.     

The prime and generalized nullspaces of right regular pencils

The classical notion of the -generalized nullspace, defined on a matrixA R ^n×n,where is an eigenvalue, is extended to the case of ordered pairs of matrices(F, G), F, G R ^m×nwhere the associated pencilsF – G is right regular. It is shown that for every C {} generalized eigenvalue of (F, G), an ascending nested sequence of spaces {P ⁱ ,i=1, 2,...} and a descending nested sequence of spaces {ie495-02 i=1, 2,...} are defined from the -Toeplitz matrices of (F, G); the first sequence has a maximal elementM ^* , the -generalized nullspace of (F, G), which is the element of the sequence corresponding to the index , the -index of annihilation of (F, G), whereas the second sequence has the first elementP ^* as its maximal element, the -prime space of (F, G). The geometric properties of the {M ⁱ ,i=1, 2,..., and {P ⁱ ,i=1, 2,...sets, as well as their interrelations are investigated and are shown to be intimately related to the existence of nested basis matrices of the nullspaces of the -Toeplitz matrices of (F, G). These nested basis matrices characterize completely the geometry ofM ^* and provide a systematic procedure for the selection of maximal length linearly independent vector chains characterizing the-Segre characteristic of (F, G).     

Factorizations in the elementary Abelian p-group and their cryptographic significance

Let G be a finite group and let A _i 1 i s, be subsets of G where ¦A _i ¦ 2, 1 i s and s 2. We say that (A₁, A₂,..., A₃) is a factorization of G if and only if for each g G there is exactly one way to express g = a ₁ a ₁ a ₂··· a ₃, where a _j A _i , 1 i s.The problem of finding factorizations of this type was first introduced by Hajos [3] in 1941. Since then a number of papers have appeared on the subject. More recently, Magliveras [6] has applied factorization of permutation groups to cryptography to obtain a private-key cryptosystem. Factorizations in the elementary abelian p-group were exploited (but not explicitly stated in these terms) by Webb [13] to produce a public-key cryptosystem conceptually similar to cryptosystems based on the knapsack problem.Using the result that certain types of factorizations in the elementary abelian p-group are necessarily transversal (a term introduced by Magliveras), this paper shows that the public-key system proposed by Webb is insecure.