The channel assignment problem with separation is formulated 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.
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 [
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 frequency 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 interference. 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 [
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 [
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
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 [
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
subgraph G0 = (V 0, E0) 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 [
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 [
(a) (b) (c) (d) (e) (f)
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 δmax as the maximum value of δ1. Note that
1
δ1 represents the minimum frequency separation requirement between any two
adjacent vertices. In [
Result 1 In honeycomb grid, the minimum λ for any L(1t) coloring of Dt can be computed as: λ ≥ 6p2 + 6p + 2, if t = 4p + 1 6p2 + 12p + 6, if t = 4p + 3 6p2 + 3p + 1, if t = 4p 6p2 + 9p + 4, if t = 4p + 2, where p is a non negative integer. 4 4.1
L(δ1max, 1t−1) coloring of the honeycomb grid
Upper bound of δmax
1 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 δmax obtained by this assignment is found to be 7. We now state a 1 bound on δ1max in the following Lemma 1. 7 8
Lemma 1. For any L(δ1max, 1t−1) coloring of Dt of a honeycomb grid, δ1max ≤ λ , where λ is the cardinality of Dt. 2 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. left vertex right vertex
Remark 1. The above result considers the assignment of colors to Dt only. However, 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 δmax = λ2 may not be achievable. Consider the 1 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 δmax = 4 is achieved. Our objective is to find 1 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 repetition 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 δmax between two adjacent vertices, the neighbors of 1 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 δmax which are 1 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 label a which are adjacent to n vertices of label b. Consider l = 1+max {i | Pij=1 j < n}.
9 2 9 2 7 0 12 5 7 0 12 5 10 3
10 3 8 1 13 6 8 1 13 6 11 4 9 2
11 4 9 2 7 0 12 5 9 2 7 0 12 5 10 3 7 0 12 5 10 3 8 1 13 6
10 3 8 1 13 6 11 4 8 1 13 6 11 4 9 2 11 4 9 2 7 0 12 5 7 0 12 5 10 3
10 3 8 1 13 6 8 1 13 6 11 4 11 4 (a)
2 9 0 7 5 12 2 9
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
3 10 0 7 5 12 2 9 1 8 6 13 3 10 0 7 5 12 4 11 1 8 6 13 3 10
2 9 4 11 1 8 6 13 0 7 5 12 2 9 4 11
3 10 7 5 12 1 8 6 13 3 10 4 11 1 8 6 13
4 11 (b)
Observe that l depends on n and can be expressed as l = d √8n+21−1 e. We now have the following result.
Lemma 3. The minimum number of neighbors of n nodes of label b in a honeycomb 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 in ith column is ki, 1 ≤ i ≤ l, where no two b labeled vertices are adjacent. So, Pli=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 neighbors of the b labeled vertices across all the l consecutive columns is Pli=1(ki + 1). Note 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 neighbors of the b labeled vertices across all the l consecutive columns is Pli=1 Ni, where
Ni = ki,
if i = l 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 of neighbors of b labeled vertices across all the l consecutive columns is Pli=1(ki + 1) + Pli=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 ki = (1,
if i = l ki+1 + 1, if 1 ≤ i ≤ l − 1.
So, the minimum value of the above expression is Pli=1(ki + 1) + Pli=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.
Theorem 1. In L(δ1max, 1t−1) coloring of honeycomb grid, δ1max ≤ λ2 − d √8b λ42c+1−1 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 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 λ42c+1−1 e + 1. Therefore, to √choose δ1max − b λ4 c vertices label a. So δ1max − b λ4 c ≤ λ2 − [b λ4 c + d of label a in the set S we are left with λ2 − [b λ4 c + d √ 8b λ42c+1−1 e + 1]. Hence the result.
8b λ42c+1−1 e + 1] vertices of 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 ti and can be defined by ti = p + i,
if 1 ≤ i ≤ p 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 all Pi2=p +11 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 when k is even. We now define fk as follows: f1 = 0, f2 = Pip=+11 ti = 3p2+5p+2 2 and in general, fk = Pik=−203 T2i+1, if 2p + 1 ≥ k > 2 and k is odd
k−2 fk = 3p2+5p+2 + P 2
2 i=1 T2i, if 2p + 1 ≥ k > 2 and k is even.
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 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, δ1max ≥ 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 the top of pth column is given by Pip=−11 ti = 3p2−3p . The 1st and 2nd b labeled 2 i=1 ti = 3p2+p and Pp vertices from the top of (p + 1)th column are Pp 2 i=1 ti + 1 = 3p2+p+2 respectively. The 1st a labeled vertex from the top of (p + 1)th column 2 is λ2 + 3p2−3p , which is adjacent to all three said b labeled vertices. The color gap 2 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: δmax = λ 1 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 expressed 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 [
Theorem 3. For L(δ1max, 1t−1) coloring of the honeycomb grid, 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.