Indoor location-based services (LBS) have witnessed rapid growth in applications such as user tracking, healthcare monitoring, and smart facility management, driving the critical need for efficient and pervasive indoor localization. Traditional WiFi fingerprinting methods face significant challenges: multi-site localization (MSL) relies on densely deployed static WiFi sites, incurring high infrastructure costs and conflicting with the Integrated Sensing and Communication (ISAC) paradigm; single-site localization (SSL) requires complex hardware; and single mobile site localization (SMSL) suffers from poor real-time performance due to long traversal paths. To address these limitations, this paper proposes a Multi-Agent Deep Reinforcement Learning-based Collaborative Indoor Localization (MADRL-CIL) framework. MADRL-CIL leverages multiple collaborative mobile sites to dynamically acquire Received Signal Strength (RSS) fingerprints. By modeling each mobile site as an agent, the framework formulates the path selection and fingerprint acquisition task as a Multi-Agent Deep Reinforcement Learning (MADRL) problem under a Centralized Training with Decentralized Execution (CTDE) paradigm, facilitating effective collaboration among multiple mobile sites to optimize localization accuracy while minimizing localization time. Additionally, a Multi-Site Fingerprint Matching (MS-FM) model is specifically designed to process collaboratively collected RSS fingerprints, enabling fine-grained localization accuracy. Experimental evaluations in a real-world indoor environment demonstrate that MADRL-CIL achieves localization accuracy comparable to dense multi-static site deployments while provides good real-time performance.

The utilization of Wi-Fi-based technology for pervasive indoor user identification has gained prominence due to its cost-effective nature and compatibility with user devices. Previous works proposed capturing the media access control (MAC) address emitted from a user’s device and using information element (IE)-based MAC de-randomization methods to mitigate the impairment caused by random MAC. However, IE types of different Wi-Fi devices are not consistently differentiated, leading to identification errors in IE-based methods. Additionally, typical Wi-Fi fingerprinting approaches require densely predeployed Wi-Fi stations, contradicting the principle of pervasive localization. To address these challenges, we propose the mobile single-station-based user identification (MS.Id) technique, which leverages Wi-Fi mobile single stations for pervasive indoor user identification. MS.Id includes mobile single-station localization (MSL) and MAC de-randomization based on users’ spatiotemporal location and IE information (DR.LIE). MSL can be implemented on a standard mobile Wi-Fi station without extensive predeployment. DR.LIE performs MAC de-randomization using the LIC algorithm to identify users with random MAC addresses. Experimental results demonstrate that MS.Id outperforms previous IE-based user identification methods and multistation localization techniques. MSL achieves a localization error of 1.15 m which is better than multistation with 12 APs of 1.40 m. DR.LIE demonstrates an identification accuracy of 95.24% which is better than AIMAC of 85.48%.

Leveraging the widespread deployment of existing WiFi sites, WiFi-based techniques offer substantial potential for achieving pervasive indoor localization among various indoor localization techniques. Conventional WiFi-based indoor localization techniques primarily focus on providing fine-grained accuracy. However, previous techniques are not pervasive due to the following constraints: 1) they can hardly be implemented in environments with limited resources of WiFi sites; and 2) they are constrained by high hardware requirements, such as the need for multiple antennas. In this paper, we propose a novel technique called Mobile Single-site Localization (MS-Loc), which leverages a mobile single-site to perform indoor localization. Specifically, MS-Loc utilizes existing hardware at off-the-shelf mobile WiFi sites to achieve pervasive localization rather than relying on multiple sites or multiple antennas. Moreover, in MS-Loc, a tailor-designed path planning algorithm guides the movement of the mobile single-site to locate targets quickly and accurately. We conducted extensive experiments using a real-world testbed. The experimental results demonstrate that MS-Loc presents a competitive localization accuracy compared to previous techniques but is pervasive.

With the proliferation of sensors and the emergence of novel applications, IoT data has grown exponentially in recent years. Given this trend, efficient data management is crucial for a system to easily access vast amounts of information. For decades, B + -tree-based indexing schemes have been widely adopted for providing effective search in IoT systems. However, in systems with pre-distributed sensors, B + -tree-based indexes fail to optimally utilize the known IoT data distribution, leading to significant write overhead and energy consumption. Furthermore, as non-volatile memory (NVM) technology emerges as the alternative storage medium, the inherent write asymmetry of NVM leads to instability issues in IoT systems, especially for write-intensive applications. In this research, by considering the write overheads of tree-based indexing schemes and key-range distribution assumption, we rethink the design of the tree-based indexing schemes and propose an adaptive pre-built tree (APB-tree) indexing scheme to reduce the write overhead in serving insertion and deletion of keys in the NVM-based IoT system. The APB-tree profiles the hot region of the key distribution from the known key range to pre-allocate the index structure that alleviates online index management costs and runtime index overhead. Meanwhile, the APB-tree maintains the scalability of a tree-based index structure to accommodate the large amount of new data brought by the additional nodes to the IoT system. Extensive experiments demonstrate that our solution achieves significant performance improvements in write operations while maintaining effective energy consumption in the NVM-based IoT system. We compare the energy and time required for basic key operations such as Put(), Get(), and Delete() in APB-trees and B + -tree-based indexing schemes. Under workloads with varying ratios of these operations, the proposed design effectively reduces execution time by 47% to 72% and energy consumption by 11% to 72% compared to B + -tree-based indexing schemes.

