1 Introduction
Grid (Foster & Kesselman, Reference Foster and Kesselman2004) is a large-scale virtual computing environment where geographically distributed resources collaboratively provide a computing infrastructure. It is used for solving computing-intensive and data-intensive problems that are not practically feasible to run in traditional distributed computing environments. The early Grid was implemented mostly with physically fixed resources with high performance, and the resources are connected through reliable networks with high speed. Emerging Grids (Kurdi et al., Reference Kurdi, Li and Al-Raweshidy2008) are extending the scope of resources to mobile devices and sensors that are loosely connected through wireless networks, which is referred to as mobile Grid. Mobile Grid incorporates mobile devices by supporting new functionalities such as mobility.
A mobile device in mobile Grid can act as both a consumer (Banavar et al., Reference Banavar, Beck, Gluzberg, Munson, Sussman and Zukowski2000; Migliardi et al., Reference Migliardi, Maheswaran, Maniymaran, Card and Azzedin2002) and a provider (Phan et al., Reference Phan, Huang and Dulan2002; Litke et al., Reference Litke, Skoutas and Varvarigou2004). As a consumer, it requests for service to a Grid, and as a provider it actively participates in processing service requests. Compared with physically fixed Grid resources such as desktop computers, mobile devices tend to provide a relatively inferior performance in terms of CPU capability, amount of main memory, and storage capacity. They also have a limited battery life and are commonly connected to wireless network that is not as reliable as wired network. Owing to the availability and reliability issues, it is not straightforward to use mobile devices as Grid resources and there are skepticisms on using mobile devices as service providers. Nevertheless, mobile devices offer various capabilities such as location awareness that are not normally incorporated in fixed Grid resources. Nowadays, the number of mobile device users is exploding and mobile devices are rolled out equipped with processor(s) and a large amount of memory with advanced technology at an ever-faster pace. Considering the enormous population with their capability, mobile devices have an immense potential to serve as resource providers in mobile Grid environment.
Mobile Grid exhibits different challenges from traditional Grid mainly owing to the users’ mobility and load-balancing. For example, the movement of users could incur a failure of the network link while executing a job that may require data communication. Then, the job should wait until the connection is re-established. This leads to the performance degradation in job execution. Without a proper load-balancing, all jobs may be allocated only to the stable resources such as physically fixed Grid components. It results in discriminating mobile devices with less performance but with the enormous number of population. It incurs not only the decrease in the resource utilization, but also the performance degradation owing to the improper load-balancing. Therefore, it is imperative to provide a job scheduling considering the users’ mobility and load-balancing under the loosely connected network.
A mobile agent is a software program that migrates from one node to another while performing given tasks on behalf of users (White, Reference White1996; OMG, 1997; Fuggetta et al., Reference Fuggetta, Picco and Vigna1998; Maes et al., Reference Maes, Guttman and Moukas1999; Wong et al., Reference Wong, Paciorek and Moore1999). According to the research (White, Reference White1996; Fuggetta et al., Reference Fuggetta, Picco and Vigna1998; Lange & Oshima, Reference Lange and Oshima1998; Maes et al., Reference Maes, Guttman and Moukas1999; Wong et al., Reference Wong, Paciorek and Moore1999; Cardoso & Kon, Reference Cardoso and Kon2002; Spyrou et al., Reference Spyrou, Samaras, Pitoura and Evripidou2004), the mobile agent provides the following benefits: (1) A mobile agent can reduce network load and latency. (2) It can be used in an environment where the network disconnection occurs frequently or intermittently. (3) It enables dynamic service customization and software deployment. (4) It enables the dynamic adaptation to heterogeneous environment as well as the environmental changes. Owing to these benefits, the mobile agent technology has been widely used in various areas including distributed computing, mobile computing, Grid computing, and ubiquitous computing. Its applications encompass distributed information retrieval, electronic commerce, distributed network management, and parallel computing (Fuggetta et al., Reference Fuggetta, Picco and Vigna1998; Lange & Oshima, Reference Lange and Oshima1998; Maes et al., Reference Maes, Guttman and Moukas1999; Wong et al., Reference Wong, Paciorek and Moore1999; Puliafito et al., Reference Puliafito, Tomarchio and Vita2000). Recently, mobile agents are largely adopted in resource monitoring and management as well as scheduling mechanism in Grid computing (Fukuda et al., Reference Fukuda, Tanaka, Suzuki, Bic and Kobayashi2003), resource discovery in peer-to-peer computing (Dunne, Reference Dunne2001), and service discovery and composition and context awareness in ubiquitous computing environments (Bagci et al., Reference Bagci, Petzold, Trumler and Ungerer2003; Stevenson et al., Reference Stevenson, Nixon and Ferguson2003).
In traditional Grid, a message is delivered to a receiver in synchronous or asynchronous manner. Mobile Grid suffers from intermittent disconnections as a result of users’ movements. This characteristic makes it inefficient and troublesome to adopt the synchronous message delivery. It is because a sender could be blocked in a synchronous delivery when the network disruption occurs. In addition, it is not practical to use the traditional Grid middleware in mobile Grid because it is not lightweight enough to be installed on mobile devices. There are two key functionalities for a mobile agent to support: location management and asynchronous message delivery. The location management keeps trace of the location of mobile devices that can be moved physically across network domains or logically among mobile devices. The asynchronous message delivery guarantees the delivery of a message to a destination by implementing a queue that temporarily stores a message upon submission. These location management and asynchrony in mobile agent system are appropriate and attractive in supporting mobility in mobile Grid.
This paper presents a mobile Grid system architecture based on mobile agents and proposes a novel balanced scheduling algorithm taking into account the mobility, availability, and adaptability of mobile devices in mobile Grid. We analyzed users’ mobility patterns to quantitatively measure and classify the tolerance of network links, and defined availability metrics. We also propose a load-balancing technique by classifying mobile devices into nine groups depending on availability and the job type (computing intensive and communication intensive). In addition, our algorithm uses adaptability based on the multi-level feedback queue to dynamically handle the job type change.
The rest of the paper is organized as follows. Section 2 presents related work on scheduling algorithms in mobile Grid. Section 3 discusses challenges introduced by mobility in mobile Grid. Section 4 demonstrates the mobile Grid system architecture and a key concept of our architecture. Section 5 illustrates our balanced scheduling algorithm in mobile Grid. Section 6 details the implementation of the mobile Grid system. Experimental results are presented in Section 7. Finally, we conclude our paper with future works in Section 8.
2 Related work
2.1 Mobile agent-based Grid
A mobile agent system is a platform that can create, interpret, execute, transfer, and terminate mobile agents (White, Reference White1996; OMG, 1997; Lange & Oshima, Reference Lange and Oshima1998). There are distinguishing mobile agent systems: Telescript (White, Reference White1996), Aglets (Lange & Oshima, Reference Lange and Oshima1998), Voyager (Glass, Reference Glass1999), Concordia (Wong et al., Reference Wong, Paciorek, Walsh, DiCelie, Young and Peet1997), Mole (Baumann et al., Reference Baumann, Hohl, Rothermel and Straer1998), JAMES (Silva et al., Reference Silva, Simões, Soares, Martins, Batista, Renato, Almeida and Stohr1999), Ajanta (Karnik & Tripathi, Reference Karnik and Tripathi1998), Ara (Peine, Reference Peine2002), D’Agent (Gray et al., Reference Gray, Cybenko, Kotz, Peterson and Rus2002), MobileSpaces (Satoh, Reference Satoh2000), MAP (Puliafito et al., Reference Puliafito, Tomarchio and Vita2000), MESSENGERS (Fukuda et al., Reference Fukuda, Bic, Dillencourt and Merchant2001), TACOMA (Johansen et al., Reference Johansen, Lauvset, Renesse, Schneider, Sudmann and Jacobsen2002), ODDUGI (Choi et al., Reference Choi, Choo, Baik, Kim and Byun2009), and so on. Java is mainly selected as a language to implement mobile agent systems (Wong et al., Reference Wong, Paciorek, Walsh, DiCelie, Young and Peet1997; Baumann et al., Reference Baumann, Hohl, Rothermel and Straer1998; Karnik & Tripathi, Reference Karnik and Tripathi1998; Lange & Oshima, Reference Lange and Oshima1998; Glass, Reference Glass1999; Silva et al., Reference Silva, Simões, Soares, Martins, Batista, Renato, Almeida and Stohr1999; Satoh, Reference Satoh2000; Gray et al., Reference Gray, Cybenko, Kotz, Peterson and Rus2002; Choi et al., Reference Choi, Choo, Baik, Kim and Byun2009). Most of the mobile agent systems are implemented in Java except Telescript (telescript), Ara (C, C++, Tcl), MESSENGERS (M0), D’Agent (Java, Tcl, Scheme), and TACOMA (C).
The Open Grid Services Architecture (OGSA) (Foster et al., Reference Foster, Kesselman, Nick and Tuecke2002) describes architecture for a service-oriented Grid environment. OGSA is based on Web service technologies such as Web Services Resource Framework (WSRF) (Czajkowski et al., Reference Czajkowski, Ferguson, Foster, Frey, Graham, Maguire, Snelling and Tuecke2004). WSRF is a set of specifications that integrates and accesses stateful resources using Web services for complementing shortcomings of stateless Web services. WSRF consists of WS-ResourceProperties, WS-ResourceLifetime, WS-ServiceGroup, WS-BaseFaults for representing, accessing, managing, and grouping WS-Resource. WSRF also includes WS-Notification for notifying change in resource status. Currently, there is a representative middleware called Globus (Foster, Reference Foster2006) for WSRF.
There are different requirements for Grid and the agent system. Grid relies more on flexibility and agility in job execution. The agent system relies more on reliability and scalability. Thus, the convergence of Grid and the agent system complements the shortcomings of each other and provides benefits. There are several studies integrating Grid and the agent system. Foster et al. (Reference Foster, Jennings and Kesselman2004) discussed a convergence of Grid and the agent system. Zahreddine and Mahmoud (Reference Zahreddine and Mahmoud2005) proposed the agent-based composition of Web services on behalf of the mobile user. However, they utilized the mobile agent only for composing external Web services rather than for using mobile devices as resource providers. Bellavista et al. (Reference Bellavista, Corradi and Monti2005) developed an infrastructure of integrating the mobile agent and the Web service technologies to provide interoperability. In this system, a mobile agent invokes external Web services and the Web services are allowed to access mobile agents via proxy with WS2MA and MA2WS interfaces. Athanaileas et al. (Reference Athanaileas, Tselikas, Tsoulos and Kaklamani2007) presented a Grid services-based agent platform that all platform components are implemented as Grid services conforming to WSRF. This platform provides mobility in Grid services to facilitate the migration of Grid services. However, it is not lightweight enough to be installed on mobile devices.
2.2 Scheduling in mobile Grid
There are numerous studies on scheduling in mobile Grid, focusing on power efficiency, communication availability, and job replication. For the power efficiency, Huang et al. proposed a proxy-based hierarchical scheduling model that takes into account mobility and power management in wireless environment (Huang et al., Reference Huang, Zhu, Wu and Xia2006). In this model, the scheduler is comprised of two levels (top level and proxy level) to utilize the energy of wireless node and guarantee QoS at the same time.
There are several studies on the communication availability. Park et al. proposed a scheduling algorithm with the processor and the communication availabilities (Park et al., Reference Park, Ko and Kim2003). This algorithm confines the communication scope and is useable even when the network link is broken owing to mobility. However, this algorithm has a shortcoming in that it is applicable to a specific job type with no communication during job execution. Farooq et al. devised a generic mobility model to predict the time duration during which a user (thus, and a device) would remain in a specific domain (Farooq & Khalil, Reference Farooq and Khalil2006). It is based on the history of user’s behavior in the past. This model computes the average mobility and the time in range based on the user range parameter. Based on the computations, it figures out how many jobs a mobile device can execute. Ghosh et al. proposed a scheduling algorithm that applies a pricing strategy to the job allocation problem and optimizes a total system cost (Ghosh et al., Reference Ghosh, Roy and Das2007). As these algorithms do not consider the processor availability and the load-balancing, they have limitations on the scheduling optimization. Lee et al. proposed a balanced scheduling in mobile Grid (Lee et al., Reference Lee, Song, Gil, Chung, Suh and Yu2009), which takes into account the load-balancing and mobility patterns of users. However, they did not present a concrete architecture and the adaptability of the scheduling algorithm.
In the job replication aspect, Litke et al. proposed a method that estimates a number of job replications using the Weibull reliability function and maximizes the resource utilization for workloads caused by replication with the knapsack formulation (Litke et al., Reference Litke, Skoutas, Tserpes and Varvarigou2007).
3 Problem statement
As opposed to the traditional Grid, mobile Grid has a distinctive characteristic in that Grid resources are changing their physical positions according to users’ movement from one zone to another. When a mobile device crosses domains in wireless network, mobile Grid should support the terminal mobility (also referred to as physical mobility) to maintain a session. Without the terminal mobility, once a device loses its connection to the previous network domain, the communication with the correspondence node is discontinued because a new IP address is allocated for the device in a new domain. Even when a mobile user opens a session on one device and moves to another device, mobile Grid should support both user mobility and session mobility for the continuation of the service, which is referred to as logical mobility.
The mobile computing at present guarantees the terminal mobility and the session mobility through MIP (Perkins & Johnson, Reference Perkins and Johnson1996) and SIP (Wedlund & Schulzrinne, Reference Wedlund and Schulzrinne1999). It is implemented either in the network layer or in its upper layer. When a resource with MIP and SIP support changes the access point under the stable network condition, the resource and job management techniques in traditional Grid are directly applicable to the mobile Grid. However, resources in mobile Grid may not participate in a Grid and/or they may be separated from the Grid, depending primarily on the network health. They may not support MIP and SIP either. Therefore, the traditional techniques in the resource and job management are not pertinent to the mobile Grid environment. Especially, mobile Grid requires the incorporation of the application-level location management and the fault tolerance feature withstanding unstable network links, to meet the performance, reliability, and stability requirements.
The availability and reliability of a system is greatly influenced by mobility. The availability is defined as whether a user can use the system immediately at a specific time. On the other hand, the reliability is whether the user can utilize a resource without a failure. Thus, the availability in mobile Grid is defined as a ratio of the expected uptime (e.g. system power is on) to the sum of the expected uptime and downtime (e.g. system power is off).
$$Availability={{T_{{up}} } \over {T_{{up}} {\,\plus\,}T_{{down}} }}$$
where T up is the uptime and T down the downtime.
The downtime is classified into a planned downtime and an unplanned downtime. For example, the rebooting caused by system configuration changes is categorized as the planned downtime. Unhandled exceptions and physical problems such as hardware failures are categorized as the unplanned downtime. As the planned downtime is inevitable, we focus on reducing the unplanned downtime caused by power supply shortage and network link failure. There are four different combinations depending on the power status and network link status. Especially, we pay a special attention to the case where the system power is on, but the network link is down. This case is an uptime from a job point of view if it does not require communication during execution via network link. However, it becomes a downtime in the opposite situation where the job does require communication. It indicates that the system availability becomes different according to the job characteristic. When a job should be executed for a relatively long time without suspension, the reliability plays an important role and the communication failure by mobility should be taken into account in the formula.
4 System model
Mobile Grid is a convergence of wired and wireless computing environment to efficiently utilize both fixed and mobile resources. It typically consists of physically fixed devices, mobile devices, and proxies. Consequently, it requires a new system model incorporating various homogeneous and/or heterogeneous resources. The new system should be lightweight to be ported to mobile devices with limited resources. It also should guarantee the delivery of messages in an unreliable communication environment. In this section, we first present the mobile Grid system (MGS) architecture that is a mobile Grid framework based on a novel mobile agent system. Then, we describe a multi-domain proxy environment where MGS is deployed to. Finally, we illustrate location management and message delivery protocols to control mobile agents and guarantee message transfer between mobile agents.
4.1 Mobile Grid system architecture
In Choi et al. (Reference Choi, Choo, Baik, Kim and Byun2009), we proposed ODDUGI, a mobile agent system, that enables the creation, execution, transfer, and termination of mobile agents. ODDUGI provides primitives necessary for the development and management of mobile agents. Basic primitives support the creation, execution, clone, migration, activation, deactivation, and termination of a mobile agent. Extended primitives provide communication, fault tolerance, security, location management and message delivery, and monitoring tools. Mobile devices typically do not provide enough capacity to accommodate service-based Grid middleware such as Globus. One of the distinct features in ODDUGI is that it is lightweight enough to be installed on mobile devices such as PDA. Based on ODDUGI, we propose a MGS architecture to utilize mobile devices as resource providers.
MGS is composed of infrastructure, runtime, place, agent, proxy, and application layers as shown in Figure 1. The infrastructure layer includes physical devices such as supercomputer, data storage, cluster, desktop PC, laptop, and PDA. The runtime layer contains the Globus Toolkit and various managers: resource manager, communication manager, and security manager. The communication manager is a daemon that listens to a certain port, waiting for mobile agents and messages from proxy and other nodes. It cooperates with the location management and message delivery and messaging units in the place layer. The resource manager manages the system properties and resources used in ODDUGI. The security manager is responsible for maintaining security in ODDUGI. It cooperates with the security unit in the place layer. The place layer is an execution environment for mobile agents. It provides core functionality such as creation, execution, clone, migration, retraction, activation, deactivation, termination, and messaging. It also provides enhanced functionality such as fault tolerance, security and location management, and message delivery of mobile agents. The place layer is implemented as a GUI-based system manager, which helps manage mobile agents systems more conveniently. The agent layer provides application developers with APIs for migration, clone, activation, and communication to implement mobile agents. It allows application developers to create, execute, clone, retract, activate, deactivate, and terminate mobile agents as well as interact with other agents. A mobile agent object that consists of code, data, various information (i.e. identifier, creator, time, codebase, etc.), and mobility metadata (i.e. itinerary, state, results, etc.) is manipulated in the agent layer. The proxy layer provides service-based delegation functionality so that users and mobile devices do not have to be online all the time when requesting or executing jobs. It is composed of information service, scheduling service, and service container. The information service collects resource information via information providers such as Network Weather Service. The scheduling service chooses suitable resources to execute requested jobs according to the scheduling algorithm. Our scheduling algorithm takes into account user mobility, load-balancing, and adaptability, as described in Section 5.
Mobile Grid system architecture
4.2 Multi-proxy-based mobile Grid computing environment
In this paper, we use a multi-proxy environment where multiple proxies exist in a system and each proxy manages its own domain. The environment is composed of five components: mobile agent, node (i.e. fixed or mobile devices), domain, proxy server (PS), and global server (GS). Figure 2 shows a multi-proxy mobile Grid computing environment.
∙ Mobile agent: A mobile agent is a mobile object that consists of code, data, state, and mobility metadata. The mobile agent is able to migrate from one node to another autonomously while performing a task. When a mobile agent migrates, it chooses the next destination according to its itinerary that is either a predefined travel plan or a dynamically determined path according to the execution result. A path from a source to the final destination is called a migration path.
∙ Node: A node is a place (i.e. a mobile device) where mobile agents can be executed on. Thus, the node should be installed with a mobile agent system. The node offers specific services such as computation and location awareness. A mobile agent executes tasks either on a single node or migrating through a sequence of nodes. The node that creates a mobile agent is called a home node (HN).
∙ Domain: A domain contains a set of nodes under one authority (such as proxy). One domain typically contains mobile devices around one access point (AP).
∙ Proxy server: A PS is responsible for managing its domain (OMG, 1997). The PS provides the naming service for mobile agents created within its domain, cooperating with its GS. It performs the location management for the mobile agents within its domain with the naming table that associates the names of mobile agents with the addresses of the HNs. In addition, the PS provides the information service, scheduling service, and service container. The information service collects information of mobile devices such as machine and network availabilities. Using this information, the scheduling service makes a decision on which mobile devices are available for the job execution. Jobs are delegated via a service-based interface to the PS (i.e. service container), which creates and deploys mobile agents for the jobs.
∙ Global server: A GS provides the lookup service for mobile agents and nodes. The GS maintains the location information as well as the list of service information for the mobile agents created and delivered in all domains.
Multi-proxy mobile Grid computing environment: (a) physical mobility, (b) logical mobility – intra-domain migration, (c) logical mobility – inter-domain migration
In such an environment, a mobile agent executes tasks migrating through a sequence of nodes possibly located in different domains. Each action that a mobile agent performs on a node is called a stage. The execution of mobile agents on a node results in a new internal state of mobile agent as well as potentially a new state of the node. Therefore, the mobile agent status in the previous stage is different from one in the current stage.
As shown in Figure 2, there are two types of mobility: physical mobility and logical mobility. The physical mobility means that a mobile node moves to other domain but a mobile agent remains in the same node, as depicted in Figure 2(a). The logical mobility means that only the mobile agent moves to a different mobile node located in the same or other domain, as depicted in the migration paths of Figures 2(b) and 2(c). In all cases, the PS should be informed of the new locations of mobile agents. Therefore, the mobile Grid system provides the location management to interact with mobile agents in a multi-proxy mobile Grid environment.
4.3 Location management and message delivery
The location management and message delivery protocols are fundamental to the further development of mobile Grid in a multi-proxy mobile Grid to control mobile agents and guarantee message transfer between mobile agents (Domel et al., Reference Domel, Lingnau and Drobnik1997; Baumann & Rothermel, Reference Baumann and Rothermel1998; Lingnau & Drobnik, Reference Lingnau and Drobnik1998; Baumann, Reference Baumann1999; Cabri et al., Reference Cabri, Leonardi and Zambonelli2000; Deugo, Reference Deugo2001; Wojciechowski, Reference Wojciechowski2001; Murphy & Picco, Reference Murphy and Picco2002; Stefano & Santoro, Reference Stefano and Santoro2002). It is more difficult to implement location management and message delivery protocol in multi-proxy mobile Grid owing to the frequent movements of mobile agents or mobile nodes as well as the limited network bandwidth in a widely distributed computing environment such as Internet.
We propose a location management and message transfer protocol based on our prior works: Broadcast-Based Message Transferring protocol (Baik et al., Reference Baik, Yang, Shon and Hwang2003) and Reliable Asynchronous Message Delivery (RAMD) protocol (Choi et al., Reference Choi, Kim, Byun, Hwang and Baik2006). The Broadcast-Based Message Transferring protocol broadcasts only the notification of changes instead of message content itself, so subscribers may request the details of changes if necessary. Therefore, it reduces the amount of network traffic. This protocol is useful for the event notification in mobile agent-based mobile Grid. In service-based Grid, WS-Notification specification allows the event-driven programming between Grid services. However, it would not be applied to the mobile agent system because it demands the Web services, which typically require the modest computing power. The RAMD protocol consists of a location management procedure and a blackboard-based asynchronous message delivery procedure. In order to reliably and asynchronously deliver messages, RAMD exploits a blackboard (i.e. a shared information space for message exchange). In addition, the message delivery is tightly related with the agent migration. It guarantees the message delivery by placing a blackboard in each domain. That is, this protocol is useful for the reliable delivery of messages in mobile Grid where mobile agents can be frequently moved.
The RAMD protocol for mobile Grid consists of three phases: creation, migration, and message delivery phases. In the creation phase, a mobile agent registers its location to the GS and the PS upon creation. In the migration phase, a mobile agent registers its location to the HN or its associated PSs when the agent migrates from one node to another. The migration phase is divided into intra-domain migration (i.e. when a mobile agent migrates to a node within the same domain) and inter-domain migration (i.e. when a mobile agent migrates to a node in other domain). According to the migration type, the location registration procedure is executed differently. In the intra-domain migration, a mobile agent sends a location update message only to the PS with which the mobile agent is associated. In the inter-domain migration, a mobile agent sends the location update message to the HN, previous PS and current PS. In the message delivery phase, a message is delivered to a mobile agent after looking up the naming table and locating the agent. First, a sender finds the address of the HN by contacting the GS and sends a message to the PS. Then the PS puts the message on its blackboard. Finally, when the PS receives a location update message from a mobile agent, the PS checks its blackboard. If there is a message, the PS retrieves it from the blackboard and delivers it to the mobile agent. In this way, the RAMD protocol for mobile Grid decreases the cost of the location management and the message delivery. Furthermore, the RAMD protocol for mobile Grid takes care of the location management and message delivery of cloned, parent, and child mobile agents, so that it ensures the message delivery of these mobile agents.
5 Balanced scheduling algorithm in mobile Grid
In the loosely connected network environment like mobile Grid, the scheduling algorithm plays a critical role in performance and the scheduler should take into account mobile-specific parameters. In this section, we discuss our novel balanced scheduling algorithm taking mobility, load-balancing, and adaptability into account. We first investigate characteristics of users’ mobility patterns to quantitatively measure the resource availability. The availability is used to evaluate the expected execution time of a job. Then, we propose an adaptive load-balancing technique, where mobile devices are classified into nine groups depending on availability and a job is allocated to a group according to the job type. Our technique allocates the job to a new group adaptively upon changes in the job type.
5.1 Users’ mobility patterns
This section discusses mobility parameters investigated in the prior research, and introduce new parameters suitable for the mobile Grid environment.
In computer networks, an AP is a device that allows wireless devices to connect to a wireless network. The mobile device user may freely move around APs and has access to the network. In a mobile environment, all time (T all) of a mobile device is divided into an uptime and a downtime. The uptime is further divided into a time (T connected) duration during which a network is connected and a time (T disconnected) duration during which a network is disconnected.
Balazinska and Castro (Reference Balazinska and Castro2003) introduced two metrics to model the user mobility: AP prevalence and user persistence. They are duplicated as follows for convenience.
Definition 1 AP prevalence (Prev) is defined as a ratio of the time duration (T ij) during which the i thuser spends in a given j thAP to the time duration (T connected) during which network is connected.
$$Prev_{{ij}} ={{T_{{ij}} } \over {T_{{connected}}^{i} }}$$
The more a user visits an AP and/or spends time at the AP, the AP prevalence becomes higher. In Balazinska and Castro (Reference Balazinska and Castro2003), each user is classified into one of five groups (stationary, occasionally mobile, regular, somewhat mobile, and highly mobile) based on the maximum prevalence and the median prevalence. As the AP prevalence does not consider the user’s mobility pattern of how often and how long a user maintains each session in AP, it is not able to represent the communication instability caused by user’s frequent movements among APs. The user persistence complements this shortcoming.
Definition 2 User persistence (Pers) is defined as a time duration during which the i thuser stays at the j thAP until the user moves to other AP or network link is down.
$$T_{{ij}} =\mathop{\sum}\limits_{k\,=\,1}^n Pers_{{ijk}} $$
where n is the number of sessions.
If the terminal mobility of mobile devices is guaranteed, a mobile device can continuously interact with the job requestor and the user persistence does not contribute to reliability. In mobile Grid, however, a network link could be down unexpectedly disabling the communications of mobile devices with the requestor. Thus, the communication stability should be taken into account as an important factor in job allocation.
As mentioned, there are four possible combinations depending on power status (on and off) and network link status (connection and disconnection). We remove one obvious and unattainable condition (power off and network link on) as the network link cannot be established without power supply. The remaining three combinations are considered in our paper. The probabilities P c, P p, and P d of the three cases are given by Equations (4), (5), and (6), respectively, assuming that the i th user stays at the j th AP. P c is a probability that power is on and network is connected. P p is a probability that power is on and network is disconnected. P d is a probability that power is off and network is disconnected.
$$P_{c}^{i} ={{\mathop{\sum}\nolimits_{k\,=\,1}^n {Pers_{{ijk}} } } \over {T_{{all}}^{i} }}={{T_{{ij}} } \over {T_{{all}}^{i} }}$$
$$\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!P_{p}^{i} ={{T_{{up}}^{i} } \over {T_{{all}}^{i} }}{\,\minus\,}P_{c}^{i} $$
$$\,\,\,P_{d}^{i} =1{\minus}(P_{c}^{i} {\,\plus\,}P_{p}^{i} )={{T_{{down}}^{i} } \over {T_{{all}}^{i} }}$$
Using the above three equations, we classify availability into three types: full availability, partial availability, and unavailability.
Definition 3 Full availability (A c) is defined as a probability that a mobile device is able to execute jobs and return outcome via network link.
$$A_{c} ={{P_{c} } \over {P_{c} {\,\plus\,}P_{p} {\,\plus\,}P_{d} }}$$
Definition 4 Partial availability (A p) is defined as a probability that a mobile device is able to execute jobs, but cannot return outcome due to the network failure.
$$A_{p} ={{P_{p} } \over {P_{c} {\,\plus\,}P_{p} {\,\plus\,}P_{d} }}$$
Definition 5 Unavailability (A d) is defined as a probability that a mobile device cannot execute jobs at all because device is off.
$$A_{d} =1{\minus}(A_{c} {\,\plus\,}A_{p} )$$
The job execution consists of three phases: input transmission, computation, and outcome transmission. Data transmission may occur in the middle of computation, which is obviously possible only when a mobile device is connected to a network. We define the unit time (u) as a time duration during which we measure availability. For example, when we measure a full availability during last 60 seconds, u is 60. The expected transmission time (E tr) is described by Equation (10).
$$\ \ \ \ \quad\quad E_{{tr}} (r)=\mathop{\sum}\limits_i p_{i} x_{i} \,\leq\, A_{c} \,{\asterisk}\,ru{\,\plus\,}(1{\,\minus\,}A_{c} )\,{\asterisk}\,((1{\,\minus\,}A_{c} )u{\,\plus\,}E_{{tr}} (r))$$
$$\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\Rightarrow \ \ E_{{tr}} (r)\,\leq\, \left(r{\,\plus\,}{1{\,\minus\,}A_{c} ^{2} \over A_{c}} \right)u \quad(0\,\leq\, r\,\leq\, 1)$$
where r is the ratio of the actual amount of data transmission for the job execution including input and outcome data to the amount of data that can be transmitted within a unit time. That is, ru means the actual data transmission time under the healthy network condition. Considering the network connection status, the expected time for the ru transmission is the sum of the transmission time during which the network condition is healthy (i.e. the first term) and the transmission time during which the network is disconnected (i.e. the second term). The 
$$(1{\,\minus\,}A_{c} )u$$
and 
$$E_{{tr}} (r)$$
in the second term is the waiting time until the network is connected again and the expected transmission time on a repeated attempt (which is recursive), respectively.
The expected computation time E cp is described by Equation (11).
$$\eqalignno{ & \,\,E_{{cp}} (k,m)=\mathop{\sum}\limits_i p_{i} x_{i} \,\leq\, (A_{c} {\,\plus\,}A_{p} )\,{\asterisk}\,(ku{\,\plus\,}\mathop{\sum}\limits_{i\,=\,1}^c E_{{tr}} (m_{i} )) \cr & {\,\plus\,}(1{\,\minus\,}A_{c} {\,\minus\,}A_{p} ){\asterisk}((1{\,\minus\,}A_{c} {\,\minus\,}A_{p} )u{\,\plus\,}E_{{cp}} (k,m)) \cr & \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\Rightarrow \ \ \ \ E_{{cp}} (k,m)\,\leq\, (k{\,\plus\,}m{\,\plus\,}{{c(1{\minus}A_{c} )^{2} } \over {A_{c} }}{\,\plus\,}{{(1{\,\minus\,}A_{c} {\,\minus\,}A_{p} )^{2} } \over {A_{c} {\,\plus\,}A_{p} }})u \quad(0\,\leq\, k,m\,\leq\, 1) $$
where k is the ratio of the amount of computation for the job execution to the amount that can be computed within a unit time and m is the ratio of the amount of data transmission to the amount of data that can be transmitted within a unit time during the job execution and c is the number of transmissions during the job execution.
Therefore, the expected execution time E is formulated as follows.
$$E(s,e,k,m)\,\leq\, (s{\,\plus\,}e{\,\plus\,}k{\,\plus\,}m{\,\plus\,}{{(c{\,\plus\,}2)(1{\,\minus\,}A_{c} )^{2} } \over {A_{c} }}{\,\plus\,}{{(1{\,\minus\,}A_{c} {\,\minus\,}A_{p} )^{2} } \over {A_{c} {\,\plus\,}A_{p} }})u \quad(0\,\leq\, s,e,k,m\,\leq\, 1)$$
where s is the ratio of the amount of input data transmitted at the beginning to the amount of data that can be transmitted within a unit time and e is the ratio of the amount of outcome transmitted to the amount of data that can be transmitted within a unit time at the end of a job execution.
The first four terms (su, eu, ku, mu) in Equation (12) are equivalent to the transmission time spent in reliable wired network as they represent the transmission time under the healthy network condition. The rest (
$${{(c{\,\plus\,}2)(1{\minus}A_{c} )^{2} } \over {A_{c} }}$$
, 
$${{(1{\minus}A_{c} {\minus}A_{p} )^{2} } \over {A_{c} {\,\plus\,}A_{p} }}$$
) is mobile-computing-related terms. In other words, the expected execution time in mobile Grid is increased by these two terms. Therefore, the parameters (A c, A p, c) should be used as criteria for choosing mobile devices as target Grid resources to minimize the overall execution time.
Under a full availability condition like a traditional Grid, the expected computation time (E cp) and the expected execution time (E) are reduced to Equations (13) and (14) as A p becomes 0.
$$\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!E_{{cp}} (k,m)=\mathop{\sum}\limits_i p_{i} x_{i} \,\leq\, A_{c} \,{\asterisk}\,(ku{\,\plus\,}\mathop{\sum}\limits_{i\,=\,1}^c E_{{tr}} (m_{i} ))$$
$$\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\plus}(1{\,\minus\,}A_{c} )\,{\asterisk}\,((1{\,\minus\,}A_{c} )u{\,\plus\,}E_{{cp}} (k,m))$$
$$\quad\Rightarrow \ \ E_{{cp}} (k,m)\,\leq\, (k{\,\plus\,}m{\,\plus\,}{{(c{\,\plus\,}1)(1{\,\minus\,}A_{c} )^{2} } \over {A_{c} }})u\quad(0\,\leq\, k,m\,\leq\, 1)$$
$$E(s,e,k,m)\,\leq\, (s{\,\plus\,}e{\,\plus\,}k{\,\plus\,}m{\,\plus\,}{{(c{\,\plus\,}3)(1{\,\minus\,}A_{c} )^{2} } \over {A_{c} }})u \quad(0\,\leq\, s,e,k,m\,\leq\, 1)$$
The Equation (14) is always higher than the Equation (12). In other words, with utilizing devices with the partial availability (A p) in mobile Grid, the expected execution time is reduced at a maximum by the difference between Equation (12) and Equation (14). Therefore, the scheduling algorithm should consider both the full availability and the partial availability of the computing resources and allocate jobs to appropriate devices, to optimize the execution time of workloads.
5.2 Adaptive load-balancing algorithm using multi-level feedback queues
In Grid, a job is commonly classified into two types: computing intensive and communication intensive. These two types of jobs have different resource requirements, so different scheduling policies are required accordingly. Mobile Grid tends to provide a superior performance when a scheduler assigns jobs with a large amount of communication, preferably to stable mobile devices under healthy network condition. It is because the probability of interruption in the job execution decreases owing to the unexpected network failure. It directly implies that it is crucial to assign jobs to pertinent mobile devices according to the job type. For the job allocation, we propose a scheduling algorithm based on a multi-level job queue with priority. The priority is determined based on the full availability and the partial availability.
Mobile devices are classified into nine groups based on the full availability and the partial availability as shown in Table 1, where o and ω represent an upper bound and a lower bound, respectively, for the classification.
Nine groups based on the full availability and the partial availability
Figure 3 shows an example of nine groups. In practice, the communication reliability of the groups HH, HM, and HL is preferable for executing jobs as the computing resource and network condition are relatively stable and healthy. However, it is inefficient in terms of execution time and resource utilization to assign all jobs to devices from just three groups, when a pool of resource is limited compared with the job execution requests. As shown in Equation (12), a job with no communication may be executed in a resource with either a full or a partial availability (A c and A p), resulting in a superior performance in overall execution (e.g. the group MH). We propose the first scheduling policies according to the job type, based on the following two guidelines.
∙ Jobs with long communication interval are assigned to mobile devices with a higher A p even if A c is not high.
∙ Jobs with a large amount of communication are assigned to mobile devices with a higher A c.
Scheduling Policy 1Determine a priority level (high, medium, low) according to the amounts of the computation and communication of a job and select a queue according to the levels of A cand A p.
Example of nine groups with 
$$\omega _{{A_{c} }} $$
, 
$$o_{{A_{c} }} $$
, 
$$\omega _{{A_{p} }} $$
, and 
$$o_{{A_{p} }} $$
set to 0.33, 0.66, 0.11, and 0.22, respectively. Solid red and blue rectangles represent minimum probabilities each group should have for A c and A p, respectively. Dotted rectangles indicate the range that A c and A p are allowed to have
The transmission frequency (c) during the job execution affects to the performance, as shown in Equation (12). The term 
$${{(c{\,\plus\,}2)(1{\minus}A_{c} )^{2} u} \over {A_{c} }}$$
indicates that the expected execution time is influenced by c and A c. As a job with a higher c is more interactive, it is preferable to assign the job to a mobile resource with a higher A c to decrease the overall execution time. Based on this observation, we propose the second scheduling policy using multi-level queues.
Scheduling Policy 2Determine a priority level (high, medium, low) according to the number of transmissions during the job execution and select a queue according to the level of 
$$A_{c} $$
.
A multi-level feedback queue scheduling (Kleinrock & Muntz, Reference Kleinrock and Muntz1972) is an advanced scheduling algorithm based on multi-level queues. It is an adaptive technique as a process is dynamically allocated to a different queue according to constraints on execution time. If the process is completed within a time quantum, the scheduler commits the current queue information and execution time to memory. Otherwise, the process is demoted to a lower level queue that provides a longer time quantum. When the same process is ready for execution next time, the scheduler allocates a queue based on the previous history. After the completion of the process, the scheduler adjusts a queue level by comparing the previous execution time with the current execution time.
Our proposed algorithm provides adaptability similar to the multi-level feedback queue scheduling. If the queue level of a job is unknown from history, our scheduler assigns the job to a queue with the highest priority, as illustrated in ➀ of Figure 4(a). Then it keeps a record of current queue level and execution time after completing the job (➁ of Figure 4(a)). If the same job comes in next time, the new job is sent to a queue with one lower level (➂ of Figure 4(a)). After the new job is completed, our scheduler compares the new execution time with the previous one (➃ of Figure 4(a)). If the difference between the execution times is under a threshold, the queue level of the job is kept as the current queue level. Otherwise, the queue level of the job is promoted to the previous one. When the queue level of a job is known in advance, our scheduler assigns a job to the queue (➀ of Figure 4(b)) and it keeps a record of execution time after completing the job (➁ of Figure 4(b)). If the difference between the previous and the current execution times is under a threshold, the queue level of the job is equal to the previous one. If the difference (previous execution time minus current execution time) exceeds the threshold negatively, the queue level of the job is promoted to the upper one (➂ of Figure 4(b)). If the difference exceeds the threshold positively, the queue level of the job is demoted to the lower one (➃ of Figure 4(b)). In this way, our scheduling algorithm changes the queue level of a job and provides adaptability with load-balancing.
Adaptive scheduling examples: (a) when the queue level of a job is unknown, (b) when the queue level of a job is known in advance
Figure 5 details the balanced scheduling algorithm in mobile Grid. su is the transmission time for input data at the beginning. mu is the transmission time for data during a job execution. eu is the transmission time for outcome at the end of a job execution. ku is the computation time when the resource is fully available. c is the number of transmissions during a job execution. E is the expected execution time.
Balanced scheduling algorithm in mobile Grid
6 Implementation
We implemented the MGS based on Globus Toolkit Version 4 and ODDUGI mobile agent system. In MGS, a PS plays key roles as follows: job reception from clients, creation, and management of mobile agents, and outcome delivery from mobile agents to clients. Globus supports a stateful Web service keeping stateful resource information. We assume that a resource corresponds to a mobile agent. A multiple-resource stateful Web service is implemented by using separate classes for service and resource. The service class is implemented with a design pattern known as the factory/instance pattern, which is shown in Figure 6. The client interacts with two services (factory service and instance service) to submit a job. The client requests a resource home to create a resource through the factory service (Figure 6 (a)). Then the client receives EPR (endpoint reference, i.e. Agent ID) from the resource home through the factory service (Figure 6(b)). The client executes a resource operation through the instance service by using a given EPR (Figure 6(c)).
Factory/instance pattern: (a) resource creation, (b) EPR reception, (c) execution of a resource operation, (d) notification of a result to a client
When the client executes the resource operation, it may have to wait for a response synchronously until timeout. Asynchrony in mobile agent system prevents the wasteful pauses as the client is notified when the mobile agent completes a job. However, in mobile Grid, the asynchrony is maintained between proxies and mobile agents. Thus, there should be a communication mechanism between proxies and clients. The simplest approach is that a client keeps track of outcome status in a proxy using polling. That is, the client periodically contacts a PS to check whether the requested job is finished. However, this approach incurs an overhead because the client repeatedly sends a polling message to a server and there is a scalability problem if many clients exist in a system. Therefore, we implemented the response message delivery using the WS-Notification family of the specification. This approach notifies the result to the client when the PS receives the result from the mobile agent (Figure 6(d)). We used different protocols among clients, proxies, and mobile devices. Between proxies and mobile devices (i.e. mobile agents), we implemented Broadcast-Based Message Transferring and RAMD protocols for the asynchronous message delivery. Between proxies and clients, we used WS-Notification specification for the asynchronous message delivery.
We implemented MGS with the GUI-based mobile agent managers that facilitate the creation, execution, clone, migration, retraction, activation, deactivation, and termination of a mobile agent, as shown in Figure 7(a). MGS implements the RAMD protocol and the Broadcast-Based Message Transfer protocol in a multi-domain mobile Grid. The protocols are implemented in the GS, PS, and HN. The GS maintains a list of mobile agents that contains information such as HN, Agent ID, Agent Name, and Home PS, as shown in Figure 7(b). The PS maintains a list of nodes and mobile agents that contains information such as Agent ID, Agent Name, HN, Current Node, and Home PS, as shown in Figure 7(c). The HN maintains a list of mobile agents that includes information such as Agent ID, Agent Name, Current Node, Home PS, and Current PS, as shown in Figure 7(d).
GUI-based mobile agent managers: (a) mobile agent manager, (b) global server, (c) proxy server, (d) home node
7 Experiments and analysis
7.1 Experimental environment
We evaluated our scheduling algorithm using SimGrid toolkit (Casanova et al., Reference Casanova, Legrand and Quinson2008) with a real-life trace: WLAN trace (Henderson & Kotz, Reference Henderson and Kotz2007) of Dartmouth campus. SimGrid is a comprehensive simulation framework for executing distributed applications on distributed platforms such as Grid. It provides various simulation interfaces such as MSG, GRAS, SMPI, and SimDag. Especially, MSG offers a mobile agent simulation environment. Therefore, we constructed a simulation environment of our mobile Grid architecture using MSG, as shown in Figure 8. Moreover, as MSG is pertinent for the study of concurrent sequential processes applications, it is suitable to experiment our scheduling algorithm. We implemented proxy, agent, and place layers in our architecture to the simulation environment. After analyzing the trace, network information was extracted and it is supplied to the SimGrid platform through SURF, which is corresponding to the runtime and infrastructure layers of our architecture. The trace is composed of the syslog records produced by APs from September 1, 2005 to October 4, 2006. The trace as of June 6, 2006 is chosen to create network information to provide input to the SimGrid platform. It includes 987 APs and 3367 mobile devices. Figure 9 shows the number of users connected to network by hours on June 6, 2006. Because not enough users (i.e. devices) are connected to the network from midnight (0 o’clock) to 4 o’clock in the morning, it may take a longer time to complete jobs, compared with other time slots, given that the number of jobs is the same. In other words, the execution time for the same amount of jobs varies according to the time slot. Figure 10 shows a histogram of the number of sessions lasting <2 hours. Figure 11 shows a cumulative density function of the number of sessions. The data shown in Figure 11 includes sessions maintained for more than 24 hours. Owing to the unstable communication environment, the number of the sessions maintained <2 hours is about 80% of the trace. After fitting the probability density function to various statistic distributions, we found that the Pareto distribution fits best with the shape and the scale parameters equal to 1.2602 and 3018.0, respectively. To provide the processor status information to the SimGrid platform, we used the Weibull distribution as it effectively represents the machine availability (Nurmi et al., Reference Nurmi, Brevik and Wolski2005). We randomly extracted time durations by the inverse function of the Weibull distribution.
Simulation environment of our mobile Grid architecture using SimGrid: the architecture layers of our mobile Grid system are indicated in dotted black lines and the rest is the SimGrid environment
Number of users connected to network according to hours in the trace on June 6, 2006
Histogram of the number of sessions lasting <2 hours in the trace on June 6, 2006
Cumulative density function of the number of sessions in the trace on June 6, 2006
Based on the network information and the time durations, we created testvectors for full and partial availabilities. The network information from the WLAN trace is used as the time slots for the full availability. The time durations are used as the time slots for partial availability. Then the processor start time is calculated by padding the time duration from the network information in front of processor time duration, and the processor completion time is calculated by padding the time duration from the network information behind the processor time duration. In this way, the processor information is synchronized with network information. Figure 12 shows a division into nine groups used in the experiment according to A c and A p. The dotted lines on the x and y axes indicate upper and lower bounds of A c and A p, so it is classified into nine groups.
Nine groups used in the experiment according to A c and A p
Then we randomly created jobs (i.e. mobile agents) with various computation and transmission sizes and limited the number of data transmissions (e.g. file download and agent migration) during the job execution to two. Figure 13 shows the distribution of computation and data transmission sizes used in the experiment. An x-axis represents the normalized distribution of the amount of computation over the maximum amount of computation and a y-axis represents the normalized distribution of the amount of transmission over the maximum amount of data transmission for 2000 jobs used in this experiment. It conforms to the Normal distribution.
Normalized distributions of the amount of computation and the amount of data transmission for the job execution
7.2 Experimental results
We investigated the effects of three factors (i.e. user mobility pattern, load-balancing, and adaptability) on execution time. The first experiment evaluates the effect of the user mobility pattern on execution time. The full and partial availabilities in the consideration of Table 2 are created by the user’s movement. Table 2 also lists four methods used in the experiment. The Method I-1 in Table 2, for example, means that the scheduler allocates jobs to resources without considering full availability, partial availability, and data transmission during job execution. The Method I-4 reflects our scheduling algorithm.
Four methods to evaluate the effect of the user mobility on performance
Figure 14 shows the average execution time of each method. As shown, the Method I-4 reports the shortest execution time. It provides about 30% performance improvement compared with a prior work (Park et al., Reference Park, Ko and Kim2003), of which condition is reflected in the Method I-3. Currently, our dynamic scheduling algorithm is not directly applicable to batch jobs. However, we expect that the performance of batch jobs would be greatly enhanced by applying minimum–minimum (Maheswaran et al., Reference Maheswaran, Ali, Siegel, Hensgen and Freund1999) and maximum–minimum (Maheswaran et al., Reference Maheswaran, Ali, Siegel, Hensgen and Freund1999) because these algorithms consider the job type in batch mode scheduling. Figure 15 shows standard deviations of the number of workloads assigned to mobile resources for Methods I-1, I-2, I-3, and I-4. The Method I-1 has the lowest standard deviation because jobs are allocated to randomly selected resources, resulting in even distribution. The rest of the methods show relatively high standard deviations as the load-balancing is not taken into account in this experiment.
Average execution time of Methods I-1, I-2, I-3, and I-4 according to the number of jobs
Standard deviation of the number of workloads assigned to mobile resources for Methods I-1, I-2, I-3, and I-4 according to the number of jobs
Second, we investigated the effect of the load-balancing on execution time. Based on the Method I-4, we experimented with the following three methods.
∙ Method II-1: jobs are evenly allocated to mobile devices in a round robin fashion.
∙ Method II-2: mobile devices are classified into three groups according to the full availability, and a job is allocated to a group corresponding to the job type.
∙ Method II-3: mobile devices are classified into nine groups according to full availability and partial availability, and a job is allocated to a group corresponding to the job type.
Figure 16 shows average execution time of each method and Figure 17 shows standard deviations of the number of workloads on Grid resources. The Method II-1 provides the best load-balancing with the worst execution time. The Method II-2 provides the best performance, yet marginally better than the Method II-3. However, the Method II-2 reports the worst load-balancing. The Method II-3 reports a medium standard deviation and a comparable execution time to the Method II-2. Consequently, it is not unreasonable to state that the Method II-3 is suitable for job scheduling because it is satisfactory in terms of execution time and at the same time it provides a relatively low standard deviation in the workload distribution.
Average execution time of Methods II-1, II-2, and II-3 according to the number of jobs
Standard deviation of the number of workloads assigned to mobile resources for Methods II-1, II-2, and II-3 according to the number of jobs
The average execution time and the degree of load-balancing are influenced by the upper and the lower bounds in the group classification. Because our scheduler determines a group according to the job type, if many mobile devices belong to a group with a fewer jobs, the average execution time and the load-balancing would get worse. Therefore, it is imperative to determine the upper and the lower bounds dynamically.
Finally, we experimented the effect of adaptability on execution time.
∙ Method III-1: a job is allocated to the same group even if its job type is changed.
∙ Method III-2: a job is allocated to a new group if its job type is changed.
Based on Method II-3, we conducted experiments, executing jobs with unknown types, with the trace on June 6, 2006 and saved the execution times and queue information. After changing a 10% of the job type, we executed these jobs with the trace on June 7, 2006. Our algorithm then compared the execution time with one in the previous execution and adjusted the queue levels. We investigated adaptability by measuring the execution times with applying the new queue levels to the trace on June 8, 2006.
Figure 18 shows the average execution time of each method and Figure 19 shows standard deviations of the number of workloads assigned to mobile resources. The execution time of the trace on June 8, 2006 is longer than the one of June 6, 2006. It is because the number of mobile devices participated in the former date is less than the one in the latter date. Figure 18 also reports that the Method III-2 provides about 8% performance improvement compared with the Method III-1, dynamically adjusting to the job type changes. Figure 20 shows increased execution times of the Method III-1 on average, compared with the Method III-2, according to the job type changes and the number of jobs. As shown, the difference in execution time diverges as the change in job type is higher. It proves that our scheduling algorithm dynamically adapts to the job type change, resulting in the superior performance in job execution.
Average execution time of Methods III-1 and III-2 according to the number of jobs
Standard deviation of the number of workloads assigned to mobile resources for Methods III-1 and III-2 according to the number of jobs
Increased execution times of Method III-1, compared with Method III-2, according to job type changes and the number of jobs
8 Conclusions and future work
This paper presents a novel balanced scheduling algorithm in mobile Grid based on mobile agents. We first described a multi-domain proxy environment and illustrated the location management and the message delivery protocols of mobile agent to guarantee the message delivery between mobile agents. The MGS is implemented based on the Globus Toolkit and the ODDUGI mobile agent system. Our algorithm takes into account mobility, load-balancing, and adaptability in scheduling. We analyzed user’s mobility patterns to quantitatively measure the resource availability that is classified into three types: full availability, partial availability, and unavailability. For the adaptive load-balancing, mobile devices are classified into nine groups depending on the full and the partial availabilities. The adaptive technique dynamically promotes or demotes the queue level of a job depending on the change in job type. The experimental results show that our scheduling algorithm provides a superior performance to the one without considering the partial availability. Throughout the experiments, we found that the partial availability and the grouping are crucial factors for the performance and the load-balancing. Overall, our study provides effective solutions to allocate mobile resource according to the job type. In the future, we have a plan to conduct a wider variety of experiments to study additional factors that contribute to performance and load-balancing in mobile Grid. We also have a plan to apply methods such as the batch scheduling and the dynamic selection of the upper and the lower bounds for A c and A p.
Acknowledgment
This work was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD) (KRF-2006-311-D00173).
