Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

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

  • Published:
Wireless Networks Aims and scope Submit manuscript

Abstract

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 \rho )\) where \(\log \rho\) 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 .

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. Other constant approximation algorithms on the MWISD problem are also applicable, depending on the desired tradeoff between computation complexity and approximation ratio. For example, we can also use other algorithms with lower complexity and smaller constant approximation ratios.

  2. For convenience, we let \(3^{\kappa } > \sigma\), but we do not necessarily assume \(3^{\kappa } > \sigma\), we later show that the lemma also holds when \(3^{\kappa } \le \sigma\).

References

  1. Li, X.-Y., & Wang, Y. (2006). Simple approximation algorithms and PTASs for various problems in wireless ad hoc networks. Journal of Parallel and Distributed Computing, 66, 515–530.

    Article  MATH  Google Scholar 

  2. Sharma, G., Mazumdar, R., & Shroff, N. (2006). On the complexity of scheduling in wireless networks. In Proceedings of the ACM MobiCom (pp. 227–238).

  3. Halldórsson, M., & Wattenhofer, R. (2009). Wireless communication is in APX. In Proceedings of the 36th international colloquium on automata, languages and programming (pp. 525–536).

  4. Le, L.-B., Modiano, E., Joo, C., & Shroff, N. B. (2009). Longest-queue-first scheduling under SINR interference model. In Proceedings of the ACM Mobihoc (pp. 41–50).

  5. Tassiulas, L., & Ephremides, A. (1992). Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE/ACM Transactions on Automatic Control, 37, 1936–1948.

    Article  MathSciNet  MATH  Google Scholar 

  6. Xu, X.-H., Tang, S.-J., & Wan, P.-J. (2010). Maximum weighted independent set of links under physical interference model. In LNCS (vol. 6221, pp. 68–74). Heidelberg: Springer.

  7. Halldórsson, M. M., & Mitra, P. (2012). Wireless capacity and admission control in cognitive radio. In Proceedings of the IEEE Infocom (pp. 855–863).

  8. Zhou, Y. Q., Li, X.-Y., Liu, M., Li, Z. C., Tang, S. J., Mao, X. F., et al.(2012). Distributed link scheduling for throughput maximization under physical interference model. In Proceedings of the IEEE Infocom (pp. 2691–2695).

  9. Xu, X. H., Tang, S. J., & Li, X.-Y. (2011). Stable wireless link scheduling subject to physical interferences with power control, manuscript.

  10. Wan, P.-J., Frieder, O., Jia, X.-H., Yao, F., Xu, X.-H., & Tang, S.-J. (2011). Wireless link scheduling under physical interference model. In Proceedings of the IEEE Infocom (pp. 838–845).

  11. Pei, G., & Vullikanti, A. (2012). Low-complexity scheduling for wireless networks. In Proceedings of the ACM MobiHoc’12 (pp. 35–44). ACM.

  12. Georgiadis, L., Neely, M. J., & Tassiulas, L. (2006). Resource allocation and cross-layer control in wireless networks. Foundations and Trends in Networking, 1(1), 1–144.

    Article  MATH  Google Scholar 

  13. Halldórsson, M. (2009). Wireless scheduling with power control. In Algorithms—ESA (vol. 5757, pp. 361–372).

  14. Sanghavi, S., Bui, L., & Srikant, R. (2007). Distributed link scheduling with constant overhead. In Proceedings of the ACM SIGMETRICS (pp. 313–324).

  15. Tang, S.-J., Li, X.-Y., Wu, X., Wu, Y., Mao, X., Xu, P., et al. (2009). Low complexity stable link scheduling for maximizing throughput in wireless networks. In Proceedings of the IEEE SECON (pp. 1–9).

  16. Modiano, E., Shah, D., & Zussman, G. (2006). Maximizing throughput in wireless networks via gossiping. In Proceedings of the ACM SIGMETRICS (pp. 27–38).

  17. Lin, X., & Rasool, S. B. (2006). Constant-time distributed scheduling policies for ad hoc wireless networks. In Proceedings of the IEEE CDC (pp. 1258–1263).

  18. Joo, C., & Shroff, N. B. (2009). Performance of random access scheduling schemes in multi-hop wireless networks. IEEE/ACM Transactions on Networking, 17, 1481–1493.

    Article  Google Scholar 

  19. Joo, C., Lin, X., & Shroff, N. B. (2008). Understanding the capacity region of the greedy maximal scheduling algorithm in multi-hop wireless networks. In Proceedings of the IEEE Infocom (pp. 1103–1111).

  20. Tassiulas, L., & Ephremides, A. (1998.) Linear complexity algorithms for maximum throughput in radio networks and input queued switches. In Proceedings of the IEEE Infocom (pp. 533–539).

  21. Chaporkar, P., Kar, K., & Sarkar, S. (2008). Throughput and fairness guarantees through maximal scheduling in wireless networks. IEEE/ACM Transactions on Information Theory, 54, 572–594.

    Article  MathSciNet  MATH  Google Scholar 

  22. Wu, D., Bao, L., & Liu, C. H. (2013). Scalable channel allocation and access scheduling for wireless internet-of-things. IEEE Sensors Journal, 13(10), 3596–3604.

    Article  Google Scholar 

  23. Wu, D., Yang, S.-H., Bao, L., & Liu, C. H. (2014). Joint multi-radio multi-channel assignment, scheduling, and routing in wireless mesh networks. Wireless Networks, 20(1), 11–24.

    Article  Google Scholar 

  24. Chafekar, D., Kumar, V., Marathe, M., Parthasarathy, S., & Srinivasan, A. (2008). Arrpoximation algorithms for computing capacity of wireless networks with SINR constraints. In Proceedings of the IEEE Infocom (pp. 1166–1174).

  25. Asgeirsson, E., Halldórsson, M., & Mitra, P. (2012). A fully distributed algorithm for throughput performance in wireless networks. In Information sciences and systems (CISS) (pp. 1 –5).

  26. Ryu, J., Joo, C., Kwon, T. T., Shroff, N. B., & Choi, Y. (2010). Distributed SINR based scheduling algorithm for multi-hop wireless networks. In Proceedings of the ACM MSWIM (pp. 376–380).

  27. Asgeirsson, E. I., Halldórsson, M. M., & Mitra, P. (2012). Wireless network stability in the sinr model. CoRR, abs/1210.4446.

  28. Lee, H.-W., Modiano, E., & Le, L. B. (2009). Distributed throughput maximization in wireless networks via random power allocation. In Modeling and optimization in mobile, ad hoc, and wireless networks (WiOPT) (pp. 1 –9).

  29. Halldórsson, M. M., & Mitra, P. (2011). Wireless capacity with oblivious power in general metrics. In Proceedings of the twenty-second annual ACM-SIAM symposium on discrete algorithms (pp. 1538–1548).

  30. Kesselheim, T. (2011). A constant-factor approximation for wireless capacity maximization with power control in the SINR model. In Proceedings of the twenty-second annual ACM-SIAM symposium on discrete algorithms (pp. 1549–1559).

  31. Wan, P.-J., Chen, D. C., Dai, G. J., Wang, Z., & Yao, F. (2012). Maximizing capacity with power control under physical interference model in duplex mode. In Proceedings of the IEEE Infocom (pp. 415–423).

  32. Pei, G., & Kumar, V. S. A. (2012). Distributed algorithms for maximum link scheduling under the physical interference model. CoRR, abs/1208.0811.

  33. Halldórsson, M. M., Holzer, S., Mitra, P., & Wattenhofer, R. (2012). The power of non-uniform wireless power. CoRR, abs/1210.3371.

  34. Blough, D. M., Resta, G., & Santi, P. (2010). Approximation algorithms for wireless link scheduling with SINR-based inteference. IEEE/ACM Transactions on Networking, 18, 1701–1712.

    Article  Google Scholar 

  35. Xu, X., Cao, J., & Li, X.-Y. (2012). Mlls: Minimum length link scheduling under physical interference model. CoRR, abs/1208.0627, 2012.

  36. Goussevskaia, O., Oswald, Y., & Wattenhofer, R. (2007). Complexity in geometric SINR. In Proceedings of the ACM Mobihoc (pp. 100–109).

  37. Lin, X., & Shroff, N. B. (2005). The impact of imperfect scheduling on cross-layer rate control in multihop wireless networks. In Proceedings of the IEEE Infocom (pp. 1804–1814).

  38. Wan, P., Ma, C., Tang, S., & Xu, B. (2011). Maximizing capacity with power control under physical interference model in simplex mode. Wireless Algorithms, Systems, and Applications, 6843, 84–95.

  39. Gupta, P., & Kumar, P. (2000). The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2), 388–404.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The research of Xiang-Yang Li is partially supported by NSF CNS-1035894, NSF ECCS-1247944, NSF CMMI 1436786. The research of Min Liu is supported by the National Natural Science Foundation of China (Nos. 61132001, 61120106008, 61472402, 61472404, 61272474 and 61202410).

