Embedded and Ubiquitous Computing – EUC 2005

Embedded systems are now ubiquitous and ubiquitous computing is now getting embedded in our day-to-day lives. Such systems are cost and power sensitive. Various nanotechnologies will provide an excellent vehicle to reduce cost and power consumption, while still meeting performance constraints. Nanoscale device technologies, such as carbon nanotube transistors, nanowires, resonant-tunneling devices, quantum cellular automata, single electron transistors, tunneling phase logic, and a host of others, have made significant advances in the last few years. However, circuit and system design methodologies for these technologies are still in their infancy. Industrial roadmaps project that these emergent technologies will make inroads in the commercial market within a decade. Therefore, such design methodologies are necessary for precise design and fabrication of nanocircuits and nanoarchitectures.

With the advance of system level integration and system-on-chip, the high-tech industry is now moving toward multiple-core parallel embedded systems using hardware/software co-design approach. To design and optimize an embedded system and its software is technically hard because of the strict requirements of an embedded system in timing, code size, memory, low power, security, etc. while optimizing a parallel embedded system makes research even more challenging. The research in embedded systems needs integrated efforts in many areas such as algorithms, computer architectures, compilers, parallel/distributed processing, real-time systems, etc.

With progress of both fixed and mobile networks, various ubiquitous information services have been brought up to apply in actual business scene. In fact, it becomes possible to receive and send information in various access points not only in offices but also in cars through sophisticated ubiquitous terminals such as PDA, cellular phone, mobile PC and so on. Moreover, the spread of RFID-tag application to household commodities will accelerate the popularization of ubiquitous services. Every ubiquitous terminal will have RFID reader/writer on board in near future. By using the ubiquitous information service environment, variety of services such as e-government, e-bank, e-commerce, Intelligent Transport Systems service that usually require customized services for each customer has already been provided. However, high-tech crimes such as skimming and phishing are increasing day by day inversely increment of its convenience. Such high-tech crimes were happened in worldwide actually. It is impossible to keep security by 4 or more digits PIN code any longer. Biometrics authentication is promising to protect against high-tech crimes in the present situation. I will give an overview of current ubiquitous information services, focusing on some of actual services in keeping security by biometrics authentication.

Future embedded imaging applications will be more demanding processing performance while requiring the same low cost and low energy consumption. This paper presents and evaluates a color-aware instruction set extension (CAX) for single instruction, multiple data (SIMD) processor arrays to meet the computational requirements and cost goals. CAX supports parallel operations on two-packed 16-bit (6:5:5) YCbCr data in a 32-bit datapath processor, providing greater concurrency and efficiency for color image and video processing. Unlike typical multimedia extensions (e.g., MMX, VIS, and MDMX), CAX harnesses parallelism within the human perceptual color space rather than depending solely on generic subword parallelism. Moreover, the ability to reduce data format size reduces system cost. The reduction in data bandwidth also simplifies system design. Experimental results on a representative SIMD array architecture show that CAX achieves a speedup ranging from 5.2× to 8.8× (an average of 6.3×) over the baseline SIMD array performance. This is in contrast to MDMX (a representative MIPS multimedia extension), which achieves a speedup ranging from 3× to 5× (an average of 3.7×) over the same baseline SIMD array. CAX also outperforms MDMX in both area efficiency (a 52% increase versus a 13% increase) and energy efficiency (a 50% increase versus an 11% increase), resulting in better component utilization and sustainable battery life. Furthermore, CAX improves the performance and efficiency with a mere 3% increase in the system area and a 5% increase in the system power, while MDMX requires a 14% increase in the system area and a 16% increase in the system power. These results demonstrate that CAX is a suitable candidate for application-specific embedded multimedia systems.

EISC (Extendable Instruction Set Computer) is a compres-breal sed code architecture developed for embedded applications. In this paper, we propose a DSP-enhanced embedded microprocessor based on the 32-bit EISC architecture. We present how we could exploit the special features, and how we could overcome the deficits, of the EISC architecture to accelerate DSP applications with a relatively low hardware overhead. Our simulations and experiments show that the proposed DSP-enhanced processor reduces the average execution time of the DSP kernels considered in this work by 47.8% and the DSP applications by 29.3%. The proposed DSP enhancements cost about 10300 gates and do not increase the clock frequency. The proposed DSP-enhanced processor has been embedded in an SoC for video processing and proven in silicon.

In this paper an intelligent sensor for fingerprint recognition is proposed. The sensor has the objective to overcome some limits of the fingerprint recognition software systems, as elaboration time and security issues related to fingerprint transmission between sensor and processing unit. Intelligent sensor has been prototyped using the Hamster Secugen sensor for image acquisition and the Celoxica RC1000 board, employing a Xilinx VirtexE2000 FPGA, for image processing and analysis. Resources used, elaboration time as well the recognition rates in both verification and identification modes are reported in the paper. To the best of our knowledge, this is the first implementation for a full hardware implemented fingerprint recognition system.

Low power register file design plays an important role in an embedded processor. In this paper, we exploit register-usage in a program to find out unused registers, and turn these unused registers into low power mode by annotating power-controlling instructions. The whole work is performed by applying the hardware/software co-design principle. For the hardware part, we propose a voltage-scaling control logic to supply voltages for each register. For the software part, we propose a power-controlling-code annotation approach to determine the voltage scaling behavior for each register. Simulation results show that the proposed approach outperforms the other related approaches in terms of the energy-delay product.

jHISC is an object-oriented processor for embedded system aiming at accelerating Java execution by hardware approach. Garbage collection is one of the critical tasks in a Java Virtual Machine. In this paper, we have conduct a study of dynamic object allocation and garbage collection behavior of Java program based on SPECjvm 98 benchmark suite and MIDP applications for mobile phones. Life, size, and reference count distribution of Java objects are measured. We found most Java objects die very young, small in size and have small number reference counts. Reference counting object cache with hardware write barrier and object allocator is proposed to provide the hardware concurrent garbage collection for small size objects in jHISC. Hardware support on write barrier greatly reduces the overhead to perform the reference count update. The reference counting collector reclaims the memory occupied by object immediately after the object become garbage. The hardware allocator provides a constant time object allocation. From the investigation, over half of Java objects can be garbage collected by the object cache that makes it unnecessary for these objects to copy to the main memory.

The hit ratio of the first level cache is one of the most important factors in determining the performance of embedded computer systems. Prefetching from lower level memory structure is one of the techniques for improving the hit ratio of the first level cache. This paper proposes an effective prefetch scheme for the first level instruction cache by exploiting cache history information. The proposed scheme utilizes two factors to improve the prefetch efficiency: the disparity of block size between memory hierarchies and continuous same page hits. According to our simulations, the proposed prefetching scheme improves the performance by up to 6.3%.

System-on-a-chip (SoC) has emerged to become a cost-effective approach for embedded systems design with rapid advance of semiconductor technology. It allows designers to integrate a number of heterogeneous IP blocks together based on a system interconnect. However, traditional dedicated wiring as the system interconnect has many shortcomings, such as non-scalable global wire delay, failure to achieve global synchronization, and errors due to signal integrity issues. These problems can be mitigated by the network-on-chip (NoC) architecture based on regular on-chip communication networks. In this paper, we present three efficient switch designs for NoC systems based on circuiting switching. Such switch designs with efficient buffer management can provide the on-chip network with guaranteed throughput and transmission latencies.

Increasing the processor resources usability and boosting processor compatibility and capability to support multi-executions models in a single core are highly needed nowadays to benefit from the recent developments in electronics technology. This work introduces the concept of a dynamic switching mechanism (DSM), which supports multi-instruction set execution models in a single and simple processor core. This is achieved dynamically by execution

mode

–

switching

scheme and a

sources

–

results

locations computing unit for a novel queue execution model and a well-known stack based execution model. The queue execution model is based on queue computation that uses queue-registers, a circular queue data structure, for operands and results manipulations and assigns queue words according to a single assignment rule. We present the DSM mechanism and we describe its hardware complexity and preliminary evaluation results. We also describe the DSM target architecture.

This paper focuses on the design of hardware framework with DSP based on embedded face recognition door manager system including the detailed technology of circuit design among the image sensor, DSP, the door manager controller, FLASH, SDRAM, RJ45 port, timer and reset. At the same time, both the programs and algorithms are discussed in the paper. The program on face recognition has been tested on the designed board; it runs all right with fixed light condition. Not only the size and cost of the board are small, but also it is fast and highly reliable.

The major goal of self-adaptive software is to provide a mechanism that allows a software system to dynamically change its architectural configuration during run-time to cope with requirement changes and unexpected conditions. Software which needs to handle dynamically changing internal and external environment is one of the areas in which self-adaptive software may do an important role in improving the reliability and performance of software systems. There are three main capabilities that are necessary to support self-adaptive software: the ability to monitor and recognize internal/external situations that affect behavior of the software system; the ability to determine when and what to reconfigure in the software system to handle the situations; and the ability to dynamically change the software architecture during run-time to make the reconfiguration effective. In this paper, we describe a software framework to support such capabilities to realize self-adaptive software and its experiment results.

This paper presents the design and implementation of Accounting System that is a resource monitoring and restriction system. The system improves the reliability and security of a system. Accounting System is a generic to offer various services, such as security improvement, overload control, class-based accounting, and resource reservation that require CPU resource control.

