基于位置感知和代理的WSN多径路由方案

汤 震，蔺 莉

(黄淮学院 信息工程学院，河南 驻马店 463000)

基于位置感知和代理的WSN多径路由方案

汤 震，蔺 莉

(黄淮学院 信息工程学院，河南 驻马店 463000)

针对无线传感器网络(WSN)中多径路由的可靠性和能量效率问题，提出了一种基于代理和位置感知的多径路由发现方案(LABMR)。事件节点根据位置信息，动态寻找其到Sink节点之间的特殊中间节点，来构建多径路由。利用移动代理来收集多径路由的局部拓扑结构信息，Sink节点根据代理收集的路由参数来计算路径权值，以此选择最优不相交路径。同时，对于信息的重要性差异，Sink节点选择单条或多条路径来传输数据，在保证传输可靠性的同时减少能耗。与现有的基于代理的多径路由(ABMR)方法相比，LABMP在数据包投递率、能量消耗、额外开销和延迟方面具有更好的性能。

无线传感器网络；多径路由；网络代理；位置感知

无线传感器网络(Wireless Sensor Network，WSN)是由多个静态传感器组成，通过无线介质连接，执行物理世界的分布式感知、数据处理和决策[1]。在传统的WSN中，传感器节点周期性地收集数据，并通过使用多跳通信方式报告给Sink节点。使用传统数据收集和处理方法可能会导致一些额外能量消耗、冗余的数据传输、增加延迟和带宽开销等现象。WSN的关键问题是网络的生命周期和传输可靠性，这主要是依赖于传感器节点的能量和通信机制[2]。

由于WSN中节点资源异构性、通信链路不对称等因素，导致数据链路容易发生断裂。为了保证可靠的数据传输，多径路由机制被广泛应用，其利用数据链路冗余方式传输数据，有效地提高了通信可靠性[3]。

1 相关工作

文献[4]描述了一种基于代理的多径路由(Agent Based Multipath Routing，ABMR)发现方案。ABMR考虑了传感器节点的一些参数，如剩余能量、距离、信道可靠性来计算从源节点到Sink节点的多径路由。从源节点触发移动代理，在传感参数的基础上，在网络中移动直到到达目的节点。每个节点上的移动代理都会移动到邻居节点来收集信息，用来在邻居节点中选择出最好的节点。一旦从邻居中选择出了最好节点，则这个最好邻居节点触发自身的移动代理到它的邻居，重复执行上述任务，选择最佳节点直到到达Sink节点。Sink节点根据代理带来的路径信息来计算多径路由。然而其存在着一些缺陷，要计算多径路由，源节点需要同时发出多个代理，ABMR中的代理从源节点到目的节点的过程中，要收集很多节点的信息，几乎遍历了整个网络。这就导致大量的额外能量消耗。

对于一些现有的多径路由技术存在的缺点，如在路径发现和路径建立过程中缺乏智能，中继节点选择机制的灵活性较小，计算多径路由的能量消耗较大，对关键信息的传输缺乏鲁棒性机制等。本文提出一种基于位置感知的代理的智能多径路由发现机制(Location aware and Agent Based Multipath Routing，LABMR)。利用传感器位置信息寻找特殊中间节点来构建多径路由，并触发代理在路径上移动，来收集多径路由的局部拓扑结构信息，Sink节点根据这些信息，计算出最优不相交路径。并根据事件重要性，选择一条或多条路径传输数据。

提出的LABMP和ABMR的根本区别如下：1)LABMP只使用局部拓扑信息来寻找从源到Sink节点的多条路径；2)建立了完善的代理机构，Sink节点能够根据代理收集的信息寻找最优路径，可靠传输关键信息；3)使用基于GPS(全球定位系统)的位置信息，能够更准确地计算多条路径。通过实验，与ABMR方法相比，LABMP在数据包投递率、能量消耗、额外开销和延迟方面具有更好的性能。

传感器节点位置信息的获取是通过内置GPS模块实现。为了尽可能减少成本，本文只在少量传感器节点上使用GPS定位模块，其他节点通过节点之间的通信来估计自己的位置。相比于GPS模块的成本，位置信息对整体网络性能更具价值。

2 提出的LABMR方案

2.1 相关概念

提出的LABMP方案中的主要名词如下：

事件节点(Event node)，即在事件影响区域，用来检测事件的传感器节点。事件节点能够触发到Sink节点的路由发现过程。节点会向其他邻居节点宣布自己为一个事件节点，防止其他节点去事件影响区域重复检测事件[5]。

中点(Midpoint)，是连接事件节点和Sink节点直线(X轴)上的中间位置点。若不存在严格中点，可将离中间位置最近的节点为中点。

特殊中间节点(Special intermediate nodes)，在事件和Sink节点之间，近似位于中点垂直上方和下方的节点。

上升角度(Rising Angle)，是指事件节点和X轴上方的特殊中间节点之间的连线与X轴的角度。

下降角度(Falling angle)，是指事件节点和X轴下方的特殊中间节点之间的连线与X轴的角度。

跳数(Hop count)，是指事件节点到Sink节点路径的中继节点总数。

2.2 网络环境

本文中的网络环境如图1所示，由多个具有数据感知能力的微小传感器节点和Sink节点组成。当传感器节点检测到一个事件时，它们会将数据通过无线多跳通信方式发送到Sink节点[6]。本文假设网络中的所有节点(传感器节点和Sink节点)都是静态的，且在初始部署阶段，所有的传感器节点具有相同的能量。在本文所提出的LABMP中，假设只有少量传感器节点具有GPS功能，其余节点根据具有GPS节点的位置，使用定位算法来估算自己的位置，以此来降低系统的成本。每个传感器节点都具有一个代理机构。

图1 WSN网络结构

2.3 多径路由发现

2.3.1 路径参数

本节描述了本文方案中所用到的路径参数，包括链接和路径的效率、能量比率和跳距离因子。

设C是离散信道的容量，B是信道的比特率，Ei是在链路i上传输1 bit数据消耗的总能量，SNR是信噪比。信道i的容量计算公式为[7]

Ci=Blb(1+SNR)

(1)

设定Et为1 bit数据每传输d距离所消耗的能量，则Ei可用下式计算

Ei=Et×d

(2)

链接效率(Leffi)计算公式为

(3)

路径效率(Peff)为整条路径上的n个链接效率的最低值，表达式如

Peff=min{Leff1,Leff2,…,Leffn}

(4)

路径能量比率(Eeff)为每条从事件节点到Sink节点路径中节点最小剩余能量和最大剩余能量之比。设定ER(1)到ER(n)为路径上n个中间节点的剩余能量。路径上n个节点的最小(ERmin)和最大(ERmax)剩余能量表达式如式(5)，式(6)所示，Eeff表达式如式(7)所示。

ERmin=min{ER(1),ER(2),…,ER(n)}

(5)

ERmax=max{ER(1),ER(2),…,ER(n)}

(6)

(7)

一条路径的跳距离因子(Hdf)表达式如式(8)所示，其中，事件节点到Sink节点路径的欧式距离为Pd，路径上跳数的总和为Phc

(8)

2.3.2 局部拓扑结构发现

图2显示了从事件节点到Sink节点的多径局部拓扑结构发现过程。S1和S7分别是事件节点和Sink节点。以S1和S7的直线连接为X轴，S2，S4和S6节点近似位于X轴上。根据GPS位置信息，设定以(xe,ye)和(xs,ys)分别作为事件节点和Sink节点的位置坐标，根据式(9)、式(10)找出S1到S7直线上的中间位置点(中点)为节点S4，其坐标为(xmid,ymid)。

(9)

(10)

S11,S22：特殊中间节点 S7：Sink节点 ⊖r1～⊖r11:上升角度 S1：事件节点 S2～S6：传感器节点 ⊖f1～⊖f11：下降角度图2 WSN中局部多径发现模型

(11)

y″mid=ymid-n×R

(12)

式中：n和R分别是中点的节点度和传输范围。

每个节点处的上升和下降的角度计算公式如

(13)

式中：θr1是上升角度，同理可得下降角度θf1表达式为

