WiFi offloading, where mobile device users (e.g., smart phone users) transmit packets through WiFi networks rather than cellular networks, is a promising solution to alleviating the heavy traffic burden of cellular networks due to data explosion. However, since WiFi networks are intermittently available, a mobile device user in WiFi offloading usually needs to wait for WiFi connection and thus experiences longer delay of packet transmission. To motivate users to participate in WiFi offloading, cellular network operators give incentives (rewards like coupons, e-coins) to users who wait for WiFi connection and transmit packets through WiFi networks. In this paper, we aim at maximizing users' rewards while meeting constraints on queue stability and energy consumption. However, we face scheduling challenges from random packet arrivals, intermittent WiFi connection and time varying wireless link states. To address these challenges, we first formulate the problem as a stochastic optimization problem. We then propose an optimal scheduling policy, named Optimal scheduling Policy under Energy Constraint (OPEC), which makes online decisions as to when to delay packet transmission to wait for WiFi connection and which wireless link (WiFi link or cellular link) to transmit packets on. OPEC automatically adapts to random packet arrivals and time varying wireless link states, not requiring a priori knowledge of packet arrival and wireless link probabilities. As verified by simulations, OPEC scheduling policy can achieve the maximum rewards while keeping queue stable and meeting energy consumption constraint.

In this paper, we propose an online scheduling system for tours by one-way electric vehicle (EV) sharing. The system takes reservations of tours with their multiple destinations, time windows and stay time for visiting each destination. It then tells the user the sequence and scheduling of visits to each destination, and which specific EVs to take. The system tells the user to change to another EV when the battery runs out. This enables users to move long distances without concerns about remaining battery. The system also calculates a schedule for moving the EVs to rebalance their distribution. In order to verify the effectiveness of our system, we evaluated it with simulations with 500 to 700 users. Our results showed that the proposed system improved the acceptance rate of reservations while reducing the relocation count(the number of EVs to be moved rebalance the distribution) by up to 15%.

A payment system in a disaster area is essential for people to buy necessities such as groceries, clothing, and medical supplies. However, existing payment systems require the needed communication infrastructures (like wired networks and cellular networks) to enable transactions, so that these systems cannot be relied on in disaster areas, where these communication infrastructures may be destroyed. In this paper, we propose a mobile payment system, adopting infrastructure less mobile adhoc networks (MANETs), which allow users to shop in disaster areas while providing secure transactions. Specifically, we propose an endorsement-based scheme to guarantee each transaction and a scheme to provide monitoring based on location information, and thus achieve transaction validity and reliability. Our mobile payment system can also prevent collusion between two parties and reset and recover attacks by any user. Security is ensured by using location-based mutual monitoring by nearby users, avoiding thereby double spending in the system.

In this paper, we propose a task scheduling algorithm for a multicore processor system which reduces the recovery time in case of a single fail-stop failure of a multicore processor. Many of the recently developed processors have multiple cores on a single die, so that one failure of a computing node results in failure of many processors. In the case of a failure of a multicore processor, all tasks which have been executed on the failed multicore processor have to be recovered at once. The proposed algorithm is based on an existing check pointing technique, and we assume that the state is saved when nodes send results to the next node. If a series of computations that depends on former results is executed on a single die, we need to execute all parts of the series of computations again in the case of failure of the processor. The proposed scheduling algorithm tries not to concentrate tasks to processors on a die. We designed our algorithm as a parallel algorithm that achieves O(n) speedup where n is the number of processors. We evaluated our method using simulations and experiments with four PCs. We compared our method with existing scheduling method, and in the simulation, the execution time including recovery time in the case of a node failure is reduced by up to 50% while the overhead in the case of no failure was a few percent in typical scenarios.

