In this section, we review the
definitions and properties of some geometrical spanners which could be used
in wireless sensor networking applications.
2.1 Planar Spanners
A network topology is preferred to be planar (no two edges crossing each other
in the graph) to enable some localized routing algorithms work correctly and
e?±ciently, such as Greedy Perimeter Stateless Routing (GPSR) [14], Greedy
Face Routing (GFG) [15], Adaptive Face Routing(AFR) [16]. and Gready
Other Adaptive Face Routing (GOAFR) [17]. Notice that with planar network
topology as the underlying routing structure, these localized routing
protocols guarantee the message delivery without using a routing table: each
intermediate node can decide which logical neighboring node to forward the
packet to, using only local information and the position of the source and the
destination. We then review several planar structures which have been used
in sensor networks as routing topologies.
Relative Neighborhood Graph and Gabriel Graph
The relative neighborhood graph, denoted by RNG(G), is a geometric concept
proposed by Toussaint [18, 19]. It consists of all edges uv ??? E such that there
is no point w ??? V with edges uw and wv in E satisfying kuwk < kuvk and
kwvk < kuvk. Thus, an edge uv is included if the intersection of two circles
centered at u and v and with radius kuvk do not contain any vertex w from
the set V such that edges uw and wv exist in E.
Pages:
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202