# Different Approximation Algorithms for Channel Scheduling in Wireless Networks

Authors: Qiufen Ni; Chuanhe Huang; Panos M. Pardalos; Jia Ye; Bin Fu
Journal: Mobile Information Systems
 (2020)

---

## Abstract

We introduce a new two-side approximation method for the channel scheduling problem, which controls the accuracy of approximation in two sides by a pair of parametersf,g. We present a series of simple and practical-for-implementation greedy algorithms which give constant factor approximation in both sides. First, we propose four approximation algorithms for the weighted channel allocation problem: 1. a greedy algorithm for the multichannel with fixed interference radius scheduling problem is proposed and an one side O1-IS-approximation is obtained; 2. a greedy O1,O1-approximation algorithm for single channel with fixed interference radius scheduling problem is presented; 3. we improve the existing algorithm for the multichannel scheduling and show an EOd/ε time 1−ϵ-approximation algorithm; 4. we speed up the polynomial time approximation scheme for single-channel scheduling through merging two algorithms and show a 1−ϵ,O1-approximation algorithm. Next, we study two polynomial time constant factor greedy approximation algorithms for the unweighted channel allocation with variate interference radius. A greedy O1-approximation algorithm for the multichannel scheduling problem and an O1,O1-approximation algorithm for single-channel scheduling problem are developed. At last, we do some experiments to verify the effectiveness of our proposed methods.


---

## Body

## 1. Introduction

An important problem in wireless network is to develop efficient algorithms for maximum throughput by scheduling channels among many nodes. Based on the Shannon capacity formula, we can know that there is a minimum SINR required for each user in the network of wireless communication, as the existence of signal propagation loss during the process of data transmission; when the distance of a communication user pair is larger than the threshold, the effect of the received power in the receiver can be neglected because the receiver’s SINR is less than the threshold. There is an interference between two users in the same channel when their distance is less than a certain distance. Given a set of users, we find a way which schedules a maximal number of them without introducing interference between any two of them. The weighted version of this problem is to achieve the sum of maximal weights for the users assigned channels for communication. The channel scheduling problem is NP-hard even in the single-channel model [1] and has been studied in a series of papers (for example, [2–4]). According to IEEE standard 802.11a, there are 13 orthogonal channels provided for wireless network [5]. The multichannel or multi-radio scheduling problem is essential to guarantee the performance of wireless networks.A channel scheduling problem for a given graphGV,E is to select an edge subset E′∈E and assign a channel to each edge in E′ under the restriction so that all edges in E′ are interference-free. The node exclusive interference model has been studied in many articles (for example, [6–12]). The algorithms for the single-channel or single-radio scheduling are reported in [13, 14]. For the model not allowing two communication edges to share the same node, the optimal scheduling problem is converted into matching problem [15–17] which has a polynomial time solution. Some approximation algorithms for single channel were reported in [18] which show the existence of a theoretical polynomial time approximation scheme for the single-channel assignment. A simple greedy algorithm which is easy to implement is shown to have a constant factor approximation [18] for the single-channel assignment.The theoretical research about the multichannel scheduling has been reported in [19–23]. In [4], they formulate the channel allocation problem as an NP-hard non-linear integer programming problem and then propose a probabilistic polynomial time 1−1/e-approximation algorithm based on linear programming. A joint approach between routing and channel scheduling is shown in [24]. Some constant factor approximation algorithms are shown in [25] for assigning a minimum number of channels for a conflict-free communication, which are also NP-hard [26, 27].A polynomial time approximation scheme was developed in [28] for multi-radio and multichannel wireless network with very high computational complexity EOd/∈2 for 1−ϵ-approximation, where d is the number of channels. This theoretical result is not practical for implementation.A maximal independent set problem based on joint scheduling and routing optimization is studied in [2], which is a mixed integer non-linear programming NP-hard problem. It developed a column generation based ϵ-approximation-bounded approximation algorithm, which can find tight ϵ-bounded approximate solutions and the optimal solutions.We introduce the notion of two-side approximation for the channel scheduling problem. A pair of parametersf,g controls the accuracy of approximation in this paper. A f,g-approximation satisfies ∑e∈E′We≥∑e∈OptWe/f and ∑e∈E−E′We≤g∑e∈E−Opt∗We, where Opt∗ is the set of edges assigned channels in an optimal solution and We is the weight of edge e. A f-approximation satisfies ∑e∈E′We≥∑e∈OptWe/f. Our two-side approximation approach combines two complementary problems. The first one is to maximize the total weights of communication edges that have been assigned channels, and the second one is to minimize the total weight of edges that do not receive channel for communication. It brings a more accurate tool for the approximation algorithms for the channel scheduling problem.As the approximation scheme developed by Cheng et al. [28] has very high computational complexity, it is impossible to implement with software. Finding simple and efficient algorithm for the multichannel scheduling problem is still a challenging research topic. We show that a simple greedy algorithm can obtain an O1,O1-approximation for the single-channel scheduling problem. In many cases, the greedy algorithms give much more accurate results than the worst ratio. Furthermore, we develop an EO1/ϵ time 1−ϵ,O1-approximation algorithm for the single-channel scheduling problem. We also show that a simple greedy algorithm satisfies ∑e∈E′We≥∑e∈OptWe/Ω1, which can obtain an O1-approximation for the single-channel scheduling problem. We also develop a EO1/ϵ time 1−ϵ-approximation algorithm for the multi-channel scheduling problem.Our proposed multi-channel scheduling algorithm can be used in many wireless systems in which the number of users is larger than the number of subchannels; this case is considered in [29] where they study the channel assignment problem in uplink wireless communication system. It also can be used in the distributed data transmission system with limited communication resources, which is shown in [30]. The proposed methods are also suitable for channel assignment problem in the cellular-VANET heterogeneous wireless networks, which is studied in [25]. Our proposed channel scheduling approach has a wide range of applications and can be applied to different wireless resource allocation scenarios.We also develop a polynomial time constant factor greedy approximation algorithm for the multi-channel scheduling that allows variate interference radius among those nodes. The paper is organized as follows: in Section2, we present approximation algorithms for the weighted scheduling problems. The interference range is determined by a uniform parameter t, but the edges of communication have different weights. In Section 2.2, we show that a greedy algorithm for multi-channel assignment has a constant factor approximation. In Section 2.3, we show a two-side approximation algorithm for the single-channel assignment problem and show that there does not exist such an approximation for the multi-channel assignment problem. In Section 2.4, we give improved approximation schemes for both single-channel and multi-channel assignment problems. In Section 3, we develop the approximation for the unweighted channel assignment problem. This is the case that all the edges have weight 1, but the interference radius is not fixed. Some simulation results for the greedy approximation algorithm for the multi-channel assignment are given in Section 4. We draw conclusion in Section 5.


## 2. Weighted Channel Assignment

We develop approximation algorithms for the weighted channel assignment. The interference range is controlled by a fixed parametert. The polynomial time approximation scheme for multi-channel scheduling problem is based on this model [28].


### 2.1. Definitions and Models

The network is modeled as an edge-weighted graphGV,E, where V is the set of nodes and E is the set of edges for traffic flow. The weight of each edge is often represented by the rate of network traffic. For each e∈E, let We be the weight of e.Definition 1.
Given an edge-weighted network graphGV,E, let du,v denote the distance between nodes u and v. The function du,v can be either the geometric distance between u and v in Euclidean space if V is a set of points in Euclidean space or the hop distance between u and v in the graph G. The edge distance between two edges e1=u1,u2 and e2=v1,v2 is defined by EDe1,e2=mini,j∈1,2dui,vj. Note that the graph GV,E only considers those edges E that need to do communication over a wireless network. No silent edge is included in E.
A setE′ of edges is t-interference-free matching if EDe1,e2>t for any two edges e and e′ in E′, where t is distance threshold for interference.
A (multiple) channel assignment problem has a demand graphG=V,E that requests communication for u,v∈E. A wireless network may not have the resource to satisfy the communications for all edges. A channel assignment algorithm selects a subset E′⊆E and assigns a channel to each edge in E′ so that the edges in the same channel form a t-interference-free matching, where t is distance threshold for interference. When there is only one channel available for the entire demand graph, the channel assignment problem is called single-channel assignment problem. Otherwise, it is called multi-channel assignment problem.
A channel assignment for an edgee=u,v is represented by e,K, where K is a channel. Assume that M is a set of channel assignments. A channel assignment e,K is interfered by M if there is a channel assignment e′,K∈M such that EDe,e′≤t. Define M∗ to be the set of all edges e with e,K∈M for some channel K. If W. is the weight function for the edges in G, define WM∗=∑e∈M∗We. An optimal solution for a channel assignment problem G=V,E with weight function W. is a set Opt of channel assignments for edges such that WOpt∗ is the maximum.Definition 2.
Assume thatA is a set of channel assignments for G.LetτAe=maxKe′:e′,K∈AandEDe,e′≤t.DefineτAG=maxe∈GτAe.DefineτG=maxAτAG,
whereτAe is the interference degree of an edge e∈E, τAG is the interference degree of the graph G=V,E, and t is distance threshold for interference.
If the distance is the Euclidean distance and all nodes are on the plane, thenτG≤11, which is shown in Lemma 1. If the distance is the hop distance and all nodes are on the plane, then τG≤49, which was proved in [18]. Therefore, τG does not depend on the threshold.Definition 3.
Assume thatG is a channel scheduling problem. We define some measures for approximations.(i)
Anf-IS-approximation App for the channel scheduling problem satisfies the condition WApp∗≥WOpt∗/f.(ii)
Ag-VC-approximation App for the channel scheduling problem satisfies the condition WE−App∗≤gWE−Opt∗.(iii)
Af,g-approximation for the channel scheduling problem satisfies the conditions WApp∗≥WOpt∗/f and WE−App∗≤gWE−Opt∗.Lemma 1.
Assume that all nodes in the demand graphG=V,E are points on a plane. Then, τG≤11 for the Euclidean distance t as the threshold for the interference.Proof.
Lete=u,v be an edge in the graph G. The distance between u and v is at most t (otherwise, they cannot communicate). Edge e and another edge e′=u′,v′ have interference if one of u and v and one of u′ and v′ have distance at most t. Let each node be a center of a circle of diameter t/2 on a plane. Let Cp,r represent a circle with center at p and radius r. Let A be a channel assignment for G, which gives a list of disjoint circles C1,⋅⋅⋅,Cm such that each node in those edges with channel assigned is a circle center. Circle Cu,t/2 touches at most 6 circles among C1,⋅⋅⋅,Cm, and so does Cv,t/2. If both Cu,t/2 and Cv,t/2 touch 6 circles, there must exist at least one of them touched by both Cu,t/2 and Cv,t/2 because the distance between u and v is at most t.


### 2.2. Multiple Channel with Fixed Interference Radius Scheduling

In this section, we present a greedy approximation algorithm for the multi-channel scheduling problem shown in Algorithm1. We can only show a one-side O1-approximation for the multi-channel scheduling problem.Algorithm 1: Greedy-multi-channel with fixed interference radius.
Input: a weighted graphG, and a distance parameter t for the largest distance of interference.Output:L′(1)
Sort all edges by the increasing order of their weights and put those edges in a listL;(2)
LetL′=∅;(3)
Repeat;(4)
Select an edgee=u,v with the largest weight from L;(5)
If there is a channelK for e not being interfered by L′(6)
Then, assign the channelK to e and put e,K into L′;(7)
Removee from L;(8)
UntilL is empty;(9)
ReturnL′;In the multi-channel scheduling problem, we assume that each node hasd channels available for allocation. Two nodes u and v can communicate if their corresponding edge e=u,v is assigned a channel (the distance between u and v is at most the threshold t) and has no interference with other edges in the same channel.We note that when there is a setF of edges that have been assigned channels, it is straightforward to check if a new edge e will be interfered at certain channel K. This can be done by checking EDe,ei≤t for all ei∈FK, where FK is the subset of edges in F assigned channel K.For the case that all nodes are on a plane, and the distance is either Euclidean distance or hop distance, the following theorem gives a constant factor approximation for the multiple channel assignment problem asτG is bounded by constants in both distances.Theorem 1.
The Algorithm 1 greedy-multi-channel (.) is agα-IS-approximation algorithm for the multi-radio multi-channel scheduling problem and has the computational complexity O|E|2, where gα=1+τG/α+2α/1−α and α=τG/2+τG.Proof.
Assume thatOpt is an optimal solution for the channel scheduling problem. Let App be an approximate solution derived by greedy-multi-channel (.).
For each edgeg in Opt∗, assign an edge e, denoted by Hg, in App∗ such that Re is the least among all edges with interference with g. When the algorithm greedy-multi-channel (.) processes an edge e=u,v, the available channels for e are those which are not allocated to the edges with end points at either u or v.Claim 1.
For each edgeg in Opt, Wg≤Wg′ for each g′ that is already processed before g.Proof.
It follows from the greedy algorithm which processes the edges according the decreasing order of their weights.
Letd be the total number of channels. For each edge e=u,v∈Opt∗−App∗, we consider two cases. The constant α used in the two cases will be assigned later.Case 1.
There are at leastαd channels available for the edge e when e is processed. Such an edge e is of type 1.
In this case, sincee is not assigned for a channel, there must be at least αd edges e′ that are already assigned channels and have EDe,e′≤t. For such an edge e′ with EDe,e′≤t, let be,e′=We/αd. Since e′ is processed before e in the algorithm, we have We≤We′. Thus, be,e′≤We′/αd. Let be,e′=0 for all the other edges e′. For each edge e of type 1, we have inequality(1)∑e′be,e′≥We.
For each edgee′ in App∗, we have(2)∑eis of type1be,e′≤d⋅τG⋅We′αd=τGWe′α=b1We′,where b1=τG/α.Case 2.
There are fewer thanαd channels available for the edge e=u,v when e is processed in greedy-multi-channel (.). Such an edge e is of type 2.
For at least one ofu and v, say u, there are at least 1−αd/2 channels that are already assigned. For each edge e′ with an end point in u already assigned channels, let be,e′=We/1−αd/2=2We/1−αd≤2We′/1−αd. Let be,e′=0 for all the other edges e′. For each edge e′∈App∗, we have(3)∑eis of type2be,e′≤αd⋅2We′1−αd=2We′1−α=b2We′,where b2=2α/1−α. For each edge e of type 2, (4)∑e′be,e′≥We.
Each edge inOpt∗−App∗ is of either type 1 or type 2. We have(5)WOpt∗−App∗=∑eis of type1We+∑eis of type2We≤∑eis of type1∑e′∈App∗be,e′+∑eis of type2∑e′∈App∗be,e′by1and1≤∑e′∈App∗∑eis of type1be,e′+∑e′∈App∗∑eis of type2be,e′≤∑e′∈App∗b1We′+∑e′∈App∗b2We′by1and1≤b1+b2WApp∗.
We have(6)WOpt∗=WOpt∗∩App∗+WOpt∗−App∗≤WApp∗+WOpt∗−App∗≤WApp∗+b1+b2WApp∗by1≤1+b1+b2WApp∗≤1+τGα+2α1−αWApp∗.
Select the constantα so that 1+τG/α+2α/1−α is minimal. Let gα=1+τG/α+2α/1−α=−1+τG/α+2/1−α. Let gα′=2/1−α2−τG/α2=0. We have α=τG/2+τG. Thus, the ratio of approximation is gα.


### 2.3. Single Channel with Fixed Interference Radius Scheduling

