基于安全连接的WSN节点优化部署*

孙子文,申 栋(.江南大学物联网工程学院,江苏 无锡 2422;2.物联网技术应用教育部工程研究中心,江苏 无锡 2422)

无线传感器网络WSN(Wireless Sensor Network)正在改变着人类与物理世界的交互方式[1-3],在许多领域得到了广泛的应用。在网络部署初期,特别是在无人触及或容易受损的环境中,保证网络的安全性具有重要意义,网络安全是无线传感器网络的首要研究问题之一。无线传感器网络节点覆盖性能的好坏很大程度上决定了无线传感器网络的性能,直接体现网络的感知、监视和通信等服务质量,同时还会影响网络资源的管理,覆盖算法的性能优劣同样影响着网络的生存期[4-5]。因此,在保证节点安全连接的前提下对无线传感器网络覆盖性能优化的方案的研究具有至关重要的意义。

为了保证无线传感器网络初始部署节点间的安全通信,研究人员已经提出了一些无线传感器网络密钥管理方案[6-8],但是此类方案初始部署以后节点往往没法覆盖整个无线传感器网络部署区域,因此需要进行节点覆盖优化。文献[9-10]针对二维部署区域的无线传感器网络覆盖优化展开了基于泰森多边形形心的部署方案的研究。文献[9]提出了基于泰森(Voronoi)多边形形心的部署方案CBS(Centroid-Based Scheme),引入了泰森多边形形心的概念,将节点移动到泰森多边形形心位置,提高了节点的覆盖率,通过把整个网络部署区域覆盖优化的问题转换为每个泰森多边形区域的覆盖优化问题,从而减小了计算复杂度,但是此方案没有考虑邻居节点的覆盖影响,因而节点移动后会产生新的盲区。文献[10]提出了一种基于泰森盲区多边形形心的覆盖控制部署方案BCBS(Blind-Zone Centroid-Based Scheme),将邻居节点对泰森多边形的覆盖考虑进来,确保泰森多边形的形心位于泰森多边形盲区的中心位置,并构造与盲区位置相似的泰森多边形,通过将无线传感器网络节点移动到泰森多边形盲区中心位置来提高节点的覆盖率,此方案虽然考虑了邻居节点的影响,但是形心确定方法太复杂。

一些网络优化部署方案在泰森多边形优化覆盖的基础上,开始考虑结合虚拟力算法[11-13]。文献[11]在泰森多边形形心的优化策略基础上,结合虚拟力算法,采用了Voronoi多边形形心导向的虚拟力自部署的无线传感器网络部署策略,在考虑传感器网络节点的邻居节点对其引力斥力的同时加入无线传感器网络节点所在的泰森多边形形心的引力,提高了节点的覆盖率,减小了节点的移动距离和能量的消耗;文献[12-13]利用虚拟力算法采用未被无线传感器网络节点覆盖的Voronoi图顶点和Voronoi图边界对无线传感器网络节点为引力作用来引导共享密钥来保证网络节点间的安全连接,文献[11-13]的方案虽然改善了无线传感器网络部署区域的覆盖性能,但是节点移动提高节点覆盖率时会破坏传感器网络节点之间已存在共享密钥的安全连接。

针对目前无线传感器网络覆盖优化方案没有考虑节点之间已有的安全连接问题,本文采用基于泰森多边形形心虚拟力和节点安全连接虚拟力的部署方案。该方案以节点覆盖率为优化目标,结合无线传感器网络节点间的共享密钥,引入安全连接虚拟力,减少了无线传感器网络覆盖优化节点移动时对存在共享密钥的邻居节点的安全连接的破坏,以保证节点的安全连接;采用改进泰森多边形形心虚拟力算法,能够有效指导节点移动过程和实现全局优化,以提高节点覆盖率。

1 WSN覆盖模型

