基于Hopfield—GA算法的移动Sink数据采集优化

吕立新　梁艳　汪伟

摘要：针对移动sink数据采集算法存在的数据采集量低、网络生存时间短等缺陷，从优化网络拓扑结构的角度设计了数据采集模型，将Hopfield反馈神经网络与遗传算法结合，设计了基于Hopfield-GA算法数据采集方案，给出了染色体编码、交叉运算、变异运算和算法执行流程。从实验结果分析，该算法具有收敛速度快、寻优精度高等特点，在数据采集量和网络生存时间二个衡量指标上均优于现有的STP算法。

关键词： 无线传感器网络； 移动Sink； Hopield； 遗传算法； 数据采集

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）14-3225-05

Abstract：According to disadvantages of mobile sink in data collection capacity and network survival time， this paper design a Hopfield - GA data acquisition algorithm based on Hopfield neural network and genetic algorithm. Chromosome coding、crossover operation and variant operation of the algorithm was designed. From the analysis of experimental results， this algorithm has fast convergence rate and higher characteristic， in the amount of data acquisition and network survival time two indicators are better than the existing STP algorithm.

Key words：wireless sensor network； mobile sink； hopield； ga algorithm； data collection

无线传感器网络作为一种新兴的通信技术在农业、军事各领域得到了广泛的应用，成为生态环境监测、数据采集和处理首选的解决方案。一般的环境监测无线传感器网络都采用固定的网络拓朴结构，所有节点采集的数据通过多跳路由的方式汇总到Sink节点，由Sink节点将数据传给远程的服务器。这种情况下导致节点的节点能耗不均，影响网络生存时间。针对这一缺点，使用移动的Sink进行数据采集，从而均衡各节点的能量损耗，提高网络生存时间的解决方案被提出并应用，给出了如最短路径树（shortest path tree，SPT）等数据采集算法[1-5]。使用移动Sink节点按照预设的运动路径，对簇首节点汇总的数据进行周期性的采集，在一定程序上能够均衡节点的能耗，但由于Sink节点的移动性，必然致使其对簇首节点的数量采集量受通信时间的约束，制约了采集周期内的数据采集量。因而，如何在均衡节点能耗的基础上尽可能提高数据采集量，提高移动Sink节点的数据采集效率，是应用移动Sink节点必须要解决的一个问题。

针对目前移动Sink数据采集算法存在的不足，该文从传感器网络拓朴结构的角度出发，对族首节点的成员数量进行优化，同时考虑数量采集量和网络能耗两个指标，建立数据采集模型，将Hopfield反馈神经网络与遗传算法结合，设计了基于Hopfield-GA算法数据采集方案，为移动Sink传感器网络提供了一种数据采集量高且全网能耗低的数据采集算法。

1 移动Sink的最小能耗最大数据量数据采集模型

1.1模型应用场景及基本假设

在使用移动Sink节点的传感器网络中，成员节点均匀分布的监测区域内，每个成员节点从属于一个簇首节点，形成一个树状的网络拓朴结构。Sink节点按照某个预设的运动轨迹，以运动轨迹为圆心，以节点的通信半径R为半径形成的一个带状区域称为直接通信区。处在直接通信区域的簇首节点可直接与移动Sink节点建立通信，上传簇内汇总的数据。该文的数据采集模型建立在如下的假设基础上：（1）每个成员节点只能从属于一个固定的簇首节点；（2）移动Sink节点只与簇首节点建立通信，接收数据；（3）各成员节点采用多跳路由的方式与簇首节点通信；（4）所有簇首节点均部署在Sink节点的直接通信区；（5）各成员节点和簇首节点具有同样的能耗和数据发送能力；（6）移动Sink节点有充足的存储空间和计算能力。

在监测区域中部署的传感器节点总数为[nt]，成员节点数为[nm]，簇首节点数为[ns]，三者之间的关系如式（1）所示。

[nt=ns+nm] （1）

各簇首节点将汇总的簇内数据传送给Sink节点，设簇首节点[i]含有[nsi]个成员节点，单位时间内的数据发送能力为[qsi]，Sink节点的数据采集总量为[Qt]，其关系可用式（2）描述。

[Qt=i=1nsiqsi] （2）

设成员节点单位时间内的数据采集量为[da]，Sink节点与簇首节点间的数据传输速度为[dt]，通信时间为[tsi]，Sink节点的单轮数据量集用时为[t]，则簇首节点的数据发送能力[qsi]应满足式（3）的关系。

[qsi=min[dttsi，datnsi]] （3）

