Journal Editorial Board Editor-in-ChiefProf. Thomas Byeongnam YOON, PhD.
Founding Editor-in-Chief
ICACT Transactions on the Advanced Communications Technology (TACT) Editors
Prof. Jun-Chul Chun, Kyonggi University, Korea
Dr. JongWon Kim, GIST (Gwangju Institute of Science & Technology), Korea
Dr. Xi Chen, State Grid Corparation of China, China
Prof. Arash Dana, Islamic Azad university , Central Tehran Branch, Iran
Dr. Pasquale Pace, University of Calabria - DEIS - Italy, Italy
Dr. Mitch Haspel, Stochastikos Solutions R&D, Israel
Prof. Shintaro Uno, Aichi University of Technology, Japan
Dr. Tony Tsang, Hong Kong Polytechnic UNiversity, Hong Kong
Prof. Kwang-Hoon Kim, Kyonggi University, Korea
Prof. Rosilah Hassan, Universiti Kebangsaan Malaysia(UKM), Malaysia
Dr. Sung Moon Shin, ETRI, Korea
Dr. Takahiro Matsumoto, Yamaguchi University, Japan
Dr. Christian Esteve Rothenberg, CPqD - R&D Center for. Telecommunications, Brazil
Prof. Lakshmi Prasad Saikia, Assam down town University, India
Prof. Moo Wan Kim, Tokyo University of Information Sciences, Japan
Prof. Yong-Hee Jeon, Catholic Univ. of Daegu, Korea
Dr. E.A.Mary Anita, Prathyusha Institute of Technology and Management, India
Dr. Chun-Hsin Wang, Chung Hua University, Taiwan
Prof. Wilaiporn Lee, King Mongkut’s University of Technology North, Thailand
Dr. Zhi-Qiang Yao, XiangTan University, China
Prof. Bin Shen, Chongqing Univ. of Posts and Telecommunications (CQUPT), China
Prof. Vishal Bharti, Dronacharya College of Engineering, India
Dr. Marsono, Muhammad Nadzir , Universiti Teknologi Malaysia, Malaysia
Mr. Muhammad Yasir Malik, Samsung Electronics, Korea
Prof. Yeonseung Ryu, Myongji University, Korea
Dr. Kyuchang Kang, ETRI, Korea
Prof. Plamena Zlateva, BAS(Bulgarian Academy of Sciences), Bulgaria
Dr. Pasi Ojala, University of Oulu, Finland
Prof. CheonShik Kim, Sejong University, Korea
Dr. Anna bruno, University of Salento, Italy
Prof. Jesuk Ko, Gwangju University, Korea
Dr. Saba Mahmood, Air University Islamabad Pakistan, Pakistan
Prof. Zhiming Cai, Macao University of Science and Technology, Macau
Prof. Man Soo Han, Mokpo National Univ., Korea
Mr. Jose Gutierrez, Aalborg University, Denmark

Copyright ⓒ 2014 GiRI (Global IT Research Institute)Dr. Youssef SAID, Tunisie Telecom, Tunisia
Dr. Noor Zaman, King Faisal University, Al Ahsa Hofuf, Saudi Arabia
Dr. Srinivas Mantha, SASTRA University, Thanjavur, India
Dr. Shahriar Mohammadi, KNTU University, IranProf. Beonsku An, Hongik University, korea
Dr. Guanbo Zheng, University of Houston, USA
Prof. Sangho Choe, The Catholic University of Korea, korea
Dr. Gyanendra Prasad Joshi, Yeungnam University, korea
Dr. Tae-Gyu Lee, Korea Institue of Industrial Technology(KITECH), korea
Prof. Ilkyeun Ra, University of Colorado Denver, USA
Dr. Yong Sun, Beijing University of Posts and Telecommunications, China
Dr. Yulei Wu, Chinese Academy of Sciences, China
Mr. Anup Thapa, Chosun University, korea
Dr. Vo Nguyen Quoc Bao, Posts and Telecommunications Institute of Technology, Vietnam
Dr. Harish Kumar, Bhagwant institute of technology, India
Dr. Jin REN, North china university of technology, China
Dr. Joseph Kandath, Electronics & Commn Engg, India
Dr. Mohamed M. A. Moustafa, Arab Information Union (AIU), Egypt
Dr. Mostafa Zaman Chowdhury, Kookmin University, Korea
Prof. Francis C.M. Lau, Hong Kong Polytechnic University, Hong Kong
Prof. Ju Bin Song, Kyung Hee University, korea
Prof. KyungHi Chang, Inha University, Korea
Prof. Sherif Welsen Shaker, Kuang-Chi Institute of Advanced Technology, China
Prof. Seung-Hoon Hwang, Dongguk University, Korea
Prof. Dal-Hwan Yoon, Semyung University, korea
Prof. Chongyang ZHANG, Shanghai Jiao Tong University, China
Dr. H K Lau, The Open University of Hong Kong, Honh Kong
Prof. Ying-Ren Chien, Department of Electrical Engineering, National Ilan University, Taiwan
Prof. Mai Yi-Ting, Hsiuping University of Science and Technology, Taiwan
Dr. Sang-Hwan Ryu, Korea Railroad Research Institute, Korea
Dr. Yung-Chien Shih, MediaTek Inc., Taiwan
Dr. Kuan Hoong Poo, Multimedia University, Malaysia
Dr. Michael Leung, CEng MIET SMIEEE, Hong Kong
Dr. Abu sahman Bin mohd Supa'at, Universiti Teknologi Malaysia, Malaysia
Prof. Amit Kumar Garg, Deenbandhu Chhotu Ram University of Science & Technology, India
Dr. Jens Myrup Pedersen, Aalborg University, Denmark
Dr. Augustine Ikechi Ukaegbu, KAIST, Korea
Dr. Jamshid Sangirov, KAIST, Korea
Prof. Ahmed Dooguy KORA, Ecole Sup. Multinationale des Telecommunications, Senegal
Dr. Se-Jin Oh, Korea Astronomy & Space Science Institute, Korea
Dr. Rajendra Prasad Mahajan, RGPV Bhopal, India
Dr. Woo-Jin Byun, ETRI, Korea
Dr. Mohammed M. Kadhum, School of Computing, Goodwin Hall, Queen's University , Canada
Prof. Seong Gon Choi, Chungbuk National University, Korea
Prof. Yao-Chung Chang, National Taitung University, Taiwan
Dr. Abdallah Handoura, Engineering school of Gabes - Tunisia, Tunisia
Dr. Gopal Chandra Manna, BSNL, India

Copyright ⓒ 2014 GiRI (Global IT Research Institute)Dr. Il Kwon Cho, National Information Society Agency, Korea
Prof. Jiann-Liang Chen, National Taiwan University of Science and Technology, Taiwan
Prof. Ruay-Shiung Chang, National Dong Hwa University, Taiwan
Dr. Vasaka Visoottiviseth, Mahidol University, Thailand
Prof. Dae-Ki Kang, Dongseo University, Korea
Dr. Yong-Sik Choi, Research Institute, IDLE co., ltd, Korea
Dr. Xuena Peng, Northeastern University, China
Dr. Ming-Shen Jian, National Formosa University, Taiwan
Dr. Soobin Lee, KAIST Institute for IT Convergence, Korea
Prof. Yongpan Liu, Tsinghua University, China
Prof. Chih-Lin HU, National Central University, Taiwan
Prof. Chen-Shie Ho, Oriental Institute of Technology, Taiwan
Dr. Hyoung-Jun Kim, ETRI, Korea
Prof. Bernard Cousin, IRISA/Universite de Rennes 1, France
Prof. Eun-young Lee, Dongduk Woman s University, Korea
Dr. Porkumaran K, NGP institute of technology India, India
Dr. Feng CHENG, Hasso Plattner Institute at University of Potsdam, Germany
Prof. El-Sayed M. El-Alfy, King Fahd University of Petroleum and Minerals, Saudi Arabia
Prof. Lin You, Hangzhou Dianzi Univ, China
Mr. Nicolai Kuntze, Fraunhofer Institute for Secure Information Technology, Germany
Dr. Min-Hong Yun, ETRI, Korea
Dr. Seong Joon Lee, Korea Electrotechnology Research Institute, korea
Dr. Kwihoon Kim, ETRI, Korea
Dr. Jin Woo HONG, Electronics and Telecommunications Research Inst., Korea
Dr. Heeseok Choi, KISTI(Korea Institute of Science and Technology Information), korea
Dr. Somkiat Kitjongthawonkul, Australian Catholic University, St Patrick's Campus, Australia
Dr. Dae Won Kim, ETRI, Korea
Dr. Ho-Jin CHOI, KAIST(Univ), Korea
Dr. Su-Cheng HAW, Multimedia University, Faculty of Information Technology, Malaysia
Dr. Myoung-Jin Kim, Soongsil University, Korea
Dr. Gyu Myoung Lee, Institut Mines-Telecom, Telecom SudParis, France
Dr. Dongkyun Kim, KISTI(Korea Institute of Science and Technology Information), Korea
Prof. Yoonhee Kim, Sookmyung Women s University, Korea
Prof. Li-Der Chou, National Central University, Taiwan
Prof. Young Woong Ko, Hallym University, Korea
Prof. Dimiter G. Velev, UNWE(University of National and World Economy), Bulgaria
Dr. Tadasuke Minagawa, Meiji University, Japan
Prof. Jun-Kyun Choi, KAIST (Univ.), Korea
Dr. Brownson ObaridoaObele, Hyundai Mobis Multimedia R&D Lab , Korea
Prof. Anisha Lal, VIT university, India
Dr. kyeong kang, University of technology sydney, faculty of engineering and IT , Australia
Prof. Chwen-Yea Lin, Tatung Institute of Commerce and Technology, Taiwan
Dr. Ting Peng, Chang'an University, China
Prof. ChaeSoo Kim, Donga University in Korea, Korea
Prof. kirankumar M. joshi, m.s.uni.of baroda, India
Dr. Chin-Feng Lin, National Taiwan Ocean University, Taiwan
Dr. Chang-shin Chung, TTA(Telecommunications Technology Association), Korea

Copyright ⓒ 2014 GiRI (Global IT Research Institute)Dr. Che-Sheng Chiu, Chunghwa Telecom Laboratories, Taiwan
Dr. Chirawat Kotchasarn, RMUTT, Thailand
Dr. Fateme Khalili, K.N.Toosi. University of Technology, IranDr. Izzeldin Ibrahim Mohamed Abdelaziz, Universiti Teknologi Malaysia , Malaysia
Dr. Kamrul Hasan Talukder, Khulna University, Bangladesh
Prof. HwaSung Kim, Kwangwoon University, Korea
Prof. Jongsub Moon, CIST, Korea University, Korea
Prof. Juinn-Horng Deng, Yuan Ze University, Taiwan
Dr. Yen-Wen Lin, National Taichung University, Taiwan
Prof. Junhui Zhao, Beijing Jiaotong University, China
Dr. JaeGwan Kim, SamsungThales co, Korea
Prof. Davar PISHVA, Ph.D., Asia Pacific University, Japan
Ms. Hela Mliki, National School of Engineers of Sfax, Tunisia
Prof. Amirmansour Nabavinejad, Ph.D., Sepahan Institute of Higher Education, Iran

Copyright ⓒ 2014 GiRI (Global IT Research Institute)

Editor Guide
 Introduction for Editor or Reviewer
All the editor group members are to be assigned as a evaluator(editor or reviewer) to submitted journal
papers at the discretion of the Editor-in-Chief. It will be informed by eMail with a Member Login ID and
Password.
Once logined the Website via the Member Login menu in left as a evaluator, you can find out the paper
assigned to you. You can evaluate it there. All the results of the evaluation are supposed to be shown in
the Author Homepage in the real time manner. You can also enter the Author Homepage assigned to
you by the Paper ID and the author's eMail address shown in your Evaluation Webpage. In the Author
Homepage, you can communicate each other efficiently under the peer review policy. Please don't missit!
All the editor group members are supposed to be candidates of a part of the editorial board, dependingon their contribution which comes from history of ICACT TACT as an active evaluator. Because the main
contribution comes from sincere paper reviewing role.

 Role of the Editor
The editor's primary responsibilities are to conduct the peer review process, and check the final cameraready manuscripts for any technical, grammatical or typographical errors.
As a member of the editorial board of the publication, the editor is responsible for ensuring that the
publication maintains the highest quality while adhering to the publication policies and procedures of
the ICACT TACT(Transactions on the Advanced Communications Technology).
For each paper that the editor-in-chief gets assigned, the Secretariat of ICACT Journal will send theeditor an eMail requesting the review process of the paper.
The editor is responsible to make a decision on an "accept", "reject", or "revision" to the Editor-in-Chief
via the Evaluation Webpage that can be shown in the Author Homepage also.

 Deadlines for Regular Review
Editor-in-Chief will assign a evalaution group( a Editor and 2 reviewers) in a week upon receiving acompleted Journal paper submission. Evaluators are given 2 weeks to review the paper. Editors are
given a week to submit a recommendation to the Editor-in-Chief via the evaluation Webpage, once all or
enough of the reviews have come in. In revision case, authors have a maximum of a month to submit
their revised manuscripts. The deadlines for the regular review process are as follows:

Copyright ⓒ 2014 GiRI (Global IT Research Institute)Evalution Procedure

Deadline

Selection of Evaluation Group
Review processing
Editor's recommendation
Final Decision Noticing

1 week2 weeks
1 week
1 week Making Decisions on Manuscript
Editor will make a decision on the disposition of the manuscript, based on remarks of the reviewers. The
editor's recommendation must be well justified and explained in detail. In cases where the revision isrequested, these should be clearly indicated and explained. The editor must then promptly convey thisdecision to the author. The author may contact the editor if instructions regarding amendments to themanuscript are unclear. All these actions could be done via the evaluation system in this Website. The
guidelines of decisions for publication are as follows:

Decision

Description

AcceptAn accept decision means that an editor is accepting the paper withno further modifications. The paper will not be seen again by theeditor or by the reviewers.
The manuscript is not suitable for the ICACT TACT publication.
The paper is conditionally accepted with some requirements. A
revision means that the paper should go back to the original
reviewers for a second round of reviews. We strongly discourage
editors from making a decision based on their own review of themanuscript if a revision had been previously required.

RejectRevision Role of the Reviewer
Reviewer Webpage:
Once logined the Member Login menu in left, you can find out papers assigned to you. You can alsologin the Author Homepage assigned to you with the paper ID and author's eMail address. In there you
can communicate each other via a Communication Channel Box.

Quick Review Required:
You are given 2 weeks for the first round of review and 1 week for the second round of review. You must
agree that time is so important for the rapidly changing IT technologies and applications trend. Pleaserespect the deadline. Authors undoubtedly appreciate your quick review.

Copyright ⓒ 2014 GiRI (Global IT Research Institute)Anonymity:
Do not identify yourself or your organization within the review text.

Review:
Reviewer will perform the paper review based on the main criteria provided below. Please provide
detailed public comments for each criterion, also available to the author.
 How this manuscript advances this field of research and/or contributes something new to theliterature?
 Relevance of this manuscript to the readers of TACT?
 Is the manuscript technically sound?
 Is the paper clearly written and well organized?
 Are all figures and tables appropriately provided and are their resolution good quality?
 Does the introduction state the objectives of the manuscript encouraging the reader to read on?
 Are the references relevant and complete?

Supply missing references:
Please supply any information that you think will be useful to the author in revision for enhancing
quality of the paperor for convincing him/her of the mistakes.

Review Comments:
If you find any already known results related to the manuscript, please give references to earlier papers
which contain these or similar results. If the reasoning is incorrect or ambiguous, please indicate
specifically where and why. If you would like to suggest that the paper be rewritten, give specificsuggestions regarding which parts of the paper should be deleted, added or modified, and pleaseindicate how.

Copyright ⓒ 2014 GiRI (Global IT Research Institute)Journal Procedure
Dear Author,

 You can see all your paper information & progress.
 Step 1. Journal Full Paper Submission
Using the Submit button, submit your journal paper through ICACT Website, then you will get newpaper ID of your journal, and send your journal Paper ID to the Secretariat@icact.org for the review andeditorial processing. Once you got your Journal paper ID, never submit again! Journal Paper/CRF
Template Step 2. Full Paper Review
Using the evaluation system in the ICACT Website, the editor, reviewer and author can communicate
each other for the good quality publication. It may take about 1 month.

 Step 3. Acceptance Notification
It officially informs acceptance, revision, or reject of submitted full paper after the full paper review
process.

Status
Acceptance
Revision
RejectActionGo to next Step.
Re-submit Full Paper within 1 month after Revision Notification.
Drop everything.

 Step 4. Payment Registration
So far it's free of charge in case of the journal promotion paper from the registered ICACT conference
paper! But you have to regist it, because you need your Journal Paper Registration ID for submission of
the final CRF manuscripts in the next step's process. Once you get your Registration ID, send it to
Secretariat@icact.org for further process.

 Step 5. Camera Ready Form (CRF) Manuscripts Submission
After you have received the confirmation notice from secretariat of ICACT, and then you are allowed tosubmit the final CRF manuscripts in PDF file form, the full paper and the Copyright Transfer Agreement.
Journal Paper Template, Copyright Form Template, BioAbstract Template,

Copyright ⓒ 2014 GiRI (Global IT Research Institute)Journal Submission Guide
All the Out-Standing ICACT conference papers have been invited to this "ICACT Transactions on the
Advanced Communications Technology" Journal, and also welcome all the authors whose conference
paper has been accepted by the ICACT Technical Program Committee, if you could extend new contents
at least 30% more than pure content of your conference paper. Journal paper must be followed toensure full compliance with the IEEE Journal Template Form attached on this page.

 How to submit your Journal paper and check the progress?
Step 1. Submit Using the Submit button, submit your journal paper through ICACT

Step 2. Confirm

Step 3. Review

Website, then you will get new paper ID of your journal, and send yourjournal Paper ID to the Secretariat@icact.org for the review and editorial
processing. Once you got your Journal paper ID, never submit again! Using
the Update button, you can change any information of journal paper
related or upload new full journal paper.
Secretariat is supposed to confirm all the necessary conditions of yourjournal paper to make it ready to review. In case of promotion from theconference paper to Journal paper, send us all the .DOC(or Latex) files ofyour ICACT conference paper and journal paper to evaluate the differenceof the pure contents in between at least 30% more to avoid the self
replication violation under scrutiny. The pure content does not include any
reference list, acknowledgement, Appendix and author biography
information.
Upon completing the confirmation, it gets started the review process thru
the Editor & Reviewer Guideline. Whenever you visit the Author
Homepage, you can check the progress status of your paper there fromstart to end like this, " Confirm OK! -> Gets started the review process > ...", in the Review Status column. Please don't miss it!

Copyright ⓒ 2014 GiRI (Global IT Research Institute)Volume 2, Issue 5

1

On ICI Canceller for Mobile OFDM DTV Receivers

290

Hai Minh TRAN*, Tomohisa WADA*** University of the Ryukyus, ** University of the Senbaru, Nishihara, Okinawa, Japan2

Simple and Feasible Dynamic Bandwidth and Polling Allocation for XGPON

298

Man-Soo HAN
Mokpo National Univ., Korea

3

Effective Use of Computational Resources in Multicore Distributed Systems

305

Hidehiro Kanemitsu*, Masaki Hanada**, Takashige Hoshiai***, Hidenori Nakazato** Waseda University, Japan, ** Tokyo University of Information Sciences, Japan, *** Sojo University, Japan

4

A Stereo-Vision Approach for a Natural 3D Hand Interaction with an AR Object

315

Seonho Lee, Junchul Chun
Kyonggi University, Suwon, S. Korea

5

The Optimum Ring Ratio of 16-APSK in LTE Uplink over Nonlinear System
Pornpimon Chayratsami*, Sorapong Thuaykaew**
King Mongkut Institute of Technology Ladkrabang, Bangkok, Thailand, **Celestica Inc., Leamchabang, Sriracha, Chon Buri, Thailand

333

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013290

On ICI Canceller for Mobile OFDM DTV
Receivers
Hai Minh TRAN*, Tomohisa WADA***Graduate School of Engineering and Science**Department of Information Engineering, University of the Ryukyus*&** Senbaru 1, Nishihara, Okinawa 903-0213, Japan
haitran@lsi.ie.u-ryukyu.ac.jp, wada@ie.u-ryukyu.ac.jp
Abstract— In mobile environment, the performance of OFDM
mobilereceiversisdegraded severely
becauseofInter-Carrier-Interference (ICI) caused by Doppler Spread. So
ICI canceller is an important task for designers of mobile OFDM
receivers. [1] and [2] proposed an efficient method to reduce ICI.
The main idea of this method is to linearly approximate timevarying channel within one OFDM symbol. Then a large ICI
matrix equation is given. However, in [1] and [2], the estimatedvalues of the channel transfer function—the diagonal of the ICI
matrix is corrupted by ICI. Consequently, the equalized signal
still is distorted. In this paper, we propose an iterative method toimprove performance of the conventional method in [1] and [2].
We implement Jacobi iteration method to solve the big ICI matrix
equation. Thereby, we are able to implement ICI canceller by asimple FIR filter rather than finding the inverse of ICI matrix.
Next, at second iteration of Jacobi method, we improve theaccuracy the diagonal by removing ICI from pilot symbols andre-estimating the channel transfer function. Simulation results for
ISDB-T mode 3 demonstrated that our method could double
performance of the conventional method under TU-6 channel andDoppler Spread. The improvement is better for two paths and one
path Doppler channel.

Keyword— Digital television (DTV), Inter-Carrier Interference(ICI), Jacobi Iteration, Orthogonal frequency-divisionmultiplexing (OFDM).

I. INTRODUCTIONO

FDM utilized a large number of orthogonal subcarrier toachieve high-spectral efficiency. The long duration
symbol and guard interval protect useful part of OFDM
symbols from inter-symbol-interference (ISI). Guard interval(GI) is implemented by cyclic prefix (CP). This scheme keeps
OFDM symbols smoothly in time domain, and reduces out ofband power of OFDM. Moreover, cyclic prefix keeps
convolution of channel and OFDM symbol is circular

