如何有效监测灾难突发区域

1、浙江工业大学第十四届大学生数学建模竞赛所选赛题： A B C我们承诺：Ø 我们仔细阅读了浙江工业大学数学建模竞赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人研究、讨论与赛题有关的问题。Ø 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。Ø 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。参赛队员（签名）：张加满 学院年级：信息分院

2、通信1103联系方式：541231参赛队员（签名）：宣 波 学院年级：信息分院软件1101联系方式：542082 参赛队员（签名）：徐晗景 学院年级：信息分院软件1102联系方式：542115 我们队伍愿意参加暑期数学建模培训，参加全国大学生数学建模竞赛如何有效监测灾难突发区域摘 要 本论文针对自然灾难突然发生时，为实时观察和监测灾难区域的状态，需要部署相当数量的智能装置构成全区域覆盖的监视系统问题，文章共建立了三个模型用以解决该类问题。 对于问题（1）：我们主要利用一个特定的矩形区域（10R*10R）展开的，对该正方形区域进行分析得知：要对矩形区域用圆进行覆盖即先需要对圆用多边形进行覆盖，由

3、最小覆盖圆模型知，当且仅当用正多边形来限制圆的半径得到的圆可以使得覆盖整个图形时所用圆的个数最少。步骤1）.一定半径（范围要求）的圆的内接正多边形可以完全覆盖该矩形区域，求若干个该正多边的外接圆能使得完全覆盖整个矩形区域所用圆的个数最少；步骤2)，满足限制条件的正多边形有正三角形，正四边形，正六边形，求相邻两个圆相交的公共面积不小于一个圆面积的K%。在步骤1）适当的假设条件下，对假设的合理性进行说明和验证，得到了题目所求的最优值。用到了几何知识、覆盖原理、微积分等一些数学知识探究了矩形覆盖的问题，通过计算机模拟分析了不同正多边形相交率变化趋势，最后运用mat lab作出符合一般性的程序并得出相

4、关图形。 对于问题（2）， 该问题可以归结为多元目标线性规划的问题，目标一是全区域覆盖传感器节点数最少；目标二是在智能装置系统判断节点受到损毁后，飞机（以一架飞机为例）如何在高空中飞行使得代价（时间、能量消耗）最小。我们在第一题的基础上，选择0-1判断节点损毁情况，又假设了一些距离变量，判断用哈密顿回路，启发式算法等思想求最短路径。 对于问题(3)， 修复后的网络运行一段时间后，会有一些节点死亡而导致再次修复。综合考虑网络监测性能和修复成本，我们会采取问题(2)中所给的覆盖的方法进行数据优化。以及传感器节点会受到感知其位置附近的各种状态变化，如温度、震动、湿度等，其感知能力随节点与目标距离的增

5、加而衰减。我们会给予这些因素以不同的权重。 关键词：监测灾难区域，覆盖原理，数学建模，多目标规划，数据优化一.问题重述 自然灾难突然发生时，为实时观察和监测灾难区域的状态，需要部署相当数量的智能装置构成全区域覆盖的监视系统。这种装置内嵌了传感器，称为传感器节点，用于感知其位置附近的各种状态变化，如温度、震动、湿度等，其感知能力随节点与目标的距离增加而衰减。由于每个节点的感知能力和覆盖范围十分有限，需要部署大量的节点才能实现区域监视。这些节点通过无线通信相互联系和发送数据，以传感器网络的形式进行协同工作。传感器节点部署的一般途径是通过飞机或机器人进行布撒，当节点所能感知的面积与区域总面积的比率达

6、到一定数值时，我们认为该区域已经被有效监测。没有被任何节点覆盖到的区域，称为覆盖空洞；只要该区域被任何一个或多个节点覆盖即认为该区域被有效覆盖；当节点受到外部干扰或破坏而损毁时，节点的死亡或失效也有可能形成覆盖空洞。这些空洞的总面积不能过大，否则将无法实现区域的有效监测。根据以上原理，针对10R*10R（R为传感器节点的有效感知半径）的监测区域，试分析和解决如下问题：(1)对于初始部署后存在的覆盖空洞，给出一种新节点部署方案，使得网络的覆盖率达到95%以上。(2)若节点随机死亡，并且当网络的覆盖率低于85%时必须进行修复，怎样部署新的节点使部署的代价（时间、能量消耗）最小？(3)修复后的网络运

