常豐田,周光輝,李錦濤,張超,肖忠東

(1.西安交通大學(xué)機(jī)械工程學(xué)院,710049,西安;2.長安大學(xué)工程機(jī)械學(xué)院,710064,西安;3.西安交通大學(xué)管理學(xué)院,710049,西安)

工業(yè)物聯(lián)網(wǎng)、無線傳感網(wǎng)絡(luò)、深度學(xué)習(xí)、云計算、邊緣計算等新一代信息技術(shù)的迅猛發(fā)展和融合促進(jìn)了制造業(yè)的轉(zhuǎn)型和升級,形成了以數(shù)據(jù)化、網(wǎng)絡(luò)化和智能化為支撐的具備自感知、自決策、自執(zhí)行、自適應(yīng)和自學(xué)習(xí)的新一代智能制造[1]。為落實(shí)和應(yīng)用智能制造,智能裝備、智能單元和智能產(chǎn)線快速發(fā)展,網(wǎng)絡(luò)智能裝備數(shù)量和產(chǎn)生的數(shù)據(jù)量急劇增長。然而,傳統(tǒng)采用單一的云計算模式,將所有數(shù)據(jù)通過網(wǎng)絡(luò)傳輸?shù)皆破脚_集中式處理的方式已無法滿足工業(yè)現(xiàn)場實(shí)時處理數(shù)據(jù)的需求,極易造成傳輸延遲大、寬帶壓力高、云計算資源消耗嚴(yán)重、不利于隱私保護(hù)等問題[2-3]。為彌補(bǔ)云計算的不足,邊緣計算得到快速發(fā)展。利用邊緣計算的就近、實(shí)時、短周期數(shù)據(jù)處理分析能力,結(jié)合云計算的全局、長期、海量數(shù)據(jù)優(yōu)化管控能力,同時發(fā)揮邊-云協(xié)同價值,已受到企業(yè)和學(xué)者的廣泛關(guān)注[4]。

針對離散智能產(chǎn)線/單元,為實(shí)現(xiàn)邊緣計算和邊-云協(xié)同,在單元的設(shè)備和邊緣端往往需要配置大量的感知節(jié)點(diǎn)(如傳感器、射頻識別器(RFID)、超寬頻定位器(UWB))和邊緣節(jié)點(diǎn),并依賴物聯(lián)網(wǎng)絡(luò)采集和傳輸振動、圖像、功率、壓力、溫度、噪聲、電壓、電流以及物料位置、狀態(tài)等信息,同時利用這些信息在邊緣側(cè)實(shí)現(xiàn)能耗監(jiān)測、狀態(tài)評估、物流追蹤等實(shí)時統(tǒng)計展示和分析處理服務(wù),支撐邊-云協(xié)同能力的實(shí)現(xiàn)[5]。然而,不同的物聯(lián)網(wǎng)絡(luò)配置方案,將導(dǎo)致差異化的節(jié)點(diǎn)部署結(jié)果,從而引起節(jié)點(diǎn)間不可靠的數(shù)據(jù)傳輸、互聯(lián)和協(xié)同能力。因此,在邊-云協(xié)同中,考慮網(wǎng)絡(luò)低時延、高可靠感知、傳輸和計算的最優(yōu)配置顯得尤為重要。為此:Ma等[6]將消息傳輸跳數(shù)作為影響端到端時延的因素,研究了在跳數(shù)約束下基于覆蓋的中繼節(jié)點(diǎn)部署方法;Jiang等[7]研究了基于貪婪策略的最優(yōu)傳感器部署方法;何欣等[8]采用遺傳算法確定了最佳節(jié)點(diǎn)部署位置,顯著降低了網(wǎng)絡(luò)節(jié)點(diǎn)部署成本;Zhu等[9]綜合考慮邊緣網(wǎng)關(guān)的覆蓋性、任務(wù)計算時延以及網(wǎng)關(guān)容量分配等因素,采用改進(jìn)模擬退火算法對網(wǎng)關(guān)部署問題進(jìn)行了多目標(biāo)求解;Jiang等[10]綜合考慮網(wǎng)絡(luò)時延、部署成本、空間分布、設(shè)備功能、邊緣計算能力等因素,采用改進(jìn)k-means算法獲得最優(yōu)邊緣節(jié)點(diǎn)部署位置和數(shù)量。在這些研究中,時間延遲[9-11]、部署成本[8,10,12]、負(fù)載均衡[9,11,13]、網(wǎng)絡(luò)壽命[14-15]等已成為各學(xué)者研究邊緣配置的主要因素。然而,大部分研究主要聚焦在基于感知節(jié)點(diǎn)的邊緣網(wǎng)關(guān)配置或整體物聯(lián)網(wǎng)絡(luò)的配置等,忽視了感知從節(jié)點(diǎn)與邊緣主節(jié)點(diǎn)間的互相影響和關(guān)聯(lián)協(xié)調(diào)機(jī)制,難以在已有部分節(jié)點(diǎn)的基礎(chǔ)上,通過對已有節(jié)點(diǎn)和擴(kuò)展節(jié)點(diǎn)間的協(xié)調(diào)配置和部署[16],滿足低延遲、低成本和高可靠協(xié)同數(shù)據(jù)的最佳交互,導(dǎo)致物聯(lián)網(wǎng)絡(luò)的節(jié)點(diǎn)擴(kuò)展性差,邊-云協(xié)同能力不足。