(14)

在下面的描述中，代理会在这3条路径上移动只到Sink节点，以此来收集路径节点和邻居的参数信息，这些信息将被Sink节点用来构建局部拓扑结构和发现多路径。

2.4 代理机构

本文方案中，为路径发现和路径计算设置了一组静态和动态代理，并为普通传感器节点和Sink节点的构建代理机构。本节介绍了提出的代理机构和相应的代理。

2.4.1 普通节点代理机构

本文中普通节点代理机构是由节点管理者代理(NMA)、路径发现代理(PDA)和多径路由知识库(MKRB)组成，其中NMA是静态代理，PDA是移动代理。节点代理机构和它们之间的相互作用如图3所示。

图3 普通节点代理机构

节点管理者代理(NMA)：是一个静态代理，用来检测可有信息，如信号强度、传输范围、剩余能量，并计算链路效率，最小和最大剩余能量比和跳距离等参数。当检测到事件时，NMA开始根据位置信息，计算中点和特殊中间节点(SINs)。然后，NMA创建PDA和MKRB，使用MKRB更新路径信息。运行过程中，NMA会根据节点剩余能量，使节点进入睡眠或活动模式。NMA会和邻居节点的NMA进行交流，以此得到邻居节点信息，如节点ID、位置，并更新MKRB。

路径发现代理(PDA)：一旦检测到事件，事件节点的NMA会创建一个事件节点的PDA(移动代理)，并复制成3个。3个PDA在3条路径上移动，第1个PDA几乎在X轴上移动，直到到达Sink节点；第2个PDA先以上升角度移动，到达SIN节点后，再以下降角度迁移，直到到达Sink节点。第3个PDA先以下降角度移动，到达SIN节点后以上升角度迁移。最后，PADs将收集的局部拓扑信息传递给Sink节点。

多径路由知识库(MKRB)：是基于网络路径相关信息建立的知识库，通过代理可以读取和更新。它包括节点ID、活动/睡眠模式、剩余能量、邻居节点之间的距离、Sink节点ID、SINs的ID、Sink节点和SINs的位置信息、事件感知时间、信号强度、可用带宽、自身和Sink节点之间的距离、上升和下降的角度等信息。它也保存着邻居节点的信息，如节点的ID和位置信息。

2.4.2 Sink节点代理机构

Sink节点代理机构由Sink管理者代理(SMA)、路径设置代理(PSA)和Sink知识库(SKB)组成。Sink节点代理机构的组成以及之间的相互作用如图4所示。

图4 Sink节点代理机构

Sink知识库(SKB)：是用于Sink节点计算路径的信息知识库，能够被SMA、PDA和PSA读取和更新。它存储了与网络有关的信息，包括路径长度、跳总数、剩余能量、每条路径剩余能量的最小和最大值、可用带宽、信道容量、到事件节点的可用路径数量、路径权重因子等。

Sink管理者代理(SMA)：是存在于Sink节点中的一个静态代理，检测网络相关信息。基于收集的信息，如剩余能量、可用带宽、每条路径的跳总数和路径距离，SMA能够计算出从Sink节点到事件节点的不相交路径。同时计算每条路径的路径权重因子，根据事件的重要性，决定选择一条或多条路径进行传输。根据路径权重因子决定路径的优先级，如果事件是重要的，则选择出多条路径，并使PSAs在这些路径上移动到事件节点。为了减少开销，本文考虑最多选择3条最优不相交路径。如果事件是不重要的，则只选择一条最优路径给PSA移动，当事件节点收到PSA时，开始传输信息数据。

路径设置代理(PSA)：是通过SMA构建的移动代理，其从Sink节点的SKB获得路径信息，从Sink节点移动到事件节点来检查路径上的节点。在到达事件节点后，它根据路径信息更新事件节点的MKRB。

2.4.3 示例场景

本文方案的一个应用示例场景如图5所示。图中数字表示的本文方法步骤的序号，执行步骤如下：

1)传感器节点S1检测到一个事件时，事件节点的NMA启动到Sink节点的路径发现过程。

