基于改进模拟退火算法的无线传感器布设
- 文档名称：基于改进模拟退火算法的无线传感器布设
- 文档关注次数：474
- 文档格式：纸质版或者PDF电子版（用Acrobat Reader打开）或Word版本doc格式
- 文档大小：263KB
- 上传者：qazwsxedc
- 添加时间：2019/05/05
- 内容摘要：
通信论坛
计算机与创新生活ww(53
基于改进模拟退火算法的无线传感器布设
戎纪光1马培埓1王晋2
(1中国电子科技集团公司第五十四研究所石家庄050081)
(2武警石家庄指挥学院石家庄050061)
摘要对子已被证明是组合优化问题的无线传感器布设而言,模拟退火算法是一种有效的解决方法。在生成无绒传感器
布设方彙的过程中,针对传统模拟退火算法的缺陷,采用了保存当前最优布设方策及灵活设置退火温度的改进算法来生成布设
方紫,并给出了使用被算法的无线传感器布设方策生成流程及算法伪码。最后逼过仿真实验验证了改进算法在生咸无传感
器布设方案过程中的可行性和有效性
关词模拟退火算法无銭传感器布设组合优化探测能力
中图分类号:TP311文献标识码:A文章编号:1008-1739(2011)08-53-04
Wireless Sensor Node Placement Based on Modified Simulated
Annealing Algorithm
RONG Jiguang, MA Peibo WANG Jin
(1. The 54th Research Institute of CETC, Shijiazhuang Hebei 050081, China
(2. Shijiazhuang Commanding Colle e of CAPF, Shijiazhuang Hebei 050061, China)
Abstract: Simulated annealing al orithm is an efficient approach for wireless sensor node placement which has been proved to be
a combinator al optimization prom By akin in the consideration of the limitations of the traditional simulated annealing
algorithms in the generation process of wireless sensor layout, the layout scheme is generated by saving the current optimal layout and
flexibly seting annealing temperature. The wieless sensor layout scheme generation flow and a m pseudocode which uses this
ago t hm are g e T xx e o a m has een demonstrated to be practical and efficient
ey words: SA algorithm, wireless sensors placement combinatoral optimization, capability of etection
1引言
退火算法是一种基于物理退火过程的启发式的随机搜索方
法,在搜索的迭代过程中,不仅接受目标函数好”的结果,还
对于无人值守的区域监控而言,布没分布式无线传感器能够根据 Metropolis transition y法列,以一定的概率接受坏"的
是一种有效的手段,但由于成本、环境等条件的制约,传感器
结果,从而获得全局最优解。
布设是否合理就成为直接影响着监控结果准确性和全面性的
重要因素。在无线传感器布设中,通常是将待监控的区城划分2改进算法
成大小相同的若干网格,传感器布设在网格中的某些节点上,
通过计算传感器对网格中各节点的监控覆盖能力,来判别布
最然模拟退火算法可以跳出局部最优解,找到全局最优
设方案的好坏
或近似全局最优解,但还是存在缺点:①送代次数过多:在変
无线传感器布设问题已被证明是一种组合优化问题,而
量多、目标函数复杂时,为了得到一个较好的近似解,初始温
由 Kirkpatrick将物理退火过程引入组合优化领域而产生模拟
度T需从一个较大的值开始,并对每一次的降温T执行多次
退火算法作为一种有效的非线性组合优化算法,已在理论上的 Metroplis算法;⑨初始温度T及降温步长较难确定:若是
被证明是严格的,在实际应用中也被证明是有效的叫?。模拟
T选择过大,降温步长过小,虽然最终得到较好的近似解,但
定稿日期:2011-03-26
算法收敛的速度太慢,若是T的初值选择较小,降温步长过
2011年第08期《计算机与网络》
万方数据
通信论坛
4)ctc计算机与网条创新生活
大,很可能得不到较好的近似解;③搜索过程中由于执行概率 maxstep:退温次数, acceptnum:抽样过程中新方案被采纳的次
接受环节而遗失当前遇到的最优解
数。约束条件
针对模拟退火算法的这些缺点,提出一种改进算法,通过
ad≤y,Vk∈S,ieG,i≠k
保存当前最优解及设置双温度阈值来,减少抽样次数,提高传
感器布设算法的计算效率。
Vik X]
,Vk∈S,ieG,i=k,
21改进方法
通过对模拟退火鏱法进行分析可知,由于全局收敛添加
难以实现,造成实际过程中往往得到的是近似最优解,该解可Vk,y=1or0,Vk∈S,i∈G
能会比中间结果更差,且降低了搜索效率。为了避兔概率接收
环节而遗失当前的"asoF'的结果,在布设方案搜索过程3算法实现
中增加记忆功能,记录当前最优解并更新。
为了提高搜索效率,采用一种新的温度更新方法:在某
31基本流程
温度下,若形成的布设方案被接受的次数较多,则降温的幅度
无线传感器布设的基本流程见图1所示。
应该增大,否则則,降温幅度应该减小,以保证在温度更新时有
定的自适应性。设置温度双國值后,使得在不遗失最优解的
划分探测区城初始化退
情况下,降低计算量,既在各温度下当前状态连续保持不变则
火温度等相关参媺
认为 Metropolis抽样稳定,若连续退温过程中所得的最优解均
将当前湿度及布设方案作
不变则认为算法收斂。
为初始抽样数
需要指出的是,上述改进是对退火方式的改变,而算法所
计算当前布设方案的
采用的广义 Boltzmanngibbs分布接收概率及 Metropolis准则
探能力
并没有改变,模拟退火算法之所以能够成为全局搜索算法,其
机移去一传感路计算
接受概率方式及 Metropolis准则是其精隨,因此上述的改变没
新布设方案的探能力
有影响其精。
2.2传感器布设模型
断是否要方、否、英同原有方
更新相关参效
将监控区域圳分成若干网格,并为网格中的每一个节点
定义一个传感器探测能力的向量V,以表示所布设的传感器是
保存新方察更新相关参数
否能够探测到该节点(若能探测到则为1,否则为0)的能力。
在该算法中设置如下相关参数
否
抽样过程是否结束
S=(1,2,mn:布设传感器位置集合
是
G=(1,2,…n}:网格节点,mn
降严过程是否结京
両:位置点i和j间的欧几里德距离,2,jeG
rk:布设在k点上的传感器的探测半径,k∈S
否