On-line disjoint path routing for network capacity maximization in energy-constrained ad hoc networks

In this paper we consider on-line disjoint path routing in energy-constrained ad hoc networks. The objective is to maximize the network capacity, i.e. maximize the number of messages routed successfully by the network without any knowledge of future disjoint path connection request arrivals and generation rates. Specifically, in this paper we first present two centralized on-line algorithms for the problem. One is based on maximizing local network lifetime, which aims to minimize the transmission energy consumption, under the constraint that the local network lifetime is no less than γ times of the optimum after the realization of each disjoint path connection request, where γ is constant with 0 < γ  1. Another is based on the exponential function of energy utilization at nodes, and the competitive ratio of this latter algorithm is also analyzed if admission control mechanism is employed. We then conduct extensive experiments by simulations to analyze the performance of the proposed algorithms, in terms of network capacity, network lifetime, and the transmission energy consumption for each disjoint path connection request. The experimental results show that the proposed algorithms outperform those existing algorithms that do not take into account the power load balancing at nodes in terms of maximizing the network capacity.     

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.

     

Time synchronization algorithm of wireless sensor networks based on data aggregation tree

Time synchronization is a critical technique of wireless sensor networks (WSNs). Aimed at the disadvantages of hierarchical time synchronization algorithm, this paper proposes an improved algorithm used for WSNs based on data aggregation tree. Based on collection and selection principles of multiple time data point tuples, the relative time drift and phase offset of the node are calculated through linear programming method, and time synchronization is achieved eventually during the establishment of data aggregation tree. Performance analysis and simulation results prove that, compared with the existing time synchronization algorithms, the proposed algorithm can reduce the energy cost of nodes and shorten the time of synchronization effectively.     

Optimized asset planning for minimizing latency in wireless sensor networks

Wireless Sensor Networks (WSNs) has been attracting lots of interest in recent years. In such networks sensors data are collected over multi-hop routes at one or multiple base-stations (gateway nodes) for processing. In many WSN applications such as disaster management and combat field surveillance, rapid response to detected events is necessary and thus data latency should be minimal. Given the sensor’s energy and radio range constraints, direct communication with the gateway is inefficient and often infeasible for most deployed sensors. An intuitive approach to limit data latency is to increase the population of gateways and place them in the vicinity of sensors. However, gateway nodes are typically costly and thus it is desired to limit their count. Therefore, there is a need to balance between such conflicting requirements. In this paper, we pursue an integrated approach to asset planning in WSNs so that the data latency is minimized. The goal is to determine the least number of gateways and identify where to place them in the network in order to achieve a certain delay bound on data delivery. We formulate an optimization model for the asset planning problem and present effective algorithms for solving it. The proposed solution scheme employs contemporary search heuristics such as k-means and genetic algorithms. Validation results confirm the effectiveness of our approach in achieving the desired design goals.     

传感器网络中基于最短路径树的低延时节能路由算法

借助图论中最短路径和最小生成树的原理,在无线传感器网络中构建若干棵以Sink节点为根的最短路径源路由树。与最小生成树相比,最短路径树能保证路径上大部分节点找到节点间RSSI较强的通讯路径并以较少的跳数把数据传输给Sink节点,而最小生成树中的节点则需较多跳数。因此,提出的算法在一定程度上降低了延时。算法通过事先设定最低RSSI和节点最大剩余能量MRE来构建路由树,并修改已存在的路由算法,从而保证节点通讯的可靠性和网络的节能。     

Energy-efficient Tree-based Message Ferrying Routing Schemes for Wireless Sensor Networks

Wireless sensor networks (WSNs) are prone to partitioning due to limited energy in sensor nodes and unreliable radio communications between them. Message ferrying (MF) has been proposed as an effective means to deliver data between disjoint parts of a partitioned WSN. In this paper, we propose a tree-based MF algorithm (TMFA) with least ratio tree (LRT) construction in order to prolong the lifetime and reduce energy usage in a WSN employing MF routing. LRT constructs a spanning tree from the topology graph of each partition of the WSN by setting the weight of each edge in the graph as the ratio between the energy cost to deliver a packet over the corresponding wireless link and a linear combination of the residual energy of the transmitting and receiving nodes connected by the link. In addition, the root of the spanning tree is randomly chosen among the nodes in the partition with residual energy equal to or larger than the mean residual energy of all nodes in the partition, so that the energy of nodes are expended evenly. Experimental results show that, compared with the previously proposed Least Energy Tree (LET) and Minimum Spanning Tree (MST) construction methods for TMFA, LRT construction outperforms both the LET and the MST construction in network lifetime and in the ratio of the number of packets reaching the sink to the total energy expended by all the nodes.     

