As future home appliances will have many useful built-in functions, a communication network that allows a user to access these built-in functions and to control the appliances is highly desirable. If the home appliances are fitted with a wireless communication module, a wireless ad hoc network can be used to easily connect the appliances. For ease of use the nodes are given names such as “living room TV”, “kitchen oven” etc. for identification. This paper proposes the use of counting bloom filter as a routing table for message routing in a name-based home ad hoc network and also discusses the performance of the proposed algorithms via simulation.

 

Published In : IJCSN Journal Volume 3, Issue 1

Date of Publication : 01 February 2014

Pages : 15 - 23

Figures : 09

Tables : 05

Publication Link : IJCSN-2014/3-1/Message-Routing-with-Counting-Bloom-Filter-for-Name-Based-Home-Ad-Hoc-Networks

 

 

 

V.G. Tharinda Nishantha VIDANAGAMA : received his B.Sc. in computer science with first-class honors from Peradeniya University, Sri Lanka in 2003. He received his M.Sc. in Computer Systems and Network Engineering from Waseda Univer¬sity in 2010 where he is currently pursuing his Ph.D. His research interests include wireless ad hoc networks, multi¬cast, mobility and content centric networks.

Hidenori NAKAZATO : received his B. Engineer¬ing degree in electronics and telecom¬munications from Waseda University in 1982 and his MS and Ph.D. degrees in computer science from University of Illinois in 1989 and 1993, respectively. He was with Oki Electric from 1982 to 2000. Since 2000, he has been a faculty member of Gradu¬ate School of Global Information and Telecommunications Studies, Waseda Univer¬sity. His research interests include performance issues in distributed systems and networks.

 

 

 

 

 

 

 

Ad hoc network

Home network

Name-Based addressing and routing

Bloom filtere

This paper investigates the possibility of implementing a routing protocol using a counting bloom filter for a cluster-based ad hoc network with a name-based addressing scheme. The paper describes the reasoning and method of using the counting bloom filter as a routing cache. A performance comparison with CBRP on equal resources showed that the proposed scheme shows preferable results. This research will continue to investigate the possibility of network expansion to cover a larger expanse to construct a network of home networks. A larger expanse would require a new naming scheme which has a higher order of hierarchy. This naming structure should also reflect the hierarchy of the network’s topological structure such as a sub-cluster within a much larger generalized super cluster and so forth. As the number of nodes in such a network would be very high a bloom filter would also require a very large size to keep an optimal false positive ratio. Here it is possible to use any one from a multitude of improved versions of bloom filters which achieve better space savings and higher accuracy [17][18][19] rather than a basic CBF. Also in a name-based environment the intermediate message forwarding nodes need not know the entire network topology as long as there is sufficient routing information to deliver the messages to the next hop. In a hierarchical topology a node would only require the routing information to reach its neighbors and sub or super cluster. This approach would drastically reduce the number of entries to a bloom filter which in turn also reduces the bloom filter size requirements.

 

 

 

 

 

 

 

 

 

[1] Burton H. Bloom. 1970. Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13, 7 (July 1970), 422-426.

[2] Osano, T.; Uchida, Y.; Ishikawa, N., "Routing Protocol Using Bloom Filters for Mobile Ad Hoc Networks," Mobile Ad-hoc and Sensor Networks, 2008. MSN 2008. The 4th Int. Conference on , vol., no., pp.89,94, 10-12 Dec. 2008.

[3] Mingliang Jiang, Jinyang Li, and Y.C. Tay. Cluster based routing protocol, (CBRP). draft-ietf-manet-cbrp-spec-01.txt, Internet draft, August 1999.

[4] Johnson, D.B.;, "Routing in ad hoc networks of mobile hosts," Mobile Computing Systems and Applications (WMCSA), pp.158-163, 8-9 Dec. 1994.

[5] P. Krishna, N.H. Vaidya, M. Chatterjee and D.K. Pradhan. “A cluster-based approach for routing in dynamic networks”. ACM SIGCOMM Comp. Commun. Review 27:49-65, 1997.

[6] M. Petorvic, V. Muthusamy, H.Jacobsen, “Content-Based Routing in Mobile Ad Hoc Networks”, IEEE MobiQuitous, 2005.

[7] M. Meisel, V. Pappas and L. Zhang; “Ad hoc networking via named-data” MobiArch '10, Proc. of the 5th ACM intl. work¬shop, pp 3-8, 978-1-4503-0143-5.

[8] M.Gerla, J.T-C. Tsai, “Multicluster, Mobile, Multimedia radio network”. ACM- Baltzer Journal of Wireless Networks, 1995.

[9] Vidanagama, T.N.; Nakazato, H.; “Name-Based Message Forwarding for Home Ad hoc Networks”, Journal of Wireless Networking and Communications, Vol.3, No.4, Oct. 2013.

[10] Shah, R.C.; Rabaey, J.M., "Energy aware routing for low energy ad hoc sensor networks," Wireless Communications and Networking Conference (WCNC), IEEE , vol.1, no., pp.350,355 vol.1, 17-21 Mar 2002.

[11] A. Ephremides, J.E. Wieselthier, D.J. Baker,; A design concept for reliable mobile radio networks with frequency hopping signal¬ing, Proc. of IEEE, 75(1) (1987), pp.56~73.

[12] A. K. Prakah, “Selecting routers in ad-hoc wireless networks, Proc. of SBT/IEEE ITS (1994).

[13] Li Fan, Pei Cao, Jussara Almeida, and Andrei Z. Broder. 2000. Summary cache: a scalable wide-area web cache sharing protocol. IEEE/ACM Trans. Netw. 8, 3 (June 2000), 281-293.

[14] Vidanagama, T.N.; Nakazato, H., "Mobility in a description based clustered ad hoc network," GLOBECOM Workshops (GC Wkshps), 2010 IEEE, pp.148-152, 6-10 Dec. 2010.

[15] Deke Guo; Yunhao Liu; XiangYang Li; Panlong Yang, "False Negative Problem of Counting Bloom Filter," Knowledge and Data Engineering, IEEE Transactions on , vol.22, no.5, pp.651,664, May 2010.

[16] J. Blustein and A. El-Maazawi, “Bloom ?lters. a tutorial, analysis, and survey,” Technical Report CS-2002-10.

[17] Bonomi, F., Mitzenmacher, M., Panigrahy, R., Singh, S., & Varghese, G. (2006). An improved construction for counting bloom filters. In Algorithms–ESA 2006 (pp. 684-695). Springer Berlin Heidelberg.

[18] Kun Huang; Jie Zhang; Dafang Zhang; Gaogang Xie; Salamatian, K.; Liu, A.X.; Wei Li, "A Multi-partitioning Approach to Building Fast and Accurate Counting Bloom Filters," (IPDPS), 2013 27th Int. Sym. IEEE,., pp.1159,1170, May 2013.

[19] Rottenstreich, O.; Kanizo, Y.; Keslassy, I., "The Variable-Increment Counting Bloom Filter," IEEE/ACM Trans. on Networking, no.99, pp.1880-88, 2012.

[20] Vidanagama, T.N.; Nakazato, H.; “Message Routing with Bloom Filter for Name-Based Home Ad Hoc Networks”, IEICE Tech. Rep., CS2013-53, pp.75-80, Nov. 2013.