針對上述不足,本文以離散智能制造產(chǎn)線的最小生產(chǎn)單元——智能制造單元為研究對象,在提出的邊-云協(xié)同框架的基礎(chǔ)上,構(gòu)建了邊緣物聯(lián)網(wǎng)絡(luò)模型。進(jìn)一步地,利用網(wǎng)絡(luò)模型,詳細(xì)研究了基于改進(jìn)的覆蓋的中繼節(jié)點(diǎn)部署(cover-based relay node placement,CRNP)算法的主節(jié)點(diǎn)配置方法和基于貪婪策略的主從節(jié)點(diǎn)協(xié)調(diào)配置方法,為制造單元或企業(yè)產(chǎn)線的邊-云協(xié)同實(shí)現(xiàn)或能力提升,提供了節(jié)點(diǎn)協(xié)調(diào)的底層物聯(lián)配置基礎(chǔ)。

1 智能制造單元物聯(lián)網(wǎng)絡(luò)模型構(gòu)建

1.1 智能制造單元系統(tǒng)組成及邊-云協(xié)同框架

智能制造單元(smart manufacturing cell,SMC)是支持離散智能制造企業(yè)實(shí)現(xiàn)智能感知、智能決策、智能執(zhí)行和智能控制等智能生產(chǎn)任務(wù)的最小實(shí)現(xiàn)單元,同時也是智能制造車間的最小組成單元[17]。典型完備的SMC主要包括加工子系統(tǒng),物料搬運(yùn)子系統(tǒng)、倉儲子系統(tǒng)、智能采集感知子系統(tǒng)和智能決策云平臺系統(tǒng)等軟硬件系統(tǒng)。

為充分發(fā)揮系統(tǒng)內(nèi)數(shù)控車床、銑床、加工中心、自動導(dǎo)引小車(AGV)和機(jī)器人等異構(gòu)智能裝備邊緣端生產(chǎn)數(shù)據(jù)實(shí)時、動態(tài)、低延時的快速傳輸、處理、計算、分析和控制能力,同時提升云平臺大數(shù)據(jù)的全局、長期、最優(yōu)的智能決策和管控能力[18-19],構(gòu)建設(shè)備層、邊緣層和云平臺層的“端-邊-云”3層邊-云協(xié)同框架,如圖1所示。其中:設(shè)備層由智能制造單元中的各種物聯(lián)設(shè)備組成,如傳感器、攝像頭、RFID、數(shù)控機(jī)床、機(jī)器人、AGV等,這些物聯(lián)設(shè)備作為端節(jié)點(diǎn)(從節(jié)點(diǎn))通過各種有線網(wǎng)絡(luò)(如工業(yè)以太網(wǎng)、各種現(xiàn)場總線等)或無線網(wǎng)絡(luò)(如藍(lán)牙、Wi-Fi、RFID等)與邊緣層相連接;邊緣層由邊緣服務(wù)器和邊緣計算節(jié)點(diǎn)構(gòu)成,邊緣層通過物聯(lián)網(wǎng)絡(luò)與設(shè)備層端節(jié)點(diǎn)相連,負(fù)責(zé)接受、處理和轉(zhuǎn)發(fā)獲取的設(shè)備層數(shù)據(jù),并提供協(xié)同解析、數(shù)據(jù)集成、智能感知、隱私保護(hù)和實(shí)時計算管控等服務(wù);云平臺層具備強(qiáng)大的計算和存儲能力,對邊緣層無法處理的計算任務(wù)以及全局信息任務(wù),通過物聯(lián)網(wǎng)絡(luò)的收集匯總進(jìn)行綜合地處理、分析以及任務(wù)的卸載和下發(fā)。

綜上可知,為發(fā)揮邊-云協(xié)同效應(yīng),充分利用邊緣節(jié)點(diǎn)的協(xié)同計算能力,通過對設(shè)備層、邊緣層感知和計算節(jié)點(diǎn)的最優(yōu)協(xié)調(diào)配置,實(shí)現(xiàn)物聯(lián)網(wǎng)絡(luò)低延遲、高可靠、可互聯(lián)的最佳部署顯得尤為重要。

1.2 邊緣物聯(lián)網(wǎng)絡(luò)模型構(gòu)建

