Search

A Wireless Sensor Network (WSN) consists of a group of energy-constrained tiny devices called sensors which have sensing, processing, and communicating capabilities. These sensors are deployed in a region of interest for monitoring targets or detecting events, and forwarding the processed data to the sink nodes or gateways. In any wireless network scenario, the targets are to be covered by at least one sensor in the network in order to detect certain events. Maximizing coverage along with improving energy efficiency of the network is a fundamental issue in WSN. Therefore, a Biogeography Based Optimization (BBO) meta-heuristic technique is employed to place sensors in the region of interest. The proposed scheme solves a multi-objective problem using classical weighted sum approach. A fitness function is derived from combination of conflicting objectives, minimum interference, maximum target coverage, and selection of minimum number of sensor nodes along with connectivity of the network as a constraint. The scheme selects minimum number of sensors to deploy in the field of interest which maximizes the target coverage by minimizing the interference of sensors. The proposed scheme is tested on random and grid deployment scenarios. Finally, the scheme is compared with Genetic Algorithm and Random Scheme. The average interference energy loss on BBO-based scheme is found to be 16% less than that of the GA-based scheme, and 60% less than that of a Random-based scheme.

A Wireless Sensor Network (WSN) is a group of sensors which communicate with each other and perform some specific task. Clustering is used to conserve energy in a WSN. In this work, the aim is to minimize the energy consumption and maximize the network lifetime of a homogeneous WSN using PSO (Particle Swarm Optimization) based Clustering algorithm in conjunction with quantum computing. In quantum computing, a bit is known as a qubit and it can exist in the following states: a ‘0’, a ‘1’ or a superposition of ‘0’ and ‘1’. In this chapter, the Quantum Computing based PSO clustering algorithm for Optimizing Energy consumption and Network lifetime (QCPOEN) algorithm for homogeneous wireless sensor networks is proposed. The proposed algorithm is compared with the PSO-ECHS algorithm and the LEACH algorithm. The superiority of the algorithm can be verified from the results.

In wireless sensor networks, the performance metric such as energy conservation becomes paramount. One of the fundamental problems of energy drains is due to the interference of sensors during sensing, transmission, and receiving data. The issue of placing sensors on a region of interest to minimize the sensing and communication interference with a connected network is NP-complete. In order to overcome the existing problem, we have proposed a new work for interference minimization technique for optimal placement of sensors by employing biogeography-based optimization scheme. An efficient habitats representation, objective function derivation, migration, and mutation operators are adopted in the scheme. The simulations are performed to obtain the optimal position for sensor placement. Finally, the energy-saving of the network is compared with and without interference aware sensor nodes placement.

Minimizing the total power in a wireless sensor network (WSN) has great significance, since the nodes are powered by a small battery of limited capacity. By using an appropriate topology, the energy utilization of the network can be minimized which results in an increased lifetime of a WSN. In reality, WSN is modeled as an undirected graph in which each vertex represents a sensor node and an edge represents the link between the two sensor nodes. We define a distance function that maps a pair of vertices to a positive real number, i.e., Euclidean distance between the two vertices. On this initial topology, we construct a reduced topology satisfying special connectivity constraints like bi-connectivity, k-connectivity, bounded diameter, degree restricted, etc. We assign power to each node as the maximum distance of all its adjacent edges, and total power of the network is the sum of the powers of all the vertices. Fault tolerance addresses the issue of a node or link failure in a WSN. Fault-tolerant network aims at k-connectivity in the network so that there exist at least k vertex disjoint paths between any two sensor nodes of the network. Minimum power 2-connected subgraph (MP2CS) problem is to contrive a 2-connected network with minimum total power. It is proved that MP2CS problem is NP-hard. Minimum power k backbone node 2-connected subgraph (MPkB2CS) problem is a special case of MP2CS problem, which seeks a power assignment satisfying 2-connectivity with k backbone nodes. In this paper, the problem of finding a 3-connected network for a given set of nodes, which minimizes the total power with k backbone nodes, is addressed which is termed as MPkB3CS problem. We propose an algorithm for MPkB3CS problem and establish that the proposed algorithm has an approximation ratio of 4k + 1, for k ≥ 3.

