Ubiquitous Intelligence and Computing: 5th International Conference, UIC 2008, Oslo, Norway, June 23-25, 2008 Proceedings

Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen

Editorial Board David Hutchison Lancaster University, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Alfred Kobsa University of California, Irvine, CA, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen University of Dortmund, Germany Madhu Sudan Massachusetts Institute of Technology, MA, USA Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Gerhard Weikum Max-Planck Institute of Computer Science, Saarbruecken, Germany

5061

Frode Eika Sandnes Yan Zhang Chunming Rong Laurence T. Yang Jianhua Ma (Eds.)

Ubiquitous Intelligence and Computing 5th International Conference, UIC 2008 Oslo, Norway, June 23-25, 2008 Proceedings

13

Volume Editors Frode Eika Sandnes Oslo University College, Oslo, Norway E-mail: [email protected] Yan Zhang Simula Research Laboratory, Lysaker, Norway E-mail: [email protected] Chunming Rong University of Stavanger, Stavanger, Norway E-mail: [email protected] Laurence T. Yang St. Francis Xavier University, Antigonish, NS, Canada E-mail: [email protected] Jianhua Ma Hosei University, Tokyo 184-8584, Japan E-mail: [email protected]

Library of Congress Control Number: 2008929350 CR Subject Classification (1998): H.4, C.2, D.4.6, H.5, I.2, K.4 LNCS Sublibrary: SL 3 – Information Systems and Application, incl. Internet/Web and HCI ISSN ISBN-10 ISBN-13

0302-9743 3-540-69292-4 Springer Berlin Heidelberg New York 978-3-540-69292-8 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 is a part of Springer Science+Business Media springer.com © Springer-Verlag Berlin Heidelberg 2008 Printed in Germany Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acid-free paper SPIN: 12277919 06/3180 543210

Preface

This volume contains the proceedings of UIC 2008, the 5th International Conference on Ubiquitous Intelligence and Computing: Building Smart Worlds in Real and Cyber Spaces. The conference was held in Oslo, Norway, during June 23–25, 2008. The event was the fifth meeting of this conference series. USW 2005 (First International Workshop on Ubiquitous Smart World), held in March 2005 in Taiwan, was the first event in the series. This event was followed by UISW 2005 (Second International Symposium on Ubiquitous Intelligence and Smart Worlds) held in December 2005 in Japan, by UIC 2006 (Third International Conference on Ubiquitous Intelligence and Computing: Building Smart Worlds in Real and Cyber Spaces) held in September 2006 in Wuhan and Three Gorges, China, and by UIC 2007 held in July 2007 in Hong Kong. Ubiquitous computers, networks and information are paving the road to a smart world in which computational intelligence is distributed throughout the physical environment to provide trustworthy and relevant services to people. This ubiquitous intelligence will change the computing landscape because it will enable new breeds of applications and systems to be developed; the realm of computing possibilities will be significantly extended. By embedding digital intelligence in everyday objects, our workplaces, our homes and even ourselves, many tasks and processes could be simplified, made more efficient, safer and more enjoyable. Ubiquitous computing, or pervasive computing, composes these numerous “smart things/u-things” to create the environments that underpin the smart world. A smart thing can be endowed with different levels of intelligence, and may be context-aware, active, interactive, reactive, proactive, assistive, adaptive, automated, sentient, perceptual, cognitive, autonomic and/or thinking. The field of intelligent/smart things is an emerging research field that covers many disciplines. A series of grand challenges exist to move from the world of ubiquitous computing with universal services of any means/place/time to the smart world of trustworthy services with the right means/place/time. The UIC 2008 conference offered a forum for researchers to exchange ideas and experiences in developing intelligent/smart objects, environments, and systems. This year, the technical program of UIC drew from a very large number of submissions: 102 papers submitted from 26 countries representing four regions – Asia Pacific, Europe, North and South America. Each accepted paper was reviewed (as a full paper) by at least three reviewers, coordinated by the international Program Committee. In order to allocate as many papers as possible and keep the high quality of the conference, we finally decided to accept 27 regular papers for presentation, which reflected a 26% acceptance rate. In addition, there were 28 special session papers included into the proceedings. The accepted papers provide research contributions

VI

Preface

in a wide range of research topics that were grouped into 14 conference tracks: smart objects and embedded systems, smart spaces/environments/services, intelligent computing, wireless sensor networks, context-aware applications and systems, and wireless networks. In addition to the refereed papers, the proceedings include Jadwiga Indulska’s keynote address on “Challenges in the Design and Development of Context-Aware Applications,” Petter Øyan’s keynote address on “The Importance of Including the Haptics Factor in Interaction Design,” and an invited paper from Stephen S. Yau on “Security Policy Integration and Conflict Reconciliation for Collaborations Among Organizations in Ubiquitous Computing Environment.” We believe that the conference not only presented novel and interesting ideas but also stimulated future research in the area of ubiquitous intelligence and computing. Organization of conferences with a large number of submissions requires a lot of hard work and dedication from many people. We would like to take this opportunity to thank the numerous people whose work made this conference possible and ensured its high quality. We wish to thank the authors of submitted papers, as they contributed to the conference technical program. We wish to express our deepest gratitude to the Program (Vice) Chairs for their hard work and commitment to quality when helping with paper selection. We would also like to thank all Program Committee members and external reviewers for their excellent job in the paper review process, the Steering Committee and Advisory Committee for their continuous advice, and Jadwiga Indulska and Daqing Zhang for organizing a panel on the important question: “What do we expect from pervasive/intelligent computing and how far are we from achieving it?” A special thanks to Yo-Ping Huang for organizing a special session on “Object Identification: Techniques and Applications.” We are also in debt to the Publicity Chairs for advertising the conference, to the Local Organizing Committee for managing the registration and other conference organization-related tasks, and to Oslo University College for hosting the conference. We are also grateful to Kyrre Begnum for the hard work on managing the conference website and the conference management system.

June 2008

Frode Eika Sandnes, Yan Zhang, Chunming Rong, Laurence Tianruo Yang and Jianhua Ma UIC 2008 Editors

Organization

Executive Committee General Chairs

Program Chairs

Program Vice Chairs

Honorary Chairs Steering Committee

International Advisory Committee

Frode Eika Sandnes, Oslo University College, Norway Mark Burgess, Oslo University College, Norway Chunming Rong, University of Stavanger, Norway Yan Zhang, Simula Research Laboratory, Norway D. Manivannan, University of Kentucky, USA Michael Beigl, University of Hannover, Germany Yo-Ping Huang, National Taipei University of Technology, Taiwan Oliver Sinnen, University of Auckland, New Zealand Graham Megson, University of Reading, UK Stephen S. Yau, Arizona State University, USA Norio Shiratori, Tohoku University, Japan Jianhua Ma (Chair), Hosei University, Japan Laurence T. Yang (Chair), St. Francis Xavier University, Canada Hai Jin, Huazhong University of Science and Technology, China Jeffrey J.P. Tsai, University of Illinois at Chicago, USA Theo Ungerer, University of Augsburg, Germany Leonard Barolli, Fukuoka Institute of Technology, Japan Victor Callaghan, University of Essex, UK Yookun Cho, Seoul National University, Korea Sumi Helal, University of Florida, USA Frank Hsu, Fordham University, USA Ali R. Hurson, Pennsylvania State University, USA Qun Jin, Waseda University, Japan Beniamino Di Martino, Second University of Naples, Italy Christian Muller-Schloer, University of Hannover, Germany Timothy K. Shih, Tamkang University, Taiwan Ivan Stojmenovic, Ottawa University, Canada Makoto Takizawa, Tokyo Denki University, Japan David Taniar, Monash University, Australia Jhing-Fa Wang, National Cheng Kung University, Taiwan

VIII

Organization

Executive Committee(continued) International Advisory Committee

Publicity Chairs

International Liaison Chairs

Award Chairs

Panel Chairs

Special Session Organizer Publication Chairs Web Chair Local Organizing Chair

Guangyou Xu, Tsinghua University, China Yaoxue Zhang, Tsinghua University, China Albert Zomaya, University of Sydney, Australia Yueh-Min Huang, National Cheng Kung University, Taiwan Jinhua Guo, University of Michigan - Dearborn, USA Mieso Denko, University of Guelph, Canada Hakan Duman, British Telecom, UK Ohbyung Kwon, Kyunghee University, Korea Wen Jing Hsu, National University of Singapore, Singapore Benxiong Huang, Huazhong University of Science and Technology, China Jong Hyuk Park, Kyungnam University, Korea Leonel Sousa, INESC-ID, Portugal Si Qing Zheng, University of Texas at Dallas, USA David Nelson, University of Sunderland, UK Jiannong Cao, Hong Kong Polytechnic University, Hong Kong Demissie Aredo, Oslo University College, Norway Jadwiga Indulska, University of Queensland, Australia Daqing Zhang, National Institute of Telecommunications, France Yo-Ping Huang, National Taipei University of Technology, Taiwan Tony Li Xu, St. Francis Xavier University, Canada Liu Yang, St. Francis Xavier University, Canada Ismail Hassan, Oslo University College, Norway Siri Fagernes, Oslo University College, Norway Simen Hagen, Oslo University College, Norway Kirsten Ribu, Oslo University College, Norway Kyrre Begnum, Oslo University College, Norway Jie Xiang, Simula Research Laboratory, Norway Qin Xin, Simula Research Laboratory, Norway Hai Ngoc Pham, University of Oslo, Norway

Program Committee Waleed Abdulla Sheikh Iqbal Ahamed

The University of Auckland, New Zealand Marquette University, USA

Organization

IX

Program Committee(continued) Alexandra Branzan Albu Najah Abu Ali Noureddine Boudriga Phillip G. Bradford Tsun-Wei Chang Jiming Chen Ruey-Maw Chen Shu-Chen Cheng Wei Chen Wen Chen Peter H.J. Chong Hung-Chi Chu Alva Couch Alma Leora Culn Waltenegus Dargie Reza Dilmaghani Panayotis E. Fouliras Alois Ferscha Edgar Gabriel Antonio Mana Gomez Zonghua Gu Khoon Guan Winston Seah Arobinda Gupta Laurence Habib Hrek Haugerud Dag Haugland Jianhua He Shang-Lin Hsieh Bin Hu Lin-Huang Chang Yu Hua Tao Jiang Wenbin Jiang Tore Møller Jonassen Audun Josang James B.D. Joshi Akimitsu Kanzaki Helen Karatza Andreas J. Kassler

University of Victoria, Canada United Arab Emirates University, UAE University of Carthage, Tunisia University of Alabama, USA De Ling Institute of Technology, Taiwan Zhejiang University, China National Chin-Yi University of Technology, Taiwan Southern Taiwan University, Taiwan Nanjing University of Posts and Telecommunications, China Shanghai Jiaotong University, China Nanyang Technological University, Singapore Chaoyang University of Technology, Taiwan Tufts University, USA University of Oslo, Norway Technical University of Dresden, Germany King’s College London, UK University of Macedonia, Greece Johannes Kepler Universit¨ at Linz, Austria University of Houston, USA University of Malaga, Spain Hong Kong University of Science and Technology, Hong Kong Institute for Infocomm Research, Singapore Indian Institute of Technology, India Oslo University College, Norway Oslo University College, Norway Bergen University, Norway Swansea University, UK Tatung University, Taiwan University of Central England, UK National Taichung University, Taiwan Huazhong University of Science and Technology, China University of Michigan, USA Huazhong University of Science and Technology, China Oslo University College, Norway Queensland University of Technology, Australia University of Pittsburgh, USA Osaka University, Japan Aristotle Univeristy of Thessaloniki, Greece Karlstad University, Sweden

X

Organization

Program Committee(continued) Paris Kitsos Gabriele Kotsis Lars Kristiansen Stefan Lankes Matti Latva-aho Cai Li Frank Li Jie Li Shiguo Lian Daw-Tung Lin Giuseppe Lo Re Arne Lkketangen Sathiamoorthy Manoharan Hassnaa Moustafa Josef Noll Lukowicz Paul

Hellenic Open University, Greece Johannes Kepler University of Linz, Austria University of Oslo, Norway RWTH Aachen University, Germany Oulu University, Finland Communications University of China, China Agder University, Norway University of Tsukuba, Japan France Telecom R&D Beijing, China National Taipei University, Taiwan University of Palermo, Italy Molde University College, Norway

University of Auckland, New Zealand France Telecom R&D , France UniK/Movation, Norway Lehrstuhl f¨ ur Informatik, Universit¨ at Passau, Germany Marius Portmann University of Queensland, Australia Ravi Prakash University of Texas at Dallas, USA Antonio Puliafito University of Messina, Italy Ragnihild Kobro Runde University of Oslo, Norway Hamid Sharif University of Nebraska, USA Albrecht Schmidt University of Munich, Germany Rose Shumba Indiana University of Pennsylvania, USA Isabelle Simplot-Ryl University of Lille, France Lingyang Song University of Oslo, Norway Min Song Old Dominion University, USA Lambert Spaanenburg Lund University, Sweden Zhou Su Waseda University, Japan Evi Syukur Monash University, Australia Chik How Tan Gjvik University College, Norway Hallvard Trtteberg Norwegian University of Science and Technology, Norway Shiao-Li Tsao National Chiao Tung University, Taiwan Thanos Vasilakos University of Western Macedonia, Greece Javier Garcia Villalba Complutense University of Madrid, Spain Agustinus Borgy Waluyo Institute for Infocomm Research (I2R), Singapore Guojun Wang Central South University, China Tzone-I Wang National Cheng-Kung University, Taiwan Xinbing Wang Shanghai Jiaotong University, China Zhijun Wang Hong Kong Polytechnic University, Hong Kong Jiang (Linda)Xie University of North Carolina at Charlotte, USA Qin Xin Simula Research Laboratory, Norway

Organization

Program Committee(continued) Stephen Yang Wei Yen Muhammad Younas Rong Yu Hongwei Zhang Chi Zhou Yuefeng Zhou

National Central University, Taiwan Tatung University, Taiwan Oxford Brookes University, UK South China University of Technology, China Wayne State University, USA Illinois Institute of Technology, USA NEC Laboratories Europe, UK

XI

Table of Contents

Keynote Speech Challenges in the Design and Development of Context-Aware Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jadwiga Indulska

1

The Importance of Including the Haptics Factor in Interaction Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Petter Øyan and Anne Liseth Schøyen

2

Regular Papers Ubiquitous Computing Security Policy Integration and Conflict Reconciliation for Collaborations among Organizations in Ubiquitous Computing Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Stephen S. Yau and Zhaoji Chen Improved Weighted Centroid Localization in Smart Ubiquitous Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Stephan Schuhmann, Klaus Herrmann, Kurt Rothermel, Jan Blumenthal, and Dirk Timmermann A Formal Framework for Expressing Trust Negotiation in the Ubiquitous Computing Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Deqing Zou, Jong Hyuk Park, Laurence Tianruo Yang, Zhensong Liao, and Tai-hoon Kim Pervasive Services on the Move: Smart Service Diffusion on the OSGi Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Davy Preuveneers and Yolande Berbers

3

20

35

46

Smart Spaces/Environments/Services Robots in Smart Spaces - A Case Study of a u-Object Finder Prototype - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tomomi Kawashima, Jianhua Ma, Bernady O. Apduhan, Runhe Huang, and Qun Jin Biometrics Driven Smart Environments: Abstract Framework and Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Vivek Menon, Bharat Jayaraman, and Venu Govindaraju

61

75

XIV

Table of Contents

A Structured Methodology of Scenario Generation and System Analysis for Ubiquitous Smart Space Development . . . . . . . . . . . . . . . . . . . . . . . . . . . Ohbyung Kwon and Yonnim Lee Capturing Semantics for Information Security and Privacy Assurance . . . Mohammad M.R. Chowdhury, Javier Chamizo, Josef Noll, and Juan Miguel G´ omez

90

105

Context-Aware Services and Applications A Framework for Context-Aware Home-Health Monitoring . . . . . . . . . . . . Alessandra Esposito, Luciano Tarricone, Marco Zappatore, Luca Catarinucci, Riccardo Colella, and Angelo DiBari Semantic Learning Space: An Infrastructure for Context-Aware Ubiquitous Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Zhiwen Yu, Xingshe Zhou, and Yuichi Nakamura A Comprehensive Approach for Situation-Awareness Based on Sensing and Reasoning about Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Thomas Springer, Patrick Wustmann, Iris Braun, Waltenegus Dargie, and Michael Berger

119

131

143

Context-Adaptive User Interface in Ubiquitous Home Generated by Bayesian and Action Selection Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . Han-Saem Park, In-Jee Song, and Sung-Bae Cho

158

Use Semantic Decision Tables to Improve Meaning Evolution Support Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Yan Tang and Robert Meersman

169

Combining User Profiles and Situation Contexts for Spontaneous Service Provision in Smart Assistive Environments . . . . . . . . . . . . . . . . . . . Weijun Qin, Daqing Zhang, Yuanchun Shi, and Kejun Du

187

Ubiquitous Phone System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Shan-Yi Tsai, Chiung-Ying Wang, and Ren-Hung Hwang

201

Utilizing RFIDs for Location Aware Computing . . . . . . . . . . . . . . . . . . . . . Benjamin Becker, Manuel Huber, and Gudrun Klinker

216

Intelligent Computing: Middleware, Models and Services A Component-Based Ambient Agent Model for Assessment of Driving Behaviour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tibor Bosse, Mark Hoogendoorn, Michel C.A. Klein, and Jan Treur

229

Table of Contents

XV

A Cartesian Robot for RFID Signal Distribution Model Verification . . . . Aliasgar Kutiyanawala and Vladimir Kulyukin

244

Self-Localization in a Low Cost Bluetooth Environment . . . . . . . . . . . . . . . Julio Oliveira Filho, Ana Bunoza, J¨ urgen Sommer, and Wolfgang Rosenstiel

258

Penetration Testing of OPC as Part of Process Control Systems . . . . . . . Maria B. Line, Martin Gilje Jaatun, Zi Bin Cheah, A.B.M. Omar Faruk, H˚ avard Husev˚ ag Garnes, and Petter Wedum

271

Intersection Location Service for Vehicular Ad Hoc Networks with Cars in Manhattan Style Movement Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Yao-Jen Chang and Shang-Yao Wu

284

Ubiquitous and Robust Text-Independent Speaker Recognition for Home Automation Digital Life . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jhing-Fa Wang, Ta-Wen Kuan, Jia-chang Wang, and Gaung-Hui Gu

297

Energy Efficient In-Network Phase RFID Data Filtering Scheme . . . . . . . Dong-Sub Kim, Ali Kashif, Xue Ming, Jung-Hwan Kim, and Myong-Soon Park Energy-Efficient Tracking of Continuous Objects in Wireless Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jung-Hwan Kim, Kee-Bum Kim, Chauhdary Sajjad Hussain, Min-Woo Cui, and Myong-Soon Park

311

323

Wireless Sensor Networks Data Randomization for Lightweight Secure Data Aggregation in Sensor Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Abedelaziz Mohaisen, Ik Rae Jeong, Dowon Hong, Nam-Su Jho, and DaeHun Nyang Mobile Sink Routing Protocol with Registering in Cluster-Based Wireless Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ying-Hong Wang, Kuo-Feng Huang, Ping-Fang Fu, and Jun-Xuan Wang

338

352

Towards the Implementation of Reliable Data Transmission for 802.15.4-Based Wireless Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . Taeshik Shon and Hyohyun Choi

363

An Energy-Efficient Query Processing Algorithm for Wireless Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jun-Zhao Sun

373

XVI

Table of Contents

Special Session Papers Smart Objects and Embedded Computing Rule Selection for Collaborative Ubiquitous Smart Device Development: Rough Set Based Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kyoung-Yun Kim, Keunho Choi and Ohbyung Kwon

386

An Object-Oriented Framework for Common Abstraction and the Comet-Based Interaction of Physical u-Objects and Digital Services . . . . Kei Nakanishi, Jianhua Ma, Bernady O. Apduhan, and Runhe Huang

397

Personalizing Threshold Values on Behavior Detection with Collaborative Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hiroyuki Yamahara, Fumiko Harada, Hideyuki Takada, and Hiromitsu Shimakawa IP Traceback Using Digital Watermark and Honeypot . . . . . . . . . . . . . . . . Zaiyao Yi, Liuqing Pan, Xinmei Wang, Chen Huang, and Benxiong Huang

411

426

Wireless Networks: Routing, Mobility and Security Multi-priority Multi-path Selection for Video Streaming in Wireless Multimedia Sensor Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lin Zhang, Manfred Hauswirth, Lei Shu, Zhangbing Zhou, Vinny Reynolds, and Guangjie Han

439

Energy Constrained Multipath Routing in Wireless Sensor Networks . . . Antoine B. Bagula and Kuzamunu G. Mazandu

453

Controlling Uncertainty in Personal Positioning at Minimal Measurement Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hui Fang, Wen-Jing Hsu, and Larry Rudolph

468

RFID System Security Using Identity-Based Cryptography . . . . . . . . . . . . Yan Liang and Chunming Rong

482

Ubiquitous Computing RFID: An Ideal Technology for Ubiquitous Computing? . . . . . . . . . . . . . . . Ciaran O’Driscoll, Daniel MacCormac, Mark Deegan, Fred Mtenzi, and Brendan O’Shea An Experimental Analysis of Undo in Ubiquitous Computing Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Marco Loregian and Marco P. Locatelli

490

505

Table of Contents

XVII

Towards a Collaborative Reputation Based Service Provider Selection in Ubiquitous Computing Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . Malamati Louta

520

Petri Net-Based Episode Detection and Story Generation from Ubiquitous Life Log . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Young-Seol Lee and Sung-Bae Cho

535

Smart Spaces/Environments/Services Protection Techniques of Secret Information in Non-tamper Proof Devices of Smart Home Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Abedelaziz Mohaisen, YoungJae Maeng, Joenil Kang, DaeHun Nyang, KyungHee Lee, Dowon Hong, and Jong-Wook Han

548

Universal Remote Control for the Smart World . . . . . . . . . . . . . . . . . . . . . . Jukka Riekki, Ivan Sanchez, and Mikko Pyykk¨ onen

563

Mobile Navigation System for the Elderly – Preliminary Experiment and Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Takahiro Kawamura, Keisuke Umezu, and Akihiko Ohsuga

578

Time Stamp Protocol for Smart Environment Services . . . . . . . . . . . . . . . . Deok-Gyu Lee, Jong-Wook Han, Jong Hyuk Park, Sang Soo Yeo, and Young-Sik Jeong

591

Intelligent Computing: Middleware, Models and Services An Analysis of the Manufacturing Messaging Specification Protocol . . . . Jan Tore Sørensen and Martin Gilje Jaatun

602

A Long-Distance Time Domain Sound Localization . . . . . . . . . . . . . . . . . . . Jhing-Fa Wang, Jia-chang Wang, Bo-Wei Chen, and Zheng-Wei Sun

616

Towards Dataintegration from WITSML to ISO 15926 . . . . . . . . . . . . . . . . Kari Anne Haaland Thorsen and Chunming Rong

626

A SIP-Based Session Mobility Management Framework for Ubiquitous Multimedia Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chung-Ming Huang and Chang-Zhou Tsai

636

Context-Aware Services and Applications AwarePen - Classification Probability and Fuzziness in a Context Aware Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Martin Berchtold, Till Riedel, Michael Beigl, and Christian Decker

647

XVIII

Table of Contents

A Model Driven Development Method for Developing Context-Aware Pervasive Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Estefan´ıa Serral, Pedro Valderas, and Vicente Pelechano

662

Intelligent System Architecture for Context-Awareness in Ubiquitous Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jae-Woo Chang and Seung-Tae Hong

677

User-Based Constraint Strategy in Ontology Matching . . . . . . . . . . . . . . . . Feiyu Lin and Kurt Sandkuhl

687

Object Identification: Techniques and Applications RFID-Based Interactive Learning in Science Museums . . . . . . . . . . . . . . . . Yo-Ping Huang, Yueh-Tsun Chang, and Frode Eika Sandnes

697

Real-time Detection of Passing Objects Using Virtual Gate and Motion Vector Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Daw-Tung Lin and Li-Wei Liu

710

A Ubiquitous Interactive Museum Guide . . . . . . . . . . . . . . . . . . . . . . . . . . . . Yo-Ping Huang, Tsun-Wei Chang, and Frode Eika Sandnes

720

Dynamic Probabilistic Packet Marking with Partial Non-Preemption . . . Wei Yen and Jeng-Shian Sung

732

Fractal Model Based Face Recognition for Ubiquitous Environments . . . . Shuenn-Shyang Wang, Su-Wei Lin, and Cheng-Ming Cho

746

Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

761

Challenges in the Design and Development of Context-Aware Applications Jadwiga Indulska School of Information Technology and Electrical Engineering, The University of Queensland and NICTA [email protected]

Abstract. Context-awareness plays an important role in pervasive computing as adaptations of applications to context changes (changes in computing environment and in user activities/tasks) help to achieve the goal of computing services available everywhere and at any time. There is a growing body of research on context-aware applications that are adaptable and capable of acting autonomously on behalf of users. However, there are still many open research issues that challenge the pervasive computing community. In this talk I discuss several of these research challenges. First, I outline the state of the art in context information modelling, management and reasoning as well as possible future research directions in this area. This is followed by a discussion of context information management that allows development of fault-tolerant and autonomic context-aware applications. As one of the challenges inhibiting the development of context-aware applications is their complexity, I discuss software engineering approaches that ease the task of developing such applications. Context-aware applications adapt to context changes using context information. However this context information may be imprecise or erroneous and therefore can lead to incorrect adaptation decisions creating usability problems and affecting acceptance of context-aware applications. This creates a need for some balance between autonomy of context-aware applications and the user control of the applications. I describe some early approaches my team is working on to tackle this problem. Finally, I discuss research issues related to privacy of context information and how context can be used to enhance security mechanisms within pervasive computing environments.



NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence program; and the Queensland Government.

F.E. Sandnes et al. (Eds.): UIC 2008, LNCS 5061, p. 1, 2008. c Springer-Verlag Berlin Heidelberg 2008 

The Importance of Including the Haptics Factor in Interaction Design Petter Øyan and Anne Liseth Schøyen

Abstract. One aspect of interaction design is communication of information through the use of a screen. Another aspect, the physical or haptic interaction with the device itself, is another important issue, especially to reduce errors when the device is used in critical situations. Ostfold university college has cooperated with the Institute for Energy Technology in Halden and the Norwegian Defence Research Establishment in Kjeller, and several student groups have been given the opportunity to work on research data and in collaboration with researchers from these two institutions within their final year studies. The focus of the projects has been realistic; emphasizing the importance of minimizing operating errors to ensure safe operation in critical situations, where the ability to give correct feedback through haptic interaction is as important as the correct understanding of visual communication. The cases are demonstrating the user centered approach to problem solving used by industrial designers and the analogy between the design- and the resarch process, especially focusing on the use of physical designs to test and review and thereby exploring form as an interaction parameter.

F.E. Sandnes et al. (Eds.): UIC 2008, LNCS 5061, p. 2, 2008. © Springer-Verlag Berlin Heidelberg 2008

Security Policy Integration and Conflict Reconciliation for Collaborations among Organizations in Ubiquitous Computing Environments Stephen S. Yau and Zhaoji Chen Department of Computer Science and Engineering School of Computing and Informatics Arizona State University Tempe, AZ 85287-8809, USA {yau,zhaoji.chen}@asu.edu

Abstracts. The investigative capabilities and productivity of researchers and practitioners of various organizations can be greatly expanded with collaborations among these organizations in ubiquitous computing environments. However, in order to provide effective collaborations among organizations in ubiquitous computing environments, due to the heterogeneity and dynamic nature of the ubiquitous computing environments it is critical to generate an integrated security policy set to govern the interactions among collaborating organizations during the collaboration. Existing approaches in security policy integration and conflict analysis have focused on static policy analysis which cannot address the dynamic formation of collaborative groups in ubiquitous computing environments. In this paper, an approach is presented to security policy integration, including a similarity-based policy adaptation algorithm for changing collaborative groups and a negotiation-based policy generation protocol for the new resources generated by the collaboration as well as for conflict reconciliation. Our approach can be automated with user defined control variables, which can greatly improve the efficiency and make the system scalable with little human intervention. Keywords: Security policy integration, conflict reconciliation, organization collaboration, similarity-based policy adaptation, negotiation-based policy reconciliation, ontology, ubiquitous computing environments.

1 Introduction Due to rapid development of mobile devices and embedded systems, computing resources are embedded in various devices, appliances, such as cell phones, PDAs, televisions, TiVo, refrigerator and cars. All these devices can provide certain information processing capability. With the technologies, such as Bluetooth and Wi-Fi, these devices can easily communicate and share data and/or resources with each other. These advances in ubiquitous computing can greatly improve the investigative capabilities and productivity of researchers and practitioners in many fields, such as health care, e-business, e-government, telecommunication, and homeland security, F.E. Sandnes et al. (Eds.): UIC 2008, LNCS 5061, pp. 3–19, 2008. © Springer-Verlag Berlin Heidelberg 2008

