数学建模第二次个人赛论文

1第一次个人赛论文姓名代码：123无线传感网络设计问题摘要本文主要研究了无线传感网络设计问题，首先运用概率论与数理统计相关思想给出了覆盖概率的定义，并用蒙特卡罗方法得出了最少节点数，为无线传感网络的设计提供了最佳方案。然后建立了节点间的通信模型，并利用图论思想对该模型进行了相应的改进。针对问题1：我们运用概率论相关思想，结合蒙特卡罗方法，给出了覆盖概率的定义，根据贪婪算法基本原理，利用软件求解得当节点数为540个时，才能使得成功覆盖整个区域的概率在95%以上。然后我们对模型求解结果进行了分布检验，验证了模型的正确性。针对问题2：我们首先建立了节点间的通信模型，给出了任意10组两节点间的通信通路，然后结合图论思想，利用Dijkstra算法对模型进行了相应的改进，给出了节点间的最短通信通路。最后运用Floyd算法对结果进行了检验，从而验证了结果的合理性。最后，本文对模型进行了检验，并结合实际评价了模型的优缺点，对模型中存在的不足进行了改进，将模型进行了推广。关键词：覆盖概率，节点，通信模型，Dijkstra算法；2一、问题的提出和重述1.1问题的提出大气污染所引起的地球气候异常，导致地震、旱灾等自然灾害频频发生，给人民的生命财产造成巨大损失。因此，不少国家政府都在研究如何有效监测自然灾害的措施。在容易出现自然灾害的重点地区放置高科技的监视装置，建立无线传感网络，使人们能准确而及时地掌握险情的发展情况，为有效地抢先救灾创造有利条件。科技的迅速发展使人们可以制造不太昂贵且具有通讯功能的监视装置。放置在同一监视区域内的这种监视装置（以下简称为节点）构成一个无线传感网络。如果监视区域的任意一点都处于放置在该区域内某一节点的监视范围内，则称节点能覆盖该监视区域。研究能确保有效覆盖且数量最少的节点放置问题显然具有重要意义。图1（见附录一）中，叉形表示一个无线传感网络节点，虚线的圆形区域表示该节点的覆盖范围。可见，该无线传感网络节点完全覆盖了区域B，部分覆盖了区域A。网络节点间的通信设计问题是无线传感器网络设计的重要问题之一。如前所述，每个节点都有一定的覆盖范围，节点可以与覆盖范围内的节点进行通信。但是当节点需要与不在其覆盖范围内的节点通信时，需要其它节点转发才可以进行通信。图2（见附录二）所示，节点C不在节点A的覆盖范围之内，而节点B在A与C的覆盖范围之内，因此A可以将数据先传给B，再通过B传给C。行成一个A－B－C的通路。1.2问题的重述问题1：在一个监视区域为边长b=100(长度单位)的正方形中，每个节点的覆盖半径均为r=10(长度单位)。设计传感网络时，需考虑节点数最少原则，根据已知条件，确定使得成功覆盖整个区域的概率在95%以上的最少节点数。问题2：在问题1所给的条件下，已知在该监视区域内放置了120个节点，它们位置的横、纵坐标如表1（见附录三）所示。设计一种节点间的通信模型，并给出任意10组两节点之间的通信通路。二、问题的分析无线传感网络设计问题要考虑到节点数量，达到一定覆盖率，节点间通信等因素，是一类基于概率论与数理统计的随机问题。由于在模拟节点分布时追求完全覆盖且节点数最少，我们可以运用蒙特卡罗思想进行分析，结合Matlab软件进行求解，从而得到最少节点数。在保证节点间通信的情况下，我们可以根据图论原理，找出两节点间的最短通信路径，获得最经济合理的通信方式。针对问题一：根据题意可知，在设计传感网络时，需要知道对给定监视区域在一定的覆盖保证下应放置节点的最少数量。对于一个给定的区域，我们可以考虑蒙特卡罗原理，采用随机模拟的方法产生多组节点，不断调整节点的数值，计算满足成功覆盖整个区域的概率，使其达到95%以上，此时的节点数即可视为最少节点数。针对问题二：对于该问题，题目中要求给出任意10组两节点之间的通信通路，由于两节点间距离小于节点覆盖半径时即可进行通信，利用Matlab做出节点间的连通图，即可给出任意两节点间的通信通路。为了使通信通路达到最优，我们还可以考虑运用图论的相关思3想对节点间的通信通路进行优化，从而获得最经济合理的通信方式。三、模型假设1、节点的产生服从均匀随机分布。2、监视装置工作稳定，监测工作不受外界影响。3、监测区域为二维平面，监测区域中所有节点都作用在同一个平面内。四、符号及变量说明a：监视区域长度；b：监视区域宽度；r：节点覆盖半径；P：成功覆盖整个区域的概率；ix：节点横坐标，ni,...,2,1；iy：节点纵坐标，ni,...,2,1；iC：第i个节点，ni,...,2,1；n：节点个数，单位：个；k：随机模拟次数，单位：次；m：成功覆盖次数，单位：次；),(yxA：网格中任意结点坐标；1S：阴影部分面积；S：图形总面积。五、模型的建立和求解5.1对于问题一模型的建立和求解5.1.1数据处理根据题意可知监测区域为边长100b的正方形，每个节点的覆盖半径为10r，要求达到的最小覆盖概率为95%，具体数据如下表1所示。表1监测区域长度监测区域宽度节点覆盖半径覆盖概率随机模拟次数方格划分1001001095%1000100005.1.2模型建立5.1.2.1覆盖概率本题要求成功覆盖整个区域的概率在95%以上，而直接计算覆盖概率比较困难，因此本文提出了一种基于网格划分的覆盖概率计算方法，如下图1所示，其中五角星表示节点，圆圈表示节点覆盖区域，小圆点表示矩形格的结点，在此以100个网格为例进行分析。4图1定义覆盖概率计算方法如下：1、将目标区域均匀划分成qq个矩形格；2、依次取每一矩形格上的结点，设其结点坐标为),(yxA；3、利用蒙特卡罗方法，随机生成服从均匀分布的n个节点),(iiiyxC；4、计算矩形格结点与节点iC之间的欧氏距离22)()(iiyyxxd（1）若10d则表示该结点被覆盖；5、以每一个矩形格结点的覆盖特性代表整个矩形格的覆盖特性，统计满足覆盖要求的矩形格结点的数量M，若M的值等于所有矩形格结点的数量，则表示节点成功覆盖整个区域；6、当随机模拟次数为k次时，若满足成功覆盖整个区域的次数为m次，则覆盖概率的计算方法为：kmP（2）在此，我们可以借助流程图简单模拟覆盖概率的计算，其具体计算方法如下图2所示：5图2覆盖概率计算流程图5.1.2.2最少节点计算根据覆盖概率的计算流程图，可以利用贪婪算法进行求解：先给定一个节点数n，按照覆盖概率计算方法求出当节点数为n时的覆盖概率，若此时覆盖概率小于95%，则开始随机抛洒节点n个（半径为r）将正方形分为10000个小方格1000mp计算所有节点与小方格结点之间的距离d1mm试验次数1k，成功次数0m所有dr是1000k是否否1kk6增大节点个数继续进行计算，直到满足覆盖概率大于95%为止，此时的节点数即为使得成功覆盖整个区域的概率在95%以上的最小节点数。5.1.3模型求解及结果分析由5.1.2中给出的覆盖概率计算方法，利用Matlab编程求解（程序见附录四）可得：当节点数为540个时，才能使得成功覆盖整个区域的概率在95%以上。由于节点是随机产生的，每次得出的覆盖概率不是确定的，但我们可以多次运行程序，对所有结果进行分布检验，从而验证结论的合理性。结论：当节点数为540个时，才能使得成功覆盖整个区域的概率在95%以上。5.2对于问题二的讨论求解5.2.1节点间的通信模型在问题一的条件下，已知该监视区域内120个节点的坐标值),(iiiyxC，若使节点间实现通信，需满足：120,...,2,1120,...,2,1)()(22jiryyxxjiji（3）其中：r——节点覆盖半径。利用Matlab（程序见附录五）做出节点间连通图如下图3所示：01020304050607080901000102030405060708090100123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120节点间的通信模型图xy图3节点间连通图根据上图可知，每两个可以连通的节点之间均用一条线连接，若想知道两个节点之间的通信通路，只要从一个节点开始，沿着连线找到下一个节点即可。由于每两个节点之间都有很多条通路，在此对每两个节点选取一条通路，给出10组两节点间的通信通路如下表2所示：7表2节点间通信通路起始节点终止节点通信通路1101—80—55—40—33—101201—80—50—12—30—4—22—54—111—98—99—201301—11—5—62—106—301401—80—64—401501—80—501601—80—64—25—10—65—66—13—3—6—67—34—15—601701—11—107—701801—801901—80—64—25—10—65—66—13—3—6—67—34—15—60—9011001—80—50—12—30—4—22—54—111—98—99—1005.2.2节点间最短通路由5.2.1中给出的节点间通信通路可知任意两个可以连通的节点间的通路都有很多条，这些通路所包含的路径有长有短，而在现实生活中，我们有时希望节点间的通信通路尽可能短，以达到节省通信成本等目的，故我们采用最短路径法求解两节点间的最短通信通路。5.2.2.1Dijkstra算法计算最短路径原理利用Dijkstra算法计算最短路径，即采用标号作业法,每次迭代产生一个永久标号,从而生长一颗以0v为根的最短路树,在这颗树上每个顶点与根节点之间的路径皆为最短路径。5.2.2.2Dijkstra算法计算最短路径步骤S——具有永久标号的顶点集；)(vl——v的标记；)(vf——v的父顶点,用以确定最短路径。具体步骤如下：1、输入加权图的带权邻接矩阵nxmjivvww)],[(。2、初始化：令0)(0vl,S，0vv,)(vl。3、更新)(vl,)(vf，寻找不在S中的顶点u，使)(ul为最小。把u加入到S中，然后对所有不在S中的顶点v,如),()()(vuwulvl,则更新)(vl,)(vf,即),()()(vuwulvl，uvf)(。4、重复步骤（3）,直到所有顶点都在S中为止。5.2.2.3Dijkstra算法求解结果及分析根据Dijkstra原理，我们可以利用Matlab编程（程序见附录五）进行求解。当考虑最短路径时，与5.2.1中相同的两节点之间的通信通路将发生相应的变化，具体如下表3所示：表3考虑最短路径节点间通信通路8起始终止最短距离通信通路11036.14981—80—64—25—1012072.22261—11—5—62—106—4—54—111—98—99—2013030.85941—11—5—62—106—3014021.75391—80—55—4015016.29061—80—5016095.65081—80—64—25—46—65—66—93—13—3—87—15—6017020.38521—11—107—701809.21951—80190101.03601—80—64—25—46—65—66—93—13—3—87—15—60—90110068.33681—11—5—62—106—26—89—45—47—39—100将表3与表2进行比较，有些节点间的通信通路长度有所减少，可知利用Dijkstra方法可以减少两节点间路径，得到最为经济合理的通信通路。六、模型的检验6.1针对问题一该模型用于求解成功覆盖整个区域的概率在95%以上的最少节点数，根据程序运行结果可知每次得到的概率具有随机性，不是一个特定的值，因此我们利用分