# Hypergraph Modeling and Approximation Algorithms for the Minimum Length Link Scheduling in Multiuser MIMO Networks

Authors: Hu Shen; Shaohe Lv; Xuan Dong; Junquan Deng; Xiaodong Wang; Xingming Zhou
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

This paper investigates the problem of the minimum length link scheduling (MLLS) in multiuser MIMO (MU-MIMO) networks. Generally, in the networks with MU-MIMO capability, the number of concurrent transmissions can be as large as that of antenna elements at the receiver. As a result, link interference is no longer binary but demonstrates a strong correlation among multiple links, which cannot be captured by the conventional conflict graph interference model. Hence, we propose a novel hypergraph interference model, which can accurately and efficiently characterize the relationship of multiple interferences induced by concurrent transmissions, and provide a tractable formalization of the minimum length link scheduling in MU-MIMO networks (MU-MIMO MLLS). Afterwards, we prove that the MU-MIMO MLLS problem is NP-hard and introduce two approximation algorithms to find the near-optimal feasible schedule. Finally, extensive simulation experiments are presented.


---

## Body

## 1. Introduction

Link scheduling in wireless networks is one of the key and classical research topics for the communication and network communities. In wireless networks, nodes communicate with each other through a shared common channel. On one hand, to shorten the communication latency, node pairs are required to communicate concurrently as much as possible; on the other hand, concurrent transmissions induce the cochannel interference, which results in severe deterioration or even interruption of an ongoing transmission. To control the cochannel interference, link scheduling is required to coordinate the transmission of different links. A good schedule not only avoids communication failures by silencing the interferers of every receive node in each time slot but also minimizes the number of time slots and hence the communication latency. To sum up, link scheduling in wireless networks usually requires the minimum length conflict-free assignment of time slots in which each communication link is activated at least once [1, 2] and the link scheduling problem is difficult because many subsets of nonconflicting nodes are candidates for each time slot, and the subset selected for transmission in one slot affects the number of concurrent transmissions in the next time slot.The interference model, which characterizes the interference relationship of communication links, has a major impact on the complexity of wireless link scheduling. The conflictgraph based interference model, as a simple and powerful modeling tool, has been widely employed [3, 4]. In [3], Hajek and Sasaki consider the MLLS problem and propose an optimal scheduling scheme with polynomial time complexity. However, they consider only the primary interference; that is, two links are interfered with each other when they are neighboring. In practice, the transmission of a link can interrupt that of the other even when they are not neighboring. At this time, link scheduling is shown as an NP-hard problem. Just recently, constant factor approximation bounds have emerged for link scheduling under the conflictgraph interference model with k-hop interference [4].The conventional conflict graph interference model cannot capture the interference when multiple-input multiple-output (MIMO) is deployed. As a revolutionary technology from an information theoretic perspective and physical layer communications, MIMO has been introduced as a de facto component of wireless standards [5, 6]. In the networks with multiuser MIMO capability (MU-MIMO networks), a node with multiple antenna elements can decode a composite signal from different transmitters. Therefore, more communication links are permitted to transmit concurrently. In general, the number of concurrent transmissions can be as large as that of antenna elements at the receiver. For example, given a network consisting of a receiver R1 with two antenna elements, and three senders S1,  S2, and S3 with single antenna, respectively, consider the interference of S1 on  S2: when S3 is silent, there is no interference; however, when S3 is active, S1 and S2 cannot transmit simultaneously. That is, the interference relationship between S1 and S2 has strong correlation with the activity of  S3. Such dependence has not been characterized in the binary conflict graph model.Recently there is a few existing works in the literature trying to explore the optimal link scheduling problem in MU-MIMO networks. Chu and Wang [7] presented an integer linear programming (ILP) formulation of the optimal link scheduling problem in MU-MIMO networks, and proposed an opportunistic scheduling algorithm that can adaptively select different transmission strategies. Blough et al. [8] considered the same problem in MU-MIMO networks with interference suppression capabilities, and formulized the one-shot optimal link scheduling problem as an integer linear programming. However, all of them cannot be applied directly to the MLLS with MU-MIMO capability: on one hand, the goal of [7, 8] is maximizing throughput while the objective of MU-MIMO MLLS is minimizing the schedule length; on the other hand, both work in [7, 8] model the optimal link scheduling problem in MU-MIMO networks as an ILP formulation, which is well-defined in mathematics while difficult to find approximation algorithms providing a guaranteed performance.In this paper, we address the issue of the minimum length link scheduling in MU-MIMO networks, aiming for providing at least one transmission time slot for every communication link with a minimum schedule length. Firstly, we propose a novel interference model based on hypergraph to characterize multiple interferences in MU-MIMO networks. The concept of hypergraph is extended from graph, and is a nature way for representing multiple interferences among multiple links. Afterwards, two algorithms for the problem of MU-MIMO MLLS are proposed: the first one is a performance guaranteed approximation algorithm whose approximation ratio is at most2n/log2(n); the second one is a time efficient heuristic algorithm based on degrees of interference (DOI) greedy. Extensive simulations are presented to test how well the proposed algorithms based hypergraph model may be applied in practice.The remainder of this paper is organized as follows. Section2 presents the integer programming formalization and the proposed hypergraph interference model of MU-MIMO MLLS. Section 3 introduces two algorithms to approximate the optimal solution. Section 4 shows the extensive simulation results. Finally, in Section 5, conclusions are given.


## 2. System Model

### 2.1. Problem Statement

Consider a wireless networkG of n communication links, and N stationary nodes, each of which is equipped with M antenna elements. A link with transmit node i and receive node j is denoted by  lij. We assume that: (i) nodes work in the half-duplex mode, that is a node can either transmit or receive, but not at the same time; (ii) every link is of a single data stream as to enhance as many concurrent transmissions as possible.The use of a MIMO antenna array is typically modeled as degree of freedom (DOF) model [9]. For simplicity, a receive node with M antenna elements has up to M DOFs, which can be used for multiplexing A desired data streams and suppressing (M-A) interferences from other neighboring concurrent transmission links. And if and only if the number of the concurrent transmission link in vicinity of receive node j, including link lij, does not exceed M, then receive node j can successfully decode the data stream carried by link lij.


### 2.2. Integer Programming Formulization

We formulize the problem of MU-MIMO MLLS as an integer programming (IP) by referencing [7, 8].Firstly, notations used in the IP formulation are specified as follows:T={t1,t2,…,tm}: set of transmission time slots for link scheduling;L={l1,l2,…,ln}: set of communication links to be scheduled;V={v1,v2,…,vN}: set of wireless nodes;L(v): set of links incident into node v;ti,ri: transmit node and receive node of link li, respectively;IL(i): set of links interfered by ti;xit: an integer variable, equals to 1 iff link li is active at the tth time slot, otherwise equals 0.The proposed IP formulation for MU-MIMO MLLS is as follows(1)minimizem(2)subjectto:∑t=1mxit≥1i=1,…,n(3)∑j∈L(ri)xjt≤M+Mi·(1-xit)i=1,…,n;t=1,…,m(4)xit∈{0,1}i=1,…,n;t=1,…,m.The objective function (1) states that we aim to minimize the length of scheduling time slots. Constrain (2) ensures that each of communication links is assigned at least one transmission time slot in a schedule period. The next constraint (3) provides that every active communication link does not suffer too much cochannel interference. And to make constrain (3) always feasible when xit=0, the constant parameter Mi needs to be set large enough. A sufficiently large value is Mi=n-M. From constraint (4), we know that the size of search space is 2O(n), rising at an exponential rate with the network size n.The disadvantage of the IP formulation is that it is difficult to find approximation algorithms, but the IP formulation provides a way to calculate the optimal solution through exhaustive searching in cases of networks with a small size.


### 2.3. Hypergraph Modeling MU-MIMO MLLS

Typically, a wireless network can be modeled as adirectional graph  G=(V,E). The set V includes all the nodes in the network, and E is a link set, of which for a pair of nodes u,v∈V, a directional edge e=(u,v) is a member of E if node u’s signals can be decoded successfully at node v in the absence of interference. Further, the interference relationship between transmission links is modeled as a conflict graph  Gc=(Vc,Ec), where Vc is the set of links (in fact, Vc is the set E in the graph G) and Ec is the set of conflicts; that is, (i,j)∈Ec means that the concurrent transmission of link  li and lj is invalid. However, the conflictgraph interference model is restrictive and cannot descript the interference relationship among three links or more. For example, even when (i,j)∉Ec, (i,k)∉Ec, and (j,k)∉Ec are given, we cannot conclude whether the concurrent transmission of link  li, lj, and  lk is valid or not. While generally the interference relationship in MU-MIMO networks involves multiple communication links. Thus, the conflict graph interference model is not appropriate to handle the case of MU-MIMO networks.


#### 2.3.1. Hypergraph Model

Construct. Here, we present a new graph model, hypergraph [10, 11], to characterize the interference relationship in MU-MIMO networks. Let  GH=(VH,EH) denote a hypergraph, where VH is the set of links, the same as  Vc and E, and EH={S1,S2,…,Sq} is also the set of conflicts, similar to Ec. The difference between EH and Ec is that the element of  Ec is limited to 2-tuple of E, while the element of  EH, named as hyperedge, is extended to a subset of E. And for any link set S⊆VH, S∈EH if and only if satisfies three rules as follows.R1: (Invalidity Rule). When all the links of  S are assigned in a same transmission time slot, there is at least one link in  S failing to transmit data successfully.R2: (Minimality Rule). If any link in  S is removed, no failure will occur if only the remaining links in  S are scheduled.R3: (Integrality Rule). All link set S, satisfying conditions R1 and R2, must be contained in  EH.


#### 2.3.2. Hypergraph Model

Problem Formalization. Given a hypergraph model GH=(VH,EH), the problem of MU-MIMO MLLS can be transformed to the problem of finding the optimal coloring of the hypergraph GH: give all node in VH a color, and for every hyperedge S∈EH, having at least two nodes as endpoints, the nodes of this hyperedge that connect  S are not all of the same color. Denote the hypergraph coloring solution by C={C1,C2,…,Cm}, where Ci is the link set with the same color  i. Then, the coloring solution with the least number of colors is the optimal solution to the problem of MU-MIMO MLLS. And the problem of MU-MIMO MLLS could be formulized as follows:
(5)minimizem,whereC=C1∪C2∪⋯∪Cmsubject  to:colors(S)≥2∀S∈EH,
where colors(S) means the number of colors appeared in the hyperedge S.Example 1.
Consider the network in Figure1, where there are four communication links and seven nodes, all of which are equipped with two antenna elements. According to the proposed hypergraph model, we can model the network as hypergraph GH=(VH,EH) showed in Figure 2, in which VH={l13,l24,l50,l60} and EH={{l13,l24,l50},{l24,l50,l60}}. And we can easily find a coloring solution C={{l13,l24}, {l50,l60}}; thus, all the four communication links are assigned in two transmission time slots.Figure 1
A Multi-user MIMO Network.Figure 2
Coloring on Hypergraph.


#### 2.3.3. Hypergraph Model

Analysis.Lemma 2.
Given a MU-MIMO hypergraphGH=(VH,EH), then, for any S∈EH, the cardinality of S is M+1; that is GH is M+1-uniform hypergraph.Proof.
We adopt the counterexample method: (1) if there is any hyperedgeS∈EH, satisfying card(S)≤M (card(S) denotes the cardinality of S), then, according to the receive condition in the DOF model, all links in S could concurrently transmit together; that is, the link set S is a feasible link set, which evidently conflicts with the Invalidity Rule R1; (2) if there is any hyperedge S∈EH, satisfying card(S)≥M+2, then after removing one link l in S, card(S∖{l}) equals M+1 and S∖{l} is still an infeasible link set, which directly conflicts with the Minimality Rule R2. Considering (1) and (2) together, we can conclude that, for any S∈EH, card(S)=M+1.Lemma 3.
The MU-MIMO MLLS problem is NP-hard.Proof.
We reduce the problem of finding the chromatic number of aM+1-uniform hypergraph to the MU-MIMO MLLS problem. The chromatic number of a hypergraph GH is the smallest number k such that GH is k-colorable and GH is k-colorable if its vertices can be colored using k different colors in such a way that for every hyperedge in GH, the nodes of this hyperedge are not all of the same color. According to the hypergraph modeling above mentioned and Lemma 2, we know that every link scheduling solution corresponds to a coloring solution of hypergraph GH. Meanwhile, due to the three construction rules, every hypergraph coloring is also a link scheduling solution. Thus, the minimum scheduling length is equal to the chromatic number of the M+1-uniform hypergraph GH. And several results [12, 13] show that it is NP-complete to optimally color r-uniform hypergraphs, for various values of r (r≥3). Specific statements can be found in the corresponding papers.


## 2.1. Problem Statement

Consider a wireless networkG of n communication links, and N stationary nodes, each of which is equipped with M antenna elements. A link with transmit node i and receive node j is denoted by  lij. We assume that: (i) nodes work in the half-duplex mode, that is a node can either transmit or receive, but not at the same time; (ii) every link is of a single data stream as to enhance as many concurrent transmissions as possible.The use of a MIMO antenna array is typically modeled as degree of freedom (DOF) model [9]. For simplicity, a receive node with M antenna elements has up to M DOFs, which can be used for multiplexing A desired data streams and suppressing (M-A) interferences from other neighboring concurrent transmission links. And if and only if the number of the concurrent transmission link in vicinity of receive node j, including link lij, does not exceed M, then receive node j can successfully decode the data stream carried by link lij.


## 2.2. Integer Programming Formulization

We formulize the problem of MU-MIMO MLLS as an integer programming (IP) by referencing [7, 8].Firstly, notations used in the IP formulation are specified as follows:T={t1,t2,…,tm}: set of transmission time slots for link scheduling;L={l1,l2,…,ln}: set of communication links to be scheduled;V={v1,v2,…,vN}: set of wireless nodes;L(v): set of links incident into node v;ti,ri: transmit node and receive node of link li, respectively;IL(i): set of links interfered by ti;xit: an integer variable, equals to 1 iff link li is active at the tth time slot, otherwise equals 0.The proposed IP formulation for MU-MIMO MLLS is as follows(1)minimizem(2)subjectto:∑t=1mxit≥1i=1,…,n(3)∑j∈L(ri)xjt≤M+Mi·(1-xit)i=1,…,n;t=1,…,m(4)xit∈{0,1}i=1,…,n;t=1,…,m.The objective function (1) states that we aim to minimize the length of scheduling time slots. Constrain (2) ensures that each of communication links is assigned at least one transmission time slot in a schedule period. The next constraint (3) provides that every active communication link does not suffer too much cochannel interference. And to make constrain (3) always feasible when xit=0, the constant parameter Mi needs to be set large enough. A sufficiently large value is Mi=n-M. From constraint (4), we know that the size of search space is 2O(n), rising at an exponential rate with the network size n.The disadvantage of the IP formulation is that it is difficult to find approximation algorithms, but the IP formulation provides a way to calculate the optimal solution through exhaustive searching in cases of networks with a small size.


## 2.3. Hypergraph Modeling MU-MIMO MLLS

Typically, a wireless network can be modeled as adirectional graph  G=(V,E). The set V includes all the nodes in the network, and E is a link set, of which for a pair of nodes u,v∈V, a directional edge e=(u,v) is a member of E if node u’s signals can be decoded successfully at node v in the absence of interference. Further, the interference relationship between transmission links is modeled as a conflict graph  Gc=(Vc,Ec), where Vc is the set of links (in fact, Vc is the set E in the graph G) and Ec is the set of conflicts; that is, (i,j)∈Ec means that the concurrent transmission of link  li and lj is invalid. However, the conflictgraph interference model is restrictive and cannot descript the interference relationship among three links or more. For example, even when (i,j)∉Ec, (i,k)∉Ec, and (j,k)∉Ec are given, we cannot conclude whether the concurrent transmission of link  li, lj, and  lk is valid or not. While generally the interference relationship in MU-MIMO networks involves multiple communication links. Thus, the conflict graph interference model is not appropriate to handle the case of MU-MIMO networks.


### 2.3.1. Hypergraph Model

Construct. Here, we present a new graph model, hypergraph [10, 11], to characterize the interference relationship in MU-MIMO networks. Let  GH=(VH,EH) denote a hypergraph, where VH is the set of links, the same as  Vc and E, and EH={S1,S2,…,Sq} is also the set of conflicts, similar to Ec. The difference between EH and Ec is that the element of  Ec is limited to 2-tuple of E, while the element of  EH, named as hyperedge, is extended to a subset of E. And for any link set S⊆VH, S∈EH if and only if satisfies three rules as follows.R1: (Invalidity Rule). When all the links of  S are assigned in a same transmission time slot, there is at least one link in  S failing to transmit data successfully.R2: (Minimality Rule). If any link in  S is removed, no failure will occur if only the remaining links in  S are scheduled.R3: (Integrality Rule). All link set S, satisfying conditions R1 and R2, must be contained in  EH.


### 2.3.2. Hypergraph Model

Problem Formalization. Given a hypergraph model GH=(VH,EH), the problem of MU-MIMO MLLS can be transformed to the problem of finding the optimal coloring of the hypergraph GH: give all node in VH a color, and for every hyperedge S∈EH, having at least two nodes as endpoints, the nodes of this hyperedge that connect  S are not all of the same color. Denote the hypergraph coloring solution by C={C1,C2,…,Cm}, where Ci is the link set with the same color  i. Then, the coloring solution with the least number of colors is the optimal solution to the problem of MU-MIMO MLLS. And the problem of MU-MIMO MLLS could be formulized as follows:
(5)minimizem,whereC=C1∪C2∪⋯∪Cmsubject  to:colors(S)≥2∀S∈EH,
where colors(S) means the number of colors appeared in the hyperedge S.Example 1.
Consider the network in Figure1, where there are four communication links and seven nodes, all of which are equipped with two antenna elements. According to the proposed hypergraph model, we can model the network as hypergraph GH=(VH,EH) showed in Figure 2, in which VH={l13,l24,l50,l60} and EH={{l13,l24,l50},{l24,l50,l60}}. And we can easily find a coloring solution C={{l13,l24}, {l50,l60}}; thus, all the four communication links are assigned in two transmission time slots.Figure 1
A Multi-user MIMO Network.Figure 2
Coloring on Hypergraph.


### 2.3.3. Hypergraph Model

Analysis.Lemma 2.
Given a MU-MIMO hypergraphGH=(VH,EH), then, for any S∈EH, the cardinality of S is M+1; that is GH is M+1-uniform hypergraph.Proof.
We adopt the counterexample method: (1) if there is any hyperedgeS∈EH, satisfying card(S)≤M (card(S) denotes the cardinality of S), then, according to the receive condition in the DOF model, all links in S could concurrently transmit together; that is, the link set S is a feasible link set, which evidently conflicts with the Invalidity Rule R1; (2) if there is any hyperedge S∈EH, satisfying card(S)≥M+2, then after removing one link l in S, card(S∖{l}) equals M+1 and S∖{l} is still an infeasible link set, which directly conflicts with the Minimality Rule R2. Considering (1) and (2) together, we can conclude that, for any S∈EH, card(S)=M+1.Lemma 3.
The MU-MIMO MLLS problem is NP-hard.Proof.
We reduce the problem of finding the chromatic number of aM+1-uniform hypergraph to the MU-MIMO MLLS problem. The chromatic number of a hypergraph GH is the smallest number k such that GH is k-colorable and GH is k-colorable if its vertices can be colored using k different colors in such a way that for every hyperedge in GH, the nodes of this hyperedge are not all of the same color. According to the hypergraph modeling above mentioned and Lemma 2, we know that every link scheduling solution corresponds to a coloring solution of hypergraph GH. Meanwhile, due to the three construction rules, every hypergraph coloring is also a link scheduling solution. Thus, the minimum scheduling length is equal to the chromatic number of the M+1-uniform hypergraph GH. And several results [12, 13] show that it is NP-complete to optimally color r-uniform hypergraphs, for various values of r (r≥3). Specific statements can be found in the corresponding papers.


## 2.3.1. Hypergraph Model

Construct. Here, we present a new graph model, hypergraph [10, 11], to characterize the interference relationship in MU-MIMO networks. Let  GH=(VH,EH) denote a hypergraph, where VH is the set of links, the same as  Vc and E, and EH={S1,S2,…,Sq} is also the set of conflicts, similar to Ec. The difference between EH and Ec is that the element of  Ec is limited to 2-tuple of E, while the element of  EH, named as hyperedge, is extended to a subset of E. And for any link set S⊆VH, S∈EH if and only if satisfies three rules as follows.R1: (Invalidity Rule). When all the links of  S are assigned in a same transmission time slot, there is at least one link in  S failing to transmit data successfully.R2: (Minimality Rule). If any link in  S is removed, no failure will occur if only the remaining links in  S are scheduled.R3: (Integrality Rule). All link set S, satisfying conditions R1 and R2, must be contained in  EH.


## 2.3.2. Hypergraph Model

Problem Formalization. Given a hypergraph model GH=(VH,EH), the problem of MU-MIMO MLLS can be transformed to the problem of finding the optimal coloring of the hypergraph GH: give all node in VH a color, and for every hyperedge S∈EH, having at least two nodes as endpoints, the nodes of this hyperedge that connect  S are not all of the same color. Denote the hypergraph coloring solution by C={C1,C2,…,Cm}, where Ci is the link set with the same color  i. Then, the coloring solution with the least number of colors is the optimal solution to the problem of MU-MIMO MLLS. And the problem of MU-MIMO MLLS could be formulized as follows:
(5)minimizem,whereC=C1∪C2∪⋯∪Cmsubject  to:colors(S)≥2∀S∈EH,
where colors(S) means the number of colors appeared in the hyperedge S.Example 1.
Consider the network in Figure1, where there are four communication links and seven nodes, all of which are equipped with two antenna elements. According to the proposed hypergraph model, we can model the network as hypergraph GH=(VH,EH) showed in Figure 2, in which VH={l13,l24,l50,l60} and EH={{l13,l24,l50},{l24,l50,l60}}. And we can easily find a coloring solution C={{l13,l24}, {l50,l60}}; thus, all the four communication links are assigned in two transmission time slots.Figure 1
A Multi-user MIMO Network.Figure 2
Coloring on Hypergraph.


## 2.3.3. Hypergraph Model

Analysis.Lemma 2.
Given a MU-MIMO hypergraphGH=(VH,EH), then, for any S∈EH, the cardinality of S is M+1; that is GH is M+1-uniform hypergraph.Proof.
We adopt the counterexample method: (1) if there is any hyperedgeS∈EH, satisfying card(S)≤M (card(S) denotes the cardinality of S), then, according to the receive condition in the DOF model, all links in S could concurrently transmit together; that is, the link set S is a feasible link set, which evidently conflicts with the Invalidity Rule R1; (2) if there is any hyperedge S∈EH, satisfying card(S)≥M+2, then after removing one link l in S, card(S∖{l}) equals M+1 and S∖{l} is still an infeasible link set, which directly conflicts with the Minimality Rule R2. Considering (1) and (2) together, we can conclude that, for any S∈EH, card(S)=M+1.Lemma 3.
The MU-MIMO MLLS problem is NP-hard.Proof.
We reduce the problem of finding the chromatic number of aM+1-uniform hypergraph to the MU-MIMO MLLS problem. The chromatic number of a hypergraph GH is the smallest number k such that GH is k-colorable and GH is k-colorable if its vertices can be colored using k different colors in such a way that for every hyperedge in GH, the nodes of this hyperedge are not all of the same color. According to the hypergraph modeling above mentioned and Lemma 2, we know that every link scheduling solution corresponds to a coloring solution of hypergraph GH. Meanwhile, due to the three construction rules, every hypergraph coloring is also a link scheduling solution. Thus, the minimum scheduling length is equal to the chromatic number of the M+1-uniform hypergraph GH. And several results [12, 13] show that it is NP-complete to optimally color r-uniform hypergraphs, for various values of r (r≥3). Specific statements can be found in the corresponding papers.


## 3. Algorithms

In this section, two algorithms based on the uniform hypergraph coloring for the problem of MU-MIMO MLLS are proposed. Here, we firstly give some definitions: given ar-uniform hypergraph GH=(VH,EH), a link set U⊆VH is called independent if U does not contain any hyperedge in EH. An m-coloring of GH is a mapping C: VH→{C1,…,Cm} such that no hyperedge of GH with one single color. Equivalently, an m-coloring of GH is a partition of the vertex set VH into m independent sets. The chromatic number of GH, denoted by  χ(GH), is the minimal m, for which GH admits an m-coloring.


### 3.1. Performance-Guaranteed (P-G) Approximation Algorithm

Similar to Wigderson’s paper [14], we find an independent set with the following algorithm, named as performance-guaranteed (P-G) algorithm, whose approximation ratio is 2n/log2(n). It is worth noting that the idea of partitioning the vertex set of a k-colorable hypergraph GH on n into groups of size klogkn and performing an exhaustive search for an independent set of size logkn  in each group is due to Berger and Rompel’s paper [15].Define(6)hk(n)=logkn=lognlogk.Lemma 4.
For ak-colorable hypergraph GH with n vertices, Procedure 1 outputs an independent set of size hk(n), in time polynomial in n (see, Procedure 1).Procedure 1
Procedure
B
(
G
H
,
k
): if GH=(VH,EH) is k-colorable, return a independent link set of
size hk(|VH|); otherwise, an arbitrary subset of size hk(|VH|).
Input: An integer k≥2 and a hypergraph GH=(VH,EH).
Output: A subset U of VH with the size |U|=hk(|VH|).
(1)n=|VH|; h=hk(n);
(2)l=⌊n/hk⌋;
(3)Partition VH into sets V1,…,Vl where |V|=⋯=|Vl-1|=hk and hk≤|Vl|<2hk;
(4)for  i=1  to  l
(5) foreach subset U of Vi of size |U|=h
(6) if  U is independent in GH
(7)return  (U);
(8) endif
(9) endfor
(10)endfor
(11)return an arbitrary subset of VH of size h;Proof.
IfGH is k-colorable, it contains an independent set I of size |I|≥n/k. Then, for some 1≤i≤k, we have |I∩Vi|≥|I|/l≥n/kl≥hk(n). Checking all subsets of Vi of size hk(n) will reveal an independent set of size hk(n). The number of subsets of size  hk(n) to be checked by the algorithm does not exceed l(2hk(n)khk(n))=(O(1)k)hk(n)=nO(1).The idea of our proposed AlgorithmP-G is simple: as long as there are some uncolored vertices (their union is denoted by W), call Procedure 1 for finding an independent set U in the subhypergraph spanned by W, denoted by GHW, give the output U a fresh color, and update W.Lemma 5.
AlgorithmP-G outputs a coloring solution in time polynomial in n (see, Algorithm 1).Algorithm 1
Algorithm
P
-
G
(
G
H
): Providing a coloring solution for hypergraph GH=(VH,EH).
Input: A r-uniform hypergraph GH=(VH,EH).
Output: A coloring solution of GH.
(1)k=2;
(2)i=1; W=VH;
(3)while  W≠∅
(4) U=B(GHW,k);
(5) if  U is not independent
(6)   k=k+1;
(7) else
(8)   Ci=U; % color U by color i %
(9)   i=i+1; k=2;
(10)W=W∖U;
(11)endif
(12)endwhile;
(13)return a coloring C={C1,C2,…,Ci-1};Proof.
Inevitably, any hypergraphGHW=(VHW,EHW) is |VHW|-colorable; thus, Procedure 1 is called at most ∑|VHW|=n1∑k=2|VHW|1=n(n-2)/2=O(n2) times, and according to Lemma 4, the time complexity of Procedure 1 is nO(1); hence, the time complexity of Algorithm P-G is polynomial in n.Lemma 6.
The approximation ratio of AlgorithmP-G is at most 2n/log2(n) (see, Algorithm 1).Proof.
For a hypergraphGH=(VH,EH), we denote the chromatic number of GH by χ; that is, GH is χ-colorable. Furthermore, the optimal coloring of GH is the solution of coloring GH by χ colors. In addition, for any subhypergraph of GH, which is spanned by the subset W and denoted by GHW=(VHW,EHW) as above mentioned, due to VHW⊆VH, it is obvious that GHW is also χ-colorable. Through Procedure 1, the size of the independent set U picked by Algorithm P-G is at least hχ(|GHW|). And we know that hχ(n) is a positive, nondecreasing function. Then, Algorithm P-G produces a coloring with at most fχ(n)=∑i=1n(1/hχ(i)) colors, since each link in VH contributes at most 1/hχ(n′) colors, where n′ is the number of links remaining in the subhypergraph GHW at the time when the link was assigned a color. It is proofed that when hχ(n) grows no faster than n1/t (t>1), fχ(n) is at most t/(t-1)·n/hχ(n) [16]. Specifically in our proposed Algorithm P-G, hχ(n)=logn/logχ grows no faster than n3/4. Thereby, Algorithm P-G colors the χ-colorable hypergraph GH on n vertices in at most 4n·logχ/logn, then the approximation ratio of Algorithm P-G is at most g(χ)=4n·logχ/(χ·logn). Finally, g(χ) (χ≥2) is decreasing function that is max(g(χ))=2n/log2n.


