DEIM Forum 2016 G8-6

Reducing Expenses of Sensor-Cloud Services for Dynamic Skyline
Monitoring
Kamalas UDOMLAMLERT† , Takahiro HARA† , and Shojiro NISHIO†† Graduate School of Information Science and Technology, Osaka University
1-5 Yamadaoka, Suita, Osaka 565-0871, Japan
E-mail: †{kamalas.u,hara,nishio}@ist.osaka-u.ac.jp
Abstract In the concept of Sensor-Cloud, many sensor networks are unified and provide Sensing as a Service tousers. The users can utilize provisioning virtual sensors to perform desired tasks. The expense (cost) is based on
the amount and types of data requests. In this paper, unlike other existing works, we propose a cost-minimizing
framework for dynamic skyline monitoring. Our approach avoids paying the cost of all attributes by iteratively
requesting the most cost-eﬀective attributes that can identify whether a tuple is in dynamic skyline. We conduct
some experiments on various real datasets. The results confirm the eﬀectiveness compared with the baseline andthe random strategy.
Key words dynamic skyline, monitoring query, sensor cloud, sensing-as-a-service

wide-spread area without technical diﬃculties. In commer-

1. Introduction

cial services [4], cloud users pay the usage cost based on the

Wireless Sensor Networks (WSNs) play an important roleamount of utilization (pay as you go) without the necessity

in various fields including environmental monitoring, struc-of deploying their own infrastructure, while WSNs providers

ture health monitoring, disaster prevention, industrial mon-(owner) and mobile phone users may receive the rewards initoring and so forth. These have been extensively researched

the forms of rental fee or the cost of requested data.

in the research community. Because of the development of

Meanwhile, primitive tasks of WSNs are monitoring. Duemobile phones and social networks, the concept of mobile

to various types of sensors integrated in Sensor-Cloud, many

sensing – using sensors on mobile phones as a sensing plat-monitoring systems take more than one attribute into ac-form has been introduced.

Therefore, a massive amountcount from various kinds of provided sensors to make a deci-of information has been generated everyday, which enables

sion (Multiple-criteria decision-making). Hence, many com-many captivating applications. However, most of real sen-plex monitoring queries for multidimensional data have been

sor networks are deployed and utilized for only a specificdeveloped including top-k query, k-nearest neighbor query,purpose on limited locations by private organizations. Ac-

skyline query and reverse skyline query. Based on the invest-

cording to individually-invested expensive installation cost,

ment and production cost, diﬀerent types of sensors provide

those resources are rarely federated and not often open to

diﬀerent kind of data at diﬀerent prices in Sensor-Cloud.

public. Moreover, in mobile sensing, mobile phone users are

Even though, the traditional monitoring methods can be

not willing to do sensing tasks due to privacy concerns andused on Sensor-Cloud, none of previous works has addressedmobile battery constraints.

the important objective for cloud users when using Sensor-

Dealing with Big Sensor Data, the idea of using cloud

Cloud, i.e., cost minimization.

computing (Sensor-Cloud) aims to unify available sensors

In this work, we firstly propose a cost-minimization moni-

together, i.e., various existing WSNs and mobile users, andtoring framework for dynamic skyline queries, a useful query

many research challenges to create such a platform have been

method for WSNs, where a traditional skyline is a special

addressed [1].

case. Given a reference point (query point) in normal situ2

Sensing as a service (S aaS) [8] in Sensor-Cloud abstracts

ation and a data set of critical points, the system monitors

all the physical layers of sensor network integration. It pro-periodically-sensed data from sensors (event tuple). To il-vides the cloud users to eﬀectively utilize the provisioning

lustrate, an administrator monitors a combination of risk

virtual sensors, so cloud users can perform their desire sens-

factors of flash flood, e.g., ground water level, precipitation,

ing tasks by using various kinds of sensors in an available

high tide and melting snow on a location every 30 minutes.

