不確定網(wǎng)絡條件可信近鄰查詢

郭長友 鄭雪峰 高秀蓮

?

不確定網(wǎng)絡條件可信近鄰查詢

郭長友*①②鄭雪峰①高秀蓮②

①(北京科技大學計算機與通信工程學院 北京 100083)②(德州學院 德州 253000)

不確定因素在現(xiàn)實世界中普遍存在，因此研究不確定網(wǎng)絡條件可信近鄰查詢具有重要意義。該文給出一種新的解決方法。將不確定網(wǎng)絡建模為不確定賦權圖，定義不確定圖的樣本圖，樣本圖指數(shù)，基礎網(wǎng)絡，可達路徑長度及可達路徑期望長度，并給出基于不確定理論的高效不確定圖條件可信近鄰查詢算法。將不確定網(wǎng)絡上的近鄰查詢等價地轉化為基礎網(wǎng)絡上的近臨查詢問題。理論分析和實驗結果表明所提可信近鄰查詢算法能夠從非確定角度解決不確定網(wǎng)絡環(huán)境下的近鄰查詢問題。

不確定網(wǎng)絡；不確定圖；樣本圖指數(shù)；可信距離；基礎網(wǎng)絡

1 引言

現(xiàn)實世界中，不確定因素普遍存在于各種現(xiàn)象中，因此研究不確定網(wǎng)絡的可信近鄰查詢具有重要意義。例如，在云計算環(huán)境下，數(shù)據(jù)中心的選址問題。云計算環(huán)境下，虛擬機、虛擬集群的遷移、調(diào)度問題。Ad-hoc網(wǎng)絡的遷移、自組織問題，傳統(tǒng)網(wǎng)絡模型無法刻畫、表示、求解這些問題，所以對不確定網(wǎng)絡的研究需要也越來越迫切。數(shù)據(jù)中心[1]是為各種IT應用和服務提供的中心，是集數(shù)據(jù)計算、交換和存儲為一體的中心。數(shù)據(jù)中心主要由計算、網(wǎng)絡、存儲、災備4個要素組成。網(wǎng)絡是數(shù)據(jù)中心的基礎設施，包括交換機、連接線路、數(shù)據(jù)中心網(wǎng)絡優(yōu)化設備等。云計算虛擬化技術[2]的出現(xiàn)使得運行在虛擬機上的服務器能夠很方便地遷移。將云計算網(wǎng)絡中的數(shù)據(jù)中心抽象建模為圖，由于異構性、隱私保護、數(shù)據(jù)不完整、數(shù)據(jù)不精確等原因，該圖數(shù)據(jù)存在不確定性。對于不確定性數(shù)據(jù)處理，目前已有很多成果，多集中在實體數(shù)據(jù)的不確定性，對現(xiàn)實中一些實際問題覆蓋還不夠。云計算網(wǎng)絡上數(shù)據(jù)中心之間的距離不是一個具體的數(shù)，而是一個不確定量，這時就無法用傳統(tǒng)的基于兩點間有確定距離值的算法，求得最有效近鄰。此時，不確定網(wǎng)絡中的近鄰查詢問題的研究就非常有必要了。對于實體間關系的非確定性處理，文獻[3,4]運用隨機和模糊理論解決近鄰查詢處理問題。

實際上，在上述文獻中還是用概率、模糊刻畫現(xiàn)實中的實體間關系，不能科學地反映被判斷對象的真實情況。而實體間關系有時還表現(xiàn)為主觀不確定性，這種主觀不確定性既不是隨機的也不是模糊的，如云計算網(wǎng)絡上數(shù)據(jù)中心內(nèi)部虛擬機之間的動態(tài)遷移性，使得數(shù)據(jù)在遷移前考慮源和目的節(jié)點間的距離、成本、代價等數(shù)據(jù)時具有很大的主觀不確定性。再者，模糊圖中兩點間的最短距離的可信度用求和來計算也存在問題。因為可信度的取值范圍應該是在[0,1]區(qū)間，故對兩點間最短距離的可信度用求和運算存在溢出等不合理現(xiàn)象，建立在模糊理論基礎上的這些方法都不能從根本上解決上述問題。據(jù)我們所知，基于不確定理論的不確定網(wǎng)絡條件可信近鄰查詢尚未被研究過。現(xiàn)實中，很多問題無法獲得歷史數(shù)據(jù)，從而無法用概率論求解事件發(fā)生的頻率，此時必須依據(jù)專家經(jīng)驗對事件可能發(fā)生的信度進行評估，此方法使得信度的方差遠遠大于頻率。為了處理主觀不確定性，文獻[5-7]于2007年創(chuàng)立了數(shù)學的一個新的分支不確定理論。之后不確定理論被廣泛應用于科學和工程中，解決了許許多多的問題。

