譚朋柳,冒蘇敏,周 樂

(南昌航空大學(xué) 軟件學(xué)院,南昌 330063)

0 概述

信息物理融合系統(tǒng)(Cyber-Physical System,CPS)[1-4]是一個前沿性研究領(lǐng)域,是信息系統(tǒng)和物理系統(tǒng)所有過程和功能的集合。CPS注重信息系統(tǒng)與物理系統(tǒng)的有機融合,將已有的各獨立設(shè)備進行智能化連接,實現(xiàn)自適應(yīng)的組網(wǎng)與交互,從而使系統(tǒng)之間實現(xiàn)相互感知與協(xié)同運作。同時,信息系統(tǒng)會收到物理系統(tǒng)的反饋,并根據(jù)反饋結(jié)果做出相應(yīng)調(diào)整[5]。CPS技術(shù)在航空航天、電力、交通、醫(yī)療、環(huán)境監(jiān)測、能源、農(nóng)業(yè)等人類社會發(fā)展的各個領(lǐng)域都有著廣泛的應(yīng)用前景。CPS被普遍認為是計算機信息處理技術(shù)史上的下一次革命,Internet改變了人與人之間的交互方式,而CPS將會改變?nèi)伺c現(xiàn)實物理世界之間的交互方式[6]。

事件驅(qū)動的無線 CPS通常是由無線傳感網(wǎng)絡(luò)(Wireless Sensor Network,WSN)、數(shù)據(jù)與控制中心以及無線執(zhí)行器網(wǎng)絡(luò)(Wireless Actuator Network,WAN)等部分構(gòu)成的大規(guī)模多跳無線自組織網(wǎng)絡(luò)系統(tǒng)。其中,傳感節(jié)點周期性地采集被控對象的信息,當感知異常時向中心實時返回異常事件消息,經(jīng)控制中心處理后產(chǎn)生控制事件消息,并實時地傳給 WAN相應(yīng)的執(zhí)行節(jié)點,執(zhí)行具體控制任務(wù),以便改變物理對象。如在一個醫(yī)療CPS系統(tǒng)中,醫(yī)療CPS是以保障生命安全為重要前提的網(wǎng)絡(luò)化、智能化的醫(yī)療設(shè)備系統(tǒng),通過各醫(yī)療單元之間的實時網(wǎng)絡(luò)化通信和決策與控制,輔助醫(yī)務(wù)人員實施操作,實現(xiàn)了醫(yī)療資源的高效合理利用[7]。

事件驅(qū)動的無線CPS是一種多跳無線自組織網(wǎng)絡(luò)實時系統(tǒng),實時性要求較高。為此,本文提出一種實時消息并行調(diào)度算法(RMPS),該算法主要研究并行消息的判定、消息傳輸?shù)穆窂竭x擇和消息的并行傳輸。

1 相關(guān)工作

近年來,國內(nèi)外學(xué)者提出了許多無線傳感器網(wǎng)絡(luò)實時消息的調(diào)度方法,歸納起來主要分為基于競爭的方法、基于TDMA的方法、混合方法、基于優(yōu)先級等。

1)在基于競爭的方法中,文獻[8]在經(jīng)典的HEED[9]協(xié)議基礎(chǔ)上提出一種基于預(yù)約調(diào)度的無線傳感器網(wǎng)絡(luò)MAC協(xié)議(SSMAC)。該協(xié)議采用分布式競爭接入和預(yù)約發(fā)送,提高信道接入效率,支持服務(wù)質(zhì)量(QoS)業(yè)務(wù)的傳輸,較好地解決了隱藏終端和暴露終端的問題。文獻[10]提出一種按需匯聚的MAC協(xié)議,采用請求融合機制,將時隙分配給有數(shù)據(jù)需要傳輸?shù)墓?jié)點,大大節(jié)約了能量,降低了網(wǎng)絡(luò)延時,但沒有考慮事件優(yōu)先級。文獻[11]提出了L-CSMA協(xié)議。該協(xié)議為節(jié)點分配不同的優(yōu)先級別,根據(jù)他們的位置在接近目的地時擁有更高的優(yōu)先級調(diào)度權(quán)限。管理的首要任務(wù)是分配節(jié)點載波感知階段的持續(xù)時間。文獻[12]采用多個虛擬信道來避免擁塞問題,同時建立相應(yīng)的鏈路調(diào)度表,減少信道間的碰撞問題,增加了網(wǎng)絡(luò)吞吐量,但只針對低復(fù)雜網(wǎng)絡(luò)。

