Analysis of gradient-based routing protocols in sensor networks
Analysis of Gradient-based Routing Protocols in
Sensor Networks?
Jabed Faruque,Konstantinos Psounis,and Ahmed Helmy
Department of Electrical Engineering
University of Southern California,Los Angeles,CA90089
{faruque,kpsounis,helmy}@https://www.sodocs.net/doc/f04408398.html,
Abstract.Every physical event results in a natural information gradi-
ent in the proximity of the phenomenon.Moreover,many physical phe-
nomena follow the di?usion laws.This natural information gradient can
be used to design e?cient information-driven routing protocols for sen-
sor https://www.sodocs.net/doc/f04408398.html,rmation-driven routing protocols based on the natural
information gradient,may be categorized into two major approaches:(i)
the single-path approach and(ii)the multiple-path approach.In this
paper,using a regular grid topology,we develop analytical models for
the query success rate and the overhead of both approaches for ideal and
lossy wireless link conditions.We validate our analytical models using
simulations.Also,both the analytical and the simulation models are used
to characterize each approach in terms of overhead,query success rate
and increase in path length.
1Introduction
Sensor networks are envisioned to be widely used for habitat and environmental moni-toring where the attached tiny sensors sample various physical phenomena.More specif-ically,advances in the MEMS technology make it possible to develop sensors to detect and/or measure a large variety of physical phenomena like temperature,light,sound, radiation,humidity,chemical contamination,nitrate level in the water,etc.Every phys-ical event leaves some?ngerprints in the environment in terms of the event’s e?ect;
e.g.,?re increases the temperature,chemical spilling increases the contamination,nu-clear leakage increases the radiation so on.Moreover,most of the physical phenomena follow the di?usion law[13][14]with distance,i.e.,f(d)∝1
?This research has been partially supported by NSF award0435505.
2
domain-speci?c knowledge,i.e.,the information gradient about the monitored phe-nomenon.Here,we keep our focus on the routing protocols that exploit the information gradient to route a query e?ciently in sensor networks from the sink to the source.
In real life,sensors are not always perfect and are subject to malfunction due to obstacles or failures.Also,the characteristics of the sensor nodes,e.g.,limited battery life,the energy expensive wireless communication,and the unstructured nature of the sensor network,make the data-centric routing protocols based on the information gradient a challenging problem.Several routing protocols have been proposed to exploit the information gradients.These query routing protocols use greedy forwarding and can be broadly classi?ed in two categories:(1)Single-path approach[5][6][8],where the query reaches the source from the sink through a single path,and(2)Multiple-path approach[7],where the query uses multiple paths to reach the source.
In this paper,we do not aim to design new routing protocols per se.Rather,the objective of the research is the evaluation and the analysis of the general approaches to route a query using the natural information gradient in the sensor networks.In particular,we use probabilistic modeling methods to derive analytical expressions for the energy overhead and the query success rate of each approach.Also,we compare the performance of the query routing approaches using carefully selected performance metrics.Our analysis is validated through extensive simulations.For the analysis and the simulations,we only consider sensor networks with static nodes,which is usually the case for environmental monitoring,and we assume that the queries are triggered from a sink to identify the origin(i.e.,source)of the event,after the event’s occurrence. To keep the analysis simple,we ignore potential packet collisions,which can be(and usually is)e?ectively reduced by inserting a random delay time before forwarding the query packet.However,wireless link loss is considered in both the analysis and the simulations.The main contributions and?ndings of this paper include:
–Analytical models for the query success rate and the overhead of the single-path and the multiple-path approaches to route a query using the information gradients in sensor networks.Validation of the analytical models using extensive simulations.–Performance analysis of both routing approaches using the analytical models and simulations in ideal and lossy link conditions.
–In the ideal wireless link case,it is found that the multiple-path approaches are more energy e?cient than the single-path approaches when the source is relatively close to the sink.Also,the multiple-path approaches yield shorter paths than the single-path approaches.Further,as the number of malfunctioning nodes in the network increases,the query success rate of the multiple-path approaches degrades
a lot slower than that of the single-path approaches.
–In the lossy wireless link case,the query success rate of the single-path approaches drops drastically while the multiple-path approaches are quite resilient.
2Related work
Several approaches have been proposed for routing in sensor networks.The major dif-ference between the information-gradient based approach[5][6]and the?ooding[1][2] and the random-walks[3][4][9]based approaches is that the former uses the sensors measurements about the event’s e?ect for routing decisions.In[9],Servetto and Bar-renechea have shown that multiple random-walks improve load balancing and minimize latency with increased communication cost.Also,they analyzed the random-walk ap-proach in regular/irregular and static/dynamic grid topology,but they did not consider
3 the existence of information gradients.We now brie?y summarize previously proposed gradient based routing protocols.
Chu,Hausseker and Zhao propose CADR(Constrained Anisotropic Di?usion Rout-ing)mechanism[5],especially designed for localization and target tracking.CADR uses a proactive sensor selection strategy for correlated information based on a criterion that combines information gain and communication cost.CADR is a single path greedy al-gorithm that routes a query to its optimal destination using the local gradients to maximize the information gain through the sensor network.
Later work by Liu,Zhao and Petrovic[6]proposed the min-hop routing algorithm to overcome the limitation of CADR to handle local maxima and minima.The algorithm uses a multiple step look-ahead approach with single path query forwarding.Here, the initial network discovery phase determines the minimum look-ahead horizon(in hops)so that the path planning phase can avoid network irregularities.The algorithm improves the success rate of routing message with additional search cost.Also,the increase in the neighborhood size causes more communications between the cluster leaders and their neighbors.
Some recent studies on information-driven routing protocols also use the single-path approach[8].It is important to note that all the above information-driven protocols based on the single-path approach,use a proactive phase to prepare the gradient in-formation repository.In our study we analyze the performance of the query routing mechanisms without considering the cost of the proactive phase.
In[7],a multiple path exploration mechanism is proposed to discover a route or an event.It is a reactive and distributed routing mechanism to e?ectively exploit the natural information gradient repository.The protocol controls the instantiation of mul-tiple paths using a probabilistic function based on the simulated annealing concept.It uses?ooding to forward the query when no information gradient is available.The e?-ciency of the protocol depends on properly selecting the parameters of the probabilistic function.
According to[7],the di?usion information in the environment consists of a?at(i.e. zero)and a gradient information region.However,the single-path protocols are unable to forward a query in the?at information region.In this work,we only consider the performance of various routing approaches in the gradient information region,while malfunctioning sensors are uniformly distributed.
In this work,our interest is primarily focused on the systematically analyzing the performance e.g.,the query success rate and the overhead,of the single-path and the multiple-path approaches to design data centric routing protocols in the presence of a natural information gradient.In the analysis,we use a probabilistic framework to develop simple analytical models for the success rate and the overhead for both approaches in ideal and lossy wireless link conditions.We also simulate these protocols with more realistic scenarios.
3Query Routing Approaches
According to the discussion of Section2,two major approaches,(i)the single-path approach and(ii)the multiple-path approach,are used for query routing protocols to exploit the information gradients.To properly describe these routing approaches, we need to de?ne two terms:(1)Active node,a node which is currently holding the query,and(2)Candidate node,a node which has never received the query.Now,a brief description of both routing approaches is given below:
4
Single-path approach:The query follows a single path to reach the source from the sink.At each step of the query forwarding,the active node uses a look-ahead parameter r,r≥1,to collect information from all candidate nodes within r-hops.For r>1,all nodes within r?1hops need to transmit the request of the active node to gather information about the event.Note that for r=0,the single-path approach becomes a random-walk and is unable to utilize the gradient information repository.
Single-path approach based protocols can be designed in several ways using di?erent selection policies for the next active node.In our study,we consider the following two policies:
a)Basic single-path approach:In this policy,the protocol always selects the node
with the maximum information among all candidate nodes within r-hops of the active node,when the node’s information is higher than that of the active node.
This selection policy is sensitive to local maxima and arbitrarily high readings of the malfunctioning nodes that cause these local maxima.The resilience of the protocols based on this approach can be improved by using?lters to avoid such arbitrarily high readings.
b)Improved single-path approach:In this policy,the active node forwards the query to
a node having the maximum information among all candidate nodes within r-hops
of the active node.So,the information content of all candidate nodes can be less than that of the active node.Here,the query forwarding ends either at the source node or at an active node having no candidate nodes within r-hops.
Multiple-path approach:This approach forwards the query through multiple paths towards the source without any look-ahead phase.These paths may not be disjoint https://www.sodocs.net/doc/f04408398.html,ually the active nodes forward the query greedily when information level improves.In the presence of malfunctioning nodes having wrong information,the protocols based on this approach can use probabilistic forwarding.For example,the protocol proposed in[7]uses a di?usion function for probabilistic forwarding.It creates some extra paths but the protocol can adaptively change the forwarding probability to control the instantiation of these extra paths.To capture this in the analysis,the forwarding probability is considered di?erent at each step of the query forwarding.
All query routing protocols considered in this paper use unique query IDs to sup-press duplicates and to avoid loops.
4Analytical Model
In this section,we derive models to describe the characteristics of the approaches used to design information-driven routing protocols for sensor networks.
4.1Assumptions and Metrics
Let a sensor network consist of N nodes and the nodes be deployed as a regular grid as shown in Fig.1.Assume that only one event occurs and the e?ect of the event follows the di?usion law as previously described.Assume also that the information gradient is available in the whole network,i.e.,there is no?at information region. Further,consider that the malfunctioning nodes have arbitrary information and that these nodes are uniformly distributed in the network which may cause failure during
5 the route discovery.Let p f be the probability that a node is malfunctioning.The stored information in the malfunctioning node can be arbitrarily high or low and this is equally likely.Finally,assume each node is able to communicate via broadcast with its eight neighbors on the grid.
Fig.1.A regular grid topology.Here, f j indicates the magnitude of informa-tion and f0 of the j?th step Overlapped (a)A j?1and A j are the active nodes of steps(j?1)and j. Active node A j with r- hop neighbors. Fig.2.Single path approach with look-ahead r. Suppose that the querier,i.e.the sink,is located d hops away from the source node. The query is forwarded step by step,where the term“step”is de?ned as follows: 1)Single-path approach:The active node collects information from all candidate nodes within r-hops.Then it forwards the query to the next active node which is r-hops away. 2)Multiple-path approach:The active nodes forward the query either greedily or probabilistically via broadcasts.Then the query reaches the candidate nodes which are1-hop away. Due to greedy forwarding based on the information gradient,after each step of the query forwarding,the query reaches one step closer to the source with some probability. Here,we are interested to develop analytical models for the following two metrics: 1)Query Success rate,i.e.success probability,is the probability that the query initi- ated from the sink reaches the source. 2)Overhead in terms of energy dissipation,calculated as the number of transmissions required to forward the query to the source and to get the reply back from the source using the reverse path. 4.2Single-path Approach Let n b be the number of nodes that are one hop away from the active node.Overlap of the sensor nodes radio coverage causes some nodes to receive the same query multiple times.The query ID is used to suppress duplicate queries.If we consider the radio coverage of a node to be circular and the radius to be the same for all nodes,then using simple geometry,it can be shown that the overlap is one-third.For all except the ?rst step of the query forwarding,let n c=2 2and n C=2 6 Within one-hop of the active node,let n h and n l be the number of candidate nodes having high and low information respectively according to the di?usion pattern of the event’s e?ect in the grid,where n c =n l +n h .Thus,except for the ?rst step of the query forwarding,it can be shown from Fig.2that the total number of high information candidate nodes within r -hops of the active node equals n H =r (r +1)2.Finally,n L =n C ?n H denotes the number of low information candidate nodes within r -hops,since n C =n L +n H . Basic Single-path approach:At each step of the query forwarding,the proto-col selects the node that has the highest information among all nodes (including the active node)within r -hops and forwards the query to that node.When all candidate nodes function properly,the query forwarding ends at the source.However,the query forwarding also halts at a local maxima.A malfunctioning node contains arbitrarily high information with probability p f r ˇ ?j ′r ′and R max .Therefore,the probability of success equals P single B =l d 2·R max ?f ``?d R max #n C .(1) Here,the product term is the probability that at each step of the query forwarding,there is no malfunctioning candidate node having arbitrarily high information when the source is i -hops away and a total of ?d r ?“1+r 2n b +r ”+d.(2) Here,1+r 2n b +r is the required number of transmissions at each step of the query forwarding and total ?d r ??1?"1+2r 2n b 3+r transmissions for non-overlapping nodes. 7 Improved Single-path approach:In this policy,at each step of the query for-warding,the protocol selects the node with the maximum information among all can-didate nodes within r-hops of the active node and forwards the query to that node. For protocols based on this approach,the query success rate and the overhead depend on the length of the path followed by the protocol.Though the sink node is d-hops away from the source,in the presence of arbitrary information in the malfunction-ing nodes,the query may follow a path other than the shortest path.Let l j denote the length of the path after the j-th forward of the query.If all sensor nodes in the network were perfect,the query should follow the shortest path and l j?l j?1=r. However,due to malfunctioning nodes,some low information candidate nodes may contain arbitrarily high information with probability p f 2′n L 2.n L2.n L 2,high informa- tion candidate node(s)may contain arbitrarily low information which may be lower than that of some low information candidate nodes.When all high information can-didate nodes are malfunctioning and containing arbitrarily low information,the query forwarding proceeds through a low information candidate node.Such low information candidate nodes are unable to?nd any candidate node as its all neighbors may al-ready have received the query and the query fails to reach the source.Therefore,the probability of query success equals P single I =?1?…p f r?.(4) Here,1?(p f r m such steps are required. Similar to the Equation(2),here the total number of transmissions required to forward the query from the sink to the source for path length l d and get the reply equals T single I =‰l d r??1 ?"1+2r2n b 3 +r transmissions for the non-overlapping nodes. 8 4.3Multiple-path Approach In this routing approach,except for the?rst step of the query forwarding,multiple active nodes may forward the query to the candidate nodes without any look-ahead phase.The active nodes with lower information forward the query probabilistically. Let p j denote the probability of forwarding the query probabilistically at the j-th step of the query forwarding.So,at the j-th step of the query forwarding,a high infor- (a)Sink at i=0. (b)Sink at i=1. (c)Sink at i=d?1. (d)Sink at i=d. Fig.3.Query forwarding pattern using the multiple path approach.Depending on the position of the sink patterns are di?erent.Here,the white dots indicate the participating nodes to forward the query towards the source and d is the distance between the source and the sink. mation candidate node fails to forward the query with probability q j=`p f 2′is the probability that the high information candidate node is malfunc-tioning and containing low information.For simplicity of the analysis,we assume that the query forwarding steps are independent.This simpli?ed model still captures the characteristics of the multiple-path approach,while the analysis is kept tractable. Let P multiple and T multiple denote the query success rate and the overhead of the multiple-path approach.Consider that i denotes the position of the querier,i.e.the sink,in the last row of the grid as shown in Fig.1and Fig.3.The query forwarding patterns,i.e.the number of participating nodes,are di?erent for di?erent values of i as shown in Fig.3.Also,it is easy to show that according to the di?usion pattern in the grid,the average number of low information candidate nodes is four at each step of the query forwarding.These nodes forward the query probabilistically. According to the query forwarding patterns as shown in Fig.3,for an even value of i,0≤i≤d,the query success probability equals P multiple e (i)=(1?q1)· 26 4d?i2“1?q i+1m+1(1?p m+1)4”37 5·i 2 ?≤m≤d??i 2?in the?rst and the second products respectively).Here,the terms having the form q x y,1≤y≤d,in the above equation expresses the probability of not forwarding the query at the y-th step by all high information candidate nodes,x,as they are malfunctioning and containing less information.Also,the surrounding four low information candidate nodes fail to forward the query with probability(1?p y)4.Thus, at the y-th step,1?q x y(1?p y)4is the probability of forwarding the query towards the 9 source.Detailed derivation of these equations and all the equations of the remaining document are presented in [15]. Similarly,to compute the energy dissipation,we also consider the di?erent forward-ing patterns of the query as shown in Fig.3.The total number of transmissions required to forward the query to the source for an even value of i ,0≤i ≤d ,equals T multiple e (i )="i 22X m =1 (2m ?1)q m +i 2+m 375+4d X m =1p m +1,(7) and for an odd value of i ,0≤i ≤d ,it equals T multiple o (i ),where the di?erences with Equation(7)are the ?rst term ( h (i +1)22,1≤m ≤i +1 d +1264?d 2?X k =1P multiple o (2k ?1)375.(8) Similarly,the average number of transmissions required to forward the query from the sink to the source and get the reply using the reverse path equals T multiple =12?X k =0 T multiple e (2k )+ ?d 10 Improved Single-path approach:Due to the lossy links,at each step of the query forwarding,the broadcast of the active node may not reach to all candidate nodes within r-hops.Thus,at each step of the query forwarding,n H(1?p c)high information candidate nodes receive the broadcast.Similarly,the active node receives responses from n H(1?p c)2high information candidate nodes.Also,the probability to forward the query to the next active node,which is r-hops away,is(1?p c)r.Thus,for the improved-single path approach,the probability of success equals P single I c =" 1?…p f r ? .(10) Here,“1?`p f r m such steps are required. In this routing approach,the?rst step of the query forwarding requires1+r(r?1) 2n b(1?p c)+r(1?p c)transmissions,which equals1+r(1?p c)(rn b+1). With probability p c,the nodes of the overlapped region can be candidate nodes of the current active node as they failed to receive the broadcast of the previous active node due to the lossy links.Further,consider that the overlapped region nodes re-spond only one time.So,each remaining step of the query forwarding requires1+ 1 2n b(1?p c)+r(r+1) 3h r(r?1)2n b(1?p c)i+ r 3 r2(1?p c)?n b(p c+2)+3 r??1 ?·?1+1r?–+l d 1?p c transmissions. Multiple-path approach:In this approach,multiple active nodes forward the same query to the candidate nodes and reduce the possibility of the failure due to the wireless link loss.Since,the probability of lossy links,p c is small,so in the analytical models,we consider that1?p n c≈1,n≥2,where n is the number of copies of the same query received by a candidate node.Results with this assumption are later compared to (and validated with)simulations in Section5.5.Now,according to the query forwarding patterns as shown in Fig.3,for an even value of i,0≤i≤d,the success probability equals P multiple e c (i)=(1?q1)264d?i2“1?q i+1?p c m+1(1?p m+1)4+3p c” 37 5· i 2 ?≤m≤d??i 2 ?for the?rst and the second products respectively)Here,the terms having 11 the form1?q x y(1?p y)z in the above equation expresses the probability of forwarding the query at the y-th step of the query forwarding,where x and z are the number of nodes that perform greedy and probabilistic forwarding respectively. Similarly,to compute the overhead,we consider the di?erent forwarding patterns of the query as shown in Fig.3.Due to the lossy links,the query may fail to reach some nodes.So the overhead reduces due to the less number of participating nodes. Thus,using the Equations(7),the total number of transmissions required to forward the query to the source for an even value of i,0≤i≤d,equals T multiple e c (i)=T multiple e (i) ?p c2642i2+m?+4i2+m+2i 2,1≤m≤d?i+1,2≤m≤i 2 ?1 respectively).Here,the second term of the above equation computes the overhead reduction due to the lossy links. Now,similar to the Equation(8)and(9),the average success probability and the average number of transmissions can be computed.Here,the reply to the sink through the reverse path requires d 12 The querier,i.e.,the sink,and the source are di?erent and can be any node.We use a ?ooding technique to ?nd the set of sink nodes that are speci?c shortest distance away from the source.In the simulations,we use only single-value queries,that search for a speci?c value and have a single response. The simulated protocol based on the single-path approach uses a look-ahead pa-rameter r =1.For r =1,it can be easily shown from Fig.1that n B =8,L err ≈2and n H ≈2.5.So,using the expressions of Section 4.2,we get n C =2 j β,where j is the hop count in the information gradient region and β<α. 5.2Query Success Rate i.e.,Probability of Success The basic single-path approach is not resilient to local maxima.The query success rate 0 0.2 0.4 0.6 0.8 1 0 10 20 30 40 50 60 70 P (s u c c e s s ) Distance of the source Err=0% (A)Err=5% (A)Err=10% (A)Err=15% (A)Err=0% (S)Err=5% (S)Err=10% (S)Err=15% (S)Fig.4.Query success rate of the basic single-path approach.‘A’and ‘S’indicate the analytical and the simulation results respectively. 0.86 0.88 0.9 0.92 0.94 0.96 0.98 1 0 10 20 30 40 50 60 70P (s u c c e s s )Distance of the source Err=0% (A)Err=5% (A)Err=15% (A)Err=0% (S)Err=5% (S)Err=15% (S) Fig.5.Query success rate of the improved single-path approach. of the protocol based on this approach is shown in Fig.4,where the analytical result closely matches with the simulation result.With the increase of malfunctioning nodes,local maxima increases and the query success rate drops close to zero.However,using a ?lter to avoid the nodes having arbitrarily high information,the query success rate of this approach can be improved.Detailed derivation for the ?lter and corresponding simulation results are presented in [15].Also,The remaining results of the performance analysis of this approach are detailed in [15]. For the improved single-path approach,the query success rate of the routing pro-tocols depends on the availability of high information candidate nodes.From Fig.5,it is obvious that the analytically results are more or less in line with the simulation results.The number of high information candidate nodes reduces with the exploration of more nodes,especially for large d and causes some minor di?erences between the analytical and the simulation results.The improved single-path approach is resilient to local maxima due to its selection policy for the next active node.So,the query success rate of this approach is signi?cantly higher than that of the basic single-path approach. In the analytical model for the multiple-path approach,we consider that each step of the query is independent,and that low information candidate nodes forward the query probabilistically.However,due to correlation with previous steps of the query 13 0.9 0.92 0.94 0.96 0.98 1 0 10 20 30 40 50 60 70P (s u c c e s s )Distance of the source Err=0% (A)Err=5% (A)Err=10% (A)Err=15% (A)Err=0% (S)Err=5% (S)Err=10% (S)Err=15% (S)Fig.6.Probability of success for the multiple path approach.The exponent of the probabilistic function β=0.65. 0.86 0.88 0.9 0.92 0.94 0.96 0.98 1 0 10 20 30 40 50 60 70 P (s u c c e s s )Distance of the source Err=0% (multi)Err=5% (multi)Err=15% (multi)Err=0% (single)Err=5% (single)Err=15% (single)https://www.sodocs.net/doc/f04408398.html,parison of the query success rate of the improved single-path and the multiple-path routing approaches using analytical results. (Simulation results yield very similar plots.) forwarding,some extra nodes may also forward the query and create few more extra paths,which actually improve the query success rate when less number of nodes are malfunctioning.Also,with the increase of malfunctioning nodes,active nodes use more probabilistic forwarding that results less number of paths and the query success rate drops.For these reasons,we notice some minor di?erence between the analytical and the simulation results in Fig.6. The use of multiple paths and the probabilistic forwarding in the presence of mal-functioning nodes improves the query success rate of the multiple-path approach with compare to that of the single-path approach as shown in Fig.7.For the single-path ap-proach,it is important to notice that the query success rate drops fast as the number of the malfunctioning nodes in the network increase. 5.3Overhead i.e.,Energy Dissipation Fig.8shows the overhead in terms of the average energy dissipation of the improved single-path approach.In both models,the overlapped region nodes respond only one time.The analytical and the simulation results are very similar.The minor discrepancy is due to following reason.With the exploration of more nodes,the number of high information candidate nodes reduces and the path length increases due to choosing the malfunctioning nodes to forward the query. 0 100 200 300 400 500 600 700 800 900 0 10 20 30 40 50 60 70A v e r a g e e n e r g y d i s s i p a t i o n Distance of the source Err=0% (A)Err=5% (A)Err=10% (A)Err=15% (A)Err=0% (S)Err=5% (S)Err=10% (S)Err=15% (S)Fig.8.Overhead for the single path approach.‘A’and ‘S’indicate the analytical and the simu-lation results respectively. 0 500 1000 1500 2000 2500 0 10 20 30 40 50 60 70 A v e r a g e e n e r g y d i s s i p a t i o n Distance of the source Err=0% (A)Err=5% (A)Err=10% (A)Err=15% (A)Err=0% (S)Err=5% (S)Err=10% (S)Err=15% (S)Fig.9.Overhead for the multiple path ap-proach.The exponent of the probabilistic func-tion is β=0.65. 14 Both analytical and simulation results for the overhead of the multiple-path ap-proach are given in Fig.9.The analytical results are quite close to the simulation results with a small discrepancy.In the analytical model,we assume that the sink is located at the last row of the grid i.e.,an edge node as shown in Fig.1and 3.However,in our simulation scenarios,the sink is not always at an edge node and the initial high value of the probabilistic function causes the exploration of some nodes in the low information gradient region.Also,as we have already explained in Section 5.2,due to correlations between the query forwarding steps,this routing approach creates some extra paths and increases the overhead which is not considered in the analytical model.Thus,simulation results show sightly more overhead than the analytical results. In Fig.10,the overhead of both approaches is compared using the analytical results.It is obvious that in our model,if the source is less than 22hops away from the sink 0 500 1000 1500 2000 2500 0 10 20 30 40 50 60 70A v e r a g e e n e r g y d i s s i p a t i o n Distance of the source Err=0% (multi)Err=5% (multi)Err=10% (multi)Err=15% (multi)Err=0% (single)Err=5% (single)Err=10% (single)Err=15% (single)https://www.sodocs.net/doc/f04408398.html,parison of the overhead of the improved single-path and the multiple-path ap-proaches using analytical results.-40 -20 0 20 40 5 10 15 20 25 P e r c e n t a g e o f t h e e n e r g y s a v i n g Distance of the source Err=0% (A)Err=5% (A)Err=10% (A)Err=15% (A)Err=20% (A)Fig.11.Percentage of energy saving of the mul-tiple path approach over the improved single-path approach for d ≤25using analytical models.then the multiple-path approach is more energy e?cient;otherwise,the single path approach is preferable when energy dissipation is only considered.The overhead of the multiple-path approach increases more due to the extra paths created by probabilistic forwarding. Using analytical models,the percentage of energy savings of the multiple-path approach over the single-path approach is shown in Fig.11.As the number of malfunc-tioning nodes increase,the overhead of the single-path approach increases.Since,the length of the path followed by this approach increases.On the other hand,with the increase of malfunctioning nodes,the multiple-path approach uses more probabilistic forwarding.This creates less number of paths,and the overhead reduces. 5.4Path Quality Fig.12shows the path length increase factor of both routing approaches.The multiple-path approach results the shorter paths which are very close to the shortest path length.We notice that the path length for the single-path approach increases with the increase of the malfunctioning nodes.As expected,in the presence of malfunctioning nodes,the single path approach fails to follow the shortest path towards the source.On the other hand,the instantiation of multiple paths and probabilistic forwarding help the multiple path approach to alleviate the problem for malfunctioning nodes. 15 P a t h l e n g t h i n c r e a s e f a c t o r Distance of the source Fig.12. Path length increase factor for the improved single-path and the multiple-path ap-proaches.The exponent of the probabilistic func-tion β=0.60. 0 0.2 0.4 0.6 0.8 1 0 10 20 30 40 50 60 70P (s u c c e s s )Distance of the source p c =0% (A)p c =1% (A)p c =3% (A)p c =5% (A)p c =7% (A)p c =0% (S)p c =1% (S)p c =3% (S)p c =5% (S)p c =7% (S)Fig.13.Query success rate of the improved single-path approach with the varying lossy link conditions.The probability of malfunctioning nodes is p f =0.05.5.5Wireless Link Loss E?ect So far,all the results presented in Section 5consider ideal wireless links.However,the wireless links are lossy and likely a?ect the query success rate of the routing protocols 0 0.2 0.4 0.6 0.8 1 0 10 20 30 40 50 60 70P (s u c c e s s )Distance of the source Err=0% (multi)Err=5% (multi)Err=10% (multi)Err=15% (multi)Err=0% (single)Err=5% (single)Err=10% (single)Err=15% (single)(a)Using analytic models. 0 0. 2 0.4 0.6 0.8 1 0 10 20 30 40 50 60 70 P (s u c c e s s ) Distance of the source Err=0% (multi)Err=5% (multi)Err=10% (multi)Err=15% (multi)Err=0% (single)Err=5% (single)Err=10% (single)Err=15% (single)(b)Using simulation models. https://www.sodocs.net/doc/f04408398.html,parison of the query success rate of the improved single-path and the multiple-path approaches in the presence of link loss,p c =0.05.The exponent of the probabilistic function β=0.65. signi?cantly.Fig.14shows the query success rate of both approaches in the presence of lossy links with probability p c =0.05.Here,the analytical (Fig.14(a))and simulation (Fig.14(b))results are identical.In both cases,the query success rate of the multiple-path approach drops quite slowly and it is more than 93%even at the presence of 15%malfunctioning nodes in the sensor network.The ability to send the same query from multiple active nodes towards a candidate node improves the resilience of this approach signi?cantly. For the improved single-path approach,the query success rate drops drastically with the increase of the distance between the source and the sink.Also,Fig.13shows that the query success rate drops further with the increase of loss probability of the lossy links,i.e.,p c .From Equation (10),it is obvious that the term (1?p c )r ,which corresponds to forwarding the query from the current active node to the next active node in the presence of lossy links,is responsible for the low success rate of this https://www.sodocs.net/doc/f04408398.html,ing ARQ,the query success rate can be improved signi?cantly [15]. 16 6Summary and Conclusions In this paper,we have presented a detailed performance analysis of information-driven routing approaches in ideal and lossy wireless link conditions using analytical models and simulations.We consider the e?ect of(various kinds of)noise,malfunctioning nodes and node failures in our analysis. From our study,it is found that the query success rate of the single-path approach drops quite fast as the number of malfunctioning nodes in the network increase while the multiple-path approach retains very high query success rate.Also,it is found that the multiple-path approach is more energy e?cient when the source is less than22 hops away from the sink;otherwise,the single-path approach is more energy e?cient. For example,in Fig.11,for5%malfunctioning nodes and a source15hops away from the querier,the overhead of the multiple-path approach is only75%of that of the improved single-path approach.Further,the multiple-path approach results in shorter paths which are close to the shortest path.Finally,in the lossy link case,the query success rate of the single path approach drops drastically with the increase of the link loss probability and the distance between the source and the querier.On the other hand,the multiple-path approach achieves over93%success rate even at the presence of15%malfunctioning nodes in the sensor network. The analytical models of both routing approaches can be used to determine the performance and the bottleneck of a protocol for a large sensor network without sim-ulations or when simulations are not possible due to resource constraints.Further, the performance of a new protocol,based on either of these two approaches,can be determined using our models. From the analytical models,it is obvious that more e?cient information-driven routing protocols can be designed based on these two approaches by tuning the pa-rameters of the models,which can be one possible future research direction. References 1. C.Intanagonwiwat,https://www.sodocs.net/doc/f04408398.html,indan and D.Estrin,“Directed Di?usion:A Scalable and Robust Communication Paradigm for Sensor Networks”,MobiCom2000. 2. C.Intanagonwiwat,D.Estrin,https://www.sodocs.net/doc/f04408398.html,indan,and J.Heidemann,“Impact of Network Density on Data Aggregation inWireless Sensor Networks”,ICDCS’02. 3. D.Braginsky and D.Estrin,“Rumor Routing Algorithm for Sensor Networks”,WSNA2002. 4.N.Sadagopan,B.Krishnamachari,and A.Helmy,“Active Query Forwarding in Sensor Networks (ACQUIRE)”,SNPA2003. 5.M.Chu,H.Haussecker,and F.Zhao,“Scalable Information-Driven Sensor Querying and Rout- ing for ad hoc Heterogeneous Sensor Networks”,Int’l J.High Performance Computing Appli-cations,16(3):90-110,Fall2002. 6.J.Liu,F.Zhao,and D.Petrovic,“Information-Directed Routing in Ad Hoc Sensor Networks”, WSNA2003. 7.J.Faruque,A.Helmy,“RUGGED:RoUting on?nGerprint Gradients in sEnsor Networks”, IEEE International Conference on Pervasive Services(ICPS),2004. 8.Q.Li,M.D.Rosa and D.Rus,“Distributed Algorithms for Guiding Navigation across a Sensor Network”,MobiCom2003. 9.S.D.Servetto and G.Barrenechea,“Constrained Random Walks on Random Graphs:Routing Algorithms for Large Scale Wireless Sensor Networks”,WSNA2002. 10.Fan Ye,Gary Zhong,Songwu Lu and Lixia Zhang,“GRAdient Broadcast:A Robust Data Delivery Protocol for Large Scale Sensor Networks”,ACM WINET(Wireless Networks). 11. A.Woo,T.Tong,and D.Culler.“Taming the Underlying Issues for Reliable Multhop Routing in Sensor Networks”.ACM SenSys,November2003. 12.J.Zhao and https://www.sodocs.net/doc/f04408398.html,indan.“Understanding Packet Delivery Performance in Dense Wireless Sensor Networks”.ACM Sensys,November2003. 13. D.R.Askeland,The Science and Engineering of Materials,PWS Publishing Co.,1994. 14.J.F.Shackelford,Intro to Materials Science For Engineers,5th Ed.,Prentice Hall,2000. 15.J.Faruque,K.Psounis,A.Helmy,“Analysis of Gradient-based Routing Protocols in Sensor Networks”,CS Technical report,USC2005.