文献类型：期刊文献

英文题名：Low-delay Node-disjoint Multi-path Routing using Complementary Trees for Industrial Wireless Sensor Networks

作者：Liu, Luming[1,2];Ling, Zhihao[1,2];Zuo, Yun[1,2]

机构：[1]E China Univ Sci & Technol, Sch Informat Sci & Engn, Shanghai 200237, Peoples R China;[2]Minist Educ, Key Lab Adv Control & Optimizat Chem Proc, Shanghai 200237, Peoples R China

年份：2011

卷号：5

期号：11

起止页码：2052

外文期刊名：KSII TRANSACTIONS ON INTERNET AND INFORMATION SYSTEMS

收录：;WOS:【SCI-EXPANDED(收录号:WOS:000300514600010)】；

基金：The work was supported by the National High Technology Research and Development Program of China (863 Program), under Grants 2007AA041201-4 and 2009AA04Z144 and the Shanghai Leading Academic Discipline Project under Grant B504.

语种：英文

外文关键词：Node-disjoint multi-path routing; complementary trees; path discovery method; average path length; time complexity

摘要：Complementary trees are two spanning trees rooted at the sink node satisfying that any source node's two paths to the sink node on the two trees are node-disjoint. Complementary trees routing strategy is a special node-disjoint multi-path routing approach. Several complementary trees routing algorithms have been proposed, in which path discovery methods based on depth first search (DFS) or Dijkstra's algorithm are used to find a path for augmentation in each round of path augmentation step. In this paper, a novel path discovery method based on multi-tree-growing (MTG) is presented for the first time to our knowledge. Based on this path discovery method, a complementary trees routing algorithm is developed with objectives of low average path length on both spanning trees and low complexity. Measures are employed in our complementary trees routing algorithm to add a path with nodes near to the sink node in each round of path augmentation step. The simulation results demonstrate that our complementary trees routing algorithm can achieve low average path length on both spanning trees with low running time, suitable for wireless sensor networks in industrial scenarios.