数学建模遥测遥感网

1遥测遥感网摘要本文对覆盖矩形及多边形区域所需的最少监视装置问题和支配集和连通支配集的搜寻问题做了模型研究。如何寻找覆盖指定监视区域所需的最少监视装置数以及最少工作装置数，对于节省人力物力资源是至关重要的。对于问题一（1），我们在充分理解了蜂窝网格的特性后，遵照蜂窝网格的排布规律和原则，对监视装置从正方形区域的横、纵侧的进行部署，直至实现区域覆盖。此时所需装置数量最少，共有45个。对于问题一（2），我们根据题意设定了MATLAB中的循环条件（成功覆盖的概率达到设定值95%），依照“随机均匀放置-标记、画圆-判断-终止或继续循环”的流程，模拟了监视装置随机均匀放置的过程。由计算机模拟结果可知，需要随机放置400个装置，可以使得成功覆盖整个区域的概率在95%以上。对于问题一（3），我们改进了问题一（1）的蜂窝网格模型，将该模型推广到一般矩形的监视区域，并得到了实现区域覆盖所需最少装置数的公式。而后，我们改进了问题一（2）中的随机均匀模拟算法，加入边界判断，对凸多边形区域作了覆盖处理。又由凸包算法可知，简单凹多边形可分解为多个凸多边形的差组合，凹多边形区域的覆盖问题也得到解决。对于问题二（1），我们采用了逆序启发式算法。在构造初始邻接矩阵，得到现实的邻接矩阵和各点的度数后，开始搜寻度数最大的点，直至再无支配点出现。计算得到较好的一个支配集由44个支配装置组成，其具体位置坐标已在后文中给出。同时，我们用SPSS软件对算法结果进行了验证。其结果与启发式算法得到的结果大致相同，从而印证了逆序启发式算法的准确性。对于问题二（2），我们沿用了问题二（1）模型的算法，计算得到一个较好的支配集由63个支配装置组成。对于问题二（3），我们建立了两种模型对题目进行了求解。在第一个模型中，我们先在区域中找出一个较小的独立支配集,然后再通过增加一些节点将这个独立集连通起来，得到问题二（1）中的连通支配集元素个数为59个。在第二个模型中，我们采用了基于最小生成树的CDS（连通支配集）启发算法，得到问题二（1）中的连通支配集元素个数为58个。通过比较，第二个模型更见优越。因此我们使用了第二个模型对问题一（2）的情形进行求解，得到连通支配集元素个数为106个。最后，我们对文中模型的优缺点进行了评价，并针对蜂窝网格模型和随机模拟算法，提出了网格移动的改进算法。对多边形区域的覆盖问题，给出了一种简单方法（割补法）的思想。且对模型进行了简单的推广。关键词：区域覆盖；蜂窝网格；随机模拟；支配集；连通支配集；最小生成树2一．问题重述1.1问题背景大气污染所引起的地球气候异常，导致大面积严重森林大火的频频发生，给人民的生命财产造成巨大损失。因此，不少国家政府都在研究有效的森林防火措施，在容易出现高森林火险的重点地区放置高科技的监视装置，建立遥测遥感网，以便及时地掌握险情的发展情况，为有效地防止火灾发生或在酿成严重灾害之前将其扑灭创造条件。科技的迅速发展使人们可以制造不太昂贵且具有收发报通讯功能的监视装置。放置在同一监视区域内的这种监视装置（以下简称为装置）构成一个AdHoc无线网络，即通常所说的遥测遥感网。研究能确保有效（即按一定概率）覆盖且数量最少的装置系统的随机放置问题显然具有重要意义。1.2问题重述本文涉及的相关概念：1.覆盖：监视区域的每一点都处于放置在该区域内某个装置的监视范围内，则称这些装置能覆盖该监视区域。2.通讯半径：两主机可直接通信的最长距离（某装置的通信范围指以该装置为圆心，通信半径为半径确定的圆域）。3.支配集：遥测遥感网的若干装置组成的整体具有与遥测遥感网的每个装置都能联系的功能，从而保证当任何休眠装置定时“苏醒”后若发现“险情”，都能及时向值班者之一传递险情信息。这些装置的集合称为遥测遥感网的一个支配集。4.连通支配集：通过仅在支配集内部传递信息的手段可以让它的每个装置共享任一装置所得到的信息，这样的支配集自然称为连通支配集。根据以上所给信息，解答下列问题：问题一：(1)现有边长b=100(长度单位)的正方形监视区域，每个装置的监视半径均为r=10(长度单位)。参考蜂窝网格的特性讨论覆盖该区域所需装置的最少数量。(2)在设计遥测遥感网时，首先需要知道对给定监视区域在一定的覆盖保证下应放置装置的最佳（越少越佳）数量，并且常假设装置在监视区域内是均匀地随机放置的。在上述假设下建立数学模型，利用随机模拟实验回答：对于该题（1）中给定的监视区域及监视半径，至少需要随机放置多少个装置，才能使得成功覆盖整个区域的概率在95%以上。并给出一个均匀随机放置装置的分布图。(3)对一般矩形以及多边形的监视区域进一步探讨以上问题。问题二：(1)现有一监视区域为边长b=100（长度单位）的正方形，每个装置的通讯半径均为R=10（长度单位）。已知在该监视区域内放置了120个装置，这些装置的坐标已知。建立数学模型找出一个较好的支配集；画出该120个装置的分配图，并在此图上标出所找到的支配集。(2)在问题一（2）中给出的装置分配图中找出一个较好的支配集；在原装置分配图上标出该支配集。(3)建立寻找连通支配集的数学模型，并对问题二（1）中给定的含120个装置的遥测遥感网和问题一（2）中给出的装置分配图分别求出元素个数较少的连通支配集，且在原装置分配图上标出该连通支配集。3二．问题分析问题一（1）要求参考蜂窝网格的特性讨论覆盖该区域所需装置的最少数量。我们首先明确了蜂窝网格特性，即当装置的监视圆域与其邻近装置的监视圆域构成正六边形时,装置的有效覆盖面积达到最大。我们遵照这一原则，对装置从正方形区域的横纵侧的进行部署，直至实现区域覆盖，此时所需装置数量最少。问题一（2）要求用随机模拟试验，对问题一（1）中给定的监视区域及监视半径，求所需随机放置的装置的最少个数，使其成功覆盖整个区域的概率在95%以上。显然，随机放置的装置个数不断增加，成功覆盖整个区域的概率不断上升。我们只需根据题意设定循环条件（成功覆盖区域的概率条件），在MATLAB程序中使用条件循环即可解决该类问题。问题一（3）要求对一般矩形以及多边形的监视区域进一步探讨以上问题。对于一般矩形，我们仍可应用问题一（1）的模型，利用蜂窝网格特性部署装置。之后，我们还需对得到的装置位置进行微调。而对于多边形区域，由于边界的不对称、不规则，难以用蜂窝网格模型求解。所以我们考虑采用区域内随机模拟的方式探讨该问题。问题二（1）要求建立数学模型找出并标记一个较好的支配集并画出分配图。支配集的寻找可使用逆序启发式算法模型，依照度数的逆序逐步寻找遥测遥感网的支配点，这些点构成的便是它的支配集。此外，我们可用SPSS软件作了分层聚类分析，验证算法的准确性。问题二（2）要求在问题一（2）中给出的装置分配图中，找出一个较好的支配集；并在原装置分配图上标出该支配集。这一问是问题二（1）建立的算法模型在不同情形的应用，仍采用上述算法，MATLAB编程实现。问题二（3）要求建立寻找连通支配集的数学模型，并应用于问题二（1）和问题一（2）中的两种情形。我们可先在图中找出一个较小的独立支配集,然后再通过增加一些节点将这个独立集连通起来。这便构成了连通支配集。此外，基于最小生成树的CDS（连通支配集）启发算法也是寻找连通支配集的有效方法。我们可比较两者优缺，择优选用。三．模型假设1、假设监测区域为二维平面，监测区域中所有装置不可移动、同构、且处于同一平面；2、假设问题一（2）中装置在监视区域内是均匀地随机放置的；3、不考虑监测装置的损坏以及电池用尽；4、不考虑周围地形和气候因素对装置功率、监测和通信范围的影响。四．符号说明r：装置的监视半径；：监视区域的覆盖率；kA：第k个装置的覆盖面积；n：装置的数目；4sA：整个监测区域的面积；t：成功覆盖给定区域这一事件出现的次数；j：总的试验次数；p：成功覆盖给定区域的概率；N：覆盖此区域所需的最少装置数；iD：第i个点在图G中的相邻节点的个数（1,2,3120i）；五．模型的建立及求解5.1问题一的求解5.1.1问题一（1）的求解蜂窝网格特性：通过几何证明（见附录一）可以得出，三个半径相同的圆两两相交,以圆心为顶点的三角形是正三角形且正三角形边长是圆半径的3倍时，圆域的面积最大，相交部分最小，如图1所示。这是三个圆两两相交面积最大的极限情况,也就是说，在这种情况下，三个圆构成的无缝拓扑面积为最大。为了控制覆盖成本，则图中阴影部分面积取最小值。根据上面推理,阴影部分面积最小，则装置监视域的交线构成正六边形，即蜂窝网格。图1:半径相同的三个圆两两相交于一点基于蜂窝网格的装置部署：对题中给定的正方形目标区域ABCD，装置的部署可按以下步骤实现：首先，以A为坐标原点，AB所在直线为x轴，AD所在直线为y轴，建立直角坐标系。在横坐标上从A至B绘制边长为r的蜂窝网格，然后，在纵坐标上从A至D绘制边长为r的蜂窝网格，直至到达边界，最后得到图3所示蜂窝网格。其中，监视半径为r。5图3:利用CAD得到的正方形区域“蜂窝网格”部署其中，图中黑点代表监视装置部署点，这些装置实现了对目标区域的全覆盖。此时覆盖此区域所需的装置数目最少，需45个。5.1.2问题一（2）的求解题中假设装置在监视区域内是均匀地随机放置的，并要求在上述假设下，利用随机模拟实验得到至少需要随机放置多少个装置，才能使得成功覆盖给定区域的概率在95%以上。覆盖率：衡量监视装置部署好坏的一个重要指标是覆盖率。覆盖率一般定义为所有装置覆盖的总面积与监测区域总面积的比值,其中装置覆盖的总面积取集合概念中的并集。1nkksAA（1）其中代表覆盖率，kA表示第k个装置的覆盖面积，n代表节点的数目，sA表示整个监测区域的面积。成功覆盖给定区域的概率：在相同的条件下做大量的重复试验，成功覆盖给定区域这一事件出现的次数t和总的试验次数j之比，称为这个事件在这j次试验中出现的频率。当试验次数j很大时，频率将‘稳定’在一个常数附近。t越大，频率偏离这个常数大的可能性越小。通过多次随机试验，我们可用频率替代概率。我们在上述问题一（1）的条件、问题一（2）的假设下建立数学模型，利用随机模拟实验对问题一（1）中给定的监视区域及监视半径，确定了能成功覆盖整个区域的概率在95%以上的所需均匀随机放置装置的最少个数。算法的具体步骤如下：Step1：在给定的监视区域内随机选取装置放置点；Step2：标记该点，以该点为圆心，以监视半径为半径作圆，求出此时的覆盖率以及覆盖整个区域的概率p；Step3：判断求得的覆盖率及覆盖整个区域的概率p。若1且0.95p，则停止计算，得到满足条件的装置个数；否则，返回step1。6上述步骤可用流程图直观表示：图3：覆盖正方形区域模拟随机流程图由以上算法编程求解，最终放置的装置的数量为400。随即选取400个监视装置，且可成功覆盖整个区域的概率96%p，满足题目要求。模拟过程得到了覆盖该正方形区域装置随机放置图和覆盖率随着监测装置数量n的变化图：00.5100.10.20.30.40.50.60.70.80.910204060801000102030405060708090100scale=23.22%,N=900.5100.10.20.30.40.50.60.70.80.910204060801000102030405060708090100scale=63.95%,N=31（ⅰ）（ⅱ）在给定区域随机选取装置放置点，记录放置点个数停止计算，得到结果标记，画圆，求覆盖率及覆盖整个区域的概率p1且0.95pYN700.5100.10.20.30.40.50.60.70.80.910204060801000102030405060708090100scale=76.82%,N=5500.5100.10.20.30.40.50.60.70.80.910204060801000102030405060708090100scale=89.53%,N=79（ⅲ）（ⅳ）以上四图是显示了在不同的覆盖率下，监视装置的数目。显然，监视装置数目