# Distributed Link Scheduling Algorithm Based on Successive Interference Cancellation in MIMO Wireless Networks

Authors: Junhua Wu; Dandan Lin; Guangshun Li; Yuncui Liu; Yanmin Yin
Journal: Wireless Communications and Mobile Computing
 (2019)

---

## Abstract

The performance of multiple input multiple output (MIMO) wireless networks is limited mainly by concurrent interference among sensor nodes. Effective link scheduling algorithms with the technology of successive interference cancellation (SIC) can maximize throughput in MIMO wireless networks. Most previous works on link scheduling in MIMO wireless networks did not consider SIC. In this paper, we propose a MIMO-SIC (MSIC) algorithm under the SINR model. First, a mathematical framework is established for the cross-layer optimization of routing and scheduling, with constraints of traffic balance and link capacity. Second, the interference regions are divided to characterize the level of interference between links. Finally, we propose a distributed link scheduling algorithm based on MSIC to eliminate the interference between competing links in the MIMO network. Experimental results show that the MSIC algorithm can increase the end-to-end throughput per unit by approximately 73% on average compared with non-SIC algorithms.


---

## Body

## 1. Introduction

Due to the explosiveness of big data, many new high-performance requirements of network throughput, real-time performance, security privacy, and bandwidth have been put forward [1–4]. It is consequently challenging to design efficient link scheduling algorithms to improve communication efficiency in wireless communication. Wireless network multiple input multiple output (MIMO) technology can transmit multiple data streams simultaneously without increasing bandwidth and enhance data throughput; MIMO has therefore attracted increasing attention[5, 6].MIMO refers to the technology of using multiple transmitting antennas and multiple receiving antennas in wireless transmission, which is a major technology of smart antennas in wireless communication networks. The main idea of MIMO is to combine the signals of the receiving and sending antennas to increase transmission reliability and data throughput [7, 8]. The architecture of MIMO wireless communication networks is shown in Figure 1.Figure 1
The architecture of a MIMO wireless communication network.However, concurrent links also generate some problems in communication interference, which reduces the success probability of communication links [9]. The reason is that, due to transmission interference of adjacent channels, mixed superimposed signals will reach the receiver node [10, 11]. The cumulative interference effect of the link depends not only on itself but also on concurrent links. When conflict occurs between concurrent links, transmissions fail due to bad interference. In wireless networks, MIMO gain is closely related to link scheduling.The link scheduling problem focuses on the study of capacity optimization and throughput maximization [12] and can be divided into the following two types of problems. One is the maximum independent set link (MISL) problem [13], also known as the capacity maximization problem or single-slot link scheduling problem. In this problem, given a set of communication links, the largest subset of concurrent links that can be transmitted simultaneously in the same time slot must be identified. The other type of problem is the shortest link scheduling (SLS) problem [14, 15], also known as the delay minimization problem. This problem refers to scheduling a given set of links with a minimum of time slots. This paper studies the former problem, namely, designing a link algorithm that schedules as many links as possible in the same time slot.There are many factors that affect the link scheduling problem, such as different choices of centralized [16] or distributed algorithms [17, 18]. Before the centralized algorithm is executed, various information of the network node is broadcast to the execution node, such as the set of neighbors and the transmit power of the node. As the network scale increases, the time complexity of centralized algorithms will increase dramatically. However, the distributed algorithm only needs to obtain the corresponding information of the neighbors during the execution process. Such information exchange can be achieved only by a broadcast, and the running time of the algorithm is independent of the network scale.In addition, establishing a reasonable interference model is the key to designing a correct and efficient link scheduling algorithm. The most commonly used interference models can be classified into the protocol interference model [19] and SINR (signal-to-interference-plus-noise ratio) interference model [20, 21]. Under the protocol model, the transmission of a link is deemed successful if no other links within a certain transmission range are active. Therefore, the coexistence relationship between two links is mainly determined by the geometry. Due to its simplicity, the protocol model has been widely used. By contrast, under the SINR model, the coexistence relationship depends on its own channel condition and the level of the aggregated interference. Specifically, a transmission of a link is said to be successful if its SINR value is greater than a predetermined threshold. One challenge under the SINR model is that multiple links can transmit successfully through a common channel, even if they observe some interference signal from each other, in marked contrast to the protocol model. Furthermore, the link relationship is a function of the distance to the neighboring links and their status, which may change over time. Therefore, the link coexistence relationship under the SINR model is “multilateral” and “dynamic.” As a result, link scheduling under the SINR model is much more complicated. The literature [22] proves the robustness of SINR models with geometric path loss. The SINR model opens a new avenue for more efficient resource allocation.SIC is an effective physical layer technology for multipacket reception to combat interference, and it allows other concurrent transmission links to decode correctly [20]. According to the descending order of the receivers’ power level, SIC regards the interference signals as a useful signal obeying a specific structure. As SIC is able to resolve the collision, more simultaneous transmission and higher performance could be expected [23, 24]. We therefore focus on link scheduling in MIMO wireless networks with SIC. However, there has been little work on exploring SIC in MIMO networks based on the SINR model.The main contributions of this paper are as follows. We propose a distributed link scheduling algorithm in MIMO wireless networks with SIC to maximize the link throughput. First, based on the characteristics of MIMO and SIC, we propose a combination of these two technologies to establish the MSIC model, and a mathematical framework is established for cross-layer optimization of scheduling, with constraints of traffic balance and link capacity. Second, due to the global characteristic of the interference, localization of the interference and division of the interference regions are considered. Finally, a distributed link scheduling algorithm based on MSIC to generate a feasible scheduling set is proposed.The rest of this article is organized as follows: the first and second parts describe the background and current situation. In the third part, the MSIC network model is constructed based on SIC technology, and the cross-layer optimization problem is modeled. In the fourth part, the interference regions are divided, and the detailed process of the distributed link scheduling algorithm based on the MSIC network model is given. The fifth part provides experimental results. The last part summarizes the paper and puts forward the future development trends.


## 2. Related Work

The link scheduling problem has been the subject of extensive research. Moscibroda et al. first defined the link scheduling problem and introduced the concept of scheduling complexity under the SINR model [25]. Goussevkaia et al. proved that the link scheduling problem is NP-hard [26]. Dinitz considered single-slot scheduling and gave the first distributed algorithm [27]. Although his goal was to design a distributed algorithm, the technique relies mainly on the machine learning theory of the algorithm. Qian et al. [21] first developed a new “MIMO-pipe” model that captured the rate-reliability trade-off in MIMO communications. However, the “conservative scheduling” achieves a suboptimal performance. Choi et al. combined a two-segment queue structure and carrier sensing technology to design a fully distributed link scheduling algorithm based on the SINR model [17]. In [28], Chen et al. proposed a low-complexity approximate optimal scheduling algorithm based on a cross-entropy optimization framework.Most previous work in MIMO wireless networks did not consider SIC. We therefore focus on link scheduling in MIMO wireless networks with SIC. The effectiveness of SIC has been verified recently [29]. In [30], Lv et al. studied link scheduling in a network with SIC but ignored the effects of aggregate interference. Then, in 2012, they took the lead in researching link scheduling under the SINR model in wireless networks with SIC [20]. The algorithm considers the influence of cumulative interference, but it is a greedy algorithm based on independent sets that can obtain an approximate optimal schedule. In [24], Kontik et al. proposed a heuristic algorithm based on the column generation method using SIC technology to study the problem of minimized scheduling length in single-hop wireless networks. The performance of this algorithm is very close to the optimal linear programming algorithm and has better robustness. SIC technology was shown to effectively improve network performance.In addition, due to the degree of freedom (DoF) of MIMO, network throughput can be improved by spatial multiplexing (SM). Therefore, the problem of link scheduling based on DoF has also been extensively studied. Based on the DoF concept, Sultan et al. [31] proposed a handover standard that maximizes the capacity of the downlink channel when uplink capacity is maintained at a certain level. To further improve the overall performance of the network, the data link layer, the network layer, and the transmission layer need to be designed cooperatively for optimization. The layered protocol architecture with network adaptability has received widespread attention, such as the joint routing and scheduling optimization scheme [6] and joint power control and link scheduling optimization scheme [32, 33], but there are still many limitations in the practical applications of these optimization schemes. Therefore, a mathematical framework is established in this paper for the cross-layer optimization of routing and scheduling, with constraints of traffic balance and link capacity.


## 3. The System Model

### 3.1. Network Model

When the links are transmitted in the SINR model, if the signal at the expected receiver is higher than a given threshold, the link is transmitted successfully [17], that is,(1)SINRri=PrisiIri+N0≥βwhere Pri(si) is the received power at receiver ri from sender si; Iri is the aggregated interference from the active links in the neighbors of link li; N0 is the background noise; and β is the minimum SINR threshold required for receiver ri to decode signals successfully.Consider a set of MIMO networks consisting ofn communication links L={l1,...,ln}, where each link li includes a sender si and a receiver ri. The Euclidean distance between sj and ri is dji=d(sj,ri). Thus, the length of link li is dii. If si is the intended sender, (1) can be converted into(2)SINRri=Psi/dsi,riαN0+∑sj∈St\siPsj/dsj,riα=Pli/diiαN0+∑lj∈L′\liPlj/djiαwhere P(sj) is the transmission power from sender sj; α is the path-loss factor; St is the set of all senders that are transmitted concurrently in the same time slot t as the expected sender; L′ is a set of links that are simultaneously scheduled in the same time slot.Assume that all nodes are static and apply MIMO technology withM antennas. A node communicates with others through wireless links, and each node has an input links set Liin and an output links set Liout of node i. Suppose a time frame consists of T slots, and the state of a link subset in a time slot t  (1≤t≤T) depends on link scheduling. For a given slot t, the data flow from sender sj to ri can be expressed as a signal vector xj=[xj1,xj2,...,xjM]T, and the MIMO signal yji received by receiver ri from sender sj can be expressed as the following:(3)yji=αjiVji†Hji†UjAjxj+∑k∈Ii,k≠jαkiVji†Hki†UkAkxk+Vji†niwhere Hki∈CM×M is the channel matrix between sender sk and receiver ri and is normalized to mean power 1; □† is the Hermitian operations of the corresponding matrix; Uk∈CM×M is the unitary transmitting precoding matrix at sender sk; Aj∈RM×Mand Aj=diagpj,pj,...,pj is the real-valued diagonal transmit amplitude matrix, where pj is the transmission power of the corresponding sender sj; Vji∈CM×M is the unitary receiving decoding matrix at receiver ri for signals from sender sj; ni∈CM×1 is a white Gaussian noise vector with variance N0 per element; 2 is the norm of the vector. Figure 2 shows that the sender and receiver 2-antenna array and MIMO channel are used at both ends. To simplify calculations, assuming that data streams are uncorrelated, the SINR for the n-th element in yji is given by the following:(4)SINRjin=pjαji2vjin†Hji†ujn2N0+∑k∈Ii,k≠jpkαki2vjin†Hki†Uk2Figure 2
Multi-antenna Wireless Channel.


### 3.2. MSIC Model

The manner in which interference is dealt with effectively affects the performance of the link scheduling algorithm in MIMO networks. The MSIC model is constructed based on SIC under the SINR model. The main idea of SIC is that the power level of the signals fromK senders received at ri are in descending order: Pri(sK)≥Pri(sK-1),...,Pri(si),...,Pri(s2)≥Pri(s1) [20]. If the strongest signal dissatisfies the SINR constraint, the process of SIC ends. Otherwise this signal will be decoded, while other signals are considered interference and noise. If it is the expected signal, then the transmission is successful; if not, this signal is removed, and the remaining signals are decoded sequentially until the expected signal is decoded successfully.In detail, the SIC model needs to satisfy the following constraints. Receiverri tries to decode signal from sender sn in the order k,k-1,...,n. Then, the signal with received power Pri(sn) can be decoded successfully if and only if (5)step1PriskN0+∑j∈Ii,j=1k-1Prisj≥βki,step2Prisk-1N0+∑j∈Ii,j=1k-2Prisj≥βk-1i,⋯stepk-n+1PrisnN0+∑j∈Ii,j=1n-1Prisj≥βni.If signalyii wants to be decoded correctly, it must satisfy the MSIC constraints shown in (6)SINRjin=pjαji2vjin†Hji†ujn2N0+∑k∈Ii,k<jpkαki2vjin†Hki†Uk2≥βji,∀j,s.t.Prisi<PrisjSINRiin=piαii2viin†Hii†uin2N0+∑k∈Ii,k<ipkαki2viin†Hki†Uk2≥βiiBecause SIC is used, the receiver can sequentially cancel all interference signals that are stronger than its expected signal if those stronger signals satisfy (6). Therefore, it is only necessary to consider the residual interference at the sender, which is weaker than the expected signal. Specifically, the residual SINR from sender sj to receiver ri at time slot t is defined as follows:(7)r-SINRjit=pjαji2vjin†Hji†ujn2N0+∑k∈Ii,k≠jpkαki2vkin†Hki†Uk2≤pjαji2vjin†Hji†ujn2pkαki2vjin†Hki†Uk2≥βjiwhere sender sk in the summation formula includes all senders’ signals with weaker power than node sj.


### 3.3. Problem Model

Consider the problem of throughput maximization in MIMO wireless networks. This paper transforms the cross-layer joint scheduling problem into congestion control, routing, and scheduling problems. By using local information, the congestion control problem is solved at the source node of each flow, and the routing and scheduling are transformed into the problem of flow balance and link capacity constraint, which facilitates distributed deployment and ensures network throughput.LetF denote a set of active link session flows that describes the flow routing in the network. Denote s(f) and d(f) as the source and destination nodes of session flow f∈F, respectively. Υ(f) represents the reachable end-to-end throughput of session flow f∈F, and Υmin is the minimum reachable end-to-end throughput in all sessions, that is, Υmin=minf∈FΥ(f). Υl(f) represents the number of data rates caused by session flow f∈F on link l. The goal of this paper is to maximize the minimum reachable end-to-end throughput Υmin to maximize network throughput.We assume a half-duplex node on a MIMO node. If nodei∈N is a sender in time slot t, the binary variable si(t) is 1; otherwise, it is 0. Similarly, if node i∈N is a receiver in time slot t, the binary variable ri(t) is 1; otherwise, it is 0. For half-duplex mode, the constraint can be written as follows:(8)sit+rit≤1,1≤i≤N,1≤t≤TDenotexl(t) as the number of data streams over link l. If node i is not a sender, then there is ∑l∈Lioutxl(t)=0. Otherwise, in order to satisfy the DoF constraint at the sending node, the total number of outgoing data streams should be positive and cannot exceed the number of antennas it owns, that is, 1≤∑l∈Lioutxl(t)≤M. These two cases can be summarized as follows:(9)sit≤∑l∈Lioutxlt≤Msit,1≤i≤N,1≤t≤TSimilarly, according to whether node i is an active receiver, we have the following constraint at the receiving node:(10)rit≤∑l∈Liinxlt≤Mrit,1≤i≤N,1≤t≤TFor the congestion control problem of the transport layer, each flowf in the network determines the data rate of the next slot independently according to the local congestion queue information of the node in the current time slot. Uif(t) represents the congestion queue length of flow f at node i in time slot t, and U(t)=[Uif(t)],(i∈N,f∈F) is the set of all congestion queues. According to the input and output mode of each node, the local congestion queue information is updated dynamically as follows: Uif(t+1)=Uif(t)+∑l∈Liinxl(t)-∑l∈Lioutxl(t)+vf(t), and the initialized condition queue is satisfied with Uif(0)=0. The source session flow f is compressed into a source rate vf(t) before being pushed into the queue. Since the local congestion queue length of each node determines the upper limit of the data sum that can be transmitted in the current time slot t, there are the following constraints:(11)∑l∈Lioutxlt≤Uift,1≤i≤N,1≤t≤T,f∈FThe session flow f in the network determines the data rate of the next time slot according to the congestion queue constraint. Meanwhile, in order to guarantee the strong robustness of the network, the following inequalities must be satisfied:(12)limT→∞⁡1T∑t=0T-1∑i∈N∑f∈FEUift<∞For routing and scheduling problems,D=max⁡∑l∈Lrlf∗maxf∈F⁡uslf-udlf, and each link l can use local congestion queue information to find a flow f∗ that satisfies f∗=arg⁡maxf∈F⁡uslf-udlf. Let wl=usl(f∗)-udl(f∗) as the weight of link l  (wl can also be understood as the queue length at link l with flow f∗). To solve routing and scheduling problems, we will propose a distributed algorithm in Section 4 to generate an active set LS′ of concurrent links. In each time slot, the links in set LS′ can send data to the receivers (we assume that, in each time slot, each active link transmits a packet). Let D be converted into the following form:(13)D=max⁡∑l∈LΥlf∗·wlTo achieve the goal of maximizing the minimum end-to-end throughputΥmin, a feasible routing scheduling also needs to satisfy the following two constraints: flow balance constraints and the link capacity constraint. We have the following flow balance constraints:(a)
at the source node, we have(14)∑l∈LioutΥlf=Υf,i=sf,f∈F(b)
at each relay node, we have(15)∑l∈LiinΥlf=∑l∈LioutΥlf,1≤i≤N,i≠sf,i≠df,f∈F(c)
at the destination node, we have(16)∑l∈LiinΥlf=Υf,i=df,f∈FIt is easy to verify that as long as any two of these equations are satisfied, the other one will also be satisfied. Therefore, it is sufficient to satisfy the first two equations.It is assumed that a fixed modulation and encoding scheme is used for each data stream and that each data stream corresponds to one unit data rate. Since the total data rate on linkl cannot exceed the average rate of the link, we have the following link capacity constraint:(17)∑f∈FΥlf≤1T∑t=1Txltwhere the right side represents the average throughput on link l of a frame (T time slots). Putting all the constraints together, we have the expression for the throughput maximization problem:(18)maxΥmins.t.Υmin≤Υf,f∈F;r-SINRjit=pjαji2vjin†Hji†ujn2N0+∑k∈Ii,k≠jpkαki2vkin†Hki†Uk2≤pjαji2vjin†Hji†ujn2pkαki2vjin†Hki†Uk2≥βji;sit+rit≤1,1≤i≤N,1≤t≤T;sit≤∑l∈Lioutxlt≤Msit,1≤i≤N,1≤t≤T;rit≤∑l∈Liinxlt≤Mrit,1≤i≤N,1≤t≤T;∑l∈Lioutxlt≤Uift,1≤i≤N,1≤t≤T,f∈F;limT→∞1T∑t=0T-1∑i∈N∑f∈FEUift<∞;∑l∈LioutΥlf=Υf,i=sf,f∈F;∑l∈LiinΥlf=∑l∈LioutΥlf,1≤i≤N,i≠sf,i≠df,f∈F;∑f∈FΥlf≤1T∑t=1Txlt.


## 3.1. Network Model

When the links are transmitted in the SINR model, if the signal at the expected receiver is higher than a given threshold, the link is transmitted successfully [17], that is,(1)SINRri=PrisiIri+N0≥βwhere Pri(si) is the received power at receiver ri from sender si; Iri is the aggregated interference from the active links in the neighbors of link li; N0 is the background noise; and β is the minimum SINR threshold required for receiver ri to decode signals successfully.Consider a set of MIMO networks consisting ofn communication links L={l1,...,ln}, where each link li includes a sender si and a receiver ri. The Euclidean distance between sj and ri is dji=d(sj,ri). Thus, the length of link li is dii. If si is the intended sender, (1) can be converted into(2)SINRri=Psi/dsi,riαN0+∑sj∈St\siPsj/dsj,riα=Pli/diiαN0+∑lj∈L′\liPlj/djiαwhere P(sj) is the transmission power from sender sj; α is the path-loss factor; St is the set of all senders that are transmitted concurrently in the same time slot t as the expected sender; L′ is a set of links that are simultaneously scheduled in the same time slot.Assume that all nodes are static and apply MIMO technology withM antennas. A node communicates with others through wireless links, and each node has an input links set Liin and an output links set Liout of node i. Suppose a time frame consists of T slots, and the state of a link subset in a time slot t  (1≤t≤T) depends on link scheduling. For a given slot t, the data flow from sender sj to ri can be expressed as a signal vector xj=[xj1,xj2,...,xjM]T, and the MIMO signal yji received by receiver ri from sender sj can be expressed as the following:(3)yji=αjiVji†Hji†UjAjxj+∑k∈Ii,k≠jαkiVji†Hki†UkAkxk+Vji†niwhere Hki∈CM×M is the channel matrix between sender sk and receiver ri and is normalized to mean power 1; □† is the Hermitian operations of the corresponding matrix; Uk∈CM×M is the unitary transmitting precoding matrix at sender sk; Aj∈RM×Mand Aj=diagpj,pj,...,pj is the real-valued diagonal transmit amplitude matrix, where pj is the transmission power of the corresponding sender sj; Vji∈CM×M is the unitary receiving decoding matrix at receiver ri for signals from sender sj; ni∈CM×1 is a white Gaussian noise vector with variance N0 per element; 2 is the norm of the vector. Figure 2 shows that the sender and receiver 2-antenna array and MIMO channel are used at both ends. To simplify calculations, assuming that data streams are uncorrelated, the SINR for the n-th element in yji is given by the following:(4)SINRjin=pjαji2vjin†Hji†ujn2N0+∑k∈Ii,k≠jpkαki2vjin†Hki†Uk2Figure 2
Multi-antenna Wireless Channel.


