无线传感器网络节点多目标安全优化部署*

孙子文,申 栋

(1.江南大学物联网工程学院,江苏 无锡 214122;2.物联网技术应用教育部工程研究中心,江苏 无锡 214122)

无线传感器网络WSN(Wireless Sensor Network)在许多领域得到了广泛的应用[1-3],对无线传感器网络性能的研究也就成了重要的研究内容。网络安全是网络的基础[4],网络部署是影响WSN性能的关键环节,而重要的考虑因素包括网络部署时的覆盖质量以及网络部署时的安全性[5],因而网络通信链路的安全连接性和网络的覆盖质量等问题,成为网络节点部署研究领域的关键问题。

为提高网络部署时的节点覆盖性能,部分学者提出了以节点覆盖率为目标函数的单目标优化部署方案[6-8]。基于泰森多边形形心的部署方案CBS(Centroid Based Scheme)将节点移动到泰森多边形形心位置[6],把整个网络部署区域覆盖优化问题转换为每个泰森多边形区域的覆盖优化问题,从而减小了计算复杂度,提高了节点的覆盖率;在泰森多边形优化覆盖的基础上,结合虚拟力算法,引入Voronoi图顶点引力和Voronoi图边界引力,引导网络部署时节点的位置移动[7,8],以提高节点覆盖率。考虑提高节点覆盖率的单目标优化网络节点部署优化方案虽然提高了网络的覆盖率[6-8]的方案对网络的能耗等性能并没有改善。

为提高网络部署时的覆盖率和降低能耗,研究人员提出了多目标优化的节点优化部署方案[9-12]。通过建立最大化节点覆盖率和最小化网络能耗两个优化目标函数,采用多目标优化的二进制粒子群算法,并引入Pareto求解策略,得到高节点覆盖率和低能耗的网络节点部署方案[9];一种新的基于信息共享的粒子群优化算法PSO(Particle Swarm Optimization),设计了人工免疫系统多样性维持机制,将免疫优化引入粒子群算法,维持种群多样性,提高了节点覆盖率,减小了能量消耗[10];通过遗传算法来进行无线传感器节点部署,结合能耗与覆盖率计算节点的地理位置,提出了基于模糊主导地位的多目标优化算法,利用切比雪夫公式进行多种不同权值下的子问题优化,将个体中每个目标转换为模糊主导因子,利用主导因子来替代支配关系,使网络节点的覆盖率提高、网络寿命增长、节点连通性提高[11];一种二进制和概率覆盖模型的一种集中免疫-Voronoi部署算法,以节点覆盖率、节点移动能耗为优化目标,采用多目标集中免疫算法,利用Voronoi图的特性进行目标优化,提高了节点覆盖率、减小了节点移动能耗[12]。以上的多目标优化算法已考虑了节点部署时网络覆盖率,但是没有考虑节点之间已有的安全连接问题。

针对目前无线传感器网络节点多目标覆盖优化方案没有考虑节点之间安全连接的问题。本文在节点部署优化中以提高网络覆盖率为优化目标的同时,将节点的安全连接度也作为优化目标,以节点全连通约束和节点移动能耗作为约束条件,建立多目标节点安全部署优化模型,采用改进的粒子群优化算法进行求解,能够得到最大的网络覆盖率以及最大网络安全连通度。

1 多目标节点安全优化部署模型

将无线传感器网络多目标节点的优化部署问题建模为节点全连通约束和节点移动能耗两个约束条件下,以节点覆盖率、节点安全连通度为目标函数的多目标节点优化部署方案。

1.1 网络模型

设在无线传感器网络二维平面部署区域T中,随机部署着N个有相同感知半径Rs和通信半径Rc的无线传感器网络节点(以下简称节点),节点集为S={S1,S2,S3,…,SN},其中节点Si的位置坐标表示为(xSi,ySi)。

1.2 多目标节点安全优化部署的数学模型

多目标组合优化问题,可以看作是一组参数(决策变量)到一组目标的映射[13]。在无线传感器网络节点安全优化部署问题中,需考虑提高网络的安全性的同时提高网络覆盖率,因此,引入多目标优化策略,设计了考虑安全性和覆盖率的两个目标函数。为此,建立基于安全连通度的多目标节点优化部署的数学模型:

(1)

1.3 目标函数

1.3.1 安全连通度目标函数

无线传感器网络中的节点连通度是指网络中节点一跳范围之内能够与其通信的相邻节点的数量与网络中节点总数量二次方的比值,连通度越大,网络中存在的通路就越多,网络的连通性能越好。无线传感器网络中的节点连通度可以描述为:

(2)

式中:ρij为相邻节点的连通因子:

(3)

当节点间距离d(Si,Sj)小于或者等于通信半径Rc时,ρij=1,即节点Si与Sj存在无线通信;当节点间的距离d(Si,Sj)大于通信半径RS时,ρij=0,即节点Si与Sj不存在无线通信。

假设无线传感器网络在节点部署前使用了密钥管理方案,节点能够通过共享密钥建立安全的连接。本文将节点连通度的概念延伸,定义无线传感器网络节点安全连通度为:

(4)

(5)

进一步建立第1个目标函数为节点安全连通度目标函数:

(6)

节点安全连通度能够反映网络安全性能的高低,节点的安全连通度越大节点与更多的邻居节点存在共享密钥,网络的安全性能越高。

1.3.2 网络覆盖率目标函数

将部署区域T离散化为m×n个目标点集T={T1,T2,T3,…,Tm×n},其中目标点Tl的位置坐标表示为(xTl,yTl)(l=1,2,3,…,m×n)。则目标点Tl与节点Si的欧氏距离为:

(7)

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

(8)

如果d(Si,Tl)≤Rs,节点Si对目标点Tl的感知概率为1,即目标点被节点覆盖;否则,节点Si对目标点Tl的感知概率为0,即目标点没有被节点覆盖。

对目标点Tl的联合感知概率Il是节点集S={S1,S2,S3,…,SN}对目标点Tl覆盖率的并集为:

(9)

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

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

(10)

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

建立第2个目标函数即网络覆盖率目标函数:

(11)

网络覆盖率能够反映网络对整个覆盖区域的监测性能,覆盖率越大表示能够监测的区域越大。

1.4 约束条件

1.4.1 节点全连通约束

无线传感器网络节点全连通保证了网络中任意两个节点之间均存在至少一条可以直接或者间接进行通信的路径。节点全连通约束可以表示为:

∀i∈[1,N],∃j∈[1,N],i≠j,满足d(Si,Sj)≤Rc

(12)

1.4.2 节点移动能耗约束

节点的能量有限,因此需要考虑节点移动消耗的能量,对节点移动的最大距离进行限定。节点移动能耗约束表示为:

(13)

2 基于改进的多目标粒子群节点安全部署优化求解

多目标优化问题中的多个目标不可能同时取得最优解,有时会存在冲突甚至相反的情况,与普通单目标优化问题不同,它并非是寻找一个最优解,而是寻找一个折中了这些目标的非劣解集。本文采用改进的粒子群算法求解节点多目标部署优化问题,采用精英档案策略保存更新最优解集。

2.1 粒子群优化求解模型

在本文的WSN位置优化部署中,粒子为所有N个节点在部署过程中的位置坐标。假设节点部署中粒子群种群规模为n,最大迭代次数即节点部署过程中最多移动次数为tmax,由于目标函数为f1(x)和f2(x)且x=(xS1,yS1,xS2,yS2,…,xSN,ySN),因此,每个粒子k(k=1,2,3,…,n)的维数为2N。

所有粒子的初始位置为:

lk(0)=[lkxS1,lkyS1,lkxS2,lkyS2,…,lkxSN,lkySN]0

(k=1,2,3,…,n)

(14)

每个粒子以不同的速度迭代,其中第k个粒子第t次迭代的速度,即所有节点在节点部署中坐标更新速度为:

vk(t)=[vkxS1,vkyS1,vkxS2,…,vkxSN,vkxSN]t

(15)

式中:每个粒子都能够计算目标函数值f1和f2,个体的历史最优位置称为“个体极值”,即第k个粒子节点部署节点最优位置,记作:

Pbestk(t)=[PkxS1,PkyS1,PkxS2,…,PkxSN,PkySN]t

(16)

算法种群的粒子全局最优的个体位置是通过对比粒子寻优过程中的每个粒子的个体极值来确定的,这个全局最优个体位置称为“全局极值”,即所有粒子节点部署节点最优位置。粒子群算法不断通过迭代优化地搜索并更新个体极值和全局极值,最终求得全局的最优位置。

粒子通过式(17)来更新个体极值:

vk(t+1)=ωvk(t)+e1r1[Pbsetk(t)-lk(t)]+e2r2[gbest-lk(t)]

(17)

粒子通过式(18)、式(19)来更新每个粒子的速度与位置:

(18)

lk(t+1)=lk(t)+vk(t+1)

(19)

式中:ω表示惯性权重,对算法中粒子对当前速度的继承程度起到了决定性作用,e1、e2表示学习因子,决定了粒子飞向个体极值和全局极值位置速度的快慢,r1、r2是[0,1]区间内的随机数,能够增强粒子位置的多样性。

2.2 改进粒子群优化策略

①惯性权重自适应调整

在粒子群算法中,由粒子的速度更新式(18)可知,惯性权重ω决定了粒子对当前速度的继承程度。如果惯性权重ω取值较小,则对当前速度继承程度较小,粒子的局部搜索能力强,但是容易陷入局部最优;若惯性权重取值较大,则对当前速度继承程度较大,粒子的全局搜索能力强,但是不利于算法局部的寻优能力。所以对于惯性权重ω的最佳的选取是前期取较大值,保证粒子有较强的全局搜索能力,后期为了能够利于粒子的精细搜索,惯性权重ω取较小值。为此,改进惯性权重ω为自适应惯性权重,如式(20)所示:

(20)

随着迭代次数t由零增大到tmax,惯性权重ω由最大值ωmax减小到最小ωmin。

②粒子更新速度调整

粒子更新速度加上虚拟力的调整后粒子速度能够及时调整,避免了陷入局部最优,既具有较好的全局搜索能力,又具有较好的局部搜索能力。

(21)

(22)

式中:式(22)虚拟力合力按文献[17]介绍的方法求解。

③精英档案Pareto最优解策略

由于WSN中的节点存储空间有限,而且改进的多目标粒子群算法每次迭代所产生的Pareto最优解不是唯一的,因此采用精英档案策略[18]保存Pareto最优解。而在迭代终止后档案中的成员即是算法的最终解集,档案内存储解的数量在一定的范围内,即当档案存储解的数量超过某个值时,剔除档案中的部分解,从而一部分解进入档案。

为了衡量解的优劣,精英档案策略引入了密集距离概念,通过删除密集距离较小的解即处在密集位置的解,以限制档案的成员数量。而且通过比例选择的方法为每个粒子选取全局最优,即Pareto最优解中存在的密集距离越大的解会有更大的概率被选为全局最优的粒子。

2.3 多目标粒子群优化求解算法流程

改进多目标粒子群算法流程如图1所示。具体算法步骤:

①初始化WSN:初始化种群规模n,最大迭代次数tmax,随机初始化所有粒子的位置和速度,粒子的历史最优位置为当前位置;

②每个粒子的目标函数值计算:f1和f2;

③粒子更新:首先按照式(20)更新惯性权重,再根据式(22)、式(19)更新粒子的速度和位置;

④约束检验:若粒子同时满足约束条件,满足则转到步骤⑤,否则,转到步骤③重新更新粒子;

⑤个体极值选择:计算粒子的适应度值,更新个体极值;

⑥精英档案求解:删除档案中重复的成员,根据密集距离降序排列档案内成员,得到较优的存档。同时,根据密集距离,采用比例选择法为每个粒子选取全局最优;

⑦最优解集判断:若迭代次数t≥tmax,则结束循环迭代,输出最优解集;否则转步骤②继续迭代。

3 仿真实验及其结果分析

为了研究基于改进的多目标粒子群节点部署优化算法的有效性,对该算法进行了仿真实验。通过对比仅仅以网络覆盖率为优化目标的节点部署和以网络覆盖率与节点的安全连通度为优化目标的多目标的节点部署的覆盖性能;对比改进的多目标粒子群节点部署算法与多目标粒子群节点部署算法的覆盖性能,验证该算法的有效性。

3.1 环境与参数设置

仿真采用MATLAB 2014a进行,仿真实验所涉及的参数如下:

①WSN参数选择

表1 WSN参数的选择

②改进多目标粒子群算法参数选择

表2 改进多目标粒子群算法参数的选择

3.2 结果与分析

仿真的目的是比较仅考虑网络覆盖率的改进的粒子群算法单目标覆盖优化和考虑安全连通度以及网络覆盖率多目标粒子群算法覆盖优化以及改进的多目标粒子群算法覆盖优化的网络覆盖率和安全连接情况进行分析,此外比较了本文算法与粒子群算法的收敛性。

①网络覆盖率

无线传感器网络初始部署以及改进的单目标粒子群算法覆盖优化和考虑安全连通度以及网络覆盖率多目标粒子群算法覆盖优化以及改进的多目标粒子群算法覆盖优化的网络覆盖率的仿真结果如图2,圆表示节点的通信半径。

由仿真结果图2,可知与节点的初始部署相比,在算法迭代运行200次以后,节点分布更加均匀,网络覆盖率都有显著地提高,网络覆盖质量有了很大的提高并且网络覆盖率都是随着算法迭代次数的增加而增大。初始部署时,节点的覆盖率为72.64%,在算法运行200次以后,仅考虑网络覆盖率的单目标覆盖优化算法能够提高网络覆盖率到98.53%,而考虑安全连通度以及网络覆盖率的粒子群多目标优化算法和改进的粒子群多目标优化算法能够提高网络覆盖率分别到95.94和97.69%。

②节点的安全连通度

假设在无线传感器网络初始部署时,每一对邻居节点都会存在共享密钥,能够建立安全的通信连接。在应用优化算法提高节点的网络覆盖率时,可能会破坏这些已经存在共享密钥的安全连接,导致节点的安全连通率降低。初始部署以及改进的单目标粒子群优化算法、多目标粒子群优化算法和改进多目标粒子群优化算法在迭代200次以后存在共享密钥节点的安全连接的仿真结果如图3,图中的连线表示节点之间存在共享密钥的安全连接。

仿真结果图3所示,算法运行200次以后安全连接的个数都会减少,安全连通度都会降低。具体存在共享密钥节点的安全连接个数以及安全连通度

图2 网络覆盖情况比较

图3 安全连接比较图

如表3所示,节点初始部署时,节点间有共享密钥的安全连接的个数为262个,算法运行200次以后,仅仅以网络覆盖率为优化目标的改进的单目标粒子群算法存在183个安全连接,安全连通度为0.0183,并且在多目标优化算法中,粒子群算法与改进的粒子群算法存在安全连接的个数分别为229、243个,安全连通度分别为0.022 9和0.024 3。可见,单目标优化算法虽然能够提高网络覆盖率,但是对节点之间的安全连接破坏严重,改进多目标粒子群优化算法比多目标粒子群算法在运行200次以后有更高的网络覆盖率以及安全连通度。

表3 存在共享密钥节点的安全连接的情况

(3)算法的收敛性

通过对比算法的收敛速度可以反映出算法的运行效率,由仿真结果图4得知,本文的改进的粒子群算法比传统的粒子群算法在迭代次数相同时,会有更高的节点网络覆盖率,同时,会更快地达到最大的节点网络覆盖率。

图4 收敛过程比较

4 小结

本文设计了一种基于改进的多目标粒子群节点安全部署优化方案,通过设置节点的安全连通度和网络覆盖率两个目标函数,寻找满足节点全连通约束条件和节点移动能耗约束条件的最优解集,解决无线传感器网络节点安全部署的问题。采用并通过自适应的调整惯性权重以及精英档案策略改进多目标粒子群优化算法对节点安全部署问题求解,与粒子群优化算法相比能达到更高的网络覆盖率和节点安全连通度。