Ensuring relative consistency in executing temporal queries to access real-time sensor data streams maintained in a database is a challenging problem, particularly when data transmission delays are lengthy and highly variable. Due to the unordered arrivals of sensor data, the databases may contain numerous open data versions (ODVs) with undefined validity intervals. Accessing ODVs may violate the relative consistency requirements of temporal queries, resulting in incorrect results. Although the Re-execution with Every Update (REU) method can resolve this issue, it may introduce heavy re-execution costs and significant delays in query completion. In this article, we study the problem of retrieving data items with temporal consistency requirements in a multi-data-stream database. To balance response time and meet the relative consistency requirements of queries, we introduce an enhanced REU mechanism called Re-Execution with Deadline (RED). Moreover, we propose a novel optional mechanism called Backward Execution Option (BEO) for temporal queries to achieve relative consistency in their execution with quick results by relaxing the data freshness constraints. By combining RED with BEO, we formulate the Repeated BEO (RBEO) to further reduce the query response time. We extend the timestamped key-value store MVLevelDB into MVLevelDB + to implement the proposed mechanisms. To reduce the query re-execution cost as required in RED and REU, we designed the Query Pool with Execution State (QpES) mechanism to achieve relative consistency in query execution with lower checking overhead and only one re-execution. We conducted extensive evaluation experiments on MVLevelDB + using benchmark programs to illustrate their performance characteristics on handling temporal queries in the modeled IoT system.

As widely deployed WiFi sensors in indoor scenarios, e.g., WiFi access points and WiFi monitors, WiFi signal-based indoor localization has attracted increasing attention from research communities in the past decade. Among various WiFi-based localization techniques, received signal strength (RSS) fingerprinting based on multiple sensors reveals its superiority and effectiveness in complex indoor environments. Existing multi-sensor-based techniques mainly focus on designing efficient algorithms to improve localization performance. However, the limitations of 1) densely pre-deployed WiFi sensors and, 2) sensitivity to changing sensors are not considered appropriately. In this paper, we propose a novel technique called Single Mobile Sensor (SMS) localization, which leverages a single mobile sensor for indoor localization. The SMS localization technique employs a fingerprinting technique with a custom-designed model, named SMS Fingerprint Matching (SMSFM) model, which is responsible for matching fingerprints constructed by a single mobile sensor to estimate targets' location. Numerous experiments conducted on a practical testbed have revealed that the SMSFM model surpasses conventional models, leading to SMS localization delivering competitive localization accuracy compared to previous multi-sensor-based technologies, despite relying solely on a single sensor.

Recommendations are important web services in the era of information explosion. Particularly, group recommendations aim to suggest new items to groups such that the members of groups are likely interested in. However, existing works still suffer from sparsity and cold-start issues (e.g., cold-start groups or items) for groups with few interactions on items. Most of them model the preferences or features of entities (i.e., users, items and groups) from heterogeneous interactions (i.e., user-item, group-item and user-group interactions) between two distinct types of entities, while ignoring the homogeneous interactions (i.e., user-user, item-item and group-group interactions) between entities of one type. To this end, we propose a new model, called H3Rec, which learns the representations of entities by developing two graph embedding layers based on an interaction graph of all entities. Specifically, the two graph embedding layers make full use of the hidden information in theHigher-orderHeterogeneous andHomogeneous interactionsof the graph. Therefore, H3Rec can alleviate the sparsity and cold-start issues and improve the performance of group recommendations. The experimental results on two real world datasets in different domains show the superiority of H3Rec in group recommendations, especially for cold-start groups and items.

Although log-structured merge trees (LSM-trees) are commonly adopted in many NoSQLs as they can significantly improve the write performance in updating a database, most of the proposed LSM-trees are concentrated on storing a single version of data. On the other hand, in many Internet of Things (IoT) applications, it is important to maintain the old versions of data in addition to the latest version. In this article, we introduce our design and implementation of an enhancement of LevelDB to multiversion LevelDB (called MVLevelDB) with the purpose to efficiently support temporal queries on multiversion data in IoT applications. Based on the temporal consistency, we formulated the log-structured multiversion tree (LSMV-tree) to be implemented into MVLevelDB. In LSMV-tree, each data version is associated with two time-stamps to define its validity interval, and both the data versions and the components are time-sorted to improve the efficiency in searching data in processing temporal queries. To handle the problem of multicomponents data versions, we designed the data version duplication (DvD) method in which a data version will be duplicated in the next component if it is valid while its component is being flushed from the main memory to disk storage. Extensive experiments using a benchmark program have been performed to investigate the performance of MVLevelDB as compared with LevelDB both in writing and reading data.

Passive indoor localization for mobile Wi-Fi devices, e.g., smartphones, has attracted increasing attention from research communities recently. Existing passive localization techniques leverage received signal strength (RSS) of packets transmitted by target Wi-Fi devices and do not require a dedicated software installed on the devices. However, RSS-based passive localization techniques: 1) are device dependent, which results in poor localization accuracy for a wide variety of mobile devices and 2) cannot perform real-time passive localization. In this article, we present a novel passive localization technique, namely, packet delivery ratio (PDR) fingerprinting, to address these problems. In PDR fingerprinting, the lowest-power and highest-modulation scheme (LPHMS) is proposed to generate device-invariant PDR, which replaces RSS to construct fingerprints, to achieve device-invariant localization accuracy. Moreover, instead of passively monitoring packets rarely sent by mobile devices, in PDR fingerprinting, access points (APs) actively transmit request-to-send (RTS) frames to trigger target devices to reply clear-to-send (CTS) frames to calculate PDR. The RTS/CTS mechanism enables PDR fingerprinting to perform real-time localization. We have conducted extensive experiments in a real-world testbed. The experimental results demonstrate that PDR fingerprinting presents a competitive localization accuracy compared to RSS-based passive fingerprinting methods but is device invariant.

We consider the problem of clustering graph nodes over large-scale dynamic graphs, such as citation networks, images and web networks, when graph updates such as node/edge insertions/deletions are observed distributively. We propose communication-efficient algorithms for two well-established communication models namely the message passing and the blackboard models. Given a graph with n nodes that is observed at s remote sites over time [1,t], the two proposed algorithms have communication costs Õ(ns) and Õ(n + s) (Õ hides a polylogarithmic factor), almost matching their lower bounds, Ω(ns) and Ω(n + s), respectively, in the message passing and the blackboard models. More importantly, we prove that at each time point in [1,t] our algorithms generate clustering quality nearly as good as that of centralizing all updates up to that time and then applying a standard centralized clustering algorithm. We conducted extensive experiments on both synthetic and real-life datasets which confirmed the communication efficiency of our approach over baseline algorithms while achieving comparable clustering results.

