| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Distributed Bayesian Algorithms for Fault-Tolerant Event Region Detection in Wireless Sensor Networks
March 2004 (vol. 53 no. 3)
pp. 241-250
Abstract—We propose a distributed solution for a canonical task in wireless sensor networks—the binary detection of interesting environmental events. We explicitly take into account the possibility of sensor measurement faults and develop a distributed Bayesian algorithm for detecting and correcting such faults. Theoretical analysis and simulation results show that 85-95 percent of faults can be corrected using this algorithm, even when as many as 10 percent of the nodes are faulty.
[1] 241 D. Estrin, L. Girod, G. Pottie, and M. Srivastava, Instrumenting the World with Wireless Sensor Networks Proc. Int'l Conf. Acoustics, Speech and Signal Processing (ICASSP 2001), May 2001.[2] C. Intanagonwiwat, R. Govindan, and D. Estrin, Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks Proc. ACM/IEEE Int'l Conf. Mobile Computing and Networks (MobiCom 2000), Aug. 2000.[3] C. Intanagonwiwat, D. Estrin, R. Govindan, and J. Heidemann, Impact of Network Density on Data Aggregation in Wireless Sensor Networks Proc. 22nd Int'l Conf. Distributed Computing Systems (ICDCS '02), July 2002.[4] D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, Next Century Challenges: Scalable Coordination in Sensor Networks Proc. ACM/IEEE Int'l Conf. Mobile Computing and Networks (MobiCom '99), Aug. 1999.[5] K. Marzullo, Implementing Fault-Tolerant Sensors TR89-997, Dept. of Computer Science, Cornell Univ., May 1989.[6] L. Prasad, S.S. Iyengar, R.L. Kashyap, and R.N. Madan, Functional Characterization of Fault Tolerant Interation in Distributed Sensor Networks IEEE Trans. Systems, Man, and Cybernetics, vol. 21, no. 5, Sept./Oct. 1991.[7] N. Lynch, Distributed Algorithms. Morgan Kauffman, 1997.[8] B.A. Forouzan, Data Communications and Networking. McGraw-Hill, 2001.[9] A. Cerpa et al., Habitat Monitoring: Application Driver for Wireless Communications Technology Proc. 2001 ACM SIGCOMM Workshop Data Comm. in Latin America and the Caribbean, Apr. 2001.[10] A. Cerpa and D. Estrin, "ASCENT: Adaptive Self-Configuring Sensor Network Topologies," to be published in Proc. IEEE Infocom, IEEE Press, Piscataway, N.J., 2002.[11] J. Heidemann, F. Silva, C. Intanagonwiwat, R. Govindan, D. Estrin, and D. Ganesan, Building Efficient Wireless Sensor Networks with Low-Level Naming Proc. 18th ACM Symp. Operating Systems Principles, Oct. 2001.[12] W.W. Manges, Wireless Sensor Network Topologies Sensors Magazine, vol. 17, no. 5, May 2000.[13] G.J. Pottie and W.J. Kaiser, Wireless Integrated Network Sensors Comm. ACM, vol. 43, no. 5, pp. 551-558, May 2000.[14] S. Singh, M. Woo, and C.S. Raghavendra, Power-Aware Routing in Mobile Ad-Hoc Networks Proc. ACM/IEEE Int'l Conf. Mobile Computing and Networks (MOBICOM '98), pp. 76-84, Oct. 1999.[15] J. Warrior, Smart Sensor Networks of the Future Sensors Magazine, Mar. 1997.[16] K. Chakrabarty, S.S. Iyengar, H. Qi, and E.C. Cho, Grid Coverage of Surveillance and Target Location in Distributed Sensor Networks IEEE Trans. Computers, vol. 51, no. 12, pp. 1448-1453, Dec. 2002.[17] S.S. Iyengar, M.B. Sharma, and R.L. Kashyap, Information Routing and Reliability Issues in Distributed Sensor Networks IEEE Trans. Signal Processing, vol. 40, no. 2, pp. 3012-3021, Dec. 1992.[18] S.S. Iyengar, D.N. Jayasimha, and D. Nadig, A Versatile Architecture for the Distributed Sensor Integration Problem IEEE Trans. Computers, vol. 43, no. 2, Feb. 1994.[19] L. Prasad, S.S. Iyengar, R.L. Rao, and R.L. Kashyap, Fault-Tolerant Sensor Integration Using Multiresolution Decomposition Physical Rev. E, vol. 49, no. 4, Apr. 1994.[20] K. Sohrabi, J. Gao, V. Ailawadhi, and G. Pottie, “Protocols for Self-Organization of a Wireless Sensor Network,” IEEE Personal Comm. Magazine, vol. 7, no. 5, pp. 16-27, Oct. 2000.[21] M. Chu, H. Haussecker, and F. Zhao, Scalable Information-Driven Sensor Querying and Routing for Ad Hoc Heterogeneous Sensor Networks Proc. Int'l J. High Performance Computing Applications, 2002.[22] P. Bonnet, J.E. Gehrke, and P. Seshadri, "Querying the Physical World," IEEE Personal Comm., vol. 7, no. 5, Oct. 2000, pp. 10-15.[23] B. Krishnamachari, R. Bejar, and S.B. Wicker, Distributed Problem Solving and the Boundaries of Self-Configuration in Multi-Hop Wireless Networks Proc. 35th Hawaii Int'l Conf. System Sciences, 2001.[24] R. Min et al., An Architecture for a Power-Aware Distributed Microsensor Node Proc. IEEE Workshop Signal Processing Systems (SiPS '00), Oct. 2000.[25] S. Chessa and P. Santi, Crash Faults Identification in Wireless Sensor Networks Computer Comm., vol. 25, no. 14, pp. 1273-1282, Sept. 2002.[26] D. Estrin et al., Embedded, Everywhere: A Research Agenda for Networked Systems of Embedded Computers Nat'l Research Council Report, 2001.[27] N. Bulusu, J. Heidemann, and D. Estrin, “GPS-Less Low Cost Outdoor Localization for Very Small Devices,” IEEE Personal Comm., vol. 7, no. 5, pp. 28–34, 2000.[28] R.A. Maxion, Toward Diagnosis as an Emergent Behavior in a Network Ecosystem Emergent Computation, S. Forrest, ed. MIT Press, 1991.[29] V. Park and S. Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks Proc. 18th Ann. Joint Conf. IEEE Computer and Comm. Soc. (INFOCOM), pp. 1405-1414, Apr. 1997.[30] N. Megiddo, Linear Time Algorithm for Linear Programming in R3 and Related Problems SIAM J. Computers, vol. 12, no. 4, pp. 759-776, 1983.[31] M.E. Dyer, Linear Time Algorithms for Two and Three-Variable Linear Programs SIAM J. Computers, vol. 13, no. 1, pp. 31-45, 1984.[32] B. Cain, T. Speakman, and D. Towsley, Generic Router Assist (GRA) Building Block Motivation and Architecture RMT Working Group, Internet-Draft$<$draft-ietf-rmt-gra-arch-01.txt$>$, work in progress, Mar. 2000.[33] D.L. Tennenhouse, J.M. Smith, W.D. Sincoskie, D.J. Wetherall, and G.J. Minden, “A Survey of Active Network Research,” IEEE Comm. Magazine, vol. 35, no. 1, pp. 80-86, Jan. 1997.[34] I.F. Akyildiz et al., "A Survey on Sensor Networks," IEEE Comm., vol. 40, no. 8, Aug. 2002, pp.102-114.[35] D.K. Gifford, Weighted Voting for Replicated Data Proc. ACM Symp. Operating Systems Principles, 1979.[36] R.H. Thomas, A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases ACM Trans. Database Systems, vol. 4, pp. 180-209, 1979.[37] L.A. Klein, Sensor and Data Fusion Concepts and Applications. SPIE, Apr. 1993.
Index Terms:
Fault tolerance, event detection, sensor fusion, Bayesian algorithms, wireless sensor networks.
Citation:
Bhaskar Krishnamachari, Sitharama Iyengar, "Distributed Bayesian Algorithms for Fault-Tolerant Event Region Detection in Wireless Sensor Networks," IEEE Transactions on Computers, vol. 53, no. 3, pp. 241-250, Mar. 2004, doi:10.1109/TC.2004.1261832
