DocumentCode :
1246617
Title :
Computing reliability and message delay for Cooperative wireless distributed sensor networks subject to random failures
Author :
AboElFotoh, Hosam M F ; Iyengar, S.S. ; Chakrabarty, Krishnendu
Author_Institution :
Dept. of Math. & Comput. Sci., Kuwait Univ., Safat, Kuwait
Volume :
54
Issue :
1
fYear :
2005
fDate :
3/1/2005 12:00:00 AM
Firstpage :
145
Lastpage :
155
Abstract :
One of the most compelling technological advances of this decade has been the advent of deploying wireless networks of heterogeneous smart sensor nodes for complex information gathering tasks. A wireless distributed sensor network (DSN) is a self-organizing , ad-hoc network of a large number of cooperative intelligent sensor nodes. Due to the limited power of sensor nodes, energy-efficient DSN are essentially multi-hop networks. The self-organizing capabilities, and the cooperative operation of DSN allow for forming reliable clusters of sensors deployed near, or at, the sites of target phenomena. Reliable monitoring of a phenomenon (or event detection) depends on the collective data provided by the target cluster of sensors, and not on any individual node. The failure of one or more nodes may not cause the operational data sources to be disconnected from the data sinks (command nodes or end user stations). However, it may increase the number of hops a data message has to go through before reaching its destination (and subsequently increase the message delay). In this paper, we focus on two related problems: computing a measure for the reliability of DSN, and computing a measure for the expected & the maximum message delay between data sources (sensors) & data sinks in an operational DSN. Given an estimation of the failure probabilities of the sensors, as well as the intermediate nodes (nodes used to relay messages between data sources, and data sinks), we use a probabilistic graph to model DSN. We define the DSN reliability as the probability that there exists an operating communication path between the sink node, and at least one operational sensor in a target cluster. We show that both problems are #P-hard for arbitrary networks. We then present two algorithms for computing the reliability, and the expected message delay for arbitrary networks. We also consider two special cases where efficient (polynomial time) algorithms are developed. Finally, we present some numerical results that demonstrate some of the applications of our algorithms.
Keywords :
ad hoc networks; failure analysis; intelligent sensors; telecommunication network reliability; telecommunication network routing; wireless sensor networks; ad-hoc network; communication path; complex information gathering task; cooperative intelligent sensor nodes; cooperative wireless distributed sensor network; data sink; data sources; energy-efficient DSN; event detection; expected network diameter; failure probability; graph-theoretic algorithm; heterogeneous smart sensor node; intermediate nodes; message delay computing; multihop network; polynomial time; probabilistic graph model; random failures; reliability computing; routing algorithm; self-organizing capability; target cluster; Ad hoc networks; Clustering algorithms; Computer networks; Delay; Distributed computing; Energy efficiency; Intelligent sensors; Sensor phenomena and characterization; Telecommunication network reliability; Wireless sensor networks; Clustering; distributed sensor networks; expected message delay; expected network diameter; graph-theoretic algorithms; multi-hop networks; probabilistic graph models; reliability; wireless sensor networks;
fLanguage :
English
Journal_Title :
Reliability, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9529
Type :
jour
DOI :
10.1109/TR.2004.842540
Filename :
1402693
Link To Document :
بازگشت