Offloading Topology

Application components and the surrogate sites are the two sides of the offloading topology. While there can be one or multiple application components and there can be one or multiple surrogate sites, there are four total combinations. They are $1:1$, $1:n$, $m:1$, and $m:n$ topologies.

If a Boolean matrix named E is used to describe the mapping and the rows corresponding to application components and the columns are corresponding to surrogate sites, the four topologies are $E_{1\times 1}$, $E_{1\times m}$, $E_{m\times 1}$, and $E_{m\times n}$. For each row, there are at least one 1 since that application component has to find a surrogate to run. If there is more than one surrogate running an application component, that application component gets duplicate copies to be resistant to device or network failures.

Offloading Series

The execution environment changes with time, thus the impact of one time offloading may diminish. In this scenario, the subsequent offloading may be applied to adjust the offloading topology and maintain the offloading benefit. Multiple offloading forms the offloading series. For each offloading topology above, there could be a series as shown in Fig. 5.2.

Execution Time

According to [269], at any time, the computation load for every component and the volume of data exchange for every edge in application graph is known based on a given task, or is predictable based on the application and user historical behavior. The workload is distributed on the application graph, which makes $G_{app}$ into a weighted graph. The computation load is presented as a weight value on each vertex: the component x is labeled with computation load $w_x$ and vector w is computation load of all vertexes. The data exchange amount is presented as a weight value on an edge: the edge $a=(x_1,x_2)$ from $x_1$ to $x_2$ is labeled with data transfer load $f_{x_1{x}_2}$ and matrix $F_{n\times n}$ is data exchange load of all edges. The diagonal of F are all 0's because the component's interaction with itself does not count for intercomponent data exchange load; and $f_a=0$ if $a\in A$ is false.

Meanwhile, the surrogates' capability is measurable, so the egocentric network $G_{sur}$ is transformed into a weighted graph as well. The available computation capability on a candidate site s is labeled as a vertex weight $u_s$ and vector u is the weights of all the sites. The network throughput on link $b=(y_1,y_2)$ from $y_1$ to $y_2$ is labeled as link weight $d_{y_1{y}_2}$ and matrix $D_{m\times m}$ is the weights of all the links. The diagonal of D are large values because data exchange in the same site can be considered negligible.

In this article, we define the operator .⁎ as array inner multiplication that multiplies arrays or matrices in an element-by-element way, which is different from matrix multiplication. Let $\tilde{\mathbf{u}}$ be the vector that satisfies $\mathbf{u}.⁎\tilde{\mathbf{u}}=\mathbf{1}$ where 1 is the vector whose elements are all 1's. Then the upper bound of total time spent for computation load is the sum of workload on every site over its processing capability:

$t_c={\mathbf{w}}^{T}X\tilde{\mathbf{u}}.$

Similarly, let ${\tilde{D}}_{n\times n}$ be the matrix that satisfies $D.⁎\tilde{D}={\mathbf{1}}_{m\times m}$ where ${\mathbf{1}}_{m\times m}$ is the matrix whose elements are all 1's. The transformation $E^{T}FE$ redistributes the communication load of $F_{n\times n}$ into an $m\times m$ matrix where element positions are corresponding to ${\tilde{D}}_{m\times m}$. The upper bound of total time spent on networks for data exchange load is the sum of workload on every link over its throughput:

$t_n=tr(E^{T}FE{\tilde{D}}^T),$

where the $tr(\cdot )$ function calculates matrix trace $tr(H_{n\times n})=\sum _{i=1}^n{h}_{ii}$. So the upper bound of total time is the sum of the computation and communication times:

$t=t_c+t_n.$

Energy Consumption

Energy consumption on mobile devices can be categorized according to hardware modules. The major categories are CPU, radio module (including WiFi and Cellular), display, audio device, GPS module, and vibration motor [153][245][286][289]. The components that involve modules, except CPU and radio, are hardware dependent components that have to run on the original mobile device and are not considered for offloading. Both CPU and radio power can be modeled as a linear model that consists of two parts: base consumption and dynamic consumption when hardware module is active [196][269]. The dynamic part of CPU power is proportional to the utilized processing capability according to [153][206][245][289]:

$P^{CPU}={\mathbf{1}}^{T}E(\mathbf{u}.⁎{\mathbf{c}}^{CPU}),$

where ${\mathbf{c}}^{CPU}$ is the coefficient vector for all sites, and the coefficients of nonmobile sites in ${\mathbf{c}}^{CPU}$ are 0's. Let's code E as e, then the dynamic part of radio module power is proportional to the outgoing packet rate [153][289]:

$D^{\prime }=D.⁎({\mathbf{1}}_{n\times n}-I).⁎({\mathbf{c}}^{radio}{\mathbf{1}}^T),$

$P^{radio}=\sum _{\forall l\in f_{E\to L}(\mathbf{e})}{d}_l^{\prime },$

where ${\mathbf{c}}^{radio}$ is the coefficient vector for all sites, I is the identity matrix, and $d_l^{\prime }$ is the element of $D^{\prime }$ corresponding to link l. The coefficients of nonmobile sites in ${\mathbf{c}}^{radio}$ are 0's. Let $P_{idle}^{CPU}$ be the static part of CPU power and $P_{base}^{radio}$ be the static power of radio module. Then the total power is the sum of the above four parts:

$P=P^{CPU}+P_{idle}^{CPU}+P^{radio}+P_{base}^{radio}.$

Execution Time

For a given task, bundle $x_i$ has an attribute $t_i$ indicating its computation time on smart phone. And edge $a_{ij}$ is associated with an attribute $d_{ij}$ indicating the transferred date size from bundle i to bundle j. These values can be measured or estimated from collected application and device data. Total time of running the task only on the smart phone is

$t_{phone}=\sum _{x_i\in X}{t}_i$

where data exchanges between bundles are not counted as they happen locally and cost little time compared to time of data exchange over the network. For a particular configuration c, offloading rate p [224] is defined as the proportion of offloaded task to all tasks in terms of computation time. The proportion of the task is the same as time proportion due to the same processing capability on the same mobile device $p(c)=(\sum _{x_i\in X_{cloud}}{t}_i)/t_{phone}$, and $p(c)$ satisfies $0⩽p(c)⩽1$. Then, the computation time on the smart phone is

$t_{computation}^{phone}(c)=\sum _{x_i\in X_{phone}}{t}_i=(\sum _{x_i\in X}-\sum _{x_i\in X_{cloud}})t_i=(1-p(c))t_{phone}.$

Assume the cloud is q times faster than the smart phone, thus the time consumption in the cloud is q times less than the time spent on the mobile device [281], which is $t_i^{cloud}=t_i/q$. The computation time in the cloud is

$t_{computation}^{cloud}(c)=\sum _{x_i\in X_{cloud}}{t}_i^{cloud}=\frac{1}{q}\sum _{x_i\in X_{cloud}}{t}_i=\frac{p(c)}{q}{t}_{phone}.$

Thus the total computation time is

$t_{computation}(c)=t_{computation}^{phone}(c)+t_{computation}^{cloud}(c)=(1-(1-\frac{1}{q})p(c))t_{phone}.$

A typical offloading process works as follows: Initially, the application starts on the smart phone and all components run locally. Then, the application may offload some components to a remote virtual machine. These offloaded bundles run in the cloud remotely. However, they need to communicate with the bundles resident on the smart phone. Thus, they have to exchange data through the network. Assume that the network bandwidth is w, then the network delay is the sum of delays in both data transfer directions, namely

$t_{network}(c)=\sum _{\genfrac{}{}{0ex}{}{x_i\in X_{phone}}{x_j\in X_{cloud}}}\frac{d_{ij}}{w}+\sum _{\genfrac{}{}{0ex}{}{x_i\in X_{cloud}}{x_j\in X_{phone}}}\frac{d_{ij}}{w}.$

In an ideal network environment, the total execution time for a given configuration c is the sum of computation time and network delay, that is,

$t(c)=t_{computation}(c)+t_{network}(c).$

The offloading benefit of execution time comes from the trade of $t_{computation}$ and $t_{network}$. The computation part saves execution time because the cloud processing capability is greater than that of the mobile device. However, the offloading has to pay for network delay, which counteracts the computation time saving. For computation-intensive applications whose computation time saving is much larger than the network delay, the offloading benefit is obviously seen.

Energy Consumption

Two hardware modules of the mobile device are involved in the energy consumption estimation: CPU and radio frequency (RF) module. Other modules like display, audio, GPS etc., are not considered because the components that interact with these modules have to run on the mobile device locally. The energy consumption on both CPU and RF modules can be further separated into the dynamic and static parts [269]. When the hardware module is in the idle state, the energy consumption is corresponding to the static part. When the hardware module is in the active state, more energy is consumed, which is corresponding to the dynamic part. Assume that the power of CPU in the idle state is $K_{CPU}^{sta}$ and the power of CPU in the active state is $K_{CPU}^{sta}+K_{CPU}^{dyn}$. The energy consumption of CPU is then

$P_{CPU}(c)=K_{CPU}^{sta}t(c)+K_{CPU}^{dyn}{t}_{computation}^{phone}(c).$

Similarly, let $K_{RF}^{sta}$ and $K_{RF}^{dyn}$ be the power of RF module in the idle and active states separately. The energy consumption on radio frequency module is

$P_{RF}(c)=K_{RF}^{sta}t(c)+K_{RF}^{dyn}{t}_{network}(c).$

Thus, the total energy consumption is

$P(c)=P_{CPU}(c)+P_{RF}(c).$

If offloading is not applied, only CPU consumes energy and its active period is the whole execution time. The total energy consumption of running tasks only on the smart phone is

$P_{phone}=(K_{CPU}^{sta}+K_{CPU}^{dyn})t_{phone}.$

The offloading influences energy consumption of the mobile device in two aspects. First, the mobile device may save energy because the mobile device does not pay for the energy consumption corresponding to the tasks that are offloaded and completed in the cloud. Second, the data exchanges between application components are now fulfilled by networking instead of local procedure invocation, which leads to energy cost for sending and receiving packets. Similar to the time benefit of offloading, the computation-intensive application may obtain an obvious energy benefit when computation tasks are offloaded as large CPU energy consumption is spared and network energy consumption is small.

Execution Time

When the network is unavailable, the application has to wait because the phone cannot send input to the cloud and cannot retrieve output from the cloud either. The application resumes the execution after the network becomes available again. The total execution time is prolonged according to the proportion of ρ, namely

