基于PSO算法的无线传感器网络组网方法

宫　华，卢海龙，袁　田

(沈阳理工大学 理学院，沈阳 110159)



基于PSO算法的无线传感器网络组网方法

宫华，卢海龙，袁田

(沈阳理工大学 理学院，沈阳 110159)

针对无线传感器网络中各节点能量有限的特点，设计了一种基于PSO算法的分簇组网方法。目标函数为最小化节点数据传输能耗、平衡簇头节点的负载、协调成员节点的通信能耗和网络的最优通信结构。算法由基站发起，广播至网络中的每个节点，利用PSO算法设计了两阶段组网算法，将目标网络划分为若干簇，形成高效的数据传输网络。仿真结果证明了算法能够有效延长网络的生存期和提高通信效率。

无线传感器网络；分簇；PSO算法；负载平衡

无线传感器网络(WSN)由大量体积微小的低功耗传感器节点组成，随机或者由人工部署在目标区域，具有能量资源和计算存储资源受限的特点。因此在无线传感器网络中设计基于能量高效的分簇算法是一个关键的研究问题。

基于群智能优化的分簇或路由算法，Iyengar等[1]探讨了基于遗传算法和基于蚁群算法的各种版本的衍生算法。Ducatelle等[2]对蚁群优化算法在有线网络和MANET中的可靠性和服务质量路由进行了大量研究。Kuila等[3]从延长无线传感器网络生存期的角度出发，提出基于负载平衡的分簇和路由选择模型，并设计了基于粒子群优化算法的分簇算法。Guo等[4]针对无线传感器网络中最小能耗的分配问题提出JOPRA问题，设计出一种改进的自适应粒子群算法，将更多的网络资源分配给连通条件更好的链路。Hamid等[5]通过多目标粒子群优化算法提出一种多目标方案优化分簇网络中的簇头数，降低了网络能耗速率，以延长网络生存期。

可以看出，现有研究在设计组网算法过程中并未充分考虑各节点的能耗均衡和数据传输效率，与其它智能优化算法相比，粒子群算法具有更快的收敛速度和简便的实现过程。因此，本文根据WSN内部传感器节点硬件资源和能量供应受限的特点，在充分考虑负载均衡、最优能耗和数据传输效率的基础上建立关于分簇方案的非线性规划模型，并设计PSO算法求解该问题。

1　系统模型

1.1能量模型

无线通信的能耗模型是基于Heinzelman[6]研究成果。在模型中由通信距离决定使用自由空间或是多径衰落信道。首先根据阈值d0，当收发距离小于给定阈值d0时，则基于自由空间建立能耗模型，否则采用多径衰落模型。令Eelec表示节点中收发器发送一位数据的能耗，εfs、εmp分别表示处于自由空间或者多径衰落信道的放大器发送一位数据的能耗。当距离为d时发送l-bit数据能耗为

(1)

接收l-bit能耗为

ER(l)=lEelec

(2)

式中，变量Eelec取决于多种因素比如数字编码方案、调制、滤波和信号传播发送;而放大器的能耗(εfs、εmp)只取决于发送距离和误比特率。

1.2网络模型

Dietrich等[7]介绍了网络生存期的多种定义，本文选择N-of-N运行期为网络生存期定义，即从部署完成到第一个簇头消亡这一时期为网络生存期。网络中每个成员节点只隶属于一个簇头。数据的收集分成若干轮次。每一轮次中，成员节点负责收集目标区域的监测数据，并发送给对应的簇头。簇头节点对接收到的数据进行融合处理，把处理后的目标数据经过多跳传输发送给其它簇头，多跳通信的中继任务由附近的簇头承担。两个节点间存在无线通信链路的条件是它们都在对方通信范围内。

网络部署分为三阶段：引导加载阶段，分簇形成阶段，簇头选择阶段。由于各节点中都配置GPS模块，第一阶段中节点根据GPS获取各自坐标值，节点在网络内通过CSMA/CAMAC层协议广播其坐标。因此，任一节点可以获得通信范围内其它节点的位置信息，并通过多跳通信发送至基站。基站根据收集到数据执行分簇算法，将网络划分成若干簇并选择簇头，为每个簇头分配一个ID，此ID同时也表示对应簇的编号。经过以上操作，所有节点均被安排给一个簇头，每个簇头记录所辖成员信息。运行过程中，各簇头提供一个TDMA时间表给本簇成员节点以完成簇内通信。

2　组网模型

分簇的目标是最大化网络生存期和提高网络通信效率，在组网过程中不仅需考虑网络的能量有效性和数据传输效率，也需考虑各节点能耗均衡。能耗均衡有两层含义，首先是簇头的负载平衡问题，当簇头剩余能量相近时其所在分簇规模不能相差太大，避免出现某些簇头管理过多的成员，而其余簇头管理的成员过少，造成前者因能耗速率较大而很快消亡。其次最小化簇头与本簇成员节点的距离方差，使所属成员在与簇头通信时的能耗不会出现较大的差异，有利于延长网络的整体寿命。

2.1参数定义

S={s1,s2,s3,…,sN}：传感器节点集合，N表示网络内节点总数；

ξ={g1,g2,g3,…,gM}：簇头节点集合，M表示网络中簇头数目，等于分簇数；

dmax：传感器节点最大通信距离；

dis(si,sj)：节点间距离；

NextHop(gi)：某簇头通信范围内的其它簇头集合；

ComCH(si)={gj|dis(si,gj)≤dmax∩gj∈ξ}：成员节点si通信范围内的簇头集合；

Nmax、Nmin：每簇中成员数的上限和下限；

Nj：ID为j(1≤j≤M)的簇中成员节点数；

2.2网络生存期

根据网络生存期的定义，延长网络的生存期可以通过延长具有最短寿命的簇头节点生存期实现，即降低每一通信周期中剩余能量少的簇头的能耗速率。簇头能耗包括接收成员节点的感知数据，数据融合以及簇间通信。每个周期内管理ni个成员节点的簇头gi的能耗为

ECLUSTER(gi)=ni×ER+ni×EDA+ET(gi,NextHop(gi))

(3)

式中ER、EDA、ET分别是数据接收、数据融合、簇间通信能耗。

在一个多跳网络中，除了存在簇内信息传输，有时簇头还需转发来自于其它簇的分组。在计算簇头作为中继节点能耗前，首先计算gi收到的来自于其它簇的分组总数，

其他最终得出每个周期gi做为中继节点需转发NIN(gi)个分组，中继能耗为

EFORWARD(gi)=NIN(gi)×ER+NIN(gi)×ET(gi,NextHop(gi))

(5)

因此，簇头gi每个周期能耗可表示为

EG(gi)=EFORWARD(gi)+ECLISTER(gi)

=ni×ER+ni×EDA+ET(gi,NextHop(gi))+

NIN(gi)×ER+NIN(gi)×ET(gi,NextHop(gi))

(6)

令Eresidual(gi)表示gi的剩余能量，则gi的生存期可表示为

(7)

令L表示寿命最短的簇头生存期，即L=min{L(j)|∀i,1≤j≤M}，所以最大化网络生存期可表示为

maxL=min{L(i)|∀i,1≤i≤M}

(8)

2.3网络通信效率

网络运行过程中，簇头不但对簇内数据进行处理融合，而且负责簇间通信。本文研究的WSN网络属于Adhoc网络，即网络中所有节点无论簇头还是成员节点的功能和硬件配置都是相同的，在实际运行中容易发生某个簇头管理的成员节点过多而引起数据拥塞和通信延时的增加。因此为提高网络的通信效率并且实现簇头的负载平衡，对每个簇的分簇规模进行优化。通过Var_load计算各簇的规模差异。

(9)

最大化网络通信效率表示为

(10)

2.4簇内平均距离

在分簇过程中可能出现为了节省簇头能耗，某些成员节点被强制安排给较远处的其它簇头的情况。这样的成员节点的通信能耗就会较大，因此在目标函数中也要考虑优化成员节点能耗，即最小化成员节点和其簇头的平均距离，表示为

(11)

AvegDist是成员节点和其所属簇头的平均距离。

结合方程(8)、(10)、(11)，得目标函数为

minObj=AvegDist×Var_load/L

(12)

s.t

(13)

(14)

Nmin≤Nj≤Nmax, j∈(0,M]

(15)

式(13)表示任意成员节点只能分配给一个簇头。式(14)表示任意成员节点只能安排给位于其通信范围内的簇头。式(15)规定每个簇的成簇规模。

3　基于粒子群算法的两阶段分簇组网算法

3.1初始组网方案

首先根据各网络节点的位置坐标，将整个网络区域直接按照面积划分为M簇。网络划分成若干簇后，需要确定每个簇的簇头。每个成员与对应簇头通信时，根据能耗与传输距离成正比，为保证成员节点能耗均衡。簇头与成员节点距离方差应最小。

(17)

式中：AvegDistj表示簇j中各成员与簇头平均距离；Variancej表对应方差；(xj,yj)表示簇头坐标；(xi,yi)表成员节点坐标。遍历完本簇所有节点后选择方差取值最小时对应的节点作为簇头。

3.2基于PSO算法的组网优化

PSO算法由一个预定义规模为(Np)的粒子群组成，每个粒子代表一个求解多维优化问题的方案。所有粒子的维度都为D。每个粒子Pi(1≤ i≤ Np)有两个参数，位置参数Xid(1≤ d≤ D)和速度参数Vid。种群中第i个粒子Pi用向量表示为

Pi=[Xi,1,Xi,2,Xi,3,...,Xi,D]

(18)

通过目标函数评估每个粒子对应的方案。粒子Pi根据个体最优值(Pbesti)和种群全局最优值(Gbest)更新自身的位置和速度。每次迭代中，粒子Pi通过以下方程更新位置参数和速度参数：

Vi,d(t)=w×Vi,d(t-1)+c1×r1×(Pbesti,d-Xi,d(t-1)+c2×r2×(Pbesti,d-Xi,d-Xi,d(t-1))

(19)

Xi,d(t)=Xi,d(t-1)+Vi,d(t)

(20)

式中：w为惯性权重；c1、c2为加速因子；r1、r2为[0,1]间的随机数。粒子的更新过程被迭代多次，直到最终结果能够接受或者达到预定的迭代次数。

3.2.1粒子初始化

粒子的维度等于网络中传感器节点总数N。种群的第i个粒子表示为Pi=[Yi,1,Yi,2,Yi,3,…,Yi,D]。粒子中的每维元素Yi,d(1≤ i≤ Np,1≤d≤N)表示传感器节点sd被分配在第gk簇。初始化粒子时，首先结合3.1中所述的簇头选择方案并根据坐标将所有节点分成M簇，为各簇头分配ID，取(0,1]范围内的随机数初始化粒子的每一维元素。粒子Pi的元素Yi,d=Rand(0,1],l≤d≤N映射了成员节点sd从属于哪个簇头(假设为gk)。若sd被选做簇头，则Yi,d等于0。映射方法为

gk=Index(ComCH(sd),n)

(21)

式中Index是索引函数，表示集合ComCH(sd)中的第n个元素被选中赋给gk。

n=Ceiling(Yi,d×|ComCH(sd)|)

(22)

3.2.2速度位置更新

通过方程(19)、(20)实现粒子位置和速度更新。注意到方程在迭代过程中可能会出现粒子中某些元素的取值非正或大于1。本文规定粒子的每个维度的元素取值范围必须在(0,1]区间内。因此，算法做出如下调整：

(1) 如果新的位置取值为负数或者0，则使用一个趋近于0的正数代替；

(2) 如果新的位置取值大于1，则用1代替。

每次迭代完成后，通过适应度函数Fitness评价粒子Pi，并根据最终结果决定是否更新个体最优值Pbesti和全局最优值Gbest。速度和位置被迭代更新直到满足停止准则。本文的停止准则是一个预先定义的迭代次数。

4　仿真结果与分析

选定90m×50m的区域随机抛撒无线传感器节点，固定抛撒节点数为60，各节点坐标随机生成。(εfs、εmp)的取值分别为10pJ/bit/m2和50nJ/bit。粒子群算法参数c1、c2取值为1.5，迭代次数为200，更新速度的最大值Vmax和最小值Vmin分别为0.1、-0.1。表1列出试验中的网络参数。

表1　网络参数

图1与图2为抛撒节点数60，通信半径30情况下网络初始化后与经过粒子群算法执行200次迭代运算的组网效果。可以看出初始化后的组网结构图，虽然簇头节点互不相邻，并且在目标区域分布较为均匀。但是各簇的成簇规模差异较大，衡量负载平衡的参数Var_load此处取值为5，每个通信轮次中成簇规模最大的簇头能耗为1.7mJ。经过优化后的网络中，参数Var_load取值为1，每个通信轮次中能耗最大的簇头为1.2mJ，最小为0.9mJ。显然经过粒子群算法优化后的组网方案，不仅保证了簇头在网络中均匀分布，而且各簇的成簇规模相近，较好地实现了簇头的负载均衡。

图1　初始化后的网络结构图

图2　优化后的网络结构图

图3表示在抛撒节点数60，通信半径30的情况下，算法迭代200次的收敛图。可以看出算法迭代150次后即趋于收敛。

图3　算法迭代200次的收敛图

为研究算法的有效性，在不同种群规模下对运算结果进行比较。

表2　不同种群规模以及对应的目标函数值

通过以上数据可以看出，根据粒子群优化算法的搜索结果所构造的无线传感器网络具有较好的能量有效性与通信效率。

5　结论

针对无线传感器网络中各节点具有严格的能量供应约束的特征，提出了一种基于PSO算法的能量有效分簇组网算法，根据节点能耗、负载平衡和最高通信效率等指标来选取簇头，从而能够显著减少网络中数据传输能耗，并提高通信效率，为网络路由提供了合理的理论基础。仿真结果从分簇算法的组网结果、算法的参数选择、不同的网络规模等方面说明了算法的有效性。

[1]S S Iyengar,H C Wu,N Balakrishnan,et al.Biologically inspired cooperative routing for wireless mobile sensor networks[J]. IEEE Systems Journal,2007,1(1):29-37.

[2]F Ducatelle,G A Di Caro,L Gambardella.Principles and applications of swarm intelligence for adaptive routing in telecommunications networks[J].Swarm Intelligence,2010,4(3):173-198.

[3]P Kuila,P K Jana.Energy efficient clustering and routing algorithms for wireless sensor networks:Particle swarm optimization approach[J].Engineering Applications of Artificial Intelligence,2014,33(8):127-140.

[4]S T Guo,C Y Dang,X F Liao.Joint opportunistic power and rate allocation for wireless ad hoc networks:An adaptive particle swarm optimization approach[J].Journal of Network and Computer Applications,2011,34(4):1353-1365.

[5]H Ali,W Shahzad,F A Khan.Energy-efficient clustering in mobile ad-hoc networks using multi-objective particle swarm optimization[J].Applied Soft Computing,2012,12(7):1913-1928.

[6]W B Heinzelman.Application specific protocol architecture for wireless microsensor networks[J].IEEE Transaction on Wireless Communications,2002,1(4):660-670.

[7]I Dietrich,F Dressler.On the Lifetime of Wireless Sensor Networks[J].ACM Transactions on Sensor Networks,2009,5(1):976-978.

(责任编辑：马金发)

Networking Method Based on PSO Algorithm in Wireless Sensor Network

GONG Hua,LU Hailong,YUAN Tian

(Shenyang Ligong University,Shenyang 110159,China)

A clustering network algorithm is proposed based on PSO algorithm for the feature with the limited power sources of wireless sensor network. The objective is to minimize transmission energy consumption,balance load among the cluster heads,tradeoff between transmission energy of the member nodes and the effective communication structure. The clustering algorithm begins with the base station,and broadcasts messages in the network. A two-stage network algorithm based on PSO algorithm can divide objective network into clusters in order to find a highly efficient communication network. The computational results show that the algorithm proposed in this paper can prolong the life time of the network and improve the efficiency of communication.

wireless sensor networks；clustering；PSO algorithm；load balancing

2015-07-14

国家自然科学基金资助项目(71101097)；辽宁省“百千万人才工程”培养资助项目(2014921043)

宫华(1976—)女，教授，博士，研究方向：组合优化、生产调度。

O224

A