Alonso Bounds Energy Consumption

Bounds on the Energy Consumption of Routings in Wireless Sensor Networks Juan Alonso1 , Adam Dunkels1,2 , and Thiemo Voigt1 SICS, Swedish Institute of Computer Science, Stockholm Sweden Dept. of Comp. Sci. and Engineering, M¨alardalen University, Sweden 1

2

E-mail: [email protected]

Abstract. Energy is one of the most important resources in wireless sensor networks. We use an idealized mathematical model to study the impact of routing on energy consumption. We find explicit bounds on the minimal and maximal energy routings will consume, and use them to bound the lifetime of the network. The bounds are sharp and can be achieved in many situations of interest. Our results apply to sensor networks with a continuous data delivery model, in which all sensors transmit with the same power. Within this class, the results are very general as they apply to arbitrary topologies, routings and radio energy models. We illustrate the theory with some examples. Among these, there is one contradicting the popular belief that it is always the nodes deployed nearest to base nodes that are the most heavily loaded and, hence, the ones that die first.

1

Introduction

Recent technological advances have made the production of small and inexpensive wireless sensor devices possible, prompting a flurry of research and experiment. The starting point for this paper was a statement by Mainwaring et al. [1], one of the initial exciting deployments of this type of sensors. When discussing different routing algorithms, the authors write (in Section 6.2): ”Although these methods provide factors of 2 to 3 times longer network operation, our application requires a factor of 100 times longer network operation...”. We thought this was intriguing: What factor is reasonable to expect of a routing algorithm? Typically, communication is the most expensive activity in terms of energy [2]. In this paper we focus on the energy consumed in communication (only the energy required to receive and send data is considered), regardless of the particular routing scheme used, and address questions such as: How much improvement in the lifespan of a network can be expected by changing only the routing algorithm? Which factors (as far as routing is concerned) affect the network’s lifespan the most? How good is my favorite routing? There is a vast literature relating energy consumption to routing, see for instance [4], [5], [6]. With few exceptions (see e.g. [3]) this previous work has concentrated on the performance of specific routing algorithms. In this paper we use an idealized mathematical model to quantify the fundamental role played by the spheres of different radii in determining the energy consumption of routings in networks satisfying the assumptions of Section 2 below. We use these results to obtain explicit bounds on the lifetime of the network. Within the framework of these simplifying assumptions, our results are very general and apply regardless of the topology, routing algorithm, or radio energy model used. This allows us to make general remarks as to what it takes to reach the optimum

value (see the discussion preceding Theorem 1 in Section 4, and Section 6). We also give some examples to illustrate the theory developed. Among these, Example 2 below is particularly interesting because it contradicts the popular belief that the nodes deployed nearest to base nodes are always the most heavily loaded and, hence, the ones that die first. We have recently learnt [7], [8] that Mhatre et. al. have used the sphere of radius 1 to study energy consumption in wireless sensor networks. These authors consider a twotiered hierarchical architecture, with lifetime constraints, and an object function that includes hardware costs, in order to optimize the ratio between sensing nodes and cluster heads. In [7], where the nodes are deployed in square grids, the authors simply state that the nodes nearest a base node are the most heavily loaded ones. This statement is true [11], but it takes some proving (about two pages). In [8], where the nodes are randomly deployed, the same statement is made, and a few lines justification is provided (Section III.C of [8]). As already mentioned, Example 2 in Section 6 below, is a counter example. The paper is organized as follows. Section 2 summarizes the assumptions we make on the sensor networks. Routings and the way we measure energy consumption are defined in Section 3. Section 4 contains Theorem 1, the main theoretical result of the paper, giving explicit lower bounds on the energy consumption of routings. These results are applied in Section 5 to bound the lifetime of a sensor network. In Section 6 we give examples to illustrate the theory developed in the previous sections. The final Section 7 presents conclusions and future work. Finally, we would like to thank Laura M. Feeney and the referees for carefully reading the paper and making interesting comments and questions.

2

Assumptions on the sensor network

