Embedded and Ubiquitous Computing – EUC 2005 Workshops

This paper proposes human activity recognition based on the actual semantics of the human’s current location. Since predefining the semantics of location is inadequate to identify human activities, we process information about things to automatically identify the semantics based on the concept of affordance. Ontology is used to deal with the various possible representations of things detected by RFIDs, and a multi-class Naïve Bayesian approach is used to detect multiple actual semantics from the terms representing things. Our approach is suitable for automatically detecting possible activities under a variety of characteristics of things including polysemy and variability. Preliminary experiments on manually collected datasets of things demonstrated its noise tolerance and ability to rapidly detect multiple actual semantics from existing things.

Smart spaces are open complex computing systems, consisting of a large variety of cooperative smart things. Central to building smart spaces is the support for sophisticated coordination among diverse smart things collaborating to accomplish specified tasks. Multi-agent systems are often used as the software infrastructures to address the coordination in smart spaces. However, since agents in smart spaces are dynamic, resource-bounded and have complicated service dependencies, current approaches to coordination in multi-agent systems encounter new challenges when applied in smart spaces. In this paper, we present Baton, a service management system to explicitly resolve the particular issues stemming from smart spaces while coordinating agents (delegating smart things in smart spaces). Baton is designed as a complement to coordination approaches in multi-agent systems with a focus on mechanisms for service discovery, service composition, request arbitration and dependency maintenance. Baton has been now deployed in our own smart spaces to achieve better coordination for smart things.

Continuous technological innovation is entailing that living environments be equipped with products that improve the quality of daily life. Unluckily, the adopted solutions do not always represent an adequate support and people continue to execute repetitive tasks that software infrastructures could perform automatically. This is partially due to the fact that the existent technological solutions cannot be always integrated in a coherent communication platform, as they use proprietary protocols and ad hoc implementations not easily reusable. This paper proposes an extensible ubiquitous architecture for networked virtualized devices in smart living environments. The aim is realizing ubiquitous applications and integrating networked devices through an architecture that hides their complexity and heterogeneity. Several intelligence techniques have been integrated for offering a smart environment through the use of automatic learning techniques.

A world model for ubiquitous computing environments is presented. It can be dynamically organized like a tree based on geographical containment, such as in a user-room-floor-building hierarchy and each node in the tree can be constructed as an executable software component. It provides a unified view of the locations of not only physical entities and spaces, including users and objects, but also computing devices and services. A prototype implementation of this approach was constructed on a Java-based mobile agent system.

With the increasing globalization of economy and consequent increasing in the inter and intra organizational competitiveness, the role of groups in organizations and businesses achieve greater significance. The work, as well as the responsibility involved to reach a decision, is distributed among group members, which may be distributed geographically and may cooperate in an asynchronous way. This paper shortly presents the

WebMeeting

prototype, which is a group decision support system that supports ubiquitous group decision meetings. It is also discussed the influence of emotional factors in group decision making and it is proposed a multi-agent model to simulate ubiquitous group decision making processes, where argumentation and emotional capabilities are considered.

Software Platform is a middleware component of Smart Space to coordinate and manage all modules. Location-awareness is a common feature of many modules. Current several typical methods for distributed systems can hardly be competent for both the role of Software Platform and accommodating location-awareness simultaneously. Aiming at this, we present our method: SLAP (Smart Location-awareness-Accommodating Platform). The method, on the basis of OAA (Open Agent Architecture), adopts such new technologies as

Poll-Ack mechanism

,

dual-central coupling model

and

hybrid architecture

. Consequently it not only reserves the advantages of OAA to coordinate multi-modal modules efficiently and flexibly, but also accommodates location-aware computing well.

In USA, 2002, approximately 3.2 million intersection-related crashes occurred, corresponding to 50 percent of all reported crashes. In Japan, more than 58 percent of all traffic crashes occur at intersections. With the advances in Intelligent Transportation Systems, such as off-the-shelf and in-vehicle sensor technology, wireless communication and ubiquitous computing research, safety of intersection environments can be improved. This research aims to investigate an integration of intelligent software agents and ubiquitous data stream mining, for a novel context-aware framework that is able to: (1) monitor an intersection to learn for patterns of collisions and factors leading to a collision; (2) learn to recognize potential hazards in intersections from information communicated by road infrastructures, approaching and passing vehicles, and external entities; (3) warn particular threatened vehicles that are approaching the intersection by communicating directly to the in-vehicle system.

In this paper, we propose combination of Ubiquitous Computing and Semantic Web. Data and services will be annotated even in the ubiquitous devices, and should be connected to the web of the semantics near future. We call it Ubiquitous Semantics, where we would find huge amount of knowledge information, but also find most of them transitive along with user context. Therefore, in order for an agent to meet user’s real-time query it is required to efficiently retrieve timely and useful piece of the knowledge from the Ubiquitous Semantics. Thus, this paper shows a knowledge-filtering agent, which quickly responds the query by dynamic classification of the necessary information along with the user context changing in the real world. Further, to evaluate our approach we validate the performance of an application: Recipe Recommendation Agent.

Java for embedded devices is today synonym of “embeddable pseudo-Java”. Embedded flavors of Java introduce incompatibilities against the standard edition and break its portability rule. In this paper, we introduce a way to embed applications written for Java 2 Standard Edition. The applications are pre-deployed into a virtual Java execution environment, which is analyzed in order to tailor the embedded Java virtual machine according to their runtime needs. Experiments reveal that this method produces customized virtual machines that are comparable in size to existing embedded Java solutions, while being more flexible and preserving standard Java compatibility.

Java Card is now a mature and accepted standard for smart card and SIM technology. Java Card is distinguished primarily by its independence from hardware platforms and portability and is now the most important open standard. However, the main concern of Java Card is now its low execution speed caused by the hardware limitation. In this paper, we propose how to improve a execution speed of Java Card by reducing the number of EEPROM writing. Our approaches are an object-buffer based on a high locality of Java Card objects, the use of RAM, has a speed more faster 1000 times than EEPROM, as much as possible and new transaction mechanism using RAM.

In this paper, we propose an intelligent object extraction algorithm based on foreground/background classification. The proposed algorithm can offer the users more friendly interface for object extraction from image without unnecessary steps. After the interactive steps from user (marking the foreground and background parts), the wanted object is extracted from the background automatically. The proposed algorithm processes the input image by watershed to produce the regions. Then, the regions are labeled after marking parts of regions. We also introduce an implementation of hierarchical queues to store the unlabeled regions. The classification of foreground and background will generate the final image with selected object. In our experimental results, the proposed algorithm provides the output image with high efficiency. The wanted object is generated after user marking the foreground and background parts less than one second. In addition, the application of this work also can be used in image synthesis or object removal in other fields of image processing.

