传感器网络节点表面部署优化算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇传感器网络节点表面部署优化算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：节点部署是传感器网络中的一个基本问题，其直接关系到整个网络的性能。但现有的传感器网络节点部署研究大多针对平面以及3D空间的场景，对于3D表面场景部署的研究较少，为此针对该场景研究传感器网络节点部署优化算法。首先通过数学微分几何方法对3D表面构建数学模型，然后通过质心Voronoi剖分对3D表面进行分区，提出一种误差函数来评价部署方法的优劣程度，最后通过仿真比较了该方法与其他表面部署方法的性能优劣，结果表明，所提方法优于对比算法。
关键词：传感器网络；节点部署；3D表面；质心Voronoi剖分；误差函数
0 引言
传感器网络节点部署是传感器网络的一个基本问题，对感知精确、覆盖优化以及网络拓扑等多方面有重要影响。传感器网络的传统部署方式常常采用随机播撒或者人工部署。随机播撒由于存在着许多不确定性，部署质量往往不高，因此在条件允许时为提高感知质量一般采用人工部署。传感器网络的应用广泛，其部署情形包括平面、立体以及立体表面等场景，因此在特定场景中如何实现感知节点优化部署，提高区域的感知效率，减少感知误差是传感器网络应用的一个重要问题，学者针对不同的应用场景对传感器网络节点的部署进行了大量的研究[1-13]。
当前对于传感器网络部署的研究主要集中在平面和立体中的兴趣区域（Field of Interest， FoI）的部署研究。对于传感器节点部署的早期较为经典的研究主要是K覆盖[4-5]，通过节点的优化部署，实现对区域的增强覆盖，监测区域的每个点都能被K个感知节点感知。如何在使得覆盖性能优化情况下保证整个网络连通性，大量学者针对该问题做了大量研究[6-7]。
对于立体部署的研究主要应用场景为水下监测[8-10]。文献[10]提出了一种鱼群启发的水下传感器节点布置算法， 通过模拟鱼群行为， 并结合拥挤度控制， 使节点自主趋向并覆盖事件， 同时实现节点分布密度与事件分布密度相匹配。文献[11]提出一种基于检测融合的部署策略，采用NeymanPearson准则融合单元网格内所有传感器节点的检测信息，实现正方形和正三角形两种单元网格的高效覆盖，进而分别给出针对两种单元网格的监测区域网格划分方法，从而确定监测区域需要的传感器节点数量以及放置的具置。
上述研究大多是针对覆盖质量的研究，而针对感知质量的部署研究尚较少。文献[12]提出一种本地控制率，每个传感器节点结合事件概率密度函数来考虑移动方式。该函数意义为不同位置事件发生的概率，若某位置函数值大，则表示事件发生概率大，可理解为当前区域更加重要，需要更加可靠的感知。然后，节点通过一个成本函数来确定移动方式。文献[13]研究表明对于3D表面的传感器网络部署是不同于对应的2D平面和三维立体的情况，并被证明表面部署的完全覆盖最优解为NP难问题。因此前期对于2D平面和三维立体的研究的算法策略不能直接应用于3D表面的部署。
在本文研究中，考虑在3D表面情形下的FoI，通过优化部署使得最大化整个网络感知质量。传感器节点感知模型中的布尔模型考虑为比较理想情况，而概率感知模型更加精确。一般来说感知节点读取的数据存在误差，对于给定的传感器节点部署在FoI中，往往不同的部署策略获取的数据精度各不相同。
本文假定传感器节点集合部署在FoI的3D表面，节点能够随机部署在区域上的任何位置。为优化表面部署性能，提出一种测量感知数据不可靠性的函数，研究表面通过广义的质心Voronoi剖分达到优化部署。通过保形参数，本文提出了一系列的算法来实现感知节点的优化部署。
1 问题模型
本文研究的3D表面部署模型为开阔、不封闭、且为凸的，这样的部署应用较多，如野外山地部署、大型建筑区域等。传感器节点部署为静态同构，部署后不能移动，感知节点的感知半径和感知能力相同。传感器节点的感知数据往往存在误差，造成该误差的主要原因有很多，如与目标点距离、环境干扰感知能力等，在本文中定义数据感知误差主要由感知节点与监测目标的距离引起，因此定义误差函数为其距离函数。
2 部署优化方法
下面先研究如何在感知节点部署确定下，通过合理对每个感知节点感知区域分区，优化表面感知效果。
优化表面感知问题（Optimal Surface Sensing Problem，OSSP）定义：对于确定的位置部署，寻找一种分区使得G（P，V）最小。
对于给定的区域A和节点位置部署P，对传感器节点的分区有无限种可能。依据Voronoi剖分的定义有：
对于平面V剖分的计算算法较多，通过一个预定义的函数计算质心V剖分。但平面的V剖分算法不能直接应用于3D表面，因为其表面复杂，且距离相对于平面的关系是不同的。且V剖分算法的边界条件也限制了其在3D表面的应用。因此需要一种近似算法将平面的V剖分有效扩展到3D表面。
3 3D表面到平面映射
下面研究如何将3D表面映射到2D平面的问题。主要思想为通过3D表面参数化实现从3D曲面到平面的映射，将平面的质心V剖分算法扩展到3D表面，首先在平面计算出质心V剖分，然后反映射到3D表面。但是，需要一种特定的表面参数化方法，其不带边界限制条件。
3D表面参数化的方法采用保角映射，通过黎曼映射定理，表面参数被映射到平面上。计算保形映射的一种方法是离散表面瑞奇流。在3D曲面投影到平面上时需要补偿距离失真，本文采用黎曼度量的比例因子，称为保形因子（Conformal Factor，CF）。平面压缩通过保形映射到3D曲面，有
4 算法
本章设计一种基于三角结构的算法来解决OSDP。3D表面模型数据由SRTM数据库提供，它是一种网格结构，本文将其转化为三角表面结构。
算法思想主要步骤如下：
1）节点随机部署在3D表面上，表示为M；
2）通过计算表面的保形映射，将其映射到平面上，表示为 f：MD；
3）计算保形因子cf，其度量了M在平面D上的失真率；
4）基于补偿度量计算平面D的广义质心V剖分，代表传感器位置和感知区域；
5）通过D到M的逆映射f-1，将该剖分映射到感知区域模型上。
4.1 参数表面化
通过离散表面瑞奇流工具实现3D表面参数化通过三角模型M=（V，E，F）映射到平面D上。算法的关键步骤是设置目标顶点vi∈V的高斯曲率为i，使得其满足边界条件。映射结果存储在每个vi的数据结构中，称为uv值，通常把U 方向称为行，V 方向称为列， 曲面也因此可以看作U方向为轨迹引导线对很多V 方向的截面线做的一个扫描，对应于平面上的每个坐标点。
5 算法仿真分析
本文针对不复杂的3D表面带复杂边界的外形进行了仿真分析。模型1为720m×720m，高度500m，近似为5k三角覆盖，模型2为900m×900m，高度约为550m，近似为20k三角覆盖。
感知节点首先随机部署在测试区域表面，模型1为300个节点，模型2为200个节点。图1、2显示了表面部署的进化过程。第1轮，感知节点区域随机剖分，从图3可以看出高度的误差；第2轮，感知区域重新通过V剖分，其总体误差值减少47.58%；第3轮，通过重新部署，满足广义质心剖分，其整体误差值显著减少到89.94%。感知的误差函数为：
6 结语
传感器部署是传感器网络中的一个基本问题，本文研究在3D表面区域部署传感器节点的优化方法。3D表面与平面映射存在距离失真，因此传统的平面部署方法无法直接应用到传感器节点3D表面部署中。本文研究了3D表面到平面的保形映射方法，提出一种基于距离的误差函数来刻画衡量传感器节点部署的性能，证明通过质心V剖分可使得传感器网络部署的感知性能达到最优；提出一种优化部署算法首先将3D表面映射通过保形映射到平面，得出最优部署后反映射到3D立体表面。最后通过仿真分析证明了本文提出的算法的有效性。本文算法能够适应复杂的立体表面的部署情形，通过部署其感知误差值最小。下一步工作考虑降低算法的复杂性，研究更为简洁的3D表面的平面映射方法。
图片
图4 不同感知误差函数的感知效率
参考文献：
[1] BARTOLINI N， CALAMONERI T， la PORTA T F， et al. Autonomous deployment of heterogeneous mobile sensors[J]. IEEE Transactions on Mobile Computing， 2011，10（6）：753-766.
[2] SAIPULLA A， WESTPHAL C， LIU B， et al. Barrier coverage of linebased deployed wireless sensor networks[C]// Proceedings of the 28th IEEE Conference on Computer Communications. Piscataway： IEEE， 2009：127-135.
[3] 刘惠， 柴志杰， 杜军朝， 等. 基于组合虚拟力的传感器网络三维空间重部署算法研究[J]. 自动化学报， 2011， 37（6）： 713-723.
[4] BEJERANO Y. Simple and efficient kcoverage verification without location information[C]// Proceedings of the 27th IEEE Conference on Computer Communications. Piscataway： IEEE， 2008：291-295.
[5] BAI X， XUAN D， YUN Z， et al. Complete optimal deployment patterns for fullcoverage and kconnectivity wireless sensor networks[C]// Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York： ACM，2008：401-410.
[6] ZHANG C， BAI X， TENG J， et al. Constructing lowconnectivity and fullcoverage three dimensional sensor networks[J]. IEEE Journal on Selected Areas in Communications， 2010，28（7）：984-993.
[7] 黄晓，程宏兵，杨庚.无线传感器网络覆盖连通性研究[J].通信学报，2009，33（2）：129-135.
[8] DOMINGO M C. Optimal placement of wireless nodes in underwater wireless sensor networks with shadow zones[C]// Proceedings of the 2nd IFIP Conference on Wireless Days. Piscataway： IEEE，2009：1-6.
[9] POMPILI D， MELODIA T， AKYILDIZ I F. Threedimensional and twodimensional deployment analysis for underwater acoustic sensor networks[J]. Ad Hoc Networks， 2009， 7（4）： 778-790.
[10] 夏娜，王长生，郑榕，等.鱼群启发的水下传感器节点布置[J].自动化学报，2012，38（2）：295-302.
[11] 黄艳，梁韦华，于海斌.一种高效覆盖的水下传感器网络部署策略[J].电子与信息学报，2009，31（5）： 1035-1039.
[12] SCHWAGER M， MCLURKIN J， RUS D. Distributed coverage control with sensory feedback for networked robots[C]// Proceedings of Robotics： Science and Systems. Philadelphia，PA：[s.n]， 2006：1-8.
[13] ZHAO M C， LEI J， WU M Y， et al. Surface coverage in wireless sensor networks[C]// IEEE INFOCOM 2009. Piscataway： IEEE，2009： 109-117.