基于邊-云協(xié)同框架,聚焦設(shè)備層和邊緣層的底層物聯(lián)網(wǎng)絡(luò)。首先,將智能制造單元物聯(lián)網(wǎng)絡(luò)假設(shè)為無線傳感網(wǎng)絡(luò),網(wǎng)絡(luò)的節(jié)點(diǎn)類型抽象為從節(jié)點(diǎn)、主節(jié)點(diǎn)和根節(jié)點(diǎn)。其中:從節(jié)點(diǎn)是設(shè)備層配置的傳感器和終端設(shè)備,負(fù)責(zé)感知現(xiàn)場設(shè)備的實(shí)時數(shù)據(jù);主節(jié)點(diǎn)即邊緣計算設(shè)備,負(fù)責(zé)對傳感節(jié)點(diǎn)數(shù)據(jù)的預(yù)處理及轉(zhuǎn)發(fā),并將數(shù)據(jù)交付給根節(jié)點(diǎn);根節(jié)點(diǎn)即邊緣服務(wù)器,是整個物聯(lián)網(wǎng)絡(luò)的中心,負(fù)責(zé)控制網(wǎng)絡(luò)的數(shù)據(jù)傳輸及匯總,并與云平臺進(jìn)行數(shù)據(jù)交互。依據(jù)節(jié)點(diǎn)類型,給出如下假設(shè)。

(1)為滿足制造單元的可擴(kuò)展性,網(wǎng)絡(luò)的通信方式采用多對一的方式[20],即同級節(jié)點(diǎn)不進(jìn)行通信。

(2)物聯(lián)網(wǎng)絡(luò)基于樹狀網(wǎng)絡(luò)拓?fù)浯罱?其中根節(jié)點(diǎn)作為數(shù)據(jù)匯入的中心。

(3)由于設(shè)備供電以及禁放區(qū)域限制,節(jié)點(diǎn)的部署位置只能通過預(yù)定義的候選部署位置(candidate deployment location,CDL)確定[21]。

(4)制造單元設(shè)備間距近,網(wǎng)絡(luò)傳輸延遲主要依賴數(shù)據(jù)從設(shè)備節(jié)點(diǎn)到邊緣服務(wù)器的轉(zhuǎn)發(fā)次數(shù)。

1.2.1 物聯(lián)網(wǎng)絡(luò)節(jié)點(diǎn)通信建模

Vadj(u)={?v|cover(u,v)},u,v∈V

(1)

式中cover(u,v)表示u、v節(jié)點(diǎn)為近鄰節(jié)點(diǎn)。

若u、v節(jié)點(diǎn)不近鄰,要實(shí)現(xiàn)兩節(jié)點(diǎn)的數(shù)據(jù)通信,就必須要求存在一個V的子集Vcon,Vcon中的節(jié)點(diǎn)可以通過兩兩相鄰的方式建立一條u到v的數(shù)據(jù)通道p(u,v),即

(2)

式中:padj(ri,ri+1)是近鄰節(jié)點(diǎn)ri與ri+1之間的網(wǎng)絡(luò)數(shù)據(jù)通路;Vcon是u到v的節(jié)點(diǎn)集合(包含u、v);k是Vcon中u到v的數(shù)據(jù)通道數(shù)。

1.2.2 物聯(lián)網(wǎng)絡(luò)傳輸延遲建模

網(wǎng)絡(luò)傳輸延遲是指從數(shù)據(jù)發(fā)送節(jié)點(diǎn)到接收節(jié)點(diǎn)的網(wǎng)絡(luò)傳輸延遲時間,由跳數(shù)(轉(zhuǎn)發(fā)次數(shù))和單跳轉(zhuǎn)發(fā)延遲確定,即

τuv=γuvτ0

(3)

式中:τuv是節(jié)點(diǎn)u到v的傳輸延遲時間;γuv是u到v的跳數(shù);τ0代表單跳傳輸延遲。

基于數(shù)據(jù)通信模型,節(jié)點(diǎn)轉(zhuǎn)發(fā)所經(jīng)歷的跳數(shù)可由數(shù)據(jù)的轉(zhuǎn)發(fā)次數(shù)表達(dá),而轉(zhuǎn)發(fā)次數(shù)依賴數(shù)據(jù)通道p(u,v),即

γuv=H(p(u,v))

(4)

式中H(·)代表數(shù)據(jù)通道內(nèi)數(shù)據(jù)轉(zhuǎn)發(fā)所經(jīng)過的節(jié)點(diǎn)數(shù)。

依據(jù)假設(shè),在制造單元內(nèi),傳輸延遲主要由數(shù)據(jù)的轉(zhuǎn)發(fā)跳數(shù)決定。因此,為保證設(shè)備間數(shù)據(jù)通信的延遲最小,可選取轉(zhuǎn)發(fā)次數(shù)最小(最短路徑)的通道pmin(u,v),記為

pmin(u,v)=arg minH(p(u,v))

(5)

1.2.3 物聯(lián)網(wǎng)絡(luò)傳輸可靠性建模

數(shù)據(jù)傳輸?shù)目煽啃灾饕蕾囉跀?shù)據(jù)包接收率[22],即在發(fā)送節(jié)點(diǎn)傳輸范圍內(nèi),能成功接收來自發(fā)送節(jié)點(diǎn)數(shù)據(jù)包的節(jié)點(diǎn)數(shù)量百分比,其大小主要與節(jié)點(diǎn)間的距離有關(guān),故相鄰節(jié)點(diǎn)u和v間的數(shù)據(jù)包接收率ψu(yù)v可定義為

(6)

式中:duv是節(jié)點(diǎn)u、v之間的歐式距離;d0是節(jié)點(diǎn)參考距離;B是傳輸比特總數(shù);η是路徑衰減指數(shù);PL(d0)是參考距離下的功率衰減。

在計算實(shí)際的數(shù)據(jù)包接受率時,往往需要依賴于一條完整的數(shù)據(jù)轉(zhuǎn)發(fā)鏈路,而每一次的數(shù)據(jù)轉(zhuǎn)發(fā)都可能伴隨著部分?jǐn)?shù)據(jù)的丟失。因此,在路徑p(u,v)中數(shù)據(jù)包接收率的定義為

(7)

式中:ψ(p(u,v))表示u、v節(jié)點(diǎn)間整條通信通道的數(shù)據(jù)包接收率;ψ(ri,ri+1)是通道p(u,v)中某相鄰節(jié)點(diǎn)間的數(shù)據(jù)包接收率。

2 基于改進(jìn)CRNP算法的主節(jié)點(diǎn)配置

基于智能制造單元物聯(lián)網(wǎng)絡(luò)模型,為實(shí)現(xiàn)邊-云協(xié)同的節(jié)點(diǎn)配置,首先需要求配置的主節(jié)點(diǎn)在實(shí)現(xiàn)所有從節(jié)點(diǎn)與根節(jié)點(diǎn)數(shù)據(jù)互聯(lián)互通的基礎(chǔ)上,保證整個網(wǎng)絡(luò)的時延與通信質(zhì)量達(dá)到指定的標(biāo)準(zhǔn)。依據(jù)假設(shè),所有主節(jié)點(diǎn)的位置需要從預(yù)定義的候選部署位置集合Lm中進(jìn)行選取。

CRNP算法[6]主要用于解決跳數(shù)約束下的中繼節(jié)點(diǎn)部署問題[23],即:當(dāng)數(shù)據(jù)的轉(zhuǎn)發(fā)次數(shù)受到限制的情況下,通過合理的中繼節(jié)點(diǎn)布局,可以解決整個網(wǎng)絡(luò)的連通性問題。為此,本文基于CRNP算法,結(jié)合制造單元物聯(lián)網(wǎng)絡(luò)特點(diǎn)和節(jié)點(diǎn)通信質(zhì)量約束,在解決整個網(wǎng)絡(luò)連通性問題的基礎(chǔ)上,盡可能地降低傳輸延遲,提高通信質(zhì)量,實(shí)現(xiàn)網(wǎng)絡(luò)的優(yōu)化配置。本文算法的具體步驟如下。

步驟1判斷原始網(wǎng)絡(luò)連通性。建立根節(jié)點(diǎn)到各從節(jié)點(diǎn)的直接通路,此時對于每一個從節(jié)點(diǎn),其跳數(shù)為最小值1,滿足跳數(shù)約束。如果存在從節(jié)點(diǎn)不在根節(jié)點(diǎn)的通信范圍內(nèi)或不滿足通信質(zhì)量的條件約束,那么判定原始網(wǎng)絡(luò)在不添加任何主節(jié)點(diǎn)的基礎(chǔ)上無法解決各節(jié)點(diǎn)間的連通性問題。否則,證明目前的網(wǎng)絡(luò)已經(jīng)在滿足約束條件的情況實(shí)現(xiàn)各從節(jié)點(diǎn)與根節(jié)點(diǎn)的數(shù)據(jù)互通,原始網(wǎng)絡(luò)滿足優(yōu)化配置需求。

步驟2建立連通網(wǎng)絡(luò)。連通網(wǎng)絡(luò)的建立是一個迭代的過程,每一次迭代都是建立節(jié)點(diǎn)與鄰接節(jié)點(diǎn)間的數(shù)據(jù)通信,最終構(gòu)成所有節(jié)點(diǎn)的數(shù)據(jù)通路。節(jié)點(diǎn)的通路選擇有最大轉(zhuǎn)發(fā)跳數(shù)和單跳通信質(zhì)量要求兩個約束限制,其中轉(zhuǎn)發(fā)跳數(shù)由通信路徑內(nèi)的轉(zhuǎn)發(fā)次數(shù)確定,單跳通信質(zhì)量由數(shù)據(jù)包接收率確定。

針對最大跳數(shù)限制,約束條件為

H(pmin(v,vr))≤γmax(u)-1;u∈Vadj(v)

(8)

式中:H(pmin(v,vr))是任一節(jié)點(diǎn)v到根節(jié)點(diǎn)vr(vr∈Vr)的最短路徑的轉(zhuǎn)發(fā)跳數(shù);γmax(u)是節(jié)點(diǎn)u的最大轉(zhuǎn)發(fā)跳數(shù),其中u是v的某一鄰接節(jié)點(diǎn)。

