Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks

Connected dominating set (CDS) has been proposed as virtual backbone or spine of wireless ad hoc networks. Three distributed approximation algorithms have been proposed in the literature for minimum CDS. In this paper, we first reinvestigate their performances. None of these algorithms have constant approximation factors. Thus these algorithms cannot guarantee to generate a CDS of small size. Their message complexities can be as high as O(n ²), and their time complexities may also be as large as O(n ²) and O(n ³). We then present our own distributed algorithm that outperforms the existing algorithms. This algorithm has an approximation factor of at most 8, O(n) time complexity and O(nlogn) message complexity. By establishing the (nlogn) lower bound on the message complexity of any distributed algorithm for nontrivial CDS, our algorithm is thus message-optimal.     

Multidimensional fourier transforms by systolic architectures

In this paper, time-efficient systolic and semi-systolic architectures for the implementation of multidimensional DFTs are proposed that allow modularity and easy expansibility while keeping throughput independent of the dimension of the DFT. We shall call an array semi-systolic if the input data is to be preloaded into every cell of the array or if the output data can be calculated not only in the boundary cells of the array. DFT algorithms are represented by FORTRAN-like code, in order to explicitly display the suggested rotational transformations in the index space. After the transformation, multidimensional DFT algorithm can be mapped onto a systolic structure. The area-time² complexity of the proposed design is within logk factor of the lower bound for ak-point DFT (AT ²=(k ² log² k)), i.e. equals 0(k ² log³ k)=0(N ^2M log³ N) fork=N ^2M point DFT;A is the area complexity andT is the system throughput.     

An Efficient Parallel Algorithm for the Single Function Coarsest Partition Problem on the EREW PRAM

In this paper, we derive an efficient parallel algorithm to solve the single function coarsest partition problem. This algorithm runs in O(log2n) time using O(nlogn) operations on the EREW PRAM with O(n) memory cells used. Compared with the previous PRAM algorithms that consume O(n1+ε) memory cells for some positive constant ε > 0, our algorithm consumes less memory cells without increasing the total number of operations.     

Universal approximation capability of EBF neural networks with arbitrary activation functions

The purpose of this paper is to investigate the approximation capability of elliptic basis function (EBF) neural networks. The main results are: (1) A necessary and sufficient condition for a functionS (R ¹) to be qualified as an activation function in the hidden layer of an EBF neural network is given. (2) Every nonzero functionG L ²(R ⁿ ) is qualified to be an activation function in the elliptic neural network to approximate any function in L²(Rⁿ). (3) As applications, we give new proofs of the theorems concerning the approximation capability of affine basis function (ABF) neural networks and generalized radial basis function (GRBF) neural networks (including radial basis function neural networks) with arbitrary activation functions. In particular, we solve the problem of the approximation capability of sigma-pi neural networks.Work was supported in part by CNSF, the Shanghai Science Foundations and Doctoral Program of Education Commissions of China.     

Fast Discrete Cosine Transform via Computation of Moments

Discrete cosine transform (DCT) is widely used in signal processing. This paper presents a novel approach to perform DCT. DCT is expressed in terms of discrete moments via triangle function transforms and later Taylor series expansion. From this, a fast systolic array for computing moments is converted to compute DCT with only a few multiplications and without any cosine evaluations. The systolic array has advantages of pipelinability, regularity, modularity, local connectivity and scalability, thus making it to be very suitable for VLSI implementation. We provide an estimate of the realizability of our array in a 0.5 m CMOS technology and comparisons with other methods. The execution time of the systolic array is only O(N log₂ N/log₂ log₂ N) in computing 1D N-point DCT if N is sufficiently large. The approach is also applicable to multiple dimensional DCT and DCT inverses.     

A New Bluetooth Scatternet Formation Protocol

A Bluetooth ad hoc network can be formed by interconnecting piconets into scatternets. The constraints and properties of Bluetooth scatternets present special challenges in forming an ad hoc network efficiently. In this paper, we present and analyze a new randomized distributed protocol for Bluetooth scatternet formation. We prove that our protocol achieves O(logn) time complexity and O(n) message complexity. The scatternets formed by our protocol have the following properties: (1) any device is a member of at most two piconets, and (2) the number of piconets is close to be optimal. These properties can help prevent overloading of any single device and lead to low interference between piconets. We validate the theoretical results by simulations, which also show that the scatternets formed have O(logn) diameter. As an essential part of the scatternet formation protocol, we study the problem of device discovery: establishing multiple connections simultaneously with many Bluetooth devices. We investigate the collision rate and time requirement of the inquiry and page processes. Our simulation results indicate that the total number of packets sent is O(n) and that the maximum number of packets sent by any single device is O(logn).     

