無(wú)線傳感器網(wǎng)絡(luò)形式化模型研究

無(wú)線傳感器網(wǎng)絡(luò)形式化模型研究

無(wú)線傳感器網(wǎng)絡(luò)（wsd）是由各種傳感器節(jié)點(diǎn)通過(guò)自組織生成的網(wǎng)絡(luò)。它能夠獨(dú)立地檢測(cè)、檢測(cè)和跟蹤環(huán)境，并完成大多數(shù)任務(wù)，如監(jiān)測(cè)、目標(biāo)發(fā)現(xiàn)、檢測(cè)和跟蹤。由于WSN具有隨機(jī)布設(shè)、自組織和隱蔽性強(qiáng)等特點(diǎn),使它在軍事、工業(yè)和商業(yè)等領(lǐng)域有著廣闊的應(yīng)用前景和很高的應(yīng)用價(jià)值,已經(jīng)引起了許多國(guó)家的軍事部門、安全部門、工業(yè)界和學(xué)術(shù)界的高度重視。多Agent系統(tǒng)(Multi-agentsystems,MAS)是分布式人工智能研究的一個(gè)重要分支,已成為計(jì)算機(jī)及自動(dòng)化領(lǐng)域的一項(xiàng)關(guān)鍵性主流技術(shù)和一種重要的計(jì)算范型。MAS是由多個(gè)Agent組成的Agent社會(huì),具有自治性、并發(fā)性、分布性、協(xié)調(diào)性和自適應(yīng)性,并具有自組織能力、學(xué)習(xí)能力和推理能力。鑒于MAS特性與WSN十分相似,可以利用MAS理論構(gòu)建無(wú)線傳感器網(wǎng)絡(luò),提高WSN的智能性。WSN是一個(gè)自適應(yīng)的柔性動(dòng)態(tài)系統(tǒng),它具有規(guī)模大、拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化等特點(diǎn),必須提供足夠的柔性來(lái)滿足環(huán)境及目標(biāo)的不確定性和動(dòng)態(tài)性需求,這給系統(tǒng)的設(shè)計(jì)與開(kāi)發(fā)帶來(lái)了相當(dāng)大的難度,很難保證系統(tǒng)的可靠性、可重用性和可擴(kuò)展性。因此需要利用形式化方法從高抽象層次上構(gòu)建系統(tǒng)精確、無(wú)歧義的模型,輔助WSN的設(shè)計(jì)與開(kāi)發(fā)。目前國(guó)內(nèi)外對(duì)WSN的形式化建模研究較少。文獻(xiàn)提出了一種形式化方法——傳感器網(wǎng)絡(luò)演算用于構(gòu)建WSN的精確模型。但該方法不能反映WSN的物理結(jié)構(gòu)信息,不便于WSN結(jié)構(gòu)設(shè)計(jì)和處理,并且不能很好地反映WSN的真并發(fā)行為。文獻(xiàn)利用多Agent邏輯形式化語(yǔ)言,構(gòu)建了一種特定的基于BDI的多Agent系統(tǒng)模型。然而該模型不能較好地體現(xiàn)WSN的物理結(jié)構(gòu),而且用包含許多數(shù)學(xué)符號(hào)的復(fù)雜邏輯來(lái)描述WSN是不切實(shí)際的,很難對(duì)模型進(jìn)行精化,將會(huì)給系統(tǒng)開(kāi)發(fā)人員帶來(lái)許多難以理解的困難。本文將在我們已建立的面向?qū)ο驪etri網(wǎng)基礎(chǔ)上,構(gòu)建一種通用的無(wú)線傳感器網(wǎng)絡(luò)形式化模型(WirelessSensorNetworksModel,WSNM)。WSNM可以對(duì)WSN進(jìn)行建模與分析,減少在系統(tǒng)開(kāi)發(fā)早期潛在的錯(cuò)誤,降低開(kāi)發(fā)成本,提高系統(tǒng)質(zhì)量。這對(duì)于無(wú)線傳感器網(wǎng)絡(luò)而言具有十分重要的理論和實(shí)際意義。1生成系統(tǒng)模型我們根據(jù)軟件組件的思想,結(jié)合面向?qū)ο蠹夹g(shù)和Petri網(wǎng)的優(yōu)點(diǎn),建立了一種新的面向?qū)ο驪etri網(wǎng)(Object-OrientedPetrinets,OPN)。OPN提高了模型的模塊性和柔性,能彌補(bǔ)一般Petri網(wǎng)建模的復(fù)雜性等缺點(diǎn),可簡(jiǎn)潔地表示復(fù)雜系統(tǒng)中的各種資源。根據(jù)面向?qū)ο蠓椒?系統(tǒng)由對(duì)象組成,每一個(gè)對(duì)象都具有相應(yīng)的屬性及行為。定義1一個(gè)對(duì)象的OPN模型是一個(gè)九元組,OPN=(Σ,P,T,IT,OT,F,E,G,C)。其中,Σ為數(shù)據(jù)類型、變量、函數(shù)的有限集合,即顏色集(ColorSets);P={p1,p2,…,pj}為庫(kù)所的有限集合;T={t1,t2,…,tk}為變遷的有限集合;IT={it1,it2,…,itl}為輸入接口變遷集合;OT={ot1,ot2,...,otm}為輸出接口變遷集合;F?(P×T)∪(T×P)∪(P×IT)∪(IT×P)∪(P×OT)∪(OT×P)為庫(kù)所和變遷之間的輸入輸出弧的有限集合;E:F→(ID,CDS)為定義在弧上的表達(dá)式函數(shù)(ArcExpression),ID為對(duì)象的編號(hào),CDS?Σ表示復(fù)雜的數(shù)據(jù)類型;G為定義在接口變遷上的衛(wèi)函數(shù)(GuardFunction),為布爾表達(dá)式;C(P)?Σ為與庫(kù)所P相關(guān)聯(lián)的顏色集。系統(tǒng)模型由對(duì)象和它們之間的關(guān)聯(lián)關(guān)系組成,定義如下:定義2系統(tǒng)S是一個(gè)三元組,S=(OPN,Channel,C)。其中OPN={OPN1,OPN2,…,OPNi}為系統(tǒng)對(duì)象的集合;Channel={ch1,ch2,…,chn}是通信庫(kù)所的集合,表示OPNi之間的消息傳遞通道;C(Channel)?Σ為與通信庫(kù)所相關(guān)聯(lián)的顏色集。采用OPN對(duì)復(fù)雜系統(tǒng)進(jìn)行建模,可以通過(guò)抽象和求精建立系統(tǒng)的層次模型。OPN可以單獨(dú)描述系統(tǒng)中每一個(gè)對(duì)象,這樣當(dāng)環(huán)境或某個(gè)對(duì)象的屬性或行為發(fā)生變化時(shí),只需更改某個(gè)或某幾個(gè)對(duì)象,而不需修改整個(gè)系統(tǒng)的模型,降低了建模的復(fù)雜度,提高了模型的適應(yīng)性。OPN是以面向?qū)ο鬄榛A(chǔ)進(jìn)行定義的,它能較好地體現(xiàn)面向?qū)ο蟮姆庋b、繼承、多態(tài)等特性,同時(shí)可以利用分支互相似的概念判斷兩個(gè)OPN模型的等價(jià)性,可參見(jiàn)文獻(xiàn)。2分簇頭agent我們從多Agent系統(tǒng)的角度理解無(wú)線傳感器網(wǎng)絡(luò),把每一個(gè)節(jié)點(diǎn)看作一個(gè)Agent。由于WSN節(jié)點(diǎn)數(shù)量較多,我們采用聚類分層網(wǎng)絡(luò)結(jié)構(gòu),網(wǎng)絡(luò)可劃分為多個(gè)簇(Cluster)。每個(gè)簇由一個(gè)簇頭Agent和多個(gè)簇成員Agent組成,簇頭Agent可以構(gòu)成高一級(jí)的網(wǎng)絡(luò)。在分層結(jié)構(gòu)中,簇頭管理簇內(nèi)節(jié)點(diǎn),并負(fù)責(zé)簇間數(shù)據(jù)的轉(zhuǎn)發(fā),而簇成員只負(fù)責(zé)數(shù)據(jù)的采集和初步處理。簇頭使用分簇算法自動(dòng)選舉產(chǎn)生。由于簇頭可以隨時(shí)選舉產(chǎn)生,所以分層結(jié)構(gòu)具有很強(qiáng)的抗毀性。我們以面向?qū)ο驪etri網(wǎng)為語(yǔ)義基礎(chǔ),建立一種通用的無(wú)線傳感器網(wǎng)絡(luò)形式化模型WSNM。在WSNM中,假定數(shù)據(jù)包丟失、數(shù)據(jù)流沖突等錯(cuò)誤已被底層通信協(xié)議處理過(guò),WSNM僅從高抽象層次上指導(dǎo)系統(tǒng)的設(shè)計(jì)與開(kāi)發(fā)。定義3WSNM是一個(gè)二元組,WSNM=(ASensor,ACom),其中ASensor=(ASensor1,ASensor2,…,ASensoro)表示傳感器節(jié)點(diǎn)Agent的集合,ACom表示W(wǎng)SN通信模型。2.1反應(yīng)模塊或bca模型形式上的描述,描述了一個(gè)條件-編碼傳感器節(jié)點(diǎn)Agent是一個(gè)二元組,ASensoro=(ID,NI),其中,ID是傳感器節(jié)點(diǎn)Agent的標(biāo)識(shí)符;NI定義了傳感器節(jié)點(diǎn)Agent的接口和內(nèi)部實(shí)現(xiàn)。傳感器節(jié)點(diǎn)Agent中的元NI以BDI(Belief-Desire-Intention)模型為基礎(chǔ),是一個(gè)六元組,NI=(OPNo,Pd,Pr,Pk,Pg,Pp),其中Pr,Pk,Pg,Pp為抽象庫(kù)所,用橢圓表示,分別表示反應(yīng)模塊、知識(shí)庫(kù)模塊、目標(biāo)模塊和規(guī)劃模塊。Pd為決策模塊,主要用于消息派遣和事件捕獲,把感知的信息按類型派遣到反應(yīng)模塊或BDI模型中。反應(yīng)模塊表示傳感器節(jié)點(diǎn)Agent利用知識(shí)庫(kù)存儲(chǔ)的IF-THEN規(guī)則,可以對(duì)采集數(shù)據(jù)或傳輸數(shù)據(jù)等簡(jiǎn)單行為做出快速反應(yīng)。知識(shí)庫(kù)模塊對(duì)應(yīng)于BDI模型中的信念(Bliefs),主要描述了環(huán)境、鄰居傳感器節(jié)點(diǎn)Agent的信息以及條件-動(dòng)作規(guī)則庫(kù);目標(biāo)模塊對(duì)應(yīng)于BDI模型中的愿望(Desires),主要描述了傳感器節(jié)點(diǎn)Agent所接收的任務(wù);規(guī)劃模塊對(duì)應(yīng)于BDI模型中的意圖(Intentions),主要描述了傳感器節(jié)點(diǎn)Agent完成任務(wù)所需要的行為。OPNo中的元IT和OT描述了傳感器節(jié)點(diǎn)Agent的輸入和輸出接口,傳感器節(jié)點(diǎn)Agent的實(shí)現(xiàn)部分由OPNo的其它元進(jìn)行描述。傳感器節(jié)點(diǎn)Agent的模板如圖1所示,反應(yīng)、知識(shí)庫(kù)、目標(biāo)和規(guī)劃庫(kù)所用帶陰影的橢圓表示,在具體的實(shí)現(xiàn)中,可根據(jù)文獻(xiàn)提出的Agent心智狀態(tài)模型進(jìn)行精化。傳感器節(jié)點(diǎn)Agent是一種混合型Agent,既能及時(shí)而快速地響應(yīng)外來(lái)信息和環(huán)境的變化,又能利用主流人工智能的方法生成規(guī)劃和決策。在WSN中,傳感器節(jié)點(diǎn)Agent包括簇成員Agent和簇頭Agent,要根據(jù)具體需求,選擇不同的模塊完成相應(yīng)的功能。由于簇成員Agent僅負(fù)責(zé)數(shù)據(jù)采集、簡(jiǎn)單處理和通信,因此其模型可以采用圖1中的反應(yīng)模塊部分;簇頭Agent要執(zhí)行數(shù)據(jù)融合等復(fù)雜任務(wù),因此可以采用混合Agent結(jié)構(gòu),提高執(zhí)行的實(shí)時(shí)性和自治性。當(dāng)簇頭Agent因能量等原因降為簇成員Agent時(shí),其模型也應(yīng)采用反應(yīng)模塊部分。在WSNM中,傳感器節(jié)點(diǎn)Agent主要從微觀層次上描述了節(jié)點(diǎn)Agent的結(jié)構(gòu)、方法和接口信息。2.2petri網(wǎng)對(duì)wsn研究的意義ACom表示W(wǎng)SN的通信拓?fù)?主要描述了由傳感器節(jié)點(diǎn)Agent構(gòu)成的MAS拓?fù)?。ACom是一個(gè)四元組,ACom=(AMem,AHed,Channel,Role),其中AMem=(AMem11,AMem12,…,AMemij)表示簇成員Agent的集合,AHed=(AHed1,AHed2,…,AHedi)表示簇頭Agent的集合;Channel為OPN中的元,用雙圓表示,表示Agent間的通信信道;Role是系統(tǒng)中的角色,表示所有節(jié)點(diǎn)Agent集合,Role={CID1,…,CIDi}。在ACom中,角色有靜態(tài)和動(dòng)態(tài)兩種類型。靜態(tài)角色在WSN建立時(shí)就已確定,但隨著WSN的演化,系統(tǒng)中的傳感器節(jié)點(diǎn)Agent可能會(huì)隨著環(huán)境變化動(dòng)態(tài)地增加或刪除,角色因而也就發(fā)生動(dòng)態(tài)的變化。WSN通信模型主要從宏觀層次上描述系統(tǒng),側(cè)重于系統(tǒng)的整體行為和Agent之間的交互,也描述了系統(tǒng)模型的靜態(tài)語(yǔ)義。通信模型的動(dòng)態(tài)語(yǔ)義可以通過(guò)變遷的使能和發(fā)射規(guī)則來(lái)描述,變遷的發(fā)射,使Token從一個(gè)庫(kù)所分配到另外一個(gè)庫(kù)所,表明了信息的傳遞,形象地刻畫了傳感器節(jié)點(diǎn)Agent之間的路由協(xié)議。借助于OPN對(duì)WSN的描述能力,我們能夠描述簇成員Agent和簇頭Agent不斷更改的配置,從而能清晰地理解系統(tǒng)的演化過(guò)程。WSN通信模型主要從宏觀層次上描述系統(tǒng),側(cè)重于系統(tǒng)的整體行為和Agent之間的交互,也描述了系統(tǒng)模型的靜態(tài)語(yǔ)義。通信模型的動(dòng)態(tài)語(yǔ)義可以通過(guò)變遷的使能和發(fā)射規(guī)則來(lái)描述,變遷的發(fā)射,使Token從一個(gè)庫(kù)所分配到另外一個(gè)庫(kù)所,表明了信息的傳遞,形象地刻畫了傳感器節(jié)點(diǎn)Agent之間的路由協(xié)議。在WSN的最終實(shí)現(xiàn)中,可以開(kāi)發(fā)WSN分析與管理平臺(tái),顯示系統(tǒng)中的各個(gè)節(jié)點(diǎn)Agent及其功能和狀態(tài)等,并對(duì)采集的數(shù)據(jù)進(jìn)行可視化和分析,同時(shí)監(jiān)控系統(tǒng)的拓?fù)浣Y(jié)構(gòu)。利用形式化方法建模的一個(gè)重要目的就是可以利用數(shù)學(xué)分析方法對(duì)模型進(jìn)行分析和驗(yàn)證,確保系統(tǒng)的安全性和無(wú)死鎖性等關(guān)鍵屬性的正確,使開(kāi)發(fā)人員能根據(jù)系統(tǒng)需求開(kāi)發(fā)出穩(wěn)定、可靠的產(chǎn)品。我們可以利用Petri網(wǎng)的相關(guān)分析方法和工具對(duì)WSNM的死鎖、有界性和可達(dá)性等進(jìn)行分析;對(duì)WSNM的一些關(guān)鍵特性,如并發(fā)性等,可以利用模型檢測(cè)方法進(jìn)行驗(yàn)證。限于篇幅,對(duì)于WSNM的分析和驗(yàn)證,我們將在后續(xù)的文章中詳細(xì)討論。3系統(tǒng)模型的建立在本節(jié)中,我們將無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用于目標(biāo)跟蹤系統(tǒng)的研究中,利用WSNM對(duì)系統(tǒng)進(jìn)行建模與分析,并設(shè)計(jì)開(kāi)發(fā)相應(yīng)的原型系統(tǒng)?，F(xiàn)假設(shè)以下應(yīng)用場(chǎng)景:在一個(gè)WSN監(jiān)測(cè)的區(qū)域中,傳感器節(jié)點(diǎn)對(duì)聲音信號(hào)進(jìn)行周期性的采集。當(dāng)目標(biāo)進(jìn)入該區(qū)域時(shí),某個(gè)傳感器節(jié)點(diǎn)發(fā)現(xiàn)聲音強(qiáng)度超過(guò)某個(gè)閾值,則通知其它節(jié)點(diǎn)處理突發(fā)事件,啟動(dòng)目標(biāo)跟蹤任務(wù)。各個(gè)傳感器節(jié)點(diǎn)利用基于聲音傳感器陣列的聲源定位技術(shù)對(duì)目標(biāo)進(jìn)行定位,并把相關(guān)信息發(fā)送到簇頭節(jié)點(diǎn),簇頭節(jié)點(diǎn)對(duì)數(shù)據(jù)進(jìn)行初步的融合處理后將數(shù)據(jù)發(fā)送到網(wǎng)關(guān),網(wǎng)關(guān)將最終的數(shù)據(jù)發(fā)送給指揮中心。指揮中心根據(jù)網(wǎng)絡(luò)采集的信息,將目標(biāo)的位置實(shí)時(shí)顯示出來(lái),對(duì)相應(yīng)的數(shù)據(jù)進(jìn)行處理、分析、統(tǒng)計(jì)、顯示、存儲(chǔ),并可以根據(jù)用戶的需要對(duì)網(wǎng)絡(luò)進(jìn)行查詢、監(jiān)控等。根據(jù)以上場(chǎng)景,我們?cè)O(shè)計(jì)了一個(gè)初步的原型系統(tǒng),該原型系統(tǒng)包括8個(gè)傳感器節(jié)點(diǎn)、1個(gè)網(wǎng)關(guān)和指揮中心,其中8個(gè)節(jié)點(diǎn)被分為兩個(gè)簇。傳感器節(jié)點(diǎn)采用MICAz無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn),利用MDA320數(shù)據(jù)采集板并配置相應(yīng)的聲音傳感器采集聲音信號(hào),利用MIB520CB及MICAz節(jié)點(diǎn)構(gòu)成網(wǎng)關(guān),指揮中心采用普通計(jì)算機(jī)。根據(jù)WSNM,我們建立了該原型系統(tǒng)的形式化模型,如圖3所示。限于篇幅,圖3只顯示了一個(gè)簇的模型,簇頭及簇成員Agent模型都采用反應(yīng)式Agent結(jié)構(gòu),并根據(jù)系統(tǒng)需求進(jìn)行了精化。由于簇成員Agent模型都相同,為了模型的簡(jiǎn)潔,簇成員Agent2與3用抽象模型表示。實(shí)驗(yàn)中,我們用簇頭節(jié)點(diǎn)定期檢測(cè)聲強(qiáng),如果出現(xiàn)異常,則喚醒其它節(jié)點(diǎn),節(jié)點(diǎn)間相互協(xié)作計(jì)算目標(biāo)的位置,將結(jié)果通過(guò)網(wǎng)關(guān)發(fā)送給指揮中心將目標(biāo)的位置實(shí)時(shí)顯示出來(lái),并與預(yù)定的軌跡進(jìn)行比較。建立了目標(biāo)跟蹤原型系統(tǒng)的形式化模型后,要對(duì)模型進(jìn)行分析,確保模型的正確性。首先對(duì)模型進(jìn)行相應(yīng)的簡(jiǎn)化,把模型中的抽象庫(kù)所和變遷作為CPN中的一般庫(kù)所,這樣的約簡(jiǎn)并不影響系統(tǒng)的性質(zhì)分析,然后利用Petri網(wǎng)分析工具INA分析系統(tǒng)的有界性、可達(dá)性和活性等特性。INA的分析結(jié)果如下:根據(jù)INA分析的結(jié)果,在圖3所示的系統(tǒng)模型中,模型是有界的,可達(dá)狀態(tài)有62個(gè),且模型是活的,不存在死鎖,可以保證系統(tǒng)的正常運(yùn)行。與其它建模方法相比,利用WSNM簡(jiǎn)單、直觀易懂,具有較好的工程應(yīng)用前景。目標(biāo)跟蹤原型系統(tǒng)的形式化模型是系統(tǒng)高層抽象和集成的藍(lán)本,在系統(tǒng)開(kāi)發(fā)之初產(chǎn)生,定義良好的形式化模型可以減少和避免系統(tǒng)錯(cuò)誤的產(chǎn)生以及后期糾錯(cuò)帶來(lái)的高昂代價(jià)。根據(jù)我們建立的多Agent系統(tǒng)開(kāi)發(fā)工具箱MASDT,將模型中的知識(shí)庫(kù)表示為一系列的IF-THEN規(guī)則,將輸入和輸出接口映射為相應(yīng)的接口,負(fù)責(zé)Agent之間的通信。最后,根據(jù)多Agent系統(tǒng)的開(kāi)發(fā)過(guò)程,我們開(kāi)發(fā)了簇成員、簇頭及指揮中心應(yīng)用程序。其中傳感器節(jié)點(diǎn)嵌入式操作系統(tǒng)采用TinyOS,利用nesC語(yǔ)言開(kāi)發(fā)相關(guān)應(yīng)用程序,指揮中心在Windows環(huán)境下開(kāi)發(fā)具體的應(yīng)用。圖4為目標(biāo)跟蹤效果圖,其中實(shí)線為設(shè)定的目標(biāo)軌跡,虛線為根據(jù)聲源定位算法計(jì)算出的目標(biāo)軌跡。4wsnm模型構(gòu)建本文在無(wú)線傳感器網(wǎng)絡(luò)中引入多Agent系統(tǒng)理論,提高了網(wǎng)