Ad Hoc网络是一种不依赖任何固定基础设施的无线移动网络，具有无中心、自组织、高动态和能量受限等特点。在战场环境、紧急救援和移动会议中具有广泛的应用前景，同时其安全问题也更加突出，网络抗攻击能力尤为脆弱，因此需要设计有效的安全路由算法^[1-2]。

Ad Hoc网络中，由于能量和带宽受限，会产生自私节点，这些节点会部分或者全部地丢弃接收到的分组，使网络安全性能降低^[3]。现有的安全路由协议，如SAODV^[4]、Ariadne^[5]和ARAN^[6]等通过完整性校验、签名认证和RSA密码体制来满足安全需求，但是存在计算开销大、无法发现不协作的自私节点的缺陷。针对自私节点，近年来，国内外研究者提出了很多基于信任评估方法的安全路由协议。信任评估方法的优点是计算开销小，模型运用灵活，能在整个网络范围内检测节点的信任值。文献^[7]基于信任保留的认证协议提高了节点认证的可靠性，但是增加了信任评估方法的复杂度。文献^[8]构造了一个新的信任模型，但在路由过程中没有确切的实现。文献^[9-10]基于信任评估的安全路由协议都假设节点行为保持不变或者忽略节点行为的变化，无法检测如通断攻击^[11]节点行为的改变，从而会出现自私节点的误判和安全路径的错误选择。文献^[12]在判断节点是否自私时使用了固定时间窗机制，对节点行为的判断存在延迟。文献^[13]中的协议虽然能够检测节点行为的变化，但是在计算信任值时存在证据不足的问题。

针对上述问题，本文提出了一种基于节点行为检测的Ad Hoc安全路由协议信任评估方案TESBB，并将其整合到AODV协议中。在信任评估方案中，引入间接信任评估来计算链路信任值(link trust)，每个节点通过比较前后链路信任值的变化来判断节点的行为改变。当发现某个邻居节点的行为发生改变时，通过可变时间窗来重新评估链路信任值；在路由过程中，每个节点的路由表中维护一个路径信任值，并通过控制分组的计算和路由表的查询来选择安全的分组传送路径。该方案满足了Ad Hoc安全路由协议快速发现自私节点和准确选择安全路径的需求。

1 基本理论 1.1 公共邻居

如果一个节点同时处在另外两个不同节点的传输范围内，那么这个节点就称为公共邻居节点。如图 1所示，在Ad Hoc网络中，节点A和节点H既是节点E的邻居，又是节点F的邻居，则节点A和节点H就被称为公共邻居。

1.2 节点行为

Ad Hoc网络节点通常无法在一跳范围内完成分组的传送任务，需要中间节点的转发，自私节点为了节省自身资源会出现不转发的行为。这些节点的行为会引起如黑洞攻击^[14]、灰洞攻击^[15]等威胁。

1) 黑洞攻击：在路由请求过程中，恶意节点收到RREQ后，在并没有到目的节点的路由的情况下，立即进行路由应答RREP，谎称自己有到达目的节点的最近路由，使源节点和该恶意节点建立路由。此后源节点就沿该路径发送分组，恶意节点在此过程中丢弃经过它的分组，形成丢弃报文的黑洞。

2) 灰洞攻击：灰洞攻击是针对分组的Dos攻击。攻击节点在网络状况良好的情况下，首先以正常方式参与路由发现过程，然后根据分组的类型或者数量选择性地丢弃数据。有时该类节点只丢弃数据分组，使得路由信息正确，但是数据无法传送。灰洞攻击节点的存在会降低系统的性能，扰乱路由的建立过程，从而造成安全隐患。

2 信任模型 2.1 信任模型及其改进

在安全路由协议中有两种信任值：链路信任值和路径信任值。

1) 链路信任值：其定义类似于节点信任值^[16-17]，但是为了更加确切描述不同节点对公共邻居的信任值，本文使用链路信任值。当一个节点要求其邻居节点转发分组时，会立即使用监视模块对邻居节点的行为进行监视，同时，若邻居节点正确地转发了分组，则计算链路信任值。本文中链路信任值引入间接信任值评估方法，在计算直接信任值T_i→j^D的基础上，通过和公共邻居之间进行信息交换，获得推荐信任值T_i→j^I，最终进行综合评估得出链路信任值T_l。

在t时刻节点i对节点j的直接链路信任值表示为T_i→j^D(t)，定义如下：

