Online abnormal event detection with spatio-temporal relationship in river networks

doi:10.11772/j.issn.1001-9081.2015.11.3106

Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (11): 3106-3111.DOI: 10.11772/j.issn.1001-9081.2015.11.3106

• DPCS 2015 Paper • Previous Articles Next Articles

Online abnormal event detection with spatio-temporal relationship in river networks

MAO Yingchi¹, JIE Qing¹, CHEN Hao^2,3

1. College of Computer and Information, Hohai University, Nanjing Jiangsu 211100, China;
2. College of Water Conservancy and Hydropower Engineering, Hohai University, Nanjing Jiangsu 210098, China;
3. Huaneng Lancang River Hydropower Company Limited, Kunming Yunnan 650214, China

Received:2015-06-17 Revised:2015-07-28 Published:2015-11-13

河网中具有时空关系的异常事件在线检测

毛莺池¹, 接青¹, 陈豪^2,3

1. 河海大学计算机与信息学院, 南京 211100;
2. 河海大学水利水电学院, 南京 210098;
3. 华能澜沧江水电股份有限公司, 昆明 650214

通讯作者: 毛莺池(1976-),女,上海人,副教授,博士,CCF会员,主要研究方向:分布式计算、并行处理、分布式数据管理.
作者简介:接青(1989-),女,山东烟台人,硕士研究生,主要研究方向:分布式计算、并行处理、数据管理; 陈豪(1982-),男,上海人,高级工程师,博士研究生,主要研究方向:水工结构安全监测.
基金资助:
国家自然科学基金资助项目(61272543);国家科技支撑计划项目(2013BAB06B04);中央高校基本科研业务费专项资金资助项目(2015B22214)中国华能集团公司总部科技项目(HNKJ13-H17-04);云南省科技计划项目(2014GA007).

Abstract

Abstract: When the network abnormal event occurs, the spatial-temporal correlation of the sensor nodes is very obvious. While existing methods generally separate time and space data properties, a decentralized algorithm of spatial-temporal abnormal detection based on Probabilistic Graphical Model (PGM) was proposed. Firstly the Connected Dominating Set (CDS) algorithm was used to select part of the sensor nodes to avoid monitoring all the sensor nodes, and then Markov Chain (MC) was used to predict time exception event, at last Bayesian Network (BN) was utilized in modelling the spatial dependency of sensors, combining spatio-temporal events to predict whether the abnormal events would or would not occur. Compared with the simple threshold algorithm and BN algorithm, the experimental results demonstrate that the proposed algorithm has higher detection precision, and low delay rate, greatly reducing the communication overhead and improving the response speed.

Key words: abnormal event detection, Markov chain, Bayesian Network (BN), spatial-temporal event, Connected Dominating Set (CDS)

摘要： 当网络异常事件发生时,传感器节点间的时空相关性往往非常明显.而现有方法通常将时间和空间数据性质分开考虑,提出一种分散的基于概率图模型的时空异常事件检测算法.该算法首先利用连通支配集算法(CDS)选择部分传感器节点监测,避免监测所有的传感器节点;然后通过马尔可夫链(MC)预测时间异常事件;最后用贝叶斯网络(BN)推测空间异常事件是否出现,结合时空事件来预测异常事件是否会发生.与简单阈值算法和基于贝叶斯网络算法对比,实验结果表明该算法有高检测精度、低延迟率, 能大幅降低通信开销,提高响应速度.

关键词: 异常事件检测, 马尔可夫链, 贝叶斯网络, 时空事件, 连通支配集

CLC Number:

TP393

MAO Yingchi, JIE Qing, CHEN Hao. Online abnormal event detection with spatio-temporal relationship in river networks[J]. Journal of Computer Applications, 2015, 35(11): 3106-3111.

毛莺池, 接青, 陈豪. 河网中具有时空关系的异常事件在线检测[J]. 计算机应用, 2015, 35(11): 3106-3111.

References

[1] TANG H, XIE J, LU Y, et al. Wireless sensor network theory and application[M].Beijing: Posts & Telecom Press, 2010: 2-3, 143-146.(唐宏,谢静,鲁玉芳,等.无线传感器网络原理及应用[M].北京:人民邮电出版社,2010:2-3,143-146.)
[2] ELIADES D G, LAMBROU T P, PANAYIOTOU C G, et al. Contamination event detection in water distribution systems using a model-based approach[J]. Procedia Engineering, 2014, 89: 1089-1096.
[3] KOLLER D, FRIEDMAN N. Probabilistic graphical models: principles and techniques[M]. Cambridge: MIT Press, 2009:72-75.
[4] KARLIN S. A first course in stochastic processes[M].New York: Academic Press, 2014:16-22.
[5] LU D. Research on construction of connected dominating sets in wireless sensor network[D]. Suzhou: Soochow University, 2014: 33-46. (鲁登月. 无线传感器网络中连通支配集的构造算法研究[D]. 苏州:苏州大学, 2014: 33-46.)
[6] YIM S J, CHOI Y H. Fault-tolerant event detection using two thresholds in wireless sensor networks[C]// Proceedings of the 15th IEEE Pacific Rim International Symposium on Dependable Computing. Piscataway: IEEE,2009: 331-335.
[7] XUE W, LUO Q, WU H. Pattern-based event detection in sensor networks[J]. Distributed and Parallel Databases, 2012, 30(1): 27-62.
[8] PIAO D, MENON P G, MENGSHOEL O J. Computing probabilistic optical flow using Markov random fields[C]// Proceedings of the 4th International Conference on Computational Modeling of Objects Presented in Images, LNCS 8641. Berlin: Springer, 2014: 241-247.
[9] WANG X R, LIZIER J T, OBST O, et al. Spatiotemporal anomaly detection in gas monitoring sensor networks[C]// Proceedings of the 5th European Conference on Wireless Sensor Networks. Berlin: Springer-Verlag, 2008: 90-105.
[10] HUANG T, MA X, JI X, et al. Online detecting spreading events with the spatio-temporal relationship in water distribution networks[M]// Proceedings of the 9th International Conference on Advanced Data Mining and Applications. Berlin: Springer, 2013: 145-156.
[11] DAI F, WU J. An extended localized algorithm for connected dominating set formation in Ad Hoc wireless networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2004, 15(10): 908-920.
[12] ROSSMAN L A. EPANET 2 Users manual[J]. Laboratory Office of Research and United States Environmental Protection Agency, 2000, 19(1):115-118.
[13] LI H, LIU J. New progress of study of water quality monitoring sensors[J]. Transducer and Microsystem Technologies, 2012, 31(3): 11-14. (黎洪松, 刘俊. 水质检测传感器研究的新进展[J]. 传感器与微系统, 2012, 31(3): 11-14.)

[1]	LI Yanzhi, FAN Yong, GAO Lin. Anomaly detection of oil drilling water flow based on shape flow [J]. Journal of Computer Applications, 2021, 41(6): 1842-1848.
[2]	YIN Fei, LONG Lingli, KONG Zheng, SHAO Han, LI Xin, QIAN Zhuzhong. Deployment method of dockers in cluster for dynamic workload [J]. Journal of Computer Applications, 2021, 41(6): 1581-1588.
[3]	LYU Ruimin, MEI Lilin, XING Hongcha, MENG Lei, ZE Yuefeng. Sequentiality perception quantification method of painting and calligraphy based on Markov chain [J]. Journal of Computer Applications, 2021, 41(1): 295-299.
[4]	DU Xusheng, YU Jiong, YE Lele, CHEN Jiaying. Outlier detection algorithm based on graph random walk [J]. Journal of Computer Applications, 2020, 40(5): 1322-1328.
[5]	MAO Xinyi, NIU Jun, DING Xueer, ZHANG Kaile. QoS verification of microservice composition platform based on model checking [J]. Journal of Computer Applications, 2020, 40(11): 3267-3272.
[6]	TANG Junyong, TIAN Penghui, WANG Hui. Network availability based on Markov chain and quality of service [J]. Journal of Computer Applications, 2018, 38(12): 3518-3523.
[7]	WANG Zhongqiang, CHEN Jide, PENG Jian, HUANG Feihu, TONG Bo. Airline predicting algorithm based on improved Markov chain [J]. Journal of Computer Applications, 2017, 37(7): 2124-2128.
[8]	CHENG Lingfang, GUO Gongde, CHEN Lifei. Classification of symbolic sequences with multi-order Markov model [J]. Journal of Computer Applications, 2017, 37(7): 1977-1982.
[9]	LU Ling, YANG Wu, LIU Xu, LI Yan. Stance detection method based on entity-emotion evolution belief net [J]. Journal of Computer Applications, 2017, 37(5): 1402-1406.
[10]	MAO Yingchi, QI Hai, JIE Qing, WANG Longbao. M-TAEDA: temporal abnormal event detection algorithm for multivariate time-series data of water quality [J]. Journal of Computer Applications, 2017, 37(1): 138-144.
[11]	XING Zhiwei, TANG Yunxiao, LUO Qian. Dynamic estimation about service time of flight support based on Bayesian network [J]. Journal of Computer Applications, 2017, 37(1): 299-304.
[12]	SONG Tao, WANG Xing. Customer behavior prediction for card consumption based on two-step clustering and hidden Markov chain [J]. Journal of Computer Applications, 2016, 36(7): 1904-1908.
[13]	PAN Lei, ZHOU Huan, WANG Minghui. Real-time detection method of abnormal event in crowds [J]. Journal of Computer Applications, 2016, 36(6): 1719-1723.
[14]	XU Weishan, YU Lei, FENG Junchi, HOU Shaofan. Software testing data generation technology based on software hierarchical model [J]. Journal of Computer Applications, 2016, 36(12): 3454-3460.
[15]	GUO Ning MAO Jianlin WANG Rui QIAO Guanhua HU Yujie ZHANG Chuanlong. Network throughput analysis of IEEE 802.15.4 based on M/G/1/K queuing theory [J]. Journal of Computer Applications, 2014, 34(3): 619-622.

Online abnormal event detection with spatio-temporal relationship in river networks

河网中具有时空关系的异常事件在线检测

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics