A Deterministic Protocol for Permutation Routing in Dense Multi-Hop Sensor Networks

Alain Bertrand Bomgni, Jean Frédéric Myoupo

.

DOI: 10.4236/wsn.2010.24040                

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.

Keywords

Permutation Routing Problem, Wireless Sensor Networks, Hierarchical Clustering, Clique

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	D. Estrin, R. Govindan, J. Heidemann and S. Kumar, “Next Century Challenges: Scalable Coordination in Sensor Networks,” Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, Seattle, 1999, pp. 263-270.
[2]	G. J. Pottie and W. J. Kaiser, “Wireless Integrated Network Sensors,” Communications of the ACM, Vol. 43, No.5 2000, pp. 51-58.
[3]	F. Zhao, J. Liu, J. Liu, L. Guibas and J. Reich, “Collaborative Signal and Information Processing: An Information Directed Approach,” Proceedings of the IEEE, New York, Vol. 91, No. 8, 2003, pp. 1199-1209.
[4]	K. Nakano, S. Olariu and J. L. Schwing, “Broadcast- Efficient Protocols for Mobile Radio Networks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 10, No. 12, 1999, pp. 1276-1289.
[5]	F. Myoupo, “Concurrent Broadcasts-Based Per¬mutation Routing Algorithms in Radio Networks,” IEEE Symposium on Computers and Communica¬tions, 2003, pp. 1272-1278.
[6]	A. Datta, “Fault-Tolerant and Energy-efficient Permu¬tation Routing Protocol for Wireless Networks,” Proceedings of the 17th International Symposium on Parallel and Distributed Processing, Nice, 2003, pp. 22-26.
[7]	D. Karimou and J. F. Myoupo, “A Fault Tolerant Permutation Routing Algorithm in Mobile Ad Hoc Networks,” International Conference on Networks-Part II, 2005, pp. 107-115.
[8]	K. Nakano, S. Olariu and A. Y. Zomaya, “Energy-Efficient Permutation Routing in Radio Networks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 12, No. 6, 2001, pp. 544-557.
[9]	A. Datta and A. Y. Zomaya, “An Energy-Efficient Permutation Routing Protocol for Single-Hop Radio Networks”. IEEE Transactions on Parallel and Distributed Systems, Vol. 15, No. 4, 2004, pp. 331-338.
[10]	I. S. Walls and J. Žerovnik, “Optimal Permutation Routing on Mesh Networks,” International Network Optimization Conference, Belgium, 22-25 April 2008.
[11]	D. Karimou and J. F. Myoupo, “An Application of an Initialization Protocol to Permutation Routing in a Single-hop Mobile Ad-Hoc Networks,” Journal of Supercomputing, Vol. 31, No. 3, 2005, pp. 215-226.
[12]	D. Karimou and J. F. Myoupo, “Randomized Permutation Routing in Multi-hop Ad Hoc Networks with Unknown destinations,” IFIP International Federation of Information Processing, Vol. 212, 2006, pp. 47-59.
[13]	S. Basagni, “Distributed Clustering for Multi Hop Wire¬less Networks,” Proceedings of the IEEE International Symposium on Wireless Communications, Vic¬toria, 3-4 June 1999, pp. 41-42.
[14]	R. Wattenhofer, S. Khuller, et al., “A Clustering Scheme for Hierarchical Control in Multi-Hop Wireless Networks,” Proceedings of the 20th IEEE International Conference on Computer Communications, Vol. 3, 2001, pp. 1028- 1037.
[15]	C. L. Fullmer and J. J. Garcia-Luna-Aceves, “Solutions to Hidden Terminal Problems in Wireless Networks,” Sigcomm, September 1997.
[16]	A. B. McDonald and A. Zanati, “A Mobility-Based Framework for Adaptive Clustering in Wireless Ad Hoc Networks,” IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, 1999, pp. 1466-1487.
[17]	K. Sun, P. Peng and P. Ning, “Secure Distributed Cluster Formation in Wireless Sensor Networks,” 22nd Annual Computer Security Applications Conference, Las Vegas, 2006, pp. 131-140.
[18]	P. Tosic and G. Agha, “Maximal Clique Based Distributed Coalition Formation for Task Allocation in Large- Scale Multi-Agent Systems,” Lecture Notes in Computer Science, Vol. 3446, 2005, pp. 104-120.