Figure 4.1 shows both the Delaunay
triangulation and the Voronoi diagram. It is shown that the Voronoi diagram is
a centroidal Voronoi diagram [18]. The centroidal Voronoi diagram is used for the
quantization of planar space and evaluation of the coverage area [14], [18].
If the mobile robots are sparsely deployed in an open space, the algorithm can
be used to congregate the mobile robots to cover a certain area. Figure 10 shows
the deployment results when the mobile robots use Delaunay triangulation and partial
Delaunay triangulation topological structure respectively, applying the controller
in eq. (4). Both of these two topology structures can congregate the mobile robots
to form a pattern similar to Figure 11(b). Thus, using the proposed algorithm, the
mobile sensor network can either disperse or congregate the mobile robots in responding
to the task requirements. When the partial Delaunay triangulation is used
to define the topological structure, the final pattern is more dependent on the initial
deployment because each robot considers only the positions of the robots within
??’60 ??’40 ??’20 0 20 40 60
??’60
??’40
??’20
0
20
40
60
??’60 ??’40 ??’20 0 20 40 60
??’60
??’40
??’20
0
20
40
60
Chapter 3 A Scalable Graph Model and Coordination Algorithms 77
its communication range and some neighbors in Delaunay triangulation may not be
counted when employing the algorithm.
(a) Initial Deployment with DT
neighborhood
(b) Final Deployment based on a
DT neighborhood
(c) Initial Deployment with PDT
neighborhood
(d) Final Deployment based on a
PDT neighborhood
Fig.
Pages:
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150