CFP last date
15 November 2024
Call for Paper
December Edition
IJAIS solicits high quality original research papers for the upcoming December edition of the journal. The last date of research paper submission is 15 November 2024

Submit your paper
Know more
The week's pick
Responsive image
Ordered Frequent Itemsets Matrix Based On Fp-Tree Structure And Apriori Algorithm

Abdulkader M. Al-Badani Abdualmajed A. Al-Khulaidi
Random Articles
Reseach Article

Minimum Connected Dominating Set based Virtual Backbone Construction in OLSR Protocol

by P. S. Vinayagam
journal cover thumbnail

International Journal of Applied Information Systems
Foundation of Computer Science (FCS), NY, USA
Volume 12 - Number 6
Year of Publication: 2017
Authors: P. S. Vinayagam
10.5120/ijais2017451707

P. S. Vinayagam . Minimum Connected Dominating Set based Virtual Backbone Construction in OLSR Protocol. International Journal of Applied Information Systems. 12, 6 ( September 2017), 1-9. DOI=10.5120/ijais2017451707

@article{ 10.5120/ijais2017451707,
author = { P. S. Vinayagam },
title = { Minimum Connected Dominating Set based Virtual Backbone Construction in OLSR Protocol },
journal = { International Journal of Applied Information Systems },
issue_date = { September 2017 },
volume = { 12 },
number = { 6 },
month = { September },
year = { 2017 },
issn = { 2249-0868 },
pages = { 1-9 },
numpages = {9},
url = { https://www.ijais.org/archives/volume12/number6/999-2017451707/ },
doi = { 10.5120/ijais2017451707 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2023-07-05T19:08:15.696944+05:30
%A P. S. Vinayagam
%T Minimum Connected Dominating Set based Virtual Backbone Construction in OLSR Protocol
%J International Journal of Applied Information Systems
%@ 2249-0868
%V 12
%N 6
%P 1-9
%D 2017
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In ad hoc wireless networks, nodes have limited energy and short transmission range. There are no pre-designated routers in these networks and hence routing cannot be done in the conventional way as done in wired networks. To facilitate routing in ad hoc wireless networks, some sort of backbone like structure needs to be built. One of the widely used routing protocols in ad hoc wireless networks is Optimized Link State Routing Protocol (OLSR), which makes use of Multipoint Relay sets (MPRs) to construct the virtual backbone. Various improvements have been proposed in the literature for the MPR selection scheme used in OLSR to improve its efficiency. In this paper, with the aim of enhancing the performance of OLSR, we propose an Improved OLSR (IOLSR) protocol, wherein Minimum Connected Dominating Set (MCDS) is used, instead of multipoint relay sets, to construct the virtual backbone. The performance of IOLSR is compared with that of OLSR in terms of the performance metrics – throughput, packet delivery ratio, end-to-end delay and size of the backbone. From the results, it is found that IOLSR protocol performs better than OLSR with respect to all these metrics.

References
  1. Funke, S., Kesselman, A., Meyer, U., Segal, M. (2005). A simple improved distributed algorithm for minimum CDS in unit disk graphs. IEEE International Conference on Wireless and Mobile Computing, Networking and Communications, (WiMob'2005), vol. 2, pp. 220 – 223.
  2. Kim, D., Wu, Y., Li, Y., Zou, F., and Du, D. (2009). Constructing minimum connected dominating sets with bounded diameters in wireless networks. IEEE Transactions on Parallel and Distributed Systems, vol. 20, no. 2, pp. 147-157.
  3. Kassaei, H., Mehrandish, M., Narayanan, L., Opatrny, J. (2009). A new local algorithm for backbone formation in ad hoc networks, Proceeding. PE-WASUN'09 Proceedings of the 6th ACM symposium on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, Tenerife, Canary Islands, Spain, pp. 49-57.
  4. Sakai, K., Huang, S. C. H., Ku, W., Sun, M., Cheng, X. (2011). Timer-based CDS construction in wireless ad hoc networks. IEEE Transactions on Mobile Computing, vol. 10, no. 10, pp. 1388-1402.
  5. Ge, Y., Kunz, T., Lamont, L. (2003). Quality of service routing in ad-hoc networks using OLSR. Proceedings of the 36th Annual Hawaii International Conference on System Sciences (HICSS’03).
  6. Badis, H., Munaretto, A., Agha, K. A., Pujolle, G. (2004). Optimal path selection in a link state QoS routing protocol. IEEE 59th Vehicular Technology Conference, VTC, vol. 5, pp. 2570 – 2574.
  7. Li, Z., Yu, N., Deng, Z. (2008). NFA: A new algorithm to select MPRs in OLSR. 4th International Conference on Wireless Communications, Networking and Mobile Computing, WiCOM '08, Dalian, pp. 1 – 6.
  8. Rango, F. D., Fotino, M., Marano, S. (2008). EE-OLSR: energy efficient OLSR routing protocol for mobile ad-hoc networks. IEEE Military Communications Conference, MILCOM 2008, San Diego, CA, pp. 1 – 7.
  9. Koga, T., Tagashira, S., Kitasuka, T., Nakanishi, T., Fukuda, A. (2009). Highly efficient multipoint relay selections in link state QoS routing protocol for multi-hop wireless networks. IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks & Workshops, WoWMoM 2009, Kos, pp. 1-9.
  10. Yamada, K., Itokawa, T., Kitasuka, T., Aritsugi, M. (2010). Cooperative MPR selection to reduce topology control packets in OLSR. TENCON 2010 - 2010 IEEE Region 10 Conference, Fukuoka, pp. 293 – 298.
  11. Kitasuka, T., Tagashira, S. (2011). Density of multipoint relays in dense wireless multi-hop networks. Second International Conference on Networking and Computing, (ICNC), Osaka, pp. 134 – 140.
  12. Boushaba, A., Benabbou, A., Benabbou, R., Zahi, A., Oumsis, M. (2012). Optimization on OLSR protocol for reducing topology control packets. 2012 International Conference on Multimedia Computing and Systems (ICMCS), Tangier, pp. 539 – 544.
  13. Kitasuka, T., Tagashira, S. (2013). Finding more efficient multipoint relay set to reduce topology control traffic of OLSR. 2013 IEEE 14th International Symposium and Workshops on a World of Wireless, Mobile and Multimedia Networks (WoWMoM), Madrid, pp. 1-9.
  14. Kots, A., Kumar, M. (2014). The fuzzy based QMPR selection for OLSR routing protocol. Wireless Networks, vol. 20, no. 1, pp. 1-10.
  15. Mans, B., Shrestha, N. (2004). Performance evaluation of approximation algorithms for multipoint relay selection. Proceedings of the 3rd Annual Mediterranean Ad Hoc Networking Workshop, pp. 480-491.
  16. Belkheir, M., Qacem, Z., Bouziani, M., Ghelamellah, A. (2012). An energy optimization algorithm for mobile ad hoc network. International Journal of Soft Computing and Software Engineering (JSCSE), vol.2, no.10, pp. 20-26.
  17. Malik, R. F., Rahman, T. A., Ngah, R., Hashim, S. Z. M. (2012). The new multipoint relays selection in OLSR using particle swarm optimization. TELKOMNIKA, vol.10, no.2, pp. 343-352.
  18. Maccari, L., Cigno, R. L. (2012). How to reduce and stabilize MPR sets in OLSR networks. 2012 IEEE 8th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), Barcelona, pp. 373 – 380.
  19. Dashbyamba, N., Wu, C., Ohzahata, S., Kato, T. (2013). An improvement of OLSR using fuzzy logic based MPR selection. 15th Asia-Pacific Network Operations and Management Symposium (APNOMS), Hiroshima, Japan, pp. 1 – 6.
  20. Ephremides, A., Wieselthier, J. E., Baker, D. J. (1987). A design concept for reliable mobile radio networks with frequency hopping signaling. Proceedings of the IEEE, vol. 75, no. 1, pp. 56-73.
  21. Guha, S., Khuller, S. (1998). Approximation algorithms for connected dominating sets. Algorithmica, vol. 20, no. 4, pp. 374–387.
  22. Das, B., Bharghavan, V. (1997). Routing in ad-hoc networks using minimum connected dominating sets. IEEE International Conference on Communications, ICC '97 Montreal, Towards the Knowledge Millennium, vol. 1, Montreal, Que, pp. 376 – 380.
  23. Wu, J., Li, H. (2001). A dominating-set-based routing scheme in ad hoc wireless networks. Telecommunication Systems, vol. 18, no. 1–3, pp. 13–36.
  24. Alzoubi, K. M., Wan, P., Frieder, O. (2002). Distributed heuristics for connected dominating sets in wireless ad hoc networks. Journal of Communications and Networks, vol.4, no.1, pp. 22-29.
  25. Wu, J., Dai, F., Gao, M., Stojmenovic, I. (2002). On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks. Journal of Communications and Networks, vol.4, no.1, pp. 59-70.
  26. Alzoubi, K. M., Wan, P., Frieder, O. (2002). Message-optimal connected dominating sets in mobile ad hoc networks. Proceeding MobiHoc'02 Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, EPFL Lausanne, Switzerland, pp. 157 – 164.
  27. Li, Y., Zhu, S., Thai, M., Du, D. (2004). Localized construction of connected dominating set in wireless networks. In Proceedings of US National Science Foundation Proc. NSF International workshop on Theoretical Aspects of Wireless Ad Hoc, Sensor and Peer-to-Peer Networks (TAWN’04), Chicago, USA.
  28. Dai, F., Wu, J. (2004). An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 10, pp. 908-920.
  29. Mohammed, K., Gewali, L., Muthukumar, V. (2005). Generating quality dominating sets for sensor network. Proceedings of the Sixth International Conference on Computational Intelligence and Multimedia Applications (ICCIMA’05), pp. 204 – 211.
  30. Kamei, S., Kakugawa, H. (2007). A self-stabilizing distributed approximation algorithm for the minimum connected dominating set. IEEE International Parallel and Distributed Processing Symposium, IPDPS 2007, Rome, pp. 1 – 8.
  31. Sheu, P., Tsai, H., Lee, Y., Cheng, J. (2009). On calculating stable connected dominating sets based on link stability for mobile ad hoc networks. Tamkang Journal of Science and Engineering, vol. 12, no. 4, pp. 417-428.
  32. Yin, B., Shi, H., Shang, Y. (2011). An efficient algorithm for constructing a connected dominating set in mobile ad hoc networks. Journal of Parallel and Distributed Computing, vol. 71, no. 1, pp. 27–39.
  33. Chakradhar, P., Yogesh, P. (2013). Energy efficient minimum connected dominating set algorithm for MANETs. IEEE International Conference on Recent Trends in Information Technology (ICRTIT), Chennai, pp. 270 – 276.
  34. Ting-jun, S., Xu, S., Xu-ming, F. (2014). A Virtual Backbone Construction Algorithm Based on Connected Dominating Set in Wireless Sensor Networks. International Conference on Computer, Communications and Information Technology (CCIT 2014), Beijing, pp. 156-159.
  35. Fu, D., Han, L., Liu, L., Gao, Q., Feng, Z. (2015). An Efficient Centralized Algorithm for Connected Dominating Set on Wireless Networks. Procedia Computer Science, vol. 56, pp. 162 – 167.
  36. Das, B., Sivakumar, R., Bharghavan, V. (1997). Routing in ad hoc networks using a spine. Proceedings. Sixth International Conference on Computer Communications and Networks, Las Vegas, pp. 34 – 39.
  37. Sivakumar, R., Das, B., Bharghavan, V. (1998). The clade vertebrata: spines and routing in ad hoc networks. Proceedings. Third IEEE Symposium on Computers and Communications, ISCC '98, Athens, pp. 599 – 605.
  38. Stojmenovic, I., Seddigh, M., Zunic, J. (2002). Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks. IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 1, pp. 14-25.
  39. Wan, P., Alzoubi, K. M., Frieder, O. (2004). Distributed construction of connected dominating set in wireless ad hoc networks. Mobile Networks and Applications, vol. 9, no. 2, pp. 141–149.
  40. Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., Ko, K. (2004). A greedy approximation for minimum connected dominating sets. Theoretical Computer Science, vol. 329, no. 1-3, pp. 325 – 330.
  41. Kim, B., Yang, J., Zhou, D., Sun, M. (2005). Energy-aware connected dominating set construction in mobile ad hoc networks. Proceedings of 14th International Conference on Computer Communications and Networks, ICCCN 2005, pp. 229 – 234.
  42. Zongkai, Y., Dasheng, Z., Yuming, W., Jianhua, H. (2005). An efficient distributed algorithm for connected dominating set construction in wireless sensor networks. Journal of Electronics (China), vol. 22, no. 6, pp. 671-675.
  43. Cheng, X., Ding, M., Du, D. H., Jia, X. (2006). Virtual backbone construction in multihop ad hoc wireless networks. Wireless Communications and Mobile Computing, vol. 6, no. 2, pp. 183–190.
  44. Han, B., Zhang, L., Jia, W. (2010). Connected dominating set for topology control in ad hoc networks, in Mobile Intelligence. New Jersey: Wiley, ch. 2, pp. 26-42.
  45. Gao, B., Ma, H., Yang, Y. (2005). A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks, in Parallel and Distributed Processing and Applications. Berlin Heidelberg: Springer, pp. 352–356.
  46. Cardei, M., Cheng, X., Cheng, X., Du, D. (2002). Connected domination in multihop ad hoc wireless networks. Proceedings of the 6th Joint Conference on Information Science (JCIS), North Carolina, pp. 251-255.
  47. Clausen, T., Jacquet, P. (2003). Optimized Link State Routing Protocol (OLSR), Request for Comments: 3626. Available: https://www.ietf.org/rfc/rfc3626.txt.
  48. NS3, http://www.nsnam.org.
Index Terms

Computer Science
Information Sciences

Keywords

OLSR IOLSR MCDS MPR ad hoc network wireless network

Powered by PhDFocusTM