Distributed trajectory design for data gathering using mobile sink in wireless sensor networks

Several studies have demonstrated the benefits of using a mobile sink (MS) to reduce energy consumption resulting from multi-hop data collection using a static sink in wireless sensor networks (WSNs). However, using MS may increase data delivery latency as it needs to visit each sensor node in the network to collect data. This is a critical issue in delay-sensitive applications where all sensed data must be gathered within a given time constraint. In this paper, we propose a distributed data gathering protocol utilizing MS for WSNs. The proposed protocol designs a trajectory for the MS, which minimizes energy consumption and delay. Our protocol operates in four main phases: data sensing, rendezvous point (RP) selection, trajectory design, and data gathering. In data sensing, a number of deployed sensor nodes keep sensing the target field for a specific period of time to capture events. Then, using a cluster-based RP selection algorithm, some sensor nodes are selected to become RPs based on local information. The selected RPs are then used to determine a trajectory for the MS. To do so, we propose three trajectory design algorithms that support different types of applications, namely reduced energy path (REP), reduced delay path (RDP), and delay bound path (DBP). The MS moves through the constructed path to accomplish its data gathering according to an effective scheduling technique that is introduced in this work. We validate the proposed protocol via extensive simulations over several metrics such as energy, delay, and time complexity.     

Minimum spanning tree–based delay‐aware mobile sink traversal in wireless sensor networks

Energy efficient data collection in a delay‐bound application is a challenging issue for mobile sink–based wireless sensor networks. Many researchers have proposed the concept of rendezvous points (RPs) to design the path for the mobile sink. Rendezvous points are the locations in the network where the mobile sink halts and collects data from the nearby sensor nodes. However, the selection of RPs for the design of path has a significant impact on timely data collection from the network. In this paper, we propose an efficient algorithm for selection of the RPs for efficient design of mobile sink trajectory in delay‐bound applications of wireless sensor networks. The algorithm is based on a virtual path and minimum spanning tree and shown to maximize network lifetime. We perform extensive simulations on the proposed algorithm and compare results with the existing algorithms to demonstrate the efficiency of the proposed algorithm of various performance metrics.     

WSNs中基于智能水滴的信宿路径规划算法

为了有效避免无线传感网络(WSNs)中的热点问题,常利用移动信宿收集数据。信宿依据预定路线遍历预定的驻留点(RPs)。而其他传感节点就将数据传输至离自己最近的驻留点。因此,构建最优的RPs非常重要。为此,提出基于智能水滴的信宿路径规划(IWD-SPP)算法。提出IWD-SPP算法的目的在于延长网络寿命,并最小化转发数据包的能量消耗。利用智能水滴算法构建最优的RPs,规划信宿的移动路径。仿真结果表明,提出的IWD-SPP算法在能量消耗和网络寿命方面的性能优于同类算法。     

Energy efficient dispatch strategy for the dual-functional mobile sink in wireless rechargeable sensor networks

Scavenging energy from radio-frequency (RF) signals has drawn significant attention in recent years. By introducing the technology of RF energy harvesting into wireless sensor networks, a new type of network named mobile data gathering based wireless rechargeable sensor network (MGWRSN) is considered in this paper. In the MGWRSN, a dual-functional mobile sink (MS) which has the abilities of data collecting and RF energy generating is employed. Data sensed by sensor nodes is gathered at several selected head nodes (HNs). Through using the RF energy supplied by the MS, the HNs deliver the gathered data to the MS arriving at the corresponding rendezvous points (RPs). In our works, the network energy consumption model of the MGWRSN is built, and the energy efficient dispatch strategy for the MS is studied, aiming at cutting down the total network energy consumption. For the simplest case, i.e., the one-HN MGWRSN, the optimal location of the RP is provided to minimize the total network energy consumption. After that, the researches are extended into the case of multi-HN MGWRSN and a heuristic dispatch strategy named HEEDS is proposed. Theoretical analysis and numerical results show that: (1) in the one-HN MGWRSN, the optimal location of the RP is close related to the data bulk to be transmitted, the unit mobility energy cost, the required bit error rate, the modulation scheme, and the departure position of the MS; (2) comparing with the existing algorithm WRP which directly dispatches the MS to the locations of HNs to collect data, the proposed strategy HEEDS is shown to be more energy efficient. Moreover, when a high energy transfer power is available at the MS, HEEDS renders shorter packet delay compared to WRP.     

A grid based clustering and routing algorithm for solving hot spot problem in wireless sensor networks

Energy conservation of the sensor nodes is the most important issue that has been studied extensively in the design of wireless sensor networks (WSNs). In many applications, the nodes closer to the sink are overburdened with huge traffic load as the data from the entire region are forwarded through them to reach the sink. As a result, their energy gets exhausted quickly and the network is partitioned. This is commonly known as hot spot problem. Moreover, sensor nodes are prone to failure due to several factors such as environmental hazards, battery exhaustion, hardware damage and so on. However, failure of cluster heads (CHs) in a two tire WSN is more perilous. Therefore, apart from energy efficiency, any clustering or routing algorithm has to cope with fault tolerance of CHs. In this paper, we address the hot spot problem and propose grid based clustering and routing algorithms, combinedly called GFTCRA (grid based fault tolerant clustering and routing algorithms) which takes care the failure of the CHs. The algorithms follow distributed approach. We also present a distributed run time management for all member sensor nodes of any cluster in case of failure of their CHs. The routing algorithm is also shown to tolerate the sudden failure of the CHs. The algorithms are tested through simulation with various scenarios of WSN and the simulation results show that the proposed method performs better than two other grid based algorithms in terms of network lifetime, energy consumption and number of dead sensor nodes.     

Multihop data gathering in wireless sensor networks with a mobile sink

Network performance can be improved by using a mobile sink (MS) to collect sensed data in a wireless sensor network. In this paper, we design an efficient trajectory for MS, collecting data from sensor nodes in a multihop fashion, with the aim of prolonging the network lifetime. Considering event‐driven applications, we present an approach to jointly determine the optimal trajectory for MS and data paths and transmission rates from source nodes to MS, without considering any rendezvous points. In these applications, an MS is supposed to harvest the data from source nodes in a given time‐slot. We first show that this problem is in form of a mixed integer nonlinear programming model, which is NP‐hard. Then, to achieve an approximate solution, we divide the mentioned problem into 2 simple subproblems. In fact, after determining an approximate zone for the trajectory of MS, the optimal data paths and transmission rates from source nodes to the MS are obtained through a mathematical optimization model. Finally, to illustrate the efficiency of the proposed approach, we compare the performance of our algorithm to an rendezvous point–based and also the state‐of‐the‐art approach in different scenarios.     

A novel approach for designing delay efficient path for mobile sink in wireless sensor networks

In the recent years, the use of mobile sink has drawn enormous attention for data collection in wireless sensor networks (WSNs). Mobile sink is well known for solving hotspot or sinkhole problem. However, the design of an efficient path for mobile sink has tremendous impact on network lifetime and coverage in data collection process of WSNs. This is particularly an important issue for many critical applications of WSNs where data collection requires to be carried out in delay bound manner. In this paper, we propose a novel scheme for delay efficient trajectory design of a mobile sink in a cluster based WSN so that it can be used for critical applications without compromising the complete coverage of the target area. Given a set of gateways (cluster heads), our scheme determines a set of rendezvous points for designing path of the mobile sink for critical applications. The scheme is based on the Voronoi diagram. We also propose an efficient method for recovery of the orphan sensor nodes generated due to the failure of one or more cluster heads during data collection. We perform extensive simulations over the proposed algorithm and compare its results with existing algorithms to demonstrate the efficiency of the proposed algorithm in terms of network lifetime, path length, average waiting time, fault tolerance and adaptability etc. For the fault tolerance, we simulate the schemes using Weibull distribution and analyze their performances.     

