Elsevier

Ad Hoc Networks

Volume 6, Issue 4, June 2008, Pages 621-655
Ad Hoc Networks

Strategies and techniques for node placement in wireless sensor networks: A survey

https://doi.org/10.1016/j.adhoc.2007.05.003Get rights and content

Abstract

The major challenge in designing wireless sensor networks (WSNs) is the support of the functional, such as data latency, and the non-functional, such as data integrity, requirements while coping with the computation, energy and communication constraints. Careful node placement can be a very effective optimization means for achieving the desired design goals. In this paper, we report on the current state of the research on optimized node placement in WSNs. We highlight the issues, identify the various objectives and enumerate the different models and formulations. We categorize the placement strategies into static and dynamic depending on whether the optimization is performed at the time of deployment or while the network is operational, respectively. We further classify the published techniques based on the role that the node plays in the network and the primary performance objective considered. The paper also highlights open problems in this area of research.

Introduction

Recent years have witnessed an increased interest in the use of wireless sensor networks (WSNs) in numerous applications such as forest monitoring, disaster management, space exploration, factory automation, secure installation, border protection, and battlefield surveillance [1], [2]. In these applications, miniaturized sensor nodes are deployed to operate autonomously in unattended environments. In addition to the ability to probe its surroundings, each sensor has an onboard radio to be used for sending the collected data to a base-station either directly or over a multi-hop path. Fig. 1 depicts a typical sensor network architecture. For many setups, it is envisioned that WSNs will consist of hundreds of nodes that operate on small batteries. A sensor stops working when it runs out of energy and thus a WSN may be structurally damaged if many sensors exhaust their onboard energy supply. Therefore, WSNs should be carefully managed in order to meet applications’ requirements while conserving energy.

The bulk of the research on WSNs has focused on the effective support of the functional, such as data latency, and the non-functional, such as data integrity, requirements while coping with the resource constraints and on the conservation of available energy in order to prolong the life of the network. Contemporary design schemes for WSNs pursue optimization at the various layers of the communication protocol stack. Popular optimization techniques at the network layer include multi-hop route setup, in network data aggregation and hierarchical network topology [3]. In the medium access control layer, collision avoidance, output power control, and minimizing idle listening time of radio receivers are a sample of the proposed schemes [1], [4]. At the application layer, examples include adaptive activation of nodes, lightweight data authentication and encryption, load balancing and query optimization [5], [6].

One of the design optimization strategies is to deterministically place the sensor nodes in order to meet the desired performance goals. In such case, the coverage of the monitored region can be ensured through careful planning of node densities and fields of view and thus the network topology can be established at setup time. However, in many WSNs applications sensors deployment is random and little control can be exerted in order to ensure coverage and yield uniform node density while achieving strongly connected network topology. Therefore, controlled placement is often pursued for only a selected subset of the employed nodes with the goal of structuring the network topology in a way that achieves the desired application requirements. In addition to coverage, the nodes’ positions affect numerous network performance metrics such as energy consumption, delay and throughput. For example, large distances between nodes weaken the communication links, lower the throughput and increase energy consumption.

Optimal node placement is a very challenging problem that has been proven to be NP-Hard for most of the formulations of sensor deployment [7], [8], [9]. To tackle such complexity, several heuristics have been proposed to find sub-optimal solutions [7], [10], [11], [12]. However, the context of these optimization strategies is mainly static in the sense that assessing the quality of candidate positions is based on a structural quality metric such as distance, network connectivity and/or basing the analysis on a fixed topology. Therefore, we classify them as static approaches. On the other hand, some schemes have advocated dynamic adjustment of nodes’ location since the optimality of the initial positions may become void during the operation of the network depending on the network state and various external factors [13], [14], [15]. For example, traffic patterns can change based on the monitored events, or the load may not be balanced among the nodes, causing bottlenecks. Also, application-level interest can vary over time and the available network resources may change as new nodes join the network, or as existing nodes run out of energy.

In this paper we opt to categorize the various strategies for positioning nodes in WSNs. We contrast a number of published approaches highlighting their strengths and limitations. We analyze the issues, identify the various objectives and enumerate the different models and formulations. We categorize the placement strategies into static and dynamic depending on whether the optimization is performed at the time of deployment or while the network is operational, respectively. We further classify the published techniques based on the role that the node plays in the network and the primary performance objective considered. Our aim is to help application designers identify alternative solutions and select appropriate strategies. The paper also outlines open research problems.

