# Optimal Control Channel Selection for Wireless Channel Assignment

Authors: Sheng Zhong
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

In wireless channel assignment, control channels are often needed for coordination among wireless devices. In this paper, we propose an algorithm for finding the optimal set of control channels given a number of wireless devices and the ranges of channels these devices can access.


---

## Body

## 1. Introduction

Wireless communications are now a crucial part of our everyday life. In wireless communications, there is a fundamental problem calledchannel assignment [1–3]: each wireless device needs to determine which channels it should use for its own communications, before any message can be sent or received. In this process, there need to be one or more control channels for coordination among wireless devices. These channels are used by the wireless devices to exchange information regarding their decisions on channel assignment (with the base station). Hence, a natural question is which channel(s) should be used as the control channel(s).In this paper, we study the following mathematical problem regarding the selection of control channels: given a base station and a number of wireless devices, which control channels should be used as the control channels, so that only the smallest number of control channels is used but each involved device can access at least one control channel? The answer may be trivial if all involved wireless devices can access all channels available. Nevertheless, in reality, many wireless devices actually have limited tunability. Such a device can only access channels in a certain range of frequency. Consequently, in this paper, we assume that for each involved device, the range of channels accessible by this device is also given as input. Our objective is to develop an algorithm that finds the optimal set of control channels when given devices and their ranges of accessible channels.


### 1.1. Related Work and Our Contribution

Channel assignment has been studied in various settings, under various assumptions. A lot of results have been obtained, for example, [1–6]. Most of these channel assignment schemes require that there is one or more control channels, so that wireless devices can exchange information with each other (and/or with the base station) in the process of channel assignment. However, as far as we know, there is no previous result on optimal selection of control channels in this context.There are some existing studies (e.g., [7, 8]) of control channel selection in a different context, namely, cognitive radio networks. Since both their models and their objectives differ from ours, their results cannot be applied to our problem.Our main contribution in this paper is that we design an algorithm to find the optimal set of control channels for channel assignment. Here optimality means under the constraint that each device can access at least one control channel, the total number of control channels is minimized. We provide a formal proof for the correctness of our algorithm. We also analyze its complexity.We emphasize that the problem studied in this paper is not the channel assignment problem. In fact, it is a closely related, but very different problem, namely, the control channel selection problem. Specifically, our objective is not to assign channels to devices for their data communications, but to choose control channels for devices, so that they can coordinate with each other for their transmissions. One of the key differences here is that in channel assignment, performance metrics such as system throughput are of great importance. In contrast, in control channel selection, such performance metrics are not so important because the number of control packets is typically much smaller than that of data packets.


## 1.1. Related Work and Our Contribution

Channel assignment has been studied in various settings, under various assumptions. A lot of results have been obtained, for example, [1–6]. Most of these channel assignment schemes require that there is one or more control channels, so that wireless devices can exchange information with each other (and/or with the base station) in the process of channel assignment. However, as far as we know, there is no previous result on optimal selection of control channels in this context.There are some existing studies (e.g., [7, 8]) of control channel selection in a different context, namely, cognitive radio networks. Since both their models and their objectives differ from ours, their results cannot be applied to our problem.Our main contribution in this paper is that we design an algorithm to find the optimal set of control channels for channel assignment. Here optimality means under the constraint that each device can access at least one control channel, the total number of control channels is minimized. We provide a formal proof for the correctness of our algorithm. We also analyze its complexity.We emphasize that the problem studied in this paper is not the channel assignment problem. In fact, it is a closely related, but very different problem, namely, the control channel selection problem. Specifically, our objective is not to assign channels to devices for their data communications, but to choose control channels for devices, so that they can coordinate with each other for their transmissions. One of the key differences here is that in channel assignment, performance metrics such as system throughput are of great importance. In contrast, in control channel selection, such performance metrics are not so important because the number of control packets is typically much smaller than that of data packets.


## 2. Assumptions and Formal Model

To solve the problem of control channel selection, we make the following crucial assumptions.(1)
All involved devices are in a single collision domain.(2)
Devices are equipped with radios that can access arbitrary sets of channels.(3)
Devices coordinate with each other through their common control channels. In particular, we assume it suffices for each pair of devices to have a control channel in common, such that they can use this control channel to coordinate with each other.(4)
Under the constraint that every pair of devices should have a common control channel, it is desirable to minimize the number of control channels, such that more channels can be used for data communications. Based on these assumptions, we have the following formal model for the problem.Suppose that there is a base station andn wireless devices, all in a single collision domain. For simplicity, denote the wireless devices by 1,2,…,n. Thus the device set D={1,2,…,n}. Let the set of available channels be {L,L+1,L+2,…,U} (L<U). For each device i, the channels that can be accessed are ℓi through ui, that is, ℓi, ℓi+1,…,ui. Clearly, we always have L≤ℓi≤ui≤U.Our target is to find an algorithm to compute a setC of control channels. This set C must be a subset of available channels {L,L+1,L+2,…,U}. It should also include at least one accessible channel for each device, that is, for all device i∈D, there should exist c∈C such that ℓi≤c≤ui. We want to minimize the cardinality of C under the above constraint.


## 3. The Algorithm

We summarize our algorithm in Algorithm1.Algorithm 1:Algorithm for finding optimal control channel set.
Step1:
D
'
←
D;
for eachi∈D'
for eachj∈D' such that j≠i
if ℓi≤ℓj and uj≤ui
D
'
←
D
'
-
{
i
};
break;
C
←
ϕ;
Step2:
Repeat untilD'=ϕ
i
←
arg
min
i
∈
D
′
ℓ
i
;
C←C∪{ui};
for eachj∈D' such that j≠i
ifℓj≤ui
D'←D'-{j};
D
'
←
D
'
-
{
i
};


