![](https://csdnimg.cn/release/download_crawler_static/15826684/bg4.jpg)
4350 Fan et al.: Adaptive Application Component Mapping for Parallel Computation Offloading in Variable Environments
solving the pathfinding problem. Section IV shows the simulation results and the evaluations
of our algorithm. Our work is concluded in Section V.
2. Graph Mapping Model for Application Component Multi-partitioning
An application running in a mobile terminal can be expressed as an undirected weighted graph
[15] according to its program structure. The graph is called application component graph
(ACG), which consists of vertices and edges. The vertices denote the components of the
application with a certain granularity, such as classes, objects, modules, interfaces, functions
or threads. Additionally, the vertices are from two categories: offloadable vertices or
unoffloadable vertices. The formers are the ones that can be executed either in the terminal or
in any one of the outside computation devices, whereas, the latter are the ones that can only run
in the terminal, such as the components which operate the terminal's I/O hardware or are in
charge of user interfaces, etc. An edge connecting two vertices in the ACG represents the
communication between the two components that the two vertices correspond to. The weight
of a vertex is defined as the amount of the computation that the corresponding component
generates, and the weight of an edge is defined as the amount of data that needs to be
transmitted between the two corresponding components that it connects with, if the two
components are allocated to different computation devices in parallel computation offloading.
We use
to express the ACG of an application
with vertices and edges.
is the vertex set of
.
is
the subset including all offloadable components, and
is the subset including all
unoffloadable ones.
is the edge set of
. The weight sets of
and
are denoted by
and
, which contain the
amount of computation of each computation device and the amount of data transmitted
between two components if allocated differently, respectively.
In order to structurally express the relationships among vertices and edges in an ACG, an
upper triangular matrix
with rows and columns is employed to represent the
existences and weights of edges between vertices.
represent the edge between
and
.
if or there is no edge between
and
, whereas,
if
and there is an edge between
and
. Here, the value of
is equal to the weight of the
edge between
and
. As an instance, an ACG is shown in 0, which consists of 5
vertices and 7 edges, and its
is
(1)
In the scenarios of the mobile terminal-centric ambient intelligence [16] developed by IoT
technologies, the topology of the mobile terminal and its surrounding computation devices is
actually a star network, where the computation devices are connected with the terminal via
heterogenous networks, and the terminal is the center of the network. In the same way, the star
network can be also expressed as an undirected weighted graph, called computation device
graph (CDG), where the vertices denote the terminal and the computation devices, and the