葛玉君

（江南大学，江苏 无锡 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)表示。……