Embedded and Ubiquitous Computing: IFIP International Conference, EUC 2007, Taipei, Taiwan, December 17-20, 2007, Proceedings (Lecture Notes in Computer Science, 4808)

It has been widely recognized that embedded and ubiquitous computing will have tremendous impacts on many aspects of our daily life. Innovation and close collaboration between academia and industry are the keys to guaranteeing success in the development and deployment of the technology in embedded and ubiquitous computing. TheIFIP InternationalConferenceonEmbeddedandUbiquitous Computing (EUC) provides a forum for engineers and scientists in academia, industry, and governmentto address challenges and to present and discuss their ideas, results, work in progress and experience. The Technical Program Committee (TPC) of EUC 2007 was lead by the TPC Chair, Tei-Wei Kuo, and TPC Vice Chairs. A strong international TPC was formed to review and evaluate the submissions. Each paper was reviewed carefully by at least three TPC members or external reviewers. It was extremely di?cult for the TPC to select the presentations because there were so many excellent and interesting submissions. There were 217 submissions from all over the world, and only 65 papers are published in this proceedings volume. Title Page Preface Organization Table of Contents Real-Time Loop Scheduling with Energy Optimization Via DVS and ABB for Multi-core Embedded System Introduction Motivational Examples Models and Concepts Power Model Rotation Scheduling The Energy Optimization Loop Scheduling with DVS and ABB Algorithm Experiments Conclusion A Software Framework for Energy and Performance Tradeoff in Fixed-Priority Hard Real-Time Embedded Systems Introduction Related Work Proposed DEPS Framework System Model Problem Formulation for Static Application of DEPS Decision Algorithm for Selecting Candidate DEPS Configurations Implementation of Static DEPS A Case Study Simulation Environment Setup Experimental Results Conclusion References A Shortest Time First Scheduling Mechanism for Reducing the Total Power Consumptions of an IEEE 802.11 Multiple Rate Ad Hoc Network Introduction The Shortest Time First Scheduling Performance of the STFS Conclusions Energy Efficient Scheduling for Real-Time Systems with Mixed Workload Introduction Related Work Aperiodic Real-Time Task Scheduling Schemes On-Line Inter-task DVS Strategies for Period Tasks Dynamic Reclaiming Algorithm Existing Inter-task DVS Algorithm for Mixed Workload Real-Time Systems System Model, Assumptions and Notations Proposed SS-DVS Algorithm Simulation Results Simulation Model Effect of the Workload of Aperiodic Tasks on Energy Consumption and Response Time Effect of BCET/WCET Ratio of Periodic Tasks on Energy Consumption Conclusion References Function-Level Multitasking Interface Design in an Embedded Operating System with Reconfigurable Hardware Introduction Related Work Functional-Level Multitasking Interface Design Prototype Implementation and Experimental Results Conclusions Task Scheduling for Context Minimization in Dynamically Reconfigurable Platforms Introduction Problem Definition Problem Properties $\mathcal{NP}$-Complete Subproblems Subproblems in $\mathcal{P}$ Conclusion Compiler Support for Dynamic Pipeline Scaling Introduction Related Work The Proposed Approach Basic Idea Evaluation Model for Switching Pipeline Modes DPS Enabling Experimental Results System Configuration Experimental Results Conclusions Parallel Network Intrusion Detection on Reconfigurable Platforms Introduction Architecture Basic Concepts and Data Structures Algorithms Implementation Conclusion Evaluating Mobility Support in ZigBee Networks Introduction Overview IEEE 802.15.4 ZigBee Network Layer Mobility Support in ZigBee Mesh Topology Mobile End Device Mobile Router Mobility Support in ZigBee Tree Topology Mobile End Device Mobile Router Evaluation Scenarios with Varying Percentage of Mobile Nodes Scenarios with Mobile Nodes of Varying Speed Conclusion On Using Probabilistic Forwarding to Improve HEC-Based Data Forwarding in Opportunistic Networks Introduction Related Work and Overview of the H-EC Scheme Related Work H-EC: An Overview HEC-PF: H-EC with Probabilistic Forwarding Delivery Probability Probabilistic Forwarding Evaluation Evaluation I: Two-Hop Scenario Evaluation II: Variable $H$ Scenarios Evaluation III: Variable $k$ Scenarios Conclusion Employment of Wireless Sensor Networks for Full-Scale Ship Application Introduction Characteristics of Ships and of the WSN Technologies Full-Scale Ship Tests Using the WSN Data Delivery Ratio for Zigbee WSN Tests in Main Engine-Room Investigation of the WSN Characteristics at the Test Bed Battery Consumption Tests Conclusion References Improving the Performance of the Wireless Data Broadcast by the Cyclic Indexing Schemes Introduction The System Architecture The Proposed Alphabetic Huffman Algorithms The Numerical Analysis Conclusions References Revisiting Fixed Priority Techniques Introduction Discrete Scheduling by Empty-Slot Method Empty-Slot Method Discrete Static-Priority Schedulability Analysis Discrete Static-Priority Schedulability Test Comparisons with Classical Continuous Schedulability Tests Enhanced Deasibility Analysis Previous Results on Exact Test Deadline Monotonic Analysis Improved Experimental Results Conclusions and Future Work A Server-Side Pre-linking Mechanism for Updating Embedded Clients Dynamically Introduction LyraOS Related Work Design and Implementation Server-Side Pre-linking Client-Side Loading Component Relocation Component Protection Performance Comparison of Space Overheads Component Loading/Pre-linking Time Component Invocation Time Conclusion References Real-Time Scheduling Under Time-Interval Constraints Introduction Time-Interval Model QoS Metric Scheduling Approach Offline Feasibility Test Experimental Evaluation Conclusions and Future Work Towards a Software Framework for Building Highly Flexible Component- ased Embedded Operating Systems Introduction Related Work An overview of our Software Framework The overall structure Supports for Black-Box Software Reuse Supports for Runtime Structure Evolution Construction Process and Supporting Tools Experimental tudy Reorganize uC/OS-II into a Component-Based One TICK, a Component-Based EOS Conclusion and Future Works References A Study on Asymmetric Operating Systems on Symmetric Multiprocessors Introduction Related Work - Virtualization Full-Virtualization Para-virtualization Pre-virtualization Design and Implementation Approach and Overview Boot Sequence of SIGMA Linux Memory Management InterOS Communication Device Management Performance Evaluation LMbench Memory Access Collision Engineering Cost Discussion Limited Memory Protection Estimated Use Cases Conclusion An Efficient Code Generation Algorithm for Code Size Reduction Using 1-Offset P-Code Queue Computation Model Introduction 1-Offset P-Code Queue Computation Model Code Generation Algorithm Augmented LDAG Construction {\tt dup} Instruction Assignment and Ghost Nodes Elimination Increase in Number of Instructions Experiments Discussion Conclusion Interconnection Synthesis of MPSoC Architecture for Gamma Cameras Introduction Background MPSoC System Design Architecture Overview Interconnection Synthesis Experimental Results and Discussions Conclusion Integrated Global and Local Quality-of-Service Adaptation in Distributed, Heterogeneous Systems Introduction Related Work Resource Management Framework Matrix Framework QoS Levels Application Adapter Integrated QoS Adaptation Approach Local Adaptation Mechanism Global Adaptation Mechanism Pseudo-Code for Integrated Approach Example Implementation and Evaluation Implemented Modules Evaluation Conclusions and Future Work Toward to Utilize the Heterogeneous Multiple Processors of the Chip Multiprocessor Architecture Introduction The Processor-in-Memory Architecture The Octans System Statement Splitting and WPG Construction Weight Evaluation Experimental Results Conclusions References Consensus-Driven Distributable Thread Scheduling in Networked Embedded Systems Introduction Dynamic Distributed Real-Time Systems Contributions and Related Work The DUA-CLA Algorithm Models Rationale and Design Algorithm Description Constructing Section Schedules Algorithm Properties Implementation Experience Conclusions and Future Work Novel Radio Resource Management Scheme with Low Complexity for Multiple Antenna Wireless Network System Introduction System Model and Problem Formulation System Model Problem Formulation Proposed Radio Resource Management Scheme Subcarrier Allocation by Avoiding Using Ill-Conditioned Subcarrier Power Allocation among Users and Subcarriers Simulation Results and Analysis Conclusions References Modelling Protocols for Multiagent Interaction by F-logic Introduction F-Logic The AUML Introduction to the AUML Notations the Agent UML Transformation Rules and Deductive Rules Introduction to the E-Commerce Example of a Multiagent System Transformation Rules of the AUML/F-Logic The Deductive Rules of the AUML/F-Logic Related Work Conclusion References Adding Adaptability to Mailbox-Based Mobile IP Introduction A Mailbox-Based Scheme An Adaptive Algorithm Performance Evaluation Conclusion References Palpability Support Demonstrated Introduction Active Surfaces The Prototype Games Implementation PalCom Runtime System Simulation Framework Services Assemblies The Puzzle Game Evaluation Conclusions and Future Work GPS-Based Location Extraction and Presence Management for Mobile Instant Messenger Introduction Location Extraction and Place Annotation Context-Aware Presence Management The MIM System Design Implementation and Evaluation MIM Client and Map Display Evaluation of ${i-Cluster}$ Algorithm Presence Reasoning Logic Conclusion and Future Work Bilateration: An Attack-Resistant Localization Algorithm of Wireless Sensor Network Introduction and Related Work Problem Formulation LS, LMS and LLMS Least Square Least Median Square Linear LMS Bilateration Simulation Influence of Average Number of Anchors Influence of Percentage of Compromised Nodes Influence of Distance Measurement Error Tradeoff Between Performance and Communication Complexity Computation Complexity Analysis Conclusion and Future Work ID-Based Key Agreement with Anonymity for Ad Hoc Networks Introduction Preliminaries Bilinear Pairing Parameters for ID-Based Cryptosystems from Pairing Anonymous Key Agreement Schemes Static Pair-Wise Key Agreement Dynamic Pair-Wise Key Agreement Tripartite Key Agreement with Anonymity Group Key Management Conclusions and Future Work References Buffer Cache Level Encryption for Embedded Secure Operating System Introduction Related Work Buffer Cache Level Support Performance Evaluation Conclusions and Future Work SOM-Based Anomaly Intrusion Detection System Introduction Self-organizing Maps (SOMs) About SOM Algorithm The Steps of the Learning Algorithm of SOM Data Sampling, Preprocess, Standardization and Training Data Sampling and Preprocess Standardization Data Training Experiment Result and Its Analysis Conclusions References TCP-Taichung: A RTT-Based Predictive Bandwidth Based with Optimal Shrink Factor for TCP Congestion Control in Heterogeneous Wired and Wireless Networks Introduction Network Model Adaptive Network Bandwidth Approach In the Increasing $cwnd$ Phase While the Expected Network Bandwidth Is Enough In the Decreasing $cwnd$ Phase While the Expected Network Bandwidth Is Insufficient Numerical Results Scenario 1: $N$ TCP Connections in a Wired Network Scenario 2: $N$ TCP Connections in a Wired Network with a Single Wireless Link Conclusions References Dynamic Rate Adjustment (DRA) Algorithm for WiMAX Systems Supporting Multicast Video Services Introduction System Model DRA Simulation Results Conclusion References Efficient and Load-Balance Overlay Multicast Scheme with Path Diversity for Video Streaming Introduction Background and Related Work Multi-path Streaming Multiple Description Coding (MDC) Topology-Aware Hierarchical Arrangement Graph (THAG) Topology-Aware Load-Balance Hierarchical Independent Tree (TLHIT) Independent Multicast Trees in Virtual Graph Extending Virtual Graph to Hierarchical Structure Member Joining to Virtual Graph Simulation Results Average Received Descriptions and Stretch Stress and Delay Distribution Conclusions and Future Work References A Cross Layer Time Slot Reservation Protocol for Wireless Networks Introduction Description of the Proposed CLTSR Theoretical Analysis Simulation Results Conclusions References An Efficient Handoff Strategy for Mobile Computing Checkpoint System Introduction Preliminaries The Recovery Scheme The Data Structure and Denotations The Checkpointing and Logging The Handoff Strategy Independent Recovery Garbage Collection Correctness of the Algorithm Performance Study Conclusion References A Lightweight RFID Protocol Using Substring Introduction Review of Li et al.’s Scheme Vulnerabilities of Li et al. Scheme The Replay Attack Disclosing the Secret Value $SID$ A New Lightweight RFID Authentication Protocol Analysis Security Analysis Performance Analysis Conclusion and Future Work References The Reliability of Detection in Wireless Sensor Networks: Modeling and Analyzing Introduction Detection Models Model Construction Fault Probability of Detection Probability of Detection Reliability Probability Estimation Theoretical Analysis Sensing Improvements Probability Analysis Illustrative Example Intrusion Detection System Impact of Sensing Improvements Related Work Conclusions and Future Work Fast and Simple On-Line Sensor Fault Detection Scheme for Wireless Sensor Networks Introduction System Model and Problem Formulation Network Operation Sensor Fault Types Sensor Fault Detection Scheme Record Table Proposed Scheme Simulation Results Error Rate of Fault Detection Simulation Setup Results and Analysis Conclusions References An Activity-Centered Wearable Computing Infrastructure for Intelligent Environment Applications Introduction Challenges Involved in Designing Intelligent Environments Activity Recognition Situative and Multi-modal Interaction Design Maintaining a Model of the Environment Privacy and Personalization An Activity-Centered Wearable Computing Infrastructure Experimental Set-Up and Evaluation Conclusions References Finding and Extracting Data Records from Web Pages Introduction Basic Observations and Properties Finding the Dominant List of Records in a Page Dividing the List into Records Edit-Distance Similarity Measure Generating the Candidate Record Lists Choosing the Best Candidate Record List Extracting the Attributes of the Data Records Experience Related Work References Towards Transparent Personal Content Storage in Multi-service Access Networks Introduction Related Work Use Cases Model Description Storage Server Placement Algorithm (SSPA) Implementation and Evaluation Striping and Resilience Conclusion Extraction and Classification of User Behavior Introduction Related Work The Model Experiments and Results Conclusion Future Work A Floorplan-Based Power Network Analysis Methodology for System-on-Chip Designs Introduction Preliminaries The Modeling Technique for Reused Blocks The Motivation The Proposed Method The Full-Chip Analysis Methodology Full-Chip Equivalent Resistive Circuit The Analysis Procedures Experimental Results Studies on the New Modeling Technique Studies on the Resolution of Grids Conclusions A Multi Variable Optimization Approach for the Design of Integrated Dependable Real-Time Embedded Systems Introduction and Paper Objectives Related Work System Model and Problem Statement The MVO Approach Quantification of Design Variables Interactions Scheduling Length Bandwidth Utilization The Algorithm - Employing MVO The MVO Function Application of SA The Transformation Operator $\Gamma$ Evaluation of the MVO Framework Experimental Settings Experimental Results Conclusions SystemC-Based Design Space Exploration of a 3D Graphics Acceleration SoC for Consumer Electronics Introduction Preliminary 3D Graphics Rendering Pipeline 3D Graphics Acceleration SoC Platform Building System Configurations Simulation Environment Hardware/Software Configurations Design Space Explorations Cache Size Optimization Without Hardware Acceleration Performance of Hardware Acceleration Efficiency of Bus Transfer Mode Performance Bottleneck on Clear Buffer Performance of Geometry Processing Characteristics of 3D Graphics Benchmarks Conclusions References Optimal Allocation of I/O Device Parameters in Hardware and Software Codesign Methodology Introduction Cost Models Formulation of Exact Minimization Design Methodology Experimental Results Conclusion References A Semantic P2P Framework for Building Context-Aware Applications in Multiple Smart Spaces Introduction System Architecture Overview Data Model Sensor Wrapper Local Context Storage Data Mapping Query Routing Subscription Application Development Prototype Measurements Bootstrapping Dynamic Characteristic Response Time Analysis Query Processing Capability Related Work Conclusion References Usage-Aware Search in Peer-to-Peer Systems Introduction Literature Overview Problem Description Solution Locality of Reference Properties Active Networks Distributed Computing Usage-Aware Search Mechanisms Simulation Results Test Case 1: Temporal Locality Test Case 2: Geographical Locality Test Case 3: Spatial Locality Conclusions References A Service Query Dissemination Algorithm for Accommodating Sophisticated QoS Requirements in a Service Discovery System Introduction QoS Requirement Classification A General Algorithm Performance Analysis Conclusion References User Preference Based Service Discovery Introduction Related Work Design Considerations Decentralized Architecture Qualifying Service Selection Network Implosion Avoidance Architecture Quality of Service Discovery Query Service Conformance Score Calculation Multicast Response and Service Selection Implementation Performance Evaluation Conclusion References An Optimal Distribution of Data Reduction in Sensor Networks with Hierarchical Caching Introduction Cost Model Optimal Distribution of Data Reduction Solution of the Optimization Problem Sample Problem with Two Levels Sample Problem with Four Levels Related Work Conclusion MOFBAN: A Lightweight Modular Framework for Body Area Networks Introduction Related Work Properties of a WBAN Modular Framework Modules Controller Module Required Modules Optional Modules Communication Future Work Conclusion Performance Analysis for Distributed Classification Fusion Using Soft-Decision Decoding in Wireless Sensor Networks Introduction Fault-Tolerant Distributed Detection and DCSD Fusion Rule Performance Analysis Numerical and Simulation Results Conclusions and Future Works Hard Constrained Vertex-Cover Communication Algorithm for WSN Introduction Related Work Communication Problem Formulation Evolutionary Approach for Solving the Communication Problem Chromosome Representation Experimental Results Conclusion and Future Directions References A Selective Push Algorithm for Cooperative Cache Consistency Maintenance over MANETs Introduction Greedy Walk-Based Selective Push Providing Delta Consistency by Pull with TTR Selective Push Greedy Walk-Based Data Update Propagation Analysis of the Greedy Walk Strategy Experimental Evaluation Experimental Methodology and Configurations Evaluating the Greedy Walk Strategy Effects of Tuning the Number of Caching Nodes Effects of Tuning the Cache Query Rate Conclusion and Future Work References A Constrained Multipath Routing Protocol for Wireless Sensor Networks Introduction Related Work Protocol Design Details Route Discovery Phase Data Relay Phase Failure Recovery Phase SOS Double Path - {SOS_d} Simulation Performance Metrics Non-ideal Conditions Conclusions References PerSON: A Framework for Service Overlay Network in Pervasive Environments Introduction and Motivation Related Work and Limitations Architecture of PerSON PerSON Stack Physical Network Connections Overlay Network Prototype Implementation PICO Implementation Using PerSON Emergency Response System Features of PerSON Light-Weight Framework Heterogeneous Network Connectivity Dynamic Service Discovery and Routing Conclusion References Universal Adaptor: A Novel Approach to Supporting Multi-protocol Service Discovery in Pervasive Computing Introduction Related Work System Model and Architecture Universal Adaptor Primitives (UAP) Universal Adaptor Mapping (UAM) Prototype Implementation and Experience Conclusion References U-Interactive: A Middleware for Ubiquitous Fashionable Computer to Interact with the Ubiquitous Environment by Gestures Introduction Related Works U-Interactive System Architecture U-Interactive Infrastructures on the U-TOPIA Internal Architecture of U-Interactive Coordination of Location Service Management of Interactive Object Interactive Object Registration Interactive Object Discovery Target Selection in a Virtual Map Interaction Methods UbiSpace Implementation and Experiment Conclusions Towards Context-Awareness in Ubiquitous Computing Introduction Definitions of Context Acquiring Contexts Acquiring Physical Contexts Acquiring Computing Contexts Acquiring User Contexts Modeling Context Data Structure Integrity Manipulation Adapting to Contexts What to Adapt How to Adapt When to Adapt Challenges for Context-Awareness in Ubiquitous Computing Real-Time Embedded Software Design for Mobile and Ubiquitous Systems Introduction Previous Work Design and Verification Flow in VERTAF UML Modeling Real-Time Embedded Software Scheduling Formal Verification Component Mapping Code Generation Analysis and Evaluation Conclusions and Future Work Schedulable Online Testing Framework for Real-Time Embedded Applications in VM Introduction Related Works Target Application Model Online Testing Service Online Testing Framework An Isolated Testing Environment Preemptible Checkpointing and Recovery Logging and Reconstructing Experiments Cost Analysis for Testing Sequence Scheduling Online Testing and Space Overhead Conclusion Scalable Lossless High Definition Image Coding on Multicore Platforms Introduction Motivation for the Multicore Approach Studying Digital Cinema Solutions Scaling State-of-the-Art Software Solution Traditional Parallelization Approach in JPEG2000 JPEG2000 Flow Traditional Approach in Parallelizing JPEG2000 Coding Oblivious Parallelization Paradigm Illustration and Rationale Modeling the Computation Power of Platform Experimental Results Conclusion and Future Work References Self-stabilizing Structure Forming Algorithms for Distributed Multi-robot Systems Introduction System Model and Problem Specification Mobile Robot Model Basic Definitions Problem Specification and Analysis Self-stabilizing Structure Forming Algorithms Shape Mapping First Algorithm Second Algorithm Experimental Study Conclusion References Author Index This book constitutes the refereed proceedings of the International Conference on Embedded and Ubiquitous Computing, EUC 2007, held in Taipei, Taiwan, in December 2007. The 65 revised full papers presented were carefully reviewed and selected from 217 submissions. The papers are organized in topical sections on power aware computing, reconfigurable embedded systems, wireless networks, real-time/embedded operating systems, embedded system architectures, scheduling and resource management, mobile computing, system security, network protocols, fault tolerance, human-computer interface and data management, hw/sw co-design and design automations, service-aware computing, sensor networks, ad hoc and sensor networks, ubiquitous computing, and embedded software designs