设在无线传感器网络二维平面部署区域T中,N个有相同感知半径Rs和通信半径Rc的无线传感器网络节点(以下简称节点)随机部署在区域T内,设节点集为S={S1,S2,S3,…,SN},其中节点Si的位置坐标表示为(Sxi,Syi)。初始部署时,采用适当的无线传感器网络密钥分配方案进行密钥分配,使邻居节点之间存在共享密钥以建立安全连接。

将部署区域T离散化为m×n个目标点集T={T1,T2,T3,…,Tm×n},其中目标点Ti的位置坐标表示为(Txi,Tyi),则目标点Tj与节点Si的距离为:

(1)

节点Si对目标点Tj的感知概率P(Si,Tj)采用布尔感知模型[14-15]计算:

(2)

如果目标点Tj到节点Si的距离小于或者等于节点的感知半径Rs,即d(Si,Tj)≤Rs,节点Si对目标点Tj的感知概率为1,即目标点被节点覆盖;否则,节点Si对目标点Tj的感知概率为0,即目标点没有被节点覆盖。

对目标点Tj的联合感知概率Ij是节点集对目标点Tj覆盖率的并集,计算公式为:

(3)

只要目标点Tj被节点集S任意一个节点覆盖,则对目标点的联合感知概率为1,否则联合感概率为0[16]。

假设所有目标点Tj的面积均为Δm×Δn,如果目标点被覆盖,则目标点的联合感知概率为1,覆盖面积为Δm×Δn,否则为0,所以目标点Tj的覆盖面积可表示为Ij×Δm×Δn;同样可知,整个区域T的总面积为AS=(m×n)(Δm×Δn)。在网络部署区域T中,节点部署后节点所覆盖的面积占部署区域总面积的比值称为节点覆盖率ψ[17],计算如下:

(4)

式中:AT表示所有节点覆盖的总面积,AS表示整个部署区域的总面积。

2 基于安全连接的形心导向虚拟力覆盖方案

基于安全连接的形心导向虚拟力覆盖方案主要分为两个阶段:节点虚拟力受力分析、节点移动过程。

2.1 节点虚拟力受力分析

虚拟力算法VFA(Virtual Force Algorithm)[18]最早应用于未知环境中的移动机器人实时避障的算法,Zou等人[18]首先将虚拟力算法应用于解决无线传感器网络覆盖优化问题,其基本思想是将每个节点抽象为一个虚拟电荷,各节点受周围其他节点力的作用为虚拟力。

基于虚拟力的原始定义,本文加以拓展,定义了4种类型的虚拟力:节点虚拟力、安全连接虚拟力、泰森多边形形心虚拟力、Voronoi图顶点虚拟力。前两种虚拟力是节点受到来自其他实体节点的虚拟力,后两种虚拟力是节点受到来自其他虚拟节点的虚拟力。

2.1.1 节点虚拟力

节点之间的虚拟力用式(5)描述:

(5)

图1 节点虚拟力

2.1.2 安全连接虚拟力

(6)

2.1.3 泰森多边形形心虚拟力

①泰森多边形的划分

在无线传感器网络部署区域中,对部署区域进行Delaunay三角剖分,节点连线形成Delaunay三角网,如图2所示。

图2 Delaunay三角网

图3 Voronoi图

对每个Delaunay三角形每条边作垂直平分线,各条垂直平分线与部署区域边界围成的凸多边形称为泰森多边形,即图3中凸多边形D1D2D3D4D5是其中一个泰森多边形。泰森多边形构成的网状图则称为Voronoi图,即图3中虚线与部署区域边界构成的网状图称为Voronoi图。

②泰森多边形形心

形心取截面图形的几何中心,对于密度均匀的实物体,质心和形心重合。n条边顶点为(Vixi,Viyi)的泰森多边形形心(Cix,Ciy)的计算公式为[11]:

(7)

式中:AVi表示泰森多边形的面积,其计算公式为:

(8)

③节点的形心虚拟力

图4 泰森多边形形心引力

(9)

2.1.4 Voronoi图顶点虚拟力

