WSN中基于势能场的多策略路由协议

基金项目：国家自然科学基金课题(60971102、60773138)

    自组织路由协议是无线传感器网络研究领域的一个基本课题。目前已有的多数典型路由算法[1-10]在实现寻址这一基本功能的前提下，通过优化路由协议的能耗来延长网络生命周期，对于资源受限的网络节点无疑是有针对性的，但片面强调低功耗的设计目标则会限制路由协议提供其他附属功能。为突破这一固有认识与理解，本文充分利用无线传感器网络中节点密集冗余的特点，以及数据分组空间分布“多对一”的向心性特征，借用物理学中势能场的概念，选择适当的网络状态参数，构造复合虚拟势能场驱动数据分组沿着势能梯度变化最大的方向移动，最终回到Sink节点，实现路由基本功能。在这一开放路由实现框架下，通过调整复合虚拟势能场的组成元素以及合理的参数配置，为路由协议附加各种有利于实现其他优化目标的品质与属性，如能耗均衡、拥塞避免、支持服务质量保障和利于数据聚合等，最终在无线传感器网络中实现多策略的路由协议设计、服务工程应用多样性的要求。

    基于以上考虑，我们研究设计了一种开放路由框架，并在该框架下相继实现了多个具有不同属性的路由协议，如能量均衡路由协议(EBRP)、感知流量的动态路由协议(TADR)、区分服务的动态路由协议(DDR)以及动态路由支持的数据聚合协议(DASDR)，本文使用基于势能场的提供实时传输的路由协议(PRTR)作为例子，来介绍在该框架下设计路由协议的具体步骤和方法。

1 开放路由框架设计
    图1给出的是典型无线传感器网络(WSN)拓扑结构的局部图，工作区域内的网络节点采集数据，通过中间节点的中继，以多跳方式将携带观测数据的分组汇集到Sink节点，因此在WSN中，通信的“多对一”特性和数据分组在空间分布的向心性是明显的。为探测网络拓扑结构，Sink节点广播管理分组，接收到该分组的节点自然认为它与Sink节点仅距1跳之远，我们可将其定义为节点的深度，即Depth=1。之后，Depth=1的节点可修改管理分组中的记录，继续广播分组，接收到分组的节点的Depth=2，依次类推，节点容易得到它们各自的深度值。为直观解释势能路由协议的基本原理，我们可直接将节点的Depth值定义为虚拟势能场中该点势函数的大小，得到如图2所示的势能场。

    如果我们将这个用节点深度值构造的虚拟势能场形象类比为“碗”，而将网络中的分组视为附着在碗壁上的“水滴”。在重力场的作用下，水滴将沿特定路径滑向碗底。如果能将物理学中的场强、势差、作用力和梯度等场论的基本概念恰当引入到虚拟场中来，等同于“水滴”的数据分组就完全有可能在虚拟势能场“作用力”的驱使下，沿着势能梯度变化最大的方向移动，最终回到位于“碗”底的Sink节点，实现路由的基本功能。当然，自然界中水滴沿碗壁下滑受自然规律的约束，也就是说重力场中势与力的关系是受客观规律约束。我们虽然可以任意定义虚拟势能场中各基本参量的关系，但利于路由协议优化目标的实现应该是具体研究过程需要遵从的基本原则。基于势能场的路由协议有两个显见的优点是非常适合WSN特点的：(1)数据分组空间分布中“多对一”的向心性使我们只需要在整个网络中为路由协议的实现维护一个虚拟势能场；(2)势能梯度变化最大的方向只取决于相邻节点间的势差，这意味着在势能路由协议中节点仅仅需要局部信息即可做出路由决策。对于大规模的无线传感器网络，无需全局网络拓扑结构与状态参数的分布式路由协议具有较小的实现开销与较好的可扩展性。

    至此，我们仅仅通过“隐喻”手段简单直观论述了如何利用“深度势能场”实现WSN路由的基本功能，即发现至Sink节点的路径。实际上，在“深度势能场”的独立作用下，我们只能发现跳数最小的路径。如果停留于此，我们在WSN路由协议设计中引入势能场概念的价值就相当有限。所幸的是，我们可以在“深度势能场”上叠加用其他网络参数构造的虚拟势能场来实现多策略路由。譬如，我们可以用节点上的队列长度作为网络负载状态的观测变量，构造动态虚拟势能场，采取线性组合等合理方式叠加到基本的“深度势能场”上，形成复合势能场共同驱动分组在网络中的移动。图2中的局部小“凸起”暗示此处节点上的队列出现了明显的积累，已成为“热点”，并有可能导致拥塞。复合势能场将动态改变路由，疏导后来的分组绕开此区域，就如同下滑的水滴会绕开碗壁上的小凸起一样自然。如此，路由协议将在实现寻址这一基本功能的前提下，为平衡负载、缓解拥塞贡献力量。相似地，我们也可以用节点的剩余能量等物理参数来构造动态虚拟势能场，设计出能耗均衡的路由协议。

    如果我们在平滑碗壁的某个方向上附加的电场，带电水滴和非带电水滴将会沿不同轨迹滑动。这一现象进一步启发我们可以将不同应用生成的数据分组通过报头标志域加以区分，在复合虚拟势能场中与不同势能场作用，产生不同运动轨迹，服务于不同的优化目标。譬如，让敏感延时的分组沿最短路径运动提高实时性，让敏感丢失但对延时无特殊要求的分组在网络中迂回，避免重载链路上缓存溢出导致的分组丢弃，提高监测数据的完整性和保真度。基于这一基本思路，我们可以为WSN设计出支持区分服务质量保障的势能路由协议。相似地，通过势能路由协议我们还可以有目的改变不同应用分组的运动轨迹，强化分组在空间与时间分布上的相关性，支持数据聚合协议设计，提高聚合效果。

