1 Introduction

Various wireless networks (single-hop or multi-hop), e.g., sensor networks, cellular networks, mesh networks, have been deployed for a broad range of applications. Of all these networks, a common fundamental problem is to develop efficient scheduling algorithms that can achieve closely to the optimal throughput capacity. This problem is difficult because of various challenging factors, especially, wireless interference, which constraints the set of links that can transmit simultaneously.

Most of previous algorithm design for the link scheduling problem and its variants simply models wireless interference through geometric graphs, such as conflict graphs and disk graphs [1]. In these graph-based models, interference is pairwise and binary. A set of links is conflict-free if they are pair-wisely conflict-free. Therefore, the interference effect of a transmitter is local and predefined. Intuitively, these features of graph-based interference models enable the link scheduling problems more tractable. We note that many scheduling problems are NP-hard even under this simplified graph-based conflict models [2].

While graph-based interference models help to understand these complex link scheduling problems in wireless networks, they do not capture some key features of real wireless communication because they are just simple approximations of the realistic interference constraints. A more realistic interference model is the so-called physical interference model [3]. Under the physical interference model, a transmission is successful if the signal-to-interference-plus-noise ratio (SINR) constraint is satisfied. That is, the ratio of the desired signal strength and the summed interference from all other concurrent transmissions plus ambient noise exceeds some threshold \(\sigma\). This additive and global interference, considering transmission powers, has a significant impact on the capacity of a wireless network. Since these features are not captured in graph-based models, a direct application of algorithms under graph-based models may even suffer arbitrarily bad performance [4].

Given a time-slotted wireless system, one class of optimum solution to this link scheduling problem for throughput maximization is to find a maximum weighted independent set of links (MWISL) under the SINR constraint at every time slot [5]. Here weight is the queue length of a link. There are two variants of the MWISL problem under the physical interference model, whether each node has an adjustable or fixed transmission power. The variant with adjustable transmission power shall jointly solve the power assignment; the variant with fixed transmission power takes predefined powers as input of the problem.

Existing works mainly focus on approximation algorithms of MWISL for some special cases of power assignment. Constant approximation ratios are only available for the linear power assignment in literature, with [6, 7] in centralized implementation and [8] for distributed implementation. For other power assignments, there are various logarithmic approximation or poly-logarithmic approximation. For uniform power assignment, Halldórsson and Mitra [7] achieves poly-logarithmic approximation where the logarithmic factors are the size of network, and [9] attains a logarithmic approximation factor that is the ratio between the maximum weight and minimum weight [9]. Through algorithmic reductions from maximum independent set of links (MISL) problem, Wan et al. [10] proves the existence of another logarithmic approximation dependent on the cardinality of a maximum independent set of links for adjustable and fixed transmission power. Finding a MISL under physical interference itself is NP hard, and there are no closed-form expressions for size of MISL. Under some extreme cases, the number may be in the order of network size.

On the other hand, the throughput-optimal link scheduling problem can be solved using traditional network stability technique, instead of solving MWISL directly. Recently [11] has combined this technique and randomized technique to get O(g(E))-fractional capacity region for a special case of fixed power assignment. The result holds only if, for any two links having almost the same length, transmission powers are at most a constant factor away from each other. The achieved network stability, however, is not strict Lyapunov Stability that stabilizes the system whenever the arrival rates are interior to the capacity region [12]. The MWISL policy we approximate can guarantee strict Lyapunov Stability [12], which indicates faster convergence and better delay performance. Meanwhile, the results on MWISL problem can imply existence of the same order of approximation ratios for other scheduling problems (i.e., the minimum length scheduling problem and the maximum multiflow problem) [10].

In this paper we focus on developing efficient approximation algorithms for the two variants of MWISL problem to achieve nearly optimal throughput region. Different from previous works that respectively develop specific algorithms for different power assignments, our work provides a unified approach to solve these variants of MWISL problem via some intrinsic properties of physical interference. The design of our approaches is motivated by the method presented for the linear power assignment in [9]. This approach [9] works as follows. It maps every link to a disk with a radius of double link length, and selects a maximum weighted set of disks among the disks. Then it maps the maximum weighted set of disks back to a set of links. It proves that the interference of the link set has a constant upper bound, so the link set can be further refined into an independent set of links. However, in contrast to their method, we applied several new designs and novel techniques.

  1. 1.

    We utilize our characterized property of distance separation to identify candidate link sets for refinement. Here we do not require a previously known power of any link.

  2. 2.

    We design a new method to extract link sets sufficient for adjustable power assignments from these candidate link sets.

  3. 3.

    We employ the fact of fading metrics [13] to prove those relevant results (Lemmas 1 and 3). These results are independent of any power assignment.

The main contributions are summarized as follows.

  1. 1.

    We characterize a kind of link set with a property of potential feasibility, irrespective of any power assignment. We provide a sufficient condition for the property, and investigate rich features of it.

  2. 2.

    Based on these fundamental results, we discover some intrinsic connections between the SINR-based and graph-based interference models regarding the MWISL problem. These connections enable us to utilize results under graph-based models to design the following two efficient scheduling algorithms for the physical interference model.

  3. 3.

    For the problem with adjustable transmission power, we present a sufficient condition for feasible power assignments, and propose a O(g(E))-approximation algorithm for MWISL with adjustable transmission power.

  4. 4.

    For the problem with fixed transmission power, we design a method applicable to any fixed transmission power case. It achieves O(g(E)) approximation when the transmission power diversity \(\log \rho\) is a constant. In general it achieves \(O(g(E)\log \rho )\) approximation. We further prove that the algorithm retains O(g(E)) approximation for any length-monotone, sub-linear fixed power assignment.

  5. 5.

    We conduct extensive simulations to verify the correctness of our adjustable power assignment and evaluate throughput performance of our proposed scheduling algorithms in various network settings. Our simulation results demonstrate correctness and performance efficiency of our proposed algorithms. For the fixed power case when we have a previous algorithm for comparison, our proposed algorithm shows advance on throughput performance.

The rest of the paper is organized as follows. Section 2 introduces the network models and problem to be studied. Section 3 exploits properties on distance separation for the SINR-based interference model. Based on these properties, Sect. 4 reveals the connections between the SINR-based and graph-based interference. Sections 5 and 6 describe our proposed algorithms for the case of adjustable and fixed transmission power respectively. Section 7 improves the approximation ratios and discusses distributed implementation. Section 8 evaluates our proposed algorithms through simulations. Section 9 reviews the related works. Section 10 concludes the paper.

2 Related work

The link scheduling problem and its variants have been extensively studied in literature [14–23]. Early works are mostly on graph-based models that simplify the complexity of wireless communication [14–21]. In the seminal work [5], Tassiulas and Ephremides prove that the celebrated maximum weighted scheduling (MWS) achieves the optimal throughput capacity. Since finding a MWS is NP-hard in general interference models, a variety of simpler and/or suboptimal scheduling algorithms are proposed to achieve full or fractional optimal throughput capacity.

Under the physical interference model, Chafekar et al. [24] make a first attempt on logarithmic-approximation algorithms for the problem with the uniform and linear power assignments. However, the attained bound is not relative to the original optimal throughput capacity, but to the optimal value by using slightly smaller power levels. Le et al. [4] analyzes the performance of GMS under the physical model with uniform power assignment, and employs a technique named “interference localization” to prevent the achievable performance vanishing. Xu et al. [6] firstly get a constant-approximation algorithm for the MWISL problem with linear power assignment. A subsequent work gains a logarithmic-approximation factor related to ratio between the maximum and minimum weight for the uniform case [9]. Most recently, Halldórsson and Mitra also claim a constant-approximation ratio for the linear power setting, and poly-logarithmic approximation ratios dependent on size of link set for other length-monotone, sub-linear fixed power settings [7]. The proposed algorithms utilize a LP based approach to find a link set with constant affectance, and then refine the set into a feasible scheduling set. Nevertheless, they have to rely upon a huge constant (the exact value is not specified in [7]) to upper bound the affectance, which results in a quite small approximation ratio in the order of the square of the huge constant.