### 3.2. DOI-Based Greedy (D-G) Heuristic Algorithm

Although AlgorithmP-G can provide a guaranteed performance, its time complexity is nO(1). The distinguishing time complexity promotes us to design another time efficient heuristic coloring algorithm.Recall that the goal of link scheduling is to keep the cochannel interference at a proper level. Here, the concept ofdegree of interference, denoted by DOI (l), is defined to measure the interferences induced by a link l and presents the impact of the link l brought to the other links. DOI (l) is equal to the amount of communication links affected by the link l when link l is in activation. The main idea of Algorithm D-G is to assign the link with maximum degrees-of-interference as early as possible; hence, the interferences in the whole network would reduce drastically and then a relative larger independent link set might be picked in next scheduling time slots. To improve the performance, we refresh the DOI information every time after picking an independent link set.Lemma 7.
The time complexity of AlgorithmD-G is O(n2logn) (see, Algorithm 2).Algorithm 2
Algorithm
D
-
G
(
G
H
): Providing a coloring solution for hypergraph GH=(VH,EH)
Input: An r-uniform hypergraph GH=(VH,EH).
Output: A coloring of GH.
(1)i=1; W=VH;
(2)while  W≠∅
(3) QuickSort (GHW);   % sort GHW by the DOI item in a decreasing order %
(4) U=∅
(5) while  (j≤|W|)
(6) if  U∪{W(j)} is an independent set
(7)  U=U∪{W(j)}; % W(j) is the jth element of W %
(8) else
(9)  break;
(10)endif
(11)endwhile
(12)Ci=U; % color U by color i %
(13)i=i+1;
(14)W=W∖U;
(15)endwhile;
(16)return a coloring C={C1,C2,…,Ci-1};Proof.
The bottleneck of AlgorithmD-G is the procedure of QuickSort (GHW), which is called at most n times, and the expected running time of QuickSort (GHW) is O(nlogn).


## 3.1. Performance-Guaranteed (P-G) Approximation Algorithm

Similar to Wigderson’s paper [14], we find an independent set with the following algorithm, named as performance-guaranteed (P-G) algorithm, whose approximation ratio is 2n/log2(n). It is worth noting that the idea of partitioning the vertex set of a k-colorable hypergraph GH on n into groups of size klogkn and performing an exhaustive search for an independent set of size logkn  in each group is due to Berger and Rompel’s paper [15].Define(6)hk(n)=logkn=lognlogk.Lemma 4.
For ak-colorable hypergraph GH with n vertices, Procedure 1 outputs an independent set of size hk(n), in time polynomial in n (see, Procedure 1).Procedure 1
Procedure
B
(
G
H
,
k
): if GH=(VH,EH) is k-colorable, return a independent link set of
size hk(|VH|); otherwise, an arbitrary subset of size hk(|VH|).
Input: An integer k≥2 and a hypergraph GH=(VH,EH).
Output: A subset U of VH with the size |U|=hk(|VH|).
(1)n=|VH|; h=hk(n);
(2)l=⌊n/hk⌋;
(3)Partition VH into sets V1,…,Vl where |V|=⋯=|Vl-1|=hk and hk≤|Vl|<2hk;
(4)for  i=1  to  l
(5) foreach subset U of Vi of size |U|=h
(6) if  U is independent in GH
(7)return  (U);
(8) endif
(9) endfor
(10)endfor
(11)return an arbitrary subset of VH of size h;Proof.
IfGH is k-colorable, it contains an independent set I of size |I|≥n/k. Then, for some 1≤i≤k, we have |I∩Vi|≥|I|/l≥n/kl≥hk(n). Checking all subsets of Vi of size hk(n) will reveal an independent set of size hk(n). The number of subsets of size  hk(n) to be checked by the algorithm does not exceed l(2hk(n)khk(n))=(O(1)k)hk(n)=nO(1).The idea of our proposed AlgorithmP-G is simple: as long as there are some uncolored vertices (their union is denoted by W), call Procedure 1 for finding an independent set U in the subhypergraph spanned by W, denoted by GHW, give the output U a fresh color, and update W.Lemma 5.
AlgorithmP-G outputs a coloring solution in time polynomial in n (see, Algorithm 1).Algorithm 1
Algorithm
P
-
G
(
G
H
): Providing a coloring solution for hypergraph GH=(VH,EH).
Input: A r-uniform hypergraph GH=(VH,EH).
Output: A coloring solution of GH.
(1)k=2;
(2)i=1; W=VH;
(3)while  W≠∅
(4) U=B(GHW,k);
(5) if  U is not independent
(6)   k=k+1;
(7) else
(8)   Ci=U; % color U by color i %
(9)   i=i+1; k=2;
(10)W=W∖U;
(11)endif
(12)endwhile;
(13)return a coloring C={C1,C2,…,Ci-1};Proof.
Inevitably, any hypergraphGHW=(VHW,EHW) is |VHW|-colorable; thus, Procedure 1 is called at most ∑|VHW|=n1∑k=2|VHW|1=n(n-2)/2=O(n2) times, and according to Lemma 4, the time complexity of Procedure 1 is nO(1); hence, the time complexity of Algorithm P-G is polynomial in n.Lemma 6.
The approximation ratio of AlgorithmP-G is at most 2n/log2(n) (see, Algorithm 1).Proof.
For a hypergraphGH=(VH,EH), we denote the chromatic number of GH by χ; that is, GH is χ-colorable. Furthermore, the optimal coloring of GH is the solution of coloring GH by χ colors. In addition, for any subhypergraph of GH, which is spanned by the subset W and denoted by GHW=(VHW,EHW) as above mentioned, due to VHW⊆VH, it is obvious that GHW is also χ-colorable. Through Procedure 1, the size of the independent set U picked by Algorithm P-G is at least hχ(|GHW|). And we know that hχ(n) is a positive, nondecreasing function. Then, Algorithm P-G produces a coloring with at most fχ(n)=∑i=1n(1/hχ(i)) colors, since each link in VH contributes at most 1/hχ(n′) colors, where n′ is the number of links remaining in the subhypergraph GHW at the time when the link was assigned a color. It is proofed that when hχ(n) grows no faster than n1/t (t>1), fχ(n) is at most t/(t-1)·n/hχ(n) [16]. Specifically in our proposed Algorithm P-G, hχ(n)=logn/logχ grows no faster than n3/4. Thereby, Algorithm P-G colors the χ-colorable hypergraph GH on n vertices in at most 4n·logχ/logn, then the approximation ratio of Algorithm P-G is at most g(χ)=4n·logχ/(χ·logn). Finally, g(χ) (χ≥2) is decreasing function that is max(g(χ))=2n/log2n.


