Sleepwalk : Scalable and Energy-Efficient Processing of Continuous Range Queries for Location-Aware Mobile Computing

Abstract

Recently, monitoring queries are getting attention for various real-life applications such as safety, security, and personalization services. This work proposes a distributed sensing and monitoring technique (called Sleepwalk) for continuous range queries with energy- and computation-efficient optimizations. In our scheme, each mobile client (MC) is aware of its nearby monitoring queries by leveraging its processing power. The proposed Sleepwalk has three major contributions. First, with piecewise linear movement assumption and motion vector $\bar{v}$ , it can locally preevaluate every possible query result in advance in bulk and sends them to the server at once. We also provide a timestamp-based invalidation technique for efficiently removing failed preevaluated results by computing the smallest valid timestamp. Second, an energy-conserving technique that repeatedly sleeps off MCs whenever possible is proposed by calculating the safely sleepable time. Third, we provide a set of localized query optimization techniques for MCs' local query subset using plane-sweeping, which effectively minimize search space. Extensive experiments indicate that Sleepwalk technique remarkably outperforms existing state-of-the-art techniques in terms of server scalability, communication cost, and energy consumption of MCs.

1. Introduction

With emergence of GPS-capable mobile devices and introduction of 3G and 4G mobile broadband networks, location-based services (LBSs) are rapidly becoming all-pervasive [1, 2]. More importantly, location-based sensing and monitoring (LBSM) services, which monitor mobile objects in a geographic region of interest, have only recently started to receive attention. Representative applications of LBSM are traffic monitoring for a specific region, area monitoring for sending mobile coupons, child-caring with real-time monitoring in a dangerous area, and triggering special tasks with a given region (see Figure 1). LBSM can be formalized as continuous range queries processing with a large number of mobile objects (e.g., mobile clients (MCs)). Such services impose heavy workloads on the central server for recomputing and managing real-time query results continuously. Moreover, moving objects (in the work, moving objects and mobile clients are used interchangeably) should transmit their location continuously in order to support up-to-date query results. This incurs a huge communication cost and excessive energy consumption of battery-powered mobile clients.

Figure 1

Real-world example from practical and real mobile applications: aToDo Map app for iPhone (a), LOCALE app for Android (b).

In order to address this problem, numerous works have proposed in a centralized setup (e.g., see [3, 4]) and a distributed setup (e.g., see [5, 6]). Centralized approaches only can improve server's scalability while distributed approaches can also do the communication cost of MCs by leveraging their processing power. As representative techniques of the latter, Figure 2 shows the conceptual differences between the proposed technique and two existing works such as Q-index [7] and Monitoring Query Management (MQM) [8]. Similarly, these introduce some kind of spatial region called safe region and resident domain (RD), respectively, for reducing communication costs. In Q-index technique [7], an MC filters out every location update within its safe region and sends location update only if it exits its safe region (cf. Figure 2(a)). In this work, however, both processing range queries and computing safe regions (with $\mathcal{O}(n)$ to $\mathcal{O}(n\hspace{0.17em}{\mathrm{l}\mathrm{o}\mathrm{g}}^{\mathrm{3}}n)$ computations) are performed in server. Consequently, the server is not very scalable, and each MC's processing power is not fully utilized. In MQM technique [8], the server effectively distributes the query workload over a number of MCs by leveraging their processing power; for example, in Figure 2(b), a query set $\{Q_{\mathrm{4}},Q_{\mathrm{5}},Q_{\mathrm{6}},Q_{\mathrm{8}}\}$ with $RD$ is allocated and cached as MC's local query subset by server based on its location and processing capability. By referring to the cached local query subset, MC is capable of evaluating query results locally and autonomously. During that, all unnecessary movements irrelevant to the query results can easily be filtered out; then no updates are triggered. MC sends an update only when it exits its RD or its query results are updated.

Figure 2

Conceptual differences: (a) Q-index technique with the concept of safe region, (b) MQM technique with the concept of resident domain, and (c) the proposed technique with preevaluation and selective sleep.

Existing distributed monitoring techniques [7, 8] have two major shortcomings. One is the lack of consideration of MC's motion vector; that is, most of previous works focused only on point location with oversimplified mobility assumption. Hence, the performance improvement in query processing is limited. For instance, 4 updates of MQM technique in Figure 2(b) can be reduced into a single update which includes 4 predictive results in advance by linear prediction. The other one is no harnessing of sleep mode (or power-saving mode) for reducing energy consumption, which is supported in every modern mobile processor. As long as accurate results are maintained, mobile devices should transit themselves into sleep mode as possible proactively. To our knowledge, there are only limited researches on proactively exploiting the sleep mode in continuous range query processing.

Motivation. In the light of the weakness of existing techniques, we propose a scalable and energy-efficient technique (called Sleepwalk) for processing continuous range queries. In addition to the virtue of MQM technique, we present three major improvements: (1) bulk preevaluation of query results with linear prediction, (2) energy-conserving strategy by selective sleep-off, and (3) localized query optimizations for MCs. First, by exploiting MC's motion vector $\bar{v}$ , we preevaluate all possible query results in advance in bulk. Thus, four separate intersecting points (i.e., query results) in Figure 2(b) can be preevaluated in advance and aggregated into a single query result set including them. Failed preevaluated results are efficiently removed by a timestamp-based invalidation technique. The query processing cost and communication cost will be greatly reduced as MCs' movements are close to linear movements and the number of intersecting points increases. Second, in order to conserve energy consumption of MCs, we propose a selective sleep-off technique that repeatedly transits MCs into sleep mode whenever possible; the safely sleepabletime (called $SafeSleepTime$ ) can be calculated by considering maximum velocity $v_{\mathrm{m}\mathrm{a}\mathrm{x}}$ and minimum perimeter distance to the nearest query ( $SleepDist$ ) (cf. Figure 2(c)). Third, we provide a set of localized query optimization techniques using plane-sweeping over MCs' local query subset, which effectively minimize search space. Basic idea is to sort local query subset along an axis and maintain lower- and upper-bound of it for computing query results in a computationally efficient manner. Through these improvements, our Sleepwalk proposal can achieve low server maintenance cost and processing delay, minimized energy consumption of MCs, minimized communication cost, and low computational cost in MCs in comparison to the existing state-of-the-art techniques.

Organization. The rest of the paper is organized as follows: Section 2 provides the details of Sleepwalk techniques with its data structures and distributed query processing. In Section 3, we discuss advanced techniques for further improving the proposed approach. Section 4 presents the results of a performance evaluation of the proposed and previous studies. Section 5 gives the related work on the subject. Finally, we conclude in Section 6 with directions for future work.

2. Sleepwalk: Efficient Processing of Range Monitoring Queries

2.1. The Basic Idea and Design Goals

In a systematic viewpoint, the proposed system architecture is a set of a single central server (as mediator) and numerous mobile clients (as distributed query processors) with positioning, computational, and communication capabilities. The basic idea is to make the utmost use of MCs' processing power to improve system's performance in terms of server scalability, communication cost, and the energy consumption of MCs. To this end, based on the virtue of distributed query processing discussed in Section 1, we propose the following techniques.

