王慧英，周愷卿，周 輝

(1.重慶工程學(xué)院計(jì)算機(jī)與物聯(lián)網(wǎng)學(xué)院，重慶 400056；2. 吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南 吉首 416000；3. 湖南中醫(yī)藥大學(xué)，湖南 長沙 410208)

1 引言

隨著社會(huì)的進(jìn)步，科技的不斷創(chuàng)新，計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)也變得愈加復(fù)雜，Petri網(wǎng)的出現(xiàn)給計(jì)算機(jī)系統(tǒng)帶來了新的表現(xiàn)形式。而隨著Petri網(wǎng)的利用率越來越高，Petri網(wǎng)的可達(dá)性就越高，Petri網(wǎng)中的偽標(biāo)識也隨之增加，如何有效地去除Petri網(wǎng)中的可達(dá)性偽標(biāo)識一時(shí)之間成為人們爭相討論的熱門話題。當(dāng)傳統(tǒng)的可達(dá)性偽標(biāo)識判定方法滿足不了更新后的Petri網(wǎng)可達(dá)性偽標(biāo)識的判定，提出一種行之有效的判定方法成為必要。

鄭學(xué)恩等人提出基于面向?qū)ο驪etri-net的LWF建模方法。該方法首先基于躍遷狀態(tài)轉(zhuǎn)移機(jī)制確定Petri網(wǎng)的虛擬托肯標(biāo)識，并將Petri網(wǎng)中LWF從無限循環(huán)的活鎖狀態(tài)轉(zhuǎn)變?yōu)榭捎?jì)數(shù)的有限循環(huán)迭代狀態(tài)；再基于獲取的托肯標(biāo)識對Petri網(wǎng)進(jìn)行可達(dá)性分析；最后依據(jù)分析結(jié)果構(gòu)建Petri網(wǎng)可達(dá)性偽標(biāo)識判定模型。由于該模型未能利用獨(dú)立成分分析方法對Petri網(wǎng)中的數(shù)據(jù)特征進(jìn)行提取，導(dǎo)致該方法構(gòu)建的模型在運(yùn)行時(shí)CPU的占用率較高。王媛媛等人提出基于邏輯Petri網(wǎng)的模型修正方法。該方法首先利用一致性檢測技術(shù)計(jì)算數(shù)據(jù)的最優(yōu)校準(zhǔn)度，并通過標(biāo)識數(shù)據(jù)庫對偏差位置進(jìn)行定位；再依據(jù)邏輯校準(zhǔn)和邏輯最優(yōu)校準(zhǔn)的定義對Petri網(wǎng)中的異常數(shù)據(jù)進(jìn)行校正處理；最后基于最優(yōu)校準(zhǔn)的計(jì)算擬合度構(gòu)建Petri網(wǎng)可達(dá)性偽標(biāo)識判定模型。該方法由于未能依據(jù)獲取的獨(dú)立成分偏度對Petri網(wǎng)數(shù)據(jù)進(jìn)行排序，導(dǎo)致該方法構(gòu)建的模型在進(jìn)行偽標(biāo)識判定時(shí)的網(wǎng)絡(luò)路徑覆蓋率低。翟禹堯等人提出基于層次廣義隨機(jī)Petri網(wǎng)的測試性建模方法。該方法首先基于依據(jù)層次廣義理論對Petri網(wǎng)中的數(shù)據(jù)進(jìn)行層次化處理；再依據(jù)層次劃分的結(jié)果構(gòu)建分層GSPN模型；最后將Petri網(wǎng)中的數(shù)據(jù)放入模型中進(jìn)行求解，從而實(shí)現(xiàn)對Petri網(wǎng)可達(dá)性偽標(biāo)識的判定。該方法由于未能通過對Petri網(wǎng)數(shù)據(jù)集正交矩陣計(jì)算，獲取Petri網(wǎng)數(shù)據(jù)的獨(dú)立成分偏度，所以該方法構(gòu)建的模型在進(jìn)行偽標(biāo)識判定時(shí)的判定效果較差。

為解決上述Petri網(wǎng)可達(dá)性偽標(biāo)識判定模型構(gòu)建時(shí)存在的問題，提出基于約束優(yōu)化的Petri網(wǎng)可達(dá)性偽標(biāo)識判定模型構(gòu)建方法。

2 特征提取

