CWSC: Connected k-coverage working sets construction algorithm in wireless sensor networks

One of the most important issues for wireless sensor networks is to get a long network lifetime without affecting either communication connectivity or sensing coverage. Many sensors that are deployed randomly in a dense sensor network in a redundant way waste a lot of energy. One effective way to save energy is to let only a subset of sensors work at any given time. In this paper, we mainly consider such a problem. Selecting the minimum number of connected sensor nodes that can provide k-coverage (k ≥ 1), i.e., selecting a subset S of working sensors, such that almost every point in the sensing region can be covered by at least k sensors and the sensors in S can form a connected communication subgraph. We propose a connected k-coverage working sets construction algorithm (CWSC) based on Euclidean distance to k-cover the sensing region while minimizing the number of working sensors. CWSC can produce different coverage degrees according to different applications, which can enhance the flexibility of the sensor network. Simulation results show that the proposed algorithm, which can conserve energy and prolong the lifetime of the sensor network, is better than the previous 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     

Energy efficient path selection for mobile sink and data gathering in wireless sensor networks

Mobile sink (MS) has drawn significant attention for solving hot spot problem (also known as energy hole problem) that results from multihop data collection using static sink in wireless sensor networks (WSNs). MS is regarded as a potential solution towards this problem as it significantly reduces energy consumption of the sensor nodes and thus enhances network lifetime. In this paper, we first propose an algorithm for designing efficient trajectory for MS, based on rendezvous points (RPs). We next propose another algorithm for the same problem which considers delay bound path formation of the MS. Both the algorithms use k-means clustering and a weight function by considering several network parameters for efficient selection of the RPs by ensuring the coverage of the entire network. We also propose an MS scheduling technique for effective data gathering. The effectiveness of the proposed algorithms is demonstrated through rigorous simulations and comparisons with some of the existing algorithms over several performance metrics.     

Multi-covered path in wireless sensor networks

The progress of development on sensor networks has inspired many new applications. Some of these applications require the target to be observed by more than one sensors simultaneously. Sensor coverage, which reflects how well a sensor network is monitored by sensors, is an important measure for the quality of service (QoS) that a sensor network can provide. In this paper, we addressed the coverage problem from two different view points and referred to them as the worst-case and best-case coverage problems. Most existing works on these two problems assumed that the coverage degree is one (i.e. the target area falls within the sensing range of at least one sensor). In this paper, we address the k-coverage problem, where the coverage degree is a user-defined parameter k. This is a generalization of the earlier work where only k=1 is assumed. By combining geometric and algorithmic techniques, we establish optimal algorithms to solve the two variants of the k-coverage problem in polynomial time. An important extension of our study on the k-coverage problem was also proposed: the distributed algorithm for the problem. This helps in applying the proposed algorithm under more practical scenarios.     

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.     

Dynamic clustering approach with ACO-based mobile sink for data collection in WSNs

Enhancing the network lifetime of wireless sensor networks is an essential task. It involves sensor deployment, cluster formation, routing, and effective utilization of battery units. Clustering and routing are important techniques for adequate enhancement of the network lifetime. Since the existing clustering and routing approaches have high message overhead due to forwarding collected data to sinks or the base station, it creates premature death of sensors and hot-spot issues. The objective of this study is to design a dynamic clustering and optimal routing mechanism for data collection in order to enhance the network lifetime. A new dynamic clustering approach is proposed to prevent premature sensor death and avoid the hot spot problem. In addition, an Ant Colony Optimization (ACO) technique is adopted for effective path selection of mobile sinks. The proposed algorithm is compared with existing routing methodologies, such as LEACH, GA, and PSO. The simulation results show that the proposed cluster head selection algorithm with ACO-based MDC enhances the sensor network lifetime significantly.

     

Connected sensor cover: self-organization of sensor networks for efficient query execution