2 基于势能场提供实时传输的路由协议

2.1 基本思想
    对于实时应用程序来说，路由协议的首要目标是保证来自这些应用程序的数据分组能够获得最小化的端到端传输时延[11-12]。为满足这些要求，我们在上述框架下实现了一个提供实时传输的路由协议PRTR。PRTR实现了与TADR[13]不同的路由策略，它把对时延敏感的分组始终放在最短路径上进行传输，将其余的分组分散到别的空闲路径上进行缓存，等待网络拥塞减轻后再继续转发。PRTR路由策略如图3所示。这样，PRTR既最小化了实时性分组的端到端延迟，又能同时缓解网络可能出现的拥塞，提高全网的吞吐率。

2.2 模型设计
    参考文献[14]引入的势能场的模型，我们在PRTR中，建立了节点深度和节点队列长度两个势能场，节点深度势能场定义如下，Vd(v )表示在节点v处的深度势能(标量)值：

    而Depth(v)则表示节点v 的深度值，即距离Sink节点的跳数。图4给出了深度势能场的函数曲线，在距离Sink较远的节点处，深度场不是主导因子，这有利于非实时数据包被分散到旁路上以让路给对时延敏感的分组，在越靠近Sink的地方，深度势能场逐渐成为主导因子，这有利于保障实时数据包始终沿着最短路径进行传输，最小化其端到端延迟。

    深度势能场的作用是保障数据包始终朝向位于碗底的Sink节点流动，如果拥塞发生，则需要能感知拥塞状况的另一个势能场的介入，才能把非实时性分组有效地分散到空闲或轻载的旁路上去。由此，队列长度势能场定义如下：
Vq (v)=Q(v)

    根据队列长度这个参数建立的势能场能感知网络的实时流量情况，将分组适当的转发到轻载或空闲的路径上去，以缓解网络的拥塞。得到这两个独立势能场后，我们通过线性叠加的方式形成了一个混合势能场，α是调整路由策略的关键变量：
