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

金 芳

（中國人民解放軍91404部隊，河北 秦皇島 066000）

0 引 言

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

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

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

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

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

消息形式如圖1所示。

圖1 消息形式

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

符號說明：

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

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

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

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

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

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

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

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

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

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

詢問消息格式如圖4所示。

TRUST-SUBSET.query原語用來詢問鄰居節(jié)點是否持有某個目標節(jié)點的信任數(shù)據(jù)。

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

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

圖4 詢問消息格式

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

鄰居通知消息：

圖5 鄰居通知消息格式

TRUST-SUBSET.indication原語用來通知鄰居節(jié)點其有能力接受新的鄰居節(jié)點。

鄰居通知消息：

圖6 鄰居通知消息格式

TRUST-SUBSET. confirm原語用來確認新的鄰居節(jié)點加入成功。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.1 仿真設(shè)計

設(shè)置拓撲結(jié)構(gòu)中共有10 000個節(jié)點，對每個節(jié)點進行1到10 000編號，編程產(chǎn)生0到1的100個不同的隨機數(shù)p，用p乘以拓撲中總的節(jié)點數(shù)10 000即可產(chǎn)生0到10 000之間的100個不同的隨機數(shù)，把它們設(shè)置為持有所需信任數(shù)據(jù)的節(jié)點，即在網(wǎng)絡(luò)中隨機設(shè)置100個持有信任數(shù)據(jù)的節(jié)點。

5.2 響應(yīng)時間

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

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

圖9 響應(yīng)時間

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

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

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

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

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

6 結(jié) 語

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

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