s2fieldsofstudy:
Computer Science
Business

text:
A Cloud-based Approach for Context Information Provisioning

As a result of the phenomenal proliferation of modern mobile Internet-enabled devices and the widespread utilization of wireless and cellular data networks, mobile users are increasingly requiring services tailored to their current context. High-level context information is typically obtained from context services that aggregate raw context information sensed by various sensors and mobile devices. Given the massive amount of sensed data, traditional context services are lacking the necessary resources to store and process these data, as well as to disseminate high-level context information to a variety of potential context consumers. In this paper, we propose a novel framework for context information provisioning, which relies on deploying context services on the cloud and using context brokers to mediate between context consumers and context services using a publish/subscribe model. Moreover, we describe a multi-attributes decision algorithm for the selection of potential context services that can fulfill context consumers' requests for context information. The algorithm calculates the score of each context service, per context information type, based on the quality-of-service (QoS) and quality-of-context information (QoC) requirements expressed by the context consumer. One of the benefits of the approach is that context providers can scale up and down, in terms of cloud resources they use, depending on current demand for context information. Besides, the selection algorithm allows ranking context services by matching their QoS and QoC offers against the QoS and QoC requirements of the context consumer.

INTRODUCTION
The proliferation of wireless and cellular networks over the last few years has led to a remarkable rise in the number of users who are using a variety of modern mobile Internetenabled devices --such as iPhones, iPads, and Android-based smartphones--to consume online services. Mobile users are increasingly requiring services tailored to their context as they are on the move. Therefore, enterprise services should be context-aware to deal with the changing environment of the user. Several definitions of the notion of context have been provided in the literature. According to Dey [1], "Context is any information that can be used to characterize the situation of an entity. An entity is a person, place, or object that is considered relevant to the interaction between a user and an application, including the user and applications themselves." According to this definition, the amount of information that can be categorized as context information is extremely wide. Location, time, temperature, humidity, pressure, and mobile user activity are the most widely used context indicators by applications. Specialized services, that we call context services, capture, store, analyze and aggregate data to provide high-level context information to consumer application services as needed. Context services and context consumers are often physically distributed. Besides, it is likely that these context sources provide the same context information but with different QoC [2] [3]. The QoC concept is explained in Section 3. Context-awareness raises challenges like aggregation of context information in a structured format, discovery, and selection of appropriate context services for context delivery to context consumers.
To cope with the issues of context delivery and context service selection, we propose a novel framework for context provisioning, which is relying on using components called context brokers, and deploying context services on the cloud. Context brokers mediate between context consumers and context services using a publish/subscribe model. To the best of our knowledge there was no previous work on deploying context services on the cloud. We believe that our approach will take advantage of the power of the cloud in terms of elasticity, storage abundance, and scalability. Furthermore, we describe a multi-attributes algorithm for the selection of context services on the basis of the QoS and QoC they can offer. The algorithm takes into account the QoS and QoC requirements of context consumers for each context information to which they subscribe with the Context Broker.
The remainder of the paper is organized as follows. Section 2 describes related work on context-awareness and context information provisioning. Section 3 provides background information on the concepts of cloud services and quality-ofcontext. Section 4 presents an overview of our proposed framework, describes the interactions among the framework components and our proposed algorithm for the selection of context services in both a single cloud and multiple clouds. Section 5 discusses the challenges of the approach. Finally, Section 6 concludes the paper and describes future work.

II. RELATED WORK
Over the last two decades, context provisioning has been a particularly popular research topic, especially with the advent of smart mobile devices, the advances in sensing technology, and the proliferation of mobile applications. Many research works have proposed, designed, and implemented frameworks and middleware infrastructures for managing context information and providing users with context-aware services. Moreover, many surveys have been made in order to understand the features and shortcomings of existing systems [4][5] [6].
With the emergence of service-oriented computing, numerous research works have investigated the design and the implementation of context services. A context service typically provides infrastructure support for collection, management, and dissemination of context information vis-àvis a number of subjects. Subjects may be users, objects such as handheld devices and equipment, or the environment of users. The context service acquires context information from various context sources. For example, consider the -temperature‖ at the current location of the mobile user; this information may be obtained directly from the mobile device of the user. It can also be obtained from a local weather station. Alternatively, it may be obtained from weather TV channels providing weather information nation-wide.
Schmidt et al. designed and implemented a generic context service with a modular architecture that allows for context collection, discovery and monitoring [7]. This context service provides a Web service interface that allows its integration in heterogeneous environments. The implementation uses OWL to describe context information and SPARQL to query and monitor context information.
Lei et al. described the design issues and the implementation of a middleware infrastructure for context collection and dissemination [8]. They realize this middleware infrastructure as a context service. To allow for wide deployment of the context service, this work has addressed the following issues: extensibility of the context service architecture by supporting heterogeneous context sources, integrated support for privacy, and quality of context information support. Coronato et al. proposed a semantic context service that relies on semantic Web technologies to support smart offices [9]. It uses ontologies and rules to infer high-level context information, such as lighting and sound level, from low-level raw information acquired from context sources.
As it was described in the surveys mentioned earlier, many of the existing context-aware systems are suffering from the lack of scalability, extensibility, interoperability, and adoption difficulties. The originality of our approach lies in bringing context management and delivery to the cloud by deploying context services on the cloud. We believe that our approach will benefit from the power of the cloud in terms of scalability, elasticity, cloud storage abundance, and scaling up and down.

A. Quality-of-Context
Context information is characterized by some properties referred in literature as QoC indicators. Buchholz et al. [2] have defined the QoC as: "Quality of Context (QoC) is any information that describes the quality of information that is used as context information. Thus, QoC refers to information and not to the process nor the hardware component that possibly provide the information." Buchholz et al. [2] and Sheikh et al. [3] have identified the following QoC indicators: precision, freshness, temporal resolution, spatial resolution, and probability of correctness.
Precision represents the granularity with which context information describes a real world situation. Freshness represents the time that elapses between the determination of context information and its delivery to a requester. Spatial resolution represents the precision with which the physical area, to which an instance of context information is applicable, is expressed. Temporal resolution is the period of time during which a single instance of context information is applicable. Probability of correctness represents the probability that a piece of context information is correct.
Several competing context services may provide the same context information [2]. Therefore, potential context consumers should be able to select context services on the basis of the QoC they can assure.

B. Cloud services
Cloud computing enables a service-provisioning model for computing services that relies on the Internet. This model typically involves the provisioning of dynamically scalable and virtualized services.
Applications or services offered by means of cloud computing are called cloud services. Typical examples of cloud services include office applications (word processing, spreadsheets, and presentations) that are traditionally found among desktop applications. Nearly, all large software corporations, such as Google, Microsoft, Amazon, IBM, and Oracle, are providing various kinds of cloud services. Besides, many small businesses have launched their own Web-based services, mainly to take advantage of the collaborative nature of cloud services.
The user of a cloud service has access to the service through a Web interface or via an API. Once started, the cloud service application acts as if it is a normal desktop application. The difference is that working documents are on the cloud servers.
Cloud services models are: organizations rent computing resources and storage space and access them through a private network or across the Internet.
 Platform-as-a-Service (PaaS): With PaaS, organizations can develop their business applications in a cloud environment by using software tools supported by their cloud provider. Maintenance and management of the cloud infrastructure including severs and operating system is the responsibility of the cloud provider.
 Software-as-a-Service (SaaS): With SaaS, the cloud service application runs on the cloud provider servers and users access the service through a Web interface or via an API.

IV. A FRAMEWORK FOR CLOUD-BASED CONTEXT PROVISIONING
In every business with a delivery/consumption model, brokers emerge to mediate between consumers and providers. This could be the case for context delivery. Context brokers may, then, be used to decouple context consumers from context services. Our interest in using brokers is motivated by the fact that they have been used for a while in Service Oriented Architecture (SOA) to mediate between services providers, service consumers, and partners. They have also been extensively used in multimedia systems and in mobile computing systems to deal mainly with the issue of QoS management. Context-aware Web services (context consumers), Context Brokers, and Cloud-based Context Services. Multiple context brokers may be deployed, one for each local domain for instance. A discovery service will allow context-aware consumers to bind to the right context broker.

