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

1.15 LOCALIZED PROTOCOLS AS THE SOLUTION FRAMEWORK

On the basis of the information required to run algorithms, existing algorithms or protocols in wireless networks can be roughly classified into two groups: globalized protocols and localized protocols. In globalized protocol, one or more nodes (usually the central node like a BS) need(s) to gather global information ranging from detailed information such as the whole network topology to simple information of global nature, such as the maximum degree in the network, to execute the protocol. However, in localized protocol, each node makes protocol decisions based solely on some local knowledge available. To be more precise, local knowledge in wireless networks is based on information from neighbors within k hops from a certain node, where k is usually a small integer like 1 or 2. Some protocols, for example beaconless georouting, do not require any information from neighbors. Another such example is the probabilistic flooding scheme (Ni et al., 1999) where each node makes its own decision about possible retransmission using a predefined fixed probability.

Shortest (weighted) path routing is a typical globalized protocol which computes the best route between the source and the destination. Both well known shortest weighted path algorithms, Dijkstra's and Prim's, require all nodes to know full network topology (all nodes and all edges between them) to make proper decisions. Globalized shortest path routing has huge setup costs because ...