本文是運用不確定理論對復雜云計算環(huán)境下數(shù)據(jù)中心不確定網(wǎng)絡的近鄰查詢問題進行分析、評價和測試，提出了不確定網(wǎng)絡在信度、距離等條件約束下近鄰查詢新的解決方法，理論分析與實驗結果表明，不確定網(wǎng)絡條件可信近鄰查詢算法能夠從不確定角度解決不確定網(wǎng)絡環(huán)境下的近鄰查詢問題，且符合實際情況。

2 相關概念

2.1 不確定理論

不確定理論是清華大學劉寶碇教授在2007年[5]提出并于2010年[6]進行了修訂，為處理不確定因素提供了一種新的研究方法。

現(xiàn)在，我們介紹一些本文所用的不確定理論的概念和結果[6]。

2.2 不確定圖的相關概念

集合元素之間的關系可以用兩個相關元素構成的有序對來表示。這種關系可以用經(jīng)典圖論中的圖來表示，即用結點(稱之為圖的頂點)表示實體，結點間的連線(稱之為圖的邊)表示實體間的關系，若給圖中的頂點或邊賦予一定的信息(稱之為權)，則將此圖稱之為網(wǎng)絡，例如以云計算數(shù)據(jù)中心為結點構建的云計算網(wǎng)絡，兩個云計算數(shù)據(jù)中心之間的距離就可以用他們之間的邊權來表示。但是現(xiàn)實生活中，兩個實體之間是否有關系不能完全確定，有時即使關系能確定，但關系信息(即權值)卻不能確定，那么如何來刻畫這種關系呢? 本文先給出相關概念。

定義 2(不確定網(wǎng)絡) 不確定網(wǎng)絡是指網(wǎng)絡實體確定而實體間關系的權值不確定，表現(xiàn)為實體間關系權值的不確定性。

不確定網(wǎng)絡中關系權值的不確定性可以是某種關系權值是否存在，如云計算網(wǎng)絡中以參與計算的數(shù)據(jù)中心之間的距離為權，也可以是某種關系權值的取值情況以不同的不確定測度存在，如云計算網(wǎng)絡中以參與計算的數(shù)據(jù)中心之間的流量速度為權，本文所指的不確定網(wǎng)絡均為前者，后者將另行撰文。

定義 3[12](不確定圖) 設表示不確定圖，其中，表示圖的結點集；表示圖的邊集；表示邊存在的不確定測度集。表示邊存在的不確定測度。其中,表示邊一定存在，表示邊一定不存在，稱為不確定邊。

我們將網(wǎng)絡實體確定，實體間關系的不確定性用不確定圖來描述。結點表示網(wǎng)絡實體，邊表示實體間關系，邊的不確定測度表示實體間關系的可信度。經(jīng)典圖論中的圖可以用它的鄰接矩陣表示，不確定圖也可以用它的鄰接矩陣表示。從不確定圖的定義中，我們可以得出這樣的結論：不確定圖的邊集中每個元素都是一個不確定布爾變量，其權值是此元素取值為1時的不確定測度。即，其中,。為簡單起見，移除滿足的邊，而將邊集表示為。

不確定圖可分為有向圖與無向圖，加權圖與無權圖。這里討論的是無向加權不確定圖(即不確定網(wǎng)絡)。圖為不確定圖及其鄰接矩陣示例。

圖1 不確定圖及其鄰接矩陣示例

圖 2 圖1的樣本圖示例

