Summary
|
For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE. |
|
An Optimal Certificate Dispersal Algorithm for Mobile Ad Hoc Networks Hua ZHENG Shingo OMURA Jiro UCHIDA Koichi WADA Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Vol.E88-A No.5 pp.1258-1266 Publication Date: 2005/05/01 Online ISSN: DOI: 10.1093/ietfec/e88-a.5.1258 Print ISSN: 0916-8508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: certificate dispersability, certificate dispersal algorithm, mobile ad hoc network, optimal algorithm, Full Text: PDF(340.5KB)>>
Summary: In this paper, 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 system, special data called certificate is issued between two users and these issued certificates are stored among the network. Our final purpose on this certificate dispersal problem is to construct certificate graphs with lower dispersability cost which indicates the average number of certificates stored in each node in an ad hoc network. As our first step, when a certificate graph is given, we construct two efficient certificate dispersal algorithms for strongly connected graphs and directed graphs in this paper. We can show 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(DG +|E|/|V|) and O(pG dmax +|E ′|/|V ′|) respectively, where DG is the diameter of G, dmax is the maximum diameter of strongly connected components of H and pG is the number of strongly connected components of H. Furthermore, we give some new lower bounds for the problem and we also show that our algorithms are optimal for several graph classes. | ||||||||||
| ||||||||||
