论文摘要
扫描覆盖是当前移动传感器网络的一个重要覆盖技术,其主要通过规划移动传感器的巡逻路径对事件兴趣点（Points of Interest,POI）进行定期监测,从而以相对于普通覆盖方案更低廉的成本实现对POI监控.研究最大价值路径扫描覆盖,即使用移动传感器扫描覆盖分布在一条路径上的POI集合,使得被覆盖POI的价值总和达到最大.首先设计了一个基于线性规划随机取整的近似算法,通过将问题松弛并刻画为一个线性规划,然后对线性规划最优解取整得到一个扫描覆盖方案.该算法可在O(mn3.5L)时间内求解,并具有可证明的近似比1-1/e.其次,通过扩展基于贪心策略的集合覆盖算法,设计了一个时间复杂度为O（m2n2）的贪心算法,其主要思想为循环选取一个单位巡逻范围覆盖POI价值最大的传感器.为优化运行时间,基于MVSCP问题的特殊结构将算法时间进一步改进至O（m log m+mn2）.最后,通过仿真实验分析所设计算法的实际性能.实验结果表明,线性规划随机取整算法运行时间低至整数规划算法的百分之一,但其所求解的质量只略低于整数规划算法;改进的贪心算法虽然不具有可证明的近似比,但其实际所求解的质量并不弱于线性规划随机取整算法,并且具有三者中最佳的运行时间.
论文目录
文章来源
类型: 期刊论文
作者: 黄培煌,朱文兴
关键词: 扫描覆盖,线性规划,贪心算法,移动传感器
来源: 运筹学学报 2019年04期
年度: 2019
分类: 基础科学,信息科技
专业: 数学,电信技术,自动化技术
单位: 福州大学物理与信息工程学院,福州大学数学与计算机科学学院
基金: 国家自然科学基金(Nos.61772005,61672005)
分类号: TP212.9;O221.1;TN929.5
DOI: 10.15960/j.cnki.issn.1007-6093.2019.04.014
页码: 155-164
总页数: 10
文件大小: 664K
下载量: 62
相关论文文献
- [1].几种典型无线传感器网络中的自身定位算法[J]. 巴音郭楞职业技术学院学报 2012(02)
- [2].浅析无线传感器网络技术的特点与应用[J]. 广东职业技术教育与研究 2019(06)
- [3].基于剩余能量的认知无线传感器网络频谱分配[J]. 传感技术学报 2019(12)
- [4].山区地形无线传感器网络覆盖机制研究[J]. 计算机产品与流通 2020(01)
- [5].无线传感器网络技术在物联网中的应用及其发展趋势[J]. 信息记录材料 2019(11)
- [6].无线传感器网络的异常检测[J]. 电子技术与软件工程 2019(24)
- [7].以实践能力为培养目标的“无线传感器网络”教学改革与实践[J]. 科技资讯 2020(01)
- [8].无线传感器网络技术在物联网中的应用及其发展趋势[J]. 海峡科技与产业 2019(07)
- [9].基于遗传算法的茶园无线传感器网络的优化方法[J]. 科学技术创新 2020(02)
- [10].可充电传感器网络能量管理策略研究[J]. 电子测试 2020(04)
- [11].通信类课程创新能力培养研究与改革——以“无线传感器网络”课程为例[J]. 教育教学论坛 2020(08)
- [12].无线传感器网络研究现状与应用[J]. 通信电源技术 2020(03)
- [13].基于无线传感器网络的桥梁结构健康监测设计研究[J]. 工程技术研究 2020(03)
- [14].基于ZigBee技术的矿用无线传感器网络的分析与设计[J]. 内蒙古煤炭经济 2019(19)
- [15].无线传感器网络在矿山环境监测中的应用研究[J]. 中国新通信 2020(06)
- [16].无线传感器网络中移动充电和数据收集策略[J]. 电子元器件与信息技术 2020(02)
- [17].无线传感器网络定位精度的优化研究[J]. 浙江水利水电学院学报 2020(02)
- [18].无线传感器网络在智能电网中若干关键问题的研究[J]. 中国新通信 2020(07)
- [19].无线传感器网络中基于邻域的恶意节点检测[J]. 湖北农业科学 2020(05)
- [20].无线传感器网络在煤矿安全智能监控系统中的运用[J]. 电子技术与软件工程 2020(08)
- [21].无线传感器网络发展应用[J]. 电脑知识与技术 2020(14)
- [22].异构分级式认知传感器网络分簇优化[J]. 产业与科技论坛 2020(09)
- [23].一种无线传感器网络感知覆盖空洞搜寻与修复方法[J]. 传感技术学报 2020(05)
- [24].无线传感器网络定位精度的优化研究[J]. 信息记录材料 2020(06)
- [25].无线传感器网络中能量问题研究进展[J]. 无线通信技术 2020(02)
- [26].无线传感器网络在工业网络中的应用研究[J]. 现代工业经济和信息化 2020(08)
- [27].新一代箭载无线传感器网络系统架构综述[J]. 宇航计测技术 2020(04)
- [28].无线传感器网络在船舶通信系统中的应用[J]. 舰船科学技术 2020(18)
- [29].无线传感器网络故障诊断分析与研究[J]. 科技视界 2020(31)
- [30].无线传感器网络的特点和应用[J]. 电子技术与软件工程 2019(04)