# Heuristic Algorithms for One-Slot Link Scheduling in Wireless Sensor Networks under SINR

Authors: Hui Deng; Jiguo Yu; Dongxiao Yu; Guangshun Li; Baogui Huang
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

One-slot link scheduling is important for enhancing the throughput capacity of wireless sensor networks. It includes two aspects: maximum links scheduling (MLS) and maximum weighted links scheduling (MWLS). In this paper we propose two heuristic algorithms for the two NP-hard problems with obvious power assignments under the SINR (signal-to-interference-plus-noise-ratio) model. For MLS, we propose an algorithm MTMA (maximum tolerance and minimumaffectance), which improves the currently best approximation algorithm by 28%–62% on average. For MWLS, we give an effective heuristic algorithm MWMA (maximum weighted and minimum affectance), which performs better on improving the throughput and reducing the running time. The correctness and performance of our algorithms are confirmed through theoretical analysis and comprehensive simulations.


---

## Body

## 1. Introduction

During the past two decades, wireless networks have obtained a fast and comprehensive development due to low cost, low power, and self-organization. The application areas ranged from military to civil, enterprise to home, wide area to short distance, and so on (e.g., [1–4]). In a wireless network, a fundamental problem is how many communication links can be concurrently transmitted. This problem has attracted tremendous attention. Link scheduling determines which transmitter-receiver pairs (links) can be simultaneously activated at a given time slot. It is widely acknowledged that efficient scheduling can enhance the capacity, decrease delay, and prolong the lifetime of wireless networks. Link scheduling is one of the major performance bottlenecks in wireless multihop networks, especially after the pioneer work of Gupta and Kumar [5]. As transmissions utilize common medium in wireless communications environments, mutual interference among concurrently transmission links is an important issue. In order to characterize the interference, two models have been commonly used: one is the graph-based interference model and another is the physical interference model. The signal-to-interference-plus-noise-ratio (SINR) model reflects physical reality more accurately and is therefore often simply called the physical model. Link scheduling problem under both models has been proved to be NP-hard [6]. The choice of the interference model has a significant impact on the difficulty of developing algorithms with performances close to being optimal. For graph-based model, a node can receive a message correctly if and only if no other nodes in physical proximity transmit at the same time. However, this model has deficiency; for instance, if the power levels of the nodes are chosen properly, then a node may successfully receive a message in spite of being in the transmission range of other simultaneous transmitters. It has been recognized that graph-based interference models may be overly simplistic because they ignore the cumulative effect of wireless interference. Compared to the graph-based model, the physical interference model has been recognized as a more realistic and accurate model for interference in wireless communications. In this model, a communication is successful if and only if the ratio of the received signal to the total interference caused by all other concurrently transmitting nodes plus noise at the receiver is beyond a threshold.One-slot link scheduling includes maximum link scheduling (MLS) and maximum weighted link scheduling (MWLS), which have been proved to be NP-hard. It is possible to design heuristic algorithms with better realistic performance. Given a set of links, MLS is to compute the largest possible subset of links that can be scheduled simultaneously without interference. Given a set of links and given that each link is assigned a weight, MWLS is to find a set with maximum total weight which can be scheduled simultaneously without interference.In wireless communication networks with limited resources, efficient resource allocation (e.g., power control, link scheduling) plays an important role in achieving good performance. Resource allocation in wireless networks involves solving a joint link scheduling and power allocation problem which is very difficult in general. Due to this difficulty, most of the existing works in the literature consider a simple setting where all nodes in the network use fixed transmission power levels where the resource allocation problem degenerates into simply a link scheduling problem. There are two variants of the link scheduling under the physical interference. In link scheduling with power control, the power assignment is part of the solution. In link scheduling with fixed power assignment, the power assignment is prespecified. Typically, the prespecified power assignment is oblivious; in other words, the transmission power of the sender of each link depends only on the path loss factor of the link.In this paper, we use oblivious power assignments and the most basic oblivious assignment is uniform power, where each linkli uses the same power Pi=P. Another common oblivious assignment is linear power, where Pi=liα. The third oblivious assignment is the mean (or square-root) power, where Pi=liα/2. It is very important to choose the right power assignment.The main contributions of the problem are as follows. First, we give two effective algorithms for MLS and MWLS under the SINR model, respectively. And we prove the correctness of our algorithms through theoretical analysis. Second, we confirm the good performance of the two algorithms by comprehensive simulations. We also verify the importance of choosing the right power assignment and find out which power assignment performs better on our algorithms by simulation.The rest of the paper is organized as follows. In Section2, we briefly review related work. In Section 3, we present our system model and formally define MLS and MWLS problems. We give effective heuristic algorithms for MLS and MWLS problems in Sections 4 and 5, respectively. In Section 6, we verify the efficiency of our algorithms by simulation. Finally, we conclude this paper in Section 7.


## 2. Related Works

In this section, we only review the previous work related to the one-slot link scheduling problem. Most of the existing works in this context adopt the graph-based interference models, where transmissions on any two links in the network are assumed to be conflict or conflict-free. The inefficiency of graph-based protocols is well documented and has been shown theoretically as well as experimentally [7, 8]. These models are simple to analyze but are too simplistic, while the physical interference model (referred to as the SINR model) is considered much more realistic. And link scheduling in the SINR model is more difficult than that in graph-based models. In 2000, Gupta and Kumar first presented the physical model, analyzed the total capacity of wireless networks, and gave some upper bounds [5]. In 2006, Moscibroda and Wattenhofer presented an algorithm that successfully schedules a set of links in polylogarithmic time, even in arbitrary worst-case networks [9]. In another paper, Moscibroda et al. first defined the link scheduling problem [10].In [6], Goussevskaia et al. proved MLS problem is NP-hard and presented an O(g(L))-approximations algorithm when the noise is 0, where g(L) denotes the number of nonempty length classes of the set of links to be scheduled. This result has been improved to a constant factor approximation algorithm for uniform power assignments [11–13]. With uniform power assignment, Wan et al. [12] and Halldorsson and Wattenhofer [13] obtained independently constant approximation algorithms for maximum link scheduling, the former of which having better approximation bound. In [14], Halldórsson gave an algorithm with an approximation ratio of O(log⁡⁡n·log⁡⁡log⁡⁡Δ), where n is the number of links and Δ is the ratio of length between the longest and the shortest links. Under the natural assumption that lengths were represented in binary, this gave the first approximation ratio that was polylogarithmic in the size of the input. The algorithm has the desirable property of using an oblivious power assignment, where the power assigned to a sender depends only on the length of the link. In [15], Pei and Vullikanti found that different aspects of available technology, such as full/half-duplex communication and nonadaptive/adaptive power control, have a significant impact on the performance of the algorithm. These issues have not been explored in the context of distributed algorithms in the SINR model before. They also provided a constant approximation for the MLS problem under uniform power assignment; the running time is O(g(L)log⁡c⁡m), where c=1, 2, and 3 for different problem instances and m is the number of links. In [16], Dams et al. studied algorithms for MLS problem under the Rayleigh-fading model. The main result is a generic reduction from Rayleigh fading to the deterministic SINR model, which allows us to apply the existing algorithms for the nonfading model into the Rayleigh-fading scenario while losing only a factor of O(log⁡∗⁡n) in the approximation guarantee.In [17], Xu and Tang proposed a maximum weighted link scheduling algorithm with approximation ratio of O(min⁡⁡(log⁡⁡max⁡l∈L⁡wl/min⁡l∈Lwl,log⁡⁡(max⁡l∈L∥l∥/min⁡l∈L∥L∥))), where ∥l∥ is the length of link l and w(l) is the weight of link l. Another attempt was made by Andrews and Dinitz, who proposed an approximation algorithm with approximation ratio of O(log⁡⁡dmax⁡) for MWLS [18], where dmax⁡ denotes the number of nonempty length classes of the set of links. They studied the complexity of the problem and present some game theoretic results regarding capacity. They also showed that maximizing the number of supported connections is NP-hard, even though there is no background noise. In [19], Wan et al. built a unified framework to develop approximation algorithms for MWLS problem. Assuming that MLS has a polynomial μ-algorithm, then we can get a polynomial e(1+ln⁡⁡α)μ-approximation for MWLS algorithm, where α is the number of maximum independent sets of links and e is the natural base. In [20], Wang et al. designed a new approximation algorithm for MWLS with constant approximation bound regardless of the value of the ambient noise, when the ratio of the maximum power level to the minimum power level or the number of power levels is bounded by a constant. In [21], Lam et al. presented a constant approximation algorithm for MWLS with power control under the SINR model.The relation between scheduling using oblivious power and scheduling using arbitrary power was first studied in [22]. The works of Halldórsson [22] and Kesselheim and Vöcking [23] are particularly relevant: the first in the context of oblivious-arbitrary comparison and the second in the context of oblivious power. In [24], Halldórsson and Mitra studied how well oblivious power assignments can handle the power control problem and provide tight characterization (upper and lower bounds) for certain cases. They also proved that the mean power assignment is optimal for capacity maximization of bidirectional links. However, they assumed that the ambient noise N is neglected. In our paper, we study the scheduling problem with oblivious power assignments and take the noise into consideration.