2)NMA产生PDA，PDA产生3个PDA复制品，并计算得出特殊中间节点(S11和S12)和移动的角度；3个PDA按3条路径移动，直到它们分别到达Sink节点、S11和S12，在迁移过程中，它们收集路径信息。

3)PDA的两个复制品在S11和S12处分别改变移动的角度，只到Sink节点并传递路径信息给Sink节点。

4)Sink节点的SMA计算到事件节点的不相交多路径，根据每条不相交路径的权重因子来设定优先级。

5)根据事件的重要性，SMA触发单条或多条最佳路径上的PSA，并移动到事件节点。

图5 LABMP网络示例场景

3 实验及分析

为了评估本文算法的有效性，利用MATLAB仿真各种网络环境，将本文方案与现有的基于代理多径路由的ABMR方案进行比较。

3.1 仿真模型

网络模型：本文考虑一个l×b(平方米)区域的WSN网络，由N个随机布置的静态节点组成。设定以一跳距离相互连接的节点的信道带宽为BWsingle-hop，本文假设所有信道都是可用的。仿真网络参数如表1所示。

表1 仿真参数

传播模式：本文使用一个传播常数为β的自由空间传播模型，WSN节点的传输范围为R。假设在任何给定的时间上，节点传输一个数据包所需的能量为Eu(焦耳)，节点的R正比于Eu，R=CEu，其中比例常数C取决于传输介质常数β[9]。

3.2 性能参数

本文通过以下几种性能参数来比较本文方法和ABMR算法。

数据包投递率(PDR)：指接收和发送的数据包的比例。

能耗(EC)：指在网络中路径发现、路径设置和事件节点向Sink节点发送数据包所消耗的总能量，以毫焦耳(mJ)表示。

延迟(Delay)：从事件节点传输数据到Sink节点的总时间，以毫秒(ms)表示。

额外开销(Overhead)：指获得可用的通信路径所需的能量开销。

3.3 实验结果

3.3.1 数据包投递率和能量消耗

图6显示了在给定数量节点和传输范围下，两种算法的数据包投递率(PDR)。在ABMR和LABMP中，PDR都随着节点数量的增加而减小，随着通信范围的增加而增加。然而，相比于ABMR，LABMP具有更好的PDR。当节点数量增加时，节点信息数据的量也随之增加，这就导致需要更多的带宽，因此，可用带宽可能不足以来成功传输数据，使得PDR下降。LABMP方案提供较好的可用带宽，这是因为它在可用路径计算中考虑了链接效率，均衡了信道带宽。LABMP在较高传输范围下的PDR表现更好，这是因为减少了孤立节点的数量。

图6 不同节点数量和传输范围下的数据包投递率

图7描述了在给定数量节点和传输范围下，网络运行单位时间的总能量消耗。随着节点数量和传输范围的增加，ABMR和LABMP的能量消耗都会增加，然而LABMP具有较好的性能。能量消耗主要由收集局部拓扑结构信息、路径计算、路径信息发送和接收形成。提出的LABMP方案具有较少的能量消耗，这是因为它在计算路径时，考虑了局部拓扑、跳距离因素和能量信息。而ABMR只使用基本拓扑信息来计算路径。

图7 不同节点数量和传输范围下的能量消耗

3.3.2 延迟和额外开销

图8描述了在给定节点数量和通信范围下的延迟。由于节点数量和通信范围的增加，收集和计算多条不相交路径的时间需求也增加。LABMP比ABMR需要较少的时间，因为LABMP只利用局部拓扑结构信息来寻找路径，而ABMR则利用全局拓扑结构信息，需要更多时间来收集信息。

图8 不同节点数量和传输范围下延迟

图9和图10显示了在给定节点数量和通信范围下，传输关键和非关键数据时的额外开销。开销随着通信范围和节点数量的增加而增加。LABMP比ABMR具有较少的开销，因为LABMP对于关键信息通信，选择多径路由来实现可靠传输，而对于非关键信息通信，只选择具有最高权值因子的单一路径来传输信息。由于LABMP利用代理在设定的方向上移动来获得局部拓扑结构信息，寻找多径路由所需的通信量比ABMR少。