We assume the nodes in the network are of two types: sensor nodes and base nodes. Sensor nodes (or, simply, nodes) are low-energy and have very limited memory and processing capabilities, whereas base nodes are high-energy and have significantly more processing power and memory capacity than sensor nodes. We make the assumption that there is an underlying hierarchic architecture whereby the base nodes control the sensor nodes deciding, in particular, which routing to use. We use the term routing to denote a specific set of paths (or multi-paths) that packets take through a network. A routing is the result of the particular routing algorithm used. The sensor nodes take readings and send them to the bases using other sensor nodes to reach them i.e., communication occurs in a multi-hop fashion. This process is iterated until nodes die, eventually breaking connectivity and making the network non-operational. While time is not an explicit parameter in our model, we do implicitly assume a weak form of synchronization: Each iteration takes a certain amount of time that may be different for different iterations, and within each time interval every node makes its reading and transmission/reception. Observe that the time each iteration takes may vary from seconds to days or even months. There is no assumption that any of these events occur simultaneously. These assumptions are suitable for sensor networks with a continuous data delivery model. Recall that in the taxonomy of Tilak et. al. [9], sensor networks are classified in accordance to their data delivery model into continuous, event-driven, observer-initiated and hybrid. Continuous networks are those in which ”the sensors communicate their

data continuously at a pre-specified rate”. The deployment at Great Duck Island [1] is an example of continuous network. We restrict the class of continuous sensor networks by further assuming that during the whole process all nodes transmit at the same, constant power. Moreover, no data aggregation is done in the network: all data gathered is sent unchanged to the base nodes. The restriction that all nodes transmit at the same constant power simplifies the mathematics. We believe that this hypothesis can be relaxed, but this is the subject of future work. Data aggregation is certainly an important way to save energy and to extend the lifetime of sensor networks. We left it out of our analysis because our main interest is in the effect that routing has on energy consumption. We also felt that data aggregation is too intimately related to specific applications.

3

Routings and their energy consumption

We model the network by a directed graph G = (V, E). Given a link e = (v, w), we let e = (w, v) denote the reverse link. The hypothesis that all nodes transmit with the same power implies that if e ∈ E then also e ∈ E. We assume given a set B ⊆ V of base nodes with 0 < |B| < |V |. The network operates with the following traffic pattern. For each iteration t, 1 ≤ t ≤ T , every node sends a packet of a certain length to some base node. Informally, each way to do this is a routing. More formally, a routing is a vector y = (yet )1≤t≤T, e∈E where yet represents the total number of packets destined to some base node that are sent through e during the t:th iteration. Observe that we can think of the routing y as being a sequence y = (y 1 , . . . , y T ), where y t is the routing used during the t:th iteration. The only restriction we place on routings is that they should be effective, in the sense of not having loops. A routing has no loops if for all 1 ≤ t ≤ T the following holds: for every node, the directed path used to send its packet to a base node never visits a node more than once. Let RT = {y = (yet )1≤t≤T, e∈E | y is a routing with no loops} The energy consumption of a routing y will be measured by the following cost function f T : R T → R+ : f T (y) = maxv∈V {

T X t=1

(

X e∈I v

ρyet +

X

τ yet )}

(1)

e∈Ov

where ρ [resp. τ ] is the cost for the reception [resp. transmission] of one packet, I v is the set of incoming links of v, I v = {(i, j) ∈ E|j = v}, and Ov is the set of outgoing links of v, Ov = {(i, j) ∈ E|i = v}. Thus, f T (y) measures the maximum energy used by nodes when transmitting and receiving according to routing y. In using f T we are disregarding the energy consumption of base nodes. This is in line with the assumption that base nodes have no shortage of energy. When T = 1 we write simply f (y). Observe that we disregard the routing protocol overhead and concentrate instead on the energy consumption of the

application related communication. We think this is a reasonable simplification to make in sensor networks with a continuous data delivery model. In practice, this situation is achieved when the network, after an initial set up phase, reaches a steady state. Notice that the condition that there is no data aggregation in the network implies that all the routings we consider conserve flow. This can be expressed rigorously as follows. For all t and every v that is not a base node, the equations X

yet = 1 +

e∈Ov

X

yet

e∈I v

hold. Indeed, the left-hand side computes the number of packets sent by v during iteration t, while the right-hand side equals one (the packet produced and sent by v at each iteration) plus the number of packets received by v during iteration t.

4

How parsimonious is my favorite routing?

