作为物联网的重要构成--无线传感器网络(Wireless Sensor Networks,WSNs)以其成本低廉、感知能力丰富和部署容易等特点得到了广泛的应用,极大地延伸了人类感知世界的深度与广度。然而在传统的静态传感器网络中,由于采用多跳转发的数据汇聚方式,汇聚节点(sink)周边的节点需要帮助其它节点向sink节点转发数据,因此在长时间运行之后会由于过载而失去效用,从而形成“能量空洞”。在无线传感器网络中使用移动sink可以大大缓解这一问题,移动sink可以在移动过程中以单跳或有限跳收集各个节点的数据,从而动态变换“热点”区域,平衡网络中的数据传输负载、节点能耗,提高节点能量使用效率,最终延长整个网络的生存时间。此外移动sink还具有帮助孤立节点与网络建立连接,改善网路连通性等优点。然而,由于移动sink载体的能量有限使其工作时间与移动里程受限,因此如何在能量有限的条件下最大化收集的数据量是目前研究中的焦点问题。解决这一问题的核心方法是为移动sink规划最短移动路径:在保证移动sink对整个网络覆盖的同时,路径长度最短,从而提高移动sink的能效,并减小节点数据收集时延。本文即针对这一最短路径规划问题,以提高算法适应性以及高效性为研究目标,对移动sink路径规划及相关算法进行了研究。本论文主要的研究内容以及创新点包括以下几个方面:第一,提出了一种无需测距信息的节点自身定位算法LLS-GRID(Linear Least Squares-GRID),提高了非均匀网络中的节点定位精度。移动sink路径规划的基本前提是对于网络中传感器节点分布情况的充分掌握,因此节点位置信息的获取是需要解决的首要问题。该定位算法不依赖于测距信息,因此不需要给节点添加测距相关设备;此外算法通过栅格划分以及锚节点筛选策略,大大降低了网络分布特性对节点自身定位算法效果的影响。仿真结果表明,该算法在均匀与非均匀网络中,都可以获得理想的定位效果,并且算法基于分区组合过程,在降低计算量的同时提高了定位精度,从而实现了多种网络环境下无需测距的高精度节点定位。第二,提出了一种基于信息收集点即汇聚点(rendezvous points,RP)筛选的移动sink最短路径规划算法,简化了路径搜索步骤,加快了路径搜索的速度。算法首先基于覆盖理论对移动sink信息收集点进行选择,简化可行解的搜索空间维度,并在传统遗传算法中使用可变长编码方式增加搜索灵活性,进而实现性能优良的移动sink路径规划。算法所规划的路径令所有节点能够以单跳方式向移动sink发送数据,去除了节点间多跳的数据转发过程,将节点能量使用效率最大化。仿真结果表明算法计算量小,能够为移动sink寻找到近似最优的信息收集路径。第三,提出了一种无信息收集点约束的移动sink路径规划算法,降低了对路径求解过程的约束,在更加广阔的解空间内对最佳路径进行搜索。在无信息收集点位置约束条件下,信息收集点的位置有无限种可能,每条可行路径上信息收集点的数量也无法预先估计,因此会大大增加问题求解难度。本文首次提出一种新颖的可变维度粒子群(Variable Dimension Particle Swarm Optimization,VD-PSO)移动sink路径规划算法,算法将每一个路径的可行解表达为一个变维度粒子,并且对每一个路径可行解中所途径的信息收集点位置以及数量都不进行任何约束,因此每个粒子的维度都可能不同。仿真结果表明,算法能够在无信息收集点约束的情况下,在整个传感器网络的部署区域内,计算出移动sink近似最优的巡游路径。第四,提出了一种VD-PSO算法的优化算法,解决了无信息收集点约束的移动sink路径规划算法中,由于路径解维度可变且复杂而导致的搜索时间长的问题。算法利用粒子即路径解之间的部分相似性,对邻近维度进行搜索、合并,在提高算法运行速度的同时提高了最终解的质量;同时算法引入了模拟退火思想,增强了粒子跳出局部最优解的能力。大量仿真结果表明,算法解决了无信息收集点约束情况下移动sink路径规划中全局最优解跟踪求精问题,大大提高了算法收敛速度,算法性能明显优于其他同类算法。