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

摘要：借鑒自主計(jì)算的思想，研究Internet資源抽象的自主元素模型。引入了半邊概念描述Internet資源的特征屬性，為網(wǎng)絡(luò)環(huán)境下各類資源特征屬性建立一個統(tǒng)一描述框架。模擬無尺度網(wǎng)絡(luò)特性提出資源動態(tài)關(guān)聯(lián)的時變半邊圖，進(jìn)而利用超分子自組裝機(jī)制建立超分子資源模型，超分子資源再被賦予環(huán)境動態(tài)感知、自主行為決策和協(xié)同等能力，形成自主元素。該方法可實(shí)現(xiàn)Internet資源自主負(fù)載調(diào)度，提高網(wǎng)絡(luò)資源效用。

關(guān)鍵詞：自主元素；時變半邊圖；無尺度網(wǎng)絡(luò)；超分子；自組裝

中圖分類號：TP393文獻(xiàn)標(biāo)志碼：A

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

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

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

內(nèi)容之間有機(jī)聯(lián)系如圖1所示。

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

在開放、動態(tài)變化的網(wǎng)絡(luò)環(huán)境中，資源及其關(guān)聯(lián)關(guān)系存在動態(tài)演化趨勢，相應(yīng)的資源特征信息（即有關(guān)資源屬性的描述信息）也必將不斷地?cái)U(kuò)充和變化。用圖的頂點(diǎn)表示實(shí)體，用邊表示關(guān)系，是知識表示的常用方法，但這種方法將頂點(diǎn)和邊作為不可分割的原子概念。針對這個問題，本文引入了一個比邊更基本的圖元素，稱為可結(jié)合半邊，簡稱半邊。在圖中，資源視為頂點(diǎn)，資源的屬性信息表示為半邊，不同頂點(diǎn)的半邊依據(jù)可結(jié)合性而結(jié)合起來稱為邊，邊表示資源之間的關(guān)聯(lián)關(guān)系。有了半邊，邊就不再是不可分的原子了。

1．1半邊

資源屬性用半邊描述，資源有若干屬性，對應(yīng)于一個頂點(diǎn)有若干個半邊。半邊具有以下特點(diǎn)：

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

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

1．2頂點(diǎn)

頂點(diǎn)是資源的抽象表示，是組成圖的基本元素。頂點(diǎn)集合記為V，頂點(diǎn)有若干半邊，不同頂點(diǎn)的半邊可以相互識別與結(jié)合。這樣，資源之間就實(shí)現(xiàn)了關(guān)聯(lián)。

1．3邊

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

（1）邊類型對應(yīng)于半邊結(jié)合類型，對應(yīng)于資源之間的關(guān)聯(lián)。

（2）每個邊可以依據(jù)其兩個組成半邊的權(quán)值由邊權(quán)計(jì)算函數(shù)計(jì)算出一個數(shù)值作為邊的權(quán)值。其中，邊權(quán)計(jì)算函數(shù)滿足非負(fù)性、單調(diào)性條件，如可取min/max/average等。

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

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

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

（3）邊由兩個可結(jié)合的半邊組成。但由于半邊必須附屬于頂點(diǎn)，邊不能獨(dú)立于頂點(diǎn)而存在于圖中，或可以認(rèn)為邊是由頂點(diǎn)導(dǎo)出的。

2模擬無尺度網(wǎng)絡(luò)生成時變半邊圖

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

2．1時變半邊圖

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

在本文，圖不是最基本要素，它是一種由半邊、頂點(diǎn)以及邊構(gòu)成的組合體。實(shí)際問題中的動態(tài)過程則需要由圖的構(gòu)造過程來模擬。

（1）加邊操作

（2）減邊操作

2．3生成時變半邊圖

（1）無尺度網(wǎng)絡(luò)

用規(guī)則圖研究分析網(wǎng)絡(luò)結(jié)構(gòu)，范圍很有限。1959年，數(shù)學(xué)家Erdobs 和Renyi提出了ER隨機(jī)網(wǎng)絡(luò)模型。在這種模型中，兩個節(jié)點(diǎn)（習(xí)慣上，網(wǎng)絡(luò)拓?fù)渲羞B接點(diǎn)稱為節(jié)點(diǎn)，圖中各邊的連接點(diǎn)稱為頂點(diǎn)。在本文中不區(qū)分節(jié)點(diǎn)和頂點(diǎn)）之間是否有邊相連不再是確定的，而是根據(jù)一個概率決定。在科學(xué)界，這種方法主導(dǎo)了半個世紀(jì)，但這種方法是靜態(tài)的，對于開放、動態(tài)變化的網(wǎng)絡(luò)環(huán)境，存在動態(tài)演化趨勢的資源及其關(guān)聯(lián)關(guān)系不能進(jìn)行分析研究。

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

本文先對Internet資源引入半邊描述，將各類資源抽象為圖中節(jié)點(diǎn)， 各種相互作用抽象為資源之間的連接線或邊，并根據(jù)Internet資源的自然特性對BA模型加以調(diào)整。考慮到資源既有增加，也有減少的可能，本文給出一種資源動態(tài)關(guān)聯(lián)圖的構(gòu)造算法：

（2）時變半邊圖構(gòu)造算法

（1）以p的概率增加一個新節(jié)點(diǎn)。

（2）從新節(jié)點(diǎn)出發(fā)，對K個節(jié)點(diǎn)進(jìn)行加邊操作；節(jié)點(diǎn)被選中的概率與該節(jié)點(diǎn)的度成正比。

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

（4）返回（1），直到生成一定數(shù)量的節(jié)點(diǎn)或達(dá)到計(jì)算要求為止。

通過資源屬性之間的結(jié)合性逐步建立邊而動態(tài)導(dǎo)出一個圖，即圖不是人為確定的，也不是客觀上預(yù)先存在的，而是由資源集合導(dǎo)出的。如圖3中時變半邊圖可由圖2 中Internet資源經(jīng)過有限步關(guān)聯(lián)生成。時變半邊圖很好地描述了Internet資源屬性之間的依賴關(guān)系。

3超分子資源自組裝

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

（1）資源的組裝準(zhǔn)則應(yīng)是各個組合模式互不相同的。

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

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



3．1超分子資源與自組裝準(zhǔn)則

（1）超分子資源

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

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

（2）自組裝準(zhǔn)則

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

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

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

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

（1）模型

輸入：①一個資源集合和資源屬性關(guān)系集（半邊結(jié)合類型）構(gòu)成的時變半邊圖；

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

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

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

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

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

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

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

(2)算法

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

（3）自組裝算法結(jié)束。

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

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

自主元素是對傳統(tǒng)計(jì)算機(jī)中各類資源概念的延伸。以資源主體化為出發(fā)點(diǎn)，將靜態(tài)、被動的資源客體變成能夠獨(dú)立提供服務(wù)的、活躍的行為主體； 使資源主體具備自主決策、適應(yīng)變化和可成長演化的能力。

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

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

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

5結(jié)束語

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

本文目的在于使Internet可以按照應(yīng)用的需求來分配共享資源，能夠自動地對自身進(jìn)行管理，讓Internet資源的使用更加簡便，并維持其可靠性，為虛擬計(jì)算環(huán)境下按需聚合和自主協(xié)同的實(shí)現(xiàn)打下堅(jiān)實(shí)的基礎(chǔ)。

參考文獻(xiàn)：

［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]孟朝暉.半邊圖與擠出吸入算法及制造單元設(shè)計(jì)[J].計(jì)算機(jī)工程與應(yīng)用，2005，41(24):228－232.

[3]孟朝暉.半邊圖模型之多層次認(rèn)知系統(tǒng)[J].計(jì)算機(jī)工程與應(yīng)用，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].北京:國防工業(yè)出版社，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.

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