基于差分算法的无线传感器网络路由分簇协议

李志明 唐永中

(河西学院信息技术中心 甘肃 张掖 734000)

基于差分算法的无线传感器网络路由分簇协议

李志明 唐永中

(河西学院信息技术中心 甘肃 张掖 734000)

针对异构无线传感器网络分簇路由协议存在节点能耗不均衡问题，提出一种基于差分进化算法的路由协议及基于节点能耗的分簇协议。该协议首先以最大化网络中簇头节点的最小生存周期为目标，建立函数优化模型，并采用差分进化算法对其进行优化，从而延长网络整体的生存周期；然后根据节点通信列表中的簇头数目进行分簇，将节点分配给能耗因子较低的簇头，以达到均衡网络能耗的目的，延长普通节点的生存周期。仿真结果表明，基于差分的路由分簇协议能有效均衡网络中节点的能量消耗，显著延长网络的生存周期并提高网络能量利用率。

异构无线传感器网络 路由 分簇 差分算法

0 引 言

无线传感器网络受到了国内外学者们的广泛关注，它可以被应用在环境监测、医疗等领域[1]。然而由于传感节点的能量有限，直接限制了网络的工作时间。尤其在战争、森林等复杂环境里，节点很难被访问、更换或充电。因此，对无线传感器网络来说，最大化网络的工作时间是非常关键的问题。

为降低节点通信中的网络能耗，广泛使用的一种策略是分簇[2]，即网络中的节点被组织分配到特定数量的独立区域内，每个区域选出一个负责接收、融合和转发本区间内的节点监测信息的簇头，每个节点只与一个簇头连接，簇头将融合后的信息通过单跳或多跳的方式传输给基站。如文献[3]提出LEACH策略，通过周期性的选取簇头的方式以平衡网络中节点的能耗。然而由于节点携带能量较低，充当簇头的节点会较快地耗费掉自身能量，且频繁更换簇头有需要重新设计簇头节点的路由通信链路，这会为网络带来较大的通信开销。对此，文献[4]提出了一种改进策略PEGASIS，该算法相比于LEACH虽能在一定程度上延长网络生存周期，但是它需要对网络进行动态拓扑调整，如果网络中节点数量较多，则网络延迟将会相当大，因此该算法不适合于大规模传感网络。

为进一步解决网络生存周期较低的问题，文献[5-6]采用向网络中布撒高能节点充当簇头节点，以延长网络生存周期。 这种方式相比于同构网络虽然较大程度的延长了网络寿命，但由于簇头节点能耗较大，因此网络寿命仍然面临着能耗的限制，因此采用合理的路由拓扑结构和均衡的分簇算法对网络显得尤为重要，对此文献[7]提出GLBCA算法；文献[8]提出基于GA的路由分簇算法；文献[9]提出的GAR算法。这三种算法虽然在一定程度上优化了拓扑结构延长了网络生存周期，然而都没有从节点的生存周期这一根本目标出发对网络进行优化。

基于以上分析，为降低节点在通信中的能耗、延长网络生存周期，本文结合差分算法[9]较好的优化性能，提出了基于差分的路由分簇算法。首先以最大化最小簇头节点的生存周期为目标，采用差分算法对其进行优化，以尽量延长网络中簇头节点的最短生存周期；然后根据节点的能耗，建立了能耗因子，对每个节点进行分簇时，选择能耗因子最小，也即能最好均衡普通节点和高能节点能耗的簇头。实验表明，本文算法能够有效的均衡网络能耗、延长网络生存周期。

1 能耗模型

本文采用LEACH提出的能量模型[10]。假设发送端能耗包括信号处理和功率放大两个部分，接收端能耗为信号处理和数据融合。则根据无线通信理论，两个距离为d的传感器节点之间发送和接受lbit数据时，发送端消耗的能量为:

(1)