The paper is organized as follows. The next section is dedicated to static strategies for node positioning. The different techniques are classified according to the deployment scheme, the primary optimization metrics and the role that the nodes play. In Section 3 we turn our attention to dynamic positioning schemes. We highlight the technical issues and describe published techniques which exploit node repositioning to enhance network performance and operation. Section 4 discusses open research problems; highlighting the challenges of coordinated repositioning of multiple nodes and node placement in three-dimensional application setups and describes a few attempts to tackle these challenges. Finally, Section 5 concludes the paper.

Section snippets

Static positioning of nodes

As mentioned before, the position of nodes have a dramatic impact on the effectiveness of the WSN and the efficiency of its operation. Node placement schemes prior to network startup usually base their choice of the particular nodes’ positions on metrics that are independent of the network state or assume a fixed network operation pattern that stays unchanged throughout the lifetime of the network. Examples of such static metrics are area coverage and inter-node distance, among others. Static

Dynamic repositioning of nodes

Most of the protocols described above initially compute the optimal location for the nodes and do not consider moving them once they have been positioned. Moreover, the context of the pursued optimization strategies is mainly static in the sense that assessing the quality of candidate positions are based on performance metrics like the data rate, sensing range, path length in terms of the number of hops from a sensor node to the base-station, etc. In addition, the placement decision is made at

Open research problems

While significant progress has been made in researching the optimization of node positioning in WSNs, many challenging problems remain. In this section, we highlight open research problems, identify the issues involved and report on ongoing work and preliminary results. We categorize open problems into coordinated dynamic placement of multiple nodes and the positioning of sensors in three-dimensional application setups.

Conclusion

Wireless sensor networks (WSNs) have attracted lots of attention in recent years due to their potential in many applications such as border protection and combat field surveillance. Given the criticality of such applications, maintaining efficient network operation is a fundamental objective. However, the resource-constrained nature of sensor nodes and the ad-hoc formation of the network, often coupled with unattended deployment, pose non-conventional challenges and motivate the need for

Mohamed F. Younis received B.S. degree in computer science and M.S. in engineering mathematics from Alexandria University in Egypt in 1987 and 1992, respectively. In 1996, he received his Ph.D. in computer science from New Jersey Institute of Technology. He is currently an associate professor in the department of computer science and electrical engineering at the university of Maryland Baltimore County (UMBC). Before joining UMBC, he was with the Advanced Systems Technology Group, an Aerospace

References (86)

  • A. Efrat, S. Har-Peled, J.S.B. Mitchell, Approximation algorithms for two optimal location problems in sensor networks,...
  • X. Cheng, DZ Du, L. Wang, B. Xu, Relay sensor placement in wireless sensor networks, ACM/Springer Journal of Wireless...
  • S. Poduri, S. Pattem, B. Krishnamachari, G.S. Sukhatme, Sensor network configuration and the curse of dimensionality,...
  • J. Pan et al.

    Optimal base-station locations in two-tiered wireless sensor networks

    IEEE Transactions on Mobile Computing

    (2005)
  • S.S. Dhillon, K. Chakrabarty, Sensor placement for effective coverage and surveillance in distributed sensor networks,...
  • T. Clouqueur, V. Phipatanasuphorn, P. Ramanathan and K.K. Saluja, Sensor deployment strategy for target detection, in:...
  • K. Akkaya et al.

    Sink repositioning for enhanced performance in wireless sensor networks

    Computer Networks

    (2005)
  • G. Wang, G. Cao, T. La Porta, W. Zhang, Sensor relocation in mobile sensor networks, in: Proceedings of the 24th...
  • J. Wu, S. Yang, SMART: A scan-based movement assisted sensor deployment method in wireless sensor networks, in:...
  • A. Brooks, A. Makarenko, T. Kaupp, S. Williams, H. Durrant-Whyte, Implementation of an indoor active sensor network,...
  • V.A. Petrushin, G. Wei, O. Shakil, D. Roqueiro, V. Gershman, Multiple-sensor indoor surveillance system, in:...
  • L. Krishnamurthy et al., Design and deployment of industrial sensor networks: experiences from a semiconductor plant...
  • J. Paek, K. Chintalapudi, J. Cafferey, R. Govindan, Sami Masri, A wireless sensor network for structural health...
  • K. Mechitov, W. Kim, G. Agha, T. Nagayama, High-frequency distributed sensing for structure monitoring, in: Proceedings...
  • J. Berry, L. Fleischer, W.E. Hart, C.A. Phillips, Sensor placement in municipal water networks, in: Proceedings of the...
  • J.-P. Watson, H. Greenberg, W.E. Hart, A multiple-objective analysis of sensor placement optimization in water...
  • H.H. Gonzalez-Banos, J.C. Latombe, A randomized art-gallery algorithm for sensor placement, in: Proceedings of the 17th...
  • L. Navarro, J. Dolan, P. Khosla, Optimal sensor placement for cooperative distributed vision, in: Proceedings of the...
  • M. Ishizuka, M. Aida, Performance study of node placement in sensor networks, in: Proceedings of the 24th International...
  • K. Xu, H. Hassanein, G. Takahara, W. Wang, Relay node deployment strategies in heterogeneous wireless sensor networks:...
  • K. Xu, H. Hassanein, G. Takahara, Q. Wang, Relay node deployment strategies in heterogeneous wireless sensor networks:...
  • C.-F. Huang, Y.-C. Tseng, The coverage problem in a wireless sensor network, in: Proceedings of the ACM 9th Annual...
  • A. Boukerche, X. Fei, R.B. Araujo, A coverage preserving and fault tolerant based scheme for irregular sensing range in...
  • S. Meguerdichian, F. Koushanfar, M. Potkonjak, M.B. Srivastava, Coverage problems in wireless ad-hoc sensor networks,...
  • D. Pompili, T. Melodia, I.F. Akyildiz, Deployment analysis in underwater acoustic wireless sensor networks, in:...
  • E.S. Biagioni, G. Sasaki, Wireless sensor placement for reliable and efficient data collection, in: Proceedings of the...
  • K. Kar, S. Banerjee, Node placement for connected coverage in sensor networks, in: Proceedings of the Workshop on...
  • J. Bredin, E. Demaine, M. Taghi Hajiaghayi, D. Rus, Deploying sensor networks with guaranteed capacity and fault...
  • P. Jacquet, Geometry of information propagation in massively dense ad hoc networks, in: Proceedings of the 5th ACM...
  • S. Toumpis, L. Tassiulas, Packetostatics: deployment of massively dense sensor networks as an electrostatics problem,...
  • S. Toumpis, G.A. Gupta, Optimal placement of nodes in large sensor networks under a general physical layer model, in:...
  • K. Dasgupta, M. Kukreja, K. Kalpakis, Topology-aware placement and role assignment for energy-ecient information...
  • Y. Chen, C. Chuan, Q. Zhao, Sensor placement for maximizing lifetime per unit cost in wireless sensor networks, in:...
  • Cited by (0)

    Mohamed F. Younis received B.S. degree in computer science and M.S. in engineering mathematics from Alexandria University in Egypt in 1987 and 1992, respectively. In 1996, he received his Ph.D. in computer science from New Jersey Institute of Technology. He is currently an associate professor in the department of computer science and electrical engineering at the university of Maryland Baltimore County (UMBC). Before joining UMBC, he was with the Advanced Systems Technology Group, an Aerospace Electronic Systems R&D organization of Honeywell International Inc. While at Honeywell he led multiple projects for building integrated fault tolerant avionics, in which a novel architecture and an operating system were developed. This new technology has been incorporated by Honeywell in multiple products and has received worldwide recognition by both the research and the engineering communities. He also participated in the development the Redundancy Management System, which is a key component of the Vehicle and Mission Computer for NASA’s X-33 space launch vehicle. His technical interest includes network architectures and protocols, embedded systems, fault tolerant computing and distributed real-time systems. He has four granted and three pending patents. He served on multiple technical committees and published over 85 technical papers in referred conferences and journals.

    Kemal Akkaya received his BS degree in Computer Science from Bilkent University, Ankara, Turkey in 1997, MS degree in Computer Engineering from Middle East Technical University (METU), Ankara, Turkey in 1999 and PhD in Computer Science from University of Maryland Baltimore County (UMBC), Baltimore, MD in 2005. He worked as a Software Developer in A World Bank Project in Ankara, Turkey in 2000. He is currently an assistant professor in the Department of Computer Science at Southern Illinois University Carbondale, IL. His research interests include energy-aware protocols for wireless sensor networks, security and quality of service issues in ad hoc wireless and sensor networks.

    View full text