基于DPSO的智能WSN分簇路由算法*

范兴刚，侯佳斌，介 靖，王万良，王 翊

(浙江工业大学计算机科学与技术学院杭州310023)

无线传感器网络WSN(Wireless Sensor Network)是21世纪新兴的信息技术之一，并且被美国商业周刊列为21世纪改变世界的十大技术之一。WSN是由许多廉价的具有信息采集功能的传感器节点组成的网络，用来感知和采集各种信息，并将采集到的信息传输给基站BS(Base Station)对信息做进一步处理。传感器节点由电池提供能量，因此能量非常有限，而且每个节点的计算存储能力也很弱［1］。

由于WSN能量有限，设计能量有效的WSN路由协议显得犹为重要。目前WSN路由协议分为平面路由协议和分层路由协议两大类。LEACH协议是一种有代表性的低功耗分层路由协议，LEACH相比其他平面路由协议生命周期提高15%以上［2］。然而LEACH依照概率随机选择簇头的机制有很大的随机性不保证产生均匀的簇结构，不均匀的簇结构会大大缩短WSN的生命周期。而且LEACH中簇首和BS直接通信的机制也会消耗大量的能量。

PSO是一种群智能算法，由Kennedy和Eberhart首先提出［3］。PSO已经被证明是一种解决工程领域NP难问题的有效的解决方法［4－6］。为解决LEACH协议分簇不均匀的问题，本文把基本粒子群优化(PSO)算法改造成适合分簇问题的DPSO。并且直接由基站运行改造后的DPSO计算出最佳簇首的位置。在计算过程中，本文使用PSO惯性权重调整和变异策略来避免PSO的容易陷入局部最优的现象并且通过针对本问题的启发算法来帮助计算最佳簇首的位置。计算出最佳簇首位置后，本文根据能量传输代价为权值计算每个簇首经由其他簇首到基站的最短路径。另外本文提出让簇首感应自己的剩余能量，当能量小于一定阈值时，算法会选择当前簇内节点剩余能量最多的簇内节点当选新的簇首，从而避免LEACH中隔一定时间全部重新选择簇首带来的能量消耗。

最后本文使用MATLAB对本文提出的算法进行仿真验证。实验比较了DPSO—CR和LEACH的分簇效果，还比较了传输数据所消耗的能量情况。实验结果表明无论从分簇的均匀性还是网络生命周期来看，DPSO—CR相对LEACH协议都有大幅提高。

1 LEACH协议及其改进

1．1 LEACH协议描述和分析

下面简要描述LEACH协议的原理并给出分析。

LEACH协议分为两个阶段。第一个阶段是产生簇的阶段。这个阶段中每个传感器节点产生一个0－1的随机数，如果该随机数小于一个阈值公式的值这个节点就成为簇首。这个阈值公式表达式如下:

其中n表示某个传感器节点的编号，N是传感器节点的个数，K是期望产生的簇头个数，r是选举簇首的轮数，Gr是最近的N/K轮中还没当选过簇首的节点集合。

节点当选簇首后会广播其成为簇首的消息，其余普通节点选择收到信息的信号强度也就是距离自己最近的簇首加入。普通节点发送给簇首加入它的消息，簇就建立了。

第二个阶段是稳定的数据传输阶段，普通节点按TDMA时间片在规定时间给簇首，簇首对数据经过一定的融合后将数据一跳传给基站。数据传输阶段进行一个时间段后(远长于第一阶段)进行下一轮簇首的选择［2］。

LEACH的随机选择簇首机制可能导致非常差的分簇效果。首先导致簇首个数不确定，可能出现簇首个数远小于期望簇首数K的情况;簇首可能分布很不均匀，比如集中某一区域，这样普通节点可能距离最近的簇首仍然非常远，这样在通信中必然耗费大量的能量，簇首分布不均匀还导致簇与簇之间能量消耗不均衡;在簇首选择的时候也没有考虑剩余能量因素，剩余能量少的节点担任簇首将导致节点能量迅速耗尽而死亡。再者簇首直接将数据一跳传输给基站也不合理，长距离的传输对节点能量的消耗是非常大的;最后LEACH协议按轮重新全局选择簇首的机制由于当选簇首的广播消息也耗费大量的能量［10，15］。

1．2 对LEACH协议的改进

针对LEACH协议存在的问题，国内外学者也提出了不少LEACH的改进策略。

M．J．Handy等人对LEACH协议簇首选择公式进行改进，考虑了剩余能量的因素，改进后的公式如下［7］:

其中P是簇首所占所有节点百分比，Ecur是现在剩余能量，Emax是初始能量，rs是该节点到目前为止还没当选簇首的轮数。通过该改进一定程度上避免了低剩余能量的节点当选簇首。但是概率性机制没有改变，仍然可能选择低剩余能量成为簇首，而且分簇不均匀这个大问题也没有解决。

王国芳等人利用Prim算法生成包括基站在内的所有簇首节点的最小生成树，实现了簇首和基站之间的多跳通信，找到了簇首间短距离通信的最优路径［8］。

梁英等人采用先使用LEACH算法进行分簇得到候补簇首，然后用粒子群算法进行优化在已经产生的簇内确定最后簇首［13］。虽然先用LEACH算法进行分簇，再在簇内用粒子群选择最优簇首的方法能在一定程度上解决簇首位置不合理的情况，但是从全局来看先用LEACH进行分簇可能已经产生不合理的簇划分，再在已经划分的簇内优化只是一种局部优化。而本文提出利用粒子群算法直接寻找全局最优的簇首位置，从而使簇结构在整个监测区域来看都是分布均匀合理的。

2 本文的协议描述

本文算法假设节点能量有限且能感知剩余能量，并且可以根据发送距离长短调整发射的功率。另外本文假设传感器节点拥有GPS定位功能能获取自己相对基站的位置信息。基站能量无限，计算最佳簇首位置和簇首到基站的多跳路径都由基站来计算。

2．1 计算最佳簇首位置

本文提出算法的第一步就是通过改造的离散粒子群算法计算最佳簇首的位置。下面详细描述。

2．1．1 粒子群算法的适应度函数

运用粒子群算法的第一步就是要确定适应度函数。本文的问题是从N个节点找出一组处于最佳位置的节点担当簇首的角色使分成的簇均匀。当一个簇内的节点能紧密地围绕着簇首节点时可以被认为是个均匀的簇。当簇内所有节点到簇首的距离总和最小且它们到簇首距离都差不多大小时(也就是簇内所有节点到簇首的距离方差最小时)可以刻画出紧密围绕的特征。因此从所有节点来看，当所有簇的簇内节点到各自簇首距离总和的平均值与所有簇的簇内节点到各自簇首的距离方差的平均值同时达到最小时，所有的簇的结构应该是均匀合理的。适应度函数定义如下:

其中Dji－jCH代表第j个簇中第i个簇内节点到簇首的距离，i从簇内第一个节点到第m个节点，j从第一个簇到第n个簇。mean是求平均值的函数，var是求方差的函数。

这里还有一点要说明，根据文献［9］，当簇首节点所占百分比为所有节点5%时，能量最有效。本文中运用了这个研究成果，簇首个数就设定为所有节点的5%，簇内节点个数都相等。

2．1．2 分簇问题的离散粒子群改造

要解决本文提出的计算最佳簇首位置的问题，必须对基本PSO进行相应的离散改造。国内外学者对解决TSP问题(Travelling Salesman Problem)的粒子群离散改造的研究成果比较多，比较著名的是Clerc提出的基于交换子的离散改造方案［11］。但分簇问题并非经典的TSP问题，本文在借鉴Clerc方法的基础上，提出了针对分簇问题的DPSO模型。

首先本文定义了针对分簇问题的粒子结构:

图1 本路由算法粒子结构示意图

如图1所示，粒子的维数n代表有n个传感器节点，其中每一维里的数字代表每个节点的编号。m代表每个簇内都有相等的m个节点，这里m应为20(1/5%=20)。CH代表簇首(Cluster Head)假设i是n维粒子的坐标，如果i对20取余结果为1，则i代表的是簇首的坐标，否则为簇内节点坐标。

标准PSO按照以下两个公式更新粒子的速度和位置:

其中xin=(xi1，xi2，…，xin)代表粒子 i的位置也就是上述粒子的结构，每个位置就是问题的一个解。vin=(vi1，vi2，…，vin)代表粒子 i的速度。pin=(pi1，…，pin)代表粒子 i的最好位置，pgn=(pg1，…，pgn)代表所有粒子的最好位置。C1是粒子个体学习因子，C2是群体学习因子，w是惯性权重因子。