A. Context Brokers
A context broker is a mediator service that decouples context consumers from context services. It is in charge of handling subscriptions of context consumers in which they express their interest to receive context information, and registration of context services. Context services may then publish their newly acquired context information to the context broker, which notifies context consumers about that newly acquired context information. Context brokers can also be deployed on the cloud. Fig. 2 illustrates our topic-based publish-subscribe system in which context services are the publishers and the CAWSs are the subscribers. Context information --such as location, temperature, and user activity --represents the topics of the system. The Publish/subscribe messaging model is a one-to-many pattern of asynchronous message distribution based on registration of interest. In this model, publishers associate the name of a topic to each message (-publish‖) rather than addressing it directly to subscribers. Then, the message system sends the message to all eligible recipients that expressed their interest in receiving messages on that topic (-subscribe‖). As opposed to point-topoint messaging systems, such as message queuing, the publish/subscribe model of asynchronous communication is a far more scalable architecture. This is because the source of the information has only to concern itself with creating the information, and can leave the task of servicing potential recipients to the messaging system. It is a loosely coupled architecture in which senders often do not need to know who their potential subscribers are, and the subscribers do not need to know who generates the information.
In addition to this publish/subscribe model for provisioning context information, a context broker implements a regular on-demand request/response model, in which it requests up-to-date context information from context services once a context consumer requires information for a given topic. Therefore, a context broker may either pull context information from context services or let context services push updated context information.
Context services, typically residing in different clouds, deliver context information to context consumers with various quality-of-context and quality-of-service (QoS). Therefore, the Context Broker is in charge of selecting appropriate context services to deliver context information to which a context consumer has subscribed. Context information may be delivered to the same consumer by several context services. Each one may deliver a piece of context information (a topic) that the consumer requires to adapt its behavior to the current context of a user. In Sub-section 4.5, we describe a selection algorithm that allows ranking context services with regard to the QoC and the topics required by a context consumer.

B. Context Consumers
In our framework, context-aware Web services (CAWS) are the consumers of context information obtained from the cloud-based context services. A CAWS is a Web service that can understand situational context and can adapt its behavior according the changing circumstances as context data may change rapidly. It produces dynamic results according to the 5 WH questions: who, where, when, what, and why it was invoked. A CAWS can be responsive to various situational circumstances, such as:  The identity of the client who invoked the service, whether it is a person, or another Web service.
 The location of the client.
 The time at which the client invokes the service.
 The activity that the client is carrying out at the time it invokes the service.
 The preferences that the client may have defined prior to invoking the service.
 The security and privacy policies associated with the client of this service.
 The device (laptop, PDA, smartphone, etc.) that the client is using to invoke the service.

C. Cloud-based Context Services
As we have mentioned earlier in the related work section, high-level context information is typically obtained from context services that aggregate raw context information sensed by sensors and mobile devices. Given the massive amount of context data processed and stored by context services and the wide acceptance of the cloud computing technology, context providers now can leverage their services by deploying them on the cloud. Fig. 3 depicts the process of context acquisition and the deployment of context services on the cloud to provide highlevel context information to context consumers. Raw context data sensed by various devices and sensors is processed, aggregated by Context Aggregator components in a structured format, and then uploaded to the cloud-based context services. One of the underlying advantages of the deployment of context services in the cloud is the economy of scale. By making the most of the cloud infrastructure provided by a cloud vendor, a context provider can offer better, cheaper, and more reliable services than is possible within its premises. The context service can utilize the full processing and storage resources of the cloud infrastructure if needed. Another advantage is scalability in terms of computing resources. Context providers can scale up when additional resources are required as a result of a rise in the demand for context information. Conversely, they can scale down when the demand for context information is decreasing. Another benefit of the approach is to enable context-aware application services to acquire their required context information on a pay-as-yougo basis and to select cloud-based context services on the basis of the price they have to pay and other criteria, such as the QoC they can get. Furthermore, context-aware applications can obtain context information from cloud-based context services without having to be involved in context management. The net benefit for consumers and mobile users, in particular, is the ability to receive better services tailored to their current context. The SaaS model is the most appropriate model for cloudbased context provisioning. Indeed, SaaS is seen as the trend of the future and the most common form of cloud service development. With SaaS, software is deployed over the Internet and delivered to thousands of customers. Using this model, the context service provider may license its service to customers through a subscription or a pay-as-you-go model. The service is then accessible using an API.

D. Interfaces and Interaction model
In this section, we describe the interactions among the components of the framework and do consider only the case of a single context broker. The model can be easily extended to consider several context brokers. Fig. 4 shows a simplified class diagram of the framework components, and

The context broker acts as an intermediary between publishers (context services) and subscribers (context consumers) on a collection of topics (context information).
A context consumer invokes the subscribe() method of the context broker to register its interest to receive updates on some topics, such as location, and temperature. If the processing of subscribe() is successful, the context broker returns a subscription ID to the context consumer.
Similarly, a context service invokes registerContextService() of the context broker to register its interest to publish some types of context information through the context broker. If the processing of that method is successful, the context broker returns a registration ID to the context service.
The context broker receives notifications of context change through its notify() method that a context service invokes. It, then, notifies a context consumer about context change by invoking its notify() method. Furthermore, a context consumer may request the current value for a given topic by invoking getCurrentTopicValue() of the context broker. The broker forwards the request to context services that are providing that topic requested by the context consumer. A newly-subscribed context consumer can invoke getLastTopicValue() in order to get the last value of a given topic that other consumers have already received.
The context broker has also two additional methods findContextConsumers() and findContextServices() that are self-invoked. The former is invoked to get the list of context consumers that have subscribed to a given topic once a notification of context change has been received for that topic. The latest is invoked to get the list of context services that are publishing the topic requested by a context consumer that has invoked getCurrentTopicValue().
A context aggregator can register at a context service by specifying what topics it is an aggregator for. Once registered, a context aggregator can submit the current value for a given topic by invoking the setTopicValue() method at the context service. When the topic value is changed in the context service, the notify() method at the context broker is triggered to notify all subscribers of that topic.

E. A Multi-attributes Algorithm for Context Services Selection
As we have stated earlier, the Context Broker is in charge of selecting suitable context services to deliver context information to which context consumer (CAWS) subscribed. Context information may be delivered to the same context consumer by several context services. Each one may deliver a piece of context information (a topic) that the context consumer requires to adapt its behavior to the current context of a user. Thus, the selection has to be done per topic. In this subsection, we describe our proposed algorithm for context services selection. The algorithm allows ranking context services with regard to the QoC and the QoS required by a context consumer. We first describe how the algorithm works in the case of a single cloud; then, we extend the algorithm to the case of multiple clouds as depicted by Fig. 1.

1) Single Cloud-based Service Selection
As numerous potential context services, within the cloud, can deliver the context information required by a consumer, it is indispensable to consider only potential context services that can satisfy both the QoC and the QoS required by the context consumer.

