An optimal certificate dispersal algorithm for mobile ad hoc networks

摘要

We focus on the problem that in an ad hoc network, how to send a message securely between two users using the certificate dispersal system. In this paper, we construct two efficient certificate dispersal algorithms. We can prove that for a strongly connected graph G = (V, E) and a directed graph H= (V', E'), new upper bounds on dispersability cost on the average number of certificates stored in one node are O(D/sub G/+|E|/|V|) and O(pd/sub max/+|E'|/|V'|) respectively, where D/sub G/ is the diameter of G, d/sub max/ is the maximum diameter of strongly connected components of H and p is the number of strongly connected components of H. Furthermore, we can prove our algorithms are optimal for several graph classes.