彭珍瑞，李 辉，董海棠，殷 红

(兰州交通大学 机电工程学院，甘肃 兰州730070)

0 引 言

无线传感器网络(WSNs)节点结构紧凑，重量轻，采用电池供电，一般情况下，节点分布在不便于维护的恶劣环境中，必须通过各种手段节约传感器节点能量。另外，尽量减小延迟保证信息获取的实时性是无线传感器网络的更高性能的要求［1，2］。目前大多数节能算法通过分层传输数据包方法实现，如LEACH 算法［3］、PEGASIS 算法［4］等。相对于节点到基站间的数据直接传输，分层方法减小了传输距离，降低了能耗，但算法中簇内成员在将数据送到簇头节点时存在排队竞争，同时多跳发送数据到基站，增大了网络的延迟，影响网络实时性。和声搜索(harmony search，HS)算法［5］作为一种新的启发式算法，在解决车辆运输问题［6］、水网设计［7］等方面都取得了一系列的研究成果。

本文提出一种基于和声搜索算法的无线传感器网络最优路径选取方法，旨在保证传输能耗较小的前提下，降低网络的传输延迟，完成对能量和传输延迟两方面的优化。

1 无线传感器网络模型建立

1.1 路径传输延迟［2］

路径传输延迟是指数据包从该路径的源节点发送到该路径的目的节点所需要的时间，整个网络信息交互导致的通信延迟由四部分组成:处理延迟、排队延迟、传输延迟和传播延迟。处理延迟由传感器节点的处理器决定，传输延迟和传播延迟分别由网络带宽和信号传播速度决定，这三种网络延迟条件恒定，所以，选取相同的权值因子，将这三种延迟视为只与传输路径的跳数有关，通过中间节点的数量越多，则延迟越高，即通过单个节点的网络延迟为χ。而减小排队延迟则需要限制数据流尽量少地通过某同一节点进行中转，减少数据传输之间的竞争。若节点等待接收一个数据包的网络延迟为w，若该节点有k 个数据包等待接收，则网络延迟为k·w。假设网络有一条传输路径从V0将数据发送到Vn，路径P 为(V0，V1，…，Vi，…，Vn)，di为节点i 与上一个节点i－1 之间的传输延迟，di=χ+kiw，则该路径P 的网络延迟Dp为

假设从节点V0将数据发送到Vn有m 条路径，则每条路径被选中的概率为

1.2 网络能耗模型［1］

无线传感器网络节点的能耗通常由三部分组成:微控制器单元(MCU)、收发单元(TCR)、传感器主板(SB)。每个部分都会有一定的能量消耗，所以，传感器节点i 能耗可以表示为

其中，Ei_MCU为传感器微控制单元消耗能量;Ei_TCR为传感器收发单元消耗的能量;Ei_SB为传感器主板消耗的能量。收发单元消耗的能量又可以分为接收数据的能耗Ei_TCR_RX和发送数据产生的能耗Ei_TCR_TX(di)，所以，选择路径P 能量消耗为

2 和声搜索算法概述

和声搜索算法将乐器声调的和声类比于优化问题中的解向量，对音乐的评价对应优化问题的目标函数值［5］。和声搜索的计算步骤如下:

初始化问题和算法参数

1)优化问题描述如下

其中，f(x)为目标函数，x 为由决策变量xi构成的解向量，i=1，2，…，N，每一个决策的值域为Xi。和声记忆库的大小定义为HMS、和声记忆库取值概率HMCR、音调微调概率PAR、音调微调带宽bw、创作的次数Tmax。

2)初始化和声记忆库

随机生成HMS 个和声x1，x2，…，xHMS放入和声记忆库，和声记忆库形式如下

3)生成一个新的和声

生成新的和声x'i=［x'1，x'2，…，x'N］，新的和声每一个音调x'i(i=1，2，…，N)通过以下三种机理产生:a.学习和声记忆库;b.音调微调;c.随机选择音调。

4)更新和声记忆库

对第三步中的新解进行评估，如果优于HM 中的函数值最差的一个，则将新解更新至HM 中。

5)检查是否达到算法终止条件

重复步骤第3 步和第4 步，直到创作(迭代)次数达到Tmax为止。

3 基于和声搜索算法的无线传感器网络模型求解

3.1 路径生成的编码方式

和声搜索算法应用于无线传感器网络数据传输中，最棘手的问题在于如何将网络中的路径编码到和声记忆库中，同时，编码方式会对搜索最优路径的有效性有重要影响。本文采用基于优先级路径编码方式［8］。

假设网络中的节点数目为Nmax，同时将网络中的节点编号为将被选入传输路径中的节点的集合，xk表示和声记忆库中的变量，该变量赋值为－2/Nmax～2/Nmax的随机数。路径从节点1 开始，逐个产生，当每次有新的节点加入时，该节点对应在的变量将被赋值较大的负优先值－2/Nmax，使得该节点很难被再次选中。具体算法步骤:

2)判断是否满足终止条件，如果tk=Nmax或跳转到第4 步;否则k=k+1，跳转到第3 步。