針對單跳通信質(zhì)量,約束條件為

ψu(yù)v≥ψmin;v∈Vadj(u)

(9)

式中ψmin是u到鄰近節(jié)點(diǎn)v的最小數(shù)據(jù)包接收率。

在滿足上述約束條件的基礎(chǔ)上,連通網(wǎng)絡(luò)的建立步驟為:

(1)在候選部署位置集Lm中,找到與各從節(jié)點(diǎn)最近的主節(jié)點(diǎn)位置,配置主節(jié)點(diǎn),建立連接;

(2)進(jìn)入迭代過程,每一次迭代在上一次迭代的基礎(chǔ)上找到一個與主節(jié)點(diǎn)最相鄰的點(diǎn)建立連接,要求節(jié)點(diǎn)間的連接建立需要滿足通信質(zhì)量約束;

(3)迭代完成后,建立從與根之間的數(shù)據(jù)通路,此時需要進(jìn)行最大跳數(shù)的驗證,若超過最大跳數(shù),跳至第(2)步,重新進(jìn)行路徑的選擇;

(4)完成連通網(wǎng)絡(luò)的建立。

步驟3冗余節(jié)點(diǎn)優(yōu)化。在連通網(wǎng)絡(luò)的建立過程中,只考慮連通性的要求,可能會導(dǎo)致冗余節(jié)點(diǎn)的出現(xiàn),增加額外的網(wǎng)絡(luò)配置成本。因此,需要對冗余節(jié)點(diǎn)進(jìn)行優(yōu)化,主要流程如下:

(1)遍歷整個連通網(wǎng)絡(luò),找到主節(jié)點(diǎn)集合Vm;

(2)選擇任一個節(jié)點(diǎn)u(u∈Vm),將該節(jié)點(diǎn)去除,在去除該節(jié)點(diǎn)的基礎(chǔ)上,驗證網(wǎng)絡(luò)是否依然滿足質(zhì)量約束與連通性準(zhǔn)則;

(3)如果滿足,則去除該節(jié)點(diǎn),否則對該節(jié)點(diǎn)進(jìn)行還原;

(4)重復(fù)第(2)(3)步,直到對所有的節(jié)點(diǎn)完成檢測,從而去除所有冗余節(jié)點(diǎn)。

基于上述步驟,本文提出的改進(jìn)CRNP算法的整體流程如圖2所示。

圖2 基于改進(jìn)CRNP算法的主節(jié)點(diǎn)配置流程Fig.2 Master node configuration flow chart based on improved CRNP algorithm

3 基于貪婪策略的主從節(jié)點(diǎn)協(xié)調(diào)配置

基于已有主節(jié)點(diǎn)的配置結(jié)果,為實(shí)現(xiàn)對已有節(jié)點(diǎn)和擴(kuò)展節(jié)點(diǎn)的協(xié)調(diào)配置,提出基于貪婪策略的主從節(jié)點(diǎn)協(xié)調(diào)配置方法,即先通過CRNP算法求解主節(jié)點(diǎn)位置,再通過貪婪策略對擴(kuò)展從節(jié)點(diǎn)和補(bǔ)充主節(jié)點(diǎn)的協(xié)調(diào)配置。貪婪策略的主要思路為:①確定問題的最優(yōu)子結(jié)構(gòu);②設(shè)計迭代方式;③在每一次迭代時,選擇局部的最優(yōu)解;④通過迭代,將局部最優(yōu)解演化為全局最優(yōu)解。基于該思路,算法的輸入為:需要擴(kuò)展部署的從節(jié)點(diǎn)數(shù)量ns,目前已有的物聯(lián)網(wǎng)絡(luò)節(jié)點(diǎn)集合Vs,Vm和Vr以及從節(jié)點(diǎn)的預(yù)部署節(jié)點(diǎn)位置集合Ls。具體配置要求滿足:①不能更改原有節(jié)點(diǎn)的位置;②盡可能少地引入新的主節(jié)點(diǎn)。

為盡可能減少數(shù)據(jù)通信延遲,需減少數(shù)據(jù)傳輸過程中的轉(zhuǎn)發(fā)次數(shù)。顯然,如果在與根節(jié)點(diǎn)最近主節(jié)點(diǎn)的近鄰區(qū)域部署從節(jié)點(diǎn),則新部署的從節(jié)點(diǎn)會具有最小的數(shù)據(jù)轉(zhuǎn)發(fā)次數(shù)。因此,每一次從節(jié)點(diǎn)的部署需要選擇到根節(jié)點(diǎn)具有最小跳數(shù)的主節(jié)點(diǎn),再從這些被選中節(jié)點(diǎn)中,挑選一個滿足通信質(zhì)量要求的近鄰位置(從Ls中選擇)來部署從節(jié)點(diǎn)。

到根節(jié)點(diǎn)跳數(shù)最小的主節(jié)點(diǎn)集合可表示為