其中，d0为判决阈值，εfsd2和εmpd4是发送每比特数据放大器的能量消耗，Eelec是每比特数据在发送电路和接收电路消耗的能量。节点接收l比特数据时的能量消耗如式(2)所示。

ER(l)=lEelec

(2)

2 基于DE的路由算法

对异构无线传感器网络，由于受能量的限制，因此必须设计合理的拓扑结构降低节点能耗以延长网络生命周期，对此本文提出了基于DE算法的路由算法以及基于簇头节点能耗的分簇算法，距离过程描述如下。

2.1 基于差分的路由算法

假设网络中的簇头个数为5，当簇头gi与簇头gj的距离满足式(3)-式(4)，则说明两个簇头可进行通信且簇头gj比gi更靠近基站，因此将gj存入gi的通信列表中。

dis(gi,gj)

(3)

dis(gj,BS)

(4)

则簇头节点的可通信列表如表1所示。

表1 簇头节点通信列表

则种群中的粒子Xi,d表示粒子i的第d个簇头在选择下一跳簇头时的概率值，假设粒子i的初始化结果为[0.54,0.36,0.11,0.36,0.37]，则通过计算可得到网络中簇头节点的连接列表，具体如表2所示。

表2 簇头选择下一跳列表

当采用差分算法对簇头节点的通信链路进行规划时，需要为算法设定目标函数，因为异构无线传感器网络首要考虑的因素是网络生存周期，而簇头节点不仅要接收转发其他簇头的信息包，还要接收转发本簇内节点的数据信息，因此簇头节点的能量消耗较大。所以簇头节点的工作时间，决定了传感网络的监测效果，对此，本文将最大化簇头节点的最短生命周期作为算法的目标函数，具体如式(5)所示。

f=Max(min{(lifetime_gi)|∀i,1≤i≤D})

(5)

其中，lifetime_gi表示簇头节点gi在不考虑接收融合簇内节点时的生存周期。则簇头节点的网络生存周期如式(6)所示。

lifetime_gi=E/(ER×NIN(gi)+(NIN(gi)+1)×ET(gi,NextHop(gi)))

(6)

其中，E表示簇头节点的总能量；NIN(gi)表示簇头gi接收到的来自其他簇头的数据包的个；(gi,NextHop(gi))表示簇头gi与它下一跳簇头的距离。

2.2 基于能量的分簇算法

由式(1)可知，普通节点与其簇头节点通信距离的不同，则在每轮通信中的能耗不同，也即具有不同的网络周期；另外，簇头节点接收和融合本簇内节点时也需增加一定的能耗，且随着簇内节点数目的增多，簇头节点的能耗压力会逐渐增大。因此，为了使普通节点和高能节点的生存周期都达到最大，本文提出基于簇头节点能耗的分簇算法，具体描述如下。

1) 根据普通节点的位置及它的通信距离得到每个普通节点可连接簇头的通信列表；

2) 以列表中含有簇头数目的多少为顺序对普通节点进行分簇，节点可连接的簇头数越少，则可选择簇头的机会就越少，因此从连接矩阵较小的普通节点开始分簇；

3) 分簇时，要兼顾普通节点和簇头节点的网络生存周期，也即兼顾普通节点和簇头节点在每轮通信中的能耗情况。当将一个节点i分配给簇头k时，一方面簇头节点增加了接收和融合的能耗，另一方面节点Si的发送距离是基于与簇头gk的距离计算的，因此对监测节点来说，其可连接簇头矩阵中必然存在一个能较好均衡节点能耗与簇头能耗的簇头节点，则将节点连接到该簇头上。具体的衡量节点和簇头能耗的能耗因子如式(7)所示：

lk=αEgk+βE(sk,gk)

(7)

