三维传感器网络空间结构及其覆盖特性

开篇：润墨网以专业的文秘视角，为您筛选了一篇三维传感器网络空间结构及其覆盖特性范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：三维传感器网络在现实世界中的空间结构远远复杂于二维传感器网络。当前大多数研究采用的随机空间结构假设，不能完全代表三维传感器网络的实际需求。因此提出三种空间对称的立方格结构传感器网络，并利用空间镶嵌理论分析其覆盖特性。同时，针对现有随机结构无线网络中相变现象的分析工具复杂的问题，采用箱覆盖技术推导了随机结构三维传感器网络的临界覆盖半径。

关键词：三维传感器网络;立方格;空间镶嵌;箱覆盖

中图分类号：TP393文献标识码：A

文章编号：1001-9081(2007)04-0909-04

0引言

三维传感器网络是由部署在三维物理空间中、执行一定感知任务的传感器节点组成的无线网络系统。现在已经有大量三维传感器网络应用，如水下静态传感器网络、移动水下设备网络、部署在建筑物各层的传感器网络、放置在树木上监视森林环境的传感器网络等[1―3]。即使一般的地面传感器网络，由于地形起伏，网络往往也并非理论假设的那样是完全平坦的。

图片图1单位立方体内随机分布的无线传感器网络模型

传感器网络的空间结构由传感器节点在空间中的分布方式决定，是传感器网络的一项基本属性。随机空间结构（图1）即节点随机分布于平面或三维空间，是目前传感器网络研究的基本假设。但是,二维随机结构的大部分理论成果并不能直接推广到三维[4]。因为随着空间维数的增加，求解问题的难度大大增加，许多在二维平面可以简单解决的问题，在三维空间中却异常复杂。例如艺术画廊问题（ArtGalleryProblem），在二维平面有最优解，而在三维空间中是一个NP―难问题[5]。

文献[6，7]指出随机结构无线网络中存在相变现象。对于无线传感器网络而言，当感知半径（或传输半径）超过一个临界值时，网络达到覆盖要求（或开始连通），这种变化是突然发生的。文献[8]计算了二维正方形区域内，节点按照固定密度Poisson过程部署的无线网络的临界感知半径。而对于三维无线传感器网络临界覆盖特性的研究还很少。

本文利用晶体学的概念，提出三种适于三维无线传感器网络的规则空间结构，并分析其覆盖条件和连通覆盖条件。对于空间、水下和建筑物内部等应用，规则空间结构的传感器网络具有很多优点，如易于形成连通的稀疏网络；节点数一定的条件下可以最大化覆盖范围；减少节点间的通信量等。在算法设计和性能分析方面，规则空间结构也有助于减小由于维度增加带来的计算复杂性。

针对当前分析随机空间机构传感器网络中相变现象的数学工具复杂，以及三维传感器网络临界覆盖问题研究不足的情况，利用箱覆盖技术，计算三维均匀随机分布的传感器网络覆盖的阈值。

1相关研究