In this section, we present a greedyO1,O1 approximation algorithm for the channel scheduling problem shown in Algorithm 2. Our two-side approximation bound for the greedy algorithm improves the one-side approximation bound in [18].Algorithm 2: Greedy-single-channel with fixed interference radius (G,t).
Require: a weighted graphG, and a distance parameter t for the largest distance of interference.Ensure:L′;(1)
Sort all edges by the decreasing order of their weights and put those edges in a listL;(2)
LetL′=∅;(3)
Repeat;(4)
Select an edgee=u,v with the largest weight from L;(5)
Ife is not being interfered by L′;(6)
Then, assign the channelK to e and put e,K into L′;(7)
Removee from L;(8)
UntilL is empty;(9)
ReturnL′;We note that when there is a setF of edges that have been assigned channels, it is straightforward to check if a new edge e will be interfered at certain channel K. This can be done by checking EDe,ei≤t for all ei∈FK, where FK is the subset of edges in F in channel K.Theorem 2.
The Algorithm2 greedy-single-channel (.) is a τG,τG-approximation algorithm for the single-channel scheduling problem and has the computational complexity O|E|2.Proof.
Assume thatOpt is an optimal solution for the channel scheduling problem. Let App is an approximate solution derived by greedy-single-channel (.).
For each edgeg in Opt∗, assign a edge e, denoted by Hg, in App∗ such that e has the largest weight among all edges with interference with g.
Consider an edgee=u,v selected in App∗. Let Ae=e1,⋅⋅⋅,em be the list of edges with Hei=e.Claim 2.
For each edgeg in Opt, Wg≤WHg.Proof.
Ifg is in App∗, we consider an edge has interference with itself. Thus, it is trivial. By the definition of Hg, Hg has the largest of weight among all edges in Opt∗ with interference with g.
Assume thatg′ is the first edge in App∗ and has the same channel with g∈Opt∗. Before selecting g′ for assigning a channel, there is no interference between g and other edges in App. Therefore, Wg′≥Wg (otherwise, g′ should not be selected for channel assignment). Since Hg has the largest weight among all edges with interference with g in App, we have WHg≥Wg′≥Wg.
Assume thatApp contains channel assignments for edges e1,⋅⋅⋅,em. Partition Opt∗ into Ae1,⋯,Aem. By Claim 2, we have that(7)τGWei≥τeiWei≥∑e′∈AeiWe′.
Therefore, we haveτGWApp∗≥WOpt∗. Thus, App is a τG-IS approximation for G.
On the other hand, for eachei∈E−Opt∗∩App∗, we always have τeiWei≥∑e′∈AeiWe′ (by Claim 2). For each edge e′ in E−App∗∩Opt∗, there is an edge e∈App∗ such that e and e′ have the interference at the same channel (otherwise, e′ would be assigned some channel by Greed1 (.)). Furthermore, e∉Opt∗ since e has interference with e′. Therefore, there is an edge e∗∈E−Opt∗∩App∗ such that e′∈Ae∗. By inequality (1), we have(8)WE−App∗∩Opt∗≤τGWE−Opt∗∩App∗.
We have the inequalities:(9)WE−App∗=WE−App∗∩E−Opt∗+WE−App∗∩Opt∗≤WE−Opt∗∩E−App∗+τGWE−Opt∗∩App∗by1≤τGWE−Opt∗∩E−App∗+WE−Opt∗∩App∗=τGWE−Opt∗.
This givesWE−App∗≤τGWE−Opt∗. Therefore, greedy-single-channel (.) gives a τG,τG-approximation.Theorem 3.
Letdu,v be the Euclidean distance and the input has the geometric position of all nodes in a Euclidean plane. The Algorithm 2 greedy-single-channel (.) gives a 11,11-approximation for the single-channel scheduling problem and runs in OE time.Proof.
For the implementation, we partition the plane into grid of sizet×t. When an edge is assigned a channel, put the assignment into the corresponding grid for one of its two nodes in the edge. When assigning a channel a new edge, check the assigned edges in the nearby O1 grids. Thus, each edge only costs an O1 time.
Ifdu,v is defined to be the hop distance, then τG is at most 49, which is shown in [18]. If du,v is the Euclidean distance, we show that τG is at most 11.Theorem 4.
Letdu,v be the hop distance in network graph GV,E. The Algorithm 2 greedy-single-channel (.) gives a 49,49-approximation for the single-channel scheduling problem and runs in O|E|2 time.Proof.
It follows from Theorem2 and the fact τG≤49, which is shown in [18]. A brute force implementation takes O|E|2 time.
For the multi-channel scheduling problem, we show that it does not have two-side approximation unless P=NP.Theorem 5.
Assume thatfn is a function from N to N with fn>0. Then, there is no polynomial time fn-VC-approximation for the multiple channel scheduling problem unless P=NP.Proof.
LetG be the input graph of the multi-channel assignment problem. Assume that there exists a polynomial time fn-VC-approximation algorithm, the multiple channel scheduling problem. Let k be the least number of channels that can support the communications of all edges in G. When the number of total available channels is equal to k, an optimal solution Opt assigns channels to all edges in G. This makes WE−Opt∗=0. When the approximate solution App satisfies WE−App∗≤fnWE−Opt∗=0, it becomes an optimal solution. Thus, we can search the least number of channels from 1 to k to support all edges in G. This brings a polynomial time solution for the conflict-free channel assignment problem, which was proved to be NP-hard [26]. Therefore, P=NP.
We have the following corollary that shows we cannot have a two-side approximation for the multi-channel scheduling problem.Corollary 1.
Assume thatfn is a function from N to N with fn>0. Then, there is no polynomial time fn,fn-approximation for the multiple channel scheduling problem unless P=NP.
In Section2.4, we show a faster approximation for 1−ϵ-IS-approximation than that in [28]. Part of the algorithm is based on the shifting technology which has originated from [31] and has been widely used in developing approximation for networking problem (for example, [18, 28]).
In Section3.1, we present a greedy O1-approximation algorithm for the unweighted multi-channel scheduling problem with variate interference radii.
In Section3.2, we present a greedy O1,O1 approximation algorithm for the unweighted single channel with variate interference radii scheduling problem.
In Section4, we did some simulation for the multi-channel assignment problems for the greedy algorithm. Greedy algorithm is easy to implement and fast to output the result. Its experimental results show much better performance than the theoretical approximation ratio, which is derived under the worst case analysis.


### 2.4. Improving the Existing Algorithm for the Multichannel Scheduling

We show a faster approximation for1−ϵ-IS-approximation than that in [28]. Let PTAS (.) (polynomial-time approximation scheme) represent the algorithm described below. Part of the algorithm is based on the shifting technology which has originated from [31] and has been widely used in developing approximation for networking problem (for example, [18, 28]).Assume that the maximal distance of two nodes for communication is one. Lett be the distance of interference. The grid size is D=t+2. The plane is partitioned into grids of size D×D.Letϵ be a constant in (0, 1). Define m = ⌈1/1−1−ϵ⌉.For two integersa,b∈0,m−1, define Pa,b to be a partition such that the plane is partitioned into the disjoint union of squares of size mD×mD, and the left bottom point of each square of size mD×mD in Pa,b has coordinates imD+a,imD+b for some integers i and j.Lemma 2.
There is amOdm time algorithm to find an optimal solution for the multi-channel scheduling problem in a m×m square with at most d channels in each node.Proof.
We apply a division and conquest method to find an optimal solution. Partition am×m square into four squares by one strip in the vertical middle and one strip in the horizontal middle. The width of the two stripes is equal to the width of the grid t+2. We can only select at most Om edges in the two strips. The number of cases of choices is |E|Om for a single channel. The number of cases of choices is |E|Odm for d channels. The four sub-problems in the four sub-squares can be solved independently.
LetTm be the computational time for solving the channel scheduling problem in a m×m square. We have the recursive equation: Tm=|E|Odm4Tm/2. Select a constant c0 so that Tm=|E|c0m4Tm/2. Expanding the recursion, we have(10)Tm=Ec0dm4Tm2=4OlogmEc0dm2+c0dm22+c0dm23+...=EOdmmO1.Theorem 6.
Assume thatϵ is an arbitrary constant in 0,1. Then, there is an |E|Od/ϵ time algorithm to give a 1−ϵ-IS-approximation for the multi-channel scheduling with d channels.Proof.
A point is in the boundary ofGi,j if it is in a D×D grid in the boundary of a mD×mD big grid of Pi,j. Let Ei,jB,O be the set of all edges that connect the points in the boundary of Gi,j in an optimal solution.
AssumePi,j is the disjoint union of mD×mD grids Q1∪Q2∪,…,Qt. Let OQi be the optimal solution for the set of edges connecting at least one node not in any D×D boundary grid of Qi. Let Ei,jI=OQ1∪OQ2∪,…,∪OQt. We have(11)WEi,jB,O+WEi,jI≥WOpt∗.Each boundary grid is in at most 2m−1Pi,j. We also have ∑i,jWEi,jB,O≤2m−1WOpt∗. Therefore, there are i0 and j0 such that(12)WEi0,j0B,O≤2m−1m2WOpt∗.
By inequalities (11) and (12), we have(13)WEi0,j0I≥WOpt∗−WEi0,j0B,O≥WOpt∗−2m−1m2WOpt∗≥m−12m2WOpt∗≥1−ϵWOpt∗.
The computational time is reduced toEO1Tm, where Tm is the time for finding the optimal solution in a m×m area. By Lemma 2, the algorithm runs in EOd/ϵ time and gives an 1−ϵ-approximation.


### 2.5. Merging Two Algorithms in Single-Channel Scheduling

In this section, we show that merging Algorithm1 and PTAS (.) can speed up the polynomial time approximation scheme in many cases for the single-channel scheduling. We propose Algorithm 3 which shows a polynomial time 1−ϵ,O1-approximation scheme for the single-channel scheduling problem.Algorithm 3: Optimized algorithm in single-channel MG,ϵ.
Require: constantϵ∈0,1 and graph GV,E.Ensure:Appi(1)
LetApp1=App2=∅;(2)
Run greedy-single-channel (.) to find anO1,O1-approximation App1;(3)
Letc=WOpt/WE;(4)
If1−τG1−c≥1−ϵ;(5)
Then, run PTAS (.) to find an1−ϵ-IS-approximation App2;(6)
ReturnAppi with WAppi∗=maxWApp1∗,WApp2∗;Lemma 3.
Assume that a channel scheduling problemG satisfies the condition WOpt≥cWE. Then, a g-VC-approximation for the channel scheduling implies a 1−g1−c-IS-approximation.Proof.
Assume an approximationApp satisfies WE−App∗≤gWE−Opt∗.(14)WApp∗=WE−WE−App∗≥WE−gWE−Opt∗≥WE−g1−cWE≥1−g1−cWE≥1−g1−cWOpt∗.Theorem 7.
Assume thatϵ is an arbitrary constant in 0,1. Then, there is an |E|O1/ϵ time algorithm to give a 1−ϵ,O1-approximation for the single-channel scheduling. Furthermore, Algorithm 3 runs in O|E|2 time if τG1−WOpt∗/WE≤ϵ, where G is the graph of wireless network.Proof.
By Theorem2, we have that App1 is a τG,τG-approximation for the single-channel scheduling problem with WE−App1∗≤τGWE−Opt∗ and WApp1∗≤τGWOpt∗. By Lemma 3, if g1−WOpt∗/WE≤ϵ, then App1 is a 1−ϵ-IS-approximation, where g=τG.
SinceApp2 is a 1−ϵ-IS-approximation for the channel scheduling problem and App2 is also an approximation for the channeling problem, we have WAppi∗ with WAppi∗=maxWApp1∗,WApp2∗ being at most WOpt∗ and at least WOpt∗/1−ϵ. Therefore, Appi is a 1−ϵ-IS-approximation for the channel scheduling problem.
SinceWE−Appi∗≤WE−App1∗≤O1WE−Opt∗, we have that Appi is a 1−ϵ,O1-approximation for the channel scheduling problem.