其中Egk表示节点si的可连接簇头列表中第gk个簇头的总能耗；E(si,gk)表示将节点si分配给簇头gk时的传输能耗；α和β表示普通节点生存周期和簇头节点生存周期的权重因子。因为簇头节点要接收转发其它节点发来的信息，因此相比于普通节点，簇头节点的生存周期应受到更多的关注，当计算完节点si与其矩阵中的簇头gk之间的能耗因子后，将节点连接到能耗因子最小的簇头上。通过实验发现，当α取值为0.8、β取值为0.2时，得到的实验效果较好。

2.3 基于DE的路由分簇算法步骤

设网络中簇头节点的个数为D，种群规模为N，则基于差分的路由分簇算法的具体操作步骤如下：

1) 向网络中布撒传感节点，得到每个节点的位置坐标；

2) 对比通信距离，得到每个簇头的节点的可连接路由列表；

3) 对比通信距离，得到每个普通节点的可连接簇头列表；

4) 种群初始化，采用差分算法对最大化最小簇头生存周期进行优化；

5) 根据差分算法得到的最优值，得到路由通信列表并得到此时每个簇头节点在每轮通信中的能耗；

6) 对每个普通节点，按照其簇头集合的规模并通过比较能耗因子将节点进行分簇，且每个普通节点完成分簇后，更新簇头节点的能耗值。

3 实验结果

为验证本文算法的有效性和先进性，选择了目前针对异构无线传感器网络优化效果较好的GLBCA、GA和GAR等算法，在不同基站位置、布撒不同比例的普通节点和高能节点等情况下进行对比验证本文算法的性能。实验中的相关参数如表3所示。三个算法中的参数采用相关文献给出的数值进行设置。每组实验保证初始的节点布撒场景相同。

表3 参数设置

3.1 路由算法有效性验证

为验证本文提出的基于差分的路由算法的有效性，分别与GLBCA、GA和GAR进行对比，具体如图1所示。其中，图1为基站位置在(250,250)时，向网络中布撒50个高能节点时，四种算法得到的拓扑结构。

(a) DE (b) GLBCA

(c) GA (d) GAR

从图1中可以看出，DE、GLBCA、GA和GAR四种算法优化网络得到的拓扑结构差异较大。因为簇头节点更靠近基站，所以会接收和转发其他簇头的数据信息给基站，而接收转发信息会消耗一定的能量，因此，靠近基站的簇头将会率先耗尽自身的能量，也即每条通信链路上含有的节点数目越少，则靠近基站的簇头的生存周期越长。从图中可以看出DE算法得到的网络中最长通信链路上的簇头数为9个，GLBCA的最大通信链路上的簇头数为16个，GA为14个，GAR为14个。也即DE算法优化的网络中，靠近基站的簇头能耗更低，因此具备更长的网络生存周期。

3.2 路由分簇算法性能对比

通过对比不同基站位置、不同普通节点数和不同高能节点数目下， 验证DE、GLBCA、GA和GAR的算法性能。表4、表5是在基站位置在 (250,250)时，分别布撒20和50高能节点，普通节点数目在200～500之间各个算法获得网络生命周期的对比情况。表6、表7是在基站位置在(250,500)时，分别布撒20和50高能节点，普通节点数目在200～500之间各个算法的对比情况。

表4 基站在(250,250)，簇头数为20不同算法性能对比

表5 基站在(250,250)时，簇头数为50不同算法性能对比

表6 基站在(250,500)，簇头数为20不同算法性能对比

表7 基站在(250,500)，簇头数为50不同算法性能对比

从表4-表7可以看出：

1) 随节点数目的增多，四种算法优化的网络生存周期都逐渐下降，这是因为节点数目的增加，簇头节点接收融合信息的能耗也随之增加；

2) 当基站位置及普通节点的数目相同时，布撒50路由节点的能耗高于布撒20路由节点，这是因为实验中假设不论本簇内含有普通节点的数目是多少，每个路由节点发送融合后的数据包大小相同；

3) 当基站位置不同、路由节点数不同或普通节点数不同时，基于差分的分簇路由协议与其他三种算法相比有着明显的优势，也即能得到生存周期更长的异构网络。

