第4次课WSN覆盖技术详解.ppt

第4次课 WSN 覆盖技术; 2. GAT算法;3.5启发机制;2. ASCENT算法;3.6 覆盖; 无线传感器网络覆盖相关的两个计算几何问题,(三角形、圆)。 第一个就是艺术馆问题(Art Gallery Problem)。设想艺术馆的业主想在馆内放置照相机，以便能够预防小偷盗窃。关于实现这个想法存在两个问题需要回答：首先就是到底需要多少台相机；其次，这些相机应当放置在哪些地方才能保证馆内每个点至少被一台相机监视到。假定相机可以有 的视角而且可以极大速度旋转，相机可以监视任何位置，视线不受影响。; 问题优化要实现的目标就是所需相机的数目应该最小化，在这个问题当中，艺术馆通常建模成一个二维平面的简单多边形。一个简单的解决办法就是将多边形分成不重叠的三角形，每个三角形里面放置一个相机。通过三角测量法将多边形分成若干个三角形，这样可以实现任何一个多边形都可被 个相机所监视到，这里 n 表示多边形所包含的三角形的数目。这也是最糟糕情况下的最佳结果。 ; 如图2-7所示是将一个简单多边形用三角测量法拆分的例子，放置两个监视相机足以覆盖整个艺术馆。尽管这个问题在二维平面可以得到最优解，然而扩展到三维空间，这个问题就变成了NP-hard问题了。 图2-7多边形的三角测量法及监视相机的位置配置 NP-hard问题: NP是指非确定性多项式（non-deterministic polynomial，缩写NP）。所谓的非确定性是指，可用一定数量的运算去解决多项式时间内可解决的问题。NP 问题通俗来说是其解的正确性能够被“很容易检查”的问题，这里“很容易检查”指的是存在一个多项式检查算法。相应的，若NP中所有问题到某一个问题是图灵可归约的，则该问题为NP困难问题; 另外一个与无线传感器网络覆盖相关的几何问题是圆覆盖问题，即在一个平面上最多需要排列多少个相同大小的圆，才使其能够完全覆盖整个平面。换个角度说，也就是给定了圆的数目，如何使得圆的半径最小。A．Heppes和J．B．M．Melissen实现了矩形平面的圆最优覆盖问题，分为最多用5个圆和7个圆来完成覆盖两种情况。如图2-8所示给出了一个7个圆最优覆??的一个例子。 图2-8用7个圆实现最优覆盖的样例; 无线传感器网络的覆盖问题在本质上和上面的几何计算问题是一致的：需要知道是否某个特定的区域被充分覆盖和完全处于监视之下。就成本而言，配置的传感器节点的数量是非常重要的。在典型的无线传感器网络应用当中，放置或配置一些传感器节点来监视一个区域或点集。; 确定性配置和非确定性的配置(随机配置)　 1. 一些应用中可以选择传感器配置场地，如定点部署和配置，这种方式称为确定性配置； 2.　而另外一些应用(如敌方区域或非常恶劣等人员不能到达的环境)，只能通过随机部署(如空投撒播方式)足够多的传感器节点到监视区域，希望空投后未遭破坏的传感器足以监视目标区域，这种方式称为非确定性的配置或随机配置。如果可以选取部署场地，可采用确定性的传感器配置方法；否则，该配置就是随机配置。 ; 在上面两种配置情况下，都希望部署的传感器集合能够彼此通信，或者直接或者间接通过多跳方式通信。 因此，除了要覆盖感应的区域或点集外，通常需要配置的传感器集合能够形成一个互联的网络。就连接特性而言，需要知道传感器的感应半径r与通信半径c，其连接覆盖的充分必要条件，满足定理1。 定理1：当传感器的密度(即单位区域的传感器数目)为有限时，c ≥r是覆盖包含连接性的充分必要条件。; X.Wang等人也证明了在 k 阶覆盖(每个点至少被 k 个传感器覆盖)和 k 阶连接性(配置传感器的通信图是k阶连接的)情况下的一个类似的结论，满足定理2。 定理2：当c ≥ 2r，一个凸区域的 k 阶覆盖必定包含了k 阶连接性。 注意到k1的k阶覆盖提供了一定的容错度，能够监视所有的点，只要不多于k-1个传感器故障或失效。 凸区域:就是凸的区域。凸从几何上看就是图形是往外凸的，没有凹进去的地方。代数上是这样定义的：集合中任取两个点a，b，有t*a+(1－t)*b仍属于这个集合，其中0t1。这个表达式的意思就是连接两个点a b的直线段还在集合中。这是凸的意思。区域就是连通的开集，也可以等价的说是道路连通的开集。所谓道路连通也很好理解，就是集合中的任意两个点有一条道路连接它们。 ; 与覆盖问题直接相关的是传感器节点的感知模型。目前，无线传感器网络主要有两种基本感知模型。 　1．布尔感知模型 2．概率感知模型 ;3.