## 2.1. Definitions and Models

The network is modeled as an edge-weighted graphGV,E, where V is the set of nodes and E is the set of edges for traffic flow. The weight of each edge is often represented by the rate of network traffic. For each e∈E, let We be the weight of e.Definition 1.
Given an edge-weighted network graphGV,E, let du,v denote the distance between nodes u and v. The function du,v can be either the geometric distance between u and v in Euclidean space if V is a set of points in Euclidean space or the hop distance between u and v in the graph G. The edge distance between two edges e1=u1,u2 and e2=v1,v2 is defined by EDe1,e2=mini,j∈1,2dui,vj. Note that the graph GV,E only considers those edges E that need to do communication over a wireless network. No silent edge is included in E.
A setE′ of edges is t-interference-free matching if EDe1,e2>t for any two edges e and e′ in E′, where t is distance threshold for interference.
A (multiple) channel assignment problem has a demand graphG=V,E that requests communication for u,v∈E. A wireless network may not have the resource to satisfy the communications for all edges. A channel assignment algorithm selects a subset E′⊆E and assigns a channel to each edge in E′ so that the edges in the same channel form a t-interference-free matching, where t is distance threshold for interference. When there is only one channel available for the entire demand graph, the channel assignment problem is called single-channel assignment problem. Otherwise, it is called multi-channel assignment problem.
A channel assignment for an edgee=u,v is represented by e,K, where K is a channel. Assume that M is a set of channel assignments. A channel assignment e,K is interfered by M if there is a channel assignment e′,K∈M such that EDe,e′≤t. Define M∗ to be the set of all edges e with e,K∈M for some channel K. If W. is the weight function for the edges in G, define WM∗=∑e∈M∗We. An optimal solution for a channel assignment problem G=V,E with weight function W. is a set Opt of channel assignments for edges such that WOpt∗ is the maximum.Definition 2.
Assume thatA is a set of channel assignments for G.LetτAe=maxKe′:e′,K∈AandEDe,e′≤t.DefineτAG=maxe∈GτAe.DefineτG=maxAτAG,
whereτAe is the interference degree of an edge e∈E, τAG is the interference degree of the graph G=V,E, and t is distance threshold for interference.
If the distance is the Euclidean distance and all nodes are on the plane, thenτG≤11, which is shown in Lemma 1. If the distance is the hop distance and all nodes are on the plane, then τG≤49, which was proved in [18]. Therefore, τG does not depend on the threshold.Definition 3.
Assume thatG is a channel scheduling problem. We define some measures for approximations.(i)
Anf-IS-approximation App for the channel scheduling problem satisfies the condition WApp∗≥WOpt∗/f.(ii)
Ag-VC-approximation App for the channel scheduling problem satisfies the condition WE−App∗≤gWE−Opt∗.(iii)
Af,g-approximation for the channel scheduling problem satisfies the conditions WApp∗≥WOpt∗/f and WE−App∗≤gWE−Opt∗.Lemma 1.
Assume that all nodes in the demand graphG=V,E are points on a plane. Then, τG≤11 for the Euclidean distance t as the threshold for the interference.Proof.
Lete=u,v be an edge in the graph G. The distance between u and v is at most t (otherwise, they cannot communicate). Edge e and another edge e′=u′,v′ have interference if one of u and v and one of u′ and v′ have distance at most t. Let each node be a center of a circle of diameter t/2 on a plane. Let Cp,r represent a circle with center at p and radius r. Let A be a channel assignment for G, which gives a list of disjoint circles C1,⋅⋅⋅,Cm such that each node in those edges with channel assigned is a circle center. Circle Cu,t/2 touches at most 6 circles among C1,⋅⋅⋅,Cm, and so does Cv,t/2. If both Cu,t/2 and Cv,t/2 touch 6 circles, there must exist at least one of them touched by both Cu,t/2 and Cv,t/2 because the distance between u and v is at most t.


## 2.2. Multiple Channel with Fixed Interference Radius Scheduling

In this section, we present a greedy approximation algorithm for the multi-channel scheduling problem shown in Algorithm1. We can only show a one-side O1-approximation for the multi-channel scheduling problem.Algorithm 1: Greedy-multi-channel with fixed interference radius.
Input: a weighted graphG, and a distance parameter t for the largest distance of interference.Output:L′(1)
Sort all edges by the increasing order of their weights and put those edges in a listL;(2)
LetL′=∅;(3)
Repeat;(4)
Select an edgee=u,v with the largest weight from L;(5)
If there is a channelK for e not being interfered by L′(6)
Then, assign the channelK to e and put e,K into L′;(7)
Removee from L;(8)
UntilL is empty;(9)
ReturnL′;In the multi-channel scheduling problem, we assume that each node hasd channels available for allocation. Two nodes u and v can communicate if their corresponding edge e=u,v is assigned a channel (the distance between u and v is at most the threshold t) and has no interference with other edges in the same channel.We note that when there is a setF of edges that have been assigned channels, it is straightforward to check if a new edge e will be interfered at certain channel K. This can be done by checking EDe,ei≤t for all ei∈FK, where FK is the subset of edges in F assigned channel K.For the case that all nodes are on a plane, and the distance is either Euclidean distance or hop distance, the following theorem gives a constant factor approximation for the multiple channel assignment problem asτG is bounded by constants in both distances.Theorem 1.
The Algorithm 1 greedy-multi-channel (.) is agα-IS-approximation algorithm for the multi-radio multi-channel scheduling problem and has the computational complexity O|E|2, where gα=1+τG/α+2α/1−α and α=τG/2+τG.Proof.
Assume thatOpt is an optimal solution for the channel scheduling problem. Let App be an approximate solution derived by greedy-multi-channel (.).
For each edgeg in Opt∗, assign an edge e, denoted by Hg, in App∗ such that Re is the least among all edges with interference with g. When the algorithm greedy-multi-channel (.) processes an edge e=u,v, the available channels for e are those which are not allocated to the edges with end points at either u or v.Claim 1.
For each edgeg in Opt, Wg≤Wg′ for each g′ that is already processed before g.Proof.
It follows from the greedy algorithm which processes the edges according the decreasing order of their weights.
Letd be the total number of channels. For each edge e=u,v∈Opt∗−App∗, we consider two cases. The constant α used in the two cases will be assigned later.Case 1.
There are at leastαd channels available for the edge e when e is processed. Such an edge e is of type 1.
In this case, sincee is not assigned for a channel, there must be at least αd edges e′ that are already assigned channels and have EDe,e′≤t. For such an edge e′ with EDe,e′≤t, let be,e′=We/αd. Since e′ is processed before e in the algorithm, we have We≤We′. Thus, be,e′≤We′/αd. Let be,e′=0 for all the other edges e′. For each edge e of type 1, we have inequality(1)∑e′be,e′≥We.
For each edgee′ in App∗, we have(2)∑eis of type1be,e′≤d⋅τG⋅We′αd=τGWe′α=b1We′,where b1=τG/α.Case 2.
There are fewer thanαd channels available for the edge e=u,v when e is processed in greedy-multi-channel (.). Such an edge e is of type 2.
For at least one ofu and v, say u, there are at least 1−αd/2 channels that are already assigned. For each edge e′ with an end point in u already assigned channels, let be,e′=We/1−αd/2=2We/1−αd≤2We′/1−αd. Let be,e′=0 for all the other edges e′. For each edge e′∈App∗, we have(3)∑eis of type2be,e′≤αd⋅2We′1−αd=2We′1−α=b2We′,where b2=2α/1−α. For each edge e of type 2, (4)∑e′be,e′≥We.
Each edge inOpt∗−App∗ is of either type 1 or type 2. We have(5)WOpt∗−App∗=∑eis of type1We+∑eis of type2We≤∑eis of type1∑e′∈App∗be,e′+∑eis of type2∑e′∈App∗be,e′by1and1≤∑e′∈App∗∑eis of type1be,e′+∑e′∈App∗∑eis of type2be,e′≤∑e′∈App∗b1We′+∑e′∈App∗b2We′by1and1≤b1+b2WApp∗.
We have(6)WOpt∗=WOpt∗∩App∗+WOpt∗−App∗≤WApp∗+WOpt∗−App∗≤WApp∗+b1+b2WApp∗by1≤1+b1+b2WApp∗≤1+τGα+2α1−αWApp∗.
Select the constantα so that 1+τG/α+2α/1−α is minimal. Let gα=1+τG/α+2α/1−α=−1+τG/α+2/1−α. Let gα′=2/1−α2−τG/α2=0. We have α=τG/2+τG. Thus, the ratio of approximation is gα.