$t^{\prime }(c)=\frac{t(c)}{\rho }.$

The offloading gives time benefit when $t^{\prime }(c)<t_{phone}(c)$. In an ideal network environment, $\rho =1$ and $t^{\prime }(c)=t(c)$. $t^{\prime }(c)$ rises to infinity when ρ decreases from 1 to 0. At some point, the benefit finally disappears. We define this point as a critical value of ρ for the time benefit,

${\rho }_{time}^{\prime }(c)=\frac{t(c)}{t_{phone}}.$

And the time benefit is

$\mathrm{\Delta }t(c)=t_{phone}(c)-t^{\prime }(c)$

when $\rho >{\rho }_{time}^{\prime }(c)$.

Energy Consumption

During the time $t^{\prime }(c)$, the computation time $t_{computation}^{\prime }(c)$ and network time $t_{network}^{\prime }(c)$ are the same as $t_{computation}(c)$ and $t_{network}(c)$, respectively, in an ideal network environment because computation and data transfer only work properly when an ideal network is available. The CPU active time period is the same as that in an ideal network model because the given task is the same. However, the CPU idle time period is the whole execution time that is different from that in an ideal network model. Thus, the energy consumption for CPU is

$P_{CPU}^{\prime }(c)=K_{CPU}^{sta}{t}^{\prime }(c)+K_{CPU}^{dyn}{t}_{computation}^{phone}(c).$

The RF module is active even when the network is unavailable because it continues scanning for the available network to resume connection. Thus, the active time period for the RF module is $t^{\prime }(c)-t_{computation}(c)$. The energy consumption for RF is

$P_{RF}^{\prime }(c)=K_{RF}^{sta}{t}^{\prime }(c)+K_{RF}^{dyn}(t^{\prime }(c)-t_{computation}(c)).$

Thus, the total energy consumption is

$P^{\prime }(c)=P_{CPU}^{\prime }(c)+P_{RF}^{\prime }(c).$

The offloading gives energy benefit if $P^{\prime }(c)<P_{phone}$. As ρ decreases, both $P_{CPU}^{\prime }(c)$ and $P_{RF}^{\prime }(c)$ increase. Similarly, the critical value of ρ for energy is defined as the point where the energy benefit disappears, i.e.,

$\begin{array}{ccc}\hfill & \hfill \hfill & {\rho }_{energy}^{\prime }(c)\hfill \\ \hfill & \hfill \hfill & =(K_{CPU}^{sta}+K_{RF}^{sta}+K_{RF}^{dyn})t(c)/(P_{phone}-K_{CPU}^{dyn}{t}_{computation}^{phone}(c)+K_{RF}^{dyn}{t}_{computation}(c)).\hfill \end{array}$

And the offloading energy benefit is

$\mathrm{\Delta }P(c)=P_{phone}(c)-P^{\prime }(c)$

when $\rho >{\rho }_{energy}^{\prime }(c)$.

Problem Formulation

When network availability ρ is greater than the larger of the ${\rho }_{time}^{\prime }(c)$ and ${\rho }_{energy}^{\prime }(c)$, both time and energy benefits are obtained. We define the critical value of ρ as

${\rho }^{\prime }(c)=\max \{{\rho }_{time}^{\prime }(c),{\rho }_{energy}^{\prime }(c)\}.$

The offloading problem with possible network unavailability is finding the application partition c to minimize ${\rho }^{\prime }(c)$:

$\min {\rho }^{\prime }(c)$

while both time and energy benefits exist, i.e., when

$\rho >{\rho }^{\prime }(c),$

where ρ is the current network availability estimated based on observations. The c satisfying (5.28) may not exist when ρ is too low. In this situation, the application should not offload any components to the cloud. The solution to (5.27) is the best partition that tolerates network unavailability, and it may give benefit when current network availability ρ gets worse.

Optimization Solution

The solution space for configuration x is $2^n$, which means it costs a lot of time to search for the optimal solution. To find a proper x within acceptable time, we propose an Artificial Bee Colony (ABC) [157] based algorithm. The colony consists of three types of bees: employed bees, onlooker bees, and scout bees. A bee that goes to a food source visited by it before is named an employed bee. A bee that waits in the dance area to make a selection of the food source is called an onlooker bee. And a bee that carries a random search to discover a new food source is named a scout bee. The food source is a possible solution x, and every bee can memorize one food source. It is assumed that there is only one employed bee for each food source. The memory of employed bees is considered as the consensus of the whole colony, and the food sources found by onlooker or scout bees merge into employed bees' memory in the algorithm. Assume that the number of employed bees is N and the number of onlooker bees is M $(M>N)$. And let MCN be the Maximum Cycle Number. The algorithm overview is shown in Algorithm 5.1.

In the first step, the algorithm generates a random initial population X $(cycle=0)$ of N solutions where the population size is the same as the number of employed bees. Based on this initial generation, the algorithm starts to evolve the generation in cycles. The evolution repeats until the cycle number reaches the limit MCN. The algorithm outputs the best solution, denoted as ${\mathbf{x}}_{best}$, ever found in all cycles.

In the cycle, three types of bees work in sequence. The details of various bees' actions are shown in Algorithm 5.2. Employed bees produce new solutions by two local search methods:

Flip when an employed bee randomly flips one element in the vector x.

Swap when an employed bee randomly flips two elements of different values in the vector x, which is equivalent to swapping two different elements in that vector.

Each employed bee evaluates the fitness of its original solution x, newly found ${\mathbf{x}}_{flip}$, and ${\mathbf{x}}_{swap}$ by (5.26). Then, each employed bee memorizes the best one of these three food sources and forgets the others.

Onlooker bees watch employed bees dancing, and plan the preferred food source. Onlooker bees record critical values of all food sources and calculate the probability for the $i\text{th}$ food source as follows:

$p_i=\frac{1/{\rho }^{\prime }({\mathbf{x}}_i)}{\sum _{j=1}^N(1/{\rho }^{\prime }({\mathbf{x}}_j))}.$

Intentionally, the lower the food source's critical value, the more likely the onlooker bee would like to go. The onlooker bees choose the food source y randomly according to its probability. Since $M>N$, several onlooker bees may follow the same employed bee and choose the same food source. Then each onlooker bee applies the same local search methods used by employed bees previously to explore new neighbor solutions, and picks the best one of the three. After all onlooker bees update their solution, each employed bee compares its solution with its followers' solutions, and picks the best one as its new solution.

In our algorithm, only one scout bee is used. This scout bee randomly generates a vector z and compares z to the worst solution of employed bees. If this randomly generated z is better than the worst solution of employed bees, the corresponding employed bee memorizes this new solution and forgets the old one.

Evaluation and Tuning

In this section, we evaluate ABC based partition algorithm, including algorithm tuning and impact of different mobile applications and the cloud. We evaluate our model and algorithms in MATLAB.

We generate 200 random application graphs as a base evaluation data set. The default parameter settings are shown in Table 5.2. We use a set of typical energy parameters K for a phone according to [269]. The cloud–phone processing ability ratio q varies in a large range from previous work [274][281]. We pick a medium value from the possible range as the default value and evaluate its impact to algorithm in Section 5.2.3. We evaluate the algorithm based on three aspects: bee colony, different applications, and cloud–phone relation.

Table 5.2

Default parameter setting

Parameter		Default value
Application	m	10
	n	8
Cloud [274][281]	q	30
Phone [269]	$K_{CPU}^{sta}$	2.5
	$K_{CPU}^{dyn}$	5
	$K_{RF}^{sta}$	1.25
	$K_{RF}^{dyn}$	1.25
Algorithm	N	3
	M	5

Bee Colony and Algorithm Tuning

This experiment is based on 200 random application graphs (t and D). These application graphs are randomly generated, and at least one configuration of each graph is guaranteed to obtain both time and energy benefit in an ideal network environment. We evaluate the proposed algorithm performance with respect to different bee colony size. The results are shown in Fig. 5.5. The x-axis represents how many iterations the algorithm needs to reach ${\mathbf{x}}_{best}$, and the y-axis represents how many cases are needed to reach the solution of corresponding iterations. From the figure, we may draw the following guidelines for algorithm tuning:

•  By increasing the onlooker bee number, the algorithm shows better convergence rate. For the same employed bee number (N), the more onlooker bees there are, the fewer iterations are obviously required to reach the optimal solution in all three situations ($N=2,3,4$).

•  While increasing the employed bee number improves convergence rate, the improvement is not as obvious compared to increasing the onlooker bee number. For the same onlooker bees of $M=3$ (Fig. 5.5B, Fig. 5.5D), $M=4$ (Fig. 5.5C, Fig. 5.5G), and $M=7$ (Fig. 5.5F, Fig. 5.5H), the cases that have more employed bees have slightly better performance improvement, which is not as obvious as the improvement given by increasing onlooker bees. For $M=4$ figures, more than 0.05 cases reach the optimal solution in 7 iterations in Fig. 5.5C while there are only 0.05 cases that reach a solution in 7 iterations, which means more cases reach a solution in less than 7 iterations, in Fig. 5.5G. Similar phenomenon is found for $M=3$ and $M=7$ figures.

•  For the same total numbers of employed and onlooker bees, the algorithm prefers more onlooker bees slightly. For the same total bees of $N+M=6$ (Fig. 5.5C, Fig. 5.5D) and $N+M=8$ (Fig. 5.5E, Fig. 5.5G), we can see that the overall performance is almost the same. But the iterations needed to get optimal solutions in the cases that have more onlooker bees are slightly concentrated on some iteration numbers. For $N+M=6$, the iterations in Fig. 5.5C are concentrated demonstrated by a higher summit at iteration 4, while they are diversely distributed from 1 to 8 in Fig. 5.5D. A similar situation occurs for $N+M=8$.

Application Impact

To evaluate the algorithm performance for different applications, three experiments are done for varying component number, unmovable component proportion, and computation–communication ratio separately. The experiment result for different component number is shown in Fig. 5.6. For the same bee colony, the iterations to find the solution increase along with the component number. For the large applications that have many components, the algorithm may use a large bee colony to assure small number of iterations.

We evaluate the impact of unmovable component proportion of application in the second experiment, and the result is shown in Fig. 5.7. From the figure, we find that more iterations are required to get the solution when the movable component number increases. The trend is very like that in Fig. 5.6, which implies that the unmovable component number does not play a significant role in the algorithm performance. This is because the algorithm always considers the movable components and ignores the unmovable component when generating new solutions in each cycle. The total component size increase in Fig. 5.6 leads to the increase of movable component number, which is like what this experiment does in Fig. 5.7. Besides, we also found in this experiment that a higher movable proportion results in the robust solution that can work under low network availability ${\rho }^{\prime }(c)$ situations. This is because the high movable proportion provides more candidate partition options so that a more robust solution may be achieved.

We generate another two sets of application graph data for different computation load. The data sets used in previous experiments are used as the reference data set. Then we adjust the computation task to half and double of the reference data set in the application graph generation process. The network task remains the same, thus the computation–communication ratio is adjusted to half and double in the new data sets. The experiment results for these three data sets are shown in Fig. 5.8. From the figure, we can see that the iterations, distributed at $2,3,4,5$, and 6, are almost the same, which implies the computation proportion of the given task does not influence the algorithm performance. This is because the computation proportion in the task influences the time and energy benefits in the same direction. In the experiment, we also find that the computation proportion impacts the ${\rho }^{\prime }(c)$, because a larger computation proportion leads to a larger offloading benefit and the possible solution is more resistant to network unavailability.

Cloud Impact

We evaluate the algorithm performance under different cloud speedup ratios shown in Fig. 5.9. The figure shows that the iteration number does not depend on the cloud processing capability. The cloud processing capability influences the execution time considered in the algorithm, which is similar to the computation proportion impact. And similarly, the higher cloud processing capability results in a more robust partition configuration.

Application Graph

A modern mobile application is usually guided by component oriented design. Components provide functionality via interfaces and may, conversely, consume functionality provided by other components [277]. The application can be presented as a graph $G_{app}=(C,E)$ where the vertexes are the components and the edges show the interaction between components.

To be extensible, the application graph is not limited to present only one application. The application graph can be extended to contain several applications and even the connections between applications.

Surrogate Network

In a multisite service composition scenario, some computation workload is offloaded from the original mobile device and distributed onto the chosen surrogate sites from candidate sites. The original site and its candidate sites form an egocentric network $G_{sur}=(S,L)$, where the node is the site and the link is the network connection between sites.

Component–Surrogate Mapping

The service composition mapping is a mapping from the application graph $G_{app}$ to a surrogate network $G_{sur}$, where vertexes are mapped to nodes and the edges are mapped to links correspondingly. Let matrix X present this mapping, whose element $x_{ij}$ is set to either 1 when component i is assigned to site j or 0, otherwise. Matrix X has the following properties:

1.  Let n be the component number, $n=|X|$, and m be the candidate site number, $m=|Y|$. Then, E is $E_{n\times m}$. The relation of m and n is not strict, which means $m>n$, $m<n$, and $m=n$ are all valid.

2.  The mapping is also not strict, which means several components may be mapped to the same surrogate site and some surrogate site may not host any components. However, each component in the application is assigned to exactly one site, thus, there is one and only one 1 in each row of E, i.e., $\sum _{j=1}^n{e}_{ij}=1$ for every row i.

3.  In a mobile application, some components have to be assigned to particular sites due to application requirements. For example, human–machine interaction components and sensor components have to be put on the original mobile device because they use mobile device hardware that is not available on surrogate sites. This requirement enforces the positions of some 1's in some rows of E to be predefined and not to be moved. These rows are put at the bottom of E. Except for these rows, the rest of E is the effective matrix $E_{\tilde{n}\times m}$, which corresponds to the movable components.

Based on E, four more mappings can be defined for easy expression in the following sections. Mapping $f_{C\to S}$ implements a similar function as E, which maps component i to site j: $f_{X\to Y}(i)=j$, $\forall e_{ij}=1$, $e_{ij}\in E$. Mapping $f_{Y\to X}$ is the reverse mapping of $f_{X\to Y}$, which given site j outputs a set of components $\{i_1,i_2,\dots ,i_k\}$ coded as a vector i. Besides, mappings can also be defined between A and B. Mapping $f_{A\to B}$ maps edge $a=(i_1,i_2)$ to link $b=(f_{X\to Y}(i_1),f_{X\to Y}(i_2))$. And similarly to $f_{Y\to X}$, mapping $f_{B\to A}$ maps a link to a vector of edges.

Decision Points

Decision points are the moments when the service composition topology reconfiguration decisions are made. At these moments in Fig. 5.11, the Monitor triggers the Service composition topology reconfiguration to generate a service composition topology. The moments are decided by the Monitor that is always observing the Infrastructure and the Mobile application states. The Monitor can trigger decisions periodically according to a predefined period Δt.

The decision points are a sequence that starts from the time when the application starts to the time when the application ends, $T=\{0,1,2,\dots ,N-1\}$. In some scenarios, the application termination time is not expected and the sequence is an infinite sequence, $T=\{0,1,2,\dots \}$.

Measures

The Monitor measures the Infrastructure states. The node computation capability and link throughput are labeled on the surrogate network, which transforms $G_{sur}$ into a weighted graph. The available computation capability on a candidate site s is labeled as a node weight $u_s$ and vector u collects weights of all sites. The network throughput on link $l=(s_1,s_2)$ from $s_1$ to $s_2$ is labeled as link weight $d_{s_1{s}_2}$ and matrix $D_{n\times n}$ contains weights of all links. The diagonal of D has large values because the delay in the same site can be considered negligible.

The above measures may be continuous variables. They are manipulated by normalization and quantization to make them into discrete states. A relatively large value is picked and the observation is scaled to be in $[0,1]$. Quantization precision determines the size of state space. The evaluation shows the results of different state space. The state space is denoted as S.

Service Composition Topology

The service composition topology is the effective component surrogate mapping $X_{\tilde{m}\times n}$. Each mapping corresponds to an action that enforces the mapping. The size of service composition topology space is $n^{\tilde{m}}$ since each component has n choices and there are $\tilde{m}$ components that make their choices independently. Let A be the corresponding action space from which the Service composition system in Fig. 5.11 acts – picking and enforcing the mappings. The output of the Service composition topology reconfiguration is a service composition topology. If the outputted service composition topology is different from the old one, reconfiguration is needed. “Reconfiguration” means that the components in the old service composition topology should be moved properly to satisfy the new service composition topology, which is fulfilled by the Service composition executor.

Observation Learning

The Service composition topology reconfiguration in Fig. 5.11 counts the historical states and actions, and estimates the state transition probability $p(j|i,a)$ where $i,j\in S$ and $a\in A$. The transition probability satisfies $\sum _{j\in S}p(j|i,a)=1$. This probability is updated at decision points. The Service composition topology reconfiguration maintains a buffer that keeps the count for valid observed states and the count of historical actions. At each decision point, it gets the current state j from the Monitor and, the last state i and the last topology decision a from its buffer. Then it calculates the state transition probability for every pair of states with every action. This transition probability that comes from the recent history is used to predict the probability of transition for the near future Δt period assuming the transition probability stays steady in a short time period.

Service Composition Objective

One major service composition goal in mobile cloud computing is to save mobile device energy. Following the same procedures of equations from (5.4) to (5.7), the total power is calculated through the following equations:

$P^{CPU}(i,a)={\mathbf{1}}^{T}E(\mathbf{u}.⁎{\mathbf{c}}^{CPU}),$

$D^{\prime }(i)=D.⁎({\mathbf{1}}_{n\times n}-I).⁎({\mathbf{c}}^{radio}{\mathbf{1}}^T),$

$P^{radio}(i,a)=\sum _{\forall l\in f_{A\to B}(\mathbf{e})}{d}_l^{\prime },$

$P(i,a)=P^{CPU}+P_{idle}^{CPU}+P^{radio}+P_{base}^{radio}.$

When a topology is picked at a decision point, a reward value is calculated to indicate how good the decision is. The reward of choosing action a at state i depends on not only state i and action a but also the next state j. The reward is

$r(i,a)=\sum _{j\in S}r(i,a,j)p(j|i,a),$

where the reward of transition from state i to state j with action a is the expected delta power between two states i and j with the same action a, and

$r(i,a,j)=P(j,a)-P(i,a).$

Model Formulation

The service composition topology reconfiguration process is modeled as a five element tuple:

$\{T,S,A,p(\cdot |i,a),r(i,a)\}.$

This is a Markov decision process [188].

Topology Reconfiguration Policy

The service composition reconfiguration policy is a function π that maps states to actions $\pi :S\to A$. The function π can be stored in memory as an array whose index is the state and whose content of each element is the corresponding action.

Let $Y_t$ and ${\mathrm{\Delta }}_t$ be the system state and the picked action at decision point t, ${\mathrm{\Delta }}_t=\pi (Y_t)$. The sequence $L(\pi )=\{Y_0,{\mathrm{\Delta }}_0,Y_1,{\mathrm{\Delta }}_1,\dots \}$ is a stochastic process depending on π. Let $R_t(\pi )=r(Y_t,{\mathrm{\Delta }}_t)$, then the sequence $\{R_0(\pi ),R_1(\pi ),\dots \}$ is a reward process depending on π.

Finite Decision Points

At any decision point, the current period reward could be used as a decision goal, which, however, is shortsighted because the maximum current period reward does not guarantee that the sum of rewards in all periods is maximum. To make a proper decision on service composition topology, the total rewards of N periods should be considered as the goal:

$V_N(Y_0,\pi )=\sum _{t=0}^{N-1}{\beta }^t{R}_t(\pi )=\sum _{t=0}^{N-1}{\beta }^{t}r(Y_t,{\mathrm{\Delta }}_t)$

(5.37)

where β is the confidence index. As the N periods' rewards are estimated future rewards, the degree of confidence on the reward sequence $R_t(\pi )$ decreases with t. The confidence index presents this decreasing confidence trend. The service composition topology reconfiguration problem is to find the policy π that maximizes $V_N(Y_0,\pi )$.

Let $u_t$ be the reward sum from decision point t to N. There is backward recursive relation between $t+1$ and t:

$u_t(i_t,a_t)=r(i_t,a_t)+\beta \sum _{j\in S}p(j|i_t,a_t)u_{t+1}(j)$

(5.38)

$=\sum _{j\in S}p(j|i_t,a_t)(r(i_t,a_t,j)+\beta u_{t+1}(j))$

(5.39)

where $i_t\in S$ is the state at time t. Equation (5.38) shows the reward sum from time t to N consists of the current period reward and the β scaled reward sum from time $t+1$ to N.

Let the superscript notation ^⁎ represent the maximum value of the corresponding variable. To get the maximum rewards, the backward recursive relation formulation is

$\begin{array}{cc}\hfill & u_t^{⁎}(i_t)=\hfill \\ \hfill & \underset{a_t\in A}{\max }\{r(i_t,a_t)+\beta \sum _{j\in S}p(j|i_t,a_t)u_{t+1}^{⁎}(j)\}\hfill \end{array}$

(5.40)

Algorithm 5.3 shows the algorithm to calculate the policy π. The main body of the algorithm repeats equation (5.40) N times. In the algorithm, line 5 and line 6 could share the intermediate result of equation (5.38), which means $r(i_t,a)+\sum _{j\in S}p(j|i_t,a)u_{t+1}^{⁎}(j)$, $\forall i_t\in S$ is calculated only once but used in both operations.

The algorithm requires storage for two arrays indexed by state, v and f. The ith element of the array v is $u^{⁎}(i)$ where $i\in S$. The ith element of the array f is an action ${\pi }^{⁎}(i)\in A$ that is the optimal action corresponding to state $i\in S$. The array f hosts one instance of π. The length of both v and f is $|S|$.

At the end of the algorithm, v contains the discounted sum of the rewards to be earned on average from the corresponding initial state i: $V_N^{⁎}(i)=\mathbf{v}(i)=u_0^{⁎}(i)$ where $i\in S$. The policy is $\pi =\{{\pi }_0^{⁎},{\pi }_1^{⁎},\dots ,{\pi }_{N-1}^{⁎}\}$ for N decision points. The array f contains ${\pi }_0^{⁎}$ when the algorithm ends. The action ${\pi }_0^{⁎}(Y_0)=\mathbf{f}(Y_0)$ is the action that should be performed at the current decision point.

Infinite Decision Points

The previous discussion of the finite horizon scenario can be extended to the infinite horizon scenario. The objective function for the infinite horizon scenario can be achieved by pushing N to ∞ in equation (5.37), i.e.,

$V(Y_0,\pi )=\underset{N\to \infty }{\lim }{V}_N(Y_0,\pi ).$

(5.41)

Similarly, the problem is to find the policy π that maximizes the total rewards $V(Y_0,\pi )$. In the infinite horizon scenario, the recursive relation (5.38) is generalized by removing iteration subscript:

$u(i,a)=r(i,a)+\beta \sum _{j\in S}p(j|i,a)u(j).$

(5.42)

Similarly, the recursive relation (5.40) changes to

$u^{⁎}(i)=\underset{a\in A}{\max }\{r(i,a)+\beta \sum _{j\in S}p(j|i,a)u^{⁎}(j)\}$

(5.43)

which means the $u^{⁎}(i)$ achieves to the maximum total rewards.

Algorithm 5.4 shows the algorithm to calculate the policy π. Compared to Algorithm 5.3, the iteration termination condition is changed to comparing the vector norm and tolerance. ε indicates the tolerance for the converging state. In line 6, $\Vert \cdot \Vert$ is a vector norm that could be any type of $L_p$: $L_1$, $L_2$, or $L_{\infty }$ norm. In addition, a local improvement loop is added inside the main iteration. The sequence $\{m\}$ consists of nonnegative integers that are used in each iteration as improvement depth; $\{m\}$ could be generated in many ways. For example, it may be constant, i.e., $m_n=m$, or it may get more precise along with the iteration sequence number, i.e., $m_n=n$. When the algorithm ends, the policy is ${\pi }_{n+1}$ that is stored in the array f.

The column vector $\mathbf{r}(\pi )$ and matrix $P(\pi )$ are defined to simplify expressions in the algorithm. The ith element of vector $\mathbf{r}(\pi )$ is $r(i,\pi (i))$ where $i\in S$. The size of $\mathbf{r}(\pi )$ is $|S|$. The $(i,j)$th element of matrix $P(\pi )$ is $p(j|i,\pi (i))$ where $i,j\in S$. The size of $P(\pi )$ is $|S|\times |S|$. In the algorithm, lines 13 through 15 repeat the same operations as lines 3 to 5. Line 8 is the vector version of equation (5.42). Lines 5 and 15 are the vector version of equation (5.43). Lines 3 and 5 share the intermediate computation result. Similarly, lines 13 and 15 also share the intermediate computation result.

Large State Space

To make a more accurate and agile decision, the real world measures usually lead to a large state space in Section 5.3.2. The large state space size results in a long responding time. To mitigate the response time in a large state space situation, MapReduce could be used. This section discusses the conversion from Algorithm 5.3 and Algorithm 5.4 to MapReduce algorithms.

Algorithm 5.5 and Algorithm 5.6 show the MapReduce algorithms for the finite horizon scenario. The input to the mapper function, which is also the output of the reducer function, is the state id i and an object Q that encapsulates the state information defined in Section 5.3.2. Besides encoded state information, two components $Q.v$ and $Q.f$ corresponding to the arrays v and f are also included in the state object. Moreover, a component $Q.p$ corresponding to the state transition probability obtained in Section 5.3.2 is included in the state object as well. The state object is passed from the mapper to the reducer for calculating Equation (5.39). This is accomplished by emitting the state data structure itself, with the state id as a key in line 2 of the mapper. In the reducer line 3, the node data structure is distinguished from other values.

The mapper function associates the current state with all backward states. The reducer function aggregates the reward sum of all forward states according to Equation (5.39), which is categorized by action. Then it picks the maximum reward sum and the corresponding action as the current reward sum and action according to Equation (5.40).

It is apparent that Algorithm 5.3 is an iterative algorithm, where each iteration corresponds to a MapReduce job. The actual checking of the termination condition must occur outside of MapReduce. Typically, execution of an iterative MapReduce algorithm requires a non-MapReduce “driver” program, which submits a MapReduce job to iterate the algorithm, checks to see if a termination condition has been met, and if not, repeats [187].

As presented in Section 5.3.3, just as the infinite horizon algorithm is obtained by extending the finite algorithm, the MapReduce based algorithm for the infinite horizon scenario can be obtained by extending the MapReduce based finite horizon algorithms. The mapper function could be used without modification in the infinite horizon algorithms. The improvement loop in the infinite horizon algorithm can be achieved by repeating lines 8 through 12 $m+n$ times. Besides the modification on the reduce function, a modification on the driver is required. The iteration termination condition in the driver is changed from a fixed number to a comparison of norm and coverage tolerance.

Evaluation Cases and Default Parameter Setting

We generate 200 test cases of the proposed model in Section 5.3.2. To make the mobile device profile based on solid ground, we pick up the mobile device profiling parameters obtained in a previous work [289]. The maximum dynamic power consumption values in each mobile CPU and RF components, $c^{CPU}$ and $c^{radio}$, are normally distributed with mean of 4.34 and 710, and variance of 1.46 and 48, respectively. The static power consumption values in each mobile CPU and RF components, $P_{idle}^{CPU}$ and $P_{base}^{radio}$, are normally distributed with mean of 121.46 and 20, and variance of 9.20 and 4.86, respectively. To estimate the surrogate infrastructure, we pick up the cloud profiling parameters obtained in a previous experience report [81]. The CPU utility is uniformly distributed from $40\text{\%}$ to $90\text{\%}$. The network throughput is uniformly distributed from $10\text{\%}$ to $40\text{\%}$ after normalization.

Besides the mobile device and cloud profiling, we use the default algorithm parameter values (see Table 5.3). These values may be changed in the experiments to show their impact on the algorithms.

Table 5.3

Default parameter setting

Parameter		Default value
application and cloud	$\tilde{m}$	8
	n	5
	|S|	100
finite horizon	N	3
	β	0.7
infinite horizon	L p	L 2
	m n	n
	ε	1
large state space	|S|	1000

Experiments on Finite Horizon

We first evaluate the norm of the reward sum trend along with the variance of forecast decision point number N for different confidence index β. Since the reward sum range of test cases vary, we normalize the reward sum against the maximum reward sum in the evaluation. The experiment result is shown in Fig. 5.12. The trend in the figure shows that the reward sum approaches the maximum reward sum as N increases. The approach follows a monotonically increasing trend. When the reward sum approximates a stable value (e.g., N is greater than 8 for $\beta =0.7$), we can claim that N is large enough to be considered as an infinite horizon scenario.

In Fig. 5.12, when the confidence index is small ($\beta =0.5$), the reward sum converges after a short period ($N=4$). When $\beta =0.7$, the value for the reward sum to converge ($N=8$) is twice as that for $\beta =0.5$. The higher the confidence index, the larger the decision point number to make the expected reward sum converge. Since the N values for convergence are related to the iteration times in the infinite scenario, we can infer that the smaller the confidence index, the fewer iterations are required in the infinite horizon scenario.

We then evaluate the norm of the reward sum trend along with the variance of confidence index β. The experiment result is shown in Fig. 5.13. In the figure, the reward sum is normalized against the values of the default confidence index. The reward sum increases monotonically along with the confidence index. The higher the confidence index, the more reward values are added to the total considered reward, which leads to the higher norm value of the reward norm. The reward sum increases sharply when the confidence index approaches 1, which leads to a linear proportional relation between the reward sum and the forecast period N or an infinite horizon reward sum calculation failure. When the confidence index is small, the reward sum is steady because the reward sum mainly consists of rewards in several near future forecast periods.

Experiments on Infinite Horizon

In the infinite horizon algorithm, the main loop of the infinite horizon algorithm terminates using a condition controlled by the reward sum tolerance. We experiment with different tolerance and their corresponding main loop iteration cycles and show the results in Fig. 5.14. In the figure, the x-axis ranges from 1 times ε to 50 times ε, and the y-axis is the iteration cycle number that is normalized against the cycle number of the default ε situation. Obviously, the higher the tolerance, the sooner the iteration ends. A large tolerance means that larger reward sum values fall into the area of considered converged values, so fewer iterations may let the reward sum trend go into that area and terminate the iteration cycle. We also illustrate the reward sum of different ε in Fig. 5.15. Here, similar to Fig. 5.14, the x-axis ranges from 1 times ε to 50 times ε, and the y-axis is the reward sum that is normalized against the cycle number of the default ε situation. We can see that the reward sum decreases when the tolerance increases, which demonstrates the that the coverage area is enlarged by the large tolerance. In addition, the reward sum decreases proportionally to the tolerance variance, which is expected because the convergence area is enlarged by turbulence proportionally.