第二次个人赛论文
无线传感网络设计问题
摘要
对于一些频频发生的自然灾害，比如地震、旱灾等，人们通过建立无线传感网络的方法来传递信息，这样，人们就能够准确而又及时地掌握险情的发展情况，减少灾害带来的损失。本文就是针对如何确定放置节点的个数，怎么建立两个网络节点之间的通信通路这两个问题进行了深入的研究。
对于问题一：我们采用的方法是对本问题所处的数学情景进行模拟。用Matlab软件，对此问题进行编程。通过不断改变程序中的节点的个数，并且观察程序的运行结果，由于，这是一个模拟实验，存在一定的误差。所以，我们规定相对误差为0.5%，故当运行结果为0.95?0.00475时，我们就可以认为此时的节点个数就是本问题的解。最后我们通过不断改变程序运行，计算结果的检验与改进，得到了如下结论：当监视区域为边长b=100（长度单位）的正方形且每个节点的覆盖半径为r=10（长度单位）时，至少需要放置518个节点，才能使得成功覆盖整个区域的概率在95%以上。
对于问题二：本问题要求我们建立任意两点之间的通信通路。根据附录一的各个点的坐标，又考虑到每个节点的覆盖半径为r=10（单位长度），所以可以用Matlab软件画出各个节点之间的通信通路，这通信通路图反应的时任意两个节点之间所以的可能路径。但考虑到信息传递的时间需要尽可能的短，所以我们对两个节点间的所有通信通路进行筛选，选出其中的最短的通信通路。我们处理两点间最短通信通路时，采用的方法是利用Matlab软件进行编程，运用Dijkstra算法。比如节点1与节点90的通信通路是：1-80-64-25-10-65-66-92-13-3-87-15-60-90。
在模型改进方面，我们运用了概率论及统计学的相关知识。对于改进方法（1）：把问题一模型的模拟实验次数提高到原先设置的10倍，或是选取正方形监视区域内随机均匀分布的点的个数为原来的100倍，这种做法需要的计算机配置比较高。对于改进方法（2）：通过多次运算求解，取n的平均值的方法来提高结果的准确度。
本文所建立模型的最大优点是建模过程清晰、易懂，模型的适用范围比较广；最大缺点是问题一求解过程采用的是随机模拟，所求结果不是一个准确值。
关键词： 无线传感网络； 最短路径； 设计问题； Dijkstra算法
1
一、 问题的提出和重述
1.1问题的提出
大气污染所引起的地球气候异常，导致地震、旱灾等自然灾害频频发生，给人民的生命财产造成巨大损失。为了应对这种情况，建立无线传感网络能够使人民准确而及时地掌握险情的发展情况，为有效的抢险救灾创造有利条件。这是一种简单有效且不是很昂贵的方法。但是，一个网络节点的覆盖范围是有限的，又考虑节点的信号传输的特殊性。所以，当需要对一片大型区域实行监控时，往往要求安装多个节点。因此，我们需要知道，该如何在该监视区域内安装网络节点和怎样决定安排的节点的数量。 1.2问题的重述
问题1：在设计传感网络时，为了使得成功覆盖整个监视区域的概率在95%以上，已知节点的覆盖半径为r=10（长度单位），监视区域为边长b=100（长度单位）的正方形。那么，设计传感网络的专家应该至少需要放置多少个节点。
问题2：由于每个节点的覆盖范围的限制，各节点只能与覆盖范围内的节点进行通信，若一个节点需要跟不在其覆盖范围内的节点通信，需要其他节点转发。由此，要求设计一种节点间的通信模型。这种模型可以知道任意两个点之间的通信通路。
二、 问题的分析
针对问题一：
对于该问题，我们从另一个角度理解。假设放置的节点数量为n个，当在该监视区域内设置这些节点时，设试验次数为w，那么这些节点可以成功覆盖整个监视区域的次数可达到0.95w次以上。再考虑到每个节点的覆盖半径均为10（长度单位），我们可以由此利用Matlab进行编程、验算、求解，当试验次数足够大时，我们就可以较为准确地求出至少需要放置的节点的数量。
针对问题二：
对于该问题，由于两节点之间信号传输的特殊性，即当一节点不在另一节点的覆盖范围内时，需要通过其他节点转发。而第一问已经给出每个节点的覆盖范围，又附录一给出了120个节点的坐标。因此，通过Matlab软件，运用Dijkstra算法，就可以求出该监视区域内任意两个节点之间的最短通信通路。
三、 模型假设
1、 各个网络节点之间的信息传递工作始终保持正常，不会出现信息中断的情况。 2、 假设程序一计算出来的p值与题目所给的覆盖成功率的相对误差为0.5%。 3、 各个网络节点工作状态相同，即每个节点的覆盖半径始终为10（长度单位），信息传输能力相同。
四、 符号及变量说明
d：两个网络节点之间的距离；
aij：网络节点的坐标；
bij：正方形监视区域内的点的坐标；
2
xi：第i个网络节点的横坐标；
xj：第j个网络节点的横坐标； yi：第i个网络节点的纵坐标
yj：第j个网络节点的纵坐标；
p：成功覆盖整个区域的概率；
W：计算机模拟试验次数； n：网络节点的个数；
五、 模型的建立和求解
5.1.1对于问题一的模型建立和求解
根据题意，我们可以利用计算机对本问题的数学情景就行模拟，假设对于边长为b=100（长度单位）的正方形监视区域以及覆盖半径为10（长度单位）的节点，安装的节点的个数为n。我们提取这个区域内均匀分布的100?100即10000个点。为形象表示这一模型，我们画出简易示意图，如图一所示。
Y
图一 我们可以这样认为，当这些均匀分布的10000个点都在n个圆所形成的区域内，就可以认为成功覆盖了。规定计算机模拟次数w为1000次，通过模拟次数的不断增加，我们可以得到节点数为n时，成功覆盖整个区域的概率。由题目的条件，可以知道成功
3
0 X