## 2.3. Single Channel with Fixed Interference Radius Scheduling

In this section, we present a greedyO1,O1 approximation algorithm for the channel scheduling problem shown in Algorithm 2. Our two-side approximation bound for the greedy algorithm improves the one-side approximation bound in [18].Algorithm 2: Greedy-single-channel with fixed interference radius (G,t).
Require: a weighted graphG, and a distance parameter t for the largest distance of interference.Ensure:L′;(1)
Sort all edges by the decreasing order of their weights and put those edges in a listL;(2)
LetL′=∅;(3)
Repeat;(4)
Select an edgee=u,v with the largest weight from L;(5)
Ife is not being interfered by L′;(6)
Then, assign the channelK to e and put e,K into L′;(7)
Removee from L;(8)
UntilL is empty;(9)
ReturnL′;We note that when there is a setF of edges that have been assigned channels, it is straightforward to check if a new edge e will be interfered at certain channel K. This can be done by checking EDe,ei≤t for all ei∈FK, where FK is the subset of edges in F in channel K.Theorem 2.
The Algorithm2 greedy-single-channel (.) is a τG,τG-approximation algorithm for the single-channel scheduling problem and has the computational complexity O|E|2.Proof.
Assume thatOpt is an optimal solution for the channel scheduling problem. Let App is an approximate solution derived by greedy-single-channel (.).
For each edgeg in Opt∗, assign a edge e, denoted by Hg, in App∗ such that e has the largest weight among all edges with interference with g.
Consider an edgee=u,v selected in App∗. Let Ae=e1,⋅⋅⋅,em be the list of edges with Hei=e.Claim 2.
For each edgeg in Opt, Wg≤WHg.Proof.
Ifg is in App∗, we consider an edge has interference with itself. Thus, it is trivial. By the definition of Hg, Hg has the largest of weight among all edges in Opt∗ with interference with g.
Assume thatg′ is the first edge in App∗ and has the same channel with g∈Opt∗. Before selecting g′ for assigning a channel, there is no interference between g and other edges in App. Therefore, Wg′≥Wg (otherwise, g′ should not be selected for channel assignment). Since Hg has the largest weight among all edges with interference with g in App, we have WHg≥Wg′≥Wg.
Assume thatApp contains channel assignments for edges e1,⋅⋅⋅,em. Partition Opt∗ into Ae1,⋯,Aem. By Claim 2, we have that(7)τGWei≥τeiWei≥∑e′∈AeiWe′.
Therefore, we haveτGWApp∗≥WOpt∗. Thus, App is a τG-IS approximation for G.
On the other hand, for eachei∈E−Opt∗∩App∗, we always have τeiWei≥∑e′∈AeiWe′ (by Claim 2). For each edge e′ in E−App∗∩Opt∗, there is an edge e∈App∗ such that e and e′ have the interference at the same channel (otherwise, e′ would be assigned some channel by Greed1 (.)). Furthermore, e∉Opt∗ since e has interference with e′. Therefore, there is an edge e∗∈E−Opt∗∩App∗ such that e′∈Ae∗. By inequality (1), we have(8)WE−App∗∩Opt∗≤τGWE−Opt∗∩App∗.
We have the inequalities:(9)WE−App∗=WE−App∗∩E−Opt∗+WE−App∗∩Opt∗≤WE−Opt∗∩E−App∗+τGWE−Opt∗∩App∗by1≤τGWE−Opt∗∩E−App∗+WE−Opt∗∩App∗=τGWE−Opt∗.
This givesWE−App∗≤τGWE−Opt∗. Therefore, greedy-single-channel (.) gives a τG,τG-approximation.Theorem 3.
Letdu,v be the Euclidean distance and the input has the geometric position of all nodes in a Euclidean plane. The Algorithm 2 greedy-single-channel (.) gives a 11,11-approximation for the single-channel scheduling problem and runs in OE time.Proof.
For the implementation, we partition the plane into grid of sizet×t. When an edge is assigned a channel, put the assignment into the corresponding grid for one of its two nodes in the edge. When assigning a channel a new edge, check the assigned edges in the nearby O1 grids. Thus, each edge only costs an O1 time.
Ifdu,v is defined to be the hop distance, then τG is at most 49, which is shown in [18]. If du,v is the Euclidean distance, we show that τG is at most 11.Theorem 4.
Letdu,v be the hop distance in network graph GV,E. The Algorithm 2 greedy-single-channel (.) gives a 49,49-approximation for the single-channel scheduling problem and runs in O|E|2 time.Proof.
It follows from Theorem2 and the fact τG≤49, which is shown in [18]. A brute force implementation takes O|E|2 time.
For the multi-channel scheduling problem, we show that it does not have two-side approximation unless P=NP.Theorem 5.
Assume thatfn is a function from N to N with fn>0. Then, there is no polynomial time fn-VC-approximation for the multiple channel scheduling problem unless P=NP.Proof.
LetG be the input graph of the multi-channel assignment problem. Assume that there exists a polynomial time fn-VC-approximation algorithm, the multiple channel scheduling problem. Let k be the least number of channels that can support the communications of all edges in G. When the number of total available channels is equal to k, an optimal solution Opt assigns channels to all edges in G. This makes WE−Opt∗=0. When the approximate solution App satisfies WE−App∗≤fnWE−Opt∗=0, it becomes an optimal solution. Thus, we can search the least number of channels from 1 to k to support all edges in G. This brings a polynomial time solution for the conflict-free channel assignment problem, which was proved to be NP-hard [26]. Therefore, P=NP.
We have the following corollary that shows we cannot have a two-side approximation for the multi-channel scheduling problem.Corollary 1.
Assume thatfn is a function from N to N with fn>0. Then, there is no polynomial time fn,fn-approximation for the multiple channel scheduling problem unless P=NP.
In Section2.4, we show a faster approximation for 1−ϵ-IS-approximation than that in [28]. Part of the algorithm is based on the shifting technology which has originated from [31] and has been widely used in developing approximation for networking problem (for example, [18, 28]).
In Section3.1, we present a greedy O1-approximation algorithm for the unweighted multi-channel scheduling problem with variate interference radii.
In Section3.2, we present a greedy O1,O1 approximation algorithm for the unweighted single channel with variate interference radii scheduling problem.
In Section4, we did some simulation for the multi-channel assignment problems for the greedy algorithm. Greedy algorithm is easy to implement and fast to output the result. Its experimental results show much better performance than the theoretical approximation ratio, which is derived under the worst case analysis.


## 2.4. Improving the Existing Algorithm for the Multichannel Scheduling

We show a faster approximation for1−ϵ-IS-approximation than that in [28]. Let PTAS (.) (polynomial-time approximation scheme) represent the algorithm described below. Part of the algorithm is based on the shifting technology which has originated from [31] and has been widely used in developing approximation for networking problem (for example, [18, 28]).Assume that the maximal distance of two nodes for communication is one. Lett be the distance of interference. The grid size is D=t+2. The plane is partitioned into grids of size D×D.Letϵ be a constant in (0, 1). Define m = ⌈1/1−1−ϵ⌉.For two integersa,b∈0,m−1, define Pa,b to be a partition such that the plane is partitioned into the disjoint union of squares of size mD×mD, and the left bottom point of each square of size mD×mD in Pa,b has coordinates imD+a,imD+b for some integers i and j.Lemma 2.
There is amOdm time algorithm to find an optimal solution for the multi-channel scheduling problem in a m×m square with at most d channels in each node.Proof.
We apply a division and conquest method to find an optimal solution. Partition am×m square into four squares by one strip in the vertical middle and one strip in the horizontal middle. The width of the two stripes is equal to the width of the grid t+2. We can only select at most Om edges in the two strips. The number of cases of choices is |E|Om for a single channel. The number of cases of choices is |E|Odm for d channels. The four sub-problems in the four sub-squares can be solved independently.
LetTm be the computational time for solving the channel scheduling problem in a m×m square. We have the recursive equation: Tm=|E|Odm4Tm/2. Select a constant c0 so that Tm=|E|c0m4Tm/2. Expanding the recursion, we have(10)Tm=Ec0dm4Tm2=4OlogmEc0dm2+c0dm22+c0dm23+...=EOdmmO1.Theorem 6.
Assume thatϵ is an arbitrary constant in 0,1. Then, there is an |E|Od/ϵ time algorithm to give a 1−ϵ-IS-approximation for the multi-channel scheduling with d channels.Proof.
A point is in the boundary ofGi,j if it is in a D×D grid in the boundary of a mD×mD big grid of Pi,j. Let Ei,jB,O be the set of all edges that connect the points in the boundary of Gi,j in an optimal solution.
AssumePi,j is the disjoint union of mD×mD grids Q1∪Q2∪,…,Qt. Let OQi be the optimal solution for the set of edges connecting at least one node not in any D×D boundary grid of Qi. Let Ei,jI=OQ1∪OQ2∪,…,∪OQt. We have(11)WEi,jB,O+WEi,jI≥WOpt∗.Each boundary grid is in at most 2m−1Pi,j. We also have ∑i,jWEi,jB,O≤2m−1WOpt∗. Therefore, there are i0 and j0 such that(12)WEi0,j0B,O≤2m−1m2WOpt∗.
By inequalities (11) and (12), we have(13)WEi0,j0I≥WOpt∗−WEi0,j0B,O≥WOpt∗−2m−1m2WOpt∗≥m−12m2WOpt∗≥1−ϵWOpt∗.
The computational time is reduced toEO1Tm, where Tm is the time for finding the optimal solution in a m×m area. By Lemma 2, the algorithm runs in EOd/ϵ time and gives an 1−ϵ-approximation.


