无线视频传感器网络β-QoM目标栅栏覆盖构建算法

doi:10.11772/j.issn.1001-9081.2023010084

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (9): 2877-2884.DOI: 10.11772/j.issn.1001-9081.2023010084

无线视频传感器网络β-QoM目标栅栏覆盖构建算法

郭新明¹(), 刘蕊², 谢飞³^,⁴, 林德钰⁵

^1.咸阳师范学院计算机学院, 陕西咸阳 712000
^2.贵州警察学院计算机系, 贵阳 550005
^3.西安电子科技大学前沿交叉研究院, 西安 710071
^4.西安市智能康复人机共融与控制技术重点实验室(西京学院), 西安 710123
^5.南昌大学软件学院, 南昌 330047

收稿日期:2023-02-06 修回日期:2023-06-03 接受日期:2023-06-06 发布日期:2023-06-08 出版日期:2023-09-10
通讯作者: 郭新明
作者简介:刘蕊（1981－），女，贵州赫章人，副教授，硕士，主要研究方向：网络安全
谢飞（1984－），男，陕西咸阳人，研究员，博士，主要研究方向：人工智能、知识图谱
林德钰（1988－），男，江西吉安人，副教授，博士，主要研究方向：无线传感网络、物联网、雾计算。
基金资助:
国家重点研发计划项目(2022YFB4300701);国家自然科学基金资助项目(61973249);陕西省重点研发计划项目(2020NY-175);江西省自然科学基金资助项目(20224BAB212016);贵州省教育厅青年科技人才成长项目(黔教合KY字［2021］287);咸阳师范学院“学术带头人”资助项目(XSYXSDT202124)

β-QoM target-barrier coverage construction algorithm for wireless visual sensor network

Xinming GUO¹(), Rui LIU², Fei XIE³^,⁴, Deyu LIN⁵

^1.School of Computer Science，Xianyang Normal University，Xianyang Shaanxi 712000，China
^2.Department of Computer Science，Guizhou Police College，Guiyang Guizhou 550005，China
^3.Academy of Advanced Interdisciplinary Research，Xidian University，Xi’an Shaanxi 710071，China
^4.Xi’an Key Laboratory of Human-Machine Integration and Control Technology for Intelligent Rehabilitation （Xijing University），Xi’an Shaanxi 710123，China
^5.School of Software，Nanchang University，Nanchang Jiangxi 330047，China

Received:2023-02-06 Revised:2023-06-03 Accepted:2023-06-06 Online:2023-06-08 Published:2023-09-10
Contact: Xinming GUO
About author:LIU Rui， born in 1981， M. S.， associate professor. Her research interests include network security.
XIE Fei， born in 1984， Ph. D.， research fellow. His research interests include artificial intelligence， knowledge graph.
LIN Deyu， born in 1988， Ph. D.， associate professor. His research interests include wireless sensor network， internet of things， fog computing.
Supported by:
National Key Research and Development Program of China(2022YFB4300701);National Natural Science Foundation of China(61973249);Key Research and Development Program of Shaanxi Province(2020NY-175);Natural Science Foundation of Jiangxi Province(20224BAB212016);Youth Science and Technology Talent Development Project of Department of Education of Guizhou Province （Qian Jiao He KY［2021］287）, “Academic Leader” Project of Xianyang Normal University(XSYXSDT202124)

摘要/Abstract

摘要：

针对传统无线视频传感器网络（WVSN）目标栅栏因捕获图像宽度过小而导致的入侵检测失效问题，提出一个能确保捕获不小于β监测质量（β-QoM）的无线视频传感器网络β-QoM目标栅栏覆盖构建（WβTBC）算法。首先，建立视频传感器β-QoM区的几何模型，并证明了所有相邻视频传感器β-QoM区相交的目标栅栏捕获的入侵者图像宽度必大于等于β；然后，在对WVSN最优β-QoM目标栅栏覆盖建立线性规划模型的基础上，证明了它是一个NP-hard问题；最后，为了获得该问题的次优解，设计了一个启发式算法WβTBC。根据传感器间的逆时针β邻居关系建立WVSN的有向图，并采用Dijkstra算法在WVSN中搜索β-QoM目标栅栏。实验结果表明，WβTBC算法能有效构建β-QoM目标栅栏，且分别比螺旋外围外覆盖（SPOC）、螺旋外围内覆盖（SPIC）及目标栅栏构建（TBC）算法节省了23.3%、10.8%和14.8%的传感器节点。此外，在满足入侵检测要求的前提下，β值越小，WβTBC算法构建β-QoM目标栅栏的成功率越高，形成栅栏的节点越少，WVSN进行β-QoM入侵检测的工作周期越长。

关键词: 无线视频传感器网络, 目标栅栏, β图像宽度, 线性规划, 启发式算法

Abstract:

Focusing on the failure of intrusion detection resulted from low captured image width of traditional Wireless Visual Sensor Network （WVSN） target-barrier， a Wireless visual sensor network β Quality of Monitoring （β-QoM） Target-Barrier coverage Construction （WβTBC） algorithm was proposed to ensure that the captured image width is not less than β. Firstly， the geometric model of the visual sensor β-QoM region was established， and it was proven that the width of intruder image captured by the target-barrier of intersection of all adjacent visual sensor β-QoM regions must be greater than or equal to β. Then， based on the linear programming modeling for optimal β-QoM target-barrier coverage of WVSN， it was proven that this coverage problem is NP-hard. Finally， in order to obtain suboptimal solution of the problem， a heuristic algorithm WβTBC was proposed. In this algorithm， the directed graph of WVSN was constructed according to the counterclockwise β neighbor relationship between sensors， and Dijkstra algorithm was used to search β-QoM target-barriers in WVSN. Experimental results show that WβTBC algorithm can construct β-QoM target-barriers effectively， and save about 23.3%， 10.8% and 14.8% sensor nodes compared with Spiral Periphery Outer Coverage （SPOC）， Spiral Periphery Inner Coverage （SPIC） and Target-Barrier Construction （TBC） algorithms， respectively. In addition， under the condition of meeting the requirements of intrusion detection， with the use of WβTBC algorithm， the smaller β is， the higher success rate of building β-QoM target-barrier will be， the fewer nodes will be needed in forming the barrier， and the longer working period of WVSN for β-QoM intrusion detection will be.

Key words: Wireless Visual Sensor Network (WVSN), target-barrier, β Quality of Monitoring (β-QoM), linear programming, heuristic algorithm

中图分类号:

TP393

郭新明, 刘蕊, 谢飞, 林德钰. 无线视频传感器网络β-QoM目标栅栏覆盖构建算法[J]. 计算机应用, 2023, 43(9): 2877-2884.

Xinming GUO, Rui LIU, Fei XIE, Deyu LIN. β-QoM target-barrier coverage construction algorithm for wireless visual sensor network[J]. Journal of Computer Applications, 2023, 43(9): 2877-2884.

图/表 17

图1 WVSN感知模型

Fig. 1 WVSN sensing model

图2 WVSN部署范围示意图

Fig. 2 Schematic diagram of deployment scope of WVSN

图3 入侵者几何模型

Fig.3 Geometric model of intruder

图4 视频传感器图像监测失效示意图

Fig. 4 Schematic diagram of visual sensor image monitoring failure

图5 目标栅栏入侵行为检测示意图

Fig. 5 Schematic diagram of target-barrier intrusion behaviour detection

图6 视频传感器β-QoM区

Fig. 6 Visual sensor β-QoM region

图7 最优β-QoM目标栅栏覆盖

Fig. 7 Optimal β-QoM target-barrier coverage

图8 假β-QoM目标栅栏

Fig. 8 Fake β-QoM target-barrier

图9 逆时针β邻居

Fig. 9 Counterclockwise β neighbor

表1 实验平台的参数设置

Tab. 1 Parameter setting of experimental platform

参数	值	参数	值
L	900 m	γ	60°
W	150 m	β	10~30 m
r	100 m	网络部署规模	100~1 000

图10 WβTBC算法仿真结果

Fig. 10 Simulation results of WβTBC algorithm

图11 栅栏平均节点数对比

Fig. 11 Comparison of average nodes in barriers

图12 栅栏构建成功率对比

