A spatially aware policy conflict resolution for information services

1.Introduction

A pervasive computing environment is characterized by computing capabilities and effective use of smart spaces. Many critical elements of pervasive computing such as wireless networks are now viably commercial products. Ambient services are known as one of the main types of pervasive information services in which suitable information is presented to the users based on their surrounding geographical environments as their contexts. In other words, if a person is located in a predetermined domain of a service provider, he or she can receive appropriately relevant services [17]. For each service domain, there is a physical area called “service site” where the services are accessible. It should be noted that a “service site” is different from a “service domain”.

When service domains are characterized by geographic boundaries, domain overlapping may occur; and each user may be located in several domains simultaneously. In this case, what matters is the composition of services presented to the users. For example, similar or same services may be combined, or services of a domain can be given precedence over similar services in other domains [18]. “User context” was used in previous studies conducted on providing relevant services for such users. Context is any information used to characterize the situation of an entity [1]. User context is the information received directly from the user, such as name, age, username, and password. Since in pervasive information services on which this study is focused all of the users have the same privilege, utilizing the user context seems to be unnecessary. The aim of this paper is to provide the best information services for such users by minimizing the user role in providing services. Since such services are generic, the system does not need to identify users. On the other hand, users prefer to maintain privacy in information retrieval on many applications, especially in generic services. Therefore, user-based methods in which users are required to log in seem unnecessary. It is possible to replace the user context with other contexts, such as spatial and temporal ones. A spatial context provides information on the situation of an entity such as location, direction, and speed. For example, the destination of a user can be implicitly understood from his/her movement instead of asking him/her. The advantage of using spatial relationships for providing services is that they are independent from the user context. User privacy is maintained, too.

In order to clarify the aim of this paper, the following example is presented:

“Maria is a tourist who intends to visit a national museum. The service provider of the museum presents some information services such as visiting hours, introduction to various booths, and information on the existing objects. Such information is sent to those who are moving towards the museum. In addition, there is a restaurant near the museum that provides services as well. This restaurant broadcasts its menu to the users nearby. In this scenario, when Maria is located in two areas at the same time, i.e. the museum domain and the restaurant domain, an important issue is how to decide what composition of services should be provided to her at a given time. In such situation, a conflict is more likely to occur as two domains may have many services with different policy patterns sent to Maria at the same time. A large amount of services that may confuse the user is a source of conflict. One solution for resolving this type of conflicts is using Maria’s personal information for selecting relevant services which can be directly received from herself. For instance, based upon information captured from her registration in the system (i.e. name, age, address) we can anticipate her affairs. One of the weak points of this solution that uses personal information is invasion of privacy. In this scenario, maybe Maria would not like the system to accesses to her personal information without her consent. On the other point of view, since both of the above-mentioned services are generic, receiving user profile information seems to be redundant. Given that the generic services are a main type of smart services, we must access the user preferences without her direct supervision. For this aim, we utilize spatial contexts and topological relationships to reduce user intervention in service composition. For instance, when Maria is inside the museum building, she does not need to receive restaurant services. Here, “inside” is a topological relationship that can help the system to eliminate irrelevant services of restaurant”.

The rest of the paper is organized as follows: Section 2 focuses on the works related to service composition and policy conflict resolution. Section 3 presents a new methodology for resolving conflicts in overlapped service domains by utilizing spatial contexts and analyses. Section 4 introduces the case study. Section 5 presents the results and discussions. Finally, the conclusions are provided in Section 6.

2.Related works

Service composition is the construction of complex services from primitive ones, thus enabling rapid and flexible creation of new services. Service composition is the combination of many existing services in order to carry out a larger and more complex task. There have been many published studies on service composition in recent years. For example, to find the exact optimal execution plan, Zeng et al. [30] used linear integer programming, Gao et al. [11] used dynamic programming for linear objective function, while Aiello et al. [3] applied the Backward Breadth First algorithm and Wan et al. [25] adopted an efficient divide-and-conquer approach for service selection. Gaia dealt with conflicts occurring among simultaneously triggered rules in the same application [4]. It uses priority to resolve a conflict, which means, that if there are conflicting rules, the rule with the highest priority wins.

Since the ranking of web service combinations depends on user requirements and willingness for investment of resources, Agarwal and Lamparter [2] considered user constraints and preferences for calculating the rank of a web service composition. Gamha et al. [10] presented a framework for the semantic composition of web services handling user constraints. Karakoc et al. [14] presented an approach based on constraint programming for web service composition in order to model and schedule composite web services under user constraints. Unlike most previous methods, this method does not use pre-defined rules. Lin et al. [16] introduced a fuzzy method to solve the selection of web services in a global and flexible manner. They tried to express user preferences using fuzzy expression. Mokhtar et al. [22] captured both services-related and user-related contexts enabling service composition to be effectively context-sensitive. Yu and Reiff-Marganiec [29] introduced a new concept of composition context to drive runtime service selection and composition. They tried to develop a backward composition context based service selection approach (BCCbSS) for service composition. Ying et al. [28] utilized the event-condition-action (ECA) rules to manage web service composition for multimedia conference systems in the case of updating user needs. The appropriate event will trigger when the business process request changes and allows service rescheduling. Wang et al. [26] offered a framework for dynamic complex service composition based on multi-agent reinforcement learning to obtain adaptivity in a dynamic environment.

Providing the best composition of services requires policy conflict resolution; thus, there is a trend toward resolving conflicts in the ambient intelligent systems [23]. Conflict is a natural disagreement between different attitudes, beliefs, values, or needs [27]. So far, the techniques used for policy conflict resolution have been chiefly role-based; i.e. the fixed and dynamic policies are used in order to detect and resolve conflicts [6,7]. This means that the component of policy conflict resolution can manage and resolve conflicts based on the user group (e.g., general user, power user, or super user) [17]. The conflicts can be resolved according to the role hierarchy [24]. Service presentation can be done according to the importance and priority of services [13], and it is also possible that a user is allowed to receive only the services which have already been defined by the policy author based on his/her role [12,17,23]. One of disadvantages of nearly all mentioned studies is that at first, the user is recognized by the user context (username, password, ID, etc.), and then he/she is assigned to a group. Finally, conflicts are resolved based on the user role.

Our approach differs from previous works because we focus on spatial contexts such as topological relationships. In this approach, policy conflicts can be resolved through spatial contexts and analyses without user’s direct involvement.

3.Methodology

This section presents the architecture of the system and its main components first. Then it focuses on spatio-temporal topological relationships based on influenceability regarded as the basic relation for topological context. Finally, it illustrates the spatial rules for presenting the services.

Fig. 1.

The System Architecture.

3.3.Topological relationships between users and service sites

A topological relationship is a type of relationship in the space that describes our qualitative relationships with objects in an environment. Our requirement of objects can be a function of such relationships. In other words, we need the objects to which we are more related more than the objects to which we are less related. For instance, we need the services of a store more when we are near it in comparison with the time when we are far from it. Put another way, our requirements of nearby services change according to these relationships. In order to provide a suitable service composition for the user, it is necessary to consider his/her topological relationships with the service sites. Thus, spatio-temporal topological relationships were used in this study. In general, there are two viewpoints in topological relations, named point-set topology [8] and pointless topology [15]. In this paper, an influenceability relation used for modeling the pointless topology.

The spatial casual relation is also called influenceability. It means that objects are in contact with each other and influence other objects [19]. As an example, a moving car influences surrounding objects. An influenceability relation does not coincide with connection relation.

The influenceability relation, symbolized by ≺ is an order and primitive relation which is also an irreflexive, antisymmetric, but transitive relation.

Let X×X be the Cartesian product of X with itself. Then influenceability can be defined for every x,y∈X as:

x≺y:=RIn(1)={⟨(x,y),μIn(x,y)⟩|(x,y)∈X×X}

As a reflexive and symmetric relation [5] for two objects x and y, connection can be defined by influenceability:

∀x,yC(x,y)∀x,y:={[(x≺y)∨(y≺x)]∀x,y∧[(¬∃a)((x≺a≺y)(2)∀x,y∨(y≺a≺x))]}

where object x influences y, or y is influenced by x, and there is no object like a, the second part of the relation will be obtained. Therefore, all other exhaustive and pairwise disjoint relations in Region Connection Calculus (RCC) can be defined by influenceability relation.

3.3.1.Spatio-temporal topological relationships

It is assumed that the user and service site are two regions in our model. TPP or NTPP are considered for a user who is located “inside” the service site and DC relation is considered for a user “outside” it. The users who are located inside the service sites will receive all the services (level 1). The other spatio-temporal analyses are “entering” and “leaving” the service site. The users who enter a service site have the highest priority to receive relevant services. Conversely, presenting services to those who are leaving the service site seems to be unnecessary.

As in a similar study [9] for a point-based view, other definitions can be presented for region objects. The following relations can be proposed for entering and leaving the service site:

(3)Enter=DC⊳EC⊳PO⊳TPPi(4)Leave=Enter←

where DC, EC, PO and TPPi are exhaustive and pairwise disjoint relations. These relations can be derived from influeceability relation. The symbol ← means the definitions of leave and enter are vice-versa.

3.3.2.Influenceability relation modeling

In order to study influenceability relations, the first step is to model the effective objects, such as a user and a service site. The user model in a space-time framework is like a spatio-temporal cone. The spatio-temporal cone can be used as a mobile agent (in a fixed period of time) in pervasive environments [21]. The idea of spatio-temporal cone is borrowed from the light cone in relativity physics. It means that, the mobile agent can travel in the cone because of its speed [20]. The spatio-temporal cone can be defined as a portion of space-time containing all locations which mobile agent can reach from a particular location [20]. The apex of this cone is a user’s current location reported by a navigation system. The period will be defined by the user or the system. With respect to a given event, spatio-temporal cone separates space-time into three parts, inside and on the future spatio-temporal cone, inside and on the past spatio-temporal cone, and elsewhere [21]. In this paper, the focus is on the future part of this cone, because we want to present services in the near future.

Since in the real world, the user can be located just in the space ahead, then the direction of the user movement is applied to prepare the user model. The service site model is a cube (Fig. 2(a)). After the time interval Δt (at the time t), the user and service site will be as a circle sector and a 2D plane, respectively (Fig. 2(b))

Fig. 2.

Influenceability of the User and the Service Site Models: (a) In a spatio-temporal framework. (b) At the time t and applying the direction of movement.

After modeling the objects, the topological relationships are investigated using the influenceability relation. By considering x and y as a user and a service site respectively, the relations indicated in Table 1 express the influence of the user on the service site. If a user influences the service site, its services are in priority to be sent to him/her. Moreover, if a user influences several service sites, then the priority will be allocated to the site which was influenced the most.

Table 1

The Relations Extracted from the Influenceability Relation

Category	Logical relation
Externally Connection	EC(x,y):=C(x,y)∧¬O(x,y)
Partially Overlap	PO(x,y):=O(x,y)∧¬P(x,y)∧¬P(y,x)
Tangential Proper Part	TPP(x,y):=PP(x,y)∧∃z[EC(z,x)∧EC(z,y)]
Non Tangential Proper Part	NTPP(x,y):=PP(x,y)∧¬∃z[EC(z,x)∧EC(z,y)]

4.Case study

In order to implement the proposed approach, an area was considered consisting three nested domains. The first domain sends information services to the users within a 250-meter radius of a hospital. The second domain sends advertising information including sports fields, class times, and competition dates to the users within a 200-meter radius of a gymnasium located near the hospital. The third domain belongs to a shop near the last two domains. In this domain, the information regarding electronic devices, home appliances, sales, and the bestselling products will be sent to the users within a 200-meter radius of the shop (Fig. 3).

Fig. 3.

Service Sites and Service Domains in the Case Study.

After collecting the data derived by tracking the users by GPS, the server analyzes the topological relationships between the user and the service sites. Furthermore, Android simulator was employed to present services on the user device. A sample output will be something similar to the illustration in Fig. 4.

Fig. 4.

A Sample of the Output.

Now the system performance in different spatial contexts is explained in two scenarios meant consider the important situations.

Scenario 1

A user located in (437549, 4111494) UTM 39S as the start point moves towards the shop at an average speed of 1.1 m/s and in an approximate direction of 10 degrees (Fig. 5). As it can be seen in this figure, in spite of going towards the shop site, the user has no effects on it. Since the shop is active in the time of tracking, the system will present the information to the user in level 4.

Fig. 5.

The Output on the User Device.

Fig. 6.

The Output on the User Device.

Scenario 2

A user located in (437500, 4111502) UTM 39S as the start point, leaves the hospital at an average speed of 1.6 m/s and in an approximate direction of 40 degrees (Fig. 6). In this case, the system does not send the hospital information to the user; however, it sends services of the shop and the gymnasium in level 4. Since the user had declared that he was just willing to receive the gymnasium information, sending the information of the shop is not pleasant to him. When tracking continued and the user got closer to the gymnasium, its information was in priority, and the user was more satisfied with the result.

5.Results and discussions

In this paper, user studies are employed to evaluate recommender systems from a user’s perspective. For this purpose, 40 individuals were asked to move toward their favorite service sites in the multiple domains and select their favorite service sites. Figure 7 shows a sample of user interaction with the system.

Fig. 7.

Selecting Favorite Service Sites by a User.

Fig. 8.

The Users Satisfaction Levels for the Proposed Services.

Finally, according to the surveyed test users, their satisfaction levels were described in three categories as good, average, and weak concerning to the presented services. For example, the users in Scenarios 1 and 2 declared that the proposed services were good and average, respectively. The results are shown in Table 3. Based on the results, 75% of the participants were satisfied with the services and described them as good level (Fig. 8).

User satisfaction depends on receiving services at the right time. In this study, because data were collected by spatial sensors, it is faster than the methods based on receiving data from the users (e.g. user context). Therefore, the services are updated at an acceptable time.

The total time required to discover and update the relevant services for a user by the proposed system is as follows:

The updating time for the same system based on the user context is as follows:

As it can be seen in the second method, the times T1, T2, and T3 are added to T. Among them, T2 is varied for different users, because people react differently in answering the context questions (for example, what is your name?). Therefore, another advantage of the proposed model is reducing the time of updating services or the time users take to wait for receiving services. According to the results of surveying the participants, 80% of them were satisfied with the time of service update (Fig. 9).

Fig. 9.

Users Satisfaction Levels for Service Updating Time.

Furthermore, an experiment was conducted to prove that the topological relationships could be regarded as one of the criteria for providing services. For this purpose, the services are provided both with and without considering topological relationships. Then, the mean absolute error (MAE) is taken to measure the error range between the prediction preference value and true preference value. MAE is a commonly used quantity to measure how close forecasts or predictions are to the eventual outcomes. Then MAE was calculated through the following equation:

In order to provide the actual value, participants are asked to rate each service based on their own preference. In this way, 1 is the least favorite, and 5 is the most favorite. The results are shown in Fig. 10.

Fig. 10.

Comparing MAE with and without Considering Topological Relationships.

Fig. 11.

A Building Floor at the University Campus.

This comparison confirmed our reasoning to the use of topological relationships. The results indicate that topological relationships can be significantly effective in providing users with services, especially in a mobile environment with respect to continuous changes in spatial relationships between users and objects.

To evaluate the performance of the proposed method, the results are compared with traditional role-based service composition in [18]. The services provided in the current study are generic; however, the services provided in [18] were role-based. In generic services, either no roles are defined, or all of the roles are equally important to the service provider. To compare the two methods, we assume that all of the services are of the same priorities. To do this, we define three logical areas; i.e. Office Logical Area, External Logical Area, and Library Logical Area in a floor area of a section of K.N.Toosi University campus (Fig. 11). Experiments are carried out in both spatial and role-based modes. According to [18], users were divided into three groups (Student, Lecturer, and Administrator). The tables of rules were also taken into account. In this method, users were first asked to log in to the system; so that they could be identified. In the other method, the tables of rules were defined according to the spatial relationships proposed in our study. In this case, users were not required to log in to the system. Then MAE was calculated for them. The result is shown in Fig. 12.

Compared with the role-based method, the proposed method may be a little inaccurate. One reason is that this study is concentrated on information services; however, the services defined in [18] are role-based. It is obvious that if we have more information than users do, the results will be more accurate. Since the results were obtained without needing to log in to the system, and they were simply based on spatial information, the accuracy is acceptable. The main advantage of the proposed method over the role-based method is that it can support mobility, too, because of considering spatial relationships, especially topological relationships. However, such a problem was not considered in [18]. For instance, the proposed method does not send library services to a student who intends to exit the library. However, the method used in [18] sends library services until the user position is not entirely outside the library logical area. This is because this method does not consider user direction and topological relationships.

Fig. 12.

Comparison MAE.

6.Conclusion

Due to the variety of ambient services, they have attracted a great deal of public attention in recent years. Due to domain overlapping, the number of users located in multiple domains is increasing. The important issue about these users is deciding upon the services which should be sent to them. In this study, the spatial contexts and analyses such as spatial topological relationships between the users and service sites were used in the policy conflict resolution. Moreover, spatio-temporal topological relationships and the influenceability relation were utilized in order to model the topological context. Based on the results, 75% of the users were satisfied with the provided services, something which indicates an acceptable performance of the proposed approach in utilizing spatial contexts and analyses.

Another advantage of the proposed approach is using spatial sensors instead of the user contexts. Using spatial sensors makes the system independent from the user. It means that eliminating the time of sending and receiving contextual information between the server and the user will reduce the time of updating the services. In addition, the spatial sensors are easily available and do not impose an overhead time on the system. Time saving is an important advantage of the system, because inappropriate time of updating services will cause conflicts for the users. The results also indicate that 80% of the users were content with the updating time of the services.