检索结果-南通市图书馆

移动传感器网络中最少数量-罚时路径扫描覆盖问题研究

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

计算机工程 2022年

作者：缪欣陈璇鲍红莹张静轩余炜华东理工大学数学学院华东理工大学商学院

作为无线传感器网络中的一个重要应用，扫描覆盖通过规划移动传感器对区域内兴趣点（Point of Interest，POI）进行定期覆盖，从而相对传统覆盖方法以更低廉的成本实现对POI的监测。研究最少数量-罚时路径扫描覆盖问题，即调度移动传感... 详细信息

作为无线传感器网络中的一个重要应用，扫描覆盖通过规划移动传感器对区域内兴趣点（Point of Interest，POI）进行定期覆盖，从而相对传统覆盖方法以更低廉的成本实现对POI的监测。研究最少数量-罚时路径扫描覆盖问题，即调度移动传感器扫描给定路径上的POI集合，使其耗用成本以及产生的POI总罚时成本之和最小。首先将问题刻画为整数规划，其次，由于整数规划只能高效求解中小规模实例，故基于该问题的特殊结构设计了复杂度为O(m;n;)的贪心算法和O（MAXGEN×Nnlogn）的遗传算法求解大规模实例。为增加求解质量，提高算法局部寻优能力，在遗传算法基础上引入模拟退火操作设计了遗传模拟退火算法，其复杂度为O(MAXGEN×Nnlogn×logT;/T;)。最后，通过仿真实验分析以上算法的实际性能。实验结果表明，三种算法均有较好的收敛性，贪心算法求解质量相对较差，但求解速度快；遗传算法解的质量更好，但存在不稳定的问题，局部寻优能力较弱；遗传模拟退火算法，局部寻优能力和求解稳定性明显增强，解的质量优于以上算法。

关键词：无线传感器扫描覆盖整数规划贪心算法遗传算法模拟退火

基于兴趣点分类的无线传感器网络扫描覆盖机制

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

西南交通大学学报 2014年第1期49卷 165-172页

作者：舒莉林锋刘中豪游健周激流四川大学计算机学院四川成都610065

针对无线传感器网络中的扫描覆盖问题,建立了同时满足兴趣点覆盖需求和数据投递要求的扫描覆盖数学模型,并通过与组合覆盖中经典的车辆路径问题类比分析,证明了该问题是NP-hard问题.在此基础上,提出了一种基于兴趣点分类的扫描覆盖机制F... 详细信息

针对无线传感器网络中的扫描覆盖问题,建立了同时满足兴趣点覆盖需求和数据投递要求的扫描覆盖数学模型,并通过与组合覆盖中经典的车辆路径问题类比分析,证明了该问题是NP-hard问题.在此基础上,提出了一种基于兴趣点分类的扫描覆盖机制FCSC(FDBSCAN_clustering_based sweep coverage).该机制利用FDBSCAN聚类算法,根据兴趣点位置信息将兴趣点分类,针对每类兴趣点,利用启发式算法生成移动传感器节点对兴趣点的访问路径,完成数据采集.仿真结果表明,在相同的网络场景下,相较于传统的扫描覆盖机制,提出的机制有效地降低了算法复杂度,节约了50%以上的算法运行时间.

关键词：无线传感器网络覆盖机制扫描覆盖聚类分析启发式算法

在线全文

学校读者我要写书评

暂无评论

基于目标分层和路径分割策略的扫描覆盖算法

计算机工程 2020年第11期46卷 231-237,245页

作者：张景昱刘京菊叶春明国防科技大学电子对抗学院合肥230037

针对带有权重目标和返回时间约束的扫描覆盖问题,提出一种基于目标分层和路径分割的区域覆盖算法TLPS。通过分析所有目标的位置和权重信息,将目标抽象成一系列的点目标并计算基站位置,分层提取不同权重的节点,基于贪心策略计算相同层次... 详细信息

针对带有权重目标和返回时间约束的扫描覆盖问题,提出一种基于目标分层和路径分割的区域覆盖算法TLPS。通过分析所有目标的位置和权重信息,将目标抽象成一系列的点目标并计算基站位置,分层提取不同权重的节点,基于贪心策略计算相同层次间点目标集的TSP路径。在此基础上,设计一种针对权重节点的环路分割策略,对TSP路径进行再分割处理以得到最终扫描路径。实验结果表明,相对tcwtp、OSweep等算法,TLPS算法能够在增加少量传感器节点的情况下缩短平均扫描周期,提高目标覆盖效率和路径有效率。

关键词：无线传感器网络扫描覆盖 TSP问题目标分层路径分割