Manuscript received March 11, 2013. Hai Minh TRAN is with the Graduate
School of Engineering and Science, University of the Ryukyus, Okinawa-ken,
903-013 Japan. (phone 080-427-6768; email: haitran@lsi.ie.u-ryukyu.ac.jp)
Tomohisa WADA is with Department of Information Engineering, Universityof the Ryukyus. (email: wada@lsi.ie.u-ryukyu.ac.jp)

convolution. However, in mobile environment, GI or CP could
not avoid Doppler-effect. Doppler-effect spreads energy of one
sub-carriers to many other subcarriers. This is called ICI. In
other word, in time-varying channel, the orthogonality among
subcarriers is lost. Thus performance is degraded severely.
Many researches are conducted to deal with ICI caused by
Doppler. In [1] and [2], an efficient approach is to linearly
approximate time-varying channel within one OFDM symbol.
Then we should solve a large ICI matrix equation. In [3], amethod is proposed to solve the large ICI matrix equation. As
most ICI power concentrates near the diagonal of ICI matrix,[3] considered 𝐷 lines that are closest to the diagonal. Instead
finding invert of [𝑁 × 𝑁] matrix, [3] find inverse of 𝑁 matrixof order [ 2𝐷 + 1 × 2𝐷 + 1 ]. This still requires heavy
computation.
As pilot symbols suffer from ICI, the estimated values of the
diagonal also is corrupted by ICI. In addition, the diagonal has
the most important rule. Therefore, performance of [1], [2] islimited, even we solve the full ICI matrix equation. In thispaper, we apply Jacobi iteration method to solve the large ICI
equation, so we do not need calculate any inverse matrix. The
simulation result shown that performance of Jacobi iteration at
first iteration is the same as [3]. It is noted that Jacobi iteration
method also is considered in [4]. However, in our method, we
improve the diagonal of ICI matrix at second iteration of Jacobi
method. By using output of the first iteration, we remove ICI
from pilot symbols. Then, we re-estimate the diagonal of ICI
matrix. As the diagonal is reliable, our method achieved a good
improvement at second iteration.
The rest of paper is organized as follows: Section II reviews
the conventional method. Section III shows our proposed
method. Section IV presents implementation of the proposed
method. Simulation result is shown in section V. Finally,
conclusion is presented in section VI.
II. REVIEW OF THE CONVENTIONAL METHOD
A. A Linear Approximation of Time Varying Channel
Time varying channel causes ICI. Therefore, we needcharacterizing time varying channel to define the ICI effect. By
a linear approximation of time varying channel, the ICI isdefined.

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013291

Vl (n )

Channel Impulse
Response

hs

N-1

Pa
t

D

2

Time (n)Approximate Channel

el
ay

3

0

1

N 1
2

NS

N

2NS

0

n

GI

Prev symbol

Time (n)Vl (n )Vl ( 0 )GI Current symbol GI

Next symbol

Figure 2. Approximation of 𝑽𝒍 (𝒏)Figure 1. 𝑽𝒍 (𝒏) in Time Domain

As in [1], the received signal in frequency domain can be
written as follows:
𝑁−1

𝑌 𝑘 = 𝑋 𝑘 𝐻𝑘 ,𝑘 +𝑋 𝑙 . 𝐻𝑘 ,𝑙 + 𝑊 𝑘
𝑙=0,𝑙#𝑘(1)

If 𝑕(𝑚, 𝑛) is linear in time domain, then 𝑉𝑙 (𝑛) also is linear intime domain. Instead of linear approximating 𝑕(𝑚, 𝑛), it isequivalent to linearly approximate 𝑉𝑙 (𝑛). The two first termsof Taylor series for 𝑉𝑙 𝑛 is
𝑁−1
𝑉𝑙 𝑛 ≈ 𝑉𝑙 + 𝑛 −. 𝑉𝑙 ′(5)
2

𝐼𝐶𝐼

𝑋(𝑘) and 𝑌(𝑘) is transmitted and received signal respectively.
𝑙, and 𝑘 are subcarrier indexes. 𝑁 is number of subcarrier. 𝑊
denotes random noise. The channel transfer function from 𝑙 𝑡𝑕to 𝑘 𝑡𝑕 subcarrier is calculated as1
𝐻𝑘 ,𝑙 =𝑁

𝑁−1 𝑁−1

𝑕 𝑚, 𝑛 . 𝑒

−𝑗

2𝜋𝑙𝑚
2𝜋
−𝑗 𝑛(𝑘−𝑙)
𝑁 .𝑒
𝑁

(2)

𝑛=0 𝑚 =0𝑕(𝑚, 𝑛) is channel impulse response, with 𝑚 and n are delay
path and time index, respectively. 𝐻𝑘 ,𝑙 should be determined.
However, we do not know 𝑕(𝑚, 𝑛) at all (𝑚, 𝑛). By assuming
𝑕(𝑚, 𝑛) changes linearly in time domain and within an OFDM
symbol, 𝐻𝑘 ,𝑙 can be determined.

The first central difference at
′

𝑉𝑙 ≈

2𝜋
𝑕 𝑚, 𝑛 . 𝑒 −𝑗 𝑁 𝑙𝑚

𝑉𝑙 𝑛 =

𝐻𝑘 ,𝑙 =

1𝑁(𝑝𝑟𝑒 )(6)

𝑁−1

𝑌 𝑘 = 𝑋 𝑘 𝐻𝑘,𝑘 +𝑋 𝑙 𝑉𝑙 ′ΦΔ 𝑙 + 𝑊 𝑘 , Δ𝑙 = 𝑙 − 𝑘
𝑙=0,𝑙#𝑘ΦΔ 𝑙 =

(7)
1

, 𝑙#𝑘
2𝜋
𝑒 𝑗 𝑁 Δ𝑙 − 1(8)

For more detail about capability of linear approximating timevarying channel, please refer to [1] and [2].

2𝜋𝑉𝑙 𝑛 . 𝑒 −𝑗 𝑁 𝑛(𝑘−𝑙)

(4)

𝑛=0

B. The Large ICI Matrix Equation
Equation (7) can be represented in matrix form as (9). In
this paper, we assumed 𝑊 = [0].

If 𝑘 = 𝑙, we have1
𝐻𝑘 ,𝑘 =
𝑁

− 𝑉𝑙
2𝑁𝑠

is approximated as

(3)

𝑚 =0
𝑁−1

(𝑛𝑒𝑥𝑡 )

2

It is noted that error of the first central difference is 𝑂(𝑕2 ),while the error of the first backward or forward difference is′𝑂(𝑕) [5]. Therefore, 𝑉𝑙 is approximated by the first central
difference. From (1), (4), and (5) we have the ICI equation:

𝑉𝑙 (𝑛) denotes Fourier Transform of channel impulse
response 𝑕(𝑚, 𝑛) at 𝑛 instant time.
𝑁−1

𝑉𝑙

𝑁−1

𝑁−1

𝑉𝑙 𝑛 = 𝑉𝑙 (𝑛)

(5)

𝑛=0

𝐼𝐶𝐼 𝑀𝑎𝑡𝑟𝑖𝑥 [𝐻]

𝐻0,0
𝑌(0)
𝑌(1)
Φ1 V0′⋮=⋮
𝑌(𝑁 − 2)
Φ𝑁−2 𝑉0′
𝑌(𝑁 − 1)
Φ
𝑉′
𝑁−1 0

Φ−1 𝑉1′⋯

Φ−𝑁+2 𝑉𝑁−2 ′𝐻1,1⋮
Φ𝑁−3 𝑉1′⋯⋱⋯

Φ−𝑁+3 𝑉𝑁−2⋮
𝐻𝑁−2,𝑁−2

Φ𝑁−2 𝑉1′⋯

Φ1 𝑉𝑁−2 ′Φ−𝑁+1 𝑉𝑁−1 ′

𝑋(0)
𝑊(0)
Φ−𝑁+2 𝑉𝑁−1 ′
𝑋(1)
𝑊(1)
⋮
⋮
×
+
⋮
𝑋(𝑁 − 2)𝑊(𝑁 − 2)
Φ−1 𝑉𝑁−1 ′𝑋(𝑁 − 1)𝑊(𝑁 − 1)𝐻

(9)𝑁−1,𝑁−1

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

In order to recover the transmitted signal, we should solve avery lager matrix equation. In ISDB-T mode 3, as number ofsubcarrier is (𝑁 = 8192), finding inverse of 𝐻 8192 ×8192 isa heavy task. Therefore, it is necessary to reduce complexity of(9).
To solve the larger matrix equation, we investigate
characteristics of matrix [𝐻]. Firstly, we consider ICI power
distribution. Absolute value of ΦΔ𝑙 indicates ICI power from𝑙 𝑡𝑕 subcarrier to 𝑘 𝑡𝑕 subcarrier, Δ𝑙 = (𝑙 − 𝑘) is distance
between 𝑙 𝑡𝑕 and 𝑘 𝑡𝑕 subcarrier.
ΦΔ 𝑙 =1

ΦΔ 𝑙 =

2 sin

𝜋𝛥
𝑁

1
𝜋 Δ𝑙
2𝑒 𝑗 𝑁 sin

(10)

𝜋𝛥
𝑁

0.5𝑁
𝑖𝑓 Δ𝑙 → 0
𝜋Δ𝑙
=
0.5𝑁
𝑖𝑓 Δ𝑙 → −𝑁 + 1
𝜋(𝑁 + Δ𝑙 )(11)

Δ𝑙 → 0 means that the subcarriers that are near 𝑙 𝑡𝑕 subcarriercauses a big ICI power on 𝑙 𝑡𝑕 subcarrier. Δ𝑙 → (−𝑁 + 1)
means the subcarriers that are far 𝑙 𝑡𝑕 subcarrier may generate a
big ICI power on 𝑙 𝑡𝑕 subcarrier. For example, Fig.1 shows ICI
power from (𝑁 − 1) subcarrier to 1𝑠𝑡 subcarrier. In matrix
form, ICI power concentrated on the elements that near the
diagonal and the elements that at low-left corner or upper-rightcorner of [𝐻] matrix.
Because ICI power concentrates on near diagonal of 𝐻
matrix, in paper [1], [3] researchers considered 𝐷 elements thatclosest the diagonal and solve 2𝐷 + 1 × 2𝐷 + 1 matrix
size equation instead for [𝑁 × 𝑁] matrix equation. For
example, 𝐷 = 1, we have 3 × 3 matrix equation as
𝑌0
𝑌1 =
𝑌2

𝐻0,0
𝜙−1 𝑉0′𝜙−2 𝑉0′𝜙1 𝑉1′𝐻1,1

𝜙−1 𝑉1′

𝜙2 𝑉2′
𝜙1 𝑉2′
𝐻2,2

𝑋0
× 𝑋1
𝑋2

(12)

292

By increasing 𝐷, we can achieve more improvement, but thecomputational complexity also is increased. Even (𝐷 = 1) weshould find 𝑁 invert matrix size of [3 × 3]. In next section, byusing Jacobi iteration we do not need calculate inverse of any
matrix, while performance is remaining.
III. THE PROPOSAL METHOD
As section II, through linearly approximating time varying
channel, the conventional method can define the ICI matrix
equation. However, we face with two challenges. First, thegiven ICI matrix is very big such as 𝐻 8192 ×8192 for ISDB-T
mode 3. Second, the diagonal of the ICI matrix-theconventional channel transfer function is not accurate becauseof pilots were corrupted by ICI. To deal with the twochallenges, we first apply Jacobi iteration method for solving
the big ICI matrix. By this way, we do not need calculate any
inverse matrix. Next, we re-estimate channel at 2nd iteration to
improve accuracy of the diagonal of the ICI matrix.
A. Jacobi Iteration Method for The Large ICI Matrix
In this section, we apply Jacobi iteration method for the large
ICI matrix equation. First we separate the ICI matrix into twoparts. The first part is the diagonal of ICI matrix as
𝑃 = 𝑑𝑖𝑎𝑔 𝐻0,0 𝐻1,1 … 𝐻𝑁−2,𝑁−2 𝐻𝑁−1,𝑁−1(13)
The remained part of ICI matrix is
𝑇 = 𝐻 − [𝑃](14)Equation (9) can be re-written as
𝑌 = 𝑃 . 𝑋 + 𝑇 . [𝑋](15)

𝑃 . 𝑋 = 𝑌 − 𝑇 . [𝑋](16)

According to Jacobi method, the approximate solution at(𝑘 + 1) iteration is updated as:
𝑃 . 𝑋𝑘+1 = 𝑌 − 𝑇 . 𝑋𝑘

(17)

ICI Power From N-1 Subcarrier To The First Subcarrier
35

Because 𝑃 is diagonal matrix, it is easy to solve (17). The
initial value 𝑋0 is calculated from 1 tap equalizer. For example,
kth subcarrier is initiated as

30

ICI Power in dB

25
20

𝑋0 (𝑘) =

15

𝑌(𝑘)
𝐻𝑘 ,𝑘

(18)

At each iteration, error is10

𝑒𝑘+1 = 𝑋 𝑘+1 − 𝑋 = [𝐼] − 𝑃−1 𝐻 𝑒𝑘 = 𝑀 𝑒𝑘

50-5

𝑒𝑘+1 = 𝑀 𝑘 𝑒1 ≤ 𝜆𝑀 𝑘 𝑒1 ,
0

1000

2000

3000

4000 5000
Subcarrier Index

6000

7000

8000

9000

(19)

Figure 3. ICI Power From Other Subcarriers to First Subcarrier

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

Y0

DATA0 + SP0

293

2nd Iteration
SP1

SP0
Interpolation
CTF

Equalizer

X0

ICI
Reduction

Equalizer

X1

ICI
Reduction

Interpolation
CTF

Equalizer

X2

DATA1
Hslope

SP: Scatter Pilot
Y0: Received Signal
X: Equalizer Output

Figure 4. Two Iterations with Improved The Diagonal of The ICI Matrix

𝜆𝑀 is the biggest engine value of [𝑀]. In this case, as the
diagonal is dominated, Jacobi iteration method is effective. For
more detail about Jacobi iteration, please refer to [4], [5].
Since most ICI power concentrated near the diagonal, we canreduce size of [𝑇] to get the low complexity. We form [𝑇] by
30 elements that are nearest the diagonal. 𝑘 𝑡𝑕 subcarrier is
updated at first iteration as
𝑋1 (𝑘) =𝑌𝑘 −15
Δ=−15 𝑋0 Δ + 𝑘 . 𝑉Δ+k ′. ΦΔ

𝐻𝑘 ,𝑘

B. Two Iterations with Re-estimating Channel Transfer
Function
Normally, the approximate solution at 2nd iteration of Jacobi
method is
𝑌𝑘 −

(2)

𝑋𝑘

=

(21)

We should remind that 𝐻𝑘 ,𝑘 is estimated from pilots that were(2)
corrupted by ICI. Consequently, 𝑋𝑘 still is distorted. In orderto improve performance, we re-estimate channel 𝐻𝑘 ,𝑘 at 2nd
iteration.
Firstly, we remove ICI from pilot symbols by using output at
1st iteration as

A. Implementation of ICI Canceller using FIR Filter
In this section, we present an implementation of ICI canceller
using a FIR filter. By using linear approximating time varying
channel, the ICI matrix is obtained. In addition, interestingly,
the ICI coefficient ΦΔ is constant. As ΦΔ is constant, we canimplement ICI canceller by using a FIR filter.
From (1) the transmitted signal can be recovered as
𝑋(𝑘) =

𝑌(𝑘) −𝑋1 (Δ + m). 𝑉Δ+m ′. ΦΔ

𝑚 is pilot symbol index. Secondly, the channel transfer
function is re-estimatedusing 𝑌1 (𝑚). Therefore,(𝑟𝑒 −𝑒𝑠𝑡𝑖𝑚𝑎𝑡𝑒 )𝐻𝑘 ,𝑘is more accurate. Finally, the recover signal atsecond iteration is updated as (23). The channel transfer(24)

We separate (24) into two steps. At first step, ICI power issubtracted from the received signal, so the clean ICI signal is
obtained. At second step, the clean ICI signal is equalized by
dividing by conventional channel transfer function. At firststep, we consider 𝑊 nearest subcarrier to 𝑘 𝑡𝑕 subcarrier.
𝑊 = 2. 𝑄 + 1

(22)

Δ=−15

𝑁−1
𝑙=0,𝑙#𝑘 𝑋 𝑙 . 𝐻𝑘 ,𝑙

𝐻𝑘 ,𝑘

15

𝑌1 𝑚 = 𝑌(𝑚) −(23)

IV. IMPLEMENTATION OF THE PROPOSAL METHOD15
Δ=−15 𝑋1 Δ + 𝑘 . 𝑉Δ+k ′. ΦΔ

𝐻𝑘,𝑘

(1)
15
Δ 𝑘 =−15 𝑋Δ+𝑘 . 𝑉Δ+k ′. ΦΔ(𝑟𝑒 −𝑒𝑠𝑡𝑖𝑚𝑎𝑡𝑒 )
𝐻𝑘 ,𝑘

𝑌𝑘 −

(20)

ΦΔ , Δ = −15, −14, … , 15 is fixed coefficient as (11). We canimplement iteration equation by a FIR filter with 31 taps.

𝑋2 (𝑘) =function -the diagonal of ICI matrix is the most importantelement of the ICI matrix. As the channel transfer function isrefined at 2nd iteration, we could achieve a significant
improvement. The all above procedures are shown in Fig. 4.

The ICI term that impacts on 𝑘 𝑡𝑕 subcarrier is re-written as
follow
𝑄

𝐼𝐶𝐼(𝑘) =𝑋(𝑘 + Δ). VΔ+k ′. ΦΔ

(25)

Δ=−𝑄

𝐼𝐶𝐼(𝑘) = 𝑐𝑜𝑛𝑣 ΦΔ ,𝑋(𝑘). VΔ+k ′(26)

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013294

ICI amplitude decrease over frequency distance

15

Z 1

Z 1

Z 1

Z 1

...
...

1400

Z 1

1200

14

14

0  0

15

Amplitude of ICI coefficients

S(k). Vk'

...
...


ICI(k)
Figure 5. Implement ICI Canceller Using FIR Filter

1000

800

600

400

200

0

As (26), 𝐼𝐶𝐼(𝑘) is output of a FIR filter with the coefficientsare ΦΔ , and input is 𝑋 𝑘 + Δ . Vk ′ . The input 𝑋 𝑘 + Δ iscalculated by conventional 1 tap equalizer as (17). This value iscalled the initial value of ICI canceller. The FIR filter causes
delay, so we have to locate and extract the ICI term from the
FIR output. If the FIR filter has 𝑊 taps, the extracted signal iswithin the range of
𝑊−1
+1
2

𝑁−

𝑆 𝑘 + 𝛥 . 𝛷𝛥 . 𝑉𝛥+𝑘 ′
𝛥=−15

(26)

Fig. (5) illustrates calculating 𝐼𝐶𝐼(𝑘) using a FIR with 31
taps ΦΔ .
After the ICI term is calculated, we subtract the ICI termfrom the received signal. Thus, the clean ICI signal is obtained.
Next, the clean ICI signal is equalized by only one tap equalizer
as follow
𝑌 𝑘 − 𝐼𝐶𝐼(𝑘)
𝐻𝑘 ,𝑘

20

30
40
50
60
70
Frequency distance or Delta index

ΦΔ =B. Finding a Reasonable ICI Window Size
In this section, we explain how to choose a reasonable 𝑊, thenumber taps of FIR filter. We can choose a maximum(𝑊 = 𝑁) to ensure the best ICI canceller performance.
However, that is not necessary, even a big 𝑊 increases FIR
implementation cost.
ΦΔ quantifies ICI from 𝑙 𝑡𝑕 subcarrier to 𝑘 𝑡𝑕 subcarrier. We
exam |ΦΔ | to know how strong the ICI from 𝑙 𝑡𝑕 subcarrier to𝑘 𝑡𝑕 subcarrier is.

90

100

1
𝜋
2𝑗𝑒 𝑗 𝑁 Δ . sin

𝜋𝛥
𝑁

(28)

0.5
𝜋𝛥
sin
𝑁

(29)

From (29), the ICI amplitude decays over the distance from𝑙 𝑡𝑕 subcarrier to 𝑘 𝑡𝑕 subcarrier. It decays quickly with the rate𝜋𝛥
of sin. Fig. (6) shows the ICI amplitude |ΦΔ | decreases
𝑁over frequency distance Δ.
More specifically, we compare the ICI power is removed
by 𝑊 coefficients with the total ICI. The removed ICI power isnumerator of (30), and the total ICI is the denominator.
2

𝑊−1
2
𝑛=1

0.5
𝜋𝛥
sin
𝑁

𝐼𝐶𝐼𝑐𝑜𝑛𝑠𝑖𝑑𝑒𝑟𝑒𝑑 =
𝑁
2
𝑛=1

(27)

The number of FIR coefficients is 𝑊, it means we consider
ICI from the 𝑊 closest subcarriers to the interest subcarrier 𝑘.
Therefore, the value 𝑊 determines how much ICI is removed
from the received signal. The bigger 𝑊, the more ICI isremoved. However, the big 𝑊 increases FIR implementation
cost. In next section, we show how to find a reasonable 𝑊.

80

Figure 6. ICI Amplitude Decays over Frequency Distance

ΦΔ =

𝛥=15

𝑋(𝑘) =

10

𝑊−1
2

.
For example 𝑊 = 31, we have

𝐼𝐶𝐼(𝑘) =

0

(30)
2

0.5
𝜋𝛥
sin
𝑁

If 𝑊 = 31 and 𝑁 = 8192, we have
2
15
Δ=1

𝐼𝐶𝐼𝑐𝑜𝑛𝑠𝑖𝑑𝑒𝑟𝑒𝑑 =
4096
Δ=1

0.5
𝜋𝛥
sin
𝑁

2 = 96.0793%

0.5
𝜋𝛥
sin
𝑁

(31)

If 𝑊 = 63, 𝑁 = 8192
𝐼𝐶𝐼𝑐𝑜𝑛𝑠𝑖𝑑𝑒𝑟𝑒𝑑 = 98.0071%(32)

From (31), we conclude that, 𝑊 = 31 results in 96.0793%
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