## 4. Algorithm Analysis

Theorem 4.1 (correctness).
When the algorithm terminates,C is a subset of {L,L+1,L+2,…,U} with the smallest cardinality such that for all i∈D, there exists c∈C, ℓi≤c≤ui.Proof.
LetC⋆ be the value of C when the algorithm terminates. We divide our proof into two parts: first, we show that for all i∈D, there exists c∈C⋆ such that ℓi≤c≤ui. Second, we show the cardinality of C⋆ is the smallest among all subsets of {L,L+1,L+2,…,U} that satisfy the above constraint.
Let the value ofD′ be D0′ after Step 1 of the algorithm finishes and before Step 2 begins. For any k∈D0′, there exists an iteration in Step 2, in which k is removed from D′. There are two possibilities. The first possibility is that i=k in that iteration and thus k is removed from D′. The other possibility is that i≠k in that iteration but ℓk≤ui in that iteration, and thus k is removed from D′.
For the first possibility, it is clear thatuk=ui is added to C in that iteration. Hence, ui=uk∈C⋆.
For the second possibility, sinceui is added to C in that iteration, we know that ui∈C⋆. We have also known that ℓk≤ui. Furthermore, we should have ui≤uk because otherwise we would have ℓi≤ℓk and uk<ui, which implies that i should have been removed from D′ in Step 1. Since i∈D0′, the above is impossible. Consequently, we must have ui≤uk.
Putting together the above two possibilities, we know that for anyk∈D0′, the value ui found above always satisfies that ui∈C⋆ and that ℓk≤ui≤uk. Consequently, we have proved the following Lemma.
Lemma
1. For alli∈D0′, there existsc∈C⋆such thatℓi≤c≤ui.
Now we replaceD0′ with D in Lemma 1. We note that D0′⊆D and that, due to Step 1 of the algorithm, for any k∈D-D0′, there exists m such that ℓk≤ℓm and um≤uk, and that either m is removed from D′ after k has been removed, or m∈D0′. Applying induction to the above statement, we can easily obtain that, for any k∈D-D0′, there exists m∈D0′ such that ℓk≤ℓm and um≤uk. Combining this with Lemma 1, we get that there exists c∈C⋆ such that ℓk≤c≤uk.
So far we have finished the first part of our proof. Now let us proceed to the second part.
Consider any subsetCX of {L,L+1,L+2,…,U} such that for all i∈D0′, there exists c∈CX such that ℓi≤c≤ui. Now sort the elements of CX in increasing order: e1,e2,…,e|CX|. Using induction, below we show that ei≤fi, where fi is the element added to C in the ith iteration of Step 2 of the algorithm.
Due to the algorithm,f1=ui1 where i1=argmini∈D0′ℓi. Assuming for the purpose of contradiction that e1>f1, then for all i, ei>f1. Hence, there is no c∈CX such that ℓi1≤c≤ui1. Contradiction. So e1≤f1.
Next, suppose thatek≤fk. Let the value of D′ at the end of the kth iteration of Step 2 be Dk′. Therefore, fk+1=uik+1 where
(4.1)ik+1=argmin⁡i∈Dk′li.
Now assume for the purpose of contradiction that ek+1>fk+1; thus, ek+1>uik+1. Consequently, for all k′≥k+1, ek′>uik+1. On the other hand, for all k′≤k, ek′≤ek≤fk=uik. Due to the algorithm, we must have uik<ℓik+1 because otherwise ik+1 would have been removed from D′ in the kth iteration. Consequently, for all k′≤k, ek′<ℓik+1. In summary, we have obtained that there is no ek′∈CX such that ℓik+1≤ek′≤uik+1. Contradiction.
Therefore, if|CX|<|C⋆|, then e1≤f1, e2≤f2,…,e|CX|≤f|CX|. Since f|CX|=ui|CX|<ℓi|CX|+1, this implies that there is no c∈CX such that ℓi|CX|+1≤c≤ui|CX|+1, which contradicts our definition of CX. Hence, we must have that |CX|≥|C⋆|.
The above has actually proved the following lemma.
Lemma
2
.
C
⋆
is a subset of
{
L
,
L
+
1
,
L
+
2
,
…
,
U
}
with the smallest cardinality such that for all
i
∈
D
0
′
, there exists
c
∈
C
⋆
,
ℓ
i
≤
c
≤
u
i
.
Finally, it suffices to observe that any subset of{L,L+1,L+2,…,U} such that for all i∈D, there exists c∈C⋆, ℓi≤c≤ui is also a subset of {L,L+1,L+2,…,U} such that for all i∈D0′, there exists c∈C⋆, ℓi≤c≤ui. Consequently, combining Lemmas 1 and 2, we get that C⋆ is a subset of {L,L+1,L+2,…,U} with the smallest cardinality such that for all i∈D, there exists c∈C⋆, ℓi≤c≤ui.Theorem 4.2.
The time complexity of the algorithm isO(n2).Proof.
In step 1, at the beginning of the loop,|D′|=|D|=n. Hence, the loop clearly has n(n-1) iterations. The time complexity of this step is thus O(n2).
Note that throughout step 1,|D′| can only decrease but not increase. Hence, in step 2, at the beginning of the loop, |D′|≤n. In each iteration of this loop, |D′| must decrease by at least 1 because of the last line of the algorithm. Therefore, the number of iterations in the external loop must be no more than n. On the other hand, the number of iternations in each internal loop is no more than the current value of |D′|-1 and so no more than n-1. Consequently, the time complexity of this step is O(n2).
Summarizing the above analysis, the total time complexity of the algorithm isO(n2).



---

*Source: 653523-2012-08-29.xml*