Correctness of fault-tolerant cluster-based beacon vector routing for ad hoc networks

In this paper, correctness is proven for a new clustering method and fault-tolerant routing approach to beacon vector routing. The correctness is proven through termination, liveness, and safety properties. The complexity of the proposed algorithms is analyzed. The clustering approach provides load balancing between clusters, and organizes beacon placement which reduces the number of hops for packet transmissions. The fault-tolerant routing approach improves significantly the percentage of successful packet transmission attempts, and reduces flooding in the network, in the presence of multiple simultaneous faults.