复杂三维曲面覆盖算法研究

Algorithm research for complex 3-D surface coverage

针对无线传感器网络中三维空间曲面覆盖问题进行研究,建立传感器节点的三维感知模型,考虑到曲面的不规则性,曲面凸点会成为节点感知过程中的障碍物,形成三维空间中特有的三维感知盲区。首先从理论上对简单曲面进行分析,计算出实现有限曲面全覆盖所需的最少节点数,在对三维曲面进行网格划分以及根据三维感知盲区改进适应度函数后,引入差分进化(DE)算法对随机部署在三维空间中的传感器节点的位置坐标进行优化,通过大量仿真实验得出实现目标曲面全覆盖所需的最少的节点数,引入误差率,通过提出的测试准则验证了引用DE算法解决简单三维曲面覆盖问题的有效性。最后将DE算法运用到解决复杂三维曲面覆盖问题中,取得了良好的效果。

To solve the coverage problem of 3-D surface in wireless sensor networks, a 3-D perceptual model of sensornodes is built, and considering the irregularities of the 3-D surface, the salient point on the surface can become obstacles inthe process of perception of the node and lead to the problem of 3-D monitoring blind area. Firstly it calculates the requiredminimum number of nodes which can realize complete coverage of the limited surface through analyzing the simple 3-Dsurface theoretically, meshes on the surface and improving fitness function based on the 3-D monitoring blind area, optimizesthe position coordinates of the randomly deployed nodes by reference of Differential Evolution(DE)algorithm, and calculatesthe minimum number of nodes for realizing a complete coverage of target surface through a large number of simulationexperiments, then introduces the error rate and test criterion to verify the effectiveness of referencing to DE algorithmto solve the simple 3-D surface coverage problems. Finally the DE algorithm is applied to solve the complex 3-D surfacecoverage problems which achieves good results.