田贤忠，刘 强，胡同森

(浙江工业大学计算机科学与技术学院，杭州 310023)

传统无线自组织网络和传感器网络的路由协议都采用确定性路由［1－3］方式，即:在端到端的数据传输过程中，首先建立一条端到端的节点序列，然后在每次分组转发时，首先确定一个下一跳节点，再执行链路层转发。如果传输过程中发生分组丢失或差错，则启动链路层重传。在链路质量和稳定性较差的环境下，频繁的链路层数据重传将消耗大量的带宽资源。因此，尽管确定性路由方式逻辑简单，但未能充分考虑无线信道的广播特性、时变特性和干扰不规则性等特点。无线信道的广播特性使得一次分组转发可能被多个节点收到，且接收概率各不相同；无线链路的时变特性导致网络中链路的状态随时间而改变。路由协议设计过程中如果缺乏对信道广播和丢失特性的充分考虑，必将导致大量网络资源无谓浪费，这将严重影响网络的吞吐量及其它性能。

针对无线信道的广播、时变、丢失特性和确定性路由策略的不足，麻省理工学院(MIT)的Biswas等人于2004年率先提出了机会路由［4－5］的概念。机会路由通过多个潜在中继节点竞争、自主智能进行下一跳节点选择。它充分利用了信道广播特性，提高了网络的吞吐量和传输可靠性。研究机会路由算法［6－8］来提升无线多跳网络的性能，已成为当前无线自组织网络与传感器网络组网协议研究中的一个重要方向。

网络 编 码［9－12］(Network Coding) 技 术 由 R.Ahlswede等人在2000年首次提出的。该技术可以极大地提高网络的吞吐量和可靠性。如何同时发挥机会路由和网络编码的优势，文献［13］中的MORE协议对此进行了尝试。MORE是一个MAC无关的协议，它通过引入网络编码解决了数据传输过程中节点协作难的问题，即:转发节点可以不管其他节点发送的是什么数据，而只需要将自己缓存下来的数据进行编码后转发出去即可，目的节点收到一定数量的编码包后解出相应的原数据包。同时它充分利用了网络的空间关系，通过多个节点的协作转发数据包，而不是某一个节点转发。但是它有一个致命的缺陷就是“停止－等待”机制，即网络中只能存在一段数据，源节点只有收到目的节点的ACK确认信息后才开始发送下一段数据，这样就影响了网络的吞吐量。为此，Lin Y［14－15］等人给出了两种不同的解决方案:文献［14］同样是采用分段的形式传输，但能够同时传输多个段，效率有一定的提高，但是存在ACK数量较多的问题，它在一定程度上占用了网络带宽资源；文献［15］则从另一个方面入手来解决MORE的问题，它摒弃了段的概念，将数据看成一个很长的流，采用“滑动窗口”的形式进行传输，也在一定程度上解决了MORE的问题。文献［16］则从另一个角度发挥机会路由与网络编码的优势，它用个一种新的确认机制来压缩传统ACK确认机制带来的开销，在一定程度上改善了网络的性能。

从上面的分析可以看出，提高网络的吞吐量需从两个方面着手:(1)发送ACK确认信息要及时；(2)发的ACK确认信息要少。为此，本文提出一种最大限度的压缩ACK的机制，我们称之为MinACK算法。它较为及时地发送ACK，从而允许同时在网络中传输多个数据段；同时每发送一段数据只需回一个ACK，减少了ACK的发送。另外，它还与MAC无关，省去了许多节点之间协作的开销，从而进一步提高网络的吞吐量。我们在仿真实验中也充分证明了MinACK的优势所在。

1 MinACK基本思想与算法

