无线传感器网络多径路由机制研究

陈良文,李敬兆

(安徽理工大学 计算机科学与工程学院, 安徽 淮南 232001)

无线传感器网络路由协议的设计目的是以合理的方式组织无线传感器节点形成可靠链路，并将数据包从源节点正确发送至目标节点，同时提高网络综合性能、降低网络能耗，延长网络生存时间.无线传感器节点由于其低成本及微型化要求，决定了其在计算、数据存储、能源供应和数据传输等方面的性能非常有限.各个传感器节点需要将采集到的数据传递给基站(base station)或数据收集中心节点(data collection center)，数据链路的可靠性与网络的综合性能密切相关.国内外针对提高传感器网络数据链路可靠性的研究主要分为数据重传、纠错码机制和多路径方法3个方面[1].

本文针对无线传感器网络路由机制及可靠数据链路展开研究，在多径路由算法[2](hybrid energy-efficient distributed clustering approach，HEED)的基础上，提出一种基于移动代理的多路径发现算法 (HEED with mobile agent technology，MAHEED).该算法采用备用链路的思想并对其进行优化，能够有效提高网络的可靠性及生存时间.

1 相关研究

1.1 多径路由机制

无线传感器路由协议根据数据传输路径的方式可以分为单径路由协议(如DD、Rumor、GBR、Gossiping、LEACH、PEGASIS等)和多径路由协议[3](如HEED、Flooding、SPIN、HREEMR等).单径路由算法相对简单，传感器节点通常直接与基站或中心节点进行数据通信，能够有效节省存储空间、减少数据通信量，但是，网络的能耗均衡性、稳定性、可扩展性和容错性差，一旦某些关键性节点失效，就很容易导致网络中出现盲区.图1所示为单径路由的2种形式.

多路径算法通过在源节点与目标节点之间建立多条数据链路，有效地提高了数据传输的可靠性和容错性，对于网络的负载均衡性也有较好的保障.图2所示为多径路由的2种形式.

多径路由机制通过泛洪的方式定期更新路由信息并获取备用链路，防止网络中因节点失效导致数据链路退化，该机制能够很好地实现网络负载平衡并提高数据传输的可靠性.多径路由机制具有以下特点[4-5]：

1) 根据不同的应用需求可以提供不同的数据链路；

2) 为同一种类型的服务能够提供多条数据链路，保证资源利用率及数据传输质量；

3) 各个节点可以根据数据链路的实际情况(如节点剩余能量、数据重传率等)调整路径，从而保证网络的整体能耗均衡性.

1.2 移动代理技术

移动代理(mobile agent)[6]是一种能在异构网络中与其他代理或资源交互的程序，在无线传感器网络中，能够在节点间自主移动并执行特定任务.图3所示为移动代理的系统模型.

移动代理具有以下特征[7]：①具有智能性、自治性、移动性；②具有在不同主机或资源执行特定任务的能力；③移动代理能够保持自身状态，且执行过成功是可持续的.其执行周期如图4.

1.3 HEED路由算法的描述

HEED(a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks)是Younis等[2]提出的一种混合式的分布式成簇路由算法，作为一种典型的分层式多径路由算法，不仅具有良好的可扩展性和实用性，同时，对于降低网络中节点能耗及数据通信量也能起到良好效果.该算法指出，无线传感器网络的3个基本需求为可扩展性、负载平衡和延长网络生命周期.HEED路由算法可以分为簇的建立阶段TCP和稳定数据传输TNO2个阶段，但必须确保TNO远远长于TCP.

簇的建立过程又分为网络初始化阶段和路径建立阶段，经多次迭代完成.首先，网络初始化阶段，根据公式(1)计算各个节点当选为簇头的概率CHprob，并与生成的随机数Random(0,1)比较，确定该节点是否能当选为临时簇头[2].

(1)

其中，Cprob为系统设定的初始簇头比例(通常为5%)，与最终簇头比例无关；Eresidual表示当前节点的剩余能量；Emax表示当前网络节点最大参考能量值(即节点的初始能量值).

然后，在迭代选举簇头阶段，通过将CHprob加倍并与1比较，直到CHprob的值等于1，迭代过程结束，簇头选举完成.

