Science Models
Science Fair Projects

Published on Sep 19, 2023


In location-based mobile continual query (CQ) systems, the two key measures of quality-ofservice (QoS) are freshness and accuracy. To achieve freshness the CQ server must perform frequent query reevaluations. To attain accuracy the CQ server must receive and process frequent position updates from the mobile nodes. However, it is often difficult to obtain fresh and accurate CQ results simultaneously due to limited resources in computing and communication and fast-changing load conditions caused by continuous mobile node movement.

Hence, a key challenge for a mobile CQ system is to achieve the highest possible quality of the CQ results in both freshness and accuracy with currently available resources. In this paper we formulate this problem as a load shedding one and develop MobiQual-a QoS-aware approach to performing both update load shedding and query load shedding.

The design of MobiQual highlights three important features. Firstly, the differentiated load shedding where we apply different amounts of query load shedding and update load shedding to different groups of queries and mobile nodes. Secondly, Per-query QoS specification in which individualized QoS specifications are used to maximize the overall freshness and accuracy of the query results. There is low-cost adaptation as well where MobiQual dynamically adapts with a minimal overhead to changing load conditions and available resources.

We conduct a set of comprehensive experiments to evaluate the effectiveness of MobiQual. The results show that through a careful combination of update and query load shedding the MobiQual approach leads to much higher freshness and accuracy in the query results in all cases compared to existing approaches that lack the QoS-awareness properties of MobiQual, as well as the solutions that perform queryonly or update-only load shedding.

To obtain fresher query results, the CQ server must re-evaluate the continual queries more frequently, requiring more computing resources. Similarly, to attain more accurate query results, the CQ server must receive and process position updates from the mobile nodes at a higher rate, demanding communication as well as computing resources.

However, it is almost impossible for a mobile CQ system to achieve 100% fresh and accurate results due to continuously changing positions of mobile nodes. A key challenge therefore is: How do we achieve the highest possible quality of the query results in both freshness and accuracy, in the presence of changing availability of resources and changing workloads of location updates and location queries


Mobile Node

A client is an application or system that accesses a remote service on another computer system known as a server by way of a network. The term was first applied to devices that were not capable of running their own stand-alone programs, but could interact with remote computers via a network. These dumb terminals were clients of the time-sharing mainframe computer. In the architecture used by our system, the client is represented by a mobile node enabled to send multiple messages of variable character length irrespective of any time or message length constraint. The number of mobile nodes is also variable depending upon the traffic in the network.

Server Node

In computing, a server is any combination of hardware or software designed to provide services to clients. The server performs some computational task on behalf of clients. The clients either run on the same computer or connect through the network. When used alone the term typically refers to a computer which may be running a server operating system but is commonly used to refer to any software or dedicated hardware capable of providing services. In our proposed system the server used is a CQ server which continues to execute over time. The mobile node acting as a client sends streams of data to the CQ server. When new data enters the stream the results of the continuous query are updated.

Network Model

Generally, the channel quality is time varying. For the server-AP association decision, a user performs multiple samplings of the channel quality and only the signal attenuation that results from long term channel condition changes are utilized our load model can accommodate various additive load definitions such as the number of users associated with an AP. It can also deal with the multiplicative user load contributions.

Load Shedding in Mobile CQ Systems

In a mobile CQ system, the CQ server receives position updates from the mobile nodes through a set of base stations and periodically evaluates the installed continual queries (such as continual range or nearest neighbor queries) This is because a larger number of position updates must be processed by the server, for instance, to maintain an index. When the position update rates are high, the amount of position updates is huge and the server may randomly drop some of the updates if resources are limited. This can cause unbounded inaccuracy in the query results. In MobiQual, we use accuracy-conscious update load shedding to regulate the load incurred on the CQ server due to position update processing by dynamically configuring the inaccuracy thresholds at the mobile nodes.

Algorithm used

Congestion Load Minimization The existing system minimizes the load of the congested AP, but they do not necessarily balance the load. In this section, we consider min-max load balancing approach that not only minimizes the network congestion load but also balances the load of the no congested APs. As mentioned earlier, the proposed approach can be used for obtaining various max-min fairness objectives by associating each user with appropriate load contributions. Unfortunately, min-max load balancing is NP-hard problem and it is hard to find even an approximated solution. In this paper we solve a variant of the min-max problem termed min-max priority-load balancing problem whose optimal solution can be found in polynomial time.