Set mT = miny∈RT f T (y), and M T = maxy∈RT f T (y). We thus have, for an arbitrary routing y ∈ RT , mT ≤ f T (y) ≤ M T . When T = 1 we write simply m, M . In this section we find bounds on the size of the interval [mT , M T ]. For this purpose, we partition the set of nodes into subsets S0 , . . . , Sn satisfying V = S0 ∪ S1 · · · Sn , Si ∩ Sj = ∅ for all i 6= j, and no Si is empty. The definition of the Si is as follows: S0 = B, and for i > 0, Si is the set of nodes can be reached in i hops, but not less than i hops, from some node in S0 (i.e. Si is the ”sphere” of radius i around S0 ). Thus, |V | = |S0 | + |S1 | + · · · + |Sn | and all |Si | > 0. Notice that n ≥ 1, since |B| < |V |. Corresponding to the spheres Si , there are ”balls” of radius i, denoted Bi , and defined by Bi = S0 ∪ · · · ∪ Si . It will be convenient to introduce the following notation: si = |Si |, bi = |Bi |, and N = |V |. Finally, for i = 1, . . . , n, we set: mi =

N − bi N − bi + s i ·ρ+ ·τ si si

(2)

Note that N − bi is the total number of nodes lying outside Bi . This number coincides with the number of packets that has to go through Si during each iteration, and also with the number of packets that the nodes of Si have to receive. Thus (N − bi )/si is the average number of packets received by each node of Si . We see that mi measures the energy cost incurred by a node of Si when it receives the average and transmits this average plus one (its own packet). These constants are interesting because of Theorem 1 below. Inequalities (i)-(iii) of the theorem can be seen as providing fundamental limits to the possible amount of improvement in energy consumption that can be derived from changes in the routing algorithm, and benchmarks to compare your favorite routing(s) against. The strength of Theorem 1 derives from its generality, as its results apply to any graph, routing, and radio energy model. In view of the theorem, equality holds in (ii) (and, hence, the optimal value mT is equal to T · mi for some i) when there is a routing capable of balancing traffic evenly among the nodes of Si . See Section 6 for further remarks and examples relating to Theorem 1. Theorem 1. With the notation above,

i) ii) iii) iv)

M T ≤ T · [ρ · (N − s0 − 1) + τ · (N − s0 )] = T · [(ρ + τ ) · (N − s0 ) − ρ] mT ≥ T · max {m1 , . . . , mn } M T ≤ s1 · mT + T · ρ · (s1 − 1) mn = τ .

Proof. Notice first that (iv) follows immediately from the definitions, since N = bn . P Next, for arbitrary v ∈ V and y ∈ RT , recall that for all t, e∈I v yet is the total number P of packets received by v during iteration t and, likewise, e∈Ov yet is the total number of packets transmitted by v during iteration t. We claim these numbers cannot exceed the total number of packets being sent throughout the network at each iteration, i.e. N − s0 packets transmitted and N − s0 − 1 packets received. This is true because y has no loops and hence v will receive and send at most one packet for every non-base node. (i) follows immediately from this. To prove (ii) it suffices to prove that mT ≥ T · mi , for all 1 ≤ i ≤ n. The idea of the proof is to consider Si as a bottleneck for nodes outside Bi trying to reach S0 . More formally, notice that in every routing, packets in V \ Bi−1 can only reach S0 by either going through Si (i.e. these packets originate outside of Bi and, hence, are both received and transmitted by some element of Si ) or by being transmitted by some node in Si (i.e. these packets originate at Si ). Thus at each iteration, the nodes in Si must receive N − bi packets, and they must transmit N − bi + si packets . For every y ∈ R we have: f T (y) ≥ maxv∈Si {

T X t=1

≥ρ·T ·

(

X

X

ρ · yet +

e∈I v

τ · yet )}

e∈Ov

N − bi + si N − bi +τ ·T · = T · mi si si

(3)

