基于有色Petri網(wǎng)的SPIN協(xié)議驗(yàn)證.pdf

1、無線傳感器網(wǎng)絡(luò)作為一種新興的技術(shù)，已成為當(dāng)前國際上備受關(guān)注的研究熱點(diǎn)，被認(rèn)為是對(duì)21世紀(jì)產(chǎn)生巨大影響力的技術(shù)之一。路由協(xié)議的研究是無線傳感器網(wǎng)絡(luò)的一個(gè)重要研究領(lǐng)域，其中對(duì)現(xiàn)有協(xié)議進(jìn)行分析和驗(yàn)證，確定各種現(xiàn)有協(xié)議對(duì)無線傳感器網(wǎng)絡(luò)的可用性是很重要的一個(gè)方向。SPIN是無線傳感器網(wǎng)絡(luò)中第一個(gè)基于數(shù)據(jù)的路由協(xié)議，它采用協(xié)商機(jī)制和資源自適應(yīng)機(jī)制解決了傳統(tǒng)協(xié)議所存在的問題，大大節(jié)省了能量，延長了網(wǎng)絡(luò)壽命。SPIN包括兩個(gè)協(xié)議：SPIN-1和SPIN

2、-2。 目前對(duì)SPIN協(xié)議的研究主要是通過NS平臺(tái)進(jìn)行仿真，進(jìn)而分析協(xié)議的性能。本文從另一角度出發(fā)采用形式化的方法對(duì)協(xié)議進(jìn)行驗(yàn)證。文章首先使用形式化建模工具有色Petri網(wǎng)分別對(duì)SPIN-1協(xié)議和SPIN-2協(xié)議進(jìn)行了形式化分析，并給出了它們的有色Petri網(wǎng)模型，然后利用自動(dòng)化分析工具CPN Tools分別對(duì)這兩個(gè)模型進(jìn)行模擬運(yùn)行，得到模型的可達(dá)圖和相關(guān)分析報(bào)告，依此對(duì)協(xié)議的特性進(jìn)行分析，證明協(xié)議具有活性、可達(dá)性、有界性等特性

3、。 SPIN是針對(duì)理想無損網(wǎng)絡(luò)設(shè)計(jì)的，沒有考慮到現(xiàn)實(shí)網(wǎng)絡(luò)中數(shù)據(jù)包丟失的現(xiàn)象。針對(duì)這個(gè)問題，本文提出了SPIN-E協(xié)議，它在SPIN的基礎(chǔ)上增加了重傳機(jī)制，使其能夠適用于有損網(wǎng)絡(luò)。然后文章使用有色Petri網(wǎng)對(duì)SPIN-E協(xié)議進(jìn)行建模，通過CPN Tools對(duì)模型進(jìn)行分析，證明了協(xié)議不存在死鎖，具有可達(dá)性和有界性。驗(yàn)證了使用SPIN-E協(xié)議在網(wǎng)絡(luò)傳輸有損的情況下，節(jié)點(diǎn)仍能得到它所期望的數(shù)據(jù)。 本文對(duì)無線傳感器網(wǎng)絡(luò)的路由協(xié)議