图9 不同节点数量下的开销(关键信息)

图10 不同节点数量下的开销(非关键信息)

4 小结

本文提出了一种基于代理和位置感知，由事件驱动的多径路由发现方案。事件节点根据位置信息，动态寻找事件节点和Sink节点之间的特殊中间节点，来构建多径路由。并利用移动代理来收集多径路由的的局部拓扑结构信息，并发送给Sink节点，Sink节点根据链接效率、能量比率和跳距离因子来计算路径权值，以此选择最优不相交路径。对于关键信息，Sink节点通过多条较优路径发送信息给事件节点，保证传输可靠性；对于非关键信息，Sink节点只利用具有最大权值的单路径发送信息。由于LABMP只利用局部拓扑信息构建路由，不需要了解全局节点的信息，从而节省了带宽和能量。与现有的ABMR方法相比，本文提出的LABMP在数据包投递率、能量消耗、开销和延迟方面具有更好的性能。

[1] 杨银堂，高翔，柴常春，等. 一种 WSN 中的能耗优化动态路由算法[J].西安电子科技大学学报，2010，37(5)：777-782.

[2] 刘新华，李方敏，旷海兰，等. 基于能量异构的无线传感器网络分布式成簇算法[J].小型微型计算机系统，2010，34(1)：26-31.

[3] 卢莉萍，黄飞，张宏，等. 基于网络编码的传感器网络多径路由模型能量分析[J].南京理工大学学报：自然科学版，2010，34(4)：124-130.

[4] RAMADAN R A. Agent based multipath routing in wireless sensor networks[J].IEEE Wireless Communications，2009，11(6)：63-69.

[5] 冯江，茅晓荣，吴春春.一种能量均衡有效的WSN分簇路由算法[J].计算机工程，2012，38(23)：88-91.

[6] LUO R C，CHEN O. Mobile sensor node deployment and asynchronous power management for wireless sensor networks[J]. IEEE Trans. Industrial Electronics，2012，59(5)：2377-2385.

[7] KATIYAR V，CHAND N，SONI S. A survey on clustering algorithms for heterogeneous wireless sensor networks[J].International Journal of Advanced Networking & Applications，2011，2(4)：122-129.

[8] 王建生，曹叶文. 基于动态组播代理的移动组播协议[J].计算机工程，2010，36(1)：87-90.

[9] MIAO G W，HIMAYAT N，LI G Y. Energy efficient link adaptation in frequency-selective channels[J].IEEE Trans. Commun，2010，58(2)：146-152.

[10] DI C G，DORIGO M. AntNet: distributed stigmergetic control for communications networks[J]. Journal of Artificial Intelligence Research，2011，19(3)：317-365.

汤 震(1983— )，硕士，讲师，主要从事软件工程开发、数据挖掘等研究；

蔺 莉(1982— )女，讲师，硕士，主要从事软件工程开发、数据挖掘等研究。

责任编辑：许 盈

Location Aware and Agent Based Multipath Routing Scheme in WSN

TANG Zhen, LIN Li

(DepartmentofInformationEngineering,HuanghuaiUniversity,HenaZhumadian463000,China)

To solve the problem of the reliability and energy efficiency of multipath routing in WSN, a multipath routing scheme based on location aware and Agent (LABMR) is proposed. The event node searches for special intermediate nodes between Sink node and event node according to location information, in order to build multipath routing. LABMR uses the mobile agents to collect the partial topology information of multipath routing, which will be used by Sink node to compute the path weight, so as to find out the optimal disjoint paths. Meanwhile, Sink node selects a single path or multiple paths to transmit information according to its importance, to ensure transmission reliability as well as reduce energy consumption. Compared with ABMR scheme, LABMP has better performance in packet delivery ratio, energy consumption, overhead and latency.

wireless sensor network; multipath routing; network agent; location aware

【本文献信息】汤震，蔺莉.基于位置感知和代理的WSN多径路由方案[J].电视技术,2015，39(11).

河南省教育厅科学技术研究重点项目(14B520036)

TP39

A

10.16280/j.videoe.2015.11.031

2014-12-20