為了說明不確定圖是某個樣本圖，下面給出樣本圖指數(shù)的定義。

關鍵的問題是當給出了一個不確定圖時，如何獲得它的樣本圖指數(shù)。下面的定理解決了這個問題。

根據(jù)定義5，不確定圖的樣本圖指數(shù)是指這個圖是此樣本圖的不確定測度。因此定理2得證。

定義6 賦權樣本圖中兩點間路徑的權是指這條路徑上所有邊的權和，賦權樣本圖中兩點間最短路徑是指這兩點間所有路徑中權最小的路徑，最小路徑的權稱為這兩點之間的距離，記為表示在中的距離為為的可信度為。

圖3 不確定網(wǎng)絡示例

圖4 圖3的賦權樣本圖示例

2.3 可信距離的計算方法

表 1 可信距離查詢算法

算法1 不確定網(wǎng)絡中任意兩點間的可信距離查詢算法

(1)先將不確定網(wǎng)絡建模為不確定圖，求得不確定圖的鄰接矩 陣；

(3)由不確定圖的鄰接矩陣和樣本圖的鄰接矩陣及樣本圖指數(shù)

的定義可計算得出所有樣本圖指數(shù)；

(4)找出不確定網(wǎng)絡的所有賦權樣本圖；

不確定網(wǎng)絡圖中任意兩點間可信距離的精確計算時間復雜度較高，達到指數(shù)級。在現(xiàn)實生活中，由于各種因素的限制，往往并不追求最優(yōu)解，只要求得到一個滿意解即可，因此采用以下兩種方法進行近似計算。

圖5 圖3的基礎網(wǎng)絡

2.4 可達路徑長度計算

表 2 可達路徑長度計算算法

算法 2 不確定網(wǎng)絡中任意兩點間的可達路徑長度算法

(3)根據(jù)定義6，計算出基礎網(wǎng)絡中找出的任意兩點間的所有簡單路徑的信度；

2.5 可達路徑期望長度計算

3 條件可信近鄰查詢

表 3 可達路徑期望長度計算算法

算法 3 不確定網(wǎng)絡中任意兩點間的可達路徑期望長度算法

(3)根據(jù)定義6，計算出基礎網(wǎng)絡中找出的任意兩點間的所有簡單路徑的信度；

表 4 條件可信近鄰查詢算法

算法 4 條件可信近鄰查詢算法

條件可信近鄰查詢計算方法的主要步驟如下：

下面給出一個云計算數(shù)據(jù)中心資源管理中虛擬機遷移的例子來說明不確定網(wǎng)絡中條件可信近鄰查詢的應用。在虛擬化云計算資源的管理過程中將資源負載結點抽象為不確定網(wǎng)絡的結點，將資源負載異常結點和待遷移目標結點間的可遷移性抽象為不確定網(wǎng)絡中不確定邊的信度，將遷移過程所消耗的時間抽象為不確定網(wǎng)絡中不確定邊的權重。如圖所示不確定網(wǎng)絡近鄰查詢示例圖中，共有個節(jié)點，條邊，其中數(shù)字表示節(jié)點，邊的權為，可信度為；邊的權為，可信度為；邊的權為, 可信度為；其余邊的權及可信度如圖所示。

圖 6 不確定網(wǎng)絡近鄰查詢示例

由條件可信近鄰查詢計算方法，按如下步驟計算：

圖7 刪除不滿足信度條件不確定邊后的不確定網(wǎng)絡

圖 8 圖7的基礎網(wǎng)絡

4 實驗結果分析

下面通過實驗來驗證本文所提出的不確定網(wǎng)絡條件可信近鄰查詢算法的執(zhí)行效率及其穩(wěn)定性。由于目前尚沒有處理不確定網(wǎng)絡中基于信度、可達路徑期望長度等條件約束下的可信近鄰查詢算法，因此本文主要考察提出的查詢方法在不同規(guī)模的數(shù)據(jù)集上以及不同約束條件下的效率。