4

S.S. Yau and Z. Chen

where the sharing of data, equipment and other resources among collaborating organizations may be extensive. In such an environment, computing resources are distributed throughout the physical environment, and are usually owned and managed by various organizations. An organization can be viewed as a set of nodes which has a set of users, certain resources and is capable of performing certain functions autonomously. To facilitate collaborations among participating organizations, we need to make their resources available across organizations seamlessly. By seamlessly, we mean if a user from one of the participating organizations enters the environment controlled by another organization, the user can access and use the appropriate resources through direct interactions with the resource owners. Otherwise, the user will need to send a request to his/her affiliated organization, and then the affiliated organization will forward the request to the organizations which own the resources. The resource owners would then make the decisions on whether to allow the user to access their resources, and then inform the affiliated organization, which will inform the user of their decisions. It is obvious that seamless resource sharing will greatly improve the effectiveness and efficiency of collaborations among various organizations. However, ubiquitous computing devices in such ubiquitous computing environments are more vulnerable to attacks than other distributed computing systems, especially when malicious users pretend to be legitimate users and try to sneak in the collaboration groups. With the growing concerns on security and privacy, a major obstacle for this kind of collaborations to be widely adopted, especially for critical applications, is how to govern the access to sensitive data and limited resources during the collaborations. Each organization may specify its own set of security policies to govern how its users to access its resources. But, in collaborations among organizations, we need to integrate all the relevant security policies from the participating organizations to govern the interactions throughout the collaborations. The heterogeneity and dynamic nature of ubiquitous computing environments poses certain unique challenges for generating an integrated congruous security policy set. In this paper, we will present an approach to integrating security policies of collaborating organizations in ubiquitous computing environments, including a similarity-based policy adaptation algorithm for security policy integration and a negotiation protocol for conflict reconciliation. An example will be given to illustrate our approach.

2 Challenges and Current State of the Art Collaborations among organizations in ubiquitous computing environments have the following characteristics. First, each organization is a group of nodes which manages its own resources and can function autonomously. Second, a group of collaborating organizations can be formed and changed at runtime. Each organization can choose to join or leave the group based on its needs. Third, organizations are peers to each other. Normally, there is no organization to serve as an authority to coordinate or manage the interactions among various collaborating organizations. Due to these characteristics, we have the following three major challenges for providing security in such environments.

Security Policy Integration and Conflict Reconciliation

5

1) Ambiguous security policy specifications: Each participating organization specifies its security policies describing how its resources should be used, including various limits and access control, and how these policies are enforced at runtime. Because each organization acts autonomously, the organizations can choose different vocabularies to specify their own security policies, which may cause confusion and difficulty when they try to understand each other’s policies. 2) Dynamic set of users: Individual organization’s security policies normally do not address the expanded user sets for collaborations. An organization’s security policies only address its own users and resources. Because there is no authority in the coalition to manage the requests from other organizations, and because the group of collaborating organizations may be changing, security policies specified by participating organizations need to be integrated together to govern the interactions during the collaboration, and the owner of a resource needs to know how to handle the requests from other organizations at runtime without prior knowledge of the collaborators. The collaboration may generate some resources that cannot be provided by any single participating organization. To govern future accesses to these new resources, the integrated security policy set should include policies for all these resources and the policies need to be acceptable by all participating organizations. 3) Conflicting security policies: Participating organizations may have inconsistent security policies among them. Because the group of collaborating organizations may continuously change at runtime, the organizations cannot anticipate all possible collaborative partners a priori and specify their security policies accordingly. The fact that each participating organization has little knowledge about what has or has not been specified by the other organizations may lead to redundancy and conflict when trying to integrating their security policies together. To avoid inconsistency in security policies integration and enforcement, redundant policies should be removed, and conflicts must be resolved. To address the first challenge, several approaches [1, 2, 4] have been developed to provide unambiguous interoperable security policy specifications using XML. These approaches provide syntactic tags for the security policy specifications and the tags show how the specifications should be interpreted. The general syntax of such approaches is rigid in the sense that specifications must adhere to the general rules of XML to ensure that all XML-aware software can at least read and understand the relative arrangement of information within them. This usually results in lengthy specifications as the user needs to define a lot of tags just to comply with XML standards. We have developed an approach based on ontology in [3], where the security policy has a fixed format, but users can derive individual components from an ontology to specify application-specific information needed in the security policy specifications. All these approaches can address Challenge 1) sufficiently and provide unambiguous security policy specifications across collaborating organizations. In this paper, we will present methods to address Challenges 2) and 3). To address Challenge 2), relevant security policies from various collaborating organizations need to be combined together. Bonatti et al. [5] dealt the policy composition problem through a multi-level security model. Bidan et al. [6] introduced a set of

6

S.S. Yau and Z. Chen

combination operators to combine security policies in a controlled manner. Several algebraic operators for combining enterprise privacy policies specified by EPAL were introduced in [7]. SPL [8] has stratified security rules, and there is a special layer of rules, which is used to control policy integration. These approaches are common in that they all require prior knowledge about the other collaborating organizations. However, in ubiquitous computing environments, groups of collaborating organizations are continuously changing with participating organizations joining or leaving the groups/. Each organization has little prior knowledge on the security policies of other collaborating organizations and how they will impact its own security policies. To address Challenge 3), Ribeiro, Zuquete and Ferreira [8] specified special rules to decide which security policy should override the others when there is a conflict. Similarly, Lupu and Sloman [9] specified “policy precedence relationships” to determine which one of two conflicting policies should apply and which should be ignored. Agrawal et al. [10] presented an approach to eliminating conflicts by checking the new policies and prevent them from being added to the integrated policy set if there is a conflict. All these approaches rely on some policy hierarchy structure, where certain policies are more important than the others, and more important policies override less important ones in case of conflict. For [10], the security policies that are already in the integrated set are more important than those that are waiting to join the set. It is difficult to adopt these approaches in ubiquitous computing environments because there is no authority in the group of collaborating organizations to establish such hierarchy and each participating organization is an autonomous entity. Hence, it is not reasonable to choose an organization’s security policies over the others in case of conflict. So far, no comprehensive approach addresses both Challenges 2) and 3) for collaborations among organizations in ubiquitous computing environments, where groups of collaborating organizations are continuously changing with little prior knowledge about when other organizations will join and what kinds of security policies they have specified. This makes policy integration and conflict reconciliation more difficult compared to the case that the groups of collaborating organizations remain the same.

3 Our Overall Approach Our approach aims at generating an integrated, congruous security policy set based on the security policies specified by individual participating organizations. Our overall approach is shown in Fig.1 and consists of the following three major parts. Part1) uses a specification language similar to the one we presented in [3] to generate security policy specifications for each collaborating organization, where a security policy can be specified as a quadtuple with the components derived from the ontology containing the key concepts needed for specifying security policies. For the sake of completeness, we will summarize the important aspects of this specification language needed in our approach in the Appendix.

Security Policy Integration and Conflict Reconciliation

7

Part2) adapts existing security policies to address the expanded user set for the collaboration. When an access to a resource is requested by a user from other participating organizations, the resource owner should make the decision on whether to grant the request to the resource. However, since the requester is from another organization, the resource owner may not have much knowledge about this requester, which makes it difficult to make a decision on the request. In reality, it is natural to evaluate a

OrgA

OrgB

Natural Language Security Policies

Natural Language Security Policies

Security Policy Specification Language

Security Policy Specification Language

Part1

Security Policy Specifications

Security Policy Specifications

Address expanded user set

Address newly generated resources Integration Process Negotiation-base Policy Generation

Similarity-base Security Policy Adaptation

Part2 Integrated Security Policy Specifications

Part3

Yes Have conflicts?

No

Negotiation -base Conflict Reconciliation

Final Security Policy Set for Collaboration

Fig. 1. Our overall approach for security policy integration and conflict reconciliation

8

S.S. Yau and Z. Chen

stranger’s trustworthiness based on where he comes from and how he is trusted in the organizations he belonged before. Thus, we will use a similarity-base security policy adaptation algorithm to help the resource owner make a decision based on evaluating whether the participating organizations that the user comes from have similar security policies, and whether the user request will be granted under those security policies. The details of this algorithm will be presented in Section 4. Part3) uses a negotiation-based approach to generating a congruous set of security policies which can be accepted by all participating organizations. Participating organizations will first provide their inputs towards the generation of the policies, and then make compromise in order to resolve possible conflicts and reach an agreement. This is used to address possible conflicts which arise from the integration, and to specify new security policies for the resources generated by the collaboration. In both cases, no single organization can claim the sole ownership of the generated resources, and thus no security policies of any participating organization should take priority over those of other organizations. The details of this approach will be presented in Section 5.

4 Similarity-Based Security Policy Integration Algorithm The specification approach presented in the Appendix provides an unambiguous, interoperable security policy specification that is understandable by other participating organizations. To enable collaborations among various collaborating organizations, security policies specified by these organizations need to be integrated to govern the interactions among them during collaboration. It is similar to corporation mergers, where company policies related to labor forces, equipments as well as intellectual properties need to be integrated before the merge can be completed. In such a case, the integration of the policies of different companies is done through negotiation talks between the management and legal departments of the merging companies. However, for dynamic collaborations in ubiquitous computing environments, it is simply not practical if we need to halt the collaboration and get human involvement every time there is an organization join or leave the group of collaborating organizations. In this paper, we present an alternative approach based on policy adaptation and negotiation to achieve dynamic security policy integration with minimum human intervention. During the collaboration, an organization may need to choose to make its resources available to other collaborating organizations so that users from those organizations can access the resources. Even though a collaboration may involve multiple organizations, it is rare that a user belong to two or more of these organizations. In case a user belongs to more than one organization during a collaboration, when that user requests to access a specific resource, we can require the user to specify which organization affiliation he wants to submit this request. This is similar to system administration that a person can be a normal user or an administrator. But, when the user wants to perform system administration tasks, he must sign in as an administrator. So we assume that when a user requests to access a resource, he belongs to only one organization. A general scenario of such pair-wise user-resource access scenario is shown in Figure 2.

Security Policy Integration and Conflict Reconciliation

9

Fig. 2. Pair-wise user-resource integration

There are two organizations OrgA and OrgB. OrgA has its user set UA= {ui, uj, …} and data set DatA ={datAp, datAq …}. A set of security policies PA has been specified to govern the data access behavior in OrgA. Similarly, OrgB has its user set UB, data set DatB, and security policy set PB. The collaboration will not only make existing data available to all the researchers, it may also generate some new data which appears in neither DatA nor DatB. For example, the collaboration can produce a new data datk through analysis of datAq and datBm. We use DatAB to denote the set of the newly generated data. The integrated security policy set should be able to handle all possible data access requests. Let u be the requester and dat be the requested data. There are three types of requests. Type1 consists of C1: dat ∈ DatA , u ∈ UA and C2: dat ∈ DatB , u ∈ UB, where u and dat are in the same organization. Type2 consists of C3: dat ∈ DatB , u ∈ UA and C4: dat ∈ DatA , u ∈ UB, where u and dat are in different organizations and the original security policies specified by the data owner cannot cover the new users from the other collaborating organization. Type3 is C5: dat ∈ DatAB, u ∈ UA ∪ UB, where dat is newly generated data and both collaborating organizations can claim ownership of the data. For Type1 requests, the corresponding original security policies in PA and PB apply. For Type3 requests, the policy integration needs to generate a new security policy to address the security concerns from both organizations. To generate such policies, similar to a conflict reconciliation process, we take the security concerns of the newly generated data from both organizations, and through a negotiation process, a common set of policies accepted by both organizations can be generated. The negotiation process will be discussed in Section 5.

10

S.S. Yau and Z. Chen

For Type2 requests, we will present a similarity-based security policy adaptation algorithm for generating integrated policies. This type of requests does not have existing security policies because the request and the resource belong to different organizations. Original security policies specified by the data owner cannot cover the new users from the other collaborating organization, and the collaborating organization does not have policies to govern the access to data not belonging to the organization. However, because one organization is the only owner of the data, the organization should control the generation of new security policies to address the new users of the data. To deal with this type of requests, adapting the existing security policies of the organization, which owns the data, to handle the new user set, is better than negotiation with the other organization. Because the data owner may have little knowledge about a requester which is not part of its original user set, it is difficult for the data owner to know how to adapt its security policy accordingly. However, it is very difficult to adapt existing security policies to address the new users without heavy human intervention, Because an organization may have specified a list of hundreds or even thousands security policies for its shared resources, it will greatly reduce the efficiency of the collaboration and easily cause human errors due to the large number of requests, On the other hand, even though the organization having the new requestor does not have a security policy to govern the access to this resource, it is often that there are some security policies for this requestor to access some resources similar to the resource it currently requests for accessing. For example, a user u ∈ UB wants to access the raw medical data dat1 ∈ DatA, which contains patients’ SSN. OrgA does not have existing security policy to cover u. If OrgA knows that u can access dat2 ∈ DatB, which contains patients’ mental evaluation results, medication history, and other sensitive information, it is reasonable for OrgA to draw the conclusion that u is trusted to handle sensitive data in OrgB. It is less risky to extend the access of dat1 to u compared to some other user u’ from the same organization which does not have such kind of access rights. Based on this observation, we can develop the following policy adaption algorithm based on policy similarity evaluation. We first need to define a metric for the similarities among different entities. Because our security policy specification is based on a vocabulary organized in a hierarchical structure [3], relative relations between various elements in security policies specifications can be established. Let e1, e2, and e3 be any three elements, e4 be the lowest common ancestor of e1 and e2 in the hierarchical structure, and e5 be the lowest common ancestor of e1 and e3. Element e1 is said to be closer to e2 than to e3 if e4 appears at a lower level in the class hierarchy than e5. The similarity index SI(ei , ej) between two elements ei and ej, is defined as follows:

{

SI (ei , e j ) =

1 if ei = e j SI (ek , e j ) / n if e j is ei 's ancestor, where n is the number of siblings e1 has and ek is ei 's parent SI (ei , el ) × SI (e j , el ) for all other cases, where el is the lowest common ancester of ei and e j

For example, e1:“SHA-1”is a child of e4:“Hash Function”. e2:“MD5” is also a child of e4. e3:“Fingerprint checking” is a child of e5: “Biometric Authentication” mechanism. Both e4 and e5 are derived from e6: “SecurityMechanism”. If these are all the elements in this example, then the similarity between e1 and e2, and between e1 and e3 can be calculated as follows:

Security Policy Integration and Conflict Reconciliation

11

SI(e1 , e2)= SI(e1 , e4) × SI(e2 , e4)=(1/2)×(1/2)=0.25, SI(e1 , e3)= SI(e1 , e6) × SI(e3 , e6)=((1/2)/2)×(1/2)=0.125. SI(e1 , e2) > SI(e1 , e3), which is in line with the fact that “SHA-1” is closer to “MD5” compared to “Fingerprint checking”. The similarity between two atomic security policies, P= (S, A, O, C) and P’ = (S’, A’, O’, C’), is defined as follows: SI(P, P’) = SI(S, S’) × SI(A, A’) × SI(O, O’) × SI(C, C’). The similarity between a composite security policy P = (P1∧P2) ∨ P3∨ ~P4 and an atomic security policy P’ is defined as follows: SI(P, P’)= (SI(P1, P’)× SI(P2, P’))+ SI(P3, P’)+(- SI(P4, P’)). The candidate policy for adaption can be a composite security policy. When searching for similar policies for the request in the collaborating organization, we only search for the atomic policies related to the requester. If there is a composite security policy, we can treat it as several atomic policies during our similarity calculation. Thus, we do not define the similarity between two composite security policies. Based on these definitions, our similarity-based security policy integration algorithm allows the data owner to make the decisions on whether to grant access to a requester from a participating organization based on similarity analysis of the two organizations’ security policies. Let P be the security policy specified by the data owner for a specific data dat. Let TS be a similarity threshold the data owner specified. A security policy P’ in the collaborating organization is selected by the data owner to help it make security decision only if SI(P, P’) is greater than TS. A greater TS will guarantee the selected policies to be closer to P, but if the selection criteria is too tight, it may not be able to return any policy which is certainly not the purpose of this process. The similarity-based security policy adaptation algorithm can be presented as follows: Input: a request where dat  DatA , u  UB Process: 1) Based on the request action and current situation, find the suitable policy, PA, in OrgA which is used to handle this kind of request if the user is from OrgA. 2) Find PS(u), which is the set of atomic policies regarding the requester u in OrgB. 3) For every P in PS(u), calculate SI(PA, P) 4) Select a subset PS’(u) of PS(u), where for every P in PS’(u), SI(PA, P) > TS 5) Divide PS’(u) into two subsets, PSP(u) and PSD(u), where PSP(u) is the set of rules that permit access for u, and PSD(u) is the set of rules that deny access for u. SI ( PA , P) ¦ SI ( PA , P)  P¦ PPSP ( u ) PS D ( u ) 6) Calculate R u W , where W is a confidence min( SI ( PA , P), P  PS '(u )) weight OrgA assigned to OrgB. W is originally set to 1, and every time if OrgA grants access for a user in OrgB based on this calculation and the user does not cause any security problem, W is increased by 1. On the other hand, if the user failed to meet the expectation, W is decreased by 1. Output: If R > 1, the request is granted, otherwise it is denied.

12

S.S. Yau and Z. Chen

The original similarity threshold can be generated based on sampling result of the collaboration with domain knowledge. If on the average, every node has N children, two policies with a similarity index in the range N-3 ~ N-4 are considered to be similar. At runtime, the threshold can be updated based on previous evaluation results to make it more suitable for a specific collaboration. The advantage of this approach is that this process can be automated and very efficient.

5 Negotiation-Based Conflict Reconciliation Protocol We consider two security policies P1 and P2 have conflict with each other if for their satisfactory sets Q1 and Q2, there exists an element e such that e ∈ Q1 and e ∈ Q2 , where Q1 and Q2 are satisfactory sets for P1 and P2 respectively, which contain all the elements that comply with their corresponding policies. As discussed in Section 1, due to the dynamic nature of collaborations among organizations in ubiquitous computing environments, when specifying its own security policies, an organization has difficulties in knowing what security policies have specified by other organizations which may collaborate with in the future. Thus, for a complex system, conflicts are hard to avoid. It is important that the collaborations do not undermine the security of all participating organizations. On the other hand, security should not deny participating organizations the possibility of collaboration simply because there exist some conflicting security policies. Our conflict reconciliation protocol can improve the collaboration chance. It is based on the following observations of real world scenario: it is difficult to find suitable collaborator and collaboration can generate extra synergies. Thus, instead of rejecting a possible collaborator because of some conflicting security policies, collaborating organizations often prefer to take certain risk and move forward with the collaboration by relaxing their security policies and adopting some weaker security policies to resolve the conflicts. Policy P1 is said to be weaker than P2 if P1 a Q1, P2 a Q2, and Q2 ⊂ Q1. Because each collaboration goal and collaborating participants may be different, the security compromise should not be done in a static manner. Our reconciliation protocol captures these dynamic factors as situation-aware compromise thresholds, which specify how much compromise an organization is willing to make for a specific collaboration. A compromise threshold, TC, is specified based on the following factors: (1) How much benefit can be generated if this collaboration goes through? (2) How much damage it may cause by adopting a weaker security policy? (3) What is the track record of this specific collaborating organization? How did it perform in pervious collaborations? The value of Tc should be updated when the above three factors change. Now, we will present the negotiation-based conflict reconciliation protocol as follows:

Security Policy Integration and Conflict Reconciliation

13

Step1 For a specific resource, each organization specifies a chain of security requirements instead of just one security requirement. The head of the chain is the most desirable security policy. Traveling through the chain from the head, the security requirements become weaker and weaker. Step2 Each organization specifies compromise thresholds under various situations as (TC,T), which means when situation T is true, the weakest security policy it is willing to take is indexed by TC along the chain. Step3 At runtime, the system obtains the compromise thresholds TC1 and TC2 for both organizations based on the current situation, and identifies the index for the two conflict policies in their chain. Test to see whether the current index is less than the compromise threshold. If not, go to Step6. Step4 One organization is randomly selected to make compromise first, and proceeds along the policy chain to select a weaker policy; Step5 Test whether there is still any conflict. If no conflict is detected, then reconciliation is done. If there is still conflict, repeat Step4 by proceeds along the other organization’s policy chain. Step6 Both organizations make compromise in turns, until one of the compromise thresholds is reached. If no reconciled policy is generated by then, failure is reported for human intervention.

For two conflict policies P1 and P2, the above steps can be summarized in the following pseudo-code. // sp1[] is the policy chain contains P1, and sp2[] is the policy chain contains P2 x1 = GetCompThreshold1(θ ); x2 = GetCompThreshold2(θ ); n1 = Sizeof(sp1); n2 = Sizeof(sp2); flag = 0; for (p=0, q=0; p≤n1, q ≤ n2; ) { if ((sp1[p] not conflict with sq2[q]) substitute P1 with sp1[p] and P2 with sp2[q], break; else{ if(flag == 0){ p++; flag = 1; }else{ q++; flag = 0; } } } if (p > n1 || q > n2) report the conflict cannot be automatically reconciled For the sake of simplicity, we only illustrate the reconciliation process between two collaborating organizations. The reconciliation process involving more than two organizations can be handled in a similar fashion: We will have multiple security policy chains and the compromise may be made in a loop circling all participating organizations, instead of going back and forth between two organizations.

14

S.S. Yau and Z. Chen

6 An Illustrative Example In this section, we will give an example to illustrate our approach. Continuing with the scenario described in Section 4, a university OrgA and a pharmaceutical company OrgB collaborate on a joint vaccine development project. UA is made up of a set of professors (UP), a set of graduate research assistants (UG) and a set of undergraduate students (UU). DatA includes some research papers (datAp), unpublished experiment results and paper drafts (datAo), and composition data on several promising chemicals, which the users in UA intend to use (datAq). UB consists of a set of research scientists (US), a set of lab technicians (UT) and several directors for research (UD). DatB includes patents of existing drugs related to this disease (datBn), a list of potential clinical trial participants (datBr), and a set of secret methods for fast vaccine prototype development (datBm). These users and data can be organized in a hierarchical manner as shown in Figure 3. Entity Is a

Is a

Resource

User

Is a

Data

Is a

dat Ap

Is a

Confidential Info

Is a

dat Bn

Is a

dat Ao

UD

dat Aq

Is a

Participant Is a

UG

Is a Is a

Is a

Supervisor

Is a

Is a

Pub Info

Is a

Is a Is a

Volunteer

Investigator

Is a

Is a

UU

Is a

UT

dat Bm

UP

Is a

US

DatBr

Fig. 3. The hierarchy of concepts of the example

To follow our approach, Part1), we have the following security policies specified: OrgA – (1) All members can access the published papers at anytime. P1: (UP ∪ UG ∪ UU, Access, datAp, __ ) (2) Professors can always access and modify the unpublished paper draft. P2: (UP, Access∪Modify, datAo, __ ) (3) Graduate assistants can always access the unpublished paper draft. However, they can only update the draft if they are the co-authors. P3: (UG, Access, datAo, __ ) ∧ (UG, Modify, datAo, C3), C3: Up ⊂ Author(datAo) OrgB – (1) All members can access the drug patents at anytime. P4: (UD ∪ US ∪ UT, Access, datBn, __ ) (2) Scientists and directors can access the trial participant list. P5: (UD ∪ US, Access, datBr, __ ) (3) Only directors can update the trial participant list. P6: (UD, Modify, datAo, __ )

Security Policy Integration and Conflict Reconciliation

15

Part 2), if a professor u from OrgA wants to access the list of trial participants, OrgB’s current policies cannot handle this request. Follow our similarity-based algorithm, we have 1) Because the request is to access datBr, P5 is the suitable policy for similarity comparison. We can transform P5 into P5’:(UD, Access, datBr, __ ) ∨ P5’’:(US, Access, datBr, __ ) 2) Select policies for professors in OrgA. We only consider the atomic component for professors if the policy also applies to other users. Thus, PS(u) = { P1’:(UP, Access, datAp, __ ), P2’:(UP, Access, datAo, __ ), P2’’:(UP, Modify, datAo, __ )}. 3) SI(P5, P1’) = SI(P5’, P1’) + SI(P5’’, P1’). SI(P5’, P1’) = SI(UD, UP) × SI(Access, Access) × SI(datBr, datAp) × SI( __, __) = 1/32 × 1 × 1/32 × 1 = 1/1024. Similarly, SI(P5’’, P1’) = 1/16. Thus SI(P5, P1’) = 65/1024. We can also calculate SI(P5, P2’) = 9/128, and SI(P5, P2’’) = 9/3200. 4) For this example, assume that OrgB sets the threshold Ts = N-4. Because on the average every node has 3 children, Ts = 1/81, and hence both P1’ and P2’ are selected. 5) Both P1’ and P2’ grant access to u, thus PSP(u) = { P1’ , P2’ } and PSD(u) = φ 6) Assume that this is the first time the two organizations collaborate. Then, W =1. R = (SI(P5, P1’)+ SI(P5, P2’)) / min (SI(P5, P1’), SI(P5, P2’)) = (65/1024+9/128) / min(65/1024, 9/128) = 137/65. Because R > 1, the access is granted to u. The system can make this decision automatically without any human supervision at runtime. Because professors in OrgA are the main contributors (Investigators) for this project, and professors can access confidential information in OrgA, it is reasonable for a human supervisor in OrgB to grant a professor from OrgA the access to the participant list. This decision is in line with the real world situation. Part3), since negotiation is used for conflict reconciliation as well as security policy generation for newly generated resources, we only need to show an example of the latter to illustrate this negotiation process. Assume that based on datAq, the collaboration developed several vaccine prototypes using the methods listed in datBm, and performed several clinical trials. We will have a new set of data datk which is the evaluation results of these vaccine prototypes. Neither OrgA nor OrgB can claim the ownership of datk completely. Thus, a security policy for datk will be generated through negotiation. Following our negotiation protocol discussed in Section 5, for this example, Step 1. OrgA presents its list of input policies sp1[], with the most desirable policy for at front. OrgB also presents its inputs sp2[]. Step 2. Both OrgA and OrgB specify their compromise thresholds for various situations as (TC,θ) pairs. Step 3. After analyzing the collaboration history and the importance of the data, the compromise thresholds for both organizations are 2. In the following we only list the input policies up to the threshold.

16

S.S. Yau and Z. Chen

OrgA: (1) Only investigators can access datk through a communication channel using 64-bit encryption. sp1[0]: (UI, Access, datk, “64-bit encryption” ) (2) Both investigators and participants can access datk through a communication channel using 64-bit encryption. sp1[1]: (UI ∪ UPa, Access, datk, “64-bit encryption” ) (3) Both investigators and participants can access datk. sp1[2]: (UI ∪ UI, Access, datk, __ ) OrgB: (1) Both investigators and participants can access datk through a communication channel using 128-bit encryption. sp2[0]: (UI ∪ UPa, Access, datk, “128-bit encryption” ) (2) Both investigators and participants can access datk through a communication channel using 64-bit encryption. sp1[1]: (UI ∪ UPa, Access, datk, “64-bit encryption” ) (3) Anyone in the collaboration can access datk. sp2[2]: (U, Access, datk, __ ) Both organizations start with their first choice, sp1[0] and sp2[0]. Obviously, there is a conflict since sp1[0] allows less investigators to access datk while sp2[0] grant access to both investigators and participants. Step 4. OrgA is randomly selected to initialize the negotiation. It will proceed along the input policy list and present the next policy sp1[1] which is weaker than sp1[0]. Step 5. After analyzing sp1[1] and sp2[0], there is still a conflict since sp2[0] requires access through 128-bit encryption while sp1[1] only requires 64-bit encryption. Hence, Step 4 is repeated. This time, OrgB needs to make its compromise in the negotiation process. The next policy in its input list, sp2[1], is presented. Step 6. After analysis, no conflict is found between the two input policies sp1[1] and sp2[1], and hence a security policy for datk is generated: (UI ∪ UPa, Access, datk, “64-bit encryption” ) Note that we have not reached the compromise threshold. Though there is no conflict between sp1[2] and sp2[2] either, the negotiation process stops as soon as a pair of non-conflict policies is found because they are stronger than the policies appearing later in the list. This will provide the best protection for the collaboration system without creating any conflict.

7 Conclusions and Future Work In this paper, we have presented an approach to security policy integration and conflict reconciliation for collaborations among organizations in ubiquitous computing environments. Based on the similarities between security policies, a resource owner can adapt its existing security policies to cover the new users from collaborating organizations using the similarity indices as a selection criterion for selecting similar policies in the collaborating organization and make a decision based on their inputs. Collaborating organizations with conflicting security policies can try to resolve the conflicts by gradually making security compromise and relaxing their security

