基于信任子網(wǎng)的信任數(shù)據(jù)搜索訪問(wèn)機(jī)制研究*

金 芳

（中國(guó)人民解放軍91404部隊(duì)，河北 秦皇島 066000）

0 引 言

信任度的準(zhǔn)確、快速計(jì)算對(duì)點(diǎn)對(duì)點(diǎn)（Peer-topeer，P2P）網(wǎng)絡(luò)信任模型非常重要[1]。而信任度準(zhǔn)確、快速計(jì)算的基礎(chǔ)就是對(duì)信任數(shù)據(jù)的高效搜索訪問(wèn)[2]。當(dāng)前對(duì)非結(jié)構(gòu)化網(wǎng)信任數(shù)據(jù)的搜索訪問(wèn)大多是向整個(gè)網(wǎng)絡(luò)的所有節(jié)點(diǎn)發(fā)送詢問(wèn)消息[3]。但相對(duì)于整個(gè)網(wǎng)絡(luò)，只有少數(shù)節(jié)點(diǎn)擁有信任數(shù)據(jù)。如果詢問(wèn)消息只局限于在這些持有信任數(shù)據(jù)的節(jié)點(diǎn)中傳播，可以大量的降低網(wǎng)絡(luò)消耗，同時(shí)可以縮短搜索信任數(shù)據(jù)的響應(yīng)時(shí)間[4-5]。信任模型的性能也能得到極大提高。

本文提出一種基于信任子網(wǎng)的信任數(shù)據(jù)搜索訪問(wèn)機(jī)制。該數(shù)據(jù)搜索訪問(wèn)機(jī)制包括如何尋找信任數(shù)據(jù)的位置，新的節(jié)點(diǎn)如何加入信任子網(wǎng)以及如何維護(hù)建立好的信任子網(wǎng)。

在信任數(shù)據(jù)搜索訪問(wèn)機(jī)制的第一階段，采用普遍搜索機(jī)制對(duì)當(dāng)前網(wǎng)絡(luò)中的信任數(shù)據(jù)進(jìn)行搜索訪問(wèn)，查找到持有信任數(shù)據(jù)的節(jié)點(diǎn)的位置。然后，根據(jù)第一階段查找到的節(jié)點(diǎn)，構(gòu)建信任子網(wǎng)，使信任子網(wǎng)中的節(jié)點(diǎn)均是持有目標(biāo)節(jié)點(diǎn)信任數(shù)據(jù)的節(jié)點(diǎn)。信任子網(wǎng)穩(wěn)定后，若要詢問(wèn)目標(biāo)節(jié)點(diǎn)的信任數(shù)據(jù)，只需要在信任子網(wǎng)內(nèi)部進(jìn)行搜索，這樣可大量減少詢問(wèn)信任數(shù)據(jù)的響應(yīng)時(shí)間。

1 信任子網(wǎng)中的消息描述

信任子網(wǎng)協(xié)議是一種使用自有消息的導(dǎo)向包。每個(gè)消息包含一個(gè)源節(jié)點(diǎn)ID、一個(gè)交易ID、一個(gè)消息描述符和一個(gè)有效載荷。

消息形式如圖1所示。

圖1 消息形式

協(xié)議的消息描述符涉及詢問(wèn)鄰居、響應(yīng)鄰居、聲明鄰居、確認(rèn)鄰居、搜索信任數(shù)據(jù)和答復(fù)信任數(shù)據(jù)。

符號(hào)說(shuō)明：

QN（Query Neighbor）表示鄰居詢問(wèn)，用于源節(jié)點(diǎn)向其鄰居詢問(wèn)目標(biāo)節(jié)點(diǎn)的信任數(shù)據(jù)。

RN（Respond Neighbor）表示鄰居響應(yīng)，當(dāng)鄰居節(jié)點(diǎn)收到詢問(wèn)消息時(shí)，查找自身是否持有目標(biāo)節(jié)點(diǎn)的信任數(shù)據(jù)，若有給源節(jié)點(diǎn)發(fā)送一個(gè)響應(yīng)鄰居消息，將目標(biāo)節(jié)點(diǎn)的信任數(shù)據(jù)回復(fù)給源節(jié)點(diǎn)。

IN（Indication Neighbor）表示鄰居通知，用于鄰居節(jié)點(diǎn)告知源節(jié)點(diǎn)其有能力接受新的鄰居，

