Link scheduling for throughput maximization in multihop wireless networks under physical interference

Yaqin Zhou, Xiang Yang Li*, Min Liu, Zhongcheng Li, Xiaohua Xu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


We consider the problem of link scheduling for throughput maximization in multihop wireless networks. Majority of previous methods are restricted to graph-based interference models. In this paper we study the link scheduling problem using a more realistic physical interference model. Through some key observations about this model, we develop efficient link scheduling algorithms by exploiting the intrinsic connections between the physical interference model and the graph-based interference model. For one variant of the problem where each node can dynamically adjust its transmission power, we design a scheduling method with O(g(E)) approximation to the optimal throughput capacity where g(E) denotes length diversity. For the other variant where each node has a fixed but possible different transmission powers for different nodes, we design a method with O(g(E))-approximation ratio when the transmission powers of all nodes are within a constant factor of each other, and in general with an approximation ratio of O(g(E) logρ) where logρ is power diversity. We further prove that our algorithm for fixed transmission power case retains O(g(E)) approximation for any length-monotone, sub-linear fixed power setting. Furthermore, all these approximation factors are independent of network size.

Original languageEnglish
Pages (from-to)2415–2430
Number of pages16
JournalWireless Networks
Issue number8
Publication statusPublished - Nov 2017
Externally publishedYes


  • throughput maximization
  • physical interference
  • SINR
  • link scheduling


Dive into the research topics of 'Link scheduling for throughput maximization in multihop wireless networks under physical interference'. Together they form a unique fingerprint.

Cite this