9512.net

# 1 Power-aware localized routing in wireless networks

1

Power-aware localized routing in wireless networks

2

3

4

5

6

d, the radio expends Eelec + Eampd2, and to receive the message, the radio expends Eelec. In order to normalize the constants, divide both expressions by Eamp, so that radio expands T=E + d2 for transmission and P=E for reception, where E= Eelec /Eamp=500 m2. Note that T/P= 1+ d2/E and T+P=2E+ d2. Therefore, in this model, referred to as HCB-model, the power needed for transmission and reception at distance d is u(d)= 2E+ d2. Rodoplu and Meng [RM] considered, in their experiments, the model with u(d)= d4+2*108, which will be referred to as RM-model. They also proposed a general model in which the power consumption between two nodes at distance d is u(d)=dα+c for some constants α and c, and describe several properties of power transmission that are used to find neighbors for which direct transmission is the best choice in terms of power consumption. They discuss that large-scale variations (modeled by lognormal shadowing model) can be incorporated into the path loss formula, and that small-scale variations (modeled by a Rayleigh distribution) may be handled by diversity techniques and combiners at the physical layer. Rodoplu and Meng [RM] described a power aware routing algorithm which runs in two phases. In the first phase, each node searches for its neighbors and selects these neighbors for which direct transmission requires less power than if an intermediate node is used to retransmit the message. This defines so called enclosure graph. In the second phase, each possible destination runs distributed loop-free variant of (non-localized) Bellman-Ford shortest path algorithm and computes shortest path for each possible source. The same algorithm is run from each possible destination. We observe that, since the energy required to transmit from node A to node B is the same as energy needed to transmit from node B to node A, the same algorithm may be applied from each possible source, and used to discover the best possible route to each destination node (or, alternatively, it may be used to find the location of destination and the best route to it). Ettus [E] showed that minimum consumed energy routing reduces latency and power consumption for wireless networks utilizing CDMA, compared to minumum transmitted energy algorithm (shortest path algorithm was used in experiments). Heizelman, Chandrakasan and Balakrishnan [HCB] used signal attenuation to design an energy efficient routing protocol for wireless microsensor networks, where destination is fixed and known to all nodes. They propose to utilize a 2-level hierarchy of forwarding nodes, where sensors form clusters and elect a random clusterhead. The clusterhead forwards transmissions from each sensor within its own cluster. This scheme is shown to save energy under some conditions. However, the scheme does not apply to our case since destination is not fixed in our routing problem. Nevertheless, their simple radio model and metric is adopted in our paper. 3. Existing GPS based routing methods Most existing routing algorithms do not consider the power consumption in their routing decisions. Several GPS based methods were proposed in 1984-86 by using the notion of progress. Define progress as the distance between the transmitting node and receiving node projected onto a line drawn from transmitter toward the final destination. A neighbor is in forward direction if the progress is positive (for example, for transmitting node S and receiving nodes A, C and F in Fig. 1); otherwise it is said to be in backward direction (e.g. nodes B and E in Fig. 1). In the random progress method [NK], packets destined toward D are routed with equal probability towards one intermediate neighboring node that has positive progress. The rationale for the method is that, if all nodes are sending packets frequently, probability of collision grows with the distance between nodes (assuming that the transmission power is adjusted to the minimal possible), and thus there is

7

a trade-off between the progress and transmission success. In the NFP method [HL], packet is sent to the nearest neighboring node with forward progress (for instance, to node C in Fig. 1). Takagi and Kleinrock [TK] proposed MFR (most forward within radius) routing algorithm, in which packet is sent to the neighbor with the greatest progress. In [HL], the method is modified by proposing to adjust the transmission power to the distance between the two nodes.

A B C A’ D S E F