Bulk Preevaluation of Query Results with Linear Prediction. By utilizing the linear prediction technique with MC's motion vector, we can precompute every possible query result in advance in bulk. If such prediction is correct within the location error threshold δ (location error is inherent due to sensor error, continuous movement of moving objects, and communication delay, and its threshold δ is application-specific. The distance between actual location $p(t)$ and the estimated location $\widehat{p}(t)$ does not exceed the threshold δ; i.e., $|p(t),\widehat{p}(t)|\le \delta$ , where $\left|·,·\right|$ is defined as distance between two points), query processing can be performed without any message transmission; simply the oldest result is consumed and influenced to query results. If it fails, however, the results should be recomputed totally. Assuming the piecewise linear movement of real-life moving objects (The movement of real users cannot be described as a single line (i.e., a linear function) but as a set of line segments, which is called piecewise linear function (i.e., a function composed of line segments). The approach is proved to be effective in the area of research with various works such as [9].), this technique will greatly decrease the number of transmissions between server and MCs, so that the communication cost between them is minimized.

Selective Sleep-Off. The sleep mode is mainly designed for energy saving. In the Hobbit chip from AT&T, for instance, the ratio of energy consumption in the active mode to the sleep mode is 5,000 [11]. Thus, most of energy-efficient approaches largely depend on the policy of “switching into sleep mode whenever possible” without interfering MC's main task. At least to our knowledge, only few works have been done so far on proactively exploiting the sleep mode for continuous range query processing. Assuming each MC's maximum velocity, we can define safe period of time (called $SafeSleepTime$ ) which ensures the correctness of query results during sleep.

Localized Query Optimizations. Despite various woks on minimizing the communication cost and energy consumption of MCs, there is still a lack of research in optimizing the localized query processing of MCs. Based on a plane-sweeping algorithm, we study a lightweight optimization technique by pruning unnecessary search space of MC's local query table.

2.2. Client/Server Data Structure Design

2.2.1. Server Data Structures

As illustrated in Figure 3, the server acts as a mediator of a large number of mobile clients; it manages monitoring queries and their up-to-date results and allocates optimal query subset to each MC:

• (i)

Global query table ( $GQT$ ): GQT is a table of all registered stationary monitoring queries $〈\underset{\_}{qid},qr,olist〉$ in a rectangle shape $qr$ , indexed by a query identifier $qid$ . Each tuple's $olist$ is the list of $oid$ intersected with its query rectangle $qr$ (i.e., $oid\in OT$ ) (for the sake of simplicity, monitoring queries are abstracted as rectangles in this work. However, these can be extended to any kinds of shape including circles and polygons).

(ii)

Preevaluated query result ( $PQR$ ) is a sorted list (or heap) of all preevaluated results $〈oid,p(x,y),\underrightarrow{t},flag,qid,sq〉$ from mobile object $oid$ in ascending order of time t ( $\underrightarrow{t}$ means that each entry in PQR is sorted in ascending order of t). Each tuple means that object $oid\in OT$ will enter or exit the monitoring query $qid\in GQT$ at point $p(x,y)$ at time t ( $flag$ is either “enter” or “exit”). Since each PQR entry is predictive, the failed prediction should be purged efficiently; in the case it is called expired. To minimize the purging cost, every PQR entry is timestamped by the sequence number $sq$ generated by each MC's sequence generator $sqGen$ .

(iii)

Object table ( $OT$ ) is a table of all registered objects in forms of tuple $〈\underset{\_}{oid},qlist,s{q}_{\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}〉$ indexed by object-id $oid$ . The list of all intersected queries is $qlist$ , and $s{q}_{\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}$ is the smallest sequence number of all preevaluated results in PQR. Thus, expired PQR entries can be identified by referring to $s{q}_{\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}$ (cf. Section 2.3.3).

(iv)

Query index ( $QI$ ) is a spatial index over $GQT$ . It can be either an R-tree [12] or a grid-file. Thanks to simplicity and efficiency of MQM technique, and for fair comparison, we exploit its BP-tree index in this work (cf. Section 2.3.1).

Figure 3

Client/server-side data structures and interchanged messages between them.

2.2.2. Mobile Client Data Structures

Each client maintains a local subset of the global query database (called GQT) in server:

• (i)

Resident domain ( $RD$ ) is a unique spatial region which guarantees that MC's current location $\dot{p}$ is always enclosed by its $RD$ . Local query table ( $LQT$ ) is a cached subset of $GQT$ with respect to $RD$ . More clearly, $LQT=\{q\in GQT\mathrm{\hspace{0.17em}\hspace{0.17em}}|\mathrm{\hspace{0.17em}\hspace{0.17em}}q.qr\cap RD\ne \varnothing \}$ and each of its entries is form of $〈qid,qr〉$ . Each MC's $capacity$ indicates its processing power ( $capacity\ge \left|LQT\right|$ ).

(ii)

Monitoring result ( $MR$ ) is a set of queries intersecting with MC's location $\dot{p}$ at current time $\dot{t}$ (we assume that every MC and server share synchronized clocks $\dot{t}$ ).

(iii)

Locally preevaluated query result ( $LPQR$ ) is $oid$ 's original source of PQR and a sorted list of locally preevaluated results (or predicted points) in ascending order of  t. Each point is computed by linear prediction using motion vector $\bar{v}$ , and similar to PQR entry it is represented as a tuple $〈p(x,y),\underrightarrow{t},flag,qid,sq〉$ with the same meaning.

For supporting server to efficiently filter out “expired” PQR entries, each MC timestamped its LPQR entries using its $sqGen$ , a monotonic increasing sequence generator. Actually, PQR is the aggregated global view of all LPQRs that are reported to server and appended into PQR whenever updates occur. Each MC synchronously consumes $p_i\in LPQR$ and updates its $MR$ , whenever server does $p_i\in PQR$ . For denoting the end of preevaluation, the last LPQR entry's $flag$ should be “end.”

2.3. Server-Side Processing

In server, query manager manages monitoring queries in GQT and QI, while result refresher does the up-to-date query results from MCs.

2.3.1. Query Management with Query Index

Algorithm 1 describes ServerMessageHandler() needed to deal with 3 messages for query management with query index (in the following, messages handled by MessageHandler() are denoted as [[MessageName ( ${arg}_{\mathrm{1}},{arg}_{\mathrm{2}},\dots$ )]]). Once a monitoring query is issued (or deleted) by a user using [[InsertQuery ( $q〈qid,qr〉$ )]] (or [[DeleteQuery ( $q〈qid,qr〉$ )]]), it should be registered (or deleted) in the server's GQT and QI and then notified to the relevant MCs via broadcasting (without loss of generality, we assume one-to-all broadcasting via wireless channel without base station-level filtering discussed in [13]. We also do not consider communication delay and failures). In order to efficiently manage monitoring queries, as our query index (QI), we exploit BP-tree scheme with center split approach proposed in [8]. As shown in Figure 4, domain D is recursively partitioned along x- and y-axis in turn, into a set of subdomains until each subdomain contains fewer queries than leaf node's capacity. Capacity of BP-tree's leaf node is predefined, which is strongly related to MC's minimum processing capacity. Once a new query $q〈qid,qr〉$ is inserted, its fraction $qr\cap D_i$ should be inserted into every subdomain $D_i$ intersecting with it. When an MC requests its effective subset (RD and LQT) with its location and computational capacity ([[RequestRD ( $oid$ , p, $capacity$ )]]), the server should be able to respond with [[UpdateRD ( $RD$ , $LQT$ )]] by searching QI in a top-down manner. See [8] for more details about BP-tree.

Algorithm 1: Query management with query index in server.

// Performed upon receiving the following messages

ServerMessageHandler()

(1) Upon receiving [[InsertQuery ( $q〈qid,qr〉$ )]]:: // from applications

(2)    Insert $q〈qid,qr〉$ into QI and GQT;

(3)    BroadcastMsg([[AddQuery ( $q〈qid,qr〉$ )]]);

 

(4) Upon receiving [[DeleteQuery ( $q〈qid,qr〉$ )]]:: // from applications

(5)    Delete $q〈qid,qr〉$ from GQT and QI;

(6)    BroadcastMsg([[RemoveQuery ( $q〈qid,qr〉$ )]]);

 

(7) Upon receiving [[RequestRD ( $oid$ , p, capacity)]]:: // from an MC with $oid$

(8)    Perform a top-down search until domain node's size ≤ capacity; Choose RD and LQT;

(9)    SendMsg( $oid$ , [[UpdateRD (RD, LQT)]]);

Figure 4

BP-tree with center split (the leaf node's capacity is 4): (a) domain partitioning, (b) BP-tree directory structure.

2.3.2. Scheduled Broadcasting

Broadcasting every update in GQT is required to maintain consistency between server and MCs. In order to optimize the broadcasting frequency, each update is scheduled to be broadcasted in a batch with a certain broadcast interval ω. With the expected latency of $\omega /\mathrm{2}$ , this can reduce the number of broadcasts as well as the communication cost. As a primitive, BroadcastMsg (msg) enqueues the update message msg into server's broadcast queue which maintains all updates in time window of $[\dot{t}-accQ+\mathrm{1},\dot{t}]$ (called broadcast window) (lines 3, 6 in Algorithm 1). Determining $accQ$ and ω is an optimization problem with communication cost, query responsiveness, and disconnection time by selective sleep-off (cf. Section 2.4.3).

2.3.3. Management of Query Results

As a distributed query processor, each MC asynchronously sends its query results, [[UpdateQueryResults ( $oid$ , $MR$ , $LPQR$ )]] where $MR$ and $LPQR$ are current and predictive results, respectively, whenever its new location invalidates the previous results. Algorithm 2 shows how to maintain up-to-date query results at server by receiving preevaluated results from MCs. Current query result ( $MR$ ) at $\dot{t}$ is registered in the cross-referenced $OT[oid].qlist$ and $GQT[qid].olist$ (lines 1–6, Algorithm 2). Predictive query results ( $LPQR$ ) for $t>\dot{t}$ are enheaped into PQR (lines 7-8, Algorithm 2). At each time $\dot{t}$ , ServerProcessing() will process all PQR entries with $t\le \dot{t}$ and refresh the cross-referenced query results in OT and GQT (lines 10–20, Algorithm 2).

Algorithm 2: Management of query results in server.

// Performed upon receiving the following messages

ServerMessageHandler()

(1) Upon receiving [[UpdateQueryResults ( $oid$ , MR, LPQR)]]::

(2)   foreach   $qid\in OT[oid].qlist$   do

(3)     $GQT[qid].olist\leftarrow GQT[qid].olist\setminus \left\{oid\right\}$ ;

(4)    $OT[oid].qlist\leftarrow$ MR;

(5)   foreach   $qid\in OT[oid].qlist$   do

(6)     $GQT[qid].olist\leftarrow GQT[qid].olist\cup \left\{oid\right\}$ ;

(7)   foreach   $p\in LPQR$   do // Enheap all LPQR entries into PQR

(8)     $PQR.enheap(〈oid\parallel p〉)$ ;

(9)    $OT[oid].s{q}_{\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}\leftarrow \min (e.sq,\forall e\in LPQR)$ ; // update OT

 

ServerProcessing() // Result refreshing in server

(10) while   $PQR.top.t\le t_{\mathrm{n}\mathrm{o}\mathrm{w}}$   and   $PQR\ne \mathrm{\varnothing }$   do

(11)    $e\leftarrow PQR.deheap()$ ;

(12)   if   $OT[e.oid].s{q}_{\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}>e.sq$   then continue; // expired PQR entry

(13)   if   $e.flag=$   enter  then

(14)     $GQT[e.qid].olist\leftarrow GQT[e.qid].olist\cup \left\{e.oid\right\}$ ;

(15)     $OT[e.oid].qlist\leftarrow OT[e.oid].qlist\cup \left\{e.qid\right\}$ ;

(16)   else if   $e.flag=$   exit  then

(17)     $GQT[e.qid].olist\leftarrow GQT[e.qid].olist\setminus \left\{e.oid\right\}$ ;

(18)     $OT[e.oid].qlist\leftarrow OT[e.oid].qlist\setminus \left\{e.qid\right\}$ ;

(19)   end-if

(20) end-while

Receiving [[UpdateQueryResults ( $oid$ , $MR$ , $LPQR$ )]] and inserting new LPQR entries keep/sustain expired PQR entries. The purging cost for removing all previous PQR entries immediately is very expensive. Alternatively, based on Lemma 1, we can minimize the purging cost by adopting a timestamp-based approach.

Lemma 1 (expired PQR entry).

A PQR entry e is expired (and should be removed) iff its sequence number $e.sq$ is smaller than its $s{q}_{valid}$ in $OT$ (i.e., $OT[e.oid].s{q}_{valid}>e.sq$ ).

Proof.

It is omitted for brevity.

Every PQR entry is timestamped with a unique sequence number $sq$ generated by each MC's $sqGen$ , and the minimum $sq$ of all valid PQR entries is preserved in $OT.s{q}_{\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}$ (line 9, ServerMessageHandler()). By Lemma 1, those expired PQR entries with smaller $sq$ than $OT.s{q}_{\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}$ can easily be removed whenever they are deheaped; the purging cost is thus minimized negligibly (line 12, ServerProcessing()).

2.4. Mobile Client-Side Processing

Each MC's query manager keeps its LQT up to date according to $\dot{p}$ and server's GQT, and query processor evaluates and sends query results in a real-time manner as necessary.

2.4.1. Query Management

Algorithm 3 describes query management of MC. Each MC initializes its local query subset by invoking MobileClientInit() which sends $\dot{p}$ and $capacity$ to the server (line 1, Algorithm 3) and then receives $RD$ and $LQT$ (lines 2, 8-9, Algorithm 3). After that, MC computes $MR$ and $LPQR$ and then sends them back to the server (lines 3-4, 5–7, Algorithm 3). MC's LQT is always synchronized by the broadcasted messages from server that modify the GQT of server (lines 10–19, Algorithm 3).

Algorithm 3: Query management in MCs.

MobileClientInit() // Invoked upon power on

(1) SendMsg(server, [[RequestRD ( $oid$ , $\dot{p}$ , capacity)]]);

(2) ReceiveMsg(server, [[UpdateRD ( $R{D}^{\prime }$ , $LQ{T}^{\prime }$ )]]);

(3) $MR\leftarrow \mathrm{\varnothing }$ ; $LPQR\leftarrow \mathrm{\varnothing }$ ;

(4) SendUpdateMsg();

 

SendUpdateMsg()

(5) $MR\leftarrow$   ComputeMR( $\dot{p}$ );

(6) $LPQR\leftarrow$   ComputeLPQR( $\dot{p}$ );

(7) SendMsg(server, [[UpdateQueryResults ( $oid$ , MR, LPQR)]]);

 

// Performed upon receiving the following messages

MobileClientMessageHandler()

(8) Upon receiving [[UpdateRD ( $R{D}^{\prime }$ , $LQ{T}^{\prime }$ )]]::

(9)    $RD\leftarrow R{D}^{\prime }$ ; $LQT\leftarrow LQ{T}^{\prime }$ ;

 

(10) Upon receiving [[AddQuery ( $q〈qid,qr〉$ )]]::

(11)   if   $q.qr\cap RD\ne \mathrm{\varnothing }$   then

(12)   if   $|LQT|+\mathrm{1}>capacity$

(13)      then  Invoke MobileClientInit();

(14)      else   $LQT\leftarrow LQT\cup \left\{q\right\}$ ;

(15)        if   $q.qr\cap l_{\mathrm{D}\mathrm{R}}\ne \mathrm{\varnothing }$   then  SendUpdateMsg();

 

(16) Upon receiving [[RemoveQuery ( $q〈qid,qr〉$ )]]::

(17)   if   $q\in LQT$   then

(18)    Delete $q〈qid,qr〉$ from LQT;

(19)    if   $q.qr\cap l_{\mathrm{D}\mathrm{R}}\ne \mathrm{\varnothing }$   then  SendUpdateMsg();

2.4.2. Query Processing with Movement Handling

Each MC continuously monitors the spatial relationship between its location $\dot{p}$ and its local query subset (i.e., $LQT$ ). If the relationship breaks the preevaluated $LPQR$ , MC should recompute $MR$ and $LPQR$ and then sends them to server.

Integrity Requirements. As a distributed query processor, each MC has to meet the following requirements properly:

• (i)

R1: $\dot{p}\in RD$ .

(ii)

R2: $LPQR\ne \varnothing$ .

(iii)

R3: $LPQR.top.t>\dot{t}$ , where $LPQR.top$ is LPQR's top entry.

(iv)

R4: during $LPQR.top.t>\dot{t}$ , MR should be maintained.

(v)

R5: at $LPQR.top.t=\dot{t}$ , $|LPQR.top.p,\dot{p}|\le \delta$ .

Algorithm 4 describes MC-side query processing, and this can be explained in corresponding actions for holding each requirement. First, R1 is clearly satisfied by reinvoking MobileClientInit() every time an MC gets new RD (line 4, Algorithm 4). R2 and R5 are also done by invoking SendUpdateMsg() which recomputes MR/LPQR and sends them to the server (lines 11-12, Algorithm 4). R3 does hold by deheaping every LPQR entry with $LPQR.top.t\le \dot{t}$ (lines 9–17, Algorithm 4). During $LPQR.top.t>\dot{t}$ , in order to hold R4, SendUpdateMsg() is invoked if $MR$ is changed (lines 5–7, Algorithm 4). Selective sleep-off (lines 2-3, Algorithm 4) will be discussed in Section 2.4.3.

Algorithm 4: Query processing with movement handling in MCs.

MobileClientProcessing()

(1) forever do  // at each discrete time slot $\dot{t}$

(2)    $t_{\mathrm{s}\mathrm{l}\mathrm{e}\mathrm{e}\mathrm{p}}\leftarrow$   ComputeSafeSleepTime( $\dot{p}$ );

(3)   Sleep $\min (t_{\mathrm{m}\mathrm{a}\mathrm{x}\_\mathrm{s}\mathrm{l}\mathrm{e}\mathrm{e}\mathrm{p}},t_{\mathrm{s}\mathrm{l}\mathrm{e}\mathrm{e}\mathrm{p}})$ times, then wake up;

(4)   if   $\dot{p}\notin RD$   then  MobileClientInit();

(5)   if ( $LPQR.top.t>\dot{t}$ )  then

(6)    $M{R}^{\prime }\leftarrow$   ComputeMR( $\dot{p}$ );

(7)   if  ( $MR\ne M{R}^{\prime }$ )  then  SendUpdateMsg();

(8)   else  // $LPQR.top.t\le \dot{t}$

(9)   while   $LPQR.top.t\le \dot{t}$   and   $LPQR\ne \mathrm{\varnothing }$   do

(10)      $e\leftarrow LPQR.deheap()$ ;

(11)     if   $e.flag=$   end  or   $|e.p,\dot{p}|>\mathrm{\delta }$   then

(12)     SendUpdateMsg();

(13)     else // $e.flag=$   enter/exit  and   $|e.p,\dot{p}|\le \mathrm{\delta }$

(14)     if   $e.flag=$   enter

(15)        then   $MR\leftarrow MR\cup \left\{e.qid\right\}$ ;

(16)        else   $MR\leftarrow MR\setminus \left\{e.qid\right\}$ ;

(17)    end-while

(18) end-forever

 

ComputeMR(p)

(19) return   $\left\{qid\hspace{0.17em}|\hspace{0.17em}e〈qid,qr〉\in LQT\hspace{0.17em}\hspace{0.17em}\mathrm{a}\mathrm{n}\mathrm{d}\hspace{0.17em}\hspace{0.17em}p\cap qr\ne \mathrm{\varnothing }\right\}$ ;

 

ComputeLPQR(p)

(20) Let P be a heap, $P\leftarrow \mathrm{\varnothing }$ ;

(21) $p_{\mathrm{e}\mathrm{n}\mathrm{d}}\leftarrow$ the point intersected with RD; $P.enheap(p_{\mathrm{e}\mathrm{n}\mathrm{d}})$ ;

(22) Let $l_{\mathrm{D}\mathrm{R}}$ be a line segment consiting of two points $p_{\mathrm{r}\mathrm{e}\mathrm{f}}$ and $p_{\mathrm{e}\mathrm{n}\mathrm{d}}$ ;

(23) foreach   $LQT[i]\in LQT$ intersecting with $l_{\mathrm{D}\mathrm{R}}$   do

(24)  Compute $p_{\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}}$ and $p_{\mathrm{e}\mathrm{x}\mathrm{i}\mathrm{t}}$ of $LQT[i]$ if exists;

(25)   $P.enheap(\{p_{\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}},p_{\mathrm{e}\mathrm{x}\mathrm{i}\mathrm{t}}\})$ ;

(26) end-foreach

(27) return  P;

 

ComputeSafeSleepTime(p)

(28) return   $\min (minperdist(p,R)$ , $R\in \left\{LQT\cup RD\right\})/v_{\mathrm{m}\mathrm{a}\mathrm{x}}$ ;

Bulk Preevaluation by Dead-Reckoning (DR). Query preevaluation performed by ComputeLPQR(p) (lines 20–27) is the key of the proposed technique for improving the query processing power. Dead-Reckoning (DR) is the most popular method to estimate moving objects' location, and its underlying principle is the piecewise linear movements [9]. The object's estimated location at any future time t can be obtained as $\widehat{p}(t)=p_{\mathrm{r}\mathrm{e}\mathrm{f}}+\bar{v}·(t-t_{\mathrm{r}\mathrm{e}\mathrm{f}})$ , where $p_{\mathrm{r}\mathrm{e}\mathrm{f}}$ is a reference point at some reference time $t_{\mathrm{r}\mathrm{e}\mathrm{f}}$ ( $t>t_{\mathrm{r}\mathrm{e}\mathrm{f}}$ ) and $\bar{v}$ is a movement vector. As illustrated in Figure 5, MC computes all intersected points with the predicted line segment $l_{\mathrm{D}\mathrm{R}}$ which is always cropped by RD, timestamps them with increasing $sq$ , and then sends them. At this point, the smallest $sq$ is preserved as $s{q}_{valid}$ (1 for $l_{\mathrm{D}\mathrm{R}}$ and 5 for $l_{\mathrm{D}\mathrm{R}}^{\prime }$ ). In 2nd preevaluation with $l_{\mathrm{D}\mathrm{R}}^{\prime }$ , all expired points that have smaller $sq$ than $l_{\mathrm{D}\mathrm{R}}^{\prime }$ 's $s{q}_{\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}}$ will efficiently be removed by Lemma 1 (e.g., they are 3rd and 4th points of $Q_{\mathrm{2}}$ ).

Figure 5

Query preevaluation by Dead-Reckoning (DR).

2.4.3. Selective Sleep-Off

In order to reduce energy consumptions, MC selectively sleeps off whenever possible (lines 2-3, Algorithm 4). Each MC is able to compute the amount of maximum sleepable time which does not break the abovementioned 5 requirements (line 28, ComputeSafeSleepTime()).

Definition 2 (MINPERDIST).

The minimum perimeter distance of a point $p=(p_{\mathrm{1}},p_{\mathrm{2}},\dots ,p_d)$ to the perimeters of a rectangle $R=\left[l_{\mathrm{1}},u_{\mathrm{1}}\right]\times \cdots \times [l_d,u_d]$ , denoted as $minperdist(p,R)$ , is

$$\begin{array}{cc}& minperdist\left(p,R\right)=\left\{\begin{array}{cc}\stackrel{d}{\underset{i=\mathrm{1}}{\mathrm{m}\mathrm{i}\mathrm{n}}}\min \left(\left|u_i-p_i\right|,\left|p_i-l_i\right|\right),\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}q\in R;\hfill \\ mindist\left(p,R\right),\hfill & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\hfill \end{array}\right.=\left\{\begin{array}{cc}\stackrel{d}{\underset{i=\mathrm{1}}{\mathrm{m}\mathrm{i}\mathrm{n}}}\min \left(\left|u_i-p_i\right|,\left|p_i-l_i\right|\right),\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}q\in R;\hfill \\ \sqrt{{\displaystyle \sum }_{i=\mathrm{1}}^d{\left(\left\{\begin{array}{cc}\left|l_i-p_i\right|,\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}{p}_i<l_i;\hfill \\ \left|p_i-u_i\right|,\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}{u}_i<p_i;\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}\right.\right)}^{\mathrm{2}}},\hfill & \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e},\hfill \end{array}\right.\end{array}$$

(1)

where d is dimensionality and $mindist(p,R)$ is the minimum distance of rectangle R from point p [14]. We only consider the case of $d=\mathrm{2}$ .

Lemma 3 ( $\mathrm{S}\mathrm{a}\mathrm{f}\mathrm{e}\mathrm{S}\mathrm{l}\mathrm{e}\mathrm{e}\mathrm{p}\mathrm{T}\mathrm{i}\mathrm{m}\mathrm{e}$ ).

With the known maximum velocity $v_{\mathrm{m}\mathrm{a}\mathrm{x}}$ of an MC at current location $\dot{p}$ , it is guaranteed that during $SafeSleepTime$ , MC's movement does not break any requirement for maintaining accurate query results. Thus, it is safe to switch into sleep mode for $\mathrm{m}\mathrm{i}\mathrm{n}(t_{\mathrm{m}\mathrm{a}\mathrm{x}\_\mathrm{s}\mathrm{l}\mathrm{e}\mathrm{e}\mathrm{p}},SafeSleepTime)$ times, and $SafeSleepTime$ is defined as the amount of time to the nearest minperdist query with $v_{\mathrm{m}\mathrm{a}\mathrm{x}}$ :

$$\begin{array}{cc}& SafeSleepTime=\frac{SleepDist}{v_{\mathrm{m}\mathrm{a}\mathrm{x}}}=\frac{\min \left(minperdist\left(\dot{p},R\right),R\in \left\{LQT\cup RD\right\}\right)}{v_{\mathrm{m}\mathrm{a}\mathrm{x}}},\end{array}$$

(2)

where $SleepCircle$ in Figure 6 is a circle centered at the current location $\dot{p}$ with radius $SleepDist$ .

Figure 6

Illustration of SleepDist, SleepCircle, and $SafeSleepTime$ ( $=SleepDist/v_{\mathrm{m}\mathrm{a}\mathrm{x}}$ ).

Proof.

It is omitted for brevity.

Based on Lemma 3, MCs can sleep off for $SafeSleepTime$ to save considerable energy consumption only if $SafeSleepTime>t_{\text{min\_sleep}}$ ( $t_{\text{min\_sleep}}$ is the minimum amount of time to compensate the energy consumption for sleep-off/wake-up, and this can simply be 0 for brevity), and this may result in deteriorated query responsiveness by missing newly incoming queries from server's broadcasting channel. As we already discussed in Section 2.3.2, the server periodically broadcasts updates in GQT with interval ω, and each broadcast covers $accQ$ times back from $\dot{t}$ (see Figure 7). To control the deterioration by selective sleep-off, $t_{\text{sleep}}$ should be limited by defining its lower- and upper-bound, $t_{\text{sleep}}\in [t_{\text{min\_sleep}},t_{\text{max\_sleep}}]$ , being optimized between energy efficiency and query responsiveness.

Figure 7

Scheduled broadcasting with interval ω.

To ensure the consistency between server's $GQT$ and MCs' $LQT$ s, each MC must obey the following rules. (1) The safely sleepable time $SafeTime\le t_{\text{max\_sleep}}$ . (2) Once woken up, each MC cannot sleep off before it received the next broadcasted message. The worst latency for the next broadcast is simply its interval ω. (3) Thus, the size of broadcast window ( $accQ$ ) should be big enough to cover the maximum sleepable time ( $t_{\text{max\_sleep}}$ ) and the worst case latency (ω); that is, $accQ\ge t_{\text{max\_sleep}}+\omega$ (ω can be different for various real-life applications).

3. Localized Query Optimizations in MCs

As long as the above 5 requirements (in Section 2.4.2) hold, we can defer any kind of operations for reducing communication and computation costs. In Sleepwalk technique, query processing is performed on MCs in a fully distributed manner. For MCs, the most frequently performed operation is MobileClientProcessing() where three iterative searches over $LQT$ for $MR$ , $LPQR$ , and $SafeTime$ , ComputeMR(), ComputeLPQR(), and ComputeSafeSleepTime(), are performed. A popular way to improve search efficiency is to create an additional index (e.g., R-trees [12]) over $LQT$ . However, this is not feasible on resource-scarce mobile devices since it surely incurs high maintenance costs. Rather, increasing $\left|LQT\right|$ can be more profitable from a performance perspective. In this section, we will discuss a plane-sweep based optimization technique for these operations without any additional indexes over $LQT$ .

In order to exploit plane-sweeping technique, we assume that $LQT$ is sorted, by the server when it is chosen, along x-axis (resolving ties by sorting y-axis). The ith query in $LQT$ is denoted as $LQT[i]$ where $i\in [\mathrm{0},|LQT|-\mathrm{1}]$ . Only insertions and deletions in $LQT$ are performed on mobile clients. Consequently, the overall computational overhead is quite low as $\mathcal{O}(|LQT\left|\mathrm{l}\mathrm{o}\mathrm{g}\right|LQT|+|LQT|)$ where $\left|LQT\right|$ is the number of queries stored in the mobile client.

Definition 4 (nearest lower/upper rectangle index).

Given a point $p\in RD$ , its nearest lower rectangle index $\mathrm{N}\mathrm{L}\mathrm{R}(p)$ and nearest upper rectangle index $\mathrm{N}\mathrm{U}\mathrm{R}(p)$ are formally defined as follows:

$$\begin{array}{cc}& \mathrm{N}\mathrm{L}\mathrm{R}\left(p\right)=\mathrm{m}\mathrm{a}\mathrm{x}\hspace{1em}\left(\underset{i\in \left[\mathrm{0},\left|\mathrm{LQT}\right|-\mathrm{1}\right]}{\arg \hspace{0.17em}\min }\left(p.x-LQT\left[i\right].hx\right)\right)\\ \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\hspace{0.17em}\hspace{0.17em}\mathrm{t}\mathrm{o}\hspace{1em}p.x-LQT\left[i\right].hx>\mathrm{0},\\ \mathrm{N}\mathrm{U}\mathrm{R}\left(p\right)=\mathrm{m}\mathrm{i}\mathrm{n}\hspace{1em}\left(\underset{i\in \left[\mathrm{0},\left|\mathrm{LQT}\right|-\mathrm{1}\right]}{\arg \hspace{0.17em}\min }\left(LQT\left[i\right].lx-p.x\right)\right)\\ \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\hspace{0.17em}\hspace{0.17em}\mathrm{t}\mathrm{o}\hspace{1em}LQT\left[i\right].lx-p.x>\mathrm{0}.\end{array}$$

(3)

Given a point p, its $\mathrm{N}\mathrm{L}\mathrm{R}$ / $\mathrm{N}\mathrm{U}\mathrm{R}$ can be computed as follows: first, it performs a forward scan from $LQT[\mathrm{0}]$ until $LQT[i].lx<p.x$ ; then $\mathrm{N}\mathrm{U}\mathrm{R}(p)\leftarrow (i+\mathrm{1})$ . During this operation, it repeatedly updates $\mathrm{N}\mathrm{L}\mathrm{R}(p)\leftarrow i$ only if $LQT[i].hx\in (LQT[\mathrm{N}\mathrm{L}\mathrm{R}(p)].hx,p.x)$ . For example, $\mathrm{N}\mathrm{L}\mathrm{R}(\dot{p})$ and $\mathrm{N}\mathrm{U}\mathrm{R}(\dot{p})$ in Figure 9 are $LQT[\mathrm{9}]$ and $LQT[\mathrm{16}]$ , respectively. By definition, $\mathrm{N}\mathrm{L}\mathrm{R}$ and $\mathrm{N}\mathrm{U}\mathrm{R}$ are greatly impacted by the extent/sizes of queries. For more optimized search boundary for $\mathrm{N}\mathrm{L}\mathrm{R}$ / $\mathrm{N}\mathrm{U}\mathrm{R}$ , narrow extent is preferred. From computational cost viewpoint for computing $\mathrm{N}\mathrm{L}\mathrm{R}(p)$ and $\mathrm{N}\mathrm{U}\mathrm{R}(p)$ , optimal axis is

$$\begin{array}{cc}& opt\_axis=\underset{i\in \left\{x,y\right\}}{\arg \hspace{0.17em}\min }\left(\frac{{\sum }_{LQT\left[j\right]\in LQT}^{}\left(LQT\left[j\right]\text{'s}\hspace{0.17em}\hspace{0.17em}i\mathrm{t}\mathrm{h}\hspace{0.17em}\hspace{0.17em}\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{e}\mathrm{n}\mathrm{t}/RD\text{'s}\hspace{0.17em}\hspace{0.17em}i\mathrm{t}\mathrm{h}\hspace{0.17em}\hspace{0.17em}\mathrm{e}\mathrm{x}\mathrm{t}\mathrm{e}\mathrm{n}\mathrm{t}\right)}{\left|LQT\right|}\right).\end{array}$$

(4)

3.1. Optimizations for ComputeSafeSleepTime()

ComputeSafeSleepTime() is to choose $LQT[i]\in LQT$ which minimizes $SleepCircle$ and its radius $SleepDist$ . As depicted in Figure 8, it can be optimized by computing $\mathrm{N}\mathrm{U}\mathrm{R}$ of the rightmost point of $SleepCircle$ . Initially, we set $SleepDist=minperdist(\dot{p},RD)$ and then perform a forward scan until $SleepDist+\dot{p}.x<LQT[i].lx$ simultaneously updating $SleepDist$ as $\mathrm{m}\mathrm{i}\mathrm{n}(SleepDist,minperdist(\dot{p},LQT[i]))$ . Finally, $SafeTime=SleepDist/v_{\mathrm{m}\mathrm{a}\mathrm{x}}$ . Note that $SafeTime$ is always recomputed due to its dependency on $\dot{p}$ .

Figure 8

Search boundary for ComputeSafeSleepTime ().

Figure 9

Search boundary $MRB$ and safe region $SR$ for ComputeMR().

3.2. Optimizations for ComputeMR()

The most frequently invoked procedure is ComputeMR() which returns a set of queries intersecting with given point p (line 21, Algorithm 4). It should be invoked at each time $\dot{t}$ to hold R4. By exploiting the notion of $\mathrm{N}\mathrm{L}\mathrm{R}$ / $\mathrm{N}\mathrm{U}\mathrm{R}$ , we can minimize the search space for computing $MR$ . By definition, the monitoring query result ( $MR$ ) only exists in $LQT(\mathrm{N}\mathrm{L}\mathrm{R}(\dot{p}),\mathrm{N}\mathrm{U}\mathrm{R}(\dot{p}))$ . We call the interval $[LQT[\mathrm{N}\mathrm{L}\mathrm{R}(\dot{p})].hx,LQT[\mathrm{N}\mathrm{U}\mathrm{R}(\dot{p})].lx]\mathrm{\hspace{0.17em}\hspace{0.17em}}MR$ -boundary; based on this, we can optimize ComputeMR() by minimizing its search space:

• (i)

Initially, compute $\mathrm{N}\mathrm{L}\mathrm{R}(\dot{p})$ and $\mathrm{N}\mathrm{U}\mathrm{R}(\dot{p})$ .

(ii)

Then, by referring to current location $\dot{p}$ and next location $p^{\prime }$ , it is possible to have proper new $MR$ and $MR$ -boundary by searching optimized search space ( $MR$ -boundary $\equiv \mathrm{\hspace{0.17em}\hspace{0.17em}}MRB$ ):

• (a)

Case of $p^{\prime }.x<MRB.lx$ ( $p_{\mathrm{1}}^{\prime }$ ): perform a forward scan from $LQT[\mathrm{0}]$ .

(b)

Case of $p^{\prime }.x\in MRB$ ( $p_{\mathrm{2}}^{\prime }$ ): perform a forward scan from $LQT[\mathrm{N}\mathrm{L}\mathrm{R}(\dot{p})]$ .

(c)

Case of $p^\prime \mathrm{\hspace{0.17em}\hspace{0.17em}}.x>MRB.hx$ ( $p_{\mathrm{3}}^{\prime }$ ): perform a forward scan from $LQT[\mathrm{N}\mathrm{U}\mathrm{R}(\dot{p})]$ .

3.2.1. Deferring the Update of $MR$ and $MR$ -Boundary with Safe Region

Although this optimization effectively minimizes the search space for ComputeMR(), it should be still performed always and sometimes performed for unchanged MR (in the worst case). In order to better computational efficiency, we can defer the update of $MR$ and $MR$ -boundary by exploiting a circular-shaped safe region which is the same as in [7] geometrically. Its uniqueness came from the fact that our safe region is computed not in the server but in MCs; moreover it is not for reducing communication cost, but for computational cost of MCs. Simply speaking, safe region and MR-boundary are maintained unless $p^{\prime }\notin safe\_region$ . As depicted in Figure 9, the safe region can go beyond the MR-boundary. Moreover, the notion of safe region is capable of relaxing R2 ( $LPQR\ne \varnothing$ ); that is, each MC simply does nothing without recomputing $MR$ when $LPQR=\varnothing$ and $p^{\prime }\in safe\_region$ . This will be very effective in a huge free space and the skewed distribution of monitoring queries.

3.3. Optimizations for ComputeLPQR()

As illustrated in Figure 10, optimization of ComputeLPQR() is quite similar to that of ComputeMR(). $\mathrm{N}\mathrm{L}\mathrm{R}$ and $\mathrm{N}\mathrm{U}\mathrm{R}$ of line segment $l_{\mathrm{D}\mathrm{R}}=(s,e)$ can be obtained from its start and end points (s and e, resp); that is, $\mathrm{N}\mathrm{L}\mathrm{R}(l_{\mathrm{D}\mathrm{R}})=\mathrm{N}\mathrm{L}\mathrm{R}(s)$ and $\mathrm{N}\mathrm{U}\mathrm{R}(l_{\mathrm{D}\mathrm{R}})=\mathrm{N}\mathrm{U}\mathrm{R}(e)$ . For correctness and simplicity, swap s and e when e precedes s along with the sorting axis. Based on the interval $[LQT[\mathrm{N}\mathrm{L}\mathrm{R}(s)].hx,LQT[\mathrm{N}\mathrm{U}\mathrm{R}(e)].lx]$ (called $LPQR$ -boundary), we can optimize ComputeLPQR() by minimizing its search space:

• (i)

Initially, compute $\mathrm{N}\mathrm{L}\mathrm{R}(l_{\mathrm{D}\mathrm{R}})$ and $\mathrm{N}\mathrm{U}\mathrm{R}(l_{\mathrm{D}\mathrm{R}})$ .

(ii)

Then, by referring to current line segment $l_{\mathrm{D}\mathrm{R}}$ and next line segment $l_{\mathrm{D}\mathrm{R}}^{\prime }=(s^{\prime },e^{\prime })$ , it is possible to have proper new $LPQR$ and $LPQRB$ by searching optimized search space.

• (a)

Case of $s^{\prime }.x<LPQRB.lx$ : perform a forward scan from $LQT[\mathrm{0}]$ .

(b)

Case of $s^{\prime }.x\in LPQRB$ : perform a forward scan from $LQT[\mathrm{N}\mathrm{L}\mathrm{R}(l_{\mathrm{D}\mathrm{R}})]$ .

(c)

Case of $s^{\prime }.x>LPQRB.hx$ : perform a forward scan from $LQT[\mathrm{N}\mathrm{U}\mathrm{R}(l_{\mathrm{D}\mathrm{R}})]$ .

Owing to the forward scan-based searches over $LQT$ , this optimization is related with the start point s only. As shown in Figure 10, another optimization is to check only $LQT[i]$ intersecting with $l_{\mathrm{D}\mathrm{R}}$ 's minimum bounding rectangle ( $MBR(l_{\mathrm{D}\mathrm{R}})$ ).

Figure 10

Search boundary for ComputeLPQR().

4. Performance Evaluation

This section describes the experiments we have carried out to evaluate the proposed technique.

4.1. Experiment Setup

We evaluate the performance of the existing Q-index [7], MQM techniques [8], and the proposed Sleepwalk technique in terms of the following performance metrics:

• (i)

Power consumption of mobile clients: this cost is measured as the number of messages sent by the client and the amount of time for sleep-off during processing continuous range queries. As the sleep-off time increases, the CPU of client can be in the sleep mode for conserving battery consumption. For measuring power consumption, we use the reference values in Table 1 describing the power consumption of representative components [10]. The power consumption is measured by the unit energy which is the amount of power consumption per second in sleep mode. In this experiment, the unit energy is assumed as 0.16 mW [10].

(ii)

Server processing cost: this cost is defined as the total number of data accesses (including query index, global query table, precomputed query table, and object table) in server in order to evaluate the same number of range queries. The size of the BP-tree leaf node is set to be 50 rectangles as in [8]. For realistic experiment, LRU cache is applied for the BP-tree of the server; this makes most of nonleaf nodes reside in the buffer when query pattern is uniform. In this experiment, the access cost of the BP node is assumed to be the same as that of other tables.

Table 1

The components of example MC (in mW) [10].

	Model	Sleep	Active	Receive	Transmit
CPU	StrongARM SA-1100	0.16	400	—	—
Network	RangeLAN2 7401/02	25	—	750	1,500
GPS	μ-blox GPS-MS1E	33	462	—	—

In this work, the concept of safe region exploited in Q-index technique [7] is implemented as follows: With a given location of a mobile object, we first search query index (i.e., BP-tree) for finding the subdomain containing the location. Then we compute the largest rectangular region as the safe region for the object, such that the region does not overlap with the boundaries of any query [7].

For more realistic experiments, we use two different ways of generating mobility patterns of mobile objects. One is to exploit mobility simulator which simulates the movements of real-world objects. We use the network-based generator of moving objects [15] (described as NETWORK dataset). Another is to trace the movements of real user (described as TRACE dataset). For the NETWORK dataset, every object moves along the road network Oldenburge, Germany, in the normalized data space $[\mathrm{0,100}\hspace{0.17em}\mathrm{k}{]}^{\mathrm{2}}$ . The number of mobile objects varies from 100 to 10 k, and their speed varies from 10 to 30 per simulation time (default speed 10). The number of query rectangles varies from 1 k to 100 k, and the size is from [10 × 10] to [500 × 500]. And the overall experiment time is 10 k unit times. For the TRACE dataset, we trace the real movement of a user for 6 hours in Suwon, Korea. The tracked trajectory is normalized into the same data space of $[\mathrm{0,100}\hspace{0.17em}\mathrm{k}{]}^{\mathrm{2}}$ . The number of query rectangles is the same as for the NETWORK dataset. And the overall experiment time is also normalized 10 k unit times. Experiment parameters and their default values, in bold, are summarized in Table 2.

Table 2

Experimental parameters and their values.

Parameters	Value used (default) [DATASET]
Data space	[0, 100 k] × [0, 100 k]
Number of mobile objects	100~10,000 (1,000) [NETWORK]   1 [TRACE]
Speed of mobile objects	10~30 (10) [NETWORK]
Number of monitoring queries	1,000~100,000 (10,000)
Size of monitoring queries	10 × 10~500 × 500 (50 × 50)
Simulation time	10,000

All experiments were conducted on a Windows PC with an Intel Core2 Duo 3 GHz CPU and 4 GB memory. All techniques were implemented in Java language. In our implementations, every hash table was implemented using the HashMap class, and disk I/Os are performed using the RandomAccessFile class in Java 2 SE library.

4.2. Experiment Results

This section describes the experiment results as a function of the number of monitoring queries and that of moving objects.

4.2.1. Effect of the Number of Monitoring Queries

Figure 11 shows the result of evaluating the server cost and energy cost of mobile clients varying the number of monitoring queries from 1 k to 100 k with both NETWORK and TRACE datasets.

Figure 11

Effect of the number of monitoring queries.