Novel chemical reaction optimization based unequal clustering and routing algorithms for wireless sensor networks

Energy conserving of sensor nodes is the most crucial issue in the design of wireless sensor networks (WSNs). In a cluster based routing approach, cluster heads (CHs) cooperate with each other to forward their data to the base station (BS) via multi-hop routing. In this process, CHs closer to the BS are burdened with heavier relay traffic and tend to die prematurely which causes network partition is popularly known as a hot spot problem. To mitigate the hot spot problem, in this paper, we propose unequal clustering and routing algorithms based on novel chemical reaction optimization (nCRO) paradigm, we jointly call these algorithms as novel CRO based unequal clustering and routing algorithms (nCRO-UCRA). In clustering, we partition the network into unequal clusters such that smaller size clusters near to the sink and larger size clusters relatively far away from the sink. For this purpose, we develop the CH selection algorithm based on nCRO paradigm and assign the non-cluster head sensor nodes to the CHs based on derived cost function. Then, a routing algorithm is presented which is also based on nCRO based approach. All these algorithms are developed with the efficient schemes of molecular structure encoding and novel potential energy functions. The nCRO-UCRA is simulated extensively on various scenarios of WSNs and varying number of sensors and the CHs. The results are compared with some existing algorithms and original CRO based algorithm called as CRO-UCRA to show the superiority in terms of various performance metrics like residual energy, network lifetime, number of alive nodes, data packets received by the BS and convergence rate.     

LUCA: An Energy-efficient Unequal Clustering Algorithm Using Location Information for Wireless Sensor Networks

Over the last several years, various clustering algorithms for wireless sensor networks have been proposed to prolong network lifetime. Most clustering algorithms provide an equal cluster size using node??s ID, degree and etc. However, many of these algorithms heuristically determine the cluster size, even though the cluster size significantly affects the energy consumption of the entire network. In this paper, we present a theoretical model and propose a simple clustering algorithm called Location-based Unequal Clustering Algorithm (LUCA), where each cluster has a different cluster size based on its location information which is the distance between a cluster head and a sink. In LUCA, in order to minimize the energy consumption of entire network, a cluster has a larger cluster size as increasing distance from the sink. Simulation results show that LUCA achieves better performance than conventional equal clustering algorithm for energy efficiency.     

Energy efficient clustering algorithms for wireless sensor networks: novel chemical reaction optimization approach

Clustering has been accepted as one of the most efficient techniques for conserving energy of wireless sensor networks (WSNs). However, in a two-tiered cluster based WSN, cluster heads (CHs) consume more energy due to extra overload for receiving data from their member sensor nodes, aggregating them and transmitting that data to the base station (BS). Therefore, proper selection of CHs and optimal formation of clusters play a crucial role to conserve the energy of sensor nodes for prolonging the lifetime of WSNs. In this paper, we propose an energy efficient CH selection and energy balanced cluster formation algorithms, which are based on novel chemical reaction optimization technique (nCRO), we jointly called these algorithms as novel CRO based energy efficient clustering algorithms (nCRO-ECA). These algorithms are developed with efficient schemes of molecular structure encoding and potential energy functions. For the energy efficiency, we consider various parameters such as intra-cluster distance, sink distance and residual energy of sensor nodes in the CH selection phase. In the cluster formation phase, we consider various distance and energy parameters. The algorithm is tested extensively on various scenarios of WSNs by varying number of sensor nodes and CHs. The results are compared with original CRO based algorithm, namely CRO-ECA and some existing algorithms to demonstrate the superiority of the proposed algorithm in terms of energy consumption, network lifetime, packets received by the BS and convergence rate.     

Data gathering via mobile sink in WSNs using game theory and enhanced ant colony optimization

Optimal performance and improved lifetime are the most desirable design benchmarks for WSNs and the mechanism for data gathering is a major constituent influencing these standards. Several researchers have provided significant evidence on the advantage of mobile sink (MS) in performing effective gathering of relevant data. However, determining the trajectory for MS is an NP-hard-problem. Especially in delay-inevitable applications, it is challenging to select the best-stops or rendezvous points (RPs) for MS and also to design an efficient route for MS to gather data. To provide a suitable solution to these challenges, we propose in this paper, a game theory and enhanced ant colony based MS route selection and data gathering (GTAC-DG) technique. This is a distributed method of data gathering using MS, combining the optimal decision making skill of game theory in selecting the best RPs and computational swarm intelligence of enhanced ant colony optimization in choosing the best path for MS. GTAC-DG helps to reduce data transfer and management, energy consumption and delay in data delivery. The MS moves in a reliable and intelligent trajectory, extending the lifetime and conserving the energy of WSN. The simulation results prove the effectiveness of GTAC-DG in terms of metrics such as energy and network lifetime.

     

Energy Efficient Energy Hole Repelling (EEEHR) Algorithm for Delay Tolerant Wireless Sensor Network

Reducing energy consumption and increasing network lifetime are the major concerns in Wireless Sensor Network (WSN). Increase in network lifetime reduces the frequency of recharging and replacing batteries of the sensor node. The key factors influencing energy consumption are distance and number of bits transmitted inside the network. The problem of energy hole and hotspot inside the network make neighbouring nodes unusable even if the node is efficient for data transmission. Energy Efficient Energy Hole Repelling (EEEHR) routing algorithm is developed to solve the problem. Smaller clusters are formed near the sink and clusters of larger size are made with nodes far from the sink. This methodology promotes equal sharing of load repelling energy hole and hotspot issues. The opportunity of being a Cluster Head (CH) is given to a node with high residual energy, very low intra cluster distance in case of nodes far away from the sink and very low CH to sink distance for the nodes one hop from the sink. The proposed algorithm is compared with LEACH, LEACH-C and SEP routing protocol to prove its novel working. The proposed EEEHR routing algorithm provides improved lifetime, throughput and less packet drop. The proposed algorithm also reduces energy hole and hotspot problem in the network.     

Flow-balanced routing for multi-hop clustered wireless sensor networks

Power efficiency and coverage preservation are two important performance metrics for a wireless sensor network. However, there is scarcely any protocol to consider them at the same time. In this paper, we propose a flow-balanced routing (FBR) protocol for multi-hop clustered wireless sensor networks that attempts to achieve both power efficiency and coverage preservation. The proposed protocol consists of four algorithms, one each for network clustering, multi-hop backbone construction, flow-balanced transmission, and rerouting. The proposed clustering algorithm groups several sensors into one cluster on the basis of overlapping degrees of sensors. The backbone construction algorithm constructs a novel multi-level backbone, which is not necessarily a tree, using the cluster heads and the sink. Furthermore, the flow-balanced routing algorithm assigns the transferred data over multiple paths from the sensors to the sink in order to equalize the power consumption of sensors. Lastly, the rerouting algorithm reconstructs the network topology only in a place where a head drops out from the backbone due to the head running out of its energy. Two metrics called the network lifetime and the coverage lifetime are used to evaluate the performance of FBR protocol in comparison with previous ones. The simulation results show that FBR yields both much longer lifetime and better coverage preservation than previous protocols. For example, FBR yields more than twice network lifetime and better coverage preservation than a previous efficient protocol, called the coverage-preserving clustering protocol (CPCP) [18], when the first sensor dies and the network coverage is kept at 100%, respectively.     

Efficient Approach for Maximizing Lifespan in Wireless Sensor Networks by Using Mobile Sinks