Given a directed graph G(V,E), a k-(Shortest) Path Cover is a subset C of the nodes V such that every simple (or shortest) path in G consisting of k nodes contains at least one node from C. In this paper, we extend the notion of k-Path Covers such that the objects to be covered don't have to be single paths but can be concatenations of up to p simple (or shortest) paths. For the generalized problem of computing concatenated k-(Shortest) Path Covers, we present theoretical results regarding the VC-dimension of the concatenated path set in dependency of p as well as (approximation) algorithms. Subsequently, we study interesting special cases of concatenated k-Path Covers, in particular, covers for piecewise shortest paths, round tours and trees. For those, we show how the pruning algorithm for k-Path Cover computation can be abstracted and modified in order to also solve concatenated k-Path Cover problems. An extensive experimental study on different graph types proves the applicability and efficiency of our approaches.

Graph sparsification has been used to improve the computational cost of learning over graphs, e.g., Laplacian-regularized estimation and graph semi-supervised learning (SSL). However, when graphs vary over time, repeated sparsification requires polynomial order computational cost per update. We propose a new type of graph sparsification namely fault-tolerant (FT) sparsification to significantly reduce the cost to only a constant. Then the computational cost of subsequent graph learning tasks can be significantly improved with limited loss in their accuracy. In particular, we give theoretical analyze to upper bound the loss in the accuracy of the subsequent Laplacian-regularized estimation and graph SSL, due to the FT sparsification. In addition, FT spectral sparsification can be generalized to FT cut sparsification, for cut-based graph learning. Extensive experiments have confirmed the computational efficiencies and accuracies of the proposed methods for learning on dynamic graphs.

When a shingle magnetic recording (SMR) drive has been widely applied to modern computer systems (e.g., archive file systems, big data computing systems, and large-scale database systems), storage system developers should thoroughly review whether current designs (e.g., index schemes and data placements) are appropriate for an SMR drive because of its sequential write constraint. Through many prior works excellently manage data in an SMR drive by integrating their proposed solutions into the driver layer, an index scheme over an SMR drive has never been optimized by any previous works because managing index over the SMR drive needs to jointly consider the properties of B + -tree and SMR natures (e.g., sequential write constraint and zone partitions) in a host storage system. Moreover, poor index management will result in terrible storage performance because an index manager is extensively used in file systems and database applications. For optimizing the B + -tree index structure over an SMR storage, this work identifies performance overheads caused by the B + -tree index structure in an SMR drive. By such observation, this study proposes a sequential-write-constrained B + -tree index scheme, namely SW-B + tree, which consists of an address redirection data structure, an SMR-aware node allocation mechanism, and a frequency-aware garbage collection strategy. According to our experiments, the SW-B + tree can improve the SMR storage performance 55% on average.

In order to maintain a healthy living both physiologically and psychologically, it is important for patients with mild cognitive impairment (MCI) to maintain active in daily life. In this paper, we demonstrate how to use simple motion sensors, e.g., accelerometers, gyroscopes and magnetometers, to design and develop a system, called ActiveLife, for effective tracking of the daily living activities of MCI patients within their living rooms. In order to simplify the activity detection process, in ActiveLife, we adopt the context-based approach to model the common activities performed by the user within a day. Since the accelerometer and gyroscope are tri-axial sensors, the sensor data for different axes can be used to predict the current posture of the user while he is performing an activity. Combining with the heading direction of the posture obtained from the magnetometer and distance travelled during the transition of activities, we can estimate the current activity of the user. To further improve the estimation accuracy, we have designed an algorithm using the machine-learning technique, i.e., support vector machines (SVM), for activity classification.

Maintaining the freshness of real-time data is one of the crucial design issues in cyber-physical systems (CPS). Past studies have focused on designing update algorithms to minimize the workload imposed by a fixed set of update tasks while ensuring the temporal validity of data. In this paper, we revisit this problem in dynamic cyber-physical systems (DCPS) which may exhibit multi-modal behavior. Any solution to this problem must recognize that: (1) different update algorithms may be needed in different modes according to the workload in each mode, and (2) temporal validity of data must be maintained not only in each mode but also during the mode switch. To strike a balance between data freshness and system schedulability, we propose a utilization-based scheduling selection (UBSS) strategy. We first introduce two synchronous mode switch algorithms, named search-based switch (SBS) and adjustment-based switch (ABS) to search for the proper switch point online and execute all update tasks in the new mode synchronously. SBS checks for temporal validity at the beginning time slot of each idle period in the schedule, while ABS relaxes this restriction through schedule adjustment. To support immediate mode switch, we propose an asynchronous switch algorithm named instant switch (IS) to reduce the switch delay. IS schedules outstanding jobs from the old mode together with the jobs in the new mode using the least-available-laxity-first scheduling policy. Our experimental results demonstrate the effectiveness of these three algorithms. They also show that UBSS strategy can significantly outperform a single fixed update algorithm in terms of maintaining better data freshness while incurring only limited online switch overhead.

In this paper, we introduce SmartMind, an activity tracking and monitoring system to help Alzheimer's diseases (AD) patients to live independently within their living rooms while providing emergent help and support when necessary. Allowing AD patients to handle their daily activities not only can release some of the burdens on their families and caregivers, but also is highly important to help them regain confidence towards a healthy life and reduce the degeneration rates of their memories. The daily activities of a patient captured from SmartMind can also serve as important indicators to describe his/her normal living habit (NLH). By checking with NLH, the patient's current health status can be estimated on a daily basis.