Vmmin={?vm:Vm|arg minH(p(vm,vr))}

(10)

式中H(vm,vr)是vm到vr的數(shù)據(jù)轉(zhuǎn)發(fā)跳數(shù)。

從節(jié)點(diǎn)的整個部署過程是一個迭代過程,令Vsnew(i)為第i次迭代的新部署從節(jié)點(diǎn)集合,則

(11)

(12)

(13)

綜上,新部署從節(jié)點(diǎn)的迭代求解過程為

(14)

基于上述算法模型,構(gòu)建基于貪婪策略的主從節(jié)點(diǎn)協(xié)調(diào)配置流程圖,如圖3所示。

圖3 基于貪婪策略的主從協(xié)調(diào)配置流程Fig.3 Master-slave node coordination configuration flow chart based on greedy strategy

基于貪婪策略的主從節(jié)點(diǎn)協(xié)調(diào)配置流程具體如下。

步驟1輸入需要部署的從節(jié)點(diǎn)數(shù)量ns、當(dāng)前網(wǎng)絡(luò)節(jié)點(diǎn)集合Vs、Vm和Vr以及從節(jié)點(diǎn)的預(yù)部署節(jié)點(diǎn)位置集合Ls。

步驟2對Vm中的所有節(jié)點(diǎn)按照到跟節(jié)點(diǎn)的跳數(shù)大小進(jìn)行分組,并按照升序排序。

步驟3依次從跳數(shù)最小的分組中選擇主節(jié)點(diǎn),在選中的主節(jié)點(diǎn)附近搜索與之近鄰且滿足通信質(zhì)量要求的CDL位置,選擇這個位置進(jìn)行從節(jié)點(diǎn)的部署。

步驟4檢測是否完成所有從節(jié)點(diǎn)的部署,如果完成,則跳至步驟7,否則跳至步驟5。

步驟5檢測現(xiàn)有的主節(jié)點(diǎn)是否還有近鄰的CDL,如果有,則跳至步驟2進(jìn)行下一次迭代,否則跳至步驟6。

步驟7算法結(jié)束,輸出新部署的主節(jié)點(diǎn)集合和從節(jié)點(diǎn)集合的所有位置。

4 案例研究

本文以中國西部科技創(chuàng)新港智能制造創(chuàng)新中心的智能制造單元——數(shù)字孿生制造單元(DTMC)[17,24]為應(yīng)用對象進(jìn)行案例驗證。該單元主要用于微型渦噴發(fā)動機(jī)葉輪等復(fù)雜零件的智能加工,由數(shù)控加工中心、數(shù)控銑床、工業(yè)機(jī)器人、工業(yè)AGV、倉儲貨架、邊緣服務(wù)器等裝備以及數(shù)字孿生系統(tǒng)等構(gòu)成。該單元通過對邊緣感知節(jié)點(diǎn)、計算節(jié)點(diǎn)和物聯(lián)網(wǎng)絡(luò)的部署和計算,利用邊-云協(xié)同實(shí)現(xiàn)加工過程的視頻監(jiān)測、零件加工狀態(tài)追蹤、能耗統(tǒng)計、產(chǎn)量統(tǒng)計以及虛實(shí)同步等。制造單元的主要設(shè)備布局如圖4所示。以單元的邊緣服務(wù)器為原點(diǎn),建立物聯(lián)網(wǎng)絡(luò)坐標(biāo)系,測量得到相關(guān)設(shè)備的具體位置坐標(biāo),如表1所示。依據(jù)該坐標(biāo),可以明確傳感器等從節(jié)點(diǎn)和邊緣計算主節(jié)點(diǎn)的可部署區(qū)域和禁止部署區(qū)域,從而確定預(yù)定義的候選部署位置集合Lm。

圖4 數(shù)字孿生制造單元主要設(shè)備布局Fig.4 Equipment layout for DTMC

4.1 數(shù)字孿生制造單元邊緣主節(jié)點(diǎn)配置實(shí)例

為保證主節(jié)點(diǎn)電源供應(yīng),且考慮到制造單元的部署區(qū)域,只能在預(yù)定義節(jié)點(diǎn)集中選擇滿足要求的位置部署相應(yīng)的主節(jié)點(diǎn)。依據(jù)表1,制造單元的設(shè)備布局位置、禁止部署區(qū)域(紅色)、可部署區(qū)域(綠色)如圖5所示。禁止部署區(qū)域主要考慮機(jī)床占用,可部署區(qū)域主要考慮電源供應(yīng)。

表1 制造單元設(shè)備坐標(biāo)信息

圖5 數(shù)字孿生制造單元主節(jié)點(diǎn)可部署區(qū)域示意Fig.5 Deployable area of master nodes in DTMC

為保證通信質(zhì)量和時延,限制設(shè)備的最小接收率ψmin為93%、數(shù)據(jù)轉(zhuǎn)發(fā)的最大跳數(shù)為5,其他參數(shù)如表2所示。CDL位置可在部署區(qū)域內(nèi)進(jìn)行隨機(jī)選擇,每個區(qū)域的CDL節(jié)點(diǎn)數(shù)目設(shè)置為100。