综上说明，在不同基站位置、不同路由节点和普通节点布撒数目的情况下，本文算法在优化异构无线传感器网络时，都能更好地延长网络整体的工作时间。

4 结 语

针对异构传感器网络中的能耗不均问题，本文提出一种基于差分进化算法的路由算法和基于节点能耗的分簇算法。首先以网络中簇头节点的最短生存周期为目标，采用差分算法对其进行优化，降低了通信中各个簇头节点的能耗差异，然后根据节点与簇头的距离、网络中簇头节点的负载压力以及两种节点的能量差异对各个节点进行分簇，使簇头和节点的寿命都尽可能达到最大。实验仿真表明，本文算法在不同节点数目以及不同的环境下，均能使整个网络的生存周期达到最大，验证了本文算法的有效性及先进性。

[1] Chong C Y, Kumar S P. Sensor networks: evolution, opportunities, and challenges[J].Proceedings of the IEEE, 2003, 91(8):1247-1256.

[2] Abbasi A A, Younis M. A survey on clustering algorithms for wireless sensor networks[J].Computer Communications, 2007,30(14-15):2826-2841.

[3] Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocols for wireless microsensor networks[C]//Proceedings of the Hawaaian International Conference on Systems Sciences, Hawaii,2000:3005-3014.

[4] 余勇昌, 韦岗. 无线传感器网络中基于PEGASIS协议的改进算法[J].电子学报,2008,36(7):1309-1313.

[5] Tang J, Hao B, Sen A. Relay node placement in large scale wireless sensor networks[J].Computer Communications,2006,29(4):490-501.

[6] 孙力娟, 魏静, 郭剑,等.面向异构无线传感器网络的节点调度算法[J].电子学报,2014,42(10):1907-1912.

[7] Low C P, Fang C, Ng J M, et al. Efficient Load-Balanced Clustering Algorithms for wireless sensor networks[J].Computer Communications,2008,31(4):750-759.

[8] Gupta S K, Jana P K. Energy Efficient Clustering and Routing Algorithms for Wireless Sensor Networks: GA Based Approach[J].Wireless Personal Communications, 2015,83(3):2403-2423.

[9] Gupta S K, Kuila P, Jana P K. GAR: An Energy Efficient GA-Based Routing for Wireless Sensor Networks[C]//9th International Conference on Distributed Computing and Internet Technologies, 2013:267-277.

[10] Heinzelman W B, Chandrakasan A P, Balakrishnan H. Application-specific protocol architectures for wireless networks[D].Cambridge, MA, USA: Massachusetts Institute of Technology,2000.

ROUTING CLUSTERING PROTOCOL FOR WIRELESS SENSOR NETWORKS BASED ON DIFFERENCE ALGORITHM

Li Zhiming Tang Yongzhong

(CenterforInformationTechnology,HexiUniversity,Zhangye734000，Gansu，China)

Aiming at the problem of node energy consumption imbalance in heterogeneous wireless sensor networks, a routing protocol based on differential evolution algorithm and a clustering protocol based on node energy consumption are proposed. The protocol first aims at maximizing the minimum lifetime of cluster head nodes in the network to establish the function optimization model, and uses differential evolution algorithm to optimize it to extend the whole life cycle of the network. Then, the nodes are clustered according to the number of cluster heads in the node communication list, and the nodes are allocated to the cluster head with lower energy consumption, so as to balance the energy consumption of the network and extend the life cycle of the common nodes. The simulation results show that the difference-based routing clustering protocol can effectively balance the energy consumption of nodes in the network, extend the life cycle of the network and improve the network energy efficiency.

Heterogeneous wireless sensor networks Routing Clustering Difference algorithm

2016-05-31。李志明，讲师，主研领域：图像处理，计算机网络应用。唐永中，教授。

TP393

A

10.3969/j.issn.1000-386x.2017.01.024