An efficient algorithm for quality of service assessment
Journal of Science Hong Duc University, E.2, Vol.7, P (11 - 20), 2016
AN EFFICIENT ALGORITHM FOR QUALITY OF SERVICE
ASSESSMENT
Nguyen The Cuong, Trinh Thi Anh Loan, Nguyen The Loi1
Received: 7 August 2015 / Accepted: 2 April 2016 / Published: May 2016
©Hong Duc University (HDU) and Journal of Science, Hong Duc University
Abstract: In environmental monitoring systems, services are developed both in sensors and
the server (base station) to provide interfaces where users can interact to systems to retrieve
required information. Because of network’s resource limitation, some services may not keep
their quality level stable over long period which could lead to the violation of quality of
service agreements. In order to keep quality level stable, risk factors must be realized and
monitored as soon as possible. Based on information retrieved through the monitoring
process, an algorithm is built for estimating the quality of services. In this paper, we introduce
how this algorithm is built and how it is applied to estimate the quality of internet services.
Keywords: Algorithm, internet services
1. Introduction
In environmental assessment systems where sensors are used to retrieve noise and air
pollution data, QoS level management becomes significant. There are efforts of developers to
provide sensed data to users. Internet services are considered as a means of sensed data
distribution to interested users. However, due to resource limitation of sensor networks,
developed services’ quality changes during execution time which leads to the violation of
quality of service agreements.
To deal with the drawbacks described above, firstly, it is necessary to recognize that
potential failures may happen in the system during runtime. From the aforementioned failures,
several factors, which may impact on the performance of the system, are defined. Then, QoS
parameters have been added to the system to indicate the performance of the services. In our
work, we focus on two importance QoS parameters: speed of the system’s response (to user
Nguyen The Cuong
Faculty of Information Technology & Communication
Trinh Thi Anh Loan
Faculty of Information Technology & Communication
Nguyen The Loi
Faculty of Quality Assurance and Testing
11
Journal of Science Hong Duc University, E.2, Vol.7, P (11 - 20), 2016
requests) and reliability of delivered data. Finally, the QoS level of a service must be
estimated before a service invocation to help selecting the most appropriate one [1].
We propose a Naive Bayesian algorithm for estimating QoS values of services in
sensor networks deployed for environmental assessment. This algorithm uses as input
measurable service parameters - for example service availability and service response time -
that can be regularly monitored. The proposed algorithm must be able to reliably estimate in
near real-time QoS levels to avoid the degraded performance of the composed service. The
constraint on near real-time estimation can be met with an algorithm based on a Naive
Bayesian classifier which is known for its ease of implementation, good performance, and
good accuracy [2].
2. Service profiling
Considering the QoS agreement between service providers and service consumers,
quality of Web services can be represented by a six dimensional model which includes
expected value, agreed value, delivered value, perceived value, transmitted value, and statistic
value [3]. The key point of this approach is to use agents, which capture the data on the
service performance at both client-side and provider-side in order to evaluate the QoS
agreement.
As presented in [4], the authors used machine learning techniques such as Bayesian
Classifiers and Decision Trees to assign the quality of marine sensor data to discrete quality
flags that indicate the level of uncertainty associated with a sensor reading. To do that, the
authors built multiple classifiers and multiple training sets corresponding with each classifier.
Output of classifiers is used to make the final decision using majority voting. QoS monitoring
is also presented in [5], when Zeng et al., proposed a model for QoS monitoring in service
composition.
Service profiling implies the identification of factors that affect QoS levels in
environmental sensor networks and the strategies to measure directly or indirectly their
respective parameters. The results of service profiling, i.e. measured service parameters, serve
as input to our QoS level classification model. In next subsections, we present how service-
related factors are identified and how their relationship is defined.
2.1. Potential Failures in Sensor Networks and Service-based Applications
Sensor networks are resource-constrained and usually deployed in outdoor,
inaccessible environments in order to collect data about the real world. Although advances
in microelectronics provide sensor nodes that are becoming more powerful and robust,
sensor nodes can still fail due to a number of causes such as exposure to harsh
environments, low battery levels, or communication failures. Moreover, node failures can
hinder the network’s capacity to deliver acceptable QoS levels. Understanding potential
12
Journal of Science Hong Duc University, E.2, Vol.7, P (11 - 20), 2016
failures (will be listed in Figure 1) is a very first step in handling and controlling the
quality of service of the entire network. There are main nine failures which may occur in
sensor network in runtime as followings: Sensor Failures, Data Acquisition Platform
Failure, Battery Failure, Power Source Failure, Timing Synchronization Accuracy,
Communication Channel Failure, Communication Channel Overload, Server Overload,
Service Failure.
2.2. Service Parameters
Because the system architecture is sensor-based and service-based (the values of QoS
level of services) depend on the performance of the sensors and the server. The state of the
sensors and the state of the communication network also play an important role, which
determines the QoS level of services. Based on the observation of the potential failures
mentioned in the previous subsection, we identify five measurable parameters that reflect the
profile of a service and determine directly or indirectly their QoS levels.
Quality of measurement represents quality of the sensors at the moment data is
recorded. Its value shows how good the sensors measure a phenomenon in reality.
The higher values, the better quality of sensed data.
Data availability refers to the percentage of data that can be directly accessed. The
availability of data depends on two aspects: the requested location and the status of
sensor nodes around that location.
Data freshness is an expression of the time between the moment data is measured and
the moment data is returned to a user request.
Service response represents how fast a service can respond to a request. It is the
duration between the sending request time and the receiving result time.
Service availability indicates the percentage of successful calls to a service. To check
the service availability, a service invocation will be made.
2.3. QoS Parameters and the Relationship with Service Parameters
Considering the performance of an environmental monitoring system, we consider the
two most important quality parameters, the speed of processing data and the reliability of the
provided data. Therefore, we define two QoS parameters and offer them to end-users and
application developers:
Reliability: indicates the correctness of the data, which are recorded by sensors and
provided to end-users.
Responsiveness: represent show quickly the system can respond to given requests
from users
As depicted in Figure 1, there are dependencies between potential failures and
aforementioned service parameters.
13
Journal of Science Hong Duc University, E.2, Vol.7, P (11 - 20), 2016
Figure 1. The relationship between failures, service parameters and QoS parameters
clearly illustrates the connection between offered QoS levels and system failures
3. The QoS level estimation model
The service profile parameters presented in the previous section are used as inputs to
our QoS level estimation model. This model needs to process a service’s profile parameters
and to output a QoS level estimation in near real-time. To support online estimation, our
model needs to be flexible, highly accurate, and needs a very short time to train. Although,
there are several well-known machine learning techniques used for data classification and
estimation such as Neutral Networks, Support Vector Machines, and Decision Trees, we have
chosen for the method based on Bayesian Networks (BN). This method is easy to construct,
requires a small amount of training data to estimate, has fast performance, high accuracy, and
can work with both numerical and non-numerical data [6].
The structure of a BN is represented in the form of a directed, acyclic graph in which
nodes correspond to random variables of interest and directed arcs represent direct causal or
influential relation between nodes. The uncertainty of the interdependence of variables is
represented locally by the Conditional Probability Table. Each cell of the table contains a
function 푃(퐵|퐴), which is the probability that event B occurs given that event A has already
occurred:
( | )
P A B P(B)
( | )
P B A =
(3.1)
P(A)
( )
( )
P A and P B are the probabilities of the occurrence of event A and B respectively,
( | )
P A B is the probability of the occurrence of event A, given that event B has already
occurred.
The BN for QoS level estimation in our approach is a Naive Bayesian Network
consisting of a root node and several leaf nodes. There are no arcs between any two leaf nodes
because we assume that service profile parameters are independent - i.e. the value of a
particular parameter does not impact the value of another. Use of a Naive BN has the
14
Journal of Science Hong Duc University, E.2, Vol.7, P (11 - 20), 2016
following benefits: the model is fast to train and fast to estimate data; it is able to handle real
and discrete data; the model is not sensitive to irrelevant features. This means if more features
are used as inputs of the model, the model may work better.
In Naive Bayesian Networks used in our case, QoS parameters (reliability and
responsiveness) are represented with root nodes, and the measurable profile parameters will
be leaf nodes. Since there are two QoS parameters to be taken into account, two BNs are
developed, one for the reliability parameter and the other one for the responsiveness
parameter Figure 2. The two BNs are presented as following.
Figure 2. Two naive Bayesian Networks represent two QoS parameters
In the Naive Bayesian algorithm, each sample 푥 can be represented by a set of
〈
〉
measurable parameters, 푥 = 푎1, 푎2, . . , 푎푛 where n is the number of service parameters (in
our case, n = 5). Sample x will be classified to one of the levels in a definite set 퐿 =
〈
〈
〉
푙1, 푙2, . . , 푙푚 where m is the number of levels (in our case, m is 3). With a given sample 푥 =
〉
푎1, 푎2, . . , 푎푛 the corresponding level assigned to the parameters must satisfy:
푙푚푎푥 = 푎푟푔푚푎푥푙 ∈퐿푃(푙푖|푎1, 푎2, . . , 푎푛)
(3.2)
푖
Where the 푎푟푔푚푎푥 function returns the value of 푙푚푎푥 for which the probability
function 푃(푙푖|푎1, 푎2, . . , 푎푛) attains is largest value.
Applying Bayes theory to formula (3.2) and because 푃 푎1, 푎2, . . , 푎푛 is independent
from 푙푖, we have:
(
)
(
)
푃 푎1, 푎2, . . , 푎푛|푙푖 ∗ 푃(푙푖)
푙푚푎푥 = 푎푟푔푚푎푥푙 ∈퐿
푖
(
)
푃 푎1, 푎2, . . , 푎푛
(3.3)
(
)
= 푎푟푔푚푎푥푙 ∈퐿푃 푎1, 푎2, . . , 푎푛|푙푖 ∗ 푃(푙푖)
푖
Assume that the attributes are independent. In which:
푛
(
)
푃 푎1, 푎2, . . , 푎푛|푙푖 = ∏ 푃(푎푗|푙푖)
푗=1
Then 푙푚푎푥 is determined:
푙푚푎푥 = 푎푟푔푚푎푥푙 ∈퐿
푛
∏
푃(푎푗|푙푖) ∗ 푃(푙푖)
(3.4)
푖
푗=1
15
Journal of Science Hong Duc University, E.2, Vol.7, P (11 - 20), 2016
Based on Equation (3.4), an algorithm (see Algorithm 1) is developed to estimate the
QoS level of the offered services. The algorithm consists of two phases: training phase and
classification phase.
Training phase: Compute the probability of the value of service parameters and the
value of labels in the training data set.
Classification phase: Assign the sample to the label name which gets the highest
probability.
The algorithm is applied to two QoS parameters to estimate their values before the
data service is consumed. Because the algorithm uses a training data set, which is created
based on historical observations; the value of QoS level based on the probability theorem
could be estimated. After being trained, the estimation models can be tested with other data
sets to check its accuracy. These data sets were also created by experienced experts. The
number of records in the training data set is finite, so the algorithm is finished after a limited
time.
Algorithm 1: QoS level estimation Algorithm
〈
〉
푰풏풑풖풕:푊푒푏푠푒푟푣ꢀ푐푒푥 = 푎1, 푎2, . . , 푎푛
≫ 푎푗: 푝푎푟푎푚푒푡푒푟 푣푎푙푢푒푠
〈
〉
푆푒푡 표푓 푙푒푣푒푙푠 퐿 = 푙1, 푙2, . . , 푙푚
≫ 푙푖: 푎 ꢁ푎푚푒 표푓 푎 푙푒푣푒푙
푩풆품풊풏
푓푚푎푥 ← 0
≫ 푈푠푒푑 푡표 푠푡표푟푒 푡ℎ푒 ℎꢀ푔ℎ푒푠푡 푝푟표푏푎푏ꢀ푙ꢀ푡푦 푣푎푙푢푒
≫ 푈푠푒푑 푡표 푠푡표푟푒 푡ℎ푒 푙푒푣푒푙 푤ꢀ푡ℎ 푡ℎ푒 ℎꢀ푔ℎ푒푠푡 푣푎푙푢푒
푙푚푎푥 ← ꢁ푢푙푙
푭풐풓풆풂풄풉 푙푖 ∈ 퐿 풅풐
푩풆품풊풏
( )
푃 푙푖 ← 푃푟표푏푎푏ꢀ푙ꢀ푡푦 표푓 푙푖 ꢀꢁ 푡ℎ푒 푡푟푎ꢀꢁꢀꢁ푔 푑푎푡푎 푠푒푡
푓(푙푖) ← 푃(푙푖) ≫ 퐼ꢁꢀ푡ꢀ푎푙ꢀ푧푒 푡ℎ푒 푓(푙푖)
푭풐풓풆풂풄풉 푎푗 ∈ 푥풅풐
푩풆품풊풏
푃(푎푗|푙푖) ← 푃푟표푏푎푏ꢀ푙ꢀ푡푦 표푓 푎푗 푔ꢀ푣푒ꢁ 푙푖 ꢀꢁ 푡ℎ푒 푡푟푎ꢀꢁꢀꢁ푔 푑푎푡푎 푠푒푡
( ) ( )
푓 푙푖 ← 푓 푙푖 ∗ 푃(푎푗|푙푖) ≫ 퐶푎푙푐푢푙푎푡푒 푡ℎ푒 푎푐푐푢푙푢푚푎푡ꢀ푣푒 푣푎푙푢푒
푬풏풅
( )
푰풇 푓 푙푖 ≥ 푓푚푎푥 풕풉풆풏
푩풆품풊풏
≫ 퐶ℎ푒푐푘 푤ℎ푒푡ℎ푒푟 푡ℎ푒 ꢁ푒푤 푣푎푙푢푒 ꢀ푠 ℎꢀ푔ℎ푒푟 푡ℎ푎ꢁ 푓푚푎푥
푓푚푎푥 ← 푓(푙푖)
푙푚푎푥 ← 푙푖
≫ 퐴푠푠ꢀ푔ꢁ 푓푚푎푥 푤ꢀ푡ℎ 푎 ꢁ푒푤 푣푎푙푢푒
≫ 퐴푠푠ꢀ푔ꢁ 푙푚푎푥 푤ꢀ푡ℎ 푎 ꢁ푒푤 푣푎푙푢푒
푬풏풅
푬풏풅
푬풏풅
〈 〉
푊푒푏 푠푒푟푣ꢀ푐푒 푥 = 푎1, 푎2, . . , 푎푛 ꢀ푠 푎푠푠ꢀ푔ꢁ푒푑 푡표 푡ℎ푒 푐푙푎푠푠 푙푚푎푥
푶풖풕풑풖풕:
16
Journal of Science Hong Duc University, E.2, Vol.7, P (11 - 20), 2016
4. Experiments & results
The estimation model is implemented based on the proposed algorithm and built-in
libraries coming from the Waikato Environment for Knowledge Analysis (Weka). The Weka
is an open source software that implements many state-of-the-art machine learning and data
mining algorithms. It has achieved widespread acceptance within academic environment and
business market, and has become a widely used tool for data mining research. The Weka
project aims at providing a comprehensive collection of machine learning algorithms and data
pre-processing tools to researchers and practitioners alike.
4.1. Building Training Data Sets
A training set is a set of data used to discover potentially predictive relationships. It
consists of an input vector and an answer vector. In the machine learning model, like the QoS
estimation model, the training set is used to train the model that can be used to estimate a
concerned value from one or more values of available parameters.
In the context of our estimation model, data training sets are made by experienced
developers and service users. The model trainers will query the latest measurement data at
sensors node. Returned values include a sound level value (dB) and other values related to the
performance of the service. Based on knowledge and experience, trainers express their
evaluation by selecting one of the available options for each QoS parameters. The trainers’
choice will be stored and used as training data for the estimation model. To guarantee the
validation of the outputs, model trainers have to provide both selections before submitting. At
the moment of writing, we have two training data sets for two estimation models (one for
responsiveness parameter and another for reliability parameter). Each training data set
contains 114 records.
Figure 3. Developers and experienced users can express their evaluation on service
quality based on monitored performance factors via this interface. Outputs of this phase
are used for training the estimation model
17
Journal of Science Hong Duc University, E.2, Vol.7, P (11 - 20), 2016
4.2. Cross-validation for Training Data Sets
Cross-validation is a technique used for evaluating and comparing learning algorithms
by dividing data into two segments. The first segment is used to learn or train the model and
the other one is used to validate the model [7].
The purpose of using cross-validation is to check the fit of a model to a hypothetical
validation when an explicit validation set is not available. The basic form of cross-validation
is a k-fold cross-validation. Other forms are special cases of k-fold cross-validation or involve
repeated rounds of k-fold cross-validation.
The cross-validation method used for this training data set is 10-fold cross-validation.
The results of the cross-validation are 66.67% and 68.42% for reliability and responsiveness
models correspondingly.
4.3. Experiment Results
The accuracy of the Naive Bayes classification algorithm can be evaluated by testing
the model with several testing data sets. These sets were created by developers and service
users using the aforementioned interface. Its size is increased from 100 to 500 records during
tests. A test is done by first estimating a testing data set with the model; and then comparing
the estimated labels with the real labels (as evaluated by developers and users) in the testing
data set.
The accuracy of the model is determined based on the percentage of records that are
estimated correctly (i.e. matching to labels assigned by experts) by the model. For each
number of test sets, the estimation model on 5 different same-size test sets is repeated.
Afterward, the mean values are determined; the confidence level of 95% is chosen when
calculating the confidence interval of mean values.
The performance of the QoS estimation models was evaluated based on their
execution time - the amount of time needed to finish the given task (s). In our tests, we
considered execution time as the total time spent for estimating a number of records.
Particularly, it is a summation of the time spent for training the models, time spent for
estimating records, and time spent for returning the result.
Table 1 presents the results of 5 tests in terms of execution time and accuracy. The
accuracy of the estimation model for the reliability parameter is between 74 ± 1% and 79 ±
1%, while it is between 75 ± 1% and 78 ± 1% for the responsiveness parameter.
Additionally, the bundle performed well in terms of the execution time, i.e. it took a short
time to finish the tests.
The average time spent for estimating a record decreases when the size of the testing
data set increases. The obtained results prove the possibility of using these estimation models
for the online service suggestion.
18
Journal of Science Hong Duc University, E.2, Vol.7, P (11 - 20), 2016
Table 1. Reliability and Responsiveness estimation accuracy and performance for
differently sized testing data sets
Reliability
Responsiveness
# testing
records
Execution time
Execution time
Accuracy
(%)
Accuracy (%)
(millisecond)
(milliseconds)
100
200
300
400
500
72 ± 2
74 ± 1
77 ± 1
76 ± 1
79 ± 1
78 ± 1
41 ± 1
77 ± 1
78 ± 1
78 ± 1
77 ± 1
75 ± 1
84 ± 2
46 ± 2
93 ± 2
55 ± 3
96 ± 2
65 ± 3
103 ± 2
75 ± 3
5. Conclusions and future work
An efficient algorithm to estimate the value of QoS parameters offered in an
environmental assessment system based on monitoring measurable parameters is studied. This
approach could help developers and users to understand about quality of service they may be
interested in. From the relationships between risk factors and QoS parameters, a
probabilistic graphical model, Naive BN based model, for estimating the values of QoS
parameters from the monitored data is built. This model consists of two main phases: the
training and the classifying phases. The training phase is used to train the model based on a
training data set built by the model developer. The classifying phase labels the given service
to a class, which has the highest value of the probabilistic distribution. This model helps to
determine the value of QoS parameters of services when they are invoked to answer a service
composition request. Due to limitation of data training sets, the accuracy of estimation is not
high as expected. The data training sets for our two models should be improved in the future
work.
References
[1]
[2]
[3]
Q. Tao, H. Chang, C. Gu, and Y. Yi (2012), “A novel prediction approach for
trustworthy QoS of web services”, Journal of Expert Systems with Applications, vol.
39, no. 3, pp. 3676 - 3681.
D. Smith, G. Timms, P. De Souza, and C. D’Este (2012), “A Bayesian Framework
for the Automated Online Assessment of Sensor Data Quality”, Sensors, vol. 12, pp.
9476 - 9501.
N. Guo, T. Gao, and B. Zhang (2008), “A Trusted Quality of Web Services
Management Framework Based on Six Dimensional QoWS Model and End-to-End
Monitoring”, in Proceedings of the 11th Asia-Pacific Symposium on Network
Operations and Management: Challenges for Next Generation Network Operations
19
Journal of Science Hong Duc University, E.2, Vol.7, P (11 - 20), 2016
and Service Management, pp. 437 - 440.
[4]
[5]
[6]
[7]
A. Rahman, D. Smith, and G. Timms (2014), “A Novel Machine Learning Approach
towards Quality Assessment of Sensor Data”, IEEE Sensors Journal, vol. 14, no. 4,
pp. 1035 - 1047.
L. Zeng, H. Lei, and H. Chang (2007), “Monitoring the QoS for Web Services”, in
Service-Oriented Computing – ICSOC 2007, vol. 4749, Springer Berlin / Heidelberg,
pp. 132 - 144.
P. Bhargavi and S. Jyothi (2009), “Applying Naive Bayes data mining technique for
classification of agricultural land soils”, International Journal of Computer Science
and Network Security, vol. 9, no. 8, pp. 117 - 122.
M. W. Browne (2000), “Cross-Validation Methods”, Journal of Mathematical
Psychology, vol. 44, no. 1, pp. 108 - 132, Mar.
20
10 trang
20940
Free
Bạn đang xem tài liệu "An efficient algorithm for quality of service assessment", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- an_efficient_algorithm_for_quality_of_service_assessment.pdf
