Download (direct link):
Observe that in a connecting range assignment any node must have a transmitting range at least equal to the distance to its closest neighbor. Let RAmin be the range assignment for S(G) such that every node have a transmitting range equal to the distance to its closest neighbor. Given the properties of gadgets, RAmin is such that nodes in the VX-components have transmitting range X, and nodes in the YZ-components have transmitting range X'. Because of the symmetry of points in the plane, RAmin is symmetric. The communication graph induced by RAmin is composed of m + 1 connected components, where m = |E|: the YZ-components of the m gadgets and the union VX of all the VX-components of the gadgets. Hence, in order to have a connected and symmetric communication graph, we need to define some bridge points between VX and every YZ-component.
82 THE RANGE ASSIGNMENT PROBLEM
Let Y = (J Yab, X = (J Xab, Z = (J Zab, and V = (J Vab. The following
a,beE a,beE a,beE a,beE
lemma characterizes the properties of the optimal symmetric range assignment for S(G).
Definition 7.4.3 (Canonical RA) A symmetric connecting range assignment RAc for S(G) is said to be canonical if
- RAc(v) = X for any v e X;
- RAc(v) = X' for any v e Z;
- RAc(v) = X or RAc(v) = X + e for any v e V;
- RAc(v) = X' or RAc(v) = X + e for any v e Y.
Lemma 7.4.4 (Blough et al. 2002) Let S(G) be a set of points placed in R2 according to the above described construction, where y, X, and e are positive constants such that
(yk)2 >’E^l((X + e)2-X2) + (X + e)2. (7.1)
Then, for any symmetric connecting range assignment RA for S(G), there exists a canonical range assignment RAc such that c(RAc) < c(RA).
Proof. We prove that any symmetric connecting noncanonical range assignment RA can be transformed into a feasible canonical range assignment RAc through a sequence of iterative steps, where each step does not increase the cost of the range assignment. Every step considers a node u whose transmitting range is not canonical, and derives a symmetric connecting range assignment such that the transmitting range for u is canonical. Since the
THE RANGE ASSIGNMENT PROBLEM
number of noncanonical points in S(G) decreases at each step, the iterative process ends in finite time.
We describe the generic step of this process. Let v be a noncanonical point and let RA(v) be its transmitting range. We have the following cases:
1. RA(v) < yk. In this case, the transmitting range of v is not sufficiently large to reach points in the YZ-components of other gadgets. Note that if RA(v) < k + e then v cannot be a bridge between the YZ-component and the VX-component. Hence, its transmitting range can be decreased to k or k' (depending on whether v e V U X or v e Y U Z) without disconnecting the graph and preserving symmetry. Assume now RA(v) > k + e. Assume without loss of generality that v e gab, for some (a, b) e E. If v e Vab U Yab, then its transmitting range can be reduced to k + e without disconnecting the graph and preserving symmetry. Otherwise, consider the range assignment RAab such that
- RAab (w) = RA(w) for any w e S(G) - gab;
- RAab (a) = RAab (yab) = k + e;
- RAab (b) = k and RAab (yab) = k ;
- RAab (x ) = k for any X e Xab;
- RAab (z) = k' for any Z e Zab.
Given the properties of points in a gadget, it follows that RAab is symmetric. Furthermore, the communication graph resulting from RAab is connected, and RAab is canonical in gab, and hence, in v. Let c(S(G)\gab) = Jf veS(G)\gab RA(v)2. Given the requirement for symmetry, we have
c(RA) > c(S(G)\gab) + 2 ? RA(v)2 + (h + 1) ? k2 + (h + 1) ? k/2,
where li = \Xab | and h = \Zab |.
On the other hand, we have
c(RAab) = c(S(G)\gab) + 2 ? (k + e)2 + (li + 1) ? k2 + (l2 + 1) ? k,2_
Since RA(v) > k + e, we can conclude that c(RA) - c(RAab) > RA(v)2 - (k + e)2 > 0.
2. RA(v) > yk. In this case v could be a bridge point between many YZ-components and VX. Assume without loss of generality that v e gab, for some (a, b) e E. We first transform the range assignment as described above, obtaining the range assignment RAab, with c(RA) - c(RAab) > y2k2 - (k + e)2. However, RAab in general is not symmetric and could leave some YZ-components isolated. For this reason, we consider the isolated components YZ1,..., YZ* in the graph generated by RAab, and for each of this component we apply the same construction as for the gadget gab. The resulting range assignment RAab is symmetric and connecting. In order to prove the lemma, we have to show that c(RAab) < c(RA). Note that the cost associated with any YZ-component YZ, could increase in the new range assignment RAab. However, observing that because of symmetry at least one node in YZ, must have transmitting range of at
THE RANGE ASSIGNMENT PROBLEM
least yX, the increase for every YZ-component is bounded by 2(A. + e)2 — (yX)2 — X2. Considering that k < m — 1, we have
c(RA) — c(RAab) > y2X2 — (X + e)2 — (m — 1)(2(X + e)2 — (yX)2 — X2) > 0
by inequality (7.1). This ends the proof of the lemma.