基于信任子网的信任数据搜索访问机制研究*

金 芳

（中国人民解放军91404部队，河北 秦皇岛 066000）

0 引 言

信任度的准确、快速计算对点对点（Peer-topeer，P2P）网络信任模型非常重要[1]。而信任度准确、快速计算的基础就是对信任数据的高效搜索访问[2]。当前对非结构化网信任数据的搜索访问大多是向整个网络的所有节点发送询问消息[3]。但相对于整个网络，只有少数节点拥有信任数据。如果询问消息只局限于在这些持有信任数据的节点中传播，可以大量的降低网络消耗，同时可以缩短搜索信任数据的响应时间[4-5]。信任模型的性能也能得到极大提高。

本文提出一种基于信任子网的信任数据搜索访问机制。该数据搜索访问机制包括如何寻找信任数据的位置，新的节点如何加入信任子网以及如何维护建立好的信任子网。

在信任数据搜索访问机制的第一阶段，采用普遍搜索机制对当前网络中的信任数据进行搜索访问，查找到持有信任数据的节点的位置。然后，根据第一阶段查找到的节点，构建信任子网，使信任子网中的节点均是持有目标节点信任数据的节点。信任子网稳定后，若要询问目标节点的信任数据，只需要在信任子网内部进行搜索，这样可大量减少询问信任数据的响应时间。

1 信任子网中的消息描述

信任子网协议是一种使用自有消息的导向包。每个消息包含一个源节点ID、一个交易ID、一个消息描述符和一个有效载荷。

消息形式如图1所示。

图1 消息形式

协议的消息描述符涉及询问邻居、响应邻居、声明邻居、确认邻居、搜索信任数据和答复信任数据。

符号说明：

QN（Query Neighbor）表示邻居询问，用于源节点向其邻居询问目标节点的信任数据。

RN（Respond Neighbor）表示邻居响应，当邻居节点收到询问消息时，查找自身是否持有目标节点的信任数据，若有给源节点发送一个响应邻居消息，将目标节点的信任数据回复给源节点。

IN（Indication Neighbor）表示邻居通知，用于邻居节点告知源节点其有能力接受新的邻居，

CN（Confirm Neighbor）表示邻居确认，当源节点收到邻居节点的通知消息后，将其加入到自己的邻居列表，并发送确认邻居消息告知邻居节点。

STD（Search Trust Data）表示搜索信任数据，用于源节点在信任子网内部搜索目标节点的信任数据。

RTD（Reply Trust Data）表示答复信任数据。信任子网内持有信任数据的节点将信任数据回复给源节点。

6种消息的对应关系如图2所示。

图2 6种消息之间的关系

2 信任子网构建

任意peeri若要查询peerj的信任数据，需首先检查是否有peerj的信任子网存在。若信任子网尚未建立，则peeri首先采用普遍搜索机制来搜索持有peerj的信任数据的peers，然后开始构建信任子网。信任子网构建的流程图如图3所示。

询问消息格式如图4所示。

TRUST-SUBSET.query原语用来询问邻居节点是否持有某个目标节点的信任数据。

peerk接收到peeri的询问消息后，首先将询问消息继续转发给自己的邻居，这样可以提高搜索信任数据的效率，然后再查找自身是否持有peerj的信任数据，若有则回复一个响应邻居消息给peeri，将信任数据回复给peeri，这样，peeri不需要等到信任子网建立后再次发送搜索信任数据消息即可得到peerj的信任值，可以降低网络开销并减少搜索访问信任数据的响应时间。

图3 信任子网构建流程图（以peerk为例）

图4 询问消息格式

然后，如果节点k有能力接受新的邻居，则会给peeri发送一个邻居通知消息。peeri收到peerk的邻居通知消息后，将其加入到自己的邻居列表并发送一个邻居确认消息给peerk。peerk接收到来自peeri的邻居确认消息后，再将peeri加入到自己的邻居列表中。邻居通知和确认消息格式如图5所示。

邻居通知消息：

图5 邻居通知消息格式

TRUST-SUBSET.indication原语用来通知邻居节点其有能力接受新的邻居节点。

邻居通知消息：

图6 邻居通知消息格式

TRUST-SUBSET. confirm原语用来确认新的邻居节点加入成功。

3 信任数据搜索

当信任子网建立后，网络上的任意节点i欲查询节点j的信任数据，可以直接向整个信任子网广播搜索信任数据消息，peerk收到STD消息后将向消息的源节点peeri回复一个答复信任数据消息。搜索和答复信任数据消息如下：

搜索信任数据消息如图7所示。

图7 搜索信任数据消息格式

TRUST-SUBSET. search原语用来在整个信任子网中查询某个节点的信任数据。

答复信任数据消息如图8所示。

图8 答复信任数据消息格式

TRUST-SUBSET. reply原语用来给发起查询的节点答复信任数据。

4 信任子网维护

事实上，信任子网需要处理通信失败或自由离开的节点[4]。当以下情况发生时，信任邻居列表将会被修改。

（1）接收到IN消息。这意味着有其它节点已经接受了接入请求，可以将其加入到自己的信任邻居列表。

（2）接收到CN消息。这意味着自己已经加入到源节点的邻居列表，并且源节点也将被加入到自己的信任邻居列表中。

（3）失败或自由离开。如果向信任邻居发送消息失败，说明此邻居节点可能已经离开网络，则它将被从信任邻居列表中删除。

（4）收到非信任邻居列表中的节点发送的STD消息。由于底层网络的拥塞，信任子网中的一些节点可能并不知道它们已经离开网络，而继续发送搜索信任数据消息来搜索访问目标节点的信任数据。当信任子网中有节点收到这些离开节点的STD消息后，可将这些节点再次加入到信任子网中。由于这些节点可在不发送QN、IN等消息的情况下重新加入信任子网，因此可以降低网络开销。

（5）信任子网超时。如果信任子网的时限内没有信任数据搜索，信任邻居列表将会被删除，即该信任子网失效。

5 仿真设计及结果分析

5.1 仿真设计

设置拓扑结构中共有10 000个节点，对每个节点进行1到10 000编号，编程产生0到1的100个不同的随机数p，用p乘以拓扑中总的节点数10 000即可产生0到10 000之间的100个不同的随机数，把它们设置为持有所需信任数据的节点，即在网络中随机设置100个持有信任数据的节点。

5.2 响应时间

由于很难直接测量系统的搜索响应时间，所以一般采用消息转发的跳数作为响应时间的单位。同时测量不同搜索算法的最大运行时间可以比较它们在搜索过程中的响应时间。首先假设一种简单的离散时间模型，每个节点接收来自其邻居节点的询问，必要时还可以处理并继续向其邻居节点传送询问副本。

由于几种不同的搜索算法的响应时间处于不同的数量级，所以图9的纵坐标采用对数坐标，这样可以清晰地看出它们在响应时间上的差别。由图可以看出，洪泛、信任子网搜索、普遍搜索的响应时间依次增加，但在同一数量级上，而浅洪泛随机走和随机走的响应时间依次显著增加且明显大于洪泛、信任子网搜索和普遍搜索。

图9 响应时间

在仿真实验过程中，没有考虑转发消息和消息询问应答延时等参数，所以洪泛的响应时间与生存时间（Time-to-live，TTL）相同。信任子网搜索和普遍搜索均是对洪泛的改进，所以它们的响应时间处在同一数量级。信任子网搜索的搜索范围相对很小，所以它的响应时间也非常小。信任子网建立过程中采用普遍搜索机制，所以它们的响应时间相同。

5.3 搜索过程中转发消息数量

判断搜索算法优劣的一个重要条件是在搜索相同信息的同时使用的消息数量的多少。因为达到相同的搜索效果，网络中转发的消息数量越少，网络负载越小，越节约网络带宽。

由图10可以看出，只有信任子网搜索转发的消息包数量非常小，而其它几种搜索机制的转发消息包数量相等，且随TTL的增加显著递增。

图10 搜索访问过程中转发消息包数量

6 结 语

本文根据信任模型中信任数据搜索的特点，提出了一种改进的信任数据搜索机制，即基于信任子网的信任数据搜索机制，该搜索机制的第一阶段采用普遍搜索方法查找持有目标节点信任数据的节点，以缩小第二阶段信任子网建立过程中信任数据的搜索范围。信任子网建立完成后，采用一种基于最小消息转发集合的优化洪泛策略在信任子网内部搜索访问目标节点的信任数据，该优化策略可以避免大量的消息冗余，有效地节约网络资源。

文章编程设计仿真实验，利用传播消息数量（网络消耗）以及最长响应时间等参数分析比较了洪泛、随机走、浅洪泛随机走、普遍搜索和信任子网搜索等搜索机制的性能。由仿真结果可以很明显地看出，基于信任子网的搜索机制在转发消息数量和响应时间等方面的性能均比其它几种搜索方法有较大提高。更进一步说，在信任模型中采用基于信任子网的搜索机制搜索访问信任数据，可以提高信任度计算的准确性和计算速度，信任模型的性能随之改进。