Service-Oriented Node Scheduling Schemes with Energy Efficiency in Wireless Sensor Networks

Abstract

The wireless sensor network is expected to provide various data sensing services by employing the advantage of dense deployment. Energy efficiency is an important criterion for many applications since the sensor nodes are generally budgeted by limited battery. In this paper, we are concerned with the node scheduling problem to provide the required services for the service-oriented wireless sensor network. We firstly propose an Energy-aware Centralized Heuristic Scheme (ECHS) for the problem in which an energy-aware benefit function is used to determine active sensor nodes and rotate sensor nodes by periodically reconstructing the scheduling scheme. We also present an Energy-aware Distributed Heuristic Scheme (EDHS) as the distributed version. Extensive simulation is performed to evaluate the proposed schemes, and the results show that the two schemes have better performance compared with related works.

1. Introduction

Wireless sensor network (WSN) [1] is emerging as an important technology, which includes hundreds or thousands of self-organized sensor nodes connected by wireless communications. These sensor nodes are generally designed with lower-energy units and their cheapness and self-organization characteristics make it possible to deploy the network in various applications, such as environment data collection, industrial process monitoring and control, and machine health monitoring. The rapid development and deployment of sensor technology involve many new type sensors that are equipped with different sensing components. One important trend for the sensor networks is to provide various services to users, and service-oriented wireless sensor network has been proposed as an important solution for the future of sensor networks [2–7]. It can be seen that the current wireless sensor networks are generally data centric or application centric which leads to many obvious disadvantages, such as lacking both uniform operations and a standard representation for sensor data that can be used by diverse sensor applications [4]. The service-oriented wireless sensor networks can support different applications in more general and flexible way, which helps to improve the network performance and also leads to some other advantages, for example, the resource sharing among applications and efficient collection of the information generated by heterogeneous sensor nodes. However, service is not a pure new term and it may be a task of data sensing [8, 9] or a software component provided by sensors [10]. In case the task of data sensing is considered as service, different services provided by the network are helpful to gather different types of sensed data in the monitored area, such as temperature, humidity, sound, or motion. To provide all these different services is one challenge issue for the future service-oriented wireless sensor networks.

In general, a lot of redundancy and correlation occur among the sensed data especially in wireless sensor networks due to the following observations. Firstly, the network is intended to deploy in dense way so that the node failure and other faults can be tolerant to support the network to work in proper way. Secondly, the sensed data depends on the location of nodes as well as the event source. The data of adjacent nodes is generally correlated since they observe the same physical phenomena in the same geographic region [11–13]. Obviously, it is not efficient to wake up all nodes in the network to collect data and provide services since it leads to unnecessary energy consumption due to the data redundancy among neighbor nodes. It means that the sensor nodes should be organized in one more efficient way to enlarge the network lifetime while the required services are guaranteed. It leads to the problem of scheduling large numbers of sensor nodes in an energy-efficient way to support various services in the service-oriented wireless sensor networks.

In order to conserve energy resources and extend network lifetime, one important idea is to schedule the nodes in the network. The scheduling techniques generally select a group of nodes in each epoch, and the selected nodes work in active mode to provide the required services, while other nodes are kept in sleep mode in order to reduce energy consumption since that the sleep mode consumes only a small fraction of energy compared to the active mode [14, 15]. The scheduling problems in wireless sensor network are widely investigated in the literature recently [16–19], but most of them focus on fully different research issues, such as target tracking, coverage, topology control.

However, the node scheduling problem in the service-oriented sensor networks is not only to select a set of nodes to provide the required services during each epoch but also to choose the service each active node should provide. Furthermore, different services in the sensor network have different metrics in the applications, such as different importance (profit) of the applications and different amount of resources (requirement) required in providing the service [20–22]. How to measure the importance of these different services is one challenge issue in the network. Since the sensor is generally budgeted by limited battery, and the network lifetime is the most important criterion for the wireless sensor networks, we introduce the profit to describe the benefit received from one service when it is provided by the network. Generally, the service is more preferred in case that its profit is larger than others in the network since it is helpful to improve the network performance.

Figure 1 shows an example including seven sensor nodes supporting two different services. In Figure 1(a), the circle represents sensor node, the triangle denotes sensing target (we assume that each sensing target is combined with one different service), and the dotted line indicates that nodes within the event area are available to support corresponding service. In this example, service $s_1$ is supported by nodes $n_1$ , $n_2$ , $n_3$ , and $n_4$ , and $s_2$ is supported by nodes $n_4$ , $n_5$ , $n_6$ , and $n_7$ . Assume that the selected number of nodes is at least two for each service. Obviously, there are several ways to schedule nodes to provide the required services, and Figure 1(b) shows two of them. The major difference between them is the second epoch in which the first scheduling selects $\{n_3,n_4\}$ to provide $s_1$ , while the second scheduling selects $\{n_4,n_7\}$ to provide $s_2$ . As shown in Figure 1(a), the network can only support one service in the next epoch due to the lack of resources if we use the above two scheduling schemes. However, in case that service $s_1$ is more crucial than service $s_2$ (i.e., service profit of $s_1$ is larger than $s_2$ ), scheduling 1 is preferred compared with scheduling 2 because it can obtain more profit for the network.

Figure 1

An example to demonstrate the node scheduling problem in service-oriented wireless sensor networks.

