Books
in black and white
Main menu
Share a book About us Home
Books
Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics
Ads

Topologi control in wireles ad hoc and sensor network - Santi P.

Santi P. Topologi control in wireles ad hoc and sensor network - Wiley publishing , 2005. - 282 p.
ISBN-10 0-470-09453-2
Download (direct link): topologycontess2005.pdf
Previous << 1 .. 69 70 71 72 73 74 < 75 > 76 77 78 79 80 81 .. 122 >> Next

Let us now suppose that the TC protocol is executed again at time t + e. The changes in u’s local view of the network topology are reported in Figure 13.4. The neighbors of u with LMST are NLMST(u) = {o, w, z}, and the power settings are as follows:
node w —> power level p0 node z —> power level p0 node o —> power level p3 broadcast power —> power level p3
As in the previous case, node u sends four messages to compute its neighbor set: one to broadcast its ID and position and three messages to probe the links with nodes o, w and z.
The neighbors of u with KNeigh are NKN(u) = {q, v, w,z} (note that all these nodes are symmetric neighbors of u), and the broadcast power level is set to p2. In order to
(a)
(b)
Figure 13.4 Local view at node u of the topology computed by LMST (a) and KNeigh
(b) at time t + e. The parameter k in KNeigh is set to 4. The links connecting node u to its neighbors (gray nodes) are in bold.
DEALING WITH NODE MOBILITY
151
Table 13.1 Comparison of u’s local view of the network topology at time t and t + e with the LMST and KNeigh topology control protocols. In the entry for power levels, bc stands for broadcast power
LMST t t + e
N LMST (u) {o, v, z} {o, w, z}
Power levels v —> po s 1 ^3 O
z —> P1 M 1 ^3 o
O > P2 o —> p3
bc > P2 bc —> p3
KNeigh t t + e
NKN(u) {o, v, w, z} {q, v, w, z}
Power level bc —> p2 bc —> p2
compute its neighbor set, node u sends two messages: one to broadcast its ID and one to broadcast its neighbor list.
Table 13.1 summarizes u’s local view of the network topology at time t and t + e with the two protocols. The neighbor set changes only slightly with both protocols: one out of three neighbors is changed with LMST and one out of four neighbors is changed with KNeigh. The situation is considerably different if we consider the power level settings: with LMST, all the power settings are changed, including the broadcast power level; with KNeigh, the broadcast power (which is the only power setting used by the protocol) is unchanged at level p2.
Summing up, we can conclude the following. The topology computed by LMST is quite sparse (one of the design objectives in LMST is to reduce the node logical degree), and it is computed using location information. This implies that the generated topology, although it has good properties (e.g. it preserves worst-case connectivity), is not very resilient to node mobility: a relatively modest change in node positions is sufficient to cause a reexecution of the protocol (otherwise, many route breakages are experienced at the routing layer - see above). This problem is exacerbated by the use of per-packet transmit power adjustment. In order to prevent a surge of routing message overhead, the only possible solution is to recompute the network topology quite frequently, which also causes a certain message overhead (in the example above, node u sends four messages to compute its local view of the network topology). On the other hand, KNeigh produces a relatively denser topology (with k = 4, almost all the network nodes have logical and physical degree equal to four), which has good properties in the average case (e.g. connectivity w.h.p.). The topology is built on the basis of the concept of distance ordering of the neighbors, a notion that provides more resilience to node mobility than that of local MST: relatively modest changes in the node positions are unlikely to cause a dramatic change in the neighbor order. Combined with the use of a unique power level (the broadcast power) to send packets, this implies that the network topology can be recomputed less frequently as compared to LMST, with a positive effect on the number of control messages circulating in the network. Furthermore, computing the topology with KNeigh requires exchanging fewer
152
DEALING WITH NODE MOBILITY
messages than those needed to compute G-MST: in the example above, node u sends two messages instead of four; if we consider the overall number of exchanged messages, KNeigh exchanges 2n messages, while LMST exchanges O(n2) messages. This fact again plays in favor of KNeigh, further reducing the control overhead generated by KNeigh with respect to that generated by LMST.
Although examples of mobile networks in which the relative advantage of using KNeigh instead of LMST is less evident can be easily built, it is virtually impossible to find an example in which using LMST in mobile networks is better than using KNeigh. The reason for this is simple: contrary to LMST, KNeigh combined with the use of periodical transmit power adjustments complies to most of the guidelines discussed in the previous section: KNeigh is fast, it generates a ‘reasonably good’ topology composed of bidirectional links, it is based on mobility-resilient information (distance-based neighbor ordering), and it uses periodical power adjustment.
13.3 The Effect of Mobility on the CNN
In the previous sections, we have discussed in detail the guidelines that should inspire the design of TC protocols for mobile ad hoc networks, and we have argued in favor of a neighbor-based approach to TC. One protocol exploiting this type of information is the KNeigh protocol, which we have discussed in the context of mobile networks in Section 13.2. However, we have not yet answered a fundamental question concerning the utilization of KNeigh in mobile networks, that is: which is the appropriate setting for the desired number of neighbors k when the network is mobile? Should we use the value computed for stationary networks, or a higher (or a lower) one? Putting it more formally, which is the effect of node mobility on the CNN?
Previous << 1 .. 69 70 71 72 73 74 < 75 > 76 77 78 79 80 81 .. 122 >> Next