7、行一段时间后，会有一些节点死亡而导致再次修复。综合考虑网络监测性能和修复成本，试给出一种优化的修复准则。二.问题分析2.1问题（1） 题目要求是对矩形区域用圆进行覆盖，使得完全覆盖整个矩形区域所用圆的个数最少的数学模型，该问题其实就是利用的覆盖原理建立的模型。一定半径（范围要求）的圆的内接正多边形可以完全覆盖该矩形区域，求若干个该正多边的外接圆能使得完全覆盖整个矩形区域所用圆的个数最少；步骤2)，满足限制条件的正多边形有正三角形，正四边形，正六边形，求相邻两个圆相交的公共面积不小于一个圆面积的K%。在LINGO软件中，通过设立一约束条件，最后将目标函数进行最优化求解。22问题（2） 该问题可以

8、归结为多元目标线性规划的问题，所以我们在目标一是全区域覆盖传感器节点数最少；目标二是在智能装置系统判断节点受到损毁后，飞机（以一架飞机为例）如何在高空中飞行使得代价（时间、能量消耗）最小的条件下求最短路径。23问题（3）该问题要求的是综合考虑修复后的网络运行一段时间后会有一些节点死亡而导致再次修复的网络监测性能和修复成本。以及传感器节点会受到感知其位置附近的各种状态变化，如温度、震动、湿度等，其感知能力随节点与目标的距离增加而衰减。我们会给予这些因素以不同的权重。三模型的假设与符号说明3模型的假设（1）10R*10R（R为传感器节点的有效感知半径）的监测区域进行覆盖。我们可以把问题简而言之为一

9、个特定的矩形区域（10R*10R）中,用半径为R的圆对其进行完全覆盖,(为了题目方便，我们暂时性把网络覆盖率设为100%，在实验最后除去5%的覆盖。设区域（10*10），半径为1)。（2）.区域中所有用于覆盖的圆是半径相等的圆。（3）在区域中所有的地形是相对平整的，不考虑地形的影响。（问题（1),问题（2）中的区域环境相对平稳，不考虑温度、震动、湿度等因素）。（4）在覆盖过程中不考虑圆周长，半径及圆心的宽度。（5）为研究方便只考虑正多边形覆盖，不考虑不规则多边形覆盖。32符号说明 符号符号说明正多边形的内角度数x正多边形的边数y覆盖一个圆周所需的正多边形的个数正多边形的边所对的圆心角K%相交园

10、的公共面积占一个圆面积的百分率Di第i个与第j个传感器之间的距离Xi第i个传感器的横坐标Ai第i个传感器的纵坐标四.模型的建立与求解41问题1的模型建立与求解4.1.1 解决问题1).圆的排列方式因为不可能穷举圆的任意形状的内接多边形来覆盖这个正方形区域，所以采用圆的内接正多边形覆盖方案，此即一个以正多边形为基本图形覆盖某一平面区域的问题。又有：定理1：若干半径为R的圆完全覆盖正方形区域的充分条件是这些圆的内接正多边形完全覆盖了正方形区域。证明：假设正n边形覆盖了正方形区域中的，所有（i1，2，M），覆盖的区域包含了正方形区域B，即所有覆盖的区域包含了正方形区域B。因为对于由形成的外接圆，必包

11、含区域，所以，所有（i1，2，M）覆盖的区域必包含了正方形区域B。定理2: 两圆相交面积不小于两个圆中较大的圆面积的k时，当两圆半径相等时，公共面积占两个圆总面积的百分比最小。证明：如图两圆，半径因为，所以 又因为 ，所以 （当且仅当即时取等）。考虑在一个无限大的平面内采用两种半径，的圆相交完全覆盖平面。定义圆的有效利用率: 则 （当且仅当S1=S2即时取等）。推论：两圆相交，满足相交面积不小于一个整圆面积的k的条件下，当两圆半径相等时，圆有效利用率最高。 由定理2及推论得知，应选取半径相同的圆。2).平面拼装的若干定义和定理 定义1 如果一组图形拼铺后完全覆盖平面，并且这组图形没有重叠，则这

12、组图形称为平面的拼装。 定义2 如果在平面的拼装中，只有一种基本元素图形，则称为平面的单元拼装；如果在单元拼装中基本元素图形为正多边形，则称为单元正规拼装；如果在单元拼装中基本元素图形为三角形，则称为单元三角拼装。 定理3 拼装中，其基本元素图形能且只能是正三角形、正方形和正六边形。现在我们来证明定理3证明：设在单元正规拼装中, 其基本元素图形为正边形, 正边形的每个内角值为, 显然 ，我们设，则 （1）解不定方程(1)可得: 。即: 在单元正规拼装中, 其基本元素图形只可能是正三角形、正四边形、正六边形，因此，要使单元正规拼接的均匀覆盖效率最大，则应选择正三角形、正方形或正六边形拼接正方形区

13、域。 定理4 在两等半径的圆相交的时候，若两交点夹的劣弧所对的圆心角固定，则相交面积与整个圆面积的比值与圆半径R无关，为常数。证明：如图1，两圆的圆心分别为，半径均为R，两交点为A，B。相交面积为 令 由知，k值与圆的半径R无关，定理4得证。将中的化为数量 所以随着增大，k的值是单调增加的并且增长速度满足正弦形式。两半径相等圆相交，以公共面积中心为坐标原点，圆心距。则两圆方程分别为: 公共面积: 令 4.1.2模型建立用半径为r =1的圆如何完全覆盖整个矩形区域（1010），使得相邻两圆相交的公共面积不小于一个圆面积的k。因此，我们用正多边形来覆盖则需讨论用什么类型的正多边形和什么方式覆盖1）

14、.正多边形的类型由多边形的内角和公式可得正多边形的一个内角 ，即 ，我们设，则 （1） y643x346 所以： 则满足完全覆盖条件的正多边形只有正三边形、正四边形、正六边形。 2）.正多边形的覆盖方式由于相邻两圆相交的公共面积不小于一个圆面积的k,现在设一个圆的内接正多边形的边所对的圆心角为，由面积之间的关系()则可得关于k的不等式： 当时 ，则k=39.09 当时 ，则k=18.15 当时 ，则k=5.77经过重复实验过后，我们得出了两种正多边形的最优覆盖方式： 用正四边形覆盖覆盖整个矩形区域只需半径为1的圆64个，其覆盖的图形如图1所示。 图1 图2 用正六边形覆盖覆盖整个矩形区域只需半

15、径为1的圆45个，其覆盖的图形如图2所示。第1题答案：网络覆盖率为100%时，覆盖整个矩形区域只需半径为1的圆45个。除去5%的覆盖率后，圆的个数为38。42问题2的模型建立与求解4.2.1解决问题1） 模型选择：在问题（1）中我们已经获得三种覆盖方法（正三角形，正四边形，正六边形）以及他们所对应的相邻两个圆相交的公共面积占一个圆面积的K%值，问题（2）考虑的因素不只是这个，还需要考虑例如：节点到节点之间的距离，数据处理方式，统计难易程度等。考虑因素1：相邻两个圆相交的公共面积占一个圆面积的K%值 当时 ，则k=39.09 当时 ，则k=18.15 当时 ，则k=5.77我们选择当 当时 ，则

16、k=5.77。考虑因素2：节点到节点之间的距离（因为考虑到数据处理方式，统计难易程度等等方面正三角形就不选择了）。 考虑到节点到节点之间的距离我们选择正四边形考虑因素3：数据处理方式以及统计难易程度正四边形的数据相对稳定，对后期数据处理比较方便。正六边形上面建立坐标轴比较困难（后期求最短路径是放在坐标轴上做的），而相对于正四边形建坐标轴比较容易。综上所述我们在考虑问题（2）的时候我们选择用正四边形的覆盖模型为基础。2）节点损毁检测：注：对于问题(2) “若节点随机死亡，并且当网络的覆盖率低于85%时必须进行修复，怎样部署新的节点使部署的代价（时间、能量消耗）最小”是在问题（1）“对于初始部署后