## 3. Model and Definition

Given a setL={l1,l2,…,ln} of links, a set W={w(l1),w(l2),w(l3),…,w(ln)} expresses their weights. Link li represents a communication request from a sender si to a receiver ri. The Euclidean distance between two nodes i and j is denoted by di,j. The asymmetric distance from link li to link lj is the distance from the sender of li and the receiver of lj, denoted by dij=dsi,rj. The length of link li is denoted simply by li; that is, li=li=dii. Assume that each link has a unit-traffic demand, and the case of nonunit traffic demands can be modeled by replicating the links.Choosing an appropriate interference model is crucial when studying scheduling problem in wireless networks. We use the standard signal-to-interference-plus-noise-ratio (SINR) model, where a message can be transmitted successfully depending on the ratio of the received signal strength and the sum of the interference caused by nodes sending simultaneously plus noise level.Assume that the nodes can transmit with different power. LetPi denote the power assigned to sender si. We use the path loss radio propagation model for the reception of signals, where the signal received from sj at receiver ri is Iji=Pj/djiα and α denotes the path loss exponent (2≤α≤6). Under the SINR model, a node ri successfully receives a message from a sender si if and only if the following condition holds:(1)Pi/liα∑lj∈S∖{li}‍Pj/djiα+N≥β,where N is the ambient noise, β denotes the minimum SINR threshold required for a message to be successfully received, and S is the set of concurrently scheduled links in the same slot. We say that S is SINR-feasible if (1) is satisfied for every link in S. This model captures important aspects of real wireless networks and it is at the same time succinct enough to allow a concise performance analysis.Next we formally define the MLS problem and MWLS problem.MLS Problem. Given a set L={l1,l2,…,ln} of links, compute a set S⊆L to be SINR-feasible, and seek the largest possible subset S of L that can be scheduled simultaneously.MWLS Problem. Given a set L={l1,l2,…,ln} of links, where each link li is assigned a weight w(li), find a set Lw⊆L with maximum total weight W(Lw)=∑li∈Lww(li)  which can be scheduled simultaneously without interference.The notion ofaffectance was introduced in [11] and refined in [24], which has many technical advantages. TheaffectanceajP(i) of link li caused by another link lj is the interference of lj on li relative to the received power; that is,(2)ajPi=ciPj/djiαPi/liα=ciPjPilidjiα,where ci=β/(1-βNliα/Pi) is a constant depending only on the length and power of the link li. For a set S of links and a link li, let aSP(i)=∑j∈S‍ajP(i) and aiP(S)=∑j∈s‍aiP(j). Using this notation, (1) can be rewritten as aSP(i)≤1, and this is the form we will use. This transforms the relatively complicated formula (1) into an inequality involving a simple sum that can be operated more easily.Thetoleranceφit of a link li indicates how much interference the link can endure before the SINR falls below the threshold β. It can be calculated by(3)φit=P/diiαβ-N.Theresidual toleranceφir of a link li indicates, when li is scheduled in Lw, how much more interference the link li can endure before the SINR falls below the threshold β. It can be calculated by(4)φir=φit-∑lj∈Lw‍Iji.A linkli is feasible with respect to a set S of links if, after the addition of li to the link set, condition (1) is satisfied for all links lj∈S∪{li}.


