葛玉君

（江南大学，江苏 无锡 214122）

0 引言

无线传感器网络（Wireless Sensor Network，WSN）[1-2]在生活中应用广泛。边界检测主要基于位置[3]、基于统计[4]、基于连接[5]。基于位置与统计的方法，要么需要传感器精确的坐标信息，代价昂贵；要么要求高节点密度，精度与网络普适性差。基于连接性的方法，实现成本低于位置方法，精度优于统计方法，适用性强。本文提出的算法基于两跳邻居节点的连接信息。引入的中心性方法，常用来判断节点的重要性，识别WSN边界是其副产品[6]。通过计算中介中心性，量化节点重要程度。仿真表明，在边界识别问题上有良好的适用性。

1 中介中心性

1.1 概念

最著名的中间度量为Freeman[7]首次在图论中引入的中介中心性，将中心性与信息控制相联系，描述一个节点被其他节点的需要程度[8]。

其中，σst为节点s到节点t的最短路径数量，σst(v)为从节点s到t的所有最短路径中经过节点v的最短路径的数目。由定义求解中心性过于复杂，故通过引入节点对依赖值对定义实现简化[9]。据此Brands提出目前已知的最快的算法。

1.2 中心性与边界的关系

由定义知，节点的中介中心性越大，越可能靠近网络中心[10]，反之，中心性值越小，成为边界节点的概率就越大。WSN中，高中心性节点（图1中节点1）可促进节点间直接或间接通信，对从任何节点开始的信息流都至关重要。基于这一发现，可以通过计算节点的中心性值从而确定边界节点。

图1 简单网络

2 算法介绍

2.1 模型假设

WSN由G(V,E)表示，其中V为节点集，E是连接节点边的集合。节点i的k跳领域图，使用Gi(Vi,Ei)表示。节点均具各向同性且ID信息唯一。考虑实际应用中环境的友好程度，传感器均匀分布在感知区域，可具任意形状的通信范围。

2.2 算法实现

精确计算大型网络中节点的中心性，其网络和计算成本及其昂贵。在实际WSN中算法复杂度随节点数增加而增加，如邻接矩阵的规模即达到O(N2)。因此将全局问题转化为局部求解。如表1所示，k从2开始取。算法主要思想是，基于边界节点的中心性值较低。对节点对之间的路径计算，主要通过最短路径算法（不考虑多次经过同一个节点的情况）。故对边界识别问题，采用近似化算法，进行分布式检测。先为每个传感器构建其k跳邻域图，根据邻域图计算节点的中介中心性。再比较中心性的值选择值较低的节点为边界节点。

表1 不同k值的节点中心性

3 仿真与分析

为便于仿真，假设节点的通信区域为以节点为中心的圆，通信半径rc，在图上仅标注通过算法识别的边界节点。

3.1 不同k值

图2为k取不同值时所得结果，WSN总节点数为3 236，平均节点密度为12。实验表明仅使用原始计算的小部分，结果就具很高的有效性。另一方面，由于算法的复杂度主要在于k跳领域图内的节点数，故当k取值越小，其算法复杂度也越小。表2为k取不同值时的误认率情况。在节点密度恒定的网络中，通过算法运行时间和边界误认率的综合比较，证明2-中介中心性测度是较好的中心性近似选择，且对于边界识别算法具有较好的使用性。

图2 不同k值结果

表2 不同k值误认率

故对于每个节点，只使用k个步骤来计算最短路径，通过BFS算法遍历每个节点的k跳邻居节点，节省大量计算时间，且对结果度量的影响最小。

3.2 不同形状的边界

WSN平均节点密度为10，k取2，在不同形状边界的网络中，结果如图3所示。左图为网络部署，右图为检测出的边界。结果表明，本算法适用性较强，对不同形状的边界均适用良好。

图3 不同边界形状的WSN

4 结语

本文提出一种边界识别算法，通过引入中心性概念识别出边界点。综合考虑算法的复杂度与结果的误认率，选择通过节点的2-中介中心性，从而找到WSN边界节点。