Finding a vacant parking space in a large crowded parking facility takes long time. In this paper, we propose a navigation method that minimizes the parking time based on collected real-time positional information of cars. In the proposed method, a central server in the parking facility collects the information and estimates the occupancy of each parking zone. Then, the server broadcasts the occupancy data to the cars in the parking facility. Each car then computes a parking route with the shortest expected parking waiting time and shows it to the driver. We conducted simulation-based evaluations of the proposed method using a realistic model based on trace data taken from a real parking facility. We confirmed that the proposed method reduced parking waiting time by 20%-70% even with low system penetration.

When disasters occur, a common characteristic is the partial or complete failure of the telecommunications infrastructure so the usual means of communication are often not available. However, accurate and timely information of the disaster area is important. In this paper, a data collection method from an area of interest (AoI) within the disaster zone is proposed that uses the mobile phones of the people to serve as sensing nodes. To achieve maximum AoI coverage while minimizing delay, we propose a DTN-based data aggregation method. Mobile phone users create messages containing disaster-related information and merge them with their respective coverage areas into a new message with the merged coverage to reduce message size and to minimize the overall message collection delay. However, simply merging messages may result in duplicate counting thus, to prevent this, a Bloom filter is constructed for each aggregated message. Also, to reduce further the message delivery time, the expected time of a node to reach its destination is introduced as a routing metric. Through computer simulation with a real geographical map, we confirmed that the proposed method achieved a smaller delay in message delivery than epidemic routing.

In this paper, aiming to reduce cellular network load, we propose a cooperative download method by which user terminals exchange fragments of a content called chunks through short-range wireless communication like Bluetooth or Wi-Fi with other user terminals who want the same content. In order to reduce the cellular network load, it is necessary to receive as many chunks as possible via short-range wireless communication. Our basic idea is to predict contact time when other user terminals get within a range of short-range wireless communication and to obtain chunks efficiently from other user terminals. To predict the contact time, each terminal periodically registers information of its location and retaining and requiring chunks with a server in the fixed network. The server calculates for each terminal the probability and time to contact other terminals so that the terminal can determine its communication schedule with those meeting terminals to obtain chunks efficiently. Through computer simulations with measured energy consumption parameters, we confirmed that terminals using our method obtained from other terminals 50% more chunks with 20 % less energy consumption than the method of greedily collecting chunks by always turning on the wireless device.

In this paper, we tackle the problem to achieve k-coverage of a target indoor space with obstacles, that is, any point in the target monitoring area has a line-of-sight to and is located in the sensing range rsof at least k sensors. We propose heuristic algorithms for computing a deployment pattern achieving the k-coverage in an arbitrary 3D target space with stationary and mobile obstacles, while minimizing the overall deployment cost. For the case with only stationary obstacles, we propose a greedy algorithm that puts sensor nodes one by one on a grid point of the deployable area in the descending order of the cost-performance value (i.e., how many monitoring points are covered by putting a sensor at the deployment point per unit deployment cost). In order to extend the algorithm for the case with a mobile obstacle, we define mobile k-coverage that guarantees k-coverage of a target space for arbitrary position of a mobile obstacle, then provide a sufficient condition for the mobile k-coverage: the half-sphere of radius rscentered at a monitoring point bounded by the vertical plane containing the point includes at least k sensor nodes. Based on this condition, we propose a heuristic algorithm that puts at least one sensor node in each π over k+1 spherical wedge for each monitoring point. With the proposed algorithms, we have computed the sensor nodes position in an existing indoor environment and confirmed that the obtained WSN deployment in the real space accurately achieves k-coverage.

Aiming to achieve sensing coverage for a given Area of Interest (AoI) in a People-Centric Sensing (PCS) manner, we propose a concept of (α, T)-coverage of the target field where each point in the field is sensed by at least one node with probability of at least α during the time period T. Our goal is to achieve (α, T)-coverage by a minimal set of mobile sensor nodes for a given AoI, coverage ratio α, and time period T. We model pedestrians as mobile sensor nodes moving according to a discrete Markov chain. Based on this model, we propose two algorithms: the inter-location and inter-meeting-time algorithms, to meet a coverage ratio α in time period T. These algorithms estimate the expected coverage of the specified AoI for a set of selected nodes. The inter-location algorithm selects a minimal number of mobile sensor nodes from nodes inside the AoI taking into account the distance between them. The inter-meeting-time selects nodes taking into account the expected meeting time between the nodes. We conducted a simulation study to evaluate the performance of the proposed algorithms for various parameter setting including a realistic scenario on a specific city map. The simulation results show that our algorithms achieve (α, T)-coverage with good accuracy for various values of α, T, and AoI size.