Selecting Forwarding Neighbors in Wireless Ad Hoc Networks

Broadcasting is a fundamental operation which is frequent in wireless ad hoc networks. A simple broadcasting mechanism, known as flooding, is to let every node retransmit the message to all its 1-hop neighbors when receiving the first copy of the message. Despite its simplicity, flooding is very inefficient and can result in high redundancy, contention, and collision. One approach to reducing the redundancy is to let each node forward the message only to a small subset of 1-hop neighbors that cover all of the node's 2-hop neighbors. In this paper we propose two practical heuristics for selecting the minimum number of forwarding neighbors: an O(nlogn) time algorithm that selects at most 6 times more forwarding neighbors than the optimum, and an O(nlog² n) time algorithm with an improved approximation ratio of 3, where n is the number of 1- and 2-hop neighbors. The best previously known algorithm, due to Bronnimann and Goodrich [2], guarantees O(1) approximation in O(n ³ logn) time.     

Geometric problems on two-dimensional array processors

Parallel algorithms for solving geometric problems on two array processor models—the mesh-connected computer (MCC) and a two-dimensional systolic array—are presented. We illustrate a recursive divide- and-conquer paradigm for MCC algorithms by presenting a time-optimal solution for the problem of finding thenearest neighbors of a set of planar points represented by their Cartesian coordinates. The algorithm executes on an×n MCC, and requires an optimalO(n) time. An algorithm for constructing theconvex hull of a set of planar points and anupdate algorithm for thedisk placement problem on ann ^2/3×n ^2/3 two-dimensional systolic array are presented. Both these algorithms requireO(n ^2/3) time steps. The advantage of the systolic solutions lies in their suitability for direct hardware implementation.This research was partially supported by an IBM Faculty Development Award.     

Capacity of data collection in randomly-deployed wireless sensor networks

Data collection is one of the most important functions provided by wireless sensor networks. In this paper, we study theoretical limitations of data collection and data aggregation in terms of delay and capacity for a wireless sensor network where n sensors are randomly deployed. We consider different communication scenarios such as with single sink or multiple sinks, regularly-deployed or randomly-deployed sinks, with or without aggregation. For each scenario, we not only propose a data collection/aggregation method and analyze its performance in terms of delay and capacity, but also theoretically prove whether our method can achieve the optimal order (i.e., its performance is within a constant factor of the optimal). Particularly, with a single sink, the capacity of data collection is in order of \Uptheta(W)\Uptheta(W) where W is the fixed data-rate on individual links. With k regularly deployed sinks, the capacity of data collection is increased to \Uptheta(kW)\Uptheta(kW) when k=O(\fracnlogn)k=O\left({\frac{n}{\log n}}\right) or \Uptheta(\fracnlognW)\Uptheta\left({\frac{n}{\log n}}W\right) when k=\Upomega(\fracnlogn)k=\Upomega\left({\frac{n}{\log n}}\right). With k randomly deployed sinks, the capacity of data collection is between \Uptheta(\fracklogkW)\Uptheta\left({\frac{k}{\log k}}W\right) and \Uptheta(kW)\Uptheta(kW) when k=O(\fracnlogn)k=O\left({\frac{n}{\log n}}\right) or \Uptheta(\fracnlognW)\Uptheta\left({\frac{n}{\log n}}W\right) when k=w(\fracnlogn)k=\omega\left({\frac{n}{\log n}}\right). If each sensor can aggregate its receiving packets into a single packet to send, the capacity of data collection with a single sink is also increased to \Uptheta(\fracnlognW)\Uptheta\left({\frac{n}{\log n}}W\right).     

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.     

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.     

On a case of symbiosis between systolic arrays

The paper studies the problem of efficiently computing the product of three n × n matrices using O(n²) elementary processors in O(n) time. The problem is relevant in image processing.After a critical analysis of extensions on well-known systolic arrays for matrix multiplication to solve the proposed problem, a systolic system is disclosed, which achieves the optimal VLSI-complexity AT² = O(n⁴).     

Stability Testing of Two-Dimensional Discrete-Time Systems by a Scattering-Type Stability Table and Its Telepolation

Stability testing of two-dimensional (2-D) discrete-time systems requires decision on whether a 2-D (bivariate) polynomial does not vanish in the closed exterior of the unit bi-circle. The paper reformulates a tabular test advanced by Jury to solve this problem. The 2-D tabular test builds for a real 2-D polynomial of degree (n ₁, n ₂) a sequence of n ₂ matrices or 2-D polynomials (the 2-D table). It then examines its last polynomial - a 1-D polynomial of degree 2n ₁ n ₂ - for no zeros on the unit circle. A count of arithmetic operations for the tabular test is performed. It shows that the test has O(n ⁶) complexity (assuming n ₁ = n ₂ = n)- a significant improvement compared to previous tabular tests that used to be of exponential complexity. The analysis also reveals that, even though the testing of the condition on the last polynomial requires O(n ⁴) operations, the count of operations required for the table's construction makes the overall complexity O(n ⁶). Next it is shown that it is possible to telescope the last polynomial of the table by interpolation and circumvent the construction of the 2-D table. The telepolation of the tabular test replaces the table by n ₁ n ₂ + 1 stability tests of 1-D polynomials of degree n ₁ or n ₂ of certain form. The resulting new 2-D stability testing procedure requires a very low O(n ⁴) count of operations. The paper also brings extension for the tabular test and its simplification by telepolation to testing 2-D polynomials with complex valued coefficients.     

A Practical Vector Restoration Technique for Large Sequential Circuits

Given a test sequence and a list of faults detected by the sequence, vector restoration techniques extract a minimal subsequence that detects a chosen subset of modeled faults. Vector restoration techniques are useful in static compaction of test sequences and in fault diagnosis. We propose a new vector restoration technique that is a significant improvement over the state of the art in several ways: (1) a sequence of length n can be restored with only O(n log ₂ n) simulations while known approaches require simulation of O(n ²) vectors, (2) a two-step restoration process is used that makes vector restoration practical for large designs, and (3) restoration process for several faults is overlapped to provide significant acceleration in vector restoration. Our new ideas can be used to improve run-times of known static compaction and fault diagnosis methods. We integrated the proposed vector restoration technique into a static test sequence compaction system. Our experiments show that the new restoration technique, as compared to known techniques (Proceedings of Int. Conf. on Computer Design, University of Iowa, Aug. 1997, pp. 360–365.), is (1) about 2 times faster for the ISCAS benchmark circuits, and (2) 3 to 5 times faster on large, industrial designs. Using the new restoration technique, we successfully processed large industrial designs that could not be handled by earlier techniques (Proceedings of Int. Conf. on Computer Design, University of Iowa, Aug. 1997, pp. 360–365.) in 2 CPU days.     

Input Locality and Hardness Amplification

We establish new hardness amplification results for one-way functions in which each input bit influences only a small number of output bits (a.k.a. input-local functions). Our transformations differ from previous ones in that they approximately preserve input locality and at the same time retain the input size of the original function. Let f:{0,1} ⁿ →{0,1} ^m be a one-way function with input locality d, and suppose that f cannot be inverted in time $\exp(\tilde{O}(\sqrt{n}\cdot d))$ on an ε-fraction of inputs. Our main results can be summarized as follows:

• If f is injective then it is equally hard to invert f on a (1?ε)-fraction of inputs.
• If f is regular then there is a function g:{0,1} ⁿ →{0,1} ^m+O(n) that is d+O(log³ n) input local and is equally hard to invert on a (1?ε)-fraction of inputs.

A natural candidate for a function with small input locality and for which no sub-exponential time attacks are known is Goldreich’s one-way function. To make our results applicable to this function, we prove that when its input locality is set to be d=O(logn) certain variants of the function are (almost) regular with high probability. In some cases, our techniques are applicable even when the input locality is not small. We demonstrate this by extending our first main result to one-way functions of the “parity with noise” type.     

Removing edges from hypercubes to obtain vertex‐symmetric networks with small diameter

The binary hypercube Q _n has a small diameter, but a relatively large number of links. Because of this, efforts have been made to determine the maximum number of links that can be deleted without increasing the diameter. However, the resulting networks are not vertex‐symmetric. We propose a family of vertex‐symmetric spanning subnetworks of Q _n , whose diameter differs from that of Q _n by only a small constant factor. When n=2^k, the cube‐connected cycles network of dimension n is a vertex‐symmetric spanning subnetwork of Q _{n+lg n} . By selectively adding hypercube links, we obtain a degree 6 vertex‐symmetric network with diameter 3n/2. We also introduce a vertex‐symmetric spanning subnetwork of Q _n−1 with degree log₂ n, diameter 3n/2−2, log₂ n‐connectivity and maximal fault tolerance. This network hosts Q _n−1 with dilation 2(log₂ n)−1. This revised version was published online in June 2006 with corrections to the Cover Date.     