根据文献［11］，本文也将粒子速度定义为vi=swap(j，k)，即代表将粒子位置坐标j的节点编号与坐标k的节点编号进行交换，一个速度可能是若干个这样的交换序列的集合。同时也更改了公式(4)和式(5)中的“+”，“—”和“* ”的定义。

(位置+速度):旧位置与速度“+”的结果为新位置。让速度中的所有交换序列依次改变旧位置的节点编号。假设旧位置为(1，4，5，3，2)，速度为((1，2)，(3，5))，则新位置为(4，1，2，3，5)。

(位置—位置):两个位置的“—”的结果为一个速度。假设p1为第一个位置，p2为第二个位置，p1－p2产生的v应满足p2+v=p1。如上p1为(4，1，2，3，5)，p2 为(1，4，5，3，2)，则“—”的结果应为((1，2)，(3，5))。

(速度+速度):两个速度的“+”的结果为新速度。即简单将两个速度的交换序列合并。设一个速度为((1，2)，(3，5))，另一个为((3，4))，新速度为((1，2)，(3，5)，(3，4))。

(因子*速度):因子与速度的“*”结果仍然为一速度，定义为速度中的每一个交换序列以因子的值为概率保留(因子都为一个小于1的实数)。

2．1．3 避免PSO的局部最优现象

粒子群算法在迭代过程中容易出现陷入局部最优的现象，本文采用线性惯性权重调整和变异策略来避免这种现象发生。

公式(4)中的w就是惯性权重，它是个重要的参数。较大的w具有较好的全局收敛能力，而较小的w则有较强的局部搜索能力。现在的惯性权重研究一般分为3类:固定惯性权重，线性惯性权重调整，非线性惯性权重调整。其中线性递减的惯性权重调整策略迭代前期具有较好的全局搜索能力，后期收敛性也较好，但缺点是收敛速度慢［12］。本文采用线性递减的惯性权重调整来避免陷入局部最优，同时结合启发算法来提高收敛速度。调整公式如下:

本文还提出使用变异的策略来避免陷入局部最优即如果在粒子群算法迭代过程中判断如果每个粒子隔一定轮数个体最优解没有发生变化，并且该粒子位置和全局最优粒子位置的相似度在一定程度以上就使该粒子位置的某些维(即粒子编号)进行交换。本文中具体的做法是如果经过总迭代次数maxiter的10%轮后，如果某个粒子隔一定轮数个体最优解没有发生变化，并且该粒子位置和全局最优粒子位置相似度在80%以上时，则在粒子位置中的每个簇中随机选择一维与当前的簇首所在的维交换即选择本簇内其他节点当簇首。当然本来就是全局最优粒子不需要变异。这种变异策略可以使粒子在迭代过程中产生一定的概率找到比当前全局最优解更好的解，避免陷入局部最优。

2．1．4 启发式算法

本文提出两种启发式算法来提高粒子群迭代计算最优簇首的效率。

(1)交换簇之间簇内成员的位置

如果在PSO迭代过程中发现某粒子位置中某个簇内节点相比自己当前的簇首更靠近另外某个簇首，那这样的簇内节点应该被交换到合适的簇中去。

(2)调整簇首位置

使用两种启发式算法的策略是每经过总迭代次数maxiter的5%轮数后全局最优解，随机选择一半粒子依次使用启发式算法(1)和算法(2)对粒子结构进行指导调整。

2．1．5 最优簇首计算的流程

整个最优簇首的计算阶段的过程如下:

(1)随机初始化粒子群中每个粒子的位置和速度。由当前粒子位置根据公式(3)计算每个粒子的适应度值，并根据最优适应度值得出全局最优粒子，个体最好粒子初始化为每个粒子的初始位置。

(2)接下来开始粒子群算法的迭代过程，更新迭代轮数。每个粒子根据公式(4)和(5)计算新的位置和速度。

(3)每个粒子根据更新的位置计算各自的适应度函数值，得出最优适应度值。如果新的个体适应度值比个体历史最优适应度值更好，更新个体最优粒子位置。如果新的最优适应度值比历史最优适应度值更好则更新最优粒子位置。

(4)判断迭代轮数，如果达到maxiter的5%则随机对一半粒子运用两种启发式算法，然后转第(5)步。否则直接转第(5)步。

(5)判断每个粒子是否连续maxiter的10%轮个体最优解未发生变化，若是则对该粒子进行变异，然后转第(6)步，否则直接转第(6)步。

(6)判断是否达到迭代最大轮数，若是则结束迭代，否则更新惯性权值然后转第(2)步继续迭代。

2．2 计算簇首与基站之间多跳路径

LEACH协议的另外一个严重的缺点就是簇首和基站之间都是单跳的，每个簇首无论距离基站多远，簇首都将收集到的数据直接发给基站。

下面先来看一下无线传感网络的传输能量模型:

在文献［8］中，王国芳等人提出建立包括所有簇首和基站在内的最小生成树来减少LEACH中簇首与基站单跳通信消耗的能量。但是最小生成树的目的是使图上各点连通且使这棵生成树的权值总和最小，而本文认为计算每个簇首到基站的最小能量代价更符合改进簇首与基站单跳传输能量消耗过大的缺点这个目标。且在文献［14］中，过文亮用理论和实验证明了以能量传输代价为权值的最段路径算法比最小生成树的方法更节省能量。文献［14］将此算法用于LEACH协议中簇内各节点到簇首的多跳路径。文献［14］主要考虑LEACH的分簇不均匀，有些簇内节点到簇首距离非常远，于是考虑在簇内采用多跳传输，但这样将增加数据传输的时延。本文由于采用了基于群智能算法对选举簇首经过改造后，簇变的很均匀，簇内节点到簇首距离相对比较小，然而仍然存在簇首距离基站过大的情况，因此本文在簇首与基站之间运用此算法建立多跳路径。

本文以下面公式作为最短路径计算时的权值:

2．3 局部簇首更新机制

和LEACH协议多次进行簇首选举不同，本文提出只由基站进行一次簇首选举出最好位置的簇首，在后面轮次中不再进行全局簇首选举，而通过节点自感知剩余能量局部更新簇首从而进一步节省能量。具体过程如下:在传输数据给簇首时，簇内节点都会捎带一个剩余能量信息。簇首会将其簇内节点当前剩余能量记录下来，同时簇首检查自己的剩余能量，当剩余能量低于初始能量的10%时，簇首选出本簇内剩余能量最多的簇内节点，让它成为新的簇首。在本次数据传输给基站时将这个新节点ID报告给基站。然后由基站来通知该簇内节点新的簇首信息以及向多跳簇首间的相关簇首(指老簇首的上跳和下跳簇首)报告新簇首信息。可以看到基于能量感应机制的局部簇首更新机制基本不需要耗费额外的能量，大部分广播新簇首相关信息耗费的能量都由基站来完成，这样相比LEACH的全局更新簇首机制可以大大节省能量。当然付出的代价是需要记录簇内节点的剩余能量信息。

2．4 路由算法的整体描述

DPSO—CR和LEACH协议一样，也分为簇首选举阶段和数据传输阶段。

在簇首选举阶段首先由所有传感器节点向基站报告位置信息，由基站根据所有节点的位置信息来运行改造的DPSO算法计算出全局最优簇首。这个过程前面已经详细说明，这里不再赘述。然后基站再根据簇首运行以能量代价为权值计算簇首到基站的多跳路径。然后基站将广播它的计算结果，包括簇首ID及位置(每个节点都有自己预先设置的ID)，以及簇首通信的上一跳和下一跳信息。每个节点收到自己的身份，簇内节点记录各自的簇首ID。簇首节点记录它的簇成员ID以及上下跳簇首ID以及位置，然后就可以进入数据传输阶段。

在数据传输阶段，也和LEACH协议一样，簇内节点将数据发送给各自的簇首，簇首收集所有簇内节点的数据后将数据经过簇首间的多跳路径传送给基站。当全部簇内节点都死亡只剩簇首节点时，簇首直接感知数据并将采集的数据传给簇首。

3 仿真实验分析

本文以MATLAB为仿真工具，对LEACH协议和DPSO—CR算法从分簇效果和生命周期两方面进行比较。

首先介绍实验的场景:100个传感器节点随机地分布在一个200 m为边长的正方形区域。基站位于正方形的正中心且能量无限。

3．1 分簇效果的比较

这里比较LEACH协议和DPSO—CR的分簇效果。LEACH协议和DPSO—CR使用的节点位置都一样。改造的DPSO的参数如下:最大迭代次数maxiter为1000轮，初始惯性权重，迭代结束的惯性权重，个体学习因子 C1=0．2，群体学习因子C2=0．2，在以后的迭代过程中惯性权重w线性递减，且始终保持C1=C2并且C1+C2+w=1。而LEACH协议中期望簇首概率P(即K/N)=0．05。

图2显示了运行LEACH协议的分簇效果。相同图形代表同个簇，某个簇当中下三角形代表簇首节点，其他围绕簇首的相同图形代表簇内节点。可以看出，虽然期望簇头个数为5个，但由于LEACH依照概率选簇头的机制导致簇头个数可能少于5个;簇内成员个数严重不均衡，簇首和簇内各节点的距离可能很大;簇首位置可能非常不合理。

图2 LEACH分簇效果(期望簇首个数为5)

图3显示同样位置的节点分布运行DPSO—CR的分簇效果，可以看出DPSO—CR的分簇效果明显要比LEACH协议好。簇首均匀地分布在整个区域，且簇内节点个数都一样，除了节点随机布撒比较稀疏的区域外簇内节点都比较紧密地围绕在簇首周围，没有出现簇首与簇内节点距离过大的情况。

图3 本文路由算法分簇效果

这里比较LEACH协议和DPSO—CR算法的适应度函数(公式3)的值，可以对两种算法的分簇效果有更直观的认识。公式3分成f1和f2，其中

表1 LEACH和DPSO—CR的适应度函数值比较

上表数据是相同分布的传感器节点连续各运行3次LEACH协议和DPSO—CR适应度函数的平均值。从表中可以看出，无论是f1的值还是f2的值，LEACH协议的值都比DPSO—CR大好几倍，总适应度函数值LEACH协议是DPSO—CR的20倍左右。这说明LEACH协议中簇首和簇内节点不但距离总和过大而且距离大小非常不均匀，这将大大缩短网络生命周期，这可以从生命周期比较中看出。

3．2 网络生命周期和能量消耗比较

这里通过模拟传感器节点周期性的数据传输来比较LEACH协议和DPSO—CR的生命周期和能量消耗情况。每个传感器节点初始能量均为0．5 J，按公式(7)和公式(8)的能量传输模型计算能量消耗，其中参数为 Eelec=50 nJ/bit，Efs=10 pJ/(bit*m2)，Emp=0．0013 pJ/(bit*m4)，d0=87 m。实验比较两个协议中从分簇到数据传输的能量消耗情况。实验中分两种控制信息包和数据包两种，控制信息包为分簇阶段信息传递的数据包，大小为100 bit，数据包为传输数据所用的数据包，大小为4 000 bit。数据传输阶段按轮进行，两个协议中都规定每轮中每个簇内节点采集一个数据包，并发送给它的簇首，簇首收集本簇内所有簇内节点的数据包，并且按照两种协议中单跳或多跳方式传给基站。

其中横轴是实验中规定的轮数，纵轴是仍然存活的节点数量。下面表2对图4中的关键数据进行了描述。

表2 LEACH和DPSO—CR的网络生命周期数据比较

图4 网络生命周期比较

从图4和表2中可以看到，LEACH协议第一个节点死亡的轮数是80轮，而DPSO—CR第一个节点死亡轮数是243轮，DPSO—CR比LEACH协议晚了两倍左右的时间。LEACH协议中最后一个节点死亡的轮数605轮，而DPSO—CR最后一个节点死亡的轮数是1008轮。网络每轮平均能耗也是个重要的指标，它反映了路由算法的能量有效性，可以看到LEACH算法每个节点每轮的能耗是DPSO—CR的1．7倍，这正是本文提出的三种节省能量机制的效果体现。

图5中显示了整个网络总能耗情况。纵轴代表网络总能量50 J(0．5 J×100)，横轴代表实验轮数。可见，从整个网络能量消耗来看，DPSO—CR与LEACH协议相比大大节省了能量。文献［13］先LEACH分簇然后通过粒子群局部优化簇首的方法在相近的实验条件下只比LEACH延长20%左右的生命周期，可见本文提出的路由算法要优于文献［13］的方法。

图5 网络总能耗比较

4 总结和展望

本文针对LEACH协议中存在的三个使能量消耗过大的机制，提出了基于离散粒子群算法的智能无线传感网络分簇路由算法DPSO—CR。该算法主要包含三种新的机制来分别改进LEACH协议中存在的三个问题。其中基于离散粒子群算法计算全局最优位置的簇首是本文的核心和主要创新点，这个机制能大大改进LEACH协议分簇不均匀的缺点。在簇首间基于能耗代价的最短路径算法也改善了LEACH协议簇首和基站单跳通信能耗过大的缺点。基于能量自感应的局部簇首更新机制通过将广播消息所耗费的能量转嫁到基站上的方法又进一步延长了网络的生命周期。

当然DPSO—CR算法是有一定代价和前提条件的。首先计算全局最优簇首需要节点的位置信息，这要求传感器节点具有GPS定位功能或者先通过无线传感网络定位算法计算出每个节点相对于基站的位置。局部簇首更新机制也需要付出一定的节点存储代价。但节能是无线传感网络的首要考虑因素，通过一定的代价来延长网络的生命周期还是很有必要的。

接下来的工作是要进一步提高全局最优簇首的精度，因为粒子群算法不保证能找到全局最优解，这还需要结合智能算法研究领域来进一步深入研究。另外可以结合其他新型智能算法来研究簇首间的多跳路径，比如蚁群算法。

［1］ 孙利民，李建中，陈渝等．无线传感器网络［M］．北京:清华大学出版社，2005．

［2］ 胡钢，谢冬梅，吴元忠．无线传感器网络路由协议LEACH的研究与改进［J］．传感技术学报．2007，20(6):1391 －1396．

［3］ Kennedy J，Eberhart R．Particle Swarm Optimiaztion［C］//Proceeding of The IEEE International Conference on Neural Networks．Piscataway，NJ:IEEE Service Center，pp 1942 －1948，1995．

［4］ Coello C A C，Pulido G T，Lechuga MS M S．Handling multiple objectives with particle swarm optimization［C］//IEEE Transactions on Evolutionary Computation，2004，8(3):256 －279．

［5］ Wachowiak，M．P．，Smolikova，R．，Zheng，Y．F．，Zurada，J．M．，and Elmaghraby A．S．:An approach to multimodal biomedical image registration utilizing particle swarm optimization［J］．IEEE Trans．Evol．Comput．，2004，8(3):289 －301．

［6］ Fukuyama，Y．，Yoshida，H．:A Particle Swarm Optimization for Reactive Power and Voltage Control in Electric Power Systems［C］//Proc．Congress on Evolutionary Computation，Seoul，Korea．Piscataway，NJ:IEEE Service Center，2001:87 －93．

［7］ Handy M J，Haase M，Timmermann D．Low Energy Adaptive Clustering Hierarchy with Deterministic Cluster-Head Selection．2002．

［8］ 王国芳，李腊元，李春林，刘会静．无线传感器网络中基于能量约束的簇首多跳算法［J］．传感技术学报，2009，22(7):997 －1001．

［9］ Wendi B Heinzelman，Anant ha P Chandrakasan，Hari Bal2 akrishnan．An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］．IEEE Transactions on Wireless Communications，2002，1(4):660 －670．

［10］张伟华，李腊元，张留敏，王选政．无线传感器网络LEACH协议能耗均衡改进［J］．传感技术学报，2008，21(11):1918 －1922．

［11］ M．Clerc，in:Discrete Particle Swarm Optimization，illustrated by the Traveling Salesman Problem New Optimization Techniques in Engineering［M］．Springer，2004:219 －239．

［12］田雨波，朱人杰，薛权祥．粒子群优化算法中惯性权重的研究进展［J］．计算机工程与应用，2008，44(23):39 －41．

［13］梁英，于海斌，曾鹏．应用PSO优化基于分簇的无线传感器网络路由协议［J］．控制与决策，2006，21(4):453 －457．

［14］过文亮．无线传感器网络节能路由协议研究［D］，上海大学硕士论文，2009．

［15］ Wairagu G．Richard，Extending Leach Routing Algorithm for Wireless Sensor Networks［D］，in Msc．Thesis，Makerere University，March，2009．