势流理论在无线传感器网络多径路由协议中的研究*

姜志鹏，陈正宇，阎 浩，赵 炜

（金陵科技学院电子信息工程学院，南京211169）

Kalantari M等在解决ad-hoc网路的路由问题时，将传感器网络类比成静电场。作者根据电场的性质导出一系列偏微分方程，通过求解偏微分方程确定网路中各节点对应的路由［5］。文献［6］在文献［5］的基础上引入了能量因素。文献［7-8］进一步将文献［5-6］中的方法扩展到多汇聚节点、多种类负载情况，通过将多汇聚节点传感器网络类比成静电场，提出了一种多汇聚节点传感器网络最佳路由选择和负载分配的方法。文献［9］等提出了一种基于静电场模型的移动多汇聚节点传感器网络部署

近年来传感器网络得到了迅速发展和广泛关注，它可以广泛地应用到国防军事、环境监测、医疗护理等许多领域。典型的传感器网络由节点、汇聚节点组成。当节点监测到事件发生后，需要将监测到的信息通过其他节点，采用“多跳”方式传输至汇聚节点［1］，汇聚节点可以与卫星进行通信。

目前在对传感器网络相关问题进行研究时，一些研究人员将传感器网络的问题映射成经典的物理学问题，利用数学物理方法来解决这些问题。Toumpis S等在研究大规模无线传感器网络的节点部署时，将问题抽象成静电场中电荷的分布问题，根据电荷在电场中的分布特性，得出了传感器网络中节点最优分布时应满足的条件［2］。文献［3-4］对方法。该方法根据节点的剩余能量动态地调整节点的电性和带电量，从而构建一个能量高效的网路。文献［10］提出了一种基于静电场的移动ad-hoc网路服务发现演算法，该演算法用正负点电荷分别类比服务实例和服务请求，服务请求根据邻居节点的电势路由到服务实例。文献［11］提出了一种基于磁场的磁扩散MD（Magnetic Diffusion）算法，该演算法将汇聚节点节点抽象成磁铁，将资料抽象成可以被磁铁吸引的铁屑，从而建立了一个由磁铁激发的磁场。资料根据磁场中节点的磁场强度路由至汇聚节点节点。MD算法可以完成资料的即时、可靠传输，并可以实现网路中节点能量高效利用。但对于普通的传感器网络，MD算法并不能十分均衡地利用网路资源。文献［12-13］提出了一种基于几何光学的传感器网络路由选择演算法，该演算法将资料在网路中传播抽象成光在具有一定折射率的介质中传播，进而得出网路的路由。文献［14］在研究传感器网络的路由选择问题时，将网路抽象成一个由热源激发的温度场，根据网路中节点的温度值进行路由选择，最终到达热源（汇聚节点）。文献［15］对采用经典数学物理方法解决传感器网络问题的部分研究成果进行了总结。

上述文献进行的相关研究对传感器网络的路由设计做出了巨大贡献，但几乎没有学者从势流理论的角度去解决路由问题。本文将探讨传感器网络的路由设计与势流理论之间的关系，因为二者有许多相似之处。点源势流发散流体，它类似于传感器网络中源节点的发送数据。此外，点汇势流汇聚流体，它类似于传感器网络中汇聚节点接收数据的功能。从点源发出的流体最终收敛于点汇，而这个过程正类似于传感器网络的数据从源节点发出并到达接收节点。通过理论分析和实验仿真可以得出结论，本文提出的基于势流理论的路由算法能够实现较好的数据可靠传输，以及改善节点的能量效率。与其它路由算法相比，这种算法具有较少的网络等待时间，更高的吞吐能力，较低的能量消耗和更高的能量效率。

1 势流理论与路由协议

不可压、理想流体的无旋流动称为势流。势流即无源、无旋的流动，其势函数满足拉普拉斯方程：

式（1）中Φ称为流速场的势函数（速度势）。通过求解满足边界条件和初始条件的拉普拉斯方程，可求得速度势。对于平面流动，也可以通过求解满足拉普拉斯方程的流函数（ψ称为流速场的流函数），来求速度分布，速度势和流函数构成复势，是解析函数，可利用有关的保角变换法求解。