A systolic architecture for optimal filter design support

A prototype filter design is reviewed to underscore the computational problems arising in such designs. A purely systolic-array architecture is presented. This array provides the computational support necessary for filter design. Due to a simple and novel data steering technique the array is capable of carrying out a number of important matrix operations such as factorization, inversion of factors, and matrix-matrix multiplication. Another interesting attribute is the array's ability to maximally overlap computations of multiphase algorithms. In this study we demonstrate the execution of a dense matrix factorization phase and a factor inversion phase on the array with no need for intraphase or interphase I/O. We show that these phases (which are the backbone of an optimal filtering algorithm) are completed in the optimal count of aboutn time units. The array employs 2n ⁿ–n simple processing elements (PEs) that are active every other time unit. It is shown that the functions of two adjacent PEs can be merged and assigned to a single PE thus maximizing PE utilization. A possible design of a merged PE is given.     

Phase relations in Cu- RO1.5- O (R < Ho,Er, Yb) and gibbs energy of formation of Cu2R2O5 (R < Ho,Er, Yb) between 1000 and 1325K

Phase relations in Cu-RO_1.5-O(R < Ho,Er,Yb) ternary systems at 1273K have been established by isothermal equilibration of samples containing different ratios of Cu:R(R < Ho,Er,Yb) in flowing air or high purity argon atmosphere for four days. The samples were then rapidly cooled to ambient temperature and the coexisting phases were identified by powder x-ray diffraction analysis. Only one ternary oxide, Cu₂R₂O₅(R < Ho,Er,Yb) was found to be stable. The chemical potential of oxygen for the coexistence of the three phase assemblage, Cu₂O + R₂O₃ + Cu₂R₂O₅(R < Ho,Er,Yb) has been measured by employing the solid-state galvanic cells,< (−) Pt, Cu₂O + Ho₂O₃+ Cu₂Ho₂O₅//CSZ//Air (Po₂< 2.12 × 10⁴ Pa), Pt (+) (−) Pt, Cu₂O + Er₂O₃+ Cu₂Er₂O//CSZ//Air (Po₂< 2.12 × 10⁴ Pa), Pt (+) (−) Pt, Cu₂O + Yb₂O₃ + Cu₂Yb₂O₅//CSZ//Air (Po₂ < 2.12 × 10⁴ Pa), Pt (+) in the temperature range of 1000 to 1325K. Combining the measured emf of the above cells with the chemical potential of oxygen at the reference electrode, using the Nernst relationship, gives for the reactions, 2Cu₂O(s) + 2Ho₂O₃(s) + O₂(g) → 2Cu₂Ho₂O₅(s) (1) 2Cu₂O(s) + 2Er₂O₃(s) + O₂(g) → 2Cu₂Er₂O₅(s) (2) and 2Cu₂O(s) + 2Yb₂O₃(s) + O₂(g) → 2Cu₂Yb₂O₅(s) (3) δΜo₂ = −219,741.3 + 145.671 T (±100) Jmol⁻¹ (4) δΜo₂ = −222,959.8 + 147.98 T(±100) Jmol⁻¹ (5) and δΜo₂ = −231,225.2 + 151.847 T(±100) Jmol⁻¹ (6) respectively. Combining the chemical potential of oxygen for the coexistence of Cu₂O + R₂O₃ + Cu₂R₂O₅(R− Ho,Er,Yb) obtained in this study with the oxygen potential for Cu₂O + CuO equilibrium gives for the reactions, 2 CuO(s) + Ho₂O₃(s) → Cu₂Ho₂O₅(s) (7) 2 CuO(s) + Er₂O₃(s) → Cu₂Er₂O₅(s) (8) and 2 CuO(s) + Yb₂O₃(s) → Cu₂Yb₂O₅(s) (9) δG‡ < 22,870.3 − 23.160 T (±100) Jmol⁻¹ (10) δG‡ < 21,261.1 − 22.002 T (±100) Jmol⁻¹ (11) and δG‡ < 17,128.4 - 20.072 T (±100) Jmol^-1 (12) It can be clearly seen that the formation of Cu₂R₂O₅R < Ho,Er,Yb) from the component oxides is endothermic. Further, Cu₂R₂O₅(R < Ho,Er,Yb) are an entropy stabilized phases. Based on the results obtained in this study, the oxygen potential diagram for Cu-R-O(R < Ho,Er,Yb) ternary system at 1273K has been composed.