In this paper, the authors examine the use of thin client based user terminals to realize the RFID tag based ubiquitous computing environment. The ubiquitous service targeted is not information retrieval via RFID but the user observation service based on environment perception. Thus the user terminal must ensure service consistency even when the communication link to the server is disconnected. In order to achieve this, the authors propose an event cache mechanism that stores predicted event conditions and the corresponding reactions. A prototype and evaluation results are also described.

In this paper, we propose an application development environment for the ubiquitous chip, which is a rule-based event-driven input/output (I/O) control device for constructing ubiquitous computing environments. The proposed development environment simulates the behaviors of multiple ubiquitous chips and helps users to create rules. Moreover, it has a function for developing applications by cooperation between virtual ubiquitous chips and real ubiquitous chips. The application environment enables both programmers and general users to develop and customize applications for ubiquitous computing environments.

To develop context-aware workflow services in ubiquitous computing environments, a service developer must describe and recognize context information as transition constraints. uWDL (ubiquitous Workflow Description Language) [1] is a workflow language that describes the situation information of ubiquitous environments as a rule-based service transition condition. In this paper, we suggest a uWDL handler that supports workflow’s service transition to be aware of user’s condition information. The uWDL handler consists of a uWDL parser and a uWDL context mapper. The uWDL parser represents contexts described in the scenario with sub-trees of a DIAST (Document Instance Abstract Syntax Tree) as a result of the parsing. To derive the right transition of workflow services, the uWDL context mapper compares contexts described in sub-trees of DIAST with a user’s situation information generated from ubiquitous environments by using a context comparison algorithm. Therefore, the uWDL handler will be used in developing context-aware workflow applications that can change the flow of a service scenario according to the user’s situation information in the ubiquitous computing environment.

A new class of m-commerce applications is emerging due to the unique features of handheld devices, such as mobility, personalization and location-awareness. This paper presents SMMART, a context-aware, adaptive and personalized m-commerce application designed to deliver targeted promotions to the users of mobile devices. SMMART adapts to changing interests of its user by monitoring his or her shopping habits and guarantees the privacy of its users by not transmitting any personally identifiable information to the retailers. We describe our experiences of building and evaluating a fully functional prototype of SMMART implemented for Pocket PCs.

In this paper, we introduce a concrete, practical Ubiquitous Organizational Information (UOI) service framework, providing novice users intelligent and useful services with respect to the environment. The UOI framework based on the sensor networks is composed of 3-level hierarchical network architecture. To provide a rich array of services, the modular software framework and foundation software are designed and implemented on our hardware prototype. We define three representative UOI services and illustrate each service flow operating on the proposed UOI network. In addition, we describe some details in the implementation of a distributed UOI network on the UOI test-bed.

In the paper a novel methodology, TS-U, is proposed based on existing model checking techniques that were extended to successfully model the systems in a ubiquitous environment by introducing time and space constraints relevant in modeling of some ubiquitous system for its validation. Method proposed requires only slight modification of the existing model checking tools by introducing the notion of a Transition Checking Matrix (TCM) which holds time and space constraints for model’s transitions. By applying TS-U methodology, regular CTL formulae can be used without modifications to successfully check the system’s model as in the traditional model checking based on the Kripke structure.

With advanced technologies, computer devices have become smaller and powerful. As a result, many people enjoy ubiquitous learning using mobile devices such as Pocket PCs. Pocket PCs are easy to carry and use as a distance learning platform. In this paper, we focus on the issues of transferring the current PC based Sharable Content Object Reference Model (SCORM) to Pocket PC based. We will also introduce the Pocket SCORM Run-Time Environment (RTE) which has been developed in our lab. Pocket SCORM architecture is able to operate, even when the mobile device is off-line. It will keep the students’ learning record. When it is on line, the records will then be sent back to Learning Management System (LMS). With memory limitation, we provides course caching algorithm to exchange the course content on the Pocket SCORM.

This paper aims to develop a simulated system used for teaching and training basketball defensive strategies. Respectively, defensive strategies can be described within one method by editing video recorded from basketball games into desired clips for analysis and storing them into the database. In this paper, we used Spatial-Temporal Relationships to describe the local defensive movements by the basketball players in a game. The system will automatically capture tracks of defensive movements by the basketball players in the video clips, from which basketball coaches and players can learn various defensive strategies within the shortest period of time. The simulated system is expected to become a computerized educational aid to basketball teaching and training and to replace the unscientific and stereotyped system of basketball teaching and training.

Intelligent rooms are responsive environments in which human activities are monitored and responses are generated to facilitate these activities. Research and development on intelligent rooms currently focuses on the integration of multiple sensor devices with pre-programmed responses to specific triggers. Developments in intelligent agents towards intrinsically motivated learning agents can be integrated with the concept of an intelligent room. The resulting model focuses developments in intelligent rooms on a characteristic reasoning process that uses motivation to guide action and learning. Using a motivated learning agent model as the basis for an intelligent room opens up the possibility of intelligent environments being able to adapt both to people’s changing usage patterns and to the addition of new capabilities, via the addition of new sensors and effectors, with relatively little need for reconfiguration by humans.

We evaluated several multivariate stream data reduction techniques that can be used in sensor network applications. The evaluated techniques include Wavelet-based methods, sampling, hierarchical clustering, and singular value decomposition (SVD). We tested the reduction methods over the range of different parameters including data reduction rate, data types, number of dimensions and data window size of the input stream. Both real and synthetic time series data were used for the evaluation. The results of experiments suggested that the reduction techniques should be evaluated in the context of applications, as different applications generate different types of data and that has a substantial impact on the performance of different reduction methods. The findings reported in this paper can serve as a useful guideline for sensor network design and construction.

Graph Neuron (GN) is a network-centric algorithm which envisages a stable and structured network of tiny devices as the platform for parallel distributed pattern recognition. However, the unstructured and often dynamic topology of a wireless sensor network (WSN) does not allow deployment of such applications. In this paper, using GN as a test-bed application, we show that a simple virtual topology overlay would enable distributed applications requiring stable structured networks to be deployed over dynamic unstructured networks without any alteration.