## 3.2. MSIC Model

The manner in which interference is dealt with effectively affects the performance of the link scheduling algorithm in MIMO networks. The MSIC model is constructed based on SIC under the SINR model. The main idea of SIC is that the power level of the signals fromK senders received at ri are in descending order: Pri(sK)≥Pri(sK-1),...,Pri(si),...,Pri(s2)≥Pri(s1) [20]. If the strongest signal dissatisfies the SINR constraint, the process of SIC ends. Otherwise this signal will be decoded, while other signals are considered interference and noise. If it is the expected signal, then the transmission is successful; if not, this signal is removed, and the remaining signals are decoded sequentially until the expected signal is decoded successfully.In detail, the SIC model needs to satisfy the following constraints. Receiverri tries to decode signal from sender sn in the order k,k-1,...,n. Then, the signal with received power Pri(sn) can be decoded successfully if and only if (5)step1PriskN0+∑j∈Ii,j=1k-1Prisj≥βki,step2Prisk-1N0+∑j∈Ii,j=1k-2Prisj≥βk-1i,⋯stepk-n+1PrisnN0+∑j∈Ii,j=1n-1Prisj≥βni.If signalyii wants to be decoded correctly, it must satisfy the MSIC constraints shown in (6)SINRjin=pjαji2vjin†Hji†ujn2N0+∑k∈Ii,k<jpkαki2vjin†Hki†Uk2≥βji,∀j,s.t.Prisi<PrisjSINRiin=piαii2viin†Hii†uin2N0+∑k∈Ii,k<ipkαki2viin†Hki†Uk2≥βiiBecause SIC is used, the receiver can sequentially cancel all interference signals that are stronger than its expected signal if those stronger signals satisfy (6). Therefore, it is only necessary to consider the residual interference at the sender, which is weaker than the expected signal. Specifically, the residual SINR from sender sj to receiver ri at time slot t is defined as follows:(7)r-SINRjit=pjαji2vjin†Hji†ujn2N0+∑k∈Ii,k≠jpkαki2vkin†Hki†Uk2≤pjαji2vjin†Hji†ujn2pkαki2vjin†Hki†Uk2≥βjiwhere sender sk in the summation formula includes all senders’ signals with weaker power than node sj.


## 3.3. Problem Model

Consider the problem of throughput maximization in MIMO wireless networks. This paper transforms the cross-layer joint scheduling problem into congestion control, routing, and scheduling problems. By using local information, the congestion control problem is solved at the source node of each flow, and the routing and scheduling are transformed into the problem of flow balance and link capacity constraint, which facilitates distributed deployment and ensures network throughput.LetF denote a set of active link session flows that describes the flow routing in the network. Denote s(f) and d(f) as the source and destination nodes of session flow f∈F, respectively. Υ(f) represents the reachable end-to-end throughput of session flow f∈F, and Υmin is the minimum reachable end-to-end throughput in all sessions, that is, Υmin=minf∈FΥ(f). Υl(f) represents the number of data rates caused by session flow f∈F on link l. The goal of this paper is to maximize the minimum reachable end-to-end throughput Υmin to maximize network throughput.We assume a half-duplex node on a MIMO node. If nodei∈N is a sender in time slot t, the binary variable si(t) is 1; otherwise, it is 0. Similarly, if node i∈N is a receiver in time slot t, the binary variable ri(t) is 1; otherwise, it is 0. For half-duplex mode, the constraint can be written as follows:(8)sit+rit≤1,1≤i≤N,1≤t≤TDenotexl(t) as the number of data streams over link l. If node i is not a sender, then there is ∑l∈Lioutxl(t)=0. Otherwise, in order to satisfy the DoF constraint at the sending node, the total number of outgoing data streams should be positive and cannot exceed the number of antennas it owns, that is, 1≤∑l∈Lioutxl(t)≤M. These two cases can be summarized as follows:(9)sit≤∑l∈Lioutxlt≤Msit,1≤i≤N,1≤t≤TSimilarly, according to whether node i is an active receiver, we have the following constraint at the receiving node:(10)rit≤∑l∈Liinxlt≤Mrit,1≤i≤N,1≤t≤TFor the congestion control problem of the transport layer, each flowf in the network determines the data rate of the next slot independently according to the local congestion queue information of the node in the current time slot. Uif(t) represents the congestion queue length of flow f at node i in time slot t, and U(t)=[Uif(t)],(i∈N,f∈F) is the set of all congestion queues. According to the input and output mode of each node, the local congestion queue information is updated dynamically as follows: Uif(t+1)=Uif(t)+∑l∈Liinxl(t)-∑l∈Lioutxl(t)+vf(t), and the initialized condition queue is satisfied with Uif(0)=0. The source session flow f is compressed into a source rate vf(t) before being pushed into the queue. Since the local congestion queue length of each node determines the upper limit of the data sum that can be transmitted in the current time slot t, there are the following constraints:(11)∑l∈Lioutxlt≤Uift,1≤i≤N,1≤t≤T,f∈FThe session flow f in the network determines the data rate of the next time slot according to the congestion queue constraint. Meanwhile, in order to guarantee the strong robustness of the network, the following inequalities must be satisfied:(12)limT→∞⁡1T∑t=0T-1∑i∈N∑f∈FEUift<∞For routing and scheduling problems,D=max⁡∑l∈Lrlf∗maxf∈F⁡uslf-udlf, and each link l can use local congestion queue information to find a flow f∗ that satisfies f∗=arg⁡maxf∈F⁡uslf-udlf. Let wl=usl(f∗)-udl(f∗) as the weight of link l  (wl can also be understood as the queue length at link l with flow f∗). To solve routing and scheduling problems, we will propose a distributed algorithm in Section 4 to generate an active set LS′ of concurrent links. In each time slot, the links in set LS′ can send data to the receivers (we assume that, in each time slot, each active link transmits a packet). Let D be converted into the following form:(13)D=max⁡∑l∈LΥlf∗·wlTo achieve the goal of maximizing the minimum end-to-end throughputΥmin, a feasible routing scheduling also needs to satisfy the following two constraints: flow balance constraints and the link capacity constraint. We have the following flow balance constraints:(a)
at the source node, we have(14)∑l∈LioutΥlf=Υf,i=sf,f∈F(b)
at each relay node, we have(15)∑l∈LiinΥlf=∑l∈LioutΥlf,1≤i≤N,i≠sf,i≠df,f∈F(c)
at the destination node, we have(16)∑l∈LiinΥlf=Υf,i=df,f∈FIt is easy to verify that as long as any two of these equations are satisfied, the other one will also be satisfied. Therefore, it is sufficient to satisfy the first two equations.It is assumed that a fixed modulation and encoding scheme is used for each data stream and that each data stream corresponds to one unit data rate. Since the total data rate on linkl cannot exceed the average rate of the link, we have the following link capacity constraint:(17)∑f∈FΥlf≤1T∑t=1Txltwhere the right side represents the average throughput on link l of a frame (T time slots). Putting all the constraints together, we have the expression for the throughput maximization problem:(18)maxΥmins.t.Υmin≤Υf,f∈F;r-SINRjit=pjαji2vjin†Hji†ujn2N0+∑k∈Ii,k≠jpkαki2vkin†Hki†Uk2≤pjαji2vjin†Hji†ujn2pkαki2vjin†Hki†Uk2≥βji;sit+rit≤1,1≤i≤N,1≤t≤T;sit≤∑l∈Lioutxlt≤Msit,1≤i≤N,1≤t≤T;rit≤∑l∈Liinxlt≤Mrit,1≤i≤N,1≤t≤T;∑l∈Lioutxlt≤Uift,1≤i≤N,1≤t≤T,f∈F;limT→∞1T∑t=0T-1∑i∈N∑f∈FEUift<∞;∑l∈LioutΥlf=Υf,i=sf,f∈F;∑l∈LiinΥlf=∑l∈LioutΥlf,1≤i≤N,i≠sf,i≠df,f∈F;∑f∈FΥlf≤1T∑t=1Txlt.