for dynamic skyline [6], which is a superclass of traditional

𝑎𝑡𝑡2

𝑎𝑡𝑡2
𝑑 ′6

𝑑6

𝑑 ′5

𝑑5

𝑑

𝑑8

𝑞

𝑑8

𝑑5
4

𝑑

𝑑
𝑑 ′3

3. 1 Problem Statement
𝑑1

3

𝑑2

𝑂

𝑞

(a) Dynamic skyline

Given a set of m attributes including AT = {att1 , att2 , . . . ,1

𝑑𝐴𝐷𝑞1 (𝑎𝑡𝑡1 )

𝑎𝑡𝑡1

𝑑7

𝑑4

1

𝑑

skyline, in Sensor-Cloud.
𝑒1

3. Cost Minimizing Framework

7

′2

𝑑 ′1
𝑑1

𝑒2

𝑑6

3

𝑑2

𝑂

𝑎𝑡𝑡1

(b) Initial anti-dominance ranges

Figure 1: The example of dynamic skyline of q 1

The standard levels of these factors are used as a reference
point. If their values are close to the reference point, it showsa benign event takes place. Otherwise, if the values deviate
from the reference point until they are worse than (dominated by) the given critical points, i.e., become a dynamic
skyline, the administrator must look at such an event with at-

attm }, and let D = {d1 , d2 , . . . , dND } be a dataset of critical points in m-dimensional positive Euclidean space of attributes A = A1 ×A2 ×. . .×Am . di ∈ D can be represented asa point (di1 , di2 , ..., dim ) ∈ A where dij ∈ Aj , i ∈ {1, 2, ..., ND }and j ∈ {1, 2, . . . , m}.
Definition 1. (Dynamic Skyline Query) [2], [6]: Given an
m-dimensional query point q ∈ A and a dataset D, a Dynamic Skyline Query (DSQ) w.r.t.

q retrieves all data

points in D that are not dynamically dominated denoted by
DSQ(D, q). A point d ∈ D dynamically dominates d′ ∈ D
w.r.t. the query point q if (1) ∀i ∈ {1, 2, ..., m} : |qi − di | <=tention. However, knowing actual values of some attributes|qi −d′i |, and at least one j ∈ {1, 2, ..., m} : |qj −dj | < |qj −d′j |.

may lead to a conclusion. For example, the readings now

DSQ can be computed by using the traditional sky-shows that ground water level and precipitation are very low

line computation（注 1） by transforming all points diand close to the standard levels, so, regardless of other fac-(di1 , di2 , ..., dim )tors, there is no chance of flood. In this case, we can saved′i = (|di1 − q1 |, |di2 − q2 |, ..., |dim − qm |). However, the query

utilization cost by not requesting sensor data for such negli-

points registered in the system can be more than 1 point,gible factors.

e.g., many reference points. Let Q = {q 1 , q 2 , ..., q |Q| } be a=to the new data space w.r.t. point q, i.e.,

Our proposed framework evaluates cost-eﬀective measure-set of monitoring dynamic skyline query points. In this case,ment for each attribute to decide a plan, which sensor should
be requested in order to lead to the query answer with

Dynamic Skyline Query of Q is defined by DSQ(D, Q) =
∪
1
1
4
5
q∈Q DSQ(D, q). In Fig.1a, DSQ(D, q ) = {d , d , d } be-the lowest cost. We conduct some experiments using realcause the traditional skyline on the new space consists ofdatasets to ensure the capability and scalability of our pro-d′1 , d4 and d′5 .

posed framework.

2. Related WorkAn event tuple e is a group of values read from diﬀerent
types of sensors associated with meta-data, e.g., a timestamp and a location. We assume that to acquire each at-

Sensor-Cloud is a new concept which is inherited fromCloud computing. Cloud computing basically provides users

