降低网络能耗、限制网络平均节点度以及提高网络容错性是无线传感器网络(Wirelesssensor networks, WSNs)中的重要问题, 而拓扑控制算法的主要任务是在满足网络连通性和覆盖性的前提下, 使得网络中各个节点依据给定的规则从它的物理邻居节点间选取合适的逻辑邻居节点, 形成一个优化的网络结构, 以达到降低网络能耗^[1-4], 限制平均节点度, 提高网络容错性的目的.

降低网络能耗是能量受限网络协议设计的首要目标.由于传感器节点的体积限制, 其可用能量必然有限^[5], 因此, 对于能量受限的无线传感器网络来说降低网络能耗是构建拓扑结构需要考虑的首要因素.目前, 拓扑控制技术中主要有两种节能策略: 1)通过调节网络中各节点的传输功率实现降低网络能耗的目的; 2)是将网络中部分节点调节为休眠状态以达到降低网络能耗的目标.本文为进一步降低网络能耗, 采用睡眠调度与功率控制方案, 以更好地实现节能降耗目标.

有效限制平均节点度是拓扑控制技术中的另一个重要设计指标.网络节点度是指与该节点存在直接通信链路的一跳邻居节点的数目.在无线传感器网络中, 高的网络平均节点度需要在MAC (Media access control)层设计相应的接入访问控制机制, 节点度过高时还可能引发访问冲突和数据碰撞, 浪费节点有限的能量.因此, 密集部署的无线传感器网络中, 限制网络的平均节点度是十分必要的.

网络的容错性能是拓扑构建过程中需要考虑的另一个重要指标.无线传感器网络经常部署于恶劣的环境中, 一旦网络中某个节点遭到破坏或能量耗尽, 将可能导致整个网络瘫痪以致其不能正常运行.因此, 在拓扑控制算法的设计中需要考虑网络的容错性.

基于上述设计目标, 本文提出了一个基于Voronoi覆盖及Delaunay三角剖分图的无线传感器网络最小刚性拓扑控制算法(Minimal rigid topology control algorithm based on Voronoi coverage and Delaunay triangulation, MRTc), 该算法基于Voronoi原理调节节点的活动状态, 实现了目标区域的全覆盖, 在此基础上基于Delaunay三角剖分图构建了最小刚性拓扑结构.本文的主要贡献为: 1)采用睡眠调度与功率控制相结合的方法, 在保持网络连通的情况下进一步降低网络能耗; 2)提出定理, 为构建基于Delaunay三角剖分图的最小刚性拓扑提供了理论依据; 3)充分利用最小刚性拓扑的特性, 即2-容错、稀疏性以及平均节点度有限等特点, 实现了提高网络鲁棒性、简化路由计算、降低节点间干扰的目标.