Inequality (3) follows from Lemma 1 below. Indeed, by the discussion above, we have P P P P P P t t v∈Si ( t e∈I v ρ · ye ) = T · ρ · (N − bi ), and v∈Si ( t e∈Ov τ · ye ) = T · τ · (N − bi + si ). Adding these two sums and applying Lemma 1 yields (3), as desired. Next, since f T (y) ≥ T · mi holds for all y ∈ R, we obtain mT ≥ T · mi , as desired. Finally, using (i) and T · m1 ≤ mT , we get M T ≤ T · ρ · (N − s0 − 1) + T · τ · (N − s0 ) = T · ρ · (N − b1 ) + T · ρ · (s1 − 1) + T · τ · (N − s0 ) = T · m1 · s1 + T · ρ · (s1 − 1)

(4)

This completes the proof of (iii) and of the theorem. Lemma 1. Let I denote a finite set. If

P i∈I

Ai = a, then

max{Ai |i ∈ I} ≥

a |I|

Proof. Suppose, for contradiction, that the conclusion of the Lemma is false. Then Ai < P P a/|I|, for all i ∈ I. But then I Ai < I a/|I| = a, contradicting the hypothesis. This proves the lemma. It is meaningful to distinguish two cases in Theorem 1, according to whether or not n = 1. We consider first the rather trivial case when n = 1, i.e. when all nodes are one hop

away from a base node. The network deployed in Great Duck Island [1] in the summer of 2002 was of this type; the one deployed in 2003 was multi-hop [10]. Inequality (ii) in Theorem 1 reduces to mT ≥ T · τ , i.e. the minimal energy use after T iterations is the transmission cost times T . It is easy to find an optimal routing, i.e. a routing achieving this minimum: for each node, select a unique base node one hop away, and transmit the node’s unique packet to the chosen base node; repeat T times. In this case, the upper bound for M T , T · [(ρ + τ ) · s1 − ρ], can be achieved if, for instance, the non-base nodes can use each other to transmit their packets to a specified non-base node that receives all the packets minus its own, and transmits all s1 packets to a base node. Summarizing: Corollary 1. In the special case when every node is only one hop away from a base node, we have: i) M T ≤ T · [(ρ + τ ) · s1 − ρ] ii) mT ≥ T · τ Moreover, (ii) is a sharp bound, i.e. there is a routing y ∈ RT with f T (y) = mT . One can obtain a nicer form for the coefficient in Theorem 1(iii), by moving from the above case, where S1 is ”thick”, to the opposite case, where S1 is ”thin” in the sense that s1 ≤ s2 + · · · + sn or, equivalently, when N − b1 ≥ s1 . In this case Theorem 1 takes the neater form expressed in Corollary 2. The corollary says that, in terms of f T -value, no routing is worse than 2 · s1 − 1 times the best possible routing. This gives an answer to a question asked in Section 1: What factor is reasonable to expect of a routing algorithm? Corollary 2. Suppose the network contains many nodes at least two hops away from all base nodes, i.e. that N − b1 ≥ s1 . Then for all T ≥ 1: M T ≤ (2 · s1 − 1) · mT Proof. The condition N − b1 ≥ s1 implies that m1 in (2) satisfies m1 ≥ ρ. Together with equation (4) this gives M T ≤ T · m1 · (2 · s1 − 1) ≤ (2 · s1 − 1) · mT , since T · m1 ≤ mT by Theorem 1(ii). This completes the proof.

5

Bounds on the lifetime of a sensor network

Suppose each node has the exact same amount EE of energy and we use a routing y in a traffic pattern consisting of T iterations. The network will be operational as long as f T (y) ≤ EE and, to compute the break point1 , we set f T (y) = EE, and let Tmax denote the corresponding value of T . The next theorem bounds the life of the network in terms of Tmax . Theorem 2. The maximum number Tmax of readings a sensor network can take under the given assumptions is bounded as follows: EE EE ≤ Tmax ≤ (ρ + τ ) · (N − s0 ) − ρ max {m1 , . . . , mn } 1

Tmax is time to first node failure. When (iii) of Theorem 1 is sharp, i.e. when, say, mT = T · max {m1 , . . . , mn } = T ·mi , all nodes of the sphere Si will fail at the same time, breaking connectivity. That mT > T · max {m1 , . . . , mn } indicates that it is not possible to balance traffic evenly (see Section 6). This lends support to the conjecture that the portion(s) of the network depending on the corresponding dead node(s) to reach B, will be disconnected.

Proof. It follows from f Tmax (y) = EE, that mTmax ≤ EE ≤ M Tmax . Applying Theorem 1 to these inequalities, Tmax ·max {m1 , . . . , mn } ≤ EE ≤ Tmax ·[(ρ+τ )·(N −s0 )−ρ]. Theorem 2 follows immediately from this.

6

Examples

In this section we discuss inequality (ii) of Theorem 1. We show via examples (mostly for T = 1) that (ii) is sharp and that, even in those cases where m = max{m1 , . . . , mn }, it is not necessarily true that max{m1 , . . . , mn } = m1 . The quantity max{m1 , . . . , mn } is a bound (not an equality) because there are examples where m > max{m1 , . . . , mn }; it is a sharp bound because there are examples where m = max{m1 , . . . , mn }. Notice that m is, by definition, the optimal value. Equality would thus mean that the explicit formula max{m1 , . . . , mn } computes the optimum for all possible networks that satisfy the conditions of Section 2. This is plainly too much to expect, so it should not be difficult to find examples with m > max{m1 , . . . , mn }. On the other hand, there are many cases where the bound is sharp, i.e. cases where the expression max{m1 , . . . , mn } does indeed compute the optimal value. In general, we think of max{m1 , . . . , mn } as the ”theoretical” optimum: it is the value that ”should” be optimal. It is achieved in networks where traffic can be balanced evenly between the elements of the sphere of appropriate radius. Example 3 is interesting in this context because traffic cannot be evenly balanced in a strict sense, but only ”on average” (see Example 3 below). We consider this case as one in which the optimum is achieved. Suppose that (ii) is sharp, i.e. that m = max{m1 , . . . , mn }. Then for some i = 1, . . . , n, max{m1 , . . . , mn } = mi . Popular belief has it that i = 1, i.e. max{m1 , . . . , mn } = m1 . This is intuitively appealing, and explanations sound convincing [8]. However, Example 2 below is an example where max{m1 , . . . , mn } = m2 > m1 ; thus, in this example it is not S1 but S2 that supports the heaviest burden of communication. It is easy to generalize the example to push the most heavily burdened sphere further away from the center, thus obtaining examples where max{m1 , . . . , mn } = mi for i > 2 (of course, i will be much smaller than n). Examples 1 and 5 below illustrate two different networks in which the theoretical optimum can fail to be achieved, i.e. m 6= max{m1 , . . . , mn }. Notice that the reason for failure is the same in both cases: it is impossible to balance traffic evenly among the members of the sphere of radius one. Example 2 shows that max{m1 , . . . , mn } need not equal m1 . Example 3 is a simple case to illustrate that using the same routing at each iteration can be far from optimal. Example 4 is characteristic for square networks with ”judicious” choice of base nodes in that m = max{m1 , . . . , mn } = m1 . Example 5 shows, however, that size and placement of the base are important parameters to consider if this is to hold. Giving a general proof of these facts for square networks is cumbersome because there are many cases to consider. In [11] we prove that m = max{m1 , . . . , mn } = m1 (perhaps on average) in case there is only one base node, which is located either at a corner or at the center of a square network of arbitrary size. 1. Consider network (1) of Figure 1, where B consists of the square node. The network consists of two trees rooted at the base node. In this case m1 = 2ρ+3τ , m2 = m3 = ρ+2τ , m4 = τ , and max{m1 , . . . , m4 } = m1 . However, m = f (y) = 3ρ + 4τ > m1 , where y is the only routing without loops on each of the rooted trees.

(1)

(3)

t

t

t

t

t

t

t

t

t

t

t

(2)

t © t © HHt HH© t ©

t

t

t

t t t t t (4)

Figure 1. Networks (the square node is the base node)

2. The network in Figure 1(2) illustrates a case where max{m1 , . . . , mn } 6= m1 . We assume that traffic towards the base is evenly split at the bifurcation. According to equation (2), m1 = 2ρ + 3τ = m3 , m2 = 3ρ + 4τ , m4 = ρ + 2τ , and m5 = τ . Hence, max{m1 , . . . , m5 } = m2 . On the other hand, it is easy to see that m = max{m1 , . . . , m5 }. Thus m = m2 . 3. For the graph in Figure 1(3), m1 = (1/2)ρ + (3/2)τ , and m2 = τ . In this case m1 = max{m1 , m2 }, but mT 6= T ·m1 . However, if we let y = (y1 , y2 , y1 , y2 , . . .), then f T (y) = mT ”on average”, in the sense that f T (y)/T → m1 when T → ∞. Indeed, f T (y) = T · m1 when T is even, and f T (y) = (T + 1)/2 · ρ + (3T + 1)/2 · τ when T is odd. 4. The graph in Figure 1(4) consists of 25 nodes, one for each intersection. The figure emphasizes only B1 . For this graph, m1 = 5ρ + 6τ , m2 = (7/3)ρ + (10/3)τ , m3 = (4/3)ρ + (7/3)τ , m4 = (3/5)ρ + (8/5)τ ,m5 = (1/2)ρ + (3/2)τ , and m6 = τ . In this case m = m1 = max{m1 , . . . , m6 }. 5. Consider again the graph in Figure 1(4), but this time with five base nodes consisting of the whole fourth row (from, say, top to bottom). The sphere S1 consists then of ten nodes, namely rows three and five. In this case max{m1 , . . . , m3 } < m since one cannot take advantage of all ten nodes to balance the traffic load.

7

Conclusions and future work

In this paper, using an idealized mathematical model, we have explicitly quantified the fundamental role played by the spheres of different radii in determining the energy consumption of routings in sensor networks with a continuous data delivery model, and where all nodes transmit with the same energy. We have computed explicit bounds on the energy consumption of routings, shown that these are sharp, and applied them to bound the lifetime of sensor networks. Finally, we have given some examples to illustrate the theory we developed. One of these contradicts the popular belief that it is always the nodes deployed nearest to base nodes that are the most heavily loaded and, hence, the ones that die first. For future work, we plan to apply these results to square networks [11], and to relax the hypothesis that all nodes transmit with the same power.

References [1] A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler and J. Anderson “Wireless sensor networks for habitat monitoring” in ACM International Workshop on Wireless Sensor Networks and Applications (WSNA’02) 2002. [2] V. Raghunathan, C. Schurgers and M. Shrivastava “Energy aware wireless microsensor networks” IEEE Signal Processing Magazine, Vol. 19 pp. 40-50 2002. [3] M. Bhardwaj and A. Chandrakasan “Bounding the Lifetime of Sensor Networks via Optimal Role Assignment” Proceedings of INFOCOM 2002 pp. 1587-1596 2002.

[4] J.H. Chang, L. Tassiulas “Energy conserving routing in wireless adhoc networks” IEEE INFOCOM 2000 2000. [5] Y. Xu, J. Heidemann, and D. Estrin “Adaptive Energy-Conserving Routing for Multihop Ad Hoc Networks” Research Report 527, USC/Information Sciences Institute 2000. [6] W.R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “An Application-Specific Protocol Architecture for Wireless Microsensor Networks” IEEE Transactions on Wireless Communications, Vol.1, No.4 pp. 660-670, 2002. [7] V. Mhatre, C. Rosenberg, D. Kofman, R. Mazumdar and N. Shroff “Design of Surveillance Sensor Grids with a Lifetime Constraint” First European Workshop on Wireless Sensor Networks (Berlin, January 2004) LNCS 2920, pp. 263-275, 2004. [8] V. Mhatre, C. Rosenberg, D. Kofman, R. Mazumdar and N. Shroff “A Minimum Cost Heterogeneous Sensor Network with a Lifetime Constraint” Preprint. 12 pp. 2004. [9] S. Tilak, N.B. Abu-Ghazaleh and W.R. Heinzelman “A Taxonomy of Wireless Micro-Sensor Network Models” ACM Mobile Computing and Communications Review (MC2R), Volume 6, Number 2, 2002. [10] R. Szewczyk, J. Polastre, A. Mainwaring, and D. Culler “Lessons from a Sensor Network Expedition” First European Workshop on Wireless Sensor Networks (Berlin, January 2004) LNCS 2920, pp. 307-322, 2004. [11] J. Alonso, A. Dunkels and T. Voigt “Bounds on the Lifetime of Square Wireless Sensor Networks” In preparation. 2004.