## 4. Maximum Tolerance and MinimumAffectance Based MLS Algorithm

In this section, we give an effective heuristic algorithm to solve the MLS problem under the SINR model, which can achieve significantly better results in practice. Our proposed algorithm MTMA (maximum tolerance and minimumaffectance) is an improved version of MTIR (maximum tolerance-to-interference-ratio) given by Yang et al. [25].The basic idea of MTMA is as follows. Firstly, we add a link with maximum link tolerance into the time-slot and update the residual tolerance of other links. Then we greedily schedule a feasible link with minimumaiP(S). This process is repeated until every link is either removed or scheduled. Obviously, the most important step is to schedule a feasible link with minimumaffectance. The pseudocodes for MTMA are given in Algorithm 1.Algorithm 1:Maximum tolerance and minimum affectance based MLS algorithm (MTMA).
Input:  A set of links L={l1,l2,…,li,…,ln} located arbitrarily in the Euclidean plane
Output:  A set of links S⊆L that can transmit simultaneously
(1)S=∅;
(2) Computeφit for each li∈L and set φir=φit;
(3) Select a linkli with maximum φit;
(4)S=S⋃‍{li}; L=L∖{li};
(5)for  lj∈L  do
(6)φjr=φjr-Iij;
(7)if  φjr<0  then
(8)L=L∖{lj}
(9)end if
(10)end for
(11)while  L≠∅  do
(12)  Select a feasible linkli with minimum aiP(S);
(13)S=S⋃‍{li}; L=L∖{li}
(14)for  each lj∈S  do
(15)φjr=φjr-Iij
(16)end for
(17)for each lj∈L  do
(18)φjr=φjr-Iij
(19)if  φjr<0  then
(20)L=L∖{lj}
(21)end if
(22)end for
(23)end while
(24)return  SThe key of MTMA is to choose the link with minimumaiP(S) to schedule. From the definition of theaffectance, we know that when we choose the new link to schedule, the smaller value of theaffectance is better. Choosing the link with minimumaffectance is more advantageous for scheduling more links simultaneously; aiP(S) helps us choose the optimal link. Can the links in set S be scheduled simultaneously? Is it feasible to schedule the links? These problems all depend on theaffectance, because theaffectance transforms from the formula of the SINR model.Next, we prove the correctness and the time complexity of Algorithm1.Theorem 1.
MTMA can compute a feasible link set with time complexity ofO(n2), where n is the number of links in L.Proof.
The feasibility of each link inS can be directly guaranteed by Lines 5–10, Line 12, and Lines 17–22. In those steps we check whether the selected links constitute a feasible schedule by making the links update the residual tolerance of other links. The definition of residual tolerance transforms from the formula of the SINR model. If residual tolerance of unscheduled links drops below 0, we remove it from L, because it does not satisfy the SINR constraints. Hence, we can obtain a feasible link set at last. Next we analyze the time complexity of MTMA. Line 2 takes O(n) time to initialize the tolerance for each link. It then takes O(n) time to pick a link in Line 3 and update the residual tolerance for other links. Obviously, the while-loop is executed at most n times. For each execution of the while-loop, it takes O(n) time to pick the feasible link li and update the residual tolerance for each link in S and each unscheduled link. Therefore, the time complexity of Algorithm 1 is On+n2=On2.


## 5. Maximum Weighted and MinimumAffectance Based MWLS Algorithm

