International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 9, No. 12, 8 Dec. 2017
Cover page and Table of Contents: PDF (size: 690KB)
A Fault-tolerant Improved OLSR Protocol using k-Connected m-Dominating Set
Full Text (PDF, 690KB), PP.55-63
Views: 0 Downloads: 0
Author(s)
Vinayagam P. S.
1,*
Index Terms
kmCDS, MPR, OLSR, Virtual backbone, Fault-tolerant, FT-IOLSR
Abstract
The inherent properties of ad hoc networks such as limited energy, short transmission range and absence of routers along with node mobility, node failures and link failures make routing a challenging task. In order to facilitate routing, virtual backbone has been proposed as a viable solution in the literature. Optimize Link State Routing (OLSR) protocol, a proactive routing protocol, uses Multipoint Relay (MPR) set to construct virtual backbone. Prior research has, however, identified various issues with the MPR selection scheme that needs improvement. One of the alternatives that could be used to construct virtual backbone is Connected Dominating Set (CDS). Although CDS generates a smaller virtual backbone, its 1-connected 1-domination nature may render a virtual backbone obsolete in case of networks which witness frequent node mobility, node failures and link failures. To overcome this, k-Connected m-Dominating CDS (kmCDS) could be used to construct fault- tolerant virtual backbone structure. In this direction, the present paper proposes a Fault-Tolerant Improved Optimized Link State Routing (FT-IOLSR) protocol that uses kmCDS to form fault-tolerant virtual backbone, effectively replacing the MPR set of OLSR protocol. Simulations are carried out to assess the performance of the FT-IOLSR protocol in relation to the OLSR protocol, with respect to various node speed and pause time combinations, and varying network size. The results show that the FT-IOLSR protocol is better in terms of packet delivery ratio under varying mobility and varying network size. Also it has been observed that, with increase in k-connectivity and m-domination factor, there is improvement in the performance of the protocol.
Cite This Paper
Vinayagam P. S., "A Fault-tolerant Improved OLSR Protocol using k-Connected m-Dominating Set", International Journal of Computer Network and Information Security(IJCNIS), Vol.9, No.12, pp.55-63, 2017. DOI:10.5815/ijcnis.2017.12.07
Reference
[1]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, 75(1), 56-73.
[2]Kim, D., Gao, X., Zou, F., & Wu, W. (2011). Construction of fault-tolerant virtual backbones in wireless networks. In Y. Xiao, F. H. Li & H. Chen (Eds.), Handbook of Security and Networks (pp. 465-486). Singapore: World Scientific.
[3]Zhang, N., Shin, I., Zou, F., Wu, W., & Thai, M. T. (2008). Trade-off scheme for fault tolerant connected dominating sets on size and diameter. Proceedings of the 1st ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing (FOWANC’08). Hong Kong SAR, China (pp. 1-8).
[4]Clausen, T. H., & Jacquet. P. (2003, October). Optimized link state routing protocol (OLSR), Request for Comments: 3626. Retrieved from https://www.ietf.org/rfc/rfc3626.txt.
[5]Wu, J. (2002). Dominating-set-based routing in ad hoc wireless networks. In I. Stojmenovic′ (Ed.), Handbook of Wireless Networks and Mobile Computing (pp. 425-450). New York: Wiley.
[6]Li, Y., Wu, Y., Ai, C., & Beyah, R. (2012). On the construction of k-connected m-dominating sets in wireless networks. Journal of Combinatorial Optimization, 23(1), 118-139.
[7]Kim, D., Wu, Y., Li, Y., Zou, F., & Du, D. (2009). Constructing minimum connected dominating sets with bounded diameters in wireless networks. IEEE Transactions on Parallel and Distributed Systems, 20(2), 147-157.
[8]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, 12(4), 417-428.
[9]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).
[10]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).
[11]Gao, B., Ma, H., & Yang, Y. (2005). A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks. In J. Cao, L. T. Yang, M. Guo, & F. Lau (Eds.), Parallel and Distributed Processing and Applications (pp. 352–356). Berlin Heidelberg: Springer.
[12]Li, Y., Zhu, S., Thai, M., & Du, D. (2004). Localized construction of connected dominating set in wireless networks. Proceedings of US National Science Foundation International workshop on Theoretical Aspects of Wireless Ad Hoc, Sensor and Peer-to-Peer Networks (TAWN’04). Chicago, USA.
[13]Dai, F., & Wu, J. (2006). On constructing k-connected k-dominating set in wireless ad hoc and sensor networks. Journal of Parallel and Distributed Computing, 66(7), 947-958.
[14]Kuhn, F., Moscibroda, T., & Wattenhofer, R. (2006). Fault-tolerant clustering in ad hoc and sensor networks. Proceedings of the 26th IEEE International Conference on Distributed Computing Systems (ICDCS '06). Lisbon, Portugal.
[15]Shang, W., Wan, P., Yao, F., & Hu, X. (2007). Algorithms for minimum m-connected k-tuple dominating set problem. Theoretical Computer Science, 381(1–3), 241-247.
[16]Thai, M. T., Zhang, N., Tiwari, R., & Xu, X. (2007). On approximation algorithms of k-connected m-dominating sets in disk graphs. Theoretical Computer Science, 385(1–3), 49-59.
[17]Wu, Y., Wang, F., Thai, M. T., & Li, Y. (2007). Constructing k-connected m-dominating sets in wireless sensor networks. Military Communications Conference (MILCOM 2007). Orlando, FL, USA (pp. 1-7).
[18]Couture, M., Barbeau, M., Bose, P., & Kranakis, E. (2008). Incremental construction of k-dominating sets in
wireless sensor networks. Ad Hoc & Sensor Wireless Networks, 5(1-2), 47-67.
[19]Wu, Y., & Li, Y. (2008). Construction algorithms for k-Connected m-Dominating sets in wireless sensor networks. Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '08). Hong Kong SAR, China (pp. 83-90).
[20]Wang, F., Thai, M. T., & Du, D. (2009). On the construction of 2-connected virtual backbone in wireless networks. IEEE Transactions on Wireless Communications, 8(3), 1230-1237.
[21]Bian, Y., Yu, H., & Zeng, P. (2009). Construction of a fault tolerance connected dominating set in wireless sensor network. International Conference on Measuring Technology and Mechatronics Automation (ICMTMA '09). Zhangjiajie, Hunan (pp. 610-614).
[22]Schleich, J., Bouvry, P., & An, L. T. H. (2009). Decentralized fault-tolerant connected dominating set algorithm for mobile ad hoc networks. Proceedings of the 2009 International Conference on Wireless Networks (ICWN 2009). Las Vegas Nevada, USA (pp. 354-360).
[23]Schleich, J., Danoy, G., Bouvry, P., & An, L. T. H. (2009). Blackbone2, an efficient deterministic algorithm for creating 2-connected m-dominating set-based backbones in ad hoc networks. Proceedings of the Seventh ACM International Workshop on Mobility Management & Wireless Access, (MobiWac’09). Tenerife, Canary Islands, Spain (pp. 91-98).
[24]Wang, W., Kim, D., An, M. K., Gao, W., Li, X., Zhang, Z., & Wu, W. (2013). On construction of quality fault-tolerant virtual backbone in wireless networks. IEEE/ACM Transactions on Networking, 21(5), 1499-1510.
[25]Foerster, K. (2013). Approximating fault-tolerant domination in general graphs. Proceedings of the Tenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO). SIAM (pp. 25–32).
[26]Zhou, J., Zhang, Z., Wu, W., & Xing, K. (2014). A greedy algorithm for the fault-tolerant connected dominating set in a general graph. Journal of Combinatorial Optimization, 28(1), 310-319.
[27]Ahn, N., & Park, S. (2015). An optimization algorithm for the minimum k-connected m-dominating set problem in wireless sensor networks. Wireless Networks, 21(3), 783-792.
[28]Wang, W., Liu, B., Kim, D., Li, D., Wang, J., & Jiang, Y. (2015). A better constant approximation for minimum 3-connected m-dominating set problem in unit disk graph using Tutte decomposition. Proceedings of the 34th IEEE International Conference on Computer Communications (INFOCOM 2015). Hong Kong (pp. 1796-1804).
[29]Wu, Y., & Li, Y. (2009). Connected Dominating Sets. In H. Liu, X. Chu, & Y. Leung (Eds.), Ad Hoc and Sensor Wireless Networks: Architectures, Algorithms and Protocols (pp. 19-39). Bentham Science Publishers.
[30]https://www.nsnam.org