Vm (v)=(1-α)Vd (v)+αVq (v)

    接下来，我们需要在场中引入“力”的概念，最终由“力”来引导数据包的流向。所谓势能场中的力，是位于势能场中的两个节点间的势能差与距离的比值，由于我们只在一跳邻居节点之间考虑转发问题，因此距离可以统一设定为1，那么节点v和节点w之间的力可以通过如下的公式来计算：
Fm (v,w)=(1-α)Fd (v,w)+αFq (v,w)

    势能场最大力规则：场中的每个数据包都将沿着其所承受的最大的“力”的方向被转发(至下一跳的邻居节点)，即：
w 点是v的下一跳节点，当且仅当Fm (v,w)=max{Fm (v,x),?坌   x∈nbr (v)}

2.3 协议实现
    在协议的具体实现中，我们首先在每个分组的头部都增加了一个标志位(Flag)，用以区分对时延敏感的数据包和其他数据包。对于实时分组(Flag为1)，α参数被设为0，混合势能场退化为了深度势能场，PRTR相应退化为了最短路径算法，这样能够最小化它们的端到端传输延迟。对于其他分组(Flag为0)，我们则用混合势能场来传输(0<α<1)，既保证了它们朝向Sink流动，又使得它们在最短路径发生拥塞时能够被转发到轻载的节点上去，即被缓存到旁路中等待后续的发送。

    根据PRTR的势能场模型，我们分析了它能够提供实时传输和缓解拥塞的两个固有属性。
属性1：对于实时性分组，节点只会向下一深度的节点(即深度减1)转发分组。即对时延敏感的数据包只会沿着最短路径进行传输。

    属性2：对与非实时性分组，当同深度的两个节点的队列长度差小于一个关于α的函数时，分组即能在同深度的节点间进行转发。即对时延不敏感的数据包在网络发生拥塞时将被缓存到别的路径上，在最短路径上让路给实时分组。

    关于属性2，我们还可以总结出一个简单的推论，即当α较大时，非实时性数据包更容易被分散到旁路上，对时延敏感的分组将获得更低的端到端平均传输延迟。

    为了进一步减小实时数据包的排队延时，我们还使用了叫做优先级队列的辅助机制，使得在同一节点的缓冲队列中，对时延敏感的数据包能够被调度到队列的前端，先于非实时数据包被转发。

2.4 仿真实验
    我们在TOSSIM[15]仿真平台上实现了PRTR路由协议，并进行了一系列的仿真实验。我们选取了多个路由协议进行对比，包括TADR和典型的WSN实时路由协议(SPEED)。同样基于TOSSIM我们复现了SPEED协议有关实时性的核心算法部分。

    为了进行对比实验，我们设立了统一的仿真环境。我们使用3个不同参数的PRTR协议，以及TADR、SPEED进行了实验。主要考察了在5种路由算法下，数据包的端到端平均延迟(图5)以及网络吞吐量(图6)等性能指标。实验结果表明，PRTR能够提供比SPEED更优的实时传输功能。α参数的设定和优先级队列机制的使用都将极大的影响PRTR的性能。α较大时，非实时分组将更容易被驱散到旁路上进行缓存，因此它们的传输延迟将增大，而实时性分组的延迟会减小，这也是与之前提出的推论相吻合的。如果使用优先级队列机制，实时数据包的端到端平均延迟将大大减少。此外，PRTR能够像TADR一样提供较高的全网吞吐量，但α较大的PRTR协议将因此带来更高的系统能量开销。

4 结束语
    路由协议设计是WSN研究中的一个基本问题，得到了广泛的关注，并且已经产生了不少典型的策略和算法。相比而言，本工作的创新之处在于：

    (1)充分利用WSN固有的“多对一”业务模式和流量分布的向心性特征，通过“隐喻”手段将物理学中势能场的概念引入路由协议研究中，提出了一种开放的分布式路由协议设计框架。

    (2)结合研究与应用的发展，重新审视了过分强调低功耗对WSN路由协议研究产生的影响，提出了多策略路由设计的指导原则。

    (3)设计能耗均衡、敏感流量、支持区分服务质量保障和利于数据聚合等一系列富有特色的多策略路由协议。开放的势能路由协议框架便于用统一的结构进行实现，增加了工程实践的可行性。

    我们的仿真结果表明，PRTR为实时应用程序提供了良好的实时传输功能，同时保证了较高的全网吞吐量。总的来说，PRTR路由协议具有以下几个特点：

    (1)PRTR是一个数据集中式的算法，而不是一个点对点的路由协议，它只把数据包朝向Sink节点转发。

    (2)无线传感器网络(WSN)的固有属性为势能场概念的引入提供了可操作的空间，在WSN中只存在一个目的节点(Sink)，只需要建立一个以Sink为中心的势能场。尽管在实际协议中，我们为两种不同的应用程序(实时\非实时应用)建立了两个不同的虚拟势能场，但由于我们所使用的路由信息(节点深度和队列长度)都只是局部信息，不需要在整个势能场范围内洪泛多次，因而极大地减小了额外的开销。

    (3)PRTR具有良好的可扩展性。节点深度和队列长度这两个局部信息，只在一跳之内的邻居节点间进行交换，这种分布式的路由算法降低了实现、部署和扩展的难度。

    (4)PRTR很好地满足了实时传输的需求，同时尽量避免了拥塞所引起的大量丢包发生，保证了全网的高吞吐率。

5 参考文献
[1] POTHURI P, SARANGAN V, THOMAS J. Delay-constrained, energy efficient routing in wireless sensor networks through topology control[C]// Proceedings of the 2nd IEEE International Conference on Networking, Sensing and Control (ICNSC’06), Apr 23-25, 2006, Lauderdale, FL,USA. Piscataway, NJ,USA:IEEE, 2006:34-51..
[2] AHMED A A, FISAL N. A real-time routing protocol with load distribution in wireless sensor networks[J]. Computer Communications, 2008,31(14):3190-3203.
[3] LU C, BLUM B M, ABDELZAHER T F, et al. Rap: A real-time communication architecture for large-scale wireless sensor networks[C]// Proceedings of the 8th IEEE Real-time and Embedded Technology and Applications Symposium(RTAS’02),Sep 25-27, 2002, San Jose,CA,USA. Piscataway, NJ,USA:IEEE, 2002:55-66.
[4] ZHAO J, GOVINDAN R. Understanding packet delivery performance in dense wireless sensor networks[C]// Proceedings of the 1st International Conference on  Embedded Networked Sensor Systems (SenSys '03), Nov 5-7, 2003, Los Angeles, CA, USA. New York, NY,USA: ACM,2003: 1-13..
[5] DECOUTO D, AGUAYO D, BICKET J, et al. A high-throughput path metric for multi-hop wireless routing[C]// Proceedings of the  9th Annual International Conference on Mobile Computing and Networking,Sep 14-19,2003,San Diego,CA,USA. New York, NY,USA:ACM, 2003:134-146.
[6] HUANG S, JAN R. Energy-aware, load balanced routing schemes for sensor networks[C]// Proceedings of the 10th International Conference on Parallel and Distributed Systems (ICPADS’04),Jul 7-9,2004,Newport Beach,CA,USA.Los Alamitos, CA,USA: IEEE Computer Society, 2004:419-425.
[7] CHIPARA O, HE Z, XING G, et al. Real-time power control in wireless sensor networks[R]. WUCSE-2005-31. St Louis, MO,USA: Washington University in St Louis, 2005.
[8] HE T, STANKOVIC J, LU Chenyang, et al. Speed: A stateless protocol for real time communication in sensor networks[C]// Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS’03), Mar 19-22, 2003, Providence, Rhode Island, USA. Piscataway, NJ,USA:IEEE, 2003:46-55.
[9] FELEMBAN E, LEE C, EKICI E, et al. Probabilistic QOS guarantee in reliability and timeliness domains in wireless sensor networks[C]// Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’05): Vol 4, Mar 13-17, 2005,Miami, FL, USA. Piscataway, NJ,USA:IEEE, 2005:2646-2657.
[10] CHIPARA O, HE Z, XING G, et al. Real-time power-aware routing in sensor networks[C]// Proceeding of 14th IEEE International Workshop on Quality of Service (IWQoS’06), Jun 19-21, 2006, New Haven, CT,USA. Piscataway, NJ, USA: IEEE, 2006:83-92.
[11] LU C, XING G, CHIPARA O, et al. A spatiotemporal query service for mobile users in sensor networks[C]// Proceedings of the 25th International Conference on Distributed Computing Systems (ICDCS’05), Jun 5-10, 2005, Columbus, OH, USA. Piscataway, NJ,USA:IEEE, 2005: 381-390.
[12] HE T, VICAIRE P, YAN T, et al. Achieving real-time target tracking using wireless sensor networks[C]// Proceedings of the 12th IEEE Real-time and Embedded Technology and Applications Symposium(RTAS’06),Apr 4-7,2006, San Jose,CA,USA. Piscataway, NJ, USA:IEEE, 2006:37-48.
[13] HE T, REN F, LIN C, et al. Alleviating congestion using traffic-aware dynamic routing in wireless sensor networks[C]//Proceedings of the 5th Annual IEEE Communications Society Conference on in Sensor, Mesh and Ad Hoc Communications and Networks (SECON’08), Jun 16-20, 2008, San Francisco, CA, USA. Piscataway, NJ, USA:IEEE, 2008:233-241.
[14] BASU A, LIN A, RAMANATHAN S. Routing using potentials: A dynamic traffic-aware routing algorithm[C]//Proceedings of Conference on Applications,Technologies, Architectures,and Protocols for Computer Communication(SIGCOMM’03),Aug 25-29, 2003, Karlsruhe, Germany. New York, NY,USA:ACM,2003: 37-48.
[15] LEVIS P, LEE N, WELSH M, et al. Tossim: Accurate and scalable simulation of entire tinyOS applications[C]// Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys '03), Nov 5-7, 2003, Los Angeles, CA, USA. New York, NY,USA: ACM, 2003: 126-137.