Security Policy Integration and Conflict Reconciliation

17

policies until either the conflict is resolved or the conflict reconciliation process reaches certain compromise threshold associated with that particular collaboration. This approach can also be used for generating security policies for the new resources generated as a result of the collaboration, where all participating organizations specify their security concerns for the resource, and the negotiation process is trying to find a common set of policies that will satisfy all the organizations’ concerns. We plan to conduct case studies to establish some applicable guidelines for specifying the similarity threshold and updating the confidence weight in the decision making process. In addition, we will investigate the impact of extending the security policy set through logical reasoning and try to associate that impact with policy similarity so that we can update the resource owner’s security policies based on the similarity analysis, rather than relying on similar security policies specified by the collaborating organizations.

References [1] Xu, F., Lin, G., Huang, H., Xie, L.: Role-based Access Control System for Web Services. In: Proc. 4th Int’l Conf. on Computer and Information Technology, pp. 357–362 (2004) [2] Bhatt, R., Joshi, J.B.D., Bertino, E., Ghafoor, A.: Access Control in Dynamic XMLBased Web Services with XRBAC. In: Proc. 1st Int’l Conf. on Web Services (2003), http://www.sis.pitt.edu/~jjoshi/ICWS_XRBAC_Final_PDF.pdf [3] Yau, S.S., Chen, Z.: A Framework for Specifying and Managing Security Requirements in Collaborative Systems. In: Yang, L.T., Jin, H., Ma, J., Ungerer, T. (eds.) ATC 2006. LNCS, vol. 4158, pp. 500–510. Springer, Heidelberg (2006) [4] OASIS, eXtensible Access Control Markup Language (XACML) Version 2.0, OASIS standard (2005), http://docs.oasis-open.org/xacml/2.0/ access_control-xacml-2.0-core-spec-os.pdf [5] Bonatti, P.A., Sapino, M.L., Subrahmanian, V.S.: Merging Heterogeneous Security Orderings. In: Martella, G., Kurth, H., Montolivo, E., Bertino, E. (eds.) ESORICS 1996. LNCS, vol. 1146, pp. 183–197. Springer, Heidelberg (1996) [6] Bidan, C., Issarny, V.: Dealing with Multi-policy Security in Large Open Distributed Systems. In: Quisquater, J.-J., Deswarte, Y., Meadows, C., Gollmann, D. (eds.) ESORICS 1998. LNCS, vol. 1485, pp. 51–66. Springer, Heidelberg (1998) [7] Backes, M., Durmuth, M., Steinwandt, R.: An Algebra for Computing Enterprise Privacy Policies. In: Samarati, P., Ryan, P.Y.A., Gollmann, D., Molva, R. (eds.) ESORICS 2004. LNCS, vol. 3193, pp. 33–52. Springer, Heidelberg (2004) [8] Ribeiro, C., Zuquete, A., Ferreira, P.: SPL: An access control language for security policies with complex constraints. In: Proc. Network and Distributed System Security Symp (NDSS 2001), pp. 89–107 (2001) [9] Lupu, E., Sloman, M.: Conflicts in policy-based distributed systems management. IEEE Trans. on Software Engineering 25(6), 852–869 (1999) [10] Agrawal, D., Giles, J., Lee, K.W., Lobo, J.: Policy ratification. In: Proc. 6th IEEE Int’l Workshop on Policies for Distributed Systems and Networks (POLICY), pp. 223–232 (2005) [11] Yau, S.S., Huang, D., Gong, H., Yao, Y.: Support for Situation-Awareness in Trustworthy Ubiquitous Computing Application Software. J. Software Practice and Engineering 36(9), 893–921 (2006)

18

S.S. Yau and Z. Chen

Appendix Ontology-Based Security Policy Specification Our approach uses ontology-based security policy specification language in [3]. For the sake of completeness, we summarize the important features of the specification language. Natural language security policy specifications can be expressed by a set of logic expressions with the key vocabulary derived from a hierarchical security policy ontology. The ontology is shown in Fig. 4, where the generic classes in the core ontology are defined as follows: • SecurityPolicy can be an AtomicSecurityPolicy or CompositeSecurityPolicy. • CompositeSecurityPolicy is composed of AtomicSecurityPolicy. • AtomicSecurityPolicy has four components: Subject, Object, Action and Condition. • Both Subject and Object are Entity. • Entity can be User or Resource, and Data is also considered as Resource. • Action specifies what action Subject can perform on Object, which includes Access, Share, Delegate, Delete and Modify. • Condition can be specified as a specific SecurityMechanism, which must be adopted, or as a certain environment or system Situation, which will trigger the security policy. The value of a Situation expression is determined by situationaware processors [11].

Security Policy

compose

Is a

Is a

Composite Security Policy

Has

Atomic Security Policy

Has

Subject Is a

Is a

Condition

Has Has Is a

Action

Is a

Resource

Is a

Is a Is a

User Is a

Data

Is a

Security Mechanism

Object

Entity

Is a

Access

Is a

Share

Situation

Is a

Modify

Delegate Delete

Fig. 4. An ontology for security policy specification

This ontology provides the fundamental vocabulary for specifying security policies. However, users can extend the basic concepts and introduce more applicationspecific terms when specifying their own security policies. The basic building block is the atomic security policy, which can be specified as a quadtuple: P = (S, A, O, C), where S ⊂ Subject, A ⊂ Action, O ⊂ Object, and C ⊂ Condition. The quadtuple is interpreted as follows: Security policy P specifies that a set of subjects S can perform

Security Policy Integration and Conflict Reconciliation

19

a set of actions A on a set of objects O when a set of conditions C is met. A request is granted if there exists a policy P = (S, A, O, C) such that the requester s ∈ S, the requested action a ∈ A, the requested target o ∈ O and the conditions listed in C are satisfied when the request is made. If C is omitted, it means the policy applies to all conditions. Atomic security policies can be composed through logic operators conjunction ‘∧’, disjunction ‘∨’ and negation ‘¬’ to form more complex security policy specifications. Based on these definitions, for a give set of security policies, we can derive a satisfactory set Q which contains all the elements that comply with the given set of policies. We use P a Q to denote this logic reasoning process. This specification approach has two advantages. First, because all four elements within a specification are specified based on the ontology, each element is clearly defined. There is only one interpretation for a quadtuple, and thus a specified security requirement is unambiguous. Second, the hierarchical structure of the ontology can be used to establish common understanding of different terms used by different organizations in their security policy specifications. For example, one policy specifies “administrator can only access the account information through a 128-bit encrypted channel”, and the other policy specifies “administrator must use a 128-bit encrypted channel to access the username/password information”. Based on the ontology we used in our specifications, both “account information” and “username/password information” are Objects. If the two collaborating organizations establish a common understanding that “username/password” used by OrgA is the “account information” used by OrgB, the system will be able to “understand” this fact and process the policies from both organizations based on this fact accordingly. In this example, the two security policies will be treated as the same policy. The algorithm to bridge different terms used by different organizations and form common understandings was presented in [3].

Improved Weighted Centroid Localization in Smart Ubiquitous Environments Stephan Schuhmann1 , Klaus Herrmann1 , Kurt Rothermel1 , Jan Blumenthal2 , and Dirk Timmermann2 1 University of Stuttgart, Germany Institute of Parallel and Distributed Systems (IPVS) {firstname.lastname}@ipvs.uni-stuttgart.de 2 University of Rostock, Germany Institute of Applied Microelectronics and CE {jan.blumenthal,dirk.timmermann}@uni-rostock.de

Abstract. Location-awareness is highly relevant subject in ubiquitous computing, as many applications exploit location information to provide adequate services or adapt to a changing physical environment. While GPS provides reliable outdoor localization, indoor positioning systems present a bigger challenge. Many indoor localization systems have been proposed. However, most of them rely on customized hardware or presume some dedicated infrastructure. In this paper, we focus on WLAN-based localization in smart ubiquitous environments. We propose an improved scheme of the Weighted Centroid Localization (WCL) algorithm that is robust and provides higher location accuracy than the original WCL algorithm. The improvements are based on the use of dynamic weighting factors that are solely dependent on the correlation of the Received Signal Strength Indicators of the received beacon signals. Compared to the original WCL scheme, our approach does not increase requirements to the environment. Real-world experiments in a typical environment that we report on in this paper confirm that the increased location accuracy determined in previous calculations is reproducible in a realistic noisy environment. This provides a simple, cost-efficient, and battery-conserving, but yet adequate technique for getting the accurate location information of mobile devices.

1

Introduction

Location-awareness is an essential service for many wireless ubiquitous computing scenarios, as many applications integrate location information to increase context knowledge. However, ubiquitous computing environments have specific characteristics which limit the approaches that are applicable to maintain location-awareness. For instance, pervasive applications have to deal with fluctuating availability of devices due to mobility and network failures. Thus, environmental contexts are highly dynamic. Furthermore, processor performance and available energy of mobile nodes in ubiquitous computing scenarios are often limited. Therefore, intensive communication and computation tasks are not F.E. Sandnes et al. (Eds.): UIC 2008, LNCS 5061, pp. 20–34, 2008. c Springer-Verlag Berlin Heidelberg 2008 

Improved Weighted Centroid Localization

21

feasible. In this context, algorithms are subject to strict requirements covering reduced memory consumption, communication, and processing time. In Smart Environments, available infrastructure devices can provide additional support for mobile devices. Determining the position of nodes in wireless networks, particularly in noisy environments, represents a real challenge. To identify the exact coordinates of a device (also called Station Of Interest, or SOI ) requires measuring a distance, e.g., measuring Time of Arrival (ToA) or Time Difference of Arrival (TDoA). Difficulties concerning time measurements result from synchronization of involved devices as well as the high computational effort to calculate the position. Measuring the Received Signal Strength Indicator (RSSI) offers a possibility to realize distance determination with minimal effort. A good localization algorithm should calculate a position as fast as possible and should be resistant to environmental influences as well as imprecise distances. However, it is desirable to use standard off-the-shelf consumer products without the necessity for far-reaching customization as this reduces the effort necessary for setting up the positioning system. Thus, our approach of combining the Weighted Centroid Localization (WCL) [1] with standard Wireless LAN technology has high practical relevance in typical environments. The main contribution of this paper is an improved Weighted Centroid Localization scheme that uses weighting factors of dynamic degrees to increase location accuracy in smart ubiquitous environments. Therefore, we derived optimal dynamic weighting factors through theoretical calculations and approximated the obtained weighting factors by a power function using the least-squares method. Furthermore, we evaluated the improved localization scheme in an office room that represents a typical noisy ubiquitous computing environment. The measurements confirmed that our approach increases location accuracy almost to the best possible value for weighted centroid schemes. The paper at hand is divided into six sections. The second section discusses the requirements to be met by the localization scheme and the environment. Section 3 gives a broad survey of existing localization approaches. In Section 4, we at first describe the original WCL scheme. Following, we derive an improved WCL scheme that uses dynamic weighting factors and increases location accuracy. We present our theoretical and practical evaluation results in Section 5. This is followed by the conclusion and a brief outlook to future work in Section 6 which closes this paper.

2

Requirements

In this paper, we focus on indoor localization for resource-restricted devices in smart ubiquitous environments. This requires to avoid high battery consumption, as mobile devices like PDAs or smart phones are equipped with limited battery and computation power. Hence, we aim at minimizing the requirements for the localization devices as well as the infrastructure to allow applicability to a wide

22

S. Schuhmann et al.

range of scenarios. This means we want to provide a flexible solution for indoor localization. Thus, our system has to maintain the following properties: – Minor Environmental Requirements: The environment solely has to provide infrastructure nodes with fixed positions that send periodic beacon signals. Many realistic ubiquitous scenarios fulfill this property, as they include 802.11 WLAN Access Points (APs), for example. These devices have to know their exact position and notify other devices of their location, e.g. within the beacon signals which needs slight adaptations to the APs. If changes to the APs are undesired, AP positions can be received by queries to a location server that provides the clients with AP locations. – Minimal Costs: Additional hardware costs should be avoided by relying on standard components that are available in typical ubiquitous scenarios, both on the client and on the infrastructure side. For instance, the localization scheme ought to integrate existing infrastructure devices without the need of large changes in their configuration. To minimize costs, we rely on exactly four beacon nodes in this paper. These beacons are placed at the edges of a rectangular plain, as common rooms typically have a rectangular base. This AP positioning enables nodes to localize themselves in the whole region. – Minimal Communication Needs on the Client Devices: Since power supply is critical for small mobile devices, the clients should avoid any additional communication during the localization process to maximize battery lifetimes. So, only the infrastructure devices should send beacons needed for the localization process, while the mobile devices have to exploit the information provided by these beacons. As localization is supposed to be executed in various scenarios in real-time, a solution that demands prior configuration of the client devices is not feasible, as this limits the use of the system. – Applicability in Realistic Ubiquitous Scenarios: Contrary to laboratory environments, realistic scenarios often suffer from effects like multi-path propagation or interferences with other wireless networks operating on the same frequency spectrum. This can significantly influence the accuracy of the localization. A localization scheme must be able to cope with this interference in order to provide accurate localization nevertheless.

3

Related Work

In this section, we investigate several related localization approaches concerning the above requirements to confine WCL from these approaches, and we clarify why they prove inadequate in our scenarios. In Figure 1, we provide a classification of proposed schemes. At first, these schemes can be divided into those that are based on coordinates and those that are coordinate-free. Coordinate-free schemes, as presented by Fekete et al. [2], focus on an abstract way of location-awareness. These schemes aim at achieving consistent solutions by the use of geographic clustering. Unfortunately, they rely on rather dense sensor networks to achieve adequate accuracy and, therefore, are not usable here. Thus, we focus on coordinate-based approaches that can further be divided into

Improved Weighted Centroid Localization

23

Fig. 1. Classification of proposed localization schemes

range-free and range-based schemes. Range-free schemes comprise implicit distance measurements, while range-based schemes use explicit distances for localization. Regarding range-free schemes, there exist three main approaches: – Anchor-based approach: This approach uses anchor beacons, containing two-dimensional location information (xi , yi ), to estimate node positions. After receiving these beacons, a node estimates its location using a specific formula. Besides a scheme proposed by Pandey et al. [3], another anchorbased approach is Centroid Localization (CL), proposed by Bulusu et al. [4]. In this approach, the SOI calculates its position as the centroid of the coordinates from the stations whose beacons are received. While CL performs only averaging the coordinates of beacons to localize SOIs, the Weighted Centroid Localization (WCL) algorithm [1] uses weights to ensure an improved localization and, hence, represents a direct advance over CL. – Hop-based approach: In this type of localization scheme, the SOI calculates its position based on the hop distance to other nodes [5],[6]. This scheme delivers an approximate position for all nodes in networks where only a limited fraction of nodes have self-positioning capability. Through this mechanism, all nodes in the network (including other anchors) get the shortest distance, in hops, to every anchor. However, this approach only works well in dense networks and relies on flooding of messages which produces high communication overhead that is undesired in our scenarios. – Area-based approach: Area-based schemes [7],[8] perform location estimation by isolating the environment into triangular regions between beaconing nodes. The presence inside or outside of these triangular regions allows a node to narrow down the area in which it can potentially reside. Area-based approaches normally perform particularly well in heterogeneous networks with high node density. Unfortunately, this condition does not hold in our case and, thus, area-based approaches cannot be used here.

24

S. Schuhmann et al.

Besides range-free schemes, a couple of approaches exist that are based on the transmission ranges of the nodes. Range-based approaches can be subdivided into the following approaches: – Signal Propagation Time: The Time of Arrival (ToA) technology is commonly used as a means of obtaining range information via signal propagation time. This approach is used by satellite navigation systems [9]. Though this approach guarantees high precision and can be globally used, it suffers from several major drawbacks as this scheme can only be used outdoors, needs expensive hardware, and the receivers consume much energy. Thus, ToA approaches are inapplicable in our case. – Localization by Measuring Signal Propagation Time Differences and Arrival Angles: This technology is based on measurements of the Time Difference of Arrival (TDoA) [10], or the Angle of Arrival (AoA) [11]. While TDoA estimates the distance between two communicating nodes (this is also called ranging), AoA allows nodes to estimate and map relative angles between neighbors. Like ToA technology, TDoA and also AoA rely on special hardware that is expensive and energy consuming. Thus, these approaches are unsuited here. – Simple Signal Strength Measurements: This approach uses the Received Signal Strength Indicator (RSSI) of incoming beacon signals and has been proposed for hardware-constrained systems. Contrary to techniques like ToA, TDoA or AoA, RSSI is the only feature that is measurable with reasonably priced current commercial hardware. RSSI techniques use either theoretical or empirical models to translate signal strengths into distance estimates where each point is mapped to a signal strength vector [12], or to a signal strength probability distribution [13]. This technology suffers from problems such as background interference or multi-path fading which make range estimates inaccurate, as shown in [14]. Furthermore, many signal strength based approaches rely on special hardware, like small infrared badges [15], magnetic trackers [16], or multiple cameras [17], which usually are not included in typical environments and mobile devices. Some approaches do not use client-based, but sniffer-based localization [18]. However, this technique cannot be used here as it assumes that the access points can localize other devices which induces major changes in the APs. Many approaches use location fingerprinting for localization in wireless networks [12],[13]. This method consists of a training phase and a positioning phase. Unfortunately, this approach needs additional preconditioning and the creation of a training database for several environments beforehand, which makes it inapplicable in our case. In summary, one can see that most approaches cannot be chosen since they rely on extensive special hardware, need additional preconditioning to build a training database, use sniffer-based localization, or depend on high node densities to perform well. This narrows the huge field of localization schemes down to few anchor-based approaches. Among those, Weighted Centroid Localization uses more fine-grained parameters than CL to weight the received beacon signals, as

Improved Weighted Centroid Localization

25

CL simply uses binary weighting (weight 1 for those APs whose beacons were received, weight 0 for the others). This ensures higher location accuracy for WCL.

4

Improved Weighted Centroid Localization

After a short introduction to the original WCL scheme with static weighting factors [1], we propose an advanced scheme that uses dynamic weighting factors which are based on the correlation of the received RSSI values. 4.1

Static Degree Weighted Centroid Localization (SWCL)

We assume that the network consists of SOIs that want to localize themselves, and n beacons. In our case, beacons are WLAN access points whose position is assumed to be known exactly. We depend on a small number of n = 4 beacons, placed at the edges of a rectangular plain. The SOIs are mobile devices that initially do not know their own position. Algorithms such as CL use centroid determination to calculate a device’s position [4]. In the first phase, each beacon Bj sends its position (xj , yj ) to all nodes within its transmission range, which can simply happen through the periodically sent beacon signals. In the second phase, the SOI Pi calculates an approximation (xi , yi ) of its real position (xi , yi ) by a centroid determination from all n positions of the beacons in range (1). 1 (xj , yj ) n j=1 n

(xi , yi ) =

(1)

The localization error fi for the SOI Pi is defined as the distance between the exact position (xi , yi ) and the approximated position (xi , yi ) of Pi (2).  fi = (xi − xi )2 + (yi − yi )2 (2) While CL only averages the coordinates of beacon devices to localize SOIs, WCL uses weights to ensure an improved localization. In CL, all weights of received beacon signals are implicitly equal to 1. WCL represents a generalization of this scheme since it introduces variable weights wij for each device Pi and each beacon Bj . These weights depend on the distance between the two as it will be explained later in this section. In the more general WCL equation, the number of beacons n is replaced by the sum of weight factors wij , and each beacon position (xj , yj ) is multiplied by its weight factor wij . Hence, (1) is expanded to the WCL formula (3) yielding the new approximation (xi , yi ) for Pi ’s position. n j=1 wij · (xj , yj )   n (xi , yi ) = (3) i=1 wij The weight wij is a function depending on the distance and the characteristics of the SOI’s receivers. In WCL, shorter distances cause higher weights. Thus, wij

26

S. Schuhmann et al.

and dij (the distance between beacon Bj and SOI Pi ) are inversely proportional. As an approximation, the correlation is equivalent to the function 1/dij . To weight longer distances marginally lower, the distance is raised to a higher power hs . For a concentric wave expansion with a linear characteristic of the receiver and a uniform density of the beacons, we form (4). wij =

1 (dij )hs

(4)

The static degree hs has to ensure that remote beacons still impact the position determination. Otherwise in case of a very high hs , the approximated position moves to the closest beacon’s position and the positioning error fi increases. There exists a minimum of fi where hs is optimal [19]. However, as the next section clarifies, this use of static weight values leads to suboptimal accuracy if you compare it to the use of adapted dynamic weight factors that are based on the correlation between the received RSSIs from several APs. According to Friis’ free space transmission equation (5), the detected signal strength decreases quadratically with the distance to the sender. Prx = Ptx · Gtx · Grx · (

λ 2 ) 4πdij

(5)

Prx = Remaining power of wave at receiver Ptx = Transmission power of sender Gtx , Grx = Gain of transmitter and receiver λ = Wave length dij = Distance between sender and receiver In embedded devices, the received signal strength is converted to the RSSI which is defined as ratio of the received power to the reference power (Pref ). Typically, the reference power represents an absolute value of Pref = 1 mW .  The actually received power Prx can be obtained by the RSSI and vice versa, as denoted in the following equations.  Prx = Pref · 10

RSSI 20

⇐⇒

RSSI = 20 · log10

 Prx Pref

(6)

An increasing received power results in a rising RSSI. Thus, distance dij is  indirect proportional to Prx , and (7) with power gs ( = hs ) is formed.  gs wij = (Prx )

(7)

So, it can be seen that the knowledge of dij is not necessary, as the algorithm  can simply use the received power Prx or, alternatively, the RSSI. In this paper, we use the RSSI, i.e. we take (6) and (7), and form (8). wij = (Pref · 10

RSSI 20

)gs .

(8)

Improved Weighted Centroid Localization

AP3

R1,1 AP1

R1,2

R2,1 l1

AP4 AP1

AP2

a)

l2

AP3

R1,1

R2,2

l1

R2,2

R1,2

R2,1 AP2

27

AP4

l2

b)

Fig. 2. a) Distribution of gopt at a rectangular plain (p = 43 ), b) Potential for improvement of location error at a rectangular plain (p = 43 ), relative to longer side l1

In practical scenarios, the ideal distribution of Prx does not hold, because the radio signal propagation is interfered with many influencing effects, like reflection on objects, diffraction at edges, or superposition of electro-magnetic fields.  Thus, Prx and Prx represent different values which yields localization errors. 4.2

Dynamic Degree Weighted Centroid Localization (DWCL)

Using an optimally chosen static degree gs , as original WCL does, results in improved location accuracy, compared to CL [1]. However, the degree gopt that leads to minimal error can significantly differ from gs in some regions, as this  section will clarify. Therefore, we used (5) and (6), and put Prx = Prx to calculate the expected RSSI in various positions within an idealized region under observation. Following, we used the WCL algorithm with different powers g to determine the optimal gopt which yields highest location accuracy at a particular place in the region. Figure 2a shows the distribution of the factors gopt in a rectangular region where the proportion p of the length l1 of the longer side divided by the length l2 (≤ l1 ) of the shorter side is p = ll12 = 43 . It can be seen that the distribution of gopt is very uneven. The values at the regions R1,1 and R1,2 exactly between two adjacent anchors with a distance of l1 to each other (e.g., AP1 and AP3 ) are relatively high (up to 5.0), as well as at those regions R2,1 and R2,2 between two anchors with a distance of l2 to each other (e.g., AP1 and AP2 ), where the maximum gopt is approximately 2.5. In the special case of a quadratic plain (l1 = l2 , i.e. p = 1), the distribution of gopt is symmetric to the center of the region. By selecting the determined optimal dynamic powers shown in Figure 2a, the mean error could be decreased by about 30 % (compared to WCL with an optimal static weight factor of gs = 0.87 in a region with p = 43 ) to the best possible value for WCL. Thus, it is obvious that there is huge potential for improvements by using dynamic weight factors. Figure 2b shows this potential which represents the difference between the error if gs is used, and the minimum possible error if

28

S. Schuhmann et al.

the optimal gopt is used. This figure clarifies that the potential for improvements is alike very unevenly distributed. Particularly the regions Ri,j (i, j ∈ {1, 2}) offer an enormous potential of more than 10 % of l1 for improvements, which corresponds to the noticeably increased optimal weight factor at these regions, as Figure 2a shows. It is obvious that the influence of the two farthest access points was too high there, as the value of gs was chosen too low. This shifted the calculated position near the centre of the region. The proceeding of DWCL to obtain the optimal dynamic weighting factor gd is the following: At first, the SOI has to identify the approximate subregion it is located in. Then, it has to lookup subregion-specific parameters. Now, the SOI can at first calculate the value of a balancing function and, based on this result, the approximated actual dynamic weight gd and its location within the whole region under observation. We will focus on these steps in the following. Subregion Determination. First of all, a SOI has to determine the approximate subregion in which it is located. This has to happen by solely regarding the RSSIs of incoming beacon signals. Figure 2a suggests to define four different subregions, as there exist four peaks for the optimal values of g. A simple way to divide the region in adequate subregions is using the perpendicular bisectors of the sides from AP1 to AP4 and from AP2 to AP3 , as illustrated in Figure 3. A SOI then can easily determine in which of the emerging subregions C1,1 , C1,2 , C2,1 , and C2,2 it is located. This is performed by simply comparing the RSSIs pairwise, as denoted in Table 1. Table 1. Determination of subregions RSSI constraints

Subregion

(RSSI(AP1 ) > RSSI(AP4 )) ∧ (RSSI(AP3 ) > RSSI(AP2 )) (RSSI(AP4 ) > RSSI(AP1 )) ∧ (RSSI(AP2 ) > RSSI(AP3 )) (RSSI(AP1 ) > RSSI(AP4 )) ∧ (RSSI(AP2 ) > RSSI(AP3 )) (RSSI(AP4 ) > RSSI(AP1 )) ∧ (RSSI(AP3 ) > RSSI(AP2 ))

C1,1 C1,2 C2,1 C2,2

Determination of Subregion-Specific Parameters. After determining the subregion it is located in, a SOI needs to obtain further parameters which we will derive in this paragraph. Regarding the beacon signals received within Ri,j , the RSSIs have several special characteristics there: – The RSSIs of the two strongest received signals are almost equal, as the distances from the SOI to the corresponding access points, respectively, are almost the same. The same holds for the two weakest signals. – At those points in Ri,j where gopt is maximal, the quotient Qi (i ∈ {1, 2}) of the distance to the far APs by the distance to the close APs can be calculated by Pythagoras’ formula, as depicted in Figure 3.   l22 + ( 12 l1 )2 l12 + ( 12 l2 )2 x1 x2 Q1 = = ; Q = = (9) 2 1 1 y1 y2 2 l1 2 l2

Improved Weighted Centroid Localization





























    
































29












   

Fig. 3. Calculation of parameters Q1 and Q2











 

 





  


    







 

     

   



 

 






































Fig. 4. Typical values in common rooms a) for D1 and D2 , b) for a1 , a2 , b1 , and b2

According to Equation 6, the RSSI differences between the received signals from the corresponding APs are Di = 20 · log10 Qi , i ∈ {1, 2}.

(10)

Thus, a SOI only needs to know l1 and l2 to achieve the parameters Qi and Di . The values of l1 and l2 can easily be obtained by the fixed AP positions. The SOI has to use D1 if it is situated in region C1,1 or C1,2 . Otherwise, it has to choose D2 , as it is situated in region C2,1 or C2,2 then. Common values for Di are shown in Figure 4a. For example, in a region with p = 43 , the calculation results for Di are D1 = 9.0908 dB and D2 = 5.1188 dB. The differences between the received RSSIs can generally be expressed as follows: Δk = RSSIk − RSSIk+1 , k ∈ {1, 2, 3} where RSSIk represents the k-th strongest received RSSI. Within regions Ri,j , the values of Δ1 and Δ3 are typically very low (close to 0), while those of Δ2 are close to D1 (in R1,j ) or D2 (in R2,j ).

30

S. Schuhmann et al.

Fig. 5. Distribution of calculated gi (S) in theory (p = 1, i.e. g1 (S) = g2 (S))

Balancing Function. To differ if a SOI is located in Ri,j where gopt is considerably high, we decided to define the following balancing function S that is based on the special RSSI characteristics in Ri,j that were mentioned above: S = Δ1 + |Di − Δ2 | + Δ3 , i ∈ {1, 2}

(11)

