Multi-requests satisfied based on energy optimization for the service composition in wireless sensor network

Abstract

Wireless sensor network based on service-oriented architecture has provided important support for Internet of Things in smart city; therefore, multi-requests can be satisfied through service composition. However, as the number and complexity of requests increase, the dynamic and low energy of sensors in wireless sensor network gradually limit the development of the service-oriented architecture in Internet of Things; therefore, optimizing energy under the condition that multi-requests can be satisfied in the dynamic wireless sensor network becomes an important problem. To address this challenge, first, this paper analyzes the mobility of sensors to predict the path stability and manage the information and capabilities on them so that we can find the satisfactory service provider candidates. Then, this article proposes a service mapping pre-process to achieve the work flow reduction in a service layer to save energy in advance and a service mapping process to find the optimal sensors in a network layer that can satisfy the requests. Simulation results show that our strategies can achieve the goal of energy conservation, load balancing, and network lifetime extension under the premise of guaranteeing requests function and non-function attributes and have better performance than traditional ones.

Introduction

In smart cities, wireless sensor network (WSN) uses a service-oriented architecture (SOA) to provide support for the execution of services in the novel paradigms of Internet of Things (IoT).^1,2 Services include both functional and non-function attributes. ³ The function attributes refer to the process in which service operates input data to produce expected output data, while the non-function attributes refer to the quality of service (QoS) which the service can provide, including delay, cost, and reliability.

Generally, service composition represents the process that several atomic services implement complex functions which cannot be fulfilled individually. ⁴ The related researches have achieved such results in the traditional platform.^5,6 Currently, it mainly adopts the method of matching between input and output of atomic services and then generating work flow to realize functions. In SOA-based WSN, a large number of sensors not only sense environment information but also have certain communication and computing capabilities and can provide multiple atomic services. Using work flow technology, WSN integrates the capabilities of sensors and converges them to the sink node to satisfy the functions of IoT requests.

Besides function attributes, QoS that can improve experience of users should also be considered. ⁷ In this article, the atomic service provided by the node is called concrete service. Correspondingly, a service set consisting of the same or similar concrete service is represented as abstract service (AS). In the work flow, the AS representing a certain function takes concrete services with different levels of QoS as candidates ⁸ to satisfy non-functions of IoT requests.

However, unlike traditional platforms that deploy atomic services on servers with powerful capabilities, resources of nodes in WSN such as energy, computing, and bandwidth are quite limited. At the same time, WSN has some special properties such as high mobility. All of those make supporting stable services by traditional methods impossible. ⁹ Hence, how to intelligently and efficiently meet the functions and non-functions of complex and variable requests through service composition becomes a hot topic of current researches.

To satisfy the functions of IoT requests, we need to obtain the services that can be provided in the WSN. However, in WSN, there is a lack of powerful central management devices, and the high mobility of nodes leads to unstable functions. These factors make it difficult to obtain and maintain global services information. Currently some methods assume that all services information is known ¹⁰ or set devices in hot area to record; ¹¹ however, they are not adaptive enough. Satisfying the non-functions of IoT requests is a current main research direction. Most of the work focus on finding best QoS service composition such as delay, ¹² cost, ¹³ and reliability. ¹⁴

Wireless sensors are generally battery powered, have limited power, and work at one-time; therefore, energy is the most important factor of WSN. The work flow of service layer executed by mapping to the network layer. ¹⁵ Since similar service nodes are relatively dispersed, a large amount of energy consumption will be generated in the data-transmission process. ¹⁶ However, few studies optimized the energy consumption of the network layer in service composition.

In this article, we propose a strategy named multi-requests satisfied based on energy optimization for the service composition in WSN to save energy, maintain load balance, and extend WSN lifetime with the function and non-function attributes of the user requests satisfied in the process of mapping work flow from the service layer to the network layer. Our main contributions are summarized as follows

1. Node mobility prediction: according to the relative motion relationship of nodes, the mobility law of nodes is analyzed. Based on this, we predict the link connectivity probability. The node with the optimal connectivity and residual energy is identified as the cluster head and the service information of local nodes is managed in the unit of cluster. All cluster heads aggregate information to the sink node to dynamically cover global services.

2. Work flow reduction: work flow is described as a directed acyclic graph (DAG) composed of the matching of the AS input and output. Service subgraph pruning (SSP) algorithm is proposed to delete the redundant nodes and links. In the service layer, energy consumption is reduced in advance.

3. Mapping from service layer to network layer: mapping the service work flow to a specific network architecture includes nodes and links mapping. In the nodes mapping process, qualified candidate services are filtered according to the QoS and energy. In the links mapping process, the optimal anypath network subgraph (OANS) algorithm is proposed to obtain the energy optimal subgraph in network layer.

Related work

Obtaining the service information provided in the network is a simple task in the traditional platform. However, in WSN, services are provided by sensor nodes and the high mobility makes services management quite hard. Recently, hierarchical routing protocols^17,18 used clusters to manage nodes distributedly by electing cluster heads locally, and then, cluster heads collect sensor data from nodes in the cluster and exchange data with other heads to gather global data. Mobility is an important factor in the process of cluster head election. In order to reduce the frequent validation/failure of routes for the mobility of nodes, the MOBIC algorithm is proposed by Basu et al. ¹⁹ to select nodes with the most stable relative motion as cluster heads. Leng et al. ²⁰ proposed a uniform linear motion model, adopting node connectivity as the cluster head–selection criteria. Sakhaee and Jamalipour ²¹ proposed a pseudo-linear motion model to analyze the Doppler effect during motion and selecting the cluster heads through the stability of the route. The recent researches are generally based on special node motion law. Therefore, inspired by Qin et al., ²² this article proposes a probability analysis method which can support the random motion of nodes, measure the stability of the route, predict the connectivity of the nodes, and then select the cluster heads. As the existing results are quite mature, this article uses few previous studies^18,23 as the fundamental methods to manage the sensor nodes in WSN and uses Wu et al.’s method ²⁴ as the basic method to manage the sensor data.

The general process of the service composition is selecting the AS related to the requests through the matching of semantic similarity ¹⁵ and then get the work flow according to the matching between the input and output. ²⁵ However, there are often many redundancies in the work flow, for example, multiple subflows that can achieve the same function. In recent years, work flow has been described as a service dependency graph,^25,26 and it has received much attention from the perspective of graph theory. The Sim–Dijkstra ²⁵ algorithm proposed for traditional platforms selects and retains the subgraph that can provide the optimal QoS, but it is difficult to replace QoS directly with energy in WSN. Zhou et al. ²⁶ assumes that any service is executed sequentially. Based on this, a method for finding the optimal service chain is proposed. But in order to improve efficiency, parallel links are necessary during service-execution process, which means that oversimplified service graph as service chain is not very reasonable. Therefore, this article proposes a work flow reduction algorithm based on Dijkstra algorithm for service-execution process to find optimal service subgraph. Energy optimization is implemented first in the service layer.

Service mapping refers to executing work flow in the specific devices of the network layer. Main methods include linear programming^27,28 and shortest path search.^15,29 Ngoko et al. ²⁷ used energy as a factor of QoS for global modeling optimization, but the energy consumption in WSN is concentrated in the data-transmission process and cannot be uniformly measured as the attribute of QoS. The use of multi-dimensional multi-choice knapsack problem (MMKP) ²⁸ has improved the computational efficiency, but there is still a problem of the computational complexity increasing exponentially as the size of service and network expand. To solve the shortcomings of the linear programming problem, the shortest path search method was introduced. An improved backward search was proposed by Chen et al., ¹⁵ and an improved breadth-first search (BFS) was proposed in Yan et al. ²⁹ However, due to the dynamic nature of the WSN, the shortest path is difficult to maintain stably, and each hop requires multi-node coordination, so the shortest path problem should be converted into the optimal subgraph problem. Inspired by Zhong et al. ³⁰ and Laufer et al., ³¹ this article utilizes the characteristics of anypath routing, which mainly find the minimum of the sum of the weighted paths to coordinate multi-nodes at each hop, successfully solving the problem of searching for optimal subgraphs.

Mathematical model and problem description

In this section, we will introduce the mathematical model about the scene that we have concentrated on, and describe the problems that we have encountered. The frequently used notations in this article are listed in Table 1.

Table 1.

Frequently used notations.

Notation	Description
$c{s}_i$	Concrete service
$A{S}_j$	Abstract service
$\mathrm{Re}{q}_k$	User requests
$G^s(N^s,\overrightarrow{L^s})$	Service dependency graph
$G^c(N^c,\overrightarrow{L^c})$	Service subgraph
$G^v(N^v,\overrightarrow{L^v})$	Simplified service subgraph
$\mathrm{QoS}\left(c{s}_i\right)$	QoS of $c{s}_i$
$\mathrm{Pref}\left(\mathrm{Re}{q}_k\right)$	Preference of $\mathrm{Re}{q}_k$
$\mathrm{EInfo}\left(c{s}_i\right)$	Energy information of $c{s}_i$
$\mathrm{EInfo}(n_1,n_2)$	Energy information of transmission
$\mathrm{SNPS}(\mathrm{Re}{q}_k,A{S}_{k,j})$	Service node pre-mapping set
$H_n$	Adjacent node set of $n$
$p_{n,H_n}$	Statistical transmission probability
$d_{n,H_n}$	Statistical transmission distance/cost
$D_n$	Shortest distance to destination

QoS: quality of service.

Service model

A concrete service $(\mathrm{cs})$ is provided by sensor nodes, which can be presented as follow

$$\begin{array}{c}c{s}_i=\{\mathrm{InputData}\left(c{s}_i\right),\mathrm{OutputData}\left(c{s}_i\right)\hfill \\ \multicolumn{1}{c}{\mathrm{Operation}\left(c{s}_i\right),\mathrm{QoS}\left(c{s}_i\right),\mathrm{EInfo}\left(c{s}_i\right)\}}\end{array}$$

(1)

where $\mathrm{InputData}(c{s}_i)\mathrm{and}\mathrm{OutputData}(c{s}_i)$ represent the data vector that the $c{s}_i$ needs and produces, respectively, and $\mathrm{Operation}(c{s}_i)$ represents the operation that the $c{s}_i$ performs. $\mathrm{QoS}(c{s}_i)$ represents the QoS of $c{s}_i$ . $\mathrm{EInfo}(c{s}_i)$ represents the energy status of the node which provides the $c{s}_i$ .

An $\mathrm{AS}$ is the set of concrete services with same or similar functions. All of them own the same input and output but have different levels of QoS and energy. An AS can be presented as follow

$$A{S}_j=\{c{s}_{j,1},c{s}_{j,2},...,c{s}_{j,i},...,c{s}_{j,I}\}$$

(2)

where $I$ represents the number of $\mathrm{cs}$ in $A{S}_j$ .

Request $(\mathrm{Req})$ can be presented as follow

$$\begin{array}{c}\mathrm{Re}{q}_k=\{\mathrm{OutputData}\left(\mathrm{Re}{q}_k\right)\hfill \\ \multicolumn{1}{c}{\mathrm{DescFunc}\left(\mathrm{Re}{q}_k\right),\mathrm{Pref}\left(\mathrm{Re}{q}_k\right)\}}\end{array}$$

(3)

where $\mathrm{OutputData}(\mathrm{Re}{q}_k)$ represents expected output, $\mathrm{DescFunc}(\mathrm{Re}{q}_k)$ represents the description of the function, and $\mathrm{Pref}(\mathrm{Re}{q}_k)$ represents the preference about the QoS.