CN（Confirm Neighbor）表示鄰居確認(rèn)，當(dāng)源節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)的通知消息后，將其加入到自己的鄰居列表，并發(fā)送確認(rèn)鄰居消息告知鄰居節(jié)點(diǎn)。

STD（Search Trust Data）表示搜索信任數(shù)據(jù)，用于源節(jié)點(diǎn)在信任子網(wǎng)內(nèi)部搜索目標(biāo)節(jié)點(diǎn)的信任數(shù)據(jù)。

RTD（Reply Trust Data）表示答復(fù)信任數(shù)據(jù)。信任子網(wǎng)內(nèi)持有信任數(shù)據(jù)的節(jié)點(diǎn)將信任數(shù)據(jù)回復(fù)給源節(jié)點(diǎn)。

6種消息的對(duì)應(yīng)關(guān)系如圖2所示。

圖2 6種消息之間的關(guān)系

2 信任子網(wǎng)構(gòu)建

任意peeri若要查詢peerj的信任數(shù)據(jù)，需首先檢查是否有peerj的信任子網(wǎng)存在。若信任子網(wǎng)尚未建立，則peeri首先采用普遍搜索機(jī)制來(lái)搜索持有peerj的信任數(shù)據(jù)的peers，然后開(kāi)始構(gòu)建信任子網(wǎng)。信任子網(wǎng)構(gòu)建的流程圖如圖3所示。

詢問(wèn)消息格式如圖4所示。

TRUST-SUBSET.query原語(yǔ)用來(lái)詢問(wèn)鄰居節(jié)點(diǎn)是否持有某個(gè)目標(biāo)節(jié)點(diǎn)的信任數(shù)據(jù)。

peerk接收到peeri的詢問(wèn)消息后，首先將詢問(wèn)消息繼續(xù)轉(zhuǎn)發(fā)給自己的鄰居，這樣可以提高搜索信任數(shù)據(jù)的效率，然后再查找自身是否持有peerj的信任數(shù)據(jù)，若有則回復(fù)一個(gè)響應(yīng)鄰居消息給peeri，將信任數(shù)據(jù)回復(fù)給peeri，這樣，peeri不需要等到信任子網(wǎng)建立后再次發(fā)送搜索信任數(shù)據(jù)消息即可得到peerj的信任值，可以降低網(wǎng)絡(luò)開(kāi)銷(xiāo)并減少搜索訪問(wèn)信任數(shù)據(jù)的響應(yīng)時(shí)間。

圖3 信任子網(wǎng)構(gòu)建流程圖（以peerk為例）

圖4 詢問(wèn)消息格式

然后，如果節(jié)點(diǎn)k有能力接受新的鄰居，則會(huì)給peeri發(fā)送一個(gè)鄰居通知消息。peeri收到peerk的鄰居通知消息后，將其加入到自己的鄰居列表并發(fā)送一個(gè)鄰居確認(rèn)消息給peerk。peerk接收到來(lái)自peeri的鄰居確認(rèn)消息后，再將peeri加入到自己的鄰居列表中。鄰居通知和確認(rèn)消息格式如圖5所示。

鄰居通知消息：

圖5 鄰居通知消息格式

TRUST-SUBSET.indication原語(yǔ)用來(lái)通知鄰居節(jié)點(diǎn)其有能力接受新的鄰居節(jié)點(diǎn)。

鄰居通知消息：

圖6 鄰居通知消息格式

TRUST-SUBSET. confirm原語(yǔ)用來(lái)確認(rèn)新的鄰居節(jié)點(diǎn)加入成功。

3 信任數(shù)據(jù)搜索

當(dāng)信任子網(wǎng)建立后，網(wǎng)絡(luò)上的任意節(jié)點(diǎn)i欲查詢節(jié)點(diǎn)j的信任數(shù)據(jù)，可以直接向整個(gè)信任子網(wǎng)廣播搜索信任數(shù)據(jù)消息，peerk收到STD消息后將向消息的源節(jié)點(diǎn)peeri回復(fù)一個(gè)答復(fù)信任數(shù)據(jù)消息。搜索和答復(fù)信任數(shù)據(jù)消息如下：

搜索信任數(shù)據(jù)消息如圖7所示。

圖7 搜索信任數(shù)據(jù)消息格式