2)在基于TDMA的方法中,文獻[13]提出一種分布式數(shù)據(jù)融合調(diào)度算法,這種方式使用了一個多片結(jié)構(gòu)調(diào)度節(jié)點到基站的數(shù)據(jù)傳輸,減少了數(shù)據(jù)的復(fù)雜程度和算法調(diào)度的運行時間。該算法不能隨著網(wǎng)絡(luò)的改變而自適應(yīng)變化。文獻[14]提出的算法在構(gòu)建路由和傳輸調(diào)度階段都進行優(yōu)化,但它并不能有效降低消息傳輸端到端的延時。文獻[15]提出了一種能量感知的消息調(diào)度方法(CC-TDMA)。雖然該算法降低了高優(yōu)先級事件的傳輸延時,但它不是分布式的且不適合大型網(wǎng)絡(luò)。文獻[16]提出一種新的基于權(quán)重因子的消息調(diào)度算法,將信道質(zhì)量、傳輸速度和事件優(yōu)先級作為影響因子,提高了信道傳輸?shù)墓叫?但它不能保證消息的硬實時性。文獻[17]針對實時性較高的無線網(wǎng)絡(luò),提出一種保障無線傳感器網(wǎng)絡(luò)消息實時性的調(diào)度方法(L-RQS)。該方法將消息進行優(yōu)先級劃分,同時根據(jù)路由節(jié)點轉(zhuǎn)發(fā)的高優(yōu)先級消息個數(shù)或等待時間設(shè)置節(jié)點的狀態(tài)。該方法提高了網(wǎng)絡(luò)吞吐量,但沒有考慮消息傳輸?shù)牟⑿行浴?/p>

3)在混合及優(yōu)先級方法中,文獻[18]將節(jié)點感知到的事件消息分為實時和非實時2種情況,實時消息進入優(yōu)先發(fā)送隊列,搶占現(xiàn)有時隙進行發(fā)送。這種方法可以提高實時消息的傳輸效率,但沒有很好地解決消息間的干擾問題。文獻[19]基于業(yè)務(wù)優(yōu)先級對用戶進行排隊,可以有效地解決群組用戶同時切換所可能造成的網(wǎng)絡(luò)擁擠。文獻[20]提出的算法將傳感器節(jié)點劃分為多個區(qū)域,每個區(qū)域內(nèi)采用CDMA和TDMA混合調(diào)度,在數(shù)據(jù)傳輸之前不需要建立路由協(xié)議,減少了節(jié)點能量消耗和鏈路通信干擾,但該協(xié)議沒有考慮事件的截止期限。

很多實時消息調(diào)度協(xié)議并不能滿足事件驅(qū)動型無線CPS實時性的要求,也沒有考慮消息傳輸中端到端的延遲和數(shù)據(jù)收集過程中能量的消耗等問題,而本文提出的RMPS算法通過建立實時消息并行優(yōu)化模型,在此基礎(chǔ)上采用圖著色理論和禁忌搜索算法求解,實現(xiàn)了無干擾消息并行調(diào)度,提高了網(wǎng)絡(luò)的信道利用率,降低了消息傳輸端到端的延時,減少了能量消耗。

2 系統(tǒng)模型

本文對網(wǎng)絡(luò)模型做了如下簡化假設(shè):1)網(wǎng)絡(luò)包含n個同構(gòu)節(jié)點,均勻部署在M×M的正方形區(qū)域。2)網(wǎng)絡(luò)各節(jié)點都有唯一的位置坐標,基站的位置坐標全網(wǎng)已知。3)網(wǎng)絡(luò)在初始化時以分布式的方式存儲,各節(jié)點知道自身的位置信息和其一跳范圍內(nèi)節(jié)點位置信息。4)網(wǎng)絡(luò)中節(jié)點部署后靜止,節(jié)點間的有效通信半徑為Rc,干擾范圍半徑為Ri,且要求Rc

2.1 網(wǎng)絡(luò)通信模型

通信模型描述了無線傳感器網(wǎng)絡(luò)的通信情況,本文采用網(wǎng)絡(luò)拓撲圖建立通信模型,模型中節(jié)點可以在各自的無線通信范圍內(nèi)相互通信。圖1為一個網(wǎng)絡(luò)拓撲圖示例,其中,Node(a,b,…,p)代表節(jié)點,通信邊表示兩節(jié)點相鄰且處在彼此的通信范圍Rc內(nèi)。通信邊的子集可以構(gòu)成一個用于數(shù)據(jù)聚合的路由樹。

圖1 網(wǎng)絡(luò)拓撲示意圖

2.2 網(wǎng)絡(luò)干擾模型

在無線傳感器網(wǎng)絡(luò)中,消息間的干擾可以分為沖突干擾和并行干擾。因為一個節(jié)點不能同時擁有發(fā)送和接收2種狀態(tài),也不能同時接收2個發(fā)送節(jié)點的消息,如果違反了這2點,則稱消息之間存在沖突干擾,如圖2(a)、圖2(b)所示。與已有的消息干擾模型不同,消息的并行干擾主要針對接收方起作用,如圖2(c)所示判斷消息m1(s1為發(fā)送方,r1為接收方)是否干擾消息m2(s2為發(fā)送方,r2為接收方),不需考慮s1與s2,r1與r2間的干擾情況,只判斷r2是否在s1的干擾范圍Ri之內(nèi)來確定,如果在,則消息m1會干擾消息m2;否則不會。消息m2是否干擾消息m1也可以通過同樣的方法確定。如果消息m1干擾m2,或者m2干擾m1,則稱消息m1和m2之間存在干擾,存在干擾的2個消息只能串行發(fā)送;如果消息m1不會干擾m2,并且m2不會干擾m1,則稱消息m1和m2之間互不干擾。

圖2 消息干擾情況

2.3 消息并行調(diào)度模型

無線網(wǎng)絡(luò)節(jié)點傳輸距離及干擾范圍均有限,因此,互不干擾的消息可以并行調(diào)度。2個消息是否可以并行調(diào)度,主要看它們之間是否存在相互干擾,如果沒有干擾,則可以并行調(diào)度,否則不能。因此,并行消息的判定問題可以轉(zhuǎn)化為消息之間是否存在相互干擾的判定問題。通過網(wǎng)絡(luò)干擾模型可以判定網(wǎng)絡(luò)各消息間的干擾情況,互不干擾的2個消息可以并行調(diào)度。多個消息是否可以并行調(diào)度,主要看它們倆倆之間是否存在相互干擾。

本文采用消息圖建立并行調(diào)度模型,圖中頂點mn代表消息,實線代表干擾邊,利用網(wǎng)絡(luò)干擾模型判斷消息間的干擾情況。假設(shè)網(wǎng)絡(luò)中一組消息按截止期限從早到晚依次排列,為了讓盡可能多的消息并行發(fā)送,提高信道利用率,縮短總延時,應(yīng)建立實時消息調(diào)度并行優(yōu)化模型。如果2個消息之間存在干擾,則在這2個消息對應(yīng)的頂點之間畫一條邊。這樣就得到如圖3所示的消息圖,沒有干擾的消息可以并行發(fā)送。

圖3 消息圖

3 RMPS算法描述

RMPS算法在已知無線傳感器節(jié)點的部署情況下,利用預(yù)約機制構(gòu)建一個調(diào)度請求,用于各節(jié)點在上報階段向基站發(fā)送時隙請求?；緦⑸蠄笮畔⒄喜?gòu)建并行調(diào)度表,讓調(diào)度階段內(nèi)無干擾的消息盡可能同時傳輸。這種有序的時隙分配算法,既有效地避免了信道沖突,又實現(xiàn)了消息調(diào)度的并行優(yōu)化,充分利用有限的時隙傳輸盡可能多的消息,最大化消息傳輸?shù)牟⑿谐潭取Ｔ诓⑿姓{(diào)度表中無時隙分配的節(jié)點進入休眠狀態(tài),降低了節(jié)點的能耗。

算法按周期進行,每個周期可以劃分為上報階段、調(diào)度階段和傳輸階段。

1)上報階段:用于事件消息的發(fā)現(xiàn),采用固定順序和固定長度分配方式,每個節(jié)點分配等同的時間片。節(jié)點檢測到消息后,向基站發(fā)送少量的請求信息。

2)調(diào)度階段:調(diào)度階段也采用固定順序和固定長度分配方式,每個節(jié)點分配相應(yīng)的時間片?；靖鶕?jù)收到的請求信息構(gòu)建消息并行調(diào)度表并下傳調(diào)度表至各個節(jié)點。

3)傳輸階段:該階段細分為多個時隙,各節(jié)點根據(jù)按并行調(diào)度表中分配的時隙傳輸消息,未分配到時隙的節(jié)點則進入休眠狀態(tài)。

算法幀結(jié)構(gòu)如圖4所示。

圖4 RMPS算法調(diào)度周期劃分

3.1 上報階段

上報階段運行了RTQS[21]算法中預(yù)約機制,預(yù)約機制類似于一種數(shù)據(jù)采集過程,即節(jié)點檢測到環(huán)境中的消息后,并不立即發(fā)送,而是先發(fā)送一個預(yù)約請求,預(yù)約請求中只包含少量的信息CH(消息的編號mi,消息截止期限di,檢測到消息的節(jié)點id)?？紤]到基站必須收到所有的節(jié)點的上報信息,因此節(jié)點發(fā)送上報信息時具有先后順序,父節(jié)點必須在收到所有子節(jié)點的上報信息后,將自身的信息和收到的信息進行數(shù)據(jù)融合,再將融合后得到的新上報信息發(fā)送給上一層的父節(jié)點,最終將所有節(jié)點的信息都上報給基站。

3.2 調(diào)度階段

本文提出的算法用以解決無線CPS中調(diào)度階段內(nèi)消息的并行傳輸問題。在無線CPS中,節(jié)點具有周期性檢測周圍環(huán)境中特定數(shù)據(jù)的能力,當節(jié)點檢測到的數(shù)據(jù)發(fā)生變化時,需及時將消息發(fā)送到基站。消息從源節(jié)點到目的節(jié)點往往要經(jīng)過若干個中間節(jié)點?；靖鶕?jù)上報信息構(gòu)建消息并行調(diào)度表,并行調(diào)度表包含消息傳輸?shù)捻樞虿襟E、節(jié)點在各時隙內(nèi)所處的狀態(tài)(發(fā)送狀態(tài)、接收狀態(tài)和休眠狀態(tài))和消息間并行調(diào)度情況。并行調(diào)度表的構(gòu)建主要從路徑選擇和并行發(fā)送兩方面來考慮?；緸槊總€消息的發(fā)送節(jié)點選擇最優(yōu)的接收節(jié)點,進而選擇合適的傳輸路徑,同時通過判斷同一時隙內(nèi)各個消息間的干擾情況,讓無干擾的消息并行發(fā)送。

3.2.1 路徑選擇

網(wǎng)絡(luò)中一組消息從源節(jié)點到目的節(jié)點往往要經(jīng)過若干個中間節(jié)點,并且可能存在多條可達路徑,因此,需要為鏈路中的每一跳傳輸選擇合適的接收節(jié)點,進而選擇合適的傳輸路徑。無線CPS網(wǎng)絡(luò)具有較高的服務(wù)質(zhì)量(QoS)要求,消息的截止期限是網(wǎng)絡(luò)需要考慮的首要因素。從發(fā)送節(jié)點(Si)相鄰一跳范圍內(nèi),選出能滿足消息mi傳輸時限要求的節(jié)點作為Si的候選接收節(jié)點(CRi)。判斷依據(jù)是在時隙tn內(nèi)消息mi最晚發(fā)送時間L(i,tn)能否滿足下列關(guān)系式:

t≤L(i,tn)=di-w(i,tn)

(1)

其中,t代表時隙tn段首對應(yīng)網(wǎng)絡(luò)全局時鐘的時刻,di為消息mi的截止期限,w(i,tn)為消息mi經(jīng)過CRi到達基站最短路徑上所需的時間。

在選擇消息傳輸鏈路時,還要考慮節(jié)點剩余能量和消息傳輸延時。在滿足式(1)的候選接收節(jié)點CRi中,選出權(quán)值最高的節(jié)點作為最終的接收節(jié)點(Ri)。在時隙tn內(nèi),接收節(jié)點Ri的權(quán)值定義(RW)如下:

(2)

其中,Ec是表示候選節(jié)點CRi當前剩余能量,Em表示候選節(jié)點CRi的初始能量,NCRi表示候選接收節(jié)點CRi到基站最短路徑上節(jié)點的數(shù)目,L(i,tn)表示消息i在時隙tn內(nèi)最晚發(fā)送時間,α、β、θ是大于0的常數(shù),且α+β+θ=1,它們是調(diào)節(jié)各因子在接收權(quán)值中的比重。針對本文所述網(wǎng)絡(luò),設(shè)定α、β、θ之間的關(guān)系為α<β<θ。

在式(2)中,引入了3個影響網(wǎng)絡(luò)消息傳輸?shù)囊蜃?節(jié)點剩余能量,消息傳輸路徑,消息傳輸延時。選擇最短傳輸路徑傳固然可以最快傳輸消息,但最短傳輸路徑上的某些節(jié)點可能成為“關(guān)鍵節(jié)點”,即其擔(dān)任了較多鏈路的中繼節(jié)點,能量消耗相對較大,為了平衡網(wǎng)絡(luò)的能耗,提高消息傳輸成功率,需要考慮節(jié)點的剩余能量。同時,還考慮網(wǎng)絡(luò)的平均延時,避免某些消息經(jīng)過過多的節(jié)點傳輸。

以圖1為例,網(wǎng)絡(luò)中一組節(jié)點{a,b,c,g,i,k,n}檢測到事件消息,這組消息按最晚發(fā)送時間從早到晚排列為{m2,m7,m1,m4,m6,m5,m3}。根據(jù)本文提出的算法,為時隙t1內(nèi)各發(fā)送節(jié)點選擇的接收節(jié)點如表1所示。

表1 消息接收節(jié)點

3.2.2 并行發(fā)送

無線網(wǎng)絡(luò)是一種共享信道的網(wǎng)絡(luò),2個消息同時發(fā)送時相互之間可能會產(chǎn)生沖突或碰撞而使消息失真或丟失;無線網(wǎng)絡(luò)中節(jié)點的傳輸距離和干擾半徑均有限,互不干擾的消息可以并行發(fā)送,因此消息之間存在干擾性和并行性等特征。網(wǎng)絡(luò)中各節(jié)點發(fā)送的消息需基站統(tǒng)一調(diào)度,避免信道競爭及消息間的干擾,實現(xiàn)無沖突的消息并行傳輸。

仍以圖1為例,在時隙tn內(nèi)確定了一組消息的接收節(jié)點,選擇這組消息中L(i,tn)最小的消息mim優(yōu)先發(fā)送,這是為了讓截止期限早的消息能夠盡快地傳輸?shù)交尽Ｍ瑫r,為了提高信道利用率,降低傳輸平均延時,要使這組消息中與mim無干擾的消息并行發(fā)送。

首先給時隙t1內(nèi)所需傳輸?shù)南?chuàng)建一個頂點。然后根據(jù)并行消息的判定原則,如果2個消息之間存在干擾,就在這2個消息對應(yīng)的頂點之間畫一條邊。這樣就得到如圖5(a)所示的消息圖。