In this paper, we study the energy-efficient node scheduling problem in service-oriented wireless sensor networks by adopting profit to measure the network performance, and aim at maximizing the total profit during the network lifetime. Since this problem is proven to be NP-hard [20, 21], we propose two heuristic schemes with energy efficiency. The main contributions of this paper are summarized as follows. (1) We have proposed an Energy-aware Centralized Heuristic Scheme (ECHS) in which an energy-aware benefit function is used to determine the state of nodes as well as the corresponding services provided by each active node. The function takes into account both the capabilities of providing services and the residual energy of nodes, which is helpful to improve the network performance as demonstrated in the simulation results. (2) We have designed a distributed solution for this problem, namely, Energy-aware Distributed Heuristic Scheme (EDHS), in which one header is assigned to each service and the scheduling scheme is carried out in a distributed way that only local information is necessary for the active node selection process.

The rest of this paper is organized as follows. In Section 2, we present the related works. Section 3 introduces the network model and the problem formulation. In Sections 4 and 5, we introduce the centralized and distributed node scheduling schemes, respectively. Section 6 provides performance comparison by detailed simulation. And Section 7 is the conclusion.

2. Related Works

Recently, the service-oriented wireless sensor networks appear as a new emerging trend for the future of wireless sensor networks, which are generally considered as a service provider. It leads to the idea of service-oriented wireless sensor networks [2, 3]. Gračanin et al. [2] proposed a service-centric model, which provides a general and flexible framework for wireless sensor networks. This model consists of mission, network, region, sensor, and capability layers. Within each layer, there are four planes or functionality sets: communication, management, application, and generational learning. Rezgui and Eltoweissy [3] introduced service-oriented sensor-actuator networks as an approach for building a new generation of open, efficient, interoperable, scalable, and application-aware sensor-actuator networks. In this approach, sensor-actuator networks would providing sensing and actuation services to any application, rather than provide sensing and actuation capabilities to a specific application.

Some researchers focused on building the platform/middleware to provide various services in the wireless sensor networks. Mohamed and Al-Jaroodi [5] surveyed the challenges and requirements of service-oriented middleware for wireless sensor network and reviewed some representative approaches. Familiar et al. [6] presented a service-oriented middleware that implements an agent-based virtual sensor service abstraction in ubiquitous smart environments. This middleware offers a lightweight service-oriented framework for sensor networks, with compact service exposure and dynamic virtual service composition through the use of semantic tags. In [7], a service-oriented architecture called TinySOA is proposed, which provides a high-level abstraction for the development of applications in wireless sensor networks. In addition, TinySOA allows application developers to access sensor networks from their applications using a simple service-oriented API via the programming language of their choice, which helps to relive application developers from dealing with the low-level technical details of the sensor networks. Zhang et al. [8] considered the sensor data as the service and designed an open community-oriented platform. The proposed platform allowed users to discover reusable data and data analysis tools and to integrate them into value-added workflows.

To provide various services satisfying the requirement of client applications is an important design goal in the service-oriented sensor networks, and several works have been done to achieve the efficiency of supporting services. Cheng et al. [9] investigated the node selection problem with data accuracy guarantee in service-oriented wireless sensor networks by exploiting the spatial correlation between the service data. However, the proposed algorithms select active sensor nodes without considering energy efficiency that may lead to shorter network lifetime. Geyik et al. [23] proposed a graph-based model for describing sensor services and formulated the process of dynamic sensor service composition as a cost-optimization problem that is shown to be NP-complete. The objective of this problem is to minimize the total cost of the component services that are selected for the composition. Besides, they designed two heuristic algorithms for service composition problem that differ in the direction of traversing the service graph during the composition process. Wang et al. [10] introduced the service-availability-aware sleep scheduling, which aimed to minimize the energy consumption, and guaranteed that there are enough active sensors providing each required service in the system at any time. They considered the wake-up energy consumption and developed approximation algorithms based on LP relaxation. However, they assumed that each service needs fixed number of nodes in order to process the service in the system. In fact, sensor nodes might have different capacities in providing services due to the fact that they have different distances to the monitored target.

Node scheduling is an efficient way to prolong the network lifetime with respect to a network with nodes always on [14]. Under different application backgrounds and assumptions, researchers have proposed many schemes to determine how many and which nodes should be put into sleep mode. Zhao et al. [16] presented a sleep-scheduling technique called Virtual Backbone Scheduling (VBS), which forms multiple overlapped backbones that work alternatively. The rotation of multiple backbones helps to balance the energy consumption of all sensor nodes, which fully utilizes the energy and prolongs the network lifetime. Lin et al. [17] explored the node scheduling scheme for target tracking. Their scheme selects multiple sensors to track target collaboratively such that it achieves better tracking accuracy and reliability with respect to single-sensor-based schemes. Zorbas et al. [18] proposed a cover sets-based node scheduling technique for solving coverage problem, which adopts the strategy that produces both disjoint cover sets, that is, cover sets with no common sensor nodes, and nondisjoint cover sets. In [19], the minimum energy broadcast problem was formulated as the problem of finding the minimum Connected Dominating Set (CDS), and a Minimum Energy-consumption Broadcast scheme (MEBS) was proposed that aimed at providing an efficient scheduling scheme with maximized network lifetime.

