基于二进制量子行为粒子群优化的WSN自适应设计

唐肝翌,刘 涛,卢桂馥

(安徽工程大学 计算机与信息学院，安徽 芜湖 241000)

基于二进制量子行为粒子群优化的WSN自适应设计

唐肝翌,刘 涛,卢桂馥

(安徽工程大学 计算机与信息学院，安徽 芜湖 241000)

无线传感器网络(WSN)所处的物理环境，探测对象以及WSN本身都存在很多不确定的因素，这要求WSN能够适时地调整和优化。提出一种基于簇结构的自适应WSN，采用二进制量子行为粒子群算法实现网络拓扑控制优化与网络覆盖优化，提高了全局搜索能力。算法中采用基于并行位操作的高效率算子处理二进制串。该算法融合于WSN动态结构设计，能有效延长WSN的使用寿命。

无线传感器网络; 粒子群优化; 量子; 自适应设计; 节能

无线传感器网络(Wireless Sensor Networks , WSN)综合了传感器技术、网络及无线通信技术、嵌人式计算技术和分布式信息处理技术，广泛地应用于工业、农业、军事、仓储物流、安全监控、环保监测、医疗监护、空间探索、智能家居等领域。

WSN采用低成本的传感节点，单个节点的计算能力、存储能力、电源容量均非常有限。在WSN实际应用中，有两个关键的问题亟需关注。一是网络拓扑控制。WSN中通信的能量代价非常大，传输一个比特的能量近似于计算处理一千个比特。[1]研究表明，将传感器节点组织成簇的形式可以有效地减少网络的能量消耗，延长网络的生命。另一个问题是网络的连接与覆盖。一方面，网络要保证足够数量的活跃节点以保证网络连通并覆盖整个监测区域。另一方面，为了让网络工作更长的时间，应该尽量冗余节点进入休眠状态。采用轮换“活跃”和“休眠”节点的节能覆盖方案，可以有效地提高网络生存时间。[2]在网络拓扑控制与网络覆盖的研究中，节能是其中的核心环节，WSN中节点的能耗对网络的生存时间有重大的影响，是优化的核心目标。[3]

1 WSN设计

网络设计的根本依据是应用需求。网络的自组织应该根据实际应用确定监测参数，确定WSN的硬件设计和网络部署，确定路由协议与拓扑结构，确定网络优化策略。

1.1 WSN建模

将400个传感节点等距离地部署于一个20×20的网格区域，传感器数量足以覆盖整个监控区域并存在冗余，为方便分析，网格宽度视为一个长度单位。后面的分析中采用文献[4]中提出的WSN模型。WSN在簇结构的基础上设计，传感节点可以作为簇首(Clusterhead)与基站(Sink)直接通信，也可以作为常规传感器只与簇首通信。还可以在基站控制下调整自己的发射功率，工作于不同的状态或者休眠状态。节点按不同功率有两种感知范围，分别称为High-signal Range与Low-signal Range。这样，每一个传感器有四种不同的工作方式，分别是Clusterhead(CH), High-signal Range(HSR), Low-signal Range(LSR), Inactive。在大型WSN中，可以采用比较复杂的多层簇结构，考虑到本应用的覆盖范围，只使用单层簇结构，如果要推广到多层结构，则需要设计更复杂的候选解编码。

1.2 优化参数分析

在实际应用中，为了充分利用传感节点的冗余，节点需要在“活跃”与“休眠”之间切换，传感节点的电量会不断衰减，其中CH传感器的衰减比常规传感器要快得多。随着电量的衰减，CH传感器与常规传感器、HSR传感器与LSR之间都需要切换。这种状态切换或者说网络优化应该动态适应节点电量的变化。接下来的分析中，得到了一组衡量WSN性能的指标，由此把网络优化问题转化为多目标优化问题，并进一步转化为非线性函数优化问题。衡量WSN性能的指标分为两部分，分别是连接覆盖参数与能量关联参数，这些参数值越小，WSN结构越优化。

连接覆盖参数包括下面四个参数：

(1)平均相对偏差(Mean Relative Deviation, MRD)。MRD体现的是节点均匀分布的度量。把整个监控区域划分为N个重叠的子区域，子区域的划分决定于四个因素，两个方向上的大小(长度、宽度)以及两个方向上的重叠率。

(1)

其中ρS为整个监控区域的活跃节点密度，ρSi为第i个子区域的节点密度。MRD值越小，活跃节点分布越均匀。在本应用中，MRD应该在0.15以下。

(2)空间密度差(Spatial Density Error, SDE)。SDE的定义是为了保证活跃节点的密度满足监控的最低要求。

(2)

其中ρS为整个监控区域的活跃节点密度，ρd为满足监测要求的最小密度，取值为0.2。

(3)每簇传感器差量(Sensors-per-Clusterhead Error, SCE)。SCE用于控制簇中活跃传感器数量不超过上限。簇中活跃传感器数量受限于传感器的通信与数据处理能力，这里把簇中活跃传感器的最大值设为15，nfull为活跃传感器超过上限(15)的簇的数量，ni为这些簇中活跃传感器的数量。参数SCE定义如下

(3)

(4)孤立传感器差量(Sensors-Out-of-Range Error, SORE)。这里把不能与CH传感器通信的活跃节点称为孤立节点，其中HSR传感器的覆盖范围为10，LSR的覆盖范围为5。nout为网络中孤立节点的数量，这里通过优化SORE减少孤立节点的数量。SORE定义为

(4)

能量关联参数包括下面三个参数：

(1)操作能量(Operational Energy, OE)。操作能量参数依赖于活跃节点的工作模式，由经验设定CH、HSR、LSR三种模式的操作能量消耗比为20:2:1。nch, nhs, nls为CH、HSR、LSR三种传感器的数量，则OE定义为

(5)

(2)通信能量(Communication Energy, CE)。通信能量依赖于常规传感器与CH传感器之间的距离。令c为网络中簇的数量，ni为第i个簇中活跃传感器的数量，dji为第i个簇中的第j个传感器到簇首的欧式距离。CE定义如下：

(6)

(3)电池容量惩罚(Battery Capacity Penalty, BCP)。BCP[t]表示在第t个周期对使用低电量电池的惩罚，BCP[t]定义如下：

(7)

(8)

综合以上7个参数，设计评价函数如下：

f=1/(α1·MRD+α2·SDE+α3·SCE+α4·SORE+α5·OE+α6·CE+α7·BCP)

(9)

假设以上7个参数有相同的重要性，以α5的值为标准值10，则α1，α2，α3，α4，α5，α6，α7的取值分别为102，104，2，103，10，10-2，10-3，这样使得每个相加项的值在同一个数量级。考虑到α3，α4是关乎网络正常工作至关重要的两个参数，要保证每一个簇的活动节点的数量都不超过15，也要保证网络中没有孤立节点，必须提高这两个参数的相对重要性，所以将这两个参数的值提升为α3=106，α4=105。α7是能量优化的关键参数，实验表明其合理的取值范围为0.01≤α7≤10。

2 量子行为粒子群优化

本应用采用基于簇结构的WSN设计，将簇的活动节点的数量限制到15以下，这样WSN设计的问题等价于寻找最小度限制生成树的问题，这是一个NP-hard问题。群集智能算法在这一类优化问题中已经得到了非常成功的应用。粒子群优化(Particle Swarm Optimization, PSO)过程简明，参数较少，容易实现，能快速获取较好的解，应用非常广泛。采用各种方法对经典PSO加以改进也是近年来群集智能研究领域的热点之一。[5-6]

2.1 量子行为粒子群优化算法概述

Sun等人深入研究了PSO算法的智能行为及其收敛性能，把量子力学相关概念引入到PSO中，在全局优化能力上做出了理论分析和算法改进，提出了量子行为粒子群优化算法 (Quantum-behaved Particle Swarm Optimization, QPSO)。[7]与经典PSO相比，QPSO取消了速度的概念，迭代公式更加简单，参数更少，收敛速度更快，全局优化能力更强。[7-8]

QPSO的粒子迭代公式如下[8]:

xi(t+1)=pi(t)±α·|C(t)-Xi(t)|·ln[1/ui(t)]

(10)

上式中，第i个粒子在t时刻的位置为Xi(t)，个体最优位置为pt(t)。ui(t)为[0,1]范围内均匀分布的随机数在t时刻的一次取值，α称为扩张-收缩因子，其取值为α<1.782,[8-9]为所有粒子个体最优位置的平均值，即

(11)

2.2 二进制量子行为粒子群优化算法(Binary Quantum-behaved Particle Swarm Optimization, BQPSO)实现思想

QPSO是针对连续空间优化提出来的，为了解决离散组合优化问题，需要采用二进制编码重新设计QPSO算法，文献[10-11]为此做了有益的探索。这里设计一种新的BQPSO算法，算法中主要的算子采用并行位运算，能大大提高运行效率。

异或运算有很多与加减法相通的数学性质。例如二进制异或运算可以看成无进位的加法或无借位的减法，异或运算也有与加减法类似的交换律与结合律。下面分析在二进制编码粒子迭代公式中用异或代替加减运算的合理性。

使用迭代法寻优的基本思想如下所示[12]:

θnext=θnow+η·d

(12)

其中d为搜索方向，η为搜索步长。不考虑中间过程，从当前位置θnow一步跳到最优位置θbest，即

θbest=θnow+(θbest-θnow)

(13)

上式中，如果θnow，θbest采用二进制编码，用异或替换等式右边的加减法，等式依然成立，即

θnow⊕(θbest⊕θnow) =θnow⊕(θnow⊕θbest)

=θnow⊕θnow⊕θbest

=0⊕θbest

=θbest

即：θbest=θnow⊕(θbest⊕θnow)

(14)

在上式基础上考虑迭代学习，增加学习步长R(ω)的因素[先不考虑R(ω)符号表示的含义，只要知道这是一个学习步长]，得到

θbest=θnow⊕R(ω)⊕(θbest⊕θnow)

(15)

回到QPSO的粒子迭代公式，式(10)等号右边做简单的乘法交换可以得到如下表达式：

Xi(t+1)=pi(t)±α·ln[1/ui(t)]·|C(t)-Xi(t)|

(16)

上式中，α·ln[1/ui(t)]可以看成学习步长，|C(t)-Xi(t)|可以看成搜索方向。对比式(15)、(16)的形式，设计二进制编码的QPSO迭代公式如下：

Xi(t+1)=pi(t)⊕R(ω)⊕[C(t)⊕Xi(t)]

(17)

式(17)中，有两个有待实现的关键因素，即R(ω)与C(t)。

(1)R(ω)表示一个二进制串，串中出现“1”的概率为ω。二进制数中，某一位的翻转可以通过与“1”进行“异或”得到，因此与R(ω)做异或运算意味着以ω的概率翻转某些二进制位。R(ω)是一个随机数，与R(ω)进行异或运算是一种具有量子行为的变异。R(ω)串的获取是容易的，以16位串为例，R(ω)串中有16ω位“1”。随机产生16ω个[0,15]之间的不重复的整数a0，a1, a2, …, 实际应用中ω取一个比较小的值，16ω个不重复整数的获取是快速的。则R(ω)=2a0,+2a1+2a2+…。

(2)C(t)为所有粒子个体最优位置的平均值，使用文献[11]的方法，统计所有粒子个体最优位置每一位出现0或者1的次数，出现0的次数多，C(t)对应位为0；反之则为1。

2.3 BQPSO算法设计

前面的WSN设计中，传感器有四种不同的状态：Inactive, LSR, HSR, CH, 分别编码为00, 01, 10, 11, 则20×20的网络需要800比特长度的位置编码。粒子群M大小设为100。基于BQPSO的WSN自适应设计算法如下：

step1 随机产生粒子群M，由式(9)计算每个粒子的适应度，得到初始的粒子位置Xi与粒子个体最优位置pi(显然初始条件下Xi=pi)。由粒子全局最优位置gbest构造WSN；

step2 如果WSN电力足以正常工作则转到step3(从step2到step8为外循环)；

step3 判断粒子群算法退出条件(连续3次迭代最优位置gbest未更新)，满足则退出(转到step6)，否则转到下一步(从step3到step5为内循环)；

step4 由式(17)更新M每一个粒子的位置Xi，重新计算每个粒子的适应度并更新pi，更新粒子全局最优位置gbest；

step5 回到step3；

step6 取gbest设计WSN结构；

step7 由式(8)更新WSN节点剩余电量；

step8 回到step2。

3 实验性能表现

在2.3的BQPSO算法中有两重循环，外循环用于模拟WSN的电量更新，内循环实现WSN优化。在外循环中，由式(8)更新WSN节点剩余电量，CH、HSR、LSR模式下的传感器分别减少总电量的20%、2%和1%。在后面的分析中，把一次外循环称为一个测量周期。

下面我们看一下BCP参数设置与性能表现。式(9)设定的评价函数中，BCP的权值参数α7是能量优化的关键参数，在后面的分析中，把α7称为节能因子(Energy-Conservation Factor, ECF)。实验表明，ECF有一个较大的合理取值范围。本文取ECF=0.01, ECF=0.1, ECF=10时的实验结果对比。

图1所示的是ECF分别取0.01、0.1和10时，从1到15测量周期MRD、OE、CE的优化值。图中可以看出，ECF的不同取值对上述三个参数的优化效果均产生影响，其中ECF取0.1时能较好的平衡各个参数的优化值。

图1 MRD、OE、CE的优化值

图2所示的是ECF分别取0.01、0.1和10时，从1到15测量周期电量处于50%、40%、30%及20%以下的传感器数量。从图2可以看出传感器的使用是比较均衡的，当ECF取0.01时，经15个测量周期，只有4个传感器电量小于20%(传感器总数为400)，WSN的工作时间能明显延长。从图2也可以看出不同取值对节能效果有明显的影响。当ECF取0.1时，WSN的性能表现与节能效果能达到较好的平衡。

图2 处于不同电量下限的传感器数量

表1显示了从1到15测量周期传感器处于不同模式的平均周期与标准差。从表1可以看出，传感器作为高能耗的CH平均只占大约1.6个测量周期，而Inactive与低能量消耗的LSR模式则大约为4.9个测量周期。可以看出算法在尽量减少传感器作为簇传感器的时间，而尽可能地处于Inactive与LSR状态。较小的标准差则说明节点的能量消耗比较均匀。

表1 传感器处于不同模式的平均周期与标准差

结语

在实际应用中，由于成本约束，无线传感器的电池电量非常有限且无法补充，所以任何WSN技术和协议的研究都要以节能为前提。本文设计了一种簇结构的WSN自适应网络，在网络设计中集成网络拓扑控制优化与网络覆盖优化，以实现一个高效节能的自组织WSN。为实现这一目标，将BQPSO优化算法集成于WSN动态结构设计中。

优化算法在运行过程中，动态控制传感节点在不同阶段分别处于CH、HSR、LSR、Inactive四种不同模式，实验结果表明，算法能在保证网络正常工作的情况下将较多节点处于LSR与Inactive状态，并使得整个网络的各个节点能量消耗比较均匀，由此延长整个WSN的使用寿命。

[1]Raghunathan V, Schuraers C, Sung Park, Srivastava M B. Energy-aware wireless microsensor networks [J]. IEEE Signal Processing Magazine, 2002,19(2):40-50.

[2]Cardei M, Du D Z. Improving wireless sensor network lifetime through power aware organization. Wireless Networks, 2005,11(3):333-340.

[3]Giuseppe A, Marco C, Mario D F, Andrea P. Energy conservation in wireless sensor networks: a survey [J]. Ad Hoc Networks, 2009, 7(3): 537-568.

[4]Konstantinos P, Ferentinos, Theodore A, TsiLiGiridis. Adaptive design optimization of wireless sensor networks using genetic algorithms [J]. Computer Networks, 2007, 51(4): 1031-1051.

[5]Samrat L S, Layak A, Siba K U. Integrated learning particle swarm optimizer for global optimization [J]. Applied Soft Computing, 2011, 11(1): 574-584.

[6]Leu M S, Yeh M F. Grey particle swarm optimization [J]. Applied Soft Computing, 2012, 12(9): 2985-2996.

[7]Sun J, Feng B, Xu W B. Particle swarm optimization with particles having quantum behavior [C] / / Proceeding of IEEE 2004 Congress on Evolutionary Computation. Piscataway: IEEE, 2004: 325-331.

[8] 孙俊. 量子行为粒子群优化算法研究[D]. 江苏: 江南大学,2009.

[9] 陈伟, 周頔, 孙俊, 须文波. 一种采用完全学习策略的量子行为粒子群优化算法[J].控制与决策，2012, 27(5):719-723.

[10]陈伟, 傅毅, 孙俊, 须文波. 一种改进的二进制编码量子行为粒子群优化聚类算法[J].控制与决策. 2011, 26(10):1463-1468.

[11]奚茂龙, 孙俊, 耿汝年. 基于二进制编码QPSO算法的移动机器人路径规划[J].系统仿真学报,2009,21(17):5516-5519.

[12]Jang J S R, Sun C T, Mizutani E. Neuro-fuzzy and soft computing: a computational approach to learning and Machine Intelligence [M].Prentice Hall,1997.

[13]Keskin, Muhammed Emre. A column generation heuristic for optimal wireless sensor network design with mobile sinks. European Journal of Operational Research. 2017, 260(1):291-304.

[14]Mitici M, de Graaf M, Boucherie R J. Data retrieval time for energy-harvesting wireless sensor networks[J].Ad Hoc Networks, 2016,17(1):32-40.

Class No.:TP393 Document Mark：A

(责任编辑：宋瑞斌)

Design of Wireless Sensor Networks Based on Binary Quantum-behaved Particle Swarm Optimization

Tang Ganyi，Liu Tao，Lu Guifu

(School of Computer and Information, Anhui Polytechnic University, Wuhu, Anhui 241000，China)

There are many uncertain factors in physical environment, detecting targets and wireless sensor networks themselves. Wireless sensor networks application required duly adjusting and optimizing. It presents an adaptive cluster structure, and uses binary quantum-behaved particle swarm optimization for network topology controlling and network coverage optimization. Efficient binary series processing operators are designed based on parallel bit operation. This method prolongs network service life effectively.

wireless sensor networks; particle swarm optimization; quantum; adaptive design; energy conservation

唐肝翌，硕士，讲师，安徽工程大学。研究方向：计算机网络与信息安全、模式识别与机器学习. 刘涛，硕士，教授，安徽工程大学。研究方向：计算机网络与信息安全、软件工程。 卢桂馥，博士，教授，安徽工程大学。研究方向：机器视觉、模式识别。

国家自然科学基金资助项目(No. 61300170, 61572033)；安徽省高校自然科学研究重大项目(No. KJ2015ZD08)；安徽省高等教育提升计划项目(No. TSKJ2015B14)；安徽工程大学2016年校级本科教学质量提升计划项目(No. 2016jyxm27)。

1672-6758(2017)07-0048-6

TP393

A