All these aforementioned algorithms are centralized, some works also develop distributed link scheduling algorithms for practical applications. Zhou et al. [8] firstly propose a distributed algorithm with a constant-approximation ratio for the linear power case, and a randomized vision is also seen in [25]. Pei and Vullikanti [11] very recently proposed a low complexity scheduling algorithm for a special fixed power assignment where transmission powers of two links with almost equal length are within a constant from each other. Ryu et al. [26] proposes a CSMA-type distributed link scheduling approach with throughput optimality for the uniform power case. However, this approach has high communication overhead. Distributed implementations with approximation including logarithmic of link size are also available in a quite recent work [27].

A quite related work [28] studies the distributed throughput maximization problem via random power allocation under the SINR-RATE based interference model. In such an interference model, the capacity of a link is not a fixed value (e.g., 1 if SINR threshold satisfied and 0 otherwise), but determined by the SINR value at the receiver (i.e., \(\log (1+SINR_i)\)). For simplification, it assumes static path gain over time, whereas the gain is actually determined by concurrent transmissions and thus varies over time. Consequently, the problem studied in [28] does not include an ISL problem with complex interference constraints. The solution bases on a pick-and-compare approach [16] to asymptotically achieve the optimal. However, the probability of this near-optimal approach is quite low (i.e., the probability is \(4N^{-N}\) where N is the number of nodes). The simulation results in [28] show that it can just stabilize an arrive rate of 0.03 under a random network of 16 nodes, while we can support an maximum arrival rate of 0.195 under a random network of 20 Nodes.

Two related problems on capacity are the capacity maximization problem which seeks a maximum number of independent links of a given set of links, and the minimum length scheduling problem which seeks a partition of a given set of links into the fewest independent sets. We make a brief review on the problems under the context of physical interference.

For the capacity maximization problem, [29] and [30] respectively achieve a constant-approximation factor with the oblivious power and power control. However, to ignore the influence of ambient noise, Kesselheim [30] has to assume arbitrary transmission power for each link. This assumption is not reasonable in practice. Motivated by this, Wan et al. [31] then get a constant-approximation algorithm which does not assume unbounded maximum transmission power. A distributed implementation with a constant-approximation factor is proposed in [32] which implicitly assumes the uniform power assignment. The algorithm makes a strong assumption that all nodes have physical carrier sensing capability and can detect if the sensed signal exceeds a threshold. This assumption undoubtedly reduces the difficulties because the main challenge of the original problem is to locally approximate and bound the unknown global interference. Most recently, Halldórsson et al. [33] studies the price of oblivious power assignment that transmission power only depends on link length.

For the minimum length scheduling problem, the overall state-of-the-art retains in the order of logarithm under the uniform power setting [3, 10, 34], and polynomial in maximum link length for general power assignment [35]. In [3], an attempt on a constant-approximation algorithm for this problem with uniform power assignment fails, and the claim has been retracted by the authors.

3 Models and preliminaries

3.1 Network model

We model a wireless network by a two-tuple (V, E), where V denotes the set of nodes and E denotes the set of links. We assume that all nodes are distributed in the Euclidean plane. Each node with one radio can transmit or receive at a time. Each directed link \(l_i=(s_i,t_i)\in E\) represents a communication request from a sender \(s_i\) to a receiver \(t_i\). Let d(u, v) denote the Euclidean distance between node u and v, then the length of link \(l_i\) is \(d(s_i,t_i)\). The length of link \(l_i\) satisfies \(r \le d(s_i,t_i) \le R\), where r and R respectively denote the shortest link length and the longest link length that ensure a successful transmission. We assume that r and R are known for a given network, and let \(r = \delta R\), \(0<\delta \le 1\). Taking logarithm of \(1/\delta\), we get length diversity \(g(E)=\log {(R/r)}\) for link set E [36] . We further assume that geographical position of every node is known (Table 1).

Table 1 Summary of notations
Full size table

A set of links to be scheduled simultaneously must be an independent set of links (ISL) regarding to the underlying interference models. Such a set of links is also called a feasible scheduling set. Under the physical interference model, it is that each link in the set fulfills the following SINR constraint, \(SINR_i \buildrel \Delta \over = \frac{p(l_i) \cdot g(s_i,t_i) }{\sum \nolimits _{l_j \in {\mathcal {S}}} {p(l_j) \cdot g(s_j,t_i) +\xi } }\ge \sigma _{.}\)

Here \(p(l_i)\) is the transmitting power of link \(l_i\), and the power received by \(t_i\) at a distance of \(d(s_i,t_i)\) is \(p(l_i)\cdot g(s_i,t_i) \text{, } \text{ where } g(s_i,t_i)= \min \{\eta \cdot d(s_i,t_i)^{-\kappa }, 1\}\) is the path gain from node \(s_i\) to \(t_i\). The constant \(\eta\) is the reference loss factor, and \(\kappa\) is the path-loss exponent which satisfies \(2< \kappa < 5\) generally. \({\mathcal {S}}\) is the set of links which simultaneously transmit with \(l_i\). The constant \(\xi >0\) denotes the ambient noise, and \(\sigma\) denotes certain threshold for correct decoding of the wanted signals.

Typically, fixed transmission power is length-monotone (i.e., \(p(l_i) \ge p(l_j) \text{ whenever } d(s_i,t_i) \ge d(s_j,t_j)\)) and sub-linear (i.e., \({p(l_i)}\slash {d(s_i,t_i) ^{\kappa }} \le {p(l_j)}\slash {d(s_j,t_j)^{\kappa }} \text{ whenever } d(s_i,t_i)\ge d(s_j,t_j)\)) [7]. There are three length-monotone and sub-linear fixed power assignments widely investigated in literature [7, 31]. The first is the uniform power assignment, where every link transmits at the same power level. The second is the linear power assignment, where \(p(l_i)\) is proportional to \(d(s_i,t_i)^{\kappa }\). The third is the mean power assignment, where \(p(l_i)\) is proportional to \(\sqrt{d(s_i,t_i)^{\kappa }}\).

For a specific power assignment P, we assume each link transmits at a power level \(p(l_i)\), satisfying that \(P_{\min } \le p(l_i) \le P_{\max }.\) Here \(P_{\max }\) and \(P_{\min }\) denote the maximum transmission power and the minimum transmission power. Let \(\rho =P_{\max }/P_{\min }\), and \(\log \rho\) denote power diversity. To ensure successful transmission, \(P_{\min }\) must satisfy \(P_{\min } \ge {\sigma \xi r^{\kappa }} \slash {\eta } ,\) even if interference from all other concurrent transmissions is zero.

3.2 Problem definition

The maximum throughput link scheduling problem [5], characterizes the supportable arrival rate vectors of links for multihop wireless networks. The standard model is described as follows. It assumes time-slotted and synchronized wireless systems with a single frequency channel. All links are assumed to have unit capacity (i.e., a link can transmit one packet with unit length in one time slot). At the beginning of each time slot, packets arrive at each link independently in a stationary stochastic process with an average arrival rate \(\lambda _i\). The vector \(\overrightarrow{Y}(T)=\{Y_i(T)\}\) denotes the number of packets arriving at each link in time slot T. Every packet arrival process \(Y_i(T)\) is assumed to be i.i.d over time. We also assume all packet arrival process \(Y_i(T)\) have bounded second moments and they are bounded by \(Y_{\max }\), i.e., \(Y_i(T) \le Y_{\max }, \forall l_i \in E\). Let a vector \(\{0,1\}^{|E|}\) denote a feasible schedule \(\overrightarrow{S}(T)\) at each time slot T, where \(S_i(T)=1\) if link i is active in time slot T and \(S_i(T)=0\) otherwise. Packets arrive at receivers of activated links at the end of time slots. Then, the queue length (it is also referred to as weight or backlog) vector \(\overrightarrow{Q}(T)=\{Q_i(T)\}\) evolves according to the following dynamics: \(\overrightarrow{Q}(T+1) = \max \{\overrightarrow{0}, \overrightarrow{Q}(T)-\overrightarrow{S}(T)\}+ \overrightarrow{Y}(T).\)

