UNIVERSITI PUTRA MALAYSIA

AHMAD SABRI MOUSA SAQER

FK 2012 63

EFFICIENT SIGNALING SCHEDULE FOR CENTRALIZED AND DISTRIBUTED SCHEDULING ALGORITHMS FOR WIMAX MULTI-HOP

RELAY NETWORKS

© COPYRIG

HT UPM

i

EFFICIENT SIGNALING SCHEDULE FOR CENTRALIZED AND

DISTRIBUTED SCHEDULING ALGORITHMS FOR WIMAX MULTI-HOP

RELAY NETWORKS

By

AHMAD SABRI MOUSA SAQER

Thesis Submitted to the School of Graduate Studies, University Putra Malaysia,

in Fulfillment of the Requirements for Degree of Doctor of Philosophy

December 2011

© COPYRIG

HT UPM

ii

DEDICATION

قال تعاىل:

نا اإلنسان بوالديه حلته أمه )) (( وهنا على وهن وفصاله ف عامي أن اشكر ل ولوالديك إل المصي ووصي

14لقمان

This thesis is dedicated to:

my beloved parents,

my dearest wife and daughter who have waiting for me for a long time,

my brothers and sisters,

my parents, brother and sisters in-laws

all of my friends

and to my beloved home land Jordan.

© COPYRIG

HT UPM

iii

ABSTRACT

Abstract of the thesis presented to the Senate of Universiti Putra Malaysia in fulfillment

of the requirement for the degree of Doctor of Philosophy

EFFICIENT SIGNALING SCHEDULE FOR CENTRALIZED AND

DISTRIBUTED SCHEDULING ALGORITHMS FOR WIMAX MULTI-HOP

RELAY NETWORKS

By

AHMAD SABRI MOUSA SAQER

December 2011

Chairman: Raja Syamsul Azmir bin Raja Abdullah, PhD

Faculty: Engineering

The Institute of Electric and Electronic Engineers (IEEE) 802.16j standard uses relay

station to extend coverage and enhance throughput for remote users at the base station.

The IEEE 802.16 standards specify services and how the transmissions should occur.

However, the way how to run these services and when the transmission should be

started are the task of scheduling algorithms which are not specified in the IEEE 802.16

standards. The IEEE standards left the design of scheduling algorithms open for the

manufacturers. However, the scheduler is a very important component in wireless

systems and the scheduling period presents the most common challenging issue in

terms of time delay. This thesis presents new scheduling algorithms; centralized and

distributed scheduling algorithms, for the WiMAX Multihop Relay (MR) Networks

taking into account the bandwidth allocation signaling scheme for both the centralized

and distributed scheduling modes. The proposed algorithms aim at making the MR

© COPYRIG

HT UPM

iv

network auto-configurable and flexible through reducing overhead and improving the

network throughput. The proposed algorithms were also customized to produce

signaling with less time delay over relay-link.

In order to evaluate the proposed algorithms and validate their efficiency for IEEE

802.16j networks, the authors simulated the algorithms in QualNet simulator.

Evaluation of the proposed centralized scheduling algorithm (MR-CSA) was carried

out through comparing its performance with those of the Round Robin and the

centralized pairing algorithms. On the other hand, the proposed distributed scheduling

algorithm (MR-DSA) was evaluated by comparing its performance against

performances of Greedy and the factor-graph-based low-complexity distributed

scheduling algorithm (FGDS) algorithms in terms of delay, throughput, and overhead.

Validation of the proposed algorithm (MR-CSA) was based on comparison of its

performance with the performance of the centralized pairing algorithm while the

proposed MR-DSA algorithm was validated through comparing its performance against

that of the factor-graph-based low-complexity distributed scheduling algorithm (FGDS)

algorithms in terms of throughput and the average packet throughput. The simulation

results highlighted that the proposed algorithms (MR-CSA and MR-DSA) outperform

all previous algorithms with the current signaling scheme. The proposed algorithms

achieve higher performance in terms of end-to-end delay, throughput, overhead, link

utilization, and fairness index than all other algorithms.

© COPYRIG

HT UPM

v

ABSTRAK

Abstrak tesis ini dikemukakan kepada Senat Universiti Putra Malaysia sebagai

memenuhi keperluan untuk ijazah Master of Science

PENJADUALAN PROSEDUR PENGIRAAN TERPUSAT DAN TERAGIHKAN

UNTUK PELBAGAI LALUAN PENGHANTARAN DALAM JARINGAN

WIMAX

Oleh

AHMAD SABRI MOUSA SAQER

Disember 2011

Pengerusi: Raja Syamsul Azmir bin Raja Abdullah, PhD

Fakulti: Kejuruteraan

Standard piawaian 802.16j Institut Jurutera Elektrik dan Elektronik (Institute of

Electric and Electronic Engineers (IEEE)) menggunakan stesen penghantar untuk

meluaskan liputan dan seterusnya meningkatkan jumlah penghantaran bagi pengguna

pengguna terpencil di stesen pengkalan. Standard piawaian IEEE 802.16 menentukan

jenis perkhidmatan dan cara bagaimana penghantaran tersebut sepatutnya berlaku.

Walau bagaimana pun, cara bagaimana perkhidmatan ini dilakukan dan bilakah masa

yg sepatutnya penghantaran bermula merupakan tugas bagi penjadualan prosedur

pengiraan. Ini kerana penjadualan ini tidak ditentukan dalam standard piawaian IEEE

8012.6. Standard piawaian IEEE meninggalkan reka bentuk prosedur pengiraan

berjadual kepada para pihak pengeluar. Akan tetapi, susunan acara merupakan

komponen yang terpenting dalam system tanpa wayar dan tempoh masa bagi

penjadualan merupakan isu yang paling mencabar dalam soal masa dan penangguhan

© COPYRIG

HT UPM

vi

masa. Tesis ini membentangkan prosedur pengiraan berjadual yang baru iaitu

pemusatan dan jadual penyebaran prosedur pengiraan untuk menghantarnya dalam

pelbagai laluan penghantaran (Multihop Relay (MR)) bagi jaringan WIMAX. Justeru,

ia mengambil kira lebar jalur pemberi isyarat yang diperuntukkan bagi cara pemusatan

dan cara penyebaran terjadual. Matlamat prosedur pengiraan yang dicadangkan ini

adalah untuk melaksanakan rangkaian MR yang tersusun dengan sendirinya dan

fleksibel melalui pengurangan lebihan muatan dan memperbaiki jumlah penghantaran

jaringan. Prosedur pengiraan yang dicadangkan ini juga disesuaikan bagi menghasilkan

pemberian isyarat dengan pengurangan pertangguhan masa berbanding pautan

pemberian dan penerimaan isyarat.

Bagi menilai prosedur pengiraan yang dicadangkan dan memperakiu kecekapan

perlaksanaanya dalam rangkaian IEEE 802.16j, penulis mensimulasikan prosedur

pengiraan menggunakan pensimulasi QualNet. Penilaian bagi penjadualan prosedur

pengiraan terpusat yang dicadangkan dilaksanakan dengan cara membandingkan hasil

prestasinya dengan Round Robin dan pasangan prosedur pengiraan terpusat. Dalam

pada itu, pengagihan penjadualan prosedur terpusat (MR-DSA) dinilai dengan cara

membandingkan kecekapannya melawan kecekapan Greedy dan graf faktor kerumitan

rendah dalam pengagihan penjadualan prosedur pengiraan (FGDS). Ini berkaitan

dengan soal penangguhan dari satu penghujung ke penghujung seterusnya, daya

pemprosesan dan lebihan muatan. Pengesahan prosedur pengiraan yang dicadangkan

adalah berasaskan kepada pembandingan hasil prestasinya dengan prestasi bagi

penjadualan prosedur terpusat. Dalam pada itu, prosedur pengiraan MR-DSA yang

dicadangkan telah ditentu sahkan melalui perbandingan prestasinya melawan graf

© COPYRIG

HT UPM

vii

faktor kerumitan rendah dalam pengagihan penjadualan prosedur pengiraan (FGDS).

Ia meliputi persoalan berkaitan daya pemprosesan dan purata pemprosesan paket data.

Keputusan simulasi menekankan bahawa algoritma yang dicadangkan (MR-CSA dan

MR-DSA) bersesuaian dengan semua algoritma yang terdahulu dengan skim isyarat

semasa. Algoritma yang dicadangkan telah mencapai prestasi yang lebih tinggi dari

segi kelewatan akhir-ke-hujung, throughput, overhead, penggunaan link, dan indeks

keadilan daripada semua algoritma yang lain.

© COPYRIG

HT UPM

viii

ACKNOWLEDGEMENTS

First and foremost, I would like to thank the most gracious Allah for giving me the

strength, patience, courage, and determination for completing this work, Alhamdulillah.

All grace and thanks belongs to Almighty Allah. This works would not have been

accomplished without the help of so many people. In the following lines is a brief

account of some but not all who deserve to be thanked.

I would like to extend my gratitude to Assoc. Prof. Dr. Raja Syamsul Azmir bin Raja

Abdullah for his supervision, advice, and guidance from the very early stage of this

research as well as giving me extraordinary experiences throughout the work. Above

all and the most needed, he provided me unflinching encouragement and support in

various ways. My deepest gratitude and appreciation also goes to Professor Dr.

Borhanuddin B. Mohd. Ali and Assoc. Prof. Dr. Nor Kamariah Noordin for their

valuable comments and suggestions which have been indispensable in the preparation

of this thesis; their professional review helped me to further improve my research and

thesis writing.

I do not know how to thank my family for their endless support encouragement and

love: my beloved father (Sabri Mousa), my beloved mother, my brothers and sisters

were always there for me and shared my joys and sorrows. They are always proud of

me. My wife and daughter are the meaning of my life, my wife always believed in me

more than I believe in myself. In fact, words can’t express my thanks and gratitude for

© COPYRIG

HT UPM

ix

her support and encouragements. Many thanks also to my mother in-law, brothers and

sisters in law.

I must extend my sincere thanks to the MIMOS Berhad, Malaysia, for their support and

help, and for the precious experience that I had achieved during the MIMOS Project

WiFi-WiMAX (WiWi) for more than two years. Very special thanks to my dear Dr.

Hafizal Mohamad for his great support and help. None the less, my gratitude to the

Malaysian people in general for their kindness and perfect hospitability in their green

land during my study period.

I truly appreciate the comrade of my friends in the lab and all around the world who

made my life more lively and colorful (Wael, Nidhal, Asem, Saleh, Samer, and all my

friends).

In the final note, I would like to extend my sincere thanks to all and sundry, who

helped me in one way or other, but whose names I have not been able to mention one

by one.

Always and forever, thank you Allah.

© COPYRIG

HT UPM

x

APPROVAL

I certify that a Thesis Examination Committee has met on (08 Dec 2011) to conduct the

final examination of (AHMAD SABRI MOUSA SAQER) on his thesis entitled

“Efficient Signaling Schedule for Centralized and Distributed Scheduling

Algorithms for WiMAX Multi-Hop Relay Networks” in accordance with the

Universities and University Colleges Act 1971 and the Constitution of the Universiti

Putra Malaysia [P.U.(A) 106] 15 March 1998. The Committee recommends that the

student be awarded the (Doctor of Philosophy degree).

Members of the Thesis Examination Committee were as follows:

Abdul Rahman b. Ramli, PhD

Associate Professor

Faculty of Engineering

(Chairman)

Mohd. Fadlee b. A.Rasid, PhD

Associate Professor

Faculty of Engineering

(Internal Examiner)

Mohamed Othman, PhD

Professor

Faculty of Computer Science and Information Technology

(Internal Examiner)

Lawrence Wong, PhD

Professor

Department of Electrical and Computer Engineering

National University of Singapore

(External Examiner)

SEOW HENG FONG, PhD

Professor and Deputy Dean

School of Graduate Studies

Universiti Putra Malaysia

Date:

© COPYRIG

HT UPM

xi

This thesis was submitted to the Senate of Universiti Putra Malaysia and has been

accepted as fulfillment of the requirement for the degree of Doctor of Philosophy. The

members of the Supervisory Committee were as follows:

Raja Syamsul Azmir b. Raja Abdullah, PhD

Associate Professor

Faculty of Engineering

University Putra Malaysia

(Chairman)

Borhanuddin B. Mohd. Ali, PhD

Professor

Faculty of Engineering

University Putra Malaysia

(Member)

Nor Kamariah Noordin, PhD

Associate Professor

Faculty of Engineering

University Putra Malaysia

(Member)

_________________________

BUJANG KIM HUAT, PhD

Professor and Dean

School of Graduate Studies

Universiti Putra Malaysia

Date:

© COPYRIG

HT UPM

xii

DECLARATION

I declare that the thesis is my original work except for quotations and citations which

have been duly acknowledged. I also declare that it has not been previously, and is not

concurrently, submitted for any other degree at Universiti Putra Malaysia or at any

other institutions.

AHMAD S. M. SAQER

Date: 27 April 2012

© COPYRIG

HT UPM

xiii

TABLE OF CONTENTS

Page

DEDICATION ii ABSTRACT iii ABSTRAK v ACKNOWLEDGEMENTS viii APPROVAL x DECLARATION xii LIST OF TABLES xv LIST OF FIGURES xvi

LIST OF APPENDICES xx LIST OF ABBREVIATIONS xxi

CHAPTER

1 INTRODUCTION 1 1.1 Background 1 1.2 Wireless Multihop Networks 3

1.2.1 Overview of WiMAX Multihop Mesh Networks 4 1.2.2 Overview of the WiMAX MR Networks 5

1.3 Scheduling in the WiMAX MR Networks 8 1.4 The Last Mile Problem 9

1.5 Aim and Objectives 11 1.6 Thesis Scope 12 1.7 Contributions 13 1.8 Thesis Organization 14

2 LITERATURE REVIEW 15 2.1 Overview 15 2.2 Overview of the WiMAX Network 16

2.3 The WiMAX MR Network Overview 24 2.3.1 The WiMAX MR Frame Structure 28 2.3.2 The WiMAX MR Protocol Stack 31 2.3.3 WiMAX Network Architecture 32

2.4 Scheduling in the WiMAX MR Networks 33 2.4.1 Scheduling Services and Connections 33 2.4.2 Bandwidth Allocation 37

2.4.3 Scheduling Techniques 40 2.5 Self-organizing Algorithms 44

2.5.1 Centralized Scheduling 47 2.5.2 Distributed Scheduling 50

2.6 Summary 53

3 CENTRALIZED SCHEDULING FOR WiMAX MR NETWORKS 56

3.1 Introduction 56

© COPYRIG

HT UPM

xiv

3.2 Bandwidth Allocation 58

3.2.1 Delay Analysis 59 3.2.2 The New Signaling Scheme 62

3.3 Centralized Scheduling 65 3.3.1 Centralized Scheduling Mechanism 65 3.3.2 The Proposed Centralized Scheduling Algorithm 71

3.4 System Description and Design Parameters 76 3.4.1 The Simulation Setup and Parameters 77 3.4.2 Performance Parameters 79 3.4.3 Performance Evaluation 81 3.4.4 Validation of the CPS and CS Algorithms 86 3.4.5 Results 88

3.5 Chapter Summary 101

4 DISTRIBUTED SCHEDULING FOR WiMAX MR NETWORKS 102 4.1 Introduction 102 4.2 Bandwidth Allocation with Distributed Scheduling 102

4.2.1 Delay Analysis 103 4.2.2 New Signaling Scheme 106

4.3 Distributed Scheduling 108 4.3.1 Distributed Scheduling Mechanism 108 4.3.2 Distributed Scheduling Algorithm 116

4.4 System Description and Design Parameters 121 4.4.1 The Simulation Setup 121

4.4.2 Performance Evaluation 122 4.4.3 Validation of the DPS and DS Algorithms 125 4.4.4 Results 127

4.5 Chapter Summary 137

5 CONCLUSION AND FUTURE WORK 139 5.1 Conclusion 139 5.2 Future Work 141

REFERENCES 143 APPENDICES 156 BIODATA OF STUDENT 172

LIST OF PUBLICATIONS 173