In this paper, we propose a method for improving the playback quality of one segment terrestrial television broadcasting (called 1seg, hereafter) at mobile terminals staying in a weak 1seg radio reception area (called WRA terminals) by wireless multi-hop video streaming from terminals in strong 1seg radio area (called SRA terminals). First, we formulate the problem to derive the set of video forwarding paths that maximize the number of WRA terminals to be “relieved” by receiving the forwarded video, under the constraints on the wireless bandwidth and the maximum number of hops. Since this problem is NP-hard and deriving the optimal solution in real-time is infeasible, we propose a greedy algorithm that each WRA terminal find a video forwarding path from a SRA terminal receiving the required 1seg channel based on the information periodically exchanged among neighboring terminals. In order to increase the number of relieved terminals, we introduce a technique to let a SRA terminal change its watching 1seg channel, forward the video to a WRA terminal, and ask for the relief for itself. Through computer simulations, we confirme that the proposed algorithm with 2-hop relief paths improved the video playback quality in more than 60% of the total WRA staying time.

For accident prevention at intersections, it is useful for drivers to grasp the position of vehicles in blind spots. This can be achieved without infrastructure if some vehicles passing near the intersection capture and share live video of the intersection through inter-vehicle communications. However, such video streaming requires a congestion control mechanism. In this paper, aiming to let a driver grasp the situation at an intersection, we propose a method to select vehicles that send a video in order to generate a live bird's-eye-view video of the intersection. In our method, each vehicle at an intersection exchanges information with others, such as the sub-areas of the intersection it captures, the quality of its video, and its position and speed. Based on the exchanged information, each vehicle autonomously judges whether it should send its video or not. Through simulation with a QualNet simulator, we confirm that our method achieves a good video arrival rate and video quality sufficient for practical use.

In vehicular ad hoc networks (VANETs), delivering messages to a specific location is difficult due to the high mobility of vehicles. In this paper, we propose a method for efficient message delivery in VANETs utilizing the route information in car navigation systems. In the proposed method, each car periodically exchanges the information on its current position and scheduled route in the car navigation system with neighboring cars within radio range. By referring to the exchanged information, each car forwards messages to the neighboring car that will most closely approach the destination. Through simulations, we confirm that the proposed method achieves a better delivery rate with low bandwidth usage than a geocast-based method and epidemic routing.

In this paper, we propose a framework named ``UbiREMOTE'' for controlling information appliances connected to a home network with a unified and intuitive user interface from a remote place.The UbiREMOTE framework provides users with a way to control appliances in a home through a virtual space drawn on a mobile terminal screen which reflects the latest conditions of the real appliances and the rooms in the home. With UbiREMOTE, a user controls appliances by (1) moving to the front of an appliance, (2) choosing the appliance to control and (3) pushing buttons on the virtual remote controller which imitates the real remote controller for the appliance or the real console.In this paper, we propose a method to improve the drawing speed of 3D virtual space on mobile terminals and a method for automatically reflecting condition changes of the real space in the virtual space.We implemented the methods and evaluated the performance. The results showed that the proposed methods can be practically used on small mobile terminals.

In this paper, we propose a method for video ads dissemination through a hybrid network consisting of WiFi and cellular networks, in order to provide timely delivery of video ads with preferred content to users according to the users' contexts. In recent years, video download/streaming services for cellular phones have already become popular. Among various video delivery services, a service for disseminating video ads according to the users' contexts is expected to achieve high advertising effects. However, context-aware video ads dissemination will consume large bandwidth since the size of video ad is rather large and the same ad is required at different time from various users. We propose a new video ads dissemination method for mobile terminals which utilizes both WiFi and cellular networks. In the proposed method, a file of video ad is divided into pieces and each node exchanges the pieces with neighbor nodes using WiFi ad hoc communication so that the usage of cellular network is reduced. In order to make the method works effectively for a large number of nodes, we propose an algorithm where mobile nodes autonomously and probabilistically decide their actions without a central control. Through simulations, we confirmed that our method reduces cellular network usage by about 93% compared with a case that all nodes download video ads via cellular network, and works effectively in cases with a large number of nodes and high mobility.

Mobile ad hoc networks (MANETs) can be used to provide mobile users temporary infrastructure to use services such as database retrieval service when traditional infrastructure-based networks are unavailable in infrastructure-less situations (e.g. after a destructive disaster like an earthquake). The challenging task in such dynamic environments is how we can improve the service availability. An effective strategy is replicating a service at some nodes distributed across the network. However, service replication can considerably impact the system energy consumption. Since mobile devices have a limited amount of battery, a dynamic and efficient service replication is necessary to support such environments. In this paper, we propose a distributed service replication scheme for achieving high service availability with reasonable energy consumption for MANETs. The proposed method called distributed adaptive service replication (DAR) divides the whole network into disjoint zones of at most 2-hops in diameter and builds a dynamic replication mechanism which puts replicas only in zones with high service demand. Through simulations, we have confirmed that our approach can achieve higher service availability and lower energy consumption than an existing method.

One of the important issues in wireless sensor network (WSN) is to k-cover the target sensing field and to extend its lifetime. We propose a method to k-cover the field and maximize the WSN lifetime by moving mobile sensor nodes to appropriate positions for a WSN consisting of both static and mobile sensor nodes which periodically collect environmental information. Our target problem is NP-hard. So, we propose a genetic algorithm (GA) based scheme to find a near optimal solution in practical time. In order to speed up the calculation, we devised a method to check a sufficient condition of k-coverage of the field. For the problem that nodes near the sink node have to forward the data from farther nodes, we make a tree where the amount of communication traffic is balanced among all nodes, and add this tree to the initial candidate solutions of our GAbased algorithm. Through computer simulations, we confirmed that our method achieves much longer k-coverage lifetime than conventional methods for 100 to 300 node WSNs.

In this paper, we propose a framework which allows remote users to form conversation groups based on spatial relationship in a shared virtual space. Our proposed framework can transport awareness information of real world by capturing and transferring user's audio visual information. Our framework also provides functions useful to CSCW, which allow each user to simultaneously join different conversation groups, and communicate with others asynchronously exchanging awareness information. We show a reference implementation architecture to realize the framework in an ordinary computing and networking environment.

This paper presents a cost-efficient video multicast method for live video streaming to heterogeneous mobile terminals over a content delivery network (CDN), where CDN consists of a video server, several proxies with wireless access points, and overlay links among the server and proxies. In this method, the original video sent from the server is converted into multiple versions with various qualities by letting proxies execute transcoding services based on the users' requirements, and delivered to mobile terminals along video delivery paths. To suppress the required computation and transfer costs in CDN, we propose an algorithm to calculate cost-efficient video delivery paths which minimizes the sum of the computation cost for proxies and the transfer cost on overlay links. Our basic idea for deriving cost-efficient delivery paths is to place transcoding service on different proxies in load-balancing manner, and to construct a minimal Sterner tree from all transcoding points of requested qualities. The overall goal of the placement is the balance between computation and transfer cost. Through simulations, we show that our algorithm can calculate more cost-efficient video delivery paths and achieve lower request rejections than other algorithms.

We have proposed FAIRVIEW, a framework for realizing 3D graphics-based interaction between mobile users in real world and remote network users. In order to realize FAIRVIEW in an ordinary wireless LAN and Internet environment, a QoS adaptation mechanism is essential. The QoS adaptation mechanism of FAIRVIEW regulates, for each user, update frequency of his/her observable objects depending on the importance values associated with regions of his/her sight within available bandwidth. In this demonstration, we show how our QoS adaptation mechanism changes the quality of each observable object as the user moves his/her sight.

