第二次个人赛论文 姓名代码：88
无线传感网络设计问题
摘要
本文针对无线传感网络节点的放置和节点间相互通信的路径选择问题做了深入的研究。
对于问题（1），本文根据概率论知识（当试验次数足够大时，可以近似认为事件发生的频率等于其概率）采用计算机仿真法，在监视区域内随机安放n个节点，组建无线传感网络，然后在监视区域随机取20000个点，通过检验这些点是否全部被所组建的无线传感网络覆盖来判断所组建的无线传感网络能否成功覆盖整个区域。进行多次仿真，统计并计算出由这n个节点组成的无线传感网络成功覆盖整个区域的频率，将此频率与95%比较，然后根据不同情况适当调整n的大小，最后找出能成功覆盖整个区域的概率在95%以上的最少节点数n为565个。 对于问题（2），本文建立图论模型，在满足题设节点间通信条件的前提下，考虑通信的及时性的时效性，以通信所用时间最短为选取最优通路的原则，先建立所给的120个节点间的距离矩阵，然后将距离矩阵中大于10的元素变为无穷大，从而将距离矩阵转化为带权邻接矩阵，最后用matlab软件求解，通过调用Dijkstraf算法，求解出10组节点间的通信通路，比如节点1与节点90间的通信通路为 1 80 64 25 46 65 66 93 13 3 87 15 60 90（详见表1）。
最后，本文对问题（1）和问题（2）中的模型进行了评价，并对第一问中的仿真模型求解时只检验无线传感网络对整个监视区域是否完全覆盖，而没有考虑随机安放的节点间能否相互通信的问题进行了进一步讨论，并提出以节点间距离的最小值为判断依据，在原覆盖的基础上剔除一些与其他节点间最小距离大于10的节点的修正方案。并对模型进行了简单的推广。
关键词： 计算机仿真；图论模型；概率论；Dijkstraf算法
一、 问题的提出和重述
1.1问题的提出
大气污染所引起的地球气候异常，导致地震、旱灾等自然灾害频频发生，给人民的生命财产造成巨大损失。因此，不少国家政府都在研究如何有效监测自然灾害的措施。在容易出现自然灾害的重点地区放置高科技的监视装置，建立无线传感网络，使人们能准确而及时地掌握险情的发展情况，为有效地抢先救灾创造有利条件。科技的迅速发展使人们可以制造不太昂贵且具有通讯功能的监视装置。放置在同一监视区域内的这种监视装置（以下简称为节点）构成一个无线传感网络。
如果监视区域的任意一点都处于放置在该区域内某一节点的监视范围内，则称节点能覆盖该监视区域。研究能确保有效覆盖且数量最少的节点放置问题显然具有重要意义。
1.2问题的重述
图1 无线传感网络覆盖示意图 图1中，叉形表示一个无线传感网络节点，虚线的圆形区域表示该节点的覆盖范围。可见，该无线传感网络节点完全覆盖了区域B，部分覆盖了区域A。
网络节点间的通信设计问题是无线传感器网络设计的重要问题之一。如前所述，每
个节点都有一定的覆盖范围，节点可以与覆盖范围内的节点进行通信。但是当节点需要与不在其覆盖范围内的节点通信时，需要其它节点转发才可以进行通信。
图2 无线传感网络节点通信示意图
图2所示，节点C不在节点A的覆盖范围之内，而节点B在A与C的覆盖范围之内，因此A可以将数据先传给B，再通过B传给C。行成一个A－B－C的通路。
问题1：在一个监视区域为边长b=100(长度单位)的正方形中，每个节点的覆盖半径均为r=10(长度单位)。在设计传感网络时，需要知道对给定监视区域在一定的覆盖保证下应放置节点的最少数量。对于上述给定的监视区域及覆盖半径，确定至少需要放置多少个节点，才能使得成功覆盖整个区域的概率在95%以上？
问题2：在1所给的条件下，已知在该监视区域内放置了120个节点，它们位置的横、纵坐标如表1所示。请设计一种节点间的通信模型，给出任意10组两节点之间的通信通路，比如节点1与节点90如何通信等。
二、 问题的分析
根据查询的相关资料，无线传感网络设计中的节点放置和节点间通信问题是近今年的热门课题。由于地理条件的复杂，一般情况下无线传感网络设计中的节点只能采用非均匀投放的方法[1]。鉴于此，本文对题目中的问题做了如下分析：
针对问题一：
由于安放节点是随机的，某事件发生的概率可以用多次实验中该事件发生的频率代替[2],而两者均可用计算机仿真实现，因此可通过计算机不断产生随机数模拟节点安放和监视区域各点被覆盖的情况，再以题目中95%为约束，找出最优节点数。
针对问题二：
对于该问题，根据题目中所给的120个节点的坐标，很容易求出各节点间的距离，由题设可知，一个节点不在另一个节点覆盖的范围之内，则两节点间不能直接通信，要通过其它节点间接通信。在通过其它节点实现间接通信的过程中，肯定会产生不同的通信通路，本文要做的是找出任意两点间的最优通信通路。这很容易让人联想到图论模型最短路径的求法，于是可根据题设限制条件，将各点间的距离矩阵转化为带权邻接矩阵，通过matlab软件求解出各点间的最优通信通路。
三、 模型假设
1、 各节点的覆盖范围相同且稳定，不受天气及电磁干扰； 2、 任何节点与其覆盖范围内的节点间的通信强度相同； 3、 节点间的通信距离与通信所用的时长成正比。
四、 符号及变量说明
n：每次仿真随机产生的节点数；
N：每次安放好节点后在监视区域内随机取的检验点个数；
dij：监视区域内第i个随机点与第j个节点间的距离（i=1,2…N；j=1，2…n）；
dimin：第i个监测点与n个节点的距离最小值(i=1,2…N)； r：每个节点的覆盖半径，r=10； T；仿真次数；
t：可以成功覆盖整个监视区域的仿真次数； f：仿真中能成功覆盖整个监视区域的频率；
p：n个节点成功覆盖整个监视区域的概率；
； Dij：问题2中所给120个点中第i个点与第j个点之间的距离（i，j=1,2…120）
D：问题2中所给120个点之间的距离矩阵；
Wij：问题2中所给120个点中第i个点与第j个点之间通信路径权值（i，j=1,2…120）； W：问题2中所给120个点之间的带权邻接矩阵；
； limin：第i个节点域其他节点距离的最小值（i=1,2…n）
五、 模型的建立和求解
5.1对于问题一的模型建立和求解
查阅相关文献得知，无线传感网络中的节点安放是非均匀的[1]，本文建立仿真模型，通过计算机在监视区域内随机产生n个节点(Xj,Yj)来模拟节点的非均匀安放根据概率论知识：当试验次数足够大时，可以近似认为事件发生的频率等于其概率，于是可通过计算机在已将安放好节点的监视区域内随机产生N个检验点(xi,yi)，并求出这N个点与各节点间的距离
然后选出每个检验点与n个节点的距离最小值dimin，根据题设节点间的通信条件，将dimin与覆盖半径r比较，对于所有的i=1,2……N(N取足够大) ，若满足
dimin 则可以认为这n个节点组成的无线通信网络可以成功将监视区域覆盖，否则则认为没有成功覆盖。对上述过程进行T次仿真,统计能成功覆盖整个监视区域次数t，并计算出相应的频率f,当T取足够大时，可以认为这n个节点能成功覆盖整个监视区域的概率 根据题目要求，比较p与95%的大小 若 则增大n值；反之则减小n值，再重复上述仿真过程，直至找出p?95%时的最小n值。 仿真算法流程图如下： 初始化系统状态 手动调整n值 N 仿真次 数到了吗？ 求频率，等于95%吗 在监视区内随机产生n个节点 Y 在已经安放好节点的区内随机取检验点 频数增加 Y N 检验点被 覆盖了吗？ N 检验次数 到了吗？ 本文仿真程序相应的参数为：T=1000 N=20000（详见附录二第一题程序），通过不断手动调整n的大小，最后找出能成功覆盖整个区域的概率在95%以上的最少节点数为565个。 5.2对于问题二模型的建立和求解 根据题意，两节点间能直接相互通信的条件为 Dij