- 相关推荐
能量有效的三维无线传感器网络覆盖算法
论文关键词:无线传感器网络;覆盖率;连通;网络寿命
论文相关查阅：毕业论文范文、计算机毕业论文、毕业论文格式、行政管理论文、毕业论文
论文摘要:无线传感器网络通常都工作在三维空间中，因此需要三维空间中的覆盖算法。结合三维空间的特点对二维空间内的覆盖算法SGA进行改进，在此基础上提出一种三维空间的覆盖算法—SSG算法，该覆盖算法的优点是不依赖于节点位置信息，并通过仿真实验给出了覆盖质量分析。
覆盖问题是无线传感器网络(Wireless Sensor Network,WSN)设计中的一个基本问题。由于无线传感器网络节点携带的资源有限，如有限的处理能力、存储和能量，且大部分无线传感器网络需要部署在无人看守的区域，因此，提高监测质量和延长网络使用寿命是无线传感器网络设计的两个重要方面。节约能源的使用是延长无线传感器网络寿命的有效措施，因此提出能量有效的覆盖算法是覆盖研究的方向之一。
目前无线传感器网络的大部分覆盖算法是基于二维平面的。其中能量有效的算法可以分为两类:与位置有关的算法和与位置无关的算法。与位置有关的算法需要在传感器节点中嵌人GPS或有向天线等，不仅硬件成本相对较高，而且位置信息、方向变化等消息的传递和计算也会增大节点能量的开销。而与位置无关的连通性覆盖算法可以减少节点获得和维护位置信息的开销，极大地降低了硬件成本。然而，现有的覆盖算法大多是与位置信息有关的。
与位置有关的算法需要节点自身和邻居的位置信息，根据节点的位置信息计算覆盖关系。例如，Slijepcevi。等人提出了集中式算法，该算法在获知节点位置信息的条件下，可以计算其最大覆盖集，但此算法的可扩展性不好。Xing等人提出了CCP算法，该算法能够根据不同的应用和环境灵活地配置网络覆盖度与连通度，但是需要较为精确的位置信息。虽然在无线传感器网络中提出了很多节点定位算法，但位置误差的可能还是很大。
与位置无关的算法不需要节点的位置信息。比如，Ye等人提出了PEAS算法。在PEAS算法中，工作节点一直工作到能量耗尽，而休眠节点以指数间隔时间开始工作，同时检查是否至少有一个工作节点在它的探测范围内。如果是，它再次休眠;否则，它工作直到能量耗尽。毛莺池等人提出了一种节点位置无关的连通性部分覆盖(Location-Unaware Connected Partial Coverage,LUCPC)协议。首先利用应用期望的覆盖质量与所需的工作节点数量之间的数学关系，随机选取工作节点满足应用需求;然后根据每个节点距基站最小跳数，执行Add-On规则，增加额外节点保证网络连通。Tian等人也提出了三种与位置无关的算法，包括基于最近邻居的算法，基于邻居数量的算法和基于概率的算法。Bai等人提出了一种与位置无关的能量有效的连通性覆盖算法(Stand Guard Algorithm , SGA )。
以上算法都是在二维平面上考虑的。事实上，在一些环境中二维网络是没有意义的。例如，节点部署在森林中不同高度的树上、水域的不同深度、多楼层建筑中或大气层中都需要三维的网络设计。森林防火、海洋学资料收集、污染控制和海上勘探等这些应用的成功与否取决于所考虑的三维空间的覆盖率。全覆盖网络能够检测穿过这个三维空间的任何物体。因此，在三维空间中，满足100%覆盖且使监测所需的节点数最少成为覆盖研究的重要问题之一。但从二维到三维的转变并不容易，因为即使在二维中容易解决的问题，在三维中也是相当困难的。例如，Kelvin猜想、Kepler猜想以及Alam等人提出的三维空间中的节点配置策略，都没有给出最优性的证明。
近几年越来越多的研究者对三维无线传感器网络感兴趣。例如，Ammari等人利用连续渗流理论给出三维无线传感器网络中覆盖和连通的临界密度。Alam等人在三维空间中找到一种节点部署策略，满足100%覆盖，同时使监测所需的节点数目最小。目前三维空间中能量有效的覆盖算法也是研究的热点之一，而把二维的算法推广到三维是解决问题的一种有效途径。
1、模型假设与定义
由于无线传感器网络经常应用于很多不同的环境，节点的布置通过辅助设备抛撒，如飞机将节点随机播撒在监测区域内，所以本文以概率分布描述节点在空间的分布，采用的网络模型和网络满足的条件如下。
1)所有节点随机均匀地部署在一个三维空间中，节点是同类的，每个节点的传感域是一个以节点的位置为中心、半径为Rs的球，假设任何两个节点不部署在同一位置，且节点是静止的。
2)所有处于以某节点为中心、以定长R;为半径的球内的点被认作能够被该节点覆盖。假设当所有节点工作时，目标区域一定能达到100%的覆盖。
3)每个节点无需装备GPS，且无需通过测量或定位方法获得其具体的物理位置，每个节点有唯一的ID编号。
4)节点能量的高低只影响传感时间，不影响传感范围。
定义临界覆盖范围。对一个静态WSN，存在距离集，且r满足:以目标区域内任意一点为中心、;为半径的球内至少有一个传感器节点，则称R1的最小值为临界覆盖范围，用表示。
显然，。
2、三维空间的覆盖算法—SSG算法
2. 1SGA介绍
无线电波可以通过空气、水等介质传播，当某个节点发射信号时，其他节点接收到信号就执行相应操作，若没有收到信号就不执行任何操作，执不执行操作与节点的位置无关。SGA即是用信号作为节点之间的“桥梁”这种思想设计的，避免了对节点位置的依赖性。SGA将监测区域分为若干网格，通过保证每个网格的覆盖实现区域的全覆盖。为了延长网络寿命，SGA采用节点轮换工作机制，在每一轮中，对每个节点设置标记tag=0，该节点每收到一条消息，tag值加1，当tag值达到覆盖度k时使该节点处于休眠状态;否则，使其处于工作状态。仿真表明SGA的覆盖率或冗余节点率有一定优势。但是SGA还存在不足:首先该算法是针对二维空间设计的，而一般节点部署的实际环境均是三维空间，不符合实际。其次是没有考虑节点的能量消耗问题。在SGA中，第一轮执行时所有节点的能量相同，工作一段时间后，由于部分节点消耗能量，下一轮开始时节点的能量是不同的，SGA忽略了这个差异，使每一轮取到的工作节点都是相同的或大部分是相同的，导致集中消耗一部分节点的能量，而使另一部分节点完全浪费掉了，这样会造成整体能量消耗的不均衡。为此本文将SGA推广为考虑能量均衡消耗的三维空间的无线传感器网络覆盖算法(SSG)。
2. 2SSG算法
在SSG算法中，也采用节点轮换工作机制，每一轮包括状态选择阶段和工作阶段。在每一轮开始，所有节点处于工作状态，且进人状态选择阶段。在状态选择阶段，每个节点选择自己的状态(工作或休眠)，且保持这种状态直到下一轮开始。在SSG算法中每一轮尽可能选取能量高的节点作为工作节点，使能量消耗分散在更多的节点上，从而可以达到能量平衡，延长网络寿命。在工作阶段，工作节点执行传感任务。每个工作节点以半径Rsg向周围广播SSG消息(SSGM )，其中包括节点ID。以工作节点为中心，Rsg为半径的球内(包括边界)的所有工作节点能够收到这个消息。节点检查自身传感任务是否可由邻居节点完成，收到SSGM的可替代节点返回一条状态通告消息，之后进入休眠状态，需要继续工作的节点执行传感任务。SSG算法详细描述如下。
1)设置一个固定的时间片，并以其为周期。在每轮中，状态选择时间用T1表示，工作时间用T2表示。
2)在状态选择阶段，按照低能量节点到高能量节点的次序等时间间隔，N为随机部署的节点个数)广播SSG消息(第一轮节点次序随机)，如果在时间t内没有其他节点收到广播节点的SSG消息，转4);否则，转3)。
3)使广播消息节点处于休眠状态，转4)。
4)保持它的状态直到下一轮开始。
2. 3SSG算法的分析
根据SSG算法，任意一个处于休眠状态的节点，在它的Rsg范围内至少有一个工作节点(依赖Rsg，处于休眠状态的节点集可能为空)。也就是说，Rsg≤Rs是目标区域内任意一个休眠节点被工作节点覆盖的充分条件。因此，为了保证覆盖质量，Rsg的取值一般小于传感半径Rs。下面给出目标区域内任意一点被工作节点覆盖的充分条件。
定理 。是工作节点能100%覆盖目标区域的充分条件。
证明假设P是目标区域内任意一点，根据的定义，以P为中心、。为半径的球内至少有一个传感器节点，记为A。以下分两种情况讨论:
1)若A是工作节点，因为，则P被A覆盖。
2)若A是休眠节点，由SSG算法知，以A为中心、Rsg为半径的球内至少有一个工作节点，记为B。根据三角不等式得:
又因为，所以，从而P被工作节点B覆盖。其中|·|表示两点间的欧氏距离。
综上，由P点的任意性证得定理成立。
本文从理论上证明了定理的正确性，下面给出一个具体的实例。根据Alam等人提出的一种三维空间中的节点部署策略，假设目标区域的体积为V，部署目标区域所用的平截八面体(细胞)的体积为Vl，则满足100%覆盖所需要的工作节点数目M=V/Vl，其中，Vl = 0. 683 29 x (R可以看作节点的传感半径)。这样，得到R的表达式为R =，如果V和M的值就能求出R的一个值。根据这种部署策略和的定义，可以用=来估计定理中的值。这里设目标区域为边长为50的正方体，即V _- 50 x 50 x 50 ; M的值是运行算法的结果，随Rsg的不同而不同。计算得到表1数据。
3、仿真
N个节点随机均匀部署在一个边长为L的正方体中，Ｌ=SO,Rs=10。在仿真中，本文考虑覆盖率、冗余节点率和工作节点数。覆盖率是工作节点覆盖的区域和整个目标区域的比，它反映了WSN的监测质量。为了计算覆盖率的值，把边长为50的正方体划分成边长为1的小立方块(共125 000个)，把中心被覆盖的小立方块数量和目标区域中所有立方块数量的比作为覆盖率。冗余节点率是休眠节点数目和总节点数目N的比。冗余节点率越高，网络消耗的能量越少。
为了估计覆盖率和冗余节点率，选择N分别为800和1000 , Rsg是从I到15取值，仿真结果如图1 ,2所示。
从图中看到当Rsg增大时，冗余节点率上升，覆盖率下降。为了证实工作过的节点数确实随着轮数的增加而增加，以N=800为例，Rsg是从1到10取值，其中i(i=1,2,…,5)轮工作过的节点数是指第1轮到第i轮工作过的节点个数，仿真结果如图3所示，所有图中标记的每个点是多次重复实验的平均值。
在实际应用中，选择最优的Rsg值，使网络既满足覆盖要求，同时使冗余节点率达到最大，从而节省节点能耗，延长网络寿命。从图中可以看出，当Rsg≤Rs/2时，覆盖率为1(或接近1);当Rsg>Rs/2时，覆盖率迅速下降。所以对于三维空间中的覆盖问题，如果不能精确估计Rsg的值，最好取Rsg的值为传感半径的一半。
4、结语
本文将SGA推广到三维空间中，提出SSG算法，解决在没有节点位置信息的情况下三维空间的覆盖问题。实验结果表明，该算法在满足100%覆盖的前提下，使冗余节点的数目达到最大，从而节省了能耗，延长了网络寿命。
论文相关查阅：毕业论文范文、计算机毕业论文、毕业论文格式、行政管理论文、毕业论文
【能量有效的三维无线传感器网络覆盖算法】相关文章：
简论控制算法理论和网络图计算机算法显示05-04
试析无线定位技术论文04-14
探讨医疗仪中新型微型传感器特征及应用05-01
家庭无线局域网的组建08-13
明确目标 有效示范-探索有效美术课堂05-25
Flash三维效果应用实例08-20
矿井安全生产用传感器误码的防范措施论文05-19
高校三维动画教育论文05-26
如何有效组织英语早读09-28
无线通信抗干扰问题探讨论文04-28