赖 欣， 李伟勤， 胡 泽

(1.西南石油大学 电气信息学院，四川 成都 610500;2.电子科技大学 通信与信息工程学院，四川 成都 610054)

基于和声搜索方法的无线传感器网络寿命优化算法*

赖 欣1， 李伟勤2， 胡 泽1

(1.西南石油大学 电气信息学院，四川 成都 610500;2.电子科技大学 通信与信息工程学院，四川 成都 610054)

在无线传感器网络中，基站位置的动态调整可以提高网络的寿命，然而基站位置的最优化问题是NP完全问题。为了快速地更新基站的位置并减少数据的交互总量，提出了一种基于和声搜索方法的无线传感器网络寿命优化算法。首先，通过聚类方法将传感器节点分成若干组。其次，在每一个组中选出头节点，应用头节点对组中节点的数据进行压缩并与基站进行数据交互。最后，提出一种基于和声搜索方法的基站位置动态更新协议。实验表明：提出的协议与模糊聚类协议相比，传输数据总量更小，传感器节点的能量使用率更低，能更好地提高传感器网络的整体使用寿命。

无线传感器网络； 寿命； 优化算法； 和声搜索方法

0 引 言

无线传感器网络(WSNs)在民用和军用领域都有着广泛的应用，例如:环境监测，紧急救援，医疗服务，交通控制和目标跟踪等[1]。在传感器节点中，很大一部分能量都用于节点自身与基站之间的数据交互，因此，高效的路由协议在减少数据交互的同时可以延长传感器节点的使用寿命。由于传感器节点的能源都是轻量级的电池提供，高效的路由协议在减少传感器节点能源损耗的同时，可相应地增加了传感器网络的整体使用寿命[2]。

无线传感器网络基础设施中基站节点的选择对于传感器节点的能源消耗有着举足轻重的作用。当传感器节点与基站之间的距离增大时，传感器节点的能源损耗也相应地增大；相反，传感器节点与基站之间的距离变小，那么传感器节点的能源损耗也减少。因此，选择最佳的基站位置可以减少传感器节点的能源损耗，从而增大整个传感器网络的使用寿命。为了解决上述问题，可以采用移动基站来替代固定基站，从而平衡整个传感器网络的能源，以提高网络的使用寿命[3]。

移动基站的重新定位问题是图论问题，可以通过不同的数学规划方法进行解决。研究表明，最优的基站重新定位问题是NP完全问题[4]，因此，在大规模无线传感器网络下，不可能在短时间内找到最优解。文献[5，6]分别对采用线性规划和混合整数规划来优化基站的重新定位问题进行了综述。此外，移动基站的重新定位问题可以通过不同的启发式方法来解决，如，粒子群优化[7]和遗传算法[8]。

和声搜索算法[9]是一种元启发式优化算法，该算法在解决优化问题时模拟音乐家进行演奏，并将演奏表现调整到协调且美妙。为了研究基站重新定位问题，本文提出了一种基于和声搜索算法的优化框架，将无线传感器网络中的节点聚类成不同的组。在每个组中选出一个头节点，头节点收集同组中其它节点发来的数据，在将数据进行过滤后发往基站。在这种结构中，和声搜索算法用来寻找基站的最佳位置，即基站应当接近每个组的头节点，而不是网络中所有节点。

1 系统模型与问题定义

本节首先定义了无线传感器网络的网络模型和无线能量模型，接着给出了研究问题的定义。

1.1 网络模型

本文定义的无线传感器网络的模型如下：

1)基站的初始位置位于感知区域的中央，在每一轮的起始时刻，基站可以移到预先定义的节点；

2)网络中所有传感器节点是同类的，并且有能源约束；

3)节点间的传播通道是对称的；

4)每个节点都有各自的能量和位置信息；

5)节点的位置是固定的。

1.2 无线能量模型

在本文的无线能量模型中，发射节点消耗能量用于运行无线电和功率放大器，接收节点消耗能量用于运行无线电。节点将bbits数据传输到距离为d的节点所使用的能量为

(1)

接收该消息所使用的能量为

ERx=Eelec×b.

(2)

其中,Eelec为收发器电路所使用的能量，Efs和Emp是为了将误码率控制在可接受范围内传输1bit数据所消耗的能量。当传输的距离d小于阈值d0时，采用自由空间模型Efs；当传输的距离d不小于阈值d0时，采用多路径模型Emp。此处的阈值为

(3)

1.3 问题定义

图1给出了移动基站重新定位协议的整体结构。该协议以轮(即循环)的形式进行，每一轮分为初始化阶段和稳态阶段。在初始阶段，节点间形成分组，并确定新的基站位置。在随后的稳态过程中，节点之间进行数据的传输。在分组的形成中，本文提出了一种模糊C-means聚类算法用户优化无线传感器网络的基本结构。此后，根据选择的每个分组的头节点的位置，在感知区域中确定基站的新位置。每个分组的头节点负责收集本组内节点的数据，并与基站交互。本文的目的是最小化每个分组的头节点与基站之间的距离。为了实现上述目标，本文应用和声搜索算法用于确定新的基站的位置。

图1 基站位置更新流程Fig 1 Base station location update process

节点之间的数据传输发生在稳态过程。在初始化阶段完成后，分组内的每一个节点收到一条关于本组头节点的信息。传感器节点以很短的时间打开无线组件收集信息，并将数据发送到分组的头节点。头节点收集本组节点发来的数据，压缩后发往基站。由于传输的数据总量减少了，因而，导致整个网络的能量消耗减少。

2 协议描述

在无线传感器网络中，基站的最佳位置由每个组的头节点决定。理想情况下，基站应当位于所有头节点的中心。但实际上，寻找该中心位置是一个NP完全问题。当传感器网络中节点规模很大时，准确算法的执行时间长，节点消耗的能量多，必须采用近似算法。本文提出一种基于和声搜索算法的基站位置选择协议。和声搜索算法的搜索空间限制在头节点位置的边界，可以大大减小算法的复杂性。基于和声搜索算法的基站重新定位协议如下：

1)和声搜索初始化

在和声算法中，优化问题是一个最小化或者最大化问题，即最小化或者最大化目标函数f(a)，使得ai∈Ai,i=1,2,…N，其中,a为决策变量的集合{ai}，A为决策变量的取值范围Ai={ai(1),ai(2),…，ai(M)}，M为相应决策变量的值域的大小，N为决策变量的个数。在传感器网络中，中心节点距离所有分组的距离的最大值为

fobj=max∀k∈K{d(ai,Ck)}.

(4)

本文的目标是找出找到一个中心位置，使其距离所有分组的最大距离最小化，即

minfobj=min max∀k∈K{d(ai,Ck)}.

(5)

采用和声搜索算法，通过最小化公式(5)的目标函数得到相应的位置坐标，并将该位置坐标作为新的基站位置。

2)和声记忆库初始化

和声记忆库是一个由问题的解构成的矩阵，如公式(6)所示。在该步骤中，随机产生若干解，并按照目标函数对这些解进行反序排列

(6)

其中,HMS为和声库的大小，矩阵中的每一个元素为实数，表示新基站的位置坐标。每一个和声库向量ai的构建公式为

ai=[bsi,x,bsi,y].

(7)

其中,第i个向量的x轴坐标和t轴坐标分别为bsi,x和bsi,y。为了保证初始化的和声库中包含若干有效的和声向量，需要满足以下公式

(8)

其中,rand(1,k)为产生一个1～k的整数的随机函数，maxChsLocx和maxChsLocy分别是所有头节点位置的x轴和y轴坐标的上届，minChsLocx和minChsLocy分别是所有头节点位置的x轴和y轴坐标的下届，k为节点的分组个数。式(8)产生的位置坐标可以保证基站位于所有头节点的中间，因而是有效的。