平面点源和点汇是二维势流里的较简单形式，参见图1。设从源注入流场的体积流量为Q，称Q为平面点源的强度。Q＞0，是点源；Q＜0，是点汇。

图1 点源（Q＞0）和点汇（Q＜0）

源点位于坐标系统的原点。从图1可以看到，无论是点源还是点汇都只存在径向速度而不存在环向速度。其x方向和y方向的速度矢量可以表示为：

对式（2）进行积分运算，可以求解出Φ和ψ：

传感器网络中的源节点可以类比于二维势流里的点源概念，同样地，目的节点可以类比于点汇概念。路由是从源节点起始至目的节点结束的路径。源节点连续地产生消息，并将它们发送到目的节点，在同一时间，目的节点接收它们。节点间消息的传递必然将产生网络流量，此流量可以用流量密度函数ρ（x，y）来表示，它体现了坐标（x，y）处网络流量密度的大小，刻画了单位时间内该处流量的大小情况，同势流理论里的体积流量Q相对应。所以，在无线传感器网络的源节点和目的节点可以类似于势流理论里的点源和点汇。

2 基于势流理论的路由算法

2.1 路由模型

在势流理论中，不同的势流可以相互叠加从而产生新的势流（叠加定理）。拉普拉斯方程式（1）是线性的，假设存在两个不同的势流（势流1和势流2），即意味着势流1和势流2的代数和也满足拉普拉斯方程。即，如果∇2ψ1=0、∇2ψ2=0，则满足

式中，ψ1和ψ2分别是势流1和势流2的流函数。此式表明流函数的和满足拉普拉斯方程，同理，势流1和势流2的速度势函数之和Φ1+Φ2同样满足叠加定理。

先从简单的单源单汇模型开始，复杂的网络（如多源多汇）可以利用叠加定理来处理，即多个单源单汇模型的叠加。参见图2，源节点（Q＞0）位于左上角而汇聚节点（Q＜0）位于右下角，左图是速度矢量，右图是流线，从右图中可以看出从源节点到汇聚节点有多条流线，这些流线和势线相互垂直。把流线附近的节点按照流线方向连接，就可以形成路径，这些路径提供了从源节点至汇聚节点链路（即路由）。

考虑到传感器网络在实际应用时的复杂性，把上述的单源单汇模型向多源多汇模型推广。当传感器网络中存在多个源节点与汇聚节点时，可以把他们看做是势流里的多个点源与点汇，这些点源与点汇产生的流场可以叠加，如图3所示。汇聚节点1（Q＜0）位于左上角，汇聚节点2（Q＜0）位于右下角，而4个源节点散落分布在网络中，从图中可以看出，位于两个汇聚节点中间的源节点3既有到汇聚节点1的流线又有到汇聚节点2的流线，也即源节点可以同时‘流向’2个汇聚节点。源节点1因为源节点2对其的‘阻碍’只能‘流向’汇聚节点1。这些都符合势流理论。

图2 单源单汇：速度矢量（左图）及流线（右图）

图3 多源多汇：速度矢量（左图）及流线（右图）

2.2 路由算法设计

假设汇聚节点和源节点可以通过某些定位方法获得自己的坐标信息（例如GPS）。源节点构建一个广播数据包（Msg_broadcast），携带数据包类型，坐标，负载（相当于Q值），跳数等字段，并将其广播发送。中间节点接收到广播数据包后进行转发，最终该数据包会到达汇聚节点。通常，对汇聚节点设置一个覆盖区域最大半径（R_sink），当然，也可以用最大允许跳数来替代，其目的是区域分割，这和分簇的原理是一样的。汇聚节点根据接收到的广播数据包中的坐标或跳数信息进行筛选，确定其包括的源节点成员列表（List_src）。在有了成员列表和成员坐标、负载等信息后，汇聚节点将根据这些信息进行一次计算，得到叠加后的Φ和ψ。汇聚节点接下来会构建一个路由请求数据包（Msg_request），携带数据包类型，Φ和ψ，当前节点速度矢量（velocity vector）和跳数等字段，在其覆盖区域内广播发送。邻居节点收到路由请求数据包后，取出Φ和ψ，经过简单计算即可求得自己的velocity vector，然后选取夹角最小的节点作为上一跳节点，并向其发送路由确认数据包（Msg_ack），携带数据包类型，上一跳节点ID等字段。