In this paper, we propose a novel multi-version B$^+$-tree index structure, called block-based multi-version B$^+$-tree ( BbMVBT), for indexing multi-versions of data items in an embedded multi-version database (EMVDB ) on flash memory. An EMVDB needs to support streams of update transactions and version-range queries to access different versions of data items maintained in the database. In BbMVBT, the index is divided into two levels. At the higher level, a multi-version index is maintained for keeping successive versions of each data item. These versions are allocated consecutively in a version block. At the lower level, a version array is used to search for a specific data version within a version block. With the reduced index structure of BbMVBT, the overhead for managing the index in processing update operations can be greatly reduced. At the same time, BbMVBT can also greatly reduce the number of accesses to the index in processing version-range queries. To ensure sufficient free blocks for creating version blocks for efficient execution of BbMVBT, in this paper, we also discuss how to perform garbage collection using the purging-range queries for reclaiming “old” versions of data items and their associated entries in the index nodes. Analysis of the performance of BbMVBT is presented and verified with performance studies using both synthetic and real workloads. The performance results illustrate that BbMVBT can significantly improve the read and write performance to the multi-version index as compared with MVBT even though the sizes of the version blocks are not large.

This paper describes SmartMood, a mood tracking and analysis system designed for patients with mania. By analyzing the voice data captured from a smartphone while the user is having a conversation, statistics are generated for each behavioral factor to quantitatively describe his/her mood status. By comparing the newly generated statistics with those under normal mood, SmartMood tries to identify any new manic episodes so that appropriate consultation and medication actions can be taken. The daily behavioral statistics may serve as important references for psychiatrists to show the effectiveness of treatments. To reduce the probability of false alarms, we propose an adaptive running range method to estimate the normal mood range for each behavioral factor, and study methods to minimize the effects of background noise on the generated statistics. The preliminary experimental results on SmartMood show that a method using the pitch of a voice data sample to identify silent periods can better differentiate the voice of a normal or manic user in a call session than other methods. The results from the limited proof of concept testing indicate that moving to clinical testing is warranted.

In this paper, we study how mobile computing and wireless technologies can be explored to provide effective ubiquitous healthcare services. Instead of reinventing the wheels, we make use of smartphones, off-the-shelf components, and existing technologies in ubiquitous computing (i.e. wireless and mobile positioning technologies, and data acquisition techniques and processing via sensors) to develop a middleware, and tools for the development of systems and applications to provide effective ubiquitous healthcare services. Two main tasks to be studied are: 1) Developing a framework, called SmartHealth, to provide the infrastructure and architectural support for realizing ubiquitous healthcare services, and 2) Designing and developing ubiquitous healthcare applications by utilizing the SmartHealth framework to let users experience and benefit from the provided services. We use scenarios to illustrate how mobile/wireless and sensor technologies can enable ubiquitous healthcare services in Smart Health. Some of the examples included in Smart Health are: location tracking, vital signs and well-being data acquisition and analysis, fall detection and behavior monitoring, and sleep analysis. As a start, based on the Smart Health framework, we introduce a smartphone app, called Smart Mood, for tracking the mood of patients who are suffering mood disorder (i.e., manic and depression) to demonstrate how Smart Health can effectively enable ubiquitous healthcare services.

Embedded database systems are widely adopted in various control and motoring systems, e.g., cyber-physical systems (CPSes). To support the functionality to access the historical data, a multiversion index is adopted to maintain multiple versions of data items and their index information. However, CPSes are usually battery-powered embedded systems that have limited energy, computing power, and storage space. In this work, we consider the systems with phase-change memory (PCM) as their storage due to its non-volatility and low energy consumption. In order to resolve the problem of the limited storage space and the fact that existing multiversion index designs are lack of space efficiency, we propose a space-efficient multiversion index scheme to enhance the space utilization and access performance of embedded multiversion database systems on PCM by utilizing the byte-addressability and write asymmetry of PCM. A series of experiments was conducted to evaluate the efficacy of the proposed scheme. The results show that the proposed scheme achieves very high space utilization and has good performance on serving update transactions and range queries.

In this paper, we study the important performance issues in using the purging-range query to reclaim old data versions to be free blocks in a flash-based multi-version database. To reduce the overheads for using the purging-range query in garbage collection, the physical block labeling (PBL) scheme is proposed to provide a better estimation on the purging version number to be used for purging old data versions. With the use of the frequency-based placement (FBP) scheme to place data versions in a block, the efficiency in garbage collection can be further enhanced by increasing the deadspans of data versions and reducing reallocation cost especially when the spaces of the flash memory for the databases are limited.

Although the deferrable scheduling algorithm for fixed priority transactions ( DS-FP) has been shown to provide a better performance compared with the More-Less (ML) method, there is still a lack of any comprehensive studies on the necessary and sufficient conditions for the schedulability of DS-FP. In this paper, we first analyze the necessary and sufficient schedulability conditions for DS-FP, and then propose a schedulability test algorithm for DS-FP by exploiting the fact that there always exists a repeating pattern in a DS-FP schedule. To resolve the limitation of fixed priority scheduling in DS-FP, we then extend the deferrable scheduling to a dynamic priority scheduling algorithm called DS-EDF by applying the earliest deadline first (EDF) policy to schedule update jobs. We also propose a schedulability test for DS-EDF and compare its performance with DS-FP and ML through extensive simulation experiments. The results show that the schedulability tests are effective. Although the schedulability of DS-EDF is lower than DS-FP and the repeating patterns in DS-EDF schedules are longer than those in DS-FP due to the use of dynamic priority scheduling, the performance of DS-EDF is better than both DS-FP and ML in terms of CPU utilization and impact on lower priority application transactions.

Recently, flash-based embedded databases have gained their momentum in various control and monitoring systems, such as cyber-physical systems (CPSes). To support the functionality to access the historical data, a multiversion index is adopted to simultaneously maintain multiple versions of data items, as well as their index information. However, maintaining a multiversion index on flash memory incurs considerable performance overheads on garbage collection, which is to reclaim the spaces occupied by the outdated/invalid data items and their index information on flash memory. In this work, we propose an efficient garbage collection strategy to solve the garbage collection issues of flash-based multiversion databases. In particular, a version-tracking method is proposed to accelerate the performance on the process on identifying/reclaiming the space of invalid data and their indexes, and a pre-summary method is also designed to solve the cascading update problem that is caused by the write-once nature of flash memory and is worsened when more versions refer to the same data item. The capability of the proposed strategy is then verified by analytical and experimental studies.