Node scheduling in service-oriented wireless sensor network should determine the states of sensor nodes, that is, sleep or active, and the service should provide when a sensor node is in active state. In [20], sensor-mission (service) assignment problem was investigated with the objective of maximizing the achieved profit, which was shown to be NP-hard. In this problem, the profit is a property of services indicating their importance as well as the reward for their execution. They modeled this problem as a weighted bipartite graph whose vertex sets consist of sensors and services and discussed some of its variants. Furthermore, they proposed a centralized Greedy algorithm and a distributed Energy-aware Dynamic Proposal Algorithm (EDPA). The Greedy algorithm repeatedly attempted the highest-potential-profit untried service that can be satisfied with the greatest profit using the currently available sensors. The EDPA algorithm uses information about the current energy level of sensors to make better decisions, which helps to improve the network lifetime. Furthermore, the EDPA algorithm adopts the strategy that sensor nodes are allowed to be stolen by other services, while it may lead to a large amount of messages exchange. Johnson et al. [21] extended the work of [20], and proposed a multiround proposal algorithm called MRGAP, which treats the services as knapsacks that together form an instance of the Generalized Assignment Problem (GAP). Moreover, Porta et al. [22] extended the work of [20, 21] into the environment that sensor nodes equipped with energy harvesting components. The proposed scheduling algorithm exploits not only the nodal residual energy, but also takes into account the energy that is expected to be harvested in the future, which can ensure that the required energy of sensor nodes is always available regardless of the fact that its source is battery or harvesting. However, their solution assumed that the distribution of services' profit and requirement is known a priori, which may not be the case in practice. Recently, Cho et al. [24] proposed a multiple dynamic mission (service) assignment problem for tactical mobile ad hoc networks. The proposed solution is based on combinatorial auction theory, which can minimize communication overhead while maximizing node utilization and mission completion ratio. In this paper, we aim at the node scheduling problem with energy efficiency in the service-oriented wireless sensor networks. We present two heuristic node scheduling schemes that exploit redundancy among sensed data to conserve energy while preserving the availability of required services.

3. System Model and Problem Formulation

In this section, we first introduce the system model as well as the definition of network lifetime and then formulate the node scheduling problem in the service-oriented wireless sensor networks. To be convenient, the symbols used in this work are summarized in Abbreviations Section.

3.1. System Model

We consider a wireless sensor network in the plane consisting of a set of nodes $N=\{n_1,n_2,\dots ,n_n\}$ . Suppose that every node has limited sensing range $R_s$ and communication range $R_c$ . The initial energy of each node is denoted as E. Then, the senor network can be described as an undirected graph $G=(N,L)$ , where N denotes the set of nodes and L denotes the set of links. There is a link ( $n_i,n_j$ ) in case that nodes $n_i$ and $n_j$ are within the transmission range of each other. We also assume that all nodes are stationary and each node knows its geographic location [25, 26].

The service in the wireless sensor network is considered as a sensing task for a specific target located as a stationary position, and all the services provided in the network is notated as $S=\{s_1,s_2,\dots ,s_m\}$ . In this paper, we use a triple ( $l_j,d_j,p_j$ ) to describe the property for a given service $s_j$ , where $l_j$ is the geographic location of the sensing target in the field, $d_j$ is the service requirement which indicates the amount of sensing resources it needs, and $p_j$ is the profit of the service which indicates both its importance and the reward achieved by the network for its execution. Generally, these services are fully separate and we assume there is no correlation relationship among them in this paper.

For a given sensing task located at a given position, the corresponding service is generally provided by several nodes. Each node whose sensing range covers the task position has contribution to the service, and here we denote the effect of node $n_i$ to provide service $s_j$ as $e_{i,j}$ . Generally, we have $e_{i,j}=0$ in case that node $n_i$ cannot provide service $s_j$ or service $s_j$ is located outside of the sensing range of $n_i$ . We also assume that the value $e_{i,j}$ for service $s_j$ is additive [21]. It shall be mentioned that the value of $e_{i,j}$ depends on the practical scenario and the sensing object and is generally considered as one preknown parameter for the node scheduling problem. However, there are several models that can be used to formulate this parameter. For example, the distance-based model is proposed in [20–22], which can be described as

$$\begin{array}{cc}& e_{i,j}=\{\begin{array}{cc}\frac{\mathrm{1}}{\mathrm{1}+D_{i,j}^{\mathrm{2}}/c},\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}{D}_{i,j}^{}\le R_s,\hfill \\ \mathrm{0},\hfill & \text{otherwise},\hfill \end{array}\end{array}$$

(1)

where $D_{i,j}$ is the Euclidean distance between node $n_i$ and the sensing target of service $s_j$ and $\hspace{0.17em}c$ is the decay factor. This model follows typical signal attenuation models in which signal strength decays inversely with distance squared.

In the practical application, some nodes might be deployed in an area far away from the sensing task and they cannot provide the required services due to the limited sensing range. In this case, the effect for this given service is zero. However, such nodes can be used to forward the collected data to the sink since the sensor networks always run in ad hoc model. On the other hand, one node is feasible to provide a given service only in case that the service is located in the sensing range.

3.2. Network Lifetime

The network lifetime is one of the most important metrics for the wireless sensor networks, and there are various measurements for network lifetime, such as the first node to die, the number of alive nodes, and the fraction of alive nodes [27, 28]. In this paper, we focus on the problem of how to schedule nodes in an efficient way to provide required services. Due to the fact that the sensor network is generally densely deployed, the network can still keep on providing required services although the first node is already dead since there is data redundancy among the adjacent nodes. Let AN(t) be the number of nodes that are alive and also available to provide services at time slot t, and the network lifetime TL is defined as follows in this paper:

$$\begin{array}{cc}& \text{TL}=\max \left\{t:\text{AN}\left(t\right)\ge \tau \text{AN}\left(\mathrm{0}\right)\right\},\end{array}$$

(2)

where τ denotes a given alive nodes threshold. It is obvious that the network lifetime indicates the time-period during which the wireless sensor network can keep on providing the required services.

3.3. Problem Formulation

The problem studied in this paper is to find a schedule for each node so that the required services in the sensor network can be guaranteed. In some special case, it might be impossible to satisfy all the constraints required by all services in the network due to the lack of resources. Then the network intends to provide the service with higher importance, which is generally described as the profit of the service. Meanwhile, the network has better performance when it supports more services during its lifetime. In this way, we aim at maximizing the total profit during the network lifetime for the node scheduling problem.

The total network profit is calculated as the sum of the profits achieved over all time slots during the network lifetime. Let $x_{i,j,t}$ be a binary variables (0 or 1), where $x_{i,j,t}$ is 1 if and only if node $n_i$ is active and assigned to provide $s_j$ at time slot t, and $\{x_{i,j,t}\}$ indicates one scheduling scheme for the given wireless sensor network at time slot t. In some cases, the services are still tolerant with acceptable quality even though the required resources are partly satisfied. Based on the above observation, we adopt a simple model to describe the profit obtained during the service providing process. Let $y_{j,t}$ denote the stratification level of service requirement at time slot t, the profit $p_j(y_{j,t})$ which is obtained by providing service $s_j$ at time slot t can be formulated as follows [20, 21]:

$$\begin{array}{cc}& p_j\left(y_{j,t}\right)=\{\begin{array}{cc}{p}_j,\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}{y}_{j,t}\ge \mathrm{1},\hfill \\ p_j·y_{j,t},\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}{T}_{\mathrm{sat}}\le y_{j,t}<\mathrm{1},\hfill \\ \mathrm{0},\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}{y}_{j,t}<T_{\mathrm{sat}},\hfill \end{array}\end{array}$$

(3)

where $y_{j,t}={\sum }_{i=\mathrm{1}}^n{x}_{i,j,t}{e}_{i,j}/d_j$ .

Given a set of nodes $N=\{n_1,n_2,\dots ,n_n\}$ , a set of services $S=\{s_1,s_2,\dots ,s_m\}$ , the requirement $d_j$ and profit $p_j$ for each service $s_j\in S$ , and the service effect $e_{i,j}$ for each node $n_i\in N$ and each service $s_j\in S$ , the node scheduling problem for the service-oriented wireless sensor network is to find a set of scheduling schemes $\{x_{i,j,1}\},\{x_{i,j,2}\},\dots ,\{x_{i,j,\text{TL}}\}$ , so that the total achieved profit of the network, that is, ${\sum }_{t=\mathrm{1}}^{\text{TL}}\hspace{0.17em}{\sum }_{j=\mathrm{1}}^m{p}_j(y_{j,t})$ is maximized.

The node scheduling problem studied in this paper has been proven to be NP-hard [20, 21], which means that it is impossible to find optimal solution in polynomial time. In this work, we develop two heuristic schemes to obtain sub-optimal solution, namely, energy-aware centralized heuristic scheme (ECHS) and energy-aware distributed heuristic scheme (EDHS).

4. Centralized Scheme

The basic idea for the proposed Energy-aware Centralized Heuristic Scheme (ECHS) can be described as follows. (1) Use a novel heuristic approach to construct a scheduling scheme based on the concept of energy-aware benefit function and a greedy strategy aiming at minimizing the number of selected nodes. (2) Secondarily, reconstruct the scheduling scheme after the time expires by replacing the selected nodes that have low level of residual energy with the unselected nodes that have high level of residual energy. The second process continues until the fraction of alive nodes is below a given threshold τ , and finally the network ends.

In this section, we first introduce the novel energy-aware benefit function and then describe the procedure of initial scheduling construction and the swapping procedure, respectively; finally, we describe the detailed process of the proposed ECHS.

4.1. Energy-Aware Benefit Function

Here we introduce a novel energy-aware benefit function that is used as metric to sort nodes during the node selection process. We consider three important factors for the benefit function, that is, the node's service effect for a service, the remaining requirement of a service, and the node's residual energy. Let $u_j$ be the sum of the selected nodes' service effect for service $s_j$ . Then, the remaining requirement of service $s_j$ can be described as $(d_j-u_j)$ . The nodes with larger service effect and higher level of residual energy are preferred to be selected so that the number of required nodes can be minimized. Meanwhile, the part of service effect that exceeds the requirement is generally neglected since the solution only needs to satisfy the requirement. In this way, the benefit function is formulated as follows:

$$\begin{array}{cc}& f\left(e_{i,j},{\text{RE}}_i\right)=\frac{\min \left(e_{i,j},d_j-u_j\right)}{d_j}·{\left(\frac{{\text{RE}}_i}{E}\right)}^{\beta },\end{array}$$

(4)

where ${\text{RE}}_i$ denotes the current residual energy of node $n_i$ and $\beta \hspace{0.17em}\hspace{0.17em}(\beta \ge 0)$ is a given parameter. Note that β represents the trade-off between the service effect and the residual energy, and the scheme intends to select nodes with larger residual energy rather than better service effect in case that the value of β is larger.

4.2. Initial Scheduling Construction

The basic idea of the initial scheduling construction is that we select a minimum number of nodes for each required service in a separate way, and the union of selected nodes for all services is considered as a scheduling scheme. Note that all the selected nodes will switch into active state to provide corresponding service when scheduling process has been finished. We prefer to select nodes for services that have more profit but fewer requirements for resources so that the network can achieve larger profit with less number of active nodes. Thus, we firstly sort services and then select nodes for services with the above energy-aware benefit function in the sequence. The selection process for each service terminates if the service requirement is satisfied or no more nodes can be found.

