Home   >   CSC-OpenAccess Library   >    Manuscript Information
Design And Evaluation of Time Slot Assignment Algorithm For IEEE 802.16j Relay Networks
Go Hasegawa, Shoichi Takagi, Yoshiaki Taniguchi, Hirotaka Nakano, Morito Matsuoka
Pages - 50 - 65     |    Revised - 10-05-2014     |    Published - 01-06-2014
Volume - 6   Issue - 3    |    Publication Date - June 2014  Table of Contents
MORE INFORMATION
KEYWORDS
IEEE 802.16j, Radio Interference, TDMA, Time Slot Assignment, Heuristic Algorithm.
ABSTRACT
In IEEE 802.16j relay networks, wireless communications are carried out based on TDMA where the wireless network resources are divided into multiple time slots and they are assigned to wireless links between relay nodes as transmission opportunities. The network performance is improved by decreasing the total number of different time slots assigned to all links in a single scheduling cycle, because it brings the increase in the transmission opportunities of the links per unit time. Although it can be achieved when multiple links utilize the same time slot, the capacity of such links is degraded due to the radio interference. On the other hand, since all links in the network need to have enough time slots to accommodate their traffic load, degrading the link capacity may increase the total number of different time slots in the scheduling cycle. Therefore, we should determine the time slot assignment by considering the above-mentioned tradeoff relationship. In this paper, we propose heuristic algorithms for time slot assignment problem in IEEE 802.16j relay networks, and evaluate them through extensive simulation experiments. Two algorithms based on different heuristic are introduced. One algorithm assigns a set of time slots to links by a greedy approach. The other algorithm determines a set of links that use a time slot by a brute-force search for maximizing the total link capacity. Performance evaluation results exhibit that the proposed algorithms reduces around 34% and 39% of the total time slots compared with the case where no link utilizes the same time slot, respectively. Meanwhile, they also show that calculation time of the latter algorithm is longer than that of the former algorithm to reduce the total time slots. Thus, we show that there is a tradeoff between performance and calculation time.
1 Google Scholar 
2 CiteSeerX 
3 Scribd 
4 SlideShare 
5 PdfSR 
A. Chockalingam, M. Zorzi, L. Milstein, and P. Venkataram, “Performance of a wireless access protocol on correlated Rayleigh fading channels with capture,” IEEE Transactions on Communications, vol. 46, no. 5, pp. 644–655, May 1998.
A. J. Goldsmith and S. G. Chua, “Adaptive coded modulation for fading channels,”Communications, vol. 46, no. 5, pp. 595–602, June 1998.
A. P. Subramanian, M. M. Buddhikot, and S. Miller, “Interference aware routing in multiradio wireless mesh networks,” in Proceedings of WiMesh 2006, pp. 55–63, Sept 2006.
B. Jaumard, T. M. Murillo, and S. Sebbah, “Scheduling vs. pseudo-scheduling models in IEEE 802.16j wireless relay networks,” in Proceedings of QBSC 2012, pp. 101–106, May2012.
B. Sklar, “Rayleigh fading channels in mobile digital communication systems .I.Characterization,” IEEE Communications Magazine, vol. 35, no. 7, pp. 90–100, July 1997.
C. Cicconetti, I. F. Akyildiz, and L. Lenzini, “Bandwidth balancing in multi-channel IEEE 802.16 wireless mesh networks,” in Proceedings of INFOCOM 2007, pp. 2108 –2116, May 2007.
D. Ghosh, A. Gupta, and P. Mohapatra, “Admission control and interference-aware scheduling in multi-hop WiMAX networks,” in Proceedings of MASS 2007, pp. 1–9, Oct 2007.
F. Aurenhammer, “Voronoi diagrams - a survey of a fundamental geometric data structure,”ACM Computing Surveys, vol. 23, no. 3, pp. 345–405, Sept 1991.
F. Li, Y. Wang, X.-Y. Li, A. Nusairat, and Y. Wu, “Gateway placement for throughput optimization in wireless mesh networks,” Mobile Networks and Applications, vol. 13, no. 1-2,pp. 198–211, Apr 2008.
G. Farhadi and norman C. Beaulieu, “Ergodic capacity of multi-hop wireless relaying systems in Rayleigh fading,” in Proceedings of GLOBECOM 2008, pp. 1–6, Dec 2008.
G. Hasegawa, R. Ishii, Y. Taniguchi, and H. Nakano, “Time slot assignment algorithms for reducing transmission latency in IEEE 802.16j multi-hop relay networks,” Journal of Communications and Networking, vol. 2, no. 3, Mar 2012.
G. Zhou, T. He, J. A. Stankovic, and T. Abdelzaher, “RID: Radio interference detection in wireless sensor networks,” in Proceedings of INFOCOM 2005, vol. 2, pp. 891–901, Mar 2005.
I. F. Akyildiz, X. Wang, and W. Wang, “Wireless mesh networks: a survey,” Computer Networks, vol. 47, no. 4, pp. 445–487, Mar 2005.
I.-K. Fu,W.-H. Sheen, and F.-C. Ren, “Deployment and radio resource reuse in IEEE 802.16j multi-hop relay network in manhattan-like environment,” in Proceedings of ICICS 2007, pp.1–5, Dec 2007.
IEEE Std 802.16-2009, “IEEE standard for local and metropolitan area networks, part 16: Air interface for broadband wireless access systems,,” IEEE Standard for Local and metropolitan area networks, May 2009.
IEEE Std 802.16e-2005 and IEEE Std 802.16-2004/Cor 1-2005, “IEEE standard for local and metropolitan area networks part 16: Air interface for fixed and mobile broadband wireless access systems amendment 2: Physical and medium access control layers for combined fixed and mobile operation in licensed bands and corrigendum 1,” IEEE Std 802.16e-2005 and IEEE Std 802.16-2004/Cor 1-2005 (Amendment and Corrigendum to IEEE Std 802.16-2004), Feb 2006.
IEEE Std 802.16j-2009, “IEEE standard for local and metropolitan area networks part 16: Air interface for broadband wireless access systems amendment 1: Multiple relay specification,”IEEE Standard for Local and metropolitan area networks, June 2009.
L. Kleinrock and J. Silvester, “Spatial reuse in multihop packet radio networks,” Proceedings of the IEEE, vol. 75, no. 1, pp. 156–167, Jan 1987.
M. Haenggi, “On routing in random Rayleigh fading networks,” IEEE Transactions on Wireless Communications, vol. 4, no. 4, pp. 1553 – 1562, July 2005.
M. Zorzi and R. Rao, “Capture and retransmission control in mobile radio,” IEEE Journal on Selected Areas in Communications, vol. 12, no. 8, pp. 1289–1298, Oct 1994.
M. Zorziy, R. R. Raoz, and L. B. Milstein, “On the accuracy of a first-order markov model for data transmission on fading channels,” in Proceedings of IEEE ICUPC ’95, pp. 211–215,Nov 1995.
N. A. Abu Ali, A.-E. M. Taha, H. S. Hassanein, and H. T. Mouftah, “IEEE 802.16 mesh schedulers: Issues and design challenges,” IEEE Network, vol. 22, no. 1, pp. 58 –65, Feb 2008.
P. Djukic and S. Valaee, “Link scheduling for minimum delay in spatial re-use TDMA,” in Proceedings of INFOCOM 2007, pp. 28 –36, May 2007.
P. Gupta and P. R. Kumar, “The capacity of wireless networks,” IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 388–404, Mar 2000.
Q. Liu, S. Zhou, and G. B. Giannakis, “Queuing with adaptive modulation and coding over wireless links: Cross-layer analysis and design,” IEEE Transactions on Wireless Communications, vol. 4, no. 3, pp. 1142–1153, May 2005.
Q. Liu, X.Wang, and G. B. Giannakis, “A cross-layer scheduling algorithm with QoS support in wireless networks,” IEEE Transactions on Vehicular Technology, vol. 55, no. 3, pp. 839–847, May 2006.
R. Fantacci, D. Marabissi, D. Tarchi, and I. Habib, “Adaptive modulation and coding techniques for OFDMA systems,” IEEE Transactions on Wireless Communications, vol. 8,no. 9, pp. 4876–4883, Sept 2009.
R. Fei, K. Yang, S. Ou, and H.-H. Chen, “QoS-aware two-level dynamic uplink bandwidth allocation algorithms in IEEE 802.16j based vehicular networks,” Wireless Personal Communications, vol. 56, no. 3, pp. 417–433, Feb. 2011.
R. Nelson and L. Kleinrock, “Spatial TDMA: A collision-free multihop channel access protocol,” Communications, vol. 33, no. 9, pp. 934 – 944, Sept 1985.
S. C. Ergen and P. Varaiya, “TDMA scheduling algorithms for wireless sensor networks,”Wireless Networks, vol. 16, no. 4, pp. 985–997, May 2010.
S. Catreux, V. Erceg, D. Gesbert, and R.W. Heath, “Adaptive modulation and MIMO coding for broadband wireless data networks,” IEEE Communications Magazine, vol. 40, no. 6, pp.108–115, June 2002.
S. Kompella, J. E. Wieselthier, A. Ephremides, H. D. Sherali, and G. D. Nguyen, “On optimal SINR-based scheduling in multihop wireless networks,” IEEE/ACM Transactions on Networking, vol. 18, no. 6, pp. 1713–1724, Dec 2010.
S. Ramanathan and E. Lloyd, “Scheduling algorithms for multihop radio networks,”IEEE/ACM Transactions on Networking, vol. 1, no. 2, pp. 166–177, Apr 1993.
S. W. Kim, J. Y. Jung, and J. W. Jang, “Frequency reuse during relay transmission for twohop IEEE 802.16j relay networks,” in Proceedings of WCSP 2009, pp. 1–5, Nov 2009.
S. W. Peters and R. W. Heath, “The future of WiMAX: Multihop relaying with IEEE 802.16j,”IEEE Communications Magazine, vol. 47, no. 1, pp. 104–111, Jan. 2009.
V. Genc, S. Murphy, Y. Yu, and J. Murphy, “IEEE 802.16j relay-based wireless access networks: An overview,” Wireless Communications, vol. 15, no. 5, pp. 56–63, Oct 2008.
W. Wang, C. Chen, Z. Guo, J. Cai, and X. S. Shen, “Isolation band based frequency reuse scheme for IEEE 802.16j wireless relay networks,” in Proceedings of QSHINE 2008, pp. 1–7, July 2008.
W. Wang, Y. Wang, X.-Y. Li, W.-Z. Song, and O. Frieder, “Efficient interference-aware TDMA link scheduling for static wireless networks,” in Proceedings of ACM MOBICOM 2006, pp.262–273, Sept 2006.
W.-H. Liao, K.-P. Shih, C. Liu, A. K. Dubey, S. Arora, and S. P. Kedia, “An efficient scheduling algorithm for radio resource reuse in IEEE 802.16j multi-hop relay networks,”Computers and Electrical Engineering, vol. 37, no. 4, pp. 511–525, July 2011.
X. Liu and M. Haenggi, “Performance analysis of Rayleigh fading ad hoc networks with regular topology,” in Proceedings of GLOBECOM 2005, vol. 5, pp. 2725 –2729, Dec 2005.
Associate Professor Go Hasegawa
Osaka University - Japan
hasegawa@cmc.osaka-u.ac.jp
Mr. Shoichi Takagi
Osaka University - Japan
Dr. Yoshiaki Taniguchi
Osaka University - Japan
Professor Hirotaka Nakano
Osaka University - Japan
Professor Morito Matsuoka
Osaka University - Japan


CREATE AUTHOR ACCOUNT
 
LAUNCH YOUR SPECIAL ISSUE
View all special issues >>
 
PUBLICATION VIDEOS