本文用到的符号	符号的含义
${G_u}({\mathcal {V}_u},{\mathcal {E}_u})$	网络节点构成的无向图,${\mathcal{V}_u}$为网络中节点的集合,${\mathcal{E}_u}$为可相互通信的链路集合;
${\bar G_u}({\bar {\mathcal {V}_u}},{\bar {\mathcal {E}_u}})$	冗余节点构成的无向图,${\bar {\mathcal {V}_u}}$为冗余节点的集合,${\bar {\mathcal {E}_u}}$为互为 Voronoi 邻居的冗余节点间的链路集;
$G(\mathcal {V},\mathcal {E})$	传感器节点构成的网络拓扑,${\mathcal{V}}$为构成拓扑的传感器节点的集合,${\mathcal{E}}$为拓扑中链路的集合;
${G_m}({\mathcal {V}_m},{\mathcal {E}_m})$	传感器节点构成的最小刚性拓扑,${\mathcal {V}_m}$为最小刚性拓扑中节点的集合,${\mathcal{E}_m}$为最小刚性拓扑中链路的集合;
${G_C}({\mathcal {V}_C},{\mathcal {E}_C})$	传感器节点形成的初始拓扑;
${G_D}({\mathcal {V}_D},{\mathcal {E}_D})$	经算法 MRTc 优化后得到的拓扑结构;
${G_j}({\mathcal {V}_j},{\mathcal {E}_j})$	节点$j$与其邻居节点构成的基于 Delaunay 三角剖分图的局部最小刚性拓扑,${\mathcal {V}_j}$为节点$j$与其邻居节点的集合,${\mathcal {E}_j}$为该最小刚性拓扑中链路的集合;
${\hat G_i}({{\mathcal {V}_i}},{\hat {\mathcal {E}_i}})$	由拓扑 ${G_i}({\mathcal {V}_i},{\mathcal {E}_i})$改变圈内的链路生成的新拓扑,${\mathcal {V}_i}$为节点$i$与其邻居节点的集合,${\hat {\mathcal {E}_i}}$为生成新拓扑的链路的集合;
${G_{ij}}({\mathcal {V}_{ij}},{\mathcal {E}_{ij}})$	由拓扑 ${\hat G_i}({{\mathcal {V}_i}},{\hat {\mathcal {E}_i}})$和拓扑${G}({\mathcal {V}_j},{\mathcal {E}_j})$的公共节点组成的拓扑,${\mathcal {V}_{ij}}$为两个拓扑的公共节点的集合,${\mathcal {E}_{ij}}$为两个拓扑的公共链路的集合;
$G'$	拓扑结构$G$的一个子拓扑;
$G''$	子拓扑$G'$有相同节点的另一个刚性拓扑;
$\hat G$	刚性拓扑$G''$代替子拓扑$G'$得到的拓扑;
$({l_u})_i^j$	无向图中可以相互通信的节点间的链路;
$({\bar l_u})_i^j$	互为 Voronoi 邻居的冗余节点间的链路;
$l_i^j$	网络拓扑中可以相互通信的节点间的链路;
${l'_q}(q=1,\cdots,m)$	局部最小刚性拓扑$G_i$中的$m$条链路;
${l'_p}(p=1,\cdots,m)$	局部最小刚性拓扑${{G}_{j}}(i\ne j)$中的$m$条链路;
${\mathcal {N}_i}$	节点 $i$的通信邻居的集合;
${\mathcal {N}_i}^\prime $	节点$i$的逻辑邻居节点集合;
${D_i}$	节点$i$的度;
$i_2^{VV}$	节点$i$的 2-Voronoi 顶点;
$i_2^{VIP}$	节点$i$的 2-Voronoi 交点;
${q_i}(t)$	节点$i$的位置函数;
$(q_i^1,q_i^2)$	节点$i$的位置坐标;
$id(i)$	节点$i$的 ID;
$P_i^j$	节点$i$和$j$信息成功传输所需的功率;
$d_i^j$	节点$i$和$j$的欧氏距离;
$w_i^j$	链路$l_i^j$的权重函数;
${r_c}$	节点的通信半径;
${r_s}$	节点的感知半径;
$M$	Delaunay 三角剖分图对应的刚性矩阵;
${M_{f}}$	最小刚性图对应的刚性矩阵;
${D_{ev}}$	网络的平均节点度;
$|\mathcal {E}|$	拓扑结构中链路的数目;
${a_s}$	拓扑${\hat G_i}$与${G_j}$的公共链路;
${b_{s1}}$	${\mathcal {E}_{ij}}$中仅存在于${\hat G_i}$中的链路;
${b_{s2}}$	${\mathcal {E}_{ij}}$中仅存在于${G_j}$中的链路;
${r_a}$	每个网格的长度值;
${r_b}$	每个网格的宽度值;
${E_{Tx}}(k,d)$	节点传输$k$bits 信息所需的发射能耗;
${E_{Rx}}(k)$	节点传输$k$bits 信息所需的接收能耗;
$d$	传输距离;
${E_{elec}}$	发射电路和接收电路的能量消耗;
${\varepsilon _{fs}}$	自由空间传输模型系数;
${E_{0}}$	节点的初始能量.

下载: 导出CSV 

| 显示表格

1.   相关工作

作为无线传感器网络的基础技术, 拓扑控制技术已引起学者的广泛关注^[6-15].通过拓扑控制, 可以有效降低网络能耗、限制节点度以及提高网络的容错性.

降低网络能耗是拓扑控制算法需要首先考虑的设计目标.近几年来, 研究人员提出了多种面向节能应用的拓扑控制算法^[6-9], 其节能方案主要有功率控制和睡眠调度两种.对于功率控制而言, 其主要思想为通过调节网络中所有节点的功率来降低网络能耗.例如文献[6]中的COMPOW (Smallest common power)算法和文献[7]中的CBTC(Cone-based distributed topology-control)算法.COMPOW算法中所有节点采用能够保持整个网络连通的最小功率, 统一的功率设置确保了网络中链路的双向连通性, 且功率的最小化达到了降低网路能耗的目的.CBTC算法中每个节点则通过调整各自的传输功率, 使得以该节点为中心, 当在任意角度$\alpha (\alpha \le 5\pi /6)$的扇形区域内至少存在一个邻居节点时, 能够保持网络的连通性, 降低网络能耗.在睡眠调度方面, Chen等^[8]提出的Span算法其基本思想是:在维持网络连通性的前提下, 网络中每个节点根据其剩余能量、邻居节点个数以及节点效用等多种因素, 自适应地判定该节点成为骨干节点或休眠节点.对于MSNL (Maximization ofsensor network life)算法^[9]而言, 节点状态可细分为活动、休眠以及过渡状态.处于过渡状态的节点将进行实时监测, 且当其发现自身的监测区域不能被其余处于活动状态或过渡状态的节点覆盖时, 此过渡状态节点转化为活动状态.上述4种算法均采用睡眠调度或功率控制中的一种方案面向节能设计而缺乏对多种方法的结合的运用.本文针对上述弊端, 提出了基于Voronoi覆盖的睡眠调度与功率控制相结合的方案, 进一步降低网络能耗.

作为拓扑控制技术的重要设计目标之一, 节点度的限制问题已成为国内外学者的研究热点.文献[10]中, Li等提出了LMST (Local minimum spanning tree)算法, 算法中节点相互独立地构建局部最小生成树, 并根据邻近图中与之距离最远的逻辑邻居节点确定自身功率.此外, 文献中证明了LMST算法中每个节点的节点度均不大于6, 网络的平均节点度接近于最小生成树算法, 略高于2, 可见该算法限制了网络的平均节点度.在LMST算法基础上, 文献[11]通过定义每条链路的临界能耗, 提出一种基于LMST的改进算法X-LMST.它旨在以链路的能量有效性为指标, 构建局部最小生成树, 网络中节点的度数不多于6.LMST算法和X-LMST算法虽然限制了网络平均节点度, 但是这两个算法均是1-容错的, 如果网络中的某条链路因节点能量耗尽或环境干扰而意外中断, 将会导致网络失效. Delaunay三角剖分图和UDG (Unit disk graph)图相结合, 删除Delaunay三角剖分图中不能相互通信的链路, 构建出Udel拓扑结构^[12], 该拓扑是$t$-支撑的, 并且经Udel算法优化后得到的拓扑结构的平均节点度不高于6.然而, 该拓扑结构是集中式拓扑, 需要已知网络的全局信息.

容错性是拓扑控制技术的另一重要设计目标.目前, 已有较多文献关注网络容错性能的研究.文献[13]中Xu等提出了一个典型的睡眠调度算法GAF (Geographical adaptivefidelity), 它以划分网格的方式将节点分组, 通过睡眠调度的方法使每个网格中仅保留一个活动节点, 网格内其余节点则调节为休眠状态, 以降低网络能量消耗.理论上, GAF算法是~4-容错的, 有着良好的容错性能.但是, GAF算法中节点的平均度数较大.过高的节点度会在节点间引发较严重的干扰和冲突, 严重时引起数据包重传, 造成不必要的能量浪费.苏金树等^[14]提出了一种容错算法, 该算法在局部最小生成树(LMST)的基础上, 通过增添链路的方式减少网络拓扑结构中的割边和割点的数目, 构建了一个2-容错的拓扑结构.实验证明, 该拓扑具有一定的网络容错性能.然而, 该算法在删除拓扑的割边和割点时, 需要已知网络的全局信息, 增加了算法的计算复杂度.文献[15]中提出的$FGS{S_k}$ (Fault-tolerantglobal spanningsubgraph)算法是Kruskal最小生成树算法在$k$-容错的网络中的推广, 它是一个集中式的拓扑控制算法.此算法通过插入较短链路的方式构建了一个$k$-容错的拓扑结构, 由于该算法是集中式算法, 网络中所有节点均需了解全局信息, 因此, 该算法的计算量较大.

针对上述算法的局限性, 本文综合考虑了网络能耗、平均节点度以及容错性三方面内容, 提出了基于Voronoi覆盖及Delaunay三角剖分图的无线传感器网络最小刚性拓扑控制算法.该算法首先依据Voronoi覆盖原理, 判断网络中的覆盖冗余节点, 在保证网络区域全覆盖的条件下, 将其调节为休眠状态.然后, 在活动节点间, 构建基于Delaunay三角剖分图的无线传感器网络最小刚性拓扑结构.算法中睡眠调度与功率控制相结合, 在保持网络连通性的情况下, 进一步降低网络能耗.文中所提出的定理对于构建具有~2-容错、稀疏性的网络拓扑结构, 提高网络鲁棒性, 有效约束平均节点度, 提供了理论依据和基础.文中第4节分析证明了MRTc算法的性能; 算法性能评估与结果分析在第5节给出.

2.   网络模型与定义

2.1   网络模型

在二维空间中, 无线传感器网络可用一个无向图(Undirected graph)$G_u(\mathcal {V}_u,\mathcal {E}_u)$来表示.其中, $ {\mathcal{V}_u} = {\rm{\{ }}1,2,\cdots,n{\rm{\}}}$表示无线传感器网络中节点的集合; ${\mathcal {E}_u} = {\rm{\{}}({l_u})_i^j,i \in {\mathcal {V}_u},j \in {\mathcal {V}_u}{\rm{\}}}$为网络中节点间可相互通信的链路集.在同构网络中, 如果两个节点$i$和$j$的欧氏距离$d_i^j$满足$d_i^j \le {r_c}$ (其中, ${r_c}$为节点的通信半径), 则称节点$i$与$j$互为通信邻居^[16].若两节点可相互通信, 链路$({l_u})_i^j \in {\mathcal {E}_u}.$本文中, $\mathcal {N}_i$为节点$i$的通信邻居的集合, 集合$\mathcal{N}_i$中的元素个数(集合$\mathcal{N}_i$的势)定义为节点$i$的度${D_i}$ (${D_i} = \left| {\mathcal{N}_i} \right|$, 也可简称为$i$的节点度).网络中所有节点的度的平均值${D_{ev}}$称为网络平均节点度(${{D}_{ev}}=\sum\nolimits_{i=1}^{n}{{{D}_{i}}}/n=\sum\nolimits_{i=1}^{n}{\left| {{N}_{i}} \right|}\text{ /}n)$).

为了方便后文分析, 给出以下常用定义.

定义1 ($\pmb k$-容错).在无线传感器网络中, 如果删除$k-1$条链路后网络仍然保持连通性, 则称该网络是$k$-容错的, 也称该网络是$k$-连通的.

定义2(稀疏性)^[5].网络拓扑生成后, 若拓扑中的链路数目与节点数目满足线性关系, 则称该网络拓扑具有稀疏性.

定义3(区域完全覆盖).如果监测区域内的任意一点均能够被至少一个活动节点成功感知, 则称该监测区域被完全覆盖.

本文假设无线传感器网络是同构网络, 即网络中所有节点的属性相同, 且节点的位置信息已知.节点的通信范围和覆盖范围(也称感知区域)可以看作以节点为中心, 分别以通信半径${r_c}$和感知半径${r_s}$为半径的圆盘, 并且网络中每个节点具有唯一的身份标识ID.

此外, 我们引入一种常用于无线传感器网络中的无线传输能量消耗模型^[16].在该模型中, 节点的工作能耗由发送器能耗和放大器能耗两部分构成, 接收能耗为接收器能耗.网络节点的发射消耗与传输距离$d$有关.因此, 节点传输$k$ bits的信息所需的发射能耗为

接收$k$ bits信息的接收能耗为

其中, ${E_{elec}}$为发射电路和接收电路的能量消耗, $k$为传输数据比特数, ${\varepsilon _{fs}}$为自由空间传输模型系数.

2.2   Voronoi覆盖原理

无线传感器网络中, 由于大量节点部署于监测区域内, 部分区域可被多个节点同时覆盖, 同一监测信息也可被多个节点重复感知, 导致大量的冗余感知数据.针对该问题, 本文采用Voronoi覆盖方案, 将网络中的覆盖冗余节点调整为休眠状态, 在保证网络区域完全覆盖的前提下降低网络能耗.为了清楚地阐述Voronoi覆盖原理, 给出以下定义4～定义7.

定义4(感应邻居).在网络中, 如果一个节点$i$的感知区域和另外一个节点$j$的感知区域相交$(i \ne j)$, 则称这两个节点$i$, $j$互为感应邻居.

定义5(Voronoi邻居).在二维无线传感器网络中, 如果节点$i$所形成的Voronoi多边形与节点$j$所形成的Voronoi多边形共边, 则称节点$i$和节点$j$互为Voronoi邻居.

定义6 (2-Voronoi图).在网络拓扑中, 如果去掉节点$i$后, 由$i$的Voronoi邻居构成的Voronoi图称为节点$i$的2-Voronoi图.节点$i$的2-Voronoi图的顶点称为2-Voronoi顶点, 记为$i_2^{VV}$.节点$i$的2-Voronoi图的边与节点$i$自身覆盖圆盘边界的交点, 称为2-Voronoi交点, 记为$i_2^{VIP}$.

举例而言, 图 1为节点$i$的2-Voronoi图.其中, 节点$j$, $k$, $m$, $n$均为节点$i$的Voronoi邻居节点.由图 1可知, 节点$i$的2-Voronoi顶点有两个, 分别为$i_2^{VV1}$和$i_2^{VV2}$.节点$i$的2-Voronoi交点有4个, 它们分别为$i_2^{VIP1}$, $i_2^{VIP2}$, $i_2^{VIP3}$和$i_2^{VIP4}$.

图 1  节点$i$的2-Voronoi图

Fig. 1  The 2-Voronoi diagram of node $i$

下载: 全尺寸图片 幻灯片

定义7 (冗余节点).如果一个节点的感知区域被其他节点完全覆盖, 我们就称该节点为冗余节点.

为了简化计算, 我们使用引理1仅根据节点感应邻居的信息分布式地判断节点的冗余性.文献[17]证明了引理1的复杂度仅为${\rm O}(N{\rm log}N)$, 其中, $N$为单个节点的Voronoi邻居的个数.

引理1^[17].节点$i$是一个冗余节点的充分必要条件是节点$i$的2-Voronoi顶点和的2-Voronoi交点均被其Voronoi邻居覆盖.

然而, 在使用引理1判断冗余节点时, 如果两个冗余节点互为Voronoi邻居节点, 同时将它们调节为休眠状态后, 它们感知区域的交叉区域可能不会被完全覆盖.为了解决该问题, 本文将所有冗余节点看做一个新的无向图${\bar G_u}({\bar {\mathcal{V}}_u},{\bar {\mathcal {E}}_u})$, 其中, ${\bar {\mathcal{V}}_u}$为所有冗余节点的集合, ${\bar {\mathcal{E}}_u}$为互为Voronoi邻居的冗余节点间的链路集.然后计算图${\bar{G}_u}$的最大独立集¹, 最大独立集中的节点即为覆盖区域的盲节点.为了保证监测区域的完全覆盖, 将这部分盲节点调节为活动状态, 其余冗余节点(即覆盖冗余节点)进入休眠状态.

¹最大独立集:假设存在一个无向图${G_u}({\mathcal {V}_u},{\mathcal {E}_u})$, 如果集合$\mathcal {S} \subseteq {\mathcal {V}_u}$且$\mathcal {S}\ne \emptyset $, 若$\mathcal {S}$中任意顶点在图${G_u}$中逻辑不相邻则称集合$\mathcal {S}$为图${G_u}$的独立集, 如果不存在$|\mathcal {S}'| > |\mathcal {S}|$, 则称集合$\mathcal {S}$为图${G_u}$的最大独立集.

综上所述, Voronoi覆盖原理可概括为:每个节点分布式的收集其感应邻居的信息后构建局部的Voronoi图, 然后由其Voronoi邻居构建2-Voronoi图, 并找出所有的2-Voronoi顶点和所有的2-Voronoi交点, 并根据引理1判断其是否为冗余节点.最后通过计算图${\bar{G}_u}$的最大独立集找出网络的盲节点, 将其调节为活动状态, 其余冗余节点维持休眠状态.此方法可保证在监测区域完全覆盖的基础上, 减少活动节点数量, 因此可以进一步降低能耗.

2.3   最小刚性拓扑

最小刚性拓扑中每个顶点至少连有两条链路, 并且它的链路数与节点数满足线性关系, 它满足无线传感器网络2-容错的特性以及稀疏性.为了构建容错且稀疏的拓扑结构, 本文在活动节点间构建最小刚性拓扑.如果对网络拓扑中部分链路的长度加以限制, 就可以维持整个拓扑构型不变, 那么就称该网络拓扑是一个刚性拓扑^[5].如果一个拓扑不是刚性的, 则称该拓扑为可变形拓扑.图 2(a)和图 2(b)分别为由4个节点构成的刚性拓扑与可变形拓扑.由图 2易知, 组成刚性拓扑的任意一个节点至少连有两条链路.

图 2  刚性拓扑和可变形拓扑((a)刚性拓扑; (b)可变形拓扑; (c)最小刚性拓扑)

Fig. 2  The rigid topology and flexible topology ((a) Rigid topology; (b) Flexible topology; (c) Minimal rigid topology

下载: 全尺寸图片 幻灯片

如果删除一个刚性拓扑中的任意一条链路则会影响该拓扑的刚性, 我们称这样的拓扑为最小刚性拓扑.显然地, 最小刚性拓扑是链路数最少的刚性拓扑^[18].图 2(c)为二维空间中由4个节点构成的最小刚性拓扑.在二维空间中, 给定一个含有$n$个节点的拓扑结构${G}({\mathcal{V}},{\mathcal {E}}(t))$, 节点$i$位置的时变函数为${q_i}(t) =f\left( {{x_i}(t),{y_i}(t)} \right)$ (其中, $i = 1,2,\cdots,n$).本文假设每个节点的位置函数${q_i}(t)$是可微的.如果拓扑中的任意一条链路$l_i^j$满足$||{q_i}(t) - {q_j}(t)|| = c$(其中, $c$为正实数), 则称该链路的移动为刚性移动.在此基础上, 如果该链路同时满足$[{{({{q}_{i}}(t)-{{q}_{j}}(t))}^{\text{T}}}\times ({{\dot{q}}_{i}}(t)-{{\dot{q}}_{j}}(t))]{{|}_{t=0}}=0$, 则称$\dot{q}=({{\dot{q}}_{1}}(t),{{\dot{q}}_{2}}(t),\cdots ,{{\dot{q}}_{n}}(t))$为该拓扑结构的无穷小变形.如果一个拓扑结构的无穷小变形均是由刚性移动引起的, 那么则称该拓扑结构为无穷小刚性拓扑.显然, 无穷小刚性拓扑也是一个刚性拓扑.

二维空间中, 常用$(q_i^1,q_i^2)$来表示节点$i$的位置坐标, 即$q_i^1 ={x_i}$, $q_i^2 = {y_i}$, 将$n$个传感器节点随机排序, 按照序号由小至大的顺序列写其位置坐标如下:

本文引入刚性矩阵检测某个拓扑是否具有刚性, 并辅助生成刚性拓扑结构.链路集${\mathcal {E}}$中的每一条链路, 均可用于转化并对应生成刚性矩阵中的一个行向量.设链路集${\mathcal{E}}$中的所有链路均可随机排序, 当构建一个刚性矩阵${M_{\left|{{\mathcal {E}}} \right| \times 2n}}$ ($|{\mathcal{E}}|$为网络拓扑中的链路数)时, ${\mathcal{E}}$中第$k$条链路$l_i^j$对应于刚性矩阵$M$中第$k$行元素构成的行向量${{\pmb{A}}_k}$ (如式(4)所示).

在该行向量${{\pmb{A}}_k}$中, 第$m$个元素${a_{km}}$满足式(5):

由上述$|\mathcal {E}|$个行向量${{\pmb{A}}_1},{{\pmb{A}}_2},\cdots,{{\pmb{A}}_{|\mathcal {E}|}}$生成的矩阵$M$ ()称为刚性矩阵.

以下引理2和引理3分别描述了刚性矩阵与无穷小刚性拓扑、无穷小刚性拓扑与最小刚性拓扑之间的内在联系.

引理2^[19].在二维空间中, 假设矩阵$M$为$n$个传感器节点所构成拓扑的刚性矩阵, 该拓扑是无穷小刚性的当且仅当${\rm Rank}\left(M \right) = 2n - 3$.

引理3^[5].由$n$个传感器节点构成的链路数为$2n - 3$的无穷小刚性拓扑是最小刚性拓扑.

以下引理4表明可以分布式地生成最小刚性拓扑.

引理4^[16].一个刚性拓扑$G$的一个子拓扑$G'$被其他刚性拓扑$G''$替代后, 得到一个新拓扑$\hat G$, 那么新拓扑$\hat G$是刚性的.

2.4   Delaunay三角剖分图

Delaunay三角剖分图是由Voronoi邻居节点相互连接而成的三角形, 其外接圆圆心是与该三角形相关的Voronoi图的一个顶点.图 3为由传感器节点构成Voronoi图与Delaunay三角剖分图, 其中, 虚线表示由节点构成的Voronoi图, 实线表示由这些节点构成的Delaunay三角剖分图.以Delaunay三角剖分图中任意两个三角形(如图 3中所示的矩形虚线框内的三角形)为例, 以下定理1使用数学归纳法证明由$n (n \ge3)$个节点构成的Delaunay三角剖分图至少含有$2n-3$条链路, 并且它是刚性的.

图 3  节点的Voronoi图以及Delaunay三角剖分图

Fig. 3  The Voronoi graph and Delaunay triangulation of nodes

下载: 全尺寸图片 幻灯片

定理1.在无线传感器网络中, 每个节点与其$n - 1 (n \ge3)$个通信邻居节点构成的Delaunay三角剖分图的链路数不小于$2n - 3$, 且其是刚性的.

证明.采用数学归纳法证明由$n (n \ge3)$个传感器节点构成的Delaunay三角剖分图至少含有$2n - 3$条链路.假设由$n$个传感器节点构成的Delaunay三角剖分图的链路数为$m$.

1)当$n = 3$时, Delaunay三角剖分图的链路数$m = 3$, 满足链路数不小于$2n - 3$;

2)假设当$n = k$时, Delaunay三角剖分图的链路数$m \ge 2k - 3$;

