This paper deals with the query problem in the Internet of Things (IoT). Flooding is an important query strategy. However, original flooding is prone to cause heavy network loads. To address this problem, we propose a variant of flooding, called Level-Based Flooding (LBF). With LBF, the whole network is divided into several levels according to the distances (i.e., hops) between the sensor nodes and the sink node. The sink node knows the level information of each node. Query packets are broadcast in the network according to the levels of nodes. Upon receiving a query packet, sensor nodes decide how to process it according to the percentage of neighbors that have processed it. When the target node receives the query packet, it sends its data back to the sink node via random walk. We show by extensive simulations that the performance of LBF in terms of cost and latency is much better than that of original flooding, and LBF can be used in IoT of different scales.
References
[1]
Butgereit, L.; Coetzee, L.; Smith, A.C. Turn Me On! Using the “Internet of Things” to Turn Things On and Off. Proceedings of the 2011 6th International Conference on Pervasive Computing and Application, Pretoria, South Africa, 26–28 October 2011; pp. 4–10.
[2]
Huang, Y.; Chen, Z.; Xi, J. A new RFID tag code transformation approach in internet of things. J. Netw. 2012, 7, 145–155.
[3]
Silva, J.S.; Krishnamachari, B.; Boavida, F. An Adaptive Strategy for Energy-Efficient Data Collection in Sparse Wireless Sensor Network. Proceedings of the European Workshop on Wireless Sensor Networks, Coimbra, Portugal, 17–19 February 2010; pp. 322–337.
[4]
Ma, X.; Liu, T. The Application of Wi-Fi RTLS in Automatic Warehouse Management System. Proceedings of the 2011 IEEE International Conference on Automation and Logistics, Dalian, China, 12–14 October 2011; pp. 64–69.
[5]
Mayordomo, I.; Spies, P.; Meier, F.; Otto, S.; Lempert, S.; Bernhard, J.; Pflaum, A. Emerging Technologies and Challenges for the Internet of Things. Proceedings of the Midwest Symposium on Circuits and Systems, Seoul, Korea, 7–10 August 2011.
[6]
Wang, H.; Yu, Y.; Zhu, P.; Yuan, Q. Cloud Computing Based on Internet of Things. Proceedings of the 2011 2nd International Conference on Mechanic Automation and Control Engineering, Hohhot, Inner Mongolia, China, 15–17 July 2011; pp. 1106–1108.
[7]
Tu, B.; Yu, F. Bimodal emotion recognition based on speech signals and facial expression. Adv. Intell. Soft Comput. 2012, 122, 691–696.
[8]
Sadagopan, N.; Krishnamachari, B.; Helmy, A. The ACQUIRE Mechanism for Efficient Querying in Sensor Networks. Proceedings of the 1st IEEE International Workshop on Sensor Network Protocols and Applications, Anchorage, AK, USA, 11 May 2003; pp. 149–155.
[9]
Chang, N.B.; Liu, M. Controlled flooding search in a large network. IEEE/ACM Trans. Netw. 2007, 7, 436–449.
Gehrke, J.; Madden, S. Query processing in sensor networks. IEEE Pervas. Comput. 2004, 3, 46–55, doi:10.1109/MPRV.2004.1269131.
[12]
Silva, J.S.; Krishnamachari, B.; Boavida, F. Querying Dynamic Wireless Sensor Networks with Non-Revisiting Random Walks. Proceedings of the European Workshop on Wireless Sensor Networks, Coimbra, Portugal, 17–19 February 2010; pp. 49–64.
[13]
Gertz, M.; Ludascher, B. Optimizing Query Processing in Cache-Aware Wireless Sensor Networks. Proceedings of the 22nd International Conference on Scientific and Statistical Database Management, Heidelberg, Germany, 30 June–2 July 2010; pp. 69–77.
[14]
Huang, H.; Hartman, J.; Hurst, T. Data-Centric Routing in Sensor Networks Using Biased Walk. Proceedings of the 3rd IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks, Reston, VA, USA, 28 September 2006; pp. 1–9.
[15]
Ahn, J.; Kapadia, S.; Pattern, S.; Sridharan, A.; Zuniga, M.; Jun, J.H.; Avin, C.; Krishnamachari, B. Empirical evaluation of querying mechanisms for unstructured wireless sensor networks. ACM SIGCOMM Comput. Commun. Rev. 2008, 38, 17–26.
[16]
Cheng, Z.; Heinzelman, W. Flooding strategy for target discovery in wireless networks. Wirel. Netw. 2005, 607–618, doi:10.1145/940991.940999.
[17]
Avin, C.; Brito, C. Efficient and Robust Query Processing in Dynamic Environments Using Random Walk Techniques. Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks, Berkeley, CA, USA, 26–27 April 2004; pp. 277–286.
[18]
Braginsky, D.; Estrin, D. Rumor Routing Algorithm for Sensor Networks. Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications, Atlanta, GA, USA, 28 September 2002; pp. 22–30.
[19]
Khan, M.; Gabor, A. An Effective Compiler Design for Efficient Query Processing in Wireless Sensor Networks. Proceedings of the Internal Conference on Circuit and Signal Processing, Shanghai, China, 25 December 2010; pp. 157–159.
[20]
Chakroaborty, A.; Lahiri, K.; Mandal, S.; Patra, D.; Mrinal, K.; Mukherjee, A. Optimization of service discovery in wireless sensor networks. Wired/Wirel. Int. Commun. 2010, 6074/2010, 351–362.
[21]
Rachuri, K.K.; Murthy, C.R. Energy efficient and low latency biased walk techniques for search in wireless sensor networks. J. Parallel Distrib. 2011, 71, 512–522, doi:10.1016/j.jpdc.2010.08.009.
[22]
Johnson, D.B.; Maltz, D.A. Mobile Computing, Chapter Dynamic Source Routing in Ad Hoc Wireless Networks; Imielinski, K., Ed.; Kluwer Academic Publishers: Dordrecht, The Netherlands, 1996; pp. 153–181.
[23]
Perkins, C.; Royer, E.M. Ad Hoc on-Demand Distance Vector Routing. Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, New Orleans, LA, USA, 25–26 February 1999; pp. 90–100.
[24]
Rachuri, K.K.; Muerthy, C.R. On the scalability of expanding ring search for dense wireless sensor networks. J. Parallel Distrib. 2010, 70, 917–929, doi:10.1016/j.jpdc.2010.05.004.
[25]
Haas, Z.J.; Halpem, J.Y.; Li, L. Gossip-based ad hoc routing. IEEE/ACM Trans. Netw. 2006, 14, 479–491, doi:10.1109/TNET.2006.876186.
[26]
Hou, N.; Feng, H.L.; Gu, X. Calculation of flooding probability based on number of neighbor nodes. Appl. Res. Comput. 2010, 27, 3443–3445.
[27]
Lee, I.H.; Yang, S.; Chao, S.H.; Kim, H.S. Robot path routing for shortest moving distance in wireless sensor network. IEICE Trans. Commun. 2010, E92-B, 3495–3498.
[28]
Chao, C.H.; Li, I.H.; Yang, Y.; Li, J.S. An efficient diversity-driven selective forwarding approach for replicated data queries in wireless sensor networks. J. Syst. Archit. 2011, 57, 830–839, doi:10.1016/j.sysarc.2011.01.001.
[29]
Doss, R.; Li, G.; Mark, V.; Tissera, M. Information discovery in mission-critical wireless sensor networks. Comput. Netw. 2010, 54, 2383–2399, doi:10.1016/j.comnet.2010.03.018.
[30]
Andreou, P.; Zeinalipour-Yazti, D.; Pamboris, A.; Chrysanthis, P.K.; Samaras, G. Optimized query routing trees for wireless sensor networks. Inf. Syst. 2011, 36, 267–291, doi:10.1016/j.is.2010.06.001.
[31]
Mian, A.N.; Beraldi, R.; Baldoni, R. On the Coverage Process of Random Walk in Wireless Ad Hoc and Sensor Networks. Proceedings of the IEEE 7th International Conference on Mobile Ad hoc and Sensor Systems, San Francisco, CA, USA, 8–12 November 2010; pp. 146–155.
