算術計算Petri網模型及實現

摘 要：為便捷證明算術計算Petri網模型的計算能力，分析其具體計算過程.結合面向對象編程語言Java開發插件Arithmetic Petri Net Simulation（APNS），對網中的庫所、變遷、弧元素進行實例化，重寫Fire方法生成自定義格式的模型運行日志;利用輕量級控件Swing實現交互界面，在模擬運行時對可觸發變遷的發生進行選擇，利于模型計算過程是否唯一的分析;提出（A+B）*（C-D）與A*B-C*D兩個計算模型.實驗對冪次方運算、（A+B）*（A-B）以及A^2-B^2模型進行模擬，對插件的可交互性、模型的可行性、冪次方模型運算過程的唯一性以及（A+B）*（A-B）與A^2-B^2模型的等價進行了分析與證明.

關鍵詞：算術計算Petri網;面向對象;Java;Swing;日志

中圖分類號：TP391.9 ?文獻標識碼：A ?文章編號：1673-260X（2020）08-0021-04

0 引言

算術運算Petri網是帶抑制弧的増廣Petri網的一類模型舉例，通過對帶抑制弧的Petri網模型的理解輔助解決實際建模中的問題[1，2].文獻[3]提出了一個增廣Petri網模型實現乘法運算和除法運算;文獻[4]提出了一個增廣Petri網模型模擬乘方和開方運算的方法;以上運算模型均從理論方面證明了模型的可行性.在計算機高速發展的今天，通過編程可以輔助科研人員進行許多數據的處理與可視化、算法的證明等繁雜工作.文獻[5]利用Cpntools及分析代碼對SAMG問題的驗證進行輔助及補充，彌補人類專業知識對SAMG工作流程驗證的不足;文獻[6]使用PIPE對具有多個控制器攻擊的SDN問題進行建模，以分析攻擊者的不確定性;文獻[7]使用Tina對具有時間因素的無線傳感器網絡丟包問題進行建模，并分析模型的有界性、可逆性等，以證明協議的正確性;以上工具均為科研工作提供了很多便捷之處以及助力，但驗證的模型結構是靜態的.綜上所述，由于計算模型大多僅有理論證明，且如冪次方計算模型的動態性，一般仿真軟件不可對其證明.文章在此開發出一個對算術計算Petri網模型的正確性、可行性進行編程化驗證分析的插件.

1 算數計算的增廣Petri網模型

本節首先展示冪次方運算的Petri網模型[4]，隨后基于對網模型的理解提出計算模型（A+B）*（C-D）與A*B-C*D.出于篇幅限制，本文密切相關的Petri網知識見文獻[2].

1.1 冪次方運算Petri網模型

正此小節給出了計算xm的増廣Petri網模型如圖1所示，主要思路是xm=x*x*x*…*x，將多個乘法運算模型通過變遷t4n+i和庫所P5n+1+i（i=1，2，3…m-1）進行關聯，其中t4n+i相關聯的抑制弧保證了完成當前乘法運算模型的運行后在繼續下一個乘法模型的計算;通過P6n+2輸入冪次方運算的底數x，限制第一個x2的計算;并利用t5n，對每個乘法模型輸入乘數x;最后使用P6n+1中m-2個Token個數限制乘法模型的關聯個數為m-1，自此完成計算xm的増廣Petri網模型，其中P5n+1輸出計算結果.

1.2 復合算術運算Petri網模型

此小節給出了計算A*B-C*D=E與（A+B）*（C-D）=E的増廣Petri網模型如圖2所示，主要思路利用加減法模型與乘法模型[8]的復合生成新的計算模型，通過抑制弧的加入限制復合后模型的分塊執行順序.

通過乘法模型實現A*B與C*D的計算，用減法模型對乘法模型模型連接，加入抑制弧（C，t10）， （s6，t10），（s7，t10）生成A*B-C*D算術計算模型.抑制弧的加入是為了確保C*D計算在s4-s8的運算開始之前完成，避免抑制弧（s8，t10）因減數的缺失而失去應有抑制效果，導致復合模型中減法運算結果異常.

通過加法模型與減法模型實現（A+B）、（C-D）的運算，再利用乘法模型對加減法模型連接，加入抑制弧（C，t5），（D，t5）生成最終的（A+B）*（C-D）算術計算模型.抑制弧的加入是為了（C-D）的計算在t5觸發之前完成，避免因乘數的異常，導致復合模型中乘法運算結果異常.

2 APNS插件的開發以及計算模型的分析

2.1 APNS插件的開發以及計算模型的分析

在此利用Java編碼實現帶抑制弧的増廣Petri網的運行邏輯，Eclipse插件WindowBuilder實現可交互圖形界面.利用面向對象的思想，創建Arc.java，InhibitorArc.java，Petrinet.java，Petrinet-Obj.java，Place.java，Transition.java共六個類，對庫所、變遷、流弧、抑制弧和網結構進行實例化，且對變遷是否可觸發及觸發規則進行了代碼化（類圖如圖3所示）;并在主界面定義多個觸發事件，利用java.io.File包實現變遷觸發日志的導出;創建Operation.java將算術運算Petri網的模型代碼抽象化;創建Gui_Main.java和PetrinetGUI.java利用WindowBuilder Editor實現插件主控、交互以及文件導出界面如圖4所示.

交互界面可以觀察可觸發變遷，通過點擊進行觸發，并在主界面生成對應觸發記錄;同樣可以點擊autoRun按鈕，對Petri網中的變遷進行遍歷，對當前可觸發變遷利用ArrayList進行緩存，然后隨機觸發，直到當前無變遷可觸發即停止運行.對應代碼如Code-1：

從插件大小、模型設定、交互運行、日志導出共4個方面，用此插件與PIPE、CPNTools、Tina3個Petri網仿真軟件進行對比，結果如表1所示.插件APNS在實現算術Petri網模型仿真方面，具有體積小、可交互以及自定義日志導出的優勢.由于冪次方計算模型的動態性，將在2.2節詳細介紹其模型構建方式.

2.2 冪次方運算的實現

此小節介紹了將xm對應算術運算Petri網模型輸入至插件的過程.在此増廣Petri中，當網處于初始狀態M0時，庫所P6n+2輸入x個Token用作乘法結構的乘數、庫所P6n+1輸入m-2個Token用作限制乘法結構個數為m-1.此時可計算出圖中變遷總數為5*（m-1）、庫所總數為6*（m-1）+2.

對于圖1中流弧個數可分為9個部分來求取：頂部P6n+1直接關聯的所有流弧共（m-1）條;乘法増廣Petri網結構內的所有流弧共15*（m-1）條;底部輸入弧，t5n的所有輸出弧共m條;頂部關聯抑制弧乘法結構抑制t4n+h的3條抑制弧共3*（m-2）條;連接乘法結構的流弧共2*（m-2）條;頂部輸入弧，對t4n+h輸入的流弧共（m-2）條;頂部輸出流弧共（m-3）條;初始化弧共3條;輸出流弧共1條，庫所與變遷之前的關系弧共24*m-28條.

對于模型的輸入代碼，首先初始化庫所集、變遷集以及弧集，其中重要的部分為弧集的初始化問題，部分代碼如Code-2：

3 實驗部分

本節對（A+B）*（A-B）、A^2-B^2以及xm三個計算模型進行模擬運行，通過調整輸入參數獲得不同計算結果，以及輸出日志.所有的測試均在配有I5-7300HQ 2.5Ghz四核處理器和16GB運存的機器上進行的，使用的Java SE 1.7開發環境.

首先就模型執行過程的唯一性，由于存在加、減法運算的復合，假設（A+B）*（A-B）與A^2-B^2運算過程不為一.設A=3，B=2.（A+B）*（A-B）模擬運行兩次獲得兩條長度為28的變遷觸發日志：

