Special Issue: Computer Networks and Distributed Computing

• Computer Network and Internet • Previous Articles     Next Articles

Scoped Bellman-Ford Geographic Routing for Large Dynamic Wireless Sensor Networks

Xue Zhang1,3, Jue Hong1, Sang-Lu Lu1, Li Xie1, and Jian-Nong Cao2   

  1. 1State Key Laboratory for Novel Software Technology, Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China 2Department of Computing, Hong Kong Polytechnic University, Hong Kong, China 3Department of Electrical Engineering, College of Engineering, Nanjing Agricultural University, Nanjing 210031, China
  • Received:2007-09-11 Revised:2008-07-21 Online:2008-11-10 Published:2008-11-10

Routing is a fundamental problem in wireless sensor networks. Most previous routing protocols are challenged when used in large dynamic networks as they suffer from either poor scalability or the void problem. In this paper, we propose a new geographic routing protocol, SBFR (Scoped Bellman-Ford Routing), for large dynamic wireless sensor networks. The basic idea is that each node keeps a view scope of the network by computing distance vectors using the distributed Bellman-Ford method, and maintains a cost for routing to the sink. When forwarding a packet, a node picks the node with minimum cost in its routing table as a temporary landmark. While achieving good scalability, it also solves the void problem in an efficient manner through the combination of Bellman-Ford routing and cost-based geographic routing. Analytical and simulation results show that SBFR outperforms other routing protocols not only because of its robustness and scalability but also its practicality and simplicity.


