The radiation patterns are synthesized by properly disposing surface variations on dielectric rod waveguides. The genetic algorithm (GA) is applied for searching the optimum disposition of variation sections. A very fast calculation method used in the optimization is presented. The guided waves are related in the form of a 2-port circuit and the radiation field is expressed by superposition of the waves from variation sections. Various conical beams can be synthesized. Short variation sections and combination of several variation sections with different height are used to improve the synthesis performance. The ripple of the mainlobe and the sidelobe levels become small. Spherical sector patterns with a steep fall are synthesized and the agreement with the experimental values is confirmed.

This paper describes a rhythm pattern accuracy diagnosis system based on the rhythm pattern matching algorithm and a diagnosis feedback method by employing the SVM technique. A beat rhythm pattern is recorded by a PC and analyzed with an algorithm including cluster-analysis-based pattern matching. Rhythm performance is represented by a performance feature vector, which features note length deviation, note length instability, and tempo instability. The performance feature vector is effective for objectively evaluating the accuracy of rhythm patterns objectively. In addition, this system has the music experts' knowledge base, which is calculated from the performance feature vectors associated with the experts' subjective evaluation by listening to the performance. The system generates both an objective measuring report, and experts' comments for learners. Reproductivity of experts' comments is statistically indicated to be excellent for eight rhythm patterns, two tempo levels, and eight users. Reliability of experts' comments are also described considering the threshold of the decision function of SVM. Subjective evaluation of the system is carried out by fifteen users by a questionnaire using the SD method. As a result of factor analysis for the sixteen questions, four factors named "Audio-visual representation," "User-friendliness," "Reliability," and "Window representation," are extracted. Users' four factor scores indicate that the system is reliable and easy to use.

This paper discusses encoding of vehicular position information using predictive algorithms in inter-vehicle communications (IVC) from the viewpoints of source coding and noisy channels. Two vehicular driving models are assumed; one is the 15-mode as a suburban rapid transit driving pattern, the other is called calming mode as a street-driving pattern. Three types of schemes are compared; a pulse code modulation (PCM) scheme, a predictive coding (PC) scheme, and the variable interval prediction (VIP) scheme that is proposed here. This paper assumes that precise position information is got from a positioning system, and that all the transmitters and receivers have common predictors. Performance comparisons of the three types of schemes are carried out both of noiseless and noisy channels. Results show that the VIP scheme is superior to any other scheme.

A siphon-trap of a Petri net N is defined as a place set S with S = S, where S = { u| N has an edge from u to a vertex of S} and S = { v| N has an edge from a vertex of S to v}. A minimal siphon-trap is a siphon-trap such that any proper subset is not a siphon-trap. The following polynomial-time algorithms are proposed: (1) FDST for finding, if any, a minimal siphon-trap or even a maximal class of mutually disjoint minimal siphon-traps of a given Petri net; (2) FDSTi that repeats FDST i times in order to extract more minimal siphon-traps than FDST. (3) STFM_T (STFM_Ti, respectively) which is a combination of the Fourier-Motzkin method and FDST (FDSTi) and which has high possibility of finding, if any, at least one minimal-support nonnegative integer invariant.

Multiple access interference (MAI) due to many simultaneous users is the main factor that limits the performance of DS-CDMA system. Multiuser detection is a method to avoid performance degradation due to MAI. We propose a blind multiuser detection method based on the algorithm consisting of two-stage decoding process, i.e., linearly constrained constant modulus (LCCM) and iterative least squares (ILS). The computer simulations confirmed that the algorithm is near-far resistant and that the proposed method is effective in the application to the slow fading channels.

In this work we study the performance of a distributed GA that incorporates in its core parallel cooperative-competitive genetic operators. A series of controlled experiments are conducted using various large and difficult 0/1 multiple knapsack problems to test the robustness of the distributed GA. Simulation results verify that the proposed distributed GA compared with a canonical distributed GA significantly gains in search speed and convergence reliability with less communication cost for migration.