Adaptive concentric chains protocol for energy efficient routing in wireless sensor networks

This paper addresses the energy efficiency of data collection based on a concentric chain clustering topology for wireless sensor networks (WSNs). To conserve the energy dissipation of nodes spent in data routing, the paper attempts to take advantage of the two opportunities: (a) the impact of the relative positions of wireless nodes to the base station on the energy efficiency of the routing chain within each cluster; (b) the effect of the varying‐sized chains on the selection rule of cluster heads (CHs). To establish an energy‐efficient chain to connect all the nodes in a cluster, the paper proposes a principal vector projection approach, which takes into account both the position of each node and that of the base station, to determine the order to which a node can be linked into the chain in order to reduce the energy requirement of the chain. Since the CH selection rules in the concentric chains are mutually independent, solely based on their self‐cluster sizes, the multi‐hop path passing through all the CHs will consist of longer links and thus consume a significant fraction of the total energy. Thus, in order to suppress the effect of the unequal cluster sizes on decreasing the energy efficiency of the multi‐hop path of CHs, the paper offers an average‐cluster‐size‐based rule (ACSB) for each cluster in order to adapt the CH selection with both the number of active nodes in the current cluster and the average value of all cluster sizes. With these two proposed schemes, an adaptive concentric chain‐based routing algorithm is proposed which enables nodes to collaboratively reduce the energy dissipation incurred in gathering sensory data. By computer simulation, the results demonstrate that the proposed algorithm performs better than other similar protocols in terms of energy saved and lifetime increased capabilities for WSNs which deploy random sensor nodes. Copyright © 2010 John Wiley & Sons, Ltd.     

Cache consistency in Wireless Multimedia Sensor Networks

The production of cheap CMOS cameras, which are able to capture rich multimedia content, combined with the creation of low-power circuits, gave birth to what is called Wireless Multimedia Sensor Networks (WMSNs). WMSNs introduce several new research challenges, mainly related to mechanisms to deliver application-level Quality-of-Service (e.g., latency minimization). Such issues have almost completely been ignored in traditional WSNs, where the research focused on energy consumption minimization. Towards achieving this goal, the technique of cooperative caching multimedia content in sensor nodes can efficiently address the resource constraints, the variable channel capacity and the in-network processing challenges associated with WMSNs. The technological advances in gigabyte-storage flash memories make sensor caching to be the ideal solution for latency minimization. Though, with caching comes the issue of maintaining the freshness of cached contents. This article proposes a new cache consistency and replacement policy, called NICC, to address the cache consistency issues in a WMSN. The proposed policies recognize and exploit the mediator nodes that relay on the most “central” points in the sensor network so that they can forward messages with small latency. With the utilization of mediator nodes that lie between the source node and cache nodes, both push-based and pull-based strategies can be applied in order to minimize the query latency and the communication overhead. Simulation results attest that NICC outperforms the state-of-the-art cache consistency policy for MANETs.     

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.     

Multi‐regional query scheduling in wireless sensor networks with minimum latency

Query scheduling as one of the most important technologies used in query processing has been widely studied recently. In this paper, we investigate the Minimum Latency Multi‐Regional Query Scheduling (ML‐MRQS) problem in wireless Sensor Networks (WSNs), which aims to generate a scheduling plan with minimum latency under a more practical query model called Multi‐Regional Query (MRQ). An MRQ targets at interested data from multiple regions of a WSN, where each region is a subarea. Because the ML‐MRQS problem is NP‐hard, we propose a heuristic scheduling algorithm Multi‐Regional Query Scheduling Algorithm (MRQSA) to solve this problem. Theoretical analysis shows that the latency of MRQSA is upper bounded by 23A + B + C for an MRQ with m query regions , where is the maximum latency for non‐overlapped regions, is the maximum latency for overlapped regions, and is the accumulated latency for data transmission from the accessing nodes to the sink. Simulation results show that MRQSA reduces latency by 42.7% to 51.63% with respect to different number of query regions, network density, region size, and interference/transmission range compared with C‐DCQS, while guaranteeing energy efficiency. Copyright © 2012 John Wiley & Sons, Ltd.     

