基于改进型粒子群的无线传感器网络分簇
路由算法#
夏季文，马福昌**
基金项目：教育部科学技术研究重点项目(210270)；教育部博士点新教师基金(20091402120006)
作者简介：夏季文，(1987-)，女，太原理工大学在读硕士，主要研究方向为无线传感器网络。
通信联系人：马福昌，(1953-)，男，博士，教授，博士生导师。主要研究方向为新型传感器，自动化仪表，
电路与系统等. E-mail: mfc526@126.com
5 （太原理工大学测控技术研究所，太原 030024）
摘要：为了有效延长WSN 网络的生存时间，需要设计能量有效的簇头选择和成簇机制，以适
应无线传感器网络的特点。提出一种改进型粒子群(非线性自适应PSO)的分簇路由算法。在
适应度函数中，根据节点的能量分布定义了基于节点剩余能量的簇内加权平均距离，并同时
考虑了网络节点和簇头节点的平均剩余能量比以及网络节点的平均传输能量损耗三个因素。
10 在成簇过程中融入了新的竞争机制F，考虑了簇头的剩余能量和距离基站的远近等因素，并
对其进行仿真。仿真结果表明，该优化算法使得簇头均匀分布，均衡了网络能耗，是解决
WSN 能耗最小化的一种有效方法。
关键词：无线传感器网络；非线性自适应粒子群；分簇算法；簇内加权平均距离；单-多跳
 35 0 引言
无线传感器网络(Wireless Sensor Network，WSN)作为现阶段物联网发展的核心，高度
融合了传感器技术、通信技术以及计算机技术。由于无线传感器网络节点能量、存储、计算
和通信能力有限，能源的高效使用就成为无线传感器网络路由设计的首要目标。
大规模的无线传感器网络一般都采用分簇路由协议[1]来减少能量消耗。分簇路由协议将
40 网络分成若干簇，选择簇头节点负责簇内数据的收集、融合并传送至基站。其中，低功耗自
适应分簇多层协议(Low Energy Adaptive Clustering Hierarchy, LEACH)是大部分研究的基础。
LEACH 的基本思想是以循环的方式随机选择簇头，将整个网络的能量负载平均分配到每个
 传感器节点中，从而降低网络能耗，提高网络生存时间。但难以保证每轮选举簇头在网络中
均匀分布，易造成节点过早死亡、部分检测区域过早失效等问题。改进的LEACH-C[2]很好
45 地利用了汇聚节点关于全网能量的判断，对簇进行预决策，但还是没有解决建立阶段的优化
问题。Latiff 等人[3]提出运用PSO 算法优化分簇的过程(PSO-C)，避免簇内节点过早出现盲
节点现象。但由于是在LEACH 算法预分簇的基础上运用PSO 优化簇头选择，因此难以避
免LEACH 算法的局限性，而且优化过程需要消耗额外的能量，没有考虑簇内节点的能量，
使得簇头的选择不能有效的保护簇内低能量的节点，同时也因粒子群本算法本身存在的在后
50 期却易于陷入局部最优的缺点而受到局限，因此寻求有效的启发式算法来解决WSN 分簇和
路由问题非常重要。为此本文提出了基于非线性自适应粒子群的无线传感器网络分簇路由算
法(NAPSO—CA)。
1 粒子群优化算法(PSO)
粒子群优化(Particle Swarm Optimization，PSO)算法是由Kennedy 和Eberhart 等人于1995
55 年提出的一种基于群体的随机优化过程[4]。在PSO 中，每个优化问题的解都是搜索空间中
的一只鸟,称为“粒子”，所有的粒子都有一个由被优化的函数决定的适应值，每个粒子还
有一个速度决定他们飞翔的方向和距离。然后粒子们追随当前的最优粒子在解空间中搜索。
假设在D 维搜索空间中，有m 个粒子组成一群体，第i 个粒子经历过的最好位置（最
好适应度）记为向量1 2 ( , ,... ) i i i id P= p p p ，每个粒子的飞行速度为向量1 2 ( , ,... ) i i i id V= v v v ，
i= 1, 2,...m。在整个群体中，所有粒子经历过的最好位置为向量1 2 ( , ,... ) g g g gd 60 P= p p p ，每
一代粒子根据下面公式更新自己的速度和位置：
1 1 2 2 ( 1) () ( ()) ( ()) id id id id gd id V t+ =wV t +cr P −X t +cr P −X t (1)
( 1) () ( 1) id id id X t+ =X t +V t+ (2)
其中，W 是惯性权重系数； 1 c 、2 c 为学习因子； 1 r 、2 r 是[0,1] 之间的随机数。
65 2 非线性自适应权重粒子群算法(Nonlinear Adaptive weighting
Particle Swarm Optimization)
传统的线性迭代权重，不能保证当权重不够大时，粒子能跳出局部最优。为了平衡PSO
算法的全局搜索能力和局部改良能力，本文采用了惯性权重随着粒子的目标函数值而自动改
变的非线性自适应权重的粒子群算法NAPSO[5]。非线性动态权重表达式如下：
max min min
min
min
max
( )*( ) ,
( )
,
avg
avg
avg
w w w f f ff
w f f
w ff
− − ⎧ − ≤ ⎪ − =⎨⎪
⎩ ≤
70 (3)
max w 、min w 分别表示w 的最大和最小值，f 表示粒子当前的目标函数值， avg f 、min f 分
别表示当前所有粒子的平均目标值和最小目标值。
当各微粒的目标趋于一致或者趋于局部最优是，将使惯性权重增加，而各微粒的目标值
比较分散时，将使惯性权重减小，同时对于目标函数值优于平均目标值的微粒，其对应的惯
75 性权重因子较小，从而保护了该微粒，反之对于目标函数值差于平均目标值的微粒，其对应
的惯性权重因子较大，使得该微粒向较好的搜索区域靠拢。
NAPSO 算法的流程如下：
 Step1 初始化 随机初始化种群中各微粒的位置和速度；
Step2 评价每一个粒子 计算每个微粒的适应度，将当前个微粒的位置和适应值存储在
80 各微粒的Pi 中，将所有Pi 中适应值最优个体的位置和适应值存储于Pg中；
Step3 粒子的更新 根据(1)和(2)式更新粒子的速度和位移；
Step4 权重的更新 根据(3)式更新权重；
Step5 对每个微粒，将其适应值与其经历过的最好位置作比较，如果较好，则将其作为
当前的位置，比较当前所有Pi 和Pg的值，更新Pg ；
85 Step6 检验是否符合结束条件 若满足停止条件(最大迭代次数)，搜索停止，输出最优解，
否则返回Step3 继续搜索。
3 SAPSO—CA 的相关工作
3.1 无线通信能量模型和网络模型
无线能量模型根据发送节点和接收节点的距离d 分为自由空间模型和多径衰落信道模
型。定义距离阈值fs
crossover
amp
d
ε
ε
= ，该模型中elec E 表示发射电路损耗的能量。DA 90 E 为簇头
数据融合消耗能量。fs ε 、amp ε 分别为这两种模型中功率放大所需的能量。当crossover d<d 时，
适用自由空间信道模型，能耗与d 2 成正比；当crossover d>d 时，适用多径衰落信道模型，能
耗与d 4 成正比。这里的距离阈值约为87m。在距离d 上输k 比特的消息时，发送能耗的计
算公式为：
( , ) ( ) ( , ) TX TX elec TX amp E k d E k E k d − − = + =
2
4
,
,
elec fs crossover
elec amp crossover
k E k d d d
k E k d d d
ε
ε
⎧ ⋅ + ⋅ ⋅ < ⎪⎨
⋅ + ⋅ ⋅ ≥ ⎪⎩
95 (4)
接收能耗： ( ) ( ) RX RX elec elec E k E k k E − = = ⋅ (5)
3.2 算法描述
Step1 预分簇阶段。此阶段可采用各种分簇算法(如LEACH 算法)对无线传感器网络进
行簇的初步划分，选出候选簇头。基站计算全网节点的当前平均剩余能量，设定能量阈值，
100 大于或等于阈值的节点成为候选簇头，主要收集簇内邻居节点的ID、位置和剩余能量等信
息。簇头在候选簇头节点中产生。
Step2 应用SAPSO 优化并确定最优簇头阶段。由于PSO 优化WSN 簇头问题是二维的，
因此对粒子的速度和位置进行分解，对横坐标和纵坐标分别进行迭代更新，直到达到算法的
终止条件。
105 新的簇头不仅应当有较高的剩余能量，而且其周围节点的分布也应当较为合理，使得离
它越远的节点能量相应较大，而离它越近的节点能量可以适当小一些，这样就能使网络中节
点的能量消耗较为均衡。据此构造的适值函数为：
1 2 3 '( ) ( ) ( ( ) ( )) i i i i f x = f x ×αf x +βf x (6)
1、网络节点平均能量损耗1 f （簇内平均传输损耗）
110 网络节点的能量损耗包括了簇头节点数据融合能量损耗、簇头节点与基站间通信能量损
耗以及簇内节点上传检测数据能量损耗三个部分。网络节点平均能量损耗体现了网路在某轮
 中的通信代价，选择了低损耗的粒子有利于延长网络的整体寿命。
1
, 2
1 ,
( ) 1 ( ) 1( )
i j
r
amp j bs j r
i elec DA elec fs k j
j m k C j j
d C
f x k E E E d
N C C
ε
ε
∈ ∈
= ⎧⎨⎪ + + ⋅ + − + ⋅ ⎫⎪⎬
⎩⎪ ⎪⎭
Σ Σ (7)
N 为网络中节点数目，k 为每个节点每次发出的数据包比特数， j C 为簇头集合i m 中以
节点j 为簇头的簇内节点集合， j C 为簇内节点数目。j,bs 115 d 为簇首到基站的距离，若
j,bs 0 d >d，则1 r =4，否则1 r =2； k,j d 为节点k 到簇头j 的距离，若k,j d 0 > d 则2 r =4，否则2 r =2。
2、簇内加权平均距离
传统的粒子群分簇路由算法中，在均衡网络的能量消耗时，考虑的仅仅是簇头的能量因
素，并没有考虑形成簇后，簇内节点的能量分布情况。为了更加有效的均衡网络的能耗，我
120 们希望在成簇后簇头距离能量较低的节点更近一些，即图2 中簇2 的结构优于簇1 的结构。
两个簇每轮中的能量总消耗相同，但是簇1 中能量少的节点消耗的能量反而比能量多的节点
多，而簇2 中簇头靠近能量少的节点，有利于对于低能量节点的保护。
图2 两种簇的结构
125 Fig.2 the structure of two clusters
为了有效的根据簇内节点的能量分布情况做出选择，给出了簇内加权平均距离的定义：
_ _
, ,
2 _, _ ,
, ,
( ) max( )
j k j j j k j j
k k
i kj k j
k C d d j k C d d j
f x ed ed
∈ <e ∈ >e
= Σ + Σ (8)
其中， k e 、
_
j e 分别表示节点k 的剩余能量和簇j 的簇内平均能量，
_
j d 、k,j d 表示簇j
130 内的节点到簇头的平均距离和节点k 到簇头j 的距离。
考虑在面积为M 的监测区域内，均匀分布了pN 个簇，N 为节点总数， p 为簇头节点
比例。则每个簇的监测区域大小为M/pN，由于分布在簇内的节点数目较多，可以近似计
学术论文网Tag：代写论文 代写代发论文 代发论文 职称论文发表