第二章无线传感网络概述 复习
第二章无线传感网络概述
2.1 无线传感器网络拓扑结构
分类
组网形态和方式分类
1.集中式
2.分布式
3.混合式：集中+分布
节点功能及结构层次：
1.平面网络结构
最简单的一种拓扑结构
所有节点为对等结构
具有完全一致的功能特性
每个节点均包含相同的mac地址、路由、管理和安全等协议
Ad Hoc网络结构形式
拓扑结构简单
易维护
具有较好的健壮性
无中心管理节点
采用自组织协同算法形成网络
其组网算法比较复杂
2.分级网络结构（层次网络结构）
层次网络结构
平面网络结构的一种扩展拓扑结构
网络分为上层和下层
上层为中心骨干节点
下层为一般传感器节点
骨干节点之间采用平面网络结构，为对等结构
骨干节点有着相同的mac 、路由、管理、安全等功能协议
一般传感器节点可能没有路由、管理及汇聚处理等功能，可能不能直接通信
特点：扩展性好、便于集中管理，降低系统的建设成本，提高网络覆盖率和可靠性。
管理开销大，硬件成本高
3.混合网络结构
平面网络结构和分级网络结构的一种混合拓扑结构
网络骨干节点之间及一般传感器节点之间都采用平面网络结构
网络骨干节点和一般传感器节点之间采用分级网络结构
与分级的不同点：
一般传感器节点可以直接通信，不需要通过汇聚骨干节点来转发数据
支持的功能更加强大，所需成本更高
4.Mesh网络结构
也称为对等网
规则分布的网络
不同于完全连接的网络结构
通常只允许和节点最近的邻居通信
内部节点一般都相同
采用分级网络结构技术可使Mesh网络路由设计简单化
一些数据处理可以在每个分级的层次里面完成
适合于WSN分布式信号处理和决策
理论上是规则结构，但实际中不必是规则的Mesh结构形态
单点或单个链路有较强的容错能力和鲁棒性。
特点
无线节点构成网络
每个节点至少可以和一个其他节点通信
支持多跳路由：来自与一个节点的数据在其到达下一个主机网关或控制器之前，可以通过多个其余节点转发。
功耗限制和移动性取决于节点类型和应用
存在多种网络接入形式
2.2无线传感器网络覆盖
2.2.1 无线传感器覆盖问题
覆盖问题是WSN配置首先面临的基本问题
节点任意分布在配置区域，反映WSN区域被监测和跟踪的状况
传感器网络的部署、监测、覆盖与连接的关系
面向特定的应用需求，其核心思想都是与覆盖问题有关的
1.无线传感器网络覆盖理论基础
艺术馆问题
艺术馆问题(Art Gallery Problem)。
目标：艺术馆业主想在馆内放置照相机，预防小偷盗窃。
假设：假定相机可以有360度的视角而且可以极大速度旋转，相机可以监视任何位置，视线不受影响。
问题：需要多少台相机？分别应放置在哪些地方？才能保证馆内每个点至少被一台相机监视到
优化：所需相机的数目应该最小化
建模：二维平面的简单多边形
方法：简单多边形用三角测量法拆分
解决：两个监视相机在二维平面可以得到最优解
扩展：三维空间，这个问题就变成了NP-hard问题了
圆覆盖问题
圆覆盖问题
问题：在一个平面上最多需要排列多少个相同大小的圆，才使其能够完全覆盖整个平面。
优化：给定圆的数目，如何使得圆的半径最小
解决：A．Heppes和J．B．M．Melissen实现了矩形平面的圆最优覆盖问题，5个圆、7个圆
2.无线传感器网络覆盖的计算
（1）贪婪算法
Andrew Howard等专门针对移动无线传感器网络提出了一种增量自我配置的贪婪算法(Greedy and Incremental Self-deployment Algorithm)
基本思想：
每次配置一个节点到未知区域，每个加入的节点都充分利用先前配置的节点收集到的信息来确定其最佳目标位置。
目的：
使网络的覆盖最大化，而同时又确保节点彼此保持视距通信，即本地化
核心：
贪婪和增量，该算法的复杂度为 O(n2)，其中n 为配置的传感器节点数目
（2）电势场技术
A．Howard等提出了
基于电势场技术的未知环境移动传感器网络的部署配置方法，网络内的节点可以随意扩展，使得网络覆盖最大化
基本思想：
将节点当做假想的物粒子，且受到势力场的势力。势力压迫节点彼此之间和障碍物之间发生作用力。通过节点的初始简易配置快速地在整个网络扩散，从而最大化网络的覆盖。
核心：
利用了电势场技术，具有较高的鲁棒性和扩展性
（3）决策问题
Huang和Tseng提出
基于传感器数目的多项式时间算法，将覆盖问题抽象表述为一个决策问题，并验证了一个传感器配置是否提供了k 阶覆盖。
目标：
确定无线传感器网络服务区域中的每个点是否至少被k 个传感器节点监视覆盖
时间复杂度 O(ndlogd)，
n为传感器数目，d为和一个传感器感应范围交叉的最大床更年期数目。
（4）连接选择
Gupta提出的算法是
通过选择连接的传感器节点路径来得到最大化的网络覆盖效果。
该算法同时属于连接性覆盖中的连接路径覆盖及确定性区域点覆盖类型。
当基站或汇聚中心向无线传感器网络发送一个感应区域查询消息时，
连接传感器覆盖的目标是选择最小的连接传感器节点集合并充分覆盖无线传感器网络区域。
Gupta分别给出了集中与分布式两种贪婪算法。
连接选择过程
从最新加入的候选节点开始执行，广播候选路径查找消息
收到候选路径查找消息的节点判断自身是否为候选节点
如果是，则以单播方式返回发起者一个候选路径响应消息
发起者选择可以最大化增加覆盖区域的候选路径，更新各参数，算法继续执行
直到网络查询区域可完全被更新后的区域所覆盖。
一般准则
如已知节点的通信距离，可以通过提出的方法得知所需配置的节点数，然后选择适当的感知覆盖半径
如已确定感知覆盖半径，可先计算出布置的节点数，然后选择合适的通信距离或调整控制传感器节点功率大小
如通信距离和感知覆盖半径都确定的情况下，只有增加或减少节点数来满足给定的最低连接可靠性和成本设计要求
覆盖算法和协议分类
2.2.2无线传感器网络区域覆盖
1.能效性随机覆盖方法
无线传感器网络能效性设计能够延长网络寿命，满足无线传感网络对节点能耗的限制。
通过规划各节点工作状态，在同一时间段中仅让部分节点激活而让其余冗余节点尽可能长时间的处于休眠状态，以延长网络寿命。
在设计这些机制的时候应当着重考虑以下问题：
(1)节点是否进入休眠状态应当遵循何种规则?
(2)节点何时需要做出决定?
(3)节点在休眠状态需要停留多长时间?
目标：
通过控制各节点的位置和工作状态提高无线传感网络的覆盖和能效性
同时间段内有且仅有一个集合处于工作状态，其它集合则进入休眠状态。
各集合通过轮休节约网络能耗。
由此可知，通过最大化可用集合的数量，可以延长各节点切换到工作状态的时间，从而延长网络寿命。
最大约束-最小约束算法能有效计算分散的覆盖区域
非轮值检测规则检查各节点监测区域是否与其周围节点感知区域相重合，
2.连接性随即覆盖方法
无线传感网络的连接性也是网络性能的重要评价指标。
当任一激活节点都能与其余激活节点通信时，网络则处于连通状态
当节点布置完毕后，节点必须能够相互连通，获取的信息才可以返回接收器或控制器中
保证监测区域的覆盖性和节点的有效连通性对于确保网络测量性能而言都是十分重要的
分布式最优地理密度控制算法(OGDC，Optimal Geographical Density Control)
假设任何时刻，节点可能处于3个状态中的一种：未决定、开和关
网络初始化时，随机激活若干节点。而后这些节点将在网络中广播“能源开”的信息，同时将其自身状态设置为开
所传递信息包含：①发送者的位置；②下一个工作节点的位置与方向
网络中每个节点都保留邻近节点的信息列表
覆盖结构协议(CCP，Coverage Configuration Protocol)是另一种用于优化网络连接性的网络协议。
该协议能动态组织网络，为各类应用提供不同的覆盖度。为提高算法运算速度，每个节点都包含周围节点的信息列表，并周期性发送信息以广播自身的位置和状态。
混合网络动态能量管理策略步骤：
①当节点同时满足SPAN和CCP的评价标准时，它由休眠状态转变为激活状态
②当节点既不满足SPAN又不满足CCP评价标准时，节点由激活状态变为休眠状态
混合网络动态能量管理策略既能够通过CCP方法实现k覆盖，又能在SPAN方法的支持下保证单点连接
基于NS-2的仿真结果显示，该混合算法在覆盖比例、工作节点数量、系统工作时间等指标上都具有很好的优化效果。
2.2.3无线传感器网络的点覆盖
随机型点覆盖
可以将所有的分散集合看做是分散覆盖集合，而确保每个集合都能监测所有的目标点
确定型点覆盖
采用最少的节点对确定目标点集进行监测，同时保证节点间有效通信
2.2.4无线传感器网络的边界覆盖
当前研究的边界覆盖问题包含两种边界覆盖模型
第一种模型：在一个区域中布置节点，已知一个要穿过该区域的起始和终止位置，测定该区域的最大突破路径(MBP，Maximal Breach Path)和最大支持路径(MSP，Maximal Support Path)
MBP和MSP分别与最差和最优覆盖相关
分别对应于使路径中的每个点与最近节点之间的距离最大(最小)的情况
第二种边界覆盖问题模型是基于目标暴露的模型。该模型假设当测量距离增加时，节点的测量精度随之下降，除此之外，测量时间(即目标暴露时间)也是一个很重要的因素。通常测量时间越长，对应的测量精度也越高。节点的二维感知模型可定义为：
式中，d (s，p)为传感节点s与点p间的欧式距离， 和k是传感节点的相关参数。
2.2.5无线传感器网络覆盖能效评价指标
1.覆盖指标
由于节点布置的固有冗余性，网络覆盖评价采用了可靠度的概念。
对一定区域，若在t 时刻处于n 个节点测量范围内，该区域综合可靠度表示为
式中，ri (t)表示第i 个节点的测量可靠度。
2.能耗指标
无线信号在传播过程中随着传播距离增加而发生衰减，采用自由空间模型计算传播损耗如下：
式中，Lp为路径损耗；D为传播距离；λ为信号波长。
针对无线信号传播过程，假设通信能耗模型为：运行发送器或接收器的无线花费为Eelec=50nJ/bit，发送放大器实现容许放大倍率的无线花费为Eamp=100pJ/bit ×m-2。
二维空间内，坐标分别为(xi，yi)、(xj，yj)的无线传感节点i、j，通信时信号传播距离计算如下：
若节点i向j发送长度为k bit的数据包，则节点i能耗为：
节点j接收此数据包的能耗为：
节点i与j节点，进行一次数据包传输所消耗的总能量为：
说明两节点相距较远时，直接传输数据会消耗较大能量，采用多跳通信则可节省能量。
2.3无线传感器网络的连接可靠性
2.3.1无线传感器网络连接可靠性分析
对于无线传感器网络设计，通常会遇到两个关键问题：
①在给定布置区域大小和节点无线收发距离(即通信半径R)的条件下，究竟要布置多少个无线传感器网络节点才能连通一个网络，且连接的可靠性能满足多大的需求；
②给定节点感知覆盖距离(即感知距离半径)的条件下，如何布置节点才能实现对给定区域的有效覆盖和监测。
连接可靠性是一个稳定运行的WSN设计必须面临的基本问题，通常有两种主要的理论研究方法和途径：
一种是基于图的连接性；
另外一种是基于扩散理论的连接性。
通常WSN用连接概率来表示网络的连接性，而用每个节点邻居数不低于某个特定值来表示网络的连接可靠性需求
连接度为在其通信传输距离范围内的平均邻居节点数，邻居节点数越多，网络连接度越强
连接性是和连接度成某种分布关系的。连接度CD (Connection Degree) 可反映网络的连接性
为简化模型，假设无线传感器网络是采用全向天线情况下的同构网络，传输通信半径为R，感知覆盖距离半径为R’，实际网络配置区域为L×W的矩形带状区域，这样CD就集中反映了传感器节点数n、实际物理布置区域大小以及每个节点的无线传输通信半径R三种因素的相互关系，D表示节点密度，L和W分别表示矩形域的长和宽。
值得注意的是，无线网络特有的隐藏或暴露终端问题产生的节点干扰距离半径R’(感知距离半径)通常满足条件R<R’<2R，如前公式所示。网络连接度和同频干扰会随着节点数增加而增强，同样增大通信距离范围或减小网络布置区域大小也会增大网络连接度和同频干扰。因此，选择适当的网络连接度对网络性能有着重要的意义。
影响可靠连接的另一个重要参数为网络的冗余度。不考虑链路相互干扰等情况，冗余度K越高，网络的连接性越强。冗余度是指在无穷维节点阵列空间连接的链路节点比。
如图(a)中表示连接性最弱的冗余度K=1，例如一个环状或线性网络。网格网络冗余度可以是K=1.5，2，3，4等，如图 (b)～(e)所示。
网格扩散(Percolation)方法给出了冗余度如何影响连接性的一个很有效的估计。暂不管扩散的方向和路径如何，仅考虑最大连接节点数目所占比例Cmax与单个链路故障概率Pd的关系，在给定某个冗余度K，如K=1，2，3和4，可以得到Cmax与单个链路故障概率Pd之间的变化关系
2.3.2 基于概率和图论的连接可靠性
图分为有向图和无向图两种。无向图是指在图的顶点与顶点之间存在的边是无向边。由于网络拓扑的不确定性，可将无线传感器网络抽象成一个随机的无向图Gp(n)，其中n为图中的顶点数(表示传感器网络的节点数)，p为任意两个节点之间的连接概率。在随机无向图Gp(n)中，链路之间的连接是相互独立的事件。节点的度定义为与节点直接相连接的节点数目，即节点的直接邻居数。图Gp(n)中，节点的度服从二项分布：
式中，z为平均节点度，即z=E[d]=(n-1)p；右式为节点数n较大时的泊松近似结果。
l/n 所有节点度的总和/所有节点
2.3.3 基于扩散理论的连接可靠性
由许多正方形格子组成的区域，每个格子随机被小圆点填充占据，格子被占据的概率为p，这样整个区域会形成许多格子簇(Cluster)。簇是由相邻的被小圆点占据的格子组成的，相邻的格子之间有一条公共边。扩散理论(Percolation)就是对簇的数目和特性进行研究的理论。
扩散理论——布尔模型
节点按照泊松点过程分布。当两个节点间的距离小于等于发射半径时，能够相互连接。因此，在一维网络中，如泊松点过程为半径为r/2的圆的中心，两节点间的距离按指数分布，则不存在扩散现象。
当给定r和 时，距离为x的两节点连接的概率为:
从式可知，随着x增加，两节点间的连接概率按指数规律下降。如果在二维网络中有下面的定理：
对于给定的r，存在临界的节点密度，且当节点密度 ，网络由无限个有限簇组成，即网络不连接；当节点密度 ，网络由唯一的无限簇组成，则网络全连接。
扩散理论——SITIRG模型
信噪比图模型STIRG (Signal To Interference Radio Graph)定义为：如果节点j 收到从节点i发送的信号信噪比大于某个门限制 ，则节点j 将能接收到从节点i 发送来的数据。
式中， 为干扰因子，N0为热噪声。
当 时，即无干扰情况下，节点能与某一固定范围内的节点进行通信(与节点发射功率有关)，则存在临界节点密度 (与布尔模型相同)。
当 时，由于存在干扰，网络图中会形成许多节点数目较少的簇，从而导致网络不连接或连接较差。因此干扰因子 存在临界值 。
当 ，则可能存在扩散现象；当 时，无论节点密度如何，网络中不存在扩散现象，即网络不连接。