## 4. Distributed Link Scheduling Algorithm Based on MSIC

### 4.1. Division of Interference Regions

Due to the characteristics of transmission loss, the receiving powerPri(sj) of different links is also different [34]. The total interference at receiver ri is expressed as follows:(19)Iri=∑sj∈St\siPsjdsj,riα=∑sj∈St\siPrisjThe scheduling problem of using SIC under the SINR model has been proved to be NP-hard [20]. If the stronger signal in the network satisfies (5), it can be decoded and removed due to the adoption of SIC. Therefore, the strength of the receiving power does not completely measure the interference generated by the link. In this paper, in order to describe the interference localization, the interference regions are defined to measure the level of interference.Different interference regionsAli,Bli, and Cliare divided according to (19). Ali,Bli, and Cli are concentric ring (circular) regions centered on receiver ri of link li, respectively, as shown in Figure 3 (the red circular region is Ali, the blue ring region is Bli, and the black dotted ring region is Cli). The interference generated by the active link in the Ali and Bli regions will interrupt the transmission of link li, and the set of concurrent links in these regions is denoted as LS. The cumulative interference generated by the active link in the Cli region has a negligible effect on the receiver of link li.Figure 3
Division of Interference Regions.According to (2), the maximum cumulative interference value that link li can tolerate is the following:(20)Iri≤Ilimax≤PliβdiiαTherefore, in order to satisfy the MSIC constraints, the sum of the cumulative interference values at receiverri of link li cannot exceed Ilimax. If the total interference in the Ali and Bli regions is (1-m)Ilimax and the total interference in the Cli region is mIlimax, then we have (21)1-mIlimax+mIlimax≤IlimaxAssuming that the link lj at receiver ri from sender sj∈Ali is stronger than link li from sender si, SIC is used. That is, receiver ri uses SIC to decode these strong signals continuously before decoding the expected signal from sender si. Let all links in a feasible set LS of concurrent links be transmitted successfully. When any link lj is added to the set LS′⊆LS, the link transmission will fail. Obviously, LS′ is the maximum set of concurrent links, and LS′ must satisfy the constraints in (7).


### 4.2. Distributed MSIC Scheduling Algorithm

In this section, based on the CSMA/CA mechanism and MSIC constraints, we design the distributed single-slot MSIC algorithm to solve the scheduling problems. If the linksl∈L′ in the network can be transmitted concurrently, then L′ can be defined as a scheduling set. In each scheduling time slot, each link will run scheduling algorithms to generate a new feasible scheduling set LS′.Next, considering the MSIC model and interference regions division introduced above, a distributed link scheduling algorithm is proposed under the MSIC constraints. The algorithm flow chart is shown in Figure4. Three states of the link are defined: Active, Inactive, and Standby. The four sets correspond to different states, where sic is the active link set that satisfies the MSIC constraint and can be scheduled in the current scheduling time slot; acc is the standby link set that has not been judged by MSIC constraints; loc is the local cache link set in the standby state; and seq is the candidate link set in the inactive state. Therefore, the state of a link in the current slot can be distinguished by the set of links to which the link currently belongs.Figure 4
Distributed MSIC scheduling algorithm flow chart.(  1) Initialization Stage. At the beginning of each scheduling cycle, each link l maintains two sets of local links: set accl and set seql. The links contained in the set accl are added to a feasible set LS of concurrent links in a certain scheduling cycle, and the links contained in set seql are candidate links to be added into set LS. At the beginning of each scheduling cycle, initializing accl=Ø and seql=l,Al∪Bl.(  2) MSIC Feasibility Judgment Stage. Each scheduling cycle consists of several slots, and in each slot each link l makes a decision about whether it should be added to accl or removed from seql. At the beginning of each scheduling slot, all links in the set seql are weighted for comparison. The sender of link l broadcasts its weight information wl to all links k whose sender is located in the Al region of link l. If link l has the largest weight among all links in seql, it will run Algorithm 1 to try to add itself to accl.Algorithm 1:Distributed MSIC Scheduling Algorithm (MSIC feasibility judgment).
1 sets of intaccl, seql, locl, sicl′, sicl′      %initialize 2accl←Ø and seql←l,Al∪Bl 3 Sender of linkl broadcasts Request message to links in {Al∪Bl}; 4for link l′∈Al∪Bl∩accl∪locl do     %MSIC feasibility judgment 5if sender of link l′ receives Request message from sender of link l then 6sender of link l′ adds link l into lock; 7sender of link l′ calculates cumulative interference Il′; 8if Il′>(1-m)Il′max then 9Sender of link l′ broadcasts Error message to sender of link l; 10else 11Generate sicl′; 12for k∈sicl′ do 13Link k calculates cumulative interference Ik; 14if Ik>(1-m)Ikmax then 15Sender of link l′ broadcasts Error message to sender of link l; 16end if 17end for 18end if 19end if 20 end for 21 if sender of linkl does not receive Error messages then  %Generate concurrent links set 22accl←accl∪l; 23seql←seql/l; 24locl←locl/l; 25Sender of link l broadcasts Success message to all its neighbors to update their link sets acc, seq and loc; 26Goto Algorithm 2; 27 else 28seql←seql/l;        %Does not satisfy MSIC feasibility conditions 29Sender of link l broadcasts Remove message to all its neighbors to update their local link sets seq and loc; 30 end ifAlgorithm 2:Distributed MSIC Scheduling Algorithm (MSIC feasibility test).
1 sets of intIk′, Ij′, sick′ 2for link k∈Al∪Bl∩seql do    %MSIC feasibility test 3if the sender of link k receives a Successmessage from the sender of link l then 4Link k calculates the cumulative interference Ik′; 5if Ik′>(1-m)Ikmax then 6The sender of link k broadcasts a Remove message to its neighbors to update their link sets seq; 7else 8Generate sick′; 9for j∈sick′ do 10Link j calculates the cumulative interference Ij′; 11if Ij′>(1-m)Ijmax then 12The sender of link k broadcasts a Remove message to its neighbors to update their link sets seq; 13end if 14end for 15end if 16end if 17end forThe detailed process is as follows. The sender of linkl broadcasts a Request message to links in {Al∪Bl} first. If there is a collision, all of the links select a random back-off time and wait for it. If there is no collision, the sender of all links in {Al∪Bl} will add link l to set locl. When link l is added to the current schedule, any link l′∈accl∪locl will determine whether it remains feasible under the MSIC constraints. The specific judgment process is as follows. For each link l′∈accl∪locl, the set of links with sender sl′∈{accl′∪locl′}∩Al′ and receiver rl′ is defined as the MSIC link set sicl′. The MSIC constraints will be satisfied when any link l′∈accl∪locl satisfies the following conditions: (i) the total interference Il′ coming from set Bl′ does not exceed (1-m)Il′max; (ii) all links k∈sicl′ are feasible; that is, the total interference Ik coming from set Bk does not exceed (1-m)Ikmax.According to the above procedure, if any linkl′∈accl∪locl does not satisfy the MSIC constraints, the sender of link l′ will send an Error message to link l indicating that link l cannot be added to set LS (the current scheduling is not feasible due to the strong interference caused by link l). If link l∈locl does not receive any Error messages from its neighbors, it adds link l to set accl and removes link l from seql and locl. Then, the sender broadcasts a Success message to all its neighbors to update their link sets acc, seq, and loc. Otherwise, it removes link l from seql and locl and then broadcasts a Remove message to all its neighbors to update their link sets seq and loc. After the above process is performed until a new link is added to LS, the current scheduling process is still feasible under the MSIC constraints.(  3) MSIC Feasibility Test Stage. After a new LS′ is generated in each slot, all links l∈seql need to make the following decision about whether the MSIC constraints are satisfied. For each link l∈seql, the set of links with sender sl∈accl∩Al and receiver rl is defined as another MSIC link set sicl′. Similar to the first procedure, any link l∈seql that satisfies any of the following conditions will dissatisfy the MSIC constraints: (i) the total interference Il′ coming from set Bl exceeds (1-m)Ilmax or (ii) for any link k′∈sicl′ is not feasible; that is, the total interference Ik′ coming from set Bk′ exceeds (1-m)Ik′max. After the above process, if there is a link l in seql that does not satisfy the MSIC constraints, the sender will remove link l from seql and broadcast a Remove message to all its neighbors to update their link sets seq and acc. The above process ensures that each link in seql satisfies the MSIC constraints under the current scheduling.In the distributed algorithm, the number of time slots in each scheduling cycle is a fixed value. In each scheduling slot, each link will run the distributed scheduling algorithm to generate a new feasible scheduling setLS′ during scheduling. Once the scheduling is completed, the selected link will transmit a packet during the transmission cycle.


### 4.3. Theoretical Proof of Algorithm

Theorem 1.
The setLS of scheduling generated by the MSIC algorithm is feasible.Proof.
Based on the MSIC algorithm under interference regions division, each link will run the algorithm independently in each scheduling slot to generate a new feasible scheduling setLS′. From Algorithm 2, it is known that after a new set LS′ is generated in each time slot, all links l∈seql need to be tested to determine if the MSIC constraints are still satisfied. To ensure that each link in seql satisfies the MSIC constraints under the current scheduling, any link l that does not satisfy the MSIC constraints will be removed from seql. Therefore, the interference links cannot be scheduled at the same time; that is, the links in the current set LS′ are feasible, which ensures the feasibility of the algorithm.Theorem 2.
The time complexity of the MSIC algorithm isO(k2).Proof.
In the process of MSIC feasibility judgment of Algorithm1, it is necessary to judge the MSIC constraints formula (4) of any link l′∈accl∪locl and decide whether to add the link to the current scheduling set. This process requires two loop statements to be executed with the algorithm execution complexity of O(k2), where k represents the number of concurrently transmitted signals. After Algorithm 1 generates a new set LS′, the MSIC feasibility test is performed in Algorithm 2. The MSIC constraints condition needs to be tested again for all links l∈seql to ensure that any link in seql satisfies the MSIC constraints. This process also needs to execute two loop statements with the algorithm execution complexity of O(k2). Therefore, the total algorithm execution complexity is O(k2).Theorem 3.
The messages complexity of the MSIC algorithm isO(n).Proof.
The message complexity of sending a Request broadcast message isO(1). To find a set of links that can be concurrently given by a network of n links, an MSIC constraint judgment is performed for each link of l′∈{Al∪Bl}∩{accl∪locl}, and the number of Error or Success messages sent is at most n-1. For each link of k∈{{Al∪Bl}∩seql}, a feasibility test is performed, and the number of Remove or Success messages is up to n-1. When the execution of the algorithm ends, the total number of messages used is up to O(n).


## 4.1. Division of Interference Regions

Due to the characteristics of transmission loss, the receiving powerPri(sj) of different links is also different [34]. The total interference at receiver ri is expressed as follows:(19)Iri=∑sj∈St\siPsjdsj,riα=∑sj∈St\siPrisjThe scheduling problem of using SIC under the SINR model has been proved to be NP-hard [20]. If the stronger signal in the network satisfies (5), it can be decoded and removed due to the adoption of SIC. Therefore, the strength of the receiving power does not completely measure the interference generated by the link. In this paper, in order to describe the interference localization, the interference regions are defined to measure the level of interference.Different interference regionsAli,Bli, and Cliare divided according to (19). Ali,Bli, and Cli are concentric ring (circular) regions centered on receiver ri of link li, respectively, as shown in Figure 3 (the red circular region is Ali, the blue ring region is Bli, and the black dotted ring region is Cli). The interference generated by the active link in the Ali and Bli regions will interrupt the transmission of link li, and the set of concurrent links in these regions is denoted as LS. The cumulative interference generated by the active link in the Cli region has a negligible effect on the receiver of link li.Figure 3
Division of Interference Regions.According to (2), the maximum cumulative interference value that link li can tolerate is the following:(20)Iri≤Ilimax≤PliβdiiαTherefore, in order to satisfy the MSIC constraints, the sum of the cumulative interference values at receiverri of link li cannot exceed Ilimax. If the total interference in the Ali and Bli regions is (1-m)Ilimax and the total interference in the Cli region is mIlimax, then we have (21)1-mIlimax+mIlimax≤IlimaxAssuming that the link lj at receiver ri from sender sj∈Ali is stronger than link li from sender si, SIC is used. That is, receiver ri uses SIC to decode these strong signals continuously before decoding the expected signal from sender si. Let all links in a feasible set LS of concurrent links be transmitted successfully. When any link lj is added to the set LS′⊆LS, the link transmission will fail. Obviously, LS′ is the maximum set of concurrent links, and LS′ must satisfy the constraints in (7).


