Printer Friendly

Reasoning on context satisfiability for service recommendation in mobile network.

1. Introduction

In recent years, Service Oriented Computing [1] has emerged as a highly-promising paradigm for distributed computing and software engineering, changing the way that software applications are designed, delivered and consumed. As a result, a lot of Web services have been published on the Internet, providing consumers various functionalities in a language independent, platform independent and protocol independent manner. A subsequent challenge is to locate target services in a quick, accurate and efficient way.

The challenge becomes especially pressing with the increasing popularity of smart-phones and tablet devices like the iPad, along with ubiquitous network connectivity. Nowadays people tend to search and invoke services with mobile devices, requiring helpful, accurate and real-time feedback from services at any time and any place. However, mobile devices usually have limited display, processing, storage, power and communication resources, therefore it requires more accurate and adaptive recommendation list of services for a service query on mobile devices.

A promising way to increase the accuracy and adaptivity of service discovery and recommendation, which is often neglected, is to filter services by matching the precondition of service execution and the context information of the service query request. For instance, a service consumer wants to query a bus line from location A to 6, common service discovery approaches would return a bus list without considering the service time of the bus line. Since there are time of early bus and that of last bus for a bus line, suppose the last run of a bus in the returned list is 8:00pm, while the time when the consumer submits the request is 9:00pm, hence if the precondition satisfiability of the bus service is considered, the bus is unavailable for the consumer and should not be returned. Take another example, a service consumer searches a translation service to translate a text from Chinese to Spanish, common service discovery approaches would return a service list by just matching the input and output, which are both a kind of language, however a service in the list may not support the translation from the source language Chinese to the target language Spanish. In a word, it is important to take the precondition satisfiability of a service into account to increase the accuracy and adaptivity of service discovery and recommendation.

In this paper, we propose to construct context ontology first, so that we can determine what context information of service consumers will be matched against service information for service recommendation, and then we propose to formalize the precondition of successful service invocation based on a lightweight Description Language, and finally based on the formalization of both context of service consumers and precondition of service invocation, we can reason on context satisfiability for service recommendation in mobile network.

The paper is organized as follows. Section 2 reviews the related work on the formalization and reasoning of web services. Section 3 introduces the context ontology that defines the context information of a service consumer. Section 4 introduces the formalization of precondition under which a service can be invoked successfully. Section 5 proposes two kinds of reasoning problem on context satisfiability. And finally the conclusion and future work is given in Section 6.

2. Related Work

Although research on context aware service discovery and recommendation started in early days, matchmaking between user's context and a service description is still an important issue especially for mobile network. Our work presented in this paper is related to existing research on representation, modeling and context aware query of Web services. We therefore comment on some of these in the following.

2.1 Formalization and Reasoning of Web services

The most popular formal theories used for the formalization of Web services include Description Language [2], automata [3], Petri Net [4] and process algebra [5]. The latter three theories are appropriate to express the internal behavior of a web service, while DL is more appropriate to express the interface semantic of a web service, especially the properties, constraints and relations of the ontology referenced by service interface. Hence we concentrate on the related work on DL-based service formalization and reasoning.

DL is a formalized language for knowledge representation. Based on atomic concepts and relations, it can construct more complex concepts and relations by constructs such as number restriction, inverse relation and composite relation. There are two main components in DL: TBox and ABox. TBox contain a set of axioms for concepts and relations, while ABox contain a set of instances of concepts and relations. Researchers [6-16] proposed to model the interface semantics of services by DL and its extension such as DDL [17]. DL and DDL provides powerful reasoning mechanism such as the consistency, satisfiability, inclusion relation between axioms and instances, therefore it can support automatic and intelligent service discovery and composition. However, in most existing work, they simply model the precondition of a successful service invocation as an ABox assertion, in the form of a function name with some parameters. As the authors in [18] analyzed, the precondition satisfiability plays an important role in service discovery and composition, but current work does not provide solutions on how precondition will be modeled. Hence in this paper we detailed on how precondition is modeled based on a lightweight DL. The application of simplified DL alleviates the complex of reasoning on precondition as well, which is very suitable for service recommendation in mobile network.

2.2 Context aware service discovery

Presently there is much work on service discovery based on the matchmaking of interface, behavior and QoS. Recently, context matching has been applied to service discovery. Generally speaking, context is all the information that can describe the environment a service consumer is in [19].