3)当$n = k+1$时, 根据生成Delaunay三角剖分图逐点插入法^[20]的原理可知在原来的Delaunay三角剖分图中任意插入一点$Q$时, 共包含有两种情况:

a)插入点$Q$在三角形的内部:如图 4(a)所示, △$IJN$和△$JNM$为Delaunay三角剖分图中相邻的两个三角形, 如图 4(a)所示, 当插入点$Q$在△$IJN$的内部时, 连接$IQ$, $JQ$和$NQ$, 然后逐个对它们进行外接圆检测.通过交换对角线的方法, 保证所形成的图形(如图 4(a)所示)为Delaunay三角剖分图.因此, 在这种情况下增加一点$Q$后, 形成的Delaunay三角剖分图增加了三条链路, 即当$n = k+1$时, Delaunay三角剖分图的链路数$m' = m + 3 \ge 2k - 3+ 3 = 2k \ge 2(k + 1) - 3$.

图 4  Delaunay三角剖分图逐点插入法((a)插入点$Q$在△$IJN$的内部; (b)插入点$Q$在边$JN$上)

Fig. 4  Point by point insertion method of Delaunay triangulation ((a) Insertion node $Q$ in the interior of a triangle △$IJN$; (b) Insertion node $Q$ is on the $JN$)