Consisting of a large number of sensing and computational devices distributed in an environment, a sensor network can gather and process data about a physical area in real time. Due to the limited computing power in each sensor, limited bandwidth connections, limited storage and other limitations, how to deal with the data and uncertainty knowledge is one of the most important and central problems in such kind of distributed systems. This paper presents a graphical model based intelligent system that can model the uncertainty knowledge in sensor networks. This system uses belief messages as a basis for communication. We focus on parameter learning process for building the model, and experiments are presented.

The communicative behaviors in Wireless Sensor Networks(WSNs) can be characterized by two different types: routing and broadcasting. The broadcasting is used for effective route discoveries and packet delivery. A blind flooding approach for broadcasting generates many redundant transmissions. The Dominant Pruning(DP) algorithm is reduced the redundant transmissions of packets based on 2-hop neighborhood information. However, in DP(include TDP/PDP) algorithm, a particular node is frequently selected as a rebroadcasting node and its life-time is shortened. As a result, DP algorithm is insufficient in terms of the overall energy dissipation in sensor network. In this paper, we propose the algorithm based on Partial Dominant Pruning(PDP) algorithm to enhance sensor network lifetime. We compare and analyze the simulation result of our algorithm with PDP.

Wireless Ad Hoc networks are particularly vulnerable due to their fundamental characteristics such as an open medium, dynamic topology, distributed cooperation and constrained capability. Location information of nodes can be critical in wireless ad hoc networks, especially in those deployed for military purposes. In this paper, we present a set of protocols for anonymous routing to prevent location disclosure attacks in wireless ad hoc networks.

Ubiquitous computing as the integration of sensors, smart devices, and intelligent technologies to form a “smart space” environment relies on the development of both middleware and networking technologies. Several kinds of smart space middleware have been developed and OSGi (Open Service Gateway Initiative) was initiated mainly for interoperability support with service distribution among various middleware environments. In this paper, we analyze the weaknesses in the OSGi service platform such as a non-distributed framework, passive user management, device management, and service bundle management. Moreover, we propose that in a smart space environment, Location-aware SBM (Service Bundle Manager) is most capable of efficiently managing various service bundles. This paper concludes with the implementation results for the SBM.

We present a

C

ontext-Aware and

A

ugmented Reality-supported service

F

ram

e

work for distributed and collaborative interactions in

U

biquitous environments (U-CAFÉ). The proposed approach adopts semantic web-based context management and reasoning for supporting context-aware services. Further, it utilizes augmented reality for providing more relevant and human-centered interactions and collaborations. A semantic web representation language, Topic Map, is used to manage and reason about ubiquitous service-related contexts explicitly and systematically. Augmented reality-based interactions are used for embedding virtual models onto physical models considering contexts and for enabling bi-augmentation between virtual and physical models. The proposed framework has been successfully applied to design collaboration and intelligent home services.

Cooperative learning links students together to help them attain their learning objective under the guidance of teachers. With the spread of the Internet, cooperative learning has attracted educational technology interest, and research is proceeding into the use of bulletin boards, teleconferencing and chat rooms, etc., to support cooperative learning systems. However, cooperative learning systems tend to be used independently of distance learning, and very little work is being done on cooperative learning methods that include distant lectures. We believed that if remote lectures could be included in cooperative learning by students, the effectiveness of this cooperative learning could be improved. The article proposes a methodology for incorporating distant lectures in cooperative learning and provides an experimental evaluation. To evaluate this method we created a cooperative learning prototype and performed evaluations within our department.

The ubiquitous computing paradigm has made the telemedicine field being changed. However, research on the telemedicine field in a ubiquitous environment has not been carried out yet. In this paper, we have designed and implemented a ubiquitous medical image processing system for telemedicine applications based on the time-triggered message-triggered object (TMO) structuring scheme that is a distributed real-time object model. The initial version of our system is named KoMIPS (Konkuk Medical Image Processing System) that is a result of joint work with a Samsung Medical Center team. KoMIPS is a stand-alone system. Currently, KoMIPS is being extended to run on a ubiquitous environment. The extended version, named u-KoMIPS (ubiquitous KoMIPS), is designed with the TMO model and its execution environment is based on TMOSM/Linux that is an execution engine for a TMO structured program on Linux. The u-KoMIPS can acquire a medical image from various medical image scanners (e.g., MRI, CT, gamma camera, etc.) and then convert it into a DICOM image, transfer the DICOM image to one or more clients. Then, a client can analyze, process, and diagnose the DICOM image. We expect that telemedicine applications based on our system would accurately acquire a medical image from various medical image devices and efficiently analyze it.

This paper describes the extended PARLAY X for the Adaptive Context-aware Personalized Service (ACPS) in a ubiquitous computing environment. It can be expected that the context-awareness, adaptation and personalization for the Quality of Service (QoS) / Quality of Experience (QoE) in a ubiquitous computing environment will be deployed. But the existing PARLAY X is lacking when considering QoS / QoE in network. To address this issue, this paper suggests the extended PARLAY X for ACPS. The objective of this paper is to support the architecture and the Application Programming Interface (API) of the network service for the context-awareness, adaptation and personalization in a ubiquitous computing environment. ACPS provides a user with QoS / QoE in network according to the detected context such as location, speed and user’s preference. The architecture of the extended PARLAY X for ACPS is comprised of a Service Creation Environment (SCE), the semantic context broker, and the overlay network. SCE uses Model Driven Architecture (MDA)-based Unified Modeling Language (UML) / Object Constraint Language (OCL) for an expression of context-awareness, adaptation, and personalization. The semantic context broker is a broker role between the SCE and PARLAY gateways. The overlay network is a broker role for QoS / QoE between PARLAY gateway and the IP network.

Context-awareness is an important part for ubiquitous computing. Many applications of ubiquitous computing have to access some related contexts in order to provide the right services at the right time and the right places. However, there are some challenges for applications in ubiquitous computing, especially for those in smart home. These challenges make the design of smart home applications much more difficult than other applications. Therefore, we propose a context-aware system, CASSHA (Context-Aware System for Smart Home Applications), which is designed for smart home applications. CASSHA consists of the components for processing, representation, provision, and coordination, and is able to provide required contexts for smart home applications without conflicts. The system overcomes most of the technical challenges for smart home applications, and satisfies the requirements for these applications.