Feng et al [20] constructed user's context ontology and service context ontology first, proposed three kinds of inference rules between user and service context, which are rules for filtering, priority selection and user's preference, and implemented corresponding context inference algorithms. Yang et al [21] proposed to infer the implied context of users based on directly perceptive context information first, and then find appropriate services based on the matchmaking between service descriptions and the implied user's context. [22] proposed a new context query language to describe complex constrains on context. Doulkerides et al [23] proposed a context aware service discovery system in which context information is represented as key-value pairs and matched against service interfaces. Bormann et al [24] proposed to find the most appropriate network operator before making phone calls based on user's location and call time. There are also some approaches on extending service discovery protocols in mobile computing with support of context awareness [25-26].

Compared with the work above, in this paper, we propose a relatively complete ontology to describe user's context when he submits his service request. The context ontology explicitly determines what information can fully describe the environment a user is in and what information will be matched against service description. Second, existing work neglected the fulfillment of precondition of a successful service invocation, and here we concentrate on the matchmaking between context of service consumers and precondition of service invocation, so that quick, accurate and efficient service recommendation can be achieved.

3. Context Ontology

In order to recommend services based on context reasoning in mobile network, we need to identify what context means first. In this section, we construct context ontology so that we can determine what context information of service consumers will be matched against service information for service recommendation in the following.

In general, context is all the information that can represent the activities of a user. As Figure 1 shows, we specialize the concept of context into an ontology consisting of two parts: user profile context, describing the intrinsic information of a user, which is irrelevant to current service invocation; and service invocation context, describing all the instant information relevant to current service invocation.

User profile context can be further divided into basic information and personal preferences. Basic information characterizes the static features of a user, such as gender, date of birth, specialty, and social role. Personal preferences characterizes implicit priority rules when the user chooses services, for instance, one wants a service with short response time although it takes more price.

Service invocation context can be further divided into three parts: (1) purpose of service invocation, which is the potential service invocation instances for current user. For example, a user wants to find a translation service that can translate Italian into Korean, such request will be translated into finding a service whose input and output signatures are both of a language, while ignoring the real use of the service for current user, that is, to translate from Italian to Korean, and we have analyzed how the ignorance of such information affects the result of service discovery in Section 1, hence we emphasize such context information as the purpose of service invocation; (2) Natural environment, which describes the local environment of the user when he submits the service request, such as the location where he is, the time when he requests a service, the date (whether it is a workday or a holiday); (3) Computing environment, which describes the computing environment of the user that is closely related to the software and hardware requirements to invoke a service. For example, the hardware device the user uses for service invocation, including the model, the operating system, the memory, CPU of the device and so on, the network where the user invokes a service, such as network delay, bandwidth, security level, and access pattern.


Example 3-1. On 1st Aug 2011, a user wants to translate some texts in Chinese into Spanish by using an online translating service. He submits the service request in Hangzhou by his mobile phone. The model of the mobile phone is HTC G7 with operating system android 2.2, CPU QSD8250 1GHz, 576MB RAM and 512MB ROM. The following segment is an example of the description of user's context information.
  <user profile>
  </user profile>
  <service invocation>
  <Natural Environment>
      <date>1st Aug 2011</date>
  </Natural Environment>
  <Computing Environment>
      <Hardware Device>
        <Model> HTC G7 </Model>
          <Operating System>Android 2.2
      </Operating System>
          <CPU>QSD8250 1GHz</CPU>
          <Memory>576MB RAM and 512MB ROM
      </Hardware Device>
    </Computing Environment>
  </service invocation>

4. Modelling Preconditions Expressions

Service description standards such as WSDL-S and OWLS do not support reasoning on service precondition satisfiability itself, although they may provide the framework to describe the preconditions that a service can be invoked successfully. Hence we need to formalize preconditions.

Definition 1. (Basic Symbol) The basic symbols of DL can be divided into several parts:

(1) a set of concept names [N.sub.C];

(2) a set of role names [N.sub.R];

(3) a set of individual names [N.sub.I];

(4) a concrete domain D consisting of a set of data, where each element is associated with a data type and a value;

(5) concept constructs {} (enumeration), [less than or equal to] (max number restriction), [greater than or equal to] (min number restriction), [for all] (any value restriction), [there exists](value existence restriction), [union] (union), [intersection] (intersection) and [logical not](negative);

(6) role construct - (inverse), [union] (union), [intersection] (intersection);

(7) formula constructs [logical not] (negative), [LAMBDA] (and), V (or).

Definition 2. (Role) R,T are roles in the following form:

R,T :: [equivalent to] r[absolute value of [r.sup.-]] R [union] T|R [intersection] T

where r [member of] NR. Roles can be divided into abstract roles and concrete roles. Abstract roles can be constructed by concrete roles and other abstract roles using [union] and [intersection]. [r.sup.-] represents the inverse of the role r. The inclusion relations between two roles and the inverse of a role are defined in the RBox.

Definition 3. (Concept) C,S are concepts in the following form:

C,S:: [equivalent to] c[absolute value of {u}] [less than or equal to] nS[absolute value of [greater than or equal to] nS [for all]S.C][there exists]S.C [absolute value of [logical not]S [absolute value of S [union] C] S [intersection] C

where c [member of] [N.sub.c], u [member of] [N.sub.I], and n can be any number. Hence a concept can be a concept name c, an individual instance {u}, a number restriction on another concept S denoted by [less than or equal to] n S or [greater than or equal to] n S which means the defined concept is composed of/has at least n copies of S ([less than or equal to]n S) or at most n copies of S([greater than or equal to]nS), a type restriction denoted by [for all]S.C which means any S must be of the type C, or [there exists]S.C which means there exists some S be of the type C, the inverse of another concept S denoted by [logical not] S. And concepts can be connected by union symbol [union] or intersection symbol [intersection].

A finite set of concept definitions with unique left-hand sides constitute TBox T. Concepts are called defined in T if concept names occur in the left-hand side of a definition in T, otherwise concepts are called primitive in T. And we set TBox T acyclic, i.e. no cyclic dependencies between concepts are not allowed.

Definition 4. (Formula) [psi], [phi] are formulae in the following form:


where u, v, [v.sub.1], [v.sub.2], [v.sub.n] [member of] [N.sub.I], C(u) and C(v) are concepts instantiated by individual u and v respectively, op can be =, [not equal to], <, [less than or equal to], >, [greater than or equal to], and R is a relation function between u and v. Hence, an atomic formula can be an arithmetic comparison between concepts denoted by C(u) op C(v); a test for set membership denoted by C(u) in ([v.sub.1], [v.sub.2])[parallel]{[v.sub.1], ... [v.sub.n]} where ([v.sub.1], [v.sub.n]) is a continuity interval and {[v.sub.1], ... [v.sub.n]} is a discrete set; a set comparison denoted by C(u) op some[parallel]all {[v.sub.1], ... [v.sub.n]}, where C(u) op some {[v.sub.1], ... [v.sub.n]} is equal to true when there exists some v [member of] {[v.sub.1], ... [v.sub.n]) that C(u) op v is true, while C(u) op all {[v.sub.1], ... [v.sub.n]} is equal to true when for all v [member of] {[v.sub.1], ... [v.sub.n]}, C(u) op v is true; and a user defined role relation R between individual u and v. Formula can be composed of atomic formulae in the above form and formula constructs. [psi][LAMBDA][phi] is true when [psi] is not true. [psi][phi] is true when [psi] and [phi] are both true. [phi][LAMBDA][phi] is true when either [psi] or [phi] is true.

Definition 5. (Precondition) P = {[[phi].sub.1], ... [[phi].sub.n]} represents the preconditions that must be fulfilled before a service can be executed successfully, where [[phi].sub.1]|1 [less than or equal to] i [less than or equal to] n is a formula.

Example 4-1. The online BabelFish translator services can convert text from one language to another language. This service has three inputs: the text to be translated, its language and the desired output language. There are total of nine languages supported by the translator. The precondition of the service requires that the input language and output language should be different.

LanguagePair [equivalent to] ([greater than or equal to]1 source) [intersection]([for all] source. Language) [intersection] ([greater than or equal to]1 target) [intersection] ([for all] target.Language)

SupportedLanguagePair [equivalent to] {(English, Chinese), (Chinese, English), (Korean, Chinese), (Chinese, Korean), (Spanish, English), (English, Spanish), (French, Italian), (Italian, French)}

LanguagePair (source, target) in SupportedLanguagePair

5. Reasoning On Precondition Satisfiablity

Based on the formalization of both context of service consumers and precondition of service execution, we can reason on the precondition satisfiability for service recommendation.

The reasoning problem can be divided into two kinds: the executability of a service instance and the realizability of a web service.

For a list of candidate web services, we need to identify whether the services can be executed successfully under the context of current consumer. The reasoning problem is defined as the executability of a service instance, which can be implemented as Definition 6 states.

Definition 6. (Executability of a service instance) Let [CT.sub.u] = {[T.sub.1] = [v.sub.1], [T.sub.2] = [v.sub.2], ... [T.sub.n] = [v.sub.n],} be the context description of a service consumer, in which [T.sub.i]|i = 1, ... n are properties belonged to the context ontology and [v.sub.i]|i = 1, ... n are instance values, let [P.sub.s] = {[[phi].sub.1] ... [[phi].sub.m]} be the precondition of successful execution of service s. For all [[phi].sub.j]|j = 1, ... m with arguments [alpha]1, ... [alpha]k, i.e. [[phi].sub.I][[v.sub.i1]/[[alpha].sub.j1], ... [v.sub.ik]/[[alpha].sub.jk]] and appropriate mappings between [T.sub.i]|i = 1, ... n and [[alpha].sub.jl]|l = 1, ... k, if the substitution of corresponding values into [[alpha].sub.jl]|l = 1, ... k, i.e. can be inferred to be true, then the service s is said to be executable under the context [CT.sub.u] of current user u.

Example 5-1. Identify whether the service s described in Example 4-1 can be invoked successfully by the user under the context u stated in Example 3-1, i.e. the executability of service instance in Example 4-1 under context in Example 3-1.

u.context/service invocation/purpose/input [left right arrow] s.Language Pair.source

u.context/service invocation/purpose/output [left right arrow] s.Language

LanguagePair(Chinese/source, Spanish/target) in Supported LanguagePair

= (Chinese, Spanish) in {(English, Chinese), (Chinese, English), (Korean, Chinese), (Chinese, Korean), (Spanish, English), (English, Spanish), (French, Italian), (Italian, French)} [??] False.

Hence we can conclude that the service s in Example 4-1 cannot be invoked successfully by user under context u in Example 3-1.

The second kind of reasoning is the realizability of a web service. For any web service, we need to identify whether there exists some state under which the web service can be executed successfully. If the service cannot be executed under any state, such service is meaningless. It can be implemented as Definition 7 states.

Definition 7. (Realizability of a web service) Let [P.sub.s] = {[[phi].sub.1], ... [[phi].sub.m]} be the precondition of successful execution of service s, let {[CT.sub.u1], ... []} be the context of service consumers who have tried to invoke s. If there exists some [CT.sub.ui] that [CT.sub.ui]|[P.sub.s] can be inferred to be true, then the service s is said to be realizable, otherwise, s is not.

Example 5-2. Identify whether the service s described in Example 4-1 is realizable.

u. context/service invocation/purpose/input[left right arrow]s. Language Pair.source

u. context/service invocation/purpose/output[left right arrow]s.Language

If u.context/service invocation/purpose/input = English and u.context/service invocation/purpose/output = Chinese, then LanguagePair(English/source, Chinese/target) in Supported LanguagePair [??] True.

And it is true for all the source and target pairs that belong to SupportedLanguagePair.

Hence we can conclude that there exists some context under which the precondition of s is true and s is realizable.

6. Conclusion And Future Work

In this paper, we propose to reason between service precondition and user's context information based on a lightweight DL in order to achieve accurate and efficient service recommendation in mobile network.

Our main contributions include: First, we construct context ontology and clearly define what properties should be described to express the environment when a user submits service request. Second, we detailed the formalization of service precondition based on a simplified DL. And third, we reason about the executability of a service instance and the realizability of a web service by inferring the satisfiability of service precondition under user's context.

In the future, we plan to develop tools that can formalize and reason on user's context and service precondition automatically, as well as conduct large scale of experiments for application of context aware service recommendation in mobile network.

7. Acknowledgement

The work is supported in part by the following funds: Zhejiang Provincial Natural Science Foundation of China under grant number Y1110591, Hangzhou Normal University under grant number 2010HSKQ0006, National Natural Science Foundation of China under grant number 61002009, Science and Technology Planning Project of Zhejiang Province under grant number 2010C31018.


[1] Papazoglou, M.P., Georgakopoulos, D. (2003). Introduction to a special issue on Service-Oriented Computing, Communications of the ACM, 46 (10) 24-28.

[2] Baader, F. (2003). The description logic handbook: theory, implementation, and applications. Cambridge University Press New York, NY, USA.

[3] Gill, A. (1962). Introduction to the Theory of Finite-state Machines. McGraw-Hill.

[4] Petri, C.A. (1962). Kommunikation mit Automaten. University of Bonn.

[5] Milner, R. (1989). Communication and Concurrency. Prentice Hall.

[6] Benatallah, B., Hacid, M.S., Rey, C., Toumani, F. (2003). Request Rewriting-based Web Service Discovery. Lecture notes in Computer Science: 242-257.

[7] Zhongzhi Shi, Liang Chang, (2008). Reasoning About Semantic Web Services with an Approach based on Dynamic Description Logics. Chinese Journal of Computers, 31(9) 1599-1611.

[8] Cali, A., Calvanese, D., Colucci, S., Donini, T.D.N.F.M. (2004). A description logic based approach for matching user profiles, In: Proceedings of the 17th International workshop on Description Logics: 187-195.

[9] Benatallah, B., Hacid, M.S., Leger, A., Rey, C., Toumani, F. (2005). On automating Web services discovery. The VLDB Journal, 14 (1) 84-96.

[10] Agarwal, S., Ankolekar, A. (2006). Automatic matchmaking of web services, In: Proceedings of the 15th international conference on World Wide Web: 45-54.

[11] Klusch, M., Fries, B., Sycara, K. (2006). Automated semantic web service discovery with OWLS-MX, In: Proceedings of the Fifth International Joint conference on Autonomous Agents and Multiagent Systems: 915-922.

[12] Baader, F., Lutz, C., Milicic, M., Sattler, U., Wolter, F. (2005). A description logic based approach to reasoning about web services, In: Proceedings of the WWW 2005 workshop on Web Service Semantics.

[13] Chang, L., Lin, F., Shi, Z. (2007). A Dynamic Description Logic for Semantic Web Service, In: Third International Conference on Semantics, Knowledge and Grid: 74-79.

[14] Shen, G., Huang, Z., Zhu, X., Yang, J. (2009). Reasoning about Web Services with Dynamic Description Logics, In: 2009 WRI World Congress on Computer Science and Information Engineering: 106-110.

[15] Chen, L., Hu, H., Shi, Z. (2009). Web Service Composition as Satisfiability Checking in Dynamic Description Logics, In: 2009 Eighth International Conference on Grid and Cooperative Computing: 55-60.

[16] Liu, S., Liu, D., Qi, H. (2009). Semantic Web Service Modeling and Composition Based on Description Logic Rule, In: 2009 International Conference on Information Technology and Computer Science: 205-208.

[17] Shi, Z., Dong, M., Jiang, Y., Zhang, H. (2005). A logical foundation for the semantic Web. Science in China Series F: Information Sciences, 48 (2) 161-178.

[18] Urbieta, A., Azketa, E., Gomez, I., Parra, J., Arana, N. (2008). Analysis of effects-and preconditions-based service representation in ubiquitous computing environments, In: The IEEE International Conference on Semantic Computing: 378-385.

[19] Dey, A.K., Abowd, G.D. (2000). Towards a better understanding of context and context-awareness. CHI 2000 workshop on the what, who, where, when, and how of context-awareness: 1-6.

[20] Feng, Z.W., He, K.Q., Li, B., Gong, P., He, Y.F., Liu, W. (2008). A method for semantic web service discovery based on context inference. Chinese Journal of Computers, 31 (8) 1354-1363.

[21] Yang, S.J.H., Zhang, J., Chen, I.Y.L. (2008). A JESS-enabled context elicitation system for providing context-aware Web services, Expert systems with applications, 34 (4) 2254-2266.

[22] Spanoudakis, G., Mahbub, K., Zisman, A. (2007). aware runtime web service discovery, In: IEEE 2007 International Conference on Web Services: 233-240.

[23] Doulkeridis, C., Loutas, N., Vazirgiannis, M. (2006). A System Architecture for Context-Aware Service Discovery. Electr. Notes Theor. Comput. Sci. 146 (1) 101-116.

[24] Bormann et al, F. (2005). Towards Context-Aware Service Discovery: A Case Study for a new Advice of Charge Service, In: 14th IST Mobile and Wireless Communications Summit.

[25] Choonhwa, L., Helal, S. (2003). Context Attributes: An Approach to Enable Context-awareness for Service Discovery. Symp. on App. & the Internet.

[26] Pawar, P., Tokmakoff, A. (2006). Ontology-Based Context-Aware Service Discovery for Pervasive Environments, In: IEEE Int. Work. on Services Integration in Pervasive Environments.

Li Kuang (1), Liang Chen (2), Yingjie Xia (1)

(1) Hangzhou Institute of Service Engineering Hangzhou Normal University, China

(2) College of Computer Science Zhejiang University, China {kuangli,cliang,xiayingjie}
COPYRIGHT 2011 Digital Information Research Foundation
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Kuang, Li; Chen, Liang; Xia, Yingjie
Publication:Journal of Digital Information Management
Article Type:Report
Date:Dec 1, 2011
Previous Article:A dynamic role-based authorization model in grid environment.
Next Article:The design and challenges of online reprogramming system for wireless sensor networks.

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters