无线传感网络设计问题概要

1无线传感网络设计问题摘要本文针对无线传感网络节点展开讨论，主要研究在监视区域内放置节点个数与成功覆盖概率的关系、节点的通信模型设计问题。对于问题1，首先考虑将节点分为两大类，一类节点一定完全落在监视区域内，另一类节点只能部分落在监视区域内，通过这两类节点的发生概率以及这两类节点覆盖面积的期望值，可以求得所有节点覆盖面积的期望值。运用概率论的知识综合两类节点的期望，求解出至少要放置88个节点，才能使成功覆盖整个区域的概率在95%以上。同时通过随机模拟仿真实验，我们得出了成功覆盖概率与节点个数的关系图，可以清晰的看出成功覆盖概率随着节点个数的变化趋势。对于问题2，首先根据题目要求描点连线，将不可以通行的路径去掉，得到节点通信路径图，通过该图我们可以找出任意两个节点间的通信通路，例如节点31到节点74的通信通路为：31692174，但显然其路径不唯一，我们在节点通信路径图的基础上进行优化，找出两个节点之间的最短路径，在解决这个问题上我们分为两步优化：第一步：运用Dijkstra算法求出固定起点到任意点的最短路径；第二步：运用Floyd算法求出任意两节点间的最短通信通路，例如节点1到节点90的最短通信通路为：18064254665669313387156090。对于问题3，从节能角度出发，在问题2通信模型的基础上，进一步考虑无线传感网络节点间通信半径与能量消耗的关系。本文认为通信半径越长，能量消耗越多。因此，问题3的目标变为了使相邻节点间路径最短，根据这个目标我们可以引用最小生成树的思想得到一个最小生成树路径图，得到从节能角度考虑设计的任意两节点间的通信路径，例如节点76到节点19的通信通路为：766019。在问题3上的基础上我们提出了相应的改进思想，根据最小生成树路径图，我们发现有些节点处于其他若干个节点的通信路径交汇处，如节点72、106、107，这类节点存在过载使用。为避免这种情况，最大最小通信使得节点的剩余电量尽可能多，即最大化节点的最小剩余电量。基于以上的思想我们认为可以定义一个电源的开销函数。这样可以避免交叉节点的过载使用，延长整个遥测遥感网的通信寿命。关键词：成功覆盖率；通信模型；Dijkstra算法；Floyd算法；最小生成树2一、问题的重述自然灾害频频发生，给人民的生命财产造成巨大的损失，因此一些国家通过在容易出现自然灾害的重点地区放置高科技的监视装置，进而建立无线传感网络的方式，帮助人们准确而及时地掌握险情的发展情况，为有效地抢先救灾创造有利条件，这对于减少人民的生命财产损失具有重大意义。放置在同一监视区域内的这种监视装置（以下简称为节点）可以构成一个无线传感网络如附录一图1。如果监视区域的任意一点都处于放置在该区域内某一节点的监视范围内，则称节点能覆盖该监视区域，可见研究能确保有效覆盖且数量最少的节点放置问题显然具有重要意义。网络节点间的通信设计问题也是无线传感器网络设计的重要问题之一，每个节点都有一定的覆盖范围，节点可以与覆盖范围内的节点进行通信。但是当节点需要与不在其覆盖范围内的节点通信时，需要其它节点转发才可以进行通信如附录一图2。通过查找相关资料，建立数学模型解决以下问题：问题一：在一个监视区域为边长b=100(长度单位)的正方形中，每个节点的覆盖半径均为r=10(长度单位)。确定至少需要放置多少个节点，才能使得成功覆盖整个区域的概率在95%以上。问题二：在问题一所给的条件下，已知在该监视区域内放置了120个节点，它们位置的横、纵坐标如附录二表1中120个点的坐标表所示。试设计一种节点间的通信模型，给出任意10组两节点之间的通信通路，比如节点1与节点90如何通信等。问题三：对用于监视旱情的遥测遥感网，由于地处边远地区，每个节点都只能以电池为能源，电池用尽节点即报废。实际情况下，节点的覆盖范围也会随着节点能量发生变化。针对附录二中表1的数据，从节能角度考虑设计，改进问题2中的通信模型。给出任意10组两节点之间的通信通路，比如节点1与节点90如何通信等。二、问题的分析建立无线传感网络，使人们能准确而及时地掌握险情的发展情况，但到底要设置多少个节点使得成功覆盖概率较高的问题值得我们关注，同时设计一个合理有效的节点通信模型也是整个无线传感网络中的重中之重。对于问题（1），基于给定的监视区域以及覆盖半径，要求放置最少的节点使得成功覆盖整个区域的概率在95%以上。由于给定监视区域存在边界，故可以将节点分为两大类，一类节点一定完全落在监视区域内，另一类节点只能部分落在监视区域内，这两类节点发生的概率可以由相应区域面积与总监视区域面积之比得出，同时，可以得到两类节点覆盖面积的期望值，进而可以求得随机在给定监视区域内放置节点，节点覆盖面积的期望值。可以运用概率论的知识综合两类节点的期望求解覆盖整个监视区域的概率，令该概率值大于95%即可求解。当然，还可以通过设计随机仿真实验的方法进行进一步的分析求解最少的节点数目。对于问题（2），由于每个节点都有一定的覆盖范围，节点只可以与其覆盖范围内的节点进行通信，根据120个节点的坐标，即可得到两两节点之间的距离，于是满足节点通信条件的所有节点都可以找到。通过这样的方法，任意两节点之间的通信通路即可得出。由前面的方法可以找到两节点的通信路径，但是路径不唯一，所以通过Dijkstra算3法可以求出固定起点（本文我们固定节点1为起点）到其余任意节点的最短通信路径。借鉴上述Dijkstra求特解的思路，我们又可运用Floyd算法求出任意两节点之间的最短通信路径，因此本文可以尝试用上述两种算法对模型进行进一步优化从而快速得到任意两节点之间的最短通信通路。对于问题（3），我们需从节能角度出发，在问题（2）所得节点间最短通信路径模型的基础上，进一步考虑无线传感网络节点间通信半径与能量消耗的关系，即通信半径越长，能量消耗越多。因此，这里我们可以引用最小生成树的思想得到一个最短路径图，得到从节能角度考虑设计的任意两点间的通信路径。三、模型的假设与符号的说明3.1模型的假设（1）监视装置工作稳定，不会突然失效；（2）每个监视装置单位感知距离内耗能相同；3.2符号的说明r：节点的覆盖半径；b：正方形监视区域的边长；(C)E：节点覆盖面积的期望值；：监测区域的面积；n：放置的节点数目；：无线传感网络覆盖率；ix：节点位置的x坐标，=1,2,3,...,119,120i；iy：节点位置的y坐标，=1,2,3,...,119,120i；ijd：节点i到节点j的距离，=1,2,3,...,119,1201,2,3,...,119,120ij，；k：无线传感网络的某一节点；R：节点间的通信半径e：无线传感网络中某一节点的能量消耗；E：无线传感网络中所有节点的能量消耗总和。四、模型的建立与求解4.1问题（1）的模型建立与求解4.1.1模型一：无线传感网络概率覆盖模型【1】首先考虑在监测区域内部部署一些节点，这些节点构造成一个节点集合S，每个节点的覆盖面积为为(C)E，覆盖概率为(C)/E；当节点集合为空时，放置n个节点便得到网络的覆盖率：(C)(S)=1-nEP为空（），这样就得到了S不为空集的情况下，网络节点的覆盖概率值：(C)(S)=1-1-nnEP（）（1）式（1）和观察到的lim(S)=1nnE是一致的，它表明了当节点数目足够大时，该区域4是被完全覆盖的。本文按照图1的方式将网络区域划分成区域1和区域2，节点放置好之后，或位于区域1内，或位于区域内2。图1：节点p位于区域Ⅱ内的示意图由此得到网络节点覆盖的期望值为：1212(C)=P()E(C)+P()E(C)E（2）其中，1P()和2P()分别表示节点被随机放置在区域1和区域2里的概率。1E(C)和2E(C)分别表示其相应的覆盖期望值。由于传感器节点的放置服从均匀分布函数，得到：21222(b-2r)4r(b-r)P()=,P()=bb（3）当节点位于区域1时，它的覆盖范围被完全包含。覆盖期望值为2r。根据图1，当节点位于区域2时，2C的面积应等于其覆盖圆周的面积减去弓形区域ACBD的面积。A和B是节点p的覆盖圆周和网络边界的交叉点。设=APB。其面积为：2221C=-(2-+sin)2ACBDrSr（4）于是，由式（5）得到2C的期望值：2-200-0011C=4(2-+sin)=4(b-r)r2(2-+sin)2(b-r)brrbrrErdxdyrdxdy（5）假设覆盖半径为r的节点均匀分布在边长为b的正方形区域，在考虑边界因素的情况下，由式（2）~式（5）推导得到节点的覆盖期望值为：22C=(-2)+2(-)(2++)2rEbrbrrrb（6）5在给定边长为b的正方形区域，节点覆盖半径是r和较小的参数，要确保网络覆盖率的期望值不小于，根据式（1），应满足：(C)(S)=1-1-nnEP（），这样得到(C)ln(1-)ln(1-)En，由于(C)ln(1-)0E，可以得到：ln(1-)(C)ln(1-)nE（7）本题目中，=100b，=10r，=0.95，故由（6）（7）式可以得到：87.922n，故基于本文给出的监视区域及覆盖半径，通过无线传感网络覆盖模型得出，至少需要88个节点才能使得成功覆盖整个区域的概率在95%以上。4.1.2无线传感网络概率覆盖模型仿真实验本文设计随机仿真实验，经过多次重复实验，得到无线传感器网络成功覆盖整个区域的概率和节点数目的关系如图2所示：图2：成功覆盖的概率与节点数的关系通过随机仿真实验的方法，结合图2所示，本文得出当节点数目为88时，成功覆盖整个区域的概率为95.18%。4.2模型二：无线传感网络通信模型4.2.1节点通路图由于每个节点都有一定的覆盖范围，节点可以与覆盖范围之内的节点进行通信。任意两个节点之间的距离为：22=(-)+(y-y)ijijijdxx（8）即对于10ijd的两个节点之间不可以进行通信，只有10ijd的两个节点之间才可以进行通信。因此，本文将所有10ijd的两节点之间用直线连接，得到节点通路图如图36所示：01020304050607080901000102030405060708090100节点通路图节点X坐标节点Y坐标123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120图3：节点通路图通过图3的节点通路图，可以得到无线传感网络中任意10组两节点之间的通信通路，如下表1所示：表1：节点1到各节点的最短通信距离及最短通信通路起始节点终止节点通信路径11118050765111271115765027110711151071411115107704116218050765621861115621062689456184861591806425466566929313591131806425466566929313169180642546656693135985110190180642546656693133873415但是，本文也发现，该模型下每两个节点之间的通信通路并不唯一，结合实际情况，本文认为有必要在模型一的基础上作进一步的优化，直接获得两节点之间的最短通信通路，为有效地抢先救灾创造有利条件。