本文是一篇计算机论文，本文主要就WSN在覆盖和路由算法方面进行研究，在一些现有算法基础上进行优化。首先提出了CD-CS算法来确定传感器节点的部署情况，提高节点的覆盖率，然后提出了DCRUC算法来均衡节点能耗，提高网络的耐用性。
第一章 绪论
1.1 研究背景及意义
如今，物联网技术的开发热度高居不下，大家对技术的要求也越来越严苛[1]。人类已经不再简单局限于可以达到的环境，对于那些人类无法前往的复杂环境，也想去一探究竟，于是便提出了无线传感器网络（WSN，wireless sensor network）这一技术[2]。有了这项技术，人类可以更好地从物理世界获取需要的信息，更方便地做到现实生活的数字一体化。
WSN是一种由若干个传感器节点组成的智能网络，它根据人类需求部署在特地的领域内，进行数据收集、数据传输以及数据处理等功能，具有良好的自组织性[3]。它很好的改变了人类与物理的联系方式，在现实生活中的很多方面都产生了巨大的作用，如工业生产、军事监控、智能家居以及农业种植等方面[4]。每项技术都不是一提出来就十全十美的，都需要经过无数人的改进，才能被广泛应用。WSN也不例外，从这项技术被提出至今，历经无数研究人员的改良与更新，才演变成如今各方面都较为完善的科学技术。此过程可概括为三个阶段。
第一阶段为70年代，此时WSN刚刚形成，各方面都不是很完善。网络内节点数量很少，节点没有计算能力，只能进行简单的数据传输，由于功能不强，实际应用比较少；第二阶段为80年代到90年代，此时的WSN逐渐成熟，到了智能化阶段。网络内可以部署大量节点，并且节点功能也更加丰富，可以很好地应用于实际生活中；第三阶段就是90年代末至今，WSN已经发展的十分智能，具有很好的自组织性，部署变得十分简单，容错率也高了很多，并且节点具备多跳传输功能，可以更好分配各节点的任务负载，提高网络的耐用性，被广泛应用。
1.2 国内外研究现状
在WSN的发展至今，许多研究人员都致力于提高其覆盖能力。由于网络应用环境的不同，其覆盖要求也不尽相同，所使用的优化算法也需要针对具体的应用场景做出相应的调整。
文献[13]使用智能遗传算法来重新定位，以减少重叠，该算法相比普通的遗传算法使用时间更少，覆盖范围更大。文献[14]首先建立K覆盖的网络模型，然后以此模型为依据实现传感器节点之间的连接，并且使用传感器节点的调度机制来进行节点间的能量转换，实现节点间的能量均衡。文献[15]首先提出了一种基于连续最大流量法的检测算法去发现网络覆盖漏洞，然后使用改进的和声搜索算法去将覆盖漏洞进行修复。文献[16]提出了一种算法模型来提高节点的覆盖面积，主要根据节点的剩余能量和虚拟力来设计目标函数，提高模型效率。文献[17]则完全根据虚拟力的作用来实现节点的部署。首先利用算法计算出最佳目标路径，然后节点根据邻居节点的虚拟作用力和最佳路径的虚拟作用力的合力来进行部署，确定好位置后，再根据邻居节点的虚拟作用力来自主旋转，寻找最佳位置。文献[18]通过对蚁群算法进行改进，选择合适的传感器节点，实现改进算法位置的平衡，减少网络覆盖冗余，减少能源消耗，改善网络覆盖质量。
以上大部分算法的全局搜索性能都不够突出。在2009年，Xin-She Yang等人提出了一种元启发式布谷鸟算法[19]，用来解决优化问题。在算法的特别之处在于，布谷鸟在找鸟巢时会有一个淘汰概率，使布谷鸟在一个概率下放弃当前选择，转而以一个步长的距离在远处找最优解，以此避免局部最优，去搜索全局最优。在2017年，Yaoming Zhuang等人[20]首次提出将布谷鸟算法应用于WSN的覆盖优化问题中，取得了理想的效果。后来也有很多研究者在其基础上进行了优化。
第二章 无线传感器网络综述
2.1 无线传感器网络概述
2.1.1 无线传感器网络体系结构
一般来说，无线传感器网络体系由以下几种节点所组成，包括收集、融合、处理、发送数据的传感器节点、调度任务的任务管理节点、接收并汇总所有数据并连接到外部服务器的汇聚节点。具体如下图所示，传感器节点通常由飞机播撒，或人工部署在非人类的活动区域，然后通过自组织的形式智能地形成传感器网络进行监测任务。在网络工作时，会首先通过最初设定的算法选择簇头节点，然后普通节点收集周围的数据并发送给簇头节点，簇头节点接收后将其去重打包，然后发送给汇聚节点，最后传输至网络，人类便可以得到想要的数据了。如此，无线传感器网络的监测任务就完成了。
2.2 无线传感器网络覆盖算法概述
2.2.1 WSN覆盖的基本概念
传感器节点的覆盖问题是无线传感器网络领域重点研究的一个问题，监测区域的覆盖率越高，监测结果就越精确可靠。覆盖问题的实质就是如何保证在传感器节点的数量固定的情况来实现覆盖面积的最大化，或者是如何使用最少的传感器节点数量来实现监测区域的全部覆盖。
WSN的覆盖算法应该在满足要求的监测区域覆盖率的同时，尽可能地降低传感器节点的能耗，提高网络的耐用性。以下是一些WSN中覆盖问题的专业术语：
（1）节点的感知范围：传感器节点的感知范围是指节点在监测区域中所能感知到的最大范围，由其感知半径决定。这是节点的固有属性，一般不会发生变化。
（2）节点的通信范围：传感器节点的通信范围是指节点与其它节点能够进行数据传输的最大距离，由其通信半径决定，表现了节点间的连通性。
（3）网络覆盖率：无线传感器网络覆盖率是指监测区域内所有节点所能感知到的最大面积与总区域面积的比值，是衡量无线传感器网络优劣的标准之一。
（4）网络覆盖重数：在无线传感器网络中，如果某一块监测区域被k个节点覆盖了，那么该区域的覆盖重数就是k。
第三章 无线传感器网络的覆盖优化 .................................. 20
3.1 问题描述 .................................... 20
3.2 无线传感器网络系统模型 ........................ 21
第四章 无线传感器网络的路由优化 ............................ 32
4.1 问题描述 ..................................... 32
4.2 非均匀分簇路由算法 ................................... 32
第五章 总结与展望 ................................... 43
5.1 总结 ......................... 43
5.2 展望 ........................... 44
第四章 无线传感器网络的路由优化
4.1 问题描述
由于传感器节点体积小，所以携带能量较少。此外，无线传感器网络常常被应用于人类不方便前往的区域内，也就不能为节点补充能量。所以，需要尽量减少网络工作时的能量消耗，确保其能长时间运行。为了实现这一目标，需要设计性能良好的路由算法来提高节点的数据传输效率。
在所有的路由算法中，分簇路由算法由于其优秀的性能经常被采用。该算法最开始由W.B.Heinzelman等人提出，主要思想是将节点划分为若干个簇，以循环的方式随机选取簇头节点，普通节点收集数据并发送给簇头节点，然后簇头节点将其去重并打包给基站。但是由于簇头节点离基站的距离不同，距离近的簇头节点必然会承担过大的数据转发压力，导致其能量耗损过快，这一现象被称为“热点区域问题”，会影响整体网络的使用寿命。
在本章的主要内容为：
（1）介绍经典的非均匀分簇路由算法（EEUC）；
（2）分析EEUC算法的优劣，对其进行改进；
（3）做好仿真实验并进行结果比较。
第五章 总结与展望
5.1 总结
本文主要就WSN在覆盖和路由算法方面进行研究，在一些现有算法基础上进行优化。首先提出了CD-CS算法来确定传感器节点的部署情况，提高节点的覆盖率，然后提出了DCRUC算法来均衡节点能耗，提高网络的耐用性。对全文的总结如下：
本文首先在第一章介绍了无线传感器网络的研究背景及意义，并归纳了当前国内外的研究现状，最后列举了本文的主要工作内容以及结构安排。 然后在第二章里，首先对WSN相关概念进行概述，介绍了其节点结构、体系结构、特点和应用。然后针对其覆盖算法做了一些归纳，介绍了覆盖的基本概念、评价指标、分类状况以及空洞监测方式。最后针对其路由协议做了一些归纳，包括基本概念、性能指标和分类情况。
最后分别在第三章和第四章里，详细地叙述了对于覆盖和路由算法的优化算法。对于覆盖算法，本文选取了可以较好跳出局部最优解的布谷鸟优化算法为基础，对其寻优效率低，收敛速度慢以及跳出局部最优解效果不明显的缺陷，做出了一些改进。首先用动量梯度下降法和均方根法联合通过改变步长来加快布谷鸟算法的求解速度。然后用柯西变异因子可以很好的提升算法的全局检测能力，收敛精度和稳定度的特性，来使其更好地跳出局部最优解从而寻找全局最优解。最后通过仿真实验对比发现，若将传感器节点随机部署，覆盖率只有62.4%，而用本文提出的覆盖优化算法后，覆盖率可达93.1%。将此覆盖优化算法与CS算法和PCA-CS算法对比，也可以看出覆盖率有小幅提升。
参考文献（略）