On energy provisioning and relay node placement for wireless sensor networks
On energy provisioning and relay node placement for wireless sensor networks
复制标题
DOI：
10.1109/twc.2005.853969
复制
发表时间：
2005-09-01
影响因子：
10.4
通讯作者：
Midkiff, SF
中科院分区：
文献类型：
--
作者：
Hou, YT;Shi, Y;Midkiff, SF
使用电池运行的无线传感器网络的网络寿命有限。最近，人们对如何设计协议和算法以延长网络生命周期进行了广泛的研究。然而，由于能量限制，即使在最高效的协议和算法下，网络寿命仍可能无法满足任务要求。在本文中，我们考虑两层无线传感器网络的能量供应（EP）问题。除了在现有节点上提供额外的能量外，我们还考虑在网络中部署中继节点（RN），以减轻网络几何缺陷并延长网络生命周期。我们将 EP 和 RN 放置的联合问题 (EP-RNP) 表述为混合整数非线性规划 (MINLP) 问题。由于 MINLP 问题一般来说是 NP 难问题，即使是最先进的软件和技术也无法提供令人满意的解决方案，因此我们开发了一种启发式算法，称为智能配对和智能光盘搜索（SPINDS）来解决这个问题。我们在 SPINDS 的设计中展示了许多新颖的算法设计技术，这些技术可以有效地将复杂的 MINLP 问题转化为线性规划 (LP) 问题，而不会丢失搜索空间中的关键点。通过数值结果，我们表明 SPINDS 提供了一个非常有吸引力的解决方案以及对 EP-RNP 问题的一些重要见解。
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.