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 2

1

Reducing delay and jitter for real-time control communication in Ethernet

162

Mohamad Khairi Ishak*, Guido Herrmann*, Martin Pearson*** Queens School of Engineering University Walk, Bristol BS8 1TR, United Kingdo, **Bristol Robotics Laboratory, Bristol, United Kingdom

2

Design of ETC Violation Enforcement System for Non-payment Vehicle Searching169

Guo-Huang Hsu*, Liang-Rui Lin**, Rong-Hong Jan**, and Chien Chen*** ITRI(Industrial Technology Research Institute), Hsinchu, Taiwan R.O.C., **Department of Computer Science, National Chiao Tung University,
Hsinchu, Taiwan R.O.C

3

Radio Frequency Identification Networks Planning Using a New Hybrid Evolutionary Algorithm179

Han Feng, Jie Qi
College of Information Science and Technology, Donghua University, Shanghai, China

4

Ontology-based Multimedia Contents Retrieval Framework in Smart TV Environment

189

Moohun Lee*, Joonmyun Cho*, Jeongju Yoo*, Jinwoo Hong**Next Generation SmartTV Research Department, ETRI (Electronics and Telecommunications Research Institute), Korea

5

A Proposal of Semantic Analysis based Integrated Multi-Level Search System for Smart TV
Myung-Eun KIM*, Joon-Myun CHO*, Jeong-Ju YOO*, Jin-Woo HONG*, Sang-Ha KIM*** Smart TV Media Research Team, ETRI, 218 Gajeong-ro, Yuseong-gu, Daejeon, 305-700, KOREA, ** Department of Computer Science andEngineering, Chungnam National University, 99 Dae, k-ro, Yuseong-gu, Daejeon, 305-764, KOREA

197

ICACT
ICACTTransactions
Transactionson
onthe
Advanced
Advanced
Communications
Communications
Technology
Technology(TACT)(TACT)
Vol.Vol.
2, Issue2, Issue2, March
2, March
2013
2013

162
162

Reducing delay and jitter for real-time control
communication in Ethernet
Mohamad Khairi Ishak∗ , Guido Herrmann∗ , Martin Pearson∗∗∗

Queens School of Engineering
University Walk, Bristol BS8 1TR, United Kingdom∗∗
Bristol Robotics Laboratory, Bristol, United Kingdom
memki@bristol.ac.uk, g.herrmann@bristol.ac.uk, martin.pearson@brl.ac.uk

Abstract—The aim of this paper is to develop an approach forcheap and deterministic control communication using Ethernet.
A half-duplex Ethernet network populated with a small/medium
number of Media Access Controllers (MACs) is used for timed
real-time communication. Data packages are sent at well definedtimes to avoid collisions. Collisions mainly occur due to jitter of
the transmitter system, so that arbitration (similar to CANopen)
is necessary. In this paper, simulation models using a Binary
Exponential Backoff (BEB) scheme and a Linear Backoff scheme
are developed. This paper analyzes and investigates how thebackoff time affects the performance of the Carrier Sense
Multiple Access protocol with Collision Detection (CSMA/CD) ina basic Media Access Controller (MAC), in terms of data arrival
characteristics, i.e jitter and delay. We propose to assign different
minimal back-off times for each of the CSMA/CD controller units
to minimize packet collisions. Simulated tests show the advantage
of our approach over a standard CSMA/CD setting.
Index Terms—CSMA/CD, Ethernet, Binary Exponential Backoff, Linear Backoff, network model

I. I NTRODUCTION
Research in networking technology and control engineering
are blending uniquely into a challenging area, the development of embedded networked real-time applications. Hence,
the applications should timely deliver synchronized data-sets,minimize latency in their response and meet their performancetarget.
Today, an embedded communication network offers flexibility of the designed system and reduces wiring complexity
which leads to use embedded networks for safety criticalapplications [1], [2]. Most of the applications like robotics,
manufacturing, medical, military, and transportation systems,
depend on embedded computer systems that interact with thereal world [3], [4]. The many fields of applications come withdifferent requirements on such embedded systems [5], [6].
Messages in distributed embedded systems can be sent at a
certain time or when an event occurs, known as time-triggered
and event-triggered communications.
Manuscript received June 9, 2012. This work was not supported by anyorganization.
M.K Ishak and G. Herrmann are with Faculty of Engineering, Departmentof Mechanical Engineering, University of Bristol, BS8 1TR, United Kingdom,
e-mail: memki@bristol.ac.uk
M. Pearson is with the Bristol Robotics Laboratory, University of
the West of England, Bristol, BS34 8QZ, United Kingdom, email: martin.pearson@brl.ac.uk

Ethernet has been the predominant networking technology
for over 20 years. Ethernet is potentially the most practical
network solution due to its expendability, robustness andself-configuration capability. It is nonproprietary in contrast
to other real-time communication protocols. These are thekeys that make it widely used commercially. Our interest
is to use Ethernet for real-time control communication. The
required key characteristic is deterministic processing in thesystem [7]. Real-time control networks must provide a guarantee of service and consistently operate deterministically andcorrectly [8], [9], [10].
Over the last few years, various protocols have been proposed based on a deterministic communication scheme. A
number of network architectures solve the communication
problems: protocols such as EtherCAT, ControlNet, Interbus,
Time Triggered Ethernet (TTEthernet), CANopen, and CAN
have been developed specifically for networking embedded
real-time systems [11], [12]. EtherCat (Ethernet for Control
Automation Technology) is an open real-time Ethernet network, based on standard Ethernet. EtherCat communication
employs a master and slave approach where dedicated hardware is used for slave implementation. A frame is composed
and periodically sent by the master and transferred to all
slave units and finally sent back to the master. TTEthernet
combines standard Ethernet network traffic and hard real-timecommunication for the same infrastructure. It integrates timetriggered and event triggered traffic into a single hardware
infrastructure for distributed communication with mixed critical time requirements. TTEthernet relies on specific switches
to organize the data communication and establish global
synchronization. Custom switches to support the time triggered
communication model are only available from TTTech [13].
Basic ideas of our work are lent from CAN. CAN is adeterministic network which is protocol optimized for shortmessages. The messages have different priority, and higher
priority messages always gain access to the network [14],[15], [16]. Therefore, the transmission delay for higher priority
messages can be guaranteed. But, compared with the othernetworks, CAN has a slow data rate of a maximum of 1Mb/s.
Variants of CAN, Profibus and CANopen, for example, usea master-slave architecture in which one node controls all
communication on the network which carries certain benefits
and cost. A CANopen network uses, a synchronization signal,

Copyright ⓒ GiRI (Global IT Research Institute)

ICACTTransactions
Transactionson
onthe
Advanced
Communications
Technology(TACT)
Vol.Vol.
2, Issue2, March
2013
ICACT
Advanced
Communications
Technology(TACT)
2, Issue2, March
2013

163
163

Synchronization trigger point
Cycle iUnits

1

2 Time 3
slot

4

5

6

Cycle i + 1

7

Fig. 1.

8

9

10

1

2

3

4

5

6

7

8

9

10

Time slot for the communication network approachthe ‘transmit signal’, which triggers transmission of different
nodes at the same time. The data frames need to be arbitrated. In CAN-networking, prioritisation via the CAN-address
is used. As a result, the time-triggered architecture (TTA)
offers fault-tolerant and deterministic communication services.
For Ethernet, many modifications of CSMA/CD have been
extensively studied considering software and hardware based
solutions to enhance the operating system and application layer[17], [18], [19], [20], [21], [22], [23].
This paper aims to establish a cheap control solution forcommunication and deterministic real-time communication in
Ethernet using CANopen similar network features. Thus, asynchronized signal causes the sending of short data packages
from CSMA/CD controllers, which have a data package scheduled. The main feature of this strategy is that a specific minimal backoff time and a specific slot time for each CSMA/CD
controller unit is used for minimal packet collisions. In particular, the assignment of different minimal backoff times toeach CSMA/CD controller results in reduction of collisions,
as it will be seen later. Thus, this paper uses the existing
CSMA/CD protocol and investigates how the back-off interval
affects the performance in a LAN (Local Area Network). We
explore the benefits of the original CSMA/CD scheme forbetter performance without significant modification.
The rest of the paper is organized as follows. In Sections
2 and 3, the principles of the communication system and thesimulation setup are described. Section 4 describes the simulation setup and Section 5 analyzes the CSMA/CD performance
under different minimal back-off interval scenarios. Finally,
Section 6 concludes this paper.
II. COMMUNICATION IN ETHERNETNETWORKSThis section revises the media access control (MAC) protocol,
based on Carrier Sense Multiple Access/Collision Detection(CSMA/CD) and introduces important network characteristics.
A. Ethernet and CSMA/CD
The Binary Exponential Backoff (BEB) algorithm isused [24]. At a time, when a station wants to transmit, it listens
to the transmission medium. When a node detects a carrier, its
Carrier Sense is turned on and it will defer transmission until
the medium is free: if two or more stations simultaneously
begin to transmit, a collision occurs. In this case, the BEB
algorithm for a random time interval is employed as below:

When a collision occurs, each CSMA/CD unit chooses
to back off for a period of time, determined by the
backoff value. The maximal backoff time value at each
unit involved in the collision is multiplied by 2 (maximum
upper bound of 1024 for the factor). The first or initial
backoff time value is termed ‘the minimal backoff time’.
Each CSMA/CD unit will choose a random backoff timevalue which follows an equal distribution with an upperbound given by the maximal backoff value.
• On a successful transmission, the transmitting unit sets
its backoff value to zero.
• If a unit has attempted backoff 16 times due to collisions
for transmitting the same packet, the BEB algorithm
forces that unit to discard that packet. Furthermore, thebackoff value of this unit is reset to zero, i.e any new
backoff/retransmission attempt will be determined again
by the minimal backoff time.
•

B. Jitter
Jitter is one of the critical parameters in high speed
data communication channels [25]. In real-time technology,
a missed hard deadline can have serious consequences. All
real-time systems have a certain level of jitter (a variance on
actual timing). In a real-time systems, particulary, jitter should
be minimal so system performance can be guaranteed. In highspeed communication systems, jitter will generally degrade
performance. Jitter is used to express how much individual
latencies tend to differ from the mean.
The standard deviation which is related to the message
transfer jitter is given by Equation (1), where N is thetotal number of simulated packets, xi is the delay of eachtransferred packet and x̄ is the evaluated average packet delay.
v
u
N
u1 ∑
σ=t
(xi − x̄)2
(1)
N i=1
In our analysis, we use the standard deviation to measure thejitter.
III. PRINCIPLE OF OUR COMMUNICATIONNETWORK APPROACH
We have four principles for the suggested real-timecommunication. The first principle is the synchronization
signal, the second is the introduction of a time slot for each

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced
Communications
Technology(TACT)
Vol.Vol.
2, Issue2, March
20132013
the Advanced
Communications
Technology(TACT)
2, Issue2, March

164
164

Bandwidth
Set Bandwidth (b/s)

Out1

Out1

Out1

Out1

Conn2

Conn2

Out2

Out2

Out2

Out2

Out1

Conn2

Conn2

Conn2

Out2
Conn3

Conn3

Conn3

Conn1

Conn3

Conn3

Conn1

Subsystem01

TX
OUT
IN

Terminator (L)Subsystem02

RX

IN_L

IN_L

OUT_R

OUT_L

OUT_R

T−Junction (A)IN_R

Cable (A<−−>B)

RX

IN_L

OUT_L

OUT_R

IN_R

IN_R

TX

Cable (A<−−>B)1

TX

RX

IN_L

OUT_L

RX

IN_L

OUT_R

IN_R

IN_R

OUT_L IN_R

Cable (A<−−>B)2

T−Junction (A)3

IN_R

RX

Cable (A<−−>B)3

OUT_L

IN_R

T−Junction (A)4

Out1

Conn2

Conn2

Out1

Conn2

Out2

Out2

TX

IN_L OUT_R
OUT_L

Out1

Out1

OUT_R

IN_L OUT_R
OUT_L

T−Junction (A)2

Out2
Out2

Conn3

Conn3

Subsystem04

IN_L OUT_R
OUT_L

T−Junction (A)1

Out2

Subsystem05

Subsystem03

OUT_R

Conn2

Out1

Conn2

TX
IN_L

OUT_L

IN_R

Conn1

Conn1

Conn1

Conn3

Conn1

Conn1

Conn3

Conn1

Conn3

Conn1

Conn1

Subsystem06

Subsystem07

Subsystem08

Subsystem09
Subsystem10

TX
IN_L
OUT_L

RX

IN_L

OUT_R

OUT_R
IN_R

TX
IN_L

OUT_L

IN_R

T−Junction (A)5 Cable (A<−−>B)4

OUT_L

RX

IN_L

TX

OUT_R

IN_L

OUT_R
IN_R

T−Junction (A)6

OUT_L

OUT_L

IN_R

Cable (A<−−>B)5

Fig. 2.

IN_L

RX
OUT_R

OUT_L

IN_R

T−Junction (A)7

IN_R

Cable (A<−−>B)6

TX
IN_L
OUT_L

RX
OUT_R
IN_R

T−Junction (A)8

IN_L
OUT_L

OUT_R
IN_R

TX

OUT_L

Cable (A<−−>B)7

RXIN

IN_L OUT_R
IN_R

OUT

Terminator (R)T−Junction (A)9Network simulation model [26]

Ethernet package and finally the application of different
minimal backoff times for each MAC. In this paper, thelength of one data package is fixed to 64 bytes for a 100Mbps
network. Fixed-length and fixed-order transmission has a
predictable transmission time and reduce the probability offrame collision.

data are sent at well defined time slots, jitter of each
CSMA/CD unit may cause that data packages are sent
outside their time slot and collisions occur. The BEB
scheme comes into play for the half duplex Ethernet
network. For, this the minimal backoff is specificallyassigned to each of the CSMA/CD units.
•

•

OUT_R

Synchronization signal: Real-time applications require
tight synchronization so that the delivery of control
messages can be guaranteed within defined message
cycle times. In this paper, we have employed an internal
synchronization clock for each CSMA/CD/MAC unit.
It implies a precise clock synchronization among thedifferent units so that all nodes are able to agree on theirrespective transmission slot. Practical implementation
would be possible by using the IEEE 1588 clock
synchronization approach.

•

Dedicated time slot for each of Ethernet unit: In thiscommunication network approach, we specify a timeslot for each unit to avoid initial collision in the network
bus. Messages are sent at time slots assigned to each of
the units. Figure 1 shows the communication network
approach.

•

Applying different minimal backoff times: Despite

Linear Backoff Scheme: In a Linear Backoff scheme,
the increase of the maximum backoff window grows
linearly on each successive failure.
IV. SIMULATION SETUP

Simevents, part of Simulink for Matlab is used for modelingthe communication bus. It uses state flow chart for implementation of the backoff logic in the communication system. The
system consists of 10 CSMA/CD/MAC units that share thebandwidth on the Ethernet bus. The physical components of
the network are represented by the terminator, T-junction, andcable blocks at the bottom of the simulation model. Apart from
that, this model provides the number of collision and delivered
packets of each unit [26].
This simulation system enables to evaluate characteristics
such as the average latency and jitter of the message
transmission. Each of the units consists of the following:•

An Application block that models the consumption ofdata.

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced
Communications
Technology(TACT)
Vol.Vol.
2, Issue2, March
2013
the Advanced
Communications
Technology(TACT)
2, Issue2, March
2013

A MAC controller that governs the Ethernet unit’s use of
the shared channel.
• A T-junction to connect each of the units to the networkmodel.
•

This basic setup [26] allows the implementation of our
specific problem for synchronized sending of data packages.

1.5

1

2

3

4

5

6

7

8

9

1

2

3

4

5

Collisions

6

7

8

9

10

Unit

4

x 10

10
8
6

1

Average
JitterAverage
Delay

Maximum
Collisions

Binary Exponential
Backoff(ST1)

1.2761ms

1.6745ms

88,194

Linear Backoff(ST1)

1.1847ms

1.4913ms

74,670

Binary Exponential
Backoff(ST2)

1.1825ms

1.6211ms

87,637

Linear Backoff(ST2)

1.1750ms

1.4522ms

72,491

10

2
1.5

Slot
Time

Unit

−3

x 10

2.5

Scheme

2

3

4

5

6

7

8

9

10

Unit

Jitter (seconds)

1

TABLE IIC ASE 2 : D IFFERENT SLOT TIME AND IDENTICAL BACKOFF TIME .

Delay (seconds)

Jitter (seconds)
Delay (seconds)

Linear
BEB

−3

x 10

2

BEB
Linear

−3

x 10

2
1.5
1

1

2

3

4

5

x 10

Jitter, delay and collisions for Case 1

TABLE I

1

1

2

3

4

5

Binary Exponential Backoff
Linear Backoff

1.4068ms
1.3063ms

1.8393ms
1.6881ms

94,68980,715

Delay (seconds)

Jitter (seconds)

Maximum
Collisions

Linear
BEB

−3

1

x 10

1

2

3

4

5

x 10

7

8

9

10

6

7

8

9

10

6

7

8

9

10

1.5
1

1

2

3

4

5

Unit

4

10
Collisions

6

Unit

−3

2

x 10

8
6
1

2

3

4

5

Unit

Fig. 4.

Jitter, delay and collisions for Case 2

For this, we specify the packet generation rate and packet
size range at the application blocks, the transmission buffer
size of 25 packets at the MAC Controller blocks, and thelength of the cable at the Cable blocks. We also implemented
additional Simulink logic to measure the latency of the communication network from a transmit point, Tx to receive point

10

6

7

8

9

10

6

7

8

9

10

6
2

3

4

5

Unit

Fig. 5.

Average
Delay

9

8

1

Average
Jitter

8

Unit

x 10

C ASE 1 : I DENTICAL MINIMAL BACKOFF TIME AND IDENTICAL SENDING
TIME .
Scheme7

1.5

10Collisions

Fig. 3.

6

Unit

−3

2

4

1.5

165
165

Jitter, delay and collisions for Case 3

for, Rx in the Ethernet MAC control block to measure thesending of a packet. All the units transmit at the average rateof 100 packets per second with the packet size of 64 bytes andthe length of the cable determined at the Cable blocks of 100
meter. The synchronization signal has a frequency of 100Hz
which is artificially created by a synchronized signal througha frequency generator in the subsystem application block.
It is assumed that the data source has a certain jitter: eachpacket is created with a jitter of 10µs (standard deviation).
The packet rate guarantees that any collision between packets
is only due to packets being sent after a synchronization
event. Thus, no collision should occur due to overload of
the network, but only arbitration between synchronized data
packets. This guarantees to understand the true delay and jitter
due to our suggested scheme. The statistical evaluation ofjitter and packet delay is carried out for 300 seconds. This
gives a sufficiently large number of synchronization events
for statistical evaluation.
V. SIMULATION ANALYSISThe performance of the proposed strategy is compared tothe traditional setting of the backoff scheme in Ethernet. It
is our target to investigate the effect of different minimal
backoff intervals and dedicated sending time slots for each
MAC unit. The approach is to assign the minimal back-offtimes and sending time slots either in a random fashion or

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT
Communications
Technology(TACT)
Vol.Vol.
2, Issue2, March
2013
ICACT Transactions
Transactions on
on Advanced
the Advanced
Communications
Technology(TACT)
2, Issue2, March
2013

TABLE IIIC ASE 3 : D IFFERENT MINIMAL BACKOFF TIMES AND IDENTICAL PACKAGESENDING IN TIME SLOTS .
BackoffTime

Average
JitterAverage
Delay

Maximum
Collisions

Binary Exponential
Backoff(BT1)

1.2187ms

1.5766ms

85,698Linear Backoff(BT2)

1.1531ms

1.4563ms

75,945Binary Exponential
Backoff(BT2)

1.1471ms

1.3271ms

81,760Linear Backoff(BT2)

1.1092ms

1.2116ms

72,512

Delay (seconds)

Jitter (seconds)

SchemeLinear
BEB

−3

x 10

2
1
0

1

2

3

4

5

x 10

7

8

9

10

1
0

1

2

3

4

5

6

7

8

9

10

Unit

4

8
Collisions

6

Unit

−3

2

x 10

6
4

1

2

3

4

5

6

7

8

9

10

Unit

Fig. 6.

Jitter, delay and collisions for Case 4

according to a linear approach to the 10 available MACs.
Case 1: Identical minimal backoff time and identical sendingtime.
For this case, all the data packages are sent with identicalminimal backoff time of 51.2 µs and an identical sendingtime triggered by the synchronization signal, is set foreach CSMA/CD controller unit. Table 1 summarizes theperformance of both schemes and Figure 3 and Table 1
illustrate the values of jitter, delay and number of collisions
for each MAC unit controller. As illustrated, the results
show for this case that the Linear Backoff setting is thebetter strategy to reduce jitter, delay and collisions. Clearly,
the Linear backoff scheme appears to be more deterministic
than the BEB scheme as jitter in general about is 9.2% smaller.
Case 2: Identical minimal backoff times and different
package sending in time slots.
We investigated the backoff characteristic by assigning
different time slots for the sending of each data package(see Table 5, ST1 and ST2). The minimal backoff times
for each MAC unit is identical at the value of 51.2 µs forboth the BEB and Linear Backoff scheme. The assignment ofdifferent sending slots to data packages will reduce the need

166
166

TABLE IVC ASE 4 : R ESULTS OF DIFFERENT MINIMAL BACKOFF TIMES AND
DIFFERENT SLOT TIMES .
SchemeAverage
JitterAverage
Delay

Maximum
Collisions

Binary Exponential Backoff
Linear Backoff

0.9760ms
0.7642ms

1.0819ms
1.0431ms