A wireless sensor network (WSN) faces various issues one of which includes coverage of the given set of targets under limited energy. There is a need to monitor different targets in the sensor field for effective information transmission to the base station from each sensor node which covers the target. The problem of maximizing the network lifetime while satisfying the coverage and energy parameters or connectivity constraints is known as the Target Coverage Problem in WSN. As the sensor nodes are battery driven and have limited energy, the primary challenge is to maximize the coverage in order to prolong network lifetime. The problem of assigning a subset of sensors, such that all targets are monitored is proved to be NP-complete. The Objective of this paper is to assign an optimal number of sensors to targets to extend the lifetime of the network. In the last few decades, many meta-heuristic algorithms have been proposed to solve clustering problems in WSN. In this paper, we have introduced a novel meta-heuristic based differential evolution algorithm to solve target coverage in WSN. The simulation result shows that the proposed meta-heuristic method outperforms the random assignment technique.

Clustering is done in wireless sensor networks (WSN) to conserve the energy of sensor nodes in the network. The network lifetime of WSN can be defined as the duration for which the network remains operational. It is a critical design issue in WSN’s since once a node is deployed, it may not be feasible to replace or recharge the sensor nodes. In this paper, we proposed a quantum PSO algorithm for improving network lifetime called quantum PSO clustering algorithm to improve network lifetime(QPCINL). The QPCINL uses quantum bits. A quantum bit can exist in ‘0’ state, ‘1’ state or a linear superposition of ‘0’ and ‘1’ states, unlike the binary bit which can exist in only ‘0’ state or ‘1’ state. We define a factor called network lifetime factor(NLF) which allows us to compare various algorithms. We test our algorithm by giving different values to the number of sensor nodes and cluster heads, varying the base station position, etc. Then, we compare our results to existing algorithms and demonstrate the superiority of our algorithm.

The minimum power assignment problem in a Wireless Sensor Network (WSN) is to assign transmission range to the nodes of the network with specified connectivity constraints minimizing the total power. This problem is termed as Strong Minimum Energy Topology (SMET) problem. Fault tolerance addresses the issue of a node or link failure in a WSN. So, with an objective of achieving high connectivity, we consider SMET problem with an additional property, i.e., the resultant network must satisfy the property of two or high connectivity. Minimum Power [Formula: see text]-Connected Subgraph (MP[Formula: see text]CS) problem is to contrive an [Formula: see text]-connected network with minimum power. Minimum Power [Formula: see text]-Connected Subgraph (MP2CS) problem is proved to be NP -hard. Minimum Power [Formula: see text] Backbone node [Formula: see text]-Connected Subgraph (MP[Formula: see text]B[Formula: see text]CS) problem is a special case of MP[Formula: see text]CS problem, which seeks a power assignment satisfying [Formula: see text]-connectivity with [Formula: see text] backbone nodes. We study MP[Formula: see text]B[Formula: see text]CS problem for [Formula: see text] backbone nodes, [Formula: see text]-connectivity and derive the approximation ratios. We also propose an algorithm of approximation ratio [Formula: see text], for Minimum Power [Formula: see text] Backbone node 3-Connected Subgraph (MP[Formula: see text]B3CS) problem for [Formula: see text] that runs in [Formula: see text] time and generalize for the case [Formula: see text] for any [Formula: see text] and [Formula: see text].

Given a set of $$n$$n sensors, the strong minimum energy topology (SMET) problem in a wireless sensor network is to assign transmit powers to all sensors such that (i) the graph induced only using the bi-directional links is connected, that is, there is a path between every pair of sensors, and (ii) the sum of the transmit powers of all the sensors is minimum. This problem is known to be NP-hard. In this paper, we study a special case of the SMET problem, namely , the $$k$$k-strong minimum energy hierarchical topology ($$k$$k-SMEHT) problem. Given a set of $$n$$n sensors and an integer $$k$$k, the $$k$$k-SMEHT problem is to assign transmission powers to all sensors such that (i) the graph induced using only bi-directional links is connected, (ii) at most $$k$$k nodes of the graph induced using only bi-directional links have two or more neighbors, that is they are non-pendant nodes, and (iii) the sum of the transmit powers of all the sensors in $$G$$G is minimum. We show that $$k$$k-SMEHT problem is NP-hard for arbitrary $$k$$k. However, we propose a $$\frac{k+1}{2}$$k+12-approximation algorithm for $$k$$k-SMEHT problem, when $$k$$k is a fixed constant. Finally, we propose a polynomial time algorithm for the $$k$$k-SMEHT problem for $$k=2$$k=2.