3)和声优化

(9)

其中,变量bw为一个任意的距离带宽，该变量用来提升和声搜索算法的性能。概率PAR通过调整频率来模拟音乐，可以对新产生的和声向量进行微调，从而在搜索空间中发现更多的解。

4)和声库更新

5)算法停止

重复第3和第4步，直到算法完成了最大迭代次数。最后，在和声矩阵向量中选出最优值作为和声算法的解，即基站的新的位置。

3 模拟实验与结果

3.1 实验设置

为了对提出的协议进行验证，本文应用Matlab模拟了100个节点的传感器网络，并进行了2组实验。在第一组实验中，传感器节点随机部署在100 m×100 m 的区域内，并且保证没有相同的节点在同一位置。在第二组实验中，传感器节点随机部署在500 m×500 m的区域内，同时也保证每个位置最多含有一个节点。

在初始情况下，基站设置在感知区域的中间。当基站到达目的位置后，先进行数据的收集，然后再重新确定新的基站位置。在每一轮基站选择结束后，将新的分组头节点位置发送到基站，基站根据协议计算新的基站的位置，并移动到新的位置坐标。本文将节点分为5个组，即k=5，每个节点的初始能量为2 J。

模拟实验中的参数设置为Eelec=50 pJ/bit，Efs=50 pJ/bit/m2，Emp=0.001 3 pJ/bit/m4。局部节点向分组的头节点发送的消息和头节点向基站发送的消息的大小为b=4 000 bits。控制信号的大小为200 bits。和声搜索算法的参数分别为HMCR=0.95，PAR=0.3，HMS=30，迭代次数NI=3 000。

3.2 实验结果

为了评价提出的方法的性能，实验将本文提出的协议与文献[10]提出的模糊聚类协议进行对比。模糊聚类方法与本文提出的方法相似，都将传感器节点进行分组，然后选出头节点进行数据的传输。区别在于，本文在对节点进行分组后，根据分组的头节点动态的调整基站的位置。

本文提出的协议由于利用头节点对局部数据进行压缩传输到基站，其传输的数据总量减少了，能耗更低。图2给出了基站在2种方法下接收到的数据总量对比。从该图可以看出：本文提出的协议在2组实验中传输的数据都低于模糊聚类方法。此外，在500 m×500 m的实验中，数据的传输总量减少的更为明显。这表明本文提出的方法在传感器节点部署稀疏的大区域内可以更好减少数据的传输量，从而能更好地节约传感器节点的能量。

图2 数据传输总量对比图Fig 2 Comparison of data transmission amount

实验测试了2种算法的能量消耗随着迭代次数的变化。图3和图4分别为2种网络拓扑下，传感器网络的能源消耗随着时间的变化图。从图中可以看出：本文提出的基于和声搜索的基站位置更新算法与模糊聚类方法随着时间的变化，逐渐耗尽传感器网络的能量。在500m×500m的传感器网络中，由于传感器节点数是相同的，所有传感器之间的距离较远，因而能量损耗的速度快于100m×100m的传感器网络。在2种算法的对比中，本文提出的方法在同一时间的活跃节点数高于模糊聚类方法，并且网络节点耗尽的时间要滞后与模糊聚类方法。

图3 活跃节点随迭代次数的变化(感知区域100 m×100 m)Fig 3 Change of active nodes vs iteration numbers(sensing area 100 m×100 m)

图4 活跃节点随迭代次数的变化(感知区域500 m×500 m)Fig 4 Change of active nodes vs iteration numbers (sensing area 500 m×500 m)

实验同时对比了2种算法在不同传感器环境下，初始失效节点和最终失效节点的时间对比，对比结果如表1所示。初始失效节点为网络中第一个节点能量耗尽的时间，最终失效节点为网络中最后一个节点能量耗尽的时间。当网络中最后一个传感器节点的能量耗尽时，传感器网络消失。从表1可以看出，由于本文提出的协议根据和声搜索算法动态的调整基站的位置，使得节点的能量消耗相对均衡，因而初始失效节点的时间滞后。此外，由于本文在动态调整基站的同时，使得基站与数据传输节点的距离近了，导致数据传输消耗的能量少，因而网络的寿命更长。

