1.   引言

无线传感器网络(Wireless Sensor Networks, WSNs)中的能耗问题直接影响到网络寿命。随机的高密度部署方式致使网络中存在大量的冗余节点与叠加覆盖，在造成资源浪费的同时，势必会降低网络的生命周期。目前，面向同构型WSNs的节点调度研究均已经比较成熟^[1,2]，但在实际应用中，由于自然因素或工作负荷的差异，异构型的WSNs却是更加普遍存在。设计面向多级随机异构WSNs的节点去冗余调度算法，对于提高节点利用效率，延长网络寿命具有重要的意义。

目前，WSNs的去冗余策略主要从减少冗余覆盖面积和休眠冗余节点两个方面入手。在不影响网络覆盖性能的条件下，文献[3]根据邻居节点感知圆的交点被其他节点覆盖的程度，适当调节感知半径以降低网络的覆盖冗余度。文献[4]通过虚拟力作用实现了节点的优化部署，利用能耗阈值对感知半径进行自适应调整，以降低网络的整体能耗。

直接将不影响网络覆盖效果的冗余节点置于休眠状态，也是一种高效的降低覆盖冗余的方法。文献[5]给出了节点与邻居重叠覆盖区域的简化表达形式，通过考量重叠面积，实现对冗余节点的认定。为了避免对重叠面积的直接计算，将2维网格简化为4个象限或特定子区域内的待检测点，通过分析节点及其邻居对特定点的覆盖叠加程度^[6,7]，确定节点是否可以进入休眠状态。利用节点与其邻居节点间的能量差异、位置关系以及邻居节点数目信息也是判定节点冗余的有效依据。文献[8]引入非合作博弈理论，利用节点覆盖率和剩余能量等关键因素，构建节点的收益函数，优化传感器网络拓扑。综合与邻居节点的距离、数目及对自身感知区域的重叠覆盖程度^[9]，也可以作为节点是否冗余的判别依据。针对2级异构网络，文献[10]将邻居节点划分成3类，根据目标覆盖率确定邻居节点的数目要求，从邻居节点数量上衡量节点是否需要被休眠。

几何方法也被用来辅助节点冗余的判别。文献[11]利用节点的邻居节点集构建局部的2次Voronoi剖分图，辅以邻居节点集的冗余属性，判定节点是否属于绝对冗余节点。文献[12]选取网络中具有最大面积的Delaunay 三角形重心作为决策方向，联合邻居节点的覆盖信息，利用分布式贪婪算法解决冗余覆盖问题。

但在面向任务的WSNs中，已有的同构或2级异构网络的成功结论，不能简单地移植到多级异构网络中。因此，本文提出了一种随机异构无线传感器网络的节点调度算法(Node Scheduling algorithm for Stochastic Heterogeneous wireless sensor networks, NSSH)。NSSH基于Delaunary三角剖分、邻居节点对自身的覆盖重叠程度以及节点有效约束圆弧，对节点的感知半径进行适当调整，识别网络中的具有冗余属性的灰色节点和黑色节点，对冗余节点进行休眠操作，减少网络中不必要的覆盖开销，扩展网络的生命周期。

2.   数学模型

2.1   网络模型

考虑到传感器网络中节点的异质性，且休眠网络中的冗余节点，保留满足网络覆盖要求的有效节点子集本身就是一个${\rm{NP}}$难的问题，故在本文中，不失一般性地对网络场景和研究模型作如下假设：

(1) 在给定的被监测2维矩形区域$I = B \times L$内，随机部署$N$个多级随机异构的传感器节点，其感知范围为一系列以节点$s = \{ {s_i}{\rm{(}}{x_i},{y_i}{\rm{)|}}i = 1,2, ·\!·\!· ,N\}$所在位置为圆心，感知半径$r = \{ {r_i}|i = 1,2, ·\!·\!· ,N\}$的圆盘${S_i} = \left\{ (x,y)\Bigr|\sqrt {{{(x - {x_i})}^2} + {{(y - {y_i})}^2}} < {r_i}\right\}$，圆盘的面积${A_{{S_i}}}{\rm{ = {\text{π}} }}{r_i}^2$，其中，认为节点的多级异构性体现为感知半径之间的差异^[13]，即存在${r_i} \in [{r_{{\rm{min}}}},{r_{{\rm{max}}}}]$。

