《无线传感网络设计问题.doc》由会员分享，可在线阅读，更多相关《无线传感网络设计问题.doc（11页珍藏版）》请在三一文库上搜索。
1、第二次个人赛论文 姓名代码： 88无线传感网络设计问题摘要本文针对无线传感网络节点的放置和节点间相互通信的路径选择问题做了深入的 研究。对于问题（ 1），本文根据概率论知识（当试验次数足够大时，可以近似认为事件发 生的频率等于其概率）采用计算机仿真法，在监视区域内随机安放 n 个节点，组建无线 传感网络，然后在监视区域随机取 20000 个点，通过检验这些点是否全部被所组建的无 线传感网络覆盖来判断所组建的无线传感网络能否成功覆盖整个区域。进行多次仿真， 统计并计算出由这 n 个节点组成的无线传感网络成功覆盖整个区域的频率， 将此频率与 95%比较，然后根据不同情况适当调整 n 的大小，最后找
2、出能成功覆盖整个区域的概率 在 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）。最后，本文对问题（
3、1）和问题（ 2）中的模型进行了评价，并对第一问中的仿真模 型求解时只检验无线传感网络对整个监视区域是否完全覆盖， 而没有考虑随机安放的节 点间能否相互通信的问题进行了进一步讨论，并提出以节点间距离的最小值为判断依 据，在原覆盖的基础上剔除一些与其他节点间最小距离大于 10 的节点的修正方案。并 对模型进行了简单的推广。关键词 ： 计算机仿真；图论模型；概率论； Dijkstraf 算法问题的提出和重述1.1 问题的提出 大气污染所引起的地球气候异常，导致地震、旱灾等自然灾害频频发生，给人民的 生命财产造成巨大损失。因此，不少国家政府都在研究如何有效监测自然灾害的措施。 在容易出现自然灾害的重
4、点地区放置高科技的监视装置，建立无线传感网络，使人们能 准确而及时地掌握险情的发展情况，为有效地抢先救灾创造有利条件。科技的迅速发展 使人们可以制造不太昂贵且具有通讯功能的监视装置。 放置在同一监视区域内的这种监 视装置（以下简称为节点）构成一个无线传感网络。如果监视区域的任意一点都处于放置在该区域内某一节点的监视范围内， 则称节点 能覆盖该监视区域。研究能确保有效覆盖且数量最少的节点放置问题显然具有重要意 义。1.2 问题的重述图 1 中，叉形表示一个无线传感网络节点， 虚线的圆形区域表示该节点的覆盖范围 可见，该无线传感网络节点完全覆盖了区域 B，部分覆盖了区域 A。网络节点间的通信设计问
5、题是无线传感器网络设计的重要问题之一。如前所述，每 个节点都有一定的覆盖范围，节点可以与覆盖范围内的节点进行通信。但是当节点需要 与不在其覆盖范围内的节点通信时，需要其它节点转发才可以进行通信。图 2 无线传感网络节点通信示意图图2所示，节点 C不在节点 A的覆盖范围之内，而节点 B在 A与 C的覆盖范围之内， 因此 A 可以将数据先传给 B，再通过 B传给 C。行成一个 ABC的通路。问题 1：在一个监视区域为边长 b=100（长度单位 ） 的正方形中，每个节点的覆盖半 径均为 r=10（ 长度单位 ） 。在设计传感网络时， 需要知道对给定监视区域在一定的覆盖保 证下应放置节点的最少数量。对
6、于上述给定的监视区域及覆盖半径，确定至少需要放置 多少个节点，才能使得成功覆盖整个区域的概率在 95%以上？问题 2：在 1 所给的条件下，已知在该监视区域内放置了 120个节点，它们位置的 横、纵坐标如表 1 所示。请设计一种节点间的通信模型，给出任意 10 组两节点之间的 通信通路，比如节点 1 与节点 90 如何通信等。二、问题的分析根据查询的相关资料， 无线传感网络设计中的节点放置和节点间通信问题是近今年 的热门课题。由于地理条件的复杂，一般情况下无线传感网络设计中的节点只能采用非 均匀投放的方法 1 。鉴于此，本文对题目中的问题做了如下分析：针对问题一 ：由于安放节点是随机的， 某事
7、件发生的概率可以用多次实验中该事件发生的频率代 替 2 , 而两者均可用计算机仿真实现，因此可通过计算机不断产生随机数模拟节点安放 和监视区域各点被覆盖的情况，再以题目中 95%为约束，找出最优节点数。针对问题二 ： 对于该问题，根据题目中所给的 120 个节点的坐标，很容易求出各节点间的距离，由题 设可知，一个节点不在另一个节点覆盖的范围之内，则两节点间不能直接通信，要通过 其它节点间接通信。在通过其它节点实现间接通信的过程中，肯定会产生不同的通信通 路，本文要做的是找出任意两点间的最优通信通路。这很容易让人联想到图论模型最短 路径的求法，于是可根据题设限制条件，将各点间的距离矩阵转化为带权
8、邻接矩阵，通 过 matlab 软件求解出各点间的最优通信通路。三、模型假设1、各节点的覆盖范围相同且稳定，不受天气及电磁干扰；2、任何节点与其覆盖范围内的节点间的通信强度相同；3、节点间的通信距离与通信所用的时长成正比。四、符号及变量说明n ：每次仿真随机产生的节点数； N：每次安放好节点后在监视区域内随机取的检验点个数； dij ：监视区域内第 i 个随机点与第 j 个节点间的距离（ i=1,2 N；j=1 ， 2n）； dimin ：第 i 个监测点与 n 个节点的距离最小值 （i=1,2 N）；r ：每个节点的覆盖半径， r=10 ； T；仿真次数；t ：可以成功覆盖整个监视区域的仿真
9、次数； 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 对于问题一的模型建立和求解查阅相关文献得知， 无线传感网络中的节点安放是非
10、均匀的 1 ，本文建立仿真模型， 通过计算机在监视区域内随机产生 n个节点 ( X j ,Yj )来模拟节点的非均匀安放根据概率 论知识：当试验次数足够大时，可以近似认为事件发生的频率等于其概率，于是可通过 计算机在已将安放好节点的监视区域内随机产生 N个检验点 (xi, yi) ，并求出这 N个点与 各节点间的距离dij(xi X j)2 (yi Yj)2然后选出每个检验点与 n个节点的距离最小值 dimin ，根据题设节点间的通信条件， 将dimin 与覆盖半径 r 比较，对于所有的 i=1,2 N(N取足够大 ) ，若满足 dimin <r 则可以认为这 n 个节点组成的无线通信网
11、络可以成功将监视区域覆盖， 否则则认为没有 成功覆盖。对上述过程进行 T次仿真,统计能成功覆盖整个监视区域次数 t ，并计算出相 应的频率 f, 当 T取足够大时，可以认为这 n 个节点能成功覆盖整个监视区域的概率 pf 根据题目要求，比较 p 与 95%的大小 若p 95%则增大 n 值；反之则减小 n 值，再重复上述仿真过程， 直至找出 p 95%时的最小 n 值。检验次数 了吗？ 4本文仿真程序相应的参数为： T=1000 N=20000（详见附录二第一题程序） ，通过不 断手动调整 n的大小，最后找出能成功覆盖整个区域的概率在95%以上的最少节点数为565个。5.2 对于问题二模型的建
12、立和求解根据题意，两节点间能直接相互通信的条件为Dij <r否则要通过其它节点间接进行通信，在通过其它节点实现间接通信的过程中，肯定会产 生不同的通信通路，本文要做的是找出任意两点间的最优通信通路。于是本文建立图论 模型，考虑到通信的时效性和及时性，以通信所用时间最短为选取最优通路的原则，并 根据本文条件假设 3（节点间的通信距离与通信所用的时长成正比） ，将通信时间最短转 化为路径最短，采用 Dijkstraf 算法求出任意给定的两点间的最优通信通路 3 。Step1：求出 120 点两两之间的距离矩阵D11D12D1120DD21D22D2120D1201D1202D120120Ma
13、tlab 程序求解步骤如下：Step2：将 D中大于 r 的元素变为 ，将距离矩阵 D 转化为带权邻接矩阵W11 W12W1120W21 W22W2120W；W1201 W1202W120120Step3：采用 Dijkstraf 算法，将 W带入其中，计算出任意给定两节点间的最优通信通路。 所得的十组节点间的最优通信通路如表 1： 表11-21111077041951021836104103 21-101806425101-201115621064541119899201-30111562106301-4018055401-50180501-6018064254665669313 387 1
14、5 601-70111107701-801801-9018064254665669313387 15 6090六、模型的评价和改进6.1 模型的评价6.1.1 优点 对于问题 1 本文在题目信息和查阅相关资料的基础上， 用计算机仿真法模拟无 线网络节点的不规则放置和检验无线网络的覆盖率， 充分利用计算机的优势， 化繁为简， 以频率代替概率，得出的结论可信度高。 在仿真过程中，对重要参数调整问题，本文采用手动调整法，这样可以避免计 算机仿真次数过多，程序运行时间过长的问题，既可以节省时间又可以较准确判断最理 想的 n 值。 求解问题 2 时，本文在考虑通信的时效性和及时性的基础上，建立图论模型，
15、 并以通信时间最短为最佳路径选取依据，又通过合理假设将时间最短转换成距离最短， 这样就能与 Dijkstraf 算法完美结合， 也能很便捷的求出题目要求的制定两点间的通信 通路。6.1.2 缺点1. 计算机仿真次数有限，所得结果不可避免会有一定误差2. 在建立仿真模型，检验监视区域是否完全被覆盖时，只考虑了区内点的被覆盖的 概率，没有考虑所有节点间是否能实现相互通信。6.2 模型的改进本文通过分析对问题 1 的中的仿真模型进行改进。在每次随机布置好节点后，先通 过节点间的距离对这 n 个节点布置合理性进行初步检验， 以一个节点与其他各节点距离 的最小值 limin 为判断依据，当 时，则该节点
16、与其他节点不能实现通信，应该讲该节点剔除。修改后测程序见附表二。 讲过修改后，得到能成功覆盖整个区域的概率在 95%以上的最少节点数为 571 个。mini>r七、模型的推广和应用本文所建立的仿真模型，用到了随机抽取和循环迭代思想，可广泛应用于估计某些事件 可能发生的概率。 本文建立的图论模型也可广泛应用到无线设备比如手机的信号传递路 径选取上。参考文献：1 陶丹，马华东，刘亮 无线传感器网络节点部署问题研究 , 北京 1008762 茆诗松，程依明，濮晓龙 . 概率论与数理统计教程 M. 北京：高等教育出版社 .2009 ；3 刘卫国 主编 MATLAB程序设计教程 （ 第二版 ）M.
17、 水利水电出版社出版社 .2010 ；附录一： 120 个节点的坐标表节点标号XY节点标号XY节点标号XY节点标号XY1575831633613295917444295743285962477192412533412336437635043933921431683422136456439495515526735694365562595727663043680836647259679871575377613678064977844875523888946810969810809753039259569123399889106528406245706370100159511556341707071
18、399101459012416142454272818910270821336204335973431410390781472244475417417251048478151610453591758055105207016854946563076456110640711786904727927792401075570187590489290787822108595193220492558798945109731820592504452805151110222821163551580814090111178022256652173382654911250102372453905837671135
19、520246833542574843098114872225613555584785263411572982637785695286289911655792748465787728725811772288131586888882963118852029239059302889408311935503035666099904111201068附录三：第一题程序clcclearn=565; %设定 n个节点T=1000; %随机设定节点的次数N=20000; %检验覆盖率的仿真次数r=10; % 覆盖半径t=0; % 被完全覆盖次数for i=1:Tm=0; % 覆盖的点的个数，每次循环初始化为零
20、Q=0; % 区域覆盖率，每次循环初始化为零for i=1:n % 在监视区域内随机产生 n个节点A(i)=100*rand; % 横坐标B(i)=100*rand; % 纵坐标endfor i=1:N % 在监视区域内随机取 N个点看其是否被覆盖 x=100*rand; % 横坐标 y=100*rand; % 纵坐标for i=1:n d(i)=sqrt(x-A(i).2+(y-B(i).2); %计算该点与 n 个节点的距离endif min(d)<=r % 判断该点是否被覆盖 m=m+1;endendif m=N % 判断是否被完全覆盖t=t+1endendp=t/T % 监视区域
21、被完全覆盖的频率第二题程序clc clear x=load('x.txt');y=load('y.txt'); % 输入节点坐标for i=1:120for j=1:120d(i,j)=sqrt(x(i)-x(j).2+(y(i)-y(j)2); % 求出各节点间的距离矩阵 if d(i,j)>10 % 将距离矩阵转化为带权邻接矩阵d(i,j)=inf;endendenddis, path=dijkstraf(d, 1, 5) %调用 Dijkstraf 算法第一题改进后的程序clcclearn=565; %设定 n个节点 t=500; % 随机设定节点的
22、次数 N=5000; %检验覆盖率的仿真次数 r=10; % 覆盖半径 f=0; % 被完全覆盖次数for i=1:tm=0; % 覆盖的点的个数，每次循环初始化为零Q=0; % 区域覆盖率，每次循环初始化为零 for i=1:n % 在监视区域内随机产生 n个节点A(i)=100*rand; % 横坐标B(i)=100*rand; % 纵坐标 endfor i=1:n % 剔除不能与其他节点相互通信的节点for j=1:n d(i,j)=sqrt(A(i)-A(j).2+(B(i)-B(j)2);if d(i,j)=0d(i,j)=inf;endendendL=min(d);for i=1:nif L(i)>10A(i)=inf;B(i)=inf;endendA(A=inf)=;B(B=inf)=;for i=1:N % 在监视区域内随机取 N个点看其是否被覆盖x=100*rand; % 横坐标y=100*rand; % 纵坐标for i=1:size(A,2) % 变化循环次数 d(i)=sqrt(x-A(i).2+(y-B(i).2); %计算该点与 n 个节点的距离endif min(d)<=r % 判断该点是否被覆盖m=m+1;endendif m=N % 判断是否被完全覆盖f=f+1endendp=f/t % 监视区域被完全覆盖的概率