Recently, sink mobility has been shown to be highly beneficial in improving network lifetime in wireless sensor networks (WSNs). Numerous studies have exploited mobile sinks (MSs) to collect sensed data in order to improve energy efficiency and reduce WSN operational costs. However, there have been few studies on the effectiveness of MS operation on WSN closed operating cycles. Therefore, it is important to investigate how data is collected and how to plan the trajectory of the MS in order to gather data in time, reduce energy consumption, and improve WSN network lifetime. In this study, we combine two methods, the cluster‐head election algorithm and the MS trajectory optimization algorithm, to propose the optimal MS movement strategy. This study aims to provide a closed operating cycle for WSNs, by which the energy consumption and running time of a WSN is minimized during the cluster election and data gathering periods. Furthermore, our flexible MS movement scenarios achieve both a long network lifetime and an optimal MS schedule. The simulation results demonstrate that our proposed algorithm achieves better performance than other well‐known algorithms.     

Online Data Gathering for Maximizing Network Lifetime in Sensor Networks

Energy-constrained sensor networks have been deployed widely for monitoring and surveillance purposes. Data gathering in such networks is often a prevalent operation. Since sensors have significant power constraints (battery life), energy efficient methods must be employed for data gathering to prolong network lifetime. We consider an online data gathering problem in sensor networks, which is stated as follows: assume that there is a sequence of data gathering queries, which arrive one by one. To respond to each query as it arrives, the system builds a routing tree for it. Within the tree, the volume of the data transmitted by each internal node depends on not only the volume of sensed data by the node itself, but also the volume of data received from its children. The objective is to maximize the network lifetime without any knowledge of future query arrivals and generation rates. In other words, the objective is to maximize the number of data gathering queries answered until the first node in the network fails. For the problem of concern, in this paper, we first present a generic cost model of energy consumption for data gathering queries if a routing tree is used for the query evaluation. We then show the problem to be NP-complete and propose several heuristic algorithms for it. We finally conduct experiments by simulation to evaluate the performance of the proposed algorithms in terms of network lifetime delivered. The experimental results show that, among the proposed algorithms, one algorithm that takes into account both the residual energy and the volume of data at each sensor node significantly outperforms the others     

Spanning tree based algorithms for low latency and energy efficient data aggregation enhanced convergecast (DAC) in wireless sensor networks

Many wireless sensor networks (WSNs) employ battery-powered sensor nodes. Communication in such networks is very taxing on its scarce energy resources. Convergecast – process of routing data from many sources to a sink – is commonly performed operation in WSNs. Data aggregation is a frequently used energy-conversing technique in WSNs. The rationale is to reduce volume of communicated data by using in-network processing capability at sensor nodes. In this paper, we address the problem of performing the operation of data aggregation enhanced convergecast (DAC) in an energy and latency efficient manner. We assume that all the nodes in the network have a data item and there is an a priori known application dependent data compression factor (or compression factor), γ, that approximates the useful fraction of the total data collected.The paper first presents two DAC tree construction algorithms. One is a variant of the Minimum Spanning Tree (MST) algorithm and the other is a variant of the Single Source Shortest Path Spanning Tree (SPT) algorithm. These two algorithms serve as a motivation for our Combined algorithm (COM) which generalized the SPT and MST based algorithm. The COM algorithm tries to construct an energy optimal DAC tree for any fixed value of α (= 1 − γ), the data growth factor. The nodes of these trees are scheduled for collision-free communication using a channel allocation algorithm. To achieve low latency, these algorithms use the β-constraint, which puts a soft limit on the maximum number of children a node can have in a DAC tree. The DAC tree obtained from energy minimizing phase of tree construction algorithms is re-structured using the β-constraint (in the latency minimizing phase) to reduce latency (at the expense of increasing energy cost). The effectiveness of these algorithms is evaluated by using energy efficiency, latency and network lifetime as metrics. With these metrics, the algorithms’ performance is compared with an existing data aggregation technique. From the experimental results, for a given network density and data compression factor γ at intermediate nodes, one can choose an appropriate algorithm depending upon whether the primary goal is to minimize the latency or the energy consumption.     

Power-Saving Scheduling for Multiple-Target Coverage in Wireless Sensor Networks