Spatial query execution is an essential functionality of a sensor network, where a query gathers sensor data within a specific geographic region. Redundancy within a sensor network can be exploited to reduce the communication cost incurred in execution of such queries. Any reduction in communication cost would result in an efficient use of the battery energy, which is very limited in sensors. One approach to reduce the communication cost of a query is to self-organize the network, in response to a query, into a topology that involves only a small subset of the sensors sufficient to process the query. The query is then executed using only the sensors in the constructed topology. The self-organization technique is beneficial for queries that run sufficiently long to amortize the communication cost incurred in self-organization. In this paper, we design and analyze algorithms for suchself-organization of a sensor network to reduce energy consumption. In particular, we develop the notion of a connected sensor cover and design a centralized approximation algorithm that constructs a topology involving a near-optimal connected sensor cover. We prove that the size of the constructed topology is within an O(logn) factor of the optimal size, where n is the network size. We develop a distributed self-organization version of the approximation algorithm, and propose several optimizations to reduce the communication overhead of the algorithm. We also design another distributed algorithm based on node priorities that has a further lower communication overhead, but does not provide any guarantee on the size of the connected sensor cover constructed. Finally, we evaluate the distributed algorithms using simulations and show that our approaches results in significant communication cost reductions.     

Improved clustering with firefly-optimization-based mobile data collector for wireless sensor networks

To maximize the network lifetime of a wireless sensor network, an efficient transmission technique is critical. The energy constraint is a crucial factor in the sensor network because the sensor nodes are typically battery-run and it is impossible or difficult to recharge them in most application scenarios. Unbalanced data transference in the communication channel frequently produces an energy hole problem, which causes the premature death of the sensor nodes and reduces the network lifetime. To resolve this issue and improve the network lifetime, the proposed approach adjusts the transmission range according to the distances between the cluster heads and their members. Furthermore, a mobile data collector based on the firefly optimization algorithm is employed to increase the network lifetime. The proposed algorithm is compared with standard benchmark algorithms in several scenarios. The simulation results demonstrate that the proposed algorithm outperforms existing algorithms with respect to the network lifetime.     

An Energy-Balanced Data Gathering Algorithm for Linear Wireless Sensor Networks

Aiming at the data unbalance of sensor nodes in the wireless sensor networks (WSN), this paper mainly studies the data gathering algorithm for linear WSNs. As the data amount varies from the time spent on data gathering of entire network minimal, it is a key factor to balance energy consumption and further prolong the network lifetime. Therefore, this paper proposes a TDMA scheduling algorithm for general k-hop networks, and takes detail performance analysis on the algorithm. Furthermore, we present the method of selecting the optimal hop-count and its formula as well as the formula of the number of timeslots required for converge-cast in order to maximize network lifetime. Finally, we obtain some general conclusions of network optimization based on the theoretical analysis and simulations. Compared with the 1-hop algorithm in (C. Florens and R. McEliece, Packets Distribution Algorithms for Sensor Networks, IEEE INFOCOM, San Diego, pp. 1063–1072, 2003), the TDMA scheduling algorithm for the general k-hop network proposed in our paper is more universal and has more practical application value.     

On delay-minimized data harvesting with mobile elements in wireless sensor networks

We consider the problem of routing and scheduling a set of mobile elements that act as mechanical carriers of data, harvesting them from sensor nodes and delivering them to a sink. The objective is to minimize the data delivery latency. Most of the existing work has focused on designing delay minimizing routes for the mobile nodes by leveraging variants of the Traveling Salesman Problem (TSP). We show that TSP-based routes can lead to delay that is arbitrarily worse than the optimal. The main insight is that as data generation rates of sensors may vary, some sensors need to be visited more frequently than others. To that end, we consider a network with a single sink and develop a path splitter algorithm that “splits” a TSP-based route into several loops intersecting at the sink. Numerical results show that our algorithm can improve average delay by more than 40% in some instances while requiring a modest computational effort to modify the TSP-based route. The work is useful in prolonging sensor network lifetime and in relaying data in partitioned networks.     

Lifetime Maximization Based on Coverage and Connectivity in Wireless Sensor Networks

