基于几何方法的分布式无线传感器网络边界节点识别算法研究*

赵利辉，杨秋翔

(中北大学 软件学院，山西 太原 030051)

0 引 言

无线传感器节点具有成本低、功耗小，能够感知声、光、震动和辐射等多种事件的功能，并且能够以无线通信的方式自组织形成多跳网络[1]，由众多无线传感器节点构成的多跳网络称为无线传感器网络(Wireless Sensor Networks，简称WSN). WSN在执行恶劣环境下的目标监测任务方面展现出独有的优势，例如在军事领域的战场态势监测、无人值守环境下的边境越境监测、建筑物结构安全监测、危化品监测等方面都发挥了重要作用.

大规模WSN通常基于机载平台以抛洒方式进行部署，在此过程中，极易遭受各种外力作用造成节点布撒不均匀、外力撞击破坏和节点能量耗竭导致的节点失效，从而使WSN无法完整地感知整个监测区域内事件的发生，通常将目标区域中无法由传感器节点感知的监测区域称为网络覆盖空洞. WSN固有的特性使得覆盖空洞的出现不可避免，一方面覆盖空洞降低了WSN对目标监测区域的覆盖能力，另一方面覆盖空洞会引发WSN中监测数据路由路障、导致节点负载不均衡等一系列问题，甚至使更多节点失效形成更大规模的覆盖空洞，从而严重影响整个网络的生命周期和服务质量.

由于WSN在军事和民用领域不断延伸的应用趋势和特定场景下的无可替代性，研究能够长时、稳定和可靠地执行值守任务的WSN成为该领域的重要问题. 识别WSN中的边界节点是研究覆盖空洞的关键问题，对其研究不仅可以深入刻画覆盖空洞的形状、规模而且可以提高WSN数据路由效率，保障数据路由安全. 依据国内外学者采用的边界节点识别技术的不同，边界节点识别算法可以归类为： ① 基于几何的边界节点识别方法； ② 基于统计的边界节点识别方法； ③ 基于网络结构拓扑的边界节点识别方法.

由于WSN中边界节点的感知区域通常不能被其它节点的感知区域覆盖，利用这一特性学者们研究出了基于几何和网络拓扑的边界节点识别算法. 不同的学者分别使用三角形环绕、多边形环绕、通过抽取网络的最大独立集构建节点的多层次闭合环绕多边形的方式判断WSN中的节点是否为边界节点.

Khedr等[2]提出一种通过搜索WSN中每个节点的邻居节点是否能形成闭合“周界”的算法来判断节点是否为边界节点，该算法简称为PD算法. PD算法基于Barycentric坐标技术，通过检测分布于坐标系四个象区之间待识别节点的邻居节点之间的连通性判断节点是否为边界节点. Simek[3]和Deogun[4]等利用WSN中节点的一跳或多跳邻居是否能构成闭合三角形并将其环绕在内实现边界节点的判别，两种算法的区别在于Simek改进了三角形构建方法，加速了三角形构建速度，也提高了识别的精度. Ma[5]则利用三角形外接圆特性实现了边界节点识别算法. Massinissa Saoudi[6]等基于最小极角提出一种称为D-LPCN的边界节点识别算法. Khder[7]等通过改进文献[8]的算法提出一种通过计算节点邻居感知区域交叉点的方式进行边界节点识别的算法. 通常情况下，边界节点的度低于网络中非边界节点的度，Fekete[9]利用该特性提出一种“限制压力中心”算法用于识别边界节点，该算法仅适用于网络密度大于100的情况，当前应用场景下的WSN很难达到如此高的节点密度. Wang等[10]利用最短路径树、割点对和最近公共祖先提出一种基于拓扑的识别方法，该算法的优点是网络密度较小(≥7)的情况下也可以识别边界节点，缺点是根节点选择困难，识别过程多次使用泛洪算法导致节点能量消耗较大，且无法识别三角形覆盖空洞. Sauth[11]和Khan[12]等分别利用改进的“花”结构的模式搜索和跳信息实现边界节点的识别. 边界节点的一个本质特征是其不能与其邻居节点构成封闭的环状网络，也不能由其邻居构成封闭环状网络包围，利用上述特征，Funke等提出了一种基于节点闭合轮廓识别的边界节点识别算法，简称DHD[13]. 上述算法共同的问题是算法仅在网络节点密度大于20的情况下才可使用，否则节点识别精度过低且不能识别较小空洞边缘的节点，难以适应稀疏网络的需求.