實驗使用定義2中定義的不確定網(wǎng)絡。隨機生成T1,T2,×××,T10 10個不確定網(wǎng)絡。每個不確定網(wǎng)絡的節(jié)點和不確定邊的數(shù)量如表5所示。每個不確定網(wǎng)絡的不確定邊隨機在兩個點間生成，每個不確定邊的信度為隨機生成的間的實數(shù)，每個不確定邊的權重為隨機生成的間的實數(shù)。

實驗 1 測試可信度對基于可信距離的近鄰查詢算法的影響，可信度的查詢結果如圖所示。從圖可知，可信度對基于可信距離的近鄰查詢算法有相似分布，隨著不確定網(wǎng)絡中節(jié)點和不確定邊的數(shù)量變化而相應變化。

表 5 實驗使用人工模擬的不確定網(wǎng)絡數(shù)據(jù)

實驗 2 測試可達路徑期望長度對基于可信距離的近鄰查詢算法的影響?？蛇_路徑期望長度的查詢結果如圖所示。從圖可知，可達路徑期望長度對基于可信距離的近鄰查詢算法情況相似，有相似分布，隨著不確定網(wǎng)絡中節(jié)點和不確定邊的數(shù)量變化而相應變化。

5 結束語

本文研究了不確定網(wǎng)絡條件可信近鄰查詢問題，首次運用不確定理論形式化定義了不確定網(wǎng)絡條件可信近鄰查詢問題，提出了基于不確定理論的不確定網(wǎng)絡、不確定圖及其鄰接矩陣、樣本圖及其指數(shù)、不確定網(wǎng)絡中兩點間距離、可信距離的定義，設計了不確定網(wǎng)絡中任意節(jié)點間可信距離的求解算法。鑒于不確定網(wǎng)絡中，節(jié)點間可信距離的精確計算代價較高，本文又提出了不確定網(wǎng)絡的基礎網(wǎng)絡、可達路徑長度、可達路徑期望長度的定義，在此基礎上給出了信度，可達路徑長度(或可達路徑期望長度)約束條件下的高效可信近鄰查詢算法。本文進行了大量實驗來考察該算法的性能。

理論分析與實驗結果表明算法可行且性能穩(wěn)定，能有效處理不確定網(wǎng)絡條件可信近鄰查詢。在不確定網(wǎng)絡中同時考慮不確定性與隨機性，使非確定網(wǎng)絡環(huán)境下的不確定隨機近鄰查詢更有效是下一步的研究方向。

圖 9 可信距離分布 圖 10 可信距離與樣本數(shù)關系

[1] 羅亮, 吳文峻, 張飛. 面向云計算數(shù)據(jù)中心的能耗建模方法[J]. 軟件學報, 2014, 25(7): 1371-1387. doi: 10.13328/j.cnki. jos.004604.

LUO L, Wu W J, and Zhang F. Energy modeling based on clouddata center[J]., 2014, 25(7): 1371-1387. doi: 10.13328/j.cnki.jos.004604.

[2] 殷波, 王穎, 邱雪松, 等. 一種面向云服務提供商的資源分配機制[J]. 電子與信息學報, 2014, 36(1): 15-21. doi: 10.3724/ SP.J.1146.2013.00427.

Yin Bo, Wang Ying, Qiu Xuesong,. A resource provisioning mechanism for service providers in cloud[J].&, 2014, 36(1): 15-21. doi: 10.3724/SP.J.1146.2013.00427.

[3] 張海杰, 姜守旭, 鄒兆年. 不確定圖上的高效top-近鄰查詢處理算法[J]. 計算機學報, 2011, 34(10): 1885-1896. doi: 10.3724/SP.J.1016.2011.01885.

Zhang Haijie, Jiang Shouxu, and Zou Zhaonian. An efficient algorithm for top-proximity query on uncertain graph[J]., 2011, 34(10): 1885-1896. doi: 10.3724/SP.J.1016.2011.01885.

[4] 高峻, 郝忠孝. 受限模糊網(wǎng)絡可信近鄰查詢[J]. 計算機工程, 2015, 41(1): 54-60. doi: 10.3969/j.issn.1000-3428.2015.01.010.

