Energy-Aware Service Composition Algorithms for Service-Oriented Heterogeneous Wireless Sensor Networks

Abstract

Wireless sensor networks are evolving with increasingly device heterogeneity, while the problem of effectively composing the platform-specific functionalities provided by heterogeneous sensor nodes to achieve specific goals still remains a challenge. Because of the constrained resources and unreliable communication in sensor networks, traditional service composition techniques in web services with adequate resources are insufficient. In this paper, focusing on the limited energy of sensor nodes, we propose an energy-aware service composition framework for developing various applications in heterogeneous wireless sensor networks. With both the energy-aware metrics: energy-aware load-balancing factor and overall energy consumption, we formulate the process of energy-aware sensor service composition into a combinatorial optimization problem; furthermore, an improved discrete particle swarm optimization (IDPSO) algorithm with inertia weights adjustment and extreme perturbation scheme is proposed to solve the combinatorial optimization problem. The experiment results have shown that the performance of the service route given by IDPSO is approximately equal to the best service route searched out by the exhaustive algorithm. Meanwhile, our proposed energy-aware service composition method is able to reduce the energy consumption and prolong the lifetime of the sensor network when providing stable service composition for various applications.

1. Introduction

In recent years, wireless sensor networks (WSNs) are evolving with new features such as larger scale, higher device heterogeneity and the capability of supporting multiple applications [1]. For example, a WSN deployed for intelligent buildings contains a variety of different sensors, for example, video, audio, temperature, humidity, smoke, and light sensors, and it should be able to support video surveillance, accident location and tracking, environmental monitoring, and other applications. For example, as is shown in Figure 1, the target identification and tracking application is provided by combining acoustic sensing, target localization, target identification, and camera-based target tracking functionalities. In such environments, the device heterogeneity presents a great challenge for application programmers because it requires them to master the details of the underlying software and hardware platform [2, 3]. In order to develop diverse applications rapidly and efficiently, it is really necessary to provide programmers with adequate abstractions of the low-level platform-specific software and hardware details.

Figure 1

Collaboration among heterogeneous nodes for an application.

Existing service-oriented architecture (SOA) [4–6] has been considered as a promising means to provide higher level abstraction for the development of applications, and it helps enable applications to be platform-independent and adapt to network dynamics. Among the SOA technologies, service composition, that is, the process through which kinds of complex applications are developed by composing a set of primitive services with various restrictions (e.g., QoS [7], fault-tolerant [8]), has been well studied in the context of web services.

Service composition in wireless sensor networks is faced with more difficulties and has gradually gained attention. The existing service models and composition techniques for web services have limitations when directly applied to wireless sensor networks. The main reason is that the software-based web services are often supported with adequate resources. However, the service capabilities of the heterogeneous sensor nodes are affected by their intrinsic properties, such as the limited and dynamic computational ability, power supply, and residual memory and communication bandwidth. Meanwhile, too many service invocations in the same node will easily cause excessive computation and storage usage, energy consumption, and network traffic. More seriously, it will exhaust the battery of the involved service nodes and then create the energy holes that split the network into isolated islands. Therefore, it is critical to bind service requests to sensor nodes according to their available resources and current service load.

Considering that the network lifetime and energy spent at the node and system level are much important in WSNs, the objective of the work presented herein is to propose an energy-aware service composition framework for sensor services in the service-oriented heterogeneous wireless sensor networks.

With this service-oriented approach, nodes’ sensing, data processing and transmission, and actuation capabilities are encapsulated as a collection of services. Conceptually, a service provided by a sensor node can be understood as a computational component that inherits the specific contexts of the related physical node. Meanwhile, a service can be provided by multiple different sensor nodes, although each service implementation may have different spatial, temporal, and QoS characteristics.

Then, based on resolving the application request into a workflow graph, we are able to develop new applications rapidly by combining a suitable set of available service nodes with service composition. Here, the process of choosing the appropriate set of service nodes is called service routing. Within the process of service routing, not only the service functionalities provided by the candidate node is concerned, but also its available energy is checked. We have exploited two different energy-aware metrics: energy-aware load-balancing factor and overall energy consumption. Based on both the metrics, we formulate the process of energy-aware sensor service routing into a combinatorial optimization problem. Considering that the traditional exhaustive algorithm suffers from the high computational complexity, we then propose an improved discrete particle swarm optimization algorithm to compute the optimal service route. In summary, we make the following contributions. (1)

In Section 3, we provide a framework to model the problem of energy-aware sensor service composition for developing sensor network applications.

(2)

In order to optimize for the energy balance and total energy minimization goals, we formulate the energy-aware sensor service composition process as a combinatorial optimization problem.

(3)

To deal with the high computational complexity of exhaustive algorithm, we propose an improved discrete particle swarm optimization algorithm to find out the approximately optimal service route effectively.

With our proposed methods, the workload of the service nodes is well balanced and the total energy cost is minimized as much as possible. Therefore, our proposal is able to reduce the energy consumption and prolong the lifetime of the sensor network when providing stable service composition for various applications.

2. Related Works

In recent years, service composition for pervasive computing such as distributed real-time system, MANETs, CPSs, and WSNs has been received more and more attention. In this section, we will discuss the related works on modeling and composition of services in these systems.

2.1. Related Works of Service Composition for Pervasive Computing

Excepting for web services, service composition for pervasive computing has also been the subject of intense study over the past several years. Brønsted et al. [9] discussed that service composition mechanisms for pervasive computing should address the following four goals including context awareness, managing contingencies, leveraging heterogeneous devices, and empowering users. Their analysis suggests that there are indeed opportunities and reasons to focus on service composition for pervasive computing. The work of Kalasapur et al. [10] presented a dynamic service composition mechanism in pervasive computing. They modeled and represented resources as services, maintained a repository of service graphs, and dynamically combined multiple basic services into complex services. However, the scheme of context-aware (e.g., residual energy and location) service selection for dependable service composition was not deeply studied in this paper.

The work of Estévez-Ayres et al. [11] presented a model for QoS-aware service composition in distributed systems with real-time and fault-tolerance requirements. However, they selected out the appropriate service nodes mainly based on their QoS properties, but it is not enough for dependable service provision in WSNs. The work developed by Wang [12] studied a dependable service composition problem in MANET. They proposed to achieve dependable service composition by taking the mobility prediction of the service providers into consideration. The work of Jiang et al. [13] proposed a new service composition and recovery framework designed to achieve minimum service disruptions for mobile ad hoc networks. However, the common WSNs do not have the mobility characteristics; moreover, energy issues should be more important for service composition because of the fewer available resources in sensor nodes.

In [14], the authors proposed OSGi-based service architecture for Cyber-Physical Home Control Systems, which supports service-oriented control methods. Users can control appliances in the physical environment by intuitive operation through a virtual home on the network. In [15], Huang et al. developed an ontology model for physical entity specification. Based on this model, OWL-S is extended to accurately model the characteristics of service providers in the context of cyber-physical worlds. These proposed SOAs in CPS are helpful for our studies in WSNs; however, the WS standards such as OWL and XML exploited in CPS are too much complex for the low-capacity sensor nodes.

2.2. Related Works of Service Composition for WSNs

In recent years, some researchers have begun to focus on service composition for service-oriented wireless sensor networks. In order to handle the device heterogeneity, some kinds of service-oriented architectures and middleware have been proposed for a flexible service provision. In [5], the authors presented a service-centric WSN model, which focused on services provided by a WSN and viewed a WSN as a service provider. In [6], the authors presented a service-oriented, flexible, and adaptable middleware for QoS configuration and management of wireless sensor networks. Both proposed service-oriented models are meaningful for our studies; however, no details on automated service composition are studied in them.

Amundson et al. [16] have developed OASiS, which is an object-centric, service-oriented programming model and middleware for ambient-aware sensor network applications; however, it did not include automated composition with cost measures. In [17], the authors introduced the WSN-SOA suite which enables SOA-based communications in networks of low-capacity sensors. Service-oriented middleware TinySOA [18] allows programmers to access wireless sensor networks from their applications by using a simple service-oriented API via the language of their choice. However, both the studies did not address automatic composition construction. In [19], the authors presented a Distributed Operating System (DOS) based on the service-oriented architecture (SOA) to manage all embedded devices in a home network at high level of interoperability. Another service provision middleware, Servilla[20], enables applications to be both platform independent and energy efficient by facilitating in-network collaboration among heterogeneous devices. With Servilla, the available energy in the candidate nodes has been taken into account in the service binding process; however, the common service composition model and service selection algorithm had not been presented.