Let
be the list of context information (topics) to which a context consumer has subscribed by showing its interest in receiving such context information. Let be the list of context services in the cloud that have subscribed with the Context Broker. Two context services may provide different context information; each one specializes in offering particular context information. One service, for example, may offer location information while another service may offer only temperature information, and a third one may offer both of them.
These services typically provide context information with different QoC and QoS. We assume that QoC and QoS indicators are in normalized form with values between 0 and 1. A value of 1 means highest quality and 0 means lowest quality. For example for the freshness quality indicator, 1 means that context sources have sensed the information in the last minute, and 0 means that they have sensed it in the last 10 minutes. QoS indicators may concern for instance parameters such as availability, response-time, reputation, and cost of service.
When subscribing to context information, a context consumer specifies the min values of the normalized QoC and QoS indicators that he can tolerate. For instance, the context consumer may subscribe to the location information may require a min value of 80% for the freshness indicator, 93% for the probability of correctness indicator. He may require also 98% for the Availability QoS indicator. Let be the list of QoC indicators (parameters) considered in the system. Let be the list of QoS indicators considered in the system.
The minimum QoC requirements that the context consumer tolerates for a given context information (topic) are expressed by the following vector: , with and is the cardinality of .
Therefore, the whole quality-of-context requirements of the context consumer for all its subscribed topics and all QoC indicators considered in the system can be expressed by the following matrix: The minimum QoS that the context consumer tolerates concern all topics, are expressed by the following vector: .
represents the minimal value that the context consumer is willing to accept for the QoS parameter , for A zero value in any QoC or QoS parameter means that the user has not specified any constraint on that parameter.
The goal of the selection algorithm is to find for each topic , to which the context consumer subscribed, a suitable context service from the set that can satisfy the minimum quality requirements of the context consumer.
The QoC offer of a context service is expressed by the following matrix: The QoS offer of is expressed by the following vector: , Where is the offer of for the QoS indicator ; .
The quality-of-service requirements of the context consumer are independent from the topics.
is suitable for a topic if the following condition is satified: for and and for (1) In other words, is suitable for provisioning topic if the minimum quality-of-context requirements as well as the minimum quality-of service requirements are satisfied.
In the following, we will consider in the selection process only context servers that meet the minimum QoS requirements of the context consumer.
The context consumer may set relative weights for the QoC indicators. He may even set weights for each topic to which it subscribed. For example, for the location topic, more weight may be given to the spatial resolution indicator than to the probability of correctness indicator. For the time of the day topic, more weight may be given, for example, to the precision indicator than to the other QoC indicators. Therefore, the weight matrix is given by: The score of a given QoC indicator for a given topic by the offer is: for and (2) Therefore, the score matrix of the offer, for all QoC indicators and all topics is: Given the weight matrix and the minimum QoC requirements matrix, the minimum score matrix is: Where for and The difference matrix, , shows whether may satisfy or not all QoC requirements for all topics to which the context consumer has subscribed to. A value that is less than zero in this matrix means that cannot satisfy the QoC requirement for the associated topic and QoC indicator. Therefore, we have to reason per topic, and consider only context services that can meet the QoC requirement for that topic.
The score per topic for a potential context service offer is: . ( The score of for all topics can be expressed by the following vector: Considering the scores of all the potential context services, we get the following decision matrix: A score in the decision matrix is zero if the context service cannot meet the QoC requirements for a given topic.
The maximum score value of each row j corresponds to the best QoC offer that can fulfill the QoS and QoC requirements of the context consumer for the topic .
The most suitable context service for topic , that we call here , will be the one that maximizes the above score, that is: . (4) If no context service satisfies the context consumer QoS and QoC requirements for a given topic, then the Context Broker may ask the context consumer to lower its QoC expectations.
The steps of the algorithm are summarized in Fig. 6.

2) Multiple Clouds-based Service Selection
The previous subsection describes how the ranking and selection of context services is achieved within a single cloud. In order to find out the most suitable context services, for each topic, within multiple clouds, the context broker selects potential context services in each cloud according to the algorithm described in the previous sub-section. Selected context services from the clouds are then ranked to find out the best context services per topic, which maximizes the score expressed by equation (3).
Step-1: Construct the matrix of minimum QoC requirements of the context consumer for all the topics it subsribes to, and the vector S of minimum QoS requirements the context consumer can tolerate. We assume that all values of the matrix and the vector are normalized to be in the range [0,1].
Step-2: Construct the weight matrix W set by the context consumer for each topic and for each QoC indicator, then the minimum score matrix .
Step  (3). Note that rows with negative values in the difference matrix will have a score 0 in the score vector.
Step-4: Create the decision matrix, and fill out the maximum score for each topic and the CS providing that score. In conjunction with the benefits provided by the cloud, deploying context services to the cloud raises numerous issues for context providers to consider, including possible interoperability, security, and performance concerns.
The interaction model described in the previous section provides the basis for the development of a context service API that will be used by both context brokers and context consumers to interact with context services. Heterogeneity of the APIs offered by various context services will be one of the challenges of the approach, especially if they are residing on different clouds. Context brokers should, then, be able to interoperate with all these heterogeneous context services.
Security is a significant concern with any SaaS application on the cloud. Care must be taken when designing and implementing a security solution for a cloud-based contextservice to keep it as simple and efficient as possible. For instance, the context service may have to be integrated with an identity management service. In this scenario, each customer of the context service has an identity account, which is used to authenticate the customer and track all its requests for service.
Performance monitoring, billing, managing customers' expectations are also significant concerns among others that a context service provider has to handle. The context provider must ensure that its context service is highly available and that its customers can access it. One outage or crash of the service can affect all its customers. Now, there is a general trend toward implementing a Service Level Agreement (SLA) between providers of cloud services and customers, even though that most SaaS vendors do not provide them at present.
Another concern, which is not linked to the cloud, but that should be handled by context brokers and consumers is the heterogeneity in the representation and modeling of context information by each context service. Bettini et al. [10] provide a survey in which they describe and compare current context modeling and reasoning techniques. Strang et al. [11] provide another similar survey. Modeling approaches mainly include key-values models, graphical models, object-oriented models, markup scheme models, logic-based models, and ontologybased models. With this heterogeneity in context information models, context brokers should provide a common ontologybased context information model and the mappings from the various models to this common model.

VI. CONCLUSION AND FUTURE WORK
High-level context information is typically obtained from context services that aggregate raw context information sensed by sensors and mobile devices. Given the enormous amount of context data processed and stored by context services and the wide acceptance of the cloud computing technology, context providers now can leverage their services by deploying them on the cloud.
In this paper, we have presented our proposed framework for cloud-based context provisioning. The framework relies on context brokers for context information dissemination using a publish/subscribe model. Context services, deployed on the cloud, can scale up and down, in terms of cloud resources they use, according to the demand for context information. We have described a preliminary model of interactions, among the components of the framework, and that could be the basis for a context service API. As a future work, we first intend to investigate further on a common ontology-based model for context information representation that can be used by context brokers; and then, describe the mappings from the various context representation models described in the literature to that common model. We also intend to implement a prototype of the framework by considering some real scenarios for context provisioning, and implementing a context broker and few similar cloud-based context services using open-source software tools.


Formal definition of a user-adaptive and length-optimal routing graph for complex indoor environments

Car routing solutions are omnipresent and solutions for pedestrians also exist. Furthermore, public or commercial buildings are getting bigger and the complexity of their internal structure has increased. Consequently, the need for indoor routing solutions has emerged. Some prototypes are available, but they still lack semantically-enriched modelling (e.g., access constraints, labels, etc.) and are not suitable for providing user-adaptive length-optimal routing in complex buildings. Previous approaches consider simple rooms, concave rooms, and corridors, but important characteristics such as distinct areas in huge rooms and solid obstacles inside rooms are not considered at all, although such details can increase navigation accuracy. By formally defining a weighted indoor routing graph, it is possible to create a detailed and user-adaptive model for route computation. The defined graph also contains semantic information such as room labels, door accessibility constraints, etc. Furthermore, one-way paths inside buildings are considered, as well as three-dimensional building parts, e.g., elevators or stairways. A hierarchical structure is also possible with the presented graph model.

Introduction
With the technological improvement of mobile devices, today's navigation systems offer a variety of functionalities for nearly any kind of requirement, but they are mainly designed for outdoor environments and hardly offer any solutions for indoor routing. By comparing indoor and outdoor space, it is evident that there are objects such as rooms or distinct areas in huge halls which do not have a counterpart in the outdoor street network (e.g., corridors can be compared to streets etc.), resulting in a complicated path network construction process. Nevertheless, there is an increasing need for specialized indoor solutions. Public buildings such as airports or shopping malls have become bigger and their internal structures have become more complex, resulting in a very complicated overall structure so that even familiar persons are likely to get lost when searching for a particular room or place. If the person is unfamiliar with the inner building structure, there is an even stronger need for proper guidance. [1,2] The field of application for indoor routing is very broad and there are many diverse application scenarios, e.g., emergency routing or personal routing at the airport. [3] Routing a person through space can be generalized to finding the shortest path between two nodes in a network. Well proven algorithms such as Dijkstra, [4] A* [5] and various specialized algorithms and heuristics, can compute shortest routes, but the creation of a network model is required beforehand. Several efforts (cf. next chapter) have been made in creating indoor networks, but existing approaches lack details and can only provide coarse routes without considering complex interior structures. Furthermore, none of the existing approaches tries to formally define a graph model for indoor environments, although existing approaches utilize graphs.
The main contribution of this paper is the formal definition of an improved indoor routing graph that allows route computation in complex indoor environments. The presented graph allows length-optimal routing based on the (complex) geometry of indoor spaces, whereby computations can be user-adaptive. The graph elements are manually extracted from floor plans and additional semantic information is collected for different functions of the graph. By applying a shortest path algorithm on the graph, the shortest route between two distinct points can be obtained. Detailed routing information, e.g., travel distances, etc., can also be obtained from the graph segments.

Related work
According to Pradhan [6] and Brummit & Shafer [7] indoor space models can be separated into two different classes. The so called topological/semantic class contains models relying on abstract descriptions of spatial relations (e.g., "Office X is near the Elevator"). In contrast, so called metrics models rely on concrete measurements of distances and angles (e.g., "The distance from Office X to Office Y is 12.3 meters"). Early examples for such topological models are presented by Raubal & Worboys [8] or Brummit & Shafer, [7] but they all lack geometric aspects, thus they are not usable for computing optimal routes and predicting distances.
In contrast, Gilliéron & Bertrand [9] invented an indoor space representation model based on CAD files. The files only contain metric information, i.e., manual enrichment with semantic data is required. In doing so, information about locations, shapes and topological relations of spatial entities (e.g., rooms, corri-dors, hallways, etc.) can be received. Afterwards all available data are used to derivate a so called link/node view of the building network. The authors decided to model each room as one node and corridors as a huge link with connection nodes. However, this procedure rather provides a very abstract view on the topology than a detailed perspective on the geometry. Important constraints and details such as the position of doors or obstacles inside rooms are not considered at all. A hybrid spatial model for indoor environments, which consists of hierarchically structured paths and optional semantic information, is presented by Lorenz et al. [10] They propose a direct mapping for small building instances (e.g., small rooms, corridors) to nodes in the graph. Furthermore, pathways between rooms are described as links. For gangways, they propose decomposing cells into several non-overlapping disjoint cells (cf. Fig. 1). This approach has been extended, so that also rooms with a concave shape can be modeled. [11] A three-dimensional navigable data model is described by Lee. [12] The network model is deviated via Poincaré duality combined with a graph-theoretic framework, a hierarchical representation schema and a straight-medial axis transformation. [13,14] The model contains two dual graphs, where one contains topologic information and the other one geometric aspects. Thereby, the separation into two different graphs is similar to the ISO standard 19107:2003 for describing the spatial characteristics of geographic features. [15] Other modelling frameworks following this standard are described by Becker et al. [16] and Becker et al. [17] Moreover, the latter one is also utilized for defining the format IndoorML, a LOD4 CityGML based format for exchanging interior models. [18] Also the models presented by Lee & Zlatanova [19] or Kolbe et al. [20] are based on. [12] A 3D-GIS based framework that supports BIM for topologic analysis-oriented indoor navigation is also proposed. [21] The BIM file covers geometric and semantic information and is utilized for creating the network model. They propose to separate floor elements according to their functional aspects, but they do not provide detailed information on their graph model. Yuan & Schneider proposed an indoor model that produces optimal non-circuitous routes. [22] They consider all building parts as cells and separate those into simple cells, complex cells, open cells, and connectors. Furthermore, their mapping, i.e., relationship between doors/rooms to nodes/edges, is different to other models. Doors are mapped to nodes and the rooms are mapped to edges. This approach is based on the assumption that doors, i.e., entrances of rooms, are the destination of the user and furthermore, this allows the construction of length-dependent routes. Additionally the authors describe how to connect two doors in a concave shaped room (cf. Fig. 2).
They define a direct path graph (DPG) G := (V,E) "which reflects all possible path constructions in a given indoor space scenario". [22] However, this is a coarse formal definition of a routing graph. Also, the computation of length-optimal routes comes at the Fig.2 Various directly connected access points in a concave room [22] cost of a negative impact on the runtime. The complexity of routing algorithms strongly depends on the amount of graph elements. By following their approach and trying to model a long office corridor, this results in n nodes (n is the amount of doors) and several links between all these nodes. The amount of required links (arl) can be calculated according to Eq.(1): For an exemplary corridor with 20 offices, this approach leads to 20 nodes and 190 edges. Extending this to a building with 7 levels, two elevators and one building entrance, such a graph would require 1.800 graph elements for a simple building structure, which is inacceptable for performance and storage and furthermore similar models get along with less graph elements (as will be described later).
In conclusion, it needs to be emphasized that all existing models do not discuss how to deal with obstacles or walls inside a room. The direct connection between two doors might not be navigable, due to physical constraints (cf. Fig. 3), but existing models are not able to capture this. Furthermore, existing models are not capable of considering different areas inside rooms (e.g., smoking area and check-in counter in an airport entrance hall), because rooms are modeled as single elements. Moreover, existing models assume that path segments do not have directions. This might be true for most buildings, but there are some scenarios (e.g., airport) where the consideration of one-way paths inside a building is required. Also, none of the existing approaches tries to formally define the utilized graphs. That is, existing approaches use a graph that has never been formally defined beforehand.

Fig.3 A convex shaped room with physical constraint inside 2 Relevant building components for indoor routing
Routing describes the process of leading users from a starting point to a destination point in an optimal manner (according to distinct requirements). Such routes are often obtained by applying a routing algorithm onto a graph. In this chapter, we discuss which inner building components are relevant for routing, and thus need to be integrated in an indoor routing model. Special constraints such as obstacles or one-way paths are also discussed. In general, small rooms (e.g., offices, kitchens, etc.) are modelled as described by Yuan & Schneider [22] (cf. Fig.4). We share the opinion that doors are the first targets of users, but nevertheless navigation inside rooms (as will be refined later) is also required. In contrast to previous approaches, modelling of corridors is also discussed.

Corridors
From a geometric point of view, corridors are a special type of rectangular rooms in which two opposing sides are short (i.e., just a few meters) and the other two sides are way much longer (i.e., 0 < long_side/short_side 1 ). Big corridors (i.e., all sides are several meters long), need to be rather considered as a hall than a corridor. In addition, from a semantic point of view, a corridor is often not a destination node, but just a connector node. There are two basic possibilities for modelling a corridor: [23] just one node per corridor (not applicable) or by utilizing an adjusting line in the centre of the corridor. In contrast, Yuan & Schneider [22] proposed to model a corridor in the same manner as a room (cf. Fig.4). So practically there are two different methodologies for corridors, but which one is more appropriate with respect to computation performance and accuracy. When considering a corridor with 14 doors (quite common) this results in 105 graph elements for any kind of corridor layout, when modelling a corridor in the same way as a room. In contrast for the centreline approach, the total amount of required nodes depends on the corridor layout (i.e., the exact location of doors) and the amount of required edges is always #edges = #nodes -1. One possible corridor layout is that all doors are located at one side of the corridor (cf. Fig.5 (a)) leading to #nodes = 2·|n| for n doors and to 55 graph elements for exemplary 14 doors. Another possible layout is that two doors are at every short side and the rest of the doors are at one single side (cf. Fig.5 (b)). In general this leads to #nodes = 2·|n| -2 and for the example to a total of 51 graph elements. A third possible corridor layout (depicted in Fig.5 (c)) is that the half amount of doors is on one long side and the others on the opposed side with the constraint that there is no pair of opposed doors, resulting in #nodes = 2·|n|, thus in 28 nodes for the exemplary floor. Another layout is illustrated in Fig.5 (d), whereby opposed doors are allowed. For the exemplary corridor, the route graph has 21 nodes. Generally, such a layout requires #nodes = 3/2·|n|. A last possible layout (Fig.5 (e)) has the characteristics that there is one door on every small corridor side and the remaining ones are equally distributed on both long sides, whereby pairs of opposed doors are allowed, leading to #nodes = 3/2·|n| -1 (39 graph elements for the example).
Of course there are other corridor layouts possible, but the described ones represent special cases. Layout a (cf. Fig.5 (a)) and layout e (cf. Fig.5 (e)) represent the upper and lower borders for the complexity and the amount of required graph elements (arge) can be approximated as follows: Additionally, Table 1 provides an overview for different door amounts. It depicts, that the centreline approach might need less elements for more than four doors per corridor, but it definitely is advantageous for more than six doors in the corridor (which can be found very often in public or commercial buildings). Trying to reduce the complexity of the route graph, the centreline approach is preferable. By adding geometric information to the model (as will be described later), it is possible to analyze travel distances and provide nearly length-optimal routes. However, distance calculations also depend on the model itself, i.e., investigations on the overhead (additional travel distance) are required. A 50 m long and 2 m wide floor with 4 doors (depicted in Fig.6 (a)) serves as an example. The iNav approach [22] proposes an edge between every possible pair of nodes ( Fig.6  (b)) and the centreline approach adds additional nodes in the middle of the corridor (Fig.6 (c)). Table 2 shows the different travel distances and compares the two approaches. Thereby it becomes obvious that, the more distant two doors are, the lesser is the overhead of travel distance. Therefore, e.g., for d 3 → d 4 the overhead is 25.7%, whereas it is 2.0% for d 1 → d 3 . Furthermore, there is no additional overhead for opposed doors (Table 2). In general, the resulting overhead can be approximated by Ω (0) ≤ overhead ≤ Ο(b) whereby the parameter b is the width of the corridor. Concluding this discussion, it becomes apparent that the centreline approach is advantageous because it reduces the amount of graph elements, and thus is likely to increase performance. The additional travel distance is rather fractional and has no serious impact on the route. Furthermore, the centreline model is more realistic because a user is likely to take a step in the middle of the corridor and then walk along it, rather than directly walking next to the wall.

