基于時變半邊圖的Ｉｎｔｅｒｎｅｔ自主元素模型研究

摘要：借鑒自主計算的思想，研究Internet資源抽象的自主元素模型。引入了半邊概念描述Internet資源的特征屬性，為網絡環境下各類資源特征屬性建立一個統一描述框架。模擬無尺度網絡特性提出資源動態關聯的時變半邊圖，進而利用超分子自組裝機制建立超分子資源模型，超分子資源再被賦予環境動態感知、自主行為決策和協同等能力，形成自主元素。該方法可實現Internet資源自主負載調度，提高網絡資源效用。

關鍵詞：自主元素；時變半邊圖；無尺度網絡；超分子；自組裝

中圖分類號：TP393文獻標志碼：A

文章編號：1001－3695(2007)05－0237－04

未來的Internet將會從聯網通信逐步演變為無處不在的計算平臺。這個平臺意味著可以同時運用網絡中所有的CPU存儲、操作系統、應用軟件系統的資源。換句話說，Internet將變成一個虛擬的、非常強大的計算平臺（虛擬計算環境），包括了全球的資源。與傳統的單機或并行計算機的資源相比，Internet資源無論是在數量上還是在種類上都發生了重大變化，具有成長性、自治性和多樣性等自然特性。為了滿足用戶需求，必然使得資源的管理和使用方式也要發生相應變化，不可能也沒有必要采用傳統的全局集中控制式的管理。

本文將借鑒自主計算[1]的思想，在資源主體化的框架下，研究Internet資源抽象的自主元素模型。“自主”這個詞是由人的自主神經系統而來。自主神經系統能夠自動調節呼吸、溫度、抵抗病菌侵害等。自主元素就是希望Internet資源也能夠像人的自主神經系統一樣實現自我管理、自我監測、自我分析、自我決策和自我執行；能夠根據運行時刻的自身狀態、系統資源和外部環境狀態動態地調整和控制自身行為，適應環境的改變，實現Internet資源自主負載調度，從而提高網絡資源效用。

內容之間有機聯系如圖1所示。

1Internet資源屬性的半邊描述

在開放、動態變化的網絡環境中，資源及其關聯關系存在動態演化趨勢，相應的資源特征信息（即有關資源屬性的描述信息）也必將不斷地擴充和變化。用圖的頂點表示實體，用邊表示關系，是知識表示的常用方法，但這種方法將頂點和邊作為不可分割的原子概念。針對這個問題，本文引入了一個比邊更基本的圖元素，稱為可結合半邊，簡稱半邊。在圖中，資源視為頂點，資源的屬性信息表示為半邊，不同頂點的半邊依據可結合性而結合起來稱為邊，邊表示資源之間的關聯關系。有了半邊，邊就不再是不可分的原子了。

1．1半邊

資源屬性用半邊描述，資源有若干屬性，對應于一個頂點有若干個半邊。半邊具有以下特點：

（1）一個半邊屬于某個頂點且分為不同的半邊類型。半邊類型由資源特征屬性決定，半邊類型集合記為H。（2）半邊與其他的半邊可以相結合。稱有序半邊類型對為半邊結合類型，表示什么類型的兩個半邊可以結合。所有的半邊結合類型所成的集合稱為半邊結合類型集合，表示資源特征屬性之間的相互作用關系集合記為R。

（3）每個半邊還有一個數值性度量值，稱為半邊權值。一般取大于0的實數，與資源相關屬性的載荷情況成反比，即半邊權值越大，資源相關屬性的載荷越小（對于非數值型屬性可用云模型[6]轉換成定量數值屬性，方便計算機進行數值處理）。

1．2頂點

頂點是資源的抽象表示，是組成圖的基本元素。頂點集合記為V，頂點有若干半邊，不同頂點的半邊可以相互識別與結合。這樣，資源之間就實現了關聯。

1．3邊

若兩個頂點的兩個半邊類型對是半邊結合類型，則這兩個半邊就可以相結合；若兩個半邊已經結合在一起，則兩個半邊合起來稱為一個邊。邊集合記為E。邊具有以下特點：

（1）邊類型對應于半邊結合類型，對應于資源之間的關聯。

（2）每個邊可以依據其兩個組成半邊的權值由邊權計算函數計算出一個數值作為邊的權值。其中，邊權計算函數滿足非負性、單調性條件，如可取min/max/average等。

已給出的三個主要概念及它們之間的基本關系如下：

（1）半邊是資源屬性的抽象概念。這些屬性還可以根據不同問題的需要添加和修改，能滿足有關資源屬性的描述信息擴充和變化，具有很好的時變特點；半邊不獨立存在于圖中，一個半邊一定依附于某個頂點，即一個屬性一定依附于某個資源。

（2）頂點是資源的抽象表示，有若干個半邊。頂點是圖演算中能夠獨立存在與運算的基本要素。

（3）邊由兩個可結合的半邊組成。但由于半邊必須附屬于頂點，邊不能獨立于頂點而存在于圖中，或可以認為邊是由頂點導出的。

2模擬無尺度網絡生成時變半邊圖

資源的多樣性使得資源描述的復雜度急劇加大；同時，資源的成長性和自治性使得資源配置只能在變化中保持視圖的動態穩定。

2．1時變半邊圖

2．2在圖中加邊和減邊

在本文，圖不是最基本要素，它是一種由半邊、頂點以及邊構成的組合體。實際問題中的動態過程則需要由圖的構造過程來模擬。

（1）加邊操作

（2）減邊操作

2．3生成時變半邊圖

（1）無尺度網絡

用規則圖研究分析網絡結構，范圍很有限。1959年，數學家Erdobs 和Renyi提出了ER隨機網絡模型。在這種模型中，兩個節點（習慣上，網絡拓撲中連接點稱為節點，圖中各邊的連接點稱為頂點。在本文中不區分節點和頂點）之間是否有邊相連不再是確定的，而是根據一個概率決定。在科學界，這種方法主導了半個世紀，但這種方法是靜態的，對于開放、動態變化的網絡環境，存在動態演化趨勢的資源及其關聯關系不能進行分析研究。

1999年Barabási和Albert在《Science》上發表論文，指出許多現實復雜網絡的度分布具有冪律分布規律P(k)=ck-γ。其中的γ與網絡規模無關，稱為無尺度網絡（Scale－Free Networks）[4]。并以他們的名字命名為BA模型。BA模型第一次把冪律分布引入網絡。它描述的是一個生長的開放系統， 從一個小組核心節點開始，在網絡進行的整個過程中，外界會不斷地有節點加入這個系統。BA 模型中有兩個主要因素，即節點生長和連接偏好。 

本文先對Internet資源引入半邊描述，將各類資源抽象為圖中節點， 各種相互作用抽象為資源之間的連接線或邊，并根據Internet資源的自然特性對BA模型加以調整。考慮到資源既有增加，也有減少的可能，本文給出一種資源動態關聯圖的構造算法：

（2）時變半邊圖構造算法

（1）以p的概率增加一個新節點。

（2）從新節點出發，對K個節點進行加邊操作；節點被選中的概率與該節點的度成正比。

（3）以q的概率決定是否刪除一個節點，及對與該節點相連的所有邊進行減邊操作；如果減邊，那么減去與哪個節點相連的邊，與該節點的度成反比。

（4）返回（1），直到生成一定數量的節點或達到計算要求為止。

通過資源屬性之間的結合性逐步建立邊而動態導出一個圖，即圖不是人為確定的，也不是客觀上預先存在的，而是由資源集合導出的。如圖3中時變半邊圖可由圖2 中Internet資源經過有限步關聯生成。時變半邊圖很好地描述了Internet資源屬性之間的依賴關系。

3超分子資源自組裝

在許多實際應用中，自主元素問題可以抽象為如下提法：將一個時變半邊圖按給定的聚類標準分解為若干相對簡單一些的組合模式。本文將一個由Internet資源集合構成的時變半邊圖，按不同的組裝準則自組裝為若干小的相對簡單一些的子組合模式。滿足如下兩個條件：

（1）資源的組裝準則應是各個組合模式互不相同的。

（2）同一個資源應可以屬于多個組合模式。

1987年Nobel化學獎獲得者C.J.Pedersen、D.J.Cram和J.M.Lehn提出了超分子化學概念[5]，并給出了超分子自組裝機制：超分子的形成是分子導向性識別引起的特定的、有限數目分子的組分在分子間的非共價相互作用控制下聚集到一起的自發過程。由于動力學的不穩定性，分子識別使自組裝體系具有退火和自我修復的能力。本文在超分子自組裝機制思想的指導下，組裝過程的子組合模式也稱為超分子資源。因此，超分子自組裝對應于將一個時變半邊圖自組裝為若干個超分子資源，具有同質性的頂點和邊組裝在同一個超分子資源中。不同的超分子資源之間有組裝準則上的差別。由于同一個頂點或邊可能符合不同的組裝準則，一個頂點或一個邊可以屬于不同的超分子資源。



3．1超分子資源與自組裝準則

（1）超分子資源

將上述過程稱為自組裝。其中的各個子圖稱為圖G的超分子資源。

自組裝與圖劃分的區別：自組裝不是對圖的劃分。圖的劃分一般是指劃分后的各個子圖之間不相交；而自組裝對組裝后的各個子圖之間相交與否未作限定，各個超分子資源之間可以相交，也可以不相交。

（2）自組裝準則

自組裝算法實際上是聚類算法。聚類是將物理或抽象對象的集合分組為由類似對象組成的多個類的過程。圖就相當于抽象對象（半邊、頂點、邊）的集合；自組裝就是對抽象對象集合的分類。按聚類的定義，聚類算法的關鍵是對象之間相似性的評判標準，不同的標準就會有不同的分類結果。自組裝算法同樣需要這樣的評判標準，各種評判標準可以通稱為自組裝準則。任何一個具體的自組裝準則均涉及兩個基本概念，即圖中的對象和對象之間的相似性。

時變半邊圖中的對象有半邊、頂點和邊。其中半邊是組成圖的最基本元，但不能獨立存在，故不適合于作為自組裝對象；頂點和邊均為具體模式性質的獨立基元要素，所以適合于作為自組裝的對象。時變半邊圖中對象之間的相似性可以指頂點之間的相似性，也可以指邊之間的相似性，而圖本身的一些性質也可以成為自組裝的評判準則，如圖的連通性、無環性等均可作為自組裝判別準則。下面給出一個以邊的相似性為聚類標準的同類邊自組裝準則。

同類邊自組裝準則：一個時變半邊圖自組裝后，每個超分子資源內的所有頂點只有同一種類型的邊互相連接，即一個超分子資源是以某一特定的邊類型為自組裝準則通過聚類算法來確定的。

3．2自組裝模型及其算法

（1）模型

輸入：①一個資源集合和資源屬性關系集（半邊結合類型）構成的時變半邊圖；

②一些針對資源及其關系的不同的組裝準則；超分子資源粒度可由自組裝準則來反映。

求解過程：將時變半邊圖按不同的組裝準則自組裝成一些超分子資源。

輸出：超分子資源集合。超分子資源滿足如下兩個條件：①各個超分子資源是按互不相同的組裝準則獲得的；②各個超分子資源之間可以相交。

上述模型類似于聚類分析算法，如DBSCAN[7]和CHAMELEON[8]。但在聚類準則和聚類結果上，自組裝模型與已有的聚類分析算法有很大不同：

①已有的一些聚類算法的聚類準則均是單一的。例如DBSCAN中的聚類準則是一個依據距離計算出的統一的密度度量準則；CHAMELEON中的聚類準則是根據距離計算出的相似度準則；而自組裝模型的組裝準則可以是性質和表現均不同的特異性準則。

②已有的一些聚類算法雖然不強調各個聚類后的子類之間一定不相交，但在算法的實現上均是按照聚類的各個子類不相交這一準則來做的，即基元要素不能同時屬于兩個以上的子類。這也是在統一的距離準則或相似度準則的制約下的自然做法。而自組裝模型的各個組裝模式之間可以相交。

模型示意圖如圖4所示。

(2)算法

注：邊分類算法可以是一個通用子算法，這里只給出了功能說明，具體實現較簡單，故省略。

（3）自組裝算法結束。

4基于超分子自組裝機制的自主元素模型

自主元素是資源的抽象載體或虛擬化單元，也是對虛擬計算環境下各種異構和多樣化資源的抽象表示。它能夠通過靈活的封裝屏蔽各類資源的異構性，是虛擬計算環境中的基本資源管理單位。

自主元素是對傳統計算機中各類資源概念的延伸。以資源主體化為出發點，將靜態、被動的資源客體變成能夠獨立提供服務的、活躍的行為主體； 使資源主體具備自主決策、適應變化和可成長演化的能力。

在上述超分子資源模型的基礎上，可建立動態、可交叉的自主元素模型。對超分子資源組裝對象（多種異構資源）進行封裝，并賦予其環境動態感知、自主行為決策和協同等能力（內部結構如圖5所示），從而形成抽象的計算能力和軟件功能等。

自主元素的核心是自我監測、自我分析、自我決策和自我執行。自我監測，即自主元素能夠知道內部每個資源當前的狀態、容量以及它們之間的連接關系等信息；自我分析，即自主元素對環境的動態分析能夠自動完成；自我決策，即自主元素能根據需要自動調整；自我執行，即自主元素能夠自動調度資源，以滿足任務需求。也就是說，Internet資源完成半邊描述后，模擬無尺度網絡生成時變半邊圖，并在自組裝準則指導下，自組裝成超分子資源集；超分子資源通過自我監測修改Internet資源的半邊描述，并通過自我分析修改時變半邊圖。而自組裝準則可以根據需要由自我決策完成，自我執行即自組裝最終得到自主元素。

自主元素與Internet上資源之間具有一對多或多對一的關系，即一個自主元素可能對多個資源進行抽象和封裝，并被賦予環境動態感知、自主行為決策和協同等能力；一個資源也可能被封裝成多個自主元素。如圖6所示，自主元素A對資源2、4、7進行抽象和封裝，而資源8被封裝為自主元素D、E。

5結束語

本文引入半邊概念描述Internet資源的特征屬性，為網絡環境下各類資源特征屬性建立一個統一描述框架。該概念的提出，較好地解決了不斷擴充和變化的資源特征信息描述問題。通過分析大規模Internet資源相互作用所具有的網絡特性，模擬無尺度網絡提出資源動態關聯的時變半邊圖；由超分子自組裝機制啟發，建立了超分子資源模型；超分子資源再被賦予環境動態感知、自主行為決策和協同等能力，從而形成自主元素。該模型的提出可以對軟件和硬件資源進行優化利用，從而使閑置資源可以被有效利用，進而提高整個Internet的性能。某個應用所釋放的資源可以及時補充給其他應用，最終的自主元素可以做到自我監測、自我分析、自我決策和自我執行，并能夠對環境變化作出及時反應。

本文目的在于使Internet可以按照應用的需求來分配共享資源，能夠自動地對自身進行管理，讓Internet資源的使用更加簡便，并維持其可靠性，為虛擬計算環境下按需聚合和自主協同的實現打下堅實的基礎。

參考文獻：

［1］VIDALES P， BALIOSIAN J， SERRAT J，et al. Autonomic system for mobility support in 4G networks[J]. IEEE Journal on Selected Areas in Communications，2005，23(12):2288－2304.

[2]孟朝暉.半邊圖與擠出吸入算法及制造單元設計[J].計算機工程與應用，2005，41(24):228－232.

[3]孟朝暉.半邊圖模型之多層次認知系統[J].計算機工程與應用，2006，42（30）：28－34.

[4]BARABSI A L， ALBERT R. Emergence of scaling in random networks [J]. Science， 1999， 286(5439):509－512.

[5]LEHN J M. Supermolecular chemistry: concepts and perspectives[M]. Weinheim:VCH，1995. 

[6]李德毅，杜鹢.不確定性人工智能[M].北京:國防工業出版社，2005.

[7]ESTER M， KRIEGEL H P， SANDER J， et al. A density－based algorithm for discovering clusters in large spatial databases with noise:proc.of the 2nd International Conference on Knowledge Discovery in Databases and Data Mining (KDD’96)[C]. Portland:[s.n.]，1996:226－231.

[8]KARYPIS G， HAM E H， KUMAR V. CHAMELEON: a hierarchical clustering algorithm using dynamic modeling[J]. Computer，1999，32(8):68－75.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”