数学建模-遥测遥感网2教材

摘要本文针对遥测遥感网中的监测装置分配在监测区域中的分配方式，建立了优化模型，使其在固定的监测区域，分别在不考虑节能和考虑节能时，得出了对监测装置进展合理的安排，最后对模型进展了评价和推广。问题一：(A1)在监视区域为边长b=100(长度单位)的正方形，每个装置的监视半径均为r=10(长度单位)中，我们利用蜂窝网格的特点，按蜂窝网格的方式来放置使其到达最优，得出最小装置数为45个。(A2)我们在整个监测区域进展随机的投圆，得出至少需要多少装置使其全部覆盖的概率到达95%。通过在matlab中进展均匀随机模拟实验，得出最终结果：至少需要装置数530个。(A3)当监测区域变成一般的矩形或者多边形时，利用A1和A2的方法，同样可以求出区域所需要的最少装置数及使得区域被全部覆盖的概率到达95%的最少装置数。问题二：〔B1〕为使得能量消耗最少，应该尽量让更多的装置处于“休眠〞状态。我们从第一个点坐标开场找出所有与它距离小于半径10〔长度单位〕的点，然后依次将这些点删掉，最后通过matlab筛选出来的剩余点即为较好的支配集。所求得的较好支配集中装置的个数为28个。〔B2〕通过在问题〔A2〕所得结果的根底上，同样利用问题〔B1〕的方法，求出其较好支配集中的装置的个数为55个。〔B3〕先以任何两点的距离作为权重，利用prim算法求得最小生成树，作为较少连通集的一条主要路径，然后经过大量的分析求得最终的较少连通支配集。利用B1的数据得到的较少连通支配集中装置的个数为59个。关键词：遥测遥感网蜂窝网格随机模拟matlabprim支配集问题重述大气污染所引起的地球气候异常，导致大面积严重森林大火的频频发生，给人民的生命财产造成巨大损失。因此，不少国家政府都在研究有效的森林防火措施。在容易出现高森林火险的重点地区放置高科技的监视装置，建立遥测遥感网，使人们能准确而及时地掌握险情的开展情况，为有效地防止火灾发生或在酿成严重灾害之前将其扑灭创造条件。科技的迅速开展使人们可以制造不太昂贵且具有收发报通讯功能的监视装置。放置在同一监视区域的这种监视装置〔以下简称为装置〕构成一个AdHoc无线网络，即通常所说的遥测遥感网。如果监视区域的每一点都处于放置在该区域*个装置的监视围，则称这些装置能覆盖该监视区域。研究能确保有效〔即按一定概率〕覆盖且数量最少的装置系统的随机放置问题显然具有重要意义。第一个问题涉及能覆盖给定监视区域的装置数目及分配问题，具体如下：A1设监视区域为边长b=100(长度单位)的正方形，每个装置的监视半径均为r=10(长度单位)。请参考蜂窝网格的特性讨论覆盖该区域所需装置的最少数量。A2在设计遥测遥感网时，首先需要知道对给定监视区域在一定的覆盖保证下应放置装置的最正确〔越少越佳〕数量，并且常假设装置在监视区域是均匀地随机放置的。请在上述假设下建立数学模型，利用随机模拟实验答复：对于A1中给定的监视区域及监视半径，至少需要随机放置多少个装置，才能使得成功覆盖整个区域的概率在95%以上？并给出一个均匀随机放置装置的分布图。A3对一般矩形以及多边形的监视区域进一步探讨以上问题。由于监视旱情的遥测遥感网地处遥远地区，它的每个〔除极少数例外〕装置都只能以电池为能源，电池用尽装置即报废。因此，如何节省电池能耗是设计此类网络运行方案的头等大事。常用的一个很有效的节能措施是：让大多数装置“休眠〞只保存尽可能少的装置“值班〞。对同时选出的这些值班装置的全体，必须要求它们整体具有与遥测遥感网的每个装置都能联系的功能，从而保证当任何休眠装置定时“醒〞后假设发现“险情〞，都能及时向值班者之一传递险情信息。遥测遥感网的假设干装置组成的子集S称为一个支配集，如果该遥测遥感网中不属于S的任一装置必位于S中*个装置的通讯围之〔即二者可互相交换信息〕。不言而喻，上述同时“值班〞的装置的集合必须要该遥测遥感网络的一个支配集。从实际应用的角度来说，这种支配集的优劣以其包含的装置个数来衡量〔越少越优〕。此外，如果把考虑的遥测遥感网视为一个无向图〔每个装置是它的顶点，二顶点相邻接当且仅当二点间的距离小于公共的通讯半径R〕。支配集按图论意义是连通者更为可取，因为通过仅在支配集部传递信息的手段可以让它的每个装置共享任一装置所得到的信息，这样的支配集自然称为连通支配集。第二个问题涉及求元素尽可能少的支配集和连通支配集的问题，具体如下：B1设监视区域为边长b=100〔长度单位〕的正方形，每个装置的通讯半径均为R=10〔长度单位〕。在该监视区域放置了120个装置，它们位置的横、纵坐标依次是：*=57,95,34,31,52,30,15,75,75,65,55,41,36,72,16,85,86,75,32,5,16,25,72,68,61,37,48,81,23,35,6,85,64,22,69,y=58,74,12,68,67,4,75,52,30,28,63,61,20,24,10,49,90,90,20,92,35,66,4,33,35,78,46,31,90,66,33,9,37,13,43,83,13,请建立数学模型找出一个较好的支配集；画出该120个装置的分配图，并在此图上标出所找到的支配集。B2对于你在A2问题中给出的装置分配图，找出一个较好的支配集；并在原装置分配图上标出该支配集。B3建立寻找连通支配集的数学模型，并对B1中给定的含120个装置的遥测遥感网和A2问题中给出的装置分配图分别求出元素个数较少的连通支配集，且在原装置分配图上标出该连通支配集。模型假设假设单个装置所覆盖的形状为圆形。假设每个装置可以看做一个点。假设监测区域是平整的。模型的建立与求解问题一A1.1问题的分析首先，我们证明了一个圆与其它六个圆的交点构成正六边形时，此时，单个装置的有效覆盖面积是最大的〔证明过程见附录1.1〕。因此，对于边长为100〔长度单位〕的正方形区域，我们直接利用正六边形来模拟，参考蜂窝网格的特性，求得出覆盖整个区域的最少装置数。A1.2模型的建立及求解将一个正六边形放置于该区域的中心，然后让其四周向外扩展，直到充满整个区域为止，所得到的个数即为最少装置数。利用matlab编程求得图形如下〔代码见附录1.2〕：A2.1问题的分析为使得装置覆盖整个区域的概率到达95%，我们采用类似于蒲丰投针的随机实验进展模拟，即：对于一个边长为100〔长度单位〕的正方形区域，随机的向此区域投入半径为10〔长度单位〕的圆。所求得的最小装置数应满足：按这个数目进展随机投入时，其中至少有投入次数的95%的次数应该使得整个区域被覆盖住，则，该结果必能满足求解要求。A2.2模型的建立及求解通过matlab编程，运行得到结果为〔代码见附录1.3〕：最少需随机放置的装置数为：530个。A3.1模型的分析〔1〕利用问题A1的思路，我们认为，对于矩形和多边形，都可以利用正六边形来进展模拟，可以求出矩形区域或多边形区域时的最少装置数；〔2〕利用问题A2的思路，同样利用投针的思想，用半径为10〔长度单位〕的圆去投入矩形或多边形区域中，当所投的次数当中，有其中95%的次数使得区域被完全覆盖，则所得的最小的结果即为最少装置数。A3.2模型的建立〔1〕同样将一个正六边形放置于矩形或多边形区域的中心，然后让其四周向外扩展，直到充满整个区域为止，所得到的个数即为最少装置数。〔2〕当所投的次数当中，有其中95%的次数使得区域被完全覆盖，则所得的最小的结果即为最少装置数。问题二B1.1问题的分析要让大多数装置“休眠〞只保存尽可能少的装置“值班〞，即找出一组最小装置数组成的支配集。此支配集并不能将边长为100〔长度单位〕的正方形区域覆盖住，但它所有连接的其它装置“醒〞后，是一定要能将该区域覆盖住，而且此支配集中任何两个装置之间并不一定要有连接。因此，我们先找出与任意一点的距离小于10〔长度单位〕的所有点，然后将这些点删掉，即让删掉的这些点处于“休眠〞状态，重复这些过程，经过大量的人工分析，最终得到剩余的点即为支配集的元素；同时，也利用matlab编程得到了同样的结果。B1.2模型的建立及求解先求其它点与*任一个点的距离小于半径10〔长度单位〕〔代码见附录1.4〔1〕，再利用matlab运行的结果如下(代码见附录1.4〔2〕)：最终得出较少支配集的总个数为：28个。用E*cel画得各个装置的位置如下列图所示：B2.1问题的分析利用A2的结果，同样，要让大多数装置“休眠〞只保存尽可能少的装置“值班〞，即找出一组最小装置数组成的支配集。此支配集并不能将边长为100〔长度单位〕的正方形区域覆盖住，但它所有连接的其它装置“醒〞后，是一定要能将该区域覆盖住，而且此支配集中任何两个装置之间并不一定要有连接。因此，我们先找出与任意一点的距离小于10〔长度单位〕的所有点，然后将这些点删掉，即让删掉的这些点处于“休眠〞状态，重复这些过程，经过复杂的人工分析最终得到剩余的点即为支配集的元素。B2.2模型的建立与求解经matlab运行后得以下结果〔代码见附录1.5〕最终得到的较少支配集的数量为：55个B3.1问题的分析对于B1和A2中的数据，由于此时所求的是连通支配集，即说明所求得的支配集中各个装置之间必须有至少有一条直接或间接的通路，使各个装置之间也产生关联，这便是此问题的关键所在。我们在上述所求支配集的情况下，在各个支配集的装置之间参加一些元素，使得任何两个装置之间至少有一条通路〔即满足二装置间的距离小于公共的通讯半径10〔长度单位〕〕。B3.2模型的建立于求解〔1〕对于B1中的数据，我们首先根据最小生成树图〔代码见1.6〕得出一条主要路径，然后经过分析得到一条最小连通集。用E*cel所描绘出来的最小连通支配集如下列图所示：最小连通集的个数为：59个〔2〕对于A2中的数据,同样利用B3.2〔1〕的方法求出其较少的连通支配集，由于时间的关系，未能具体求出其值。模型的评价模型的优点〔1〕本文所建立的模型都具有一定的理论根底，可行性较高。〔2〕所得到的图形都是通过matlab编程或E*cel而实现，准确度很高。〔3〕模型与实际问题联系严密，结合实际情况对所提出的问题进展了求解，使模型更贴近实际，运用性更广。模型的缺点〔1〕模型虽然综合考虑到了很多因素，但为了建立模型，理想化了许多因素，具有一定的局限性，得到的结果可能并不一定是最优的。〔2〕有些得到的图形经过了一定的人工分析才得到了结果，使得结果可信度会降低。模型的推广本文所建立的所有模型均比拟抽象，但实用性很强，而且与实际联系非常严密。〔1〕问题一中A1所建立的模型可以推广于一定区域中各种装置的最优安放问题中;A2中建立的模型即可用于大量随机模拟实验中，如蒲丰投针等计算概率的实验当中。〔2〕问题二中B1和B2建立的模型可推广于电路中各个元件的工作问题当中；B3建立的模型即可推广于有条件约束的铁路铺设问题、求最优路径等问题中。参考文献[1]凡志刚郭文生桑楠，一种基于蜂窝网格的传感器节点部署算法，传感器与微系统，第27卷第4期：15-17，2008.附录1.1证明过程：定理1：如果3个半径一样的圆两两相交且覆盖面积最大，则三圆必交于一点。定理2：如果三圆两两相交且相交于一点，并且，3个圆圆心围成等边三角形，则其覆盖面积最大。证明：如果3个半径一样且两两相交的圆覆盖面积最大，则必相交一点(定理1)。图3中，设n为三圆交点。每个圆心到交点n的距离为，所以，三圆心必然处在以n为圆心，以为半径的圆周上。要使三圆覆盖面积最大，则等价于阴影局部、、的面积和最小。因，所以，。设上面3个扇形面积和为，，则。因此，要使阴影局部面积最小，则等价于面积最大，等价于面积最大。共圆，则为等边三角形时面积最大。从定理2可知，当覆盖面积最大时，三圆心构成了等边三角形。如图4(a)中，。，则与6个圆相交，不妨设六圆圆心分别为，则圆与这6个圆的交点构成正六边形。此时，单个传感器节点的有效覆盖面积到达最大。1.2问题一A1的matlab代码clc,closeallr=10;rc=0.7;figure;a*issquareholdon;A=pi/3*[0:6];aa=linspace(0,pi*2,80);plot(r*e*p(i*A),'k','linewidth',2);%Authoremail:zjliu2001163.%From:萝卜驿站g1=fill(real(r*e*p(i*A)),imag(r*e*p(i*A)),'k');set(g1,'FaceColor',[1,0.5,0])g2=fill(real(rc*e*p(i*aa)),imag(rc*e*p(i*aa)),'k');set(g2,'FaceColor',[1,0.5,0],'edgecolor',[1,0.5,0],'EraseMode','*or')te*t(0,0,'1','fontsize',10);Z=0;At=pi/6;RA=-pi/2;N=1;At=-pi/2-pi/3*[0:6];fork=1:4;Z=Z+sqrt(3)*r*e*p(i*pi/6);forpp=1:6;forp=1:k;N=N+1;zp=Z+r*e*p(i*A);zr=Z+rc*e*p(i*aa);g1=fill(real(zp),imag(zp),'k');set(g1,'FaceColor',[1,0.5,0],'edgecolor',[1,0,0]);g2=fill(real(zr),imag(zr),'k');set(g2,'FaceColor',[1,0.5,0],'edgecolor',

[1,0.5,0],'EraseMode','*or');te*t(real(Z),imag(Z),num2str(N),'fontsize',10);Z=Z+sqrt(3)*r*e*p(i*At(pp));endendend*lim([-50,50])ylim([-50,50])a*isoff;1.3〔1〕问题一A2算覆盖率代码clear;clc;lu=0;forl=1:1:100L=100;%正方形区域边长R=10;%圆半径M=zeros(L);%覆盖状态N=0;%统计圆的数目ss=1;%循环控制变量[m,n]=meshgrid(1:L);Ar=linspace(0,pi*2,200);%圆周角度scale=0;%覆盖面积比例whiless*=L*rand;%随机位置坐标y=L*rand;%随机位置坐标D=sqrt([m-*].^2+[n-y].^2);%计算坐标点到圆心的距离[m0,n0]=find(D<=R);%检测出圆覆盖点的坐标Ind=sub2ind([L,L],m0,n0);%坐标与索引转化M(Ind)=1;%改变覆盖状态N=N+1;%增加圆数目*inde=sum(M(1:end))/L/L;%计算覆盖比例scale=*inde;ifN==531;%检测是否满足覆盖比例ss=0;%完毕循环endendifscale==1lu=lu+1;endendlu/1001.3〔2〕作图代码clc;clear;closeall;L=100;%正方形区域边长R=10;%圆半径M=zeros(L);%覆盖状态N=0;%统计圆的数目ss=1;%循环控制变量[m,n]=meshgrid(1:L);a*is([0,L,0,L]);a*issquare;holdon;Ar=linspace(0,pi*2,200);%圆周角度scale=0;%覆盖面积比例Tt=title(['scale=0,','N=0']);A1=gca;A*=a*es('Position',[0.9,0.11,0.04,0.8],'TickDir','out');Fi=fill([0,1,1,0],[0,0,0.003,0.003],'r');%绘制覆盖比例的变化a*is([0,1,0,1]);whiless*=L*rand;%随机位置坐标y=L*rand;%随机位置坐标C=rand(1,3);%随机颜色a*es(A1);plot(*,y,'+','color',C);%画圆心D=sqrt([m-*].^2+[n-y].^2);%计算坐标点到圆心的距离[m0,n0]=find(D<=R);%检测出圆覆盖点的坐标Ind=sub2ind([L,L],m0,n0);%坐标与索引转化M(Ind)=1;%改变覆盖状态N=N+1;%增加圆数目scale=sum(M(1:end))/L/L;%计算覆盖比例set(Tt,'string',['scale=',num2str(scale*100),'%,N=',num2str(N)]);set(Fi,'YData',[0,0,scale,scale]);SC(N)=scale;ifN==531;%检测是否满足覆盖比例ss=0;%完毕循环scale%输出覆盖比例N%输出圆数目endpause(0.1);endfigure;plot(1:N,SC);*label('\itN');ylabel('scale');1.4〔1〕问题二B1求距离代码clc;clear;closeall;L=100;%正方形区域边长R=10;%圆半径M=zeros(L);%覆盖状态N=0;%统计圆的数目ss=1;%循环控制变量e=1;js=0;j=1;chunchu2=zeros(120,10);[m,n]=meshgrid(1:L);a*is([0,L,0,L]);a*issquare;holdon;Ar=linspace(0,pi*2,200);%圆周角度scale=0;%覆盖面积比例Tt=title(['scale=0,','N=0']);A1=gca;A*=a*es('Position',[0.9,0.11,0.04,0.8],'TickDir','out');Fi=fill([0,1,1,0],[0,0,0.003,0.003],'r');%绘制覆盖比例的变化a*is([0,1,0,1]);w=[57,95,34,31,52,30,15,75,75,65,55,41,36,72,16,85,86,75,32,5,16,25,72,68,61,37,48,81,23,35,6,85,64,22,69,80,76,88,25,62,70,45,35,75,35,56,27,92,25,44,5,17,90,25,58,95,87,68,30,9,32,47,50,56,56,47,80,10,12,63,39,81,43,17,80,45,92,78,89,51,40,65,76,30,26,28,25,29,40,4,74,41,39,95,72,79,78,10,8,15,45,70,90,84,20,40,55,5,73,22,17,50,55,87,72,55,7,85,35,10];u=[58,74,12,68,67,4,75,52,30,28,63,61,20,24,10,49,90,90,20,92,35,66,4,33,35,78,46,31,90,66,33,9,37,13,43,83,13,94,95,45,70,42,9,41,91,30,92,90,58,52,80,33,5,74,47,2,72,88,28,9,95,71,43,43,25,25,64,96,33,70,9,89,14,25,55,61,40,22,45,51,90,49,7,98,34,99,8,63,83,11,44,25,21,51,76,8,44,80,89,95,90,82,78,78,70,71,70,95,18,28,80,10,20,22,98,79,2,20,50,68];whiless*=w(e);%随机位置坐标y=u(e);%随机位置坐标C=rand(1,3);%随机颜色a*es(A1);plot(*,y,'+','color',C);%画圆心plot(*+i*y+R*e*p(i*Ar),'color',C);%画圆D=sqrt([m-*].^2+[n-y].^2);%计算坐标点到圆心的距离[m0,n0]=find(D<=R);%检测出圆覆盖点的坐标Ind=sub2ind([L,L],m0,n0);%坐标与索引转化M(Ind)=1;%改变覆盖状态forf=1:1:120D1=sqrt([w(f)-w(e)].^2+[u(f)-u(e)].^2);ifD1<Rjs=js+1;chunchu2(e,j)=f;j=j+1;endendj=1;chunchu1(e)=js;N=N+1;%增加圆数目scale=sum(M(1:end))/L/L;%计算覆盖比例set(Tt,'string',['scale=',num2str(scale*100),'%,N=',num2str(N)]);set(Fi,'YData',[0,0,scale,scale]);SC(N)=scale;e=e+1;js=0;ife==121;%检测是否满足覆盖比例ss=0;%完毕循环scale%输出覆盖比例N%输出圆数目endpause(0.1);endfigure;plot(1:N,SC);*label('\itN');ylabel('scale');chunchu21.4〔2〕问题二B1画图代码clc;clear;closeall;L=100;%正方形区域边长R=10;%圆半径M=zeros(L);%覆盖状态N=0;%统计圆的数目j=1;ff=1;ss=1;%循环控制变量[m,n]=meshgrid(1:L);a*is([0,L,0,L]);a*issquare;holdon;Ar=linspace(0,pi*2,200);%圆周角度scale=0;%覆盖面积比例ju=zeros(1,120);Tt=title(['scale=0,','N=0']);A1=gca;A*=a*es('Position',[0.9,0.11,0.04,0.8],'TickDir','out');Fi=fill([0,1,1,0],[0,0,0.003,0.003],'r');%绘制覆盖比例的变化a*is([0,1,0,1]);a=[57,95,34,31,52,30,15,75,75,65,55,41,36,72,16,85,86,75b=[58,74,12,68,67,4,75,52,30,28,63,61,20,24,10,49,90,90,ccc=[7 10 17 18 22 27 30 35 47 50 53 60 66 69 73 75 78 79 80 83 87 89 93 95 99 103 107 110];Ar=linspace(0,pi*2,200);whilessff=1;*=a(j);%随机位置坐标y=b(j);%随机位置坐标C=rand(1,3);%随机颜色a*es(A1);plot(*,y,'+','color',C);%画圆心whileff<29ifccc(ff)==jplot(*+i*y+R*e*p(i*Ar),'color',C);%画圆break;endff=ff+1;endD=sqrt([m-*].^2+[n-y].^2);%计算坐标点到圆心的距离[m0,n0]=find(D<=R);%检测出圆覆盖点的坐标Ind=sub2ind([L,L],m0,n0);%坐标与索引转化M(Ind)=1;%改变覆盖状态N=N+1;%增加圆数目*inde=sum(M(1:end))/L/L;%计算覆盖比例if*inde==scaleju(N)=j;endscale=*inde;set(Tt,'string',['scale=',num2str(scale*100),'%,j=',num2str(j)]);set(Fi,'YData',[0,0,scale,scale]);SC(N)=scale;j=j+1;ifj==121;%检测是否满足覆盖比例ss=0;%完毕循环scale%输出覆盖比例N%输出圆数目endpause(0.1);endfigure;plot(1:N,SC);*label('\itN');ylabel('scale');1.5问题二B2代码clc;clear;closeall;L=100;%正方形区域边长R=10;%圆半径M=zeros(L);%覆盖状态N=0;%统计圆的数目ss=1;%循环控制变量en=1;ji=1;e=1;mm=1;nn=1;lu=zeros(1,210);da=zeros(1,210);chunchu2=zeros(210,210);[m,n]=meshgrid(1:L);a*is([0,L,0,L]);a*issquare;holdon;Ar=linspace(0,pi*2,200);%圆周角度scale=0;%覆盖面积比例Tt=title(['scale=0,','N=0']);A1=gca;A*=a*es('Position',[0.9,0.11,0.04,0.8],'TickDir','out');Fi=fill([0,1,1,0],[0,0,0.003,0.003],'r');%绘制覆盖比例的变化a*is([0,1,0,1]);lu=w;da=u;whilessmm=1;*=lu(ji);%随机位置坐标y=da(ji);%随机位置坐标C=rand(1,3);%随机颜色a*es(A1);if*==200ji=ji+1;elseif*~=200plot(*,y,'+','color',C);%画圆心plot(*+i*y+R*e*p(i*Ar),'color',C);%画圆D=sqrt([m-*].^2+[n-y].^2);%计算坐标点到圆心的距离[m0,n0]=find(D<=R);%检测出圆覆盖点的坐标Ind=sub2ind([L,L],m0,n0);%坐标与索引转化M(Ind)=1;%改变覆盖状态nn=nn+1;forf=1:1:210iff~=jiD1=sqrt([lu(f)-lu(ji)]