In this paper, we investigate a fundamental assignment problem for a type of constrained group service. A group is considered successfully formed only if the number of assigned patrons falls within the specified lower and upper-bound constraints. We introduce the concept of rank-consistent to characterize a useful subset of the assignment problem. Although the problem is still NP-hard, we introduce the technique of allocation vectors to handle the complexity. This technique not only allows us to exploit several characteristics for performance optimization but also enables us to design a generic procedure to obtain the optimal physical assignment under a given allocation vector. We lay the foundation of a 1/2 approximation algorithm and a branch and bound algorithm for seeking the optimal solution. The branch and bound algorithm employs a specific pattern of optimal allocation vector and several newly proposed pruning techniques, especially the one that utilizes the dominance relations between allocation vectors. Extensive experiments demonstrate that our algorithm is much more effective than a set of heuristic greedy algorithms.

As mobile customers gradually occupying the largest share of cloud service users, the effective and cost-sensitive provisioning of mobile cloud services quickly becomes a main theme in cloud computing. The key issues involved are much more than just enabling mobile users to access remote cloud resources through wireless networks. The resource limited and intermittent disconnection problems of mobile environments have intrinsic conflict with the continuous connection assumption of the cloud service usage patterns. We advocate that seamless service provisioning in mobile cloud can only be achieved with full exploitation of all available resources around mobile users. An elastic framework is proposed to automatically and dynamically deploy cloud services on data center, base stations, client units, even peer devices. The best deployment location is dynamically determined based on a context-aware and cost-sensitive evaluation model. To facilitate easy adoption of the proposed framework, a service development model and associated semi-automatic tools are provided such that cloud service developers can easily convert a service for execution on different platforms without porting. Prototype implementation and evaluation on the Google Cloud and Android platforms demonstrate that our mechanism can successfully maintain seamless services with very low overhead.

Group services are highly important for a variety of computing application domains. In this paper, we study the fundamental problem of allocating a set of service patrons to a set of service groups in an attempt to maximize the total profit gained by the grouping platform. The problem under consideration is unique in that group service is not provided at all unless its lower bound requirement is satisfied. In addition, we allow each service patron to join multiple groups. In this paper, after proving the hardness property of the problem, we focus first on a special case of the problem. To this end, we propose two approaches. One aims at providing a suboptimal solution using a 1/2-approximation algorithm. The other approach turns to seeking an optimal solution using a branch and bound technique. For this purpose, we introduce a theorem that captures a useful property of an optimal allocation. Based on this theorem, we design an efficient branch and bound algorithm to find an optimal solution. We then extend these methods to solve the general problem. Extensive experiments show that our branch and bound algorithm is able to obtain an optimal solution with a small amount of computation time in many different settings.

Enterprise RFID data management is highly challenging not only because of the huge volume of data from distributed sources, but particularly because of the dynamic nature of the reader inputs. With user-designated quality of service (QoS) requirements, the data management system must be able to dynamically detect the status changes of the RFID inputs and adjust the processing strategies for continuously maintaining the desired level of QoS. We propose a QoS-aware framework for modeling the enterprise data service problem, and for on-line adaptive processing of distributed RFID data streams. The data processing structure is modeled as a hierarchy of aggregation nodes in accordance with the structure of an organization. Leaf nodes correspond to the RFID streaming inputs. A set of aggregation/deaggregation operations is devised to adjust the processing granularity level based on QoS dynamics. A QoS constrained query issued at any aggregation node is parsed into an aggregation subtree rooted at that node. For QoS-aware processing of the query, several algorithms are designed to dynamically apply proper aggregation/deaggregation operations on selected nodes for raising or lowering the granularity levels or changing the aggregation methods. The goal is to continuously maintain the desired level of QoS under constant variation of the streaming data volume. Prototype development and extensive simulation show that our framework and techniques can handle highly varied RFID streaming inputs and continuously satisfy the QoS constraints.

Target detection is an important problem in wireless sensor networks where a number of sensors form a network to detect the presence or absence of a certain target or event. Data fusion is a potential method broadly used to improve detection performance when the sampling data are noisy. However, low detection probability cannot be avoided if detection decisions are made based on a collection of sampling data taken at just one particular moment. This paper adopts fusion-based sequential detection to guarantee the quality of detection results. A fusion center is used to collect local data from individual sensors periodically. A final detection decision is made only after the pre-defined constraints of false alarm and missing probability are satisfied. Rules for each sensor to make local decisions and for the fusion center to make global decisions are derived. Simulations are conducted to show the latency of making the final decisions based on the proposed fusion scheme.

Media streaming is expected to be one of the most promising services in mobile environments. Effective data streaming management techniques are, therefore, in strong demand. In an earlier paper, the ideas and benefits of two-level cooperative media streaming with headlight prefetching and dynamic chaining were demonstrated. Though complementary to each other, they operate in session-wide static and distinctive modes. Moreover, users do not have control over the quality and cost levels of the streaming services. The performance degradation or cost increment can reach an unacceptable level under fast or highly unstable moving patterns. In this paper, we propose the QoS-based dynamic adaptation techniques for the flexible employment and smooth integration of headlight prefetching and dynamic chaining to continuously provide quality streaming services to mobile users. The QoS-aware dynamic headlight prefetching is for the cooperation between streaming access points to dynamically adjust the prefetching scheme in response to the fast changing moving patterns. Adaptive P2P media streaming is for the cooperation between mobile users such that multiple peers can be used as streaming sources to increase the likelihood of successful chaining. Furthermore, a QoS-based technique is developed to dynamically trigger and proportionally adjust the prefetching degree when the stability and quality of P2P streaming service vary. With extensive simulation and performance evaluation, we demonstrate that the proposed dynamic adaptation techniques significantly improve the service quality and streaming performance of cooperative media streaming in mobile environments.

Most users in a mobile environment are moving and accessing wireless services for the activities they are currently engaged in. We propose the idea of complex activity for characterizing the continuously changing complex behavior patterns of mobile users. For the purpose of data management, a complex activity is modeled as a sequence of location movement, service requests, the cooccurrence of location and service, or the interleaving of all above. An activity may be composed of subactivities. Different activities may exhibit dependencies that affect user behaviors. We argue that the complex activity concept provides a more precise, rich, and detail description of user behavioral patterns which are invaluable for data management in mobile environments. Proper exploration of user activities has the potential of providing much higher quality and personalized services to individual user at the right place on the right time. We, therefore, propose new methods for complex activity mining, incremental maintenance, online detection and proactive data management based on user activities. In particular, we devise prefetching and pushing techniques with cost-sensitive control to facilitate predictive data allocation. Preliminary implementation and simulation results demonstrate that the proposed framework and techniques can significantly increase local availability, conserve execution cost, reduce response time, and improve cache utilization.

Media streaming in mobile environments is becoming more and more important with the proliferation of 3G technologies and the popularity of online media services such as news clips, live sports, and hot movies. To avoid service interruptions, proper data management strategies must be taken by all parties. We propose a two-level framework and cooperative techniques for mobile media streaming. Headlight prefetching is for the cooperation of streaming access points to deal with unpredictable client movement and seamless hand-off. For each user, we maintain a virtual fan-shaped prefetching zone along the direction of movement similar to a vehicle headlight. The overlapping area and accumulated virtual illuminance of the headlight zone on a particular cell determine the degree and volume of prefetching on that cell. Dynamic chaining facilitates cooperation among users to maximize cache utilization and streaming benefit. On receiving a request from a client, the streaming access point starts a search for supplying partners before attempting to a remote media server. If a qualified partner is found, the client is chained to the partner and receives subsequent segments without server intervention. The client can itself be a supplying partner for other clients and naturally form a chain of users that are viewing and sharing the same media. Simulation results demonstrate that headlight prefetching and dynamic chaining can significantly decrease streaming disruptions, reduce bandwidth consumption, increase cache utilization and improve service response time.

A replication scheme determines the number and location of replicas in a distributed system. Traditional static replication schemes do not perform well in mobile environments due to the assumptions of fixed hosts, relatively static access patterns, and the lack of considerations on users' behalf. For effective data management in mobile environments, we define the notion of activity-data dependency for inferring the information requirement of mobile users based on their scheduled activities. We then propose a dynamic replication scheme which employs user profiles for recording users' mobility schedules, accesses behaviors and read/write patterns, and actively reconfigures the replicas to adapt to changes in user locations, data requests, and system status. Simulation results demonstrate that the scheme can accurately predict the data requirement to facilitate effective replication, reduce response time, and increase data availability.

We characterize the dynamic data management problem for location based services (LBS) in mobile environments and devise a cost model for servicing both location independent and location dependent data. The cost analysis leads to a set of dynamic data management strategies that employs judicious caching, proactive server pushing and neighborhood replication to reduce service cost and improve response time under changing user mobility and access patterns. Simulation results suggest that different strategies are effective for different types of data in response to different patterns of movement and information access.

A replication scheme determines the number and location of replicas in a distributed system. Traditional static replication schemes do not perform well in a mobile environment since the assumptions of fixed hosts and relatively static access patterns no longer hold. For effective data management in a mobile environment, we propose a dynamic replication scheme which employs user profiles for recording users' mobility schedules, access behavior and read/write patterns, and actively reconfigures the replicas to adjust to the changes in user locations and system status. Simulation results demonstrate that the scheme can accurately predict the data requirement to facilitate effective replication, reduce response time, and increase data availability.

Decomposition abstraction is the process of organizing and specifying decomposition strategies for the exploitation of parallelism available in an application. In this paper we develop and evaluate declarative primitives for rule-based programs that expand opportunities for parallel execution. These primitives make explicit, implicit relations among the data and similarly among the rules. The semantics of the primitives are presented in a general object-based framework such that they may be applied to most rule-based programming languages. We show how the additional information provided by the decomposition primitives can be incorporated into a semantic-based dependency analysis technique. The resulting analysis reveals parallelism at compile time that is very difficult, if not impossible, to discover by traditional syntactic analysis techniques. Simulation results demonstrate scalable and broadly available parallelism.

We propose a new approach for the parallel execution of production system programs. This approach embodies methods of decomposition abstraction using declarative mechanisms. Application semantics can then be exploited to achieve a much higher degree of concurrency. We present the underlying object-based framework of production systems and discuss the ensuing semantic-based dependency analysis technique. In particular, we define a new notion of functional dependency to characterize associative relationships among data objects, which can be used to determine concurrently executable rules.