12.4. DISTRIBUTED APPLICATIONS 153

to use UDP/IP protocols and simpler addressing schemes are conceivable. For instance, in some

applications, the location may be a suitable address. If the goal is to ﬁnd the temperature in a room

of a building, the speciﬁc ID of the corresponding sensor does not matter. If the nodes are mobile,

then a suitable addressing based on location is more challenging.

Routing in a sensor network may be quite challenging, depending on the application. If the

nodes are ﬁxed and always send information to a speciﬁc gateway, then the network can run some

shortest path algorithm once or rarely. If the nodes are moving, the routing algorithm can either run

in the background or nodes can discover routes when needed. As for the other protocols, routing

should be designed with a good understanding of the characteristics of the application.

In-Network Processing and Queries

Say that the goal of a sensor network is to measure the highest temperature to which its nodes

are exposed. One approach is for all the nodes to periodically report their temperature and for the

supervising host to calculate the largest value. A different approach if for each node to compare its

own temperature with the value that its neighbors report; the node then forwards only the maximum

value. A similar scheme can be designed to measure the average value of the temperatures. More

generally, one can design a communication scheme together with processing rules by the individual

nodes to calculate a given function of the node measurements. The goal may be to minimize the

number of messages that the nodes must transmit.

For a given sensor network, one may want to design a query language together with an

automatic way of generating the processing rules and the messages to be exchanged to answer the

query.

12.4 DISTRIBUTED APPLICAT IONS

Networks execute distributed applications to implement many different protocols including BGP,

OSPF, RIP and TCP. More generally, nodes on a network can be used to implement distributed

applications for users. The properties of distributed applications are of interest to designers of the

applications and the protocols. This section explores a number of representative applications and

their properties.

12.4.1 BELLMAN-FORD ROUTING ALGORITHM

In the Routing chapter, we explained that the Bellman-Ford algorithm converges after a ﬁnite

number of steps if the network topology does not change during that time.Recall that when running

this algorithm, each node i = 1, 2,...,J maintains an estimate x

n

(i) of its shortest distance to a

given destination node, say node D. Here, n = 0, 1,... denote the algorithm steps. In the basic

version of the algorithm, if node i gets a new message x

n

(j) from a neighbor j , the node updates

its estimate to x

n+1

(i) that it calculates as follows:

x

n+1

(i) = min{x

n

(i), d(i, j) + x

n

(j)}.

Get *Communication Networks* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.