表1 初始和最终失效节点的时间对比(单位：s)Tab 1 Comparison of time between initial and final failure nodes(unit:s)

4 结束语

为了快速确定基站位置的更新，减小基站与数据传输节点的距离，降低数据传输量，本文将传感器节点进行分组并选择投节点，并通过头节点对数据压缩后传输到基站。在基站位置的动态更新中，本文提出了一种基于和声搜索方法的基站位置更新协议。模拟实验表明:提出的协议与模糊聚类协议相比，传输数据总量更小，传感器节点的能量使用率更低，能更好地提高无线传感器网络的整体使用寿命。

[1] Lewis F L.Wireless sensor networks[J].Smart environments:Technologies,protocols,and applications,2004,8(5):11-46.

[2] 沈 波,张世永,钟亦平.无线传感器网络分簇路由协议[J].软件学报,2006,17(7):1588-1600.

[3] Vlajic N,Stevanovic D.Sink mobility in wireless sensor networks:When theory meets reality[C]∥Sarnoff Symposium,2009,SARNOFF’09,IEEE,2009:1-8.

[4] Akkaya K,Younis M,Youssef W.Positioning of base stations in wireless sensor networks[J].Communications Magazine,IEEE,2007,45(4):96-102.

[5] Cheng Z,Perillo M,Heinzelman W B.General network lifetime and cost models for evaluating sensor network deployment strategies[J].IEEE Transactions on Mobile Computing,2008,7(4):484-497.

[6] Zhao M,Yang Y.Bounded relay hop mobile data gathering in wireless sensor networks[J].IEEE Transactions on Computers,2012,61(2):265-277.

[7] Poli R,Kennedy J,Blackwell T.Particle swarm optimization[J].Swarm Intelligence,2007,1(1):33-57.

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

[9] Geem Z W,Kim J H,Loganathan G V.A new heuristic optimization algorithm:Harmony search[J].Simulation,2001,76(2):60-68.

[10] Alia O M.A decentralized fuzzy clustering-based energy-efficient routing protocol for wireless sensor networks[C]∥Proceedings of the 13th Annual Wireless Telecommunications Symposium,Washington,DC,USA,2014:145-147.

Lifetime optimization algorithm for WSNs based on harmony searching method*

LAI Xin1, LI Wei-qin2, HU Ze1

(1.School of Electrical and Information,Southwest Petroleum University,Chengdu 610500,China;2.School of Communication and Information Engineering,University of Electronic Science and Technology,Chengdu 610054,China)

In wireless sensor networks(WSNs),dynamic regulation of position of base station can improve lifetime of the whole networks,however,the optimization problem of base station location is NP-complete problem.In order to relocate the base station quickly and reduce the total amount of exchange data,propose a lifetime optimization algorithm based on harmony searching for WSNs.Firstly,through clustering method,divide sensor nodes into groups.Secondly,select head node in each group,compress datas in each group and apply the head node to exchange data with the base station.Finally,propose a base station relocation protocol based on harmony searching.The experiments show that compared with the fuzzy cluster protocol,the proposed protocol has less data transmission amount and low energy usage rate,and then can better improve the whole lifetime of WSNs.

wireless sensor networks(WSNs); lifetime; optimization algorithm; harmony searching method

10.13873/J.1000—9787(2014)08—0134—04

2014—05—19

国家“863”计划资助项目(2007AA090801—03)；国家重大专项资助项目(2008ZX05026—001—09)；国家自然科学基金资助项目(51304165)；四川省教育厅资助项目(14ZB0052)

TP 319

A

1000—9787(2014)08—0134—04

赖 欣(1981-)，女，四川蓬安人，硕士，讲师，主要研究方向为传感器技术、自动化技术。