In this selection, we propose effective heuristic algorithms with good performances for MWLS. It is easy to know that the key step of the algorithm is to greedily select an appropriate link to schedule. When we choose the links, if we take maximum weight into consideration only, a set of links may not satisfy the feasible link condition since link tolerance is too small. If we consider link tolerance andaffectance only, it is meaningless for solving MWLS problem. In order to choose the optimal links, we combine the maximum weighted link tolerance and minimumaffectance into consideration. The pseudocodes for MWMA are provided in Algorithm 2.Algorithm 2:Maximum weighted and minimum affectance based MWLS algorithm (MWMA).
Input: A set of links L={l1,l2,…,li,…,ln} with the corresponding weight
W={w(l1),w(l2),…,w(li),…,w(ln)}
Output: A subset of links in which all links Lw can transmit successfully.
(1)Lw=ϕ; flag=0
(2) For each linkli∈L, compute φit and set φir=φit;
(3) Select a linkli with maximum φit·wi;
(4)Lw=Lw∪{li}; L=L∖{li};
(5)for  lj∈L  do
(6)φjr=φjr-Iij;
(7)if  φjr<0  then
(8)L=L∖{lj}
(9)end if
(10)end for
(11)while  L≠∅  do
(12)flag=0;
(13)Select a feasible link li with maximum φir·wi/aiP(Lw);
(14)for each lj∈Lw  do
(15)if  φir-Iij<0  then
(16)L=L∖{li}; flag=1
(17)break;
(18)end if
(19)end for
(20)if  flag==0  then
(21)Lw=Lw∪{li}; L=L∖{li}
(22)for each lj∈Lw  do
(23)φjr=φjr-Iij
(24)end for
(25)for each lj∈L  do
(26)φjr=φjr-Iij
(27)if  φjr<0  then
(28)L=L∖{lj}
(29)end if
(30)end for
(31)end if
(32)end while
(33)return a feasible link set Lw.The basic idea of Algorithm2 is as follows: we first compute the φit of all links and initialize the tolerance φir for each link; then we add a link with maximum φir·wi into the time-slot (Lines 3-4) and update the residual tolerance of other links (Lines 5–10). If the residual tolerance of unscheduled link drops below 0, we remove it from L (Lines 7-8). We greedily schedule a feasible link with maximum ratio φir·wi/aiP(Lw). We try to balance the maximum weighted and minimumaffectance so that we can choose the optimal links. For lj∈Lw compute φjr-Iij. If φjr-Iij<0, we set flag=1, which implies that the link fails to be chosen. Then we remove li from L and stop the for-loop. If flag=0 we know we are successful in choosing the link and then we add li into Lw and update Lw, L (Lines 20–31). This process is repeated until every link is either removed or scheduled. Finally, the algorithm returns a feasible link set Lw.  It is better to choose a new link with a small value ofaffectance. Therefore, we useaffectanceaiP(S) to help us choose the optimal link.Theorem 2.
All links inLw can be scheduled successfully; that is, the links satisfy the SINR constraints.Proof.
LetLi⊂⊆Lw denote the links before link li adding to Lw. Li⊃⊆Lw denotes the links after li adding to Lw. That is, Li⊂∪{li}∪Li⊃=Lw. For an arbitrary link li∈Lw, before link li adding to Lw, li endures the interference caused by Lw which is ∑lj∈Li⊂‍Iji; then the residual tolerance of li is(5)φir′=φir-∑lj∈Li⊂‍Iji.
After the joining ofli to the link set, if there still are links to add to Lw, then link tolerance of li is ∑lk∈Li⊃‍Iki. When the algorithm ends, the residual tolerance of li is(6)φir′′=φir′-∑lk∈Li⊃‍Iki.
The residual tolerance ofli is greater than 0 that can be guaranteed by Lines 5–10 and Lines 25–30; that is, (5) is greater than 0. Our algorithm can satisfy (6) that can be guaranteed by Line 12 and Lines 15–18. So we can get(7)φir-∑lj∈Li⊂‍Iji+∑lk∈Li⊃‍Iki≥0.
From (1), then(8)P/diiαN+∑lj∈Lw∖{lj}Iji≥β.
Therefore all links inLw satisfy the SINR constraints.Theorem 3.
The time complexity of MWMA isO(n2), where n is the number of links in n.Proof .
MWMA takesO(n) time to select a link in Line 3 and update the set L (Lines 5–10). Obviously, the while-loop is executed at most n times. For each execution of the while-loop, it takes O(n) time to select the feasible link (Line 13) and update the sets L and Lw. Therefore, the time complexity of MWMN is O(n+n+n2)=O(n2).


## 6. Numerical Results