17、存在的覆盖空洞，给出一种新节点部署方案，使得网络的覆盖率达到95%以上”上面建立的。我们建立正四边形是以100%覆盖率为假设的，但在最我们把网络的覆盖率5%是除去的。考虑到这个遗留因素我们将两位0-1二进制表示。第一位0-1二进制表示模型除去的5%覆盖率。第二位表示节点是否随机死亡。“00”或者“01”不予处理；“11”表示节点正常，而“10”表示节点是在布点后受到外部干扰或破坏而损毁出现节点死亡或失效。符号（二进制）说明00或者01不予处理11节点正常10节点是在布点后受到外部干扰或破坏而损毁出现节点死亡或失效。这些节点通过无线通信相互联系和发送数据，以传感器网络的形式进行协同工作。我们选取

18、一个节点为原点建立一张坐标轴（以最左下角位置上的节点为原点）。系统对每个节点进行检测。当传感器节点变为“10”时，记录其出现的坐标Aij。3）修复机制：1.通过分析我们可以得到当i=0，i=7, j=0,或者j=7是我们需要单独考虑其损失面积 ; ;；顶点以及边界位子的特殊情况损失面积：i=0i=7j=0j=7i=0i=7j=0j=7顶点以及边界位子的特殊情况相邻节点A ij, A i+1j, A ij+1,A i-1j , Aij-1中任意两点同时死亡是则要考虑两节点相交的公共面积;当每个节点(除顶点以及边界位子)死亡后都会损失的面积，如果有相邻节点(除顶点以及边界位子)A ij, A i+

19、1j, A ij+1,A i-1j , Aij-1中任意两点同时死亡是则要考虑两节点相交的公共面积。当时，进行节点修复。按传感器失效的先后顺序，分别给他们标号a1,a2.an（原点a0(0,0)）。2.制定修复路径计算点与点之间的距离Di=制作成一个n阶矩阵1 从原点开始，i=0，k=1。2 从第i行中选出该行中的最小数Di。3 然后i=j(把j赋给i)，且把第i列的值全改为。4 ak=i，k=k+1。5 重复的步骤，直到矩阵中的数全为。则修复传感器的顺序为a1,a2, a3an，此时所部署的代价（时间、能量消耗）最小。43问题3的模型建立与求解该问题要求的是综合考虑修复后的网络运行一段时间后

20、会有一些节点死亡而导致再次修复的网络监测性能和修复成本。以及感器节点会受到感知其位置附近的各种状态变化，如温度、震动、湿度等，其感知能力随节点与目标的距离增加而衰减。我们会给予这些因素以不同的权重。 图4.1 图4.2如图4.1所示有ABCDEF六个点，（A为起始点）计算出A与他们之间的距离。根据距离所示我们可以得到如果在情况不是很危急时，去修复D点不是很经济。那我们就暂时性把D放置。飞机从A点开始飞向离它距离最小的B（图4.2）。然后A点在系统内消失。系统默认B变为起始点（图4.3 ）。 图4.3 图4.4以B为起始点后测得B点到其他平面内的点距离。从经济等各方面考虑D点还是暂时性放置。B点

21、上的飞机就飞往离它距离最小的C点（图4.4），然后B点在系统内消失。系统默认C变为起始点（图4.5 ）。 图4.5在B消失的同时，出现点GH两个点，C为起始点，测得C点到其他平面内的点距离。从经济等各方面考虑D点还是暂时性放置。C点上的飞机就飞往离它距离最小的G点（图4.6），然后C点在系统内消失。同时平面内出现很多点。这时候不能不考虑D点了。再以上述方法进行飞行修复节点。五模型的分析5.1模型1满足完全覆盖条件的正多边形只有正三角形、正四边形、正六边形；正多边形346K的取值39.0918.155.77则只需k5.77，就可以根据实际情况找到一种完全覆盖一个给定的n*n(覆盖率为100%)矩

