模拟退火算法优化无线传感器网络路由技术

袁桂霞

（江苏城市职业学院，南京210017）

摘要：由于模拟退火算法具有全局快速收敛优点，同时利用遗传算法优化模拟退火算法，加快模拟退火算法收敛速度，使其达到具有很强的全局搜索能力，最后对WSN 路由优化问题求解。实验表明，本文方法有效地提高了节点能量利用效率。关键词：无线传感器；模拟退火算法；路由中图分类号：ＴＰ３９３

文献标识码：Ａ

文章编号：１００１－７１１９（２０１２）１２－０１５５－０３

Wireless Sensor Network Routing Technology

Yuan Guixia

(City Vocational College of Jiangsu,Nanjing 210017,China)

Abstract:The simulated annealing algorithm has rapid global convergence advantages,at the same time using genetic algorithm optimization simulated annealing algorithm,simulated annealing algorithm to accelerate the convergence speed,so as to reach the has strong global search ability,at the end of the WSN routing optimization problem solving.Experi －ments show that,this method effectively improves the utilization efficiency of node energy.Key words:wireless sensor;simulated annealing algorithm;routing

收稿日期：2012-03-23

基金项目：江苏广播电视大学、江苏城市职业学院“十二五”规划课题（12SEW-C-112）。

作者简介：袁桂霞（1978-），女，江苏海安人，讲师，硕士，研究方向：人工智能及网络信息系统与安全。

无线传感器网络高效通信的基础[1]是完成信息在无线传感网络的传递，将信息从源节点发动到目标节点，具有多跳路由、动态拓扑的优点，但是开销大，是WSN 路由中的一大难点。目前针对这个问题，许多学者都提出了自己的改良算法[3]，

其中DD 算法是这些算法中比较经典的一种，是一个里程碑的标志，在很多的应用中都用到了这个算法[2]。

本文给出了基于模拟退火算法优化无线传感器方法。由于遗传算法具有全局快速收敛优点，同时利用遗传算法优化模拟退火算法[4]，加快模拟退火算法收敛速度，使其达到具有很强的全局搜索能力，最后对WSN 路由优化问题求解[5]。

1无线传感器能耗模型

在WSN 路由优化过程中，节点能量消耗主要消耗

于数据传输，节点传送距离为的bit 数据所消耗的能量

为：

E Tx （k,d ）=

E Tx-elec （k ）

+E Tx-amp

（k,d ）（

d）

E elec

×k+εamp

×k ×d 2

（d ≥d

0≥）

（1）

WSN 节点接收k bit 数据消耗的能量为：

E Rx （k ）=E Rx-elec （k ）（2）E Rx （k ）=E elec ×K

（3）

式中，

εamp 是信号放大器的放大倍数，E elec 表示发送电路和接受电路消耗的能量。在WSN 路由优化中，采用的接收、发送能理消耗模型如图1所示。

2改进的模拟退火无线传感器路由

算法

2.1模拟退火算法

模拟退火算法源于对固体退火过程的模拟，采用Metropolis 接受准则，并用一组称为冷却进度表的参数控制算法进程，依据Metropolis 准则接受新解，在搜索

第28卷第12期

2012年12月

科技通报

BULLETIN OF SCIENCE AND TECHNOLOGY

Vol.28No.12Dec.2012

科技通报第28卷

时既向“优化”的方向搜索，又按一定的概率接受“劣化”的方案，使算法有能力跳出局部极小区域，从而得到全局最优解或渐进全局最优解。

模拟退火算法是局部搜索算法的扩展。它不同于局部搜索之处是以一定的概率选择邻域中费用值最大的状态。理论上来说，它是一个全局最优算法。它与以往的近似算法相比，具有描述简单、使用灵活、运用广泛、运行效率高和较少受初始条件等优点，而且特别适合并行计算。模拟退火算法主要是针对固体在恒定温度下达到热平衡过程而提出的一种采样方法。由父代群产生子代群，然后从父代群和子代群中随机选取个体和，和竞争进入下一代的入选概率为：

p （i ）=

1f （i ）≥f （j ）

exp （f （i ）-f （j ）T

）f （i ）≤f （j ≤

）

（4）

p （j ）=

f （j ）≤f （i ）

1-exp （f （i ）-f （j ）T

）f （j ）≥f （i ≤

）

（5）T =aT

（6）

式中：

f （i ）、f （j ）为个体i 、j 的适应度，T 为温度值，a （0T 值乘以降温系数，以使T 值下降。

如果f （i ）≥f （j ），则个体i 以概率1入选，j 被淘汰；如果f （i ）j 以概率exp （f （i ）-f （j ）

T

被淘汰。随着迭代次数的增加，当温度T →0

时，有lim T →0

exp f i -f

j T →→

=0，这时个体i 、j 入选的概率为：