根据簇首节点的数据传送能力，设簇首节点[i]的最小成员节点数量为[nminsi]，由式（3）可推导出Sink节点最大化数据采集量的充分必要条件为：

[nsi≥dttsidat=nminsi] （4）

根据模型的假设条件，成员节点的数据接收和发送能耗为一常量，设成员节点收发数据的单位比特能耗为[e]，数据接收、发送量分别为[qt]和[qr]，则节点的数据收发总能耗[Ert=e（qt+qr）]。在一个数据采集周期内，成员节点[i]的数据发送量[qit]和数据接收量[qir]应满足式（5）所述关系。

[qit=qir+dat] （5）

设成员节点到簇首节点的路由跳数为[Ci]，则全网数据接收总量和[Ci]应满足如式（6）所示的关系，其中如果[i]为簇首节点，则[Ci=0]。

[i=1ntqir=i=1ntCi?（dat）] （6）

根据式（5）和式（2）可知，全网总能耗[Et]可表示为：

[Et=i=1ntErti=i=1nte（qir+qit）=i=1nte（2qir+dat）=i=1nte（2Ci+1）?（dat）] （7）

1.2数据采集量最大化模型

基于模型的前提假设和式（7）所示的关系，最小的全网能耗问题可转化为节点间通信的跳数总和最小的问题，即[min（Et）=min（i=1nte（2Ci+1）?（dat））=min（i=1ntCi）]，同时，只要满足[nsi≥nminsi]，即可以实现数据采集最大化。

设矩阵[A（nm，ns）]，是由元素[aij][（i=1，…，nm，j=1，…，ns）]组成，其中[aij]为0-1变量，如果节点[i]从属于簇首节点[j]，则[aij=1]，否则，[aij=0]。设矩阵[C（nm，ns）]，是由元素[cij][（i=1，…，nm，j=1，…，ns）]组成，[cij]表示成员节点[i]到簇首节点[j]的路由最短跳数，则数据采集模型可表示为：

目标函数：[min（i=1nmj=1nsaij?cij）] （8）

约束条件：[j=1nsaij=1，?i；i=1nmaij≥nminsj，?jnm≥j=1nsnminsj] （9）

2 Hopfield-GA优化算法设计

根据上述的目标函数和约束条件可知，该模型属于NP类组合优化问题，对这类问题一般使用启发式的算法来寻求最优解。该文采用二维染色体编码方案设计遗传算法的交叉运算和变异运算，利用遗传算法来对模型求解。考虑到移动Sink节点一般采用嵌入式处理器，其运算能力和运算资源受到制约，为了提高算法的收敛速度，提高算法的实时性，采用Hopfield反馈神经网络对遗传算法的解种群进行优化，尽可能地消除初始种群中的不可行解，缩小可行解搜索空间，使算法可以快速的收敛于最优解。

2.1 适应度函与数染色体编码设计

适应度函数是衡量当前解优劣程度的重要指标，同时也是遗传算法进行种群进化选择子代种群的依据，根据优化模型中的目标函数（式8），其表示形式如下：

[f（A）=i=1nmj=1nsaij?Cij] （10）

从模型的约束条件可知，对一任意的当前解中簇首节点的最小成员需求量与已分配成员节点的数量之差，反应该解与约束条件的适应程度。为了尽可能消除不可行解，采用式（11）所示的不适应度函数来衡量当前解的可行度，函数值越小，表示当前解越可行。

[unf（A）=j=1nsmin（0，i=1nm（aij-nminsj）] （11）

设计合适的染色体编码方案，是应用遗传算法求解首先要解决的问题。在本文的模型中，对于任意一可行解[aij][（i=1，…，nm，j=1，…，ns）]是一个[nm]行[ns]列的二维矩阵，为了便于设计交叉运算和变异运算，该文采用二维矩阵作为染色体编码方案。假设[ni（i=1，…8）]表示8个成员节点，[sj（j=1，…3）]表示3个簇首节点，每个成员节点对应于簇首节点均有一个值，如果该值为1，表示该成员节点从属于对应的簇首节点，在如图1所示的网络拓朴结构中，形成的染色体编码方案如图右侧所示。

2.2 Hopfield网络初始解局部搜索算法设计

为了节省Sink节点的运算资源，尽可能地消除解种群中的不可行解，提高算法的收敛速度和最优值搜索能力，对遗传算法随机生成的初始解种群使用Hopfield反馈神经网络进行局部搜索。借助Hopfield网络局部搜索能力，快速度地消除初始种群中的不可行解，为遗传算法提供进行交叉、变异运行所需要的父代基因池。

