无线传感器网络中的中继节点布置问题研究

Placing relay nodes in wireless sensor networks can effectively prolong the network lifetime and enhance the connectivity or fault tolerance of the network. With reducing the required number of relay nodes as the starting point, this project will explore relay node placement schemes that can further reduce the network cost and have wide applicable range and strong practicality. The proposed schemes can basically meet the theory and application requirements of wireless sensor networks. Based on the geometric theory, an algorithm of placing relay nodes in a cluster will be proposed, which is applicable to the case of sensor nodes distributed in the three-dimensional space; Base on the classical Euclidean Steiner tree problem, an algorithm of relay node placement in the flat network will be proposed. Based on the theory of geometric covering, an algorithm of relay node placement in the hierarchical network will be proposed, in which both the coverage of relay node and the connectivity among relay nodes are considered when selecting relay node. Based on the relay node placement problem in the hierarchical network, an algorithm of minimum cost relay node placement in the hierarchical network will be proposed, in which the cost of relay nodes and the cost of energy are comprehensively considered. To enlarge the applicable range and enhance the practicality, the algorithms of relay node placement that only meet the connectivity will be further extended to the cases such as meeting the fault tolerance, having base station and so on.

在无线传感器网络布置中继节点可有效延长网络生存时间、增强网络的连通性或容错性，本项目以减少所需的中继节点数目为切入点，探索能进一步减少网络成本、适用范围广且实用性强的中继节点布置方案，使之基本满足在无线传感器网络中的理论和应用的需要。以几何理论为基础，提出一种适用于传感器节点三维分布的簇内中继节点布置算法；以经典的欧几里德Steiner树问题为基础，提出一种单层网络中的中继节点布置算法；以几何覆盖原理为基础，提出一种分层网络中的中继节点布置算法，在选定中继节点时统一考虑中继节点的覆盖性以及中继节点之间的连通性；以分层网络中的中继节点布置问题为基础，提出一种分层网络中的最小成本中继节点布置算法，综合考虑中继节点的成本和能量的成本。为了扩大适用范围和增强实用性，进一步将仅满足连通性的中继节点布置算法扩展到满足容错性以及存在基站等情况。

为了延长网络生存时间或保证网络的连通性，可以在无线传感器网络中布置少量专门用于路由数据的中继节点。本项目以几何理论为基础，系统深入地研究了无线传感器网络中的中继节点布置问题，主要研究内容和研究结果包括：.(1) 研究了不同网络模型和优化目标下的簇内中继节点布置问题，由于作为簇头的中继节点的功能类似于一个独立网络中的基站，因此无线传感器网络中的基站布置算法也可用于求解类似的簇内中继节点布置问题。(i) 假设传感器节点可以自动调整其无线发送功率，提出了一种基于最速下降法的中继节点布置算法，使得传感器节点发送数据所消耗的总功耗最小。在该算法中，先选择基站的一个初始位置，然后沿着负梯度方向，通过不断迭代求出总功耗的极小值点。实验结果表明，该算法可以得到使得传感器节点总功耗最小的中继节点位置。(ii) 假设传感器节点可以自动调整其无线发送功率，提出了一种基于贪婪搜索的中继节点布置算法，最大化了所有传感器节点的最短生存时间。首先证明了对于一个三维无线传感器网络，中继节点的最优位置最多只取决于所有传感器节点中的某四个节点，然后通过贪婪搜索得到这四个节点。相比现有算法，该算法可以适用于三维空间。(iii) 假设传感器节点具有固定的无线发送功率和通信范围，提出了一种基于平面分割的中继节点布置算法，使得传感器节点用于传输数据的总功耗最小。通过所有传感器节点的通信圆来分割二维平面，可以得到有限多个具有不同总功耗的中继节点位置，从而将中继节点位置在二维平面的无限搜索空间缩小为有限多个搜索空间。实验结果表明，该算法可以得到使得传感器节点总功耗最小的中继节点位置。.(2) 研究了单层网络中满足连通性的中继节点布置问题，提出了一种基于合并连通片的近似算法，以最小化使得网络连通所需的中继节点数目。在该算法迭代求解过程的每步中，先基于Voronoi图求出各个连通片的外围节点，然后尝试布置最小数目的中继节点，以连接其中两个连通片或三个连通片中的外围节点，形成新的连通片，重复该迭代过程直至所有节点连通。实验结果表明该算法得到的平均中继节点数目约为现有算法的90%。.通过本项目的研究，推动了无线传感器网络中继节点布置问题的研究，促进了项目组团队的成长，已发表和录用了5篇相关论文，其中3篇被SCI收录，5篇被EI收录，此外还有4篇论文已投稿，已培养了1名硕士研究生毕业，现有5名在读硕士研究生正在研究此方向。