On energy provisioning and relay node placement for wireless sensor networks

Wireless sensor networks that operate on batteries have limited network lifetime. There have been extensive recent research efforts on how to design protocols and algorithms to prolong network lifetime. However, due to energy constraint, even under the most efficient protocols and algorithms, the ne...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on wireless communications 2005-09, Vol.4 (5), p.2579-2590
Main Authors: Hou, Y.T., Yi Shi, Sherali, H.D., Midkiff, S.F.
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Applied sciences
Batteries
Energy provisioning
Exact sciences and technology
flow routing
Heuristic
Heuristic algorithms
Mathematical models
network lifetime
Networks
Placement
Power control
Protocols
Provisioning
relay node placement
Relays
Routing
Searching
Senior members
Sensors
Services and terminals of telecommunications
Software algorithms
Studies
Systems, networks and services of telecommunications
Telecommunications
Telecommunications and information theory
Telemetry. Remote supervision. Telewarning. Remote control
Transmission and modulation (techniques and equipments)
Wireless communication
Wireless sensor networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Wireless sensor networks that operate on batteries have limited network lifetime. There have been extensive recent research efforts on how to design protocols and algorithms to prolong network lifetime. However, due to energy constraint, even under the most efficient protocols and algorithms, the network lifetime may still be unable to meet the mission's requirements. In this paper, we consider the energy provisioning (EP) problem for a two-tiered wireless sensor network. In addition to provisioning additional energy on the existing nodes, we also consider deploying relay nodes (RNs) into the network to mitigate network geometric deficiencies and prolong network lifetime. We formulate the joint problem of EP and RN placement (EP-RNP) into a mixed-integer nonlinear programming (MINLP) problem. Since an MINLP problem is NP-hard in general, and even state-of-the-art software and techniques are unable to offer satisfactory solutions, we develop a heuristic algorithm, called Smart Pairing and INtelligent Disc Search (SPINDS), to address this problem. We show a number of novel algorithmic design techniques in the design of SPINDS that effectively transform a complex MINLP problem into a linear programming (LP) problem without losing critical points in its search space. Through numerical results, we show that SPINDS offers a very attractive solution and some important insights to the EP-RNP problem.
ISSN:1536-1276
1558-2248
DOI:10.1109/TWC.2005.853969