TRUST-SUBSET. search原語(yǔ)用來(lái)在整個(gè)信任子網(wǎng)中查詢某個(gè)節(jié)點(diǎn)的信任數(shù)據(jù)。

答復(fù)信任數(shù)據(jù)消息如圖8所示。

圖8 答復(fù)信任數(shù)據(jù)消息格式

TRUST-SUBSET. reply原語(yǔ)用來(lái)給發(fā)起查詢的節(jié)點(diǎn)答復(fù)信任數(shù)據(jù)。

4 信任子網(wǎng)維護(hù)

事實(shí)上，信任子網(wǎng)需要處理通信失敗或自由離開(kāi)的節(jié)點(diǎn)[4]。當(dāng)以下情況發(fā)生時(shí)，信任鄰居列表將會(huì)被修改。

（1）接收到IN消息。這意味著有其它節(jié)點(diǎn)已經(jīng)接受了接入請(qǐng)求，可以將其加入到自己的信任鄰居列表。

（2）接收到CN消息。這意味著自己已經(jīng)加入到源節(jié)點(diǎn)的鄰居列表，并且源節(jié)點(diǎn)也將被加入到自己的信任鄰居列表中。

（3）失敗或自由離開(kāi)。如果向信任鄰居發(fā)送消息失敗，說(shuō)明此鄰居節(jié)點(diǎn)可能已經(jīng)離開(kāi)網(wǎng)絡(luò)，則它將被從信任鄰居列表中刪除。

（4）收到非信任鄰居列表中的節(jié)點(diǎn)發(fā)送的STD消息。由于底層網(wǎng)絡(luò)的擁塞，信任子網(wǎng)中的一些節(jié)點(diǎn)可能并不知道它們已經(jīng)離開(kāi)網(wǎng)絡(luò)，而繼續(xù)發(fā)送搜索信任數(shù)據(jù)消息來(lái)搜索訪問(wèn)目標(biāo)節(jié)點(diǎn)的信任數(shù)據(jù)。當(dāng)信任子網(wǎng)中有節(jié)點(diǎn)收到這些離開(kāi)節(jié)點(diǎn)的STD消息后，可將這些節(jié)點(diǎn)再次加入到信任子網(wǎng)中。由于這些節(jié)點(diǎn)可在不發(fā)送QN、IN等消息的情況下重新加入信任子網(wǎng)，因此可以降低網(wǎng)絡(luò)開(kāi)銷(xiāo)。

（5）信任子網(wǎng)超時(shí)。如果信任子網(wǎng)的時(shí)限內(nèi)沒(méi)有信任數(shù)據(jù)搜索，信任鄰居列表將會(huì)被刪除，即該信任子網(wǎng)失效。

5 仿真設(shè)計(jì)及結(jié)果分析

5.1 仿真設(shè)計(jì)

設(shè)置拓?fù)浣Y(jié)構(gòu)中共有10 000個(gè)節(jié)點(diǎn)，對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行1到10 000編號(hào)，編程產(chǎn)生0到1的100個(gè)不同的隨機(jī)數(shù)p，用p乘以拓?fù)渲锌偟墓?jié)點(diǎn)數(shù)10 000即可產(chǎn)生0到10 000之間的100個(gè)不同的隨機(jī)數(shù)，把它們?cè)O(shè)置為持有所需信任數(shù)據(jù)的節(jié)點(diǎn)，即在網(wǎng)絡(luò)中隨機(jī)設(shè)置100個(gè)持有信任數(shù)據(jù)的節(jié)點(diǎn)。

5.2 響應(yīng)時(shí)間

由于很難直接測(cè)量系統(tǒng)的搜索響應(yīng)時(shí)間，所以一般采用消息轉(zhuǎn)發(fā)的跳數(shù)作為響應(yīng)時(shí)間的單位。同時(shí)測(cè)量不同搜索算法的最大運(yùn)行時(shí)間可以比較它們?cè)谒阉鬟^(guò)程中的響應(yīng)時(shí)間。首先假設(shè)一種簡(jiǎn)單的離散時(shí)間模型，每個(gè)節(jié)點(diǎn)接收來(lái)自其鄰居節(jié)點(diǎn)的詢問(wèn)，必要時(shí)還可以處理并繼續(xù)向其鄰居節(jié)點(diǎn)傳送詢問(wèn)副本。

