MobiQual: QoS-aware Load Shedding in Mobile CQ Systems

Freshness and accuracy are two key measures of quality of service (QoS) in processing location-based, mobile continual queries (CQs). Freshness necessitates the CQ server to perform frequent query re-evaluations. Accuracy demands the CQ server to receive and process frequent position updates from the mobile nodes. However, it is often difficult to provide both fresh and accurate CQ results due to (a) limited resources in computing and communication and (b) fast-changing load conditions caused by continuous mobile node movement. Thus a key challenge for a mobile CQ system is: How do we achieve the highest possible quality of the query results, in both freshness and accuracy, with currently available resources under rapidly changing load conditions? In this paper, we formulate this problem as a load shedding one, and develop MobiQual as a solution. It is a dynamic and QoS-aware framework for performing both update load shedding and query load shedding. MobiQual uses per-query QoS specifications to maximize the overall freshness and accuracy of the query results. In view of the QoS specifications, it employs query clustering and space partitioning mechanisms to apply differing amounts of query and update load shedding for different query and mobile node groups, respectively. We show that our solution is superior to competing approaches that lack the QoS-awareness properties of MobiQual, as well as solutions that perform query-only or update-only load shedding.

By: Bugra Gedik; Kun-Lung Wu; Philip S. Yu; Ling Liu

Published in: RC24214 in 2007

LIMITED DISTRIBUTION NOTICE:

This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

rc24214.pdf

Questions about this service can be mailed to reports@us.ibm.com .