Service dependency graph is a DAG that is generated based on work flow, can be presented by $G^s(N^s,\overrightarrow{L^s})$ , where $N^{\mathrm{s}}$ and $\overrightarrow{L^{\mathrm{s}}}$ represent the set of nodes and links of AS, respectively. $\forall \overrightarrow{l^{\mathrm{s}}}\in \overrightarrow{L^{\mathrm{s}}}$ represents the flow of service data from output to input between ASs. $\mathrm{Data}(\overrightarrow{l^s})$ represents the data size of the link.

The action of choosing all relevant ASs in the service dependency graph according to the request and generating a subgraph can be presented by $G^{\mathrm{c}}(N^{\mathrm{c}},\overrightarrow{L^{\mathrm{c}}})$ , where $N^c\subseteq N^s,\overrightarrow{L^c}\subseteq \overrightarrow{L^s}$ . This article assumes that for all requests, a single connected $G^c$ can be found. Set $V_D\in N^c$ collects output data, corresponding to the sink node in the network layer.

Algorithm 1. Service subgraph pruning
Require: $G^c(N^{\mathrm{c}},\overrightarrow{L^{\mathrm{c}}})$ ;
1: list for reserved node in $N^c$ : $\mathrm{setNode}$ ;
2: $\mathrm{setNode}\Leftarrow \left\{V_D\right\}$ ;
3: queue for backward reachable vertices: $\mathrm{backReachVertices}$ ;
4: $\mathrm{backReachVertices}$ .add $\left(V_D\right)$ ;
5: while $\mathrm{backReachVertices}\ne \varnothing$ do
6:  $v\Leftarrow \mathrm{backReachVertices}$ .poll();
7:  for all $\mathrm{inputdata}\in v$ do
8:   $\mathrm{queue}\Leftarrow$ the nodes providing the inputdata;
9:   if $\mathrm{queue}.\mathrm{length}=1$ then
10:    if $!\mathrm{backReachVertices}$ .contains( $\mathrm{queue}$ .peek())
&& $!\mathrm{setNode}$ .contains( $\mathrm{queue}$ .peek()) then
11:     $\mathrm{setNode}+=\{\mathrm{queue}$ .peek()};
12:     $\mathrm{backReachVertices}$ .add( $\mathrm{queue}$ .poll());
13:    end if
14:   else
15:    priority queue $\mathrm{pq}<\mathrm{map}<\mathrm{node},\mathrm{list}>>$ for recording the lists of potential redundant nodes ordered by size;
16:    for all $\mathrm{node}\in \mathrm{queue}$ do
17:     if $\mathrm{node}.\mathrm{outCounts}=1$ then
18:      $\mathrm{list}\Leftarrow$ search from $\mathrm{node}$ backward until
find $\mathrm{node}.\mathrm{outCounts}>1$ via BFS or DFS;
19:     else
20:      $\mathrm{list}\Leftarrow \left\{\right\}$ ;
21:     end if
22:      $\mathrm{pq}$ .add $(\mathrm{map}<\mathrm{node},\mathrm{list}>)$ ;
23:    end for
24:    for $i=1$ to $\mathrm{pq}.\mathrm{length}-1$ do
25:     $\mathrm{tempList}\Leftarrow \mathrm{pq}$ .removeBiggest().value();
26:    delete relative input and output links of nodes in the $\mathrm{tempList}$ ;
27:    end for
28:    if $!\mathrm{backReachVertices}$ .contains( $\mathrm{pq}$ .peek().key())
&& $!\mathrm{setNode}$ .contains( $\mathrm{pq}$ .peek().key()) then
29:     $\mathrm{setNode}+=$ $\mathrm{pq}$ .peek().key();
30:     $\mathrm{backReachVertices}$ .add( $\mathrm{pq}$ .poll().key());
31:    end if
32:   end if
33:  end for
34: end while

Network model

WSN can be presented by $G^a(N^a,L^a)$ , where $N^a$ represents sensor nodes and $L^a$ represents wireless links.

For simplicity, assuming that each node provides only one cs, which means $\forall n\in N^a$ when it is not selected to perform operation; it is just a relay node for transmission. The communication range is $R$ , and the communication rate is fixed to $r(\mathrm{bits}/\mathrm{s})$ .

$\forall n_1,n_2\in N^a$ and $p_{n_1,n_2}^a$ represents the probability of successfully forwarding packets between two nodes, and $d_{n_1,n_2}^a$ represents the communication distance between two nodes. $\forall l^{\mathrm{a}}\in L^a$ and $b_l^a$ represents residual bandwidth.

QoS model

The QoS of a concrete service can be presented as

$$\mathrm{QoS}\left(c{s}_i\right)=(\mathrm{qo}{s}_{i,1},\mathrm{qo}{s}_{i,2},...,\mathrm{qo}{s}_{i,q},...,\mathrm{qo}{s}_{i,Q})$$

(4)

where $\mathrm{qo}{s}_{i,q}$ represents the value of the $q$ attribute, and $Q$ represents the number of attributes.

There are two types of QoS attributes

• 1. Positive attribute: the bigger the value, the better (e.g. availability and security). It can be calculated as