Figure 1. Progress based routing methods Recently, three articles [BCSW, KV, KSU] independently reported variations of fully distributed routing protocols based on direction of destination. In the compass routing (or DIR) method proposed by Kranakis, Singh and Urrutia [KSU], the source or intermediate node A uses the location information for the destination D to calculate its direction. The location of one hop neighbors of A is used to determine for which of them, say C, is the direction AC closest to the direction of AD. The message m is forwarded to C. This process repeats until the destination is, hopefully, reached. A counterexample showing that undetected loops can be created in directional based method is given in [SL]. The method is therefore not loop-free. [SL] introduced the GEDIR routing algorithm for a MANET based on the locations (latitude and longitude) of all nodes. When node A wants to send a message to node B, it uses the location information for B and for all its one hop neighbors to determine the neighbor C which is closest to B among all neighbors of A. The message is forwarded to C, and the same procedure is repeated until B, if possible, is eventually reached. GEDIR algorithm is inherently loop-free [SL]. The proof is based on the observation that distances of nodes toward destination are decreasing. Similarly, the proof of loop-free MFR algorithm is based on a decreasing dot product. All described GPS based routing algorithms are fully distributed, demand-based and adapt well to 'sleep' period operation. The 2-hop variants of three mentioned GPS based routing algorithms were proposed in [SL]. The delivery rate of GEDIR, compass routing (or DIR) or MFR algorithms can be improved if each node is aware of its 2-hop neighbors (neighbors of its neighbors). In this case, the node A currently holding the message may choose the node closest to the destination among all direct (1-hop) and 2hop neighbors, and forward the message to its neighbor that is connected to the choice. In case of ties (that is, more than one neighbor connected to the closest 2-hop neighbor), choose the one that is closest to destination. There are no multiple copies of the message in MANET at any transmission step in these 2-hop methods. A routing algorithm that guarantees delivery by finding a simple path between source and destination (without any flooding effect) is described in [BMSU].

8

9

10

Proof. Follows directly from Lemma 2. Let us verify whether power savings over direct transmission are obtained. For n=d(a/c)1/2 the power consumption with n shorter transmissions is 2cd(a/c)1/2 + bd < ad2 + bd +c since 2d(ac)1/2 < ad2 + c follows from the inequality of arithmetic and geometric means. Thus power savings are indeed obtained. Assuming that we can set additional nodes in arbitrary positions between the source and destination, the following theorem gives power optimal packet transmissions. Theorem 1. Let d be the distance between the source and the destination. The power needed for direct transmission is u(d)=adα + bd +c which is optimal if d  (c/(a(1-21-α)))1/α. Otherwise (that is, when d > (c/(a(1-21-α)))1/α), n-1 equally spaced nodes can be selected for retransmissions, where n= d(a(α-1)/c)1/α (rounded to nearest integer), producing minimal power consumption of about v(d)= bd + dc(a(α-1)/c)1/α + da(a(α-1)/c)(1-α)/α. For α=2, the power needed for direct transmission is u(d)=ad2 + bd +c which is optimal if d  (2c/a)1/2. Otherwise (that is, when d > (2c/a)1/2), n-1 equally spaced nodes can be selected for retransmissions, where n= d(a/c)1/2 (rounded to nearest integer), producing minimal power consumption of about v(d)=2d(ac)1/2+ bd. Theorem 1 announces the possibility of converting polynomial function in d (with exponent α) for power consumption (in case of direct transmission from sender to destination) to linear function in d by retransmitting the packet via some intermediate nodes that may be available in MANET. 5. Power saving routing algorithms If nodes have information about position and activity of all other nodes in the network (or if the decisions are made centrally) then optimal power saving algorithm, that will minimize the total energy per packet, can be obtained by applying Dijkstra’s single source shortest weighted path algorithm, where each edge has weight u(d)=adα + bd +c, where d is the length of the edge (that is, the relative distance between the two nodes). This will be referred as the SP-power algorithm. A r B d s D

Figure 3. Distributed power-conserving routing algorithm We shall now describe a corresponding localized routing algorithm. The source (or any intermediate node) S should select one of its neighbors to forward packet toward destination, with the goal of reducing the total power needed for the packet transmission. Let A be a neighbor of B, and let r=|AB|, d=|BD|, s=|AD| (see Figure 3). The power needed for transmission from B to A is u(r)=arα + br +c, while the power needed for the rest of routing algorithm is not known. Assuming uniformly distributed network, we shall make a fair assumption that the power consumption for the rest of routing algorithm is equal to the optimal one, as outlined in Theorem 1. That is, the power needed for transmitting message from A

11

to D is estimated to be v(s)= bs + sc(a(α-1)/c)1/α + sa(a(α-1)/c)(1-α)/α. For α=2, v(s)=2s(ac)1/2 + bs. This is, of course, an unrealistic assumption. However, it is fair to all nodes. A more realistic assumption might be to multiply the optimal power consumption by a factor t, which is a constant that depends on the network, and is equal to the average power consumption per packet (obtained experimentally) divided by the optimal one. The localized power efficient routing algorithm can be described as follows. Each node B (source or intermediate node) will select one of its neighbors A which will minimize p(B,A)=u(r)+v(s)= arα + br +c + bs + sc(a(α-1)/c)1/α + sa(a(α-1)/c)(1-α)/α. For α=2 it becomes u(r)+v(s)= ar2 + br +c + 2s(ac)1/2 + bs. If destination D is a neighbor of B then compare the expression with the corresponding one, u(d)=ad2 + bd +c, needed for direct transmission. Deliver the packet directly to D if it reduces the energy. In fact, s=0 for D, and D can be treated as any other neighbor. The algorithm proceeds until the destination is reached, if possible. A generalized power efficient routing algorithm may attempt to minimize p(B,A)=u(r)+tv(s), where t is a network parameter (however, we only experimented with t=1). In the basic (experimental) version of the algorithm (and in the remaining localized algorithms presented below), the transmission stops if message is to be returned to a neighbor it came from (otherwise, a detectable loop is created). Various flooding based or multiple path techniques [SL] can be added to the protocol if delivery rate is to be improved; however, their total power consumption needs to be studied. The power-efficient routing algorithm may be formalized as follows. Power-routing(S,D); A:=S; Repeat B:=A; Let A be neighbor of B that minimizes p(B,A)=u(r)+ tv(s); Send message to A until A=D (* destination reached *) or A=B (* delivery failed *); Let us now consider the second metric proposed in [SWR], measuring the nodes lifetime. Recall that the cost of each node is equal to f(A)=1/g(A) where g(A) denotes the remaining lifetime, normalized to be in the interval [0,1]. [SWR] proposed shortest weighted path algorithm based on this node cost. It is referred to as the SP-cost algorithm in experimental data on Table 2. The algorithm uses the cost to select the path, but the actual power is charged to nodes. The localized version of this algorithm, assuming constant power for each transmission, can be designed as follows. The cost c(A) of a route from B to D via neighboring node A is the sum of the cost f(A) =1/g(A) of node A and the estimated cost of route from A to D. The cost f(A) of each neighbor A of node B currently holding the packet is known to B. What is the cost of other nodes on the remaining path? We assume that this cost is proportional to the number of hops between A and D. The number of hops, in turn, is proportional to the distance s=|AD|, and inversely proportional to radius R. Thus the cost is ts/R, where factor t is to be investigated separately. Its best choice might even be determined by experiments. We have considered the following choices for factor t: i) ii) iii) t is a constant number, which may depend on network conditions, t= f(A) (that is, assuming that remaining nodes have equal cost as A itself), t= f'(A), where f'(A) is the average value of f(X) for A and all neighbors X of A,

12

iv) v) vi)

t=1/g'(A), where g'(A) is the average value of g(X) for A and all neighbors X of A, t=f'(B) (that is, assuming that remaining nodes have equal cost to the cost of B), t=1/g'(B).