Maintaining sensor data validity while exercising timely control is crucial in real-time sensing and control systems. The goal of scheduling algorithms deployed in such systems is to maintain the validity of real-time sensor data so as to maximize the schedulability of update transactions with minimum update workload so that control actions occur on time. In this paper, we first propose a dynamic scheduling algorithm, called Deferrable Scheduling with Least Actual Laxity First (DS-LALF). DS-LALF is designed by extending the deferrable scheduling algorithm, DS-FP which is designed for fixed priority systems. We develop a schedulability test algorithm for DS-LALF based on pattern analysis and a pattern search algorithm to find the shortest and earliest pattern in the schedule. Then, based on DS-LALF, a co-scheduling algorithm called Co-LALF-to schedule update transactions and control transactions in a real-time sensing and control system together-is developed 1) to meet the deadlines of all the control transactions and 2) to maximize the quality of data (QoD) utilized by the control transactions. Co-LALFschedules the jobs in the ascending order of their actual laxities and defers the release times of update jobs as long as the corresponding sensor data are maintained within the required quality. Experimental results show that DS-LALF incurs lower update workload compared with DS-FP and ML, and its schedulability is close to DS-FP but is much better than ML and DS-EDF. The experimental results also show that Co-LALF is effective in improving the overall performance by ensuring better QoD for the real-time data while meeting the deadline constraints of all the control transactions.

In a real-time database system for detection of critical events,On co-scheduling of periodic update and application transactions with fixed priority assignment for real-time monitoring meeting the deadlines of the application transactions and maintaining the quality of the real-time data objects are two critical issues in ensuring the effectiveness of performing the real-time monitoring tasks. Unfortunately, these two goals conflict with each other and are difficult to be achieved at the same time. To address this update and application transaction co-scheduling problem, in this paper, we propose a fixed priority scheduling algorithm called Periodic Co-Scheduling (PCS). PCS uses periodic update transactions to maintain the temporal validity of real-time data objects. It judiciously decides the priority order among all the update and application transactions so that the constructed co-schedule can satisfy the deadline constraints of all the application transactions while maximizing the qualities of the real-time data objects. The effectiveness of the PCS algorithm is validated through our extensive simulation experiments.

In typical location-based services (LBS), moving objects (e.g., GPS-enabled mobile phones) report their locations through a wireless network. An LBS server can use the location information to answer various types of continuous queries. Due to hardware limitations, location data reported by the moving objects are often uncertain. In this paper, we study efficient methods for the execution of Continuous Possible Nearest Neighbor Query (CPoNNQ) that accesses imprecise location data. A CPoNNQ is a standing query (which is active during a period of time) such that, at any time point, all moving objects that have non-zero probabilities of being the nearest neighbor of a given query point are reported. To handle the continuous nature of a CPoNNQ, a simple solution is to require moving objects to continuously report their locations to the LBS server, which evaluates the query at every time step. To save communication bandwidth and mobile devices' batteries, we develop two filter-based protocols for CPoNNQ evaluation. Our protocols install "filter bounds" on moving objects, which suppress unnecessary location reporting and communication between the server and the moving objects. Through extensive experiments, we show that our protocols can effectively reduce communication costs while maintaining a high query quality.

Typical real-time sensing and control systems consist of a set of update tasks for installing sensor measurements from the operation environment and a set of control tasks to access to these measurements for making control decisions. Although configuring the sensors with higher sampling rates could improve the accuracy of the measurements and control quality in general, scheduling high frequent update jobs may seriously affect the schedulability of the control tasks. Missing or delaying the control tasks may severely degrade the overall control performance of the system. In this paper, instead of using the traditional periodic update model, we adopt the a periodic update model in generating update jobs for maintaining data validity. We propose an adaptive co-scheduling algorithm called Least Idle Slot First (LISF) to schedule the update tasks and control tasks with the purposes to meet the deadlines of the control tasks and maximize the quality of control (QoC) offered by the control tasks. LISF schedules the jobs in the ascending order of the number of available idle slots before their deadlines and defers the release times of update jobs as long as the corresponding data objects are maintained within the required quality. The experiment results show that LISF can effectively improve the system schedulability and the control performance in the real-time sensing and control systems.

The periodic update transaction model has been used to maintain the freshness (or temporal validity) of real-time data. Period and deadline assignment has been the main focus of past studies, such as the More-Less scheme [25], in which update transactions are guaranteed by the Deadline Monotonic scheduling algorithm [16] to complete by their deadlines. In this paper, we propose a deferrable scheduling algorithm for fixed-priority transactions, a novel approach for minimizing update workload while maintaining the temporal validity of real-time data. In contrast to prior work on maintaining data freshness periodically, update transactions follow an aperiodic task model in the deferrable scheduling algorithm. The deferrable scheduling algorithm exploits the semantics of temporal validity constraint of real-time data by judiciously deferring the sampling times of update transaction jobs as late as possible. We present a theoretical estimation of its processor utilization and a sufficient condition for its schedulability. Our experimental results verify the theoretical estimation of the processor utilization. We demonstrate through the experiments that the deferrable scheduling algorithm is an effective approach and it significantly outperforms the More-Less scheme in terms of reducing processor workload.

The more-less (ML) scheme has been shown to be an efficient approach for maintaining temporal consistency of real-time data objects. Although ML provides a deterministic guarantee in temporal consistency, the number of update transactions that can be supported in a system is limited. This is due to its use of the worst-case computation time in deriving deadlines and periods of update transactions. This paper studies the problem of temporal consistency maintenance where a certain degree of temporal inconsistency is tolerable. A suite of statistical more-less (SML) approaches are proposed to explore the trade-off between quality of service (QoS) of temporal consistency and the number of supported transactions. It begins with a baseline algorithm, SML-BA, which provides the requested QoS of temporal consistency. Then, SML with optimization (SML-OPT) is proposed to further improve the QoS by better utilizing the excess processor capacity. Finally, SML-OPT is enhanced with a slack reclaiming scheme (SML-SR). The reclaimed slacks are used to process jobs whose required computation time is larger than the guaranteed computation time. Simulation experiments are conducted to compare the performance of these schemes (SML-BA, SML-OPT, and SML-SR) together with the deterministic more-less and half-half schemes. The results show that the SML schemes are effective in trading the schedulability of transactions for the QoS guaranteed. Moreover, SML-SR performs best and offers a significant QoS improvement over SML-BA and SML-OPT.

An approach to improve the reliability of query results based on error-prone sensors is to use redundant sensors. However, this approach is expensive; moreover, some sensors may malfunction and their readings need to be discarded. In this paper, we propose a statistical approach to decide which sensors to be used to answer a query. In particular, we propose to solve the problem with the aid of continuous probabilistic query (CPQ), which is originally used to manage uncertain data and is associated with a probabilistic guarantee on the query result. Based on the historical data values from the sensors, the query type, and the requirement on the query, we present methods to select an appropriate set of sensors and provide reliable answers for aggregate queries. Our algorithm is demonstrated in simulation experiments to provide accurate and robust query results.

Although simultaneous multithreading (SMT) has been shown being an efficient technique to improve processor performance, little work has been done on real-time SMT scheduling. The objective of this paper is to explore realtime SMT scheduling for independent periodic task sets with schedulability guarantees. We propose emulation-based scheduling algorithms with and without task migration to emulate an adjustable SMT processor over a non-adjustable SMT processor. The schedulability tests for the proposed scheduling algorithms are presented. An approximation bound on the average number of tasks running in parallel is also shown. The performance of the proposed algorithms was evaluated by a series of simulation experiments.

Periodic update transaction model has been used to maintain freshness (or temporal validity) of real-time data. Period and deadline assignment has been the main focus in the past studies such as the more-less scheme by Xiong and Ramamrithan (2004) in which update transactions are guaranteed by the deadline monotonic scheduling algorithm by Leung and Whitehead (1982) to complete by their deadlines. In this paper, we propose a novel algorithm, namely deferrable scheduling, for minimizing imposed workload while maintaining temporal validity of real-time data. In contrast to previous work, update transactions scheduled by the deferrable scheduling algorithm follow a sporadic task model. The deferrable scheduling algorithm exploits the semantics of temporal validity constraint of real-time data by judiciously deferring the sampling times of update transaction jobs as late as possible. We present a theoretical analysis of its processor utilization, which is verified in our experiments. Our experimental results also demonstrate that the deferrable scheduling algorithm is a very effective approach, and it significantly outperforms the more-less scheme in terms of reducing processor workload

This paper studies the location management problem in cellular wireless networks. We propose a handoff-velocity prediction (HVP) scheme to minimize the paging cost in searching a mobile terminal. HVP is based on the assumptions that the movement behavior of mobile terminals has temporal and spatial properties. Based on handoff statistics the system maintains a handoff graph to describe the movement probabilities of a mobile terminal in a cell to the neighboring cells within a location area. Combining with the velocity information of a mobile terminal we calculate the probabilities of finding the mobile terminal in the cells within the paging area. Then, the paging of the mobile terminal follows the cell probabilities to minimize the paging cost of a mobile terminal. Analysis on HVP has been performed to calculate the optimal threshold for update generation to minimize the total cost in location management. A group paging scheme based on a non-linear programming technique is suggested to limit the paging delay within the quality of services (QoS) requirement in call connection delay and at the same time to minimize the paging cost. In 3G networks and the next generation wireless networks different connection requests may have different QoS requirements in connection delay. Extensive experiments have been performed to investigate the performance characteristics of HVP when compared with the adaptive distance-based (ADB) method, the direction-based location update (DBLU) method and the basic velocity paging (BVP) method under different system settings. The results have shown that HVP gives a better performance when compared with ADB, DBLU and BVP for different call-to-mobility ratio values and update cost to paging cost ratios.

In this correspondence, several errors related to the distributed Bayesian algorithms for fault-tolerant event region detection in wireless sensor networks in (B. Krishnamachari et al., 2004) are spotted and corrected.

In this paper, we study the problem of temporal consistency maintenance where a certain degree of temporal inconsistency is tolerable. We propose a suite of statistical more-less (SML) approaches to tradeoff of quality of service (QoS) of temporal consistency against the number of supported transactions. We begin with a base-line algorithm, SML-BA, which provides the requested QoS of temporal consistency. We then propose SML with optimization (SML-OPT) to further improve the QoS by better utilizing the excessive CPU capacity. Finally, we enhance SML-OPT with a slack reclaiming scheme (SML-SR). The reclaimed slacks are used to process jobs whose required computation time is larger than the guaranteed computation time. Simulation experiments are conducted to compare the performance of these schemes (SML-BA, SML-OPT and SML-SR) together with the deterministic more-less and half-half schemes. Our results show that the SML schemes are effective in trading off the schedulability of transactions and the QoS guaranteed. Moreover, SML-SR performs best and offers a significant QoS improvement over SML-BA and SML-OPT.

IMVS (Intelligent Mobile Video Stream Monitoring System) is a mobile video surveillance system. The objective of IMVS is to design a high performance video stream monitoring system in a mobile computing environment. In particular, the technical questions to be addressed are: (1) how to minimize the amount of video signals to be transmitted between the front-end mobile device and the backend server over the mobile network; and (2) how to divide the jobs to be performed between the front-end and backend processes so that the workload at the front-end mobile device can be maintained within its processing capacity.

In this paper, we study the impacts of checkpointing and write-through procedures, which are critical in maintaining database recoverability and transaction durability, on the performance of a well-known real-time concurrency control protocol, the Read/Write Priority Ceiling Protocol (RWPCP). Although RWPCP can guarantee the schedulability of real-time transactions, it could be unrecoverable, and the priority inversion problems could be unbounded, when transaction commitment is considered. In this paper, we first propose to extend RWPCP with deferred-commitment and extended-locking-period methods to resolve the problems. Then, we study the impacts of different checkpointing granularities and checkpointing methods on the proposed recoverable RWPCP. A detailed simulation study was conducted to evaluate the performance of the recoverable RWPCP with different checkpointing methods under various workloads.

