Download (direct link):
A second, more serious opportunity for optimization is motivated by the example reported in Figure 14.12: node u’s current power level is P2, resulting in covering all the nodes in area A2. Thus, this transmit power is sufficient to have at least k - 1 symmetric neighbors. According to KNeighLev’s specification, u then sends a help message at power level P3, forcing all the nodes in area A3 - A2 to increase their power to level at least P3. This mechanism induces unnecessary power increases, because all the four nodes in A3 - A2 must increase their power level, while the power increase of a single node would be sufficient to meet the requirement on the symmetric neighbors count at node u.
A more subtle situation in which KNeighLev displays inefficient behavior is depicted in Figure 14.13. The target number of symmetric neighbors is k = 4. At the current power level P1, node u has at most three symmetric neighbors. To increase the symmetric neighbors count, node u sends a help message at power level P2, forcing node v, which currently has power level Po, to increase its power to level P2. Then, the overall power increase for node u to have the target number of symmetric neighbors is P2 - Pi for node u, and P2 - P0 for node v. Note that there exists a third node in this scenario, node w, whose power level
Figure 14.12 Example of inefficient KNeighLev’s behavior. The target number of neighbors is k = 5. Area Ai denotes the radio coverage of node u at power level Pi. At power level P2, node u has at most 4 = k — 1 symmetric neighbors. Thus, it sends the help message at power level P3, forcing all the nodes in A3 — A2 to increase their power to level at least P3.
LEVEL-BASED TOPOLOGY CONTROL
/ • / / A0
/ / •
\ \ u i • 1 i ]
Figure 14.13 A second, more subtle example of inefficient KNeighLev’s behavior. The target number of neighbors is k = 4. The power level of node v is P0, and the power level of node w is P3. At power level Pi, node u has at most 3 = k - 1 symmetric neighbors. Instead of sending the help message at power level P2, node u might autonomously increase its power level to P3, thus fulfilling the symmetric neighbor count requirement without forcing node v to increase its power level.
is set to P3, and thus it is in u’s incoming neighbor set. Node u is aware of node w and of its current power level. So, instead of sending the help message at power level P2, it could decide to autonomously increase its power level to P3. With this power level setting, node u would satisfy the symmetric neighbor count requirement. Note that this second option is nonoptimal from node u’s point of view (it increases u’s power level of two steps, instead of a single step as in the standard KNeighLev specification); however, this solution might be optimal from a local neighborhood point of view: if
(P2 - P1) + (P2 - Po) > (P3 - P1),
it is locally optimal to increase u’s transmit power of two steps. For instance, if P0 = 1 mW, P1 = 5 mW, P2 = 20 mW and P3 = 30 mW, the ‘unselfish’ behavior of node u (the second option described above) is locally optimal from the energy consumption point of view. Conversely, if P0 = 5 mW, P1 = 20 mW, P2 = 30 mW and P3 = 50 mW, the situation is reversed.
The examples shown in Figures 14.12 and 14.13 motivated the authors of (Blough et al. 2003c) to design an optimized version of KNeighLev, which is called KNeighLevU (U stands for ‘unselfish’).
Three additional types of control messages are used in KNeighLevU: enquiry, reply, and selective help messages. Enquiry and reply messages contain the same information as beacon and help messages (sender ID and transmit power level), while the selective help message contains the ID of the sender and the ID(s) of the node(s) that must increase its (their) transmit power levels.
LEVEL-BASED TOPOLOGY CONTROL
Suppose node u, which currently has less than k symmetric neighbors, is transmitting at power level Pi:
1. Instead of sending a help message at power level Pi+1, node u sends an enquiry message at power level Pi+i.
2. When a node (say, node v) in u’s transmitting range whose current power level is below Pi receives the enquiry message, it does not immediately step up the power level; instead, it sends to u a reply message at temporary power level Pi. The purpose of this message is to inform u that v is a potential helper, which is currently using a certain power level.
3. Once node u has gathered the information from all its potential helpers, it is able to compute the locally optimal solution, accounting also for the nodes in Ni(u) that might become symmetric neighbors by simply increasing u’s power level. Then, node u schedules one of several possible actions, depending on the locally optimal solution that has been identified. In particular, u can
(a) increase its own power level, so as to reach more nodes in Ni(u);
(b) send a selective help message, asking some of the nodes in the neighborhood to increase their power levels;