彭鑫+魏叶华+欧阳竟成+刘樑骄

收稿日期：2013-05-28

基金项目：国家自然科学基金项目（61173036， 61300039， 61272061）；湖南省教育厅重点项目（12A057）；湖南省高校科技创新团队支持计划（湘教通[2012]318）；中国博士后基金面上项目（2013M542109）；湖南省自然科学基金项目（14JJ3130）

作者简介：彭 鑫（1981—），男，湖南岳阳人，讲师，博士，研究方向：物联网。

通讯联系人，E-mail：yehua366@sohu.com

文章编号：1003-6199（2014）03-0123-03

2.湖南大学 嵌入式与网络计算湖南省重点实验室，湖南 长沙 410082； 3.湖南师范大学 物理与信息科学学院，湖南 长沙 410081）

摘 要：针对多跳无线网络中机会路由的副本传输问题，提出一种新的机会路由协议。提出的策略不再简单采用单跳广播的方式转发数据，而是通过节点间的距离确定转发开销，再让数据包携带下一跳候选节点信息并根据候选节点的ACK选择下一跳节点，从而保证了每个数据包只有一个候选节点进行转发。仿真结果显示，提出的方案能减少不必要的传输行为，有效改善了网络吞吐率。

关键词：多跳无线网络；路由；转发

中图分类号：TP393 文献标识码：A

Routing Protocol with Duplicate Inhibit in Multi-hop Wireless Networks

PENG Xin1，2， WEI Ye-hua3， OUYANG Jing-cheng1， LIU Liang-jiao2

（1.Key Laboratory on Complex Systems Optimization and Controlling of Hunan High Education Institutions， College

of Information and Communication Engineering， Hunan Institute of Science and Technology， Yueyang，Hunan 414000，China；

2.Key Laboratory for Embedded and Network Computing of Hunan Province， Hunan University， Changsha，Hunan 410082，China；

3.Institute of Physics and Information Science， Hunan Normal University， Changsha，Hunan 410081，China）

Abstract：A novel protocol of duplicate elimination in opportunistic routing was introduced. At first we decide the priority of candidate nodes by computing the distance of candidate node among present node and destination node. The protocol allows each node to control relay transmissions of its next hop candidate nodes using information piggybacked on packets. The protocol guarantees that for each packet， only one candidate node that correctly receives the packet can deliver the packet. Simulation results show that the protocol achieves higher throughput than existing opportunistic routing protocols by reducing duplicate packets.

Key words：multi-hop wireless networks； routing；forward

1 引 言

多跳无线网络（Wireless Multi-hop Networks）的机会路由（Opportunistic Routing）[1]过程将数据包转发给多个下一跳候选节点。这种转发模式使得数据产生多个副本，影响网络性能。所以怎样控制网络中的冗余副本成为机会路由研究的热点问题。

ExOR[2]路由协议使每个节点周期性发送探测包，获得相邻链路的ETX（Expected Transmission Count）并进行广播，从而让每个节点获得全部链路的状态。当某节点需要发送数据，采用Dijkstra算法计算自己的邻居到目的ETX，然后选择到目的节点的最短ETX小于自身的节点作为备选节点，并根据其到目的节点的距离设置转发优先级。但是ExOR需要每个节点广播链路消息，网络负载较大，并且缺乏副本控制机制。MORE[3]协议引入流内随机网络编码来降低副本产生的概率。协议对发送的数据进行分批，然后作随机线性编码并广播。中间节点收到数据包后判断是否与本地数据包线性独立，若线性独立则缓存在本地，否则丢弃。CORE[4]协议针对基于局部信息网络编码方案只能被动利用各节点现有的编码机会，将局部流间网络编码应用于机会路由。在确定候选转发节点优先级时，编码机会越大的节点优先级越高，从而确保编码机会多的节点转发数据包。SOAR[5]协议首先建立到目的节点的最短路径，协议以偏离这条路径的跳数作为候选节点的选择参数，并且各候选节点间链路的ETX必须高于一定门限使得候选节点集分布在最短路径附近，减少了副本的产生。MGOR[6]协议的每个节点可以有不同的速率和不同的转发范围，从而导致候选转发节点集和优先级关系的变化。MGOR采用EOT（Expected One-hop Throughput）作为候选节点选择尺度来实现候选节点的选择和传输速率的平衡优化。

