An efficient lossy link localization approach for wireless sensor networks

Wen-yan CUI; Xiang-ru MENG; Bin-feng YANG; Huan-huan YANG; Zhi-yuan ZHAO

doi:10.1631/FITEE.1601247

Your Location：

Home >

Browse articles >

An efficient lossy link localization approach for wireless sensor networks

Regular Papers | Updated：2022-05-19

- An efficient lossy link localization approach for wireless sensor networks
- 一种有效的无线传感器网络失效链路定位方法
- Frontiers of Information Technology & Electronic Engineering Vol. 18, Issue 5, Pages: 689-707(2017)
- Affiliations：
  
  1College of Information and Navigation, Air Force Engineering University, Xi'an 710077, China
  2Department of Electronic Engineering, Tsinghua University, Beijing 100084, China
  3PLA of 94543, Jining 272000, China
- Author bio：
  
  E-mail:cwy_edu@163.com
- Funds：
- DOI：10.1631/FITEE.1601247
  CLC： TP393
- Received：10 May 2016，
  
  Accepted：10 November 2016，
  
  Published：2017-05
- Accepted：
Scan QR Code
Wen-yan CUI, Xiang-ru MENG, Bin-feng YANG, et al. An efficient lossy link localization approach for wireless sensor networks[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(5): 689-707.
DOI：

Wen-yan CUI, Xiang-ru MENG, Bin-feng YANG, et al. An efficient lossy link localization approach for wireless sensor networks[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(5): 689-707. DOI： 10.1631/FITEE.1601247.

摘要

由于无线传感器网络中经常发生故障，网络故障管理对其维持正常运行状态非常重要。当前的故障定位方法通常先推断最有可能故障集，然后给出故障假设集。然而假设集中往往含有大量实际并未发生的故障。推断集中的冗余信息会大大加重故障推断的计算量，从而降低评估精度且增加故障定位时间。为了解决这个问题，本文提出了基于条件信息熵的冗余消除算法，该算法可以在保留核心信息的基础上消除大部分冗余信息。此外，还提出一种可以精确反映故障关系的概率关联故障模型，并为非确定性故障传播构建模型。通过一系列数学推导，本文将故障定位问题转化为覆盖件问题进行求解，并提出启发式算法推导故障假设集。在仿真环境和真实平台上验证了提出的方法相比现有故障定位方法的有效性。

Abstract

Network fault management is crucial for a wireless sensor network (WSN) to maintain a normal running state because faults (e.g.

link failures) often occur. The existing lossy link localization (LLL) approach usually infers the most probable failed link set first

and then gives the fault hypothesis set. However

the inferred failed link set contains many possible failures that do not actually occur. That quantity of redundant information in the inferred set can pose a high computational burden on fault hypothesis inference

and consequently decreases the evaluation accuracy and increases the failure localization time. To address the issue

we propose the conditional information entropy based redundancy elimination (CIERE)

a redundant lossy link elimination approach

which can eliminate most redundant information while reserving the important information. Specifically

we develop a probabilistically correlated failure model that can accurately reflect the correlation between link failures and model the nondeterministic fault propagation. Through several rounds of mathematical derivations

the LLL problem is transformed to a set-covering problem. A heuristic algorithm is proposed to deduce the failure hypothesis set. We compare the performance of the proposed approach with those of existing LLL methods in simulation and on a real WSN

and validate the efficiency and effectiveness of the proposed approach.

关键词

Keywords

references

ML Ali , , , PH Ho , , , J Tapolcai , , , 等 . . Multi-link failure localization via monitoring bursts . . J. Optim. Commun. Netw. , , 2014 . . 6 ( ( 11 ): ): 952 - - 964 . . DOI: 10.1364/JOCN.6.000952 http://doi.org/10.1364/JOCN.6.000952 . .

AE Assaf , , , S Zaidi , , , S Affes , , , 等 . . Low-cost localization for multihop heterogeneous wireless sensor networks . . IEEE Trans. Wirel. Commun. , , 2015 . . 15 ( ( 1 ): ): 472 - - 484 . . DOI: 10.1109/TWC.2015.2475255 http://doi.org/10.1109/TWC.2015.2475255 . .

FZ Benhamida , , , Y Challal , , , M Koudil . . Adaptive failure detection in low power lossy wireless sensor networks . . J. Netw. Comput. Appl. , , 2014 . . 45 ( ( 4 ): ): 168 - - 180 . . DOI: 10.1016/j.jnca.2014.07.028 http://doi.org/10.1016/j.jnca.2014.07.028 . .

A Benveniste , , , E Fabre , , , S Haar , , , 等 . . Diagnosis of asynchronous discrete-event systems: a net unfolding approach . . IEEE Trans. Autom. Contr. , , 2003 . . 48 ( ( 9 ): ): 714 - - 727 . . DOI: 10.1109/TAC.2003.811249 http://doi.org/10.1109/TAC.2003.811249 . .

DLV Bossuyt , , , B O'Halloran , , , N Papakonstantiou . . Cable routing modeling in early system design to prevent cable failure propagation events . . 2016 . . IEEE Annual Reliability and Maintainability Symp. . . 1 - - 6 . . DOI: 10.1109/RAMS.2016.7448006 http://doi.org/10.1109/RAMS.2016.7448006 . .

O Chipara , , , G Hackmann , , , C Lu . . Practical modeling and prediction of radio coverage of indoor sensor networks . . 2010a . . Proc. 9th Int. Conf. on Information Processing in Sensor Networks . . 339 - - 349 . . DOI: 10.1145/1791212.1791252 http://doi.org/10.1145/1791212.1791252 . .

O Chipara , , , C Lu , , , TC Bailey . . Reliable clinical monitoring using wireless sensor networks: experiences in a step-down hospital unit . . 2010b . . Proc. 8th Int. Conf. on Embedded Networked Sensor Systems . . 155 - - 168 . . DOI: 10.1145/1869983.1869999 http://doi.org/10.1145/1869983.1869999 . .

GS Choi , , , IK Park . . Uncertainty improvement of incomplete decision system using Bayesian conditional information entropy . . J. Inst. Int. Broadc. Commun. , , 2014 . . 14 ( ( 6 ): ): 47 - - 54 . . DOI: 10.7236/JIIBC.2014.14.6.47 http://doi.org/10.7236/JIIBC.2014.14.6.47 . .

M Collotta , , , LL Bello , , , G Pau . . A novel approach for dynamic traffic lights management based on wireless sensor networks and multiple fuzzy logic controllers . . Expert Syst. Appl. , , 2015 . . 42 ( ( 13 ): ): 5403 - - 5415 . . DOI: 10.1016/j.eswa.2015.02.011 http://doi.org/10.1016/j.eswa.2015.02.011 . .

R Couillet , , , W Hachem . . Local failure localization in large sensor networks . . 2011 . . 45th Asilomar Conf. on Signals, Systems and Computers . . 1970 - - 1974 . . DOI: 10.1109/ACSSC.2011.6190369 http://doi.org/10.1109/ACSSC.2011.6190369 . .

A Dias , , , P Campos , , , P Garrido . . An agent based propagation model of bank failures . . Lect. Notes Econ. Math. Syst. , , 2015 . . 676 119 - - 130 . . DOI: 10.1007/978-3-319-09578-3_10 http://doi.org/10.1007/978-3-319-09578-3_10 . .

WW Fang , , , JM Chen , , , L Shu , , , 等 . . Congestion avoidance, detection and alleviation in wireless sensor networks . . J. Zhejiang Univ.-Sci. C (Comput. & Electron.) , , 2010 . . 11 ( ( 1 ): ): 63 - - 73 . . DOI: 10.1631/jzus.C0910204 http://doi.org/10.1631/jzus.C0910204 . .

W Gong , , , K Liu , , , Y Liu . . Directional diagnosis for wireless sensor networks . . IEEE Trans. Parall. Distr. Syst. , , 2015 . . 26 ( ( 5 ): ): 1290 - - 1300 . . DOI: 10.1109/TPDS.2014.2308173 http://doi.org/10.1109/TPDS.2014.2308173 . .

V Gupta , , , E Tovar , , , K Lakshmanan , , , 等 . . Inter-application redundancy elimination in wireless sensor networks with compiler-assisted scheduling . . 2012 . . 7th IEEE Int. Symp. on Industrial Embedded Systems . . 112 - - 119 . . DOI: 10.1109/SIES.2012.6356576 http://doi.org/10.1109/SIES.2012.6356576 . .

A Haddad , , , EA Doumith , , , M Gagnaire . . A fast and accurate meta-heuristic for failure localization based on the monitoring trail concept . . Telecommun. Syst. , , 2013 . . 52 ( ( 2 ): ): 813 - - 824 . . DOI: 10.1007/s11235-011-9579-0 http://doi.org/10.1007/s11235-011-9579-0 . .

P Harris , , , R Philip , , , S Robinson , , , 等 . . Monitoring anthropogenic ocean sound from shipping using an acoustic sensor network and a compressive sensing approach . . Sensors , , 2016 . . 16 ( ( 3 ): ): 415 DOI: 10.3390/s16030415 http://doi.org/10.3390/s16030415 . .

W He , , , B Wu , , , PH Ho , , , 等 . . Monitoring trail allocation for SRLG failure localization . . 2011 . . IEEE Global Telecommunications Conf. . . 1 - - 5 . . DOI: 10.1109/GLOCOM.2011.6133707 http://doi.org/10.1109/GLOCOM.2011.6133707 . .

W Kim , , , G Park , , , S Pack , , , 等 . . Lightweight traffic redundancy elimination in software-defined wireless mesh networks . . 2014 . . 3rd IEEE Global Conf. on Consumer Electronics . . 723 - - 724 . . DOI: 10.1109/GCCE.2014.7031262 http://doi.org/10.1109/GCCE.2014.7031262 . .

M Li . . Underground structure monitoring with wireless sensor networks . . 2007 . . 6th Int. Symp. on Information Processing in Sensor Networks . . 69 - - 78 . . DOI: 10.1109/IPSN.2007.4379666 http://doi.org/10.1109/IPSN.2007.4379666 . .

Y Li , , , H Shi , , , S Zhang . . An optimized scheme for battlefield target tracking in wireless sensor network . . 2010 . . 2nd Int. Conf. on Industrial and Information Systems . . 356 - - 359 . . DOI: 10.1109/INDUSIS.2010.5565835 http://doi.org/10.1109/INDUSIS.2010.5565835 . .

K Liu , , , Q Ma , , , W Gong . . Self-diagnosis for detecting system failures in large-scale wireless sensor networks . . IEEE Trans. Wirel. Commun. , , 2014 . . 13 ( ( 10 ): ): 5535 - - 5545 . . DOI: 10.1109/TWC.2014.2336653 http://doi.org/10.1109/TWC.2014.2336653 . .

W Ma , , , J Zhang . . Algorithm based on heuristic strategy to infer lossy links in wireless sensor networks . . Algorithms , , 2014 . . 7 ( ( 3 ): ): 397 - - 404 . . DOI: 10.3390/a7030397 http://doi.org/10.3390/a7030397 . .

N Mahadevan , , , S Abdelwahed , , , A Dubey , , , 等 . . Distributed diagnosis of complex systems using timed failure propagation graph models . . 2010 . . IEEE AUTOTESTCON . . 1 - - 6 . . DOI: 10.1109/AUTEST.2010.5613575 http://doi.org/10.1109/AUTEST.2010.5613575 . .

R Manolov , , , G Guilera , , , V Sierra . . An analysis of a large scale habitat monitoring application . . 2004 . . 2nd Int. Conf. on Embedded Networked Sensor Systems . . 214 - - 226 . . DOI: 10.1145/1031495.1031521 http://doi.org/10.1145/1031495.1031521 . .

M Manzano , , , E Calle , , , J Ripoll , , , 等 . . Epidemic survivability: characterizing networks under epidemic-like failure propagation scenarios . . 2013 . . 9th Int. Conf. on the Design of Reliable Communication Networks . . 95 - - 102 . . . .

X Miao , , , K Liu , , , Y He . . Agnostic diagnosis: discovering silent failures in wireless sensor networks . . IEEE Trans. Wirel. Commun. , , 2011 . . 12 ( ( 12 ): ): 6067 - - 6075 . . DOI: 10.1109/TWC.2013.110813.121812 http://doi.org/10.1109/TWC.2013.110813.121812 . .

HX Nguyen , , , P Thiran . . Using end-to-end data to infer lossy links in sensor networks . . 2006 . . 25th IEEE Int. Conf. on Computer Communication . . 1 - - 12 . . DOI: 10.1109/INFOCOM.2006.271 http://doi.org/10.1109/INFOCOM.2006.271 . .

Q Niu , , , S Xia , , , G Tan . . A method of fuzzy reasoning based on semantic similarity and bipartite graph matching . . 2009 . . IEEE Int. Conf. on Artificial Intelligence and Computational Intelligence . . 141 - - 145 . . DOI: 10.1109/AICI.2009.89 http://doi.org/10.1109/AICI.2009.89 . .

S Ntalampiras . . Fault identification in distributed sensor networks based on universal probabilistic modeling . . IEEE Trans. Neur. Netw. Learn. Syst. , , 2014 . . 26 ( ( 9 ): ): 1939 - - 1949 . . DOI: 10.1109/TNNLS.2014.2362015 http://doi.org/10.1109/TNNLS.2014.2362015 . .

M Nyberg . . Failure propagation modeling for safety analysis using causal Bayesian networks . . 2013 . . IEEE Conf. on Control and Fault-Tolerant Systems . . 91 - - 97 . . DOI: 10.1109/SysTol.2013.6693936 http://doi.org/10.1109/SysTol.2013.6693936 . .

G Park , , , Y Shim , , , I Jang , , , 等 . . Bloom-filter-aided redundancy elimination in opportunistic communications . . IEEE Wirel. Commun. , , 2016 . . 23 ( ( 1 ): ): 112 - - 119 . . DOI: 10.1109/MWC.2016.7422413 http://doi.org/10.1109/MWC.2016.7422413 . .

P Patil , , , U Kulkarni . . SVM based data redundancy elimination for data aggregation in wireless sensor networks . . 2013 . . IEEE Int. Conf. on Advances in Computing, Communications and Informatics . . 1309 - - 1316 . . DOI: 10.1109/ICACCI.2013.6637367 http://doi.org/10.1109/ICACCI.2013.6637367 . .

C Priesterjahn , , , C Heinzemann , , , W Schafer . . From timed automata to timed failure propagation graphs . . 2013 . . 16th IEEE Int. Symp. on Object/Component/Service-Oriented Real-Time Distributed Computing . . 1 - - 8 . . DOI: 10.1109/ISORC.2013.6913236 http://doi.org/10.1109/ISORC.2013.6913236 . .

S Rajasegarar , , , C Leckie , , , M Palaniswami . . Anomaly detection in wireless sensor networks . . IEEE Wirel. Commun. , , 2008 . . 15 ( ( 1 ): ): 34 - - 40 . . DOI: 10.1109/MWC.2008.4599219 http://doi.org/10.1109/MWC.2008.4599219 . .

MK Sandhya , , , K Murugan , , , P Devaraj . . Selection of aggregator nodes and elimination of false data in wireless sensor networks . . Wirel. Netw. , , 2015 . . 21 ( ( 4 ): ): 1327 - - 1341 . . DOI: 10.1007/s11276-014-0859-y http://doi.org/10.1007/s11276-014-0859-y . .

M Shakeri , , , R Pattipati , , , V Raghavan . . Optimal and near-optimal algorithms for multiple fault diagnosis with unreliable tests . . IEEE Trans Syst. Man Cybern. C , , 1996 . . 28 ( ( 3 ): ): 431 - - 440 . . DOI: 10.1109/5326.704583 http://doi.org/10.1109/5326.704583 . .

D Shen . . Adaptive fault monitoring in all-optical networks utilizing real-time data traffic . . J. Netw. Syst. Manag. , , 2012 . . 20 ( ( 1 ): ): 76 - - 96 . . DOI: 10.1007/s10922-011-9206-0 http://doi.org/10.1007/s10922-011-9206-0 . .

S Strasser , , , J Sheppard . . Diagnostic alarm sequence maturation in timed failure propagation graphs . . 2011 . . IEEE AUTOTESTCON . . 158 - - 165 . . DOI: 10.1109/AUTEST.2011.6058741 http://doi.org/10.1109/AUTEST.2011.6058741 . .

Y Tang , , , E Al-Shaer , , , R Boutaba . . Efficient fault diagnosis using incremental alarm correlation and active investigation for Internet and overlay networks . . IEEE Trans. Netw. Serv. Manag. , , 2008 . . 5 ( ( 5 ): ): 36 - - 49 . . DOI: 10.1109/TNSM.2008.080104 http://doi.org/10.1109/TNSM.2008.080104 . .

Y Tang , , , G Cheng , , , Z Xu . . Community-based fault diagnosis using incremental belief revision . . 2009 . . IEEE Int. Conf. on Networking, Architecture and Storage . . 121 - - 128 . . DOI: 10.1109/NAS.2009.24 http://doi.org/10.1109/NAS.2009.24 . .

L Troiano , , , AD Cerbo , , , M Tipaldi , , , 等 . . Fault detection and resolution based on extended time failure propagation graphs . . 2015 . . IEEE Conf. on Soft Computing and Pattern Recognition . . 337 - - 342 . . DOI: 10.1109/SOCPAR.2013.7054155 http://doi.org/10.1109/SOCPAR.2013.7054155 . .

G Urbanics , , , L Gnczy , , , B Urbán , , , 等 . . Combined error propagation analysis and runtime event detection in process-driven systems . . 2014 . . 6th Int. Workshop on Software Engineering for Resilient Systems . . 169 - - 183 . . DOI: 10.1007/978-3-319-12241-0_13 http://doi.org/10.1007/978-3-319-12241-0_13 . .

B Wang , , , W Wei , , , H Dinh . . Fault localization using passive end-to-end measurements and sequential testing for wireless sensor networks . . IEEE Trans. Mob. Comput. , , 2011 . . 11 ( ( 3 ): ): 439 - - 452 . . DOI: 10.1109/TMC.2011.98 http://doi.org/10.1109/TMC.2011.98 . .

R Wang , , , Q Wu , , , Y Xiong . . Multi-parameters link failure localization algorithm based on compressive sensing . . J. Electron. Inform. Technol. , , 2013 . . 35 ( ( 11 ): ): 2596 - - 2601 . . DOI: 10.3724/SP.J.1146.2013.00265 http://doi.org/10.3724/SP.J.1146.2013.00265 . .

A Woo , , , T Tong , , , D Culler . . Taming the underlying challenges of reliable multi-hop routing in sensor networks . . 2003 . . Int. Conf. on Embedded Networked Sensor Systems . . 14 - - 27 . . DOI: 10.1145/958491.958494 http://doi.org/10.1145/958491.958494 . .

C Wu , , , J Wang , , , J Zeng . . A network traffic awareness architecture for universal redundancy elimination . . 2011 . . Int. Conf. on Electronic and Mechanical Engineering and Information Technology . . 52 - - 55 . . DOI: 10.1109/EMEIT.2011.6022836 http://doi.org/10.1109/EMEIT.2011.6022836 . .

L Xie , , , PE Heegaard , , , Y Jiang . . Modeling and quantifying the survivability of telecommunication network systems under fault propagation . . 2013 . . International Federation for Information Processing . . 25 - - 36 . . . .

Y Xu , , , Y Liu , , , Y Liu . . Algorithm for redundancy elimination in network traffic . . 2012 . . 2nd IEEE Int. Conf. on Consumer Electronics, Communications and Networks . . 1613 - - 1617 . . DOI: 10.1109/CECNet.2012.6201599 http://doi.org/10.1109/CECNet.2012.6201599 . .

S Yamamoto , , , A Nakao . . P2P packet cache router for network-wide traffic redundancy elimination . . 2012 . . IEEE Int. Conf. on Computing, Networking and Communications . . 830 - - 834 . . DOI: 10.1109/ICCNC.2012.6167541 http://doi.org/10.1109/ICCNC.2012.6167541 . .

C Yang , , , H Shi , , , G Xue , , , 等 . . Network redundancy elimination by dynamic buffer allocation . . 2014 . . IEEE 17th Int. Conf. on Computational Science and Engineering . . 1109 - - 1114 . . DOI: 10.1109/CSE.2014.218 http://doi.org/10.1109/CSE.2014.218 . .

Y Yang , , , Z An , , , Y Xu , , , 等 . . Passive loss inference in wireless sensor networks using EM algorithm . . Wirel. Sens. Netw. , , 2010 . . 2 ( ( 7 ): ): 512 - - 519 . . . .

C Zhang , , , J Liao , , , X Zhu . . Heuristic fault localization algorithm based on Bayesian suspected degree . . J. Softw. , , 2010 . . 21 ( ( 10 ): ): 2610 - - 2621 . . . .

L Zhang , , , W Wang , , , J Gao . . Lossy links diagnosis for wireless sensor networks by utilizing the existing traffic information . . Int. J. Embed. Syst. , , 2014 . . 6 ( ( 2 ): ): 140 - - 147 . . DOI: 10.1504/IJES.2014.063811 http://doi.org/10.1504/IJES.2014.063811 . .

N Zhang , , , X Yang , , , M Zhang , , , 等 . . RMI-DRE: a redundancy-maximizing identification scheme for data redundancy elimination . . Sci.China Inform. Sci. , , 2016 . . 59 089301 DOI: 10.1007/s11432-016-5523-y http://doi.org/10.1007/s11432-016-5523-y . .

Y Zhang , , , N Ansari . . On protocol-independent data redundancy elimination . . IEEE Commun. Surv. Tutor. , , 2014 . . 16 ( ( 1 ): ): 455 - - 472 . . DOI: 10.1109/SURV.2013.052213.00186 http://doi.org/10.1109/SURV.2013.052213.00186 . .

Z Zhao , , , W Cai . . Passive localizing lossy links in sensor network using max-product algorithm . . 2010 . . 3rd IEEE Int. Conf. on Computer Science and Information Technology . . 571 - - 575 . . DOI: 10.1109/ICCSIT.2010.5563652 http://doi.org/10.1109/ICCSIT.2010.5563652 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