Advanced
SINR based Maximum Link Scheduling with Uniform Power in Wireless Sensor Networks
SINR based Maximum Link Scheduling with Uniform Power in Wireless Sensor Networks
KSII Transactions on Internet and Information Systems (TIIS). 2014. Nov, 8(11): 4050-4067
Copyright © 2014, Korean Society For Internet Information
  • Received : May 21, 2014
  • Accepted : October 02, 2014
  • Published : November 30, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Baogui Huang
School of Information Science and Engineering Rizhao, Shandong, 276826, China
Jiguo Yu
School of Information Science and Engineering Rizhao, Shandong, 276826, China
jiguyu@sina.com
Dongxiao Yu
Department of Computer Science, The University of Hong Kong Pokfulam, Hong Kong, China
Chunmei Ma
School of Information Science and Engineering Rizhao, Shandong, 276826, China

Abstract
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 ,..., ln }, 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 (signal-to-noise-plus-interference-ratio) 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%.
Keywords
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 sub-problems, that is, throughput-optimum scheduling problem and minimum delay scheduling problem. Formally, for an arbitrary given set of links L = { l 1 , l 2 ,..., ln }, each li is a sender-receiver pair of sensor nodes in the Euclidean plane, the throughput-optimum 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 graph-based interference models and the other is physical interference model. For graph-based models, the interference is modeled as a binary and a local measure, i.e., the interference beyond a certain range is neglected. The graph-based interference models make the algorithm design tractable since they localize the interference of a transceiver on others. Unfortunately, the graph-based 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 graph-based 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 (signal-to-interference-plus-noise-ratio) 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 hardware-specific threshold. The SINR model reflects the physical reality more accurately than the graph-based interference models. However, due to the non-locality of SINR, it is difficult to design a link scheduling algorithm under SINR constraints. On the other hand, both MLS and SLS are NP-hand [7 , 8] .
PPT Slide
Lager Image
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 power-control-based 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 large-scale 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 graph-based 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 NP-completeness proofs for link scheduling problems under SINR model and proposed an
PPT Slide
Lager Image
factor approximation algorithm for MLS with uniform power, where dmax ( l ) and dmin ( 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 time-slot, 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 ,..., ln }, 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 lu to lv is denoted by d ( lu lv )= d ( s ( lu ), r ( lv )). 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 unit-traffic demand, and we can model the case of non-unit 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 sender-receiver distance. As common, we assume that α > 2 [10] . We adopt the physical interference model, in which the link lu transmits successfully if and only if the following inequality holds.
PPT Slide
Lager Image
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 SINR-feasible 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 lu and lv is denoted by
d ( lulv ) = d ( lvlu ) = min{ d ( s ( lu ), r ( lv )), d ( s ( lu ), s ( lv ), d ( r ( lu ), r ( lv ), d ( r ( lu ), s ( lv ))}.
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 lw on link lv is the increase caused by lw in the inverse of the SINR at lv , namely
PPT Slide
Lager Image
. For convenience, define RI lv ( lv ) = 0 .
The affectance of link lv , caused by link set S , is the sum of the relative interferences of the links in S on lv , as well as the effect of noise, scaled by β , or
PPT Slide
Lager Image
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 SINR-feasible set if and only if, for all l S , aS ( 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 non-decreasing 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 non-decreasing 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 lv is added to the solution S , its “safety” is guaranteed in two steps. Firstly (step (3)), all links lu whose distance to lv is shorter than c 1 d ( s ( v ), r ( v )) are removed from L . Secondly (step (4)), all links lw whose affectedness aS ( lw ) 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 lu and lv transmit concurrently, then link lu suffers from the interference from link lv . According to (1), the sufficient condition of link lu communicating successfully is that
PPT Slide
Lager Image
, i.e.,
PPT Slide
Lager Image
That is, if two links lu and lv can transmit concurrently, their distance must exceed a threshold.
Now, we define the “safe distance” of lu .
Definition 4.1 Safe distance (SD) The safe distance of lu is a function on the length of lu ,
PPT Slide
Lager Image
By the definition of safe distance , if lu and lv can transmit at the same time, then the distance between lv and lu is greater than or equal to the safe distance of lu . Therefore, if lu S , the links whose distance to lu is shorter than safe distance of lu must not join into S .
We use d min = min{ d ( lvlu )| lv S } to denote the shortest distance between S and lu .
The main idea of our algorithm can be described as follows. Firstly, we sort the links of L by non-decreasing order of length. Then, we select the shortest link lu 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 lu and S cannot impact on the successful communication of lu , then S and lu can communicate simultaneously and lu can join into S . Let c =(1/ β -1/ β 1 ) 1/α , where β 1 > β is a constant. We can prove that if link lu satisfies lu / d min c and
PPT Slide
Lager Image
, then lu can join into S . Finally, if lu joins into S , the links whose distance to lu is shorter than safe distance of link lu 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.
PPT Slide
Lager Image
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 lu L S satisfies the condition lu / d min c , lu can join into S and do not impact on other links in S .
For ∀ lv , lw S ,
PPT Slide
Lager Image
The above inequality holds, since lv lu and d min d ( lvlu ).
Due to lu / d min ≤ (1/ β -1/ β 1 ) 1/α and
PPT Slide
Lager Image
≤ 1/ β -1/ β 1 ,
we have,
PPT Slide
Lager Image
That is,
PPT Slide
Lager Image
The inequality (5) implies that link lu 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 lu . According to line 9, we have
PPT Slide
Lager Image
, which means that
PPT Slide
Lager Image
.
Therefore, the feasible set S does not impact on link lu .
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 polynomial-time 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 polynomial-time 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 lu joins into S , some links are removed because their distance to lu is shorter than SD ( lu ). Next, we seek for the bound of removed links yet belong to OPT , which is denoted by |
PPT Slide
Lager Image
|.
Lemma 4.2 Let S be a SINR-feasible solution returned by MLSA. For ∀ lu S and lv
PPT Slide
Lager Image
, the distance of lv to lu is shorter than SD ( lu ). The number of lv , which is denoted by |
PPT Slide
Lager Image
|, is at most
PPT Slide
Lager Image
| S |.
Proof. Since d ( lvlu ) < SD ( lu ), the relative interference of lv on lu is
PPT Slide
Lager Image
Due to lu S ,
PPT Slide
Lager Image
We have,
PPT Slide
Lager Image
Therefore,
PPT Slide
Lager Image
Since the total relative interference on lu is at most 1, the number of lv is at most
PPT Slide
Lager Image
.
Therefore, we have |
PPT Slide
Lager Image
| ≤
PPT Slide
Lager Image
| S |.
If link lu 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 |
PPT Slide
Lager Image
|.
Lemma 4.3 Let S be a SINR-feasible solution returned by MLSA. For lu S and lv
PPT Slide
Lager Image
, the distance from lv to lu is shorter than lv / c . The number of lv , which is denoted by |
PPT Slide
Lager Image
|, is at most Δ α
PPT Slide
Lager Image
| S |.
Proof. Without loss of generality, assume that lu S is the closest link to lv for one iteration, and d min = d ( lvlu )< lv / c , then lv S . According to the definition of relative interference and SINR constraint,
PPT Slide
Lager Image
Since the total relative interference on lu is at most 1, therefore,the number of lw is at most Δ α / cα . Given a link lu S , the number of lv
PPT Slide
Lager Image
is at most Δ α / cα = Δ α
PPT Slide
Lager Image
. Therefore, |
PPT Slide
Lager Image
| ≤ Δ α
PPT Slide
Lager Image
| 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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
. 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
PPT Slide
Lager Image
. In [22] , the approximation ratio is 20·3 α+1 . The approximation ratio of MLSA is 1+(1+Δ α )
PPT Slide
Lager Image
. 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 built-in 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 SINR-feasible set and lu = ( s ( lu ), r ( lu )) is the shortest active link which is not be scheduled. Next, we estimate if lu can join into S . First, lu should compute the shortest distance between lu and S . s ( lu ) and r ( lu ) send a probe to the active nodes in S , respectively, and the active nodes send a ack to s ( lu ) and r ( lu ) . Obviously, the first response comes from the nearest active node. Therefore, the shortest distance is done. Second, if lu can join into S , lu sends its location and the “safe distance” SD ( lu ) to other unscheduled active links, which receive the information and compute the distance to lu . The links whose distance to lu is shorter than SD ( lu ) 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 Pr = 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
PPT Slide
Lager Image
. Therefore, the distance between two nodes, which is one-hop 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
PPT Slide
Lager Image
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 SINR-feasible set under bidirectional transmission model is also a SINR-feasible set under unidirectional transmission model.
Proof. Let S be a SINR-feasible set under bidirectional transmission model, for ∀ lu S , according to SINR constraint, we have
PPT Slide
Lager Image
On the other hand, we have d ( lwlu )= d ( lulw )≤ d ( s ( lw ), r ( lu )) . Therefore,
PPT Slide
Lager Image
(7) shows that S is a SINR-feasible set under unidirectional transmission model.
Assume that S 1 L is a SINR-feasible set under bidirectional transmission model and S 2 L is a SINR-feasible 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 ).
PPT Slide
Lager Image
Unidirectional VS. bidirectional communication links.
PPT Slide
Lager Image
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) ).
PPT Slide
Lager Image
The number of links is 1000, α=3 and β=3.
PPT Slide
Lager Image
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 path-loss exponent.
PPT Slide
Lager Image
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.
PPT Slide
Lager Image
The number of links is 1000, α=3 and R=16 .
PPT Slide
Lager Image
The number of links is 1000, α=3, β=3 and R=16 .
PPT Slide
Lager Image
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.
PPT Slide
Lager Image
R=16, α=3 and β=3 .
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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). E-mail: 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. E-mail: 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
References
Ge X. , Huang K. , Wang C. , Hong X. , Yang X. 2011 “Capacity analysis of a multi-cell multi-antenna cooperative cellular network with co-channel 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 14-19, 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 16-18, 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 Ad-hoc and Sensor Networks, MSN2010 December 20-22, 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 9-14, 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 5-12, 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 19-25, 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 22-26, 2009 1 - 9
Joo C. , Lin X. , Shroff N. B. “Understanding the capacity region of the greedy maximal scheduling algorithm in multi-hop wireless networks,” in Proc. of the 27th IEEE International Conference on Computer Communications, INFOCOM 2008 April 13-18, 2008 1103 - 1111
Li B. , Boyaci C. , Xia Y. “A refined performance characterization of longest-queue-first policy in wireless networks,” in Proc. of the 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2009 May 18-21, 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 23-29, 2006 1 - 13
Lakshminarayana S. , Li B. , Assaad M. , Eryilmaz A. , Debbah M. “A fast-CSMA based distributed scheduling algorithm under SINR model,” in Proc. IEEE International Symposium on Information Therory, ISIT 2012 July 1-6, 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 25-30, 2012 415 - 423
Halldórsson M. M. 2012 “Wireless scheduling with power control,” ACM Transactions on Algorithms 9 (1)    DOI : 10.1145/2390176.2390183
Blough D. M. , Resta G. , Santi P. 2010 “Approximation algorithms for wireless link scheduling with SINR-based interference,” IEEE/ACM Transactions on Networking 18 (6) 1701 - 1712    DOI : 10.1109/TNET.2010.2047511
Pei G. , Anil Kumar V. S. “Low-complexity scheduling for wireless networks,” in Proc. of the 13th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2012 June 11-14, 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 ACM-SIAM symposium on Discrete algorithms (SODA) January 23-25, 2011 1538 - 1548
Kesselheim T. “A constant-factor approximation for wireless capacity maximization with power control in the sinr model,” in Proc. of the 22nd annual ACM-SIAM symposium on Discrete algorithms (SODA) January 23-25, 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 10-12, 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 12-16, 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