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

更新时间：2024-04-06 21:17:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

第一次个人赛论文姓名代码：123

无线传感网络设计问题

摘要

本文主要研究了无线传感网络设计问题，首先运用概率论与数理统计相关思想给出了覆盖概率的定义，并用蒙特卡罗方法得出了最少节点数，为无线传感网络的设计提供了最佳方案。然后建立了节点间的通信模型，并利用图论思想对该模型进行了相应的改进。

针对问题1：我们运用概率论相关思想，结合蒙特卡罗方法，给出了覆盖概率的定义，根据贪婪算法基本原理，利用软件求解得当节点数为540个时，才能使得成功覆盖整个区域的概率在95%以上。然后我们对模型求解结果进行了分布检验，验证了模型的正确性。

针对问题2：我们首先建立了节点间的通信模型，给出了任意10组两节点间的通信通路，然后结合图论思想，利用Dijkstra算法对模型进行了相应的改进，给出了节点间的最短通信通路。最后运用Floyd算法对结果进行了检验，从而验证了结果的合理性。

最后，本文对模型进行了检验，并结合实际评价了模型的优缺点，对模型中存在的不足进行了改进，将模型进行了推广。

关键词：覆盖概率，节点，通信模型，Dijkstra算法；

一、问题的提出和重述

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做出节点间的连通图，即可给出任意两节点间的通信通路。为了使通信通路达到最优，我们还可以考虑运用图论的相关思

想对节点间的通信通路进行优化，从而获得最经济合理的通信方式。

三、模型假设

1、节点的产生服从均匀随机分布。

2、监视装置工作稳定，监测工作不受外界影响。

3、监测区域为二维平面，监测区域中所有节点都作用在同一个平面内。

四、符号及变量说明

a：监视区域长度； b：监视区域宽度； r：节点覆盖半径；

P：成功覆盖整个区域的概率； xi：节点横坐标，i?1,2,...,n；

yi：节点纵坐标，i?1,2,...,n； Ci：第i个节点，i?1,2,...,n； n：节点个数，单位：个； k：随机模拟次数，单位：次； m：成功覆盖次数，单位：次； A(x,y)：网格中任意结点坐标； S1：阴影部分面积； S：图形总面积。

五、模型的建立和求解

5.1对于问题一模型的建立和求解 5.1.1数据处理

根据题意可知监测区域为边长b?100的正方形，每个节点的覆盖半径为r?10，要求达到的最小覆盖概率为95%，具体数据如下表1所示。

表1 监测区域长度监测区域宽度节点覆盖半径覆盖概率随机模拟次数方格划分 100 100 10 >95% 1000 10000 5.1.2模型建立 5.1.2.1覆盖概率

本题要求成功覆盖整个区域的概率在95%以上，而直接计算覆盖概率比较困难，因此本文提出了一种基于网格划分的覆盖概率计算方法，如下图1所示，其中五角星表示节点，圆圈表示节点覆盖区域，小圆点表示矩形格的结点，在此以100个网格为例进行分析。

图1

定义覆盖概率计算方法如下：

1、将目标区域均匀划分成q?q个矩形格；

2、依次取每一矩形格上的结点，设其结点坐标为A(x,y)；

3、利用蒙特卡罗方法，随机生成服从均匀分布的n个节点Ci(xi,yi)； 4、计算矩形格结点与节点Ci之间的欧氏距离

d?(x?xi)2?(y?yi)2

（1）

若d?10则表示该结点被覆盖；

5、以每一个矩形格结点的覆盖特性代表整个矩形格的覆盖特性，统计满足覆盖要求的矩形格结点的数量M，若M的值等于所有矩形格结点的数量，则表示节点成功覆盖整个区域；

6、当随机模拟次数为k次时，若满足成功覆盖整个区域的次数为m次，则覆盖概率的计算方法为：

mP? （2）

k在此，我们可以借助流程图简单模拟覆盖概率的计算，其具体计算方法如下图2所示：

开始试验次数k?1，成功次数m?0 随机抛洒节点n个（半径为r）将正方形分为10000个小方格计算所有节点与小方格结点之间的距离d 否所有d?r k?k?1 是 m?m?1 否 k?1000 是 m p? 1000 图2 覆盖概率计算流程图

5.1.2.2最少节点计算

根据覆盖概率的计算流程图，可以利用贪婪算法进行求解：先给定一个节点数n，按照覆盖概率计算方法求出当节点数为n时的覆盖概率，若此时覆盖概率小于95%，则

增大节点个数继续进行计算，直到满足覆盖概率大于95%为止，此时的节点数即为使得成功覆盖整个区域的概率在95%以上的最小节点数。 5.1.3模型求解及结果分析

由5.1.2中给出的覆盖概率计算方法，利用Matlab编程求解（程序见附录四）可得：当节点数为540个时，才能使得成功覆盖整个区域的概率在95%以上。由于节点是随机产生的，每次得出的覆盖概率不是确定的，但我们可以多次运行程序，对所有结果进行分布检验，从而验证结论的合理性。

结论：当节点数为540个时，才能使得成功覆盖整个区域的概率在95%以上。

5.2对于问题二的讨论求解 5.2.1节点间的通信模型

在问题一的条件下，已知该监视区域内120个节点的坐标值Ci(xi,yi)，若使节点间实现通信，需满足：

(xi?xj)2?(yi?yj)2??ri?1,2,...,120j?1,2,...,120

（3）

其中：r——节点覆盖半径。

利用Matlab（程序见附录五）做出节点间连通图如下图3所示：

节点间的通信模型图10090807060508684681081003961204745811012999519871201051115489261066251161071117011558102954167753818721748361041035724223088127649119508809482165527403591977942636444407733212585316952243046928110591074926665147811493201913113118109733437390101511260437132878396536231175600102030405060708090100xy

图3 节点间连通图

根据上图可知，每两个可以连通的节点之间均用一条线连接，若想知道两个节点之间的通信通路，只要从一个节点开始，沿着连线找到下一个节点即可。由于每两个节点之间都有很多条通路，在此对每两个节点选取一条通路，给出10组两节点间的通信通路如下表2所示：

表2 节点间通信通路起始节点终止节点通信通路 1 10 1—80—55—40—33—10 1 20 1—80—50—12—30—4—22—54—111—98—99—20 1 30 1—11—5—62—106—30 1 40 1—80—64—40 1 50 1—80—50 1 60 1—80—64—25—10—65—66—13—3—6—67—34—15—60 1 70 1—11—107—70 1 80 1—80 1 90 1—80—64—25—10—65—66—13—3—6—67—34—15—60—90 1 100 1—80—50—12—30—4—22—54—111—98—99—100 5.2.2节点间最短通路

由5.2.1中给出的节点间通信通路可知任意两个可以连通的节点间的通路都有很多条，这些通路所包含的路径有长有短，而在现实生活中，我们有时希望节点间的通信通路尽可能短，以达到节省通信成本等目的，故我们采用最短路径法求解两节点间的最短通信通路。

5.2.2.1Dijkstra算法计算最短路径原理

利用Dijkstra算法计算最短路径，即采用标号作业法,每次迭代产生一个永久标号, 从而生长一颗以v0为根的最短路树,在这颗树上每个顶点与根节点之间的路径皆为最短路径。

5.2.2.2Dijkstra算法计算最短路径步骤

S——具有永久标号的顶点集；l(v)——v的标记； f(v)——v的父顶点,用以确定最短路径。具体步骤如下：

1、输入加权图的带权邻接矩阵w?w[(vi,vj)]nxm。

2、初始化：令l(v0)?0,S??，?v?v0 ,l(v)??。

3、更新l(v), f(v)，寻找不在S中的顶点u，使l(u)为最小。把u加入到S中，然后对所有不在S中的顶点v,如l(v)?l(u)?w(u,v),则更新l(v),f(v), 即 l(v)?l(u)?w(u,v)，f(v)?u。

4、重复步骤（3）, 直到所有顶点都在S中为止。 5.2.2.3Dijkstra算法求解结果及分析

根据Dijkstra原理，我们可以利用Matlab编程（程序见附录五）进行求解。当考虑最短路径时，与5.2.1中相同的两节点之间的通信通路将发生相应的变化，具体如下表3所示：

表3 考虑最短路径节点间通信通路

