Vol 6, No 1 (2015) > Electrical, Electronics and Computer Engineering >

Exploiting Geometrical Node Location for Improving Spatial Reuse in SINR-based STDMA Multi-hop Link Scheduling Algorithm

Nachwan Adriansyah, Muhamad Asvial, Bagio Budiarjo


Abstract: This paper proposes a novel approximation for a Spatial Time Division Multiple Access (STDMA) link-scheduling algorithm based on geometrical node exploitation to improve spatial reuse performance. The geometrical location of nodes was exploited in order to reduce computational complexity and to achieve higher accuracy in transmission to satisfy the Signal to Interference and Noise Ratio (SINR) requirement. The process of SINR global checking is a main constraint in the SINR based interference model but is reduced through geometrical partition and interference approximations based on geometrical node locations. Simulation results show that the proposed algorithm increases the spatial reuse performance in comparison to the greedy physical interference model in similar scenarios. The model utilizing geometrical partition exhibits lower complexity compared to the pure physical interference model that includes SINR global checking.
Keywords: Approximation algorithm; Geometrical node location exploitation; Link scheduling; Mesh network; STDMA

Full PDF Download


Adriansyah, N.M., Asvial, M., Budiardjo, B., XXXX. Modified Greedy Physical Link Scheduling Algorithm for Improving Wireless Mesh Network Performance. TELKOMNIKA (In-press), pp. 1–9

Akyildiz, I.F., Wang, X., Wang, W., 2005. Wireless Mesh Networks: A Survey. Journal of Computer Networks, Volume 47, pp. 445–487

Blough, D.M., Resta, G., Santi, P., 2010. Approximation Algorithms for Wireless Link Scheduling with SINR-Based Interference. IEEE/ACM Transactions on Networking, Volume 18(6), pp. 1701–1712

Brar, G., Blough, D.M., Santi, P., 2006. Computationally Efficient Scheduling with the Physical Interference Model for Throughput Improvement in Wireless Mesh Networks. In Proceedings of the 12th Annual International Conference on Mobile Computing and Networking (ACM). pp. 2–13

Bruno, R., Conti, M., Gregori, E., 2005. Mesh Networks: Commodity Multihop Ad Hoc Networks. Communications Magazine, IEEE, (March), pp. 123–131

Gore, A.D., Karandikar, A., 2011. Link Scheduling Algorithms for Wireless Mesh Networks. Communications Surveys & Tutorials, IEEE, Volume 13(2), pp. 258–273

Grönkvist, J., Hansson, A., 2001. Comparison between Graph-based and Interference-based STDMA Scheduling. Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking & Computing - MobiHoc ’01, p. 255

Gupta, P., Kumar, P.R., 2000. The Capacity of Wireless Networks. IEEE Transactions on Information Theory, Volume 46(2), pp. 388–404

Liu, W., et al., 2012. A Novel Link Scheduling Algorithm for Spatial Reuse in Wireless Networks. IEEE Vehicular Technology Conference (VTC Fall), pp. 1–5

Nelson, R., Kleinrock, L., 1985. Spatial TDMA: A Collision-Free multihop Channel Access Protocol. IEEE Transactions on Communications, COM-33(9)

Niculescu, D., Nath, B., 2003. Ad Hoc Positioning System ( APS ) Using AOA. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications (INFOCOM 2003), Volume 3(C), pp. 1734–1743

Ramanathan, S., Lloyd, E.L., 1993. Scheduling Algorithms for Multihop Radio Networks. IEEE/ACM Transactions on Networking, Volume 1(2), pp. 166–177

Shariat, M., et al., 2009. Scheduling as an Important Cross-layer Operation for Emerging Broadband Wireless Systems. IEEE Communications Surveys & Tutorials, Volume 11(2), pp. 74–86