Journal of Communications, Vol 7, No 3 (2012), 246-257, Mar 2012
doi:10.4304/jcm.7.3.246-257

Generalized Multi-Constrained Path (G_MCP) QoS Routing Algorithm for Mobile Ad hoc Networks

Kunagorn Kunavut, Teerapat Sanguankotchakorn

Abstract


In mobile ad hoc network, efficient routing protocol is required to perform route discovery and maintenance. These protocols can be classified into two main types which are proactive and reactive routing protocols. Most of them usually use the suboptimal path to reach destination without considering QoS parameters. This results in network congestion during high traffic load situation. Hence, many algorithms have been proposed to offer QoS routing to these protocols. However, most of them find the feasible path by using only one or two QoS metrics. This is not enough to support many applications with QoS guaranteed, especially multimedia applications since they have more stringent various QoS requirements. To provide QoS routing in ad hoc network based on such environment, we propose the effective algorithm called Generalized MCP (G_MCP) to find the feasible path based on proposed weighted Connectivity Index (combination of link connectivity and capacity) and non-linear cost (combination of multiple additive QoS metrics using non-linear function). We adopt the fall-back approach. That is, G_MCP will find the path from source to destination by considering weighted Connectivity Index first. If there is a tie, the path with least non-linear cost will be chosen. Based on this approach, G_MCP has the comparable time complexity with the Shortest-Widest Path algorithm. We construct the simulation in a number of scenarios based on proactive protocol called OLSR. According to the simulation results, it is obvious that G_MCP performances are superior than OLSR and Shortest-Widest Path algorithms in terms of throughput, packet delivery ratio, delay and success ratio. Therefore, it can be concluded that G_MCP is able to support various applications and be operated well in highly dynamic mobility environment


Keywords


Connectivity Index; non-linear cost; multi-constrained path; QoS routing; mobile ad hoc network

References


 

[1] C.E. Perkins and P. Bhagwat, Highly Dynamic Destination Sequenced Distance Vector Routing (DSDV) for Mobile Computers, Proceedings of ACM SIGCOMM, pp. 234-244, August 1994.

[2] R. Ogier, F. Templin and M. Lewis, Topology Dissemination Based on Reverse-Path Forwarding (TBRPF), RFC 3684, February 2004.

[3] T. Clausen and P. Jacquet, Optimized Link State Routing Protocol (OLSR), RFC 3626, October 2003.

[4] C. E. Perkins, E. Belding-Royer and S. Das, Ad hoc On-Demand Distance Vector (AODV) Routing, RFC 3561, July 2003.

[5] D. Johnson, Y. Hu and D. Maltz, The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4, RFC 4728, February 2007.

[6] C. Mbarushimana and A. Shahrabi, Comparative Study of Reactive and Proactive Routing Protocols Performance in Mobile Ad Hoc Networks, Proceedings of 21st International Conference on Advanced Information Networking and Applications Workshop (AINAW), pp. 679-684, May 2007.
http://dx.doi.org/10.1109/AINAW.2007.123

[7] A. Qayyum, L. Viennot and A. Laouiti, Multipoint Relaying: An Efficient Technique for Flooding in Mobile Wireless Networks, INRIA Research Report RR-3898, 2000.

[8] A. S. Tanenbaum, Computer Networks, Fourth edition, New Jersey, Prentice Hall, 2003.

[9] S. Chen and K. Nahrstedt, Distributed Quality-of-Service Routing in Ad hoc Networks, IEEE Journal on Selected Areas in Communications, vol. 17, no. 8, pp. 1488-1505, August 1999.
http://dx.doi.org/10.1109/49.780354

[10] H. Xiao, W. K.G. Seah, A. Lo and K. C. Chua, A Flexible Quality of Service Model for Mobile Ad hoc Networks, Proceedings of IEEE Vehicular Technology Conference, Vol. 1, pp. 445-449, September 2000.

[11] Y. Hwang and P. Varshney, An Adaptive QoS Routing Protocol with Dispersity for Ad Hoc Networks, Proceedings of 36th Hawaii International Conference on System Sciences (HICSS), January 2003.
http://dx.doi.org/10.1109/HICSS.2003.1174851

[12] Y. Hwang and P. Varshney, An Adaptive Routing Protocol for Ad-hoc Networks using Multiple Disjoint Path, Proceedings of IEEE Vehicular Technology Conference, vol. 3, pp. 2249-2253, May 2001.

[13] Q. Xue, and A. Ganz, Ad Hoc On-demand Routing (AQOR) in Mobile Ad Hoc Networks, Journal of Parallel and Distributed Computing, vol. 63, no. 2, pp. 154-165, 2003.
http://dx.doi.org/10.1016/S0743-7315(02)00061-8

[14] S. Medidi and K. Vik, Quality of Service-aware Source-Initiated Ad Hoc Routing, Proceeding of IEEE Sensor and Ad Hoc Communications and Networks (SECON), pp. 108-117, October 2004.

[15] L. Chen and W. Heinzelman, QoS-aware Routing Based on Bandwidth Estimation for Mobile Ad Hoc Networks, IEEE Journal on Selected Areas in Communications, vol. 23, no. 3, pp. 561-572, March 2005.
http://dx.doi.org/10.1109/JSAC.2004.842560

[16] P. Sinha, R. Sivakumar and V. Bharghavan, CEDAR: A Core-Extraction Distributed Ad hoc Routing Algorithm, Proceedings of IEEE INFOCOM, March 1999.

[17] Y. Ge, T. Kunz and L. Lamont, Quality of Service Routing in Ad Hoc Networks Using OLSR, Proceedings of the 36th Hawaii International Conference on System Sciences (HICSS'03), January 2003.

[18] H. Badis, A. Mauaretto, K. A. Agha and G. Pujolle, QoS for Ad Hoc Networking Based on Multiple Metrics: Bandwidth and Delay, Proceedings of the 5th IEEE International Conference on Mobile and Wireless Communications Networks, pp. 15-18, October 2003.

[19] H. Badis and K. A. Agha, QOLSR Multi-path Routing for Mobile Ad Hoc Networks Based on Multiple Metrics: Bandwidth and Delay, Proceedings of IEEE Vehicular Technology Conference, vol. 4, pp. 2181-2184, May 2004.

[20] H. Badis, A. Mauaretto, K. A. Agha and G. Pujolle, Optimal Path Selection in a Link State QoS Routing Protocol, Proceedings of IEEE Vehicular Technology Conference, vol. 4, pp. 2570-2574, May 2004.

[21] D. Nguyen and P. Minet, QoS Support and OLSR Routing in a Mobile Ad hoc Network, Proceedings of the International Conference on Networking, International Conference on Systems and International Conference on Mobile Communications and Learning Technologies, April 2006.

[22] K. Kunavut and T. Sanguankotchakorn, QoS-aware Routing for Mobile Ad hoc Networks Based on Multiple Metrics: Connectivity Index (CI) and Delay, Proceedings of IEEE Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON 2010), pp. 46-50, May 2010.

[23] K. Kunavut and T. Sanguankotchakorn, Multi-Constrained Path (MCP) QoS Routing in OLSR based on Multiple Additive QoS Metrics, Proceedings of IEEE Symposium on Communications and Information Technologies 2010 (ISCIT 2010), pp. 226-231, October 2010.

[24] M. Randic, On Characterization of Molecular Branching, Journal of The American Chemical Society, vol. 97, no. 23, pp. 6609-6615, November 1975.
http://dx.doi.org/10.1021/ja00856a001

[25] I. Gutman, O. Araujo and D.A. Morales, Estimating the connectivity index of a saturated hydrocarbon, Indian Journal of Chemistry, vol. 39, pp. 381-385, 2000.

[26] I. Gutman, O. Miljkovic, G. Caporossi and P. Hansen, Alkanes with small and large Randic connectivity indices, Chemical Physics Letters, vol. 306, no. 5, pp. 366-372, June 1999.
http://dx.doi.org/10.1016/S0009-2614(99)00472-8

[27] G. Caporossi, I. Gutman, P. Hansen and L. Pavlovic, Graphs with maximum connectivity index, Computational Biology and Chemistry, vol. 27, pp. 85-90, 2003.
http://dx.doi.org/10.1016/S0097-8485(02)00016-5

[28] M. A. Rajan, M. G. Chandra, L. C. Reddy and P. Hiremath, A Study of Connectivity Index of Graph Relevant to Ad Hoc Networks, International Journal of Computer Science and Network Security, vol. 7, no. 11, pp. 198-203, November 2007.

[29] L. Shi, A. Fapojuwo, N. Viberg, W. Hoople and N. Chan, Methods for Calculating Bandwidth, Delay, and Packet Loss Metrics in Multi-hop IEEE 802.11 Ad Hoc Networks, Proceedings of IEEE Vehicular Technology Conference, pp. 103-107, May 2008.

[30] H. D. Neve and P. V. Mieghem, A Multiple Quality of Service Routing Algorithm for PNNI, Proceedings of IEEE ATM Workshop, pp. 324-328, May 1998.

[31] T. Korkmaz and M. Krunz, Multi-constrained Optimal Path Selection, Proceedings of the IEEE INFOCOM, vol. 2, pp. 834-843, April 2001.

[32] J. M. Jaffe, Algorithms for finding paths with multiple constraints, Networks, vol. 14, pp. 95-116, 1984.
http://dx.doi.org/10.1002/net.3230140109

[33] Z. Wang and J. Crowcroft, Quality of Service Routing for Supporting Multimedia Applications, IEEE Journal on Selected Areas in Communications, vol. 14, no. 7, pp. 1228-1234, September 1996.
http://dx.doi.org/10.1109/49.536364

[34] K. Kunavut and T. Sanguankotchakorn, Optimized Path Selection Process in OLSR Based on Weighted Connectivity Index and Delay, Proceedings of IEEE Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON 2011), pp. 348-351, May 2011.

[35] Network Simulator 2, http://www.isi.edu/nsnam/ns

[36] Chen, T. Farley and N. Ye, QoS Requirements of Network Applications on the Internet, International Journal on Information-Knowledge-Systems Management, vol. 4, pp. 55-76, January 2004.

[37] B. Melamed, TES: A Class of Methods for Generating Autocorrelated Uniform Variates, ORSA Journal on Computing, vol.3, pp. 317-329, 1991.
http://dx.doi.org/10.1287/ijoc.3.4.317

[38] B. Melamed, D. Raychaudhuri, B. Sengupta and J. Zdepski, TES-Based Modeling for Performance Evaluation of Integrated Networks, Proceedings of IEEE INFOCOM, 1992.

[39] Video Traffic Generator, http://www.sce.carleton.ca/~amatrawy/mpeg4


Full Text: PDF


Journal of Communications (JCM, ISSN 1796-2021)

Copyright @ 2006-2013 by ACADEMY PUBLISHER – All rights reserved.