梁玉珠 梅雅欣 楊 毅 馬 櫻 賈維嘉 王 田

1(華僑大學(xué)計算機科學(xué)與技術(shù)學(xué)院 福建廈門 361021) 2(數(shù)據(jù)挖掘與智能推薦福建省高校重點實驗室(廈門理工學(xué)院) 福建廈門 361024) 3(智慧城市物聯(lián)網(wǎng)國家重點實驗室(澳門大學(xué)) 澳門 999078)(cs_yuzhuliang@163.com)

物聯(lián)網(wǎng)有著極其廣泛的應(yīng)用場景，包括智慧城市、工業(yè)物聯(lián)網(wǎng)、健康物聯(lián)網(wǎng)、智能家居以及車聯(lián)網(wǎng)等［1].目前隨著傳感器及帶寬成本的大幅下滑以及云計算技術(shù)發(fā)展和通信標(biāo)準(zhǔn)的落地，物聯(lián)網(wǎng)已從最初的導(dǎo)入期發(fā)展至現(xiàn)在的成長期初期，國外第三方咨詢機構(gòu)普遍預(yù)期2016—2020年將保持25%～30%的復(fù)合增速，其中Growth Enabler and Markets預(yù)期全球物聯(lián)網(wǎng)市場在2020年達到4 570億美元，復(fù)合增速28.5%.2016年我國物聯(lián)網(wǎng)整體產(chǎn)業(yè)規(guī)模達到了9 300億元人民幣，同比增長24%，預(yù)計到2020年，市場規(guī)模將會進一步擴大到1.8萬億元.據(jù)預(yù)測，至2020年，物聯(lián)網(wǎng)的前五大下游應(yīng)用場景分別為智慧城市、工業(yè)物聯(lián)網(wǎng)、健康物聯(lián)網(wǎng)、智能家居以及車聯(lián)網(wǎng)［2].

近年來，伴隨云計算技術(shù)的快速發(fā)展，研究者提出通過云端控制傳感器網(wǎng)絡(luò)進行信息采集［3]，利用云平臺進行信息處理和存儲［4]，為不同類型的應(yīng)用提供開放、靈活、可配置的服務(wù)平臺.用戶不再需要購置或部署傳感網(wǎng)，無需關(guān)注節(jié)點的位置，可通過使用或控制云服務(wù)器提供的虛擬節(jié)點來滿足服務(wù)請求［5].虛擬節(jié)點是由物理傳感器節(jié)點組成的用戶可視節(jié)點，隨著用戶需求而創(chuàng)建，服務(wù)停止而銷毀.當(dāng)服務(wù)復(fù)雜度較高時，不同功能的虛擬節(jié)點組成虛擬節(jié)點組協(xié)作完成服務(wù).單個物理節(jié)點可以參與多個虛擬節(jié)點的組建，單個虛擬節(jié)點也可以參與多個虛擬節(jié)點組的組建，這種機制極大提高了物理節(jié)點的利用率，為傳感云服務(wù)的高效率和多樣化提供了便利.

用戶通過傳感云系統(tǒng)，足不出戶即可獲取自己所需的數(shù)據(jù).目前已有的傳感云系統(tǒng)，如商業(yè)化的Xively、開源的Nimbits以及國內(nèi)的YeeLink和阿里云IoT［6-7]，他們提供的服務(wù)不盡相同，用戶可以把自己的傳感器收集的信息上傳到系統(tǒng)，也可以選擇把自己的傳感器共享給其他用戶使用.但是傳感云系統(tǒng)同樣面臨著物聯(lián)網(wǎng)和云計算自身存在的安全問題，甚至衍生出新的安全問題，如傳感云的耦合問題.當(dāng)多用戶同時對傳感云系統(tǒng)中的同一個物理節(jié)點進行請求時，因為每個物理傳感器只有一個通信信道，同一時間不能接收多個消息，那樣會出現(xiàn)沖突.例如對于物聯(lián)網(wǎng)中的移動節(jié)點，一個用戶通過云平臺接口發(fā)出的請求是讓它向左收集收據(jù)，而另一個用戶對其發(fā)出的請求是向右收集數(shù)據(jù)，會出現(xiàn)耦合沖突.其次，多用戶獲取服務(wù)時共用同一個虛擬傳感節(jié)點，從而共用其所代表的所有物理傳感器節(jié)點，導(dǎo)致用戶對服務(wù)的反饋命令出現(xiàn)耦合.

耦合問題會帶來極大的安全隱患，耦合問題會造成用戶等待服務(wù)時間長，系統(tǒng)服務(wù)質(zhì)量低下；物理節(jié)點調(diào)度嚴重不均，降低系統(tǒng)的使用壽命；甚至?xí)?dǎo)致系統(tǒng)死鎖，導(dǎo)致系統(tǒng)無法正常運行.因此，傳感云系統(tǒng)中耦合問題不可忽視且亟待解決.一些研究者提出利用云層來管理這些傳感器節(jié)點，這種方法存在的主要問題是云層離底層較遠，這種方式往往是不及時的.還有一些研究者提出利用傳統(tǒng)的調(diào)度算法并結(jié)合啟發(fā)式算法提高資源利用率，這種方式簡單地把問題轉(zhuǎn)化為調(diào)度問題，實際上不能取得很好的效果.此外，還有一些研究者提出結(jié)合邊緣計算這一新型計算模式來研究耦合問題，但沒有給耦合問題下一個形式化的定義，且大都僅僅提出一個框架并沒有給出具體的方法來解決這個問題.基于此，本研究首先對邊緣計算這一新型計算模式進行了探索.并在邊緣層設(shè)計了2個緩存隊列，利用邊緣存儲對問題做預(yù)處理，簡化問題.并改進了KM(Kuhn-Munkres)算法，實現(xiàn)多次匹配并達到最佳匹配，以最短的時間解決耦合問題.

本文的主要貢獻包括2個方面:

1) 在傳感云中，用戶可以通過虛擬傳感器來使用傳感器，當(dāng)多個用戶或攻擊者發(fā)送大量請求同時控制一個物理傳感器時，可能導(dǎo)致耦合問題.據(jù)已有文獻調(diào)研所知，本文形式化地描述了傳感云中的耦合問題;

2) 創(chuàng)新地將邊緣計算引入到系統(tǒng)中來解決耦合問題.在邊緣層的支持下，系統(tǒng)的響應(yīng)延遲大大縮短.此外，設(shè)計了一個有效的算法，以達到用戶請求和資源節(jié)點之間的最大匹配，從而實現(xiàn)資源的最佳利用.理論和實驗結(jié)果驗證了該方法的有效性.

1 相關(guān)工作

1.1 基于云計算的耦合資源管理方法

Sharma等人［8]指出，許多調(diào)度方法是為了獲得最大的吞吐量和就緒隊列中最小等待的時間.他們提出一種基于遺傳算法的最優(yōu)調(diào)度方案，基于自適應(yīng)函數(shù)，達到最優(yōu)調(diào)度的目的.劉炳濤等人［9]提出了一種基于概率控制的新型循環(huán)隊列調(diào)度方法，相比于傳統(tǒng)的FIFO(first in first out)調(diào)度，有更好的效果.Li等人［10]首先構(gòu)建了任務(wù)模型和資源模型，并分析任務(wù)的偏好，然后用模糊聚類算法對資源進行分類.最后計算資源期望并將任務(wù)分配給不同的資源集群，從而減少資源選擇的復(fù)雜性，進而減少任務(wù)的等待時間并提高資源利用率.Tang等人［11]基于云環(huán)境提出了一種新方案.首先計算所有任務(wù)的初始調(diào)度順序，并根據(jù)異構(gòu)最早完成時間算法獲取整個完成時間和限制時間,該算法可以在低電壓和低頻率下將任務(wù)分配到空閑時隙中.Kayvanfar等人［12]提出了一個基于基礎(chǔ)設(shè)施即服務(wù)(infrastructure as a service, IaaS)的科學(xué)工作流的資源配置和調(diào)度策略，并提出基于元啟發(fā)式優(yōu)化技術(shù)算法，利用粒子群優(yōu)化，在滿足條件的基礎(chǔ)上最小化執(zhí)行時間.

1.2 基于二分圖的耦合資源調(diào)度方法

Chopra等人［13]通過在匈牙利算法中使用廣泛的聚合算子來開發(fā)新的賦值算法.基于匈牙利算法，使用有序加權(quán)平均距離(ordered weighted average distance, OWAD)算子和誘導(dǎo)OWAD算子的新過程.這種方法的主要優(yōu)點是可以在最小和最大值之間提供一個參數(shù)化的聚合算子族.陳曉旭等人［14]設(shè)計了一種迭代技術(shù)，迭代匈牙利法(iterative Hungarian method, IHM).數(shù)值結(jié)果表明：所提出的方法可以提供具有多項式復(fù)雜度的近似最優(yōu)性能.Zhang等人［15]提出了改進的Max-min任務(wù)調(diào)度算法，均衡調(diào)度最長的資源和最短的資源.Zhu等人［16]提出一個Kuhn-Munkres并行遺傳算法來解決集覆蓋問題，使用分而治之降維策略，因此采用Kuhn-Munkres并行遺傳算法來拼接在每個分區(qū)中獲得可行的解決方案以改善搜索效率.

1.3 基于邊緣計算的耦合資源管理方法

基于邊緣計算模式，一些研究者提出了相關(guān)的解決方案.在物聯(lián)網(wǎng)系統(tǒng)中，所有原始事件數(shù)據(jù)都是從傳感器上收集的，并且僅在云中處理，導(dǎo)致不必要的數(shù)據(jù)冗余和網(wǎng)絡(luò)開銷.事件和動作之間存在更緊密的耦合［17].通過基于邊緣計算的局部數(shù)據(jù)處理技術(shù)，可以降低成本，提高系統(tǒng)的整體響應(yīng)性能.De等人［18]認為物聯(lián)網(wǎng)系統(tǒng)的發(fā)展制約于物理過程和數(shù)字世界的耦合，對下一次工業(yè)革命的影響至關(guān)重要.考慮了邊緣計算范式，并擴展了一個標(biāo)準(zhǔn)兼容的通信體系結(jié)構(gòu)，以支持基于容器的編排機制.Magurawalage等人［19]介紹了一種為連接設(shè)備提供計算服務(wù)的新設(shè)想.它基于未來計算資源將與通信資源耦合的關(guān)鍵概念，用于增強用戶體驗，以及優(yōu)化基礎(chǔ)設(shè)施提供者的資源.此外，這種耦合是基于聯(lián)合/協(xié)作的資源分配算法，通過集成計算和通信服務(wù)，在網(wǎng)絡(luò)中集成硬件來實現(xiàn)的.Wang等人［20]提出虛擬節(jié)點的耦合是阻礙傳感云發(fā)展的原因之一［21].虛擬節(jié)點是由物理傳感器節(jié)點組成的用戶可視節(jié)點，隨著用戶需求而創(chuàng)建，服務(wù)停止而銷毀［22-23].文獻［24-25]提出了一種基于數(shù)據(jù)緩存隊列的擴展KM算法，使資源的利用率最大化.Gao等人［26]提出了一個貪婪算法，利用KM算法求解二部圖上的最大匹配問題，從而得到原問題的擬最優(yōu)解的有效算法［27].這些算法包括2種離線算法和一種在線算法，其中2種離線算法返回原問題的上界和下界［28-29].Li等人［30]提出將數(shù)據(jù)塊優(yōu)化放置和任務(wù)優(yōu)化調(diào)度相結(jié)合，以減少提交任務(wù)的計算延遲和響應(yīng)時間，提高用戶的體驗.其中在數(shù)據(jù)塊的最佳放置中，數(shù)據(jù)塊的放置不僅考慮了數(shù)據(jù)塊的流行程度，還考慮了存儲這些數(shù)據(jù)塊的邊緣服務(wù)器的數(shù)據(jù)存儲容量和替換率.

上述研究都是資源分配中對經(jīng)典算法進行的一些改善，采用不同的分配策略，加入不同參數(shù)，結(jié)合啟發(fā)式算法或基于邊緣計算模式等進行處理.然而在傳感云耦合問題上，上述研究提出的方案都無法有效解決這個問題.其主要原因有：沒有足夠的信息預(yù)測傳感云系統(tǒng)的實時需求，結(jié)合啟發(fā)式算法不能很好的解決問題，且增加了時間復(fù)雜度.其次，調(diào)度最長或者最短的資源可能會造成系統(tǒng)死鎖，且這種資源也不一定是最緊急的資源.此外，以上方法最終完成的匹配都是一對一的匹配，而在這個問題上每一次匹配是允許出現(xiàn)一對多的情況，因為同一時間一個用戶可以使用多個資源.因此如何對現(xiàn)有的資源管理方法進行改進并結(jié)合邊緣存儲的思想提出復(fù)雜度低、效率高的低耦合算法以提升傳感云系統(tǒng)的各項指標(biāo)來擴大其應(yīng)用范圍是一個亟待解決的問題.

