UCLA

uclatopo.gif (12675 bytes)

Description

Distributed Clustering Algorithm ensures that all nodes form clusters. Also uses LCC algoritm to minimize reclustering required. All nodes within a cluster share same CDMA code and communication between clusters require gateways to resynchronize with other clusterhead. All intercluster packets pass through these gateway nodes. Bandwith  is controlled by a PRMA (packet reservation media access) style polling scheme. Delay increases dramatically if packets traverse other clusters, while within a cluster there exist excellent connectivity.

The clusterheads are responsible for synchronization, fowarding packets within the cluster and through the cluster via gateways. Routing is done by maintaining two types of tables. The first is a cluster member  and the destiation clusterhead table at each node. This table is used to map destination addresses to the destination clusterhead address. This is broadcasted peridoically and a node will update its table when it receives a new one from its neighbor. Sequence numbers are attached to the updates as in DSDV to avoid stale tables. The second table is used to select the next node needed to reach the destination cluster. It is constructed by a minimum hop to a clusterhead criteria. Packets are sent first to a clusterhead and then get routed appriately to the correct gateway. This gateway then forwards it the adjacent clusterhead and this process can repeat many times until the final clusterhead forwards the packet to the final destination. The exact method used to distribute the hop information varies slightly from paper to paper. DSDV style updates are sometimes used to distribute the minimum hop to clusterhead infomation. Sometimes all nodes participate in these updates and sometimes only gateways and clusterheads.

Note that most of the results that come from the UCLA project is through simulation.

 

Definitions:
LCC -- Least Clustering Change
This algorithim used to reduce traffic caused my membership changes that can occur because of mobile mobility. Two conditions cause reclustering. One is when two clusterheads come within range of one another. The other is when a node becomes disconnected from any other cluster. This was an improvement in stability over existing algortims which select the clusterhead every time the cluster membership changes.

 

PRMA -- Packet Reservation Media Access
Maybe viewed as a combination of slotted Aloha and TDMA. Designed orginally for packet radio to take advantage of silences in speech. This allowed for increase capacity. Allows regular access for periodic information by letting it reserve slots for the next transmission on the trailer of their current packet. New sources contend as in an Aloha scheme for available slots.
DSDV -- Destination Sequenced Distance Vector
A routing protocol used for ad-hoc networks. It is a variant of the simple distance-vector routing or (Bellman-Ford) algorithm. Sequence numbers are attached to routing updates to ensure which update is the most recent and from which node. The destination node advertises increasing even number sequence numbers while any node which detects breakage will advertise a new increased number (now odd). This prevents looping and will let other nodes reconfigure properly when the new even number update from the destination arrives.

 

 

 

For More Information