TITLE:
A Deterministic Protocol for Permutation Routing in Dense Multi-Hop Sensor Networks
AUTHORS:
Alain Bertrand Bomgni, Jean Frédéric Myoupo
KEYWORDS:
Permutation Routing Problem, Wireless Sensor Networks, Hierarchical Clustering, Clique
JOURNAL NAME:
Wireless Sensor Network,
Vol.2 No.4,
April
23,
2010
ABSTRACT: A large variety of permutation routing protocols in a single-hop Network are known in the literature. Since they are single hop, there is always a wireless link connecting two nodes. One way to solve this problem in a multiple hop environment is to partition nodes into clusters, where a node in each cluster called clusterhead is responsible for the routing service. In this paper, we propose a hybrid clustering mech¬anism to perform permutation routing in multi-hop ad hoc Networks. We first propose to partition the network in single-hop clusters also named cliques. Secondly, we run a local permutation routing to broad¬cast items to their local destinations in each clique. Next we partition the clusterheads of cliques with the hierarchical clustering technique. We show how the outgoing items can be routed to their destination cliques. We give an estimation of the number of broadcast rounds in the worse case. More precisely, we show that solving the permutation routing problem on a multi-hop sensor network need in the worse case. Where n is the number of the data items stored in the network, p is the number of sensors, |HUBmax| is the number of sensors in the clique of maximum size and k is the number of cliques after the first clustering. Finally, simulation results show that our algorithm performs better than the naïve multiple gossiping. To the best of our knowledge, it is the first algorithm for permutation routing in multi-hop radio networks.