Channel assignment with separation for interference avoidance in wireless networks

Given an integer /spl sigma/>1, a vector (/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/), of nonnegative integers, and an undirected graph G=(V, E), an L(/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/)-coloring of G is a function f from the vertex set V to a set of nonnegative integers, such that |f(u)-f(v)|/spl ges//spl delta//sub i/, if d(u,v)=i, for 1相似文献   

Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements

A many-to-many k-disjoint path cover (k-DPC) of a graph G is a set of k disjoint paths joining k distinct source-sink pairs in which each vertex of G is covered by a path. We deal with the graph G/sub 0/ /spl oplus/ G/sub 1/ obtained from connecting two graphs G/sub 0/ and G/sub 1/ with n vertices each by n pairwise nonadjacent edges joining vertices in G/sub 0/ and vertices in G/sub 1/. Many interconnection networks such as hypercube-like interconnection networks can be represented in the form of G/sub 0/ /spl oplus/ G/sub 1/ connecting two lower dimensional networks G/sub 0/ and G/sub 1/. In the presence of faulty vertices and/or edges, we investigate many-to-many disjoint path coverability of G/sub 0/ /spl oplus/ G/sub 1/ and (G/sub 0/ /spl oplus/ G/sub 1/) /spl oplus/ (G/sub 2/ /spl oplus/ G/sub 3/ ), provided some conditions on the Hamiltonicity and disjoint path coverability of each graph G/sub i/ are satisfied, 0 /spl les/ i /spl les/ 3. We apply our main results to recursive circulant G(2/sup m/, 4) and a subclass of hypercube-like interconnection networks, called restricted HL-graphs. The subclasses includes twisted cubes, crossed cubes, multiply twisted cubes, Mobius cubes, Mcubes, and generalized twisted cubes. We show that all these networks of degree m with f or less faulty elements have a many-to-many k-DPC joining any k distinct source-sink pairs for any k /spl ges/ 1 and f /spl ges/ 0 such that f+2k /spl les/ m - 1.     

A simple and fast parallel coloring for distance-hereditary graphs

In the literature, there are quite a few sequential and parallel algorithms to solve problems on distance-hereditary graphs. Two well-known classes of graphs, which contain trees and cographs, belong to distance-hereditary graphs. We consider the vertex-coloring problem on distance-hereditary graphs. Let T/sub d/(|V|, |E|) and P/sub d/d(|V|, |E|) denote the time and processor complexities, respectively, required to construct a decomposition tree representation of a distance-hereditary graph G=(V,E) on a PRAM model M/sub d/. Our algorithm runs in O(T/sub d/(|V|, |E|)+log|V|) time using O(P/sub d/(|V|, |E|)+|V|/log|V|) processors on M/sub d/. The best known result for constructing a decomposition tree needs O(log/sup 2/ |V|) time using O(|V|+|E|) processors on a CREW PRAM. If a decomposition tree is provided as input, we solve the problem in O(log |V|) time using O(|V|/log |V|) processors on an EREW PRAM. To the best of our knowledge, there is no parallel algorithm for this problem on distance-hereditary graphs.     

Learning capability and storage capacity of two-hidden-layer feedforward networks

The problem of the necessary complexity of neural networks is of interest in applications. In this paper, learning capability and storage capacity of feedforward neural networks are considered. We markedly improve the recent results by introducing neural-network modularity logically. This paper rigorously proves in a constructive method that two-hidden-layer feedforward networks (TLFNs) with 2/spl radic/(m+2)N (/spl Lt/N) hidden neurons can learn any N distinct samples (x/sub i/, t/sub i/) with any arbitrarily small error, where m is the required number of output neurons. It implies that the required number of hidden neurons needed in feedforward networks can be decreased significantly, comparing with previous results. Conversely, a TLFN with Q hidden neurons can store at least Q/sup 2//4(m+2) any distinct data (x/sub i/, t/sub i/) with any desired precision.     

L/sup p/ approximation of Sigma-Pi neural networks

A feedforward Sigma-Pi neural network with a single hidden layer of m neurons is given by /sup m//spl Sigma//sub j=1/c/sub j/g(n/spl Pi//sub k=1/x/sub k/-/spl theta//sub k//sup j///spl lambda//sub k//sup j/) where c/sub j/, /spl theta//sub k//sup j/, /spl lambda//sub k//spl isin/R. We investigate the approximation of arbitrary functions f: R/sup n//spl rarr/R by a Sigma-Pi neural network in the L/sup p/ norm. An L/sup p/ locally integrable function g(t) can approximate any given function, if and only if g(t) can not be written in the form /spl Sigma//sub j=1//sup n//spl Sigma//sub k=0//sup m//spl alpha//sub jk/(ln|t|)/sup j-1/t/sub k/.     

A strip-splitting-based optimal algorithm for decomposing a query window into maximal quadtree blocks

Decomposing a query window into maximal quadtree blocks is a fundamental problem in quadtree-based spatial database. Recently, Proietti presented the first optimal algorithm for solving this problem. Given a query window of size n/sub 1//spl times/n/sub 2/, Proietti's algorithm takes O(n/sub 1/) time, where n/sub 1/=max(n/sub 1/, n/sub 2/). Based on a strip-splitting approach, we present a new optimal algorithm for solving the same problem. Experimental results reveal that our proposed algorithm is quite competitive with Proietti's algorithm.     

Nearly Linear Time Minimum Spanning Tree Maintenance for Transient Node Failures

Given a 2-node connected, real weighted, and undirected graph $G=(V,E)$, with $n$ nodes and $m$ edges, and given a minimum spanning tree (MST) $T=(V,E_T)$ of $G$, we study the problem of finding, for every node $v \in V$, a set of replacement edges which can be used for constructing an MST of $G-v$ (i.e., the graph $G$ deprived of $v$ and all its incident edges). We show that this problem can be solved on a pointer machine in ${\cal O}(m \cdot \alpha(m,n))$ time and ${\cal O}(m)$ space, where $\alpha$ is the functional inverse of Ackermanns function. Our solution improves over the previously best known ${\cal O}(\min\{m \cdot \alpha(n,n), m + n \log n\})$ time bound, and allows us to close the gap existing with the fastest solution for the edge-removal version of the problem (i.e., that of finding, for every edge $e \in E_T$, a replacement edge which can be used for constructing an MST of $G-e=(V,E \backslash \{e\})$). Our algorithm finds immediate application in maintaining MST-based communication networks undergoing temporary node failures. Moreover, in a distributed environment in which nodes are managed by selfish agents, it can be used to design an efficient, truthful mechanism for building an MST.     

Designing and learning of adjustable quasi-triangular norms with applications to neuro-fuzzy systems

We introduce a new class of operators called quasi-triangular norms. They are denoted by H and parameterized by a parameter /spl nu/:H(a/sub 1/,a/sub 2/,...,a/sub n/;/spl nu/). From the construction of function H, it follows that it becomes a t-norm for /spl nu/=0 and a dual t-conorm for /spl nu/=1. For /spl nu/ close to 0, function H resembles a t-norm and for /spl nu/ close to 1, it resembles a t-conorm. In the paper, we also propose adjustable quasi-implications and a new class of neuro-fuzzy systems. Most neuro-fuzzy systems proposed in the past decade employ "engineering implications" defined by a t-norm as the minimum or product. In our proposition, a quasi-implication I(a,b;/spl nu/) varies from an "engineering implication" T{a,b} to corresponding S-implication as /spl nu/ goes from 0 to 1. Consequently, the structure of neuro-fuzzy systems presented in This work is determined in the process of learning. Learning procedures are derived and simulation examples are presented.     

A min-max approach to fuzzy clustering, estimation, and identification