[1] Heinzelman W, Kulik J, Balakrishnan H. Adaptive protocols
} for information dissemination in wireless sensor networks. In {\it Proc. the ACM International Conference on Mobile Computing and Networking $($MobiCom$)$}, Seattle, Washington, USA, 1999, pp.174--185.
[2]} Intanagonwiwat C, Govindan R, Estrin D. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In {\it Proc. the ACM International Conference on Mobile Computing and Networking $($MobiCom$)$}, Boston, Massachusetts, USA, 2000, pp.56--67.
[3]} Braginsky D, Estrin D. Rumor routing algorithm for sensor networks. In {\it Proc. the ACM International Workshop on Sensor Networks and Applications $($WSNA$)$}, Atlanta, Georgia, USA, 2002, pp.22--31.
[4]} Schurgers C, Srivastava M B. Energy efficient routing in wireless sensor networks. In {\it Proc. the MILCOM on Communications for Network-Centric Operations: Creating the Information Force}, Washington DC, USA, 2001, pp.357--361.
[5]} Ye F, Chen A, Lu S, Zhang L. A scalable solution to minimum cost forwarding in large sensor networks. In {\it Proc. the IEEE International Conference on Computer Communications and Networks $($ICCCN$)$}, Scottsdale, Arizona, USA, 2001, pp.304--309.
[6]} Servetto S, Barrenechea G. Constrained random walks on random graphs: Routing algorithms for large scale wireless sensor networks. In {\it Proc. the ACM International Workshop on Wireless Sensor Networks and Applications $($WSNA$)$}, Atlanta, Georgia, USA, 2002, pp.12--21.
[7]} Karp B, Kung H T. Greedy perimeter stateless routing for wireless networks. In {\it Proc. the ACM International Conference on Mobile Computing and Networking $($MobiCom$)$}, Boston, Massachusetts, USA, 2000, pp.243--254,
[8]} S\'{a}nchez J A, Mar\'{i}n-P\'{e}rez R, Ruiz P M. Beacon-less geographic routing in real wireless sensor networks. \it Journal of Computer Science and Technology, \rm 2008, 23(3): 438--450.
[9]} Xing Guoliang, Lu Chenyang, Pless Robert, Huang Qingfeng. Impact of sensing coverage on greedy geographic routing algorithms. \it IEEE Transactions on Parallel and Distributed Systems, \rm 2006, 17(4): 348--360.
[10]} Chen D, Varshney P K. On-demand geographic forwarding for data delivery in wireless sensor networks. \it Computer Communications, \rm 2007, 30(14/15): 2954--2967.
[11]} Zorzi M, Rao R. Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Energy and latency performance. \it IEEE Transactions on Mobile Computing, \rm 2003, 2(4): 349--365.
[12]} Kuhn F, Wattenhofer R, Zollinger A. An algorithmic approach to geographic routing in ad hoc and sensor networks. \it IEEE/ACM Transactions on Networking, \rm 2008, 16(1): 51--62.
[13]} Wang Guojun, Wang Tian, Jia Weijia, Guo Minyi, Li Jie. Adaptive location updates for mobile sinks in wireless sensor networks. \it Journal of Supercomputing, \rm 2008. (To appear)
[14]} Jia Weijia, Wang Tian, Wang Guojun, Guo Minyi. Hole avoiding in advance routing in wireless sensor networks. In {\it Proc. the IEEE Wireless Communications and Networking Conference $($WCNC$)$}, Hong Kong, China, 2007, pp.3519--3523.
[15]} Chen Guihai, Li Chengfa, Ye Mao, Wu Jie. An unequal cluster-based routing protocol in wireless sensor networks. \it Wireless Networks, \rm 2007, 42(2): 183--198. \newpage
[16]} Fang Qing. Robust and compact geographic/topological structures for routing and information dissemination in \hbox{wireless} sensor networks [Dissertation]. Adviser-Leonidas J. Guibas, Stanford, CA, USA, 2007.
[17]} Frey Hannes, Gorgen Daniel. Geographical cluster-based routing in sensing-covered networks. \it IEEE Transactions on Parallel and Distributed Systems, \rm 2006, 17(9): 899--911.
[18]} Al-Karaki J N, Kamal A E. Routing techniques in wireless sensor networks: A survey. {\it IEEE Wireless Communications}, 2004, 11(6): 6--28.
[19]} Pei Guangyu, Gerla Mario, Chen Tsu Wei. Fisheye state routing: A routing scheme for ad hoc wireless networks. In {\it Proc. the IEEE International Conference on Communications $($ICC$)$}, New Orleans, LA, USA, 2000, pp.70--74.
[20]} Clausen T, Jacquet P. Optimized link state routing protocol (OLSR). \it IETF RFC 3626, \rm 2003, http://www.ietf.org/rfc/rfc3626.txt.
[21]} Perkins C, Bhagwat P. Highly dynamic destination-sequenced distance-vector routing ({DSDV}) for mobile computers. In {\it Proc. the ACM Conference on Communications Architectures, Protocols and Applications $($SIGCOMM$)$}, London, UK, 1994, pp.234--244.
[22]} Murthy S, Garcia-Luna-Aceves J J. An efficient routing protocol for wireless networks. \it ACM Mobile Networks and Applications, \rm 1996, 1(2): 183--197.
[23]} Ahmed N, Kanhere S S, Jha S. The holes problem in wireless sensor networks: A survey. \it ACM SIGMOBILE Mobile Computing and Communications Review, \rm 2005, 9(2): 4--18.
[24]} Chen D, Varshney P K. A survey of void handling techniques for geographic routing in wireless networks. \it IEEE Communications Surveys and Tutorials, \rm First Quarter, 2007, 9(1): 50--67.
[25]} Kranakis E, Singh H, Urrutia J. Compass routing on geometric networks. In {\it Proc. the Canadian Conference on Computational Geometry}, Vancouver, Canada, 1999, pp.51--54.
[26]} Kuhn F, Wattenhofer R, Zollinger A. Asymptotically optimal geometric mobile ad-hoc routing. In {\it Proc. International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications $($DIAL-M$)$}, Atlanta, Georgia, USA, 2002, pp.24--33.
[27]} Kuhn F, Wattenhofer R, Zollinger A. Worst-case optimal and average-case efficient geometric ad-hoc routing. In {\it Proc. the ACM International Symposium on Mobile Ad-Hoc Networking and Computing $($MobiHoc$)$}, Annapolis, Maryland, USA, 2003, pp.267--278.
[28]} Huang Qingfeng, Bhattacharya Sangeeta, Lu Chenyang, Roman Gruia-Catalin. F{AR}: Face-aware routing for mobicast in large-scale sensor network. \it ACM Transactions on Sensor Networks, \rm 2005, 1(2): pp.240--271.
[29]} Li Xiang Yang, Song W Z, Wang Y. Localized topology control for heterogeneous wireless sensor networks. \it ACM Transactions on Sensor Networks, \rm 2006, 2(1): 129--153.
[30]} Zou L, Lu M, Xiong Z. P{AGER}: A distributed algorithm for the dead-end problem of location-based routing in sensor networks. In {\it Proc. the IEEE International Conference on Computer Communications and Networks $($ICCCN$)$}, Chicago, Illinois, USA, 2004, pp.509--514.
[31]} Chen S, Fan G, Cui J. Avoid voids in geographic routing for data aggregation in sensor networks. \it International Journal of Ad Hoc and Ubiquitous Computing, \rm 2006, 1(4): 169--178.
[32]} Yu Y, Estrin D, Govindan R. Geographical and energy-aware routing: A recursive data dissemination protocol for wireless sensor networks. Technical Report UCLA-CSD TR-01-0023, Department of Computer Science, UCLA, May 2001.
[33]} Lim Menghow, Greenhalgh Adam, Chesterfield Julian, Crowcroft Jon. Landmark guided forwarding. In {\it Proc. the IEEE International Conference on Network Protocols $($ICNP$)$}, Boston, Massachusetts, USA, 2005, pp.169--178.
[34]} Joa-Ng Mario, Lu I-Tai. A peer-to-peer zone-based two-level link state routing for mobile ad hoc networks. \it IEEE Journal on Selected Areas in Communications, \rm 1999, 17(8): 1415--1424.
[35]} Stojmenovic Ivan, Lin Xu. Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks. \it IEEE Transactions on Parallel and Distributed Systems, \rm 2001, 12(10): 1023--1032.
[36]} Du X, Wu D. Adaptive cell-relay routing protocol for mobile ad hoc networks. \it IEEE Transactions on Vehicular Technology, \rm 2006, 55(1): 278--285.
[37]} Mathur Gaurav, Desnoyers Peter, Ganesan Deepak, Shenoy Prashant. Ultra-low power data storage for sensor networks. In {\it Proc. the ACM International Conference on Information Processing in Sensor Networks $($IPSN$)$}, Nashville, Tennessee, USA, 2006, pp.374--381.
[38]} Cheng X, Thaeler A, Xue G, Chen D. T{PS}: A time-based positioning scheme for outdoor wireless sensor networks. In {\it Proc. the IEEE Conference on Computer Communications $($INFOCOM$)$}, Hong Kong, China, 2004, pp.2685--2696.
[39]} Hu L, Evans D. Localization for mobile sensor networks. In {\it Proc. the ACM International Conference on Mobile Computing and Networking $($MobiCom$)$}, Philadelphia, Pennsylvania, USA, 2004, pp.1--13.
[40]} Karloff Howard. On the convergence time of a path-vector protocol. In {\it Proc. the ACM-SIAM Symposium on Discrete Algorithms}, New Orleans, Louisiana, USA, 2004, pp.605--614.
[41]} Prakash R. Unidirectional links prove costly in wireless ad-hoc networks. In {\it Proc. the International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications $($DIAL-M$)$}, Seattle, Washington, USA, 1999, pp.15--22.
[42]} Zhou Gang, He Tian, Krishnamurthy S, Stankovic J. Models and solutions for radio irregularity in wireless sensor networks. \it ACM Transactions on Sensor Networks, \rm 2006, 2(2): 221--262.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Wang Xuan; Lü Zhimin; Tang Yuhai; Xiang Yang;. A High Resolution Chinese Character Generator[J]. , 1986, 1(2): 1 -14 .
[2] Liu Tong; C.S.Tang;. Semantic Specification and Verification of Data Flow Diagrams[J]. , 1991, 6(1): 21 -31 .
[3] Wang Xianchang; Chen Huowang; Zhao Qinping;. On the Relationship Between TMS and Logic Programs[J]. , 1994, 9(3): 245 -251 .
[4] Gao Hong;. Transformation List for SGML Application[J]. , 1995, 10(5): 455 -462 .
[5] Lu Bo; Cai Shijie;. A Skeleton-Based Approach of Automatically Generating Some Chinese Typefaces[J]. , 1996, 11(1): 30 -38 .
[6] XI Haifeng; LUO Yupin; YANG Shiyuan;. An Approach to Active Learning for Classifier Systems[J]. , 1999, 14(4): 372 -378 .
[7] LI Laruan; LI Chunlin;. Studies on Algorithms for Self-Stabilizing Communication Protocols[J]. , 1999, 14(6): 606 -613 .
[8] HUANG Hao; CHEN Guihai; XIE Li; SUN Zhongxiu;. Multicast Protocol for Uni-Directional Networks[J]. , 2000, 15(2): 158 -168 .
[9] Min Liu, Zhong-Cheng Li, and Xiao-Bing Guo. An Efficient Handoff Decision Algorithm for Vertical Handoff Between WWAN and WLAN[J]. , 2007, 22(1): 114 -120 .
[10] Jie Liang and Xue-Jia Lai. Improved Collision Attack on Hash Function MD5[J]. , 2007, 22(1): 79 -87 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved