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 find the temperature in a room
of a building, the specific 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 fixed and always send information to a specific 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 finite
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.