This study, for any unknown physical process y=f(x/sub 1/,...,x/sub n/), is concerned with the: 1) fuzzy partition of n-dimensional input space X=X/sub 1//spl times//spl middot//spl middot//spl middot//spl times/X/sub n/ into K different clusters, 2) estimating the process behavior y/spl circ/=f(x/spl circ/) for a given input x/spl circ/=(x/spl circ//sub 1/,/spl middot//spl middot//spl middot/,x/spl circ//sub n/)/spl isin/X, and 3) fuzzy approximation of the process, with uncertain input-output identification data {(x(k)/spl plusmn//spl delta/x/sub k/),(y(k)/spl plusmn/v/sub k/)}/sub k=1,.../, using a Sugeno type fuzzy inference system. A unified min-max approach (that attempts to minimize the worst-case effect of data uncertainties and modeling errors on estimation performance), is suggested to provide robustness against data uncertainties and modeling errors. The proposed method of min-max fuzzy parameters estimation does not make any assumption and does not require a priori knowledge of upper bounds, statistics, and distribution of data uncertainties and modeling errors. To show the feasibility of the approach, simulation studies and a real-world application of physical fitness classification based on the fuzzy interpretation of physiological parameters, have been provided.     

图的树分解算法及其应用

一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。     

Computation of the frequency response of multilinear affine systems

Deals with the problem of computing the frequency response of an uncertain transfer function whose numerator and denominator polynomials are multiples of independent uncertain polynomials of the form P(s, q) = l/sub o/ (q) + l/sub 1/ (q) s + /spl middot//spl middot//spl middot/ + l/sub n/, (q) s/sup n/ whose coefficients depend linearly on q = [q/sub 1/, q/sub 2/, ..., q/sub q/]/sup T/ and the uncertainty box is Q = {q: q/sub i/ /spl epsiv/ [q/sub i/, q/sub i/], i = 1, 2,..., q}. Using the geometric structure of the value set of P(s, q), a powerful edge elimination procedure is proposed for computing the Bode, Nyquist, and Nichols envelopes of these uncertain systems. A numerical example is included to illustrate the benefit of the method presented.     

The critical role of environment in fatigue damage accumulation in deep-reactive ion-etched single-crystal silicon structural films

The importance of service environment to the fatigue resistance of n/sup +/-type, 10 /spl mu/m thick, deep-reactive ion-etched (DRIE) silicon structural films used in microelectromechanical systems (MEMS) was characterized by testing of electrostatically actuated resonators (natural frequency, f/sub 0/, /spl sim/40 kHz) in controlled atmospheres. Stress-life (S-N) fatigue tests conducted in 30/spl deg/C, 50% relative humidity (R.H.) air demonstrated the fatigue susceptibility of silicon films. Further characterization of the films in medium vacuum and 25% R.H. air at various stress amplitudes revealed that the rates of fatigue damage accumulation (measured via resonant frequency changes) are strongly sensitive to both stress amplitude and, more importantly, humidity. Scanning electron microscopy of high-cycle fatigue fracture surfaces (cycles to failure, N/sub f/>1/spl times/10/sup 9/) revealed clear failure origins that were not observed in short-life (N/sub f/<1/spl times/10/sup 4/) specimens. Reaction-layer and microcracking mechanisms for fatigue of silicon films are discussed in light of this empirical evidence for the critical role of service environment during damage accumulation under cyclic loading conditions.     

IR uncooled bolometers based on amorphous Ge/sub x/Si/sub 1-x/O/sub y/ on silicon micromachined structures

In this work, we present the fabrication of bulk micromachined microbolometers made of amorphous germanium-silicon-oxygen compounds (Ge/sub x/Si/sub 1-x/O/sub y/) grown by reactive sputtering of a Ge/sub 0.85/Si/sub 0.15/ target. We describe the complete procedure for fabricating thermally isolated microbolometers consisting of Ge/sub x/Si/sub 1-x/O/sub y/ sensing films deposited on sputtered silicon dioxide membranes suspended over a silicon substrate. The electrical properties of the sensitive material are set by controlling the deposition parameters of the sputtering technique. Under optimum deposition conditions, Ge/sub x/Si/sub 1-x/O/sub y/ layers with moderate electrical resistivity and thermal coefficient at room temperature as high as -4.2% /spl middot/ K/sup -1/ can be obtained. Isolated structures measured at atmospheric pressure in air have a thermal conductance of 3 /spl times/ 10/sup -6/ W /spl middot/ K/sup -1/ and a thermal capacitance of 6/spl middot/10/sup -9/ W /spl middot/ s /spl middot/ K/sup -1/, yielding a response time of 1.8 ms. Bolometers with an IR responsivity of 380 V /spl middot/ W/sup -1/ and a NEDT of 3.85 K at 100 nA bias current are obtained. The use of sputtered films allows designing a fully low-temperature fabrication process, wholly compatible with silicon integrated circuit technologies.     