tribute value costs diﬀerently, so cloud providers use a fixed⟨⟩price vector C = c1 , c2 , . . . , cm as a price per reading ofmany XaaS (X as a service) such as Platform as a Service

attribute att1 , att2 , . . . , attm respectively.

(PaaS). Sensor-Cloud aims to integrate and abstract many
physical sensors and/or any communicating things as an in-

Definition 2. (Dynamic Skyline Monitoring Query): Given

frastructure that allows users to easily utilize it with lower

a set of query points Q ⊂ A and a dataset D, Dynamic

cost than owning WSNs. This is called Sensing as a Service

Skyline Monitoring Query (DSMQ) according to Q identifies(S2 aaS) [8], and some services can become commercial [4].

whether an m-dimensional event tuple e = (e1 , e2 , ..., em ) be-

The comprehensive survey of architecture, advantages andprovisioning applications are covered up in [1].
To draw a conclusive decision from multi-dimensional data,

long to a dynamic skyline w.r.t. at least one query q ∈ Q.
true
; e ∈ DSQ(D ∪ {e}, Q)
DSM Q(D, Q, e) =f alse ; Otherwisee.g, sensor data, many complex query processing techniques
have been developed. Among these, skyline processing plays
an important role in various applications such as monitoringand service discovery [9]. Most works address eﬃcient skyline processing [7] and distributed skyline processing [3]. In
this work, we firstly investigate a cost minimization problem

In Fig.1b, event tuple e1 is dynamically dominated by4

d while e2 is not dynamically dominated by any point, so
DSM Q(D, {q 1 }, e1 ) returns f alse and DSM Q(D, {q 1 }, e2 )returns true.
（注 1）：The definition of traditional skyline is referred to [2], [3], [7]To periodically fetch all attributes for monitoring applica∑itions, the cost is fixed at m
i=1 c at each timestamp. In this𝑑paper, we object to execute monitoring DSMQ by minimizing the total expense for Sensor-Cloud services. We observe

𝑎𝑡𝑡2

𝑎𝑡𝑡2
𝑑

6

8

𝐷𝑆𝑄 𝐷, 𝑞1 = {𝑑1 , 𝑑4 , 𝑑5 }𝐷𝑆𝑄 𝐷, 𝑞 2 = {𝑑3 , 𝑑4 , 𝑑7 }

𝑑8

𝑑6
𝑑5

𝑑5

𝑑7

𝑒′2

𝐴𝐷𝑞2 𝑎𝑡𝑡2 = [1.1,2.0]

𝑑7

𝑑4

𝑑4

that, many monitoring applications only focus on unusual

𝑞2

events (returning false in DSMQ) in real-time while the oth𝑑1

ers (possibly a majority) are neglected not even to be stored
into the disk. Note that if users prefer to access historical
data to analyze in details, they may pay additional fees to

𝑞1

𝑂

𝑑1

𝑑3
𝑑

𝑒2

𝐴𝐷𝑞1 𝑎𝑡𝑡1 = [0.75,1.7]

𝑂

𝑎𝑡𝑡1

(a) Anti-dominance ranges after

access those data directly from the cloud.

𝑑3

𝐴𝐷𝑞1 𝑎𝑡𝑡2 = [1.0,1.45]

2𝐴𝐷𝑞1 (𝑎𝑡𝑡1 |{𝑎𝑡𝑡2 = 𝑒2 })𝑞1
𝑑2

𝐴𝐷𝑞2 𝑎𝑡𝑡1 = [2.5,3.0] 𝑎𝑡𝑡1(b) Running example

fetching e2

3. 2 Sequential Attribute Request Strategy

Figure 2: An example of anti-dominance range

Instead of getting all attribute values, it is more economical to sequentially get only a set of partial attributes that isstill able to lead to the same decision making. However, that
optimal set is unknown in prior. Our proposed frameworkpresents the strategy to sequentially request some promising