采用圖著色理論和禁忌搜索算法,對如圖5(a)所示的所有頂點進行多輪條件著色,使得所用的顏色數(shù)最少,顏色相同的頂點所對應(yīng)的消息可以并行發(fā)送。著色的基本原則是從最晚發(fā)送時間L(i,tn)最小的消息mim代表的頂點開始著色,使用盡可能少的顏色,著色過程中優(yōu)先選擇編號較小的顏色。著色結(jié)果如圖5(b)所示,只需2種顏色C1、C2即可將消息圖著色完畢。在時隙t1內(nèi)節(jié)點b、g、k、n,處在發(fā)送狀態(tài),節(jié)點c、h、l、BS處在接收狀態(tài),其他節(jié)點處在休眠狀態(tài),即鏈路bc、gh、kl、nBS可以并行傳輸消息。

圖5 時隙t1內(nèi)消息圖和著色結(jié)果

基站為每個時隙內(nèi)所需傳輸?shù)南⒍歼M行路徑選擇和并行調(diào)度,直到所有消息都能成功傳輸?shù)交?相應(yīng)的并行調(diào)度表也構(gòu)建完成并下傳給各個節(jié)點。表2是基站為以圖1為例的一組消息構(gòu)建的并行調(diào)度表。

表2 消息并行調(diào)度

3.3 傳輸階段

傳輸階段細分為多個時隙,各節(jié)點根據(jù)自己在調(diào)度表中分配的時隙傳輸消息,沒有分配時隙或者對應(yīng)時隙內(nèi)不需要調(diào)度的節(jié)點則進入休眠狀態(tài),節(jié)約能量消耗。

4 實驗仿真

網(wǎng)絡(luò)仿真可以解決大多數(shù)研究人員因沒有條件搭建對部署環(huán)境及硬件成本很高要求的大規(guī)模傳感器網(wǎng)所帶來的困擾。當前主要網(wǎng)絡(luò)仿真軟件有NS2、OPNET、GloMoSim、OMNeT++等。NS2是一種開源的網(wǎng)絡(luò)仿真軟件,它擁有的模塊幾乎囊括網(wǎng)絡(luò)技術(shù)的所有方面。使用NS2可以很容易進行網(wǎng)絡(luò)技術(shù)開發(fā),目前已成為廣泛使用的一種網(wǎng)絡(luò)模擬軟件,因此本文選取NS2作為協(xié)議的網(wǎng)絡(luò)仿真軟件。實驗部分Tcl腳本代碼如下:

set n(0) [$ns node]

$n(0) random-motion 0

$n(0) set X_ 100.0

$n(0) set Y_ 100.0

$n(0) set Z_ 0.0

$ns initial_node_pos $n(0) 60

set n(1) [$ns node]

$n(1) random-motion 0

$n(1) set X_ 300.0

$n(1) set Y_ 100.0

$n(1) set Z_ 0.0

$ns initial_node_pos $n(1) 60

set n(2) [$ns node]

$n(2) random-motion 0

$n(2) set X_ 500.0

$n(2) set Y_ 100.0

$n(2) set Z_ 0.0

$ns initial_node_pos $n(2) 60

set udp0 [new Agent/UDP]

$ns attach-agent $n0 $udp0

set null0 [new Agent/Null]

$ns attach-agent $n(2) $null0

$ns connect $udp0 $null0

set cbr0 [new Application/Traffic/CBR]

$cbr0 attach-agent $udp0

4.1 實驗參數(shù)

對于算法的驗證選用NS2作為實驗仿真平臺,從消息截止期限失去率、網(wǎng)絡(luò)平均延時和能量消耗3個方面來評估算法的性能。本文將實驗場景均勻劃分成10 m×10 m的網(wǎng)格,各個網(wǎng)格中只有一個節(jié)點,節(jié)點位置固定不再變化,節(jié)點和網(wǎng)絡(luò)的主要實驗參數(shù)配置如表3所示。

表3 基本參數(shù)設(shè)置

4.2 對比分析

本文研究采用截止期限失去率、平均傳輸延時和節(jié)點能量消耗作為主要網(wǎng)絡(luò)性能評價指標,將本文提出的RMPS算法與經(jīng)典HEED算法、L-RQS算法和CC-TDMA算法對比分析,來評估RMPS算法的性能。