經(jīng)測試,制造單元現(xiàn)場設(shè)備的單跳網(wǎng)絡(luò)傳輸延遲τ0約為1.5 ms,則網(wǎng)絡(luò)最大傳輸延遲限制為τmax=γmaxτ0=7.5 ms。進(jìn)行20組實(shí)驗,得到主節(jié)點(diǎn)物聯(lián)配置的測試結(jié)果,如圖6所示。同時,為驗證配置的合理性和有效性,將本文提出的改進(jìn)的CRNP算法與最小路徑樹(shortest path tree,SPT)算法[25]、傳統(tǒng)CRNP算法進(jìn)行比對。SPT算法主要是通過確定數(shù)據(jù)轉(zhuǎn)發(fā)的最小跳數(shù)在設(shè)備節(jié)點(diǎn)與跟節(jié)點(diǎn)間形成數(shù)據(jù)通路,在節(jié)點(diǎn)選擇的過程中,不考慮其他約束條件。傳統(tǒng)CRNP算法僅考慮了跳數(shù)約束,未綜合考慮通信質(zhì)量等約束。各算法的對比結(jié)果如圖6所示?？梢钥闯?在主節(jié)點(diǎn)部署上,SPT、CRNP和改進(jìn)CRNP的平均值部署數(shù)量分別為11.1、4.2和5.1個主節(jié)點(diǎn);在傳輸延遲上,三者的平均傳輸延遲為4.69、6.35和6.22 ms;在數(shù)據(jù)包接收率方面,三者的平均接收率為91.6%、91.7%和94.2%。

表2 物聯(lián)網(wǎng)絡(luò)參數(shù)列表

(a)主節(jié)點(diǎn)數(shù)量

(b)傳輸延遲

(c)數(shù)據(jù)包接收率

(d)改進(jìn)CRNP的綜合評價指標(biāo)圖6 主節(jié)點(diǎn)物聯(lián)配置實(shí)驗測試結(jié)果及對比分析Fig.6 Experimental test results and comparison analysis of master nodes configuration

由以上測試結(jié)果可知:在主節(jié)點(diǎn)數(shù)量上,CRNP算法和改進(jìn)CRNP算法由于考慮了冗余節(jié)點(diǎn)的去除,主節(jié)點(diǎn)配置數(shù)量明顯比SPT算法的結(jié)果更少(分別減少了7和6個主節(jié)點(diǎn)),網(wǎng)絡(luò)部署成本更小;在網(wǎng)絡(luò)傳輸上,SPT算法的時延較小,但CRNP算法和改進(jìn)CRNP算法遵循了最大跳數(shù)限制,滿足時間延遲7.5 ms的實(shí)際要求;在數(shù)據(jù)包接收率上,改進(jìn)CRNP算法由于考慮最低接收率93%的限制,會得到較大的數(shù)據(jù)包接收率(分別比SPT算法和CRNP算法提升2.6%和2.5%)。綜合來看,相比SPT和CRNP算法,本文提出的改進(jìn)CRNP算法可以在滿足傳輸時間限制的條件下,得到具有較少主節(jié)點(diǎn)個數(shù)和較大數(shù)據(jù)包接收率的配置結(jié)果。同時,在改進(jìn)的CRNP算法中,為獲取最小部署成本、最小時延和最大數(shù)據(jù)包接收率,選取綜合評價指標(biāo)φ作為評估標(biāo)準(zhǔn),即

(15)

式中:ψ是配置網(wǎng)絡(luò)最大數(shù)據(jù)包接收率;τ是配置網(wǎng)絡(luò)最大傳輸延遲;nm是主節(jié)點(diǎn)數(shù)量。

依據(jù)圖6(d),選取具有φ最大值的第3組實(shí)驗(nm=5,τ=6.0 ms,ψ=94.5%)作為最終配置結(jié)果,此時各主節(jié)點(diǎn)的坐標(biāo)及實(shí)際部署結(jié)果如圖7所示。

(a)單元主節(jié)點(diǎn)配置坐標(biāo)示意

(b)單元主節(jié)點(diǎn)部署結(jié)果示意圖7 基于第3組的主節(jié)點(diǎn)配置坐標(biāo)和部署結(jié)果Fig.7 Configuration coordinates and actual deployment results from the 3rd experiment

4.2 數(shù)字孿生制造單元主從節(jié)點(diǎn)協(xié)調(diào)配置實(shí)例

為獲取AGV實(shí)時位置、追蹤工件狀態(tài)、監(jiān)測設(shè)備能耗,在制造單元內(nèi)需擴(kuò)展4個UWB位置傳感器、2個RFID傳感器和4個能耗監(jiān)測傳感器。各傳感器節(jié)點(diǎn)作為物聯(lián)網(wǎng)絡(luò)從節(jié)點(diǎn),由于所在設(shè)備和功能區(qū)域部署空間限制,需要在指定的區(qū)域內(nèi)進(jìn)行部署,故設(shè)定RFID、UWB和能耗傳感器的部署半徑分別為60、30和40 cm,具體可部署區(qū)域如表3所示。

