Processing math: 100%
We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Xue Zhang, Jue Hong, Sang-Lu Lu, Li Xie, Jian-Nong Cao. Scoped Bellman-Ford Geographic Routing for Large Dynamic Wireless Sensor Networks[J]. Journal of Computer Science and Technology, 2008, 23(6): 944-956.
Citation: Xue Zhang, Jue Hong, Sang-Lu Lu, Li Xie, Jian-Nong Cao. Scoped Bellman-Ford Geographic Routing for Large Dynamic Wireless Sensor Networks[J]. Journal of Computer Science and Technology, 2008, 23(6): 944-956.

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

More Information
  • Received Date: September 10, 2007
  • Revised Date: July 20, 2008
  • Published Date: November 09, 2008
  • Routing is a fundamentalproblem in wireless sensor networks. Most previous routing protocols arechallenged when used in large dynamic networks as they suffer fromeither poor scalability or the void problem. In this paper, we propose anew geographic routing protocol, SBFR (Scoped Bellman-Ford Routing), forlarge dynamic wireless sensor networks. The basic idea is that each nodekeeps a view scope of the network by computing distance vectors usingthe distributed Bellman-Ford method, and maintains a cost for routing tothe sink. When forwarding a packet, a node picks the node with minimumcost in its routing table as a temporary landmark. While achieving goodscalability, it also solves the void problem in an efficient mannerthrough the combination of Bellman-Ford routing and cost-basedgeographic routing. Analytical and simulation results show that SBFRoutperforms other routing protocols not only because of its robustnessand scalability but also its practicality and simplicity.
  • [1] Heinzelman W, Kulik J, Balakrishnan H. Adaptive protocols
    [2]
    } 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.
    [3]
    } 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.
    [4]
    } 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.
    [5]
    } 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.
    [6]
    } 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.
    [7]
    } 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.
    [8]
    } 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,
    [9]
    } 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.
    [10]
    } 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.
    [11]
    } 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.
    [12]
    } 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.
    [13]
    } 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.
    [14]
    } 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)
    [15]
    } 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.
    [16]
    } 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
    [17]
    } 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.
    [18]
    } 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.
    [19]
    } Al-Karaki J N, Kamal A E. Routing techniques in wireless sensor networks: A survey. {\it IEEE Wireless Communications}, 2004, 11(6): 6--28.
    [20]
    } 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.
    [21]
    } Clausen T, Jacquet P. Optimized link state routing protocol (OLSR). \it IETF RFC 3626, \rm 2003, http://www.ietf.org/rfc/rfc3626.txt.
    [22]
    } 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.
    [23]
    } 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.
    [24]
    } 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.
    [25]
    } 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.
    [26]
    } 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.
    [27]
    } 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.
    [28]
    } 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.
    [29]
    } 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.
    [30]
    } 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.
    [31]
    } 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.
    [32]
    } 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.
    [33]
    } 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.
    [34]
    } 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.
    [35]
    } 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.
    [36]
    } 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.
    [37]
    } 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.
    [38]
    } 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.
    [39]
    } 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.
    [40]
    } 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.
    [41]
    } 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.
    [42]
    } 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.
    [43]
    } 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.

Catalog

    Article views (18) PDF downloads (1404) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return