下载: 全尺寸图片 幻灯片

b)插入点$Q$在三角形的边上:如图 4(b)所示, 当插入点$Q$在公共边$JN$上时, 连接$IQ$和$MQ$, 并且$JN$被分成了两条链路$JQ$和$NQ$, 然后逐个对它们进行外接圆检测, 通过交换对角线的方法来保证所形成的图形为Delaunay三角剖分图.因此, 在这种情况下增加一点$Q$后形成的Delaunay三角剖分图, 同样增加了三条链路, 即当$n = k+1$时, Delaunay三角剖分图的链路数$m'= m + 3 \ge 2k - 3 + 3 = 2k \ge 2(k + 1) - 3$.因此, 当$n=k+1$时, Delaunay三角剖分图的链路数不小于$2n-3$.

因此, 每个传感器节点与其$n - 1 (n \ge3)$个邻居节点构成的Delaunay三角剖分图的链路数$m$满足$m \ge 2n -3$.

以上我们证明了每个传感器节点与其$n - 1 (n \ge3)$个邻居节点构成的Delaunay三角剖分图的链路数$m$满足$m \ge 2n -3$.实际上, Delaunay三角剖分图是由若干个三角形构成的, 根据引理4可知刚性拓扑$G$的一个子拓扑$G'$被其他刚性拓扑${G''}$替代后, 得到一个新拓扑$\hat G$是刚性的, 而三角形是一个最简单的刚性图, 因此由$n (n \ge 3)$个传感器节点构成的Delaunay剖分图是刚性的.

综上所述, 由$n (n \ge3)$个传感器节点构成的Delaunay剖分图至少含有$2n-3$条链路, 且其是刚性的. $\Box$

基于定理1, 我们给出了以下定理2, 为分布式的生成基于Delaunay三角剖分图的最小刚性拓扑提供了理论依据.

定理2.如果网络中任意节点$i$与其通信邻居节点构成基于Delaunay三角剖分图的最小刚性拓扑记为${G_i}$$(i = 1,\cdots,n)$, ${G_m}$ $({\mathcal {V}_m},{\mathcal{E}_m})$为网络节点生成的全局最小刚性拓扑, 则有以下结论:

1)若${G_i}$与${G_j}$ ($i \ne j$)有公共节点$e$和$f$, 如果存在链路$l_e^f \in {G_j}$且$l_e^f \notin {G_i}$, 那么$l_e^f\notin {\mathcal {E}_m}$.

2)若${G_i}$与${G_j} (i \ne j)$有$n$个公共节点, 且${G_i}$或${G_j}$中存在由该$n$个节点构成的圈², 如果拓扑${G_j}$中存在$m$$(2m\le n)$条链路(链路的顶点均为公共点) ${l'_p} (p = 1,\cdots,m)$满足${l'_p} \in {G_j}$但${l'_p} \notin {G_i}$, 拓扑${G_i}$中同样存在$m$条链路(链路的顶点均为公共点)${l'_q} (q = 1,\cdots,m)$ (${l'_p}$与${l'_q}$中任意链路均不相同)满足${l'_q} \in {G_i}$但${l'_q} \notin {G_j}$, 且$m$条链路${l'_p}$的权值和大于另外$m$条链路${l'_q}$.那么, 将权值和较小的链路${l'_p}$代替权值和较大的链路${l'_q}$后, 再删除满足条件1)的链路, 得到的拓扑是最小刚性拓扑.

²圈:节点间链路首尾相连构成的封闭回路.

证明. 1)假设${G_i}$与${G_j}$ ($i\ne j$)有公共节点$e$和$f$, 如果存在$l_e^f \in {G_j}$且$l_e^f \notin{G_i}$由于最小刚性拓扑是链路数最少的刚性拓扑.因此, 连接最小刚性拓扑中任意两个不存在链路的点, 得到的拓扑同样是刚性的, 故存在$l_e^f + {G_i}$是刚性的.根据引理4一个刚性拓扑的子拓扑由另外一个刚性拓扑代替得到的拓扑仍然是刚性的.因此, $l_e^f + {G_i}$可用${G_i}$替换来保持最终拓扑仍然是刚性的, 因此, 去掉该链路不改变拓扑的刚性特性, 即$l_e^f \notin {\mathcal{E}_m}$, 1)得证.

