[發(fā)明專(zhuān)利]一種基于多元組的物聯(lián)網(wǎng)復(fù)雜關(guān)系鏈建模及構(gòu)造方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310470683.2
• 申請(qǐng)日: 2013-10-10
• 公開(kāi)（公告）號(hào): CN103530457A
• 公開(kāi)（公告）日: 2014-01-22
• 發(fā)明（設(shè)計(jì)）人: 李玲娟;楊震;楊庚;吳蒙;沈蘇彬;李雄
• 申請(qǐng)（專(zhuān)利權(quán)）人: 南京郵電大學(xué)
• 主分類(lèi)號(hào): G06F17/50
• 分類(lèi)號(hào): G06F17/50
• 代理公司: 南京知識(shí)律師事務(wù)所 32207
• 代理人: 汪旭東

1.一種基于多元組的物聯(lián)網(wǎng)復(fù)雜關(guān)系鏈建模及構(gòu)造方法，其特征在于，所述方法包括：

(1)基于多元組的物聯(lián)網(wǎng)復(fù)雜關(guān)系鏈建模方法；

本發(fā)明使用基于多元組的建模方法對(duì)物聯(lián)網(wǎng)復(fù)雜關(guān)系鏈進(jìn)行建模，將復(fù)雜關(guān)系鏈劃分為實(shí)體域、關(guān)聯(lián)域、約束域、行為或事件域和結(jié)果域；關(guān)系鏈RC用五元組表示，RC=(E，L，C，A，R)；

其中E代表實(shí)體域，實(shí)體域中的實(shí)體是人、物、概念，實(shí)體域E=(S,F,K)；表示每個(gè)實(shí)體都有其唯一的序號(hào)S、有其所屬的領(lǐng)域F、有其所屬的類(lèi)型K，實(shí)體i在物聯(lián)網(wǎng)中的唯一序號(hào)為s_i；實(shí)體i所屬的領(lǐng)域?yàn)閒_i；實(shí)體i的類(lèi)型為k_i，實(shí)體域中的一個(gè)實(shí)體e_i由(s_i，f_i，k_i)描述；

L代表關(guān)聯(lián)域，L=(<e_i,e_j>)是一個(gè)反映有向關(guān)聯(lián)的矩陣，矩陣中的元素<e_i,e_j>代表實(shí)體e_i向e_j的關(guān)聯(lián)關(guān)系，記為L(zhǎng)e_ij；元素<e_j,e_i>代表實(shí)體e_j向e_i的關(guān)聯(lián)關(guān)系，記為L(zhǎng)e_ji；

C代表約束域，C=(P,W,T)表示約束由兩實(shí)體關(guān)聯(lián)時(shí)的參與度P、權(quán)重W和關(guān)聯(lián)的時(shí)間期間T組成，P是1:1、1:n、m:n，表示參與聯(lián)系的實(shí)體數(shù)量關(guān)系是一對(duì)一、一對(duì)多還是多對(duì)多，T由(ts,te)表示，ts是起時(shí)間，te是止時(shí)間；對(duì)應(yīng)于一個(gè)關(guān)聯(lián)關(guān)系Le_ij有0-n個(gè)約束條件；每個(gè)約束條件包含P、W、T或其中的某一個(gè)或某兩個(gè)；對(duì)應(yīng)于關(guān)聯(lián)關(guān)系Le_ij的條件記為Ce_ij，Ce_ij是一個(gè)向量，Le_ij的第m個(gè)條件記為Ce_ijm，Ce_ij=(Ce_ij1,Ce_ij2，…，Ce_ijm，…，Ce_ijn)；

A代表行為或事件域，表示兩實(shí)體關(guān)聯(lián)時(shí)對(duì)應(yīng)的行為或事件，即在行為或事件發(fā)生的前提下，兩實(shí)體產(chǎn)生關(guān)聯(lián)關(guān)系，對(duì)應(yīng)于一個(gè)關(guān)聯(lián)關(guān)系Le_ij有0-n個(gè)行為或事件，Le_ij對(duì)應(yīng)的行為或事件記為Ae_ij，Ae_ij是一個(gè)集合，Le_ij的第m個(gè)行為或事件記為Ae_ijm；Ae_ij={Ae_ij1,Ae_ij2,…,Ae_ijm,…,Ae_ijn}；

R代表結(jié)果域，表示兩實(shí)體關(guān)聯(lián)時(shí)產(chǎn)生或?qū)е碌慕Y(jié)果，對(duì)應(yīng)于一個(gè)關(guān)聯(lián)關(guān)系Le_ij有0-n個(gè)結(jié)果，Le_ij對(duì)應(yīng)的結(jié)果記為Re_ij，Re_ij是一個(gè)集合，Le_ij的第m個(gè)結(jié)果記為Re_ijm，Re_ij={Re_ij1,Re_ij2,…,Re_ijm,…,Re_ijn}；