最后，在普通节点选择簇头阶段，各个非簇头节点再根据最小传输功耗least_cost(SCH)选择并加入簇头.簇内成员节点与簇头之间的通信通过AMRP (average minimum reach-ability power)[2]进行衡量：

(2)

其中，minPi为节点vi与簇头间数据传输的最低功耗；M为簇头通信范围内节点的个数.

簇的建立过程结束后，簇头与Sink节点间以多跳的方式建立数据链路，各个簇头使用TDMA的方式为簇内各个成员节点分配时隙，继而进入稳定的数据传输阶段.

图5所示为基于HEED路由算法的网络拓扑结构.

2 MAHEED算法的设计与实现

2.1 网络模型及能量模型[2]

在无线传感器网络中，有数量众多的传感器节点分布在监测区域，本文采用的网络模型与HEED路由算法的网络模型基本一致：

1) 网络中所有的节点都是同构的；

2) 网络节点间的数据链路是对称的，即2个节点间进行数据通信采用相同的传输功率;

3) 网络中的节点可以承担多种任务，这就意味着网络节点的能耗不完全一致；

4) 各个传感器节点无法感知自己的地理位置；

5) 传感器节点一旦部署就无法置换，也无法更换电池或其它部件；

6) 传感器节点具有多级传输功率，且各个节点能够自主调节发送功率.

在无线传感器网络中，采用的能量模型[4]如下：

1) 无线传感器节点发送l bit数据消耗的能量:

(3)

2) 无线传感器节点接收l bit数据消耗的能量

ERX(l,d)=lEelec.

(4)

其中，l为数据包的大小，d为节点间的距离，Eelec为节点收发数据产生的电路损耗，Efs和Emp为功率放大器分别在不同的工作模型下的能耗，d0为传感器节点采用自由空间模型与多路衰减模型的临界距离.

2.2 MAHEED算法设计与实现

本文设计的MAHEED路由算法中的网络初始化、簇头选举及簇的建立过程基于HEED路由算法，在多径路由的发现过程引入移动代理技术.

移动代理能够在节点间自由移动，通过收集周边节点信息，使得节点对局部链路信息的认知得以提升，从而建立优化的多径路由及备用链路.

MAHEED路由算法创建多径路由的步骤如下：

1) 根据HEED路由算法选举簇头节点，网络中其他非簇头节点根据AMRP值选择加入合适的簇；

2) 创建移动代理数据包，并将其在网络节点间传递.移动代理数据包(mobile agent packet,MAP)的格式如图6所示.

Agent_ID：移动代理的唯一标识；

Path_info：区域节点泛洪事件信息得到的路由表；

Path_flag：链路发生改变的标识；

Path_hops：数据链路的跳数；

Points_sum：数据链路的整体能耗.

3) 建立主要数据链路.各个源节点以低速率在网络中试探性泛洪事件信息，通过接收邻居节点发送的信息建立传输梯度[8].当事件信息从各个源节点发送至Sink节点时，就会建立整个网络的传输梯度.

各个节点在处理事件信息时采用以下规则：①若接收到新的事件信息，则将该事件信息转发到邻居节点；②接收到的事件信息与之前转发的事件信息一致，则只记录转发该事件信息的邻居节点而不再转发给邻居节点.

按照以上规则处理事件信息能够防止网络中出现信息环路(loop).

Sink节点会逐渐接收到来自多个邻居节点转发的事件信息，根据转发数据的先后顺序，向各个邻居节点发送主路径增强信息.

4) 建立备用数据链路.在主要数据链路建立的过程中，Sink节点根据邻居节点转发事件信息的先后顺序确定各个邻居节点的优先级，Sink节点根据优先级由高向低的顺序向邻居节点发送移动代理包MAP，继而建立备用数据链路.

图7所示为改进型路由算法MAHEED多径链路建立的过程.具体过程如下.

1) Sink节点根据邻居节点的优先级依次发送移动代理包MAP，各个移动代理包采用Agent_ID唯一标识;

2) 移动代理数据包具有路径增强和否定增强机制.如节点A将移动代理包向最优邻居节点B发送，但此时节点B已经位于主要数据链路，则B节点采用否定增强机制，向A节点发送否定增强信息，A节点则将移动代理包发送至次优邻居节点C，并重复该过程，直至移动代理包传递到源节点；

3) 移动代理包在传递的过程中，需将链路中的节点信息存储在Path_info单元，若节点已经在其他主要数据链路或备用链路中，则通过Path_flag标识位进行标识.Path_hops用于记录Sink节点与各个节点之间的跳数.Points_sum用于记录路径的能量消耗；

4) 源节点最终会接收到多个移动代理包，根据移动代理包中的数据，能够得到多条备用数据链路，根据数据链路跳数最优、能耗最小的规则就能确定备用数据链路的优先级；

5) 多径数据链路建立完成之后，网络进入稳定数据通信阶段，位于监测区域内的无线传感器节点将采集到的环境信息高速传递至Sink节点，同时，在备用数据链路上进行低速率数据传输，保证备用数据链路的可用性.一旦主要数据链路失效，就选用最优备用链路继续传输数据，保证数据传输的可靠性.

3 实验仿真与性能分析

本文采用Matlab软件将改进型算法MAHEED与HEED路由算法在网络生存时间、数据链路可靠性等方面的性能进行比较，环境参数如表1.

表1 仿真环境参数

图8为仿真网络中Sink节点及簇头节点的分布情况及数据链路的权值.

在仿真环境中，将HEED路由算法与MAHEED算法进行比较，在网络生存时间方面，MAHEED算法由于采用备用数据链路机制，当主要数据链路发生变化时，立即启用最优备用数据链路，保证了网络中各节点的能耗均衡性，因此，网络生命周期提升约70%.图9为HEED路由算法与MAHEED算法网络生命周期的比较.

网络自适应性(networks adaptability)与网络整体性能具有较密切的关系，随着网络中失效的传感器节点越来越多，如果网络依旧保持较高的自适应性，意味着网络抗毁性越强、可靠性越高.图10所示为HEED路由算法与MAHEED算法在网络自适应率与节点失效率的关系.

通过比较发现，改进型算法MAHEED随着网络节点失效率的提高，网络自适应率较HEED路由算法有较大提升.

4 结语

本文基于典型分簇式多路径路由协议HEED及移动代理技术(mobile agent)针对无线传感器网络在实际应用中对数据链路高可靠性的要求，设计了一种基于移动代理和备用数据链路的多径路由机制MAHEED，通过移动代理在网路中按照一定规则进行移动，收集网络节点信息并建立主要数据链路和备用数据链路，进而确定备用数据链路的优先级，一旦网络中的数据链路发生变化，随即启用最优备用数据链路.仿真实验显示，改进型路由算法MAHEED较HEED路由算法，有效提高了网络自适应率、数据链路可靠性和网络生存时间.本文设计的多径路由机制在网络数据链路可靠性要求较高的应用中具有较强的实用性，但是，网络中节点间传输移动代理包会增加额外开销，如何确保移动代理包数据量最小以及选举周期的最佳时间是下一步研究的方向.

参考文献:

[1] SHIH H C, HO J H, LIAO B Y, et al. Fault node recovery algorithm for a wireless sensor network[J].IEEE SENSORS JOURNAL, 2013,13(7): 2683-2689.

[2] YOUNIS O, FAHMY S. HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks[J].Mobile Computing, IEEE Transactions on, 2004, 3(4): 366-379.

[3] CHEN Yun-xia, ZHAO Qing. On the lifetime of wireless sensor networks[J]. IEEE Communication Letters, 2005, 9(11): 976-978.

[4] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J].Wireless Communications, IEEE Transactions on, 2002, 1(4): 660-670.

[5] 宗平,龚瑜.WSN中多路径路由协议算法的改进研究[J].计算机技术与发展,2012,22(8):34-38.

[6] MINAR N, KRAMER K H, MAES P. Cooperating mobile agent for dynamic network routing[J].Software Agent for Future Communications Systems, 2004,3(4):366-378.

[7] MATSUO H, MORI K. Accelerated ants routing in dynamic networks[C]//2nd Int. Conf. on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing. 2001:333-339.

[8] DORIGO M, CARO G D. The ant colony optimization meta-heuristic[C]//New Ideas in Optimization. London: MoGraw Hill, 1999:11-32.