3)路径拓展，选择与节点tk－1有数据链接，同时节点优先值最大的节点作为下一跳的节点xk(tk)=－2/Nmax，跳转到第2 步。

4)路径完成，如果最后得到的终止节点为目标节点，则生成的集合为有效路径;若终止节点不为目标节点，则为无效路径。

在Matlab 仿真环境下，以N=20 为例，在100 m×100 m的区域内随机生成20 个节点，假定每个节点的传输半径为R，在此例中R 取50 m，即两节点间的距离小于50 m，视为相邻节点，数据包需要从节点1 发送到节点20，网络拓扑结构如图1 所示。同时随机生成编码如表1。

图1 网络拓扑结构图Fig 1 Structure diagram of network topology

表1 编码表Tab 1 Encoding table

由拓扑结构可知，节点1 与节点2，3，5，6，7 可以产生数据通信，比较节点2，3，5，6，7 对应的变量优先值，选择节点3 作为下一跳的节点，并将节点1 的变量赋值为－10，确保其在后面的搜索中不会被选为中转点，同时节点3 和2，4，5，9，10 有数据链接，比较后确定节点4 作为下一跳的中转节点，依此类推，得到传输路径V={1，3，4，8，17，20}。

3.2 基于和声搜索的算法流程

由对网络模型的分析可知，网络建立由网络延迟和通信能耗两方面因素决定，通过用户对网络中延迟和能耗的要求不同，延迟和能耗权重不同，分别设为α 和β，α+β=1。和声向量的质量通过目标函数值来判断，对低延迟和低功耗的目标定义目标函数为

考虑延迟和能耗影响，得到算法流程如图2 所示。

3.3 结果与分析

图2 算法流程图Fig 2 Flow chart of algorithm

在Matlab 环境下，对100 个节点的网络应用和声搜索算法进行仿真实验，考虑传感器相邻节点距离R ＜30 m。对延迟和能量消耗两个目标所占权重值的不同，分析延迟和能耗对网络数据传输路径选择的影响。

分别取α=0，β=1;α=0.5，β=0.5;α=1，β=0;迭代次数J=1200;图3(a)为网络能耗图，图3(b)为网络延迟图。

图3 网络能耗和网络延迟图Fig 3 Diagram of network energy consumption and network delay

由图3 变化趋势可以看出:在运行约600 代后，基本可以得到稳定的数据传输路径。由记录的数据可知，取α=0，β=1，即单独考虑能耗影响因素，路径产生的能耗为2 695.86 J，延迟为10.4 s;取α=1，β=0，即单独考虑降低延迟，导致的延迟为6.2 s，能耗为3 355.73 J;取α=0.5，β=0.5，即给定选择路径中能耗及延迟各占50%权重，则产生的路径能耗为2 851.1 J，延迟为7.4 s。比较3 组数据，当优先考虑能耗因素，延迟会相应偏高，而优先考虑延迟因素，则能耗相对较高，虽然都未达到单方面的最优值，但综合考虑能量消耗和网络延迟两方面因素，可以得到满足总目标的较优传输路径。由此可见，网络延迟和网络中的能量消耗两方面因素相互制约，无法同时达到最优状态，而给延迟和能耗设定相应的权重值，可以得到用户所需求的相应优化路径。

4 结 论

本文应用和声搜索算法解决无线传感器网络中低延迟和低能耗的双目标优化问题。分析了网络中延迟和能耗模型，同时在找寻最优路径时，采用基于优先级的路径编码算法，迭代更新和声记忆库。在Matlab 仿真环境下对网络进行仿真实验后，验证网络延迟和网络中的能量消耗的相互制约关系，可以根据用户对网络的需求，得到相应的优化路径。

［1］ Cheng Chi－Tsun，Tse Chi K，Lau Francis C.M.A delay－aware data collection network structure for wireless sensor networks［J］.IEEE Sensors Journal，2011，11(3):699－710.

［2］ 顾洪军，张 佐，吴秋峰.网络控制系统中周期性通信的实时性充分条件［J］.测控技术，2001，20(6):1－4.

［3］ Heinzelman W，Chandrakasan A，Balakrishnan H.An applicationspecific protocol architecture for wireless micro sensor networks［J］.IEEE Translations on Wireless Communications，2002，1(4):660－670.

［4］ Lindsey S，Raghavendra C S.PEGASIS:Power－efficient gathering in sensor information systems［C］∥Proc IEEE Conf Aerosp Big Sky，MT，USA，2002:1125－1130.

［5］ Geem Z，Kim J，Loganathan G.A new heuristic optimization algorithm:Harmony search［J］.Simulation，2001，76(2):60－68.

［6］ Geem Z W，Lee K S，Park Y.Application of harmony search to vehicle routing［J］.American Journal of Applied Sciences，2005，2(12):1552－1557.

［7］ Geem Z W.Optimal cost design of water distribution networks using harmony search［J］.Engineering Optimization，2006，38(3):259－280.

［8］ Mohemmed A W，Sahoo N C，Geok T K.Solving shortest path problem using particle swarm optimization［J］.Applied Soft Computing，2008，8(4):1643－1653.