2)假设${G_i}$与${G_j}$$(i \ne j)$有$n$个公共节点, 且${G_i}$或${G_j}$中存在由该$n$个节点构成的圈, 如果拓扑${G_j}$中存在$m$条链路(链路的顶点均为公共点) ${l'_p} (p =1,\cdots,m)$满足${l'_p} \in {G_j}$但${l'_p} \notin {G_i}$, 拓扑${G_i}$中存在$m$条链路(链路的顶点均为公共点)${l'_q}$ $(q = 1,\cdots,m)$ $({l'_p}$与${l'_q}$中任意链路均不相同)满足${l'_q} \in {G_i}$但${l'_q} \notin {G_j}$, 由于生成Delaunay三角剖分图时, 在同一个圈内生成三角形的连接链路不同, 如果直接删除满足条件1)的链路, 即同时删除${l'_p}$和${l'_q}$, 则圈内的刚性不能保证, 全局拓扑的刚性也不能保证, 因此, 则将权值和较小的链路${l'_p}$代替权值和较大的链路${l'_q}$后, 根据引理4一个刚性拓扑的子拓扑由另外一个刚性拓扑代替生成的新拓扑${\hat G_i}$是刚性的, 由于新拓扑${{\hat{G}}_{i}}$与原拓扑${G_i}$有相同的链路, 因此拓扑${{\hat{G}}_{i}}$是最小刚性拓扑, 然后删除满足条件1)的链路.用${G_{ij}}({\mathcal {V}_{ij}},{\mathcal {E}_{ij}})$表示由拓扑${{\hat{G}}_{i}}({{\mathcal{V}}_{i}},\widehat{{{\mathcal{E}}_{i}}})$和拓扑${G_j}({\mathcal {V}_j},{\mathcal {E}_j})$的公共节点组成的拓扑, 其中, ${\mathcal {V}_{ij}} = {\mathcal {V}_i} \cap {\mathcal {V}_j}$,${\mathcal {E}_{ij}}$表示两个顶点均在${\mathcal {V}_{ij}}$中的链路, 因此有${\mathcal {E}_{ij}} \subset ({\hat {\mathcal {E}_i}} \cap {\mathcal {E}_j})$.令${\mathcal {E}_{ij}} = {a_s} \cup {b_{s1}} \cup {b_{s2}}$, 其中, ${a_s}$表示拓扑${\hat G_i}$与${G_j}$的公共链路, ${b_{s1}}$和${b_{s2}}$分别表示${\mathcal {E}_{ij}}$中仅存在于${\hat G_i}$和${G_j}$中的链路.同时删除${b_{s1}}$和${b_{s2}}$后, 每个子拓扑$G_{ij}' (\mathcal{V}_{ij}',\mathcal{E}_{ij}') \subset{G_{ij}}$, 满足$\left| \mathcal {E}_{ij}' \right| \le 2\left| \mathcal{V}_{ij}' \right| - 3$; 否则, 至少存在一条链路使${\hat G_i}$或${G_j}$的链路数超过$2\left| {{\mathcal {V}_i}} \right| - 3$或$2\left| {{\mathcal {V}_j}} \right| - 3$, 这与条件${\hat G_i}$或${G_j}$均为最小刚性拓扑相矛盾.假设删除${b_{s1}}$和${b_{s2}}$后得到的拓扑${\hat G_i} \cup {G_j}$有超过$2\left| {{\mathcal {V}_i} \cup {\mathcal {V}_j}} \right| - 3$的链路, 则${G_{ij}}$有$\left| {{\mathcal {E}_{ij}}} \right| > 2\left| {{\mathcal {V}_{ij}}} \right| - 3$, 这将导致在删除${b_{s1}}$和${b_{s2}}$之前, ${\hat G_i}$或${G_j}$的链路数超过$2\left| {{\mathcal {V}_i}} \right| - 3$或$2\left| {{\mathcal {V}_j}} \right| - 3$, 这与条件${\hat G_i}$或${G_j}$均为最小刚性拓扑相矛盾, 因此, 得到的拓扑${\hat G_i} \cup {G_j}$满足$\left| {{{\hat {\mathcal {E}}}_i} + {\mathcal {E}_j} - {\mathcal {E}_{ij}}} \right| \le 2\left| {{\mathcal {V}_i} \cup {\mathcal {V}_j}} \right| - 3$.由上述1)可知删除${b_{s1}}$和${b_{s2}}$后不改变拓扑的刚性, 因此, 有$\left| {{{\hat {\mathcal {E}}}_i} + {\mathcal {E}_j} - {\mathcal {E}_{ij}}} \right| \ge 2\left| {{\mathcal {V}_i} \cup {\mathcal {V}_j}} \right| - 3$.因此, 删除${b_{s1}}$和${b_{s2}}$后有$\left| {{{\hat {\mathcal{E}}}_i} + {\mathcal {E}_j} - {\mathcal {E}_{ij}}} \right| = 2\left|{{\mathcal {V}_i} \cup {\mathcal {V}_j}} \right| - 3$, 生成的最终拓扑为最小刚性拓扑. $\Box$

3.   MRTc算法

本节我们详细介绍基于Voronoi覆盖及Delaun-ay三角剖分图的最小刚性拓扑控制算法MRTc.算法执行过程可分为以下4个阶段: 1)信息收集阶段, 网络中各节点仅根据其感知邻居节点和通信邻居节点的信息构建拓扑, 可降低网络中消息传送数量; 2)权值确定阶段, 利用权值函数判定权值大小, 保证拓扑结构的唯一性; 3)拓扑构建阶段, 网络首先分布式确定覆盖冗余节点, 将其调节为休眠状态, 在保证网络监测区域完全覆盖的条件下, 通过减少活动节点数量, 降低网络能耗.然后通过构建基于Delaunay三角剖分图的最小刚性拓扑结构, 提高网络容错性, 并可限制平均节点度数; 4)功率调节阶段, 为了进一步地降低网络能耗, 将每个节点的功率调节为网络所需要的最小功率.

3.1   信息收集

首先, MRTc算法采用与文献[5]相同的机制实现通信邻居节点的收集.通过该机制, 网络中的每个节点均能获得其通信邻居节点的信息, 该信息包含每个通信邻居节点的ID、节点位置坐标以及与其通信邻居节点的欧氏距离.通过这些信息, 可得知每个节点的通信邻居和感应邻居, 也可通过下节的权值函数计算该节点与其通信邻居节点的链路权值.

3.2   权值函数的确定

无线传感器网络中保证两节点$i$, $j$通信所需要的最小传输功率^[11]为$P_i^j = {(d_i^j)^\alpha }+ \delta $.其中, $\alpha$和$\delta$为可调参数, 并且与特定无线通信系统硬件和传输环境有关, 通常有$2 \le \alpha \le4$.显然, 传输功率$P_i^j$随着两节点间距离$d_i^j$的增加而增大.因此, 本文用两点间的距离代表这两点间链路的权值.然而, 在无线传感器网络中, 不同节点间的距离可能相同, 这会导致链路不同, 但却拥有相同的权值, 所生成的最终拓扑结构不唯一.

为了保证生成拓扑的唯一性, 本文采用了以下权值函数.当节点间距离满足如式(6)～式(8)所示的三个条件之一时, 即可得链路$l_i^j$与$l_m^n$的权值函数满足$w_i^j > w_m^n$.

式中, $id(i),~id(j),~id(m),~id(n)$分别表示节点$i$, $j$, $m$, $n$的ID.由于每个节点的ID是唯一的, 因此该权值函数$w$保证了拥有最小权值的链路具有唯一性, 由此可知使用MRTc算法生成的拓扑结构也是唯一的.

3.3   拓扑构建

1)冗余节点选择与休眠调度

监测区域的良好覆盖性是传感器网络拓扑构建的基本要求之一.由于节点经常采用随机部署方式, 导致部分监测区域可被多个节点同时覆盖, 由此产生大量冗余感知信息.因此, 在保证网络全覆盖的前提下, 将覆盖冗余节点调节为休眠状态, 对于降低网络能耗是必要的.本文第2.2节中Voronoi覆盖原理提供了判定覆盖冗余节点的理论依据, 它能够保证在将选出的覆盖冗余节点调节为休眠状态后, 活动节点依然能够保持对监测区域的完全覆盖.其具体过程如MRTc算法伪代码中第4～10行伪代码所示.

2)基于Delaunay三角剖分图的最小刚性拓扑的构建