L1=（t2，t1，t1，t2，t1，t3，t3，t4，t5，t8，t6，t7，t5，t8，t6，t7，t5，t8，t6，t7，t5，t8，t6，t7，t5，t8，t6，t7）

L2=（t1，t3，t3，t4，t2，t5，t1，t1，t2，t8，t6，t7，t5，t8，t6，t7，t5，t8，t6，t7，t5，t8，t6，t7，t5，t8，t6，t7）

A^2-B^2模擬運行兩次獲得長度為45的變遷觸發日志：

L3=（t5，t1，t3，t7，t7，t3，t3，t2，t9，t9，t6，t8，t4，t4，t8，t5，t4，t1，t3，t7，t3，t7，t3，t2，t4，t9，t6，t8，t9，t8，t4，t4，t1，t10，t10，t3，t10，t3，t10，t3，t10，t2，t4，t4，t4）;

L4=（t1，t3，t5，t3，t7，t3，t7，t6，t8，t2，t4，t9，t9，t4，t4，t1，t3，t3，t8，t3，t5，t2，t7，t9，t4，t4，t4，t7，t6，t9，t8，t1，t8，t10，t10，t3，t10，t3，t3，t10，t2，t4，t4，t4，t10）;

其次取A=i+1，B=i（其中i=1，2，3，4，5，6），兩個計算模型均能正確計算出結果且模型結構不隨參數變化，但執行效率隨著i的增大差異愈發明顯，如圖5所示.

取底數為x（x=2，3，4），次數為i（i=3，4，5，6，7），對應計算的流程有且唯一，冪次方計算模型復雜度（變遷個數如圖6a所示），以及對應變遷觸發次數如圖6b所示所示.隨著次數i的的增加，模型中變遷個數呈線性增加;隨著次數或底數的增加，模型計算變遷觸發次數呈指數增長如圖6c所示.

4 總結

文章通過帶抑制弧Petri網的強模擬能力引出算術計算Petri網模型的構建.使用Java語言開發出插件APNS模擬帶抑制弧Petri網的運行，且可導出變遷觸發日志用以分析運行過程;通過對現有網模型的復合，提出平方差公式的計算模型;將模型嵌入APNS中，模擬計算證明模型的正確性，導出變遷觸發日志分析隨自變量i的增加A^2-B^2計算效率高于（A+B）*（A-B）;冪次方運算過程有且唯一，隨次數i的增加模型中變遷數量線性增加，變遷觸發次數呈指數增長.

已開發的插件APNS可有效模擬帶抑制弧Petri網的運行，但模型的代碼化輸入不夠常規.在未來的工作中主要是利用復合網模型的方法生成更多常用模型嵌入插件中并驗證，以及增加界面化的模型輸入.

參考文獻：

〔1〕吳哲輝.Petri網導論[M].北京：機械工業出版社，2006.

〔2〕邵叱風.基于流程挖掘的并行優化算法[J].赤峰學院學報（自然科學版），2019，35（10）：66-70.

〔3〕吳哲輝.實現乘法計算的增廣Petri網模型[J].山東礦業學院學報，1986，96（02）：12-16.

〔4〕許安國.實現自然數m次乘方和開m次方的增廣Petri網模型[J].山東礦業學院學報，2017，34（04）：81-89.

〔5〕Lee Y S， No Y G， Seong P H. Validation of severe accident management guidelines （SAMGs） for advanced power reactor 1400 （APR1400） using colored Petri net （CPN） Tools[J]. Annals of Nuclear Energy， 2019， 126： 186-193.

〔6〕Almutairi L， Hong L， Shetty S. Security analysis of multiple SDN controllers based on stochastic Petri nets[C]//2019 Spring Simulation Conference （SpringSim）. IEEE， 2019： 1-12.

〔7〕Louazani A， Sekhri L. Time Petri Nets based model for CL-MAC protocol with packet loss[J]. Journal of King Saud University-Computer and Information Sciences， 2019.