In this section, we evaluate the performance of our algorithms by comparing them with existing algorithms. For the maximum links scheduling problem, we implemented Algorithm1 (denoted by MTMA) under the uniform power assignment and compared it with algorithms in [5, 12, 25] (denoted by GSINR-OS, MISL-OS, and MTIR, resp.). We also implemented Algorithm 1 with three different obvious power assignments. For maximum weighted links scheduling problem, we implemented Algorithm 2 (denoted by MWMA) with three different obvious power assignments and compared it with algorithm in [19] (denoted by PMWSL).It is easy to know that the length of link would affect the performance, because we focus on oblivious power assignments, where the received signal strength depends on the length of link. In the SINR model, a message can be transmitted successfully depending on the ratio of the received signal strength and the sum of the interference caused by nodes sending simultaneously plus noise level. Hence, the propagation distance, one-hop transmission range, distribution of nodes, and nodes density can affect the performance of the algorithms. As in [25], we uniformly distributed links in a 1000 × 1000 square region. The length of each link is randomly chosen between 1 and 30. The number of nodes (twice the number of links) was chosen to be 500,2000,…,5000. For each value of numbers of nodes, we run simulation 20 times and average the results. The SINR threshold β was set to 16, the environment noise N=10-9w, the path loss exponent α=4, and transmit power Pi=0.2w. In addition, the links in the maximum links scheduled by GSINR-OS may be infeasible, since the algorithm requires the environment noise to be 0, which is not a fair assumption [12]. Thus the results shown in Figures 1(a) and 1(b) can be considered as the upper bounds of the feasible schedule obtained by GSINR-OS.Figure 1
Performance comparison of MLS algorithms.
(a)
Comparison of number of links
(b)
Comparison of running times
(c)
Comparison under different power assignmentsFigures1(a) and 1(b) show the average number of links scheduled by MTIR, MISL-OS, GSINR-OS, and MTMA and the corresponding average running times with the increase in the density of nodes. We observe that MTMA schedules more links in one slot than MTIR, MISL-OS, and GSINR-OS by 28%–62%, 103%–122%, and 912%–995%, respectively. Moreover, our algorithm performs better along with the number of links increasing. As shown in Figure 1(b), GSINR-OS runs very fast since it is a linear time algorithm. Surprisingly, MISL-OS with a theoretical time complexity of O(n2) also runs very fast. The reason is that it can abandon a large number of links after each iteration, which may significantly reduce the number of links to be checked in the next iterations. Although MTMA and MTIR take more time than GSINR-OS and MISL-OS, for a network with even 5,000 nodes, it can finish scheduling within 3 seconds. Considering the significant improvement on the number of links in one time slot, the sacrificed running time is worthwhile. Figure 1(c) shows the influence of the three different oblivious power assignments for MTMA, we can observe that the mean power assignment is just a little better than uniform power assignment, and choosing powers proportional to the linear of the path loss is the best alternative for our algorithm.Figures2(a) and 2(b) show the total weight of links scheduled by MWMA and PWMSL and the corresponding average running times with the increase in the density of nodes. From Figure 2(a), we observe that the total weight obtained by MWMA is almost twice as many as the corresponding schedule weight computed by PWMSL. This is what we expected, since more accurate information is used by MWMA for selecting the next link. We take maximum weighted and minimum interference into account and MWMA can find a better feasible set to schedule. From Figure 2(b), we can see our algorithm takes less time than PWMSL. Hence. MWMA performs better on both improving the throughput and reducing the running time. Figure 2(c) shows the influence of the three different oblivious power assignments for MWMA; our Algorithm 2 performs better with the linear power assignment than mean power assignment and uniform power assignment. Hence, linear power assignment is the best alternative for our algorithm.Figure 2
Performance comparison of MWLS algorithms.
(a)
Comparison of number of links
(b)
Comparison of running times
(c)
Comparison under different power assignments


## 7. Conclusion

In this paper, we study the link scheduling problem with oblivious power assignment and propose two algorithms for one-slot link scheduling. For the maximum links scheduling problem, we designed an effective heuristic algorithm MTMA, which improves the currently best approximation algorithm by 28%–62% on average. For maximum weighted links scheduling problem, we designed an effective heuristic algorithm MWMA, which performs better on improving throughput and reducing the running time. As a following work, we will study scheduling problem under other interference models such as various fading models and explore distributed SINR based scheduling algorithm for wireless networks.



---

*Source: 806520-2015-03-30.xml*