71,39254,885for arbitration, although collisions are still expected due tojitter in the transmission units/times. Again, based on Table 2
and Figure 4, the Linear Backoff scheme shows an advantage
over the BEB scheme. Nevertheless, a general decrease in jitteris also evident from Case 2 in relation to Case 1. This is clearly
due to the different time slots for each MAC-unit. However,note that for the ST1 scheme, some MAC-unit use similar
slot times in this case. This contrasts scheme ST2, where
each MAC unit has different time slots. Thus, less arbitration,
collisions and lower sending jitter, delay are observed for ST2
in relation to ST1.
Case 3: Different minimal backoff times and identicalpackage sending in time slots.
We observed the backoff characteristic by assigning
different minimal backoff times (as in Table 5 (BT1)),
multiples of 51.2µs, to each of the MAC controller in the
Ethernet network with identical package sending time slots.
Table 3 and Figure 5 depict the network performance for bothschemes where the random different backoff times still affectthe results of jitter and delay in comparison to Case 2. In thiscase, the Linear Backoff scheme has again achieved a betterlevel of performance over the BEB scheme. It is interesting tonote that there is an advantage of the Linear Backoff schemein Case 3 over Case 2 results. Thus, the backoff algorithm
and the minimal backoff times have significant effect on jitter.
Case 4: Linearly increasing minimal backoff times anddifferent package sending in time slots.
In this case, the minimal back-off times are linearly
distributed across the ten MACs. The principal idea isto reduce collision between different packages once a firstcollision has occurred. By assigning different minimal backoff
times and different slot time (see Table 5 (ST1 and BT1) tothe Linear and BEB algorithms of each MAC unit, it is hopedthat the MACs will have a lowered probability of collision.
Hence, in this case, each unit in the network model has been
specified by the different minimal backoff and slot time value
as in Table 1. Figure 6 and Table 4 illustrate the performance
result of the communication in Ethernet networks.
Case 5: Random minimal backoff times and package sendingin time slots.
For further investigation, the minimal back-off times are
randomly distributed across the ten MACs (see Table 3 (ST2and BT2)). Table 6 and Figure 7 illustrate the performance

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced
the Advanced
Communications
Communications
Technology
Technology(TACT)(TACT)
Vol.Vol.
2, Issue2, Issue2, March
2, March
2013
2013

167
167

TABLE VS IMULATION : D ISTRIBUTED SLOT TIMES WITH RANDOM BACKOFF TIMES
Different slottime(ST1)

1
2
3
4
5
6
7
8
9
10

0.0512 ms
0.0512 ms
0.0512 ms
0.1024 ms
0.1024 ms
0.1024 ms
0.2048 ms
0.2048 ms
0.2048 ms
0.4096 ms

Different minimal
backoff time(BT1)

Different slottime(ST2)

Different minimal
backoff time (BT2)0.0512 ms
0.1024 ms
0.1536 ms
0.2048 ms
0.2560 ms
0.3072 ms
0.3584 ms
0.4096 ms
0.4608 ms
0.5120 ms

0.2048 ms
0.1024 ms
0.0512 ms
0.4096 ms
0.2560 ms
0.4608 ms
0.3072 ms
0.1536 ms
0.3584 ms
0.5120 ms

0.1024 ms
0.2560 ms
0.0512 ms
0.1536 ms
0.4096 ms
0.5120 ms
0.2048 ms
0.1024 ms
0.3072 ms
0.3584 msof the different test for the combination of ST2 and BT2.
It is evident that the Linear Backoff scheme provides anadvantage over the BEB case, as the smallest average jitteris provided by the Linear Backoff scheme. Moreover, a too
close set of sending and backoff times increase the chancefor collisions, which is evident when comparing Case 4 with
Case 5. Case 5 shows better results since each unit has now
indeed a dedicated time slot (and minimal backoff time).

Delay (seconds) Jitter (seconds)

Unit

Linear
BEB

−3

x 10

2
1
0
2

1
−3
x 10

2

1

2

3

4

5

6

7

8

9

10

6

7

8

9

10

6

7

8

9

10

Unit

1
0

3

4

5

Unit
4

x 10

Comparative analysis
After simulating all the communication scenarios as above,it has been found that both numbers of successful transmissions and collisions are affected by the back-off times for bothschemes, Linear and BEB. When the minimal back-off time is
not long enough the number of collisions detection scheme canbe very significant. The different minimal back off time andtime slot method are able to avoid the stations from repetitively
entering the back off state, minimizing the collision possibility.
This is particularly obvious for the Case 3 in relation to Case2.
It is shown that Linear Backoff is significantly lower than
BEB in the results of jitter, delay and collisions. In Case 5, up
to 54.8% of jitter and delay can be reduced using the Linear
Backoff compared to the standard setting of Ethernet, BEB
scheme. One of the reasons of this scenario is that linear
increments give enough backoff time to enhance the network
performance by reducing the number of transmission failures.
The number of collisions for both schemes particularly MACunit 10 has indeed significantly decreased more than 55.6%.
Hence, Linear Backoff introduces a higher level of fairness.
Case 5 is in fact providing the best overall result for theinvestigated cases here. This is also true when considering the
combination of sending time slots ST2 together with minimal
backoff times as in BT1 (See Table 3 for ST2 and BT1 andTable 7 for results)
In future work, longer minimal backoff times will be
investigated. It is expected that a long random backoff timecause ineffective channel utilization, but a short one may sufferfrom high collision rate. The backoff time relates directly

Collisions

8
6
4

1

2

3

4

5

Unit

Fig. 7.

Jitter, delay and collisions for Case 5

TABLE VIC ASE 5 : R ESULTS OF RANDOM MINIMAL BACKOFF TIMES AND SLOTTIMES .
SchemeAverage
JitterAverage
Delay

Maximum
Collisions

Binary Exponential Backoff
Linear Backoff

0.9322ms
0.7167ms

1.0566ms
1.0163ms

69,79552,655to the ability to access to the channel in Ethernet network
communication, lower backoff time means more chance tosucceed in channel contention. Thus, it can be seen that
selection of the backoff algorithm is very significant for the
network performance.
Overall, the backoff mechanism dramatically affects theperformance of the MAC protocol, and hence the overall
network performance. The backoff period is directly related
to the nodes’ idle times. As a result, the standard exponential
back-off scheme has been shown on 5 cases to result in highpacket delays and jitter.
VI. CONCLUSION
In this paper, we constructed and simulated the original
CSMA/CD protocol through Simevents-Matlab block. We

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced
Communications
Technology(TACT)
Vol.Vol.
2, Issue2, March
2013
the Advanced
Communications
Technology(TACT)
2, Issue2, March
2013

TABLE VIIR ESULTS OF DIFFERENT MINIMAL BACKOFF TIMES AND DIFFERENT SLOTTIMES (BT1 & ST2)
SchemeAverage
JitterAverage
Delay

Maximum
Collisions

Binary Exponential Backoff
Linear Backoff

0.9773ms
0.8421ms

1.0733ms
1.0345ms

72,65554,828created a time synchronized bus communication by taking
inspiration from CANopen, i.e packets are sent at given timeslots while any collision is resolved through the BEB andLinear Backoff schemes of Ethernet in a random approachfor the minimal backoff time. We analyzed the effect of thebackoff time on the system performance, in terms of jitter anddelay. The simulated test results have shown that the delay
jitter can be reduced by choosing the correct backoff time to be
implemented in the MAC controller. The special assignmentof the minimal backoff times to each MAC unit allowed tominimize the packet transmission time jitter by up to 55%. The
key results are that a Linear Backoff scheme exhibits lower
jitter and access delay than a BEB scheme. Linear Backoff
appears to be more deterministic. Our approach of an Ethernet
network based communication system improves determinism
at low cost.
ACKNOWLEDGEMENTS
The authors gratefully acknowledge the contribution of the
Ministry of Higher Education Malaysia (MOHE) and thereviewers’ comments.
R EFERENCES[1] K. C. Lee and S. Lee, “Performance evaluation of switched ethernet
for real-time industrial communications,” Computer Standards and Interfaces, vol. 24, no. 5, pp. 411 – 423, 2002.
[2] C. Venkatramani and T.-c. Chiueh, “Design, implementation, and evaluation of a software-based real-time ethernet protocol,” SIGCOMM
Comput. Commun. Rev., vol. 25, pp. 27–37, October 1995.
[3] “Embedded network,” in http://techon.nikkeibp.co.jp/article, 1 November. 2009.
[4] G. Kopetz, H. Griinsteidl, “Ttp-a protocol for fault-tolerant real-timesystems,” in IEEE Computer, pp. 14–23, January 1994.
[5] D. Wiklund and D. Liu, “Socbus: switched network on chip for hardreal time embedded systems,” in Parallel and Distributed Processing
Symposium, 2003. Proceedings. International, p. 8 pp., april 2003.
[6] M. Felser, “Real-time ethernet - industry prospective,” Proceedings ofthe IEEE, vol. 93, pp. 1118 –1129, june 2005.
[7] V. Pallares-Lopez, A. Moreno-Munoz, M. Gonzalez-Redondo, R. RealCalvo, I. Garcia, A. de Castro, F. Perez, and J. de la Rosa, “Deterministic
ethernet synchronism with ptp-base system for synchrophasor in smart
grid,” in Compatibility and Power Electronics (CPE), 2011 7th International Conference-Workshop, pp. 22 –27, june 2011.
[8] R. Focardi, R. Gorrieri, and F. Martinelli, “Real-time information flow
analysis,” Selected Areas in Communications, IEEE Journal on, vol. 21,
pp. 20 – 35, jan 2003.
[9] R. Metcalfe, “Computer/network interface design: lessons from arpanet
and ethernet,” Selected Areas in Communications, IEEE Journal on,
vol. 11, pp. 173 –180, feb 1993.
[10] F. Tobagi and I. Dalgic, “Performance evaluation of 10base-t and100base-t ethernets carrying multimedia traffic,” Selected Areas inCommunications, IEEE Journal on, vol. 14, pp. 1436 –1454, sep 1996.
[11] S.-K. Kweon and K. Shin, “Statistical real-time communication over
ethernet,” Parallel and Distributed Systems, IEEE Transactions on,
vol. 14, pp. 322 – 335, march 2003.

168[12] F. Carreiro, R. Moraes, J. Fonseca, and F. Vasques, “Real-time communication in unconstrained shared ethernet networks: the virtual tokenpassing approach,” in Emerging Technologies and Factory Automation,
2005. ETFA 2005. 10th IEEE Conference on, vol. 1, p. 8 pp.432, sept.
2005.
[13] F. Recacha, J. Melus, X. Simon, M. Soriano, and J. Forne, “Securedata transmission in extended ethernet environments,” Selected Areas inCommunications, IEEE Journal on, vol. 11, pp. 794 –803, jun 1993.
[14] J.-L. Scharbarg, M. Boyer, and C. Fraboul, “Can-ethernet architectures
for real-time applications,” in Emerging Technologies and Factory
Automation, 2005. ETFA 2005. 10th IEEE Conference on, vol. 2, pp. 8
pp. –252, sept. 2005.
[15] J. Cloud, L. Zeger, and M. Medard, “Mac centered cooperation; synergistic design of network coding, multi-packet reception, and improved
fairness to increase network throughput,” Selected Areas in Communications, IEEE Journal on, vol. 30, pp. 341 –349, february 2012.
[16] B. Wiese and K. Jacobsen, “Use of the reference noise method bounds
the performance loss due to upstream power backoff,” Selected Areas inCommunications, IEEE Journal on, vol. 20, pp. 1075 –1084, jun 2002.
[17] T. Skeie, S. Johannessen, and O. Holmeide, “Timeliness of real-time
ip communication in switched industrial ethernet networks,” Industrial
Informatics, IEEE Transactions on, vol. 2, pp. 25 – 39, feb. 2006.
[18] L. Seno, S. Vitturi, and C. Zunino, “Real time ethernet networks
evaluation using performance indicators,” in Emerging Technologies
Factory Automation, 2009. ETFA 2009. IEEE Conference on, pp. 1 –8,
sept. 2009.
[19] L. Tao, T. Jiang, and Z. Xiangli, “A solution for ethernet-based real-timecommunication network of distributed numerical control system,” inTechnology and Innovation Conference 2009 (ITIC 2009), International,
pp. 1 –6, oct. 2009.
[20] L. Lo Bello, G. Kaczynski, and O. Mirabella, “Improving the realtime behavior of ethernet networks using traffic smoothing,” Industrial
Informatics, IEEE Transactions on, vol. 1, pp. 151 – 161, aug. 2005.
[21] P. Ferrari, A. Flammini, D. Marioli, and A. Taroni, “A distributed
instrument for performance analysis of real-time ethernet networks,”
Industrial Informatics, IEEE Transactions on, vol. 4, pp. 16 –25, feb.
2008.
[22] G. Chockler, D. Malkhi, and M. Reiter, “Backoff protocols for distributed mutual exclusion and ordering,” in Distributed Computing
Systems, 2001. 21st International Conference on., pp. 11 –20, apr 2001.
[23] O. Kleineberg, P. Frohlich, and D. Heffernan, “Fault-tolerant ethernet
networks with audio and video bridging,” in Emerging Technologies
Factory Automation (ETFA), 2011 IEEE 16th Conference on, pp. 1 –8,
sept. 2011.
[24] K. Wang, C. Zhang, X. Ding, S. Ji, and T. Hu, “A new real-time ethernet
for numeric control,” in Intelligent Control and Automation (WCICA),
2010 8th World Congress on, pp. 4137 –4141, july 2010.
[25] A. Mejia, J. Flich, J. Duato, S.-A. Reinemo, and T. Skeie, “Boosting
ethernet performance by segment-based routing,” in Parallel, Distributedand Network-Based Processing, 2007. PDP ’07. 15th EUROMICROInternational Conference on, pp. 55 –62, feb. 2007.
[26] “Simevents,” in http://www.mathworks.co.uk/products/simevents/demos.html,
15 November. 2010.

Mohamad Khairi Ishak received
a B.Eng. (Hons.) in Communication
Engineering from the International
Islamic University Malaysia. In 2008,
he received an MSc. in Embedded
System from the University ofEssex, United Kingdom. Currently,
he is a final year PhD student at
the University of Bristol. His PhD
research focuses on real-time control communication system
particularly in Ethernet.

Copyright ⓒ GiRI (Global IT Research Institute)Dr. Guido Herrmann received theGerman degree Diplom-Ingenieur der
Elektrotechnik (with highest honours)
from the Technische Universitt zu
Berlin. In 2001, he received a Ph.D.
from the University of Leicester.
From 2001 to 2003, he worked in
the mechatronics and micro-systems
group of the A*Star Data Storage
Institute (Singapore) doing research and consultancy for thedata storage industry. From 2003 until February 2007, he
was a Research Associate, Research Fellow and a Lecturer
in the Department of Engineering at Leicester University. In
March 2007, he took up a permanent lecturing position at the
Department of Mechanical Engineering of the University ofBristol. In August 2009, he was promoted to Senior Lecturer.
Since August 2012, he has been a Reader in Control andDynamics.
Martin Pearson received a B.Eng.
(Hons.) in Electrical and Electronic
Engineering from the University ofManchester in 1996, an MSc. in
Advanced Technologies in Electronics from the University of the Westof England in 2002 and a PhD.
in Computational Neuroethology andRobotics in 2008. He is currently a
Research Fellow and theme leader of the Biomimetics and
NeuroRobotics group at the Bristol Robotics Laboratory,
United Kingdom.

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013

169

Design of ETC Violation Enforcement System
for Non-payment Vehicle Searching
Guo-Huang Hsu*, Liang-Rui Lin**, Rong-Hong Jan**, and Chien Chen***ITRI(Industrial Technology Research Institute), Hsinchu, Taiwan R.O.C.
**Department of Computer Science, National Chiao Tung University, Hsinchu, Taiwan R.O.C.
GHHsu@itri.org.tw, {ljlin, rhjan, chienchen}@cs.nctu.edu.tw

Abstract—As we know, the heaviest traffic congestion on
highways occurs near toll gates where vehicles make a short stop
to pay the toll. So an electronic toll collection (ETC) system isusually built to eliminate the traffic jams. In order to find out the
non-payment vehicles, the violation enforcement usually includes
cameras to capture images of license plates, and a license plate
reader system to recode photographs and license plate numbers ofall vehicles. Thus, automatic license plate recognition (ALPR)
technology is often used in violation enforcement. However, theidentification precision of ALPR is not always reliable. Humanreview and correction will be needed to improve the accuracy andtherefore will result in extra manual operation cost. In this paper,
we consider multilane-free-flow ETC systems and formulate thenon-payment vehicle searching problem into a matching problem
and propose a Photograph-to-Transaction matching algorithm(PT algorithm) based on bipartite graph. The PT algorithm not
only can reduce the human loading to review and correct theimage recognition results but also can accurately identify all
non-payment vehicles. The performance of the PT algorithm wasevaluated in ns-2 simulator and three different traffic scenarios:
congested traffic, normal traffic and sparse traffic. The simulation
results show that our algorithm greatly reduce the number of plate
recognitions, and is more feasible and reliable for ETC
enforcement. This will activate some consequent activities against
the violation vehicles.
Keyword—ETC, multilane free flow, violation enforcement,
bipartite graph, matching.

I. INTRODUCTION

O

wing to the dramatic cost down on electronic components
and the advances on wireless technologies, thedevelopment of Intelligent Transportation System (ITS) has
drawn intensive attention in recent years from many countries.

Manuscript received June 20, 2012. This work was supported in part by the
National Science Council of the Republic of China under grants NSC
100-2221-E-071-MY2.
Guo-Huang Hsu is with the Industrial Technology Research Institute, 195, Sec.
4, Chung Hsing Rd., Chutung, Hsinchu, Taiwan 31040, R.O.C.
Phone: +886-3-5915682; fax: +886-3-5836236; e-mail: GHHsu@itri.org.tw.
Liang-Rui Lin, Rong-Hong Jan and Chien Chen are with the Department ofComputer Science, National Chiao Tung University, 1001 Ta Hsueh Road,
Hsinchu, Taiwan 300, ROC.
Phone: +886-3-5712121; e-mail: {ljlin, rhjan, chienchen}@cs.nctu.edu.tw

The Vehicular Ad hoc Network (VANET) is a promising
approach for the future ITS. In this novel architecture, thein-vehicle device (On-Board Unit, OBU) can communicate withroadside units (RSU) and with each other, referred to as
vehicle-to-roadside (V2R) and vehicle-to-vehicle (V2V)
communication, respectively. Due to VANETs have thecharacteristics of low-latency transmission and rapid topology
change, 802.11 doesn’t fit with above characteristics. So theIntelligent Transportation Systems (ITS) Committee of theIEEE Vehicular Technology Society (VTS) develops the IEEE
802.11p/1609.X draft and the Federal Communications
Commission (FCC) of the U.S allocates 75MHZ Dedicated
Short Range Communication (DSRC) spectrum within the(5.85-5.925) GHZ for VANET [19]. The overall bandwidth isdivided into seven channels which are composed of one control
channel (CCH) and six service channels (SCHs). The CCH ismainly used to transmit safety-critical messages and highpriority messages in the form of WAVE short message. On theother hand, the SCHs are used to deliver non-safety messages.
In all applications for VANET, it can be divided into two
main categories: safety and non-safety applications. The
purpose of the safety application is to transmit the emergency
messages and collision avoidance to decrease the traffic
accident. The emergency messages are usually reserved at the
specific zone for a long time so that the drivers can pay attention
to the warning area. The Cooperative Collision Avoidance(CCA) [2] informs the backward vehicles the front roadinformation so that the vehicle collision accident could be
reduced. The common characteristic of the applications are thatthe messages should be propagated in low delay time reliably. In
non-safety applications, the focus is on transmission of large
data files, multi-hop communication and service provision suchas the Electronic toll collection (ETC).
According to a research of traffic congestion on highways,
the heaviest congestion occurs near toll gates where vehicles
make a short stop to pay the toll. Hence, the primary cause of
traffic jams can be eliminated by building an ETC system.
Through wireless communication between OBU and theroadside antenna of a toll gate, vehicles are able to pay the tolland drive through toll gate without stopping. In general, ETC
systems currently used in the world can be classified into two
types: single-lane free flow (SLFF) and multilane free flow

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013

(MLFF) as shown in Fig. 1. It is also known that MLFF ETC
systems have much greater complexity than SLFF ETC systems,
but the former is more convenient for faster passing due to theless restriction on vehicle speed.

(a)

(b)

Figure 1. (a) Multilane Free Flow. (b) Single Lane Free Flow.
In Fig. 2, it shows the four components of a typical ETC
system [15]. It includes 1) Automatic Vehicle Identification(AVI); 2) Automatic Vehicle Classification (AVC); 3)
transaction processing; and 4) violation enforcement. The AVI
component involves the use of OBU-to-RSU communications
to identify the vehicle when entering the toll gate area. The typeof OBU can be either a transponder or a radio-frequency
identification (RFID) tag so that the vehicle can automaticallybe identified. The communication technology of ETC can beclassified into two types of categories: Dedicated Short Range
Communication (DSRC) System and Vehicle Position System(VPS). In DSRC system, it has two main communication
technologies called infrared and microwave. The infraredcommunication technology is mature and has the features of low
cost, fewer channel collision, easy installation and maintenance.
But it is also easily affected by weather conditions and only
suitable for SLFF. In order to increase traffic flow throughput,
microwave communication is mostly adopted for MLFF inmany countries now. In VPS, it combines GPS and mobile
communication such that vehicles could report its real-time
position to the server and the drivers could receive the bills bycell phone. Because of the high precision requirement of thevehicle position, the technique is still not matured.
Transponder
(OBU)

RSU

Automatic Vehicle Identification(DSRC, VPS)

Plaza Host Computer(Automatic Vehicle Classification)(Transaction processing)170

debiting the toll from the customer’s account and addressing
customer inquiries. Violation enforcement usually includes
cameras to capture images of license plates, and a license plate
reader system to recode photographs and license plate numbersof all vehicles. Thus, automatic license plate recognition(ALPR) technology is often used in violation enforcement. In
addition to taking and recognizing pictures, the most common
current practice in violation enforcement involves determining
and sending out written notices for each violation. The
determining can be performed by matching the transaction datawith the correct license plate number recognized by ALPR. As
the factors of dirty plate surface, weather or equipment, so theidentification precision of ALPR is not always reliable. For thisreason, human review and correction will be needed to improve
the accuracy of the license plate recognition. However,
employing a lot of human labor for recognizing a large numberof photographs will increase the extra manual operation cost. In
SLFF, the violation enforcement system is easy to match thevehicle’s transaction record to its image record correctly
because the two records must take place at the same lane;
however, in MLFF, it is relatively complicated to match thevehicle’s transaction record to its image record because thetransaction location can be anywhere in the highway toll gatearea.
In this paper, we consider the violation enforcement of MLFF
ETC systems and focus on improving the efficiency of finding
the non-payment vehicles. As we known, ALPR technology is
one of the important factors for matching the vehicle’s
transaction data to its license plate image data. However the
precision of the ALPR is not always reliable as mentioned
above. So human loading will be increase. In order to reduce thecount of executing ALPR, we formulate the non-payment
vehicle searching problem into a bipartite graph matchingproblem and propose a Photograph-to-Transaction matchingalgorithm (PT algorithm). PT algorithm not only can reduce thehuman loading to review and correct the image recognition
results but also can accurately identify the vehicles that drive
through a highway toll gate area without paying for toll. The restof this paper is organized as follows: Section 2 provides
previous results and system model. Based on the system model,
the PT algorithm for identifying all violations is proposed in
Section 3. In Section 4, we show and discuss the simulation
results. Finally, our conclusions are given in Section 5.

Cameraviolation enforcement system

II. PRIOR WORKS AND SYSTEM MODEL
Toll Processing
Violation Processing
Account Management

Figure 2. Electronic toll collection Architecture.
For AVC component, vehicle class can be determined by thevehicle’s physical characteristics, such as the number of axles.
A higher toll is usually imposed on a vehicle with more axles.
Larger commercial trucks or vehicles pulling trailers, therefore,
would likely pay a higher toll. Transaction processing entails

A. Prior Works
Currently in the world, many countries and cities haveconducted the MLFF system, and many related techniques havebeen proposed [3-13, 16-18]. Some of these researches were
proposed for AVI components. In [12], the authors designed
in-pavement antennas with carrier frequency 915MHZ. The tag
is on the lower edge of the front license plate, and thein-pavement antennas are buried under the road. The
transmission range is one meter wide and 2 meter high. It
support variable bits packet for several operations. However, it
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013