Different areas and obstacles in halls and big rooms
Previous indoor model approaches do not present any work on big rooms (i.e., halls) with complex inner shapes (e.g., solid walls in the inner room). The main problem of such rooms is that the intended route through a room cannot be taken due to this physical constraint or the next target point cannot be seen (cf. Fig.3), i.e., additional instructions are required for proper guidance. By manually adding additional nodes, it is possible to securely bypass such obstacles and computed routes will be more length-optimal (cf. Fig.7).

Fig.7 Routing graph for bypassing obstacles inside rooms
How many and where nodes need to be added, is a question of the accuracy of navigation and not related to the routing itself. The procedure is not limited to fixed, solid obstacles, and can also be applied to other obstacles affecting the route (e.g., consideration of desks or plants for navigating visually impaired). In the future it is likely that this procedure can be achieved (semi)-automatically, by utilizing intelligent space-partitioning methodologies.
Another factor not considered in previous research approaches is the consideration of special areas inside rooms. All the previous models abstract a room as a single graph element, not permitting a detailed separation of a room into different areas. For example the entrance hall of an airport is a huge room (hall) with different areas such as check-in counters or smoking areas etc., and existing solutions do not model that kind of information (i.e., routing a user from the entrance to the check-in counter is not possible). Another example is a huge exhibition hall with many different booths inside, where the previous approaches model this hall as one single graph element.

Motivated by such examples, it is advisable to have additional nodes for every point of interest and to
connect them with existing nodes. Therefore, e.g., in Fig.8 (a) the route graph for an airport entrance hall is modelled and in Fig.8 (b) the route graph of an exhibition hall is depicted. The decomposition of rooms into different areas can be further refined in a hierarchical manner (cf. Hierarchical outdoor wayfinding [24] ). In doing so, route instructions such as "From the check-in counter go to departure A and then to gate 22" can be realized.

Considering the possibility of one-way paths inside a building
In the street network, one-way roads are very common and therefore routing models are often realized as directed graphs. In contrast, most "ways" or doors in indoor-environments do not have a distinct direction (e.g., people can walk through a corridor in both directions). Existing approaches for indoor routing utilize non-directed graphs. However, they do not consider the possibility of one-way paths at all. There are few scenarios, e.g., escalators or passport checks at the airport, which require the consideration of one-way paths or doors. Since one-way paths in buildings are rare, it is proposed to realize an undi-rected graph with additional semantic information, reducing the amount of graph elements significantly.

Vertical building parts
Most buildings have several levels that are connected via stairways, elevators, etc., and it needs to be discussed how such vertical connections should be treated. Modeling an elevator is quite intuitive: all elevator doors are already included in the network model, because they are integrated when individual floors are modeled. Furthermore, there are only edges required for directly adjacent doors, i.e., door1 is connected with door2, door2 is connected with door3 etc., but there is no edge between door1 and door3. That is, an elevator connecting n levels can be modeled with n nodes and (n-1) edges (cf. Fig.9 (a)). Modeling staircases is achieved in a similar way, however it might be possible that edges are not congruent (from a bird-perspective). This is the case when stairway exits are on opposite sides of the stairway (cf. Fig.9 (b)). However, the modeling procedure is the same.
Modeling escalators is also intuitive: the start and the end of an escalator are modeled as a node inside rooms, and furthermore these nodes are connected with an edge. Since escalators cannot be strictly vertical, the edge is also not strictly vertical, but strictly horizontal edges (cf. moving walkway) are possible. Escalators are one-way and therefore additional information on the direction is required.

Formal definition of the weighted indoor routing graph
The most efficient way to find routes in a graph is applying a shortest path algorithm to the graph. Therefore, a graph for supporting shortest path algorithms has been developed.
Definition 1: A weighted indoor routing graph is a labelled graph that describes all possible path constructions in an indoor environment and furthermore contains semantic information about the different parts of the indoor environment. The WIRG is defined via the 7-tupel WIRG := (N, E, f, g, h, i, j), where N (nodes) is a set of relevant points, i.e., access points or doors or distinct areas in the indoor space, and E (edges) is a set of edges, i.e., connections between relevant points in the indoor space. Additionally, f, g, h, i and j are mathematical functions which are responsible for labelling, weight distribution, one-way definition, localization, access restrictions, and other semantic information. For providing the above mentioned functions and for making the graph adaptable to different user requirements, the sets L, TC, R, ID and SI are defined below. The set SI (semantic information) is a set of additionally available semantic information, whereby |SI|>1.
After defining different sets which are required for the model, the functions f, g, h, i and j are defined. The function f is responsible for labelling different edges in the route graph.

Definition 3:
The mathematic function f is defined as f: N → L describing a monadic, surjective and non-injective function from the set of all nodes N to the set of all labels L. That is, for each l ∈ L there is a corresponding n ∈ N, but f(n 1 )=f(n 2 ) does not automatically imply n 1 = n 2 . This function assigns a label, e.g., a room name or door name, to a node, thus adds semantic information to the model.
Next the function g, which is responsible for the weight distribution, is defined as follows.
Definition 4: The mathematic function g is defined as g: E × TC × R → ℝ + describing a non-surjective and non-injective function from the Cartesian product of the sets E, TC and R to the set ℝ + . This function assigns a non-negative weight to an edge e ∈ E and thereby considers different travelling conditions and different requirements.
The necessity of such a modular weight function can be illustrated by the following example, where e describes an edge between two stairway nodes: g(e,'healty','shortest_route')=5.2 and g(e,'elderly', 'shortest_route') = 19.9. Since stairways are easy to use for a healthy person, but are exhausting for an elderly person, the weight function g calculates different weights for this distinct edge e. That is, the function g is user-adaptive to individual user requirements and therefore also the WIRG is user-adaptive.
Furthermore, the function h is defined for considering one-way paths in indoor environments.
That is, the function h can be utilized for considering one-way ways inside a building while computing a route.
Also the function i is defined for retrieving the exact coordinates of a node. Definition 6: The mathematic function i is defined as describing a monadic, non-surjective and non-injective function from the set N to a triple of elements ℝ. The function i returns the three-dimensional coordinates (according to a distinct coordinate system) of a node. Additionally the function j is defined for adding additional semantic information, e.g., accessibility constraints, to the model. Definition 7: The mathematic function j is defined as j: N × ID → SI describing a binary non-surjective and non-injective function from the Cartesian product of the sets N and ID to the set SI. This function adds additional information from a distinct information domain i ∈ ID to a distinct n ∈ N.
For the possibility of a hierarchical structure inside the building, i.e., transition points and transition parts (e.g., corridors) are described as nodes and important parts are modelled in a more detailed perspective, it is furthermore possible to replace a single node with an additional graph, so that there are one or more WIRGs included in a WIRG. In doing so, it is possible to efficiently compute routes from room A to an area in room B.