ICI is removed. If we increase 𝑊 to 63, the removed ICI is98.0703%.
Obviously we can (𝑊 = 31) to keep
implementation at low cost. In section IV, we will compare bit
error rate with different values of 𝑊.

0295

Investigate effect of matrix size on ICI reduction - TU6 Channel

10

-1

10

A. Comparison of Jacobi Iteration Method and Direct
Solving ICI Matrix
As section I, [3] proposed a method to solve the large ICI
matrix equation. Instead finding inverse of [𝑁 × 𝑁] matrix, [3]find inverse of 𝑁 matrix order of [ 2𝐷 + 1 × 2𝐷 + 1 ]. We
set 𝐷 = 2, 7, 15 and solve matrix order of 5 × 5 ,15 × 15 , [31 × 31], respectively. As shown in Fig. 5, under
TU-6 channel condition, as 𝐷 increases, the performance isimproved. Because most ICI energy concentrated near the
diagonal, improvement by increasing (𝐷 = 2) to (𝐷 = 7) or(𝐷 = 15) is small.

-2

10

-3

10

1X1 Matrix
5X5 Matrix
15X15 Matrix
31X31 Matrix

-4

10

0

10

20

30

Values8192
5617
992.06 (Hz)1008µs126 µs64QAM

TABLE II. TU-6 CHANNEL
Tap
number
1
2
3
4
5
6

Delay
(µs)
0.0
0.2
0.5
1.6
2.3
5.0

Power
(dB)
-3.0
0.0
-2.0
-6.0
-8.0
-10.0

DopplerSpread (Hz)
[0 200][0 200][0 200][0 200][0 200][0 200]TABLE III. TWO PATHS DOPPLER CHANNEL
Tap
number
1
2

Delay
(µs)
0.0
12.3

Power
(dB)
0.0
-3.0

DopplerSpread (Hz)
[0 200][0 200]TABLE IV ONE PATH DOPPLER CHANNEL
Tap
number
1

Delay
(µs)
12.3

Power
(dB)
-3.0

DopplerSpread (Hz)
[0 200]

80

90

100

Jacobi Iteration Method -TU6

0

-1

10

-2

10

-3

10

Pure Jacobi 1st Iter
Modified Jacobi 31Taps 1Iter
Direct Solving 31X31-4

Parameters
FFT size
Number of sub-carrier
Carrier interval
Effective Sym. Duration
Guard interval
Modulation

70

10

10

TABLE I. ISDB-T MODE 3 PAREMETERS

40
50
60
Frequency Offset

Figure 5. The Original Method with different value of 𝑫 under
TU-6 Channel

Bit Error Rate

In this section, firstly, we compare Jacobi iteration methodand direct solving the ICI matrix in [3]. Secondly, we evaluate
and compare our proposed method with the conventional
method. Finally, we investigate our proposal method withdifferent value of ICI window size 𝑊. We apply our proposal
method for ISDB-T mode 3. The parameter of OFDM system isshown in table I. We evaluate our proposal method under threedifferent channel conditions. These are the TU-6 channel, twopath Doppler channel, and one path Doppler channel. The detailchannel parameters are shown in table II, III, IV.

Bit Error Rate

V. SIMULATION RESULT

0

10

20

30

40
50
60
Frequency Offset

70

80

90

100

Figure 6. Jacobi Iteration Method with TU-6 Channel

Next, we compared Jacobi iteration method and method in [3]with (𝐷 = 15). In Fig 6, pure Jacobi means 𝑇 = 𝐻 − 𝑃 ,and [𝑃] is the diagonal of 𝐻 . Modified Jacobi 31 taps used 30lines that closest the diagonal of ICI matrix for [𝑇]. In Fig. 6,
under TU-6 channel, the modified Jacobi with 31 taps achieved
a performance as (𝐷 = 15) or pure Jacobi iteration.
B. Comparison of Our Proposed Method and theConventional Method
In this section, we compare our proposal method with theconventional method under three different channel conditions.
We investigate improvement of our proposal method withre-estimating channel at 2nd and 3rd iteration.
By removing ICI from pilot symbols and re-estimating
channel at 2nd iteration, the re-estimate channel is moreaccurate. Thereby, our proposal method improved performance
significantly. In Fig. 7, under TU-6 channel, the proposed
method doubles performance of 1st iteration-the conventional
method over a wide range of frequency offset. Moreover, theproposed method achieved more improvement for two paths
and one path Doppler channel. This is because the residual ICI
in two paths and one path Doppler channel is less than that in
TU-6 channel.
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

3 Iterations w ith TU6 Doppler Channel

0

10

296

3 Iterations w ith 1 Doppler Path Channel

0

10

-1

-2

No ICI Canceller
1st Iter
2nd Iter
3rd Iter10
Bit Error Rate

Bit Error Rate

10

No ICI Canceller
1st Iter
2nd Iter
3rd Iter

-1

10

-2

10

-3

10

-4

10
-3

10

-5

10

-4

10

-6

0

20

40

60

80
100
120
Frequency Offset (Hz)

140

160

180

10

200

Figure 7. The Propsed Method with TU-6 Channel

40

60

80

100
120
140
Frequency Offset (Hz)

160

180

200

Figure 9. The Proposed Method with One Path Doppler Channel

3 Iterations w ith 2 paths Doppler channel

020

2 Iterations w ith different ICI Window size for TU6 channel

0

10

10

-1

-1

Bit Error Rate

Bit Error Rate

10

No ICI Canceller
1st Iter
2nd Iter
3rd Iter

10

-2

10

W=3
W=5
W=15
W=31
W=63

-2

10

-3

10

-3

10

-4

10

-4

0

20

40

60

80
100
120
140
Frequency Offset (Hz)

160

180

0

10

20

30

200

Figure 8. The Proposed Method with Two Paths Doppler Channel

In more detail, at 2nd iteration, by reducing ICI effect in pilot
symbols, the diagonal is improved. However, the residual ICI
in pilot symbols still degrade reliability of the diagonal. As
number of paths channel decreases, the residual ICI becomes
smaller and the diagonal suffer less effect of the ICI residual.
Therefore, the proposed method got more improvement for one
and two paths channel.
In order to get more improvement, we extend our proposed
method to 3 iterations. The signal is derived from 2nd iteration isclearer and closer to real transmitted signal. The output at 2 nd
iteration is utilized to remove ICI from pilot symbols. Then, thechannel transfer function 𝐻(𝑘, 𝑘) is re-estimated. As a result
𝐻(𝑘, 𝑘) is more accurate, and output at 3rd iteration is better. In
Fig. 7, 8, 9, simulation results show 3rd iteration achieved better
performance than 2nd iteration.
C. ICI Canceller with Different ICI Window Size 𝑊
As our above analysis, the bigger 𝑊 the more ICI is removed.
In addition, (𝑊 = 31) and (𝑊 = 63) provide similar
performance, and almost ICI is considered. We evaluate bit
error rate with different 𝑊 at 1st iteration, and 2nd iteration. In
Fig. 10 and Fig. 11, 𝑊 = 3, 5, 15, 31, 63. The bit error rate
confirmed the bigger 𝑊, the better performance. In addition, it
is a slightly different between 𝑊 = 31 and 𝑊 = 63 .
Therefore, 𝑊 = 31 is a reasonable choice for ICI window size.

40
50
60
Frequency Offset (Hz)

70

80

90

100

Figure 10. The Proposed Method with Different ICI Window Size

2 Iterations w ith different ICI Window size for 2 path Doppler channel

0

10

-1

10

Bit Error Rate

10

W=3
W=5
W=15
W=31
W=63

-2

10

-3

10

-4

10

-5

10

0

10

20

30

40
50
60
Frequency Offset (Hz)

70

80

90

100

Figure 11. The Proposed Method with Different ICI Window Size

VI. CONCLUSION
In this paper, we achieved a good improvement by removing
ICI from pilots and re-estimating channel transfer function-the
diagonal of ICI matrix at 2nd, and 3rd iteration. The performanceof our method is evaluated and compare with original method.
As simulation result, our method doubled performance of
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

original method for TU-6 channel. The improvement is betterfor two paths and one path Doppler channel.
In addition, instead of direct solving ICI matrix, we applied
Jacobi iteration with low complexity. We also present a simple
and beautiful implementation of ICI canceller using FIR filter.
This method is easy for hard-ware implementation. Moreover,
we prove that 96% the ICI is considered by only 31 FIR taps. It
is not necessary to choose a big number FIR taps such as
maximum N taps. Therefore, we can keep the FIR at low cost.
The simulation with different 𝑊 also is consistent with ournumerical analysis.

REFERENCES
[1]

[2]

[3]

[4]

[5]

Fischer, V. and Kurpiers, A. and Karsunke, D., “ICI reduction method
for ofdm systems”, Hamburg: 8th International OFDM-Workshop, pp.
1-5, 2003.
Mostofi, Y. and Cox, D.C., “ICI mitigation for pilot-aided OFDM mobile
systems”, Wireless Communication, IEEE Transactions on, IEEE, vol. 4,
no. 2, pp. 765-774, 2005.
Jeon, W.G. and Chang, K.H. and Cho, Y.S., “An equalization techniquefor orthogonal frequency-division multiplexing systems in time-variant
multipath channels”, Communications, IEEE Transactions on, IEEE, vol.
47, no. 1, pp. 27-32, 1999.
Molisch, A.F. and Toeltsch, M. and Vermani, S., “Iterative methods forcancellation of intercarrier interference in OFDM systems”, VehicularTechnology, IEEE Transactions on, IEEE, vol. 56, no. 4, pp. 2158—2167,
2007
Strang, G. and Massachusetts Institute of Technology, “Computational
science and engineering”, Wellesley-Cambridge Press Wellesley, MA,
2007.

297

Hai Minh Tran was born in Hanam, Vietnam, on June09, 1988. He received the B.S. degree from Hanoi
University of Technology, Vietnam in 2011.
He is currently a Master student in Graduate School ofEngineering and Science, University of the Ryukyus.
His research interests are channel estimation with its
application to digital television mobile receiver and LTE
system.

Tomohisa Wada
received the BS degree inelectronic engineering from Osaka Univ., Osaka, Japan,
in 1983, M.S.E.E degree from Stanford Univ., Stanford
CA, in 1992, and Ph.D. in electronic engineering from
Osaka Univ. in 1994.
He joined the ULSI Laboratory Mitsubishi Electric
Corp., Itami, Japan, in 1983. From 1983 to 1999, hehas been engaged in the development of
CMOS/BiCMOS static RAMs, 3-D graphics
controller ASIC, flash memory, low-voltage static RAM, and synchronousburst static RAMs. In 1998, he joined Mitsubishi Electric
Corp.,
Semiconductor Group, Memory ICI Division, Itami, where he has beenworking on the development of application specific synchronous burst
static RAMs. In 1999, he became an Associate Professor with the Department
of Information Engineering, Univ. of the Ryukyus, Okinawa, Japan. Since 2001,
he has been a Professor at the Department of Information Engineering, Univ.
Of the Ryukyus, Okinawa, Japan. In 2001, He was the founding member of
Magna Design Net, Inc., which is a fab-less LSI design Company forcommunication related digital signal processing such as OFDM. Currently, heis also the chief scientist of Magna Design Net, Inc. From 1999 up to now, he
has been engaged in the research and development of high bandwidthcommunication systems such as terrestrial video broadcasting receivers andwireless LAN. Currently, his research includes system-level large-scale VLSI
design, digital signal processing for high-bandwidth communication, error
correction algorithm and circuit, networking software and protocols.

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

298

Simple and Feasible Dynamic Bandwidth andPolling Allocation for XGPONMan-Soo HAN
Dept. of Information and Communications, Mokpo National Univ., Korea
mshan@mokpo.ac.kr

Abstract—In this paper, we propose a simple and feasible
dynamic bandwidth allocation (SFDBA) algorithm in order toutilize the unallocated bandwidth and to achieve the implementation feasibility. SFDBA is based on an immediate allocation
with colorless grant (IACG) algorithm but SFDBA uses onlya single available byte counter and a single down counter for
multiple queues of a same service class. Since multiple queues
share the same available byte counter, the unallocated bandwidthof a queue can be utilized by another queues. For better service
fairness, SFDBA changes the starting queue of scheduling in around-robin manner. Using simulations, we show that SFDBA issuperior to existing methods in mean delay, frame delay varianceand frame loss rate.
Keywords—Keywords: Passive Optical Network, Dynamic Bandwidth Allocation, Polling, XGPONI.

I NTRODUCTIONXGPON (10-gigabit-capable Passive Optical Network) consists of an optical line termination (OLT) and multiple optical
network units (ONUs) [1]. In order to allocate non-collisiontransmission slots to ONUs, the OLT receives requests from
ONUs and performs dynamic bandwidth allocation (DBA).
In the XGPON technology, the OLT has to produce DBA
result in every frame duration which has a fixed to 125 µs[1], [2]. Therefore, it is crucial that a DBA algorithm can be
run within the frame duration in XGPON. Many algorithms
have been proposed for GPON DBA [5]–[11]. To the best of
our knowledge, however, only a GigaPON access network (GIANT), an immediate allocation with colorless grant (IACG),
and efficient bandwidth utilization (EBU) have been physically
implemented. These algorithms are simple and compliant to
the GPON standards.
The GIANT algorithm is the first DBA algorithm that is
physically implemented [6], [7]. In GIANT, each queue has adown counter for bandwidth allocation. The OLT can allocate
bandwidth to a queue only when the down counter of thequeue has expired. The simplicity of GIANT provides theimplementation feasibility. Although GIANT provides good
performance, it degrades performance since a request of aqueue can not be granted until the down counter has expired.
In [8], IACG algorithm had been introduced. In IACG,
each queue has an available byte counter and a down counter
Manuscript received June 6, 2013.
M.-S. Han is with the Dept. of Information and Communication, Mokpo
National Univ., Jeonnam, Korea (phone: +82-61-450-2744; fax: +81-61-4506470; e-mail: mshan@mokpo.ac.kr).

in order for the fast bandwidth allocation. The OLT can
immediately allocate a bandwidth to a queue if its available
byte counter has a positive value. The available byte counteris decreased by the grant amount. The available byte counteris recharged when its down counter has expired. It was
shown that IACG outperforms GIANT in [8]. Although IACG
provides good performance, it does not effectively utilize theunused bandwidth of queues. The unused bandwidth of a queue
cannot be used by another queues. It is desirable that theunused bandwidth is utilized by queues whose request sizes
are larger than their reserved service bandwidth.
In [9], EBU algorithm had been introduced. EBU improves
the unallocated bandwidth problem of IACG. In EBU, eachqueue has an available byte counter and a down counter like
IACG. To utilize the unused bandwidth, the available byte
counter can be negative. In addition, at the end of scheduling,
the unused remainder of the available byte counter is added to
the negative available byte counters. It was shown that EBU
increases the utilization of the unused bandwidth comparedto IACG in [9]. However, the operation of the available byte
counter is complex and an extra stage is required for the updateof the available byte counters. Therefore, the implementation
complexity of EBU is higher than that of IACG.
In this paper, we propose a simple and feasible dynamic
bandwidth allocation (SFDBA) algorithm in order to utilize
the unused bandwidth and to achieve the implementation
feasibility. SFDBA is based on IACG but it uses only a single
available byte counter and a single down counter for a groupof queues of a same service class. Since multiple queues sharethe common available byte counter, the unused bandwidth ofa queue can be utilized by another queues. For better service
fairness, SFDBA changes the starting queue of scheduling ina round-robin manner. Since only a common counter is used
for a group of queues, SFDBA is simpler than IACG. Hence
SFDBA is more feasible than IACG. Using simulations, weshow that SFDBA is superior to IACG in mean delay, frame
delay variance and frame loss rate. In addition, we illustratethat SFDBA is better than EBU in mean delay and frame delay
variance despite that SFDBA is simpler than EBU.
In this paper, in the section II, we explain the bandwidth utilization problem of IACG algorithm and describe the proposed
SFDBA algorithm. Then, we explain the polling mechanismof the proposed SFDBA algorithm in the section III. In thesection IV, we evaluate performance of each algorithm andshow that SFDBA algorithm outperforms IACG algorithm
using simulations. Also we compare performance of SFDBA

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

algorithm to that of EBU algorithm using simulations. The
conclusions are given in the section V.
II.

S IMPLE AND FEASIBLE DYNAMIC BANDWIDTHALLOCATION

Fig. 1 shows the XGPON system. The XGPON system
consists of an OLT and N ONUs. To support multiple service
classes, ONU i maintains a queue qij for a service class j. A
service class is known as a transmission container (T-CONT)
type in XGPON technology. In this paper, we consider threeservice classes: T-CONT types 2, 3 and 4. Since a static
bandwidth allocation is used for T-CONT type 1 in XGPON,
we do not consider the T-CONT type 1. An incoming framefrom users to ONU i is saved in qij if its T-CONT type is j.
A queue has its unique Allocation Identifier (AllocID).

Fig. 1.

XGPON system

In the downstream direction, the OLT broadcasts frames toeach ONU. When a frame arrives from the OLT, each ONU
accepts only if the destination of the frame is matched. In
the upstream direction, ONUs transmit frames to the OLT
in a time division multiple access manner. To assign a nonoverlapping transmission time-slot to each ONU, the OLT
performs dynamic bandwidth allocation (DBA).
In XGPON, every operation of OLT and ONU is synchronised with a fixed frame duration (FD) which is 125 µs long.
The OLT collects the requests from ONUs, performs the DBA
and produces the DBA result in every FD. The DBA result
has the transmission slot information for an upcoming single
FD. To receive the requests from ONUs, the OLT assigns adynamic bandwidth report upstream (DBRu) transmission slot
to a queue of an ONU. Using the DBRu slot, the queue sends
its queue length to the OLT.
In IACG algorithm, a queue qij has two service parameters:
a service interval Sij with unit of FD and a maximum

299

allocation byte Aij that can be maximally allocated to qij
during its service interval Sij . The queue qij has a down
counter Tij which is decreased by 1 for each FD. In addition,
the queue qij maintains an available byte counter Vij which
denotes the remaining service bytes during its Sij .
When the down counter Tij has expired, Tij is recharged
to Sij and the available byte counter Vij is reset to Aij . Let
rij be the request of queue qij . In IACG, the OLT grants theminimum of the request rij and the value of Vij . The OLT
immediately decreases each the request rij and the value of
Vij by the grant amount. The maximum grant size of qij islimited by Aij .
We now explain the bandwidth utilization problem of IACG.
In IACG, a queue cannot use an unused bandwidth of anotherqueue. For example, consider two queues of T-CONT typej, q1j and q2j . Suppose that r1j = 100, V1j = 0, r2j = 0,
and V2j = 100. Than IACG will not grant any bandwidth forqueue q1j despite V2j remains unused. This inefficiency of
IACG degrades the DBA performance.
In order to solve the utilization problem of IACG, we
propose SFDBA algorithm. In SFDBA, a queue does not havethe individual counters Tij and Vij . Instead, all queues of thesame T-CONT type share a single down counter and a single
available byte counter. Let Tj and Vj be the common down
counter and the common available byte counter of T-CONT
type j, respectively. Also let Sj and Aj be the common service
interval and the common maximum allocation bye of T-CONT
type j, respectively.
The common down counter Tj is decreased by 1 for each
FD. When the down counter Tj has expired, Tj is recharged
to Sj and the common available byte counter Vj is reset to
Aj . The common maximum allocation byte Aj is calculated
by
N
X
Aj
Aij
=
.
(1)
Sj
S
i=1 ijIn SFDBA, the OLT grants the minimum of the request rij
and the value of Vj . The OLT immediately decreases each of
the value of Vj and the request rij by the grant amount.
Since the single available byte counter is used for multiple
queues, the upstream channel can be monopolized by a queue.
To prevent the monopolization, the maximum grant size of aqueue can be limited. In this case, the OLT grants the minimumof the request rij , the maximum grant size and the value of
Vj . Another method to prevent the monopolization is traffic
policing using the leaky bucket method [13] to control the
traffic arrival rate of a queue. Since traffic policing is requiredin XGPON, we assume that the leaky bucket method is usedin this paper for simplicity.
Fig. 2 shows the pseudo code of SFDBA for T-CONT typej where j = 2, 3, 4. Scheduling is performed in the order of
T-CONT types 2, 3, and 4. In Fig. 2, the round robin pointerPj denotes the ONU number at which scheduling starts. To
provide the service fairness, the starting ONU number inthe scheduling is changed in the round robin fashion. The
variable F is the remaining bytes of FD and its initial value
is 38,880 bytes when the upstream channel speed is 2.5 Gbps.
The variable gkj is the grant amount of queue qkj . The

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013// k = ONU number// j = T-CONT typek = stop = Pj ;while(1){if (Vj > 0 and F > 0){
gkj = min(Vj , rkj , F );Vj = Vj − gkj ;rkj = rkj − gkj ;F = F − gkj ;} else if (alloc end = 0 and F = 0){
Pj = k;alloc end = 1;}
Tj = Tj − 1;
if (Tj = 0){
T j = Sj ;Vj = Aj ;P Fkj = 0;}k++;k = k mod N ;if (k = stop) break;}Fig. 2.

Pseudo code of SFDBA for T-CONT type 2, 3 and 4

variable alloc end means the end of the allocation. When
alloc end = 1, the allocation has ended. The initial valuesof gkj and alloc end are zero. The variable P Fkj denotes thepolling flag of qkj . The polling flag P Fkj is used in the polling
operation of SFDBA and will be explained in Section III.
For the previous utilization example of IACG, we apply
SFDBA by assuming Vj = V1j + V2j = 100. Then SFDBA
will grant 100 byte for queue q1j . Unlike IACG, the unused
bandwidth of q2j is used by q1j in SFDBA.
If the total sum of requests is less than the size of FD,then the upstream channel cannot be fully allocated. To utilize
the unallocated remainder of FD, the remainder is evenly
distributed to each ONU in IACG [8]. To distinguish theremainder from normal grants, the remainder has T-CONT type
5 and is called as the colorless grant. An ONU can send packets
arrived after the ONU sent its request using the colorless grant.
Note that ONU does not has a queue with T-CONT type 5.
Using the colorless grant, ONU transmits packets from queues
in the order of T-CONT types 2, 3 and 4. We use the colorless
grant scheme of IACG in SFDBA. At the end of DBA, thecolorless grant of ONU k is given by F/N where F is theremaining bytes of FD.

III.

300

P OLLING OPERATION OF SFDBA

Now we describe the polling method of SFDBA. Fig. 3
describes the transmission timing diagram of XGPON. In Fig.
3, the maximum distance between an OLT and and ONU is
20 Km. Also, Ui means the i-th upstream FD and Di denotes
the i-th downstream FD. RTT is the round trip time between
an ONU and an OLT. If the distance between the OLT and the
ONU is 20 Km, RTT is 200 µs. The variable TO is the ONU
response time to receive the grant result from the OLT and toprepare an upstream response. In this paper, TO = 35 µs as
in [1].

Fig. 3.

Transmission timing diagram

In this paper, we modify the polling mechanism of IACG
[8]. In Fig. 3, Gi is the i-th grant result and R0 is the first
request of the ONU. The DBRu field is used by the ONU
to transmit its request. The i-th grant result is produced by
the DBA operation in Di and is transmitted to the ONU at
the beginning of the downstream FD, Di+1 . When the ONU
receives the grant result, it waits for TO , then sends its request
R0 and data packets during the upstream FD, U0 . The request
R0 is the total length of packets in a queue. Since the request
R0 is sent before data packets, it does not reflect the grant
result G0 . The requests received during U0 are used in the DBA
at the downstream FD, D4 . Since SFDBA may produces grant
results for the ONU during D1 , D2 , and D3 , the grant resultsmust be reflected in R0 . Thus, in order to obtain the correct
request, the OLT has to subtract the grant results G0 , · · · , G3from R0 at the beginning of D4 . Therefore, the OLT needs toremember the four most recent grant results for obtaining thecorrect request.
We now explain the DBRu field allocation mechanism of
SFDBA. Queue qkj has a polling flag P Fkj . The OLT can
allocate the DBRu field to queue qkj when P Fkj = 0. If the
OLT allocate the DBRu field to qkj , the flag P Fkj is set to
1. The flag P Fkj is reset to 0 when the down counter Tj
has expired. Therefore, queue qkj has a chance to receive the
DBRu field once per the service interval Sj .
Fig. 4 describes the pseudo code of the SFDBA polling
operation. In Fig. 4, Lj is the ONU number at which thepolling operation starts for T-CONT type j. The variable
DBRkj means whether or not the DBRu field is assigned
to qkj . The variable DS is the size of the DBRu field. In
the XGPON standard, the size DS is 4 bytes. The variablepoll end represents the end of polling operation. The polling
flag P Fkj is set to 0 when the down counter Tj has expired
as shown in Fig. 2.

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

0.0001
0.1

P ERFORMANCE EVALUATION

A. Comparison to IACG
Now we compare performance of SFDBA, IACG andpredictive-colorless-grant offset-based scheduling with flexible
intervals (PCG-OSFI) [10] using simulations. We consider an
XGPON system with N = 16, the maximum ONU line rateof 200 Mbps, the upstream channel rate of 2.5 Gbps. Also
suppose that the maximum round trip time between the OLT
and ONUs is 200 µs, and the ONU response time is 35 µs.
The size of a queue qij is 1 Mbytes.
For the T-CONT type 2 of IACG, we set Ai2 = 7812, Si2 =5, which is equivalent to 100 Mbps. For the T-CONT type 3of IACG, we set Ai3 = 15624, Si3 = 10. That is, 100 Mbps
is given to the T-CONT type 3. For the T-CONT type 4 of
IACG, Ai4 = 15624, and Si4 = 10, which is equivalent to
100 Mbps. For the T-CONT type 2 of SFDBA, we set S2 = 5
and we obtain V2 = 7812 × N from Eq. (1). For the T-CONT
types 3 and 4, we set S3 = S4 = 10. Then we have V3 =V4 = 15624 × N . The reserved bandwidth for each T-CONT
type of PCG-OSFI is equal to that of IACG.
We use the self-similar traffic model of [12] where each
ONU is fed by a number of Pareto distributed on-off processes.
The shape parameters for the on and off intervals are set to 1.4
and 1.2, respectively. Hence, the Hurst parameter is 0.8. The
frame size follows the tri-modal distribution [12], where theframe sizes are 64, 500, and 1500 bytes and their load fractions
are 60%, 20% and 20%, respectively as in [6]. Each simulationis performed until the total number of frames transmitted by
ONUs exceeds 109 for each algorithm.
Traffic is balanced so that each ONU and each queue has
an identical traffic load fraction. The traffic load of each ONU

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0.7

0.8

0.9

1

Offered load

Fig. 5.

Mean delay of T-CONT type 2
1

Pseudo code of SFDBA polling operationIV.

IACG T-CONT2
PCG-OSFI T-CONT2SFDBA T-CONT2

0.001

0.1
Mean delay (sec)Fig. 4.

0.01

Mean delay (sec)// k = ONU number// j = T-CONT typek = stop = Lj ;while(1){
DBRkj = 0;
if (P Fkj = 0 and F > 0){
P Fkj = 1;
DBRkj = 1;
F = F − DS;} else if (poll end = 0 and F = 0){
Lj = k;poll end = 1;}k++;k = k mod N ;if (k = stop) break;}301

IACG T-CONT3
IACG T-CONT4
PCG-OSFI T-CONT3
PCG-OSFI T-CONT4SFDBA T-CONT3SFDBA T-CONT4

0.01

0.001

0.0001
0.1

0.2

0.3

0.4

0.5

0.6

Offered load

Fig. 6.

Mean delay of T-CONT types 3 and 4varies from 0.1 to 0.99. Figs. 5 and 6 show the mean delayof each algorithm. Note that the offered load means the input
traffic load of a single ONU in the Figs. As we can see from
Figs. 5 and 6, the proposed method outperforms other methods
in mean delay.
Figs. 7 and 8 depict the frame delay variance of eachalgorithm. Figs. 7 and 8 show that the proposed method
outperforms other methods in frame delay variance. Fig. 9
illustrates the frame loss rate of each algorithm for T-CONT
types 2 and 3. Thanks to the utilization of unused bandwidth,
the loss rate of SFDBA is better than those of other methods.
B. Comparison to EBU
To increase the DBA efficiency, EBU can allocate an additional DBRu field to a queue [9]. In EBU, the OLT allocatesthe DBRu field once per its service interval like IACG. Also
the OLT can allocate an additional DBRu field to a queue. If
the grant gij > 0 and the DBRu field is not allocated to the

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

0.0001

0.01

IACG T-CONT2
PCG-OSFI T-CONT2SFDBA T-CONT2

0.001

Frame loss rate

Frame delay variance (sec^2)

1e-0051e-0061e-0071e-008IACG T-CONT2
IACG T-CONT3
PCG-OSFI T-CONT2
PCG-OSFI T-CONT3SFDBA T-CONT2SFDBA T-CONT3

0.0001

1e-0051e-0061e-0091e-007
0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0.1

0.2

0.3

0.4

Offered load

Fig. 7.

0.1

Frame delay variance (sec^2)

0.01

Fig. 9.

IACG T-CONT3
IACG T-CONT4
PCG-OSFI T-CONT3
PCG-OSFI T-CONT4SFDBA T-CONT3SFDBA T-CONT40.001
0.0001
1e-0051e-0061e-0071e-0081e-009
0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Offered load

Fig. 8.

0.5

0.6

0.7

0.8

0.9

1

Offered load

Frame delay variance of T-CONT type 2
1

302

Frame loss rates of T-CONT types 2 and 3

expired. It means that the unused bandwidth of the queue qij
cannot be utilized until its down counter Tij has expired. In
contrast, since SFDBA uses a common available byte counter,an unused bandwidth of a queue can be immediately used byanother queues. This difference makes the proposed SFDBA
algorithm works better than the EBU algorithm.
Figs. 12 and 13 depict the frame delay variance of eachalgorithm. Figs. 12 and 13 show that the proposed SFDBA isbetter than the EBU method in frame delay variance. Fig. 14
illustrates the frame loss rate of each algorithm for T-CONT
type 4. The frame loss rates of T-CONT types 2 and 3 arezero in both algorithm thanks to the utilization of the unused
bandwidth and the additional polling mechanism. The frame
loss rates of both algorithms are comparable to each other for
T-CONT type 4 as we can see in Fig. 14.

Frame delay variance of T-CONT types 3 and 4

queue qij then the OLT allocates the additional DBRu field tothe queue qij . It was shown that the additional DBRu is very
effective in [9]. To compare performance of EBU with thatof SFDBA, we apply the additional DBRu mechanism to thepolling operation of SFDBA in this subsection.
We use the same system, the same parameters, and the same
traffic of the subsection IV-A. For the T-CONT type 2 of EBU,
we set Ai2 = 7812, Si2 = 5, which is equivalent to 100
Mbps. For the T-CONT type 3 of EBU, we set Ai3 = 15624,
Si3 = 10. That is, 100 Mbps is given to the T-CONT type 3.
For the T-CONT type 4 of EBU, Ai4 = 15624, and Si4 = 10,
which is equivalent to 100 Mbps. We do not use the nonassured T-CONT type 3 of EBU.
Figs. 10 and 11 show the mean delay of each algorithm.
As we can see from Figs. 10 and 11, the proposed SFDBA
outperforms the EBU algorithm in mean delay. In EBU, an
unused bandwidth of a queue qij is added to the available byte
counter of another queue only when the down counter Tij has

EBU T-CONT2SFDBA T-CONT2

Mean delay (sec)

0.001

0.0001
0.1

Fig. 10.

0.2

0.3

0.4

0.5
0.6
Offered load

0.7

0.8

0.9

1

Mean delay of T-CONT type 2

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

1

0.01

EBU T-CONT3
EBU T-CONT4SFDBA T-CONT3SFDBA T-CONT4

0.001
Frame delay variance (sec^2)

Mean delay (sec)

0.1

0.01

0.001

303

EBU T-CONT3
EBU T-CONT4SFDBA T-CONT3SFDBA T-CONT4

0.0001

1e-0051e-0061e-0070.0001

1e-008
0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

0.1

0.2

0.3

0.4

Offered load

Fig. 11.

Mean delay of T-CONT types 3 and 4

0.00000010

0.5

0.6

0.7

0.8

0.9

1

0.8

0.9

1

Offered load

Fig. 13.

Frame delay variance of T-CONT types 3 and 4
1

EBU T-CONT2SFDBA T-CONT2EBU T-CONT4SFDBA T-CONT4

0.01
Frame loss rate

Frame delay variance (sec^2)

0.1

0.00000001

0.001

0.0001

1e-0051e-0060.00000000
0.1

Fig. 12.

0.2

0.3

0.4

0.5
0.6
Offered load

0.7

0.8

0.9

1

Frame delay variance of T-CONT type 2

V. C ONCLUSIONS
We have proposed the SFDBA algorithm for the dynamic
bandwidth allocation of XGPON by modifying the IACG
algorithm. In IACG, a queue has a down counter to count its
service interval and has an available byte counter to control its
service amount. Because of the individual counters, a queue
can not utilize the unused bandwidth of another queues in
IACG. In order to solve the utilization problem of IACG, in
SFDBA, all queues of a same T-CONT type use a common
down counter and a common available byte counter. Thanks
to the common counters, a queue can utilize the unused
bandwidth of another queues. Using simulations, we haveshown SFDBA outperforms existing algorithms in mean delay,
frame delay variance and frame loss rate.
R EFERENCES[1] ITU-T Rec. G.987.3 Rev.2, “10-Gigabit-capable passive optical networks (XG-PON): Transmission convergence (TC) specifications,”

1e-007
0.1

Fig. 14.

0.2

0.3

0.4

0.5
0.6
Offered load

0.7

Frame loss rate of T-CONT type 4

2010.
[2] ITU-T Rec. G.987.1, “10 Gigabit-capable passive optical network (XGPON): General requirements,” 2010.
[3] ITU-T Rec. G.984.3, “Gigabit-capable passive optical networks (GPON): Transmission convergence layer specification,” 2008.
[4] ITU-T Rec. G.984.1, “Gigabit-capable passive optical networks (GPON): General characteristics,” 2008.
[5] J. D. Angelopoulos, H. C. Leligou, and T. Argyriou, “Prioritized
multiplexing of traffic accessing an FSAN-compliant GPON,” Third
IFIP-TC6 Networking Conference, Arthens, Greece, 2004.
[6] H. C. Leligou, Ch. Linardakis, K. Kanonakis, J. D. Angelopoulos, andTh. Orphanoudakis, “Efficient medium arbitration of FSAN-compliant
GPONs,” Int. J. Comm. Syst., vol. 19, no. 5, pp. 603-617, June 2006.
[7] J. D. Angelopoulos, T. Argyriou, S. Zontos, and T. Van Caenegem,“Efficient transport of packets with QoS in an FSAN-aligned GPON,”
IEEE Comm. Mag., vol. 42, no. 2, pp. 92-98, Feb. 2004.
[8] M.-S. Han, H. Yoo, B.-Y. Yoon, B. Kim, and J.-S. Koh, “Efficient
dynamic bandwidth allocation for FSAN-Compliant GPON,” OSA J.
Opt. Netw., vol. 7, no. 8, pp. 783-795, Jul. 2008.
[9] M.-S. Han, H. Yoo, and D.-S. Lee, “Development of Efficient Dynamic

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

[10]

[11]

[12]
[13]

304

Bandwidth Allocation Algorithm for XGPON,” ETRI Journal, vol. 35,
no. 1, pp. 18-26. 2013.
K. Kanonakis and I. Tomkos, “Offset-Based Scheduling With Flexible
Intervals for Evolving GPON Networks,” Journal of Lightwave Technology, vol. 27, no. 15, pp. 3259-3268, Aug. 2009.
C. H. Chang, N. M. Alvarez, P. Kourtessis, R. M. Lorenzo, and J. M.
Senior, “Full-Service MAC Protocol for Metro-Reach GPONs,” Journalof Lightwave Technology, vol. 28, no. 7, pp. 1016-1022, April 2010.
G. Kramer, Ethernet passive optical networks, McGraw-Hill, 2005.
A. S. Tanenbaum, “Computer Networks, Fourth Edition,” Prentice Hall
PTR, 2003,

Man Soo Han received the B.S., M.S. and Ph.D. degrees in electrical engineering from Korea Advanced
Institute of Science and Technology (KAIST), Korea
in 1992, 1994 and 1999 respectively. He was asenior researcher of the Electronics and Telecommunications Research Institute (ETRI) Daejon, Korea
from 1999 to 2003. He is an associate professor
in the Department of Information and Communications Engineering at Mokpo National University,
Korea. His research interest includes scheduling inhigh speed networks, passive optical networks andwireless networks. He is a member of IEEE, OSA, IEICE, and KICS.

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013305

Effective Use of Computational Resources inMulticore Distributed Systems
Hidehiro Kanemitsu*, Masaki Hanada**, Takashige Hoshiai***, Hidenori Nakazato*****Media Network Center, Waseda University, Japan**Department of Information Systems, Tokyo University of Information Sciences, Japan***Department of Computer and Information Science, Sojo University, Japan****Global Information and Telecommunication Institute, Waseda University, Japan.
kanemih@ruri.waseda.jp, mhanada@rsch.tuis.ac.jp, hoshiai@cis.sojo-u.ac.jp, nakazato@waseda.jp

Abstract— In the last decades, many kinds of task execution
models such as grid and cloud computing have been developed. In such distributed systems, each task is processed byrespective processor in multicored computers e.g., household
PCs which we can easily harness in recent years. If there is
one policy to automatically decide the “best” combination andthe number of processors (and computers), we effectively utilize
those computational resources, thereby large number of jobs canbe executed in parallel. In this paper, we propose a method
for mapping of execution units for such environments. The
method adopts a remapping technology after processor-execution
unit mapping[11] is finished. Experimental comparisons by asimulation show the advantages of the proposed method.
Index Terms— Task Clustering, Multicore, Distributed Systems, Parallel Computing

I. I NTRODUCTIONR

ECENTLY, task execution models are becoming diverse,
e.g., grid computing[1], cloud computing. Such computational models often require parallel execution models suchas parametric job execution, background data analysis for data
mining, and searching for a target value in a key-value store[2].
Irrespective of dedicated computers or household computers,
they should be effectively used when a parallel execution
model is applied. Moreover, requirements for job execution
tends to become diverse due to multiple demands from thejob submitter. To handle with such diversity, multi-objective
approaches for task scheduling and resource allocation model
have been proposed and being under development[3], [4],[5]. Those approaches assume that requirements (e.g., QoS,
deadline for the job execution, total costs, and so on) are
decided by a job submitter, i.e., an user. Thus, those multiobjective approaches focus on how to satisfy every objective
specified by an user. If multiple objective should be satisfied
Manuscript received June 25, 2013.
Hidehiro Kanemitsu is with Media Network Center, Waseda University,
1-104, Totsuka, Shinjuku, Tokyo, Japan (phone: +81-3-3204-8223; e-mail:kanemih@ruri.waseda.jp).
Masaki Hanada is with Department of Information Systems, Tokyo
University of Information Sciences, 4-1, Onaridai, Wakaba, Chiba, Japan(phone:+81-43-236-1101;e-mail: mhanada@rsch.tuis.ac.jp).
Takashige Hoshiai is with Department of Computer and Information
Science, Sojo University, 4-22-1, Ikeda, Nishi, Kumamoto, Japan (phone: +8196-326-3111;e-mail: hoshiai@cis.sojo-u.ac.jp).
Hidenori Nakazato is with Global Information and Telecommunication
Institute, Waseda University, Bldg. 29-7, 1-3-10 Nishi-Waseda Shinjuku-ku,
Tokyo, Japan (phone: +81-3-3203-4151; e-mail: nakazato@waseda.jp) .

at the same time in a distributed environment, dynamic natures
such as every computer’s load and CPU status and so on
must be taken into account. To do this, provisioning is needed
for preparing calculate every problems provided by thoseobjectives. For example, how to propagate each computer’s
resource information and how to aggregate “peers” to constructpeer groups in the overlay network based on specific criteria
in advance are indispensable[3], [6], [7].
We proposed a method for effective use of computational
resources each of which has a single processor in a heterogeneous distributed system [11]. The method automaticallyderives set of mapping between each processor and eachassignment unit (i.e., the set of tasks in a DAG (Directed
Acyclic Graph) program such as a workflow type job), bywhich the degree of contribution for each processor toward
the response time minimization is maximized. However, themethod does not assume more realistic situations, e.g., eachcomputer may have a parallel execution scheme such as
multicore and multi OS by virtualization. Thus, our previously
proposed method can not be applied to those environments.
If a model which accommodates them, the response time
can be minimized with a smaller number of computers. In
this paper, we propose a theoretical method for deciding theset of mapping between each computer and each assignment
unit for effective use of computational resources, where eachcomputer can have parallel execution scheme. The proposed
method assumes that a computer with two or more processors
as two or more processors are completely connected overthe network with infinite network bandwidth . Then a lower
bound of assignment unit size is mathematically decided foreach processor for limiting the number of processors. Actual
assignment units are generated by a task clustering algorithm
until each size exceeds the lower bound. Among processors
which belong to the same computer, every task in assignment
units is locally scheduled without degrading task parallelism.
Consequently, the required number of computer can be smaller
than that of the method proposed in [11]. Experimental
comparison is conducted by a simulation program. In thesimulation, we evaluate the degree of contribution for eachcomputer and show advantages of the proposed method overrelated works and the method we proposed in [11].
The remainder of this paper is organized as follows. Sec. II
presents our assumed model. Then problem definitions and theobjective of the proposal are presented in sec. III. The detailed
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

306

CPU
AssignData Dependency

Task(I) Derive a lower
bound for eachassignment unit
(cluster)

Assignment
Unit(II) Decide the PE
for the cluster

Job(III) Generate acluster whose size
exceeding thelower boundAssignParallelized Job

Proposed in [6].

(IV) Re-mapping
for reducing # ofcomputers(Proposed Part)CPU
AssignAssignment
Unit

AssignParallelized Job
Fig. 1.

Proposed partcontent of the proposal is presented in sec. IV, and theoreticalanalysis in terms of effect of the proposal is presented in sec.
V. Advantages of the proposal is shown by the experimental
comparisons in sec. VI. Finally, a conclusion and a future work
are presented in sec. VII.
II. A SSUMED M ODEL
A. Job ModelAn assumed job is expressed as a Directed Acyclic Graph(DAG), which is known as one of task graph representations.
s) be the DAG, where s is the number
Let Gscls = (Vs , Es , Vcls
of task merging steps (described in the latter half part in thissubsection), Vs is the set of tasks after s task merging steps, Es
is the set of edges (data communications among tasks) aftersis the set of clusters whichs task merging steps, and Vcls
consists of one or more tasks after s task merging steps. An
i-th task is denoted as nsi . Let w(nsi ) be a size of nsi , i.e.,w(nsi ) is the sum of unit times taken for being processed by
the reference processor element. We define data dependency
and direction of data transfer from nsi to nsj as esi,j . And c(esi,j )is the sum of unit times taken for transferring data from nsi to
nsj over the reference communication link.

One constraint imposed by a DAG is that a task can not
be started execution until all data from its predecessor tasks
arrive. For instance, esi,j means that nsj can not be started until
data from nsi arrives at the processor which will execute nsj .
And let pred(nsi ) be the set of immediate predecessors of
nsi , and suc(nsi ) be the set of immediate successors of nsi . If
pred(nsi ) = ∅, nsi is called START task, and if suc(nsi ) = ∅,nsi is called END task. If there are one or more paths from nsi
to nsj , we denote such a relation as nsi ≺ nsj .

B. Task Clusterings
We denote the i-th cluster in Vcls
as clss (i). If nsk is included in clss (i) by “the s + 1 th task merging”, we formulate
one task merging as clss+1 (i) ← clss (i) ∪ {nsk }. If any twotasks, i.e., nsi and nsj , are included in the same cluster, they
are assigned to the same processor. Then the communication
between nsi and nsj is localized, so that we define c(esi,j )becomes zero. Task clustering[8], [9], [10] is a set of task
merging steps, that is finished when certain criteria have beensatisfied.

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

C. System Model
We assume that each computer is completly connected toothers, with not identical processing speeds and communication bandwidths. Each computer has one or more processing elements (PE). The set of computers is expressed as
M = {M1 , M2 , . . . , Mm }. The set of PEs in Mi is expressed
as Pi = {Pi,1 , Pi,2 , . . . , Pi,|Pi | }, and let the set of processing
speeds in Pi as αi , i.e., αi = {αi,1 , αi,2 , . . . , αi,|Pi | }, where|Pi | = |αi |.
As for data communication among computers, let the set ofcommunication bandwidths be β, i.e.,∞
β1,2 β1,3 . . . β1,m
 β2,1∞
β2,3 . . . β2,m  β3,1 β3,2∞ . . . β3,m 
(1)
β=

 ..
..
..
..
.. 
 .

.
.
.
.
βm,1 βm,2 βm,3 . . . ∞βi,j means the bandwidth from Mi to Mj . We assume that acommunication bandwidth between two computers, e.g., Mi
and Mj is the same between any one of Pi and any oneof Pj . The processing time in the case that nsk is processedon Pi,p is expressed as tp (nsk , αi,p ) = w(nsk )/αi,p . The datatransfer time of esk,l over βi,j is tc (esi,j , βk,l ) = c(esi,j )/βk,l .
This means that both processing time and data transfer time
are not changed with time, and suppose that data transfer timewithin one computer is negligible.
III. P ROBLEM D EFINITION
A. Processor Utilization in Singlecore Distributed systems
In this paper, we propose a method for processor utilization
in a distributed system, where each computer has one or more
PEs. The difference between the method proposed in [11] anda method in this paper is whether such multicore computers are
considered or not. According to [11], “processor utilization”,
in other words, “effective use of computational resources”,
means to maximize the degree of contribution for reducing
the schedule length for each PE. Fig. 1 shows a process flow
we are assuming. A job is processed by three steps, i.e., (I) alower bound for each cluster (set of tasks) execution time isderived, (II) mapping procedure to assign a PE to a cluster,(III) task clustering algorithm to generate actual clusters. Since
these procedures were proposed in [11], we describe only theabstract.
1) Lower Bound Derivation for each Cluster Execution
Time: According to fig. 1, the method proposed in [11] derives
a lower bound for each cluster execution time (total task
execution time in a cluster on a PE). To impose a lower
bound, the number of required PEs is limited to some extent.
At the same time, the response time should be minimized forachieving processor utilization.
Since the schedule length can not be derived until every
task is scheduled, each lower bound should be decided withestimating the schedule length. This is because these three procedures in fig. 1 are performed before a task scheduling[14].
Thus, the method in [11] defines an indicative value for theschedule length as WSL (Worst Schedule Length) [11]. Let

n15

cls5 (1)
n 52







n 53









5

assign

n15

cls5 (1)



n5



307

n 54




n 56


cls5 (4)

n 52








n 57 





n 53



 n 55 cls (4)

n 54



5





n 56

n 57 



assignβ1,2 = 0.5

P1,1
α1,1 = 4β2,1 = 2

P2 ,1
α 2,1 = 2(a) After 5 tesk merging steps have been done.

Fig. 2.

(b) After processor assignments have been done.

Example of WSL

define “WSL after s-th task merging step” as slw (Gscls , ϕs ),which means the largest value that the response time can takewhen every task is executed as late as possible after s task
merging steps and the mapping state ϕs has been decided.
Fig. 2 shows one example of how WSL is decided. In thisfigure, (a) is the state after 4 task merging steps have been
finished, and (b) is the state that each generated cluster isassigned to one actual PE. In (b), note that data communication
time in the same PE is set to 0. Then we WSL is derived bytracing n51 → n53 → n55 → n52 → n57 , i.e., slw (G6cls , ϕ6 ) = 25.
In [11], it is proved that minimizing WSL has good effecton the schedule length, i.e., it is necessary that WSL should
be minimized to minimize the schedule length. Since actual
WSL after s-th task merging step can not be decided until stask merging steps have been finished, we must estimate theupper bound of WSL after s − 1 task merging steps have been
finished(i.e., before s-th task merging step). If we define an
upper bound of the difference between WSL after s-th task
merging step and the initial WSL(i.e., 0-th task merging step)s−1
as ∆slw(δ), we haves−1∆slw,up
(δ) =
{
}

∑
{
}
0
0
w(n0k )
max
c(e
)
max
w(n
)
k,l
k
≺
0
0
 n0k ∈V0
 nk ∈seqs−1
ek,l ∈E0


+


αp
β(p)
δαp

max
0

+δ −

ek,l ∈E0{}c(e0k,l )max {βp,q },(2)βp,q ∈βwhere ϕ0 is the initial mapping state that each task is assigned
to a “virtual PE” having the maximum processing speed andthe maximum communication bandwidth. At the mapping state
ϕ0 , the critical path length equals to the WSL at the initial state
ϕ0 (for more details, see [11]). At eq. (2), δ is the lower boundof each cluster execution time. δ is derived by temporarily
assuming identical network, where we derive the lower boundfor every cluster execution time on tasks dominating the WSL.
≺
seqs−1is a set of tasks on a path dominating slw (Gs−1
cls , ϕs−1 )(e.g., at (b) in fig. 2, seq5≺ is {n51 , n53 , n55 , n57 } or {n51 , n52 , n57 }).
Fig. 3 shows one example how δ is derived. In this figure,(a) is the state after 4 task merging steps have been finished. In(a) there are unmerged tasks each of which is assigned to the
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

assignP1

assigncls 4 (1)4Path of sl w (G cls, φ4 )

cls '6 (1)PpP2

assignPp
assignunmerged
tasks

2
×
αp
{
}


αp 0max c(e0k,l ) ek,l ∈E0
w(n0k ) + max
{w(n0k )}


0
β(p)
nk ∈V0s−1s∆slw,up(δopt(αp , β(p))) =

v
u
u
u
u
u
t

∑

≺
n0k ∈seqs−1

P3
assignPp

max
0

assign−P44(a) State after 4 task mergings. (b) Try to minimize sl w (G cls , φ4 )over the identical network of Pp .

P1

assigncls 6 (1)P2

assignPp

P3

new cluster

assignP4(c) State after 6 task mergings.
Fig. 3.

Assumed model for WSL derivation“virtual PE” having the maximum processing speed and communication bandwidth, respectively. On the other hand, othertasks are assigned to an actual PE. In this state, the dashedline corresponds to the path of WSL, i.e., slw (G4cls , ϕ4 ). Then
we temporarily assume these tasks will be clustered and eachcluster is assigned to an identical PE(in (b), the PE is Pp ). We
4
have ∆slw,up(δ), which is a function with respect to δ. From(b) we obtain the optimal value of δ (let call “δopt ”) by which
4∆slw,up(δ) is minimized. Once δopt is obtained, every clusterin (b) is restored to clusters in (a) and then unmerged tasksin (a) are merged into one new cluster until its execution timeexceeds δopt (see (c)). It is assumed that the cluster execution
time of the new cluster in (c) exceeds δopt after 6 task merging
steps (it was not enough after 5 task merging steps).
s−1
We obtain the minimum value of slw,up
by differentiatingeq. (2) with respect to δ. If we define the value of δ whens−1sslw,uptakes the minimum as δopt
(Pp ), we haves
δopt(Pp ) =
v
{
}

∑
u
0 )
u
w(n0k )
0 )}
max
c(e
max
{w(n
u n0 ∈seq≺k,lk
 n0k ∈V0

e0k,l ∈E0
u k
s−1

,
u
+


t
αp
αp
β(p)
where β(p) is the minimum communication bandwidth of Pp .
sδopt
(Pp ) is the lower bound of the cluster execution time to besgenerated after s-th task merging step. If δopt
(Pp ) is applieds−1
to ∆slw,up (δ), we have308

ek,l ∈E0{}c(e0k,l )max {βp,q }.

(3)

βp,q ∈β2) Processor Selection: At this phase, a PE to be assigned
to a new cluster(e.g., “new cluster” at fig. 3) is decided.
s−1s
If ∆slw,up(δopt(αp , β(p))) is minimized by applying actual
values of αp and β(p), the PE having these values should
be selected for processor assignment. Then the minimizeds−1s∆slw,up(δopt(αp , β(p))) is obtained, by which the upperbound of WSL can be minimized.
3) Task clustering: Since the PE to be assigned has beenss−1sdecided, both values of δopt
(Pp ) and ∆slw,up(δopt(αp , β(p)))
are decided. The objective of the task clustering is to generatesthe cluster whose execution time exceeds δopt
(Pp ) and tosminimize WSL, i.e., slw (Gcls , ϕs ). One policy of the taskclustering is to select pivot (a cluster in which at least one task
belongs to slw (Gs−1
cls , ϕs−1 ) and target (a cluster in which atleast one task has data dependency with one of task in pivot).
These two clusters are merged into a new cluster, and thenif the cluster execution time of the cluster does not exceedssδopt(Pp ), the cluster becomes the “new pivot”. Then the newtarget is selected for more merging steps.
By repeating (1) - (3), every cluster execution time becomeslarger than each decided lower bound. In such an obtained
output DAG, it was found that the degree of contribution forspeed up can be maximized[11].
B. Objective of the Proposal
The method for processor utilization described above has
good effect on a “single core distributed system”, where each
PE is completely connected over the network. However, themethod does not take into account the locality among PEs. In
fig. 1, a multicore distributed system is assumed. If the method
proposed in [11] is applied in such an environment, eachcluster(assignment unit) is assigned to different computers (seefig. 1). Thus, we propose a processor mapping policy taking
into account the locality among PEs. In the top part of fig.
1, two clusters are assigned to different computers. This isbecause that the method proposed in [11] tries to find the PE
to be assigned to a cluster by only applying its performance
information to eq. (3). On the other hand, the bottom part offig. 1 corresponds to the result by applying the proposal. In
this case, both clusters are assigned to the same computer. The
process of our proposal is performed after three steps ((I)-(III)in fig. 1).
IV. P ROPOSALAs stated in the previous section, the proposed method is
performed after three steps proposed in [11] have finished. In
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

INPUT: < GR
cls , ϕR >, where R is ♯ of task merging step required toobtain the output DAG of [11].
′OUTPUT: < GR
cls , ϕR′ >, where R is R plus “♯ of the remapping
required to obtain the output DAG of the proposal”.
Define P (clsR (k), ϕR ) = Pi,p , where clsR (k) is assigned to Pi,p at
ϕR .
Define M (clsR (k), ϕR ) = Mi , where P (clsR (k), ϕR ) = Pi,p isincluded in Mi .
Define comR (k) as the set of tasks in clsR (k) s.t., they have outgoingor incoming communication with other clusters.
Define CHK is the set of clusters dominating slw (GRcls , ϕR ) obtainedby the method of [11].
1. WHILE CHK ̸= ∅ DO
2.
Find clsR (k) s.t.,φ(clsR (k)) =max{φ(clsR (i))};309

immediate predecessor

Pj,r

Pj,q

of top R (k)

Pj,q

Pj,r

assignassignassigntop R (k)assign
Pi,1

Pi,1

Pi,p

cls R (k)Pi,pcls R (k)clsR (i)∈CHK

3.
4.
5.
6.
7.
8.
9.

Set an immediate predecessor or successor task of inR (k)Ror outR (k) as nRu , s.t., nu ∈ clsR (l).;FOR EACH clsR (l) DO∆(k, αi,p , αj,q ) ← ε(k, αi,p , αj,q ) − ω(k, αj,q );END FOR
Find max of ∆(k, αi,p , αj,q ) and move clsR (k) to Pj,q .;Remove clsR (k) from CHK.;
END WHILE(a) before remapping: a set of tasks on one seq pR .
Fig. 5.

Fig. 4.

(b) after remapping

Example of the cluster remapping algorithm

Procedures for cluster remapping.

this section, we present details in the proposal.
A. Algorithm Overview
As stated above, it was proved that minimizing WSL canlead to reduction of the schedule length. Thus, at first clusters
dominating WSL must be specified for “remapping”. This isbecause such a remapping can make WSL smaller than thatobtained after three steps ((I)-(III) at fig. 1), thereby it isconceivable that the schedule length is also made smaller by
the localization of the data communication.
Fig. 4 shows the cluster remapping algorithm, and fig. 5
shows one example of the algorithm with using the same
notations as fig. 4. The algorithm firstly tries to find a cluster to≺be moved by tracing tasks in seqR(line 1 - 9 at fig. 4). In fig.
5, (a) means the state after procedures proposed in [11] havebeen finished. In this state, suppose that colored tasks belong≺
to seqR. At first, one cluster in which at least one task belongs≺
to seqR
is selected for the remapping algorithm. The selection
criterion is based on calculating the evaluation value(i.e., ∆function at line 7 in fig. 4). This evaluation value means how
long the response time can be reduced by moving the cluster toanother PE. For each cluster dominating WSL, the algorithm
derive ∆ function as an evaluation value and then select thecluster as a moving target by which the response time caneffectively reduced.

cluster to be moved is the one having the maximum sum ofcommunication time and task execution time in WSL.
Next, we describe the details of the criterion for cluster
selection. Let us return to the definition of slw (GRcls , ϕR ),whose details of the derivation are defined in table. I(for moredetails, see [12]). As can be seen in table. I, slw (GRcls , ϕR )is derived by taking the maximum of LVR (i), which isderived by applying T LR (i) and BLR (i). T LR (i) means
the maximum start time of a task in clsR (i), while BLR (i)means the maximum elapsed time from start time of a task
to the finish time of the END task including communicationtime(i.e., the path length from a task to the END task). In thetable, inR (i) and outR (i) are sets of tasks having incoming
communications and outgoing communications, respectively(In fig. 2, in5 (1) = {n55 }, and out5 (1) = {n51 , n52 , n55 }). Communication time taken by a cluster in WSL is derived by anincoming communications(edge) and an outgoing communications(edge). On the other hand, task execution time taken by acluster (let define as clsR (i) in WSL is derived by calculatingR
the maximum of S(nRk , i) for each nk ∈ clsR (i) defined inRtable. I. S(nk , i) means the start time of nR
k in clsR (i) whennR
k is scheduled as late as possible. For example, in fig. 2(b),we have∑
1
1
S(n53 ) =w(n5k ) − (w(n53 ) + w(n55 ))4 5
4nk ∈cls5 (1)=B. Cluster Selection
The proposed cluster remapping is to move each cluster
dominating slw (GRcls , ϕR ) to one of unassigned PEs. Thus,
as first the algorithm finds one of those clusters for eachmoving procedure. Intuitively, the cluster to be selected for the
remapping is the one which has the greatest effect on the WSL,
i.e., that has the most execution time and communication timein slw (GRcls , ϕR ). This is because that WSL can be largely
reduced by moving such a cluster to the faster PE. Moreover,
localization of large amont of communication can contributeto the reduction of WSL. Thus, the criterion for selecting the1(w(n51 ) + w(n52 )) = 1.5.
4

(4)

R
After the time of S(nRk , i) has been elapsed, nk can beRprocessed. Then nk sends data to other tasks in other clusters
as outgoing communications. Thus, the total time taken by data
communication and task execution of one cluster in WSL canbe defined as follow.

φ(clsR (i)) =R
comin (clsR (i)) + S(nRk , i) + tp (nk , αp,q )+comout (clsR (i)),(5)

where comin (clsR (i)) is the incoming communication time
as a part of T LR (i), comout (clsR (i)) is the outgoing communication time as a part of BLR (i). That is, φ(clsR (i)) is
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

310

TABLE I
R
PARAMETER DEFINITION RELATED TO slw (GRcls ) (H ERE nk ∈ clsR (i)).

Parameter

Definition
}
R
R
R
nR
|∀n
∈
pred(n)s.t.,
n∈/clsR (i) ∪ {ST ART T asks ∈ clsR (i)}.
l
k
l
{ k
}
R
R
R
nR
/ clsR (i) ∪ {ST ART T asks ∈ clsR (i)}.
k |∃nl ∈ pred(nk )s.t., nl ∈
{
}
R
R
R
nR
/ clsR (i) ∪ {EN D T asks ∈ clsR (i)}.
k |∃nl ∈ suc(nk )s.t., nl ∈{topR (i)inR (i)outR (i)desc(nRk , i)S(nR
k , i)
tlevel(nRk)
T LR (i)RR
R{nR∈ clsR (i)} ∪ {nR
l |nk ≺ nl , nl ∑
k}
t (nR
t (nR
l , αp ) −l , αp ).
nR ∈clsR (i) pnR ∈desc(nR ,i) p
l{
l
k
}
R
R
max
tlevel(nl ) + tp (nl , αp ) + tc (el,k , βq,p ) , if nRk ∈ topR (i).
nR ∈pred(nR )lkR
T LR (i) + S(nk , i), otherwise.
{}
tlevel(nRmaxk ) ..
Rn ∈topR (i)
k

∑





{

blevel(nR
k)

max

/
nR ∈suc(nR ),nR ∈cls
R (i)
l
k
l

level(nRk)

RRtlevel(n{ k ) + blevel(nk ).
}
R
S(nR
,
i)
+
blevel(nkk) .

BLR (i)maxnR ∈outR (i)k

LVR (i)ncls5 (1)
n

5
2





n


max

5
3

comin (cls5 (1))



n

}
level(nRk) .

{LVR (i)}.

C. Cluster Remapping
n15

n

5
4




5
5

max

nR ∈clsR (i)kclsR (i)∈V R
cls

5
1





{

T LR (i) + BLR (i) =slw (GRcls , ϕR )



}
R
R
tp (nRk , αp ) + tc (ek,l , βp,q ) + blevel(nl ) .



n 56

n 57 

t p (n 52 , α1,1 )cls5 (4)Suppose that a cluster which will be checked is clsR (k), andclsR (k) was assigned to Pi,p ∈ Mi by the method[11]. Thenthe algorithm calculates the difference between ε(k, αi,p , αj,r )and ω(k, αj,q ). They are defined as follows.

S(n 52 ,1)

n 53

n 52

n 55

com out (cls5 (1))

cls5 (1)cls5 (4)n 57

Path of sl w (G 5cls , φ5 )ε(k, αi,p , αj,r )∑1=
αi,p Rw(nRu)+

nu ∈clsR (k)Fig. 6.

Example of the cluster selection criteria

+

1
βq,p

∑

comin (cls5 (1)) = 0,comout (cls5 (1)) = tc (e52,7 , β1,2 ) = 10,
φ(cls5 (1))= comin (cls5 (1)) + S(n52 , 1)
+tp (n52 , α1,1 ) + comout (cls5 (1))= 0 + 3 + 1 + 20 = 24.

(6)

In fig. 4, at line 2 the algorithm finds a cluster clsR (k)having the maximum φ value in CHK for cluster remapping.

βq,pc(ey,x )nR
x ∈clsR (k),nRy ∈clsR (l)c(ex,y ),(7)nR
x ∈clsR (k),nRy ∈clsR (l)total time involved by clsR (i).
Fig. 6 shows one example of how φ(clsR (i)) is decided.
In this figure, the path of WSL is the same as fig. 2. At theleft side, cls5 (1) and cls5 (4) have been assigned to individual
PEs, and the right side shows elements of φ(cls5 (1)). A
dashed circle corresponds to the area for communications,while a dashed rectangle corresponds to the area for task
executions. In this example, comin (cls5 (1)) is 0 because there
is no incoming communication at cls5 (1)). Since the path ofsl5 (G5cls ) is n51 , n53 , n55 , n52 as fig. 2, we have∑1ω(k, αj,q ) =

1
αj,q

∑

w(nR
u ).

(8)

nR
u ∈clsR (k)ε(k, αi,p , αj,r ) is the sum of cluster execution time and data
communication time (incoming communication and outgoing
communication with a specific cluster (let define as clsR (l)and clsR (l) is assigned to Pj,r )). That is, ε(k, αi,p , αj,r )means the total time taken to process clsR (k) and to communicate with clsR (l). On the other hand, ω(k, αj,q ) does
not require data communication time with clsR (l) because
it is included in the same computer(let assume no cluster
is assigned to Pj,q ). Then we define the evaluation value asfollow.
∆(k, αi,p , αj,q ) = ε(k, αi,p , αj,q ) − ω(k, αj,q ).

(9)

For each cluster clsR (k), the algorithm finds the maximum
value of ∆(k, αi,p , αj,q ) with varying j and q. This is the same
meaning as varying l in clsR (l)(at line 5 in fig. 4). When thecluster clsR (l) or Pj,q is found at line 7 in fig. 4, the cluster isremoved from the set of clusters CHK. When CHK becomes
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

empty, the algorithm is finished.
Selection of the target for moving the cluster clsR (k) by
maximizing ∆(k, αi,p , αj,q ) means that the algorithm tries tofind the PE by which the time taken for processing and data
communication is minimized.

V. T HEORETICAL A NALYSIS
Since an objective of the proposed cluster remapping is
to reduce WSL in order to minimize the schedule length,with maintaining the number of required PEs. Thus, in thissection we analyze the possibility for WSL reduction byeach cluster remapping procedure. Assume that an cluster
clsR (k) is assigned to Pi,p and clsR (k) dominates WSL, i.e.,slW (GRcls ). Then suppose that clsR (k) is moved to Pj,q by acluster remapping procedure. We define φ(clsR (k)) after the
remapping as φ′(clsR (k)) and the difference of φ(clsR (k))
as ∆φ(clsR (k)). Similarly, let differences of comin (clsR (k)),
R
S(nRm ), and comout (clsR (k)) be ∆comin (clsR (k)), ∆S(nm ),and ∆comout (clsR (k)), respectively. Then we have∆φ(clsR (k)) = φ(clsR (k)) − φ′(clsR (k))= ∆comin (clsR (k)) + ∆S(nRm)
R+tp (nRm , αi,p ) − tp (nm , αj,q )+∆comout (clsR (k))
(
)
1
1
=
−
c(eR
r,s )
βu,i
βu,j
)
(
∑
1
1
−
w(nR
+
l )
αi,p
αj,q
R
nl ∈clsR (k)
(
)
1
1
+
(10)
−
c(eR
y,z ),
βi,v
βj,v

where clsR (k) is moved from Pi,p to Pj,q ,while eRis a communication part of T LR (k)
r,s
R
(nR
∈
/
cls
(k),
nR
R
r
s ∈ clsR (k)), and ey,z is a communication
R
part
of
BL(k)
(ny ∈ clsR (k), nR/ clsR (k)).
Ifz ∈φ(clsR (k)) > 0, WSL can be reduced by this cluster
remapping procedure. Otherwise, WSL may not be reduced.
In this analysis we present the lower bound of φ(clsR (k)) inseveral cases.
At line 5 in fig. 4, the target PE for cluster remapping isselected by computing every incoming and outgoing communication of the cluster selected at line 2 in fig. 4. Thus, we have 2
cases for analyzing the effect on the WSL reduction by cluster
remapping, i.e., (i) comin (clsR (k)) or comout (clsR (k)) is
localized and the WSL path is not changed, and (ii) bothcomin (clsR (k)) and comout (clsR (k)) are not localized (othercommunications are localized).
(i) comin (clsR (k)) or comout (clsR (k)) is localized and the
WSL is not changed:
This case means that u = j or j = v obtained by cluster
11= 0 or βj,v
= 0. Withremapping. Consequently, βu,j1
out loss of generality, suppose that βu,j = 0, while1
comout (clsR (k)) remains unlocalized, i.e., βj,v
̸= 0.

311

From eq. (10), we have∆φ(clsR (k)) =1c(eR )
βu,i r,s
(
)
∑
1
1
+
−
w(nR
l )
αi,p
αj,q
nR
∈cls
(k)
R
) l
(
1
1
R
−
c(ey,z ).
(11)
+
βi,v
βj,v

From eq. (11), there are 4 cases for satisfying
φ(clsR (cls(k)) ≥ 0 depending on magnitude relationships of αi,p to αj,q , and βi,v to βj,v .
(i-I) The case of αi,p ≤ αj,q , βi,v ≤ βj,v :In this case, the target PE to which clsR (k)has faster processing speed and wider communication bandwidth. Let the maximum of processing
speed, communication bandwidth, and data size be
αmax , βmax , cmax , respectively. Let the minimumof processing speed, communication bandwidth, anddata size be αmin , βmin , cmin , respectively. Then wehave
1∆φ(clsR (k)) ≥
cmin
βmax
(
)
∑
1
1
w(nR
+
−
l )
αi,p
αj,q
R
n ∈clsR (k)
(
) l
1
1
+
−
c(eR
y,z )
βi,v
βj,v
1
≥
cmin > 0.
(12)
βmax
Thus, in this case, φ(clsR (k)) always takes the
positive value.
(i-II) The case of αi,p ≤ αj,q , βi,v ≥ βj,v :In this case, we have1
∆φ(clsR (k)) ≥
cmin
βmax
(
)
1
1
+
−
cmax
βmax
βmin
1
cmax
=
(cmin + cmax ) −
βmax
βmin
(13)
At eq. (13), the condition
φ(clsR (k)) ≥ 0 is as follow.

for

cmax
1
(cmin + cmax ) −
≥0
βmax
βmin
βmax
cmin
⇔
≤
+ 1 ≤ 2.
βmin
cmax

satisfying(14)

From eq. (13), the lower bound becomes small if
the heterogeneity (i.e., max to min ratio) in termsof communication bandwidth is also small. If eq.
(13) is satisfied, φ(clsR (k)) takes the positive valueirrespective of processing speed.
(i-III) The case of αi,p ≥ αj,q , βi,v ≤ βj,v :In this case, the target PE has slower processing
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

TABLE II

speed than Pi,p . Then we have

C OMPARISON RESULTS IN TERMS OF THE SCHEDULE LENGTH∆φ(clsR (k))
(
)
∑
c(eR
1
1
r,s )
≥
+
−
w(nR
l )
βu,i
αi,p
αj,q
R
nl ∈clsR (k)
(
)
∑
cmin
1
1
≥
+
−
w(nR
l ).
βmax
αmax
αmin
R
nl ∈clsR (k)(15)
The condition for satisfying φ(clsR (k)) ≥ 0 is asfollow.
(
)
∑
αmax
αmax
cmin ≥
−1
w(nR
l )
βmax
αmin
R
nl ∈clsR (k)
(
)∑
w(nR
αmax
αmax
l )
nR
l ∈clsR (k)
⇔
≥
−1
βmax
αmin
cmin
(16)
In eq. (15), if αmax is much larger than βmax andheterogeneity in terms of processing speed is small,φ(clsR (k)) has possibility of taking the positive
value.
(i-IV) The case of αi,p ≥ αj,q , βi,v ≥ βj,v :In this case, we have∆φ(clsR (k))
(
)
∑
c(eR
1
1
r,s )
≥
+
−
w(nR
l )
βu,i
αi,p
αj,q
R
nl ∈clsR (k)
)
(
1
1
−
c(eR
+
y,z )
βi,v
βj,v
(
)
∑
cmin
1
1
≥
+
−
w(nR
l )
βmax
αmax
αmin
R
nl ∈clsR (k)
(
)
1
1
+
−
cmax .
(17)
βmax
βmin
The condition for satisfying φ(clsR (k)) ≥ 0 is asfollows.
()∑
cmin + cmax
1
1
≥
−
w(nR
l )
βmax
αmin
αmax
R
nl ∈clsR (k)

cmax
+
.
βmin

312

No.

α

β

CCR

R
|Vcls
|

A
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5

5

5

10

10

5

10

10

0.1
1.0
5.0
10.0
0.1
1.0
5.0
10.0
0.1
1.0
5.0
10.0
0.1
1.0
5.0
10.0

156
58
42
16
165
55
32
14
139
48
37
27
188
67
40
29

Schedule Length
B
C

1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000

1.002
1.011
1.031
1.109
1.001
1.076
1.103
1.107
1.001
1.068
1.103
1.198
1.004
1.143
1.170
1.179

1.002
1.008
1.048
1.144
1.044
1.071
1.142
1.281
1.003
1.042
1.009
1.201
1.002
1.107
1.140
1.151

not be estimated.
From results of the theoretical analysis a cluster to be selected
at line 7 in fig. 4 should be the case of (i-I). However, thealgorithm can not always select by (i-I) because WSL after
each cluster remapping may be changed due to the variationof communication time and processing time for each task. Thismeans that a strategy to use (i-I) in every cluster remapping
step has possibility to increase WSL by the change of thepath dominating WSL. Thus, at eq. (7) the algorithm tries tofind the target PE by summing up all communication times
involved by the cluster selected at line 2 in fig. 4 in order tolocalize communication as many as possible.
VI. E XPERIMENTS
We conducted the experiments by a simulation to confirm
advantages of our proposal, i.e., how the cluster remapping
can reduce the schedule length. We compared with the method
proposed in [11] in terms of the following points.
1) Effect on the cluster remapping with compared to thecase of “non remapping”.
2) Effect on the proposed remapping policy and algorithm.
Thus, comparison targets are, (A) the proposed cluster remapping, (B) each cluster is randomly remapped. (C) non
remapping[11].

(18)

From this result, at least heterogeneity in terms
of processing speed and communication bandwidth
should be small in order to satisfy φ(clsR (k)) ≥ 0.
(ii) Nor comin (clsR (k)) and comout (clsR (k)) are localized:
Since the algorithm tries to trace incoming edges andoutgoing edges to find the target PE, the edge whichcorresponding to comin (clsR (k)) or comout (clsR (k)) is
not always localized by the proposed cluster remapping.
This case assumes that some edges which are not partsof LVR (k) are localized. In this case, the new WSL isderived by tracing every edges and tasks after cluster
remapping. This fact means that the path of WSL canbe changed. Thus, the lower bound of φ(clsR (k)) can

A. Experimental Environment
In the simulation, a random DAG is generated. In each
DAG, each task size and each data size are decided randomly.
Also CCR (Communication to Computation Ratio)[13], [14]is changed from 0.1 to 10. The max to min ratio in termsof data size and task size is set to 100. Also we decided
the Parallelism Factor (PF) is defined as ρ, taking values of
0.5, 1.0, and√ 2.0 [15]. By using PF, the depth of the DAG is|V |defined as ρ 0 . Since we assume a heterogeneous distributed
system by multicore computers, each PE’s performance andnetwork bandwidth are varied by parameters. The simulation
environment was developed by JRE1.6.0 0, the operating
system is Windows XP SP3, the CPU architecture is Intel
Core 2 Duo 2.66GHz, and the memory size is 2.0GB.
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

313

TABLE IIIC OMPARISON RESULTS IN TERMS OF THE SCHEDULE LENGTH AND SELECTED PE TYPES
No.

α

β

CCR

R
|Vcls
|

Schedule Length Raio to (A)A
B
C

Ratio of of (i-I) (%)
A
B
C

Ratio of (i-IV) (%)
A
B
C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5

5

5

10

10

5

10

10

0.1
1.0
5.0
10.0
0.1
1.0
5.0
10.0
0.1
1.0
5.0
10.0
0.1
1.0
5.0
10.0

143
67
41
14
166
73
38
18
145
55
39
13
173
66
40
26

1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000
1.000

24.0
27.9
29.2
33.3
27.0
34.1
36.4
57.1
22.9
22.4
43.5
33.3
28.6
34.2
27.3
37.5

6.7
4.7
8.3
0.0
4.1
7.3
9.1
11.7
8.6
10.2
13.0
0.0
7.1
10.5
4.5
0.0

1.003
1.010
1.044
1.072
1.002
1.013
1.041
1.102
1.000
1.018
1.039
1.121
1.006
1.149
1.166
1.133

B. Effect on Cluster Remapping
One comparison is done by executing 100 random DAGs
and averaging the schedule length for each approach (A)(C). Since (C) does not require cluster remapping, at firstthe simulation output the schedule length by (C). Then each
remapping procedures is performed in (A) and (B), respectively. Then both approaches output each schedule length forthe same DAG as (C). Table II shows comparison results by
the experiment. In the table, α and β are ratios of maximum
to minimum processing speed and maximum to minimum
communication bandwidth, respectively. In the 6th column,
values mean the schedule length ratio when the schedule
length obtained by (A) is set to 1. Thus, a value over 1
is worse than (A). In every cases, it is observed that the
proposed method (A) outperforms other approaches. If β issmall such as No. 1-5 and No. 9-12, we can not observe
noticeable characteristics among three approaches, except thatthe schedule length obtained by (A) is the smallest. On theother hand, β is large such as No. 5-8, the schedule length
obtained by (C) is considerably large with increasing CCR.
From this result, it is conceivable that data localization isnecessary irrespective of cluster remapping methods if eachdata size is large. As for No. 13-16, the schedule length
obtained by (B) is the largest with increasing CCR. From thisresult, the cluster remapping method has large effect on theschedule length if the heterogeneity of the network is large.
From these results, it is concluded that the proposed cluster
remapping method has good effect on the schedule length byeffectively localizing data communications among PEs.
C. Relationship between PE Selection Policies and the Schedule Length
According to the results obtained in sec. V, selecting thetarget PE having faster processing speed and larger communication bandwidth (type of (i-I)) in sec. V than the original PE
can lead to the reduction of WSL after one cluster remapping
procedure has finished. Nonetheless, the proposed algorithm
tries to find the target PE by summing up all communication
times involved by the moving target cluster rather than finding
a cluster of (i-I) in sec. V. This is because not always a cluster

1.011
1.013
1.089
1.182
1.009
1.023
1.099
1.183
1.009
1.026
1.088
1.282
1.087
1.181
1.159
1.198

40.0
44.2
58.3
50.0
39.2
53.7
72.7
71.4
47.1
53.1
82.6
50.0
48.6
50.0
54.5
50.0

9.3
11.6
8.3
0.0
5.4
4.9
4.5
0.0
7.1
6.1
8.7
0.0
8.6
7.9
4.5
0.0

16.0
14.0
16.7
33.3
14.9
17.1
22.7
14.3
15.2
16.3
8.7
16.7
15.7
15.8
9.1
12.5

46.7
51.2
45.8
83.3
39.2
39.0
45.5
42.9
41.4
22.4
21.7
66.7
34.3
39.5
45.5
37.5

of type (i-I) can be found and WSL path may be changed by
a cluster remapping procedure, thereby
In this experiment, we compared the schedule length anddistribution of the selected PE type ((i-I) to (ii) at sec. V)in (A) proposed algorithm, (B) trying to find a cluster oftype (i-I), (C) trying to find a cluster of type (i-IV). This
comparison is conducted by averaging the schedule length of
DAGs having 1000 tasks by 100 tries for all three approaches.
In the method (B), if a cluster of type (i-I) is not found, themethod selects a PE randomly from the set of PEs by which
at least one communication involved by a cluster selected atline 2 in fig. 4 is localized. In the method (C), if a clusterof type (i-IV) is not found, the target PE is selected as thesame policy as (B). Table. III shows the comparison results.
“Ratio of (i-I)” means the percentile of the number of that a
PE of type (i-I) is selected as the target PE to the numberof all cluster remapping, while “Ratio of (i-IV)” means thepercentile of the number of that a PE of type (i-IV) is selected
as the target PE to the number of all cluster remapping. From
this table, it is observed that in every cases (No. 1 - 16), theproposed algorithm has the smallest schedule length, while(B) has the largest ratios of (i-I) and (C) has the largest ratiosof (i-IV) in every cases. From this result, it can be conceived
that selecting a PE of type (i-IV) has bad effects on both
WSL and the schedule length. Furthermore, Even if a PEof type (i-I) is selected as the moving target, the schedule
length can be made larger by the facts that WSL path may
be changed. This is because an communication time dominating comin (clsR (i)) or comout (clsR (i)) is made smaller
by a cluster remapping, while other edges may dominates
comin (clsR (i)) or comout (clsR (i)).
From this result, it is concluded that the PE selection criteria
by the proposed cluster remapping have good effect on theschedule length.
VII. C ONCLUSION AND F UTURE W ORKS
In this paper, we presented a cluster remapping method ina multicore distributed system for processor utilization. The
method tries to move clusters for data localization with taking
into account both data dependencies which can have goodeffect on the schedule length. This procedure is performed by
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

calculate the difference between time taken to execute every
task in the cluster in the new PE and the time taken to execution and data communication in the previously decided PE
decided by the method of [11]. From preliminary experiments,
the proposed method was proved to have good effect on theschedule length.
As a future work, we develop more efficient method which
does not use remapping in multicore distributed systems forprocessor utilization.

314

Hidehiro Kanemitsu received the B.S. degree fromWaseda University, Japan in Science, and the M.S.
and D.S. degrees from Waseda University, Japan in
Global Information and Telecommunication Studies(GITS). His research interests are in areas of paralleland distributed computing, grid, peer-to-peer computing, and web service technology. He is currently
an assistant professor at Media Network Center,
Waseda University, Japan.

R EFERENCES[1] I. Foster, “The Grid: A new infrastructure for 21st century science,”
Physics Today, Vol.55(2), pp. 42–47, 2002.
[2] G. DeCandia et al, “Dynamo: amazon’s highly available key-value store,”
Proc. of ACM SIGOPS symposium on Operating systems principles(SOSP’12), pp. 205 – 220, 2007.
[3] S. Di and C.L. Wang, “Dynamic Optimization of Multiattribute Resource
Allocation in Self-Organizing Clouds,” IEEE Trans. on Parallel andDistributed Systems, Vol. 24, No. 3, pp. 464-478, 2013.
[4] M. Xu, L. Cui, H. Wang, and Y Bi, “A Multiple QoS Constrained
Scheduling Strategy of Multiple Workflows for Cloud Computing,” Proc.
of 2009 IEEE International Symposium on Parallel and Distributed
Processing with Applications, pp. 629–634, 2009.
[5] H. Mohammadi Fard, R. Prodan, J. J. D. Barrionuevo, and T. Fahringer,“A Multi-Objective Approach for Workflow Scheduling in Heterogeneous
Environments,” Proc. of 2012 12th IEEE/ACM International Symposium
on Cluster, Cloud and Grid Computing, pp. 300–309, 2012.
[6] J.S. Kim et al., Using Content-Addressable Networks for Load Balancing in Desktop Grids, Proc. of 16th ACM International Symposium on
High Performance Distributed Computing (HPDC 07), pp. 189- 198,
2007.
[7] A. Leite, H. Mendes, L. Weigang, A. de Melo, and A. Boukerche,“An Architecture for P2P Bag-of-Tasks Execution with Multiple Task
Allocation Policies in Desktop Grids,
Proc. of IEEE International
Conference on Cluster Computing, pp. 1-11, 2011.
[8] A. Gerasoulis and T. Yang, “A Comparison of Clustering Heuristics
for Scheduling Directed Acyclic Graphs on Multiprocessors,” Journalof Parallel and Distributed Computing, Vol. 16, pp. 276-291, 1992.
[9] T. Yang and A. Gerasoulis, “DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors,” IEEE Trans. on Parallel and Distributed
Systems,” Vol. 5, No. 9 pp. 951-967, 1994.
[10] J. C. Liou, M. A. Palis, “An Efficient Task Clustering Heuristic for
Scheduling DAGs on Multiprocessors,” Proc. of the 8th Symposium on
Parallel and Distributed Processing,October, 1996.
[11] Hidehiro Kanemitsu, Gilhyon Lee, Hidenori Nakazato, Takashige
Hoshiai, and Yoshiyori Urano, “A Processor Mapping Strategy for Processor Utilization in a Heterogeneous Distributed System,” Journal ofComputing, Vol. 3, Issue 11, pp. 1 – 8, November 2011.
[12] Hidehiro Kanemitsu, Gilhyon Lee, Hidenori Nakazato, Takashige
Hoshiai, and Yoshiyori Urano, “On the Effect of Applying the Task
Clustering for Identical Processor Utilization to Heterogeneous Systems,”
Grid Computing - Technology and Applications, Widespread Coverage
and New Horizons, InTech(ISBN: 978-953-51-0604-3), pp. 29 - 46,
March, 2012.
[13] O. Sinnen and L. A. Sousa, “Communication Contention in Task
Scheduling,” IEEE Trans. on Parallel and Distributed Systems, Vol. 16,
No. 6., pp. 503-515, 2005.
[14] O. Sinnen, “Task Scheduling for Parallel Systems,” Wiley, 2007.
[15] H. Topcuoglu, S. Hariri, M. Y. Wu, “Performance-Effective and LowComplexity Task Scheduling for Heterogeneous Computing,” IEEE Trans.
on Parallel and Distributed Systems, Vol. 13, No. 3 pp. 260-274, 2002.

Masaki Hanada received the B.E. degree in Resources Engineering from Waseda University in
1996, and the M.S. and D.S. degrees in Global
Information and Telecommunication Studies fromWaseda University in 2003 and 2007, respectively.
He has been an assistant professor at the Department of Information Systems, Tokyo University ofInformation Sciences. His research interests include
QoS/traffic control and resource management incommunication networks.

Takashige Hoshiai has been a Professor at Sojo
University since 2012. He was a senior researchscientist supervisor at NTT Network Service Systems Laboratories from 1986 to 2012. He received
his Ph.D. degree in Communications and Systems
from The University of Electro-Communications,Japan. His research areas are distributed object technologies, real-time systems, agent systems and P2P.
Since he proposed a new business model called
Brokerless Model in 1998, especially, he hasstudied SIONet architecture that is a solution of P2P
platforms.

Hidenori Nakazato received his B. Engineering
degree in Electronics and Telecommunications fromWaseda University in 1982, and his MS and Ph.D.
degrees in Computer Science from University of
Illinois in 1989 and 1993, respectively. He wase with
Oki Electric from 1982 to 2000 where he developed
equipment for public telephony switches, distributed
environment for telecommunications systems, andcommunications quality control mechanisms. He has
been a Professor at Graduate School of Global Information and Telecommunications Studies, Waseda
University since 2000. His research interests include performance issues in
distributed systems and networks, cooperation mechanisms of distributed
programs, distributed real-time systems, and network QoS control.

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013315

A Stereo-Vision Approach for a Natural 3D
Hand Interaction with an AR Object
Seonho Lee*, Junchul Chun**Department of Computer Science, Kyonggi University, San 94-6 Yiui-Dong, Yeongtong-Gu, Suwon, S. Korea
sunho36@naver.com, jcchun@kgu.ac.kr

Abstract—Providing natural hand interaction between a virtual
object and a user on Augmented Reality is a major issue tomanipulate a rendered object in a convenient way. Conventional
2D image-based recognition and interaction technique in AR has
a limitation to perform a natural interaction between the user andthe virtual object. In this paper, we present a stereo-vision based
natural 3D hand interaction with the augmented object. In the
proposed 3D hand interaction approach, 3D hand location andfinger direction can be easily obtained by using stereo-vision
technique while user hand is approaching to the virtual object.
Two types of hand manipulation for the augmented object such as
the hand pointing and hand pinching are defined. The collision
detection between user hand and the virtual object is determinedby using a simple ray casting emitted from the user’s finger-point
against the virtual object in the case of hand pointing. In the handpinching, the collision is occurred when the thumb and the index
finger are approaching to the object and the degree of angle
between two fingers becomes a predetermined value. From theexperiments, the proposed 3D hand interaction method cancontrol the virtual object in a natural way rather than using avision-based 2D hand interaction since the stereo-vision technique
can obtain the depth information from the AR environments.
Keyword— Stereo-vision, Haptic interface, Augmented Reality,
Collision detection, Hand detection

I. INTRODUCTION

R

ecently one of the main issues in Augmented Reality (AR)is how to interact the overlaid virtual objects in aconvenient fashion by users. Newly introduced tracking andinteraction methods in AR allow users to work with andexamine the real physical world, while controlling augmented
objects in the system more feasible fashion. In general AR can
be classified into two categories such as marker-based AR andmarker-less AR. In marker-based AR a specific marker is used
Manuscript received July 29, 2013. This work was supported by Basic
Science Research program through the National Research Foundation of
Korea(NRF) funded by the Ministry of Education, Science and Technology(No.
2012006018).
Seonho Lee is a graduate student in the department of computer science at
Kyonggi University, South Korea (Tel: +82-31-249-8947; e-mail:sunho36@naver.com ).
Junchul Chun is currently a professor in the department of computer scienceand a principal investigator of GIP(Graphics and Image Processing Lab) at
Kyonggi University, South Korea. (Tel: +82-31-249-9668; Fax:
+82-31-249-8949; e-mail: jcchun@kgu.ac.kr).

for overlaying an object in the scene. Meanwhile, marker-less
AR does not require the forethought of adding markers to ascene in order to render a virtual object. It uses a detectedfeature from the scene as a marker instead of using apredetermined specific marker. Regardless of their types of AR
system, most of AR systems need various interactions between
users and augmented object in many AR applications. Therefore,
the major issue in AR is how to interact with a virtual model indynamic or convenient way. Conventional vision-based
interaction techniques in AR are based on 2D image analysis
and recognition methods and have a limitation to obtain three
dimensional information of the virtual object and user who
participates in the interaction.
In this paper, we present a vision-based 3D hand interaction
with a virtual object in AR system with a natural way. To
develop the 3D hand interaction we adopt stereo-vision
technique which can expand the dimension of the AR
interaction from 2D to 3D and provide more intuitive
interactions between the virtual object and users. In the
proposed 3D hand interaction, a user can directly contact with avirtual object by simply detecting the collision between user’s
hand and the virtual object while the interaction is being
processed.
The rest of the paper includes related work, the description of
the proposed vision-based 3D interaction method, theexperimental results and the conclusion and future works.
II. RELATED WORKS
Both marker-based and marker-less AR systems require
some indication of where exactly the virtual objects should be
augmented. This has been conventionally accomplished by AR
markers such as ARTag[1] or ARToolkit[2] in marker-based
AR. In mobile AR system ARToolkitPlus[3] is well-adopted
because it provides an efficient management of the memory and
fixed point unit computing by optimizing the libraries ofARToolkit.
In order to register a virtual object to a detected marker on thescene, we can use the vision-based tracking technologies such asfeature-based and model based approach. The main idea
underlying feature-based methods is to find a correspondence
between 2D image features and their 3D world coordinate
system. The camera pose can be found from projecting the 3D
coordinates of the features into the 2D image coordinate alongwith minimizing the difference between their corresponding 2Dfeatures. The ARToolKit library utilizes the four corners of a

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013square marker to the positions of the 3D object rendered.
Tracking algorithms for non-square visual markers such as ring
shaped and circular shaped markers were also used[4].
Model-based methods tracking explicitly use a model offeatures of tracked objects such as 2D template object or CAD
model.
Once a virtual object is registered on the marker, the users
usually want to manipulate or interact with the augmented
object. The most of introduced interaction techniques for AR
applications allow end users to contact with virtual objects in an
intuitive way. Tangible interface and tangible interaction
metaphor have become one of the most frequently used AR
interaction methods[5]. Tangible AR interactions leads tocombining real object input with human gesture interaction andhand gesture interaction methods have been widely studied fromthe perspective of computer vision and AR[6].
In vision-based interaction, hand and fingertip tracking alongwith hand gesture recognition method are widely used toprovide an easy way to interact with virtual object in AR. The
approaches to use bare stretched human hand as a distinctive
pattern instead of a marker for marker-less AR system are
introduced[7]-[9]. In their work, 6-DOF camera pose wasestimated by tracking fingertips and virtual objects areaugmented on hand coordinate system. However, the limitationof these approaches is the inspection of the object is hinderedwhen the fingertips are occluded by themselves when the hand isflipping or moving. Chun and Lee[10][11] presents a real-time
vision-based approach to manipulate the overlaid virtual objects
dynamically in a marker-less AR system using bare hand with asingle camera. In their approach, the left bare hand is considered
as a virtual marker in the marker-less AR and the right hand isused as a hand mouse. Thus the manipulation of the virtual
objects on the marker-less AR system can be dynamicallyobtained and a vision-based hand control interface which
exploits the fingertip tracking for the movement of the objects
and pattern matching for the hand command initiation isdeveloped. However, all of these interactions are based on
vision-based 2D interaction with the augmented object in AR.
Simple 3D interaction in AR[15] was presented however in thiswork we provide various scenarios of 3D interaction with morefeasible fashion in actual AR applications.

III. PROPOSED APPROACH
A. Manipulation of a Virtual Object in AR
The interaction between a human and an augmented object in
AR is by manipulating the virtual object by actual human hand
illustrated in Fig 1. In this work, we introduce the two types ofhand interaction by hand pointing and hand pinching.

316

Fig. 1 Manipulating a virtual object in AR by hand pointing and pinchinginteraction

Fig 2 shows the overall steps of the proposed 3D handinteraction method, which consists of three major phase. In thefirst phase, the human hand is detected from input video image
using the skin color model and image segmentation. In thesecond phase, the 3D locations of fingertip, the center of thepalm and the center of the marker are evaluated using the
disparity map of the stereo-vision. In the final stage, the user caninteract with an augmented object by detecting collision
between the human hand and the object.

Fig. 2 Steps for stereo-vision based 3D hand interaction in AR

B. Hand Detection Method
For hand region detection like in our previous works, we use
YCb Cr skin color model which is proven to detect skin region
effectively to segmenting hand region[10][11]. Skin color
model has been widely used for hand and face detection because
the use of color information can simplify the task of hand
localization in complex environments. Mostly the primary
components of RGB are used for skin segmentation. Other
models such as HSI , normalized RGB , and YCb Cr etc. areused for the segmentation of skin-like region[12]. Even though,color information is an efficient tool for identifying skin region
if the skin tone color can be properly adapted for different
lighting conditions, it has some limitation since the skin color
model is sensitive to the light source varies significantly orcomplex background.
As a skin color model we adopt the YCb Cr since it isperceptually uniform and it is similar to the TSL space in termsof the separation of luminance and chrominance. It is known
that the chrominance components of the skin color are
independent of the luminance component. Thus, the normalized

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

RGB color model is transformed to YCb Cr model by using
following equation (1).

éY ùêC ú =
ê búêëCr úû

0.587
0.114 ùé 0.299
ê- 0.16874 - 0.3313
0.500 úúê
êë 0.500- 0.4187 - 0.0813úûéRù é 0 ùêG ú + ê128ú (1)ê ú ê úêë B úû êë128úû

By disregarding the luminance component (Y ) , robustnessof skin detection can be obtained in the case of variations
lighting conditions. Thus, in this work we only utilize Cb , Crvalues from samples of skin color pixels. For the hand region
detection, the threshold values of each chrominancecomponents are derived from the set of hand images. The
average values of Cb and Cr for hand region obtained throughthe experiments are as follow(128 £ Cb £ 170) I (73 £ Cr £ 158)

(2)

317

C. Stereo Vision TechniqueIn this work, we use stereo camera to get the 3D coordinatesof the hand and the marker itself for detecting any possible
collision between the user and the virtual object while
manipulating the augmented object. Using two different views
from the same scene then we can estimate the 3D coordinates ofany point in the scene by finding the position of that point in theleft image and in the right image and then apply sometrigonometry. To get the accurate 3D coordinates of the points
such as fingertip or the center of the marker, we calibrate thestereo camera. The calibration can make that the match of apoint in the left image will appear in the exact same line on theright image and it can also fix the possible distortion caused by
the lenses.
An offline camera calibration is performed by use of a simple
planar grid pattern of known size in the field of view. Fig 4
illustrates two grid patterns for left and right un-calibrated
images and their rectified images after calibrating those images.
We can see each correspondent point of the left and right images
are same epipolar line after calibrating the stereo images.

With carefully selected threshold range values, a pixel value
is assigned to the hand region if its value meets the range. Fig 2shows the hand region with Cb , Cr values from the RGB based
input hand image. In order to enhance the segmented handregion by removing noise a morphological operator are applied
to the segmentation result. The center of the hand can beextracted from the medial axis of the segmented hand region I (P ) .
The distance transform which is used to compute the medial axisof the segmented hand[13] is used to obtain the single connected
hand. The distance transform (DT) is the transformation thatgenerates a map D whose value in each pixel p of the segmented
region O is the smallest distance from this pixel to thebackground O c . The distance map D can be defined as follow
Fig 4. The rectified images from two images after calibration{}

D( p ) = min d ( p, q ) q Î O c = min{d ( p, q ) I (q ) = 0}

(3)

Using the calibrated images, we can calculate the dense
disparity map which provides the distance between the camera
and the object. Fig 5 shows the geometry of the stereo visionand the relationship between disparity and camera distance.

Fig 3. Steps for hand segmentation: (a) Cb Cr converted input image andsegmentation of hand(left) (b) distance transform of the hand segmentationand the center of the hand(right) (c) Finger tip detection (bottom)

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013318

direction of the finger when we use two feature points (P0 , P1 ) of
the hand in the hand pointing.

Fig 5. The geometry of stereo vision (top) and the relationship between
disparity and camera distance (bottom)

Once the disparity (d ) between x l and x r is calculated, thedepth value (z ) can be obtained by using T and the focal length
f as follows:
T
(4)
z= f
d
The calculated (z ) value will be used for the (z ) coordinate
value of the objects such as the center of the hand or the marker
in the marker-based AR system. Fig 6 shows a dense disparity
map from two images taken from a left and right camera.

Fig 6. Dense disparity map from two input images

D. Collision Detection Using Ray Casting
It is natural that the collision between the human hand and theaugmented object can be occurred during manipulating thevirtual 3D object. In AR, however, the collision is occurred
between a virtual and a real object thus the collision detection
method may be different comparing with the ways in the realworld. In this work, since we already have 3D information of
the hand and the marker for the AR using stereo-vision
technique, the 3D direction of the finger tip can be obtainable
like Lee’s work[14]. When both the calculated finger directionis aligned with the central position of the marker or the positionsof augmented object and the hand is approaching to the object inthe some distances, we can assume the collision between two
objects.
Since the manipulation of an object can be done by two typesof hand interaction i.e. pointing and pinching, the collision
detection between the hand and a virtual object is also definedby two different approaches, respectively. Fig 7 illustrates theFig 7. The direction of the finger pointing by simple ray casting

The direction of the finger can be easily calculated as a linear
parametric function f (t ) between the centre of thehand P0 (x1 , y1 , z1 ) and the location of the fingertip P1 ( x2 , y 2 , z 2 )as follows:f x (t ) = x1 + ( x2 - x1 )t
f y (t ) = y1 + ( y 2 - y1 )t(5)

f z (t ) = z1 + ( z 2 - z1 )t

The linear function f (t ) can be used for evaluating where
the user is pointing at and the parameter t can control themagnitude of the function. For the collision detection, we canuse finger ray casting which is known to be a fast for pointing atand selecting a distant object. The collision between the hand
and the virtual object is detected when the ray touch the virtual
object. In this work, we assume that two objects are collided in acertain range of distance (D) for example the parameter t off (t ) is less than equal to 2 or the distance between thelocations of the hand and marker is less than a predefined
distance (e ) . Three different reactions from the virtual object:pushing, pulling and changing the color of the virtual object are
obtained when the collision between the user and the virtual
object is detected.
Meanwhile, when the pinching is used the collision between
the object and finger is determined by the angle between the
thumb and the index finger as illustrated in Fig 8.

Fig 8. The angle of the thumb and a finger in pinching interaction

The

degree

of

angle

r
v = ( P0 , P2 ) becomes as follow:

q betweenru = ( P0 , P1) and

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

r r
u ·v
cosq = r r
u v

(6)

Fig 9 (a) illustrates the locations of the thumb and the index
fingers during pinching interaction in a sequences of image
frames between the user and a virtual object when thez-coordinates of the fingers and the augmented object are same
locations. The collisions between the fingers and the object aredetected in the range of the marker. In this work, it is assumed
that the collision between the finger and the virtual object isoccurred when the thumb and the index finger are approachingto object and the degree of angle between two fingers is locatedin the range of 0o 0 to 42o during pinching the virtual 3D
object as illustrated in Fig 9 (b).

319

IV. EXPERIMENTAL RESULTS
The proposed 3D hand interaction supports four different
manipulations of the augmented object in AR. In thisexperiment, we use ARTookit to register the virtual object on areal scene. One of the difficulties in developing AR applications
is the tracking the users viewpoint however ARToolkit cansolve this problem using vision algorithm. In the experiment we
use two Logitech Quick Cameras to obtain stereo images.
Fig 10 illustrates the sequence of hand images and detected
3D locations of the centre of hand, fingertips and finger ray
using stereo-vision technique and our proposed method.

Fig 10. 3D locations of the center of hand, fingertip and its ray.

(a) Locations of the thumb and the index finger in a sequence of image frames
during pinching interaction

Based on the hand pointing and the hand pinchinginteraction with a virtual object in AR, we can produce various
3D interaction results. In the hand pointing interaction, 4different reactions are generated when the hand is collided withthe augmented object as illustrated in Fig 11(a). The firstinteraction is to change the colour feature of the virtual object
when a user touches the augmented object. The second
interaction is changing the shape of the object. The thirdinteraction is pushing the augmented object from the currently
registered position on the marker. While applying thisinteraction, the rendered object is translated from the current
location of the marker to the opposite direction and got back to
its original position when user’s hand is moved away from thecurrent marker. Final interaction is pulling the augmented object
and locating the object on the hand. Like pushing, the object canbe relocated into original position when the human hand isdisappeared from the scene.
Meanwhile, in the hand pinching interaction, the color, shapeand size of the virtual object is instantly changed when theobject is touched by pinching as illustrated in Fig 11(b). The
sequence of the image in Fig 11(c) is the size variation of thevirtual 3D object when a user manipulates the object during
pinching interaction.

(b) Angle between the thumb and the index finger during pinching interaction
Fig 9. Collision detection in pinching interaction.

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013320

disadvantage of 2D image and support more feasible
manipulation of the virtual object in AR. In the proposed 3D
hand interaction, the 3D information of the hand and the virtual
object was utilized to detect the 3D collision between twomodels when the hand was approaching to the virtual object.
The user interaction can change the features of the object suchas color and shape. In addition, the user can change thegeometric locations of the object by pushing or pulling theobject from the current 3D locations of the object. This simple
collision detection can make the 3D hand interaction come true
in AR applications.
As for the future work, we will study to combine the proposed
stereo-vision technique with actual haptic device formanipulating a virtual object in AR.
(a) The hand pointing interaction

REFERENCES[1](b) Three different reaction with the hand pinching interaction(c) The size variation of the object by pinching interaction
Fig 10. Manipulation of virtual object using the hand pointing and pinchinginteraction

CONCLUSION
In this paper we present a stereo vision-based natural 3D
hand interaction with an augmented object in Augmented
Reality System. In traditional AR interaction using 2D input
image, it have been limitations to provide a natural interaction
between the user and the augmented object because of the lackof Z information of the user and the virtual object. The
proposed stereo-vision technique can overcome thisM Fiala. ARTag, a fiducial marker system using digital techniques, In
CVPR 05, (2005), Vol 2., pp. 590-596.
[2] H. Kato and M. Billinghurst, Marker tracking and HMD calibration for avideo-based augmented reality conferencing system, In IWAR ` 99(1999),
pp. 85-94.
[3] D. Wagner and D. Schmalstieg ARToolKitPlus for Pose Tracking on
Mobile Devices, In Procedings of 12th Computer Vision WinterWorkshop’07 (2007), pp. 139-146.
[4] Cho, Y; Lee, J. & and Neumann, U. A multi-ring fiducial system and an
intensity-invariant detection method for scalable augment reality, In
IWAR `98, (1998). pp. 147-156..
[5] H. Kato, M. Billinghurst, I. Poupyrev, K. Imamoto and K. Tachibana,
Virtual object manipulation on a table-top AR environments, In ISAR
`00, (2000), pp. 111-119.
[6] Lee, W. & Park, J. Augmented foam: A tangible augmented reality for
product design. In ISMAR `05, (2005), pp. 106-109.
[7] T. Lee and T. Hollerer, Hand AR: Markerless Inspection of Augmented
Reality Objects Using Fingertip Tracking, In Proc. IEEE ISWC
`07,(2007), pp. 83-90.
[8] T. Lee and T. Hollerer, “Initializing Markerless Tracking Using a Simple
Hand Gesture,” In Proc. ACM/IEEE ISMAR `07, (2007), pp. 1-2.
[9] T. Lee and T. Hollerer, “Hybrid Feature Tracking and User Interaction forMarkerless Augment Reality,” In IEEE Int’l Conference on Virtual
Reality`08 (2008), pp. 145-152.
[10] Lee, BS and Chun, JC, Interactive manipulation of augmented objects inmarker-less AR using vision-based hand mouse, In Int’l Conference on
Information Technology(ITNG), (2010), pp. 398-403.
[11] Chun, J.C and Lee, B.S, Dynamic Manipulation of a Virtual Object inMarker-less AR system Based on Both Human Hands, Transactions on
Internet and Information Systems, (2010), Vol. 4, No.4, pp. 618-632.
[12] K. Min and J. Chun, A nonparametric skin color model for face detection
from color images, PDCAT `04, pp. 115-119 , 2004[13] G. Borgefors, Distance transformations in digital images, Computer
Vision, Graphics and Image Processing,(1986), Vol. 34, pp. 344-371.
[14] M. Lee, R. Green, and M. Billinghurst, 3D Natural hand interaction for
AR application, Image and Vision Computing New Zealand 2008,(2008),
pp.1-6.
[15] JC Chun, SH Lee, A Vision-based 3D Hand Interaction for marker-based
AR, International Journal of Multimedia and Ubiquitous Eng., Vol. 7, No.
3, (2012), pp. 51-57.

Seonho Lee is currently a graduate student in thedepartment of computer science at Kyonggi University,
South Korea. He received BS degree from Kyonggi
University majoring computer science in 2012. His
major research interests are augmented reality andhaptic interaction in AR

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

321

Junchul Chun is currently a professor in thedepartment of computer science and a principal
investigator of GIP(Graphics and Image ProcessingLab) at Kyonggi University, South Korea. He has
been served as a chief research director at Contents
Convergence Software Research Center supported by
Geyonggi Regional Government in South Korea. He
received BS from Chung-Ang University majoring
computer science. He also received Ph.D and MS
degrees of computer science and engineering fromthe University of Connecticut, U.S. respectively. His major research areas are
vision-based interaction, augmented reality and computer graphics.

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

322

The Optimum Ring Ratio of 16-APSK in LTE
Uplink over Nonlinear System
Pornpimon Chayratsami*, Sorapong Thuaykaew***Department of Engineering Education, Faculty of Industrial Education,
King Mongkut Institute of Technology Ladkrabang, Bangkok 10520, Thailand**Celestica Inc., Leamchabang, Sriracha, Chon Buri, 20230, Thailand
kcpornpi@gmail.com, siamcreative@gmail.com

Abstract— Single Carrier Frequency Division Multiple Access(SC-FDMA) has been selected for use in the Long Term Evolution(LTE) uplink due to its lower Peak-to-Average Power Ratio(PAPR) relative to OFDMA. The resultant lower PAPR results in
fewer excursions into the amplifier’s nonlinear region, where
signal distortion can occur and results in degraded bit error rate
(BER). The SC-FDMA scheme normally applies 16-ary
Quadrature Amplitude Modulation (16-QAM), but amplitude
phase shift keying (APSK) modulation has a lower PAPR thandoes 16-QAM, resulting in improved BER. This paper investigatesthe constellation ring ratio of the 16-APSK modulation scheme
and its effects on BER through its effects on the PAPR.
Simulation results are used to conclude that a ring ratio that
ranges from 2.5 to 3.5 delivers the best results and provides BER
and PAPR improvement.
Keyword—16-APSK, SC-FDMA, LTE, Nonlinear system,
PAPR

I. INTRODUCTION

T

HE 3GPP Long Term Evolution or LTE is a standard thathas been developed by the 3rd Generation Partnership
Project (3GPP), to become a truly global mobile standard andto apply to high-speed wireless data transmission for mobile
phone and data terminal [1], [2]. It is the next step in
progression from GSM / EDGE and UMTS / HSPA
technologies with higher capacity and faster speed.
In order to reduce the interference signals and to improve thechannel capacity of the LTE system, orthogonal frequency
division multiple access (OFDMA) and single carrier
frequency multiple access (SC-FDMA) are employed for the
downlink and uplink, respectively. The SC-FDMA is themultiplexing technique for the LTE uplink because its PAPR islowers than that of other transmission techniques, especially,
OFDMA [1], [3], [4].
The high PAPR is a principal weakness of OFDM. It bringson the signal distortion in the nonlinear region of high power
amplifier (HPA) [3]. The closer the HPA is operated to thesaturation region, the more frequent are excursions into theManuscript received July 31, 2013.
Pornpimon Chayratsami is with King Mongkut Institute of Technology
Ladkrabang, Ladkrabang, Bangkok, 10520, Thailand (corresponding author
phone: 66-8-5119-0510; fax: 66-2-738-7055; e-mail: kcpornpi@gmail.com).
Sorapong Thuaykaew was with Celestica Inc., Leamchabang, Sriracha,
Chon Buri, 20230, Thailand. (e-mail: siamcreative@gmail.com).

nonlinear region and the more pronounced is the signal
distortion. The signal distortion induces the degradation of bit
error rate (BER). Therefore, it is desirable to have low PAPR to
improve the BER performance.
To reduce the PAPR of OFDM, there are mainly two
categories, which are signal scrambling techniques and signal
distortion techniques [5]. The practical solutions of the signal
scrambling techniques include block coding, Selective Level
Mapping (SLM), and Partial Transmit Sequences (PTS). The
signal distortion techniques include clipping, peak windowing,peak cancellation, peak power suppression, weighted
multicarrier transmission, companding, etc.
Previously, there have been many researches on the PAPR
reduction techniques. For examples, the signal scrambling
techniques of the Partial Transmit Sequences and the block
coding are proposed in [6] and [11]. The signal distortion
techniques of clipping, suppression, peak windowing, peakcancellation, and companding are proposed in [7], [8], [9], [10],and [12], respectively. However, the disadvantage of all thesetechniques is the complexity increase of the system.
Other than the PAPR reduction techniques stated above, J.
Gazda, D. Dupak and D. Kocur in [4] proposed to apply the
M-ary APSK modulation to reduce the PAPR in the LTE uplink.
They show that 16-APSK outperforms the standardized
16-QAM, which is generally used in the LTE uplink. The BER
performance of the 16-APSK system improves for two reasons,the low PAPR of the APSK modulation causes fewer
excursions into the nonlinear region and the 16-APSK signal ismore robust to the distortions caused by the amplifier
nonlinearities than is 16-QAM. Also, W. Sung, S. Kang, P.
Kim and D. Chang in [13] give the preliminary analysis on the
PAPR of the 16-APSK modulation in the digital video
broadcasting for satellites (DVB-S2). They show that the PAPR
of the 16-APSK depends on a ratio of the radius of each ring.
However, according to the authors’ knowledge, the effects ofthe constellation ring ratio of the 16-APSK (4+12 APSK)
modulation scheme are not yet evaluated in the LTE uplinksystem. Therefore, this paper will present the investigation on
the constellation ring ratio of the 16-APSK modulation used in
the LTE uplink system with the nonlinear distortion due to a
HPA. The optimal value of the ring ratio is also proposed.

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

323

1.34
1.32
R2/R1
1.3
1.28

PAPR

1.26
1.24
1.22
1.2
1.18
1.16
1

The paper is organized as follows. First, the effects of theconstellation ring ratio of the 16-APSK modulation, on both the
PAPR and the BER, are presented in Section II. Section III
shows the description of the system model adopted for the
analysis and the simulation. Then, the simulation results areshown in section IV. Finally, section V provides conclusions.

4

5
6
R2/R1 ratio

7

8

9

10

0.18

0.16
0.15
BER

Amplitude phase shift keying (APSK) is a digital modulation
scheme that conveys data by changing or modulating both theamplitude and the phase. It is a combination of Amplitude shift
keying (ASK) and Phase shift keying (PSK) applied to more
effectively populate the signal space. Its constellation iscomposed of concentric rings, each with uniformly spaced PSK
points [14]. Fig. 1 shows an example of 16-APSK constellation
which has 2 concentric rings, with 4 PSK points in the inner and
12 PSK points in the outer. The effects of its constellation ringratio on PAPR and BER could be analyzed as following.
A. The Effects on PAPR
Peak to Average Power Ratio (PAPR) is the ratio between
the maximum power and the average power of the transmitted
signal. The PAPR is defined as [3]2(1)where xn is the transmitted signal.
For 16-APSK modulation, there are many types of
constellation patterns, such as 4+12 ASPK, 5+11 ASPK, and6+10 APSK. Each type assigns a different number of points toeach ring, with the total number of points summing to 16. Here,the 4+12 APSK is used in the investigation, since it delivers thebest performance under the nonlinear conditions imposed by
the saturation region of a power amplifier and is adopted in
DVB-S2 [15].
The average power level of the 4+12 APSK, which has theconstellation mapping shown in Fig. 1, can be defined as [13]

5dB
6dB

0.17

II. EFFECTS OF THE APSK CONSTELLATION RING RATIO

max n = 0,1,..., N −1 xn
1 N −1 2
∑ xn
N n=0

3

Fig. 2. The relationship between the ratio (R2/R1) of 4 +12 APSK and PAPR

Fig. 1. 16-APSK (4+12 APSK) Constellation

PAPR =

2

0.14
0.13
0.12
0.11
0.1
0.09

1

2

3

4

5
6
R2/R1 ratio

7

8

9

10

Fig. 3. R2/R1 ratio vs. BER of 16-APSK for the linear transmission over
AWGN channel

Es =R12 + 3R22 (1 + 3β 02 ) R12
=
4
4

(2)

where R1 is the radius of the inner ring,andR2 is the radius of the outer ring,
β 0 = R2 / R1 is the ratio between the outer and the innerring radius.

From eq. (1) and (2), we can plot the relationship between
the ratio (R2/R1) of the 4+12 APSK and the PAPR as shown in
Fig. 2. This shows that the PAPR increases when the ratio(R2/R1) increases.
B. The Effects on BER
Considering the 16-APSK modulation for linear transmitterover an additive white Gaussian noise (AWGN) channel
operating at energy per bit to noise power spectral density ratio(Eb/No) of 5 dB and 6 dB, the simulation results in Fig. 3 show
the effects of the ratio (R2/R1) on the performance of thesystem. From Fig. 3, it is seen that the ratio in the range from
2.5 to 5 gives the lowest BER for both Eb/No values.

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

324

Fig. 4. Block diagram of the SC-FDMA system with APSK modulation

From the effects of the constellation ring ratio of 16-APSK
modulation on the PAPR and BER, the appropriate value of theratio can be determined by selecting the ratio that minimizes
both the PAPR and the BER.
The previous analysis shows the effects of the constellation
ring ratio of 16-APSK modulation on the PAPR in general andthe BER for the linear channel only. This clearly shows that theconstellation ring ratio can play a significant role in the nonlinear
channel as well.
Next, the optimal ratio values providing a low BER and
PAPR in the presence of nonlinearities will be addressed.
III. SYSTEM MODEL
Fig. 4 shows the block diagram of the general SC-FDMA
system [3] with the APSK modulation. The binary sequence ismodulated into data symbols, C(n), by using the 4+12 APSK
modulation scheme. Then, a block of N modulated symbols is
applied to the N-point Discrete Fourier Transform (DFT) to
produce a frequency domain representation, D(k).
D(k ) =1

N −1

∑ C (n)e− j 2πnk / N

N n=0

1

M −1

∑ S (k )e + j 2πtk / M

M k =0(5)where r (t ) and θ (t ) are the amplitude and phase of the input
signal to the HPA.
At the receiver, the received signal is processed by removing
the cyclic prefix, first. Then, the signals are demodulated byusing M-point DFT, subcarrier De-mapping, N-point IDFT and
the APSK demodulator.
For this investigation, the nonlinear HPA uses the Soft
Limiter (SL) model, which defines the Amplitude Modulation
to Amplitude Modulation (AM/AM) and the Amplitude
Modulation to Phase Modulation (AM/PM) characteristics asfollowing [8]⎧ − A,⎪
F[ρ ] = ⎨ ρ ,
⎪ A,
⎩
and

where

(4)

Then, the M-point inverse DFT (IDFT) transforms thesedata symbols into the time-domain samples, T(t), of thesesubcarriers.

T (t ) =V (t ) = A[r (t )]e [ j {Φ ( r (t ) +θ (t ))}]

(3)This output is fed to the Localized FDMA (LFDMA)
subcarrier mapping block, which is the subcarrier mappingused in the LTE standard. At this point, each of the N-DFT
outputs is mapped to one of M orthogonal subcarriers (M>N) as⎧⎪ D(k ) ; 0 ≤ k ≤ M − 1
S (k ) = ⎨⎪⎩ 0 ; Otherwise

Similar to OFDM, the cyclic prefix is added to the symbols.
Before entering the AWGN channel, the transmitted signal isamplified by the high power amplifier (HPA), which makes theoverall channel nonlinear. The signal at this point can be
expressed asandif ρ < − A
if − A ≤ ρ ≤ A
if ρ > A(6)

Φ[ ρ ] = 0(7)

A is the saturating level of the amplifier,ρ is the amplitude of the input signals,
F [ ρ ] is the amplitude of the output signals of the Soft
Limiter,Φ[ ρ ] is the phase of the output signals of the Soft
Limiter.

There is only amplitude distortion and no phase distortion in
the SL model. The severity of the distortion can be measured by
the Input-Back-Off (IBO) of the PA, which can be calculated asfollowing [16]Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

325

Fig. 7. The superimposed plot of BER and PAPR when SNR = 5 dB and
IBO = 1 dB

Fig. 5. BER and PAPR under nonlinear PA when IBO = 1 dB

TABLE ITHE OPTIMUM RING RATIOS FOR VARIOUS SNRS AND IBO = 1 AND 2 dB.
SNR

As2
Pin

2 dB

5 dB

2.86

2.81

6 dB

2.75

2.65

10 dB

2.62

2.60

15 dB

2.85

-

20 dB

2.93

2.73

The simulation results include the optimum ring ratio
analysis, the Bit Error Rate (BER) analysis, the 16-QAM and
16-APSK performance comparison, the Peak-to-Average
Power Ratio (PAPR) analysis, and the 16-QAM and 16-APSKPAPR comparison. The description of the results is shown
below.

Fig. 6. BER and PAPR under nonlinear PA when IBO = 2 dB

IBO = 10 log10

IBO
1 dB

(8)

where As is the saturation level of the amplifier input and
Pin is the average input power of the amplifier.
The investigation on the constellation ring ratio of the16-APSK (4+12 APSK) modulation scheme, used in the LTE
uplink system with the nonlinear distortion due to a PA, isbased on the computer simulations. The results are shown in thenext section.
IV. SIMULATION RESULTS
The simulation of a general SC-FDMA transmission is set up
to meet the LTE standard for 5 MHz bandwidth: the IDFT size(M) of 512, DFT size (N) of 300, and a cyclic prefix (CP) of
144 [3], [17]. The 16-APSK modulation scheme, with various
constellation ring ratios, is used instead of the 16-QAM
modulation that is normally used in the LTE standard.

A. Optimum Ring Ratio Analysis
To determine the appropriate range of ratio (R2/R1) for the
16-APSK modulation scheme in the nonlinear channel, theBER and PAPR performances are shown in Fig. 5 and Fig. 6,
with the distortion measured by the IBO of 1 dB and 2 dB,
respectively. The BER and PAPR are measured with various
SNR. These results show that the ring ratio in the range of 2.5
to 3.5 gives the lowest BER range, but not the highest PAPR
values.
Consider more carefully in the above resultant range of
2.5-3.5, the optimum ring ratio for each Eb/No may be
estimated by superimposing the BER and PAPR performance
curves on the dual-scale data chart. Here, the superimposed
chart is chosen because it is commonly used when two data sets
have only one axis in common [18].
For example, the superimposed plot of BER and PAPR when
SNR = 5 dB and IBO = 1 dB, created by the “plotyy()” functionin MATLAB, is shown in Fig. 7. The plot indicates that the
optimum ring ratio is at R2/R1 = 2.86 because the BER and the
PAPR are optimized (low BER and low PAPR) at theirintersection.
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

0

326

0

10

10

QAM IBO=1
APSK IBO=1QAM IBO=2
APSK IBO=2
QAM Linear
APSK Linear

-1

10
-1

10

-2

BER

BER

10

-2

10

-3

10

R2/R1=1.1
R2/R1=2-4

10

R2/R1=2.5
R2/R1=2.75
R2/R1=3

-3

10

-5

R2/R1=3.5

0

5

10

10

15
EbNo

20

25

30

Fig. 8. BER performance when IBO = 1 dB with various R2/R1

0

-1

10

-2

BER

10

-3

10

R/R1=1.1
R2/R1=2
R2/R1=2.5
R2/R1=2.75
R2/R1=3
R2/R1=3.5

-4

-5

10

0

5

10

15
EbNo

20

25

5

Fig. 10.

10

10

0

30

Fig. 9. BER performance when IBO = 2 dB with various R2/R1

By doing the same to the results getting from the simulationfor various SNRs and IBO = 1 dB and 2 dB, the optimum ringratios are found for each value of SNR as shown in Table I.
However, these ratios just give the idea of what the optimum
ring ratios should be for the specific values of SNR and IBO.
The supperimposed plot might provide the optimum ratios
differently if the scale of the y-axis is changed. This is thetrade-off of the dual-scale chart.
Notice that there is no optimum ratio when SNR = 15 dB and
IBO = 2 dB (no intersection of BER and PAPR curves). Thismight be the scale problem of this plot. Also, in practicalimplementation, the SNR values could be changed constantly
due to the channel condition variation. Therefore, it is
impossible to determine the optimum ring ratio specifically and
it is more appropriate to state it in range.
B. Bit Error Rate Analysis
From Fig. 5 and Fig. 6, the ratio R2/R1 gives low PAPR but
high BER when the ratio R2/R1 is lower than 2.5. Fig. 8 andFig. 9 show the simulation results of the system with the IBO of

10

15
EbNo

20

25

30

BER performance when the ratio = 3.5 with various IBO

1 dB and 2 dB, and various values of ring ratios (1.1, 2, 2.5,
2.75, 3, and 3.5), respectively.
In this analysis, we consider at SNR = 20 dB, which gives thehighest throughput for the LTE system with four bits per
symbol modulation [3]. The BERs from Fig. 8 are 7.5x10-2,
5x10-3, 2.5x10-3, 2x10-3, 1.6x10-3, and 1.1x10-3 for each ringratio. At the same SNR of 20 dB, the BERs for each ratio of thesystem with IBO = 2 dB shown in Fig. 9 are 5x10-2, 2.5x10-4,
8x10-5, 5x10-5, 4.5x10-5, and 2.5x10-5. The results in both
figures show that the ratio range of 2.5-3.5 gives better BER
performance than that of 1.1 and 2. Also, These results agree
that the best BER performance occurs when the ratio R2/R1 isequal to 3.5 at high Eb/No.
In addition, the error floor occurs at high SNR and it iscaused by the channel nonlinearity based upon the simulation
results.
C. 16-QAM and 16-APSK Performance Comparison
Fig. 10 shows the BER performance comparison of thestandard 16-QAM and the 16-APSK with the ring ratio R2/R1of 3.5. To make a fair comparison, both modulation schemes
are set to have the same average energy per symbol.
The 16-QAM modulation scheme gives better BER
perfomance than the 16-APSK in the linear channel. But, the16-APSK modulation scheme performs better than the
16-QAM in the nonlinear channel for LTE system. These
outcomes confirm the results in [4]. The error floors associatedwith the average bit error probability shift down from 5x10-3 to
6x10-4 and from 2x10-4 to 6x10-5 for the IBO of 1 dB and 2dB,
respectively.
D. Peak-to-Average Power Ratio (PAPR) Analysis
The Peak-to-Average Power Ratio (PAPR) is analyzed byusing Complementary Cumulative Distribution Function(CCDF). The CCDF of PAPR, which is the probability that
PAPR is higher than a certain PAPR value PAPR0( Pr( PAPR > PAPR0 ) ), for N subcarriers of an OFDM
multi-carrier signal can be calculated by [3](Pr( PAPR > PAPR0 ) = 1 − 1 − e − PAPR0

)

N

(9)

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

Fig. 11. CCDF of PAPR for the nonlinear system with IBO of 1 dB andvarious ring ratios

327

Fig. 13. Comparison of CCDF of PAPR for the 16-QAM and 16-APSK
modulations in the nonlinear system

E. 16-QAM and 16-APSK PAPR Comparison
To make a comparison of the system applying the standard
16-QAM and 16-APSK with constellation pattern of 4+12 andring ratio of 3.5, the average energy per symbol is set to be thesame for both modulation schemes. Fig. 13 shows the PAPR
performance comparison in terms of CCDF measurement. The
system that applies the 16-QAM modulation scheme has ahigher PAPR than the 16-APSK in both linear and nonlinear
channels for LTE system.
Consider at the 99 percentile that the Pr( PAPR > PAPR0 ) isless than 10-2, the PAPR0 of the 16-QAM system is equal to 7.6
dB while it is 7.4 dB for the 16-APSK system. This means thatthe system with 16-APSK outperforms the one with 16-QAM
for 0.2 dB or 2.63 percent.
V. CONCLUSION
Fig. 12. CCDF of PAPR for the nonlinear system with IBO of 2 dB andvarious ring ratios

where

N is the number of subcarriers
PAPR0 is the clipping level in the nonlinear system.

The CCDF is measured by using the Monte Carlo simulation
for the system applying the 16-APSK (4+12 APSK)
modulation with various values of ring ratios in the nonlinear
system with IBO of 1 dB and 2 dB. The comparison of the
CCDF of PAPR for the ring ratios of 1.1, 2, 2.5, 2.75, 3, 3.5, 4,
and 7 is shown in Fig. 11 and Fig. 12.
Consider at the 99 percentile that the Pr( PAPR > PAPR0 )is less than 10-2, the ring ratio of 1.1 gives the smallest PAPR
while the PAPRs of the others are similar.
To choose the optimum ratio for the 16-APSK, one should
consider both the BER and PAPR performances. Then, the ratioof 1.1 is not the appropriate choice for the system even if it has
the smallest PAPR because it gives the poorest BER to thesystem as shown in Subsection B.

LTE technology is attractive in the telecommunicationsindustry due to the high speed data transfer rate it offers.
Therefore, the modulation techniques must be selected properly
as an important consideration because it can push the system toits fullest potential. The APSK modulation works better interms of both BER and PAPR performances than QAM in the
nonlinear system. So, the APSK modulation is an appropriate
modulation scheme to be adopted, as studies have noted in [4],and the ratio of R2/R1 is an important factor affecting the
PAPR and BER of the APSK. The PAPR increases as the ratioof R2/R1 increases. While BER changes differently to theR2/R1 ratio and is shown to have one range with a low BER. In
this paper, it is shown that the optimal R2/R1 ratio of the 4+12
APSK is more suitable to state in range, which is between 2.5 to
3.5. This optimal ratio range gives the best results in terms of
the low BER and PAPR to the nonlinear LTE uplink system.
Also, the 16-APSK with the proposed ring ratio provides better
BER and PAPR performances compared with the standard
system with 16-QAM in the nonlinear system. The authors
hope that this paper will help to drive the performance of the
LTE system that makes the implementation widespread in the
future.
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 5, September 2013

REFERENCES[1]

H. Holma and A. Toskala, LTE for UMTS –OFDMA and SC-FDMA
Based Radio Access, John Wiley & Sons, 2009.
[2] F. Khan, LTE for 4G Mobile Broadband Air Interface Technologies andPerformance, Cambridge University Press, 2009.
[3] H. G. Myung, Single carrier FDMA a new air interface for long term
evolution, John Wiley & Sons, 2008.
[4] J. Gazda, D. Dupak and D. Kocur, “M-APSK modulation for SC-FDMA
communication systems,” Radioelektronika (RADIOELEKTRONIKA),
2011 21st International Conference, 2011, pp. 1-4.
[5] V. Vijayarangan and R. Sukanesh, “An Overview of Techniques for
Reducing Peak to Average Power Ratio and Its Selection Criteria for
Orthogonal Frequency Division Multiplexing Radio Systems,” Journal of
Theoretical and Applied Information Technology, Vol. 5, No. 1, pp. 25-36,
2009.
[6] S. K. Yusof and N. Fisal, “Reducing PAPR of OFDM signals using partial
transmit sequences,” 9th Asia-Pacific Conference on Communications(IEEE Cat. No.03EX732), 2003, pp. 411–414.
[7] R. AliHemmati, P. Azmi, and F. Marvasti, “OFDM clipping distortioncompensation using an iterative method,” VTC-2005-Fall. 2005 IEEE
62nd Vehicular Technology Conference, 2005, vol. 1, no. 1, pp. 444–447.
[8] S. Pagadarai, A. M. Wyglinski, and R. Rajbanshi, “A Sub-optimal
Sidelobe Suppression Technique for OFDM-based Cognitive Radios,”
Military Communications Conference, Nov. 2008, pp. 1-6, 16-19.
[9] G. Chen, R. Ansari, and Y. Yao, “Improved Peak Windowing for PAPR
Reduction in OFDM,” VTC Spring 2009 - IEEE 69th VehicularTechnology Conference, Apr. 2009, pp. 1–5.
[10] Y. Huang and Z. Zeng, “A Simplified Peak Cancellation Method for
OFDM Signals,” 2012 International Conference on Computer Scienceand Electronics Engineering, Mar. 2012, pp. 336–339.
[11] K. Bani, R. Bansode, and B.K. Mishra, “Novel Technique for PAPR
Reduction in OFDM System Using n/4-shifted-DQPSK Modulation &Turbo Code,” Devices, Circuits and Systems (ICDCS), 2012 International
Conference, 15-16 Mar. 2012, pp. 627–633.
[12] Y. Wang, J. Ge, L. Wang, J. Li, B. Ai, and S. Member, “Nonlinear
Companding Transform for Reduction of Peak-to-Average Power Ratioin OFDM Systems,” IEEE Transactions on Broadcasting. pp. 1–7, 2012.
[13] W. Sung, S. Kang, P. Kim and D. Chang, “Performance analysis of APSK
modulation for DVB-S2 transmission over nonlinear channels,”International Journal of Satellite Communications, pp. 295–311, 2009.
[14] Z. Liu, Q. Xie, K. Peng, and Z. Yang, “APSK Constellation with Gray
Mapping,” IEEE Communications Letters, Vol. 15, No. 12, pp.
1271-1273, December 2011.
[15] J. Sebesta, “Efficient Method for APSK Demodulation,” Proceedings ofthe 3rd International Conference on Circuits Systems and Signals(CSS'09), 2009, pp. 187-190.
[16] G. Hill, “Peak Power Reduction in Orthogonal Frequency Division
Multiplexing Transmitters,” PhD. thesis, Victoria University ofTechnology, Melbourne, Australia, March 2011.
[17] Technical Specification Group Radio Access, “Evolved Universal
Terrestrial Radio Access (E-UTRA); Physical Channels and Modulation(Release 10),” 3rd Generation Partnership Project (3GPP), Tech. Rep. TS
36.211 Version 10.5.0, June 2012.
[18] P. Isenberg, A. Bezerianos, P. Dragicevic, and J. D. Fekete, “A Study on
Dual-Scale Data Charts,” IEEE Transactions on Visualization andComputer Graphics, Vol. 17, no. 12, pp. 2469-2478, Dec. 2011.

328

Pornpimon Chayratsami received the BS degree inElectrical Engineering from King Mongkut Institute ofTechnology Ladkrabang, Thailand, in 1994 and the MS
and PhD degrees in Electrical Engineering from
University of Colorado, USA, in 1999 and 2004,
respectively. Since 2004, she has been an instructor at
King Mongkut Institute of Technology Ladkrabang,
Thailand. Her research interests include digitalcommunications, wireless communications, signal
processing, and engineering education.
Sorapong Thuaykaew was born in Chiang Mai,
Thailand, on Apr 2, 1984. He received the B.S. in
Telecommunication engineering and M.S. in Industrial
Education from King Mongkut Institute of Technology
Ladkrabang, Thailand in year 2006 and 2013,
respectively. He is currently a test engineer at Celestica,
Inc., Leamchabang, Chon Buri. His main researchinterests include design and analysis of physical layer
algorithms, multiple access schemes, and mobile
communication.

Copyright ⓒ GiRI (Global IT Research Institute)