2 耦合問題

2.1 問題定義

假設(shè)傳感云系統(tǒng)中，1個用戶可以使用多個資源，而1個資源在同一時刻只能被1個用戶使用.如果同一時刻同1個資源被分配給多個用戶，這時會產(chǎn)生沖突，稱為耦合問題.即需要解決的問題是，假設(shè)有用戶集X和資源集Y，給出帶權(quán)二分圖G〈V，E〉,X∪Y=V，X∩Y=?，M〈Xi∪Yj，Eij〉是G的一個分配，使Gn+1=Gn-M；如此，直到Gn=0；在此過程中，使得n最小.假設(shè)完成調(diào)度的總時間為T，目標(biāo)即最小化T值.

2.2 耦合實例

為了讓讀者更清楚了解耦合問題，本節(jié)給出傳感云系統(tǒng)中的1個耦合實例.假設(shè)傳感云系統(tǒng)此時存在5名用戶和4類資源，每個用戶請求資源的時間片相同，均為t(單位為s).當(dāng)5名用戶同時發(fā)起資源請求時，不同請求對資源的需求不同，如圖1所示，用戶請求和資源的耦合關(guān)系如下：用戶1和用戶2的耦合資源為R1和R2，用戶2和用戶3的耦合資源為R3，用戶3～5的耦合資源為R4.

Fig.1 An illustration of the coupling problem圖1 耦合問題實例

表1給出了所有用戶請求執(zhí)行的順序，及完成所有資源請求消耗的時間.方案a是把資源R4的數(shù)據(jù)實時緩存在邊緣層(因為其被請求最多)，當(dāng)用戶發(fā)出請求時可以從邊緣層直接返回結(jié)果.用戶2和用戶3的耦合資源為R3，因此用戶2和用戶3的請求只能串行執(zhí)行.此時方案a先執(zhí)行用戶1和用戶3的請求，再執(zhí)行用戶2的請求.方案b則先并行執(zhí)行沒有耦合資源的用戶1和用戶3的請求，然后并行執(zhí)行用戶2和用戶4的請求，最后執(zhí)行用戶5的請求.方案c同樣是先并行執(zhí)行沒有耦合資源的用戶1和用戶4的請求，但是用戶2和用戶3的請求有耦合資源R3，因此用戶2和用戶3的請求只能串行執(zhí)行.方案d是順序執(zhí)行用戶的請求.從表1可以看出，方案a耗時最短，為2t.

Table 1 Comparisons for Different Methods表1 不同方法得到結(jié)果對比

3 算法設(shè)計與分析

3.1 算法設(shè)計思路

基于邊緣計算的耦合管理平臺如圖2所示.其包括基于邊緣計算的耦合管理平臺、云層和底層，云層的下方是邊緣層.傳感器網(wǎng)絡(luò)處在架構(gòu)的底層，用于收集數(shù)據(jù)，將用戶需求的數(shù)據(jù)由各處收集，上傳集合到云層中，由云服務(wù)進行整合，返回給用戶.

Fig.2 Edge-based coupling management platform圖2 基于邊緣計算的耦合管理平臺

虛擬傳感器組對于用戶來講實際上是透明的，每個虛擬傳感器由一種或多種物理傳感器組成.虛擬傳感器使得用戶可以在不考慮傳感器的物理位置的情況下應(yīng)用傳感器.邊緣層離底層的傳感器較近(底層一些計算能力較強的傳感器也可以作為邊緣節(jié)點)，可實時了解底層傳感器的狀態(tài)，可以更快地和底層交互［27-28].其中,基于邊緣層的數(shù)據(jù)緩存隊列是指利用邊緣層緩存的數(shù)據(jù)可以對問題作預(yù)處理，在緩存隊列里面的資源可以直接返回結(jié)果給用戶，降低調(diào)用物理節(jié)點的次數(shù)，減少耦合度，邊緣端也可以對云端傳送來的多個重復(fù)操作命令進行合并，進一步減少耦合度.

3.2 算法設(shè)計

首先，通過已有的研究經(jīng)驗，基于時間片思想，為代價矩陣加入權(quán)值，形成帶權(quán)二分圖.因此，由解決耦合問題成功轉(zhuǎn)化為解決非均勻服務(wù)時間的耦合問題.接著，發(fā)現(xiàn)在時間片系統(tǒng)中，絕大多數(shù)的處理時間都被浪費到系統(tǒng)的正常運轉(zhuǎn)維護當(dāng)中，即當(dāng)用戶的占用時間結(jié)束時，系統(tǒng)實際上并不需要重新分配資源，時間復(fù)雜度很大的資源調(diào)度算法此時并不需要運行.所以，在每次時間片中試圖將資源分配給原用戶，并在不成功時回滾，避免了系統(tǒng)正常運轉(zhuǎn)中對于調(diào)度算法的調(diào)用，節(jié)省了大量時間.

然后，在邊緣層設(shè)計了2個緩存隊列，緩存隊列1緩存來自云端的請求命令，并合并重復(fù)的請求命令.合并后的命令請求作為輸入傳到緩存隊列2，此隊列用于緩存底層節(jié)點的數(shù)據(jù)，當(dāng)請求的數(shù)據(jù)在緩存隊列2時，直接從緩存隊列2中返回數(shù)據(jù)到云端，進而返回給用戶.

最后，在KM算法中加入了調(diào)度完成狀態(tài)的檢測，通過遍歷的手段尋找最優(yōu)匹配結(jié)果.顯然，這個算法的最差時間復(fù)雜度極高，但在第1層循環(huán)中剔除掉了已分配資源，且此算法的最差情況只發(fā)生在調(diào)度后期矩陣極為稀疏或進程較少的情況下，故相比于算法對于調(diào)度輪次的顯著減少，其時間耗費影響并不明顯.

給出3個算法的詳細設(shè)計步驟.

算法1的輸入是資源請求矩陣(用戶和節(jié)點的調(diào)度關(guān)系)，輸出是經(jīng)命令緩存隊列處理后的代價矩陣.首先，從資源請求矩陣中獲取資源請求.然后，將資源請求放入到一個命令數(shù)組中.之后，對數(shù)組進行排序，并合并數(shù)組中的相同元素.最后，輸出合并后的命令矩陣.

算法1.命令緩存隊列算法.

輸入：代價矩陣;

輸出：經(jīng)命令緩存隊列處理后的代價矩陣.

① 從代價矩陣中獲取請求隊列;

② 請求隊列按照先來先服務(wù)的原則賦值到命令緩存數(shù)組中;

③ 排序命令緩存隊列;

④ for 每個命令 do

⑤ 合并重復(fù)命令;

⑥ end for

⑦ 輸出經(jīng)命令緩存隊列處理后的代價矩陣.

算法2給出了數(shù)據(jù)緩存隊列設(shè)計的算法.輸入是經(jīng)命令緩存隊列處理后的代價矩陣，輸出是經(jīng)數(shù)據(jù)緩存隊列處理后的代價矩陣.因為緩存隊列的大小受限，在仿真實驗中，設(shè)置霧層的緩存能力是底層傳感網(wǎng)某一刻產(chǎn)生數(shù)據(jù)量X的1/4，緩存的節(jié)點數(shù)據(jù)主要依據(jù)于節(jié)點的狀態(tài)(優(yōu)先級，剩余能量，到邊緣節(jié)點跳數(shù))，其中剩余能量和到邊緣節(jié)點的跳數(shù)是并行的影響因素，例如2個節(jié)點的優(yōu)先級和剩余能量相同，此時2個節(jié)點到邊緣節(jié)點的跳數(shù)分別為2跳和3跳，則優(yōu)先緩存跳數(shù)較小的節(jié)點數(shù)據(jù).選擇緩存節(jié)點數(shù)據(jù)之前，剩余能量和到邊緣節(jié)點的跳數(shù)比重相當(dāng).

算法2.數(shù)據(jù)緩存隊列算法.

輸入：經(jīng)命令緩存隊列處理后的代價矩陣;

輸出：經(jīng)數(shù)據(jù)緩存隊列后的代價矩陣.

①map=代價矩陣;

② 設(shè)緩存隊列大小為X/4+1;

③ formap中的每個進程 do

④ 在生成代價矩陣的同時獲取節(jié)點的狀態(tài)值(優(yōu)先級priority，剩余能量Eresidual和到邊緣節(jié)點的跳數(shù)Thop);

⑥ 對S值的大小進行排序;

⑦ 插入排序組建緩存預(yù)處理隊列;

⑧ end for

⑨ 輸出經(jīng)數(shù)據(jù)緩存隊列處理后的代價矩陣.

算法3給出基于雙緩存隊列的擴展KM算法(extended KM with double buffer queues, EKMDB).算法輸入為調(diào)度矩陣，輸出為總的時間戳以及每一種資源調(diào)用完成時算法的狀態(tài).其中，加入了對于調(diào)度完成狀態(tài)的檢測，在當(dāng)前用戶調(diào)度未完成，即當(dāng)前資源調(diào)用進程未運行完畢時算法將跳過調(diào)度分配算法，同時剔除已完成的進程.

算法3.基于雙緩存隊列的擴展KM算法.

輸入:經(jīng)數(shù)據(jù)緩存隊列后的代價矩陣;

輸出:時間戳、每輪調(diào)用的矩陣情況及資源調(diào)用情況.

① while 進程未全部結(jié)束 do

② 對map中進程遍歷，尋找完成進程并剔除，設(shè)running標(biāo)記;

③ ifrunning=1

④ 遍歷當(dāng)前分配，嘗試分配資源，分配失敗則回滾;

⑤ end if

⑥ 使用改進KM算法;

⑦ formap中的每一個資源 do

⑧ 找到還未使用資源，將還未使用資源和對應(yīng)的用戶加入匹配，退出;

⑨ end for

⑩ end while

3.3 理論分析

定理1.設(shè)計傳感云中用戶和資源的最優(yōu)調(diào)度方案是一個NP難問題.

證明.若存在一個問題p，可以被分為k個部分(k≥1且有限)，其中至少有一個部分可以由一個已知的NP-Hard問題歸約而來，則p為NP-Hard問題.

第1次分治：通過采用時間片算法，將問題轉(zhuǎn)化為在一個時間片范圍下對于二分圖Gn產(chǎn)生最優(yōu)分配Mn∈Gn，顯然，當(dāng)|Yi|=|Y|時，M為最優(yōu)分配.此次分治采用貪婪方法將問題分劃，以得出近似最優(yōu)解，此時時間片長度n近似最小.

當(dāng)max{Yi}有限時，時間片算法使子問題p1可在多項式時間O(n)中歸約為問題p.顯然，對于問題p向子問題p1的分劃是在二項式時間內(nèi)的，即子問題p1可歸約為p.

因為Yi有上界，問題p1可以視為在定上界多約束下的1-M二分圖組匹配問題，此問題為NP完全問題［22-23]，則p1為NP-Hard問題，即證p為NP-Hard問題.

證畢.

定理2.基于雙緩存隊列的擴展KM算法的時間復(fù)雜度同級于KM算法.

證明.第2次分治：對于子問題p1，采用分治的方法將其拆分成2個問題，首先，由二分圖Gn獲得最優(yōu)匹配Mn，然后利用剩余資源檢測算法提高剩余資源的利用率，獲得了2個子問題p2和p3.

對于問題p2，通過采用了Munkres對于KM算法的改進算法，其時間復(fù)雜度可以估計為

O(p2)=O(|X|2|Y|).

(1)

對于問題p3，通過對剩余資源的類冒泡排序(在單個時間片下實際體現(xiàn)為最小值獲取)獲取最優(yōu)分配方案，顯然，當(dāng)n有限時，此問題為時間復(fù)雜度為O(n3)的P類問題，即：

O(p3)=O(n3)=O(p2).

(2)

證畢.

定理3.基于雙緩存隊列的擴展KM算法可以最大化資源利用率.

證明.如圖3所示，圖3的粗線(紅線)為KM算法調(diào)用1次所得到的結(jié)果.即U1→R5，U2→R1，U3→R2.顯然，資源R3仍可以被繼續(xù)調(diào)度，出現(xiàn)了資源浪費.此時的資源利用率并非100%.

通過遍歷的手段尋找剩余資源，當(dāng)檢測到資源有R3空閑時，將其分配給用戶U1，提高了資源利用率.

證畢.

Fig.3 Maximize resource utilization圖3 最大化資源利用率示意圖

4 實驗與結(jié)果

4.1 實驗環(huán)境設(shè)置

本節(jié)描述實驗的基本設(shè)置環(huán)境.實驗采用Visual studio和MATLAB R2017b作為仿真平臺.實驗采用了8種場景，用戶數(shù)從50～400，為等差數(shù)列.詳細的實驗參數(shù)如表2所示.為了進一步測試提出的算法的擴展性，發(fā)現(xiàn)資源的請求符合正態(tài)分布.故正態(tài)分布下分別進行了實驗.為了驗證方法的性能，分別與先來先服務(wù)方法(FIFO)［10]，擴展KM算法(extension of KM, EKM)［18]，僅使用底層數(shù)據(jù)緩存隊列的擴展KM算法(EKM with buffer data, EKMB)［20]進行比較.

Table 2 Experiment Parameters Descriptions表2 實驗參數(shù)描述

4.2 實驗和結(jié)果

圖4～5是不同場景下基于正態(tài)分布的平均運行輪數(shù)和資源利用率的比較.圖4(a)和圖5(a)是用戶值和資源值的比值為1/5的情況.圖4(b)和圖5(b)是用戶值和資源值的比值為2/5的情況.EKMDB算法所需的調(diào)用輪數(shù)是最小的，且較其他算法所耗費的輪數(shù)都大幅度的下降，且隨著場景越來越復(fù)雜，算法有更好的適用性，這是因為在邊緣層經(jīng)過2個緩存隊列的處理，大大簡化了代價矩陣的規(guī)模，有更快的處理速度.

Fig.4 Comparison of the number of rounds圖4 不同場景運行輪數(shù)比較

Fig.5 Comparison of the resource utilization圖5 不同場景資源利用率比較

Fig.6 Comparison of the running time圖6 不同場景運行時間比較

圖6是不同場景下基于正態(tài)分布不同算法平均運行時間的比較.其中，圖6(a)是用戶值和資源值的比值為1/5時的情況.圖6(b)是用戶值和資源值的比值為2/5時的情況.由圖6可知，當(dāng)場景的規(guī)模較小時，算法的運行時間很短，隨著場景逐漸復(fù)雜,算法的運行時間也越來越大.從結(jié)果可以看出,提出的EKMDB算法與傳統(tǒng)的KM算法相比,該算法有較低的時間復(fù)雜度,也佐證了定理2的正確性.

Fig.7 The number of rounds with different tasks圖7 運行輪數(shù)和任務(wù)數(shù)量的關(guān)系

Fig.8 The running time with different tasks圖8 運行時間和任務(wù)數(shù)量的關(guān)系

圖7和圖8顯示了任務(wù)數(shù)從1 000～64 000時運行輪數(shù)和運行時間的變化.這些結(jié)果表明：提出的算法調(diào)用輪數(shù)最少,運行時間最短.這也表明在邊緣層利用緩存隊列進行預(yù)處理有很好的性能.

5 總 結(jié)

本文研究了基于邊緣計算的傳感云系統(tǒng)低耦合控制方法.對于傳感云中的耦合問題，首先證明了轉(zhuǎn)化的問題是NP-Hard問題，基于邊緣計算和雙緩存隊列的思想，提出了基于雙緩存隊列的擴展KM算法解決這一問題.仿真結(jié)果驗證了相關(guān)理論的正確性，同時表明，該方法能有效地降低資源調(diào)度時間，提高資源利用率，該方法有效地解決了傳感云系統(tǒng)中的耦合問題.所提算法核心思想之一是在邊緣層設(shè)計了2個緩存隊列，以“空間換時間”的思想提高算法的性能，越復(fù)雜的場景，緩存隊列所占空間越大，空間復(fù)雜度越高.未來研究工作之一即在有效解決耦合問題的前提下減小算法的空間復(fù)雜度.