Open Access Open Access  Restricted Access Subscription or Fee Access

Breadth Fixed Gossip: a Route Discovery Mechanism in Ad Hoc Network


(*) Corresponding author


Authors' affiliations


DOI: https://doi.org/10.15866/irecos.v11i11.10537

Abstract


The lack of information from a root node to neighbors becomes a particular constraint in a message delivery. While the transmission range of node needs to be considered also for ensuring a delivered packet message to them. Therefore, a route discovery mechanism is a good start to make a reliable path in an unknown environment. The objective of this study is to explore the implementation of Breadth First Search, fixed radius model, and gossip algorithms (Breadth Fixed Gossip) on the ad hoc network. Simulations were conducted to obtain the value of three metrics i.e. saved retransmission, transmission failure, and hop counts. These results were compared with Depth First Search and Gossip performance. It indicates that saved retransmission metric Breadth Fixed Gossip has a 58 times better performance, reduces transmission failure by 20%, and requires 50% more hops at transmission range below 15 than Depth First Search and Gossip.
Copyright © 2016 Praise Worthy Prize - All rights reserved.

Keywords


Route Discovery; Breadth First Search; Gossip; Fixed Radius; Wireless; Ad Hoc Network

Full Text:

PDF


References


Enshaei, M., Mohd Hanapi, Z., Othman, M., A Review: Mobile Ad Hoc Networks Challenges, Attacks, Security, Vulnerability and Routing Protocols, (2014) International Journal on Communications Antenna and Propagation (IRECAP), 4 (5), pp. 168-179.
http://dx.doi.org/10.15866/irecap.v4i5.3001

Adnan, A., Hanapi, Z., Geographic Routing Protocols for Wireless Sensor Networks: Design and Security Perspectives, (2015) International Journal on Communications Antenna and Propagation (IRECAP), 5 (4), pp. 197-211.
http://dx.doi.org/10.15866/irecap.v5i4.6252

Senthil Kumar, R., Sureshkumar, C., Cluster Based AODV Protocol to Minimizing the Route Rediscovery Process and to Improve the Lifetime of Network in MANET, (2014) International Review on Computers and Software (IRECOS), 9 (1), pp. 38-47.

Alzabin, N., Mesleh, A., Hamed, S., Massadeh, S., AlHeyasat, O., AlQaisi, A., A QoS Based DSR Routing Protocol for MANETs Using Bandwidth, (2014) International Journal on Communications Antenna and Propagation (IRECAP), 4 (5), pp. 151-156.
http://dx.doi.org/10.15866/irecap.v4i5.3702

Ramachandran, P., Murukanantham, D., A Location Based-Energy Aware Routing Approach for Mobile Ad Hoc Networks, (2014) International Journal on Communications Antenna and Propagation (IRECAP), 4 (4), pp. 114-123.
http://dx.doi.org/10.15866/irecap.v4i4.3106

Yakine, F., Idrissi, A., Performance Comparison of ILP Models for QoS Topology Control to Conserve Energy in WANETs, (2015) International Journal on Communications Antenna and Propagation (IRECAP), 5 (6), pp. 328-336.
http://dx.doi.org/10.15866/irecap.v5i6.7653

Kuppuchamy, N., Manimegalai, R., Fuzzy Logic with Hybrid Optimization Approach for Optimal Route Selection in MANET, (2014) International Review on Computers and Software (IRECOS), 9 (2), pp. 230-237.

Sasson, Y., Cavin, D., Schiper, A., Probabilistic Broadcast for Flooding in Wireless Mobile Ad hoc Networks, Proceedings of Wireless Communications and Networking (Page: 1124-1130 Year of Publication: 2003 ISBN:0-7803-7700-1).
http://dx.doi.org/10.1109/wcnc.2003.1200529

X. Wang, Probabilistic Flooding Simulation [Internet]. The MartWorks, Inc. June 27, 2005. Available from: https://www.mathworks.com/matlabcentral/fileexchange/7928-probabilistic-flooding-simulation/content/Gossip.m.

Montresor, A., Intelligent Gossip, Proceedings of the 2nd International Symposium on Intelligent Distributed Computing (Page: 3-10 Year Publication: 2008 ISBN:978-3-540-85257-5).
http://dx.doi.org/10.1007/978-3-540-85257-5_1

B. Blywis et al. A survey of flooding Gossip routing and related schemes for wireless multi-hop networks. Berlin: Institute of Computer Science, Freie Universitat Berlin, Germany. Technical Report No. TR-B-11-106, October 10, 2011. Available from: http://www.diss.fu-berlin.de/docs/servlets/MCRFileNodeServlet/FUDOCS_derivate_000000001761/2010-Gossip-Routing.pdf.

D. H. Rothman, Modeling Environmental Complexity [Internet]. Boston: Massachusetts Institute of Technology, MIT OpenCourseWare; November 8, 2011 [cited 2016 Nov 25]. [36p.]. Available from: https://dspace.mit.edu/bitstream/handle/1721.1/99739/12-086-fall-2011/contents/lecture-notes/MIT12_086F11_percolation.pdf.

