Communications in Computer and Information Science
88
Filip Zavoral Jakub Yaghob Pit Pichappan Eyas El-Qawasmeh (Eds.)
Networked Digital Technologies Second International Conference, NDT 2010 Prague, Czech Republic, July 7-9, 2010 Proceedings, Part II
13
Volume Editors Filip Zavoral Charles University Prague, Czech Republic E-mail:
[email protected] Jakub Yaghob Charles University Prague, Czech Republic E-mail:
[email protected] Pit Pichappan Al Imam University Riyadh, Saudi Arabia E-mail:
[email protected] Eyas El-Qawasmeh Jordan University of Science and Technology Irbid, Jordan E-mail:
[email protected]
Library of Congress Control Number: Applied for CR Subject Classification (1998): H.4, C.2, H.3, I.2, D.2, H.5 ISSN ISBN-10 ISBN-13
1865-0929 3-642-14305-9 Springer Berlin Heidelberg New York 978-3-642-14305-2 Springer Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. springer.com © Springer-Verlag Berlin Heidelberg 2010 Printed in Germany Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acid-free paper 06/3180 543210
Message from the Chairs
The Second International Conference on ‘Networked Digital Technologies’ (NDT2010)––co-sponsored by Springer––was organized and hosted by the Charles University in Prague, Czech Republic, during July 7–9, 2010 in association with the Digital Information Research Foundation, India. NDT2010 was planned as a major event in the computer and information sciences and served as a forum for scientists and engineers to meet and present their latest research results, ideas, and papers in the diverse areas of Web and Internet technologies, computer science, and information technology. This scientific conference included guest lectures and the presentation of 85 research papers in the technical session. This meeting was a great opportunity to exchange knowledge and experience for all the participants who joined us from all over the world and to discuss new ideas in the area of Web applications. We are grateful to the Charles University in Prague for hosting this conference. We use this occasion to express our thanks to the Technical Committee and to all the external reviewers. We are grateful to Springer for co-sponsoring the event. Finally, we would like to thank all the participants and sponsors.
May 2010
Filip Zavoral Mark Wachowiak Jakub Yaghob Veli Hakkoymaz
Preface
On behalf of the NDT 2010 conference, the Program Committee and Charles University in Prague, Czech Republic, we welcome you to the proceedings of the Second International Conference on ‘Networked Digital Technologies’ (NDT 2010). The NDT 2010 conference explored new advances in digital and Web technology applications. It brought together researchers from various areas of computer and information sciences who addressed both theoretical and applied aspects of Web technology and Internet applications. We hope that the discussions and exchange of ideas that took place will contribute to advancements in the technology in the near future. The conference received 216 papers, out of which 85 were accepted, resulting in an acceptance rate of 39%. These accepted papers are authored by researchers from 34 countries covering many significant areas of Web applications. Each paper was evaluated by a minimum of two reviewers. Finally, we believe that the proceedings document the best research in the studied areas. We express our thanks to the Charles University in Prague, Springer, the authors and the organizers of the conference.
May 2010
Filip Zavoral Mark Wachowiak Jakub Yaghob Veli Hakkoymaz
Organization
General Chairs Filip Zavoral Mark Wachowiak
Charles University, Czech Republic Nipissing University, Canada
Program Chairs Jakub Yaghob Veli Hakkoymaz
Charles University, Czech Republic Fatih University, Turkey
Program Co-chairs Noraziah Ahmad Yoshiro Imai Eyas El-Qawasmeh
University Malaysia Pahang, Malaysia Kagwa University, Japan Jordan University of Science and Technology, Jordan
Publicity Chair Maytham Safar
Kuwait University, Kuwait
Proceedings Chair Pit Pichappan
Al Imam University, Saudi Arabia
Table of Contents – Part II
Green Computing and Health Care Informatics Lot-Size Planning with Non-linear Cost Functions Supporting Environmental Sustainability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Markus Heck and Guenter Schmidt Electronic Health Record (Dossier M´edical Personnel) as a Major Tool to Improve Healthcare in France: An Approach through the Situational Semiotic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Christian Bourret Data Mining Technique for Medical Diagnosis Using a New Smooth Support Vector Machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Santi Wulan Purnami, Jasni Mohamad Zain, and Abdullah Embong
1
7
15
Rule Induction as a Technique in Genomic Analysis for Cancer . . . . . . . . M. Adib, Md. Mosharrof Hossain Sarker, S. Syed Ahmed, Ezendu Ariwa, and Fuzail Siddiqui
28
Clustering Analysis for Vasculitic Diseases . . . . . . . . . . . . . . . . . . . . . . . . . . Pınar Yıldırım, Cınar ¸ Ceken, ¸ Ka˘gan Ceken, ¸ and Mehmet R. Tolun
36
Analysis on the Characteristics of Electroencephalogram (EEG) and the Duration of Acupuncture Efficacy, Depending on the Stimulation at the Acupuncture Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jeong-Hoon Shin and Dae-Hyeon Park
46
Web Services Architecture, Modeling and Design Open Service Platform Based Context-Aware Services across Home . . . . . Jin-Neng Wu and Yu-Chang Chao
60
Web Services Testing Approaches: A Survey and a Classification . . . . . . . Mohamad I. Ladan
70
Benefits of Semantics on Web Service Composition from a Complex Network Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chantal Cherifi, Vincent Labatut, and Jean-Fran¸cois Santucci
80
Development Tool for End-to-End QoS Sensitive Frameworks and Technologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bogdan Iancu, Adrian Peculea, and Vasile Teodor Dadarlat
91
XII
Table of Contents – Part II
Learning-Based Call Admission Control Framework for QoS Management in Heterogeneous Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . Abul Bashar, Gerard Parr, Sally McClean, Bryan Scotney, and Detlef Nauck
99
A Multi-Objective Particle Swarm Optimization for Web Service Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hamed Rezaie, Naser NematBaksh, and Farhad Mardukhi
112
A Comparison between EJB and COM+ Business Components, Case Study: Response Time and Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Abedulhaq Abu-Kamel, Raid Zaghal, and Osama Hamed
123
Integration of Similar Location Based Services Proposed by Several Providers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Roula Karam, Franck Favetta, Rima Kilany, and Robert Laurini
136
Distributed and Parallel Computing A Central Management for Reducing Volumes of Data Harvested from Distributed Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Min-hwan Ok and Duck-shin Park A Trial Evaluation of Distributed Campus Network Environment Based on Comparison of Theoretical and Real Performance of Packet Flow Amount Using Video Transmission System . . . . . . . . . . . . . . . . . . . . . . . . . . Yoshiro Imai, Yukio Hori, Kazuyoshi Kawauchi, Mayumi Kondo, Toshikazu Sone, Yoshitaka Seno, Nobue Kawada, Shinobu Tada, Miho Yokoyama, and Rieko Miki Locality Preserving Scheme of Text Databases Representative in Distributed Information Retrieval Systems . . . . . . . . . . . . . . . . . . . . . . . . . . Mohammad Hassan and Yaser Hasan
145
152
162
Neural Networks Solving the Problem of Flow Shop Scheduling by Neural Network Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Saeed Rouhani, Mohammad Fathian, Mostafa Jafari, and Peyman Akhavan Artificial Neural Network-Based Algorithm for ARMA Model Order Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Khaled E. Al-Qawasmi, Adnan M. Al-Smadi, and Alaa Al-Hamami
172
184
Table of Contents – Part II
Efficient Substructure Preserving MOR Using Real-Time Temporal Supervised Neural Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Othman M.K. Alsmadi, Zaer. S. Abo-Hammour, and Adnan M. Al-Smadi
XIII
193
E-Learning Dynamic Properties of Knowledge Networks and Student Profile in e-Learning Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Radoslav Fasuga, Libor Holub, and Michal Radeck´y
203
An Optimized Cost-Benefit Analysis for the Evaluation in E-Learning Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Gianni Fenu and Massimiliano Picconi
215
Services Recommendation in Systems Based on Service Oriented Architecture by Applying Modified ROCK Algorithm . . . . . . . . . . . . . . . . . Agnieszka Prusiewicz and Maciej Zieba
226
Web Mining Mining Website Log to Improve Its Findability . . . . . . . . . . . . . . . . . . . . . . Jiann-Cherng Shieh
239
Mining Relations between Wikipedia Categories . . . . . . . . . . . . . . . . . . . . . Julian Szyma´ nski
248
Web Document Classification by Keywords Using Random Forests . . . . . Myungsook Klassen and Nikhila Paturi
256
Wireless Networks Minimizing the Effects of Multi-rate WLANs by Adapting Link Adaptation and Call Admission Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . M. Fatih T¨ uys¨ uz and Hacı A. Mantar Marmot: A Novel Low-Power Platform for WSNs . . . . . . . . . . . . . . . . . . . . P´eter V¨ olgyesi, J´ anos Sallai, S´ andor Szilv´ asi, Prabal Dutta, and ´ Akos L´edeczi Steerable Distributed Large-Aperture Audio Array Using Low-Power Wireless Acoustic Sensor Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ J´ anos Sallai, Akos L´edeczi, Xenofon Koutsoukos, and P´eter Volgyesi An Experimental Wireless Platform for Acoustic Source Localization . . . S´ andor Szilv´ asi and P´eter V¨ olgyesi
262
274
281
289
XIV
Table of Contents – Part II
A Simulation Discipline in OpenUP to Satisfy Wireless Sensor Networks Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Gian Ricardo Berkenbrock and Celso Massaki Hirata
295
Architecture for Interoperability between Instant Messaging and Presence Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Patricia E. Figueroa and Jes´ us A. P´erez
306
An Approach towards Time Synchronization Based Secure Protocol for Wireless Sensor Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Arun Kumar Tripathi and Ajay Agarwal
321
Intelligent Agent Based Systems, Cognitive and Reactive AI Systems Agent Behavior Diagram for Intelligent Agents . . . . . . . . . . . . . . . . . . . . . . Michal Radeck´ y, Petr Gajdoˇs, and Radoslav Fasuga Multi-agent System Environment Based on Repeated Local Effect Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kazuho Igoshi, Takao Miura, and Isamu Shioya
333
342
Hierarchical Model of Trust in Contexts . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jan Samek and Frantisek Zboril
356
Multi-Agent Linear Array Sensors Modeling . . . . . . . . . . . . . . . . . . . . . . . . . Benadda Belkacem and Fethi Tarik Bendimerad
366
A Framework for Intelligent Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Diana F. Adamatti
376
Agent-Based Digital Networking in Furniture Manufacturing Enterprises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Anthony Karageorgos, Dimitra Avramouli, Christos Tjortjis, and Georgios Ntalos Detecting Malwares in Honeynet Using a Multi-agent System . . . . . . . . . . Michal Szczepanik and Ireneusz J´ o´zwiak Reputation Model with Forgiveness Factor for Semi-competitive E-Business Agent Societies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Radu Burete, Amelia B˘ adic˘ a, and Costin B˘ adic˘ a RoadMic: Road Surface Monitoring Using Vehicular Sensor Networks with Microphones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Artis Mednis, Girts Strazdins, Martins Liepins, Andris Gordjusins, and Leo Selavo
381
396
402
417
Table of Contents – Part II
Model Generated Interface for Modeling and Applying Decisional Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Thomas Tamisier, Yoann Didry, Olivier Parisot, J´erˆ ome Wax, and Fernand Feltz
XV
430
Information and Data Management Directed Graph Representation and Traversal in Relational Databases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mohammad Beydoun and Ramzi A. Haraty
443
Transferring Clinical Information between Heterogeneous Hospital Database Systems in P2P Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Meghdad Mirabi, Hamidah Ibrahim, and Leila Fathi
456
Lowest Data Replication Storage of Binary Vote Assignment Data Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Noraziah Ahmad, Ainul Azila Che Fauzi, Roslina Mohd. Sidek, Noriyani Mat Zin, and Abul Hashem Beg The Location Path to Hell Is Paved With Unoptimized Axes: XPath Implementation Tips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Martin Kruliˇs and Jakub Yaghob Neighbour Replica Transaction Failure Framework in Data Grid . . . . . . . Noraziah Ahmad, Noriyani Mat Zin, Roslina Mohd. Sidek, Mohammad Fadel Jamil Klaib, and Mohd. Helmy Abd Wahab Mobile Agent-Based Digital Rights Management Scheme Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bartlomiej Zi´ olkowski and Janusz Stoklosa A Toolkit for Application Deployment on the Grid . . . . . . . . . . . . . . . . . . . Jie Tao and Holger Marten A Parallel Tree Based Strategy for Test Data Generation and Cost Calculation for Pairwise Combinatorial Interaction Testing . . . . . . . . . . . . Mohammad Fadel Jamil Klaib, Sangeetha Muthuraman, Noraziah Ahmad, and Roslina Mohd Sidek Integrity Check for Printed Binary Document Images . . . . . . . . . . . . . . . . . Dave Elliman, Peter Blanchfield, and Ammar Albakaa FACE – A Knowledge-Intensive Case-Based Architecture for Context-Aware Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Monica Vladoiu, J¨ org Cassens, and Zoran Constantinescu
466
474
488
496
503
509
523
533
XVI
Table of Contents – Part II
Application of Genetic Algorithm in Automatic Software Testing . . . . . . . Faezeh Sadat Babamir, Alireza Hatamizadeh, Seyed Mehrdad Babamir, Mehdi Dabbaghian, and Ali Norouzi Reliability Optimization of Complex Systems Using Genetic Algorithm under Criticality Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Samer Hamed, Belal Ayyoub, and Nawal Al-Zabin A Novel Technique for ARMA Modelling with Order and Parameter Estimation Using Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Zaer. S. Abo-Hammour, Othman M.K. Alsmadi, and Adnan M. Al-Smadi
545
553
564
Networks Metadata Management in P2P over Mobile Ad Hoc Network . . . . . . . . . . Pekka Kaipio and Jouni Markkula
577
Prediction of Network Delay with Variable Standard Deviation, Skewness and Kurtosis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Renads Safins
587
A New Computational Model to Evaluate the Quality of Perceptual Voice Using E-Model in VOIP Communications . . . . . . . . . . . . . . . . . . . . . . Meysam Alavi and Hooman Nikmehr
594
Modeling and Verification of RBAC Security Policies Using Colored Petri Nets and CPN-Tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Laid Kahloul, Karim Djouani, Walid Tfaili, Allaoua Chaoui, and Yacine Amirat GSM-Based Notification System for Electronic Pigeon Hole . . . . . . . . . . . . Mohd Helmy Abd Wahab, Ahmad Al’ Hafiz Riman, Herdawatie Abdul Kadir, Rahmat Sanudin, Ayob Johari, Roslina Mohd Sidek, and Noraziah Ahmad An Efficient Alert Broadcasting Scheme Considering Various Densities in VANET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hyunsook Kim New Secure Communication Protocols for Mobile E-Health System . . . . . M. Aramudhan and K. Mohan Determination of IDS Agent Nodes Based on Three-Tiered Key Management Framework for MANET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Marjan Kuchaki Rafsanjani and Arsham Borumand Saeid On Wind Power Station Production Prediction . . . . . . . . . . . . . . . . . . . . . . Jiˇr´ı Dvorsk´ y, Stanislav Miˇsa ´k, Luk´ aˇs Prokop, and Tadeusz Sikora
604
619
631 639
648 656
Table of Contents – Part II
Packet Count Based Routing Mechanism – A Load Balancing Approach in MANETS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bollam Nagarjun, L. Sathish, S. Santhosh Chaitanya, Md. Tanvir Ansari, and Shashikala Tapaswi A Comparative Study of Statistical Feature Reduction Methods for Arabic Text Categorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fouzi Harrag, Eyas El-Qawasmeh, and Abdul Malik S. Al-Salman A Scalable Framework for Serializable XQuery . . . . . . . . . . . . . . . . . . . . . . . Sebastian B¨ achle and Theo H¨ arder Artificial Neural Network Based Technique Compare with “GA” for Web Page Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ali Alarabi and Kamta Nath Mishra
XVII
669
676 683
699
Generating XForms from an XML Schema . . . . . . . . . . . . . . . . . . . . . . . . . . J´ an Kasarda, Martin Neˇcask´ y, and Tom´ aˇs Bartoˇs
706
Semantic Information Retrieval on Peer-to-Peer Networks . . . . . . . . . . . . . Mehmet Ali Ert¨ urk, A. Halim Zaim, and Selim Akyoku¸s
715
Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
727
Table of Contents – Part I
Information and Data Management A New Approach for Fingerprint Matching Using Logic Synthesis . . . . . . Fatih Ba¸sc¸ift¸ci and Celal Karaca
1
Extracting Fuzzy Rules to Classify Motor Imagery Based on a Neural Network with Weighted Fuzzy Membership Functions . . . . . . . . . . . . . . . . . Sang-Hong Lee, Joon S. Lim, and Dong-Kun Shin
7
Distributed Data-Mining in the LISp-Miner System Using Techila Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˇ unek and Teppo Tammisto Milan Sim˚
15
Non-negative Matrix Factorization on GPU . . . . . . . . . . . . . . . . . . . . . . . . . Jan Platoˇs, Petr Gajdoˇs, Pavel Kr¨ omer, and V´ aclav Sn´ aˇsel
21
Chatbot Enhanced Algorithms: A Case Study on Implementation in Bahasa Malaysia Human Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Abbas Saliimi Lokman and Jasni Mohamad Zain
31
Handwritten Digits Recognition Based on Swarm Optimization Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Salima Nebti and Abdellah Boukerram
45
A Framework of Dashboard System for Higher Education Using Graph-Based Visualization Technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Wan Maseri Binti Wan Mohd, Abdullah Embong, and Jasni Mohd Zain An Efficient Indexing and Compressing Scheme for XML Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I-En Liao, Wen-Chiao Hsu, and Yu-Lin Chen
55
70
Development of a New Compression Scheme . . . . . . . . . . . . . . . . . . . . . . . . . Eyas El-Qawasmeh, Ahmed Mansour, and Mohammad Al-Towiq
85
Compression of Layered Documents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bruno Carpentieri
91
Classifier Hypothesis Generation Using Visual Analysis Methods . . . . . . . Christin Seifert, Vedran Sabol, and Michael Granitzer
98
Exploiting Punctuations along with Sliding Windows to Optimize STREAM Data Manager . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lokesh Tiwari and Hamid Shahnasser
112
XX
Table of Contents – Part I
A Framework for In-House Prediction Markets . . . . . . . . . . . . . . . . . . . . . . . Miguel Velacso and Nenad Jukic Road Region Extraction Based on Motion Information and Seeded Region Growing for Foreground Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . Hongwu Qin, Jasni Mohamad Zain, Xiuqin Ma, and Tao Hai Process Mining Approach to Promote Business Intelligence in Iranian Detectives’ Police . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mehdi Ghazanfari, Mohammad Fathian, Mostafa Jafari, and Saeed Rouhani Copyright Protection of Relational Database Systems . . . . . . . . . . . . . . . . . Ali Al-Haj, Ashraf Odeh, and Shadi Masadeh Resolving Semantic Interoperability Challenges in XML Schema Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chiw Yi Lee, Hamidah Ibrahim, Mohamed Othman, and Razali Yaakob Some Results in Bipolar-Valued Fuzzy BCK/BCI-Algebras . . . . . . . . . . . A. Borumand Saeid and M. Kuchaki Rafsanjani
120
128
135
143
151
163
Security The Effect of Attentiveness on Information Security . . . . . . . . . . . . . . . . . . Adeeb M. Alhomoud
169
A Secured Mobile Payment Model for Developing Markets . . . . . . . . . . . . Bossi Masamila, Fredrick Mtenzi, Jafari Said, and Rose Tinabo
175
Security Mapping to Enhance Matching Fine-Grained Security Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Monia Ben Brahim, Maher Ben Jemaa, and Mohamed Jmaiel
183
Implementation and Evaluation of Fast Parallel Packet Filters on a Cell Processor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Yoshiyuki Yamashita and Masato Tsuru
197
On the Algebraic Expression of the AES S-Box Like S-Boxes . . . . . . . . . . M. Tolga Sakallı, Bora Aslan, Ercan Bulu¸s, Andac S ¸ ahin Mesut, Fatma B¨ uy¨ uksara¸co˘glu, and Osman Karaahmeto˘glu
213
Student’s Polls for Teaching Quality Evaluation as an Electronic Voting System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Marcin Kucharczyk
228
An Improved Estimation of the RSA Quantum Breaking Success Rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Piotr Zawadzki
234
Table of Contents – Part I
Mining Bluetooth Attacks in Smart Phones . . . . . . . . . . . . . . . . . . . . . . . . . Seyed Morteza Babamir, Reyhane Nowrouzi, and Hadi Naseri
XXI
241
Users’ Acceptance of Secure Biometrics Authentication System: Reliability and Validate of an Extended UTAUT Model . . . . . . . . . . . . . . . Fahad AL-Harby, Rami Qahwaji, and Mumtaz Kamala
254
Two Dimensional Labelled Security Model with Partially Trusted Subjects and Its Enforcement Using SELinux DTE Mechanism . . . . . . . . Jaroslav Jan´ aˇcek
259
A Roaming-Based Anonymous Authentication Scheme in Multi-domains Vehicular Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chih-Hung Wang and Po-Chin Lee
273
Human Authentication Using FingerIris Algorithm Based on Statistical Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ahmed B. Elmadani
288
Aerial Threat Perception Architecture Using Data Mining . . . . . . . . . . . . . M. Anwar-ul-Haq, Asad Waqar Malik, and Shoab A. Khan
297
Payload Encoding for Secure Extraction Process in Multiple Frequency Domain Steganography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Raoof Smko, Abdelsalam Almarimi, and K. Negrat
306
An Implementation of Digital Image Watermarking Based on Particle Swarm Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hai Tao, Jasni Mohamad Zain, Ahmed N. Abd Alla, and Qin Hongwu
314
Genetic Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Abdelwadood Mesleh, Bilal Zahran, Anwar Al-Abadi, Samer Hamed, Nawal Al-Zabin, Heba Bargouthi, and Iman Maharmeh
321
Multiple Layer Reversible Images Watermarking Using Enhancement of Difference Expansion Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Shahidan M. Abdullah and Azizah A. Manaf
333
Modeling and Analysis of Reconfigurable Systems Using Flexible Nets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Laid Kahloul, Allaoua Chaoui, and Karim Djouani
343
Using Privilege Chain for Access Control and Trustiness of Resources in Cloud Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jong P. Yoon and Z. Chen
358
XXII
Table of Contents – Part I
Social Networks Modeling of Trust to Provide Users Assisted Secure Actions in Online Communities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lenuta Alboaie and Mircea-F. Vaida
369
A Collaborative Social Decision Model for Digital Content Credibility Improvement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Yuan-Chu Hwang
383
Improving Similarity-Based Methods for Information Propagation on Social Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Francesco Buccafurri and Gianluca Lax
391
Approaches to Privacy Protection in Location-Based Services . . . . . . . . . . Anna Rohunen and Jouni Markkula Social Media as Means for Company Communication and Service Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Elina Annanper¨ a and Jouni Markkula A Problem-Centered Collaborative Tutoring System for Teachers Lifelong Learning: Knowledge Sharing to Solve Practical Professional Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Thierry Condamines Bridging the Gap between Web 2.0 Technologies and Social Computing Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Giorgos Kormaris and Marco Spruit
402
410
420
430
Ontology Using Similarity Values for Ontology Matching in the Grid . . . . . . . . . . . . Axel Tenschert Rapid Creation and Deployment of Communities of Interest Using the CMap Ontology Editor and the KAoS Policy Services Framework . . . . . . Andrzej Uszok, Jeffrey M. Bradshaw, Tom Eskridge, and James Hanna
444
451
Incorporating Semantics into an Intelligent Clothes Search System Using Ontology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ching-I Cheng, Damon Shing-Min Liu, and Li-Ting Chen
467
SPPODL: Semantic Peer Profile Based on Ontology and Description Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Younes Djaghloul and Zizette Boufaida
473
Table of Contents – Part I
Ontology Based Tracking and Propagation of Provenance Metadata . . . . Miroslav Vacura and Vojtˇech Sv´ atek
XXIII
489
Real Time Biometric Solutions for Networked Society A Real-Time In-Air Signature Biometric Technique Using a Mobile Device Embedding an Accelerometer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ J. Guerra Casanova, C. S´ anchez Avila, A. de Santos Sierra, G. Bailador del Pozo, and V. Jara Vera On-Demand Biometric Authentication of Computer Users Using Brain Waves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Isao Nakanishi and Chisei Miyamoto Encrypting Fingerprint Minutiae Templates by Random Quantization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bian Yang, Davrondzhon Gafurov, Christoph Busch, and Patrick Bours
497
504
515
Web Applications Method for Countering Social Bookmarking Pollution using User Similarities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Takahiro Hatanaka and Hiroyuki Hisamatsu
523
A Human Readable Platform Independent Domain Specific Language for WSDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Balazs Simon and Balazs Goldschmidt
529
A Human Readable Platform Independent Domain Specific Language for BPEL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Balazs Simon, Balazs Goldschmidt, and Karoly Kondorosi
537
Impact of the Multimedia Traffic Sources in a Network Node Using FIFO scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tatiana Annoni Pazeto, Renato Moraes Silva, and Shusaburo Motoyama
545
Assessing the LCC Websites Quality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Saleh Alwahaishi and V´ aclav Sn´ aˇsel
556
Expediency Heuristic in University Conference Webpage . . . . . . . . . . . . . . Roslina Mohd Sidek, Noraziah Ahmad, Mohamad Fadel Jamil Klaib, and Mohd Helmy Abd Wahab
566
Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
577
A Central Management for Reducing Volumes of Data Harvested from Distributed Sensor Networks Min-hwan Ok and Duck-shin Park Korea Railroad Research Institute 360-1 Woulam, Uiwang, Gyeonggi, Korea 437-757
[email protected]
Abstract. Potential for large scale data monitoring through sensor networks has been realized where factors of interest are compared for extended durations over different geographical locations. Further reducing volumes of the relations is required when the data are harvested from sensor networks distributed in a region or a nation, and a central management of the data is appropriate for the regional or national coverage. Condensed data are congregated in a regional server, for the remote user collects data from an event observed by several source nodes out of a locality or a closed boundary. For the empirical case we conducted a practice with an implemented system in a subway station. Keywords: Sensor Network, Stream Data, Distributed Databases Application.
1 Overview Sensor networks deployed near human lives are operated for better habitation in many facilities. An organization could maintain a few sensor networks for some interests, and such organizations could be located across several regions. In that environment the sensor networks would require a central management of data in a regional or nationwide scale. Each sensor captures the attribute states of a certain physical phenomenon by time, and nowadays, many applications use the sensors that produce a series of one variable such as temperature, humidity, density or pressure. Since the volume of sensor data becomes enormous if they are harvested nationwide, those data do not seem accommodated in a few database systems, in the form of raw data. For central management of data harvested from hundreds of sensor networks, a condensing method is necessary to reduce the amount of data. By condensing the data according to semantics shared among servers, the reduced amount of data would be manipulated to be transmitted and stored for central management. The underlying database is a specific database including TinyDB, and COUGAR[1], which are the common database management systems for sensor networks. An early system designed to provide a worldwide sensor database system is IrisNet[2]. It supports distributed XML processing over a worldwide collection of multimedia sensor nodes, and addresses a number of fault-tolerance and resource-sharing issues[3]. an XML extension technique called Stream Feed[4] has addressed the sensor data-stream and evaluated their technique against the large streaming data object. As the sampling interval decreases the number of clients reduced, and as the network F. Zavoral et al. (Eds.): NDT 2010, Part II, CCIS 88, pp. 145–151, 2010. © Springer-Verlag Berlin Heidelberg 2010
146
M.-h. Ok and D.-s. Park
is deeper the latency increased. They are natural results but a big obstacle in creating an application of sensor database with a nationwide coverage.
2 Reduced Volumes of Relations in Concept The conventional data flow model in a sensor network is a multiple-source single-sink model. This follows from the typical data querying applications where a remote user collect data from an event observed by several source nodes in a locality or a closed boundary, which may be referred to as the target sector. The query is initiated by the sink to the target sectors and is flooded within the boundary of the entire target sectors. As the sensor nodes is equipped with a little memory not enough to record data captured for a long time, commonly the sink node gather the data from sensor nodes for past references. A sensor network server has a sensor database of relations composed of data gathered from many kinds of senor nodes which are placed at multiple positions. For a sensor node of one kind, the data is not small if gathered for a long time, i.e., a month and there are several kinds of sensor nodes for habitat concern, for example, temperature, humidity, CO, CO2, and more. Potential for large scale data monitoring through sensor networks has been realized where factors of interest are compared for extended durations over different geographical locations. Thus in the case an organization maintains a few sensor networks,
500 450 400 350 300 250 200 150 100 50 0
0:05:39
9:37:41
11:38:04
14:38:42
17:09:21
18:09:27
23:10:42
Fig. 1. Captured and stored values by a CO2 sensor(Top) and data in a reduced size(Bottom)
A Central Management for Reducing Volumes of Data Harvested
147
the sensor database of the organization should contain data of multiple kinds of sensor nodes which each of them could be placed at multiple positions. In the case there are multiple such organizations spread in a region, the volume of relations should be huge in the sensor database of the region constituted with organization databases. Therefore reducing volumes of the relations is required when the data are harvested from sensor networks distributed in a region or a nation, and a central management of the data is appropriate for the regional or national coverage. In reducing the volume, some information may be lost except the useful ones. Exploiting semantics of data should be an adequate method. Let’s consider an example that a certain physical phenomenon should be attended, an air temperature higher than the 50 degrees centigrade in the rooms of the buildings in a region. In this example the data produced in the region should be huge and if a database of the servers covered the region, it would be easily overwhelmed. In this example, it is normal temperature below 50 degrees centigrade, but abnormal temperature over 50 degrees centigrade. It is no more meaningful for the regional fire brigades what high the temperature over 50 degrees centigrade is. As soon as the fire brigades are notified and they should turn out. Therefore whether the air temperature is over or below 50 could be the only interest of the regional command and then the central database may merely stores whether over-50 or not, for the regional command of the fire brigades. For the empirical case we conducted a practice with an implemented system in a subway station. The sensor networks are deployed on two floors, at the platform and
1.4 1.2 1 0.8 0.6 0.4 0.2 0
92 :5 0: 0
83 :5 3: 0
15 :5 0: 1
75 :5 0: 2
21 :6 3: 2
21 :6 3: 3
91 :6 3: 3
22 :6 0: 4
63 :6 0: 5
74 :6 0: 6
00 :7 0: 7
31 :7 0: 8
03 :7 3: 8
63 :7 0: 9
14 :7 0: 01
01 :8 3: 11
61 :8 0: 21
31 :8 3: 21
52 :8 3: 31
13 :8 0: 41
6 :3 8 3 :4 1
9 :5 8 0 :5 1
9 :4 8 0 :6 1
7 :0 9 0 :7 1
3 :2 9 3 :7 1
0 :3 9 0 :8 1
7 :2 9 3 :8 1
2 :4 9 3 :9 1
8 :4 9 0 :0 2
7 :5 9 0 :1 2
9 :0 0 4 :1 2
7 :2 0 1 :3 2
Fig. 2. Captured and stored values by a Dust sensor(Top) and data in a reduced size(Bottom)
148
M.-h. Ok and D.-s. Park
140 120 100 80 60 40 20 0 0:05:41
23:10:38
Fig. 3. Captured and stored values by a CO sensor(Top) and data in a reduced size(Bottom)
at the waiting room of a subway station. To reduce the data generation rate and power consumption, the intervals between sensing and sleeping are preset by the kinds of sensor nodes. Sensor nodes are deployed and connected to a sensor network server through a micro gateway. Temperature and humidity are sensored under field-based monitoring. These sensors have their own batteries. Dust sensors and CO2 sensors are deployed at particular positions and they use external power due to their fast consumptions. Each kind of sensors transmits with Zigbee-based communication.
3 Composite Relations in an Empirical Case The physical phenomenon could be more easily detected by a combination of multiple kinds of sensors. There are various physical phenomena could be detected by sensors. In a habitat concern, a set of sensors are emplaced to detect those that should be early detected to be alarmed for fine livings. In an application of air-contamination monitoring in the subway stations, several factors are sensored including temperature, humidity, carbon monoxide(CO), carbon dioxide(CO2), dust(PM10), and smoke. Because of energy shortage, the sensors capture values between intervals, as shown in
A Central Management for Reducing Volumes of Data Harvested
149
Fig. 1. These values are captured at a subway station for a day. Common components for each sensor node are ATmega 128L, Chipcon CC2420, and SMA antenna. The sensor nodes with the specific sensor component require quick updates in monitoring, such as Smoke sensor, have external powers for short sampling intervals. An organizational server, Station Server, has raw data contained in its database. We call converting a value into one of separations to reduce volume condensing, at some resolution that continues maintaining its semantic meaning. Every a timeinterval, the values are condensed at respective resolutions and sent to a regional server. The resolutions of condensing are 2%(10/500) for CO2 values and 0.5%(7/1400) for Dust values, respectively. Further, there are 7 value changes at the resolution of condensing for CO2 thus only 7 tuples are sent to the regional server for this sensor. In Fig. 2, 32 value changes are at the resolution of condensing for Dust thus 32 tuples are sent. Capturing CO value and Smoke value are important in sensing the occasion of fire. In the Fig. 3 and 4, a couple of 1 tuple are sent at respective resolutions for CO and Smoke for the sensors. Due to their importance, the preset time-intervals are modified into the shorter ones by the sink node once a value change is detected. Those of relevant factors such as temperature are also modified.
1
0 0:05:42
23:10:40
Fig. 4. Captured and stored values by a Smoke sensor(Top) and data in a reduced size(Bottom)
150
M.-h. Ok and D.-s. Park
Fig. 5. Captured and stored values by a humidity sensor and a temperature sensor
Some factors may have the same sampling interval. In Fig. 5, the humidity is represented as the upper line and the temperature is represented as the lower line. They are gathered separately by the sink nodes but appear in one relation at the organizational server. The captured values are condensed at the same resolution, and become ones appropriate to join to composite relations. Two parameters should be common if two attributes are in one relation. The resolution of condensing should be the same for the first, and the sampling time should be the same for the second. The former is not necessarily the same between factors but could be converted within the resolution continues not losing its semantic meaning. However the latter is not suitable in the same ones, since an occurrence detection should not be prolonged on some specific factors including Smoke. This is one hard problem in joining for composite relations.
4 Summary The raw data is contained in the sensor database of an organization. They require a vast storage space for aggregate data of a month. Condensed data are congregated in a regional server, for the remote user collects data from events observed by several source nodes out of a locality or a closed boundary. It necessitates a central management of data harvested from distributed sensor networks by converting values but maintaining their semantic meanings. The reduced amount of data lessens transmissions over network, and should be also helpful in exchanging the condensed data. This work is not for a management of distributed databases but for a central management of data. The reducing rates are variable by condensing resolutions applicable however, many values are in the same separations at a resolutions thus those values are represented by one value. The reducing rate would be higher as the values of the factor changed with slower slopes. Over the half of habitat factors has such a property.
A Central Management for Reducing Volumes of Data Harvested
151
References 1. Henricksen, K., Robinson, R.: A Survey of Middleware for Sensor Networks: State-of-theArt and Future Directions. In: International Workshop on Middleware for Sensor Networks, pp. 60–65. ACM, New York (2006) 2. Campbell, J., Gibbons, P.B., Nath, S.: IrisNet: An Internet-Scale Architecture for Multimedia Sensors. In: Annual ACM International Conference on Multimedia, pp. 81–88. ACM, New York (2005) 3. Deshpande, A., Nath, S., Gibbons, P.B., Seshan, S.: Cache-and-query for wide area sensor databases. In: ACM SIGMOD International Conference, pp. 503–514. ACM, New York (2003) 4. Dickerson, R., Lu, J., Lu, J., Whitehouse, K.: Stream Feeds - An Abstraction for the World Wide Sensor Web. In: Floerkemeier, C., Langheinrich, M., Fleisch, E., Mattern, F., Sarma, S.E. (eds.) IOT 2008. LNCS, vol. 4952, pp. 360–375. Springer, Heidelberg (2008)
A Comparative Study of Statistical Feature Reduction Methods for Arabic Text Categorization Fouzi Harrag1, Eyas El-Qawasmeh2, and Abdul Malik S. Al-Salman3 1
Compt Sci Department, College of Engineering, Farhat ABBAS University, Setif, 19000, Algeria,
[email protected] 2 Software Engineering Dept., Jordan University of Science and Technology, Irbid, 22110, Jordan,
[email protected] 3 College of computer & Information Science, King Saud University, Riyadh, 11543, Saudi Arabia,
[email protected]
Abstract. Feature reduction methods have been successfully applied to text categorization. In this paper, we perform a comparative study on three feature reduction methods for text categorization, including Document Frequency (DF), Term Frequency Inverse Document Frequency (TFIDF) and Latent Semantic Analyses (LSA). Our feature set is relatively large (since there are thousands of different terms in different texts files). We propose the use of the previous feature reduction methods as a preprocessor of Back-Propagation Neural Network (BPNN) to reduce the input data on training process. The experimental results on an Arabic data set demonstrate that among the three dimensionality reduction techniques proposed, TFIDF was found to be the most effective in reducing the dimensionality of the feature space. Keywords: Feature Reduction, Back-Propagation Neural Network, Arabic Text Categorization, DF, TFIDF, Latent Semantic Analyses.
1 Introduction An important component of Information Retrieval (IR) is the effectiveness of “text classification (TC)” or “automated text categorization” [8]. In TC, an initial dataset of pre-classified documents is partitioned into a training dataset and a test dataset that are subsequently used to construct and evaluate classifiers. Several methods have been used for text classification [8] such as: Support Vector Machine (SVM), KNearest Neighbor (KNN), Artificial Neural Networks, Naïve Bayes probabilistic Classifier, and Decision Trees. A common and often overwhelming characteristic of text data is its extremely high dimensionality. The high dimensionality posed an open F. Zavoral et al. (Eds.): NDT 2010, Part II, CCIS 88, pp. 676–682, 2010. © Springer-Verlag Berlin Heidelberg 2010
A Comparative Study of Statistical Feature Reduction Methods
677
challenge for classification algorithms [11]. Therefore, it becomes critical to apply effective dimensionality reduction techniques (DR), including feature selection and extraction. The goal of this paper is to present and compare results obtained against Arabic text collection using feature reduction techniques with Back-Propagation Neural Network (BPNN) algorithm. The remainder of this paper is organized as follows: Section 2 is a state of the art of feature reduction related works. The detail algorithm of Back-Propagation neural network is described in Section 3. Section 4 introduces the three used feature reduction techniques. Experiment results are given in Section 5 and Section 6 is reserved for conclusion.
2 Features Reduction: State of the Art Feature reduction is at least as important as the choice of the induction algorithm in text categorization. Accordingly, many studies to evaluate the feature reduction metrics have been done in recent years. Yang et. al. [12] evaluates five of the most popular feature selection metrics on the Reuters and Ohsumed datasets. In this study, KNN and LLSF are used as the classification algorithms instead of SVM. Only global policy is used and the metrics are evaluated in terms of precision. Few researchers have been working on Feature reduction for Arabic text categorization. Syiam et. al. [9] experimental results show that the suggested hybrid method of statistical and light stemmers is the most suitable stemming algorithm for Arabic language and gives generalization accuracy of about 98%. Mesleh [6] described a SVM based text classification system for Arabic language articles. This classifier uses CHI square method as a feature selection method. The system effectiveness for Arabic data set in term of F-measure is 88.11. Duwairi et. al. [1] present and compare three feature reduction techniques that were applied to Arabic text. The techniques include stemming, light stemming, and word clusters. Experiments results show that the light stemmed vectors superseded the other three representations in terms of classification accuracy. Harrag et. el [3] used the Singular Value Decomposition (SVD) to select the most relevant features for the classification. The experimental results show that ANN model using SVD achieves 88.33% which is better than the performance of basic ANN which yields 85.75% on Arabic document classification. Zahran et. al. [14] implemented Radial Basis Function (RBF) networks with Particle Swarm Optimization (PSO) algorithm as feature selection technique and they compared to the document frequency, tf×idf and Chi-square statistic algorithms. Theirs results on an Arabic dataset show the superiority of the PSO algorithm.
3 Text Classification Using Neural Networks Neural network is a popular classification method. It can handle linear and nonlinear problems for text categorization. Both of linear and nonlinear [8] classifiers can achieve good results [13]. Neural networks have been widely applied by many researchers to classify the text documents with different types of feature vectors. Wermeter [10] has used the document title as the vectors to be used for a document categorization. Lam et al. [4] have used the principal component analysis (PCA)
678
F. Harrag, E. El-Qawasmeh, and A.M.S. Al-Salman
method as a feature reduction technique of the input data to the neural networks. Using neural networks, the problem of text categorization can be solved by using back-propagation. The classification decision for any document of reasonable size is based on the combined evidence from many sources. Each word is a source to classify a document [3]. In this paper, a three layer feed-forward neural network is trained with back-propagation algorithm. The inputs are the components of the document vector, and the outputs are the document categories.
4 Feature Reduction Techniques 4.1 Document Frequency In the DF method, terms are ranked based on the document frequency (DF) of each term within a document group. The set of terms which are good representatives of the category topics are used by most documents belonging to that category. The important terms are those that appear frequently within a group of documents belonging to the same category [4]. 4.2 TFIDF Method TFIDF method is the product of the term occurrence frequency (TF) and the inverse document frequency (IDF). The inverse document frequency of the term is commonly defined as [7]: IDFi=log (N/n), where N is the number of documents in the document set, and n is the number of documents in which the ith term appears. For term reduction, the terms are ranked according to their TFIDF values, and terms with the highest TFIDF values are selected to form the reduced feature set [4]. The terms that are concentrated in a few documents are more helpful in distinguishing between documents with different topics. 4.3 Latent Semantic Analysis (LSA) LSA is a dimension reduction method. It automatically computes a subspace containing meaningful semantic associations which is much smaller than the initial space. It uses a truncated SVD of the co-occurrence term-document matrix. The correlation matrix of the words is produced by multiplying the co-occurrence matrix by its transpose. The SVD is then performed on the correlation matrix to obtain the most informative singular vectors that define the latent semantic subspace. The different steps to compute the SVD are the following: First, the word-document cooccurrence matrix, noted A is computed. Next, the SVD technique is applied on A. A can be decomposed into the product of three other matrices A=U S VT where U and V are the matrices of left and right singular vectors matrices and S is the diagonal matrix of singular values, i.e. the non-negative square root of the eigenvalues of A.AT. The first columns of U and V define the orthonormalized eigenvectors associated with the non-zero eigenvalues of A.AT and AT.A respectively. By choosing the n largest singular values, the space can be furthermore reduced, eliminating some of the noise due to style or non-informative words An = Un Sn VnT. In this n-dimensional space the ith word wi is encoded: xi = ui Sn / ||ui Sn||, where ui Sn is the ith row of the matrix Un Sn.
A Comparative Study of Statistical Feature Reduction Methods
679
The LSA selects the p best factors and rejects negligible information contained in the data [3].
5 Experiments After executing Stop words elimination and Stemming as preprocessing routines on all documents of the corpus, we start the construction of features vectors by applying term reduction [12] and term weighting [7] processes on the stemmed vectors. Finally, the classifier is constructed by learning the characteristics of every category from a training set of documents. Once a classifier has been built, its effectiveness may be tested by applying it to the test set and checking the degree of correspondence between the decisions of the classifier and those encoded in the corpus. 5.1 Data Set We use an Arabic corpus to evaluate our classifier. This corpus is a set of prophetic traditions or “Hadiths’ (Say’s of the Prophet Mohammed 'Peace Be Upon Him') collected from the Prophetic encyclopedia (Alkotob Altissâa, “The Nine Books”) [2]. It is characterized by the specialization of its domain “Hadith”. It includes 453 documents distributed over 14 categories. Table 1 represents the number of documents for each category for this corpus. Table 1. Number of documents per category for the second corpus Category name Faith Koran Knowledge Crimes Al-Djihad Good Manners Past Generations Biography Judgments Worships Behaviors Food Clothes Personal States
# of training documents 31 32 30 30 32 39 25 25 32 31 33 39 42 32
First, we have removed the Arabic stop words and we have applied a Stemming process. We then have applied DF, TFIDF and LSA reduction techniques. Next, we have used one third of the Arabic data set for testing the classifier and two thirds for training the TC classifier.
680
F. Harrag, E. El-Qawasmeh, and A.M.S. Al-Salman
5.2 Evaluation Criteria We employ the F1 measure [8] to evaluate the performance of text classifiers. This measure combines recall and precision in the following way: F-measure:
F = (2.R.P)/(R + P)
(1)
Where the Recall R is the total of correct classes found divided by the total of correct classes and the Precision P is the total of correct classes found divided by the total of classes found. For ease of comparison, we summarize the F1 scores over the different categories using the Macro-averages of F1 scores [8]. The MacroF1 gives equal weight to every category, regardless of its frequency. 5.3 Preprocessing and Input Data for the Neural Network The goal of our experiments is to evaluate the performance of Back-Propagation Neural Network algorithm (BPNN) on classifying Arabic text using feature reduction techniques described in Section 4. After the stemming and stopping processes of the terms in each document, we will represent them as the document-term frequency matrix (Docj ×TfIdfjk). Docj is referring to each document that exists in the corpus where j = 1…n. DF, TFIDF and LSA as feature reduction techniques have been used to reduce the original feature vectors into a small number of vectors. In our experiments, we compare the performance by varying the number of dimension k, the neural network’s input nodes number is equal to the dimension of the document vectors. For DF, the dimensions is range from 9 to 615. For TFIDF, the range is from 13 to 997. For LSA, the range is from 50 to 530. The number of hidden nodes is 30 and the number of the output nodes is 14. Some others parameters used in our network are shown in Table 3. The trial and error approach has been used to find the suitable number of hidden layers that provide good classification accuracy based on the input data to the neural networks. Table 2. The error back-propagation neural network Parameters NN Parameters Learning rate (q) Momentum rate(a) Number of iteration(I) Mean Square Error (MSE)
Value 0.050 0.010 1000 0.001
5.4 Results and Analyses The categorization performances are given in Figure 1 and Figure 2. Figure 1 shows the Macro-Avg F1 measure for every category. F1 measure reaches its highest values of 71% 75% and 80% for the Al-Djihad, the Crimes and the Koran categories LSA, TFIDF and DF respectively. The lowest values are: 20% for the Faith category for LSA, 33% for the Biography category for TFIDF and 37% for the Crimes category for DF.
A Comparative Study of Statistical Feature Reduction Methods
681
Fig. 1. Comparison of classification results for BPNN with feature reduction model
From Figure 2, we can see that the Macro-Avg F-measure of the BPNN with all features (dimensions=1063) is equal to 0.48. For F-measure of BPNN using LSA, when the dimensions are less than 80, the F-measure of BPNN using LSA is better than the F-measure of BPNN using DF and TFIDF but it remains lower than those of All Features and at the eleventh dimension (d=250), it gets the best performance of 0.53. The two curves of DF and TFIDF tends to degrade at the last dimension, contrary to the LSA curve that continues to progress with the increasing number of dimensions. The reduced size of the vectors is greatly decrease the computational (training) time in the back-propagation neural network. The computational time on neural network with features reduction methods is increased when the number of the dimension is increased. The Computation time of BPNN with DF method is equal to (86.75 s) at the dimension d=211. For BPNN with LSA method, this time is equal to (75.2 s) at d=250 and for BPNN with TFIDF method is equal to (67.15 s) at d=436. All these values are much faster than the computation time of BPNN model with all features (2168.96 s).
Fig. 2. Categorization performance according to the number of dimension
682
F. Harrag, E. El-Qawasmeh, and A.M.S. Al-Salman
6 Conclusion In this paper, some shallow statistic techniques for feature reduction were proposed and applied to Arabic text categorization using back-propagation neural network. The introducing of dimensionality reduction methods not only reduces the number of dimensions drastically, but also overcomes the problems existing in the vector space model commonly used for text representation. The experimental results show that BPNN enhances the performance of text categorization and Feature reduction techniques further improves its accuracy and efficiency.
References 1. Duwairi, R.M., Al-Refai, M.N., Khasawneh, N.: Feature Reduction Techniques for Arabic Text Categorization. Journal of the American society for information science and technology 60(11), 2347–2352 (2009) 2. Encyclopedia of the Nine Books for the Honorable Prophetic Traditions, Sakhr Company, http://www.Harf.com 3. Harrag, F., El-Qawasmeh, E.: Neural Network for Arabic Text Classification. In: The Second International Conference on the Applications of Digital Information and Web Technologies (ICADIWT 2009), pp. 778–783 (2009) 4. Lam, S.L.Y., Lee, D.L.: Feature Reduction for Neural Network Based Text Categorization. In: Sixth International Conference on Database Systems for Advanced Applications (DASFAA 1999), pp. 195–202 (1999) 5. Larkey, L., Ballesteros, L., Connell, M.E.: Improving Stemming for Arabic Information Retrieval: Light Stemming and Co-occurrence Analysis. In: Proceedings of SIGIR 2002, pp. 275–282 (2002) 6. Mesleh, A.A.: Chi Square Feature Extraction Based Svms Arabic Language Text Categorization System. Journal of Computer Science 3(6), 430–435 (2007) 7. Salton, G., Buckley, C.: Term-weighting Approaches in Automatic Text Retrieval. Information Processing and Management 24(5), 513–523 (1988) 8. Sebastiani, F.: Machine Learning in Automated Text Categorization. ACM Computing Surveys 34(1), 1–47 (2002) 9. Syiam, M.M., Fayed, Z.T., Habib, M.B.: An Intelligent System for Arabic Text Categorization. International Journal of Intelligent Computing and Information Sciences 6(1), 1–19 (2006) 10. Wermeter, S.: Neural Network Agents for Learning Semantic Text Classification. Information Retrieval 3(2), 87–103 (2000) 11. Witten, I.H., Frank, E.: Data mining: practical machine learning tools and techniques, 2nd edn. Morgan Kaufmann, San Francisco (2005) 12. Yang, Y., Liu, X.: A Re-examination of Text Categorization Methods. In: 22nd ACM International Conference on Research and Development in Information Retrieval, SIGIR 1999, pp. 42–49. ACM Press, New York (1999) 13. Yu, B., Zong-ben, X., Cheng-hua, L.: Latent Semantic Analysis for Text Categorization Using Neural Network. Knowledge-Based Systems Journal 21, 900–904 (2008) 14. Zahran, B.M., Kanaan, G.: Text Feature Selection using Particle Swarm Optimization Algorithm. World Applied Sciences Journal 7 (Special Issue of Computer & IT), 69–74 (2009)
A Comparison between EJB and COM+ Business Components, Case Study: Response Time and Scalability Abedulhaq Abu-Kamel, Raid Zaghal, and Osama Hamed Dept of Computer Science, Al-Quds University Software Development Directorate, Hulul Business Solutions Palestine
[email protected], {zaghal,ohamed}@science.alquds.edu,
[email protected] http://www.alquds.edu/
Abstract. Most distributed system architectures are designed as a three-tier systems consisting of a thin-client, middleware and a database. The overall performance of such systems depends on the performance of each tier individually and the overhead incurred by the collaboration between these three tiers. Nowadays, the two most popular middleware systems are: Microsoft’s .NET platform and Sun’s Java 2 Enterprise Edition (J2EE) platform. In J2EE, the middle tier infrastructure is called Enterprise JavaBeans (EJB) and in the .NET framework, it is called Component-Oriented Middle-Tier (COM+). Usually, the middle tier provides the business logic (any code that is not specifically related to storing and retrieving data, or formatting data for display to the user) and the performance of this tier is crucial to the overall performance of the distributed system. In this paper, we will measure via real experimentation the performance of the middle-tier (business logic) of the two platforms, namely: EJB3 and COM+ 1.5, in terms of response time and scalability. Then we compare and analyze the performance of each technology under different workload scenarios.
1 Introduction Computer software had rapidly increased and developed specially in Distributed Software Systems, these systems need connectivity, ignoring whether these systems are homogeneous or heterogeneous; a middleware is needed, the performance of the middleware affects the overall system performance. Within just few years, the Windows platform has evolved from personal computing operating system to a complete Enterprise solution. Distributed applications grew from the traditional client-server approach to threetier applications, since the client-server approach had some problems such as fatclients—when most or all of the code is written on the client side, which requires downloading all data to the client to fulfill any business task. Therefore, the traffic on network becomes overloaded when the system has a large number of clients and thus affects the system’s performance severely. F. Zavoral et al. (Eds.): NDT 2010, Part II, CCIS 88, pp. 123–135, 2010. © Springer-Verlag Berlin Heidelberg 2010
124
A. Abu-Kamel, R. Zaghal, and O. Hamed
The three-tier approach was proposed as a solution for client-server problems. It consists of the presentation tier, the business tier (or business logic), and the database tier. This approach offers more advantages such as performance, scalability, maintenance, security, flexibility and more freedom. Figure (1) shows the three-tier architecture. Protocol
HTTP Presentation Tier
Business Tier
HTML Firewall Database Tier
Fig. 1. Distributed architectures are typically based on three tiers
A presentation tier is responsible for working with clients (users), it accepts an HTTP requests from a web browser and returns an HTML page that browser can then display. The business tier is where much of the business logic is implemented, since the business tier lies between the presentation tier and the database tier, it is often called the middle tier. Business logic often requires expensive resources, such as database connections, threads, TCP/IP connections, and message queue connections. These resource requirements would normally make it difficult to support a large number of clients at any one time, a requirement of most e-Commerce applications. Both J2EE and the .NET framework business tiers include a sophisticated middle tier infrastructure that supports resource sharing among clients. This infrastructure is critical to supporting large numbers of clients, and thereby achieving high system throughput. In J2EE, this middle tier infrastructure is called Enterprise JavaBeans (EJB). In the .NET framework, it is called COM+. In this study, we consider specific versions of middle tier namely EJB3 and COM+ 1.5. In this work, an emulation approach will be used to do a comparison among EJB3 server and COM+ 1.5 to identify the performance in terms of response time and scalability for the business tier in both frameworks. This work will help software engineers and developers to choose the right platform for their new distributed applications to fit their business requirements.
2 Background Performance is defined as an indicator of how well a software system or its component can meet the timeline requirements, and this is usually measured in terms of response time and throughput. There are two important dimensions of software performance timelines: responsiveness and scalability. Responsiveness is the ability of a system to meet its objectives for response time or throughput, while Scalability is its ability to continue to meet these objectives as the demand for the software functions increases.
A Comparison between EJB and COM+ Business Components, Case Study
125
Meeting performance requirements is not enough for stringent performance application, but also must be able to scale gracefully to changing patterns of use as well as increasing in demand. Studying performance can be estimated or measured by studying the system’s architecture. And performance failures can be avoided early in the design process. Vast numbers of performance modeling/testing studies were done on JAVA EE and .NET technologies, among these [13][14]. Even the field of EJB and its performance has been much researched [2][3][9], but these researches focused on how to improve the performance of EJB systems in general. This work will focus on examining the specific performance aspects of EJB systems and gives quantitative results. Most of previous researches focused on one particular Application Server [2][7], whereas other works focused on making a comparison between different vendor’s products [4][5]. Some researches modified the Application Server configuration parameters, that includes parameters such as the number of server threads and the number of beans deployed, some of these researchers examined the effects of changes in the hardware architecture. Many researches where conducted in this area with different objectives, such as which EJB system was used, which type of beans were used, whether local or remote calls were made, which transactional or security options were utilized, or changes to any other software specific parameters. The EJB server manages one or more EJB containers. The container is responsible for providing component pooling and lifecycle management, client session management, database connection pooling, persistence, transaction management, authentication, and access control. COM is a standard; it is platform independent, distributed, object-oriented system for creating binary software components that can interact with each other. COM components can be written in any programming language. COM+ is an extension to COM, and it is possible to use COM objects in COM+, it was developed as a standard for designing distributed, multi-tier applications. In COM+ it is possible to move and copy components. Jeremy Singer [1], conducted a comparative study JVM vs. CLR. He found that CLR and JVM Compilers are approximately the same regarding compilations and executing object oriented programs.
3 Methodology and Testbed First, we will define the infrastructures of EJBs and COM+ and the similarities and differences between them. COM+ is an extension of Component Object Model (COM), Microsoft's strategic building block approach for developing application programs. COM+ is both an object-oriented programming architecture and a set of operating system services. It adds to COM a new set of system services for application components while they are running, such as notifying them of significant events or ensuring they are authorized to run. COM+ is intended to provide a model that makes it relatively easy to create business applications that work well with the Microsoft Transaction Server (MTS) in a Windows NT or subsequent systems. It is viewed as
126
A. Abu-Kamel, R. Zaghal, and O. Hamed
Microsoft's answer to the Sun Microsystems-IBM-Oracle approach known as Enterprise JavaBeans (EJB). Enterprise JavaBeans (EJB) technology is the server-side component architecture for Java Platform Enterprise Edition (Java EE). EJB technology enables rapid and simplified development of distributed, transactional, secure, and portable applications based on Java technology. To measure the performance (Response Time) of these two middle tiers (COM+ 1.5 & EJB3) we will build two distributed web applications that use the same hardware and software, but differ at the middle tier, first we will use COM+ and then EJB as a middle tier (or business tier). Hardware Components: Four Computers with the following properties or higher, CPU Pentium 4 (3.00 GHz), RAM 1 GB DDR1, Network card 100Mbps, 8-port switch, and STP wires for network connections. Software Components: Windows Server 2003, Windows XP, Oracle 10g (Server and Client), Java platform, JDeveloper, OC4J, Visual Studio 2005, .NET Framework 2.0, and LoadRunner 8.1 [12]. At this experiment a compatible presentation, database, and middle tiers are used, EJB/JAVA and COM+/.NET platforms are used as an environment to deploy the business logics at each one. For the presentation tier, HTML with Suitable Scripting Language is used. For the Database tier, Oracle10g is used since oracle 10g is compatible with both Java and .NET platforms. To achieve the comparison two parts of the experiment were developed (these two parts must be equivalent at each tier). In the first part of the experiment, the COM+/.NET platform was used as a middle tier and the experiment was repeated several times. At each attempt, the workload was increased at both the presentation tier (increasing the number of users) and the database tier. A log file keeps track of response times for each attempt. Figure (2) illustrates the configuration. Presentation Tier
HTML + ASP.NET
Business Tier
COM+/.NET
Database Tier Oracle 10g
Fig. 2. The architecture of COM+ experiments
In the second part, the experiment is repeated using the same parameters (Hardware and software) but we replaced the COM+/.NET platform with EJB/J2EE platform. We also used the JSP as the scripting language for the presentation tier since it is compatible with Java (most Web sites built on Java use JSP). This experiment represents a real distributed application as seen in any business installation. The configuration is shown in Figure (3).
A Comparison between EJB and COM+ Business Components, Case Study
Presentation Tier
HTML + JSP
Business Tier
EJB/ J2EE
127
Database Tier Oracle 10g
Fig. 3. The architecture of EJB experiments
After each run, all relevant readings from the experiment were logged and analyzed. Then the differences in performance among these middle tiers were noticed. This experiment represents a simple university registration system, implemented as a distributed web application using both middle tiers. Table (1) summarizes the software that we have used at each tier. Table 1. Software used at each application in our experiment Presentation Tier Experiment 1 First application Experiment 2 Second application
HTML with ASP.Net as scripting language
HTML with JSP as scripting language
Business Tier
COM+ / VB.NET
EJB using JDeveloper as integration development environment
Database Tier
Oracle10g Version 10.2.0.1.0
Oracle10g Version 10.2.0.1.0
Since we want to make a judgment on the performance of these technologies, the implementation was equivalent in both technologies. All transactions took place at the business tier. In such application, there are many transactions, and the following scenarios describe the transaction model for our experiment. The user chooses the student ID, department ID, and semester from drop down lists, then he/she edits the year. After that he/she presses the (insert) button. The values that were chosen are inserted into the table (regest). The student will be enrolled into all
128
A. Abu-Kamel, R. Zaghal, and O. Hamed
courses from the selected department. The application gives a random grade for each course for this student, and inserts this data into the (semester_courses) Table. In the scenario just describes, many transactions took place to complete one process; If the application has 5 departments in the (dept) table, 300 students in the (student) table, and 10 courses for each department in the (courses) table, the application deal with (300*10*5 = 15,000) records to be able to insert into the (semester_courses) table for the student. Therefore, in one process there are a lot of transactions for the CPU to execute. Furthermore, the application must process many transactions for each student, many transactions for the selected departments, and many transactions for the selected semesters. After that they will be inserted into (semester_courses) Table. This is for one user only. Naturally, the workload will be multiplied when more than one user performs this scenario concurrently.
4 Experiment Results We will take the COM+ experiment as an example, and the same applies for EJB experiment. The experiment consists of three tiers, presentation, business, and database tiers. Thus, the application is distributed on more than one machine (the database server, the COM+ server, the Web server + application proxy from the COM+ components, and the client machine that runs the LoadRunner program). We open the http page on the client machine; the client requests the web page from the web server, which responses and opens the page on the client. The user chooses from drop-down lists; student, department, and semester. Then, he edits the year of registration and presses the (insert) button. The client sends these commands to the web server which has the web page and to COM+ components as a proxy, the connection among application proxy and COM+ server will be established since the COM+ server has all methods of our application. Also, the COM+ server establishes a connection with the database server whenever the transaction needs to access the database. Most transactions happen on the COM+ server since it has all the methods (business logic), and it is responsible for the connection to database and web server. Furthermore, if we want to add security to the application, it will be deployed on the COM+ server (as a property of the COM+ components). Since we aim to test performance we will implement more than one scenario. 4.1 Scenario 1 (Loading Page) In this scenario we will just load an empty page without any transactions (the page doesn’t contain any data). We did this scenario to test the response time to establish a connection for both EJB and COM+. The virtual users were loaded simultaneously, the duration of the scenario was 10 seconds, and all virtual users stopped simultaneously too. This scenario was repeated several times for both COM+ and EJB applications and the response time for both cases is shown in table (2).
A Comparison between EJB and COM+ Business Components, Case Study
129
Table 2. The average response times for scenario1 Number of Virtual users
EJB
10
0.006
0.008
20
0.012
0.016
30
0.018
0.024
50
0.029
0.036
70
0.039
0.052
100
0.044
0.071
130
0.06
0.078
150
0.061
0.107
AVG of Response Time COM+
At this scenario as we saw, the EJB applications had better results than COM+ applications, at the beginning when we had just 10 users the results for both were approximately the same, but when we increased the number of virtual users the EJB applications had a better result than COM+ applications, at 150 virtual users EJB response was at 0.061 seconds, but COM+ response was at 0.107 seconds, that is a big difference, COM+ application needs approximately double the time that was needed for EJB application to respond. Figure (4) shows the results of scenario 1. Response Time (pge load) 0.12
T im e (Sec)
0.1 0.08 EJB
0.06
COM+ 0.04 0.02 0 10
20
30
50
70
100
130
150
Num ber of Vertual Users
Fig. 4. Connection establishment times for EJB and COM+
4.2 Scenario 2 (Inserting Data) We built a site to insert registration data into the database. In this scenario we only attempted to insert data into the database and not retrieve any data from the page. The scenario ran as follows: we loaded 15 virtual users for 15 seconds each. The duration
130
A. Abu-Kamel, R. Zaghal, and O. Hamed
of the scenario was 1 minute and the virtual users were stopped simultaneously to exit. The scenario was repeated several times on the COM+ and the EJB applications. At each run we increased the number of virtual users, and then took readings of response times and the number of transactions (i.e. number of record inserted into the registration table). The results are summarized in table (3). Table 3. Scenario 2 results Number of Virtual users 1 10 20 30 40 50 60 70 80 90 100
AVG of Response Time
Number Of transactions
EJB
COM+
EJB
COM+
0.008 0.021 0.033 0.049 0.061 0.066 0.076 0.083 0.089 0.155 0.162
0.046 0.061 0.082 0.109 0.164 0.209 0.254 0.293 0.332 0.373 0.414
6,981 29865 41749 45760 51317 59546 61539 65519 69691 71815 75188
1289 25984 52191 65764 70832 80492 82423 91523 96403 103056 108978
It can be noted from the table that the response times and the number of transactions increased dramatically as the number of virtual users were increased. Also, we can notice when the scenario has one user, the response time for COM+ was 0.046 seconds and added 1289 records, on the other hand, and the response time for EJB was 0.008 seconds and added 6981 records. This is interesting since even though EJB has incurred much more transactions than COM+, the response time was much better. This trend continues for the rest of the table with multiple users. Figure (5) shows the performance for both COM+ and EJB application for one user. Pe rform ance (CPU Re sponse Tim e ) 0.05 Response Time(Seconds)
0.045 0.04 0.035
EJB
0.03 0.025
COM+
0.02 0.015 0.01 0.005 0 1 Num ber of Ve rtual Use rs
Fig. 5. Average response time for one user for scenario2
A Comparison between EJB and COM+ Business Components, Case Study
131
Figure (6) shows the relationship between (response time) and the (number of virtual users) for the previous scenario. In this figure, we can see that the COM+ application needed more time than the EJB application in order to complete the same process for all scenarios. Here, EJB delivers better performance than COM+. If we look closely at the figure we can also notice that when the number of virtual users increase, the time needed by COM+ increases faster than that needed by EJB in order to complete the same process for the same number of users which is an indication for the scalability of the system; it is obvious that EJB scales-up better than COM+.
T i m e (S e c )
Response Time 0.45 0.4 0.35 0.3 0.25 0.2 0.15 0.1 0.05 0
EJB
COM+
1
10
20
30
40
50
60
70
80
90
100
Number of Vertual Users
Fig. 6. Average of response times for all users for scenario2
Figure (7) shows the relationship between the number of virtual users and number of transactions that were completed. In this plot we can see that COM+ have added more records than EJB and thus incurred more time to complete the same process, and thus needed more time to complete one transaction. Figure (8) shows the average response time per transaction for one user on both middle tiers, and figure (9) represents
Number of Transactions N u m b e r o f T r a n s a c to n s
120,000 100,000 80,000 60,000
EJB
40,000
COM+
20,000 0 1
10
20
30
40
50
60
70
80
90
100
Number of Vertual Users
Fig. 7. Number of transaction vs. number of virtual users for scenario2
132
A. Abu-Kamel, R. Zaghal, and O. Hamed
response tim e per transactions 0.05 0.045
Time (Seconds)
0.04 0.035
EJB
0.03
COM+
0.025 0.02 0.015 0.01 0.005 0 f or one user
Fig. 8. Average response time per transaction for one user
Res ponse tim e pe r Transactions 0.0045 0.004
Time(Seconds)
0.0035 0.003 EJB 0.0025
COM+
0.002 0.0015 0.001 0.0005 0 For 100 of users
Fig. 9. Average response time per transaction for 100 users
the average response time per transaction for 100 users. It took 0.414 and 0.162 seconds for COM+ and EJB respectively, and incurred 108978 and 75188 records on COM+ and EJB respectively. Again EJB wins since it needed less time per transaction and this is another indication that the EJB applications delivers better response time and scales-up better than COM+ applications. 4.3 Scenario 3 (Loading Data) In this scenario data will be retrieved from the database to fill-in the drop-down lists on the Web page. Here, the scenario will open the page and fill these drop-down lists with values retrieved from the database tables. The duration if the scenario was 3 seconds, and the data was filled into the page without insertions of any new data. The virtual users were loaded simultaneously and stopped simultaneously too. Table (4) summarizes the results of this scenario in terms of response time and standard deviation. In this scenario the maximum number of virtual users was 50. It can be seen that the performance of the EJB application was better than that of the COM+ application;
A Comparison between EJB and COM+ Business Components, Case Study
133
when we had one virtual user the EJB application needed 0.014 seconds to respond to the user (e.g. load the page), while the COM+ application needed 0.027 seconds to load the page. Figure (10) shows the response time while varying the number of virtual users from 1 to 50 on both EJB and COM+. Table 4. Average response time and standard deviation for scenario 3 Number of virtual users
Std deviation of response time
Average response time
EJB
COM+
EJB
1
0.008
0.002
0.014
COM+ 0.027
10
0.118
0.128
0.084
0.155
20
0.156
0.205
0.164
0.282
30
0.175
0.307
0.247
0.419
40
0.268
0.227
0.315
0.583
50
0.344
0.287
0.408
0.71
For this scenario we take a standard deviation for response time, standard deviation measures the spread of the data about the mean value. It is useful in comparing sets of data which may have the same mean but a different range. Figure (11) plots the standard deviation values that we have presented in Table (4). In this figure cannot see a steady pattern or consistency on the COM+ application. This is reflected in the leap from top to bottom around 30 users. This is not the case on EJB applications where the growth can be characterized as being stable.
Response Time (Load Data) 0.8 0.7
Time(Sec)
0.6 0.5 0.4
EJB
0.3
COM+
0.2 0.1 0 1
10
20
30
40
50
Number of Vertual Users
Fig. 10. Average of response times for scenario 3
134
A. Abu-Kamel, R. Zaghal, and O. Hamed
Std.Deviation of response time 0.4 0.35 T im e(sec)
0.3 0.25
EJB
0.2
COM+
0.15 0.1 0.05 0 1
10
20
30
40
50
Number of virtual users
Fig. 11. Standard deviation of response time for scenario 3
5 Conclusion In this paper we have presented the results of a real experiment that we have conducted in the lab to study the performance of the middle tiers (business logic tiers) of two prominent distributed applications: The EJB technology of Sun’s J2EE applications, and the COM+ technology of Microsoft’s .NET applications. The experiments aimed at measuring the performance in terms of response-time and scalability of each technology using three scenarios (page load, data insertion, and data loading) and by varying the number of virtual users and the workloads in each scenario. It was observed that in all three scenarios EJB applications have demonstrated better performance in terms of response time, scalability. In our opinion this is due to the fact that COM+ environment is more heavy-weight than the EJB as it needs to load (and re-load) many supportive and system files for each session regardless of the user load.
References 1. Singer, J.: JVM versus CLR: A Comparative Study. In: Proc. of 2nd International Conference on Principles and Practice of Programming in Java Kilkenny City, Ireland (2003) 2. Cecche, E., Marguerite, J., Zwaenepoel, W.: Performance and Scalability of EJB Applications. ACM SIGPLAN Notices (2002) 3. Sessions, R.: Java 2 Enterprise Edition (J2EE) versus The .NET Platform Two Visions. ObjectWatch (2001) 4. Kárason, R.: Dependability aspects of COM+ and EJB in multi-tiered distributed systems. Springer, Heidelberg (2002) 5. Hirschfeld, R.: Three-Tier Distribution Architecture (1996) 6. Eddon, G.: COM+: The Evolution of Component Services. IEEE, Los Alamitos (1999), ISSN: 0018-9162 7. Voth, G.R., Kindel, C., Fujioka, J.: Distributed Application Development for Three-Tier Architectures: Microsoft on Windows. IEEE Internet Computing (1998)
A Comparison between EJB and COM+ Business Components, Case Study
135
8. Kambhampaty, S., Modali, V.S.: Performance Modeling for Web based J2EE and .NET Applications. In: Proc. of World Academy of Science, Engineering and Technology 8 (October 2005), ISSN 1307-6884 9. Microsoft: Improving Performance and Scalability. Patterns and Practices. Microsoft Corporation, ISBN 0-7356-1851-8 10. Meier, J.D., Vasireddy, S., Babbar, A., Mackman, A.: Improving .NET Application Performance and Scalability. In: Patterns & Practices 11. Kounev, S., Buchmann, A.: Performance Modeling and Evaluation of Large-Scale J2EE Applications. In: Proc. of Computer Measurement Group (CMG 2003), Dallas, Texas (2003) 12. HP LoadRunner software, https://h10078.www1.hp.com/cda/hpms/ display/main/hpms_content.jsp?zn=bto&cp=1-11-126-17%5E8_ 4000_100 13. Hamed, O., Kafri, N.: Performance Testing for Web Based Applications Architectures (.NET vs. Java EE). In: Proc. of Networked Digital Technologies, NDT 2009, Ostrava, Czech Republic, pp. 218–224. IEEE, Los Alamitos (2009) 14. Hamed, O., Kafri, N.: Performance Prediction of Web Based Application Architectures Case Study: NET vs. Java EE. International Journal of Web Applications (IJWA) 1 (2009)
A Framework for Intelligent Games Diana F. Adamatti* Laboratório de Inteligência Computacional Centro de Ciências Computacionais Universidade Federal do Rio Grande - Brasil
[email protected]
Abstract. This paper presents the conceptual definition of a framework to help in the construction of intelligent games, where Artificial Intelligence Techniques could be inserted in the game in an easier way. The main AI techniques are presented as well as the requirements of this framework. Keywords: Artificial Intelligence Techniques, Computer Games, CASE Tools.
1 Introduction The motivation to work with games is enormous. In Brazil, the experience of the game industry in world has shown extremely positive, where some companies have moved more than $ 30 billion, including distribution, packaging, marketing and advertising. In education, the games could help in learning process, because they develop skills such as memory, attention, creativity and reasoning. They are no longer part only the leisure. Now, there are emerged the serious games, a kind of games using to treat important themes, as natural resources management, political problems, business scenarios, etc. In literature, there are several definitions for games. In the context of this paper, a good definition is “Game: a voluntary activity or occupation (which may be physical or mental), exercised within certain time and space, according to rules freely created, but absolutely mandatory, which has an end in itself, and whose purpose is recreation"[2]. The games can be classified in several ways, but in computer games, they are a simulation of some mechanism or situation that may or may not exist in the real world, from a computational device. The computer games differ from other software for their subjectivity, because their main goal is fun (it can be associated to other goals, such as teaching, training, etc.). Even though the game is based on a real and deterministic game, there is subjectivity, since the graphical interface and the level of the game's features are based on its creator and it is adjusted to a user audience [2]. Artificial Intelligence (AI) seeks to develop tools that assist in the implementation of human activities [10]. In practice, the main goal of AI is to help the machines to perform tasks that were previously performed only by people. The computer games *
Corresponding author.
F. Zavoral et al. (Eds.): NDT 2010, Part II, CCIS 88, pp. 376–380, 2010. © Springer-Verlag Berlin Heidelberg 2010
A Framework for Intelligent Games
377
and AI areas have a long tradition of cooperation. The games provide the AI a variety of problems to be solved and the great challenge is the answers in real time, as MMORPGs (Massive Multiplayer Online Role-Playing Games), where many players interact each other via web. The AI gives to games more realistic features for interaction with users, such as the unpredictability of behavior [10]. Laird and van Lent [4] present several types of computer games that using AI, with dynamic roles. Genesereth et al. [3] present a new dynamic development of computer games, entirely based on AI, called General Game Playing (GGP) that tries to develop any types of games from a declarative description. Normally, the focus of the computer games is the graphical interfaces. However, it is necessary to provide smart games, making the relations between users and system more dynamics. This paper proposes the definition of a framework to help in the construction of intelligent games, where AI techniques (intelligent agents, fuzzy logic, recommender systems, genetic algorithms, etc.) could be inserted in the game in an easier way. This framework should provide to developers a skeleton of the players and environment of proposed game, using AI techniques. This paper is organized in 4 sections. In Section 2 are presented the main AI techniques, which will be implemented in framework. Section 3 presents the conceptual proposed framework and section 4 the conclusions and the further work of the paper.
2 Artificial Intelligence Techniques This section presents the main AI techniques that will be initially implemented the proposed framework. The explanation of these techniques is purely descriptive, to better understand their functionalities. 2.1 Intelligent Agents and Multiagent Systems For the development of complex systems, its necessary to create a new programming paradigm that includes the distribution, autonomy, flexibility and heterogeneity. This paradigm must allow add or remove functions, in a flexible and extensible way. Agents meet these requirements and they are being adopted as the basis for this new paradigm. Multiagent Systems (MAS) study the behavior of a set of autonomous agents with different characteristics, evolving into a common environment. These agents interact with each other, and try to execute their tasks in a cooperative way by sharing information, preventing conflicts and coordinating the execution of activities. In this type of system, it is assumed that agents are part of a society with certain autonomy and intelligence [10]. The MAS agent behavior is a function of perception, that it has its own state, its interactions with other agents and its knowledge. The MAS has a different perspective to design and develop environments and more sophisticated and powerful computational tools, in order to increase the complexity of real systems. According to Caglayan and Harrison (1997) [1], the MAS allow: • •
improve the robustness of the system, avoiding failures; provide parallel solution to accelerate the implementation of the resolution of problems;
378
D.F. Adamatti
• •
integrate methodologies to solve problems; combine paradigms and knowledge sources.
2.2 Recommender Systems Resnick and Varian [7] define Recommender Systems (RS) as systems that use opinions of user’s community to help them to identify content of interest from a number of options. Recommender systems help users to identify interesting products or services, where the number and complexity of data are very large, and the user could not take the right decision. Recommender systems help to increase the capacity and effectiveness of a natural process well known in social relations: the indication process. The biggest challenge in this kind of system is to achieve the correct integration (called "marriage") between the items to be evaluated [8]. The first recommender systems have emerged in the mid-90. Different authors classify theses systems in three categories [7, 5]: •
•
•
Collaborative Filtering: it is based on the proposal to recommend for a user items that other user, with similar profiles, have acquired. The idea is to promote the exchange of experiences among people with common interests. For example, for a Web purchase, people who have acquired the same products will receive similar recommendations. Content-Based Filtering: it is based on the proposal to analyze the items content previously consulted by the users and to infer a new recommendation. The filter analyzes users’ content and profile. For example, for a Web purchase, if the user has previously acquired, these products will be analyzed and the recommendation will be based in products with similar content. Knowledge-Based Recommender System: it is based in intelligent inference mechanisms (using cognitive psychology and statistical methods), where a user model is created. For example, for a Web purchase, a user model is generated, basing in the user registration data as well as the purchase data.
There are recommender systems that combine models basing in these three categories, called hybrid recommender systems. 2.3 Genetic Algorithms Genetic algorithms (GA) are a family of computational models inspired by evolution. These algorithms model a specific problem using a data structure similar to a chromosome [9]. An implementation of genetic algorithm starts with a population, usually random, of chromosomes. These structures are programmed to generate solutions of the problem and chromosomes with the better solutions will reproduce faster than chromosomes with the worse solutions. In a wider view, a genetic algorithm is any population-based model that uses selection operators and re-combination to generate new samples in a search space. Many genetic algorithms were introduced by researchers of an experimental perspective. Most of them are interested in the genetic algorithm as optimization tool.
A Framework for Intelligent Games
379
Usually, there are two components of the genetic algorithm: problem encoding and evaluation function. 2.4 Fuzzy Logic Fuzzy Logic can be defined as a logic that supports approximate reasoning rather than exact and it is based on fuzzy set theory [11]. This logic was developed by Lotfi A. Zadeh University of California at Berkeley in the 60s and it combines multi-valued logic, probability theory, artificial intelligence and neural networks that can represent human thought. The truth value of a proposition can be a fuzzy subset of any partially ordered set, unlike the binary logic systems, where the true value can only take 2 values: true (1) or false (0) [11]. Fuzzy Logic is an efficient tool to capture vague information, generally described in a natural language and it can convert to an electronic format.
3 Proposed Framework The main objective of this research is developing a tool to help in development of Computer Games using AI techniques. Therefore, we have defined the architecture for the proposed framework, divided in four modules: AI Techniques, Graphical Interface, Parser and Pre-source Code. The first module (AI Techniques) is used to the subsequent module (Graphical Interface) and so on, as presented in Figure 1.
Fig. 1. The architecture for the proposed framework
For each module, some requirements are defined: • AI Techniques module: it has all logic data structures for each AI technique and it must provide the parameters for each technique to the Graphical Interface module; • Graphical Interface: it has all graphical objects to use AI techniques in the reasoning of the players and the environment of the game. For each technique, different structures could be used. The idea is similar to CASE tools, in Software Engineering area, where for each different diagram (class, sequence, etc), there are different graphical objects; • Parser: it is a translator to the graphical definition to a computational language. The first idea is to transform to Java and C++ languages;
380
D.F. Adamatti
• Pre-source Code: it is the final result of the framework. It will provide a presource code file, with the skeleton of the reasoning of the player and the environment, using AI techniques. This file will be incorporated in the final game source code.
4 Conclusions e Further Work Computer games are a special way to work with different abilities of the humanbeing, because different skills, as memory, attention, creativity and reasoning, which could be tested and analyzed. The use of AI in games still is very restrict, because the main games focus is the graphical interface (engines, renderization, etc), but it could bring more realist action, with a level of uncertainty into the game. Develop a tool to make easier the insertion of AI techniques in computer games could be the way to a massive use of them. In this paper, there is presented the logical idea for a framework of intelligence games. Initially, the AI techniques to compose the framework were shown, and after the modules of this framework were defined. The next step is the implementation of these modules in Java language. The validation of the framework will be done in some small computer games, included players and environment actions to evaluate their performs with unpredictability. Acknowledgments. Diana F. Adamatti is financed by FAPERGS (Brazil), grant number 0902806/2009.
References 1. Caglayan, A., Harrison, C.: Agent SourceBook - A complete Guide to Desktop, Internet and Intranet Agents, 349 p. Wiley Computer Publishing, New York (1997) 2. Funge, J.D.: Artificial Intelligence for Computer Games. A.K. Peters, Wellesley (2004) 3. Genesereth, M., Love, N., Pell, B.: General game playing: Overview of the AAAI competition. AI Magazine, 63–72 (June 2005) 4. Laird, J.E., van Lent, M.: Human-level ai’s killer application: Interactive computer games. AI Magazine, 15–25 (2001) 5. Mobascher, B., Burke, R., Bhaumik, R., Sandvig, J.J.: Attacks and Remedies in Collaborative Recommendation. IEEE Intelligent Systems 22(3), 56–63 (2007) 6. Nareyek, A.: Constraint-Based Agents - An Architecture for Constraint-Based Modeling and Local-Search-Based Reasoning for Planning and Scheduling in Open and Dynamic Worlds. Springer, Berlin (2001) 7. Resnick, P., Varian, H.R.: Recommender Systems. Communications of the ACM 40(3), 55–58 (1997) 8. Ricci, F., Nuygen, Q.N.: Acquiring and Revising Preferences in Critique-Based Mobile Recommender Systems. IEEE Intelligent Systems 22(3), 22–29 (2007) 9. Whitley, D.: A Genetic Algorithm Tutorial. Technical Report: Colorado State University (2002), http://xpusp.sourceforge.net/ga_tutorial.ps (July 2009) 10. Russel, S., Norvig, P.: Artificial Intelligence: A Modern Approach, 3rd edn (2009) 11. Nguyen, H.T., Walker, E.A.: A First Course in Fuzzy Logic, 3rd edn. Chapman & Hall/CRC (2006)
A Multi-Objective Particle Swarm Optimization for Web Service Composition Hamed Rezaie, Naser NematBaksh, and Farhad Mardukhi University Of Isfahan, Isfahan, Iran
[email protected], {Nemat,Mardukhi}@eng.ui.sc.ir
Abstract. The main advantage of the web services technology is the possibility of preparing a compound web service with the existing to perform a proper task, but a service may be presented by several producers which one different in the quality of services. An adaptive process should select the elements of a compound web service in a way to answer effectively the user's needs in the quality of the services. There may be contrast in the optimization of the services qualities for some of them and against the others so we are involved with a multi multi-objective optimization. In this paper a web service composition model based on the Discrete Multi-Objective Particle Swarm Optimization is presented at which besides using the main advantages of standard PSO namely simplicity and speed a Pareto optimal set is presented as solutions. Keywords: Web Service Composition, QoS, Multi-Objective Particle Swarm Optimization (MOPSO).
1 Introduction Currently increasingly Web services, as possible instrument of accessing web-based applications, have been adopted [1]. Web service technology devotes more flexibility and adaptability to applications because a number of loose coupling components, namely Web services, corporate to obtain a common goal. Now, most companies motivate towards deploying business processes as web services compositions [3]. Also, the composition of web services has received much interest to support B2B or enterprise application integration [4]. With the improvement of the net and growth of web users, simple services are no longer suitable for web users and in order to give more complex services, we need combine simple services but there are different services which have the same functionality and can replace one another. These services are of course different with regard to quality factors such as response time, availability, throughput, security, reliability, execution cost and etc. Therefore web service composition problem leads to quality engineering problem, because these services should be chosen in such a way that the best QoS is prepared for the total composition. Therefore, at the step of service composition it is very important to select services which are relied on non-functional QoS (Quality of Service) attached to each service, where Web Services selection based on QoS is a NP problem [6].Effective strategies F. Zavoral et al. (Eds.): NDT 2010, Part II, CCIS 88, pp. 112–122, 2010. © Springer-Verlag Berlin Heidelberg 2010
A Multi-Objective Particle Swarm Optimization for Web Service Composition
113
based on evolutionary algorithms (EA) are introduced to overcome this problem. The majority of these approaches [7-12] on Web Services selection are almost QoS locally optimal or single-objective. In ref. [7-9] the authors introduced a Genetic Algorithm with a penalty technique to handle infeasible solutions. Difference between them is in coding scheme and in the design of penalty functions. Ref. [10] takes advantage of simulated annealing algorithm to avoid premature convergence of Genetic Algorithm. Ref. [11] proposed a service selection optimization method based on particle swarm optimization. But in all of these approaches the multiple QoS indexes optimization problem is turned into a single-objective problem using a weighted method, which will inevitably miss some feasible solutions. To solve these problems, in this paper we proposed a discrete multi-objective particle swarm optimization (MOPSO) for the optimal web service composition. The main objective of the Multi-Objective Optimization (MOO) is finding the set of acceptable (trade-off) Optimal Solutions. This set of accepted solutions is called Pareto front. These acceptable trade-off solutions give more ability to the user to make an informed decision by seeing a wide range of near optimal solutions that are near optimum from an “overall” standpoint. Single Objective (SO) optimization may ignore this trade-off viewpoint [12], which is crucial. This paper is organized as follows. In the next section we present preliminary introduction to Multi-objective optimization. The general PSO algorithm is reviewed in section 3. Section 4 describes the web service composition problem. We will introduce our proposed multi-objective PSO in Section 5. A comparison with a genetic algorithm and experimental results are given in Section 6. Finally, we conclude the paper in Section 7.
2 Multi-Objective Optimization Many optimization problems the aim is to find solutions that are best with regard to various objectives. These optimization problems are named multi objective and they are usually hard computing. Evolutionary based algorithms have been successfully used for these types of problems because they simultaneously work with a population of points that is crucial to find the non-dominated solution set [13]. The concept of no dominance [14] is one of the basic concepts of multi objective. For a problem having more than one objective function to optimize any two solutions x1 and x2 can have one or two possibilities: one dominates the other or none dominates the other. A solution x1 is said to dominate the other solution x2 if both the following conditions are true: a) The solution x1 no worse than x2 in all objectives. b) The solution x1 is strictly better than x2 in at least one objective. If x1 dominates the solution x2, it is also customary to write x2 is dominated by x1, or x1 is not dominated by x2, or simply, between two solutions, x1 is the non-dominated solution. A solution is said to be Pareto optimal if and only if there is no other solution in the search-space that dominates it. This set of Pareto optimal solutions is called the Pareto optimal set.
114
H. Rezaie, N. NematBaksh, and F. Mardukhi
3 Particle Swarm Optimization The particle swarm optimization (PSO) algorithms are a population-based search algorithms based on the simulation of the social behavior of birds within a flock [15]. They all work in the same way, which is, updating the population of individuals by applying some kind of operators according to the fitness information obtained from the environment so that the individuals of the population can be expected to move toward better solution areas. In the PSO each individual flies in the search space with velocity which is dynamically adjusted according to its own flying experience and its companion flying experience, each individual is a point in the D-dimensional search space [16]. 3.1 General PSO Algorithm Generally, the PSO has three major algorithms. The first is the individual best. This version, each individual compares position to its own best position, pbest, only. No information from other particles is used in these type algorithms. The second version is the global best. The social knowledge used to drive the movement of particles includes the position of the best particle from the entire swarm. In addition, each particle uses its history of experience in terms of its own best solution thus far. In this type the algorithms is presented as: 1.
Initialize the swarm of particles such that the position X ti of each particle P i ∈ Pt is random within the search-space, with t = 0.
2.
Evaluated the performance F of each particle, using its current position X ti .
3.
Compare the performance of each individual to its best performance thus far: if F( X ti ) < F( X ti ,Pbest ) then: X ti ,Pbest = X ti
4.
Compare the performance of each individual to global best particle: if F( X ti )
5.
< F( X ti ,Gbest ) then: X ti ,Gbest = X ti Change the velocity vector for each: V ti+1 = ω ×V t i + ρ 1× (X ti ,Pbest − X ti ) +
ρ 2× (X ti ,Gbest − X ti )
(1)
Where ω is the inertia factor, ρ 1 and ρ 2 are random variables. The second term above is referred to as the cognitive component, while the last term is the social component. 6. Move each particle to a new position
X ti+1 = X ti +V t i+1 t = t +1 7.
(2)
Go to step 2, and repeat until convergence.
The random variables ρ 1 and ρ 2 are defined as ρ 1= r1 × c1 and ρ 1= r2 × c 2 , with r1, r2 ~ U (0,1) , c1 and c 2 are positive acceleration constant. Kennedy has studied
A Multi-Objective Particle Swarm Optimization for Web Service Composition
115
the effects of the random variables ρ 1 and ρ 2 on the particle's trajectories. He asserted that c1 + c 2 ≤ 4 guarantees the stability of PSO [17]. 3.2 Multi-Objective PSO (MOPSO)
The main problem in multi-objective particle swarm optimization (MOPSO) is to select the global and local guides such that the swarm is guided towards the Pareto optimal front and maintains sufficient diversity. Our paper simply adopts one of the proposed strategies, namely the sigma-method [18].In this method the global and local guides are selected from an updated set of non-dominated solutions stored in the archive.
4 Problem Description Given an abstract specification for a workflow, suppose the composite service is defined as follows: S= (AS1, AS2… ASn). We also assume that for each basic service Si there is a set of candidate web services, for example, ASi has l candidate web services. These candidate web services are functionally equivalent and thus can be replaced by each other. The aim is to search for the optimal set of services that composed to create a new service, result in the best QoS, and under the user constraints. In optimal QoS-based Composed Web service, the best concrete service should be selected for each corresponding abstract Web such that the value of objective functions meets the customers' requirements. Fig. 1 is an example used to demonstrate the problem. In Fig. 1, a specification of workflow is defined using YAWL notions [19]. Abstract Web services are shown by rectangles, and concrete Web services are represented by rounded rectangle. In this paper, we attention to the two typical attributes: response time, price. Normally, users may desire the composite service with minimal response time and price. Existing
Fig. 1. Example of web service selection workflow
116
H. Rezaie, N. NematBaksh, and F. Mardukhi
studies reported in literature often aggregate all criteria into a single objective. This resolution approach is known to be limited from a multi-objective optimization perspective since it leads to one single solution instead of a set of solutions which are needed in a multi-objective context. Here we highlight the most important difference between our work and Zeng et al’s work (Zeng et al., 2003) [11], because we do not give any weight to any criterion. We treat all criteria with the same importance using a multi-objective optimization approach. Even though our objectives are contradictory, they are taken into account simultaneously by our resolution algorithm. According to above requirements, the problem is formulated as follows: Given (1) A set of abstract Web services A = {A1, A2, …, An}; (2) A set of implementations, or concrete Web services, for each of the abstract Web service Ai, Ci = {ci1, ci2, …, cim}; (3) QoS(S) = (Time(S), Cost(S)) be QoS index of Solution Where 1 ≤ i ≤ n, 1 ≤ j ≤ m, Find a solution S = (s1,s2, …, sn), meaning abstract Web service Ai uses concrete Web service cij , such that: ⎧⎪Minimize Time ( S ) ⎨ ⎪⎩Minimize Cost ( S )
4.1 Computing the QoS of Services Composition
When computing the QoS of Web Service Composition, we consider response time and price as the measurement metrics the aggregate QoS of Web Service Composition depends on the QoS of its component services. Computing the QoS of a workflow is based on the control structures included in workflow. BPEL4WS has four control structures to compose service. They are sequence, flow (concurrence), switch (choice), while (loop). The aggregated rules of QoS are different for different control structures and different quality metrics. Table 1. The model for computing the QoS of Services Composition QoS Attr.
Price
Time
n
Sequence
∑q
n
price (S i
)
i =1
∑q
price (S i
resp (S i
)
i =1
n
Concurrence
∑q
)
{
MAX i ∈{1,.., p} q resp ( S i
i =1
n
Choice
∑
n
p i × q price (S i )
i =1
Loop
k × q price (inner )
∑p
i
× q resp (S i )
i =1
k × q resp (inner )
)}
A Multi-Objective Particle Swarm Optimization for Web Service Composition
117
For example, the response time is sum measurement for sequence structure, while the response time of concurrence is the maximal value among its sub branches. The price is the sum for both sequence and concurrence control structure, but it is multiple measurements for availability. Each branch in choice structure is assigned to the probability to be chosen, and the sum of all of branches is 1. Finally, a loop structure with k iterations of task t is equivalent to a sequence structure of k copies of t.
5 Optimal Web Service Composition Based on MOPSO Algorithm The implementation of MOPSO in application of the Web service composition problem incorporates three basic steps so that the algorithm is formulated for the specific application: the presentation of Particle, the formulation of the fitness function, and redefinition of discrete PSO operators. 5.1 Particle Representation
When we are designing the PSO algorithm one of the important matters is the solution representation where particles carry the necessary information related to the problem domain at hand. In PSO, each particle corresponds to a candidate solution of the underlying problem. For Web Service Composition, a direct representation is obtained as follows. A feasible solution is encoded in a D-dimensional vector, called particle, where d is equal to the number of abstract service in workflow. Every dimension of each particle represents one of the abstract services in workflow, and the value of each element in the vector X indicates the index of concrete web service in the corresponding list of concrete web services for each abstract web service. For example X = {3, 1, 4, 11, 6} represents an individual for a workflow with five dimensions. In this individual for the first abstract service the concrete web service with index 3 in associated list is selected, and so on. The PSO randomly generates an initial swarm of n particles, where n is the swarm size. These particle vectors will be modified iteratively based on collective experiences in order to improve their solution quality. 5.2 Fitness Functions
The MOPSO associates a fitness measure with each solution to specify the quality or performance of each encoded solution in the population. For the problem of Web service composition, performance of every service composition solution is measured by its QoS index. Here we adopt the two QoS optimization functions defined in Problem Description section as two fitness functions in MOPSO and computing them according to the table 1. 5.3 Redefinition of Discrete PSO Operators
The classical PSO algorithm is not applicable if the search space is discrete, that is if the position of each particle is bound to a discrete set of values. A modification of
118
H. Rezaie, N. NematBaksh, and F. Mardukhi
the classical algorithm is proposed in the current paper suitable for optimization within such a search space. The proposed solution is inspired by Discrete PSO algorithm, explained in [20]. In this paper, the equation of particle's position update has been modified in a way to presence all the benefits of the standard PSO algorithm. In the proposed method, the position of a particle can be update by the equation (3).at this equation each coefficient c1 × rand1 , c 2 × rand 2 , ω and c3 means the choosing probability. Here, c1,c 2 ,c 3 are three constant and rand1 and rand 2 are two random number in ⎡⎣0,1⎤⎦ . Also in each iteration ω is updated in this manner ωt +1 = ωt × β . β is a decreasing factor less than 1. v ti +1 instead of being reserved from the last iteration, generated from [1, m] randomly that m indicates the number of concrete web services at the corresponding abstract web service group.
X ti+1 = c 3 ⊗ X ti ⊕ ω ⊗V ti+1 ⊕ c1 × rand1 ⊗ X ti ,Pbest ⊕ c 2 × rand 2 ⊗ X ti ,Gbest
(3)
In our method to overcome the premature convergence of standard PSO, we use particle velocity like a mutation operator. In this manner, we extend the search ability of particles at the beginning of the search and then, we decrease this ability (with respect to the number of iterations) in each iteration. In addition when the nondominated set size of archive exceeds a given maximum M, in this situation to reduce the size of archive to a predefined constant size we use an average linkage based hierarchical clustering algorithm used by SPEA [21] with multi-start technique [22]. 5.4 MOPSO for Optimal Service Composition
When specific representation scheme and fitness functions to evaluate the solutions have been decided, the final MOPSO for the optimal web service composition will be developed. The detailed algorithm is given in Table 2 and 3. Table 2. Multi-Objective Particle Swarm Optimization for Web Service Composition Input: Optimization problem. Output: Non-dominated solutions in archive (A) Step 1: t = 0 Step 2: Initialization: Initialize population Pt :
for i = 1 to n initialize X ti , V t i = 0; end If t = 0 then Initialize the archive At = { End Step 3: Evaluate( X t );
};
A Multi-Objective Particle Swarm Optimization for Web Service Composition Table 2. (continued)
Step 4: At +1 = Update ( X t , At ) ; If |At| > M then Hierarchical_Clustering (); Go to Step 2. End Step 5: Pt +1 = Generate ( X t , At ) : for i = 1 to n i ,g i a ) X t = FindGlobalBest (At +1 , X t ); i
b )V t +1 = Rand ( X ); i
i
i ,l
c ) X t +1 = c 3 ⊗ X t ⊕ c1 × rand 1 ⊗ X t
⊕
c 2 × rand 2 ⊗ X t ⊕ ω ⊗V t ; i i ,l d ) if Dominate ( X t +1 , X t +1 ) then i ,l i X t +1 = X t +1 ; end end i ,g
i
Step 6: Unless a termination criterion is met: t = t + 1 and go to Step 3. End Table 3. Average linkage based hierarchical clustering algorithm
Input: Non-dominated solutions in archive (A), S /*size of reduced archive*/ Output: reduced Non-dominated solutions in archive (A) Step 1: Initialization Clusters = {
};
for i = 1 to size ( A ) Clusters = Clusters ∪ {A ( i )}; end
Step 2: Clustering W hile Clusters > S {Cluster 1} = two cluster with minimum distance ; newCluster = Cluster 1 ∪ Cluster 2; Clusters = Clusters −
{Cluster 1, Cluster 2} ;
Clusters = Clusters + newCluster; End
Step 3:Reproduce archive A =
{ };
for i = 1 to Clusters Cluster = Clusters ( i ) ; A =A ∪ end
{centeroid (Cluster )} ;
119
120
H. Rezaie, N. NematBaksh, and F. Mardukhi
6 Experimental Result To verify performance of the proposed method we compared it with a multi objective genetic algorithm namely NSGA II. All experiments were conducted on a test-bed of Windows Pcs with Pentium quad core 2.66 GHZ processor and 2 GB RAM and the simulation environment is Matlab R2007b. Table 4. Comparison results of Multi-Objective Particle Swarm Optimization and NSGA II
Number of Iteration Abstract × services Population size 50 400×400 50 400×300 50 400×200 50 300×400 50 300×300 50 300×200 50 200×400 50 200×300 50 200×200 20 400×400 20 400×300 20 400×200 20 300×400 20 300×300 20 300×200 20 200×400 20 200×300 20 200×200 5 400×400 5 400×300 5 400×200 5 300×400 5 300×300 5 300×200 5 200×400 5 200×300 5 200×200
Execution Time (mopso:nsga) (103 Sec) 3.553:2.035 2.601:0843 0.1746:0.362 2.234:1.272 1.528:0.652 0.988:0.251 1.003:0.736 0.721:0.356 0.162:0.102 3.770:1.410 3.183:0.802 1.867:0.410 2.183:0.704 1.664:0.473 1.092:0.270 1.018:0.471 0.747:0.380 0.507:0.172 4.750:0.758 3.134:0.572 2.026:0.341 2.305:0.618 1.716:0.318 1.152:0.209 1.045:0.336 1.060:0.165 0.519:0.106
Average Number of Average Number of Pareto Solutions Dominated Solutions (mopso:nsga) (mopso:nsga) 825.3:378 74.3:177.3 571:369 98.6:200 420:265.3 55.5:206.9 735.5:291.5 49.3:190.6 562:289.6 40.1:214.8 356.3:195 34.5:257.3 545:2003 55.4:153.1 447.6:188.6 82.7:202.1 226.3:161.3 35.6:159.1 235:233.6 10.7:15.1 209:230 9.4:11.2 229:215 45:51.6 222:220 8:9.8 203.3:211.3 9:20.1 212:204.6 14:15.7 229:172.6 6.7:17.6 196:168 8.2:13.7 207.3:164 12: 26.8 20:20 0:0 20:20 0:0 20:20 0:0 20:20 0:0 20:20 0:0 19.3:20 0:0 20:19.3 0:0 20:20 0:0 20:19.6 0:0
In these experiments all related parameters are assigned as follows: mutation and crossover probability in NSGA II are respectively 0.5 and 0.5 ; c1 ,c 2 ,c 3 ,ω , β in MOPSO are respectively 0.3,0.49,0.21 ,0.0275 and 0.995 ;the size of populations are :200 , 300 and 400;the number of iteration are 200 ,300 and 400. Due to no guideline problem, we create three workflow with 5, 20 and 50 abstract services. In each workflow number of concrete web service corresponding to each abstract web services
A Multi-Objective Particle Swarm Optimization for Web Service Composition
121
varied from 4 to 50. The ranges of two quality of services are given as service cost (11000) and response time(1-1000). In this paper to evaluate our method we compare the Pareto set results of two methods with each other and record the average number of dominated solutions after 9 tests. It is shown in table 4 that the proposed method will find out better or equal solutions in shorter time.
7 Conclusion In this paper we have presented a multi-objective discrete particle swarm optimization algorithm for web service composition problem to generate a set of Pareto optimal solutions that meet users' requirements. A set of experiments are conducted to analyze and evaluate the performance of proposed method, and the experimental result show that MOPSO is a good method for web service composition.
References 1. Rezgui, A., Ouzzani, M., Bouguettaya, A., Medjahed, B.: Preserving privacy in Web services. In: Proceedings of the 4th International ACM Workshop on Web Information and Data Management, pp. 56–62 (2002) 2. Medjahed, B., Bouguettaya, A., Elmagarmid, A.K.: Composing Web services on the Semantic Web. The VLDB Journal 12(4), 333–351 (2003) 3. Lakhal, N.B., Kobayashi, T., Yokota, H.: THROWS: An architecture for highly available distributed execution of Web services compositions. In: Proceedings of the 14th International Workshop on Research Issues on Data Engineering: Web Services for E-Commerce and E-Government Applications, pp. 56–62 (2004) 4. Srivastava, B., Kohler, J.: Web Service Composition-Current Solutions and Open Problems. In: ICAPS 2003 Workshop on Planning for Web Services, pp. 1–8 (2003) 5. Agarwal, S., Handschuh, S., Staab, S.: Annotation, composition and invocation of semantic web services. In: Web Semantics: Science, Services and Agents on the World Wide Web, vol. 2(1), pp. 31–48 (2004) 6. Garey, M., Johnson, D.: Computers and Intractability: a Guide to the Theory of NPCompleteness. W.H. Freeman, New York (1979) 7. Zhang, C., Ma, Y.: Dynamic Genetic Algorithm for Search in Web Service Compositions Based on Global QoS Evaluations. In: ScalCom-EmbeddedCom, pp. 644–649 (2009) 8. Lei, Z., Kai, S.: TTS-Coded Genetic Algorithm for QoS-driven Web Service Selection. In: Proceedings of IEEE International Conference on Communication Technology and Applications, pp. 885–889 (2009) 9. Gao, C., Cai, M., Chen, H.: QoS-aware Service Composition based on Tree-Coded Genetic Algorithm. In: 31st Annual International Computer Software and Applications Conference (COMPSAC 2007), vol. 1, pp. 361–367 (2007) 10. Gao, Z., Chen, J., Qiu, X., Meng, L.: QoE/QoS driven simulated annealing-based genetic algorithm for Web services selection. The Journal of China Universities of Posts and Telecommunications 16, 102–107 (2009)
122
H. Rezaie, N. NematBaksh, and F. Mardukhi
11. Chen, M., Wang, Z.W.: An Approach for Web Services Composition Based on QoS and Discrete Particle Swarm Optimization. In: Proceedings of the Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, pp. 37–41 (2007) 12. Ngatchou, P., Zarei, A., El-Sharkawi, A.: Pareto Multi Objective Optimization. Intelligent Systems Application to Power Systems, 84–91 (2005) 13. Coello, C.A.C.: A comprehensive survey of evolutionary-based multiobjective optimization. Knowledge and Information Systems 1(3), 269–308 (1999) 14. Deb, K.: Evolutionary Algorithms for Multi-Criterion Optimization in Engineering Design. In: Proceedings of Evolutionary Algorithms in Engineering and Computer Science (EUROGEN 1999), pp. 135–161 (1999) 15. Kennedy, J., Ebenhart, R.C.: Particle Swarm Optimization. Proceedings of the IEEE International Conference on Neural Networks 4, 1942–1948 (1995) 16. Engelbrecht, P.: Computational Intelligence An introduction. John Wiley & Sons Ltd., Chichester (2002) 17. Kennedy, J.: The behavior of particle swarm. In: Saravan, V.W.N., Waagen, D. (eds.) Proceedings of the 7th International Conference on Evolutionary Programming, pp. 581–589 (1998) 18. Mostaghim, S., Teich, J.: Strategies for finding good local guides in multi-objective particle swarm optimization. In: IEEE Swarm Intelligence Symposium, pp. 26–33 (2003) 19. van der Aaslt, W.M.P., Hofstede, A.H.M.: YAWL: Yet Another Workflow Language. Information Systems 30(4), 245–275 20. Qinma, K., Hong, H., Hongrun, W., Changjun, J.: A novel discrete particle swarm optimization algorithm for job scheduling in grids. In: Proceedings of the 4th International ACM Workshop Conference on Natural Computation, ICNC, pp. 401–405 (2008) 21. Zitzler, E., Thiele, L.: An Evolutionary Algorithm for Multiobjective optimization: The Strength Pareto Approach. TIK-Report, No. 43, Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich (1998) 22. Torn, A.: A program for global optimization. In: Proceedings of Euro IFIP, pp. 427–434 (1979)
A New Computational Model to Evaluate the Quality of Perceptual Voice Using E-Model in VOIP Communications Meysam Alavi1 and Hooman Nikmehr2 1
Department of Computer Engineering & IT, Qazvin Islamic Azad University, Qazvin, Iran
[email protected] 2 Department of Computer Engineering, Bu-Ali Sina University, Hamedan, Iran
[email protected]
Abstract. The quality perceptual voice in VOIP networks is of great importance as IP networks are not designed for real-time applications, disturbances such as packet loss, jitter and delay influence negatively on the quality. Emodel for VOIP networks is a well known approach has been developed for evaluating the quality of perceptual voice. In this model, the result is expressed in term of MOS ranged from 1 to 5. Having modified the traditional E-model, we present a unified computational model, applicable for both narrowband and wideband codecs. Keywords: VOIP, E-model, MOS, Packet loss, Delay.
1 Introduction VOIP, as an important technique, has been widely used in the transmission of voice traffic on computer networks. While VOIP services are economically cost- effective, their success is compared with that of PSTN qualities. The surveys show that voice quality mainly depends on packet loss, delay and jitter, although the present Internet does not guarantee the delay and packet loss. There have been reported much about quality improvement in VOIP services in [1], [2], [3], [4], [5], [6], [7], [8]. Three factors affect VOIP services quality: End-to-End delay, which is influenced by packet size, coding algorithm, buffer playout size and network characteristics (e.g. network topology, bandwidth and configuration); the effect of delay variability (jitter); packet loss rate, which is due to the congestion problem caused by lack of resources supplied by the Internet [9]. The assessment of perceptual voice quality can be based on MOS [10], as shown in Table.1 and can be determined in terms of subjective and objective tests [11]. In the subjective tests, MOS values are specified directly through asking a sample population on voice quality in five levels (excellent, good, fair, poor and bad). This case is time consuming and expensive since the test must be carried out by individuals [1]. The objective tests are classified as PSQM, PESQ [12] and the most frequent, Emodel proposed by ITU-T [13]. In this paper, we present a new method to assess and F. Zavoral et al. (Eds.): NDT 2010, Part II, CCIS 88, pp. 594–603, 2010. © Springer-Verlag Berlin Heidelberg 2010
A New Computational Model to Evaluate the Quality of Perceptual Voice
595
measure voice quality in narrowband and wideband codecs. The paper is organized as follows. An introduction on E-model is given in Sect. 2 and 3. Then the new model is introduced and described in Sect. 4 followed by some experiment results in Sect. 5. Section 6 includes conclusion. Table 1. Score of MOS
MOS 5 4 3 2 1
Classification Excellent Good Fair Poor Bad
2 E-Model E-model is a computational model proposed and standardized by ITU-T that assesses the combination of effects from parameters on conversation quality [12], [14]. These reports show that it is not any necessity to use the original version of E-model to determine the quality in VOIP communications, but its simplified version [2], in which only delay and packet loss effects are considered, while there are no echo and noise and also loudness is constant. E-model calculated in term of impairment factor gives a formulation, which must be transformed to an expression in term of R as
R = Ro − I s − I d − I e −eff + A
(1)
Equation (2) provides a simplified form used in VOIP communication where Ro= 93.2 is the maximum score obtained by codecs [12].
R = Ro − I d − I e − eff
(2)
Id is the impairment due to delay calculated from equation (3).
I d = 0.024 D + 0.11( D − 177.3) × H ( D − 177.3)
(3)
where D is End-to-End delay and H(x) denotes the heaviside function. Also, Ie-eff is the impairment induced by equipment dependent on equipment, packet loss and robustness against loss. The advantage factor A can be used for compensation when there are other advantages of access to the user. In (2), Ie-eff is obtained from
I e−eff = I e + (95 − I e )
Ppl Ppl + Bpl
(4)
in which Ie is the equipment induced impairment (codec quality) expressed in [14]. The calculation method of Ie is described in [15]. In (5), Bpl is the robustness against packet loss and Ppl denotes the packet loss rate in percent. Factor Id, the delay impairment in E-model, includes propagation, queuing and transmission delays. In
596
M. Alavi and H. Nikmehr
G.114 recommendation of ITU-T [16], accepted delay time is 150 ms [17], possible delay is between 150 and 400 and any delay beyond 400 ms is unacceptable. Factor R can be mapped into a number in term of MOS to assess the voice quality. This mapping introduced in [12] is expressed as
R 100 ⎩
(5)
Based on (4), R and MOS are interrelated (see Fig.1).
Fig. 1. MOS as function of rating factor R
The normal E-model is designed for narrowband communications. Therefore, the maximum value of MOS for two cases of narrowband and wideband is 4.5 (i.e. R>100). However, some quality control experiments [18], [19] show that the highest quality for wideband codecs is from 4.7 to 4.8, which is not comparable with the MOS results narrowband codecs. For instance, for MOS=3.5 for narrowband and MOS=3.3 for wideband, we cannot claim that the narrowband quality is better than that of the wideband as there is no proven technique to justify this quality difference. Regarding the increase of bandwidth and the higher quantization rate in wideband codecs, improves the voice quality that can result in a better hearing (understanding) [20]. This necessitates a unique criterion to compare both codecs. Therefore, we are going to present a new computational E-model, which is applicable for both codecs. First, we refer to the research results reported in this field and then in Sect. 4, we introduce the new model.
A New Computational Model to Evaluate the Quality of Perceptual Voice
597
3 E-Model for Wideband Codecs To the best of our knowledge, there has not been any perfect model presented to establish a new E-model applicable for wideband communications. In [21], the necessity of adding a advantage factor to narrowband and which increases the voice quality is put forward but without any formulation or computational estimate. In [22], R domain for wideband communications has been introduced between 0 and 120 while in [23] it is mostly 105 for wideband codecs. In [24], the domain of 0 to 100 has been raised to 120 with a ratio of 1.1 and [25] considers it to be 140 by using an extrapolation. In [26], based on amendment 1 of recommendation G.107, R=129 is the highest quality of wideband codecs. In some other studies addition of some constant value to Ie of narrowband codecs has been suggested. In overall, there is no unified model to measure voice quality and therefore, the values obtained are not applicably comparable. The main goals of the presented research are: • To develop a single MOS scale for narrowband and wideband VOIP codecs and to establish a quantitative expression between the new and the traditional scales. • To propose a single measure for factor R in the computational E-model, that can be applicable for both narrowband and wideband VOIP codecs.
4 Extended E-Model In this section, a new extended E-model is presented. It consists of two parts: 1. The first part, similar to the traditional E-model, ranged from 1 to 5 for narrowband codecs. 2. The second part is dedicated to wideband codecs. To extend MOS range for wideband codecs, the upper limit of this range needs to be determined by mapping the range of 1 to 5 for narrowband codecs, labeled (a) in Fig. 2, to 1 to MOSnew, named (b) in Fig. 2, for wideband codecs Based on results of France Telecome [19] aiming at comparing PESQ values of wideband and narrowband to present extended PESQ.
Fig. 2. MOS domain for extended E-model
598
M. Alavi and H. Nikmehr
Fig. 3. Relationship between MOS for NB and WB
we made an interpolation and obtained (6) with R2=0.99.
Y = αX β
(6)
in which α and β are 1.033 and 0.901,respectively. In (6), X is MOSNB and Y denotes MOSWB. Using Fig. 3, we can determine upper limit of MOS domain for wideband codecs is 5.75. In the other word, MOS domain of 1 to 5 for narrowband codecs is mapped into the range of 1 to 5.75 for wideband codecs. Based on recommendation G.113 by IUT-T, the highest quality obtained for narrowband codecs belongs to G.711 codec and is equal to 4.41. This is now 5.75 in the new scale. It must be noted that the difference between the highest quality obtained from narrowband and wideband codecs in G.711 codec is about 1.06 in MOS, which is a significant value. The range of 4 to 4.4, according to Fig. 4 that is satisfactory for the user is increased to range of 4 to 5.47. This shows 3.6 times increase for the satisfaction range.
Fig. 4. Classification of voice quality for different R-Factors
A New Computational Model to Evaluate the Quality of Perceptual Voice
599
As MOS is determined in term of factor R, the way domain R changes in the new model must be studied. The maximum quality in narrowband codecs is reported 4.41 belonging to G.711 codec. Based on Fig. 4, this value is equal to 93.2 in term of R. As seen in Fig. 5, in the suggested E-model, MOS value varies from 1 to 5.5, however, using the extrapolation, the red curve in Fig. 6 is obtained that can be formulated as in (7). The R domain for the proposed model is 0 to 120. In Fig. 6, the blue curve relates to the traditional E-model expressed by (4).
Fig. 5. Classification of voice quality for the new model
Fig. 6. MOS as a function of R in the new classification
⎧1 ⎪ MOS= ⎨− 3×10−6 R3 + 6×10−4 R2 + 8.85×10−3 R +1 ⎪5.5 ⎩
R1962 into // article [ @id ="41"]
! " #
Fig. 1. Conflicting transactions
1.1
Problem Statement
In the first place, transaction isolation for XML has to cope with the same challenges as traditional relational systems. It must provide stability for data read and it must protect against phantoms, i.e., preserve stability of predicates evaluated like, e.g., range scans over content. Queries and updates for semi-structured data impose here some new challenges not known so far. In the following, we point out the most important aspects: On the one hand, there is the ordered, hierarchical nature of XML, which leads to complex dependencies between the “data atoms”, i.e., the nodes of the document tree. Thus, serializability requires that structural updates are carefully isolated and do violate neither vertical nor horizontal relationships seen by concurrent transactions. On the other hand, when using XQuery-like languages, it is particularly difficult to predict what data will be accessed by a query. As a consequence, it is generally impossible to determine in advance – just by looking at the statements – whether two given queries will conflict with each other or not. One might assume that the latter is a consequence of the absence of schema information. However, as we will show, even the presence of a schema – pre-defined or dynamically derived from the actual data – may not be sufficient. Let us assume that two transactions T1 and T2 access a document as depicted in Figure 1: T1 queries the subtree of the “Science” journal, while T2 inserts a small year fragment into the subtree of article 41. Obviously, T1 and T2 conflict with each other and concurrent access is prohibited. However, the statements themselves contain no hint about that there may be a conflict. Using schema information, we could at least derive that there is a conflict potential. Unfortunately, knowledge about potential contention within a document is not sufficient to establish maximal permissive concurrency control. This is similar to the relational world, where some conflict potential is already given whenever transactions concurrently access and modify the same table. High concurrency can only be achieved when concurrency control is applied to the smallest meaningful granule, i.e., tuples in the relational world and nodes in the XML world. A major difference between relational tuples and nodes in an XML tree is the amount of information that each data atom represents. A single XML node
A Scalable Framework for Serializable XQuery
685
usually carries much less information – namely a name and a value – than a single tuple, which may have tens of attributes or even more. Further information is encoded in the XML document structure, typically by grouping related nodes in subtrees. Consequently, queries and updates often refer to variable-size subtrees. A fact that has to be naturally supported by XML concurrency control. The above observation does not necessarily mean that transactions are always interested in completely expanded subtrees. Instead, queries often address subtrees by certain predicates and then read only smaller parts of them – a great chance to increase concurrency. For example, if the return clause of transaction T1 would refer to $j/article/author instead, it would not conflict with the insertion of T2 and both requests could be processed in parallel. To summarize, we can state the following key observations: – Read/write or write/write dependencies between two transactions can only be decided in a meaningful way at the instance level, i.e., the document. – High concurrency requires small granules of isolation and the smallest granule available in XML is a node. – Mostly, subtrees are the logical target granule for queries and updates, but they vary in size and may be nested. – Typical usage allows concurrent reads and writes even within a single subtree. – XML’s ordered tree structure adds new dimensions for the evaluation of predicates and, thus, for the appearance of phantoms. Taking these observations into account, it becomes obvious that design and implementation of correct and scalable concurrency control for XQuery is a challenging task. Nevertheless, we believe that it can be reduced to a small set of clear-cut measures that can be efficiently realized and improve the overall value of native XML DBMS. 1.2
Contribution
In this paper we analyze the isolation requirements of XQuery Update and disclose sources of anomalies during query processing. Our findings take general XML query processing strategies into account and, thus, are applicable to a great variety of systems. We also present new extensions to our proven XML lock protocol taDOM providing effective protection against the XML-specific “schema phantoms”. All concepts were implemented in our native XML DBMS research prototype and provide a scalable framework with guaranteed serializability for XQuery. The remainder of this paper is organized as follows: We analyze the update primitives of XQuery Update and their isolation requirements in Section 2. Section 3 briefly introduces XML query processing and investigates general caveats and sources of phantoms which different query evaluation strategies have to observe. We present our approach implemented in our native XML DBMS XTC in Section 4, and review related work in Section 6. Finally, Section 7 summarizes the paper.
686
2
S. B¨ achle and T. H¨ arder
XQuery Update
The XQuery Update Facility is an XQuery extension for declarative updates of XML. Similar to SQL, it allows to query “nodes of interest” for which an update like, e.g., value change or insertion of a new subtree should be performed. Before the actual updates are applied, all of these so-called target nodes are collected together with the requested update operation in a pending update list. In a second phase, the list is checked to, e.g., eliminate duplicate deletes of a single node etc. and, finally, the updates are performed. Because of this two-phased processing, XQuery updates are called snapshot-based. Note that this defines only the semantics of update expressions and that XQuery neither requires or nor favors snapshot isolation in concurrent environments. The extension defines five kinds of update expressions: insert, delete, replace, rename, and transform. The latter, however, applies updates only to copies of the target nodes. As these copies are per definition private to a transaction, we must not consider transform expressions as an issue for concurrency control. Trivially, transactions must be guaranteed that the state of every read node is committed and stable; of course, modified nodes do not become visible to others before commit. In the following, we will focus on implicit consequences of updates for other nodes as potential sources of phantoms. 2.1
Update Primitives
The insert expression inserts a node or subtree relative to the specified context node. The insertion position can be precisely specified for the new previous or next sibling (before, after ) or the new first or last child (first, last). If sibling order does not play a role for the application, one may also specify “any new child” (into) to allow an actual implementation to choose the “optimal” insertion postion with regard to, e.g., storage consumption or concurrency. From the perspective of transaction isolation, all flavors of insert operations modify only a fixed set of basic properties of adjacent nodes. If the root of the new subtree is an element or a text node, then the nextSibling or previousSibling properties of the right or left sibling and, depending on the insert position, the firstChild and lastChild properties of the parent are affected. For our discussion, we need not distinguish between insertion of a single node and a whole subtree, because descendants of the root must be inaccessible to other transactions, too. If the new node is an attribute, only the correspondingly named attribute property of the parent element is affected. Figure 2 illustrates the changed foreign node properties for these two cases. Insertions affect many more properties influencing the outcome of concurrent queries like, e.g., position of all following siblings, containment for all ancestors, preceding axes of all following nodes, etc. But, they are transitively derived from the mentioned ones. Therefore, it is sufficient to ensure that inserts do not violate general repeatable-read and visibility rules for the five basic properties and that the evaluation of other structural predicates regards these transitive dependencies. The same observation holds for delete, which simply deletes the subtree rooted at the context node.
A Scalable Framework for Serializable XQuery
687
Fig. 2. Affected properties of inserts
A replace expression distinguishes between the replacement of a node/subtree with another and the update of a node’s value. The former logically translates into a sequence of delete and insert. The latter does not affect other nodes, because node identity is preserved and tree structure is not modified. Accordingly, special care is not necessary. Finally, rename changes the name of element and attribute nodes. For attributes, this operation equals to a deletion followed by an insertion under the new name. Renaming elements is similar to value updates for text and attribute nodes. It is a local operation and does not modify the tree structure. Although it changes the path of all descendants, a heavily used concept in queries, we must not impose further restrictions, because the rationale of transitive properties holds. 2.2
Phantoms
Phantom anomalies arise when the result set of a previously evaluated predicate changes due to concurrent modifications [8]. We already mentioned that a node embodies only three kinds of information: name, value and its position in the document hierarchy2. Accordingly, we can classify three different kinds of phantoms that may appear. Content-predicate phantoms step up when, e.g., attribute values or text nodes are modified and fall into a concurrently evaluated range scan. Name-predicate phantoms appear when nodes are concurrently renamed, inserted, or deleted, which fulfill a queried name predicate. Finally, structural-predicate phantoms arise, e.g., when a transaction navigates from a node to its first child and another transaction concurrently inserts a new first child in front of it. In practice, these kinds of phantoms would typically appear in combination. Consider a transaction T1 evaluates query //a/b/@c > 5 and a second transaction T2 adds a new attribute c with value 60 to any node with label b and a parent a. If T1 now re-evaluates the query, the new attribute appears as a phantom in all kinds of categories. The query of transaction T1 describes a complex predicate. As there are plenty of ways to evaluate it, we cannot easily locate a single point in a system where phantoms originate. Therefore, we will investigate common query 2
Note that we omit namespaces, types, etc. for the sake of simplicity as they do not influence the main points of this paper.
688
S. B¨ achle and T. H¨ arder
evaluation strategies for XML and distill a general principle how to prevent the emergence of phantoms.
3
Query Processing
XQuery engines can be categorized by their processing strategy into four groups: streaming, navigational, relational, and native, which embraces concepts of all former in conjunction with native XML techniques like indexing and metadata usage. The strategy is typically determined by the capabilities of the underlying storage system, if any, and non-functional requirements like, e.g., memory footprint. From the perspective of transactional concurrency, it is most important that an engine touches as few data as possible because the isolation aspect requires to keep accessed data stable until commit thereby limiting concurrency. Pure streaming and navigational engines are mostly stand-alone solutions or directly embedded in applications. They work on a per-file basis, which implies that they always access whole documents making concurrent transactional read and write access impossible. Relational engines run on top of standard RDBMSs and translate XQuery to SQL, having documents shredded into relational tables. Consequently, they are per se ACID compliant and allow concurrent queries and updates of the tables with the shredded documents. The underlying concurrency control mechanisms, however, are blind for the actual semantics of XML and XQuery, and potential concurrency is jeopardized. Achievable concurrency depends on the shredding scheme and the degree to which it allows to use column-based indexes to reduce the number of tuples that must be touched and to perform XML-level updates with low side-effects on the shredded data. Native engines can draw from plentiful techniques and data access alternatives to tackle a query. In addition with context knowledge about the inherent data model and query properties, they allow for very efficient query processing. A desired side-effect for our purposes is that efficient evaluation most often implies minimal access to a document. Accordingly, we focus on native engines and analyze pro’s and con’s for concurrency of native query processing algorithms. 3.1
Basic Concepts
XML engines base on the traditional stages of query processing: translation, planning and optimization, and execution. First, a query is parsed, checked, and translated into an internal representation, a so-called query plan. In the second stage, the logical query plan is transformed into a – hopefully – efficient physical query plan, which is finally processed in the third stage. The whole process is a very complex topic, which we do not want to detail here. For our purposes, it is sufficient to look at the physical query plans, because they define how the data is accessed and, accordingly, where isolation properties might be violated. A physical query plan is a data flow graph with a single output node and several input nodes. The output node returns the query result, typically serialized into a string, and the – possibly empty – pending update list, which has to be processed. Input nodes can be any type of physical access to documents, but also
A Scalable Framework for Serializable XQuery
689
sources for “non-physical” input like node constructions, arithmetic and logical expressions, literals, function calls, etc. Inner nodes, finally, represent the actual query processing logic in form of operators or algorithms. Amongst them are traditional ones like select, join, and sort, but also – depending on the platform – XML-specific ones like structural join, twig join, or other primitives for the nested-loops-like for construct of XQuery. General processing logic and various path processing algorithms are already quite complex. But even worse, interdependencies between them, introduced by their combination in a query plan, are even inscrutable. Node identifiers, for example, mostly encode structural relationships and are used by algorithms to compute identifiers of related nodes. Some systems include information to directly compute the whole path for each node and, thus, allow to evaluate many predicates for theirs ancestors without actually accessing them. In such settings, many predicates over paths and content will be evaluated in manifold constellations, making it unfeasible to enumerate all potential sources of phantoms. The above shows that any plans to implement concurrency control by reasoning about the semantics of the query must necessarily fail. The complexity, however, only draws the attention from a clear-cut, even trivial fact: Independent of the query, it will be sufficient to protect both explicitly and implicitly gathered information from concurrent modification until commit, whenever a document is physically accessed. Explicit information is identity, name, and value of a node. Implicit information is all meta knowledge gained and exploited during query processing. If the requirement for repeatable read for both kinds of information is met, phantoms cannot occur, because even complex predicates can only be evaluated out of this basic data. The roadmap for the realization of a waterproof isolation concept is now clear. We have to identify all alternatives for physical document access (access path) and determine how much information about the document a particular implementation really delivers – with a close eye on the critical properties and types of information identified in Section 2. Then, we have to install efficient, yet maximal permissive measures to protect the returned data from modifications through concurrent transactions. 3.2
Access Paths
Availability of several access paths allows a system to choose the cheapest combination to answer a query. If only navigational access is available to answer a query //a/b/@c>5, for example, the document must be traversed node by node to find each match. If, however, a special XML index that contains all attributes on the path //a/b is available, all candidate attributes may be read efficiently from the index and only the conditions name=c and value>5 must be checked requiring document access, and so on. Generally, we observe that the more complex the information provided by an access path is, the less nodes have to be touched, and, in turn, the higher is the concurrency achievable. Without – here irrelevant – consideration of physical properties, the vast number of XML storage and indexing structures can be classified into specific access
690
S. B¨ achle and T. H¨ arder
path classes3 . First and most important is the document store itself. It allows for direct node access, navigation in the tree structure, and bulk reconstruction of document fragments. Accordingly, in addition to its role as “node store”, the document store can be seen as an index for tree structure predicates. The two other kinds of information carried by nodes, values and names, can be indexed by special content and element /attribute indexes, respectively. They map the property of a node to an identifier, which can be used to look up the related node in the document store. Finally, advanced path and CAS (content and structure) indexes combine all three kinds of information and allow to evaluate complex path predicates with minimal effort. With this great variety, selection of appropriate access paths to feed operators in a query plan is challenging. Identification of path and other predicates suitable to be processed with a powerful path or CAS index, for example, is not a simple task. Nevertheless, demand for high concurrency encourages to exploit them whenever possible to reduce the number of nodes to be accessed.
4
Concurrency Control in XTC
XTC is our research platform for native XML database concepts, such as storage, indexing, query processing, transaction isolation and crash recovery [13]. It uses a flexible storage layout and supports the query engine with powerful indexing capabilities. XTC also provides full ACID transactions based on the tailored XML lock protocol taDOM [12], which initially targeted only to navigational APIs. In the following, we will give a r´esum´e of its key aspects, before we extend its scope to full XML query support. 4.1
taDOM
The key of taDOM is to transfer the idea of hierarchical locking [7] to document trees and to enrich the protocol with lock modes aligned to the permissible concurrency of XML updates. The protocol provides transactional isolation for the existing structure and content. According to the general principle, a suitable lock and intention locks for all ancestors must be acquired, before a node is accessed. To master the acquisition of intention locks efficiently, we depend on prefix-based node labels like DeweyIDs or OrdPaths [9], because they allow for the computation of all ancestor node labels without further physical access. However, such labeling schemes are already widely established in XML DBMS because of their benefits for query processing. taDOM yields its high concurrency with lock modes that focus on minimal protection requirements of XML-specific operations. As depicted in Figure 3, it distinguishes between shared access for single nodes, tree levels, and whole subtrees, and exclusive access for single nodes and subtrees. With these modes 3
In practice, the classes are not strictly disjoint. A specific implementation might fall into several classes and may provide all or only a subset of the access operations of a class.
A Scalable Framework for Serializable XQuery
691
Fig. 3. Special taDOM lock modes
it is, e.g., possible for a query to iterate over a node and all its children, while, at the same time, nodes and subtrees in the subtrees of its grandchildren are updated. Lock overhead can easily be controlled by switching lock coverage from the very fine node level to the coarse subtree level. Whenever a transaction physically or logically navigates from a node to a related one, a structural predicate is evaluated that has to be kept stable. taDOM in conjunction with prefix-based node labels already delivers this protection for many predicates like, e.g., ancestor/descendant, following/preceding, following-/preceding-sibling, etc. However, the danger of phantom inserts and deletes remains in three cases: navigation from a node to its first and last child respectively, navigation between direct siblings, and navigation from an element to one of its attributes. If you recall the discussion in Section 2.1, these are the identified critical foreign node properties affected by update operations. To overcome this issue, so-called edge locks [11,15] were introduced, which are simply fixed-predicate locks that must be acquired whenever one of these properties is read or modified. The example in Figure 4 illustrates the concept. Transaction T1 starts at node p, navigates to its first child and to the next sibling, acquiring shared locks for each node visited and each edge passed. Transaction T2 now attempts to append a new node c requiring exclusive locks for affected foreign node properties, i.e., edges. The request for the lastChild edge of p can be granted, because the lock is free. The request for the nextSibling property of b, however, is incompatible with the shared request of T1 and T2 must be blocked. The initial solution proposed the processing of edge locks orthogonal to node locks with simple read, write, and update lock modes. Attribute edges were handled also separately with so-called phantom locks. Having learned from efficiency experiments, we merged our concepts and model all edges as nodes with pre-defined positions amongst the actual nodes to profit from lock escalation heuristics. In various experiments, we proved that taDOM not only provides compelling concurrency but can also be implemented efficiently [1,2,14]. We also addressed advanced topics like deadlock prevention through update lock modes and
692
S. B¨ achle and T. H¨ arder
Fig. 4. Edge locks
dynamic lock escalation. The confinement to logical document trees makes the protocol independent of the underlying document store – except for the need of prefix-based node labels. It must only provide atomicity for concurrent read and write operations and must also take implications of sophisticated storage layouts into account for transaction rollback and crash recovery. Although these are interesting aspects, we will not discuss them further, because implementation details are beyond the scope of this paper. 4.2
Indexes
Physical storage in XTC omits redundant element nesting and stores only leaf nodes of the document tree [10]. The ancestor path, i.e., the inner structure of a document, can be computed at any time with a leaf’s DeweyID and its PCR (path class reference) – an integer identifying the node’s path in a structural summary of the document. The structural summary, called path synopsis, is itself a small tree reflecting all unique paths within a document. Figure 5 shows a DeweyID-labeled document and the corresponding path synopsis. By combining DeweyIDs and PCRs, we can also create sophisticated indexes, which may be carefully adjusted to document properties and query requirements [16]. Using permutations of PCR, DeweyID, and, optionally, content of a node, we have various opportunities to build key/value pairs for different types of path and CAS indexes. They can be precisely scoped with path patterns and content type specifications to specific node sets. The path synopsis is used to identify the set of PCRs matching the path patterns, which greatly simplifies creation, use, and maintenance of an index. Additionally, we can employ a two-staged element index, which allows for efficient access to all elements with the same name in document order. It is logically the same as a path index for the pattern //*, but has different physical properties. Of course, we can use this technique also for attribute names or exploit PCRs to index only a subset of all node names. Finally, XTC also supports plain conventional content indexes, which map content and attribute values to DeweyIDs. For concurrency control, a big advantage of all our four index types is that they are realized with standard B*-trees. This enables us to employ standard index locking techniques, which do not only lock the index entries for repeatable reads, but also the gaps between them to prevent phantom inserts and deletes.
A Scalable Framework for Serializable XQuery
1. 1.3
1.5
1
1.7
1.3.3 1.5.3 1.7.3 1.3.5
693
2
3
4
5
1.3.3.3 1.3.5.3 1.5.3.3
Fig. 5. Document and path synopsis
Note that even renaming elements does not violate consistency of our PCR-based indexes, because a rename implies that the PCRs of all descendants also change, and, accordingly, it results in normal index updates. Our current implementation uses ARIES key/value locking [17] for all index types, which uses separate locks on index keys. Of course, any other index locking approach preserving serializability and further sophisticated measures to reduce the lock overhead are also applicable [4,6]. In future work, we will work on new strategies to harmonize the interplay between index locking and taDOM to further reduce lock overhead. 4.3
Schema Phantoms
The path synopsis is undoubtedly the central data structure for all document accesses. Therefore, we rely on its performance and avoid to burden it with heavy-weight concurrency control. In contrast, we relaxed some properties to increase throughput. First, a path synopsis must not necessarily be minimal, i.e., it may contain paths without counterparts in the document. In other words, a path synopsis only grows and deletes must not take care if the last instance of a path in the document is deleted; stale paths may be removed by isolated maintenance tasks. Second, a path synopsis contains no payload data and, thus, newly created paths may be shared directly with other transactions. Once a new path is created and a PCR is assigned, it is immutable. While the above is great for minimal synchronization overhead in the data structure, we cannot completely dispense transactional concurrency control for a path synopsis. As a kind of dynamic schema, it lends itself as a powerful vehicle for query optimization and, especially, index selection. During query planning, we match path expressions against the path synopsis to get a set of matching PCRs. This set can be used by the optimizer to choose appropriate indexes to answer the query. A PCR set, however, reflects only a snapshot of the current document structure, and this may lead to so-called schema phantoms.
694
S. B¨ achle and T. H¨ arder
Assume a transaction T1 matches the path expression //c against the path synopsis in Figure 5. The current PCR set is {3}, and the optimizer may choose to read all matching nodes from a path index /a/b/c. As only nodes on this path will be covered and protected by the index, a transaction T2 may create a new path /a/d/c with PCR 6 in the document and commit. If T1 re-evaluates the path //c, the PCR set is now {3, 6} and the optimizer must not use the same path index again. Instead, the document may have to be scanned and nodes inserted by T2 will appear as phantoms. The problem of schema phantoms arises whenever the path synopsis is “misused” to make statements about the non-existence of certain paths. In the above example, the PCR set was used to justify the application of an index, which is in general too narrow to answer the desired path expression. Similar problems arise when empty PCR sets are taken as indication that whole branches of a query plan must not be executed, because they are expected to return no result. Accordingly, we can say that the phenomenon of schema phantoms already appears in the planning phase and not in the execution phase. There are two possible solutions to the problem. The simplest way, the optimizer is never allowed to choose too narrow indexes or to cut query branches although the path synopsis indicates that it is reasonable. In a real environment, however, we can observe that a path synopsis grows only infrequently and, thus, it is desirable to leverage all indexes available to the maximum extent. We developed a straightforward solution. Whenever a transaction matches a path expression against the path synopsis, a shared lock for the expression is acquired. Transactions creating new paths must probe these locked expressions matching the new path with instant requests for exclusive locks – a type of lock that is directly released at the moment it is granted. This way, writers are delayed until all readers that might have missed the new path have ended. As schema extensions are rare situations and search for locked expressions matching the new path can be easily truncated, general impact on writers is very low. Note also that matching queries will never have to wait for a shared expression lock, because exclusive locks are instantly released when granted.
5
Insightful Experiment
We can illustrate the effects of a specific query evaluation strategy on our locking protocol using a distinct experiment. We compared four different strategies for query Q1 of the widely-used XMark benchmark [21]: let $auction := doc (" auction . xml ") return for $b in $auction / site / people / person [ @id = " person0 "] return $b / name / text ()
The Scan plan evaluates the query using a single scan over the whole document. ElementIndex constructs the path /site/people/person with a structural join over three element index scans for the respective element names. The
A Scalable Framework for Serializable XQuery
1000
10000 Scan ElementIndex PathAndContentIndex CASIndex
1000 # locks
Execution time [ms]
10000
100
Scan ElementIndex PathAndContentIndex CASIndex
100
10
10
1 110KB
695
1.1MB
11MB
110MB
1 110KB
1.1MB
11MB
110MB
Fig. 6. Query execution times and number of requested locks
attribute predicate and the final result construction are evaluated using navigation. Finally, PathAndContentIndex and CASIndex identify person elements using a join over a path index /site/people/person and content index scan for “=person0” and a CAS index /site/people/person/@id for “=person0”, respectively. Both plans construct the final result using navigation. We executed all plans for XMark documents of size 110KB, 1.1 MB, 11MB, and 110MB in XTC on a server with 4 quad-core Intel Xeon 2,66GHz and 4GB memory. XTC was configured with 64KB pages and a 64MB buffer and lock escalation was turned off to investigate the access behavior of the different plans. As expected, the query execution time given in Figure 6 directly correlates with the number of nodes each plan accessed. The scan scaled poorest with document size although the result size remained stable with one qualified node. The ElementIndex plan performed much better but response time also degraded slowly, because the attribute predicate must be checked for all persons qualified by the structural join. The response times of the last two plans remained constantly low in the range from 5 to 30 ms for all sizes. Their big advantage is the ability to evaluate the highly selective content predicate with an index access first; this dramatically reduces the intermediate result size. The CASIndex plan only needs a single access to the CAS index to evaluate the qualifying path expression. A look at the number of locks acquired by each execution strategy in Figure 6 might be a bit suprising at first. The Scan, although touching always each node, constantly acquired only 4 locks. Three were acquired to locate the document in the database4 ; and the document root node was locked with a shared subtree lock (SR) for the scan. Consequently, concurrency is limited by scan-based plans to shared access. The overhead of PathAndContentIndex and CASIndex is also constant. In contrast to the Scan, however, their locks only cover the actually accessed nodes and allow concurrent modifications everywhere else in the document. In this discipline, ElementIndex reveals its undesirable access behavior. Although this strategy generally performs adequately and is, therefore, widely used in native engines, it “spreads” access, i.e., locks over the whole document. Accordingly, this strategy tends to increase both runtime and memory consumption and also reduces concurrency more than necessary. 4
Similar to relational systems, which store their metadata catalogs in tables, XTC uses an XML document for metadata.
696
6
S. B¨ achle and T. H¨ arder
Related Work
To the best of our knowledge, only a small fraction of the work on XML concurrency control copes with full support for XQuery and XQuery Update. Instead, most proposals focus only XPath, subsets of XPath, or home-brew path expression languages. We do not consider the latter here because they lack practical relevance and restrict ourselves to the few XQuery-capable solutions that found their way into products or prototypes. MonetDB/XQuery is a powerful system implemented on top of the columnstore MonetDB. It uses a pre/post encoding scheme to shred documents into relations which implies their reorganization after structural updates. Its answer to reduce maintenance effort and to increase throughput under concurrent updates is an update-friendlier table layout and a combination of shadow paging together with page-level and document-level read/write locks [3]. Commutative delta operations help to avoid concurrency bottlenecks when encoding changes have to be propagated up the document tree. The mechanism described provides snapshot isolation, but, contribution [3] neither states on concurrency achieved nor deadlock threats raised by page-level locks. DGLOCK [5] and (S)XDGL [18,19] are hierarchical lock protocols applied to structural summaries similar to our path synopsis instead of document nodes. SXDGL additionally uses MVCC to isolate readers with snapshot isolation. While these approaches promise minimal lock overhead, they come with some practical shortcomings. They require general predicate locks, e.g., on content, to reduce contention on the nodes of the summaries. This leads to serious performance penalties, when lock compatibility decisions require document access to check if predicates overlap. Further, identification of paths and, accordingly, choice of correct yet sufficiently permissive locks in advance is a complex issue and only manageable for simple queries. Optimistic concurrency control for XQuery, finally, has, so far, only been proposed in [20]. However, the approach is quite complex and has never been proved to scale to serious data volumes.
7
Conclusions
Poor support for intra-document concurrency in native XML DBMSs is an unnecessary restraint. Nowadays, the way documents, i.e., semi-structured, hierarchical data, must be used and organized is determined by the DBMSs and not – as it should be – by the applications. Analysis of general isolation requirements of XQuery and concurrency pitfalls in native XML query processing lead to a central observation: Serializable, phantom-free, and highly concurrent query processing can be achieved when the problem is reduced to the provision of maximal permissive concurrency control for all data access paths within a system. One must ensure that the data delivered as well as the implicitly exhibited information is protected against concurrent modifications.
A Scalable Framework for Serializable XQuery
697
This requirement for repeatable read couples the goal of high concurrency directly with the goal to touch as few data as possible during query processing. XML’s tendency to group and query related information in subtrees supports this objective in a natural way. Accordingly, we emphasize the value and encourage the use of efficient path indexes and CAS indexes to profit from both fast query processing and increased concurrency. With their expressiveness, relevant subtrees can be identified very quickly and further processing can be scoped to avoid scattered document access, which also burdens concurrency. Our solution is taDOM, a hierarchical XML lock protocol, in conjunction with standard index locks. It embraces XML specifics like subtree locality, path processing, and common types of XML indexes, but does not affect the degrees of freedom which the query engine can utilize. We have implemented all concepts in XTC to accomplish a real concurrent and guaranteed phantom-free native XML DBMS. Experiments also confirm that our concepts effectively increase concurrency and can easily trade overhead off against parallelism.
References 1. B¨ achle, S., H¨ arder, T.: The Real Performance Drivers Behind XML Lock Protocols. In: Bhowmick, S.S., K¨ ung, J., Wagner, R. (eds.) DEXA 2009. LNCS, vol. 5690, pp. 38–52. Springer, Heidelberg (2009) 2. B¨ achle, S., H¨ arder, T., Haustein, M.P.: Implementing and Optimizing FineGranular Lock Management for XML Document Trees. In: Zhou, X., Yokota, H., Deng, K. (eds.) DASFAA 2009. LNCS, vol. 5463, pp. 631–645. Springer, Heidelberg (2009) 3. Boncz, P.A., Flokstra, J., Grust, T., Keulen, M., Manegold, S., Mullender, K.S., Rittinger, J., Teubner, J.: MonetDB/XQuery-Consistent and Efficient Updates on the Pre/Post Plane. In: Ioannidis, Y., Scholl, M.H., Schmidt, J.W., Matthes, F., Hatzopoulos, M., B¨ ohm, K., Kemper, A., Grust, T., B¨ ohm, C. (eds.) EDBT 2006. LNCS, vol. 3896, pp. 1190–1193. Springer, Heidelberg (2006) 4. Lomet, D.: Key Range Locking Strategies for Improved Concurrency. In: VLDB, pp. 655–664 (1993) 5. Grabs, T., B¨ ohm, K., Schek, H.-J.: XMLTM: Efficient Transaction Management for XML Documents. In: CIKM, pp. 142–152 (2002) 6. Graefe, G.: Hierarchical locking in B-tree indexes. In: BTW. LNI, vol. P-65, pp. 18–42. Springer, Heidelberg (2007) 7. Gray, J.: Notes on Database Operating Systems. In: Operating Systems: An Advanced Course. LNCS, vol. 60, pp. 393–481. Springer, Heidelberg (1978) 8. Gray, J., Reuter, A.: Transaction Processing: Concepts and Techniques. Morgan Kaufmann, San Francisco (1993) 9. H¨ arder, T., Haustein, M.P., Mathis, C., Wagner, M.: Node Labeling Schemes for Dynamic XML Documents Reconsidered. Data & Knowledge Engineering 60(1), 126–149 (2007) 10. H¨ arder, T., Mathis, C., Schmidt, K.: Comparison of Complete and Elementless Native Storage of XML Documents. In: IDEAS, pp. 102–113 (2007) 11. Haustein, M.P., H¨ arder, T.: A Lock Manager for Collaborative Processing of Natively Stored XML Documents. In: Proc. SBBD, pp. 230–244 (2004)
698
S. B¨ achle and T. H¨ arder
12. Haustein, M.P., H¨ arder, T.: An Efficient Infrastructure for Native Transactional XML Processing. Data & Knowledge Engineering 61(3), 500–523 (2007) 13. Haustein, M.P., H¨ arder, T.: Optimizing Lock Protocols for Native XML Processing. Data & Knowledge Engineering 65(1), 147–173 (2008) 14. Haustein, M.P., H¨ arder, T., Luttenberger, K.: Contest of XML Lock Protocols. In: VLDB, pp. 1069–1080 (2006) 15. Helmer, S., Kanne, C.-C., Moerkotte, G.: Evaluating lock-based Protocols for Cooperation on XML Documents. SIGMOD Record 33(1), 58–63 (2004) 16. Mathis, C., H¨ arder, T., Schmidt, K.: Storing and Indexing XML Documents Upside Down. Computer Science – Research & Development 24(1-2), 51–68 (2009) 17. Mohan, C.: ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. In: VLDB, pp. 392–405 (1990) 18. Pleshachkov, P., Chardin, P., Kuznetsov, S.O.: XDGL: XPath-Based Concurrency Control Protocol for XML Data. In: Jackson, M., Nelson, D., Stirk, S. (eds.) BNCOD 2005. LNCS, vol. 3567, pp. 145–154. Springer, Heidelberg (2005) 19. Pleshachkov, P., Kuznetsov, S.O.: SXDGL: Snapshot Based Concurrency Control Protocol for XML Data. In: Barbosa, D., Bonifati, A., Bellahs`ene, Z., Hunt, E., Unland, R. (eds.) XSym 2007. LNCS, vol. 4704, pp. 122–136. Springer, Heidelberg (2007) 20. Sardar, Z., Kemme, B.: Don’t be a Pessimist: Use Snapshot-based Concurrency Control for XML. In: ICDE, p. 130 (2006) 21. Schmidt, A., Waas, F., Kersten, M.L., Carey, M.J., Manolescu, I., Busse, R.: XMark: A Benchmark for XML Data Management. In: VLDB, pp. 974–985 (2002)
A Simulation Discipline in OpenUP to Satisfy Wireless Sensor Networks Requirements Gian Ricardo Berkenbrock and Celso Massaki Hirata Department of Computer Science Instituto Tecnol´ ogico de Aeron´ autica - ITA S.J. Campos, SP, Brazil
[email protected],
[email protected]
Abstract. Embedded software for networked devices is becoming popular. One example is wireless sensor networks (WSN). WSN are a technology used to collect data from different sources and they can be applied in monitoring and instrumentation area. The development of WSN offers complex challenges. Developers should be aware of restrictions such as limited storage, battery consumption, low accuracy sensor, and short transmission range. WSN are highly dependent on application requirements mainly due to the above restrictions. So, one application is hardly equal to another. In general, application requirements of WSN include fault-tolerance, load-balance, scalability, customized hardware, and deployment area coverage. There is not a specific process to address the development os WSN applications. Open Unified Process is an iterative software development process that is intended to be minimal, complete, and extensible, and because of these features it is a good candidate for WSN application development. However, OpenUP does not support the challenges and requirements of WSN systems, because it does not have specific tasks that consider such requirements. Then in order to address this lack of support, this paper proposes a simulation discipline in OpenUP to satisfy the WSN application requirements. An example of use of the proposed process is shown. Keywords: Wireless sensor network, Software development process, OpenUP, Simulation Discipline, Environmental monitoring.
1
Introduction
Wireless sensor networks are composed of nodes that have capability to sense and communicate over-the-air to each other. In addition, the nodes can perform local processing and they have local storage. In order to deliver the collected data to a base station in a multi-hop scenario, nodes transmit data using ad-hoc communication. Nodes impose constraints to the system such as short communication range, low bandwidth, small memory, and limited battery. Then, typical scenarios for WSN applications are environmental monitoring, surveillance of F. Zavoral et al. (Eds.): NDT 2010, Part II, CCIS 88, pp. 295–305, 2010. c Springer-Verlag Berlin Heidelberg 2010
296
G.R. Berkenbrock and C.M. Hirata
installations or areas, such as, home, border, or building, object tracking, precision agriculture, bridge monitoring, hospital monitoring, and herd monitoring. Moreover, the feasibility of WSN are highly dependent on application requirements mainly due to the restrictions aforementioned. Even when the application is similar to other one, one must perform a complete application verification and validation in the new environment because the behavior of WSN can be different from that one deployed in the previous environment. However, one might face some problems when developing WSN applications. The difficulties include requirements satisfaction, gap between model and implementation, and short development time[1,2,3]. Thus, one should consider the use of specific software development process to improve the development organization and to enable a better project management. Software development process [4] is a set of activities whose goal is the development or evolution of software. An example of software development process is Open Unified Process (OpenUP) [5]. OpenUP is an iterative open-source software development process that is intended to be minimal, complete, and extensible [6]. Nevertheless, OpenUP does not address the specific requirements for development of WSN systems. Thus, it is difficult to achieve a predictable system behavior that complies with the WSN application requirements. Furthermore, the use of simulation is a valuable verification technique for the system development due to the diversity of requirements for WSN applications, distributed nature of embedded systems, the complexity to model analytically a WSN, the difficulty for debugging and profiling such systems, and the need to perform evaluation at different levels (application, network protocol, operating system, hardware)[7,8,9,10,11]. However, simulation is poorly explored in OpenUP. The remainder of the paper is organized as follows. Section 2 presents the background for our proposal. It includes an overview of wireless sensor networks focusing on the need of simulation, a brief overview of software development process, and OpenUP. Section 3 presents and discuss the simulation discipline in OpenUP. Section 4 presents an illustrated use of the proposed process. Finally, in Section 5 we present some conclusions and discuss future work.
2 2.1
Background Wireless Sensor Networks
Wireless sensor networks are composed of small, low cost, and dispensable devices called sensor nodes or just nodes, which can communicate over-the-air to each other using an embedded radio. Nodes have sensing capability and usually are applied to monitor some phenomenon. Nodes can also be deployed very close to some phenomenon or inside it. In order to deliver the collected data to the base station, it is common that nodes communicate in an ad-hoc way until the data is delivered to the base station. WSN components include nodes, monitored area, base station (BS) and control station. Fig. 1 depicts an example of WSN components and their relationships. In WSN, the number of nodes can
A Simulation Discipline in OpenUP to Satisfy WSN Requirements
297
Fig. 1. Components of Wireless Sensor Network
vary from a few to hundreds of thousand. WSN are application-oriented because of the aforementioned constraints. Currently, the most used operating system of WSN is TinyOS [12]. TinyOS is an event-based OS developed by Berkeley University. Developing software for WSN is not a trivial task. One could consider noncritical task the development for only a single node without the complexity of wireless communication, but the development of software for the entire network is not easy and specially when one needs to make sure that the software complies to the application requirements. Due to aforementioned challenges, one must consider the use of simulation during the development process. Yet, in order to achieve more refined results, when it is essential, one might consider the use of a prototype of a small scale WSN. 2.2
Software Development Process
Software development process can be seen as a set of guidelines that assist a team to perform the work in a disciplined way from the concept to the deployment of a given solution. Thus, the usage of software development process aids the developer from specification to deployment. In Rational Unified Process (RUP), there are four phases: inception, elaboration, construction, transition [13]. In each phase a defined milestone must be achieve to enable the team to start the next phase and proceed with the software development. The life cycle-based process models include waterfall, incremental development, iterative development, and spiral model [14]. We choose to work with an iterative and incremental development model called OpenUP. Like RUP, it uses iterative and incremental models [13]. OpenUP is an adaptation of RUP. OpenUP is an agile and lightweight process and it includes only fundamental contents. The most central concepts in OpenUP are roles, tasks, artifacts, and activities [6]. Roles refer to the essential skills needed by teams in order to perform tasks. The roles specified by OpenUP are stakeholder, analyst, architect, developer, tester, and project manager. Tasks refer to a unit of work performed by roles, for example, the primary tasks performed by analyst are Define Vision, Find and Outline Requirements, and Detail Requirements. Artifacts refer to something that is produced, modified, or used by a task. Activities refer to tasks and their
298
G.R. Berkenbrock and C.M. Hirata
sequences. OpenUP targets small teams and few months of development effort [15]. Such characteristics are of the WSN application development.
3
Integrating Simulation Discipline into Open Unified Process
There are some studies reporting the extension and integration of OpenUP [6,15]. However, they do not address the WSN application development. And complex products, such as WSN, need special handling of requirements as well. There is a lack of software development process to address the development of a WSN application project. The main reason why development processes do not fit to WSN development is their inability to meet requirements of WSN satisfactorily and they do not provide an organized way to perform simulation activities. In addition, the integration with third party systems considering data exchange between them and WSN system, employment of verification techniques as soon as required, and different viewpoints used for analysis are other characteristics that need to be addressed during the development process. Yet due to the development characteristics of WSN systems, as it was described in section 2.1, it is important to assist the development team with a disciplined mode to perform their tasks, including the simulation activities. Besides the development of an application for running on nodes, the development process must also concern on others interests. One interest is the simulation used by developers to evaluate their solutions and, in this case, it can play an important role through the design and implementation activities. One can use simulation in order to minimize type III [16] error. And, also, it is important to document the activities to perform a simulation study in a way that the knowledge about how to perform a simulation study shoud not be restricted to the simulation analyst. Thus the description of specific tasks to perform the simulation study is needed. In the next section we introduce the Simulation Discipline that can be integrating to the software development process. 3.1
Simulation Discipline
The simulation discipline corresponds to the workflow to perform a simulation study of WSN systems. It is based on simulation studies proposed in literature [17,18,19]. The simulation discipline can be used at any process phase of the OpenUP. Nevertheless, for the first time when using this discipline during the development process at least one iteration of the inception phase should be already performed. Then, one can use the simulation discipline for requirements analysis, parameter analysis, integration evaluation, and so on. In addition, this discipline is not static, the project manager can add or remove as he want some activities of this workflow or any other from the OpenUP. For example, if the organization already know some simulator or it has experience on using some specific WSN OS simulator like TOSSIM from TinyOS or like COOJA from ContikiOS, then he can remove it or ignore it, in this workflow, the Analyse the simulator activity.
A Simulation Discipline in OpenUP to Satisfy WSN Requirements
299
Fig. 2. Workflow for simulation discipline
This discipline was created to attend specific tasks to perform the simulation during the software development process for WSN application. The discipline workflow is depicted in Fig. 2. The activities of this workflow include planning, development, and experimentation. The activities for planning are Refine Requirements, Define Objectives, Define the Input/Output Data, and Analyse the Simulator. The activities for development are Collect Data, Implement the Model, Validate the Model, and Model Revision. The activities for experimentation are Design the Experiments, Run the Experiments, Assess the Results, and Implement the Results. The roles that are responsible to perform this discipline are Phenomenon Specialist, Simulation Analyst, and Simulation Developer. The role Phenomenon Specialist aids the Simulation Analyst role during the execution of the following activities: Refine Requirements, Define the Input/Output data, and Assess the Results. The role Simulation Developer is responsible to perform the following activities: Implement the Model, Model Revision, and Run the Experiments. When the Run the Experiments activity is performed, the Simulation Analyst assists the primary role. And the remain activities are the responsibility of the Simulation Analyst.
4
Case Study
This case study aims to assess the use of simulation discipline for the software development process for WSN application in an ordinary real environment.
300
4.1
G.R. Berkenbrock and C.M. Hirata
Description
The sugar cane spirits (Cacha¸ca) is a genuine Brazilian drink, known worldwide. Its production began in the sixteenth century. According to Brazilian law, which standardizes and ranks drinks, cacha¸ca is defined as a typical beverage produced in Brazil, with an alcoholic strength of 38 % vol (thirty-eight percent by volume) to 48 % vol (forty-eight percent by volume) at a temperature of 20o C (twenty degrees Celsius). It is obtained by distilling the fermented juice of sugar cane with peculiar sensory features. The production cycle of sugar cane spirits starts with the milling of sugar cane, through the preparation of the wort, fermentation, distillation, filtration and dilution. After filtering and resting, the sugar cane spirits can now be bottled or go to wooden barrels for aging. The higher the aging of the sugar cane spirits, the higher is the value of the drink [20]. In the aging process, the characteristics of the sugar cane spirits changes, improving its qualities with new flavors, new tastes and new coloring. User Environment The main environment place is a warehouse for aging drinks (WAD). During the solution use there might be some tasks where people are involved, for example: deployment task, monitoring task, and maintenance task. The platform is the TelosB. The maintenance task should occur only once per year. The solution should present soft-alarms when the environment condition is closer to the upper or lower limits. And emergence-alarms when the conditions are greater or less than the upper and lower limits imposed. The WSN should be integrated to a database system in order to keep the change history saved. Functional Requirements The warehouse for aging the sugar cane spirits has dimension of 8 meters wide per 80 meters long and 5 meters height. This warehouse has storage capacity of 800 barrels with capacity of 250 liters each or 200000 liters in total. The barrel dimension is 95 cm of height, 72 cm of diameter at middle, and 58 cm of diameter at top/bottom, according to Ferreira [21]. As mentioned by Silva [22], during the aging time (from 1 year up to 5 years) the temperature must be within the range of 15o C (fifteen degrees Celsius) and 20o C (twenty degrees Celsius) and the air relative humidity must be within 70% and 90%. Fig. 3 shows the arrangement of barrels in the WAD and the gray dots represent the nodes’ positions. In WSN the nodes must be able to set upper and lower range for some environmental variable (temperature and humidity). If the sensed value is near to the boundaries values, the node must rise an alarm and send it to the control station. It only stops to send the alarm when the control station notifies it that the alarm was received and it only is in condition to send the alarms again after 5 units of time interval. Nodes should be able to connect to the network and it must be able to perform the following activities: sensing, routing, disseminating, and aggregating. The threshold has two levels, either for upper and lower boundaries. One is called soft threshold and it is 10% lower than the second one that
A Simulation Discipline in OpenUP to Satisfy WSN Requirements
301
Fig. 3. Warehouse illustration with the barrels and the position of the nodes
is the hard threshold and this one has the limit value. All the parameters must be changeable and be retrievable through the control station. At least, once a day the node must inform its sensing values to the sink node. All information received in the sink node is retransmitted to the control station. When nodes send the alarm message to the control station, they also indicate their battery level. The nodes are deployed 1 meter above the barrels and 2 meters from each other in the same line. There are three lines of nodes. The Control Station must communicate to the network using the node sink, i. e., it is directly connected to the sink node. The control station must also indicate the battery level of all nodes that perform any communication with it. Additionally, it must indicate the upper and lower threshold used by each node. The Control Station must be able to set any parameter of a single node or of the whole network and it must indicate alarms received and notify back to the source node. Results The case study was performed by only one developer. The developer performed all the roles. During the execution of one simulation study, the time needed to execute each activity was measured. The whole simulation study was completed in fourteen days, including weekends. The state diagram of the node’s application is depicted in Fig. 4. In order to increase the network lifetime, the distributed balance sensing approach was used. The approach keeps a WSN working only with half of its nodes for sometime. For example, in this case study the node reads its sensors in a 30 minutes interval. However, not all nodes read the sensors at the same time (they do at a 2 minutes interval), when the node is booting half of the nodes sleep for about 15 minutes
302
G.R. Berkenbrock and C.M. Hirata
Fig. 4. State diagram of the application for the node Table 1. Measured time for each activity Activity Refine Requirements Define Objectives Define Input/Output Data Analyse the Simulator Collect Data Implement the Model Validate the Model Design the Experiments Run Experiments Assess the Results Model Revision Implement the Results
Time (%) 2.14 1.43 0.71 0.71 0 28.57 7.14 3.57 1.43 2.86 0 0
and then they start to read their sensors in a 30 minutes interval. In this way, the sensors reading interval is 30 minutes but the environment is monitored each 15 minutes. With this approach, we can get the lifetime around of three months using an ordinary AA battery. Fig. 5 depicts the relative time spent for each activity and the values are listed in the Table 1. The activities with zero time were not executed. As expected the activity that needs more effort to be completed is the Implement the Model following by the Validate the Model. Although the activity Run Experiments used more time to be completed, most of the time was used to run all the simulations ( 24 in total) of the experimentation part. In each simulation we tried different MAC protocol parameters, such as, duty cycle, listening interval, and transmission power.
A Simulation Discipline in OpenUP to Satisfy WSN Requirements
303
Fig. 5. Relative time to perform each activity
Using this discipline to perform the simulation study aided the developer to increase the study organization and to be more objective in each step of the process. As a future work of this research is to simulate the workflow of the simulation discipline and improve the development process with a prototyping discipline.
5
Final Remarks
In this article we present a simulation discipline to be performed within a software development process, in our case, the OpenUP. Using the proposed workflow for performing the simulation the development team can perform its work in a more organized way. We add three roles and twelve activities. In addition, it is important to have the simulation study integrated to a software development process in a such way that the project manager can keep track of the activities and requirements. Our case study was to monitor a warehouse used for aging drinks. The simulation process was performed in fourteen days and the results complied with our expectation. Our next step in this research is to develop a process on how to perform a prototyping study and then perform a simulation study of this part in a software development process.
References 1. Arora, A., Dutta, P., Bapat, S., Kulathumani, V., Zhang, H., Naik, V., Mittal, V., Cao, H., Demirbas, M., Gouda, M., Choi, Y., Herman, T., Kulkarni, S., Arumugam, U., Nesterenko, M., Vora, A., Miyashita, M.: A line in the sand: a wireless sensor network for target detection, classification, and tracking. Computer Networks 46, 605–634 (2004)
304
G.R. Berkenbrock and C.M. Hirata
2. Hasler, A., Talzi, I., Beutel, J., Tschudin, C., Gruber, S.: Wireless sensor networks in permafrost research: Concept, requirements, implementation, and challenges. In: 9th Intl. Conference on Permafrost (NICOP 2008), pp. 669–674 (2008) 3. L´edeczi, A., V¨ olgyesi, P., Mar´ oti, M., Simon, G., Balogh, G., N´ adas, A., Kusy, B., D´ ora, S., Pap, G.: Multiple simultaneous acoustic source localization in urban terrain. In: IPSN 2005: Proceedings of the 4th International Symposium on Information Processing in Sensor Networks, Piscataway, NJ, USA, p. 69. IEEE Press, Los Alamitos (2005) 4. Sommerville, I.: Software Engineering, 7th edn. Addison-Wesley, Reading (2004) 5. IBM: Openup (2009), http://www.eclipse.org/epf/openup_component/openup_index.php (accessed in May 15, 2009) 6. Borg, A., Sandahl, K., Patel, M.: Extending the openup/basic requirements discipline to specify capacity requirements. In: IEEE International Conference on Requirements Engineering, pp. 328–333 (2007) ¨ 7. Osterlind, F., Dunkels, A., Eriksson, J., Finne, N., Voigt, T.: Cross-level sensor network simulation with cooja. In: Proceedings of the First IEEE International Workshop on Practical Issues in Building Sensor Network Applications (SenseApp 2006), Tampa, Florida, USA (November 2006) 8. Fraboulet, A., Chelius, G., Fleury, E.: Worldsens: development and prototyping tools for application specific wireless sensors networks. In: IPSN 2007: Proceedings of the 6th International Conference on Information Processing in Sensor Networks, pp. 176–185. ACM, New York (2007) 9. Levis, P., Lee, N., Welsh, M., Culler, D.: Tossim: accurate and scalable simulation of entire tinyos applications. In: SenSys 2003: Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, pp. 126–137. ACM, New York (2003) 10. Egea-Lopez, E., Vales-Alonso, J., Martinez-Sala, A., Pavon-Mari˜ no, P., GarciaHaro, J.: Simulation tools for wireless sensor networks. In: International Symposium on Performance Evaluation of Computer and Telecommunication Systems (July 2005) 11. Wen, Y., Wolski, R., Moore, G.: Disens: scalable distributed sensor network simulation. In: PPoPP 2007: Proceedings of the 12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 24–34. ACM, New York (2007) 12. Hill, J., Szewczyk, R., Woo, A., Hollar, S., Culler, D., Pister, K.: System architecture directions for networked sensors. SIGPLAN Not. 35(11), 93–104 (2000) 13. Kruchten, P.: The Rational Unified Process: An Introduction, 3rd edn. Addison Wesley, Reading (2003) 14. Madachy, R.J.: Software Process Dynamics. IEEE Press, Los Alamitos (2008) 15. Ardi, S., Shahmehri, N.: Integrating a security plug-in with the openup/basic development process. In: International Conference on Availability, Reliability and Security, pp. 284–291 (2008) 16. Balci, O., Nance, R.: Formulated problem verification as an explicit requirement of model credibility. Simulation 45(2), 76–86 (1985) 17. Banks, J., Carson, J.S., Nelson, B.L.: Discrete–Event System Simulation, 3rd edn. Prentice-Hall, Englewood Cliffs (1999) 18. Law, A.M., Kelton, W.D.: Simulation Modeling and Analysis, 3rd edn. McGrawHill, New York (2000)
A Simulation Discipline in OpenUP to Satisfy WSN Requirements
305
19. Balci, O.: Guidelines for successful simulation studies. In: Proceedings of Simulation Conference, pp. 25–32 ( December 1990) (Winter) 20. SEBRAE-MG: Diagn´ otico da cacha¸ca de minas gerais (in portuguese). Technical report, Servi¸co de Apoio a `s Micro e Pequenas Empresas de Minas Gerais (2001) 21. Ferreira, C. (Supervisor): Vinifica¸ca ˜o (2009) (in portuguese), http://www.aesbuc.pt/twt/ETGI/MyFiles/MeusSites/Enologia/2005/ Madeira vt.htm (accessed in November 22, 2009) 22. da Silva, J.M.: Cacha¸ca: O mais brasileiro dos prazeres, 2nd edn. Anhembi Morumbi, S˜ ao Paulo (2006) (in portuguese)
A Toolkit for Application Deployment on the Grid Jie Tao and Holger Marten Steinbuch Centre for Computing Karlsruhe Institute of Technology, Germany {jie.tao,holger.marten}@kit.edu
Abstract. This paper describes a toolkit developed for supporting Grid users in the task of application deployment on computing resources. The toolkit presents a graphical interface where users give required information, simply with context menu and mouse actions. More importantly, the jobs for starting the deployment process are automatically created and submitted to the Grid without the need of any interaction activity from the user. In this way, the implementation details on the Grid is hidden from the application developers. Keywords: Grid computing, application deployment, graphical interface.
1
Introduction
Grid computing [7] has been investigated for more than a dozen of years. The well-established technology is bringing scientists of various fields together to share computational resources and scientific data. Grid computing applies the job-submission model for running applications. In this model, a computing task has to be first described using a kind of job description language and then submitted to the Grid resources usually via a resource broker. Different Grid middleware stacks [1,4,6] have individual requirements on the job descriptions; however, they commonly allow only executables specified in a job description file. Therefore, applications must be pre-compiled for the architectures of the target Grid work nodes on which the applications run. This can be a burden to the users when their local machines do not meet the architecture requirements. Fortunately, the gLite [2] middleware supports application deployment, where the source codes of an application can be deployed on the work nodes and executables can be created directly on them. Nevertheless, application deployment on gLite is a tedious task for users and requires their specific knowledge, especially the details of deployment commands. We developed a toolkit to simplify the users’ task. The toolkit provides a set of graphical views for users to upload the source codes, to specify the actions, and to observe the progress and results of the deployment task. With this support, users not only are freed of understanding the implementation details but also F. Zavoral et al. (Eds.): NDT 2010, Part II, CCIS 88, pp. 503–508, 2010. c Springer-Verlag Berlin Heidelberg 2010
504
J. Tao and H. Marten
enjoy the graphical interface that is more straightforward and easier to use than the command line interface. The remainder of the paper is organized as following. Section 2 first gives an overview of the application deployment concept in gLite. Section 3 describes the design and views of the developed toolkit, followed by the implementation details in Section 4. The paper concludes in Section 5 with a short summary and the future directions.
2
Experiment Software Installation
The concept of application deployment [9] was designed and implemented within the LHC Computing Grid (LCG) project. Main goal of this concept is to allow authorized users to install software on computing resources of the Grid. The installed software, called Experimental Software, is published in the information system, so that the software can be shared across the users in an individual virtual organization (VO). The software is identified with a tag which is specified by the user. The software can also be removed. To implement this concept, LCG developed a script, called lcg-ManageSoftware, which has to be installed on each work node to steer the process of installing, validating, and removing the software. The script defines several actions, which can be specified as parameters by invoking the script. lcg-ManageSoftware must be invoked by job submission. This means that a job description has to be created with all required parameters specified and all input files correctly pointed. Then the job is submitted to the Grid and its execution is examined to see whether the job is successfully terminated. Finally, the information system has to be checked to make sure that the application tag is added or removed. These tasks are undoubtedly not easy for non-professional Grid users.
3
Graphical Interface for Application Deployment
To support the user in the task of application deployment, we developed a graphical interface that simplifies the use of the LCG script for Experimental Software Installation. This toolkit was developed within the g-Eclipse project. g-Eclipse [3,5] aims at building a generic framework that allows users to access the power of the existing grid infrastructures via a standardized, customizable, and intuitive interface. This framework is designed for all Grid users, operators, and application developers. Grid users can interact with grid resources in a simple, graphical way without having to know the technical details. Resource providers can use the intuitive tools to operate and maintain the grid sites, manage the virtual organizations, and perform benchmarking. Application developers reduce the development cycle with the g-Eclipse support of remote building and deployment tools. g-Eclipse is developed on top of Eclipse [8]. We relies on the g-Eclipse functionality to access the Grid for software install/uninstall.
A Toolkit for Application Deployment on the Grid
3.1
505
Application Deployment
The menu item for software install is combined with the computing elements shown in the VO folder of the g-Eclipse framework. Figure 1 depicts a screenshot of the g-Eclipse platform with an open action list.
Fig. 1. The start menu for Application Deployment
Project is a basic concept of g-Eclipse. For any Grid activities on g-Eclipse a Grid project has to be created. Figure 1 shows a Grid project with the name glite that contains several folders including a VO folder called geclipse. The VO folder of g-Eclipse presents VO-related information such as available computing elements, storage elements, and services. The installed software stacks are also depicted in this folder under its subfolder Applications. As software install is an action on computing elements (CE), we put this functionality in the action list of a CE. The first wizard page of Application Deployment, shown in the left side of Fig. 2, allows the user to specify the CEs on which the software will be installed. The CE, where the action is started, is automatically selected. In case that several CEs are selected, the application software are installed on all of them. Users can use the buttons on the right side to select or deselect all CEs. The next wizard page for application deployment, shown in the right side of Fig. 2, allows the user to specify the application source. The source can be on-line created files contained in any project in the runtime workspace of the user, like the project named cproject in the example; or some software packages or files already stored in the local disk or any storage element.
506
J. Tao and H. Marten
Fig. 2. The wizard page for software install: selecting computing elements (left) and selecting the application source (right)
The next wizard page allows the user to specify a tag for identifying the installed software. This tag will be used later to uninstall the software. The tag can be just a name or a combination of the name, the version, and the created date, time, etc. With the last wizard page, users can specify the location of the install script file. The install script is used to guide the process of building the applications. The top window on the right side of Fig. 1 actually shows a sample install script called test.sh. This script simply tells the system to first go to the directory where the source of the application is located, in this case the path specified by the environmental variable VO GECLIPSE SW DIR. In the following a subdirectory is created where the C file of a test program is extracted from the tarball and compiled. We provide the users with a template to simplify their work of writing the install script. 3.2
Application Uninstall
Deployed applications can be removed from the Grid site. This includes the deletion of the software on the computing elements and the removal of the application tags from the information system. The uninstall action can be started either by a single application tag shown in the folder Applications/CE or at the level of the folder. The former only selects the specified application while the latter works with all installed applications on the CE. Figure 3 is an example of the first case. It can be seen that all application tags in the example have a suffix “to-be-validated”, which is added to the user-given tags by lcg-ManageSoftware automatically and removed after the deployed software is validated. The uninstall wizard contains two pages, one for users to choose the applications to remove and the other for users to specify the uninstall script. The first page allows the users to select one, several, or all applications. This is useful when a user starts the uninstall menu at a wrong location and has to change his selection. The uninstall script usually contains commands for the system to delete the source files and the directories holding them.
A Toolkit for Application Deployment on the Grid
507
Fig. 3. The start menu for Application Uninstall
Similar to the deployment task, a job description is automatically created and submitted to the associated CE with lcg-ManageSoftware as the executable. The progress of the job is monitored and the result is delivered to the user. In case of a successful uninstall operation, the application tag disappears from the folder Applications and the folder CE.
4
Implementation
The implementation of the toolkit comprises of two tasks. One task is to program the wizards and wizard pages shown in the previous section. As Eclipse has specific support for producing graphical interfaces, the implementation of the views for application deployment and uninstall is not a tedious work. The other task is to program the actions. As described in Section 2, the script developed within the LCG project covers all actions, including install, uninstall, and validation, the focus of this task is therefore on creating a job to execute this script on the working nodes of a computing element. We have programmed the system to automatically generate a Grid job with the action of copying the install script to the work nodes of the specified CE and then starting a selfwritten version of the lcg-ManageSoftware script on it. We modified the original script in order to add information for showing the reasons of a failing action. The job execution on the Grid is monitored and the progress of the job execution is reported to the user with a small window on the g-Eclipse platform. Actually, gLite provides the functionality of monitoring the running jobs; our
508
J. Tao and H. Marten
task is to continuously check the job status to know whether a job is done and if it is successfully terminated.
5
Conclusions
In this paper, we present a toolkit for supporting application deployment. With this help, users are freed not only from the deployment process but also from the necessity of understanding the underlying implementation. Additionally, users are well informed with concrete reasons when the task fails. The toolkit has been tested by g-Eclipse developers and Grid users who have no any knowledge about the LCG implementation of the experimental software install. All of these volunteers have successfully installed/uninstalled test software without any problems. This renders the toolkit as simple and useful. The approach is combined with gLite but can be extended to any other middleware stacks. However, most of the existing middleware stacks do not support software installation. A more general approach may be a Cloud service, so called Build as a Service, which maintains a server to hold the application software and create the executables. This is our future work.
References 1. Erwin, D.: UNICORE - A Grid Computing Environment. Concurrency, Practice and Experience 14, 1395–1410 (2002) 2. Laure, E., et al.: Programming the Grid with gLite. Computational Methods in Science and Technology 12(1), 33–45 (2006) 3. Kornmayer, H., et al.: gEclipse- An Integrated, Grid Enabled Workbench Tool for Grid Application Users, Grid Developers and Grid Operators based on the Eclipse Platform. In: Proceedings of the 2nd Austrian Grid Symposium, Innsbruck, Austria (September 2006) 4. Surridge, M., et al.: Experiences with GRIA - Industrial applications on a Web Services Grid. In: E-SCIENCE 2005: Proceedings of the First International Conference on e-Science and Grid Computing, pp. 98–105 (2005) 5. Wolniewicz, P., et al.: Accessing Grid computing resources with g-Eclipse platform. Computational Methods in Science and Technologie 13(2), 131–141 (2007) 6. Foster, I.: Globus Toolkit Version 4: Software for Service-Oriented Systems. In: Proceedings of the International Conference on Network and Parallel Computing, pp. 2–13 (2006) 7. Foster, I., Kesselman, Tuecke, S.: The Anatomy of the Grid: Enabling Scalable Virtual Organizations. International Journal of Supercomputer Applications 15(3) (2001) 8. Gamma, E., Beck, K.: Contributing To Eclipse: Principles, Patterns, And Plug-Ins. Addison-Wesley Professional, Reading (2003) 9. Santinelli, R., Campana, S.: Experiment Software Installation in LCG-2 (July 2005), http://grid-deployment.web.cern.ch/grid-deployment/eis/docs/ ExpSwInstall/sw-install.html
A Trial Evaluation of Distributed Campus Network Environment Based on Comparison of Theoretical and Real Performance of Packet Flow Amount Using Video Transmission System Yoshiro Imai1,*, Yukio Hori1,*, Kazuyoshi Kawauchi1, Mayumi Kondo2, Toshikazu Sone1, Yoshitaka Seno1, Nobue Kawada1, Shinobu Tada1 Miho Yokoyama2, and Rieko Miki2 1
Kagawa University, Information Technology Center (* Graduate School of Engineering), Hayashi-cho 2217-20, Takamatu City, 761-0396, Japan 2 Kagawa University, Information Group, Saiwai-machi 1-1, Takamatsu City, 760-8521, Japan
[email protected], {imai,horiyuki}@cc.kagawa-u.ac.jp
Abstract. In order to manage and utilize distributed campus network environment efficiently, a video transmission scheme has been designed for simultaneous communication among multiple areas. The scheme is organized with a specified server, a digital video encoder, client devices and so on. This paper introduces design of our video transmission scheme, formulation procedure for performance evaluation of real campus network and demonstration of quantitative evaluation of the network with comparison of its measured packet flow amount. And it also illustrates a summary of experimental results for the above performance evaluation and describes several comments to future problem solving for phenomena, which has been met in such a real experiment. Keywords: Network conference system, protocol of DVTS (Digital Video Transmission System), System design and performance evaluation, Distributed campus network environment.
1 Introduction As ICT-based services go more popular, network itself becomes more important and more indispensable for our lives. Such services of network include e-Learning, eHealthcare, e-Commerce, e-Government, e-Verything and so on. Even in a distributed environment of several schools, users(including students, teachers and other staffs) always utilize their network and apply it to ICT-based services described above. At the same time, they need direct communication with face-to-face style. In such a case, e-Conference, i.e. dual directed video transmission, is very much useful to realize face-to-face communication on network in a distributed campus network environment. Therefore, some e-Conference systems are developed and utilized in several domains. We have designed an inter-multipoint video transmission scheme and applied it to network conference in a real distributed network environment. A prototype system is F. Zavoral et al. (Eds.): NDT 2010, Part II, CCIS 88, pp. 152–161, 2010. © Springer-Verlag Berlin Heidelberg 2010
A Trial Evaluation of Distributed Campus Network Environment
153
prepared and evaluated in the case of a practical usage. And we have tried to evaluate our distributed campus network environment through comparison of theoretical and real values of packet flow amount. After that, we have analyzed a result of the above performance evaluation in order to do for problem solving and introduce some idea for improvement of network. In the following sections, this paper describes a simple explanation of target network to be evaluated (our distributed campus network environment), a configuration of our inter-multipoint video transmission scheme and a formulation of our scheme to analysis and evaluation of system performance. It introduces theoretical value of packet flow amount and compares them with measured value of packet flow amount for our prototype system. Finally, it also summarizes system performance, detected problem and future works for improvement.
2 Overview of Inter-multipoint Video Transmission Scheme An inter-multipoint video transmission scheme has been designed to realize 2-way communication for every user. Fig.1(a) gives an organization overview of our scheme. Its subsystem consists of a DVTS-encoder, some DVTS-clients and an IPTunneling Server. The DVTS-encoder can obtain dynamically altering pictures and transform them to video signal stream in the mode of DVTS protocol. In Fig.1(b) this encoder is symbolized as "video camera" and needs special functionality, which can support real-time conversion. The DVTS-client in Fig.1(b) can receive DTVS-based signal stream, decode it into a series of video pictures on a Personal Computer (PC). Such a client provides viewing function for signal stream of DTVS protocol and plays a role of real-time decoding mechanism, which may be placed face to face with the above DVTS-encoder through network.
IP-Tunneling Server
DVTS-encoder
DVTS-clent
(b) its Element subsystem (a) Overview of DVTS-video transmission system
Fig. 1. Overview of Distributed (i.e. inter-multipoint) video transmission system
154
Y. Imai et al.
IP-Tunneling Server (subsequently denoted as IPTS) provided in Fig.1(b) is a special information server to catch the target information and/or signal generated by DVTS-encoder in each segment, encapsulate it into a special IP packet and throw the result to the according IPTS directly. When one IPTS receives encapsulated information/signal from another IPTS in another segment, the former IPTS decapsulates such information/signal, i.e. converts them to be viewed on DTVS-clients in its segment. Fig.1(a) shows such a mechanism with 2 broken arrows. Namely, both of righthanded and bottom DVTS-encoders generate encapsulated information simultaneously. Such information can be transmitted by means of right-handed and bottom IPTS's into left-handed one. The left-handed IPTS provides such information to its 2 DVTS-clients respectively.
3 Estimation for Packet Flow Amount This section presents an estimation of packet flow amount of IPTS. It is assumed that there are n times of IPTS's in our scheme and the i-th IPTS in the focused segment has only one DVTS-encoder and mi times of DVTS-clients with focusing attention on the i-th IPTS. Fig. 2 shows an inter-multipoint video transmission scheme for network conference system, which consists of n times of IPTS's with one DVTS-encoder and mi times of DVTS-clients respectively. As focusing attention on the i-th IPTS, packet flow amount about it can be assumed as follows. We are separating input-bound packet flow amount and outputbound one for the i-th IPTS (focused IPTS). At first, in-bound packet flow amount includes (n-1) times packet flow amount from other IPTS and ei times of packet flow amount from its DVTS-encoders. Secondly, out-bound packet flow amount includes (n-1) times packet flow amount to other IPTS and mi times packet flow amount to its DVTS-clients. Generally speaking, with focusing attention to i-th IPTS, it is assumed that there are ei times of DVTS-encoders, mi times of DVTS-clients and (n-1) times of other IPTS's. So the corresponding IPTS has {ei +(n-1)} times of packet flow amount for in-bound and {(n-1) + mi} times of packet flow amount for out-bound. Totally, the i-th IPTS has {ei +2(n-1)+ mi} times of packet flow amount. In order to evaluate system performance of the above inter-multipoint video transmission scheme, we assume the following three applicable conditions in using our prototype as network conference system: (a) Each IPTS receives the same size of packet flow amount from every DVTSencoder. (b) Each DVTS-client can receive the same size of packet flow amount generated from the objective DVTS-encoder. Namely, it can be assumed to be almost loss less. (c) The speed rate of packet is the same as other one. Namely, it is normally that speed rate is unique and the same as others in the whole system. In this point, it is assumed that the size of packet flow amount from each DVTSencoder is same and its value is N (bit per second: bps). It is normal and never loses generality. So the i-th IPTS (i.e. each IPTS in the later section) has N{ei +2(n-1)+ mi } (bps). Frankly speaking, when our inter-multipoint video transmission scheme is applied to network conference system, organization of IPTS, DVTS-encoder and
A Trial Evaluation of Distributed Campus Network Environment
155
(n-1) times of IPTS's
the i-th IPTS (focused IPTS) ei times of DVTS-encoders (normally ei = 1)
mi times of DVTS-clients Fig. 2. An inter-multipoint video transmission scheme for network conference system
DVTS-client is simple and very much similar to one another. Almost always, the whole system may employ similar figure. For example, every IPTS has the same number of DVTS-encoder and the same ones of DVTS-clients naturally.
4 Formulation for Network Performance Evaluation This section presents specification of use conditions to configure a network conference system with an inter-multipoint video transmission scheme. And then it is defined to realize formulation of packet flow amount for our scheme with such conditions in the later half of this section. 4.1 Use Condition to Configure Network Conference System with Inter-multipoint Video Transmission Scheme In order to realize a network conference system with our inter-multipoint video transmission scheme, we should define constant of general parameters as specific
156
Y. Imai et al.
value. At first, it is supposed that there can be one video camera and one microphone in each conference room normally. So ei = 1. Normally each conference room needs to communicate with the other conference ones. If such a conference room is corresponding to the i-th IPTS, numbers of the other conference ones are (n-1) and it needs {mi =(n-1)} times of DVTS-clients for the other conference rooms. Sometimes, there are the only n times of DVTS-clients necessary because the last DVTS-client is corresponding to the i-th conference room itself. So mi =(n-1), sometimes mi =n. There are at most 5 points of conference rooms simultaneously in usual network conference system of our University. So n=2, 3, 4, or 5. N is the size of packet flow amount of DVTS-encoder, and we have employed such a DVTS-encoder that its output can be controlled by means of 10Mbps, 15Mbps, 20Mbps or 30Mbps. In other words, we can select N in the following mode: N = 10M[bps], 15M[bps], 20M[bps] or 30M[bps]. Secondly, it is described that specification of IPTS should transmit and/or receive N{ei +2(n-1)+ mi } of packet flow amount. In the case of mi =(n-1), the size of packet flow amount of IPTS is calculated in the following, N{ei +2(n-1)+ mi } = N{1 + 2(n1) + (n-1)}=N(3n-2). In the case of mi =n, it is also calculated as follows, N{ei +2(n1)+ mi } = N{1 + 2(n-1) + n}=N(3n-1). On the other hand, it is assumed that there is only one IPTS in the according segment. It is one of normal conditions to use IPTS practically. Each IPTS can get packet flow amount from its DVTS-encoder and send it to the other IPTS's. So total amount of packet which each IPTS receives and transmit are N{2(n-1)}=2N(n-1)[bps]. With the above parameters, we can express a formulation of packet flow amount of IPTS and inter-segment. 4.2 Formulation of Packet Flow Amount for Our Transmission Scheme On the condition of N ={10M[bps], 15M[bps], 20M[bps], 30M[bps]} and n={2, 3, 4, or 5}, we can formulate the two-mode of packet flow amount size of IPTS and total amount of packet between each segment. Each value can be denoted as N(3n1), N(3n-2) and 2N(n-1), respectively. For example, there are 3 inter-multipoint video transmission scheme employed for a real network conference system. We can control the volume of output from DVTS-encoder into 20M[bps]. Such a case needs that n=3, N=20M[bps]. Formulation about three values of N(3n-1), N(3n-2) and 2N(n-1) are simply specified as 160M[bps], 140M[bps] and 80M[bps], respectively. We can define the formulation about the size of packet flow amount between IPTS's in the according segments theoretically which is shown in the Table 1. The upper limit of communication rate is at most 100M[bps]. On the above case, 2N(n-1) becomes 80M[bps]. It is similarly 100M[bps]. Because other users communicate one another, so there may be over 100M[bps] between specific segments. In such a case, packet flow can be regulated and some accidents may occur. By means of using boldface numbers, table 1 indicates such cases with warning message. Such
A Trial Evaluation of Distributed Campus Network Environment
157
Table 1. Packet flow amount between IPTS's in the according segments (Theoretical value, Unit: M[bps])
N= 10M[bps] N= 15M[bps] N= 20M[bps] N= 30M[bps]
n= 2
n= 3
N(3n-1)= 50 N(3n-2)= 40 2N(n-1)= 20 N(3n-1)= 75 N(3n-2)= 60 2N(n-1)= 30 N(3n-1)= 100 N(3n-2)= 80 2N(n-1)= 40 N(3n-1)= 150 N(3n-2)= 120 2N(n-1)= 60
N(3n-1)= 80 N(3n-2)= 70 2N(n-1)= 40 N(3n-1)= 120 N(3n-2)= 105 2N(n-1)= 60 N(3n-1)= 160 N(3n-2)= 140 2N(n-1)= 80 N(3n-1)= 240 N(3n-2)= 210 2N(n-1)= 120
n= 4 N(3n-1)= 110 N(3n-2)= 100 2N(n-1)= 60 N(3n-1)= 165 N(3n-2)= 150 2N(n-1)= 90 N(3n-1)= 220 N(3n-2)= 200 2N(n-1)= 120 N(3n-1)= 330 N(3n-2)= 300 2N(n-1)= 180
n= 5 N(3n-1)= 140 N(3n-2)= 130 2N(n-1)= 80 N(3n-1)= 210 N(3n-2)= 195 2N(n-1)= 120 N(3n-1)= 280 N(3n-2)= 260 2N(n-1)= 160 N(3n-1)= 420 N(3n-2)= 390 2N(n-1)= 240
a formulation can be introduced theoretically and easily up to a case with n=10 or more.
5 Comparison of Theoretical and Real Values This section presents comparison of theoretical values of the formulation described above and real values of packet flow amount of IPTS/segment by measurement with Layer 2 switch. 5.1 One-to-One and Inter-3 Point Areas Communication with Inter-multipoint Video Transmission Scheme In our experiments, we have investigated two different patterns of one-to-one communication and inter-3 point area one with suitable IPTS's. Two results of the above experiments are illustrated in the following graphs. CASE(I) is an experiment for one-to-one communication, and CASE(II) is another experiment for inter-3 point area communication. Both of two experiments have been performed and measured with 24-ported Cisco Catalyst 2960G, which provides direct connectivity with other segments and local devices such as IPTS, DVTS-encoder, and DVTS-clients. Measurement of each packet flow amount can be done with facility of 2960G. We can obtain the measured values of N(3n-2) and 2N(n-1) directly. Fig.3 shows the result graph for comparison of theoretical values of N(3n-2) and 2N(n-1) and the according measured ones by 2960G. As you recognize clearly and easily, we can obtain very much preferred comparison result, which measured values can come into line of theoretical ones. Namely, it is said definitely that predicted value can coincide with real one. Such a case demonstrates that our scheme will work suitably.
㪧㪸㪺㫂㪼㫋㩷㪽㫃㫆㫎㩷㪸㫄㫆㫌㫅㫋㩷㪽㫆㫉㩷㪸㪺㪺㫆㫉㪻㫀㫅㪾㩷㪠㪧㪫㪪㩷㫀㫅㩷㫋㪿㪼 㪪㪼㪾㫄㪼㫅㫋
158
Y. Imai et al.
㪈㪋㪇 㪫㪿㪼㫆㫉㪼㫋㫀㪺㪸㫃㩷㪭㪸㫃㫌㪼㪑㩷㪥㩿㪊㫅㪄㪉㪀 㪫㪿㪼㫆㫉㪼㫋㫀㪺㪸㫃㩷㪭㪸㫃㫌㪼㪑㩷㪉㪥㩿㫅㪄㪈㪀 㪤㪼㪸㫊㫌㫉㪼㪻㩷㪭㪸㫃㫌㪼㪑㩷㪥㩿㪊㫅㪄㪉㪀 㪤㪼㪸㫊㫌㫉㪼㪻㩷㪭㪸㫃㫌㪼㪑㩷㪉㪥㩿㫅㪄㪈㪀
㪈㪉㪇 㪈㪇㪇 㪏㪇 㪍㪇 㪋㪇 㪉㪇 㪇 㪇
㪌 㪈㪇 㪈㪌 㪉㪇 㪉㪌 㪊㪇 㪦㫌㫋㫇㫌㫋㩷㫇㪸㪺㫂㪼㫋㩷㫆㪽㩷㫋㪿㪼㩷㫋㪸㫉㪾㪼㫋㩷㪛㪭㪫㪪㪄㪼㫅㪺㫆㪻㪼㫉
㪊㪌
Fig. 3. CASE(I) one to one communication using 2 IPTS's system
Fig.4 shows the result of CASE (II) whose graph compares theoretical values of N (3n-2) and 2N (n-1) with the according measured ones. Dislike the above CASE (I), the theoretical values have very little correspondence with the measured ones. Especially, as packet flow amount generated form DVTS-encoder grows more and more, difference between theoretical and measured ones spreads wider and wider. After more than 15Mbps of output of DVTS-encoder, packet flow amount of IPTS and its segment have begun to be saturated or burst into the mode of breakdown. Such a case gives us an image that process of IPTS loses stream. In the subjective evaluation, there happen some kinds of communication troubles in voice and display. It works just like encouragement to result of quantitative evaluation. After output of DVTS-encoder grows 15Mbps and more, block noises make an intrusion into the display monitor and voices from speaker begin to be disturbed and audibly noisy. So we cannot use real communications in such a case.
㪧㪸㪺㫂㪼㫋㩷㪽㫃㫆㫎㩷㪸㫄㫆㫌㫅㫋㩷㪽㫆㫉㩷㪸㪺㪺㫆㫉㪻㫀㫅㪾㩷㪠㪧㪫㪪㩷㫀㫅㩷㫋㪿㪼㩷㪪㪼㪾㫄㪼㫅㫋
A Trial Evaluation of Distributed Campus Network Environment
159
㪫㪿㪼㫆㫉㪼㫋㫀㪺㪸㫃㩷㪭㪸㫃㫌㪼㪑㩷㪥㩿㪊㫅㪄㪉㪀
㪉㪇㪇
㪫㪿㪼㫆㫉㪼㫋㫀㪺㪸㫃㩷㪭㪸㫃㫌㪼㪑㩷㪉㪥㩿㫅㪄㪈㪀
㪈㪎㪌
㪤㪼㪸㫊㫌㫉㪼㪻㩷㪭㪸㫃㫌㪼㪑㩷㪥㩿㪊㫅㪄㪉㪀 㪤㪼㪸㫊㫌㫉㪼㪻㩷㪭㪸㫃㫌㪼㪑㩷㪉㪥㩿㫅㪄㪈㪀
㪈㪌㪇 㪈㪉㪌 㪈㪇㪇 㪎㪌 㪌㪇 㪉㪌 㪇 㪇
㪌
㪈㪇 㪈㪌 㪉㪇 㪉㪌 㪦㫌㫋㫇㫌㫋㩷㫇㪸㪺㫂㪼㫋㩷㫆㪽㩷㫋㪿㪼㩷㫋㪸㫉㪾㪼㫋㩷㪛㪭㪫㪪㪄㪼㫅㪺㫆㪻㪼㫉
㪊㪇
㪊㪌
Fig. 4. CASE(II) inter-3 point areas communication using 3 IPTS's system
5.2 Prospects for Comparison of Theoretical Values and Measured Ones Generally speaking, we have good prospect for comparison result of theoretical values and measured ones in the CASE(I), where a network conference system is realized in the one-to-one communication mode with IPTS's, DVTS-encoders and DVTS-clients. Such a case will be able to provide a good environment for network conference. But more cheap methods will be suitable enough to provide only one-to-one communication, such as Skype and other simple communication media. So scalability is very much important. On the other hand, we have not relieved prospect about the CASE(II), where a network conference system is realized in the inter-3 point area communication mode of our video transmission scheme. Whenever such a network conference system is utilized in the state where DVTS-encoders generate 15M[bps] or more of output packet flow amount, block noises and audible one should happen and grow larger and larger. Such a case gives users uncomfortable situation in full progress of network conference. Some prospects from the technical view can describe that there may be some troubles in the inter-3 point area communication mode of our video transmission scheme under conditions for our current network environment. One of troubles seems to be based on channel capacity between segments. Others may be effective from system
160
Y. Imai et al.
performance of IPTS, which transfers and receives a lot of packet for other IPTS, DVTS-encoder and DVTS-clients. They are summarized as follows: (a) The former specifies a problem to improve the campus network environment. This is not only essential but also sometimes very difficult problem to be resolved for general users of campus network. But now we have a great opportunity to improve our campus network environment in Layer 2 level. With some request including our this time experimental usage of network, our network will have been improved with replacement of new L2 switches all over the campuses in the next semester. (b) The latter should be a limited problem for our application of video transmission scheme to a real network conference system. First of all, functions of ITPS should be inspected again, reconfigured (if it is necessary) and upgraded into such a level that provide a useful inter-3 point area communication mode of our video transmission scheme. (c) Comments and requests related to network environment are finally described as follows. Generally speaking, we have used 70Mbps of packet flow amount continuously between 2 and/or 3 points of multi-campus during this time experiments. Such cases need 70Mbps of channel capacity in the end-to-end communication. (d) Now, Layer 3 switches within each building of our university’s campus are all Giga-bit speed devices, however Layer 2 switches under L3 are still not Giga-bit speed but 100Miga-bit one. So some troubles including block noise and audible noise may be based on performance limitation of Layer 2 switches of our network environment. And more over, difference and inconsistency of MTU (Maximum Transfer Unit) between L3 switches and L2 ones can dominate network overhead to downgrade performance of network conference system.
6 Conclusion This paper introduces an overview of inter-multipoint video transmission scheme, its element system and formulation of packet flow amount for system performance analysis. It also describes specification of use conditions to configure a network conference system with our inter-multipoint video transmission scheme and formulation of packet flow amount for our scheme. Our paper presents comparison of theoretical values of the above formulation and real values of packet flow amount of IPTS and/or segment by measurement with Layer 2 switch (for example, Cisco Catalyst 2960G). As result of trouble analysis for network performance, we have summarized some resolutions to improve our network environment. In the experiment for one-to-one communication with our video transmission scheme, we have obtained a good comparison result of theoretical value of formulation and measured value. Such a case is suitable to realize a network conference system. On the other hand, we have not taken so agreeable result in the experiment for inter-3 point area communication with our video transmission scheme. Sometimes there are not a few block noises nor audible noises during experiment of network conference. Namely, users of network conference suffer from unstable and bad conditions during inter-3 point area communication with our video transmission scheme. In the future, we should improve either performance of our video transmission scheme and IPTS especially or capacity of network environment and speed of Layer 2
A Trial Evaluation of Distributed Campus Network Environment
161
switches, for example. Functions and scalability of IPTS should be inspected again. In order to realize entire improvement of network environment, Layer 2 switches should be upgraded and suitable requirement should include adjustment for coincidence of MTU between L2 and L3. Acknowledgments. The authors would like to express sincere thanks for Mr. Hidetaka Noma, Mr. Toshiaki Yamashita of Net One Systems Co., Ltd (Japan) and Mr. Shigeto Koike of NTT Advanced Technology Corporation (Japan) for their constructive and heart-warming contribution to realize inter-multipoint video transmission scheme. And they are grateful to Dr. Hajime Maeta and Dr. Naoto Sumida, who were both former vice presidents of Kagawa University to support our project. They are also thankful to late Mr. Hiroshi Yamaji, Dr. Toshihiro Hayashi, Mr. Ryo Takeda, Mr. Takashi Fuke, Mr. Satoshi Hirose, and Dr. Zengo Furukawa for their kind supports for experiments of network conference. This study was partly supported by Grand-in-Aid for scientific research (2008 Special Edition) from Kagawa University.
References 1. Inoue, T., et al.: Design and Implementation of the Incrementally Deployable Multicast System Based on Flexcast. IEICE Transactions on Information and Systems, The Institute of Electronics, Information and Communication Engineers (IEICE) J88-D1(2), 272–291 (2005) (in Japanese) 2. LiveSpark, http://www.ntt-at.co.jp/product/livespark/ 3. Digital Video Transfer System, http://www.sfc.wide.ad.jp/DVTS/ 4. DV-CUBE, http://www.fase.co.jp/DvCube/ 5. Cisco Catalyst 2960G, http://www.cisco.com/en/US/products/ps6406/ 6. Imai, Y., et al.: Design and Trial Evaluation of an Inter-multipoint Video Transmission Scheme for Efficient Management of Distributed Campus Network. IPSJ SIG Technical Report 2009-GN-71 (26), 151–156 (March 2009) (in Japanese)
Agent Behavior Diagram for Intelligent Agents Michal Radeck´ y, Petr Gajdoˇs, and Radoslav Fasuga Department of Computer Science, FEI, VSB - Technical University of Ostrava, 17. listopadu 15, 708 33, Ostrava-Poruba, Czech Republic {michal.radecky,petr.gajdos,radoslav.fasuga}@vsb.cz
Abstract. This paper describes our approach of modeling and developing Multi-Agent System (MAS) which extends traditional approach of process modeling. An Extended UML Activity Diagram has been proposed. Mentioned diagram makes the basis of the specification of agents behaviors and plays an important role within the process of agent reconfiguration. Keywords: Agent, ABD, Agent Behavior Diagram, UML, Activity Diagram.
1
Introduction
The MAS technology is quite youthful field of computer science that occurs on the borders where “Software Engineering”, “Artificial Intelligence” and other computer, natural and social science areas meet. The MAS technology is based on the concepts of the Complex Systems (e.g. macromolecules, ants colony, economical systems), and on the facilities and capabilities of software information systems [2][11][12][13]. The MAS can be formed as a general information system that is composed from a number of autonomous elements (called Agents). In this context, the Multi-agent System is a framework for agents, their lives, their communication and mobility and it is an environment where the goals of the particular agents should be obtained too. From the perspective of the standard information systems, the Agent are components of such systems. These components have special features like autonomy or intelligence, which is consistent with the essential properties of MAS. The typical applications of this Multi-agent technology are the large systems with a big volume of decentralization and autonomy of their elements. The overall behavior of whole system that is based on the MAS technology is formed by internal behaviors; by internal processes in the context of this research, of several elements (agents) and also by the communication between all of these elements. This paper covers research concerned with the internal agent specification based on processes inspired by standard business process approach. The main aim of this research is to offer the tool for modeling agent behaviors which should be close to common users without special knowledge about MAS. On the other hand, this modeling approach should be formed on the formal grounds that offer wide utilization. F. Zavoral et al. (Eds.): NDT 2010, Part II, CCIS 88, pp. 333–341, 2010. c Springer-Verlag Berlin Heidelberg 2010
334
2
M. Radeck´ y, P. Gajdoˇs, and R. Fasuga
Modeling of the Agent Behavior
Each agent is determined by its own objectives and the way to meet these objectives is founded on the internal behavior of a given agent. From our point of view, the internal behavior of such agent is specified by the algorithm – an order of activities, conditions, forks, sub-algortihms, etc. The term algorithm is similar to a business process term according to this research. The agent lives, behaves and reacts to stimulus and environment, according to the requirements of the algorithm. Any agent in the MAS has the main internal life process consequent on the agent’s classification from the reactive and proactive point of view. It is necessary to take into account the fact that each agent is an absolutely autonomous element of MAS and thus the internal behavior have to be based only on the processes, activities, knowledge and facilities that belong to a given agent. Then, the result behavior of whole MAS is formed by communication of separated agents and by the interconnection of several internal agent behaviors. This interaction is realized through the use of message passing adapted to the demands of MAS. In the context of MAS modeling and agents behavior, the term Agent expresses only the “type of agents”. The real separate agents are the instances of this type. It is analogous with the terms Class and Object from the object oriented approaches. The real agents (instances of agent Classes) are not issues of MAS design and modeling phase but they will appear in the implementation phase, simulation and operation of a given MAS. 2.1
Agent Behavior Diagram
The UML (Unified Modeling Language) is an essential tool suitable for process modeling. This standardized methodology is, both on the business level and analytic level of description [7,9]. It can be applicable for modeling of the internal behavior of agents as well. However, traditional UML approach can be too complex to express a simple communication pattern among agents. This usually results in unclear formalization of activity diagrams. Proposed Agent Behavior Diagram comes from UML activity diagram and uses Petri Nets for its formalization. The Agent Behavior Diagrams could contain all the elements of the standard UML Activity Diagrams, and moreover some new elements that can be used in the agent modeling process. These new elements are primary concerned with message passing between agents or with other specific attributes of MAS. In early phases of development, these extensions are supported by the implementation of special “send/receive activities” which include an additional information about message content and message receiver/sender identification, see the Figure 1. The decision elements from standard activity diagrams are improved too. A complex example of utilization of a mentioned elements is depicted on Figure 2. The modified “decision elements” and their output edges can hold the extra information. This information is usable for message-based determination of following control flow of the behavior led to the agent’s objectives.
Agent Behavior Diagram for Intelligent Agents
Main activity element shape with the name of the sended message. This name represents the message that is unique in the whole MAS.
Envelope icon for send/ receive activity indication.
getAgentName Agent_B
Main activity element shape with the name of the received message. The name of this activity can be real name of received message (in the case of one-to-one communication) or it can be replaced by “” string in the case of multiple or unknown messages receiving.
335
getAgentName Agent_A
Identification of the Agent (type of agents) acts in the receiver role during this communication. The receiver can be just one instance of Agent type (Agent_B) or all instances of a given Agent type ([Agent_B]). Identification of the Agent acts in the sender role. This name of agent can be replaced by the “” string in the case of receiving message from unknown or multiple sources.
Agent_A
[msg: getAgentName from: Agent_A]
[msg: getColor from: Agent_A]
The illustration of branching based on incoming message and standard decision element.
Fig. 1. The stereotypes of the new communication activities and illustration of decision point. These send/receive activity nodes are able to use beside the other standard activity and process elements. Internal implementation of these new activities is concerned only with preparation, en/decapsulation and receiving/sending of the message.
2.2
Rules and Relation to the WF-Nets
A couple of rules are bound together with creation process of these diagrams. At first, each process, as well as diagram, have to have just one “initial node” and just one “final node”. This prerequisite is necessary for the further connection of the processes together to model overall agent behavior. The demand of the “well-formed” diagrams is also required. There is a set of general structural rules (e.g. the level of split/join nodes preservation, no crossing of the levels of control flow) that should be kept in mind during the drawing of diagrams [1]. These rules are inspired by WF-Nets that bring ABD close to the Petri Nets. It is able to verify them, to transform them to other forms or to process them by several formal tools. The transformation is not so tricky. The activities and sub-processes are linked to transitions with control-flow places and input/output objects are transformed to places. The parts where the messages are received or
336
M. Radeck´ y, P. Gajdoˇs, and R. Fasuga
#1: WithoutNavigation car #2: WithNavigation car navigation
Inicialization
MoveToCity I_AM_LEAVING
SetDestinationAsPosition
ParkingAgent
I_WOULD_LIKE_TO_PARK
Parking
[ParkingAgent]
Parking
FindingAnotherParkingRange
I_AM_READY_FOR_YOU car parkingElement
UpdateParkingTable
ParkingAgent
parkingElement parkingTable
msg: OK_USE_PARKPLACE agent: ParkingAgent
msg: SORRY_YOU_ARE_LATE agent: ParkingAgent
parkingTable MsgTimeOut
msg: NO_FREE_PLACES agent: ParkingAgent
ParkingSelection
ParkingAgent
I_WANT_TO_PARK
I_AM_HERE
ParkingAgent
ParkingAgent
UpdateCarPosition
MoveToDestination
ParkingAgent
Fig. 2. Example of agent internal process modeled by ABD. Special elements for sending and receiving of messages are there, as well as decision element with communication based conditions. Also, the extended activity and sub-process elements with definition of input and output objects are placed within this process model. It illustrates Car agent behavior during parking process.
sent can be a more complex, it is necessary to add some special transitions to the net. The Figure 3 shows an example of mapping a part of ABD to WF-Net - Petri Net. The transformation of control flow is simple and fully covers control structures from ABD, it is activities and subprocesses are transitions with places between them. If the activities or subprocesses are generators or consumers of a set of objects, it is necessary to add object flow into the WF-Net too. Thanks to these rules, the well applicable and formalized expressions of algorithms are obtained. This example is based on the internal process, model of internal agent behavior, described by ABD. The presented two elements are the parts of the Car agent behavior during parking process. The simple, clear and formal definition of the internal agent behavior is a precondition for moving to the next phases of the multi-agent software process. Thanks to the new stereotypes established in the Agent Behavior Diagram and other additional information, it should be able to generate other types of diagrams (e.g. sequential diagrams, maps of the agents communication) as well as the source code templates of the agents and MAS automatically (e.g. interfaces of agents, class and method templates, BPEL specification [8]). As it is mentioned
Agent Behavior Diagram for Intelligent Agents
337
Msg: I_WOULD_LIKE_TO_PARK Receiver: all ParkingAgents Prepare message
Send message
I_WOULD_LIKE_TO_PARK car destination
=>
[ParkingAgent]
destination
car
Parking
FindingAnotherParkingRange
car parkplace
car #1: NewParkingFound car parkplace
#1: AfterParking car
msg: OK_USE_PARKPLACE agent: ParkingAgent
msg: SORRY_YOU_ARE_LATE agent: ParkingAgent
=>
Msg: OK_USE_PARKPLACE Sender : ParkingAgent Msg from ParkingAgent Msg: SORRY_YOU_ARE_LATE Sender : ParkingAgent
Receive Msg control-flow condition based on a given instance of received message
Msg: PARKING_IS_FULL Sender : ParkingAgent
Msg: HELLO Sender : CarAgent
ParkingAgent Parsing Msg content car
Parking
FindAnotherParkingRange parkplace
Fig. 3. Example of transformation ABD to WF-Net. Additional places (orange places) are there to provide mapping of input and output objects of activities. It is necessary to distinguish pure control-flow (bold solid lines) of Petri Net theory and object instances flow (gray dotted lines).
above, the agent internal behavior is specified by the algorithms expressed in the processes. Primary, each process is modeled as just one agent Behavior Diagram based on UML Activity Diagram. Fortunately, the process can be specified by more than one diagram in the case of multiple Realizations belong to a given process too. The Realizations are the topic of the following text.
3
Internal Agent Structure
Each agent must try to realize its tasks and to solve the upcoming situations in order to meet its design objectives during its life. From this point of view, the standard agent is consisted in definite and constricted description of its behavior already defined during the modeling phase of the agent. Therefore, there is no way to change the behavior during the agent running. It is able to do this, in the case of Intelligent agent. Such type of agents is based on the main life process model that specifies just the framework of its behavior. The agent can dynamically change the pieces of its own behavior according to the situations. This principle is denoted as behavior reconfiguration approach. The process of reconfiguration is founded on the replacement of a given part of the whole agent’s process by another one that is the most suitable for current situation and conditions. A set of possible applicable behaviors, called Realizations (defined by
338
M. Radeck´ y, P. Gajdoˇs, and R. Fasuga
Process 1
Agent A
Agent B
Primary Process
Primary Process
Process 1
Process 2
Process 2
Process 3
restricted
Process 1
Process 4
Process 3
Process 5
Process 3 Action/Reaction
extended
Process 6
Global Process Repository
Fig. 4. Structure and hierarchy of realization specification within agent and MAS itself
agent Behavior Diagram), of each “reconfiguration” point (generally the subprocess node of activity diagrams) is defined for this purpose. These definitions of the behavior can be distributed on the whole MAS as definitions of process realizations. They can be saved in some global repository or within the particular agents; actually they can be deliberated in the real-time too. Every process, expect the Primary process, can be specified by more than one diagram (see the Figure 4). Then, each diagram describes one Realization of a given process. Realizations depend upon knowledge, experiences, environment and states of agents. The Realizations can be stored within agent internal knowledge base or global MAS repository. Moreover, the agents can extend own sets of Realizations thanks to communication and cooperation with other agents and/or platform facilities. This feature enables agents to learn. The Figure 4 illustrates an example of the static processional structures of two agents and global repository. Each agent must have one Primary process that covers whole life of a given agent. This primary process and its Realization are unique in the context of a given agent. The ABD is able to be transfered between agents and thanks to this they are able to extend their knowledge base of Realizations. Some principles of inheritance could be applied there, like extensions or restrictions of a set of Realizations for each agent. 3.1
Intelligent Selection of Process Realization
The behavior reconfiguration approach represents the way how to implement intelligent agents with respect to processes [4,14]. The idea behind the reconfiguration comes from the hypothesis, that each sub-process (reconfiguration point )
Agent Behavior Diagram for Intelligent Agents
339
Processes = Reconfiguration Points Current position in the Behavior
Control Flow of the Agent Behavior in the moment of reconfiguration
All Realizations related to a given Process Inapplicable Realizations
The most suitable Realization
Applicable Realizations of a given Process
Control Flow of the Agent Behavior after the reconfiguration
Fig. 5. Reconfiguration approach during agent life
can be realized by different ways – Realizations. Reconfiguration algorithm is applied in time of process firing. Each process requires a set of input objects and can produce the outputs. The same holds for the Realizations. The ability to connect these autonomous specifications together (link initial and final element with another processes) is provided by rules of ABD construction mentioned above. The figure 5 depicts the basic scheme of mentioned reconfiguration method. At the beginning, the set of all processes and their Realizations is defined. Based on reconfiguration point (process resp. sub-process element of parent behavior – ABD), a set of matching Realizations is formed. Next, the selection phase is initiated. Depicted selection consists of two steps. The first one represents a simple selection of applicable Realizations, based on input objects occurrences. The second one chooses the most suitable Realization according to input objects properties, scores, etc. Methods of multicriterial analysis or logical tools can be used during the selection phase. The important and expected situation will appear whenever one process corresponds to the two or more Realizations. The logic tools are responsible for solving this situation. But before this state, it is necessary to find the Realizations which are applicable to the reconfiguration of a given process. For this purpose, there are two ways to find them – selection based on the process or on the logic grounds. The combination of the process and logic approach in reconfiguration algorithm seems to be more effective due to the ability to choose the best Realization. Simple process approach is not able to select the Realization in dependence on inner set of properties owned by agents or Objects. On the other hand, the logic approach is not able to discard all Realizations which cannot be executed at the time of Process firing.
340
M. Radeck´ y, P. Gajdoˇs, and R. Fasuga
Pursuant to these ideas, it is able to define such procedure as an algorithm of reconfiguration process: 1. The Specification Phase - definition of all Realizations related to the Process that could be reconfigured. 2. The Selection Phase - checking of the applicable Realizations of a given Process and finding the most suitable one. (a) the selection of applicable Realizations - based on Input Objects occurrence (b) the finding the most suitable Realizations - based on Input Objects values and properties, Scores, etc. 3. The Execution Phase - chosen Realization firing.
4
Conclusion and Future Work
The extended UML diagrams (ABD) were used to model agents’ behaviors. The reconfiguration principles were developed and implemented in a new application called AgentStudio (Designer and Simulator). As case studies, we developed two applications “Car Parking System” and “Road Traffic Control System” [3,5] which are based on mentioned approach. The future work attention has to be paid to imperfect and vague information, its sharing and knowledge storing. Automatic code generation must be improved to reduce human work during MAS development. Mentioned modeling approach is not a complex methodology for MAS development, so it is not a full-value competitor to a huge approaches as Gaia, AUML, Prometheus, etc. The contribution of this modeling approach is focused on understandable and utilizable way to describe the agents behavior and to communication among the actors of MAS development process.
References 1. van der Aalst, W.M.P.: Verification of Workflow Nets. In: Azema, P., Balbo, G. (eds.) Application and Theory of Petri Nets 1997, pp. 407–426. Springer, Berlin (1997) 2. Kubik, A.: Intelligent Agents. Computer Press, Prague (publication in czech language) 3. Radecky, M., Gajdos, P.: Traffic Simulation and Intelligent agents. In: Sborn´ık IEEE: ICITST 2009, London, pp. 127–132. IEEE, Los Alamitos (2009) 4. Radecky, M., Gajdos, P.: Reconfigurable Intelligent agents. In: Sborn´ık UKSim 2008, pp. 543–548. IEEE, Cambridge (2008) 5. Radecky, M., Gajdos, P.: Intelligent agents for Traffic Simulation. In: Sbornik SpringSim ADS 2008, Ottawa, pp. 109–115 (2008), ISBN 1-56555-319-5 6. Radecky, M., Gajdos, P.: Process and Logic Approaches in the Inelligent agents Behavior. In: Duˇz´ı, M., Jaakkola, H., Kiyoki, Y., Kangassalo, H. (eds.) Sborn´ık Information Modelling and Knowledge Bases XVIII, pp. 295–300. IOS Press, Amsterdam, ISBN 978-1-58603-710-9 7. Vondrak, I.: Methods of Business Modeling. VSB-TUO, Ostrava (2004) (lecture notes in Czech)
Agent Behavior Diagram for Intelligent Agents
341
8. Matjaz, B.J.: Business Process Execution Language for Web Services BPEL and BPEL4WS, 2nd edn. Packt Publishing, Birmingham (2006) 9. Pilone, D., Pitman, N.: UML 2.0 in a Nutshell. O’Reilly Media, Sebastopol (2004) 10. Wooldridge, M., Jennings, J.R.: Intelligent agents - Theories, Architectures and Languages. Springer, Heidelberg (1995) 11. Namee, B.M.: A Proposal for an Agent Architecture for Proactive Persistent Non Player Characters (2001), http://www.cs.tcd.ie/publications/tech.reports/ reports.01/TCD-CS-2001-20.pdf 12. Zambonelli, F.: Developing Multi-Agent Systems: The Gaia Methodology, vol. 12(3). ACM, New York (July 2003) 13. Ferber, J.: Multi Agent Systems. In: An introduction to Distributed Artificial Intelligence. Addison-Wesley Professional, Reading (1993), ISBN 978-0201360486 14. Radecky, M., Gajdos, P.: Process and Logic Approaches in the Inelligent agents Behavior. In: Du, M., Jaakkola, H., Kiyoki, Y., Kangassalo, H. (eds.) Sbornk Information Modelling and Knowledge Bases XVIII, pp. 295–300. IOS Press, Amsterdam, ISBN 978-1-58603-710-9
Agent-Based Digital Networking in Furniture Manufacturing Enterprises Anthony Karageorgos1, Dimitra Avramouli1, Christos Tjortjis2,3, and Georgios Ntalos1 1
TEI of Larissa, Karditsa Branch, GR-43100 Karditsa, Greece 2 University of Ioannina, Ioannina, GR-45110, Greece 3 University of Western Macedonia, Kozani, GR- 50100, Greece {karageorgos,avramouli,gntalos}@teilar.gr,
[email protected]
Abstract. International competition and varying customer needs commonly cause small and medium furniture manufacturing enterprises to join dynamically-formed, ‘smart’ enterprise networks, established and operating using digital information technologies. In this paper, we propose a technological approach to support such enterprise networks which is primarily based on the use of software agents. First we outline the reasons motivating networking in furniture manufacturing enterprises and we briefly present core smart enterprise network concepts. Subsequently, we provide an overview of the main technologies currently used to support enterprise networks, and we make the case for utilising service-orientation and adaptive, (semi-) autonomous software components, such as software agents. Furthermore, we propose a four-tier software architectural framework based on software agents and web services, and we briefly describe the requirements, the architecture and main features of the e-Furn software system, which is based on that framework. Finally, we discuss the intelligent recommendation feature of e-Furn. Keywords: Smart Business Networks, Enterprise Networks, Software Agents, Multi-Agent Systems, Web Services, Furniture Manufacturing, Data Mining.
1 Introduction To cope with increased competition and dynamically varying customer needs Small and Medium Enterprises (SMEs) join dynamically formed collaborative networks. In such networks, participants can exploit the competencies offered by network partners to improve their efficiency and meet the stiff market demands. Such business networks have a number of characteristic features, the prominent one being their dynamic nature and flexibility in participation. For these reasons they are termed ‘smart’. In Smart Business Networks (SBNs) members act solely towards achieving their personal goals and maximizing their individual benefits. This contrasts other forms of enterprise networks and virtual organisations, where there is a different sense of membership and members aim to increase their individual benefit by acting towards the benefit of the whole organization. The dynamic nature of smart business networks makes the use of software agents mandatory in developing software to support their operation. Agents offer flexibility F. Zavoral et al. (Eds.): NDT 2010, Part II, CCIS 88, pp. 381–395, 2010. © Springer-Verlag Berlin Heidelberg 2010
382
A. Karageorgos et al.
and interoperability while they can provide both decentralised and inherently adaptive coordination and control. Furthermore, to better support the regularly changing business network competencies it is necessary to combine agent capabilities with serviceorientation in the design of the software architecture. In this paper, we present an agent-based approach to support ‘smart’ networking in furniture manufacturing SMEs. The motivation for ‘smart’ networking in furniture enterprises and a brief description of main SBN concepts are presented in Section 2. Section 3 provides an overview of digital technologies currently used to support enterprise networks and makes the case for using service-orientation and adaptive components, such as web services and software agents. Based on these arguments a four-tier software architectural framework is proposed in Section 4, and as an example of application of this framework an overview of the e-Furn system is given in Section 5. Finally, Section 6 concludes the paper.
2 Motivation and Background 2.1 Networking in Furniture Manufacturing SMEs The global financial crisis which has recently hit EU has forced many furniture manufacturing SMEs to reduce their product range and their production capacity attempting to reduce costs. In addition, increased competition and sophisticated customer demands has often led furniture manufacturers to specialisation in a small range of products aiming to maximise product quality. However, such an approach has certain drawbacks. Customers often prefer to purchase complete solutions and the lack of variety shown by specialising manufacturers propels them towards larger stores with higher product ranges. In other cases, knowledgeable customers have done extensive market search, using the internet for instance, and have sophisticated product requirements that small furniture manufacturers can not individually meet. To address such problems furniture manufacturing SMEs have traditionally tended to form relatively stable partnerships and alliances, for example small manufacturers commonly market both own and partner products showing this way a higher product range to customers [1, 2]. Such approaches have been sufficient until recently when customer demands were relatively stable and product ranges were more or less fixed or rarely changing. Today, however, this is not the case due to the aforementioned reasons. As a result, to tackle the above issues furniture manufacturing SMEs need to be able to form dynamic and flexible partnerships involving more partners and providing access to a wider range of customisable products. In this respect, the existing forms of business networks, such as clusters and static virtual enterprises are not sufficient. Another issue of major concern in furniture manufacturing SMEs is the efficient use of resources. To achieve high product quality and to cover a large number of customisation options, expensive equipment with high maintenance costs is needed, which is not fully used due to low production levels. Traditionally, an approach to mitigate this problem has been to carry out outsourced manufacturing tasks from selected partners at an agreed cost. Again, due to the relatively stable types of products, outsourced tasks were more or less known and suitable outsourcing partnerships
Agent-Based Digital Networking in Furniture Manufacturing Enterprises
383
were selected shortly after a new product was decided and were maintained during the most part of the product lifecycle. Today, however, this is also not possible. The increased product customisability makes outsourcing manufacturing tasks even harder. For example, a furniture manufacturing SME in South Europe specialising in wooden furniture will typically have equipment and outsourcing partnerships suitable for European markets. A customer, such as a hotel, may require sophisticated, e.g. baboo-type, furniture needing specialised processing not capable of being carried out in-house. In that case, the manufacturer would need to immediately know the best outsourcing options, even internationally, in order to produce the most competitive quote to the customer in the shortest possible time. This would not be possible with traditional methods. From the above arguments, it is evident that traditional forms of enterprise networking are not sufficient to meet current challenges faced by furniture manufacturing SMEs. We argue that the solution to this problem is to provide the technological means for such enterprises to rapidly join dynamically formed business networks and within them to form ‘smart’ collaborations acting rationally to promote their goals while benefiting from the overall network context and collaboration infrastructure. 2.2 Smart Business Networks An SBN is a collection of dynamically connected enterprises linked to each other and acting smarter than any individual business can [3]. SBNs are characterised as ‘smart’ because of the add-on value they provide to their members in terms of goods, products, services and experiences, as well as in terms of the possibilities individual members have to organise themselves and collaborate in innovative ways. The most important key characteristic of SBNs is their ability to demonstrate agile behaviour, for example by allowing their members to rapidly “pick, plug, and play” [4] business processes and reconfigure them to meet specific objectives, such as react to customer orders and cope with unexpected situations. The term “pick”, refers to the possibility for members to quickly connect to and disconnect from the network, while the term “plug” refers to the ability of members to select and globally execute business processes across the entire network. Finally, the term “play” refers to the ability of members to establish their own decision rules and business logic in the above mentioned business processes. A typical example of ‘smart’ add-on value gained in an SBN is the dynamic exploitation of market opportunities, such as identifying and filling unfilled market positions (termed ‘structural hole strategy’ in [5]). This outstanding agility of SBNs has only been enabled through the latest developments in information and communication technologies [6]. In particular, SBN ‘smartness’ does not only result from the dynamically formed and adaptively modifiable business models applied, but also from the sophisticated combinations of the state-of-the-art ICT technologies used [7]. A schematic representation of two SBNs is depicted in Figure 1. Each SBN has a node acting as coordinator which all other SBN members are connected on. An SME joins an SBN by registering with the respective coordinator node and subsequently it can access all other SBN members and establish contacts and collaborations as needed.
384
A. Karageorgos et al.
Fig. 1. A Smart Business Network
3 Supporting SBNs with Digital Information Technologies 3.1 Overview of SBN Support Technologies As mentioned in Section 2.2 ‘smartness’ in SBNs is largely a matter of utilising and appropriately combining advanced ICT methods. To this purpose, various technologies have been so far used to support operations of such networks. Examples are Semantic Web Models, Tools and Ontologies, Web Services (WS), Grid Computing, Sensors and Radio Frequency Identification Devices (RFIDs), and Software Agents. A survey of such technologies is summarised in Table 1. An example of using semantic web technologies for enabling business network operations is the work described in [8], which focuses on mechanisms for enabling rapid connectivity between network partners. The approach involves the use of OWL ontologies to build interfaces between partner systems, which expose their public functionality in the form of services. In that model, the logic connection between services is realised by associating services with pre-conditions and post-conditions which describe in detail, and according to the agreement of the business partners, the conditions that must be satisfied for particular services to be invoked to ensure interoperability between partner systems. However, that approach focuses only on predefined services and does not support dynamic service composition and configuration of partner collaborations, for example by means of negotiation. Once partners in a business network have “picked” and “plugged” the appropriate process modules together, these need to be executed. This has often been supported by using Web Services. For example in [10] an approach involving using Web Services and handling dynamic adaptations of business network behaviour with suitable WS orchestration is described. However, the disadvantage of using only WS is that high orchestration and coordination costs are involved (for example when searching for appropriate services, negotiating for price and quality of services and monitoring B2B transactions) and therefore we argue that a form of technological intelligence should be added to WS to better support operations of business networks.
Agent-Based Digital Networking in Furniture Manufacturing Enterprises
385
Table 1. Technologies used to support Smart Business Networks Technology Semantic Web Models, Tools & Ontologies Web Services
Radio Frequency Identification Devices (RFIDs)
Grid Computing
Software Agents
Approach Used for automatic and fast interoperability between many different systems. Used to integrate the computer applications of different participating firms and facilitates the connect and disconnect method, and can be used together with the other technologies. Used for reducing costs, improving service levels and offering new possibilities for identifying unique product instances.
References Xiao and Zheng [8] Werthner, Fodor and Herzog [9] Hillegersberg, Boeke, and Heuvel [10] Busquets, Rodona and Warehama [11]
Used for improving organisational agility to respond to rapidly changing requirements, for example to cope with disasters. Used for supporting organisational decision-makers in making multi-attribute decisions in environments that are characterised by a high velocity of change.
Oosterhout, Koenen and Heck [15] Boden [16] Chen et. al [17]
Rodon, Busquets, and Christiaanse [12] Pramatari and Doukidis [13] Pramatari, Doukidis and Kourouthanassis [14]
Collins, Ketter and Gini [18] Douma et. al [19] Ketter et. Al [20]
In [12] an approach for tracing a company’s products based on the use of RFID technology is described. The approach involves a specialised business operating system which is responsible for coordinating the process among nodes on a business network. Products are tagged with RFIDs and there is both a global business knowledge store, as well as a number of industry wide local repositories which are shared via intranet and extranet connections. However, that approach lacks flexibility, for example it considers statically predefined products. Oosterhout et al in [15] use grid technology and demonstrate how it can improve organisational agility to be able to respond to rapidly changing circumstances. In that paper, the authors describe a business experiment involving development of an application solution for backup and recovery of enterprise data. That solution is based on sharing data storage hardware by users in a grid. This approach however, does not provide full-scale support for SBN operations. Collins et al in [18] show how intelligent agents can support organisational decision-makers in making multi-attribute decisions in highly dynamic environments. They present an architecture that offers innovative capabilities for automatically connecting, disconnecting and communicating with the appropriate actors in a business network. They offer a technological solution for companies to create the highly
386
A. Karageorgos et al.
needed quick-connect capabilities allowing companies to change its position in the network more swiftly. However, that approach does not use standardised technologies, such as WS. In summary, semantic web approaches solve the interoperability problem, but they currently suffer from lack of universally applicable standardised technologies, as well as from effective support for implementing flexible and adaptive behaviour. Standardisation and industrial strength technologies are ensured by using Web Services, RFIDs and Grid technologies. However, these technologies suffer from interoperability and flexibility problems. Finally, adaptivity and flexibility is addressed by using software agents. However, agents too currently suffer from lack of broadly accepted, industrial strength technologies, for advertising and executing their services. Therefore, we argue that a combination of agent and WS technologies would be required to support ‘smart’ business networking operations. 3.2 Service-Orientation and Flexible, Adaptive Software Components As described in the previous Section there are different technological approaches that can be followed to develop support for SBN operations. We advocate the use of the Service-Oriented Architecture (SOA) approach. SOA can be seen as an application architecture in which all functions are seen as services [21]. Services are capable of being remotely invoked by external users and by other services and they encapsulate application logic with a uniformly defined interface and are commonly made publicly available via discovery mechanisms [22]. The SOA paradigm has many advantages, for example it enables on demand linkage of users and computational resources. SOA is essential for delivering business agility and IT flexibility. A well-executed SOA implementation can bridge the gap between enterprise architecture and business strategy, enabling companies to achieve closer alignment of IT and business, and robust reuse of existing applications with agility and cost effectiveness [23]. However, SOAs do not provide any support for rational (semi-)automated selections when it comes to the creation of virtual organizations and enterprise networks. Such rational selection is crucial for establishing and operating viable business formations. This issue can be addressed by enriching SOA with software components with reasoning abilities or “intelligence”. Software agents are particularly suitable for this task since they provide inherently adaptivity and flexible behaviour, both individual and collective in the form of Multi-Agent Systems (MAS). The benefits of combining SOA and agents are therefore increased flexibility and adaptability of enterprise network processes to suit varying individual organisational needs. However, still much research on the business and technical aspects of the combination of SOA and such components to support SBN operations is needed. 3.3 Software Agents and Web Services SOAs are commonly, but not necessarily, implemented as web services leading to the issue of combining agents and web services [24]. Therefore, a main effort in the integration of agents and web services concentrates on masking services for redirection, aggregation, integration and administration purposes [25]. Although the evolution of MAS and web services has been completely different, both technologies have pursued
Agent-Based Digital Networking in Furniture Manufacturing Enterprises
387
common goals such as providing dynamic, open and oriented architectures. In order to solve their differences and to give interoperation and integration possibilities, various approaches have evolved, such as WSIG [25], WD2JADE [26] and ESWA [27]. These efforts, as pointed out in [28], can be classified in three categories. Firstly, WS can provide the most basic level functionality while agents can supply higher-level functions by using, combining and choreographing WS, so achieving added-value functions [26]. Alternatively, communication in WS and agents may become equivalent, so that there is no distinction between them (‘agents in web service wrappers’) [27]. Finally, both concepts can remain separate creating a heterogeneous service space and interoperating through gateways and translation processes [25]. Most of the current agent works strongly related with Web services do not take into account regulation aspects and they are mainly focused on heterogeneity problems in MAS systems. With this aim, they lean on an explicit description of the offered services, an approach which lacks expressivity and cannot serve as a basis for intelligent service orchestration and coordination. Therefore, it is necessary to employ expressive semantic languages, such as OWL for agent domain ontologies, and, as was originally suggested by Hendler [29], OWL-S for WS semantic annotation. In this way, new complex services will be able to be formed semi-automatically by agents and users.
4 A Four-Tier Software Architectural Framework A commonly accepted view in software architecture research is that according to the principle of separation of concerns, software agents and web services must lie on different layers of abstraction due to the conceptual differences between them [30]. From a system designer’s point of view, web services can be used to model passive software components that exhibit reactive, deterministic behaviour. On the other hand, proactive and autonomous behaviours are more suitably modelled by software agents. Agents have inherent flexibility and can represent stochastic, intelligent behaviours at various levels of autonomy. Application functionality, such as workflow process tasks, can be materialised both by agents and web services depending on the particular context. Finally, lower level software components encapsulating internal business logic, such as legacy systems and databases, can be accessed both by web services and agents according to the application requirements. Therefore, we propose that software architectures aiming to support smart business networks should be lying on four layers (see Fig. 2). The lower layer, namely, the Business Logic Layer provides for the most specific operations. It comprises the internal business processes within companies. It usually consists of conventional ERP system components. Upon this layer, Web Services are deployed exposing parts of the internal business processes and making them publicly available. These services along with the semantic description of their capabilities lie on the second layer, namely the Web Services Layer. Adding semantic annotations to web service capabilities can help software entities, such as software agents, to (semi-)automatically interact with them in a dynamic way. Agents interact with, and take advantage of basic services and they are located at the Agent Layer. Agents make use of the semantic annotation of services capabilities
388
A. Karageorgos et al.
Fig. 2. Four-tier Architectural Framework based on Agents and Web Services
to automatically discover, compose, invoke and monitor web services. They are also able to dynamically exhibit and propagate the changing functionality provided in lower layers. Finally, the User interface Layer is responsible for interacting with users and organising (for example configuring and guiding) agents to execute networked business processes. In this way, depending on the agents available in the system and the way they interoperate, different user-tailored ‘smart’ networked applications can be produced.
5 The E-Furn System As an example of a system following the software framework introduced in Section 4 we present a high-level view of the e-Furn system. e-Furn aims at supporting smart networking of furniture manufacturing enterprises [31]. The approach followed in the development of e-Furn is to use as standardised mature technologies where possible, and combine and extend these technologies to address the furniture enterprise SBN domain requirements. To this purpose, an approach combining agent-technology and service-orientation has been selected. The e-Furn system (see Figure 3) has been designed following the principle of separation of concerns, considering four layers: the Business logic layer comprising legacy systems and other information resources, the WS and the agent layers corresponding to WS and agents respectively, and the user interface layer where the capabilities of all other three layers are combined to produce ‘smart’ business networking functionality. The system is viewed a grid of distributed interconnecting partner nodes that are all linked with each other. One of the nodes is considered the main e-Furn
Agent-Based Digital Networking in Furniture Manufacturing Enterprises
389
Fig. 3. Overview of e-Furn System Architecture
node and acts as coordinator of the other nodes, for example for intermediating to establish communication for new partner nodes joining the network, and for resolving conflicts that may arise. To establish communication, new partner nodes get in contact with the main e-Furn node and after necessary authorisations they obtain access to the partner details, such as addresses and available services. The e-Furn is considered to be an open system based on software agents in the sense described in [32, 33]. 5.1 SBN Support System Requirements Based on the needs for ‘smart’ networking furniture industry SMEs we identify a number of high-level requirements for the e-Furn system: RQ1: The system should be able to support new enterprise member registration and authorisation procedures which should be able to be carried out dynamically and on run-time. e-Furn end-users will be employees of registered e-Furn member enterprises, such as salesmen for instance, and not end customers. RQ2: For each e-Furn member enterprise, employees with necessary privileges should be able to locate and select other appropriate e-Furn member enterprises and designate them as collaborators by placing them in groups created for this purpose. RQ3: e-Furn member enterprises should be able to publish their products and services they wish to offer for reselling or outsourcing respectively. In particular, they should be able to specify general as well as specific parameters for product offer and service provision. RQ4: e-Furn end-users should be able to receive technological assistance in their interactions with other users within the e-Furn network. In particular, repeated or
390
A. Karageorgos et al.
standardised interactions should be able to be carried out (semi-)automatically requiring only final confirmation from the user. For example, the price of products offered by other network member enterprises should be possible to be finalised via semiautomated negotiation. Users should be assisted in carrying out such negotiations in short time and for a large number of products. RQ5: Since the number of options and combinations will generally be large, endusers should be able to receive intelligent recommendation assistance for preparing the best offers for the customers and for selecting the best outsourcing options. The system should be able to estimate the combinations that are more likely to increase customer satisfaction and maximise the sellers profit and provide a list of options to the user who will finally select the best one based on her experience. RQ6: e-Furn users are expected to have different needs and preferences which will normally be changing based on the form and type of collaboration. System interfaces should be able to adapt to user needs both statically based on user configuration, and dynamically based on collaboration and usage results. For example, if a user tends to prefer certain products of a certain type then these products should be able to be conveniently accessible by that particular user. RQ7: Users should be able to monitor the status of their product orders, product delivery and execution of their outsourced tasks. It must be noted that furniture product particularities should be taken into account. For example, furniture products have specific packing and storing requirements, for instance they require much more storage volume than their actual mass. RQ8: Users should be able to expose only part of their local information as and when needed. Any information exchanged should be revealed only to the intended recipient. 5.2 Main e-Furn Features The main architectural elements of the e-Furn system are software agents that act as mediators between system components. Each external actor to the system, for example service providers, service users and system administrators, is associated with a software agent acting on her behalf, interconnecting the actor with the rest of the system and providing assistance. Agent behaviour is modelled using roles, as suggested in [34] and [35]. Agents make use of various (external or internal) data repositories, (stored in the form of ontologies) containing the knowledge that is to carry out the system operations and based on input from users they adaptively orchestrate system functionality which is provided in the form of web services. Adaptation and overall behaviour is further determined with global as well as individual for each partner business rules. All global network information is stored in the main e-Furn repository. Among the main features of e-Furn are polymorphic user interfaces that adapt dynamically to user preferences and to system operation results. Furthermore, there are sophisticated decision making tools embedded in the system assisting users in operational decisions such as partner lookup. Another important feature of e-Furn is support for outsourcing tasks to partners and it provides advanced optimisation and task allocation tools that are manipulated by software agents and can be invoked by users to facilitate outsourcing of tasks with minimal costs. This is accompanied with
Agent-Based Digital Networking in Furniture Manufacturing Enterprises
391
Fig. 4. Intelligent Recommendation Process in e-Furn
effective monitoring and control mechanisms allowing examination of the execution stage of outsourced tasks. Finally, e-Furn provides intelligent recommendation assistance through specialized recommendation algorithms, which is further described in Section 5.3. 5.3 Intelligent Recommendation Subsystem E-Furn provides users with intelligent recommendation assistance, based on advanced recommendation algorithms that take into account furniture features, patterns and customer profiles to formulate and propose bundles of furniture and services. These are cross-referenced with a database of current network capabilities to produce a set of outsourcing tasks, as depicted in Figure 4 and detailed in the following paragraphs. E-Furn comprises and maintains a database of features concerning furniture, not only in a standalone fashion (such as colour, price, dimension, weight, style, material, utility etc.), but also with regards to other furniture or domestic appliances in the broad sense. For instance, possible combinations can be considered (for example a set of chairs and a dinner table, kitchen furniture, and electrical appliances such as oven, fridge and dishwasher). These feature combinations can include matching schemes in terms of style, colour, utility and spatial collocation. The system uses innovative intelligent information processing methods, including association rule mining from sales data stored in the customer database and furniture features to extract sales and configuration patterns [36-38]. For instance, the system can identify items that sell together, such as sofas and TV tables. It subsequently estimates the best selling price for this bundle, considering numerous additional parameters, such as customer details, customer sales history and profit expectations. An important feature of our approach is the customer profile repository. This is initially populated using empirical data and information provided by experts, in terms of furniture arrangements suitable for a variety of business and domestic purposes, settings, budgets and so on. It is kept up-to-date and enriched using actual customer data, where customers can opt in a “loyalty scheme” in return for providing demographic and other information, such as individual preferences and requirements. All these data are mined in order to construct useful profiles. Initially we cluster customer related data in order to formulate clusters (i.e. groups) of customers [39]. These clusters indicate similarity across a number of dimensions including demographic,
392
A. Karageorgos et al.
marketing, even subjective factors. These clusters can then be processed by intelligent agents in order to formally determine classes of customers which in turn can be used for customer classification [40, 41] and customer profile formation [42, 43]. Finally, e-Furn maintains a log of products and services, keeping tags on their availability within the network and elsewhere in real-time, using appropriate services/agents. Customer profiles, furniture features and patterns, along with availability information are fed into the recommendation engine, which is the core of the system. This engine matches potential customer requirements with provider’s capabilities, in order to determine bundles of products and services. Priority is given to bundles involving existing network capabilities, but outsourcing is not excluded if necessary. In that case a list of outsourcing tasks is generated and relevant reservations are placed.
6 Concluding Remarks As argued in Section 2, furniture manufacturing SMEs need to resort to enterprise networking to respond to contemporary global economic challenges. In this respect, traditional forms of business networking are not sufficient, given the current market state, the varying and sophisticated nature of customer requirements and the international competition. Therefore, we argued that furniture manufacturing SMEs need to join and operate flexible and adaptive, in other words ‘smart’, business networks, which in turn are highly relying on the efficient use of state-of-the-art ICT technologies to fully exploit their potential. Existing ICT methods currently used for supporting business network operations tend to be applied in isolation and therefore suffer from certain drawbacks, such as lack of adaptivity and flexibility. We argued on combined use of ICT methods and in particular on jointly using software agents and web services, and we described our perspective in the form of a four-tier architectural software framework. As an example of a system based on the proposed framework, we provided a highlevel view of e-Furn, a system aiming to assist furniture manufacturing SMEs in participating in ‘smart’ business networks. E-Furn is based on combined use of agents and semantic web services and its main futures include providing intelligent assistance and adaptive interfaces to users. However, there are many issues relevant to providing robust and effective technological support for SBN operations in general, and furniture manufacturing SBNs in particular, that are still open. In the near future we plan to further elaborate on issues concerning provision of intelligence assistance to furniture manufacturing SBN members, such as product bundling recommendations and task outsourcing optimisation.
References 1. Databank: ICT and e-Business Impact in the Furniture Industry. Impact Study No 3/2008 (2008) 2. Camarinha-Matos, L.M.: Collaborative Networks In Industry Trends and Foundations. In: Cunha, P.F., Maropoulos, P.G. (eds.) Digital Enterprise Technology, pp. 45–56. Springer, Heidelberg (2007)
Agent-Based Digital Networking in Furniture Manufacturing Enterprises
393
3. van Heck, E., Vervest, P.: Smart business networks: how the network wins. Communications of the ACM 50, 28–37 (2007) 4. van Heck, E., Vervest, P.: Smart business networks: Concepts and empirical evidence Decision Support Systems 47, 275–276 (2009) 5. Vervest, P.H.M., van Liere, D.W., Dunn, A.: The Network Factor - How to Remain Competitive. In: Vervest, P.H.M., van Liere, D.W., Zheng, L. (eds.) The Network Experience, pp. 15–35. Springer, Heidelberg (2009) 6. Vervest, P.H.M., van Heck, E., Pau, L.F., Preiss, K.: Smart Business Networks. Springer, Heidelberg (2005) 7. Vervest, P.H.M., van Heck, E., Preiss, K.: Smart Business Networks: A New Business Paradigm. In: SBNi Discovery Session, p. 529 8. Xiao, L., Zheng, L.: Achieving Quick Connect with the Support of Semantic Web. In: SBNi Discovery Session 2006. Vanenburg Castle in Putten, The Netherlands (2006) 9. Werthner, H., Fodor, O., Herzog, M.: Web Information Extraction and Mediation as a Basis for Smart Business Networking. In: Vervest, P., van Heck, E., Pau, L.-F., Preiss, K. (eds.) Smart Business Networks, pp. 405–419. Springer, Heidelberg (2005) 10. van Hillegersberg, J., Boeke, R., van de Heuvel, W.-J.: The Potential of Webservices to Enable Smart Business Networks. In: van Peter Vervest, E.H., Pau, L.-F., Preiss, K. (eds.) Smart Business Networks, vol. 4, pp. 349–362. Springer, Heidelberg (2005) 11. Busquets, J., Rodona, J., Warehama, J.: Adaptability in smart business networks: An exploratory case in the insurance industry Smart Business Networks. Concepts and Empirical Evidence 47, 287–296 (2009) 12. Rodon, J., Busquets, X., Christiaanse, E.: Orchestration in ICT-enabled Business Networks: A Case in the Repairs Industry. In: 18th Bled eConference eIntegration in Action. Bled, Slovenia (2005) 13. Pramatari, K., Doukidis, G.: Intelligent Integration of Supply Chain Processes based on Unique Product Identification and a Distributed Network Architecture. In: SBNi Discovery Session, p. 369 14. Pramatari, K., Doukidis, G.I., Kourouthanassis, P.: Towards Smarter Supply and Demand Chain Collaboration Practices Enabled by RFID Technology. In: Vervest, P.H.M., van Heck, E., Pau, L.-F., Preiss, K. (eds.) Smart Business Networks, vol. Section 2, pp. 197– 210. Springer, Heidelberg (2005) 15. van Oosterhout, M., Koenen, E., van Heck, E.: Empirical Evidence from a Business Experiment with Small and Medium Enterprises in the Netherlands The Adoption of Grid Technology and Its Perceived Impact on Agility. In: Vervest, P.H.M., Liere, D.W., Zheng, L. (eds.) The Network Experience, pp. 285–299 (2009) 16. Boden, T.: The Grid Enterprise — Structuring the Agile Business of the Future. BT Technology Journal 22, 107–117 (2004) 17. Chen, X., Duan, G., Sun, Y., Gu, J.: Research on Key Technologies for Grid-Based Network Collaborative Design. In: Fourth International Conference on Networked Computing and Advanced Information Management, pp. 639–644. IEEE, Los Alamitos (2008) 18. Collins, J., Ketter, W., Gini, M.: Flexible Decision Support in a DynamicBusiness Network. In: The Network Experience, Part 4, pp. 233–248. Springer, Heidelberg (2009) 19. Douma, A., Moonen, H., van Hillegersberg, J., van de Rakt, B., Schutten, M.: Designing an Agent-Based Inter-Organizational Coordination System for Planning and Control of Container Barges in the Port of Rotterdam. In: SBNi Discovery Session 2006. Vanenburg Castle in Putten, The Netherlands (2006)
394
A. Karageorgos et al.
20. Ketter, W., Collins, J., Gini, M., Gupta, A., Schrater, A.P.: Strategic Sales Management Guided By Economic Regimes. In: Smart Business Networks A new Business Paradigm (2008) 21. McAfee, A.: Will Web Services Really Transform Collaboration? MIT Sloan Management Review 46, 78–84 (2005) 22. Schroth, C., Janner, T.: Web 2.0 and SOA: Converging Concepts Enabling the Internet of Services 9, 36–41 (2007) 23. Laurent, W.: The Importance of SOA Governance. DM Review 17, 38–38 (2007) 24. Dominic, G., Margaret, L., Ashok, M., Hiroki, S.: The IEEE FIPA approach to integrating software agents and web services. In: Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems. ACM, Honolulu (2007) 25. Greenwood, D., Calisti, M.: Engineering web service-agent integration. In: Proceedings of the International Conference on Systems, Man and Cybernetics (SMC 2004), The Hague, The Netherlands, pp. 1918–1925 (2004) 26. Nguyen, X., Kowalczyk, R., Chhetri, M., Grant, A.: WS2JADE: A Tool for Run-time Deployment and Control of Web Services as JADE Agent Services. In: Software AgentBased Applications, Platforms and Development Kits, pp. 223–251 (2005) 27. Ramírez, E., Brena, R.: Integrating agent technologies into enterprice systems Using Web Services. Enterprise Information Systems VII, 223–227 (2006) 28. Blacoe, I., Portabella, D.: Guidelines for the integration of agent-based services and webbased services (2005) 29. Hendler, J.: Agents and the Semantic Web. IEEE Intelligent Systems 16, 30–37 (2001) 30. García-Sánchez, F., Alvarez Sabucedo, L., Martínez-Béjar, R., Anido Rifón, L., ValenciaGarcía, R., Gómez, J.: A Knowledge Technologies-Based Multi-agent System for eGovernment Environments. In: Service-Oriented Computing: Agents, Semantics and Engineering, pp. 15–30 (2008) 31. Karageorgos, A., Avramouli, D., Ntalos, G., Tjortjis, C., Vasilopoulou, K.: Towards Agent-based ‘Smart’ Collaboration in Enterprise Networks. In: 8th Int’l Workshop on Agent-based Computing for Enterprise Collaboration (ACEC) at WETICE 2010, Larissa, Greece. IEEE Computer Society Press, Los Alamitos (2010) 32. Carrascosa, C., Giret, A., Julian, V., Rebollo, M., Argente, E., Botti, V.: Service Oriented MAS: An open architecture. In: Proc. of 8th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1291–1292. IEEE Press, Los Alamitos (2009) 33. Giret, A., Julian, V., Rebollo, M., Argente, E., Carrascosa, C., Botti, V.: An Open Architecture for Service-Oriented Virtual Organizations. In: Seventh International Workshopon Programming Multi-Agent Systems, PROMAS 2009, pp. 23–33. Springer, Budapest (2009) 34. Karageorgos, A., Mehandjiev, N., Thompson, S.: RAMASD: a semi-automatic method for designing agent organisations. The Knowledge Engineering Review 17, 331–358 (2002) 35. Stuit, M., Szirbik, N.B.: Towards Agent-Based Modeling and Verification of Collaborative Business Processes: An Approach Centered on Interactions and Behaviors. International Journal of Cooperative Information Systems 18, 423–479 (2009) 36. Dong, L., Tjortjis, C.: Experiences of Using a Quantitative Approach for Mining Association Rules. In: Liu, J., Cheung, Y.-m., Yin, H. (eds.) IDEAL 2003. LNCS, vol. 2690, pp. 693–700. Springer, Heidelberg (2003) 37. Han, J., Kamber, M., Pei, J.: Data Mining: Concepts and Techniques, 2nd edn., November 3, 2005. Morgan Kaufmann, San Fransisco (2006)
Agent-Based Digital Networking in Furniture Manufacturing Enterprises
395
38. Wang, C., Tjortjis, C.: PRICES: An Efficient Algorithm for Mining Association Rules. In: Yang, Z.R., Yin, H., Everson, R.M. (eds.) IDEAL 2004. LNCS, vol. 3177, pp. 352–358. Springer, Heidelberg (2004) 39. Witten, I.H., Frank, E.: Data Mining: Practical Machine Learning Tools and Techniques, 2nd edn. Morgan Kaufmann, San Francisco (2005) 40. Rokach, L., Maimon, O.: Top-down induction of decision trees classifiers - a survey. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews 35, 476–487 (2005) 41. Tjortjis, C., Keane, J.: T3: A Classification Algorithm for Data Mining. In: Yin, H., Allinson, N.M., Freeman, R., Keane, J.A., Hubbard, S. (eds.) IDEAL 2002. LNCS, vol. 2412, pp. 50–55. Springer, Heidelberg (2002) 42. Cumb, C., Fano, A., Ghani, R., Krema, M.: Predicting customer shopping lists from pointof-sale purchase data. In: Proc. of the 10th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining, Seattle, WA, USA, August 22-25 (2004) 43. Adomavicius, G., Tuzhilin, A.: Using Data Mining Methods to Build Customer Profiles. Computer 34(2), 74–82 (2001)
An Approach towards Time Synchronization Based Secure Protocol for Wireless Sensor Network Arun Kumar Tripathi and Ajay Agarwal Department of Computer Application, Krishna Institute of Engineering and Technology, Ghaziabad
[email protected],
[email protected]
Abstract. Wireless sensor networks (WSN) have received a lot of attention recently due to their wide applications such as target tracking, environment monitoring, and scientific exploration in dangerous environments. Time synchronization is an important component of sensor networks to provide a common clock time in sensor nodes. Time synchronization protocols provide a mechanism for synchronizing the local clocks of the nodes in a sensor network. Some of the sensor nodes may be malicious, which can disrupt the normal operation of a sensor network. In this paper, we find out malicious nodes and propose time synchronization based secure protocol for a group of non-malicious nodes. Keywords: Sensor Networks, Security, Time Synchronization, Malicious nodes.
1 Introduction Wireless Sensor Network (WSN) consists of hundreds or thousands of micro sensor nodes that are joining together to form a network. Wireless sensor network [1] accurately monitors remote environment intelligently by combing the data from individual nodes. The special nature of wireless sensor network imposes challenging requirements on secure time synchronization design. All the attacks on time synchronization protocols have one main goal, to somehow convince some nodes that their neighbor’s clocks are at a different time [2] than they actually are. There exist two types of attacks [3]: (i) external and (ii) internal. External attacks are those in which an (external) attacker manipulates the communication between pairs of trusted nodes and causes the nodes to desynchronize, or to remain unsynchronized even after a successful run of the synchronization protocol. Pulse delay attack is an example of external attack. Internal attacks are those in which internal attackers (group members) report false clock references to their neighboring nodes. The rest of the paper is organized as follows: In Section 2 we survey the existing time synchronization protocols [18]. An approach for the proposed protocol is given in Section 3. In support of the approach related theorems and their proofs are also shown. Concluding remarks and future work are made in Section 4 and 5 respectively. F. Zavoral et al. (Eds.): NDT 2010, Part II, CCIS 88, pp. 321–332, 2010. © Springer-Verlag Berlin Heidelberg 2010
322
A.K. Tripathi and A. Agarwal
2 Related Work Researchers have proposed many protocols for time synchronization [15] based on classification receiver-receiver [4,5] and sender-receiver [4,6]. For discussion we have considered reference broadcast synchronization (RBS) [7] protocol and time synchronization protocol for sensor network (TPSN) [8] as receiver-receiver based protocols. On the other hand, secure pair-wise synchronization (SPS) [9] protocol is considered as sender-receiver based protocol. In receiver-receiver based synchronization, sender sends message to more than one receiver and then exchange of messages take place between receivers to synchronize each other and compute their offsets based on the difference in reception time. Sender does not take part in the synchronization. On the other hand, in sender-receiver based synchronization [5] protocol, the sender node periodically sends a message with its local time as a timestamp to the receiver. The receiver then synchronizes with the sender using the timestamp it receives from the sender. The message delay [6] between the sender and receiver is calculated by measuring the total round-trip time, from the time a receiver requests a timestamp until the time it actually receives a response. 2.1 Receiver-Receiver Protocols Reference Broadcast Synchronization (RBS) protocol [7] is based on receiverreceiver synchronization which reduces some uncertainty of packet delays. RBS does not need to consider about sender’s nondeterministic packet delays: send time and access time. To remove sender’s nondeterministic packet delays, RBS provides high precision of time synchronization.
Fig. 1. Time-critical path for traditional protocols (left) and RBS protocol (right)
Fig. 1 shows traditional protocol with RBS. In RBS a reference message is broadcast to two or more receivers and then receivers try to synchronize their respective local clocks. Each receiver records its local time when it gets the reference message. Then receivers exchange their local times [10]. Another receiver-receiver based protocol is TPSN [8] which initially creates a spanning tree of the sensor network. The tree starts at the root of the network, which is generally a base station, and each node establishes its level based on the 'level discovery' message that it receives. While the tree is being built, the nodes perform pair-wise
An Approach towards Time Synchronization Based Secure Protocol for WSN
323
synchronization along the edges of the tree. Each node exchanges synchronization messages with its parent in the spanning tree. By comparing the reception time of the packets with the time of transmission, which is placed on the packet by the parent, the node can find and correct for its own phase offset. 2.2 Sender-Receiver Synchronization In sender-receiver approach all receivers should be synchronize with sender. Senderreceiver approach basically includes three steps. i. ii. iii.
The sender node periodically sends a message with its local time as a timestamp to the receiver. The receiver then synchronizes with the sender using the timestamp it receives from the sender. The message delay between the sender and receiver is calculated by measuring the total round-trip time from the time a receiver requests a timestamp until the time it actually receives a response. Table 1. Pseudo code for sender-receiver synchronization
Sender-receiver Synchronization 1. A(T1) —›(T2) B : A, B, sync /* At Time T1 node A sends a synchronization packet which is received by node B at time T2. Packet contains synchronization message time stamp along with node-id of node A and B. */ 2. B(T3) —›(T4) A : B, A, T2, T3, ack /* In response to synchronization packet at time T3 node B sends response packet which is received by node A at time T4. The response packet contains node-id of nodes A and B along with receiving time of synchronization packet T2, sending time of response packet T3 and acknowledgement. */ 3. A calculates offset between the nodes A and B. The pseudo code used in sender-receiver synchronization [9] is given in Table 1. Here, T1, T4 represent the time measured by the local clock of node A. Similarly T2, T3 represent the time measured at node B. At time T1, A sends a synchronization pulse packet to B. Node B receives this packet at T2, where T2 =T1+d+δ. Here, δ and d represent the offset between the two nodes and end-to-end delay respectively. At time T3, B sends back an acknowledgement packet. This packet contains the values of T2 and T3. Node A receives the packet at T4. Similarly, T4 is related to T3 as T4 = T3+d-δ. Node A can calculate the clock offset [9] and the end-to-end delay [9] as: Offset (δ) = ((T2 – T1) – (T4 – T3))/2
(1)
Delay (d) = ((T2 – T1) + (T4 – T3))/2
(2)
324
A.K. Tripathi and A. Agarwal
Sender-receiver synchronization suffers from pulse delay attack. The pulse-delay attack [11], [20] is performed by jamming the initial pulse, storing it in memory and then replaying it later at an arbitrary time. Fig. 2 shows the idea behind pulse-delay attack.
Fig. 2. Pulse delay attack
Without any pulse delay [12] attack the T2= T1+δ+d and T4 = T3-δ+d. If an attacker performs pulse-delay attack (e.g., on the initial sync packet), the equations will change to: T2* = T1+δ+d+Δ and T4*= T3-δ+d+Δ. Here Δ is the pulse-delay introduced by the attacker [3]. In presence of pulse delay clock offset and the end-to-end delay will be Offset (δ) = ((T2 – T1) – (T4 – T3) + Δ)/2
(3)
Delay (d) = ((T2 – T1) + (T4 – T3) + Δ)/2
(4)
Secure pair-wise synchronization (SPS) is a sender-receiver based approach. In Sender-receiver synchronization approach security mechanism is integrated to make it resilient to adversarial attacks from external attackers [19]. In this protocol, message integrity and authenticity [17] are ensured through the use of Message Authentication Codes (MAC) and a key KAB [13,14,16] shared between A and B. This prevents external attackers from modifying any values in the synchronization pulse or in the acknowledgement packet. Furthermore, the attacker cannot assume an identity of node B as it does not hold the secret key KAB. An attacker can hear the packet over the wireless channel and can use the MAC in future to generate authenticated packets. Using a random nonce, NA, during the handshake safeguards the protocol against such replay attacks. In SPS, pulse delay attacks are detected through a comparison of the computed message end-to-end delay, d, with the maximal expected message delay d*. Note that the calculation of the end-to-end delay, d. If the computed delay is greater than the maximal expected delay, we recognize that there is replay on packet. The pseudo code for secure pair-wise synchronization protocol is given in Table 2.
An Approach towards Time Synchronization Based Secure Protocol for WSN
325
Table 2. Pseudo code for secure pair-wise synchronization
Secure Pair-wise Synchronization (SPS) 1. A (T1) —>(T2) B : A, B, NA, sync /* At Time T1 node A sends a synchronization packet which is received by node B at time T2. Packet contains synchronization message time stamp, nonce NA (pseudo-random number issued in an authentication protocol to ensure that old communications cannot be reused in replay attacks) along with node-id of node A and B. */ 2. B(T3) —>(T4)A : B, A, NA, T2, T3, ack, MAC {KAB}[ B, A, NA,T2, T3, ack] /* In response to synchronization packet at time T3 node B sends response packet which is received by node A at time T4. The response packet contains node-id of nodes A and B, nonce NA, receiving time of synchronization packet T2, sending time of response packet T3 and acknowledgement along with all above contains encrypted by shared key KAB and then protected by MAC. */ 3. Node A calculates end-to-end delay d = {(T2 – T1) + (T4 – T3)}/2 if d ≤ d* then δ= {(T2 – T1) - (T4 – T3)}/2, else abort
3 Proposed Protocol We have proposed an approach to develop a protocol. The protocol not only finds malicious node(s) but also counts them within the group. Further, it synchronizes all non-malicious nodes to a common clock i.e. fastest clock in the group. Let us assume that group membership is known to all group nodes in the group and all group nodes reside in each other’s power ranges. Let us consider Gs is a sender node which is a non- malicious and not considered in a group. The sending time of the packet at node Gs is represented by Ts (time measured by node Gs) and receiving time of packet by node Gj is Tj (already sent by node Gs). These times are measured by two different clocks. Ts is measured in the local clock of node Gs (i.e. Cs) whereas Tj is measured by the local clock of node Gj (i.e. Cj). The offset (or the difference between the local clocks) between the two nodes is represented by δsj (calculated by node Gj with respect to node Gs). The delay for the packet transfer from Gs to Gj is represented by dsj. In proposed protocol we have assumed that a node is said to be malicious, if it does not report the exact time at which it receives or sends the packet. Herein, we assume that malicious node [14] does not report the exact time at which it receives the packet.
326
A.K. Tripathi and A. Agarwal
3.1 Steps of Proposed Protocol The proposed protocol has following five steps: Step 1: Node Gs sends packets containing its node identifier (ID) and challenge nonce (Ns) to all group members. If there are N nodes in the group then in the first step the number of messages transmitted is N. In proposed protocol the initiator node is taken as sender node. Step 2: In this step of the protocol, every node Gj, which have received the challenge packet acknowledges back to sender node Gs, known as response packet. This packet contains triples {Tj, Ns, Gs}, where Tj is the receipt time of the challenge packet from node Gi, Ns is nonce by sender and Gs is node-id of sender respectively. It also contains Message Authentication Code (MAC), which enables Gs to authenticate the packet sent by Gj in this step. The response packet also includes the sending time (T′j) from node Gj. MAC is used to provide resiliency against external attacker. So in this step N MACs are calculated one for each Gs and Gj pair and then each Gj sends messages to Gs. A pair wise secret key (Ksj) which is shared between nodes Gs and Gj is also used in the response messages. Step 3: Now node Gs calculates the delay occurred (dsj), corresponding to challengeresponse and if all the calculated delays for each node are less than a maximal delay (d*) then node Gs calculates the offset for each node Gj. If any node’s calculated delay is more than maximal delay then Gs assumes that Gj is external attacker. Step 4: Node Gs will calculate for every other node, Gj, in the group Ssj (Ssj is sent time of packet from node Gs to Gj) and Rjs (Rjs is received time of packet from node Gj to Gs). If Gj is malicious then Ssj should not be equal to Rjs. This step also calculates number of internal attackers. Step 5: Sender forms a circular path, P, of all remaining non-malicious nodes and calculate sum of all offsets along the path P. If this sum is zero, it synchronizes every node of the path P to the fastest clock. The pseudo code for proposed protocol is given in the Table 3. Table 3. Pseudo code for proposed protocol
Proposed Protocol for Time Synchronization Gj (1,……,N ) } { 1. Gs (Ts) → Gj(Tj ) : Gs, Ns, sync; j=1, ......., N /* Node Gs sends a challenge packet for synchronization, containing its node-id Gs and nonce Ns at time Ts to all nodes in the group and node Gj receive the packet at time Tj */
∀
∈
An Approach towards Time Synchronization Based Secure Protocol for WSN
327
Table 3. (continued)
Gj (T′j) → Gs(T′s) : Gj, T′j, m, M, ACK m = {Tj, Ns, Gs } M = {MAC{ Ksj}[Gj, T′j, Tj, Ns, Gs,, ACK]} /* Node Gj neighboring node of Gs will send response packet to Gs at time T′j. The packet also contains receiving time of challenge packet at Gj i.e.Tj from node Gs with nonce Ns. */ 3. Compute Ds={ dsj : dsj=[(Tj–Ts)+(T′s–T′j)]/2, j=1,..,N } if all dsj ≤ d* /* Calculate end-to-end delay and offset set between each node from source node. */ then Os={ δsj : δsj=[(Tj–Ts)–(T′s-T′j)]/2, j=1,...,N } else Gj is Malicious (external attacker) end if 4. /* Finding internal attackers */ counter=0 /* counter for internal attacker */ for each pair of Gs and node Gj in the group if (| Ssj |≠| Rjs |) /* Ssj= sent time of packet from node Gs to Gj. Rjs= received time of packet from node Gj to Gs.*/ then Gj is Malicious (internal attacker) counter= counter + 1 end if end for Print “Total number of malicious nodes”= counter 5. Calculate δsum= sum of all offsets along the circular path of non-malicious nodes if (δsum==0) then synchronize every node Gj to the fastest clock end if 2.
The proposed protocol is secure against internal as well as external attacks and can synchronize non-malicious nodes to the fastest clock in the group. We have developed three theorems in support of proposed protocol. Theorems are discussed as follows.
328
A.K. Tripathi and A. Agarwal Table 4. Based on synchronization of nodes
Theorem 1: Prove that in a non-malicious environment, circular path of length ≥ 3 can be synchronized to the fastest clock if and only if the sum of offsets along the path is zero. Proof: Assume a circular path P={Gi, Gj, Gk, Gi} of length 3 is formed by nodes Gi, Gj and Gk. The offset of node Gj with respect to node Gi, δij =[(Tj-Ti)–(T′i-T′j)]/2 Similarly, offset of node Gk with respect to node Gj, δjk =[(Tk-Tj)–(T′j-T′k)]/2 and, offset of node Gi with respect to node Gk, δki=[(Ti- Tk)–(T′k- T′i)]/2 Now the sum of offsets along triangled circular path P={Gi, Gj, Gk, Gi} will be δsum = δij + δjk + δki ={(Tj-Ti)–(T′i-T′j)]+[(Tk-Tj)–(T′j-T′k)]+ [(Ti-Tk)–(T′k-T′i)]}/2 = {[Ti+Ti′+Tj+Tj′+Tk+T′k]-[Ti+T′i+Tj+T′j+Tk+T′k]}/2 = 0 Similarly, circular path P={Gi, Gj, Gk, Gl, Gi} is formed by four nodes Gi, Gj, Gk, and Gl . The offset of node Gj with respect to node Gi, δij=[(Tj-Ti)–(T′i-T′j)]/2 Similarly, offset of node Gk with respect to node Gj, δjk=[(Tk-Tj)–(T′j-T′k)]/2 and, offset of node Gl with respect to node Gk, δkl=[(Tl-Tk)–(T′k-T′l)]/2 and, offset of node Gi with respect to node Gl, δli=[(Ti-Tl)–(T′l-T′i)]/2 Now the sum of offsets along triangled circular path P={Gi, Gj, Gk, Gi} will be δsum = δij + δjk + δkl + δli ={[(Tj-Ti)–(T′i-T′j)]+[(Tk-Tj)–(T′j-T′k)] +[(Tl-Tk)–(T′k-T′l)]+[(Ti-Tl)–(T′l-T′i)]}/2 ={[Ti+Ti′+Tj+Tj′+Tk+T′k+Tl+T′l][Ti+T′i+Tj+T′j+Tk+T′k+Tl+T′l]}/2 = 0 From above, δsum=0 is true for N=3 and N=4. Now, we will prove the theorem using Principal of Mathematical Induction. Induction Hypothesis: P(k):There exists δsum=0 on circular path of length k. According to hypothesis for N=k nodes, δsum={[Ti+Ti′+Tj+Tj′+………Tk+T′k][Ti+T′i+Tj+T′j+…………+Tk+T′k]}/2 =0 (5)
An Approach towards Time Synchronization Based Secure Protocol for WSN
329
Table 4. (continued)
Induction step: Now we have to show that P(k+1) is true. Add a new node G(k+1) in circular path of length k. δsum={[Ti+T′i+Tj+T′j+…+Tk+T′k]-[Ti+T′i+Tj+T′j+…+Tk+T′k]+ [T(k+1)+T′(k+1)]-[T(k+1)+T′(k+1)]}/2 = 0 (from eqn 5) + 0 = 0 (6) Hence, from Eqn (5) and (6) it can be concluded that δsum=0 in group of (k+1) nodes. Therefore, P(k+1) is true. This shows that δsum=0 along the path of (k+1) nodes. Hence Proved.
Table 5. Effect of malicious nodes in synchronization
Theorem 2: Prove that if at least one node is malicious in the group, nodes cannot be synchronized to the fastest clock. Proof: A node is said to be malicious, if it does not report the exact time at which it receives or sends the packet. Herein, we assume that malicious node do not report the exact time at which it receives the packet. Let us consider node Gj as malicious. Here, we have assumed that malicious node do not report the exact time at which it receives the packet. Therefore, instead of Tj, node Gj will send receiving time of challenge packet as time T′′j in response packet. As we know, in non-malicious environment, sending time of the packet must be equal to receiving time of packet (since nodes are directly linked to each other in a group). |Tj-Ti|=|T′i-T′j| Now, since node Gj sends receiving time of packet T′′j instead of Tj. Tj ≠ T′′j Therefore, Gi will calculate |T′′j-Ti|≠|T′i-T′j| Hence, Gj will be identified as malicious node by node Gi, and, therefore Gi and Gj cannot be synchronized to the fastest clock. Hence Proved.
330
A.K. Tripathi and A. Agarwal Table 6. To find out maximum number of internal attacker(s)
Theorem 3: Prove that using algorithm for proposed protocol (refer Table 3) one can find N-1 internal attacker(s) in the group size of N nodes. Proof: It is assumed that, the group is made up with the help of N nodes and each node is directly connected to all other nodes in the group. Therefore, (N(N-1))/2 edges exists. Assume that node Gi is non-malicious. Now, let us consider Sij= send time of packet from node Gi to Gj. Rji= receive time of packet from node Gj to Gi.
CASE A: When there are two nodes (N=2) in the group: In the group of size two nodes. If | Sij |≠| Rji |, then node Gj is malicious. Hence, Gj will be identified as malicious node therefore Gi and Gj cannot be synchronized to the fastest clock. CASE B: When there are three nodes (N=3) in the group: In the group of size three nodes. If | Sij |≠| Rji |, then node Gj is malicious. If | Sik |≠| Rki |, then node Gk is malicious. If |Sij|≠|Rji| and |Sik|≠|Rki| then nodes Gj and Gk both are malicious. Hence, if N=3, then at most two nodes (Gj and Gk) can be identified as malicious nodes. From above, the hypothesis is true for N=2 and N=3. Now, we will prove theorem using Principal of Mathematical Induction. Induction Hypothesis: P(k)=(k-1) internal attackers are identified for N=k nodes. (a) Induction step: Now we have to show that (a) is true for N=k+1 i.e. P(k+1)=k internal attackers can be identified for N=k+1. Consider there are k nodes in the group having node Gi as non-malicious node. Now consider one new node G(k+1). If |Si(k+1)|≠|R(k+1)i|, then node G(k+1) is malicious. (b) Hence, from hypothesis steps (a) and (b) it can be concluded that there exists k malicious nodes in the group of (k+1) nodes. Therefore, P(k+1) is true. This shows that at most k nodes can be identified as malicious in group of (k+1) nodes. Hence Proved.
An Approach towards Time Synchronization Based Secure Protocol for WSN
331
4 Conclusion Existing solutions for time synchronization in sensor networks are not resilient to malicious behavior from external attackers or internally compromised nodes. The feasibility of a pulse-delay attack (external attack), whereby an attacker can introduce arbitrarily long delays in the packet propagation time directly can affect the achieved synchronization precision. The external attacks can be resolved with the help of MAC message authentication codes and the use of private keys. Internal attacks which occur in case of group wise synchronization can’t be resolved completely and efficiently by the existing protocols till date. We have proposed a protocol to remove external as well as internal attacker problems in group synchronization. Further, proposed protocol ensures that it can cope up with both problems securely. This protocol uses MAC to cope up with the external attacker problem, and uses a consistency check mechanism to cope up with the problem of internal attacker. It firstly ensures that the group is secured against attackers. Consistency check mechanism is applied on every node and if this step