Adaptation of the breadth first search algorithm for cut-edge detection in wireless multihop networks

ABSTRACT

We extend the Breadth First Search (BFS) algorithm to use it for cut-edge(bridge) detection in graphs. The changes in the algorithm are tailored such that the algorithm can be applied in wireless multihop networks: e.g., it fully utilizes the broadcasting nature of the wireless medium. The distributed BFS algorithm (flooding) is widely used for route discovery and information dissemination in wireless multihop networks (WMNs) so the overhead introduced by our bridge detection algorithm is limited - the network is already performing the distributed BFS and we reuse the information from it to detect the bridges.

We verify our detection algorithm on the data sampled from Berlin's free multi-hop wireless network. Detection precision varies depending on the algorithm parameters but for the representative algorithm configurations it stabilizes around 75%. Analysis of the data samples indicated that due to unreliability of wireless links and frequent occurrence of bridges the route discovery mechanism cannot find the route between two nodes although a valid route exists. We use our bridge detection algorithm to improve the route discovery success ratio from about 47% to approximately 90% by utilizing unicast of route discovery messages over the bridges. We verified by using fault injection the robustness of our approach as precision and route discovery remained high even for frequent node failures in the network.

REFERENCES

• 1: B.A.T.M.A.N. (Better Approach To Mobile Ad-hoc Networking) routing protocol. https://www.open-mesh.net/batman.
• 2: Berliner Freifunk-Community. http://olsrexperiment.de/.
• 3: Hannover free network map. http://map.freifunk-hannover.de/map.php.
• 4: Tropos MetroMesh Proven: Metro-Scale Wi-Fi in Chaska, MN. Performance Whitepaper, 2005.
• 5: Jiří Barnat , Ivana Černá, Distributed breadth-first search LTL model checking, Formal Methods in System Design, v.29 n.2, p.117-134, September 2006 [doi>10.1007/s10703-006-0009-y]
• 6: T. Camp, J. Boleng, and L. Wilcox. Location information services in mobile ad hoc networks. volume 5, New York, USA, 2002.
• 7: I. Chakeres and C. Perkins. Dynamic manet on-demand (DYMO) routing (IETF Draft). March 2007.
• 8: Kai Chen , Samarth H. Shah , Klara Nahrstedt, Cross-Layer Design for Data Accessibility in Mobile Ad Hoc Networks, Wireless Personal Communications: An International Journal, v.21 n.1, p.49-76, April 2002 [doi>10.1023/A:1015509521662]
• 9: T. Clausen , P. Jacquet, Optimized Link State Routing Protocol (OLSR), RFC Editor, 2003
• 10: Emden R. Gansner , Stephen C. North, An open graph visualization system and its applications to software engineering, Software—Practice & Experience, v.30 n.11, p.1203-1233, Sept. 2000 [doi>10.1002/1097-024X(200009)30:11<1203::AID-SPE338>3.3.CO;2-E]
• 11: D. Goyal , J. Caffery, Jr., Partitioning Avoidance in Mobile Ad Hoc Networks Using Network Survivability Concepts, Proceedings of the Seventh International Symposium on Computers and Communications (ISCC'02), p.553, July 01-04, 2002
• 12: M. Hauspie, D. Simplot, and J. Carle. Partition detection in ad-hoc networks using multiple disjoint paths set. In Proc. of the 1st Int. Workshop on Objects Models and Multimedia Technologies (OMMT), Geneva, Switzerland, 2003.
• 13: D. Johnson, D. Maltz, and Y.-C. Hu. The dynamic source routing protocol for mobile ad hoc networks (RFC 4728). February 2007.
• 14: Y. Daniel Liang , Chongkye Rhee, An optimal algorithm for finding biconnected components in permutation graphs, Proceedings of the 1995 ACM 23rd annual conference on Computer science, p.104-108, February 28-March 02, 1995, Nashville, Tennessee, United States [doi>10.1145/259526.259544]
• 15: B. Milic and M. Malek. Dropped edges and faces' size in gabriel and relative neighborhood graphs. In Proceedings of The Third IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2006), Vancouver, Canada, 2006.
• 16: B. Milic and M. Malek. Analyzing large scale real-world wireless multihop network. Accepted for IEEE Communication Letters, 2007.
• 17: Bratislav Milic , Nikola Milanovic , Miroslaw Malek, Prediction of Partitioning in Location-Aware Mobile Ad Hoc Networks, Proceedings of the Proceedings of the 38th Annual Hawaii International Conference on System Sciences (HICSS'05) - Track 9, p.306.3, January 03-06, 2005 [doi>10.1109/HICSS.2005.501]
• 18: C. Perkins , E. Belding-Royer , S. Das, Ad hoc On-Demand Distance Vector (AODV) Routing, RFC Editor, 2003
• 19: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 20: R. Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1:146--160, 1972.
• 21: Ramakrishna Thurimella, Sub-linear distributed algorithms for sparse certificates and biconnected components, Journal of Algorithms, v.23 n.1, p.160-179, April 1997 [doi>10.1006/jagm.1996.0832]
• 22: K. Wang and B. Li. Group mobility and partition prediction in wireless ad-hoc networks. In Proc. of IEEE International Conference on Communications (ICC 2002), New York, 2002.
• 23: Brad Williams , Tracy Camp, Comparison of broadcasting techniques for mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513825]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

General Terms:
Algorithms, Reliability

Keywords:
cut-edge detection, real network analysis, wireless multihop networks