Few approaches have been proposed for modeling service composition problem and the related resolution algorithms. In [21], the authors provided service composition solutions during a persistent query's lifetime such that the involved routing update cost and transmission cost are minimized. Another approach [22] proposed a probabilistic context-free grammar (PCFG) based modeling technique to construct service compositions. In [23], the authors proposed a policy-aware sensor service composition framework, which can automate the process of combining simple sensor services into larger ones with pre-specified policies. To the best of our knowledge, energy-aware automatic service composition in our study is novel in the sensor network domain.

3. Mathematical Formulations for Energy-Aware Service Composition

3.1. Network and Application Model

3.1.1. Service Model Description in Sensor Networks

Currently, there are many modeling languages, protocols, and frameworks in web services, for example, OWL-S [24], WSDL [25], BPEL [26], and SOAP [27]. However, these technologies are heavyweight for the limited resources of sensor nodes. Meanwhile, they view services as explicit entities and the resources that provide services as implicit entities.

In contrast with traditional resource-implicit web service description model, our proposed model is resource explicit, and the state of node services is affected by the dynamic properties of the sensor nodes. In addition, each heterogeneous node $N_{i}$ has its own contexts, such as its location, residual battery, available storage, and computation ability and bandwidth. Note that these contexts will affect the service capability of the node, and we only concentrate on the residual battery in this paper. Then, a sensor service $s_{i}$ in sensor networks can be described as follows:

\begin{matrix} s_{i} = 〈 {Name}_{i}, {Input}_{i}, {Output}_{i}, {Op}_{i}, {E R}_{i} 〉 . \end{matrix}

(1)

The service $s_{i}$ is defined by the name, input data that it accepts, the operation function that it applies to its input, the output data that it produces, and the residual energy of the sensor node. The service functionality of $s_{i}$ is defined by ${Input}_{i}$ , ${Output}_{i}$ , and ${Op}_{i}$ . Then, a service class $S_{i} = {s_{i 1}, s_{i 2}, \dots, s_{i k}}$ is defined as a set of sensor services that provide the same functionality but differ in the energy attribute.

3.1.2. Network Model Description