本文在总结近几年WSN网络覆盖与边界节点识别研究成果的基础上，详细分析了WSN网络覆盖空同的结构特征，针对刻画覆盖空洞结构的网络边界节点识别问题进行了深入的研究、分析和仿真验证. 为克服传统识别方法中对网络密度要求高、识别精度低的问题提出一种基于几何技术的边界节点识别方法，该方法具有复杂度低、网络密度要求低、识别精度高、泛化能力好的特点，同时本文也是对前期工作[14]的一次改进.

1 系统模型与定义

1.1 定义与符号

定义 1 边界节点： 如图 1 所示为一个WSN，网络最外层节点11～15，17～26一起构成了环绕监测区域的外围边界，本文将上述节点称为边界节点，而节点1, 2, 3, 4, 5, 6, 7, 8和节点4, 5, 25, 26所环绕的阴影监测区域由于没有节点能够感知覆盖因而形成覆盖空洞，这些环绕覆盖空洞的节点本文也称为边界节点.

定义 2 参考节点： WSN中执行边界节点识别算法的节点，如图 2 中节点so.

定义 3 内部节点： 无线传感器网络中除边界节点之外的节点称为内部节点.

图 1 边界节点、覆盖空洞示意图Fig.1 Illustration of boundary node and coverage hole

图 2 定义说明Fig.2 Illustration of definition

(1)

文中用到的其它符号如表 1 所示.

表 1 符号说明表Tab.1 Symbol description

1.2 网络模型

(2)

2 基于几何方法的分布式边界节点识别算法

识别边界节点是检测和修复无线传感器网络覆盖空洞的关键问题，已有方法存在的主要问题是： ① 需要节点的精确节点位置信息，② 边界节点正确识别率低，③ 识别过程能量消耗大. 针对上述问题，本文提出一种自适应的基于几何技术的分布式无线传感器网络边界节点识别算法(A distributed geometric scheme for detecting boundary nodes in the wireless sensor networks，简称DGSD).

2.1 算法描述

DGSD算法可描述为：

输入：G=(V,E)；

输出： 边界节点集；

步骤1： 收集节点的一跳和二跳邻居信息，该过程通过构建节点的无向连通图G=(V,E)，由节点向其邻居节点发送Hello报文收集和维护其邻居信息表.

步骤2： 参考节点根据定义2构建LCCS.

步骤3： 参考节点利用LCCS和公式(1)收集其一跳和二跳邻居节点，并计算相应的绝对角.

步骤4： 参考节点以绝对角升序规则排序其邻居节点.

步骤5： 如果节点存在绝对角相同的邻居节点，则保留其邻居表中距离其最近的邻居节点.

步骤7： 输出边界节点集.

2.2 算法理论分析

定理1 如果一个节点满足条件deg(so)≤2，则该节点必为边界节点.

(3)

(4)

(5)

引理1 给定参考节点so，对于so的一跳和二跳邻居集合{sk|sk(k=1,…,n)}，如果节点so满足下列任意条件，则该节点为无线传感器网络中的一个边界节点：

1) max(∠abs(sk))≤π,

2) min(∠abs(sk))>π,

图 3 定理1证明示意图Fig.3 Diagram of the demonstration of theorem 1

图 4 推论 1 证明示意图Fig.4 Diagram of the demonstration of lemma 1

引理2 给定参考节点，假设的感知区域边界能被他的邻居节点完全覆盖，但其邻居节点之间不能形成一个闭合环路，则该节点为边界节点.

证明如图 5 所示，虽然B(so)能够由其邻居节点集{s1,s2,…,s8}完全覆盖，由于d(so,s8)>Rc和d(s1,s8)>Rc，因而so无法计算其是否被邻居节点覆盖而判断为边界节点. 证毕.

图 5 推论 2 证明示意图Fig.5 Diagram of the demonstration of lemma 2

3 仿真实验与性能评估

本文基于Windows 10和MATLAB 2016b进行了实验仿真，实验首先在文献[3]提供的数据集中进行了验证，同时还通过多种自建场景下的仿真数据对DGSD算法性能进行了评估，实验评估的指标包括： 节点正确识别率(为便于公式表述记为succ)、节点错误识别率(为便于公式表述记为false)，其计算方法分别如式(6)和(7)所示.

(6)

false=

(7)

式中：R(nodes)表示仿真实验中实际检测到的边界节点；P(nodes)表示Simek数据集中提供的标准边界节点集.

3.1 检测率比较