A real-time database system contains base data items which record and model a physical, real-world environment. For better decision support, base data items are summarized and correlated to derive views. These base data and views are accessed by application transactions to generate the ultimate actions taken by the system. As the environment changes, updates are applied to base data, which subsequently trigger view recomputations. There are thus three types of activities: base data update, view recomputation, and transaction execution. In a real-time database system, two timing constraints need to be enforced. We require that transactions meet their deadlines (transaction timeliness) and read fresh data (data timeliness). In this paper, we define the concept of absolute and relative temporal consistency from the perspective of transactions for discrete data objects. We address the important issue of transaction scheduling among the three types of activities such that the two timing requirements can be met. We also discuss how a real-time database system should be designed to enforce different levels of temporal consistency.

We propose an adaptive buffer sensitive (ABS) protocol for scheduling transmission of video streams over a mobile network. Two important considerations in the design of ABS are: (1) to minimize the impact of transient overloading and communication errors on video playback; and (2) to minimize the impact of a video playback on the playback of other video streams. In ABS, the allocation of network bandwidth for serving client requests is divided into two phases. In the first phase, a minimum bandwidth is allocated to serve each request with an aim to minimize the impact of a video request on the performance of other requests. The allocation of bandwidth in the second phase is based on the playback buffer levels of the clients in order to make the system more adaptive to the playback status of individual client. Extensive simulation experiments have been performed to investigate the performance of ABS under different network failure probabilities.

In this paper, we present the Buffer Sensitive Rate-Based (BSRB) algorithm, which provides a fair scheduling scheme to serve video playback requests, while maximizing the performance of individual playback. In BSRB, the amount of bandwidth allocated to serve a video request depends on the buffer level of the requesting client, and the expected and minimum bandwidth requirements of the video. By maintaining a high video buffer level at a client, the quality of the playbacks can be maintained and its performance will be more adaptive to the changing playback conditions. By employing the rate-based policy in BSRB, the performance of the requests is less affected by the poor performance of a single client and hence fair services can be provided to the clients.

Recent advances in mobile computing and mobile communication technology have led to the emergence of many innovative mobile computing applications. Some of them require providing support to location-dependent continuous queries (LDCQs) on moving objects. The result of a location-dependent query depends on the current locations of the moving objects. When the query is specified as continuous, the requesting client can get continuously changing results. In order to provide correct and timely results to requesting clients, the locations of moving objects have to be closely monitored. In this paper, we propose an adaptive monitoring method (AMM) for managing the locations of moving objects to maintain the correctness of the results of query evaluation without significantly increasing the wireless bandwidth requirements. Extensive simulation experiments have been conducted to investigate the performance of the proposed method as compared to plain dead-reckoning (PDR).

An important issue in the design of a mobile computing system is how to manage the real-time locations of mobile clients. In the existing commercial cellular mobile computing systems, a two-tier architecture is used [13]. However, the two-tier architecture is not scalable and is not suitable to the new mobile computing applications. In the literatures [1, 12], a hierarchical database structure is proposed in which the location information of the mobile clients within a cell is managed by the location database responsible for the cell. The location databases of different cells are organized into a tree structure to facilitate the search of mobile clients. Although this architecture can distribute the update and searching workload amongst the location databases in the system, it has the problem of heavy location update overhead and long search delay. Thus, it is not suitable to the system which is supporting real-time queries. In this paper, we study how to generate location update in...

An important mobile application is to provide users information in a real-time fashion over a mobile network, such asthose for news updates and traffic information. The contents of such information are often highly dynamic, and its validity maychange with time rapidly. It is the best benefit of users if the most recent data can be received by users on time. Informationupdates, which capture the most recent status of interested objects in the external environment, must be done continuously andin a real-time fashion to refresh the values of the corresponding data items in the information servers. However, mobilenetworks are often unreliable, and the available bandwidth is usually very limited. If the rate of information update is too high,the total system workload will be very heavy, and, as a result, the completion times of updates and the validity of many dataitems might be seriously affected. On the other hand, if the update rate is low, the uncertainty level of data validity might behigh, and the external consistency cannot be maintained [1]. In addition to the unreliable mobile network, the mobility ofclients complicates the design of a mobile information system. Queries from mobile clients could have some location-dependent properties. For example, the result of a query might depend on the current location of the originating client. Timingconstraints are often implicitly associated with the processing of queries.In this paper, we introduce a system prototype called

Although many efficient concurrency control protocols have been proposed for real-time database systems, they are mainly designed for those systems with a single type of real-time transaction. Due to the very different performance requirements of each type of real-time transaction, these proposed protocols may not be suitable for mixed real-time database systems (MRTDBSs), where different types of real-time transactions, and even non-real-time transactions, may co-exist in the systems at the same time. In this paper, we propose strategies for resolving data conflicts between different types of transactions in a MRTDBS so that their different performance requirements can be achieved and, at the same time, the overall system performance can be improved. The performance of the proposed strategies is evaluated and compared with a real-time optimistic approach. The performance of our proposed conflict resolution methods has also been investigated in a more realistic environment with a limited number of priority levels and disk-resident data items.

This paper proposes a real-time concurrency control protocol called the reduced ceiling protocol (RCP) for real-time database systems consisting of hard and soft real-time transactions. The schedulability of hard real-time transactions can be improved by bounding the blocking time from soft real-time transactions. Different concurrency control strategies are proposed to resolve data conflicts between different combinations of hard and soft real-time transactions, and the properties of the RCP schedules are shown. In the RCP, methodologies are proposed to reduce the number of aborts for soft real-time transactions due to data conflicts with hard real-time transactions. Simulation experiments have been performed to study the performance of the RCP as compared with the optimistic concurrency control with wait 50 (OCC wait-50) under different workloads of soft real-time transactions, various ratios of read/write operations and deadline constraints. It has been found that the RCP can not only guarantee the performance of hard real-time transactions but also reduce the number of deadlines missed by the soft real-time transactions under all situations.