is not sufficient for congested traffic. In [9] the authors
proposed MLFF architecture for ETC. The gantry is 6.2m
height cross the width of three lanes and the transceivers arewith carrier frequency 5.8GHz. In [10] the authors proposed anovel architecture by employing millimeter-wave range in
MLFF. Each lane is equipped with antennas and the frequencyof each is different. The proposed scheme utilized highresolution in lateral directions to track the vehicle’s direction.
This is for separating the packets into segments so that cancommunicate with RSU consecutively. The communication
range may overlap on the intersection of adjacent lane.
Some of researches were proposed for AVC components. In[16], the authors proposed a wire device that can get theelectronic signal when vehicle passing. The device can classify
type of vehicles by the variation signal information. ETC
System can utilize the information to toll different amount ofmoney.
For violation enforcement system, some of papers were also
proposed to study the performance in MLFF. In [6], Lee et al.
designed and implemented a MLFF system based on VPS
techniques. As shown in Fig. 3, a virtual toll zone is a rectangle
area identified by a pair of coordinates {(x1,y1), (x2,y2)}, andconsists of notification area, toll area and enforcement line. The
vehicle moving into the notification area will be notified that atolling transaction is going to be carried out, and the debit
transaction is going on when the vehicle passing through the tollarea. Enforcement line has enforcement devices such as
cameras, vehicle classification sensors installed on it in order to
identify the vehicle class and capture the vehicle license plates.
Camera modules take pictures for every vehicle entering the tollarea and ALPR module recognizes every license plate number
in order to discriminate the registered and un-registered vehicles
by matching the license plate number with the tollingtransaction data. Since all the missions should be done in nearlyreal time, it is a computing critical task for the enforcement
system. The authors, therefore, propose a match pre-processing
skill to reduce the computing capacity in license plate
recognition and arise the pre-matching accuracy. The license
plate number is sent to the enforcement system immediately by
querying the registered user database in the backend system
when it receives ‘TS’ message, an online debit message send
tracks in toll zone, from a vehicle. Thus whenever the vehicle
passes through the enforcement line, the enforcement system
has the capability of ‘prediction’ the next coming registeredvehicle license plate. This action improves the efficiency andaccuracy of ALPR and match pre-processing. The match
pre-processing is done when the license plate number received
from the backend is matched to the license plate number
recognition, and all the images of unrecognized vehicle is stored
in the backend database for the post matching and violation
processing.

171

Enforcement Line
X

Toll
Area

(x1, y1)
X

Notification
Area
X

Notification
Area

Toll
Area
X

(x2, y2)

Figure 3. Virtual toll zone configuration in VPS system.
In [17], the authors proposed a tolerant algorithm to matchthe license plate number with the tolling transaction data. The
steps of this algorithm are as follows: 1) for all license plate
numbers recognized by ALPR, if there exists a transaction data
which can fully match with the digits of the license plate number,the license plate image is a paid vehicle. 2) For remaining
license plate numbers, if there exists a transaction data which
can match with four or more digits, the license plate image also
can be seen a paid vehicle. 3) Discriminate all unmatchedlicense plate numbers to be paid or unpaid by manual operation.
In [18], the authors also consider the MLFF system based on
VPS and proposed an automatic matching method to improve
the performance of violation enforcement. As shown in Fig. 4,
the vehicle equipped with GPS receiver will report the location
information per second when passing through the toll area. The
lane location where the vehicle is taken a picture at can be
estimated by two location points at the left and right sides
closest to the enforcement line. Then the enforcement system
only needs to check the image data captured by the camera
located at the same lane location, and the computing capacity
can be reduced.
We observe that the methods discussed in previous literatures
about improving the performance in violation enforcement
system still need to recognize all the image data. Human review
and correction is still needed to improve the identification
precision of ALPR. In contrast, our algorithm not only can
reduce the human loading but also can accurately identify all
non-payment vehicles.

Enforcement Line
Lane 1
Lane 2
Lane 3
Lane 4(x1, y1 , t1, v1)(x2, y2 , t2, v2)

Figure 4. Two location points to estimate the lane position.
B. System ModelIn this paper, we consider the MLFF ETC system andpropose a PT algorithm to identify all violations. As shown in
Fig. 5, the scenario of the road is a highway with 4-lanes. Thereis a RSU to provide the AVI service and transaction processing,and each lane is equipped with a camera at the enforcement line.
For PT algorithm, the primary step is to create a bipartite graph
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013

representation of the relation between license plate image data
and transaction data. The flow for creating a bipartite graph is
described as follows. Consider Fig. 5. A vehicle equipped withan OBU is driving on a highway. When the vehicle enters the
highway toll gate area identified by the RSU, the OBU can use
wireless communication to pay the toll to the RSU and then the
RSU sends the transaction data to the enforcement system. The
transaction data includes the time of transaction and license
plate ID information. When the vehicle passes through the gate,
the enforcement line will take a picture of the license plate inorder to get the license plate image data. At the same time, theenforcement system gets the speed of the vehicle and uses thetime of taking the picture (T1) to infer the times of entering (T2)and exiting (T3) the toll gate area. All the transaction data fromT2 to T3, said the possible matching targets, will be connectedto the image data. As the shown example in Fig. 5, there are fivetransaction data from T2 to T3. So the image data has fivepossible matching targets. In Fig. 6, for each image data, we canconnect it with the corresponding transaction data and then amaximum connected bipartite graph G(P∪T, E) is created,
where the set of vertices P represents image data, the set ofvertices T represents transaction data and the set of edges E
represents links between P and T.

T1

172

III. THE PT MATCHING ALGORITHM
Throughout this paper, we focus on an undirected graphwithout loops and follow [14] for graph theoretical definitions
and notations. Let G(V, E) be a graph and v∈V(G) be a vertex.
We use the notation N(v) and E(v) to denote the set of vertices
connected to v and the set of edges incident with v, respectively.
The cardinality |E(v)| is called the degree of v, denoted bydeg(v). Consider a maximum connected bipartite graph G(P∪T,
E) representing the relation between license plate image data
and transaction data. Then G(P∪T, E) has the following
properties:
Property 1. The number of vertices of the image data set P must
be greater or equal to the number of vertices of thetransaction data set T.
1.1 If |P| = |T|, all the vertices in P are legal
vehicles. The legal vehicle means that it
drives through the toll gate area with paying
for toll.
1.2 If |P| > |T|, there exists at least one illegal
vehicle in P without paying for toll.
Property 2. For a vertex v in P, if v is a legal vehicle, thetransaction data of v must be in N(v). It means thatthe transaction data of v is in the set of possible
matching targets of v.
Property 3. For a vertex v in P, if deg(v) = 0, v must be an
illegal vehicle.

RSU
T3
T1
Speed

T2
T1
Speed

Time5, ID5
Plate

T3

Time4, ID4

Image data

Time3, ID3
Time2, ID2
Time1, ID1

T2

Figure 5. An image data and the possible matching targets.
Time
00:00:14
00:00:1200:00:10
00:00:08

Photos(P)

Transactions(T)

Plate9Plate8
Plate7
Plate6
Plate500:00:06

Plate400:00:04

Plate300:00:02

Plate200:00:00

Plate1Figure 6. A bipartite graph representation of the relation
between image and transaction.

Property 4. For a vertex u in T, the image data of u must be inN(u).
Property 5. For a vertex u in T, if deg(u) = 1 and vertex v is the
only neighbor of u, v must be a legal vehicle and uis the transaction data of v.
Consider an example of a bipartite graph as shown in Fig.
7(a). The degree of the transaction data with the license plate ID
P01802 is one and Plate1 is the only neighbor. So Plate1 must bea legal vehicle and the other two edges adjacent to Plate1 can beignored. Using the same method, the transaction data with thelicense plate ID B00010 and A21787 also have degree one.
Hence we can say that plate2 is mapping to B00010 and plate3 ismapping to A21787. After removing irrelevant edges, thebipartite graph can be simplified as shown in Fig. 7(b).
Plate500:00:09, B13111

Plate400:00:06, A21787

Plate300:00:05, B00010

Plate2

Plate500:00:09, B13111

Plate400:00:06, A21787

Plate300:00:05, B00010

Plate200:00:04, P01802

Plate1(a)

00:00:04, P01802

Plate1(b)

Figure 7. (a) Initial bipartite graph.
(b) Removing irrelevant edges by Property 5.
According to the properties mentioned above, a
Photograph-to-Transaction matching algorithm is proposed for
determining the non-payment vehicles in MLFF system. Fig. 8
shows the execution of each step of the algorithm. The main

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013

spirit of the algorithm here is the use of Property 1. When thenumber of vertices of the image data set is equal to the numberof vertices of the transaction data set, it can determine all theimage data are legal vehicles quickly and reduce the number ofimage recognitions. On the other hand, if the number of image
data is greater to the number of the transaction data, there exists
at least one illegal vehicle in image data set. In this case, theimage recognition processing can make that the two sets havethe same number of vertices or disconnect the bipartite graphinto several disjoint components. For each component, it isrecursive and used as the input of the algorithm.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Input: a maximum connected bipartite graph G(P∪T, E).
Output: two sets of illegal vehicles and legal vehicles.
Input (G(P∪T, E)) {If |P| = |T|move u into the set of legal vehicles, ∀u∈P;
exit;
If |P| = 1 and |T| = 0
move u into the set of illegal vehicles, where u∈P;
exit;
run Check_Degree_One_Vertices_In_T;
If G is disconnected and has G1, G2, …, Gn components∀Gi, Input(Gi(Pi∪Ti, Ei)), i = 1, 2, …, n;else {
while (G is connected and G is not empty) {take the middle node u∈P;
Image_Recognition(u);If (License_check(u) = true)
move u into the set of legal vehicles;
else {
move u into the set of illegal vehicles;
If |P| = |T|move u into the set of legal vehicles, ∀u∈P;
exit;}
run Check_Degree_One_Vertices_In_T;}
If G is not empty and has G1, G2, …, Gn components∀Gi, Input(Gi(Pi∪Ti, Ei)), i = 1, 2, …, n;}}illegal vehicles.
− line 10: Run the Check_Degree_One_Vertices_In_T
function. By Property 5, for a vertex in transaction data set
with degree one, the only neighbor of this vertex must be
legal and can be moved to the set of legal vehicles.
− line 11 ~ line 12: If G is disconnected and has somecomponents after the steps above, the components can berecursive and used as the input of the algorithm.
− line 13 ~ line 29: Use the image recognition processing
repeatedly until the two sets of image data and transaction
data have the same number of vertices or G is disconnected.
Now we take two examples to explain how the PT Algorithm
can reduce the count of executing ALPR. Consider Fig. 9. The
set of image data has nine vertices and the set of transaction data
has eight vertices. By Property 1.2, there exists one illegal
vehicle in P. To find the illegal vehicle, we take the middle
vertex plate5 of the set P to execute ALPR first and the result is
A21787. As shown in Fig. 9(a), we can find that the transaction
data of plate5 is in its possible matching targets. So plate5 is alegal vehicle. Next, we remove plate5 from the set P and thetransaction data with the license plate ID A21787 from the set T.
After removing the two vertices, the bipartite graph is stillconnected and the number of vertices of the image data set isstill greater than the number of vertices of the transaction data
set. So we take the middle vertex plate4 of the set P to execute
ALPR again and the result is B01610 as shown in Fig. 9(b). In
this time, we can not find the transaction data of plate4 in its
possible matching targets. So plate4 is an illegal vehicle and canbe removed from the set P. Now, we can see that the two sets
have same number of vertices. By Property 1.1, all the vertices
in set P are legal vehicles. In this example, the system performs
only twice ALPR to identify which vehicles are legal or illegal.
Photos(P)

Transaction(T)

Photos(P)

Transaction(T)plate900:00:14, P01802

plate900:00:14, P01802

plate8The details are described as follows.
− line 1 and 2: Explain the input and output.
− line 3: The input is a maximum connected bipartite graph
G(P∪T, E)− line 4 ~ line 6: Apply Property 1.1 to check whether thenumber of vertices of image data set is equal to the numberof vertices of transaction data set or not. If agree, all image
data are legal and moved to the set of legal vehicles.
− line 7 ~ line 9: Apply Property 3 to check whether thenumber of vertices of image data set is equal to one and thenumber of vertices of transaction data set is equal to zero. If
agree, the only image data is illegal and moved to the set ofplate800:00:13, H11171

plate7plate600:00:13, H11171

plate700:00:10, B13213

00:00:10, B13213

plate600:00:09, H29175

00:00:09, H29175

00:00:07, A21787
plate400:00:05, A21227

plate300:00:02, B13111

plate200:00:01, B00010

plate1Figure 8. The Photograph-to-Transaction matching algorithm.

173

X

00:00:05, A21227
plate300:00:02, B13111

plate200:00:01, B00010

plate1(a)(b)

Figure 9. (a) Plate5 is recognized as legal.
(b) Plate4 is recognized as illegal.
Consider another example shown in Fig. 10. We assume thatthe vertex B01610 is legal. After removing B01610 from the set
P and the transaction data with the license plate ID B01610 fromthe set T, the bipartite graph is disconnected as shown in Fig.
10(b). There are two components with four and three vertices,
respectively. By Property 1.1, all the vertices in the subgraphwith four vertices are legal. On the other hand, the subgraphwith three vertexes exists one illegal vehicle by Property 1.2.
The components can be recursive and used as the input of the
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013

algorithm to find remain illegal vehicle.
Photos(P)

Transaction(T)

Photos(P)

Transaction(T)plate900:00:14, P01802

plate900:00:14, P01802

plate800:00:13, H11171

plate700:00:10, B13213

plate600:00:09, H29175

plate800:00:13, H11171

plate700:00:10, B13213

plate600:00:09, H29175

174

blue vertex is finished at the left side. Since the transaction timeof the blue vertex is 00:00:05, the time of taking the picture must
be after 00:00:05, and therefore the blue vertex is only
connected to plate5. Using the same method, the time of taking
pictures of the red vertices transacting at the right side must be
before 00:00:01 and 00:00:03, respectively. Therefore, thedegree of red vertices can be decreased as shown in Fig. 12(b).

(a)
00:00:05, B01610
plate300:00:02, B13111

plate200:00:01, B00010

plate1plate3

Plate 500:00:04

Plate 400:00:01, B00010

plate1(b)

00:00:03

Plate 3Figure 10. (a) B01610 is legal.
(b) Remain two bipartite subgraphs.

00:00:02

Plate 200:00:01

Plate 1

IV. SIMULATION RESULTS
A. Simplify Bipartite Graph
Before showing the simulation results, we first introduce two
methods to simplify the bipartite graph in order to improve theperformance of our algorithm. Since the speed of vehicles
driving in the congested traffic environment is lower than the
speed in the normal or sparse environment, the number ofvehicles staying in the toll gate area will be increased. It meansthat the degree of each image data in the bipartite graph createdbased on the congested environment will be higher. In order todecrease the degree and simplify the bipartite graph, we assume
the vehicle would report their location information when the
tolling transaction is finished. According to the location
information, the enforcement system can determine whether the
tolling transaction is finished before the time of taking picture ornot. As shown in Fig. 11, there are two types of vehicles paidroad-user charges in the toll gate area. One finishes the tollingtransaction at the left side of the enforcement line, and the otherat the right side.
Enforcement Line

Charged before theenforcement line
Charged after theenforcement line

Figure 11. Two types of paid vehicles.
For the vehicles at the left side, the time of image data mustoccur after the time of transaction data; in the same way, thetime of image data must occur before the time of transaction
data at the right side. According to above characteristics, theunnecessary edges of each image data can be eliminated andfurther the bipartite graph will be simplified. Consider an
example as shown in Fig. 12, the red vertices are the transaction
data finished at the right side of the enforcement line and the

00:00:05

Plate 500:00:04

Plate 400:00:03 00:00:03

Plate 300:00:02

Plate 200:00:01

Plate 1

00:00:05

00:00:02, B13111

plate2(a)

00:00:05(b)

00:00:01

00:00:05

00:00:03

00:00:01

Figure 12. (a) Initial graph.
(b) After eliminate the unnecessary edges.
In addition to the location information of transaction data, wecan apply the lane prediction technique [18] as shown in Fig. 4
to estimate the lane ID where the vehicles are taken pictures at.
Then the image data and transaction data can be classified by
the lane ID. The number of lanes is four, for example, we candivide the original bipartite graph into four subgraphs. This
would eliminate the unnecessary edges and decrease the degreeof each vertex again. To simplify the bipartite graph would
decrease the number of ALPRs that can reduce the humanloading to find the illegal vehicles. The impact of the factor to
our algorithm will be investigated in simulation.
B. Simulation Environment
The simulation environment is described in this section. In[1], the mobility generator tool is a set of mobility scenario
generators including Random Waypoint model, Reference
Point Group Mobility model, Freeway mobility model andManhattan mobility model. The Freeway model is used in ouralgorithm to generate mobility scenario. The simulation
scenario is in a 4 km highway with four lanes. We conduct thesimulation using the ns-2 simulator [21] in three scenarios:
congested traffic, normal traffic and sparse traffic, and compare
the number of ALPRs of orginal bipartite graph and simplified
graphs, respectively. The main different parameters among
these scenarios are velocity, number of vehicles andacceleration. Table 1 shows the details.
Table 1. Simulation Parameters.
The Length of Highway
Number of lanes
Number of Vehicles
Velocity
Acceleration Speed
Simulation times
Transmission Range
Location of the camera
Location of the RSU

4 km
4 lanes[4410, 3286, 2519]
Vmax:[108, 80, 54]Km/h
Vmin:[90, 72, 36] Km/h[0.4, 0.8, 1.2]m/s2
1800s
100m
2000m
2000m

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013

Traffic Flow

In rush hour, the tolerance of the traffic flow in Taiwan ETC
is 2,210 vehicles per hour [20]. As shown in Fig. 13, themaximum traffic flow appears from 7 a.m. to 7 p.m., and it isalmost 8000 vehicles per hour for all lanes. Electronic tollcollection has been implemented in Taiwan for five years. The
proportion of illegal vehicles which are not equipped OBUs tototal traffic flow is shown in Fig. 14. In recent years, the average
error rate is closed to 0.06%. In our simulation, we utilized theerror rate from 0.06% to 3.0% in the three scenarios.

9000
8500
8000
7500
7000
6500
6000
5500
5000
4500
4000
3500
3000
2500
2000
1500
1000
500
0

Taishan

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Time

175

beginning of this section are named PCL and PCL+PL. The
simplified method related to the partition by the camera’s
location is PCL, and partition by the combination of thecamera’s location and lane ID is PCL+PL. We can observe thatin the worst case, the ratio of illegal vehicles is 3% and thenumber of ALPRs is almost close to the number of total vehicles
in origin. The reason is that our algorithm has to repeat the
ALPR step continuously until the number of vertices of theimage data set is equal to the number of vertices of thetransaction data, or the bipartite graph becomes disconnected.
In other words, it has to recognize a large number of image datato achieve the termination condition of the algorithm incongested traffic environment. On the other hand, the simplified
bipartite graphs can get better performance than origin. Using
PCL and PCL+PL methods, the numbers of ALPRs compared
to origin can be reduced by 15% and 60%, respectively. In the
bipartite graph simplified by PCL+PL, it is divided into four
subgraphs and each lane has its own independent bipartite graph.
So PCL+PL can get less number of ALPRs. Fig. 16 shows thenumber of ALPRs of each lane by utilizing PCL and PL.
Obviously, it gets larger when the error rate grows up. In Fig. 17,
it shows the distribution of the average degree of the threemethods. The average degree of original bipartite graph is morethan eight times the average of PCL+PL during 300s to 500s.
This claims that the degree is an impact factor for PT algorithm.

Figure 13. The traffic flow at Taishan Toll Station a day.

Total vehicles: 4410

http://211.79.135.72/volume/drawday.htm

OriginPCL

PCL+PL

2.0

2.5

3.0

0.16%

2007

2008

2009

2010

0.14%

Error rate

0.12%

Number of ALPRs

3500
3000
2500
2000
1500
1000
500
0.1%

0
0.0

0.08%

0.5

1.0

1.5

3.5

Ration of illegal vehicles (%)
0.06%

Figure 15. The number of ALPRs in congested traffic.

0.04%
350

Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nor Dec

MonthFigure 14. The proportion of illegal vehicles.
C. Result Analysis
In this section, we show the simulation results for the threetraffic models in terms of the number of ALPRs, and of the
distribution of average degree.
1) Congested Traffic Analysis： Fig. 15 shows the numberof ALPRs over different ratios of illegal vehicles and thenumber is increasing with the growing of the ratio. The origin
represents that the input of PT algorithm is the original bipartite
graph. The two simplified methods as mentioned in the300

Number of ALPRs

0.02%

250
200

lane1

150

lane2

100

lane3

50

lane4

0
0.1%

0.6%

1.2%

2.0%

3.0%

Error rate

Figure 16. The number of ALPRs of each lane in congested
traffic.

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013

176

Figure 17. The distribution of average degree in congested
traffic.

Figure 20. The distribution of average degree in normal traffic.

2) Normal Traffic Analysis： In Fig. 18, it shows that the
number of ALPRs of the origin is still half of the total vehicles inworst cast. But, compared with the congested traffic, the ratio
number of ALPRs is relatively small. By utilizing PCL and
PCL+PL methods, the numbers of ALPRs compared to origin
can be reduced by 23% and 80%, respectively. In Fig. 19, it
presents the number of ALPRs of each lane by utilizing
PCL+PL. The numbers in the worst case of normal traffic are
one-third to congested traffic. In Fig. 20, it shows the
distribution of the average degree of origin, PCL and PCL+PL.
In normal traffic, the average degree is half of the degrees incongested traffic. So the number of ALPRs required in PT
algorithm is relatively small.

3) Sparse Traffic Analysis： Fig. 21 shows the simulation
results in the sparse traffic environment. The number of ALPRs
is the smallest of three scenarios and it can be reduced by 36%
and 87% in the original bipartite graph simplified by PCL and
PCL+PL, respectively. Even in the worst case, only five percent
of image data need to perform ALPR in PCL+PL method. Since
the velocity is faster and the density is lower in the sparse traffic,
the degree of each vertex is small. Under this condition, thebipartite graph can more easily be disconnected. In Fig. 22, it
presents the number of APLRs of each lane under PCL with PL.
Compare to another two scenarios, The number is much lower.
In Fig. 23, it shows the distribution of the average degree per ten
seconds in the three methods. We observe that all the average
degrees in PCL+PL are smaller than five. So PT algorithm
doesn’t need to recognize many image data in order todisconnect the graph. On the other hand, the enforcement
system can create many smaller bipartite graphs in sparse traffic
environment, and some of them have exactly the same numbersof vertices of image data set and transaction data set. That is thereason why PT algorithm has a better efficiency in sparse traffic.

Total vehicles: 3286
Origin1800

PCL

PCL+PL

Number of ALPRs

1600
1400
1200
1000
800

Total vehicles: 2519

600
400

1200

OriginPCL

PCL+PL

2.0

2.5

3.0

0
0.0

0.5

1.0

1.5

2.0

2.5

3.0

3.5

Ration of illegal vehicles (%)

Figure 18. The number of ALPRs in normal traffic.
120

Number of ALPRs

200

1000
800
600
400
200

Number of ALPRs

100

0
0.0

80
lane1

60

lane2
lane3

40

lane4

0.5

1.0

1.5

3.5

Ration of illegal vehicles (%)

Figure 21. The number of ALPRs in sparse traffic.

20
0
0.1%

0.6%

1.2%

2.0%

3.0%

Error rate

Figure 19. The number of ALPRs of each lane in normal traffic.

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013

50
40

Number of ALPRs

45
35
30

lane1

25

lane2

20

lane3

15

lane4

10
5
0

0.1%

0.6%

1.2%

2.0%

3.0%

Error rate

Figure 22. The number of ALPRs of each lane in sparse traffic.

177

number of license plate recognitions such that human loading
can be reduced. The simulation results shows that the original
bipartite graph without simplifying, it has the worst
performance in the congested scenario. So we proposed two
methods, called PCL and PCL+PL, to simplify the bipartite
graph. PCL method is based on the location of transaction data
relative to enforcement line, and PCL+PL is based on the lane
location where images are captured by cameras. Simulation
results show that PCL+PL method has the best performance andthe size of degree is an important impact factor. Although oursearching method can reduce human loading, there is an
important limitation – camera modules must take pictures forevery vehicle passing through the enforcement line. How tosurmount this limitation is a worth investigation in the future.
REFERENCES

Figure 23. The distribution of average degree in sparse traffic.

4) The degree Analysis：Fig. 24 shows the number of degreein three scenarios with original graph and simplified graphs.
The number of degree is the most by exploiting original graph.
It seen to has closed number of degree by utilizing PL with PCL
in each scenario, but our simulation show the number of degree
in dense is ten times more than in sparse. This is because thenumber of vehicles in dense is much more than in sparse during
the same time period. In other words, it has to check as many asvertices so that the bipartite graph could be disconnected.
60

Number of degree50Congested
NormalSparse

40
30
20
10
0

OriginPCL

PCL+PL

Figure 24. The average number of degree in each scenario.

V. CONCLUSIONSIn this paper, we proposed a Photograph-to-Transaction
matching algorithm based on bipartite graph for the violation
enforcement of MLFF ETC system. Our algorithm canaccurately find all non-payment vehicles and decrease the[1] F. Bai, N. Sadagopan, and A. Helmy, “User Manual for IMPORTANT
Mobility Tool Generators in ns-2 Simulator,” University of Southern
California, February 2004.
[2] S. Biswas, R. Tatchikou, and F. Dion, “Vehicle-to-vehicle wirelesscommunication protocols for enhancing highway traffic safety,” IEEE
Communications Magazine, vol. 44, no. 1, pp. 74-82, 2006.
[3] W. Du and W. Chen, “ETC development pushes combination of RFID and
ITS,” 13th International Conference on Advanced Communication
Technology (ICACT), pp.1515-1518, 2011.
[4] Z. Feng, Y. Zhu, P. Xue and M. Li, “Design and realization of expressway
vehicle path recognition and ETC system based on RFID,” 3rd IEEE
International Conference on Computer Science and Information
Technology (ICCSIT), vol. 7, pp.86-90, 2010.
[5] W.H. Lee, B.S. Jeng, S.S. Tseng, and C.H. Wang, “Electronic toll collection
based on vehicle-positioning system techniques,” in: Proc. 2004 IEEE
Int. Conf. Networking, Sensing, and Control, pp. 643-648, 2004.
[6] W.H. Lee, S.S. Tseng, and C.H. Wang, “Design and Implementation ofElectronic Toll Collection System Based on Vehicle Positioning System
Techniques,” Computer Communications, vol. 31, no. 12, pp.
2925–2933, 2008.
[7] Y. Li, L. Jiang, Y. Yin, F. Liu, H. Yu and Z. Ji, “System optimization of a 5.8
GHz ETC receiver using Memetic algorithm,” 2011 IEEE Workshop on
Memetic Computing (MC), pp. 1-5, 2011.
[8] D.W. Lim and J.S. Jun, “Free-flow multi-lane ETC system using real-time
individual vehicle tracking,” in Proc. 5th Asia-Pacific Intelligent
Transportation System (ITS) Forum, Seoul, Korea, pp. TS1-TS3, 2002.
[9] M.A.S. Mustafa, M. Pitsiava-Latinopoulou, and G..A. Giannopoulos, “The
multilane electronic toll collection system in Thessaloniki: Evaluationof its first 6 months of operation,” in Proc. IEEE Vehicle Navigation
and Information Systems Conf., pp. 699–703, 1994.
[10] W.Y. Shieh, W.H. Lee, S.L. Tung, and C.D. Ho, “A Novel Architecture
for Multilane-Free-Flow Electronic-Toll-Collection Systems in theMillimeter-Wave Range,” IEEE Trans. Intell. Transp. Systems, vol. 6,
no. 3, pp. 294–301, Sep. 2005.
[11] W.Y. Shieh, W.H. Lee, S.L. Tung, B.S. Jeng, and C.H. Liu, “Analysis of
the optimum configuration of roadside units and onboard units indedicated short-range communication systems,” IEEE Trans. Intell.
Transp. Systems, vol. 7, no. 4, pp. 565-571, 2006.
[12] C. M. Walker and W. K. Brockelsby, “Automatic Vehicle Identification(AVI) technology design considerations for highway applications,” inProc. 41st IEEE Vehicular Technology Conf., Gateway to the Future
Technology in Motion, pp. 805–811, 1991.
[13] W. Wang, Y. Zhang, W. Yao and S. Wang, “The propagation model of
RFID systems in ETC,” 2009 IEEE International Conference on
Communications Technology and Applications (ICCTA), pp. 54-57,
2009.
[14] D.B. West, Introduction to Graph Theory, Prentice Hall, 2001.
[15] Z.H. Xiao, Z.G. Guan, and Z.H. Zheng, “The Research and Developmentof the Highway's Electronic Toll Collection System,” International
Workshop on Knowledge Discovery and Data Mining, pp. 359-362,
2008.

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013178[16] Bertrand, Jean and Dicko, Mamadou, “Method and device forclassifying vehicles,” U.S. Patent, NO. 20030163263.
[17] Chunghwa Telecom, “A Multiple Experts Style for Multilane Free Flow
Electronic Toll Collection Systems,” Republic of China (Taiwan) Patent
Application, NO. 200415528.
[18] Chunghwa Telecom, “A Method for Improving the Success Rate ofAutomatic Matching Operation for Transaction Data and Enforcement
Data in Electronic Toll Collection Based on Vehicle Positioning
System,” Republic of China (Taiwan) Patent Application, NO.
200839652.
[19] L. Armstrong, “Dedicated Short Range Communications (DSRC),”[Online]. Available:
http://www.leearmstrong.com/dsrc/DSRCHome.htm[20] (2011) Taiwan Area National Freeway Bureau. [Online]. Available:
http://www.freeway.gov.tw[21] (2011) The network simulator: NS-2. [Online]. Available:
http://www.isi.edu/nsnam/ns/

Guo-Huang Hsu received the BS degree in electronicengineering from National United University, Taiwan,
Republic of China, in 2002, and the MS and PhD
degrees in computer and information science from
National Chiao Tung University, Taiwan, Republic ofChina, in 2004 and 2009, respectively. He is currently anengineer in the Information and Communication
Research Laboratories of Industrial Technology
Research Institute. His research interests include
telematics, interconnection networks, analysis algorithms, and graph theory.
Liang-Rui Lin received the BS degree in Department ofComputer Science and Information Engineering from
National Taiwan Normal University, Taiwan, Republicof China, in 2009 and the MS degree in computer andinformation science from National Chiao Tung
University, Taiwan, Republic of China, in 2011,
respectively. He is currently an assistant Clerk in Data
Communications Business Group of Chunghwa
Telecom.
Rong-Hong Jan received the B.S. and M.S. degrees inIndustrial Engineering, and the Ph.D. degree in
Computer Science from National TsingHua University,
Hsinchu, Taiwan, in 1979, 1983, and 1987, respectively.
He joined the Department of Computer Science,
National Chiao Tung University, in 1987, where he iscurrently a Professor. During 1991-1992, he was a
Visiting Associate Professor in the Department ofComputer Science, University of Maryland, College
Park, MD. His research interests include wireless networks, mobile computing,
distributed systems, network security, and network reliability.
Chien Chen received his B.S degree in Computer
Engineering from National Chiao Tung University in1982 and the M.S. and Ph.D. degrees in Computer
Engineering from University of Southern California andStevens Institute of Technologies in 1990 and 1996. Dr
Chen hold a Chief Architect and Director of Switch
Architecture position in Terapower Inc., which is aterabit switching fabric SoC startup in San Jose, before
joining National Chiao Tung University as an AssistantProfessor in August 2002. Prior to joining Terapower Inc., he is a key member
in Coree Network, responsible for a next-generation IP/MPLS switch
architecture design. He joined Lucent Technologies, Bell Labs, NJ, in 1996 as a
Member of Technical Staff, where he led the research in the area of ATM/IP
switch fabric design, traffic management, and traffic engineering. His current
research interests include vehicular ad-hoc networks, content-centric networks,
and cloud computing.

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013179

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013162

Radio Frequency Identification Networks
Planning Using a New Hybrid Evolutionary
Algorithm
Han Feng, Jie Qi
College of Information Science and Technology, Donghua University, Shanghai, China
fh-1@163.com, jieqi@dhu.edu.cn
Abstract—The problem of choosing the optimum locations andthe associated parameters of readers in RFID communication
systems is considered. All these choices must satisfy a set ofobjectives, such as tag coverage, load balance, economic
efficiency, and interference in order to obtain accurate andreliable network planning. In this paper, a novel optimization
algorithm, namely the multi-community GA-PSO, is proposed tosolve the complicated RFID network planning problem oflarge-scale system. The main idea of the algorithm is to divide thesingle population of the canonical PSO into multi-swarm and use
the genetic selection and mutation strategy to improve particle
swarm dynamic rules. The simulation results show that the
proposed algorithm obtains the superior solution for networking
planning problem than canonical PSO does.
Index Terms—Evolutionary computation, Particle swarm
optimization, Radiofrequency identification

I. INTRODUCTION

R

adio Frequency Identification (RFID) as a short-range
radio technology for automated data collection is
becoming an integral part of our life. The technology is in theascendant with a concerted effort in recent years to make afurther development. Nowadays, an enormous amount oftechnical and commercial development of RFID has been
demonstrated in many industrial applications, such as
production automation, anti-theft of merchandises, supply
chain management, access control and asset tracking [1]-[2].
The RFID systems consist of two types of devices:
unsophisticated, chip, and uniquely-identifiable tags and more
powerful electromagnetic readers. RFID interrogators orreaders ‘senses’ the unique identifier and other information
stored in RF tags affixed to objects by actively transmitting asignal to communicate with the RF tags [3].
In many applications, the deployment of RFID systems has
generated the RFID network planning (RNP) problem thatneeds to be solved in order to operate the large-scale network of
RFID readers in an optimal fashion [4]. However, RNP is one

Manuscript received June 29, 2012. This work was supported by the “China
National Natural Science Foundation Key Program No. 61134009 and by the“China Fundamental Research Funds for the Central Universities”.
Han Feng was with College of information sciences and technology,
Donghua University, China (e-mail: fh-1@163.com).
Jie Qi is with College of information sciences and technology, Donghua
University, China (corresponding author phone: +8621-67792312; fax:
+86216779-800; e-mail: jieqi@ dhu.edu.cn).

of the most challenging problems that has to meet manyrequires of the RFID systems. In general, the RNP aims tooptimize a set of objectives (coverage, load balance, economic
efficiency and interference between readers) simultaneously byadjusting the control variables (the coordinates of the readers,
the number of the readers, and the antenna parameters, etc.) of
the system [5]. As other wireless communication systems, thenetwork planning is a nonlinear optimization problem and has
aroused many researcher’ interest. Recently, many studies havebeen carried out and a large number of approaches have appliedin the literature. In [6]-[7], the method for optimal placement ofreaders is proposed mainly based on the coverage constraint.
The work in [8] focuses on the scheduling problem in which theheuristic algorithm is used to solve the interference problem. A
load balance problem is rigorously researched in [9] and theminimum multiprocessor scheduling (MMS) algorithm and the
maximum network flow (MNF) algorithm is used to solve theload balance problem. In [10], the authors combine the main
constraints to propose a combined measure to present an overall
optimal solution for the RNP problem.
For the possible combination of RFID reader positions are
too numerous, the exhaustive optimization of the nonlinear
optimization problem demands an impractically tremendous
computational effort which leads to the application of theheuristic algorithm in the filed. The particle swarm
optimization and genetic algorithm usually work in a
population which search around the solution space by some
operators until finding the optimal solution. However, in nature,
the common feature of many social networks is community
structure, the tendency for individuals to divide into groups,
with dense connections within groups and only sparser
connections between them [11]. A number of recent results
suggest that networks can have properties at the community
level that are quite different from their properties at the level ofthe entire network, so that analyses that focus on wholenetworks and ignore the community structure may miss many
interesting features [12]. Indeed, in biological populations there
is a continuous interplay between individuals of the same
species, and also encounters and interactions of various kindsof with other species [13]. Inspired by the community structure
cluster phenomenon, we extend the single population to theinteracting multi-community structure in the heuristic
algorithm and combined the genetic strategy and particle
swarm dynamic rules to propose a multi-community GA-PSO
algorithm. Then the algorithm is applied into the RNP problem
compared with canonical PSO to validate the effectively of the
proposed method.
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013180

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013

163

An outline of this paper is as follows. In Section II, theformulation model for the network planning in RFID networks
is introduced. Section III gives brief reviews of the canonical
PSO and the genetic algorithm and then presents the proposed
multi-community GA-PSO algorithm in details. In Section IV
and Section V, the proposed solution procedures for solving the
RNP problem using multi-community GA-PSO algorithm ispresented. In Section IV, the propagation pattern of reader iscircle and in Section V the propagation pattern of reader is
ellipse and corresponding simulation results in two different
propagation pattern are illustrated. Finally, in Section VI
concluding remarks are stated and ideas are proposed forfurther research.
II. RFID NETWORK PLANNING PROBLEM FORMULATIONIn this section, the formulation and some basic elements for
RFID network planning are presents. This model simplifies thecomplexity of spatial transmission of electromagnetic waves.
The up-link signal constraint, which ask for the backscattersignals reflected by tags must be received by a reader, isreasonably omitted by increasing the signal threshold size.

C. Coverage
In the RNP optimization problem, the first objective function
represents the level of coverage, which is most important in the
RFID systems. For that if any large amount of tags cannot beread by any reader, the RFID systems will be no practical use.
Before define the coverage constraint and other constraints, aswell as to define the mathematical formulation for optimization,some basic notations are formulated:• Rq : received power threshold guaranteed reader-to-tag
communication•Pr, t: the field strength received at a tag t from a reader r•

ST : set of all tags in the working area•

SR: set of the reader serving the area•

Cv(r): the set of tags served by reader r, which is defined[4] as:Cv (r ) = {t ∈ ST Pr , t ≥ Rq , ∀r '∈ SR, r ' ≠ r ,(3)
Pr ,t ≥ Pr ',t }Then the constraint can be formally expressed by thefollowing formula equations:(4)
ST = ∪ C v ( r )A. Propagation Modelr∈SR
In order to calculate the signal strength at each tag, a radio
In
order
to
defineameasureto facility the calculation, thewave propagation model is needed. Such a model is used toisdefinedasfollow:functionf
1
compute the propagation loss of an electromagnetic field(5)max
f1 = N cov erag / ST
between a reader and a tag. In many cases, RFID is used in anindoor environment such as production management andwhere Ncoverage is the number of tags covered by all readers,anti-theft of merchandises. In this paper, the propagation model |ST| is the number of total tags which is used to normalize
on indoor communications [4], [14] is employed:
performance indicators.
(1)
Ptag = Preader − L[dB]
D. Interference(2)
L = 10 log[( 4π λ ) 2 d n Greader Gtag ] + α [dB ]Reader interference mainly occurs in a dense reader
Where Ptag is the power output by the RFID reader, L is the environment, where several readers try to interrogate tags at the
propagation loss considering multipath fading, n is between 1.5 same time which will result in an unacceptable level ofand 3, αis about 10dB in the worst case and Gread and Gtag are misreads. The reasonable planning of networks will reduce theinterferences and improve the Quality of Service. In order toreader antenna gain and tag antenna gain respectively [4].
estimate the interference level, each tag’s best service reader
B. Readers and Tags
should be predicted. Thus, for a tag, the sum of received signals
In RFID systems, the RFID readers communicate with the which are less than Cdr, t , which represents the best signal
tags by reading/writing the information stored on them. In most received at a given tag t covered by the reader r, and greatercases, the tags are passive and low functionality which means than the required sensitivity threshold Sm can stand forthe tags receive power from a reader to operate and then interference in a certain sense [4]. Hence, the interference leveltransmit the backscatter signal to the reader. However, the at tag t is given by:reader has a limit on its interrogation range. If the radio signal(6)
γ (t ) = ( Pr ',t − Sm ), Cd r ,t ≥ Pr ',t ≥ Sm
received at a tag is higher than a quality threshold, noted Rq
The objective of minimizing the total amount of
hereafter, then the communication between the reader and tag
interferences
can be expressed as follows:
can be established. For the power needed for a tag transmitting(7)
max f 2 = ∑t∈ST (Cd r ,t (Cd r ,t + γ (t ))) ST
the backscatter signal back to the reader is taken from thereceived power, the threshold in this discussion is reasonably
It is the optimal condition when f2 equals to 1, in that case theset higher than the rated value which is dependent on the type of interference level returns to zero.
RF tags considered and carrier frequency.
As for the reader, we take the power-adjustable antenna to E. Load Balance
For various performance measures, it is important to design
make the optimization problem more flexible. The emitted
power is adjusted by the attenuation. In this paper, the problem effective load balancing schemes for distributing tags among
only concerns the variables of the position and radiated power readers as evenly as possible [5]. In [9], the author formulatedof the RFID readers serving the working area.
the planning problem into a bipartite graph G=(U ∪ V,E),
where U equals to SR and V denotes the set of tags, equivalent
to ST defined before, E donates the set of edges between reader∑

Copyright ⓒ GiRI (Global IT Research Institute)

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

181

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013164

and tag if and only if they can communicate with each other.
Each edge has a non-negative energy cost ci,j representing theenergy cost of reader ri to read tag tj once. Then the problem
definitions in [9] is to find an assignment φ:V→U of each tag tj
to a reader ri =φ(tj) such that the maximum of the total energy
cost:
(8)
Ci = ∑ r =φ (t ) ci , jijover all readers is minimized. To simplify our discussion, theenergy cost has a fixed unit energy cost, namely ci,j=1, then theload balance constraint become:(9)minCi = ni
ni is the number of the tags assigned to reader ri. The
constraint, in other words, is to balance the number of tags
assigned to each readers as far as possible. For facilitating the
calculation and presenting the fitness function, some measures
have been proposed.
The mean square deviation method is to calculate thecovariance of the numbers of tags and the lower value indicatesthe higher equilibrium of the tags assignment. The formula is as
below:(10)
D( X ) = 1 SR × ∑ (ni − E (n)) 2
when the label distribution is uniform, this method canachieve minimum value. However, if the ni not equal to theaverage number of tag, or all reader are assigned the same
number of tags but equal to a small number, for instance 1, thevalue of D(X) also equal to zero. That is, the measurement only
can reflect the balance of tags assigned to reader, but can only
be used under the maximum coverage rate premise.
Also the product of ni is another approach, in that way, theindicator obtains maximum value if and only if in the situationthat equal distribution of the label. The formula is as below:(11)max
f = ∏ ni
However, this method has the shortcomings of hard to benormalized.
In information theory, entropy is a measure of theuncertainty associated with a random variable. Entropy is astate function of the system; it can be used to describe the stateof existence of a certain system, and its changes can also be
used to indicate the direction of the evolution of the system.
Since 1850 when Clausius put forward the second law ofthermodynamics and 1865 when he introduced the statefunction, entropy and accurately proved the principle ofentropy increase in mathematical terms, the concept of entropy
has been quickly extensified with swift extension to otherdisciplines, an extremely strong capability of its development
to many fields.
When studying the efficiency of communication system,
Shannon introduced the concept of information entropy basedon the basic concept of thermodynamics entropy [25], which
was defined as:(12)
S = −∑ Pi log Pi
Pi is the probability of the ith basic event. Here, entropy
reflects the degree of a certain "uncertainty" in the state of thesystem. And the entropy difference of system change provides
us with a message like this: RTIE is closely related to matter,energy and information conversion; entropy can be regarded as
an important variable for the description of the RTIE. For acomplex system such as the RTIE, entropy will not only reflect
its state, but also show its uniqueness [24].
Take the form of the information entropy function S, the loadbalance constraint measurement f3 is defined using the entropy
concept as follows:
SR
(13)
max
f = −∑ (ni ST ) ln(ni ST )i =1where |SR| is the number of total readers and |ST| is thenumber of total tags. The form of ni/|ST| takes the form of Pi ,the probability of ith basic event. To normalize themeasurement, the term ln(|SR|) is used and the performanceindicator is as below:
SR(14)
max f 3 = −∑ (ni ST ) ln(ni ST ) / ln( SR )i =1then the measurement can achieve maximum value 1 if andonly if each reader was assigned the same number of tags.
F. Combined Measures
The overall optimal solution for RNP is represented by alinear combination of the three objective functions:3(15)
max f = ∑ ωi f i ; ω1 + ω2 + ω3 = 1
i =1The weight values of each objective function can be flexible
varied to account for any specific situation.
III. MULTI-COMMUNITY GA-PSO
A. Basic Concepts of GA and PSO
Genetic algorithm is stochastic search procedures based on
the mechanics of natural selection, genetics, and evolution [15].
The individual, or chromosome, is a potential solution which
searches in the solution space by three operators - selection,
crossover and mutation to find the global best solution. Particle
swarm optimization is also a kind of algorithm to search for thebest solution by simulating the movement of birds flocking.
The particle, akin to the chromosome in GA, updates according
to the dynamic rules until the entire particles converge to the
optimal solution. However, both canonical PSO and GA both
operate in the same population, whereas in the natural world,social community structure is commonly existent in the
network [11] and interactions between groups of the same
species are easily observed. Inspired by the community
structure phenomenon, we extend the single population in theheuristic algorithm to the interacting multi-community
structure and propose multi-community GA-PSO.
B. The Hybrid Algorithm of Multi-community GA-PSO
Community organizational structures extensively emerge inmany biological, social, man-made engineering systems. In
these organizations, all the members are divided into somegroups, and it has been demonstrated that the hierarchicalstructure can be organized more efficiently and thus canaddress larger scale problem [16].
The multi-colony or multi-swarm PSO algorithm is
proposed by many researchers base on the concept of dividing
single population into many colonies and the individuals
cooperate with each other to achieve the global optimum
solution [5],[17]-[22]. The proposed method, however,simulates the mutation and selection phenomenon in nature
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013182

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013165

colony and adds the corresponding operator in the single
community to better mimic the natural laws of population.
In the proposed algorithm, the population is divided intosome communities. The individuals in the same community canshare information with each other and construct a fully
connected topology, and all the communities form a ring
topology, among which each community can exchange theglobal best solution found in adjacent group. The topology
schematic diagram is shown in Fig. 1.
In this case, each individual of the proposed model evolves
based on individual’s own cognition, social interaction withineach community and information exchanged from othercommunities. The main parameters and operators of the novel
GA-PSO algorithm are described as below.
1) Coding and Initialization: Coding cares about how torepresent the practical parameters of the optimization problem
into an individual. The novel algorithm adopts the floating
point coding scheme. At the beginning of the algorithm, all theindividuals in the population should be generated initially andare uniformly distributed random numbers in [Xmin ,Xmax],
where Xmin is the lower limitation of the particle position and
Xmax is the upper limitation. At the same time, the velocity ofthe particles should be initialized at first, within the limit of3) Selection Operator: In order to produce well-performing
individuals in the novel algorithm, the selection mechanism is
adopted in each group. In each generation, after the fitness
values of all the individuals in the same community arecalculated, the low half worst performing individuals aremarked out. Instead of replacing the worst-performing
individuals with the top-half well-performing individuals [23]in the same group, the paper only replaces the worst performing
one with the previous community’s global best position pgk(t-1)
in order to accelerate the convergence speed.
4) Mutation operator: In Multi-community GA-PSO,
mutation occurs after the velocity and position update operator.
Mutation is an operator derived from the mimic of biologicalgenetic breeding behaviour and by the operator, the appositionof an individual is altered randomly so that new genetic
materials can be introduced into the population. In the proposed
method, the mutation operator can be used to overcome thepremature convergence. Here, uniform mutation is adopted,
that is, the mutated gene is drawn randomly, uniformly from thecorresponding search iteration. In the following simulations, aconstant mutation Pm probability is used. The mutation operator
rests the individual’s position by re-initialized the position
randomly in the searching space. Compare with traditional
methods by which the individual adds a stochastic disturbanceto the original position, the method taken in the work issomehow a large scale operation in order to avoid thepremature phenomenon.