收稿日期：2009-08-27

[摘要] 文章结合无线传感器网络(WSN)中流量分布的向心性特点，借鉴物理学中势能场的概念与机理，提出一种开放的路由协议实现框架。利用不同的网络参数构造不同的“虚拟势能场”，叠加后形成的复合势能场将驱动数据分组沿着势场梯度变化最快的方向移动，一方面可以最终将网络中的数据分组汇聚于目的节点，实现路由协议的基本功能；同时，在动态时变“虚拟势能场”的调节下，还可以为路由协议附加各种有利于实现其他优化目标的策略与属性，如能耗均衡、拥塞避免、支持服务质量保障和利于数据聚合等，在无线传感器网络中实现多策略路由。作为例子，文章提出了一个基于势能场的提供实时传输的路由协议，它能在严格保障实时分组获得最小化端到端延迟的前提下，有效缓解网络拥塞，提高全网吞吐量。

[关键词] 无线传感器网络；势能场；路由协议；多策略；实时传输；端到端延迟

[Abstract] In this paper, motivated by the centralized traffic pattern in the Wireless Sensor Network (WSN), we propose a unified implementation framework for routing protocols based on the concept of potential field in the physics. Utilizing various parameters and factors, the multi-strategy routing protocol constructs different virtual potential fields, which move the data packets along the direction of the steepest gradient in the field. In consequence, the traffic is aggregated in the Sink node which satisfies the basic requirements of routing, while the dynamic time-variant field provides kinds of additional strategies and attributes for optimization purposes of the protocols. These optimization targets include energy balance, congestion control, QoS support and data aggregation, all of which achieve the multi-strategy routing in the WSN. As a case, we present the Potential Based Real-Time Routing (PRTR) protocol, which minimizes the end-to-end delay of real-time packets and effectively alleviates the congestion for throughput improvement simultaneously.

[Keywords] wireless sensor network; potential filed; routing protocol; multi-strategy; real-time transmission; end-to-end delay