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

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 minimum affectance), 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.

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 link $l_{i}$ uses the same power $P_{i} = P$ . Another common oblivious assignment is linear power, where $P_{i} = l_{i}^{α}$ . The third oblivious assignment is the mean (or square-root) power, where $P_{i} = l_{i}^{α / 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 Section 2, 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 \cdot \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 \in L} w (l) / \min_{l \in L} w (l)), \log (\max_{l \in L} ∥ l ∥ / \min_{l \in 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 d_{\max})$ for MWLS [18], where $d_{\max}$ 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 set $L = {l_{1}, l_{2}, \dots, l_{n}}$ of links, a set $W = {w (l_{1}), w (l_{2}), w (l_{3}), \dots, w (l_{n})}$ expresses their weights. Link $l_{i}$ represents a communication request from a sender $s_{i}$ to a receiver $r_{i}$ . The Euclidean distance between two nodes i and j is denoted by $d (i, j)$ . The asymmetric distance from link $l_{i}$ to link $l_{j}$ is the distance from the sender of $l_{i}$ and the receiver of $l_{j}$ , denoted by $d_{i j} = d (s_{i}, r_{j})$ . The length of link $l_{i}$ is denoted simply by $l_{i}$ ; that is, $l_{i} = ‖l_{i}‖ = d_{i i}$ . 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. Let $P_{i}$ denote the power assigned to sender $s_{i}$ . We use the path loss radio propagation model for the reception of signals, where the signal received from $s_{j}$ at receiver $r_{i}$ is $I_{j i} = P_{j} / d_{j i}^{α}$ and α denotes the path loss exponent ( $2 \leq α \leq 6$ ). Under the SINR model, a node $r_{i}$ successfully receives a message from a sender $s_{i}$ if and only if the following condition holds:

\begin{matrix} \frac{P_{i} / l_{i}^{α}}{\sum_{l_{j} \in S ∖ {l_{i}}} ‍ P_{j} / d_{j i}^{α} + N} \geq β, \end{matrix}

(1)

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 = {l_{1}, l_{2}, \dots, l_{n}}$ of links, compute a set $S \subseteq 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 = {l_{1}, l_{2}, \dots, l_{n}}$ of links, where each link $l_{i}$ is assigned a weight $w (l_{i})$ , find a set $L^{w} \subseteq L$ with maximum total weight $W (L^{w}) = \sum_{l_{i} \in L^{w}}^{} w (l_{i})$ which can be scheduled simultaneously without interference.

The notion of affectance was introduced in [11] and refined in [24], which has many technical advantages. The affectance $a_{j}^{P} (i)$ of link $l_{i}$ caused by another link $l_{j}$ is the interference of $l_{j}$ on $l_{i}$ relative to the received power; that is,

\begin{matrix} a_{j}^{P} (i) = c_{i} \frac{P_{j} / d_{j i}^{α}}{P_{i} / l_{i}^{α}} = c_{i} \frac{P_{j}}{P_{i}} {(\frac{l_{i}}{d_{j i}})}^{α}, \end{matrix}

(2)

where $c_{i} = β / (1 - β N l_{i}^{α} / P_{i})$ is a constant depending only on the length and power of the link $l_{i}$ . For a set S of links and a link $l_{i}$ , let $a_{S}^{P} (i) = \sum_{j \in S} ‍ a_{j}^{P} (i)$ and $a_{i}^{P} (S) = \sum_{j \in s} ‍ a_{i}^{P} (j)$ . Using this notation, (1) can be rewritten as $a_{S}^{P} (i) \leq 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.

The tolerance $φ_{i}^{t}$ of a link $l_{i}$ indicates how much interference the link can endure before the SINR falls below the threshold $β$ . It can be calculated by

\begin{matrix} φ_{i}^{t} = \frac{P / d_{i i}^{α}}{β} - N . \end{matrix}

(3)

The residual tolerance $φ_{i}^{r}$ of a link $l_{i}$ indicates, when $l_{i}$ is scheduled in $L^{w}$ , how much more interference the link $l_{i}$ can endure before the SINR falls below the threshold $β$ . It can be calculated by

\begin{matrix} φ_{i}^{r} = φ_{i}^{t} - \sum_{l_{j} \in L^{w}} ‍ I_{j i} . \end{matrix}

(4)

A link $l_{i}$ is feasible with respect to a set S of links if, after the addition of $l_{i}$ to the link set, condition (1) is satisfied for all links $l_{j} \in S \cup {l_{i}}$ .

4. Maximum Tolerance and Minimum Affectance 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 minimum affectance) 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 minimum $a_{i}^{P} (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 minimum affectance. The pseudocodes for MTMA are given in Algorithm 1.

Algorithm 1: Maximum tolerance and minimum $a f f e c t a n c e$ based MLS algorithm (MTMA).

Input:A set of links $L = {l_{1}, l_{2}, \dots, l_{i}, \dots, l_{n}}$ located arbitrarily in the Euclidean plane

Output:A set of links $S \subseteq L$ that can transmit simultaneously

(1) $S = \emptyset$ ;

(2) Compute $φ_{_{i}}^{t}$ for each $l_{i} \in L$ and set $φ_{i}^{r} = φ_{_{i}}^{t}$ ;

(3) Select a link $l_{i}$ with maximum $φ_{_{i}}^{t}$ ;

(4) $S = S ⋃_{} ‍ {l_{i}}$ ; $L = L$ ∖ ${l_{i}}$ ;

(5) for $l_{j} \in L$ do

(6) $φ_{j}^{r} = φ_{j}^{r} - I_{i j}$ ;

(7) if $φ_{j}^{r} < 0$ then

(8) $L = L$ ∖ ${l_{j}}$

(9) end if

(10) end for

(11) while $L \neq \emptyset$ do

(12) Select a feasible link $l_{i}$ with minimum $a_{i}^{P} (S)$ ;

(13) $S = S ⋃_{} ‍ {l_{i}}$ ; $L = L$ ∖ ${l_{i}}$

(14) for each $l_{j} \in S$ do

(15) $φ_{j}^{r} = φ_{j}^{r} - I_{i j}$

(16) end for

(17) for each $l_{j} \in L$ do

(18) $φ_{j}^{r} = φ_{j}^{r} - I_{i j}$

(19) if $φ_{j}^{r} < 0$ then

(20) $L = L$ ∖ ${l_{j}}$

(21) end if

(22) end for

(23) end while

(24) return S

The key of MTMA is to choose the link with minimum $a_{i}^{P} (S)$ to schedule. From the definition of the affectance, we know that when we choose the new link to schedule, the smaller value of the affectance is better. Choosing the link with minimum affectance is more advantageous for scheduling more links simultaneously; $a_{i}^{P} (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 the affectance, because the affectance transforms from the formula of the SINR model.

Next, we prove the correctness and the time complexity of Algorithm 1.

Theorem 1.

MTMA can compute a feasible link set with time complexity of $O (n^{2})$ , where n is the number of links in L.

Proof.

The feasibility of each link in S 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 $l_{i}$ and update the residual tolerance for each link in S and each unscheduled link. Therefore, the time complexity of Algorithm 1 is $O (n + n^{2}) = O (n^{2})$ .

5. Maximum Weighted and Minimum Affectance 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 and affectance only, it is meaningless for solving MWLS problem. In order to choose the optimal links, we combine the maximum weighted link tolerance and minimum affectance into consideration. The pseudocodes for MWMA are provided in Algorithm 2.

Algorithm 2: Maximum weighted and minimum $a f f e c t a n c e$ based MWLS algorithm (MWMA).

Input: A set of links $L = {l_{1}, l_{2}, \dots, l_{i}, \dots, l_{n}}$ with the corresponding weight

$W = {w (l_{1}), w (l_{2}), \dots, w (l_{i}), \dots, w (l_{n})}$

Output: A subset of links in which all links $L^{w}$ can transmit successfully.

(1) $L^{w} = ϕ$ ; $flag = 0$

(2) For each link $l_{i} \in L$ , compute $φ_{i}^{t}$ and set $φ_{i}^{r} = φ_{i}^{t}$ ;

(3) Select a link $l_{i}$ with maximum $φ_{i}^{t} \cdot w_{i}$ ;

(4) $L^{w} = L^{w} \cup {l_{i}}$ ; $L = L$ ∖ ${l_{i}}$ ;

(5) for $l_{j} \in L$ do

(6) $φ_{j}^{r} = φ_{j}^{r} - I_{i j}$ ;

(7) if $φ_{j}^{r} < 0$ then

(8) $L = L$ ∖ ${l_{j}}$

(9) end if

(10) end for

(11) while $L \neq \emptyset$ do

(12) $flag = 0$ ;

(13) Select a feasible link $l_{i}$ with maximum $φ_{i}^{r} \cdot w_{i} / a_{i}^{P} (L^{w})$ ;

(14) for each $l_{j} \in L^{w}$ do

(15) if $φ_{i}^{r} - I_{i j} < 0$ then

(16) $L = L$ ∖ ${l_{i}}$ ; $flag = 1$

(17) break;

(18) end if

(19) end for

(20) if $flag = = 0$ then

(21) $L^{w} = L^{w} \cup {l_{i}}$ ; $L = L$ ∖ ${l_{i}}$

(22) for each $l_{j} \in L^{w}$ do

(23) $φ_{j}^{r} = φ_{j}^{r} - I_{i j}$

(24) end for

(25) for each $l_{j} \in L$ do

(26) $φ_{j}^{r} = φ_{j}^{r} - I_{i j}$

(27) if $φ_{j}^{r} < 0$ then

(28) $L = L$ ∖ ${l_{j}}$

(29) end if

(30) end for

(31) end if

(32) end while

(33) return a feasible link set $L^{w}$ .

The basic idea of Algorithm 2 is as follows: we first compute the $φ_{i}^{t}$ of all links and initialize the tolerance $φ_{i}^{r}$ for each link; then we add a link with maximum $φ_{i}^{r} \cdot w_{i}$ 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 $φ_{i}^{r} \cdot w_{i} / a_{i}^{P} (L^{w})$ . We try to balance the maximum weighted and minimum affectance so that we can choose the optimal links. For $l_{j} \in L^{w}$ compute $φ_{j}^{r} - I_{i j}$ . If $φ_{j}^{r} - I_{i j} < 0$ , we set $flag = 1$ , which implies that the link fails to be chosen. Then we remove $l_{i}$ from L and stop the for-loop. If $flag = 0$ we know we are successful in choosing the link and then we add $l_{i}$ into $L^{w}$ and update $L^{w}$ , L (Lines 20–31). This process is repeated until every link is either removed or scheduled. Finally, the algorithm returns a feasible link set $L^{w}$ . It is better to choose a new link with a small value of affectance. Therefore, we use affectance $a_{i}^{P} (S)$ to help us choose the optimal link.

Theorem 2.

All links in $L^{w}$ can be scheduled successfully; that is, the links satisfy the SINR constraints.

Proof.

Let $L_{i}^{\subset} \subseteq L^{w}$ denote the links before link $l_{i}$ adding to $L^{w}$ . $L_{i}^{\supset} \subseteq L^{w}$ denotes the links after $l_{i}$ adding to $L^{w}$ . That is, $L_{i}^{\subset} \cup {l_{i}} \cup L_{i}^{\supset} = L^{w}$ . For an arbitrary link $l_{i} \in L^{w}$ , before link $l_{i}$ adding to $L^{w}$ , $l_{i}$ endures the interference caused by $L^{w}$ which is $\sum_{l_{j} \in L_{i}^{\subset}} ‍ I_{j i}$ ; then the residual tolerance of $l_{i}$ is

\begin{matrix} {(φ_{i}^{r})}^{'} = φ_{i}^{r} - \sum_{l_{j} \in L_{i}^{\subset}} ‍ I_{j i} . \end{matrix}

(5)

After the joining of $l_{i}$ to the link set, if there still are links to add to $L^{w}$ , then link tolerance of $l_{i}$ is $\sum_{l_{k} \in L_{i}^{\supset}} ‍ I_{k i}$ . When the algorithm ends, the residual tolerance of $l_{i}$ is

\begin{matrix} {(φ_{i}^{r})}^{′′} = {(φ_{i}^{r})}^{'} - \sum_{l_{k} \in L_{i}^{\supset}} ‍ I_{k i} . \end{matrix}

(6)

The residual tolerance of $l_{i}$ 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

\begin{matrix} φ_{i}^{r} - (\sum_{l_{j} \in L_{i}^{\subset}} ‍ I_{j i} + \sum_{l_{k} \in L_{i}^{\supset}} ‍ I_{k i}) \geq 0 . \end{matrix}

(7)

From (1), then

\begin{matrix} \frac{P / d_{i i}^{α}}{N + \sum_{l_{j} \in L^{w} ∖ {l_{j}}}^{} I_{j i}} \geq β . \end{matrix}

(8)

Therefore all links in $L^{w}$ satisfy the SINR constraints.

Theorem 3.

The time complexity of MWMA is $O (n^{2})$ , where n is the number of links in n.

Proof .

MWMA takes $O (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 $L^{w}$ . Therefore, the time complexity of MWMN is $O (n + n + n^{2}) = O (n^{2})$ .

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 Algorithm 1 (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, \dots, 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 = 1 0^{- 9} w$ , the path loss exponent $α = 4$ , and transmit power $P_{i} = 0.2 w$ . 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.

Figures 1(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 (n^{2})$ 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.

Figures 2(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.

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.

Footnotes

Conflict of Interests

The authors declare that they do not have any conflict of interests.

Acknowledgments

This work is partially supported by the NNSF of China for Contract 61373027 and NSF of Shandong Province for Contract ZR2012FM023.

References

Sendra

Bri

Granell

E. G.

Lloret

IEEE 802.11g radio coverage study for indoor wireless network redesign

International Journal On Advances in Intelligent Systems 2012 5 4 518 532

Sendra

Lloret

Turró

Aguiar

J. M.

IEEE 802.11a/b/g/n short-scale indoor wireless sensor placement

International Journal of Ad Hoc and Ubiquitous Computing 2014 15 1–3 68 82

10.1504/ijahuc.2014.059901

Wan

P.-J.

Jia

Dai

Frieder

Fast and simple approximation algorithms for maximum weighted independent set of links

Proceedings of the IEEE International Conference on Computer Communications (INFOCOM '14)

April 2014

Toronto, Canada

1653 1661

10.1109/infocom.2014.6848102

Zhou

Liu

Mao

Tang

Throughput optimizing localized link scheduling for multihop wireless networks under physical interference model

IEEE Transactions on Parallel and Distributed Systems 2014 25 10 2708 2720

10.1109/tpds.2013.210

Gupta

Kumar

P. R.

The capacity of wireless networks

IEEE Transactions on Information Theory 2000 46 2 388 404

10.1109/18.825799

MR1748976

2-s2.0-33747142749

Goussevskaia

Oswald

Y. A.

Wattenhofer

Complexity in geometric SINR

Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '07)

September 2007

100 109

2-s2.0-37849036026

10.1145/1288107.1288122

Moscibroda

Wattenhofer

Weber

Protocol design beyond graph-based models

Proceedings of the ACM Workshop on Hot Topics in Networks (HotNets '06)

2006

25 30

Grönkvist

Hansson

Comparison between graph-based and interference-based STDMA scheduling

Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '01)

October 2001

255 258

2-s2.0-0035789902

Moscibroda

Wattenhofer

The complexity of connectivity in wireless networks

Proceedings of the Conference on Computer Communications (INFOCOM '06)

April 2006

10.

Moscibroda

Wattenhofer

Zollinger

Topology control meets SINR: the scheduling complexity of arbitrary topologies

Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC '06)

May 2006

Florence, Italy

310 321

2-s2.0-33748084040

10.1145/1132905.1132939

11.

Goussevskaia

Wattenhofer

Halldrsson

M. M.

Welzl

Capacity of arbitrary wireless networks

Proceedings of the IEEE INFOCOM

2009

1872 1880

12.

Wan

Jia

Yao

Maximum independent set of links under physical interference model

Proceedings of the 5th International Conference on Wireless Algorithms, Systems, and Applications (WASA '09)

August 2009

Beijing, China

169 178

13.

Halldorsson

M. M.

Wattenhofer

Wireless communication is in APX

Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP '09)

2009

525 536

10.1007/978-3-642-02927-1_44

14.

Halldórsson

M. M.

Wireless scheduling with power control

ACM Transactions on Algorithms (TALG) 2012 9 1

10.1145/2390176.2390183

MR3008302

15.

Pei

Vullikanti

A. K. S.

Efficient algorithms for maximum link scheduling in distributed computing models with SINR constraints

http://arxiv.org/abs/1208.0811

16.

Dams

Hoefer

Kesselheim

Scheduling in wireless networks with Rayleigh-fading interference

Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '12)

June 2012

ACM

327 335

2-s2.0-84864122195

10.1145/2312005.2312061

17.

Tang

A constant approximation algorithm for link scheduling in arbitrary networks under physical interference model

Proceedings of the 2nd ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing (FOWANC '09)

2009

13 20

18.

Andrews

Dinitz

Maximizing capacity in arbitrary wireless networks in the SINR model: complexity and game theory

Proceedings of the IEEE INFOCOM

April 2009

1332 1340

2-s2.0-70349689930

10.1109/infcom.2009.5062048

19.

Wan

P.-J.

Frieder

Jia

Yao

Tang

Wireless link scheduling under physical interference model

Proceedings of the IEEE INFOCOM

April 2011

838 845

10.1109/infcom.2011.5935307

2-s2.0-79960857901

20.

Wang

Abubucker

C. P.

Lawless

W. F.

Baker

A. J.

A constant-approximation for maximum weight independent set of links under the SINR model

Proceedings of the 7th International Conference on Mobile Ad-hoc and Sensor Networks (MSN '11)

December 2011

9 14

10.1109/msn.2011.1

2-s2.0-84862960065

21.

Lam

N. X.

M. K.

Huynh

D. T.

Nguyen

T. N.

Scheduling problems in interference-aware wireless sensor networks

Proceedings of the International Conference on Computing, Networking and Communications (ICNC '13)

January 2013

783 789

10.1109/iccnc.2013.6504188

2-s2.0-84877626080

22.

Halldórsson

M. M.

Wireless scheduling with power control

Algorithms—ESA 2009 2009 5757

Berlin, Germany

Springer

361 372 Lecture Notes in Computer Science

10.1007/978-3-642-04128-0_33

MR2557766

23.

Kesselheim

Vöcking

Distributed contention resolution in wireless networks

Distributed Computing: Proceedings of the 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13–15, 2010 2010 6343

Berlin, Germany

Springer

163 178 Lecture Notes in Computer Science

10.1007/978-3-642-15763-9_16

24.

Halldórsson

M. M.

Mitra

Wireless capacity with oblivious power in general metrics

Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '11) 2011 1538 1548

25.

Yang

Fang

Xue

Irani

Misra

Simple and effective scheduling in wireless networks under the physical interference model

Proceedings of the 53rd IEEE Global Communications Conference (GLOBECOM '10)

December 2010

1 5

10.1109/glocom.2010.5683486

2-s2.0-79551626341

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

Abstract

1. Introduction

2. Related Works

3. Model and Definition

4. Maximum Tolerance and Minimum Affectance Based MLS Algorithm

Algorithm 1: Maximum tolerance and minimum a f f e c t a n c e based MLS algorithm (MTMA).

Theorem 1.

Proof.

5. Maximum Weighted and Minimum Affectance Based MWLS Algorithm

Algorithm 2: Maximum weighted and minimum a f f e c t a n c e based MWLS algorithm (MWMA).

Theorem 2.

Proof.

Theorem 3.

Proof .

6. Numerical Results

7. Conclusion

Footnotes

Conflict of Interests

Acknowledgments

References

Algorithm 1: Maximum tolerance and minimum $a f f e c t a n c e$ based MLS algorithm (MTMA).

Algorithm 2: Maximum weighted and minimum $a f f e c t a n c e$ based MWLS algorithm (MWMA).