图4 路由建立过程

为了更清晰的说明路由建立这一过程，参见图4，中间节点C同时收到邻居节点A，B的路由请求数据包，节点C计算与A、B的速度矢量夹角，分别记为θa与θb，比较θa与θb的大小（θa＜θb），选取夹角小的节点A作为上一跳节点，向A发送路由确认数据包，并建立路由表，记录上一跳节点为A；节点A收到C发送的路由确认数据包后，更新路由表将C作为下一跳节点。依此类推，C继续向前发送路由请求数据包，直到源节点接收结束，源节点向汇聚节点发送路由确认数据包，由此一条从汇聚节点至源节点的路由建立完毕。

整个路由建立算法可以用算法1表示。

算法1 势流路由算法

接下来用一个例子来演示该路由算法。建立一个1 000×1 000单位的平面区域A，随机分布300个传感器网络节点，汇聚节点位于区域A的中心，4个源节点分别位于四角（如图5左图），根据路由算法，对区域A内的节点进行路由建立，结果如图5右图所示，从图中可以看出，路径的平滑程度与节点的密度相关，节点密度越高，其平滑程度越好。

图5 势流路由算法示例

3 路由仿真与分析

利用 MATLAB 平台下的 Rmase［9］工具来进行路由仿真与分析。选用以下四个指标来评价路由协议的性能：网络延迟、吞吐量、成功交付率和能耗。

选择本文提出的势流路由协议PF（Potential flow routing）与三种经典的多经路由协议进行比较：按需距离矢量路由协议AODV（Ad-hoc on-de⁃mand distance vector）、基于蚁群优化启发式算法的洪泛路由协议（FF，Flooded forward ant routing）、感知及成本驱动的蚁行路由SC（Sensor driven and cost-aware ant routing）。表1给出了仿真参数。

图6左图，PF的网络要延迟远低于FF而略高于SC和AODV。因为PF包含了从源节点到目的节点的多条路径，其中包括最短路径。所有路径的平均跳数比最短路径要高，因此其网络延迟会略高一些。仿真结果，PF的网络延迟是0.045 3 s，而AODV的是0.036 s。PF的延迟要高出大约25%。

图6右图，可以看到PF的吞吐量比其他三种路由协议的都要高，因为PF可以同时在多条路径上传输数据而AODV仅有一条传输路径。仿真结果表明，AODV下发送了406个数据包而PF下共发送了1 352个数据包，这大约是前者的三倍左右。同时我们看到图中SC和FF的吞吐量随时间在趋于增大。PF并不存在这种现象而是稳定在3.75左右。

从图7左图可以看出，整个仿真过程中PF的成功交付率都高于90%，这意味着更多的数据包可以正确的到达目的节点。大约从30 s开始，PF的成功交付率指标就接近92%。相反，在其他三种协议中，仿真开始时的成功交付率是相当低的。并且可以看到SC和FF的成功交付率在增大而AODV却在减少。PF的成功交付率指标比其他三种协议要高出不少（最高点比最低点高约50%）。

表1 仿真参数

图6 网络延迟（左图）及网络吞吐量（右图）

图7 成功交付率（左图）和网络能耗（右图）

从图7右图可以看到，所有协议的网络能耗随着仿真的进行都在增加。AODV具有最大的网络能耗而SC最小。同时我们可以看到AODV曲线的斜率要高于PF，这意味着随着时间的推移，前者会消耗更多的增量能耗

4 结论

本文提出了一种基于势流理论的传感器网络路由模型，整个网络被抽象成流场。点源和点汇分别发散和吸收流体，这类似于传感器网络中源节点发送数据包而目的节点接收数据包。点源和点汇之间形成的流线用于建立路由。理论分析和仿真结果表明，该方法在通信中使用较少的能量，有较高的网络的成功率，故能有效地延长了网络的生命周期。

本文只对势流理论的路由算法进行初步研究。许多问题仍需要进一步的研究，如路由算法到网络规模的适应性，并且对网络拓扑的变化等。

［1］乔学工，王哲，王华倩，等.基于权值的非均匀分簇路由算法［J］.传感技术学报，2014，01：107-112.

［2］Toumpis，Stavros.Mother Nature Knows Best：A Survey of Recent Results on Wireless Networks Based on Analogies with Physics［J］.Computer Networks，2008，52（2）：360-383.

［3］Toumpis，Stavros，Leandros Tassiulas.Packetostatics：Deployment of Massively Dense Sensor Networks as An Electrostatics Problem［C］//24th Annual Joint Conference of the IEEE Computer and Communications Societies，2005.

［4］Toumpis，Stavros，Gautam A Gupta.Optimal Placement of Nodes in Large Sensor Networks Under A General Physical Layer Model［C］//Second Annual IEEE Communications Society Conference，2005：275-283.

［5］Toumpis，Stavros，Leandros Tassiulas.Optimal Deployment of Large Wireless Sensor Networks［J］.Information Theory，2006，52（7）：2935-2953.

［6］Kalantari，Mehdi，Mark Shayman.Design Optimization of Multi-Sink Sensor Networks by Analogy to Electrostatic Theory［C］//Wireless Communications and Networking Conference，2006：1.

［7］Kalantari，Mehdi，Mark Shayman.Routing in Multi-Commodity Sensor Networks Based on Partial Differential Equations［C］//40th Annual Conference on Information Sciences and Systems，2006.

［8］Vincze，Zoltán，，et al.Electrostatic Modelling of Multiple Mobile Sinks in Wireless Sensor Networks［C］//Proc of the IFIP Network⁃ing Workshop on Performance Control in Wireless Sensor Net⁃works（PWSN 2006），Coimbra，Portugal，2006.

［9］Lenders，Vincent，Martin May，et al.Service Discovery in Mobile Ad Hoc Networks：A Field Theoretic Approach［J］.Pervasive and Mobile Computing，2005，1（3）：343-370.

［10］Ghica，Oliviu C.Security of Electrostatic Field Persistent Routing：Attacks and Defense Mechanisms［C］//Dependable Computing Conference（Ninth EDCC），2012.

［11］Huang H J，Chang T G，Hu S Y，et al.Magnetic Diffusion Scalabil⁃ity，Reliability，and Qos of Data Dissemination Mecha-Nisms for Wire-Less Sensor Networks［C］//Proceedings of Computer Com⁃munications Special Issue on Wireless Sensor Networks.Perfor⁃mance，Reliabil-ity，Security，and Beyond，2006：2482-2493.

［12］Chang Shihhao，Madjid Merabti，et al.Coordinate Magnetic Rout⁃ing for Mobile Sinks Wireless Sensor Networks［C］//Advanced In⁃formation Networking and Applications Workshops，21st Interna⁃tional Conference，2007：1.

［13］Catanuto R，Morabito G，Toumpis S.Optical Routing in Massively Dense Networks：Practical Issues and Dynamic Programming In⁃terpretation［C］//3rd International Symposium on Wireless Com⁃munication Systems，2006.

［14］Catanuto，Roberto，Stavros Toumpis，et al.Opti{c，m}al：Optical/Op⁃timal Routing in Massively Dense Wireless Networks［C］//26th IEEE International Conference on Computer Communications，2007.

［15］Baumann，Rainer.HEAT：Scalable Routing in Wireless Mesh Net⁃works Using Temperature Fields［C］//International Symposium on World of Wireless，Mobile and Networks，2007.