Pyroelectric sensors can detect changes of infrared rays. Usually, typical pyroelectric sensors are the digital output type, used for lighting switches and security systems. We can acquire, however, limited information from such digital on or off signals. We can also acquire a wealth of sensor data by using the analog type. Thus, this paper proposes a new approach to human position detection that discriminates human height (adults or children) by using analog type pyroelectric sensors. The proposed method employs Fast Fourier Transform (FFT) to calculate human position and analyzes the spectrum distribution to discriminate between adults or children. We built an experimental room 2.5 meters square and 2.5 meters high. Analog type sensors were installed at intervals of 0.8 meters in a grid shape. The proposed position detection method can calculate human position even if two persons are in the same room. Our height detection method that discriminates between adults and children is almost 90% accurate. Future research targets are improvements in accuracy and the development of an application system using these sensors.

We look into the combination of a SIP application (IP based multimedia telephony) together with a context-aware smart environment. We start by describing a scenario where it is highly relevant to use such a combination. The combined application is called ENME, and is managing and moving communication sessions based on user context. We are realizing the service with SIP REFER and SIP extensions. We also discuss briefly other solutions such as ’virtual terminals’, and we identify pros and cons of the different solutions. The application is implemented, and runs on a model railroad system, but the context model itself is more general. A next step would be to deploy the application in other smart environments, and we look briefly into a hospital environment. We end the paper by identifying some human issues for the service to work properly, and relate these issues to the technical solutions.

We propose DartDataFlow, a semantic-base Sensor Grid to manage sense data. In our system, the data and subscriptions are all represents as RDF graph, so we provide a RDF Graph Filter to filter RDF graph to meet subscriptions. And also, we design an intelligent data dissemination framework to support different cases of data dissemination. This system integrates Semantic Web technology into Sensor Grid and can be used in intelligent transportation systems, military, weather forecast, environment monitor, etc.

In this paper, we describe an augmentation of everyday artefact called

sentient artefact

. A sentient artefact is expected to capture the user’s specific context implicitly and naturally from its original usage since such an everyday artefact has inherent roles and functionalities. Therefore, a context-aware space is built incrementally using the specific contextual information. We show three types of everyday artefact augmentation, and propose a sensor selection framework that allows an artefact developer to systematically identify desirable sensors. Also, we discuss expectations and issues on the augmentation through prototyping.

In the future, homes will have numerous intelligent communicating devices, and the user would like to configure and coordinate their actions. Appliances and people in intelligent environments will have some degree of mobility. If the user wants to go from one place to another, using the same community, the agent should be able to generalize the service, trying to build an equivalent collection of coordinating services. This ‘work in progress’ paper addresses this issue by proposing a multi-dimensional model that allows visualistation of devices, temporal relationships, mutual interdependencies and the environment dynamics. The model both offers a simplified means of visualising the task space and the interdependencies together with a means of reasoning about algorithmic solutions to task processing. The work is aimed at supporting research into Pervasive Home Environment Networks (PHEN) which is funded by the UK’s Department of Trade and Industry Next Wave Technologies and Markets programme.

Ubiquitous environments are characterized by their openness, dynamicity and autonomy. Electronic institutions are the agents’ counterpart of human organizations, which are specifically designed for providing support, trust, and legitimacy in ubiquitous applications. In this paper, we propose an algorithm for norms enforcement in electronic institutions as a coordination strategy in ubiquitous environments by introducing substitution rules that map the norms set for the electronic institution to normative rules that can be implemented in the protocols to govern agents’ interactions in ubiquitous environments.

Recently there are getting more and more systems and applications using RFID. There is a necessity of a framework for them. This paper presents a Java-based framework that offers a set of general services to support various RFID systems for different purposes and application scenarios. The framework emphasizes on the semantic data binding for contextual information mapping between real and cyber spaces. The Java interface classes are provided to support general communications among a RFID, a reader and an application. Real and cyber spaces are synchronized via dynamic and real-time mapping from symbolic strings or IDs to the semantic XML data representations that are more effectively and efficiently useable by RFID applications. In this paper, the architecture and functional modules of the Java-based RFID service framework are explained in detail.

Privacy is a major concern with RFID tags and many solutions have been proposed. As many approach requires secure hash function on each tag, cost of tags imposed by those solutions is significantly high for wide development. We propose a protocol that uses pre-calculated Bloom filter to send tag identity for increased privacy with little additional cost per tag. In our approach, secure hash function calculation is done in tag production phase and each tag does not have any hash functions. Instead, each tag must have random number generator and volatile memory.

RFID is rapidly being deployed because of its versatility. However, the privacy problem cannot be handled effectively because of limited capability of RFID tags. We propose a secure medium access control(MAC) protocol to solve the privacy problem. Our secure MAC protocol defines a special kind of tag called an “ownership tag”. The singulation procedure is well defined only if the ownership tag is involved in the singulation process. Instead of scrambling the information of ordinary tag using the ownership tag’s key information and just sending ownership tag’s information in clear form, we use forced collision generated by the ownership tag to let a reader know garbage bits that are inserted in ordinary tags. Security and performance analysis for the protocol are provided.

Any modern society should be concerned over the well-being of the visually impaired citizen. It is the responsibility of the society to lessen the inconvenience and anxiety experienced by the handicapped. In addition to helping one to avoid obstacles on the sidewalks, technology can further help in navigating to places. In this paper we attempt to create a supportive environment with timely and useful information to guide the visually impaired to comfortably roam in a city that cares.

Hints for traditional storage system come from three aspects: file or directory attribute layout, user input and file content analysis. But in the OBS (object-based storage), object, a new fundamental storage component different from traditional storage unit (file or block), provides ample hints for storage system, which are help for designing more intelligent (or smarter) storage device. RAID (redundant arrays of independent disks) is a popular mechanism to offer fault-tolerance storage. But RAID based on file or block interface has very limited intelligence. This paper presents a novel object-based device: ORAID (object RAID). ORAID consolidates disk space of individual disk into a single storage spool and implements object-sharing and fault-tolerance through the object-interface. In ORAID, storage object is stored in form of original block fragments and their XOR verification fragments are among the disks of the device. As the higher abstract of data encapsulation, storage object provides more intelligent properties, and ORAID has more effective ability to implement online data re-layout and online capacity expansion.

To gain high level of performance in distributed object oriented computing, a required level of reliability in objects has to be maintained. This brings in a set of complex requirements into consideration. Furthermore depending on the unpredictability of the underlying environment, the replication should have architecture for the adaptable fault tolerance so that it can handle different situations of the underlying system before the system fails. We propose a mechanism for analyzing the complexity of this underlying environments and designing a dynamically reconfigurable architecture. The architecture provides the user required reliability by analyzing the performance and the reliability of the underlying environment and then either adjusting the replication degree or adaptively shifting to a suitable replication protocol. This architecture is a part of the Juice system which supports adaptation properties for a distributed environment.

The latest IEEE 802.11i uses a keyed hash function, called

Michael

, as the message integrity code. This paper describes some properties and weaknesses of Michael. We provide a necessary and sufficient condition for finding collisions of Michael. Our observation reveals that the collision status of Michael only depends on the second last block message and the output of the block function in the third last round. We show that Michael is not collision-free by providing a method to find collisions of this keyed hash function. Moreover, we develop a method to find fixed points of Michael. If the output of the block function in any round is equal to any of these fixed points, a packet forgery attack could be mounted against Michael. Since the Michael value is encrypted by RC4, the proposed packet forgery attack does not endanger the security of the whole TKIP system.

Thanks to the spread of mobile technologies, we will be able to realize the ubiquitous computing environment, in which equipment connected to the Internet assists users in their activities without special care on their part. Then, a function to protect private information is needed. This paper proposes a model for protecting private information. The basic idea of our model is to make use of private information through a program which a user trusts. A user offers a trusted program to a partner and compels a partner to make use of his private information through this program. In this way, a user prevents illegal use of his private information.

The micro-mobility is an important aspect in ubiquitous communications, where the applications are anywhere and used anytime. In this paper, we analyze two solutions for IP micro-mobility. The first one is based on the Stream Control Transmission Protocol, which allows the dynamic address configuration of an association by means of the ASCONF messages. The second one is based on Session Iinitiation Protocol, which is the most popular protocol for multimedia communication over IP networks. Both in the single and simultaneous movements case, we show that for the SCTP solution, there is space for the further optimization of the handoff latency by using slight changes to the protocol. For the SIP solution, we show that for a correct and fast handoff, the SIP Server should be statefull.

Wireless sensor networks consist of small nodes with sensing, computation, and wireless communications capabilities. The energy efficiency is a key design issue that needs to be enhanced to improve the life span of the network. In this paper, we propose a Hierarchy-Based Multipath Routing Protocol (HMRP) for wireless sensor networks. In HMRP, the network will be constructed to layered-network at first. Based on the layered-network, sensor nodes will have multipath route to sink node through some candidate parent nodes. The simulation results show that our HMRP can improve the lifetime of sensor networks

.

This paper proposes an energy-efficient nonlinear programming based dynamic clustering protocol (NLP-DC) unique to sensor networks to reduce the consumption of energy of cluster heads and to prolong the sensor network lifetime. NLP-DC must cover the entire network, which is another basic functionality of topology control. To achieve these goals, NLP-DC dynamically regulates the radius of each cluster for the purpose of minimizing energy consumption of cluster heads while the entire sensor network field is still being covered by each cluster. We verify both

energy-efficiency

and

guarantee of perfect coverage

. Through simulation results, we show that NLP-DC achieves the desired properties.

Clustering algorithm is an essential element to implement a hierarchical routing protocol, especially for a large-scale wireless sensor network. In this paper, we propose a new type of energy-efficient clustering algorithm, which maximizes the physical distance between cluster head and gateway by a neighbor node discovery mechanism. Furthermore, a slave/master patching scheme is introduced as a useful means of further improving the energy-efficiency. It has been shown that the number of cluster heads can be reduced by as many as 21% as compared with the existing clustering algorithms.

We present a cryptanalysis on the short proxy signature scheme recently proposed in [11] and propose a novel short proxy signature scheme from bilinear pairings. Compared with the existing proxy signature schemes, the signature length of our scheme is the

shortest

. Our short proxy signature scheme satisfies all the properties required for proxy signatures. We prove that our scheme is secure in the random oracle model.

In the ubiquitous computing environment new service components should be able to connect to networks at any time, and clients also should be able to use them immediately even without extra settings. Jini is one of the widely used middlewares today. Although event management is an essential component of ubiquitous middlewares, Jini is distributed without event management service. Accordingly, we design and implement the event manager based on Jini and suggest three methods in which only right event consumer can listen to the event using Access-Control Lists and SPKI/SDSI certificates. In the proposed method, our event manager controls the access of events by putting trust checking engine on Jini.

This paper introduces a novel approach to enhancing safety through RFID technology, location tracking, and monitoring person-object interaction. We design and develop RFID-based wearable devices for (1)tracking people’s locations, (2)monitoring person-object interactions, and (3)tracking objects’ locations. An intelligent object reminder and safety alert system is proposed to relief the common safety-related worries many of us face in our everyday lives – “Where did I leave my keys?”, “Did I turn off the stove?”, or “Did I close all the windows in my house?” etc. Experimental results on the precision of object identification and location tracking are also presented.

Transactions within an embedded database management system face many restrictions. These can not afford unlimited delays or participate in multiple retry attempts for execution. The proposed embedded concurrency control (ECC) techniques provide support on three counts, namely – to enhance concurrency, to overcome problems due to heterogeneity, and to allocate priority to transactions that originate from critical host.

The plasticity-stability dilemma is a key problem for learning with data streams. On the one hand, the learner must be plastic enough to adapt to the new data. On the other hand, it must be stable enough to integrate information. In this paper, we try to resolve this problem using neural network trees (NNTrees). An NNTree is a decision tree (DT) with each non-terminal node containing an expert neural network (ENN). The NNTrees are plastic because they can adapt to the new data through retraining of the ENNs and/or through generation of new nodes. The NNTrees are also stable because retraining is performed partially and locally. In this paper, we propose an algorithm that can grow NNTrees effectively and efficiently. Experiments with several public databases show that the NNTrees obtained by the proposed methods are comparable with the NNTrees or DTs obtained with all data provided all-at-once.

To evolve robot controllers that generalize well, we should evaluate the controllers using as many environment patterns (evaluation patterns) as possible. However, to evolve the controllers faster, we should use as few evaluation patterns as possible in evaluation. It is difficult to know in advance what patterns can produce good controllers. To solve this problem, this paper studies co-evolution of the robot controllers and the evaluation patterns. To improve the effectiveness of co-evolution, we introduce fitness sharing in the population of evaluation patterns, and the inter-generation fitness in selecting good controllers. Simulation results show that the proposed method can get much better robot controllers than standard co-evolutionary algorithm.

An ideal ubiquitous computing environment can be a network system of such intelligent and human-friendly robots that never appear in front of humans except when needed. In this paper the distributed intelligent robot network (DIRN) is proposed as one kind of wireless sensor and actor networks (WSAN) consisting of one brain node and numerous sensor and actor nodes with human-friendly interfaces. In order to realize well-coordinated DIRNs, it is very important to develop a systematically computable knowledge representation language universal for any kind of device as well as efficient networking technologies. As a candidate for this purpose, the multimedia description language

L

md

was evaluated by applying it to simulation of DIRN-world interaction.

Interactive video browsing tools are designed for e-learning applications on future interactive TVs. The integrated system includes an authoring tool that produces multi-paths videos and a playback tool that uses video tracking technology and a remote controller. The playback tool enables multi-modal interaction between the user and a multi-story video clip. Three types of hyper-interactive controls are incorporated, which include a reference link of a video object to show supplementary information on the Web, a hyper link to enable hyper-video jumps, and a choice link for online answers to pre-designed questions. The underlying video is coded using the standard MPEG technology, with navigation information hidden in the user-defined data of MPEG. Thus, the default sequence of a hypervideo can also be presented using an ordinary video player.

In the field of multimedia content provision, many researchers investigate numerous techniques for adapting the content based on device, network, environment and user characteristics. In this paper, we present an MPEG-21 middleware design for dynamic content adaptation and we demonstrate a true mobile multimedia client that is able to communicate information about device and network characteristics and provide the necessary tools for the configuration of user preferences.

Ontology is a promising tool to model and reason about context in-formation in pervasive computing environment. However, ontology does not support representation and reasoning about uncertainty. Besides, the underlying rule-based reasoning mechanism of current context-aware systems obviously can not reason about ambiguity and vagueness in context information. In this paper, we present an ongoing research on context modeling which follows the ontology-based approach while supports representation and reasoning about uncertain context. This unified context model then is used as a framework in our implementation of the context management and reasoning module of our context-aware middleware for ubiquitous systems.

Devising switching schemes for networks of colliding and correlated RFID readers is a core challenge in the deployment of RFID networks. We derive optimal scheduling schemes for readers in RFID networks in four cases of practical importance. Most other cases can be reduced to a combination of these basic cases.

The reader collision problem occurs when the signal from one reader interferes with the signal from other readers. Solutions like RTS-CTS are not applicable because a reader may communicate with multiple tags simultaneously. In this paper, we describe Pulse, a distributed protocol to reduce reader collisions. The operation of the Pulse protocol is based on periodic beaconing on a separate control channel by the reader, while it is reading the tags. The protocol functions effectively with fixed as well as mobile RFID readers. We show, using simulation in QualNet, that using Pulse protocol, the throughput (overall read rate) is increased by as high as 98%(with 49 readers) as compared to “Listen Before Talk” (CSMA) and by 337%(with 9 readers) as compared to Colorwave. We also present an analytical model for our protocol in a single hop scenario.

Radio Frequency Identification (RFID) finds use in numerous applications involving item identification and tracking. In a typical application, RFID tags are attached to the items and are periodically queried by readers. Using a fixed placement of readers to guarantee complete coverage of all tags in a given area at all times increases the deployment costs. Also, most practical applications do not need complete coverage at all times. It is enough to provide complete coverage periodically, say each tag being covered every

τ

seconds. For such applications, using mobile readers to cover the area would be more cost-effective.

Given an area to be covered completely within a period

τ

, determining the number of mobile readers required, their placement and movement pattern, is a difficult problem. We have developed

RFIDcover

, an automated coverage planning tool, that addresses this problem. Given an application scenario and reader specifications,

RFIDcover

determines an optimal number of readers required to guarantee complete coverage within the specified period

τ

. It also generates a layout giving the placement and movement pattern of the readers. The architecture of

RFIDcover

is generic and extendible, making it easy to implement different application scenarios. In this paper, we present

RFIDcover

implementation for a retail inventory tracking application scenario and evaluate its effectiveness.

Real-time supply chain management, theft prevention, and environmental monitoring motivate the need for RFID systems. Battery-assisted RFID tags increase read range and reliability; however, batteries offer only a finite lifetime solution. Hence, an experiment in powering a battery-assisted passive RFID tag using ambient vibration energy was conducted. A piezoelectric power generator was designed at a resonant frequency of 52 Hertz, with potential power output of 500

μ

W. Manipulation of the electric signal from the generator through a power circuit produced 8mW pulses to the tag, resulting in successful communication with the reader. Power needs were compared to an earlier experiment in powering a Mica2Dot “Mote” showing a 88% decrease in necessary power supply and 90% decrease in charge time.

A new system for real-time customer relationship management is proposed. The system is based on deploying a network of RFID readers throughout an environment. Information about the presence or lingering of participating customers at different times of day is collected providing valuable marketing information for better service provision. The implementation of the proposed system includes a database management program and an intuitive user interface allowing real-time access to the data acquired by the network.

For RFID-based applications, the uniqueness of ID assigned to each RFID tag should be guaranteed. Several research/standard organizations such as EPCglobal, ISO/IEC, Ubiquitous ID Center, and so on, have developed their own Unique Item ID (UII) specifications. The existence of various UII schemes may cause interoperability problems between applications using different UII schemes when those applications are operated on future global Internet network environment. In addition, it is expected that the traffic for UII query will be increased ten-times higher than that for DNS query in the current Internet. In order to overcome these problems, this paper proposes a fast tree-based classification algorithm applicable for various UII schemes, which can make it efficient to construct global directory lookup services for RFID applications with various UII schemes. Since the proposed scheme can be operated on readers, it can not only distribute traffic loads for UII queries, but also global RFID networks.

Wide-spread deployment of sensor networks is emerging and it presents an economical solution to numerous problems. A number of applications are dependent on secure operation of the sensor network, however, and serious consequences are incurred if the network is compromised or disrupted. In the existing key pre-distribution scheme suitable for low power and resource sensor nodes, shared key is not guaranteed to be found and mutual authentication is not allowed. This paper thus proposes a new key pre-distribution scheme guaranteeing that any pair of nodes can find a common secret key between themselves by using the keys assigned by LU decomposition of a symmetric matrix of a pool of keys. Furthermore, it allows node-to-node mutual authentication. Analysis shows that the existing scheme requires a large number of keys in each sensor node to display a comparable performance as the proposed scheme. Therefore, the superiority of the proposed scheme is more substantial when the memory size of the sensor node is small.

Wireless sensor network consists of small battery powered sensors. Therefore, energy consumption is an important issue and several schemes have been proposed to improve the lifetime of the network. In this paper we propose a new approach called energy-driven adaptive clustering hierarchy (EDACH), which evenly distributes the energy dissipation among the sensor nodes to maximize the network lifetime. This is achieved by using proxy node replacing the cluster-head of low battery power and forming more clusters in the region relatively far from the base station. Comparison with the existing schemes such as LEACH (Low-Energy Adaptive Clustering Hierarchy) and PEACH (Proxy-Enabled Adaptive Clustering Hierarchy) reveals that the proposed EDACH approach significantly improves the network lifetime.

Wireless ad-hoc network is a collection of wireless mobile nodes dynamically forming a temporary communication network without the use of any existing infrastructure or centralized administration. It is characterized by both highly dynamic network topology and limited energy. So, the efficiency of MANET depends not only on its control protocol, but also on its topology and energy management. Clustering strategy can improve the performance of flexibility and scalability in the network. With the aid of graph theory, genetic algorithm and simulated annealing hybrid optimization algorithm, this paper proposes a new clustering strategy to perform topology management and energy conservation. Performance comparison is made between the original algorithms and our two new algorithms, namely an improved weighting clustering algorithm and a novel Genetic Annealing based Clustering Algorithm (GACA), in the aspects of average cluster number, topology stability, load-balancing and network lifetime. The experimental results show that our clustering algorithms have a better performance on average.

In cluster-based schemes such as LEACH, cluster reconfiguration algorithm is one of the most critical issues to achieve longer lifetime of sensor networks. In this paper, we propose a new energy efficient cluster reconfiguration algorithm, called EECRA. EECRA does not require any location or energy information of sensors, and can configure clusters with fair cluster regions such that all the sensors in a sensor network can utilize their energies equally. The performances of EECRA have been compared with LEACH and LEACH-C. We also show that EECRA can be well applied to the environments that sensors are moving.

In this paper we propose a new routing protocol called virtual sink rotation (VSR) routing for large-scale sensor networks. VSR can efficiently handle a large number of sources as well as a large number of sinks with potential mobility. Each sensor node is not required to know the global network topology nor the location awareness. The main ideas underlying the VSR are two folds. First, to alleviate the frequent location updates associated with multiple mobile sinks, the algorithm introduces a

virtual sink

, which acts as a data collection and dissemination center to collect the data from all the sources and forward them to the actual sinks. This virtual sink can easily support multiple sinks as well as the mobility of the sinks. Second, to address the excessive energy consumption among the sensor nodes around a sink, VSR employs

virtual sink rotation

, which distributes the role of the virtual sink over all the participating sensor nodes, thus achieving a uniform energy distribution across the entire sensor field and prolonging the lifetime of the network. Experimentation results confirm that the VSR routing can significantly save energy while it can also reduce both the message delay and the message delivery failures compared to previous schemes.

Some sensor applications are interested in collecting data from multiple regions. For supporting such applications with multiple target regions, most conventional protocols are based on either a network flooding or multiple unicastig to cover those more than one target region. Either one will result in a lot of redundant packets to transmit by energy scared sensor nodes. To alleviate this problem, we propose a novel geocasting scheme which can make a suitable shared path among multiple target regions. We utilize the theorem of “Fermat Point,” in order to find an optimal junction point branching into each region. By using this shared path, an interest dissemination can be performed very efficiently. Our simulation study shows that the proposed scheme FERMA reduces a lot of network traffic and achieves significant energy saving as the number of target regions increase.

We propose PPVR, a power-aware position vector routing protocol for wireless sensor networks. PPVR is an energy efficient geographical routing protocol that improves existing geographic routing protocols in two ways. First, in the forwarding phase, PPVR reduces the transmission energy by passing packets through a relay node called a power-aware node. Second, PPVR provides an efficient void node avoidance scheme that mitigates the cases forwarding packets to a wrong path so that higher route discovery success rate is achieved. The simulation results shows that the PPVR outperforms existing geographic routing protocols including GPSR and GEAR, in terms of the energy consumption and the successful delivery rate.

In this paper, we consider the multicast routing with minimum energy cost and minimum delay (MEMD) in wireless sensor networks under the access control scheme of Spatial Time Division Multiple Access (STDMA). We formulate and explore both MEMD multicast and ME multicast, and show that the latter is just the Maximum Leaf Spanning Tree (MLST) problem, which is NP-complete. A 2-approximation algorithm is proposed for the MLST problem through improving a known one. Based on this algorithm, an approximation algorithm is obtained for the MEMD multicast problem. To further improve the delay result, we provide another approximation algorithm for our main problem using a different approach. These algorithms are all near linear in the size of the network graph, and also are shown to have good performance by simulation results.

In wireless channel environments, location estimation error is inevitable when we use the ROA(Received signal strength Of Arrival) for location estimation. Because of multi-path fading and shadowing the received signal strength can not be obtained appropriately in wireless channel. Especially in NLOS(Non-Line Of Sight) environments, the location estimation error is increased significantly. Therefore, it is required to consider the wireless channel to reduce the estimation error. In this paper, we propose a new location estimation scheme to work precisely in NLOS environments. Reference nodes more than three are used to broadcast their location information continuously and each sensor node sorts the average received signal strength considering shadowing characteristics. We use the residual weighting algorithm[1] for ROA location estimation to obtain higher accuracy. As a result, we can obtain accurate location estimation only using location estimation scheme without any special device for location awareness.

In this paper, we propose an energy-efficient target localization scheme (TLS) based on a prediction model that can reveal the most likely zone the target will be in, and also a corresponding two-step communication protocol between base station (BS) and sensors. BS uses a query mechanism to determine which sensors should be used for detailed information according to a limited amount of data received from the sensors. This scheme reduces both energy consumption and communication bandwidth requirement, prolongs the lifetime of the wireless sensor networks. Simulation results indicate that it can achieve a high accuracy while saving a large amount of energy.

This paper presents a framework for a congestion reduction mechanism in multiple objects tracking applications. The multiple objects tracking application has a real-time characteristic, through which all packets should be delivered in as timely fashion as possible. The proposed framework consists of sink nodes, backbone nodes, mobile nodes and agent nodes. The location information of the mobile node is delivered to the sink node using both localization and routing techniques, which consider the network congestion. The proposed congestion reduction technique avoids network congestion by decreasing the number of transmitting packets based on the idea that network congestion occurs when the total data in transit is greater than the total channel capacity. The decrement is achieved by both merging and attachment operations, which consolidate several small packets into one large packet in intermediate backbone nodes. The mechanism also considers a time-constrained delivery to assure the user’s service request. The simulation is conducted using a TOSSIM simulator, and the result shows that the proposed mechanism improves performance in terms of the successful delivery ratio and the delay time.

Wireless sensor networks, which are composed of advanced MEMS (Micro-Electro-Mechanical-Systems) called sensor nodes, has been broadly researched as ad-hoc networks recently. Since sensor nodes are powered by limited-life batteries and are usually deployed in severe environments, they need to be able to conserve their power consumption as well as guarantee broad coverage and connectivity. In active sensor networks, such as RFID sensing systems, shorter sensing and communication ranges will result in a higher measuring precision and more efficient energy dissipation. In this paper, we propose a novel self-controlling method for sensor nodes to decide the most appropriate sensing radius, communication radius, and an active/sleep schedule simultaneously. The energy-saving effect is proved in our simulation section.

Recently, the verification method of schedulability of real-time operating systems using timed automata have been developed. On the other hand, as soft real-time systems such as distributed systems and multimedia systems have been increasing, it is important to design soft real-time systems. Especially, performance analysis methods are important for soft real-time systems. In this paper, we develop the automata-theoretic performance analysis method of soft real-time systems by extending the verification method of schedulability of hard real-time systems using utility functions.

The increasing pervasiveness of wide-area distributed computing resources, like computational Grids, has given rise to applications that have inherent problems of complexity, adaptability, dynamism and heterogeneity etc. The emerging concept of autonomic computing holds the key to the self-management of such a multifarious undertaking and provides a way to further build upon this complexity without incurring additional drawbacks. Furthermore, access to Grid services at present is generally limited to devices having substantial computing, network and memory resources whereas most of mobile devices do not have the sufficient capabilities to be either direct clients or services in the Grid environment. The existing middleware platforms like Globus do not fully address mobility, yet extending the potential of the Grid to a wider audience promises increase in its flexibility and productivity. In this paper, we present a component-based autonomic middleware that can handle the complexity of extending the potential of the Grid to a wider mobile audience, by incorporating the features of context-awareness and self-management. We also address the middleware issues of job delegation to a Grid service, support for disconnected operation/offline processing and secure communication.

Autonomic Systems are essentially about creating self-managing systems based on the biological metaphor of the non-conscious acting autonomic nervous system. The Autonomic initiative has been motivated by ever increasing complexity and total cost of ownership of today’s system of systems. Autonomicity also offers inroads in terms of fault-tolerant computing and assisting in creating survivable systems. This paper examines the relevant technologies including Agents for engineering autonomicity and survivability in a secure location biometric system.

Autonomic Computing (AC), self-management based on high level guidance from humans, is increasingly gaining momentum as the way forward in designing reliable systems to hide complexity and conquer IT management costs. Effectively, AC may be viewed as Policy-Based Self-Management. In this paper we look at the motivation for utilizing NASA requirements-based programming technologies for mechanically transforming policies (expressed in restricted natural language, or appropriate graphical notations) into a provably equivalent formal model that can be used as the basis for code generation and other transformations, with the goal of self-generation of provable autonomic policies.

DDoS(Distributed Denial of Service) is the most troublesome attack nowadays, especially for those people whose operational environment relies on network services and/or the Internet. However

,

attackers often penetrate innocent routers and hosts to make them unwittingly participate in such a large scale attack as zombies or reflectors. In this paper, we propose an Intrusion Detection System (IDS), named CUSUM Intrusion Detection System (CIDS), which invokes CUSUM as its detection algorithm and logically divides Internet into many autonomous network management units (NMUs), each deploys a CIDS to discover attacks and identify what role a client in such an attack acts as.

Regarding the design of a multimedia digital content distribution system, the important issues are to supply a large amount of multimedia digital content to users and to guarantee the security of digital content. In this study we proposed designing a security technique for each group in a multilayered structure, and on a caching technique, which is based on this security technique, and to improve the user’s response speed. Using these techniques guarantees the security of digital content distribution.

We propose an access control scheme for developing authorization rules for XML documents, allowing flexible data granularity and authorization propagation. To simplify the complex access control policies in XML, we introduce a new tool:

Authorization Policy Sheet

(APS). Complex access control rules can be easily described in an APS. The administrator of a system can easily manage the access control of the system. With aid of Data Type Definitions(DTD), the policies given in an APS can be converted into a standard XML code that can be implemented in a normal XML environment.

Software rejuvenation is a preventive and proactive solution that is particularly useful for counteracting the phenomenon of software aging. In this article, we consider a periodic software rejuvenation model based on the steady-state system availability in discrete operational circumstance. More precisely, we treat a telecommunication billing application as a simple ubiquitous application, and describe its stochastic behavior by applying the discrete renewal reward process. The main objective is the determination of the optimal frequency to rejuvenate the ubiquitous application, maximizing the steady-state system availability. Also, we develop a statistically non-parametric algorithm to estimate the optimal rejuvenation schedule with the discrete total time on test concept.

Dependability for a ubiquitous computing system must be guaranteed for each single component of a system and for the whole system, which—designed to fulfill a certain task—might be more than just a sum of its components. Ubiquitous computing systems must enable the testing not only each of software components separately but also of the whole system. In this paper, we propose a management mechanism for applying software rejuvenation technology into a ubiquitous computing system. It adopts the automatic monitoring scheme, the automatic analysis scheme, the autonomic plan and the execution scheme to suggest the optimal configuration alternative of a ubiquitous computing system. We validate the autonomic fault management scheme based on a workload model derived from the system log analysis.

A Radio-Frequency-Identification (RFID) tag is a small and cheap device which is combined in IC chip and an antenna for radio communications. The RFID tag is used for management of goods and used as a substitute for a bar code. However, RFID system may infringe on a consumer’s privacy because it has a strong tracing ability. In this paper, we propose a key change scheme which can prevent previous owner from reading the RFID tag after changing its owner. By using our scheme, previous owner cannot read and trace ID information on the RFID tag. Moreover it is possible to combine other privacy protection scheme with our scheme because our scheme uses only symmetric key cryptography.