p （i ）=

1f （i ）≥f （j ）0f （i ）≤f （j ≤）（7）p （j ）=0f （j ）≤f （i ）1f （j ）

≥f （i ≤）

（8）

即在温度T →0时，个体i 、j 的竞争变为谁好谁入选，这实际上成为两两竞争。

2.2遗传算法优化模拟部分主要设计

（1）适度函数

适度函数是衡量个体优劣程度的标准，WSN 路径优化中的个体适应度函数为：

图1WSN 路由的能量消耗框图

Fig.1Block diagram of the energy consumption for WSN

routing

图2消耗能量对比

Fig.2Comparison of energy

consumption

156

第12期

SINEs 比例最大，其次为LINEs ，再次为LTRs 。通过进一步把TEs 细分为不同的家族，发现小鼠、裸鼹鼠、地松鼠和家兔基因组中，拷贝数最多的LINEs 家族均为L1。SINEs 家族则在不同物种见发生了特异性的扩张：小鼠中拷贝数最多的SINEs 为B1,裸鼹鼠和地松鼠中拷贝数最多的SINEs 家族为ID ，家兔拷贝数最多的SINEs 家族为C 。目前对小鼠中B1扩张的研究较多，已经证实B1SINEs 家族与某些基因表达有重要联系，例如，一项研究表明B1是中枢神经系统的压力诱导因子（stress-inducible factors ），人们推断其它SINEs 家族在物种中的扩张也与基因表达有着密切的联系，还有待进一步研究证实。总之，通过研究裸鼹鼠，地松鼠，

兔子基因组中的散在重复序列，比较4个物种中TEs 类别、拷贝数等，为理解重复序列在啮齿类动物中的进化提供了参考信息。

参考文献：

[1]

Kim E B ，et al .Genome sequencing reveals insights into physiology and longevity of the naked mole rat[J].Nature,2011，479：223-227.[2]

Kalkkila J P,et al .Cloning and expression of short inter －spersed elements B1and B2in ischemic brain [J].Eur J Neurosci.2004，19(5).

（上接第31页）

fitness （x ）=nx-1

i =1

ΣE a

i +1R β

i

n λx （9）

式中，i +1为节点选择的下一个节点，E a

i +1

表示节点i +1的剩余能量，

n x 表示x 的跳数。（2）选择操作

为了使比较优秀的个体进行下一代种群，通过选择操作保证了“适者生存、优胜劣汰”的群体进化现象，具体采用轮盘赌选择方式。个体x i 被选中的概率：

f （x i ）=fittness （x i

）size

j =1

Σx

j

（10）

式中，fittness （x i ）为x i 的适应度值。

（3）交叉算子

首先随机地从种群中选择两个个体，然后交换个体交叉段，交叉位置根据保持父体中节点的相对次序来确定。例如，设两个交叉个体为A 1和A 2，交叉后，得到的两新个体如图具体如下：

B 1=（254|8167|93）B 2=（452|7368|91）

3仿真实验分析

为验证本文提出的WSN 路由优化算法有效性，在

matlab 实验环境下，任取100个传感器节点，进行随机分布，采用的基本算法有遗传算法和模拟退火算法。

τmax =200，τmin =4，交叉概率为0.7，变异概率为0.01，ρ=0.2，a=1.2,β=2，最大迭次为200。为了保证本实验提出的算

法的较低的耗能性，选取不同情况下的能量进行统计，得出如图2所示的能量图。

从图2可知，随着传感器节点的增加，全部算法能量消耗都增加，其中混合计算智能算法能量消耗平均增长速度最慢，增长的幅度较小，对比结果表明混合计算智能算法减少住处广播能耗，有效提高了能量利用效率，使整个网络能量更加均衡，提高了路由可靠性，延长了WSN 寿命。

4结论

本文提出的算法加快了路由选择的速度，有效降

低能量消耗，减少了数据传输的时延，整个WSN 网络生命周期得到延长，同时相对于单一遗传算法和模拟退火算法，网络能量更加均衡，提高了节点能量利用效率。

参考文献:

[1]

I F Akyildiz,W Su,Y Sankarasubramanian,E Cayirci.A Survey on Sensor Networks [J].IEEE Communications Magazine,2002,40(8):102-114.[2]任丰原,黄海宁,林闯.无线传感器网络[J].软件学报,2003,14(7):1282-1291.

[3]

K Akkaya,M Younis.A Survey on Routing Protocols for Wireless Sensor Networks [J].Ad Hoc Networks.2005,3(3):325-349.[4]于海滨.智能无线传感器网络系统[M].北京:科学出版社,2006.

[5]

缪强,郑扣根.无线传感器网络路由协议设计研究[J].计算机应用研究,2004,21(8):33-35.

袁桂霞.模拟退火算法优化无线传感器网络路由技术

157