## 3.2. DOI-Based Greedy (D-G) Heuristic Algorithm

Although AlgorithmP-G can provide a guaranteed performance, its time complexity is nO(1). The distinguishing time complexity promotes us to design another time efficient heuristic coloring algorithm.Recall that the goal of link scheduling is to keep the cochannel interference at a proper level. Here, the concept ofdegree of interference, denoted by DOI (l), is defined to measure the interferences induced by a link l and presents the impact of the link l brought to the other links. DOI (l) is equal to the amount of communication links affected by the link l when link l is in activation. The main idea of Algorithm D-G is to assign the link with maximum degrees-of-interference as early as possible; hence, the interferences in the whole network would reduce drastically and then a relative larger independent link set might be picked in next scheduling time slots. To improve the performance, we refresh the DOI information every time after picking an independent link set.Lemma 7.
The time complexity of AlgorithmD-G is O(n2logn) (see, Algorithm 2).Algorithm 2
Algorithm
D
-
G
(
G
H
): Providing a coloring solution for hypergraph GH=(VH,EH)
Input: An r-uniform hypergraph GH=(VH,EH).
Output: A coloring of GH.
(1)i=1; W=VH;
(2)while  W≠∅
(3) QuickSort (GHW);   % sort GHW by the DOI item in a decreasing order %
(4) U=∅
(5) while  (j≤|W|)
(6) if  U∪{W(j)} is an independent set
(7)  U=U∪{W(j)}; % W(j) is the jth element of W %
(8) else
(9)  break;
(10)endif
(11)endwhile
(12)Ci=U; % color U by color i %
(13)i=i+1;
(14)W=W∖U;
(15)endwhile;
(16)return a coloring C={C1,C2,…,Ci-1};Proof.
The bottleneck of AlgorithmD-G is the procedure of QuickSort (GHW), which is called at most n times, and the expected running time of QuickSort (GHW) is O(nlogn).


## 4. Simulation and Discussion

We evaluate the performance of our proposed AlgorithmsP-G and D-G via extensive simulations. The network settings include wireless nodes that are distributed in a square area of 1250 m × 1250 m and form an ad hoc network with random or grid topology; each node is equipped with M antennas and has a communication range of 250 m and an interference range of 400 m (Figure 3). A simulation result is obtained by averaging over 50 runs of simulations, and all simulations run on a 2.8 GHz Intel Core Duo machine with 4 GB of RAM.Figure 3
A network with random topology, 60 nodes and 250 communication links.Four algorithms are implemented and compared in our simulations: (1) the algorithm of exhaustive searching (E-A) to compute the optimal solution of MU-MIMO MLLS; (2) the centralized algorithm of opportunistic scheduling (O-S) modified from [7]; (3) the approximation algorithm of performance guaranteed (P-G) illustrated in Section 3.1; and (4) the heuristic algorithm of DOI-based greedy (D-G) in Section 3.2. Algorithm E-A and Algorithm O-S use the IP formulation presented in Section 2.2, while Algorithm P-G and Algorithm D-G are based on the proposed hypergraph model in Section 2.3. And the later three algorithms only produce suboptimal solutions. To be noted here, our simulation experiments were only partially successful. In certain cases, where the networks are of a small size (refer to the number of links), Algorithm E-S converged quickly to the optimal solution. While in other cases, convergence was much slower and in some cases memory usage rose dramatically preventing the optimal solution from being found. In addition, slow convergence also occurred in the cases with a large network size when executing the approximation or heuristic algorithms. Hence, we set the network size to network cases with a small or medium size.Here, two performance metrics are considered for the evaluation of the scheduling algorithms: (a)average scheduling length (ASL) is defined as the average number of time slots required for assigning all the communication links at least once in a schedule period; (b) average running time (ART) is defined as the average time spendt in executing the simulation one time. We investigate three impact factors, namely, network size, network topology, and degree of freedom. For each factor, both the average scheduling length and the average running time are compared. If not otherwise specified, wireless networks are with random topology, and the node’s degree of freedom are 2, that is, each wireless node is equipped with two antenna elements.Next, we discuss the results from our simulation experiments.


### 4.1. Impact of Network Size

In this section, we represent the network size as the number of communication links. The impact of network size is shown in Figures4(a) and 4(b). As above mentioned, the calculation of the exact optimal solution for the large or even medium scale network is infeasible with our machine, while the proposed approximation Algorithm P-G and the heuristic Algorithm D-G can scale to quite large number of communication links and produce suboptimal solutions that are not too bad. Irrespective of the network size, our proposed two algorithms perform better than the reference algorithm (Algorithm O-S) in terms of average scheduling length, and the performance gain is between 7% and 15%. Besides, Algorithm P-G has the closest performance to that of the optimal solution when the network is of medium or large number of communication links (the ASL performance curves of Algorithm P-G and D-G intersect when the number of links is around 50). The main reason for the performance improvement is that in every schedule time slot, the concurrent link set selected by Algorithm P-G is guaranteed to be of a certain size, and the size increases along with the network size. Although Algorithm P-G has ASL performance advantage, the performance difference between Algorithm P-G and Algorithm D-G is less than 10% when the network size is controlled below 115 communication links.Impact of network size.
(a)
Average scheduling length
(b)
Average running timeThe comparison of the ART performance of three algorithms is shown in Figure4(b). To represent the performance difference more effectively, we adopt the denary logarithm value of average running times. The results verify that the running time of Algorithm E-S is rising at an exponential rate with the network size; thus, Algorithm E-S can be only executed in the case of very small networks; Algorithm P-G, Algorithm D-G, and Algorithm O-S are of polynomial time complexity, while Algorithm D-G is of orders-of-magnitudes advantage over Algorithm P-G and Algorithm O-S in terms of ART performance.


### 4.2. Impact of Network Topology

We perform extensive simulations with two types of network topology: a randomly generated topology and a grid. In both two networks, the number of communication links to be scheduled is set to the same value,n=112. And the compared algorithms are Algorithm P-G, Algorithm D-G, and Algorithm O-S. From Figure 5, we see that the efficiency of all the three algorithms is higher with random topology: with random topology, fewer transmission time slots and little running time are required. The reason is that in a grid topology, each wireless node is equidistant from its neighbors; hence, the distribution of communication links is more homogeneous and the signals of neighbors arrive at a receiver node with similar powers; this limits the choices for the scheduling policies, especially for Algorithm D-G. Besides, we find that in both networks, Algorithm D-G is of a huge ART performance benefits, compared with Algorithm P-G and Algorithm O-S.Impact of network topology.
(a)
Average scheduling length
(b)
Average running time


### 4.3. Impact of Degree of Freedom

Finally, we turn to perform simulations in networks with varied degree of freedom. The networks are with a rand generated topology and 112 communication links to be scheduled. As shown in Figure6, the value of degree of freedom impacts the ASL performance significantly while it has relative little impact to the ART performance. That is because as the number of antenna elements (degree of freedom) is increased, the receive node is more effective and, thus, more communication links can be grouped in a same schedule time slot.Impact of degree of freedom.
(a)
Average scheduling length
(b)
Average running time


## 4.1. Impact of Network Size

In this section, we represent the network size as the number of communication links. The impact of network size is shown in Figures4(a) and 4(b). As above mentioned, the calculation of the exact optimal solution for the large or even medium scale network is infeasible with our machine, while the proposed approximation Algorithm P-G and the heuristic Algorithm D-G can scale to quite large number of communication links and produce suboptimal solutions that are not too bad. Irrespective of the network size, our proposed two algorithms perform better than the reference algorithm (Algorithm O-S) in terms of average scheduling length, and the performance gain is between 7% and 15%. Besides, Algorithm P-G has the closest performance to that of the optimal solution when the network is of medium or large number of communication links (the ASL performance curves of Algorithm P-G and D-G intersect when the number of links is around 50). The main reason for the performance improvement is that in every schedule time slot, the concurrent link set selected by Algorithm P-G is guaranteed to be of a certain size, and the size increases along with the network size. Although Algorithm P-G has ASL performance advantage, the performance difference between Algorithm P-G and Algorithm D-G is less than 10% when the network size is controlled below 115 communication links.Impact of network size.
(a)
Average scheduling length
(b)
Average running timeThe comparison of the ART performance of three algorithms is shown in Figure4(b). To represent the performance difference more effectively, we adopt the denary logarithm value of average running times. The results verify that the running time of Algorithm E-S is rising at an exponential rate with the network size; thus, Algorithm E-S can be only executed in the case of very small networks; Algorithm P-G, Algorithm D-G, and Algorithm O-S are of polynomial time complexity, while Algorithm D-G is of orders-of-magnitudes advantage over Algorithm P-G and Algorithm O-S in terms of ART performance.


## 4.2. Impact of Network Topology

We perform extensive simulations with two types of network topology: a randomly generated topology and a grid. In both two networks, the number of communication links to be scheduled is set to the same value,n=112. And the compared algorithms are Algorithm P-G, Algorithm D-G, and Algorithm O-S. From Figure 5, we see that the efficiency of all the three algorithms is higher with random topology: with random topology, fewer transmission time slots and little running time are required. The reason is that in a grid topology, each wireless node is equidistant from its neighbors; hence, the distribution of communication links is more homogeneous and the signals of neighbors arrive at a receiver node with similar powers; this limits the choices for the scheduling policies, especially for Algorithm D-G. Besides, we find that in both networks, Algorithm D-G is of a huge ART performance benefits, compared with Algorithm P-G and Algorithm O-S.Impact of network topology.
(a)
Average scheduling length
(b)
Average running time


## 4.3. Impact of Degree of Freedom

Finally, we turn to perform simulations in networks with varied degree of freedom. The networks are with a rand generated topology and 112 communication links to be scheduled. As shown in Figure6, the value of degree of freedom impacts the ASL performance significantly while it has relative little impact to the ART performance. That is because as the number of antenna elements (degree of freedom) is increased, the receive node is more effective and, thus, more communication links can be grouped in a same schedule time slot.Impact of degree of freedom.
(a)
Average scheduling length
(b)
Average running time


## 5. Conclusions

In this paper, we study the issue of the minimum length link scheduling in a wireless network with the MU-MIMO capability. Firstly, we formulate the MU-MIMO MLLS problem as an integer programming problem. Secondly, we introduce a novel and straight hypergraph method to model the multiple interferences, which cannot be captured by the traditional conflict graph model, and then we reformulate the MU-MIMO MLLS problem based on the new hypergraph model. And, we show that, the scheduling problem is NP-hard. Thirdly, we propose two efficient approximation solutions. For the first algorithm, named as AlgorithmP-G, we show that the approximation ratio is at most 2n/log2(n). To reduce the time complexity, we also present a time efficient heuristic algorithm based on degree of interference greedy (Algorithm D-G). Finally, extensive simulation results show that (1) both Algorithm P-G and Algorithm D-G can scale to quite a large number of links and produce satisfying suboptimal solutions; (2) generally, Algorithm P-G has a better ASL performance than Algorithm D-G, while the time complexity of Algorithm D-G is largely reduced compared with that of Algorithm P-G.



---

*Source: 982713-2013-11-25.xml*