利用獨(dú)立成分分析法對Petri網(wǎng)中數(shù)據(jù)進(jìn)行降噪處理，再基于UICA算法對降噪后的數(shù)據(jù)進(jìn)行特征提取。

2.1 數(shù)據(jù)降噪

2.1.1 查找異常數(shù)據(jù)

基于約束優(yōu)化原理尋找Petri網(wǎng)中的異常數(shù)據(jù)，并對其進(jìn)行靈活性表示。

(1)

式中，

Petri

網(wǎng)數(shù)據(jù)的期望系數(shù)為

γ

，

G

為

Petri

網(wǎng)數(shù)據(jù)中的約束條件。獲取的

Petri

網(wǎng)中的異常數(shù)據(jù)如下式所示

(2)

式中，

Petri

網(wǎng)數(shù)據(jù)中的異常數(shù)據(jù)指數(shù)為

σ

，，…，，獲取的

Petri

網(wǎng)異常數(shù)據(jù)為

s

，，…，。2

.

1

.

2 降噪基于上述計(jì)算結(jié)果將查找出的異常數(shù)據(jù)進(jìn)行剔除，再利用主成分分析法對

Petri

網(wǎng)中的數(shù)據(jù)進(jìn)行降噪處理。首先利用主成分分析法在

Petri

網(wǎng)中構(gòu)建一個(gè)三維坐標(biāo)系，設(shè)定坐標(biāo)中

x

處的數(shù)據(jù)向量為

Z

(

x

)，且

Z

(

x

)=[

Z

(

x

)，

Z

(

x

)，…

Z

(

x

)]=

S

(

x

)+

N

(

x

)，其中，

Petri

網(wǎng)數(shù)據(jù)的

p

維信號以及噪聲向量分別用

S

(

x

)，

N

(

x

)表示。通過

MNF

(最大噪聲分量)變換法則將

Petri

網(wǎng)中的數(shù)據(jù)進(jìn)行線性變換處理，過程如下式所示

(3)

(4)

2.2 特征提取

基于獨(dú)立成分分析方法將去噪后的Petri網(wǎng)數(shù)據(jù)進(jìn)行特征提取。

設(shè)定Z(x)為Petri網(wǎng)中的原始數(shù)據(jù)向量，經(jīng)過MNF變換后的數(shù)據(jù)向量為

Y

(

x

)。對

Y

(

x

)中的前

k

項(xiàng)進(jìn)行保留，其余的

p

-

k

項(xiàng)歸零處理，從而獲取

Y

(

x

)的前

k

項(xiàng)數(shù)據(jù)集，并對其進(jìn)行

MNF

反變換，過程如下式所示

(5)

式中，獲取

Y

(

x

)的前

k

項(xiàng)數(shù)據(jù)集為

Y

()(

x

)，

MNF

反變換后獲取的數(shù)據(jù)集為

Q

(

x

)，

a

為變換時(shí)的轉(zhuǎn)換量。基于上述計(jì)算結(jié)果，構(gòu)建該數(shù)據(jù)集的正交矩陣，過程如下式所示

(6)

式中，

A

為構(gòu)建的

Petri

網(wǎng)數(shù)據(jù)集的正交矩陣。依據(jù)三階中心距對矩陣進(jìn)行計(jì)算，獲取各個(gè)數(shù)據(jù)的獨(dú)立成分偏度，過程如下式所示det(

Q

)=det(0)°det(

A

)=0

(7)

式中，獲取的數(shù)據(jù)獨(dú)立成分偏度為det(

Q

)。依據(jù)獲取的獨(dú)立成分偏度對數(shù)據(jù)進(jìn)行排序，從而獲取Petri網(wǎng)數(shù)據(jù)的特征。

3 構(gòu)建偽標(biāo)識模型

基于LDA算法對獲取的Petri網(wǎng)數(shù)據(jù)特征進(jìn)行計(jì)算，從而獲取Petri網(wǎng)的邊界特征向量；再依據(jù)獲取的特征向量，構(gòu)建Petri網(wǎng)可達(dá)性偽標(biāo)識判定模型。

3.1 邊界特征向量

基于LDA原理可將Petri網(wǎng)中數(shù)據(jù)樣本之間的距離進(jìn)行壓縮，擴(kuò)展類別間的邊界，從而降低類別邊界的信息干擾。將LDA算法加入類別邊界公式中，以邊界最大化為目標(biāo)獲取Petri網(wǎng)的特征變換軸。利用多類問題的類內(nèi)離散度對Petri網(wǎng)中的類別區(qū)間邊界進(jìn)行計(jì)算，過程如下式所示