本文提出一种满足副本控制要求的机会路由协议。该协议无需候选节点进行任何信息交换，只需当前节点转发数据包时，附带少量控制信息即可指定下一跳候选节点，实现副本控制要求。

2 转发开销的确定

假设每个转发节点知道下一跳候选节点。协议首先确定候选节点的转发开销。如果多个候选节点收到数据包，那么开销低的节点进行转发，这样可有效降低总体传输开销。确定候选节点转发开销首先要确定其优先级，而优先级与链路的可靠性和路由有效性有关。由于链路可靠性与节点间的距离密切相关，本文通过节点距离判定候选节点的优先级。通常节点都能够获取相邻节点间的距离，对于相距较远的节点，只能通过计算得到。本文通过网络拓扑图的确定性求解节点间的距离数据。对于有n个节点的网络，令dij表示节点i和j的距离。建立矩阵P=[pij]n*n，其中如果i和j的距离可以直接测量，那么pij=dij2；如果i和j的距离不能直接测量那么取pij=0，表示距离未知。然后对P进行奇异值分解，并取P的前3个奇异值向量构造P3作为2维空间距离矩阵。如果用C表示节点s的候选节点集，那么应满足条件v∈C，有dvd≤dsd，即候选节点v离节点d的距离要近。节点的优先级排序准则为，候选节点到当前转发节点s和目的节点d的距离之和越小优先级越高。

确定优先级后转发节点的选定以优先级为基础，选择转发开销小的节点。本文通过期望转发时间[7]来确定，令Ts表示当前转发节点s的期望转发时间，则：

Ts=1p（t+∑Cj=1qs（j-1）·ps，C（j）·TC（j）（1）

其中，p表示数据包成功发送的概率，C（j）表示候选节点集中第j优先级的节点，T表示该节点的期望传输时间。Ps，C（j）表示节点C（j）从节点s成功接收数据包的概率，qs（j）表示优先级最高的j个候选节点均未能成功接收数据包的概率。t表示数据包的发送时间。

3 路由协议

当前转发节点s发送数据包后，通过候选节点的ACK确定哪些节点收到了数据包，然后根据转发开销确定下一跳节点。s将相关信息附带在后续数据包上，候选节点则通过数据包携带的信息，确定自己是否应当转发之前收到的数据包。每跳转发依此进行，直到将数据包送达目的节点。假设源节点发送数据包x1，x2，…，xi到目的节点，其中i表示数据包的序号。中间节点为每个候选节点建立局部变量保存数据包的序号以及候选节点的ID。a（u）表示节点s建立的候选节点u的局部变量，变量值为数据包序号，用于告知候选节点u是否转发之前收到第a（u）个数据包。s转发的每个数据包都会插入α（u）。候选节点收到数据包后缓存在本地。对于候选节点u收到数据包，如果发现数据包的a（u）=i，那么u将转发之前缓存的数据包xi。候选节点每接收到一个数据包要向上一跳节点s发送ACK确认。如果没有收到ACK，节点s将会重传。

对于节点s，令Ci表示收到数据包xi的候选节点集，|Ci|=f，Ni表示节点s的邻居节点集，|Ni|=g。Ci（1）表示集合Ci中优先级最高的节点。选择候选节点的关键是节点s如何通过数据包xi完成下一跳节点的选择，也就是让a（Ci1）=i，路由过程如下：

1）候选节点u收到数据包xi，并向s反馈ACK（u）；

2）s收到ACK（u），如果k=u则确认节点u收到xi，设置后续数据包xi+n的α（u）；

3）如果uCi，那么xi+n，α（u）不变；

4）如果u=Ci（1），那么α（Ci（1））=i；

5）如果u∈{v|v∈Ci&v≠Ci（1）}，则α（u）为空；

6）如果α（u）=i则转发xi，否则，缓存。

4 仿真分析

本文通过NS2对提出的协议进行了仿真，并与ExOR和基于地理位置的MGOR协议进行了对比。

在NS2中模拟1000×1000m的仿真区域，布设100个节点。首先，分析三种协议在不同路径长度下的性能，如图1。图中给出了端到端平均传输次数与最短路由路径长度的比值。不难看出本文协议具有较低的传输次数，从而具有较高的吞吐率。图2给出了在不同数据流的条件下，几种协议的吞吐率性能，实验中随机选取源节点和目的节点。不难看出ExOR与MGOR和本文协议有较大差距，而且随数据流的增多，由于虚警率的上升MGOR与本文协议在性能上的差距开始显现。在数据流较少的情况下，本协议的吞吐率相对于ExOR提升70%，相对于MGOR改进11.3%。

5 结 论

本文提出了具有副本控制能力的机会路由协议。提出的协议通过候选节点的距离确定其优先级，然后尽量选择转发时间开销较小的候选节点。协议通过包赋值控制下一跳候选节点的转发，而非通过单跳广播形式进行传输，保证了每个数据包只有一个节点能转发。仿真结果显示协议通过降低不必要的副本开销，显著改善了吞吐率。

参考文献

[1] ZHANG Z. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks： Overview and challenges[J]. IEEE Communications Surveys & Tutorials， 2006，8（1）：24-37.

[2] BISWAS S，MORRIS R. ExOR： opportunistic multi-hop routing for wireless networks[J]. In Proc. of 2005 Conference on Applications， Technologies ， Architectures， and protocols for computer communications （SIGCOMM05） ACM， 2005， 133-144.

[3] CHACHULSKI S，JENNINGS M，KATTI S，KATABI D.Trading structure for randomness in wireless opportunistic routing[J]. In Proc. of 2007 ACM SIGCOMM， 169–180.

[4] YAN Y，ZHANG BX，ZHENG J，MA J. CORE： A coding-aware opportunistic routing mechanism for wireless mesh networks[J]. IEEE Wireless Communications， 2010，17（3）：96-103.

[5] ROZNER E，SESHADRI J，MEHTA Y，QIU L. Simple opportunistic routing protocol for wireless mesh networks[J]. In Proc. of the IEEE WiMesh 2006. Washington： IEEE Computer Society Press， 2006. 48-54.

[6] ZENG K，LOU W，ZHAI H.On end-to-end throughput of opportunistic routing in multirate and multihop wireless networks[J]. In： Proc. of the IEEE INFOCOM 2008. Washington： IEEE Computer Society Press， 2008. 816-824.

[7] LAUFER R，DUBOIS-FERRIERE H，KLEINROCK L. Multirate anypath routing in wireless mesh networks[J]. In Proc. of 2009 IEEE INFOCOM， 2009： 37-45.

本文提出一种满足副本控制要求的机会路由协议。该协议无需候选节点进行任何信息交换，只需当前节点转发数据包时，附带少量控制信息即可指定下一跳候选节点，实现副本控制要求。

2 转发开销的确定

假设每个转发节点知道下一跳候选节点。协议首先确定候选节点的转发开销。如果多个候选节点收到数据包，那么开销低的节点进行转发，这样可有效降低总体传输开销。确定候选节点转发开销首先要确定其优先级，而优先级与链路的可靠性和路由有效性有关。由于链路可靠性与节点间的距离密切相关，本文通过节点距离判定候选节点的优先级。通常节点都能够获取相邻节点间的距离，对于相距较远的节点，只能通过计算得到。本文通过网络拓扑图的确定性求解节点间的距离数据。对于有n个节点的网络，令dij表示节点i和j的距离。建立矩阵P=[pij]n*n，其中如果i和j的距离可以直接测量，那么pij=dij2；如果i和j的距离不能直接测量那么取pij=0，表示距离未知。然后对P进行奇异值分解，并取P的前3个奇异值向量构造P3作为2维空间距离矩阵。如果用C表示节点s的候选节点集，那么应满足条件v∈C，有dvd≤dsd，即候选节点v离节点d的距离要近。节点的优先级排序准则为，候选节点到当前转发节点s和目的节点d的距离之和越小优先级越高。