Assume that n heterogeneous nodes $N = {N_{1}, N_{2}, \dots, N_{n}}$ are deployed in a specific area, and the topology of the whole sensor network can be described as $T G = {N, L}$ ; here, $L \subseteq N \times N$ represents the connection set. The set of service classes provided by the whole sensor network is denoted by $S = {S_{1}, S_{2}, \dots, S_{m}}$ , and the syntactic parameters of a service class define service name, input, output, the operation function, and some additional information of service functionality. Assume that the set of service classes provided by a node $N_{i}$ is denoted by $N S L_{i} \subseteq S$ . Therefore, we can use a $n \times m$ matrix R to describe the service capability of each node, and $R_{i j} = 1$ denotes that the node $N_{i}$ is able to provide the service class $S_{j} \in S$ . Then, the service classes provided by $N_{i}$ can be denoted by $N S L_{i} = R [i, :] * S^{'}$ , and $R [i, :]$ is the corresponding row vector of $N_{i}$ . Meanwhile, for a service class $S_{j}$ , the set of available service nodes can be denoted by ${S N L}_{j} = N * R [:, j]$ , and $R [:, j]$ is the corresponding column vector of $S_{j}$ . Then, a heterogeneous sensor network can be described as $N G = {N, L, R}$ .

3.1.3. Application Model Description

In a SOA environment, an assigned application $A_{a}$ can be decomposed into a workflow graph, which contains a set of services with the control and data flow among them. Note that the service in the workflow graph refers to a service class rather than a specified service instance. Then we are able to describe the application as a workflow graph ${A G}_{a} = {S_{a}, O_{a}}$ ; here, $S_{a} = {S_{a}^{1}, \dots, S_{a}^{l}} \subseteq S$ represents the set of the requested service classes and the dependency relation $O_{a} \subseteq S_{a} \times S_{a}$ describes the dependencies between them. Make sure that the requested service classes should be covered by the whole sensor network.

3.1.4. Description of Service Composition Problem

The service composition process can be achieved with a centralized or distributed method. In this paper, for simplicity, we use a centralized fashion. A sink node or a gateway can act as a central decision node receiving information from all service nodes and dispatch the service requests to the selected sensor nodes. The centralized fashion should be only suitable for service composition in small-scale sensor networks because of the dramatically increasing communication cost along with the scale of the wireless sensor network.

As is shown in Figure 2, we can implement a service composition for a given application ${A G}_{a} = {S_{a}, O_{a}}$ by mapping the requested service classes in its workflow graph into the sensor nodes. An application can be constructed as a set of autonomous services that perform independent operations on the data stream passing through them. A service link between two service nodes is defined by $O_{a}$ and it is an overlay link that may consist of several wireless links in the network. The communication path for a service link is built with the shortest path first routing method. Note that the arrow represents the direction of data flow,and $f_{i}$ is the invocation times of each combined service, and $w_{i j}$ represents the amount of data transferred between both the services.

Figure 2

Service composition for a given application in wireless sensor networks.

Note that if the service capability of a node $N_{i}$ can satisfy the requirements of a requested service class $S_{a}^{j}$ , it will meet the following conditions:

\begin{matrix} {N S L}_{i} \supseteq S_{a}^{j} . \end{matrix}

(2)

This formula denotes that certain service class provided by $N_{i}$ should meet the functionality requirements specified by $S_{a}^{j}$ .

Now based on the wireless heterogeneous sensor network $N G = {N, L, R}$ and the received application request $A_{a}$ with the workflow graph ${A G}_{a} = {S_{a}, O_{a}}$ , the key step of service composition for the application $A_{a}$ is to select the appropriate service nodes to serve the service classes specified by the graph ${A G}_{a}$ , and the entire selection process is called service routing. The goal of our study is to find out an approximately optimal service route ${\tilde{G}}_{a}^{opt}$ such that $(1)$ the total energy consumption should be minimized as much as possible and $(2)$ the workload of the service nodes should be well balanced to avoid excessive energy consumption of certain service nodes. We then summarize the symbols used in our model in Table 1.

Table 1

Symbols used in our system model.

Symbol	Description
$A_{a}$	An application
${A G}_{a} = {S_{a}, O_{a}}$	Workflow graph of $A_{a}$
$S_{a} = {S_{a}^{1}, S_{a}^{2}, \dots, S_{a}^{l}}$	The set of service classes required by $A_{a}$ and l is the number of required service classes
$O_{a} \subseteq S_{a} \times S_{a}$	Edges in workflow graph
$w_{i j}$	Amount of data transferred from $S_{a}^{i}$ to $S_{a}^{j}$ each time $S_{a}^{i}$ is invocated
$N G = {N, L, R}$ , $N = {N_{1}, N_{2}, \dots, N_{n}}$ $L \subseteq N \times N$	Topology and service capability description of the heterogeneous sensor network
$S = {S_{1}, S_{2}, \dots, S_{m}}$	The set of service classes provided by the whole network
$E R (N_{i})$	Residual energy of node $N_{i}$
$E_{tx}$	Energy spent by transmitting one unit of data
$E_{rx}$	Energy spent by receiving one unit of data
$E_{inv} (S_{a}^{i})$	Energy spent per invocation to the service $S_{a}^{i} \in S_{a}$ in a physical node
$f_{i}$	Invocation times of each required service $S_{a}^{i} \in S_{a}$

3.2. Energy Cost

The set of the candidate service routes can be denoted by ${\tilde{G}}_{a} = {{\tilde{G}}_{a}^{1}, {\tilde{G}}_{a}^{2}, \dots}$ , and for each candidate service route, in order to evaluate its energy-aware performance, firstly we compute the overall communication and computation cost, as well as both the cost of each involved service node.

3.2.1. Calculate the Overall Communication and Computation Cost of a Candidate Service Route

The overall communication cost contains not only the communication cost of each involved service node, but also the communication cost of the forwarding nodes within the communication paths for the service links. Note that the communication cost in this paper refers to the energy used to transmit and receive the data specified by the requested application. For two requested adjacent service classes $S_{a}^{j}$ , $S_{a}^{k}$ which are connected by a service link in the workflow graph, two nodes $N_{p}, N_{q} \in {\tilde{G}}_{a}^{t}$ are assumed to provide these two service classes, respectively. For simplicity, we exploit the shortest path network routing scheme when transferring data between two service nodes and then the communication cost from the service node $S_{a}^{j} (N_{q})$ to $S_{a}^{k} (N_{q})$ can be calculated as follows:

\begin{array}{l} E_{j k}^{t} = f_{j} * w_{j k} * (E_{t x} + E_{r x}) * hops (P_{j k}^{t}) \\ here: E R (N_{i}) > f_{j} * w_{j k} * (E_{t x} + E_{r x}), \\ for each N_{i} \in P_{j k}^{t} . \end{array}

(3)

Here,

P_{j k}^{t}

denotes the shortest path between the service nodes

N_{p}

and

N_{q}

, and the residual energy of each node in the path should be greater than the necessary communication cost.

E_{t x}

represents the energy spent by transmitting one unit of data, and

E_{r x}

represents the energy spent by receiving one unit of data. The communication cost is proportional to the number of hops between both the involved service nodes. Meanwhile, there is no communication energy consumption when both the requested services are implemented in the same node.

The overall communication cost of the candidate service route ${\tilde{G}}_{a}^{t}$ is given by

\begin{matrix} E_{comm} ({\tilde{G}}_{a}^{t}) = \sum_{(S_{a}^{i}, S_{a}^{j}) \in O_{a}} E_{i j}^{t} . \end{matrix}

(4)

The overall computation cost of the candidate service route ${\tilde{G}}_{a}^{t}$ is given by

\begin{matrix} E_{ comp} ({\tilde{G}}_{a}^{t}) = \sum_{S_{a}^{i} \in S_{a}} f_{i} E_{inv} (S_{a}^{i}) . \end{matrix}

(5)

Based on formula (5), we can conclude that the overall computation cost has no relation with the specific service routes.

3.2.2. Calculate the Communication and Computation Cost of Each Involved Service Node

For each service node involved in a candidate service route ${\tilde{G}}_{a}^{t}$ , we first calculate its communication and computation cost. Note that a specific node may have the capabilities to serve multiple requested services, so we denote the set of requested services assigned to node $N_{p} \in {\tilde{G}}_{a}^{t}$ as follows:

\begin{matrix} N S_{p} = {S_{a}^{i}, where {\tilde{G}}_{a}^{t} (S_{a}^{i}) = N_{p}} . \end{matrix}

(6)

Here,

{\tilde{G}}_{a}^{t} (S_{a}^{i}) = N_{p}

represents that

S_{a}^{i}

is provided by

N_{p}

in the candidate service route

{\tilde{G}}_{a}^{t}

. Then the computation cost for the service node is given by

\begin{matrix} E_{ comp} (N_{p}) = \sum_{S_{a}^{i} \in N S_{p}} f_{i} E_{inv} (S_{a}^{i}) . \end{matrix}

(7)

Then we compute the communication cost of the service node and before this, we assume that the amount of input and output data of a requested service $S_{a}^{i}$ is given by

\begin{matrix} input (S_{a}^{i}) = \sum_{(S_{a}^{x}, S_{a}^{i}) \in O_{a}} f_{x} \cdot w_{x i}, \\ output (S_{a}^{i}) = \sum_{(S_{a}^{i}, S_{a}^{y}) \in O_{a}} f_{i} \cdot w_{i y} . \end{matrix}

(8)

Assume that there are no adjacent relationships among the services provided by node $N_{p}$ ; then, the communication cost of $N_{p}$ can be calculated by

\begin{matrix} E_{comm} (N_{p}) = \sum_{S_{a}^{i} \in N S_{p}} [E_{r x} \cdot input (S_{a}^{i}) + E_{t x} \cdot output (S_{a}^{i})] . \end{matrix}

(9)

However, in some practical applications, a node may provide multiple services which are adjacent. For example, a specific node may provide perception and data fusion services at the same time, and these two services are usually adjacent since the perception data is directly sent to the data fusion service. Here, the data exchange between these two services is implemented within a node and there is no communication cost. Therefore, formula (10) can be rewritten as follows:

\begin{array}{l} E_{comm} (N_{p})  =  \sum_{S_{a}^{i} \in N S_{p}} f_{i} \cdot [E_{r x} \cdot input (S_{a}^{i})  +  E_{t x} \cdot output (S_{a}^{i})] \\ - \sum_{S_{a}^{p}, S_{a}^{q} \in N S_{p}, (S_{a}^{p}, S_{a}^{q}) \in O_{a}} f_{p} \cdot w_{p q} \cdot (E_{r x} + E_{t x}) . \end{array}

(10)

Here,

S_{a}^{p}, S_{a}^{q} \in N S_{p}

denotes that

S_{a}^{p}

S_{a}^{q}

are served by

N_{p}

and

(S_{a}^{p}, S_{a}^{q}) \in O_{a}

denoted that

S_{a}^{p}

S_{a}^{q}

are adjacent in the workflow graph.

3.3. Service Routing with Two Energy-Aware Metrics

As we mentioned above, the optimal service route should balance the workload on the service overlay network. Assume that $N_{i}$ is the service node for $S_{a}^{i}$ , without exhausting its energy; the residual energy in $N_{i}$ should be more than the energy required for the service $S_{a}^{i}$ . Meanwhile, if too many requested services are concentrated on a specific node, it will tend to consume the node's energy excessively and increase the response time of applications. To avoid these from happening, the service routing process should choose the appropriate service nodes by considering their residual energy and current service loads.

In this paper, we implement the service composition with two proposed energy-aware metrics. The first metric is energy-aware load-balancing factor, which we consider to be achieved when the maximal fraction of energy spent by any service node is minimized. With this goal, we define $LBF ({\tilde{G}}_{a}^{t})$ as the energy-aware load-balancing factor of the candidate service route ${\tilde{G}}_{a}^{t}$ , as follows:

\begin{matrix} LBF ({\tilde{G}}_{a}^{t}) = \max_{N_{p} \in N ({\tilde{G}}_{a}^{t})} LBF (N_{p}), \\ LBF (N_{p}) = \frac{E_{ comp} (N_{p}) + E_{comm} (N_{p})}{E R (N_{p})}, N_{p} \in {\tilde{G}}_{a}^{t}, \end{matrix}

(11)

where LBF

(N_{p})

is the energy-aware load-balancing factor of node

N_{p}

E R (N_{p})

denotes the residual energy of the node

N_{p}

The second energy-aware metric is the total energy consumption for implementing the application. Although we believe that energy balance is a better metric to measure the service routes, it is also necessary to use the goal of minimize the total energy consumption to enhance our energy-aware service composition method. The total energy spent for a candidate service route is given by

\begin{matrix} E ({\tilde{G}}_{a}^{t}) = \sum (E_{comm} ({\tilde{G}}_{a}^{t}) + E_{ comp} ({\tilde{G}}_{a}^{t})) . \end{matrix}

(12)

Our service routing algorithm then selects the smallest value of a weighted sum of total energy consumption $E ({\tilde{G}}_{a}^{t})$ and energy-aware load-balancing factor $LBF ({\tilde{G}}_{a}^{t})$ of the candidate ${\tilde{G}}_{a}^{t}$ . Note that the values of both the metrics are normalized in advance. Hence, the goal of service routing can be expressed as follows:

\begin{matrix} {\tilde{G}}_{a}^{opt} = {\tilde{G}}_{a}^{t} : \min_{\forall {\tilde{G}}_{a}^{t} \in {\tilde{G}}_{a}} {μ \cdot E ({\tilde{G}}_{a}^{t}) + λ \cdot LBF ({\tilde{G}}_{a}^{t})} . \end{matrix}

(13)

4. Exhaustive Algorithms for Service Routing

To formulate the problem, the candidate service route ${\tilde{G}}_{a}^{t}$ is denoted by a $1 - l$ dimensional matrix and ${\tilde{G}}_{a}^{t} [i]$ denotes the selected service node providing the requested service $S_{a}^{i}$ . Then, the process of searching out the optimal service route can be formulated into a combinatorial optimization problem, which is expressed as follows.

Inputs: (i)

${A G}_{a} = {S_{a}, O_{a}}$ : workflow graph of a required application;

(ii)

$N G = {N, L, R}$ : network description;

(iii)

$E R (N_{i})$ : residual energy in node $N_{i}$ ;

(iv)

$w_{i j}$ : amount of data transferred from $S_{a}^{i}$ to $S_{a}^{j}$ each time $S_{a}^{i}$ is invocated;

(v)

$f_{i}$ : invocation times of each required service $S_{a}^{i} \in S_{a}$ ;

(vi)

$E_{inv} (S_{a}^{i})$ : energy spent per invocation to the service $S_{a}^{i}$ ;

(vii)

$E_{t x}$ , $E_{r x}$ : energy spent by transmitting/receiving one unit of data.

Outputs: (i)

${\tilde{G}}_{a}^{opt}$ : the optimal service route.

Evaluation Factor:

\begin{matrix} Minimize Z = {μ \cdot E ({\tilde{G}}_{a}^{t}) + λ \cdot LBF ({\tilde{G}}_{a}^{t})} . \end{matrix}

(14)

Constraint:

\begin{matrix} E_{ comp} (N_{p}) + E_{comm} (N_{p}) \leq ER (N_{p}), where N_{p} \in {\tilde{G}}_{a}^{t} . \end{matrix}

(15)

As is shown in Algorithm 1, according to the evaluation factor and constraint, we then propose an exhaustive algorithm to explore the optimal service route for a given application graph. A service route is constructed by selecting an available service node for each requested service class of the application graph. The exhaustive algorithm traverses all combinations with a depth first search algorithm (line $(20) – (23)$ of Algorithm 1). Each valid service route found by the algorithm is scored by calculating its evaluation factor (line $(9) – (11)$ of Algorithm 1). During the execution, the algorithm stores each valid service route and its value of evaluation factor and replaces them every time it finds a service route with a smaller value.

Algorithm 1: Exhaustive composition algorithm.

Given: ${A G}_{a} = {S_{a} [l], O_{a} [l] [l]}, f [l], w [l] [l], S [m]$ , $N G = {N [n], L [n] [n], R [n] [m]}$ , $E R (n)$ , $E_{inv} (l)$ , $E_{t x}$ , $E_{r x}$

Output: ${\tilde{G}}_{a}^{opt} [l]$

(1) /*the overall service selection optimization process*/

(2) $[$ success, ${\tilde{G}}_{a}^{opt}$ , $Z_{opt}$ ] = Combine(i, j, ${\tilde{G}}_{a}^{now}$ , ${A G}_{a}$ , $N G$ , Z)

(3) {

(4) /*a node j is assigned to the requested service class $S_{a} [i]$ in ${A G}_{a}$ */

(5) if $i \neq 0$ then

(6) ${\tilde{G}}_{a}^{now} (i) = j$

(7) end if

(8) /*if the last service node is chosen*/

(9) if $i = l$ then

(10) ${\tilde{G}}_{a}^{opt} = {\tilde{G}}_{a}^{now}$

(11) $[$ success, $Z_{opt}]$ = calcSchedZ( ${\tilde{G}}_{a}^{opt}$ , ${A G}_{a}$ , $N G$ , Z)

(12) else

(13) if $i = 0$ then

(14) /*initialize the parameters*/

(15) ${\tilde{G}}_{a}^{opt} [l] ≔ []$ ; $Z_{opt} ≔ \infty$ ; $success ≔ FALSE$

(16) end if

(17) /*obtain the set of service nodes for each requested service class $S_{a} [i + 1]$ in ${A G}_{a}$ */

(18) idx = GetIndex( $S_{a} [i + 1]$ , $S [m]$ )

(19) ${S N L}_{i + 1} = N [n] * R [:, i d x]$

(20) /*for each available service node for the next level*/

(21) foreach ${S N L}_{i + 1} (k)$ in ${S N L}_{i + 1}$ do

(22) if ${S N L}_{i + 1} (k) \neq 0$ then

(23) [e, comb, z] = Combine( $i + 1$ , ${S N L}_{i + 1} (k)$ , ${\tilde{G}}_{a}^{now}$ , ${A G}_{a}$ , $N G$ , Z)

(24) /*if success and the value of evaluation factor is smaller*/

(25) if e and $z < Z_{opt}$ then

(26) ${\tilde{G}}_{a}^{opt}$ = comb; $Z_{opt} = z$

(27) end if

(28) end if

(29) end foreach

(30) end if

(31) return(success, ${\tilde{G}}_{a}^{opt}$ , $Z_{opt}$ )

(32) }

Algorithm 2 shows the whole process of calculating the evaluation factor. It mainly includes two steps: first, it calculates the expected communication and computation energy cost of every involved service node (line $(5) – (27)$ of Algorithm 2) and it should make sure that the candidate service route is valid by checking if the available energy of every involved service node is enough for providing the requested services (line $(29) – (31)$ of Algorithm 2). Meanwhile, for the valid service node, the algorithm stores its value of load-balancing factor and replaces it every time a service node with larger value of load-balancing factor is found (line $(34) – (39)$ of Algorithm 2). Second, it calculates its evaluation factor by a weighted sum of its load-balancing factor and overall energy cost (line $(43) – (46)$ of Algorithm 2).

Algorithm 2: Evaluation factor calculation algorithm.

(1) [success, $Z_{opt}$ ] = calcSchedZ( ${\tilde{G}}_{a}^{opt}$ , ${A G}_{a}$ , $N G$ , Z)

(2) {

(3) /*firstly initialize the parameters*/

(4) $E_{comp} [n] ≔ []$ ; $E_{comm} [n] ≔ []$ ; $LBF [n] ≔ []$ ; $\max LBF ≔ 0$

(5) /*obtain the index of requested services provided by each involved node

(6) foreach $N_{p}$ in ${\tilde{G}}_{a}^{opt}$ do

(7) ${S I}_{p}$ = getserviceindex( ${\tilde{G}}_{a}^{opt}$ , $N_{p}$ )

(8) /*firstly, compute the computation cost*/

(9) foreach j in ${S I}_{p}$ do

(10) $E_{comp} (p) = E_{comp} (p) + f [j] * E_{inv} (j)$

(11) end foreach

(12) /*compute the amount of input and output data for each requested service in ${A G}_{a}$ */

(13) foreach $S_{a} [i]$ in ${A G}_{a}$ do

(14) foreach $k < = l$ and $k \neq i$ do

(15) Input[i] = Input $[i] + w [k] [i] * f [k]$

(16) Output $[i]$ = Output $[i] + w [i] [k] * f [i]$

(17) end foreach

(18) end foreach

(19) /*compute the communication cost*/

(20) foreach j in ${S I}_{p}$ do

(21) $E_{comm} (p) = E_{comm} (p) + E_{r x} \cdot Input (j) + E_{t x} \cdot Output (j)$

(22) /*check if there exist adjacent services*/

(23) foreach k in ${S I}_{p}$ and $k \neq j$ do

(24) if $S_{a} [j] \to S_{a} [k]$ in $O_{a}$ then

(25) $E_{comm} (p) = E_{comm} (p) - (E_{t x} + E_{r x}) \cdot f [j] \cdot w [j] [k]$

(26) end if

(27) end foreach

(28) end foreach

(29) /*check if the residual energy of $N_{p}$ is enough*/

(30) if $E_{comp} (p) + E_{comm} (p) > E R (p)$ then

(31) $s u c c e s s = F a l s e$

(32) return (False, ∞)

(33) Else

(34) /*compute the load-balancing factor*/

(35) $s u c c e s s = T r u e$

(36) $LBF [p] = [E_{comp} (p) + E_{comm} (p)] / E R (p)$

(37) $E R (p) = E R (p) - [E_{comp} (p) + E_{comm} (p)]$

(38) if $\max LBF < LBF [p]$ then

(39) $\max LBF = LBF [p]$

(40) end if

(41) end if

(42) end foreach

(43) if success then

(44) eg = calcOverallCost( ${\tilde{G}}_{a}^{opt}$ , ${A G}_{a}$ , $N G$ )

(45) /*calculate the evaluation factor*/

(46) $z = μ \cdot e g + λ \cdot \max LBF$

(47) return (TRUE, z)

(48) end if

(49) }

Algorithm 3 shows the process of calculating the overall energy cost of each candidate service route, and it is called by Algorithm 2 (line $(41)$ of Algorithm 2). This algorithm mainly contains two steps of calculating computation energy cost and communication energy cost of the whole service route. The latter is more complex, and it needs to obtain the hops of the shortest path between both the service nodes (line $(10) – (13)$ of Algorithm 3), which depends on the specific topology of the sensor network.

Algorithm 3: Overall energy cost calculation Algorithm.

(1) [ ${E G}_{A}$ ] = calcOverallCost( ${\tilde{G}}_{a}^{opt}$ , ${A G}_{a}$ , $N G$ )

(2) {

(3) /*Firstly initialize the parameters*/

(4) ${E G}_{comp} ≔ 0$ ; ${E G}_{comm} ≔ 0$ ; ${E G}_{A} ≔ 0$ ;

(5) /*compute the overall computation cost*/

(6) foreach $S_{a} [i]$ in $S_{a}$ do

(7) ${E G}_{comp} = {E G}_{comp} + f [i] * E_{inv} (i)$

(8) end foreach

(9) /*compute the overall communication cost*/

(10) foreach $S_{a} [i] \to S_{a} [j]$ in $O_{a}$ do

(11) ${E G}_{comm} (i, j) = f [i] * w [i] [j] * (E_{t x} + E_{r x})$

(12) $* hops [{\tilde{G}}_{a}^{opt} (i), {\tilde{G}}_{a}^{opt} (j)]$

(13) ${E G}_{comm} = {E G}_{comm} + {E G}_{comm} (i, j)$

(14) end foreach

(15) /*compute the overall cost*/

(16) ${E G}_{A} = {E G}_{comp} + {E G}_{comm}$

(17) return ( ${E G}_{A}$ )

(18) }

4.1. Computational Complexity

The proposed exhaustive algorithm suffers from the relatively high computational complexity, because it evaluates all the candidate service routes. Given the $n \times m$ matrix R described in Section 3, the number of associated service instances for each service $S_{j}$ can be calculated as $N (S_{j}) = sum (R (:, j))$ , and the number of requested services of the application $A_{a}$ is m. The algorithm has to evaluate $N (A_{a}) = \prod_{j = 1}^{m} N (S_{j})$ paths, and the computational complexity increases exponentially with the number of service nodes.

5. Improved Discrete Particle Swarm Optimization for Service Routing

Considering the high computational complexity of the exhaustive algorithm, we propose to adopt the evolutionary computing techniques which are more suitable to solve the combinatorial optimization problem. PSO [28] is an adaptive evolutionary computing technique proposed by Kennedy and Eberhart in 1995, which maintains and exploits both the position and velocity information in the evolution process, while other evolutionary algorithms only use the position information. In other words, PSO performs a kind of conscious mutation, which improves the convergence speed greatly. Meanwhile, existing studies show [29] that PSO has the merits of high speed, high quality solution, and good robustness in terms of multimodal optimization in multidimensional space and dynamic optimization. PSO has been widely applied in the complex optimization areas including multiobjective optimization, and pattern recognition. Therefore, we propose to use the PSO algorithm to solve the combinatorial optimization problem in this paper.

5.1. Basic Particle Swarm Optimization

PSO is a population-based optimization tool and inspired by the social behavior of natural individuals. It searches the optimal solution for a difficult optimization problem through the collaboration between the individuals. Assume that the size of swarm is P, the coordinate position of each particle $p_{i} (i = 1 ~ P)$ at time t is denoted by $x_{i} (t) = (x_{i 1} (t), x_{i 2} (t), \dots, x_{i D} (t))$ , and the particle velocity is defined as the moving distance at each search iteration, which is represented by $v_{i} (t) = (v_{i 1} (t), v_{i 2} (t), \dots, v_{i D} (t))$ . At each search iteration, the current position and velocity of each particle are updated by two best values: $(1)$ $p b e s t$ , individual best position that has achieved so far, and $(2)$ $g b e s t$ , another best value representing the global best position among all particles in the swarm. Then the particle $p_{i}$ updates its $d th$ dimensional velocity and position according to the following formula:

\begin{array}{l} v_{i d} (t + 1) = w v_{i d} (t) + c_{1} r_{1} (p b e s t_{i d} (t) - x_{i d} (t)) \\ + c_{2} r_{2} (g b e s t_{d} (t) - x_{i d} (t)) \\ x_{i d} (t + 1) = x_{i d} (t) + v_{i d} (t + 1) . \end{array}

(16)

Here, w is the inertia weight factor which represents the impact of previous values of particle velocities on its current ones. A larger inertia weight factor is suitable for global exploration and a smaller inertia factor is suitable for fine tuning in the current search area. Parameters

c_{1}

and

c_{2}

are positive constants called acceleration coefficients; in general,

c_{1} = c_{2} = 2

. Parameters

r_{1}

and

r_{2}

are two random variables with range

[0,1]

5.2. Improved Discrete Particle Swarm Optimization for Energy-Aware Service Composition

In this section, we present a formalized description for energy-aware service composition with an improved discrete particle swarm optimization (IDPSO) algorithm.

5.2.1. Particle Representation

As we defined in Section 3, a requested application $A_{a}$ can be decomposed into a workflow graph containing a set of requested service classes $S_{a} = {S_{a}^{1}, \dots, S_{a}^{l}} \subseteq S$ . The candidate service route ${\tilde{G}}_{a}^{t} [l]$ contains the set of involved service nodes. Each candidate service route can be viewed as a certain position of a particle $p_{i}$ in the l-dimensional space. Therefore, the particle position will change if any service node in the candidate service route is substituted. Then, the ith particle can be represented as $p_{i} = (p_{i 1}, p_{i 2}, \dots, p_{i d}, \dots, p_{i l})$ , where $p_{i d}$ indicates the index of the allocated service node for the dth requested service $S_{a}^{d}$ in the application graph. The set of service node for $S_{a}^{d}$ is ${S N L}_{d} = {S N_{1}, \dots, S N_{j}, \dots, S N_{M_{d}}}$ , $S N_{j}$ represents a node $N_{i}$ with the capability of providing the requested service class $S_{a}^{d}$ , and $M_{d}$ is the number of candidate service nodes. Each dimension of the particle has a discrete set of possible limit values ${p_{i d} : 1 \leq p_{i d} \leq M_{d}}$ .

5.2.2. Fitness Function

The fitness function $f i t n e s s (p_{i})$ measures to what extent the particle $p_{i}$ satisfies the objective and constraints (which are defined by formula (14) and (15)) of the energy-aware service composition problem. According to the fitness function, the swarm evolution is navigated towards the optimal solution by the best particles. The fitness function $f i t n e s s (p_{i})$ at the tth iteration is defined as follows:

\begin{matrix} f i t n e s s (p_{i} (t)) = Z (p_{i} (t)) . \end{matrix}

(17)

Constraint:

\begin{array}{l} E_{ comp} (p_{i d} (t)) + E_{comm} (p_{i d} (t)) \\ \leq E R (p_{i d} (t)), p_{i d} (t) \in p_{i} (t) . \end{array}

(18)

Here, $p_{i} (t)$ contains a set of service nodes providing services for the requested application and $p_{i d} (t)$ represents a service node. The objective function $Z (p_{i} (t))$ measures the merit of the solution $p_{i} (t)$ under the assumption that every service node in $p_{i} (t)$ satisfies the constraint. However, if any service node in $p_{i} (t)$ violates the constraint, the solution is infeasible. Meanwhile, the value of $f i t n e s s (p_{i})$ is invalid and set to infinity.

5.2.3. Improved Discrete Particle Swarm Optimization Algorithm

As the structure of PSO algorithm is relatively simple, it is running fast. However, PSO is easy to fall into premature convergence and encounter local optimization. To overcome this problem, we propose an improved discrete PSO algorithm in this paper.

Adjustment of Inertia Weights. In this paper, we exploit the fuzzy logic approach to dynamically adjust the value of inertia weight w in the different convergence stages [30]. Then, the PSO algorithm is able to adjust the global parameter adaptively taking into account both the search efficiency and precision. In the fuzzy logic approach, the variables selected as inputs to the fuzzy system are the current best performance evaluation (CBPE) and current inertia weight, whereas the output variable is the change in the inertia weight. The normalized CBPE (NCBPE) is used as an input variable between 0 and 1 and is defined as

\begin{matrix} NCBPE = \frac{CBPE - {CBPE}_{\min}}{{CBPE}_{\max} - {CBPE}_{\min}} . \end{matrix}

(19)

Here, the optimization problem to be solved is a minimization problem, and the estimated minimum is denoted by

{CBPE}_{\min}

, and the calculated value of from (14) at the first iteration may be used as

{CBPE}_{\max}

for the next iterations. Typical inertia weight value is between 0.2 and 1.1, and a range of −0.12 to

+ 0.12

is chosen for the inertia weight correction

(Δ w)

. The specific fuzzy logic approach has been introduced in [30].

Then, we are able to update the value of w with the formula as follows:

\begin{matrix} w (t + 1) = w (t) * (1 + Δ w) . \end{matrix}

(20)

Here, t is the iteration times of the algorithm.

The convergence performance of PSO algorithm can be improved based on this adjustment strategy of the inertia weight w, because PSO algorithm can obtain better global exploration ability with a high w in prophase of the evolution process and accelerate the convergence speed with a low w in anaphase. However, for many complex combinatorial optimization problems, it is not enough to get rid of local optima and improve the exploration accuracy of PSO algorithm only by adjusting the inertia weight. Therefore, in addition to the adjustment of inertia weight, a swarm reoptimization method with extreme perturbation scheme is proposed.

Swarm Reoptimization with Extreme Perturbation Scheme. When PSO algorithm falls into evolutionary stagnation, the phenomenon of particle accumulation happens, and the particles will scatter until the stagnation is broken. This phenomenon is theoretically explained well in [31]. The definition of particle convergence is shown in formula (21), and $p (t)$ represents a particle's position at the tth iteration. This definition describes that the particles will converge to a stable position $p^{*}$ finally, which is determined by the weighted sum of individual best position $p b e s t$ and the global best position $g b e s t$ . If a position better than $g b e s t$ is not found when all the particles are converging to the position $p^{*}$ , then the evolution will fall into stagnation and the particles gradually gather to $p^{*}$ ,

\begin{matrix} \lim_{t \to \infty} p (t) = p^{*} = \frac{c_{1} r_{1}}{c_{1} r_{1} + c_{2} r_{2}} p b e s t + \frac{c_{2} r_{2}}{c_{1} r_{1} + c_{2} r_{2}} g b e s t . \end{matrix}

(21)

An extreme perturbation scheme is employed to break the stagnant state. The basic idea of this scheme is that we will randomly adjust the individual/global best position when the evolution of both the best positions is stagnant for several iterations. And the extreme perturbation operator is defined as follows:

\begin{matrix} p b e s t = r_{3}^{t_{0} > T_{0}} p b e s t; g b e s t = r_{4}^{t_{g} > T_{g}} g b e s t . \end{matrix}

(22)

Here,

t_{0}

t_{g}

represent the steps of evolutionary stagnation for individual and global best positions respectively, and

T_{0}

T_{g}

represent the corresponding thresholds of triggering the extreme perturbation. And the random variables

r_{3}

and

r_{4}

are defined as follows:

\begin{matrix} r_{3}^{t_{0} > T_{0}} = {\begin{cases} 1, & t_{0} \leq T_{0}, \\ U (0,1), & t_{0} > T_{0}; \end{cases} \\ r_{4}^{t_{g} > T_{g}} = {\begin{cases} 1, & t_{g} \leq T_{g}, \\ U (0,1), & t_{g} > T_{g} . \end{cases} \end{matrix}

(23)

Then, based on formula (16), the improved PSO algorithm with dynamic adjustment of inertia weight and extreme perturbation is given as follows:

\begin{array}{l} v_{i d} (t + 1) = w (t) v_{i d} (t) + c_{1} r_{1} (r_{3}^{t_{0} > T_{0}} p b e s t_{i d} (t) - p_{i d} (t)) \\ + c_{2} r_{2} (r_{4}^{t_{g} > T_{g}} g b e s t_{d} (t) - p_{i d} (t)), \\ p_{i d} (t + 1) = p_{i d} (t) + v_{i d} (t + 1) . \end{array}

(24)

Here, the values of

T_{0}

and

T_{g}

determine the activation delay of extreme perturbation, generally in the range of [3, 8].

As we defined before, the particle position can be encoded as a l-dimensional integer array $p_{i} = (p_{i 1}, p_{i 2}, \dots, p_{i d}, \dots, p_{i l})$ , $1 \leq p_{i d} \leq M_{d}, l$ is the number of requested service classes in the workflow graph, and $M_{d}$ is the number of candidate service nodes providing the requested service $S_{a}^{d}$ . Meanwhile, the particle velocity can also be denoted by l-dimensional array $v_{i} = (v_{i 1}, v_{i 2}, \dots, v_{i d}, \dots, v_{i l})$ , $- M_{d} \leq v_{i d} \leq M_{d}$ . Each element in both the arrays is an integer and should be rounded when it is decimal. During IDPSO search process, each element of the l-dimension particle position and velocity that is beyond the value range is adjusted as follows:

\begin{array}{l} if p_{i d} (t) > M_{d}, then p_{i d} (t) = M_{d}, \\ else if p_{i d} (t) < 1, then p_{i d} (t) = 1, \\ if v_{i d} (t) > M_{d}, then v_{i d} (t) = M_{d}, \\ else if v_{i d} (t) < - M_{d}, then v_{i d} (t) = - M_{d} . \end{array}

(25)

5.3. IDPSO Algorithm For Energy-Aware Service Routing

With the iteration formula, we have presented the detailed optimization process with IDPSO algorithm for energy-aware service routing, which is described as shown in Algorithm 4.

Algorithm 4: IDPSO for energy-aware service routing.

(1) Let

(2) P is the size of the PSO swarm

(3) $p_{i} (t) = (p_{i 1} (t), p_{i 2} (t), \dots, p_{i d} (t), \dots, p_{i l} (t))$ , $v_{i} (t) = (v_{i 1} (t), v_{i 2} (t), \dots, v_{i d} (t), \dots, v_{i l} (t))$ are the position and velocity

of particle $p_{i}$ at the tth iteration.

(4) fitness( $p_{i}$ ) is the fitness function of particle $p_{i}$

(5) $g b e s t (t)$ is the global best position so far during t iterations

(6) ${p b e s t}_{i} (t)$ is the individual best position of particle $p_{i}$ so far during t iterations

(7) K is the total number of iterations

(8) Step 1. (Initialization): for each particle $p_{i}$ in the swarm

(9) step 1.1. initialize P, K, w(1), $c_{1}$ , $c_{2}$ ,

(10) step 1.2. initialize $p_{i} (1)$ , $v_{i} (1)$ randomly

(11) step 1.3. evaluate fitness( $p_{i}$ )

(12) step 1.4. initialize $p b e s t_{i} (1)$ with a copy of $p_{i} (1)$

(13) step 1.5. initialize gbest(1) with the position of the particle with the best fitness among the swarm

(14) step 1.6. initialize CBPE with the current best fitness fitness( $P_{g} (1)$ )

(15) step 1.7. initialize CBPE_min and CBPE_max

(16) step 1.8. calculat e $Δ w$ with the fuzzy logic approach

(17) step 1.9. initialize $T_{0}$ and $T_{g}$

(18) Step 2. Repeat until a stopping criteria is satisfied

(19) for $t = 1$ : K

(20) step 2.1. for each particle $p_{i}$ , update the velocity and position of each particle $p_{i}$ according to formula (24).

$v_{i d} (t + 1) = w (t) v_{i d} (t) + c_{1} r_{1} (r_{3}^{t_{0} > T_{0}} p b e s t_{i d} (t) - p_{i d} (t)) + c_{2} r_{2} (r_{4}^{t_{g} > T_{g}} g b e s t_{d} (t) - p_{i d} (t))$

$p_{i d} (t + 1) = p_{i d} (t) + v_{i d} (t + 1)$

(21) step 2.2. reset $t_{0}$ or $t_{g}$ if the related extreme perturbation is executed:

if $t_{0} > T_{0}$ then $t_{0} = 0$ end if

if $t_{g} > T_{g}$ then $t_{g} = 0$ end if

(22) step 2.3. for each iteration, calculate $w (t + 1)$ according formula (20):

$w (t + 1) = w (t) * (1 + Δ w)$

(23) step 2.4. for each particle $p_{i}$ , update its individual best position, the fitness calculation algorithm is given in Algorithm 2:

$p b e s t_{i} (t + 1) = p b e s t_{i} (t)$

if fitness( $p_{i} (t + 1)$ ) ≤ fitness( $p b e s t_{i} (t + 1)$ ) then

$p b e s t_{i} (t + 1) = p_{i} (t + 1)$

end if

(24) step 2.5. for each iteration, update the global best position:

$g b e s t (t + 1) = g b e s t (t)$ ;

for $i = 1$ : P

if fitness( $p_{i} (t + 1)$ ) ≤ fitness( $g b e s t (t + 1)$ ) then

$g b e s t (t + 1) = p_{i} (t + 1)$ ;

end if

end for

(24) step 2.6. for each particle $p_{i}$ : calculate $t_{0}$ and $t_{g}$ for each particle $p_{i}$

(25) end for

(27) Step 3. output

Computational Complexity. In the energy-aware service composition process with IDPSO algorithm, the size of swarm is P, the number of requested service classes in the workflow graph is l, and the number of iterations is K. The computational complexity of the main steps in Algorithm 4 is given as follows: step 2.1: $O (P \times l)$ ; step 2.4: $O (P)$ ; step 2.5: $O (P)$ . Then the total computational complexity of IDPSO is expressed as $O (K \times P \times l)$ , which has no relation with the number of available service nodes for each requested service class.

6. Performance Evaluation

6.1. Simulation Environment

For evaluating the performance of our proposed energy-aware service composition algorithms, we apply them to the target identification and tracking application discussed in Section 1. The workflow graph of this application is shown in Figure 1. We build a sensor network in which there are $n (n = 60$ in this simulation) heterogeneous nodes spreading across a specific area with the size $0.5 km * 0.5 km$ , and each node can be attached to an acoustic sensor, a temperature sensor, or a video sensor that can identify and track the target within its surveillance area. The underlying physical topology is generated by GT-ITM using n-node transit-stub models [32]. For simplicity, we assume that this network provides five service classes, including acoustic sensing, temperature sensing, target localization, identification, and tracking services. Each service class may have multiple service instances, which are randomly distributed over the network. The number of service instances is set to $0.6 * n$ , $0.6 * n$ , $0.4 * n$ , $0.2 * n$ , $0.2 * n$ in turn, and the value will be rounded if it is not an integer.

Furthermore, the fire rate $f_{i}$ of each service in the workflow graph is set as follows: for acoustic sensing service, $f_{i}$ is set to 5; for localization service, it would be awaken only after it has received all the acoustic sensing data. Consider that the sensing data arrives asynchronously because of the different network transmission path and channel conditions. Therefore, the fire rate $f_{i}$ of localization service is 13. Then, the target's location information will be sent to the following services. So the fire rate $f_{i}$ of the following services in the workflow graph is set to 13 too. The amount of data $w_{i j}$ transferred between the services is assumed to be of unit size ( $w_{i j} = 1$ ).

A battery model simulates typical distributed embedded computing hardware, with a CPU and a radio module. For the parameters of our proposed IDPSO algorithm, the size of the swarm P is set to 15, the total number of iterations K is set to 150, and $c_{1} = c_{2} = 2$ ; $w (1) = 0.8$ ; $T_{0} = 3$ ; $T_{g} = 5$ . The weighting factors μ, λ in formula (14) are set to 0.5 if not specified differently.

6.2. Performance Evaluation for Our Proposed Algorithm

Firstly, we evaluate the capability of searching the optimal service route for our proposed methods. As shown in Figure 3, the IDPSO algorithm was evaluated by comparing it with the basic PSO algorithm and exhaustive composition algorithm. In this experiment, given the same initialization parameters, the requested application is executed continuously with 80 times for each algorithm. For each time, the optimal service route is refreshed by running each algorithm, respectively, and the fitness of the optimal solution of each algorithm is recorded.

Figure 3

The curve of fitness of the optimal solution along with the execution times of the requested application.

It is shown that the exhaustive composition algorithm has gained the best performance with the lowest fitness, because it traverses all combinations of service nodes to find out the best one. The value of fitness increases stably because of the gradually increasing value of load-balancing factor. The basic PSO algorithm has the worst performance with the highest fitness, and the value of fitness fluctuates severely because the basic PSO algorithm easily falls into premature convergence and encounters local optimization. Our proposed IDPSO algorithm has gained better performance than the basic PSO algorithm. And it is able to search out a service route approximated with the best one, because the capability of global exploration of the IDPSO algorithm is enhanced with the extreme perturbation scheme.

Secondly, we measure the performance of our proposed methods on extending network lifetime, which is shown in Figure 4. Here, we also assume that all nodes started with an initial energy level and the requested application is executed continuously with 80 times for each algorithm. For the basic PSO algorithm, in Figure 4(a), we can notice that the variance of the residual energy of all the network nodes is the highest and increases most quickly; in Figure 4(b), the minimum residual energy is the lowest after the application is executed with 80 times. Therefore, some network nodes will run out of battery quickly with the basic PSO algorithm, and the network lifetime will be shortened because of the rapid emergence of energy hole. For our proposed IDPSO algorithm, it has gained better performance than the basic PSO algorithm on prolonging the network lifetime (lower variance of the residual energy and higher minimum residual energy), since it has searched out those service routes with better performance on load balancing. We can also notice that the performance of IDPSO approximates to the exhaustive composition algorithm.

Figure 4

The residual energy changes along with the execution times of the requested application: (a) the curve of the variance of the residual energy; (b) the curve of the minimum residual energy.

With the proposed IDPSO algorithm, the performance of service composition is evaluated with using different energy-aware metrics, which is shown in Figure 5. Given the requested application above, we demonstrate the network energy distribution after executing the service composition for 80 times under three circumstances: (a) only use the metric “overall energy consumption” with $μ = 1$ , $λ = 0$ in formula (14); (b) use both the metrics with $μ = 0.5$ , $λ = 0.5$ ; and (c) only use the metric “energy-aware load balancing factor” with $μ = 0$ , $λ = 1$ . From Figure 5(a), it is noticed that the energy of the sensor nodes in the central area with oxford blue has been consumed excessively. This is because that the sensor nodes in the central area are exploited repeatedly in the service composition process when only using the overall energy consumption metric. In Figure 5(c), we can notice that the energy of many sensor nodes in a larger area has been exhausted; in other words, the sensor network is fallen into “malignant load-balancing.” When only the energy-aware load-balancing factor is concerned, the network routing paths will be too much long for many service routes. Further, the energy of many sensor nodes is exhausted just by forwarding data between the service nodes. In Figure 5(b), a better performance on network energy distribution has been gained when using both the metrics, and only few sensor nodes have nearly run out of battery. Therefore, in order to improve the performance of service composition, it is very important to achieve the balance between both the energy-aware metrics.

Figure 5

Network energy distribution after executing the requested application for 80 times with different energy-aware metrics: (a) $μ = 1$ , $λ = 0$ ; (b) $μ = 0.5$ , $λ = 0.5$ ; (c) $μ = 0$ , $λ = 1$ .

Further, to verify the experiment results in Figure 5, with different energy-aware metrics, we have monitored the number of total network transmission hops for the optimal service route of each execution of the requested application, which is shown in Figure 6. By the way, the number of total network transmission hops is obtained by accumulating the number of the network transmission hops between two adjacent service nodes in the service route; meanwhile, both the services nodes should have a service link specified by the workflow graph of the requested application. We notice that the number of total network transmission hops is 5 and remains almost unchanged while only using the overall energy consumption metric, and this is because the optimal service route is not refreshed until some involved sensor nodes run out of power. When only using the energy-aware load-balancing factor, the number of total network transmission hops for the optimal service route changes in a wide range mainly from 10 to 21; therefore, a greater number of sensor nodes in a larger area consume their battery quickly because of forwarding data frequently. By using both the metrics with $μ = 0.5$ and $λ = 0.5$ , the number of total network transmission hops decreases significantly and changes between 5 and 9 and this is because the number of network transmission hops is limited by the optimization objective of minimizing the overall energy consumption.

Figure 6

The total network transmission hops of the optimal service route change along with the execution times of the requested application.

To analyze the global optimization capability of the IDPSO algorithm in depth, we then evaluate its performance on convergence of fitness function by comparing with the basic PSO algorithm. The convergence performance of both the algorithms for the 1st and 80th execution of the requested application is shown in Figure 7. In both the comparison experiments, the basic PSO algorithm has converged on local optimum quickly and fallen into evolutionary stagnation after a short iterative process, and the particles have to gather into the local optimum. For our proposed IDPSO, it has better global exploration ability because of the extreme perturbation scheme. Especially in Figure 7(b), IDPSO is able to search out better solutions at the 96th, 106th, and 139th iterations through a long-time global exploration. By adjusting the individual and global best position when the particle has fallen into evolutionary stagnation, the IDPSO algorithm can increase the particles’ searching field and then improve the probability of finding out better solutions.

Figure 7

Comparison between IDPSO and Basic PSO algorithm on convergence of fitness function: (a) for the 1st execution of the requested application; (b) for the 80th execution of the requested application.

For the running time of IDPSO, as we have analyzed in the last paragraph in Section 5, the computation complexity of IDPSO has no relationship with the number of sensor nodes. As shown in Figure 8, with the increase in the number of atomic services, the running time for finding out an optimal service route with IDPSO maintained steady. For the exhaustive algorithm, the running time increases dramatically because it traverses all the combinations to find out the optimal one.

Figure 8

The running time versus the number of sensor nodes.

We then evaluate the convergence and optimization performance of IDPSO with different swarm size P, which is shown in Figure 9. For each swarm size P, the IDPSO algorithm is run for 20 times independently, and then we obtain the convergence curve with the average values. The best fitness value of the optimal service route obtained by IDPSO descends with the increase of swarm size. This is because a larger swarm size can enlarge the overall searching field and improve the probability of finding out better service routes. Meanwhile, when the swarm size exceeds a certain value, for example, $P = 20$ and $P = 25$ , both the best fitness values are almost the same and there is no significant improvement in performance of IDPSO. Therefore, an excessively large swarm size has little impact on improving the performance of IDPSO. However, it will bring higher computational complexity and delay.

Figure 9

Convergence and optimization performance of IDPSO with different swarm size.

7. Conclusion

In this paper, we have presented an energy-aware service composition method for service-oriented heterogeneous wireless sensor network, and this framework takes into account both the energy-aware metrics including overall energy consumption and energy-aware load-balancing factor. Based on this framework, we propose the IDPSO algorithm, which is able to break the evolutionary stagnation and improve the global exploration capability of the PSO algorithm with the extreme perturbation scheme. Our experiment results have shown that the IDPSO algorithm is capable of searching out better service routes with smaller fitness than the basic PSO algorithm. Meanwhile, the energy-aware performance of the service routes obtained by IDPSO is close to those optimal service routes computed by the exhaustive composition algorithm. Based on the service routes with balancing between both the energy-aware metrics, the lifetime of the sensor network can be prolonged to provide stable service composition for various applications.

Footnotes

Conflict of Interests

The authors declare that they have no conflict of interests regarding the publication of this paper.

Acknowledgments

Our work is supported by multiple funds in china, including the Key Program of NSFC-Guangdong Joint Funds (U1201251), Scientific Research Project of Guangzhou City (12C42111582), Ph.D. Start-up Fund of Natural Science Foundation of Guangdong Province (S2012040006666), and Foundation for Distinguished Young Talents in Higher Education of Guangdong (LYM11057).

References

Mottola

Picco

G. P.

Programming wireless sensor networks: fundamental concepts and state of the art

ACM Computing Surveys 2011 43 3, article 19 1 51

2-s2.0-79955656646

10.1145/1922649.1922656

Sugihara

Gupta

R. K.

Programming models for sensor networks: a survey

ACM Transactions on Sensor Networks 2008 4 2, article 8 1 29

2-s2.0-42149085241

10.1145/1340771.1340774

Mohamed

Al-Jaroodi

A survey on service-oriented middleware for wireless sensor networks

Service Oriented Computing and Applications 2011 5 2 71 85

2-s2.0-79958779556

10.1007/s11761-011-0083-x

Rouached

Chaudhry

Koubaa

Lowpans meet service-oriented architecture

Journal of Ubiquitous Systems and Pervasive Networks 2010 1 1 39 48

Gračanin

Eltoweissy

Wadaa

Dasilva

L. A.

A service-centric model for wireless sensor networks

IEEE Journal on Selected Areas in Communications 2005 23 6 1159 1165

2-s2.0-20844445668

10.1109/JSAC.2005.845625

Anastasi

G. F.

Bini

Romano

Lipari

A service-oriented architecture for QoS configuration and management of wireless sensor networks

Proceedings of the 15th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA '10)

September 2010

Bilbao, Spain

1 8

2-s2.0-78650584429

10.1109/ETFA.2010.5641336

El Hadad

Manouvrier

Rukoz

TQoS: transactional and QoS-aware selection algorithm for automatic web service composition

IEEE Transactions on Services Computing 2010 3 1 73 85

Liu

Huang

L. S.

Xiao

FACTS: a framework for fault-tolerant composition of transactional web services

IEEE Transactions on Services Computing 2010 3 1 46 59

Brønsted

Hansen

K. M.

Ingstrup

Service composition issues in pervasive computing

IEEE Pervasive Computing 2010 9 1 62 70

2-s2.0-75449108211

10.1109/MPRV.2010.11

10.

Kalasapur

Kumar

Shirazi

B. A.

Dynamic service composition in pervasive computing

IEEE Transactions on Parallel and Distributed Systems 2007 18 7 907 918

2-s2.0-34250346875

10.1109/TPDS.2007.1039

11.

Estévez-Ayres

Basanta-Val

García-Valls

Fisteus

J. A.

Almeida

QoS-aware real-time composition algorithms for service-based applications

IEEE Transactions on Industrial Informatics 2009 5 3 278 288

2-s2.0-69249213360

10.1109/TII.2009.2026422

12.

Wang

Exploiting mobility prediction for dependable service composition in wireless mobile ad hoc networks

IEEE Transactions on Services Computing 2011 4 1 44 55

2-s2.0-79952387187

10.1109/TSC.2010.46

13.

Jiang

Xue

Schmidt

D. C.

Minimum disruption service composition and recovery in mobile ad hoc networks

Computer Networks 2009 53 10 1649 1665

2-s2.0-67349208928

10.1016/j.comnet.2008.10.017

14.

Lai

C. F.

Y. W.

Chang

S. Y.

Chao

H. C.

Huang

Y. M.

OSGi-based services architecture for cyber-physical home control systems

Computer Communications 2010 34 2 184 191

2-s2.0-78651267281

10.1016/j.comcom.2010.03.034

15.

Huang

Bastani

F. B.

Yen

I.-L.

Zhang

A framework for efficient service composition in cyber-physical systems

Proceedings of the 5th IEEE International Symposium on Service-Oriented System Engineering (SOSE '10)

June 2010

291 298

2-s2.0-78449234959

10.1109/SOSE.2010.46

16.

Amundson

Kushwaha

Koutsoukos

Neema

Sztipanovits

OASiS: a service-oriented middleware for pervasive ambient-aware sensor networks

Pervasive and Mobile Computing Journal on Middleware for Pervasive Computing 2006

17.

Leguay

Lopez-Ramos

Jean-Marie

Conan

An efficient service oriented architecture for heterogeneous and dynamic wireless sensor networks

Proceedings of the 33rd IEEE Conference on Local Computer Networks (LCN '08)

October 2008

740 747

2-s2.0-58049127292

10.1109/LCN.2008.4664275

18.

Avilés-López

García-Macías

J. A.

TinySOA: a service-oriented architecture for wireless sensor networks

Service Oriented Computing and Applications 2009 3 2 99 108

2-s2.0-67651113908

10.1007/s11761-009-0043-x

19.

Sleman

Moeller

SOA distributed operating system for managing embedded devices in home and building automation

IEEE Transactions on Consumer Electronics 2011 57 2 945 952

2-s2.0-79960900687

10.1109/TCE.2011.5955244

20.

Fok

C. L.

Roman

G. C.

Servilla: a flexible service provisioning middleware for heterogeneous sensor networks

Science of Computer Programming 2012 77 6 663 684

2-s2.0-84858997440

10.1016/j.scico.2010.11.006

21.

Wang

Zheng

Yang

Service composition in service-oriented wireless sensor networks with persistent queries

Proceedings of the 6th IEEE Consumer Communications and Networking Conference (CCNC '09)

January 2009

368 372

2-s2.0-63749119981

10.1109/CCNC.2009.4784868

22.

Geyik

S. C.

Bulut

Szymanski

B. K.

Utilizing PCFGs for modeling and learning service compositions in sensor networks

Proceedings of the IEEE 9th International Conference on Services Computing (SCC '12)

2012

282 289

23.

Dilmaghani

Geyik

Grueneberg

Lobo

Policy-aware service composition in sensor networks

Proceedings of the IEEE 9th International Conference on Services Computing (SCC '12)

2012

186 193

24.

Martin

Burstein

Hobbs

OWL-S: semantic markup for web services

2003, http://www.w3.org/Submission/2004/SUBM-OWL-S-20041122/

25.

Christensen

Curbera

Meredith

Weerawarana

Web services description language (WSDL)

2001, http://www.w3.org/TR/wsdl

26.

Box

Ehnebuske

Kakivay

Simple object access protocol (SOAP)

2007, http://www.w3.org/TR/soap/

27.

Andrews

Curbera

Dholakia

Business process execution language for web services (BPEL)

2003, http://www.ibm.com/developerworks/library/specification/ws-bpel/

28.

Kennedy

Eberhart

Particle swarm optimization

Proceedings of the IEEE International Conference on Neural Networks

December 1995

Perth, Australia

1942 1948

2-s2.0-0029535737

29.

Eberhart

R. C.

Shi

Particle swarm optimization: developments, applications and resources

Proceedings of the Congress on Evolutionary Computation

May 2001

81 86

2-s2.0-0034863568

30.

Bajpai

Singh

S. N.

Fuzzy adaptive particle swarm optimization for bidding strategy in uniform price spot market

IEEE Transactions on Power Systems 2007 22 4 2152 2160

2-s2.0-36348989737

10.1109/TPWRS.2007.907445

31.

Clerc

Kennedy

The particle swarm: explosion stability and convergence in a multi-dimensional complex space

IEEE Transactions on Evolutionary Computation 2002 6 1 58 73

32.

Calvert

K. L.

Doar

M. B.

Zegura

E. W.

Modeling internet topology

IEEE Communications Magazine 1997 35 6 160 163

2-s2.0-0000178416

10.1109/35.587723