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.

Owing to the growing population and rapid urbanization, intersections, where traffic converges from various directions, have become major bottlenecks for road capacity due to frequent congestion. Recent advances in Connected and Autonomous Vehicle (CAV) technology enable signal-free intersections, where CAVs collaborate to cross intersections without collisions. Most existing signal-free intersection control methods focus on accommodating conflicts among vehicles inside the intersection and fixed-direction lanes are commonly adopted. However, the use of fixed-direction lanes is a legacy from conventional signalized intersections, where turning lanes are predetermined and fixed, so as to direct vehicles with different turning intentions to different lanes and avoid collisions. In this paper, we aim to make full utilization of the capacity of signal-free intersections by making use of free-direction lanes, which allow vehicles to make right, straight or left turns from any lane. To this end, we propose a cooperative multi-agent Deep Reinforcement Learning (DRL)-based control method for signal-free intersections with free-direction lanes. Specifically, we first study the problem of cooperatively determining coordination of vehicles inside the intersection and lane changes of vehicles on the incoming arms. Then, a multi-agent DRL-based control method for cooperatively determining coordination and lane-change of vehicles for signal-free intersections with free-direction lanes, named CD-CLC, is proposed for maximizing non-conflicting vehicles crossing the intersection simultaneously while taking vehicle fairness into consideration, to minimize travel delays of vehicles and improve traffic efficiency. Extensive experiments have been conducted to compare CD-CLC with other state-of-the-art methods to demonstrate the effectiveness of the proposed approach.

We propose a new methodology that harnesses recent advancements in AI techniques to formulate an AI-facilitating code learning cycle for students. The approach builds on an existing learning process and innovatively incorporates pair programming into the learning cycle. It first transforms the example code into scaffold code as exercises through an instructor-AI pairing. The scaffold code serves as an exercise for students to complete and debug on a hardware platform iteratively with an expert AI assistant. This design alleviates instructors' burden of crafting new exercises for new scenarios and offers students the advantage of interactive learning with scenario diversity. We evaluate the methodology using a suite of example codes and assess the semantic similarity among different code versions produced by AI assistants. The case study shows promising results of the methodology. We further discuss our findings and outline future work for the proposed methodology.

We propose a new methodology, the Exercise Creation Methodology (ECM), that leverages recent AI technology advancements to create ChatGPT-assisted programming exercises for beginners. ECM takes an existing exercise as input and mutates it by removing some contents into semantically equivalent but syntactically different versions. The pair of versions are labeled as answered correctly and misleadingly by ChatGPT. The removed contents are re-inserted incrementally with further mutation, ensuring the labels remain unchanged. Using the version with the misleading answer and the ChatGPT elaboration on the other version, we construct a ChatGPT-assisted exercise. The latter version may also serve as a solution. We illustrate ECM using a case study.

This paper explores on accelerating Deep Neural Network (DNN) inference with reliability guarantee in Vehicular Edge Computing (VEC) by considering the synergistic impacts of vehicle mobility and Vehicle-to-Vehicle/Infrastructure (V2V/V2I) communications. First, we show the necessity of striking a balance between DNN inference acceleration and reliability in VEC, and give insights into the design rationale by analyzing the features of overlapped DNN partitioning and mobility-aware task offloading. Second, we formulate the Cooperative Partitioning and Offloading (CPO) problem by presenting a cooperative DNN partitioning and offloading scenario, followed by deriving an offloading reliability model and a DNN inference delay model. The CPO is proved as NP-hard. Third, we propose two approximation algorithms, i.e., Submodular Approximation Allocation Algorithm (SA3) and Feed Me the Rest algorithm (FMtR). In particular, SA3 determines the edge allocation in a centralized way, which achieves 1/3-optimal approximation on maximizing the inference reliability. On this basis, FMtR partitions the DNN models and offloads the tasks to the allocated edge nodes in a distributed way, which achieves 1/2-optimal approximation on maximizing the inference reliability. Finally, we build the simulation model and give a comprehensive performance evaluation, which demonstrates the superiority of the proposed solutions.

As an important application of Internet of Things (IoT), Internet of Vehicles (IoVs) can provide various valuable services which may require computation-intensive tasks under strict time constraints. Most traditional vehicles may not be able to process all these computation-intensive tasks locally because of the limitation of computing resources. Therefore, task offloading has been proposed, which allows vehicles to offload computation-intensive tasks to Mobile Edge Computing (MEC) servers. With the arising and development of intelligent vehicles, the concept of Vehicle as a Resource (VaaR) has been proposed as an important supplement to MEC, which enables intelligent vehicles to share computation resources with nearby vehicles. Most studies in VaaR generally assume that the transmission data rate of offloading tasks from one vehicle to another is fixed. However, in VaaR, due to the high mobility of vehicles, the communication distance between vehicles may change over time, resulting in changing data rate. Therefore, it is challenging to make offloading decisions (i.e., selecting proper vehicles as computation resource providers) while considering adaptive data rate. In this paper, we study task offloading in vehicular networks while considering adaptive data rate. We propose an Adaptive Data Rate-based Offloading algorithm named ADRO, which can not only achieve minimum energy consumption while satisfying time constraints, but also take adaptive data rate into consideration. Comprehensive experiments have been conducted to demonstrate the efficiency of the ADRO algorithm.

For ecological protection of the ocean, biologists usually conduct line-transect vessel surveys to measure sea species’ population density within their habitat (such as dolphins). However, sea species observation via vessel surveys consumes a lot of manpower resources and is more challenging compared to observing common objects, due to the scarcity of the object in the wild, tiny-size of the objects, and similar-sized distracter objects (e.g., floating trash). To reduce the human experts’ workload and improve the observation accuracy, in this paper, we develop a practical system to detect Chinese White Dolphins in the wild automatically. First, we construct a dataset named Dolphin-14k with more than 2.6k dolphin instances. To improve the dataset annotation efficiency caused by the rarity of dolphins, we design an interactive dolphin box annotation strategy to annotate sparse dolphin instances in long videos efficiently. Second, we compare the performance and efficiency of three off-the-shelf object detection algorithms, including Faster-RCNN, FCOS, and YoloV5, on the Dolphin-14k dataset and pick YoloV5 as the detector, where a new category (Distracter) is added to the model training to reject the false positives. Finally, we incorporate the dolphin detector into a system prototype, which detects dolphins in video frames at 100.99 FPS per GPU with high accuracy (i.e., 90.95 [email protected]).

Many recent works utilize scheduling to minimize the Flow Completion Time (FCT) in Data Center Networks (DCN), like PIAS using Shortest Job First (SJF) scheduling and pFabric using Shortest Remaining Size First (SRSF) scheduling. However, they only consider the flow size information, without consideration of available bandwidth of the network, leading to inferior performance when the network is congested. Besides, information on flow size is hard to obtain in practice. Moreover, although a centralized scheduler may have optimal scheduling decisions, it suffers from high system overhead. Therefore, a new DCN scheme is expected which is deployment-friendly and implements SRTF scheduling in a distributed manner. In this paper, we propose D-SRTF, a light-weight yet effective DCN scheme to implement SRTF scheduling. D-SRTF determines the remaining time of each flow according to the estimated remaining flow size and the available bandwidth, in order to determine the priority of each flow. Switches perform Strict Priority (SP) scheduling according to the priority of each flow, in order to realize SRTF scheduling. Experiments show that D-SRTF performs better than the currently best implementable scheme, PIAS, and could perform better than pFabric if information on flow size is available.

