In wireless sensor networks, link scheduling is a fundamental problem related to throughput capacity and delay. For a given set of communication requests
L
= {
l
_{1}
,
l
_{2}
,...,
l_{n}
}, the MLS (maximum link scheduling) problem aims to find the largest possible subset
S
of
L
such that the links in
S
can be scheduled simultaneously. Most of the existing results did not consider bidirectional transmission setting, which is more realistic in wireless sensor networks. In this paper, under physical interference model SINR (signaltonoiseplusinterferenceratio) and bidirectional transmission model, we propose a constant factor approximation algorithm MLSA (Maximum Link Scheduling Algorithm) for MLS. It is proved that in the same topology setting the capacity under unidirectional transmission model is lager than that under bidirectional transmission model. However, compared with some work under unidirectional transmission model, the capacity of MLSA is improved about 28% to 45%.
1. Introduction
D
uring the past two decades, wireless sensor networks (WSNs) have been employed in a variety of applications ranging from military to medical, and from industry to home. In WSNs, the capacity is one of the most important indices of quality of service (QoS). However, due to the deficiency of frequency spectrum resource, many wireless communications share the common spectrum and there exists interference among simultaneous transmission links which leads to the decrease of communication capacity of WSNs
[1]
. How to enhance the throughput capacity becomes a challengeable problem to be solved. One feasible method is spatial reuse, i.e., sensors can transmit concurrently, without interfering.
As a fundamental problem in WSNs, link scheduling is crucial for improving networking performances through maximizing throughput and fairness. A link scheduler chooses a set of active links to transmit data and deactivate other links to eliminate their interference on the active links.
The link scheduling problem, which has been studied with different optimization objectives, mainly includes two subproblems, that is, throughputoptimum scheduling problem and minimum delay scheduling problem. Formally, for an arbitrary given set of links
L
= {
l
_{1}
,
l
_{2}
,...,
l_{n}
}, each
l_{i}
is a senderreceiver pair of sensor nodes in the Euclidean plane, the throughputoptimum scheduling problem, which is also called maximum link scheduling (MLS) problem
[2]
or maximum independent set link (MISL) scheduling
[3]
problem, is to find a subset of links with maximum cardinality satisfying the interference constraints. The minimum delay scheduling problem, which is also called the shortest link scheduling (SLS) problem
[4]
, is described as how one can partition
L
into subsets, as few as possible, so that the transmissions in each subset can be done simultaneously. In this paper, we focus on the MLS problem.
In WSNs, interference among the simultaneously transmitting links must be considered. An important issue is how to model the interference when one designs link scheduling algorithms in WSNs. In fact, the interference model has been shown to have a major impact on the complexity of optimal wireless link scheduling. Therefore, for different interference models, the scheduling problems are essentially different
[5]
. Roughly speaking, the interference models consist of two classes. One class is graphbased interference models and the other is physical interference model. For graphbased models, the interference is modeled as a binary and a local measure, i.e., the interference beyond a certain range is neglected. The graphbased interference models make the algorithm design tractable since they localize the interference of a transceiver on others. Unfortunately, the graphbased models are too simple and cannot reflect accurately the interference among links. For example, 6 communication links transmit simultaneously, as illustrated in
Fig. 1. 1
, and all the 6 links can communicate concurrently under graphbased interference model
[6]
. However, it is too optimistic. For instance, to ensure the link
l
_{1}
can transmit successfully, the accumulative interference caused by all other 5 links besides
l
_{1}
on
l
_{1}
should not be neglected. In the physical model, which is also called SINR (signaltointerferenceplusnoiseratio) model, the accumulative interference is considered. A message can be received successfully by a node if the ratio between the received signal strength and the ambient noise plus interference from other nodes exceeds a certain hardwarespecific threshold. The SINR model reflects the physical reality more accurately than the graphbased interference models. However, due to the nonlocality of SINR, it is difficult to design a link scheduling algorithm under SINR constraints. On the other hand, both MLS and SLS are NPhand
[7
,
8]
.
The influence of accumulative interference on communication.
Another issue should be considered when we design link scheduling algorithms for WSNs is power assignment. Generally, we refer to this as the powercontrolbased scheduling problem. Oblivious power assignment is one of the most important approaches for power assignment, where the power depends only on the length of the given link. The two most frequently used power assignment strategies indeed belong to this type. One is the uniform (or fixed) power assignment, the other is linear assignment which ensures that the signals received at the intended receivers are identical.
In wireless communication system, two communication models are considered, i.e., unidirectional communication model and bidirectional communication model. Most of existing results for MLS were under unidirectional communication model, since this model is easy to be tackled. In bidirectional model, the communication is in two directions. Thus, the asymmetry between sender and receiver disappears, and two nodes in one link act as sender and receiver. It is more difficult to design MLS algorithms under bidirectional model.
 1.1 Summary of contributions
In this paper, we consider the communication requests as bidirectional links, which is a challenge to link scheduling problems. In unidirectional transmission links, the signals always are transmitted from the sender to the receiver. While in the bidirectional case, a stronger separation criterion should be applied, since communication along each link can occur in different directions. The bidirectional communication model meets the reality of WSNs, though it is easy to get better networks performance under unidirectional model. We prove (see
theorem 5.1
) that the cardinality of feasible set under bidirectional model is smaller than it under unidirectional model. However, the simulation results show that our algorithm is more effective than some algorithms under unidirectional model. For example, compared with OSSA
[9]
and MISL
[3]
the capacity of our algorithm is improved about 28% to 45% (
Fig. 5. 2
).
We propose a constant factor approximation algorithm for MLS problem, which is to find the largest feasible subset
S
of links that can be scheduled simultaneously without interference. We define “safe distance”
SD
(
l
) for each link
l
. A link
l
joins into feasible set
S
, which means that no other link whose distance to
l
is shorter than
SD
(
l
) can join into
S
. The “safe distance”
SD
(
l
) is an increasing function on the length of
l
.
Due to low power and weakly computing capability of sensor nodes, it is important to design low complexity algorithms for WSNs. A low complexity algorithm means that it can be implemented in short time, which leads to low delay for WSNs. Based on the proposed concept of “safe distance”, we design a low time complexity algorithm, which is more efficient than existing results, especially for largescale WSNs (
Fig. 5. 7(a)
,
Fig. 5. 7(b)
).
The rest of the paper is organized as follows. We discuss the related work in section 2. Section 3 gives the model and the definition. In section 4, we propose an algorithm for MLS problem under SINR with theoretical analysis in detail. The simulation comparison is presented in section 5. Finally, we summarize the paper in section 6.
2. Related Work
Ever since the pioneering work of Gupta and Kumar
[10]
, how to schedule links and enhance the capacity of WSNs became an important issue. Different optimization measurements and different interference models for link scheduling have been considered. Many graph model based algorithms (e.g.
[11

14]
) were proposed. Unfortunately, the graphbased interference models fail to capture the accumulative property of actual radio signals. In 2006, Moscibroda and Wattenhofer firstly studied the scheduling problem under SINR
[15]
. From then on, SINR became a popular interference model for studying link scheduling problems
[16

23]
.
In
[7]
, Goussevskaia, Oswald and Wattenhofer presented the first NPcompleteness proofs for link scheduling problems under SINR model and proposed an
factor approximation algorithm for MLS with uniform power, where
d_{max}
(
l
) and
d_{min}
(
l
) denote the length of the longest and the shortest links, respectively. The approximation bound is large. The algorithm consists of two steps. Firstly, the problem instance is partitioned into disjoint link length classes, and then, a feasible schedule is constructed for each length class using a greedy strategy. Later, Goussevskaia et al. proposed the first scheduling algorithm with approximation guarantee independent of the topology of the network
[9]
. They proposed a constant approximation guaranteed algorithm for the problem of maximizing the number of links scheduled in one timeslot, and obtained an
O
(log
n
) approximation for the problem of minimizing the number of time slots needed to schedule a given set of requests, where
n
is the total number of links. The claimed constant approximation bound and its proof in
[9]
are valid only when the ambient noise
N
= 0. In fact, the constant approximation bound is large in
[9]
. In
[3]
, Wan et al. developed an approximation algorithm for MLS which had a constant approximation bound regardless of the value of the ambient noise and the lengths of the communication links, and a significantly small approximation bound. These algorithms assume that the transmitter uses uniform power assignment and is independent of topology structure. Recently, Halldorsson and Mitra extended the transimssion power to oblivious power assignment (including uniform, mean, and linear power assignment), and proposed a factor of
O
(1) approximation ratio algorithm for both unidirectional and bidirectional links
[22]
. In
[23]
, Kesselheim improved the result obtained in
[22]
and developed the first
O
(1)  approximation ratio algorithm for MLS with power control. Most of the above algorithms for link scheduling in the SINR model are centralized. In
[2]
, Pei and Kumar developed a distributed and
O
(1) approximation ratio algorithm for MLS problem.
Bidirectional communication is more consistent with WSNs. Fanghanel et al. introduced the bidirectional version of the scheduling problem and gave a
O
(log
^{3.5+}
^{α}
n
) approximation factor algorithm for SLS using the mean power assignment in general metrics
[24]
. This result was improved to
O
(log
n
) in
[18]
. For MLS problem, an improved approximation factors of
O
(1) in bidirectional cases was proposed in
[22]
.
3. Model and Definition
Given a set of links
L
= {
l
_{1}
,
l
_{2}
,...,
l_{n}
}, where each link
l
represents a communication request from a sender
s
(
l
) to a receiver
r
(
l
). That is, the communication link
l
= (
s
(
l
),
r
(
l
)) . All the nodes are deployed in a Euclidean plane. The length of link
l
, which represents the Euclidean distance between
s
(
l
) and
r
(
l
) , is denoted by
d
(
l
) =
d
(
s
(
l
),
r
(
l
)) . When no ambiguity arises, the length of link
l
is denoted simply by
l
=
d
(
s
(
l
),
r
(
l
)) . The asymmetric distance from link
l_{u}
to
l_{v}
is denoted by
d
(
l_{u}
l_{v}
)=
d
(
s
(
l_{u}
),
r
(
l_{v}
)). Let Δ denote the ratio of the length of the longest and the shortest links. Assume that all links are of different length, which does not affect the results essentially. Suppose that each link has a unittraffic demand, and we can model the case of nonunit traffic demands by replicating the links.
Let
P
_{s(l)}
denote the power assigned to link
l
. We use the path loss radio propagation model for the reception of signals, where the signal received from
s
(
l
) at receiver
r
(
l
) is
P
_{s(l)}
/
d^{α}
(
s
(
l
),
r
(
l
)), where constant
α
denotes the path loss exponent, whose exact value depends on external conditions of the medium (humidity, obstacles, etc.), as well as the exact senderreceiver distance. As common, we assume that
α
> 2
[10]
. We adopt the physical interference model, in which the link
l_{u}
transmits successfully if and only if the following inequality holds.
where
β
≥1 denotes the minimum SINR value required for a message to be successfully received,
N
is the ambient noise, and
S
is the set of concurrently scheduled links in the same slot. If each link in
S
can satisfy (1), then
S
is called a SINRfeasible link set.
In the bidirectional communication model, the asymmetry between senders and receivers disappear. The distance between two links is the shortest distance between any endpoints of the links. The symmetric distance between link
l_{u}
and
l_{v}
is denoted by
d
(
l_{u}l_{v}
) =
d
(
l_{v}l_{u}
) = min{
d
(
s
(
l_{u}
),
r
(
l_{v}
)),
d
(
s
(
l_{u}
),
s
(
l_{v}
),
d
(
r
(
l_{u}
),
r
(
l_{v}
),
d
(
r
(
l_{u}
),
s
(
l_{v}
))}.
Obviously, it is more difficult to calculate the SINR value under bidirectional setting.
In this paper we consider MLS problem under the uniform (or fixed) power assignment, i.e., all links are assigned the same power, which is denoted by
P
in the rest of the paper.
Definition 3.1
[8]
The relative interference (RI) of link
l_{w}
on link
l_{v}
is the increase caused by
l_{w}
in the inverse of the SINR at
l_{v}
, namely
. For convenience, define
RI
_{lv}
(
l_{v}
) = 0 .
The affectance of link
l_{v}
, caused by link set
S
, is the sum of the relative interferences of the links in
S
on
l_{v}
, as well as the effect of noise, scaled by
β
, or
Note that a solution
S
is valid if and only if the affectance (by the other nodes in
S
) of each link in
S
is at most 1. That is to say
S
is a SINRfeasible set if and only if, for all
l
∈
S
,
a_{S}
(
l
) ≤ 1.
Definition 3.2
[8]
If the affectance of any link of
S
, caused by the set
S
, is at most 1/
p
, the set
S
is defined a
p
signal set or schedule.
4. Maximum link scheduling algorithm under SINR model
 4.1 Existing methods
Firstly, we introduce some existing methods closely related to our work. In
[3
,
9
,
22]
, the algorithms process links in nondecreasing order of length. Let
L
be the initial set of links, and
S
the set of links has already been chosen (which is empty initially). The basic idea is as follows.

(1) sorting transmission links in nondecreasing order;

(2) picking the shortest linklv= (s(v),r(v)) inL＼Sand removinglvfromL;

(3) removing all the links in the following set fromL: {lu= (s(u),r(u))lu∈L＼Sandd(s(u),r(v)) ≤c1d(s(v),r(v))}, i.e., all the links nearbylvinL＼S, wherec1is a constant

(4) removing all the links in {lw= (s(w),r(w))lw∈L＼Sandas(lw) ≥c2} fromL, i.e. , all the links inL＼Sthat suffer from high interference caused by all chosen links inS, wherec2<1 is a constant;

(5) repeating (2), (3) and (4) untilL= ∅ .
The MLS algorithms greedily schedule links in increasing order of length, i.e., “strong” links are scheduled first. After a link
l_{v}
is added to the solution
S
, its “safety” is guaranteed in two steps. Firstly (step (3)), all links
l_{u}
whose distance to
l_{v}
is shorter than
c
_{1}
d
(
s
(
v
),
r
(
v
)) are removed from
L
. Secondly (step (4)), all links
l_{w}
whose affectedness
a_{S}
(
l_{w}
) greater than or equal to a threshold of
c
_{2}
are removed from
L
.
The idea of our algorithm is similar to
[3
,
9
,
22]
, the main challenge is that we consider the links under bidirectional communication setting.
 4.2 Algorithm description
Before algorithm description, we give the concept of safe distance.
If only two links
l_{u}
and
l_{v}
transmit concurrently, then link
l_{u}
suffers from the interference from link
l_{v}
. According to (1), the sufficient condition of link
l_{u}
communicating successfully is that
, i.e.,
That is, if two links
l_{u}
and
l_{v}
can transmit concurrently, their distance must exceed a threshold.
Now, we define the “safe distance” of
l_{u}
.
Definition 4.1
Safe distance (SD)
The
safe distance
of
l_{u}
is a function on the length of
l_{u}
,
By the definition of
safe distance
, if
l_{u}
and
l_{v}
can transmit at the same time, then the distance between
l_{v}
and
l_{u}
is greater than or equal to the
safe distance
of
l_{u}
. Therefore, if
l_{u}
∈
S
, the links whose distance to
l_{u}
is shorter than
safe distance
of
l_{u}
must not join into
S
.
We use
d
_{min}
= min{
d
(
l_{v}l_{u}
)
l_{v}
∈
S
} to denote the shortest distance between
S
and
l_{u}
.
The main idea of our algorithm can be described as follows. Firstly, we sort the links of
L
by nondecreasing order of length. Then, we select the shortest link
l_{u}
of
L
＼
S
( initially
S
is empty), according to SINR model, if all the links in
S
do not suffer from the join of link
l_{u}
and
S
cannot impact on the successful communication of
l_{u}
, then
S
and
l_{u}
can communicate simultaneously and
l_{u}
can join into
S
. Let
c
=(1/
β
1/
β
_{1}
)
^{1/α}
, where
β
_{1}
>
β
is a constant. We can prove that if link
l_{u}
satisfies
l_{u}
/
d
_{min}
≤
c
and
, then
l_{u}
can join into
S
. Finally, if
l_{u}
joins into
S
, the links whose distance to
l_{u}
is shorter than
safe distance
of link
l_{u}
can never join into
S
, therefore, we can remove them from
L
.
 4.3 Maximum link scheduling algorithm
The pseudo codes of our algorithm can be described as follows.
The algorithm MLSA schedules links greedily according to the link length increment, i.e., the “stronger” link is scheduled firstly. After joining into
S
, the “safety” of
l
is guaranteed by line 11, MLSA removes the links that do not join into
S
in the future, so that accelerating the performance.
 4.4 Performance analysis
Now, we discuss the correctness and efficiency of MLSA.
We prove that the solution
S
obtained in MLSA is correct, i.e., all selected links can be scheduled concurrently.
Theorem 4.1
The set
S
returned by MLSA is a feasible scheduling set under SINR constraint.
Proof.
By induction.
1˚ When
S
={
l
_{1}
} , the result holds obviously.
2˚ Assume that
S
={
l
_{1}
,
l
_{2}
,...,
l
_{i}
_{1}
} is a feasible scheduling set. Firstly, we prove that if
l_{u}
∈
L
＼
S
satisfies the condition
l_{u}
/
d
_{min}
≤
c
,
l_{u}
can join into
S
and do not impact on other links in
S
.
For ∀
l_{v}
,
l_{w}
∈
S
,
The above inequality holds, since
l_{v}
≤
l_{u}
and
d
_{min}
≤
d
(
l_{v}l_{u}
).
Due to
l_{u}
/
d
_{min}
≤ (1/
β
1/
β
_{1}
)
^{1/α}
and
≤ 1/
β
1/
β
_{1}
,
we have,
That is,
The inequality (5) implies that link
l_{u}
can join into
S
and cannot impact on the links in
S
.
It is easy to prove that the feasible set
S
do not impact on link
l_{u}
. According to line 9, we have
, which means that
.
Therefore, the feasible set
S
does not impact on link
l_{u}
.
3˚ By the above inductive hypothesis,
S
is a SINR feasible set.
Next, we prove that MLSA is competitive, i.e., it needs only a constant factor away from the optimum.
Lemma 4.1
[9]
There is a polynomialtime algorithm that takes a
p
signal schedule and refines into a
p
′signal schedule, for
p
′>
p
, increasing the number of slots by a factor of at most ⎾2
p
′/
p
⏋
^{2}
.
According to Lemma 4.1, if the minimum threshold
β
is increased to
β
_{1}
(constant
β
_{1}
>
β
), then there is a polynomialtime algorithm such that the scheduling slots increasing the number of slots by a factor of at most ⎾2
β
_{1}
/
β
⏋
^{2}
.
Now, we compare the solution
S
returned by MLSA with the optimal solution
OPT
. In order to compare the two solutions, we need to count the number of links eliminated by MLSA that could have been scheduled in the
OPT
, i.e., we bound the size of the set
OPT
′=
OPT
＼
S
.
Line 4 and line 11 of MLSA can guarantee the link
l
is “safety”. If link
l_{u}
joins into
S
, some links are removed because their distance to
l_{u}
is shorter than
SD
(
l_{u}
). Next, we seek for the bound of removed links yet belong to
OPT
, which is denoted by 
.
Lemma 4.2
Let
S
be a SINRfeasible solution returned by MLSA. For ∀
l_{u}
∈
S
and
l_{v}
∈
, the distance of
l_{v}
to
l_{u}
is shorter than
SD
(
l_{u}
). The number of
l_{v}
, which is denoted by 
, is at most

S
.
Proof.
Since
d
(
l_{v}l_{u}
) <
SD
(
l_{u}
), the relative interference of
l_{v}
on
l_{u}
is
Due to
l_{u}
∈
S
,
We have,
Therefore,
Since the total relative interference on
l_{u}
is at most 1, the number of
l_{v}
is at most
.
Therefore, we have 
 ≤

S
.
If link
l_{u}
cannot satisfy the condition of line 8 in MLSA, it is removed from
L
and does not join into
S
. Next, we seek for the bound of removed links yet belong to
OPT
, which is denoted by 
.
Lemma 4.3
Let
S
be a SINRfeasible solution returned by MLSA. For
l_{u}
∈
S
and
l_{v}
∈
, the distance from
l_{v}
to
l_{u}
is shorter than
l_{v}
/
c
. The number of
l_{v}
, which is denoted by 
, is at most Δ
^{α}

S
.
Proof.
Without loss of generality, assume that
l_{u}
∈
S
is the closest link to
l_{v}
for one iteration, and
d
_{min}
=
d
(
l_{v}l_{u}
)<
l_{v}
/
c
, then
l_{v}
∉
S
. According to the definition of relative interference and SINR constraint,
Since the total relative interference on
l_{u}
is at most 1, therefore，the number of
l_{w}
is at most Δ
^{α}
/
c^{α}
. Given a link
l_{u}
∈
S
, the number of
l_{v}
∈
is at most Δ
^{α}
/
c^{α}
= Δ
^{α}
. Therefore, 
 ≤ Δ
^{α}

S
.
Theorem 4.2
The approximation ratio of MLSA is
O
(1).
Proof.
The result follows by adding the bounds of lemmas 4.2 and 4.3, which results in
Although the approximation ratios claimed in
[9
,
3
,
22]
are constant, the bounds are large. The approximation ratio is 1+(2
x
+1)
^{α}
+5·3
^{α}
^{+1}
in
[9]
, where
. Moreover it is valid only when the ambient noise
N
=0 . In
[3]
, the ambient noise is considered, and the approximation ratio is at least
. In
[22]
, the approximation ratio is 20·3
^{α+1}
. The approximation ratio of MLSA is 1+(1+Δ
^{α}
)
. In realistic scenarios Δ is a constant
[26]
. When Δ is small MLSA is competitive. The approximation ratio is independent of Δ and only depends on
α
and
β
. In fact, with the increasing of Δ, the capacity of network gradually decreases, which will be shown in section 5.2 by simulations.
 4.5 Assumption and implementation of MLSA
In this paper we design a centralized algorithm MLSA. For some WSN systems, such as chemical process control, centralized operation of scheduling algorithm is quite realistic. In this scenario, gateway nodes serve as central points for collecting network information, computing schedules and disseminating the schedules to the other network nodes. In MLSA, we need to give some assumptions and determine some parameters. Firstly, we assume stationary nodes, a fixed topology and one hop data transmitting. Secondly, during the link scheduling, we assume stationary network, i.e., there is no other unexpected transmitting link
[25]
.
For MLSA, many parameters should be determined prior to, or at the beginning of, deployment. The ambient noise
N
and path loss exponent
α
are easily measured in the deployment environment. While parameters
P
and
β
are functions of the devices and technology used in WSNs. Furthermore, we assume that nodes know their approximation locations, which could be determined by builtin GPS or through estimation techniques such as triangulation from known points. Assume that the link demands (which are beyond our research) are known, and every active node knows the location of the response node. The gateway nodes collect and sort the link demands, compute schedules and disseminate the results to the other nodes. The last problem is how to determine the distance between two active links. Assume that
S
is a SINRfeasible set and
l_{u}
= (
s
(
l_{u}
),
r
(
l_{u}
)) is the shortest active link which is not be scheduled. Next, we estimate if
l_{u}
can join into
S
. First,
l_{u}
should compute the shortest distance between
l_{u}
and
S
.
s
(
l_{u}
) and
r
(
l_{u}
) send a
probe
to the active nodes in
S
, respectively, and the active nodes send a
ack
to
s
(
l_{u}
) and
r
(
l_{u}
) . Obviously, the first response comes from the nearest active node. Therefore, the shortest distance is done. Second, if
l_{u}
can join into
S
,
l_{u}
sends its location and the “safe distance”
SD
(
l_{u}
) to other unscheduled active links, which receive the information and compute the distance to
l_{u}
. The links whose distance to
l_{u}
is shorter than
SD
(
l_{u}
) can never be scheduled then they turn into inactive.
5. Simulation
 5.1 Parameter setting
Let
l
= (
s
(
l
),
r
(
l
)) be a communication link and
P
be the transmission power of
l
. According to radio fading theory, the received power at the receiver is
P_{r}
=
P
/
l^{α}
. We always assume that the Euclidian distance of the closest pair of the nodes is larger than 1 since the received power should be smaller than the transmission power. In (1), if
S
is empty, the SINR can be simplified to signal to noise ratio (SNR) given by
P
/
N
·
l^{α}
≥
β
or
P
≥
β
⋅
N
⋅
l^{α}
. Let
R
=(
P
/
βN
)
^{1/α}
then a link
l
can transmit successfully in the absence of interference if and only if
l
≤
R
. The value
R
is thus referred to as the maximum transmission radius. On the other hand, to ensure that the longest link transmits successfully, the power assigned to all links is at least
β
⋅
N
⋅
. Therefore, the distance between two nodes, which is onehop neighbor each other, is not too large so that preserve energy. Let the length of the longest link be at most 40, i.e. Δ ≤ 40 , during the simulation. The units of length and power are meter (
m
) and milliwatt (
mW
), respectively.
All links are deployed in a square region randomly. There are several parameters that affect the feasible set
S
, such as node density, node distribution, path loss exponent and ambient noise and so on. The parameters are listed in
Table 5. 1
.
Parameters
 5.2 Simulation results
We compare our algorithm MLSA with OSSA
[9]
(Algorithm 1 in
[9]
) , MISL
[3]
and MMHC
[22]
(Algorithm C in
[22]
). MISL and OSSA assume unidirectional transmission link, and MMHC assumes both unidirectional and bidirectional transmission links. Compared with unidirectional transmission, bidirectional transmission links suffer from more interference.
Theorem 5.1
A SINRfeasible set under bidirectional transmission model is also a SINRfeasible set under unidirectional transmission model.
Proof.
Let
S
be a SINRfeasible set under bidirectional transmission model, for ∀
l_{u}
∈
S
, according to SINR constraint, we have
On the other hand, we have
d
(
l_{w}l_{u}
)=
d
(
l_{u}l_{w}
)≤
d
(
s
(
l_{w}
),
r
(
l_{u}
)) . Therefore,
(7) shows that
S
is a SINRfeasible set under unidirectional transmission model.
Assume that
S
_{1}
⊆
L
is a SINRfeasible set under bidirectional transmission model and
S
_{2}
⊆
L
is a SINRfeasible set under unidirectional transmission model. Theorem 5.1 implies that the number of links in
S
_{2}
is greater than or equal to the number of links in
S
_{1}
. However, the converse does not hold. For example, in
Fig. 5.1
,
l
_{1}
=(
s
(
l
_{1}
),
r
(
l
_{1}
)),
l
_{2}
= (
s
(
l
_{2}
,
r
(
l
_{2}
)),
d
(
s
(
l
_{1}
),
r
(
l
_{1}
))=10,
d
(
s
(
l
_{2}
),
r
(
l
_{2}
))=10,
d
(
s
(
l
_{1}
),
r
(
l
_{2}
)=13.2 and
d
(
s
(
l
_{2}
),
r
(
l
_{1}
))=13.2. According to SINR,
l
_{1}
and
l
_{2}
can transmit concurrently under unidirectional transmission model while they cannot do under bidirectional transmission model. Thus, the number of links in feasible set
S
under unidirectional transmission model may be more than that under bid0irectional transmission model. However, the experimental results demonstrate that our algorithm under bidirectional transmission model is superior to the algorithms un0der unidirectional transmission model (
Fig. 5.2
).
Unidirectional VS. bidirectional communication links.
Experimental result.
Fig. 5. 2
demonstrates that our algorithm is effective. From
Fig. 5. 2
we see that the capacity got from MLSA is close to MMHC and is superior to OSSA and MISL. Compared with OSSA and MISL, the capacity of MLSA is improved about 28% to 45%.
In fact, both approximation bounds obtained in
[9]
and
[3]
are big constants. For example, let Δ=4,
α
=4 and
β
=16 the approximation bound obtained in
[9]
is 138135, in
[3]
is 272 and in MLSA is 37009. However, when Δ=4,
α
=3 and
β
=2, the approximation bound obtained in
[9]
decreases to 11005, in
[3]
increases to 2188 and in MLSA decreases to 261. The approximation bound of our algorithm is sensitive to the ratio of the longest and the shortest link. Note that when Δ<40, our result is acceptable (
Fig. 5. 3(a)
(b)
). It is reasonable for the assumption that Δ is small. On the contrary, in order to transmit successfully, the long link should be assigned large power, which results in energy waste for the short links and high interference. When Δ≥40 the performance of the four algorithms gets unsatisfying. Compared with other three algorithms, our algorithm can obtain a little better performance (
Fig. 5. 3(a)
(b)
).
The number of links is 1000, α=3 and β=3.
The number of links is 1000, α=3 and β=1.
Next, we analyze the influence of the path loss exponent
α
on the results (
Fig. 5. 4
). It can be seen that the performance of MLSA is superior to other three algorithms, and the performances of OSSA
[9]
and MISL
[3]
is improved with the increasing of
α
, whereas MMHC
[22]
and MLSA is more or less invariant to the path loss exponent. Hence, MLSA has the advantage of being robust to variable pathloss exponent.
The number of links is 1000, R=7.8 and β=5.
The value of
β
influences the size of
S
(
Fig. 5. 5(a)
). With the increasing of
β
, the number of links in
S
decreases. And the difference between
β
_{1}
and
β
influences the result (
Fig. 5. 5(b)
. Moreover, we point out that the scheduling result is more or less independent of transmission power (
Fig. 5. 6
). Therefore, the assumption of fixed transmission power is reasonable.
The number of links is 1000, α=3 and R=16 .
The number of links is 1000, α=3, β=3 and R=16 .
The number of links is 1000, R=16, α=3 and β=3.
Sensor nodes have limited power and low computational capabilities. Therefore, it is important to design low time complexity algorithm in WSNs.
Fig. 5. 7(a)
illustrates the time consumed by four algorithms to compute a feasible set
S
from the same communication request links. Compared with the other algorithms, MLSA is economic (
Fig. 5. 7(a)
) since MLSA computes a feasible set with a minimum cost of time. Compared with MMHC, the running time of MLSA reduces by 25% (
Fig. 5. 7(b)
). In MLSA, when a link
l
joins into
S
, the links within the “safe distance” of
l
are removed which accelerates the implementation of MLSA. However, MMHC needs to decide each link whether it joins into
S
or not.
R=16, α=3 and β=3 .
R=16, α=3 and β=3 .
6 Conclusion and discussion
Link scheduling is a fundamental problem in wireless networks. In this paper, we study MLS problem under physical interference model SINR and bidirectional communication model. Assume that the senders are assigned uniform power, based on the poposed concept of
Safe Distance
, we give a constant factor approximation algorithm MLSA for MLS problem in bidirectional transmission setting Theoretical analysis and simulation show that MLSA is correct and effective. Note that if the transmission power is set too low, some long links will never be scheduled. To ensure the longest link has opportunity to be scheduled we set the transmission power
P
≥
β
⋅
N
⋅
to all senders. On the other hand, the high power is not necessary for short links. We point out that the assumption of uniform power assignment is reasonable in some applications, such as environment monitoring and process control, where the wireless sensors are deployed manually so that the distances between two nodes are approximately equal. Moreover, uniform power assignment is implemented easy, especially to the inexpensive wireless sensors. Without a doubt, dynamically power control is economic and adaptive to the application of WSNs. Therefore, in the further study, we will improve MLSA with power control and lower approximation factor.
BIO
Baogui Huang received his M.S. degree in computer science from Qufu Normal University, Shandong, China, in 2008. He is currently a lecturer in the Information Science and Engineering, Qufu Normal University, Shandong, China. His current research interests include wireless networks and distributed computing. Email : hjbaogui@163.com
Jiguo Yu received the PhD degree in operational research and control theory from Shandong University, Shandong, China, in 2004. From 2007, He was a full professor in the School of Information Science and Engineering, Qufu Normal University, Shandong, China. His main research interests include wireless ad hoc and senor networks，cognitive radio and distributed computing. In particular, he is interested in designing and analyzing algorithms for many computationally hard problems in communication networks and systems. He is a member of the IEEE and the ACM, and a senior member of the CCF (China Computer Federation). Email: jiguoyu@sina.com OR yu@mail.qfnu.edu.cn
Dongxiao Yu received the BSc degree in 2006 for the School of Mathmetics, Shandong University and the PhD degree in 2014 from the department of Computer Science, The University of Hong Kong. He is currently a postdoctoral scholar in the Department of Computer Science, The University of Hong Kong. His research interests include wireless networks and distributed computing. Email: dxyu@cs.hku.hk
Chunmei Ma received her M.S. degree in computer science from Nanjing University of Posts and Telecommunications, Nanjing, China, in 2007. She is currently a Associate Professor in the School of Information Science and Engineering, Qufu Normal University, Shandong, China. Her current research interests include shot boundary detection, image process and database technology. Email : rsmcm@163.com
Ge X.
,
Huang K.
,
Wang C.
,
Hong X.
,
Yang X.
2011
“Capacity analysis of a multicell multiantenna cooperative cellular network with cochannel interference,”
IEEE Transactions on Wireless Communications
10
(10)
3298 
3309
DOI : 10.1109/TWC.2011.11.101551
Pei G.
,
Vullikanti A.K.S.
“Distributed approximation algorithms for maximum link scheduling and local broadcasting in the physical interference model,”
in Proc. of the 32nd IEEE International Conference on Computer Communications, INFOCOM 2013
April 1419, 2013
1339 
1347
Wan P.
,
Jia X.
,
Yao F.
“Maximum independent set of links under physical interference model,”
in Proc. of 4th International Conference on Wireless Algorithms, Systems, and Applications, WASA 2009
August 1618, 2009
169 
178
Wan P.
,
Xu X.
,
Frieder O.
“Shortest link scheduling with power control under physical interference model,”
in Proc. of 6th International Conference on Mobile Adhoc and Sensor Networks, MSN2010
December 2022, 2010
74 
78
Iyer A.
,
Rosenberg C.
,
Karnik A.
2009
“What is the right model for wireless channel interference?,”
IEEE Transactions on Wireless Communications
8
(5)
2662 
2671
DOI : 10.1109/TWC.2009.080720
Gupta P.
,
Kumar P. R.
2001
“Internets in the Sky:The capacity of three Dimentional wireless networks,”
Communications in Information and Systems
1
(1)
33 
50
DOI : 10.4310/CIS.2001.v1.n1.a3
Goussevskaia O.
,
Oswald Y.A.
,
Wattenhofer R.
“Complexity in geometric SINR,”
in Proc. of the 8th ACM international symposium on Mobile ad hoc networking and computing, MobiHoc 2007
September 914, 2007
100 
109
Halldórsson M. M.
,
Wattenhofer R.
“Wireless communication is in APX,”
in Proc. 36th International Colloquium on Automata, Languages and Programming, ICALP 2009
July 512, 2009
525 
536
Goussevskaia O.
,
Halldórsson M.
,
Wattenhofer R.
,
Welzl E.
“Capacity of arbitrary wireless networks,”
in Proc. of the 28th IEEE International Conference on Computer Communications, INFOCOM 2009
April 1925, 2009
1872 
1880
Gupta P.
,
Kumar P. R.
2000
“The capacity of wireless networks,”
IEEE Transactions On Information Theory
46
(2)
388 
404
DOI : 10.1109/18.825799
Chaporkar P.
,
Kar K.
,
Sarkar S.
2008
“Throughput and fairness guarantees through maximal scheduling in wireless networks,”
IEEE/ACM Transactions on Information Theory
54
(2)
572 
594
DOI : 10.1109/TIT.2007.913537
Tang S.
,
Li X.
,
Wu X.
,
Wu Y.
,
Mao X.
,
Xu P.
,
Chen G.
“Low complexity stable link scheduling for maximizing throughput in wireless networks,”
in Proc. of the 6th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, SECON 2009
June 2226, 2009
1 
9
Joo C.
,
Lin X.
,
Shroff N. B.
“Understanding the capacity region of the greedy maximal scheduling algorithm in multihop wireless networks,”
in Proc. of the 27th IEEE International Conference on Computer Communications, INFOCOM 2008
April 1318, 2008
1103 
1111
Li B.
,
Boyaci C.
,
Xia Y.
“A refined performance characterization of longestqueuefirst policy in wireless networks,”
in Proc. of the 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2009
May 1821, 2009
65 
74
Moscibroda T.
,
Wattenhofer R.
“The complexity of connectivity in wireless networks,”
in Proc. of the 25th IEEE International Conference on Computer Communications, INFOCOM 2006
April 2329, 2006
1 
13
Lakshminarayana S.
,
Li B.
,
Assaad M.
,
Eryilmaz A.
,
Debbah M.
“A fastCSMA based distributed scheduling algorithm under SINR model,”
in Proc. IEEE International Symposium on Information Therory, ISIT 2012
July 16, 2012
1598 
1602
Wan P.
,
Chen D.
,
Dai G.
,
Wang Z.
,
Yao F.
“Maximizing capacity with power control under physical interference model in duplex model,”
in Proc. of the 31st IEEE International Conference on Computer Communications, INFOCOM 2012
March 2530, 2012
415 
423
Blough D. M.
,
Resta G.
,
Santi P.
2010
“Approximation algorithms for wireless link scheduling with SINRbased interference,”
IEEE/ACM Transactions on Networking
18
(6)
1701 
1712
DOI : 10.1109/TNET.2010.2047511
Pei G.
,
Anil Kumar V. S.
“Lowcomplexity scheduling for wireless networks,”
in Proc. of the 13th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2012
June 1114, 2012
35 
44
Zhou Y.Q
,
Li X.
,
Liu M.
,
Mao X.
,
Tang S.
,
Li Z.
2014
“Throughput optimizing localized link scheduling for multihop wireless networks under physical interference model,”
IEEE Transactions on Parallel and Distributed Systems
25
(10)
2708 
2720
DOI : 10.1109/TPDS.2013.210
Halldorsson M. M.
,
Mitra P.
“Wireless capacity with oblivious power in general metrics,”
in Proc. of the 22nd annual ACMSIAM symposium on Discrete algorithms (SODA)
January 2325, 2011
1538 
1548
Kesselheim T.
“A constantfactor approximation for wireless capacity maximization with power control in the sinr model,”
in Proc. of the 22nd annual ACMSIAM symposium on Discrete algorithms (SODA)
January 2325, 2011
1549 
1559
Fanghanel A.
,
Kesselheim T.
,
Racke H.
,
Vocking B.
“Oblivious interference scheduling,”
in Proc. of the 28th Symposium on Principles of Distributed Computing, PODC 2009
August 1012, 2009
220 
229
Munir S.
,
Lin S.
,
Hoque E.
,
Shahriar Nirjon S. M.
,
Stankovic J. A.
,
Whitehouse K.
“Addressing burstiness for reliable communication and latency bound generation in wireless sensor networks,”
in Proc. of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks, IPSN 2010
April 1216, 2010
303 
314
Pei G.
,
Vullikanti A.K.S.
2012
“Efficient algorithms for maximum link scheduling in distributed computing models with SINR contraints,”
arXiv:1208.0811v2[cs.DC]16