本发明涉及一种自动气象站覆盖优化方法，包括以下步骤：步骤1、建模：将N个自动气象站随机部署在一个大小为L*W的二维矩形平面T内；步骤2、构建每个自动气象站的Voronoi图，得到每个自动气象站的Voronoi区域；步骤3、根据每个自动气象站的Voronoi区域，对每个自动气象站当前的位置进行更新，直至得到每个自动气象站最终的位置。本发明的优点在于：通过自动气象站覆盖优化问题转换为每个自动气象站各自覆盖对应Voronoi多边形区域的优化问题，降低问题的复杂性与计算复杂度，不仅使得自动气象站的节点部署和区域划分更加合理，同时使得自动气象站覆盖范围更佳。
1.一种自动气象站覆盖优化方法，其特征在于：包括以下步骤：步骤1、建模：将N个自动气象站随机部署在一个大小为L*W的二维矩形平面T内，并对N个自动气象站进行标记，分别记为：s1，s2，...si，...sN；
其中，s1为第1个自动气象站的标号，s1在T中的位置为c1；s2为第2个自动气象站的标号，s2在T中的位置为c2；si为第i个自动气象站的标号，si在T中的位置为ci；i＝1、2、…N；sN为第N个自动气象站的标号，sN在T中的位置为cN；
步骤2、构建每个自动气象站的Voronoi图，得到每个自动气象站的Voronoi区域；
步骤3、根据每个自动气象站的Voronoi区域，对每个自动气象站当前的位置进行更新，直至得到每个自动气象站最终的位置；
步骤3‑1、构建步骤2中每个自动气象站的Voronoi区域所对应的外接圆，并提取出每个外接圆的圆心 之后，将每个自动气象站的Voronoi区域所对应的外接圆的圆心更新为每个自动气象站当前的位置；
其中， 为第1个自动气象站s1的Voronoi区域所对应的外接圆圆心； 为第2个自动气象站s2的Voronoi区域所对应的外接圆圆心； 为第N个自动气象站sN的Voronoi区域所对应的外接圆圆心；
步骤3‑2、判断 如是，则转入步骤3‑3；如否，则转入到步骤3‑6；
步骤3‑3、按照步骤2和步骤3‑1中相同的方式，以每个自动气象站当前的位置构建每个自动气象站的Voronoi图，并构建每个自动气象站的Voronoi区域所对应的外接圆以及提取出每个外接圆的圆心 之后将每个自动气象站对应的外接圆的圆心更新为每个自动气象站当前的位置；a的初始值为2；
步骤3‑5、将a加1后更新a值，并转入到步骤3‑3；
步骤3‑6、将每个自动气象站当前的位置作为最终的位置；
步骤3‑a、计算出每个自动气象站的Voronoi区域所对应的质心 并将每个自动气象站的Voronoi区域所对应的质心更新为每个自动气象站当前的位置；
其中， 为第1个自动气象站s1的Voronoi区域所对应的质心； 为第2个自动气象站s2的Voronoi区域所对应的质心； 为第N个自动气象站sN的Voronoi区域所对应的质心；
步骤3‑b、判断 如是，则转入步骤3‑c；如否，则转入到步骤3‑f；
步骤3‑c、按照步骤2和步骤3‑a中相同的方式，以每个自动气象站当前的位置构建每个自动气象站的Voronoi图，并提取每个自动气象站的Voronoi区域所对应的质心之后将每个自动气象站Voronoi区域所对应的质心更新为每个自动气象站当前的位置；a的初始值为2；
步骤3‑d、判断 如是，则转入步骤3‑e；如否，则转入到步骤3‑f；
步骤3‑e、将a加1后更新a值，并转入到步骤3‑c；
步骤3‑f、将每个自动气象站当前的位置作为最终的位置。
2.根据权利要求1所述的自动气象站覆盖优化方法，其特征在于：所述步骤2第i个自动气象站si的Voronoi区域Vi的计算公式为：其中，i＝1，2，...N；x为二维矩形平面T内的一点，d(x，si)为计算x与si之间的欧氏距离；d(x，sj)为计算x与sj之间的欧式距离。
3.根据权利要求2所述的自动气象站覆盖优化方法，其特征在于：所述步骤1和步骤2之间还包括以下步骤：
根据地形特征对二维矩形平面T建立地形模型，并对各种不同地形特征赋予权重；
相应的，每个自动气象站的Voronoi区域Vi的计算公式为：其中，i＝1，2，...N；x为二维矩形平面T内的一点，d(x，si)为计算x与si之间的欧氏距离，wi为si的权重；d(x，sj)为计算x与sj之间的欧式距离，wj为sj的权重。
4.根据权利要求1所述的自动气象站覆盖优化方法，其特征在于：所述步骤3‑1中构建每个自动气象站的Voronoi区域所对应的外接圆的方法为：步骤a、对某个自动气象站的Voronoi区域建立最远点Voronoi图，使该自动气象站的Voronoi区域内的所有点都被包围在最远点Voronoi图内；
其中，建立最远点Voronoi图的公式为：||·||为范数计算函数，Vi为第i个自动气象站si的Voronoi区域，p和q分别为第i个自动气象站si的Voronoi区域Vi中任意两个互不相同的点；
步骤b、将最远点Voronoi图上的每一个顶点作为圆心候选点，求取最小的覆盖圆半径R1；
步骤c、对于最远点Voronoi图中的每一条边，求解每一条边与对偶边的交点，并将交点作为圆心候选点，求取最小的覆盖圆半径R2；
步骤d、将R1与R2中的最小值作为自动气象站的Voronoi区域所对应的外接圆半径。
一种自动气象站覆盖优化方法
技术领域
[0001] 本发明涉及优化方法，特别涉及一种自动气象站覆盖优化方法。
背景技术
[0002] 随着经济社会的高速发展，气象监测技术为多个行业的安全运行提供保障，在防灾减灾、交通调度、农业生产等方面发挥着极其重要的作用。其中，地面气象观测是气象监
测技术的重要基础，它主要是对近地层范围内的气象要素进行观察和测定，最常见的就是
在一个选定的观测场建立自动气象站从而对周围环境的气象要素进行采集和处理。一个有
科学依据的自动气象站网体系，可保证地面气象观测资料具有准确性和代表性。一般情况
下，这些自动气象站的选址是根据经验或者按照区域随机部署的，通过该方式部署的自动
气象站难以保证良好的自动气象站覆盖率和气象信息监测的准确性。而自动气象站获取收
集的地面气象观测资料往往代表了某一区域内的气象要素平均值，不合理的选址布局会对
气象信息监测产生较严重的影响，如地面气象观测资料误差较大、天气预报分析不精准等，
也在一定程度上增加整个自动气象站建设的成本。因此，自动气象站的选址布局和覆盖优
化是气象监测技术中的重要环节。
[0003] 针对自动气象站布局优化和区域覆盖问题，很多专家学者对其进行了深入研究并且取得了许多研究成果。近年来，基于计算几何学中的Voronoi图来提高区域覆盖效率受到
广泛的关注和应用。
[0004] 在区域覆盖控制规划中，以Voronoi图为基础主要有两种方法，一种是研究节点的冗余识别和冗余调度策略，通过识别节点是否为冗余节点来判断哪些满足覆盖冗余的节点
进入休眠状态来降低节点冗余率。另一种是研究区域覆盖中的覆盖空洞或者覆盖率来提出
修复策略。可将其分为三类：静态区域覆盖，移动区域覆盖和混合区域覆盖。静态区域覆盖
中，主要通过增加新的节点来实现。静态的覆盖空洞修复方法虽然能够提升区域覆盖率并
且减少冗余节点的部署，但是该策略普遍存在大面积的感知重叠现象并且具有较大局限
性。移动区域覆盖和混合区域覆盖中，通常使现有的节点移动来覆盖空洞。这种动态区域覆
盖考虑的是节点位置没有固定的情况下，通过调整自身位置动态完成相关覆盖任务，适用
于一些具有运动能力的节点。虽然以上方法和策略的覆盖提升能力较强，但是实验结果中
并未出现较高的覆盖率。
发明内容
[0005] 本发明所要解决的技术问题是针对现有技术的现状，提供一种计算简单且覆盖率高的自动气象站覆盖优化方法。
[0006] 本发明解决上述技术问题所采用的技术方案为：一种自动气象站覆盖优化方法，其特征在于：包括以下步骤：
[0007] 步骤1、建模：将N个自动气象站随机部署在一个大小为L*W的二维矩形平面T内，并对N个自动气象站进行标记，分别记为：s1，s2，...si，...sN；
[0008] 其中，s1为第1个自动气象站的标号，s1在T中的位置为c1；s2为第2个自动气象站的标号，s2在T中的位置为c2；si为第i个自动气象站的标号，si在T中的位置为ci；i＝1、2、...N；
sN为第N个自动气象站的标号，sN在T中的位置为cN；
[0009] 步骤2、构建每个自动气象站的Voronoi图，得到每个自动气象站的Voronoi区域；
[0010] 步骤3、根据每个自动气象站的Voronoi区域，对每个自动气象站当前的位置进行更新，直至得到每个自动气象站最终的位置。
[0011] 具体的，所述步骤2第i个自动气象站si的Voronoi区域Vi的计算公式为：
[0012]
[0013] 其中，i＝1，2，...N；x为二维矩形平面T内的一点，d(x，si)为计算x与si之间的欧氏距离；d(x，sj)为计算x与sj之间的欧式距离。
[0014] 作为改进，所述步骤1和步骤2之间还包括以下步骤：
[0015] 根据地形特征对二维矩形平面T建立地形模型，并对各种不同地形特征赋予权重；
[0016] 相应的，每个自动气象站的Voronoi区域Vi的计算公式为：
[0017]
[0018] 其中，i＝1，2，...N；x为二维矩形平面T内的一点，d(x，si)为计算x与si之间的欧氏距离，wi为si的权重；d(x，sj)为计算x与sj之间的欧式距离，wj为sj的权重。
[0019] 上述步骤3中更新方法优选的第一种方案为：所述步骤3中的具体步骤为：
[0020] 步骤3‑1、构建步骤2中每个自动气象站的Voronoi区域所对应的外接圆，并提取出每个外接圆的圆心 之后，将每个自动气象站的Voronoi区域所对应的外接圆
的圆心更新为每个自动气象站当前的位置；
[0021] 其中， 为第1个自动气象站s1的Voronoi区域所对应的外接圆圆心； 为第2个自动气象站s2的Voronoi区域所对应的外接圆圆心； 为第N个自动气象站sN的Voronoi区域所
对应的外接圆圆心；
[0022] 步骤3‑2、判断 如是，则转入步骤3‑3；如否，则转入到步骤3‑6；
[0023] 其中，ε为预设的阈值；
[0024] 步骤3‑3、按照步骤2和步骤3‑1中相同的方式，以每个自动气象站当前的位置构建每个自动气象站的Voronoi图，并构建每个自动气象站的Voronoi区域所对应的外接圆以及
提取出每个外接圆的圆心 之后将每个自动气象站对应的外接圆的圆心更新
为每个自动气象站当前的位置；a的初始值为2；
[0025] 步骤3‑4、判断 如是，则转入步骤3‑5；如否，则转入到步骤3‑6；
[0026] 步骤3‑5、将a加1后更新a值，并转入到步骤3‑3；
[0027] 步骤3‑6、将每个自动气象站当前的位置作为最终的位置。
[0028] 具体的，所述步骤3‑1中构建每个自动气象站的Voronoi区域所对应的外接圆的方法为：
[0029] 步骤a、对某个自动气象站的Voronoi区域建立最远点Voronoi图，使该自动气象站的Voronoi区域内的所有点都被包围在最远点Voronoi图内；
[0030] 其中，建立最远点Voronoi图的公式为：
[0031]
[0032] ||·||为范数计算函数，Vi为第i个自动气象站si的Voronoi区域；
[0033] 步骤b、将最远点Voronoi图上的每一个顶点作为圆心候选点，求取最小的覆盖圆半径R1；
[0034] 步骤c、对于最远点Voronoi图中的每一条边，求解每一条边与对偶边的交点，并将交点作为圆心候选点，求取最小的覆盖圆半径R2；
[0035] 步骤d、将R1与R2中的最小值作为自动气象站的Voronoi区域所对应的外接圆半径。
[0036] 上述步骤3中更新方法优选的第二种方案为：所述步骤3中的具体步骤为：
[0037] 步骤3‑a、计算出每个自动气象站的Voronoi区域所对应的质心 并将每个自动气象站的Voronoi区域所对应的质心更新为每个自动气象站当前的位置；
[0038] 其中， 为第1个自动气象站s1的Voronoi区域所对应的质心； 为第2个自动气象站s2的Voronoi区域所对应的质心； 为第N个自动气象站sN的Voronoi区域所对应的质心；
[0039] 步骤3‑b、判断 如是，则转入步骤3‑c；如否，则转入到步骤3‑f；
[0040] 其中，ε为预设的阈值；
[0041] 步骤3‑c、按照步骤2和步骤3‑a中相同的方式，以每个自动气象站当前的位置构建每个自动气象站的Voronoi图，并提取每个自动气象站的Voronoi区域所对应的质心
之后将每个自动气象站Voronoi区域所对应的质心更新为每个自动气象站
当前的位置；a的初始值为2；
[0042] 步骤3‑d、判断 如是，则转入步骤3‑e；如否，则转入到步骤3‑f；
[0043] 其中，ε为预设的阈值；
[0044] 步骤3‑e、将a加1后更新a值，并转入到步骤3‑c；
[0045] 步骤3‑f、将每个自动气象站当前的位置作为最终的位置。
[0046] 与现有技术相比，本发明的优点在于：通过自动气象站覆盖优化问题转换为每个自动气象站各自覆盖对应Voronoi多边形区域的优化问题，降低问题的复杂性与计算复杂
度，不仅使得自动气象站的节点部署和区域划分更加合理，同时使得自动气象站覆盖范围
更佳，并通过计算Voronoi图的外接圆或质心，以更新每个自动气象站的位置，通过迭代计
算能够有效提高自动气象站的覆盖率，减少自动气象站覆盖盲区，从而使自动气象站布局
更好的优化，降低整个自动气象站的成本，并且一定程度上提高了气象信息监测能力。
附图说明
[0047] 图1为本发明实施例一中4个自动气象站的优化结果图；
[0048] 图2为本发明实施例一中9个自动气象站的优化结果图。
具体实施方式
[0049] 以下结合附图实施例对本发明作进一步详细描述。
[0050] 实施例一：
[0051] 本实施例中的自动气象站覆盖优化方法包括以下步骤：
[0052] 步骤1、建模：将N个自动气象站随机部署在一个大小为L*W的二维矩形平面T内，并对N个自动气象站进行标记，分别记为：s1，s2，...si，...sN；
[0053] 其中，s1为第1个自动气象站的标号，s1在T中的位置为c1；s2为第2个自动气象站的标号，s2在T中的位置为c2；si为第i个自动气象站的标号，si在T中的位置为ci；i＝1、2、...N；
sN为第N个自动气象站的标号，sN在T中的位置为cN；
[0054] 步骤2、构建每个自动气象站的Voronoi图，得到每个自动气象站的Voronoi区域；
[0055] 其中，步骤2中每个自动气象站的Voronoi图计算方法有两种：
[0056] (一)、第i个自动气象站si的Voronoi区域Vi的计算公式为：
[0057]
[0058] 其中，i＝1，2，...N；x为二维矩形平面T内的一点，d(x，si)为计算x与si之间的欧氏距离；d(x，sj)为计算x与sj之间的欧式距离。
[0059] (二)、步骤1和步骤2之间还包括以下步骤：
[0060] 根据地形特征对二维矩形平面T建立地形模型，并对各种不同地形特征赋予权重；
[0061] 相应的，每个自动气象站的Voronoi区域Vi的计算公式为：
[0062]
[0063] 其中，i＝1，2，...N；x为二维矩形平面T内的一点，d(x，si)为计算x与si之间的欧氏距离，wi为si的权重；d(x，sj)为计算x与sj之间的欧式距离，wj为sj的权重；
[0064] 第二种方法为加权Voronoi图的计算方法，结合地形对自动气象站选址的影响，使自动气象站的选址更加准确，更加实用，当然，也可以加权其他会影响自动气象站进行数据
采集的因素；
[0065] 步骤3、根据每个自动气象站的Voronoi区域，对每个自动气象站当前的位置进行更新，直至得到每个自动气象站最终的位置；
[0066] 本实施例中，更新的具体步骤为：
[0067] 步骤3‑1、构建步骤2中每个自动气象站的Voronoi区域所对应的外接圆，并提取出每个外接圆的圆心 之后，将每个自动气象站的Voronoi区域所对应的外接圆
的圆心更新为每个自动气象站当前的位置；
[0068] 其中， 为第1个自动气象站s1的Voronoi区域所对应的外接圆圆心； 为第2个自动气象站s2的Voronoi区域所对应的外接圆圆心； 为第N个自动气象站sN的Voronoi区域所
对应的外接圆圆心；
[0069] 其中，构建每个自动气象站的Voronoi区域所对应的外接圆的方法为：
[0070] 步骤a、对某个自动气象站的Voronoi区域建立最远点Voronoi图，使该自动气象站的Voronoi区域内的所有点都被包围在最远点Voronoi图内；
[0071] 其中，建立最远点Voronoi图的公式为：
[0072]
[0073] ||·||为范数计算函数，Vi为第i个自动气象站si的Voronoi区域；
[0074] 步骤b、将最远点Voronoi图上的每一个顶点作为圆心候选点，求取最小的覆盖圆半径R1；
[0075] 步骤c、对于最远点Voronoi图中的每一条边，求解每一条边与对偶边的交点，并将交点作为圆心候选点，求取最小的覆盖圆半径R2；
[0076] 步骤d、将R1与R2中的最小值作为自动气象站的Voronoi区域所对应的外接圆半径；
[0077] 步骤3‑2、判断 如是，则转入步骤3‑3；如否，则转入到步骤3‑6；
[0078] 其中，ε为预设的阈值；
[0079] 步骤3‑3、按照步骤2和步骤3‑1中相同的方式，以每个自动气象站当前的位置构建每个自动气象站的Voronoi图，并构建每个自动气象站的Voronoi区域所对应的外接圆以及
提取出每个外接圆的圆心 之后将每个自动气象站对应的外接圆的圆心更新
为每个自动气象站当前的位置；a的初始值为2；
[0080] 步骤3‑4、判断 如是，则转入步骤3‑5；如否，则转入到步骤3‑6；
[0081] 步骤3‑5、将a加1后更新a值，并转入到步骤3‑3；
[0082] 步骤3‑6、将每个自动气象站当前的位置作为最终的位置。
[0083] 为了说明本方法中的优化过程，如图1和图2所示，图1为对4个随机分布的自动气象站进行覆盖优化，图1(a)为4个随机分布的自动气象站分布图，图1(b)为迭代2次后的自
动气象站分布图，图1(c)为迭代10次后的自动气象站分布图，图1(d)为迭代结束后的自动
气象站分布图，可以从图1(d)看出经过本方法中的优化过程后，4个随机分布的自动气象站
变成了均匀分布的4个自动气象站，其能得到最好的采集效果。
[0084] 另外，图2为对9个随机分布的自动气象站进行覆盖优化，图2(a)为9个随机分布的自动气象站分布图，其中，自动气象站分布比较密集或比较分散，这种分布情况下自动气象
站的采集效果不佳，会出现重复采集或采集不充分的情况，图2(b)为迭代4次后的自动气象
站分布图，图2(c)为迭代13次后的自动气象站分布图，图2(d)为迭代结束后的自动气象站
分布图，可以从图2(b)～2(d)看出经过本方法中的优化过程后，随机分布的自动气象站逐
步变成了均匀分布的9个自动气象站，其能得到最好的采集效果，从而本方法能有很好的覆
盖优化结果。
[0085] 实施例二：
[0086] 与实施例一不同的是，本实施例中步骤3中的具体步骤为：
[0087] 步骤3‑a、计算出每个自动气象站的Voronoi区域所对应的质心 并将每个自动气象站的Voronoi区域所对应的质心更新为每个自动气象站当前的位置；
[0088] 上述每个自动气象站的Voronoi区域所对应的质心采用现有的算法计算；
[0089] 其中， 为第1个自动气象站s1的Voronoi区域所对应的质心； 为第2个自动气象站s2的Voronoi区域所对应的质心； 为第N个自动气象站sN的Voronoi区域所对应的质心；
[0090] 步骤3‑b、判断 如是，则转入步骤3‑c；如否，则转入到步骤3‑f；
[0091] 其中，ε为预设的阈值；
[0092] 步骤3‑c、按照步骤2和步骤3‑a中相同的方式，以每个自动气象站当前的位置构建每个自动气象站的Voronoi图，并提取每个自动气象站的Voronoi区域所对应的质心
之后将每个自动气象站Voronoi区域所对应的质心更新为每个自动气象站
当前的位置；a的初始值为2；
[0093] 步骤3‑d、判断 如是，则转入步骤3‑e；如否，则转入到步骤3‑f；
[0094] 其中，ε为预设的阈值；
[0095] 步骤3‑e、将a加1后更新a值，并转入到步骤3‑c；
[0096] 步骤3‑f、将每个自动气象站当前的位置作为最终的位置。
[0097] 以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明技术原理的前提下，还可以做出若干改进和润饰，这些改进和润饰
也应视为本发明的保护范围。
