Search

Graph/network theory results are applicable to problems in communications. As a representative example, the node coloring problem in graph theory is applicable to the channel assignment problem in cellular mobile communication systems. The node coloring problem is NP-complete, meaning that optimally solving it is very difficult. Therefore, we use heuristic algorithms for the channel assignment problem. In this case, the graph theory results show the legitimacy of using heuristic techniques. On the other hand, we can directly apply graph theory to communication problems. For example, on contents delivery services in the Internet, we place mirror servers that provide the same contents on the network. Location problems on flow networks are applicable to mirror server allocation problems. In a simple case, we can efficiently solve the problem. In this paper, we concentrate on multi-hop wireless networks and consider the relationship between their problems and the results of graph/network theory.

Recently, the mulitihop wireless network system attracts the interest of many people as a communication network system of the next generation. The multihop wireless network has unique features in which neither base stations nor wired backbone networks are required and a terminal can communicate with the other terminal beyond the transmission range by multihopping. In this network, a communication link between two terminals which can communicate directly is required a channel. Since cochannel interference may occur, we need to assign channels to communication links carefully. In this paper, we describe a channel assignment strategy which takes the degree of cochannel interference into consideration, and we evaluate an effectiveness of this strategy by computer simulations. We show that this strategy is more effective than a strategy which does not take the degree of cochannel interference into consideration. And we also consider a few channel assignment algorithms briefly.

Wireless network systems introducing both of the cellular concept and the ad-hoc concept have been proposed. Communication between two nodes in a cell is guaranteed by relaying capability of the base station in these systems. Additionally, two nodes can directly communicate with each other while they are close to each other. We call this type of network a two-hop wireless network. The teletraffic performance of this network depends on various parameters such as the size of a cell, location of nodes, the communication range of nodes, channel assignment schemes, teletraffic behavior and so on. The purpose of this paper is to theoretically analyze the teletraffic performance of the network, which has been evaluated by computer simulation, by introducing a simple model. This paper shows a technique to analyze the performance in this model. Also, this paper considers the range in which the two-hop wireless network works well for the efficient use of channels.

This paper presents novel flooding schemes for wireless mobile ad hoc networks. Clustering of nodes is assumed as a basic ad hoc network structure. GWF (Gateway Forwarding) and SGF (Selected Gateway Forwarding) are presented based on clustering. A new protocol, termed FGS (Flooding Gateway Selection) protocol, between a cluster head and its gateways to realize SGF is presented. It is shown that SGF significantly improves the packet delivery performance in ad hoc networks by reducing flooding traffic.

This paper discusses the teletraffic characteristics of cellular systems using Dynamic Channel Assignment. In general, it is difficult to exactly and theoretically analyze the teletraffic characteristics of Dynamic Channel Assignment. Also, it is not easy to theoretically evaluate influence of mobility on the traffic characteristics. This paper proposes approximate techniques to analyze teletraffic characteristics of Dynamic Channel Assignment considering mobility. The proposed techniques are based on Clique Packing approximation.

In a multihop network, radio packets are often relayed through inter-mediate stations (repeaters) in order to transfer a radio packet from a source to its destination. We consider a scheduling problem in a multihop network using a graphtheoretical model. Let D=(V,A) be the digraph with a vertex set V and an arc set A. Let f be a labeling of positive integers on the arcs of A. The value of f(u,v) means a frequency band assigned on the link from u to v. We call f antitransitive if f(u,v) ≠ f(v,w) for any adjacent arcs (u,v) and (v,w) of D. The minimum antitransitive-labeling problem is the problem of finding a minimum antitransitive-labeling such that the number of integers assigned in an antitransitive labeling is minimum. In this paper, we prove that this problem is NP-hard, and we propose a simple distributed approximation algorithm for it.

This paper proposes two numerical methods to solve the optimal problem of contrast enhancement in the cross-pol and co-pol channels. For the cross-pol channel case, the contrast (power ratio) is expressed in a homogeneous form, which leads the polarimetric contrast optimization to a distinctive eigenvalue problem. For the co-pol channel case, this paper proposes a cross iterative method for optimization, based on the formula used in the matched-pol channel. Both these numerical methods can be proved as convergent algorithms, and they are effective for obtalning the optimum polarization state. Besides, one of the proposed methods is applied to solve the optimal problem of contrast enhancement for the time-independent targets case. To verify the proposed methods, this paper provides two numerical examples. The results of calculation are completely identical with other authors', showing the validity of the proposed methods.

This paper describes two dimensional (2D) equalization scheme of orthogonal coding multi-carrier CDMA for reverse link of mobile communication systems. The purpose of the 2D equalization is the reduction of Multiple Access Interference (MAI) which is caused by the random access and the different propagation path from each mobile station. The orthogonal coding multi-carrier CDMA multiplexes all mobile stations' data by Code Division Multiplexing (CDM). The 2D coding scheme spreads a preamble signal at time (in subchannel signals) and frequency (between subchannel signals) domains. The 2D decoding scheme estimates transmission delay time and instantaneous fading frequency from preamble signal for individual mobile stations and compensate the received data using these estimation values to reduce MAI.

The lower-bounded p-collection problem is the problem where to locate p sinks in a flow network with lower bounds such that the value of a maximum flow is maximum. This paper discusses the cover problems corresponding to the lower bounded p-collection problem. We consider the complexity of the cover problem, and we show polynomial time algorithms for its subproblems in a network with tree structure.

This paper describes a delay control scheme for synchronous detection of an orthogonal coding multi-carrier CDMA (Code Division Multiple Access) system. The delay control scheme estimates transmission timing of data from each mobile station. At a base station, delay time is obtained by detecting phase shift value of the preamble signal from each mobile station. The estimated transmission timing information is sent from base station to each mobile station and the mobile station then adjusts its transmission timing. Simulation results clarified that Bit Error Rate (BER) is 2.5 × 10-3 at 19dB of Eb/No under conditions of 29.4 msec initial delay time, 32kbit/sec data rate, 16 subchannels and 100Hz of fading frequency.

In this paper we extend the p-collection problem to a flow network with lower bounds, and call the extended problem the lower-bounded p-collection problem. First we discuss the complexity of this problem to show NP-hardness for a network with path structure. Next we present a linear time algorithm for the lower-bounded 1-collection problem in a network with tree structure, and a pseudo-polynomial time algorithm with dynamic programming type for the lower-bounded p-collection problem in a network with tree structure. Using the pseudo-polynomial time algorithm, we show an exponential algorithm, which is efficient in a connected network with few cycles, for the lower-bounded p-collection problem.

Location theory on networks is concerned with the problem of selecting the best location in a specified network for facilities. Many studies for the theory have been done. We have studied location theory from the standpoint of measuring the closeness between two vertices by the capacity (maximum flow value) between two vertices. In a previous paper, we have considered location problems, called covering problems and proposed polynomial time algorithms for these problems. These problems are applicable to assigning files to some computers in a computer network. This paper is concerned with a covering problem called the single cover problem defined in the previous paper. First, we define a generalized single cover problem and show that an algorithm proposed in the previous paper can be applicable to solving the generalized single cover problem. Then, we define a single cover problem satisfying cardinality constrains and show that the problem is solved in a polynomial time.

The p-collection problem is where to locate p sinks in a flow network such that the value of a maximum flow is maximum. In this paper we show complexity results of the p-collection problem. We prove that the decision problem corresponding to the p-collection problem is strongly NP-complete. Although location problems (the p-center problem and the p-median problem) in networks and flow networks with tree structure is solvable in polynomial time, we prove that the decision problem of the p-collection problem in networks with tree structure, is weakly NP-complete. And we show a polynomial time algorithm for the subproblem of the p-collection problem such that the degree sum of vertices with degree ≧ 3 in a network, is bound to some constant K ≧ 0.

This paper describes communication traffic characteristics in cellular systems employing the concept of reuse partitioning and Dynamic Channel Assignment. Such systems have a problem of the spatial unbalance of blocking probability. The objective of this paper is overcoming this problem. To accomplish this objective, we use a method for analyzing communication traffic characteristics. We also show results on traffic characteristics in the systems.

A new superresolution technique is proposed for high-resolution estimation of the scattering analysis. For complicated multipath propagation environment, it is not enough to estimate only the delay-times of the signals. Some other information should be required to identify the signal path. The proposed method can estimate the frequency characteristic of each signal in addition to its delay-time. One method called modified (Root) MUSIC algorithm is known as a technique that can treat both of the parameters (frequency characteristic and delay-time). However, the method is based on some approximations in the signal decorrelation, that sometimes make problems. Therefore, further modification should be needed to apply the method to the complicated scattering analysis. In this paper, we propose to apply a time-domain null filtering scheme to reduce some of the dominant signal components. It Can be shown by a simple experiment that the new technique can enhance the estimation accuracy of the frequency characteristic in the Root-MUSIC algorithm.

This paper applied the polarimetric filtering principle to Synthetic Aperture Radar (SAR) image sets in three possible polarimetric radar channels and compared the resultant imagery. The polarimetric radar channels in consideration here are Co-Pol, Cross (X)-pol, and Matched (M)-pol channels. Each channel has its own polarimetric characteristics for imaging. Using the formulation of the contrast enhancement factors based on the Stokes vector formalism, polarimetric enhanced images for three channels are shown using NASA JPL DC-8 AIRSAR data sets (CC0045L, Bonanza Creek, AK/USA). It is shown that the optimally enhanced Co- and X-Pol channel images play a decisive role in imaging in a complex featured background.

We need to solve various mobility problems in 1-dimensional, 2-dimensional, and 3-dimensional micro- or pico-cell environments for efficiently planning personal communications services. However, mobility problems have been thus far studied in 1- and 2-dimensional cell structures. In this paper, we extend the previous mobility modeling from 1- or 2-dimensional space to 3-dimensional indoor building environments by considering proper boundary conditions on each floor and analytically model the mobility in the multi-story buildings to estimate the number of handoffs and then verify this mathematical model by computer simulations. The computer simulation results agree very well with the analytical ones. These results can be utilized in the network plannings of future personal communications services.

The applicability of Dynamic Channel Assignment methods to a Reuse Partitioning system in cellular radio systems is investigated in this paper. The investigations indicate that such a system has a tendency to increase the difference between blocking probability for the partitioning two coverage areas in comparison with the conventional Reuse Partitioning system employing Fixed Channel Assignment method. Two schemes using new Channel Rearrangement algorithms are also proposed in order to alleviate the difference as a disadvantage which gives unequal service to the system. The simulation results show that the proposed schemes are able to reduce the difference significantly while increasing the carried traffic by 10% as compared with the conventional system.

A novel algorithm, as an advanced Hybrid Channel Assignment strategy, for channel assignment problem in a cellular system is proposed. A difference from the conventional Hybrid Channel Assignment method is that flexible fixed channel allocations which are variable through the channel assignment can be performed in order to cope with varying traffic. This strategy utilizes the Channel Rearrangement technique using the artificial neural network algorithm in order to enhance channel occupancy on the fixed channels. The strategy is applied to two simulation models which are the spatial homogeneous and inhomogeneous systems in traffic. The simulation results show that the strategy can effectively improve blocking probability in comparison with pure dynamic channel assignment strategy only with the Channel Rearrangement.

This paper presents an experimental result of polarimetric detection of objects buried in a sandy ground by a synthetic aperture FM-CW radar. Emphasis is placed on the reduction of surface clutter by the polarimetric radar, which takes account of full polarimetric scattering characteristics. First, the principle of full polarimetric imaging methodology is out-lined based on the characteristic polarization states for a specific target together with a polarimetric enhancement factor which discriminates desired and undesired target echo. Then, the polarimetric filtering technique which minimizes a surface reflection is applied to detect a thin metallic plate embedded in a sandy ground, demonstrating the potential capability of reducing surface clutter which leads to an improvement of underground radar performance, and validating the usefulness of FM-CW radar polarimetry.

The demand for mobile communication services is rapidly increasing, because the mobile communication service is synonymy of an ideal communication style realizing communication in anytime, anywhere and with anyone. The development of economic and social activities is a primary factor of the increasing demand for mobile communication services. The demand stimulates the development of technology in mobile communication including personal communication services. Thus mobile communication has been one of the most active research in communications in the last several years. There exist various problems to which graph & network theory is applicable in mobile communication services (for example, channel assignment algorithm in cellular system, protocol in modile communication networks and traffic control in mobile communication ). A model of a cellular system has been formulated using a graph and it is known that the channel assignment problem is equivalent to the coloring problem of graph theory. Recently, two types of coloring problems on graphs or networks related to the channel assignment problem were proposed. Mainly, we introduce these coloring problems and show some results on these problems in this paper.

This paper applies the principle of radar polarimetry to the synthetic aperture frequency modulated continuous wave radar. First, the principle of monochromatic wave radar polarimetry using scattering matrix and polarization ratio necessary for introducing polarimetric imaging is given. In order to accommodate this principle to a wideband radar, a scattering matrix must be introduced, because FM-CW radar utilizes a wideband signal. This paper points out that the polarimetric target reflection coefficient obtained by the synthetic aperture FM-CW radar works as the scattering matrix element. This replacement, i.e., polarimetric reflection coefficient = the scattering matrix element, was verified by an experiment based on the polarization ratio which maximizes and minimizes a target. A radar system operative in the microwave X-band was successfully applied to the polarimetric detection of a metallic pipe of different orientations, demonstrating the validity of FM-CW radar polarimetry, and indicating an establishment of full polarimetric radar system.

An FM-CW radar system for the detection of objects buried in sandy ground is explored and is applied to a field measurement. The key factors for underground FM-CW radar performance are the center frequency and bandwidth determining the depth at which the radar can detect targets and the resolution in the range direction. In order for FM-CW radar sounding, two ridged horn antennas are employed in the system, which are operative in the frequency range of 250-1000 MHz. The impedance matching to the ground is optimized by measuring the echo strength from a fixed target as a function of the spacing interval between the antenna aperture and the ground surface. It is shown that the radar with an output power of 18 dBm could detect a metallic plate (30×100 cm) and a pipe (10 cmφ) buried at the depth of 1.2 m. Also the synthetic aperture technique together with an averaging and subtracting method produced fine image in shallow region up to 100 cm in the sandy ground.

In a cellular system for mobile communications, every service area is divided into a number of cells for utilizing the frequency spectrum efficiently. Service areas for such systems are two dimensional, however, the analysis of the characteristics of the communication traffic for the areas are quite complicated, since the motion of the vehicles in the area can not be predicted precisely. For making the analysis easily, the areas are assumed to be band-shaped like a highway. Furthermore, in the analysis, the traffic offered to a cell is assumed to be stationary. In actual systems, the density of vehicles and the offered communication traffic is not stationary, so that many differences exist between the analysis and the actual systems. This paper presents an analysis method using state equations. The equations represent the transient characteristics of mobile communication traffic when a band-shaped service area is assumed. The transition is made by accidents or congestion, and causes the rapid offered traffic change in a communication system. In the method, numerical analysis is made under the consideration of "handoff" operation. The operation consists of surrendering the channel used in the previous cell and reassigning a new channel when the vehicle crosses the cell boundary. The analytical results are compared with the simulations, and the two results show good agreement. The method presented in this paper can be used for designing the switching system when the offered traffic changes rapidly due to accidents or congestion.

Location theory on networks is concerned with the problem of selecting the best location in a specified network for facilities. Many studies for the theory have been done. However, few studies treat location problems on networks from the standpoint of measuring the closeness between two vertices by the capacity (maximum flow value) between two vertices. This paper concerns location problems, called covering problems on flow networks. We define two types of covering problems on flow networks. We show that covering problems on undirected flow networks and a covering problem on directed flow networks are solved in polynomial times.

In a cellular mobile system, assigning a channel for a call in a cell so as to achieve high spectral efficiency is an important problem. In usual channel assignment for a cellular mobile system, a channel can be simultaneously assigned to some cells with a constant separation distance. This usual model of a cellular mobile system has been formulated using a graph and it is known that the channel assignment problem is equivalent to the coloring problem of graph theory. Recently, a new channel assignment scheme has been proposed. This scheme takes the degree of interference into consideration. In the scheme, a channel is simultaneously assigned if the CIR (carrier-to-interference ratio) is more than the desired value. In this paper, we formulate this new model using a network and a new coloring problem of networks. The new coloring problem of networks is a generalization of the usual coloring problem of graphs. One of the merits of this formulation is that the degree of cochannel interference between cells can be represented. In the usual formulation using a graph, the degree of cochannel interference between cells can not be represented. Therefore, spectral efficiency in the formulation using a network is higher than spectral efficiency in the formulation using a graph. In this paper, we show that the new coloring problem is an NP-hard problem. Subsequently, we rewrite the new coloring problem of networks to a coloring problem of graphs on some assumptions and consider the relation between the results on the new coloring and the results on the usual coloring.

In location problems, the outtransmission and intransmission numbers are important indices to evaluate a directed network. We formulate and consider a new problem of fault diagnosis in a system modeled by a directed network in which to each edge a positive real number called the length of edge is assigned and to each vertex a positive real number called the weight of vertex is assigned. By a fault in a directed network, we mean any increase in the length of an edge with respect to its nominal length. A theory and an algorithm for detecting a fault edge in a directed network in which the above indices, i.e. outtransmission and/or intransmission numbers, are measurable, are presented.

We introduce the distance between two edges in a graph (nondirected graph) as the minimum number of edges in a tieset with the two edges. Using the distance between edges we define the eccentricity ε_τ (e_j) of an edge e_j. A finite nonempty set J of positive integers (no repetitions) is an eccentric set if there exists a graph G with edge set E such that ε_τ (e_j) ∈J for all e_i ∈E and each positive integer in J is ε_τ (e_j) for some e_j ∈E.. In this paper, we give necessary and sufficient conditions for a set J to be eccentric.

Location theory on networks is concerned with the problem of selecting the best location in a specified network for facilities. In networks, the distance is an important measure to quantify how strongly related two vertices are. Mereover, the capacity between two vertices is also an important measure. In this paper, we define the location problems called the p-center problem, the r-cover problem and the p-median problem on undirected flow networks. We propose polynomial time algorithms to solve these problems.

The synchronic distance is a fundamental concept in a Petri net. Marked graphs form a subclass of Petri nets. Given a matrix D, we are interested in the problem of finding a marked graph whose synchronic distance matrix is D. It is wellknown that the synchronic disrance matrix of a marked graph is a distance matrix. In this letter, we give a matrix D such that D is a distance matrix and there does not exist a marked graph whose synchronic distance matrix is D.

Consider a connected network N. With each edge of N we associate a nonnegative real number called the length of the edge. Let N be a network obtained from N by adding new edges and/or by decreasing the lengths of some edges. For a generalized transmission number cf(N, v) defined on vertex v in N, we call Δc(v)=cf(N, v)-cf(N ,v) the Sabidussi difference of vertex v. In this note, we present a new theorem and its corollaries on the Sabidussi difference.

The efficient use of frequency spectrum is one of the most important problems in mobile radio communication systems. In a small zone system (the so-called cellular system), the algorithm used to make the channel assignment for a call has a great effect on system performance (traffic characteristics). This paper presents the relationships between the traffic-carrying capacity and the graph which represents the relation among a zone and its buffer zones in the system. Furthermore, using these relationships, an algorithm for the dynamic frequency (channel) assignment which has all channel available at all base stations is proposed. The performance characteristics of this algorithm obtained from computer simulations are also presented. The computer simulation treats the two examples (systems), one is the system in which the mobile units does not cross a zone boundary during a communication (the zone size is sufficiently large and the probability of the occurrence can be neglected.), the other is the system in which the mobile unit may cross a zone boundary during a communication. The results from these simulations show that the algorithm carries more traffic per channel at a given blocking rate than the RING method.