In this paper, we propose a method which efficiently collects, retains and propagates traffic information using inter- vehicle communication with "message ferrying" technique used in vehicular ad hoc network (VANET). In the proposed method, we use buses as message ferries which travel along regular routes. In order to improve information propagation efficiency in low- density areas, buses collect as much traffic information as possible from cars in their proximity, and periodically disseminate the collected information to neighboring cars. We have implemented the proposed system on the traffic simulator NETSTREAM and compared information propagation efficiency between our proposed method and a method which uses inter-vehicle communication among only ordinary cars. In the simulation, the proposed method improved the efficiency up to 50%.

In this paper, we propose a new method to construct a semi-optimal QoS-aware multicast tree on MANET using distributed computation of the tree based on genetic algorithm (GA). This tree is sub-optimal for a given objective (e.g., communication stability and power consumption), and satisfies given QoS constraints for bandwidth and delay. In order to increase scalability, our proposed method first divides the whole MANET to multiple clusters, and computes a tree for each cluster and a tree connecting all clusters. Each tree is computed by GA in some nodes selected in the corresponding cluster. Through experiments using network simulator, we confirmed that our method outperforms existing on-demand multicast routing protocol in some useful objectives.

Multi-objective genetic algorithms (MOGAs) are approximation techniques to solve multi-objective optimization problems. Since MOGAs search a wide variety of pareto optimal solutions at the same time, MOGAs require large computation power. In order to solve practical sizes of the multi objective optimization problems, it is desirable to design and develop a hardware implementation method for MOGAs with high search efficiency and calculation speed. In this paper, we propose a new method to easily implement MOGAs as high performance hardware circuits. In the proposed method, we adopt simple Minimal Generation Gap (MGG) model as the generation model, because it is easy to be pipelined. In order to preserve diversity of individuals, we need a special selection mechanism such as the niching method which takes large computation time to repeatedly compare superiority among all individuals in the population. In the proposed method, we developed a new selection mechanism which greatly reduces the number of comparisons among individuals, keeping diversity of individuals. Our method also includes a parallel execution architecture based on Island GA which is scalable to the number of concurrent pipelines and effective to keep diversity of individuals. We applied our method to multi-objective Knapsack Problem. As a result, we confirmed that our method has higher search efficiency than existing method.

In this paper, the authors propose a technique to flexibly implement genetic algorithms (GAs) for various problems on FPGAs. For the purpose, the authors propose a common architecture for GA. The proposed architecture allows designers to easily implement a GA as a hardware circuit consisting of parallel pipelines which execute GA operations. The proposed architecture is scalable to increase the number of parallel pipelines. The architecture is applicable to various problems and allows designers to estimate the size of resulting circuits. The authors give a model for predicting the size of resulting circuits from given parameters. Based on the proposed method, the authors have implemented a tool to facilitate GA circuit design and development. Through experiments using knapsack problem and traveling salesman problem (TSP), the authors show that the FPGA circuits synthesized based on the proposed method run much faster and consume much lower power than software implementation on a PC and the model can predict the size of the resulting circuit accurately enough

Genetic algorithms (GAs) are useful since they can find near optimal solutions for combinatorial optimization problems quickly. Although there are many mobile/home applications of GAs such as navigation systems, QoS routing and video encoding systems, it was difficult to apply GAs to those applications due to low computational power of mobile/home appliances. In this paper, we propose a technique to flexibly implement genetic algorithms for various problems on FPGAs. For the purpose, we propose a basic architecture which consists of several modules for GA operations to compose a GA pipeline, and a parallel architecture consisting of multiple concurrent pipelines. The proposed architectures are simple enough to be implemented on FPGAs, applicable to various problems, and easy to estimate the size of the resulting circuit. We also propose a model for predicting the size of resulting circuit from given parameters consisting of the problem size, the number of concurrent pipelines and the number of candidate solutions for GA. Based on the proposed method, we have implemented a tool to facilitate GA circuit design and development. This tool allows designers to find appropriate parameter values so that the resulting circuit can be accommodated in the target FPGA device, and to automatically obtain RTL VHDL description. Through experiments using Knapsack Problem and TSP, we show that the FPGA circuits synthesized based on the proposed method run much faster and consume much lower power than software implementation on a PC and that our model can predict the size of the resulting circuit accurately enough.

In urban areas including shopping malls and stations with many people, it is important to utilize various information which those people have obtained. In this paper, we propose a method for information registration and retrieval in MANET which achieves small communication cost and short response time. In our method, we divide the whole application field into multiple sub-areas and classify records into several categories so that mobile terminals in an area holds records with a category. Each area is associated with a category so that the number of queries for the category becomes the largest in the area. Thus, mobile users search records with a certain category by sending a query to nodes in the particular area using existing protocol such as LBM (Location-Based Multicast). Through simulations supposing actual urban area near Osaka station, we have confirmed that our method achieves practical communication cost and performance for information retrieval in MANET.

In this demonstration, we present cellular phone applications developed on top of our middleware, and show the usefulness of the proposed group formation mechanism based on user’s context and group communication. Our middleware allows application programmers to efficiently develop cooperative applications consisting of a large number of cell phone terminals. To cope with several restrictions of cellular phones, our middleware allows application software to be executed separately on a server and user terminals. Group communication is implemented as interprocess communication on the server, and only the userinterface parts are executed on the cellular phones.

In this paper, we propose a method to realize traffic information sharing among cars using inter-vehicle communication. When traffic information on a target area is retained by ordinary cars near the area, the information may be lost when the density of cars becomes low. In our method, we use the message ferrying technique together with the neighboring broadcast to mitigate this problem. We use buses which travel through regular routes as ferries. We let buses maintain the traffic information statistics in each area received from its neighboring cars. We implemented the proposed system, and conducted performance evaluation using traffic simulator NETSTREAM. As a result, we have confirmed that the proposed method can achieve better performance than using only neighboring broadcast.

In this demonstration, we show an energy-aware video streaming system which allows users to play back video for the specified duration within the remaining battery amount. In the system, we execute a proxy server on an intermediate node in the network. It receives the video stream from a content server, transcodes it to the videos with appropriate quality, and forwards it to a PDA or a laptop PC. Here, suitable parameter values of the video (such as picture size, frame rate and bitrate) which enable playback for the specified duration are automatically calculated on the proxy using our battery consumption model. The system also allows users to play back video segments with different qualities based on the importance specified to each video segment.

In this paper, we propose a method for cars to autonomously and cooperatively collect traffic jam statistics to estimate arrival time to destination for each car using inter-vehicle communication. In the method, the target geographical region is divided into areas, and each car measures time to pass through each area. Traffic information is collected by exchanging information between cars using inter-vehicle communication. In order to improve accuracy of estimation, we introduce several mechanisms to avoid same data to be repeatedly counted. Since wireless bandwidth usable for exchanging statistics information is limited, the proposed method includes a mechanism to categorize data, and send important data prior to other data. In order to evaluate effectiveness of the proposed method, we implemented the method on a traffic simulator NETSTREAM developed by Toyota Central R&D Labs conducted some experiments and confirmed that the method achieves practical performance in sharing traffic jam information using inter-vehicle communication

In order to allow every user to extract aggregated computational power from idle PCs in the Internet, we propose a distributed architecture to achieve a market based resource sharing among users. The advantages of our proposed architecture are the following: (i) aggregated resources can be bought by one order; (ii) resource prices are decided based on market principles; and (iii) the load is balanced among multiple server nodes to make the architecture scalable w.r.t. the number of users. Through simulations, we have confirmed that the proposed method can mitigate the load at each server node to a great extent.

We propose a personal navigation system (called PNS) which navigates a tourist through multiple destinations efficiently. In our PNS, a tourist can specify multiple destinations with desired arrival/stay time and preference degree. The system calculates the route including part of the destinations satisfying tourist's requirements and navigates him/her. For the above route search problem, we have developed an efficient route search algorithm using a genetic algorithm. We have designed and implemented the PNS as a client-server system so that the portable device users can use the PNS through the Internet. Experiments using general map data and PDAs show that our PNS can calculate a semioptimal route almost in real-time.

We propose a QoS adaptation method for streaming video playback for portable computing devices where the playback quality of each video fragment is automatically adjusted from the remaining battery amount, desirable playback duration and the user's preference for each fragment. In our method, we assume that video segments (or shots) are classified into some predefined categories. Each user specifies the relative importance among categories and preferred video properties, such as proportion between motion speed and vividness for each category. From this information, playback quality and the properties of each category are determined so that the video playback can last for the specified duration within the battery amount. We have implemented a video streaming system consisting of a transcoder for PCs and a video player for PDAs.

In this paper, we propose a middleware library for efficiently developing distributed cooperative applications consisting of a large number of cellular phone users. Our middleware provides: (1) a dynamic group formation mechanism depending on users' locations and preferred subjects; and (2) a group communication mechanism called multiway synchronization for multicasting, synchronization and mutual exclusion. Most of Java executors on cellular phones do not support direct communication among user programs. Usable resources are also restricted. Therefore, in our middleware, most of user programs are executed on their servers as agents. Group communication is implemented as inter-process communication on the server, and only the user-interface parts are executed on the cellular phones.

We propose an energy-aware video streaming system for portable computing devices, in which the video can be played back for the specified duration within the remaining battery amount. To save power, we introduce techniques (i) to reduce playback quality of a video at an intermediate proxy and (ii) to shorten working time of the network I/F card using periodic bulk transfer of the video data on the wireless LAN. To enable playback for the specified duration, we have developed a power consumption model for portable devices using parameters on playback quality, playback duration, battery amount, and so on. We have also developed an algorithm to assign different playback quality among multiple video segments based on the user's preference.within the battery amount. Our experiments using PDAs and laptop PCs on 802.11b WLAN show that our system achieves less than 6 prediction error in playback duration while adapting playback quality among video segments.

This paper discusses temporal reasoning with respect to constraints on two concurrent sequences of events. If two given sequences of events can be mapped into one sequence that satisfies a given constraint, then the constraint is said to be consistent. First, we mention that the consistency of such constraints is NP-complete. Then we introduce the notion of graph representations of constraints. If a graph representation of a given constraint c can be constructed in polynomial time, then the consistency of c is decidable in polynomial time. However, it is shown that the graph representability of a given c is coNP-complete. Next, we propose a subclass CDC$^{\neq} of constraints such that for each constraint c in CDC$^{\neq}$, a graph representation of c can be constructed in polynomial time. The expressive power of CDC$^{\neq}$ is incomparable to any other subclasses of constraints for which the consistency problem is known to be tractable.

Exploration efficiency of GAs largely depends on parameter values. But, it is hard to manually adjust these values. To cope with this problem, several adaptive GAs which automatically adjust parameters have been proposed. However, most of the existing adaptive GAs can adapt only a few parameters at the same time. Although several adaptive GAs can adapt multiple parameters simultaneously, these algorithms require extremely large computation costs. In this paper, we propose self adaptive island GA (SAIGA) which adapts four parameter values simultaneously while finding a solution to a problem. SAIGA is a kind of island GA, and it adapts parameter values using a similar mechanism to meta-GA. Throughout our evaluation experiments, we confirmed that our algorithm outperforms a simple GA using De Jong's rational parameters, and has performance close to a simple GA using manually tuned parameter values.

This paper describes a new visual inspection system that can reliably detect fine defects as small as 0.1 /spl mu/m in mask/wafer patterns on the basis of comparison between scanning electron microscopic (SEM) images and design data. The chip-to-CAD comparison makes it possible to reliably detect significant defects that commonly occur in all chips on a mask/wafer. To cope with the difficult problems that arise when comparing heavily deteriorated SEM images with CAD patterns, new visual inspection algorithms are proposed for the thresholding for extracting pattern portions, correction of image positional displacements, and extraction and classification of significant defects. An automated system featuring parallel/pipeline processing and a simple and flexible structure has been constructed taking the complicated processing of deteriorating SEM images into account. When the input image resolution is set to 0.05 /spl mu/m/pixel, experiments confirm 0.1 /spl mu/m defects are unfailingly detected with the throughput of 1/spl sim/2 sec/frame. The proposed system is expected to make a substantial contribution to forthcoming developments in the visual inspection of very fine mask/wafer patterns.

The problem of distributing a Cartesian product file on multiple disks to maximize the parallelism for partial match queries is addressed. C. Faloutsos et al. (1989) have proposed an allocation method for Cartesian product files on multiple disks by using linear error-correcting codes. The performance of the allocation method is analyzed. Some conditions under which the allocation method is strictly optimal for queries with a given number of unspecified attributes are presented. A necessary and sufficient condition for a linear code to give a strictly optimal allocation method is discussed. Formulas for the average response time on queries with w unspecified attributes, denoted T/sub w/, in terms of the weight distribution of the code or its dual code, and formulas for the average response time Ton all queries, are given. Several examples whose average response times T/sub w/ or T are close to theoretical lower bounds are presented.>

This correspondence describes a new stereo analysis method using three views, in which correspondence is established among three images taken from triangularly configured viewpoints. Each match-point candidate obtained by the initial matching between the first and second images is easily examined independently of the other candidates using the third image. The correspondence determination is simple, fast, and reliable. Additionally, this analysis method allows occlusion to be dealt with explicitly. The effectiveness of the three-view stereo-analysis method is demonstrated by simulation and real object experiments. Ambiguous matches are sufficiently avoided for polyhedra. Position errors are less than 2.5 mm (about 0.4 percent) with camera-object spacing of 630 mm.

Recently, the representative instance has been proposed as a generalized concept of the pure universal relation. Let ${\bf R} = \{ \langle R_1 ,F_1 \rangle , \cdots , \langle R_n ,F_n \rangle \}$ be a database scheme, where each $R_i $ is a set of attributes and $F_i $ is a set of functional dependencies over $R_i $. ${\bf R}$ is said to be consistent if the representative instance of every database $I = \{ r_1 , \cdots ,r_n \}$ of ${\bf R}$ satisfies $F (= F_1 \cup \cdots \cup F_n )$, that is, if whenever each relation $r_i $ satisfies its own functional dependencies $F_i $, the representative instance satisfies all the functional dependencies F. In this paper, we present the following two results, which are generalizations of the previous results by [Sag2]. (1) It can be determined in $O(n|F|\|F\|)$ time whether ${\bf R}$ is consistent, where $|F|$ is the number of functional dependencies in F and $||F||$ is the size of the description of F. (A polynomial time algorithm for determining whether ${\bf R}$ is consistent is presented, independently, in [GY].) (2) Suppose that ${\bf R}$ is consistent. Given a subset V of $R_1 \cup \cdots \cup R_n $, we can construct in $O(n|F|\|F\|)$ time a relational expression such that (a) its value is the total projection of the representative instance onto V for every database of ${\bf R}$, (b) it consists of projection, extension join, and union, and (c) it contains neither a redundant union nor a redundant join.

Two decision problems related to multivalued dependencies in a relational database are considered. In this paper, an algorithm is presented for deciding whether or not a multivalued dependency can be derived from sets F of functional dependencies and M of multivalued dependencies on a set U of attributes, whose running time is proportional to min $(k^2 |U|,||F \cup M||^2 )$ where k and $|U|$ are the numbers of dependencies in $F \cup M$ and attributes in U, respectively, and $||F \cup M||$ is the size of description of F and M. A related algorithm is also considered which decides whether or not there exists a nontrivial multivalued dependency that is valid in a projection of the original relation.