Loop distribution and loop fusion are two e.ective loop transformation techniques to optimize the execution of the programs in DSP applications. In this paper, we propose a new technique combining loop distribution with direct loop fusion, which will improve the timing performance without jeopardizing the code size. We .rst develop the loop distribution theorems that state the legality conditions of loop distribution for multi-level nested loops. We show that if the summation of the edge weights of the dependence cycle satis.es a certain condition, then the statements involved in the dependence cycle can be distributed; otherwise, they should be put in the same loop after loop distribution. Then, we propose the technique of maximum loop distribution with direct loop fusion. The experimental results show that the execution time of the transformed loops by our technique is reduced 21.0compared to the original loops and the code size of the transformed loops is reduced 7.0% on average compared to the original loops.

In this paper we present a quality of service (QoS) adaptive framework for dynamic reconfiguration of component-based real-time systems. Our framework is light-weighted enabling reconfiguration in resource constrained embedded environments. Furthermore, it is possible to reconfigure both components and aspects of a system, hence, enabling finer tuning of a real-time system. Real-time QoS guarantees are maintained in the system and under reconfiguration by employing feedback-based scheduling methods.

As a promising technology that enables ubiquitous computing and leads IT industries of next generation, sensor networks (SN) are foreseen to expand and populate the globe in such a way as the present Internet does. In this scenario, new challenges appear with such massive deployment, as the constant interaction of nodes and networks will transform them in dynamic entities that will need to evolve with their environment. In this paper, we discuss the future of sensor networks defining the concept of evolvability and its application. We also describe ANTS, a complete new architecture for wireless sensor networks, as our implementation to solve the challenges imposed by this evolvable future.

The widespread use of embedded systems mandates a rigorous engineering approach towards embedded software development, i.e. model-based design of embedded software. The paper presents design models of reusable and reconfigurable state machines that have been conceived in the context of the COMDES framework and in particular – the State Logic Controller and the Hybrid State Logic Controller, whose principles of operation are presented in the paper. The latter has been instrumental in developing a reconfigurable executable component, i.e. a function block of class State Machine, which can be used to implement a broad range of embedded applications such as sequential, continuous and hybrid control systems, as well as complex systems specified with hierarchical and concurrent state machines.

Embedded systems have strict timing and code size requirements. Retiming is one of the most important optimization techniques to improve the execution time of loops by increasing the parallelism among successive loop iterations. Traditionally, retiming has been applied at instruction level to reduce cycle period for single loops. While multi-dimensional (MD) retiming can explore the outer loop parallelism, it introduces large overheads in loop index generation and code size due to loop transformation. In this paper, we propose a novel approach, that combines iterational retiming with instructional retiming to satisfy any given timing constraint by achieving full parallelism for iterations in a partition with minimal code size. The experimental results show that combining iterational retiming and instructional retiming, we can achieve 37% code size reduction comparing to applying iteration retiming alone.

H.264 provides various useful features such as improved coding efficiency and error robustness. These features enable mobile device to adopt H.264/AVC standard to achieve effective video communications. However, the encoder complexity is greatly increased mainly due to motion estimation (ME) and mode decision. We implemented a realtime H.264 encoding system based on DSP and FPGA chip using the propose scheme to jointly optimize inter mode selection and ME using the multi-resolution analysis. In our paper, we focus on reducing the complexity while maintaining the visual quality output. Experimental results show that the proposed algorithm is over 3 times faster than the existing method while maintaining the coding efficiency and the implemented system. The implemented H.264 encoder meets the common requirement of the real-time video coding [30 frames/sec].

Real-time embedded systems can be used in hightly important or even vital tasks (avionic and medical systems, etc.), thus having strict temporal constraints that need to be validated. Existing solutions use temporal logic, automata or scheduling techniques. However, scheduling techniques are often pessimistic and require an almost complete knowledge of the system, and formal methods can be ill-fitted to manipulate some of the concepts involved in real-time systems.

In this article, we propose a method that gives to the designer the advantages of formal methods and some simplicity in manipulating real-time systems notions. This method is able to model and validate all the classical features of real-time systems, without any pessimism, while guaranteeing the terminaison of the validation process. Moreover, its formalism enables to study systems of which we have only a partial knowledge, and thus to validate or invalidate a system still under design. This latest point is very important, since it greatly decreases the cost of design backtracks.

The checkpointing problem in real-time systems equipped with on-line fault detection mechanisms is dealt with from a reliability point of view. The reliability analysis is performed with the assumption that transient faults occur in accordance with a Poisson process and are detected immediately by the detection mechanisms. And the best equidistant checkpointing strategy that maximizes the reliability of the system against transient faults is derived.

A real-time database system supports a mix of transactions. These include the real-time transactions that require completion by a given deadline. At the support side, existing concurrency control procedures introduce delays due to non-availability of data resources. The present study makes an effort to introduce a higher level of parallelism for execution of real-time transactions. It considers simple extensions within a transaction processing system. These permit a real-time transaction to avoid delays due to ordinary transactions. These also eliminate elements of other unpredictable delays, due to deadlocks or simple waiting for data resources. Thus, the investigated procedures can perform critical functions in parallel to process time-critical transactions. In effect, it is a model of transaction execution that permits execution of real-time transactions without interference from other executing transactions, and by reducing other probabilistic delays.

Real-time embedded systems must satisfy system-level timing constraints between external sensor inputs and actuator outputs. Real-time scheduling theory can be used to verify that the system is schedulable, that is, no deadlines are missed, but that alone is not enough. Given that the system is schedulable, how to verify that it satisfies system-level end-to-end timing constraints, such as freshness, correlation and separation? To address this question, we adopt the approach of formal modeling and model-checking. Specifically, we use Timed Automata and the model-checker UPPAAL for verification purposes. We have developed generic modeling templates for a class of distributed task systems that can be used as input the the model-checker in order to verify system-level end-to-end timing constraints. We use an application example of distributed real-time control system to illustrate the utility of our approach.

In this paper, we consider the connected coverage problem and aim to construct a minimal connected cover set that is sufficient for a given query in wireless sensor networks. We propose a centralized, Voronoi tessellation (CVT) based algorithm to select the minimum number of active sensor nodes needed to cover the target region completely. The constructed sensor set proves to be connected when sensor node’s communication range is at least twice of its sensing range. For other situations where the CVT algorithm alone cannot guarantee the network connectivity, we design a Steiner minimum tree (SMT) based algorithm to ensure the network connectivity. Theoretical analysis and simulation results show that our algorithm outperforms the greedy algorithm in terms of both the time complexity and the needed number of sensor nodes that must be kept active to respond to a given query.

In this paper, we present a new energy-aware scheduling scheme for real-time applications using architectures that employ voltage scaling technologies. Both dynamic voltage scaling (DVS) and dynamic threshold voltage scaling (DVTHS) can benefit from this scheduling scheme. The start time of each task is adapted to enhance the efficiency of voltage scaling schemes while still satisfying the required time feasibility. The introduced scheduling scheme is able to escape local minima and it can generate near-optimal schedules in terms of energy reduction. The scheduling paradigm is integrated into our automated and multiobjective system-level co-synthesis tool that performs system optimization. We report in this paper up to about 30% higher energy reduction compared to only performance-aware scheduling.

In this paper, we focus on power-aware network devices, and propose a stochastic model to evaluate their performance quantitatively. More precisely, applying the Markovian additive process (MAP) to the arrival stream for network devices, we develop a stochastic dynamic power management (DPM) model with shutdown policy. Two performance measures for power-saving and processing; steady-state power consumption and throughput, are derived analytically for the DPM model. In numerical examples, we investigate the performance of the power-aware communication device with shutdown in terms of power-saving and processing.

Cluster-based routing protocol has special advantages to enhance scalability and efficiency of the routing protocol. The technique to network clustering that maximizes the network lifetime is an important topic of research in wireless sensor networks. In this paper, we present an energy aware cluster-based routing algorithm (ECRA) for the wireless sensor networks such that the network lifetime can be maximized. ECRA randomly selects some nodes as cluster-heads to construct Voronoi diagram and rotates the intra-cluster nodes to distribute the energy load to all sensors in the network. The simulations show that ECRA algorithm outperforms than direct communication, static clustering and LEACH. The system lifetime of ECRA is approximately 2 times than LEACH. This is because the ECRA rotates intra-cluster-heads to balance the load to all nodes in the sensor networks.

In energy-constrained settings, most low-power compiler optimization techniques take the approach of minimizing the energy consumption while meeting no performance loss. However, it is possible that the available

energy budget

is not sufficient to meet the optimal performance objective. To limit energy consumption within a given energy budget, energy-constrained optimization approach is more significant. In this paper, we present an energy-constrained prefetching optimization approach through which memory or CPU stalls (caused by too early or too late prefetching) can be reduced so that energy budget is met. Optimal performance objective is achieved under a given energy budget. We evaluate the effectiveness of our energy-constrained prefetching optimization approach through simulations.

Continuous improvements in semiconductor technology are supporting new classes of System-on-a-Chip (SoC) architectures that combine extensive processing logic with high-density memory. Such architectures are generally called Processor-in-Memory (PIM) or Intelligent Memory (I-RAM) and can support high-performance computing by reducing the performance gap between the processor and the memory. The PIM architecture combines various processors in a single chip. These processors are characterized by their computation, memory-access and power consumption capabilities. Therefore, a novel parallelizing system, SAGE II, has been developed to identify their capabilities and dispatch the most appropriate jobs to them in order to exploit the advantages of PIM architectures. However, the SAGE II system only can deal with performance issues but power consumption is gradually becoming an important issue of current computing systems. This paper provides a new low-power transformation mechanism, called Energy-Oriented Power Reduction Scheduling (EOPRS), to extend the capability of SAGE II system. It can reduce the power consumption for the Processor-in-Memory system without losing execution performance. The detailed EOPRS transformation technique is presented later. The experimental results of several benchmarks are also discussed.

This paper studies the buffer planning problem for interconnect centric floorplanning. Dead-spaces not held by blocks are the available location for buffer insertion. To make best use of these spaces for buffer requirements, we have to move blocks so that blocks’ room size is adjusted and dead-spaces could be redistributed. In this paper, we introduce a new algorithm to move blocks not only within its room, but also in the space currently held by other blocks by pushing away these blocks if necessary without violating the topological and the total area. After applying this method of redistributing dead-spaces, the number of nets satisfying delay constraint can be optimized.

The demand of integration of many heterogeneous semiconductor intellectual property (IP) blocks has been introducing a new chip design paradigm so called on chip network. This paradigm promisingly offers a packet switched network among IPs to reduce the main problems in the very deep sub micron technologies that arise from non-scalable global wire delay, failure to achieve global synchronization, errors due to the signal integrity, non-scalable bus based functional interconnection, etc. This paper introduces interconnected or switched network topologies and also analyze their performances in terms of communication protocol related to the issues such as routing strategy, buffer size, routing algorithm , etc. The above mentioned evaluations are done by utilizing the tool that has been widely used in the research domain of computer network design, so called NS-2.

We purposed a new Network on Chip (NoC) architecture called Hierarchical Graph. The most interesting feature of this novel architecture is its simple implementation process. Furthermore, the flexible structure of this topology makes it suitable for use in application specified chips. To benchmark the suggested architecture with existing ones, basic models of physical implementation have been extracted and simulated using NS-2. The results compared with the common used architecture Mesh show that HG has better performance, especially in local traffics and high loads.

The key technology of the mobile multimedia application is System-On-Chip processor that integrates the major function unit with low power consumption using a small battery. The wireless communication is practical technology, which makes comfortable communications between devices, such as IEEE 802.11a/b/g and Bluetooth. By the modern streaming technology with compression, like mpeg, the wireless communication triggers high quality media service without wires.

The wireless communication spend a quite large portion of energy of mobile device if data flows continuously, hence a delicate energy control may needed to fulfill a saving of the limited energy. Due to these issues, integrating the wireless function units into the high performance embedded processor supports a seamless control of power consumption of wireless part, and the communication data flows are sealed in the SoC chip, which reduces inter-chip communiaction energy between a main processor and a wireless media access controller.

We focused the high performance wireless multimedia applications are suffered by the energy consumption, so we alleviated the power issue by integrating of IEEE 802.11a/b/g media access controller, modem, ADC/DAC, high performance DSP, and RISC core in a silicon.

We present a wireless capable SoC processor, GDM5104, that integrated the multiple wireless media access controller as well as CCK/ OFDM/ GFSK modem and ADC/DAC also. Furthermore, the processor integrates RISC and DSP independent cores with appropriate caches, and rich peripherals that sufficient to implement mobile multimedia applications, hence the processor exhibits wireless connectivity with low power consumption. The processor is fabricated in a 0.18um standard CMOS technology, and operates at 133MHz RISC, and 100MHz DSP, which provides full capability of wireless multimedia processing.

Cycle-accurate simulators are basic tools to evaluate performance improvements of computer architecture. Before confirming of the architecture improvements using cycle-accurate simulation, the simulator itself should be validated. However, off-the-shelf processors have been continuously improved, though the cycle-accurate simulators were not reflected the improved features. Simulation results show that the difference between the IPC (Instruction Per Cycle) of the modified model for ARM1136 (Sim-ARM1136) and the IPC of the original model for ARM7 (Sim-Outorder) is 19%, on average, which is large enough to mislead the impact of architecture improvements.

In this research work, we present a high-level prototyping of a new processor core based on Queue architecture as starting point for application-specific processor design exploration. Using modular design structure with control logic implemented as a set of communicating state machines, we show hardware emulation and optimizations results of a parallel queue proecssor architecture (QueueCore). We also show how to to fully exploit the capabilities of the designed QueueCore, while maintaining a common source base. From the evaluation results, we show that the QueueCore prototype fits on a single conventional FPGA device, thereby obviating the need to perform multi-chip partitioning which results in a loss of resource efficiency.

This paper proposes novel high-performance bus architecture for memory-intensive embedded multimedia SoCs. It has a pipelined bidirectional bus for high speed and small area. It has two separate bus called system bus and memory bus, where memory-intensive IPs are connected to memory bus so not to degrade system bus performance. To avoid starvation of low-priority masters, the proposed bus exploits probability-based arbitration policy where the arbitration probability of each master is determined in proportion to its execution time. To increase transmission bandwidth, it also exploits bus partitioning where several masters often access their slaves concurrently without multilayer structure. The proposed bus is designed, implemented, verified, and evaluated in hardware level. Simulation results show that the proposed bus improves effective bandwidth by 2.8~3.6 times and communication latency by 3.1~4.7 times when compared to AMBA bus.

Most of the new embedded systems require high performance pro- cessors at low power. To cater to these needs, most semiconductor companies are designing multi-core processors, also known as chip-multiprocessors, while some are developing multi-chip boards with existing multi-core processors. Developing applications on these powerful architectures require specialized tools to obtain the optimum performance. Most applications running on these processors not only require high processing power, but also have tight resource constraints. For both, chip-multiprocessors and multi-chip boards, one faces some common problems while developing applications for them. To meet this end, we have developed tools to model high-performance embedded applications on these complex high-end systems. We have integrated these tools in the modeling framework of MILAN, and have modeled a real application, Mpeg-2 Audio Video Decoder. For validation we have used Cradle Technologies MDSP multi-core chip as the target processor.

In the past, programming language are procedural, the design concept is based on the module and scope which are difficult to manage, but nowadays, the programming trend is Object-Oriented Programming (OOP), where objects are the key elements to build up application and the communications between different objects are through method invocation. A novel object-oriented processor offers an opportunity to enhance the system security, performance and provides a more effective way to manipulate OOP instead of using a software Virtual Machine. jHISC is a novel object-oriented processor which provides a natural way to map the concept of OOP into architectural level through the hardware object data structure. Our solution is to design secure hardware object data structures on a novel processor with Just-In-Time compilation for Java which then makes it possible to implement complex OO related bytecodes at hardware level and access some fields of object in parallel to improve the execution speed. It mainly targets J2ME and implements about 93% bytecodes and 83% OO related bytecodes in hardware directly.

Real-time software runs over real-time operating systems, and guaranteeing qualities are difficult. In this paper, we propose timed weak simulation relation verification and apply it to a refinement design method of real-time software. Moreover, we apply our proposed method to general real-time software scheduled by fixed-priority preemptive policy.

In this paper, for real-time embedded software we consider the problem of checking component-based designs for scenario-based timing specifications. By adding time intervals on the actions, we extend the interface automata for modelling real-time systems. The component-based designs are modelled by real-time interface automaton networks, which includes a set of real-time interface automata synchronized by shared actions, and the scenario-based timing specifications are specified by UML sequence diagrams with a set of boolean expressions. Based on analyzing the compatible integer state space of a real-time interface automaton network and its compatible reachability graph, we develop an algorithm to check the consistency between real-time component-based designs and the scenario-based timing specifications.

Algorithms that process geometric objects become more and more important for many safety-critical embedded systems, e.g. for motion planning or collision detection, where correctness is indispensable. The main challenge to demonstrating correctness is the consistent handling of degenerate cases like collinear line segments. In this paper, we therefore propose the use of an interactive theorem prover to develop dependable geometry algorithms for safety-critical embedded systems. Our solution is based on the use of a three-valued logic to make degenerate cases explicit. Using the theorem prover, we are not only able to prove the correctness of the obtained algorithms, but also to directly derive a software library of provably correct geometry algorithms for safety-critical applications.

In the present paper, we propose a novel area management method based on the concept of “pressure”. Plastic Cell Architecture (PCA) is a dynamically reconfigurable architecture that was proposed paying attention to the essentials of processing and the flexibility of Von Neumann architecture. Mechanisms in which area are managed require a function similar to “malloc” in the C language. However, for dynamically reconfigurable architectures such as PCA, uniform management and parallelism are incompatible. Therefore, it is necessary for any PCA circuit to determine its own vacant areas without assistance from an administrator. We therefore introduced a new area management method that obtains the vacant areas by moving the surrounding objects by “pressure”. “Pressure” is realize by adding new command set to original commands of PCA. We describe the basic structure for the new command set, and consider herein the development of three new command sets. Finally, we evaluate these command sets with respect to execution area and rate of effective use.

This paper describes the design and evaluation of the PCA (Plastic Cell Architecture) cell, which implements a novel space allocation method. PCA is a dynamically reconfigurable architecture which exceeds the FPGA (Field Programmable Gate Array) in flexibility and generality. Circuit dynamically reconfiguration is achieved as administrators manage the heap areas. But, because objects operate and require new space in parallel, it is difficult to manage them collectively. So, we introduced the concept of pressure, which enables space allocation. As a simulation result, we found that this new method, which relies on pressure commands, could solve the problems of object management efficiently. We designed the PCA cell with space allocation capability. Consequently, the number of gates per PCA cell is 200, and the maximum delay time per cell is 3.55 ns. Moreover, the 3×3 PCA cell processing of six space-allocation commands consumes 306.3