In this paper, we investigate the optimal assignment problem of cells in PCS (Personal Communication Service) to switches on a ATM (Asynchronous Transfer Mode) network. Given cells and switches on an ATM network (whose locations are fixed and known), the problem is to group cells into clusters and assign these clusters to switches in an optimum manner. This problem is modeled as a complex integer programming problem. Since finding an optimal solution of this problem is NP-hard, a heuristic solution model consists of three phases (Cell Pre-Partitioning Phase, Cell Exchanging Phase, and Cell Migrating Phase) is proposed. Experimental results show that Cell Exchanging and Cell Migrating Phases can really reduce total cost near 44% on average.

A plane drawing of a graph is called a floorplan if every face (including the outer face) is a rectangle. A based floorplan is a floorplan with a designated base line segment on the outer face. In this paper we give a simple algorithm to generate all based floorplans with at most n faces. The algorithm uses O(n) space and generates such floorplans in O(1) time per floorplan without duplications. The algorithm does not output entire floorplans but the difference from the previous floorplan. By modifying the algorithm we can generate without duplications all based floorplans having exactly n faces in O(1) time per floorplan. Also we can generate without duplications all (non-based) floorplans having exactly n faces in O(n) time per floorplan.

We propose two novel blind LMS algorithms, called exponential step size LMS algorithms (ES-LMS), for adaptive array antennas with fast convergence speeds. Both of the proposed algorithms are much better at tracking signal sources than the conventional LMS algorithms. In addition, they require neither spatial knowledge nor reference signals since they use the finite symbol property of digital signal. Computer simulations verify performances of the two proposed algorithms.

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.

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.

A Wireless Sensor Network (WSN, for short) is a distributed system consisting of n sensor nodes and a base station. In this paper, we propose an energy-efficient protocol to initialize the sensor nodes in a WSN, that is, to assign a unique ID to each sensor node. We show that if an upper bound u on the number n of sensor nodes is known beforehand, for any f 1 and any small µ (0<µ<1), a WSN without collision detection capability can be initialized in O((log (1/µ) + log f)u1+µ) time slots, with probability exceeding 1-(1/f), with no sensor node being awake for more than O(log (1/µ)+ log f) time slots.

When a randomized algorithm elects a leader on anonymous networks, initial information (which is called in general initial condition in this paper) of some sort is always needed. In this paper, we study common properties of initial conditions that enable a randomized algorithm to elect a leader. In the previous papers, the author introduced the notion of transformation between initial conditions using distributed algorithms. By using this notion of transformation, we investigate the property of initial conditions for the leader election. We define that an initial condition C is p(N)-complete if there exists some randomized algorithm that elects a leader with probability p(N) on any size N network satisfying C. We show that we can divide p(N)-completeness into four types as follows. 1. p(N)=1: For any 1-complete initial conditions, there exists a deterministic distributed algorithm that can compute the size of the network for any initial information satisfying the initial condition. 2. inf p(N) >0: For any p(N)-complete initial conditions with inf p(N) >0, there exists a deterministic distributed algorithm that can compute an upper-bound for the size of the network for any initial information satisfying the initial condition. 3. inf p(N) converges to 0: The set of p(N)-complete initial conditions varies depending on the decrease rate of p(N). 4. p(N) decreases exponentially: Any initial condition is regarded as p(N)-complete.

In this paper we addresses the problem of finding feasible solutions for the Group Multicast Routing Problem (GMRP). This problem is a generalization of the multicast routing problem whereby every member of the group is allowed to multicast messages to other members from the same group. The routing problem involves the construction of a set of low cost multicast trees with bandwidth requirements for all the group members in the network. We first prove that the problem of finding feasible solutions to GMRP is NP-complete. Following that we propose a new heuristic algorithm for constructing feasible solutions for GMRP. Simulation results show that our proposed algorithm is able to achieve good performance in terms of its ability of finding feasible solutions whenever one exist.