Note that t=t(A) in i-iv is a function of A only, which is not the case for v-vi. Thus the cost c(A) of a route from S to D via neighboring node A is estimated to be c(A)=f(A)+ts/R, for the appropriate choice of t. Although this seems to be the natural choice, it is not clear whether such definition of c(A) will give the best experimental results. We therefore suggest to investigate also the product of two contributing elements instead of their sum, that is the cost definition c(A)= f(A)ts/R. The localized cost efficient routing algorithm can be described as follows. If destination is one of neighbors of node B currently holding the packet then the packet will be delivered to D. Otherwise, B will select one of its neighbors A which will minimize c(A). The algorithm proceeds until the destination is reached, if possible, or until a node selects the neighbor the message came from as its best option to forward the message. The algorithm can be coded as follows. Cost-routing(S,D); A:=S; Repeat B:=A; Let A be neighbor of B that minimizes c(A); If D is neighbor of B then send to D else send to A until D is reached or A=B; We may incorporate both power and cost considerations into a single routing algorithm. A new power-cost metrics is first introduced here. What is the power-cost of sending a message from node B to node the neighboring node A? We propose two different ways to combine power and cost metrics into a single power-cost metric, based on the product and sum of two metrics, respectively. If the product is used, then the power-cost of sending message from B to a neighbor A is equal to power-cost(B,A)=f(A)u(r) (where |AB|=r). The SP-power-cost algorithm can find the optimal power-cost by applying single source shortest weighted path Dijkstra’s algorithm (the node cost is transferred to the edge leading to the node). The sum, on the other hand, leads to a new metrics power-cost(B,A)=αu(r) + βf(A), for suitably selected values of α and β. For example, sender node S may fix α=f'(S) and β=u(r'), where r' is the average length of all edges going out of S. The values α and β are (in this version) determined by S and used, without change, by other nodes B on the same route. The corresponding SP-power-cost algorithm will also use the so defined metric, and is referred to as the SP-power-cost1 algorithm in Table 2. The power-cost efficient routing algorithm may be described as follows. Let A be the neighbor of B (node currently holding the message) that minimizes pc(B,A)= power-cost(B,A) + v(s)f’(A) (where s=0 for D, if D is a neighbor of B). The algorithm is named power-cost0 in Table 2 when power-cost(B,A)=f(A)u(r), and power-cost1 when power-cost(B,A)= f'(S)u(r)+u(r')f(A). The packet is delivered to A. Thus the packet is not necessarily delivered to D, when D is a neighbor of B. The algorithm proceeds until the destination is reached, if possible, and may be coded as follows. Power-cost-routing(S,D); A:=S;

13

Repeat B:=A; Let A be neighbor of B that minimizes pc(B,A)= power-cost(B,A) + v(s)f’(A); Send message to A until A=D (* destination reached *) or A=B (* delivery failed *); The algorithm may be modified in several ways. The second term may be multiplied by a factor that depends on network conditions. We tested also the version, called power-cost2, that minimizes pc(B,A)=f(A)(u(r) + v(s)), and an algorithm, called power-costP, that switches selection criteria from power-cost to power metric only whenever destination D is a neighbor of current node A. 6. Loop-free property Theorem 2. The localized power efficient routing algorithm is loop-free. An rn An-1 sn-1 rn-1 D s3 A3 s2 r3 r1 sn s1 A1 r2 A2

Figure 4. Power efficient routing algorithm is loop-free Proof. Suppose that, on the contrary, there exists a loop in the algorithm. Let A1, A2, … An be the nodes in the loop, so that A1 send the message to A2, A2 sends the message to A3, …, An-1 sends the message to An and An sends the message to A1 (see Fig. 4). Let s1, s2, …, sn be the distances of A1, A2, … An from D, respectively, and let |AnA1|=r1, |A1A2|=r2, |A2A3|=r3, …, |An-1An|=rn. Let u(r)= arα + br +c and v(s) = bs + sc(a(α-1)/c)1/α + sa(a(α-1)/c)(1-α)/α (for α=2, v(s)= 2s(ac)1/2 + bs). According to the choice of neighbors in Fig. 4 it follows that u(r1)+v(s1)<u(rn)+v(sn-1) since the node An selects A1, not An-1, to forward the message. Similarly u(r2)+v(s2) < u(r1)+v(sn) since A1 selects A2 rather than An. Next, u(r3)+v(s3) < u(r2)+v(s1), …, u(rn)+v(sn) < u(rn-1)+v(sn-2). By summing left and right sides we obtain u(r1)+u(r2)+…+u(rn)+v(s1)+v(s2)+…+v(sn) < u(rn)+u(r1)+…+u(rn-1)+v(sn-1)+v(sn)+…+v(sn-2) which is a contradiction since both sides contain the same elements. Thus the algorithm is loop-free. In order to provide for loop-free method, we assume that (for this and other mentioned methods below), in case of ties for the choice of neighbors, if one of choices is the previous node, the algorithm will select that node (that is, it will stop or flood the message). Note that the above proof may be applied (by replacing '+' with '*') to an algorithm that will minimize p(A)=u(r)tv(s). Theorem 3. Localized cost efficient algorithms are loop-free, for parameter values t given by i-iv.

14

Proof. Note that the cost c(A) of sending message from B to A in cases i-iv is only the function of A (that is, t=t(A)), and is independent on B (this is not the case with options v-vi). The proof is by contradiction, similar to the proof of previous theorem. Suppose that there exists a loop in the algorithm. Let A1, A2, … An be the nodes in the loop (see Fig. 4). Let c(A1), c(A2), … c(An), be the costs of sending message to nodes A1, A2, … An, respectively, from the previous node in the loop. According to the choice of neighbors in Fig. 4 it follows that c(A1) < c(An-1) since the node An selects A1, not An-1, to forward the message. Similarly c(A2) < c(An) since A1 selects A2 rather than An. Next, c(A3) < c(A1), …, c(An) < c(An-2). By summing left and right sides we obtain c(A1)+c(A2)+…+c(An) < c(An-1)+c(An)+…+c(An-2) which is a contradiction since both sides contain the same elements. Thus the algorithm is loop-free. The proof is valid for both formulas c(A)=f(A)+ts/R and c(A)=f(A)ts/R. Note that the proof assumes that the cost of each node is not updated (that is, communicated to the neighbors) while the routing algorithm is in progress. It is possible to show that, on the other hand, if nodes inform their neighbors about new cost after every transmitted message, a loop (e.g. triangle) can be formed. Theorem 4. Localized power-cost efficient algorithms are loop-free for the metrics powercost(B,A)=αu(r) + βf(A) (where α and β are arbitrary constants), and pc(B,A)= power-cost(B,A) + v(s)t(A) (where t(A) is determined by one of formulas i-iv). Proof. The proof is again by contradiction, similar to the proof of previous theorems. Suppose that there exists a loop A1, A2, … An in the algorithm (see Fig. 4). Let pc(An, A1), pc(A1, A2), … pc(An-1, An), be the power-costs of sending message to nodes A1, A2, … An, respectively, from the previous node in the loop. According to the choice of neighbors in Fig. 4 it follows that pc(An, A1) < pc(An, An-1) since the node An selects A1, not An-1, to forward the message. Similarly pc(A1, A2) < pc(A1, An), pc(A2, A3) < pc(A2, A1), …, pc(An-1, An) < pc(An-1, An-2). By summing left and right sides we obtain pc(An, A1) + pc(A1, A2) + pc(A2, A3) + …+ pc(An-1, An) < pc(An, An-1) + pc(A1, An) + … + pc(An-1, An-2). This inequality is equivalent to [αu(rn) + βf(A1)+ v(s1)t(A1)] + [αu(r1) + βf(A2)+ v(s2)t(A2)] + … + [αu(rn-1) + βf(An)+ v(sn)t(An)] < [αu(rn) + βf(An-1)+ v(sn-1)t(An-1)] + [αu(r1) + βf(An)+ v(sn)t(An)] + … + [αu(rn-1) + βf(An-2)+ v(sn-2)t(An-2)] which is a contradiction since both sides contain the same elements. Thus the algorithm is loop-free. Note that the proof also assumes that the cost of each node is not updated (that is, communicated to the neighbors) while the routing algorithm is in progress. Note that this proof does not work for the formula powercost(B,A)=f(A)u(r), which does not mean that the corresponding power-cost routing algorithm is not loop-free. 7. Performance evaluation of power efficient routing algorithm The experiments are carried using random unit graphs. Each of n nodes is chosen by selecting its x and y coordinates at random in the interval [0,m). In order to control the average node degree k (that is, the average number of neighbors), we sort all n(n-1)/2 (potential) edges in the network by their length, in increasing order. The radius R that corresponds to chosen value of k is equal to the length of nk/2-th edge in the sorted order. Generated graphs which were disconnected are ignored. We have fixed the number of nodes to n=100, and average node degree k to 10. We have selected higher connectivity for our experiments in order to provide for better delivery rates and hop counts and concentrate our study on power conserving effects.

15

The comparison of DIR (compass routing), MFR and GEDIR methods in [SL] did not depend on the size m of square containing all the points. However, in case of power consumption, the actual distances greatly impact the behavior of algorithms. More precisely, the path selection (and the energy for routing) in our power saving algorithm depends on the actual size of the square. Although the path selection in DIR, MFR and GEDIR methods are independent on m, the energy needed for routing differs, and is not simply proportional to m. We compared all methods for squares of sizes m=10, 100, 200, 500, 1000, 2000, 5000 for both HCB- and RM-models. The results are averages over 20 graphs with 100 routing pairs in each chosen at random. In our comparisons, the power consumption (cost, power-cost, respectively) in all compared methods was measured by assigning the appropriate weights to each edge. The shortest weighted path algorithm was used as a benchmark. Our comparison for the category of power (only) consumption involved the following GPS based distributed algorithms: NFP, random progress, MFR, DIR, GEDIR, NC, the proposed distributed power efficient routing algorithm (with t=1), and the benchmark shortest (weighted) path algorithm (SP). A node, currently holding the message, will stop forwarding the message if the best choice, by the method, is to return the message to the node message came from. Such nodes are called concave nodes [SL], and delivery fails at such nodes. C B D A A Figure 5. NFP method fails Figure 6. Power1 frequently fails We have introduced a new routing method, called NC (nearest closer), in which node A, currently holding the message, forwards it to its nearest node among neighboring nodes which are closer to destination than A. This method is an alternative to the NFP method which was experimentally observed to have very low success rate (under 15% in our case). The reason for low success rate seems to be the existence of many acute triangles ABD (see Fig. 5) so that A and B are closest to each other, and therefore selected by NFP method which then fails at such nodes (D is the destination). The proposed power efficient method, which will be referred as power1 method, was also experimentally shown to have very low success rate for large m. The power efficient algorithm is therefore modified to increase its success rate. Only neighbors that are closer to destination than the current node are considered, and this variant will be called the power method. The success rates of power and power1 methods are almost the same for m≤200. While the success rate of power method remains at 95% level, the success rate for power1 drops to 59%, 11%, 4% and 2% only for remaining sizes of m (numbers refer to HCB-model, and are similar for the other model). Consider a scenario in which power1 fails (see Fig. 6, where |AD| < |BD| < |CD|). Node A sends message to closest neighbor B. Since A is very close to B but C is not, power formula applied at B selects A to send message back, and a loop is created. We included 2-hop GEDIR, DIR, MFR and NC methods in our experiments. 2-hop NC method is defined as follows. Each current node C finds the neighboring node A whose 1-hop nearest B D

16

(closer to destination D) neighbor B has the shortest distance (between A and B). If no such node exist (i.e. none of neighboring nodes of C has forward neighbor) then take the neighbor node E whose backward nearest neighbor F has smallest distance (between E and F). The delivery rates for 1-GEDIR, 1-DIR, and 1-MFR methods in our experiments were about 97%, 1-NC had 95% success, 2-GEDIR (that is, 2-hop GEDIR) and 2-MFR about 99%, 2-DIR about 91%, 2-NC and random methods about 98%, and power method 95% success rate (for both HCB- and RM-models). While all other methods choose the same path independently on m and power formula applied, power method does not, and almost constant and good delivery rate for it is a very encouraging result. The hop counts for non-power based methods were 3.8, 4.2, 3.9, 8.0, 3.8, 3.9, 4.1, 5.2, and 6.4, respectively (in above order). Hop counts for power method were 3.8, 3.8, 3.8, 3.8, 6.3, 9.0 and 9.7 for RM-model, and 3.8, 3.8, 4.0, 6.6, 8.3, 9.1, 9.6 for HCB-model, in respective order of m. Clearly, with increased energy consumption per distance, power method reacted by choosing closer neighbors, resulting in higher hop counts. Let us show the superiority of GEDIR method over MFR method and superiority of compass routing over random progress method. Let A and B be the nodes selected by the GEDIR and MFR methods, respectively, when packet is to be forwarded from node S (see Fig. 7). Suppose that B is different from A (otherwise the energy consumption at that step is the same). Therefore |AD|<|BD|. Node B cannot be selected within triangle SAA’ where A’ is the projection of node A on direction SD, since B has more progress than A (here we assume, for simplicity, that A and B are on the same side of line SD). However, the angle SAB is then obtuse, and |SB|>|SA|. From |SB| > |SA| and |BD| > |AD| and monotonicity of power consumption function, it follows that the packet requires more energy if forwarded to B instead of A. Note that the presented scenario is for an average case. It is possible to find a counterexample showing the opposite (or showing that a path via B exists while there is no path via A) in some very special cases. Suppose now that A and B are selected neighbors in case of compass and random progress routing algorithms (we shall use the same Fig. 7). Since the lengths |SA| or |SB| are not considered when selecting the neighbors, on the average we may assume that |SA|=|SB|. However, the direction of A is closer to the direction of destination (that is, the angle ASD is smaller than the angle BAD) and thus A is closer to D than B. Therefore one can expect more energy efficient compass routing algorithms as compared to random progress one. Again, counterexamples may be easily found for particular cases. B A

S

A’ D Figure 7. GEDIR consumes less power than MFR

Table 1 shows average power assumption (rounded to nearest integers) per routing tasks that were successful by all methods, which occurs in about 85% of cases. It is calculated as the ratio of total power consumption (for each method) for these tasks over the total number of such deliveries. The quadratic HCB-model formula is used (the results for the RM-model were similar).

17

The power consumption for GEDIR algorithm is smaller than the one for DIR routing method for small values of square size m. The reason is that the smaller hop count is decisive when no retransmission is desirable. However, for larger m, compass routing performs better, since the greatest advance is not necessarily best choice, and the closer direction, possibly with smaller advance, is advantageous. The NC method is inferior to GEDIR or DIR for smaller values of m, because the greatest possible advance is the better choice for neighbor than the nearest node closer to destination. However, for larger values of m, NC outperforms significantly both, since it simulates retransmissions in the best possible way. 2-hop methods failed to produce power savings over corresponding 1-hop methods, and were eliminated in our further investigations.
method/size SP-Power SP Power GEDIR DIR MFR NC Random 2-GEDIR 2-DIR 2-MFR 2-NC 10 3577 3578 3619 3619 3928 3644 7604 5962 3587 3937 3603 4851 100 4356 4452 4457 4460 4681 4523 8271 7099 4452 4764 4478 5824 200 6772 7170 6951 7076 7046 7264 10523 10626 7148 7386 7208 8815 500 20256 25561 21331 24823 23033 25845 25465 34382 25399 25109 25738 29125 1000 62972 92438 69187 89120 81001 93150 80136 121002 91570 89371 92816 102786 2000 229455 358094 261832 344792 311743 361021 297580 465574 354980 344644 359491 394951 5000 1404710 2236727 1647964 2152891 1942952 2254566 1833993 2896988 2216528 2148913 2248876 2466065

Table 1. Power consumption of routing algorithms As expected, the proposed distributed power efficient routing algorithm outperforms all known GPS based algorithms for all ranges of m. For small m, it is minor improvement over GEDIR or DIR algorithms. However, for large m, the difference becomes very significant, since nearest rather than furthest progress neighbors are preferred. For large m, the only competitor is NC algorithm. It is also observed that the proposed power efficient algorithm produces paths that are close to the optimal ones, obtained by SP (shortest weighted path) algorithm. More precisely, the overhead (percentage of additional energy per routing task) of power efficient algorithm with respect to SP one is 1.2%, 2.3%, 2.6%, 5.3%, 9.9%, 14.1% and 17.3% for the considered values of m, respectively. Therefore, localized power efficient routing algorithm, when successful, closely matches the performance of non-localized shortest weighted path algorithm. 8. Performance evaluation of cost and power-cost efficient routing algorithms The performance evaluation in the previous section shows the superiority of power efficient method for the case of nodes with relatively equal and high battery powers (e.g. all batteries are refreshed). In this section, we shall assume that nodes have different remaining powers, and will involve two more routing methods, cost and power-cost, with their respective shortest weighted path algorithms.

18

The experiments that evaluate cost and power-cost routing algorithms are designed as follows. Random unit connected graphs are generated as in the previous section. An iteration is a routing task specified by the random choice of source and destination nodes. Any node currently holding the message will halt the routing task if it is a concave node for that task (method failure), or if the current node does not have enough power to transmit the message to the next node, decided by the given method (power failure). Instead of running fixed number of iterations, we decided to run iterations until the first power failure at a node occurs (at which point the corresponding method 'dies'). Each node is initially assigned an energy level at random in the interval [minpow, maxpow], where parameters are chosen differently for different values of m. After sending a message from node A to node B, the energy that remained at A (B) is reduced by the power needed to transmit (receive) the message, respectively. The experiment is performed on 20 graphs for each method, for each of HCB- and RM-model formulas. Because of experience with success rate of power efficient method, we considered two variants of cost and power-cost algorithms, and in the main method we restrict the selection of neighbors to the nodes that are closer to destination than current node. The success rates for unrestricted versions (all neighbors considered) was again low in our experiments. For example, the success rate of cost0 method drops from 64% to 55% with increasing m, while power-cost0 method drops from 77% to 14% (data for other variants are similar; HCB-model is again used, while the other model had very similar data). Consequently, these methods were deemed not viable (the number of iterations before dying for them is not shown, because high failure rate certainly distorted their interpretation). The success rate for restricted versions (only closer neighbors considered) was in the range 92%-95% for all cost and power-cost methods discussed here, both models, and all sizes m. The number of iterations before each method dies, for HCB-model, is given in Table 2. RM-method gave similar results. The cost and power-cost methods from Table 2 are described in section 5.
method/trial count SP SP-Power SP-Cost SP-PowerCost SPPowerCost1 Power Cost0 Cost1 PowerCostP PowerCost0 PowerCost1 PowerCost2 1-GEDIR 1-DIR 1-MFR 1-NC Random 10 289 342 674 674 647 379 624 637 671 662 660 631 373 345 375 204 201 100 713 865 1703 1697 1668 954 1630 1616 1616 1609 1611 1537 941 921 909 551 481 200 1412 1710 3540 3530 3495 1843 3255 3304 3127 3118 3180 3211 1814 1741 1775 1268 889 500 668 983 1686 1776 1725 1009 1594 1651 1522 1513 1664 1676 832 831 800 809 546 1000 647 1114 1590 1838 1688 1162 1479 1494 1522 1528 1757 1716 849 902 797 931 512 2000 454 796 1066 1230 1124 789 988 991 1053 1056 1179 1152 548 603 525 668 312 5000 275 482 646 728 682 469 601 602 600 617 712 686 318 355 316 414 202

Table 2. Number of iterations before one of node in each method dies

19

The intervals [minpow, maxpow] were set as follows: [80K, 90K] for m=10, [200K, 300K] m=100, [500K, 1M] for m=200, [750K, 1.5M] for m=500, [3M, 4M] for m=1000, [8M, 10M] for m=2000, [30M, 40M] for m=5000, where K=1000 and M=1000000. Our experiments confirmed the expectations on producing power savings in the network and/or extending nodes lifetime by applying our algorithms on randomly generated unit graphs. Both cost methods and all four power-cost methods gave very close trial numbers, and thus it is not possible to choose the best method based on trial number alone. However, all proposed cost and power-cost methods, which are localized, performed equally well as the corresponding non-localized shortest path cost and power-cost algorithms (the number of trials is sometimes even higher, due to occasional delivery failures which save power). It is also clear that cost and power-cost routing algorithms last for significantly more iterations than the power algorithm.
method/power SP-Cost SP-PowerCost SPPowerCost1 Cost0 Cost1 PowerCostP PowerCost0 PowerCost1 PowerCost2 10 44381 44437 46338 43996 39831 30561 27434 27520 33563 100 133245 133591 136490 129608 120785 127819 126066 126201 131804 200 395592 396031 406887 410610 377549 421927 416889 409208 401174 500 618640 642748 646583 656349 619221 712958 712033 666907 652199 1000 1857188 2067025 1972185 2053190 2022771 2299590 2286840 2091211 2078140 2000 4819903 5686092 5252813 5370162 5335936 6058424 6030614 5658144 5684752 5000 19238265 23187052 21081420 21338314 21233992 24782129 24419832 22622947 23136193

Table 3. Average remaining power level at each node Table 3 shows the average remaining power at each node after the network dies, for the most competitive methods. Cost methods have more remaining power only for the smallest size m=10, when the power formula reduces to the constant function. For larger sizes of m, two better powercost formulas leave about 15% more power at nodes than the cost method. Thus, power-cost method may outperform cost methods, since the network will continue to operate without the first node with power failure. It is also of interest to check the average hop counts for the cost and power-cost routing algorithms. SP-cost, cost0 and cost1 methods have hop counts approximately 4.0, 4.5, and 4.9 for HCB-model and all values of m. Four power-cost methods have similar hop counts, 5.8, 4.7, 5.0, 6.7, 8.4, 9.1 and 9.6, respectively, for sizes of m. Two SP-power-cost methods do not similar hop counts. SP-PowerCost method has hop counts 4.0, 4.1, 4.3, 6.3, 7.8, 8.3, 8.7, while SPPowerCost1 method has hop counts between 4.0 and 4.6. Conclusion This paper described several localized routing algorithms that try to minimize the total energy per packet and/or lifetime of each node. The proposed routing algorithms are all demand-based and can be augmented with some of the proactive or reactive methods reported in literature, to produce the actual protocol. These methods use control messages to update positions of all nodes to maintain efficiency of routing algorithms. However, these control messages also consume power,

20

21

22

[NK] R. Nelson and L. Kleinrock, Tha spatial capacity of a slotted ALOHA multihop packet radio network with capture, IEEE Transactions on Communications, 32, 6, 1984, 684-694. [PL] K. Pahlavan and A. Levesque, Wireless information networks, Wiley Interscience, 1995. [R] T.S. Rappaport, Wireless communications: Principles and Practice, Prentice Hall, 1996. [RB] J.M. Rulnick and N. Bambos, Mobile power management for wireless communication networks, Wireless Networks, 3, 1997, 3-14. [RM] V. Rodoplu and T.H. Meng, Minimum energy mobile wireless networks, IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, August 1999, 1333-1344. [RS] S. Ramanathan and M. Steenstrup, A survey of routing techniques for mobile communication networks, Mobile Networks and Applications, 1, 2, 1996, 89-104. [RT] E.M. Royer and C.K. Toh, A review of current routing protocols for ad hoc mobile wireless networks, IEEE Personal Communications, April 1999, 46-55. [SC] A.K. Salkintzis and C. Chamzas, An in-band power-saving protocol for mobile data networks, IEEE Transactions on Communications, 46, 9, 1998, 1194-1205. [SR] S. Singh and C.S. Raghavendra, PAMAS – Power aware multi-access protocol with signaling for ad hoc networks, ACM Computer Communications Review, July 1998, 5-26. [SSL] A.R. Shahani, D.K. Schaeffer, and T.H. Lee, A 12mW wide dynamic range CMOS front-end for a portable GPS receiver, Proc. IEEE Int. Solid-State Circuits Conf., vol. 40, Feb. 1997, 368-369. [SWR] S. Singh, M. Woo, C.S. Raghavendra, Power-aware routing in mobile ad hoc networks, Proc. MOBICOM, 1998, 181-190. [S] I. Stojmenovic, Power aware routing algorithms with guaranteed delivery in wireless networks. [SL] I. Stojmenovic and X. Lin, GEDIR: Loop-free location based routing in wireless networks, IASTED Int. Conf. on Parallel and Distributed Computing and Systems, Nov. 3-6, 1999, Boston, MA, USA, 1025-1028. [SV] I. Stojmenovic and B. Vukojevic, A routing strategy and quorum based location update scheme for ad hoc wireless networks, Computer Science, SITE, University of Ottawa, TR99-09, September 1999. [TK] H. Takagi and L. Kleinrock, Optimal transmission ranges for randomly distributed packet radio terminals, IEEE Transactions on Communications, 32, 3, 1984, 246-257.