Author information

Authors and Affiliations

  1. Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China

    Yaqin Zhou, Min Liu & Zhongcheng Li

  2. School of Computer Science and Technology, University of Science and Technology of China, Hefei, 230026, China

    Xiang-Yang Li

  3. Department of Computer Science, Illinois Institute of Technology, Chicago, IL, 60616-3793, USA

    Xiang-Yang Li

  4. Center of Cybersecurity and Wireless Innovations, University of Toledo, Toledo, OH, USA

    Xiaohua Xu

Authors
  1. Yaqin Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xiang-Yang Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Min Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Zhongcheng Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Xiaohua Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xiang-Yang Li.

Appendix

Appendix

Proof

Our proof bases on the fact of fading metrics [13]. In fading metrics the path loss exponent \(\kappa\) must be strictly greater than the doubling dimension of the metric, and the doubling dimension \(A=n\) for the \(n-\)dimensional Euclidean space. We have assumed the Euclidean plane and the path loss exponent \(\kappa > 2\), therefore these assumptions construct a fading metric of doubling dimension \(A=2\). For the fading metric of doubling dimension A, there are at most \(Cg^A\) balls of radius Z inside a ball of radius gZ for any \(g > 0\). Here \(C=\frac{1}{6}\pi \sqrt{3} \approx 0.907\) for the Euclidean plane. A ball of radius \(\mu\), centered at v is defined by \(B(v,\mu )\).

