A radio network is a distributed system with no central shared resource, consisting of n stations each equipped with a radio transceiver. One of the most important parameters to evaluate protocols in the radio networks is the number of awake time slots in which each individual station sends/receives a data packet. We are interested in devising energy-efficient initialization protocols in the single-hop radio network (RN, for short) that assign unique IDs in the range [1,n] to the n stations using few awake time slots. It is known that the RN can be initialized in O(log log n) awake time slots, with high probability, if every station knows the number n of stations in the RN. Also, it has been shown that the RN can be initialized in O(log n) awake time slots even if no station knows n. However, it has been open whether the initialization can be performed in O(log log n) awake time slots when no station knows n. Our main contribution is to provide the breakthrough: we show that even if no station knows n, the RN can be initialized by our protocol that terminates, with high probability, in O(n) time slots with no station being awake for more than O(log log n) time slots. We then go on to design an initialization protocol for the k-channel RN that terminates, with high probability, in O(n/k + (log n)2) time slots with no station being awake for more than O(log log n) time slots.

In this paper, we present a method to analyze the steady-state performance of a complex coefficient adaptive IIR notch filter which is useful for the rejection of multiple narrow-band interferences from broad-band signals in quadrature phase shift keying (QPSK) spread-spectrum communication systems. The adaptive notch filter based on the simplified gradient algorithm is considered. Analytical expressions have been developed for the conditional mean and variance of notch filter output. The signal-to-noise ratio improvement factor is also obtained from which the validity of the use of the notch filter can be concluded. Finally, the results of computer simulations are shown which confirm the theoretical predictions.

Most conventional studies on self-stabilization have been indifferent to the vulnerability under convergence. This paper investigates how mutual exclusion property can be achieved in self-stabilizing rings even for illegitimate configurations. We present a new method which uses a state with a large state space to detect faults. If some faults are detected, every process is reset and not given a privilege. Even if the reset values are different between processes, our protocol mimics the behavior of Dijkstra's unidirectional K-state protocol. Then we have a fast and safe mutual exclusion protocol. Simulation study also examines its performance.

If there exist any two vertices in G whose distance becomes longer when a vertex u is removed, then u is defined as a hinge vertex. Finding the set of hinge vertices in a graph is useful for identifying critical nodes in an actual network. A number of studies concerning hinge vertices have been made in recent years. In a number of graph problems, it is known that more efficient sequential or parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs in O(log n) time with O(n) processors on CREW PRAM for finding all hinge vertices of a trapezoid graph.

The advances in services using the present Internet mean that there will be increasing demand for Video on Demand (VoD) on the Internet in the near future. However, because of the best-effort characteristics of the Internet, it is important to suppress the degradation of communication quality caused by packet dropping when Internet traffic is congested. This paper focuses on MPEG transmission over the Internet, and suitable control mechanisms are established for an acceptable Quality of Service (QoS) improvement through detailed evaluation. Packets are classified using a frame-based scheme. The server applies the proposed End-to-End control scheme and shuffles the order of packets to avoid burst dropping, and may omit selected packets belonging to certain frames prior to forwarding. At the intermediate routers, transferred packets are transmitted according to Round Robin (RR) or Weighted Round Robin (WRR) scheduling, and are dropped statistically using selective Random Early Detection (RED) corresponding to frame attributes when there is congestion. We evaluate the proposed performance of transmission method using both computer simulations and empirical measurements of picture quality. The results show that when the traffic volume cannot be estimated in the intermediate routers, the combined use of RR, shuffling and conditional RED is effective, and when the traffic volume can be estimated, the combination of WRR, rate control and RED is effective.

In order for a service discipline to be used for guaranteed service networks at very high speed, its overall implementation must be scalable while it provides as wide a network schedulability region as possible. From this point of view, GPS-based service disciplines provide a narrow network schedulability region while EDF-based disciplines suffer from the implementation complexities of rate-controllers and admission control. Alternatively, although service disciplines based on service-curves can provide a wider network schedulability region than GPS-based and EDF-based disciplines, they may have even worse implementation complexities than EDF-based disciplines. In this paper, we propose to employ a service discipline based on our specific service-curves. We show that our service discipline has comparable implementation complexity to GPS-based disciplines while providing the same wide network schedulability region that EDF-based disciplines can provide. In fact, this service discipline is an SCED service discipline proposed in [14]. However, our specific service-curves provide the SCED service discipline with the same network schedulability region that EDF-based disciplines can provide, O(1) complexity for deadline calculation, and O(N) complexity for admission control where N is the number of sessions.

In this paper, we propose a new consolidation algorithm called the Selective Backward Resource Management (BRM) cell Feedback (SBF) algorithm. It achieves a fast response and low consolidation noise by selectively forwarding BRM cell from the most congested branch to the source instead of waiting from all branches. Mathematical models are derived to quantitatively characterize the performance, i.e. the response time and ACR of the source, of SBF and previously proposed algorithms. The interoperation of consolidation algorithms in point-to-multipoint available bit rate (ABR) is investigated. We address response time, consolidation noise and the effect of asymmetrical round trip delay (RTD) from branch point to destinations aspects. All combinations of four different consolidation algorithms are interoperated in both local/metropolitan area network (LAN/MAN) and wide area network (WAN) configuration. By a simulation method, we found that the consolidation algorithm used at the uppermost stream branch point, especially in WAN configuration, plays an important role in determining the performance of the network. However, consolidation algorithm used at the lower stream branch point affects the network performance insignificantly. Hence, in order to achieve a good and effective performance of the consolidation algorithms interoperated network, a fast response with low consolidation noise algorithm should be used at the uppermost stream branch point and a simple and easy to implement algorithm should be used at the lower stream branch point.

In this paper, we consider a network design problem with hub-and-spoke structure. We propose a relaxation technique for the problem where the location of hub nodes is given and decides the allocation of non-hub nodes to one of the hub nodes. We linearize the non-convex quadratic objective function of the original problem, introducing Hitchcock transportation problems defined for each pair of non-hub nodes. We provide two linear relaxation problems, one based on the Hitchcock transportation problems and the other on the dual Hitchcock transportation problems. We show the tightness of the lower bounds obtained by our formulations by computational experiences.

It is known that MUSIC and ESPRIT algorithms can estimate simultaneously both the instantaneous Direction of Arrival (DOA) and the instantaneous Angular Spread (AS) in multiple scattering environments. These algorithms use the Extended Array Mode Vector (EAMV) with complex angle. The previous work evaluated the performance of those algorithms by comparing the estimated DOA and the estimated AS with the DOA and the AS given in the EAMV, which uses the first-order approximation. Thus, this evaluation method has not clearly reflected the estimation accuracy of MUSIC and ESPRIT. This paper presents the joint estimation performance of MUSIC and ESPRIT by introducing the criteria for evaluation. For this, the spatial signature (SS) is reconstructed from the estimates of the DOA and the AS, and compared to the true SS in the meaning of data fitting.

We consider equalizer initialization problems when the transmitted symbol rate is higher than the available channel bandwidth. In this case, the coefficients of an adaptive equalizer in the receiver can be updated only once per a predefined symbol period, requiring unacceptably long training time. The training time can be reduced significantly if the equalizer begins the training process from a properly initialized condition. In this letter, a fast initialization method is analytically designed for a minimum mean squared error (MMSE) type equalizer. Finally, the initialization performance is verified by computer simulation.

Coloring problem is a well-known combinatorial optimization problem of graphs. This paper considers H-coloring problems, which are coloring problems with restrictions such that some pairs of colors can not be used for adjacent vertices. The restriction of adjacent colors can be represented by a graph H, i.e., each vertex represents a color and each edge means that the two colors corresponding to the two end-vertices can be used for adjacent vertices. Especially, H-coloring problem with a complete graph H of order k is equivalent to the traditional k-coloring problem. This paper presents sufficient conditions such that H-coloring problem can be reduced to an H-coloring problem, where H is a subgraph of H. And it shows a hierarchy about classes of H-colorable graphs for any complement graph H of a cycle of order odd n 5.

A new rewritable medium utilizing a guest-host (G-H) polymer-dispersed liquid-crystal (PDLC) film has been developed in our laboratory. The medium is thermally written and electrically erased. It is portable, like paper, and can store recorded data because of the memory effect of smectic-A liquid crystal (SmA LC), which exhibits bistable states of homeotropic and focal conic alignment. Dichroic dye is added to the SmA LC to form the G-H type. An evaluation of the characteristics revealed that this medium exhibits both high contrast and good reliability.

Since the invention of the RSA scheme, a lot of public-key encryption and signature schemes based on the intractability of integer factoring have been proposed. Most employ integers of the form N = p q, such as the RSA scheme, but some employ integers of the form N = pr q. It has been reported that RSA decryption speed can be greatly improved by using N = pr q integers for large r. On the other hand, Boneh et al. proposed a novel integer factoring method for integers such as N = pr q for large r. This factoring algorithm, the so-called Lattice Factoring Method, is based on the LLL-algorithm. This paper proposes a new method for factoring integers of the form N = pr q for large r and gives a new characterization of r such that factoring integers N = pr q is easier. More precisely, the proposed method strongly depends on the size and smoothness of the exponent, r. The theoretical consideration of and implementation of our method presented in this paper show that if r satisfies a certain condition our method is faster than both Elliptic Curve Method and Lattice Factoring Method. In particular, the theoretical consideration in this paper mainly employs the techniques described in the excellent paper by Adleman, Pomerance and Rumely that addresses primality testing.