对于初始解种群的每个解向量[Aij]中的每个元素产生一个神经元[sij]，其值为0或1，对每个神经元采用式（12）所示的演化规则进行串行更新。解向量的适应度值和不适应度值用[f（A）define]和[unf（A）define]表示。

[sij（t）=0，f（Ai）>f（A）define?unf（Ai）>unf（A）define1，f（Ai）

在Hopfield网络搜索的过程中，如果所有的神经元状态都没有发生改变即表示局部搜索完成，形成了一个可行解。通过这种搜索为后续的交叉变异操作提供满足预定义的适应值的父代基因，加速算法向最优值收敛。

2.3 种群进化策略设计

通常情况下任何一个启发示算法都应该有一个包含个体协作、自我适应和竞争选择三部分组成的种群进化策略[6]。在本算法中使用染色体的交叉运算来实现解种群中的个体间协作，其流程如算法1所示。

算法1：交叉操作算法

在进化策略中，解种群中个体的自我适应采用染色体的变异操作来实现，变异操作的规则如图2所示。首先从染色体基因池中随机挑选两对基因，对基因的编码值进行交换，产生一条新的染色体，其目的是交换两个成员节点的簇首节点，增加解种群的多样性，同时保证产生的新染色体符合约束条件。

按照一定比例由染色体的复制、交叉和变异三种运算产生新的子代种群的方式作为算法的竞争选择策略。其规则为：子代种群中20%染色体由将父代种群中适应值最较好的染色体直接复制产生，75%的染色体由父代种群按算法1进行交叉运算产生，另外5%的子代染色体由父代种群通过变异操作产生，进化过程种群中染色体的数量始终保持一恒定值。

2.4 Hopfield-GA算法的执行流程

Hopfield-GA算法的执行流程如下：（1）随机生成N个染色体，形成初始解种群；（2）对初始解种群进行Hopfield局部搜索，消除不可行解，行成父代种群；（3）按式（12）计算父代种群中每个解个体的适应值，并按适应值优劣程序排序；（4）对父代种群进行交叉运算、变异运算和选择操作，产生新一代的子种群；（5）重执行（2）-（4）步骤，直至循环条件退出或连续5代最优值保持不变，输出最优解。

3 Hopfield-GA算法仿真与性能评估

基于OMNet++4.1仿真软件和Castalia传感器节点模型，建立算法的仿真环境，使用Matlab语言编写算法，进行算法的运行仿真实验。首先随机生成60个传感器节点，网络结构划分为5个簇，成员节点以250B/s的速度进行数据的连续采集并传送给簇首节点，节点的初始能量为20J，单位数据传输能耗[e=4μJ/B]，移动Sink节点单轮数据采集时间为100s，数据传输速率为25KB/s，遗传算法的解种群规模为100，计算终止进化代数为150。

为了验证Hopfield-GA算法的有效性，使用相同的参数对普通GA算法和Hopfield-GA算法分别进行仿真计算，两者的收敛速度、寻优结果如图4所示。类比参考文献[5]中提出的SPT算法，采用相同的参数从全网能耗、网络生存时间、数所采集量和成员节点分配情况4个方面，进行了仿真实验，结果如图3至图6所示。

从图3和图4可见，加入了Hopfield局部搜索功能的GA算法的收敛速度是普通GA算法的1倍，单轮数据采集量接近于理论最大采集量的90%，能够较好地满足Sink节点运算资源有限和实时性要求高的特点。综合图5和图6所示的仿真实验结果可见，Hopfield-GA数据采集算法相对于STP算法能够实现最大量采集数据的同时保证节点能耗负载的均衡分配，使其在数量采集总量和网络生存时间上突显出较大的优势。

4 结论

将移动Sink应用于无线传感器监测网络是一种提高网络生存时间的有效方法，但当前移动Sink节点数据采集算法无法获取较大的数量采集了和较长的网络生存时间。针对这些缺陷本文将Hopfield反馈神经网络与遗传算法结合，设计了基于Hopfield-GA算法数据采集方案，给出了算法的种群进化规则和计算流程。从实验结果看，该算法能够实现最大数据采集量的同时降低全网能耗，提高网络生存时间，为无线传感器网络在信息监测领域的应用提供了一套可行的技术方案。

参考文献：

[1] Chakrabarti A， Sabharwal A， Aazhang B. Using predictable observer mobility for power efficient design of sensor networks. Proceedings of the 6th International Symposium on Distributed Autono2 mous Robotics Systems [C].Fukuoka： SPR INGER2VERLAG TOKYO，2008：129-144.

[2] Chakrabarti A， Sabharwal A， Aazhang B. Communication power optimization in a sensor network with a path-constrained mobile observer. Proceedings of the IEEE INFOCOM. San Francisco，USA，2010，2（3）：297-324.

[3] Song L.Architecture of wireless sensor networks with mobile sinks： sparsely deployed sensors. IEEE Trans. Journal of Intelligent & Robotic Systems，2011，56（4）：1826-1836.

[4] Luo J， Panchard J， Piorkowski M， Grossglauser M， Hubaux JP. MobiRoute： Routing towards a mobile sink for improving lifetime in sensor networks. In： IEEE Wireless Communications and Networking Conference. Third European Workshop. Zurich， Switzerland， 2011：480-497.

[5] Somasundara A， Kansal A， Jea D， Estrin D， Srivastava M. Controllably mobile infrastructure for low energy embedded networks. Lecture Notes in Control and Information Sciences，2012，5（8）：958-973.

[6] 吕立新. 基于移动Sink节点传感器网络的农业环境信息监测系统设计与实现[D].合肥：安徽大学，2010.

2.4 Hopfield-GA算法的执行流程

Hopfield-GA算法的执行流程如下：（1）随机生成N个染色体，形成初始解种群；（2）对初始解种群进行Hopfield局部搜索，消除不可行解，行成父代种群；（3）按式（12）计算父代种群中每个解个体的适应值，并按适应值优劣程序排序；（4）对父代种群进行交叉运算、变异运算和选择操作，产生新一代的子种群；（5）重执行（2）-（4）步骤，直至循环条件退出或连续5代最优值保持不变，输出最优解。

3 Hopfield-GA算法仿真与性能评估

基于OMNet++4.1仿真软件和Castalia传感器节点模型，建立算法的仿真环境，使用Matlab语言编写算法，进行算法的运行仿真实验。首先随机生成60个传感器节点，网络结构划分为5个簇，成员节点以250B/s的速度进行数据的连续采集并传送给簇首节点，节点的初始能量为20J，单位数据传输能耗[e=4μJ/B]，移动Sink节点单轮数据采集时间为100s，数据传输速率为25KB/s，遗传算法的解种群规模为100，计算终止进化代数为150。

为了验证Hopfield-GA算法的有效性，使用相同的参数对普通GA算法和Hopfield-GA算法分别进行仿真计算，两者的收敛速度、寻优结果如图4所示。类比参考文献[5]中提出的SPT算法，采用相同的参数从全网能耗、网络生存时间、数所采集量和成员节点分配情况4个方面，进行了仿真实验，结果如图3至图6所示。

从图3和图4可见，加入了Hopfield局部搜索功能的GA算法的收敛速度是普通GA算法的1倍，单轮数据采集量接近于理论最大采集量的90%，能够较好地满足Sink节点运算资源有限和实时性要求高的特点。综合图5和图6所示的仿真实验结果可见，Hopfield-GA数据采集算法相对于STP算法能够实现最大量采集数据的同时保证节点能耗负载的均衡分配，使其在数量采集总量和网络生存时间上突显出较大的优势。

4 结论

将移动Sink应用于无线传感器监测网络是一种提高网络生存时间的有效方法，但当前移动Sink节点数据采集算法无法获取较大的数量采集了和较长的网络生存时间。针对这些缺陷本文将Hopfield反馈神经网络与遗传算法结合，设计了基于Hopfield-GA算法数据采集方案，给出了算法的种群进化规则和计算流程。从实验结果看，该算法能够实现最大数据采集量的同时降低全网能耗，提高网络生存时间，为无线传感器网络在信息监测领域的应用提供了一套可行的技术方案。

参考文献：

[1] Chakrabarti A， Sabharwal A， Aazhang B. Using predictable observer mobility for power efficient design of sensor networks. Proceedings of the 6th International Symposium on Distributed Autono2 mous Robotics Systems [C].Fukuoka： SPR INGER2VERLAG TOKYO，2008：129-144.

[2] Chakrabarti A， Sabharwal A， Aazhang B. Communication power optimization in a sensor network with a path-constrained mobile observer. Proceedings of the IEEE INFOCOM. San Francisco，USA，2010，2（3）：297-324.

[3] Song L.Architecture of wireless sensor networks with mobile sinks： sparsely deployed sensors. IEEE Trans. Journal of Intelligent & Robotic Systems，2011，56（4）：1826-1836.

[4] Luo J， Panchard J， Piorkowski M， Grossglauser M， Hubaux JP. MobiRoute： Routing towards a mobile sink for improving lifetime in sensor networks. In： IEEE Wireless Communications and Networking Conference. Third European Workshop. Zurich， Switzerland， 2011：480-497.

[5] Somasundara A， Kansal A， Jea D， Estrin D， Srivastava M. Controllably mobile infrastructure for low energy embedded networks. Lecture Notes in Control and Information Sciences，2012，5（8）：958-973.

[6] 吕立新. 基于移动Sink节点传感器网络的农业环境信息监测系统设计与实现[D].合肥：安徽大学，2010.

2.4 Hopfield-GA算法的执行流程

Hopfield-GA算法的执行流程如下：（1）随机生成N个染色体，形成初始解种群；（2）对初始解种群进行Hopfield局部搜索，消除不可行解，行成父代种群；（3）按式（12）计算父代种群中每个解个体的适应值，并按适应值优劣程序排序；（4）对父代种群进行交叉运算、变异运算和选择操作，产生新一代的子种群；（5）重执行（2）-（4）步骤，直至循环条件退出或连续5代最优值保持不变，输出最优解。

3 Hopfield-GA算法仿真与性能评估

基于OMNet++4.1仿真软件和Castalia传感器节点模型，建立算法的仿真环境，使用Matlab语言编写算法，进行算法的运行仿真实验。首先随机生成60个传感器节点，网络结构划分为5个簇，成员节点以250B/s的速度进行数据的连续采集并传送给簇首节点，节点的初始能量为20J，单位数据传输能耗[e=4μJ/B]，移动Sink节点单轮数据采集时间为100s，数据传输速率为25KB/s，遗传算法的解种群规模为100，计算终止进化代数为150。

为了验证Hopfield-GA算法的有效性，使用相同的参数对普通GA算法和Hopfield-GA算法分别进行仿真计算，两者的收敛速度、寻优结果如图4所示。类比参考文献[5]中提出的SPT算法，采用相同的参数从全网能耗、网络生存时间、数所采集量和成员节点分配情况4个方面，进行了仿真实验，结果如图3至图6所示。

从图3和图4可见，加入了Hopfield局部搜索功能的GA算法的收敛速度是普通GA算法的1倍，单轮数据采集量接近于理论最大采集量的90%，能够较好地满足Sink节点运算资源有限和实时性要求高的特点。综合图5和图6所示的仿真实验结果可见，Hopfield-GA数据采集算法相对于STP算法能够实现最大量采集数据的同时保证节点能耗负载的均衡分配，使其在数量采集总量和网络生存时间上突显出较大的优势。

4 结论

将移动Sink应用于无线传感器监测网络是一种提高网络生存时间的有效方法，但当前移动Sink节点数据采集算法无法获取较大的数量采集了和较长的网络生存时间。针对这些缺陷本文将Hopfield反馈神经网络与遗传算法结合，设计了基于Hopfield-GA算法数据采集方案，给出了算法的种群进化规则和计算流程。从实验结果看，该算法能够实现最大数据采集量的同时降低全网能耗，提高网络生存时间，为无线传感器网络在信息监测领域的应用提供了一套可行的技术方案。

参考文献：

[1] Chakrabarti A， Sabharwal A， Aazhang B. Using predictable observer mobility for power efficient design of sensor networks. Proceedings of the 6th International Symposium on Distributed Autono2 mous Robotics Systems [C].Fukuoka： SPR INGER2VERLAG TOKYO，2008：129-144.

[2] Chakrabarti A， Sabharwal A， Aazhang B. Communication power optimization in a sensor network with a path-constrained mobile observer. Proceedings of the IEEE INFOCOM. San Francisco，USA，2010，2（3）：297-324.

[3] Song L.Architecture of wireless sensor networks with mobile sinks： sparsely deployed sensors. IEEE Trans. Journal of Intelligent & Robotic Systems，2011，56（4）：1826-1836.

[4] Luo J， Panchard J， Piorkowski M， Grossglauser M， Hubaux JP. MobiRoute： Routing towards a mobile sink for improving lifetime in sensor networks. In： IEEE Wireless Communications and Networking Conference. Third European Workshop. Zurich， Switzerland， 2011：480-497.

[5] Somasundara A， Kansal A， Jea D， Estrin D， Srivastava M. Controllably mobile infrastructure for low energy embedded networks. Lecture Notes in Control and Information Sciences，2012，5（8）：958-973.

[6] 吕立新. 基于移动Sink节点传感器网络的农业环境信息监测系统设计与实现[D].合肥：安徽大学，2010.