Described by the set of arrival rate vectors under which the system is stable (i.e., all queues are kept finite), the throughput capacity (capacity region), is a major benchmark on throughput performance. A scheduling policy is stable, if for any arrival rate vector in its capacity region [16], \(\lim _{ T\rightarrow \infty } {\mathbb {E}}[\overrightarrow{Q}(T)] < \infty .\)

A throughput-optimal link scheduling algorithm can achieve the optimal capacity region, which is the union of the capacity regions of all scheduling policies [19],

$$\Lambda \triangleq \left\{ {\overrightarrow{Y}:\overrightarrow{Y} \preccurlyeq \overrightarrow{\varphi }, \text{ for } \text{ some } \overrightarrow{\varphi }\in \text{Co}(\Omega)} \right\} .$$

Here \(\preccurlyeq\) denotes element-wise less inequality. \(\Omega\) is the set of all feasible maximal schedules on E, and \(\text{ C }\text{ o }\text{( }\Omega \text{) }\) is the convex hull of \(\Omega\).

Though we have already known that the policy of finding an MWISL at every time slot achieves the optimal capacity region, unfortunately, finding an MWISL itself is NP-hard typically [2]. Thus we have to rely on approximation or heuristic methods to develop sub-optimal/imperfect scheduling algorithms running in polynomial time.

A sub-optimal scheduling policy [19] achieves a fraction of the optimal capacity region, which is characterized by efficiency ratio \(\gamma\) (\(0 < \gamma \le 1\)), i.e., \(\gamma \triangleq \sup \left\{ {\gamma \vert \text{ the } \text{ network } \text{ is } \text{ stable } \text{ for } \text{ all } \overrightarrow{Y} \in \gamma \Lambda } \right\} .\)

It has been proved that \(\gamma\)-approximation algorithms of MWISL is a class of imperfect scheduling policy ( referred to as \({\mathcal {F}}_{\gamma }\)), achieves \(\gamma\)-optimal capacity region, i.e.,

Proposition 1

([37]) Fix \(\gamma \in (0,1]\). If the arrival rates vector \(\overrightarrow{Y}\) is strictly inside \(\gamma \Lambda\) (i.e., \(\overrightarrow{Y}\) lies in the interior of \(\gamma \Lambda\) ), then any imperfect scheduling policy \({\mathcal {F}}_{\gamma }\) can stabilize the system.

Consequently, in the rest of the paper we focus on near optimal solutions to the two following variants of MWISL problem with the SINR-based physical interference constraint. Given a set \(L=\{l_1, l_2,\ldots ,l_n\}\) of links, at time slot T each link \(l_i\) associates with a weight \(W_i(T)=Q_i(T)\), then

  • MWISL problem with adjustable power is to find a set of links \({\mathcal {S}}\) with maximum total weight, and then devise a method to dynamically assign transmission power to every link in \({\mathcal {S}}\) such that \({\mathcal {S}}\) is feasible under SINR constraint;

  • MWISL problem with fixed power is to find a maximum weighted independent set of links \({\mathcal {S}}\) regarding to the predefined transmission power of every link.

4 Properties of distance separation

In this section, we introduce a novel link set, \(\phi\)-separation set, that could be used to compute independent set of links under SINR constraint irrespective of transmission power. We formally define it as follows.

Given a set L of links, let V(L) be the set of nodes containing all senders and receivers of links in L. For any node \(v \in V(L)\), if it holds that \(\sum _{w \in V(L)} {\frac{R^{\kappa }}{d(w,v)^{\kappa }} \le \phi }\) where \(\phi\) is a constant, then we refer to such a set as a \(\phi\)-separation set. For convenience, let the element \({1} \slash {d(v,v)^{\kappa }}\) be zero.

We will show later that a \(\phi\)-separation set has good potential to be a feasible set. Since any two links of a feasible scheduling set can not share a common node in a wireless network with single channel and single radio, we also suppose that links of a \(\phi\)-separation set do not share common nodes. We now introduce a sufficient condition for a \(\phi\)-separation set.

Lemma 1

Given a set L of links, if the distance between any two nodes of V(L) is at least \(d= \theta R\), where \(\theta >0\) is a constant, then for arbitrary node \(v \in V(L)\), we have \(\sum _{w \in V(L)} {\frac{R^{\kappa }}{d(w,v)^{\kappa }} \le \phi },\) where \(\phi = \frac{ 2^{2\kappa +1} \sqrt{3} \pi \kappa }{6 (\kappa -2) \theta ^{\kappa } }\).

Proof

We leave the proof in “Appendix” for a better flow of the paper. \(\square\)

Through the above lemma, we further conclude the following property for a \(\phi\)-separation set.

Corollary 1

Given a \(\phi\)-separation set L, if it satisfies that any two nodes in V(L) have a mutual distance of at least \(d=\theta R\), then for any link \(l=(s_i,t_i) \in L\), it holds that

$$\sum _{(s_j,t_j) \in L} \frac{d(s_i,t_i)^{\kappa }}{d(s_j,t_i)^{\kappa }} \le \phi , \sum _{(s_j,t_j) \in L} \frac{d(s_j,t_j)^{\kappa }}{d(s_i,t_j)^{\kappa }} \le \phi , \sum _{(s_j,t_j) \in L} \frac{d(s_j,t_j)^{\kappa }}{d(s_j,t_i)^{\kappa }} \le \phi.$$

Proof

The results follow directly Lemma 1. \(\square\)

Lemma 2

A \(\phi _1\)-separation set can be partitioned into constantly many \(\phi _2\)-separation sets, where \(\phi _1 > \phi _2\).

Proof

The proof process is similar with Theorem 1 of [3]. \(\square\)

5 Bridging the SINR-based and graph-based interference

We then propose a bridge mechanism to reveal some intrinsic connections between the SINR-based and graph-based interference regarding to the classical MWISL problem. Using the bridge mechanism, we could reduce the difficulty of finding an ISL with SINR constraint to that with graph-based interference based on the property of distance separation.

The bridging mechanism, shown in Algorithm 1, is designed as follows. Given a set L of links, we map every link \(l_i\) to a disk \(a_i\). Each disk is centered at the sender of \(l_i\), with a radius of \(\alpha \cdot d(s_i,t_i), \alpha > 1.\) The disk also has the same weight as that of \(l_i\). A set of disks is independent if any pair of disks in it do not intersect with each other. We select a maximum weighted independent set of disks (MWISD) among the disks, referred to as \({\mathcal {D}}\). Each disk in \({\mathcal {D}}\) is mapped back to the original link, and then these links compose a new set \(L_{{\mathcal {D}}}\).

figure f

The above procedure gracefully connects the graph-based interference models and SINR-based interference models. As is known there are many exiting good approximations for solving the MWISD problem (e.g., the PTAS in [1]),Footnote 1 while by the bridging mechanism we can leverage these results to solve the MWISL problem under the SINR constraint indirectly. On one hand, by explicitly setting the radius greater than the link length, it ensures that the candidate link set satisfies the sufficient condition of a \(\phi\)-separation set. An appreciate \(\phi\)-separation set is a latent independent set of links. On the other hand, the selection of MWISD can preserve a constant-approximation ratio to the optimal under the SINR constraint, providing fundamentals to theoretical proofs in later sections. The lemma below formally claims the result, irrespective of any power assignment.

Lemma 3

Let L be an independent set of links with minimum link length of r under the physical interference model, then L can be partitioned into at most \(\omega\) independent sets of disks with a radius of \(\alpha \cdot d(s_i,t_i)\). Here \(\omega =O(1/\delta ^A)\).