As already mentioned, Δ1 and Δ3 are close to zero within Ri,j , while Δ2 depends on the parameter p and is around Di in Ri,j . Thus, (Di − Δ2 ) is around zero in Ri,j . Following, S is minimum within Ri,j and increases outside of these regions. Hence, the use of S helps to state more precisely the location of the SOI. Approximation. We calculated S for various positions in the whole region, and compared the values with those of the optimal gopt at this position. The distribution of S dependent on g is shown in Figure 5 and suggests to approximate gd by the power function that is denoted in (12). ai gd = gi (S) = bi , i ∈ {1, 2} (12) S with the unknown parameters a1 and b1 if the SOI is within C1,1 or C1,2 , and with a2 and b2 if the SOI is located in C2,1 or C2,2 . Now, we approximated the power functions with the least-squares method for various values of p and got the parameters ai and bi as denoted in Figure 4 that yield minimum root mean square (RMS) errors. For example, in case of p = 1, we got a1 = a2 ≈ 1.580 and b1 = b2 ≈ 0.248 which led to a very small RMS error of only 0.002 which is a small fraction of the RMS error of SWCL with optimal static weight.

5

Evaluation

First, we present the theoretical results of DWCL and compare them with those of SWCL. Then, we concentrate on the indoor tests with 802.11 WLAN access

Improved Weighted Centroid Localization

31

Fig. 6. Evaluation results of theoretical calculations 3·108 m

points, operating at a wavelength of λ = fc = 2.44·109sHz ≈ 0.123 m, and compare our practical results with the calculated ones. 5.1

Theoretical Results

We compared the calculated location accuracies of DWCL and SWCL with the results we got by choosing the optimal gopt at each position within the observed region. The results are shown in Figure 6. The mean error of SWCL at a quadratic room (p = 1) is 7.6 %, while the mean error of DWCL is 5.3 % and, hence, very close to the best possible WCL value of 5.1 %. Regarding the maximum error within the region, DWCL and the WCL optimum are almost equal, while SWCL’s accuracy is worse by 2.5 percentage points. The results for a value of p = 2 are quite similar, even though DWCL’s mean gain decreases a bit. 5.2

Indoor WLAN Tests

We implemented the WCL scheme on a common smart phone1 which served as a client device. The infrastructure beacons were represented by standard 802.11 access points2 . The transmission power was put to the maximum possible value of 50 mW with a fixed bandwidth of 11 Mbit/s at 802.11b mode. According to [20], this provides a maximum range of about 67 meters in indoor scenarios. Figure 7a shows the setting for our indoor tests. We used four beacons, A1 to A4 , which were placed in the corners of a quadratic plain of 4.8 m x 4.8 m (i.e., p = 1) in a first test, and a rectangular plain of 5.8 m x 3.2 m (i.e., p ≈ 1.81) in a second test. The tests have been performed in a wall-enclosed office within a 1 2

T-MobileTM MDA Pro with PXA 270 CPU (520 MHz), 48 MB RAM, IEEE 802.11b. CiscoTM Aironet 1200, [20].

32

S. Schuhmann et al.

Fig. 7. a) Indoor test setup, b) Distribution of calculated gd at indoor tests (p = 1)

building where interferences with other WLANs occured. Furthermore, typical office furniture like chairs, desks, and a flip chart were available in the room. The SOI and the APs were placed on a plain table. We deactivated rate shifting on the APs to guarantee fixed transmission powers and performed 20 localization processes at various positions within the region, respectively. Then, we compared the averaged calculated positions with the real ones to determine the location errors. Figure 7b displays the values of the balance function S at the test positions and the approximated power function for p = 1. The mean square error (0.330) is

Fig. 8. Evaluation results of indoor tests

Improved Weighted Centroid Localization

33

higher than in theory as the signals suffered from noise and reflections. However, this error is still about 33.7 % lower than that of SWCL with gs = 0.93. Figure 8 presents a comparison of the mean errors of DWCL, SWCL, and calculations with gopt in these tests. It states that for p = 1, DWCL performs about 0.7 percentage points worse than the theoretical WCL optimum, but at the same time about 2.3 percentage points better than SWCL regarding the mean error, which implies it uses most of the existing potential for improvements. Concerning worst cases, DWCL’s difference to the optimum in accuracy is close to zero, while SWCL performs about 4.2 percentage points worse than the optimum. These results confirm the increased location accuracy by dynamic weighting factors, particularly regarding worst case accuracies in rooms that are almost quadratic where DWCL chooses nearly optimal values for gd .

6

Conclusion and Outlook

In this paper, we proposed an improved Weighted Centroid Localization scheme called DWCL in combination with 802.11 access points as a simple, cost-efficient, applicable, and accurate localization scheme for ubiquitous computing scenarios. We introduced the problem domain, discussed the requirements, and presented the original WCL scheme with static weight factors (SWCL). Following, we developed an improved WCL scheme called DWCL that uses dynamic weighting factors which depend on the RSSIs to increase location accuracy. From our experiments, we conclude that DWCL represents a very effective and yet simple method for indoor localization, as it implies almost optimal location accuracy for weighted centroid schemes with rectangular anchor positioning. It does not pose additional requirements to the clients as well as to the infrastructure beacons. Standard WLAN access points suffice for achieving acceptable localization errors, and the computational burden put on mobile client devices is mild. Due to the fact that WLAN-based WCL can be used in environments with off-the-shelf WLAN hardware, it is appropriate for achieving ad hoc localization in many ubiquitous smart environments with minimal prior setup efforts. The research group at the University of Stuttgart currently investigates if this improved WCL scheme is applicable for localization across several rooms with larger distances between the access points, and alternative positionings of the access points. The research team at the University of Rostock concentrates on the reduction of the positioning error that is mainly caused by border effects. Their current focus is the adaptation of weight functions according to the number of known beacons and the adjusted transmission range of the beacons.

Acknowledgement This work is funded by the German Research Foundation (DFG) within Priority Programme 1140 - Middleware for Self-organizing Infrastructures in Networked Mobile Systems.

34

S. Schuhmann et al.

References 1. Blumenthal, J., Reichenbach, F., Timmermann, D.: Position Estimation in Ad hoc Wireless Sensor Networks with Low Complexity. In: Joint 2nd Workshop on Positioning, Navigation and Communication and 1st Ultra-Wideband Expert Talk, pp. 41–49 (March 2005) 2. Fekete, S.P., Kr¨ oller, A., Buschmann, C., Fischer, S., Pfisterer, D.: Koordinatenfreies Lokationsbewusstsein. it - Information Technology 47(2), 70–78 (2005) 3. Pandey, S., Anjum, F., Kim, B., Agrawal, P.: A low-cost robust localization scheme for WLAN. In: Proceedings of the 2nd Int.’l Workshop on Wireless Internet (2006) 4. Bulusu, N., Heidemann, J., Estrin, D.: GPS-less Low Cost Outdoor Localization For Very Small Devices. IEEE Personal Communications Magazine 7(5), 28–34 (2000) 5. Niculescu, D., Nath, B.: DV Based Positioning in Ad hoc Networks. Journal of Telecommunication Systems (2003) 6. Nagpal, R.: Organizing a global coordinate system from local information on an amorphous computer. Technical Report AI Memo No. 1666, MIT A.I. Laboratory (1999) 7. He, T., et al.: Range-free localization and its impact on large scale sensor networks. Transactions on Embedded Computing Systems 4(4), 877–906 (2005) 8. Elnahrawy, E., Li, X., Martin, R.P.: Using Area-Based Presentations and Metrics for Localization Systems in Wireless LANs. In: Proceedings of the 29th IEEE International Conference on Local Computer Networks (LCN 2004), Washington, USA (2004) 9. Parkinson, B.W., Spilker Jr., J.J.: Global Positioning System: Theory and Applications, Vol. 1. In: Progress in Astronautics and Aeronautics, American Institute of Aeronautics and Astronautics, vol. 163, pp. 29–56 (1996) 10. Harter, A., Hopper, A., Steggles, P., Ward, A., Webster, P.: The Anatomy of a Context-Aware Application. Mobile Computing and Networking, 59–68 (1999) 11. Niculescu, D., Nath, B.: Ad hoc positioning system (APS). In: Proceedings of GLOBECOM, San Antonio (November 2001) 12. Bahl, P., Padmanabhan, V.N.: RADAR: An In-Building RF-Based User Location and Tracking System. In: INFOCOM, vol. (2), pp. 775–784 (2000) 13. Youssef, M., Agrawala, A., Shankar, U.: WLAN Location Determination via Clustering and Probability Distributions. In: Proceedings of IEEE PerCom 2003 (March 2003) 14. Ganesan, D., Krishnamachari, B., Woo, A., Culler, D., Estrin, D., Wicker, S.: Complex Behavior at Scale: An Experimental Study of Low-Power Wireless Sensor Networks. Technical Report CSD-TR 02-0013, UCLA (February 2002) 15. Want, R., Hopper, A., Falc˜ ao, V., Gibbons, J.: The Active Badge Location System. ACM Transactions on Information Systems (TOIS) 10(1) (1992) 16. Paperno, E., Sasada, I., Leonovich, E.: A New Method for Magnetic Position and Orientation Tracking. IEEE Transactions on Magnetics 37(4) (July 2001) 17. Krumm, J., Harris, S., Meyers, B., Brumitt, B., Hale, M., Shafer, S.: Multi-Camera Multi-Person Tracking for EasyLiving. In: Proceedings of the 3rd IEEE International Workshop on Visual Surveillance (VS 2000), Washington, USA (2000) 18. Ganu, S., Krishnakumar, A., Krishnan, P.: Infrastructure-based location estimation in WLAN networks. In: Proceedings of IEEE WCNC 2004 (March 2004) 19. Blumenthal, J., Grossmann, R., Golatowski, F., Timmermann, D.: Weighted Centroid Localization in WLAN-based Sensor Networks. In: Proceedings of the 2007 IEEE International Symposium on Intelligent Signal Processing (WISP 2007) (2007) 20. Cisco Systems, Aironet 1200 Series Access Point Data Sheet, http://www.cisco.com/en/US/products/hw/wireless/ps430

A Formal Framework for Expressing Trust Negotiation in the Ubiquitous Computing Environment* Deqing Zou1, Jong Hyuk Park2, Laurence Tianruo Yang 3, Zhensong Liao1, and Tai-hoon Kim4 1 Services Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology, China 2 Department of Computer Science and Engineering, Kyungnam University, Korea 3 St. Francis Xavier University, Canada 4 Division of Multimedia, Hannam University, Korea

Abstract. There are lots of entities in the ubiquitous computing environment. For the traditional public key Infrastructure (PKI), every entity should be signed a valid certificate by the certificate authentication center. However, it’s hard to construct a centralized trust management framework and assign a valid certificate for every entity in the ubiquitous computing environment because of large numbers of dynamic entities. Trust negotiation (TN) is an important means to establish trust between strangers in ubiquitous computing systems through the exchange of digital credentials and mobile access control policies specifying what combinations of credentials a stranger must submit. Current existing TN technologies, such as TrustBuilder and KeyNote, focused on how to solve a certain problem by using some special techniques. In this paper, we present a formal framework for expressing trust negotiation. The framework specifies the basic concepts, elements and the semantics of TN. By analyzing TN, we point out how to build a TN system in practice.

1 Introduction With the comprehensive popularity of computer knowledge and the great development of computer network, people have more and more requirements towards resource sharing over Internet. Common access control mechanisms, such as MAC [1], RBAC [2], could not work well because of their limitation in design and application. In the ubiquitous computing environment, it’s hard to construct a centralized trust management framework for large numbers of dynamic entities. Exchange of attribute credentials is a means to establish mutual trust relationship between strangers in the ubiquitous computing environment, who wish to share resources or conduct business transactions [3][4][5]. As a new access control mechanism, TN successfully provides a method to share resources for strangers from different security domains in the ubiquitous computing environment. *

The project is supported by National Natural Science Foundation of China under Grant No. 60503040.

F.E. Sandnes et al. (Eds.): UIC 2008, LNCS 5061, pp. 35–45, 2008. © Springer-Verlag Berlin Heidelberg 2008

36

D. Zou et al.

In TN, automated trust negotiation (ATN), as a new kind of TN, has a great improvement towards previous TN. Generally, ATN differs from TN as the following aspects: 1) ATN discloses the access control policy when the resource can be available. While in TN, the requestor would not know what credentials he must submit before the negotiation starts. From this, we can see that ATN saves much time, which helps to improve negotiation efficiency. 2) ATN has done much work in privacy protection. In TN, the requestor is required to submit his certificate to attain the access. In ATN, the trust relationship is established by the exchange of credentials and access control policies. The disclosure of a certificate may pose a threat towards the user private privacy, while the disclosure of a credential would not do. 3) ATN pays much attention on information protection, while TN does not. In ATN, the transmitting messages are encrypted, while in most TN systems, the exchanged data are plaintexts. Currently, there are still some problems unsolved in TN. First, there are no unified secure definitions for TN’s concepts. For example, what is a credential? What information a credential must include? Which credential is secure? Second, TN is difficult to be formalized by a certain language, which leads to a low security level. Third, since most information protection techniques are immature or heavyweight, how to protect privacy and sensitive information is still a serious issue. Finally, there is no guideline to instruct how to build a TN system. In the paper, we aim at expressing TN theoretically, specifying the internal relationship between TN’s concepts or components. Generally, our work has the following contributions: 1) A common framework of general-purpose for TN is proposed in this paper. Previous work focused on how to solve a certain problem, such as giving a model, using some special techniques and so on. Our work aims at the unification of all kinds of models and techniques. 2) We propose a lot of useful suggestions on how to build a TN system. Usually, before developing a TN system, some preparations should be made. For example, which policy language will be selected? How should we improve negotiation efficiency? Previous work did not deal with such problems. 3) We present a new thought to improve TN’s security level. According to the specification of TCSEC (Trusted Computer System Evaluation Criteria) [6], TN has a low security level. If TN is formalized by a certain policy language, TN’s security level would be improved or enhanced. The rest of this paper is organized as follows. Section 2 describes the related work, including TN project survey and information protection techniques. Section 3 is the main part of the paper. It describes the framework in detail. Section 4 purposes useful suggestions on how to build/develop a TN system. Section 5 concludes the paper and specifies the future work.

A Formal Framework for Expressing Trust Negotiation

37

2 Related Work Our work is originally motivated from the existing automated trust negotiation research [3][4][5] whose goal is to enable trust establishment between strangers in a decentralized or open environment, such as Internet. Our work focuses on analyzing TN, including the concepts, the components and the relationship between the concepts. To make it clear, existing TN projects and systems should be collected. Meanwhile, how to protect sensitive information or personal privacy is still a hot issue. Based on these, in this part, we mainly investigate TN projects/systems and information protection. In the existing TN systems, TrustBuilder [7][8], KeyNote [7][9][10] are much well-known. Some similar systems include PolicyMaker [11], SD3 [12], PRUNES [13] and Trust-X [14]. Here, we mainly discuss TrustBuilder and KeyNote. TrustBuilder represents one of the most signification proposals in the negotiation research area. It provides a broad class of negotiation strategies, as well as a strategyand language-independent negotiation protocol that ensures the interoperability of the defined strategies within the its architecture. Each participant in a negotiation has an associated security agent that manages the negotiation. During a negotiation, the security agent uses a local negotiation strategy to determine which local resources to disclose next and to accept new disclosures from other parties. In KeyNote, the predicates are written in a simple notation based on C-like expressions and regular expressions, and the assertions always return a Boolean (accepted or denied) answer. Moreover, the credential signature verification is built in to KeyNote system. Assertion syntax is based on a human-readable “RFC-822”-style syntax. And the trusted actions in KeyNote are described by simple attribute/value pairs. As far as the information protection is concerned, some typical and influencing techniques are involved as the following. W.H. Winsborough and N. Li [4] presented ACK policy to control the disclosure of credentials and policies, and developed TTG protocol to construct policy tree so that it was easy to detect whether the credentials matched the policies or not. ACK policy is useful to protect sensitive information, and TTG protocol enables two parties to do joint chain discovery in an interactive manner as well as the parties to use policies to protect sensitive credentials and the attribute information contained in the credentials. However, ACK policy and TTG are limited in applying because of difficulty in constructing them. N. Li et al [15] proposed OSBE protocol to prevent important information from leaking and void the negotiation being attacked. OSBE bases its idea on digital signature and checks the message’s integrity so as to detect whether the negotiator has the right signature. OSBE protects message from unauthorized access, but it is heavyweight to build and the signature computing has a great cost. Holt et al introduced hidden credentials in [16]. They gave a formal description for hidden credentials, including the concepts of credential and policy indistinguishability, and showed how to build them using IBE. Their work also gave some compelling examples of the utility of hidden credentials. In short, they provided a good model for trust negotiation to implement hidden credentials. Based on this, Robert W et al [17] used hidden credentials to conceal complex policies, and Keith F et al [18] used them

38

D. Zou et al.

to hide access control policies. Since hidden credential system cannot prevent from invalid inference, its implementation is limited in some degree. J. Li and N. Li proposed the notions of OACerts and OCBE in [19]. OCBE protocol adopted the idea of zero-knowledge and ensured that if and only if the recipient was the specified one, he could get the resource, otherwise he got nothing. However, the method has not discussed how to guarantee the security of message during the transmission over the insecure Internet.

3 Framework for Expressing Trust Negotiation In this section, we will describe the TN framework in detail. First, the basic concepts and elements are listed. Then, the framework is introduced. Finally, the corresponding expressions are given. 3.1 Basic Concepts and Elements TN is performed by the exchange of credentials and access control policy. In this part, we give the basic concepts of TN and put forward their corresponding formalized description as follows: • Access control policy (ACP): the constraint in accessing the resource, which indicates what credentials the accessor should prepare and submit. In TN, access control policy has two types: compound policy and meta policy. Meta policy is the minimal element to compose a compound policy. To realize it, a set of conjunctive predicates are required, such as , < ∧,∨,¬> and so on. • Access request (AR): a structural message to tell the resource provider that the resource is expected to be accessed. An access request should at least include: 1) accessor, 2) requested resource, 3) requested operation. • Certificate: to identify a person’s identity or attribute information, such as principal, public key. In previous TN, certificate is the main tool to carry a person’s information. Currently, as a person’s privacy is considered, certificate is hardly disclosed and transferred any more. • Credential: a kind of temporary certificate, whose content comes from the user’s certificate. In other words, a certificate contains many credentials. When the credential is introduced in TN, user’s certificate would not be released. • Negotiation strategy (NS): a mechanism to specify how to disclose access control policy and credentials. There are two extreme negotiation strategies: eager strategy and parsimonious strategy. The former discloses zealously without being requested, while the latter would not release any until a request is received. • Negotiation protocol (NP): a rule to specify what actions would be taken during the negotiation process, including authentication, delegation, authorization communication mode (TCP/UDP), encryption mode (symmetrical or asymmetrical), and encryption function and so on. For example, is transmitting message transferred via plaintext or ciphertext? How to select the encryption functions?

A Formal Framework for Expressing Trust Negotiation

39

Accordingly, the basic elements of TN are as follows: • ACP: access control policy set. ACP= {acp1,acp2,…,acpn}, acpi (1≤i≤n) is a meta policy. Usually, an access control policy ACP can be depicted as ACP=f(acp1,acp2,…,acpn), while f is compound function by using the specified conjunctive predicates. • AR: access request set. AR={ar1,ar2,…,arn}, ari (1≤i≤n) is a specific access request towards a certain resource. • C: credential set, C={c1,c2,…,cn}, ci (1≤i≤n) is a credential. Every credential carries only one kind of attribute information. • R: resource which can be accessed. In TN, R stands for the available resource. It can be the resource itself, or the access entry. When R is disclosed, the trust relationship is established, and the negotiation process ends up. • SEQ: disclosure sequence set, which is used to store the disclosed access requests, access control policies and credentials. SEQ=SEQAR∪SEQACP∪ SEQC∪R, while SEQAR (SEQACP, SEQC) denotes the disclosed access request (resp. access control policy, credential) sequence. When R∈SEQ, the negotiation succeeds. • NS: negotiation strategy set. NS={ns1,ns2,…,nsn}, nsi (1≤i≤n) is the selected negotiation strategy. In practice, new negotiation strategies may be developed according to the application. • NP: negotiation protocol set. NP={np1, np2,…,npn}, npi (1≤i≤n) is a certain negotiation protocol to specify how to exchange information during the negotiation process.

Fig. 1. The relationship between AR and ACP

3.2 Framework for Expressing Trust Negotiation In our framework, TN can be described as follows: TNparameter=

(1)

In (1), TNparameter denotes the parameter to deploy a TN system. When TNparameter is confirmed, the work mode of TN is established. ATN/TN stands for the negotiation

40

D. Zou et al.

type. When ATN is selected, it is an ATN system. AR (ACP, C, NS, NP) is the corresponding access request (resp. access control policy, credential, negotiation strategy, negotiation protocol) set. There are many internal relationships and constraints among TN’s parameters. 1) The relationship between AR and ACP In TN, when the resource provider receives an access request ar, he will analyze it and check whether it is valid and effect. If ar passes the examination, the resource provider will return a relative access control policy set Policy (including one or more meta policies) as a response, otherwise, ar is denied. Generally, every request should have a corresponding policy set, i.e., ∀ar∈AR,∃Policy⊆ACP⇒Correlate(ar,Policy), in which the function Correlate() is a binary logic predicate. Meanwhile, it may happen multiple requests correspond to a same policy set. This is caused by the access granularity. In short, the relationship between AR and ACP can be shown as Fig. 1.

Fig. 2. The relationship between ACP and C

2) The relationship between ACP and C In TN, credentials are submitted to meet the requirements of a compound policy. To avoid the different meanings, each credential can only satisfy a meta policy. That is to say, ∀acp∈ACP, ∃c∈C⇒Match(acp,c) and ∀c∈C,∃acp∈ACP⇒ Match(acp,c), in which the function Match() is also a binary logic predicate. The relationship between ACP and C can be shown by Fig. 2. 3) The relationship between NS and NP In TN, negotiation strategy decides the disclosure mode. Different negotiation strategy has different requirements towards system, network, user, resource provider and negotiation protocol. For example, if the parsimonious strategy is adopted, i.e., the negotiation needs a tight coupling communication, which causes a great network burden, and has a strict requirement towards the negotiation protocol. Accordingly, negotiation protocol decides the negotiation process. Usually, negotiation protocol and negotiation strategy should cooperate with each other; otherwise, the negotiation is easy to fail. The relationship between NS and NP is shown as Fig. 3.

A Formal Framework for Expressing Trust Negotiation

41

Fig. 3. The relationship between NS and NP

3.3 Trust Negotiation Expression From above, we can see that the state of TN can be depicted as: STN = SX + SY

(2)

SX = NS × NP

(3)

SY = AR × ACP × C

(4)

SX denotes a relatively static state of TN. When the negotiation starts, NS and NP would be ascertained. When SX is fixed, the disclosure sequence SEQ would be somehow clear. In short, SX decides the qualitative change of SEQ. SY stands for a relatively dynamic state of TN. SY records the total negotiation process, which can be used to track both negotiators’ actions. Meanwhile, it is the important information to compose the log file. If the negotiation fails, SY can be useful to produce feedback. In short, SY decides the quantitative change of SEQ. As negotiation protocol is taken into account, NP can be depicted as: NP=

(5)

In (5), A1 is authentication. In TN, authentication is an important means to make certain a user’s identity. Usually, authenticating process is to ensure that the acceesor holds the private key of his certificate. Suppose p and l to be a user’s principal (also called public key) and license (also called private key). The authenticating process can be: 1) the server randomly picks a string str, and encrypts it with the user’s principal p and passes it to the user; 2) the user decrypts it and returns it through a secure VPN (virtual private network) channel; 3) the server compares the original string with the received string, and decides the authentication result. Since it would take a great cost to set up a VPN channel, authentication can be realized by mutual encryption via insecure channel such as Internet without VPN. Based on this, we present a mutual authentication shown as Fig. 4.

42

D. Zou et al.

Fig. 4. Mutual authentication for TN

In short, authentication can be depicted as: A1= Principal × License

(6)

In (5), D is delegation. In TN, delegation is to endow others with one’s privileges. To finish a delegation, two users (suppose A and B) should do: 1) the authentication of A and B; 2) the delegation of B towards A, to let A own B’s privileges. Based on these, the delegation can be depicted as: DBA = A1A × A1B × PrivilegeB

(7)

In (5), A2 is authorization. In TN, authorization is to let the accessor have the specified privileges to operate on resource. In short, authorization can be depicted as: A2= Principal × License × PrivilegeR

(8)

In (5), PL/CI denotes the message encapsulation means. PL is plaintext, while CI is ciphertext. TCP/UDP denotes the communication means. TCP stands for tight coupling communication. When NS is parsimonious strategy, TCP must be selected. UDP stands for loose coupling communication. S/A denotes the encryption means. S stands for symmetric encryption, while A stands for asymmetric encryption. When S is selected, the relative algorithms could be AES [20], Rijndael [21] and so on. Corresponding, when A is selected, the relative algorithms could be RSA [22], ECC [23] etc.

4 Guideline for Building a TN System The research in theory is useful to guide teams to build practical systems. Before building a TN system, some questions should be answered.

A Formal Framework for Expressing Trust Negotiation

43

1) Application type The team should make clear what services the TN system can provide. How about the security requirements? Would the online service be high available or have high computing power? How to ensure QoS? When these problems are clear, the team can make good preparations for the development. 2) Policy language Not every language can serve for TN. TN has a lot of requirements [3][7] towards policy languages. The selection of policy language should be adapted to application type. 3) Specification of AR, ACP and C To attain the goal of high efficiency and least artificial participation, TN should be much intelligent as possible. To realize it, TN should improve the readability of access request, access control policy and credential. So before developing TN, the formats of AR, ACP and C should be ascertained. This helps to perform all kinds of operations. An example for the formats of AR, ACP and C can be: AR=(owner):(resource):(operation): (period)

(9)

ACP=(owner):(recipient):(item):(predicate): (value):(period)

(10)

C=(owner):(recipient):(item):(value):(period)

(11)

In (9), owner denotes the holder of AR, usually the principal of the user; resource denotes requested resource or service; operation denotes the requested operation towards the resource; while period denotes the valid life time of AR. In (10), owner denotes the holder of ACP; recipient denotes the receiver of ACP; item denotes the attribute content, such as role, age, name etc; predicate denotes the comparing symbol, predicate∈ {>,<,≥,≤,=,≠,∈,∉,….}; value denotes the comparing value, which may be a threshold; while period denotes the valid life time of ACP. In (11), owner denotes the holder of C; recipient denotes the receiver of C; item denotes the attribute content; while value denotes the attribute value. Note that, when the period of AR, ACP and C is specified, all the digital tools are temporary and can be automatically invalid. From this aspect, it would bring little overhead in storing access requests, access control policies and credentials.

5 Conclusions and Future Work As a new kind of access control mechanism, TN can establish the trust relationship by the exchange of access control policy and digital credentials in the ubiquitous computing environments. In the paper, we present a mathematical framework for expressing trust negotiation. The framework specifies the basic concepts, elements and the semantics of TN. By analyzing TN, we purpose some suggestions on how to build a practical TN system. Since TN still has a low security level, next step, we will pay more attention on how to combine our proposed framework with some strong security mechanisms, such as Public Key Infrastructure (PKI).

44

D. Zou et al.

References [1] Xin, L.L., Min, C.W., Lian, H.S.: Realizing Mandatory Access Control in Role-Based Security System. Journal of Software 11(10), 1320–1325 (2000) (in Chinese with English abstract) [2] Sandhu, R.S., Coyne, E.J., Feinstein, H.L., Youman, C.E.: Role-based access control models. IEEE Computer 29(2), 38–47 (1996) [3] Liao, Z.S., Jin, H., Li, C.S., Zou, D.Q.: Automated trust negotiation and its development trend. Journal of Software 17(9), 1933–1948 (2006) (in Chinese with English abstract) [4] Winsborough, W.H., Li, N.: Towards practical automated trust negotiation. In: Proceedings of the 3rd International Workshop on Policies for Distributed Systems and Networks, pp. 92–103. IEEE Computer Society Press, Los Alamitos (2002) [5] Jin, H., Liao, Z.S., Zou, D.Q., Qiang, W.Z.: A new approach to hide policy for automated trust negotiation. In: Yoshiura, H., Sakurai, K., Rannenberg, K., Murayama, Y., Kawamura, S.-i. (eds.) IWSEC 2006. LNCS, vol. 4266, pp. 168–178. Springer, Heidelberg (2006) [6] Trusted Computer System Evaluation Criteria. America Department of Defense, CSCSTD-001-93 (1983) [7] Seamons, K.E., Winslett, M., Yu, T., Smith, B., Child, E., Jacobson, J., Mills, H., Yu, L.: Requirements for Policy languages for Trust Negotiation. In: Proceeding of 3rd IEEE Intel Workshop on Policies for Distributed Systems and Networks, pp. 68–79. IEEE Computer Society Press, Los Alamitos (2002) [8] The TrustBuilder Porject, http://isrl.cs.byu.edu/ [9] Blaze, M., Feigenbaum, J., Lacy, J.: Decentralized Trust Management. In: Proceeding of the 17th symposium on Security and Privacy, pp. 164–173. IEEE CS Press, Los Alamitos (1996) [10] Blaze, M., Feigenbaum, J., Ioannidis, J., Keromytis, A.D.: The KeyNote TrustManagement System (Version 2). IETF RFC 2704 (September 1999) [11] Blaze, M., Feigenbaum, J., Strauss, M.: Compliance checking in the Poliymaker Trust Management System. In: Proceeding of 2nd Financial Crypto Conference, pp. 205–216. IEEE Press, Los Alamitos (1998) [12] Jim, T.: SD3: a trust management system with certificate evaluation. In: Proceeding of the 2001 IEEE Symposium on Security and Privacy, pp. 106–115. IEEE CS Press, Los Alamitos (2001) [13] Yu, T., Ma, X., Winslett, M.: PRUNES: An Efficient and Complete Strategy for Automated Trust Negotiation over the Internet. In: Proceeding of the 2000 ACM Conference on Computer and Communications Security, pp. 88–97. ACM Press, New York (2000) [14] Bertino, E., Ferrari, E., Squicciarini, A.: Trust-X: A peer to peer framework for trust negotiations. In: Proceeding of IEEE Transaction on Knowledge and Data Engineering, pp. 132–138. IEEE CS Press, Los Alamitos (2004) [15] Li, N., Du, W., Boneh, D.: Oblivious signature-based envelope. In: Proceeding of the 22nd ACM Symposium on Principles of Distributed Computing, pp. 182–189. ACM Press, New York (2003) [16] Holt, J.E., Bradshaw, R., Seamons, K.E., Orman, H.: Hidden credentials. In: Proceedings of 2nd ACM Workshop on Privacy in the Electronic Society, pp. 1–8. ACM Press, New York (2003)

A Formal Framework for Expressing Trust Negotiation

45

[17] Bradshaw, R.W., Holt, J.E., Seamons, K.E.: Concealing Complex Policies with Hidden Credentials. In: Proceedings of the 4th ACM Conference on Computer and Communications Security, pp. 245–253. ACM Press, New York (2004) [18] Frikken, K., Atallah, M., Li, J.: Hidden Access Control Policies with Hidden Credentials. In: Proceedings of the 3rd ACM Workshop on Privacy in the Electronic Society, pp. 130– 131. ACM Press, New York (2004) [19] Li, J., Li, N.: OACerts: Oblivious Attribute Certificates. In: Proceeding of 3rd Conference on Applied Cryptography and Network Security, pp. 108–121. ACM Press, New York (2003) [20] Johannes, B., Seifert, J.P.: Fault Based Cryptanalysis of the Advanced Encryption Standard (AES). In: Wright, R.N. (ed.) FC 2003. LNCS, vol. 2742, pp. 162–181. Springer, Heidelberg (2003) [21] Ferguson, N., Kelsey, J., et al.: Improved Cryptanalysis of Rijndael. In: Proceedings of 7th International Workshop of Fast Software Encryption, vol. 1987, pp. 136–141. Springer, Heidelberg (2001) [22] Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public key crytosystems. Communications of the ACM, 120–126 (1978) [23] Gura, N., Eberle, H., Shantz, S.C.: Generic implementations of elliptic curve cryptography using partial reduction. In: Proceedings of the 9th ACM conference on Computer and Communications Security, pp. 177–189. ACM Press, New York (2002)

Pervasive Services on the Move: Smart Service Diffusion on the OSGi Framework Davy Preuveneers and Yolande Berbers Department of Computer Science, K.U. Leuven Celestijnenlaan 200A, B-3001 Leuven, Belgium {davy.preuveneers, yolande.berbers}@cs.kuleuven.be http://www.cs.kuleuven.be

Abstract. The ubiquity of wireless ad hoc networks and the benefits of loosely coupled services have fostered a growing interest in service oriented architectures for mobile and pervasive computing. Many architectures have been proposed that implement context-sensitive service discovery, selection and composition, or that use a component-based software engineering methodology to facilitate runtime adaptation to changing circumstances. This paper explores live service mobility in pervasive computing environments as a way to mitigate the risk of disconnections during service provision in mobile ad hoc networks. It focuses on contextaware service migration and diffusion to multiple hosts to increase accessibility and expedite human interaction with the service. We analyze the basic requirements for service mobility and discuss an implementation on top of OSGi. Finally, we evaluate our approach to service mobility and illustrate its effectiveness by means of a real-life scenario.

1

Introduction

The late Mark Weiser [1] predicted that the next wave in the era of computing would be outside the realm of the traditional desktop. Everything of value would be on the network in one form or another with smart interacting objects adapting to the current situation without any human involvement. Ubiquitous computing will become the next logical step to mobile computing where people are already connected anytime and anywhere. The growing presence of WiFi and 3G wireless Internet access and sensor network technologies will give rise to this new paradigm, in which information and intelligent services are invisibly embedded in the environment around us. Service-oriented computing (SOC) [2] is a key enabler of Weiser’s vision. It represents the current state of the art in software architecture [3] that utilizes services as fundamental building blocks for the rapid development and deployment of applications. It relies on a service-oriented architecture (SOA) to organize loosely coupled services with functions to bind them and manage their life-cycle, such as the deployment and updating of services. These key features are crucial for service interaction in a ubiquitous computing environment. By breaking up an application into a configuration of independent services with well-defined F.E. Sandnes et al. (Eds.): UIC 2008, LNCS 5061, pp. 46–60, 2008. c Springer-Verlag Berlin Heidelberg 2008 

Pervasive Services on the Move

47

interfaces, SOA enables the creation of new applications with the required flexibility to customize services to changing demands and different contexts. The focus of this paper is on how we can improve the availability and accessibility of services in a highly dynamic ad hoc network where intermittent network connectivity can disrupt an application when multiple services on mobile and stationary devices are temporarily coupled to behave as one single application. We propose to replicate the same service and its state at runtime (i.e. live mobility of services) on multiple devices near to the user that can provide a guaranteed quality of service (QoS) with support for state synchronization between the replicated services. This way, we increase the number of opportunities a user can interact with a service and we can better deal with volatile network connections by handing over to a replica if the connection between two services breaks down. As such, we say that the same service has diffused to multiple hosts. In order to keep this diffusion approach scalable, the targets selected for diffusion need to be well-chosen. That is why context-awareness [4] is a necessity for service migration and diffusion in the ubiquitous computing paradigm. It addresses the inner characteristics of the services by collecting relevant information about the service requirements and the devices in the vicinity. It helps to select appropriate targets for service mobility and coordinate synchronization and access to services deployed on these devices, and learns for each service the devices the user will most likely interact with. The applicability of smart service diffusion in a distributed setting will be illustrated on top of the OSGi framework [5]. The paper is structured as follows. In section 2 we list the requirements to enable seamless service migration and diffusion. Section 3 provides details on how we realized these requirements on top of the OSGi framework. In section 4 we conduct experiments that illustrate the effectiveness of service diffusion in a real-life scenario. We measure the overhead of state transfer and synchronization as well as any benefit in improved availability and accessibility. Section 5 provides an overview of related work on distribution and mobility of services. We end with conclusions and future work in section 6.

2

Requirements for Service Migration and Diffusion

Pervasive services offer a certain functionality to nearby users. They are accessed in an anytime-anywhere fashion and deployed on various kinds of mobile and stationary devices. When users or devices become mobile, proactive live service mobility to multiple hosts can provide a solution to the increased risk of disconnecting remote services. In this section we review several non-functional concerns and requirements that need to be fulfilled to ensure that the migration and diffusion of a service in a mobile and pervasive setting can be accomplished. 2.1

Device, Service and Resource Awareness

In a pervasive services environment, the multi-user and multi-computer interaction causes a competition for resources on shared devices. Therefore, knowledge

48

D. Preuveneers and Y. Berbers

about the presence, type and context of the devices (including resource-awareness about the maximum availability and current usage of processing power, memory, network bandwidth, battery lifetime, etc.) is a prerequisite to guarantee a minimum usability and quality of service. Before relocating a service to another host, a service discovery protocol (SDP) can be used to verify if the service is not already available [6]. 2.2

Explicit Service State Representation and Safe Check-Pointing

Stateless services can be replaced with similar ones or redeployed on another host at runtime without further ado as long as the syntax and semantics of the interfaces remain the same such that the binding can be reestablished. Stateful services require a state transfer after redeployment before they can continue their operations on a different host. Furthermore, the service must be able to resume from the state it acquired. Therefore, services should model the properties that characterize their state and make sure that check-points of their state are consistent [7,8]. 2.3

State Synchronization and Support for Disconnected Operation

Due to possible wireless network disruptions in the mobile setting of the user, complete network transparency of remote service invocations can have a detrimental effect on service availability and accessibility. The service platform should provide support to deal with intermittent network connectivity in order to recover from temporary failures in network connectivity between two services. With handover to replicated services whose states are synchronized, the effect of network disruptions can be reduced. Moreover, with discrete state synchronization, the requirement for continuous network connectivity can be mitigated. 2.4

Enhanced Service Life Cycle Management

The service platform must provide functions to manage the life-cycle of services, such as deployment, withdrawal, starting, stopping and updating. If a service cannot be run locally because of a lack of resources, the service needs to be moved to a remote and more powerful device in the vicinity of the user. The service life cycle management should move services to new hosts and replicate the state if necessary. We propose two kinds of service mobility (see Fig. 1): – Service Migration: Once the replicated service has moved to a new host, the original one is stopped and uninstalled. This is the typical behavior of ‘follow-me’ applications that move along with the user. – Service Diffusion: In this adaptation, the original service becomes active again once the state has been extracted. New replicas acquire the service state and get activated. After activation, service states are synchronized. Of course, a combination where a service is replicated on multiple hosts, but where the original is uninstalled is also possible. Also note that plain service migration does not require any state synchronization at all, but handing over to a service replica is no longer possible when trying to recover from a network failure.

Pervasive Services on the Move

49

Fig. 1. Live migration and diffusion of services. Service migration completely relocates the service to another host, while service diffusion redeploys the same service on other hosts and ensures service state replication and synchronization.

As the effect of network disruptions cannot be mitigated completely, we must also clean up stale replicated services. This problem is similar to distributed garbage collection where heartbeats or lease timeouts are used to detect disconnections and recycle memory. Similar algorithms can be reused to clean up these services.

3

Context-Aware Service Mobility on the OSGi Framework

In this section we will discuss how the previous requirements have been implemented on top of the OSGi framework [5]. This lightweight service oriented platform has been chosen for its flexibility to build applications as services in a modularized form with Java technology. OSGi already offers certain functionalities that are needed to implement the service migration and diffusion requirements. OSGi is known for its service dependencies management facilities and the ability to deal with a dynamic availability of services. Moreover, OSGi can be deployed on a wide range of devices, from sensor nodes, home appliances, vehicles to high-end servers, and allows the collaboration of many small components, called bundles, on local or remote computers. As such, OSGi is a viable platform for service orientation in a ubiquitous computing environment. 3.1

Extending Service Descriptions with Deployment Constraints

Services in the frame of OSGi are published as a Java class or interface along with a set of service properties. These service properties are key-value pairs that help service requesters to differentiate between service providers that offer services with the same service interface. Service providers and requesters are packaged into a OSGi bundle, i.e. a JAR file with a manifest file that contains

50

D. Preuveneers and Y. Berbers

information about the bundle, such as version numbers and service dependencies. Service descriptions are stored in the service registry of OSGi. Service requesters can discover and bind to a service implementation by actively querying for the service or by subscribing to a notification mechanism in order to receive events when changes in the service registry occur. A recent addition to the OSGi R4 framework that simplifies the registering of POJOs (plain old Java objects) as services and the handling of service dependencies is the Declarative Services (DS) specification [5]. Dependency information that is currently not mentioned in the service descriptor deals with non-functional properties such as hardware, software and resource constraints. For example, one OSGi bundle could be successfully deployed on a J2ME CDC Foundation Profile, while another could need at least a J2ME CDC Personal Profile or a J2SE virtual machine because it uses AWT for a graphical user interface. Moreover, resource (memory, processing power, storage) and hardware (screen, audio, keyboard) dependencies need to specified as well. The current key-value pair format for service properties is too limited to describe these complex constraints. As discussed in our previous work [9,10,11], ontologies provide a convenient richer specification format to describe and discover pervasive services with support for QoS and context-awareness. We therefore opted to add a ‘deployment’ entry into the Declarative Service descriptor in which we refer to an ontology that is included in the JAR file of the OSGi bundle: <service> <provide interface=”communication.ChatClient” /> <deployment> <require name=”resources1” class=”descriptor.owl#MemoryDependency” /> <require name=”software1” class=”descriptor.owl#JavaVMDependency” /> <require name=”hardware1” class=”descriptor.owl#DisplayDependency” /> <require name=”hardware2” class=”descriptor.owl#KeyboardDependency” />

It models the above dependencies as class restrictions on concepts defined in our context ontologies1. A device should comply with these constraints if the service is to be deployed successfully. For example: = 98304” /> 1

See http://www.cs.kuleuven.be/∼ davy/ontologies/2008/01/ for the latest revision of our context ontologies.

Pervasive Services on the Move

51

The previous constraint declares that a device should have at least one memory resource instance (of class RAM or one of its subclasses) with a property currAvailable that has a value larger than or equal to 98304. The type of the property is specified in the Hardware.owl ontology, and for this value it is bytes.

The above constraint declares that a device should have at least one Java virtual machine instance with a GUI rendering engine instance that belongs to the JavaAWT class. The main advantage of our context ontologies [9] is that complex semantic relationships only need to be specified once and can be reused by every service descriptor. Moreover, each device profile can specify their characteristics with the same ontologies. If a device then would specify that it runs OSGi on top of JDK 1.6, then an AWT rendering engine dependency would semantically match, but a Java MIDP 2.0 LCDUI rendering engine would not. Resource and hardware constraints can be expressed in a similar way. The matching itself to verify that a service can move to a particular host is carried out by a context enabling service that is described in the following section. 3.2

Context-Awareness as an OSGi Distributed Declarative Service

In order to diffuse OSGi services in a way that takes into account the heterogeneity and dynamism of a ubiquitous computing environment, we need to be aware of what the characteristics and capabilities of these devices are, where they are located, what kind of services they offer and what resources are currently available. The COGITO service will provide this information on each host. It gathers and utilizes context information to positively affect the provisioning of services, such as the personalization and redeployment of services tailored to the customer’s needs. The core functions of the enabling service are provided as a set of OSGi bundles that can be subdivided into the following categories: – Context Acquisition: These bundles monitor for context that is changing and gather information from resource sensors, device profiles and other repositories within the system itself or on the network. – Context Storage: A context repository ensures persistence of context information. It collects relevant local information and context that remote entities have published in a way that processing can be handled efficiently without losing the semantics of the data.

52

D. Preuveneers and Y. Berbers




  
  
 




 
   

 

  

 
   


     






   

 

  

    

    







  

 
  







 






Fig. 2. Building blocks of the COGITO enabling service

– Context Manipulation: These bundles reason on the context information to verify that context constraints are met. Besides a rule and matching engine that exploits semantic relationships between concepts [11], it also provides adapters that transform context information into more suitable formats. A high-level overview of the building blocks of the context-awareness enabling service is given Figure 2. The advantage of decomposing the context-awareness framework into multiple OSGi bundles is that the modular approach saves resources when certain bundles are not required. COGITO is implemented as a distributed Declarative Service. As the Declarative Service specification does not cover the registration of remote services, we have each device announcing its presence and that of its context enabling service with a service discovery protocol like UPnP, SLP or ZeroConf. Upon joining a network, each other node in the network creates a remote proxy to the enabling service of the joining node, and the Declarative Services bundle will ensure lazy registration and activation of the proxy whenever remote context is acquired. When a node leaves the network, the proxies on the other nodes are deactivated. This approach for distributed Declarative Services simplifies the collection of context information on the network, but more importantly it also enables transparent sharing of intensive context processing services (such as a rule or inference engine bundle) on resource-constrained devices. 3.3

Service State Representation, Extraction and Synchronization

In order to replicate stateful services on multiple hosts with support for state synchronization, we need to explicitly model the state variables of the service, extract them at runtime and send them to the replicated peers. In order to keep

Pervasive Services on the Move

53

state representation and exchange straightforward and lightweight, we encapsulate the state of a service in a JavaBean. JavaBeans have the benefit of (1) being able to encapsulate several objects in one bean that can be passed around to other nodes, (2) being serializable and (3) providing get and set methods to automate the inspection and updating of the service state. The approach is quite similar to the stateful session beans in the Enterprise JavaBeans specification [12]. Stateful session beans maintain the internal state of web applications and ensure that during a session a client will invoke method calls against the same bean in the remote container. In our approach however, a JavaBean is situated locally within each replicated service and does not involve remote method calls. Instead, the contents of the JavaBean is synchronized with those of the replicated services. Our current implementation tries to synchronize as soon as the state of an application has been changed. When network failures arise, the state updates are put in a queue and another attempt is carried out later on. The queue holds the revision number of the last state that was successfully exchanged and this for the three replicated applications. If, however, two or more replicated services independently continue without state synchronization, a state transfer conflict will occur when the involved hosts connect again. In that case, a warning will be shown and the user can choose to treat the services as separate applications, or have one service push its state to the others. This approach is rather crude, but acceptable as long as we are mainly dealing with single-user applications.

    ! " #
$    !!
    




 

  




 

   $ 



" %

!!





 

Fig. 3. New service states in the life-cycle of a migrating or diffusing service. Some of the transitions of the original service are shown in green, the ones of the replicated service(s) in red.

54

3.4

D. Preuveneers and Y. Berbers

Extending the Life-Cycle Management to Relocate Services

In a ubiquitous computing environment where pervasive services are replicated, a user may switch from one replicated service to another. Therefore, we add extra information to the service state that helps to coordinate the synchronization of the state changes. For example, we add a revision number that is increased after each write operation on the bean and use Vector Clocks [13] among all peers to order the state updating events. Fig. 3 shows that an active service can not only be stopped, but that in another transition the state can be extracted from the service and synchronized, or that the service can continue to either migrate or replicate to a new host. We use a lease timeout algorithm to garbage collect stale replicated services in order to recycle resources. The timeouts are application dependent, but can be reconfigured by the user.

4

Experimental Evaluation

The usefulness and feasibility of dealing with context-aware service migration and diffusion will be illustrated with three applications: (1) a grocery list application, (2) a Jabber instant messaging client, and (3) a Sudoku game. The devices used in the experiment include two PDAs, a laptop and a desktop, all connected to a local WiFi network. This setup will simulate the real-life scenario in the next section. 4.1

Scenario

The scenario goes as follows: It is Saturday morning and mom and dad go shopping. Everybody at home uses the grocery list application to make up a shared grocery list. In the past, mom sometimes forgot her grocery list at home, but now she only needs to take along her smartphone. The application just diffuses along. Dad also has his PDA with him and runs the same replicated application. They decided to split up the work and go shopping separately. At the mall, each time mom or dad finds a product that they need, it is removed from the shared sticky note application. They get each others updates when the state of the application is synchronized. Mom is still checking out while dad is already at the car. As he is waiting, he has another go at the Sudoku puzzle that he was trying to solve on the home computer that morning. His daughter is online and starts a conversation. She wants to send him a picture, but the display of his PDA is too small. He takes his briefcase, turns on his laptop, the application migrates and he continues the conversation there. Unfortunately, he forgot to charge his battery so after a while his laptop gives up on him. “Back to the PDA but then without the picture”, dad decides. In the meantime, mom has arrived and dad tells her about the picture. She will have a look at it at home once the application synchronizes with the desktop computer.

Pervasive Services on the Move


 

 


55






  
 
  
 

Fig. 4. The grocery list is automatically adapted to fit the new screen size if needed. After redeployment the states of all the replicated grocery lists are synchronized.

4.2

Experiments

In the experiment all the applications are launched on the desktop PC. The Jabber instant messaging client and Sudoku puzzle diffuse to one handheld, while the grocery list application diffuses to both PDAs. The application states are continuously synchronized between all hosts. Later on, the instant messaging application migrates from one PDA to the laptop and back (while synchronizing with the desktop PC). The mobility of the grocery list is illustrated in Figure 4. Additionally, these three applications all make use of two extra general-purpose services: (i) a stateless audio-based notification service, and (ii) a stateful logging service. By only deploying them on the desktop computer and synchronizing them on the laptop, we enforce that these two services can only be reached from a PDA through a remote connection. The applications will invoke them when (1) the grocery list changes, (2) the online status of somebody changes or (3) when the puzzle is solved. The bindings to the remote services are used to test handover to a replicated service after network disruptions. We let the setup run for 30 minutes, in which the following actions are simulated: – Each 30 seconds the grocery list is modified and synchronized. This event also triggers an invocation to both the remote services. – Each 5 seconds the state of the Jabber client is synchronized. Each minute the online status of somebody in the contact list changes, and this triggers an invocation to the remote services. – The Sudoku puzzle changes each 15 seconds and the 81 digits of the puzzle are synchronized. A puzzle is solved after 10 minutes, and this initiates an invocation to the remote services.

56

D. Preuveneers and Y. Berbers Table 1. Overhead results of state transfer, synchronization and handover Grocery List

Jabber Client

Sudoku Puzzle

Bundle size

23023 bytes

288235 bytes

54326 bytes

State size

7024 bytes

18235 bytes

1856 bytes

State synchronization

53 Kbytes / min 112 Kbytes / min 37 Kbytes / min

Relocation time

9 seconds

13 seconds

7 seconds

Synchronization delay

350 msec

518 msec

152 msec

Handover delay (audio service) 47 msec

61 msec

54 msec

Handover delay (log service)

213 msec

78 msec

167 msec

Each 3 minutes we shut down a random network connection for 1 minute to verify if the replicated applications can recover from the missed state updates and that handover to one of the remote replicated services. We measured the overhead of state transfer and synchronization and compare that to the resources that the applications required. We also measured the service availability and responsiveness by measuring the delay of handing over to another remote replicated service after a network disconnection. The experiment was repeated 3 times and the averaged results are shown in Table 1. 4.3

Discussion of the Results

The test results show there is only a small overhead for the state transfer. This is mainly a consequence of the size of the applications. They are rather small as they would otherwise not run on mobile devices. For other data intensive applications, such as multimedia applications, we expect that the overhead will be a lot bigger if data files have to be moved along as part of the state of the service. As the overhead was limited, we did not implement incremental state transfers, but for media applications this could be an improvement. The delays in state synchronization are low because the experiments were carried out on a local WiFi network. Other tests in multi-hop networks showed longer but still acceptable state synchronization delays (at most 5 times longer). More interesting though is the difference in service relocation time and state exchange time. By proactively moving the service in advance, the time to get an up-to-date replica is a lot smaller for state synchronization compared to service relocation. As such, service diffusion with state synchronization provides a much better usability to the user compared to plain service migration. Of course, this assumes the required bandwidth is available. The handover to the remote services worked in all cases because we avoided the case where all network connections to the remote replicated services are disrupted. In theory, our framework can handle this particular case if the remote service calls can be buffered and invoked asynchronously. However, our current

Pervasive Services on the Move

57

implementation does not support this. Interesting to note for the handover to the replicated services (in our experiment, the stateless audio service and stateful log service), is that handover to another log service takes a bit longer on average. This result is due to the fact that for the audio service we do not need to wait until the replicated service has acquired the latest revision of the service state. If state synchronization is taking place during handover, the handover delay can become higher. In our experiment, the remote services were only available on two hosts (the laptop and the desktop). If more devices would host a replicated service, the decision to handover to a particular device could depend on which replica is already completely synchronized.

5

Related Work

In recent years, many researchers have addressed the issue of state transfer, code mobility and service oriented computing in ubiquitous computing environments. This research has greatly improved our knowledge of how context-aware service oriented architectures can accommodate to new functionality requirements in changing environments. Providing a detailed review of the state of the art on all of these domains is beyond the scope of this paper. Instead, we focus on those contributions that are most related to the work presented in this paper. In [14], the OSGi platform was used to perform context discovery, acquisition, and interpretation and use an OWL ontology-based context model that leverages Semantic Web technology. This paper has inspired us to use the OSGi platform for context-aware service orientation, and more specifically service mobility. In [15], the authors present an OSGi infrastructure for context-aware multimedia services in a smart home environment. Although the application domain that we target goes beyond multimedia and smart home environments, we envision that more data driven services like multimedia applications are good candidates to further evaluate our service mobility strategies. Other context-awareness systems leveraging the OSGi framework include [16,17]. Optimistic replication is a technique to enable a higher availability and performance in distributed data sharing systems. The advantage of optimistic replication is that it allows replicas to diverge. Although users can observe this divergence, the copies will eventually converge during a reconciliation phase. In [18], the authors provide a comprehensive survey of techniques developed to address divergence. Our current service replication and state synchronization is more related to traditional pessimistic replication, because user perceived divergence might cause confusion. As discussed in [19], we will further investigate how optimistic replication can improve the quality of service in mobile computing, while keeping the user perceived divergence at an acceptable level. Remote service invocation on the OSGi framework is an issue that has been addressed by several researchers and projects. The Eclipse Communication Framework [20] provides a flexible approach to deal with remote services and service discovery on top of the Equinox OSGi implementation. Remote OSGi

58

D. Preuveneers and Y. Berbers

services can be called synchronously and asynchronously on top of various communication protocols. The R-OSGI [21] framework also deals with service distribution. While both projects address network transparency for OSGi services, neither of them deals with explicit service mobility. The Fluid Computing [22] and flowSGI [23] projects explicitly deal with state transfer and synchronization in a similar way to ours. They also discuss state synchronization and provide a more advanced state conflict resolution mechanism. Our contribution builds upon this approach and specifically focuses on service oriented applications. Our method also enhances the peer selection for service replication by using context information of the service and the device. This approach provides better guarantees that the application will actually work on the device.

6

Conclusions and Future Work

This paper presents a context-driven approach to live service mobility in pervasive computing environments. It focuses on service migration and diffusion to multiple hosts to increase accessibility and expedite human interaction with the service. We summarized the basic requirements for service mobility, including enhanced service descriptions, context-awareness to select appropriate targets for service migration, and life-cycle management support to carry out service relocation with state transfer and state synchronization. We have discussed how we implemented these requirements on top of the OSGi framework and validated our prototype by means of several applications that are replicated in a small scale network with enforced network failures. We studied the effects of service migration and service diffusion. Service migration moves an application from one host to another including its state, while service diffusion replicates the service and the state on multiple hosts. State synchronization ensures that each service can be used interchangeably. Experiments have shown that the overhead of state transfer and synchronization is limited for relatively small applications. The results illustrate that, if the available network bandwidth permits, the time to keep the state in sync is a lot smaller than to migrate a service from one host to another. This means that if a user wants to use another device because it provides a better quality of service (e.g. the bigger screen in the scenario), that proactive service diffusion provides a much better usability (i.e. shorter delays). Future work will focus on a better handling of state synchronization conflicts and improving the state encapsulation approach to deal with incremental state transfers for data intensive applications. However, our main concern will always be to keep the supporting infrastructure flexible and lightweight enough for lowend devices with room left to actually run applications. The outcome of this future work could result in a better policy with respect to on how many remote devices a service should be replicated and under which circumstances service migration would be a better approach compared to service diffusion.

Pervasive Services on the Move

59

References 1. Weiser, M.: The computer for the 21st century. Scientific American 265, 94–104 (1991) 2. Papazoglou, M.P., Georgakopoulos, D.: Service oriented computing. Commun. ACM 46, 24–28 (2003) 3. Shaw, M., Garlan, D.: Software architecture: perspectives on an emerging discipline. Prentice-Hall, Inc., Upper Saddle River (1996) 4. Dey, A.K.: Understanding and using context. Personal Ubiquitous Comput. 5, 4–7 (2001) 5. Open Services Gateway Initiative: OSGi Service Gateway Specification, Release 4.1 (2007) 6. Helal, S.: Standards for service discovery and delivery. Pervasive Computing, IEEE 1, 95–100 (2002) 7. Kramer, J., Magee, J.: The evolving philosophers problem: Dynamic change management. IEEE Trans. Softw. Eng. 16, 1293–1306 (1990) 8. Vandewoude, Y., Ebraert, P., Berbers, Y., D’Hondt, T.: An alternative to quiescence: Tranquility. In: ICSM 2006: Proceedings of the 22nd IEEE International Conference on Software Maintenance, Washington, DC, USA, pp. 73–82. IEEE Computer Society, Los Alamitos (2006) 9. Preuveneers, D., den Bergh, J.V., Wagelaar, D., Georges, A., Rigole, P., Clerckx, T., Berbers, Y., Coninx, K., Jonckers, V., Bosschere, K.D.: Towards an extensible context ontology for Ambient Intelligence. In: Markopoulos, P., Eggen, B., Aarts, E., Crowley, J.L. (eds.) EUSAI 2004. LNCS, vol. 3295, pp. 148–159. Springer, Heidelberg (2004) 10. Mokhtar, S.B., Preuveneers, D., Georgantas, N., Issarny, V., Berbers, Y.: EASY: Efficient SemAntic Service DiscoverY in Pervasive Computing Environments with QoS and Context Support. Journal Of System and Software 81, 785–808 (2008) 11. Preuveneers, D., Berbers, Y.: Encoding semantic awareness in resource-constrained devices. IEEE Intelligent Systems 23, 26–33 (2008) 12. Burke, B., Monson-Haefel, R.: Enterprise JavaBeans 3.0, 5th edn. O’Reilly Media, Inc, Sebastopol (2006) 13. Mattern, F.: Virtual time and global states of distributed systems. In: Parallel and Distributed Algorithms: proceedings of the International Workshop on Parallel and Distributed Algorithms 14. Gu, T., Pung, H.K., Zhang, D.Q.: Toward an osgi-based infrastructure for contextaware applications. Pervasive Computing, IEEE 3, 66–74 (2004) 15. Yu, Z., Zhou, X., Yu, Z., Zhang, D., Chin, C.Y.: An osgi-based infrastructure for context-aware multimedia services. Communications Magazine, IEEE 44, 136–142 (2006) 16. Lee, H., Park, J., Ko, E., Lee, J.: An agent-based context-aware system on handheld computers, 229–230 (2006) 17. Kim, J.H., Yae, S.S., Ramakrishna, R.S.: Context-aware application framework based on open service gateway 5, 200–204 (2001) 18. Saito, Y., Shapiro, M.: Optimistic replication. ACM Comput. Surv. 37, 42–81 (2005) 19. Kuenning, G.H., Bagrodia, R., Guy, R.G., Popek, G.J., Reiher, P.L., Wang, A.I.: Measuring the quality of service of optimistic replication. In: ECOOP Workshops, pp. 319–320 (1998)

60

D. Preuveneers and Y. Berbers

20. The Eclipse Foundation: Eclipse Communication Framework (2007), http://www.eclipse.org/ecf/ 21. Rellermeyer, J.S., Alonso, G., Roscoe, T.: Building, deploying, and monitoring distributed applications with eclipse and r-osgi. In: Eclipse 2007: Proceedings of the 2007 OOPSLA workshop on eclipse technology eXchange, pp. 50–54. ACM, New York (2007) 22. Bourges-Waldegg, D., Duponchel, Y., Graf, M., Moser, M.: The fluid computing middleware: Bringing application fluidity to the mobile internet. In: SAINT 2005: Proceedings of the The 2005 Symposium on Applications and the Internet (SAINT 2005), Washington, DC, USA, pp. 54–63. IEEE Computer Society, Los Alamitos (2005) 23. Rellermeyer, J.S.: flowsgi: A framework for dynamic fluid applications. Master’s thesis, ETH Zurich (2006)

Robots in Smart Spaces - A Case Study of a u-Object Finder Prototype Tomomi Kawashima1, Jianhua Ma1, Bernady O. Apduhan2, Runhe Huang1, and Qun Jin3 1 Hosei University, Tokyo 184-8584, Japan [email protected], {jianhua, rhuang}@hosei.ac.jp 2 Kyushu Sangyo University, Fukuoka 813-8503, Japan [email protected] 3 Waseda University, Saitama 359-1192, Japan [email protected]

Abstract. A smart space is a physical spatial environment such as a room that can provide automatic responses according to the contextual information occurring in an environment. The context data is usually acquired via various devices which are installed somewhere in the environment and/or embedded into some special physical objects, called u-objects, which are capable of executing computation and/or communication. However, the devices used in current researches on smart space are either fixed or residing in real objects, which are incapable of moving by themselves. Likewise, more and more robots have been produced, but most of them are designed and developed based on the assumption that the space surrounding a robot is an ordinary one, i.e., a non-smart space. Therefore, it is necessary to study what additional services can be offered and what specific technical issues will be faced when adding robots to smart spaces. To identify the potential novel services and technology problems, this research is focused on a case study of a u-object finding service performed by a robot in a smart space. This paper presents the design and development of the system prototype robot which can communicate with other devices and can find a u-object with attached RFID tag in a smart room. Some preliminary experiments were conducted and the results verified the functionalities of the system.

1 Introduction The essential of ubiquitous computing (ubicomp), as emphasized by Mark Weiser, is “enhancing computer use by making many computers available throughout the physical environment, but making them effectively invisible to the user” [1, 2]. The synergy of ubiquitous computing and communications is the natural result of two fundamental technology trends: (1) the continuing miniaturization of electronic chips and electro-mechanical devices following Moore’s law, and (2) their interconnection via networks especially using wireless communications. Aside from the widespread use and popularity of wireless technology such as IEEE802.11 a/b/g [3] and Bluetooth [4], the WPAN (Wireless Personal Area Network) [5, 6] and high-speed wireless F.E. Sandnes et al. (Eds.): UIC 2008, LNCS 5061, pp. 61–74, 2008. © Springer-Verlag Berlin Heidelberg 2008

62

T. Kawashima et al.

networks using UWB (Ultra Wide Band) [7] will soon be available and will play important roles in short range ubiquitous communications. Due to the continuing miniaturization and availability of high-speed communications, many devices can be distributed to surrounding ambient environments and make the ordinary environments capable of computing. That is, a real spatial environment such as a room may become smart to take automatic responses according to the contextual information [8, 9] occurring in this environment. The context data is usually acquired via various devices which are installed somewhere in the environment and/or embedded into some special physical objects. Real physical objects are called u-objects [10], as opposed to virtual e-things, if they are attached, embedded or blended with computers, networks, sensors, actors, IC-tags and/or other devices [11]. The smart space/environment, as one of the major ubicomp areas, has recently received much attention, and various smart space systems have been developed to make smart homes, smart offices, smart classrooms, etc. [12, 13]. However, the devices used in the current smart space researches are either fixed or residing in real objects that cannot move on their own. On the other hand, robotics is an exciting field that has been getting a great deal of attention for decades. Lots of robots have been produced and deployed to various applications such as in games, entertainment, household chores, rescue, military, and manufacturing [14]. The robots can also be seen as some special kinds of smart u-objects with partial human-like or animal-like behaviors. The most special characteristic of robots are that they can move by themselves according to the received instructions or perceptual information. However, most of them are designed and developed based on the assumption that the space surrounding a robot is an ordinary one, i.e., a non-smart space [15, 16]. It is then interesting and worth investigating to know what new services can be offered by smart spaces in which robots exist, and what new technical issues arise when combining smart spaces and robots to make smart systems. Flipcast [17] showed a design of an agent-based platform for communications between robots and ubiquitous devices, but it was not based on a smart space and did not give any concrete examples. Generally, there is almost no systematic research on integrated systems with some combination of robots and smart spaces. One way to approach the systematic research would be to start making concrete and representative sample applications. Therefore, this research is focused on a case study of a u-object finding service done by a robot in a smart space. This paper presents the design and development of a system prototype to manage robots and u-objects attached with RFID tags in a smart room space, and for a robot to communicate with other devices and find a tagged uobject in the smart space. We have conducted some preliminary experiments and the result verifies and evaluates the aforementioned functionalities. In what follows, we first check the possible roles of robots in a smart space as well as the relevant technical problems in general, and then present the u-object finding robot prototype in detail in the remaining sections. After showing the prototype overview in Section 3, we explain how to manage robots and u-objects in Section 4, and how to control and communicate with the robots in Section 5. The experimental

Robots in Smart Spaces

63

environment and results in finding u-objects are described in Section 6. Finally, the conclusion and future work are addressed in the last section.

2 General Services and Issues of Smart Spaces with Robots This section will discuss in general the special roles of robots in a smart space and the related basic issues to be solved in order to provide the desired services of robots. A smart space that can offer automatic services mainly relies on the sensing devices to acquire contextual information, and actuation devices to take responsive actions. As mentioned earlier, these devices are usually installed in some parts of the physical environment; such as walls, or embedded in some physical objects such as books. Because such devices are fixed and don’t move by themselves, they can sense information or act only in specific locations/directions. Different from these devices, robots are capable of moving from one location to another in a space. In addition, many robots can carry sensors and/or actuators. Therefore, a robot can move to a place to sense information or take an action in that place. For example, a movable robot can monitor a place from any direction using its camera to record the condition of a house, office, classroom, shop, street, and so on. Another example is that a robot, under instruction by a virtual host/manager of the smart environment, may bring an object from somewhere in the environment. In general, additional service functions which can be done by robots in smart spaces fall into the following categories. Location-Varied Information Acquisition: When carrying sensors, a robot can get the requested information not only at a specified location, but also from some data distributed in a space. For example, a robot with a microphone can move around to locate a sound source, which is usually hard to precisely detect by fixed microphones. The temperature distribution in a room can also be easily gathered by a movable robot by carrying only a single temperature sensor. Otherwise, many temperature sensors have to be installed in different parts of a relatively large room. That is, robots can function as mobile sensors to collect information at any point in smart space where they can possibly go. Location-Dependent Responsive Action: According to the sensed information, a smart space can take responsive actions. Some reactions may be conducted best at some specific locations. For example, the sound-aware smart room we developed [18] can sense ambient sounds using a microphone array, and output a speech to one of the speakers installed in a fixed location in the room. It sends a be-quiet reminder speech to a speaker near the person who is talking/singing loudly who may disturb others in the same location. Having a robot carrying a speaker in the room, the robot can move near the person and then give the reminder. In general, a robot may conduct some action by moving to a place requested by a smart space. Location-Aware Interaction with Devices/u-Objects: When a robot works in a nonsmart environment, it has to sense and interact with the environment using multimedia data from cameras, microphones, and so on. Therefore, the sophisticated robots rely on complex intelligent technologies for multimedia processing and understanding,

64

T. Kawashima et al.

which are not yet perfect and are very costly. In a smart environment, however, there are various electronic devices which are either independent or embedded in some objects, i.e., being u-objects. Thus, robots will be able to interact with these devices or u-objects via wireless electronic communications, instead of using audiovisual communications. Through communications, a robot may interact with nearby u-objects to identify their locations, know what they are doing, etc. By means of interaction, the robots and devices/u-objects in a smart room can work collaboratively to carry out some tasks. In summary, robots can be applied to add flexible location-based service functions to smart spaces because of their capability to move. To realize the new functions, a robot must collaboratively work with a virtual space host/manager and other devices/u-objects in the space. Therefore, the two fundamental issues for robots to conduct collaborative work in a smart space are how to manage the robots, and how to enable robots to communicate with the space host and various devices/u-objects. A long-term solution to completely solve the management and communication issues would be a scalable framework or middleware capable of supporting many applications in different smart spaces with multiple robots and heterogeneous devices/u-objects. This preliminary study is focused on the necessary management and communications in a specific application, i.e., a prototype called u-object finder, a robot for finding u-object(s).

3 The u-Object Finder Overview It is a very common experience that sometimes we forget and could not immediately find some common items which we need badly, such as keys or books. This is more common to small children and elder people since they often forget what they have just seen or done. The u-object finder (UOF) is an application of the smart space in which a robot moves around to search for a lost object. Figure 1 shows the UOF conceptual environment used in our study and its development.

㫌㪄㪦㪹㫁㪼㪺㫋㩷㪝㫀㫅㪻㪼㫉

㪬㪦㪝㪄㪤㪸㫅㪸㪾㪼㫉 㪩㪝㪠㪛㩷㪩㪼㪸㪻㪼㫉

㫌㪄㪦㪹㫁㪼㪺㫋 㪩㪝㪠㪛㩷㪫㪸㪾㫊 㪬㪦㪝㪄㪩㫆㪹㫆㫋

Fig. 1. The u-object finder environment

Robots in Smart Spaces

65

The environment is a typical room space equipped with computers, devices, and robots which are connected by wireless networks. Basic assumptions to the environment are as follows.

・ ・ ・ ・

・ ・

Every object to be searched must be attached or embedded with at least one device which is used to uniquely identify the object and communicate with other devices. In the present prototype, we attached a RFID tag to every searchable uobject, also called a tagged object. A single object may have multiple attached tags, which can be used to either identify different parts of the object, or to improve search efficiency. A RFID reader is installed somewhere at the room entrance to read the RFID tag of a u-object when the object passes through the entrance. It is used to detect what and when a u-object has been brought in/out of the room. There is one or more movable robots in the room which moves according to the commands and instructions from a room manager. Each robot may carry multisensors for various purposes. To find a tagged object, a RFID reader is carried by the robot in our system. A number of RFID tags are set at fixed positions on the room floor. These tags are used for the robot to precisely locate its position since all the position data has been measured and kept in some room database. Usually a robot can remember the route it has passed, which can be used to estimate the robot’s present position. The electric-magnetic signal strength received by the robot from wireless routers can be also used to estimate its position, but this exhibits some errors in estimating the robot’s position. Thus, the position-fixed RFID tags on the floor can be read when the robot moves, and exploited to reduce or correct the errors. All machines and devices including robots are able to conduct wireless communications via either some specific communication scheme or a common wireless LAN router. There exists a virtual manager, i.e. an application residing on a PC, to manage all devices, u-objects, RFID tags and robots. It also provides an interface for a user to request a robot to find an object and receive the search result via our present UOF prototype.

The u-Object Finder system, as shown in Fig. 2, is mainly composed of the uObject Finder Manager (UOF-Manager) that functions as a central administrator of all devices including robots, and the u-Object Finder Robot (UOF-Robot) that is mainly in charge of searching u-objects in the room. The UOF-Manager has two main components: the u-Object Manager (O-Manager) to manage u-objects, and the Robot Manager (R-Manager) to manage robots. On the other hand, the UOF-Robot has two main components: the Robot Controller (RController) and the Robot Machine (R-Machine). The R-Machine is some kind of robot that has a motor, wheels, an ultrasonic sensor, etc., and thus movable by itself. When the robot moves near a barricade or blocks, it can turn and change direction using the data from the ultrasonic sensor. The movement direction, destination and route will be determined according to the robot’s task, current position, surrounding

66

T. Kawashima et al.

UOF- Manager R- Manager O- Manager

UOF- Robot IEEE802.11b

Bluet oot h

Radio Frequency

u- Object

R- Controller (PDA)

Radio Frequency

R- Machine (Robot)

Fig. 2. The u-object finder components

situations, and so on. The R-Controller functions as a mediator between R-Manager and R-Machine, and runs on a PDA that is carried by the robot. The PDA provides a popular programming environment and adopts the general TCP/IP communication protocol on top of common wireless LANs. A RFID reader and other wired sensors can be also connected directly to this PDA. Therefore, the PDA can greatly extend and enhance the functions of a low-cost robot. The PC, PDA, robot and devices are connected via several networks including IEEE 802.11b LAN, Bluetooth, and radio frequency communication between an RFID reader and an RFID tag. The general procedure to search a u-object is conducted in the following steps. At first, a user informs the UOF-Manager what u-object to search. The UOF-Manager will find out if the object is in the room by checking the object’s existence status kept in the u-object database. If it is in the room, the UOF manager will check if any UOFRobot is available in the room to do the search job. When a robot is available, the UOF-Manager will send an object finding command and the RFID tag number(s) of the u-object to the UOF-Robot. Then, the robot moves around and reads the nearby RFID tags. Once the tag number of the searched object is detected, the UOF-Robot will stop and send the UOF-Manager a search success message. At the same time, the robot will give a speech or a beeping sound to notify the user of its location, which is near to the found u-object. If the u-object cannot be found after a certain time, the UOF-Robot will send an unsuccessful message to the UOF-Manager. The next two sections will explain the UOF-Manager and UOF-Robot in details, respectively.

4 UOF-Manager The UOF-Manager is an application working on a PC. A user can operate the UOFRobot and manage the u-Object respectively using the UOF-Manager. The UOFManager consists of a UOF-GUI, an R-Manager (Robot-Manager) and an O-Manager (u-Object Manager), as shown in Fig. 3. The user can register and delete a u-Object by simply holding it over an RFID reader. The data of the registered u-Object is saved in the u-Object database by the O-Manager.

Robots in Smart Spaces

67

UOF- GUI

R- Manager

Operation Retrieval Connection Module Module Module

UFCP Stack

O- Manager

Registration Status Module Module

u- Object Database

Fig. 3. The UOF-Manager component

4.1 UFCP (U-object Finder Control Protocol) To manage robots and let them work in a smart space, the R-Manager and robots must be first enabled to communicate with each other. One objective of this study is to develop the UFCP stack based on TCP/IP, which will run the R-Manager, RController and R-Machine. It is a protocol for the UOF-Manager to retrieve and operate the UOF-Robot via message exchanges. The UFCP messages are in two forms: UFCP-TCP and UFCP-UDP. The UFCP-UDP is used to retrieve the UOF-Robots in the same network segment, while the UFCP-TCP is used to operate the UOF-robots. The format of the UFCP packet takes on ASCII. The UFCP packet has two fields: command and data, separated by a comma. Table1 shows the message format of UFCP-TCP and UFCP-UDP. 4.2 R-Manager The R-Manager has the UFCP Client which can search a UOF-Robot, make a connection, start and stop the UOF-Robot, change the threshold value of devices (ultrasonic sensor, motor), and get the status of the UOF-Robot. Through the UOF-GUI, a user can conduct the following management functions.

・ Retrieving the UOF-Robot ・

When receiving a robot retrieval demand from a user, the U-Manager will broadcast a UFCP robot search message over connected wireless LANs. The UOFRobot receiving the message will reply an acknowledgment message with its name and current position. The list of retrieved UOF-Robot is shown in UOFGUI. Connection of the UOF-Robot After the user selected one UOF-Robot from the retrieved UOF-Robot list, the user can make a connection using UFCP to the selected UOF-Robot. After the connection is established, the user can start to operate the robot.

68

T. Kawashima et al. Table 1. UFCP message format

UFCP- TCP DATA DESCRIPTION COMMAND UOF- ROBOT START RFID Starting u- Object finding UOF- ROBOT STOP Stopping u- Object finding ACK VALUE, POSITION, etc. Acknowledgement NAK ERROR MESSAGE Negative acknowledgement GET STATUS Getting UOF- Robot status GET VALUE DEVICE NAME Getting specified device’ s value GET POSITION Getting UOF- Robot position SET VALUE DEVICE NAME, VALUE Setting specified device’ s value FOUND RFID Informing found RFID tag SOUND Request for playing sound UFCP- UDP DATA DESCRIPTION COMMAND SEARCH Searching UOF- Robot ACK UOF- ROBOT NAME Acknowledgement

・ Operation of the UOF-Robot

The UOF-Manager can specify which robot will search a u-object through its RFID, can start and stop the UOF-Robot, or get the status of the UOF-Robot. In addition, the UOF-Manager can ask the UOF-Robot to produce a beeping sound to inform the user of its current position in the smart room.

4.3 O-Manager The O-Manager handles the registration and deletion of a new u-Object. When the user holds the RFID attached to an u-Object over an RFID reader, the O-Manager obtains the RFID data through the RFID reader and check whether the RFID is already registered or not. If the RFID is not yet registered, the O-Manager shows a popup window for the user to input the name of the u-Object associated with the RFID. After the user input the name successfully, the user can select the u-Object to be searched in the smart room. The user can also register a u-Object by not using an RFID reader but by inputting the RFID data and name manually. Another function of the O-Manager is to manage the existence status of all registered u-objects. A registered object can be brought out/back to the room. The u-object’s in/out state and corresponding time can be detected by the RFID reader installed at the room entrance. When a UOF-Robot moves around the room, it may encounter many u-objects including the one to be searched and others which are not to be searched. Actually, the positions’ data of all u-objects encountered by the robot can be kept in the u-object database. These existence and position status information can be further used to speedup the searching and tracing of u-objects.

Robots in Smart Spaces

69

5 UOF-Robot As explained in the previous sections, the UOF-Robot is mainly in charge of searching a u-object in the room space. The search is based on two special functions. The first is that, the UOF-Robot can move around the space; and the second is that, the robot carries a RFID reader to detect a RFID tag within a certain distance, e.g. 10cm. The UOF-Robot consists of a R-Controller, a R-Machine and a R-Reader, as shown in Fig. 4.

R- Controller (PDA) R- Machine

R- Controller (PDA)

UFCP Stack ht oot eu lB

R- Machine

UFCP Stack Motor Ultrasonic Sensor

Device Driver B S U

R- Reader

Fig. 4. The UOF-Robot components

Ultrasonic Sensor

Motor R- Reader

Fig. 5. A snapshot of the UOF-Robot

The R-Controller resides in a PDA and is used to communicate and control both the R-Machine and the R-Reader. The R-Reader is a RFID reader that is connected to the PDA via a USB cable. A manufacturer-dependent device driver should be installed in the PDA for the R-Controller to communicate with the R-Reader. The RReader’s task is relatively simple, i.e., mainly reading the nearby tags and sending the tags’ codes to the R-Controller. The R-Machine is a self-movable robot that has a motor, wheels, an ultrasonic sensor, etc. Figure 5 shows a snapshot of the UOF-Robot used in our system. The R-Machine can start to move or stop by following the instructions from the RController. The R-Machine can move around by itself by sensing the surrounding situations with its ultrasonic sensor. The sensor can measure the distance between the R-Machine and the object in front. When the distance from an encountered barricade or block is below some threshold value, it may move away from the barricade/block, and change its moving direction. The changes of rules on the robot’s turn movement and the degree of direction are programmable, and can be set by the user on the UOFGUI. Although the R-Machine is operated by the R-Manager, their interaction messages during operations are mediated via the R-Controller. The R-Controller communicates with the R-Manager over a wireless LAN (IEEE802.11b), and also communicates with the R-Machine using a Bluetooth network, which is embedded in the robot. Like the R-Manager, the UFCP stack runs on both the R-Controller and R-Machine. Therefore, the three of them can exchange

70

T. Kawashima et al.

messages with each other. When receiving a robot retrieval message request from RManager, the R-Controller sends a UFCP-UDP response message to the R-Manager. The operation request, on the other hand, is sent as an UFCP-TCP message. When the robot moves, the R-Reader detects whether there is any RFID tag nearby. If it detects one, it sends the tag code to the R-Controller which will check whether the code is the same as the u-object’s code to be searched. When the RController gets the RFID code of the u-object to be searched from the R-Reader, it sends a found message in UFCP-TCP format to the UOF-Manager. In addition, when it detects a position tag which is set on the floor in a smart room, it also sends the UOF-Manager the tag code, which can be used to get the current robot position. An operation message from the UOF-Manager is resent to the R-Machine by the RController via the Bluetooth network.

6 System Implementation and Experiment A preliminary u-object finding prototype has been implemented with emphasis on communications between heterogeneous devices across different physical networks, and management of the robots and u-objects. The following devices and software were used in our current implementation.

・ ・ ・ ・

Robot: Mindstorm NXT including an Ultrasonic sensor and a Motor developed by LEGO [19]. It adopts lejOS [20] to control the robot movement and set some moving parameters. The ultrasonic sensor is installed in front of the robot. RFID tag and reader developed by Phidgets, Inc [21]. Java-based API which can run on Windows, Linux and Mac OS X platforms. The RFID tags were attached in all objects to be searched, and were also set on some locations on the room floor. The readable distance between a tag and a reader is about 5cm. PDA: AXIM series by Dell, Inc. It runs on Windows Mobile OS and supports .NET Compact Framework. Networks: wireless LAN (IEEE 802.11a/b/g) between the PC and PDA, and Bluetooth between PDA and NXT robot. The USB cable is used to connect a Phidgets tag reader to the PDA.

The u-object finding system is developed using Java programming language. Its software consists of three main parts. The first one is the UFCP, which is a TCP/IPbased common communication platform running on PC, PDA and robot. The UFCP is a very light protocol, only about 50Kbytes, and thus able to run low-spec devices. The second one is the R-Controller running on the PDA. It has multiple functions; such as interacting with the UOF-Manager to get commands and send back results, checking the tag codes from the R-Reader, controlling the R-Machine, and mediating messages between the R-Manager and the R-Machine. The third one is the UOF-Manager running on a PC, which manages both robots and u-objects, and also provides a GUI to interact with a user. To test our system, the experimental environment was set up in our laboratory room, and a partial setting is shown in Fig. 6. The space is 5mx5m on which there is one tagged object to be searched, a robot to search the object, some position tags fixed on the floor, etc.

Robots in Smart Spaces

71

Fig. 6. The UOF experiment environment

When a user wants to find an object in the space, he/she first starts the UOFManager, which is a Java application program running on a PC. Figure 7 shows the snapshot of the manager’s UOF-GUI. All u-objects registered in this room are listed on the upper-left of the GUI. From the u-object list, the user selects the desired object to be found. Next, the user can check what UOF-Robots are available in the room by clicking a robot retrieval button. As shown in the bottom-left of Fig. 7, one robot is retrieved through communications between the R-Manager on the PC and the R-Controller on the PDA carried by the robot. When the UOF-Manager makes a connection with the UOF-Robot successfully, a new tab window is added to the right side of GUI. At the same time, the robot appears at its present position in the middle-right map of the GUI. Some parameters related to the robot movement are displayed as well. The user can operate the UOF-Robot using the buttons and the text field on the tab window. Upon receiving the instruction to find a u-object, the UOF-Manager will send a “START” message command which sends the u-object tag code to the R-Controller of the selected UOF-Robot. Then, the R-Controller gives the “START” command to the R-Machine and asks the R-Reader to read the RFID tags. When the robot moves around, the R-Reader sends every tag code it has detected to the R-Controller. The R-Controller compares the tag code received from the R-Reader with the tag code of the searched u-object. If the two codes are the same, it means that the searched object is very near the robot. Thus, the R-Controller sends a “STOP” command to the R-Machine, and a “FOUND” message to the UOF-Manager. And then, the robot stops and generates a beeping sound to notify the user of its location. If the u-object is not yet found within the specified period of time, the search operation is considered a failure, and then the process is terminated. In our experimental environment, the u-object was found in many cases, but the search time varied greatly depending upon the positions of the robots and the uobject. This is mainly due to the short readable distance between a RIFD read and a

72

T. Kawashima et al.

Fig. 7. A snapshot of the UOF-Manager GUI

tag, and the robot’s moving course in our current implementation which is based on a rather simple algorithm that the UOF-Robot monitors the distance value from its ultrasonic sensor and turns left or back whenever the distance between the robot and barrier becomes less than 10cm. Although the searching performance is unsatisfactory, the whole system works well in terms of communications and management of the robots and devices in the smart space.

7 Conclusion and Future Work The smart space/environment and robotics are used to be studied as two separate research disciplines. It is therefore very significant to study their combination so as to form a new merged research area and generate some novel applications. Based on this idea, we first investigated the potential services and possible new technical issues when integrating the robots into smart spaces, and then focused on a case study of a uobject finding movable robot prototype to search a u-object, which is attached with RFID tags, in a smart room space. We have discussed the design and implementation as well as experiments of the developed system prototype. As mentioned in the previous section, the research presented in this paper is mainly for communications and management of robots and u-objects in a smart space. However, the object searching procedure took a long time and thus it’s inefficient. This is because of two problems: the short reading distance (about 10cm) between the RFID reader and a tag, and the course was simple for the robot’s movement. To overcome the former limitation, the RFID tag with longer reading distance such as 30~50cm will be used in our next study. Multiple tags can be attached on the different sides of a large object to improve the searching efficiency. In addition, a set of RFID readers which can read tags within 1~2m may be installed in fixed locations to first detect the possible region where the u-object is located and the robot can go directly to the

Robots in Smart Spaces

73

region to find the more precise position of the u-object. To overcome the second limitation, the robot must be able to remember the route passed and the obstacles encountered to avoid going to the same places repeatedly. Another interesting approach is to ask two or more robots to search a u-object together, and study how the robots collaborate with each other. Aside from the above, there are still many technical problems and challenging issues to tackle when combining robots and smart space which should be studied along with many kinds of applications in the future.

Acknowledgement This work was partially supported by Japan Society for the Promotion of Science Grants-in-Aid for Scientific Research, 19200005.

