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

. . 第一次个人赛论文 姓名代码：123 无线传感网络设计问题 摘要 本文主要研究了无线传感网络设计问题，首先运用概率论与数理统计相关思想给出了覆盖概率的定义，并用蒙特卡罗方法得出了最少节点数，为无线传感网络的设计提供了最佳方案。然后建立了节点间的通信模型，并利用图论思想对该模型进行了相应的改进。 针对问题1：我们运用概率论相关思想，结合蒙特卡罗方法，给出了覆盖概率的定义，根据贪婪算法基本原理，利用软件求解得当节点数为540个时，才能使得成功覆盖整个区域的概率在95%以上。然后我们对模型求解结果进行了分布检验，验证了模型的正确性。 针对问题2：我们首先建立了节点间的通信模型，给出了任意10组两节点间的通信通路，然后结合图论思想，利用算法对模型进行了相应的改进，给出了节点间的最短通信通路。最后运用算法对结果进行了检验，从而验证了结果的合理性。 最后，本文对模型进行了检验，并结合实际评价了模型的优缺点，对模型中存在的不足进行了改进，将模型进行了推广。 关键词： 覆盖概率，节点，通信模型，算法； 问题的提出和重述 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做出节点间的连通图，即可给出任意两节点间的通信通路。为了使通信通路达到最优，我们还可以考虑运用图论的相关思想对节点间的通信通路进行优化，从而获得最经济合理的通信方式。 模型假设 节点的产生服从均匀随机分布。 监视装置工作稳定，监测工作不受外界影响。 监测区域为二维平面，监测区域中所有节点都作用在同一个平面内。 符号及变量说明 ：监视区域长度； ：监视区域宽度； ：节点覆盖半径； ：成功覆盖整个区域的概率； ：节点横坐标，； ：节点纵坐标，； ：第个节点，； ：节点个数，单位：个； ：随机模拟次数，单位：次； ：成功覆盖次数，单位：次； ：网格中任意结点坐标； ：阴影部分面积； ：图形总面积。 模型的建立和求解 5.1对于问题一模型的建立和求解 5.1.1数据处理 根据题意可知监测区域为边长的正方形，每个节点的