Output regulation of periodic signals for DPS: an infinite-dimensional signal Generator

In this note, we consider output regulation and disturbance rejection of periodic signals via state feedback in the setting of exponentially stabilizable linear infinite-dimensional systems. We show that if an infinite-dimensional exogenous system is generating periodic reference signals, solvability of the state feedback regulation problem is equivalent to solvability of the so called equations. This result allows us to consider asymptotic tracking of periodic reference signals which only have absolutely summable Fourier coefficients, while in related existing work the reference signals are confined to be infinitely smooth. We also discuss solution of the regulator equations and construct the actual feedback law to achieve output regulation in the single-input-single-output (SISO) case: The output regulation problem is solvable if the transfer function of the stabilized plant does not have zeros at the frequencies i/spl omega//sub n/ of the periodic reference signals and if the sequence ([CR(i/spl omega//sub n/, A+BK)B]/sup -1/ /spl times/(Q/spl phi//sub n/-CR(i/spl omega//sub n/, A+BK)P/spl phi//sub n/)) /sub n/spl isin/z//spl isin/l/sup n2/. A one-dimensional heat equation is used as an illustrative example.     

Multihop all-to-all broadcast on WDM optical networks

Wavelength-division multiplexing (WDM) optical networks provide huge bandwidth by allowing multiple data streams transmitted simultaneously along the same optical fiber, with each stream assigned a distinct wavelength. A key issue on WDM optical networks is to minimize the number of wavelengths for communications. All-to-all broadcast (gossiping) is a fundamental communication application on computer/communication networks. It is known that the minimum numbers of wavelengths for realizing gossiping in one-hop of optical routing on the ring and the two-dimensional torus of N nodes are cN/sup 2/ and cN/sup 3/2/, c /spl ap/ 1/8, respectively. These numbers can be too large even for moderate values of N. One approach to reduce the number of wavelengths is to realize gossiping in multihops of routing. We give routing algorithms which realize gossiping in k-hops (k /spl ges/ 2) by O(N/sup 1+1/k/) wavelengths on the ring, O(N/sup 1+1/(2k)/) wavelengths on the 2D torus, and O(N/sup 1+1/(3k)/) wavelengths on the 3D torus on a simple multihop routing model. We also discuss the multihop routing for gossiping on a merge model. We give the upper bounds on the numbers of wavelengths for gossiping in two-hops and three-hops for the ring, 2D torus, and 3D torus on the merge model.     

网络拓扑的超能整循环图构造

循环图是一类重要的网络拓扑结构图,在并行计算和分布计算中发挥重要作用。图[G]的能量[E(G)]定义为图的特征值的绝对值之和。具有[n]个顶点的图[G]称为超能图如果图[G]的能量[E(G)>2n-2]。一个图称为循环图,若它是循环群上的Cayley图,即它的邻接矩阵是一个循环矩阵;整循环图是指循环图的特征值全为整数。借助Ramanujans和,利用Euler函数和Mobius函数,讨论了整循环图的超能性。利用Cartesian积图给出了一个构造超能整循环图的方法。     

Designing asymmetric Hopfield-type associative memory with higher order hamming stability

The problem of optimal asymmetric Hopfield-type associative memory (HAM) design based on perceptron-type learning algorithms is considered. It is found that most of the existing methods considered the design problem as either 1) finding optimal hyperplanes according to normal distance from the prototype vectors to the hyperplane surface or 2) obtaining weight matrix W=[w/sub ij/] by solving a constraint optimization problem. In this paper, we show that since the state space of the HAM consists of only bipolar patterns, i.e., V=(v/sub 1/,v/sub 2/,...,v/sub N/)/sup T//spl isin/{-1,+1}/sup N/, the basins of attraction around each prototype (training) vector should be expanded by using Hamming distance measure. For this reason, in this paper, the design problem is considered from a different point of view. Our idea is to systematically increase the size of the training set according to the desired basin of attraction around each prototype vector. We name this concept the higher order Hamming stability and show that conventional minimum-overlap algorithm can be modified to incorporate this concept. Experimental results show that the recall capability as well as the number of spurious memories are all improved by using the proposed method. Moreover, it is well known that setting all self-connections w/sub ii//spl forall/i to zero has the effect of reducing the number of spurious memories in state space. From the experimental results, we find that the basin width around each prototype vector can be enlarged by allowing nonzero diagonal elements on learning of the weight matrix W. If the magnitude of w/sub ii/ is small for all i, then the condition w/sub ii/=0/spl forall/i can be relaxed without seriously affecting the number of spurious memories in the state space. Therefore, the method proposed in this paper can be used to increase the basin width around each prototype vector with the cost of slightly increasing the number of spurious memories in the state space.     