We consider information retrieval in a wireless sensor network deployed to monitor a spatially correlated random field. We address optimal sensor scheduling and information routing under the performance measure of network lifetime. Both single-hop and multi-hop transmissions from sensors to an access point are considered. For both cases, we formulate the problems as integer programming based on the theories of coverage and connectivity in sensor networks. We derive upper bounds for the network lifetime that provide performance benchmarks for suboptimal solutions. Suboptimal sensor scheduling and data routing algorithms are proposed to approach the lifetime upper bounds with reduced complexity. In the proposed algorithms, we consider the impact of both the network geometry and the energy consumption in communications and relaying on the network lifetime. Simulation examples are used to demonstrate the performance of the proposed algorithms as compared to the lifetime upper bounds.     

Multi-objective Binary Reinforced Cuckoo Search Algorithm for Solving Connected Coverage target based WSN with Critical Targets

In the stream of WSN, covering the targets using sensors and communication among the sensors to forward the data packets is a prime challenge due to the sparse target locations. Dedicated sensors lead more installation cost and significant amount of maintenance needs to be charged. Coverage of multiple targets by few sensors leads to network failure in case if any sensor runs out of power. Targets in sparse region also should be considered into account while sensing the environment. Hence in this paper, an effective multi-objective connected coverage target based WSN algorithm is proposed namely Multi-Objective Binary Cuckoo Search algorithm. The proposed model also handles the critical targets in the given sensing region. The algorithms hold the potentiality to handle minimized sensor deployment, maximized coverage and connectivity cost simultaneously. The proposed model is compared with the state of art algorithms to prove its significance. Two dedicated simulation region is developed in a large scale to examine the efficiency of the proposed algorithm. The results shows the significance of the proposed model over existing algorithms.

     

Increasing lifetime of wireless sensor networks using controllable mobile cluster heads

In a static wireless sensor network (WSN), sensors close to the base station (BS) run out of energy at a much faster rate than sensors in other parts of the network. This is because the sensor close to the BS always relays the data for other sensors, resulting in an unequal distribution of network residual energy. In this paper, we propose a scheme for enhancing the network lifetime using multiple mobile cluster heads (CHs) that can move in the WSN in a controllable manner. The CH controllably moves toward the energy‐rich sensors or the event area, offering the benefits of maintaining the remaining energy more evenly, or eliminating multihop transmission. Therefore, the proposed scheme increases the network lifetime. We theoretically analyze the energy consumption in our scheme and propose three heuristical mobility strategies. We further study the collaboration among CHs in order to maintain their connectivity to the BS to ensure the delay requirement for real‐time applications. Simulation shows that network lifetime is increased by upto 75% over existing approach by making CHs always move toward a stable equilibrium point. Our connectivity algorithm provides a best case improvement of 40% in transmission delays over existing schemes. Copyright © 2009 John Wiley & Sons, Ltd.     

Performance evaluation of sensor deployment using optimization techniques and scheduling approach for K-coverage in WSNs

In the wireless sensor networks, sensor deployment and coverage are the vital parameter that impacts the network lifetime. Network lifetime can be increased by optimal placement of sensor nodes and optimizing the coverage with the scheduling approach. For sensor deployment, heuristic algorithm is proposed which automatically adjusts the sensing range with overlapping sensing area without affecting the high degree of coverage. In order to demonstrate the network lifetime, we propose a new heuristic algorithm for scheduling which increases the network lifetime in the wireless sensor network. Further, the proposed heuristic algorithm is compared with the existing algorithms such as ant colony optimization, artificial bee colony algorithm and particle swarm optimization. The result reveals that the proposed heuristic algorithm with adjustable sensing range for sensor deployment and scheduling algorithm significantly increases the network lifetime.     

Energy-efficient skyline query optimization in wireless sensor networks

With the deployment of wireless sensor networks (WSNs) for environmental monitoring and event surveillance, WSNs can be treated as virtual databases to respond to user queries. It thus becomes more urgent that such databases are able to support complicated queries like skyline queries. Skyline query which is one of popular queries for multi-criteria decision making has received much attention in the past several years. In this paper we study skyline query optimization and maintenance in WSNs. Specifically, we first consider skyline query evaluation on a snapshot dataset, by devising two algorithms for finding skyline points progressively without examining the entire dataset. Two key strategies are adopted: One is to partition the dataset into several disjoint subsets and produce the skyline points in each subset progressively. Another is to employ a global filter that consists of some skyline points in the processed subsets to filter out unlikely skyline points from the rest of unexamined subsets. We then consider the query maintenance issue by proposing an algorithm for incremental maintenance of the skyline in a streaming dataset. A novel maintenance mechanism is proposed, which is able to identify which skyline points from past skylines to be the global filter and determine when the global filter is broadcast. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithms on both synthetic and real sensing datasets, and the experimental results demonstrate that the proposed algorithms significantly outperform existing algorithms in terms of network lifetime prolongation.     

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.

     

基于ERPMT改进启发式方法的WSN寿命最大化算法

针对传感器节点的电池容量限制导致无线传感网络寿命低的问题,基于容量最大化(CMAX)、线上最大化寿命(OML)两种启发式方法以及高效路由能量管理技术(ERPMT),提出了基于ERPMT改进启发式方法的无线传感网络寿命最大化算法。首先,通过启发式方法初始化每个传感器节点,将节点能量划分为传感器节点起源数据和其它节点数据延迟;然后利用加入的一种优先度量延迟一跳节点的能量消耗;最后,根据路径平均能量为每个路由分配一个优先级,并通过ERPMT实现最终的无线传感网络优化。针对不同分布类型网络寿命的实验验证了本文算法的有效性及可靠性,实验结果表明,相比较为先进的启发式方法CMAX及OML,本文算法明显增大了无线传感网络的覆盖范围,并且大大地延长了网络的寿命。     

A Novel Verification Scheme for Fine-Grained Top-k Queries in Two-Tiered Sensor Networks

A two-tiered architecture with resource-rich master nodes at the upper tier and resource-poor sensor nodes at the lower tier is expected to be adopted in large scale sensor networks. In a hostile environment, adversaries are more motivated to compromise the master nodes to break the authenticity and completeness of query results, whereas it is lack of light and secure query processing protocol in tiered sensor networks at present. In this paper, we study the problem of verifiable fine-grained top- $k$ queries in two-tiered sensor networks, and propose a novel verification scheme, which is named Verification Scheme for Fine-grained Top- $k$ Queries (VSFTQ). To make top- $k$ query results verifiable, VSFTQ establishes relationships among data items of each sensor node using their orders, which are encrypted together with the scores of the data items and the interested time epoch number using distinct symmetric keys kept by each sensor node and the network owner. Both theoretical analysis and simulation results show that VSFTQ can not only ensure high probability of detecting forged and/or incomplete query results, but also significantly decrease the amount of verification information when compared with existing schemes.     

Scheduling algorithms for extending directional sensor network lifetime

Recently, directional sensor networks that are composed of a large number of directional sensors have attracted a great deal of attention. The main issues associated with the directional sensors are limited battery power and restricted sensing angle. Therefore, monitoring all the targets in a given area and, at the same time, maximizing the network lifetime has remained a challenge. As sensors are often densely deployed, a promising approach to conserve the energy of directional sensors is developing efficient scheduling algorithms. These algorithms partition the sensor directions into multiple cover sets each of which is able to monitor all the targets. The problem of constructing the maximum number of cover sets has been modeled as the multiple directional cover sets (MDCS), which has been proved to be an NP-complete problem. In this study, we design two new scheduling algorithms, a greedy-based algorithm and a learning automata (LA)-based algorithm, in order to solve the MDCS problem. In order to evaluate the performance of the proposed algorithms, several experiments were conducted. The obtained results demonstrated the efficiency of both algorithms in terms of extending the network lifetime. Simulation results also revealed that the LA-based algorithm was more successful compared to the greedy-based one in terms of prolonging network lifetime.     

一种基于超节点和能量优先的无线传感器网络的高效查询算法

文中提出一种基于超节点和能量优先的无线传感器网络的高效查询算法.该算法包括传感器节点的层次聚类算法及基于能量代价模型等支撑技术,主要解决了以下两个问题:(1)数据如何从传感器节点传送到汇聚节点;(2)通过对传感器节点进行聚类,形成超节点,使得在查询过程中减少对无关节点的访问.实验表明该算法在提高无线传感器网络查询效率的情况下,延长网络的使用寿命.