起始终止最短距离通信通路 1 10 36.1498 1—80—64—25—10 1 20 72.2226 1—11—5—62—106—4—54—111—98—99—20 1 30 30.8594 1—11—5—62—106—30 1 40 21.7539 1—80—55—40 1 50 16.2906 1—80—50 1 60 95.6508 1—80—64—25—46—65—66—93—13—3—87—15—60 1 70 20.3852 1—11—107—70 1 80 9.2195 1—80 1 90 101.0360 1—80—64—25—46—65—66—93—13—3—87—15—60—90 1 100 68.3368 1—11—5—62—106—26—89—45—47—39—100 将表3与表2进行比较，有些节点间的通信通路长度有所减少，可知利用Dijkstra方法可以减少两节点间路径，得到最为经济合理的通信通路。

六、模型的检验

6.1针对问题一

该模型用于求解成功覆盖整个区域的概率在95%以上的最少节点数，根据程序运行结果可知每次得到的概率具有随机性，不是一个特定的值，因此我们利用分布检验验证其合理性（程序见附录六）。

做出覆盖概率分布直方图如下图4所示：

54.543.532.521.510.500.940.9450.950.9550.960.9650.970.9750.98

由直方图可以看出覆盖概率基本服从正态分布，利用ttest函数进行正态分布检验

（程序见附录六）得h?0，可知模型一中结果合理。 6.2针对模型二

该模型利用Dijkstra算法给出了节点间的最短通信路径，在此利用Floyd算法进行检验。Floyd算法思想为：直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1)， D(2)， …， D(n)，D(n)是图的距离矩阵, 同时引入一个后继点矩阵记录两点间的最短路径。其具体算法步骤如下：

d(i,j) —— i到j的距离；path(i,j)——i到j的路径上i的后继点； 1、输入带权邻接矩阵a(i,j)。

2、赋初值：对所有i，j， d(i,j)?a(i,j)，path(i,j)?j?，k=l。 3、更新d(i,j) , path(i,j)，对所有i,j，若d(i,k)?d(k,j)?d(i,j),则 d(i,j)?d(i,k)?d(k,j) ，path(i,j)?path(i,k) ，k?k?1。 4、重复3直到k?n?1。

根据Floyd算法思想，利用Matlab编程求解（程序见附录七）可得各节点间最短通信通路如下表4所示：

表4 起始终止最短距离通信通路 1 10 36.1498 1—80—64—25—10 1 20 72.2226 1—11—5—62—106—4—54—111—98—99—20 1 30 30.8594 1—11—5—62—106—30 1 40 21.7539 1—80—55—40 1 50 16.2906 1—80—50 1 60 95.6508 1—80—64—25—46—65—66—93—13—3—87—15—60 1 70 20.3852 1—11—107—70 1 80 9.2195 1—80 1 90 101.0360 1—80—64—25—46—65—66—93—13—3—87—15—60—90 1 100 68.3368 1—11—5—62—106—26—89—45—47—39—100 经检验可知两种方法所得结果一致，从而验证了模型二结果的合理性。

七、模型的评价和改进

7.1模型的评价 7.1.1优点

模型客观地考虑了一定覆盖概率下的节点放置情况，充分运用概率论与数理统计理论进行分析，为无线传感网络的设计提供了合理的分析依据。

模型形式简单，易于理解，能较好地应用于其它网络设计问题。 7.1.2缺点

模型比较理想化，随机模拟次数较少，没有完全考虑到实际应用时的节点布置情况等多种因素的影响。 7.2模型的改进

在问题一中求解最小节点数时运用了随机模拟的方法，在现实生活中，当我们不考虑节点间通信时，可以将其人为进行布置，此时所求最小节点数是一个特例。具体节点放置方法如下：

除了随机放置外，节点放置还有两种固定方法，如下图5和图6所示。

图4 交错放置图5 平行放置

上述两种放置方法不能实现完全覆盖，将其进行改进如图6、7所示。若满足尽可能的覆盖整个监视区域并且节点数最少，则应使节点间重合最少，定义重合度

S （4） ??1

图6 图7

经计算可知交错放置重合度<平行放置重合度，因此交错放置为不考虑通信时的最佳节点放置方案。利用Matlab编程（程序见附录八）做出节点放置图如下：

120100806040200-20-20020406080100120

由上图可知：当不考虑节点间通信时，若人为地使节点均匀分布，所需最少节点数

为45个。

八、模型的推广和应用

无线传感网络设计问题属于一类涉及概率论与数理统计的随机模拟问题，在我们的实际生活中，很多国家政府都在研究有效监测自然灾害的措施，如何获得准确的险情发展情况一直是人们所关心的。利用本模型可以解决现实生活中的无线传感网络设计问题，对一些自然灾害的预报控制具有一定的指导意义。

参考文献：

[1]姜启源,谢金星.数学模型案例选集[M].北京:高等教育出版社.2006.

[2]刘卫国.主编 MATLAB程序设计教程 (第二版)[M].水利水电出版社出版社.2010. [3]袁东,肖广兵.详解MATLAB快速入门与应用[M].电子工业出版社.2011.

[4] 茆诗松,程依明,濮晓龙.概率论与数理统计教程[M].北京:高等教育出版社.2009.

附录一：无线传感网络覆盖示意图

区域A区域B无线传感网络节点

图1 无线传感网络覆盖示意图

附录二：无线传感网络节点通信示意图

节点A节点B节点C

图2 无线传感网络节点通信示意图

附录三：120个节点的坐标表

节点标号 X 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Y 节点标号 X 31 32 33 34 35 36 37 38 39 40 41 42 43 44 Y 节点标号 X 61 62 63 64 65 66 67 68 69 70 71 72 73 74 Y 节点标号 X 91 92 93 94 95 96 97 98 99 100 101 102 103 104 Y 57 58 95 74 34 12 31 68 52 67 30 4 15 75 75 52 75 30 65 28 55 63 41 61 36 20 72 24 6 33 85 9 64 37 22 13 69 43 80 83 76 13 88 94 25 95 62 45 70 70 45 42 35 9 75 41 32 95 47 71 50 43 56 43 56 25 47 25 80 64 10 96 12 33 63 70 39 9 81 89 43 14 17 25 74 44 41 25 39 21 95 51 72 76 79 8 78 44 10 80 8 89 15 95 45 90 70 82 90 78 84 78 Y 节点标号 X

Y 节点标号 X Y 节点标号 X 12 Y 节点标号 X

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 16 10 85 49 86 90 75 90 32 20 5 92 16 35 25 66 72 4 68 33 61 35 37 78 48 46 81 31 23 90 35 66 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 35 91 56 30 27 92 92 90 25 58 44 52 5 80 17 33 90 5 25 74 58 47 95 2 87 72 68 88 30 28 9 9 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 80 55 45 61 92 40 78 22 89 45 51 51 40 90 65 49 76 7 30 98 26 34 28 99 25 8 29 63 40 83 4 11 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 20 70 40 71 55 70 5 95 73 18 22 28 17 80 50 10 55 20 87 22 72 98 55 79 7 2 85 20 35 50 10 68

附录四

问题一Matlab程序

clc n=540; m=0; for k=1:300 x=100*rand(n,1); y=100*rand(n,1); p=0; for i=1:10000 x0=100*rand; y0=100*rand; for j=1:n

d=sqrt((a-x(j))^2+(b-y(j))^2); if d<10 p=p+1; break; end end end

if p==10000 m=m+1; end end n

m/300

程序多次运行结果分别为

n = 540

ans =

0.9567 ans =

0.9580 ans =

0.9530 ans =

0.9660 ans =

0.9570 ans =

0.9520 ans =

0.9610 ans =

0.9530 ans =

0.9480

附录五

问题二节点间连通图

A=load('Ashuju.txt'); x=A(:,1); y=A(:,2); for i=1:120 plot(x(i),y(i),'*')

text(x(i),y(i),num2str(i)) %在画出的点上加编号 hold on end

title('节点间的通信模型图') %title 后不能加分号 xlabel('x') ylabel('y') k=1;

edge=zeros(3,432) for i=1:120 for j=1:120

d(k)=sqrt((x(j)-x(i))^2+(y(j)-y(i))^2); if d(k)<=10&d(k)>0 line([x(i) x(j)],[y(i) y(j)]) hold on edge(1,k)=i; edge(2,k)=j; edge(3,k)=d(k); k=k+1; end end

end

n=120; juli=inf*ones(n, n); for i=1:n

juli(i, i)=0; end

for i=1:size(edge,2)

juli(edge(1, i), edge(2, i))=edge(3, i); end

[dis, path]=dijkstraf(juli, 1, 90)

求解结果

[dis, path]=dijkstraf(juli, 1, 10) dis =

36.1498

path =

1 80 64 25 10 [dis, path]=dijkstraf(juli, 1, 20) dis =

72.2226 path =