为了提高网络的鲁棒性, 同时限制网络的平均节点度.本节基于定理2, 将覆盖冗余节点调节为休眠状态后, 在活动节点间构建了基于Delaunay三角剖分图的最小刚性拓扑结构.构建该拓扑的步骤如下:

步骤1.每个节点与其邻居节点构建Delaunay三角剖分图;

步骤2.在Delaunay三角剖分图的基础上不损失刚性的前提下删除较长链路构建局部最小刚性拓扑;

步骤3.删除不属于全局最小刚性拓扑的链路, 可构建全局最小刚性拓扑.

3.4   功率调节

算法的最终阶段, 为了进一步降低网络能耗, 对网络中活动节点的功率进行调节.功率调节时, 每个节点将自身功率设置为能够覆盖其全部逻辑邻居节点(节点$i$的逻辑邻居节点即为经过MRTc算法优化后, 仍然与节点$i$有通信关系的节点)所需要的最小功率, 即节点能与距离其最远的逻辑邻居节点成功通信的功率.这意味着可将每个活动节点的通信半径设置为与其距离最远的逻辑邻居节点的距离.节点通信半径的公式如下所示.

其中, ${r_c}(i)$为节点$i$的通信半径, ${\mathcal {N}_i}^\prime $为节点$i$的逻辑邻居节点的集合.

分布式构建基于Voronoi覆盖与Delaunay三角剖分图的最小刚拓扑结构的MRTc算法的伪代码如下所示.

MRTc算法的伪代码

输入: $N$个传感器节点

输出:节点的传输半径${r_c}(i) (i = 1,2,\cdots,N)$