μ

W.

In this paper, we introduce a framework for the automatic configuration of applications running in dynamic environments where changes are frequent. We propose a way to describe, for each application, its configuration policy, and the execution environment’s factors that affect its behavior. On this basis, we can generate application-specific configuration tools, called

conflets

. The application’s source code is not required. The conflet combines the information drawn from the execution environment with the knowledge of the configuration policy. It is therefore able to detect when and how the execution environment modifies its characteristics, and can automatically react by reconfiguring the application and thus adapting it to the dynamic environment.

This paper develops path concepts for the execution of different algorithms on a reconfigurable architecture. New architecture concepts demand for permanent evaluation of such extensions, also including validating case studies. The recently patented synchronous bit-serial pipelined architecture, which we investigate in this paper, comprises synchronous and systematic bit-serial processing without a central controlling instance. It targets future high speed applications due to the abdication of long wires. The application specificity of the basic version of the architecture can be overcome by so called routers, achieving a reconfigurable system. This paper focuses on the difficulty to conceptualize these routers and proposes several variations for implementation. The case study, which comprises a combined version of the FDCT/IDCT algorithm, serves as an application example for the reconfigurability of the architecture. The example – implementing both algorithms in one operator network – broadens the application area of the architecture significantly.

Power flow analysis plays an important role in power grid configurations, operating management and contingency analysis. The Newton-Raphson (NR) iterative method is often enlisted for solving power flow analysis problems. However, it involves computation- expensive matrix multiplications (MMs). In this paper we propose an FPGA-based Hierarchical-SIMD (H-SIMD) machine with its codesign of the Hierarchical Instruction Set Architecture (HISA) to speed up MM within each NR iteration. FPGA stands for Field-Programmable Gate Array. HISA is comprised of medium-grain and coarse-grain instructions. The H-SIMD machine also facilitates better mapping of MM onto recent multimillion-gate FPGAs. At each level, any HISA instruction is classified to be of either the communication or computation type. The former are executed by a controller while the latter are issued to lower levels in the hierarchy. Additionally, by using a memory switching scheme and the high-level HISA set to partition applications, the host-FPGA communication overheads can be hidden. Our test results show sustained high performance.

In today’s system design, reconfigurable computing plays more and more an important role. By the extension of reconfigurable devices like FPGAs with one or more CPUs new challenges in system design should be solved. These new hybrid FPGAs (e.g. Virtex-II Pro

TM

), provides a hardcore general-purpose processor (GPP) embedded into a field of programmable gate arrays. Furthermore, they offer partial reconfiguration. Therefore, those hybrid FPGAs are very attractive for implementation of run-time reconfigurable embedded systems. However, most of the efforts in this field were made in order to apply these capabilities at application level, leaving to the Operating System (OS) the provision of the necessary mechanisms to support these applications. In this paper, an approach for run-time reconfigurable Operating System, which takes advantage of the new hybrid FPGAs to reconfigure itself based on online estimation of application demands, is presented. Especially run-time assignment and reconfiguration of OS services over hybrid architecture are discussed. The proposed model uses a 0-1 Integer programming strategy for assigning OS components over hybrid architecture, as well as an alternative heuristic algorithm for it. Furthermore, the evaluation of the reconfiguration costs are presented and discussed.

Dynamically reconfigurable computing systems (DRCS) provides an intermediate tradeoff between flexibility and performance of computing systems design. Unfortunately, designing DRCS has a highly complex and formidable task. The lack of tools and design flows discourage designers from adopting the reconfigurable computing technology. A UML-based design flow for DRCS is proposed in this article. The proposed design flow is targeted at the execution speedup of functional algorithms in DRCS and at the reduction of the complexity and time-consuming efforts in designing DRCS . In particular, the most notable feature of the proposed design flow is a HW-SW partitioning methodology based on the UML 2.0 sequence diagram, called

Dynamic Bitstream Partitioning on Sequence Diagram (DBPSD)

. To prove the feasibility of the proposed design flow and DBPSD partitioning methodology, an implementation example of DES (Data Encryption Standard) encryption/decryption system is presented in this article.

Existing operating systems can manage the execution of software tasks efficiently, however the manipulation of hardware tasks is very limited. In the research on the design and implementation of an embedded operating system that manages both software and hardware tasks in the same framework, two major issues are the dynamic scheduling and the dynamic placement of hardware tasks into a reconfigurable logic space in an SoC . The distinguishing criteria for good dynamic scheduling and placement methods include the total schedule length and the amount of fragmentation incurred while tasks are dynamically placed and replaced. Existing methods either do not take fragmentation into consideration or postpone the consideration of fragmentation to a later stage of space allocation. In our method, we try to reduce fragmentation during placement itself. The advantage of such an approach is that not only the reconfigurable space is utilized more efficiently, but the total schedule length is also reduced, that is, hardware tasks complete faster. Experimental results on large random tasks sets have shown that the proposed improvement is as much as 23.3% in total fragmentation and 2.0% in total schedule time.

An intelligent agent which is a software component for the efficient home network system is proposed in this paper. The agent consists of six modules such as the Agent Manager, the Data Collector, the Execution Controller, the Data Storage, the Data Queue and the User Interface. The Agent Manager manages the tasks of modules, and the Data Collector collects the data from home appliances through the RFID readers. The Execution Controller determines the operations of home appliances according to the conditions of the home environment and transfers the operations to the appliances through the RFID readers. Moreover, the Data Storage keeps the data which is necessary for the operations of the agent, and the Data Queue temporarily stores the data which is collected from home appliances. Lastly, the User Interface provides the graphical user interface in which an individual can directly control and monitor the home network. The proposed intelligent agent autonomously learns the circumstances of a home network by analyzing the data about the state of home appliances, and provides the best suited environment to the user. Therefore, the user can live in an optimal home environment without effort if he/she performs home networking through the agent.

Inthis paper, a self-growing engine based adaptation system, which automatically decides the more efficiency plan about the assigning of jobs, in a mobile, grid computing environment, is proposed. Recently, research relating to grid computing has become an important issue, achieving certain goals by sharing the idle resources of computing devices, and overcoming various constraints of the mobile computing environment. In this domain, most existing research assigns work only by considering the status of resources. Hence the situation of assigning work to a peer having relatively low work efficiency, is possible. The proposed system considers various contexts and selects the most suitable peer. In addition, the system stores the history of the work result, and if the same request occurs in the future, a peer is selected by analyzing the history. In this paper, a prototype used to evaluate the proposed system is implemented, and the effectiveness of the system is confirmed through two experiments.

Web caching and replication are efficient techniques for reducing web traffic, user access latency, and server load. In this paper we present a group-based method for dynamically selecting distribution strategies for web documents according to access patterns. The documents are divided into groups according to access patterns and the documents in each group are assigned to the same distribution strategy. Our group-based model combines performance metrics with the different weights assigned to each of them. We use both trace data and statistical data to simulate our methods. The experimental results show that our group-based method for document distribution strategy selection can improve several performance metrics, while keeping others almost the same.

Searching and finding items on the WWW is increasingly difficult for businesses and for consumers. Many navigation and keyword searches are inadequate for the modern consumer. What’s plaguing e-commerce is the lack of intelligent assistance. The e-Salesman System (eSS) [11], based on a knowledge-driven intelligent model, aims to simulate the human element of traditional shopping for online sales. This paper presents a tool for authoring and managing an intelligent system that will change the current approach to online browsing, searching, and shopping. The contribution of this solution is to allow merchants to customize and change their e-retail shops to interact with online users based on their dynamic changed models to meet their business rules and marketing needs.

In this paper, we propose a conceptual architecture for a personal semantic Web information retrieval system. It incorporates semantic Web, Web service, P2P and multi-agent technologies to enable not only precise location of Web resources but also the automatic or semi-automatic integration of Web resources delivered through Web contents and Web services. In this architecture, the semantic issues concerning the whole lifecycle of information retrieval were considered consistently and the integration of Web contents and Web services is enabled seamlessly.

Compared with topology-based routing, location-based routing scales much better in large-scale mobile ad hoc networks. Location-based routing protocols assume that a location service is available to provide location information of each node in the network. Many location service protocols have been proposed in the literature. However, either they do not scale well in large-scale network environment, or they are not reliable if the network is highly dynamic. We propose a multiple home regions based location service protocol in large-scale mobile ad hoc networks. Theoretical analysis shows that the proposed protocol outperforms existing protocols in terms of both scalability and reliability.

This paper presents an algorithm for global state detection based on peer-to-peer interactions. The interactions in distributed systems can be analyzed in terms of the peer-to-peer pairwise interactions of intervals between processes. This paper examines the problem: “If a global state of interest to an application is specified in terms of the pairwise interaction types between each pair of peer processes, how can such a global state be detected?” Devising an efficient algorithm is a challenge because of the overhead of having to track the intervals at different processes. We devise a distributed on-line algorithm to efficiently manage the distributed data structures and solve this problem. We prove the correctness of the algorithm and analyze its complexity.