部署区域进行Voronoi图划分之后,可能出现未被节点覆盖的Voronoi图顶点,如图5所示,Voronoi图顶点D1,D5没有被任何节点覆盖。

图5 Voronoi图顶点虚拟力

(10)

2.1.5 节点综合受力分析

(11)

(12)

2.2 节点的移动过程

(13)

(14)

2.3 覆盖方案流程图

通过节点虚拟力受力分析,以及节点移动两个阶段,节点到达部署位置。基于安全连接的形心导向虚拟力覆盖优化方案的流程图如图6所示。

图6 基于安全连接的形心导向虚拟力覆盖方案流程图

具体算法描述如下:

①将部署区域T划分为若干个泰森多边形,泰森多边形集合为V={V1,V2,V3,…,VN},泰森多边形形心集合C={C1,C2,C3,…,CN},根据式(7)和式(8)计Voronoi多边形形心位置集合为{(C1x,C1y),(C2x,C2y),…,(CNx,CNy)};

②计算节点Si与存在共享密钥的邻居节点、Vi形心、未被覆盖的Voronoi多边形顶点、无共享密钥邻居节点的距离;

⑤计算节点Si位置更新后的覆盖率为ψ,如果覆盖率达到要求,节点停止移动,否则重复步骤①～步骤④。

3 仿真实验与结果分析

为研究该方案的有效性,对该方案进行了仿真实验,并与文献[9]方案与文献[12]方案的性能进行了对比。

3.1 仿真环境及参数设置

仿真采用MATLAB 2014a进行,仿真实验所涉及的参数如表1所示。

表1 仿真实验参数

图7 正三角形部署

3.2 仿真结果及分析

3.2.1 存在共享密钥节点的安全连接

假设在无线传感器网络初始部署时,每一对邻居节点都会存在共享密钥,能够建立安全的通信连接。在修复初始部署的覆盖空洞移动节点过程中,可能会破坏这些已经存在共享密钥的安全连接,仿真的目的是比较安全连接的破坏程度。初始部署以及每个方案节点位置更新100次以后存在共享密钥节点的安全连接的仿真结果如图8所示。

图8 安全连接比较图

由仿真结果图8所示,图8中的连线表示节点之间存在共享密钥的安全连接,节点位置更新100次后所有方案的安全连接都会减少的,具体存在共享密钥节点的安全连接个数如表2所示。节点初始部署时,节点间有共享密钥的安全连接的个数为251个,节点位置更新100次以后,本文方案存在236个安全连接,而文献[9,12]分别存在178、186个安全连接,可见,与文献[9]方案和文献[12]方案相比,本文方案节点移动对安全连接的破坏减少。

表2 存在共享密钥节点的安全连接个数

3.2.1 节点的覆盖率

提高节点的覆盖率是无线传感器网络覆盖优化的目标,直接关系到网络的覆盖质量。网络初始部署以及每种方案节点移动100次后的覆盖情况和覆盖率仿真结果如图9和图10所示。

图10 节点覆盖率

由图9可知,与节点的初始部署相比,可知每种方案在节点移动100次以后,节点分布更加均匀。由图10可知,节点的覆盖率都是随着位置更新次数的增加而增大,本文方案与文献[9]方案和文献[12]方案相比在节点位置更新相同的次数时有更高的节点覆盖率。初始部署时,节点的覆盖率为72.64%,在节点位置更新100次以后,本文方案的节点覆盖率提高到98.81%,文献[9]方案和文献[12]方案的节点覆盖率分别为97.57%和96.53%。

图9 节点覆盖情况比较

4 结束语

本文设计的基于泰森多边形形心引力和节点安全连接引力的虚拟力的部署方案,通过引入邻居节点存在共享密钥的安全连接虚拟力减小节点安全连接被破坏,同时泰森多边形形心虚拟力、泰森多边形顶点虚拟力、节点虚拟力能够有效指导节点移动过程,提高无线传感器网络覆盖率。