在线全文

学校读者我要写书评

暂无评论

移动传感器网络中路径扫描覆盖问题研究

计算机工程 2022年第12期48卷 150-155,164页

作者：缪欣陈璇鲍红莹张静轩余炜华东理工大学数学学院上海200237 华东理工大学商学院上海200237

扫描覆盖作为无线传感器网络中的重要应用之一,通过规划移动传感器对区域内兴趣点(POI)进行定期覆盖,因此相较于传统覆盖方法能以更低廉的成本监测POI。研究最少传感器数量-最小罚时路径扫描覆盖问题,即通过调度移动传感器扫描给定路径... 详细信息

扫描覆盖作为无线传感器网络中的重要应用之一,通过规划移动传感器对区域内兴趣点(POI)进行定期覆盖,因此相较于传统覆盖方法能以更低廉的成本监测POI。研究最少传感器数量-最小罚时路径扫描覆盖问题,即通过调度移动传感器扫描给定路径上的POI集合,使传感器使用数量及产生的POI总罚时成本之和最小。将该问题转换为整数规划,并基于该问题的特殊结构设计贪心算法和遗传算法,以求解大规模实例。在遗传算法基础上引入模拟退火操作,以设计一种遗传模拟退火算法,从而提高求解质量和算法局部寻优能力。实验结果表明,所提贪心算法、遗传算法及遗传模拟退火算法均有较好的收敛性,贪心算法求解质量相对较差,但求解速度快;遗传算法解的质量更好,但存在不稳定的问题,局部寻优能力较弱;遗传模拟退火算法的局部寻优能力和求解稳定性明显增强,解的质量优于其他两种算法。

关键词：无线传感器扫描覆盖整数规划贪心算法遗传算法模拟退火

在线全文

学校读者我要写书评

暂无评论

感知受限的移动传感器节点扫描覆盖优化算法

计算机应用 2017年第1期37卷 60-64,102页

作者：神显豪李军奈何广西高校嵌入式技术与智能信息处理重点实验室(桂林理工大学) 广西桂林541004

移动无线传感器网络(WSN)的应用中,因为传感器节点的感知范围受限,其覆盖分析就是一个针对目标区域的扫描覆盖问题。提出了一种基于多目标优化的扫描覆盖算法。在目标区域中,采用双目标优化策略对单个移动传感器节点进行路径规划,一方... 详细信息

移动无线传感器网络(WSN)的应用中,因为传感器节点的感知范围受限,其覆盖分析就是一个针对目标区域的扫描覆盖问题。提出了一种基于多目标优化的扫描覆盖算法。在目标区域中,采用双目标优化策略对单个移动传感器节点进行路径规划,一方面使节点的覆盖面最大化,另一方面使扫描覆盖的路径最短。仿真实验在含有障碍物和不含障碍物的情况下进行,与多节点的编队覆盖算法相比,所提算法在适度降低覆盖率的情况下,可大幅降低移动能耗。

关键词：移动传感器节点扫描覆盖双目标优化覆盖率能耗

移动传感器网络中的最大价值路径扫描覆盖算法

在线全文

学校读者我要写书评

暂无评论

运筹学学报 2019年第4期23卷 155-164页

作者：黄培煌朱文兴福州大学物理与信息工程学院福州350116 福州大学数学与计算机科学学院福州350116

扫描覆盖是当前移动传感器网络的一个重要覆盖技术,其主要通过规划移动传感器的巡逻路径对事件兴趣点(Points of Interest,POI)进行定期监测,从而以相对于普通覆盖方案更低廉的成本实现对POI监控.研究最大价值路径扫描覆盖,即使用移动... 详细信息

扫描覆盖是当前移动传感器网络的一个重要覆盖技术,其主要通过规划移动传感器的巡逻路径对事件兴趣点(Points of Interest,POI)进行定期监测,从而以相对于普通覆盖方案更低廉的成本实现对POI监控.研究最大价值路径扫描覆盖,即使用移动传感器扫描覆盖分布在一条路径上的POI集合,使得被覆盖POI的价值总和达到最大.首先设计了一个基于线性规划随机取整的近似算法,通过将问题松弛并刻画为一个线性规划,然后对线性规划最优解取整得到一个扫描覆盖方案.该算法可在O(mn^3.5L)时间内求解,并具有可证明的近似比1-1/e.其次,通过扩展基于贪心策略的集合覆盖算法,设计了一个时间复杂度为O(m^2n^2)的贪心算法,其主要思想为循环选取一个单位巡逻范围覆盖POI价值最大的传感器.为优化运行时间,基于MVSCP问题的特殊结构将算法时间进一步改进至O(m log m+mn^2).最后,通过仿真实验分析所设计算法的实际性能.实验结果表明,线性规划随机取整算法运行时间低至整数规划算法的百分之一,但其所求解的质量只略低于整数规划算法;改进的贪心算法虽然不具有可证明的近似比,但其实际所求解的质量并不弱于线性规划随机取整算法,并且具有三者中最佳的运行时间.

