一種事件驅動的無線CPS實時消息并行調度方法

譚朋柳,冒蘇敏,周 樂

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

0 概述

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

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

事件驅動的無線CPS是一種多跳無線自組織網絡實時系統,實時性要求較高。為此,本文提出一種實時消息并行調度算法(RMPS),該算法主要研究并行消息的判定、消息傳輸的路徑選擇和消息的并行傳輸。

1 相關工作

近年來,國內外學者提出了許多無線傳感器網絡實時消息的調度方法,歸納起來主要分為基于競爭的方法、基于TDMA的方法、混合方法、基于優先級等。

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

2)在基于TDMA的方法中,文獻[13]提出一種分布式數據融合調度算法,這種方式使用了一個多片結構調度節點到基站的數據傳輸,減少了數據的復雜程度和算法調度的運行時間。該算法不能隨著網絡的改變而自適應變化。文獻[14]提出的算法在構建路由和傳輸調度階段都進行優化,但它并不能有效降低消息傳輸端到端的延時。文獻[15]提出了一種能量感知的消息調度方法(CC-TDMA)。雖然該算法降低了高優先級事件的傳輸延時,但它不是分布式的且不適合大型網絡。文獻[16]提出一種新的基于權重因子的消息調度算法,將信道質量、傳輸速度和事件優先級作為影響因子,提高了信道傳輸的公平性,但它不能保證消息的硬實時性。文獻[17]針對實時性較高的無線網絡,提出一種保障無線傳感器網絡消息實時性的調度方法(L-RQS)。該方法將消息進行優先級劃分,同時根據路由節點轉發的高優先級消息個數或等待時間設置節點的狀態。該方法提高了網絡吞吐量,但沒有考慮消息傳輸的并行性。

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

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

2 系統模型

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

2.1 網絡通信模型

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

圖1 網絡拓撲示意圖

2.2 網絡干擾模型

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

圖2 消息干擾情況

2.3 消息并行調度模型

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

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

圖3 消息圖

3 RMPS算法描述

RMPS算法在已知無線傳感器節點的部署情況下,利用預約機制構建一個調度請求,用于各節點在上報階段向基站發送時隙請求。基站將上報信息整合并構建并行調度表,讓調度階段內無干擾的消息盡可能同時傳輸。這種有序的時隙分配算法,既有效地避免了信道沖突,又實現了消息調度的并行優化,充分利用有限的時隙傳輸盡可能多的消息,最大化消息傳輸的并行程度。在并行調度表中無時隙分配的節點進入休眠狀態,降低了節點的能耗。

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

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

2)調度階段:調度階段也采用固定順序和固定長度分配方式,每個節點分配相應的時間片。基站根據收到的請求信息構建消息并行調度表并下傳調度表至各個節點。

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

算法幀結構如圖4所示。

圖4 RMPS算法調度周期劃分

3.1 上報階段

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

3.2 調度階段

本文提出的算法用以解決無線CPS中調度階段內消息的并行傳輸問題。在無線CPS中,節點具有周期性檢測周圍環境中特定數據的能力,當節點檢測到的數據發生變化時,需及時將消息發送到基站。消息從源節點到目的節點往往要經過若干個中間節點。基站根據上報信息構建消息并行調度表,并行調度表包含消息傳輸的順序步驟、節點在各時隙內所處的狀態(發送狀態、接收狀態和休眠狀態)和消息間并行調度情況。并行調度表的構建主要從路徑選擇和并行發送兩方面來考慮。基站為每個消息的發送節點選擇最優的接收節點,進而選擇合適的傳輸路徑,同時通過判斷同一時隙內各個消息間的干擾情況,讓無干擾的消息并行發送。

3.2.1 路徑選擇

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

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

(1)

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

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

(2)

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

在式(2)中,引入了3個影響網絡消息傳輸的因子:節點剩余能量,消息傳輸路徑,消息傳輸延時。選擇最短傳輸路徑傳固然可以最快傳輸消息,但最短傳輸路徑上的某些節點可能成為“關鍵節點”,即其擔任了較多鏈路的中繼節點,能量消耗相對較大,為了平衡網絡的能耗,提高消息傳輸成功率,需要考慮節點的剩余能量。同時,還考慮網絡的平均延時,避免某些消息經過過多的節點傳輸。

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

表1 消息接收節點

3.2.2 并行發送

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

仍以圖1為例,在時隙tn內確定了一組消息的接收節點,選擇這組消息中L(i,tn)最小的消息mim優先發送,這是為了讓截止期限早的消息能夠盡快地傳輸到基站。同時,為了提高信道利用率,降低傳輸平均延時,要使這組消息中與mim無干擾的消息并行發送。

首先給時隙t1內所需傳輸的消息創建一個頂點。然后根據并行消息的判定原則,如果2個消息之間存在干擾,就在這2個消息對應的頂點之間畫一條邊。這樣就得到如圖5(a)所示的消息圖。

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

圖5 時隙t1內消息圖和著色結果

基站為每個時隙內所需傳輸的消息都進行路徑選擇和并行調度,直到所有消息都能成功傳輸到基站,相應的并行調度表也構建完成并下傳給各個節點。表2是基站為以圖1為例的一組消息構建的并行調度表。

表2 消息并行調度

3.3 傳輸階段

傳輸階段細分為多個時隙,各節點根據自己在調度表中分配的時隙傳輸消息,沒有分配時隙或者對應時隙內不需要調度的節點則進入休眠狀態,節約能量消耗。

4 實驗仿真

網絡仿真可以解決大多數研究人員因沒有條件搭建對部署環境及硬件成本很高要求的大規模傳感器網所帶來的困擾。當前主要網絡仿真軟件有NS2、OPNET、GloMoSim、OMNeT++等。NS2是一種開源的網絡仿真軟件,它擁有的模塊幾乎囊括網絡技術的所有方面。使用NS2可以很容易進行網絡技術開發,目前已成為廣泛使用的一種網絡模擬軟件,因此本文選取NS2作為協議的網絡仿真軟件。實驗部分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 實驗參數

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

表3 基本參數設置

4.2 對比分析

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

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

圖6 一輪循環內截止期限失去率

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

圖7 平均延時比較

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

圖8 一輪循環內平均能量消耗比較

5 結束語

本文針對事件驅動型無線CPS實時性要求較高的特點,從并行消息的判定、消息傳輸的路徑選擇和消息的并行傳輸三方面進行研究,建立有效的實時消息調度并行優化模型,并使用圖著色理論求解。實驗結果表明,本文方法可實現無干擾消息并行發送,提高信道利用率,降低端到端的延時,對無線CPS實時消息的研究具有一定的借鑒意義。

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

[2] 李仁發,謝 勇,李 蕊,等.信息-物理融合系統若干關鍵問題綜述[J].計算機研究與發展,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] 田立勤,張 琪,陳振國.一種保障無線傳感器網絡信息實時傳輸的調度方法: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] 蔣 青,任行帆,張佳星.一種基于優先級的異構無線網絡切換算法[J].重慶郵電大學學報(自然科學版),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.