A high performance cluster-based broadcasting algorithm for wireless ad hoc networks based on a novel gateway selection approach

ABSTRACT

In this paper we propose a new broadcasting algorithm for a "stability-based clustering algorithm". In this algorithm a novel traffic isolation method has been used to reduce the control message exchanges. The broadcasting traffic is divided into internal (flow inside a cluster) and external traffic (flow among the clusters). For internal flooding traffic, cluster-heads and gateways are responsible for re-broadcasting but for external ones, border nodes may perform the forwarding function as well. This simplifies the gateway selection method through the local selection of gateway nodes by its cluster head. Therefore a cluster head selects gateway in its own cluster without any knowledge of the other clusters. In the proposed method we significantly reduce the broadcast overhead and also improve the broadcast delivery ratio in mobile networks. Considering the effect of mobility and node density, a number of simulations have been conducted. The results show that the number of re-broadcasting nodes is less than 25% of the total number of nodes gwhich is almost constant with the node mobility, while the broadcast coverage is close to 100%. Moreover, we study the flooding parameters in light and dense networks and show the improvement of the broadcasting performance in comparison to other methods.

REFERENCES

• 1: Sze-Yao Ni , Yu-Chee Tseng , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.151-162, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313525]
• 2: Wei Peng , Xi-Cheng Lu, On the reduction of broadcast redundancy in mobile ad hoc networks, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 3: Wei Peng, Xicheng Lu, "AHBP: An Efficient Broadcast Protocol for Mobile Ad Hoc Networks", Journal of Computer Science and Technology, March 2001, Vol.16, No.2, pp.114--125.
• 4: Hyojun Lim , Chongkwon Kim, Multicast tree construction and flooding in wireless ad hoc networks, Proceedings of the 3rd ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.61-68, August 20-20, 2000, Boston, Massachusetts, United States [doi>10.1145/346855.346865]
• 5: I. Stojmenovic1 , M. Seddigh , J. Zunic, Internal Nodes based Broadcasting in Wireless Networks, Proceedings of the 34th Annual Hawaii International Conference on System Sciences ( HICSS-34)-Volume 9, p.9005, January 03-06, 2001
• 6: 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]
• 7: M. Gerla, Taek Jin Kwon; G. Pei , "On-demand routing in large ad hoc wireless networks with passive clustering", in Proceedings of the Wireless Communications and Networking Conference (WCNC'2000), Vol:1, 23-28 Sept.2000, pp.100--105.
• 8: C. E. Perkins, E. M. Royer, S. R. Das, and M. K. Marina, "Performance comparison of two on-demand routing protocols for ad hoc networks," IEEE Personal Communications, vol. 8, pp. 16--28, February 2001.
• 9: D.B. Johnson and D. A. Maltz, "Dynamic Source Routing in Ad-Hoc Wireless Networks", Mobile Computing, T. Imielinski and H. Korth, Eds, Kluwer, 1996, pp. 153--81.
• 10: "The network simulator - ns-2," http://www.isi.edu/nsnam /ns/, 2002.
• 11: Reza Purtoosi , Hassan Taheri , Abbas Mohammadi , Foroohar Foroozan, A Light-Weight Contention-Based Clustering Algorithm for Wireless Ad Hoc Networks, Proceedings of the The Fourth International Conference on Computer and Information Technology (CIT'04), p.627-632, September 14-16, 2004
• 12: R. Purtoosi, H. Taheri, A. Mohammadi and F. Foroozan, "A Stability-Based Clustering Algorithm for Wireless Ad Hoc Networks", in Proceedings of The Australian Telecommunication Networks and Applications Conference (ATNAC 2004), Dec 2004, Sydney, Australia, pp.29--35.
• 13: R. Purtoosi, H. Taheri, A. Mohammadi and F. Foroozan, "Effect of Connectivity and Mobility on the Performance of Stability-Based Clustering Algorithm for Ad Hoc Wireless Networks", in Proceeding of WOCN'05, Dubai, UAE.
• 14: C.R. Lin and M. Gerla, "Adaptive Clustering for Mobile Wireless Networks", IEEE Journal on Selected Areas in Communications, Vol. 15, No. 7, pp. 1265--1275, Sept. 1997.
• 15: A.D. Amis, R. Prakash, T.H.P. Vuong and D.T. Huynh, "Max-Min D-Cluster Formation in Wireless Ad Hoc Networks", Proceedings of IEEE INFOCOM'2000, Tel Aviv, March 2000.
• 16: Ivan Stojmenovic , Mahtab Seddigh , Jovisa Zunic, Dominating Sets and Neighbor Elimination-Based Broadcasting Algorithms in Wireless Networks, IEEE Transactions on Parallel and Distributed Systems, v.13 n.1, p.14-25, January 2002 [doi>10.1109/71.980024]
• 17: Fei Dai , Jie Wu, Performance Analysis of Broadcast Protocols in Ad Hoc Networks Based on Self-Pruning, IEEE Transactions on Parallel and Distributed Systems, v.15 n.11, p.1027-1040, November 2004 [doi>10.1109/TPDS.2004.69]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Algorithms, Performance

Keywords:
ad hoc networks, broadcasting, clustering