Regarding NETWORK dataset, Figures 11(a) and 11(b) show the result of evaluating the server processing cost and the average energy consumption of mobile clients, respectively. The queries are uniformly generated; their sizes are fixed as [50 × 50]. We also generated 1,000 moving objects and their initial locations are uniformly distributed in the road network. As depicted in Figure 11(a), all three techniques incur higher server processing and communication costs as the number of queries increases. Particularly the costs of Q-index are many times higher than those of MQM and Sleepwalk techniques. With the increased number of queries, the average size of RD adpoted in MQM and Sleepwalk techniques decreases and the number of [[RequestRD]] and [[UpdateRD]] messages interchanged increases proportionally. Overall, Sleepwalk technique clearly outperforms the existing Q-index and MQM techniques in all cases. This is due to the fact that it performs query processing in bulk predictively and sends the results at once. As depicted in Figure 11(b), all three techniques suffer performance degradation with high power consumption as the number of queries increases. Due to the batch processing capability and sleep-off behavior, the proposed technique shows graceful degradation and outperforms the existing techniques. With smaller number of queries, Sleepwalk can minimize the energy cost by increasing $SafeSleepTime$ with the increased average distance between queries.

Regarding TRACE dataset, Figures 11(c) and 11(d) show the result of evaluating the server processing cost and the average energy consumption of mobile clients, respectively. TRACE dataset shows a similar trend of performance degradation when the number of queries increases. There is an important difference from NETWORK dataset; that is, in real-world situations, people tend to have large amount of inactivity time. This means people stay in some specific places such as home or work. In that case, the proposed technique has a huge benefit of maximizing sleep-off time. As already mentioned in Lemma 3, $SafeSleepTime=SleepDist/v_{\mathrm{m}\mathrm{a}\mathrm{x}}$ can be maximized to $t_{\text{max\_sleep}}$ , where $t_{\text{max\_sleep}}$ is set as 1,500 unit time (approximately 30 min) in this experiment. Thanks to this nature, the proposed technique extremely outperforms previous works especially when the smaller number of queries is applied.

4.2.2. Effect of the Number of Moving Objects

Figure 12 shows the result of evaluating the server cost and energy cost of mobile clients varying the number of moving objects from 100 to 10 k with the NETWORK dataset (in this scenario, we omit the experiment with TRACE dataset since it can only provide a single object). Figure 12(a) shows the result of evaluating the server cost varying the number of moving objects from 100 to 10 k. Their initial locations are uniformly distributed in the road network. We also generated 10 k monitoring queries, and their sizes are fixed as [50 × 50]. As the number of objects increases, all three techniques incur higher server and communication costs proportionally. In this setting, Sleepwalk technique clearly outperforms the existing Q-index and MQM techniques in all cases. Sleepwalk technique scales well because of its localized behavior of processing monitoring queries; that is, it processes the monitoring queries in bulk predictively and selectively sleeps off whenever possible. Figure 12(b) shows the result of evaluating the average energy consumption of mobile clients. The result shows that the number of objects has no effect on the average energy cost.

Figure 12

Effect of the number of objects.

4.2.3. Effect of the Size of Monitoring Queries

Figure 13 shows the result of evaluating the server cost and energy cost of mobile clients with 10 k queries varying their size from [10 × 10] to [500 × 500].

Figure 13

Effect of the size of monitoring queries.

Regarding NETWORK dataset, Figures 13(a) and 13(b) show the result of evaluating the server processing cost and the average energy consumption of mobile clients, respectively. We generated 1,000 moving objects uniformly distributed in the road network. As depicted in Figure 13(a), all three techniques suffer higher server and communication costs as the size of monitoring queries increases. This is because the probability of intersecting query rectangles increases. Q-index will frequently send update requests for safe region, and MQM technique sends frequent query updates to server. Sleepwalk technique scales well because its cost is less affected by the size of queries and more affected by the motion pattern of clients. Figure 13(b) shows the result of evaluating the average energy consumption of mobile clients with various size of queries. The result shows that all three techniques degrade their performance due to the frequent update request to the server. Overall, Sleepwalk technique is superior to the existing Q-index and MQM techniques in all cases. This is due to the fact that it performs query processing in bulk predictively and sends the results at once. More importantly, it keeps mobile clients sleep-off whenever possible. This incurs better energy cost with increased size of queries ironically due to the increased $SafeSleepTime$ to the perimeter of query rectangles.

Regarding TRACE dataset, Figures 13(c) and 13(d) show the result of evaluating the server processing cost and the average energy consumption of mobile clients, respectively. TRACE dataset also shows a similar trend as NETWORK dataset when the number of queries increases.

5. Related Work

Location-based sensing and monitoring (LBSM) is essential to various real-life applications such as location-based advertisement, traffic monitoring, surveillance, and many context-enriched services [16]. Recently, there are many studies for scalable monitoring [7, 8, 17–29].

These studies are classified into two categories based on the type of data to be managed. One category is for modeling and indexing massive number of moving objects effectively [25–29] (called moving object indexing), and the other category is for indexing queries and their results efficiently [7, 8, 17–24, 30] (called continuous query indexing).

The former is proposed to minimize the maintenance and update costs for moving object databases (MOD) [28] in the server; various approaches are proposed such as a hash-based index structure [27], bottom-up update approach for R-trees [29], and buffer-based approaches for R-trees [25, 26].

The latter is to design specialized index structures for both objects and queries for the sake of scalability; most of works focused on how to localize query processing and manage the results both in clients and in server effectively. In [7], Prabhakar et al. firstly introduce the concept of query indexing (Q-index) and safe region where an R-tree-like index on the queries instead of the objects is built. In [19], a grid-based index structure for queries is proposed to achieve the minimized server cost. The concept of safe region has huge impact on this study, and it is improved and reused in [18, 23]. Each object maintains its own safe region and is only updated if its new location invalidates the results of any of the queries. In [17], Mokbel et al. present a centralized approach called SINA based on shared execution and incremental evaluation. Shared execution is achieved by a spatial join between the objects and the queries. In [8], Cai et al. propose MQM (Monitoring Query Management) technique which aims to reduce the communication and server costs in a distributed manner through the concept of resident domain. Similarly, Jung et al. [22] propose Query Region tree (QR-tree) to achieve efficient cooperation between server and moving objects by leveraging the computational resources. In [21], Do et al. consider the hybrid communication architecture unifying the two communication paradigms, wide-area and local-area wireless networks. They propose P2MRQ (peer-to-peer technique for moving range queries) technique which exploits peer-to-peer communication for maximizing the scalability of continuous spatial query systems. In [20], Farrell et al. propose a quality-based compensation method for reducing power consumption of moving objects. The method controls when an object should acquire and update its location with user-defined error or tolerances. In [30], Song et al. propose a privacy-preserving continuous query processing technique called anonymity of motion vectors (AMV) which utilizes motion vector to minimize cloaking region; however it does not consider power consumption and sleep-off mode.

To the best of our knowledge, none of these studies reviewed above effectively utilizes movement patterns of moving objects and their sleep-off mode (power conserving mode).

6. Concluding Remarks

This paper presents a distributed sensing and monitoring technique (called Sleepwalk) for processing monitoring queries that significantly improves the scalability of server and the energy efficiency of MCs. The proposed technique can be seen as a resource-constraint workload distribution scheme. Extensive experiments indicate that the proposed technique remarkably outperforms existing techniques in terms of server scalability, communication cost, and energy consumption of MCs with various settings. This is mainly because the proposed scheme maximizes the localized processing for computing query results and conserves battery power efficiently.

For future research, we will investigate the problem in indoor space with noncoordinate based location models. Different query types such as kNN (k-nearest neighbor) and other sophisticated queries will be investigated. We will focus on many different environments such as Internet of Things (IoT) in order to support realistic scenarios and services.