在节点识别率对比实验中，本文首先利用文献[3]中提供的数据集进行了实验仿真和比较，其数据环境为： ① 节点规模分别为50, 100和400，② 节点密度为8到26，节点密度间隔为2，③ 节点通信半径为20～35 m，间隔为5 m. 由于基于统计的识别方法要求节点密度过大，因而本文选取提供数据集的文献[3]和基于拓扑方法的文献[13]中的算法作为本文实验的对比对象，图 6 和图 7 分别给出了节点规模为400，节点密度为8～26的场景下三种算法的正确识别率和错误识别率对比图，显然可以看出，DGSD除在节点密度为8时正确检测率低于Funke提出的算法，在其余场景下的识别精度均优于其它对比算法，其平均正确识别率稳定在92%以上，平均错误识别率低于6%，而Simek算法识别精度较低的原因在于基于三角形的判断，在极端情况下会引起数值计算误差和三角形误差引起的构建不全面导致检测失败. 从对比结果来看，DGSD算法较其它算法在不同的网络节点密度和节点通信半径下均表现出较好的鲁棒性和更强的泛化能力. 同时，三种算法也呈现出一个共同的特征，即随着节点密度的增大边界节点的正确识别率也不断增大，这主要是由于随着节点密度的增加，网络覆盖能力增大，从拓扑连接和角度计算方面精确度都得到了提高，因而节点正确识别率也得到提高.

图 6 正确检测率对比图Fig.6 Comparison of precision ratio

图 7 误检率对比图Fig.7 Comparison of fallout ratios

3.2 大规模覆盖空洞实验

为进一步验证DGSD的泛化能力，随机部署了2 000个节点到一个的监测区域，区域中含有一个五角星形覆盖空洞，Simek、DGSD和Funke三种算法的检测结果分别如图 8～图 10 所示，三种算法在该场景下检测到的边界节点分别为972, 531和1 247个，由上述图中显然可看出，DSGD检测到的边界节点数目少于Simek和Funke算法检出的边界节点，然而这些检出的边界节点已经能够清晰地刻画网络边界和覆盖空洞的边缘区域.

图 8 边界节点为972的BRC检测结果Fig.8 BRC result of 972 boundary nodes

图 9 边界节点为531的DGSD检测结果Fig.9 DGSD result of 531 boundary nodes

图 10 边界节点为1 247的Funke检测结果Fig.10 Funke result of 1 247 boundary nodes

3.3 能耗比较

节点能量的消耗是影响网络生命周期的关键指标，在能量消耗仿真实验中，节点能量消耗模型如式(8)和(9)所示，参数意义与文献[15-16]相同，网络中节点数量、密度和通信半径等参数设置与正确检测率比较实验相同.图 11 给出了Simek、DGSD和Funke三种算法在上述实验条件下节点的能耗对比，由图 11 可以得出一个明显的结论即网络中节点执行边界节点识别所消耗的总体能量随着网络节点密度的增加而增大，原因是节点密度增大导致节点需要接收和处理的报文增多，由能耗模型可知这需要消耗节点更多的能量，同时也可以看出在所有对比实验中DGSD算法的能量消耗显著低于其它对比算法，这主要是由于Simek算法在每次三角形构建过程中都需要重复计算其全部二跳邻居信息，而Funke算法则在最大独立集的拓扑发现过程和以最大独立集中每节点搜寻以其为圆心的多层闭合环路过程中消耗了大量能量.

(8)

ERx=L×Eelec.

(9)

图 11 DGSD、Simek和Funke节点能量消耗对比图Fig.11 Comparison of energy dissipation of DGSD, Simek and Funke

3.4 算法复杂度分析

DGSD算法可以分解为： 收集节点邻居信息，计算节点绝对角，节点排序和边界节点识别四个过程，上述过程的算法复杂度分别为O(n+m)，O(n)，O(nlog(n))和O(kn)，这里，n=|V|，m=|E|，k表示平均节点度，因而DGSD算法的总体复杂度为O((2+log(n)+k)n+m)，Simek算法和Funke算法在邻居信息搜集极端具有相同的复杂度，在边界节点识别阶段其总体复杂度分别为O(3(k-1)n)和O(|I|n)，这里I表示网络的最大独立集，综合邻居信息收集两者的总体复杂度分别为O((3k-2)n+m)和O(|I|n+m)，在具体网络中可以得出DGSD算法复杂度低于其它对比算法.

4 结 论

针对大规模无线传感器网络中节点部署不均匀和节点失效引起的覆盖空洞问题，提出一种基于几何方法的分布式边界节点识别算法，该方法利用节点的绝对角特征，实现了边界节点的自动识别. 大量仿真实验结果表明： 同现有算法相比，该算法在不同网络规模和密度场景下都能稳定、高精度、低能耗地识别网络种的边界节点，这说明DGSD鲁棒性高、泛化性好，同时其算法复杂度较现有算法也较低，能够适应不同规模和密度的网络环境.