## 2.5. Merging Two Algorithms in Single-Channel Scheduling

In this section, we show that merging Algorithm1 and PTAS (.) can speed up the polynomial time approximation scheme in many cases for the single-channel scheduling. We propose Algorithm 3 which shows a polynomial time 1−ϵ,O1-approximation scheme for the single-channel scheduling problem.Algorithm 3: Optimized algorithm in single-channel MG,ϵ.
Require: constantϵ∈0,1 and graph GV,E.Ensure:Appi(1)
LetApp1=App2=∅;(2)
Run greedy-single-channel (.) to find anO1,O1-approximation App1;(3)
Letc=WOpt/WE;(4)
If1−τG1−c≥1−ϵ;(5)
Then, run PTAS (.) to find an1−ϵ-IS-approximation App2;(6)
ReturnAppi with WAppi∗=maxWApp1∗,WApp2∗;Lemma 3.
Assume that a channel scheduling problemG satisfies the condition WOpt≥cWE. Then, a g-VC-approximation for the channel scheduling implies a 1−g1−c-IS-approximation.Proof.
Assume an approximationApp satisfies WE−App∗≤gWE−Opt∗.(14)WApp∗=WE−WE−App∗≥WE−gWE−Opt∗≥WE−g1−cWE≥1−g1−cWE≥1−g1−cWOpt∗.Theorem 7.
Assume thatϵ is an arbitrary constant in 0,1. Then, there is an |E|O1/ϵ time algorithm to give a 1−ϵ,O1-approximation for the single-channel scheduling. Furthermore, Algorithm 3 runs in O|E|2 time if τG1−WOpt∗/WE≤ϵ, where G is the graph of wireless network.Proof.
By Theorem2, we have that App1 is a τG,τG-approximation for the single-channel scheduling problem with WE−App1∗≤τGWE−Opt∗ and WApp1∗≤τGWOpt∗. By Lemma 3, if g1−WOpt∗/WE≤ϵ, then App1 is a 1−ϵ-IS-approximation, where g=τG.
SinceApp2 is a 1−ϵ-IS-approximation for the channel scheduling problem and App2 is also an approximation for the channeling problem, we have WAppi∗ with WAppi∗=maxWApp1∗,WApp2∗ being at most WOpt∗ and at least WOpt∗/1−ϵ. Therefore, Appi is a 1−ϵ-IS-approximation for the channel scheduling problem.
SinceWE−Appi∗≤WE−App1∗≤O1WE−Opt∗, we have that Appi is a 1−ϵ,O1-approximation for the channel scheduling problem.


## 3. Unweighted Channel Assignment

In this section, we develop the approximations for the unweighted channel assignment problem. This is the case that all the edges have weight 1. The radii of interference are not fixed.In the unweighted model, each nodeu has a radius ru for the range that u has the interference. Any node v with distance at most ru to u is interfered by u when u is active. To an edge e=u,v in an active communication, we assume distu,v≤minru,rv.For edgese=u1,u2 and e′=v1,vi, there is an interference between them if distui,vj≤maxrui,rvj for some ui and vj in the nodes of the two edges.Definition 4.
Assume thatG is a channel scheduling problem. We define some measures for approximations.An optimal solution forG is a set Opt∗ of edges without interference with largest Opt∗.Af-IS-approximation App for the channel scheduling problem satisfies the condition App∗≥Opt∗/f.Ag-VC-approximation App for the channel scheduling problem satisfies the condition E−App∗≤gE−Opt∗.Af,g-approximation for the channel scheduling problem satisfies the conditions App∗≥Opt∗/f and E−App∗≤gE−Opt∗.
By Definition3, a f,g-approximation for the channel scheduling problem is both f-IS-approximation and g-VC-approximation for it. Many existing papers used the f-IS-approximation to measure the accuracy.Definition 5.
Assume thatA is a set of channel assignments for G.For each edgee=u,v, define Re=maxru,rv, where ru is the distance of interference from u.LetdA∗e=maxK|e′=s,t:e′,K∈A; there is an interference between e and e′|.DefinedA∗G=maxe∈GdA∗e.Lemma 4.
Assume that all nodes in the demand graphG=V,E are points on a plane. Then, dA∗G≤98 for the Euclidean distance for the interference.Proof.
Lete=u,v be an edge in the graph G. We only consider a fixed channel K. Let Cp,r represent a circle with center at p and radius r. Define Iu to be the set of edges e′=u′,v′∈A assigned with channel K such that u has interference with u′ or v′ (in other words, distu,u′≤minru,ru′ or distu,v′≤minru,rv′. Define J≤u=x: x is a node in e′∈Iu with ru≤rx. Define J>u=x: x is a node in e′∈Iu with ru>rx.
Assume thatdA∗G is large. Consider the case that node u has interference with other edges. For the case of v, we have similar conclusions.Case 1.
J≤u>24. Let h=12. Using u as the center, evenly partition the plane into the h fan areas with angle 2π/h each. By the pigeon hole principle, there is a fan area Fi that has at least dA∗G/4h≥2. In this case, the node xL with the largest radius interferes all other nodes of Fi. This is a contradiction since all nodes Fi are from the solution A and have no interference each other. J≤u≤24.Case 2.
J>u>25. We have more than 25 nodes y within the distance at most 2ru to u, and ry≥ru. The number of circles of radius at least ru/2 without overlap inside a big circle (with center at u) of radius 2ru+ru/2 is at most π×2.52/π×0.52≤25. This gives a contradiction. Thus, we have J>u≤25.
Similarly, we also haveJ≤v≤24 and J>v≤25. Therefore, dA∗≤J≤u+J>u+J≤v+J>v≤24+25+24+25=98.


### 3.1. Multiple Channels with Variate Interference Radii

In this section, we present a greedyO1-approximation algorithm for the unweighted multi-channel scheduling problem with variate interference radii, which is shown in Algorithm 4.Algorithm 4: Greedy-multi-channel with variate interference radii (G,t).
Require: a weighted graphG, and a distance parameter t for the largest distance of interference.Ensure:L′(1) Sort all edges by the increasing order of their sum of radii and put those edges in a listL.(2) LetL′=∅;(3)
Repeat;(4) Select an edgee=u,v with the least Re from L;(5) If there is a channelK for e not being interfered by L′(6) Then, assign the channelK to e and put e,K into L′;(7) Removee from L;(8) UntilL is empty;(9) ReturnL′;We note that when there is a setF of edges that have been assigned channels, it is straightforward to check if a new edge e will be interfered at certain channel K. This can be done by checking EDe,ei≤t for all ei∈FK, where FK is the subset of edges in F in channel K.Theorem 8.
The Algorithm4 greedy (.) is a gα-IS-approximation algorithm for the multi-radio multi-channel scheduling problem and has the computational complexity OE2, where gα=1+dA∗G/α+2α/1−α and α=dA∗G/2+dA∗G.Proof.
Assume thatOpt is an optimal solution for the channel scheduling problem. Let App be an approximate solution derived by greedy (.).
For each edgeg in Opt∗, assign an edge e, denoted by Hg, in App∗ such that Re is the least among all edges with interference with g.Claim 3.
For each edgeg in Opt, Rg≥RHg.Proof.
Ifg is in App∗, we consider an edge has interference with itself. Thus, it is trivial. By the definition of Hg, RHg is the least among all edges in Opt∗ with interference with g.
Assume thatg′ is the first edge in App∗ and has the same channel with g∈Opt∗ and has interference with g. Before selecting g′ for assigning a channel, there is no interference between g and other edges in App. Therefore, Rg′≤Rg (otherwise, g′ should not be selected for channel assignment). Since Hg has the least RHg among all edges with interference with g in App, we have RHg≤Rg′≤Rg.
Letd be the total number of channels. For each edge e=u,v∈Opt∗−App∗, we consider two cases.Case 1.
There are at leastαd channels available for the edge e when e is processed. Each of such an edge is called type A.
In this case, sincee is not assigned for a channel, e must have interference with at least αd edges already assigned channels. For each edge e′ with interference with e, let be,e′=1/αd, and let be,e′=0 otherwise. For each e of type A, we have(15)∑be,e′≥1.
Letb1=dA∗G/α. For each edge in e′∈App∗, let h1e′=∑eis of typeAbe,e′. We have(16)h1e=∑eis of typeAbe,e′≤d.dA∗G⋅1αd=dA∗Gα.Case 2.
There are less thanαd channels available for the edge e when e is processed. Each of such an edge is called type B.
For at least one ofu and v, say u, there are at least 1−αd/2 channels that are already assigned. For each edge e′ with an end point in u already assigned channels, let be,e′=1/1−αd/2=2/1−αd. For each edge in e∈App∗, let h2e′=∑eis of typeBbe,e′. For each e of type B, we have(17)∑be,e′≥1.
Letb2=2α/1−α.(18)h2e′=∑eis of typeBbe,e′≤αd⋅21−αd=21−α=b2.
We have(19)e:e∈Opt∗−App∗≤∑e1∈Opt∗−App∗,e2∈App∗be1,e2≤b1+b2App∗.
Thus, we have(20)Opt∗=Opt∗∩App∗+Opt∗−App∗≤App∗+Opt∗−App∗≤App∗+b1+b2App∗≤1+b1+b2App∗≤1+dA∗Gα+2α1−αApp∗.
We select the constantα so that 1+dA∗G/α+2α/1−α to be minimal. Let gα=1+dA∗G/α+2α/1−α=−1+dA∗G/α+2/1−α. Let gα′=2/1−α2−dA∗G/α2=0. We have α=dA∗G/2+dA∗G. Thus, the ratio of approximation is gα.


### 3.2. Single Channel with Variate Interference Radii

In this section, we present a greedyO1,O1 approximation algorithm for the unweighted single channel with variate interference radii scheduling problem; the pseudocode is shown in Algorithm 5 as follows.Algorithm 5: Greedy-signal-channel with variate interference radii (G,t).
Input: a weighted graphG, and a distance parameter t for the largest distance of interference.Output:L′(1) Sort all edges by the increasing order of their sum of radii and put those edges in a listL.(2) LetL′=∅;(3) Repeat;(4) Select an edgee=u,v with the least sum of radii from L;(5) If there is a channelK for e not being interfered by L′(6) Then, assign the channelK to e and put e,K into L′;(7) Removee from L;(8) UntilL is empty;(9) ReturnL′;We note that when there is a setF of edges that have been assigned channels, it is straightforward to check if a new edge e will be interfered at certain channel K. This can be done by checking if e has interference with any ei∈FK, where FK is the subset of edges in F in channel K.Theorem 9.
The Algorithm5 greedy (.) is an dA∗G,dA∗G-approximation algorithm for the multi-radio multi-channel scheduling problem and has the computational complexity OE2.Proof.
Assume thatOpt is an optimal solution for the channel scheduling problem. Let App be an approximate solution derived by greedy (.).
For each edgeg in Opt∗∞, assign a edge e, denoted by Hg, in App∗ such that Re is the least among all edges with interference with g.
Consider an edgee=u,v selected in App∗. Let Ae=e1,…,em be the list of edges with Hei=e.Claim 4.
For each edgeg in Opt, Rg≥RHg.Proof.
Ifg is in App∗, we consider an edge has interference with itself. Thus, it is trivial. By the definition of Hg, RHg is the least among all edges in Opt∗ with interference with g.
Assumeg′ is the first edge in App∗ and has the same channel with g∈Opt∗ and has interference with g. Before selecting g′ for assigning a channel, there is no interference between g and other edges in App. Therefore, Rg′≤Rg (otherwise, g′ should not be selected for channel assignment). Since Hg has the least RHg among all edges with interference with g in App, we have RHg≤Rg′≤Rg.
Assume thatApp contains channel assignments for edges e1,…,em. Partition Opt∗ into Ae1,…,Aem. By Claim 1, we have that(21)dA∗G≥dA∗ei≥Aei.
Therefore, we havedA∗GApp∗≥Opt∗. Thus, App is a dA∗G-IS approximation for G.
On the other hand, for eachei∈E−Opt∗∩App∗, we always have dA∗ei≥Aei (by Claim 1). For each edge e′ in E−App∗∩Opt∗, there is an edge e∈App∗ such that e and e′ have the interference at the same channel (otherwise, e′ would be assigned some channel by Greed (.)). Furthermore, e′∉Opt∗ since it has interference with e. Therefore, there is an edge e∗∈E−Opt∗∩App∗ such that e′∈Ae∗. By inequality (1), we have(22)E−App∗∩Opt∗≤dA∗GE−Opt∗∩App∗.
We have the inequalities(23)WE−App∗=WE−App∗∩E−Opt∗+WE−App∗∩Opt∗≤WE−Opt∗∩E−App∗+τGWE−Opt∗∩App∗by2≤τGWE−Opt∗∩E−App∗+τWE−Opt∗∩App∗=τGWE−Opt∗.
This givesE−App∗≤dA∗GE−Opt∗. Therefore, greedy (.) gives a dA∗G,dA∗G-approximation.


## 3.1. Multiple Channels with Variate Interference Radii

In this section, we present a greedyO1-approximation algorithm for the unweighted multi-channel scheduling problem with variate interference radii, which is shown in Algorithm 4.Algorithm 4: Greedy-multi-channel with variate interference radii (G,t).
Require: a weighted graphG, and a distance parameter t for the largest distance of interference.Ensure:L′(1) Sort all edges by the increasing order of their sum of radii and put those edges in a listL.(2) LetL′=∅;(3)
Repeat;(4) Select an edgee=u,v with the least Re from L;(5) If there is a channelK for e not being interfered by L′(6) Then, assign the channelK to e and put e,K into L′;(7) Removee from L;(8) UntilL is empty;(9) ReturnL′;We note that when there is a setF of edges that have been assigned channels, it is straightforward to check if a new edge e will be interfered at certain channel K. This can be done by checking EDe,ei≤t for all ei∈FK, where FK is the subset of edges in F in channel K.Theorem 8.
The Algorithm4 greedy (.) is a gα-IS-approximation algorithm for the multi-radio multi-channel scheduling problem and has the computational complexity OE2, where gα=1+dA∗G/α+2α/1−α and α=dA∗G/2+dA∗G.Proof.
Assume thatOpt is an optimal solution for the channel scheduling problem. Let App be an approximate solution derived by greedy (.).
For each edgeg in Opt∗, assign an edge e, denoted by Hg, in App∗ such that Re is the least among all edges with interference with g.Claim 3.
For each edgeg in Opt, Rg≥RHg.Proof.
Ifg is in App∗, we consider an edge has interference with itself. Thus, it is trivial. By the definition of Hg, RHg is the least among all edges in Opt∗ with interference with g.
Assume thatg′ is the first edge in App∗ and has the same channel with g∈Opt∗ and has interference with g. Before selecting g′ for assigning a channel, there is no interference between g and other edges in App. Therefore, Rg′≤Rg (otherwise, g′ should not be selected for channel assignment). Since Hg has the least RHg among all edges with interference with g in App, we have RHg≤Rg′≤Rg.
Letd be the total number of channels. For each edge e=u,v∈Opt∗−App∗, we consider two cases.Case 1.
There are at leastαd channels available for the edge e when e is processed. Each of such an edge is called type A.
In this case, sincee is not assigned for a channel, e must have interference with at least αd edges already assigned channels. For each edge e′ with interference with e, let be,e′=1/αd, and let be,e′=0 otherwise. For each e of type A, we have(15)∑be,e′≥1.
Letb1=dA∗G/α. For each edge in e′∈App∗, let h1e′=∑eis of typeAbe,e′. We have(16)h1e=∑eis of typeAbe,e′≤d.dA∗G⋅1αd=dA∗Gα.Case 2.
There are less thanαd channels available for the edge e when e is processed. Each of such an edge is called type B.
For at least one ofu and v, say u, there are at least 1−αd/2 channels that are already assigned. For each edge e′ with an end point in u already assigned channels, let be,e′=1/1−αd/2=2/1−αd. For each edge in e∈App∗, let h2e′=∑eis of typeBbe,e′. For each e of type B, we have(17)∑be,e′≥1.
Letb2=2α/1−α.(18)h2e′=∑eis of typeBbe,e′≤αd⋅21−αd=21−α=b2.
We have(19)e:e∈Opt∗−App∗≤∑e1∈Opt∗−App∗,e2∈App∗be1,e2≤b1+b2App∗.
Thus, we have(20)Opt∗=Opt∗∩App∗+Opt∗−App∗≤App∗+Opt∗−App∗≤App∗+b1+b2App∗≤1+b1+b2App∗≤1+dA∗Gα+2α1−αApp∗.
We select the constantα so that 1+dA∗G/α+2α/1−α to be minimal. Let gα=1+dA∗G/α+2α/1−α=−1+dA∗G/α+2/1−α. Let gα′=2/1−α2−dA∗G/α2=0. We have α=dA∗G/2+dA∗G. Thus, the ratio of approximation is gα.


## 3.2. Single Channel with Variate Interference Radii

In this section, we present a greedyO1,O1 approximation algorithm for the unweighted single channel with variate interference radii scheduling problem; the pseudocode is shown in Algorithm 5 as follows.Algorithm 5: Greedy-signal-channel with variate interference radii (G,t).
Input: a weighted graphG, and a distance parameter t for the largest distance of interference.Output:L′(1) Sort all edges by the increasing order of their sum of radii and put those edges in a listL.(2) LetL′=∅;(3) Repeat;(4) Select an edgee=u,v with the least sum of radii from L;(5) If there is a channelK for e not being interfered by L′(6) Then, assign the channelK to e and put e,K into L′;(7) Removee from L;(8) UntilL is empty;(9) ReturnL′;We note that when there is a setF of edges that have been assigned channels, it is straightforward to check if a new edge e will be interfered at certain channel K. This can be done by checking if e has interference with any ei∈FK, where FK is the subset of edges in F in channel K.Theorem 9.
The Algorithm5 greedy (.) is an dA∗G,dA∗G-approximation algorithm for the multi-radio multi-channel scheduling problem and has the computational complexity OE2.Proof.
Assume thatOpt is an optimal solution for the channel scheduling problem. Let App be an approximate solution derived by greedy (.).
For each edgeg in Opt∗∞, assign a edge e, denoted by Hg, in App∗ such that Re is the least among all edges with interference with g.
Consider an edgee=u,v selected in App∗. Let Ae=e1,…,em be the list of edges with Hei=e.Claim 4.
For each edgeg in Opt, Rg≥RHg.Proof.
Ifg is in App∗, we consider an edge has interference with itself. Thus, it is trivial. By the definition of Hg, RHg is the least among all edges in Opt∗ with interference with g.
Assumeg′ is the first edge in App∗ and has the same channel with g∈Opt∗ and has interference with g. Before selecting g′ for assigning a channel, there is no interference between g and other edges in App. Therefore, Rg′≤Rg (otherwise, g′ should not be selected for channel assignment). Since Hg has the least RHg among all edges with interference with g in App, we have RHg≤Rg′≤Rg.
Assume thatApp contains channel assignments for edges e1,…,em. Partition Opt∗ into Ae1,…,Aem. By Claim 1, we have that(21)dA∗G≥dA∗ei≥Aei.
Therefore, we havedA∗GApp∗≥Opt∗. Thus, App is a dA∗G-IS approximation for G.
On the other hand, for eachei∈E−Opt∗∩App∗, we always have dA∗ei≥Aei (by Claim 1). For each edge e′ in E−App∗∩Opt∗, there is an edge e∈App∗ such that e and e′ have the interference at the same channel (otherwise, e′ would be assigned some channel by Greed (.)). Furthermore, e′∉Opt∗ since it has interference with e. Therefore, there is an edge e∗∈E−Opt∗∩App∗ such that e′∈Ae∗. By inequality (1), we have(22)E−App∗∩Opt∗≤dA∗GE−Opt∗∩App∗.
We have the inequalities(23)WE−App∗=WE−App∗∩E−Opt∗+WE−App∗∩Opt∗≤WE−Opt∗∩E−App∗+τGWE−Opt∗∩App∗by2≤τGWE−Opt∗∩E−App∗+τWE−Opt∗∩App∗=τGWE−Opt∗.
This givesE−App∗≤dA∗GE−Opt∗. Therefore, greedy (.) gives a dA∗G,dA∗G-approximation.


## 4. Experimental Results

Greedy algorithm is easy to implement and fast to output the result. We did some simulation for the multi-channel assignment problems for the greedy algorithm. The parameterT represents a distance, which is either Euclidean distance or hop distance. In a tuple a,b, the first item a is the total weight of an optimal solution (WOpt∗), and the second item b is the total weight of the approximation solution (WApp∗).We also evaluate the effectiveness of the proposed greedy algorithm; the algorithm performance is compared with the baseline random assignment algorithm, the greedy coloring algorithm which is proposed in [32], and the conventional graph coloring algorithm (GC) in [33]. These three methods are briefly described as follows:Random: we allocate channels randomly for each node.Greedy coloring: we allocate the best channel to each node greedily and then transfer it to robust graph coloring problem which aims at minimizing the interference of system.GC: we use an interference negligible distance to find which pairs of users can share channels with the cellular users.


### 4.1. Multichannel with Hop Distance

Our experimental results for the hop distance show that the results from simulation are much better than the theoretical analysis for the greedy algorithm. In this experiment, we randomly generate a network with 30 nodes and 50 edges. For each edge, we generate a random number as a weight. Replacing with the optimal solution of total weight, we get the following simulation.T=1:560,438,575,428,606,486,598,460,576,457,590,437,545,431,501,394,589,424,556,411.T=2:570,443,586,421,607,456,605,446,582,453,558,413,579,443,607,464,666,546,538,426.T=3:525,407,580,441,569,423,566,434,558,409,537,370,486,389,658,485,486,389,485,347.The performance of the algorithm is shown in Figure1. We note that the performance of the greedy algorithm goes down as the threshold of the distance parameter T goes up. We can also observe that the performance of our greedy algorithm is superior to the greedy coloring, GC, and random algorithms.Figure 1
Multi-channel with hop distance.


### 4.2. Multichannel with Euclidean Distance

Our experimental results for the Euclidean distance show that the results from simulation are much better than the theoretical analysis for the greedy algorithm. In this experiment, we randomly generate a network with 30 nodes and 50 edges in the space of500×500. For each edge, we generate a random number as a weight. Replaced with the optimal solution of total weight, the following simulation has been achieved.T=10:411,300,467,372,443,336,463,379,475,377,407,317,471,385,416,339,494,330,456,354.T=30:421,321,445,349,466,356,436,333,436,325,425,302,418,341,418,355,486,375,454,359.T=50:467,352,499,315,459,301,488,309,502,399,484,313,403,314,481,348,466,325,390,282.T=70:426,260,476,253,415,232,432,259,459,302,449,284,454,241,488,296,507,319,445,210..T=100:444,190,459,197,531,195,435,173,478,228,441,216,442,208,488,257,458,265,490,198.The performance of the algorithm is shown in Figure2. From Figure 2, we can also know that the performance of the greedy algorithm degrades as the threshold of the distance parameter T increases from 10 to 100. The performance of the proposed greedy algorithm is better than the other three comparison algorithms.Figure 2
Multichannel with Euclidean distance.


## 4.1. Multichannel with Hop Distance

Our experimental results for the hop distance show that the results from simulation are much better than the theoretical analysis for the greedy algorithm. In this experiment, we randomly generate a network with 30 nodes and 50 edges. For each edge, we generate a random number as a weight. Replacing with the optimal solution of total weight, we get the following simulation.T=1:560,438,575,428,606,486,598,460,576,457,590,437,545,431,501,394,589,424,556,411.T=2:570,443,586,421,607,456,605,446,582,453,558,413,579,443,607,464,666,546,538,426.T=3:525,407,580,441,569,423,566,434,558,409,537,370,486,389,658,485,486,389,485,347.The performance of the algorithm is shown in Figure1. We note that the performance of the greedy algorithm goes down as the threshold of the distance parameter T goes up. We can also observe that the performance of our greedy algorithm is superior to the greedy coloring, GC, and random algorithms.Figure 1
Multi-channel with hop distance.


## 4.2. Multichannel with Euclidean Distance

Our experimental results for the Euclidean distance show that the results from simulation are much better than the theoretical analysis for the greedy algorithm. In this experiment, we randomly generate a network with 30 nodes and 50 edges in the space of500×500. For each edge, we generate a random number as a weight. Replaced with the optimal solution of total weight, the following simulation has been achieved.T=10:411,300,467,372,443,336,463,379,475,377,407,317,471,385,416,339,494,330,456,354.T=30:421,321,445,349,466,356,436,333,436,325,425,302,418,341,418,355,486,375,454,359.T=50:467,352,499,315,459,301,488,309,502,399,484,313,403,314,481,348,466,325,390,282.T=70:426,260,476,253,415,232,432,259,459,302,449,284,454,241,488,296,507,319,445,210..T=100:444,190,459,197,531,195,435,173,478,228,441,216,442,208,488,257,458,265,490,198.The performance of the algorithm is shown in Figure2. From Figure 2, we can also know that the performance of the greedy algorithm degrades as the threshold of the distance parameter T increases from 10 to 100. The performance of the proposed greedy algorithm is better than the other three comparison algorithms.Figure 2
Multichannel with Euclidean distance.


## 5. Conclusion

We develop a new measure, which controls the ratios in two sides, for the approximation algorithms for channel scheduling problem. We first study the weighted multichannel and single-channel assignment with fixed interference range problems and propose corresponding algorithms for these two problems; furthermore, we improve the existing algorithms for the multi-channel scheduling and propose a faster and more accurate1−ϵ,O1-approximation algorithm for signal channel scheduling problem. Next, we study the unweighted channel assignment with variate interference radius problem and present a multi-channel and a single-channel allocation algorithm, respectively, for this situation. All of the algorithms are given detail theoretical proofs and got constant approximation guarantees. Finally, we verified our algorithms with simulations.



---

*Source: 8836517-2020-11-16.xml*