Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication

4.3 APPLICATIONS OF COST TO PROGRESS RATIO FRAMEWORK TO GEOROUTING

Stojmenovic (2006) proposed a framework for designing network layer protocols for sensor networks including localized routing, broadcasting, area coverage, and so on. The framework is based on optimizing the ratio of the cost to progress, where the cost to reach the next hop forwarding node in routing is expressed in a certain metric, and the progress is a measure of advance toward the destination.

Examples of cost metric are hop count, power, reluctance, power * reluctance, delay, and expected hop count (Stojmenovic, 2006) (see also Chapter 1). Each link has a cost measure, which depends on the assumptions and metrics used. The framework assumes that each node knows the cost of each of its links to the neighboring nodes. The basic idea of the framework is as follows. Suppose the source or current node S has k neighbors, where only neighbors closer to the destination than the current node are considered to ensure progress at each step. That is, S has k choices to forward a packet toward the destination. Node S then computes C_i/P_i, i = 1, 2, …, k for each neighbor, where C_i and P_i are the cost and progress, respectively, of ith candidate neighbor. The neighbor with the minimum cost to progress ratio is selected to forward the packet. The same rule is continuously applied by the receiving node to select the next hop. The routing process continues until the destination is reached or no neighbors with progress are available. ...