基于情景感知的移动Ad Hoc网络自适应路由协议

周欣欣，余镇危

（1.东北电力大学 信息工程学院，吉林 吉林132012；2.中国矿业大学 （北京）

机电与信息工程学院，北京100083）

0 引 言

目前许多移动Ad Hoc网络的研究大多基于一种假设，即任意时刻发送方到接收方都存在至少一条连通路径，而在实际应用中，由于节点移动性和随机性必然会导致网络出现 “孤岛”现象，从而导致数据传输出现较大时延，降低网络可用性。因此，如何在具有间歇连通特性的移动Ad Hoc网络实现快速通信，仍然是当前该领域的重点研究内容［1－4］。

针对以上问题，本文提出一个具有情景感知的自适应路由协议 （adaptive routing protocol based on context－aware，ARPBC），主要思想是在网络出现 “孤岛”时，选择具有最佳传输概率的节点作为携带数据分组的中继节点，当中继节点移动到目的节点所在的连通域时，以多跳方式将数据分组转发给接收节点。ARPBC 协议定义了情景信息效用函数，利用预测理论和多准则决策理论对情景信息进行预测和评价，计算出节点综合传输概率值。该协议不需要节点了解任何地理位置信息，并且数据分组在网络中仅有单一副本，能够大大节省网络带宽资源。

1 ARPBC协议设计

1.1 协议概述

为了更好地理解ARPBC协议，首先考虑以下情景，两组节点的连通情况如图1所示形成两个连通域 （假设在连通域内节点使用目标序列距离矢量 （DSDV）［5］路由算法并以多跳方式进行数据传输）。节点H1想要发送数据到H8，由于发送节点和接收节点分别位于两个网络 “孤岛”内，二者无法以多跳方式完成通信。假设各节点的传输概率如图1所示，由于连通域1中H2具有最高的传输概率，因此，该数据分组被转发给H2 节点并存储在其缓冲区中。随着节点移动，当H2移动到H8所在的连通域2时，如图2所示，H2接收到H8的路由信息，H2将存储的数据分组以多跳方式发送给目的节点H8，完成通信。通过以上情景分析，当网络出现间歇连通时，节点传输概率的计算是关键所在，本文提出的ARPBC 协议新颖之处在于综合了情景信息的预测值来计算传输概率。

图1 网络连通状态

图2 网络连通状态

ARPBC协议主要由计算情景信息属性效用函数、情景信息预测、路由选择与传输三部分组成。ARPBC 协议的路由决策主要是根据对情景信息属性的预测值做出的，因此，准确预测情景信息属性趋势是协议的关键。

ARPBC协议工作原理如下：首先，每个节点对连通域内已知节点计算情景信息效用函数，然后，利用Kalman滤波器求出这些效用函数的预测值，采用多准则决策理论［6］，最终计算出节点综合传输概率值。传输概率值作为路由信息表的一个组成部分定期发送给连通域内其它节点，当网络处于间歇连通状态时启动并执行预测处理过程。

1.2 ARPBC协议相关假设

（1）在本协议中，节点不需要了解自身的地理位置，也不需要知道邻居节点的地理位置，而只需要了解其相关的逻辑连接，从而可以节省由于GPS请求定位所消耗的能量和网络带宽，有效提高网络生命周期。

（2）网络中数据传输采用两种方式，即同步传输和异步传输。若收发双方处于同一连通域内，数据分组将以同步方式进行传输 （即当发送方与接收方处于同一连通域内，传输路径上的节点均不存储所转发的数据分组，节点间以多跳方式进行数据分组传输），否则，将采取异步传输方式（即当发送方与接收方不在同一连通域内时，选择最优节点作为中继节点并将数据分组存储在其缓冲区中）。

（3）连通域内同步传输可以采用任何路由算法，本文采用距离矢量 （DSDV）路由算法。

1.3 ARPBC协议设计

1.3.1 情景信息效用函数

本文针对移动Ad Hoc网络特性，重点讨论两个情景信息，即连接变化度和未来时段节点是否处于连通域内，并给出其效用函数的具体定义。需要指出的是文中给出的模型是通用的，也可以根据不同应用加入其它情景信息，如内存可用性或者邻居节点信息等。

定义1 节点h的连接变化度函数：Dh（t）是指在一段时间间隔内节点h 遇见其它节点的总数，即包括时间间隔［t－ T，t］ 内与节点h 成为邻居或者断开连接的节点数目，定义为

式中：n（t）——节点h在t时刻的邻居节点集。函数值的大小反映的是时间间隔［t－T，t］内邻居数量是否有较大的变化，若该值较大，意味着节点h 最近一段时间邻居节点的数量变化较大。