An Enhanced Cluster Head Selection of LEACH Based on Power Consumption and Density of Sensor Nodes in Wireless Sensor Networks

The cluster head of LEACH algorithm was selected randomly in WSNs. It effects the distribution of clusters for the shadowing effect of obstruction in real scenarios. The network consumption is increased because of poor communication between nodes. A new selection method is presented to solve those problems in this paper. The logarithmic function is adopted to eliminate the shadowing effect of obstruction. The most suitable cluster is sorted out because the density of nodes is defined as the new threshold value. Simulation results show that the performances of new algorithm are obviously better than LEACH, ALEACH and Kost-LEACH algorithms. Compared with classical algorithms, the nodes utilization could enhance more than 2.0%, average energy consumption of the nodes is reduced by 9.1 J at least, and the probability of nodes failure to join the cluster could be decreased great than 3.7%.

     

Approximation algorithms for broadcasting in duty cycled wireless sensor networks

Broadcast is a fundamental operation in wireless sensor networks (WSNs). Given a source node with a packet to broadcast, the aim is to propagate the packet to all nodes in a collision free manner whilst incurring minimum latency. This problem, called minimum latency broadcast scheduling (MLBS), has been studied extensively in wireless ad-hoc networks whereby nodes remain on all the time, and has been shown to be NP-hard. However, only a few studies have addressed this problem in the context of duty-cycled WSNs. In these WSNs, nodes do not wake-up simultaneously, and hence, not all neighbors of a transmitting node will receive a broadcast packet at the same time. Unfortunately, the problem remains NP-hard and multiple transmissions may be necessary due to different wake-up times. Henceforth, this paper considers MLBS in duty cycled WSNs and presents two approximation algorithms, BS-1 and BS-2, that produce a maximum latency of at most \((\Delta -1) TH\) and \(13TH\) respectively. Here, \(\Delta\) is the maximum degree of nodes, \(T\) denotes the number of time slots in a scheduling period, and \(H\) is the broadcast latency lower bound obtained from the shortest path algorithm. We evaluated our algorithms under different network configurations and confirmed that the latencies achieved by our algorithms are much lower than existing schemes. In particular, compared to OTAB, the best broadcast scheduling algorithm to date, the broadcast latency and transmission times achieved by BS-1 is at least \(\frac{1}{17}\) and \(\frac{2}{5}\) that of OTAB respectively.     

An exact algorithm for maximum lifetime data gathering tree without aggregation in wireless sensor networks

In wireless sensor networks, maximizing the lifetime of a data gathering tree without aggregation has been proved to be NP-complete. In this paper, we prove that, unless P = NP, no polynomial-time algorithm can approximate the problem with a factor strictly greater than 2/3. The result even holds in the special case where all sensors have the same initial energy. Existing works for the problem focus on approximation algorithms, but these algorithms only find sub-optimal spanning trees and none of them can guarantee to find an optimal tree. We propose the first non-trivial exact algorithm to find an optimal spanning tree. Due to the NP-hardness nature of the problem, this proposed algorithm runs in exponential time in the worst case, but the consumed time is much less than enumerating all spanning trees. This is done by several techniques for speeding up the search. Featured techniques include how to grow the initial spanning tree and how to divide the problem into subproblems. The algorithm can handle small networks and be used as a benchmark for evaluating approximation algorithms.

     

Importance‐based data transmission optimization in multi‐source single‐sink wireless sensor networks

