无线传感器网络覆盖连通性研究

3基于代理的不可达节点解决方案

在本节，针对第2节中在无线传感器网络部署区域内节点对于基站不可达的情况，例如，由于障碍物的存在或者位于基站射频传输范围之外使得一些节点成为基站不可达节点，提出了一种在基站可达的节点中寻找一个节点作为代理来解决基站与不可达节点之间连通性问题的方案。

3.1基本思想及定义

首先，给出方案的基本思想以及一些定义。

不失一般性，可以假设基站至多以2跳的方式

到达所有的部署节点，对于所有直接到达节点的跳数为1，其余的都简化为2跳，并且认为基站可达的节点可以作为基站转发传感数据的中继节点。从这些中继节点中选出某些节点作为代理，使其作为基站与不能接收基站信息的不可达节点之间的通信中介。我们考虑使代理节点和其周围基站不可达节点形成组，代理节点作为该组的“组长”，负责在基站和基站不可达节点之间的通信中介。

假设S为部署在监测区域的节点集合，|S|=n，基站（basestation）记为B，同时又设SR和SUR分别为部署区域内基站可达和不可达节点的集合，SR和SUR定义如下：



值得注意的是，由于在实际部署区域存在某些节点其传输信号不被其他任何节点获悉，如掉入部署区域深坑的节点，集合SR∪SUR往往并不等于集合S。因此，在节点部署阶段，使基站为每个传感器节点建立以下属性参数。

Blink：节点与基站连接状态，取值为0或1，而分属SR和SUR集合；

Nlist：集合SR中节点的所有邻居节点；

Hlist：在基站信息传输范围之内节点的跳数表。

Glist：节点成组的成员参数。

3.2基于节点代理的方案

在方案中，使得选取的代理节点和不可达节点形成相应的组的目的是通过代理使该组中不可达节点可以与基站连通，因此，方案主要是在集合SR中设计一到多个代理节点，负责转发基站信息到集合SUR中的相关节点，同时，负责作为SUR中的相关节点的采集信息发送到基站的中转站。

在设计代理和不可达节点的组时，追求一种平衡代理负载的算法以延长代理节点的寿命，在算法中，基站为每个节点增加一个属性参数，称为Aid，在集合SUR中用以标识节点被分配给哪个代理节点，而其他属于集合SR中的节点的Aid=0，另外，基站为集合SR的每个候选代理节点设置一属性参数Glist用以识别其组成员。组的形成过程描述如下。

1)对于每个节点
,基站计算其与集合SR中相邻节点的Hlist值，并对获得的节点Hlist值按照升序排列；

2)对于1)中节点Hlist排序结果由低到高（顺序），在集合SR中依次为SUR中节点分配一个代理节点，此时存在2种情况，处理如下：
if|Hlist(sj)|=1

标记Aid(sj)=si,分配sj到惟一连通的节点si;加sj到Glist(si)中
else if | Hlist(sj)|>1

为sj计算分配到SR中的多个连通节点的成本Acost
标记Aid (sj)=sk,当sj分配到集合SR中节点sk时Acost最小;加sj到Glist(sk)中

在方案中，对于节点，如果在集合SR中存在多个节点与其连通，将会选择与节点sj具有最小通信代价（此时为sj分配到集合SR中节点sk的通信成本Acost）的节点作为其代理，衡量Acost的2个重要因素是监测区域内的组成员和“组长”即代理节点。一种理想的情况是对于SUR中的节点sj，当其分配到一个组中时，该组的代理节点应满足在所有的Hlist(sj)中是最小的，即离sj最近的节点，这样节点间的通信能量耗费最小。另一方面，希望在所有的代理节点之间实现负载均衡以延长网络使用寿命，在传感器网络中，首个节点“死亡”时间是衡量网络性能的重要尺度[16,17]。定义节点sj分配到以节点sk为代理的相应组的代价为

Acost(k)=r1×(sj到通信成本)+r2×|(Glist(sk)|

其中，sj到si通信成本的计算基于节点sj和si的距离，r1+r2=1，参数r1和r2是动态可调节的量，取值与Acost(k)中sj到si通信成本和|(Glist(sk)|在节点成组过程中所占的比重成正比。

4无线传感器网络覆盖连通性判定算法

正确获悉覆盖在部署区域内节点的连通性相关信息对网络决策、管理、研究与应用具有重要的基础性作用，针对上面建立的一般意义上的无线传感器网络的系统模型，考虑到现实意义上的基站和智能节点可以存储相关的节点间路由信息，如基站可以获悉其他传感器节点的能量剩余信息，可以发送相关的控制信息与参数到相应节点，节点可以存储、转发网络信息并存储相关的节点间路由信息。基于此，提出了在无线传感器网络应用之前根据节点存储的相关参数信息和路由信息进行网络节点连通性判定的算法。

算法中使用结构类型定义节点，具体如下：
节点结构定义
StructNODE{
NodetypeN;//节点类型，区分基站和普通节点
floatE;//节点能量值
boolv;//节点访问标志
NODE*n[];//指向下一跳节点的指针集
}

算法为基于深度探测的网络覆盖连通性判定算法DBDAFNCJ(depthbaseddetectionalgorithm for network connectivity judgment)，下面具体介绍。