We propose a novel relay augmentation strategy for extending the lifetime of a certain class of wireless sensor networks. In this class sensors are located at fixed and pre-determined positions and all communication takes place via multi-hop paths in a fixed routing tree rooted at the base station. It is assumed that no accumulation of data takes place along the communication paths and that there is no restriction on where additional relays may be located. Under these assumptions the optimal extension of network lifetime is modelled as the Euclidean @math -bottleneck Steiner tree problem. Only two approximation algorithms for this NP-hard problem exist in the literature: a minimum spanning tree heuristic (MSTH) with performance ratio 2, and a probabilistic 3-regular hypergraph heuristic (3RHH) with performance ratio @math . We present a new iterative heuristic that incorporates MSTH and show via simulation that our algorithm performs better than MSTH in extending lifetime, and outperforms 3RHH in terms of efficiency.
Augmenting a network by deploying additional (non-sensing) relays is a powerful and relatively inexpensive method of optimising many topology dependent WSN objectives. This concept is not new to the literature, and has been considered under various network models and objectives. Relay augmentation strategies exist that supplement the primary objective of lifetime extension with objectives related to coverage @cite_7 , connectivity @cite_6 and balanced traffic flow @cite_29 , @cite_1 .
@cite_29 @cite_1 @cite_6 @cite_7
2038464572 2156919687 2009106662 2050266688
We consider a two-tiered Wireless Sensor Network (WSN) consisting of sensor clusters deployed around strategic locations and base-stations (BSs) whose locations are relatively flexible. Within a sensor cluster, there are many small sensor nodes (SNs) that capture, encode and transmit relevant information from the designated area, and there is at least one application node (AN) that receives raw data from these SNs, creates a comprehensive local-view, and forwards the composite bit-stream toward a BS. In practice, both SN and AN are battery-powered and energy-constrained, and their node lifetimes directly affect the network lifetime of WSNs. In this paper, we focus on the topology control process for ANs and BSs, which constitute the upper tier of a two-tiered WSN. We propose approaches to maximize the topological network lifetime of the WSN, by arranging BS location and inter-AN relaying optimally. Based on an algorithm in Computational Geometry, we derive the optimal BS locations under three topological lifetime definitions according to mission criticality. In addition, by studying the intrinsic properties of WSNs, we establish the upper and lower bounds of their maximal topological lifetime. When inter-AN relaying becomes feasible and favorable, we continue to develop an optimal parallel relay allocation to further prolong the topological lifetime of the WSN. An equivalent serialized relay schedule is also obtained, so that each AN only needs to have one relay destination at any time throughout the mission. The experimental performance evaluation demonstrates the efficacy of topology control as a vital process to maximize the network lifetime of WSNs. In a heterogeneous wireless sensor network (WSN), relay nodes (RNs) are adopted to relay data packets from sensor nodes (SNs) to the base station (BS). The deployment of the RNs can have a significant impact on connectivity and lifetime of a WSN system. This paper studies the effects of random deployment strategies. We first discuss the biased energy consumption rate problem associated with uniform random deployment. This problem leads to insufficient energy utilization and shortened network lifetime. To overcome this problem, we propose two new random deployment strategies, namely, the lifetime-oriented deployment and hybrid deployment. The former solely aims at balancing the energy consumption rates of RNs across the network, thus extending the system lifetime. However, this deployment scheme may not provide sufficient connectivity to SNs when the given number of RNs is relatively small. The latter reconciles the concerns of connectivity and lifetime extension. Both single-hop and multihop communication models are considered in this paper. With a combination of theoretical analysis and simulated evaluation, this study explores the trade-off between connectivity and lifetime extension in the problem of RN deployment. It also provides a guideline for efficient deployment of RNs in a large-scale heterogeneous WSN. Clustering and relaying techniques are important approaches towards mitigating the problem of finite network lifetime in wireless sensor networks. To this end, given a clustered wireless sensor network (WSN) (with defined cluster heads and their associated clusters) and a given relay node placement, we present a distributed service allocation algorithm for the relay node for maximizing network lifetime. We evaluate the performance of our method through theoretical analysis as well as simulations, and demonstrate the superior performance of our proposed method compared to a greedy periodic approach. Abstract Energy is one of the scarcest resources in wireless sensor network (WSN). One fundamental way of conserving energy is judicious deployment of sensor nodes within the network area so that energy flow remains balanced throughout the network. This avoids the problem of occurrence of ‘energy holes’ and ensures prolonged network lifetime. We have first investigated the problem for enhancing network lifetime using homogeneous sensor nodes. From our observation it is revealed that energy imbalance in WSN occurs due to relaying of data from different parts of the network towards sink. So for improved energy balance instead of using only sensor nodes it is desirable to deploy relay nodes in addition to sensor nodes to manage such imbalance. We have also developed a location-wise pre-determined heterogeneous node deployment strategy based on the principle of energy balancing derived from this analysis, leading to an enhancement of network lifetime. Exhaustive simulation is performed primarily to measure the extent of achieving our design goal of enhancing network lifetime while attaining energy balancing and maintaining coverage. The simulation results also show that our scheme does not compromise with other network performance metrics such as end-to-end delay, packet loss, throughput while achieving the design goal. Finally all the results are compared with two competing schemes and the results confirm our scheme's supremacy in terms of both design performance metrics as well as network performance metrics.