如图1所示，在MORE算法中，源节点S首先把要发送的数据包分成相同大小的数据段，每一数据段由K个数据包组成，然后把同一段的K个数据包线性网络编码后发送。节点A、B、C在收到源节点S发送过来的编码包后，与各自之前已收到的同一数据段的编码包重新编码后再发送。目的节点D收到K个线性无关的编码包后解出原始数据包，并发送一个确认信息ACK给源节点S。源节点S在收到ACK后发送下一段数据包。这样有一个问题，目的节点D在能解码时，源节点S不能马上发送下一段的数据包，必须等到收到ACK后才开始发送，这样造成源节点S延迟发送，影响网络的吞吐量，在跳数比较多的情况下，这种影响尤为严重。

图1 MinACK原理图

MinACK的基本思想是:当源节点S向下一跳节点广播编码包时，下一跳节点A、B、C由于丢包可能各自只收到部分编码包，但当节点A、B、C总共收到足够多(大于等于K个)的线性无关的编码包后，其中一个节点发送一个确认信息ACK给源节点。源节点在收到ACK确认信息后马上可以发送下一数据段的数据包。因为这时节点A、B、C中含有足够多的线性无关编码包可以发送给目的节点D。这样源节点不需要等目的节点发送ACK，只需下一跳的节点发送的ACK，节省等待时延。而下一跳的A、B、C三个节点中只有一个节点在它们收到同一数据段的K个线性无关编码包后才发送一个ACK，这样ACK的数量也会尽可能的少。

MinACK算法针对源节点、中继节点和目的节点分三部分:

(1)源节点

①源节点S首先把要发送的数据包分成相同大小的数据段，每个数据段由K个数据包组成，然后把同一段的K个数据包线性编码产生编码包。当源节点S竞争获得信道后向下一跳节点广播(发送编码包的个数根据§2.3确定)。

②当源节点S接收到下一跳节点的ACK后，发送下一段的数据包。

(2)中继节点

①中继节点v在收到前一跳节点u发送的编码包后，就与其之前已收到的同一段的编码包重新编码后向其下一跳节点广播(发送编码包的个数也根据§2.3确定)。这时如果节点v已收到同一段的K个编码包，就向上一跳节点广播一个确认信息ACK。

②节点v向下一跳广播发送编码包时，其前一跳节点u的其它下一跳节点w也收到了，也就是说节点w不但收到上一跳节点u的编码包，也收到同层节点v的编码包。不管哪种情况，节点w对收到的编码包也判断是否与之前收到的同一段的编码包线性相关，如果线性无关就编码后向其下一跳节点广播(发送编码包的个数也根据§2.3确定)。同时判断如果节点w收到同一段的编码包个数为K个，就向上一跳节点广播一个ACK。

③如果节点u收到的是节点v向上一跳节点发送的确认信息ACK，则停止本段编码包的接收，等待接收下一段编码包。

(3)目的节点

目的节点D在收到K个编码包后，解出原始数据包，同时向前一跳节点发送确认信息ACK。

2 MinACK具体实现

上面的算法中，有几个问题必须明确:(1)如何确定下一跳节点；(2)编码解码策略；(3)节点转发编码包数目；(4)ACK确认包的格式。

2.1 下一跳节点与上一跳节点

MinACK算法中节点v的下一跳节点是指到目的节点的ETX［17］值比自己小的邻居节点，即Next(v)={u|ETX(u)＜ETX(v)且u∈Neighbour(v)}其中Neighbour(v)表示节点v的一跳邻居节点；同样，节点v的上一跳节点是指到目的节点的ETX值比自己大的邻居节点，即

网络中的节点通过周期性的互相探测来获得每条链路的成功传输率，ETX值是对应链路的成功传输率的倒数，表示发送成功一个数据包平均需要发送的次数。节点到目的节点的ETX值等于其路径上每一跳的ETX之和。每个节点都计算并记录自己到目的节点的ETX值。根据ETX值可以找到节点的下一跳与上一跳节点。

2.2 编码解码策略

编码包在转发节点处被重新编码，易得重新编码后的包仍然是原始包的线性组合，因为

目的节点一旦接收到同一段的K个线性独立的编码包，它就可以用以下方式解码:

其中PCi'是目的节点接收的编码包，Pi是原始包，i=(ci1，…，ciK)是编码包PC'i对应的编码向量，通过高斯消元即可解码出原始包。

2.3 节点发送数据包的数目

当一个节点收到一个编码包后，会触发其重新编码后向下一跳节点发送编码包。那么应该发送多少个编码包?按传统方法每收到一个发送一个会带来两个问题:①由于丢包，只发送一个包下游节点可能会收不到；②因为节点是广播编码包的，所以可能会有多个下一跳节点收到此编码包，每个收到的节点都发一个包会造成重复发送。其实多个下一跳节点中只需要一个节点发送就可以了。

首先考虑源节点需发送一个数据包时，每个节点需发送的数据包个数。根据文献［13］，设puv表示节点u到节点v的丢包率，nu表示节点u发送数据包的次数，则节点v收到编码包的个数为:

实际操作时，在每个节点v中设置一个计数器Countv。首选设Countv=0；每当节点v收到一个编码包，则 Countv=Countv+npv；这时，如果 Countv＞0，节点v发送一个编码包，同时Countv=Countv－1。当节点v发送下一数据段时Countv清零。

2.4 ACK 确认包

当节点i知道自己的下一跳节点中已接收到同一数据段的K个编码包时，节点i就向其上游节点发送一个ACK确认信息。上游节点在收到ACK后删除缓存中这一段的编码包，开始发送下一段数据的编码包。如图2所示，ACK数据包主要包含三个域:发送节点ID是指发送ACK节点的编号，接收节点ID列表为发送节点的上一跳节点的编号列表，数据段ID告诉接收节点哪一数据段已被其下游节点收到，可以清除缓存中的这段编码包。

图2 ACK包格式

3 性能分析

MinACK能在网络中同时传输多个数据段，从而提高网络的吞吐量。这里分析网络中能同时传输的数据段数以及网络的吞吐量。

3.1 网络中能同步传输的段数

从MinACK算法中我们可以知道，当某个中继节点回了一个ACK后，其上一跳节点可以发送下一数据段。我们可以从第二跳节点(和源节点直接相连的节点)发送的ACK数量来判断网络中同时传输的数据段数:

其中nseg表示网络中同时存在的数据段数，nack表示第二跳节点回ACK数量，ndestACK是目的节点回的ACK数量。

发送ACK的数量nack和ndestACK仿真实验与实际传输中很容易记录下来，但理论计算比较难。我们用另一种思路来计算网络中同时传输的数据段数。其实，段数与传输一个数据包的跳数有关。如图3所示，如果数据包从源节点S经节点B发送给目的节点D(下面称“路径P1”)，只需两跳。这时，节点B收到数据包回ACK后，源节点S可以发送下一数据包，网络中存在两个数据段。如果源节点S经节点A、B发送给目的节点D(下面称“路径P2”)，则数据包发送需要三跳。这时，节点A、B都可以回ACK，网络中同时存在三段数据段。所以数据段数与传输一个数据包的跳数相对应，即

图3 跳数与段数关系

而传输一个数据包的跳数就是传输这个数据包时各个节点所要传输的次数之和。如图3，如果采用“路径P1”节点S需传输1次，节点B需传输1次，共两次，与跳数相等；同样，如果采用“路径P2”，节点S、A、B各传输1次，共3次，也与跳数相等。当传输一个数据包，采用“路径P1”和“路径P2”的概率都为0.5，则平均跳数为:0.5×2+0.5×3=2.5。而每个节点的传输次数分别为S=1，A=0.5，B=1，共2.5次，与平均跳数相等。

在实际网络中源节点传输一个数据包，节点v需传输的数据包个数为Lv，根据式(2)，可以求出所有节点的发送次数，即网络中同时传输的数据段数为:

3.2 网络的吞吐量

网络的吞吐量是网络性能的一项重要标志。假设一个数据包发送一次所需时间为t。这里我们忽略计算时间(包括编码与解码所需要的时间)，因为计算时间比传输时间要小得多，可以忽略不计。首选计算目的节点收到一段数据包(K个编码包)所需的时间Ttotal。Ttotal包括两部分:第一个编码包从源节点传输到目的节点的时延T1和目的节点从收到第一个编码包后到收完其余K－1个编码包所用的时间T2，即:

因为一个包从源节点传输到目的节点的时延为其传输次数×t，同时考虑MinACK可以在网络中同时传输多段数据包，得T1值为:

其中ntotal是从源节点传输一个数据包到目的节点所有节点传输次数，根据式(3)，其值为:

根据式(8)、式(9)、式(11)计算出Ttotal。

网络吞吐量是单位时间内传输的数据量。由前面分析可知，传输K个编码包的时间为Ttotal，假设每个编码包的大小是M，则吞吐量

4 仿真实验

本文使用Matlab语言对MinACK协议进行仿真模拟，以观察在传输相同数量的数据包的情况下ExOR、MORE以及MinACK传输次数，网络中存在的段数以及网络的吞吐量等性能。我们在50 m×50 m的范围内随机分布30个节点，每个节点的通信范围为20 m，节点之间的传输概率是根据距离大小随机产生的(图4的仿真除外)，每个数据包的大小为M=1000 byte，数据包传输一次用时为t=0.1 s。

理论上我们的MinACK和MORE传输相同数量的数据包的情况下，他们的传输次数是相同的，图3、图4均证明了这一点。我们的优势主要在于MinACK能够几段同步传输。图4我们是通过传输50个包，改变节点间的传输成功率(从0.1到0.9变化)统计三者的传输次数得到的。从仿真结果看节点间的传输成功率越低，MinACK和MORE的优势较之ExOR就越明显；图5我们是通过改变传输包的个数，而节点间的传输概率不变得到的。总体上都是随着数据包的增多，传输次数相应的平稳增加，但在相同条件下MinACK、MORE需要的传输次数比ExOR要少。

图4 MinACK、MORE和ExOR的传输次数随节点间的传输成功的概率的变化对比

图5 MinACK、MORE和ExOR的传输次数随传输的包的个数变化对比

另外，网络中多段数据包同步传输是MinACK协议的最重要的特征，因此我们对网络中存在的段数进行了仿真测试。我们将每段数据包的个数设为10到100之间，分别测试网络中平均存在的段数，并与理论值做了对比，效果如图6所示，从仿真结果看，MinACK网络中平均存在3段左右的数据包在同步发送，而我们知道MORE网络中始终只存在一段数据包，因此MinACK应该比MORE的吞吐量性能好，接下来的吞吐量仿真也充分证明了这一点。

图6 MinACK在网络中存在的段数与理论值对比

最后，吞吐量性能是所有网络协议要考虑的重要特性之一，因此我们也对吞吐量性能进行了仿真实验，仿真结果如图7和图8所示。

图7 MinACK、MORE和ExOR的吞吐量随每段中数据包的个数变化对比

图8 MinACK、MORE和ExOR的吞吐量随传输的包的个数的变化对比

图7是我们通过传输500个数据包，让K(每段中数据包的个数)从10到100之间变化得到的，从仿真结果看随着K的增大，三者的吞吐量相差越来越小；图8中K固定为50，通过改变传输数据包的个数得到的，从仿真结果可以看出，三者的吞吐量随传输包的个数变化不大。在K较小的新情况下，MORE的吞吐量大概是ExOR的1.2倍左右，MinACK的吞吐量大概是MORE的1.2倍左右，是ExOR的的1.45倍左右，可见吞吐量性能有了不少的提高。

5 小结

本文提出了一种基于网络编码的机会路由算法－MinACK，它结合了网络编码与机会路由的优点，通过在网络中同时传输多个数据段，提高了网络的吞吐量。同时分析了网络中同时传输的数据段数和网络吞吐量等性能。

不同的网络中数据流有自己的特点，比如数据包的到达服从某种分布。如何利用网络编码，结合数据流的特点定量化地研究无线网络的传输机制是作者下一步要研究的内容。

［1］程大伟，赵海，张希元，等.基于EWMA的无线传感器网络路由度量性研究［J］.传感技术学报，2008，21(1):103－108.

［2］Garcia P J，Duato J，Flich J，et al.Cost-Effective Congestionmanagement for Interconnection Networks Using Distributed Deterministic Routing［C］//IEEE，International Conference on，Parallel and Distributed Systems，Univ of Castilla-La Mancha，Albacete，Spain，Dec 2010:355－364.

［3］程远国，李国徽.一种面向目标跟踪应用的传感器网络路由协议［J］.传感技术学报，2008，21(10):1744－1749.

［4］Biswas S，Morris R.Opportunistic Routing in Multi-Hop Wireless Networks［J］.In ACM SIGCOMM Computer ommunications Review，Jan 2004，34(1):69－74.

［5］Biswas S，Morris R.ExOR:Opportunistic Multi-Hop Routing for Wireless Networks［J］.ACM SIGCOMM Computer Communication Review，Aug 2005，35(4):133－144.

［6］Koetter R，M’edard M.An Algebraic Approach to Network Coding［J］.IEEE/ACM Transactionson on Networking，2003，11(5):782－795.

［7］Rozner E，Seshadri J，Mehta Y，et al.Simple Opportunistic Routing Protocol for Wireless Mesh Networks［C］//Proc IEEE Workshop on，Wireless Mesh Networks，Univ of Texas，Austin，Sept 2006:48－54.

［8］Rozner E，Seshadri J，Mebta Y，et al.SOAR:Simple Opportunistic Adaptive Routing Protocol for Wireless Mesh Networks［J］.In IEEE Transactions on Mobile Computing，Dec 2009，8(12):1622－1635.

［9］Jaggi S，Sanders P，Chou P A，et al.Polynomial Time Algorithms for Multicast Network Code Construction［J］.IEEE Transaction on Information Theory，2005，51(6):1973－1982.

［10］Li S Y，Yeung R W，Cai N.Linear Network Coding［J］.IEEE Transactions on Information Theory，2003，49(2):371－381.

［11］Ahlswede R，Cai N，Yeung R W，et al.Network Information Flow［J］.IEEE Transactions on Information Theory，2000，46(4):1204－1216.

［12］熊志强，刘威，程文青，等.基于网络编码的传感器网络信息交换算法研究［J］.传感技术学报，2008，21(1):141－146.

［13］Chachulski S，Jennings M，Katti S，et al.Trading Structure for Randomness in Wireless Opportunistic Routing［J］.ACM SIGCOMM Computer Communication Review，2007，37(4):169－180.

［14］Lin Y F，Li B C，Liang B.CodeOR:Opportunistic Routing in Wireless Mesh Networks with Segmented Network Coding［C］//Proc of IEEE International Conference on，Network Protocols，Univ of Toronto，Canada，Dec 2008:13－22.

［15］Lin Y F，Li B C，Liang B.Slideor:Online Opportunistic Network Coding in Wireless Mesh Networks［C］//IEEE INFOCOM International Conference on，Computer Communications，Univ of Toronto，Toronto，Canada，2010:171－175.

［16］Koutsonikolas D，Wang C C，Hu Y.CCACK:Efficient Network Coding Based Opportunistic Routing Through Cumulative Coded Acknowledgments［C］//IEEE INFOCOM Conference on，Computer Communications，Purdue Univ，West Lafayette，USA，Mar 2010:1－9.

［17］Couto D De，Aguayo D，Bicket J，et al.A High-Throughput Path Metric for Multi-Hop Wireless Routing［J］.ACM/IEEE MobiCom，2003，11(4):419－434.