Efficient channel assignment for cellular networks modeled as honeycomb grid Soumen Nandi1 , Nitish Panigrahy2 , Mohit Agrawal2 , Sasthi C. Ghosh1 , and Sandip Das1 1 Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata, India, {soumen.nandi r, sasthi, sandipdas}@isical.ac.in. 2 Department of Computer Science and Engineering, National Institute of Technology, Rourkela, India, {nitish.pani, mohitag25}@gmail.com. Abstract. The channel assignment problem with separation is formu- lated as a vertex coloring problem of a graph G = (V, E) where each vertex represents a base station and two vertices are connected by an edge if their corresponding base stations are interfering to each other. The L(δ1 , δ2 , · · · , δt ) coloring of G is a mapping f : V → {0, 1, · · · , λ} such that |f (u) − f (v)| ≥ δi if d(u, v) = i, where d(u, v) denotes the distance between vertices u and v in G and 1 ≤ i ≤ t. Here λ, the largest color assigned to a vertex of G, is known as the span. The same color can be reused in two vertices u and v if d(u, v) ≥ t+1, where t+1 is the reuse distance. The objective is to minimize λ over all such coloring function f . Here (δ1 , δ2 , · · · , δt ) is called the separation vector where δ1 , δ2 , · · · , δt are positive integers with δ1 ≥ δ2 ≥ · · · ≥ δt . Let λ∗ be the minimum span such that there exists an L(1, 1, · · · , 1) coloring of G. We denote the separation vector (1, 1, · · · , 1) as (1t ). We deal with the problem of finding the maximum value of δ1 such that there exists an L(δ1 , 1t−1 ) coloring with span equal to λ∗ . So far bounds on δ1 have been obtained for L(δ1 , 1t−1 ) coloring with span λ∗ for the square and triangular grids. Shashanka et al. [18] posed the problem as open for the honeycomb grid. We give lower and upper bounds of δ1 for L(δ1 , 1t−1 ) coloring with span λ∗ of the honeycomb grid. The bounds are asymptotically tight. We also present color assignment algorithms to achieve the lower bound. 1 Introduction In cellular networks, a large number of base stations is expected to cover a communication region. Such a covering can be achieved by placing the base stations according to a regular plane tessellation. It is well-known that only three different regular tessellations of the plane exist [6]. Specifically, the honey- comb, square and triangular tessellations cover the plane respectively by regular hexagons, squares, and triangles leading to three well-known topologies: hon- eycomb, square and triangular grids [6]. These three grid structures are shown in Figs. 1 (a), (b) and (c) where each vertex represents a base station and two 183 S.Nandi et al. Efficient channel assignment for cellular networks vertices have an edge between them if their corresponding base stations are in- terfering to each other. Considering the network cost as a product of degree and diameter the honeycomb grid beats both the triangular and square grids as ar- gued by Bertossi et al. [6]. The brick representation of the honeycomb grid has been shown in Fig. 1 (d) [6]. In this brick representation, the honeycomb grid can be viewed as a 2-dimensional grid. Thus each vertex can be represented by a 2-dimensional cartesian co-ordinate (i, j) where i and j are integers. (a) (b) (c) (d) Fig. 1: (a) Honeycomb grid, (b) Square grid, (c) Triangular grid and (d) Brick structure of honeycomb grid. The assignment of frequency channels to the base stations became a problem for enormous growth of wireless network. Since the number of available frequency channels is very limited, they must be utilized in an efficient manner. The main difficulty in efficient use of these frequency channels is the interference caused by unconstrained simultaneous transmissions of nearby stations. The same fre- quency channel can be reused by two stations provided that they are sufficiently far away so that the interference arisen between them can be negligible. However, the frequencies assigned to two nearby stations must differ by certain minimum value depending on the distance between them to avoid the channel interfer- ence. The channel assignment problem (CAP) deals with the task of assigning frequency channels to the stations such that there is no interference between the frequencies assigned to the nearby stations. The objective is to minimize the required span (bandwidth) where the span is represented by the difference between the least and the highest channel used. The minimum distance at which a channel can be reused with no interference is called the reuse distance. The cellular network is often modeled as a graph G = (V, E) where each vertex represents a base station and there is an edge between two vertices if their corresponding base stations are within the interference range of each other. Thus the channel assignment problem is basically a graph coloring problem on this graph. More formally, the L(δ1 , δ2 , · · · , δt ) coloring of a graph G = (V, E) is a way to assign colors in {0, 1, · · · , λ} to the vertices of G using as small λ as possible such that the colors assigned to the vertices say u and v which are distance i apart differ by at least δi where 1 ≤ i ≤ t and the same color can be reused to two vertices if they are distance t + 1 or more apart [14]. Here t + 1 is the reuse distance, λ is the span and (δ1 , δ2 , · · · , δt ) is known as the separation vector where δ1 , δ2 , · · · , δt are positive integers with δ1 ≥ δ2 ≥ · · · ≥ δt . Let λ∗ be the minimum span required for any L(1t ) coloring of G. It is evident that 184 S.Nandi et al. Efficient channel assignment for cellular networks minimum span required for any L(δ1 , 1t−1 ) coloring of G must be greater than or equal to λ∗ for any δ1 > 1. In this paper, we deal with the problem of finding the maximum value of δ1 such that there exists an L(δ1 , 1t−1 ) coloring of G using the span equal to λ∗ . Keeping the span restricted to the value of λ∗ ensures that such an L(δ1 , 1t−1 ) coloring is always optimal. The rationale behind maximizing δ1 is as follows. The interference between two adjacent channels can be prevented by using a guard band which is an unused part of the radio spectrum. Interference can also be prevented by using a specific channel separation requirement between two adjacent channels. It has been argued by Bertossi et al. [6] that when no extra colors are used, use of channel separation is always a better option than using guard bands between two adjacent channels. Moreover, higher channel separation between adjacent vertices will give the better quality of communication. So far bounds on δ1 have been obtained for L(δ1 , 1t−1 ) coloring with span λ∗ for square and triangular grids [5, 18]. Bertossi et al. [6] proposed an algorithm for optimal L(1t ) coloring for the honeycomb grid. Shashanka et al. [18] posed L(δ1 , 1t−1 ) coloring of honeycomb grid for δ1 > 1 as an open problem. We found lower and upper bounds of δ1 for L(δ1 , 1t−1 ) coloring with span λ∗ of the honeycomb grid. We also present color assignment algorithms to achieve the lower bound. The obtained bounds are asymptotically tight. This paper is arranged in the following way. In section 2, we have described some related works. In section 3, we have presented the basic concepts and notations. In section 4, we have provided the bounds of δ1 in L(δ1 , 1t−1 ) coloring of the honeycomb grid. We have also given assignment algorithms to achieve the lower bound in this section. Section 5 concludes the paper. 2 Related work The L(1t ) coloring has been widely studied by several authors [2, 3, 10, 15, 16] for many special type of graphs. The intractability of optimal L(1t ) coloring, for any positive integer t, has been proved by McCormick [15] for arbitrary graphs. The optimal L(1t ) colorings for rings, square grids, and honeycomb grids have been proposed in [6, 3] and in [1] for trees and interval graphs. The optimal L(δ1 , 1t−1 ) colorings have been proposed in [5, 18] for rings, square grids, and cellular grids. The optimal L(δ1 , δ2 ) coloring on square and triangular grids have been proposed [11]. Chang et al. [9] gave bounds for L(δ1 , 1) coloring of chordal graphs and trees. Griggs and Jin [12, 13] provided optimal L(δ1 , 1) coloring for buses, rings, wheels, trees, and regular grids where δ1 is a non-negative real number. The optimal L(2, 1, 1) coloring for square grids [11] and triangular grids, honeycomb grids, and rings [4, 5] have been proposed. The L(δ1 , δ2 , 1) coloring for squared and eight-regular grids has been studied in [8]. The L(2, 1) coloring has been investigated in [7, 19] for different graphs. All these results stated above basically deal with finding minimum span for the concerned coloring of different graphs. Our focus is, however, to find the maximum separation between two colors assigned to two adjacent vertices in an 185 S.Nandi et al. Efficient channel assignment for cellular networks L(δ1 , 1t−1 ) coloring of the honeycomb grid. Though the problem has been solved for the triangular and square grids, it was open for the honeycomb grid [18]. 3 Basic Concepts and Notations The required span for L(δ1 , 1t−1 ) coloring will definitely be greater or equal to the required span for L(1t ) coloring. We now define the Distance-t clique of a graph G in order to establish bounds on the required minimum span for L(1t ) coloring of G. Definition 1. The Distance-t clique of a graph G = (V, E) is an induced sub- graph G0 = (V 0 , E 0 ) where distance between every pair of vertices in V 0 is at most t. A maximum Distance-k clique is the Distance-k clique where cardinality of V 0 is maximum [17]. We denote a maximum Distance-t clique of a graph by Dt . The standard graph theoretic term, maximum clique, is a Distance-t clique with t = 1. So, Distance-t clique of a graph G = (V, E) is a subgraph of G with diameter t. Though finding Dt for general graph is a hard problem, it can be found for the honeycomb grid [6]. As for example, D1 with 2 vertices, D3 with 6 vertices, D5 with 14 vertices, D0 with 1 vertex, D2 with 4 vertices and D4 with 10 vertices of the honeycomb grid are shown in Figs. 2 (a), (b), (c), (d), (e) and (f) respectively. (a) (b) (c) (d) (e) (f ) Fig. 2: (a) D1 , (b) D3 , (c) D5 , (d) D0 , (e) D2 and (f) D4 . The required span for any L(1t ) coloring of G will be at least the cardinality of Dt . Our objective is to find the maximum value of δ1 such that there exists an L(δ1 , 1t−1 ) coloring of G using the set of colors from {0, 1, · · · , λ − 1}, where λ is the cardinality of Dt . We denote δ1max as the maximum value of δ1 . Note that δ1 represents the minimum frequency separation requirement between any two adjacent vertices. In [6], the minimum λ for L(1t ) coloring of Dt in honeycomb grid was computed by considering 8 cases with t = 8p+q where 0 ≤ q ≤ 7. Based on the results reported in [6], we can state the following result by considering only 4 cases with t = 4p + q where 0 ≤ q ≤ 3. 186 S.Nandi et al. Efficient channel assignment for cellular networks Result 1 In honeycomb grid, the minimum λ for any L(1t ) coloring of Dt can be computed as:  2   6p + 6p + 2, if t = 4p + 1  6p2 + 12p + 6, if t = 4p + 3 λ≥    6p2 + 3p + 1, if t = 4p  2 6p + 9p + 4, if t = 4p + 2, where p is a non negative integer. 4 L(δ1max , 1t−1 ) coloring of the honeycomb grid 4.1 Upper bound of δ1max Let us consider p = 1 and t = 4 × 1 + 1 = 5. By putting these values in Result 1, minimum λ is found to be 14. The subgraph D5 constituted by these 14 vertices is shown in Fig. 2 (c). Observe that in D5 (Fig. 2 (c)) all the cycles are of even length, i.e., it is a bipartite graph. We see that there are 7 disjoint edges. For a bipartite graph like this each partition contains 7 nodes. We can select seven nodes of one partition and assign colors 0 to 6 to them and for the remaining seven nodes from the other partition, we can assign colors 7 to 13 as shown in Fig. 3. The δ1max obtained by this assignment is found to be 7. We now state a bound on δ1max in the following Lemma 1. o i a 9 2 b 7 0 12 5 lef t vertex 10 3 right vertex 8 1 13 6 11 4 j Fig. 3: A coloring of D5 where δ1max = λ2 . Fig. 4: 18 nodes of label a which are neigh- bors of 12 nodes of label b. Lemma 1. For any L(δ1max , 1t−1 ) coloring of Dt of a honeycomb grid, δ1max ≤ λ 2 , where λ is the cardinality of Dt . Proof. For λ number of nodes there can be at most λ2 number of disjoint edges in Dt . So we can form a maximum independent set of length at most λ2 . And our δ1max therefore, can be at most λ2 . Thus we can conclude that δ1max ≤ λ2 . We can compute λ for Dt by applying Result 1.  187 S.Nandi et al. Efficient channel assignment for cellular networks Remark 1. The above result considers the assignment of colors to Dt only. How- ever, as practical networks are very large, we have to repeat the assignment of this subgraph in a regular fashion so as to cover the entire honeycomb grid. If we want to repeat an assignment of Dt in a regular fashion with a view to covering the entire grid, we will see that δ1max = λ2 may not be achievable. Consider the assignment of D5 as shown in Fig. 3. It can easily be verified that with this assignment, δ1max = λ2 = 7. Note that here we have considered the assignment of D5 only but not considered the possibility of repeating this assignment to cover the entire grid. We now consider two different assignments of D5 and their repetition pattern to cover the entire grid. As for example one of them is shown in Fig. 5 (a). With this repetition pattern, δ1max 6= 7, rather δ1max = 2. The other one is shown in Fig. 5 (b), where δ1max = 4 is achieved. Our objective is to find an assignment of the entire grid for which the value of δ1max is maximized. As far as the assignment of Dt is concerned, there are three types of vertices with degrees 1, 2 and 3. Here the degree of a vertex is computed based on the number of adjacent vertices which are already assigned within the subgraph. If we consider the repetition of the assignment of this subgraph to cover the entire grid, the degree of each vertex will eventually become 3. Moreover, the assignment of Dt should be repeated to infinity in such a way that the colors of the adjacent three vertices of a vertex with a particular color remain fixed throughout the entire grid. Such assignment is possible which is given in Fig. 5 (b). As for example, the vertex of color 3 is having the vertices of colors 7, 8 and 10 as its adjacent everywhere. We now have the following result on δ1max that considers the assignment of the entire honeycomb grid. Lemma 2. In L(δ1max , 1t−1 ) coloring of honeycomb grid δ1max ≤ λ2 − 1, where λ is the cardinality of Dt . Proof. From Lemma 1, it follows that the maximum value for δ1max without rep- etition is λ2 . So with repetition, δ1max cannot exceed this value due to additional constraints on the vertices of degree not equal to 3 which have now become vertices of degree 3 each. Now consider the vertex colored as δ1max − 1. Because of the color separation δ1max between two adjacent vertices, the neighbors of the vertex colored with δ1max − 1, must have a color larger than δ1max − 1. So its adjacent vertices are of colors with a difference of at least δ1max which are 2δ1max − 1, 2δ1max and 2δ1max + 1. But a vertex can have a color at most λ − 1. So 2δ1max + 1 ≤ λ − 1, i.e., δ1max ≤ λ2 − 1.  Remark 2. The honeycomb grid is a bipartite graph. We label the vertices of one partition as a and that of other partition as b. The basic idea behind the result stated in Lemma 2 is that there are exactly 3 vertices of label a which are adjacent to a vertex of label b. We observe that there are a minimum of 5 vertices of label a which are adjacent to two vertices of label b. This is because if we choose any two vertices of label b there can be at most one common adjacent (neighbor) vertex of those two b labeled vertices. With a view to generalizing this idea, we required to find the minimum number of vertices of P label a which i are adjacent to n vertices of label b. Consider l = 1+max {i | j=1 j < n}. 188 S.Nandi et al. Efficient channel assignment for cellular networks 2 9 0 7 5 12 2 9 i 13 3 10 0 7 5 12 1 8 6 13 3 10 2 9 4 11 1 8 6 13 0 7 5 12 2 9 4 11 9 2 2 9 3 10 0 7 5 12 2 9 9 2 7 0 12 5 0 7 5 12 2 9 1 8 6 13 3 10 0 7 5 12 7 0 12 5 10 3 3 10 0 7 5 12 4 11 1 8 6 13 3 10 10 3 8 1 13 6 1 8 6 13 3 10 2 9 4 11 1 8 6 13 8 1 13 6 11 4 9 2 2 94 11 1 8 6 13 0 75 12 2 9 4 11 11 4 9 2 7 0 12 5 0 7 5 12 2 9 4 11 13 3 10 0 7 5 12 2 9 9 2 7 0 12 5 10 3 3 10 0 7 5 12 2 9 1 8 6 13 3 10 0 7 5 12 7 0 12 5 10 3 8 1 13 6 1 8 6 13 3 10 0 7 5 12 4 11 1 8 6 13 3 10 10 3 8 1 13 6 11 4 4 11 1 8 6 13 3 10 12 2 9 4 1 8 6 13 8 1 13 6 11 4 9 2 2 9 4 11 1 8 6 13 0 7 5 12 2 9 4 11 11 4 9 2 7 0 12 5 0 7 5 12 2 9 4 11 13 3 10 0 7 5 12 7 0 12 5 10 3 3 10 7 5 12 1 8 6 13 3 10 10 3 8 1 13 6 1 8 6 13 3 10 4 11 1 8 6 13 8 1 13 6 11 4 4 11 1 8 6 13 4 11 j 11 4 4 11 (a) (b) (c) Fig. 5: (a) Coloring of D5 with repetition where δ1max ≤ λ2 is not achieved, (b) Infinite repetition of D5 in a honeycomb grid where reuse distance is satisfied and (c) Coloring of D5 with repetition where δ1max = 4. √ 8n+1−1 Observe that l depends on n and can be expressed as l = d 2 e. We now have the following result. Lemma 3. The minimum number of neighbors of n nodes of label b in a hon- eycomb grid is n + l + 1, where no two b labeled vertices are adjacent. Proof. Let us consider the honeycomb grid which is shown in Fig. 4. Consider l consecutive columns in that graph. Assume that the number of b labeled vertices Plith column is ki , 1 ≤ i ≤ l, where no two b labeled vertices are adjacent. So, in i=1 ki = n. Note that each b labeled vertex has two neighbors within the same column and one neighbor in the (i + 1)th column. We denote the two neighbors of a b labeled vertex within the same column as the same column neighbors and the neighbor in the adjacent column ((i + 1)) as the adjacent column neighbor. Observe that the number of same column neighbors of the b labeled vertices of ith column is at least (ki + 1) and at most 2ki . The number of adjacent column neighbors of the b labeled vertices of ith column is exactly ki . Note, however, that the adjacent column neighbors of the b labeled vertices of ith column may share some same column neighbors of the b labeled vertices of (i + 1)th column. Observe that the least number of same column neighbors of the b labeled vertices of ith column is (ki + 1) when all the b labeled vertices are placed one after another at two distance apart. So the total number of same column Pl neighbors of the b labeled vertices across all the l consecutive columns is i=1 (ki + 1). Note 189 S.Nandi et al. Efficient channel assignment for cellular networks that the ki number of adjacent column neighbors of the b labeled vertices of ith column may equal or less or greater than the ki+1 + 1 number of same column neighbors of the b labeled vertices of (i + 1)th column. Let Ni be the number of adjacent column neighbors of the b labeled vertices of ith column. So the total number of adjacent column Pl neighbors of the b labeled vertices across all the l consecutive columns is i=1 Ni , where   ki , if i = l Ni = ki − (ki+1 + 1), if ki > ki+1 + 1 and 1 ≤ i ≤ l − 1   0, if ki ≤ ki+1 + 1 and 1 ≤ i ≤ l − 1. So, the total number Pl of neighbors Plof b labeled vertices across all the l con- secutive columns is i=1 (ki + 1) + i=1 Ni . If ki < ki+1 + 1, for all i, then the value of kl becomes largest and if ki > ki+1 + 1, for all i, then the total number of adjacent column neighbors will be increased. As our objective is to find the minimum number of neighbors, the best possible situation is ( 1, if i = l ki = ki+1 + 1, if 1 ≤ i ≤ l − 1. Pl Pl So, the minimum value of the above expression is i=1 (ki + 1) + i=1 Ni = n + l + 1. We conclude that the minimum number of neighbors of n nodes of b labeled vertices in a honeycomb grid is n + l + 1.  Example 1. Corresponding to Lemma 3, we are presenting one example for n = 12 in Fig. 4, where 12 can be expressed as 2 + 4 + 3 + 2 + 1. Here all the 12 nodes of label b are shown by dots and nodes of label a are circled which are the neighbors of b labeled vertices. We see that minimum number of neighbors of 12 nodes of label b is 12 + 5 + 1 = 18. In L(δ1max , 1t−1 ) coloring of honeycomb grid, Theorem 1. √ 8b λ 4 c+1−1 δ1max ≤ λ2 − d 2 e − 1, where λ is the cardinality of Dt . Proof. We know that any consecutive δ1max non negative integers will be forming an independent set. Let us consider such an independent set S = {a1 , a2 , · · · , aδ1max } such that all its elements are consecutive and in increasing order. As Dt is a bipartite graph with cardinality λ and λ is even, we can label λ2 vertices of it by a label say a and the remaining λ2 vertices by an another label say b. Let us denote the vertices colored by 0, 1, · · · , λ2 − 1 as label a vertices and the vertices colored by λ2 , λ2 + 1, · · · , λ − 1 as label b vertices. We can easily construct an independent set S with δ1max − 2 vertices of label a and 2 vertices of label b. Essentially S contains the a labeled vertices colored by λ2 −(δ1max −2), λ2 −(δ1max −3), · · · , λ2 −1 and the b labeled vertices colored by λ2 and λ2 + 1. Now to form an independent set any one of the δ1max vertices of set S must not be adjacent to other vertex of S. At minimum there can be 5 vertices which will be adjacent to these 2 vertices 190 S.Nandi et al. Efficient channel assignment for cellular networks of label b. To form an independent set these 5 nodes should not be in the set S. So to choose δ1max − 2 vertices of label a in the set S we are left with λ2 − 5 number of choices of a labeled vertices. Hence δ1max −2 ≤ λ2 −5 i.e. δ1max ≤ λ2 −3. Similarly, we can construct an independent set S with δ1max − b λ4 c vertices of label a and b λ4 c vertices of label b. If we take the number of vertices of label b more than b λ4 c, then we can think of switching the labels, i.e., all the a labeled vertices will be changed to label b and all the b labeled vertices will be changed to label a so that same case will again be happened. So b λ4 c is the threshold value. Hence, by Lemma 3, the minimum number of neighbors of b λ4 c vertices √ λ 8b 4 c+1−1 of label b is b λ4 c + d e + 1. Therefore, to choose δ1max − b λ4 c vertices 2 √ λ λ λ 8b 4 c+1−1 of label a in the set S we are left with 2 − [b 4 c + d e + 1] vertices of √ λ 2 8b 4 c+1−1 label a. So δ1max λ λ λ − b 4 c ≤ 2 − [b 4 c + d 2 e + 1]. Hence the result.  4.2 Lower bound of δ1max As mentioned earlier, the honeycomb grid can be viewed as a 2-dimensional grid where each vertex can be represented as (i, j) for some integers i and j. We call a vertex (i, j) as a right vertex if its adjacent 3 vertices are (i, j + 1), (i, j − 1) and (i + 1, j). Similarly a vertex (i, j) is called a left vertex if its adjacent 3 vertices are (i, j + 1), (i, j − 1) and (i − 1, j). Note that a left vertex has a neighbor at left side and a right vertex has a neighbor at right side. In Fig. 4, the vertices marked by circle and dots are left and right vertices respectively. It is easy to verify that all the left and right vertices are forming two separate independent sets. So we can label all the left vertices by a and all the right vertices by b. Let us consider the assignment of the first λ2 colors 0, 1, · · · , λ2 − 1 to the b labeled vertices and the rest λ2 colors λ2 , λ2 + 1, · · · , λ − 1 to the a labeled vertices in some fashion. We now describe an assignment scheme for L(δ1max , 1t−1 ) coloring of the honeycomb grid, where t is odd and p is any non negative integer. L(δ1max , 1t−1 ) coloring of a honeycomb grid for odd t: We first deal with the L(δ1max , 1t−1 ) coloring algorithm for the case of t = 4p + 1. As our objective is to maximize the value of δ1max , we assign the colors ranging from 0 to λ2 − 1 to the right vertices of D4p+1 sequentially starting from the left most column, top to bottom, towards the 2nd right most column. Similarly, the colors ranging from λ2 to λ − 1 are assigned to the left vertices of D4p+1 sequentially starting from the 2nd left most column, top to bottom, towards the right most column. Though there are (2p + 2) columns in D4p+1 only the first (2p + 1) columns contain vertices of label b. In each column from left most to 2nd right most there are (p + 1), (p + 2), · · · , 2p, (2p + 1), 2p, · · · , (p + 2), (p + 1) number of b labeled vertices respectively. So, the number of colors in column i is denoted by 191 S.Nandi et al. Efficient channel assignment for cellular networks ti and can be defined by   p + i, if 1 ≤ i ≤ p ti = 2p + 1, if i = (p + 1)   3p + 2 − i, if (p + 2) ≤ i ≤ (2p + 1). We see that (t1 + tp+2 ) = (t2 + tp+3 ) = · · · = (tp + t2p+1 ) = (3p + 1). An example of execution of this algorithm to the subgraph D4p+1 is shown in Fig. 5 (c) for the case where p = 1. So far we have considered the color assignment of the vertices of D4p+1 only. We now consider the repetition of these colors to cover the entire grid. We use the following repetition pattern to extend the coloring of D4p+1 to the entire grid: a color assigned to vertex (i, j) is repeated to exactly six vertices (i+p+1, j +3p+1), (i+2p+1, j −1), (i+p, j −3p−2), (i−p−1, j −3p−1), (i − 2p − 1, j + 1) and (i − p, j + 3p + 2) forming a hexagon of radius t + 1 (reuse distance) centered around the vertex (i, j). In Fig. 5 (c), the repetition of color 3 has been explicitly shown by filled circle. The same repetition pattern holds for each color assigned to the vertices of D4p+1 . It is evident that this pattern can be repeated infinitely and it satisfies the reuse distance. Using this pattern of repetition, when the assignment of D4p+1 is repeated infinitely, we observe that P2p+1 all i=1 ti colors are placed in each column. The sequence of colors used in each column can be described as follows: The sequence is actually composed of (2p + 1) subsequences where kth subsequence starts with color fk and ends with color fk + Tk − 1, where 1 ≤ k ≤ 2p + 1. That means, there are Tk many colors in the kth subsequence. Let us define Tk = t k+1 when k is odd and Tk = tp+ k+2 2 2 Pp+1 2 when k is even. We now define fk as follows: f1 = 0, f2 = i=1 ti = 3p +5p+2 2 and in general,  k−3 P 2 T if 2p + 1 ≥ k > 2 and k is odd i=0 2i+1 , fk = fk = 3p2 +5p+2 + P 2 T2i , if 2p + 1 ≥ k > 2 and k is even. k−2 2 i=1 Thus the sequence of colors used in each column is as follows: f1 , f1 + 1, · · · , f1 + T1 − 1; f2 , f2 + 1, · · · , f2 + T2 − 1; · · · ; fk , fk + 1, · · · , fk + Tk − 1; · · · ; f2p+1 , f2p+1 + 1, · · · , f2p+1 + T2p+1 − 1. If color f1 is placed on (i, j), then on that same ith column f1 is again placed at (i, j + 6p2 + 6p + 2) and on (i + 1)th column f1 is placed at (i + 1, j − (6p + 3)). The same pattern holds for all other colors. The coloring of D5 and its repetition to cover the entire grid has been shown in Fig. 5 (c). In this case, there are 3 subsequences 0, 1; 5, 6; and 2, 3, 4. So, the sequence of colors used in each column are 0, 1, 5, 6, 2, 3, 4. So far we have considered the assignment of label b vertices only. We now consider the assignment of a labeled vertices ranging from λ2 to λ − 1. Let color x ∈ [0, λ2 − 1] has been assigned to vertex (i, j). Then color x + λ2 ∈ [ λ2 , λ − 1] will be assigned to vertex (i + 1, j). It can now be seen that the infinite honeycomb grid will be filled up by λ colors ranging from 0 to λ − 1 where λ = 6p2 + 6p + 2 and t = 4p+1. We observe that this assignment is a no-hole assignment meaning every colors ranging from 0 to λ − 1 has been used. An example of execution 192 S.Nandi et al. Efficient channel assignment for cellular networks of the algorithm to the entire grid for t = 4p + 1 is shown in Fig. 5 (c) for the case where p = 1. Similarly the coloring scheme for the case of t = 4p + 3 can be obtained, which we omitted here due to space restriction. Theorem 2. For L(δ1max , 1t−1 ) coloring of the honeycomb grid,  2 max 3p + p, if t = 4p + 1 (1) δ1 ≥ 2 3p + 3p + 1, if t = 4p + 3 (2) where λ is the cardinality of Dt and p is a non-negative integer. Proof. Consider Dt with odd t. Depending on the value of t there are 2 cases. Case 1. t = 4p + 1: We observe that 1st b labeled vertex in D4p+1 from Pp−1 2 the top of pth column is given by i=1 ti = 3p 2−3p . The 1st and 2nd b labeled Pp 2 Pp vertices from the top of (p + 1)th column are i=1 ti = 3p 2+p and i=1 ti + 1 = 3p2 +p+2 2 respectively. The 1st a labeled vertex from the top of (p + 1)th column λ 3p2 −3p is 2 + 2 , which is adjacent to all three said b labeled vertices. The color gap between the 2nd b labeled vertex of (p + 1)th column and 1st a labeled vertex of (p + 1)th column is minimum which is found to be: λ 3p2 − 3p 3p2 + p + 2 δ1max = + − = 3p2 + p. 2 2 2 Case 2. t = 4p+3: We observe that 1st b labeled vertex in D4p+3 of (p+2)th Pp+1 2 column is i=1 ti = 3p +7p+42 . The 1st a labeled vertex of (p + 1)th column is λ Pp λ 3p2 +p 2 + i=1 (p + i) = 2 + 2 . The color gap between these two adjacent colors is minimum which is found to be: λ 3p2 + p 3p2 + 7p + 4 δ1max = + − = 3p2 + 3p + 1. 2 2 2  Observation 1 For any L(δ1max , 1t−1 ) coloring of a honeycomb grid, the lower bound of δ1max obtained from Theorem 2 and the upper bound of δ1max obtained from Theorem 1 are asymptotically equal. Proof. Observe that the bound of δ1max obtained from Theorem 1 can be ex- pressed as 3p2 + cp + d where 1.268 ≤ c ≤ 4.268 and d is a constant. Hence the result.  L(δ1max , 1t−1 ) coloring of a honeycomb grid for even t: It follows from Lemmas 2 and 6 of [6] that the L(δ1max , 1t−1 ) coloring of Dt for any even t can not be repeated to cover the entire grid using the colors from 0 to λ − 1, where λ is the cardinality of Dt . It is observed that Dt with even t can be considered as a subgraph of Dt+1 where t+1 is odd. Note that difference between the cardinality of Dt+1 and Dt is 3p + 1 when t = 4p and 3p + 2 when t = 4p + 2. Thus by 193 S.Nandi et al. Efficient channel assignment for cellular networks putting these minimum number of extra colors, we can cover the entire grid for the case of even t. So the lower and upper bounds of δ1max is same as that of the case of odd t. Hence we can conclude the following theorem. Theorem 3. For L(δ1max , 1t−1 ) coloring of the honeycomb grid,  2 max 3p + p, if t = 4p (3) δ1 ≥ 2 3p + 3p + 1, if t = 4p + 2 (4) where λ is the cardinality of Dt and p is a non-negative integer. 5 Conclusion We have derived upper and lower bounds of δ1max for any L(δ1max , 1t−1 ) coloring with span λ∗ of honeycomb grid, where λ∗ is the minimum span required for any L(1t ) coloring. We have shown that the bounds are asymptotically tight. We have also given assignment algorithms for finding the lower bounds of δ1max . References 1. G. Agnarsson, R. Greenlaw, and M. Halldorson. On powers of chordal graphs and their colorings. Congressus Numerantium, 144:41–65, 2000. 2. R. Battiti, A. Bertossi, and M. Bonuccelli. Assigning codes in wireless networks: Bounds and scaling properties. Wireless Networks, 5:195–209, 1999. 3. A. Bertossi and M. Pinotti. Mappings for conflict-free access of paths in bidimen- sional arrays, circular lists, and complete trees. Journal of Parallel and Distributed Computing, 62:1314–1333, 2002. 4. A. Bertossi, M. Pinotti, and R. Tan. Efficient use of radio spectrum in wireless networks with channel separation between close stations. DIAL M for Mobility: Intl ACM Workshop on Discrete Algorithms and Methods for Mobile Computing, Boston, 2000. 5. A. Bertossi, M. Pinotti, and R. Tan. Channel assignment with separation for interference avoidance in wireless networks. IEEE Transactions on Parallel and Distributed Systems, 14:222–235, 2003. 6. A. A. Bertossi, C. M. Pinotti, R. Rizzi, and A. M. Shende. Channel assignment for interference avoidance in honeycomb wireless networks. Journal of Parallel and Distributed Computing, 64:1329–1344, 2004. 7. T. Calamoneri. The l(h, k)-labelling problem: An updated survey and annotated bibliography. Comput. J., 54(8):1344–1371, 2011. 8. T. Calamoneri. Optimal l(δ1 , δ2 , 1)-labeling of eight-regular grids. Information Processing Letters, 113:361–364, 2013. 9. G. J. Chang, W. T. Ke, D. Kuo, and R. K. Yeh. l(d, 1)-labeling of graphs. Discrete Math., 220:57–66, 2000. 10. I. Chlamtac and S. Pinter. Distributed nodes organizations algorithm for channel access in a multihop dynamic radio network. IEEE Transactions on Computers, 36:728–737, 1987. 11. J. V. den Heuvel, R. A. Leese, and M. Shepherd. Graph labelling and radio channel assignment. Journal of Graph Theory, 29:263–283, 1998. 194 S.Nandi et al. Efficient channel assignment for cellular networks 12. J. R. Griggs and X. T. Jin. Optimal channel assignments for lattices with condi- tions at distance two. 5th IEEE International Parallel and Distributed Processing Symposium, extended abstruct, 2005. 13. J. R. Griggs and X. T. Jin. Real number graph labellings with distance conditions. SIAM J. Discrete Math., 20:302–327, 2006. 14. J. R. Griggs and R. K. Yeh. Labelling graphs with a condition at distance 2. SIAM J. Discrete Math., 5:586–595, 1992. 15. S. McCormick. Optimal approximation of sparse hessians and its equivalence to a graph coloring problem. Mathematical Programming, 26:153171, 1983. 16. A. Sen, T. Roxborough, and S. Medidi. Upper and lower bounds of a class of channel assignment problems in cellular networks. Proc. of the INFOCOM, 3:1284– 1291, 1998. 17. A. Sen, T. Roxborough, and B. P. Sinha. On an optimal algorithm for channel assignment in cellular network. Proc. of IEEE ICC, pages 1147–1151, 1999. 18. M. V. S. Shashanka, A. Pati, and A. M. Shende. A characterisation of optimal channel assignments for cellular and square grid wireless networks. Mobile Networks and Applications, 10:89–98, 2005. 19. R. Yeh. A survey on labeling graphs with a condition at distance two. Discrete Mathematics, 306(12):1217–1231, 2006. 195