Abstract: A Wireless Sensor Network (WSN) is composed of a large number of tiny sensor nodes, relay nodes and a sink that are deployed in an environment to collect information. Irregular placement of sensor nodes in WSN causes unbalanced energy depletion and reduces the overall performance of WSN. The extra cost of processing and redundant links occurrence of sensor nodes in the congested sensor node topology maximizes the overhead of wireless sensor network. In proposed two-echelon architecture, minimum sensor node deployment algorithm is used to achieve full coverage and relay node deployment algorithm is used to reduce redundant data links. In first echelon, the sensor node sends its data to relay nodes. In second echelon, the relay node forwards the incoming packets to the sink. Simulation result presents that our proposed work enhanced the lifetime of the network and data delivery. It also ensures more than 95% of the total energy utilization of the network.
INTRODUCTION
The WSN is composed of a large number of sensor nodes distributed in an environment to monitor the event precisely. The main components of each sensor node are comprised of a processor, source of energy and onboard sensors such as speed, temperature, humidity and motion detectors. The deployed sensor nodes collects information of interest, process it using data fusion and quantization algorithms, lastly forward it towards the sink via cluster heads or neighboring relay nodes. In most of the deployment strategies data gathering and data fusion are application specific. Each sensor node in a network consumed a different amount of energy in sensing, processing and transmission therefore balanced energy consumption is one of the main issues in WSNs. Energy efficiency can be achieved by hierarchically organizing sensor nodes into two-tier architecture called clusters. In the first tier, sensor node sends its data to local cluster head. Cluster head process data, such as compression and data fusion. In the second tier, the cluster heads use direct communication to forward the processed data to the sink. The distribution of cluster heads is not well controlled if the cluster heads selection is random. If a cluster head is considerably far away from the sink, energy consumption will be greater as compared to cluster members which are closer to the sin (Heinzelman et al., 2002). In some situation the cluster heads may have limited radio transmission range therefore, the two-tier architecture seems strong for sensible environment.
Efficient energy depletion can also be achieved through multi-hop transmission using relay nodes, but random deployment of sensor nodes using cluster heads or relay nodes at predetermined locations have some issues like location awareness, energy arrangement and mobility. Random deployment using three-tier architecture has been proposed without the assumptions of mobile nodes, a heuristic based algorithm has been proposed for relay node selection which enhance the network lifespan (Aslam et al., 2007).
The main objective of the most traditional algorithms is to minimize the problem of energy holes and to maximize network coverage rate with uniform sensor node placement. To minimize the energy hole, some author’s investigate the problem of joint placement for both relay nodes and sensor nodes. The authors conclude that balanced energy depletion is achievable with the "rational designed deployment density" for relay nodes with the proposal of novel relay node deployment strategy as well as a data routing scheme. Simulations result shows that their proposed approach outperforms in terms of both network lifespan and unutilized energy ratio (Jia et al., 2013). In Tang et al. (2006), an optimal placement of sink was obtained through theoretical analysis by using the given number and locations of relay nodes to extend the network lifespan but this study did not address the optimal placement of RNs.
In our proposed Two-Echelon Architecture, a minimum sensor node deployment algorithm is used to achieve full coverage in corona based wireless sensor network, wherein the sensor nodes are decreasing from outer to inner corona. Furthermore, the relay node deployment algorithm is used to reduce redundant data links. In echelon one communication, each sensor node forwards its sensed data to the relay nodes. In echelon two communications, the relay nodes forward the received data to the BS. Relay nodes are increased and sensor nodes are decreasing from outer to inner corona.
The main issues of coverage, balanced energy consumption and the placement of relay nodes in WSNs are covered in literature survey. In case of node failure due to the energy hole occurrences, the relay node placement algorithms are proposed to ensure network connectivity, coverage and survivability without the consideration of network lifespan (Tang et al., 2006). The Gaussian deployment strategies have been proposed to reduce the energy holes around the sink due to many to one traffic patterns and to enhance the lifespan and energy utilization (Atiq-ur-Rahman et al., 2012).
Xu et al. (2005) assumed Sensor Nodes (SNs) are energy constrained but RNs are not, so a recursive algorithm is proposed to solve the optimal placement problem. Furthermore, two-phase topology design framework was proposed by Wang et al. (2005), where both SNs and RNs are energy limited. To place the First Phase Relay Nodes (FPRNs), a reformulation of the optimal recursive algorithm is used. To place the Second Phase Relay Nodes (SPRNs), two fundamental design principles-the Far-Near strategy and the Max-Min strategy was proposed, so that lifespan and connectivity constraints on the whole network are satisfied.
Zhou and Yi (2013) developed a methodology and strategy of node arrangement to improve the performance of WSN, including balancing energy consumption, increasing data capacity and reducing deployment cost for long-span bridge health monitoring. A conglomerate WSN organized by sensor nodes and relay nodes is introduced for structural health monitoring. First, an energy consumption model for conglomerate WSN is presented. Second, Data Acquisition Efficiency (DAE) i.e., data capacity per unit deployment cost is suggested to evaluate the performance of WSN. A genetic algorithm is proposed to configure sensor nodes and to distribute relay nodes in non-uniform node arrangement method. The authors predict the optimum deployment of sensor nodes and propose a non-uniform node deployment scheme by calculating node energy consumption. They conduct extensive experiments and show that their non-uniform deployment scheme performed better in prolonging the network lifespan and improving energy utilization rate than the other conventional deployment schemes (Yuan et al., 2011).
Coverage and lifespan are the two major performance metrics for WSNs. Sensor nodes at different locations will suffer from different message forwarding burdens either due to the required transmission power or due to the amounts of forwarding messages. Tsai et al. (2008) focus on the node deployment problem for large-scale randomly distributed WSNs, the IFA-based deployment strategy is proposed for the multi-hop routing scenario. The sensing coverage, message forwarding and energy consumption issues are taken into considerations. Simulation result shows that their proposed IFA-based deployment strategy is more energy efficient and can significantly improve the sensing coverage of a WSN.
Guo et al. (2014), address the energy-efficient connectivity problem of WSN which consists of static sensor nodes of short communication range having limited energy level and relay nodes of longest communication range having unlimited power supply. The proposed unified backbone construction framework performed in a centralized manner with two main objectives i.e., to minimize the number of nodes in the backbone and to maximize the lifespan of the network. To solve such a challenging problem, the authors formulate three sub-problems: (a) Partial Dominating Set with Energy Threshold (PDSET), (b) Partial Dominating Set with Largest Residual Energy (PDSLE) and (c) Minimum Relay Node Placement (MRNP). They develop polynomial-time algorithms for these three sub-problems. They also prove that their algorithm for PDSLE is optimal and algorithms for the PDSET and MRNP problems have small approximation ratios. Numerical results show that their proposed framework can significantly improve energy efficiency and reduce backbone size. In order to increase energy efficiency, Lanza-Gutierrez et al. (2012) added relay nodes to a previously defined static WSN which optimizes both average energy consumption and average coverage. They use two multi-objective evolutionary algorithms: NSGA-II and SPEA-2. They have statistically proven that these methods increase the energy efficiency.
To achieve certain coverage and connectivity requirement using minimum number of relay nodes, Chen and Cui (2013) addresses the relay node placement problem in two-tiered wireless sensor networks. The 1-coverage and 1-connected problem, the authors proposed a polynomial time (5+€)-approximation algorithm under the assumption that the communication range of the sensor nodes is no more than that of the relay node. For the 2-coverage 2-connected problem a polynomial time (20+€) -approximation algorithm is presented where, € is any given positive constant. They present a polynomial time (15k-10+€)-approximation algorithm for the k-coverage 2-connected situation.
Misra et al. (2013) studied the constraint of relay node placement problem in an energy-harvesting network in which the energy harvesting potential of the candidate locations is known in priori. Ensuring the relay nodes harvests large amounts of ambient energy. A minimum number of relay nodes are placed to achieve connectivity and survivability. Furthermore the NP-hardness of the connectivity and survivability problems are discussed and the polynomial time O (1)-approximation algorithms with low approximation ratios are proposed. The numerical results validate that the RNs placement through the proposed algorithms harvest 50% more energy than those placed by the unawareness of the energy harvesting algorithm. To compute a lower bound on the optimal solution for minimum relay node placement the authors also develop a unified-Mixed Integer Linear Program (MILP)-based formulation and demonstrate that the results of their proposed algorithms were on average within 1.5 times of the optimal.
Atiq-ur-Rahman et al. (2013a) consider energy hole formation due to the unbalanced energy consumption in many-to-one wireless sensor network. They proposed a novel method using the optimum number of sensor node distribution in engineered corona-based wireless sensor network, in which the interested area was divided into a number of coronas. The optimum number of sensor node in each corona was distributed using mathematical models. Simulation result shows that their proposed algorithm utilized 95% of the total energy during network lifespan which ultimately maximize data delivery and reduce the remaining energy.
Many resources-constrained Underwater Sensor Nodes (USNs) are deployed to perform collaborative monitoring tasks over a given region in an Underwater Acoustic Wireless Sensor Network (UA-WSN). To preserve network connectivity while guaranteeing other network QoS is to deploy some Relay Nodes (RNs) in the networks. The RNs’ function is more powerful than USNs but they can lead to more interference and their cost is more expensive. The authors’ addresses constrained low-interference relay node deployment problem for 3-D UA-WSNs. They placed the RNs at a subset of candidate locations to ensure connectivity between the USNs such that the value of total incremental interference and the number of RNs deployed are minimized. They first prove that it is NP-hard, then propose a general approximation algorithm framework and based on the framework, they get two polynomial time O (1)-approximation algorithms (Li et al., 2012).
The placement of the sink node has a great impact on the energy consumption and lifetime of WSNs. Chen and Li (2013) investigates the energy-oriented and lifetime-oriented sink node placement strategies in the single-hop and multiple-hop WSNs, respectively. To minimize the total energy consumption in the networks, the energy-oriented strategy is proposed while the lifetime-oriented strategy focuses much more on the lifetime of the nodes. The performance evaluation of different placement strategies using a routing-cost based ant-routing algorithm shows that the networks with lifetime-oriented strategy achieve a significant improvement on network lifetime.
Preserving the connectivity is a serious problem in wireless sensor network and one of the most effective solutions of this problem is to deploy powerful Relay Nodes (RN). One of the important parameters for the network performance is the location of the RN. The research work investigates Relay Node Placement (RNP) problem on a weighted terrain structure to satisfy WSN connectivity. The main objective of weighted RNP is to minimize the total weights of the points on which RN is deployed instead of minimizing the number of RN. A mathematical formulation is proposed to find the optimal solution for the weighted RNP and a polynomial time heuristic algorithm is also developed due to the NP-complete nature of the problem. Simulation results show that the proposed heuristic algorithm can find near-optimal solutions in a reasonable time bound.
Atiq-ur-Rahman et al. (2011) proposed two strategies to maximize network lifespan by reducing hot-spots in sink vicinity. First, a correlation between network lifespan and quantity of sink-neighboring nodes has been observed for Gaussian deployments. Second, a correlation between network lifespan and increased energy levels of sink-neighboring nodes has been observed for heterogeneous deployments. The network lifespan is capped beyond a certain threshold in both cases. Sensor node positioning is one of the major concerns in wireless sensor network. To achieve full coverage by using minimum sensor nodes, Fidanova et al. (2012) proposed Ant Colony Optimization (ACO) algorithm for the deployment, taking full coverage and connectivity as constraints. Peng et al. (2012) studied the impacts of sensor node distributions on network coverage. They first show the impacts on network coverage by adopting different sensor node distributions through both analytical and simulation studies then they adopt a distribution-free approach to study network coverage, in which no assumption of probability distribution of sensor node locations is needed. The proposed approach improves the network coverage. De et al. (2012) proposed a multi-objective optimization coverage control strategy for solving the contradictory problem among energy consumption, equilibrium of energy and network coverage in wireless sensor networks. They designed an evolutionary algorithm named Multi-Objective Free Search algorithm (MOFS) for WSN optimization problem based on fitness functions and binary coding schemes. Their proposed strategy is used to estimate the number of active nodes because individual nodes cannot have their working state information readily. The result shows that MOFS is an effective to achieve high network coverage and reduce energy consumption effectively by the reasonable selecting parameters while equilibrium of energy consumption is also considered.
To overcome the problem of energy hole and achieving sub-balanced energy consumption in corona-based wireless sensor network, engineered Gaussian deployment strategies are proposed by Atiq-ur-Rahman et al. (2013b) and Mhatre et al. (2005), optimal nodal densities and node initial energies were derived to guarantee a lifespan threshold in either a randomly deployed or grid based WSN. The objective of minimizing the cost is considered but the proposed scheme does not produce an optimal solution when the location of placement is controllable.
METHODOLOGY
Two-echelon architecture: In our proposed work, three types of devices SNs, RNs and a BS. A SN has limited and un-replenished power supply and it does not relay packets for other nodes toward the BS as it is placed at the centre of the network. The event occurrences at the SNs are predictable and individual SNs have been deployed at the chosen sensing spots. A RN is assumed to carry higher power supply and have high computation capacity than the SNs. A RN has fixed transmission radius and is capable of relaying, coordinating and aggregating information.
In first echelon, each sensor node forwards its sensed data to the nearby relay nodes. In second echelon, the relay nodes forward the received data to the BS via inner corona relay nodes. The relay nodes make the wireless sensor network more reliable and share the burden of sensor nodes to provide an energy efficient data gathering. The relay node contains three sections, i.e., Radio Communication Section (RCS) for transmitting and receiving the information, an Information Recording Section (IRS) for storing the information and an Information Conveying Section (ICS) for deciding a destination of the information. Proposed network model of WSN considers three types of communications i.e., sensor node to relay node communication, relay node to relay node communication and relay node to base station.
The techniques and strategies as discussed so far, the problem of sparse placement in outer-most corona and dense and congested deployment in inner-most corona still needs to be addressed. The congestion can lead to an energy bottleneck in the operation of the WSN. In proposed study, we are using two types of nodes. The first type is used to sense the environment, whereas the second type; the relay node is used to relay data packets in a network. The minimum numbers of sensor nodes are deployed to achieve full coverage and to avoid redundant data transmission towards the sink. The relay nodes are distributed with the sensor nodes in such a pattern as to achieve the balanced energy depletion.
Minimum number of sensor node placement for full coverage: The sensor nodes are distributed in corona according to their sensing range. The radius of the corona decreases from the outer to the inner corona therefore the number of sensor nodes also decreases from the outer corona towards the inner corona. Each corona’s sensor node can communicate with its neighboring corona’s relay nodes directly through one hop. As sink lies in the center of the network so the adjacent corona nodes to the sink use single-hop to communicate with the sink while those far away from the sink communicate using multi-hops. In the proposed network model, the circumference of the ith corona can be calculated by Eq. 1:
| (1) |
where, Ai and ri represents the circumference and the radius of the ith corona, respectively. So, the density of the ith corona Ci, with full coverage relies on the sensor node communication range. The distribution of sensor nodes can be calculated by the Eq. 2:
| (2) |
where, Rc is the communication range and Di is the density of ith corona. Algorithm 1 is used to distribute the minimum number of sensor nodes in coronas to achieve maximum coverage as shown in Fig. 1 and the sensor node distribution in corona-based network are shown in Fig. 2. Although such a strategy renders itself to the energy-hole problem in the sink’s vicinity but it can still be applied to critical applications where a large area needs to be covered with limited sensor nodes.
| Fig. 1: | Algorithm for minimum number of sensor node placement for full coverage |
| Fig. 2: | Engineered corona-based distribution using minimum number of sensor nodes |
Another application could be in the case of heterogeneous nodes where the sink’s neighbors are less in number as compared to other nodes but are more capable in terms of energy or processing power; thereby, they able to support a longer lifespan even under high load conditions for data forwarding.
Algorithm 1: The area is partitioned into the R adjacent coronas with radius r. The width of each corona is w and the ith corona is represented by Ci. In order to achieve the maximum coverage using minimum number of sensor nodes. The full coverage can be ensured using the algorithm shown in Fig. 1.
Optimum number of relay nodes placement for achieving balanced energy consumption: As the sensor nodes are distributed in the coronas and each corona’s sensor node can communicate with its neighboring corona’s relay nodes directly through one hop. So, the inner part of the network has a heavier traffic load than the outer part therefore, the density of the relay nodes increases from the outer to the inner coronas.
The following mathematical model given in Eq. 3 is used to distribute the relay nodes:
| (3) |
Algorithm 2 shown in Fig. 3 is used to distribute the minimum number of sensor nodes to achieve full coverage and the optimum number of relay nodes to optimize balanced energy consumption and to avoid redundant data transmission. The distribution of the sensor nodes and the relay nodes in coronas are shown in Fig. 4.
Algorithm 2: The area is partitioned into the R adjacent coronas with radius r.
| Fig. 3: | Algorithm for sensor node deployment strategy using relay nodes |
| Fig. 4: | Engineered corona-based distribution using an optimum number of relay nodes |
The width of each corona is w and the ith corona is represented by Ci. In order to reduce the redundant data transmission and to achieve the balanced energy consumption using relay nodes.
RESULTS AND DISCUSSION
Simulation results: According to the proposed strategy, two types of nodes are used. First, a minimum number of sensor nodes are distributed in the simulated area to achieve full coverage.
| Fig. 5: | Network lifespan of corona based deployment using relay nodes |
Second, the optimum number of relay nodes is distributed to forward the traffic load on each corona. According to the proposed mathematical model, the optimum number of sensor node and relay nodes was distributed in four coronas C1, C2, C3, C4 are 6, 13, 19 and 25 and the relay nodes are 57, 44, 25 and 0, respectively as given in Table 1. The proposed strategy reduces the redundant data transmission and optimizes the balanced energy consumption of the network. The performance of the proposed technique is evaluated according to the network lifespan, data delivery, residual energy and utilized energy of the network.
Network lifespan: The performance of the network according to the engineered corona based sensor node deployment strategies with full coverage using relay nodes and without relay nodes are evaluated using network lifespan models i.e., the time until the first node failure or runs out of energy, ten percent of the nodes failure and last packet received at sink from any sensor node.
At first node failure, the network lifespan of minimum sensor node placement with full coverage deployed network is about 600 sec of simulation time and for the proposed non-uniform corona based deployment strategy using a relay; it is about 5800 sec of simulation time with a considerable increase of 5200 sec of simulation time shown in Fig. 5. The same increase can be observed for another lifespan models.
Data delivery: As shown in Fig. 6, the data delivery ratio is similar for both type deployment strategies until the neighbor node of the sink start to die out. It can be seen that due to the energy hole problem, the sink is not able to receive the packets from sensor nodes. In proposed non-uniform corona based deployment using relay node, about 6000 packets are received. In comparison to minimum sensor node for full coverage 87% increase in data delivery is achieved.
| Fig. 6: | Data delivery of corona based deployment using relay nodes |
| Fig. 7: | Consumed energy of corona based deployment using relay nodes |
| Table 1: | Simulation parameters for corona-based sensor node deployment using relay nodes |
Energy consumed: It is observed that for both engineered corona based deployment strategy using minimum sensor nodes for full coverage and engineered corona based deployment strategy using relay nodes, the energy consumption stays at different levels.
| Table 2: | Performance analysis of the existing sensor node deployment strategies |
| Fig. 8: | Network residual energy of corona based deployment using relay nodes |
The Fig. 7 depicts that engineered corona based deployment strategy using minimum sensor node for full coverage utilize 25% of the total energy and proposed non-uniform corona based deployment strategy using relay nodes utilize more than 95% of the total energy during the network lifespan.
Residual energy: In sink locality the energy utilization rate is higher, therefore it is confirmed that for engineered corona based deployment strategy using minimum sensor node for full coverage, up to 75% energy is not being utilized at first node failure. This justifies that network lifespan cannot be prolonged and balanced energy consumption cannot be ensured by simply achieving full coverage with minimum sensor nodes. In our proposed non-uniform corona based sensor node deployment strategy using relay nodes, about 8% of the total energy has not been used at first node failure and less than 5% energy is left unused at last packet received as shown in Fig. 8.
Performance analysis of the proposed deployment strategies: This section, discuss the performance of the proposed deployment strategies and the results are compared against the existing deployment strategies in literature. Simulation results demonstrate that the proper placement of sensor nodes guaranteed full coverage, connectivity, enhanced lifetime, increased data delivery and most importantly optimized balanced energy consumption of the sensor node in WSNs. The use of a combination of sensor and relay nodes, according to the traffic load has helped to disseminate their energy in a much more balanced rate.
The performance analysis of the existing deployment strategies of WSNs is evaluated and summarized in Table 2.
It has observed from the analysis that the network density does not affect the energy consumption rates of a network, but rather the proper placement of nodes affects it. The energy consumption stays at different levels under same node densities for the five considered deployment strategies. This implies that the network lifetime cannot be prolonged and optimized balanced energy consumption cannot be ensured by simply increasing the density of the deployed nodes. The proposed sensor node deployment strategies utilized more than 95% of the total energy of the network during the network lifetime shown in Table 2.
CONCLUSION
In order to achieve full coverage using minimum sensor node first an "Engineered Corona-based Sensor Node Deployment Strategy using Minimum Sensor Nodes for Full Coverage" has been proposed. Second, the problem of unbalanced energy consumption can be resolved using "Engineered corona-based sensor node deployment strategy using relay nodes". In the proposed study the sensor nodes are deployed in such a way as to decrease from the outer corona to the inner corona according to the communication range of the node and the density of the corona. The relay nodes are deployed in such a way is to increase from the outer coronas to the inner coronas according to the traffic pattern.
Simulation result shows that the proposed techniques achieves full coverage using minimum sensor node and optimal placement of relay nodes enhanced the lifespan of the network, energy utilization data delivery and reduces the remaining energy of the wireless sensor network.