文献[9]在对二维传感器k―覆盖问题研究的基础上，提出一个多项式时间的三维空间中k―球覆盖的判别算法。每个传感器的感知区域被看作是一个三维球体（半径可以不同），k算法可以确定网络监视区域中的每一点是否都被至少k个传感器覆盖，其中k是给定参数。算法的核心思想是将三维空间的几何问题转化到二维空间，进一步转化到一维空间来解决，从而得到高效的算法。这种k―球覆盖算法可以完全分布的运行在每个节点，复杂度为O(d2logd），所以整个网络的算法复杂度为O(nd2logd），其中n为节点个数，d≤n为节点的最大邻居节点个数。

文献[10]推导出节点独立均匀分布在有限立方体空间的Adhoc网络中，两个节点间距离的概率分布公式和节点度的概率分布公式。因为得到的解析表达式十分繁琐，所以作者指出在实际应用中使用数值计算方法更为简易。

文献[6]利用占位理论，从解析证明和仿真分析两方面研究了稀疏无线Adhoc网络中保证连通性所需的临界传输半径。主要结论为：当通信半径均为r的n个节点，随机均匀分布在边长为l的d―维区域（d=2,3）时，网络连通的充分必要条件是rdn值的数量级为ldlnl。因为在模型中考虑了代表网络部署区域边长的几何参数l，所以结论同时适用于稠密和稀疏Adhoc网络。

2三维立方格结构的传感器网络

本节利用晶体学的概念，提出适于三维无线传感器网络的对称空间结构。首先，将传感器节点抽象为一个半径为ρ的球体，球心称为格点，ρ称为堆积半径。格点在二维平面形成两种对称的堆积结构：正方形格结构和六边形格结构，如图2。

通过一定的方式由二维正方形格或六边形格一层一层堆积，可以形成三种空间对称格结构。

图片面心立方结构（FaceCenteredCubicStructure，FCC）的形成过程如图5。第二层的格点放置在第一层“×”标记的空隙处，第三层格点放置在第二层“・”标记的空隙处。

2．1三维立方格的覆盖

根据空间镶嵌理论[11]可知，SC结构中所有格点的Voronoi单元均为大小相同的正方体，如图6。BCC结构的Voronoi单元均为大小相同的截八面体，如图7。FCC结构的Voronoi单元均为大小相同的菱形十二面体，如图8。显然，堆积半径ρ是Voronoi单元的内接球半径，覆盖半径R是Voronoi单元的外接球半径。

令Voronoi单元体积为1，可分别计算得到ρ和R的数值，见表1。表1中BCC结构的覆盖半径最小，所以BCC结构是优于SC和FCC结构的空间覆盖方式。实际上有如下定理：

定理1体心立方格是三维格覆盖的最优形式。

2．2三维立方格传感器网络的覆盖特性

假设传感器网络按照立方格结构部署在一个理想的三维空间中。格中相邻两层球心所形成的平面间的距离，称为层间距，用DL表示。传感器网络是连通覆盖的是指网络在满足覆盖要求的同时还是连通的。

定理2假设传感器节点感知半径为Rs，通信半径为Rt，则：

1)简单立方格网络覆盖部署区域的充分必要条件为Rs≥

(3/2)dl，连通覆盖的充分必要条件为Rt≥(23/3)Rs≥dl；

2)体心立方格网络覆盖部署区域的充分必要条件为Rs≥

(5/2)dl，连通覆盖的充分必要条件为Rt≥(215/5)Rs≥3dl；

3)面心立方格网络覆盖部署区域的充分必要条件为Rs≥

(3/2)dl，连通覆盖的充分必要条件为Rt≥2Rs≥(6/2)dl。

证明由覆盖半径和堆积半径的定义可知，对于三种立方格传感器网络，当且仅当感知半径Rs≥R时，网络完全覆盖部署区域；当且仅当传感器节点的通信半径Rt≥2ρ时，网络是连通的。

通过计算可以得到三种结构堆积半径、覆盖半径与层间距间的关系，如表2。经过代入计算即可证明定理。

3三维随机结构传感器网络

目前研究无线网络中相变现象使用的数学工具主要是连续渗流理论，虽然对于一些情况利用该理论可以得到较好的结果，但推导过程往往十分复杂，对三维空间的问题更是如此。而文献[13]提出的箱覆盖技术是一种离散的、相对简单的随机几何图临界属性分析技术。

本节使用箱覆盖技术计算三维空间中节点均匀随机分布的传感器网络的覆盖阈值。首先介绍渐进强概率的概念。事件El以渐进强概率刻画了依赖于参数l的随机结构的一种属性是指：

4结语

空间结构是传感器网络的基本属性。三维传感器网络受到物理环境的严格限制，在现实世界中的结构远远复杂于二维传感器网络。而当前大多数研究采用的节点在空间随机均匀分布的假设，并不能完全代表三维传感器网络的实际需求。本文提出的三种规则对称空间结构适用于空间、水下和建筑网络。利用空间镶嵌理论分析得到的与感知半径相关的数值结果，可用于指导网络的部署。

相变是随机空间结构无线网络中的一种重要现象，但分析其所使用的数学工具往往比较复杂。本文采用箱覆盖技术，给出了随机空间结构三维传感器网络的临界感知半径。

三维传感器网络的研究还处于起步阶段,围绕空间结构，存在许多要进一步研究的问题。例如，移动三维传感器网络从无序结构到有序结构的自组织；空间或水下环境中，采用移动Agent部署三维规则传感器网络的方法；空间障碍物对三维传感器网络连通和覆盖的影响等。同时，三维传感器网络

的研究与应用密切相关。随着实际应用系统的不断增加，三维传感器网络的空间结构理论将得到更深入的发展。

本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。