《无线传感器网络》word版.doc

第一次个人赛论文 姓名代码：89无线传感网络设计问题摘要本文通过研究无线传感网络的覆盖问题和节点的通信模型设计，建立无线传感网络，可以准确而及时地掌握险情的发展情况。针对问题一，在给定区域面积和节点覆盖半径，且要求必须覆盖整个区域的前提下，通过随机模拟确定最少的节点数。首先通过蜂窝网格法，分析得到理论上覆盖整个区域所需最少的节点数为45个。然后通过软件在监视区域内产生N个随机测试点，再产生随机均匀分布的M个节点，观察这些节点圆是否已完全覆盖这些测试点，并保证覆盖整个区域的概率在95%以上,利用matlab通过500次模拟得到。考虑到随机产生的测试点不稳定，可以做进一步优化，使得这些测试点完全转化为区域内的固定点，当各点间隔趋于无穷小时，便可均匀覆盖整个区域，再分析节点圆覆盖整个区域的概率。通过对这两种方法进行对比，得出后者更优，最后确定至少为535个。针对问题二，设计了两种节点间的相互通信模型。已知每个节点覆盖半径，且节点只能与覆盖范围内的节点进行通信，即两节点之间的距离要小于半径。方法一把能相互通信的点连线，可以得到节点间的通信路径图，通过该图可以找出任意两个节点间的通信路径，并给出了十组任意节点之间的通路。方法二在节点通信路径图的基础上进行优化，通过Dijkstra算法求最短路径，准确快速实现任意两个节点之间的最短通路及最距离大小。通过对这两种方法的对比分析，可知方法一通信路径并不唯一，对于距离较短，节点少时，简单易用，但当通信距离较大、节点多时，不易观察，且计算路径繁琐。方法二计算准确快速，适用性更广。因此，Dijkstra算法更适用于大范围的无线传感网络设计。最后，本文对采用的模型方法进行了分析，并提出了适当的改进方案。关键词：随机模拟；节点通信；Dijkstra算法一、 问题的提出和重述1.1问题的提出大气污染所引起的地球气候异常，导致地震、旱灾等自然灾害频频发生，给人民的生命财产造成巨大损失。因此，研究如何有效监测自然灾害的措施十分必要。在容易出现自然灾害的重点地区放置高科技的监视装置，建立无线传感网络，使人们能准确而及时地掌握险情的发展情况。如果监视区域的任意一点都处于放置在该区域内某一节点的监视范围内，则称节点能覆盖该监视区域。研究能确保有效覆盖且数量最少的节点放置问题显然具有重要意义。图1 无线传感网络覆盖示意图如图1所示，叉形表示一个无线传感网络节点，虚线的圆形区域表示该节点的覆盖范围。该无线传感网络节点完全覆盖了区域B，部分覆盖了区域A。网络节点间的通信设计问题是无线传感器网络设计的重要问题之一。节点可以与覆盖范围内的节点进行通信。但是当节点需要与不在其覆盖范围内的节点通信时，需要其它节点转发才可以进行通信。图2 无线传感网络节点通信示意图图2所示，节点C不在节点A的覆盖范围之内，而节点B在A与C的覆盖范围之内，因此A可以将数据先传给B，再通过B传给C，行成一个ABC的通路。1.2问题的重述查找相关资料，建立数学模型解决以下两个问题：1、在一个监视区域为边长b=100(长度单位)的正方形中，每个节点的覆盖半径均为r=10(长度单位)。对于上述给定的监视区域及覆盖半径，确定至少需要放置多少个节点，才能使得成功覆盖整个区域的概率在95%以上？2、在1所给的条件下，已知在该监视区域内放置了120个节点，它们的横、纵坐标如附表1所示。设计一种节点间的相互通信模型，并给出任意10组两节点之间的通信通路。二、 问题的分析通过建立无线传感网络，可以准确而及时地掌握险情的发展情况。因此，本文研究的是传感网络的覆盖问题，确定设置多少个节点使得成功覆盖概率达95%，同时设计一个合理有效的节点通信模型，使得整个无线传感网络可以准确快速通信，且经济实用。针对问题一，在给定区域面积和节点覆盖半径的前提下，需要确定至少需要放置多少个节点，才能使得成功覆盖整个区域的概率在95%以上。在必须覆盖整个区域的要求下，可以通过仿真模拟来确定最少的节点数，并计算覆盖效率（覆盖效率越大越经济）。首先通过蜂窝网格法1，可以分析理论上覆盖整个区域所需最少的节点数。通过蒙特卡洛模拟编程2实现，在监视区域内产生随机均匀分布的N个测试点，再产生随机均匀分布的M个节点，观察这些节点是否已完全覆盖这些测试点，并进行多次模拟，保证覆盖整个区域的概率在95%以上。考虑到随机产生的测试点不稳定，我们可以进一步优化，使得这些测试点转化为区域内的固定点，各点间隔趋于无穷小时，便可均匀覆盖整个区域，再分析节点覆盖整个区域的概率。针对问题二，设计一种节点间的相互通信模型。已知每个节点都有一定的覆盖范围，根据节点只能与覆盖范围内的节点进行通信，即两节点之间的距离要小于半径，把能相互通信的点连线，可以得到节点间的通信路径图，通过该图可以找出任意两个节点间的通信路径。但此方法当通信距离较大、节点多时，不易观察，且手工计算路径繁琐。因此，在节点通信路径图的基础上进行优化，通过Dijkstra算法（以下简称D算法）可以准确快速实现任意两个节点之间的最短通路及最短路径大小，比如节点5到其余任何点的最短通路。三、 模型假设1、 节点装置在监视区域内是呈均匀分布随机放置的。2、 定义覆盖效率为监视区域除以各节点能覆盖的面积总和；3、 不考虑节点周围环境对通信范围的影响。4、 假设在两个节点覆盖圆临界位置（相切处）不可通信。四、 符号及变量说明:随机测试点数；:节点数； :随机模拟次数；:覆盖整个区域的概率；: 覆盖效率；：正方形小网格边长；五、 模型的建立和求解5.1针对问题一的求解5.1.1理论最少节点数的求解 根据数学定理：如果3个半径相同的圆两两相交，且覆盖面积最大，则三圆相交于一点，且三个圆心围成等边三角形。如图（1）所示，根据此定理，在的监视范围内平铺，利用CAD画图得到图（2）。图（1） 图（）在此平铺状态下，即为蜂窝网格法，得到最少的节点数为45个，其覆盖效率为。此状态在随机模拟下出现的概率几乎为零，因此要使成功覆盖整个区域的概率在95%以上，节点数远大于45个。5.1.2 随机测试点求最少节点数通过在监视区域内产生个均匀分布随机测试点，再往监视区域内随机放置个节点，若这个节点能完全覆盖这个测试点，则认为该区域被完全覆盖，通过次模拟，保证覆盖整个区域的次数至少为，以此求得最小的值。通过编程实现模拟500次，得到表（）和图（），并解得当时，左右。由表（）可以看出值与值并不成比例关系，值不稳定，难以确定具体为多少时，概率，因此，该方法仍有待进一步优化。N530531532533534535536537538539P0.94330.92670.93000.96330.93670.93330.95670.94670.96000.9533表（）十组值对应的值 图（）随机测试点模拟图5.1.3 固定测试点求最少节点数 对于的覆盖区域，分成面积为的正方形小网格，并赋予每个小网格为0值，当时，每个小网格趋向于点，网格数也就越多。为便于计算，这里取1，以网格中心点代表整个网格，当该中心点到随机分布的任意一个节点的距离小于半径时，网格被赋值为1。按此循环，当每个网格均被赋值为1时，即表示节点覆盖了整个区域，达到要求。通过matlab编程模拟500次，得到表（2）和图（4）。通过对表（1）与表（2）的对比分析可知，值更为稳定，通过线性拟合图（5）也可知用固定点模拟的方法更好。综上，在一定范围内，得出在时，符合要求。N530531532533534535536537538539P0.94170.93330.93000.94330.94270.95000.95000.95370.97330.9667表（2）十组值对应的值 图（4）固定测试点模拟图图（5）两种方法线性拟合对比图5.2针对问题二的求解5.2.1 可通信节点路径分布图的设计已知每个节点都有一定的覆盖范围（），节点只能与覆盖范围之内的节点进行通信，任意两个节点之间的欧式距离可表示为： 所以当的两个节点之间才可以进行通信，因此，通过matlab编程（附录程序三）将120节点中所有的两节点之间用直线连接，得到节点通信路径图，如图（6）所示：图（6）节点通信路径图通过观察此节点通信图，可以知道任意两节点之间的通信通路，任取10组节点，找出其通信路径，并计算其通信距离，如下表（3）所示，并通过图（7）可直接观测其通信通路：序号起始节点终止节点 通信路径 通信距离16087 601587 16.292673 64373 16.5139310 93666510 27.434 14 28 14928 12.795816 87516 13.6468012 805512 16.5674118 419510818 20.0886211 62511 11.40949106 498830106 20.18109954 9998710554 29.76表（3）：10个任意节点的通信路径及通信距离图（7）：上述10个节点的通路图通过直接观测通信图，可知通信路径并不唯一，对于距离较短，节点少时，简单易用，但是当通信距离较大、节点多时，则不易观察，且计算繁琐，不宜采用。因此下面通过适当算法来更准确快速实现通信图的设计。5.2.1 Dijkstra算法通信路径的设计D算法思路3：采用标号作业法,每次迭代产生一个永久标号, 从而生长一颗以为根的最短路树,在这颗树上每个顶点与根节点之间的路径皆为最短路径。该算法核心是求得邻阶矩阵，计算某点到其余点的距离，若其余某点在该点的通信范围内，则。反之，。本文可以得到一个邻阶矩阵，调用D算法程序，实现通信路径及距离的计算。为方便比较，仍取上述表（3）中的起始节点和终止节点，通过matlab编程得到图（8）D算法最短通信路径及距离分布图图（8）D算法最短通信路径及距离分布图通过图（7）和图（8）的对比分析，其通信路径及距离是完全吻合的，但用D算法明显更为优越，能够快速准确地给出任意两节点之间的最短通信路径以及此时的最短通信距离，且误差很小。六、 模型的评价和改进6.1模型的评价6.1.1优点(1)本文通过多次模拟来求解全部覆盖的概率，方法实用简单，容易编程实现。(2)运用D算法求解最短通信路径和距离时，准确快速可靠，且容易编程实现，易于推广。 （3）通过对覆盖效率的计算，便于经济、实用方面的分析。6.1.2缺点(1) 通过随机模拟不可避免会有误差，若模拟次数不够多，造成的误差也大。每次的模拟会有不同的在微小范围内浮动值。(2) 软件编程时计算量大，运算时间长。6.2模型的改进从第一问的覆盖效率可知，效率偏低，因此十分有必要提高其覆盖效率，可以对覆盖区域进行全面了解后，通过精确计算确定各个节点位置，减少随机模拟的误差，对于重复覆盖频率高的地区减少节点数，对于重复覆盖频率很低的地区增加节点数，使其均匀化，从而增加了覆盖效率，也更加经济。七、 模型的推广和应用 本文对研究无线传感网络的覆盖问题和节点的通信模型设计进行了讨论，建立无线传感网络，可以准确而及时地掌握险情的发展情况，在森林防火、灾区空投物资、战场空投等方面都具有一定的指导作用。参考文献：1陆克中、毛睿等 基于蜂窝结构的传感器网络覆盖问题求解算法 计算机研究与发展学报 第3期：80-84，2012；2薛山 MATLAB基础教程 清华大学出版社 2011-03-01;3Dijkstra最短路径算法（百度文库）链接:/view/680ebde29b89680203d82598.html附录： 附表1 120个节点的坐标表节点标号XY节点标号XY节点标号XY节点标号XY1575831633613295917444295743285962477192412533412336437635043933921431683422136456439495515526735694365562595727663043680836647259679871575377613678064977844875523888946810969810809753039259569123399889106528406245706370100159511556341707071399101459012416142454272818910270821336204335973431410390781472244475417417251048478151610453591758055105207016854946563076456110640711786904727927792401075570187590489290787822108595193220492558798945109731820592504452805151110222821163551580814090111178022256652173382654911250102372453905837671135520246833542574843098114872225613555584785263411572982637785695286289911655792748465787728725811772288131586888882963118852029239059302889408311935503035666099904111201068%程序（一）：随机模拟覆盖的概率clearclcfor n=530:540;%设置节点数T=10000;m=0;for k=1:500 %模拟次数x=100*rand(n,1); %产生n个圆心坐标y=100*rand(n,1);p=0;c=0;for i=1:T x0=100*rand; %产生T个随机点坐标 y0=100*rand; for j=1:n if (x0-x(j)2+(y0-y(j)2100 p=p+1; break; end end end if p=T %已全部覆盖 m=m+1; endendc=m/300c=0;end%程序（二）：固定点覆盖的概率%clearclcm=0;h=1;%间隔c=100;K=500;%模拟次数P=0;%覆盖率%产生c*c个固定点坐标，c=100；x=;for i=0:99x(1+100*i):(100+100*i),1)=0.5+i;endfor i=1:100 Y(i,1)=i-0.5;endy=;for i=1:99 y(1+100*i):(100+100*i),1)=Y;end for n=530:540for k=1:K f=0; x0=100*rand(n,1); %产生n个节点圆心坐标 y0=100*rand(n,1); p=0; for i1=1:c*c/h for p=1:n if (x(i1)-x0(p)2+(y(i1)-y0(p)2100 f=f+1; break; end end end if f=(c*c) m=m+1; endendP=m/Km=0;end%程序（三）：通信路径图clearclcX=load(shuju.txt);x0=X(:,2);y0=X(:,3);plot(x0,y0,.)te