There are two different states for the nodes during the scheduling construction process, UNSELECTED and SELECTED. Nodes in the SELECTED state are scheduled to provide the required service, and nodes in UNSLECTED are candidates, which are possible to change to SELECTED in the next time slot. Here, we introduce a new notation, $B_{i,j}$ , to denote the profit contribution of node $n_i$ for providing service $s_j$ , where $B_{i,j}=e_{i,j}·p_j/d_j$ . It is obvious that node $n_i$ contributes more profit to the network if the assigned service $s_j$ has larger $B_{i,j}$ . Consequently, we determine node $n_i\in N$ as a candidate node for service $s_j$ in case that $n_i$ is UNSELECTED and $e_{i,j}>0$ , or if $n_i$ is selected by another service, for example, service $s_k$ , and $B_{i,j}>B_{i,k}$ . It means that the network profit might be increased by changing $n_i$ to provide service $s_j$ .

Redundancy might occur when the selected nodes have fully satisfied services' requirement because the node selection process considers both the service effect and the residual energy. For example, consider service $s_1$ with requirement $d_1=0.5$ and candidate nodes are assumed to be $n_1$ , $n_2$ , and $n_3$ . Suppose that these nodes' service effect and fraction of residual energy are (0.3, 0.8), (0.1, 1.0) and (0.2, 0.4), respectively. We also assume that $\beta =\mathrm{1}$ in (4). It is seen that $n_1$ , $n_2$ , and $n_3$ will be selected simultaneously. However, the requirement of service $s_1$ can be guaranteed by $n_1$ and $n_3$ , which means $n_2$ is a redundant node. The basic idea to eliminate these redundant nodes is described as follows. In case that a service, for example, $s_j$ , is fully satisfied with its requirement for resources, we will firstly sort the selected nodes for service $s_j$ in increasing order of service effect $e_{i,j}$ , and then remove nodes from the selected nodes in sequence until the requirement $d_j$ cannot be guaranteed by the rest nodes. The pseudocode for the initial scheduling construction is listed in Procedure 1.

Procedure 1: Initial scheduling construction.

Input:  N, S, $d_j$ and $p_j$ for each $s_j\in S$ , $e_{i,j}$ for each $n_i\in N$ and $s_j\in S$ , and $T_{\mathrm{sat}}$ .

Output:  A scheduling scheme.

(1) Initialize all nodes as UNSELECTED;

(2) $S^{\prime }\leftarrow S$ ;

(3) while   $S^{\prime }\ne \varnothing$

(4)  Search candidate nodes for each service $s_j\in S^{\prime }$ , and calculate the maximum achieved

   profit $p_{\max }$ (j) that $s_j$ is provided by all candidate nodes;

(5)  Select the one $s_j$ from $S^{\prime }$ with maximum $p_{\max }$ (j)/ $d_j$ ;

(6)  Select nodes for $s_j$ from candidate nodes in decreasing order of f( $e_{i,j}$ , ${\text{RE}}_i$ )

   until the requirement of $s_j$ is satisfied, and neglect the node which is SELECTED

   and the reassignment  will cause previously assigned service failed;

   set these selected nodes as SELECTED;

(7)  Search redundant nodes, and set them as UNSELECTED;

(8)  If the satisfaction level of $s_j$ is less than threshold $T_{\mathrm{sat}}$ , change the selected

   nodes for $s_j$ to UNSELECTED;

(9)   $S^{\prime }\leftarrow S-\{s_j\}$ ;

(10) end  while

4.3. Swapping Procedure

The objective of swapping is to balance the energy consumption of nodes selected in the previous initial scheduling construction procedure, which aims at finding enough nodes to provide services and match the requirements. In case those nodes with lower energy are selected to provide the services, these nodes will run to death, which finally results in other serious issues such as network partition and failure to provide the services. In this way, to balance the residual energy is one important way to extend the network lifetime.

In this section, we introduce a novel swapping procedure used to replace some low-energy SELECTED nodes with high-energy UNSELECTED nodes. A decrement of the network profit is helpful to find candidates for the selected nodes whose contribution to the network is rather small it is possible to provide more benefit services (i.e., services with larger value of $B_{i,j}$ ) in the subsequent times. In this paper, we adopt ( $1-{\text{RE}}_i/E$ ) ( $\max B_{i,j}-B_{i,k}$ ) as the maximum acceptable profit decrement when we perform swapping for selected node $n_i$ that assigned to service $s_k$ .

The pseudo-code for the swapping procedure is listed in Procedure 2. Firstly, calculate the average residual energy of all the selected nodes and denote it as $E_{\text{avg}}$ (in Line 1). Secondarily, initialize node list RList with the selected nodes whose residual energy is less than $E_{\text{avg}}$ and then sort RList in increasing order (in Lines 2-3); Finally, perform swapping operation for node in RList in sequence (in Lines 4–9). The swapping operation is done as follows. Given a node $n_i$ that assigned to provide $s_k$ , we firstly calculate the minimum acceptable level of achieved profit for $s_k$ that indicates that the achieved profit is not less than it after swapping (in Line 6). Secondarily, searchs candidate nodes with residual energy larger than $E_{\text{avg}}$ from these unselected nodes (in Line 7). Finally, check candidate nodes and select one to replace $n_i$ , if no candidate node can be found and the network profit is still within acceptable level, $n_i$ will be released (in Line 8).

Procedure 2: Swapping procedure.

Input:  N, S, $d_j$ and $p_j$ for each $s_j\in S$ , $e_{i,j}$ for each $n_i\in N$ , and $s_j\in S$ , $T_{\mathrm{sat}}$ , and a scheduling scheme.

Output:  An improved scheduling scheme.

(1) $E_{\text{avg}}\leftarrow$ average residual energy of all nodes in SELECTED state;

(2) Initial node list RList with the nodes in SELECTED state and their residual energy is less than $E_{\text{avg}}$ ;

(3) Sort RList in increasing order of residual energy;

(4) for each node $n_i$ in RList

(5)   $s_k\leftarrow$ the assigned service of $n_i$ ;

(6)  Calculate acceptable level of profit for $s_k$ ;

(7)  Search candidate nodes for $n_i$ from nodes in UNSELECTED state with residual energy

   larger than $E_{\text{avg}}$ and $e_{i,k}>\mathit{0}$ ;

(8)  Select one node as the replacement of $n_i$ from candidate nodes with the constraints that

   achieved profit of $s_k$ is within acceptable level and the satisfaction level of $s_k$

   is not less than threshold $T_{\mathrm{sat}}$ ; if no such a replacement node is found, change $n_i$

   to UNSELECTED state in case that above constraints can be satisfied, otherwise swap

   the state of $n_i$ and its replacement node;

(9) end  for

4.4. Scheme Description

With the above description, the detailed ECHS is introduced as follows. The basic idea behind ECHS is that we reconstruct the scheduling scheme periodically or when it is necessary. Consider two special conditions that the scheduling scheme is rebuilt: (1) the scheduling scheme runs for $T_{\max }$ time slots; (2) some selected nodes are unable to provide services due to the fact that they run out of energy. The process of node scheduling will continue until the network ends; that is, $\text{AN}(t)<\tau \text{AN}(\mathrm{0})$ . Algorithm 1 provides details of pseudo-code for ECHS.

Algorithm 1: Energy aware centralized heuristic scheme (ECHS).

Input:  N, S, $d_j$ and $p_j$ for each $s_j\in S$ , $e_{i,j}$ for each $n_i\in N$ , and $s_j\in S$ , τ, $T_{\mathrm{sat}}$ , and $T_{\max }$ .

Output:  A scheduling scheme.

(1) Run Procedures 1 and 2 in sequence and get a scheduling scheme;

(2) Provide services under the scheduling scheme;

(3) Calculate the residual energy of nodes as well as AN(t), if AN $(t)\ge \tau$ AN(0) is not satisfied, go to step 5;

(4) If the scheduling scheme has been used for $T_{\max }$ time slots or there exists active nodes

  with residual energy cannot support service in the scheduling scheme, go to step 1, otherwise go to step 2;

(5) The network ends.

5. Distributed Scheme

The centralized heuristic schemes are generally efficient to find a suboptimal solution and it can be carried out on one powerful node, that is, the sink, which supports a large amount of computation and heavy communication tasks. This centralized nature requires that the sink knows the global information of the network and results in better scheduling scheme. However, in the practical applications, it is usually difficult and costly to gather a large amount of information to the sink and disseminate schedules from the sink to all other nodes especially in networks deployed in large scale. Distributed scheduling is often performed by each node in the network that only local information necessary to determine whether one node is active or not. Thus, it is more practical to deploy distributed scheduling schemes in the wireless sensor networks.

The proposed EDHS assigns a specific node as the header for each service, and the header performs a local node scheduling to select node resources for the given service. The other nodes in the network are called normal node. The EDHS consists of three phases: the data collection phase, the node selection phase, and maintenance phase. In the data collection phase, nodes collect information of required services, and then the EDHS chooses initial header node for each service. In the node selection phase, the headers select active nodes to provide services. After schedules are constructed on nodes, the nodes begin to execute their schedules and provide required services. To rotate active nodes and balance the energy consumption among nodes, the nodes will reenter the node selection phase when necessary. The details of each phase are described in the following sections.

5.1. Data Collection Phase

In this phase, each node detects sensing targets within its sensing range and the node closest to a specific sensing target will be elected as an initial header node. Then, the sink node transmits service information including profit and requirement to the corresponding header node. After receiving the information, the header node also broadcasts the service information to its neighbors. In case that a normal node receives the service information, it checks whether it is available to provide this service and drops this message if not or this message is received already; otherwise the node sends the message to neighbors and stores the information of corresponding header node for this service. Then, each normal node transmits its service effect and residual energy to the corresponding header node. The header node maintains one node table, and each entry has the following fields: node ID, service effect and residual energy. The residual energy of each node defines the reluctance or willingness of that node to provide the service. Because current energy levels of nodes are accordingly changed with the running of the network, nodes periodically update the residual energy to the header nodes so that the header nodes can select suitable nodes to provide services. This message also can be delivered in a piggyback fashion during the service data gathering process.

5.2. Node Selection Phase

In this phase, the header node runs the local node selection scheme and selects a set of active nodes to provide services. The idea of local node selection scheme is similar to the proposed centralized scheme. The difference is that selection process is done with only local information.

The basic selection process for service $s_j$ is described as follows. (1) Firstly, the header node orders the candidates to decrease of $f(e_{i,j},{\text{RE}}_i)$ and choose the nodes one by one until the requirement of $s_j$ is satisfied or there is no available node. (2) Secondarily, remove the redundant nodes by using the idea described in Section 4.2. After the active nodes are selected, the header node sends NOTIFICATION messages including the information of service $s_j$ and $\text{dec}(i,j)$ to these selected nodes. Let $N_j$ be the set of selected nodes for $s_j$ , and let $p_j(N_j)$ be the achieved network profit when $s_j$ is provided by $N_j$ . For each $n_i\in N_j$ , $\text{dec}(i,j)=p_j(N_j)-p_j(N_j-\{n_i\})$ is the network profit decrement when $n_i$ is removed from $N_j$ . Clearly, $\text{dec}(i,j)$ indicates that the level $s_j$ benefits from $n_i$ .

After the NOTIFICATION is sent out, the header node waits for ACCEPTANCE messages from the selected nodes. When the timer expires, the header node checks ACCEPTANCE messages and determines whether the number of nodes that agree to provide $s_j$ is enough or not. If it is not, the header node selects more nodes from candidates and modifies the selected nodes set $N_j$ accordingly. This process continues until the service requirement is satisfied. However, the process terminates if the header node cannot select enough nodes to meet with the service satisfaction threshold $T_{\mathrm{sat}}$ , and then the service is not provided in the current time slot.

The initial state for a normal node, that is, $n_i$ , is either UNSELECTED or SELECTED for a given service $s_k$ . During the node selection phase, $n_i$ just waits for NOTIFICATION, and selects the $s_j$ with maximum $\text{dec}(i,j)$ from all the received NOTIFICATION messages when the timer expires. In case that the initial state is UNSELECCTED, $n_i$ changes to SELECTED and sends an ACCEPTANCE message to the header node. Otherwise, it is obvious that $n_i$ has already been selected to provide another service, that is, $s_k$ . In case that $\text{dec}(i,j)>\text{dec}(i,k)$ , $n_i$ sends a MODIFICATION message to the header node of service $s_k$ to rearrange the schedule and an ACCEPTANCE message to the header node of service $s_j$ . In case that the header node of service $s_k$ receives MODIFICATION message, it will remove the corresponding node from $N_j$ and continue the node selection process for $s_k$ .

5.3. Maintenance Phase

In order to balance the residual energy among all nodes, the proposed EDHS adopts the similar strategy to reconstruct the scheduling scheme: reconstruct the selected nodes set when the scheduling scheme runs for a predefined time slots denoted as $T_{\max }$ or some selected nodes are unable to provide the required services due to lack of energy. Once the reconstruction is triggered, the header nodes just reset the selected nodes into UNSELECTED, and then the selection phase starts again.

As we can see, the header node plays an important role in the proposed EDHS and shall be replaced in case that its energy is below a given threshold. The new header node can be elected by the old header node since it has collected all information of neighbor nodes that are available to provide the corresponding service. Note that the header node provides the required service too, and so the new header node shall be selected by means of the energy-aware benefit function described in Section 4.1 with $u_j=\mathrm{0}$ . However, if several header nodes intend to select the same node as their new headers, the selected node generally chooses the service with maximum service effect. Once the new header is chosen, the elder one delivers CHANGE messages to all normal nodes of the service to notify the new header node so that the normal nodes can record the new header.

6. Simulation Results and Analysis

In this section, we present our simulation results demonstrate the performance and effectiveness of proposed schemes. We first introduce the building process of our simulation, then analyze the impact of parameter β of the energy-aware benefit function, and compare these schemes with related works.

6.1. Simulation Setup

We use MATLAB as the simulation platform that is used popularly as the simulation tools of wireless networks. All the experiments are implemented on a PC with Intel Pentium 3.0 GHz and 4 GB RAM. In our simulations, sensor nodes and sensing targets are randomly and uniformly distributed in a square sensing field. The service profit and requirement are also randomly generated. Note that we focuse on the problem of scheduling nodes to provide services and thus only energy consumption during the service providing process is considered in this paper. Assume that one node spends a certain amount of energy $E_c$ in one time slot if it is active and spends zero energy otherwise. The service satisfaction threshold $T_{\mathrm{sat}}$ is assumed to be 50%, which means that at least half of the service requirement shall be received. The simulation setting is summarized in Table 1. The final results are the average values of 100 different scenarios.

Table 1

Simulation setting.

Sensing field	200 m × 200 m
Number of nodes	200, …, 500
Number of services	10, …, 50
Requirements for services	$[$ 0.2, 1.2 $]$
Profits for services	$[$ 1, 10 $]$
Service satisfaction threshold $T_{\mathrm{sat}}$	50%
Initial energy of nodes E	100 unit
Energy consumption $E_c$	0.1 unit
Sensing range $R_s$	30 m
Communication range $R_c$	40 m
Decay factor c	60
Maximum time period for reconstructing scheduling $T_{\max }$	50
Alive nodes threshold τ	0.5, …, 1.0

6.2. Impact of Parameter β

The parameter β is an important factor used in the energy-aware benefit function as described in Section 4.1, and it is helpful to ensure trade-off between the residual energy and service effect of nodes during the node selection process. Figure 2 shows the results of network profit achieved by ECHS and EDHS with different value of β, respectively. The simulation is done with 300 nodes and the fraction of alive nodes threshold, τ, is set as 0.8. We compare the performance with different numbers of services when the parameter βvaries from 0 to 3 in steps of 0.5. As we can see from Figure 2, the achieved network profit increases together with β, and then it begins to stabilize when β is larger than 0.5, which demonstrates that the residual energy has more impact on the energy-aware benefit function when β is larger. However, the achieved network profit cannot be further improved when β is larger enough due to the fact that the schemes have distributed energy load evenly among the nodes.

Figure 2

Impact of parameter β on achieved profit, $m\in \{10,20,30,40,50\}$ .

Figure 3 shows the impact of parameter β on the achieved network profit when network size is different. The number of services provided by the network is set as 30, and other settings are identical to those in Figure 2. As we can see from Figure 3, the simulation results are similar to the cases in Figure 2, especially when β is larger. Especially, the network performance is comparatively better when β is 3. Therefore, we choose 3 as the value of β in the following simulations process.

Figure 3

Impact of parameter β on achieved profit, $n\in \{200,300,400,500\}$ .

6.3. Performance Comparison

The related works [20, 21] are most closed to the node scheduling problem in service-oriented wireless sensor networks. In order to evaluate the performance of proposed ECHS and EDHS, we compare them with Greedy and EDPA algorithms proposed in [20], and MRGAP algorithm proposed in [21], in which Greedy and MRGAP are centralized algorithms and EDPA is one distributed algorithm. We employ the following modifications to make above algorithms suitable for solving the node scheduling problem addressed in this paper. (1) Use the proposed energy-aware benefit function during the node selection process for Greedy and MRGAP algorithms since energy of nodes is not considered in these algorithms. (2) Use the same strategy as our schemes to reconstruct the node scheduling scheme.

The first set of experiment is done with 300 nodes and the threshold τ is set as 0.8, and the number of services varies from 10 to 50 in steps of 5. As shown in Figure 4, we have the following two conclusions. (1) The achieved network profit increases together with the number of services, but the trend is not obvious when the number of services is larger enough. Note that the required resource increases with the increasing number of services and thus more profit can be obtained in case that the network provides more services, and the network resources is consumed rapidly so that the network cannot support services in a longer time. Therefore, the achieved network profit increases slowly when the network provides a larger number of services. (2) The ECHS has better performance than MRGAP and Greedy in all cases, and EDHS also has better performance than EDPA.

Figure 4

Achieved profit versus number of services.

The second set of experiment is done with 30 services and the threshold τ is set as 0.8, and the network size varies from 200 to 500 in steps of 50. It can be seen from Figure 5 that the larger network size helps to achieve more profit. This is due to the fact that sensor nodes are the carrier of network resources in the wireless sensor network, and the network much better capabilities has when more nodes are deployed. Furthermore, both ECHS and EDHS run better in this set of experiment. Especially, in case that the network size is 300, ECHS performs 18.0% and 25.0% better than MRGAP and Greedy, respectively, EDHS performs 13.5% better than EDPA. In case that the network size is 500, the performance improvements are 14.6%, 18.8%, and 20.3%, respectively.

Figure 5

Achieved profit versus network size.

The third set of experiment is to evaluate the performance of different algorithms with respect to achieved profit under different threshold τ. The simulation is done with 300 nodes and 30 services, and we vary the threshold τ from 0.5 to 1.0. Figure 6 depicts that the achieved profit of network increases with the decreasing of τ and shows that the network can still provide services when a fraction of nodes run out of energy. However, the network provides worse quality of services when the number of such nodes increases. Therefore, the achieved profit increases slightly in case that τ is small enough. Moreover, it is seen that ECHS outperforms the other algorithms, and EDHS also shows better performance than EDPA. In case that τ is 1.0, the ECHS performs 9.8% and 10.1% better than MRGAP and Greedy. While the value of τ is 0.8, the performance improvements are 17.4 and 24.9%, respectively. In addition, the performance improvement of EDHS to EDPA is 14.7% in case that τ is 1.0 or 0.8.

Figure 6

Achieved profit versus threshold τ.

The simulations that we performed showed that the proposed approaches efficiently construct scheduling schemes and are effective in improving the network performance. The strategy of Greedy algorithm is to repeatedly satisfy the most currently profitable service, which is easy to implement. The MRGAP algorithm treats the problem instance as a Generalized Assignment Problem (GAP) that improves the results of Greedy algorithm. However, the proposed ECHS conserves energy by energy-aware benefit function to select active nodes for the required services and performs swapping operation for nodes with low residual energy. The EDHS can dynamically adjust nodes to provide a service that is more beneficial during the node selection phase. Although the EDPA adopts similar strategies, EDHS selects initial nodes in an efficient way with the help of header nodes and so obtains better performance in the subsequent nodes selection process, as we can see from the simulation results. In the distributed scheduling scheme EDHS, is more difficult to obtain better results than centralized approaches. The localized computation and communication make it more suitable in the practical environment.

7. Conclusion

To develop the service-oriented architecture is an important trend for the future wireless sensor network. In this paper, we are concerned with the node scheduling problem to provide various services with energy efficiency, and we propose two heuristic schemes, namely, Energy-aware Centralized Heuristic Scheme (ECHS) and Energy-aware Distributed Heuristic Scheme (EDHS). The proposed schemes select active nodes based on their contribution to services as well as residual energy, which helps to balance the load of energy consumption in the network. Extensive simulations show that both of the two schemes can significantly improve the performance of the network. In this paper, we use a simplifying energy model that neglects the energy consumed in message exchange. In addition, the temporal/spatial correlations between sensed data are important potential to improve the efficiency of scheduling schemes. In the future, we plan to investigate the node scheduling problem with a practical energy model as well as considering the correlation between sensed data and develop a fully solution in the service-oriented wireless sensor network.