Obtaining and navigating the WIRG
In chapter three, the building components relevant for the routing network were discussed, and in chapter four the WIRG was formally defined. Obviously, the combination of all relevant nodes equals the set N and the combination of all relevant edges between these nodes equals the set E. These sets can be (manually) obtained from 3D building models. For the functions f, g, h, i and j, the sets L, TC, R, ID and SI also need to be defined. The items of set L describe labels of distinct nodes inside the building (e.g. 'room 103') and such information can be gathered from diverse data source (e.g., 3D building models, facility management systems etc.). The items of the set TC vary from graph to graph and therefore need to be individually figured out. One example for sounding items of TC is {healthy, elderly, blind, wheelchair, crutches}. In most cases, the items of the set R are always the same, because R describes the different requirements for the route computation. That is, R can be defined as R = {shortest route, quickest route, most interesting, …}. The items of the set ID vary from graph to graph and therefore need to be individually decided upon. When creating the graph, it has to be decided what additional information is available and from which distinct information domain it comes from. Therefore, e.g., ID can be defined as ID = {accessibility, flowcapacity, …}. The items of the set SI are closely related to the different information domains described beforehand. Each element of SI represents a piece of information belonging to a distinct information domain, whereby these elements can be gathered from various data sources. Exemplary values for items belonging to SI are '08:00 am -04:00 pm' (accessibility) or '20' (flowcapacity). With these sets, the functions f, g, h, i and j can be defined, whereby a manual assignment of parameters and values needs to be performed (e.g., it has to be defined that g(e,'healty','shortest_route') = 5.2).
By combining all these sets and functions, a WIRG is constructed which can be utilized for shortest path algorithms. Furthermore, the functions f, g, h, i and j allow qualitative assertions and add additional topologic and semantic information. Such a WIRG has the characteristic that each edge between two nodes represents the most direct and most realistic path between any two connected nodes. Also, any two edges directly connected with each other share the characteristic that they are visible from each other, meaning that a user can directly reach the other node without encountering an obstacle inside the room. The length (i.e., travelling distance) of each edge can be calculated by using the Euclidean distance for three-dimensional spaces: where the triples (x 1 , y 1 , z 1 ) and (x 2 , y 2 , z 2 ) can be obtained from the function i. Thereby, the value of length is not necessarily equal to the value calculated by the function g, because the length of the edge is always the same but the weights can vary for different users (e.g., healthy vs. elderly). Route computation is performed by applying a shortest path algorithm on the WIRG. The corresponding weights of the different edges can be either calculated beforehand or on-demand. Normally a user is not interested in navigating to a distinct door, but to a distinct room or area. That is, if the room has several doors, the shortest path algorithm is performed for each potential target node (door) and the door with the smallest overall weight, i.e., the weight from the starting point to the potential target point, is determined as (implicit) target node.

Conclusion and future work
In this paper an advanced model which represents indoor environments with topologic, semantic, and metric information that allows nearly length-optimal routing in complex building structures has been presented. A description of the relevant parts of a complex indoor environment which are needed for route network construction and a discussion on how to model corridors and vertical building parts has been given. The importance of considering solid obstacles inside rooms by bypassing them has been described. Additionally, it has been discussed how to consider special areas inside rooms and how to integrate those areas into the routing graph. Based on these assumptions, a weighted indoor routing graph has been formally defined and constructed. This WIRG can then be used to calculate length-optimal routes between two points in a complex building structure. Since the WIRG offers semantic information, it is also possible to calculate different routes for different requirements (e.g., disabled persons, elderly persons), thus the proposed model is adaptable to different users and circumstances.
For future research, it is intended to improve the model. By developing a prototype for a huge complex multi-level building, the usability of the model can be demonstrated and performance tests can be conducted. Conciliated with this goal, it is necessary and planned to analyze how the semantic information provided by WIRG can be utilized for a clear and understandable description of the routes through the building.


Optimal Joint Multiple Resource Allocation Method for Cloud Computing Environments

Cloud computing is a model for enabling convenient, on-demand network access to a shared pool of configurable computing resources. To provide cloud computing services economically, it is important to optimize resource allocation under the assumption that the required resource can be taken from a shared resource pool. In addition, to be able to provide processing ability and storage capacity, it is necessary to allocate bandwidth to access them at the same time. This paper proposes an optimal resource allocation method for cloud computing environments. First, this paper develops a resource allocation model of cloud computing environments, assuming both processing ability and bandwidth are allocated simultaneously to each service request and rented out on an hourly basis. The allocated resources are dedicated to each service request. Next, this paper proposes an optimal joint multiple resource allocation method, based on the above resource allocation model. It is demonstrated by simulation evaluation that the proposed method can reduce the request loss probability and as a result, reduce the total resource required, compared with the conventional allocation method. Then, this paper defines basic principles and a measure for achieving fair resource allocation among multiple users in a cloud computing environment, and proposes a fair joint multiple resource allocation method. It is demonstrated by simulation evaluations that the proposed method enables the fair resource allocation among multiple users without a large decline in resource efficiency. Keywords: Cloud computing, joint multiple resource allocation, fairness

Introduction
Cloud computing services are rapidly gaining in popularity. They allow the user to rent, only at the time when needed, only a desired amount of computing resources (processing ability and storage capacity) out of a huge mass of distributed computing resources without worrying about the locations or internal structures of these resources [1]- [4]. The popularity of cloud computing owes to the increase in the network speed, and to the fact that virtualization and grid computing technologies have become commercially available. It is anticipated that enterprises will accelerate their migration from building and owning their own systems to renting cloud computing services because cloud computing services are easy to use, and can reduce both business costs and environmental loads.
The National Institute of Standards and Technology (NIST) identified four essential characteristics of cloud computing: on-demand self-service, broad network access, resource pooling, rapid elasticity and measured service [4]. For example, Amazon Elastic Compute Cloud (EC2) [2] is an example of HaaS (Hardware as a Service), which is a form of cloud computing. This could be a virtual machine rental service (similar to a conventional 'server rental' service).
Cloud computing services enable the user to use the required computing resources for the required period, thereby enabling the user to build a flexible information system economically. In addition, there are cases where processing ability and storage capacity are provided in combination with a broadband path in the form of what is called an ICT platform service (or converged service).
As cloud computing services rapidly expand their customer base, it has become important to provide them economically. To do so, it is essential to optimize resource allocation under the assumption that the required amount of resource can be taken from a common resource pool and rented out to the user on an hourly basis. In addition, to be able to provide processing ability and storage capacity, it is necessary to reserve simultaneously a network bandwidth to access them. Therefore, it is necessary to allocate multiple types of resources (such as processing ability, bandwidth, and storage capacity) simultaneously in a coordinated manner instead of allocating each type of resource independently. The amount of resource required and the period in which it is used are not fixed. They can vary greatly from user to user and from service to service. This paper proposes an optimal resource allocation method for cloud computing environments. For the preliminary evaluation, this paper assumes the use of two types of resources: processing ability and bandwidth. In general, services can be classified into two categories: a non-delay system (loss system) and a waiting system. A non-delay system allocates a spare resource immediately to the user upon the arrival of the request, and rejects the request if there is no spare capacity. A waiting system allocates a spare capacity to users in the sequence in which their requests have arrived, instead of allocating resources immediately upon the arrival of a request. This paper assumes a service that runs as non-delay. This paper also assumes static resource allocation, which is the most basic form of resource allocation, although dynamic allocation, which uses process migration and bandwidth consolidation, can increase the utilization of resources.
Section 2 develops a resource allocation model for cloud computing environments, assuming both processing ability and bandwidth are allocated simultaneously to each service request and rented out on an hourly basis. The allocated resources are dedicated to each service request. Section 3 presents an optimal joint multiple resource allocation method, based on the resource allocation model in Section 2. Section 4 defines basic principles and a measure for achieving fair resource allocation among multiple users in a cloud computing environment, and proposes a fair joint multiple resource allocation method. Section 5 explains the related work. Finally, Section 6 presents the conclusions. This paper is the extension of previous studies that were focused on an all-IP network [12], [13].

Resource allocation model for cloud computing environments
As mentioned in Section 1, the resource allocation in a cloud computing environment can be modeled as allocating the required amount of multiple types of resource simultaneously from a common resource pool for a certain period of time for each request. The allocated resources are dedicated (not shared) to each request. For the preliminary evaluation, this paper assumes two types of resource: processing ability and bandwidth.
The required amount of resource and the period of time in which it is used are not fixed. They can vary greatly from user to user and from service to service. For example, file transfer, video delivery, and videoconferencing services require a large amount of bandwidth but not so much processing ability. In contrast, an accounting service requires a large amount of processing ability but not so much bandwidth. It is assumed that the hardware resources for cloud computing services are not installed at a single center, but in multiple geographically distributed centers, as shown in Figure 1, in order to facilitate addition of resources, to implement load balancing and to ensure high reliability. Each center has servers (including virtual servers) that provide processing ability, and bandwidths that provide access to these servers. When a new request is generated, one center from among k centers is selected according to the resource allocation algorithm. The maximum size of processing ability and bandwidth at center j (j=1,2,..,k) is assumed to be C maxj and N maxj respectively. Figure 2 illustrates the concept of resource allocation that takes the resource usage period into consideration. When a service request arrives, the optimal center is selected from multiple centers, and both the processing ability and bandwidth available in the selected center are allocated for a certain period of time. The processing ability and bandwidth of only this single center are allocated. If no center has an adequate amount of spare resources (both processing ability and bandwidth), the request is rejected. The resources allocated are released after the usage period has elapsed.

Conditions
This section assumes non-delay system and static resource allocation, as discussed in Section 1. The objective of the allocation is to maximize the number of requests to which both processing ability and bandwidth are allocated well.

Impact of joint multiple resource allocation
As the size of required processing ability does not normally have a fixed relationship with that of required bandwidth, the optimal resource allocation can not be achieved if only a single resource type is considered in the selection of a center. Case 1 in Figure 3 illustrates an example of resource allocation in the case where only processing ability is considered. Case 1 tries to select the center according to Best-Fit approach, i.e. the center with the less available amount of processing ability is selected. It is clear that 'deadlock state', in which it is not possible to support a request that needs both types of resource even though spare resources of both types are available in the total sysytem, occurred in case 1 and an additional request ⑤ is rejected. This is because that case 1 does not consider bandwidth in the selection of a center and it is not an optimal allocation for bandwidth. In contrast, case 2 in Figure 3 illustrates an example of resource allocation in the case where both processing ability and bandwidth are considered in the selection of a center. The same request generation pattern as case 1 is assumed. It is clear that the deadlock state did not occur in case 2 and an additional request ⑤ is accepted.
Therefore, it is necessary to consider both processing ability and bandwidth in the selection of a center, and to study a new method for joint multiple resource allocation.

Optimal joint multiple resource allocation method
In general, it is difficult to consider multiple types of resource at the same time. It is proposed to identify one single resource type which has the largest impact on the resource allocation. We propose a new resource allocation method (Method II) which considers only 'identified resource' in the selection of a center. Method II adopts Best-Fit approach and aims to reserve as much as possible for future requests that may require a larger size of processing Processing ability Bandwidth Bandwidth ability or bandwidth, and to reduce the possibility that the deadlock situation shown in Figure 3 will occur. As for comparison, Round Robin method (Method I) in which the center is selected in turn in the pre-defined order, is also considered here. This is one of the conventional methods, which does not consider the situation of both processing ability and bandwidth in the resource allocation.

Resource allocation by Method II
The resource type that requires the largest proportionate size of resource, comparing the size of required resource with the maximum resource size for each resource type, is first selected as 'identified resource'. Then the center with the least available amount of the identified resource from among k centers is selected. In this case, the units of processing ability and bandwidth are different, being measured in percentage of CPU power and b/s (bits per second) respectively. It is proposed to compare the size of the different resources as in the following example. Suppose that the maximum amount of bandwidth in a center is 100Mb/s. A request for 20% of CPU power and 30Mb/s requires 20% of processing ability and 30% of bandwidth respectively. As the proportion of required bandwidth is larger than that of required processing ability, bandwidth will be the identified resource in this case.
When a service request is generated, the following resource allocation algorithm is carried out: i) Selection of identified resource if X C >X N then processing ability is the identified resource. else bandwidth is the identified resource. where X C ={the size of required processing ability }/X C0 X C0 = Min {the maximum amount of processing ability in a center} X N = {the size of required bandwidth}/X N0 X N0 = Min {the maximum amount of bandwidth in a center} For example, if there are two centers and the maximum amount of processing ability of each center is 100 and 50 respectively, X C0 will be 50. ii) Selection of the center The center which satisfies the following three conditions will be selected: -Min {the available size of the identified resource in the center} -Available processing ability in the center is equal to or larger than the required processing ability.
-Available bandwidth in the center is equal to or larger than the required bandwidth.
If there are two or more centers which satisfy the above conditions, one center will be selected at random. Note that the request will be rejected if there are no centers that satisfy the above conditions. iii) Allocation of resource Both required processing ability and bandwidth are allocated simultaneously in the selected center. The allocated resources are dedicated (not shared) to the request. iv) Release of resource When the service time has expired, both allocated processing ability and bandwidth will be released simultaneously.

Resource allocation by Method I
When a service request is generated, the following resource allocation algorithm is carried out: i) Selection of the center First, one center from among k centers is selected in a round-robin fashion. If there are not enough resources available for the selected center, the next center in the pre-defined order will be selected. For each request, the center which is next in the pre-defined order will be checked first, regardless of which center was selected by the previous request. Note that the request will be rejected if none of the centers have enough resources available. ii) Allocation of resource Both required processing ability and bandwidth are allocated simultaneously in the selected center. The allocated resources are dedicated (not shared) to the request. iii) Release of resource When the service time has expired, both allocated processing ability and bandwidth will be released simultaneously.

Simulation conditions
1) The evaluation is performed by a computer simulation using the C language. The simulation model is based on the case where k is 2 in Figure 1. That is, there are two centers (center 1 and center 2). The maximum size of processing ability of center 1 and center 2 is assumed to be C max1 and C max2 respectively. The maximum size of bandwidth of center 1 and center 2 is assumed to be N max1 and N max2 respectively. When a service request is generated, center 1 or center 2 is selected according to the resource allocation algorithms proposed in Section 3.3.
2) The size of required processing ability and that of bandwidth follow a Gaussian distribution, and average values are given by C and N respectively.  3) The generation interval of requests follows an exponential distribution (average interval of request arrival is given by q). The service time H, which is the total time from a generation of the request to a completion of the service, is assumed to be constant. Each request occupies the allocated processing ability and bandwidth until its service time H passes. 4) It is supposed here that the following m requests will be generated repeatedly. The value of C and N of the first generated request are a 1 and b 1 respectively. The value of C and N of the second generated request are a 2 and b 2 respectively. The value of C and N of the m-th generated request are a m and b m respectively. We denote this request generation pattern like {C=a 1 ,N=b 1 ;C=a 2 ,N=b 2 ;…; C=a m ,N=b m } in this paper.

Simulation results and analyses
Figures 4, 5 and 6 illustrate the result of simulations which compare Method II with Method I. Figure 4(1) compares the request loss probability, which is the probability that either processing ability or bandwidth is not available, in the case where the value of C is the same as that of N. Figure 4(2) compares the request loss probability in the case where the sizes of processing ability and bandwidth (C and N) rise and fall in anti-phase, i.e., a large processing ability is followed by a large bandwidth. Figure 5 evaluates the impact of ratio of maximum resource size of each center on the request loss probability, assuming the total size of processing ability (C max1 +C max2 ) and that of bandwidth (N max1 +N max2 ) are constant. Figure 6 evaluates the impact of the number of centers on the request loss probability with the same simulation conditions as those of Figure 4(2).
The following points are clear from these Figures: (1) Method II can reduce the request loss probability and as a result, reduce the total amount of resource compared with Method I, in the case where the sizes of processing ability and bandwidth rise and fall in anti-phase. This is also true even if the number of centers increases except for the case where the number of centers odd. This is because the deadlock state as in Figure 3 occurs readily in Method I when the number of centers is odd and the sizes of processing ability and bandwidth rise and fall in anti-phase. It is noted that the request loss probability will be small when the number of centers increases because the number of centers in the state that can be processed increases relatively for the same amount of service demands.
(2) To allocate resources to one specific center as much as possible is better rather than to distribute resource to multiple centers if the total amount of resource is constant. For example, the request loss probability when C max1 and N max1 are 40 (the total resource is allocated only to center 1) is small compared with the request loss probability when C max1 and N max1 are 20 in Figure 5

Fair joint multiple resource allocation
There is a possibility that unfair allocation of resources, in which most of resources are occupied by the specific user, occurs with Method II. Therefore, this section proposes to enhance Method II to enable the fair resource allocation among users.

Basic principles for achieving fairness in joint multiple resource allocation
The following four basic principles are proposed to achieve 'fairness' among users in the joint multiple resource allocation: <Principle 1> Since this paper assumes the non-delay resource allocation, it aims to achieve fairness without queuing in principle. However, it allows a delayed allocation of resources to serve some requests if it is necessary to achieve fairness. <Principle 2> Fairness should be pursued while taking multiple types of resource into consideration. There are many papers that discuss algorithms for achieving fairness for cases where a joint resource allocation is not considered [5]- [9]. These algorithms cannot be applied to cases where multiple types of resource are allocated simultaneously, because an allocation that is fair for one specific resource type may be unfair when considering other resource types. This is caused by the fact that the size of the requested processing ability and that of the requested bandwidth are not generally uniform and both processing ability and bandwidth should be allocated simultaneously. <Principle 3> Equalizing the total amount of both processing ability and bandwidth for all users would not achieve fairness. A possible solution to satisfy principle 2 may provide an equal amount of both processing ability and bandwidth to each user. However, this solution has a problem, as illustrated in Figure 7. It is supposed in Figure 7 that there are two users and half the amount of processing ability and bandwidth combined is a maximum allowable size to each user. If resources are allocated to one user like pattern 2, it will take up almost all bandwidth although the total amount of allocated resources to the user does not exceed the maximum allowable size. In this case, it is impossible to meet requests from the other user that may have pattern 1 or pattern 2 (both patterns require a large amount of bandwidth). <Principle 4> It is not unfair when there are no request rejections occurred for all users, even if there is an imbalance in the amount of allocated resources to each user.

