In this paper, we propose a discrete competitive Hopfield neural network (DCHNN) for the cellular channel assignment problem (CAP). The DCHNN can always satisfy the problem constraint and therefore ...guarantee the feasibility of the solutions for the CAP. Furthermore, the DCHNN permits temporary energy increases to escape from local minima by introducing stochastic dynamics. Simulation results show that the DCHNN has superior ability for the CAP within reasonable number of iterations.
The paper deals with the channel assignment problem in a hexagonal cellular network with two-band buffering, where channel interference does not extend beyond two cells. Here, for cellular networks ...with homogeneous demands, we find some lower bounds on the minimum bandwidth required for various relative values of s/sub 0/, s/sub 1/, and s/sub 2/, the minimum frequency separations to avoid interference for calls in the same cell, or in cells at distances of one and two, respectively. We then present an algorithm for solving the channel assignment problem in its general form using the elitist model of genetic algorithm (EGA). We next apply this technique to the special case of hexagonal cellular networks with two-band buffering. For homogeneous demands, we apply EGA for assigning channels to a small subset of nodes and then extend it for the entire cellular network, which ensures faster convergence. Moreover, we show that our approach is also applicable to cases of nonhomogeneous demands. Application of our proposed methodology to well-known benchmark problems generates optimal results within a reasonable computing time.
This paper presents an efficient heuristic algorithm for the channel assignment problem in cellular radio networks. The task is to find channel assignment with minimum frequency bandwidth necessary ...to satisfy given demands from different nodes in a cellular network. At the same time the interference among calls within the same cell and from different neighboring cells are to be avoided, where interference is specified as the minimum frequency distance to be maintained between channels assigned to a pair of nodes. The simplest version of this problem, where only cochannel interferences are considered, is NP-complete. The proposed algorithm could generate a population of random valid solutions of the problem very fast. The best among them is the optimum or very near to optimum solution. For all problems with known optimal solutions, the algorithm could find them. A statistical estimation of the performance of the proposed algorithm is done. Comparison with other methods show that our algorithm works better than the algorithms that we have investigated.
We establish new lower and upper bounds for the real number graph labelling problem. As an application, we consider a problem of Griggs to determine the optimum spans of $L(p,q)$-labellings of the ...infinite triangular plane lattice and find (using a computer) the optimum spans for all $p$ and $q$.
Motivated by $L(p,q)$-labelings of graphs, we introduce a notion of $\lambda$-graphs: a $\lambda$-graph $G$ is a graph with two types of edges: 1-edges and $x$-edges. For a parameter $x\in0,1$, a ...proper labeling of $G$ is a labeling of vertices of $G$ by nonnegative reals such that the labels of the endvertices of a 1-edge differ by at least 1 and the labels of the endvertices of an $x$-edge differ by at least $x$; $\lambda_G(x)$ is the smallest real such that $G$ has a proper labeling by labels from the interval $0,\lambda_G(x)$. We study properties of the function $\lambda_G(x)$ for finite and infinite $\lambda$-graphs and establish the following results: if the function $\lambda_G(x)$ is well defined, then it is a piecewise linear function of $x$ with finitely many linear parts. Surprisingly, the set $\Lambda(\alpha,\beta)$ of all functions $\lambda_G$ with $\lambda_G(0)=\alpha$ and $\lambda_G(1)=\beta$ is finite for any $\alpha\le\beta$. We also prove a tight upper bound on the number of segments for finite $\lambda$-graphs $G$ with convex functions $\lambda_G(x)$.
We investigate the channel assignment problem, that is, the problem of assigning channels (codes) to the cells of a cellular radio network so as to avoid interference and minimize the number of ...channels used. The problem is formulated as a generalization of the graph coloring problem. We consider the saturation degree heuristic, first proposed as a technique for solving the graph coloring problem, which was already successfully used for code assignment in packet radio networks. We give a new version of this heuristic technique for cellular radio networks, called randomized saturation degree (RSD), based on node ordering and randomization. Furthermore, we improve the solution given by RSD by means of a local search technique. Experimental results show the effectiveness of the heuristic both in terms of solution quality and computing times.
An L(2,1)-labeling of a graph G is a mapping c : V(G) \to {0,...,K} such that the labels of two adjacent vertices differ by at least two and the labels of vertices at distance two differ by at least ...one. A hole of c is an integer h \in {0,...,K} that is not used as a label for any vertex of G. The smallest integer K for which an L(2,1)-labeling of G exists is denoted by lambda(G). The minimum number of holes in an optimal labeling, i.e., a labeling with K = lambda(G), is denoted by rho(G). Georges and Mauro SIAM J. Discrete Math., 19 (2005), pp. 208-223 showed that rho(G) \le Delta, where Delta is the maximum degree of G, and conjectured that if rho(G) = Delta and G is connected, then the order of G is at most Delta(Delta + 1). We disprove this conjecture by constructing graphs G with rho(G) = Delta and order \lfloor (Delta + 1)2/4 \rfloor (Delta + 1) \approx Delta3/4.
PDF