Adaptive Fourier analysis of sinusoidal signals in noise is of essential importance in many engineering fields. So far, many adaptive algorithms have been developed. In particular, a filter bank based algorithm called constrained notch Fourier transform (CNFT) is very attractive in terms of its cost-efficiency and easily controllable performance. However, its performance becomes poor when the signal frequencies are non-uniformly spaced (or spaced with unequal intervals) in the frequency domain. This is because the estimates of the discrete Fourier coefficients (DFCs) in the CNFT are inevitably corrupted by sinusoidal disturbances in such a case. This paper proposes, at first, a modified CNFT (MCNFT), to compensate the performance of the CNFT for noisy sinusoidal signals with known and non-uniformly spaced signal frequencies. Next, performance analysis of the MCNFT is conducted in detail. Closed form expression for the steady-state mean square error (MSE) of every DFC estimate is derived. This expression indicates that the MSE is proportional to the variance of the additive noise and is a complex function of both the frequency of each frequency component and the pole radius of the bandpass filter used in the filter bank. Extensive simulations are presented to demonstrate the improved performance of the MCNFT and the validity of the analytical results.

In this letter, we present an output feedback controller design technique for uncertain discrete time systems with multiple time-delays. Based on Lyapunov second method, a sufficient condition for the robust stability of the system with a dynamic controller is derived in terms of the linear matrix inequality (LMI) with respect to design variables. The solutions of the LMIs can be easily obtained using existing efficient convex optimization techniques.

A uniform raised-salicide technology has been investigated using both uniform selective-epitaxial-growth (SEG) silicon and salicide films, to reduce a junction leakage current of shallow source/drain (S/D) regions for high-performance CMOS devices. The uniform SEG-Si film without pits is formed by using a wet process, which is a carbon-free oxide removal only using a dilute hydrofluoric acid (DHF) dipping, prior to the Si-SEG process. After a titanium-salicide formation using a conventional two-step salicide process, this uniform SEG-Si film achieves good S/D junction characteristics. The uniform titanium-salicide film without bowing into a silicon is formed by a smaller Ti/SEG-Si thickness ratio, which results in a low sheet resistance of 5 Ω/sq. without a narrow-line effect. Furthermore, the drive current is maximized by this raised-salicide film using a Ti/SEG-Si thickness ratio of 1.0.

A method for estimating propagation characteristics is described that uses the characteristics of pilot-data-inserted orthogonal frequency division multiplexing (OFDM) signal and is suitable for high-mobility OFDM transmission scheme. Several pilot data are inserted periodically along the frequency axis before the inverse fast Fourier transformation (IFFT) process in the transmitter. At the receiver, the received OFDM signal is correlated with a prepared distinctive OFDM signal in which several pilot data are inserted in the same positions as in the transmitted OFDM symbols and zeros are inserted in the other positions. The propagation characteristics can be estimated precisely and used to cancel any interference caused by delayed waves. Computer simulation shows that this method can estimate the propagation characteristics, which can then be used to cancel the interference caused by delayed waves before the FFT at the receiver under fast multipath fading conditions.

Ultra shallow low-resistive junction formation has been investigated for sub-100-nm MOSFETs using antimony implantation. The pileup at the Si/SiO2 interface and the resulting dopant loss during annealing is a common obstacle for antimony and arsenic to reduce junction sheet resistance. Though implanted arsenic gives rise to pileup even with a few seconds duration RTA (Rapid Thermal Annealing), antimony pileup was suppressed with the RTA at relatively low temperature, such as 800 or 900. As a result, low sheet resistance of 260 Ω/sq. was obtained for a 24 nm depth junction with antimony. These results indicate that antimony is superior to arsenic as a dopant for ultra shallow extension formation. However, increase in antimony concentration above 11020 cm-3 gives rise to precipitation and it limits the sheet resistance reduction of the antimony doped junctions. Redistribution behaviors of antimony relating to the pileup and the precipitation are discussed utilizing SIMS (Secondary Ion Mass Spectrometry) depth profiles.

A VLSI algorithm for division in GF(2m) with the canonical basis representation is proposed. It is based on the extended Binary GCD algorithm for GF(2m), and performs division through iteration of simple operations, such as shifts and bitwise exclusive-OR operations. A divider in GF(2m) based on the algorithm has a linear array structure with a bit-slice feature and carries out division in 2m clock cycles. The amount of hardware of the divider is proportional to m and the depth is a constant independent of m.

We consider the polymatroid packing and covering problems. The polynomial time algorithm with the best approximation bound known for either problem is the greedy algorithm, yielding guaranteed approximation factors of 1/k for polymatroid packing and H(k) for polymatroid covering, where k is the largest rank of an element in a polymatroid, and H(k)=Σi=1k 1/i is the kth Harmonic number. The main contribution of this note is to improve these bounds by slightly extending the greedy heuristics. Specifically, it will be shown how to obtain approximation factors of 2/(k+1) for packing and H(k)-1/6 for covering, generalizing some existing results on k-set packing, matroid matching, and k-set cover problems.