24-03-2012, 11:48 AM
A Reliable Topology for Efficient Key Distribution in Ad-Hoc Networks
Efficient Key Distribution in Ad-Hoc Networks.pdf (Size: 310.52 KB / Downloads: 32)
Introduction
Recent advances in wireless and mobile technologies
have fostered the development of ad-hoc networks. Security
of ad-hoc networks remains a major concern. Cryptography
is a viable means to secure ad-hoc networks, but how
to distribute the key remains a challenging issue.
The private-key distribution is an attractive means to
maintain data confidentiality. However, if a malicious node
acquires the key, the purpose of cryptography falters, and
hence several protocols have been proposed to secure distribution
of private keys.
Related works
Here, we briefly describe related works. There have been
a rich literature on public key management.
Zhou and Haas [4] proposed the method by using threshold
cryptography to distribute the CA functionality to several
nodes. Some specific nodes, called servers, store public
keys of all the nodes in the network, as well as are aware
of the public keys of other servers. They can establish secure
links among them. In [5], the authors proposed a trust
model for ad-hoc networks without an CA. In this model,
each node signs certificates for other nodes. Capkun et al.
[6] proposed a fully distributed self-organizing public key
management scheme.
Existing algorithms
In this section, we first review the LMST algorithm.
Since LMST is a 1-edge connected network, it has some
reliability deficiency. In order to apply the concept of TRT
to LMST in the next section, we will also briefly summarize
TRT.
Construction of LTRT
LTRT can be easily constructed by applying the topology
construction phase of LMST two times. The procedure
of constructing LTRT is composed of four phases: information
exchange, first topology construction, link deletion,
and second topology construction.
1) Information Exchange: Each node broadcasts a
“Hello” message which contains its ID and position, and
obtains the information of its one-hop nodes.Each node obtains
its local graph Gu(Nu,Eu) in this phase.
2) First Topology Construction: Each node u applies
Prim’s algorithm independently to obtain its local MST
(Nu,E1u) is an undirected graph constructed
by eliminating unidirectional edges. This elimination
of unidirectional edges does not destruct the connectivity
of the network.
Performance evaluation
Other localized algorithms have been proposed to construct
a 2-connected topology, but most of them have 2-
vertex connectivity which has stronger connectivity than 2-
edge connectivity. If a node is dropped, the topology has
to be recalculated, thus incurring large computational complexity.
Therefore, it is sufficient to employ 2-edge connectivity,
a weaker one, which leads to a low cost topology.
Complexity analysis
We show the time complexity of LTRT construction is
O(n logm), where n is the number of nodes which are onehop
away and m is the number of links in the local network
Gu(N,E). It is the same as LMST.
In the information exchange phase, each node broadcasts
and obtains the information. In this phase, adding the neighbors
in the local graph costs O(n). Each node calculates the
length from the node positions to obtain link lengths in its
local graph, thus costing O(n2).