=Paper=
{{Paper
|id=Vol-1231/long14
|storemode=property
|title=Efficient channel assignment for cellular networks modeled as honeycomb grid
|pdfUrl=https://ceur-ws.org/Vol-1231/long14.pdf
|volume=Vol-1231
|dblpUrl=https://dblp.org/rec/conf/ictcs/NandiPAGD14
}}
==Efficient channel assignment for cellular networks modeled as honeycomb grid==
https://ceur-ws.org/Vol-1231/long14.pdf
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