基于多路径机制的无线传感器网络动态路由算法

齐小刚，王东方

(西安电子科技大学数学科学系 西安 710071; 西安电子科技大学综合业务网国家重点实验室 西安 710071)

基于多路径机制的无线传感器网络动态路由算法

齐小刚，王东方

(西安电子科技大学数学科学系 西安 710071; 西安电子科技大学综合业务网国家重点实验室 西安 710071)

传统网络的路由机制往往选择源节点到汇聚节点之间跳数最小的路径传输数据，但是在无线传感器网络中，如果频繁使用同一条路径传输，就会造成该路径上节点应能量消耗过快而过早失效。本文提出了一种基于多路径机制的动态路由算法，主要步骤为找到源节点和汇聚节点的多条路径，选择一条节点最小能量最大的路径进行数据传递。与单路径的路由算法相比，多路径算法在节点生存期和数据传输的性能方面有了显著的提高。

多路径; 网络生存期; 路由; 无线传感器网络

无线传感器网络是由大量具有特定功能的传感器节点通过自组织的无线通信方式，相互传递信息，协同地完成特定功能的智能专用网络[1]。它具有体积小、价格低等良好性质，在工业、农业、交通、军事、安全、医疗、空间探测，以及家庭和办公环境等众多领域都有着广泛的应用[2-5]。与传统Ad hoc网络相比，无线传感器网络的每个传感器节点电源能量有限、通信能力有限以及计算和存储能量有限，是无线传感器网络最大的缺点，也是制约路由协议的主要因素[6-7]。因此，无线传感器网络路由协议设计上以节约能源为主要目标，要求路由算法实现简单、占用资源少，以提高网络的生存周期。

目前，传统网络的路由机制往往选择源节点到汇聚节点之间跳数最小的路径传输数据，但是在无线传感器网络中，如果频繁使用同一条路径传输，就会造成该路径上节点能量消耗过快而过早失效，从而使整个网络被分割成互不相连的孤立部分，缩短了整个网路的生存期[2]。因此，多路径算法的提出成为一种趋势。文献[3]提出了一种能量多路径路由算法。该算法在源节点和汇聚节点之间建立多条路径，根据路径上节点的通信能量消耗以及节点的剩余能量情况，为每条路径赋予一定的选择概率，使得数据传输均衡消耗整个网络的能量，延长整个网络的生存期。然而该算法的概率计算过于复杂，使得计算复杂度过高。

1 基于多路径机制的动态路由算法

1.1 算法基础

由于节点的移动和拓扑结构的不断变化，很难维护一个持续稳定、有效的端到端的路由。多路径的路由[8]最近引起了极大的关注。在传统的Ad hoc网络中，多路径路由相对于单路径路由能获得更好的性能。在Internet传输时，多路径是有效减少数据包丢失的方式。为此，在无线传感器网络中，每次选择多条路径进行数据传输，使节点不会在较短时间内死亡，从而数据传输可以均衡地消耗整个网络的能量，不会因为某一节点的死亡而使整个网络不连通，使网络有较好的吞吐性和整体性，最大限度地延长网络的使用寿命。

1.2 算法假设

在传感器网络的实际应用中，各节点靠电池供电，大量的节点都保持静止状态或很少移动，只有当少量节点“失效”时，网络拓扑才会发生变化。因此，本文的算法提出以下假设：(1) 每个节点都是静止的，汇聚节点固定在传感器网络的中心，接受其余各点传输的数据包；(2) 传感器网络的各个节点的初始能量是相同的，汇聚节点的能量无限大；(3) 每一轮通信结束后，计算当前各个节点的剩余能量；(4) 所有的节点有相同的计算能力支持信号处理和计算路由，并且地位平等。

1.3 相关符号说明

num_point：网络中的节点数目；xi：节点的横坐标；yi：节点的纵坐标；R：连通半径；wij：权值矩阵；dead_point：死亡节点终止数。

1.4 算法描述及流程图

为了增加多路径路由的健壮性，本文将构造最大不相连的多条路径，即尽量在每条路径中不包括相同的节点，以此来阻止在某些共用的节点上的拥塞以及能量的大量消耗，从而做到更加有效地利用整个网络资源。另外的一个好处是当某条路径崩溃时，其他的路径将不会受到影响。

在节点和路径的寿命有一定限制的条件下，本文提出了最大不相交的多路径的路由发现过程，描述如下：

(1) 建立网络。由于无线传感器网络节点的随机性，因此建立网络时，在某一个区域内随机分布传感器节点，得到每一个节点i的坐标(xi,yi)。其中汇聚节点的坐标固定，为网络区域中心。

(2) 确定各点的连通性。确定适当的半径R，距离在R范围内的即确定为两点连通，即：

考虑到节点的动态性，wij的取值是在节点之间距离的基础上进行了一个随机波动，其中rand(0,r)为波动范围。

(3) 寻找两点之间的多条不相交路径。根据Dijkstra最短路径算法，找到两点之间的第一条最短路径，同时将路径上的所有点做标记，使得下一条路径不与该路径相交，然后再用Dijkstra最短路径算法找到第二条路径，依次按照以上步骤找到这两点之间的3条路径；如果在网络不连通的情况下找不到3条路径，这种情况只要求找到最多3条路径。

(4) 算法结束条件。若存在两点之间都找不到路径，则网络不连通，算法终止；当循环dead_point时，程序也终止。

(5) 数据传输阶段。在源节点以及源节点到汇聚节点之间的多条路径中随机选一条进行数据传输。

程序流程图如图1所示。