定义2 节点h和节点i连通状态函数

若函数值为1则表示节点h与节点i在t时刻处于同一连通域内，否则说明两节点不在同一连通域内。

综合以上两种情景信息，定义情景信息效用函数为

考虑到每种情景信息的相对重要程度，赋予每种情景信息不同的权重

式中：权值w1，w2——每个属性的相对重要程度。

通常，情景信息的当前值在一定程度上是有用的，但是，那些在未来时刻会被使用的值则更为重要，例如，若两个节点在很长一段时间内一直保持连通状态，而仅仅在当前时刻断开连接十秒钟，若只考虑当前状况，则连通状态函数值为0。若两节点在过去一段时间内一直保持在同一连通域内，则它们很可能在未来仍然处于同一连通域内，可见使用情景信息的预测值比使用当前值更有价值。因此，情景信息值的准确预测对整个协议是至关重要的。

1.3.2 情景信息属性值预测

本文使用Kalman 滤波器［7，8］来对情景信息值进行预测。由于不需要节点存储全部历史信息，因此协议是轻量级的，适合于资源相对较匮乏的移动设备。

将情景信息效用函数值输入Kalman滤波器，得到t＋T 时刻的预测结果，记为（t）和（t），然后通过使用多准则决策理论得到效用函数的预测值，定义如下

上式表示节点h作为中继节点传输数据分组给节点i的优劣程度，即节点h的传输概率值。

1.3.3 效用函数的自适应参数

然而，对于式（5）中的权重值是预先确定好的，是静态的，它不能很好地反映情景信息随时间的推移各情景信息值的变化情况。例如，电池电压的小幅降低可能意味着电池电量即将用尽，因此，就要求属性权重的非线性下降应该能够准确反映出这种状况。一般情况下，我们期望效用函数各项的权值能够动态地进行调整，即具有自适应性。本文通过引入一个自适应权重值a（xi）到式 （5）中来解决这一问题。a（xi）是一个复合参数，在本文中，主要定义3个重要方面：即情景信息xi取值范围自适应权值，记为arange（xi）；情景信息可预测性自适应权值，记为apredictability（xi）；情景信息的可获性自适应权值，记为aavailability（xi）。具体定义如下：

（1）属性取值范围自适应权值：定义一个自适应权重函数arange（xi），其取值范围为 ［0，1］。例如，考虑电池剩余电量 （可以用电池电量的百分比来表示），可以使用单调减函数 （不一定是线性的）来描述具有不断降低的自适应权重，可以确保随着剩余电量逐渐趋近于0时，相应的效用函数权重也不断降低。

（2）情景信息可预测性自适应权重函数：对于给定的某种情景信息，预测模型有时也无法给出某一时间间隔的准确预测。本文通过引入两个离散值 （0或1）来对可预测性进行定义

（3）情景信息可获性自适应权重函数：如果假设所有的情景信息具有相同的可获度显然是不合理，因此，希望存在情景信息可获性的时间变化集，并且其值是已知的，定义如下

则自适应权重a（xi）定义如下

将自适应权重值a（xi）引入到式 （5）中，则将式 （8）修改为

式 （9）综合考虑了两种情景信息，目的是求出节点的最佳传输概率值，即max U∧h，i，当网络出现 “孤岛”时，选择具有最优传输概率值的节点作为承载数据分组的中继节点。

我们将此方法进一步抽象，给出一个通用模型，即

式中：xi——不同情景信息，效用函数f（U1，U2，…，Un）中包含了每种情景信息的预测值，并充分考虑了各种属性所占的权重以及权重的自适应性。显然，这是一个多目标优化问题，一般情况下，一个目标的优化往往可能伴随着其它目标的性能降低，因此，要使所有目标均达到最大化是不可能的，必须要对其进行折中以便得结果最大化，可以采用多准则决策理论进行求解。

1.3.4 路由选择

前文详细叙述了根据节点情景信息的预测值来计算其传输概率的方法。下面，讨论这些信息在网络中是如何传播的。

（1）路由表格式：每个节点维护一个包含有情景信息属性概率值的路由表，路由表结构如下：

其中，第1个字段是目的节点ID，第2个和第3个字段是根据DSDV 路由算法计算出来的下一跳节点ID 和距离，第4项是具有最佳传输概率的下一跳节点ID，其传输概率值被保存在路由表中最后一个字段中。路由表既可用于同步传输也可用于异步传输：当发送方与接收方在同一连通域内时，采用同步传输方式，即根据路由信息（nextHopId和dist）以多跳方式进行数据传输；当接收方与发送方不在同一连通域内时，启动异步传输过程，即选择具有最佳传输概率的节点作为存储数据分组的中继节点 （根据bestHopHostId和deliveryProb）。在本协议中，假定当多跳距离大于等于16 的时候认为是不可达 （选择16 是因为在路由信息协议 （RIP）中认为是不可达［9］），这一参数也可以根据实际需求进行调整。如果没有接收到任何更新信息，例如由于暂时断开连接、传输错误 （如受到干扰）或者由于节点已经移动离开等原因，这时将启用滤波器进行预测更新。如果在给定的滤波器的刷新时间间隔 （也就是等于到路由表中的发送间隔）没有接收到任何更新信息，则将滤波器上一次的输出作为本次的输入。

（2）路由表更新：节点间定期交换路由表，当节点接收到路由表更新信息时，它会根据自己存储的路由表检查对应的记录。在同步传输过程中，若接收到具有相同的targetHostId和更低或等距离的记录，则节点路由表中的记录将被替换 （需要说明的是，为了保持路由表信息的更新度，当距离相等时也会替换记录）。相反，在异步传输过程中，当且仅当接收到相同的targetHostId和更高或者等于传输概率时记录才会被替换。如前所述，当丢失一定数量的更新信息后，该记录被删除，这也避免那些具有较高传输概率但实际上已经是过期的信息仍然存在于路由表中。当路由表已满时，则将从那些不可达的节点记录开始进行替换 （即distance字段等于或大于16的节点），其次将选择最低传输概率的记录进行替换。

1.3.5 数据分组传输过程

（1）同步传输过程：当发送端已经发送出数据分组，若接收端是同步可达的 （即在路由表中存在一条记录，其targetHostId字段是接收节点且距离小于16），则数据分组被转发到nextHopId所指示的下一跳节点。由于路由表更新存在传播时延，会出现当前传输路径已经断开，而相关的路由表更新信息还未到达，这种情况下，数据分组仍然会被转发，直到转发到已经接收到路径损坏消息的节点为止。此时，节点将检查是否可以使用异步传输机制 （即选择路由表中的最佳中继节点进行数据分组的转发）。否则，节点在其缓冲区中缓存该数据分组，并尝试在下一发送周期中重新发送。

（2）异步传输过程：如果路由表中没有到达接收端的路径 （即dist等于或大于16），消息将被转发到具有最高传输概率的节点 （由deliveryProb所指示的），即选择路由表中targetHostId值等于bestHopHostId 的节点作为存储数据分组的中继节点。当然，也会由于中继节点离开连通网络区域而造成中继节点不可达的情况，这种情况下，如果连接断开的更新消息已经发送给发送端，则将该节点作为最佳中继节点的记录将被删除 （设置一个无效状态，可以用0表示）。如果这一消息尚未被转发给发送端时，中继节点发现拓扑变化后，将尝试再次发送数据分组。

（3）重传机制：对于存在缓冲区中的数据分组，节点会定期地检查自身路由表，如果路由表中存在相应的路由信息，则该消息会以同步方式转发给接收节点或者将数据分组转发给下一跳中继节点。如果没有对应的路由信息存在，则数据分组将驻留在缓冲区中。

2 仿真实验与分析

2.1 仿真环境参数设置

为了进一步验证ARPBC 协议的性能，建立了仿真环境对其进行验证分析。本文使用OMNet＋＋作为仿真实验平台［10］，仿真场景为100个节点随机分布在1000m×1000 m 的矩形区域中，节点能够随机移动，移动速度为0～20 m／s，节点无线发射半径都是100m，节点无线接口带宽均为2 M／s，MAC层采用IEEE的802.11协议，数据分组大小为512字节，发送速率为300kbps，发送节点和接收节点随机产生，每秒产生10个节点作为发送节点。假设网络中所有的节点具有相同的重要性 （即arange＝1）并且情景信息属性值在仿真期间是可获得的 （即aavailability＝1）。w1和w2的值分别设为0.25和0.75。每个数据分组都设一个生命周期字段 （初值是10），随着数据分组传输到下一个节点，该值自动减1。数据分组发送失败最大重传次数为7。数据分组重传和路由表更新间隔时间设为20s。本地效用函数更新时间也为20s。为了评价ARPBC算法性能，将其与机会网络中常用的Epidemic Routing和PRoPHET 路由算法进行性能比较。为了使实验结果更具一般性，每个实验都是10次仿真数据的平均值。

2.2 仿真结果与分析