Let \(X_g = \{w \in V(L) | d(w,v) < gd \slash 2 \}\) for \(g>0\). The distance between any two nodes in V(L) is at least d. It implies \(B(v,(g+1)d \slash 2)\) contains all balls of radius of \(d \slash 2\) centered at the nodes in \(X_g\) and these balls do not intersect. We have \(|X_2|=0\) for the smallest mutual distance between any pair of nodes is d. Then for each node \(v \in V(L),\) it holds that,

$$\begin{aligned} \sum _{w \in V(L)} {\frac{R^{\kappa }}{d(w,v)^{\kappa }}} &\le \sum _{g=3}^{\infty }|X_{g} \backslash X_{g-1}| \frac{R^{\kappa }}{[(g-1) d \slash 2]^{\kappa }} \\ &\le \frac{R^{\kappa }}{(d \slash 2)^{\kappa }} \cdot \sum _{g=3}^{\infty } |X_{g}| \left( \frac{1}{(g-1)^{\kappa }}-\frac{1}{g^{\kappa }}\right) \\ &\le \frac{R^{\kappa }}{(d \slash 2)^{\kappa }} \cdot \sum _{g=3}^{\infty } |X_{g}| \frac{\kappa }{(g-1)^{\kappa +1}} \\ & \le \frac{R^{\kappa }}{(d \slash 2)^{\kappa }} \sum _{g=3}^{\infty } C \cdot (g+1)^{A} \frac{\kappa }{(g-1)^{\kappa +1}} \\ & < \frac{ 2^{2\kappa +1}\kappa C}{\theta ^{\kappa } (\kappa -A)} = \frac{ 2^{2\kappa +1} \sqrt{3} \pi \kappa }{6 (\kappa -2) \theta ^{\kappa } } = O(1/\theta ^{\kappa }) \end{aligned}$$

\(\square\)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhou, Y., Li, XY., Liu, M. et al. Link scheduling for throughput maximization in multihop wireless networks under physical interference. Wireless Netw 23, 2415–2430 (2017). https://doi.org/10.1007/s11276-016-1276-1

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11276-016-1276-1

Keywords

Search

Navigation