This paper makes the first effort on proposing a fog computing empowered architecture together with a dedicated scheduling algorithm for data dissemination in software defined heterogeneous vehicular ad-hoc networks (VANETs). Specifically, the architecture supports both the logically centralized control via the cloud node in the core network and the distributed data dissemination via the fog nodes at the network edge. A problem calledfog assisted cooperative service(FACS) is formulated, which takes network coding and vehicular caching into consideration, and aims at minimizing the overall service delay via the cooperation of vehicle-to-cloud (V2C), vehicle-to-fog (V2F) and vehicle-to-vehicle (V2V) communications. Further, we derive an equivalence problem of FACS and prove that FACS is NP-hard. On this basis, we propose a Clique Searching based Scheduling (CSS) algorithm at the SDN controller, which considers the heterogeneous communication interfaces and vehicle mobility in scheduling, and enables the collaborative data encoding and transmission among the cloud, fog nodes and vehicles. The complexity analysis demonstrates the feasibility of the proposed algorithm. Finally, we build the simulation model and give a comprehensive performance evaluation based on real vehicular trajectories extracted from different time and space. The simulation results conclusively demonstrate the superiority of the proposed solution.

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.

Although indoor localization has been studied over a decade, it is still challenging to enable many IoT applications, such as activity tracking and monitoring in smart home and customer navigation and trajectory mining in smart shopping mall, which typically require meter-level localization accuracy in a highly dynamic and large-scale indoor environment. Therefore, this article aims at designing and implementing an adaptive and scalable indoor tracking system in a cost-effective way. First, we propose a zero site-survey overhead (ZSSO) algorithm to enhance the system scalability. It integrates the step information and map constraints to infer user's positions based on the particle filter and supports the auto labeling of scanned Wi-Fi signal for constructing the fingerprint database without the extra site-survey overhead. Further, we propose an iterative-weight-update (IWU) strategy for ZSSO to enhance system robustness and make it more adaptive to the dynamic changing of environments. Specifically, a two-step clustering mechanism is proposed to delete outliers in the fingerprint database and alleviate the mismatch between the auto-tagged coordinates and the corresponding signal features. Then, an iterative fingerprint update mechanism is designed to continuously evaluate the Wi-Fi fingerprint localization results during online tracking, which will further refine the fingerprint database. Finally, we implement the indoor tracking system in real-world environments and conduct a comprehensive performance evaluation. The field testing results conclusively demonstrate the scalability and effectiveness of the proposed algorithms.

With the recent development of wireless communication, sensing, and computing technologies, Internet of Vehicles (IoV) has attracted great attention in both academia and industry. Nevertheless, it is challenging to process time-critical tasks due to unique characteristics of IoV, including heterogeneous computation and communication capacities of network nodes, intermittent wireless connections, unevenly distributed workload, massive data transmission, intensive computation demands, and high mobility of vehicles. In this article, we propose a two-layer vehicular fog computing (VFC) architecture to explore the synergistic effect of the cloud, the static fog, and the mobile fog on processing time-critical tasks in IoV. Then, we give a motivational case study by implementing a prototype of a traffic abnormity detection and warning system, which demonstrates the necessity and urgency of developing adaptive task offloading mechanisms in such a scenario and gives insight into the problem formulation. Furthermore, we formulate the offloading model, aiming at maximizing the completion ratio of time-critical tasks. On this basis, we propose an adaptive task offloading algorithm (ATOA). Specifically, it adaptively categorizes all tasks into four types of pending lists by considering the dynamic requirements and resource constraints, and then tasks in each list will be cooperatively offloaded to different nodes based on their features. Finally, we build the simulation model and give a comprehensive performance evaluation. The results demonstrate the superiority of ATOA.

Mobile edge computing (MEC) has been an emerging paradigm to support low-latency applications in vehicular networks by offloading resources at network edge. However, it is still challenging to apply MEC- based architecture to implement multimedia services due to varying wireless communication, high vehicle mobility and heterogeneous resource integration. In this paper, we investigate adaptive-bitrate (ABR)-based multimedia services (MS) in MEC-based vehicular networks, where each multimedia file is divided into multiple chunks and can be requested at different bitrate levels. Further, MEC servers can satisfy local vehicular requests by integrating heterogeneous cache and communication resources. Based on the above observation, we formulate joint resource optimization (JSO) problem by synthesizing cache placement, wireless bandwidth allocation and chunk quality adaptation. On this basis, we propose a reinforcement- learning-based cache placement (RLCP) algorithm, which determines the optimal offloaded chunks by learning the global knowledge of cache reward in an iterative way. Further, we design an adaptive-quality- based chunk selection (AQCS) algorithm, which can be adaptive to time-varying wireless channel by dynamically adjusting bandwidth allocation and quality level based on real-time service workload. Lastly, we build the simulation model and conduct an extensive performance evaluation, which demonstrates the superiority of proposed algorithms.

Mobile edge computing (MEC) is an emerging paradigm to offload the server-side resources closer to the mobile terminals compared with cloud-based computing. However, due to highly vehicular mobility and limited wireless coverage, it is challenging to apply off-the-shelf MEC-based architecture to support the real-time services in vehicular networks, especially when the vehicle density changes dynamically. Hence, this paper investigates a novel service scenario in an MEC-based architecture, where the local MEC server has to complete the real-time services of mobile vehicles in its service range. On this basis, we formulate a novel problem of distributed real-time service scheduling (DRSS) by comprehensively considering the delay requirements of real-time services, the heterogeneous computing capabilities of MEC servers and the mobility features of vehicles, which targets at maximizing the service ratio. To resolve such an issue, we propose a multi-agent reinforcement learning algorithm called Utility-based Learning (UL), in which each local MEC server selects the optimal solution by learning the global knowledge online. Specifically, a utility table is established to determine the optimal solution by estimating the pending delay of service request at each MEC server and it will be updated periodically based on the feedback signal from the assigned MEC server. Lastly, we build the simulation model and conduct an extensive performance evaluation, which demonstrates the superiority of the proposed algorithm.

Heterogeneous network integration is a promising technique to support efficient data services in vehicular networks. However, due to highly dynamics of vehicular mobility and heterogeneous performance of wireless interfaces, it is still challenging to design an efficient scheduling policy for information services in vehicular networks. In this paper, we propose a centralized service architecture for managing heterogeneous network resources. Particularly, we comprehensively investigate the heterogeneity of networks, as well as the diversity of service requests. On this basis, we formulate the heterogeneous network resource management (HNRM) problem as a multiple-objective problem, which aims at minimizing both the service delay and the network access cost simultaneously. Then, we propose a packet-encoding based multi-objective algorithm (PEMA), which consists of two components: packet encoding for data broadcast and multiobjective algorithm for network interface selection. Specifically, for improving bandwidth efficiency, we develop a multiple-packet encoding (MPE) technique to serve more requests simultaneously. For network selection, we propose a multi-objective evolutionary mechanism to further minimize both the service delay and the network access cost via population evolution. Finally, we give a comprehensive performance evaluation to demonstrate the superiority of PEMA under a wide range of scenarios.

With recent advances in wireless communications, vehicular networks have attracted great interests in both industry and academia. This work aims at proposing a novel vehicular fog computing paradigm including both the system architecture and the scheduling algorithm. Specifically, we present a hierarchical architecture, which integrates the paradigm of both fog computing and the software defined networking (SDN). Then, we formulate a novel problem called Cooperative Service in Vehicular Fog Computing (CS-VFC), which aims at maximizing the bandwidth efficiency by coordinating the service in both the fog layer and the cloud layer. We prove that CS-VFC is NP-hard. On this basis, we propose an on-line scheduling algorithm, which incorporates with the network coding and makes scheduling decisions at SDN controller. In particular, it will determine the coding policy for each cloud node, and then it will implement both the intra and inter cooperation strategies at the fog layer. Finally, we build the simulation model by implementing NS3 simulator and SUMO. A comprehensive simulation is carried out to demonstrate the superiority of the proposed system architecture and the solution.

Heterogeneous network resources are expected to cooperate with each other to support temporal data services in vehicular networks. However, it is challenging to implement an efficient data scheduling strategy due to the following factors: first, there are different time constraints on services, which are imposed by the application requirements of both temporal data quality and transmission delay; second, the heterogeneity of wireless interfaces further complicates the transmission task assignment in dynamic vehicular environments. Therefore, this paper proposes an software-defined network-based architecture to enable unified management on heterogeneous network resources. Then, we formulate the cooperative temporal data dissemination (CTDD) problem by considering the property of temporal data, the heterogeneity of wireless interfaces, and the delay constraints on service requests. Further, we prove the NP-hardness of the CTDD by constructing a polynomial-time reduction from a well know NP-hard problem, classical knapsack problem. On this basis, we design a heuristic algorithm called priority-based task assignment (PTA), which synthesizes dynamic task assignment, broadcast efficiency, and service deadline into priority design. Accordingly, PTA is able to adaptively distribute broadcast tasks of each request among multiple interfaces, so as to improve overall system performance. Last but not least, we build the simulation model and implement the proposed algorithm. The comprehensive simulation results show the superiority of the proposed algorithm under a wide range of scenarios.

Temporal information services are critical in implementing emerging intelligent transportation systems. Nevertheless, it is challenging to realize timely temporal data update and dissemination due to an intermittent wireless connection and a limited communication bandwidth in dynamic vehicular networks. Some previous studies have considered the temporal data dissemination in vehicular networks, but they are limited to the service region, which is inside the coverage of roadside units. To enhance system scalability, it is imperative to exploit the synergic effect of vehicle-to-infrastructure (V2I) and vehicle-to-vehicle (V2V) communications for providing efficient temporal information services in such an environment. With the above motivations, we propose a novel system architecture to enable efficient data scheduling in hybrid V2I/V2V communications by having the global knowledge of network resources of the system. On this basis, we formulate a temporal data upload and dissemination (TDUD) problem, aiming at optimizing two conflict objectives simultaneously, which are enhancing the data quality and improving the delivery ratio. Furthermore, we propose an evolutionary multi-objective algorithm calledMO-TDUD, which consists of a decomposition scheme for handling multiple objectives, a scalable chromosome representation forTDUDsolution encoding, and an evolutionary operator designed forTDUDsolution reproduction. The proposedMO-TDUDcan be adaptive to different requirements on data quality and delivery ratio by selecting the best solution from the derived Pareto solutions. Last but not least, we build the simulation model and implementMO-TDUDfor performance evaluation. The comprehensive simulation results demonstrate the superiority of the proposed solution.

The vehicular sensor network (VSN) technology empowers intelligent transportation systems (ITSs) to support a wide range of road safety and traffic management applications. By taking advantage of the information collection and communication capabilities offered by VSNs, information, such as speed, travel time, dash-camera video, and so on, can be gathered from sensors embedded in vehicles and then delivered to the infrastructure to support ITS applications. The explosive growth in the availability and variety of sensor instruments as well as the number of vehicles provides us with the opportunity to create large-scale ITS applications, which demand large-scale data processing. In order to support large-scale data processing, Google proposed the MapReduce framework. The MapReduce framework provides scalability in a large-scale data cluster by performing aggregate computations as close to the data source as possible. However, supporting ITS applications over VSN is not just a matter of simply applying the existing MapReduce framework to VSN due to the limited wireless bandwidth and the highly dynamic network topology. In this paper, we propose an analytical processing framework for VSNs called Vehdoop. Vehdoop utilizes the computing capability of vehicles to efficiently process sensor data in parallel across a large number of vehicles in a decentralized manner. We conducted extensive experiments using vehicle trajectories generated from Simulation of Urban MObility (SUMO) and a network simulator, NS-3, to simulate vehicle-to-vehicle and vehicle-to-infrastructure communications. The experimental results demonstrate the superiority of Vehdoop.

With the advent of various mobile Internet applications and social network services, the demand for Internet access from traveling vehicles has largely increased. In view of the ability to provide cost-effective Internet access, the Drive-thru Internet system, where road-side Access Points (APs) enable vehicular users to obtain temporary Internet connection as the vehicle passes through, is drawing dramatic attention. In this paper, we propose an analytical model to evaluate the performance of an uplink Drive-thru Internet system in the real channel conditions. The proposed analytical model accurately quantifies the performance metrics of an uplink Drive-thru Internet in terms of a number of system parameters.

This work aims at proposing a transfer learning (TL)-based framework to enhance system scalability of fingerprint-based indoor localization by reducing offline training overhead without jeopardizing the localization accuracy. The basic principle is to reshape data distributions in the target domain based on the transferred knowledge from the source domains, so that those data belonging to the same cluster will be logically closer to each other, whereas others will be further apart from each other. Specifically, the TL-based framework consists of two parts, metric learning and metric transfer, which are used to learn the distance metrics from source domains and identify the most suitable metric for the target domain, respectively. Furthermore, this work implements a prototype of the fingerprint-based indoor localization system with the proposed TL-based framework embedded. Finally, extensive real-world experiments are conducted to demonstrate the effectiveness and the generality of the TL-based framework.

This paper embarks the first study on exploiting the synergy between vehicular caching and network coding for enhancing the bandwidth efficiency of data broadcasting in heterogeneous vehicular networks by presenting a service architecture that exercises the software defined network concept. In particular, we consider the scenario where vehicles request a set of information and they could be served via heterogeneous wireless interfaces, such as roadside units and base stations (BSs). We formulate a novel problem of coding-assisted broadcast scheduling (CBS), aiming at maximizing the broadcast efficiency for the limited BS bandwidth by exploring the synergistic effect between vehicular caching and network coding. We prove the NP-hardness of the CBS problem by constructing a polynomial-time reduction from the simultaneous matrix completion problem. To efficiently solve the CBS problem, we employ memetic computing, which is a nature inspired computational paradigm for tackling complex problems. Specifically, we propose a memetic algorithm, which consists of a binary vector representation for encoding solutions, a fitness function for solution evaluation, a set of operators for offspring generation, a local search method for solution enhancement, and a repair operator for fixing infeasible solutions. Finally, we build the simulation model and give a comprehensive performance evaluation to demonstrate the superiority of the proposed solution.

Efficient data dissemination is critical for enabling emerging applications in vehicular ad hoc networks. As a typical traffic scenario, the bidirectional road scenario of highways bring unique challenges on well exploiting the benefit of vehicle-to-vehicle (V2V) communication for data sharing among vehicles driving in opposite directions. This paper is dedicated to investigating the characteristics of data services in such a scenario and exploring new opportunities for enhancing overall system performance. Specifically, we present a system architecture to enable the road-side unit assisted data scheduling via vehicle-to-infrastructure communication. Then, we give a theoretical analysis on the opportunity of successful data sharing among vehicles driving in opposite directions based on the analysis of signal-to-interference-noise-ratio of V2V communication. On this basis, we propose a clustering mechanism based on the design of a time division policy and the derivation of the optimal cluster length. In addition, a cluster association strategy is designed to enable vehicles to dynamically join or leave a cluster based on their real-time velocities. Furthermore, a two-phase backoff mechanism is designed for distributed data sharing based on V2V communication, and a cooperative scheduling algorithm is proposed for selecting sender vehicles as well as the corresponding data items for broadcasting. Finally, we build the simulation model and give a comprehensive simulation study, which demonstrates that the proposed solutions can effectively improve the overall system performance.

Utilizing large-scale GPS data to improve taxi services has become a popular research problem in the areas of data mining, intelligent transportation, geographical information systems, and the Internet of Things. In this paper, we utilize a large-scale GPS data set generated by over 7,000 taxis in a period of one month in Nanjing, China, and propose TaxiRec: a framework for evaluating and discovering the passenger-finding potentials of road clusters, which is incorporated into a recommender system for taxi drivers to seek passengers. In TaxiRec, the underlying road network is first segmented into a number of road clusters, a set of features for each road cluster is extracted from real-life data sets, and then a ranking-based extreme learning machine (ELM) model is proposed to evaluate the passenger-finding potential of each road cluster. In addition, TaxiRec can use this model with a training cluster selection algorithm to provide road cluster recommendations when taxi trajectory data is incomplete or unavailable. Experimental results demonstrate the feasibility and effectiveness of TaxiRec.

With recent advances in wireless communications, vehicular networks are envisioned as a promising paradigm on achieving breakthroughs in transportation safety, efficiency, and sustainability. This work investigates data broadcast via Infrastructure-to-Vehicle (I2V) communication by exploiting the vehicular caching and network coding for enhancing bandwidth efficiency of the road-side unit (RSU). Specifically, we present an architecture for providing real-time data services via I2V communication in the service range of a RSU. Then, we investigate the problem of cache-aided data dissemination with network coding and prove that it is NP-hard. Further, we propose a memetic algorithm, which consists of a binary vector representation for encoding solutions, a fitness function for solution evaluation, a set of operators for offspring generation, a local search method for solution enhancement and a repair operator for fixing infeasible solutions. Finally, we build the simulation model and give a comprehensive performance evaluation to demonstrate the superiority of the proposed solution.

Barrier coverage with wireless sensors aims at detecting intruders who attempt to cross a specific area, where wireless sensors are distributed remotely at random. This paper considers limited-power sensors with adjustable ranges deployed along a linear domain to form a barrier to detect intruding incidents. We introduce three objectives to minimize: 1) total power consumption while satisfying full coverage; 2) the number of active sensors to improve the reliability; and 3) the active sensor nodes' maximum sensing range to maintain fairness. We refer to the problem as the tradeoff barrier coverage (TBC) problem. With the aim of obtaining a better tradeoff among the three objectives, we present a multiobjective optimization framework based on multiobjective evolutionary algorithm (MOEA)/D, which is called problem specific MOEA/D (PS-MOEA/D). Specifically, we define a 2-tuple encoding scheme and introduce a cover-shrink algorithm to produce feasible and relatively optimal solutions. Subsequently, we incorporate problem-specific knowledge into local search, which allows search procedures for neighboring subproblems collaborate each other. By considering the problem characteristics, we analyze the complexity and incorporate a strategy of computational resource allocation into our algorithm. We validate our approach by comparing with four competitors through several most-used metrics. The experimental results demonstrate that PS-MOEA/D is effective and outperforms the four competitors in all the cases, which indicates that our approach is promising in dealing with TBC.

Automated analysis and assessment of students' programs, typically implemented in automated program assessment systems (APASs), are very helpful to both students and instructors in modern day computer programming classes. The mainstream of APASs employs a black-box testing approach which compares students' program outputs with instructor-prepared outputs. A common weakness of existing APASs is their inflexibility and limited capability to deal with admissible output variants, that is, outputs produced by acceptable correct programs that differ from the instructor's. This paper proposes a more robust framework for automatically modelling and analysing student program output variations based on a novel hierarchical program output structure called HiPOS. Our framework assesses student programs by means of a set of matching rules tagged to the HiPOS, which produces a better verdict of correctness. We also demonstrate the capability of our framework by means of a pilot case study using real student programs.

Most of current Data Center Network (DCN) protocols leverage Explicit Congestion Notification (ECN) for congestion control. However, the majority of them assume single-queue scenario in each switch port, making their performance inferior in multiple-queue scenario. MQECN [1] solves this problem by periodically measuring the round time of queue scheduling, calculating a threshold for individual queue based on its weight and the measured round time, and adopting standard ECN in each queue. However, MQECN incurs non-negligible overhead for frequent round time measurement, and inaccurate round time measurement is unavoidable. To this end, we propose DEME, a light-weight DCN scheme for multiple-queue scenario with no need for round time measurement or per queue threshold setting. The core idea of DEME is to decouple packet marking from enqueuing, which means, when a packet is enqueued and the total queue length exceeds the standard threshold, instead of marking this newly arrived packet, we mark the head packet of the queue whose length exceeds its fair share the most. Experiments show that our light-weight DEME has similar performance with MQECN in terms of average Flow Completion Time and guarantees the fairness.

Real-time and temporal information services are intrinsic characteristics in vehicular networks, where the timeliness of data dissemination and the maintenance of data quality interplay with each other and influence overall system performance. In this work, we present the system architecture where multiple road side units (RSUs) are cooperated to provide information services, and the vehicles can upload up-to-date information to RSUs via vehicle-to-infrastructure (V2I) communication. On this basis, we formulate the distributed temporal data management (DTDM) problem as a two-objective problem, which aims to enhance overall system performance on both the service quality and the service ratio simultaneously. Further, we propose a multiobjective evolutionary algorithm called MO-DTDM to obtain a set of pareto solutions and analyze how to fulfill given requirements on system performance with obtained pareto solutions. Finally, we build the simulation model and give a comprehensive performance evaluation, which demonstrates the superiority of the proposed optimization method.

Recent advances in autonomous vehicles and vehicular communications are envisioned to enable novel approaches to managing and controlling traffic intersections. In particular, with intersection controller units (ICUs), passing vehicles can be instructed to cross the intersection safely without traffic signals. Previous efforts on autonomous intersection control mainly focused on guaranteeing the safe passage of vehicles and improving intersection throughput, without considering the quality of the travel experience from the passengers' perspective. In this paper, we aim to design an enhanced autonomous intersection control mechanism, which not only ensures vehicle safety and enhances traffic efficiency but also cares about the travel experience of passengers. In particular, we design the metric of smoothness to quantitatively capture the quality of experience. In addition, we consider the travel time of individual vehicles when passing the intersection in scheduling to avoid a long delay of some vehicles, which not only helps with improving intersection throughput but also enhances the system's fairness. With the above considerations, we formulate the intersection control model and transform it into a convex optimization problem. On this basis, we propose a new algorithm to achieve an optimal solution with low overhead. Finally, we build the simulation model and implement the algorithm for performance evaluation. Comprehensive simulation results demonstrate the superiority of the proposed algorithm.

Vehicle-to-vehicle/vehicle-to-infrastructure (referred to as V2X) communications have potential to revolutionize current road transportation systems with respect to vehicle safety, transportation efficiency, and travel experience. This paper puts the first effort on applying network coding in cooperative V2X communication environments to improve bandwidth efficiency and enhance data service performance. Specifically, we investigate new arising challenges on network-coding-assisted data dissemination by considering both communication constraints and application requirements in vehicular networks. We present the system model and give an insight into the characteristics of cooperative data dissemination with network coding. On this basis, we formulate the problem and propose a network-coding-assisted scheduling algorithm to enable the hybrid of vehicle-to-vehicle (V2V) and vehicle-to-infrastructure (V2I) communications and exploit their joint effects on providing efficient data services. We design a cache strategy that allows vehicles to retrieve their unrequested data items. This strategy not only increases the opportunity of data sharing among vehicles but also gives higher probability of packet decoding, which in turn enhances the data service performance. We give an intensive analysis on the scheduling overhead, which shows the scalability of the algorithm. Finally, we build the simulation model and conduct a comprehensive performance evaluation to demonstrate the superiority of the proposed solution.

This paper presents the first study on scheduling for cooperative data dissemination in a hybrid infrastructure-to-vehicle (I2V) and vehicle-to-vehicle (V2V) communication environment. We formulate the novel problem of cooperative data scheduling (CDS). Each vehicle informs the road-side unit (RSU) the list of its current neighboring vehicles and the identifiers of the retrieved and newly requested data. The RSU then selects sender and receiver vehicles and corresponding data for V2V communication, while it simultaneously broadcasts a data item to vehicles that are instructed to tune into the I2V channel. The goal is to maximize the number of vehicles that retrieve their requested data. We prove that CDS is NP-hard by constructing a polynomial-time reduction from the Maximum Weighted Independent Set (MWIS) problem. Scheduling decisions are made by transforming CDS to MWIS and using a greedy method to approximately solve MWIS. We build a simulation model based on realistic traffic and communication characteristics and demonstrate the superiority and scalability of the proposed solution. The proposed model and solution, which are based on the centralized scheduler at the RSU, represent the first known vehicular ad hoc network (VANET) implementation of software defined network (SDN) concept.

Utilizing large-scale GPS data to improve taxi services becomes a popular research problem in the areas of data mining, intelligent transportation, and the Internet of Things. In this paper, we utilize a large-scale GPS data set generated by over 7,000 taxis in a period of one month in Nanjing, China, and propose TaxiRec; a framework for discovering the passenger-finding potentials of road clusters, which is incorporated into a recommender system for taxi drivers to hunt passengers. In TaxiRec, we first construct the road network by defining the nodes and road segments. Then, the road network is divided into a number of road clusters through a clustering process on the mid points of the road segments. Afterwards, a set of features for each road cluster is extracted from real-life data sets, and a ranking-based extreme learning machine (ELM) model is proposed to evaluate the passenger-finding potential of each road cluster. Experimental results demonstrate the feasibility and effectiveness of the proposed framework.

BACKGROUND: Epidermal growth factor receptor (EGFR) mutation-induced drug resistance has caused great difficulties in the treatment of non-small-cell lung cancer (NSCLC). However, structural information is available for just a few EGFR mutants. In this study, we created an EGFR Mutant Structural Database (freely available at http://bcc.ee.cityu.edu.hk/data/EGFR.html ), including the 3D EGFR mutant structures and their corresponding binding free energies with two commonly used inhibitors (gefitinib and erlotinib). RESULTS: We collected the information of 942 NSCLC patients belonging to 112 mutation types. These mutation types are divided into five groups (insertion, deletion, duplication, modification and substitution), and substitution accounts for 61.61% of the mutation types and 54.14% of all the patients. Among all the 942 patients, 388 cases experienced a mutation at residue site 858 with leucine replaced by arginine (L858R), making it the most common mutation type. Moreover, 36 (32.14%) mutation types occur at exon 19, and 419 (44.48%) patients carried a mutation at exon 21. In this study, we predicted the EGFR mutant structures using Rosetta with the collected mutation types. In addition, Amber was employed to refine the structures followed by calculating the binding free energies of mutant-drug complexes. CONCLUSIONS: The EGFR Mutant Structural Database provides resources of 3D structures and the binding affinity with inhibitors, which can be used by other researchers to study NSCLC further and by medical doctors as reference for NSCLC treatment.

Location-based business review (LBBR) sites (e.g., Yelp) provide us a possibility to recommend new points of interest (POIs) for users. The geographical position and category of POIs have been considered as two major factors in modeling users' preferences. However, it is argued that the user's visiting behaviors are also affected by the attributes of POIs, which reflect the basic features of the POIs. Besides, a user may have different preference levels on the same POI with regard to different criteria. To this end, we propose a new personalized POI recommendation framework using Multi-Criteria Decision Making (MCDM). Firstly, preference models are built for the user's geographical, category, and attribute preferences. Then, an MCDM-based recommendation framework is designed to iteratively combine the user's preferences on the three criteria and select the top-N POIs as a recommendation list. Experimental results show that our framework not only outperforms the state-of-the-art POI recommendation techniques, but also provides a better trade-off mechanism for MCDM than the weighted sum approach.

Exploring massive mobile data for location-based services (LBS) becomes one of the key challenges in mobile data mining. In this paper, we propose a framework that uses large-scale cell tower data dumps and extracts points-of-interest (POIs) from a social network web site called Weibo, and provides new LBS based on these two data sets, i.e., predicting the existence of POIs and the number of POIs in a certain area. We use Voronoi diagram to divide a city area into non-overlapping regions, and a k-means clustering algorithm to aggregate neighboring cell towers into region groups. A supervised learning algorithm is adopted to build up a model between the number of connections of cell towers and the POIs in different region groups, where a classification or regression model is used to predict the POI existence or the number of POIs, respectively. We studied 12 state-of-the-art classification and regression algorithms, and the experimental results demonstrate the feasibility and effectiveness of the proposed framework.

Converge cast is a critical communication paradigm for data collection in wireless sensor networks, where both energy and bandwidth are scarce resources. Previous converge cast algorithms only focused on minimizing the energy cost without considering the constraint of wireless bandwidth. This article shows that constructing a congestion-free converge cast tree cannot ignore the bandwidth constraint. Considering the adjustable transmission power of sensor nodes, it will affect not only the topology of networks but also the bandwidth of wireless links. In this paper, we formulate the Minimum Total Transmission Power (MTTP) problem, which aims to address the issue of constructing a congestion-free converge cast tree in WSNs with adjustable transmission power of sensor nodes. We transform MTTP to an Integer Linear Programming (ILP) model, by which the optimal solution to MTTP is derived. To strike a balance between scheduling overhead and system performance, we propose a heuristic algorithm called Nearest-to-Sink, which searches viable paths in a greedy way and achieves near optimal performance. We build the simulation model and give a comprehensive performance evaluation, which demonstrates the feasibility and the effectiveness of the proposed algorithm.

Recent advances in infrastructure-to-vehicle (I2V) and vehicle-to-vehicle (V2V) communications are envisioned to enable a variety of emerging applications in vehicular networks, where it is imperative to provide efficient data services via cooperative vehicular communications. In this work, we present the data dissemination system via cooperative I2V and V2V communications. We formulate the problem by investigating both the communication constraint and the application requirement on data dissemination. The goal is to maximize the system performance by exploiting the joint effects of I2V and V2V communications. On this basis, we propose an on-line scheduling algorithm to enable scalable, fair and robust data dissemination. The algorithm makes scheduling decisions by transforming the data dissemination problem to the maximum weighted independent set (MWIS) problem and approximately solving MWIS using a greedy method. We build the simulation model based on realistic traffic and communication characteristics. A comprehensive simulation study demonstrates that the proposed solution is able to effectively strike a balance between I2V and V2V data services and maximize system performance in terms of scalability, fairness and robustness.

Timely and efficient data dissemination is one of the fundamental requirements to enable innovative applications in vehicular cyber-physical systems (VCPS). In this work, we intensively analyze the characteristics of temporal data dissemination in VCPS. On this basis, we formulate the static and dynamic snapshot consistency requirements on serving real-time requests for temporal data items. Two online algorithms are proposed to enhance the system performance with different requirements. In particular, a reschedule mechanism is developed to make the scheduling adaptable to the dynamic snapshot consistency requirement. A comprehensive performance evaluation demonstrates the superiority of the proposed algorithms.

Efficient data dissemination is one of the fundamental requirements to enable emerging applications in vehicular cyber-physical systems. In this paper, we present the first study on real-time data services via roadside-to-vehicle communication by considering both the time constraint of data dissemination and the freshness of data items. Passing vehicles can submit their requests to the server, and the server disseminates data items accordingly to serve the vehicles within its coverage. Data items maintained in the database are periodically updated to keep the information up-to-date. We present the system model and analyze challenges on data dissemination by considering both application requirements and communication characteristics. On this basis, we formulate the temporal data dissemination (TDD) problem by introducing the snapshot consistency requirement on serving real-time requests for temporal data items. We prove that TDD is NP-hard by constructing a polynomial-time reduction from the Clique problem. Based on the analysis of the time bound on serving requests, we propose a heuristic scheduling algorithm, which considers the request characteristics of productivity, status, and urgency in scheduling. An extensive performance evaluation demonstrates that the proposed algorithm is able to effectively exploit the broadcast effect, improve the bandwidth efficiency, and enhance the request service chance.

Mutations in EGFR kinase domain can cause non-small-cell lung cancer, which is one of the most lethal diseases in the world. However, current therapy is limited by the drug resistance effect in different EGFR mutants. There is an urgent demand for developing computational methods to predict drug resisted mutations. In this study, we use quantum mechanics and molecular mechanics models to generate EGFR mutants, and apply molecular dynamic to simulate EGFR-drug interactions. Hydrogen bonds and binding free energy are used to reveal the underlying principle of drug resistance in EGFR. The results show that drug resisted mutants do not establish hydrogen bond between the drug and the protein molecule while having large binding free energy. These properties can be used to predict resistance to anti-EGFR drugs due to protein mutations.

Recent advances in wireless communication technologies have spawned many new applications in vehicular networks. Data dissemination via roadside-to-vehicle communication is a vital approach to enabling most of these applications. In this work, we investigate in the scenario where data items are broadcasted from the road-side unit (RSU) in response to requests submitted by passing vehicles. Data items are associated with temporal constraints and updated periodically to reflect dynamic states of traffic information. Each request may ask for multiple temporal data items, and it is associated with a deadline, which may either be specified by the driver or imposed by the time when the vehicle drives through the service region. In particular, we develop a real-time data dissemination model based on roadside-to-vehicle communication by formulating the time-constraint of requests and the consistency requirement of retrieving temporal data items. On this basis, we propose an online scheduling algorithm to enhance the system performance in terms of maximizing request service and improving bandwidth utilization. Lastly, we build a simulation model to evaluate the algorithm performance in a variety of situations. Experimental results demonstrate that the proposed algorithm outperforms existing algorithms significantly in both request serving and bandwidth utilization.

Deriving deadlines and periods for update transactions so as to maintain timeliness and data freshness while minimizing imposed workload has long been recognized an important problem in real-time database research. Despite years of active research, the state-of-the-art still has much room for improvement, particularly for periodic transactions scheduled by the Earliest Deadline First (EDF) algorithm. In this paper, we propose a practical and efficient two-phase algorithm, GEneral EDF (GEEDF), for assigning periods and deadlines to EDF-scheduled update transactions. Phase 1 of GEEDFaims at finding solutions for most inputs in linear time, based on the observation that the execution times of update transactions are relatively small compared to the validity interval lengths of real-time data objects in many real-time applications. In the remaining cases for which Phase 1 fails to derive solutions, Phase 2 is invoked by employing an existing deadline-monotonic-based algorithm, which we show is also applicable to our problem. Meanwhile, we have devised several techniques which significantly reduce the cost of schedulability test, and hence greatly improve time efficiency. Our experimental results demonstrate that GEEDFoutperforms existing approaches in terms of generated workloads. Although Phase 2 has a pseudopolynomial time complexity, our experimental study shows that it runs much faster than other solutions with comparable quality.

Owing to its potential to satisfy all outstanding requests for the same data item with a single response, on-demand data broadcast becomes a widely accepted approach to dynamic and scalable wireless information dissemination. In some emerging applications, such as road traffic navigation system, users prefer to request multiple dependent data items at a time. In addition, requests usually have deadline constraints for real-time applications. However, in existing works, clients will not know that their requests cannot be satisfied until the deadlines expire. In this paper, admission control is introduced to data broadcast systems such that clients can be informed in advance in the case that their requests have no hope to be satisfied so that earlier remedial actions can be taken. Furthermore, a matching based allocation scheme is proposed to maximize data sharing among requests in multi-channel architectures. Simulation results show that our proposed algorithms have better performance and quality of service (QoS) than traditional algorithms.

According to data broadcast, we can satisfy multiple requests for the same data item in a broadcast tick. However, there is no significant breakthrough in performance improvement until recently that some studies proposed to use network coding in data broadcast. After broadcasting an encoded packet which encodes a number of data items, multiple clients can retrieve different requested data items in a broadcast tick. This not only utilizes bandwidth more efficiently, but also improves system performance. In this work, we propose a generalized encoding framework to incorporate network coding into data scheduling algorithms for on-demand broadcast. In the framework, data scheduling can be formulated as a weighted maximum clique problem in a graph where the weight of the clique is defined according to the performance objectives of the applications. Under the proposed framework, existing data scheduling algorithms for on-demand broadcast can be migrated into their corresponding coding versions while preserving their original criteria in scheduling data items. Our simulation results using a number of representative scheduling algorithms show that significant performance improvement can be achieved with coding.

In recent years network coding has attracted significant attention in telecommunication. The benefits of network coding to a communication network include the increased throughput as well as secure data transmission. The purpose of this work is to design secure linear network coding against wiretap attack. The problem is to maximize the transmission data rate of multiple unicast streams between a pair of source and destination nodes, under the condition of satisfying the weakly secure requirements. Different from most existing research on network coding that designs the network coding scheme based on a given network topology, we will consider the integrated network topology design and network coding design. Such an integrated approach has not been reported by other researchers. In this paper, we formally introduce the problem, prove the problem is computational intractable, and then develop efficient heuristic algorithms. We first try to find the transmission topology that is suitable for network coding. Based on the topology, we design linear network coding scheme that is weakly secure. We conduct simulations to show that the proposed algorithms can achieve good performance.

Abstract On‐demand broadcast is an effective data dissemination approach in mobile computing environments. Most of the recent studies on on‐demand data broadcast assume that clients request only a single‐data‐object at a time. This assumption may not be practical for the increasingly sophisticated mobile applications. In this paper, we investigate the scheduling problem of time‐critical requests for multiple data objects in on‐demand broadcast environments and observe that existing scheduling algorithms designed for single‐data‐object requests perform unsatisfactorily in this new setting. Based on our analysis, we propose new algorithms to improve the system performance. Copyright © 2010 John Wiley & Sons, Ltd.

On-demand broadcast is an effective wireless data dissemination technique to enhance system scalability and capability to handle dynamic data access patterns. Previous studies on time-critical on-demand data broadcast were under the assumption that each client requests only one data item at a time. With rapid growth of time-critical information dissemination services in emerging applications, there is an increasing need for systems to support efficient processing of real-time multi-item requests. Little work, however, has been done. In this work, we study the behavior of six representative single-item request based scheduling algorithms in time-critical multi-item request environments. The results show that the performance of all algorithms deteriorates when dealing with multi-item requests. We observe that data popularity, which is an effective factor to save bandwidth and improve performance in scheduling single-item requests, becomes a hindrance to performance in multi-item request environments. Most multi-item requests scheduled by these algorithms suffer from a starvation problem, which is the root of performance deterioration.

Reliable multicast in wireless networks has been well studied in the sense to solve the feedback implosion issue, which, however, can not reduce the number of retransmissions in order to recover all lost packets at receivers. Most recently, it has been proposed to use network coding for reliable multicast in wireless LANs to reduce the number of retransmissions. In this paper, we propose two new models to further reduce the number of retransmissions for reliable multicast. In the first model, each retransmission encoding decision is made according to the latest ldquowantedrdquo packet set at all receivers. Thus, the maximum number of receivers can potentially decode out one ldquowantedrdquo packet from each encoded retransmission packet. Such a model is referred to as dynamic multicast retransmission encoding (DMRE) model. This model is a memoryless model where a receiver will not buffer encoded retransmission packets for later use. In the second model, a receiver will buffer all received encoded retransmission packets and decode out their ldquowantedrdquo packets at the end of the retransmission batch. Such a model is referred to as cache-based multicast retransmission encoding(CMRE) model. The problem to minimize the number of retransmissions under both DMRE and CMRE models are NP-hard. Effective heuristic algorithms are proposed in this paper. We analyze the impact of packet delivery ratio on the gain of network coding. We derive the lower bound of the expected number of retransmissions using network coding, which provides the insights of the maximum potential gain using network coding in reliable multicast.

On-demand broadcast is an effective wireless data dissemination technique to enhance system scalability and capability to handle dynamic user access patterns. Traditional on-demand broadcast is under the assumption that only one data item can be retrieved by mobile clients in each time unit. However, the above constraint limits bandwidth utilization and throughput of broadcast systems. In this paper, we consider data broadcast with network coding in real-time on-demand broadcast environments. We analyze the coding problem in on-demand broadcast and transform it into the problem of finding the maximum clique in graph theory. Based on our analysis, a novel algorithm called ADC is proposed. ADC considers both request overlapping and request timing requirement in request scheduling and fully exploits information about clients' cached and requested data items to implement a flexible coding mechanism. The advantages of our proposed algorithm over other traditional and coding assisted broadcast algorithms are shown through simulation results. Our algorithm not only reduces deadline miss ratio of requests, but also utilizes broadcast channel bandwidth efficiently.

On-demand broadcast is an effective wireless data dissemination technique to enhance system scalability and capability to handle dynamic user access patterns. Previous studies on time-critical on-demand data broadcast were under the assumption that each client requests only one data item at a time. With rapid growth of time-critical information dissemination services in emerging applications, there is an increasing need for systems to support efficient processing of real-time multi-item requests. Little work, however, has considered on-demand broadcast environment with time-critical multi-item requests. In this paper, we investigate the scheduling problem arising in this new environment and observe that existing single item request based algorithms are unable to manage multi-item requests efficiently. Thus, an innovative algorithm that combines the strengths of data item scheduling and request scheduling is proposed. The performance results of our simulation show that the proposed algorithm is superior to other classical algorithms under a variety of circumstances. Our algorithm not only reduces deadline miss ratio of requests, but also saves broadcast channel bandwidth.

On-demand broadcast is an effective wireless data dissemination technique to enhance system scalability and capability to handle dynamic user access patterns. Previous studies on time-critical on-demand data broadcast were under the assumption that each client requests only one data item at a time. Little work, however, has considered the ondemand broadcast with time-critical multi-item requests. In this paper, we study the problem arising in this new environment and observe that existing single item based scheduling algorithms are unable to manage multi-item requests efficiently. Thus, a new scheduling algorithm that combines the benefit of data item scheduling and request scheduling is proposed. The performance results show that the proposed algorithm is superior to other classical algorithms under a variety of factors. Our algorithm not only reduces deadline-missing ratio of requests, but also saves broadcast channel bandwidth.

This paper presents a performance study on various broadcast algorithms in a Real-Time Information Dispatch System. The objective of the study is to design an efficient broadcast algorithm for providing data in a timely manner for realtime transaction processing applications in broadcast environments. We construct and conduct a series of simulation experiments to look at the performance of our proposed algorithm. Simulation results show that our proposed broadcast algorithm can further reduce the probability of mobile read only transactions missing deadlines in broadcast environments.

This paper presents a performance study on various broadcast algorithms and caching strategies for on-time delivery of data in a real time information dispatch system. The objective of the study is not just aiming at on time delivery, but to improve the response time on the data requests. We propose and perform a series of simulation experiments, using real traffic data from the access log of the official web site for FIFA 2002 World Cup. Simulation results show that our proposed broadcast algorithm not only succeeds in providing good on-time delivery of data but at the same time provides 2 to 3 times of improvement in response time over traditional scheduling algorithms like first-in-first-out (FIFO) and earliest-deadline-first (EDF). The simulation results also show that our proposed caching strategy provides further improvement in percentage of requests finished in time over traditional caching strategy like least recently used (LRU).

A new class of data-intensive applications has received wide attention. In these applications, monitoring junctions can be performed by executing pre-registered transactions periodically using data from external sources in the form of continuous data streams and producing updates as temporal data in the database. For this type of continuous transactions, the data access pattern has to be declared before submission. To keep the database fresh, these transactions must be processed in a timely fashion. However, it is also desirable to execute other one-time transactions that may use these temporal data within their deadlines. Traditional DBMS are not designed to support such applications. The theme of this paper is to propose new concurrency control protocols to process these types of transactions with competing requirements. The challenge of this work is to balance database freshness and transaction performance. Although there is a number of similar previous works in the literature, they did not consider the presence of continuous transactions and therefore the issue of data dependency between these two types of transactions is not addressed. The simulation results show that our protocols can significantly improve the performance of one-time transactions while keeping the database fresh.

On-demand broadcast is an attractive data dissemination method for mobile and wireless computing. In this paper, we propose a new online preemptive scheduling algorithm, called PRDS that incorporates the urgency, the data size and the number of pending requests for real-time on-demand broadcast system. Furthermore, we use pyramid preemption to optimize performance and reduce overhead. We have done a series of simulation experiments to evaluate the performance of our algorithm as compared with other previously proposed methods under a range of scenarios. The experimental results show that our algorithm can substantially outperform other algorithms without jeopardizing other performance metrics, such as response time and stretch.

In this paper, we study the performance and impact of maintaining temporal consistency on a recently proposed concurrency control protocol for processing transactions in broadcast environments. This protocol offers autonomy between mobile clients and the server such that mobile clients can read consistent data off the air without contacting the server. However, most of the existing mobile computing applications, such as information dispersal systems for stock prices and weather information, are comprised of real-time read only transactions. In order to deliver timely and useful results, real-time transactions must also read temporal consistent data. A number of approaches to maintaining temporal consistency are studied through a series of simulation experiments. Results show that taking advantage of data semantics and temporal consistency requirement can improve the performance of mobile read only transactions in broadcast environments.

Many studies on transaction processing in mobile environments have an implicit assumption that the server is able to broadcast consistent data to the mobile clients. However, this assumption may not be valid unless there is a special algorithm to handle broadcasting data in a consistent and timely manner. In this paper, we formulate broadcasting data at the server as a broadcast transaction which reads the entire database in a consistent way in the broadcasting process. This issue is not trivial as the broadcast transaction will create high interference to normal transactions at the server.

Most of the recent studies on broadcast based data dissemination approach have an implicit assumption that the server is able to broadcast consistent data to the mobile clients. However, this assumption may not be valid unless there is a special algorithm to handle broadcasting data in a consistent and timely manner. In this work, we address a number of issues related to this problem. An efficient algorithm called the read-write set test is adopted to read the entire database, which causes little interference with the update transactions at the server. For broadcast transaction scheduling, an algorithm based on a mixed strategy is proposed to handle the case of flat broadcast disks. Using these two algorithms together with some fine tuning, the objectives of reading entire database consistently with minimum impact to the system, broadcasting fresh data, and meeting the periodicity requirement can be met.

In the near future, tens of millions of users will have access to distributed information systems through the wireless interface in their mobile computers. The physical characteristics of the wireless medium pose new challenging issues on data consistency of transaction processing in wireless environments. In particular, the monetarily expensive wireless bandwidth and the asymmetric communication between the mobile clients and the server bar the applicability of conventional transaction processing techniques. In this paper, we first propose a concurrency control protocol in wireless environments that is adapted from the optimistic concurrency control with forward validation protocol. The protocol offers autonomy between the mobile clients and the server such that the mobile clients can read consistent data off the air without contacting the server. To reduce the number of unnecessary transaction restarts such that the timeliness of mobile transactions can be enhanced, we propose another protocol based on timestamp ordering that can show significant performance improvement. The timestamp ordering technique enjoys a number of benefits from the separate processing and flexible adjustment of serialization order by exploiting the semantics of read-only transactions. Most of the existing applications, such as information dispersal systems for stock prices, weather information and traffic condition updates, are comprised of read-only transactions. The simulation results confirm that the proposed protocol could be an efficient and effective approach to transaction processing in real-time broadcast environments for meeting transaction deadlines.

Many recent studies have suggested that the optimistic concurrency control (OCC) protocols outperform the locking-based protocols in real-time database systems (RTDBS). However, the OCC protocols suffer from the problem of unnecessary transaction restarts that is detrimental to transactions meeting their deadlines. The problem is more intensified in mixed transaction environments. Firm transactions are more vulnerable to restarts when they are in conflict with hard transactions on data access. In this paper, we addressed the problem and devised an effective OCC protocol with dynamic adjustment of serialization order, called OCC-DA, for RTDBS with mixed transactions. This protocol can avoid unnecessary transaction restarts by dynamically adjusting the serialization order of the conflicting transactions with respect to the validating transaction. As a result, much resource can be saved and more firm transactions can meet their deadlines without affecting the execution of hard transactions. The characteristics of the OCC-DA protocol were examined in detail by simulation. The results show that the performance of the OCC-DA protocol was consistently better than the other two popular protocols, OCC with forward validation and OCC with Wait-50, over a wide range of system settings. In particular, the OCC-DA protocol provides a more significant performance gain in mixed transaction environments.

Conventional concurrency control protocols are inapplicable in mobile broadcast environments due to a number of constraints of wireless communications. Previous studies are focused on efficient processing of read-only transactions at the mobile clients, neglecting update transactions. In this paper, we design a new protocol for processing both read-only and update mobile transactions. The protocol can detect data conflicts at an early stage at the mobile clients and resolve data conflicts flexibly using dynamic adjustment of timestamp ordering. Early data conflict detection saves processing and communication resources, while dynamic adjustment of timestamp ordering allows more schedules of transaction executions such that unnecessary transaction aborts can be avoided. We performed extensive simulation studies to evaluate the effectiveness of these two features for the performance of the new protocol. The analysis of simulation results showed that both features are effective and contribute differently to the satisfactory performance of the protocol.

The emergence of Intelligent I/O (I2O) architecture provides a standard for high-performance I/O subsystems and introduces intelligence at the hardware level. With an embedded processor, I2O adaptors can offload the major I/O processing workload from the CPU and, at the same time, increase the I/O performance. This paper addresses the essential issue in the design of disk scheduling for I2O RAID-0 devices. We explore online real-time multi-disk scheduling for I2O requests and propose highly efficient algorithms to minimize the number of deadline violations and, at the same time, to improve the response times of requests. The proposed methodologies are verified by a series of experiments under realistic and randomly generated workloads.

In broadcast environments, communication bandwidth asymmetry is a distinguishing feature. The low bandwidth available for clients to communicate with the broadcast server makes it expensive and inefficient to maintain global serializability among all the transactions that execute at distributed mobile clients. In this paper, investigation is made to relax the requirements of global serializability among transactions while data consistency is still achieved. The NRS-Algorithm is proposed to process read-only transactions separately from update transactions to reduce the degree of data contention between the two kinds of transactions. Moreover, each read-only transaction running at the clients is guaranteed to read consistent data values autonomously without the need to do validation at the server. This is extremely beneficial to the concurrency control in broadcast environments where the upstream communication capacity is limited. To generalize the idea, two kinds of group consistency requirements for read-only transactions are defined. Group strong consistency requires a group of read-only transactions to be conflict serializable with respect to the update transactions. A weaker form of consistency, group view consistency, is also defined to allow a group of read-only transactions to be view serializable with respect to some update transactions. The NRS-Algorithm is then extended to preserve the two kinds of group consistency within a group of read-only transactions.

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.

In this paper, we investigate the approach of using separate algorithms to process read-only transactions in real-time systems. A read-only transaction (ROT) is a transaction that only reads, but does not update any data item. Since there is a significant proportion of ROTs in several real-time systems, it is important to investigate how to process ROTs effectively. Using an algorithm to process ROTs separately from update transactions may reduce the interference between ROTs and update transactions. This reduced interference alleviates the impact of concurrency control on real-time priority-driven scheduling and improves the timeliness of the system. Moreover, we explore the different consistency requirements of ROTs. Particularly, we define a weaker form of consistency, view consistency, which allows ROTs to perceive different serialization order of update transactions. While view consistency permits non-serializability, ROTs are still ensured to see consistent data. We propose two robust algorithms for different consistency requirements of ROTs. The two algorithms are robust in the sense that they can be used in a compatible way so that a real-time system can provide different consistent data for different applications. The performance of two algorithms was examined through a series of simulation studies. The simulation results show that the two algorithms outperform the high-priority two-phase locking protocol.

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 use of ATM networks in interconnecting LANs and MANs results in a bandwidth allocation problem due to the connectionless nature of most LAN/MAN traffic. A well known scheme is to use bandwidth advertising in which available bandwidth is broadcast to allow for users contention. This paper presents an enhancement over the basic scheme that will improve the burst loss rate significantly at high network loads.