References 1. Weiser, M.: Ubiquitous Computing. IEEE Computer (October 1993) 2. Weiser, M., Brown, J.S.: The Coming Age of Calm Technology. In: Denning, P.J., Metcalfe, R.M. (eds.) Beyond Calculation: The Next Fifty Years of Computing (1996) 3. IEEE802.11, http://www.ieee802.org/11/ 4. Bluetooth, http://www.bluetooth.org/ 5. Callaway, E., Gorday, P., Hester, L., Guiterrez, J.A., Naeve, M.: Home Networking with IEEE802.15.4: A Developing Standard for Low-Rate Wireless Personal Area Networks. IEEE Communications Magazine, 70–77 (August 2002) 6. IEEE802.15 Working Group for WPAN, http://www.ieee802.org/15/ 7. Porcino, D., Hirt, W.: Ultra-Wideband Radio Technology: Potential and Challenges Ahead. IEEE Communications Magazine, 66–67 (July 2003) 8. Dey, A.K.: Understanding and Using Context. Personal and Ubiquitous Computing 5(1), 4–7 (2001) 9. Abowd, G.D., Mynatt, E.D., Rodden, T.: The Human Experience. IEEE Pervasive Computing, 48–57 (January-March 2002) 10. Ma, J.: Smart u-Things – Challenging Real World Complexity. In: IPSJ Symposium Series, vol. 2005(19), pp. 146–150 (2005) 11. Private, G.: Smart Devices: New Telecom Applications & Evolution of Human Interfaces. In: CASSIS Int’l Workshop, Nice (March 2005) 12. Cook, D.J., Das, S.K.: Smart Environments: Technologies, Protocols and Applications. Wiley-Interscience, Chichester (2005) 13. Ma, J., Yang, L.T., Apduhan, B.O., Huang, R., Barolli, L., Takizawa, M.: Towards a Smart World and Ubiquitous Intelligence: A Walkthrough from Smart Things to Smart Hyper-spaces and UbicKids. International Journal of Pervasive Comp. and Comm. 1(1) (March 2005) 14. Pinto, J.: Intelligent Robots Will Be Everywhere, in Automation.com (2003), http://www.jimpinto.com/writings/robots.html 15. Sakagami, Y., Watanabe, R., Aoyama, C., Matsunaga, S., Higaki, N., Fujimura, K.: The intelligent ASIMO: System Overview and Integration. Intelligent Robots and System (2002)

74

T. Kawashima et al.

16. Kaneko, K., Kanehiro, F., Kajita, S., Hirukawa, H., Kawasaki, T., Hirata, M., Akachi, K., Isozumi, T.: Humanoid Robot HRP-2 (ICRA 2004) (April 2004) 17. Ueno, K., Kawamura, T., Hasegawa, T., Ohsuga, A., Doi, M.: Cooperation between Robots and Ubiquitous Devices with Network Script Flipcast. In: Proc. Of Network Robot System: Toward Intelligent Robotic Systems Integrated with Environments (IROS) (2004) 18. Ma, J., Lee, J., Yamanouchi, K., Nishizono, A.: A Smart Ambient Sound Aware Environment for Be Quiet Reminding. In: Proc. of IEEE ICPADS/HWISE 2005, Int’l Workshop on Heterogeneous Wireless Sensor Networks, Fukuoka (July 2005) 19. Lego Mindstorm NXT, http://mindstorms.lego.com 20. lejOS, http://lejos.sourceforge.net/ 21. Phidgets, Inc., http://www.phidgets.com

Biometrics Driven Smart Environments: Abstract Framework and Evaluation Vivek Menon1, , Bharat Jayaraman2, and Venu Govindaraju2 1

Amrita University, Coimbatore 641 105, India vivek [email protected] 2 University at Buffalo, Buffalo, NY 14260, USA [email protected], [email protected] Abstract. We present an abstract framework for ‘smart indoor environments’ that are monitored unobtrusively by biometrics capture devices, such as video cameras, microphones, etc. Our interest is in developing smart environments that keep track of their occupants and are capable of answering questions about the whereabouts of the occupants. We abstract the smart environment by a state transition system: Each state records a set of individuals who are present in various zones of the environment. Since biometric recognition is inexact, state information is probabilistic in nature. An event abstracts a biometric recognition step, and the transition function abstracts the reasoning necessary to effect state transitions. In this manner, we are able to accommodate different types of biometric sensors and also different criteria for state transitions. We define the notions of ‘precision’ and ‘recall’ of a smart environment in terms of how well it is capable of identifying occupants. We have developed a prototype smart environment based upon our proposed concepts, and provide experimental results in this paper. Our conclusion is that the state transition model is an effective abstraction of a smart environment and serves as a basis for integrating various recognition and reasoning capabilities.

1

Introduction

The vision of pervasive computing [1] provides the inspiration for a smart environment saturated with sensors, computing, and communication devices that are gracefully interfaced with human users [2]. In this paper, we focus on smart indoor environments such as homes, offices, etc. Indoor environments do not suffer from the problems of power or battery-life that confront outdoor environments. The goal of our research is to develop smart indoor environments that can identify and track their occupants as unobtrusively as possible and be capable of answering queries about the occupants. Such ‘context-aware’ systems can identify and track people in environments ranging from homes for elderly or disabled, office workplace, department stores and shopping complexes to larger arenas such as airports, train stations, etc. 

This work was done while the author was a Visiting Research Scientist at the Center for Unified Biometrics and Sensors, University at Buffalo.

F.E. Sandnes et al. (Eds.): UIC 2008, LNCS 5061, pp. 75–89, 2008. c Springer-Verlag Berlin Heidelberg 2008 

76

V. Menon, B. Jayaraman, and V. Govindaraju

(a)

(b)

(c)

Fig. 1. Architecture of a Biometrics Driven Smart Environment

Identification approaches vary from tag-based approaches such as those involving RFID to those based on biometrics of the user. Tag-based methodologies tend to be obtrusive, requiring the individual to continuously retain them, however small the tag maybe. Some of the biometric techniques, such as fingerprint and iris scans, require a ‘pause-and-declare’ interaction with the human [3]. They are less natural than face, voice, height, and gait, which are less obtrusive and hence are better candidates for use in our smart environments. Figure 11 shows the overall architecture of a biometrics-driven smart environment. Although the figure illustrates a single biometric modality of face recognition, the architecture is also applicable to other biometric modalities. For example, zone 1 might use voice recognition, zone 2 might use face recognition, 1

Face images blurred to preserve anonymity.

Biometrics Driven Smart Environments

77

and zone 3 might use height estimation. However, in all cases the output of a biometric recognition is the set of person probability pairs as discussed in more detail below. The main contribution of this paper is a framework for abstracting the behavior of a biometrics-driven smart environment in terms of a state transition system. Our proposed framework supports multiple biometric modalities in a uniform manner and facilitates a precise statement of the performance aspects of a smart environment. The state of an environment is expressed in terms of the probabilities of the occupants being present in the different zones of the environment. The state information is probabilistic because a biometric recognizer typically provides a set of scores indicating the degree of match between the subject and the candidates in the database. Therefore, in our approach an event abstracts a biometric recognition step - whether it is face recognition, voice recognition, etc. - and is represented as a set of pairs o, p(o) where p(o) is the probability 2 that occupant o has been recognized at this event. The transition function abstracts the reasoning necessary to effect state transitions. Effectively, the transition function takes as input, a state and an event, and determines the next state by assigning revised probabilities to the occupants in the environment based upon the probabilities in the event. In this manner, we are able to accommodate different types of biometric sensors and also different criteria for state transitions, including those that incorporate declarative knowledge of the individuals and the environment. It is not necessary for us to consider non-deterministic transitions, since a state itself is represented as a set of occupants and their probabilities. We introduce the concepts of precision and recall in order to provide a quantitative measure of the performance of a smart environment. Precision captures how well an occupant is recognized, while recall captures whether an occupant is recognized at all. These are complementary concepts and together capture the overall performance of a smart environment. The concepts of precision and recall are standard performance measures in the information retrieval literature [6], but we have adapted the definitions to suit our context. The rest of this paper is organized as follows. The related work is presented in Section 2 while the details of our model are discussed in Section 3. The experimental prototype is described in Section 4 and the conclusions and the future work are presented in Section 5.

2

Related Work

There has been considerable interest in the subject of smart environments. A major difference between our proposed approach and several of the approaches surveyed below is our use of a framework in which the details of biometric recognition are abstracted simply as events in a state transition system. We also 2

Such scores can be mapped to probabilities by running the recognizer on a large number of samples, as shown in [4,5].

78

V. Menon, B. Jayaraman, and V. Govindaraju