Given a set of sensors, the strong minimum energy topology (SMET) problem is to assign transmit power to each sensor such that the sum of the transmit powers of all the sensors is minimum subject to the constraint that the resulting topology containing only bidirectional links is strongly connected. This problem is known to be NP-hard. However, most of the wireless sensor networks are hierarchical in nature, where shorter path lengths are preferred for communication between any two nodes. Given a set of sensors and a specified sensor, say $$r$$r, the strong minimum energy $$2$$2-hop rooted topology problem ($$2$$2h-SMERT) is to assign transmit power to each sensor such that the sum of the transmit powers of all the sensors is minimum subject to the constraints that the resulting topology containing only bidirectional links is strongly connected and the length of the path from $$r$$r to any other node is at most $$2$$2. We prove that the $$2$$2h-SMERT problem is NP-hard. We also prove that $$2$$2h-SMERT problem is APX-hard. We then show that $$2$$2h-SMERT problem is not approximable within a factor of $$\frac{1}{2}(1-\epsilon ) \ln n$$12(1-∈)lnn unless NP $$\subseteq DTIME(n^{\log \log n})$$⊆DTIME(nloglogn). On the positive side, we propose a $$2(1+ \ln n)$$2(1+lnn)-approximation algorithm for the $$2$$2h-SMERT problem. We also study two special cases of the $$2$$2h-SMERT problem, namely, the $$d$$d-rest-$$2$$2h-SMERT problem and the $$k$$k-int-$$2$$2h-SMERT problem. We propose a $$2(1+ \ln d)$$2(1+lnd)-approximation algorithm for the $$d$$d-rest-$$2$$2h-SMERT problem. The $$k$$k-int-$$2$$2h-SMERT problem is NP-hard for arbitrary $$k$$k. However, for fixed constant $$k$$k, we propose a $$\frac{k+1}{2}$$k+12-approximation algorithm for the $$k$$k-int-$$2$$2h-SMERT problem and obtain a polynomial time optimal algorithm for the $$k$$k-int-$$2$$2h-SMERT problem for $$k=2$$k=2.

Limiting Interference between the nodes in a Wireless Sensor Network (WSN) is of considerable importance for energy-efficiency of the network. Minimizing the interference in a WSN minimizes the overall energy consumption of the network by reducing the number of conflicting transmissions. We consider Receiver interference minimization problem. Two types of interference are defined in a WSN, namely Sender interference and Receiver interference. In this paper we consider the Receiver interference problem, where the objective is to minimize the maximum Receiver interference. The problem of minimizing the maximum Receiver interference is proved to be NP-hard. In this paper we propose two algorithms named MinMax-RIP and a modified version of the same to minimize the maximum Receiver interference in a WSN. We evaluate the performance of our algorithms through simulation. We then consider the interference minimization problem in a broadcast network. We propose MinMax-BRIP algorithm for optimal range assignment which gives minimum total Receiver interference for connectivity predicate Broadcast.

Given a set of sensors, the strong minimum energy topology SMET problem is to assign transmit power to each sensor such that the resulting topology containing only bidirectional links is strongly connected and the total energy of all the nodes is minimized. The SMET problem is known to be NP-hard. Currently available sensors in the market support a finite set of transmission ranges. So we consider the k-Distinct-SMET problem, where only k transmission power levels are used. We prove that the k-Distinct-SMET problem is NP-complete for ki¾ź3. However, on the positive side, we show that the 2-Distinct-SMET problem can be solved in polynomial time. The energy cost of transmitting a bit is higher than the cost of computation, and hence it may be advantageous to organize the sensors into clusters and form a hierarchical structure. This motivated the study of k -Distinct- r Strong Minimum Energy Hierarchical Topology k -Distinct- r SMEHT problem: Given a sensor network consisting of n sensors, and integers k and r, assign transmit powers to all sensors out of the k distinct power levels such that i the graph induced using only the bi-directional links is connected, ii at most r sensors are connected to two or more sensors by a bidirectional link and iii the sum of the transmit powers of all the sensors is minimum. We Propose a $\frac{r+1}{2}$ - approximation algorithm for the k-Distinct-rSMEHT problem for any fixed r and arbitrary k.

