2015, Vol. 38
2. 国家电网公司 电力科学研究院，北京 100193
2. State Grid, Electric Power Research Institute, Beijing 00193, P.R.China
移动Ad hoc网络(Mobile Ad Hoc Networks，MANETs)中节点具有较强动态性，无法为语音、视频等多媒体业务提供可靠传输，达到令人满意的服务质量[1-3]。应用于其中的传统路由机制，数据包传输前需在源节点和目的节点之间预先建立路径，在数据包转发过程中，一旦路径断裂，则触发路由发现或者维护过程，进行路径重建。在此过程中，数据包将会由于等待路径的建立而无法进行转发。从实际测试结果来看，节点间的链路断裂后，实时业务的分组投递率显著下降，重建路径所耗费的时间使得数据包的端到端时延超过业务门限值，导致网络无法承载实时业务。
区别于传统路由机制，机会路由机制的最大特点是数据包不再按照指定的路径转发，而是充分利用无线信道的广播特性，使部分能够监听到数据包的中间节点参与数据包的转发，并通过一定的机制，利用这些节点将数据包以最快的速度转发到目的节点[4]。这样，可以充分利用中间节点的转发能力，通过动态地选择转发节点来适应无线信道的不稳定特性，进而从根本上提高端到端网络的可靠性[5]。
文献[6]提出了一种机会路由机制利用节点的本地邻居节点完成消息的路由。在路由过程中分别考察节点与消息目的节点的距离以及节点将消息转发给邻居节点的成功率，从而选择消息的中继节点。文献[7]通过将机会路由与网络编码相联合，增加了网络中端到端的吞吐量，从理论上给出了两节点间双向通信时数据转发条数的最优选择方案。文献[8]提出了一种结合机会路由和网络编码的机制，数据包在中间节点被随机编码，该机制不需要特殊的调度机制。该机制同样基于ETX概念，每个节点计算各条链路的投递率的过程，会导致网络中探测包数量的增加，开销过大。文献[9]提出了适用于无线Mesh网络的调节机会路由策略(CORP-M)，它采用了一种基于位置的机会路由策略，优先选择距离目标节点更近的节点，作为消息的转发节点。文献[10]提出了一种移动Ad hoc网络中的协作机会路由(CORMAN)，它将机会路由的应用环境由多跳无线网络扩展到移动Ad hoc网络。文献[11]提出了一种使用离散时间的Markov链模型来描述成功传输所需的传输次数的机会路由机制。文献[12]针对Ad hoc网络中机会路由采用贪婪转发策略会引起无后续转发节点的现象，提出了在机会路由中考虑后续路径的转发机制(CFP)，将转发节点与目的节点的距离以及节点的后续转发路径同时作为路由决策的依据。
以上路由方法虽然为无线网络中的机会路由提供了多种解决方式，但是都没有考虑到在不同环境和网络要求下，如何为消息的传递提供QOS保障。在真实环境中，节点传输的带宽、缓存和能量等资源都是有限的，同时，无线信号的传输信道易受外界因素的影响，信道质量无法得到保证。针对上述问题, 利用无线网络的广播特性，笔者提出一种适用于在无线信道质量较差情况下，能够满足实时语音业务的机会路由机制，通过为转发列表中的节点设置不同的优先级，有效降低转发数据包的数量。
1 机会路由机制在无线自组织网络中，节点之间距离不同，导致信噪比不同，进而数据包成功传输概率也将出现差别，如图 1所示。若采用传统路由机制，则数据包沿路径S-B-D转发。当节点B无法成功接收来自节点S的数据包时，则节点S将会重发该数据包，直到B成功接收或者达到预先设定的最大重传次数。在此过程中，即使A或C收到该包，也会将该包丢弃。若采用机会路由机制，节点S在向节点B发送数据过程中，节点A可以在监听到节点S的数据包之后为其转发，若C可以收到S的数据包，则可以直接向D转发，即以“尽力而为”的方式，通过成功接收数据包的节点转发数据，避免路径S-B-D断裂而造成的频繁建路和重传。
|
图 1 数据包转发机制比较 Figure 1 Illustration of packet forwarding mechanisms |
提出了一种适用于实时语音业务的机会路由机制，以提高实时多媒体业务的服务质量。如前所述，无线信道受到多径效应和各种干扰的影响，节点间的分组投递率随着距离的增加而减小，为明确表明两者之间的关系，首先建立仿真场景进行模拟并分析，由于受到多径效应的影响，此场景中的信道状态非常不稳定，传统路由机制需要频繁建立路由。节点之间的距离与分组投递率的关系如图 2所示。
|
图 2 距离和投递率关系 Figure 2 Delivery ratio vs. distances |
从图中结果可知，若节点间距离小于200 m，则分组投递率较高，当节点距离大于200 m，且小于380 m的时候，投递率迅速降低，当节点间距离超过380 m的时候，投递率为零。利用无线信道的广播特性，机会路由采用距离较远且分组投递率不为零的链路，高效地转发数据包，如间距200~380 m之间的链路。
机会路由机制仅借助路由请求(route request，RREQ)和路由应答(route reply，RREP)消息来建立转发列表，且只有转发列表中的节点参与机会路由机制。由于信道的不稳定性，目的节点向源节点回复的RREP可能经过不同的路径，通过限制RREP消息的数量，并从转发过RREP的节点中合理地选择机会转发节点，以限制参与机会路由机制的节点数量。传统路由方法采用最短路径优先算法建立端到端路径，机会转发节点也将分布在传统路由机制建立的最短路径附近，如图 3所示。
|
图 3 机会路由机制的转发节点示意图 Figure 3 Illustration of relay nodes in opportunistic routing mechanisms |
转发列表中保存机会转发节点的地址，如上所述，需要有多个RREQ和RREP来收集这些节点的地址。考虑到RREQ和RREP节点在转发途中的丢失情况，每个节点需转发多个RREQ、且目的节点也需发送多个RREP。此外，源节点同样需要限制收到的RREP数量，避免机会转发节点数量过多。为了对各个节点处理的RREQ和RREP进行计数，需要在每个节点建立一个哈希表存储各个计数器，表中各条目以目的地址为索引。提出的机会路由机制并不需要建立端到端路径，因此，不需要传统路由机制中的路由维护机制。
1.2.1 RREQ消息处理过程当中间节点收到RREQ消息时，首先检查是否在本地的哈希表中存在对应的条目，若存在，则该节点需要对所收到RREQ的RequestId与当前值进行比较。RequestId的值越大表明这个RREQ越新，然后设置NewRREQ标志位为TRUE，并且更新RequestId。计数器RREQCounter加一，记录相同RequestId的RREQ个数，以限制每个节点处理的RREQ个数。
此外，中间节点还需判断RREQCounter是否超过TRREQ_I，该值为限制中间节点转发RREQ数量的门限值。不同场景下TRREQ_I的值不同，在本文的场景中，设置其值为3，这样在目的节点大约能够收到10个RREQ消息；同时，目的节点同样需要设置门限值TRREQ_D来限制所收到RREQ的数量，此处该值设置为10，即目的节点最多向源节点回复10个RREP。
1.2.2 RREP消息处理过程考虑到RREP可能在转发过程中丢失，目的节点为源节点回复多个RREP消息，以使其能够建立转发列表。RREQ处理过程中的NewRREQ标志位可以在RREP处理过程中使用，源节点只处理并记录同一轮的转发列表建立过程中的RREP，每当收到新一轮的RREP之后，启动定时器RREPTimer，以确保源节点在无法收到足够数量的RREP时，也能触发转发列表建立过程。源节点在收到TRREP_S个RREP或者RREPTimer定时器结束，都能触发转发列表建立过程，TRREP_S为源节点处理RREP数量的门限值。同时，源节点在本地存储RREPSourceList表来保存RREP消息沿途所经过的节点地址。
1.3 转发列表中节点优先级分配RREPSourceList内所有中间节点的地址经过源节点的筛重之后得到一个转发列表，列表内的地址使得每个中间节点都可以区分自己是不是中间转发节点，并且确定节点的优先级，转发列表被放置在位于各个数据包的包头位置。若转发列表中的每个节点均转发数据包，则可能距离目的节点较近的节点已经转发过数据包，同时, 离目的较远的节点可能会重复转发，这样网络中将出现较大部分的冗余数据包。因此，笔者为转发列表中的节点分配优先级，以限制转发数据包的数量。
每个中间转发节点跟目的节点间的相应位置可以根据该节点位于RREP消息内的位置来确定。可确定该节点与目的节点之间的相对位置，离目的节点越近，则优先级越高，其拓扑结构如图 4(a)所示，假设Src节点收到5个RREP，图 4(b)表示各个RREP中携带的转发节点地址，进行以下步骤：
|
图 4 基于优先级的转发列表建立过程 Figure 4 Establishing procedure of the priority forwarding list |
统计所有RREP内中间转发节点的数量，并计算平均值，本例中，该值为3。通过统计RREP 1、2和3，得到中间转发节点的数量为3，等于平均值，因此，按照图 4(c)方式分配优先级，并遵循每个优先级一个节点，优先级递增的原则。
对于其他RREP，从目的侧开始，选取第一个转发节点，并分配最高优先级，然后从源节点侧选取第一个转发节点分配最低优先级，以此类推，若分配到最优一个优先级时剩余节点数多于一个，则为这些节点均分配该剩余优先级。
最后，去掉重复节点，若同一节点被分配多个优先级，则取低优先级。按照上述操作过程，得到如图 4(d)所示结果，优先级分配完毕。
1.4 数据包处理过程为了提高单次传输的可靠性，机会转发节点均可转发已经成功接收的数据包，同时，为各个数据包增加相应的序列号，以防数据包经过广播后数量剧增，则各个机会转发节点对序列号相同的数据包只转发一次，且优先级低的转发节点不再转发已被优先级高的节点转发过的数据包，从而有效地减少了转发数据包的数量。
笔者的机会路由机制并未采用ExOR机制中的时间调度方法，该方法将各个转发节点均设置了定时器，以确保同一时刻仅有唯一节点在转发数据包，可以避免同一个流内的数据包碰撞，并且能够防止数据包经过广播后数量剧增。然而，在多个数据流并发的情况下，带有定时器的ExOR机制并不能有效运行，原因是数据流不同则其转发节点也各不相同，定时器可能导致这些转发节点在同一时刻转发数据包，由此导致某些时刻产生严重碰撞。因此，本文的机会路由机制并未采取时间调度方法，多个流的数据包在MAC层通过竞争信道获得发送机会[13]。
为了提供对多个数据流的支持，每个节点为各个数据流保存处理数据包列表(processed packet list)以记录转发过数据包的序号，且这些列表随转发列表进行更新。
1.5 转发列表的维护机制节点随机移动导致网络拓扑出现变化，机会转发节点可能由于脱离网络而中断数据包转发，或者产生新的机会转发节点，因此，需设计相应的转发列表维护机制。显然，所设计的机制进行数据包转发时并没有采用固定的路由，链路的断裂并不影响数据转发。与传统路由机制中的维护方法不同，所提出的机制利用周期性发送RREQ的方式来更新转发列表。可见，少数转发节点的变化并不会影响数据包正常转发，因此，转发列表维护周期可以设置得较长。由于没有路由维护的开销，机会路由机制的控制包数量远小于传统路由机制。
2 仿真分析为了验证所提出的ORVS (opportunistic routing for voice service)机制对实时语音业务提供的服务质量保证情况，笔者采用OPNET平台对其进行了性能仿真。由于DSR协议采用源路由的方式，在每一个数据包的头部都预先放入了它从源节点到目的节点的完整路由信息，是典型的预先建立连接的路由协议，它与ORVS机制分别代表了两种截然不同的路由方式，因而选择了DSR与ORVS机制的性能进行比较。由于ExOR等相关工作并不支持多个并发的数据流，因此，无法将其与所提出的机制进行比较。
无线链路速率为54 Mb/s，语音流大小为8 kb/s，30个节点均匀分布在大小为2 000 m×2 000 m的场景，节点使用全向天线，节点间无障碍物遮挡，传输范围最大可达380 m，数据流数量从1增加到8。多径效应将使得静态拓扑情况下链路也并不稳定，因此，运动场景和静止场景性能差别不大，链路的平均分组投递率仅为50%左右。
仿真时间为500 s，此时网络状态能够达到稳定状态。仿真结果取10次的平均值，来消除随机因素的影响。
2.1 平均转发节点个数DSR和ORVS的平均转发节点个数如图 5所示，对于DSR来说，路径中平均节点的个数为4.7，对于ORVS来说，机会转发节点的个数为8.58，即ORVS参与一个数据流转发的节点个数要多于DSR。DSR采用最短路径机制，每当路径断裂需要重新建立的时候，所建立的路径跳数基本差距不大。而ORVS机制充分利用源和目的之间能够转发的节点，不指定下一跳，因此，所需机会转发节点数量要多于DSR，也就决定了下述性能参数的差异。
|
图 5 平均转发节点个数 Figure 5 Average number of relay nodes vs. flow number |
如图 6所示，DSR机制的平均端到端时延为102.65 ms，但ORVS机制的端到端时延只有10.54 ms，约为DSR的1/10，其主要原因在于机会路由机制可以利用分组投递率不高但长度较长的链路来转发数据包，从而使其以最短的时间到达目的节点。而DSR只在事先建立的路径上转发数据包，当由于无线链路的不稳定特性导致路径频繁建立时，数据包需要等待端到端路径完成建立，消耗过多的等待时间。随着数据流的数量持续增加，则使用DSR机制的端到端时延将超过语音业务的门限值，使得语音业务的服务质量无法得到保证。
|
图 6 端到端时延和分组投递率 Figure 6 End-to-end delay and packet delivery ratio vs. flow number |
如图 6所示，当数据流数量不超过4个的时候，DSR和ORVS机制的分组投递率均高于90%，语音业务的服务质量可以得到有效保证。随着数据流数量增加至8个，采用ORVS机制依然可以保证网络的分组投递率高于90%，而DSR机制下，只能支持4个数据流，机会路由机制的优势得到直接体现，即同样的约束条件下，能够支持比传统路由机制更多的数据流。
2.4 发送RREQ数量如图 7所示，DSR和ORVS机制所需发送的RREQ的数量相差较大，仿真过程中机会路由机制的转发列表更新间隔被设置为100 s，由于转发列表的建立和更新是通过发送RREQ和RREP机制实现的，因此，ORVS机制所需RREQ的数量是固定的，且与数据流的数量成正比。而DSR机制中，每次路径断裂都会触发路由发现过程，因此，所需的RREQ数量远大于ORVS机制。
|
图 7 RREQ数量和控制包数量 Figure 7 Number of RREQ packets and number of control packets vs. flow number |
从图 7可以看出，ORVS机制所需的控制包数量(包括RREQ、RREP和路由错误(RERR)消息等)远小于DSR机制，根本原因是ORVS机制无需维护路由表，数据包的转发过程并不取决于路由表，而是所建立的转发列表，因此，所需的控制包数量远小于DSR机制。此外，控制包同样和数据包竞争无线信道，并且还会与数据包发生碰撞，因此，ORVS机制很好地限制了控制包的数量，网络性能优于DSR机制。
2.6 节点转发数据包比例不同距离的节点转发总数据包的百分比可以直接描述传统路由与机会路由机制的差异，如图 8所示。为了简化分析，选取一对源和目的节点，其距离大约为1 000 m，由图中可以看出，DSR机制的平均路径长度为4，需要3个中间节点协助转发，由于无线网络的动态特性，通信所需的端到端路径需要根据实际状况进行更新，因此，节点缓存中的数据包不一定能够得到全部转发。尽管每次更新后的端到端路径中的节点不完全相同，然而这些节点的位置都接近于最短路径。而ORVS机制充分利用源和目的节点之间的机会转发节点，由于每个机会转发节点最多可以转发同一个数据包一次，因此，每个节点转发的数据包比例很大。
|
图 8 节点转发数据包比例 Figure 8 Proportion of forwarded packets vs. distance |
由于ORVS机制的数据包采用广播方式，在MAC层没有重传。而在链路质量较差的情况下，DSR机制的单播数据包在MAC层会经历多次重传，所需要的总发送次数会比ORVS机制多，因此，ORVS机制更适用于实际环境。
3 结语针对多跳无线网络下语音业务，提出了一种机会路由机制，以在链路质量较差的环境下提供优于传统路由机制的服务质量。该机制利用传统路由机制中的路由请求和路由应答消息建立转发列表，负责数据包转发。由于没有严格的时间调度机制，在多个数据流并发的情况下，笔者提出的机会路由机制也可以有效运行。结果表明，与传统机制相比，使用所提出的路由机制，得到的分组投递率更高，端到端时延更低，同时有效地减少了控制包的数量，因此，所提出的机会路由机制能够在保证特定服务质量的情况下支持更多并发的数据流。同时，所提出的机制较容易实现，能够应用于实际测试平台，有效克服实际应用中因无线信道的动态特性所导致的路由频繁建立的现象，防止业务在路由建立过程中被阻塞，影响服务质量。
| [1] | Kim M R, Yoo S J. Distributed coordination protocol for ad hoc cognitive radio networks[J]. Journal of Communications and Networks, 2012, 14(1): 51–62. DOI:10.1109/JCN.2012.6184551 |
| [2] | Panichpapiboon S, Pattara-Atikom W. A review of information dissemination protocols for vehicular ad hoc networks[J]. Communications Surveys & Tutorials, IEEE, 2012, 14(3): 784–798. |
| [3] |
唐夲, 刘改霞, 钟汶娟, 等.
移动ad hoc网络多参数加权分簇算法[J]. 重庆大学学报, 2014, 37(2): 106–112.
TANG Hui, LIU Gaixia, ZHONG Wenjuan, et al. Mobile AD hoc network multiparameter weighted clustering algorithm[J]. Journal of Chongqing university, 2014, 37(2): 106–112. (in Chinese) |
| [4] |
王博, 陈训逊.
Ad hoc网络中一种基于信任模型的机会路由算法[J]. 通信学报, 2013, 34(9): 92–104.
WANG Bo, CHEN Xunxun. Ad hoc network an opportunity routing algorithm based on trust model[J]. Journal of Communications, 2013, 34(9): 92–104. (in Chinese) |
| [5] |
田克, 张宝贤, 马建, 等.
无线多跳网络中的机会路由[J]. 软件学报, 2010, 10(21): 2542–2553.
TIAN Ke, ZHANG Baoxian, MA Jian, et al. Wireless more opportunities to jump in the network routing[J]. Journal of software, 2010, 10(21): 2542–2553. (in Chinese) |
| [6] | Darehshoorzadeh A, Cerda-Alabern L. Distance progress based opportunistic routing for wireless mesh networks[C]//Wireless Communications and Mobile Computing Conference (IWCMC), 2012 8th International. IEEE, 2012: 179-184. |
| [7] | Mehmood T, Libman L, Dehkordi H R, et al. Optimal opportunistic routing and network coding for bidirectional wireless flows[J]. Computer Networks, 2013, 57(18): 4030–4046. DOI:10.1016/j.comnet.2013.10.004 |
| [8] | Katti S, Rahul H, Hu W J, et al. XORs in the Air: Practical Wireless Network Coding[J]. IEEE/ACM Transactions on Networking, 2008, 16(3): 497–510. DOI:10.1109/TNET.2008.923722 |
| [9] | Ajmal M M, Madani S A, Maqsood T, et al. Coordinated opportunistic routing protocol for wireless mesh networks[J]. Computers & Electrical Engineering, 2013, 39(8): 2442–2453. |
| [10] | Wang Z, Chen Y, Li C. CORMAN: A novel cooperative opportunistic routing scheme in mobile ad hoc networks[J]. IEEE Journal on Selected Areas in Communications, 2012, 30(2): 289–296. DOI:10.1109/JSAC.2012.120207 |
| [11] | Lu M H, Steenkiste P. Video transmission over wireless multihop networks using opportunistic routing [C]//16th International Packet Video Workshop, 2007. |
| [12] |
聂志, 刘静, 甘小莺, 等.
移动Ad Hoc网络中机会路由转发策略的研究[J]. 重庆邮电大学学报:自然科学版, 2010, 22(4): 421–425.
NIE Zhi, LIU Jing, GAN Xiaoying, et al. Opportunities in mobile Ad Hoc network routing forwarding strategy study[J]. Journal of chongqing university of posts and telecommunications: natural science edition, 2010, 22(4): 421–425. (in Chinese) |
| [13] | Kim S W, Kim B S, Lee I. MAC protocol for reliable multicast over multi-hop wireless ad hoc networks[J]. Journal of Communications and Networks, 2012, 14(1): 63–74. DOI:10.1109/JCN.2012.6184552 |