关键词：扫描覆盖线性规划贪心算法移动传感器

在线全文

学校读者我要写书评

暂无评论

基于不同扫描周期的传感网扫描覆盖算法研究

基于不同扫描周期的传感网扫描覆盖算法研究

作者：魏姗姗哈尔滨工业大学

学位级别：硕士

无线传感器网络是由大量静态或移动的传感器组成的无线网络,可用于感知、收集、处理和传输网络覆盖的地理区域内的传感对象的信息。在该网络中,使用少量的移动传感器覆盖更多的目标称为扫描覆盖。具体表述为:检测区域内存在携带信息的... 详细信息

无线传感器网络是由大量静态或移动的传感器组成的无线网络,可用于感知、收集、处理和传输网络覆盖的地理区域内的传感对象的信息。在该网络中,使用少量的移动传感器覆盖更多的目标称为扫描覆盖。具体表述为:检测区域内存在携带信息的兴趣点（POI,point of interest）,移动传感器结点须在兴趣点的扫描周期内通过移动到它的位置来收集兴趣点的携带信息。研究者在这一领域做了大量的研究工作,但大多忽略了兴趣点可能具有不同扫描周期,导致某些兴趣点会被频繁地覆盖,以至于超出它的扫描覆盖要求。这一研究也具有实际意义,例如,在熔炉的监测系统中,温度较高区域覆盖频率应更高,也就是它们的扫描周期应该更短。本课题基于国内外的研究现状,进一步研究基于不同扫描周期的传感网扫描覆盖算法,具体分为扫描周期不同的扫描覆盖算法和基于扫描周期的随机兴趣点扫描覆盖算法。本文提出了基于分组与贪心的FSweep算法和基于分组与迭代的USweep算法来解决扫描周期不同兴趣点的扫描覆盖问题。FSweep算法基于分组与贪心实现,以贪心的方式选取兴趣点得到最终分组,最后再利用TSP路径算法得到移动传感器结点的扫描覆盖路径;USweep算法将分组与迭代相结合,通过迭代的方式使分组中心更分散,从而得到更优的扫描覆盖路径。同时,该算法得到的多条扫描覆盖路径,其中每一条扫描覆盖路径所覆盖的POI具有相似的扫描周期。最后实验结果验证了FSweep与USweep算法对比其他算法所需要的移动传感器结点数目较少,并且通过分析两种算法可得,FSweep算法可用于对算法速度要求较高的环境,USweep算法可用于需要移动传感器数目最小化的环境。本文提出了基于分类的DSweep算法和基于相似度的RSweep算法来解决真实环境下随机兴趣点的扫描覆盖问题。DSweep采取随机分类方式,将生成结点放入距离最近的扫描覆盖路径中;RSweep算法定义多因素相似度,通过相似度来判断随机POI应该被哪一条扫描路径覆盖,从而更新扫描覆盖路径来覆盖到离散的POI。最后实验结果验证了FSweep与USweep算法能满足POI的随机性,并且所需要的移动传感器结点数量较其他算法较小。

关键词：无线传感器网络扫描覆盖扫描周期兴趣点

距离限制下移动无线传感扫描覆盖问题的近似算法

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

距离限制下移动无线传感扫描覆盖问题的近似算法

作者：梁建浙江师范大学

学位级别：硕士

无线传感网络中的覆盖问题一直在被探索和研究,近几年由于无人机的热潮,使得无线传感网络中的覆盖问题模型随着应用的变化也出现了相应的变化,即从要求对网络进行整体覆盖转变为要求对网络部分覆盖,从要求对网络长时覆盖转变为对网络周... 详细信息

无线传感网络中的覆盖问题一直在被探索和研究,近几年由于无人机的热潮,使得无线传感网络中的覆盖问题模型随着应用的变化也出现了相应的变化,即从要求对网络进行整体覆盖转变为要求对网络部分覆盖,从要求对网络长时覆盖转变为对网络周期性覆盖.伴随着无人机的热潮,实际应用中出现了许多移动无线传感器,相应的产生了扫描覆盖问题模型.无线传感网络中的移动无线传感器通常配有容量限制的电池设备,在下次充满电之前移动无线传感器的游走距离是有限的,基于这样的考虑本文定义了一系列距离限制下扫描覆盖问题.（1）距离限制下最少扫描覆盖问题是要找到最少数量的移动无线传感器及它们的路径规划,使得每一个静态传感器都能在每个需求时间段内至少被某一移动无线传感器访问一次,且每一个移动无线传感器在电量消耗完之前必须回到基站（假定每次充满电可游走的距离为D）.一个基站时,我们给出了一般图上的一个渐进αβ/β-2-近似算法和树状图上的2近似算法,其中α是旅行推销员问题的近似比,D/lmax,lmax是离基站最远点与基站间的距离;多个基站时,我们给出了 kγ-近似算法,其中γ是一个基站时的近似比.（2）给定移动无线传感器的数量,最小扫描周期覆盖问题是要找到移动无线传感器的分配和路径规划,使得其满足距离限制且静态传感最大的扫描需求时间要尽可能小.如果事先已知路径规划,我们给出了对应的分配方式并证明了其最优性;若未给定路径规划,我们给出了一般度量上的渐进k2 αβ/β-2-近似和树度量上的2k2-近似.（3）针对距离限制屏障扫描覆盖问题,把原有近似比从13/3提高到3.

关键词：距离限制扫描覆盖车辆路线问题近似算法

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

无线传感器网络中扫描覆盖问题研究

无线传感器网络中扫描覆盖问题研究

作者：刘闯哈尔滨工业大学

学位级别：硕士

近年来,无线传感器网络(Wireless Sensor Networks,WSNs)一直是热门的研究领域之一,相关的技术发展迅速,已经广泛应用于环境检测、智能家居以及安全防护等领域中。在无线传感器网络中覆盖问题是一类十分重要的问题。在某些监测任务中,... 详细信息

近年来,无线传感器网络(Wireless Sensor Networks,WSNs)一直是热门的研究领域之一,相关的技术发展迅速,已经广泛应用于环境检测、智能家居以及安全防护等领域中。在无线传感器网络中覆盖问题是一类十分重要的问题。在某些监测任务中,传感器结点不需要对兴趣点(Point Of Interest,POI)进行不间断地监测,只需要每隔一段时间进行一次数据采集便可满足要求。这样就可以利用少量的移动传感器结点去覆盖更多的目标,这种覆盖模式被称为扫描覆盖。研究人员在无线传感器网络中的扫描覆盖问题方面做了许多研究工作,但这些研究工作中,缺乏对收集数据后返回基站这个过程的研究。由于一些数据具有时效性,这些数据返回基站的时间是非常重要的约束条件,也是一个非常值得研究的问题。此外,无线传感器结点通常都具有一定的通信范围,只要在这个范围内便可以进行数据的通信。但现有的研究工作通常都是假设只有当移动传感器结点与监测目标重合时才能进行数据传输,不符合实际情况。本文针对现有研究工作的以上两点不足,分别研究了带返回时间约束的扫描覆盖问题以及距离敏感扫描覆盖问题。针对带返回时间约束扫描覆盖的研究工作,提出了带返回时间约束的扫描覆盖中最小化移动传感器结点数目问题,并且分析了该问题的NP难度,并且提出了两个启发式的算法G-MSCR和Min DExpand来解决这个问题。其中G-MSCR算法对返回时间控制得更为严格,而Min D-Expand算法侧重于在满足返回时间约束的条件下减少移动传感器结点数目。而在针对距离敏感扫描覆盖的研究中,首先阐述了在扫描覆盖问题中通信距离带来的影响,然后分析了距离敏感的扫描覆盖问题,最后提出了Circle Expand算法,该算法通过划分区域并覆盖这些区域来达到对POI的扫描覆盖。此外,本文实现了所提出的算法,并且在利用The ONE模拟器在模拟实验中通过与现有的最新方法进行比较来评估这些算法。在带返回时间约束的扫描覆盖问题中,传统扫描覆盖算法所需的返回时间要多于返回时间约束,也就是说传统扫描覆盖算法无法满足返回时间约束,而G-MSCR算法和Min D-Expand算法均可在约束内完成扫描覆盖。两个算法的不同在于G-MSCR需要更多的移动传感器结点并且将返回时间控制得更低。而在距离敏感的扫描覆盖问题中,由于CircleExpand算法考虑了移动传感器结点的通信范围,在所需的移动传感器结点方面,Circle Expand算法比已有的算法表现要好。

关键词：无线传感器网络扫描覆盖移动传感器结点