(2) 网络$s$为高密度静态网络，若${s_i}$被认定为冗余的节点，其状态为休眠态，即${\rm{s}}{{\rm{t}}_i} = 0$；否则，节点为活动态${\rm{s}}{{\rm{t}}_i} = {\rm{1}}$。

(3)节点${s_i}$采用2元感知模型，即若$\exists t \in I$, ${s_i}$对目标点$t$的感知质量可标记为$P({s_i},t) =\! \left\{ \begin{aligned} {\rm{}}& {{\rm{1}},{\rm{ }}t \in {S_i}} \\ {\rm{}}& {0,{\rm{ }}t \in I - {S_i}} \end{aligned} \right.$。

2.2   相关定义

定义1　覆盖冗余度：是衡量区域$I$被$s$覆盖的冗余程度，是评估网络质量的重要指标。覆盖冗余度^[14]$F$可用集合$s$内所有节点的感知面积和与其对$I$的感知面积的比值表征为$F{\rm{ = }}{{\displaystyle\sum\nolimits_{i = 1}^N {{S_i}} } / {\bigcup\limits_i^N {{S_i} \bigcup I} }}$。

定义2　空外接圆半径：空外接圆^[15]为以网络$s$形成的Delaunary剖分中，任意一个以节点${s_i}$为顶点形成的三角形$T_p^i$的几何外接圆，其中，$r_c^i = \{ r_{cp}^i|p = 1,2, ·\!·\!· ,P\}$表示与${s_i}$相关的三角形子集${T^i} = \{ {T_p}^i|p = 1,2, ·\!·\!· ,P\}$的空外接圆半径。

定义3　约束圆弧：若网络中节点${s_i}$的感知圆盘${S_i}$与其邻居节点${s_j}$的感知圆盘${S_j}$，存在感知重叠区域即${S_i} \cap {S_j}\ne \varnothing$，则${s_i}$的约束圆弧为其感知圆周上被${s_j}$的感知圆盘重叠感知的圆弧。

如图1所示，节点${s_i}$与其$Q$个邻居节点${\rm{N}}{{\rm{e}}_i} =$$\{ {s_{jq}}|d({s_i},{s_{jq}}) \le {r_i} + {r_{jq}},q = 1,2·\!··,Q\}$存在感知重叠区域，且对应于每个邻居节点${s_{jq}}$形成$Q$个${{{\stackrel \frown{\rm{arc}}_{i\_jq}}}}$圆弧，则${s_i}$的有效约束圆弧为${ {\stackrel \frown{{\rm{arc}}_i}}} = {\stackrel \frown {\rm{AB}}} \cup {\stackrel \frown {\rm{CD}}}$。

图 1  节点${s_i}$的有效约束圆弧${\stackrel \frown {{\rm{ar}}{{\rm{c}}_i}}}$

下载: 全尺寸图片 幻灯片

3.   NSSH调度策略

考虑到多级异构WSNs的覆盖效果与复杂性，NSSH分别从感知半径调整和节点休眠两个方面降低无价值的覆盖。在适当调整网络中节点的感知半径后，需要依赖节点间重叠面积比和有效约束圆弧判定网络中可能存在的冗余节点，并对其进行休眠操作，深度降低网络冗余度。

3.1   半径调整妥协策略

NSSH利用节点集合$s$构建的Delaunary三角剖分$T = (s,E)$，可将对$I$覆盖去冗余问题，转化为针对局部三角形子集${T^i}$中核心节点${s_i}$的去冗余问题。对当前节点${s_i}$而言，半径的调整过程必须考虑与之构建局部${T^i}$的邻居节点，若仅以距离$d({s_i},{s_{j{\rm{q}}}})/2$为调整依据，会出现三角形${T_p}^i$的中心位置覆盖缺失。因此，算法以${T^i}$为基础，分布式地调整公共顶点(节点)${s_i}$的感知半径${r_i}$，相对安全为${s_i}$设置${r_i} = \max (r_{\rm c}^i)$。对每一个节点${s_i}$，具体的半径调整算法步骤如表1所示。

表 1  半径调整算法步骤

半径调整算法(${T^i},{r_i}$)
(1)　$r_{\rm c}^i = \varnothing$
(2)　for $p = 1:P$
(3)　　　calculate the radius $r_{{\rm{cp}}}^i$ of ${T_p}^i$//计算空外接圆半径
(4)　　　　$r_{\rm c}^i = r_{\rm c}^i \cup r_{ {\rm{cp} } }^i$
(5)　end for
(6　　　${r_i} = \min ({r_i},\max \left( {r_{\rm c}^i} \right))$//若$\max \left( {r_{\rm c}^i} \right) > {r_i}$，则保留原${r_i}$
(7)　return (${r_i}$)

下载: 导出CSV 

| 显示表格

图2中，节点${s_i}$和其邻居子集${\rm{N}}{{\rm{e}}_i} = \{ {s_{{{j1}}}},{s_{{{j2}}}}, ·\!·\!·,$${s_{{{j6}}}}\}$组成网络子图，其中${T^i} = \{ {T_1}^i,{T_2}^i, ·\!·\!· ,{T_P}^i\}$是以节点${s_i}$为公共顶点的$P = 6$个三角形，可求取${T^i}$空外接圆半径的最大值$\max \left( {r_{\rm c}^i} \right)$。由于节点感知半径${r_i} > \max (r_{\rm c}^i) = r_{{\rm{c6}}}^i$，故将${s_i}$的感知半径调整为${r_i} = \min ({r_i},r_{{\rm{c6}}}^i) = r_{{\rm{c6}}}^i$。

图 2  节点${s_i}$感知半径${r_i}$调整图

下载: 全尺寸图片 幻灯片

3.2   节点休眠策略

3.2.1   节点灰度分级

节点的半径调整，可以保证以其为中心，以邻居节点为辐射范围内，尽可能多地减少无效覆盖。由于半径调整算法需要同时适应多个相关三角形${T_p}^i$进行公共顶点的感知半径调整，势必会为了顾全所有涉及的三角形外接圆半径$r_{{\rm{cp}}}^i$，而适当放宽当前节点${s_i}$的感知半径${r_i}$，因此节点间依然会存在重叠覆盖。进一步，引入节点间重叠面积比和有效约束圆弧作为衡量依据，分别识别出网络中具有冗余属性的节点，进行休眠处理。

3.2.2   灰色节点

在同构网络中，节点间的距离直接反映感知重叠面积，给定距离阈值${d_{{\rm{th}}}}$可以有效判定节点间是否存在冗余。但在多级异构的传感器网络中，由于节点感知半径的差异，无法简单依靠距离阈值判定冗余，此时评估节点间的重叠面积${\rm{ol}}({S_i},{S_j})$在有效覆盖面积中的占比，可以弥补大跨度感知半径节点间的冗余识别漏洞。

定义4　重叠面积比$\theta$：节点${s_i}$与邻居节点${s_j}$感知圆盘的重叠面积${\rm{ol}}({S_i},{S_j})$与自身感知圆盘面积${A_{{S_i}}}$的比值，为${s_i}$关于${s_j}$的重叠面积比，即${\theta _{i,j}} =$${\rm{ol}}({S_i},{S_j})/{A_{{S_i}}}$。

定义5　灰色节点(Grey node)：对于传感器节点${s_i}$与${s_j}$，给定感应重叠面积比阈值${\theta _{{\rm{th}}}}$(通常${\theta _{{\rm{th}}}} < 1$)，若存在${\theta _{i,j}} > {\theta _{{\rm{th}}}}$，则判定节点${s_i}$为灰色节点。当$d\left( {{s_i},{s_j}} \right) < {r_j} - {r_i}$时，存在${\theta _{i,j}} = 1 > {\theta _{{\rm{th}}}}$，节点${s_i}$被称之为完全冗余的包裹型灰色节点。

对于任意给定具有重叠覆盖关系的两个异质节点${s_i}$和${s_j}$(如图3)，以$\alpha$和$\beta$表示两个节点对应重叠区域的圆心角。则节点${s_i}$和${s_j}$的重叠面积${\rm{ol}}({S_i},{S_j})$可通过式(1)计算得出。

图 3  节点感知重叠面积求解

下载: 全尺寸图片 幻灯片

3.2.3   黑色节点

在网络中，除节点间的两两重叠覆盖外，节点感知圆盘被其邻居节点集联合的重叠覆盖，也是在降低网络冗余过程中不可忽视的一种情况。图4(a)中，节点${s_i}$被邻居节点集${\rm{N}}{{\rm{e}}_i} = \{ {s_{jq}}|q = 1,2,{\rm{3}}\}$联合覆盖，且${\theta _{i,jq}} < {\theta _{{\rm{th}}}}$，无法认定${s_i}$为灰色节点，但由于存在$\displaystyle\sum\nolimits_{q = 1}^Q {{\rm{ol}}({S_i},{S_j})} \gg {A_{{S_i}}}$，显然${s_i}$为冗余节点。此时，依靠${s_i}$的有效覆盖圆弧${\stackrel \frown {{\rm{ar}}{{\rm{c}}_i}}}$的度数$\left| {{\rm{ar}}{{\rm{c}}_i}} \right|$，可以补充识别${s_i}$被邻居节点集${\rm{N}}{{\rm{e}}_i}$联合重叠覆盖的情况。

图 4  黑色节点的标识与计算

下载: 全尺寸图片 幻灯片

定义6　黑色节点(Black node)：对于传感器节点${s_i}$与其邻居节点集${\rm{N}}{{\rm{e}}_i}$，给定有效约束圆弧度数的阈值${\left| {{\rm{arc}}} \right|_{{\rm{th}}}}$，若存在$\left| {{\rm{ar}}{{\rm{c}}_i}} \right| \ge {\left| {{\rm{arc}}} \right|_{{\rm{th}}}}$，且感知圆盘${S_i}$圆心${\rm{(}}{x_i},{y_i}{\rm{)}}$处满足$k$覆盖，则判定节点${s_i}$为黑色节点。

算法以当前节点${s_i}$为极坐标极点，建立局部极坐标系，选取逆时针方向为角度的正向参考，完成对${s_i}$的有效约束圆弧度数$\left| {{\rm{ar}}{{\rm{c}}_i}} \right|$的计算。鉴于${s_i}$与邻居节点之间的约束角度的计算具有相似性，因此以图4(b)中，给定一邻居节点${s_{jq}}(d\left( {{s_i},{s_{jq}}} \right),\varphi )$为例，介绍$\left| {{\rm{ar}}{{\rm{c}}_i}} \right|$的计算方法，其中$\varphi$为节点${s_{jq}}$在极坐标系中的极角。

节点${s_{jq}}$对节点${s_i}$的约束圆弧${ {{\stackrel \frown{\rm{arc}}_{i\_jq}}}}$的度数$\left| {{\rm{ar}}{{\rm{c}}_{i\_jq}}} \right|$，可以由式(2)，式(3)和式(4)计算得出。

由此，可以得出图4(a)中，节点${s_i}$的有效约束圆弧的度数$\left| {{\rm{ar}}{{\rm{c}}_i}} \right| = \left| {\bigcup\nolimits_q^{Q = 3} { {{\stackrel \frown{\rm{arc}}_{i\_jq}}}} } \right|$。

需要说明的是，增设$k$覆盖判决，是为了避免出现图5中，环形覆盖的节点被误判为冗余节点。

图 5  不满足圆心$k$覆盖的节点约束圆弧图

下载: 全尺寸图片 幻灯片

3.3   NSSH步骤

NSSH借助Delaunary三角剖分，在尽可能不损害有效覆盖的情况下，缩小覆盖冗余面积，实现了算法执行过程中的本地化。由于需要兼顾以节点为公共顶点的多个Delaunary三角形，引入识别冗余节点策略以弥补半径调整策略的保守性。算法以节点间两两相交和联合覆盖作为区分，进行灰色节点和黑色节点的辨别，对于每一个节点${s_i}$执行如表2所示的NSSH算法步骤。

表 2  NSSH算法步骤

NSSH (${T^i}$,${r_i}$,${\rm{N}}{{\rm{e}}_i}$,${\theta _{{\rm{th}}}}$,${\left| {{\rm{arc}}} \right|_{{\rm{th}}}}$,$k$)
(1)　初始化：${\rm{s}}{{\rm{t}}_i} = 1$, ${\stackrel \frown {{\rm{ar}}{{\rm{c}}_i}}}=\varnothing$
(2)　${r_i}$=半径调整算法(${T^i},{r_i}$)
(3)　for $q = 1:Q$
(4)　　${\rm{if}}({\theta _{i,jq}} > {\theta _{{\rm{th}}}})$) //基于定义5和式(1)判定灰色节点
(5)　　　${\rm{s}}{{\rm{t}}_i} = 0$
(6)　　end if
(7)　　${\stackrel \frown {{\rm{ar}}{{\rm{c}}_i}}}={\stackrel \frown {{\rm{ar}}{{\rm{c}}_i}}} \cup {\stackrel \frown {{\rm{ar}}{{\rm{c}}_{i\_jq}}}}$ //计算有效约束圆弧
(8)　end for
(9)　calculate $\left| {{\rm{ar}}{{\rm{c}}_i}} \right|$ ${k_i}$ //基于式(2)—式(4)计算有效约束圆弧度 数，统计${s_i}$的覆盖度${k_i}$
(10)　if ($\left| {{\rm{ar}}{{\rm{c}}_i}} \right| \ge {\left| {{\rm{arc}}} \right|_{{\rm{th}}}}{\rm{\& \& }}{k_i} \ge k$)//基于定义6判定黑色节点
(11)　　${\rm{s}}{{\rm{t}}_i} = 0$
(12)　end if
(13)　return (${\rm{s}}{{\rm{t}}_i}$)

下载: 导出CSV 

| 显示表格

在节点调度的过程中，半径调整妥协策略利用Delaunary三角剖分，分析以节点为公共顶点的三角集合，仅依赖局部信息对节点感知半径进行有效调整，优化了休眠冗余节点的调度效果。在识别网络中的冗余节点过程中，提出适应多级异构网络的灰色节点判定条件；对于联合冗余覆盖情况，利用有效约束圆弧概念，简化算法计算量。

3.4   算法的复杂度与能耗分析

NSSH算法利用三角图和邻居信息将对传感器网络的覆盖去冗余问题，转化为一跳范围内的节点去冗余问题，实现分布式地利用邻居节点信息，调整节点半径并休眠冗余节点。对于单一节点而言，运行NSSH的复杂度为$O\left( {P + Q} \right)$，仅与其邻居节点数目$Q$和以节点为顶点形成的Delaunary三角形的数目$P$有关。无论是在节点稀疏分布的网络或是节点高密度部署的网络中，均存在$P < N$, $Q < N$，故算法的复杂度为$O\left( N \right)$。

本文所提NSSH算法产生的能耗主要有两个方面：节点调节感知半径后的发射功耗${e_{\rm{r}}}$，节点的通信能耗${e_{\rm{c}}}$，因此整个网络中的总能耗$E$为

其中，${l_{(i)}}$表示节点的半径调整比例，${N'}$表示算法执行后的活动态节点数目，${d_{(i)}}$表示节点通信的平均距离调整比例。由于${N'} \le N$, ${l_{(i)}} \le 1$, ${d_{(i)}} \le 1$，故网络的能耗$E \le 2\max ({e_{\rm r}},{e_{\rm c}}) \cdot N$，而${N'}$, ${l_{(i)}}$以及${d_{(i)}}$随着NSSH算法的进行，逐渐减小，即通信能耗随之减少，且算法不涉及节点的移动部署，故NSSH算法的能耗较低。

4.   仿真分析

4.1   场景配置

本文采用MATLAB R2016a平台进行验证性测试和比较性试验，仿真主要从调整效果、覆盖冗余度两方面对算法进行了测试验证。测试场景设置为$I = 100 \times 100\;{\rm{m}}$的矩形区域。为体现网络中节点的异构性，在初始化阶段，每个节点的感知半径在${r_i} \in [8\;{\rm{m}},12\;{\rm{m}}]$内随机产生。考虑到实验场景和网络配置的随机性，所有实验数据均采用15次独立实验的均值，且对比实验中均保证不同算法间的初始场景一致。

4.2   NSSH的效果测试

对于传感器网络而言，节点的拓扑分布状态，直接反映网络的覆盖冗余。本实验在目标区域部署$N = 200$个和$N = 400$个随机异构节点(如图6(a)和图6(c))，经NSSH调度后，节点感知半径得到一定程度的降低，多余的冗余节点也进行了相应的休眠操作，覆盖冗余度大大降低，基于定义1的评估，原$F(N = 200) = 6.4$和$F(N = 400) = 12.8$的覆盖冗余度降低为图6(b)和图6(d)所示的$F(N = 200) = 1.82$和$F(N = 400) = 1.9$。

图 6  目标区域调整效果对比

下载: 全尺寸图片 幻灯片

4.3   $\text{N}$与$\text{λ}$对$\text{F}$的影响

网络中的节点数量$N$和节点感知半径比$\lambda$，其中$\lambda = {r_{\min }}/{r_{\max }}$，对覆盖冗余度具有至关重要的影响。本实验通过调整网络规模$N$和感知半径比$\lambda$，其中固定${r_{\max }} = 18\;{\rm{m}}$，考察NSSH对网络覆盖冗余$F\;$的影响。

图7的结果表明，随着$N$和$\lambda$的增加，网络的覆盖冗余$F$高速上升；经NSSH算法调度后，目标区域的$F$得到了极大的降低。从数值上分析，当$N = {\rm{100}}$增加到$N = 5{\rm{00}}$, $\lambda = 0.4$增大到$\lambda = 1$时，原始网络的$F$从${\rm{2}}{\rm{.6}}$增大到${\rm{33}}{\rm{.5}}$。经过NSSH调度后，网络的$F$随着$N$和$\lambda$的增加，仅呈现出小幅增长，网络冗余度保持$F < 2.5$。尤其在$N = 5{\rm{00}}$, $\lambda = 1$的极度高密度网络中，NSSH调度前后的冗余落差为$\Delta F = 31.15$。可见，NSSH对于网络规模($N$)和异构跨度($\lambda$)具有较低的敏感性，体现较为优质的场景普适性。

图 7  覆盖冗余度随节点个数和半径比变化情况

下载: 全尺寸图片 幻灯片

4.4   $\text{N}$对$\text{Δ} \text{F}$%的影响

传感器网络的冗余度直接影响网络的能耗，对网络的生命周期起着至关重要的影响。本实验在不同的网络异构条件下，改变网络中部署的节点数量，考察NSSH, MCLC^[1], COAN^[8], NDBS^[9]以及贪婪网格算法GGA对网络冗余度的影响。为保证对比算法均适应于多级异构网络，需要对算法的参数进行调整(如表3)。

表 3  5种算法参数

算法	节点数目
	$N = {\rm{100}}$, $N = {\rm{150}}$		$N = {\rm{200}}$, $N = {\rm{250}}$		$N = {\rm{300}}$, $N = {\rm{350}}$		$N = {\rm{400}}$, $N = {\rm{450}}$		$N = {\rm{500}}$
NSSH	${\theta _{{\rm{th}}}} = 0.82$ ${\left| {{\rm{arc}}} \right|_{{\rm{th}}}} = 1.96{\text{π}}$ $k{\rm{ = 2}}$
GGA	$\mu {\rm{ = 0}}{\rm{.9}}$
MCLC	$\Delta c < 0.05$
COAN	${r_{{\rm{thr}}}} = 4.4$ ${\eta _{{\rm{thr}}}} = 1.87{\text{π}}$ ${m_{{\rm{thr}}}} = 11$ $k = 1$		${r_{{\rm{thr}}}} = 4.6$ ${\eta _{{\rm{thr}}}} = 1.9{\text{π}}$ ${m_{{\rm{thr}}}} = 12$ $k = 1$		${r_{{\rm{thr}}}} = 4.8$ ${\eta _{{\rm{thr}}}} = 1.93{\text{π}}$ ${m_{t{\rm{hr}}}} = 13$ $k = 1$		${r_{{\rm{thr}}}} = 5.2$ ${\eta _{{\rm{thr}}}} = 1.96{\text{π}}$ ${m_{{\rm{thr}}}} = 13$ $k = 1$		${r_{{\rm{thr}}}} = 5.4$ ${\eta _{{\rm{thr}}}} = 1.98{\text{π}}$ ${m_{{\rm{thr}}}} = 15$ $k = 1$
NDBS	${k_2}({r_1}/{r_2}) = 4$ ${k_2}({r_2}/{r_1}) = 7$ ${k_3}({r_1}/{r_2}) = 7$ ${k_3}({r_2}/{r_1}) = 16$		${k_2}({r_1}/{r_2}) = 4$ ${k_2}({r_2}/{r_1}) = 8$ ${k_3}({r_1}/{r_2}) = 8$ ${k_3}({r_2}/{r_1}) = 16$		${k_2}({r_1}/{r_2}) = 4$ ${k_2}({r_2}/{r_1}) = 7$ ${k_3}({r_1}/{r_2}) = 8$ ${k_3}({r_2}/{r_1}){\rm{ = 15}}$		${k_2}({r_1}/{r_2}) = 3$ ${k_2}({r_2}/{r_1}) = 6$ ${k_3}({r_1}/{r_2}) = 7$ ${k_3}({r_2}/{r_1}) = 14$		${k_2}({r_1}/{r_2}) = 3$ ${k_2}({r_2}/{r_1}) = 6$ ${k_3}({r_1}/{r_2}) = 6$ ${k_3}({r_2}/{r_1}) = 13$
注：表中参数$\Delta c$代表MCLC算法覆盖子集的约束条件，${r_{{\rm{thr}}}}$, ${\eta _{{\rm{thr}}}}$, ${m_{{\rm{thr}}}}$仅针对COAN算法，${k_2}({r_1}/{r_2})$, ${k_2}({r_2}/{r_1})$, ${k_3}({r_1}/{r_2})$, ${k_3}({r_2}/{r_1})$仅针对NDBS算法，具体参数解释可查阅文献[8,9]。

下载: 导出CSV 

| 显示表格

异构性参数配置如下：多级异构网络中，每个节点的感知半径${r_i} \in [8\;{\rm{m}},12\;{\rm{m}}]$随机产生；2级异构网络中，节点分为两类，即感知半径${r_i} = 8\;{\rm{m}}$或$10\;{\rm{m}}$；同构网络中，节点的感知半径统一设置为${r_i} = 10\;{\rm{m}}$。

从图8—图10的实验数据中可以看出，无论在何种异构网络中，由于随着$N$的增加，网络冗余逐渐增加，使得5种算法进行冗余删减的空间也逐渐增加，在实验曲线上体现为5种算法对网络冗余的降低率$\Delta F$也随着$N$的增加呈递增趋势。相比于中心式算法GGA，本文所提的NSSH算法在复杂度降低的同时，实现了网络覆盖冗余降低率$\Delta F\;$的性能紧随其后，且这种差距随着$N$的增加，逐渐衰减，最终基本与GGA调度效果持平。在调度过程中，由于MCLC调度的主要目标是为了产生最大数目互不相交的覆盖集合，且对入选每个覆盖子集的节点筛选条件相对宽松，NDBS需要综合节点与邻居节点距离、重叠覆盖关系以及其邻居节点集数目等因素，而COAN需要综合3类邻居节点集间的数目关系，因而去冗余效果略差强人意。

图 8  多级异构网络中$\Delta F\;$的变化

下载: 全尺寸图片 幻灯片

图 9  二级异构网络中$\Delta F\;$的变化

下载: 全尺寸图片 幻灯片

图 10  同构网络中$\Delta F\;$的变化

下载: 全尺寸图片 幻灯片

从表3的参数设置中可以看出，COAN和NDBS在高密度节点部署的网络中，随着$N$的增加，需要对参数进行一定的调整，以保持网络覆盖率和降低冗余之间的平衡。而MCLC对节点的调度实现不依赖参数设置，NSSH和GGA则对各自参数在不同的网络中具有稳定的透明性和低敏感性，采用具有泛化性能的参数配置，即可实现多场景下的覆盖去冗余。另一方面，NSSH利用Delaunary三角剖分实现了节点调度的本地化，相较集中式的MCLC算法和贪婪机制下的GGA算法，具有更好普适性。

5.   结论

针对多级随机异构无线传感器网络中，节点间的叠加覆盖导致网络覆盖效率低下，本文提出了一种基于局部Delaunary三角形和节点相邻关系的覆盖优化算法NSSH。在研究对象上，NSSH在多级异构、2级异构和同构网络中，均能保持稳定可靠地工作；结合半径妥协调整和灰、黑色节点识别策略，保证了NSSH的去冗余质量；基于三角剖分子集，实现了节点调度过程中的本地化。但客观上分析，算法运行前期，需要节点进行多次的信息交互，会一定程度上提高通信能耗。因此，本算法对于高密度的近距离网络更具优势。