邢婷 魏小敏 李夢宇
摘 要:隨著物聯(lián)網(wǎng)的快速發(fā)展,越來越多的設(shè)備連接到互聯(lián)網(wǎng)中。云計算可以有效滿足非實時和高計算量業(yè)務(wù)的需求,但在低延遲業(yè)務(wù)方面存在很大的問題。因此,研究人員引入邊緣計算來彌補云計算的不足,并將這一理念應(yīng)用于許多場景之中。文章將邊緣計算應(yīng)用于對延遲要求較高的應(yīng)急救援場景。首先,提出了一種基于邊緣的應(yīng)急救援架構(gòu),該架構(gòu)包括3層:云層,邊緣層和設(shè)備接入層,救援任務(wù)的完成需要各層次之間的合作。設(shè)備接入層對應(yīng)物理環(huán)境中的各項資源設(shè)備,包括救援人員、無線設(shè)備和救援車輛等,文章研究基于服務(wù)質(zhì)量(Quality of Service, QoS)的復合業(yè)務(wù)多設(shè)備選擇問題,提出了一種基于QoS的多設(shè)備協(xié)同選擇機制(MDSA),并將其與傳統(tǒng)的分配算法進行比較。仿真結(jié)果表明,MDSA在丟包和能耗等方面具有良好的性能。
關(guān)鍵詞:邊緣計算;QoS;應(yīng)急救災(zāi);多設(shè)備協(xié)同
近年來,頻發(fā)的災(zāi)害給人們的生命財產(chǎn)造成了嚴重的損失,災(zāi)害已經(jīng)成為影響經(jīng)濟發(fā)展和社會安定的不可忽視因素。人們越來越重視災(zāi)害應(yīng)急管理領(lǐng)域的研究,尤其是應(yīng)急資源調(diào)度方面。應(yīng)急資源調(diào)度是應(yīng)急管理的核心環(huán)節(jié),主要研究如何在災(zāi)害發(fā)生時迅速有效地利用智能決策理論和計算機輔助工具,選擇一套最佳的應(yīng)急資源分配方案。該分配方案能夠使得分散的所需資源盡快到達應(yīng)急地點,使應(yīng)急活動得以盡快進行,從而最大限度地減少突發(fā)性災(zāi)害帶來的經(jīng)濟損失和人員傷亡[1]。
在信息技術(shù)高速發(fā)展的今天,應(yīng)急資源調(diào)度也逐漸與先進的通信技術(shù)結(jié)合起來,實現(xiàn)更好的資源調(diào)度方案。災(zāi)難現(xiàn)場擁有很多實時信息,例如道路阻塞、坍塌狀況、溫度、濕度等,這些信息對于救災(zāi)具有指導性的意義,如果缺乏對于信息的采集,盲目進行資源分配將會浪費救援時間,缺乏救援效果。此外,災(zāi)難救援時間非常寶貴,高效資源調(diào)度需要完成快速信息獲取和分析,從而得出資源調(diào)度方案。因此,建設(shè)一個實時高速的信息傳輸與分析系統(tǒng)是高效應(yīng)急資源調(diào)度的保障。
盡管當下網(wǎng)絡(luò)傳輸速率已經(jīng)有了很大的改進,但在災(zāi)害場景中,缺乏有效站點對于通信的支持,實現(xiàn)災(zāi)難現(xiàn)場與救援中心的高帶寬實時通信還是比較困難。邊緣計算作為一種新興的通信模式,通過在網(wǎng)絡(luò)邊緣搭建服務(wù)平臺,將原本中心節(jié)點提供的應(yīng)用程序、數(shù)據(jù)資源或計算服務(wù)分解為若干部分,并各自分散到邊緣節(jié)點進行處理,這種就近提供計算服務(wù)的方式能夠滿足快速連接、實時分析、快速響應(yīng)等方面的技術(shù)和應(yīng)用需求。邊緣計算的出現(xiàn)實現(xiàn)了云計算的去中心化,能夠有效避免長距離傳輸造成的時間及帶寬浪費,同時也降低了云中心的計算負荷[2]。
在本文中,我們將邊緣計算應(yīng)用于緊急救援。這個場景需要較短的響應(yīng)時間和大量的數(shù)據(jù)來制定決策。通過這種方式可以提高緊急救援的效率。本文具體研究如下:
(1)本文提出一種協(xié)作分層體系結(jié)構(gòu)。在該架構(gòu)中,計算任務(wù)可由云邊緣協(xié)調(diào)進行處理。低級服務(wù)決策過程可以從云中心移動到網(wǎng)絡(luò)邊緣,一些基本的數(shù)據(jù)可以在本地處理,減少通信帶寬的需求。
(2)基于該分層體系結(jié)構(gòu),我們討論了網(wǎng)絡(luò)邊緣的服務(wù)決策過程。在移動應(yīng)急決策方面,我們從QoS的角度引入了一種選擇機制來將服務(wù)分配給適當?shù)奈锢碓O(shè)備來執(zhí)行。在丟包率和網(wǎng)絡(luò)能耗方面,實驗數(shù)據(jù)顯示該策略具有較好的性能。
1 基于QoS的多設(shè)備協(xié)同機制
1.1 體系結(jié)構(gòu)
在緊急場景下,急救中心需要大量的實時信息才能做出快速準確的決策和協(xié)調(diào)操作。然而,道路視頻監(jiān)控和交通信息的傳輸需要高帶寬,遠距離傳輸會減慢決策速度。因此,我們提出了一種基于邊緣計算的體系結(jié)構(gòu)來提高系統(tǒng)性能。該架構(gòu)包括3層:云層、邊緣層和設(shè)備訪問層。云層是緊急命令和數(shù)據(jù)中心。指揮官在此做出高層次的決定,如救援計劃,為現(xiàn)場救援人員提供遠程培訓等。邊緣層是網(wǎng)絡(luò)的邊緣,通過在基礎(chǔ)站點上部署邊緣計算服務(wù)器,可以在邊緣層中處理一些工作,例如視頻管理和分析。通過這種方式,我們可以更好地利用通信帶寬。此外,邊緣層可以通過利用具有邊緣計算功能的網(wǎng)關(guān)來支持一些低級決策。設(shè)備訪問層主要指災(zāi)難現(xiàn)場,如道路視頻監(jiān)控,交通信息和移動緊急情況。災(zāi)難救援是一個復雜的過程,并不局限于這些部分。收集數(shù)據(jù)和執(zhí)行服務(wù)是設(shè)備訪問層的主要責任。移動突發(fā)事件是應(yīng)急指揮的重要執(zhí)行者。實際上,它可以看作是一個移動應(yīng)急平臺,包括救援人員,無線通信設(shè)備,傳感器等。如何分配資源來執(zhí)行服務(wù)也會影響救援工作的進度。在下面的部分中,我們描述了這個問題并提出了方法。
1.2 基于QoS的多設(shè)備選擇算法
1.2.1 問題模型
本文提出的移動應(yīng)急模型可以看作是移動Ad-hoc網(wǎng)絡(luò)(MANET)的典型應(yīng)用場景。具有智能設(shè)備的傳感器、無線通信設(shè)備,和救援人員可以相互通信,不依賴于先前存在的基礎(chǔ)設(shè)施,例如有線網(wǎng)絡(luò)中的路由器或受管(基礎(chǔ)設(shè)施)無線網(wǎng)絡(luò)中的接入點[3]。雙層服務(wù)映射模型如圖1所示。
圖1 雙層服務(wù)映射模型
在救援過程中,當救援點請求一個服務(wù),該服務(wù)可能由多個子服務(wù)組成并且需要多個物理設(shè)備來執(zhí)行[4]。例如,用戶請求監(jiān)視環(huán)境的服務(wù),它可以包括:監(jiān)視位置表示為S1,監(jiān)視溫度表示為S2,煙霧監(jiān)視表示為S3,環(huán)境質(zhì)量監(jiān)測表示為S4。
我們的目標是找到一套最佳的物理設(shè)備,這些設(shè)備可以協(xié)同支持服務(wù)并保持用戶體驗的質(zhì)量。圖1給出了一個雙層模型來描述將服務(wù)分配給物理設(shè)備的場景。圖示的子服務(wù)需要按順序執(zhí)行。例如,子服務(wù)S1需要S3和S2的結(jié)果。因此我們可以看到子服務(wù)之間的交互。設(shè)備層包括一些可調(diào)度資源,例如智能終端和傳感器。它們之間存在網(wǎng)絡(luò)鏈接,其中一些可以在服務(wù)層中執(zhí)行子服務(wù)。此外,不止一個設(shè)備可以執(zhí)行子服務(wù),該圖給出將子服務(wù)分配給設(shè)備的一種可能方式[5-6]。在接下來的部分中,我們將詳細介紹兩層模型,并嘗試解決如何將服務(wù)層中的GSM(S,Q,L,B)映射到設(shè)備層中的GDM(D,R,E)的問題。
(1)SM服務(wù)層模型。服務(wù)層模型將網(wǎng)絡(luò)中的服務(wù)定義為GSM(S,Q,L,B),由一組子服務(wù),S={sv|v=1,…,V},子服務(wù)所需的一組資源Q={qv|v=0,1…,V}和子服務(wù)間的一組交互L={lu|u=0,1…,U}組成。sv是服務(wù)中的第v個子服務(wù)。V是服務(wù)總數(shù)。qv={qv,w|w=1,…,W}給出子服務(wù)需要多少資源,并由相應(yīng)的權(quán)重值表示。qv,w在[0,1]范圍內(nèi)。W是資源類型的總數(shù)。lu是服務(wù)中的交互。U是子服務(wù)間的交互總數(shù)。B={bu|u=0,1…,U}是L={lu|u=0,1…,U}所需的帶寬。
(2)DM設(shè)備層模型。DM(設(shè)備層模型)給出了設(shè)備層的結(jié)構(gòu),它被定義為無向圖GDM(D,R,E),其中:
D={dk|k=0,1…,K}表示一組設(shè)備,R={rk|k=0,1…,K}表示每個設(shè)備的一組能力,E={ej|j=1,…,J}表示設(shè)備之間的一組通信鏈路。
在本文中,我們從QoS的角度選擇最佳設(shè)備集。我們在(1)中定義了一個效益函數(shù)。Pi是可以執(zhí)行第i個服務(wù)的一組設(shè)備。ρi,m是第i個服務(wù)的第m個質(zhì)量指標。αi,m是第i個服務(wù)的第m個質(zhì)量指標的權(quán)重。
F(i,Pi)=∑i∑mαi,m*ρi,m (1)
至于質(zhì)量指標,不同的服務(wù)有不同的要求。本文主要針對兩個方面,即距離和響應(yīng)時間。它們是衡量服務(wù)質(zhì)量的一般指標,我們在第4節(jié)中描述了細節(jié)。
同時,在公式(1)的基礎(chǔ)上,建立了如(2)所示的數(shù)學模型。事實上,為了正確地分配服務(wù),需要從GDM(D,R,E)中找到滿足GSM(S,Q,L,B)和最佳質(zhì)量需求的同構(gòu)子圖。
其中:δi,m是第i個服務(wù)的第m個質(zhì)量指標的最低要求。xp,v,k是一個0-1變量。 選擇dk執(zhí)行服務(wù)時設(shè)置為1,否則設(shè)置為0。yp,j也是一個0-1變量。當選擇鏈接ej來執(zhí)行服務(wù)時,它被設(shè)置為1,否則它被設(shè)置為0。
根據(jù)該模型,它是一個復雜的子圖同態(tài)問題,我們在下面的部分介紹解決方案。
1.2.2 基于QoS的多設(shè)備選擇方案MDSA
針對上一部分提出的問題,我們給出了一個具有廣度優(yōu)先搜索(Breadth First Search,BFS)和修剪機制知識的解決方案。該過程如圖2所示。
該過程由兩部分組成。第一部分是服務(wù)初始化。首先根據(jù)場景得到邏輯圖GSM(S,Q,L,B)。以圖1為例,邏輯圖表示在(3)中。
根據(jù)邏輯圖GSM(S,Q,L,B),我們得到以圖GSM的鄰接矩陣導出的以Su為根的BFS樹。并且還生成執(zhí)行服務(wù)的設(shè)備集NetTop={CDS,Gbit}的初始網(wǎng)絡(luò)拓撲。CDS是定義為CDS=(dk1,dk2,…dki)。dki是執(zhí)行第i個子服務(wù)的設(shè)備,相應(yīng)的Gbit表示找到執(zhí)行子服務(wù)的設(shè)備。例如,考慮式(3),我們得到一個執(zhí)行序列(S1,S2,S3,S4),其中BFS樹由S1生根。如果CDS=(dk1,dk2,dk3,NULL)
和Gbit=1 110,則表示有3個設(shè)備dk1,dk2,dk3可以執(zhí)行服務(wù)S1,S2,S3,尚未找到執(zhí)行服務(wù)S4的設(shè)備。因此,在開始時,NetTop=被設(shè)置為初始值,如CDS=(NULL,…,NULL)和Gbit=0…0。
設(shè)備選擇過程如下。由生存時間控制的REQ_SEL數(shù)據(jù)包將在設(shè)備之間廣播。作為第一接收器并且可以在執(zhí)行序列中執(zhí)行第一服務(wù)的設(shè)備被表示為服務(wù)開始節(jié)點,并且對REQ_SEL分組進行廣播[7-10]。在k-hop內(nèi),接收REQ_SEL數(shù)據(jù)包的設(shè)備將檢查是否有可用于執(zhí)行特定服務(wù)的資源,如果它可以執(zhí)行服務(wù)而不是終節(jié)點(執(zhí)行最后一個服務(wù)的設(shè)備),將該設(shè)備的上下文放入REQ_SEL并廣播REQ_SEL,直到找到服務(wù)端節(jié)點。如果設(shè)備是終節(jié)點,則形成ACK_SEL包并發(fā)送給用戶構(gòu)建初始UCS為(4),ρt,m表示為第t個解決方案中的第m個服務(wù)質(zhì)量指標CDSt。最后,選擇具有收益函數(shù)的最優(yōu)集合,并使用REQ_ROU數(shù)據(jù)包,ACK_ROU數(shù)據(jù)包完成設(shè)備分配。
此外,在接收到ACK_SEL消息后,用戶將構(gòu)造UCS并根據(jù)(2)選擇最佳的CDSi。由于多設(shè)備選擇過程的問題模型是多目標函數(shù),我們將計算過程分解為兩個步驟,以簡化計算的復雜度。首先,我們從UCS中選擇ZCDS作為根據(jù)(2)的初步設(shè)備集。計算Z的公式如(5)所示。
這里,M是UCS的總數(shù)。λ設(shè)定為0.5。
之后,根據(jù)(2)中的第二個目標函數(shù),我們從上述Z CDS中選擇最佳協(xié)同Z作為實現(xiàn)服務(wù)的初始設(shè)備集。這里以圖3為例。
步驟1:救援點請求組合服務(wù),并且d1被表示為服務(wù)開始節(jié)點S1并廣播REQ_SEL。
步驟2:收到REQ_SEL后,d2,d3,d10檢查是否滿足S2的要求。d3和d10只轉(zhuǎn)發(fā)REQ_SEL。d2可以將其信息添加到REQ_SEL中,然后廣播REQ_SEL,生成UCS=((d1,d2,NULL,NULL,1 100),ρ1,1,ρ1,1,…,ρ1,m)。
步驟3:d7從d5接收REQ_SEL,d8從d6接收REQ_SEL,它們是服務(wù)終節(jié)點,因此發(fā)送REQ_ACK。最后,我們選擇一個最優(yōu)集合CDS并建立路由。
2 實驗評估
2.1 實驗環(huán)境
在模擬中,我們將從兩個評估指標驗證所提出機制的性能:服務(wù)距離,服務(wù)響應(yīng)時間。我們給出這些質(zhì)量指標的定義,定義服務(wù)距離是設(shè)備和用戶間的平均距離。
2.1.1 服務(wù)距離
2.1.2 服務(wù)響應(yīng)時間
其中Ti是服務(wù)i的響應(yīng)時間,Tmax是用戶可以接受的最長等待時間。
用OPNET建立一個帶無線通信設(shè)備和MANET的仿真環(huán)境,然后通過Matlab等統(tǒng)計分析工具分析實驗結(jié)果?;贠PNET,構(gòu)建了一個面積為100×150(Ti)的網(wǎng)絡(luò),包括60個異構(gòu)設(shè)備。模擬過程中參數(shù)的詳細信息如表1所示。為了觀察MDSA與多用戶的性能,模擬了具有1、4和8個用戶的場景。此外,模擬各種最大速度(1、5、10、15和20 m/s)以顯示MDSA適用于具有高移動性設(shè)備的環(huán)境。
2.2 結(jié)果分析
考慮到應(yīng)急救援場景中救援點的網(wǎng)絡(luò)體驗和質(zhì)量,MDSA的性能已經(jīng)與基于成本的簡單分配算法CDA進行了比較[5]。我們通過兩個測量分析實驗結(jié)果,包括能耗和丟包率。
(1)能耗:由于網(wǎng)絡(luò)中終端設(shè)備的能量有限,高性能的多終端選擇算法將有助于節(jié)省能源。如圖4所示,與CDA相比,MDSA可以在情況4下節(jié)省0~22%的能耗。并且能量消耗得到顯著改善,特別是當終端的移動速度增加或多個用戶同時請求服務(wù)時。
(2)丟包率:圖5給出了1個用戶,4個用戶和8個用戶在不同場景下各種移動速度下的平均丟包率。在4個用戶的情況下,結(jié)果表明隨著終端移動速度的增加,MDSA的丟包率明顯低于其他方法。在1個用戶和8個用戶的情況下,結(jié)果表明MDSA的性能比CDA好2%~16%。
3 結(jié)語
高效的應(yīng)急救援在災(zāi)難中起著至關(guān)重要的作用。當前的應(yīng)急通信系統(tǒng)面臨多種挑戰(zhàn),例如帶寬不足導致應(yīng)急響應(yīng)緩慢。我們引入了一種基于邊緣計算的應(yīng)急系統(tǒng)架構(gòu),可以將一些過程從云中心移動到網(wǎng)絡(luò)邊緣。作為事故現(xiàn)場的重要部分,移動應(yīng)急決定了救援的效率。如何構(gòu)建服務(wù)并為設(shè)備分配服務(wù)是值得我們關(guān)注的問題。在多設(shè)備協(xié)同過程中,服務(wù)質(zhì)量將受到物理設(shè)備能力或網(wǎng)絡(luò)拓撲動態(tài)的影響。為了向用戶提供高質(zhì)量的服務(wù),保持服務(wù)的連續(xù)性和穩(wěn)定性,本文提出了一種基于QoS的多設(shè)備協(xié)同選擇機制,仿真結(jié)果表明,與CDA相比,我們的機制在能耗和丟包率方面具有較好的性能。
[參考文獻]
[1]柴秀榮.災(zāi)害應(yīng)急救助物資調(diào)度系統(tǒng)研究[D].合肥:中國科學技術(shù)大學,2009.
[2]張婷.災(zāi)害應(yīng)急管理中的應(yīng)急資源調(diào)度問題研究[D].合肥:合肥工業(yè)大學,2015.
[3]SUN Q,KONG F,ZHANG L,et al.Study on emergency distribution route decision making[C].Changchun:2011 International Conference on Mechatronic Science,Electric Engineering and Computer(MEC)2011.
[4]ZHAO T C,ZHOU S,GUO X Y.A cooperative scheduling scheme of Icloud and Internet cloud for delay-aware mobile cloud computing[C].San Diego:Proceeding IEEE Globecom Workshops,2015.
[5]HAUBENWALLER A,VANDIKAS K.Computations on the edge in the Internet of Things[J].Procedia Computer Science,2015(52):29-34.
[6]FLORES H,HUI P,TARKOMA S,et al.Mobile code offloading: from concept to practice and beyond[J].IEEE Communications Magazine,2015(3):80-88.
[7]CHEN X,JIAO L,LI W,et al.Efficient multi-user computation offloading for mobile-edge cloud computing[J].IEEE/ACM Transactions on Networking,2015(5):2795-2808.
[8]YOU C,HUANG K,CHAE H,et al.Energy-efficient resource allocation for mobile-edge computation offloading[J].IEEE Transactions on Wireless Communications,2017(16):1397-1411.
[9]SARDELLITTI S,SCUTARI G,BARBAROSSA S.Joint optimization of radio and computational resources for multicell mobile-edge computing[J].IEEE Transactions on Signal and Information Processing over Networks,2015(2):89-103.
[10]TALEB T,DUTTA S,KSENTINI A,et al.Mobile edge computing potential in making cities smarter[J].IEEE Communications Magazine,2017(3):38-43.