截止期限失去率定義為未能在截止期限之前到達目的節(jié)點的消息占總發(fā)送消息數(shù)的比率。在本文中將這一評價作為事件驅(qū)動的無線CPS網(wǎng)絡(luò)實時消息調(diào)度的重要參考指標。截止期限失去率對比結(jié)果如圖6所示。當消息數(shù)目小于10時,4種算法都能滿足消息的截止期限要求;當消息數(shù)目大于10時,經(jīng)典HEED算法截止期限失去率最高,L-RQS算法次之,RMPS算法最低;當消息數(shù)目大于90時,經(jīng)典HEED算法、L-RQS算法和CC-TDMA算法截止期限失去率都會明顯升高,而RMPS算法只是略有上升。這是因為在RMPS算法中將消息的截止期限作為網(wǎng)絡(luò)的首要因素,讓截止期限早的消息優(yōu)先發(fā)送,同時,在著色階段使用盡可能少的顏色為一組消息對應(yīng)的消息圖進行著色,實現(xiàn)無干擾消息并行調(diào)度,提高了信道利用率,減少了排隊延時。

圖6 一輪循環(huán)內(nèi)截止期限失去率

假定事件傳輸延時為從節(jié)點檢測到事件到事件成功傳輸至基站的時間間隔。網(wǎng)絡(luò)平均傳輸延時即為一輪循環(huán)內(nèi)所有事件的平均傳輸延時。平均延時對比結(jié)果如圖7所示。隨著網(wǎng)絡(luò)負載的增加,4種算法的平均延時都在增加,但相比于HEED算法和CC-TDMA,RMPS算法和L-RQS算法網(wǎng)絡(luò)的平均延時明顯偏低且增長幅度較慢,且在網(wǎng)絡(luò)負載較高時RMPS算法平均延時表現(xiàn)依然較好。這是因為RMPS算法采用圖著色理論,對消息圖進行多輪條件著色得到一個最優(yōu)的解,讓盡可能多的消息并行傳輸,提高了信道利用率,降低了網(wǎng)絡(luò)平均延時。

圖7 平均延時比較

由于傳感器節(jié)點能量有限,且不能及時補充,因此節(jié)點能量有效利用率是MAC協(xié)議需要考慮的一項因素。平均能量消耗對比如圖8所示。當消息數(shù)目較少時,4種算法能量消耗沒有明顯差別;隨著消息數(shù)目的增加,RMPS算法和CC-TDMA算法比經(jīng)典HEED算法和L-RQS算法能量消耗低,而RMPS算法又比CC-TDMA算法低。這主要是因為RMPS算法在選擇傳輸路徑時,將節(jié)點剩余能量作為一個重要因子,選擇剩余能量較高節(jié)點作為中繼節(jié)點。在傳輸階段,各節(jié)點根據(jù)消息并行調(diào)度表中分配的時隙確定自己的狀態(tài),沒有分配時隙的節(jié)點使其較長時間處于休眠狀態(tài),減少能量消耗。

圖8 一輪循環(huán)內(nèi)平均能量消耗比較

5 結(jié)束語

本文針對事件驅(qū)動型無線CPS實時性要求較高的特點,從并行消息的判定、消息傳輸?shù)穆窂竭x擇和消息的并行傳輸三方面進行研究,建立有效的實時消息調(diào)度并行優(yōu)化模型,并使用圖著色理論求解。實驗結(jié)果表明,本文方法可實現(xiàn)無干擾消息并行發(fā)送,提高信道利用率,降低端到端的延時,對無線CPS實時消息的研究具有一定的借鑒意義。

[1] 何積豐.信息物理融合系統(tǒng)[J].中國計算機學(xué)會通訊,2010,6(1):25-29.

[2] 李仁發(fā),謝 勇,李 蕊,等.信息-物理融合系統(tǒng)若干關(guān)鍵問題綜述[J].計算機研究與發(fā)展,2012,49(6):1149-1161.

[3] YOGARATHINAM A.CPS:Architecture and Distributed Computation in the Networked Control Paradigm:An Autonomous Grid Example[EB/OL].[2015-10-12].https://www.researchgate.net/publication/295010727_cps.

[4] IMRAN Q,ALESSANDRA B,ETIENNE B,et al.Modeling Methodologies for Cyber-physical Systems:Research Field Study on Inherent and Future Challenges[J].Ada User Journal,2015.

[5] ZIMMER C,BHAT MUELLER F,et al.Intrusion Detection for CPS Real-time Controllers[J].Power Systems,2015,79(1):329-358.

[6] RAJKUMAR R,LEE I,SHA L,et al.Cyber-physical Systems:The Next Computing Revolution[J].Strasbourg,2010,14(6):731-736.

[7] LEE I,SOKOLSKY O,CHEN S,et al.Challenges and Research Directions in Medical Cyber-physical Systems[J].Proceedings of the IEEE,2012,100(1):75-90.

[8] RAHMAN S U,AHMAD M,BAZAZ S A.A New Energy-efficient TDMA-based MAC Protocol for Periodic Sensing Applications in Wireless Sensor Networks[J].International Journal of Computer Science Issues,2012,9(4):215-222.

[9] YOUNIS O,FAHMY S.HEED:A Hybrid,Energy-efficient,Distributed Clustering Approach for Ad Hoc Sensor Networks[J].IEEE Transactions on Mobile Computing,2004,3(4):366-379.

[10] GUGLIELMO D D,RESTUCCIA F,ANASTASI G,et al.Accurate and Efficient Modeling of 802.15.4 Unslotted CSMA/CA Through Event Chains Computation[J].IEEE Transactions on Mobile Computing,2016,15(12):2954-2968.

[11] BURATTI C,VERDONE R.L-CSMA:A MAC Protocol for Multi-hop Linear Wireless(Sensor) Networks[J].IEEE Transactions on Vehicular Technology,2016,65(1):251-265.

[12] HUANG P K,LIN X.Achieving Optimal Throughput Utility and Low Delay with CSMA-like Algorithms:A Virtual Multichannel Approach[J].IEEE/ACM Transactions on Networking,2015,23(2):505-518.

[13] HAI V L,TANG X.An Efficient Algorithm for Scheduling Sensor Data Collection Through Multi-path Routing Structures[J].Journal of Network & Computer Applications,2014,38(2):150-162.

[14] SEVANI V,RAMAN B.HTTPDissect:Detailed Performance Analysis of HTTP Web Browsing Traffic in TDMA Mesh Networks[J].IEEE Transactions on Mobile Computing,2016,15(4):853-867.

[15] SAMI M,NOORDIN N K,KHABAZIAN M.A TDMA-based Cooperative MAC Protocol for Cognitive Networks with Opportunistic Energy Harvesting[J].IEEE Com-munications Letters,2016,20(4):808-811.

[16] ZHANG R,CHENG X,YANG L,et al.A Novel Centralized TDMA-based Scheduling Protocol for Vehicular Networks[J].IEEE Transactions on Intelligent Transportation Systems,2015,16(1):411-416.

[17] 田立勤,張 琪,陳振國.一種保障無線傳感器網(wǎng)絡(luò)信息實時傳輸?shù)恼{(diào)度方法:CN103532877A[P].2014-01-22.

[18] JAIN V,AGARWAL S,GOSWAMI K.Dynamic Multilevel Priority Packet Scheduling Design for WSN[C]//Proceedings of International Conference on Signal Propagation and Computer Technology.Washington D.C.,USA:IEEE Press,2014:86-90.

[19] 蔣 青,任行帆,張佳星.一種基于優(yōu)先級的異構(gòu)無線網(wǎng)絡(luò)切換算法[J].重慶郵電大學(xué)學(xué)報(自然科學(xué)版),2014,26(6):826-831.

[20] LING Q,YAN J,DENG H.A Novel Energy-aware Routing Algorithm for Wireless Sensor Networks Based on CDMA and TDMA[J].Ad Hoc & Sensor Wireless Networks,2015,26(1):21-41.

[21] CHIPARA O,LU C,ROMAN G C.Real-time Query Scheduling for Wireless Sensor Networks[J].IEEE Transactions on Computers,2013,62(9):389-399.