See Figure 1(a) for illustrations. Hereafter, we always assume that
UDG(V ) is a connected graph. We call all nodes within a constant k hops of
a node u in the unit disk graph as the k-local nodes (or k-hop neighbors) of u,
denoted by Nk(V ). It is clearly impossible to collect up-to-date neighborhood
information for large k e?±ciently, therefore, k is usually a small integer such
as 1 or 2 in sensor networks. The size of the unit disk graph could be as large
as the square order of the number of sensor nodes, such as the example shown
in Figure 1(b). So in topology control protocol, we try to construct a subgraph
for the unit disk graph UDG(V ) so that the subgraph is sparse and can be
constructed locally in an e?±cient way.
(a) a UDG with eight sensors (b) a UDG with 100 sensors
Fig. 1. Examples of unit disk graphs.
Notice that a unit disk graph is not a perfect model for practical sensor
networks, since the transmission ranges of sensor nodes could be di?®erent and
not be perfect disks. In [1], Zhou et al. studied the impact of radio irregularity
on wireless sensor networks. Recently, many other more practical models have
been proposed, such as quasi unit disk graph [2] and mutual inclusion graph [3].
114
Chapter 5 Topology Control for Wireless Sensor Networks
However, since the unit disk graph has its theoretical simplicity, we still use
it to model the sensor network in our chapter.
We also assume that all wireless sensor nodes have distinctive identities
(denoted by ID hereafter).
Pages:
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197