Gao Jun and Hao Zhongxiao. Credible nearest neighbor query in constraint fuzzy network[J]., 2015, 41(1): 54-60. doi: 10.3969/j.issn.1000-3428.2015.01. 010.

[5] Liu B. Uncertainty Theory[M]. 2nd ed., Berlin: Springer- Verlag, 2007, Chapter 1-Chapter 2 .

[6] Liu B. Uncertainty Theory: A Branch of Mathematics for Modeling Human Uncertainty[M]. Berlin: Springer-Verlag, 2010, Chapter 1-Chapter 2.

[7] Liu B. Uncertainty distribution and independence of uncertain processes[J]., 2014, 13(3): 259-271. doi: 10.1007/s10700-014- 9181-5.

[8] Zhou J, Chen L, and Wang K. Path optimality conditions for minimum spanning tree problem with uncertain edge weights[J].,-, 2015, 23(1): 49-71. doi: 10.1142/s0218488515500038.

[9] Gao X L. Uncertain relations on a finite set and their properties[J]., 2014, 3(1): 13-19. doi: 10.11648/j.pamj.s.20140301.13.

[10] Gao X L. Tree index of uncertain graphs[J]., 2015. doi: 10.1007/s00500-015-1597-5.

[11] Gao X L and Gao Y. Connectedness index of uncertainty graphs[J].,-, 2013, 21(1): 127–137. doi: 10.1142/S0218488513500074.

[12] Gao X L. Regularity index of uncertain graph[J].&, 2014, 27(4): 1671-1678. doi: 10.3233/IFS-141133.

[13] Ding S B. Uncertain minimum cost flow problem[J]., 2014, 18(11): 2201-2207. doi: 10.1007/s00500- 013-1194-4.

[14] Gao X, Gao Y, and Ralescu D. On Liu’s inference rule for uncertain systems[J].,-, 2010, 18(1): 1-11. doi: 10.1142/S0218488510006349.

[15] Gao Y, Yang L X,. On distribution function of the diameter in uncertain graph[J]., 2015, 296(1): 61-74. doi: 10.1016/j.ins.2014.10.048.

[16] Gao Y. Shortest path problem with uncertain arc lengths[J]., 2011, 62(6): 2591-2600. doi: 10.1016/j.camwa.2011.07.058.

[17] Liu B. Some research problems in uncertainty theory[J]., 2009, 3(1): 3-10.

郭長友： 男，1976年生，副教授，研究方向為網(wǎng)絡安全.

鄭雪峰： 男，1951年生，教授，研究方向為計算機系統(tǒng)安全、網(wǎng)絡安全.

高秀蓮： 女，1969年生，副教授，研究方向為圖論與組合優(yōu)化.

Foundation Items: The National Natural Science Foundation of China (61163025), The Project of Beijing Key Laboratory of Knowledge Engineering for Materials Science (Z121101002812005)

Credible Nearest Neighbor Query in Uncertain Network

GUO Changyou①②ZHENG Xuefeng①GAO Xiulian②

Uncertain factors are a common phenomenon in the real world; therefore, it is very meaningful to study on the trusted neighbor query under uncertain network conditions. This paper puts forwards a new solution. The uncertain network is modeled as uncertain weighed graph, and these definitions of the uncertain graph are given, such as sample graph, sample graph index, base network, length of feasible path and expected length of feasible path. Based on these the high-efficiency credible neighbor query algorithm for uncertain graph is put forward under constraint conditions. This algorithm is transforms the issue of neighbor query in the uncertain network equivalently to the issue of neighbor query in the base network. The theoretic analysis and experimental results show that the credible neighbor query algorithm proposed in the paper can solve the neighbor query problem in the environment of the uncertain network from non-deterministic perspective.

Uncertain networks; Uncertain graph; Sample graph index; Credible distance; Basic networks

TP309.5

A

1009-5896(2016)04-0811-08

10.11999/JEIT150748

2015-06-23；改回日期：2015-12-08；網(wǎng)絡出版：2016-01-22

郭長友 guochangyouustb@139.com

國家自然科學基金(61163025)，北京市重點實驗室2012年度階梯計劃項目(Z121101002812005)