Constant Modulus Algorithm (CMA) is a method that has been widely known as blind adaptive beamforming because it requires no knowledge about the signal except that the transmitted signal waveform has a constant envelope. Although CMA has the merit of this blind operation, it possesses problems in its convergence property. In this paper, problems that are inherent to this algorithm is resolved using a combination of CMA and another major adaptive algorithm SMI (Sample Matrix Inversion). The idea is to use SMI to determine the initial weights for CMA operation. Although the benefit of CMA being a blind algorithm is not fully taken advantage of, good aspects of both SMI and CMA can be introduced. By using this approach, two major problems in convergence properties of CMA can be solved. One of these problems is the reliability and this relates to the convergence performance in certain cases. When the interfering signal is stronger than the desired signal, the algorithm tends to come up with the wrong solution by capturing the interfering signal which has the stronger power. Also, the convergence time of this algorithm is slow, limiting its application in dynamic environment, although the slow convergence time of CMA has been studied previously and several methods have been proposed to overcome this defect. Using the proposed method, the deterioration due to both of these problems can be mitigated. Simulation results are shown to confirm the theory. Furthermore, evaluations are done concerning the fading characteristics. It is also confirmed from the simulation that the tracking performance of this method can be regarded as sufficient in personal mobile communication.

The k-vertex-connectivity augmentation problem for a specified set of vertices of a graph with degree-unchangeable vertices, kVCA(G,S,D), is defined as follows: "Given a positive integer k, an undirected graph G=(V,E), a specified set of vertices S V and a set of degree-changeable vertices D V, find a smallest set of edges E such that the vertex-connectivity of S in (V,E E) is at least k and E {(u,v) u,v D}. " The main result of the paper is that checking the existence of a solution and finding a solution to 2VCA(G,S,D) or 3VCA(G,S,D) can be done in O(|V|+|E|) or O(|V|(|V|+|E|)) time, respectively.

We study the performance of oblivious routing algorithms that follow minimal (shortest) paths, referred to as minimal oblivious routing algorithms in this paper, using competitive analysis on a d-dimensional, N = 2d-node hypercube. We assume that packets are injected into the hypercube arbitrarily and continuously, without any (e.g., probabilistic) assumption on the arrival pattern of the packets. Minimal algorithms reduce the total load in the network in the first place and they preserve locality. First we show that the well known deterministic oblivious routing algorithm, namely, the greedy routing algorithm, has competitive ratio Ω(N1/2). Then we show a problem lower bound of Ω(Nlog 2 (5/4)/log5 N). We also give a natural randomized minimal oblivious routing algorithm whose competitive ratio is close to the problem lower bound we provide.

This paper introduces a generalized cyclic convolution which can be implemented via the conventional cyclic convolution system by the discrete Fourier transform (DFT) with pre-multiplication for the input and post-multiplication for the output. The generalized cyclic convolution is applied for computing a negacyclic convolution. Comparison shows that the proposed implementation is more efficient and simpler in structure than other methods. The modified Fermat number transform (MFNT) is known to be useful for computing a linear convolution of integer-valued sequences. The generalized cyclic convolution is also applied for generalizing the linear convolution system by MFNT, and easing the signal length restriction imposed by the system.

We call a network an anonymous network, if each vertex of the network is given no ID's. For distributed algorithms for anonymous networks, solvable problems depend strongly on the given initial conditions. In the past, initial conditions have been investigated, for example, by computation given the number of vertices as the initial condition, and in terms of what initial condition is needed to elect a leader. In this paper, we study the relations among initial conditions. To achieve this task, we define the relation between initial conditions A and B (denoted by A B) as the relation that some distributed algorithm can compute B on any network satisfying A. Then we show the following property of this relation among initial conditions. The relation is a partial order with respect to equivalence classes. Moreover, over initial conditions, it induces a lattice which has maxima and minima, and contains an infinite number of elements. On the other hand, we give new initial conditions k-LEADER and k-COLOR. k-LEADER denotes the initial condition that gives special condition only to k vertices. k-COLOR denotes the initial condition that divides the vertices into k groups. Then we investigate the property of the relation among these initial conditions.

A distributed system is said to be self-stabilizing if it converges to some legitimate state from an arbitrary state in a finite number of steps. The number of steps required for convergence is usually referred to as the stabilization time, and its reduction is one of the main performance issues in the design of self-stabilizing systems. In this paper, we propose an automated method for computing the stabilization time. The method uses Boolean functions to represent the state space in order to assuage the state explosion problem, and computes the stabilization time by manipulating the Boolean functions. To demonstrate the usefulness of the method, we apply it to the analysis of existing self-stabilizing algorithms. The results show that the method can perform stabilization time analysis very fast, even when an underlying state space is very huge.