无线传感器网络中的能量优化与路由算法研究

基于遗传算法的无线传感器网络覆盖算法优化研究　

李娴刑萧飞　中南大学信息科学与Ｘ－程学院湖南长沙４１００８３　

【摘要】本文将遗传算法运用到无线传感器网络覆盖的中，通过研究遗传算法的杂交和变异算子，得到具有混合杂交和间歇变异的改进遗传算法，　用于解决高密度部署的无线传感器节点集的选择问题，从而得到最优覆盖节点集　仿真实验表明该优化机制能更有效地跳出局部最优，获得更精确　的结果，从而更有效的实现了无线传感器网络布局的全局优化。　【关键词】无线传感器网络遗传算法最优覆盖节点集　中图分类号：ＴＰ２１２．９文献标识码：Ｂ文章编号：１００９—４０６７（２０１３）０４—６６—０２　

引言　无线传感器网络（Ｗｉｒｅｌｅｓｓ　Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋｓ，ＷＳＮｓ）是普适计算的　

重要研究领域。集成有传感部件、微处理器和通信模块的微型传感器节　

点通过自组织的方式构成无线传感器网络，完成对环境的数据采集和监　测。无线传感器网络逐渐成为工业界及学术界的一个研究热点，在军事　

和民用领域有着非常广阔的应用前景。无线传感器网络的覆盖是指通过　

所有节点能够对整个目标区域进行监测，从而达到信息采集的目的。本　

文在比较相关网络覆盖算法的基础上，提出基于遗传算法的优化覆盖算　法。　１、相关研究　

（１将这一部分改为相关工作介绍，去掉其子章节标题．２在介绍相　

关论文时，要引用该文献，并在最后给出参考文献信息。３．引用本问题　权威期刊三年内的论文。）　将本段合并到引言部分　

无线传感器网络的覆盖控制问题，即在保证一定服务质量（ＱｏＳ）条　件下，达到网络覆盖范围最大化，保证无线传感器节点有效地覆盖被监　测的区域或目标。　

目前，关于无线传感器网络覆盖算法有很多，相关学者或研究者从　不同角度、使用不同方法提出不同的算法，具体有ＴｉａｎＤ算法、ＣＣＰ算　法、Ｃｈｉ　ｆｕ　Ｈｕａｎｇ算法和ＲＩＳ算法等。ＴｉａｎＤ算法是基于角度覆盖判定　

的覆盖保持的节点调度算法（Ｃｏｖｅｒａｇｅ　Ｐｒｅｓｅｒｖｉｎｇ　Ｎｏｄｅｓ　Ｓｃｈｅｄｕｌｉｎｇ　Ｓｃｈｅｍｅ，简称ＣＰＮＳＳ），其采用张开角方式判断覆盖，每个节点在考虑　是否被覆盖时只考虑与其距离不大于探测半径的节点，计算出的冗余节　

第３１卷第５期（上）　２０１５年５月　赤峰学院学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｈｉｆｅｎｇ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　Ｖ０１．３ｌ　Ｎｏ．５　Ｍａｖ２０１５　

基于蚁群优化算法的无线传感器网络路由研究　

宋　杰，吴　勇，陈明明　

（安徽大学　计算机科学与技术学院，安徽合肥２３０６０１）　

摘要：无线传感器网络是一种能量、资源受限的网路系统，实现网络中节点能量使用均衡延长整个网络的生命周期是　无线传感器网络路由设计的重要目标．本文在基本蚁群算法在无线传感器网络应用的基础之上提出了几点改进策略．将节点　现有的能量水平作为计算转移概率的务件之一。使优秀路径上的节点在网络中存在的时间更长．将节点的位置信息作为计算　转移概率的条件，通过将位置信息写入转移概率中。使节点在搜索路径时具有方向性．最后本文利用ＭＡＴＬＡＢ工具对改进的　策略进行了实验仿真，并将结果和原始的ＡＣＯ算法进行比较分析，仿真结果显示改进策略在延长节点的生命周期，维持网络　能量均衡方面比其他俩种算法具有一定的提升．　关键词：无线传感器网络；蚁群算法；能量均衡；路由协议　中图分类号：ＴＰ３９３　文献标识码：Ａ　文章编号：１６７３—２６０Ｘ（２０１５）０５—００１３—０３　

１　Ｓｌ言　随着传感技术、无线通信技术和嵌入式技术的不断发　

展成熟，无线传感器网络逐渐成为当今社会的研究热点．它　强大的感知能力、自组织能力、部署方式简单方便的特点决　

定了在很多领域都有广阔的应用前景㈦．由于无线传感器网　络中节点的能量受限，将传统的网络协议应用到无线传感　器路中不太现实．近年来，许多学者对无线传感器网络路由　