由于幾種不同的搜索算法的響應(yīng)時(shí)間處于不同的數(shù)量級(jí)，所以圖9的縱坐標(biāo)采用對(duì)數(shù)坐標(biāo)，這樣可以清晰地看出它們?cè)陧憫?yīng)時(shí)間上的差別。由圖可以看出，洪泛、信任子網(wǎng)搜索、普遍搜索的響應(yīng)時(shí)間依次增加，但在同一數(shù)量級(jí)上，而淺洪泛隨機(jī)走和隨機(jī)走的響應(yīng)時(shí)間依次顯著增加且明顯大于洪泛、信任子網(wǎng)搜索和普遍搜索。

圖9 響應(yīng)時(shí)間

在仿真實(shí)驗(yàn)過(guò)程中，沒(méi)有考慮轉(zhuǎn)發(fā)消息和消息詢問(wèn)應(yīng)答延時(shí)等參數(shù)，所以洪泛的響應(yīng)時(shí)間與生存時(shí)間（Time-to-live，TTL）相同。信任子網(wǎng)搜索和普遍搜索均是對(duì)洪泛的改進(jìn)，所以它們的響應(yīng)時(shí)間處在同一數(shù)量級(jí)。信任子網(wǎng)搜索的搜索范圍相對(duì)很小，所以它的響應(yīng)時(shí)間也非常小。信任子網(wǎng)建立過(guò)程中采用普遍搜索機(jī)制，所以它們的響應(yīng)時(shí)間相同。

5.3 搜索過(guò)程中轉(zhuǎn)發(fā)消息數(shù)量

判斷搜索算法優(yōu)劣的一個(gè)重要條件是在搜索相同信息的同時(shí)使用的消息數(shù)量的多少。因?yàn)檫_(dá)到相同的搜索效果，網(wǎng)絡(luò)中轉(zhuǎn)發(fā)的消息數(shù)量越少，網(wǎng)絡(luò)負(fù)載越小，越節(jié)約網(wǎng)絡(luò)帶寬。

由圖10可以看出，只有信任子網(wǎng)搜索轉(zhuǎn)發(fā)的消息包數(shù)量非常小，而其它幾種搜索機(jī)制的轉(zhuǎn)發(fā)消息包數(shù)量相等，且隨TTL的增加顯著遞增。

圖10 搜索訪問(wèn)過(guò)程中轉(zhuǎn)發(fā)消息包數(shù)量

6 結(jié) 語(yǔ)

本文根據(jù)信任模型中信任數(shù)據(jù)搜索的特點(diǎn)，提出了一種改進(jìn)的信任數(shù)據(jù)搜索機(jī)制，即基于信任子網(wǎng)的信任數(shù)據(jù)搜索機(jī)制，該搜索機(jī)制的第一階段采用普遍搜索方法查找持有目標(biāo)節(jié)點(diǎn)信任數(shù)據(jù)的節(jié)點(diǎn)，以縮小第二階段信任子網(wǎng)建立過(guò)程中信任數(shù)據(jù)的搜索范圍。信任子網(wǎng)建立完成后，采用一種基于最小消息轉(zhuǎn)發(fā)集合的優(yōu)化洪泛策略在信任子網(wǎng)內(nèi)部搜索訪問(wèn)目標(biāo)節(jié)點(diǎn)的信任數(shù)據(jù)，該優(yōu)化策略可以避免大量的消息冗余，有效地節(jié)約網(wǎng)絡(luò)資源。

文章編程設(shè)計(jì)仿真實(shí)驗(yàn)，利用傳播消息數(shù)量（網(wǎng)絡(luò)消耗）以及最長(zhǎng)響應(yīng)時(shí)間等參數(shù)分析比較了洪泛、隨機(jī)走、淺洪泛隨機(jī)走、普遍搜索和信任子網(wǎng)搜索等搜索機(jī)制的性能。由仿真結(jié)果可以很明顯地看出，基于信任子網(wǎng)的搜索機(jī)制在轉(zhuǎn)發(fā)消息數(shù)量和響應(yīng)時(shí)間等方面的性能均比其它幾種搜索方法有較大提高。更進(jìn)一步說(shuō)，在信任模型中采用基于信任子網(wǎng)的搜索機(jī)制搜索訪問(wèn)信任數(shù)據(jù)，可以提高信任度計(jì)算的準(zhǔn)確性和計(jì)算速度，信任模型的性能隨之改進(jìn)。