This paper gives an efficient algorithm for recording consistent snapshots of an asynchronous distributed system execution. The nonintrusive algorithm requires 6(

n

–1) control messages, where

n

is the number of processes. The algorithm has the following properties. (P1) The application messages do not require any changes, not even the use of timestamps. (P2) The application program requires no changes, and in particular, no inhibition is required. (P3) Any process can initiate the snapshot. (P4) The algorithm does not use the message history. A simple and elegant three-phase strategy of uncoordinated observation of local states is used to give a consistent distributed snapshot. Two versions of the algorithm are presented. The first version records consistent process states without requiring FIFO channels. The second version records process states and channel states consistently but requires FIFO channels. The algorithm also gives an efficient way to detect any stable property, which was an unsolved problem under assumptions (P1)-(P4).

A Distributed Computing Systems (DCS) calls for proper partitioning of tasks into modules and allocating them to various nodes so as to enable parallel execution of their modules by individual different processors of the system. A number of algorithms have been proposed for allocation of tasks in a Distributed Computing System. Most of the models proposed in literature consider modules of a single task for static allocation, for the purpose of allocation onto a DCS. Moreover, they did not consider the architectural capability of the processing nodes and the way of connectivity among them. This work considers allocation of disjoint multiple tasks with their corresponding modules and proposes a parallel algorithm for a realistic situation wherein multiple disjoint tasks with their modules compete for execution on an arbitrarily connected DCS based on well-known A* technique. The proposed algorithm also considers a load balanced allocation for the purpose. The paper justifies the effectiveness of the algorithm with the experimental results by comparing with previously reported works.

Since sensors have a limited power supply, energy-efficient processing of queries over the network is an important issue. As data filtering is an important approach to reduce energy consumption, interest is used to be a constraint to filter uninterested data when users query data from sensor networks. Within these interested data, some of them are more important because they may have more valuable information than that of the others. We use ‘Reward’ to denote the importance level of data. Among the interested data, we hope to query the most important data first. In this paper, we propose a novel query model ETRI-QM and a new algorithm ETRI-PF (packet filter) dynamically combines the four constraints: Energy, Time, Reward and Interest. Based on our simulation results, we find out that our ETRI-QM together with ETRI-PF algorithm can improve the quality of the information queried and also reduce the energy consumption.

Wireless ad hoc networks face many challenges in routing, power management, and basic connectivity. Existing research has looked into using predicted node movement as a means to improve connectivity. While past research has focused on assuming wireless signals propagate in clear free loss space, our previous research has focused on using signal loss maps to improve predictions. This paper presents novel testing of signal loss maps in relation to the accuracy used for prediction purposes. Through analysis of test cases and results from a custom built simulator the performance is effectively measured.

In this paper, we propose an adaptive mobility management scheme for minimizing signaling costs in Hierarchical Mobile IPv6 (HMIPv6) networks. In our proposal, if the mobile node’s mobility is not local, the mobile node sends location update messages to correspondent nodes in the same way as Mobile IPv6 (MIPv6). After the creation of a spatial locality of the mobile node’s movement, the mobile node sends location update messages to the correspondent nodes in same way as HMIPv6. Therefore, our proposal can reduce signaling costs in terms of packet transmission delays in HMIPv6 networks. The cost analysis presented in this paper shows that our proposal offers considerable performance advantages to MIPv6 and HMIPv6.

An anti-collision algorithm is very important in the RFID system, because it decides tag identification time and tag identification accuracy. We propose improved anti-collision algorithms for RFID system using UHF. In the proposed algorithms, if the reader memorizes the Bin slot information, it can reduce the repetition of the unnecessary PingID command and the time to identify tags. If we also use ScrollAllID command in the proposed algorithm, the reader knows the sequence of collided ID bits. Using this sequence, we can reduce the repetition of PingID command and tag identification time. We analyze the performance of the proposed anti-collision algorithms and compare the performance of the proposed algorithms with that of the conventional algorithm. We also validate analytic results using simulation. According to the analysis, for the random tag ID, comparing the proposed algorithms with the conventional algorithm, the performance of the proposed algorithms is about 130% higher when the number of the tags is 200. For the sequential tag ID, the performance of the conventional algorithm decreases. On the contrary, the performance of the proposed algorithm using ScrollAllID command is about 16% higher than the case of using random tag ID.

The critical issue in sensor networks is the search of balance between the limited battery supply and the expected longevity of network operations. Similar goals exist in providing a certain degree of sensing coverage and maintaining a desirable number of sensors to communicate under the energy constraint. We propose a novel sensor network protocol, called Coverage-Aware Sensor Engagement (CASE) for coverage maintenance. Different from others, CASE schedules active/inactive sensing states of a sensor according to the sensor’s contribution to the network sensing coverage. The contribution is quantitatively measured by a metric called coverage merit. By utilizing sensors with large coverage merit, CASE reduces the number of the active sensors required to maintain the level of coverage. Simulation results show that CASE considerably improves the energy efficiency and reduces the computation and communication costs to maintain the required coverage degree in a dense sensor network.

Routing in a wireless mesh network is a heterogeneous interoperability problem. First, it is possible that some users may disable the relaying functions of their mobile devices in order to save the computing power and battery charge. This will results in heterogeneous relaying capabilities. Second, due to the absence of standard layer-3 ad-hoc routing protocols, various devices may employ different layer-3 routing protocols, making routing difficult. A trivial solution to the above two problem is to flood packets through the un-routable regions to reach the destination region. However, flooding is a brute force approach and will make a broadcast storm, resulting in low throughput of the whole network. In this paper, we propose a cross-layer approach to solve the above problem. Our analysis results show that the proposed cross-layer approach can efficiently provide interoperability without causing broadcast storm.

Sensor network applications need synchronized time to the highest degree such as object tracking, consistent state updates, duplicate detection, and temporal order delivery. In addition to these domain-specific requirements, sensor network applications often rely on synchronization as typical distributed system do: for secure cryptographic schemes, coordination of future action, ordering logged events during system debugging, and so forth. This paper proposes a Reliable Time Synchronization Protocol (RTSP) for wireless sensor networks. In the proposed method, synchronization error is decreased by creating hierarchical tree with lower depth and reliability is improved by maintaining and updating information of candidate parent nodes. The RTSP reduces recovery time and communication overheads comparing to TPSN (Timing-sync Protocol for Sensor Networks) when there are topology changes owing to moving of nodes, running out of energy and physical crashes. Simulation results show that RTSP has about 10% better performance than TPSN in synchronization accuracy and the number of message in the RTSP is 10%~35% lower than that in the TPSN when nodes are failed in the network. In case of different transmission range of nodes, the communication overhead in the RTSP is reduced up to 50% than that in the TPSN at the maximum.

A lot of recent research has been focused on developing network mobility management to support the movement of a mobile network consisting of several mobile nodes. In the mobile ad-hoc network environment, network itself can be moved to another point. For the network mobility, the IETF NEMO working group proposed the basic support protocol for the network mobility to support the movement of a mobile network consisting of several mobile nodes. However, this protocol has been found to suffer from the so-called ‘dog-leg problem’, and despite alternative research efforts to solve this problem, there are still limitations in the efficiency for real time data transmission and intradomain communication. Accordingly, this paper proposes a new route optimization methodology that uses unidirectional tunneling and a tree-based intradomain routing mechanisms which can significantly reduce delay in both signaling and data transmission.

In this paper, in accordance with requirements of different users and supplying effective usage of limited network resources, we propose a stable QoS routing mechanism to determine a guaranteed route suited for mobile ad hoc wireless networks. The manner exploits the received signal strength (RSS) techniques to estimate the distance and the signal change of the velocity to evaluate the breakaway. To ensure the QoS it chooses a steady path from the source to the destination and tries to reserve the bandwidth. Ultimately, it is clear to find that the performance never decrease even the growth of the overhead and the movement of users via the simulated by ns-2.

We study cooperative caching technique for supporting data access in ad hoc networks. Two protocols that are based on the notion of zone are proposed. The IXP protocol is push-based in the sense that a mobile node would broadcast an index message to the nodes in its zone to advertise a caching event. A data requester can fetch a needed item from a nearby node if it knows that it has cached the data. The second protocol, called DPIP, is explicitly pull-based with implicit index pushing property. A data requester may broadcast a special request message to the nodes in its zone asking them to help satisfy its demand. However, this is done only if its own caching information does not result in a successful fetch. Performance study shows that the proposed protocols can significantly improve system performance when compared to existing caching schemes.

SIP is promising for VoIP signaling to support personal mobility. In this paper, we introduce and compare single registration (SR) and multiple registration (MR) for personal mobility. The SR scheme can not support personal mobility without user’s assistance. In contrast, the MR scheme supports personal mobility inherently using sequential search or pure parallel search. Sequential search may suffer from long delay for call setup, while pure parallel search consumes network resource. To compromise the two schemes, we propose pipelined search for multiple registration.

Location-aware mobile services(LAMSs) are characterized by a large number of objects and a large number of queries. Moreover, with a large candidate data set, answering LAMSs via scanning through the whole data set becomes extremely expensive. In broadcast-based services, any number of clients can monitor the broadcast channel and retrieve the data as it arrives through the broadcast channel. Thus, a wireless broadcast system capable of answering LAMSs queries is considered a promising solution because it can serve a virtually unlimited number of users within its coverage. Furthermore, if the data is properly organized to cater to the needs of the clients, such a scheme makes effective use of the low wireless bandwidth, and is ideal for achieving maximal scalability. In this paper, we address the issues of supporting spatial queries of location-aware data via wireless data broadcast. A linear data broadcast based on their location is proposed to answer spatial queries on air. Comprehensive experimentation shows that the proposed scheme is highly scalable and is more efficient in terms of both tuning time and access latency in comparison to other techniques.

The “mobility” has two important aspects: i) how to support mobility and ii) how to exploit mobility. This paper considers the latter, while many existing works only consider the former. This work is trying to prove that system performance will be greatly improved by understanding a user’s movement. In this paper, we propose a novel location update protocol, called SLUP which minimizes the energy consumption of a mobile client by exploiting a syntactic information of the user’s movement. This concept is called

mobility-awareness

. Moreover, there are three variations of the proposed protocol in terms of choosing optimal state: SLUP/BS, SLUP/UITR, and SLUP/IUT 〈

T

iut

〉. Experimental results show that the proposed protocol outperforms the well-known protocols such as dead-reckoning and distance-based protocol, that the SLUP/IUT 〈

T

iut

〉 approach can achieve difference performance tradeoffs between energy efficiency and location imprecision by fine-tuning its algorithmic parameter

T

iut

.

Mobile user data mining focuses on finding useful and interesting knowledge out from raw data collected from mobile users. Frequency pattern and location dependent mobile user data mining are among the algorithm used in this field. Parallel pattern, our previous proposed method, extracts how a group of mobile users makes similar decisions, such as by moving towards the similar direction, or by viewing similar contents at the same time. Parallel pattern is triggered group behaviour of mobile users. This paper reports our refinement work on parallel pattern which incorporated

refinement of the relationships among parallel patterns, or relationship pattern,

which shows how ‘similarities of decisions’ are related to each other. Effects found are such as conditional relationship, where one parallel pattern has to happen before the next one occurs. Other effects includes associative, sequential and loop pattern effects. Our performance evaluation reports how relationship pattern performs in real life dataset and synthetic dataset and discusses some potential implementation issues.

Recent studies in wireless sensor networks (WSN) have observed that the irregular link quality is a common phenomenon, rather than an anomaly. The irregular link quality, especially link asymmetry, has significant impacts on the design of WSN protocols. In this paper, we propose two asymmetry-aware link quality services:

the neighborhood link quality service (NLQS)

and

the link relay service (LRS)

. The novelty of the NLQS service is taking the link asymmetry into consideration to provide timeliness link quality and distinguishing the inbound and outbound neighbors with the support of LRS, which builds a relay framework to alleviate the effects of link asymmetry. To demonstrate the proposed link quality services, we design and implement two example applications,

the shortest hops routing tree (SHRT)

and

the best path reliability routing tree (BRRT)

, on the TinyOS platform. We found that the performance of two example applications is improved substantially. More than 40% of nodes identify more outbound neighbors and the percentage of increased outbound neighbors is between 14% and 100%. In SHRT, more than 15% of nodes reduce hops of the routing tree and the percentage of reduced hops is between 14% and 100%. In BRRT, more than 16% of nodes improve the path reliability of the routing tree and the percentage of the improved path reliability is between 2% to 50%.

A scalable information delivery services like data broadcasting scheme is definitely of great interest especially to deal with the exponential increase of mobile users. In this paper, we present Global Indexing with data placement scheme for multi broadcast channels environment, which aims to minimize query access time, tuning time and power consumption. This scheme considers index and data allocation over separate broadcast channel. Moreover, it concerns with single and multiple data items request. A simulation model is developed to analyze the performance of the proposed scheme. We compare the proposed scheme with conventional scheme. It is found that the proposed scheme provides substantially better performances in every aspect of evaluation.

Although wireless networks and mobile devices become popular these days, the diversity of mobile devices and unsteadiness of wireless networks still cause software development much trouble. Thus, when developing a mobile application, developers are forced to expose to these problems and to be familiar with these technologies and therefore it will spend a lot of time to write a mobile application. Furthermore, a mobile application often needs to be ported to different platform (for example from Java to .NET) which is also burdensome. In order to overcome these problems, the author proposes an adaptive framework to help developers build mobile application effortlessly and rapidly. The mobile application developed on this framework can run in different devices and operating system, so developers does not need to worry about portability. As a result, a mobile application developed on this framework can enjoy the benefit of “write once, run everywhere, and access any services.”

This study proposed a Context-Aware emergeNcy rEmedy system (CANE), based on the operations of a real hospital, to provide complete and convenient functions for emergency processes and medical consultants using mobile communication networks. The CANE system combines emergency medical services with GIS/GPS technology, mobile multimedia communications and context-aware controls. The CANE system largely focuses on allowing the EMT personnel to arrive at the accident location in the shortest possible time and give first aid the proposed dispatching procedure and the GPS/GIS location-aware service. When an ambulance is on the way to the specified hospital, the EMT can deliver the patient’s symptoms, including the data of the medical equipment and the audios/videos of the patient, to the hospital doctor via the personal communication network, e.g., GPRS. Based on real-time multimedia information, a physician can recommend to EMT the most suitable treatment for the patient on the way to the hospital.

This paper proposed and implemented a QoS-Aware MPEG-4 authoring tool with provision of content interaction control, which is named the Q4AT system. Q4AT provides friendly user interface in a WYSWYG manner for users to create their favorite MPEG-4 scenes. The characteristics of Q4AT are as follows. (i) The description of a scene is based on the standard BIFS language. (ii) The creation of the object description is based on the syntactic description language (SDL). (iii) All descriptions are VRML-based. A VRML-based system is compatible to different browsers and operation systems. Therefore, the author could simplify the steps of creating an MPEG-4 scene. (iv) Q4AT supports the functions of the quality of service by the proposed object priority differentiation control. Using Q4AT, authors are transparent to the MPEG-4 processing layers and are capable of concentrating on the editing function usage of the Q4AT. Q4AT makes it possible to easily create a complicated MPEG-4 scene and reduce the difficulty of MPEG-4 media creation and presentation.

Context-awareness is one of the most important technologies for the ubiquitous computing. To embed such a technology into applications, first of all, a well-defined architectural framework is required to support applications to obtain necessary contexts. Several studies have been proposed, but most of them overlooked one fundamental feature that contexts are subjective things and context-awareness is subjective behavior. Thus, providing pre-defined, pre-programmed operators which generate contexts by combining a couple of sensed data is very impractical. Instead, in this paper, we provide a well-defined programmable interface to applications, so that they can obtain and use contexts according to their own ideas. To evaluate our architecture and context interface, we implement all components comprising of the context infrastructure and perform several experiments. The results show the proposed method provides a flexible and expressive interface, but does not countervail the performance.

Perceived voice quality is mainly affected by IP network impairments such as delay, jitter and packet loss. Adaptive smoothing buffer at the receiving end can compensate for the effects of jitter based on a tradeoff between delay and loss to archive a best voice quality. This work formulates an online loss model which incorporates buffer sizes and applies the ITU-T E-model approach to optimize the delay-loss problem. Distinct from the other optimal smoothers, the proposed optimal smoother suitable for most of codecs carries the lowest complexity. Since the adaptive smoothing scheme introduces variable playback delays, the buffer re-synchronization between the capture and the playback becomes essential. This work also presents a buffer re-synchronization algorithm based on silence skipping to prevent unacceptable increase in the buffer preloading delay and even buffer overflow. Simulation experiments validate that the proposed adaptive smoother archives significant improvement in the voice quality.

This paper introduces a wearable computer as a wearable personal station. We propose and implement wristwatch-style wearable personal station and its I/O devices in this paper. Nowadays the progress in miniaturizing more powerful computer systems and the availability of various devices around wearable computing will bring this technology to the edge of a new quality. Wearable computing is starting to become a product by itself. The function components of our wristwatch-style wearable computer include watch, PDA functions such as PIMS, address book, portable multimedia features, personal communication features and so on. We miniaturized these functionalities into our wearable small device. We also handle a study of USB implementation without wires for human interfaces. This paper describes a platform, hardware specifications and applications we have developed.

This paper examines the perception of wearable computers for everyday life by the general public, in order to foster the adoption of this technology. We present a social study that focuses on sensors, actuators, autonomy, uses, and privacy. Carried out in 2005, it considers gender and cultural disparities in two dissimilar groups: French (115 males, 59 females) and Japanese (61 males, 54 females) citizens. Acknowledging that exposition to wearables can alter perception about them, we designed a garment-shaped prototype to check our results, estimate shifts of perception, and define guidelines for equipment and services. We describe our prototype, and future experiments dealing with face-to-face contacts, community awareness, and relaxing environments.

According to the improvements in wireless Internet technology, multimedia applications create new challenges, which must be solved. Internet-based videoconferencing systems have many variable factors, such as changes in the system operating environment or operating status of the hardware, according to the operator using the system. In this paper, we propose the Videoconferencing System, with multi-agents, for efficient videoconferencing, which is able to adapt itself to these various factors. This videoconferencing system has a dynamic architecture which is able to change the own architecture in runtime.

The purpose of this article is to describe a middleware framework for interfacing sensors and actuators, which provides abstract and useful contextual information to applications. The framework is divided into three layers with different abstraction levels, and an integration layer. The framework is evaluated, exemplified, and further described by practical implementations using the framework.

To resolve the syntax, structure and semantic heterogeneity for sharing information resources, the representative technologies are XML and Metadata. XML is used to represent the syntax and structure of information resources but the various XML schema definitions that have been developed by independent organizations without any standards or guidelines, make it difficult to share the semantic meaning of XML encoded information resources. In this paper, we propose a mechanism, named MSDL that represents the exact meaning of XML tags by describing the structural and semantic differences with standard metadata in metadata registries. MSDL overcomes the limitations of other approaches with respect to exactness, flexibility and standardization, and provides an environment for business partners using different metadata to share their XML encoded information resources.

In the current life, Internet is playing a key role in transferring diverse information. As the performance of Internet has been growing, transferred information has the form of multimedia streams such as video and audio. However, in current computing and internet environment, multimedia streaming services can’t be accomplished smoothly due to the various factors such as internet bandwidth, computing power and so on. In this paper, we are proposing an efficient system including hardware and software in terms of the design concept and system architecture for the multimedia streaming service. We also present the implementation result for the system.

Workflows used in business processes and distributed computing environments have supported service automation by connecting many tasks with rules and/or orderings. To adapt these workflows to ubiquitous computing, we must specify the context information on their transition conditions. In this paper, we propose uWDL, Ubiquitous Workflow Description Language, to specify context information on the transition constraints of a workflow in order to support adaptive services, and we designed a structural context model to express the context information in uWDL. Furthermore, uWDL is designed based on Web services, which are standardized and independent of various heterogeneous platforms, protocols, and languages. In order to verify the effectiveness of uWDL, we designed and implemented a scenario described with uWDL, and demonstrated that the uWDL system provides users with autonomic services in ubiquitous computing environments.

With rapid advancements in wireless devices, ubiquitous computing seems becoming a reality everyday. Active pervasive network infrastructure has been introduced to offer selective and intelligent information communications according to access bandwidths of end users’ devices. In this paper, research has been extended to deal with mixture of critical and non-critical information. Data classifications are devised for the infrastructure to interpret the importance of data accurately. The design relieves computation requirements at end devices, and mediates delivered information based on users’ personal preferences. Further, the operations of content adaptations are transparent to all end devices, and users always perceive high quality transactions and are satisfied with offered network services. More importantly, the resulting design further improves overall system throughput and delay performance.

There is a demand for efforts that deal with the challenges associated to the complex and time-consuming task of developing context-aware applications. These challenges include context modeling, reuse and reasoning, and software infrastructures intended to context management. This paper presents a service infrastructure for the management of semantic context called Semantic Context Kernel. The novelty is a set of semantic services that can be personalized according to context-aware applications’ requirements so as to support the prototyping of such applications. The Semantic Context Kernel has been built upon an ontological context model, which provides Semantic Web abstractions to foster context reuse and reasoning.

In recent years, principal component analysis (PCA) has attracted great attention in image compression. However, since the compressed image data include both the transformation matrix (the eigenvectors) and the transformed coefficients, PCA cannot produce the performance like DCT (Discrete Cosine Transform) in respect of compression ratio. In using DCT, we need only to preserve the coefficients after transformation, because the transformation matrix is universal in the sense that it can be used to compress all images. In this paper we consider to build a universal PCA by proposing a hybrid method called k-PCA. The basic idea is to construct k sets of eigenvectors for different image blocks with distinct characteristics using some training data. The k sets of eigenvectors are then used to compress all images. Vector quantization (VQ) is adopted here to split the training data space. Experimental results show that the proposed approach, although simple, is very efficient.

With diverse sensors, context-aware applications which aim at decreasing people’s attentions to computational devices are becoming more and more popular. But it is inadequate just with sensors because what applications really need is high-level context knowledge rather than low-level raw sensor data. So a software layer which delivers high quality contexts to applications with an easy application programming model is needed. In this paper, we establish a formal context model using semantic web languages and design a context fusion mechanism which not only generates high-level contexts by reasoning, but also brings in context lifecycle management and periodically time based conflict resolution to improve the quality of contexts. Using the context fusion mechanism, a programmable and service oriented middleware is built upon OSGi framework to support context-aware applications. Also, we propose an application programming model using RDQL as context query language and demonstrate an application called Seminar Assistant. According to the experiment results, we believe our prototype system is useful for non-real-time applications in various domains.

A large range of devices (from PDA to high-end TV) can receive and decode digital video. However, the capacity of one device is very different from the capacity of another device. This paper discusses how the same video but differently encoded can be efficiently distributed to a set of receiving devices. The key technology is scalable video coding. The paper shows how a framework assists in adapting the digital code to the changing transmission conditions to optimize the quality rendered at the different devices. The paper concludes with a validation based on a real-time streaming application.

As images are commonly transmitted or stored in compressed form such as JPEG lossy compression, image authentication demands techniques that can distinguish incidental modifications (e.g., compression) from malicious ones. In this paper, we propose an effective technique for image authentication which can prevent malicious manipulations but allow JPEG compression. An image is divided into blocks in the spatial domain, each block is divided into two parts by randomly selecting pixels, and average gray values for the parts are calculated. The average value is compared with that of the adjoining block to obtain an authentication signature. The extracted authentication information becomes the fragile watermark to be inserted into the image’s frequency domain DCT block. The experimental results show that this is an effective technique of image authentication.

To accomplish developing mobile web applications on variety of mobile execution environments, we propose Pervasive User interface Markup Language (PUML) describing user interfaces for applications on the small devices, and Pervasive loGic Markup Language (PGML) representing the computational logic of the applications. Furthermore, we exploit the XSLT/XPath transformation mechanism to transform documents of PUML/PGML into the target languages, and evaluate them by implementing toolkit and runtime service applications. In Brief, our paper contributes an XML-based application model to assist mobile application developers.

We analyze the problem of storing contextual information across a set of distributed heterogeneous mobile devices. These devices form a Mobile Ad Hoc Network (MANET) interconnected to Internet, in which partitions may eventually happen due to mobility. We present a new mechanism called Contextual Hash Table (CHT), which uses the semantic of the contextual information to select which nodes will store that information. Unlike previous general-purpose data replication algoritms, CHT manages to store information in the area of the network in which that information is most likely needed by neighboring nodes.

We propose an efficient scheme called CoReS (Configuration and Registration Scheme) that integrates address assignment and service location for ad hoc networks prevalent in pervasive computing environments. CoReS exploits node heterogeneity such that more capable and stable nodes serve others. CoReS allocates addresses to individual nodes locally, but employs global allocation states to handle network merge situations. In addition, CoReS exploits the positive features of distributed directory services to perform service location in a centralized manner resulting in minimal communication overheads. We analyze the characteristics of CoReS architecture, evaluate its performance and compare with other schemes. Through the evaluation and comparison, we demonstrate that the integrated CoReS system exhibits high efficiency and cross-layer optimization.

The introduction of pervasive computing environments in everyday life will not just be a big step for users, but also for application designers. The well defined interaction interfaces will make place for other, more intuitive ways of interaction. It is the challenge for a pervasive system middleware to capture and model the user intention in a smart way and to solve ambiguousness in the user’s expression of a pervasive action. This paper introduces the Pervasive Service Action Query Language (PsaQL), a language to formalize the description of a user intention using composed pervasive services. The work describes a way of translating the user intention into an executable action and propose algorithms performing this translation. Considerations to implement this process are given within the scope of

PerSE

, a pervasive service environment developed by our research group, together with general evaluation metrics for such algorithms.

Many sensors providing situation data will be in everywhere under the ubiquitous environment. It requires the current RFID system should be extended to recognize and use situation information from the sensors. We already proposed a new RFID system architecture that is suitable for the coming ubiquitous environment, and basically consists of the key components such as the inference engine, use policy, and definition language. It has four alternatives (types) depending on the role distributions to the components. This paper shows the performance evaluations of the alternatives. Using the research results, we can select a proper RFID system architecture for corresponding ubiquitous application. The contributions of this paper are as follow: providing a new RFID system architecture to recognize, analyze, and utilize the situation information; defining the four alternatives for ubiquitous applications.

MPEG-4 supports object-based interactive multimedia applications. To compose complex multimedia scene, MPEG-4 supports BIFS and XMT as scene description. For interoperability of the MPEG-4 content and object-based rendering information management, this paper proposes the content analyzer that supports multiple scene description. In order to improve content management’s efficiency, the content analyzer provides module optimization from scene description’s parsing to scene information management. This analyzer supports exact analysis of the scene description and object-based core information management. And it can be applied to XML-based heterogeneous players.

Perceived voice quality is a key metric in VoIP applications. The quality is mainly affected by IP network impairments such as delay, jitter and packet loss. Playout buffer at the receiving end can be used to compensate for the effects of jitter based on a tradeoff between delay and loss. Adaptive smoothing algorithms are capable of adjusting dynamically the smoothing time based on the network parameters to improve voice quality. In this article, we introduce an efficient and easy perceived quality method for buffer optimization to archive the best voice quality. This work formulates an online loss model which incorporates buffer sizes and applies the Lagrange multiplier approach to optimize the delay-loss problem. Distinct from the other optimal smoothers, the proposed optimal smoother is suitable for any codec and carries the lowest complexity. Simulation experiments validate that the proposed adaptive smoother archives significant improvement in the voice quality.

Ubiquitous computing is targeted at services and applications of computer and communication technologies in the real world. This research, as a part of UbicKids Project, is focused on designing a context-aware system that dynamically detects the possible dangerous situations in the routes where kids go to and return from schools, and provides prompt advices to kids who may encounter some dangerous situations. Based on analyses of typical dangerous situations in school routes, the paper then shows the system architecture and discusses about danger-related context information processing including context description, representation and presentation. Security and privacy issues and possible solutions are also explained. A preliminary system prototype has been implemented and some GUIs are explained. Related work is discussed with comparisons to other research work.

The study of human-computer interaction is now the most popular research domain overall computer science and psychology science. The most of essential issues recently focus on not only the information about the physical computing but also the affective computing. The emotion states of human being can dramatically affect their actions. It is important for a computer to understand what the people feel at the time. In this paper, we propose a novel method to predict the future emotion state of person depending on the current emotion state and affective factors by an advanced mental state transition network [1]. The psychological experiment with about 100 participants has been done to obtain the structure and the coefficients of the model. The test experiment also has been done to certificate the prediction validity of this model.

We have been developing a microdisplay based on the field emission display (FED) technology, which is advantageous in power consumption, image quality and long term stability. We have adopted LSI-driven anode pixels, which enables active-matrix addressing and, therefore, highly precise and high-quality microdisplay. The structure was optimized according to the simulation study of electric field and electron trajectories. The driver LSI has been designed, evaluated by simulation, and the wafers have been produced. Anti-crosstalk grid should be constructed on the LSI by photolithography and the relevant study has been performed.

The use of the Internet raises serious behavioural issues regarding, for example, security and the interaction among agents that may travel across links. Model-building such interactive systems is one of the biggest current challenges in computer science. A general model, action calculi, has been introduced by Robin Milner to unify the various emerging disciplines of interactive behaviour. In this paper action calculi is used as an abstraction of interactive systems and information flow security properties of such systems are studied. At first an information flow analysis for static action calculi is presented to predict how data will flow both along and inside actions and its correctness is proved; Next basing on the result of the analysis information security properties of both static and dynamic action calculi are discussed; Finally a general relationship are established between the static notation of information flow security and the dynamic one.

Due to the difficulty on exact measurement and expression of NGI (Next-Generation Internet) network status, the necessary QoS routing information is fuzzy. With the gradual commercialization of network operation, paying for network usage calls for QoS pricing and accounting. In this paper, a microeconomics-based fuzzy QoS unicast routing scheme is proposed, consisting of three phases: edge evaluation, game analysis, and route selection. It attempts to make both network provider and user utilities maximized along the found route, with not only the user QoS requirements satisfied but also the Pareto-optimum under the Nash equilibrium on their utilities achieved.

This paper describes the basic concepts of point-to-multipoint (p2mp) path computation on the basis of the Path Computation Element Metric Protocol (PCEMP). PCEMP, being soft-memory based, has the capability of dynamic configuration of its finite state machines (FSMs) in the participating PCEMP peers, and thus can support a wide variety of traffic engineering techniques that are needed to guarantee bandwidth demand and scalable fast protection and restoration in PCE based p2mp frameworks ensuring end-to-end QoS support. The authors have proposed this concept in the newly constituted PCE WG (Path Computation Element Work Group) in the RTG sub-area of the IETF. In this research-in-progress paper, we show how PCEMP as it is defined, and the optimal number of PCE Domain Areas (PCEDAs) that might be allocated to a PCE node for the best performance in end-to-end QoS management based on a tight optimal Cramer Rao bound for the state machine executions.

Lightweight real-time network communication is crucial for commodity cluster systems and embedded control systems. This paper introduces the design, implementation and evaluation of SS-RTUDP, a novel zero-copy data path based real-time communication protocol with efficient communication resources management. To avoid unpredictable overheads during SS-RTUDP packets transmission, all communication resources are pre-allocated. A feasible fragmentation mechanism is also proposed for transmitting SS-RTUDP packets larger than the network

MTU

. On the other hand, the additional real-time traffic smoother provides high priorities to SS-RTUDP packets and also smoothes peak packets arrival curve. The prototype of SS-RTUDP is implemented under Linux systems and performance evaluations over Fast/Gigabit Ethernet are provided. The measurement results prove that SS-RTUDP can provide not only much lower latency and higher communication bandwidth than traditional UDP protocol, but also good real-time network communication performance for commodity cluster systems.

In this article we describe a system based on a 32-bit processor, Leon, complete with security features offered by a specific cryptographic AES IP. Hardening is done not only on the principal hardware components but on the operating system as well, with attention for possible interaction between the different levels. The cryptographic IP is protected too to offer good resistance against, for example, fault-based attacks.

We have presented an optimal algorithm for minimal cost loop problem (MCLP), which consists of finding a set of minimum cost loops rooted at a source node. In the MCLP, the objective function is to minimize the total link cost. The proposed algorithm is composed of two phases: in the first phase, it generates feasible paths to satisfy the traffic capacity constraint, and finds the exact solution through matching in the second phase. In addition, we have derived several properties of the proposed algorithm. Performance evaluation shows that the proposed algorithm has good efficiency for small network with light traffic. Our proposed algorithm can be applied to find multicast loops for real-time multimedia traffic distribution.

In this paper, we present a fast and precise method for fingerprint classification. The proposed method directly extracts the directional information from the thinned image of the fingerprint. We use an octagon mask to search the center point of the region of interest and consider both the direction information and the singular points in the region of interest to classify the fingerprints. In the system, not only is the amount of computation reduced but also can the extracted information be used for identification on AFIS. The system has been tested on the NIST special fingerprint database 4. For the 4000 images in this database, 2000 images are randomly chosen by computer and classified. The classification accuracy reaches 93.1% with no rejection for 4-class classification problem.

Ensuring anonymity in sensor networks is a major security goal. Using traffic analysis, the attacker can compromise the network functionality by correlating data flow patterns to event locations/active areas. In this paper we present a novel hierarchical anonymous communication protocol that hides the location of nodes and obscure the correlation between event zones and data flow from snooping adversaries. We quantify the anonymity strength of our protocol by introducing a new anonymity metric: Degree of Exposure Index. Our protocol is designed to offer flexible tradeoffs between degree of anonymity and communication-delay overhead.

The performance of network protocols on different usage scenarios differs significantly, making the protocol choice a difficult question. This had motivated a work that aims to evaluate the TCP, UDP and Sendfile (a POSIX-defined zero-copy TCP access technique) protocols on LAN, MAN and WAN environments, in order to find the most adequate configuration for each protocol. The protocols were evaluated on default configurations, without any application-specific optimizations.

The use of

SVM

(Support Vector Machines) in detecting e-mail as spam or nonspam by incorporating feature selection using GA (Genetic Algorithm) is investigated. An GA approach is adopted to select features that are most favorable to

SVM

classifier, which is named as GA-SVM. Scaling factor is exploited to measure the relevant coefficients of feature to the classification task and is estimated by GA. Heavy-bias operator is introduced in GA to promote sparse in the scaling factors of features. So, feature selection is performed by eliminating irrelevant features whose scaling factor is zero. The experiment results on UCI Spam database show that comparing with original

SVM

classifier, the number of support vector decreases while better classification results are achieved based on GA-SVM.

With the increasing prevalence of ubiquitous computing, the software component allocation while meeting various resources constraints and component interdependence is crucial, which poses many kinds of challenges. This paper mainly presents an adaptive component allocation algorithm in ScudWare middleware for ubiquitous computing, which uses dynamic programming and forward checking methods. We have applied this algorithm to a mobile music space program and made many experiments to test its performance. The contribution of our work is twofold. First, our algorithm considers resources constraints requirement, component interdependence, and component tolerant issues. Second, we put forward a component interdependence graph to describe interdependent relationships between components. As a result, the evaluation of component allocations has showed our method is applicable and scalable.

Our approach towards context awareness is to retrieve contextual information by augmenting our daily life objects (like a chair, a mirror etc.) with sensing capabilities. We call such artefacts

sentient artefacts

. To avoid developing dedicated context-aware application integrating these artefacts, there is a need for a generic computing platform that can assist application programmers to develop and deploy applications easily and rapidly. We present a framework titled “Prottoy” for context-aware applications. The framework provides a generic interface for interacting with sentient artefacts in a unified way, regardless of their type and properties. As a result, application development is simple, rapid and independent from the underlying environments. This paper describes the design and implementation of Prottoy.

Advanced analysis of data for extracting useful knowledge is the next natural step in the world of ubiquitous computing. So far, most of the ubiquitous systems process knowledge in problem-specific or domain-specific manners. This article introduces the concept of context knowledge discovery process, and presents a middleware architecture which eases the task of ubiquitous computing developers, while supporting data mining and machine learning techniques. We show how the middleware architecture supports building ubiquitous systems which are able to “learn” and “think” by introducing some learning – reasoning combination mechanisms, such as the context recognition and prediction, or the deductive rule learning and reasoning process.

A dramatic increase of event monitoring capabilities by wireless sensors requires new, more sophisticated, event correlation over time and space. This new paradigm implies composition of events in ubiquitous computing environments and event Correlation will be a multi-step operation from event sources to final subscribers, combining information collected by wireless devices into higher level information or knowledge. We define generic composite event semantics, which extend traditional event composition with data aggregation in wireless sensor networks (WSNs). This work bridges data aggregation in WSNs with event correlation services over distributed systems. We use interval-based semantics for event detection, defining precisely complex timing constraints.