Definition of 'fairness'
This paper defines that the fairness can be achieved by allocating resources to each user in every time block, in proportion to the expected amount of resources requested by each user. The total amount of resources allocated to each resource type in a time block of length L is calculated, and then the resource type for which the total amount of requested resource is largest portion of the maximum resource of that type is selected as 'key resource'. The fairness will be judged with the total amount of allocated key resource in a time block. This idea is very similar to the idea of Method II in Section 3. Key resource could change over time and could be different for each user. Note that L is assumed to be longer than resource holding time H.

Measure of fair allocation (a) Conditions
1) The number of users: G (user 1～user G) 2) The ratio of expected amount of key resources requested by user g (g=1～G) to the least expected amount of key resources requested by a users is 1/r g . 3) The user which has the largest value of V j (g) is called as 'user g 1 ' in j-th time block, where V j (g) is given by {Total amount of key resource allocated to user g in i-th time block}*r g . r g is multiplied to normalize the amount of allocated resource, as in Figure 8. The resource allocation will be considered as fair when the normalized amount of allocated key resource is the same among users.
4) The difference between total amount of key resources allocated to user g 1 and those allocated to user g in j-th time block is set to N j (g) and is called as 'Imbalance on allocated resources of user g (g=2～G)', as shown in Figure 9. N j (g) is given by V j (g 1 )-V j (g) and N j (g 1 ) be set to 0. 5) If no request of user g is rejected in j-th time block, it is considered that the resource allocation is not unfair for user g, and N j (g) is set to 0, even if there are some differences in the amount of allocated key resource.

(b) Measure of fair allocation
It is proposed to check the value F given by Equation (1) and judge that the smaller the value of F is, the fairer the resource allocation is: where s is the total number of time blocks. Figure 10 illustrates the meaning of formula F. If the value of F is the same for multiple users, it is proposed to judge that the smaller the change of the size of N j (g) is, the fairer the resource allocation is. The change of the size of N j (g), F 1 , can be estimated with Equation (2): where N ave (g) is the average of N j (g) in all time blocks.

Fair joint multiple resource allocation method
This section proposes a new joint multiple resource allocation method which is the extension of Method II and can achieve fair resource allocation. As this paper assumes the non-delay resource allocation, it is difficult to take any action in advance, avoiding any imbalance on the total amount of key resources allocated to different users. Therefore, it is proposed that the imbalance in j-th time block will be filling up in (j+1)-th time block, by applying the delayed resource allocation only to the user that suffered imbalance in j-th time block, on condition that the service shall be completed within a maximum permissible service completion time T. If there are allocated resources for one user not enough resources available when a user request occurs, the resource allocation will be delayed until the required size of resources are available, instead of rejecting the request. The delayed resource allocation will be achieved until the total amount of key resource assigned for delayed requests exceeds N j (g) /r g in (j+1)-th time block. It is impossible to decide which resource type is key resource before the end of (j+1)-th time block. Therefore, both N j-c (g), imbalance of processing ability, and N j-n (g), imbalance of bandwidth, are calculated from the beginning of each time block and the request will be rejected when N j-c (g) / r g or N j-n (g) / r g exceeds N j (g) / r g .
Details of algorithm to fill up the imbalance in the next time block are as follows: 1) If requests for user g to which the amount of allocated key resource is small in j-th time block were rejected for a lack of resource in (j+1)-th time block, resources up to N j (g) / r g will be filled up in (j+1)-th time block, regardless of whether requests for the user to which the amount of allocated key resource is large in j-th time block are rejected or not. 2) If no requests for user g to which the amount of allocated key resource is small are rejected for a lack of resource in j-th time block, it is considered that enough resource has been allocated to user g and no action is made to fill up the imbalance in (j+1)-th time block (N j (g) is set to 0), even if requests for the user to which the amount of allocated key resource is large in j-th time block are rejected.
3) When the delayed resource allocation is applied to fill up the imbalance, it is necessary to determine the time when to start the service. For this purpose, it is proposed to manage the available resource management diagram as illustrated in Figure 11. This diagram is managed per user. Figure 12 illustrates an example of fill up the imbalance when G is three. We call the method which follows the above algorithm in unfair case but follows Method II in the fair case, as 'Method III' in this paper.

Conditions
All except for G=2 are same as the conditions in section 4.3.1. Figures 13 and 14 show simulation results. The request generating pattern of user 1 and user 2 in those figures is indicated as {C=x, N=x} and {C=z*x, N=z*x}, respectively. {C=x, N=x} means that a request with C=x and N=x will be occurred repeatedly. z is the ratio of the size of user 2 request as opposed to the size of user 1 request. The average resource utilization in Figure 13 is the average usage of both processing ability and bandwidth. The following points are clear from these figures: 1) Method III can decrease the value of F greatly (that is, Method III enables fair resource allocation), compared with Method II which does not consider fair allocation. This is also true even if the number of centers increases.

Simulation results and analyses
In Figure 13, the value of F for Method II becomes large first as z becomes large, because the imbalance of the amount of allocated resource becomes large. However, where z exceeded 3.0, the value of F for Method II becomes small as z becomes large, because the size of required resource for user 2 requests is too large and it will be difficult to get enough resources available. On the other hand, the value of F for Method III increases a few as z becomes large. 2) Method III enables fair resource allocation in proportion to the expected amount of resources requested by each user, as in Figure 14.
3) In general, the resource efficiency will fail if we pursue fairness. However, Method III can attain the almost same resource efficiency as Method II, as in Figure 13.

Related Work
The proposed resource allocation model in Sections 2, 3 and 4 is similar to the online bin packing problem [5]. The bin packing problem is a problem of determining how items can be put in multiple bins most efficiently. In an online problem, the information about items is not known in advance. The proposed resource allocation model differs from the conventional bin packing problem in the following points: 1) It deals with "composite bins", in which two bins (a processing ability bin and a bandwidth bin) are consolidated.
2) Each item has two sizes, and they are simultaneously packed in composite bins.
3) Packed items are removed after a certain period has elapsed. This period differs from item to item. The conventional bin packing problem is an NP-complete problem, for which it is difficult to derive a general solution. Among the conventionally proposed algorithms for the online pin packing problem [5] Best-Fit (select bins with a smaller spare space) is considered to be more effective than Next-Fit, Worst-Fit, or First-Fit. We proposed an algorithm that extends the consolidated bin packing problem assuming Best-Fit.
Moreover, server selection methods that take both the  (2) Method II (4) Method III (4) Method II (3) Method III (3) Method II (2) Number of Centers Ratio z server (processing ability) and the network (bandwidth) into consideration have been evaluated, as in Reference [11]. However, these methods assumed that each client requests a job processing and both servers and network are shared with multiple jobs from many clients in which servers and networks are modeled as queuing systems, and do not cover the model in which both processing ability and bandwidth, dedicated to each request, are rented out simultaneously on a hourly basis.

Conclusions
This paper has evaluated the resource allocation method for cloud computing environments.
This paper first has developed a resource allocation model for cloud computing environments and has proposed the optimal joint multiple resource allocation method, Method II, assuming that both processing ability and bandwidth are allocated simultaneously for each request and rented out on an hourly basis. The allocated resources are dedicated to each service request. It has been demonstrated by simulation evaluation that Method II could reduce the request loss probability and as a result, reduce the total amount of resource, compared with the conventional allocation method.
Then, this paper has proposed basic principles and a measure for achieving fair resource allocation among multiple users in a cloud computing environment, and has proposed a fair joint multiple resource allocation method, Method III, which tries to allocate resources in proportion to the expected amount of resources requested by each user. It has been demonstrated by simulation evaluations that Method III enables the fair resource allocation among multiple users without a large decline in resource efficiency, compared with the conventional method which does not consider the fair allocation.