IV. CIRCULAR PROPAGATION MODEL SIMULATION

Fig. 1. The topology schematic diagram[Vmin ,Vmax].
2) PSO Updating Rule: In the proposed method, theindividual updates the position and velocity according to threeguides. The enhanced dynamic rules are formulated as:vik (t + 1) = ωvik (t ) + c1r1[ pik (t ) − xik (t )] + c2 r2 [ p gk (t )− xik (t )] + c3 r3 [ p gm (t ) − xik (t )]xik (t + 1) = xik (t ) + vik (t + 1)

(16)
(17)

where ω is the inertia weight; c1, c2 and c3 are the acceleration
constants with positive values; r1, r2 and r3 are uniformly
distributed random numbers in [0, 1]; the superscript in each
item represents the serial number of community and thesubscript indicates the label of individual in corresponding
community. The vector pik represents the individual’s best
position in history in its own community; pgk represents theglobal best position founded in kth community; pgm represents
the global best position founded in mth community, where kth
and mth community are adjacent.

In this section, multi-community GA-PSO is applied to the
RFID network planning problem compared with canonical
PSO. For RNP problems, the object is to place readers at thebest position while optimizing a set of objectives- coverage,
load balance and interference between readers simultaneously.
To demonstrate the superiority of the proposed algorithm, in
simulation, the performance of the proposed algorithm iscompared with the canonical PSO.
A. Simulation Scenario
The RFID planning working area is simulated by an idealsquare scene (25m×25m) with 80 tags, which are randomly
distributed in the working area. Ten radiated-power adjustable
RFID readers are considered to cover this working area. Fig. 2
shows the ideal square working area.
B. Parameter and Procedure

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013183

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013166

For Multi-community GA-PSO, all the individuals forming
the whole population should be randomly generated into ten
communities, and each community contains ten individuals
with random positions and velocities. Each individual in thealgorithm takes a floating point coding scheme and has adimension equal to 3×|SR|, in which the first 2×|SR| elementsin the individual vector indicate the coordinates of reader

Fig. 2. The square working area

positions, and the |SR| elements in vector dimensionalities forradiated powers of each reader. The inertial weight starts at 0.9
and linearly decreases to 0.4 with the increment of the iteration.
The acceleration constants c1, c2 and c3 are set to 1.494, themutation probability constant Pm is set to 0.1 and the maximal
epochs is 500.
Then the detailed procedures for this algorithm can besummarized as follows:• Step1. Initialize the positions and velocities of the whole
population of ten communities randomly and set
parameter values as described before.
• Step2. Evaluate each particle’s fitness value using (11)in each group then record each particle’s best position Pik.
Then calculate the global best position Pgk in each
community.
• Step3. The position and velocities of all the particles are
updated according to (16) and (17). If the new particle’s
position and velocity are beyond their respective
limitation, the value must be set as the nearest boundary.
• Step4. Based on the mutation strategy, each particle ineach community will mutate according to certain
probability Pm, and then produce the new population.
• Step5. Evaluate each new particle’s fitness value andcompare each individual’s new fitness value with theprevious best record. Then update the particle’s best
position and the global best position in each group.
• Step6. After the fitness values have been calculated, theworst performing individual in each community ismarked out. By selection operator, the worst performing
individual is replaced by the previous global best
position in its community with its current velocity andhistorical best position unchanged.
• Step7. If the maximal iterative generations are achieved,or the global best position’s fitness value has achieved thesetting precision, it is the ends of the algorithm, else, go to
Step 3.

To illustrate the effective of the new algorithm, traditional
PSO is used as a comparison. For PSO, the inertia weigh takes
the same dynamic value with the proposed algorithm, theacceleration constants c1 and c2 are set to 1.494, the population
size is 100, and the maximal epoch is 1000.
C. Simulation Result
The final network planning results found by two algorithms
is presented in Fig. 3 and the fitness of optimization process isshown in Fig. 4.
The red dotted line in Fig. 3 indicates the power threshold Rq,
and the plus symbol represents the coordination of each readers.
The electromagnetic field strength in the circle descends
according to the distance to the reader, however for clarity it issimplified, then the tag in the two circle sphere need to be
calculated the received power to determine which reader it
belongs to. From the comparison of Fig. 3-(a) and Fig. 3-(b),we can easily observe that the multi-community GA-PSO
algorithm can obtain a completely coverage that no tag isneglected by readers. In the dense regions of tags, the tags are
distributed to different readers in Fig. 3-(b) to satisfy the loadbalance constraints while in Fig. 3-(a) all the tags in the dense
region belong to one reader. The interference level, however,cannot deduce from the figure, for the power is not depicted in
the picture, but from further calculation the proposed method

(a)

(b)
Fig. 3. Experimental results (a) traditional PSO algorithm; (b) Multicommunity GA-PSO algorithm

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013184

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013167

RFID for reading and writing the spread of antenna modelroughly into an oval.
In short, the patch antenna of the RFID reader is directional,
considering the antenna in the plane of the cover, the coveragearea is not a round, so in the deployment of the antenna when
RFID can't cover simple with a round instead of, and need toconsider the direction of the antenna.

Fig. 4. Fitness curvealso achieves better performance.
Seen from the Fig. 4, the new algorithm is apparently better
than the traditional method. The novel algorithm can avoid
premature phenomenon while the searching is stagnated in
traditional PSO at early iteration. The novel algorithm can keep
the diversity of the population and achieve better fitness value,
provided verification for the optimized approach.
V. ELLIPSE PROPAGATION MODEL SIMULATIONThe reading range is one of the most critical performanceindicators of radio-frequency identification (RFID) systems. It
depends on many physical and geometrical parameters.
Typically, in the ultra-high-frequency band, the maximum sizeof the reading region is estimated by the free-space propagation
model. This is based on the Friis formula, even if much moreaccurate predictions may be accomplished nowadays bytime-consuming electromagnetic simulations, accounting forthe antennas and the interaction with the nearby environment[30].
In RFID system, the propagation pattern of RFID reader
antenna equal to the space electromagnetic field distribution
model of wireless antenna which in some research literature
known as identify region [26] .
The RFID reader antenna propagation model is determinedby many parameters: the reading and writing of the antenna
power, the antenna attenuation value, radio frequency band, tag
threshold power, etc. Although communication model
calculation is a complicated process, but once these parametersof the RFID system is known, it can through the ray tracing
method or the actual way of reading and writing tests todetermine the antenna to reading and writing the scope of thelabel.
The method to classify the pattern of the RFID reader isplenty of, but the most commonly used method is classifying
the pattern by its geometric shape and then the pattern isclassify into circle pattern and ellipse pattern.
In recently, the type of antenna in used is patch antennas,
also known as micro-strip antenna. According to antenna
theory, if take the main lobe of antenna signal as the effective
coverage areas, then antenna coverage is an approximate theelliptical shape [27-28]. In [29], the author through the antenna
electromagnetic field analysis and experimental way, verify the

A. Simulation Scenario and the Ellipse Model
In ellipse propagation pattern simulation, the RFID planningworking area is as same as the scene of the circle propagation
simulation as shown in Fig. 2.
To simplify the calculation process, the reader used in thesection is different from the previous ones. The reader has therange of interrogation in an ellipse shape, with fixed length oflong axis of 5m and fixed length of short axis of 4m. Thatmeans the power of the reader is not adjustable. Considering thedirection of the reader, while in the circle propagation the
direction make nothing different, then the dip angle of this type
is considered as a variable quantity to be optimum.
B. Parameter and Procedure
In the oval propagation pattern, all the individuals forming
the whole population should be randomly generated into ten
communities, and each community contains ten individuals
with random positions and velocities as like in the circle
simulation. However, the coding strategy is somehow different
from the former simulation.
Each individual in the ellipse simulation takes a floating
point coding scheme and has a dimension equal to 3×|SR|, inwhich the first 2 × |SR| elements in the individual vector
indicate the coordinates of reader positions, and the |SR|elements in vector dimensionalities for the of angle with thehorizontal direction of each reader. The angle is illustrated inFig. 5.

Fig. 5. The ellipse propagation pattern

Copyright ⓒ GiRI (Global IT Research Institute)

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

185

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013

168

The inertial weight starts at 0.9 and linearly decreases to 0.4
with the increment of the iteration. The acceleration constants
c1, c2 and c3 are set to 1.494, the mutation probability constant
Pm is set to 0.1 and the maximal epochs is 500. For the newmodel only change the propagation of RFID reader, theoptimum algorithm apparently will not be modified
C. The fitness value calculation
It is apparently that the fitness calculation is somehow ahandicap to solve. In this section, the simplified distribution
model of electromagnetic field is shown and the method to
calculate the fitness value is illustrated.
Coordinate rotation transformation
The propagation pattern is in ellipse shape that it is not easilysolvable in the circle pattern, in which the tags receive power
can be calculate by its distance from the reader. Any tag thathas the same distance to a reader must have the same receive
power. However, in ellipse model, two tags have the same
distance to a reader, one in the long axis direction while on in
the short axis direction, but the one in the short direction may
not be covered by the reader.
Considering the ellipse general equation may take large
amount of calculation, while in contrast the calculation of theposition of tag is easy to solve, then in this paper, whencalculate whether a tag is covered by a reader and the power bysimplified calculation, all the tags’ position are rotatedaccording to the angle of the ellipse.
Take an example for instance; individual in the algorithm has
a dimension equal to 3×|SR|, in which the first 2×|SR| elementsin the individual vector indicate the coordinates of reader
positions, and the |SR| elements in vector dimensionalities forradiated powers of each reader. That is the individual is in theform of [x1,y1,x2,y2,…,x9,y9,x10,y10,θ1,…,θ10]. Considering the
speed and position limit in PSO update rules, the angle ofreader variant is separated from its position [x, y] variants suchthat the individual updating rule is simplified.
Take the ith reader’s position xi and yi and the 20+i elementof the particle vector – the angle of the reader θi, for instance thei equal to one and the corresponding coordination and angle is[10, 15, 0.25π], then the ellipse is depicted in the area, as shownin Fig. 6.
Then process the coordinate rotation transformation andtranslation transform, then the area is shown in Fig. 7.
It is easily seen that the relative position of the reader andtags without change, the tags that in the coverage area are stillin the domain. But after the coordinate rotation transformation,
the coverage area is an ellipse standard equation as below:(18)
x2 a 2 + y 2 b2 = 1
where the length of the half long axis equal to 5m and thelength of the half short axis equal to 4m in this paper.
Coverage rate calculation
After the position transformation, the tags’ positions are in a
new coordination, but the node indicator does not change. Thenput node coordinates into the ellipse standard equation, if thecoverage rate, namely the f1, will be calculate by the numbers

Fig. 6. The reader position and angleof tags covered by ten readers divided by the total value lessthan or equal to one, the tag is covered by the reader.

Fig. 7. The coordinate rotation transformation

Do the process again for other nine readers, then the numberof tags. The detail description can be seen in Algorithm 1.
Algorithm 1 Coverage rate (CR) calculation
For i=1:1:10
Transformation (position); //transformation the tag position
Rotation (position);
For j=1:1:80
value = x 2 25 + y 2 16;
status (j,i)=value;
IF value<=1 THEN
coverage(j)=1;
END IF
END FOREND FOR
f1=sum(coverage)/80;
Load balance rate calculation need to know the number oftags a reader assigned. If a tag is covered by more than one
Copyright ⓒ GiRI (Global IT Research Institute)

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

186

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013169

reader, then the tag belongs to the reader which transmits themax power on it.
In the load balance calculation, put node coordinates into theellipse standard equation and calculate the value. If a tag has theminimum value from a reader, then the tag is assigned to thereader.
The detail description can be seen in Algorithm 2.
Algorithm 2 Load balance rate (LB) calculation
For i=1:1:10
Transformation (position); //transformation the tag position
Rotation (position);
For j=1:1:80
value = x 2 25 + y 2 16;
status (j,i)=value;
END FOREND FORFOR i=1:1:80[maxpower, indicator]=min( status(i,:) );IF maxpower<1 THEN
assign(pos)=assign(pos)+1;
END IF
END FORSET sum=0
FOR i=1:1:10
sum=sum-( assign(i)/80 )*log( assign(i)/80 )/log( 10 );END FOR
f3=sum;However, the calculation of interference level needs to know
the interference signal that other readers transmit on it. The
reasonable planning of networks will reduce the interferences
and improve the Quality of Service. In order to estimate theinterference level, each tag’s best service reader should be
predicted.
Similar to the load balance algorithm, the max power Cdr, t,
which represents the best signal received at a given tag tcovered by the reader r, can be determined by the value of
ellipse standard equation. However, the value can reflect thestrength of the power of the tag received by a reader, but it can
not directly be calculated as the signal. In this paper, thecalculation is simplified by considering the power inversely
proportional to the value. Under this assumption, the pseudocode of the algorithm is as blew:

IF temp(k)==0
temp(k)=0.01;
END
IF temp(k)>1
temp(k)=0;
ELSE temp(k)=1/temp(k);END
END
r_(i)=temp(indicator)/sum(temp);
END
SET sum=0
FOR i=1:1:80
sum=sum+ r_(i);END FOR
f3=sum/80;

D. Simulation Result
In the ellipse simulation, the weight values of each objectivefunction take the value of [0.7 0.1 0.2], then the fitness function
is defined as blew:(19)
f = 0.7 f1 + 0.1 f 2 + 0.2 f 3
The basic parameter in the ellipse simulation is similar to thecircle propagation simulation and the permissible error is set
0.01.
The final network planning results found by traditional PSO
and the multi-community GA-PSO is presented in Fig. 8 andthe optimization process is shown in Fig. 9.

(a)Algorithm 3 Interference rate (IR) calculation
For i=1:1:10
Transformation (position); //transformation the tag position
Rotation (position);
For j=1:1:80
value = x 2 25 + y 2 16;
status (j,i)=value;
END FOREND FORFOR i=1:1:80[maxpower, indicator]=min( status(i,:) );temp=status(i,:);FOR k=1:1:10
Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013187

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013170

mutation operator add new best individual to the population.
The novel algorithm can keep the diversity of the population
and achieve better fitness value, provided verification for the
optimized approach.
For testing the performance of GA-PSO, we use other ten
different patterns which are randomly generated in a
two-dimensional square scene (25m×25m) with 80 tags. The
simulation results are listed in Table I.
TABLE ISIMULATION RESULTS OF TEN DIFFERENT PATTERNSCANONICAL PSO
GA-PSO
No. ofpatterns
CR
LB
IR
CR
LB
IR
1
0.94
0.92
0.93
0.85
0.83
0.86
2
0.95
0.92
0.94
0.85
0.83
0.88
3
0.94
0.92
0.94
0.83
0.82
0.87
4
0.93
0.91
0.92
0.82
0.81
0.81
5
0.96
0.95
0.95
0.89
0.88
0.89
6
0.96
0.94
0.95
0.89
0.86
0.88
7
0.94
0.91
0.95
0.82
0.81
0.8
8
0.96
0.92
0.95
0.85
0.83
0.84
9
0.92
0.90
0.92
0.82
0.80
0.81
10
0.93
0.91
0.91
0.83
0.82
0.82

(b)
Fig. 8. Ellipse model simulation results (a) traditional PSO algorithm; (b)Multi- community GA-PSO algorithm

The red dotted line in Fig. 8 indicates the power threshold Rq,
and the plus symbol represents the coordination of each readers.
The electromagnetic field strength in the circle descends
according to the ellipse propagation model, however for clarity
it is simplified, then the tag in the two circle sphere need to be
calculated the received power to determine which reader it
belongs to. From the comparison of Fig. 8-(a) and Fig. 8-(b),we can easily observe that the multi-community GAPSO
algorithm can obtain a completely coverage that no tag isneglected by readers. In the dense regions of tags, the tags are
distributed to different readers in Fig. 8-(b) to satisfy the loadbalance constraints while in Fig. 8-(a) all the tags in the dense
region belong to one reader. The interference level, however,cannot deduce from the figure, for the power is not depicted in
the picture, but from further calculation the proposed method
also achieves better performance. Also seen from the upper
right corner of the region, the reader are clustered, theinterference level must be high.

In Table I, the abbreviations CR, LB and IR denote coverage
rate, load balance rate and interference rate, respectively. These
performance indexes are normalized so that the closer to 1, thebetter the values are. For each tag distribution pattern, the twoalgorithms run 10 times respectively, so Table I gives the meanvalues of the performance indexes averaging over 10 runs. It
shows that the GA-PSO algorithm finds better solution for allthese ten tags distributing patterns, which has better
performance indexes denoted by coverage rate, load balance
rate and interference rate than the canonical PSO dose.
VI. CONCLUSIONSIn this paper, an optimization model for planning theposition of readers in the RFID network is proposed. The RFID
network planning problem is a multi-objective nonlinear
optimization problem, and a multi-community GA-PSO
algorithm is presented to find the optimum configuration for
RFID readers deployment while satisfy coverage, interference
and network load balance Constraints.
Finally, although the simulation results show the novel
algorithm’s effectively, some comments on the future research
are given. The algorithm is a static algorithm which can only
apply for a certain sense, the propagation model can further be
consummated, and the way of setting parameters of the novel
algorithm needed to be considered and moreover the novel
algorithm remains to be examined for other complicatedoptimization problem.

Fig. 9. Fitness curve in ellipse model

Seen from the Fig. 9, the proposed algorithm is apparently
better than the traditional method. The novel algorithm can
avoid premature phenomenon while the searching is stagnatedin traditional PSO at early iteration. The climacteric of thefitness curve indicate the algorithm are stagnated by the

REFERENCES[1][2]

D. Park, Y. B. Choi, and K. C. Nam, “RFID-based RTLS for
improve-ment of operation system in container terminals,” in Proc.
Asia-Pacific Conf. Commun, 2006, pp. 1-5.
C. Decker, U. Kubach, and M. Beigl, “Revealing the retail black box byinteraction sensing,” In Proc. Int. Conf. Distributed Computing Systems,
2003, pp. 328.

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013188

ICACT Transactions on the Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013

171

[3]

K. Finkenzeller, RFID Handbook: Radio-Frequency Identification
Fundamentals and Applications, John Wiley & Sons Ltd., Hoboken, NJ,
1999.
[4] Q. Guan, Y. Liu, Y. P. Yang, and W. S. Yu, “Genetic approach for
network planning in the RFID systems,” in Proc. ISDA Sixth Int. Conf.
Intelligent Sys. Design Applic,2006,pp.567-572.
[5] H. N. Chen, Y. L. Zhu, K. Y. Hu, etc., “RFID network planning using a
multi-swarm optimize,” Journal of Network and Computer Applications,vol. 34, pp. 888–901, May. 2011..
[6] I. Bhattacharya, U. K. Roy, “Optimal placement of readers in an RFID
network using particle swarm optimization”, International Journal ofComputer Networks & Communications, vol.2, pp. 225-234, Nov. 2010.
[7] K. Ali, W. Alsalih, and H. Hassanein, “Set-Cover approximation
algorithms for load-aware readers placement in RFID networks”, in IEEE
Int Conf Commun, 2011, pp.1-6.
[8] C. Y. Chiu, C. H. Ke, K.Y. Chen, “Optimal RFID networks schedulingusing genetic algorithm and swarm intelligence”, in Conf. Proc. IEEE
Syst. Man Cybern, 2009, pp. 1201-1208.
[9] Q. Dongin, A. Shukla, V. Shrivastava, etc., “Load balancing inlarge-scale RFID systems”, Computer Networks, vol. 52, pp. 1782–1976,
June 2008.
[10] H. N. Chen, Y. L. Zhu, “RFID networks planning using evolutionary
algorithms and swarm intelligence” in Int. Conf. Wirel. Commun., Netw.
Mob. Comput., WiCOM, 2008, pp. 1-4.
[11] M. E. J. Newman, M. Girvan, “Finding and evaluating community
structure in networks”, Phys. Rev. E 69, 2004.
[12] M. E. J. Newman, “Finding community structure in networks using the
eigenvectors of matrices”, Phys. Rev. E 74, 2006.
[13] H. N. Chen, Y. L. Zhu, K. Y. Hu, “Multi-colony bacteria foraging
optimization with cell-to-cell communication for RFID network
planning”, Applied Soft Computing, vol. 10, pp.539–547, Mar. 2010.
[14] A. Toledo, A. Turkmani, and J. Parsons, “Estimating coverage of radiotransmission into and within buildings at 900, 1800, and 2300 MHz,” inProc. IEEE Pers Commun, 1998, pp. 40-47.
[15] D. E. Goldberg, Genetic Algorithm in Search Optimization and Machine
Learning, MA: Addison-Wesley, 1989.
[16] A. Arenas, A. Diaz-Guilera, C. J. Perez-Vicente, “Synchronization
reveals topological scales in complex networks,” Physical Review
Letters, vol. 96, Mar. 2006.
[17] J. J. Liang, P. N. Suganthanon, “Dynamic multi-swarm particle swarm
optimizer,” in Proc. IEEE Swarm Intell. Symp., 2005, pp. 127-132.
[18] T. Blackwell, J. Branke, “Multi-swarm optimization in dynamic
environments,” Applications of Evolutionary Computin, vol. 3005, pp.
489–500, 2004.
[19] R. Li, Y. R. Guo, Y. J. Xing and M. Li, “A novel multi-swarm particle
swarm optimization algorithm applied in active contour model,” in Proc.
WRI Global Congr. Intelligent Syst., GCIS, 2009, pp. 139-143.
[20] C. Y. Hu, X. N. Wu, Y. J. Wang and F. Q. Xie, “Multi-swarm particle
swarm optimizer with Cauchy mutation for dynamic optimization
problems” Advances in computation and intelligence, vol. 5821/2009, pp.
443–453, 2009[21] P. Ghosh, H. Zafar, “A linear array geometry synthesis with minimumside lobe level and null control using dynamic multi-swarm particle
swarm optimizer with local search,” Swarm, Evolutionary, and mimetic
computing., vol. 6466, pp. 701–708, 2010.
[22] B. Niu, Y. L. Zhu, X. X. He, H. Wu, “MCPSO: A multi-swarm
cooperative particle swarm optimizer,” Applied Mathematics andComputation, vol. 185, pp. 1050–1062, Feb. 2007.
[23] P. J. Angeline, “Evolutionary optimization versus particle swarm
optimization: Philosophy and performance differences,” in Proc. of the
7th Annual Conf. on Evolutionary Programming, 1998, pp. 601-610.
[24] Y.F.Luo, L.C.Huang, "The Concept of Entropy and the Performance
Entropy of Regional Technological Innovation Ecosystem," Proc. Int.
Conf. Manage. Sci. Eng. ICMSE, 20-22 Aug. 2007.
[25] Y. D. Zhu, Z .Y. Gao, "The Study on Soot-Blowing Optimization Basedon Theory of Specific Entropy Generation," Power and Energy
Engineering Conference, 2009. APPEEC 2009. Asia-Pacific , vol., no.,pp.1-5, 27-31 March 2009.
[26] E. D. Giampaolo, G. Marrocco. "RFID Read-region Models in Real
Environments".In:3rd European Conference on Antennas andPropagation. 2009. 3269-3273[27] Y. Huang, K. Boyle. Antennas: From Theory to Practice. Wiley 2008[28] A. Donev. "Improving the Density of Jammed Disordered Packings using
Ellipsoids". Science, 2004, 303:990-993.

[29] E. D. Giampaolo, F. Fornì, G. Marrocco. "RFID-network planning by
Particle Swarm Optimization. In: Proceedings of the Fourth European
Conference on Antennas and Propagation. Barcelona Spain:2010. 1-5.
[30] G. Marrocco, G. D. Giampaolo, R. Aliberti, "Estimation of UHF RFID
Reading Regions in Real Environments," Antennas and Propagation
Magazine, IEEE , vol.51, no.6, pp.44-57, Dec. 2009
Han Feng received the B.E. degree in automation from
Shandong Polytechnic University, Jinan, China, in2006.
Nowadays, He is a graduate student in Donghua
University majored in pattern recognition and intelligent
systems. His research is in intelligent optimization
methods and its application.

Jie Qi is now an associate professor of Donghua
University, China. She got her PhD degree of Systems
Engineering at Northeastern University China in 2005.
She visited The Hong Kong Polytechnic University for
program research from 2007.3 to 2008.3. She will visit
University of California, San Diego on 2013. 3
The current research interests are intelligent
optimization methods, RFID system and its applicationin supply chain and the control systems and dynamics.

Copyright ⓒ GiRI (Global IT Research Institute)

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

189

Ontology-based Multimedia Contents Retrieval
Framework in Smart TV Environment
Moohun Lee*, Joonmyun Cho*, Jeongju Yoo*, Jinwoo Hong**Next Generation SmartTV Research Department,
ETRI (Electronics and Telecommunications Research Institute), Korea
leemh@etri.re.kr, jmcho@etri.re.kr, jjyoo@etri.re.kr, jwhong@etri.re.kr
Abstract—Semantic search promises to provide more accurate
result than present-day keyword matching-based search by using
the knowledge represented logically (i.e., knowledge base). But,
the ordinary users don’t know well the complex formal querylanguage and schema of the knowledge base. So, the system shouldinterpret the meaning of user’s keywords. Such requirements areconspicuous especially in smart media such as smart phone, IPTV
and smart TV. In this paper, we describe a framework for thesemantic retrieval of multimedia contents. Our framework is
ontological knowledge base-driven in the sense that theinterpretation process is integrated into a unified structure arounda knowledge base, which is built on domain ontologies. Our
framework also integrates such components as for knowledge baseaugmentation by user preference and context. We also present our
prototype system we have been developing to test our frameworkideas.
Keyword—Knowledge Base, Ontology, Semantic Search, Smart
TV

I. INTRODUCTIONW

E are witnessing the last few years rapid increasing ofsmart media such as smart phone, tablet PC and smart TV.
Especially, smart TV equipped with a processor, large
inexpensive disk storage, and high-speed Internet access ispredicted to be an open home digital hub in the near future [1].
In the line of such movement, digital audiovisual content
libraries and video on demand services are already making
business in the market. Furthermore, the business will be
Manuscript received June 29, 2012. This work was supported by the ETRI
R&D Program of KCC(Korea Communications Commission), Korea[11921-03001, “Development of Beyond Smart TV Technology”].
Moohun Lee is with the Next Generation SmartTV Research Department,
ETRI, 218 Gajeongno, Yuseong-gu, Daejeon, Rep. of Korea (corresponding
author to provide phone: 82-42-860-1826; fax: 82-42-860-6202; e-mail:leemh@etri.re.kr).
Joonmyun Cho is with the Next Generation SmartTV Research Department,
ETRI, 218 Gajeongno, Yuseong-gu, Daejeon, Rep. of Korea (e-mail:jmcho@etri.re.kr).
Jeongju Yoo is with the Next Generation SmartTV Research Department,
ETRI, 218 Gajeongno, Yuseong-gu, Daejeon, Rep. of Korea (e-mail:jjyoo@etri.re.kr).
Jinwoo Hong is with the Next Generation SmartTV Research Department,
ETRI, 218 Gajeongno, Yuseong-gu, Daejeon, Rep. of Korea (e-mail:jwhong@etri.re.kr).

expanded to the broadcasting contents by real-time program
capturing and streaming capabilities [2].
Recently, the advanced technology of contents retrieval
becomes a dominant factor for the success of such business[1,3,4]. For example, users want to easily search for contents
regardless of the sources (i.e. repositories) such as digitalcontents libraries, VoD(Video on Demand) services, andbroadcasting. Moreover, users expect that their preference andcontext such as favorite football player, favorite football team,the present football competition and major games of thecompetition are reflected in their search results spontaneously.
The above requirements can be satisfied in a system which
stores semantic descriptions for the multimedia contents, user
preferences, and contexts and provides semantic searchcapabilities on the semantic descriptions [1,3-8]. However,considering the requirements, we can see some features that thesystem should have. First, since there are many different content
sources and metadata representation schemes, the semantic
descriptions for the contents should be managed in a single
repository (i.e. knowledge base) to support integrated semantic
search. Second, the users should be able to express theirinformation need as a simple keyword phrases, because
ordinary users don’t know the complex formal query language
and the schema of the underlying knowledge base. Third, theknowledge of user preference and context having very dynamic
trait should be represented in the same way with the knowledgeof contents metadata and treated equally in order to reflect them
automatically.
The input of the semantic search system is a keyword phrase
and the final output is a list of contents matching with the
keyword phrase reflecting user’s intention. In this process thesystem has to interpret the keyword query to fill the gap between
the keywords and the user’s intention and has to find themetadata description in the knowledge base that accord with theinterpretation [7-10]. The target contents are those connected tothe identified metadata description. In other words, the process
converts the keyword phrase into a formal query statement of
the knowledge base. Due to the ambiguity of keyword phrase,
there may be multiple formal queries produced from one
keyword query. How to rank these queries is a big challenge[7].
In this paper, we describe a framework for semantic
multimedia contents retrieval in smart TV. Our framework is
Copyright ⓒ GiRI (Global IT Research Institute)

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

ontological knowledge base-driven in the sense that theinterpretation process is integrated into a unified structurearound a knowledge base built on domain ontologies. Moreover,
our framework allows the knowledge base augmentation withthe dynamic context and user preference knowledge in a
uniform manner. The main objectives of our framework are toprovide enhanced retrieval performance and better userinterfaces based on the ontological knowledge base. Our
framework provides domain ontologies to represent logicallythe contents metadata, user preference, and context data. It also
includes such components as for knowledge base augmentation,user query interpretation, and adjustment of the interpretation
result.
This paper is structured as follows: In Section 2 we briefly
explain the conceptual architecture and principal functional
components of our framework as well as generic approaches forthe functions. Then, the prototype system to verify ourframework ideas is presented in Section 3. In Section 4 we
describe an application of prototype system in smart TV
environment. Section 5 outlines the related works. In Section 6
we provide the conclusions of our work and a brief descriptionof our future works.

190

graph adjustment component.
As described in the figure, our framework is ontologicalknowledge base-driven as all the components provide theirfunctions based on the knowledge base which is built on thedomain ontologies. More specifically, the metadata of contents
is represented in a logical graph in the knowledge base using thedomain ontologies of such as movie, drama, and sports. The
user preference and context data are also represented in thesame way as the metadata of contents, and integrated in theknowledge graph. The user query (i.e. keyword phrase) isinterpreted into a query graph by the keyword phraseinterpretation component, and then a list of contents that accord
with user’s intention is returned by the formal query conversion& processing component. The keyword phrase interpretation is
performed by picking up the most likely partial knowledge
graph (called query graph) among candidate partial graphs thatare extracted from the knowledge base. The candidate partial
graphs are those that the user query could denote. Since theinterpretation result is given as a graph, the user can easilyadjust it to be fit for his/her intention in GUI.

II. FRAMEWORK DESCRIPTIONIn this section we provide an outline of our framework for thesemantic retrieval of multimedia contents in smart TV. The
conceptual architecture of the framework is presented in Figure
1.

Fig. 2. User preference learning based on KB

Fig. 1. Conceptual architecture of the framework

The framework has two sections. The first section relates toknowledge base construction, and the second one relates tosemantic contents retrieval. The major functional componentsof the first section are domain ontologies, a knowledge base
population component and a knowledge augmentation
component. The second section has, as its major functional
components, a keyword phrase interpretation component, aformal query conversion & processing component, and a query

Our approach for the knowledge augmentation with user
preference is as follows. We can acquire the user preference
knowledge through two ways. The first one is to get it from theuser profile that user specified explicitly. The second one is tolearn it from user’s query history. Our approach for the user
preference learning is distinct from general association rulemining, because our approach is also based on the knowledge
base. In usual association rule mining, system mines only thegathered data for association rules. In our approach, the systemmines whole knowledge base. That means the association rules
are acquired not from the gathered query history but from theknowledge having been expanded through the knowledge graph.
For example, consider the case that the history data about music
video query which consists of singer (or group) name and music
title is gathered (e.g., “2NE1, I don’t care”, “SE7EN, Lalala”,“1TYM, Make it last”, “2NE1, Let’s go party”). We can map
each element of the gathered data to knowledge entity so that we
can expand the history data to the knowledge such as composer,
genre and member of the music group. In the end we can findthat the user’s preference is for the composer “Tedy”. Figure 2

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013shows the concept of our approach.
On the other hand, the social knowledge is acquired byapplying text mining techniques to social media such as blog,
news and bulletin board. For example, we can acquire theknowledge that the term, “Ronaldo Wink” relates to thequarterfinal match between Portugal and Germany in the World
Cup Germany 2006 by analysing blogs and news. With theknowledge base being augmented by such knowledge, thesystem can give much more accurate query results to the userwhen the user enters the keyword phrase, “Ronaldo winkfootball video”.
The user query interpretation process in our approach, which
is basically a graph-based technique like as other research[7-10], converts the keyword phrase into a partial knowledge
graph of the knowledge base. A query graph can be easilytranslated into a SPARQL[11] statement, because SPARQL is agraph pattern based query language. The process consists ofthree steps: term mapping, query graph construction, querygraph ranking. Term mapping maps the terms of the keyword
phrase to the entities of the knowledge base. After that, querygraph construction links the mapped entities so that the missing
relations and concepts can be obtained and a complete querygraph can be constructed. Finally, the query graph ranking
estimates the most likely query graph that best accords with theuser’s intention among all the candidate query graphs.

191

LeadingActor class afterwards by DL reasoning engine. Such
scheme means role concepts ought to be represented differently
from type concepts. A role concept is a class, but, unlike a typeclass, its instances are not fixed [13]. For example, the instancesof LeadingActor class continuously change, as new movies areadded to the knowledge base or existing movies are removed. A
role concept must be related to an event its instance participates
in. The properties used in the necessary and sufficient
membership condition of a defined class can be regarded as theevents.

III. PROTOTYPE SYSTEM
In this section we present the prototype system that has beendeveloping to verify our framework idea, focusing on main
components such as domain ontology, ontological knowledge
base, and user query interpretation module.
A. Movie Domain Ontology
In order to evaluate our framework, we have designed an
ontology for the description of movie contents using Web
Ontology Language (OWL)[12]. Figure 3 shows a part of the
ontology. In the left section of the figure you can see thehierarchy of classes and object property. You can see thedescription of LeadingActor class in the right section. In OWL,
which is based on Description Logic (DL), classes are classified
into two categories: primitive class and defined class. A
primitive class has a necessary membership condition, while adefined class has a necessary and sufficient membershipcondition [12]. In the figure, defined classes are marked withtriple line icon.
In our approach, the usage between primitive and definedclass is distinguished strictly. Though OWL allows the ontology
modellers to assert an individual to be an instance of multiple
classes, we assert an individual to be an instance of one class.
They are automatically asserted to be an instance of otherclasses afterwards by DL reasoning. For example, every
individual that denotes a human being must be asserted to be an
instance of Person class, and some of them having
playLeadingRole property are asserted to be instances ofFig. 3. Movie domain ontology

It is very difficult and troublesome to build a knowledge basefrom scratch. So an automated or semi-automated tool is needed
to migrate contents metadata from a legacy database to theknowledge base. The above scheme makes the knowledge base
population including migration very easy. For example,
consider an individual denoting a movie content, Iron Man.
Under the above scheme it is enough to assert the individual as
an instance of Movie class and describe its properties. You
don’t need to suffer from deciding which other classes theindividual should be belonged to. The reasoning engine
automatically asserts the individual as an instance of
ActionMovie and SFMovie classes by using the described
properties.
B. Movie Contents Knowledge Base
Figure 4 shows the knowledge base built using the movie
domain ontology. In the middle section of the figure you can see
the instances of ActionMovie class, while in the right section

Copyright ⓒ GiRI (Global IT Research Institute)

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

you can see the property description of movie_0002 individual.
The individuals are automatically classified as instances of
ActionMovie class by the DL reasoning engine.

192

term mapping, query graph construction and query graphranking.

Fig. 5. KB processing & User Query Interpretation Process

Fig. 4. Movie Contents Knowledge baseIn our knowledge base, every entity has a label annotation as
in upper-right section of the figure. Using such labels the system
makes indexes of the entities and maps user keyword to thecorresponding entities. Figure 5 shows the process forknowledge base indexing and user query interpretation.
C. User Query Interpretation
The keyword phrase interpretation component translates theuser query into a partial knowledge graph (i.e. query graph).
That process is carried out through three steps as in Figure 5:

Term Mapping
The purpose of term mapping is to find correspondingknowledge entities (i.e. classes, individuals, properties andliterals) for each term in the keyword query. The name andlabels of the entities are used for mapping. In our
implementation, the term mapping process indexes the names
and labels of knowledge entities, and using the fuzzy searchfeature of Lucene[14], returns a list of knowledge entities foreach entered keyword. The returned entities are ranked
according to syntactic similarity to the respective keyword.

1
2
3
4
5
6
7
8
9

USER_QUERY_INTERPRETATION(keyword_list)
user_query_segment_mapping_list = TERM_MAPPING(keyword_list);
initialize new empty query_graph;initialize new empty instance_entity_list;
FOR mapping in user_query_segment_mapping_list
add instance_entity_list to mapping;clear instance_entity_list;
query_graph_store = CONSTRUCT_QUERY_GRAPH(mapping);
extract shortest_query_graph containing all the knowledge_entities of mappingfrom query_graph_store;10
add shortest_query_graph to query_graph;11
IF mapping is not the last one
12
THEN translate shortest_query_graph into SPARQL query statement;
13
instance_entity_list = process SPARQL query with KB;
14
RETURN query_graph;
15 TERM_MAPPING(kwyword_list)
16
initialize new empty user_query_segment_mapping_list;
17
FOR keyword in kwyword_list
18
initialize new empty mapping_list;
19
find knowledge_entity for keyword;20
add knowledge_entity to mapping_list;
21
IF knowledge_entity is class entity
22
THEN add mapping_list to user_query_segment_mapping_list;
23
RETURN user_query_segment_mapping_list;
24 QUERY_GRAPH_CONSTRUCTION(mapping)25
initialize new empty query_graph_store;
26
extract class_entity from mapping;27
FOR knowledge_entity (except class_entity) in mapping
28
make connections between knowledge_entity and class_entity;
30
add connections to query_graph_store;
31
RETURN query_graph_store;
Fig. 6. User query interpretation algorithm

Copyright ⓒ GiRI (Global IT Research Institute)

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

Query Graph Construction
The query graph construction process builds up candidate
query graphs with the knowledge entities mapped in the term
mapping step. The process explores all entities related to the
mapped entities. The exploration simply incorporates allentities and literals within a pre-defined range (i.e. distance) andmakes up the missing relations and concepts for the user query.
From the explored paths, only those, called connections, areselected where the first and the last vertex correspond to one of
the mapped entities. When the connections can be joined into agraph containing all the entities mapped in the term mapping
step, the candidate query graph is generated according to thefollowing rules: 1) Class entities mapped by the term mapping
or discovered by the exploration are regarded as variable nodes.
2) Individual entities and literals are regarded as end nodes. 3)
Property entities are regarded as the edges of the query graph.
Query Graph Ranking
After the term mapping and query graph construction,
multiple candidate query graphs will be produced. There comesthe problem: how to pick up the most appropriate query graphfor the user? Various models have been suggested for theevaluation [7-10,15]. One of the simplest way is to give higher
rank to the query graph that has the shorter path connecting all
the mapped entities. We use the shorter path model because theassumption is generally valid that the knowledge entities whichhave conceptual relations are located close to each other in aknowledge graph [9].
The algorithm for the user query interpretation process isshown in Figure 6. In the algorithm we consider the case that a
keyword is mapped to one entity. But actually it is not, so themultiple mapped entities should be split into different query sets.
The query set split step is a process of enumerating all possiblecombinations from different senses of each keyword.

193

consists of contents metadata about instances of movie, drama,
entertainment, and music video.
The knowledge base server should be to create the index
about entity-label. Then, it should be to recognize the entity forentered user keyword phrase. After that knowledge base server
links the recognized entities so that query graph can beconstructed. And the knowledge base server should be to rank
candidate query graphs. At that time, it is to make use of themodel of entities weight.
Knowledge Entity Indexing
The knowledge base server loads the contents metadata. The
server is configured with an entity label and the URI(Uniform
Resource Identifier) to generate the index. This index is used torecognize the knowledge entity to user keyword in the processof knowledge entity recognition. The creation of indexes in theimplementation of the lucene library is used. The index isdivided into a resource and literal.
Knowledge Entity Recognition
The purpose of Knowledge Entity Recognition is to findcorresponding ontology entities, such as classes, individual,
properties and literals. In our implementation, we are using
Korean morphological analyzer. After the completion ofstemming, find the best combination of keyword for entity
recognition. Morphological Analyzer is a software librarycapable of detecting morphemes in a piece of keyword phrase.
The Figure 7 describes the results of knowledge entity
recognition from the best combination of keywords. The resultsof recognized entities have contained node URI and type
information of node.

IV. IMPLEMENTATION OF PROTOTYPE SYSTEM
In this section we describe the implementation of prototype
system on smart TV environment. There should beapproximately 2,000 instances of content in ontologicalknowledge base. And they are an experimental metadata for the
performance verification of prototype system. The user
keyword phrase can be interpreted by prototype system invarious ways. It is possible for smart TV environment tointerpret the search intention of their keyword phrase andknowledge base. The interpreted user queries and search resultsof knowledge base can be used in combination with othercontents searcher, such as VoD, Broadcast, and UCC(UserCreated Contents) searcher. The prototype system consists ofthree parts: the Knowledge Base Server, Content Retrieval
Server, and Smart TV Client.

Fig. 7. Results of knowledge entity recognition

Query Graph Construction and Ranking
The knowledge base server builds up query combinationfrom the recognized entities. The query combination process
constructs candidate query graphs with the ontology resources
mapped entities. The query graph ranking is to find the bestquery graph from candidate query graphs. Figure 8 shows theconceptual spanning tree of user query. Figure 9 shows an
expanded ontological query graphs. It is expanded the querygraph through the path of graph from the conceptual spanning
tree. It is the best query graph.

A. Knowledge Base Server
The knowledge base server enable contents retrieval server toperform exploration of knowledge base. The knowledge base

Copyright ⓒ GiRI (Global IT Research Institute)

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

194

User Query Interpreter
The user query interpreter creates an interpreted query via
knowledge entity recognition, query graph construction andranking, dynamic SPARQL generation and SPARQL
processing results.

Fig. 8. Conceptual spanning tree of user query

VoD Contents Searcher
The VoD Contents Searcher retrieves contents of VoD toprovide streaming services in VoD contents repository. The
search results are applied to the dynamic classification system.
Broadcast Contents Searcher
The Broadcast Contents Searcher retrieves contents ofbroadcast in EPG(Electronic Program Guide) database.
UCC Searcher
The UCC Searcher generates a query that is suitable for
global repository, such as Youtube and Daum TV pot. The
created query is a global repository input. And search results arecompleted post-processing, such as filtering, ranking, andgrouping.

Fig. 9. Expanded ontological query graphs

Dynamic SPARQL Generation
The knowledge base server performs the dynamic SPARQL
generation through the best query graph. Figure 10 shows anexample of SPARQL query. In our implementation we are using
Jena ARQ that is SPARQL processing engine.

Fig. 10. Example of SPARQL

B. Contents Retrieval Server
The contents retrieval server is passed the user enteredkeywords. And interpreted query is created by knowledge baseserver. The interpreted query is passed to the VoD Contents
Searcher, Broadcast Contents Searcher, and UCC Contents
Searcher. The search results are returned by the each searcher.
Figure 11 shows the class diagram of contents retrieval server.

C. Smart TV Client
The smart TV client acquires the user entered keywords, and
it is passed on to the contents retrieval server. The user queryinterpreter delivers the interpreted query for user feedback. Also,
it provides the search results via filtering, ranking, andgrouping.
Smart TV Search Interface
Figure 12 describes the GUI of smart TV client. The smart
TV client consists of three parts: the preferred broadcast
channels, information of preferred broadcast contents, andhistory of VoD contents. User entered keywords is passed to thecontents retrieval server.

Fig. 12. Search interface in smart TV

Smart TV Search Results Interface
The search results interface provides two type of information.
Firstly, the client provides search results to be filtered, ranked,
and grouped. Second, it provides expanded keywords phrase forinterpretation of user keyword. Figure 13 shows search resultsinterface in smart TV.
Fig. 11. Class diagram of contents retrieval server

Copyright ⓒ GiRI (Global IT Research Institute)

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

Fig. 13. Search results interface in smart TV

Smart TV Recommendation Interface
Figure 14 shows recommendation interface for preferred
broadcast contents. In order to provide more accurate program
recommendation, we use not only the user watching history, butalso the user program preference and program preference
updated as a user preference profile by periods.

195

interpretations that can be derived from the underlying
knowledge graph can be computed.
With respect to these recent works, our approach is distinct inthree aspects. First, we enrich the knowledge graph with user
preference knowledge and context knowledge. Thus, themeanings of user query are interpreted more accurately. Second,
our framework provides the principle for ontology design andknowledge base population so that contents’ metadata can beeasily migrated by the computer from legacy content libraries.
Third, user can easily adjust the interpretation result of his/her
keyword query in GUI, since the interpretation result isprovided as a partial knowledge graph.
In Semantic Web, the semantic information of the Web isrecorded by RDF triple and is embedded in Web pages. In RDF
triple, the concepts and their relationships are defined. We callthe data defining the resource and its relations (concept andproperty) metadata. Relations between concepts/instance are
required to be explicitly stated in formal logic queries, which
are often missing in keyword queries. OntoLook is a prototype
relation-based search engine, which has been implemented in a
virtual Semantic Web environment. The core idea of“OntoLook” is that there are relations among the submitted
keywords, and Semantic Web offers the ability of processing
relations at the system architecture level[17].
VI. CONCLUSION AND FUTURE WORKS

Fig. 14. Personalized video recommendation interface in smart TV

V. RELATED WORKS

Recently, digital audiovisual library systems, video on
demand service systems are developed based on widely
accepted standards for audiovisual content descriptions such as
MPEG-7 [16] and TV-Anytime [2]. An MPEG-7 driven
framework for managing semantic metadata for audiovisualcontent was presented in [1]. The framework allows thedescription of domain ontologies within MPEG-7 and theencoding of semantic multimedia metadata descriptions thatutilize the domain ontologies in the Semantic DS of the
MPEG-7 MDS.
On the other hand, translating keywords to formal queries is aline of research of information retrieval communities. [7]represents an attempt that specifically deals with keyword
queries in semantic search engines. There, keywords are
mapped to elements of triple patterns of predefined query
templates. These templates fix the structure of the resulting
queries a priori. These problems have been tackled recently by[8.9]. In [9], a more generic graph-based approach has been
proposed to explore all possible connections between nodes that
correspond to keywords in the query. This way, all

In this paper, we proposed an ontological knowledge
base-driven framework for semantic multimedia contents
retrieval. We briefly explained the conceptual architecture andprincipal components. We also explained generic approaches toimplement each component. Our framework has the distinctive
features that the knowledge of user preference and context isspontaneously reflected in the query process and that theinterpretation of user query can be easily adjusted by the user inGUI. Such features stem from the fact that all the knowledge ofcontent metadata, user preference and context is seamlessly
represented in a single knowledge graph and that theinterpretation result is also represented as a partial knowledge
graph.
To verify our framework ideas we have been developing a
prototype system. We discussed the domain ontology, i.e.
movie ontology and some principles for ontology design andknowledge base construction. The principle is simple but very
powerful when we can use Description Logic reasoning. We
gave an illustration of the knowledge base which is built basedon the movie ontology and showed an example of DL reasoning
in use. The interpretation process of user query (i.e. keyword
phrase) was explained and the algorithm for the process wasprovided.
Our prototype is not at the final version, but still developing.
In the future we will implement the knowledge augmentation
component and the query graph adjustment component.
Especially, the user preference learning from user query history
and the social knowledge mining would give distinctive features
to our framework.

Copyright ⓒ GiRI (Global IT Research Institute)

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

REFERENCES
C. Tsinaraki, E. Fatourou and S. Christodoulakis, “An Ontology-Driven
Framework for the Management of Semantic Metadata describing
Audiovisual Information”, in Proceedings of the 15th International
Conference on Advanced Information Systems Engineering (CAiSE’03),
2003.
[2] TV-Anytime Forum, http://www.tv-anytime.org[3] E. Mäkelä, “Survey of Semantic Search Research”, in Proceedings of the
Seminar on Knowledge Management on the Semantic Web, 2005
[4] H. Wang, K. Zhang, Q. Liu, T. Tran and Y. Yu, “Q2Semantic: A
Lightweight Keyword Interface to Semantic Search”, in Proceedings of
the 5th European semantic web conference on The semantic web:research and applications (ESWC’08), 2008
[5] E. Hyvönen, S. Saarela and K. Viljanen, “Ontogator: Combining Viewand Ontology-Based Search with Semantic Browsing”, in Proceedings of
XML Finland 2003, 2003
[6] M. Lux, W. Klieber and M. Granitzer, “Caliph & Emir: Semantics inMultimeida Retrieval and Annotation”, in Proceedings of the 19thInternational CODATA Conference, 2004
[7] Y. Lei, V. Uren and E. Motta, “SemSearch: A Search Engine for the
Semantic Web”, LNCS(LNAI) vol.4248, 2006[8] Q. Zhou, C. Wang, M. Xiong, H. Wang and Y. Yu, “SPARK: Adapting
Keyword Query to Semantic Search”, LNCS vol. 4825, 2007
[9] T. Tran, P. Cimiano, S. Rudolph and R. Studer, “Ontology-Based
Interpretation of Keywords for Semantic Search”, LNCS vol.4825, 2007[10] J. Royo, E. Mena, J. Bernard and A. Illarramendi, “Searching the Web:
from keywords to semantic queries”, in Proceedings of the Third
International Conference on Information Technology and Applications(ICITA 2005), 2005[11] SPARQL Query Language for RDF, W3C, http://www.w3.org/TR/rdf-sparql-query/[12] OWL Web Ontology Language, W3C, http://www.w3c.org/TR/owl-ref/[13] N. Guarino, C. Welty, “A formal ontology of properties”, in Proceedingsof the 12th European Workshop on Knowledge Acquisition, Modelingand Management, LNCS Lecture Notes in Computer Science (LNCS) vol.
1937, 2000
[14] Lucene, Apache Software Foundation, http://lucene.apache.org/java/docs/index.html[15] N. Stojanovic, R. Studer and L. Stojanovic, “An Approach for
Step-By-Step Query Refinement in the Ontology-Based Information
Retrieval”, in Proceedings of the IEEE/ACM Web Intelligence
Conference (WI), New York, 2004[16] MPEG-7 (Multimedia Content Description Interface), MPEG Group,
http://mpeg.telecomitalialab.com/standards/mpeg-7/mpeg-7.htm[17] Y. Li, Y. Wang, X. Huang, “A Relation-Based Search Engine in Semantic
Web”, Proceedings of IEEE Transactions on Knowledge and Data
Engineering 19(2), 2007
[1]

196

project. His research interests include ontology-based knowledge base system
and intelligent agent system.

Jeongju Yoo received the BS and MS degree in
Telecommunications in 1982 and 1984, respectively,from Kwangwoon University, Seoul, Korea. He received
the Ph.D degree in Computing Science from Lancaster
University, United Kingdom in 2001. Since 1984, he has
been a Principal Member of Technical Staff in the Next
Generation Smart TV Research Department ofElectronics and Telecommunications Research Institute(ETRI), Korea. He was a Head of MPEG Korea delgatesfrom 2007 to 2009 and he is a Director of Smart TV Media Research Team at
ETRI. His research interests are in the area of QoS, video coding, media
streaming, and multiscreen service technology of Smart TV.

Jinwoo Hong received the BS and MS degrees inelectronic engineering from Kwangwoon University,
Seoul, Korea, in 1982 and 1984, respectively. He also
received the PhD in computer engineering from the same
university in 1993. Since 1984, he has been with ETRI,
Daejeon, Korea, as a principal member of engineering
staff, where he is currently a director of the Next
Generation SmartTV Research Department. From 1998
to 1999, he conducted research at Fraunhofer Institute in Erlangen, Germany,
as a visiting researcher. His research interests include multimedia frameworktechnology, broadcasting media and service, personal broadcasting, andrealistic media.

Moohun Lee received his BS and MS degree incomputer engineering from Hannam University,
Daejeon, Korea, in 2002 and 2004, respectively. He
joined ETRI, Daejeon, Rep. of Korea in 2008 and was
involved with the OPRoS (Open Platform for Robot
Service) project until 2010. He is currently working as asenior researcher in smart search and recommendation
system development for smart TV project. His researchinterests include ontology-based knowledge base system,
semantic search, and information retrieval.

Joonmyun Cho received his BS, MS and PhD in
mechanical Engineering from Korea Advanced Instituteof Science and Technology (KAIST) in 1993, 1995 and2006, respectively. He joined ETRI, Daejeon, Rep. of
Korea in 2007 and was involved with the URC(Ubiquitous Robotic Companion) project until 2011. He
is currently working as a project leader in smart searchand recommendation system development for smart TV

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013197

A Proposal of Semantic Analysis based
Integrated Multi-Level Search System
for Smart TV
Myung-Eun KIM*, Joon-Myun CHO*, Jeong-Ju YOO*, Jin-Woo HONG*, Sang-Ha KIM*** Smart TV Media Research Team, ETRI, 218 Gajeong-ro, Yuseong-gu, Daejeon, 305-700, KOREA** Department of Computer Science and Engineering, Chungnam National University, 99 Daehak-ro, Yuseong-gu,
Daejeon, 305-764, KOREA
mekim@etri.re.kr, jmcho@etri.re.kr, jjyoo@etri.re.kr, jwhong@etri.re.kr, shkim@cnu.ac.kr

Abstract—Aligned with the rapid change of broadcast
environment TV is no longer than a passive device to receive asignal of terrestrial television broadcasting. A Smart TV is the
new trend of integration of the Internet and Web 2.0 features into
the modern television sets and set-top boxes. The users having
much experience in a computer want to use a Smart TV alike.
However, a Smart TV has yet to provide various user interface
devices such as a mouse and a keyboard thus it is needed todevelop new search technology to analyze user intents from simple
user keyword phrase and search the target contents from themultiple sources including broadcast network and Internet. In
this paper, we proposed the framework of semantic analysis based
integrated multi-level search system to improve search accuracy
and expand search coverage. The proposed system can retrieve
the user desirable multimedia contents from various sources at atime by analyzing ambiguous user keywords phrase withontological knowledge.
Index Terms—Semantic Network,
Integrated Search, Smart TV

Multi-Level

Search,I. INTRODUCTIONT

The Internet technology has evolved very fast over the past
several decades, so it has been having a big effect on ourdaily life such as education, art, game, and broadcast etc. In
reality, it is no exaggeration to say Internet is an indispensable
Manuscript received June 30, 2012. This work was supported by the
ETRI R&D Program of KCC (Korea Communications Commission), Korea[11921-03001, "Development of Beyond Smart TV Technology"].
Myung-Eun KIM is with the Electronics and Telecommunications ResearchInstitute, 218 Gajeong-ro, Yuseong-gu, Daejeon 305-700, Korea (phone:+82-42-860-5303; fax: +82-42-860-6202; e-mail: mekim@ etri.re.kr)
Joon-Myun CHO is with the Electronics and Telecommunications ResearchInstitute, 218 Gajeong-ro, Yuseong-gu, Daejeon 305-700, Korea (email:jmcho@etri.re.kr)
Jeong-Ju Yoo is with the Electronics and Telecommunications ResearchInstitute, 218 Gajeong-ro, Yuseong-gu, Daejeon 305-700, Korea (email:jjyoo@etri.re.kr)
Jin-Woo HONG is with the Electronics and Telecommunications ResearchInstitute, 218 Gajeong-ro, Yuseong-gu, Daejeon 305-700, Korea (email:jwhong@etri.re.kr)
Sang-Ha KIM is with the Department of Computer Science and Engineering
Department, Chungnam National University, 99 Daehak-ro, Yuseong-gu,
Daejeon 305-764, Korea (email: shkim@cnu.ac.kr)

infrastructure to lead everyday life these days. Now Internet
technology plays a principle role in developing newtechnologies as well as becoming a fundamental infrastructure
to provide various services. As the Internet has been growing
up, many technologies have taken another big step forward to a
new paradigm shift – the convergence with IT technology. The
broadcast technology has also expanded its transmission
infrastructure to Internet. TV is no longer than a passive device
to receive a signal of terrestrial television broadcasting and now
it is evolving into a smart device providing Internet based
services [20]. Nowadays we can watch plenty of multimedia
contents scattered over the Internet and make use of interactive
services including SNS, Internet full browsing, andapplications on Smart TV.
While the Smart TV provides multiple services in addition tobroadcasting, the fact still remains the major role of TV is towatch multimedia contents either TV shows or payable videos.
These days users can get a great deal of multimedia contentsfrom various sources involving broadcasting stations orcontents providers on Internet; however, it is quite difficult tofind a multimedia content what a user wants to watch using thesimple search keywords from the limited UI/UX on TV. We
think a TV hasn’t still been a good interactive multimedia
device with easy input devices such as a mouse and a keyboard
to get lots of input data easily from users but a fantastic
appliance to watch video contents using a large screen.
Therefore it is needed to develop a new search system for SmartTV retrieving target contents easily with ambiguous search
keywords from various multimedia sources including broadcast
network and Internet. We proposed the semantic analysis based
integrated multi-level search system searching considering
newly emerged requirements from broadcast environmentchanges. In the rest of this paper, we present our contributions.
In Section II, we present the related works and Section III
describes the proposed system, the semantic network based
integrated multi-level search system. Then we discuss ourcurrent works and future works to improve multimedia searchefficiency.

Copyright ⓒ GiRI (Global IT Research Institute)

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

II. RELATED WORKS
Unlike textual data, whose content can be searched for using
text strings, multimedia information retrieval(MIR) is
dependent on processes that have either cumbersome
requirements for feature comparison (e.g. color or texture) or
rely on associated, more easily processable descriptions,selecting aspects of an image or video and expressing them astext, or as concepts from a predefined vocabulary.[17]The earliest years of MIR were frequently based on computer
vision algorithms which focused on feature based similarity
search over images, video, and audio. Influential and popular
examples of these systems are QBIC [1] and Virage [2], aroundmid-90s. Within a few years, the basic concept of the similarity
search was transferred to several Internet image search engines
including Webseek [3] and Webseer [4]. Significant effort wasalso placed on the direct integration of the feature-basedsimilarity search into enterprises-level databases such as
Informix datablades, IBM DB2 Extenders, or Oracle Cartridges[5] to make MIR more accessible to private industry.
In the area of video retrieval, the main focus in the mid-90s
was on robust shot boundary detection; the most common
approaches involved thresholding the distance between color
histograms corresponding to two consecutive frames in a video[1]. Hanjalic et al. [6] proposed a method which overcame theproblem of subjective user thresholds. Their approach was notdependent on any manual parameters. It gave a set of key
frames based on an objective model for the video information
flow. Haas et al. [7] described a method of using the motion
within the video to determine the shot boundary locations.
Their method outperformed the histogram approaches of theperiod and also performed semantic classification of the video
shots into categories such as zoom-in, zoom-out, pan, and so on.
A more recent practitioner’s guide to video transition detection
is given by Lienhart [8].
Near the turn of the 21st century, researchers noticed that thefeature-based similarity search algorithms were not as intuitiveor user-friendly as they had expected. One could say thatsystems built by research scientists were essentially systems
which could only be used effectively by scientists. The new
direction was geared toward designing systems which would beuser-friendly and could bring the vast multimedia knowledge
from libraries, databases, and collections to the world. To dothis, it was noted that the next evolution of systems would needto understand the semantics of a query, not simply the low-level
underlying computational features [18]. This general problem
was called “bridging the semantic gap”. The semantic gap is thelack of coincidence between the information that one canextract from the visual data and the interpretation that the samedata have for a user in a given situation. Techniques forattempting to bridge the semantic gap in multimedia retrieval
are followings [19].
A. Automatic Annotation
The current techniques for auto-annotation generally fall into
two categories; those that first segment images into regions, or‘blobs’ and those that take a more scene-orientated approach,198

using global information.
Duygulu et al. [9] proposed a method by which a machinetranslation model was applied to translate between keyword
annotations and a discrete vocabulary of clustered ‘blobs’. Jeonet al. [10] improved on the results of Duygulu et al. [9] byrecasting the problem as cross-lingual information retrieval andapplying the Cross-Media Relevance Model (CMRM) to theannotation task. Lavrenko et al. [11] used the Continuous-space
Relevance Model (CRM) to build continuous probability
density functions to describe the process of generating blobfeatures.
Most of the auto-annotation approaches described above
performs annotations in a hard manner; that is, they explicitly
apply some number of annotations to an image. A hardauto-annotator can cause problems in retrieval because it may
inadvertently annotate with a similar, but wrong label.
B. Semantic Spaces
Instead of applying hard annotations, we have developed an
approach in which annotation is performed implicitly in a softmanner. A semantic-space of documents (images) and terms(keywords) is created using a linear algebraic technique.
Similar documents and/or terms within this semantic-spaceshare similar positions within the space. Latent Semantic
Indexing is a technique originally developed for textual
information retrieval. Berry et al [12] described how Latent
Semantic Indexing can be used for cross-language retrieval
because it ignores both syntax and explicit semantics in the
documents being indexed.
C. Semantic Annotation
Early work on semantically describing images using
ontologies as a tool for annotating and searching images more
intelligently was described by Schreiber et al [13]. Several
authors have described efforts to move the MPEG-7 descriptionof multimedia information closer to ontology languages such as
RDF and OWL [14, 15].
The aim of using ontologies to describe multimedia
resources is to provide well-structured information to improve
the accuracy of retrieval. Semantic web technologies also
facilitate the integration of heterogeneous information sources
and formats. Well-structured information is crucial for
providing advanced browsing and visualization facilities, as
opposed to more traditional query-based systems.
There are several approaches to semantically annotating
multimedia. The aceMedia project [16] is developing aknowledge infrastructure for multimedia analysis, which
incorporates a visual description ontology and multimedia
structure ontology. They have also developed the
M-OntoMat-Annotizer tool that allows users to manuallyannotate multimedia items with semantic information.
Won-Ken Yang at al [21] developed an image description andmatching scheme using synthesized spatial and statisticalfeatures for recommendation service.

Copyright ⓒ GiRI (Global IT Research Institute)

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

III. SEMANTIC MULTIMEDIA CONTENTS RETRIEVALFRAMEWORKThe Smart TV has various multimedia content sources suchas broadcasting stations and various content providers scatteredon Internet. We classified these multimedia content sources
into three categories. The first is the local repository managed
by Smart TV businesses similar to IPTV businesses such as
QOOK TV, B TV, and U+ TV. The second is the EPG(Electronic Programme Guide) repository managing theschedule information of TV program. The third is the global
repository such as YouTube having plenty of UCCs.

199

one term, it chooses one with the highest weight.
b. If it finds nothing, it returns null value to the smart TV
agent server.
4) The knowledge base server generates candidate querygraphs connecting all possible permutations of knowledge
objects.
a. If it gets dozens of candidate query graphs, it regards
the shortest graph as the best result and selects the
top-N-best graphs.
b. It picks out knowledge objects from each best graphand then creates the list of expanded user keywords.
5) The knowledge base server sends the smart TV agent
server the interpreted results of user search keyword
involving user search keywords, knowledge objects,
query graphs and expanded user keywords.
Phase 2: Contents Search

Fig. 1. System Overview

So we designed the semantic network based integrated
multi-level search system with three search engines for local
repository, EPG repository, and global repository. The
proposed system overview is illustrated in Fig. 1. The Smart
TV is connected by Internet with back-end search systems
including Smart TV agent server, knowledge base server,
search/recommend server, contents server, and SNS/contents
information server and a user can interact with the Smart TV
agent server through a HTML5 enabled web browser.
The Smart TV agent server performs the two-phase search
process. In first phase, it analyses the meaning of user search
keywords using the knowledge base server and then searches
multimedia contents matching with the analyzed search
keywords from several contents repositories in second phase.
The details of the two-phase search process are followings:
Phase 1: Interpretation of User Keywords
1) The user search keywords phrase entered through the
web-based smart TV browser are sent to the Smart TV
agent server.
2) The Smart TV agent server parses the blank-separate user
search keywords phrase into a list of terms and sends it to
the knowledge base server.
3) The knowledge base server finds knowledge objects
corresponding to each term from the smart TV agent
server.
a. If it finds several knowledge objects matching with

1) The Smart TV agent server sends the interpreted user
query to the local repository search engine.
2) The local repository search engine creates a SPARQL
query with the best query graph and executes it.
3) The local repository search engine performs grouping,sorting and classifying on the search result sets andappends them to the interpreted user query. It finally
returns the interpreted user query to the Smart TV agent
server.
4) The Smart TV agent server dispatches the interpreted
results to two other search engines, EPG repository
search engine and global repository search engine.
5) Each search engine creates query expressions using theinterpreted results and contents list.
a. The EPG repository search engine generates a
MySQL query.
b. The global repository search engine generates
queries for web search engines (e.g. YouTube,
Daum, Naver, etc.).
6) Two search engines send the Smart TV agent server the
search results being grouped, sorted, and classified.
7) The Smart TV agent Server integrates the search resultsfrom each search engine and browses it to a user.
SNS /Contents Info.
ServerSmart TV Agent Client
Browser
Control

Mobile Device
ControlSNS
Gateway
Contents
Info.
ProviderSmart TV Agent Server
User
Management

Usage History
Management

Application
Handler

BroadcastContents
Control

Contents
Server
Search/Recommend ServerStreaming
Service
Management

Semantic
Analysis

Knowledge Base
ServerLocal Repository Search

Semantic
Network Analysis

Global Repository Search

User PreferenceManagement

EPG Repository Search

KB Indexer

Fig. 2. System Architecture

Fig. 2 presents the architecture of the proposed system

Copyright ⓒ GiRI (Global IT Research Institute)

ICACT Transactions on Advanced Communications Technology (TACT) Vol. 2, Issue 2, March 2013200

consisting of several subsystems. As it shown, each subsystem
has several functional software blocks and has close
relationship with other subsystems with various interfaces.

applications including a multimedia contents search application
so it manages the life cycle of applications and handling theevents from users and those applications.