characterize the performance of the smart environment in terms of the concepts of precision and recall. We briefly survey closely related efforts below and highlight their main features. The survey paper by Cook and Das [7] provides a good account of the stateof-the-art in smart environments. There are several projects that focus on smart homes (MavHome [8], the Intelligent Home [9], the House n [10] and development of adaptive control of home environments by also anticipating the location, routes and activities of the inhabitants. 2.1

Location Estimation

An extensive survey and taxonomy of location systems for a ubiquitous computing application is discussed in [11] while [12] provides a more recent survey of position location techniques in mobile systems and draws a comparison between their parameters. Fox et al. [13] highlight the relevance of Bayesian filtering techniques in dealing with the uncertainty characteristic of sensors in pervasive computing environments and apply them in the context of estimation of an object’s location. Data Association problem [14] is a pertinent issue in scenarios which involve tracking of multiple people using anonymous sensors. The ambiguity in identity estimation arising due to the absence of ID sensors and the corresponding tags on people is difficult to resolve. Thus identity estimation, absolute or relative is a desirable and integral subsystem of any object tracking mechanism. 2.2

Tracking

Bui et al. [15] propose an Abstract Hidden Markov Model(AHMM) based approach for tracking human movement in an office like spatial layout and to predict the object trajectories at different layers of detail. For location tracking in a single inhabitant smart space, Roy et al. [16] propose an optimal algorithm based on compressed dictionary management and online learning of the inhabitant’s mobility profile. In a related work [17], they highlight the complexity of optimal location prediction across multiple inhabitants in a smart home and propose a stochastic game-theoretic approach, which learns and estimates the inhabitants’ most likely location profiles. This study uses RFID tags to track the inhabitants. A combination of particle filters with Kalman filters to track multiple objects with accuracy of anonymous sensors and identification certainty of id-sensors is discussed in [13,18]. Krumm et al. [19] investigate the nuances of visual person tracking in intelligent environments in the context of the EasyLiving project [20] by deploying multiple cameras for tracking multiple people. However this tracking experiment was within the confines of a single room and the identity estimation and maintenance for facilitating the tracking only dealt with non-absolute, internally system generated identity of tracked persons. 2.3

Biometrics in Smart Environments

Pentland and Choudhury [3] highlight the importance of deploying audio-andvideo based recognition systems in smart environments as these are modalities

Biometrics Driven Smart Environments

79

similar to those used by humans for recognition. They summarize the face recognition efforts and discuss various commercial systems and applications as well as its novel applications in smart environments and wearable computing. Chen and Gellersen [19] propose a new method to support awareness based on fusion of context information from different sources in a work environment which included integration of audio and video sources with more specific environment sensors and with logical sensors that capture formal context. Reasoning over the context information generated by applying different perception techniques on the raw data collected is used to generate a refined context. Hamid Aghajan et al. [22] propose a vision-based technology coupled with AI-based algorithms for assisting vulnerable people and their care givers in a smart home monitoring scenario. However, users are expected to wear a wireless identification badge that broadcasts a packet upon sensing a significant signal by one of the accelerometers. Gao et al. [23] propose a new distance measure for authentication in their face recognition system for a ubiquitous computing environment which relies on a fusion of multiple views of each person. Their work focuses on optimizing a single modality to improve robustness rather than deploying a multimodal approach that fuses different biometrics. Hong et al. [24] discuss structure, operation and performance of a face verification system using Haar-like features and HMM algorithm in a ubiquitous network environment. Zhang et al. [25] propose a distributed and extensible architecture of a continuous verification system that verifies the presence of logged-in user. A Bayesian framework that combines temporal and modality information holistically is used to integrate multimodal passive biometrics which includes face and fingerprint. Driven by the proliferation of commercially available hand-held computers, Hazen et al. [26] research the improvements in identification performance by adopting a bimodal biometric approach to user identification, for use on mobile devices by integrating audio and visual biometric information in the form of voice and face. They also report significant improvements in identification performance that can stem from using dynamic video information instead of static image snapshots on a database of 35 different people. Highlighting the privacy concerns of video recording discussed in Bohn et al [27] and reliability issues of face recognition techniques for user authentication, Vildjiounaite et al. [28], deploy a fusion of accelerometer based gait recognition and speaker recognition as an unobtrusive and marginally privacy-threatening means of user authentication with personal mobile devices. They have reported improved performance in the combination mode as opposed to individual modalities for a user base of 31. More recently Bernardin Stiefelhagen [29] have implemented a system for the simultaneous tracking and incremental multimodal identification of multiple users in a smart environment which fuses person track information, localized speaker ID and high definition visual ID cues opportunistically to gradually refine the global scene model and thus increase the system’s confidence in the set of recognized identities. In terms of the focus on the use of non-obtrusive biometrics based recognition and location estimation, our work is similar to [29]. However, in our research,

80

V. Menon, B. Jayaraman, and V. Govindaraju

we propose an abstract framework where in a variety of biometric modalities can be incorporated in a uniform manner. Our approach to identity estimation deals with the absolute identity of people across multiple zones of a facility. However, we attempt to highlight the inherent uncertainty of automated face recognition by recasting the eigen distances generated by eigenface algorithm into a probability distribution of the registered faces, instead of the conventional approach of assigning the value with the least eigen distance as the matching face. This probabilistic approach to biometric recognition is a key theme around which we construct our abstract framework for a biometrics driven smart environment. 2.4

State Space Representation

It might appear that a Hidden Markov Model(HMM) would serve as an elegant basis for representing the state space. From a HMM perspective, a smart environment with n occupants and m zones can have mn distinct possible states. Thus probabilities are not associated with the states but with the transitions between them; these transition probabilities are to be learnt from past behavior or by simulation [15]. Thus an HMM approach is computationally more complex due to a state space explosion and the requirement of a priori probabilities of trajectories. In our approach, the size of a state is m ∗ n, meaning that for each of the m zones we record the probabilities of each of the n occupants being present in that zone. Therefore, in Section 4 (Evaluation), we depict a typical state as a table with n rows and m columns. The transitions from one state to another are deterministic. Therefore, given any event in a zone, the next state is unambiguously determined. In contrast with the HMM approach, we do not need to learn the transition probabilities in order to determine the next state because biometric recognition (or event) provides a direct means for effecting state transitions. Our state transition model is discussed in the next section.

3

Framework

Definition (Smart Environment). An n-person smart environment is abstracted as a state transition system (S, E, Δ) where S is the set of states labeled s0 , s1 , . . . sx ; E is the set of events labeled e1 , e2 , . . . ex and Δ : S × E → S is a function that models the state transition on the occurrence of an event. The state transitions may be depicted as follows: e

e

e

1 2 x s0 → s1 → s2 . . . → sx

We shall consider a smart environment as being divided into a number of zones, each of which may be a region (or a set of rooms). We include two special zones, an external zone and a transit zone, for the sake of convenience. Definition (State). Given n occupants, o1 . . . on and m zones labeled 1 . . . m, a state sk of the environment is represented by an m-tuple Z1k . . . Zmk  where for 1 ≤ j ≤ m, Zjk= {oi , pjk (oi ) : 1 ≤ i ≤ n}. Also, in each state sk and for m each occupant oi , i=1 pjk (oi ) = 1.

Biometrics Driven Smart Environments

81

The state of an environment is expressed in terms of the probabilities of the occupants being present in the different zones of the environment. The constraint m i=1 pjk (oi ) = 1 indicates that sum of probabilities of any occupant being present across all the zones in any state equals one. In the initial state s0 , we may assume without loss of generality that all occupants are in the external zone with probability 1. Given a smart environment with n occupants, m zones, and x number of events, the total size of the state space is m ∗ n ∗ (x + 1). Thus, the size of the state space is quadratic in m and n rather than exponential, as in HMMs. In this paper we model all exit events as entry events into a transit zone. Hence it suffices in our model to only consider entry events. An event is essentially an abstraction of a biometric or feature recognition step performed in the environment. Definition (Event). Given n occupants o1 . . . on , an (entry) event ek occurring at zone j (1 ≤ j ≤ m) at time t is represented as t, j, P , where P = {oi , pjk (oi ) : 1 ≤ i ≤ n} and pjk (oi ) is the probability that an occupant oi was recognized at zone j in event ek . As noted earlier, an event is an abstraction of a recognition step. For simplicity, we assume that events happen sequentially in time, i.e., simultaneous events across different zones are ordered arbitrarily in time. That is, the entry of an occupant oi into zone zi and occupant oj to zone zj at the same time t can be modeled as oi before oj or oj before oi . Definition (Transition Function). Δ : S × E → S, maps state sk−1 into state sk upon an event ek = t, j, P  occurring at time t in zone j, where P = {oi , pjk (oi ) : 1 ≤ i ≤ n}. Let sk−1 = Z1k−1 . . . Zjk−1 . . . Zmk−1  and Zjk−1 = {oi , pjk−1 (oi ) : 1 ≤ i ≤ n}. Then Δ determines state sk = Z1k . . . Zjk . . . Zmk  as follows: Let xi = 1 − pjk (oi ). Then, Zjk = {oi , pjk (oi ) + xi ∗ pjk−1 (oi ) : 1 ≤ i ≤ n}

(1)

Zlk = {oi , xi ∗ plk−1 (oi ) : 1 ≤ i ≤ n}, for 1 ≤ l ≤ m and l = j

(2)

The transition function maps a state sk−1 to a state sk upon an event ek occurring at zone j. For zone j, we sum the new probability pjk (oi ) for an occupant generated by event ek with the complement of the new probability value 1 − pjk (oi ), apportioned by a factor of the existing probability pjk−1 (oi ). In the event of a revision, there might be a violation of the constraint m that the sum of probabilities for any occupant across all zones equals one ( i=1 p(oi ) = 1). To restore adherence to this constraint, for each occupant oi , we apportion to the probability of oi being present in each zone l = j by redistributing the complement of the new probability value, 1 − pjk (oi ), in the ratio of the probability value in existing state plk−1 (oi ). This transition function ensures that the probability values associated with a new event as well as the current state figure in the determination of the new state as in a Markov process. Since we are dealing with a closed environment with a fixed set of occupants, o1 . . . on , we can, in general, utilize a priori declarative knowledge regarding

82

V. Menon, B. Jayaraman, and V. Govindaraju

the occupants, such as their schedules or knowledge of the environment, such as the distance between rooms and whether an occupant could move between a pair of rooms within a certain interval of time. However, the transition function presented in the above definition does not make any use of such declarative knowledge of the occupants. The nature of the declarative knowledge can also be fuzzy to factor in the probabilistic nature of the environment. The reasoning component can alleviate some of the weaknesses in the recognition component. However it should ensure that its results are not totally contradictory to the recognition system thereby generating inconsistencies. We now define the concepts of precision and recall for a smart environment. These are defined in terms of the ground truth, which, for a given input event sequence, is a sequence of states of the environment wherein the presence or absence of any occupant in any zone is known with certainty (0 or 1). Precision captures how well an occupant is recognized, while recall captures whether an occupant is recognized at all. Definition (Ground Truth). Given n occupants O={o1 . . . on } and an event sequence e1 . . . ex , then the ground truth is the sequence of states g1 . . . gx where each gk = T1k . . . Tjk . . . Tmk  and Tjk = {oi , qjk (oi ) : 1 ≤ i ≤ n ∧ qjk (oi ) ∈ {0, 1}}. Also, oi , 1 ∈ Tjk → oi , 1 ∈ Tlk , for all l = j in state gk . Given a zone of a state, the precision for that zone of the state is defined as the average probability of those occupants that are present in that zone of the state as given in the ground truth. The average precision across all zones (where at least one occupant is present as per the ground truth) is the precision for the state, and the average precision across all states is the precision for a given ground truth. Finally, the average across multiple ground truths is the precision of the smart environment. Definition (Precision). Given an environment with m zones, n occupants O = {o1 . . . on }, an event sequence E = e1 . . . ex , a ground truth G = g0 , g1 , . . . gx , and state transitions S = s0 , s1 , . . . sx . We define the precision, π, with respect to G as follows: Let πjk = ajk /bjk , where ajk =

 {pjk (oi ) : 1 ≤ i ≤ n ∧ qjk (oi ) = 1}

bjk = |

 {oi : 1 ≤ i ≤ n ∧ qjk (oi ) = 1}|

Then πk =

m  j=1

πjk /m, and we define π =

x  k=1

πk /x.

Now, given a set of ground truths {G1 , G2 , . . . G2 } with the corresponding precit sions {π 1 , π 2 , . . . π t }, the precision of the smart environment, Π = l=1 π l /t. For a given ground truth, state and zone, we define recall with respect to a threshold θ as the ratio a/b, where a is the number of occupants of that zone with probabilities greater than θ and who are present in the ground truth, and

Biometrics Driven Smart Environments

83

b is the number of occupants who are present in the ground truth for that zone. The recall for a state is the average of the probabilities across all zones where at least one occupant is present as per the ground truth. The average recall across all states is the recall for a given ground truth, and the average across multiple ground truths is the recall of the smart environment. Definition (Recall). Given an environment with m zones, n occupants O = {o1 . . . on }, an event sequence E = e1 . . . ex , a ground truth G = g0 , g1 . . . gx , and state transitions S = s0 , s1 , . . . sx . We define the recall, ρ, with respect to a threshold θ as follows: Let ρjk = ajk /bjk , where ajk = |

 {oi : 1 ≤ i ≤ n ∧ qjk (oi ) = 1 ∧ pjk (oi ) > θ}|

bjk = |

 {oi : 1 ≤ i ≤ n ∧ qjk (oi ) = 1}|

Then ρk =

m  j=1

ρjk /m, and we define ρ =

x  k=1

ρk /x.

Now, given a set of ground truths {G1 , G2 , . . . G2 } with the corresponding precit sions {ρ1 , ρ2 , . . . ρt }, the recall of the smart environment, R = l=1 ρl /t. As it is clear, the recall is inversely proportional to the threshold, θ, since lowering the threshold will result in more occupants being identified. This figure is generally arrived at experimentally for a smart environment. A reasonable choice of θ is 0.5, and this is also the value that we adopt in our experiments. In the above definition, the recall was defined zone-wise. An alternative approach is to disregard the zones while taking the ratio; doing so would increase the overall recall. Our definition gives due importance to zones, and hence is a relatively more conservative.

4

Evaluation

We have developed an experimental prototype embodying the ideas presented in this paper. Figure 1(b) illustrates a 4-zone smart environment (fourth zone representing the external zone) with 25 occupants who are monitored by video cameras installed in each of the zones. Our experimental prototype collects sample face images of the 25 occupants of an office facility and pre-registers them in a training database. The image sensors deployed in each zone detects the presence of occupants as they move through the zones and verify the face images extracted from the video against the database. The distance scores generated by eigenface is recast into a probability value [4,5] which denotes a posterior probability of the detected face matching the pre-registered occupants. This set of person-probability pairs generated essentially constitutes an event as defined in Section 3.

84

V. Menon, B. Jayaraman, and V. Govindaraju

Fig. 2. Event Sequence

Although our abstract framework is independent of the details of any particular biometric modality, we illustrate our concepts in terms of face recognition. Automated face recognition is yet to attain any comparable levels of robustness as that of humans. Factors such as viewing angle, distance, background clutter, lighting spectrum, intensity, angle and diffuseness of lighting, differences between posed photographs and spontaneous expression can cause fluctuations in the performance of computer vision based on statistical classifiers [30]. Our prototype is based upon OpenCV’s [31] implementation of the eigenface algorithm [32], which provides a basis for a simple though not robust implementation of face recognition. This prototype can be extended to incorporate other biometric recognizers in a similar manner. For example, for voice recognition, the voice samples of occupants are pre-registered in a database instead of face image samples. The ambient voice that is picked up by the voice sensors installed in different zones can be

Biometrics Driven Smart Environments

85

Fig. 3. Sample State Transition

(a)

(b) Fig. 4. Illustrating Precision and Recall

matched against the voice database to generate a set of person-probability pairs. In this manner the different biometric recognizers are interfaced in a uniform way with the rest of the system. We illustrate with figures 2, 3, and 4, the computation carried out by the state transition system that is embodied in the 4-zone smart environment. We

86

V. Menon, B. Jayaraman, and V. Govindaraju

have presented the observations and results obtained in a tabular form for ease of understanding. Figure 2 presents 10 events involving four of the occupants of the smart environment. Each event is presented as a column of probability values - these form the output of the face recognition module as it matches a given face against the training database. Shown in boldface are the probability values corresponding to the actual occupants who were involved in the corresponding events, as per the ground truth. Italicized values indicate the probabilities corresponding to the occupants who were not involved in the corresponding events, but falsely assigned values by the recognizer. This ambiguity may arise due to any of the reasons already discussed above. Figure 3 illustrates a sample transition from state s8 to s9 upon the occurrence of event e9 in zone 1. The probabilities of the occupants in zone 1 in state s9 are obtained as per equation (1) defined under the transition function definition. For the remaining zones of s9 , the probability values are obtained as per equation (2) defined under the transition function. Figure 4 illustrates the results of the precision and recall for the ground truth corresponding to the event sequence of figure 2. The low values for precision at zone 3, corresponding to states s3 and s10 in particular, can be traced to the ambiguity arising in the face recognition step at events e3 and e10 , both occurring at zone 3 which results in a low probability of recognition of occupants o1 and o2 at these events respectively. For the same reason, the values for recall at zone 3 also suffers, thereby affecting the average recall of the states s3 . . . s6 .

5

Conclusions

We have presented a novel framework for non-obtrusive biometric based indoor smart environments for identification and tracking. 1. A state transition framework in which events abstract different biometric recognition steps and transitions abstract different reasoning steps. 2. A characterization of the performance of the smart environment in terms of the concepts of precision and recall. Our state transition system is fundamentally probabilistic because the biometric recognition that underlies events is inexact in nature. Our formulation of precision and recall succinctly characterizes the performance of a smart environment. We believe that our state transition model is an effective abstraction of a smart environment and serves as a basis for integrating different recognition and reasoning capabilities. In our model, a state provides location information at a zone level and a sequence of consecutive states implicitly contains zone level tracking information for all occupants. While it is possible to define precision and recall with respect to any query of interest, we have formulated them in a query independent manner which we believe is more general. Our model is capable of supporting spatial and temporal queries, such as: the location of an occupant in the facility; time of entry/exit of an occupant; the first/last person to enter/leave the facility;

Biometrics Driven Smart Environments

87

the current occupants present in the facility; etc. A query of special interest is tracking of individuals over time and space. We plan to enhance our current prototype by incorporating a variety of biometric recognizers, such as for height, gait, voice, etc. It is possible to fuse two or more biometric modalities to enhance the overall performance of recognition. We also plan to incorporate spatio-temporal reasoning based upon declarative knowledge of the environment as well as the occupants. Through such enhancements in recognition and reasoning, we can improve the overall precision and recall of the smart environment. We plan to test this approach on larger environments and support speech-based information retrieval queries about the environment.

Acknowledgements Thanks to Philip Kilinskas for his help in developing the experimental prototype; Dr. Jason J. Corso for discussions on Markov models; and members of the Center for Unified Biometrics and Sensors for their comments and suggestions.

References 1. Weiser, M.: The Computer for the 21st Century. Scientific American 265(3), 66–75 (1991) 2. Satyanarayanan, M.: Pervasive Computing: Vision and Challenges. IEEE Personal Communications 8(4), 10–17 (2001) 3. Pentland, A., Choudhury, T.: Face Recognition for Smart Environments. IEEE Computer 33(2), 50–55 (2000) 4. Cao, H., Govindaraju, V.: Vector Model Based Indexing and Retrieval of Handwritten Medical Forms. In: Proc. of the Ninth International Conference on Document Analysis and Recognition (ICDAR 2007), pp. 88–92. IEEE Computer Society, Washington (2007) 5. Bouchaffra, D., Govindaraju, V., Srihari, S.: A Methodology for Mapping Scores to Probabilities. IEEE Transactions on Pattern Analysis and Machine Intelligence 21(9), 923–927 (1999) 6. van Rijsbergen, C.J.: Information Retrieval. Butterworths, Boston (1979) 7. Cook, D., Das, S.: How smart are our environments? An updated look at the state of the art. Pervasive and Mobile Computing 3(2), 53–73 (2007) 8. Youngblood, M., Cook, D.J., Holder, L.B.: Managing adaptive versatile environments. In: Proc. of the Third IEEE Intl. Conf. on Pervasive Computing and Communications, pp. 351–360. IEEE Computer Society, Washington (2005) 9. Lesser, V., et al.: The Intelligent Home Testbed. In: Proc. of the Autonomous Agents 1999 Workshop on Autonomy Control Software. ACM, New York (1999) 10. House n Living Laboratory Introduction (2006) 11. Hightower, J., Borriello, G.: Location Systems for Ubiquitous Computing. IEEE Computer 34(8), 57–66 (2001) 12. Manesis, T., Avouris, N.: Survey of position location techniques in mobile systems. In: Proc. of the Seventh Intl. Conf. on Human Computer interaction with Mobile Devices and Services. MobileHCI 2005, pp. 291–294. ACM, New York (2005)

88

V. Menon, B. Jayaraman, and V. Govindaraju

13. Fox, D., Hightower, J., Liao, L., Schulz, D., Borriello, G.: Bayesian filtering for location estimation. IEEE Pervasive Computing 2(3), 24–33 (2003) 14. Bar-Shalom, Y., Li, X.-R.: Multitarget-Multisensor Tracking: Principles and Techniques, Yaakov Bar-Shalom (1995) 15. Bui, H.H., Venkatesh, S., West, G.: Tracking and surveillance in wide-area spatial environments using the Abstract Hidden Markov Model. Intl. Journal of Pattern Recognition and Artificial Intelligence 15(1), 177–195 (2002) 16. Roy, A., Bhaumik, S., Bhattacharya, A., Basu, K., Cook, D.J., Das, S.K.: Location aware resource management in smart homes. In: Proc. of the First IEEE Intl. Conf. on Pervasive Computing and Communications, pp. 481–488. IEEE Computer Society, Washington (2003) 17. Das, S.K., Roy, N., Roy, A.: Context-aware resource management in multiinhabitant smart homes: A framework based on Nash H-learning. Pervasive and Mobile Computing 2(4), 372–404 (2006) 18. Schulz, D., Fox, D., Hightower, J.: People tracking with anonymous and id-sensors using Rao-Blackwellised particle filters. In: Proc. of the 18th Intl. Joint Conference on Artificial Intelligence (IJCAI), pp. 921–926 (2003) 19. Krumm, J., Harris, S., Meyers, B., Brumitt, B., Hale, M., Shafer, S.: Multi-Camera Multi-Person Tracking for EasyLiving. In: Proc. of the 3rd IEEE Intl. Workshop on Visual Surveillance (VS 2000). IEEE Computer Society, Washington (2000) 20. Brumitt, B., Meyers, B., Krumm, J., Kern, A., Shafer, S.A.: EasyLiving: Technologies for Intelligent Environments. In: Thomas, P., Gellersen, H.-W. (eds.) HUC 2000. LNCS, vol. 1927, pp. 12–29. Springer, Heidelberg (2000) 21. Chen, D., Gellersen, H.: Recognition and reasoning in an awareness support system for generation of storyboard-like views of recent activity. In: Proc. of the Intl. ACM SIGGROUP Conference on Supporting Group Work. GROUP 1999. ACM Press, New York (1999) 22. Aghajan, H., et al.: Distributed Vision-Based Accident Management for Assisted Living. In: Okadome, T., Yamazaki, T., Makhtari, M. (eds.) ICOST. LNCS, vol. 4541, pp. 196–205. Springer, Heidelberg (2007) 23. Gao, Y., Hui, S.C., Fong, A.C.: A Multi-View Facial Analysis Technique for Identity Authentication. IEEE Pervasive Computing 2(1), 38–45 (2003) 24. Hong, K., et al.: Real Time Face Detection and Recognition System Using Haar-Like Feature/HMM in Ubiquitous Network Environments. In: Gervasi, O., Gavrilova, M.L., Kumar, V., Lagan´ a, A., Lee, H.P., Mun, Y., Taniar, D., Tan, C.J.K. (eds.) ICCSA 2005. LNCS, vol. 3480, pp. 1154–1161. Springer, Heidelberg (2005) 25. Zhang, S., et al.: Continuous Verification Using Multimodal Biometrics. In: Zhang, D., Jain, A.K. (eds.) ICB 2005. LNCS, vol. 3832, pp. 562–570. Springer, Heidelberg (2005) 26. Hazen, T., Weinstein, E., Heisele, B., Park, A., Ming, J.: Multi-Modal Face and Speaker Identification for Mobile Devices. In: Hammoud, R.I., Abidi, B.R., Abidi, M.A. (eds.) Face Biometrics for Personal Identification: Multi-Sensory Multi-Modal Systems, pp. 123–138. Springer, Heidelberg (2006) 27. Bohn, J., Coroama, V., Langheinrich, M., Mattern, F., Rohs, M.: Social, Economic, and Ethical Implications of Ambient Intelligence and Ubiquitous Computing. In: Weber, W., Rabaey, J., Aarts, E. (eds.) Ambient Intelligence, pp. 5–29. Springer, Heidelberg (2005)

Biometrics Driven Smart Environments

89

28. Vildjiounaite, E., et al.: Unobtrusive Multimodal Biometrics for Ensuring Privacy and Information security with Personal Devices. In: Fishkin, K.P., Schiele, B., Nixon, P., Quigley, A. (eds.) PERVASIVE 2006. LNCS, vol. 3968, pp. 186–201. Springer, Heidelberg (2006) 29. Bernardin, K., Stiefelhagen, R.: Audio-visual multi-person tracking and identification for smart environments. In: Proc. of the 15th International Conference on Multimedia, pp. 661–670. ACM, New York (2007) 30. Hewitt, R., Belongie, S.: Active Learning in Face Recognition: Using Tracking to Build a Face Model. In: Proc. of the 2006 Computer Vision and Pattern Recognition Workshop, pp. 157–157. IEEE Computer Society, Washington (2006) 31. OpenCV, http://www.intel.com/technology/computing/opencv/index.htm 32. Turk, M., Pentland, A.: Eigenfaces for Recognition. J. Cognitive Neuroscience 3(1), 71–86 (1991)

A Structured Methodology of Scenario Generation and System Analysis for Ubiquitous Smart Space Development Ohbyung Kwon1 and Yonnim Lee2 1

School of International Management Kyunghee University Seochun, Ghiheung, Yongin, Kyunggi-do, South Korea [email protected] 2 Research Center for Ubiquitous Business and Services, Kyunghee University Seochun, Ghiheung, Yongin, Kyunggi-do, South Korea [email protected]

Abstract. Ubiquitous smart space (USS) has been regarded as a promising extension of ubiquitous services, and it is currently the subject of world-wide development. In one USS development methodology, scenario development is performed before system analysis and design. However, even though many redundant elements can be found between scenarios and system analysis results, developers have not been taking any structural approaches to join them together for more consistency and eventually higher productivity. Hence, the aim of this paper is to propose a methodology to increase the consistency in the early steps of USS development. To do so, scenario and requirement analysis are integrated in a structured manner. Keywords: ubiquitous smart space, scenario analysis, requirement analysis, structured method.

1 Introduction Advances in ubiquitous technologies have led to the development of many new types of ubiquitous services. Unlike earlier approaches, ubiquitous computing services are defined and used as services that are provided not just in physical spaces but also in logical spaces. This extension of service concept has drawn interest to USS (Ubiquitous Smart Space). USS is an artificial space that is added to ubiquitous computing technology. Recently ubiquitous computing services have developed in USS environment all over the world, for example: in the United States, there are several systems including HP’s Cool Town, Microsoft’s Easy Living, Cisco’s MIE, Intel’s Digital Home, Xerox’s Smart Media Spaces, NIST’s Smart Space, Georgia Tech’s e-Class, and MIT’s Auto-ID Center. In Europe, systems include EU’s 2Wear, Belfast’s MIME, Orange at Home of Orange, and Siemens’ Smart Home. In Japan, systems include the Ubiquitous ID Center’s Ubiquitous ID Technology, Matsushita’s eHII system, OMRON & ODAKYU’s GOOPAS, NTT’s Power Conversion System, and NTTDocomo’s Cmode. In Korea, F.E. Sandnes et al. (Eds.): UIC 2008, LNCS 5061, pp. 90–104, 2008. © Springer-Verlag Berlin Heidelberg 2008

A Structured Methodology of Scenario Generation and System Analysis

91

systems include ETRI’s u-Post, SKT’s Moneta, Samsung Electronics’ Digital Home, and CVnet’s Cyber Village. Most of these USSes are proposed by feasible service scenarios that involve various ubiquitous computing elements, technologies and products. In the first stage of development, they write a service scenario that shows a possible future lifestyle, and carries out a requirement analysis through that scenario. From this, the developers design and implement the USS. USS is totally different from the previous physical space so these services also deploy very differently. Therefore, the scenario method that is very widely used in future research has been recognized as an effective tool in developing future services. The scenario method was proven very useful for eliciting USS service idea [1]. Moreover, the scenario method is useful for explaining new ideas to another developer or to capture requirements for system implementation. Hence, the scenario method is widely used as a method to develop USS service [2]. Carnegie Mellon University’s Aura project was started with the goal of achieving invisible computing by Peter Steenkiste in 1999; they first used the scenario method and designed the Aura system to realize that scenario. However, to date, no standardized methodology exists for writing scenarios. Most scenario methods suggest simple guidelines without using all USS development phases. Therefore many scenarios have been developed by brainstorming and the contents have been decided by personal taste or by their organization’s preferences. Brainstorming is a group creativity technique designed to generate a large number of ideas for the solution to a problem. Although brainstorming is very useful for generating creative ideas, it is of course limited if there aren’t sufficient resources. Potential brainstorming problems can also include distraction, social loafing, evaluation apprehension, and production blocking. Existing scenario methods are not related to requirement analyses for software development, which can cause communication problems between scenario writer and requirement analyst. Requirements analysis for developing services has made progress independent of efforts for scenario writing. As a result, one-sided and subjective scenarios that were written without concerning the requirement analysis phase have created problems: double writing, inconsistency between scenario and requirement specification, waste of time and cost. Moreover, these types of scenarios make it difficult to objectively analyze and evaluate scenarios. It is also difficult to validate the degree of scenario reflection on requirements specifications since finding objective standards against which one can evaluate a subjective scenario is difficult. Therefore, this paper proposes the standardized and structured methodology of writing scenarios, and develops an integration methodology for requirement analysis that proceeds automatically and continuously from the written scenario. In this methodology, we focus on a technical-push scenario that is validating the utilitarian of the technology which is developed in the short term. This paper is organized in five sections. First we review previous research, and then Section 3 describes the scenario writing methodology and integration methodology for requirement analysis. A case study of our methodology is proposed in Sections 4. Finally, we provide concluding remarks in Section 5.

92

O. Kwon and Y. Lee

2 Scenario-Based Requirement Engineering Scenario-based requirements analysis methods express system requirements by using scenarios that were elicited through examples of real world experience and invented experiences [3,4]. Scenario-based requirements analysis methods can be simply divided into two methods: ScenIC and SCRAM [5,6]. ScenIC (Scenario in the Inquiry Cycle) proposes a schema of scenario-related knowledge composed of goals, objectives, tasks, obstacles, and actors [7]. Scenarios are composed of episodes and action carried out by actors, who are usually people but may also be machines. Goals are classified into achieving, maintaining, or avoiding states, while obstacles prevent goals from being achieved, or inhibit successful completion of tasks. The method proceeds in a cycle of expressing scenarios in a semistructured format, criticizing and inspecting scenarios in walkthroughs, which lead to refining requirements and specifications and the next cycle. Guidelines are given for formatting scenario narratives and identifying goals, actions and obstacles. Scenario episodes are assessed with challenges to see if goals can be achieved by the system tasks, whether the actors can carry out the tasks, whether obstacles prevent the actors carrying out the tasks, etc. Thus, dependencies between goals, tasks, actors and resources can be checked to make sure the system meets its requirements. Dependency analysis and means-ends analysis, in which tasks and the capabilities of actors are examined to ensure goals can be achieved. In SCRAM (Scenario-based Requirement Analysis Method) [8,9,10], scenarios are used with early prototypes to elicit requirements in reaction to a preliminary design. This approach does not explicitly cover modeling and specification, as this is assumed to progress in parallel, following the software engineering method of the designer’s choice. According to Alistair [5], the method consists of four phases: (1) Initial requirements capture and domain familiarization. This is conducted by conventional interviewing and fact-finding techniques to gain sufficient information to develop a first concept demonstrator; (2) Storyboarding and design visioning; (3) Requirements exploration; (4) Prototyping and requirements validation. This phase develops more fully functional prototypes and continues refining requirements until a prototype is agreed to acceptable by all the users. However, in the legacy scenario-based requirement analysis methods, requirement analysis is actually separated from scenario writing; they support system analysis only after writing scenarios completely.

3 Methodology Overview 3.1 Overall Framework To write scenarios and analyze requirements in USS development environment, an overall framework is proposed as shown in Fig. 1. There are two ways to write a scenario briefly. The first one is a guided approach. In this approach, we first analyze the environment, and then write scenarios based on the results. The other is an open-ended approach that writes scenarios freely without any environment analysis [24]. As previously stated, our research focuses on a technical-push scenario that validates the usefulness of the technology developed in the short term. Hence, we apply a guided approach because we aim to make our scenario

A Structured Methodology of Scenario Generation and System Analysis

DDefi ne efi ne the the Technol oogy Technol gy MMatri xx atri

DDefi ne efi ne the the SServi ce ervi ce MMatri xx atri

SSketch ketch oout ut the oo the SScenari cenari OOutl ine utl ine

93

GGenerate enerate the the SScenari oo cenari

DDraw raw the the SScenari oo cenari DDescri p oonn escriptiti DDiag iagram ram

GGenerate enerate the the RRequi rem equi rem ent ent SSppeci fifi cati oonn eci cati

Fig. 1. Proposed methodology for generating scenario and requirement specification from technology and service matrix

practical to implement. In this paper, we define technologies, devices, and services that we can use in the scenario at present—this is the environment analysis phase. We then write the scenario based on the results. The scenario writer defines the technology matrix after collecting usable technologies and devices. Technology matrix means a sort of tables which shows summary of available technologies and corresponding devices for making services available. Through a combination of technology and devices in the defined technology matrix, we extract services that we can use in scenarios. We then define a service matrix, which describes in detail the content of each service extracted from a technology matrix, and evaluate its service level to decide if it is available to make scenarios. Based on this evaluation result, we confirm the service that we will use in the scenario. The scenario outline is then sketched out by a final confirmed service. After that, we draw the scenario diagram using the scenario outline and confirmed services. The scenario diagram is a technique that represents scenarios by predefined notations and processes. This diagram consists of a context diagram, a level-0 diagram and a level-1 diagram. Scenarios are generated by transforming a completed scenario diagram according to automatic transformation logic. Requirement specifications are written by transforming a generated scenario according to automatic transformation logic. Meanwhile, we create a scenario dictionary to improve understanding of the scenario reader and requirement specification writer. 3.2 Technology Matrix Definition First, the scenario writer collects technologies and devices that can be used in the scenario and describes brief explanation for each. Then, the scenarios writer may draw up a table which indicates a summary of those technologies and devices as shown in Table 1:

94

O. Kwon and Y. Lee Table 1. Technology Matrix Template

Category Available Technology Possible Device

Name

Explanation

Technology name

Brief explanation for the technology

Device name

Brief explanation for the device

3.3 Service Matrix Definition (1) Extract services Through a combination of technology and devices in the previously defined Technology Matrix, we extract services that we can use in scenarios. Extracted services would take concrete shape by the Service Matrix and be confirmed in the phase of service evaluation. Table 2 is the template for Service Extraction. Among these methodologies, we will focus on the former six steps from need identification to validation on service selection in this paper. Table 2. Service extraction template

Technology and Device Tech. 1

Tech. 2

{

Device 1

Device 3

{

{

Service

Device 4

Service name

Mark ‘{’ Tech. or Device used in the Service.

(2) Define service matrix Service matrix is a table to display in detail the contents of each extracted service. At this time, the functionality of the service that is expressed as an adjective or an adverb in service must be explained as detailed as possible. Table 3 is the template for the Service Matrix. Table 3. Service matrix template

Service

Description

Functionality Enabler

Function

A Structured Methodology of Scenario Generation and System Analysis

95

(3) Evaluate service level We evaluate the service level of each service based on the checklist. Then we review the result of evaluation with the people who request the scenario. 3.4 Scenario Outline Identifying the topic and background of scenario might proceed as follows. • • • •

Define the value that can be provided for end user through the services used in scenario. Identify stakeholders related to the scenario Define the main character of the scenario and his goal. If needed we can set up the obstacles and complication elements of the scenario. Describe the brief contents for scenario.

Table 4 is the template for identifying the theme and the background of scenario. Table 4. The template for identifying the theme and the background of scenario

Category Name Theme Stakeholder Abstract

Description The name of scenario The theme of scenario Stakeholders are people who affects, or can be affected by the scenario financially Abstract of the scenario

(2) Define the actors and assign their role We define the actors who carry out the service in the scenario and assign their role. An actor might be divided by its property (device, agent, ontology, u-Product). Table 5 is the template for defining the actors and assigning their role. 3.5 Scenario Definition Diagram We draw the scenario diagram based on the sketch of the scenario. This diagram is a technique that represents scenarios by predefined notations and processes. It consists Table 5. The template for defining the actors and assigning their role

Category Device Agent Ontology u-Product

Actor Actor name

Role Actor’s role

96

O. Kwon and Y. Lee Table 6. Components of the scenario definition diagram

Component

Notation

Sequence

Scene



Stakeholder

Data Flow

Data Store

Information Flow

Description It represents the service offered in scenario. One sequence has more than one service. It represents the actual service action that is performed by using the data. It has an actor who is the object of services and an action that is service contents. It represents the stakeholders are people who affects, or can be affected by, the scenario financially It represents the data flow among services or actor’s action. It represents the optional data flow among services or actor’s action. It represents the looped data flow among services or actor’s action. It represents the data store that saves the data. It could have a number of various physical shapes. It represents the information flow between scene and data store. When a scene requests specific information, the data store provides it.

of a context diagram, a level-0 diagram, and a level-1 diagram. Table 6 shows the components of the scenario diagram. (1) Draw the scenario context diagram The scenario context diagram represents the business model of scenario. This diagram explains the relationship among stakeholders who affect, or can be affected by, the scenario financially. Hence, the scope of service is decided through this diagram. The scenario context diagram is drawn like Fig. 2. (2) Draw the scenario level-0 diagram The level-0 diagram represents all services offered in a scenario, and it depicts information flow and the transforms that are applied as data moves from input to output. The scenario level-0 diagram is drawn as a series of steps and will be drawn as in Fig. 3.

A Structured Methodology of Scenario Generation and System Analysis

Stakeholder 1

Scenario name

Financial relation

97

Stakeholder 2

Financial relation

Financial relation Stakeholder 3 Fig. 2. Scenario contxext diagram Data 1. Service 1

Data 2. Service 2 Data

Fig. 3. Scenario level-0 diagram

(3) Draw the scenario level-1 diagram The Scenario Level-1 Diagram represents the actor and his action in each service. All actors have an Event, Action, and Response. In here, Event is the cause action leads to actor’s action and Response is the result action of the actor’s action. Table. 7 is the template for Action Matrix to organize these actors and actions. Scenario Level-1 Diagram is drawn like Fig. 4. Table 7. The template for action matrix

Actor Actor name

Event

Action

Response

The cause action leads to actor’s action

The actor’s own action

The result action of the actor’s action

98

O. Kwon and Y. Lee

Data flow

1.1 Actor 1

Data flow

1.2 Actor 2

Action1

Data flow

1.3

Data flow

Actor 3

Action2

Action3

Data flow

Data flow

Data Store Fig. 4. Scenario level-1 diagram

3.6 Scenario Generation We generate the scenario by transforming completed Level-1 Diagram according to automatic transformation logic on a per-Sequence basis. Since the transformation logics are highly dependent of language to be used, Korean language has been considered so far. 3.7 Generate Requirement Specifications In this paper, we use the UML that is a modeling language widely used for requirement analysis. Software system can be visualized, described, developed and created a document by the UML. Especially, we choose the Sequence Diagram among 4 models and 8 diagrams of UML that are OMG’s public standard. Sequence Diagram is drawn as follow steps. Step 1. On the basis of Level-1 Diagram, collect all data flows in scenario and give them serial number in order. And then rearrange each data flow, input and output as Table 8. Step 2. Placed all actors appeared in scenario horizontally by using predefined symbols of Fig. 5. And draw a vertical line started from each actor. Step 3. Draw all data flows arranged in Step 1 from Input Actor to Output Actor in order. At this time, represent data flow as an arrow along the vertical line. Table 8. Template for rearranging the data flow in scenario

No 1

Action

Actor

Next Actor

The actor’s own action

Actor who acts

Actor who is affected by the action

2

…

…

…

A Structured Methodology of Scenario Generation and System Analysis

99



Human

u-product

sensor

event handler agent

ontology

Fig. 5. Symbols for sequence diagram

4 Case Study This case study describes the ‘U-Shopping Aid’ scenario. We applied our methodology to this scenario. ‘U-Shopping Aid’ scenario was proposed to make customers Table 9. Technology matrix Category Technology

Device

Name Agent Technology Semantic Web

Description Offer the information of the product reputation and the payment through the negotiation among agents Provide semantic information through the data written by Ontology Language (OWL) Transfer data between Network AP of shop and u-PDA

uPAN Scalefree Ubiquitous Mobile Object (UMO) UMO

It is a mobile object or device that people have. It can be changed own functions depended on context and share computing resource with smart objects Smart object that customer has. It play an important role in receiving the service Smart display device established in shop or customer’s house Performing a recognizing role among devices

Smart Wall Or AR Table RFID Sensor

Table 10. Extract services Technology and Device uAgent USN PDA

Augmented Reality

Teleconference

Smart Wall

Smart Table

G

G

{G

{G

{G

G

G

{G

G

{G

G

G

{G

G

G

{G

{G

G

G

G

{G

G

G

{G

{G

G

G

G

G

G

G

{G

G

{G

G

Service Customer-aware and product recommendation Virtual put-on service Image sync service Payment service1 Payment service2

100

O. Kwon and Y. Lee Table 11. Service matrix Service name

Definition

Customer-aware and product recommendation

When customer enters, it is aware of that fact automatically. Recommend products that customer would like

Image sync service

Provide the virtual image that customer puts on the chosen clothes using the pictures saved in smart object

Payment service1

It enables to share images among remote spaces and to communicate with each other

Payment service1

When customer makes the decision about buying, it automatically transmits the payment information to the seller and delivery company simultaneously When customer makes the decision about buying, it automatically transmits the payment information to the seller simultaneously

Payment service2

Functionality Function Notify the user’s current location information Mall Agent Detect the embedded chip in UMO automatically Customer Store the user profile information Ontology Shop Agent Make recommendation lists according to the user preference Augmented Display virtual images reality device when the user sees the chosen clothes through AR device AR Table or Display made picture Smart Wall u-PDA Transmit shared images AR Table or Display shared images Smart Wall and transmit the selected information u-PDA Transmit payment information Enabler UMO

u-PDA

Transmit payment information

Table 12. Scenario actors and their roles

Category

Actor Shop Agent

Agent Mall Agent

Sensor

Chip sensor at the Mall entrance

Ontology

Customer info Ontology

Role It offers the optimized service through being aware of various customer need and manage the agent of shops. It is in the shopping mall. It is aware of customer’s context information and transmits it to Shop Agent. It is a RFID chip sensor at the shopping mall entrance. It detects the customer’s smart objects. It stores a customer profile.

A Structured Methodology of Scenario Generation and System Analysis

101

convenient for their shopping more practically. ‘U-Shopping Aid’ scenario consists of customer-aware and product recommendation services, virtual put-on service, image sync service and payment service. Let’s suppose that the Technology Matrix could be defined as Table 9. Then five services in Table 10 are extracted and Service Matrix is defined as listed in Table 11, which is based on Table 9. Then the actors and assign their role for our scenario is defined as shown in Table 12. Lastly, Scenario Context Diagram and Scenario Level-0 Diagram are prepared as Appendix A.

5 Conclusion Recently, USS developers are under increasing pressure due to the increased importance of making scenario and requirement analyses; hence the increasing need for structured methodologies. However, so far there has been no standardized methodology for writing scenarios. Most scenario methods suggest simple guidelines that do not take into consideration all USS development phases. Therefore many scenarios have been developed by brainstorming and the contents have been decided by personal taste or by the organization’s favor. Moreover, existing scenario methods do not relate to requirement analysis for software development. This fact creates communication problems between scenario writer and requirement analyst. It creates problems like double writing, inconsistency between scenario and requirement specification, waste of time and cost, and so on. These kinds of scenarios make it difficult to analyze and evaluate scenario objectively. Therefore, we propose the standardized and structured methodology of writing scenario and develop the integration methodology for requirement analysis that is proceeding from written scenario automatically and continuously. We are applying our methodology to the ‘U-Shopping Aid’ service development supported by a Korea governmental project.

Acknowledgment This research is partially supported by the ubiquitous Computing and Network (UCN) Project the Ministry of Information and Communication (MIC) 21st Century Frontier R&D Program.

References 1. Ranta, M., Asplund, H.: Utilizing scenarios in service idea generation- a case of distant participation for a seminar. In: Proceedings cf COST269 Conference, pp. 379–386 (2003) 2. Anton, A.I., Potts, C.: A Representational Framework for Scenarios of System Use. Requirements Eng. 3, 219–241 (1998) 3. Sutcliffe, A.: Scenario based requirement analysis. Requirements Engineering Journal, 48– 65 (1998)

102

O. Kwon and Y. Lee

4. Plihon, V., Ralyte, J., Benjamen, A., Maiden, N.A.M., Sutcliffe, A., Dubois, E., Heymans, P.: A Reuse Oriented Approach for the Construction of Scenario Based methods. In: Proc. Int’l Software process Assoc. Fifth Int’l Conf. Software Process (ICSP 1998), Chicago, pp. 14–17 (1998) 5. Sutcliffe, A.: Scenario-Based Requirements Engineering. In: Proceedings of the 11th IEEE International Conference, Montery Bay, USA, pp. 320–329. IEEE Computer Society Press, Los Alamitos (2003) 6. Misra, S., Kumar, V., Kumar, U.: Goal-oriented or scenario-based requirements engineering technique- What should a practitioner select? In: IEEE CCECE/CCGEI, Saskatoon, pp. 2290–2291 (2005) 7. Potts, C.: ScenIC: A Strategy for Inquiry-Driven Requirements Determination. In: 4th IEEE International Symposium on Requirements Engineering, pp. 58–65. IEEE Computer Society Press, Los Alamitos (1999) 8. Sutcliffe, A.G.: Scenario-Based Requirements Analysis. Requirements Engineering 3, 48– 65 (1998) 9. Sutcliffe, A.G.: User-Centred Requirements Engineering. Springer, London (2002) 10. Sutcliffe, A.G., Ryan, M.: Experience with SCRAM: A Scenario Requirements Analysis Method. In: IEEE International Symposium on Requirements Engineering: RE 1998, pp. 164–171. IEEE Computer Society Press, Los Alamitos (1998)

Appendix A. Example Results (1) Context Diagram COEX Mall

Payment Context-aware info Info & payment User (A)

U-shop service & delivery Service

Info & payment U-shop

U-Shopping Aid Customized i Purchasing info & payment Delivery Info

Distribution and delivery Service Provider

A Structured Methodology of Scenario Generation and System Analysis

(2) Scenario Level-0 Diagram [Scenario name] Aware & recommend <Scenario Diagram>

[Scenario name] Virtual Put On

[Scenario name] Image Sync

[Scenario name] Payment and delivery



103

104

O. Kwon and Y. Lee

(3) Data Flows in Scenario No. 1 2 3 4 5 6 7 8 9

18

19 20 21 22 23

Data flow A enters Send A’s context info.

Actor Chip sensor at Mall Entrance Mall Agent Customer Info. Ontology Mall Agent

Request for A’s info. Send A’s info. Send A’s Context info. Ask A’s info. Shop Agent Send A’s info. Customer Info. Ontology Provide product list to Shop Agent recommend Send a message to A’s UMO suggest the VPO service Scenes from 10 to 17 are omitted here. Display the created IS service device augmented reality to share with family The info. about the AR Table family choices Send the family A’s UMO choices Decision to purchase A and pay Info. about payment A’s UMO Info. about payment Shop Agent and delivery

Next_Actor Mall Agent Customer Info. Ontology Mall Agent Shop Agent Customer Info. Ontology Shop Agent A’s UMO A

AR Table

A’s UMO A A’s UMO Shop Agent A

Capturing Semantics for Information Security and Privacy Assurance Mohammad M.R. Chowdhury1 , Javier Chamizo2 , Josef Noll1 , and Juan Miguel G´ omez2 1

UniK-University Graduate Center Post Box 70, N-2027 Kjeller, Norway {mohammad, josef}@unik.no 2 Escuela Polit´ecnica Superior Universidad Carlos III de Madrid Avda. de la Universidad 30, Legan