$$\mathrm{qo}s{\prime }_{i,q}=\{\begin{array}{c}\frac{\mathrm{qo}{s}_{i,q}-{\mathrm{qos}}_q^{min}}{{\mathrm{qos}}_q^{max}-{\mathrm{qos}}_q^{min}},{\mathrm{qos}}_q^{max}-{\mathrm{qos}}_q^{min}\ne 0\hfill \\ \multicolumn{1}{c}{1,{\mathrm{qos}}_q^{max}-{\mathrm{qos}}_q^{min}=0}\end{array}$$

(5)

where ${\mathrm{qos}}_q^{max}=max\{\mathrm{qo}{s}_{i,q}|i=1,...,N^a\},{\mathrm{qos}}_q^{min}=min\{\mathrm{qo}{s}_{i,q}|i=1,...,N^a\}$ .

• 2. Negative attribute: the bigger the value, the better (e.g. cost and delay). It can be calculated by

$$\mathrm{qo}s{\prime }_{i,q}=\{\begin{array}{c}\frac{{\mathrm{qos}}_q^{max}-\mathrm{qo}{s}_{i,q}}{{\mathrm{qos}}_q^{max}-{\mathrm{qos}}_q^{min}},{\mathrm{qos}}_q^{max}-{\mathrm{qos}}_q^{min}\ne 0\hfill \\ \multicolumn{1}{c}{1,{\mathrm{qos}}_q^{max}-{\mathrm{qos}}_q^{min}=0}\end{array}$$

(6)

Request preference

Request preference represents the preference for various QoS attributes. Different requests have different preferences, can be presented as follow

$$\mathrm{Pref}\left(\mathrm{Re}{q}_k\right)=(\mathrm{pre}{f}_{k,1},\mathrm{pre}{f}_{k,2},...,\mathrm{pre}{f}_{k,q},...,\mathrm{pre}{f}_{k,Q})$$

(7)

in which important attributes have higher weight.

Under the $\mathrm{Re}{q}_k$ , the utility we can get from the $c{s}_i$ is

$$\mathrm{Utility}(\mathrm{Re}{q}_k,c{s}_i)=\sum _{q=1}^Q\mathrm{pre}{f}_{k,q}*\mathrm{qo}{s\prime }_{i,q}$$

(8)

Energy model

• 1. Energy model in the service layer

$$\mathrm{EInfo}\left(c{s}_i\right)=\{E_{\mathrm{remain}}^i,\mathrm{\Delta }{E}_{\mathrm{proc}}^i\}$$

(9)

where $E_{\mathrm{remain}}^i$ represents the remaining energy of the node, and $\mathrm{\Delta }{E}_{\mathrm{proc}}^i$ represents the energy-consumption rate of the node performing operation

$$\mathrm{\Delta }{E}_{\mathrm{proc}}^i={\epsilon }_i{f}_i$$

(10)

where $f_i(\mathrm{cycles}/\mathrm{s})$ represents the CPU speed of the node that provides $c{s}_i$ . ${\epsilon }_i(\mathrm{J}/\mathrm{cycle})$ is the parameter that represents energy consumed by each CPU cycle. According to Wen et al., ³² we set ${\epsilon }_i={10}^{-11}(f_i{)}^2$ . So, we can get

$$\mathrm{\Delta }{E}_{\mathrm{proc}}^i={10}^{-11}{\left(f_i\right)}^3$$

(11)

• 2. Energy model in the network layer

$$\begin{array}{c}\multicolumn{1}{c}{\mathrm{EInfo}(n_1,n_2)=\{E_{\mathrm{remain}}^{n_1},E_{\mathrm{remain}}^{n_2},\mathrm{\Delta }{E}_{\mathrm{Tx}}^{n_1,n_2},\mathrm{\Delta }{E}_{\mathrm{Rx}}^{n_2}\},}\\ \multicolumn{1}{c}{(n_1,n_2\in N^a,d_{n_1,n_2}^a\le R)}\end{array}$$

(12)

where $E_{\mathrm{remain}}^{n_1}$ and $E_{\mathrm{remain}}^{n_2}$ represent the remaining energy in send node $n_1$ and receive node $n_2$ , respectively. $\mathrm{\Delta }{E}_{\mathrm{Tx}}^{n_1,n_2}$ and $\mathrm{\Delta }{E}_{\mathrm{Rx}}^{n_2}$ represents the energy-consumption rate of the send node $n_1$ and receive node $n_2$ , respectively

$$\mathrm{\Delta }{E}_{\mathrm{Tx}}^{n_1,n_2}=({\phi }_1+{\phi }_2{d}^m)r$$

(13)

where ${\phi }_1=45\times {10}^{-9}\mathrm{J}/\mathrm{bit}$ and $d$ represent the communication distance. If $d$ is smaller than threshold, $m=2,{\phi }_2=10\times {10}^{-12}\mathrm{J}/\mathrm{bit}/{\mathrm{m}}^2$ , else $m=4,{\phi }_2=0.0001\times {10}^{-12}\mathrm{J}/\mathrm{bit}/{\mathrm{m}}^2$ ³³

$$\mathrm{\Delta }{E}_{\mathrm{Rx}}^{n_2}=\zeta r$$

(14)

where $\zeta =135\times {10}^{-9}\mathrm{J}/\mathrm{bit}$ ³³

According to Shannon formula, to meet the communication rate we should have

$$\forall l^{\mathrm{a}}\in L^a,l^{\mathrm{a}}=(n_1,n_2),b_l^a\ge b_{\mathrm{th}}=\frac{r}{\log (1+\mathrm{\Delta }{E}_{\mathrm{Tx}}^{n_1,n_2}/N_0)}$$

(15)

where $N_0$ represents the noise power.

Service mapping

Service mapping, as shown in Figure 1, including the mapping of service nodes and links to network nodes and links, is used to find sensors to implement requests. Service nodes represents the AS corresponding to network nodes which support concrete service. Service links between service nodes represents the data flow between services corresponding to the network data flow through a few relay nodes. The algorithms proposed in this article will be introduced in the following sections to achieve the goal of energy conservation, load balancing, and network lifetime extension under the premise of guaranteeing requests function and non-function attributes during this service mapping process.

Figure 1.

Service mapping.

Energy optimization for the service composition in the WSN

Service management based on cluster

This article proposes the connectivity and energy information of nodes as the criteria for cluster head selection. First, according to the position and relative motion between nodes, the probability of connection with adjacent nodes is estimated, and then the connectivity of the nodes is predicted. Then, combined with the remaining energy status of nodes, the nodes with the best performance are elected as the cluster heads to maintain the service information locally.

• 1. Mobility analysis

As shown in Figure 2, node $O$ remains relatively stationary and can communicate with nodes within its communication range of radius $R$ . It is assumed that all nodes change the motion state with respect to node $O$ with a time interval $T$ . The change of motion rate and direction obeys the uniform distribution on $[v_{min},v_{max}]$ and $[0,2\pi ]$ , respectively. The possible range of motion in $T$ is the ring shown in Figure 2. According to the overlapping shape of the ring and the circle, we set four situations to correspond to Figures 2–5.

Figure 2.

Ring center in circle I $(v_{max}T-R<d_{O,O\prime }^a\le R-v_{min}T)$ .

Figure 3.

Ring center in circle II $(R-v_{min}T<d_{O,O\prime }^a\le R)$ .

Figure 4.

Ring center outside circle I $(R+v_{min}T\le d_{O,O″}^a<R+v_{max}T)$ .

Figure 5.

Ring center outside circle II $(R<d_{O,O″}^a<R+v_{min}T)$ .

In the following section, according to different situations, the probability that other nodes enter the node $O$ communication range in $T$ is calculated. For nodes whose motion range is within the communication range, the probability is 1. The node whose motion range is outside the communication range has a probability of 0, that is, there is no link between the two nodes.

For nodes within the communication range, as shown in (a) and (b) in the following passage, we can obtain the distance between them directly.

• (a)  $v_{max}T-R<d_{O,O\prime }^a\le R-v_{min}T$

As shown in Figure 2, according to the Helen formula, the area of $\mathrm{\Delta }\mathrm{OAO}\prime$ is

$$S_{\mathrm{\Delta }\mathrm{OAO}\prime }=\sqrt{s(s-R)(s-d_{O,O\prime }^a)(s-v_{max}T)}$$

(16)

where $s=(R+d_{O,O\prime }^a+v_{max}T)/2$ .

According to the cosine theorem

$$\alpha =\arccos \left(\frac{R^2+{\left(d_{O,O\prime }^a\right)}^2-{\left(v_{max}T\right)}^2}{2{\mathrm{Rd}}_{O,O\prime }^a}\right)$$

(17)

$$\beta =\arccos \left(\frac{R^2+{\left(v_{max}T\right)}^2-{\left(d_{O,O\prime }^a\right)}^2}{2R{v}_{max}T}\right)$$

(18)

$$\theta =\alpha +\beta$$

(19)

Furthermore

$$S_{\mathrm{AOB}}=\alpha R^2$$

(20)

$$S_{\mathrm{AO}\prime B}=\theta R^2$$

(21)

$$S_{\mathrm{AB}}=S_{\mathrm{AO}\prime B}-(S_{\mathrm{AOB}}-2S_{\mathrm{\Delta }\mathrm{OAO}\prime })$$

(22)

$$S_{O\prime }=\pi T^2(v_{max}^2-v_{min}^2)$$

(23)

Therefore, the probability is

$$p_{O,O\prime }^a=1-\frac{S_{\mathrm{AB}}}{S_{O\prime }}$$

(24)

• (b)  $R-v_{min}T<d_{O,O\prime }^a\le R$

As shown in Figure 3, in the same way, we can get

$$S_{\mathrm{AB}}=S_{\mathrm{AO}\prime B}-(S_{\mathrm{AOB}}-2S_{\mathrm{\Delta }\mathrm{OAO}\prime })$$

(25)

$$S_{A\prime B\prime }=S_{A\prime O\prime B\prime }-(S_{A\prime \mathrm{OB}\prime }-2S_{\mathrm{\Delta }\mathrm{OA}\prime O\prime })$$

(26)

$$p_{O,O\prime }^a=1-\frac{S_{\mathrm{AB}}-S_{A\prime B\prime }}{S_{O\prime }}$$

(27)

For node $O″$ outside the communication range, as shown in (c) and (d), node $O\prime$ passes $O″$ relative to its position to node $O$ . Distance between $O$ and $O″$ is presented by $d_{O,O″}^a$ .

According to the cosine theorem

$$d_{O,O″}^a=\sqrt{d^2+d{\prime }^2+2\mathrm{dd}\prime \cos \theta }$$

(28)

• (c)  $R+v_{min}T\le d_{O,O″}^a<R+v_{max}T$

As shown in Figure 4

$$S_{\mathrm{AB}}=S_{\mathrm{AO}″B}-(2S_{\mathrm{\Delta }\mathrm{OAO}″}-S_{\mathrm{AOB}})$$

(29)

$$p_{O,O″}^a=\frac{S_{\mathrm{AB}}}{S_{O″}}$$

(30)

• (d)  $R<d_{O,O″}^a<R+v_{min}T$

As shown in Figure 5

$$S_{\mathrm{AB}}=S_{\mathrm{AO}″B}-(2S_{\mathrm{OAO}″}-S_{\mathrm{AOB}})$$

(31)

$$S_{A\prime B\prime }=S_{A\prime O″B\prime }-(2S_{\mathrm{OA}\prime O″}-S_{A\prime \mathrm{OB}\prime })$$

(32)

$$p_{O,O″}^a=\frac{S_{\mathrm{AB}}-S_{A\prime B\prime }}{S_{O″}}$$

(33)

• 2. Criterion for cluster head selection

The connectivity of node $O$ is expressed as the sum of connectivity probability of all nodes in the network

$$\mathrm{Degree}={\sum }_{n\in N^a/\left\{O\right\}}{p}_{O,n}$$

(34)

The energy information is expressed as the ratio of the remaining energy to the maximum in the network

$$\mathrm{Energy}=\frac{E_{\mathrm{remain}}^O}{max(E_{\mathrm{remain}}^n,n\in N^a)}$$

(35)

The cluster head–selection criterion is set as the product of connectivity and energy information

$$\mathrm{Criterion}=\mathrm{Degree}*\mathrm{EInfo}$$

(36)

Each node broadcasts its own criterion locally, and elects the node with the largest value as the cluster head. The cluster head is responsible for collecting the service information of the nodes in the cluster and converging in the sink node to obtain and maintain the global service dependency graph $G^s(N^s,\overrightarrow{L^s})$ .

Service mapping pre-process

• 1. SSP

Service subgraph $G^c(N^c,\overrightarrow{L^c})$ composed of ASs related to the specific request, comes from the whole service dependency graph $G^s(N^s,\overrightarrow{L^s})$ . As shown in Figure 6, the left side of the node represents the required input data, and the right side represents the data that can be outputted. Only when the input data are all satisfied the output data can be generated, which is called activated. We assume the node that is not activated does not exist. A service subgraph often has large structural redundancy due to complex logical relationships. The same data may have multiple sources, which results in redundant nodes and links, as shown by the dotted lines in Figure 6. If the service mapping is directly carried out, it will cause huge waste to the network resources. This article proposes the SSP algorithm to simplify the service structure in advance.

Figure 6.

Service subgraph.

The SSP algorithm is an improved BFS. It uses a backward search method to simplify the structure while satisfying the integrity of the output data. For multiple sources of the same data, backward search is performed separately, all nodes satisfying the out-degree of 1 are recorded, multiple result lists are stored by the priority queue, the minimum list is retained, and the nodes and links in the other lists are deleted. After the traversal is completed, generating the simplified service subgraph $G^{\mathrm{v}}(N^{\mathrm{v}},\overrightarrow{L^v})$ , which is the graph in Figure 6 without dotted line parts.

• 2. Service node pre-mapping

According to the request, simplifying the candidates of ASs to get sensor nodes which can satisfy the restriction of QoS and energy. We call this process as service node pre-mapping, and the candidates we get as service node pre-mapping set (SNPS)

$$\begin{array}{c}\mathrm{SNPS}(\mathrm{Re}{q}_k,A{S}_{k,j})=\{c{s}_{k,j,i}|\mathrm{Utility}(\mathrm{Re}{q}_k,c{s}_{k,j,i})\hfill \\ \multicolumn{1}{c}{\ge U_{\mathrm{th}},E_{\mathrm{remain}}^{k,j,i}-\mathrm{\Delta }{E}_{\mathrm{proc}}^{k,j,i}*\frac{\mathrm{Tas}{k}_{k,j}}{f_{k,j,i}}\ge E_{\mathrm{th}}\}}\end{array}$$

(37)

where $\mathrm{Tas}{k}_{k,j}$ represents the size of tasks assigned on the $A{S}_{k,j}$ node by $\mathrm{Re}{q}_k$ . The unit of $\mathrm{Tas}{k}_{k,j}$ is megacycle and can be obtained with the method of Chun et al. ³⁴ $U_{\mathrm{th}}$ and $E_{\mathrm{th}}$ represent the threshold of utility and energy, respectively.

Service mapping process

Due to the limited bandwidth and instability of the wireless link in the network layer, the mapping of service links is difficult to find an optimal transmission path meeting request. Therefore, it is necessary to utilize multiple nodes at each hop, which means to find the optimal transmission subgraph; however, the difficulty of searching greatly increases. This article, inspired by anypath routing theory,^30,31 proposes an OANS algorithm and solves the problem.

We select multiple nodes per hop and named the corresponding link set as hyperlink which is presented by $(n,H_n)$ , where $H_n$ represents the adjacent node set of $n$ . Then, we can get the probability of successful transmission $p_{n,H_n}$ and the distance of transmission $d_{n,H_n}$ .

Based on anypath routing theory, $p_{n,H_n}$ is defined as the packet being forwarded to at least one node in $H_n$ to describe the stability of the hyperlink. So, we can get

$$p_{n,H_n}=1-\underset{h\in H_n}{\Pi }(1-p_{n,h}^a)$$

(38)

$d_{n,H_n}$ is used to measure the cost of transmission. In order to achieve the energy-optimization goal of this article and ensure the function and non-function attributes of the request, this article set as follows

$$d_{n,H_n}=\mathrm{\Delta }{E}_{n,H_n}$$

(39)

$$\mathrm{\Delta }{E}_{n,H_n}=\sum _{h\in H_n}{w}_h*(\mathrm{\Delta }{E}_{\mathrm{Tx}}^{n,h}+\mathrm{\Delta }{E}_{\mathrm{Rx}}^h)$$

(40)

where

$$w_h=\frac{p_{n,h}^a\underset{x\in H_n/\left\{h\right\}}{\Pi }(1-p_{n,x}^a)}{p_{n,H_n}}$$

(41)

$d_{n,H_n}$ represents the rate of the energy consumed in hyperlink system with $p_{n,H_n}$ . This article selects the hyperlink with the best energy performance.

The node $n$ transmits data to the destination node in an anypath matter through the adjacent node set. We utilize hyperlink to convert the problem of searching optimal subgraph into the problem of searching shortest path. In this article, the shortest distance from node $n$ to the destination node $\mathrm{dst}$ is set to $D_n$ , as defined below

$$D_n=d_{n,H_n}+D_{H_n}$$

(42)

$$D_{H_n}=\sum _{h\in H_n}{w}_h*D_h$$

(43)

$D_n$ is summed with the distance from $n$ to $H_n$ and the distance from $H_n$ to $\mathrm{dst}$ . This is an iterative formula based on which we can search the optimal subgraph from $\mathrm{dst}$ to $n$ .

In algorithm 2, the priority queue is used to store the D of nodes that have not found the optimal subgraph in order from small to large and F is used to record the selected forwarding nodes. For adjacent node set $H$ , first we filter out nodes that meet communication distance, bandwidth, and energy constraints, where $\mathrm{Data}(\mathrm{bits})$ represents the size of the data to be transmitted. Then judging whether the node can act as a relay node and shorten its distance to the $\mathrm{dst}$ . If it is satisfied, add the node to $F$ . After the traversal is completed, if $\mathrm{src}$ is unknown, then we select the node as $\mathrm{src}$ with the smallest $D$ in SNPS and BFS the optimal $\mathrm{subgraph}(\mathrm{src},\mathrm{dst})$ based on $F$ of each node. At last, updating the status of relative nodes and links. However, if $D_{\mathrm{src}}=\infty$ , which means there is no subgraph existing, then return Ø.

Algorithm 2. Optimal anypath network subgraph
Require: $G^a(N^a,L^a)$ , $\mathrm{dst}$ , $\mathrm{SNPS}(\mathrm{Re}{q}_k,A{S}_{k,j})$ , $\mathrm{src}$
1: priority queue for nodes which still need to find optimal $D$ ordered by their current $D$ : $\mathrm{PQ}$ ;
2: for all node $n\in N^a$ do
3:   $D_n\Leftarrow \infty$ ;
4:  $F_n\Leftarrow Ø$ ;
5: end for
6: ${\mathrm{D}}_{\mathrm{dst}}\Leftarrow 0$ ;
7: $\mathrm{PQ}\Leftarrow N^a$ ;
8: while $\mathrm{PQ}\ne Ø$ do
9:  $n\Leftarrow \mathrm{PQ}$ .removeSmallest();
10:  for all node $h\in H_n$ && $d_{h,\mathrm{dst}}^a\ge d_{n,\mathrm{dst}}^a$ && $b_{n,h}^a\ge b_{\mathrm{th}}$ do
11:   if $D_h>D_n$ && $E_{\mathrm{remain}}^n-\mathrm{\Delta }{E}_{\mathrm{Rx}}^n*\frac{\mathrm{Data}}{r}\ge E_{\mathrm{th}}$ then
12:    $H\Leftarrow F_h\cup \left\{n\right\}$ ;
13:    if $E_{\mathrm{remain}}^h-\sum _{\delta \in H}\mathrm{\Delta }{E}_{\mathrm{Tx}}^{h,\delta }*\frac{\mathrm{Data}}{r}\ge E_{\mathrm{th}}$ && $D_h>d_{h,H}+D_H$ then
14:     $D_h\Leftarrow d_{h,H}+D_H$ ;
15:     $F_h\Leftarrow H$ ;
16:     $E_{\mathrm{remain}}^n\Leftarrow E_{\mathrm{remain}}^n-\mathrm{\Delta }{E}_{\mathrm{Rx}}^n*\frac{\mathrm{Data}}{r}$ ;
17:    end if
18:   end if
19:  end for
20: end while
21: if $\mathrm{src}=\mathrm{null}$ then
22:  $\mathrm{src}\Leftarrow$ the node providing $\mathrm{c}{\mathrm{s}}_{k,j,i}$ in SNPS with the smallest $D$ ;
23: end if
24: if $D_{\mathrm{src}}=\infty$ then
25:  return $\mathrm{s}\mathrm{rc},Ø$ ;
26: end if
27: BFS the $\mathrm{subgraph}(\mathrm{src},\mathrm{dst})$ based on the $F$ of each node;
28: Update relative nodes and links;
29: return $\mathrm{src},\mathrm{subgraph}(\mathrm{src},\mathrm{dst})$ ;

Algorithm 3. Service mapping to network
1: Predict the degree and calculate the energy to select the cluster head;
2: Form the cluster and collect service information;
3: Send to the Sink and get $G^s(N^s,\overrightarrow{L^s})$ ;
4: Set the priorities of requests based on the delay sensitivity;
5: map for recording the mapping between service node and network node $\mathrm{ma}{\mathrm{p}}_k<A{S}_{k,j},n>$ ;
6: for $j=1$ to $K$ do
7:  Find the relative $A{S}_j$ according to $\mathrm{Re}{q}_k$ and get $G^{\mathrm{c}}(N^{\mathrm{c}},\overrightarrow{L^{\mathrm{c}}})$ ;
8:  $G^{\mathrm{v}}(N^{\mathrm{v}},\overrightarrow{L^v})\Leftarrow \mathrm{SSP}(G^{\mathrm{c}}(N^{\mathrm{c}},\overrightarrow{L^{\mathrm{c}}}))$ ;
9:  $\mathrm{list}\Leftarrow$ BFS nodes backward from $V_D$ ;
10: for $j=1$ to $\mathrm{list}.$ size() do
11:   Calculate $\mathrm{SNPS}(\mathrm{Re}{q}_k,A{S}_{k,j})$ ;
12:   for each incoming edge $A{S}_{k,z},A{S}_{k,j}$ do
13:    $\mathrm{dst}\Leftarrow \mathrm{ma}{p}_{\mathrm{k}}.\mathrm{get}\left(A{S}_{k,\mathrm{j}}\right)$ ;
14:    if $\mathrm{ma}{\mathrm{p}}_k.\mathrm{get}\left(A{S}_{k,z}\right)=\mathrm{null}$ then
15:     $\begin{array}{c}\mathrm{src},\mathrm{subgraph}(\mathrm{src},\mathrm{dst})\Leftarrow \hfill \\ \multicolumn{1}{c}{\mathrm{OANS}(G^a(N^a,L^a),\mathrm{dst},}\\ \multicolumn{1}{c}{\mathrm{SNPS}(\mathrm{Re}{q}_k,A{S}_{k,\mathrm{z}}),\mathrm{null})}\end{array}$ ;
16:    else
17:     $\mathrm{src}\Leftarrow \mathrm{ma}{\mathrm{p}}_k.\mathrm{get}\left(A{S}_{k,z}\right)$ ;
18:     $\begin{array}{c}\mathrm{subgraph}(\mathrm{src},\mathrm{dst})\Leftarrow \hfill \\ \multicolumn{1}{c}{\mathrm{OANS}(G^a(N^a,L^a),\mathrm{dst},}\\ \multicolumn{1}{c}{\mathrm{SNPS}(\mathrm{Re}{q}_k,A{S}_{k,\mathrm{z}}),\mathrm{src})}\end{array}$ ;
19:    end if
20   if $\mathrm{subgraph}(\mathrm{src},\mathrm{dst})=Ø$ then
21:     $\mathrm{Re}{q}_k$ Failure; Process;
22:     Process $\mathrm{Re}{q}_{k+1}$ ;
23:    end if
24:   end for
25:  end for
26: end for

Multi-requests execution process

In this section, we introduce the algorithm named service mapping to network (SMN) to achieve energy optimization for the service composition in WSN with multi-requests satisfied.

1. Initialization phase

   Nodes mobility is analyzed, and the cluster head node is elected. Service information was collected by the cluster head node and aggregated to the sink node. The whole network service information is obtained and updated regularly to provide support for the function attributes of requests.

2. Request execution phase

   Priority is set according to the delay sensitivity of requests, and the delay-sensitive requests priority is relatively high. The key-value pair is used to store the mapping relationship between service layer node and network layer node. Executing SSP to prune the service dependency subgraph. All nodes are traversed in reverse from $V_D$ via BFS, stored in the list, and the service node pre-mapping process is performed. The OANS is then implemented on the input links of all nodes. Once the link mapping process fails, this request will be canceled, and the process of the next request will start.

Simulation

In this section, we use MATLAB to evaluate the algorithms proposed in this article. We generated nodes randomly and set $R=30\mathrm{m},v_{\min }=0-0.2\mathrm{m}/\mathrm{s},v_{\max }=0.8-1.2\mathrm{m}/\mathrm{s},T=10\mathrm{s},\mathrm{and}r=10\mathrm{Mbps}$

SSP

In the service layer, the SSP algorithm is used at first to streamline service structure. The ratios of the remaining nodes and links are, respectively, used as criteria for the performance of the SSP.

All nodes randomly generate inputs and outputs that match each other to form a connected DAG. The simulation results are shown in Figure 7. The SSP algorithm proposed in this article can effectively achieve the goal of streamlined service subgraph. When it is 10 AS, reduced links by 38% and reduced nodes by 29%. In the mean time, as the network nodes increase, the redundancy ratio that can be deleted increases. Compared with deleting nodes, the SSP can delete redundant links more effectively and then reduce unnecessary energy consumption in the network layer transmission process in advance.

Figure 7.

The ratios of remaining nodes and links.

OANS

In the network layer, the OANS algorithm is implemented for network graph between the $\mathrm{src}$ and $\mathrm{dst}$ to find the subgraph with the best energy-consumption performance and compare it with the shortest path algorithm.

In order to highlight the experimental results, it is assumed that source node and target node are respectively at the two ends of the network. By increasing the number of networks nodes, the complexity of the network is increased, and the performance of two algorithms is compared. The simulation results are shown in Figure 8. Under the energy and bandwidth constraints, the OANS algorithm has a lower energy-consumption rate. With the increase of network complexity, OANS and shortest path algorithms both show an upward trend, but the growth rate of OANS is slower; therefore, the numerical gap increases, which indicates OANS has better adaptability.

Figure 8.

Energy-consumption rate with different number of network nodes.

The number of nodes is controlled at 80, and the energy-consumption performance is measured by changing the proportion of dead nodes. The simulation results are shown in Figure 9. Dead nodes refer to nodes that do not meet energy or bandwidth constrains. As the percent of dead nodes increase, the energy-consumption rate of the two algorithms increase gradually due to the decrease of available nodes. The OANS algorithm is gradually close but still lower than the shortest path algorithm, which means the OANS has better robustness and the shortest path is the lower boundary of the OANS.

Figure 9.

Energy-consumption rate with different percent of dead nodes.

SMN

In this section, we execute the SMN to map service graph to the network layer and still compare with the shortest path algorithm to evaluate the whole network performance.

The number of network nodes is controlled at 80. The standard deviation of the energy-consumption rate of the whole network is used as a criteria of the load balancing. The simulation results are shown in Figure 10. As requests increase, the standard deviation of two algorithms decrease gradually. SMN proposed in this article has a faster rate of decline and is much lower than shortest path algorithm, which means that it has better performance in load balancing. SMN can utilize multiple relay nodes per hop so that it can disperse load pressure and avoid partial over-consumption effectively.

Figure 10.

Standard deviation of energy consumption with different requests.

Network lifetime is used to evaluate both energy conservation and load balancing in the whole process of mapping in the same time, and it is the most important criteria for WSN. In this section, we set network lifetime as the duration from the moment that all nodes are 100% energy to the moment that no more requests can be satisfied due to the energy exhausted. Because we disperse the load, the pressure on the core nodes is mitigated and the SMN can support more requests than the shortest path algorithm with high probability. Because of the limitation of network resource, the lifetime keeps steady finally. As shown in Figure 11, as the requests increase, the lifetime of SMN is larger than shortest path algorithm, and the shortest path algorithm becomes stable more quickly. The results reflect that the SMN has longer lifetime and can support more requests than the shortest path algorithm; therefore, the SMN can optimize the energy consumption and achieve load balancing simultaneously.

Figure 11.

Network lifetime with different requests.

Conclusion

In this article, we propose a service-execution strategy for energy optimization in WSN. In the network layer, the motion model of the sensor is designed, the probability of connectivity between nodes is analyzed, and the cluster head is elected, based on which service information is collected and managed to satisfy function attributes. In the service layer, we propose SSP to delete the redundancy of the service graph and pre-select candidate nodes to satisfy non-function attributes. In the process of mapping from the service layer to the network layer, OANS and SMN are proposed. The simulation results show that our strategy can save energy and balance load on the basis of guaranteeing the function and non-function attributes and has better performance than traditional ones.