图1 算法运行流程图

2 算法仿真与分析

本文采用节点随机生成的网络进行计算机仿真。在两个网络规模下比较了多路径与单路径算法的无线传感器网络生命周期、节点生存期以及网络节点的死亡频率。

(1) 在50 m×50 m的网络范围内，随机地放置50个传感器节点，并设定传感节点的通信半径为20 m，节点能量为15 J；汇聚节点的坐标为(25, 25)。

(2) 在100 m×100 m的网络范围内，随机放置100个传感器节点，并设定传感器节点的通信半径为30 m，节点能量为15 J；汇聚节点的坐标为(50, 50)。

仿真结果如表1所示。

表1 节点死亡时网络经历通信轮数

从表1中可以看出，多路径算法能有效地提高网络的生命周期。在50 m×50 m的区域中，基于多路径算法的网络的周期比单路径算法下网络的寿命提高了16%；而在100 m×100 m的区域中，提高了407%。

图2 分布区域不同条件下20个节点的死亡频率对比

图2为单路径与多路径算法的网络节点死亡时间的对比图，其中横轴代表死亡频率，即节点死亡之前的通信轮数，纵轴代表网络中的剩余节点数。根据图2可以得出以下结论：

(1) 分布区域为50 m×50 m时多路径算法的效果没有区域为100 m×100 m的效果显著；

(2) 在网络区域增大为100 m×100 m时，多路径算法节点的生存期比单路径算法有了较大的延长；更显著的是前几个死亡节点的生存期都有了较大的延后。

因此，本文提出的基于多路径选择的无线传感器网络动态路由选择算法具有较优越的性能，特别是网络节点数不变而网络分布区域增大时更具显著优势。

3 结 束 语

无线传感器网络的动态路由算法是无线传感器网络研究中的热点问题[9]。本文给出了一种基于多路径的无线传感器网络动态路由算法，通过寻找源节点和汇聚节点的多条路径均衡地使用整个网络节点的能量，从而有效地减缓了节点的死亡频率，提高了网络的生命周期，提供了较好的网络性能。但在实际应用中无线传感器网络节点的移动和拓扑结构不断变化，很难维持一个稳定的、端到端的路由技术，还需要在动态条件下对无线传感器网络路由问题进行进一步研究。

[1] 任丰原, 黄海宁, 林 闯. 无线传感器网络[J]. 软件学报,2003, 14(2): 1148-1157.

REN Feng-yuan, Huang Hai-ning, LING Chuang. Wireless sensor networks[J]. Journal of Software, 2003, 14(7):1282-1291.

[2] 崔 莉, 鞠海玲, 苗 勇, 等. 无线传感器网络研究进展[J]. 计算机研究与发展, 2005, 42(1):163-174.

CUN Li, JU Hai-ling, MIAO Yong, et al. Overview of wireless sensor networks[J]. Computer Research and Development, 2005, 42(1): 163-174.

[3] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor networks: a survey[J]. Computer Networks, 2002, 38(4): 392-422.

[4] ELSON J, ESTRIN D. Sensor networks: a bridge to the physical world[M]. Norwell: Kluwer Academic Publishers,2004.

[5] AL-KARAKI J N, KAMAL A E. Routing techniques in wireless sensor networks: a survey[J]. IEEE Wireless Communications, 2004, 11(6): 6-28.

[6] JOONGSEOK P, SARTAJ S. An online heuristic for maximum lifetime routing in wireless sensor networks[J].IEEE Transactions on Computers, 2006, 55(8): 1048-1056.

[7] SHAH R C, RABAEY J M. Energy aware routing for low energy ad hoc sensor networks[C]//Proc IEEE Wireless Communication and Networking Conference (WCNC’02).[S.l.]: IEEE, 2002.

[8] 安辉耀, 卢锡城, 彭 伟, 等. MANET中基于动态拓扑的多路径自适应流量分配算法[J]. 通信学报, 2006, 27(7):20-26.

AN Hui-yao, LU Xi-cheng, PENG Wei, et al. Adaptive traffic distributing bases on dynamic topology for multipath routing in MANET[J]. Journal on Communications, 2006,27(7): 20-26.

[9] PAOLO S. Topology control in wireless Ad hoc and sensor networks[M]. West Sussex, England: John Wiley & Sons Ltd, 2005.

An Algorithm for Dynamic Routing Based on
Multi-Paths in Wireless Sensor Networks

QI Xiao-gang and WANG Dong-fang

(Department of Applied Mathematics, Xidian University Xi’an 710071;State Key Laboratory of Integrated Service Networks, Xidian University Xi’an 710071)

According to the traditional network routing mechanisms, the path with the minimal hops is often chosen to transmit data from source node to destination node. However, frequent communication requests along one path in wireless sensor network result a fact that the nodes on the path prematurely fail with its’ energy exhaustion. In this paper, a routing algorithm based on the multi-path mechanism is proposed, its main idea is to find a path among multi-paths from source node to sink node, This path has the maximized minimal remaining node energy. Compared to single-path routing algorithm, the proposed routing algorithm improves the networks’performance on the nodes’ life time and the data transmission.

multi-path; network survival period; routing; wireless sensor network(WSN)

TP918.91

A

10.3969/j.issn.1001-0548.2010.z1.019

2009 − 11 − 15

国家自然科学基金( 60703118、60674108)；陕西省自然科学基金(2007A01)；ISN国家重点实验室专项基金

齐小刚(1973 − )，男，副教授，主要从事图论与组合最优化、网络优化理论与方法以及路由与交换方面的研究.

编 辑 税 红