set F , then ei : atti ∈ F is known, the anti-dominance range
and skyline probability of atti ∈ AT \F are possibly changed
as the following equations.
ADq (atti |F ) = [max(0, qi − g ′ ), min(Ai , qi + g ′ )]attributes that are still able to answer DSMQ.

(3)Here, we give the definition of anti-dominance range of
attribute atti .

where g ′ = mins∈q.DSQ\{s′ ∈q.DSQ|∀j∈F :|qj −sj |>ej } |si − qi |.

Definition 3. (Anti-dominance range of attribute atti w.r.t

e2 has been fetched, the range ADq1 (att1 |{e2 }) is expandedq denoted by ADq (atti )): Given a dataset D and a queryfrom ADq1 (att1 ) as shown in the figure.

In Fig.2a using the same dataset as Fig.1b, assume thatpoint q, ADq (atti ) is an interval [a, b] ∈ [0, Ai ] which is expressed by:
ADq (atti ) = [max(0, qi − g), min(Ai , qi + g)]

PD,Q (atti |F ) =(1)

where g = mins∈q.DSQ |si − qi |∪q∈Q ADq (atti |F ))

Ai

(4)

′ <
Lemma 2. If F ′ ⊂=F , then PD,Q (atti |F ) = PD,Q (atti |F )Proof. Omitted.

Lemma 1. For any ei ∈ ADq (atti ) regardless of other attribute values then e ∈ DSQ(D ∪ {e}, q)

Nevertheless, the important factor is cost. Our proposed
framework selects a promising attribute to fetch based on

Proof. Omitted.
The examples of ADq1 (att1 ) and ADq1 (att2 ) (the purple intervals) are shown in Fig.1b. Note that because e21 ∈ADq1 (att1 ) regardless of e22 then DSM Q(D, Q, e2 ) = true.
However, at the beginning, we have to decide which attribute to be retrieved first. The greedy choice is to retrieve the attribute which is most likely able to draw theconclusion right after the request. Therefore, assuming that
all attributes are independent and identically distributed
random variables (iid), we can calculate the probability of
DSM Q(D, Q, e) = true (Dynamic skyline probability) after
having requested atti (ei ) by the following equation.
∪len( q∈Q ADq (atti ))PD,Q (atti ) =
Ai

