In this paper we propose four schemes that improve the performance of greedy routing method. In the alternate method, the i-th received copy of message m is forwarded to i-th best neighbor, according to the selected criterion (it fails if number of copies exceeds number of neighbors). In the disjoint method, each intermediate node, upon receiving m, will forward it to its best neighbor among those who never received the message (it fails if no such neighbor exists). In the multi-path method, the source node S forwards m to c best neighbors according to distance from D. Each of c created copies afterwards follows the original, alternate, or disjoint method (these copies may interact since copy numbers are not communicated). Component routing method follows original greedy method until a failure node F. Such node F forwards the message to one node (using distance criteria) in each connected component of its neighbors, and then withdraws from the network for that message m (that is, neighboring nodes will ignore F when forwarding further copies of m). Thus F creates c copies of the message, where c is the number of connected components in the subgraph of its neighbors. All proposed methods are loop-free, have improved delivery rate over greedy method and reduced flooding rates compared to other existing methods. Component routing method guarantees delivery of m in connected graphs (even if the location of D is inaccurate).

In a localized routing algorithm, each node makes forwarding decisions solely based on the position of itself, its neighbors, and its destination. In distance, progress, and direction-based approaches'(reported in the literature), when node A wants to send or forward message m to destination node D, it forwards m to its neighbor C which is closest to D (has best progress toward D, whose direction is closest to the direction of D, respectively) among all neighbors of A. The same procedure is repeated until D, if possible, is eventually reached. The algorithms are referred to as GEDIR, MFR, and DIR when a common failure criterion is introduced: The algorithm stops if the best choice for the current node is the node from which the message came. We propose 2-hop GEDIR, DIR, and MFR methods in which node A selects the best candidate node C among its 1-hop and 2-hop neighbors according to the corresponding criterion and forwards m to its best 1-hop neighbor among joint neighbors of A and C. We then propose flooding GEDIR and MFR and hybrid single-path/flooding GEDIR and MFR methods which are the first localized algorithms (other than full flooding) to guarantee the message delivery (in a collision-free environment). We show that the directional routing methods are not loop-free, while the GEDIR and MFR-based methods are inherently loop free. The simulation experiments, with static random graphs, show that GEDIR and MFR have similar success rates, which is low for low degree graphs and high for high degree ones. When successful, their hop counts are near the performance of the shortest path algorithm. Hybrid single-path/flooding GEDIR and MFR methods have low communication overheads. The results are also confirmed by experiments with moving nodes and MAC layer.

A cost aware metric for wireless networks based on remaining battery power at nodes was proposed for shortest-cost routing algorithms, assuming constant transmission power. Power-aware metrics, where transmission power depends on distance between nodes and corresponding shortest power algorithms were also proposed. We define a power-cost metric based on the combination of both node's lifetime and distance-based power metrics. We investigate some properties of power adjusted transmissions and show that, if additional nodes can be placed at desired locations between two nodes at distance d, the transmission power can be made linear in d as opposed to d/sup /spl alpha// dependence for /spl alpha/ /spl ges/ 2. This provides basis for power, cost, and power-cost localized routing algorithms where nodes make routing decisions solely on the basis, of location of their neighbors and destination. The power-aware routing algorithm attempts to minimize the total power needed to route a message between a source and a destination. The cost-aware routing algorithm is aimed at extending the battery's worst-case lifetime at each node. The combined power-cost localized routing algorithm attempts to minimize the total power needed and to avoid nodes with a short battery's remaining lifetime. We prove that the proposed localized power, cost, and power-cost efficient routing algorithms are loop-free and show their efficiency by experiments.

Two metrics where transmission power depends on distance between nodes, and a cost aware metric based on remaining battery power at nodes (assuming constant transmission power), together with corresponding non-localized shortest path routing algorithms, were recently proposed. We define a new power-cost metric based on the combination of both node's lifetime and distance based power metrics. We then propose power, cost, and power-cost GPS based localized routing algorithms, where nodes make routing decisions solely on the basis of location of their neighbors and destination. Power aware localized routing algorithm attempts to minimize the total power needed to route a message between a source and a destination. Cost-aware localized algorithm is aimed at extending battery's worst case lifetime. The combined power-cost algorithm attempts to minimize the total power needed and to avoid nodes with short remaining lifetime. We prove that these localized power, cost, and power-cost efficient routing algorithms are loop-free.