Constant time dynamic programming on directed reconfigurablenetworks

Several dynamic programming algorithms are considered which can be efficiently implemented using parallel networks with reconfigurable buses. The bit model of general reconfigurable meshes with directed links, common write, and unit-time delay for broadcasting is assumed. Given two sequences of length m and n, respectively, their longest common subsequence can be found in constant time by an O(mh)×O(nh) directed reconfigurable mesh, where h=min{m, n}+1. Moreover, given an n-node directed graph G=(V, E) with (possibly negative) integer weights on its arcs, the shortest distances from a source node ν ϵ V to all other nodes can be found in constant time by an O(n²w) x O(n²w) directed reconfigurable mesh, where w is the maximum are weight     

Applications of k-local MST for topology control and broadcasting in wireless ad hoc networks

We propose a family of structures, namely, k-localized minimum spanning tree (LMST/sub k/) for topology control and broadcasting in wireless ad hoc networks. We give an efficient localized method to construct LMST/sub k/ using only O(n) messages under the local-broadcast communication model, i.e., the signal sent by each node would be received by all nodes within the node's transmission range. We also analytically prove that the node degree of the structure LMST/sub k/ is at most 6, LMST/sub k/ is connected and planar and, more importantly, the total edge length of the LMST/sub k/ is within a constant factor of that of the minimum spanning tree when k/spl ges/2 (called low weighted hereafter). We then propose another low weighted structure, called Incident MST and RNG Graph (IMRG), that can be locally constructed using at most 13n messages under the local broadcast communication model. Test results are corroborated in the simulation study. We study the performance of our structures in terms of the total power consumption for broadcasting, the maximum node power needed to maintain the network connectivity. We theoretically prove that our structures are asymptotically the best possible for broadcasting among all locally constructed structures. Our simulations show that our new structures outperform previous locally constructed structures in terms of broadcasting and power assignment for connectivity.     

Analysis and analytical modeling of static pull-In with application to MEMS-based voltage reference and process monitoring

The pull-in voltage of one- and two-degrees-of-freedom (DOF) structures has been symbolically and numerically analyzed with respect to drive mode dependence and hysteresis. Moreover, the time and temperature stability has been investigated and tested. Modeling results have been applied in the design of both folded-spring-suspended 1-DOF structures and single-side-clamped 2-DOF beams with a nominal pull-in voltage in the 5-10 V range and fabricated in an epi-poly process. Asymmetrically driven structures reveal pull-in close to the value predicted by the model (V/sub pi/ 1-DOF is 4.65 V analytically simulated and 4.56 V measured; V/sub pi/ 2-DOF is 9.24 V analytically simulated, 9.30 V in FEM and 9.34 V measured). Also the hysteresis is in close agreement (release voltage, V/sub r/, 1-DOF is 1.41 V analytically simulated and 1.45 V measured; V/sub r/ 2-DOF is 9.17 V analytically simulated, 9.15 V in FEM and 9.27 V measured). In symmetrically operated devices the differences between the computed and measured V/sub pi/ and V/sub r/ are much larger and are due to process dependencies, which make these devices very suitable for process monitoring. The 2-DOF asymmetrically operated device is the most suitable for MEMS-based voltage reference. The stability in time is limited by charge build-up and calls for a 100-hour initial burn-in. Temperature dependence is -100 /spl mu/V/K at V/sub pi//spl ap/5 V, however, is calculable and thus can be corrected or compensated.