Proof

We use the technique of signal strengthening [3] to decompose L with minimum link length r into disjoint independent sets of disks with larger minimum distance among nodes. According to the technique of signal strengthening, a \(\tau\)-signal set could be refined into at most \(4(\frac{\tau '}{\tau })^2\) \(\tau '\)-signal sets, for \(\tau ' > \tau\) (See Definition 2 for \(\tau\)-signal set, and L is a 1-signal set). So we decompose the link set L into \(\lceil 2 \cdot 3^{\kappa } \slash \sigma \rceil ^2\) disjoint sets, each feasible with an SINR threshold of \(\sigma ' = 3^{\kappa }\).

We then prove that each of the sets can be partitioned into constantly many independent set of disks with a radius of \(\alpha \cdot d(s_i, t_i)\). To prove it, we need the following claim that guarantees minimum distance among nodes in ISL under SINR constraint.Footnote 2 \(\square\)

Claim 1

[30] Considering any two distinct links \(l_i=(s_i,t_i) \text{, } l_j=(s_j,t_j)\) in one of the sets \(L'\) fulfilling the SINR threshold \(\sigma ' = 3^{\kappa }\), the distance between any pair of the involved nodes \(s_i , t_i, s_j, t_j\) has to be at least r for any power setting.

Note that this claim still holds when \(3^{\kappa } \le \sigma\) as it is a stricter SINR constraint, which implies nodes in \(V(L')\) have a mutual distance of r at least.

We then prove that the corresponding disk of any link in \(L'\) intersects constantly many disks of other links. We observe that any pair of disks intersect if and only if the mutual distance of their senders are less than \(\alpha \cdot d(s_i,t_i) + \alpha \cdot d(s_j,t_j)\). We then get that no disks will intersect with other disks if the distance of any two distinct senders is above \(2 \alpha R\). Therefore, we just need to show only a constant number of senders located in the disk centered at any sender with a radius of \(2 \alpha R\).

We initially assume that set \(V_s(L')\) consists of senders of all links in \(L'\). For any sender \(s_i \in V_s(L')\), we define a following set fulfilling,

$$V' = \left\{ s_j \in V_s(L') | d(s_j,s_i) \le \frac{2 \alpha R}{r \slash 2} \cdot \frac{r}{ 2}\right\}.$$

Therefore, \(|V'|\) is the maximum possible number of links whose disks may intersect with the disk of the given link \(l_i\). To prove it, we just need to apply the fact of fading metrics and the packing bound once again (see “Appendix” for details).

By Claim 1, we have already known that the distance between any pair of distinct senders is at least r. This is, balls of radius \(r \slash 2\) centered at nodes in \(V'\) are fully contained in \(B \left( s_i, (\frac{2 \alpha R}{r \slash 2}+1) \cdot \frac{r}{ 2}\right)\). It implies

$$|V'| \le C \left( \frac{2 \alpha R}{r \slash 2}+1 \right) ^A= C \left( \frac{4 \alpha }{\delta }+1 \right) ^A,$$

and we get the number of disks which may intersect with the same disk bounded.

Thus L can be at most partitioned into \(\omega = \lceil 2 \cdot 3^{\kappa } \slash \sigma \rceil ^2 \cdot |V'|=O(1/\delta ^A)=O(1/\delta ^2)\) subsets of links, the disks of which do not intersect mutually.\(\square\)

Note that our proposed algorithm and results apply equally to the bi-directional link case. In a bi-directional case, each node is a sender and receiver. That is, for each bi-directional link \(l_i\) with endpoints u and v, u gets \(w_u\) packets to v while v gets \(w_v\) packets to u. We just need to change the previous one-to-one mapping in Algorithm 1 to a one-to-two mapping. We take link \(l_i\) as two directional links, (u, v) with a weight of \(w_u\) and (v, u) with a weight of \(w_v\). According to the mapping rules in Algorithm 1, we get two distinct disks with the same radius of \(2\Vert l_i\Vert\), one centered at u with a weight of \(w_u\), the other centered at v with a weight of \(w_v\). This process just doubles the number of candidate disks for computing of MWISD, but does not influence the derivation of a constant-approximation or logarithmic-approximation ratio for the optimal.

6 Approximation algorithms with adjustable transmission power

Now we utilize these fundamentals to develop solutions to the MWISL with adjustable transmission power.

6.1 Adjustable power assignment

Given a feasible scheduling set L, to ensure feasibility, the assigned power \(p(l_i)\) for link \(l_i\) shall satisfy, \(p(l_i)\ge \sigma \cdot \left( \frac{\xi }{\eta } {d(s_i,t_i)^{\kappa }} + \sum _{l_j \in \{L \backslash l_i\}} p(l_j)\frac{d(s_i,t_i)^{\kappa }}{d(s_j,t_i)^{\kappa }} \right) .\) That is, the assigned power shall compensate the interference of ambient noise and the simultaneous transmissions. Therefore, a natural method is to assign the power iteratively, and compensate the interference respectively from ambient noise, the previously assigned links and the later assigned links. For a specific link, the suffered interference from ambient noise and the previously assigned links is easy to calculate, the question is to estimate an upper bound of the interference from the later assigned links. Works in [30, 38] provide hints for the problem. The basic idea is to assign a power that is a scale of the summed interference from ambient noise and the preassigned links. Then the interference from the later assigned links can be actually looked upon as an indirect interference of the noise and previously assigned links. However, the sufficient conditions on the candidate link set for feasible power assignments differ greatly. We first introduce the procedure of power assignment below.

Iterative power assignment. Consider a set \(L^*\) of links, and let \(l_1,l_2,\ldots ,l_n\) be a permutation of links in \(L^*\). Note in this procedure, we do not need to order the links in the ordering of decreasing length as done in [30, 38]. It works for arbitrary ordering of links as long as the given set satisfies the sufficient condition we propose later. Assign the first link \(l_1\) a power, \(p(l_1) = m \frac{\sigma \xi }{\eta } d(s_1,t_1)^{\kappa }.\) The powers assigned to later links are iteratively set by \(p(l_i) = m \sigma d(s_i,t_i)^{\kappa } \left( \sum ^{i-1}_{j=1} \frac{p(l_j)}{d(s_j,t_i)^{\kappa }} + \frac{\xi }{\eta } \right) .\) Here m relates to the distance separation property of the given set. Certainly, m shall be greater than 1 to cover the interference from the ambient noise and the previously assigned links. A strict bound of m depends on the sufficient conditions below.

Lemma 4

Let \(L^*\) be a \(\phi\)-separation set, if \(L^*\) fulfills the two following conditions simultaneously:

  1. 1.

    for any two distinct links in \(L^*\), i.e., \(l_i\), \(l_j\), \(i \ne j\), the mutual distance between the senders \(s_i\), \(s_j\) is at least \(\alpha \cdot (d(s_i,t_i)+d(s_j,t_j))\),

  2. 2.

    the constant \(\phi\) satisfies that \(\phi \le \frac{1}{4\cdot {\beta }^{\kappa } \sigma (\sigma +1)}\), where \(\beta =\frac{2\alpha -1}{\alpha -1}\).

then the iterative power assignment generates a feasible power assignment for \(L^*\) if m is within

$$\left[ \frac{1-\sqrt{1-4\cdot {\beta }^{\kappa } \phi \sigma (\sigma +1)}}{2 \cdot {\beta }^{\kappa } \phi \sigma (\sigma +1)},\frac{1+\sqrt{1-4\cdot {\beta }^{\kappa } \phi \sigma (\sigma +1)}}{2 \cdot {\beta }^{\kappa } \phi \sigma (\sigma +1)}\right] .$$

Proof

The proof respectively treats the interference from the ambient noise, the previously assigned links and the later assigned links. It is equivalent to prove that

$$p(l_i)= m \sigma d(s_i,t_i)^{\kappa } \left( \sum ^{i-1}_{j=1} \frac{p(l_j)}{d(s_j,t_i)^{\kappa }} + \frac{\xi }{\eta } \right) \ge \sigma \cdot \left( \frac{\xi }{\eta } {d(s_i,t_i)^{\kappa }} + \sum ^{i-1}_{j=1} p(l_j)\frac{d(s_i,t_i)^{\kappa }}{d(s_j,t_i)^{\kappa }} + \sum ^{n}_{j=i+1} p(l_j)\frac{d(s_i,t_i)^{\kappa }}{d(s_j,t_i)^{\kappa }} \right) .$$

By rearranging the terms, we just need to show that the interference from the later assigned links get bounded by,

$$\sum ^{n}_{j=i+1} \frac{p(l_j)}{d(s_j,t_i)^{\kappa }}\le (m-1) \left( \sum ^{i-1}_{j=1} \frac{p(l_j)}{d(s_j,t_i)^{\kappa }} + \frac{\xi }{\eta } \right) = \frac{m-1}{m\sigma } \cdot \frac{p(l_i)}{d(s_i,t_i)^{\kappa }}.$$

As we mentioned previously, the basic idea of the proof is to take the interference from the later assigned links as the indirect effect of the interference from the previously added. A crucial claim to bound the indirect interference is as follows.

For any i and k within \(\max \{i,k\} < n\), \(\sum ^{n}_{j=\max \{i,k\} } \frac{d(s_j,t_j)^{\kappa } \cdot d(s_k,t_i)^{\kappa }}{d(s_k,t_j)^{\kappa } \cdot d(s_j,t_i)^{\kappa }} \le \left( \frac{2\alpha -1}{\alpha -1} \right) ^{\kappa } \cdot \phi .\) From the first condition of \(L^*\), we can get that \(d(s_k,t_j)> (\alpha -1) \cdot d(s_j,t_j)\), since

$$d(s_k,t_j) \ge d(s_k,s_j)-d(s_j,t_j) \ge \alpha \cdot (d(s_k,t_k)+d(s_j,t_j)) -d(s_j,t_j) = \alpha \cdot d(s_k,t_k)+ (\alpha -1) \cdot d(s_j,t_j).$$

Similarly, we get that \(d(s_j,t_i)> (\alpha -1) d(s_j,t_j)\) by

$$d(s_j,t_i) \ge d(s_j,s_i)-d(s_i,t_i) \ge \alpha \cdot (d(s_i,t_i)+d(s_j,t_j)) -d(s_i,t_i) = \alpha \cdot d(s_j,t_j)+ (\alpha -1) d(s_i,t_i ) > (\alpha -1) d(s_j,t_j).$$

Having the two inequalities, it then follows,

$$\begin{aligned}&\sum ^{n}_{j=\max \{i,k\} } \frac{d(s_j,t_j)^{\kappa } \cdot d(s_k,t_i)^{\kappa }}{d(s_k,t_j)^{\kappa } \cdot d(s_j,t_i)^{\kappa }} \\ &\quad \le\sum ^{n}_{j=\max \{i,k\} } \frac{d(s_j,t_j)^{\kappa } \cdot (d(s_k,t_j)+d(s_j,t_j)+d(s_j,t_i))^{\kappa }}{d(s_k,t_j)^{\kappa } \cdot d(s_j,t_i)^{\kappa }} \\ & \quad \le\sum ^{n}_{j=\max \{i,k\} } d(s_j,t_j)^{\kappa } \cdot \left( \frac{d(s_k,t_j) + \frac{1}{2} d(s_j,t_j)}{d(s_k,t_j) \cdot d(s_j,t_i)} + \right. \left. \frac{d(s_j,t_i)+\frac{1}{2}d(s_j,t_j)}{d(s_k,t_j) \cdot d(s_j,t_i)} \right) ^{\kappa } \\ & \quad\le\sum ^{n}_{j=\max \{i,k\} } d(s_j,t_j)^{\kappa } \cdot \left( \frac{d(s_k,t_j) + \frac{1}{2 (\alpha -1)} d(s_k,t_j)}{d(s_k,t_j) \cdot d(s_j,t_i)} + \right. \left. \frac{d(s_j,t_i)+\frac{1}{2 (\alpha -1)}d(s_j,t_i)}{d(s_k,t_j) \cdot d(s_j,t_i)} \right) ^{\kappa } \\ &\quad \le \sum ^{n}_{j=\max \{i,k\} } \left( \frac{2\alpha -1}{2(\alpha -1)}\right) ^{\kappa } 2^{\kappa -1} \cdot \left[ \left( \frac{d(s_j,t_j)}{d(s_j,t_i)} \right) ^{\kappa }+ \left( \frac{d(s_j,t_j)}{d(s_k,t_j)} \right) ^{\kappa }\right] \\ &\quad \le\frac{(2\alpha -1)^{\kappa }}{2(\alpha -1)^{\kappa }} \left[ \sum ^{n}_{j=\max \{i,k\}} \left( \frac{d(s_j,t_j)}{d(s_j,t_i)} \right) ^{\kappa } +\sum ^{n}_{j=\max \{i,k\}} \left( \frac{d(s_j,t_j)}{d(s_k,t_j)} \right) ^{\kappa } \right] \le \left( \frac{2\alpha -1}{\alpha -1} \right) ^{\kappa } \phi . \end{aligned}$$

The last third inequality results from the generalized mean inequality (cf. [38]). The last step is built on Corollary 1. For brevity, we let \(\frac{2\alpha -1}{\alpha -1} =\beta\).

Next we analyze the upper bound of the interference from the later assigned links.

$$\begin{aligned} \sum ^{n}_{j=i+1}\frac{ p(l_j)}{d(s_j,t_i)^{\kappa }}&= \sum ^{n}_{j=i+1} m \sigma \left( \sum ^{j-1}_{k=1} \frac{p(l_k) \cdot d(s_j, t_j)^{\kappa } }{d(s_k, t_j)^{\kappa } \cdot d(s_j,t_i)^{\kappa } } + \frac{ \xi }{\eta } \frac{d(s_j,t_j)^{\kappa }}{d(s_j,t_i)^{\kappa }} \right) \\ &= m \sigma \left( \sum ^{n}_{j=i+1} \sum ^{j-1}_{k=1} \frac{p(l_k) \cdot d(s_j, t_j)^{\kappa } }{d(s_k, t_j)^{\kappa } \cdot d(s_j,t_i)^{\kappa } } + \frac{ \xi }{\eta } \sum ^{n}_{j=i+1} \frac{d(s_j,t_j)^{\kappa }}{d(s_j,t_i)^{\kappa }} \right) \\ & \le m \sigma \sum ^{n}_{j=i+1} \sum ^{j-1}_{k=1} \frac{p(l_k) \cdot d(s_j, t_j)^{\kappa } }{d(s_k, t_j)^{\kappa } \cdot d(s_j,t_i)^{\kappa } } + m \sigma \phi \frac{\xi }{\eta }. \end{aligned}$$

The last inequality bases on the third inequality in Corollary 1. We then focus on the first term of the above inequality, by rearranging the sums we get

$$\begin{aligned}&m \sigma \sum ^{n}_{j=i+1} \sum ^{j-1}_{k=1} \frac{p(l_k) \cdot d(s_j, t_j)^{\kappa } }{d(s_k, t_j)^{\kappa } \cdot d(s_j,t_i)^{\kappa } } \\&\quad= m \sigma \sum ^{i}_{k=1} \sum ^{n}_{j=i+1} \frac{p(l_k) \cdot d(s_j, t_j)^{\kappa } }{d(s_k, t_j)^{\kappa } \cdot d(s_j,t_i)^{\kappa } } + m \sigma \sum ^{n}_{k=i+1} \sum ^{n}_{j=i+1} \frac{p(l_k) \cdot d(s_j, t_j)^{\kappa } }{d(s_k, t_j)^{\kappa } \cdot d(s_j,t_i)^{\kappa } } \\ &\quad= m \sigma \sum ^{i}_{k=1} \frac{p(l_k) }{d(s_k,t_i)^{\kappa }} \sum ^{n}_{j=i+1} \frac{d(s_k,t_i)^{\kappa } \cdot d(s_j, t_j)^{\kappa } }{d(s_k, t_j)^{\kappa } \cdot d(s_j,t_i)^{\kappa } } + m \sigma \sum ^{n}_{k=i+1} \frac{p(l_k) }{d(s_k,t_i)^{\kappa }} \sum ^{n}_{j=i+1} \frac{d(s_k,t_i)^{\kappa } \cdot d(s_j, t_j)^{\kappa } }{d(s_k, t_j)^{\kappa } \cdot d(s_j,t_i)^{\kappa } } \\ &\quad\le m \sigma \sum ^{i}_{k=1} \frac{p(l_k) \cdot {\beta }^{\kappa } \phi }{d(s_k,t_i)^{\kappa }} + m \sigma \sum ^{n}_{k=i+1} \frac{p(l_k) \cdot {\beta }^{\kappa } \phi }{d(s_k,t_i)^{\kappa }} \\ &\quad\le (1+m \sigma ) {\beta }^{\kappa } \phi \frac{p(l_i) }{d(s_i,t_i)^{\kappa }} - m \sigma {\beta }^{\kappa }\phi \frac{\xi }{\eta }+ m \sigma {\beta }^{\kappa }\phi \sum ^{n}_{k=i+1} \frac{p(l_k) }{d(s_k,t_i)^{\kappa }}. \end{aligned}$$

Thus we can surely get a bounded interference by,

$$\begin{aligned} \sum ^{n}_{j=i+1} \frac{p(l_j)}{d(s_j,t_i)^{\kappa }} &\le (1+m \sigma ) {\beta }^{\kappa } \phi \frac{p(l_i) }{d(s_i,t_i)^{\kappa }} - m \sigma {\beta }^{\kappa }\phi \frac{\xi }{\eta } + m \sigma {\beta }^{\kappa }\phi \sum ^{n}_{k=i+1} \frac{p(l_k) }{d(s_k,t_i)^{\kappa }} + m \sigma \phi \frac{\xi }{\eta }\\ & \le (1+m \sigma ) {\beta }^{\kappa } \phi \frac{p(l_i) }{d(s_i,t_i)^{\kappa }} + m \sigma {\beta }^{\kappa }\phi \sum ^{n}_{k=i+1} \frac{p(l_k) }{d(s_k,t_i)^{\kappa }} \le \frac{(1+m \sigma ) {\beta }^{\kappa } \phi }{1-m \sigma {\beta }^{\kappa }\phi } \cdot \frac{p(l_i) }{d(s_i,t_i)^{\kappa }}, \end{aligned}$$

because \(m \sigma {\beta }^{\kappa }\phi \le \frac{1}{1+\sigma }<1\) when m in

$$\left[ \frac{1-\sqrt{1-4\cdot {\beta }^{\kappa } \phi \sigma (\sigma +1)}}{2 \cdot {\beta }^{\kappa } \phi \sigma (\sigma +1)},\frac{1+\sqrt{1-4\cdot {\beta }^{\kappa } \phi \sigma (\sigma +1)}}{2 \cdot {\beta }^{\kappa } \phi \sigma (\sigma +1)}\right].$$

Finally we can confirm that when m lies in the region, combining \(\phi \le \frac{1}{4\cdot {\beta }^{\kappa } \sigma (\sigma +1)}\), it exactly ensures the following inequality holds, which is also the final objective of this proof,

$$\sum ^{n}_{j=i+1} \frac{p(l_j)}{d(s_j,t_i)^{\kappa }}\le \frac{(1+m \sigma ) {\beta }^{\kappa } \phi }{1-m \sigma {\beta }^{\kappa }\phi } \cdot \frac{p(l_i) }{d(s_i,t_i)^{\kappa }} \le \frac{m-1}{m\sigma } \cdot \frac{p(l_i)}{d(s_i,t_i)^{\kappa }}.$$

\(\square\)

Lemma 5

Given a \(\phi\)-separation set fulfilling the sufficient conditions, using the iterative power assignment, the assigned power has an upper bound of \(P_{\max }^{up}=\frac{m \sigma \xi R^{\kappa }}{(1-m \sigma \phi ) \eta }.\)

Proof

From Lemma 4, we have \(m \sigma \phi {\beta }^{\kappa } <1\). We then prove by induction. For the first assigned link, it holds that \(p(l_1) = \frac{m\sigma \xi }{\eta } d(s_1,t_1)^{\kappa } \le \frac{m\sigma \xi }{\eta } R^{\kappa } = (1-m\sigma \phi )P_{\max }^{up}.\) If for any later assigned link \(l_i, i>1\), \(p(l_i) \le P_{\max }\), then for \(l_{i+1}\) we still have

$$p(l_{i+1})=m \sigma d(s_{i+1},t_{i+1})^{\kappa } \left( \sum ^{i}_{j=1} \frac{p(l_j)}{d(s_j,t_{i+1})^{\kappa }} + \frac{\xi }{\eta } \right) \le m \sigma \phi P_{\max }^{up} + {(1-m \sigma \phi )} P_{\max }^{up} = P_{\max }^{up}.$$

\(P_{\max }\) is the maximum transmission power of all links, thus it also satisfies that \(P_{\max } \le P_{\max }^{up}\). \(\square\)

6.2 Approximation algorithm

Now we describe our proposed algorithm for MWISL with adjustable transmission power. The pseudo codes are shown in Algorithm 2.

figure g

Theorem 1

Algorithm 2 for MWISL with adjustable transmission power outputs a feasible scheduling set having a weight of \(O(1/\delta ^{2(\kappa +1)})\) approximating to the optimal.

Proof

We first verify the correctness of the algorithm.

According to Algorithm 2, \(L_{{\mathcal {D}}}^*\) fulfills the sufficient conditions for a feasible power assignment. And \(\phi ^*= \frac{1}{4\cdot {\beta }^{\kappa } \sigma (\sigma +1)}\) makes \(m=2\) exactly. Thus, the power assignment generates a feasible power assignment for \(L_{{\mathcal {D}}}^*\).

Then we prove the theoretical bound for the algorithm. We use W(L) to denote the summed weight of a set L, and W(OPT) to denote the optimum.

The nodes of all links in \(L_{{\mathcal {D}}}\) have a smallest mutual distance of \(r=\delta R\). Thus, according to Lemma 1, \(L_{{\mathcal {D}}}\) is a \(\phi '\)-separation set, where \(\phi ' = \frac{ 2^{2\kappa +1} \sqrt{3} \pi \kappa }{6 (\kappa -2) \delta ^{\kappa } }.\)

Next, by Lemma 2, \(L_{{\mathcal {D}}}\) can be partitioned into at most \(\omega _1\) \(\phi ^*\)-separation sets, where \(\omega _1\) is a constant upper bounded by

$$\omega _1= 4 \cdot \lceil \frac{\phi '^2}{{\phi ^*}^2}\rceil \le 4 \cdot \left[ \frac{ 2^{2\kappa +1} \sqrt{3} \pi \kappa }{6 (\kappa -2) \delta ^{\kappa } } \cdot {4\cdot {\beta }^{\kappa } \sigma (\sigma +1)}\right] ^2 = 4^{2\kappa +3} {\pi }^2 {\beta }^{2\kappa } \left[ \frac{ \kappa \sigma (\sigma +1)}{\delta ^{\kappa }(\kappa -2)}\right] ^2 / 3.$$

For \(L_{{\mathcal {D}}}^*\) is the most weighted one among the collection, we further have \(\omega _1 \cdot W(L_{{\mathcal {D}}}^*) \ge W(L_{{\mathcal {D}}}).\) By Lemma 3, any feasible set of links can be partitioned into at most \(\omega\) ISDs, so the optimal MWISL has a weight at most \(\omega \cdot W(L_{{\mathcal {D}}}) \slash (1-\epsilon )\). Here \(1 \slash (1-\epsilon )\) is the approximation ratio of Algorithm 2 in [1] for the MWISD problem.

Consequently, we get \(\frac{\omega \omega _1}{1-\epsilon } W(L_{{\mathcal {D}}}^*) \ge W(OPT).\) This completes the proof. \(\square\)

We then analyze the time complexity of Algorithm 2. The algorithm mainly consists of the bridging process, the refinement process and power assignment part. The refinement process and the iterative power assignments respectively cost O(|E|) rounds. The complexity of the bridging process depends on the graph-based algorithm for MWISD problem. If we utilize PTAS [1] in this part, the complexity would be exponential of |E|. It is ok to small-scale networks, but not applicable to large-scale networks. To improve efficiency, we can choose other simple constant-approximation algorithms with some sacrifice of approximation ratios. For instance, we can use greedy maximal schedule to find MWISD in complexity of \(O(|E|\log (|E|)\). Then the complexity of Algorithm 2 will be reduced to \(O(|E|\log (|E|))\).

7 Approximation algorithm with fixed transmission power

In this section we study the problem with fixed transmission power. Similarly with Algorithm 2, Algorithm 3 is still built on our proposed properties and bridge. We first list several existing results which facilitate a simple proof of our proposed algorithm.

Definition 1

(Affectance[3]) The relative interference of link \(l_j\) on \(l_i\) is the increase caused by \(l_j\) in the inverse of the SINR at \(l_i\), namely \(r_{l_j } (l_i ) =\frac{p(l_j) \cdot g(s_j,t_i)}{ p(l_i) \cdot g(s_i,t_i)}.\) For convenience, define \(r_{l_i} (l_i )=0\). Let \(c_i =\frac{\sigma }{1-\sigma \xi \slash \left( p(l_i) \cdot g(s_i,t_i) \right) }\) indicate the extent to which the ambient noise approaches the required signal at receiver \(t_i\). Since \(c_i\) is a constant related to the properties of link \(l_i\), we assume a constant upper bound of \(c_i\) for all links, i.e., \(c^{up}= \max _{l_i \in E}\{c_i\} \le h \sigma , h>1\). This is a fairly reasonable assumption. It simply says that in the absence of other concurrent transmissions, the transmission succeeds comfortably. The affectance of link \(l_i\), caused by a set \({\mathcal {S}}\) of links that transmit simultaneously with \(l_i\), is the sum of relative interference of the links in \({\mathcal {S}}\) on \(l_i\), scaled by \(c_i\), or \(a_{{\mathcal {S}}} (l_i )=c_i \cdot \sum _{l_j \in {\mathcal {S}}} {r_{l_j } (l_i )}.\) For a single link \(l_j\), we use the shorthand \(a_j(l_i)=a_{l_j}(l_i)\).

Definition 2

(\(\tau\)-signal set [3]) We define a \(\tau \text{-signal }\) set to be one where the affectance of any link is at most \(1 \slash \tau\). Clearly, any ISL is a \(\text{1-signal }\) set.

Lemma 6

\(L_{{\mathcal {D}}}^*\) is a \(\tau\)-signal set, and \({1}\slash {\tau }\) is bounded above by \({c^{up} \rho \phi }\) when \(\rho\) is a constant and \({2 c^{up} \phi }\) otherwise.

Proof

The affectance of each link \(l_i \in L_{{\mathcal {D}}}^*\) satisfies,

$$a_{L_{{\mathcal {D}}}^*}(l_i)\le a_{V({L_{{\mathcal {D}}}})}(t_i) \le c_i \cdot \sum _{ \begin{array}{c} w \in V({L_{{\mathcal {D}}}}) \end{array}} \left( \frac{p(l_w)}{p(l_i)} \cdot \frac{d(s_i,t_i)^{\kappa } }{d(w,t_i)^{\kappa }} \right) \le c^{up} \cdot \sum _{ \begin{array}{c} w \in V({L_{{\mathcal {D}}}}) \end{array}} \left( \frac{p(l_w)}{p(l_i)} \cdot \frac{R^{\kappa } }{d(w,t_i)^{\kappa }} \right) .$$

If \(\rho\) is a constant, then \(a_{L_{{\mathcal {D}}}^*}(l_i) \le c^{up} \rho \phi ,\) otherwise, \(a_{L_{{\mathcal {D}}}^*}(l_i) \le 2 c^{up} \phi ,\) where \(\phi = \frac{ 2^{2\kappa +1} \sqrt{3} \pi \kappa }{6 (\kappa -2) \delta ^{\kappa } }\) by Lemma 1.

Therefore, we have \({1}\slash {\tau }\) bounded by \({c^{up} \rho \phi }\) when \(\rho\) is a constant and \({2 c^{up} \phi }\) otherwise. \(\square\)

Next we give the approximation ratio for our algorithm.

figure h

Theorem 2

Algorithm 3 achieves an approximation ratio of \(O(1/\delta ^{2(\kappa +1)})\) for the MWISL problem with fixed transmission power when \(\rho\) is a constant, and an approximation ratio of \(O(\log \rho /\delta ^{2(\kappa +1)})\) generally.

Proof

By the technique of signal strengthening [3], \(L_{{\mathcal {D}}}^*\) can be partitioned into \(4 \slash \tau ^2\) ISLs at most, thus \(\frac{4}{\tau ^2} \cdot W({\mathcal {S}}) \ge W(L_{{\mathcal {D}}}^*).\) By Algorithm 3, we have \(W(L_{{\mathcal {D}}}^*) = W(L_{{\mathcal {D}}})\) if \(\rho\) is a constant, or \(\log {\rho } \cdot W(L_{{\mathcal {D}}}^*) \ge W(L_{{\mathcal {D}}})\) since the most weighted set is selected as \(L_{{\mathcal {D}}}^*\).

Through Lemma 3, the optimal MWISL has a weight at most \(\omega \cdot W(L_{{\mathcal {D}}}) \slash (1-\epsilon )\).

Hence, when \(\rho\) is a constant we have, \(\frac{4 \omega }{ (1-\epsilon )\tau ^2} \cdot W({\mathcal {S}}) \ge W(OPT), \text{ where } \frac{1}{\tau }=c^{up} \rho \phi ,\) and when \(\rho\) is not a constant we have, \(\frac{4 \omega \log {\rho } }{(1-\epsilon )\tau ^2 } \cdot W({\mathcal {S}}) \ge W(OPT), \text{ where } \frac{1}{\tau }=2 c^{up} \phi .\) \(\square\)

Theorem 3

For any sub-linear and length-monotone fixed power assignment, e.g., the uniform power assignment, the linear power assignment, and the mean power assignment, Algorithm 3 has an approximation factor of \(O(1/\delta ^{2(\kappa +1)})\).

Proof

Considering any two distinct links, \(l_i\) and \(l_j\), we assume \(d(s_i,t_i) > d(s_j,t_j)\) for brevity, then we have \({p(l_i)} \slash {p(l_j)} < {d(s_i,t_i)^{\kappa }} \slash {{d(s_j,t_j)^{\kappa }}}\) by the sub-linear feature. Thus we further get \(\rho\) bounded by, \({\rho } = {P_{\max }} \slash {P_{\min }} < {R^{\kappa }} \slash {r^{\kappa }}.\) Immediately, we also get \({1}\slash {\tau } = {c^{up} \phi }\slash { \delta ^{\kappa } }\) for the corresponding approximation ratio \(\frac{4 \cdot \omega }{(1-\epsilon )\tau ^2}\). \(\square\)

The complexity of Algorithm 3 is the same as Algorithm 2.

8 Improving the algorithms

For both Algorithm 2 and Algorithm 3, the approximation ratios polynomial in \(1/\delta =R/r\) could be further improved to logarithmic of R / r by a slight modification of the original algorithms. We then present the modification and theoretical analysis.

The modification is that we shall initially group the input links according to length diversity, and then choose the most weighted group of links as input of the two original algorithms. Let g be a constant, and links with length in \([g^{j-1}r, g^jr)\) belong to the same group \(G_j\). Then we totally get g(E) groups of links. Let \(G_{j^*}\) be the most weighted group and input of Algorithms 2 and 3, then we have,

Theorem 4

Algorithm 2 has an approximation ratio of O(g(E)); Algorithm 3 has an approximation of O(g(E)) when \(\rho\) is a constant and \(O(g(E)\log \rho )\) otherwise.

Proof

Please note that for links in \(G_{j^*}\), the ratio between the longest link and shortest link becomes the constant g. The factor \(1/\delta\) contained in previous results is then replaced by g. We give the proof of Algorithm 2. Let \({\mathcal {S}}\) be the output, then, \(O(1)\cdot W({\mathcal {S}}) \ge W(G_{j^*}).\) Since \(G_{j^*}\) is the most weighted group, we have, \(W(G_{j^*}) \ge g(E)\cdot W(E) \ge g(E)\cdot W(OPT).\) The proof for Algorithm 3 is similar to this. \(\square\)

We also get an improved result under length-monotone, sub-linear fixed power assignments.

Lemma 7

Algorithm 3 achieves O(g(E)) approximation ratio for any length-monotone, sub-linear fixed power assignment.

We then calculate some numeral results on these approximation ratios. Considering a typical wireless sensor network, we have \(R=60\) and \(r=5\). Let \(\sigma = 3^\kappa , \kappa =3\). If we set \(\alpha =2\), \(g=2\) and use PTAS in the bridging process, then we have \(\omega \approx 4^4\). For the adjustable power assignment, the ratio is around \(81 \cdot 12^{5\kappa +2}\). For the uniform power assignment, let \(c^{up}=2\), and the approximation ratio is around \(108 \cdot 4^{5\kappa }\). The computed approximation ratio for uniform power assignment is much better than adjustable power case. The larger approximation ratio for the adjustable power case is mainly caused by the constraint on a small value of \(\phi ^*\).

9 Simulations

Due to limited space, we mainly present simulation results for Algorithm 2 with adjustable powers. We evaluate the throughput performance, and verify correctness of the adjustable power assignment process. The throughput performance of scheduling algorithms is often measured by the total number of unscheduled packets, which is also termed the total backlog. Generally, the total backlog fluctuates slightly in a region if the arrival rate vector lies in the achievable capacity region of a link scheduling algorithm. Inversely, the total backlog increases dramatically if the arrival rate vector exceeds the achievable capacity region. If the total backlog increases to infinity, the network will become unstable.

Fig. 1
figure 1

Topology of the Citysee wireless sensor Network

Full size image
Fig. 2
figure 2

Capacity region of Algorithm 2 under the random network topology. a Total backlog versus average arrival rate. b Zoom in of a. c Total backlog versus time slot under different average arrival rate

Full size image
Fig. 3
figure 3

Power at different time slot under the random network topology

Full size image
Fig. 4
figure 4

Capacity region of Algorithm 2 under the Citysee topology. a Total backlog versus average arrival rate. b Zoom in of a. c Total backlog versus time slot under different average arrival rate

Full size image
Fig. 5
figure 5

Power at different time slot under the Citysee topology

Full size image

We will evaluate the algorithm in two network settings. One uses a randomly generated network topology, and the other uses a real network topology from the CitySee project. In the random network topology, we randomly select 20 links as input from a network with 100 nodes, half of which as senders randomly located on a plane with size \(100 \times 100\) units, the other half as receivers positioned uniformly at random inside disks of radius \(R = 5\) around each of the senders. The minimum length of links is then set as \(r = 1\). For the other setting, the network topology is part of the topology of the Citysee wireless sensor network, which is deployed for environment monitoring in the City Wuxi, China. The topology we use is shown in Fig. 1. (It uses the Cartesian coordinate system that is transformed from the geodetic coordinate system). It contains 446 nodes in an 1000 m \(\times\) 1250 m area. The maximum transmission range of the nodes outdoor is 100 m. A link of such a large length is easy to fail under interference, thus we set the largest link length to be 60 m. We set the minimum length of links as 10 m.

Other parameter settings are as follows. The path loss exponent is set to be 3 and the SINR threshold is 10. Packets arrive at each link independently according to a Poisson process with the same average arrival rate \(\lambda\). Initially, we assign each link k packets where k is randomly chosen from [100, 300].

We first present the throughput performance of Algorithm 2 under the random network topology. We plot three figures to evaluate the maximum supportable average arrival rate in Fig. 2. We first study the fluctuation of the total backlog when the arrival rate increases from 0 to the maximum link capacity of 1. The increasing step is set to be 0.1. It will give us an rough approximation of the achievable capacity region by link scheduling algorithms. Figure 2(a) illustrates the trend of the total backlog at time slot 100,000 as the average arrival rate increases. Figure 2(b) zooms in the region of [0.1, 0.2] in Fig. 2(a). It shows that the total backlog keeps stable around 0.185. We then plot the fluctuation of the total backlog from time slot 0 to time slot 100,000 under the average arrival rate 0.185. In Fig. 2(c) it shows that the total backlog decreases rapidly at the beginning, and then keeps stable in [600, 2000]. It indicates that Algorithm 2 can still support an average arrival rate of 0.185. Figure 2(c) also illustrates the results when the average arrival rate is 0.190, 0.195 and 0.20. The total backlog under 0.195 still converges at a stable region, but it can not be stabilized under 0.20. After an initial decrease, the total backlog for the average arrival rate 0.20 increases nearly linearly since time slot 10,000. Thus we infer that Algorithm 2 can serve an maximum average arrival rate around 0.195 under the random network topology.

Figure 3 presents the assigned powers at different time slots for the random network setting. It respectively shows the maximum assigned power, the minimum assigned power and the average power per activated link at the selected time slots. The maximum assigned power is no greater than 20, much smaller than the theoretical upper bound by Lemma 5 (The theoretical upper bound is 143 in our setting). This verifies our theoretical analysis.

We have also done the similar simulations and analysis for the Citysee network topology. The results on throughput performance and power assignments are shown in Figs. 4 and 5. Fig. 4(a) illustrates the trend of the total backlog at time slot 100,000 as the average arrival rate increases. Figure 4(b) zooms in the region of [0.06, 0.016] in Fig. 4(a). Roughly we can estimate that the total backlog keeps stable around 0.01. We then plot the fluctuation of the total backlog from time slot 0 to time slot 100,000 under the average arrival rate in [0.06, 0.012] in Fig. 4(c) for more details. In Fig. 4(c) it shows that the total backlog keeps stable under arrival rate 0.01, and increases fast under arrival rate 0.012. We can conclude that the maximum average arrival rate that Algorithm 2 achieves is 0.01 under the Citysee network setting. We then make some explanations that why the maximum average arrival rate takes such a low value. According to the classical results in [39], an arbitrary wireless network can not provide an average throughput more than \(O({1}/{\log |V|})\) if we use unit capacity. Thus we can roughly approximate that the optimal value is in the order of 0.047 for the Citysee network. The comparison indicates that Algorithm 2 perform nearly optimally.

10 Conclusion

We tackle the link scheduling problem for throughput maximization under the physical interference model. We solve two variants of the problem by developing approximation algorithms for MWISL problem in a unified scheme. Our algorithms are based on our discovery of intrinsic connections between the SINR-based and graph-based interference. Our results are applicable to the minimum length scheduling problem and the maximum multiflow problem from an algorithmic reduction view [10].

Our current work is limited to the objective of long-term throughput maximization, and would consider other SINR-constrained link scheduling problems with different optimization objectives (e.g., fairness, delay, or joint optimization [23]) as future works.