A database system contains base data items which record and model a physical, real world environment. For better decision support, base data items are summarized and correlated to derive views. These base data and views are accessed by application transactions to generate the ultimate actions taken by the system. As the environment changes, updates are applied to the base data, which subsequently trigger view recomputations. There are thus three types of activities: base data update, view recomputation, and transaction execution. In a real-time system, two timing constrains need to be enforced. We require transactions meet their deadlines (transaction timeliness) and read fresh data (data timeliness). In this paper we define the concept of absolute and relative temporal consistency from the perspective of transactions. We address the important issue of transaction scheduling among the three types of activities such that the two timing requirements can be met. We also discuss how a real-time database system should be designed to enforce different levels of temporal consistency.

The paper proposes methodologies to control the access of B-tree-indexed data in a batch and real time fashion. Algorithms are proposed to insert, query, delete, and rebalance B-tree-indexed data based on non real time algorithms (P.M. Kerttu et al., 1996) and the idea of priority inheritance (L. Sha et al., 1990). We propose methodologies to reduce the number of disk I/Os to improve the system performance without introducing more priority inversion. The performance of our methodologies was evaluated by a series of experiments, for which we have some encouraging results.

In a distributed real-time database system (DRTDBS), a commit protocol is required to ensure transaction failure atomicity. If data conflicts occur between executing and committing transactions, the performance of the system may be greatly affected. In this paper, we propose a new protocol, called deadline-driven conflict resolution (DDCR), which integrates concurrency control and transaction commitment management for resolving executing and committing data conflicts amongst firm real-time transactions. With the DDCR, a higher degree of concurrency can be achieved, as many data conflicts of such kind can be alleviated, and executing transactions can access data items which are being held by committing transactions in conflicting modes. Also, the impact of temporary failures which occurred during the commitment of a transaction on other transactions, and the dependencies created due to sharing of data items is much reduced by reversing the dependencies between the transactions. A simulation model has been developed and extensive simulation experiments have been performed to compare the performance of the DDCR with other protocols such as the Opt [1], the Healthy-Opt [2], and the base protocol, which use priority inheritance and blocking to resolve the data conflicts. The simulation results show that the DDCR can significantly improve the system performance under different workload and workload distributions. Its performance is consistently better than the base protocol and the Opt protocols in both main-memory resident and disk-resident DRTDBS.

The use of portable computers with a wireless connection to distributed databases will become as popular as the use of mobile phones in the near future. The rapidly advancing technology in this area has initiated new research areas and challenging research questions. One new area is the support of real-time database systems with a wireless network. The authors have built a model with sufficient details of a wireless distributed real-time database system (WDRTDBS) and have performed simulation experiments to identify the effect of wireless bandwidth, which is one of the most scarce resources in a wireless environment, on the performance of distributed real-time database systems. Through the experiments, they are trying to figure out the criterion for building efficient wireless DRTDBS in terms of performance. The simulation results reveal that the call duration, which may lead to call blocking and prolonged call waiting, impacts on the performance of the DRTDBS in terms of resource contention and transaction deadline missing.

Previous studies, e.g., Haritsa et al. (Haritsa, J.R., Livny, M., Carey, M., 1990. Proceedings of Ninth ACM Symposium on Principles of Database systems) have shown that optimistic concurrency control (OCC) generally performs better than lock-based protocols in disk-based real-time database systems (RTDBS). In this paper we compare the two concurrency control protocols in both disk-based and memory-resident multiprocessor RTDBS. Based on simulation, we analyze the intrinsic behaviors of the two protocols. The result of our performance evaluation experiments show that different characteristics of the two environments indeed have great impact on the protocols' performance. We identify such system characteristics and expose the weaknesses of traditional OCC and lock-based protocols. To improve performance, a new protocol, called Two Phase Locking-Lock Write All (2PL-LW), is proposed. We show that 2PL-LW performs better than the traditional protocols in meeting transaction deadlines in both disk-based and memory-resident RTDBS.

In a distributed real-time database system, if data conflicts occur between executing and committing transactions, the performance can be severely affected. In this paper, we propose an approach, called deadline driven conflict resolution (DDCR), which integrates concurrency control and commitment management in resolving data conflicts between executing and committing transactions, while at the same time maintaining the schedules to be serializable. With DDCR, many of the data conflicts can be alleviated, and concurrent execution of transactions is allowed to access data items being held by committing transactions. The impact of temporary failures occurred during the commitment of a transaction on other transactions is reduced by reversing the dependencies between the transactions. Simulation experiments have been performed and the results show that DDCR can significantly improve the system performance especially when the duration for the voting phase is long.

This paper presents a performance study of ATM networks in the support of real-time MPEG-I video transmission. Multiple classes of MPEG-I are used in the study and what makes this simulation study different from the others is the video data used. These data are captured from real video programmes and we categorized these video clips according to their workload characteristics. The performance of the ATM switch is examined in terms of the cell miss ratio due to deadline missing and the cell loss ratio due to buffer overflow in both the ATM switch as well as the gateways. Moreover, a higher level of abstraction in terms of burst loss ratio is also collected. The results indicate that the first-come-first-serve scheduling algorithm is insufficient to handle real-time traffic. This paper presents a better method to improve the performance significantly especially when the virtual path bandwidth negotiated is conservative.

The design of concurrency control protocols for time-constrained transactions is complicated due to the requirements to maintain the database consistency and to satisfy the timing constraints of the transactions. In the past few years, various real-time locking protocols have been proposed for different real-time database systems (RTDBS). However, the use of these protocols for distributed real-time database (DRTDBS) has received much less attention, even though many RTDBS are distributed in nature. In this paper, two efficient real-time locking protocols are proposed for DRTDBS. The first one, based on dynamic locking, is called Distributed Hybrid Two Phase Locking (DHb2PL). Its performance has been compared in detail with three other distributed real-time locking protocols. The performance results indicate that DHb2PL is much better than the other protocols as a result of a better approach to resolving lock conflicts and its deadlock free property. The second one, called DRT-S2PL, is based on static locking where the locks required by a transaction are assumed to be known before its execution. Its relative performance as compared with DHb2PL is dependent on the proportion of remote locks required by a transaction. DRT-S2PL is more suitable for systems with transactions which have to set a large proportion of remote locks.