(8)

式中，獲取的Petri網(wǎng)中類別區(qū)間為

D

(

ω

，

ω

)，

β

，

α

為

Petri

網(wǎng)中的系數(shù)，

β

∈[0，1]，

α

∈[0，1]，且

β

+

α

=1，用來調(diào)節(jié)均值方差和方差差異對邊界的影響，

Petri

網(wǎng)中的類別樣本均值為

u

，方差為

σ

。將

Petri

網(wǎng)中原始高維數(shù)據(jù)沿著向量

p

進(jìn)行變換，過程如下式所示

α

|

p

(

i

-

k

)

p

|-

p

(

i

-

k

)

p

(9)

(10)

式中，獲取的Lagrange函數(shù)表達(dá)方式為

L

(

p

，

λ

)，

λ

為Petri網(wǎng)中的有效特征值，相對應(yīng)的有效特征向量用

p

表示，CS為Lagrange函數(shù)中的系數(shù)?；谏鲜鲇?jì)算結(jié)果對上式進(jìn)行偏導(dǎo)，偏導(dǎo)過程如下式所示

(11)

3.2 Petri網(wǎng)可達(dá)性偽標(biāo)識判定模型構(gòu)建

基于上述獲取的邊界最優(yōu)特征值，利用支持向量機(jī)構(gòu)建Petri網(wǎng)可達(dá)性偽標(biāo)識判定模型。

首先將Petri網(wǎng)中的數(shù)據(jù)進(jìn)行聚類處理，將Petri網(wǎng)中的數(shù)據(jù)分為C個(gè)類別，再隨機(jī)選取其中的類別，將該類別與其余類別進(jìn)行對應(yīng)的特征向量提取?；谔崛〉腃-1組特征向?qū)etri網(wǎng)的原始數(shù)據(jù)進(jìn)行數(shù)據(jù)變換，獲取C-1組的Petri網(wǎng)變換數(shù)據(jù)，并利用支持向量機(jī)對其進(jìn)行訓(xùn)練，獲取C-1個(gè)分類模型，過程如下式所示

(12)

式中，各個(gè)子模型的輸出為

f

(

x

)，模型輸出為

y

，組合參數(shù)為

γ

。設(shè)定組合中的參數(shù)如下式所示

(13)

將該步驟進(jìn)行迭代計(jì)算，直到提取出Petri網(wǎng)數(shù)據(jù)中所有特征向量。由此構(gòu)建Petri網(wǎng)可達(dá)性偽標(biāo)識判定模型

Y

=sgn(

y

γ

)

(14)

依據(jù)上述構(gòu)建的分類模型，完成Petri網(wǎng)中可達(dá)性偽標(biāo)識的判定。

4 實(shí)驗(yàn)驗(yàn)證

為了驗(yàn)證上述模型構(gòu)建方法的整體有效性，需要對此方法進(jìn)行測試。

4.1 實(shí)驗(yàn)環(huán)境設(shè)置

實(shí)驗(yàn)環(huán)境具體如表1所示。

表1 測試環(huán)境選擇

在上述實(shí)驗(yàn)環(huán)境下，分別采用基于約束優(yōu)化的Petri網(wǎng)可達(dá)性偽標(biāo)識判定模型構(gòu)建方法(方法1)、基于面向?qū)ο驪etri-net的LWF建模方法(方法2)、基于層次廣義隨機(jī)Petri網(wǎng)的測試性建模新方法(方法3)進(jìn)行測試。為了保證實(shí)驗(yàn)結(jié)果的準(zhǔn)確性與可靠性，在實(shí)驗(yàn)過程中需保證實(shí)驗(yàn)條件的一致性。

4.2 實(shí)驗(yàn)結(jié)果及分析

1)隨機(jī)選取Petri網(wǎng)中不同的數(shù)據(jù)，對方法1、方法2以及方法3在模型運(yùn)行時(shí)的CPU占用情況進(jìn)行檢測，檢測結(jié)果如表2所示。

表2 不同方法的CPU占用情況檢測結(jié)果

