Institute of Information Science, Academia Sinica

This report presents two families of algorithms for scheduling medications that interact with each other. All algorithms accept as input medication directions that have been compiled into a machine readable form. One family of algorithms is called One-Medication-at-a-Time, or OMAT. As the name implies, an OMAT algorithm produces a full schedule for each of the user’s medication in turn. Algorithms in the other family are called One-Dose-at-a-Time (ODAT) algorithms. An ODAT algorithm schedules one dose at a time without prior knowledge, or with limited knowledge, about future doses. It may fail to make good scheduling decisions compared with OMAT algorithms but can better accommodate dynamic variations in user behavior. Both OMAT and ODAT algorithms apply a variety of priority assignments as well refinements such as letting the user take medications as soon as possible or as late as possible. Data presented here on performance of the scheduling algorithms in terms of success rate and schedule quality can help builders of smart medication dispensers and scheduling tools choose among algorithms and tradeoff merits along different dimensions.

A general schedule specification (GSS) defines constraints on sizes and temporal separation of individual dispatches and upper and lower bounds on the total size of dispatches in specified time intervals. A dispatch may be a dispensing of medications to an individual, a delivery of some fresh produce to a green grocer, the transmission of a multimedia data element to a web surfer, and so on. When given a GSS, the scheduler can choose any schedule that the meets the constraints defined by the specification. The GSS is consistent if the constraints defined by it do not conflict with each other and is feasible if there is a schedule that meets all constraints. This paper describes conditions and algorithms which the scheduler can use to determine whether the specification is consistent and feasible and to schedule dispatches according to the GSS.

Copyright @ January 2007

Wireless visual sensor networks are potentially applicable for several emerging applications. Since the data size of the video captured from multiple sensors increases in proportion to the number of video sensors, the efficient compression of video data from multiple sensors is important and still challenging. However, most current multiview video coding approaches extended from single-view video coding standards perform both interview and temporal predictions at the encoder with very high computational complexity, which is not suitable for resource-limited video sensors. In this paper, a resource-scalable low-complexity multiview distributed video coding scheme is proposed. We study efficient exploitation of interview correlation by exchanging the media hash data extracted from video frames of adjacent video sensor nodes at the encoder and using the global motion parameters estimated and fed back from the decoder to improve coding efficiency. In addition, we present a power-rate-distortion (PRD) model to characterize the relationship between the available resources (e.g., power supply and target bit rate) and the RD performance. More specifically, an RD function in terms of the percentages for different coding modes of blocks and the target bit rate under the available resource constraints is derived for optimal block coding mode decision. Analytic results are provided to verify the resource scalability and accuracy of the proposed PRD model, which can provide a theoretical guideline for performance optimization in low-complexity video coding under limited resource constraints. The coding efficiency of the proposed low-complexity video codec is demonstrated via simulation results to outperform three known low-complexity video codecs, especially at high power and low bit rates.

Isotope labeling combined with liquid chromatography–mass spectrometry (LC–MS) provides a robust platform for analyzing differential protein expression in proteomics research. We present a web service, called MaXIC-Q Web (http://ms.iis.sinica.edu.tw/MaXIC-Q_Web/), for quantitation analysis of large-scale datasets generated from proteomics experiments using various stable isotope-labeling techniques, e.g. SILAC, ICAT and user-developed labeling methods. It accepts spectral files in the standard mzXML format and search results from SEQUEST, Mascot and ProteinProphet as input. Furthermore, MaXIC-Q Web uses statistical and computational methods to construct two kinds of elution profiles for each ion, namely, PIMS (projected ion mass spectrum) and XIC (extracted ion chromatogram) from MS data. Toward accurate quantitation, a stringent validation procedure is performed on PIMSs to filter out peptide ions interfered with co-eluting peptides or noise. The areas of XICs determine ion abundances, which are used to calculate peptide and protein ratios. Since MaXIC-Q Web adopts stringent validation on spectral data, it achieves high accuracy so that manual validation effort can be substantially reduced. Furthermore, it provides various visualization diagrams and comprehensive quantitation reports so that users can conveniently inspect quantitation results. In summary, MaXIC-Q Web is a user-friendly, interactive, robust, generic web service for quantitation based on ICAT and SILAC labeling techniques.

This paper describes the design and implementation of an open source embedded workflow framework (EMWF). By providing a language for specifying embedded workflow processes and light weight engines for executing and managing them, EMWF enables us to design and build service robots and assistive robotic devices on workflow-based architecture. The embedded process definition language supported by EMWF is called SISARL-XPDL. It is a subset of the standard process definition language XPDL (XML Process Definition Language) augmented with elements that are essential for smart embedded devices but not offered by XPDL. The SISARL-XPDL preprocessor translates augmented elements into either directives for the engine or compound built-in activities defined in terms of standard XPDL. EMWF provides two workflow engines, for Linux and Windows CE platforms. Both are written in C in order to keep the memory footprint and runtime overhead of the engine small. We use EMWF as a test bed for experimentation with the workflow approach and evaluation of workflow-based design.

In this paper, we propose an effective scheme for enhancing the visual details of digital images with the minimal amount of user adjustment. Digital archives are becoming increasingly popular due to the development of convenient and powerful digitizing techniques. However, a substantial number of digital images suffer from loss of detail because they were captured with old-fashioned equipment. Thus, an automatic tone reproduction technique is needed. We attempt to solve the above issues by combining a novel local normalization concept with an adaptive contrast assessment process. The proposed tone reproduction scheme effectively enhances poor quality regions, while simultaneously preserving good quality regions with default parameter settings. As the proposed scheme eliminates most of the manual effort required to adjust the parameters, it can be considered as nearly automatic. The results of experiments demonstrate that the scheme outperforms many existing algorithms when applied to restoring digital images for a national digital archive program.

index terms: Detail preserving, tone reproduction

This paper presents the architecture and implementation of an automatic medication dispenser specifically for users who take medications without close professional supervision. By relieving the users from the error-prone tasks of interpreting medication directions and administrating medications accordingly, the device can improve rigor in compliance and prevent serious medication errors. By taking advantage of scheduling flexibility provided by medication directions, the device makes the user's medication schedule easy to adhere and tolerant to tardiness whenever possible. This work is done collaborative by the medication scheduler and dispenser controller in an action-oriented manner. An advantage of the action-oriented interface between the components is extensibility, as new functions can be added and existing ones removed with little or no need to modify the dispenser control structure. The paper first describes the action-oriented design, major components and hardware and software structures of the smart device. It then provides an overview of the heuristic algorithms used by the medication scheduler and their relative merits.

With wireless technologies extending to every part of our daily lives, mobile networking applications are becoming increasingly popular for accessing the Internet. Among them, web surfing is one of the most important applications because the World Wide Web, unencumbered by geographic boundaries, has accelerated the dissemination of information and knowledge via the Internet. In this paper, we propose a peer-to-peer mobile web surfing scheme called Collaborative Internet Access (CIA). Unlike traditional approaches, the proposed scheme implements a Collaborative Forwarding algorithm that takes advantage of opportunistic wireless connections to improve network capacity by exploiting the diversity of network mobility. Moreover, we propose a Scalable CIA scheme, called SCIA, which integrates the Layered Multiple Description Coding (LMDC) algorithm with the CIA scheme. SCIA allows the end user to preview the web content, even before the data has been completely transferred. Using simulations as well as real-world network scenarios, we demonstrate that the proposed scheme provides a better web surfing service than traditional schemes, and thus facilitates more effective web surfing on the go.

Index terms: Internet Access, Peer-to-peer Networks, Opportunistic Networks, Scalable Coding.

This paper presents a novel people counting system for an environment in which a stationary camera can count the number of people watching a TV-wall advertisement or an electronic billboard without counting the repetitions in video streams in real time. The people actually watching an advertisement are identified via frontal face detection techniques. To count the number of people precisely, a complementary set of features is extracted from the torso of a human subject, as that part of the body contains relatively richer information than the face. In addition, for conducting robust people recognition, an online boosted classifier trained by Fisher's Linear Discriminant (FLD) strategy is developed. Our experiment results demonstrate the efficacy of the proposed system for the people counting task.

Index terms: People counting, Video surveillance.

This paper presents the architecture and implementation of an automatic medication dispenser specifically for users who take medications without close professional supervision. By relieving the users from the error-prone tasks of interpreting medication directions and administrating medications accordingly, the device can improve rigor in compliance and prevent serious medication errors. By taking advantage of scheduling flexibility provided by medication directions, the device makes the user's medication schedule easy to adhere and tolerant to tardiness whenever possible. This work is done collaborative by the medication scheduler and dispenser controller in an action-oriented manner. An advantage of the action-oriented interface between the components is extensibility, as new functions can be added and existing ones removed with little or no need to modify the dispenser control structure. The paper first describes the action-oriented design, major components and hardware and software structures of the smart device. It then provides an overview of the heuristic algorithms used by the medication scheduler and their relative merits.

We study an online problem that occurs when the capacities of machines are heterogeneous and all jobs are identical. Each job is associated with a subset, called feasible set, of the machines that can be used to process it. The problem involves assigning each job to a single machine in its feasible set, i.e., to find a feasible assignment. The objective is to maximize the throughput, which is the sum of the bandwidths of the jobs; and minimize the total load, which is the sum of the loads of the machines. In the online setting, the jobs arrive one-by-one and an algorithm must make decisions based on the current state without knowledge of future states. By contrast, in the offline setting, all the jobs with their feasible sets are known in advance to an algorithm. Let m denote the total number of machines, ɑ denote the competitive ratio with respect to the throughput and β denote the competitive ratio with respect to the total load. In this paper, our contribution is that we propose an online algorithm that finds a feasible assignment with a throughput-competitive upper bound ɑ= O(√m), and a total-load-competitive upper bound β = O(√m). We also show a lower bound ɑβ=Ω(√m), of the problem in the offline setting, which implies a lower bound ɑβ=Ω(√m), of the problem in the online setting.

Keywords: Online algorithms, job assignment, bi-objective optimization, throughput, load.

Instant Messaging (IM) has emerged as a popular communication service over the Internet. One of the themes of IM systems is to provide a presence directory that carries information on user's presence or absence to his/her friends. In this paper, we present new presence directory architecture and give a comparison of existing presence directories. We first introduce the distributed buddy-list search problem.We then present P2Dir, a distributed peer-to-peer presence directory protocol to address this problem. For each newly arriving user, the protocol is used to search for network presence of his/her buddies and also to notify them on his/her presence. P2Dir organizes directory servers into a 2-hop P2P overlay for efficient buddy searching. Moreover, P2Dir leverages the breadth-first search algorithm and a onehop caching strategy to achieve small constant search latency on average. We measure the performance of our P2Dir system, in terms of search cost and search satisfaction, where search cost is defined as total number of messages incurred among the directories upon the arrival of a user, and search satisfaction is defined as the time it takes to search for the newly arriving user's buddy list and to notify presence of the newly arriving user to his/her buddies. We evaluate the performance of our P2Dir system in terms of search cost and search satisfaction through simulations, and compare it with a mesh-based presence protocol. The results show that our P2Dir achieves performance gains in search cost without sacrificing search satisfaction.

The resource limitation of sensor nodes poses a great challenge in designing an efficient key establishment scheme for Wireless Sensor Networks (WSNs). In spite of the fact that many elegant and clever solutions have been proposed, no practical key establishment scheme has emerged.

In this paper, a ConstrAined Random Perturbation based pairwise keY establishment (CARPY) scheme and its variant, a CARPY+ scheme, for WSNs, are presented. Compared to all existing schemes which satisfy only some requirements in so-called sensor-key criteria, including 1) resilience to various attacks, 2) directed and guaranteed key establishment, 3) resilience to network configurations, 4) efficiency, and 5) resilience to dynamic node deployment, the proposed CARPY+ scheme meets all requirements. In particular, CARPY+ is a key establishment scheme designed for WSNs, which can achieve key sharing between any two nodes without the need of communication. We examine the CARPY and CARPY+ schemes from both the theoretical and experimental aspects. They have also been practically implemented on the TelosB compatible mote to evaluate the corresponding performance and overhead.