Sage Journals: Discover world-class research

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.

Keywords

Wireless sensor network service composition Internet of Things energy conservation graph theory

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

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.

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.

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
$Re q_{k}$	User requests
$G^{s} (N^{s}, \vec{L^{s}})$	Service dependency graph
$G^{c} (N^{c}, \vec{L^{c}})$	Service subgraph
$G^{v} (N^{v}, \vec{L^{v}})$	Simplified service subgraph
$QoS (c s_{i})$	QoS of $c s_{i}$
$Pref (Re q_{k})$	Preference of $Re q_{k}$
$EInfo (c s_{i})$	Energy information of $c s_{i}$
$EInfo (n_{1}, n_{2})$	Energy information of transmission
$SNPS (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 $(cs)$ is provided by sensor nodes, which can be presented as follow

\begin{matrix} c s_{i} = {InputData (c s_{i}), OutputData (c s_{i}) \\ Operation (c s_{i}), QoS (c s_{i}), EInfo (c s_{i})} \end{matrix}

(1)

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

An $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 $cs$ in $A S_{j}$ .

Request $(Req)$ can be presented as follow

\begin{matrix} Re q_{k} = {OutputData (Re q_{k}) \\ DescFunc (Re q_{k}), Pref (Re q_{k})} \end{matrix}

(3)

where $OutputData (Re q_{k})$ represents expected output, $DescFunc (Re q_{k})$ represents the description of the function, and $Pref (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}, \vec{L^{s}})$ , where $N^{s}$ and $\vec{L^{s}}$ represent the set of nodes and links of AS, respectively. $\forall \vec{l^{s}} \in \vec{L^{s}}$ represents the flow of service data from output to input between ASs. $Data (\vec{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^{c} (N^{c}, \vec{L^{c}})$ , where $N^{c} \subseteq N^{s}, \vec{L^{c}} \subseteq \vec{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^{c}, \vec{L^{c}})$ ;
1: list for reserved node in $N^{c}$ : $setNode$ ;
2: $setNode \Leftarrow {V_{D}}$ ;
3: queue for backward reachable vertices: $backReachVertices$ ;
4: $backReachVertices$ .add $(V_{D})$ ;
5: while $backReachVertices \neq \emptyset$ do
6: $v \Leftarrow backReachVertices$ .poll();
7: for all $inputdata \in v$ do
8: $queue \Leftarrow$ the nodes providing the inputdata;
9: if $queue . length = 1$ then
10: if $! backReachVertices$ .contains( $queue$ .peek())
&& $! setNode$ .contains( $queue$ .peek()) then
11: $setNode + = {queue$ .peek()};
12: $backReachVertices$ .add( $queue$ .poll());
13: end if
14: else
15: priority queue $pq < map < node, list > >$ for recording the lists of potential redundant nodes ordered by size;
16: for all $node \in queue$ do
17: if $node . outCounts = 1$ then
18: $list \Leftarrow$ search from $node$ backward until
find $node . outCounts > 1$ via BFS or DFS;
19: else
20: $list \Leftarrow {}$ ;
21: end if
22: $pq$ .add $(map < node, list >)$ ;
23: end for
24: for $i = 1$ to $pq . length - 1$ do
25: $tempList \Leftarrow pq$ .removeBiggest().value();
26: delete relative input and output links of nodes in the $tempList$ ;
27: end for
28: if $! backReachVertices$ .contains( $pq$ .peek().key())
&& $! setNode$ .contains( $pq$ .peek().key()) then
29: $setNode + =$ $pq$ .peek().key();
30: $backReachVertices$ .add( $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 (bits / 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^{a} \in L^{a}$ and $b_{l}^{a}$ represents residual bandwidth.

QoS model

The QoS of a concrete service can be presented as

QoS (c s_{i}) = (qo s_{i, 1}, qo s_{i, 2}, . . ., qo s_{i, q}, . . ., qo s_{i, Q})

(4)

where $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

qo s'_{i, q} = {\begin{matrix} \frac{qo s_{i, q} - {qos}_{q}^{min}}{{qos}_{q}^{max} - {qos}_{q}^{min}}, {qos}_{q}^{max} - {qos}_{q}^{min} \neq 0 \\ 1, {qos}_{q}^{max} - {qos}_{q}^{min} = 0 \end{matrix}

(5)

where ${qos}_{q}^{max} = max {qo s_{i, q} | i = 1, . . ., N^{a}}, {qos}_{q}^{min} = min {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

qo s'_{i, q} = {\begin{matrix} \frac{{qos}_{q}^{max} - qo s_{i, q}}{{qos}_{q}^{max} - {qos}_{q}^{min}}, {qos}_{q}^{max} - {qos}_{q}^{min} \neq 0 \\ 1, {qos}_{q}^{max} - {qos}_{q}^{min} = 0 \end{matrix}

(6)

Request preference

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

Pref (Re q_{k}) = (pre f_{k, 1}, pre f_{k, 2}, . . ., pre f_{k, q}, . . ., pre f_{k, Q})

(7)

in which important attributes have higher weight.

Under the $Re q_{k}$ , the utility we can get from the $c s_{i}$ is

Utility (Re q_{k}, c s_{i}) = \sum_{q = 1}^{Q} pre f_{k, q} * qo {s'}_{i, q}

(8)

Energy model

1. Energy model in the service layer

EInfo (c s_{i}) = {E_{remain}^{i}, Δ E_{proc}^{i}}

(9)

where $E_{remain}^{i}$ represents the remaining energy of the node, and $Δ E_{proc}^{i}$ represents the energy-consumption rate of the node performing operation

Δ E_{proc}^{i} = ε_{i} f_{i}

(10)

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

Δ E_{proc}^{i} = 10^{- 11} {(f_{i})}^{3}

(11)

2. Energy model in the network layer

\begin{matrix} EInfo (n_{1}, n_{2}) = {E_{remain}^{n_{1}}, E_{remain}^{n_{2}}, Δ E_{Tx}^{n_{1}, n_{2}}, Δ E_{Rx}^{n_{2}}}, \\ (n_{1}, n_{2} \in N^{a}, d_{n_{1}, n_{2}}^{a} \leq R) \end{matrix}

(12)

where $E_{remain}^{n_{1}}$ and $E_{remain}^{n_{2}}$ represent the remaining energy in send node $n_{1}$ and receive node $n_{2}$ , respectively. $Δ E_{Tx}^{n_{1}, n_{2}}$ and $Δ E_{Rx}^{n_{2}}$ represents the energy-consumption rate of the send node $n_{1}$ and receive node $n_{2}$ , respectively

Δ E_{Tx}^{n_{1}, n_{2}} = (φ_{1} + φ_{2} d^{m}) r

(13)

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

Δ E_{Rx}^{n_{2}} = ζ r

(14)

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

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

\forall l^{a} \in L^{a}, l^{a} = (n_{1}, n_{2}), b_{l}^{a} \geq b_{th} = \frac{r}{\log (1 + Δ E_{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 π]$ , 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'}^{a} \leq R - v_{min} T)$ .

Figure 3.

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

Figure 4.

Ring center outside circle I $(R + v_{min} T \leq 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'}^{a} \leq R - v_{min} T$

As shown in Figure 2, according to the Helen formula, the area of $Δ OAO'$ is

S_{Δ OAO'} = \sqrt{s (s - R) (s - d_{O, O'}^{a}) (s - v_{max} T)}

(16)

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

According to the cosine theorem

α = \arccos (\frac{R^{2} + {(d_{O, O'}^{a})}^{2} - {(v_{max} T)}^{2}}{2 {Rd}_{O, O'}^{a}})

(17)

β = \arccos (\frac{R^{2} + {(v_{max} T)}^{2} - {(d_{O, O'}^{a})}^{2}}{2 R v_{max} T})

(18)

θ = α + β

(19)

Furthermore

S_{AOB} = α R^{2}

(20)

S_{AO' B} = θ R^{2}

(21)

S_{AB} = S_{AO' B} - (S_{AOB} - 2 S_{Δ OAO'})

(22)

S_{O'} = π T^{2} (v_{max}^{2} - v_{min}^{2})

(23)

Therefore, the probability is

p_{O, O'}^{a} = 1 - \frac{S_{AB}}{S_{O'}}

(24)

(b) $R - v_{min} T < d_{O, O'}^{a} \leq R$

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

S_{AB} = S_{AO' B} - (S_{AOB} - 2 S_{Δ OAO'})

(25)

S_{A' B'} = S_{A' O' B'} - (S_{A' OB'} - 2 S_{Δ OA' O'})

(26)

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

(27)

For node $O ″$ outside the communication range, as shown in (c) and (d), node $O'$ 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'^{2} + 2 dd' \cos θ}

(28)

As shown in Figure 4

S_{AB} = S_{AO ″ B} - (2 S_{Δ OAO ″} - S_{AOB})

(29)

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

(30)

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

As shown in Figure 5

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

(31)

S_{A' B'} = S_{A' O ″ B'} - (2 S_{OA' O ″} - S_{A' OB'})

(32)

p_{O, O ″}^{a} = \frac{S_{AB} - S_{A' B'}}{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

Degree = \sum_{n \in N^{a} / {O}} p_{O, n}

(34)

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

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

(35)

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

Criterion = Degree * 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}, \vec{L^{s}})$ .

Service mapping pre-process

1. SSP

Service subgraph $G^{c} (N^{c}, \vec{L^{c}})$ composed of ASs related to the specific request, comes from the whole service dependency graph $G^{s} (N^{s}, \vec{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^{v} (N^{v}, \vec{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{matrix} SNPS (Re q_{k}, A S_{k, j}) = {c s_{k, j, i} | Utility (Re q_{k}, c s_{k, j, i}) \\ \geq U_{th}, E_{remain}^{k, j, i} - Δ E_{proc}^{k, j, i} * \frac{Tas k_{k, j}}{f_{k, j, i}} \geq E_{th}} \end{matrix}

(37)

where $Tas k_{k, j}$ represents the size of tasks assigned on the $A S_{k, j}$ node by $Re q_{k}$ . The unit of $Tas k_{k, j}$ is megacycle and can be obtained with the method of Chun et al.³⁴ $U_{th}$ and $E_{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}}{Π} (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}} = Δ E_{n, H_{n}}

(39)

Δ E_{n, H_{n}} = \sum_{h \in H_{n}} w_{h} * (Δ E_{Tx}^{n, h} + Δ E_{Rx}^{h})

(40)

where

w_{h} = \frac{p_{n, h}^{a} \underset{x \in H_{n} / {h}}{Π} (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 $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 $dst$ . This is an iterative formula based on which we can search the optimal subgraph from $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 $Data (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 $dst$ . If it is satisfied, add the node to $F$ . After the traversal is completed, if $src$ is unknown, then we select the node as $src$ with the smallest $D$ in SNPS and BFS the optimal $subgraph (src, dst)$ based on $F$ of each node. At last, updating the status of relative nodes and links. However, if $D_{src} = \infty$ , which means there is no subgraph existing, then return Ø.

Algorithm 2. Optimal anypath network subgraph
Require: $G^{a} (N^{a}, L^{a})$ , $dst$ , $SNPS (Re q_{k}, A S_{k, j})$ , $src$
1: priority queue for nodes which still need to find optimal $D$ ordered by their current $D$ : $PQ$ ;
2: for all node $n \in N^{a}$ do
3: $D_{n} \Leftarrow \infty$ ;
4: $F_{n} \Leftarrow Ø$ ;
5: end for
6: $D_{dst} \Leftarrow 0$ ;
7: $PQ \Leftarrow N^{a}$ ;
8: while $PQ \neq Ø$ do
9: $n \Leftarrow PQ$ .removeSmallest();
10: for all node $h \in H_{n}$ && $d_{h, dst}^{a} \geq d_{n, dst}^{a}$ && $b_{n, h}^{a} \geq b_{th}$ do
11: if $D_{h} > D_{n}$ && $E_{remain}^{n} - Δ E_{Rx}^{n} * \frac{Data}{r} \geq E_{th}$ then
12: $H \Leftarrow F_{h} \cup {n}$ ;
13: if $E_{remain}^{h} - \sum_{δ \in H} Δ E_{Tx}^{h, δ} * \frac{Data}{r} \geq E_{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_{remain}^{n} \Leftarrow E_{remain}^{n} - Δ E_{Rx}^{n} * \frac{Data}{r}$ ;
17: end if
18: end if
19: end for
20: end while
21: if $src = null$ then
22: $src \Leftarrow$ the node providing $c s_{k, j, i}$ in SNPS with the smallest $D$ ;
23: end if
24: if $D_{src} = \infty$ then
25: return $s rc, Ø$ ;
26: end if
27: BFS the $subgraph (src, dst)$ based on the $F$ of each node;
28: Update relative nodes and links;
29: return $src, subgraph (src, 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}, \vec{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 $ma p_{k} < A S_{k, j}, n >$ ;
6: for $j = 1$ to $K$ do
7: Find the relative $A S_{j}$ according to $Re q_{k}$ and get $G^{c} (N^{c}, \vec{L^{c}})$ ;
8: $G^{v} (N^{v}, \vec{L^{v}}) \Leftarrow SSP (G^{c} (N^{c}, \vec{L^{c}}))$ ;
9: $list \Leftarrow$ BFS nodes backward from $V_{D}$ ;
10: for $j = 1$ to $list .$ size() do
11: Calculate $SNPS (Re q_{k}, A S_{k, j})$ ;
12: for each incoming edge $A S_{k, z}, A S_{k, j}$ do
13: $dst \Leftarrow ma p_{k} . get (A S_{k, j})$ ;
14: if $ma p_{k} . get (A S_{k, z}) = null$ then
15: $\begin{matrix} src, subgraph (src, dst) \Leftarrow \\ OANS (G^{a} (N^{a}, L^{a}), dst, \\ SNPS (Re q_{k}, A S_{k, z}), null) \end{matrix}$ ;
16: else
17: $src \Leftarrow ma p_{k} . get (A S_{k, z})$ ;
18: $\begin{matrix} subgraph (src, dst) \Leftarrow \\ OANS (G^{a} (N^{a}, L^{a}), dst, \\ SNPS (Re q_{k}, A S_{k, z}), src) \end{matrix}$ ;
19: end if
20 if $subgraph (src, dst) = Ø$ then
21: $Re q_{k}$ Failure; Process;
22: Process $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.

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.

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 m, v_{\min} = 0 - 0.2 m / s, v_{\max} = 0.8 - 1.2 m / s, T = 10 s, and r = 10 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 $src$ and $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.

Footnotes

Handling Editor: Michel Kadoch

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Cong Du

References

Zhang

Chen

Cheng

. Integrating events into SOA for IoT services. IEEE Commun Mag 2017; 55(9): 180–186.

Kyusakov

Eliasson

Delsing

, et al. Integration of wireless sensor and actuator nodes with IT infrastructure using service-oriented architecture. IEEE Trans Ind Inform 2013; 9(1): 43–51.

Garriga

Mateos

Flores

, et al. RESTful service composition at a glance. J Netw Comput Appl 2016; 60: 32–53.

Erl

. Service-oriented architecture: concepts, technology, and design. Concepts 2005; 118(2): 33–37.

Sonntag

Karastoyanova

. Next generation interactive scientific experimenting based on the workflow technology. In: Proceedings of the 21st IASTED international conference on modeling and simulation, Prague, 15 July 2010. Calgary, AB, Canada: ACTA Press.

Zhu

Bastani

Yen

, et al. Automated holistic service composition: modeling and composition reasoning techniques. In: International conference on web services (ICWS), Honolulu, HI, 25–30 June 2017. New York: IEEE.

Cardoso

Sheth

Miller

, et al. Quality of service for workflows and web service processes. J Web Semant 2004; 1(3): 281–308.

Jatoth

Gangadharan

Buyya

. Computational intelligence based QoS-aware web service composition: a systematic literature review. IEEE Trans Serv Comput 2015; 10: 475–492.

Mohamed

Al-Jaroodi

. A survey on service-oriented middleware for wireless sensor networks. Service-Orient Comput Appl 2011; 5(2): 71–85.

10.

Tong

Chen

. Energy-aware service selection and adaptation in wireless sensor networks with QoS guarantee. IEEE Trans Serv Comput. Epub ahead of print 5 September 2017. DOI: 10.1109/TSC.2017.2749227.

11.

Deng

Huang

Taheri

, et al. Mobility-aware service composition in mobile communities. IEEE Trans Syst Man Cybernet 2016; 47: 555–568.

12.

Sun

Zhao

. A decomposition-based approach for service composition with global QoS guarantees. Inform Sci 2012; 199: 138–153.

13.

Deng

, et al. Service selection for composition with QoS correlations. IEEE Trans Serv Comput 2014; 9(2): 201–303.

14.

Wang

. Exploiting mobility prediction for dependable service composition in wireless mobile ad hoc networks. IEEE Trans Serv Comput 2011; 4(1): 44–55.

15.

Chen

Cardozo

Clarke

. Goal-driven service composition in mobile and pervasive computing. IEEE Trans Serv Comput 2018; 11: 49–62.

16.

Geyik

Szymanski

Zerfos

. Robust dynamic service composition in sensor networks. IEEE Trans Serv Comput 2013; 6(4): 560–572.

17.

Heinzelman

Chandrakasan

Balakrishnan

. Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd annual Hawaii international conference on system sciences, Maui, HI, 7 January 2000, pp.3005–3014. New York: IEEE.

18.

Bakaraniya

Mehta

. K-LEACH: an improved LEACH protocol for, lifetime improvement in WSN. Int J Eng Trends Technol 2013; 4(5): 1521–1526.

19.

Basu

Khan

Little

TDC

. A mobility based metric for clustering in mobile ad hoc networks. In: Proceedings of the 21st international conference on distributed computing systems workshops, Mesa, AZ, 16–19 April 2001, pp.413–418. Washington, DC: IEEE Computer Society.

20.

Leng

Zhang

Chen

, et al. A novel k-hop compound metric based clustering scheme for ad hoc wireless networks. IEEE Trans Wireless Commun 2009; 8(1): 367–375.

21.

Sakhaee

Jamalipour

. A new stable clustering scheme for pseudo-linear highly mobile ad hoc networks. In: IEEE global telecommunications conference, Washington, DC, 26–30 November 2007, pp.1169–1173. New York: IEEE.

22.

Qin

Xiao

, et al. Modeling and analysis of data aggregation from convergecast in mobile sensor networks for industrial IoT. IEEE Trans Ind Inform 2018; 14: 4457–4467.

23.

Nie

Asmare

, et al. Towards distributed SDN: mobility management and flow scheduling in software defined urban IoT. IEEE Trans Parallel Distrib Syst. Epub ahead of print 28 November 2018. DOI: 10.1109/TPDS.2018.2883438.

24.

Arkhipov

Kim

, et al. ADDSEN: adaptive data processing and dissemination for drone swarms in urban sensing. IEEE Trans Comput 2016; 66(2): 183–198.

25.

Jiang

, et al. QoS-aware automatic service composition: a graph view. J Comput Sci Technol 2011; 26(5): 837–853.

26.

Zhou

Zhang

, et al. Energy-efficient optimization for concurrent compositions of WSN services. IEEE Access 2018; 5: 19994–20008.

27.

Ngoko

Goldman

Milojicic

. Service selection in web service compositions optimizing energy consumption and service response time. J Inter Serv Appl 2013; 4(1): 19.

28.

Zhang

Lin

. Efficient algorithms for Web services selection with end-to-end QoS constraints. ACM Trans 2007; 1: 6.

29.

Yan

, et al. A QoS-driven approach for semantic service composition. In: IEEE Conference on commerce & enterprise computing, Vienna, 20–23 July 2009. New York: IEEE.

30.

Zhong

Wang

Nelakuditi

, et al. On selection of candidates for opportunistic anypath forwarding. ACM SIGMOBILE Mob Comput CommunReview 2006; 10(4): 1–2.

31.

Laufer

Dubois-Ferrière

Kleinrock

. Multirate anypath routing in wireless mesh networks. In: Proceedings of IEEE INFOCOM, Rio de Janeiro, Brazil, 19–25 April 2009. New York: IEEE.

32.

Wen

Zhang

Luo

. Energy-optimal mobile application execution: taming resource-poor mobile devices with cloud clones. In: Proceedings of IEEE INFOCOM, Orlando, FL, 25–30 March 2012. New York: IEEE.

33.

Heinzelman

. Application-specific protocol architectures for wireless networks. Doctoral Dissertation, Massachusetts Institute of Technology, Cambridge, MA, 2000.

34.

Chun

Ihm

Maniatis

, et al. CloneCloud: elastic execution between mobile device and cloud. In: Proceedings of the 6th conference on computer systems, Salzburg, 10–13 April 2011. New York: ACM.

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

Abstract

Keywords

Introduction

Related work

Mathematical model and problem description

Service model

Network model

QoS model

Request preference

Energy model

Service mapping

Energy optimization for the service composition in the WSN

Service management based on cluster

Service mapping pre-process

Service mapping process

Multi-requests execution process

Simulation

SSP

OANS

SMN

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References