## 4.2. Distributed MSIC Scheduling Algorithm

In this section, based on the CSMA/CA mechanism and MSIC constraints, we design the distributed single-slot MSIC algorithm to solve the scheduling problems. If the linksl∈L′ in the network can be transmitted concurrently, then L′ can be defined as a scheduling set. In each scheduling time slot, each link will run scheduling algorithms to generate a new feasible scheduling set LS′.Next, considering the MSIC model and interference regions division introduced above, a distributed link scheduling algorithm is proposed under the MSIC constraints. The algorithm flow chart is shown in Figure4. Three states of the link are defined: Active, Inactive, and Standby. The four sets correspond to different states, where sic is the active link set that satisfies the MSIC constraint and can be scheduled in the current scheduling time slot; acc is the standby link set that has not been judged by MSIC constraints; loc is the local cache link set in the standby state; and seq is the candidate link set in the inactive state. Therefore, the state of a link in the current slot can be distinguished by the set of links to which the link currently belongs.Figure 4
Distributed MSIC scheduling algorithm flow chart.(  1) Initialization Stage. At the beginning of each scheduling cycle, each link l maintains two sets of local links: set accl and set seql. The links contained in the set accl are added to a feasible set LS of concurrent links in a certain scheduling cycle, and the links contained in set seql are candidate links to be added into set LS. At the beginning of each scheduling cycle, initializing accl=Ø and seql=l,Al∪Bl.(  2) MSIC Feasibility Judgment Stage. Each scheduling cycle consists of several slots, and in each slot each link l makes a decision about whether it should be added to accl or removed from seql. At the beginning of each scheduling slot, all links in the set seql are weighted for comparison. The sender of link l broadcasts its weight information wl to all links k whose sender is located in the Al region of link l. If link l has the largest weight among all links in seql, it will run Algorithm 1 to try to add itself to accl.Algorithm 1:Distributed MSIC Scheduling Algorithm (MSIC feasibility judgment).
1 sets of intaccl, seql, locl, sicl′, sicl′      %initialize 2accl←Ø and seql←l,Al∪Bl 3 Sender of linkl broadcasts Request message to links in {Al∪Bl}; 4for link l′∈Al∪Bl∩accl∪locl do     %MSIC feasibility judgment 5if sender of link l′ receives Request message from sender of link l then 6sender of link l′ adds link l into lock; 7sender of link l′ calculates cumulative interference Il′; 8if Il′>(1-m)Il′max then 9Sender of link l′ broadcasts Error message to sender of link l; 10else 11Generate sicl′; 12for k∈sicl′ do 13Link k calculates cumulative interference Ik; 14if Ik>(1-m)Ikmax then 15Sender of link l′ broadcasts Error message to sender of link l; 16end if 17end for 18end if 19end if 20 end for 21 if sender of linkl does not receive Error messages then  %Generate concurrent links set 22accl←accl∪l; 23seql←seql/l; 24locl←locl/l; 25Sender of link l broadcasts Success message to all its neighbors to update their link sets acc, seq and loc; 26Goto Algorithm 2; 27 else 28seql←seql/l;        %Does not satisfy MSIC feasibility conditions 29Sender of link l broadcasts Remove message to all its neighbors to update their local link sets seq and loc; 30 end ifAlgorithm 2:Distributed MSIC Scheduling Algorithm (MSIC feasibility test).
1 sets of intIk′, Ij′, sick′ 2for link k∈Al∪Bl∩seql do    %MSIC feasibility test 3if the sender of link k receives a Successmessage from the sender of link l then 4Link k calculates the cumulative interference Ik′; 5if Ik′>(1-m)Ikmax then 6The sender of link k broadcasts a Remove message to its neighbors to update their link sets seq; 7else 8Generate sick′; 9for j∈sick′ do 10Link j calculates the cumulative interference Ij′; 11if Ij′>(1-m)Ijmax then 12The sender of link k broadcasts a Remove message to its neighbors to update their link sets seq; 13end if 14end for 15end if 16end if 17end forThe detailed process is as follows. The sender of linkl broadcasts a Request message to links in {Al∪Bl} first. If there is a collision, all of the links select a random back-off time and wait for it. If there is no collision, the sender of all links in {Al∪Bl} will add link l to set locl. When link l is added to the current schedule, any link l′∈accl∪locl will determine whether it remains feasible under the MSIC constraints. The specific judgment process is as follows. For each link l′∈accl∪locl, the set of links with sender sl′∈{accl′∪locl′}∩Al′ and receiver rl′ is defined as the MSIC link set sicl′. The MSIC constraints will be satisfied when any link l′∈accl∪locl satisfies the following conditions: (i) the total interference Il′ coming from set Bl′ does not exceed (1-m)Il′max; (ii) all links k∈sicl′ are feasible; that is, the total interference Ik coming from set Bk does not exceed (1-m)Ikmax.According to the above procedure, if any linkl′∈accl∪locl does not satisfy the MSIC constraints, the sender of link l′ will send an Error message to link l indicating that link l cannot be added to set LS (the current scheduling is not feasible due to the strong interference caused by link l). If link l∈locl does not receive any Error messages from its neighbors, it adds link l to set accl and removes link l from seql and locl. Then, the sender broadcasts a Success message to all its neighbors to update their link sets acc, seq, and loc. Otherwise, it removes link l from seql and locl and then broadcasts a Remove message to all its neighbors to update their link sets seq and loc. After the above process is performed until a new link is added to LS, the current scheduling process is still feasible under the MSIC constraints.(  3) MSIC Feasibility Test Stage. After a new LS′ is generated in each slot, all links l∈seql need to make the following decision about whether the MSIC constraints are satisfied. For each link l∈seql, the set of links with sender sl∈accl∩Al and receiver rl is defined as another MSIC link set sicl′. Similar to the first procedure, any link l∈seql that satisfies any of the following conditions will dissatisfy the MSIC constraints: (i) the total interference Il′ coming from set Bl exceeds (1-m)Ilmax or (ii) for any link k′∈sicl′ is not feasible; that is, the total interference Ik′ coming from set Bk′ exceeds (1-m)Ik′max. After the above process, if there is a link l in seql that does not satisfy the MSIC constraints, the sender will remove link l from seql and broadcast a Remove message to all its neighbors to update their link sets seq and acc. The above process ensures that each link in seql satisfies the MSIC constraints under the current scheduling.In the distributed algorithm, the number of time slots in each scheduling cycle is a fixed value. In each scheduling slot, each link will run the distributed scheduling algorithm to generate a new feasible scheduling setLS′ during scheduling. Once the scheduling is completed, the selected link will transmit a packet during the transmission cycle.


## 4.3. Theoretical Proof of Algorithm

Theorem 1.
The setLS of scheduling generated by the MSIC algorithm is feasible.Proof.
Based on the MSIC algorithm under interference regions division, each link will run the algorithm independently in each scheduling slot to generate a new feasible scheduling setLS′. From Algorithm 2, it is known that after a new set LS′ is generated in each time slot, all links l∈seql need to be tested to determine if the MSIC constraints are still satisfied. To ensure that each link in seql satisfies the MSIC constraints under the current scheduling, any link l that does not satisfy the MSIC constraints will be removed from seql. Therefore, the interference links cannot be scheduled at the same time; that is, the links in the current set LS′ are feasible, which ensures the feasibility of the algorithm.Theorem 2.
The time complexity of the MSIC algorithm isO(k2).Proof.
In the process of MSIC feasibility judgment of Algorithm1, it is necessary to judge the MSIC constraints formula (4) of any link l′∈accl∪locl and decide whether to add the link to the current scheduling set. This process requires two loop statements to be executed with the algorithm execution complexity of O(k2), where k represents the number of concurrently transmitted signals. After Algorithm 1 generates a new set LS′, the MSIC feasibility test is performed in Algorithm 2. The MSIC constraints condition needs to be tested again for all links l∈seql to ensure that any link in seql satisfies the MSIC constraints. This process also needs to execute two loop statements with the algorithm execution complexity of O(k2). Therefore, the total algorithm execution complexity is O(k2).Theorem 3.
The messages complexity of the MSIC algorithm isO(n).Proof.
The message complexity of sending a Request broadcast message isO(1). To find a set of links that can be concurrently given by a network of n links, an MSIC constraint judgment is performed for each link of l′∈{Al∪Bl}∩{accl∪locl}, and the number of Error or Success messages sent is at most n-1. For each link of k∈{{Al∪Bl}∩seql}, a feasibility test is performed, and the number of Remove or Success messages is up to n-1. When the execution of the algorithm ends, the total number of messages used is up to O(n).


## 5. Experimental Results

In this section, the distributed single-slot scheduling problem in MIMO wireless networks is studied under the SINR model. The simulation is the average of 50 trials obtained on a network with 100 links. The network size is 600∗ 600, and the distance between the sender and the receiver is selected within the range of [20,40]. The SINR parameters are set as follows: the threshold value is β=3, the path loss index is α=2.2, the background noise power is N=4×10-7, and the uniform power is P=2 and P=10.First, the relationship between the size of different networks and the number of successful transmissions of links is studied. The simulation results are shown in Figure5. Under different power allocations, the number of successful transmissions of the link increases as the network size increases, and a larger transmission power can generate a larger neighbor size, which is benefited by the gain of the transmission power. However, when the network size is large, the neighbor size reaches the upper bound, and the gain from increasing the power becomes very small. At the same time, larger power will also cause more interference to other links. At this time, the impact of the interference on transmission is greater than the benefit of the network scale increase, which makes it impossible to satisfy the SINR constraint condition, although it improves its own successful transmission probability and reduces the total size of the successful transmission of the link. Therefore, the transmission scale cannot be sought blindly by increasing the power, and a larger-scale scheduling set can be realized by controlling the network scale.Figure 5
The relationship between network size and number of successful transmissions.Next, we compare the number of concurrent link transmissions of different algorithms. At the network layer, the routing algorithm based on the least hops is adopted. For convenience, the distance, data rate, bandwidth, and transmission power of the data stream are all normalized to 1.First, the MSIC algorithm is compared with the recursive largest first (RLF) algorithm and the smallest degree first (SDF) algorithm in [20]. The results in Figure 6 show that the MSIC algorithm can obtain a larger link scheduling scale compared with the other two algorithms. After the SIC is used, all signals with high power in the interference regions can be decoded and removed firstly, and thus the interference reached at the receiver is smaller, and a larger set of concurrent links can be obtained.Figure 6
Comparison of the number of concurrent link transmissions of different algorithms.Then, we study the effect of the parameterm on the number of concurrent link transmissions. Figure 7 shows that the number of concurrent links decreases as the parameter m increases. When m is smaller, the interference radius of each link in the network is larger, and there are more links that can participate in scheduling. The number of concurrent links in each selected scheduling configuration is larger, and the data flow rate is higher. At this time, the network has stronger interference management ability. As the parameters become larger, the interference in the network is larger, thereby allowing fewer links to be transmitted concurrently. The MSIC algorithm can reduce partial interference and increase the number of concurrent transmission links. When m=0.4, there is a close interference region radius between MSIC and MIMO, so m=0.4 is set here.Figure 7
The relationship between parameter m and the number of concurrent transmissions.Next, we study the influence of the number of antennas on network performance. The number of antennas is changed from 2 to 6, and the test is repeated 100 times. We then take the average value of each flow of 100 tests. Ideally, we assume that the transmission rate of one link is equal to the capacity of the point-to-point MIMO link without other transmission interference. As shown in Figure8, throughput is nearly linear with the number of antennas, and the MSIC algorithm can achieve a higher minimum flow throughput and a higher total throughput in the network.Figure 8
The relationship between antenna number and throughput.
(a)
Minimum flow throughput (b)
Total throughputTo show more detail, the flow rate gains for the four flow sessions are given in Figure9. The simulation results show that MSIC brings significant throughput gain to MIMO wireless networks. The network flow rate with SIC functionality is more than half of the network rate without interference cancellation, which means that the reachable unit end-to-end throughput is increased by approximately 73% on average due to the application of SIC. Therefore, the MSIC algorithm has obvious advantages in improving network throughput.Figure 9
The gains of data flow rate for the four flow sessions.


## 6. Conclusions and Future Work

In this paper, the MSIC scheduling algorithm based on SIC in MIMO wireless networks is proposed. First, the MSIC constraints model is constructed under the SINR interference model. Then, interference region division is carried out to describe the level of interference between links. A feasible scheduling set is generated by the distributed link scheduling algorithm to coordinate the link transmission, and the interference between competing links in the MIMO network is cancelled. Experimental results show that the distributed MSIC scheduling algorithm can bring significant performance gain to wireless networks.Since the algorithm is premised on satisfying the threshold constraint of SINR, the algorithm ends when the SINR value is less than the current threshold. Therefore, the next research goal is how to solve the link scheduling problem when the SINR value is less than threshold.With the rapid development of the social economy, the application of modern communication technology has been continuously promoted in various fields, and the capacity requirement for networks is increasing. In addition, due to the complexity of the network environment, a single technology will not have a sufficient effect on interference cancellation. Therefore, in future wireless communication networks, a variety of joint applications of multiple interference cancellation technologies will be needed. How to combine these technologies efficiently and achieve a reasonable optimization combination is an important research direction.



---

*Source: 9083282-2019-06-19.xml*