Journal of Computer Research and Development (计算机研究与发展) 2009/2009:12 PP.2053-2061

A Disjoint Multi-Path Routing Algorithm in Wireless Sensor Network

Wireless sensor network (WSN) are usually used to monitor environment by collecting data from sensors deployed in a particular area. But the link quality of WSN is unstable and the network easily has nodes failures, so the data loss is an open problem in wireless sensor network. In order to achieve routing robustness in networks, people proposed multi-path routing (MPR) in sensor networks. But MPR fails when the common links or the common nodes in multiple paths fail. To solve the common-link and common-node problem, disjoint multi-path routing (DMPR) is employed where sensors send data to the sink through link-disjoint or node-disjoint path. In this paper, the authors develop a routing mechanism where sensor nodes can send data to sink through node-disjoint paths. And the algorithm is suited for multi-sink applications where every sensor node can forward the packets to any one of the sinks. The number of routing table entries of the algorithms at each node is |K| , where |K| denotes the number of multi-path. The running time complexity of the algorithm is O(|L|) , where |L| denotes the number of links in the network. The experiment results show that the algorithm can effectively improve the routing reliability in sensor networks.

Key words:wireless sensor network,distribution,multi-path routing,disjoint multi-path routing,reliability

ReleaseDate:2014-07-21 15:00:26

[1] Li Jianzhong, Li Jinbao, Shi Shengfei. Concepts, issues and advance of sensor networks and data management of sensor networks [J] . Journal of Software, 2003, 14(10): 1717-1727 (in Chinese)(李建中, 李金宝, 石胜飞. 传感器网络及其数据管理的概念、 问题与进展 [J] . 软件学报, 2003, 14(10): 1717-1727)

[2] Sun Liming, Li Jianzhong, Chen Yu, et al. Wireless Sensor Networks [M] . Beijing: Tsinghua University Press, 2005 (in Chinese)(孙利民, 李建中, 陈渝, 等. 无线传感器网络 [M] . 北京: 清华大学出版社, 2005)

[3] Ishida K, Kakuda Y, Kikuno T. A routing protocol for finding two node-disjoint paths in computer networks [C]//Int Conf on Network Protocols. Washington DC: IEEE, 1992: 340-347

[4] Suurballe J W, Disjoint paths in a network [J] . Networks, 1974, 4: 125-145

[5] Suurballe J W, Tarjan R E. A quick method for finding shortest pairs of disjoint paths [J] . Networks, 1984, 14(2): 325-336

[6] Bhandari R. Optimal physical diversity algorithms and survivable networks [C]//Proc of the 2nd IEEE Symp on Computers and Communications 1997. Washington: IEEE, 1997: 433-441

[7] Lee S J, Gerla M. Split multipath routing with maximally disjoint paths in ad hoc networks [C]//Proc of IEEE ICC 2001. Washington: IEEE, 2001: 3201-3205

[8] Nasipuri A, Das S R. On-demand multi-path routing for mobile ad hoc networks [C]//Proc of IEEE ICCCN 1999. Washington: IEEE, 1999: 64-70

[9] Vutukury S, Garcia-Luna-Aceves J J. MDVA: A distance-vector multipath routing protocol [C]//Proc of IEEE INFOCOM 2001. Washington: IEEE, 2001: 557-564

[10] Richard G Ogier, Nachum Shacham. A distributed algorithm for finding shortest pairs of disjoint paths [C]//Proc of IEEE INFOCOM 1989. Washington: IEEE, 1989: 173-182

[11] Sidhu D, Nair R, Abdallah S. Finding disjoint paths in networks [C]//Proc of ACM SIGCOMM 1991. New York: ACM, 1991: 43-51

[12] Ogier R G, Rutenburg V, Shacham N. Distributed algorithms for computing shortest pairs of disjoint paths [J] . IEEE Trans on Information Theory, 1993, 39(2): 443-455

[13] Cheng C, Kumar S, Garcia-Luna-Aceves J J. An efficient distributed algorithm for routing over K-disjoint paths of minimum total length [C]//Proc of the 28th Annual Allerton Conf on Communication, Control, and Computing. Washington: IEEE, 1990

[14] Srinivas A, Modiano E. Minimum energy disjoint path routing in wireless ad-hoc networks [C]//Proc of the 9th Annual Int Conf on Mobile Computing and Networking (mobicom'03). New York: ACM, 2003: 14-19

[15] Ganesan D, Govindan R, Shenker S, et al. Highly-resilient, energy-efficient multipath routing in wireless sensor network [J] . Mobile Computing and Communications Review (MC2R), 2002, 1(2): 295-298

[16] Deng Jing, Han R, Mishra S. Enhancing base station security in wireless sensor network, CU-CS-951-03 [R] . Boulder, Colorado: University of Colorado, 2003

[17] Thulasiraman P, Ramasubramanian S, Krunz M. Disjoint multipath routing in dual homing networks using colored trees [C]//Proc of GLOBECOM—Wireless Ad Hoc and Sensor Network Symposium. Washington: IEEE, 2006: 1-5

[18] Thulasiraman P, Ramasubramanian S, Krunz M. Disjoint multipath routing to distinct drains in a multi-drain sensor network [C]//Proc of INFOCOM 2007. Washington: IEEE, 2007: 643-651

[19] Intanagonwiwat C, Govindan R, Estrin D. Directed diffusion: A scalable and robust communication paradigm for sensor networks [C]//Proc of ACM MOBICOM 2000. New York: ACM, 2000: 56-67

[20] Krishnamachari B, Estrin D, Wicker S. Impact of data aggregation in wireless sensor network [C]//Proc of Int Workshop of Distributed Event Based Systems (DEBS). Washington: IEEE, 2002: 575-578

[21] Das A, Dutta D. Data acquisition in multiple sink sensor networks [C]//Proc of the 2nd Int Conf on Embedded Networked Sensor Systems. New York: ACM, 2004: 271-272

[22] Ramasubramanian S, Harkara M, Krunz M. Linear time distributed construction of colored trees for disjoint multipath routing [J] . Computer Networks, 2007, 51: 2854-2866