机场噪声监测无线传感网络最小连通覆盖集研究.pdfVIP

总第295期 计算机与数字工程 Vo1．42No．5 2014年第5期 Computer＆DigitalEngineering 747 机场噪声监测无线传感网络最小连通覆盖集研究 李 国 蒿培培 (中国民航大学计算机科学与技术学院 天津 300300) 摘 要 针对机场噪声监测无线传感网络中的最小连通覆盖集问题，设计了一种基于目标区域Voronoi划分的集中式 近似算法，用于分析完全覆盖 目标区域所需的最低要求的节点集；为了更好地调整噪声监测节点的感知半径R与通信半径 R 的比值关系，在通信半径小于两倍感知半径时，提出了一种基于最小生成树的连通算法用以确保 CVT算法构造的覆盖 集连通所需的辅助节点。理论分析与仿真实验表明，与现有常用的集中式贪婪算法和DVC算法相 比，CVT(+MST)算法 的性能在时间复杂性和连通覆盖集大小等两方面都较优。 关键词 噪声监测 ；无线传感网络；最小连通覆盖；Voronoi划分；最小生成树 中图分类号 TP393 DOI：10．3969／j．issnl672—9722．2014．05．002 MinimalConnectedCoverSetofW SNsinAirportNoiseM onitoring LIGuo HAO Peipei (SchoolofComputerScienceandTechnology，CivilAviationUniversityofChina，Tianjin 300300) Abstract Targetatminimalconnectedcoversetproblem ofwirelesssensornetworksinairportnoisemonitoring，a centralizedVoronoitessellationbasedapproximatealgorithm isproposedtoconstructanearoptimalcoversetofactivesen— sorsrequiredtOcoverthetargetregioncompletely．InordertObetteradjusttherelationshipbetweensensingradiusandcorn— municationradiustOnoisemonitoringnode，aminimum spanningtreebasedconnectionalgorithm isproposedtOensurethe communicationconnectivityofthecoverset．Co mparedwithexistingalgorithms，theperformanceofCVT (+ MST)algo— rithm isbetterintermsoftheruntimeandthesizeoftheconstructedconnectedcoversetthroughtheoreticalanalysisaswell asextensivenumericalexperiments． KeyWords noisemonitoring，wirelesssensornetwork，minima1connectedcoverset，voronoitessellation，minimum spanningtree ClassNumtmr TP393 如DVC算法[、重构 Voronoi划分[、支配集[。] 1 引言 等，这些方法固然取得 了一定的成果，但 由于算法 降低功耗可以延长网络生存时间，能更持久地 本身过于庞杂，实现难度大，况且现有算法难 以有 进行全天候机场噪声监测。噪声监测节点被高密 效维持网络原有覆盖范围，并在覆盖机场时会导致 度部署在机场中，仅将最少量的节点处于工作状态