Energy‐efficient routing becomes one of the most critical technologies for sustaining the overall network lifetime of wireless sensor networks. In this paper, we propose a novel data transmission scheme between a number of specified source nodes and the single sink, which can efficiently restrict the usage frequency of each relay node, measured by the number of source nodes using it for data transmission. On the basis of the importance of source nodes that is closely related to deployed location, they form a descending sequence such that each node finds the minimum energy path earlier than the succeeding one. Then, the energy‐efficient multiple path algorithm with the computational complexity of O(n³) is developed for deriving the minimum energy paths, where n is the number of nodes in the network. Also, a polynomial algorithm is presented for deriving the range of the feasible values of N₀ serving as the threshold of the usage frequency of relay nodes, in which each can guarantee the existence of the solution. Further, we theoretically investigate the existence of the solution and the tree‐structured solution using m‐ary tree. Extensive simulation results show that our proposed scheme can achieve significant performance enhancement. Copyright © 2012 John Wiley & Sons, Ltd.     

Prolonging the lifetime of wireless sensor networks by utilizing feedback control

A new algorithm aiming to prolong the lifetime of wireless sensor networks (WSNs) is proposed to balance energy depletion. Using a feedback control combined with a discrete nonlinear programming method to adjust the transmission radii of sensor nodes located in different locations, makes network load redistribution possible and balances energy consumption, further prolongs the lifetime of the entire network. A data distribution model which specific to WSNs with sensor nodes that can adjust transmission radii is proposed to analyze the load spread of the network. This model contributes to predicting and analyzing energy consumption balance effectively. Compared with two other algorithms, dynamic transmission range adjustment and SP, respectively, the experimental results show that the proposed algorithm can lengthen the lifetime of WSNs by up to 22.7 and 27.2 %.     

Distributed fuzzy logic based energy‐aware and coverage preserving unequal clustering algorithm for wireless sensor networks

In an energy‐constrained wireless sensor networks (WSNs), clustering is found to be an effective strategy to minimize the energy depletion of sensor nodes. In clustered WSNs, network is partitioned into set of clusters, each having a coordinator called cluster head (CH), which collects data from its cluster members and forwards it to the base station (BS) via other CHs. Clustered WSNs often suffer from the hot spot problem where CHs closer to the BS die much early because of high energy consumption contributed by the data forwarding load. Such death of nodes results coverage holes in the network very early. In most applications of WSNs, coverage preservation of the target area is a primary measure of quality of service. Considering the energy limitation of sensors, most of the clustering algorithms designed for WSNs focus on energy efficiency while ignoring the coverage requirement. In this paper, we propose a distributed clustering algorithm that uses fuzzy logic to establish a trade‐off between the energy efficiency and coverage requirement. This algorithm considers both energy and coverage parameters during cluster formation to maximize the coverage preservation of target area. Further, to deal with hot spot problem, it forms unequal sized clusters such that more CHs are available closer to BS to share the high data forwarding load. The performance of the proposed clustering algorithm is compared with some of the well‐known existing algorithms under different network scenarios. The simulation results validate the superiority of our algorithm in network lifetime, coverage preservation, and energy efficiency.     

A particle swarm optimization based energy efficient cluster head selection algorithm for wireless sensor networks

Clustering has been proven to be one of the most efficient techniques for saving energy of wireless sensor networks (WSNs). However, in a hierarchical cluster based WSN, cluster heads (CHs) consume more energy due to extra overload for receiving and aggregating the data from their member sensor nodes and transmitting the aggregated data to the base station. Therefore, the proper selection of CHs plays vital role to conserve the energy of sensor nodes for prolonging the lifetime of WSNs. In this paper, we propose an energy efficient cluster head selection algorithm which is based on particle swarm optimization (PSO) called PSO-ECHS. The algorithm is developed with an efficient scheme of particle encoding and fitness function. For the energy efficiency of the proposed PSO approach, we consider various parameters such as intra-cluster distance, sink distance and residual energy of sensor nodes. We also present cluster formation in which non-cluster head sensor nodes join their CHs based on derived weight function. The algorithm is tested extensively on various scenarios of WSNs, varying number of sensor nodes and the CHs. The results are compared with some existing algorithms to demonstrate the superiority of the proposed algorithm.     

An Isochronous Testing Strategy for Hierarchical Adaptive Distributed System-Level Diagnosis

