The Gabriel graph is a long-known
planar graph that contains edges between nodes u and v if and only if no other
nodes are located within the circle centered in the middle of edge (u,v) and
with diameter kuvk. It has some good properties when used for routing in
wireless networks, such as localized computing and an energy e?±cient path
finding [33].
The process is as follows: applying the face routing, when node v finds
that no neighbor is further north than itself, it forwards the message to its
neighbor v1 that has the largest angle ?® formed from wv to vv1 in clockwise
direction (see Figure 4(a)). After v1 receives the message, it will perform the
same operation as node v. Eventually, the message will bypass the void region,
and be received by node u.
The handling of ???void areas??? in a sensor network would introduce extra
overhead to the quorum system. Since nodes don??™t have the global topology
of the entire network, the message received by the nodes truly located on
the boundary of the network will be propagated along the boundary until it
traverses back to either node v as shown in Figure 4(b), or meets some node
at its traversed route as shown in Figure 4(c). In either case, the message
travels a lot of unnecessary distance. However, this overhead is inevitable if
the case of ???void areas??? has to be handled.
(a) (b) (c)
v1
v
u
v
v
w
Fig. 4. Protocol Implementation.
C.
Pages:
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403