1. ${{\mathcal{S}}_{{{i}'}}}=\varnothing ,{{\mathcal{N}}_{i}}=\varnothing ,{{\mathcal{C}}_{i}}=\varnothing $

2.节点$i$发现邻居感知节点集合${\mathcal {N}_i}^\prime$和通信邻居节点集合${\mathcal {N}_i}$

3.计算节点$i$与其通信邻居节点的权值, 并将其加入集合${\mathcal {C}_i}$中

4.节点$i$与其感应邻居节点构建局部的Voronoi图, 并找出其Voronoi邻居

5.由节点$i$的Voronoi邻居构建2-Voronoi图, 找出所有$i_2^{VV}$和$i_2^{VIP}$节点

6.判断所有$i_2^{VV}$和$i_2^{VIP}$节点是否被节点$i$覆盖

7. if所有$i_2^{VV}$和$i_2^{VIP}$节点均被节点$i$覆盖

8.   $i \Rightarrow {\bar{ \mathcal {V}_u}}$

9. end

10.计算图${\bar G_u}({\bar {\mathcal {V}_u}},{\bar{ \mathcal{E}_u}})$的最大独立集求出盲节点, 并将其从${\bar{ \mathcal{V}_u}}$中删除

11.将集合${\mathcal {N}_i}$中存在于${\bar{ \mathcal{V}_u}}$的节点删除

12. initializes ${\mathcal {E}_i}^\prime = \emptyset $

13.节点$i$与集合${\mathcal {N}_i}$中节点构建Delaunay三角剖分图, 并将链路存入集合$\mathcal {E}'_i$

14.将这些链路按权值由小到大的顺序排列

15.按照以上顺序依次计算子图的刚性矩阵${M_{i}}^\prime $

16. initializes ${M_i = {M_{i}^\prime }}(1)$

17. for $j = 1:|{E_{i}^\prime }|$

18.  if ${\rm Rank}({M_{{i}}}) \le 2|{E_{i}^\prime }| -3$

19.   

20.   if ${M_{{i}}}$满秩

21.    记录对应于行向量的边

22.   end

23.  end

24. end

25. if ${G_i}$与${G_{{j}}}$ $(i \ne j)$含有$n$个公共节点, 且${G_i}$或${G_{{j}}}$存在该$n$个顶点构成的圈

26.  if ${G_{{j}}}$中存在$m$条链路(链路的顶点均为公共点)${l'_p}$ $(p = 1,\cdots,m)$满足${l'_p} \in {G_j}$ $\& $ ${l'_p} \notin {G_i}$, ${G_{{i}}}$中存在$m$条链路(链路的顶点均为公共点)${{{l}'}_{q}}(q=1,\cdots ,m)$ (${l'_p}$与${l'_q}$中任意链路均不相同)满足${{{l}'}_{q}}\in {{G}_{i}}\ \text{ }\!\!\And\!\!\text{ }\ {{{l}'}_{q}}\notin {{G}_{j}}$

27.   用权值和较小的链路${l'_p}$代替权值和较大的链路${l'_q}$, 形成新的最小刚性拓扑${\hat G_i}$

28.  end

29. end

30.最小刚性拓扑${G_1}$与${G_2}$有相同节点$e$和$f$, 且有$l_{e}^{f}\in {{G}_{2}}\ \And \ l_{e}^{f}\notin {{G}_{1}}$

31.  删除$l_e^f$

32. end

33. ${r_c}(i) = \max \{ d_i^{{\mathcal {N}_i}^\prime }\}$

首先, 节点通过信息的收集得到节点的感应邻居集合和通信邻居节点集合(行1～2).接着第3行根据第3.2节权值函数确定节点与通信邻居节点的权值.行4～32为拓扑的构建阶段, 该阶段节点首先根据覆盖原理(见第2.2节Voronoi覆盖原理)确定网络中的覆盖冗余节点, 并将其调节为休眠状态(行4～10).然后, 在活动节点间构建基于Delaunay三角剖分图的最小刚性拓扑结构, 改善网络容错性, 有效约束网络的平均节点度(行11～32).算法的最终阶段(行33)每个节点通过调节其传输功率来降低网络能耗, 将功率调节为能够覆盖所有逻辑邻居节点的最小功率, (即${r_c}(i) =\max\{ d_i^{{\mathcal{N}_i}^\prime }\}$).

4.   MRTc算法性能分析

MRTc算法使得网络中的覆盖冗余节点调节为休眠状态, 并在活动节点间构建最小刚性拓扑结构, 有效降低了网络能耗, 该算法还具有以下4个方面的性质.

性质1.由$n$个传感器节点形成的初始拓扑³${G_C}({\mathcal{V}_C},{\mathcal {E}_C})$, 在经过MRTc算法优化后得到的拓扑结构${G_D}({\mathcal {V}_D},{\mathcal{E}_D})$是2-容错的.

³初始拓扑:没有经过任何算法优化的起始拓扑结构

证明.通过第2.3节, 我们可知构成最小刚性拓扑的任意一个节点至少连有两条链路, 由于初始拓扑${G_C}({\mathcal {V}_C},{\mathcal {E}_C})$经过MRTc算法优化后, 得到的拓扑是最小刚性拓扑.因此, 拓扑结构${G_D}({\mathcal {V}_D},{\mathcal {E}_D})$中的任意一个节点至少连接有两条链路, 即拓扑中的任意节点至少含有两条链路, 根据第2.1节$k$-容错的定义可知, 最终生成的拓扑是~2-容错的. $\Box$

性质2.由$n$个传感器节点形成的初始拓扑${G_C}({\mathcal{V}_C},{\mathcal {E}_C})$, 在经过MRTc算法优化后得到的拓扑结构${G_D}({\mathcal {V}_D},{\mathcal{E}_D})$满足区域完全覆盖.

证明.根据第2.2节覆盖冗余节点的定义可知, 如果一个节点的覆盖区域被其他节点完全覆盖, 则该节点为覆盖冗余节点.经算法MRTc优化后, 这些覆盖冗余节点被调节为休眠状态后, 它们的覆盖区域仍然可以被其他节点所覆盖.因此, 由$n$个传感器形成的初始拓扑${G_C}({\mathcal {V}_C},{\mathcal{E}_C})$, 在经过MRTc算法优化后得到的拓扑结构${G_D}({\mathcal{V}_D},{\mathcal {E}_D})$满足区域完全覆盖. $\Box$

性质3.由$n$个传感器节点形成的初始拓扑${G_C}({\mathcal{V}_C},{\mathcal {E}_C})$, 在经过MRTc算法优化后得到的拓扑结构${G_D}({\mathcal {V}_D},{\mathcal{E}_D})$是稀疏的.

证明.根据第2.1节网络稀疏性的定义, 可知若拓扑满足网络稀疏性要求, 需要网络中的链路数量与节点数量之间呈线性关系.又根据第2.3节引理3知, 由任意$n$个节点构成的最小刚性图有$2n-3$条链路.由于${G_C}({\mathcal{V}_C},{\mathcal {E}_C})$在经过MRTc算法优化后, 得到的拓扑结构${G_D}({\mathcal {V}_D},{\mathcal {E}_D})$是一个最小刚性拓扑, 即拓扑${G_D}({\mathcal {V}_D},{\mathcal{E}_D})$中的链路数量和节点数量呈线性关系.所以, 经过MRTc算法优化后得到的拓扑结构${G_D}({\mathcal {V}_D},{\mathcal{E}_D})$是稀疏的. $\Box$

性质4.经过MRTc算法优化后得到的拓扑结构${G_D}({\mathcal{V}_D},{\mathcal {E}_D})$, 其平均节点度不大于4.

证明.由引理3和定理2可知, 经MRTc算法优化后的拓扑结构${G_D}({\mathcal {V}_D},{\mathcal {E}_D})$有$2n-3$条链路.根据握手定理^[21]可知, 对于任意拓扑$G(\mathcal {V},\mathcal {E})$, 网络内节点度之和为$2|\mathcal {E}|$, 其中$|\mathcal {E}|$为该拓扑中链路的数目.因此, 拓扑结构${G_D}({\mathcal{V}_D},{\mathcal {\mathcal {E}}_D})$中所有节点的节点度之和为$\sum\nolimits_{i \in {\mathcal {V}}}{{D_i}} = 2|\mathcal {E}| = 2 \times (2n - 3)$, 故它的平均节点度为${D_{ev}} = {\sum_{i \in V} {D_i} }/{n}= {(4n - 6)}/{n} \le 4$, 即拓扑结构${G_D}({\mathcal{V}_D},{\mathcal {E}_D})$的平均网络节点度不超过4. $\Box$

5.   MRTc算法性能评价

为了分析和评价MRTc算法的性能, 本文在Matlab R2009a环境中, 使用M语言设计了以下4组数值仿真实验.实验1分别在均匀和随机两种网络中验证睡眠调度方案的性能; 实验2以52个节点为例详细介绍了同构网络拓扑的构建过程; 实验3通过比较4种典型算法, 验证了MRTc算法的性能; 实验4对最小刚性拓扑结构下睡眠调度前后网络的总能耗以及活动节点的比例进行了详细比较.本文所有实验均假设监测区域为$100 \times 100$的方形区域, 传感器节点的最大感知半径设为20.监测区域范围与节点感知半径的大小见文献[22].节点的最大通信半径为40.在均匀网络中, 每个传感器节点均位于网格的顶点, 网格大小设置为${r_a}\times {r_b} = {100}/{6} \times {100}/({{\sqrt n - 1}})$, 式中$n$为监测区域内布置的节点数目, ${r_a}$为每个网格的长度值, ${r_b}$为每个网格的宽度值.

5.1   实验1冗余节点选择与休眠调度

降低网络能耗是拓扑控制的主要设计目标, 为了实现该目标, 本文采用了睡眠调度方案在保证网络监测区域全覆盖的前提下, 将覆盖冗余节点调节为休眠状态.为了验证睡眠调度方案的性能, 本实验分别在均匀网络和随机网络两种网络中进行仿真实验.图 5和图 6分别为在均匀网络和随机网络中部署70个节点时, 睡眠调度前后的监测区域覆盖情况.节点感知半径均为20.由这4个子图可以看出在经过睡眠调度后, 监测区域仍然被活动节点完全覆盖满足性质2.

图 5  均匀网络睡眠调度((a)睡眠调度前; (b)睡眠调度后)

Fig. 5  The sleep scheduling in uniform networks ((a) Before the sleep scheduling; (b) After the sleep scheduling

下载: 全尺寸图片 幻灯片

图 6  随机网络睡眠调度((a)睡眠调度前; (b)睡眠调度后)

Fig. 6  The sleep scheduling in random networks ((a) Before the sleep scheduling; (b) After the sleep scheduling

下载: 全尺寸图片 幻灯片

当节点数量分别为49、56、63、70、77时, 算法的覆盖性能如图 7所示, 子图 7(a)、7(b)分别为实验中冗余节点的数目和冗余节点比例.由图 7(a)、7(b)可知, 无论在均匀网络中还是冗余网络中, 冗余节点的数目随着网络节点密度的增大而增加, 并且冗余节点的占比也随之增大.该结果表明对于节点密度不同的网络, 该算法均可以起到较好的睡眠调度效果.

图 7  两种网络中冗余节点数目和所占节点比例的比较((a)冗余节点个数的比较; (b)冗余节点比例的比较)

Fig. 7  The comparison of the number of redundant nodes and the proportion of redundant nodes in the two networks ((a) The comparison of the number of redundant nodes; (b) The comparison of the proportion of the redundant nodes

下载: 全尺寸图片 幻灯片

5.2   实验2网络拓扑的构建过程

在实验1的基础上, 我们以52个节点为例详细介绍网络拓扑的构建过程.首先, 将52个感知半径为20的节点随机部署在$100 \times 100$的监测区域内, 节点的分布情况与监测区域的覆盖情况如图 8(a)所示.根据Voronoi覆盖原理选择覆盖冗余节点, 并将覆盖冗余节点调节为休眠状态.活动节点对监测区域的覆盖情况如图 8(b)所示.由图 8(b)可以看出, 在将部分节点调节为休眠节点后, 监测区域内的任意一点仍至少被一个活动节点覆盖.可见, 经过睡眠调度后, 网络满足完全覆盖.在此基础上, 每个活动节点与其邻居节点生成局部的Delaunay三角剖分图, 构建局部最小刚性拓扑结构如图~9(a)所示, 图中实线表示两点间的实际链路, 虚线表示可以被删除的链路.每个节点在维持刚性的前提下删除权重较大的链路, 与其邻居节点构建权重和最小的局部最小刚性拓扑如图 9(b)所示.最后根据定理2, 删除不属于全局最小刚性拓扑的链路, 构建起全局最小刚性拓扑结构, 如图 9(c)所示.

图 8  睡眠调度前后区域覆盖情况((a)睡眠调度前区域覆盖情况; (b)睡眠调度后区域覆盖情况)

Fig. 8  The area coverage by using the sleep scheduling ((a) The area coverage before sleep scheduling; (b) The area coverage after sleep scheduling

下载: 全尺寸图片 幻灯片

由该实验容易看出, 经MRTc算法优化后的拓扑, 即图 9(c)中的任意一个节点至少连有两条链路.这意味着该拓扑结构是2-容错的, 满足性质1.图 9(c)与图 9(a)和图 9(b)相比, 图 9(c)中的链路数明显减少, 表明经MRTc算法优化后的拓扑结构, 其网络平均节点度明显小于图 9(a)和图 9(b)拓扑的平均节点度, 即由MRTc算法优化后的拓扑结构能够帮助降低网络MAC层干扰.

图 9  MRTc拓扑结构的构建过程((a)构建局部Delaunay三角剖分图; (b)构建局部最小刚性拓扑; (c)构建全局最小刚性拓扑)

Fig. 9  The construction process of MRTc topology ((a) The construction of local Delaunay triangulation; (b) The construction of local minimum rigid topology; (c) The construction of global minimum rigid topology

下载: 全尺寸图片 幻灯片

5.3   实验3重要性能指标的横向比较

为了验证MRTc算法的性能, 本实验选取4种经典的拓扑控制算法GG (Gabrielgraph)、RNG (Relative neighborhoodgraph)、LMST、Udel与本文提出的MRTc算法进行比较.首先, 实验对5种算法生成的拓扑结构进行对比.在$100 \times 100$的区域内随机生成30个节点, 在相同的仿真环境下, 使用上述5种算法来构建拓扑结构, 并对5种拓扑结构进行比较.实验中节点的感知半径设置为20.当传感器节点的感知半径和通信半径满足${r_c} \ge 2 \times {r_s}$时, 如果网络在给定凸区域满足1-覆盖, 则能够保证网络的连通性^[23].因此, 本文假设网络节点的感知半径和通信半径满足${r_c} = 2 \times {r_s}$.然后, 在相同的仿真环境中, 通过改变传感器节点的个数, 使其在30～100的范围内变动, 比较5种不同算法的平均节点度、平均链路长度以及网络的最大与最小节点度.通过全面的性能比较, 验证本文提出的MRTc算法的性能.

1)网络拓扑结构对比

在相同的仿真环境下, 比较5种不同的拓扑控制算法GG、RNG、LMST、Udel与MRTc生成的拓扑结构.图 10显示了由图 9(c)中的30个活动节点在$100 \times 100$的区域内分别使用上述5种方法生成的拓扑结构.由图 10(d)可以看出算法Udel生成的拓扑结构中有67条链路, 是这5种拓扑结构中链路数最多的.该拓扑结构的平均节点度也是最大的.此外, Udel算法是一个集中式方法, 它需要预先获知网络中所有节点的信息.相比之下, RNG算法(见图 10(b))和LMST算法(图 10(c))是分布式算法, 它们的构建过程只需依赖邻居节点的信息.由这两种算法所生成的拓扑中, 链路数分别为34和38, 平均节点度过低.过低的节点度会导致节点间的通信链路过长, 网络能耗随之增大.而本文算法(图 10(e))和GG算法(图 10(a))的链路数分别为57和52, 两者相差不大.然而, 由这两个子图容易看出, GG算法拥有的长链路数量较多, 这意味着该算法的能耗较大.

图 10  不同算法生成的拓扑结构((a) GG; (b) RNG; (c) LMST; (d) Udel; (e) MRTc)

Fig. 10  The topological structures of different algorithms ((a) GG; (b) RNG; (c) LMST; (d) Udel; (e) MRTc

下载: 全尺寸图片 幻灯片

2)其他重要性能指标比较

在$100 \times 100$的监测区域内, 当节点数量由30逐渐递增时, 上述5种算法的平均节点度、平均传输半径、最大节点度以及最小节点度4种性能指标如图 11所示.

网络的平均节点度定义为网络中所有节点的节点度之和与节点数量的比值.在无线传感器网络中, 高的平均节点度需要在MAC层特别设计接入访问机制, 严重时还可引发访问干扰和数据碰撞, 造成非必要的网络能耗.反过来, 网络的平均节点度过低则会导致节点间的链路过长, 通信能耗值也相应地增加.文献[16]提出网络的最优平均节点度为6.根据实验2网络拓扑构建过程可知, 经过MRTc算法优化后减少了网络拓扑的链路数.由引理4可知, 经MRTc算法优化后每个节点的节点度也会相应地降低.图 11(a)为GG、RNG、LMST、Udel以及MRTc这5种算法在网络节点数目在30～100间变化时, 网络的平均节点的比较.由性质4知算法MRTc的平均节点度${D_{ev}} ={\sum_{i \in V} {D_i} }/{n} = ({4n - 6})/{n} \le 4$, 因此, 随着节点数目$n$的增加, MRTc算法的平均节点度逐渐增加, 且其值接近于4.由图 11(a)知该算法的平均节点度变化缓慢, 说明该算法较稳定.相比之下, 算法RNG和算法LMST的平均节点度在3以下, 这意味着由这两种算法生成的拓扑结构过于稀疏.而Udel算法的平均节点度接近于最优值6, 这与文献[12]相符合.

传输半径定义为节点与其最远邻居之间的距离.平均传输半径为网络中各个节点的传输半径之和与节点数量的比值.网络中节点的平均传输半径越大, 网络通信能耗也越大.上述5种算法平均传输半径的比较结果如图 11(b)所示.由第2.3节2)基于Delaunay三角剖分图的最小刚性拓扑的构建可知MRTc算法是由删除Delaunay三角剖分图的部分较长链路得到的.因此, MRTc算法生成的拓扑结构具有较小的平均传输半径.由图 11(b)可知, Udel算法和GG算法的平均传输半径均高于MRTc算法.而LMST算法与RNG算法具有更小的平均传输半径.

图 11  不同算法的性能比较((a)平均节点度的比较; (b)平均传输半径的比较; (c)最大节点度的比较; (d)最小节点度的比较)

Fig. 11  The performance comparison of different algorithms ((a) The comparison of average node degree; (b) The comparison of average transmission radius; (c) The comparison of maximum node degree; (d) The comparison of minimum node degree

下载: 全尺寸图片 幻灯片

图 11(c)和(d)分别为5种算法最大节点度与最小节点度的比较.网络的最大节点度定义为网络中逻辑链路^[5]最多的节点的度数.与之类似, 网络的最小节点度定义为网络中逻辑链路最少的节点的度数.由第2.3节知最小刚性拓扑中节点至少包含两条链路, 因此, 由MRTc算法生成的拓扑结构的最小节点度不低于2.这意味着由该算法生成的拓扑结构是2-容错的, 具有较高的鲁棒性.由图 11(c)和(d)知算法LMST和RNG的最大节点度均在最优值6以下, 进一步说明这两种算法的节点度过低.且算法LMST、GG和RNG的最小节点度均可以取值为1, 表明这三种算法均是1-容错的.当算法中的某条链路断裂时, 其他节点不能继续维持网络的连通性, 因此网络的容错性较差.

综上所述, MRTc算法在保证网络覆盖性与连通性的同时, 能够限制网络平均节点度从而降低了网络MAC层干扰, 并有效地增强了网络的鲁棒性能, 降低了网络能耗.另外, 该算法具有较强的稳定性.然而, 此算法也存在不足之处, 即当网络节点密度相同时, 与LMST算法和RNG算法相比, MRTc算法的平均传输半径较大, 这表示由MRTc算法优化得到的拓扑结构中存在部分较长链路.

针对该问题, 我们提出下一步的研究方向即为寻找合适的方法, 在保证网络2-容错性能的前提下, 删除拓扑中较长链路.

5.4   实验4睡眠调度前后能耗比较

节约能耗是网络拓扑控制的首要目标, 网络中节点存在休眠和活动两种状态.本实验使用最小刚性拓扑, 并以总能耗和存活节点比例为指标, 全面深入地比较了网络睡眠调度前、后的能量消耗情况.

计算睡眠调度前、后总能耗与活动节点比例实验的设置场景如下:假设70个传感器节点随机部署于$100\times 100$的方形监测区域内.每个节点拥有相同的初始能量${E_0} =1$kJ, 且能量无法得到补充.假设数据包的长度为50Bytes, 发射电路和接收电路的能量消耗${E_{elec}} = 50n$J/bit, 自由空间传输模型系数$\varepsilon _{fs} = 10p$J/bit/m$^2$.实验中采用洪泛式路由, 当数据包个数变化时, 睡眠调度前、后最小刚性拓扑的总能耗以及活动节点比例如图 12(a)和(b)所示.

图 12  睡眠调度前后最小刚性拓扑性能((a)睡眠调度前后最小刚性拓扑总能耗; (b)睡眠调度前后最小刚性拓扑存活节点)

Fig. 12  The performances of minimum rigid topology before and after sleep scheduling ((a) Total energy consumption of the minimum rigid topology before and after sleep scheduling; (b) The proportion of survival nodes before and after sleep scheduling in minimum rigid topology

下载: 全尺寸图片 幻灯片

由图 12(a)和(b)可知, 最小刚性拓扑在经由睡眠调度后, 均能降低网络的总能耗, 提高网络中存活节点的比例.因此, 使用基于Voronoi覆盖的睡眠调度算法后可有效降低网络能耗.

6.   结论

本文提出了一个基于Voronoi覆盖与Delaunay三角剖分图的最小刚性拓扑控制算法, 该算法采用睡眠调度与功率控制相结合的方案来降低网络能耗.算法中, 无线传感器网络通过睡眠调度在保证监测区域全覆盖的同时, 可将覆盖冗余节点调整为休眠状态.进一步地, 算法在剩余活动节点之间, 构建基于Delaunay三角剖分图的最小刚性拓扑结构.这一方法有效限制了平均节点度, 即网络平均节点度不大于4, 且所生成的链路数量满足稀疏性要求.经过MRTc算法优化后的网络拓扑是2-容错的, 提高了网络的容错性.

未来工作可进一步研究Delaunay三角剖分图的性能对算法的影响, 进而研究该拓扑在异构网络中的构建问题; 另外, 寻找合适的方法, 在保证网络2-容错性能的前提下, 删除拓扑中较长链路.