依據(jù)表2可知，方法1構(gòu)建的Petri網(wǎng)可達(dá)性偽標(biāo)識判定模型在運(yùn)行時(shí)的CPU占用率要低于方法2以及方法3，并且方法1能夠在數(shù)據(jù)較大的情況下依然能將CPU占用率穩(wěn)定在75%以內(nèi)。這主要是因?yàn)榉椒?利用了獨(dú)立成分分析方法對Petri網(wǎng)中的數(shù)據(jù)特征進(jìn)行了提取，所以該方法構(gòu)建的可達(dá)性偽標(biāo)識判定模型在運(yùn)行時(shí)的CPU占用率低。

2)在Petri網(wǎng)中添加一組雜亂數(shù)據(jù)，對方法1、方法2以及方法3的網(wǎng)絡(luò)路徑覆蓋性能進(jìn)行檢測，檢測結(jié)果如表3所示。

表3 不同方法的網(wǎng)絡(luò)路徑覆蓋性能檢測結(jié)果

分析表3可知，方法1構(gòu)建的判定模型在對Petri網(wǎng)可達(dá)性偽標(biāo)識進(jìn)行判定時(shí)網(wǎng)絡(luò)路徑覆蓋率要高于方法2以及方法3，并且在第一組與第五組路徑雜亂的情況下，依然可以將檢測出的路徑覆蓋率穩(wěn)定在90%以上。方法2雖然在第三組網(wǎng)絡(luò)路徑相對規(guī)整的情況下能夠?qū)z測出的覆蓋率穩(wěn)定在90%以上，但是該方法在路徑雜亂的情況下，路徑覆蓋率不太穩(wěn)定。方法3對比方法1和方法2來看，路徑的覆蓋率較低。

3)構(gòu)建一個(gè)虛擬化的Petri網(wǎng)，并在該P(yáng)etri網(wǎng)中隨機(jī)選取若干數(shù)據(jù)，對方法1、方法2以及方法3構(gòu)建模型的判定效果進(jìn)行測試，測試結(jié)果如表4所示。

表4 不同模型的判定性能測試結(jié)果

依據(jù)表4可知，方法1構(gòu)建的判定模型，檢測出的誤判與漏判個(gè)數(shù)均維持在5個(gè)以內(nèi)。方法2雖然也可以將誤判個(gè)數(shù)維持在5個(gè)以內(nèi)，但是該方法的漏判個(gè)數(shù)卻高達(dá)10個(gè)。而方法3構(gòu)建的判定模型在對Petri網(wǎng)可達(dá)性偽標(biāo)識進(jìn)行判定時(shí)的誤判漏判個(gè)數(shù)均在10個(gè)以上，綜上所述方法1構(gòu)建模型的判定性能要優(yōu)于方法2以及方法3。

綜合分析上述實(shí)驗(yàn)結(jié)果可知，本文方法在CPU占用率、網(wǎng)絡(luò)路徑覆蓋率以及判定效果方面均優(yōu)于現(xiàn)有方法，說明其針對Petri網(wǎng)可達(dá)性偽標(biāo)識進(jìn)行判定得出的結(jié)果具備較強(qiáng)的可靠性。

5 結(jié)束語

近幾年，隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，Petri網(wǎng)的利用率也隨之增加。Petri網(wǎng)的出現(xiàn)成功地使計(jì)算機(jī)系統(tǒng)變得簡單，但是隨著使用次數(shù)的增加，Petri網(wǎng)數(shù)據(jù)的可達(dá)性也隨之增加，此時(shí)對Petri網(wǎng)中的可達(dá)性偽標(biāo)識判定成為重中之重。針對傳統(tǒng)判定方法中存在的問題，提出基于約束優(yōu)化的Petri網(wǎng)可達(dá)性偽標(biāo)識判定模型構(gòu)建方法。該方法首先基于獨(dú)立成分分析方法將Petri網(wǎng)中的數(shù)據(jù)進(jìn)行特征提??；再利用支持向量機(jī)對獲取的數(shù)據(jù)特征進(jìn)行訓(xùn)練，構(gòu)建Petri網(wǎng)的可達(dá)性偽標(biāo)識判定模型，從而實(shí)現(xiàn)對Petri網(wǎng)中可達(dá)性偽標(biāo)識的判定。由于該方法在數(shù)據(jù)去噪時(shí)還存在一定問題，今后會(huì)針對這一缺陷繼續(xù)對該模型構(gòu)建方法進(jìn)行優(yōu)化。