Distributed wireless link scheduling in the SINR model

Dongxiao Yu (), Yuexuan Wang (), Qiangsheng Hua (), Jiguo Yu () and Francis C. M. Lau ()
Additional contact information
Dongxiao Yu: The University of Hong Kong
Yuexuan Wang: The University of Hong Kong
Qiangsheng Hua: Huazhong University of Science and Technology
Jiguo Yu: Qufu Normal University
Francis C. M. Lau: The University of Hong Kong

Journal of Combinatorial Optimization, 2016, vol. 32, issue 1, No 18, 278-292

Abstract: Abstract We present an approximation algorithm for wireless link scheduling under the physical SINR interference model. In the link scheduling problem, it is given a set of $$n$$ n links in a metric space, each of which is a sender–receiver pair, and the objective is to schedule the links using the minimum amount of time. We focus on a variant of this fundamental problem where the power is fixed, i.e., the power assignment of links is given as part of the input. Specifically, we consider an important category of power assignments called length-monotone sublinear power assignment, which includes the widely studied uniform, mean and linear power assignments. We present a distributed algorithm that can schedule all links in $$O(\log \varDelta (I_{max}+\log ^3n))$$ O ( log Δ ( I m a x + log 3 n ) ) rounds with high probability, where $$\varDelta $$ Δ is the ratio between the longest link and the shortest link and $$I_{max}$$ I m a x is the maximum nearly-equilength class affectance of the link set. It is shown that the proposed algorithm is $$O(\log \varDelta )$$ O ( log Δ ) approximate to the optimal schedule in dense networks with $$I_{max}\in \varOmega (\log ^3n)$$ I m a x ∈ Ω ( log 3 n ) . To the best of our knowledge, our algorithm is the first distributed one whose approximation ratio is independent of the network size $$n$$ n . Our result also shows that the $$\varOmega (\log n)$$ Ω ( log n ) lower bound (Halldórsson and Mitra in: ICALP, 2011) on the approximation ratio does not hold for link sets with $$\log \varDelta \in o(\log n)$$ log Δ ∈ o ( log n ) .

Keywords: Wireless link scheduling; SINR model; Distributed algorithm (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9876-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:1:d:10.1007_s10878-015-9876-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9876-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().