(2)基于圖論的關(guān)系鏈的鄰接關(guān)聯(lián)矩陣表示法；

將關(guān)系鏈的關(guān)聯(lián)域轉(zhuǎn)化為鄰接關(guān)聯(lián)矩陣進(jìn)行表示，令G=<E,L>，其中E表示實(shí)體域，E={e₁，e₂，e₃，…，e_n}，L表示實(shí)體間的鄰接關(guān)系集合，關(guān)系鏈的鄰接關(guān)聯(lián)矩陣表示為L(zhǎng)(G)=(Le_ij)_n×_n，其中

Le_ij為1則意味著存在實(shí)體e_i向?qū)嶓we_j的鄰接關(guān)系，使用能夠被計(jì)算機(jī)存儲(chǔ)的鄰接關(guān)聯(lián)矩陣對(duì)關(guān)系鏈模型進(jìn)行表示，鄰接關(guān)聯(lián)矩陣反映了實(shí)體之間的1跳關(guān)聯(lián)路徑，基于此鄰接關(guān)聯(lián)矩陣計(jì)算出反映實(shí)體間多跳關(guān)聯(lián)關(guān)系存在性的可達(dá)性矩陣，進(jìn)而通過(guò)鄰接關(guān)聯(lián)矩陣的運(yùn)算推導(dǎo)出可達(dá)實(shí)體間的有向關(guān)聯(lián)路徑，最終構(gòu)建完整的復(fù)雜關(guān)系鏈；

(3)依據(jù)關(guān)系鏈鄰接關(guān)聯(lián)矩陣反向推導(dǎo)構(gòu)造關(guān)系鏈的方法；

首先基于對(duì)關(guān)系鏈的鄰接關(guān)聯(lián)矩陣的計(jì)算，判定兩個(gè)實(shí)體間的有向可達(dá)性(在有向可達(dá)的情況下，實(shí)體e_i到實(shí)體e_j可能有多條關(guān)聯(lián)路徑)；再基于關(guān)系鏈的鄰接關(guān)聯(lián)矩陣的計(jì)算，得到兩個(gè)有向可達(dá)的實(shí)體的關(guān)聯(lián)路徑數(shù)；再通過(guò)深度遍歷得到兩實(shí)體間的所有的有向關(guān)聯(lián)路徑，具體步驟和方法如下：

①可達(dá)性矩陣計(jì)算方法

P＝L∨L⁽²⁾∨L⁽³⁾∨…∨L⁽ⁿ⁾

P是可達(dá)性矩陣，通過(guò)對(duì)對(duì)鄰接關(guān)聯(lián)矩陣的布爾運(yùn)算得到，P_ij=1意味著實(shí)體e_i和實(shí)體e_j為有向可達(dá)；

②關(guān)聯(lián)路徑的推導(dǎo)方法

(a)1跳的關(guān)聯(lián)路徑的推導(dǎo)

對(duì)關(guān)系鏈鄰接關(guān)聯(lián)矩陣L的Le_ij進(jìn)行判定，若Le_ij=1，表明實(shí)體e_i和實(shí)體e_j是鄰接關(guān)系，即存在1跳的關(guān)聯(lián)路徑；

(b)2至n跳的關(guān)聯(lián)路徑的推導(dǎo)與構(gòu)造

計(jì)算出實(shí)體e_i和實(shí)體e_j之間的各跳關(guān)聯(lián)路徑的數(shù)目：基于鄰接關(guān)聯(lián)矩陣L，依次計(jì)算L^k，k=2，…，n，L^k=(l_ij)_n×n，l_ij表示第i行第j列的元素，若矩陣L^k的元素l_ij上的值為m_k，則實(shí)體e_i到實(shí)體e_j的長(zhǎng)度為k的關(guān)聯(lián)路徑數(shù)目為m_k，若i=j，表示從實(shí)體e_i出發(fā)的長(zhǎng)度為k的回環(huán)鏈路數(shù)目為m_k；

推導(dǎo)構(gòu)造實(shí)體e_i到實(shí)體e_j之間關(guān)聯(lián)路徑：分別基于L^k，k=2，…，n的計(jì)算結(jié)果，從實(shí)體e_i出發(fā)，利用深度優(yōu)先算法進(jìn)行遍歷，每一條關(guān)聯(lián)路徑的遍歷都以到達(dá)實(shí)體e_j為結(jié)束，若某次遍歷無(wú)法到達(dá)實(shí)體e_j，則重新從e_i點(diǎn)出發(fā)，開(kāi)始下一條關(guān)聯(lián)路徑的遍歷；k跳關(guān)聯(lián)路徑遍歷的結(jié)束條件是：遍歷得到的關(guān)聯(lián)路徑數(shù)目等于m_k；

基于遍歷得到的關(guān)聯(lián)路徑構(gòu)造復(fù)雜關(guān)系鏈。