论文部分内容阅读
无线传感器网络中考虑时延约束的中继节点部署(delay constrained relay node placement,DCRNP)问题通过部署最少数量的中继节点使得所有传感器节点与汇聚节点之间都有满足时延约束条件的通路.DCRNP问题已经被证明是NP-hard问题.本文提出基于汇合点及剪枝技术的中继节点部署(convergence-pruning-based relay node placement,CPRNP)算法近似求解DCRNP问题.CPRNP算法分为两个阶段,第1阶段找出所有可能使满足时延约束的通路相交的汇合点,并生成一棵以汇聚节点为根节点连接所有传感器节点的最短路径树;在第2阶段中CPRNP算法通过不断删除或替代最短路径树中的节点,逐步缩减中继节点的部署规模.仿真结果表明,本文提出的CPRNP算法与已有算法相比可以明显地减少中继节点部署数量.
Delay constrained relay node placement (DCRNP) problem in wireless sensor networks Problem By deploying a minimum number of relay nodes, all sensor nodes and sink nodes have paths satisfying the delay constraint. The DCRNP problem has been proved to be NP-hard. This paper presents a DCRNP problem based on convergence-pruning-based relay node placement (CPRNP) algorithm. The CPRNP algorithm is divided into two phases , The first phase finds all the convergence points that may intersect the paths satisfying the delay constraint and generates a shortest path tree with all the sensor nodes connected by the sink node as the root node; in the second phase, the CPRNP algorithm continuously deletes Instead of nodes in the shortest path tree, the deployment scale of relay nodes is gradually reduced.The simulation results show that the CPRNP algorithm proposed in this paper can obviously reduce the number of relay node deployment compared with the existing algorithms.