无线传感网络设计问题

/其次次个人赛论文姓名代码：88无线传感网络设计问题摘要本文针对无线传感网络节点的放置和节点间相互通信的路径选择问题做了深化的探讨。对于问题（1），本文依据概率论学问（当试验次数足够大时，可以近似认为事务发生的频率等于其概率）接受计算机仿真法，在监视区域内随机安放n个节点，组建无线传感网络，然后在监视区域随机取20000个点，通过检验这些点是否全部被所组建的无线传感网络覆盖来推断所组建的无线传感网络能否成功覆盖整个区域。进行多次仿真，统计并计算出由这n个节点组成的无线传感网络成功覆盖整个区域的频率，将此频率和95%比较，然后依据不同状况适当调整n的大小，最终找出能成功覆盖整个区域的概率在95%以上的最少节点数n为565个。对于问题（2），本文建立图论模型，在满足题设节点间通信条件的前提下，考虑通信的刚好性的时效性，以通信所用时间最短为选取最优通路的原则，先建立所给的120个节点间的距离矩阵，然后将距离矩阵中大于10的元素变为无穷大，从而将距离矩阵转化为带权邻接矩阵，最终用matlab软件求解，通过调用Dijkstraf算法，求解出10组节点间的通信通路，比如节点1和节点90间的通信通路为18064254665669313387156090（详见表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如何通信等。问题的分析依据查询的相关资料，无线传感网络设计中的节点放置和节点间通信问题是近今年的热门课题。由于地理条件的困难，一般状况下无线传感网络设计中的节点只能接受非匀整投放的方法。鉴于此，本文对题目中的问题做了如下分析：针对问题一：由于安放节点是随机的，某事务发生的概率可以用多次试验中该事务发生的频率代替,而两者均可用计算机仿真实现，因此可通过计算机不断产生随机数模拟节点安放和监视区域各点被覆盖的状况，再以题目中95%为约束，找出最优节点数。针对问题二：对于该问题，依据题目中所给的120个节点的坐标，很简洁求出各节点间的距离，由题设可知，一个节点不在另一个节点覆盖的范围之内，则两节点间不能干脆通信，要通过其它节点间接通信。在通过其它节点实现间接通信的过程中，确定会产生不同的通信通路，本文要做的是找出随意两点间的最优通信通路。这很简洁让人联想到图论模型最短路径的求法，于是可依据题设限制条件，将各点间的距离矩阵转化为带权邻接矩阵，通过matlab软件求解出各点间的最优通信通路。模型假设各节点的覆盖范围相同且稳定，不受天气及电磁干扰；任何节点和其覆盖范围内的节点间的通信强度相同；节点间的通信距离和通信所用的时长成正比。符号及变量说明：每次仿真随机产生的节点数；N：每次安放好节点后在监视区域内随机取的检验点个数；：监视区域内第i个随机点和第j个节点间的距离（i=1,2…N；j=1，2…n）；：第i个监测点和n个节点的距离最小值(i=1,2…N)；：每个节点的覆盖半径，r=10；T；仿真次数；：可以成功覆盖整个监视区域的仿真次数；：仿真中能成功覆盖整个监视区域的频率；：n个节点成功覆盖整个监视区域的概率；：问题2中所给120个点中第i个点和第j个点之间的距离（i，j=1,2…120）；：问题2中所给120个点之间的距离矩阵；：问题2中所给120个点中第i个点和第j个点之间通信路径权值（i，j=1,2…120）；：问题2中所给120个点之间的带权邻接矩阵；：第i个节点域其他节点距离的最小值（i=1,2…n）；模型的建立和求解5.1对于问题一的模型建立和求解查阅相关文献得知，无线传感网络中的节点安放是非匀整的，本文建立仿真模型，通过计算机在监视区域内随机产生n个节点来模拟节点的非匀整安放依据概率论学问：当试验次数足够大时，可以近似认为事务发生的频率等于其概率，于是可通过计算机在已将安放好节点的监视区域内随机产生N个检验点，并求出这N个点和各节点间的距离然后选出每个检验点和n个节点的距离最小值，依据题设节点间的通信条件，将和覆盖半径r比较，对于全部的i=1,2……N(N取足够大)，若满足<r则可以认为这n个节点组成的无线通信网络可以成功将监视区域覆盖，否则则认为没有成功覆盖。对上述过程进行T次仿真,统计能成功覆盖整个监视区域次数t，并计算出相应的频率f,当T取足够大时，可以认为这n个节点能成功覆盖整个监视区域的概率依据题目要求，比较p和95%的大小若则增大n值；反之则减小n值，再重复上述仿真过程，直至找出时的最小n值。仿真算法流程图如下：初始化系统状态手动调整n值N仿真次数到了吗？求频率，等于95%吗在监视区内随机产生n个节点Y在已经安放好节点的区内随机取检验点频数增加YN检验点被覆盖了吗？N检验次数到了吗？本文仿真程序相应的参数为：T=1000N=20000（详见附录二第一题程序），通过不断手动调整n的大小，最终找出能成功覆盖整个区域的概率在95%以上的最少节点数为565个。5.2对于问题二模型的建立和求解依据题意，两节点间能干脆相互通信的条件为<r否则要通过其它节点间接进行通信，在通过其它节点实现间接通信的过程中，确定会产生不同的通信通路，本文要做的是找出随意两点间的最优通信通路。于是本文建立图论模型，考虑到通信的时效性和刚好性，以通信所用时间最短为选取最优通路的原则，并依据本文条件假设3（节点间的通信距离和通信所用的时长成正比），将通信时间最短转化为路径最短，接受Dijkstraf算法求出随意给定的两点间的最优通信通路。Matlab程序求解步骤如下：Step1：求出120点两两之间的距离矩阵；Step2：将D中大于r的元素变为，将距离矩阵D转化为带权邻接矩阵；Step3：接受Dijkstraf算法，将W带入其中，计算出随意给定两节点间的最优通信通路。所得的十组节点间的最优通信通路如表1：表11-2111107704195102183610410321-101806425101-201115621064541119899201-30111562106301-4018055401-50180501-601806425466566931338715601-70111107701-801801-9018064254665669313387156090模型的评价和改进6.1模型的评价6.1.1优点对于问题1本文在题目信息和查阅相关资料的基础上，用计算机仿真法模拟无线网络节点的不规则放置和检验无线网络的覆盖率，充分利用计算机的优势，化繁为简，以频率代替概率，得出的结论可信度高。在仿真过程中，对重要参数调整问题，本文接受手动调整法，这样可以避开计算机仿真次数过多，程序运行时间过长的问题，既可以节约时间又可以较精确推断最志向的n值。求解问题2时，本文在考虑通信的时效性和刚好性的基础上，建立图论模型，并以通信时间最短为最佳路径选取依据，又通过合理假设将时间最短转换成距离最短，这样就能和Dijkstraf算法完备结合，也能很便捷的求出题目要求的制定两点间的通信通路。6.1.2缺点计算机仿真次数有限，所得结果不行避开会有确定误差在建立仿真模型，检验监视区域是否完全被覆盖时，只考虑了区内点的被覆盖的概率，没有考虑全部节点间是否能实现相互通信。6.2模型的改进本文通过分析对问题1的中的仿真模型进行改进。在每次随机布置好节点后，先通过节点间的距离对这n个节点布置合理性进行初步检验，以一个节点和其他各节点距离的最小值为推断依据，当>r时，则该节点和其他节点不能实现通信，应当讲该节点剔除。修改后测程序见附表二。讲过修改后，得到能成功覆盖整个区域的概率在95%以上的最少节点数为571个。模型的推广和应用本文所建立的仿真模型，用到了随机抽取和循环迭代思想，可广泛应用于估计某些事务可能发生的概率。本文建立的图论模型也可广泛应用到无线设备比如手机的信号传递路径选取上。参考文献：[1]陶丹，马华东，刘亮无线传感器网络节点部署问题探讨,北京100876[2]茆诗松，程依明，濮晓龙.概率论和数理统计教程[M].北京：高等教化出版社.2009；[3]刘卫国主编MATLAB程序设计教程(其次版)[M].水利水电出版社出版社.2010；附录一：120个节点的坐标表节点标号XY节点标号XY节点标号XY节点标号XY1575831633613295917444295743285962477192412533412336437635043933921431683422136456439495515526735694365562595727663043680836647259679871575377613678064977844875523888946810969810809753039259569123399889106528406245706370100159511556341707071399101459012416142454272818910270821336204335973431410390781472244475417417251048478151610453591758055105207016854946563076456110640711786904727927792401075570187590489290787822108595193220492558798945109731820592504452805151110222821163551580814090111178022256652173382654911250102372453905837671135520246833542574843098114872225613555584785263411572982637785695286289911655792748465787728725811772288131586888882963118852029239059302889408311935503035666099904111201068附录三：第一题程序clcclearn=565;%设定n个节点T=1000;%随机设定节点的次数N=20000;%检验覆盖率的仿真次数r=10;%覆盖半径t=0;%被完全覆盖次数fori=1:Tm=0;%覆盖的点的个数，每次循环初始化为零Q=0;%区域覆盖率，每次循环初始化为零fori=1:n%在监视区域内随机产生n个节点A(i)=100*rand;%横坐标B(i)=100*rand;%纵坐标endfori=1:N%在监视区域内随机取N个点看其是否被覆盖x=100*rand;%横坐标y=100*rand;%纵坐标fori=1:nd(i)=sqrt((x-A(i)).^2+(y-B(i)).^2);%计算该点和n个节点的距离endifmin(d)<=r%推断该点是否被覆盖m=m+1;endendifm==N%推断是否被完全覆盖t=t+1endendp=t/T%监视区域被完全覆盖的频率其次题程序clcclearx=load('x.txt');y=load('y.txt');%输入节点坐标fori=1:120forj=1:120d(i,j)=sqrt((x(i)-x(j)).^2+(y(i)-y(j))^2);%求出各节点间的距离矩阵ifd(i,j)>10%将距离矩阵转化为带权邻接矩阵d(i,j)=inf;endendend[dis,path]=dijkstraf(d,1,5)%调用Dijkstraf算法第一题改进后的程序clcclearn=565;%设定n个节点t=500;%随机设定节点的次数N=5000;