Distributed System-level diagnosis allows the fault-free components of a fault-tolerant distributed system to determine which components of the system are faulty and which are fault-free. The time it takes for nodes running the algorithm to diagnose a new event is called the algorithm's latency. In this paper we present a new distributed system-level diagnosis algorithm which presents a latency of O(log N) testing rounds, for a system of N nodes. A previous hierarchical distributed system-level diagnosis algorithm, Hi-ADSD, presents a latency of O(log ² N) testing rounds. Nodes are grouped in progressively larger logical clusters for the purpose of testing. The algorithm employs an isochronous testing strategy that forces all fault-free nodes to execute tests on clusters of the same size each testing round. This strategy is based on two main principles: a tested node must test its tester in the same round; a node only accepts tests according to a lexical priority order. We present formal proofs that the algorithm's latency is at most 2log N – 1 testing rounds and that the testing strategy of the algorithm leads to the execution of isochronous tests. Simulation results are shown for systems of up to 64 nodes.     

Scheduling Algorithms for Star-Coupled WDM Networks with Tunable Transmitter and Tunable Receiver Architecture

This paper presents the design and analysis of two scheduling algorithms for a reservation-based medium access control (MAC) protocol for wavelength division multiplexed (WDM) multi-channel optical networks. The network architecture is based on a passive star topology with one tunable transmitter and receiver (TT-TR) per node. The main objective of scheduling algorithm design is to reduce the computation time while maximizing the utilization of the network resources. In this paper, we propose two scheduling schemes called SEQSAM (SEQuential Scheduling AlgorithM) and BALSAM (BALanced Scheduling AlgorithM). Let M denote the number of nodes, C the number of channels, and K the maximum number of packets transmitted by one node to another. SEQSAM uses the M × M traffic demand matrix--obtained during the reservation phase of the MAC protocol--to compute a collision-free schedule for the nodes of the network. BALSAM uses the modified MULTI-FIT algorithm (MMFT) [1] to convert the M × M matrix into a corresponding M × C matrix, which is input to the IBS (Interval Based Scheduling) algorithm [2] that schedules the requests of the nodes. The overall time complexity of SEQSAM is O(M ³) compared to BALSAM algorithm's time complexity of O(M ² CK + M ² + MlogM). Note that the lower bound for any scheduling algorithm operating on a M × M matrix is O(M ²). A simulation-based performance study that considers network utilization, computation time, tuning latency, average packet latency and throughput for 1.2 Gbps and 2.4 Gbps data streams is presented.     

PFARS: Enhancing throughput and lifetime of heterogeneous WSNs through power‐aware fusion,aggregation, and routing scheme

Heterogeneous wireless sensor networks (WSNs) consist of resource‐starving nodes that face a challenging task of handling various issues such as data redundancy, data fusion, congestion control, and energy efficiency. In these networks, data fusion algorithms process the raw data generated by a sensor node in an energy‐efficient manner to reduce redundancy, improve accuracy, and enhance the network lifetime. In literature, these issues are addressed individually, and most of the proposed solutions are either application‐specific or too complex that make their implementation unrealistic, specifically, in a resource‐constrained environment. In this paper, we propose a novel node‐level data fusion algorithm for heterogeneous WSNs to detect noisy data and replace them with highly refined data. To minimize the amount of transmitted data, a hybrid data aggregation algorithm is proposed that performs in‐network processing while preserving the reliability of gathered data. This combination of data fusion and data aggregation algorithms effectively handle the aforementioned issues by ensuring an efficient utilization of the available resources. Apart from fusion and aggregation, a biased traffic distribution algorithm is introduced that considerably increases the overall lifetime of heterogeneous WSNs. The proposed algorithm performs the tedious task of traffic distribution according to the network's statistics, ie, the residual energy of neighboring nodes and their importance from a network's connectivity perspective. All our proposed algorithms were tested on a real‐time dataset obtained through our deployed heterogeneous WSN in an orange orchard and also on publicly available benchmark datasets. Experimental results verify that our proposed algorithms outperform the existing approaches in terms of various performance metrics such as throughput, lifetime, data accuracy, computational time, and delay.