A wireless sensor network WSN is modeled as weighted directed graph, with each sensor in the plane representing a vertex. The edges represent the link between two sensors. A cost function c:Ei??ℝ+ is associated with each edge E. The power of a node v is the maximum cost of its incident edges. The sum of powers of all nodes v∈V is the total power of the graph. A graph G=V,E is 2-connected and remains connected even if any one node is deleted from the graph. Fault tolerance is an important property of a network, which demands two or higher connectivity. In this paper we consider the problem of assigning transmit power to the nodes of a WSN, such that the resulting topology is two node-connected and the the total power of the network is minimized. The minimum power two-connected subgraph MP2CS problem is known to be NP-hard. We give a polynomial reduction from strong minimum energy topology problem to MP2CS problem. This leads to an alternate NP-hard proof for MP2CS problem. We propose a heuristic for MP2CS, which is based on MST augmentation. Through simulation we show that the proposed heuristics performs better than the existing heuristic for MP2CS problem. We then consider a special case of MP2CS problem, called the minimum power k backbone 2-connected subgraphMPkB2CS problem. We prove that MPkB2CS problem can be solved optimally in On 3 time for k=2, and propose a 2-approximation algorithm for k=3. We show that MPkB2CS problem admits an approximation algorithm with approximation ratio $\frac{3k+1}{2}$ for k>3.

Given a set of sensors in a plane or in higher dimension, the strong minimum energy topology problem is to assign transmission range to each of the sensor nodes, so as to minimize the total power consumption. Here the constraint is that the network must be strongly connected. This problem is known to be NP-hard. As this problem has lot of practical application, several approximation algorithms and heuristics has been proposed. There exist a MST based 2-approximation algorithm for this problem having running time complexity of O(n 2 logn). In this paper we propose a simple parallel version of the 2-approximation algorithm. We prove that this parallel algorithm is a NC-algorithm and is also cost optimal for a dense graph. We prove that the algorithm has a time complexity O(logn) and work complexity O(n 2) when the number of processor used is O(n 2).

Reducing the interference is one of the important objectives of topology control problem as high interference number increases the probability of packet loss and hence forces the sender node to retransmit the packets resulting in more energy consumption. Strong Minimum Interference Topology (SMIT) problem is to assign transmit power to each sensor in a sensor network such that the maximum/average node interference of a sensor is minimized subject to the constraint that the induced topology containing only bidirectional links is strongly connected. In this paper we study the sender centric interference model and propose (i)an optimal solution for minimizing the maximum node interference, (ii) a 2-approximation algorithm to construct a topology for wireless sensor networks such that the average node interference of the topology is minimized. The extensive simulation results indicate that our algorithm outperforms the existing algorithm.

Energy minimization and interference minimization are two of the main objectives of topology control problem in wireless sensor networks. Reducing interference lowers energy consumption by reducing the number of collisions and packet retransmissions on the media access layer. Reducing transmission energy increases the lifetime of the network. In order to increase the lifetime of the network it is important to fulfil both these objectives. However, the topology control problem of minimizing interference as well the the topology control problem of minimizing total transmission power are shown to be NP-Complete. Several heuristics have been proposed for minimizing the energy and interferences separately. Only few heuristics are available in the literature which address these two problems simultaneously. In this paper, we propose a local search based heuristic for the problem of assigning transmit power to each of the n sensors such that the total power consumption and interference is minimum along with the constraint that the resulting topology consisting of bidirectional links only is strongly connected. We prove that the transmission power resulting from this heuristic is at most twice the optimal. The simulation result shows that we get significant reduction in interference as compared to the interference of existing heuristics.

One of the critical constraints for lifetime and operability of sensor networks is the limited amount of available energy. Reducing the interference is one of the important positive steps towards this as high interference number increases the probability of packet loss and hence forces the sender node to retransmit the packets resulting in more energy consumption. Minimum Interference Strong Bidirectional Topology MISBT problem is to assign transmit power to each sensor in a sensor network such that the maximum/average node interference of a sensor is minimised subject to the constraint that the induced topology containing bidirectional links only is strongly connected. In this paper we propose two new models for measuring the interference, namely the MAX model and SUM model. We present algorithms for minimising maximum and average node interference under these models. The average interference obtained by our algorithms for MAX and SUM models is at most twice the optimal. The simulation results show that the total power consumptions by the solution produced by our algorithm under the SUM model is less than the solution produced by the existing algorithm under the OR model. Furthermore, our algorithms under different models are 2-approximation algorithms for the average receiver-centric interference as well.