System Architecture

System architecture diagram is a simple diagrammatic form of the functions happening in the load shedding process, and it is used to understand the entire process as shown in the figure

Load Shedding In Mobile Systems

Functional Specifications


It includes the algorithm for grouping the queries into k clusters and the algorithm for partitioning the geographical space of interest into l regions. The query groups are incrementally updated when queries are installed or removed from the system. The space partitioning is recomputed prior to the periodic adaptation.


It involves computing aggregate QoS functions for each query group and region. The aggregated QoS functions for each query group represent the freshness aspect of the quality. The aggregated QoS functions for each region represent the accuracy aspect of the quality. We argue that the separation of these two aspects is essential to the development of a fast algorithm for configuring the re-evaluation periods and the inaccuracy thresholds to perform adaptation. QoS aggregation is repeated only when there is a change in the query grouping or the space partitioning.


It is performed periodically to determine the throttle fraction which defines the amount of load that can be retained relative to the load of providing perfect quality, setting of re-evaluation periods and the setting of inaccuracy thresholds.

Activity Diagram

Activity diagrams are loosely defined diagrams to show workflow of stepwise activities and actions with support for choice, iteration and concurrency. UML activity diagrams can be used to describe the business and operational step-by-step workflow of the components in a system. UML activity diagrams could potentially model the internal logic of a complex operation. In many ways UML activity diagrams are the object-oriented equivalent of flow charts and data flow diagrams (DFDs) from structural development. The working of our proposed system is shown in the activity diagram in the figure.

Activity Diagram

Highlights of the Project

The cloud has become a widely used term in academia and the industry. Education has not remained unaware of this trend, and several educational solutions based on cloud technologies are already in place, especially for software as a service cloud. However, an evaluation of the educational potential of infrastructure and platform clouds has not been explored yet. An evaluation of which type of cloud would be the most beneficial for students to learn, depending on the technical knowledge required for its usage, is missing.

In this paper we have presented MobiQual, a load shedding system aimed at providing high quality query results in mobile continual query systems. MobiQual has three unique properties. First, it uses per-query QoS specifications that characterize the tolerance of queries to staleness and inaccuracy in the query results, in order to maximize the overall QoS of the system. Second, it effectively combines query load shedding and update load shedding within the same framework, through the use of differentiated load shedding concept. Finally, the load shedding mechanisms used by MobiQual are lightweight, enabling quick adaption to changes in the workload, in terms of the number of queries, number of mobile nodes or their changing movement patterns.

Through a detailed experimental study, we have shown that the MobiQual system significantly outperforms approaches that are based on query-only or update-only load shedding, as well as approaches that do combined query and update load shedding but lack the differentiated load shedding elements of the MobiQual solution, in particular the query grouping and space partitioning mechanisms. There are several interesting issues for future work. In this paper, we only considered range queries. However, MobiQual can be applied to kNN queries as well. There are various query processing approaches where kNN queries are first approximated by circular regions based on upper bounds on the kth distances.

MobiQual should be able to dynamically adjust the values of the (number of shedding regions) and k (number of query groups) parameters as the workload changes. An overestimated value for these paramters means lost opportunity in terms of minimizing the cost of adaptation, whereas an underestimated value means lost opportunity in terms of maximizing the overall QoS. In this paper we have shown that the time it takes to run the adaptation step is relatively small compared to the adaptation period in most practical scenarios. This means relatively aggressive values for l and k could be used to optimize for QoS without worrying about the cost of adaptation.Load shedding system aimed at providing high quality query results in mobile continual query systems. The unique property of MobiQual is that it uses per-query QoS specifications that characterize the tolerance of queries to staleness and inaccuracy in the query results, in order to maximize the overall QoS of the system.

System Specification

The hardware and software requirements for the development phase of our project are:

Software Requirements :

OPERATING SYSTEM : Windows 07/ XP Professional
FRONT END : Visual Studio 2010

Hardware Requirements :

PROCESSOR : PENTIUM IV 2.6 GHz, Intel Core 2 Duo.

Related Science Topics