11Quantitative Assessment of Sensor Lifespan in Sensor Networks Using Clustering-Based Routing Mechanism Dezhen [email protected] of Industrial Engineering and Operation ResearchUniversity of California, BerkeleyEE 228A Term Project, Fall 2003 2Contents• Introduction/Review• Inputs and Assumptions• Modeling Energy-consumption rate using Renewal Theorem • Modeling sensor state using Markov Chain• Modeling energy consumed in a single rotation interval• Conclusion & Future work23Introduction/Review• Characteristic of the sensor network– Base station is fixed and far way from the sensors– Homogeneous nodes and energy constrained Sensors Base stationW. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, 20004Introduction/ReviewTdt1t1+dLEACH: Clustering-Based Routing MechanismRotation interval35Introduction• Motivation for quantitative assessment• Given a sensor in such network and located at (x,y), we are interested in – Expected energy consumption rate of the sensor– Explicit functions of network parameters6Inputs and Assumptions• Energy model– Energy for run circuitry– Energy for radio transmission– Energy for sending k bits over distance D– Energy for receiving k bitsnJ/bit50=elecE2pJ/bit/m100=ampε2),( kDkEDkEampelecTxε+=kEDkEelecRx=),(47Inputs and Assumptions• Sensors are distributed uniformly in a squared area8Modeling Energy-consumption rate using Renewal Theorem• Renewal process– Counting process N(t): number of events happened before time t.– If the sequence of nonnegative random variable {X1, X2, …} is iid, then the counting process {N(t), t>=0} is said to be a renewal process.tX2X3X4X159Modeling Energy-consumption rate using Renewal Theorem• Renewal Reward Process– If for a renewal process, there exists an iid reward R for each inter-arrival time X, then this process is a renewal reward process.tX2X3X4X1R1R2R3R410Modeling Energy-consumption rate using Renewal Theorem• Renewal Reward Theorem– Long run rate of reward)()())(()(limXEREttREttRt==∞→∑==)(1)(tNnnRtR611Modeling Energy-consumption rate using Renewal Theorem• Define a renewal reward process with respect to a sensor– Cycle X: A cycle begins when a sensor decides to be a cluster head– Reward R: Energy consumed in each cycle.– Long run energy consumption rate)()())(()(limXEREttREttRt==∞→12Modeling Energy-consumption rate using Renewal Theorem• Remaining problem– E(X): Expected time between 2 adjacent moments when the sensor decides to be a cluster head• It should be expressed in number of rotation intervals– E(R): Expected energy consumed in the cycle.713Modeling sensor state using Markov Chain• How to generate cluster head?– P: the desired percentage of cluster heads– r : the current round– G: set of nodes that have not been cluster-heads in the last 1/P rounds– Node i generate a random number – Node i become cluster head if∈−=Otherwise 0 If )1mod(1)(GnPrPPnT)1,0(~ Uri)(nTri≤14Modeling sensor state using Markov Chain• Define state variable s = number of rotational intervals that the sensor has not been a cluster head yet– S=0 means the sensor is a cluster head– Define n=1/P0 1 n n+111 1P1-P12n-1P/(1-P)1-P/(1-P)815Modeling sensor state using Markov Chain• Steady state distribution–P=0.05–1/P=20– Long run probability that a sensor becomes a cluster head is– E(X) = 1/0.0328 = 30.5 rotational intervals 0.03280=π16Modeling sensor state using Markov Chain3 5917Modeling energy consumed in a single rotation interval• Energy consumed in a single cycle– Define M as energy consumed in a single rotational interval as a cluster member– Define H as energy consumed in a single rotational interval as a cluster head– Remaining problem: E(M) and E(H)? )()(5.29 )()()1)(( )())1(()(HEMEHEMEXEHEMXERE+=+−=+−=18Modeling energy consumed in a single rotation interval•E(M)– Recall that k bit data send for each rotation interval – and assume that the transmission distance between the sensor and the nearest cluster head is D,– What is the probability density function f(a)?2),()|( kDkEDkEDMEampelecTxε+==∫∫∞∞+===020)()()|()( daafakkEdaafaDMEMEampelecε1019Modeling energy consumed in a single rotation interval•E(M)→f(a) →– D is related to cluster number N–Define D1,.., DNbe the distances between the sensor and the cluster heads.– Recall that cluster head 1,…,N are uniformly distributed in the square and iid∏=>=>NiiaDPNaDP1}{}|{}{ aDP >}{}){1()()( aDPdadaDPdadaFdadaf >−=>−==NaDPNaDP }){(}|{1>=>20Modeling energy consumed in a single rotation interval•E(M)→f(a) →→– What is the distribution of N?• Binomial– Remaining problem}{1aDP >}{ aDP > }|{ NaDP >nnnnNP−−==10000)1(100}{ππ∑=−−=>=>100110000)1(100}|{}{nnnnnNaDPaDPππ1121Modeling energy consumed in a single rotation interval• E(M) →f(a) →→ →}{1aDP >a)()(1}{1squareAreasquarecircleAreaaDP∩−=>}{ aDP > }|{ NaDP >22Modeling energy consumed in a single rotation interval• E(H): Expected energy if the sensor function as a cluster head during a rotation interval– Total energy = Energy spent on receiving + Energy spent on transmission– Define Z be number of sensors in the clusters – Define b be the distance between the sensor and the access point– Define γ be the compression ratioZkbkZEZHEampelecγε2)|( +=1223Modeling energy consumed in a single rotation interval• E(H)→E(H|Z)→P{Z=z}¦¦¦====+==+====99029902990)()( )()( )()|()(zampeleczampeleczzZzPkbkEzZPZkbkZEzZPzZHEHEγεγε24Modeling energy consumed in a single rotation interval• E(H)→E(H|Z)→P{Z=z} P{A|(x,y),N=2}– Related factors: N, number of cluster– Position of the other cluster heads– Define (x, y) be position of one of the cluster heads– x~U(0,d), y~U(0,d) – Define event A = a sensor choose the sensor as the closest cluster head)() (2}Ny),(x,|A{squareArearegionblueAreaP==(x, y) The sensor1325Modeling energy consumed in a single rotation intervalE(H)→E(H|Z)→P{Z=z} P{A|(N=2)}→P{A|(x,y),N=2}∫∫∫∫∫∫=====squaresquaresquaredxdydregionblueAreadxdydsquareArearegionblueAreadxdydyxNAPP422) (1)() (1)},(,2|{2}N | A{26Modeling energy consumed in a single rotation intervalE(H)→E(H|Z)→P{Z=z}
View Full Document
Unlocking...