len(

the following cost-eﬃcient measurement.
[]
PD,Q (atti |F )atti = arg max
ci
atti ∈AT \F(5)

Running Example : We illustrate by using Fig.2b. Given a
price vector is ⟨3, 2⟩, we calculate the probability as follows:
PD,Q (att1 ) = 1.4/3 = 0.467 and PD,Q (att2 ) = 1.0/2 = 0.5.
Hence, The first attribute to select is att2 .
Algorithm 1 summarizes the procedures of our proposed
framework. We assume that DSQ(D, q) for q ∈ Q can bepre-computed once.
3. 2. 1 Time Complexity Analysis
Finding ADq (atti |F ) requires calculating g ′ for each q andeach attribute. This takes O(m · |Q| · |S|) time where |S|(2)

where len() is a sum of lengths of union intervals.

is the cardinality of the dynamic skyline.

For indepen-

dent dimensions, the expected number of skyline points is∪θ((log n)d /(d − 1)!) [2]. In line 4, len( q∈Q ADq (atti |F )) canIn the case that after having fetched the first attribute andbe found by sorting intervals and computing their sum withDSM Q(D, Q, e) cannot be concluded, we have to choose theO(|Q| log |Q|) time. In line 8, checking the membership is

next promising attribute to be requested from the remaining

processed on an interval tree in O(log |Q|) time. For each tu-

unrequested attributes. Given the already-fetched attributeple, in the worst case, these procedures need to be repeated500000
Baseline

RandomMinCostTotal Cost

400000300000200000100000|Q|=50|Q|=75|Q|=100|Q|=75|Q|=100

6d-HOUSEHOLD|Q|=25|Q|=10

|Q|=5

|Q|=1

|Q|=100|Q|=75|Q|=50|Q|=25|Q|=10

|Q|=5

|Q|=1

|Q|=100|Q|=75|Q|=504d-NBA|Q|=502d-STOCK|Q|=25|Q|=10

|Q|=5

|Q|=1

|Q|=100|Q|=75|Q|=50|Q|=25|Q|=10

|Q|=5

|Q|=1

0

9d-COLOR

100000Random
75000

MinCostBaseline (Parallel)

50000

Baseline (Sequential)

25000

2d-STOCK

4d-NBA

6d-HOUSEHOLD|Q|=25|Q|=10

|Q|=5

|Q|=1

|Q|=100|Q|=75|Q|=50|Q|=25|Q|=10

|Q|=5

|Q|=1

|Q|=100|Q|=75|Q|=50|Q|=25|Q|=10

|Q|=5

|Q|=1

|Q|=100|Q|=75|Q|=50|Q|=25|Q|=10

|Q|=5

0

|Q|=1

Number of data requests (times)

Figure 3: Total Cost (units)

9d-COLOR

Figure 4: The number of data requests (times)

Algorithm 1: The proposed framework
Data: a dataset D, a query set Q, an event tuple e, a pricevector c
Result: DSM Q(D, Q, e), cost
1 F ← ∅
2 while F =| Q do∪3
Calculate q∈Q ADq (atti |F )
4
5

6
7
8
9
10

Calculate PD,Q (atti |F ) for all atti ∈ AT \FRequest ei whereatti = arg maxatti ∈AT \F PD,Q (atti |F )/ci
cost ← cost + ci
F ← F ∪ {atti }∪if ei ∈ q∈Q ADq (atti ) thenreturn (true, cost)
return (false, cost)[5], [10]. We sampled 1000 points from each data set as adataset D (ND = 1000). The set of query points (Q) was
drawn from independent data distribution varying between
1-100 points. The actual event tuples are also sampled fromits corresponding dataset. Price vectors specified in eachdataset were randomly generated with a random integer pricebetween 1-9.

As a result, ⟨4, 8⟩ , ⟨7, 1, 9, 2⟩ , ⟨1, 9, 3, 4, 2, 4⟩

and ⟨2, 2, 5, 4, 5, 8, 4, 8, 6⟩ were used as price vectors for 2d,
4d, 6d and 9d datasets respectively. Finally we measured
the total cost of payment (10000 event tuples) as well as thetotal number of data requests as performance metrics.
In Fig.3, we show the total cost on diﬀerent datasets andon various sizes of Q. The results indicat that the total cost
incurred by our proposed framework (MinCost) is lower than
the random scheme (Random) and the baseline (Baseline).

at most m times resulting in O(m2 · |Q| · |S| + m · |Q| log |Q|)

The reduction ratio is getting higher on high |Q| and highin total.

dimensionality (m) because the higher |Q|, the higher chance

4. Experiments and Discussionthat an event tuple belongs to the dynamic skyline of one of
the queries. In the same way, in high dimensionality, theWe empirically evaluate our proposed framework’s eﬃ-

size of dynamic skyline of each query (|DSQ(D, q i )|) is sup-ciency. All algorithms were implemented in C# and per-posed to increase exponentially. In low dimensionality i.e.,

formed in a commodity PC (8GB, Core i7 3.6GHz). Since

2d-STOCK, MinCost did not beat the other methods signif-

none of existing studies addressed this problem before, we

icantly (saving only 2.54% compared to the baseline whencompared our framework with (i) Baseline – fetching all at-|Q| = 100). Nevertheless, the total cost can be saved up to

tributes (ii) Random – choosing next attribute randomly by

22.04%, 75.98% and 86.9% in 4d, 6d and 9d datasets respec-

replacing lines 4-5, Algorithm 1. We used various dimen-

tively.

sional real data sets including STOCK (2d) (from NYSE),In Fig.4, we show the number of data requests on eachNBA (4d), HOUSEHOLD (6d) and COLOR (9d) used insetting. For the baseline, if we assume that we request all

attribute values once (parallel request), the number of re-query points.

quests is constant at 10000 (Baseline (Parallel)). Meanwhile,

As a part of our future work, we aim to investigate theassuming sequential requests, we need to request 10000 · msame problem on other types of queries and the feasibility totimes (Baseline (Sequential)). The results also showed that

employ learning models for adaptively fitting to an irregular

the number of requests of MinCost is lower than the random

data distribution.

scheme and the baseline in most cases especially on high dimensional datasets and high |Q|. However, it does not mean

6. Acknowledgementsthat requesting fewer attributes results in lower cost. To

This research is partially supported by the Grantin-Aid

illustrate, in 4d-NBA dataset and |Q| ∈ [10, 100], MinCost

for Scientific Research (A)(26240013) of MEXT, Japan, andrequested more attribute values than the random scheme,

JST, Strategic International Collaborative Research Pro-

but MinCost consumes lower cost because MinCost makes agram, SICORP.

retrieval plan based on both skyline probability and cost ofeach attribute.
In our framework, finding ADqi (atti |F ) for each q i and atti
is the highest intensive computation. However, in our experiments even in 9d, |Q| = 100, this process takes only 42ms
in the worst case for single event tuple, while less complicated cases and other process take less than 1ms. Therefore,
our proposed framework does not burden high latency, andapplicable to most real-time applications.

5. Conclusion and Future work
We have introduced the problem of dynamic skyline monitoring on Sensor-Cloud and proposed a novel approach tosave the compensation for it. Our approach iteratively requests and assesses the most promising attribute first bymeasuring our proposed cost-eﬀective attribute measurement. Hence some tuples can be identified as dynamic skyline without fetching all attributes. The experiments performed on various real datasets ensure that this strategy cansignificantly cut the cost compared to the baseline and outperform the random strategy. In addition, the processing
cost is quite small even in high dimensionality and many

References[1] A. Alamri, W. S. Ansari, M. M. Hassan, M. S. Hossain,
A. Alelaiwi, and M. A. Hossain. A survey on sensor-cloud:architecture, applications, and approaches. IJDSN, 2013.
[2] E. Dellis and B. Seeger. Eﬃcient computation of reverse
skyline queries. In VLDB, pages 291–302, 2007.
[3] K. Hose and A. Vlachou. A survey of skyline processing in highly distributed environments. VLDB Journal,
21(3):359–384, 2012.
[4] S. Madria, V. Kumar, and R. Dalvi. Sensor cloud: A cloudof virtual sensors. Software, IEEE, 31(2):70–77, Mar 2014.
[5] D. Nanongkai, A. D. Sarma, A. Lall, R. J. Lipton, andJ. Xu. Regret-minimizing representative databases. VLDB,
3(1-2):1114–1124, 2010.
[6] D. Papadias, Y. Tao, G. Fu, and B. Seeger. An optimaland progressive algorithm for skyline queries. In SIGMOD,
pages 467–478, 2003.
[7] D. Papadias, Y. Tao, G. Fu, and B. Seeger. Progressive skyline computation in database systems. TODS, 30(1):41–82,
2005.
[8] X. Sheng, J. Tang, X. Xiao, and G. Xue. Sensing as a service: Challenges, solutions and future directions. Sensors
Journal, IEEE, 13(10):3733–3741, 2013.
[9] D. Skoutas, D. Sacharidis, A. Simitsis, and T. Sellis. Serving the sky: Discovering and selecting semantic web services
through dynamic skyline queries. In ICSC, pages 222–229,
2008.
[10] A. Sultana, N. Hassan, C. Li, J. Yang, and C. Yu. Incremental discovery of prominent situational facts. In ICDE,
pages 112–123, 2014.