无线传感网络设计问题 (2).doc

第二次个人赛论文 姓名代码：49无线传感网络设计问题摘要本文主要是针对无线传感网络构建中的节点放置问题进行了研究，考虑到节点的覆盖半径和通信通路的必要条件，对固定区域内节点优化放置问题及节点间的较优的通信通路进行了模型设计。对于问题一，鉴于题目中对固定区域完全成功覆盖率的概率要求，我采用了蒙特卡洛算法，并用计算机进行了仿真模拟并进行大量实验，可得到不同节点时的完全成功覆盖的不同概率，用逼近法得到节点个数为442个时成功覆盖的概率达到95%以上，由概率统计相关知识可得当试验次数足够多时，取其中节点个数来表示需求节点的最少个数具有一定合理性。对于问题二，在已知区域和节点覆盖半径条件下，对给定的120个节点设计通信通路，我首先通过可通信条件对节点通路进行限制并做出通路图，再由算法以节点间距离为边权值，对任意节点间的通信通路进行了优化，如节点1到节点90的最优通信路径为：180642546656693139313387156090，且最短通信距离为101.0360。关键词： 通信模型；算法优化；成功覆盖率一、 问题的提出和重述1.1问题的提出大气污染所引起的地球气候异常，导致地震、旱灾等自然灾害频频发生，给人民的生命财产造成巨大损失。因此，在容易出现自然灾害的重点地区放置高科技的监视装置，建立无线传感网络，使人们能准确而及时地掌握险情的发展情况，为有效地抢先救灾创造有利条件。所以在构建无线传感网络时，在监视区域内的研究节点的优化放置以确保有效覆盖及节约成本等具有重要意义。还有由于节点只可以与其覆盖范围内的节点进行通信，故网络节点间的通信设计问题也成为无线传感网络设计的重要问题之一。1.2问题的重述问题1：在一个监视区域为边长b=100(长度单位)的正方形中，每个节点的覆盖半径均为r=10(长度单位)。在设计传感网络时，需要知道对给定监视区域在一定的覆盖保证下应放置节点的最少数量。对于上述给定的监视区域及覆盖半径，研究确定至少需要放置多少个节点，才能使得成功覆盖整个区域的概率在95%以上。 问题2：在1所给的条件下，已知在该监视区域内放置了120个节点，它们位置的横、纵坐标如表1所示。请设计一种节点间的通信模型，给出任意10组两节点之间的通信通路，比如节点1与节点90如何通信等。二、 问题的分析 对于固定区域内节点的优化放置问题 ，考虑到每个节点的覆盖能力，是涉及节点在区域中分布及其覆盖比例的概率问题；而对于节点间通信网络的构建，需要考虑节点只能与其覆盖范围内的节点进行通信，即可对各可通信点连线，从而得出任意节点间的通信通路。针对问题一：在已确定的监视区域中，每个节点的覆盖范围已知，由于要考虑成功覆盖整个区域的概率问题，所以可以对节点的放置采用随机仿真模拟进行实验，通过计算机的大次数模拟，可得到基本正确成功覆盖整个区域的概率。针对问题二： 要求在问题一的条件下，为已给出的120个节点设计节点间的通信模型，鉴于每个节点只能与其覆盖范围内的节点进行通信，故可考虑对给出节点满足通信条件的节点进行作图，由启发式算法即可得到任意节点的通信通路，不过考虑实际运用，可以通信距离较短为优对节点通路进一步优化。三、 模型假设1、 监视的节点装置工作稳定，不会突然失效；2、 所有节点间通信皆满足该节点覆盖范围内可通信；计算机仿真模拟次数无限大时，其频率可表示概率；（不需要）（假设质点假设地面平坦）四、 符号及变量说明：放置的节点数目；：节点位置的坐标， ；：节点位置的坐标， ；：节点到节点的距离， ；：节点间的通信半径；五、 模型的建立和求解5.1对于问题一的模型建立与求解5.1.1模型建立（无法用规划做只能用蒙特卡洛模拟）根据对成功覆盖整个区域的概率要求的分析，可运用蒙特卡洛仿真模拟的方法，将节点在区域内的位置分布转化为随机性问题，再通过大量的计算机模拟即可得到不同个数的节点的概率分布。蒙特卡洛的启发式算法可表述如下：用区域内均匀随机产生的无穷多个点的集合来表示区域Q;：进行次实验，用均匀随机产生的个节点对集合进行检验；：检验集合是否被个节点覆盖的标准为对于中的每个点都能在个节点中找到与之距离小于节点通信半径的节点；：对次试验中通过检验的次数进行统计,记为 ;：对次试验的节点个数进行比较，取其中的最小值；：当试验次数m足够大时，则成功覆盖整个区域的概率可表示： （1）5.1.2模型求解 由建立模型编写程序进行计算机模拟（程序见附录一），当试验次数时，可得到不同节点个数时的完全成功覆盖的概率部分结果如下表：表1 节点个数与完全成功覆盖率节点个数n439441442443445成功覆盖概率94.98%94.97%95.12%95.14%95.03%由上表可知当节点个数最少取442个左右时可保证完全成功覆盖监视区域的概率达到95%以上。5.1.3模型检验与分析由于计算机模拟的计算效率问题，用10000个点的集合来近似表示区域Q，作100次试验时得到如上数据带有一定的不稳定性，但根据概率统计的相关知识，当用集合S趋于无穷多的点来表示区域Q，试验次数尽可能大时，可以得到较为可信的概率结果。 5.2对于问题二的模型建立与求解设节点横纵坐标分别用表示，用表示节点间距离，则任意节点间距离可表示为： （2）由于节点只可以与其覆盖范围内的节点进行通信，当节点覆盖半径时，节点间可通信条件为： （3）对于给出的120个节点，可对其所有可通信的节点进行连线 ，由Matlab作图如下（程序见附录二）： 则由节点通路图即可得到一种简单的节点间通信模型： 表 2：节点1到个别节点可通信通路起始节点终止节点通信路径1761115761761805076110711151071107180507651071621805076562186111562106268945618486159180642546656692931359113180642546656692931319018063642546651366924338715609019018064251665669373714365871587156090但由此得到的两节点间的通路不唯一，且无法判断是否为最优，所以从实际考虑以上模型进行优化。为得到两节点间的最短通信距离的通信路径，采用算法对其进行优化。算法规则如下：1） 从任意一条单边路径开始，所有两点之间的距离是边的权，如果两点之间没有边相连，则其边的权重为无穷大。 2）对于每一对顶点和，看看是否存在一个顶点使得从到再到比己知的路径更短，如果是更新它。只需设置相应的起始节点和终止节点，借助算法即可快速求得该两节点之间的最短通信通路。由以上算法编写程序可得到优化后的节点通信模型（程序见附录三）。表 3：任意节点间的通信距离及通信通路起始节点终止节点通信距离通信路径190101.036018064254665669313387156090110712.3854111107 17619.604711157691772.7559913540558050123022 1057121654.03011250805540359716127857.0586125027643324 978192854.0317199366651024 928599666.40035913936665101410937967611134.7677761230454111429733.7591426364403597如节点1到节点90之间的最优通信通路如上表中所示，用可作图如下，由观察法对多对节点进行检验，可得优化后的通信路径较优。模型检验由于95%左右时的n值为不确定数值，存在不稳定性，可对其波动性进行检验，求其波动的期望值（均值），比较有可靠性。6、 模型的评价与改进6.1模型的评价6.1.1模型的优点： 1、模型一采用蒙特卡洛方法，用计算机仿真模拟进行大量实验得到符合要求的概率，有统计学依据，可信度较强；2、 用算法对模型二的优化处理对实际运用意义更大，容易理解且操作简单。6.1.2模型的缺点：1、 用计算机随机模拟的方法对节点进行设置较为符合统计学的概率意义，但产生的随机节点坐标在实际中应用不大。6.2模型的改进 1、针对采用1-100内均匀随机模拟产生的节点坐标的随机性，对于产生的非整数节点坐标在实际中应用有困难，故可以对产生的随机数采取取整处理，以达到与实际得到较大的契合。七、 模型的应用与推广 本文建立的通信通路模型，主要考虑了每个节点的覆盖范围及区域内节点间最优通信路径问题，对于实际生活中的信号塔建造的位置选址、连锁超市的城乡覆盖等问题也具有一定的指导意义。参考文献1、谢金星优化模型与MATLAB软件应用 清华大学出版社2、姜启源、谢金星、叶俊数学模型 高等教育出版社3、解可新、韩建最优化方法 天津大学出版社附录附录一 :蒙特卡洛的启发式算法的模拟ticclearclck=1000; % simulation numbern=447; % different daily ordering quantities of newspapersM=0;w=0;a=;b=;d=1;for q=1:10000 x=100*rand(1,n); y=100*rand(1,n); X=100*rand(1,k); Y=100*rand(1,k); w=0; for m=1:k for p=1:n(d) b=sqrt(x(p)-X(m)2+(y(p)-Y(m)2); if b10 w=w+1; break; end end if w=1000 M=M+1; break; end endendresult=M/10000Toc附录二：对120个可通信节点作图clearclca=load(A2.txt);x=a(:,1);y=a(:,2);for i=1:120 for j=1:120 d(i,j)=(x(i)-x(j).2+(y(i)-y(j).2).0.5; if d(i,j)10 d(i,j)=Inf; end endendtitle(节点通路图)xlabel(节点X坐标)ylabel(节点Y坐标)plot(x,y,r.)text(x,y,num2cell(1:120) hold on附录三：用算法对模型进行优化clearclca=load(A2.txt);x=a(:,1);y=a(:,2);for i=1:120 for j=1:120 d(i,j)=(x(i)-x(j).2+(y(i)-y(j).2).0.5; if d(i,j)10 d(i,j)=Inf; end endendtitle(节点通路图)xlabel(节点X坐标)ylabel(节点Y坐标)plot(x,y,r.)text(x,y,num2cell(1:120) hold onD=d;DD,path,min1,path1=floyd(D,1,90)%对节点1到节点90最优通信路径作图l=length(path1);p=;q=;for i=1:l-1 p(i)=x(path1(i+1); q(i)=y(path1(i+1);endp;q;plot(p,q,-or,LineWidth,2)title(任意两节点之间最短通信路径)xlabel(节点X坐标)ylabel(节点Y坐标)附录四：Floyd算法程序unction D,path,min1,path1=floyd(a,start,terminal)D=a;n=size(D,1);path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end endendfor k=1:n for i=1:n for j=1