首先分析节点移动速度对数据传输成功率的影响，节点移动速度为0～20m／s，每隔5个单位取一个值，计算数据传输成功率，如图3所示，ARPBC 算法传输成功率要高于其它两种算法，并且随着节点的移动速度增加，会有更好的传输成功率，这是由于随着节点移动速度增加会使中继节点更快地进入目的节点所在的连通域内，进而将数据分组以多跳方式传输至目的节点，因此，能够有效提高传输成功率。

图3 移动速度对传输成功率的影响

下面讨论节点移动速度对端到端平均时延的影响。如图4所示，ARPBC协议的平均时延相对较少，原因是该协议能够充分考虑到情景信息的预测值而不是当前值来选取中继节点，这样能够有效减少节点由于短暂离开网络而对中继节点选取的影响，从而能够较大幅度提高传输成功率，有效降低端到端时延。

图5为数据分组投递率曲线，图中可以看出，本文的数据分组成功投递率要比其它两种算法要优越。虽然在仿真的开始阶段，算法成功投递率略低于其它两种算法，这主要是由于需要转发的数据分组在网络中只存在单一副本，因此成功率略低，但是随着时间的推移，由于选取了具有最佳传输概率值的节点作为承载数据的中继节点，因此，会逐渐显示出其性能上的提高。

图4 移动速度对端到端延迟的影响

图5 数据分组投递率比较

3 结束语

本文针对具有间歇连接特性的移动Ad Hoc网络数据传输率较低，提出了具有情景感知的自适应路由协议ARPBC。本文将预测技术引入路由协议中，进行路由选择和数据转发机制。此外，文中提出了移动环境情景信息效用函数预测通用框架，用以选择最佳的中继节点作为数据承载节点。仿真实验表明，ARPBC协议具有良好的性能，能够有效提高数据传输成功率，降低端到端时延，同时能够节省宝贵的带宽资源。在下一步工作中，将主要研究权重系数对整个协议的影响以及节点缓冲区大小对协议的影响。

［1］Samuel H.DTN based dominating set routing for MANET in heterogeneous wireless networking.mobile network ［J］.Mobile Networks and Applications，2009，14 （2）：154－164.

［2］Basagni S，Conti M，Glordano S，et al.Mobile Ad Hoc networking［M］.Xi’an：Xi’an Jiaotong University Press，2012：1－460 （in Chinese）.［Basagni S，Conti M，Glordano S，等.移动Ad Hoc网络［M］.西安：西安交通大学出版社，2012：1－460.］

［3］Ikki，SS，Ahmed，MH.Performance analysis of adaptive decode－and－forward cooperative diversity networks with best－relay selection ［J］.IEEE Transaction on Communications，2010，56 （1）：68－72.

［4］XU Bintai.Research on conectivity of wireless Ad Hoc networks［D］.Nanjing：Nanjing University of Posts and Telecommunications，2013 （in Chinese）. ［徐彬泰.无线Ad Hoc网络连通性的研究 ［D］.南京：南京邮电大学，2013.］

［5］Kumar D，Srivastava A，Gupta SC.Performance comparison of DSDV and AODV routing protocols in MANETS ［J］.International Journal of Electronics Communication and Computer Technology，2012，2 （3）：120－124.

［6］FANG Guohua，HUANG Xianfeng.Multi－objective decision theory and its application ［M］.Beijing：Science Press Ltd，2011：1－236 （in Chinese）.［方国华，黄显峰.多目标决策理论、方法及其应用 ［M］.北京：科学出版社，2011：1－236.］

［7］Charles K.Chui，CHEN GR.Kalman filtering with real－time applications ［M］.4th ed.Beijing：Tsinghua University Press，2013：1－193 （in Chinese）. ［Charles K.Chui，陈关荣.卡尔曼滤波及其实时应用 ［M］.4版.北京：清华大学出版社，2013：1－193.］

［8］CAO Yuping，TIAN Xuemin.Nonlinear system fault prognosis based on SVM and Kalman predictor［J］.Control and Decision，2009 （3）：477－480 （in Chinese）. ［曹玉苹，田学民.基于SVM 和Kalman预测的非线性系统故障预报 ［J］.决策与控制，2009 （3）：477－480.］

［9］RIP ［EB／OL］.http：／／zh.wikipedia.org／wiki／%E8%B7%AF－%E7%94%B1%E4%BF%A1%E6%81%AF%E5%8D%8F%E8%AE%AE，2013.

［10］ZHAO Yongli，ZHANG Jie.OMNet＋＋and network simulation ［M］.Beijing：Posts ＆Telecom Press，2012 （in Chinese）. ［赵永利，张杰.OMNeT＋＋与网络仿真 ［M］.北京：人民邮电出版社，2012.］