Fig. 12 Comparison of success rate of barrier construction

图13 平均构建栅栏数对比

Fig. 13 Comparison of average constructed barriers

图14 构建栅栏不同阶段的网络规模对比

Fig. 14 Comparison of network scales at different stages of barrier construction

图15 不同β的β-QoM目标栅栏构建成功率

Fig. 15 Success rates of β-QoM target-barrier construction with different β

图16 不同β的β-QoM目标栅栏平均节点数

Fig. 16 Average nodes of β-QoM target-barriers with different β

参考文献 18

1	孙利民，张书钦，李志，等. 无线传感器网络：理论及应用［M］. 北京：清华大学出版社， 2018：371-372.
	SUN L M， ZHANG S Q， LI Z， et al. Wireless Sensor Network： Theory and Applications［M］. Beijing： Tsinghua University Press， 2018：371-372.
2	赵露. 有向传感器网络栅栏覆盖控制技术研究［D］. 南京：南京理工大学， 2019：15-20.
	ZHAO L. Research on barrier coverage in directional sensor networks［D］. Nanjing： Nanjing University of Science and Technology， 2019：15-20.
3	LALAMA A， KHERNANE N， MOSTEFAOUI A. Closed peripheral coverage in wireless multimedia sensor networks［C］// Proceedings of the 15th ACM International Symposium on Mobility Management and Wireless Access. New York： ACM， 2017：121-128. 10.1145/3132062.3132073
4	KUMAR S， LAI T H， ARORA A. Barrier coverage with wireless sensors［C］// Proceedings of the 11th Annual International Conference on Mobile Computing and Networking. New York： ACM， 2005： 284-298. 10.1145/1080829.1080859
5	LUO J H， ZOU S H. Strong k-barrier coverage for one-way intruders detection in wireless sensor networks［J］. International Journal of Distributed Sensor Networks， 2016， 12（6）： No.3807824. 10.1155/2016/3807824
6	郭新明，陈伟，谢飞，等. 无线传感器网络山地三维环状栅栏覆盖算法［J］. 传感器与微系统， 2021， 40（6）：149-151， 160.
	GUO X M， CHEN W， XIE F， et al. Design of mountain area 3D ring-barrier coverage algorithm in WSNs［J］. Transducer and Microsystem Technologies， 2021， 40（6）： 149-151， 160.
7	CHENG C F， WANG C W. The target-barrier coverage problem in wireless sensor networks［J］. IEEE Transactions on Mobile Computing， 2018， 17（5）： 1216-1232. 10.1109/tmc.2017.2751040
8	SI P J， WANG S S， SHU L， et al. Optimal deployment for target-barrier coverage problems in wireless sensor networks［J］. IEEE Systems Journal， 2021， 15（2）： 2241-2244. 10.1109/jsyst.2020.2990395
9	SI P J， FU Z M， SHU L， et al. Target-barrier coverage improvement in an insecticidal lamps internet of UAVs［J］. IEEE Transactions on Vehicular Technology， 2022， 71（4）： 4373-4382. 10.1109/tvt.2022.3148175
10	LI L， CHEN H B. UAV enhanced target-barrier coverage algorithm for wireless sensor networks based on reinforcement learning［J］. Sensors， 2022， 22（17）： No.6381. 10.3390/s22176381
11	CHEN G， XIONG Y H， SHE J H， et al. Optimization of the directional sensor networks with rotatable sensors for target-barrier coverage［J］. IEEE Sensors Journal， 2021， 21（6）： 8276-8288. 10.1109/jsen.2020.3045138
12	WANG P， XIONG Y H， SHE J H. A new closed-barrier covering optimization method for heterogeneous nodes in hybrid wireless sensor networks［C］// Proceedings of the 47th Annual Conference of the IEEE Industrial Electronics Society. Piscataway： IEEE， 2021： 1-6. 10.1109/iecon48115.2021.9589622
13	CHENG C F， TSAI K T. Distributed barrier coverage in wireless visual sensor networks with β-QoM［J］. IEEE Sensors Journal， 2012， 12（6）：1726-1735. 10.1109/jsen.2011.2177966
14	CHENG C F， TSAI K T. Barrier coverage in wireless visual sensor networks with importance of image consideration［C］// Proceedings of the 7th International Conference on Ubiquitous and Future Networks. Piscataway： IEEE， 2015： 793-798. 10.1109/icufn.2015.7182651
15	GUO L， LI D Y， ZHU Y Q， et al. Enhancing barrier coverage with β quality of monitoring in wireless camera sensor networks［J］. Ad Hoc Networks， 2016， 51： 62-79. 10.1016/j.adhoc.2016.08.011
16	郭新明，蔡军伟. WVSN入侵检测全视角弱栅栏β-QoM 增强构建算法［J］. 计算机科学与探索， 2022， 16（12）：2765- 2774.
	GUO X M， CAI J W. WVSN intrusion detection full-view weak barrier β-QoM enhanced construction algorithm［J］. Journal of Frontiers of Computer Science and Technology， 2022， 16（12）：2765-2774.
17	谈之奕，林凌. 组合优化与博弈论［M］. 杭州：浙江大学出版社， 2015：134-168.
	TAN Z Y， LIN L. Combinatorial Optimization and Game Theory［M］. Hangzhou： Zhejiang University Press， 2015： 134-168.
18	马克·艾伦·韦斯. 数据结构与算法分析-C语言描述（原书第2版）［M］.冯舜玺，译. 北京：机械工业出版社， 2004： 235- 240.
	WEISS M A. Data Structures and Algorithm Analysis in C［M］. 2nd ed. FENG S X， Translated. Beijing： China Machine Press， 2004： 235- 240.

[1]	林东东, 李曼曼, 陈少真. 基于神经区分器的KATAN48算法条件差分分析方法[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2462-2470.
[2]	高智慧, 韩萌, 刘淑娟, 李昂, 穆栋梁. 基于智能优化算法的高效用项集挖掘方法综述[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1676-1686.
[3]	石一鹏, 刘杰, 祖锦源, 张涛, 张国群. 基于混合整数线性规划模型的SPONGENT S盒紧凑约束分析[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1504-1510.
[4]	徐周波, 陈浦青, 刘华东, 杨欣. 基于自注意力网络的深度图匹配模型[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1005-1012.
[5]	姜松岩, 廖晓鹃, 陈光柱. 基于可满足性模理论的多处理机通信延迟优化任务调度方法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 185-191.
[6]	肖智豪, 胡志华, 朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2926-2935.
[7]	张新明, 温少晨, 刘尚旺. 差分扰动的堆优化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(8): 2519-2527.
[8]	杨杰, 张名扬, 芮晓彬, 王志晓. 融合节点覆盖范围和结构洞的影响力最大化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1155-1161.
[9]	韦铭燕, 陈彧, 张亮. 针对混合变量优化问题的协同进化蚁群优化算法[J]. 计算机应用, 2021, 41(5): 1412-1418.
[10]	刘宗甫, 袁征, 赵晨曦, 朱亮. 对PICO算法基于可分性的积分攻击[J]. 计算机应用, 2020, 40(10): 2967-2972.
[11]	隗千千, 董兴业, 王焕政. 染缸排产建模及滑动时间窗启发式调度算法[J]. 计算机应用, 2020, 40(1): 292-298.
[12]	张宪立, 唐建新, 曹来成. 基于反向PageRank的影响力最大化算法[J]. 计算机应用, 2020, 40(1): 96-102.
[13]	杨晓华, 郭健全. 模糊环境下多周期多决策生鲜闭环物流网络[J]. 计算机应用, 2019, 39(7): 2168-2174.
[14]	郑红星, 王泉慧, 任亚群. 考虑潮汐影响的班轮多船型船舶调度[J]. 计算机应用, 2019, 39(2): 611-617.
[15]	吴斌, 王超, 董敏. 基于混合果蝇优化算法的现场服务调度问题[J]. 计算机应用, 2018, 38(9): 2706-2711.

无线视频传感器网络β-QoM目标栅栏覆盖构建算法

β-QoM target-barrier coverage construction algorithm for wireless visual sensor network

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 17

参考文献 18

相关文章 15

编辑推荐

Metrics