确定优先级后转发节点的选定以优先级为基础，选择转发开销小的节点。本文通过期望转发时间[7]来确定，令Ts表示当前转发节点s的期望转发时间，则：

Ts=1p（t+∑Cj=1qs（j-1）·ps，C（j）·TC（j）（1）

其中，p表示数据包成功发送的概率，C（j）表示候选节点集中第j优先级的节点，T表示该节点的期望传输时间。Ps，C（j）表示节点C（j）从节点s成功接收数据包的概率，qs（j）表示优先级最高的j个候选节点均未能成功接收数据包的概率。t表示数据包的发送时间。

3 路由协议

当前转发节点s发送数据包后，通过候选节点的ACK确定哪些节点收到了数据包，然后根据转发开销确定下一跳节点。s将相关信息附带在后续数据包上，候选节点则通过数据包携带的信息，确定自己是否应当转发之前收到的数据包。每跳转发依此进行，直到将数据包送达目的节点。假设源节点发送数据包x1，x2，…，xi到目的节点，其中i表示数据包的序号。中间节点为每个候选节点建立局部变量保存数据包的序号以及候选节点的ID。a（u）表示节点s建立的候选节点u的局部变量，变量值为数据包序号，用于告知候选节点u是否转发之前收到第a（u）个数据包。s转发的每个数据包都会插入α（u）。候选节点收到数据包后缓存在本地。对于候选节点u收到数据包，如果发现数据包的a（u）=i，那么u将转发之前缓存的数据包xi。候选节点每接收到一个数据包要向上一跳节点s发送ACK确认。如果没有收到ACK，节点s将会重传。

对于节点s，令Ci表示收到数据包xi的候选节点集，|Ci|=f，Ni表示节点s的邻居节点集，|Ni|=g。Ci（1）表示集合Ci中优先级最高的节点。选择候选节点的关键是节点s如何通过数据包xi完成下一跳节点的选择，也就是让a（Ci1）=i，路由过程如下：

1）候选节点u收到数据包xi，并向s反馈ACK（u）；

2）s收到ACK（u），如果k=u则确认节点u收到xi，设置后续数据包xi+n的α（u）；

3）如果uCi，那么xi+n，α（u）不变；

4）如果u=Ci（1），那么α（Ci（1））=i；

5）如果u∈{v|v∈Ci&v≠Ci（1）}，则α（u）为空；

6）如果α（u）=i则转发xi，否则，缓存。

4 仿真分析

本文通过NS2对提出的协议进行了仿真，并与ExOR和基于地理位置的MGOR协议进行了对比。

在NS2中模拟1000×1000m的仿真区域，布设100个节点。首先，分析三种协议在不同路径长度下的性能，如图1。图中给出了端到端平均传输次数与最短路由路径长度的比值。不难看出本文协议具有较低的传输次数，从而具有较高的吞吐率。图2给出了在不同数据流的条件下，几种协议的吞吐率性能，实验中随机选取源节点和目的节点。不难看出ExOR与MGOR和本文协议有较大差距，而且随数据流的增多，由于虚警率的上升MGOR与本文协议在性能上的差距开始显现。在数据流较少的情况下，本协议的吞吐率相对于ExOR提升70%，相对于MGOR改进11.3%。

5 结 论

本文提出了具有副本控制能力的机会路由协议。提出的协议通过候选节点的距离确定其优先级，然后尽量选择转发时间开销较小的候选节点。协议通过包赋值控制下一跳候选节点的转发，而非通过单跳广播形式进行传输，保证了每个数据包只有一个节点能转发。仿真结果显示协议通过降低不必要的副本开销，显著改善了吞吐率。

参考文献

[1] ZHANG Z. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks： Overview and challenges[J]. IEEE Communications Surveys & Tutorials， 2006，8（1）：24-37.

