Download robust algorithms for infrastructure establishment in

Transcript
CHAPTER 4. INFORMATION POTENTIALS
81
categorized into a set of data types. These data types might be chosen from a fixed
universe, such as the parking spots or road exits. The nodes holding data with a
particular type are called sources. The nodes that search for data of this type are
called sinks. We explore in this section information diffusion schemes for pushing
information about data sources into the network, so as to later facilitate information
discovery. We establish an information potential field, that indicates the intensity of
the diffused strength at any node, for an existing data type.
4.4.1
Harmonic Functions
The key to our information gradient scheme is the notion of harmonic functions. On
a domain Ω ⊆ R2 , a harmonic function f is a real function whose continuous second
partial derivative satisfies Laplace’s equation [35]
∂ 2 f (x, y) ∂ 2 f (x, y)
+
= 0.
∂x2
∂y 2
If the value of the function is specified on all boundaries, referred to as Dirichlet
boundary conditions, the solution to the Laplace’s equation is unique.
A dense sensor network can be viewed as a discrete approximation of the underlying continuous geometric domain. A node is either interior or boundary, which
can be thought of as points sampled from the interior and boundary, respectively, of
some underlying geometric domain. Boundary nodes are used for specifying Dirichlet
boundary conditions by fixing their function values. Assuming an undirected network, and approximating derivatives using finite differences, Laplace’s equation in
the discrete form becomes
f (u) =
X
1
f (v) ,
deg(u)
v∈N (u)
for all interior nodes u. In the generalized definition for directed networks, we replace