22、形的最优方式，其变化趋势如图5.1 正多边形相交率K的变化趋势图图5.15.2模型2当时，进行节点修复。计算点与点之间的距离Di=制作成一个n阶矩阵从原点开始，i=0，k=1；从第i行中选出该行中的最小数Di；然后i=j(把j赋给i)，且把第i列的值全改为；ak=i，k=k+1；重复的步骤，直到矩阵中的数全为；则修复传感器的顺序为a1,a2, a3an，此时所部署的代价（时间、能量消耗）最小。六模型的评价及改进6.1 模型的评价 三个模型运用了几何知识等数学方法。 模型1讨论了一定条件下的完全覆盖问题可以为实际情况提供一些定量分析。模型2讨论了关于最短路径问题。模型3是对模型2进行优化和实际化

23、。 模型虽具有一般性，但并不是所有情况都适用。6.2 模型的改进模型1我们先通过具体的实例来讨论区域覆盖问题，使得问题较为简单、直观，而实际情况还有诸多相关因素与要讨论的问题相互制约；在现在的经济社会中，应该加以考虑使用的圆的半径为多少时，能使覆盖矩形的圆的面积最少，而我们只讨论了k（相邻两圆相交的公共面积不小于一个圆面积的k）的变动情况，还有待于改进讨论方向。模型2所使用的算法不够优化，存在一定的问题。例如：5%的检测区域没有很好的排布，对于一开始所选取的坐标轴不是最优的。可以有所改换。模型3，数据处理不够明了，考虑客观实际因素不够完善。七参考文献 1 姜启源,谢金星,叶俊. 数学模型（第三

24、版），高等教育出版社。 2 杨中华. 平面点列最小覆盖圆的计算方法，北京工业大学学报，2000,vol.26(2) 3 数学模型与计算机模拟，江裕钊、辛培情编，电子科技大学出版社，(1989) 4 数学建模-方法与范例，寿纪麟等编，西安交通大学出版社(1993) 5 数学模型，朱思铭、李尚廉编，中山大学出版社，(1995) 6 数学模型建模分析，蔡常丰编著，科学出版社，(1995) 7 数学建模竞赛教程，李尚志主编，江苏教育出版社，(1996) 8 数学建模入门，徐全智、杨晋浩编，成都电子科大出版社，(1996). 9 数学模型方法，齐欢编著，华中理工大学出版社，(1996)10 数学建模优秀

25、案例选编(工科数学基地建设丛书)，汪国强主编，华南理工大学出版社，(1998)11 问题解决的数学模型方法，刘来福，曾文艺编著、北京师范大学出版社， 附录附录1、判断哪些正多边形能够完全覆盖的程序for i=3:1000; m(i)=i; n(i)=2*m(i)/(m(i)-2); if mod(n(i),1)=0; dip('m=',num2str(m(i),' n=',num2str(n(i) endend附录2、正四边形完全覆盖程序r=input('请输入圆的半径r=');m=input('请输入宽m=');n=input(

26、'请输入高n=');Th=0:0.1:2*pi;for i=0:r*sqrt(2):mfor j=0:r*sqrt(2):n x=i+r*cos(th); y=j+r*sin(th); plot(x,y,'k') hold on axis equalendendhold onfor i=0:(m/(r*sqrt(2)for j=0:(n/(r*sqrt(2) x=-r*sqrt(2)/2+r*sqrt(2)*i; y=-r*sqrt(2)/2+r*sqrt(2)*j;rectangle('Position',x,y,r*sqrt(2),r*sqrt(2)endendhold onrectangle('Position',0,0,m,n,'EdgeColor','r')hold onrectangle('Position',-r*sqrt(2)/2,-r*sqrt(2)/2,m,n,'EdgeColor','b')附录3、正六边形完全覆盖程序clear;clcr=input('请输入圆的半径r=');m=input('请输入宽m=