[2] BISWAS S，MORRIS R. ExOR： opportunistic multi-hop routing for wireless networks[J]. In Proc. of 2005 Conference on Applications， Technologies ， Architectures， and protocols for computer communications （SIGCOMM05） ACM， 2005， 133-144.

[3] CHACHULSKI S，JENNINGS M，KATTI S，KATABI D.Trading structure for randomness in wireless opportunistic routing[J]. In Proc. of 2007 ACM SIGCOMM， 169–180.

[4] YAN Y，ZHANG BX，ZHENG J，MA J. CORE： A coding-aware opportunistic routing mechanism for wireless mesh networks[J]. IEEE Wireless Communications， 2010，17（3）：96-103.

[5] ROZNER E，SESHADRI J，MEHTA Y，QIU L. Simple opportunistic routing protocol for wireless mesh networks[J]. In Proc. of the IEEE WiMesh 2006. Washington： IEEE Computer Society Press， 2006. 48-54.

[6] ZENG K，LOU W，ZHAI H.On end-to-end throughput of opportunistic routing in multirate and multihop wireless networks[J]. In： Proc. of the IEEE INFOCOM 2008. Washington： IEEE Computer Society Press， 2008. 816-824.

[7] LAUFER R，DUBOIS-FERRIERE H，KLEINROCK L. Multirate anypath routing in wireless mesh networks[J]. In Proc. of 2009 IEEE INFOCOM， 2009： 37-45.

本文提出一种满足副本控制要求的机会路由协议。该协议无需候选节点进行任何信息交换，只需当前节点转发数据包时，附带少量控制信息即可指定下一跳候选节点，实现副本控制要求。

2 转发开销的确定

假设每个转发节点知道下一跳候选节点。协议首先确定候选节点的转发开销。如果多个候选节点收到数据包，那么开销低的节点进行转发，这样可有效降低总体传输开销。确定候选节点转发开销首先要确定其优先级，而优先级与链路的可靠性和路由有效性有关。由于链路可靠性与节点间的距离密切相关，本文通过节点距离判定候选节点的优先级。通常节点都能够获取相邻节点间的距离，对于相距较远的节点，只能通过计算得到。本文通过网络拓扑图的确定性求解节点间的距离数据。对于有n个节点的网络，令dij表示节点i和j的距离。建立矩阵P=[pij]n*n，其中如果i和j的距离可以直接测量，那么pij=dij2；如果i和j的距离不能直接测量那么取pij=0，表示距离未知。然后对P进行奇异值分解，并取P的前3个奇异值向量构造P3作为2维空间距离矩阵。如果用C表示节点s的候选节点集，那么应满足条件v∈C，有dvd≤dsd，即候选节点v离节点d的距离要近。节点的优先级排序准则为，候选节点到当前转发节点s和目的节点d的距离之和越小优先级越高。

确定优先级后转发节点的选定以优先级为基础，选择转发开销小的节点。本文通过期望转发时间[7]来确定，令Ts表示当前转发节点s的期望转发时间，则：

Ts=1p（t+∑Cj=1qs（j-1）·ps，C（j）·TC（j）（1）

其中，p表示数据包成功发送的概率，C（j）表示候选节点集中第j优先级的节点，T表示该节点的期望传输时间。Ps，C（j）表示节点C（j）从节点s成功接收数据包的概率，qs（j）表示优先级最高的j个候选节点均未能成功接收数据包的概率。t表示数据包的发送时间。

3 路由协议

当前转发节点s发送数据包后，通过候选节点的ACK确定哪些节点收到了数据包，然后根据转发开销确定下一跳节点。s将相关信息附带在后续数据包上，候选节点则通过数据包携带的信息，确定自己是否应当转发之前收到的数据包。每跳转发依此进行，直到将数据包送达目的节点。假设源节点发送数据包x1，x2，…，xi到目的节点，其中i表示数据包的序号。中间节点为每个候选节点建立局部变量保存数据包的序号以及候选节点的ID。a（u）表示节点s建立的候选节点u的局部变量，变量值为数据包序号，用于告知候选节点u是否转发之前收到第a（u）个数据包。s转发的每个数据包都会插入α（u）。候选节点收到数据包后缓存在本地。对于候选节点u收到数据包，如果发现数据包的a（u）=i，那么u将转发之前缓存的数据包xi。候选节点每接收到一个数据包要向上一跳节点s发送ACK确认。如果没有收到ACK，节点s将会重传。

对于节点s，令Ci表示收到数据包xi的候选节点集，|Ci|=f，Ni表示节点s的邻居节点集，|Ni|=g。Ci（1）表示集合Ci中优先级最高的节点。选择候选节点的关键是节点s如何通过数据包xi完成下一跳节点的选择，也就是让a（Ci1）=i，路由过程如下：

1）候选节点u收到数据包xi，并向s反馈ACK（u）；

2）s收到ACK（u），如果k=u则确认节点u收到xi，设置后续数据包xi+n的α（u）；

3）如果uCi，那么xi+n，α（u）不变；

4）如果u=Ci（1），那么α（Ci（1））=i；

5）如果u∈{v|v∈Ci&v≠Ci（1）}，则α（u）为空；

6）如果α（u）=i则转发xi，否则，缓存。

4 仿真分析

本文通过NS2对提出的协议进行了仿真，并与ExOR和基于地理位置的MGOR协议进行了对比。

在NS2中模拟1000×1000m的仿真区域，布设100个节点。首先，分析三种协议在不同路径长度下的性能，如图1。图中给出了端到端平均传输次数与最短路由路径长度的比值。不难看出本文协议具有较低的传输次数，从而具有较高的吞吐率。图2给出了在不同数据流的条件下，几种协议的吞吐率性能，实验中随机选取源节点和目的节点。不难看出ExOR与MGOR和本文协议有较大差距，而且随数据流的增多，由于虚警率的上升MGOR与本文协议在性能上的差距开始显现。在数据流较少的情况下，本协议的吞吐率相对于ExOR提升70%，相对于MGOR改进11.3%。

5 结 论

本文提出了具有副本控制能力的机会路由协议。提出的协议通过候选节点的距离确定其优先级，然后尽量选择转发时间开销较小的候选节点。协议通过包赋值控制下一跳候选节点的转发，而非通过单跳广播形式进行传输，保证了每个数据包只有一个节点能转发。仿真结果显示协议通过降低不必要的副本开销，显著改善了吞吐率。

参考文献

[1] ZHANG Z. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks： Overview and challenges[J]. IEEE Communications Surveys & Tutorials， 2006，8（1）：24-37.

[2] BISWAS S，MORRIS R. ExOR： opportunistic multi-hop routing for wireless networks[J]. In Proc. of 2005 Conference on Applications， Technologies ， Architectures， and protocols for computer communications （SIGCOMM05） ACM， 2005， 133-144.

[3] CHACHULSKI S，JENNINGS M，KATTI S，KATABI D.Trading structure for randomness in wireless opportunistic routing[J]. In Proc. of 2007 ACM SIGCOMM， 169–180.

[4] YAN Y，ZHANG BX，ZHENG J，MA J. CORE： A coding-aware opportunistic routing mechanism for wireless mesh networks[J]. IEEE Wireless Communications， 2010，17（3）：96-103.

[5] ROZNER E，SESHADRI J，MEHTA Y，QIU L. Simple opportunistic routing protocol for wireless mesh networks[J]. In Proc. of the IEEE WiMesh 2006. Washington： IEEE Computer Society Press， 2006. 48-54.

[6] ZENG K，LOU W，ZHAI H.On end-to-end throughput of opportunistic routing in multirate and multihop wireless networks[J]. In： Proc. of the IEEE INFOCOM 2008. Washington： IEEE Computer Society Press， 2008. 816-824.

[7] LAUFER R，DUBOIS-FERRIERE H，KLEINROCK L. Multirate anypath routing in wireless mesh networks[J]. In Proc. of 2009 IEEE INFOCOM， 2009： 37-45.