We address the multiple-target coverage problem (MTCP) in wireless sensor networks (WSNs). We also propose an energy-efficient sensor-scheduling algorithm for multiple-target coverage (MTC) that considers both the transmitting energy for collected data and overlapped targets. We introduce two algorithms: one optimal, the other heuristic. Simulation results show that the proposed algorithms can contribute to extending the lifetime of network and that the heuristic algorithm is more practical than the optimal algorithm with respect to complexity.     

A Location-less Energy Efficient Algorithm for Load Balanced Clustering in Wireless Sensor Networks

One of the biggest challenges in Wireless Sensor Networks (WSNs) is to efficiently utilise the limited energy available in the network. In most cases, the energy units of sensors cannot be replaced or replenished. Therefore, the need for energy efficient and robust algorithms for load balancing in WSNs is ever present. This need is even more pronounced in the case of cluster-based WSNs, where the Cluster Head (CH) gathers data from its member nodes and transmits this data to the base station or sink. In this paper, we propose a location independent algorithm to cluster the sensor nodes under gateways, as CHs into well defined, load balanced clusters. The location-less aspect also avoids the energy loss in running GPS modules. Simulations of the proposed algorithm are performed and compared with a few existing algorithms. The results show that the proposed algorithm shows better performance under different evaluation metrics such as average energy consumed by sensor nodes vs number of rounds, number of active sensors vs number of rounds, first gateway die and half of the gateways die.

     

An Energy-Efficient Routing Algorithm Based on Relative Identification and Direction for Wireless Sensor Networks

In studies of wireless sensor networks (WSNs), routing protocols in network layer is an important topic. To date, many routing algorithms of WSNs have been developed such as relative direction-based sensor routing (RDSR). The WSNs in such algorithm are divided into many sectors for routing. RDSR could simply reduce the number of routes as compared to the convention routing algorithm, but it has routing loop problem. In this paper, a less complex, more efficient routing algorithm named as relative identification and direction-based sensor routing (RIDSR) algorithm is proposed. RIDSR makes sensor nodes establish more reliable and energy-efficient routing path for data transmission. This algorithm not only solves the routing loop problem within the RDSR algorithm but also facilitates the direct selection of a shorter distance for routing by the sensor node. Furthermore, it saves energy and extends the lifetime of the sensor nodes. We also propose a new energy-efficient algorithm named as enhanced relative identification and direction-based sensor routing (ERIDSR) algorithm. ERISDR combines triangle routing algorithm with RIDSR. Triangle routing algorithm exploits a simple triangle rule to determine a sensor node that can save more energy while relaying data between the transmitter and the receiver. This algorithm could effectively economize the use of energy in near-sensor nodes to further extend the lifetime of the sensor nodes. Simulation results show that ERIDSR get better performance than RDSR, and RIDSR algorithms. In addition, ERIDSR algorithm could save the total energy in near-sensor nodes more effectively.     

Fault-tolerant monitor placement for out-of-band wireless sensor network monitoring

Monitoring a sensor network to quickly detect faults is important for maintaining the health of the network. Out-of-band monitoring, i.e., deploying dedicated monitors and transmitting monitoring traffic using a separate channel, does not require instrumenting sensor nodes, and hence is flexible (can be added on top of any application) and energy conserving (not consuming resources of the sensor nodes). In this paper, we study fault-tolerant out-of-band monitoring for wireless sensor networks. Our goal is to place a minimum number of monitors in a sensor network so that all sensor nodes are monitored by k distinct monitors, and each monitor serves no more than w sensor nodes. We prove that this problem is NP-hard. For small-scale network, we formulate the problem as an Integer Linear Programming (ILP) problem, and obtain the optimal solution. For large-scale network, the ILP is not applicable, and we propose two algorithms to solve it. The first one is a ln(kn) approximation algorithm, where n is the number of sensor nodes. The second is a simple heuristic scheme that has much shorter running time. We evaluate our algorithms using extensive simulation. In small-scale networks, the latter two algorithms provide results close to the optimal solution from the ILP for relatively dense networks. In large-scale networks, the performance of these two algorithms are similar, and for relatively dense networks, the number of monitors required by both algorithms is close to a lower bound.