用于VSN的低延时多径路由

吴 迪， 尹首一， 李国林

（清华大学微电子所，北京100084）

0 引言

无线传感器网络（WSN）用于感知和测量物理世界，实现了人与物理世界之间的沟通。随着技术的进步简单的物理量的测量已不能满足人们的需求。视频传感器网络(VSN)作为一种新兴的传感器网络已越来越受到人们的关注，其最突出的特点就是对网络的实时性有很高的要求而且需要更高的数据传输带宽。无线传感器网络路由协议分为两类，一类是平面路由，另一类是层次化路由。前者如 SPIN[1]、EAR[2]，后者代表是LEACH[3]。这些协议均不是从减小网络延时的角度出发的，本文提出并实现了一种新的基于多径路由的算法，MPTT(Multi-path Predicted Transmission Time)这种算法不仅能够降低数据的传输延时，而且相对于单径路由DSR可以提供更高的网络带宽，更适合视频传感器网络的要求。

1 MPTT算法

1.1 MPTT 的单路径延时

MPTT是基于文献[4]的思想，首先通过从MAC层建模根据节点以及其邻居节点的流量信息计算出每条链路的延时，然后比较分析所得到的每条路径的延时并进行流量分配，使总体的数据流延时达到最小。根据文献[4]一跳的传输延时可以表示为：

其中Ts表示数据包发送需要的时间，其值与路径上邻居节点的流量信息有关，Tq表示数据等待发送需要的时间，λij表示这条链路上传输的数据流量。如果一条路径上需要n跳的转发，那么总体的延时PD(Path Delay)可以表示为：

Tn表示第n跳的延时。总体上可以得出，路径延时既与发送路径邻居节点的流量信息相关又与自身数据流量大小相关，流量越大路径的延时也就越大。

1.2 MPTT多径流量分配

现在我们通过改进的 DSR[5]算法得到了m条路径。假设要在这些路径上分配流量Ftotal，分配给每条路径上的流量分别为F1,F2,…,Fm则有：

路径的延时与这条路径上的数据流量有关，路径上的数据流量越大则这条路径的延时就越大。为了得到数据流的最小延时，应该首先将流量分配给延时最小的路径，随着分配流量的加大路径的延时也相应的增加。当其延时大到该路延时已不再是所有路径中延时最小的路径时，就重新寻找延时最小的路径并将剩余流量分配给新寻找出来的路径。如此循环下去直到分配完所有的流量为止。因此最终的结果就是所有被使用的路径其延时相同。如果使用了k条路径则分配给每条路径的流量应该满足如下的方程组：

可以利用循环迭代的方式求出其近似解。这样就求出了延时最小的流量分配方案。

2 MPTT的实现

整个的路由算法可以由图1来实现。目前路由发现的算法的代表是DSR和AODV[6]。MPTT的路由发现的过程是基于DSR协议，在此基础上还完成了路径流量信息的采集。首先每个节点根据自身发送和接收数据包情况来建立本地流量信息表。当某一个节点想要发送数据时就发起一个路由请求，路由请求是通过全网广播的方式发送出去的，发送路由请求的同时也将本地的流量信息搭载在数据之后。当其邻居节点收到路由申请之后一方面记录搭载在路由申请之后的流量信息到邻居链路信息表中，另一方面如果检测到本地节点为目标地址则发出路由回复，否则将本地的流量信息表搭载在数据之后继续广播。当路由申请节点收到路由回复之后就开始检测这条路径，如果该路径为收到的第一条路由回复，则将其记录在本地的路由信息表之中。如果不是第一条路由回复，则用已有的路由检测新得到的路由，如此逐步的检测所有新得到的路径。这样就可以得到多条互不相关的路径。然后开始采集各个路径的流量信息，在采集之后就利用前面所提出的路由算法进行流量分配，开始发送数据，到此为止完成了发送数据的整个过程。

图1 MPTT实现的框架图

3 仿真结果及分析

3.1 仿真过程

本文所采用的就是基于TinyOS的仿真平台TOSSIM。仿真的网络为由 10个节点组成的具有三条互不相关路径的网络，三条路径的跳数分别为 3、4、4。网络的数据传输带宽为 40 Kb/s。仿真的过程是从源节点以递增的速率向目的节点发送100个数据包，速率从1～20 Kb/s，间隔为1 Kb/s。从数据包的平均延时和丢包数量来检测两个方面比较 MPPT和单路径路由DSR协议。

3.2 仿真结果

从图 2中我们可以看出在分配的数据流量比较小的时候MPTT与DSR路由的延时基本一致有时还比其小。这是由于在低速率时流量基本上分配给了跳数最少的路径，但是由于DSR每次所选出的路径具有随机性并不是每次都能选出最短的路径来传输数据，所以有时其延时比较大。MPTT总是选择跳数最少的路径来发送数据。除此之外图2中的虚线还表示出了单径所能分配的极限流量。在到达极限传输流量之后DSR无法正常工作，然而MPTT却依然可以发送数据，提供了更高的数据流带宽。

图2 MPTT与DSR延时比较

图3 MPTT与DSR丢包率比较

上页图3显示出了在传输相同的数据流时，MPTT可以提供更低的丢包率。这是由于当某一路上的数据流量增大的时候，该路上的数据包碰撞概率会以指数形式增加，当把流量分配给多条路径时就减小了数据包碰撞的概率进而减小了丢包率。

4 结语

MPTT是通过从MAC层建模，根据路径上每个节点的邻居流量信息计算出来每条链路的延时，再根据延时情况进行流量分配。利用 MPTT所得到的总体延时在流量不大的情况下与单径路由所选择的延时最小的路径相当。随着所分配流量的加大，MPTT的延时比DSR要小，而且可以提供DSR所不能提供的高速据带宽。另一方面 MPTT可以降低丢包率，提高数据流传输的可靠性。因此 MPTT是一种更适合视频数据流服务的路由协议。

[1] Xu Ning, Rangwala Sumit, Chintalapudi Krishna Kant, et al. A Wireless Sensor Network for Structural Monitoring[C].Baltimore: Association for Computing Machinery, 2004: 13-24.

[2] Mann Raminder P, Namuduri Kamesh R, Pendse Ravi. Energyaware Routing Protocol for Ad Hoc Wireless Sensor Networks[J].Eurasip Journal on Wireless Communications and Networking,2005(05):635-644.

[3] Heinzelman Wendi B, Chandrakasan Anantha P, Balakrishnan Hari. An Application-specific Protocol Architecture for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications, 2002,1(04): 660-670.

[4] Yin Shouyi, Xiong Yongqiang, Zhang Qian, et al. Trafficaware Routing for Real-time Communications in Wireless Multi-hop Networks[J]. Wireless Communications and Mobile Computing, 2006,6(06):825-843.

[5] Johnson D, Maltz D, HuYih-Chun. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR)[EB/OL].(1999-10-01)[2009-03-11] http://www.ietf.org/rfc/rfc4728.txt.2007.

[6] Perkins C E, Royer E M, Das S R, et al. Performance Comparison of Two On-demand Routing Protocols for Ad Hoc Networks[J].IEEE Personal Communications, 2001,8(01):16-28.