A. Smart TV Agent Server
The Smart TV agent server is designed to manage the user
profile, watching history and user behavior pattern. It also
controls the execution of Smart TV applications and broadcast
contents. The functional blocks of the Smart TV agent server
are as follows.

B. Knowledge Base Server
The knowledge base server manages ontology representing
metadata of multimedia contents retained in a contents server.
We chose five areas of multimedia contents such as movie,soap opera, entertainment show, sports game and music video
to implement domain ontology and designed an ontology using
the Web Ontology Language (OWL). Fig. 3 shows theexamples of film domain ontology. The left section describes
the hierarchy of classes and object properties belonged to thefilm domain. The right section illustrates the description andinstances of the Film class. For example, the Film class is a subclass of FilmDomain, Topic and Media class and it has dozens
of object properties involving film_country, film_directed_by,
film_distributors, and so on.
It is very cumbersome to set up a knowledge base fromscratch, so we used a semi-automated tool to migrate contents
metadata from a legacy database to the knowledge base server.

User Management
The Smart TV agent server manages user profiles containing
user personal information. Some properties representing user
preferences involving the favorite genre of movie, TV show,
and music are stored in the knowledge base server and used forgrouping, sorting, and classifying the search results. The
TABLE I describes the data structure of user profile.

Name

Type

seq_nou_nameu_id
u_passwd
u_sex
u_age
u_job
f_movief_show
f_music
s_id
s_passwd

IntegerStringStringStringStringStringStringString[]String[]String[]String[]String[]TABLE I
USER PROFILE
Description
Sequential number
User name
User id
User password
User sex
User age
User affiliation
Favourite movie genre
Favourite TV program genre
Favourite music genre
User id for SNS
User password for SNS

User History Management
The Smart TV agent server gets the user’s watching history
from the Smart TV agent client and stores in the user history
database. It conducts the regular time-frequency analysis ofuser histories collected during a specific period to derive user
preference data such as the favorite TV channel, the favorite
TV show and the latest watched video from the user history
database. It stores the analyzed data in the knowledge base andcreates the personalized menu page providing the current TV
show on the favorite channel and the current channel list airing
the favorite TV show by searching the EPG data with the user
preference data.
Broadcast Contents Control
The Smart TV agent server controls broadcast contents andsets the DVR alarm by user request. It delivers user requests toa TV tuner card and changes the channel of terrestrial TV
broadcasting and also provides the video recording facility
setting it up in user-specified time.
Application Handler
The Smart TV agent server takes charge in handling various

Fig. 3. Examples of the film domain ontology

The functional blocks of the knowledge base server are as
follows.
Semantic Network Analysis
The Sematic Network Analysis module analyses the user
search keyword referring to ontological knowledge and creates
the interpreted user query including analyzing results such as
knowledge objects, query graphs and expanded user keywords.
Fig. 4 depicts the interpretation process of user search
keywords consisting of keyword phrase stemming, term
mapping, query graph constructing and query graph ranking.

Copyright ⓒ GiRI (Global IT Research Institute)

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

201

Fig. 5. Examples of the list of expanded user keywords
Fig. 4. Interpretation Process of User Search Keywords• Keyword phrase stemming: it gets the blank-separated
user search keywords from the search/recommend server
and parses it into a list of terms. In this step, we don’t
consider the morphological analysis of user query since
we assumes the user inputs a query expression form of notnatural language but simple keywords.
• Term mapping: the knowledge base server makes indexesof itself with the name and labels of all knowledge objects
when it starts up. It finds all knowledge objects
corresponding to each term of user search keyword bycomparing with the indexes of knowledge base.
Sometimes it can have the ambiguity problem having
several similar knowledge objects for one term. We
ranked the knowledge objects by their pre-defined weightvalues and chose the highest one.
• Query graph constructing: it builds candidate querygraphs connecting all possible permutations of knowledge
objects within a pre-defined range (i.e. distance) with no
duplicates. It can find new intermediate knowledge
objects between user search keywords during query graphgeneration and make up the query graph including them.
• Query graph ranking: it sorts the candidate query graphs
by their ranking points. We assume the closer together
knowledge objects are, the stronger the semantic
relationship between them, so we choose to use theshortest path model and give higher rank to the shorter
query graph than others. After all we select top-N-bestquery graphs and make the list of expanded user keywords
by extracting the labels of knowledge objects having the‘isDummy’ value set to zero from those selected querygraphs. When we design the ontology, we pre-annotatedthe knowledge objects being used for user search
keywords by setting the ‘isDummy’ value to zero.
Fig. 5 shows the list of expanded words for the user search
keywords, “Seung-Wan Ryu Movie”. The knowledge baseserver makes it from query graphs connecting two knowledge
objects, the movie director named Seung-Wan Ryu and themovie.

User Preference Management
The knowledge base server manages user preference data
including favorite genre of movie, music, TV show, andfavorite actor/actress to be used for grouping, sorting, andclassifying the search results. Most of user preference
knowledge comes from the user profile information and someof that could be achieved through analysis of user behavior
pattern from the Smart TV agent server.
KB indexer
The knowledge base server creates indexes of itself with thename and label of all knowledge objects to ensure efficientperformance and updates it periodically to reflect changes of
ontology.
C. Search/Recommend Server
The search/recommend server provides three search engineswith the interpreted user query arose from the semantic analysis
of user search keywords and then searches multimedia contents
matching with the interpreted user keywords from several
repositories.

Fig. 6. Search Processing of the Search/Recommend Server

Fig. 6 depicts the searching steps of the search/recommend
server. The search/recommend server gets the interpreted user

Copyright ⓒ GiRI (Global IT Research Institute)

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

query corresponding to the user search keyword from theknowledge base server and then sends it to the local repository
search engine module at first. It receives the interpreted user
query appending the search result from the local repository
engine module and dispatches it other two search engine
modules. After all it integrates all search results from three
search engines and sends them to the Smart TV agent server.
The functional blocks of the search/recommend server are as
follows.
Semantic Analysis
The semantic analysis module gets the user search keywords
from the Smart TV agent server and creates the interpreted user
query involving user search keywords, knowledge objects,
query graphs and expanded user keywords using the semantic
analysis based on the ontological knowledge base. It delivers
the interpreted user query to three search engines creating
suitable forms of query expressions for respective repositories.
Local Repository Search Engine
The local repository search engine module is designed tosearch multimedia contents matching with the user search
keywords in the local repository. First of all it creates a
SPARQL query expression with the best query graph ofinterpreted user query and then executes it to search knowledge
objects meeting the conditions represented in the where clause.
When it gets the search results it performs grouping, sorting andclassifying on them reflecting user preferences. It appends thesearch result sets, the contents list, to the interpreted user queryand sends it to the Smart TV agent server.
EPG Repository Search Engine
The EPG repository search engine module aims to search thebroadcast schedule information of target contents in the EPG
repository retaining the weekly TV schedule including the four
major public TVs and several cable TVs.

Name

TABLE IIEPG DATA STRUCTURE
Type
Description

key
Channel
ChnameProgram Title
subtitle
StartTime
endTimeDay
Synopsis
Summarygenre
episodeNumber
Directors
castMembers

StringStringStringStringStringStringStringStringStringStringStringStringList<String>
List<String>

Uuid

StringimgUrlStringIdentifier
Channel number
Channel nameTV show title
TV show subtitle
Start time of TV show
End time of TV show
Broadcast day of TV show
Synopsis of TV show
Summary of TV show
Genre of TV show
Episode number of TV series
List of directors
List of cast members
Unique identifier of knowledge
object
URL of TV show poster

It creates a MySQL query expressions with the contents listof interpreted user query and runs it to search the broadcast

202

schedule of the contents list for the next three days. It sorts thesearch results by start time of TV show and sends them to the
Smart TV agent server. The TABLE II shows the data structureof EPG.
Global Repository Search Engine
The global repository search engine module seeks to filter
out undesirable search results from web search engines. It
creates queries adapted for the two web search engines
including YouTube and Daum TV pot with the contents list ofinterpreted user query and then dispatches queries to them. The
respective web search engine searches the UCC (User CreatedContents) matching the contents title with the contents list ofinterpreted user query and then returns them to the global
repository search engine.
The global repository search engine conducts following
three steps:• Filtering: It uses the simple term frequency (TF) to filter
out unsuitable contents from the search results. It builds
the keyword list for each UCC by collecting the tags andtokenized words of content title and then calculates
similarity between the keyword list of each UCC and theuser search keywords. After performing on all contents it
picked out contents having similarity over a specificthreshold. We set the threshold value of threshold to 0.3
by experiment results. The following simple expression
can be used to estimate a similarity S(q, ci) of a content
item ci and user query q :S(q, c ) = n(q ∩ c∈ )⁄n(q ∪ c∈ )

(1)

where
c = word list of content item i;q = word list of user query .
• Re-ranking: It conducts re-ranking on the filtered results
regarding user query, user preferences and similarity
between contents. The following expression can be used
to calculate rank point ri of a content item ci, user query q
and user preference p :Sc , c  = nc∈ ∩ c∈ nc∈ ∪ c∈ S(c ) = ∑ Sc∈, c S  (c ) =(∈)(2)(3)(0 ≤ S  (c ) ≤ 1)

(4)

S(p, c ) = n(p ∩ c∈ )⁄n(p ∪ c∈ )(5)

  ()r = α ∙ S(q, c∈ ) + β ∙ S′(c∈ ) + γ ∙ S(p, c∈ ) (6)wherec , c = word list of content item i, j ;q = word list of user query;p = word list of user preference .

Copyright ⓒ GiRI (Global IT Research Institute)

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

In Equation (6), we use the term frequency to estimate all
those similarities and set the weight value of α, β and γ to0.55, 0.35, and 0.1 in succession by experiment results.
• Grouping: It puts the re-ranked results into several
groups by contents providers, pre-defined categories andtopics. We use content tags to classify them by content
providers or categories and applies K-means algorithm togroup them by similar topic cluster.
D. Smart TV Agent Client
The Smart TV agent client provides a user with web-based
interactive user interfaces updating web pages responding touser commands. We think the current remote controllers aren’t
suitable for interactive user interfaces so we come up with theremote control application executing on the mobile device. The
users can handle the Smart TV with the mobile device leaningback in couch. It receives the signal of mobile devices
facilitating control of user interfaces using a UDP server anddelivers it to the Smart TV agent server.
The Smart TV agent client obtains the user input data fromthe Smart TV browser and sends the Smart TV agent server
those data to be used for creating new web pages. The users canenter various commands through the Smart TV browser;
besides they should get some information from the Smart TV
agent server occasionally. For example, they are allowed toreceive the alarm message set up at specific time for theirfavorite TV show while they are watching other TV show. We
designed to receive information from the Smart TV agent
server using WebSocket within a browser.

203

IV. PROTOTYPE SYSTEM
We have developed the prototype system to verify our idea
searching multimedia contents from various repositories basedon the semantic analysis. We first built up the knowledge baseserver having over 2,000 multimedia contents of five domains
including movie, soap opera, TV show, sports, and music video
consisting of 10,000 knowledge objects designed by the
ontological schema. Our prototype system has threesubsystems involving the Smart TV client system, the SmartTV agent server system, and the contents server system. The
Smart TV client system contains the Smart TV agent client andthe Smart TV browser supporting HTML5. The Smart TV
server system includes the search/recommend server, theknowledge base server, and the smart TV agent server.
The prototype system provides the integrated search results
merging the respective search results from three search engines
including the local repository search engine, the EPG
repository search engine, and the global repository searchengine for a user search request.

Fig. 7. The search results of local repository engine

E. SNS/Contents Information Server
The SNS/Contents information server plays a principle rolein managing the contents information and social network
services. It manages the detail information of a multimedia
content like poster, synopsis, director, and actor/actress etc.
The Smart TV agent server browses the detail information of
the content user chooses to watch. It provides users withfacilities utilizing the social network services such as Facebook
and Twitter to share opinions about multimedia contents while
watching a Smart TV. We build an automatic log-in system forregistered users having the account information of social
network services in their profiles.
F. Contents Server
The contents server takes charge of the seamless multimedia
streaming service for the target contents - play, stop, fast
forward, and rewind. It takes over the URL of multimedia
content as search results or user command from the Smart TV
agent Server and plays it after being clicked for watching on the
Smart TV browser. It is very important to manage the unique
URL for each multimedia content keeping consistency with theknowledge base server since it only recognizes the multimedia
content by its URL.

Fig. 7 depicts the list of VoD contents from the local
repository search engine. It listed search results for the bestinterpretation result stemming from the semantic analysis forthe user search keyword “Seung-Wan Ryu, Movie”. It gives theuser the top-N-best interpretation results the user to select oneof other interpretation results as the alternative search
keywords when the user’s not being satisfied with the best one
located on the top of the list.

Fig. 8. The search results of EPG repository search engine

Fig. 8 shows the examples of EPG data matching with theuser search keywords grouped by channel, broadcast day, andgenre from the EPG repository search engine. The user can

Copyright ⓒ GiRI (Global IT Research Institute)

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

watch TV show immediately by choosing one or set up alarm toreserve the particular TV show not being on air now.
Fig. 9 represents the list of UCCs from two web searchengines involving YouTube and Daum TV pot. We think weare not allowed to control the searching process of those web
search engines so we designed the global repository searchengine to focus on making the proper query expression andpicking up the desirable results. The prototype system gets thesearch results from the web search engines and filters out theundesired results having low similarities with the user queryand classified by the content providers, categories, and topics.
The two preceding grouping factors described in the tag
information of UCC are static, while the last factor is dynamic.
We pick up the frequently used topic words from thedescription of UCC and then use the K-means algorithm toclassify them in similar topic group.

Especially, the user preference learning from user query history
and the social knowledge mining could be other distinctive
features of our framework.
REFERENCES
[1]

[2]

[3]
[4]

[5]

[6]

[7]

[8]
[9]
Fig. 9. The search results of global repository search engine

V. CONCLUSIONSAs the Internet technology has been growing up fast, thebroadcast environment has been expanded to Internet. Alignedwith these trends TV is no longer than a passive device only toreceive a signal of terrestrial television broadcasting and it isevolving into a smart device providing Internet based services
like a smart phone. A Smart TV is the new trend of integrationof the Internet and Web 2.0 features into the modern television
sets and set-top boxes. The users having much experience in acomputer want to use a Smart TV alike. However, a Smart TV
has yet to provide various user interface devices such as amouse and a keyboard thus it is needed to develop new searchtechnology to analyze user intents from simple user search
keywords and search the target contents from multiple sources
including broadcast network and Internet.
In this paper, we proposed the framework of semantic
analysis based integrated multi-level search system to improvesearch accuracy and expand search coverage. The proposedsystem can retrieve the user desirable multimedia contents fromvarious sources at a time by analyzing ambiguous user
keywords phrase with ontological knowledge base. We hopethat the proposed system will foster the vision of user centeredsearch system to understand user’s intent from limited search
keywords for beyond Smart TV.
In the future we will implement the knowledge augmentation
component and the query graph adjustment component.

204

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

Flickner, M., Sawhney, H., Niblack, W., Ashley, J., Qianhuang Don, B.,
Gorkani, M., Hafner, J., Lee, D., Petkovic, D., Steele, D. and Yanker,
P.,”Query by image and video content: The QBIC system”, IEEE
Comput., (Sept.), 1995, pp. 23–32.
Bach, J. R., Fuller, C., Gupta, A., Hampapur, A., Horowitz, B.,
Humphrey, R., Jain, R., and Shu, C. F., “Virage image search engine: An
open framework for image management”, In Proceedings of the SPIE
Storage and Retrieval for Still Image and Video Databases, 1996, pp.76–
87.
Smith, J. R. and Chang, S. F., “Visually searching the web for content”,
IEEE Multimedia 4, 3, 1997, pp.12–20.
Frankel, C., Swain, M. J., and Athistsos, V., “WebSeer: An image searchengine for the World Wide Web”, University of Chicago Tech. rep. 96-14,
University of Chicago, Chicago, IL, 1996.
Bliujute, R., Saltenis, S., Slivinskas, G., and Jensen, C. S., “Developing a
DataBlade for a new index”, In Proceedings of IEEE International
Conference on Data Engineering. (March) Sydney, Australia, 1996, pp.
314–323.
Hanjalic, A., Lagenduk, R. L., and Biemond, J., “A new method for key
frame based video content representation”, In ImageDatabases andMultimedia Search, A. Smeulders and R. Jain, Eds. World Scientific,
1997, pp.97–107.
Haas, M., Lew, M. S., and Huijsmans, D. P., “A new method for key
frame based video content representation”, In Image Databases andMultimedia Search. A. Smeulders and R. Jain, Eds. World Scientific,
1997, pp.191–200.
Lienhart, R., “Reliable transition detection in videos: A survey andpractitioner’s guide”, Int. J. Image Graph. 1, 3, 2001, pp.469–486
Duygulu, P., Barnard, K., de Freitas, J.F.G., Forsyth, D.A., “Object
recognition as machine translation: Learning a lexicon for a fixed image
vocabulary”, In: ECCV ’ 02: Proceedings of the 7th European
Conference on Computer Vision-Part IV, London, UK, Springer-Verlag,
2002, pp.97–112.
Jeon, J., Lavrenko, V., Manmatha, R., “Automatic image annotation andretrieval using cross-media relevance models”, In: SIGIR ’03:
Proceedings of the 26th annual international ACM SIGIR conference on
Research and development in information retrieval, New York, NY,
USA, ACM Press, 2003, pp.119–126.
Lavrenko, V., Manmatha, R., Jeon, J., “A model for learning thesemantics of pictures”, In Thrun, S., Saul, L., Sch¨olkopf, B., eds.:
Advances in Neural Information Processing Systems 16. MIT Press,
Cambridge, MA, 2004.
Berry, M.W., Dumais, S.T., O’Brien, G.W., “Using linear algebra for
intelligent information retrieval”, Technical Report UT-CS-94-270,
University of Tennessee, 1994
Schreiber, A.T.G., Dubbeldam, B., Wielemaker, J., Wielinga, B.,“Ontology-based photo annotation”, IEEE Intelligent Systems 16, 2001,
pp.66–74.
Hunter, J., “Adding multimedia to the semantic web: Building an mpeg-7
ontology”, In Cruz, I.F., Decker, S., Euzenat, J., McGuinness, D.L., eds.:
SWWS, 2001, pp.261–283
Tsinaraki, C., Polydoros, P., Moumoutzis, N., Christodoulakis, S.,“Coupling owl with mpeg-7 and tv-anytime for domain-specificmultimedia information integration and retrieval”, In: Proceedings of
RIAO 2004, Avignon, France, 2004
Kompatsiaris, I., Avrithis, Y., Hobson, P., Strinzis, M., “Integratingknowledge, semantics and content for user-centred intelligent media
services: the acemedia project”, In: Proceedings of Workshop on Image
Analysis for Multimedia Interactive Services (WIAMIS ’04), Lisboa,
Portugal, 2004
Richard Arndt, Raphael Troncy, Steffen Staab, Lynda Hardman, andMiroslav Vacura, “COMM: Designing a Well-Founded Multimedia
Ontology for the Web”, K. Aberer et al. (Eds): ISWC/ASWC 2007,
LNCS 4825, 2007, pp. 30-43.
Michel S. Lew, Nicu Sebe, Chabane Djeraba, and Ramesh Jain,“Content-Based Multimedia Information Retrieval: State of Art and

Copyright ⓒ GiRI (Global IT Research Institute)

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

[19]

[20]

[21]

205

Challenges”, ACM Transactions on Multimedia Computing,Communications and Applications, Vol. 2, No. 1, 2006, pp. 1-19.
Jonathon S. Hare, Patrick A. S., Sinclair, Paul H. Lewis, Kirk Martinez,
Peter G. B. Enser, and Christine J. Sandom, “Bridging the Semantic Gap
in Multimedia Information Retrieval”, 3rd European Semantic Web
Conference, Budva, Montenegro, 2006.
Myung-Eun Kim, In-Chul Jeong, and Joon-Myun Cho, “The Technical
Trends of Search Service for Smart TV”, Electronics andTelecommunications Trends, vol. 26, no. 4, 2011.
Won-Keun Yang, Ayoung Cho, Weon-Geun Oh, and Dong-Seok Jeong,
ETRI Journal, vol. 33, no. 4, Aug, 2011, pp. 589-599

Myung-Eun KIM received the B.S degree from Soonsil
University, Seoul, Korea, in 1996, and the M.S. incomputer science from Sogang University, Seoul, Rep.
of Korea, in 1998. She joined the TongYang Systems,
Seoul, Rep. of Korea in 1998. After three years, she
moved to Electronics and Telecommunications ResearchInstitute (ETRI), Daejeon, Rep. of Korea. She iscurrently working as a senior researcher of Smart TV
Media Research Team at ETRI, Daejeon, Rep. of Korea.
Her research interests include information retrieval
technology, service and platform technologies for Smart TV, and the SocialTV.
Joon-Myun CHO received his BS, MS and PhD in
mechanical Engineering from Korea Advanced Instituteof Science and Technology (KAIST) in 1993, 1995 and2006, respectively. He joined ETRI, Daejeon, Rep. of
Korea in 2007 and was involved with the URC(Ubiquitous Robotic Companion) project until 2011. He
is currently working as a project leader in smart searchand recommendation system development for smart TV
project. His research interests include ontology-basedknowledge base system and intelligent agent system.
Jeong-Ju YOO received the BS and MS degree in
Telecommunications in 1982 and 1984, respectively,from Kwangwoon University, Seoul, Korea. He received
the Ph.D degree in computing science from Lancaster
University, United Kingdom in 2001. Since 1984, he has
been a Principal Member of Technical Staff in the Next
Generation Smart TV Research Department ofElectronics and Telecommunications Research Institute(ETRI), Korea. He was a Head of MPEG Korea delgatesfrom 2007 to 2009 and he is a Director of Smart TV Media Research Team at
ETRI. His research interests are in the area of QoS, video coding, media
streaming, and multiscreen service technology of Smart TV.
Jin-Woo HONG received the BS and MS degree inelectronic engineering from Kwangwoon University,
Seoul, Korea, in 1982 and 1984, respectively. He also
received the Ph.D degree in computing engineering fromthe same university in 1993. Since 1984, he has beenwith ETRI, Daejeon, Korea, as a principal researcher,where he is currently a managing director of the next
generation Smart TV Research Department. From 1998
to 1999, he conducted research at Fraunhofer Institute in
Erlangen, Germany, as a visiting researcher. His research interests include
multimedia framework technology, broadcasting media and service, personalbroadcasting, realistic media, and platform technology of Smart TV.
Sang-Ha KIM received the B.S. degree from Seoul
National University, Seoul, Korea, in 1980, and the M.S.
in chemical physics and Ph.D. degrees in computerscience from University of Houston, Houston, USA, in
1984 and 1989, respectively. He joined the System
Engineering Research Institute (SERI) in Korean
Institute of Science and Technology (KIST), Seoul,
Korea, as a senior research scientist in 1990. After two
years, He moved into Chungnam National University, atwhich he is currently working as a professor.

Copyright ⓒ GiRI (Global IT Research Institute)