Topk(σ)outlier detection algorithm for wireless sensor networks
Hu Shi1，2，Li Guanghui1，2，3*，Feng Hailin1，2
Author information+
{{custom_zuoZheDiZhi}}
About authors:
1.School of Information Engineering，Zhejiang A&F University，Lin’an，311300，China；2．Zhejiang Provincial Key Laboratory of Intelligent Monitoring in Forestry and Information Technology，Lin’an，311300，China；3.School of Internet of Things，Jiangnan University，Wuxi，214122，China
{{custom_authorNodes}}
{{custom_bio.content}}
{{custom_bio.content}}
{{custom_authorNodes}}
Collapse
History+
Published
2016-03-26
Issue Date
2016-03-26
Abstract
Outlier detection plays an important role in wireless sensor network(WSN)application system for environment monitoring，which helps people monitor the condition of WSNs themselves，and also can detect the emergent events of the environment such as forest fire and air pollution.After improving the topk algorithm，a topk(σ) outlier detection algorithm for WSNs was proposed in this paper.Different from topk algorithm，the proposed algorithm uses the data distribution collected by the sensor nodes to construct appropriate data grid，and puts the data sets into the grid after normalization，then sets a distance threshold σ to reconstruct the PC list(populatedcells list)．This algorithm sorts the numbers of data points in each cell and those of its neighborhood respectively，as well as computes the Euclidean distance R_D between two data subsets，and compares the value of R_D with σ so as to verify the degree of deviation of the subset from the normal data sets.Thus the topk(σ) algorithm can improve the precision of the outliers detection.For given several datasets，the simulation results under MATLAB platform show that，the threshold σ has great effect on the performance of outlier detect algorithm.When σ∈[2.5，3]，the topk(σ) algorithm has higher detection accuracy and lower false positive rate.If σ＝3，for the given five data sets，the average accuracy of outlier detection of topk(σ) algorithm is 93.70%，which is 4.94% higher than that of topk algorithm，and the average false positive rate of topk(σ) algorithm is 4.48% lower than that of topk algorithm.
Hu Shi1，2，Li Guanghui1，2，3*，Feng Hailin1，2.
Topk(σ)outlier detection algorithm for wireless sensor networks[J]. Journal of Nanjing University(Natural Sciences), 2016, 52(2): 261
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
References
[1] 周贤伟，王 培，覃伯平等．一种无线传感器网络异常检测技术研究．传感技术学报，2007，20(8)：1870－1874.(Zhou X W，Wang P，Qin B P，et al.An anomaly detection technology in wireless sensor networks.Chinese Journal of Sensors and Actuators，2007，20(8)：1870－1874.) [2] Subramaniam S，Palpanas T，Papadopoulos D，et al.Online outlier detection in sensor data using nonparametric models.In：Proceedings of the 32nd International Conference on Very Large Data Bases.Almaden，Spanish：VLDB Endowment，2006，187－198. [3] Perrig A，Stankovic J，Wagner D．Security in wireless sensor networks.Communications of the ACM，2004，47(6)：53－57. [4] 曹冬磊，曹建农，金蓓弘．一种无线传感器网络中事件区域检测的容错算法．计算机学报，2007，30(10)：1770－1776.(Cao D L，Cao J N，Jin P H．A faulttolerant algorithm for event region detection in wireless sensor networks.Chinese Journal of Computers，2007，30(10)：1770－1776.) [5] 曹 磊，韩 涛，张 婧等．无线多媒体传感器网络拥塞感知的流控制机制．南京大学学报(自然科学)，2014，50(2)：173－180.(Cao L，Han T，Zhang J，et al.Congestionware flow control strategy in wireless multimedia sensor networks.Journal of Nanjing University(Natural Sciences)，2014，50(2)：173－180.) [6] Martincic F，Schwiebert L．Distributed event detection in sensor networks.In：International Conference on Systems and Networks Communication.IEEE，2006，43. [7] 毕 冉，李建中，程思瑶．无线传感器网络(ε，δ)—近似Topk查询处理算法．通信学报，2011，32(8)：45－54.(Bi R，Li J Z，Cheng S Y．(ε，δ)－approximate Topk query processing algorithm in wireless sensor networks.Journal of Communications，2011，32(8)：45－54.) [8] 姜旭宝，李光耀，连 朔．基于变宽直方图的无线传感器网络异常数据检测算法．计算机应用，2011，31(3)：694－697.(Jiang X B，Li G Y，Lian S．Outlier detection algorithm based on variablewidth histogram for wireless sensor network.Journal of Computer Applications，2011，31(3)：694－697.) [9] 肖政宏，陈志刚，李庆华．WSN中基于分布式机器学习的异常检测仿真研究．系统仿真学报，2011，23(1)：181－187.(Xiao Z H，Chen Z G，Li Q H．Simulation study of anomaly detection based on distributed machine learning for WSN.Journal of System Simulation，2011，23(1)：181－187.) [10] 刘 群，顾 金，张足生．基于无线传感器网络的车辆分型算法．南京大学学报(自然科学)，2013，49(5)：655－663.(Liu Q，Gu J，Zhang Z S．Vehicle lassification algorithm based on wireless sensor networks.Journal of Nanjing University(Natural Sciences)，2013，49(5)：655－663.) [11] Aggarwal C C，Philip S Y．Outlier detection with uncertain data.Society for Industrial and Applied Mathematics，2008，483－493. [12] Sheng B，Li Q，Mao W，et al.Outlier detection in sensor networks.In：Proceedings of the 8th ACM International Symposium on Mobile ad hoc Networking and Computing.York，USA：ACM，2007，219－228. [13] Shaikh S A，Kitagawa H．Distancebased outlier detection on uncertain data of Gaussian distribution.Web Technologies and Applications.Berlin，Germany Springer Berlin Heidelberg，2012，109－121. [14] Shaikh S A，Kitagawa H．Fast topk distancebased outlier detection on uncertain data.WebAge Information Management.Berlin，Germany Springer Berlin Heidelberg，2013，301－313. [15] Knorr E M，Ng R T，Tucakov V．Distancebased outliers：algorithms and applications.The VLDB Journal—The International Journal on Very Large Data Bases，2000，8(3－4)：237－253. [16] Shaikh S A，Kitagawa H．Efficient distancebased outlier detection on uncertain datasets of Gaussian distribution.World Wide Web，2014，17(4)：511－538. [17] Shaikh S A，Kitagawa H．Topk outlier detection from uncertain data.International Journal of Automation and Computing，2014，11(2)：128－142. [18] Hill D J，Minsker B S．Anomaly detection in streaming environmental sensor data：A datadriven modeling approach.Environmental Modelling & Software，2010，25(9)：1014－1022.
PDF(1788107 KB)