S. R. Broadbent, J. M. Hammersley, Percolation processes I. crystals and mazes, (1957) Cambridge Philosophical Society, 53, pp. 629–641.
http://dx.doi.org/10.1017/s0305004100032680

Y. Sasson, D. Cavin and A. Schiper, Probabilistic Broadcast for Flooding in Wireless Mobile Ad hoc Networks, (2003) Wireless Communications and Networking Conference, 2, pp. 1124-1130.
http://dx.doi.org/10.1109/wcnc.2003.1200529

P. Erdos˝, A. Ren´yi, On The Evolution of Random Graphs, (1960) Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5, pp. 17–61.
http://dx.doi.org/10.1017/s1446788700025507

Krishnamachari, B., Wicker, S.B., Bejar, R., Phase transition phenomena in wireless ad-hoc networks, Proceedings of Symposium on Ad-Hoc Wireless Networks, (Page: 2921 - 2925 Year Publication: 2001 ISBN:0-7803-7206-9).
http://dx.doi.org/10.1109/glocom.2001.965963

Z. Haas, J. Y. Halpern, and L. Li, Gossip-Based Ad Hoc Routing, (2006) IEEE Transactions on Networking, 14 (3), pp. 479-491.
http://dx.doi.org/10.1109/tnet.2006.876186

X. Y. Li, K. Moaveninejad, O. Frieder, Regional Gossip Routing for Wireless Ad Hoc Networks, (2005) Mobile Networks and Applications, 10 (1), pp. 61-77.
http://dx.doi.org/10.1023/b:mone.0000048546.90440.0d

Shi, Z., Shen, H., Adaptive Gossip-based Routing Algorithm, Proceedings of IEEE International Conference on Performance, Computing, and Communications (Page: 323-324 Year of Publication: 2004 ISBN: 0-7803-8396-6).
http://dx.doi.org/10.1109/pccc.2004.1301101

A. D. G. Dimakis, A. D. Sarwate, and M. J. Wainwright, Geographic Gossip: Efficient Averaging for Sensor Networks, (2008) IEEE Transactions on Signal Processing, 56 (3), pp. 1205–1216.
http://dx.doi.org/10.1109/tsp.2007.908946

C. P. Dwivedi, S. Sharma and V. Sharma, A Survey on Gossip-based Energy Conservation for Wireless Ad Hoc Network Routing, (2012) International Journal of Computer Technology and Electronics Engineering, 2 (4), pp. 31–36.
http://dx.doi.org/10.1109/ccece.2004.1347653

Fauji, S., Kalpakis, K., A gossip-based energy efficient protocol for robust in-network aggregation in wireless sensor networks, Proceedings of IEEE International Conference on Pervasive Computing and Communications Workshops (Page: 166-171 Year of Publication: 2011 ISBN: 978-1-61284-938-6).
http://dx.doi.org/10.1109/percomw.2011.5766862

AlShawi, I. S., Yan, L., Pan, W., Luo, B., A Fuzzy-Gossip routing protocol for an energy efficient wireless sensor networks, Proceedings of IEEE Sensors (Page: 1-4 Year of Publication: 2012 ISBN: 978-1-4577-1766-6).
http://dx.doi.org/10.1109/icsens.2012.6411162

Chiuso, A., Fagnani, F., Schenato, L., Zampieri, S., Gossip algorithms for distributed ranking, Proceedings of American Control Conference (Page: 5468-5473 Year of Publication: 2011 ISBN: 978-1-4577-0080-4).
http://dx.doi.org/10.1109/acc.2011.5991301

Kempe, D., Dobra, A., Gehrke, J., Gossip-based computation of aggregate information, Proceedings of 44th Annual IEEE Symposium on Foundations of Computer Science (Page: 482-491 Year of Publication: 2003 ISBN: 0-7695-2040-5).
http://dx.doi.org/10.1109/sfcs.2003.1238221

Depth-First Search (DFS) - Algorithm and Data Structures. (2016, April 9). Retrieved from http://www.crazyforcode.com/depth-first-search-dfs-algorithms-data-structures/.

Depth First Search. (2009, December 18). Retrieved from http://intelligence.worldofcomputing.net/ai-search/depth-first-search.html#.V-DkcvQpr6s.

Yoo, A., Chow, E., Henderson, K., McLendon, W., Hendrickson, B., Catalyurek, U., A scalable distributed parallel breadth-first search algorithm on BlueGene/L, Proceedings of The ACM/IEEE Super Computing (Page: 25 Year of Publication: 2005 ISBN: 1-59593-061-2).
http://dx.doi.org/10.1109/sc.2005.4

R. Zhou, E. A. Hansen, Breadth-first Heuristic Search, (2006) Artificial Intelligence, 170 (4-5), pp. 385-408.
http://dx.doi.org/10.1016/j.artint.2005.12.002

V. K. Akram, O. Dagdeviren, Breadth-First Search-Based Single-Phase Algorithms for Bridge Detection in Wireless Sensor Network, (2013) Sensors, 13, pp. 8786-8813.
http://dx.doi.org/10.3390/s130708786

Algorithm Chapter 5: Decrease and Conquer. (2012, April 11). Retrieved from http://www.slideshare.net/chidabdu/algorithm-chapter-5.


Refbacks

  • There are currently no refbacks.



Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize