Kinetic Spanning Trees in Mobile Ad-Hoc Networks

Routing

Introduction

Routing in wireless networks proves a difficult problem due to the inherent mobility of the nodes. Power consumption remains one of the prominent concerns as it directly alters the lifetime of the network. If power is allocated wisely, the batteries of the nodes can be preserved, enabling them to stay connected for a much longer duration. The optimal routes in terms of minimum-power consumption, however, require frequent updating in order to be maintained, implying increased overhead across the network and as a result decreased throughput for a fixed bandwidth. The design goal translates to maintaining optimal routes with the least number of overhead messages.

The proposed algorithm models the trajectory of a node through a piece-wise linear curve for a time interval as x(t) = x(t0) + dx(t0)/dt*t, rather than its position at a single time instant x(t0) as in the benchmark algorithm. This enables computing in a distributed manner the sequence of minimum spanning trees through time, or the kinetic spanning tree [1], rather than just one spanning tree for time instant t0. The kinetic structure renders the time instances in which the minimum spanning tree changes a priori, and how it changes. These pre-computed routes are valid until any node changes trajectory, necessitating event-driven updates only at these time instances, as opposed to sampling at fixed intervals.

Even though the nodes are modeled moving in a linear trajectory, actual knowledge of their absolute position is unnecessary. Rather the sequence of minimum spanning trees is constructed through the measured power consumption in transmitting messages between two nodes as a function of time. In addition the number of iterations to establish the series for a time interval equals the number to establish the minimum spanning tree for a single time instant: the difference is that more information is packed into a single transmission.The tradeoff lies in increased computation at each node to determine the sequence.We argue, however, that the power required in processor speed for the increased computation is much less than that required for computing and maintaining optimal routes at fixed update periods. In fact, our technique drastically reduces the number of routing transmissions required in comparison.




Simple Example

The following example illustrates the kinetic minimum-power spanning tree for the mobile nodes A, B, C, and D to the sink node, S. Table (a) contains their trajectories and Figure (b) displays the routes at time t=0 (solid) and t=8.4 (dashed). Note the changes to the tree and their associated times of occurence, computed a priori at t0=0 and summarized in Table (c). For example, at time t=1.252 node A stops routing directly to the sink, and rather routes to S through node B.
(a) Node Trajectories
Node
Trajectory
S
(0, 0)
A
(-1.0-0.1t, 1)
B
(-0.4t, 1.5-0.2t)
C
(2-0.5t, 1+0.2t)
D
(0,2+0.3t)
(b) Routing at t=0 (solid) and t=8.4 (dash)
(c) Changes in Kinetic Tree
t
Change
1.252
A --> B
2.193
D --> C
3.754
A --> S
4.085
B --> A
5.692
C --> A
8.378
D --> A
8.452
D --> S





Experimental Results

 Consider a network of N nodes spread randomly over a 10 mile x 10 mile area at initialization. The number of nodes varies as 20, 50, 100, or 200 by simulation. We assign to each node a random velocity vector, whose magnitude does not exceed 60 miles/hour. We assume that the underlying communication links require 100 ms to transmit a packet across a single link and set the unit time step accordingly. The simulations were run for a duration of 1 minute. In Figures (a)-(c), each node maintains a fixed trajectory, while in Figure (d) the probability that some node randomly changes trajectory is uniformly distributed between zero and ten seconds. There is a trajectory change, on average, every five seconds.

(a) The number of overhead messages required to achieve convergence for one execution of the algorithm is slightly higher for the proposed than the benchmark. The figure displays the ratio of messages for the two algorithms as a function of the transmission radius, when each algorithm is executed once at time t0. It is clear that the ratio is close to one over a range of transmission radii and for the four different network sizes. (b) The power ratio quanitifes the departure of the benchmark routes from the minimum-power routes of the proposed algorithm. The measure varies according to the update period of the benchmark algorithm: a small enough period reduces the power ratio to unity... This figure displays the departure from the optimal routes of the benchmark algorithm as a function of the update period, when the algorithm is executed to recompute routes. The power ratio (i.e. the ratio of the sum of all the benchmark links to that of the proposed links integrated over one update period) quantifies this departure. The benchmark algorithm requires frequent updating to maintain optimal routes, and as show in the next figure, frequent updating requires many more overhead messages. (c) ...however a smaller period implies more frequent execution of the algorithm, and hence an increased number of total overhead messages. The power ratio quanitifes the departure of the benchmark routes from the minimum-power routes of the proposed algorithm. The figure shows that the benchmark algorithm requires frequent updating, hence an increased number of total messages, to reduce the power ratio to unity. (d) The figure reports the increase in overhead messages (compared to the proposed algorithm) incurred by the benchmark algorithm to maintain its routes for one minute. The measure varies according to the update period of the benchmark algorithm: a smaller period reduces the power consumption of the routes, but in turn necessitates execution of the algorithm each period, and hence more total messages. The proposed algorithm minimizes the overhead messages necessary to maintain the the minimum-power routes.





Clustering

Introduction

While the kinetic routing algorithm minimizes the number of overhead messages required to maintain optimal routes, this number may still prove to be prohibitive as the network grows. A popular approach to deal with issues of scalability suggests grouping nodes into clusters: the ordinary nodes of a cluster elect a clusterhead and route through it to the other nodes in the network, at the expense of sub-optimal routes. This achieves the seeming effect of a smaller network.

Here we propose the extension of the kinetic routing algorithm to clustering as well. We study the tradeoff between minimum-power routing and clustering, and accordingly develop a kinetic algorithm which simultaneously organizes both the clusters and the routes of the network. A single parameter controls the degree of clustering and consequently the degree of sub-optimality, rather than arbitrary parameters commonly found in literature such as maximum cluster size or maximum distance between nodes. The proposed algorithm promotes intelligent clustering by grouping into clusters nodes with similar trajectories. It converges in a finite number of iterations to both stable routes and stable clusters, and by setting the cluster parameter to 0 collapses to the original routing algorithm with no clusters and optimum routes.