做出了大量的研究翻．　无线传感网最初的雏形是起源于上个世纪７０年代，当　

时的技术仅处于初始的研制阶段，此时的网络采用点对点的　传输，而且传感器节点只具有简单的数据获取能力．８０年代　左右，无线传感网技术己经慢慢发展起来，该网络采用串／并　口方式与控制中心相连，并且传感器节点具有了获取各种不　

２０１５年第１期　计算机与现代化　ＪＩＳＵＡＮＪＩ　ＹＵ　ＸＩＡＮＤＡＩＨＵＡ　总第２３３期　

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

能量均衡的无线传感器网络节点路由算法　

唐翠微　

（雅安职业技术学院，四川雅安６２５０００）　

摘要：为了提高无线传感器网络的生存时间，提出一种能量均衡的无线传感器网络节点路由算法。首先利用能量阈值和　节点剩余能量将节点归类为２个区域，使得不同区域的节点当选为本轮簇头节点的概率不同，在数据稳定传输阶段，簇　

头与基站之间采用单跳与多跳相结合的通信方式，最后采用仿真实验测试算法的性能。结果表明，本算法有效提高了网　

络的能量利用率，能够实现节点之间的能耗均衡，使无线传感器的网络生存时间得到延长。　关键词：非均匀分簇；无线传感器网络；能量效率；网络寿命　中图分类号：ＴＰ３９１　文献标识码：Ａ　ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００６—２４７５．２０１５．Ｏ１．０２１　

Ｃｌｕｓｔｅｒｉｎｇ　Ｒｏｕｔｉｎｇ　Ａｌｇｏｒｉｔｈｍ　ｏｎ　Ｗｉｒｅｌｅｓｓ　Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋｓ　Ｂａｓｅｄ　ｏｎ　Ｅｎｅｒｇｙ　Ｑｕａｌｉｚａｔｉｏｎ　

ＴＡＮＧ　Ｃｕｉ．ｗｅｉ　

（Ｙａ’ａｎ　Ｖｏｃａｔｉｏｎａｌ　Ｃｏｌｌｅｇｅ，Ｙａ’ａｎ　６２５０００，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｉｎ　ｏｒｄｅｒ　ｔｏ　ｐｒｏｌｏｎｇ　ｔｈｅ　ｌｉｆｅ　ｏｆ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋ，ａ　ｎｏｖｅｌ　ｃｌｕｓｔｅｒｉｎｇ　ｒｏｕｔｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｐｒｏｐｏｓｅｄ　ｉｎ　ｗｉｒｅｌｅｓｓ　ｓｅｎ—　ｓｏｒ　ｎｅｔｗｏｒｋｓ　ｂａｓｅｄ　ｏｎ　ｅｎｅｒｇｙ　ｅｑｕａｌｉｚａｔｉｏｎ．Ｆｉｒｓｔｌｙ，ｔｈｅ　ｎｅｗ　ａｌｇｏｒｉｔｈｍ　ｃｌａｓｓｉｆｉｅｓ　ｎｏｄｅｓ　ｉｎｔｏ　ｔｗｏ　ａｒｅａｓ　ｂｙ　ｕｓｉｎｇ　ｅｎｅｒｇｙ　ｔｈｒｅｓｈｏｌｄ　ａｎｄ　ｒｅｍａｉｎｉｎｇ　ｅｎｅｒｇｙ　ｏｆ　ｎｏｄｅｓ，ｗｈｉｃｈ　ｍａｋｅｓ　ｎｏｄｅｓ　ｌｏｃａｔｅｄ　ｉｎ　ｄｉｆｅｒｅｎｔ　ａｒｅａｓ　ｈａｖｅ　ｄｉｆｆｅｒｅｎｔ　ｐｒｏｂａｂｉｌｉｔｉｅｓ　ｏｆ　ｂｅｉｎｇ　ｅｌｅｃｔｅｄ　ａｓ　ｃｌｕｓｔｅｒ　ｈｅａｄ　ｎｏｄｅｓ．Ｉｎ　ｔｈｅ　ｓｔａｇｅ　ｏｆ　ｄａｔａ　ｓｔａｂｌｅ　ｔｒａｎｓｍｉｓｓｉｏｎ，ｃｌｕｓｔｅｒ　ｈｅａｄｓ　ａｎｄ　ｔｈｅ　ｂａｓｅ　ｓｔａｔｉｏｎ　ｕｓｅ　ｃｏｍｂｉｎｅｄ　ｓｉｎｇｌｅ—ｈｏｐ　ａｎｄ　ｍｕｌｔｉ—ｈｏｐ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　ｍｏｄｅ．Ｆｉｎａｌｌｙ，ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｅｘｐｅｒｉｍｅｎｔ　ｉｓ　ｕｓｅｄ　ｔｏ　ｔｅｓｔ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ．Ｔｈｅ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｅｆｆｅｃｔｉｖｅｌｙ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｎｅｔｗｏｒｋ　ｅｎｅｒｇｙ　ｅｆｆｉｃｉｅｎｃｙ　ａｎｄ　ａｃｈｉｅｖｅ　ｅｎｅｒｇｙ　ｃｏｎｓｕｍｐｔｉｏｎ　ｂａｌａｎｃｅｄ　ａｍｏｎｇ　ｎｏｄｅｓ，　ＳＯ　ｉｔ　ｃａｎ　ｐｒｏｌｏｎｇ　ｔｈｅ　ｌｉｆｅ　ｏｆ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋ．　Ｋｅｙ　ｗｏｒｄｓ：ｕｎｅｖｅｎ　ｃｌｕｓｔｅｒｉｎｇ；ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋ；ｅｎｅｒｇｙ－ｅｆｆｉｃｉｅｎｔ；ｎｅｔｗｏｒｋ　ｌｉｆｅ　

2018年 软 件 2018, Vol. 39, No. 1 第39卷 第1期 COMPUTER ENGINEERING & SOFTWARE 国际IT传媒品牌

基金项目: 国家自然科学基金(61271007)；国家自然科学基金(60872157) 作者简介: 沙娓娓(1988)，女，汉族，硕士生，研究方向：无线通信技术。通讯联系人: 刘增力(1966)，男，汉族，教授，研究方向：现代信号处理。 基于改进蚁群算法的无线传 感器网络的路由优化 沙娓娓1，刘增力2 （1. 昆明理工大学 信息工程与自动化学院，云南 昆明 650500；2. 昆明理工大学 民航学院，云南 昆明 650500） 摘 要: 结合无线传感器网络的特点，即能量有限，在无线传感网络路由中引入蚁群算法，并提出改进的IARA算法。在考虑节点的能量、传输方向和节点间距离等因素的基础上，结合Matlab仿真以及解析数值等方法，具体从如下几方面改进蚁群算法，其一启发函数；其二更新信息素；其三概率选择公式。通过仿真表明，该算法具有多方面优势，具体体现在能量消耗少以及生存周期长等方面。 关键词: 无线传感器网络；蚁群优化；路由算法 ；能量；生命周期 中图分类号: TP212.9 文献标识码: A DOI：10.3969/j.issn.1003-6970.2018.01.001 本文著录格式：沙娓娓，刘增力. 基于改进蚁群算法的无线传感器网络的路由优化[J]. 软件，2018，39（01）：0104 Optimization of Wireless Sensor Network Routing based on Improved Ant Colony Algorithm SHA Wei-wei1, LIU Zeng-li2 (1. Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China; 2. Faculty of civil aviation, Kunming University of Science and Technology, Kunming 650500, China) 【Abstract】: As the energy of sensor nodes in wireless sensor network (WSN) is limited, and colony optimization algorithm was applied to solve the routing problems in WSN, and an improved ant-based routing algorithm (IARA) was proposed. Considering the factors of nodes energy, transmitting direction, and distance between nodes, through numerical analysis and matlab simulation, the probabilistic selecting formula and the pheromone updating formula in the basic ant colony optimization algorithm is modified. The algorithm has many advantages, such as less energy consumption and long life cycle. 【Key words】: Wireless sensor networks (WSNs); Ant colony optimization(ACO); Routing algorithm; Energy; Life cycle 0 引言 无线传感器网络：指利用无线通信的方法，将微型传感器节点（被感知对象的内部、附件之中）组成多跳自组织网络，在环境监测、国家安全以及军事侦察等相关领域得以普遍应用[1]。传感器节点由电池提供能量，同时具有数量多、体积小等特点，一旦完成部署，即难以继续补充能量。所以在设计无线传感器网络路由协议时，要充分考虑节点能量问题，以延长网络生存周期达到传输大量数据的要求[2]。 Dorigo针对TSP的问题，提出全新的模拟进化算法——蚁群优化算法[3]。与此同时随着该算法的应用，有效解决指派、调度以及旅行商等各类优化组合问题[4]。 Kassabalidis等潜心多年研究，结合蚁群算法，提出Ant-Net算法[5]，该算法中蚂蚁主要可分为两大类：其一是具有收集节点信息作用的前向蚂蚁；其二为返回蚂蚁，将前向蚂蚁收集的信息，反馈在路由表之中。 Schoonderwoerd R等人通过概率选择和更新路径的方式，提出ABC算法[6]，此算法中蚂蚁从源节 第39卷 第1期 软 件