為驗證方法的有效性,使用貪婪策略和隨機(jī)策略兩種方法進(jìn)行對比。在貪婪策略中,首先按照改進(jìn)CRNP算法進(jìn)行初始主節(jié)點(diǎn)配置,再使用基于貪婪策略的配置算法進(jìn)行主從節(jié)點(diǎn)的協(xié)調(diào)配置;在隨機(jī)策略中,首先在區(qū)域內(nèi)隨機(jī)選擇位置部署從節(jié)點(diǎn),再由改進(jìn)CRNP算法進(jìn)行主節(jié)點(diǎn)的物聯(lián)配置。兩組方法共用同一組的CDL節(jié)點(diǎn)集,其網(wǎng)絡(luò)參數(shù)與表2保持一致。實(shí)驗測試結(jié)果如圖8所示。

從圖8可以看出:在主節(jié)點(diǎn)部署數(shù)量上,隨機(jī)策略和貪婪策略平均為6.95和5.7;在傳輸延遲上,二者的平均傳輸延遲分別為6.01和5.2 ms;在數(shù)據(jù)包接收率方面,二者的平均值為94.1%和90.4%。由于貪婪策略更充分地運(yùn)用了網(wǎng)絡(luò)中已有的邊緣設(shè)備,因此在配置數(shù)量方面相比于隨機(jī)策略可以配置更少的主節(jié)點(diǎn)(少部署1.25個主節(jié)點(diǎn))。同時,由于貪婪策略優(yōu)先選擇離根節(jié)點(diǎn)最近的主節(jié)點(diǎn)進(jìn)行配置,因此鏈路的傳輸延遲更低(比隨機(jī)策略低0.9 ms)。但是,相比于隨機(jī)策略,貪婪策略因主節(jié)點(diǎn)數(shù)量少和節(jié)點(diǎn)間密度較低,導(dǎo)致協(xié)調(diào)配置的網(wǎng)絡(luò)通信質(zhì)量(數(shù)據(jù)包接收率)相對較低。在貪婪策略下,依據(jù)圖8(d)中φ的計算結(jié)果,選取具有φ最大值的第17組實(shí)驗(nm=5,τ=5.16 ms,ψ=90.44%)作為最終結(jié)果,各從節(jié)點(diǎn)在網(wǎng)絡(luò)中的配置坐標(biāo)和部署結(jié)果如圖9所示。

表3 數(shù)字孿生制造單元從節(jié)點(diǎn)可部署區(qū)域位置

(a)主節(jié)點(diǎn)部署數(shù)量

(b)傳輸延遲

(c)數(shù)據(jù)包接收成功率

(d)改進(jìn)CRNP的綜合評價指標(biāo)圖8 從節(jié)點(diǎn)配置實(shí)驗測試結(jié)果及對比分析Fig.8 Experimental test results and comparison analysis of slave node configuration

(a)單元主從節(jié)點(diǎn)協(xié)調(diào)配置坐標(biāo)示意

(b)主從節(jié)點(diǎn)協(xié)調(diào)部署結(jié)果示意圖9 基于第17組的主從節(jié)點(diǎn)協(xié)調(diào)配置坐標(biāo)和部署結(jié)果Fig.9 Coordinated configuration coordinates and actual deployment results from the 17th experiment

5 結(jié) 論

本文以智能制造單元為研究對象,結(jié)合邊-云協(xié)同框架構(gòu)建了邊緣物聯(lián)網(wǎng)絡(luò)模型,提出了基于改進(jìn)CRNP算法的邊緣主節(jié)點(diǎn)配置方法和基于貪婪策略的主從節(jié)點(diǎn)協(xié)調(diào)配置方法,結(jié)果表明:

(1)對已有從節(jié)點(diǎn)的主節(jié)點(diǎn)配置、改進(jìn)CRNP算法的配置方法可以在滿足時延約束的前提下減少主節(jié)點(diǎn)數(shù)量,提升數(shù)據(jù)包接收率;

(2)對已有主節(jié)點(diǎn)的主從節(jié)點(diǎn)進(jìn)行擴(kuò)展性配置,結(jié)合CRNP和貪婪策略的協(xié)調(diào)配置方法,可以減少主節(jié)點(diǎn)配置數(shù)量,降低傳輸延遲;

(3)在物聯(lián)網(wǎng)絡(luò)多節(jié)點(diǎn)配置中,改進(jìn)CRNP算法和貪婪策略的提出和引入可以提供低成本、低時延和高可靠性的底層物聯(lián)配置方案,從而為智能制造產(chǎn)線/單元邊-云協(xié)同的實(shí)現(xiàn)或改進(jìn)提供基礎(chǔ)支撐。