式中：N_f(t)为节点j在t时刻之前正确转发的分组；N_r(t)为在t时刻之前节点i发送到节点j的全部分组；W为时间窗。T_i→j^D(t)表示在时间窗内分组的转发率，初始化值为0.5。

在t时刻节点i对节点j的间接链路信任值表示为T_i→j^I(t)，如图 2所示，节点i计算a提供给它的间接信任值为

节点i将所有公共邻居节点的推荐信任值按式(2)进行处理，求得节点i对节点j的间接链路信任值。

式中：L_k为节点i与节点j的第k个公共节点。

综合评估节点i对节点j的链路信任值为

当T_i→j(t)接近0时，就认为该节点不可信。因此，若T_i→j(t)小于门限值T_Threshold，每个节点就将该邻居节点视为自私节点，并列入黑名单。当该自私节点存在于所有邻居节点的黑名单时，就会被移除网络。T_Threshold=(T_t^min+T_t^max)/2.0，T_t^min和T_t^max分别为网络在t时刻的最小链路信任值和最大链路信任值，其初始化值为0.5，随着网络的变化及时更新。

2) 路径信任值：分组从源节点到目的节点需要一条路径，因此，考虑一条路径的可靠性是很有必要的。路径信任值T_p用来表示一个分组从源节点传送到目的节点的可能性，其定义如下：

式中：n_i→n_j表示节点j是节点i的下一跳节点；N_d为目的节点。

在安全路由协议中，T_p由转发控制分组来计算，并在每个节点的路由表中进行维护，其计算过程如图 3所示。

图 3中，从节点A到节点E有4条路径，但是路径L_ACDE存在自私节点D，若节点A只考虑链路信任值，则其有可能会选择让节点C转发分组，不能选择最优路径。本方案在路由表中维护路径信任值T_p，节点A能够查询路由表，选择最安全的路径L_AFGHE。

2.2 安全路由缺陷

现有安全路由协议中，所有节点在计算链路信任值时都使用固定时间窗，使得计算得到的信任值可以长时间使用。这种方法能很好地检测出如黑洞攻击节点这种行为保持不变的节点，但是对于其行为随时间变化的节点，该方法不能及时检测出节点的行为变化，因此就不能评估出准确的链路信任值，在数值上表现为其收敛速度变慢，而链路信任值的收敛速度较慢会引起两个问题：一是自私节点的误判；二是不能选择安全的路径。自私节点的检测会因为信任值收敛变慢而延缓，进一步由于不能及时计算出路径信任值T_p，节点维护的路由表也不能及时更新。因此，使用可变时间窗来及时计算链路信任值T_l对提高安全路由协议性能至关重要。

3 TESBB描述

TESBB是一种基于节点行为的Ad Hoc网络安全路由信任评估方案，在该方案中，每个节点都可以通过计算邻居节点的链路信任值来发现自私节点。在实际Ad Hoc网络中，节点的行为会随着地理位置和环境的变化而变化，这就要求节点能够快速准确地评估邻居节点的行为，及时发现自私节点，并且正确选择安全路径。

TESBB方案包括两个部分：检测节点行为变化和确定评估时间窗。

3.1 检测节点行为变化

每个节点在网络里都有能力侦听到其周围每个邻居节点的分组收发情况，并且具备监控机制使得一个节点能够检测和收集其邻居节点的行为。

定义链路信任值的变化为ΔT，节点i对节点j在t时刻的链路信任值变化为ΔT_i→j(t)=T_i→j(t)-T_i→j(t′)，t和t′分别为评估链路信任值的当前时间和上一次时间。

ΔT_i→j(t)>0：节点j转发了节点i要求转发的分组。

ΔT_i→j(t)＜0：节点j丢弃了节点i要求转发的分组。

因此，当ΔT_i→j(t)为非0值时，说明节点j的行为发生了变化。为了加快节点信任值的收敛速度，定义Con_i→j(t)来反映节点行为的变化，Con_i→j(t)=ΔT_i→j(t)×ΔT_i→j(t′)。

Con_i→j(t)>0：节点j的行为保持不变。

Con_i→j(t)＜0：节点j的行为有较大变化。

因此，当Con_i→j(t)＜0时，节点i发现节点j的行为有明显改变，确定其为自私节点。

3.2 确定评估时间窗

在现有安全路由协议中，大多都采用固定时间窗来判断邻居节点自私与否，但是在实际网络中这种方法的假设条件很难实现，无法用节点以前的信任值来反映节点当前的行为状态。在TESBB中，自私节点的链路信任值被明显减小。引入适应性时间窗，根据邻居节点的行为灵活决定评估时间窗，从而精确地表示评估链路信任值所需的时间。当一个节点检测到其邻居节点行为发生改变时，该节点在链路信任值计算中使用可变时间窗来反映邻居节点的新行为。若节点从协作节点变为自私节点，链路信任值通过评估会降低。

在t时刻节点i对节点j的评估时间窗为W_i→j(t)，计算公式如下：

式中：t_i→j为节点i检测到节点j行为发生变化的时刻；W_max为固定时间窗；W_min为设置的最短检测时间间隔。

某一节点在t_i→j时刻发现其邻居节点行为改变时，其时间窗W变化如图 4所示。当邻居节点行为不变时，时间窗为W_max。

4 安全路由协议

以AODV为基础路由协议进行扩展，设计出了一种安全路由协议TEAR，去除依据跳数值得最优路径选择方法，实现了多路径功能，考虑了路径信任值的传递和计算，最终选择出安全的传输路径。本方案中，Ad Hoc网路的每个节点要维护一张路由表和一张信任表。信任表的格式如表 1所示，表中信任值初始值为0.5。

图 5给出了信任表的更新过程。当节点i要求节点j转发分组时，节点i就开始更新对节点j的信任记录。首先节点i在发送缓存中存储要发送的分组，N_r进行加一操作，若节点j能够正确地转发分组，N_f进行加一操作，然后节点i使用更新消息计算T_i→j(t)、ΔT_i→j(t)、Con_i→j(t)，如果Con_i→j(t)＜0，节点i更新t_i→j为当前时间，最后根据t_i→j来更新W_i→j(t)。

TEAR的过程描述如下：

在没有目的节点活动路由的情况下，源节点需要广播RREQ分组，其关键消息格式如图 6所示。RREQ从源节点转发到不同的目的节点时，沿途所经过的节点都要建立到源节点的反向路由Reroute。当中间节点接收到RREQ分组时，查询路由表，根据路由表中的T_p和自己节点的信任表记录更新路径信任值，并将该节点加入到Reroute中，进行上述过程直到满足下述条件：① 当前节点是目的节点；② 当前节点的路由表中有到目的节点的表项，并且表项中DestSeq大于RREQ中的DestSeq。

当RREQ分组到达目的节点或有到达目的节点的路由时，能够根据到达的分组内容来做出路由回复，将RREP分组沿着信任值最大的反向路径传输到源节点，建立路由，进行数据分组发送。

安全路由协议TEAR的伪代码描述如下所示，其中信任表的更新过程在图 5中。

if(N_s!→N_d)

send RREQ；//choice node i to analyse

while(t＜TTL){

if(RREQ.SourIP==Node_i SourIP & &

RREQ.SourSeq==Node_i.SourSeq)

drop RREQ;

else{//update node record

DestSeq=RREQ.SourSeq;

precursor=TESBB(nodes);

//nodes represent the neighbours of node i

HopCount=RREQ.HopCont;

Reset TTL;

}

if(Node_i==N_d||

Node_i→N_d)//node i keep the route to dest node

Node_end=Node_i;

reply REEP;

goto L1;

else{//update RREQ

RREQ.DestSeq=MAX(DestSeq);

//the maximum DestSeq related to dest node in record

RREQ.HopCont++;

RREQ.ReRoute←Node i;//add node i to reversse route

}

}//end while

L1;

//initialize RREP

if(RREQ.DestSeq==Nodeend.DestSeq){

Nodeend.DestSeq++;

RREP.DestSeq=Nodeend.DestSeq;

RREP.ReRoute=RREQ.ReRoute;

//copy RREQ′s reversse route to RREP

if(Node_eng==N_d)

RREP.HopCont=0;

else

RREP.HopCont=Node_end.HopCont;

}

if(Node_j.DestSeq==RREP.DestSeq||

RREP.HopCont＜Node_j.HopCont)

forward pointer=RREP.ReRoute;

RREP.HopCont++;

if(Node_j==N_s)

Set up routing connection;

5 模拟实验与分析 5.1 模拟环境设置

本文使用NS2来建立网络模拟环境，对TEAR协议进行仿真和分析，并与AODV和固定时间窗安全路由协议TA-AODV^[12]进行比较，其中TA_AODV的时间窗设置为50 s。在AODV源代码中添加自私节点类，加入转发分组计数函数与链路信任值和路径信任值的计算函数，修改路由代码后重新编译。仿真比较，分析trace文件，选择相应的字段，编写awk脚本生成最终分析所需文件。

模拟中在1 000 m×1 000 m的二维环境中设置100个节点，节点之间的通信使用点到点的CBR数据流，发送速度为每秒4个报文，报文大小为512 B，节点通信半径为250 m，无线链路的宽度为2 Mb/s，使用Random Waypoint移动模型，PauseTime设置为0，最大速度为2 m/s，仿真时间为2 000 s，用setdest程序产生相应代码。模拟中的节点分为正常节点和自私节点，自私节点转发额定数量的分组就开始把接收到的分组全部丢弃，自私节点的数量不超过30。为了减小误差，取10次模拟结果的平均值进行比较。仿真参数的设定如表 2所示。

选取以下标准来进行评价：

1) 分组交付率：目的节点接收到的分组与发送的总的分组的比率。

2) 网络吞吐量：单位时间内所有目的节点的平均接收数据速率。

3) 评估时间：检测出自私节点行为变化所用的平均时间。

5.2 模拟结果

5.2.1 分组交付率

分析比较自私节点数量对网络平均分组交付率的影响，仿真结果如图 7所示。可以看出,随着自私节点数量的增加，所有协议的分组交付率都在下降。AODV协议受自私节点的影响最大。网络中不存在自私节点时，由于TA-AODV在50 s的固定时间窗内不能对节点行为做出合理评估，有时会把正常节点当作自私节点，致使其分组交付率较低。TEAR在可变时间窗内监测节点的行为，能及时发现自私节点，所以在自私节点数达到30时仍能保持70%以上的分组交付率。

5.2.2 网络吞吐量

分析比较自私节点数量对平均网络吞吐量的影响，仿真结果如图 8所示。当不存在自私节点时，TEAR和TA-AODV的平均网络吞吐量低于AODV，这是因为AODV协议中没有添加安全相关的字段以及函数，在绝对安全条件下，其具有更高的吞吐量。随着自私节点数量的增多，AODV吞吐量下降明显，转发的分组数量变少，最终到达目的节点的分组数减少，而TEAR能够更加有效地避开自私节点，一次性选择更加安全的路径，其路径重新路由的概率较小。TEAR的平均网络吞吐量高于AODV和TA-AODV的最大值分别为46.2%和10.5%。

5.2.3 评估时间

1) 检测相同数量的自私节点所用的时间能够反映节点信任评估模型的性能。记录仿真结果如图 9所示。可以看出，当自私节点数目较少时，TEAR能较快地发现自私节点，而当自私节点数目达到14个时，两种方法所用时间基本相同，这是因为TEAR评估模型引入了公共邻居节点推荐的间接链路信任值，能更加精确地描述节点信任值的变化。

2) 自私节点数达到15时，分析得出结果如图 10所示。评估时间表示发现一个自私节点所用时间，节点数目表示有发现该自私节点的平均正常节点数目。从图 10中可以看出，TEAR能够较快地发现节点行为的改变，要使TA-AODV中的5个节点发现一个自私节点行为的改变，需要600 s，而在TEAR中只需要400 s，这是因为固定时间窗的信任评估方案信任值收敛速度较慢，无法及时反映节点的行为变化，当其行为已经发生改变时，仍使用以前的评估值来判断节点的状态。

6 结 论

本文提出了一种基于节点行为的信任评估方案，并且以AODV协议为基础进行扩展得到安全路由协议TEAR。TEAR使用直接信任评估和间接信任评估结合的方案，保证了链路信任值的可靠性；使用可变时间窗机制，当节点行为改变比较频繁时，不必等待固定的时间后再去评估，能够及时发现自私节点，确保了评估的时效性。通过对分组交付率和网络吞吐量的比较发现，TEAR能够有效地避开自私节点，选择仅由合作节点构成的安全路径进行分组传递，减少重复路由概率，提高了网络性能。本文提出的协议在信任值门限的更新以及自私节点丢包行为方面没有详细说明，如何及时根据当前网络状态更新信任门限值并采取多种机制模拟节点丢包行为，以确保Ad Hoc路由协议更加安全高效，是未来的一个研究方向。