向朝參 程文輝 張 昭 焦賢龍 屈毓錛 陳 超 戴海鵬

1（重慶大學(xué)計(jì)算機(jī)學(xué)院 重慶 400044）

2（信息物理社會(huì)可信服務(wù)計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室（重慶大學(xué)）重慶 400044）

3（南京航空航天大學(xué)電子信息工程學(xué)院 南京 210016）

4（南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系 南京 210023）

隨著城市的不斷快速發(fā)展，城市交通問題日益嚴(yán)峻，如交通擁堵等[1].為了解決這些問題，大量智能交通系統(tǒng)（intelligent transportation systems，ITSs）被廣泛地部署，用于城市交通感知和監(jiān)控[2].例如，澳大利亞新南威爾士州構(gòu)建交通流量監(jiān)控系統(tǒng)（taffic volume viewer system,TVVS）[3]，部署超過600 個(gè)交通感知站點(diǎn).然而，由于設(shè)備故障、數(shù)據(jù)傳輸和系統(tǒng)供電等問題，感知數(shù)據(jù)缺失問題在ITSs 中普遍存在[4].例如，文獻(xiàn)[5]統(tǒng)計(jì)分析發(fā)現(xiàn)，澳大利亞TVVS 系統(tǒng)中約25%的站點(diǎn)感知數(shù)據(jù)缺失率超過60%，嚴(yán)重影響該系統(tǒng)的正常使用.因此，準(zhǔn)確實(shí)時(shí)地恢復(fù)大規(guī)模ITSs 缺失感知數(shù)據(jù)對(duì)實(shí)現(xiàn)智慧城市的智能交通至關(guān)重要.

本文提出基于邊緣智能計(jì)算的大規(guī)模交通缺失感知數(shù)據(jù)恢復(fù)系統(tǒng)，既利用大量不同交通站點(diǎn)感知數(shù)據(jù)之間的相關(guān)性，又利用部署在感知站點(diǎn)附近的邊緣節(jié)點(diǎn)強(qiáng)大的計(jì)算處理能力，從而實(shí)現(xiàn)大規(guī)模交通感知數(shù)據(jù)的精確自適應(yīng)恢復(fù).但是，要實(shí)現(xiàn)該系統(tǒng)，需要解決2 方面的挑戰(zhàn)：

1）高計(jì)算復(fù)雜性的邊緣節(jié)點(diǎn)部署.邊緣節(jié)點(diǎn)部署，既需要考慮部署在不同交通感知站點(diǎn)的成本與收益各不相同，還與交通感知數(shù)據(jù)分配策略緊密相關(guān)，從而使邊緣節(jié)點(diǎn)最優(yōu)部署問題更加復(fù)雜，在2.2節(jié)被證明是NP-hard 問題.所以，如何解決這個(gè)高計(jì)算復(fù)雜性問題以實(shí)現(xiàn)最優(yōu)部署非常具有挑戰(zhàn)性.

2）高時(shí)空動(dòng)態(tài)的感知數(shù)據(jù)相關(guān)性.交通感知數(shù)據(jù)的時(shí)空相關(guān)性具有動(dòng)態(tài)性、時(shí)變性和復(fù)雜性，經(jīng)常受道路拓?fù)?、感知站點(diǎn)位置、天氣以及社會(huì)事件等多方面因素的影響[6].因此，如何基于該動(dòng)態(tài)的、時(shí)變的、難建模的時(shí)空相關(guān)性實(shí)現(xiàn)感知數(shù)據(jù)的精確恢復(fù)非常具有挑戰(zhàn)性.進(jìn)一步地，數(shù)據(jù)之間的相關(guān)性影響各個(gè)交通感知站點(diǎn)的數(shù)據(jù)分配策略，如當(dāng)感知數(shù)據(jù)之間的相關(guān)性較差時(shí)，需要增加邊緣節(jié)點(diǎn)的分配數(shù)據(jù)量，以保證數(shù)據(jù)恢復(fù)的魯棒性.但是感知數(shù)據(jù)之間的高時(shí)空動(dòng)態(tài)相關(guān)性使保證感知數(shù)據(jù)恢復(fù)精度的魯棒性非常困難.

為了解決上述2 個(gè)挑戰(zhàn)，本文提出基于邊緣智能計(jì)算的城市交通感知數(shù)據(jù)自適應(yīng)恢復(fù)系統(tǒng)，主要包括2 部分：

1）具有理論下界的邊緣節(jié)點(diǎn)次優(yōu)部署分配.針對(duì)挑戰(zhàn)1，首先，通過問題等價(jià)轉(zhuǎn)化，解耦邊緣節(jié)點(diǎn)部署和感知數(shù)據(jù)分配之間的復(fù)雜關(guān)系.然后，通過理論證明該問題具有非負(fù)的、單調(diào)的和子模的目標(biāo)函數(shù)，以及p-獨(dú)立系統(tǒng)的約束條件.最后，基于該問題的性質(zhì)分析，提出基于子模理論的邊緣節(jié)點(diǎn)次優(yōu)部署算法，能夠在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)獲得具有理論下界的近似最優(yōu)解.

2）基于低秩理論的感知數(shù)據(jù)自適應(yīng)精確恢復(fù).針對(duì)挑戰(zhàn)2，首先，基于實(shí)際交通感知數(shù)據(jù)集，對(duì)感知數(shù)據(jù)進(jìn)行時(shí)空維度的低秩分析；然后，基于該分析結(jié)果，提出基于低秩理論的時(shí)空維度聯(lián)合數(shù)據(jù)恢復(fù)算法；最后，針對(duì)感知數(shù)據(jù)相關(guān)性的高時(shí)空動(dòng)態(tài)變化，提出基于奇異值分解的感知數(shù)據(jù)非缺失下限估計(jì).基于該下限估計(jì)反饋，自適應(yīng)地調(diào)整各交通感知站點(diǎn)的感知數(shù)據(jù)分配比例，以保證感知數(shù)據(jù)的精確恢復(fù)，從而提高系統(tǒng)數(shù)據(jù)恢復(fù)性能的魯棒性.

綜上所述，本文主要具有3 方面的創(chuàng)新和貢獻(xiàn)：

1）提出基于邊緣智能計(jì)算的城市交通感知數(shù)據(jù)自適應(yīng)恢復(fù)系統(tǒng)，既利用基于子模優(yōu)化理論的邊緣計(jì)算，又利用基于低秩理論的智能計(jì)算，還基于非缺失下限估計(jì)反饋，自適應(yīng)地調(diào)整交通站點(diǎn)感知數(shù)據(jù)分配比例，從而實(shí)現(xiàn)交通感知數(shù)據(jù)的“閉環(huán)”處理，提高系統(tǒng)的魯棒性.

2）針對(duì)邊緣節(jié)點(diǎn)部署NP-hard 問題，基于子模優(yōu)化理論，通過問題解耦轉(zhuǎn)化和性質(zhì)分析，提出近似比為的邊緣節(jié)點(diǎn)次優(yōu)部署分配算法，其中cjs表示任意一個(gè)邊緣節(jié)點(diǎn)es部署在任意一個(gè)感知站點(diǎn) λj處的成本.同時(shí)，提出缺失交通感知數(shù)據(jù)的自適應(yīng)恢復(fù)算法，利用基于低秩理論的感知數(shù)據(jù)恢復(fù)，以及基于奇異值分解的非缺失下限估計(jì)反饋調(diào)整，實(shí)現(xiàn)缺失感知數(shù)據(jù)的自適應(yīng)精確恢復(fù).

3）基于澳大利亞600 個(gè)交通感知站點(diǎn)1 年的實(shí)際感知數(shù)據(jù)構(gòu)建原型系統(tǒng)，并基于該系統(tǒng)進(jìn)行全面且深入的實(shí)驗(yàn)評(píng)估.結(jié)果表明，所提算法的邊緣節(jié)點(diǎn)部署性能達(dá)到最優(yōu)性能的90%以上，缺失數(shù)據(jù)恢復(fù)精度比3 種方法至少提高43.8%.同時(shí)，自適應(yīng)數(shù)據(jù)恢復(fù)精度平均提高40.3%.

1 相關(guān)工作

為保障智能交通系統(tǒng)的正常運(yùn)行，促進(jìn)智慧城市的進(jìn)一步發(fā)展，大量工作開始致力于研究城市交通感知數(shù)據(jù)的精確恢復(fù).因此本文提出了基于邊緣智能計(jì)算的城市交通感知數(shù)據(jù)自適應(yīng)恢復(fù)系統(tǒng)，所以下面將主要介紹交通感知數(shù)據(jù)恢復(fù)和邊緣節(jié)點(diǎn)部署方面的研究工作.

1）ITSs 交通感知數(shù)據(jù)恢復(fù).智能交通系統(tǒng)在城市化進(jìn)程不斷深入的當(dāng)下起著越來越重要的作用，然而交通感知數(shù)據(jù)的普遍缺失卻極大地影響了ITSs的效用，為此越來越多的研究工作開始致力于交通感知數(shù)據(jù)的精確恢復(fù).例如，文獻(xiàn)[7]利用真實(shí)數(shù)據(jù)和仿真數(shù)據(jù)，同時(shí)結(jié)合生成式對(duì)抗網(wǎng)絡(luò)對(duì)交通感知數(shù)據(jù)進(jìn)行恢復(fù).文獻(xiàn)[8]中以高速公路交通數(shù)據(jù)為例，提出了一種數(shù)據(jù)融合方法，通過挖掘感知數(shù)據(jù)內(nèi)在特性以重構(gòu)缺失數(shù)據(jù).文獻(xiàn)[9]中通過將交通感知數(shù)據(jù)恢復(fù)問題建模為一個(gè)高維張量補(bǔ)全問題，并采用奇異值分解來進(jìn)一步了解感知數(shù)據(jù)的內(nèi)在聯(lián)系，以達(dá)到缺失數(shù)據(jù)補(bǔ)全的目的.文獻(xiàn)[4]將城市交通感知區(qū)域建模成一個(gè)具有時(shí)空相關(guān)性的張量，同時(shí)結(jié)合交通感知數(shù)據(jù)的城市特性完成對(duì)缺失數(shù)據(jù)的填補(bǔ).文獻(xiàn)[10]中提出一種聯(lián)合空間多核學(xué)習(xí)和非負(fù)矩陣分解的策略機(jī)制，去補(bǔ)全缺失感知數(shù)據(jù).該機(jī)制充分考慮了多感知區(qū)域間多層面的相關(guān)性，使得其能獲得一個(gè)較好的數(shù)據(jù)恢復(fù)精度.有別于文獻(xiàn)[4,7-10]的工作，本文提出基于邊緣智能計(jì)算的城市交通感知數(shù)據(jù)自適應(yīng)恢復(fù)系統(tǒng)，實(shí)現(xiàn)了交通感知數(shù)據(jù)的自適應(yīng)動(dòng)態(tài)精確恢復(fù).

2）邊緣計(jì)算中的節(jié)點(diǎn)部署.由于感知數(shù)據(jù)恢復(fù)存在規(guī)模龐大和計(jì)算密集等問題，本文提出通過邊緣計(jì)算來解決這一難題，充分利用邊緣服務(wù)器強(qiáng)大的計(jì)算能力來完成對(duì)感知數(shù)據(jù)及時(shí)精準(zhǔn)的恢復(fù).目前，也有很多其他關(guān)于邊緣計(jì)算應(yīng)用的研究.例如，文獻(xiàn)[11-12]中提出利用云端服務(wù)器和邊緣節(jié)點(diǎn)協(xié)同處理任務(wù)；文獻(xiàn)[13]中研究多個(gè)邊緣節(jié)點(diǎn)協(xié)作優(yōu)化任務(wù)卸載和服務(wù)緩存，以達(dá)到降低整體任務(wù)時(shí)延的目的；文獻(xiàn)[14]中提出利用邊緣計(jì)算來存儲(chǔ)整理車輛的道路感知信息，以此為無人駕駛汽車提供及時(shí)準(zhǔn)確的道路信息，確保駕駛的安全；文獻(xiàn)[15]中研究了云服務(wù)和端服務(wù)之間通過事件機(jī)制進(jìn)行的服務(wù)適配，并結(jié)合圖論和排隊(duì)論方法實(shí)現(xiàn)了服務(wù)的平均響應(yīng)時(shí)間最小.此外，關(guān)于邊緣節(jié)點(diǎn)的相關(guān)研究也有很多，例如文獻(xiàn)[16-17]中研究了關(guān)于節(jié)點(diǎn)部署成本最小的問題，文獻(xiàn)[18-20]中也研究了在站點(diǎn)容量約束和帶寬約束下最小化邊緣節(jié)點(diǎn)部署成本的問題.本文提出的部署方案主要為處理缺失感知數(shù)據(jù)而提出，對(duì)每個(gè)邊緣節(jié)點(diǎn)都有一定的數(shù)據(jù)上傳量下限要求.因此，前人的研究成果并不適用于本文的研究.雖然文獻(xiàn)[5]中提出了一種邊緣節(jié)點(diǎn)部署和數(shù)據(jù)恢復(fù)算法，但是沒有考慮數(shù)據(jù)恢復(fù)結(jié)果對(duì)于邊緣節(jié)點(diǎn)處的反饋.與該工作不同，本文提出一種基于邊緣智能計(jì)算的缺失感知數(shù)據(jù)自適應(yīng)恢復(fù)系統(tǒng)，基于恢復(fù)結(jié)果的反饋，自適應(yīng)調(diào)整恢復(fù)過程，從而保證數(shù)據(jù)恢復(fù)精度，提高系統(tǒng)恢復(fù)的魯棒性.

2 系統(tǒng)模型和問題建模

2.1 系統(tǒng)模型

為解決大規(guī)模ITSs 系統(tǒng)的感知數(shù)據(jù)缺失問題，本文提出基于邊緣智能計(jì)算的大規(guī)模交通缺失感知數(shù)據(jù)動(dòng)態(tài)自適應(yīng)恢復(fù)系統(tǒng)模型架構(gòu)，主要包括交通感知站點(diǎn)、邊緣節(jié)點(diǎn)和云服務(wù)器.

1）交通感知站點(diǎn).在智能交通系統(tǒng)中，交通感知站點(diǎn)被部署在城市的各條道路或其交叉路口上，感知和監(jiān)測(cè)道路實(shí)時(shí)的交通信息，如車流量、車速等[21].假設(shè)有N個(gè)站點(diǎn)，用λi表 示第i個(gè)站點(diǎn)，其 中i∈{1,2,…,N}.此外，用wi表示λi的感知數(shù)據(jù)規(guī)模大 小.表1給出本文主要數(shù)學(xué)符號(hào)說明.

2）邊緣節(jié)點(diǎn).所有交通感知數(shù)據(jù)被傳送至邊緣節(jié)點(diǎn)進(jìn)行缺失數(shù)據(jù)恢復(fù)處理.考慮到部署的便捷性及部署成本問題，邊緣節(jié)點(diǎn)將被部署在交通感知站點(diǎn)處.假設(shè)共有S個(gè)邊緣節(jié)點(diǎn)，用es表 示第s個(gè)邊緣節(jié)點(diǎn)，其中s∈{1,2,…,S}.用xjs=1或 0 表示邊緣節(jié)點(diǎn)es是否被部署到交通站點(diǎn)λj處，xjs=1表示被部署，否則xjs=0 .每個(gè)節(jié)點(diǎn)的部署需耗費(fèi)一定成本，用cjs表示邊緣節(jié)點(diǎn)es部 署到交通站點(diǎn) λj的成本.不同的邊緣節(jié)點(diǎn)有不同的計(jì)算存儲(chǔ)容量，用ds表示es的計(jì)算存儲(chǔ)容量.此外，用yij表示交通站點(diǎn) λi傳 輸?shù)讲渴鹪?λj處 邊緣節(jié)點(diǎn)的數(shù)據(jù)比例，即yij∈[0,1].為方便處理，在進(jìn)行缺失數(shù)據(jù)恢復(fù)時(shí)，邊緣節(jié)點(diǎn)首先將各個(gè)站點(diǎn)上傳的感知數(shù)據(jù)整合成一個(gè)含缺失數(shù)據(jù)的矩陣，即缺失矩陣，用Mjs表示 λj處邊緣節(jié)點(diǎn)es整合的缺失矩陣.同時(shí)，為保證恢復(fù)精度，缺失矩陣的元素缺失程度不能太大，即傳送到邊緣節(jié)點(diǎn)的非缺失感知數(shù)據(jù)量需滿足一定下限，用mj表示 λj處邊緣節(jié)點(diǎn)整合矩陣的非缺失下限.特別地，矩陣非缺失下限值與矩陣的秩大小密切相關(guān)，具體見3.2.2 節(jié).此外，由于外界因素，如環(huán)境、天氣、節(jié)假日等的影響，感知數(shù)據(jù)矩陣的秩也將隨之變化，進(jìn)一步地將影響到數(shù)據(jù)最后的恢復(fù)精度.為保證在變動(dòng)的外界因素下，缺失數(shù)據(jù)的恢復(fù)精度依然能滿足一定要求，邊緣節(jié)點(diǎn)將依據(jù)恢復(fù)結(jié)果計(jì)算相應(yīng)非缺失下限值，并基于非缺失下限值調(diào)整各交通站點(diǎn)的感知數(shù)據(jù)分配比例，以保證感知數(shù)據(jù)的自適應(yīng)精確恢復(fù).此外，為提高恢復(fù)效率，邊緣節(jié)點(diǎn)應(yīng)能同時(shí)處理盡可能多的感知數(shù)據(jù).

Table 1 Main Mathmatics Notations Description表1 主要數(shù)學(xué)符號(hào)的說明

3）云服務(wù)器.云服務(wù)器在整個(gè)系統(tǒng)中主要有2個(gè)功能：①管理和控制邊緣節(jié)點(diǎn).連接所有邊緣節(jié)點(diǎn)，并靈活高效地控制和管理各個(gè)交通感知站點(diǎn)和邊緣節(jié)點(diǎn)之間的數(shù)據(jù)傳輸和調(diào)度[22].具體地，首先，所有邊緣節(jié)點(diǎn)根據(jù)恢復(fù)結(jié)果，計(jì)算非缺失下限值，并將該值發(fā)送至云服務(wù)器；然后，云服務(wù)器根據(jù)各個(gè)邊緣節(jié)點(diǎn)上傳的非缺失下限值重新計(jì)算感知數(shù)據(jù)分配方案，并反饋回各個(gè)邊緣節(jié)點(diǎn)；最后，邊緣節(jié)點(diǎn)通知各個(gè)交通感知站點(diǎn)新的感知數(shù)據(jù)分配比例.②復(fù)雜的大規(guī)模數(shù)據(jù)處理[23-25].當(dāng)邊緣節(jié)點(diǎn)恢復(fù)缺失感知數(shù)據(jù)之后，利用完整的交通感知數(shù)據(jù)進(jìn)一步地進(jìn)行復(fù)雜的大規(guī)模數(shù)據(jù)分析和挖掘，如基于深度學(xué)習(xí)的交通感知大數(shù)據(jù)態(tài)勢(shì)分析和挖掘等[26-27].

2.2 問題建模

基于2.1 節(jié)所述的系統(tǒng)模型，本文研究的問題主要包括：1）如何在部署成本約束下設(shè)計(jì)邊緣節(jié)點(diǎn)部署方案，提高部署性能使其能更好地服務(wù)感知數(shù)據(jù)恢復(fù)，即能同時(shí)處理盡可能多的感知數(shù)據(jù).2）如何基于邊緣節(jié)點(diǎn)部署實(shí)現(xiàn)感知數(shù)據(jù)的動(dòng)態(tài)自適應(yīng)恢復(fù).

1）子問題P1——邊緣節(jié)點(diǎn)的次優(yōu)部署.已知邊緣節(jié)點(diǎn)的計(jì)算存儲(chǔ)容量 {ds|s∈{1,2,…,S}}和交通感知站點(diǎn)的感知數(shù)據(jù)規(guī)模 {wi|i∈{1,2,…,N}}，如何設(shè)計(jì)S個(gè)邊緣節(jié)點(diǎn)部署到N個(gè)交通感知站點(diǎn)的部署策略x=(xjs|?j∈{1,2,…,N}，?s∈{1,2,…,S})，和N個(gè)交通感知站點(diǎn)傳輸?shù)揭巡渴疬吘壒?jié)點(diǎn)的感知數(shù)據(jù)量分配方案y=(yij|?i,j∈{1,2,…,N})，以在總部署成本預(yù)算C0約束下，最大化所有部署邊緣節(jié)點(diǎn)處理總數(shù)據(jù)量，即交通感知站點(diǎn)總上傳數(shù)據(jù)量.

2）子問題P2——感知數(shù)據(jù)的自適應(yīng)恢復(fù).如何基于邊緣節(jié)點(diǎn)整合的缺失矩陣，通過矩陣中完整元素恢復(fù)缺失元素.同時(shí)基于恢復(fù)結(jié)果，估計(jì)當(dāng)前感知數(shù)據(jù)相關(guān)性程度，通過該相關(guān)性程度大小計(jì)算保證精確恢復(fù)所需的非缺失感知數(shù)據(jù)下限值，從而基于下限值調(diào)節(jié)感知站點(diǎn)上傳至各邊緣節(jié)點(diǎn)感知數(shù)據(jù)比例，達(dá)到動(dòng)態(tài)自適應(yīng)精確恢復(fù)的目的.用T表示矩陣Mjs的元素個(gè)數(shù)，用vt和分別表示該矩陣第t個(gè)元素的實(shí)際值和估計(jì)值，t∈{1,2,…,T}.因此，感知數(shù)據(jù)恢復(fù)問題可描述為：如何設(shè)計(jì)矩陣恢復(fù)函數(shù) Φt(·)，使得所有缺失感知數(shù)據(jù)的估計(jì)值與真實(shí)值之間的誤差最小，形式化表示為：

其中：式（8）表示感知數(shù)據(jù)的估計(jì)誤差，即平均絕對(duì)值誤差[30]；式（9）表示感知數(shù)據(jù)的估計(jì)恢復(fù)，Φt(Mjs)表示利用矩陣恢復(fù)函數(shù)，基于Mjs中所有非缺失數(shù)據(jù)估計(jì)其第t個(gè)元素的值.同時(shí)，為達(dá)到動(dòng)態(tài)自適應(yīng)精確恢復(fù)的目的，還需依據(jù)P2 恢復(fù)結(jié)果，更新非缺失下限值，以保證感知數(shù)據(jù)的恢復(fù)精度.

定理1.邊緣節(jié)點(diǎn)的最優(yōu)部署分配問題 P1是NPhard 問題.

證明.當(dāng)每個(gè)交通站點(diǎn)的感知數(shù)據(jù)量規(guī)模 {wi}足夠大，遠(yuǎn)大于所有邊緣節(jié)點(diǎn)的存儲(chǔ)容量上限 {ds}時(shí)，式（2）（5）可被松弛.原問題簡(jiǎn)化為

將S個(gè)邊緣節(jié)點(diǎn)與N個(gè)交通站點(diǎn)的所有配對(duì)看成S×N個(gè)物品 {(j,s)|?s∈{1,2,…,S},?j∈{1,2,…,N}}，并將每個(gè)節(jié)點(diǎn)的配對(duì)集合分為一組，共S組.因此，原問題可規(guī)約為一個(gè)經(jīng)典的0-1 背包問題：已知每個(gè)物品 (j,s) 的價(jià)值和成本分別為ds和cjs,如何從每組物品中至多選擇1 個(gè)物品，使在總成本C0約束下最大化物品價(jià)值.因?yàn)樵?-1 背包問題是NP-hard 問題[31]，所以，問題 P1也是NP-hard 問題，證畢.

3 算法系統(tǒng)設(shè)計(jì)

為了解決2.2 節(jié)所述的子問題P1 和P2，本文提出基于邊緣智能計(jì)算的城市交通感知數(shù)據(jù)動(dòng)態(tài)自適應(yīng)恢復(fù)系統(tǒng).如圖1 所示，該系統(tǒng)基于交通感知站點(diǎn)中存在缺失的交通感知數(shù)據(jù)和交通感知站點(diǎn)的交通拓?fù)渚W(wǎng)絡(luò)圖，利用邊緣智能計(jì)算進(jìn)行感知數(shù)據(jù)的動(dòng)態(tài)自適應(yīng)恢復(fù)，從而得到精確完整的交通感知數(shù)據(jù).具體地，該系統(tǒng)主要包括2 個(gè)模塊：

1）具有理論下界的邊緣節(jié)點(diǎn)次優(yōu)部署（3.1 節(jié)）.首先，通過問題等價(jià)轉(zhuǎn)化，在3.1.1 節(jié)分析 P1問題的目標(biāo)函數(shù)和約束條件性質(zhì)；然后，基于理論分析結(jié)果，在3.1.2 節(jié)提出基于子模理論的邊緣節(jié)點(diǎn)次優(yōu)部署算法，在多項(xiàng)式時(shí)間內(nèi)能獲得該NP-hard 問題的具有理論下界的近似最優(yōu)解.

Fig.1 Intelligent edge computing-empowered adaptive urban traffic sensing data recovery system圖1 基于邊緣智能計(jì)算的城市交通感知數(shù)據(jù)自適應(yīng)恢復(fù)系統(tǒng)

2）基于低秩理論的感知數(shù)據(jù)自適應(yīng)恢復(fù)（3.2節(jié)）.首先，分析交通感知數(shù)據(jù)的時(shí)空維度近似低秩特性，在3.2.1 節(jié)提出基于低秩理論的交通感知數(shù)據(jù)恢復(fù)算法；然后，基于恢復(fù)結(jié)果，在3.2.2 節(jié)利用奇異值分解和矩陣自由度理論估計(jì)交通感知數(shù)據(jù)的非缺失下限，依據(jù)此下限值更新感知數(shù)據(jù)分配比例，保證感知數(shù)據(jù)的精確恢復(fù).

3.1 具有理論下界的邊緣節(jié)點(diǎn)次優(yōu)部署

3.1.1 問題性質(zhì)理論分析

1）問題等價(jià)轉(zhuǎn)化.問題P1 包含2 類決策變量，即邊緣節(jié)點(diǎn)部署決策變量x和 感知數(shù)據(jù)分配變量y.用y*(x) 表示給定邊緣節(jié)點(diǎn)部署規(guī)劃x的最優(yōu)感知數(shù)據(jù)分配方案.通過理論分析，可得引理1.

引理1.對(duì)于問題P1，如果給定邊緣節(jié)點(diǎn)部署方案，能夠在多項(xiàng)式時(shí)間內(nèi)獲得最優(yōu)的感知數(shù)據(jù)分配方案y.

證明.給定任意的邊緣節(jié)點(diǎn)部署策略x0=()，問題P1 轉(zhuǎn)化為只關(guān)于y的感知數(shù)據(jù)分配問題 P1′：

P1′是一個(gè)簡(jiǎn)單的線性規(guī)劃問題，可利用多種經(jīng)典的線性規(guī)劃方法[32]在多項(xiàng)式時(shí)間內(nèi)求得最優(yōu)解，

證畢.

用H(x,y)表示問題P1 的目標(biāo)函數(shù).因此，根據(jù)引理1，可以將H(x,y) 轉(zhuǎn)化為只關(guān)于決策變量x的目標(biāo)函數(shù)H(x,y*(x)) .進(jìn)一步地，定義集合函數(shù)G:={(j,s)|?j∈{1,2,…,N},s∈{1,2,…,S}}，A:={(j,s)|xjs=1,?j∈{1,2,…,N},s∈{1,2,…,S}},F(A):=H(x,y*(x)).因此，可將問題P1 等價(jià)轉(zhuǎn)化為集合函數(shù)優(yōu)化問題 P1′′：

其中 1l(·)表示指示函數(shù).

2）問題性質(zhì)分析.下面基于定義1 和定義2 分別分析問題 P1′′的目標(biāo)函數(shù)性質(zhì)（如引理2）和約束條件性質(zhì)（如引理3）.

定義1.非負(fù)性、單調(diào)性和子模性[33].對(duì)于一個(gè)集合函數(shù)F(·):2R→R（R 是一個(gè) 有限集），如果F(?)=0并且F(A)≥0 (?A ?R)，則集合函數(shù)F(·)是非負(fù)的；如果?A1?A2?R，F(xiàn)(A1)≤F(A2)，則F(·)是單調(diào) 的；當(dāng)且僅當(dāng) ?A1?A2?R，?e∈RA2，F(xiàn)(A1∪{e})-F(A1)≥F(A2∪{e})-F(A2)，F(xiàn)(·) 是子模的.

引理2.P1′′的目標(biāo)函數(shù)F(A)(A ?G)是非負(fù) 的、單調(diào)的和子模的.

證明.首先，由于F(A)的物理含義是感知數(shù)據(jù)量，所以易證其是非負(fù)的和單調(diào)的.

其次，證明F(A)是子模的.根據(jù)定義1，要證其是子模的，需證明 ?A1?A2?G，?(j1,s1)∈GA2，下列不等式恒成立：

然后利用反證法可證明

具體證明：假設(shè)該結(jié)論不成立，即

因此，該不等式表明加入節(jié)點(diǎn) (j1,s1)后，A1中邊緣節(jié)點(diǎn)的感知數(shù)據(jù)量減少.然而，根據(jù)目標(biāo)函數(shù)的單調(diào)非減性可知，A1∪{(j1,s1)}中節(jié)點(diǎn)的感知數(shù)據(jù)量不會(huì)減少.因此，節(jié)點(diǎn) (j1,s1)的感知數(shù)據(jù)量增加，所以可調(diào)整節(jié) 點(diǎn) (j1,s1)的感知 數(shù)據(jù)到 A1中的邊 緣節(jié)點(diǎn).所 以A1∪{(j1,s1)}對(duì)應(yīng)的感知數(shù)據(jù)分配解不是所有最優(yōu)解中 (j1,s1)數(shù)據(jù)量最小的解.與結(jié)論的前提條件矛盾，即是 所有最優(yōu)解中 (j1,s1)數(shù)據(jù)量最小的解.所以假設(shè)不成立，原結(jié)論成立，即

進(jìn)一步地，因?yàn)?/p>

所以，

同理可證

綜上，結(jié)論1）成立.

2）證明

具體證明：假設(shè)該結(jié)論不成立，即

因此，該不等式表明 A1∪{(j1,s1)} 加入 A2A1后，節(jié)點(diǎn)(j1,s1)的 感知數(shù)據(jù)量增加.由于 A1∪{(j1,s1)}中邊緣節(jié)點(diǎn)的感知數(shù)據(jù)量在 A2A1加入前后保持不變，所以可調(diào)節(jié) (j1,s1)上 的感知數(shù)據(jù)到 A1方案中的邊緣節(jié)點(diǎn).所以，A2∪{(j1,s1)}對(duì)應(yīng)的感知數(shù)據(jù)分配解不是所有最優(yōu)解中 (j1,s1)數(shù)據(jù)量最小的解.所以假設(shè)不成立，原結(jié)論成立，即

結(jié)論2）成立.

基于上述2 個(gè)結(jié)論，可得不等式（17）成立.因此，F(xiàn)(A)是子模的.證畢.

定義2.p-獨(dú)立系統(tǒng)[34].給定一個(gè)任意有限集合 G，用 I 表示 G 的子集構(gòu)成的集合族，即 I ?2G.則集合對(duì)(G,I)被稱為獨(dú)立系統(tǒng)，當(dāng)且僅當(dāng)滿足2 個(gè)條件：①?∈I ；②如果 A ?B ∈I，則 A ∈I.

說明：I中的元素被稱為獨(dú)立集.同時(shí)，?A ?G，如果 A中的某個(gè)獨(dú)立集不是 A中的任何一個(gè)獨(dú)立集的子集，那么該獨(dú)立集被稱為 A 的基.用r(A) 和l(A)分別表示 A的最大基和最小基元素的個(gè)數(shù).對(duì)于一個(gè)任意 獨(dú)立系 統(tǒng) (G,I)和任意集合 A ?G，如果max(r(A)/l(A))≤p，則獨(dú)立系統(tǒng) (G,I)被 稱為p-獨(dú)立系統(tǒng).

引理3.式（15）（16）構(gòu)成p-獨(dú)立系統(tǒng)，且p=1+，其中cjs表示任意一個(gè)邊緣節(jié)點(diǎn)es部署在任意一個(gè)交通站點(diǎn) λj的 成本，?j∈{1,2,…,N},?s∈{1,2,…,S}.

證明.由定義2 可知原證明等價(jià)于證明 (G,Ip)構(gòu)成p-獨(dú)立系統(tǒng)，其中 G表示邊緣節(jié)點(diǎn)和交通站點(diǎn)所有可能的配對(duì)集合，Ip表示所有可行部署方案的集合.首先，顯然有 ?∈Ip.此外，對(duì)于任意2 個(gè)部署方案X,Y，若其滿足 X ?Y ∈Ip，則由于滿足問題約束條件的可行解的子集也必定滿足約束條件，所以任意可行解的子集也必為可行解.所以必有 X ∈Ip.所以，根據(jù)定義2，(G,Ip)是一個(gè)獨(dú)立系統(tǒng).

考慮任意集合 A ?G，因?yàn)?Ip是可行解集合.所以 A中獨(dú)立集都是可行解.用 A1和 A2分別表示 A中任意2 個(gè)最大可行解（即滿足全部約束已無法再加入元素），現(xiàn)如果向 A2中增加元素 (j,s)∈A1A2，就需要在 A2中拿出一些元素來滿足約束.為滿足式（15），需取出至多1 個(gè)元素.為了滿足式（16），需取出至多個(gè)元素.如此循 環(huán)直到 A2=A1.當(dāng)最差情況發(fā)生時(shí)，換入 |A1|個(gè) 元素需至多換出p|A1|個(gè)元素，即 A2中元素個(gè)數(shù)至多為 A1中 元素個(gè)數(shù)的p倍，所以，根據(jù)定義2 可得式（15）（16）構(gòu)成p-獨(dú)立系統(tǒng).

證畢.

3.1.2 基于子模理論的邊緣節(jié)點(diǎn)次優(yōu)部署算法

根據(jù)引理2 和引理3 可得，子問題P1 具有非負(fù)的、單調(diào)的、子模的目標(biāo)函數(shù)，以及p-獨(dú)立系統(tǒng)的約束條件.因此，基于文獻(xiàn)[35]的啟發(fā)，為求解子問題P1，本文提出基于子模理論的邊緣節(jié)點(diǎn)次優(yōu)部署算法.如算法1 所示.

算法1.具有理論下界的邊緣節(jié)點(diǎn)次優(yōu)部署算法.

算法1 的核心思想是在每次迭代中，貪心地選擇當(dāng)前滿足約束的、邊際效益值最大的邊緣節(jié)點(diǎn)部署方案.具體主要包含2 步：

1）添加新元素（行④⑤）.計(jì)算 GB 中所有元素邊際效益值，將其中邊際效益值最大的元素加入解集 A 中.其中，B 表示當(dāng)前加入 A中不滿足約束的元素集合.

2）剔除沖突元素（行⑥～⑩）.在每次向解集 A中添加新元素后，遍歷 GB，將當(dāng)前無法再被添加至A中的元素全添加至 B 中.當(dāng) B=G時(shí)，表明當(dāng)前已無可添加至解集 A的元素.此時(shí)得到的 A即為最終解，而后基于 A，進(jìn)一步計(jì)算邊緣部署方案x和感知數(shù)據(jù)分配方案y.

分析算法1 的時(shí)間復(fù)雜度及解最優(yōu)性，可得定理2.

定理2.算法1 能夠在多項(xiàng)式時(shí)間內(nèi)獲得近似比為的近似最優(yōu)解.

證明.基于引理2 和3，子問題 P1是具有非負(fù)、單調(diào)和子模的目標(biāo)函數(shù)及p-獨(dú)立系統(tǒng)約束的優(yōu)化問題.由文獻(xiàn)[35]可得，基于算法1，可求得近似比為1/(1+p) 的近似 最優(yōu)解.根據(jù)引 理3 得，因此，算法1 可獲得近似比為的 近似最優(yōu)解.此外，算法1 最多迭代S次，每次迭 代的時(shí) 間復(fù)雜度為O(NSΓ)，其 中，N和S分 別表示交通感知站點(diǎn)和邊緣節(jié)點(diǎn)的數(shù)量，Γ表示求解線性規(guī)劃問題 P1′的多項(xiàng)式時(shí)間耗費(fèi)[32].因此，算法1 具有多項(xiàng)式時(shí)間復(fù)雜度，即O(NS2Γ)，證畢.

3.2 基于低秩理論的感知數(shù)據(jù)自適應(yīng)恢復(fù)

3.2.1 基于低秩理論的感知數(shù)據(jù)恢復(fù)

1）基于低秩分析的問題轉(zhuǎn)化.利用實(shí)際智能交通感知數(shù)據(jù)集（詳見4.1 節(jié)），分別基于時(shí)間維度和空間維度，分析不同時(shí)間和不同站點(diǎn)交通感知數(shù)據(jù)的低秩性.首先，分析在時(shí)間維度上的低秩特性.從數(shù)據(jù)集中隨機(jī)選取4 個(gè)交通站點(diǎn)52h 的感知數(shù)據(jù)組成矩陣，并對(duì)該矩陣進(jìn)行奇異值分解.如圖2（a）所示，矩陣前10 個(gè)最大奇異值占全部奇異值之和的85%以上，即奇異值累積貢獻(xiàn)率為85%.類似地，分析交通感知數(shù)據(jù)在空間維度的低秩特性.對(duì)25 個(gè)交通站點(diǎn)感知數(shù)據(jù)構(gòu)成的矩陣進(jìn)行奇異值分解，如圖2（b）所示，前5 個(gè)最大奇異值占全部奇異值之和的90%以上.根據(jù)低秩理論[36]：如果矩陣中存在少量奇異值之和占所有奇異值總和的比值較大，則該矩陣可以近似認(rèn)為低秩矩陣.因此分析可得，交通感知數(shù)據(jù)矩陣在時(shí)間維度和空間維度上都是近似低秩的.

基于上述結(jié)論可得，Mjs在時(shí)空維度是近似低秩的.由文獻(xiàn)[37]可知，如果矩陣是近似低秩的，則通過采樣其元素可以找到另一個(gè)低秩矩陣X來近似表示該矩陣.因此子問題 P2可等價(jià)轉(zhuǎn)化為：

其 中 rank(·)表示矩 陣的秩函數(shù)，PΩ(·)表示投影采樣算子.因?yàn)樵撝群瘮?shù)是非連續(xù)和非凸的，求解非常困難，且最小化矩陣秩即最小化矩陣非零奇異值個(gè)數(shù)，可近似看作最小化矩陣奇異值總和（即核范數(shù)最小）[37].因此，為便于求解，可用核范數(shù) ‖X‖*函數(shù)近似代替目標(biāo)秩函數(shù) rank(X).

Fig.2 Low-rank analysis of traffic sensing data matrix based SVD in terms of temporal and spatial dimensions圖2 在時(shí)空維度下基于奇異值分解的交通感知數(shù)據(jù)低秩分析

2）感知數(shù)據(jù)精確恢復(fù).受文獻(xiàn)[38]啟發(fā)，本文提出基于奇異值閾值截?cái)啵╯ingular value thresholding,SVT）的缺失數(shù)據(jù)迭代恢復(fù)算法.該算法的核心思想是在每次迭代中對(duì)矩陣進(jìn)行奇異值分解，然后將較小奇異值置為0，構(gòu)造新矩陣進(jìn)行下一輪奇異值分解.如算法2 所示.

算法2.基于低秩理論的感知數(shù)據(jù)自適應(yīng)恢復(fù)算法.

以上2 步相互迭代，直至滿足以下任意一個(gè)迭代停止條件：①迭代達(dá)到最大次數(shù)kmax（即行③）；②恢復(fù)得到的矩陣Xk與原矩陣Mjs誤差不大于ε（即行⑥）.

3.2.2 基于奇異值分解的非缺失下限估計(jì)

當(dāng)Mjs中缺失元素過多，即邊緣節(jié)點(diǎn)es處感知數(shù)據(jù)量較少，而感知數(shù)據(jù)間的相關(guān)性程度又較小時(shí)，很難精確地進(jìn)行缺失數(shù)據(jù)恢復(fù).因此，為保證數(shù)據(jù)恢復(fù)精度，每個(gè)邊緣節(jié)點(diǎn)分配到的感知數(shù)據(jù)量需滿足一定下限，即非缺失下限.根據(jù)矩陣自由度理論[39]，精確恢復(fù)一個(gè)含有缺失元素的矩陣需要的最少采樣元素個(gè)數(shù)為

其中r表示該矩陣的秩即元素間相關(guān)性程度，n1和n2分別表示該矩陣的行列數(shù).由式（23）可知，矩陣元素間相關(guān)性程度越小，精確恢復(fù)缺失數(shù)據(jù)所需的最少采樣元素個(gè)數(shù)越多.

根據(jù)式（23），當(dāng)計(jì)算基于算法2 恢復(fù)得到的完整矩 陣Xopt的非缺 失下限mj時(shí)，n1和n2很容易基于其行列數(shù)得到.而矩陣的秩rjs需進(jìn)行估計(jì)，下面基于奇異值分解估計(jì)矩陣Xopt的秩rjs：

首先對(duì)矩陣Xopt進(jìn)行奇異值分解為

其中 σ1≥σ2≥···≥σn≥0.

由于矩陣的低秩性，因此，可用占全部奇異值總和比例為 η(η ∈[0,1])的最少奇異值個(gè)數(shù)作為矩陣秩的估計(jì)值：

其中B為矩陣非零奇異值總個(gè)數(shù).

最后，根據(jù)矩陣秩的估計(jì)值rjs，基于式（23）計(jì)算非缺失下限，并將該結(jié)果反饋至云服務(wù)器重新調(diào)整感知數(shù)據(jù)分配方案（子問題 P1′），以保證缺失感知數(shù)據(jù)的精確恢復(fù).

4 基于大規(guī)模交通感知數(shù)據(jù)集的實(shí)驗(yàn)評(píng)估

4.1 數(shù)據(jù)集和實(shí)驗(yàn)方法介紹

1）大規(guī)模智能交通感知數(shù)據(jù)集介紹.本文利用澳大利亞新南威爾士州的交通流量監(jiān)控系統(tǒng)TVVS的感知數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)評(píng)估.該感知數(shù)據(jù)集由部署在道路旁的大約600 個(gè)交通感知站點(diǎn)的交通監(jiān)控感知系統(tǒng)產(chǎn)生，基本覆蓋整個(gè)新南威爾士州.本文主要采用每個(gè)交通站點(diǎn)的交通流量感知數(shù)據(jù)，采樣間隔為1h，采樣時(shí)間長(zhǎng)度為12 個(gè)月，即2018-01-01—2018-12-31.

2）實(shí)驗(yàn)方法介紹.為評(píng)估邊緣節(jié)點(diǎn)部署性能，本文參照實(shí)際場(chǎng)景，設(shè)定交通站點(diǎn)數(shù)據(jù)量規(guī)模和邊緣節(jié)點(diǎn)容量等其他參數(shù)，同時(shí)通過變化交通站點(diǎn)數(shù)據(jù)量規(guī)模、邊緣節(jié)點(diǎn)容量及部署成本預(yù)算，分別評(píng)估3種因素對(duì)邊緣節(jié)點(diǎn)部署性能，即所有節(jié)點(diǎn)能同時(shí)處理的總感知數(shù)據(jù)量的影響.在實(shí)驗(yàn)評(píng)估中，同時(shí)考慮了2 種不同規(guī)模的網(wǎng)絡(luò)，即大規(guī)模網(wǎng)絡(luò)(N=100,S=20) 和小規(guī) 模網(wǎng)絡(luò) (N=10,S=5).

為了充分地評(píng)估交通感知數(shù)據(jù)恢復(fù)的性能，隨機(jī)地選擇24 個(gè)交通感知站點(diǎn)，將它們中無缺失的感知數(shù)據(jù)組成實(shí)驗(yàn)數(shù)據(jù)矩陣.進(jìn)一步地，在評(píng)估過程中，首先變化缺失數(shù)據(jù)長(zhǎng)度（即矩陣缺失元素個(gè)數(shù)）；然后固定缺失數(shù)據(jù)長(zhǎng)度，變化交通感知站點(diǎn)的數(shù)量，以評(píng)估站點(diǎn)數(shù)量對(duì)缺失感知數(shù)據(jù)恢復(fù)性能的影響.

與當(dāng)前多數(shù)邊緣節(jié)點(diǎn)部署工作[19,28,40]類似，為了全面地評(píng)估邊緣節(jié)點(diǎn)的部署性能，本文采用3 種性能不同的典型對(duì)比算法，即最優(yōu)的、近似最優(yōu)的、一般的對(duì)比算法.1）OPT.即最優(yōu)的邊緣節(jié)點(diǎn)部署方案，基于暴力搜索對(duì)所有可能的部署方案進(jìn)行窮舉以獲得最優(yōu)解.由于本文的邊緣節(jié)點(diǎn)部署問題是NP-hard問題，因此，OPT 具有指數(shù)級(jí)計(jì)算復(fù)雜度，只能適用于小規(guī)模網(wǎng)絡(luò).2）HEU[41].即基于遺傳算法的近似最優(yōu)啟發(fā)式算法，將部署方案類比成生物種群，初始化若干方案，并通過模擬自然界種群進(jìn)化的過程（即遺傳、交叉和變異），不斷迭代更新以得到近似最優(yōu)解.3）RAN.即隨機(jī)部署算法，將邊緣節(jié)點(diǎn)隨機(jī)地部署在任意交通站點(diǎn)處.

為了充分評(píng)估缺失感知數(shù)據(jù)恢復(fù)性能，采用3 種常用的數(shù)據(jù)恢復(fù)算法作為對(duì)比算法：1）MR.即基于回歸擬合的缺失數(shù)據(jù)恢復(fù)算法，利用非缺失數(shù)據(jù)擬合多項(xiàng)式，從而基于該多項(xiàng)式補(bǔ)全缺失數(shù)據(jù).2）KNN[42].基于K近鄰的缺失數(shù)據(jù)恢復(fù)算法，利用感知數(shù)據(jù)的時(shí)空相關(guān)性，通過距離缺失元素最近的k個(gè)數(shù)據(jù)的平均值來估計(jì)該缺失值.3）RF[43].基于隨機(jī)森林回歸的缺失感知數(shù)據(jù)恢復(fù)算法，即基于無缺失數(shù)據(jù)訓(xùn)練隨機(jī)森林模型，用該模型預(yù)測(cè)缺失數(shù)據(jù).

在實(shí)驗(yàn)評(píng)估中，本文采用3 種評(píng)估指標(biāo)：1）邊緣節(jié)點(diǎn)處理總數(shù)據(jù)量，即所有部署邊緣節(jié)點(diǎn)接收到的總感知數(shù)據(jù)量，如式（1）；2）平均絕對(duì)誤差（mean absolute error,MAE），即補(bǔ)全數(shù)據(jù)矩陣元素的估計(jì)值與真值之間誤差的絕對(duì)平均值，如式（27）；3）平均絕對(duì)百分比誤差（mean absolute percentage error,MAPE），即補(bǔ)全數(shù)據(jù)矩陣元素的估計(jì)誤差與真值的百分比平均值，如式（28）.

4.2 實(shí)驗(yàn)結(jié)果

1）邊緣節(jié)點(diǎn)部署性能評(píng)估

Fig.3 Impact of different sensing data scales of traffic stations on the performance of edge node deployment圖3 不同交通站點(diǎn)感知數(shù)據(jù)規(guī)模對(duì)邊緣節(jié)點(diǎn)部署性能的影響

①評(píng)估不同交通感知站點(diǎn)的感知數(shù)據(jù)規(guī)模對(duì)邊緣節(jié)點(diǎn)部署性能的影響.如圖3 所示，變化交通站點(diǎn)數(shù)據(jù)規(guī)模為實(shí)際規(guī)模的1.0～2.0 倍.實(shí)驗(yàn)結(jié)果表明，在小規(guī)模網(wǎng)絡(luò)場(chǎng)景下本文算法比RAN 算法性能平均提升25%.同時(shí)，本文算法與HEU 算法都能達(dá)到OPT算法的95%以上.主要原因是小規(guī)模網(wǎng)絡(luò)場(chǎng)景中，滿足約束的可行部署方案較少，使得HEU 算法有較大概率獲得性能較優(yōu)的解，從而性能與本文算法以及OPT 算法接近.但是，在大規(guī)模網(wǎng)絡(luò)場(chǎng)景中，本文算法比HEU 算法平均提升性能8.8%，比RAN 算法平均提升性能31.6%.

②評(píng)估不同邊緣節(jié)點(diǎn)容量對(duì)邊緣節(jié)點(diǎn)部署性能的影響.如圖4 所示，本文算法比RAN 算法，在小規(guī)模和大規(guī)模網(wǎng)絡(luò)場(chǎng)景中性能分別平均提升25.9%和28.1%.雖然本文算法和HEU 算法在小規(guī)模網(wǎng)絡(luò)場(chǎng)景中較為接近，都達(dá)到了OPT 性能的95%以上，但是在大規(guī)模場(chǎng)景下本文算法比HEU 性能平均提升10.3%.

③評(píng)估不同部署成本預(yù)算對(duì)邊緣節(jié)點(diǎn)部署性能的影響.如圖5 所示，本文算法比RAN 算法，在小規(guī)模和大規(guī)模網(wǎng)絡(luò)場(chǎng)景中性能分別平均提升45.2%和32.5%.同時(shí)，在小規(guī)模場(chǎng)景中，本文算法和HEU 算法都能達(dá)到OPT 性能的92%.但是，在大規(guī)模網(wǎng)絡(luò)場(chǎng)景下，本文算法的性能比HEU 算法平均提高11.9%.

2）交通感知數(shù)據(jù)恢復(fù)精度評(píng)估

為了評(píng)估本文所提缺失感知數(shù)據(jù)恢復(fù)算法的性能，分別與3 種常見缺失數(shù)據(jù)恢復(fù)算法在變化缺失長(zhǎng)度和交通站點(diǎn)數(shù)量情況下進(jìn)行比較.

①評(píng)估不同感知數(shù)據(jù)缺失長(zhǎng)度對(duì)缺失數(shù)據(jù)恢復(fù)精度的影響.如圖6 所示，實(shí)驗(yàn)結(jié)果表明，隨著感知數(shù)據(jù)缺失長(zhǎng)度的增大，缺失數(shù)據(jù)恢復(fù)的精度也不斷降低.該結(jié)果符合常理，即缺失的感知數(shù)據(jù)量越大，則數(shù)據(jù)所包含信息量就越小，因此，數(shù)據(jù)恢復(fù)的精度也就越差.同時(shí)，與RF 算法、MR 算法和KNN 算法比較，本文算法的MAE指標(biāo)分別平均降低48.0%，65.1%，74.8%，MAPE指標(biāo)分 別平均降低47.8%，62.4%，78.9%.

此外，當(dāng)缺失數(shù)據(jù)長(zhǎng)度較大時(shí)，MR 和KNN 算法恢復(fù)的結(jié)果不夠理想，這是因?yàn)榛诰祷謴?fù)和多項(xiàng)式擬合恢復(fù)數(shù)據(jù)的算法對(duì)數(shù)據(jù)的非缺失程度要求較高，所以當(dāng)數(shù)據(jù)缺失程度較大時(shí)，選擇SVT 算法能夠保證較好的補(bǔ)全精度.

Fig.4 Impact of different edge node capacities on the performance of edge node deployment圖4 不同邊緣節(jié)點(diǎn)容量對(duì)邊緣節(jié)點(diǎn)部署性能的影響

Fig.5 Impact of different total consumption budgets on the performance of edge node deployment圖5 不同總耗費(fèi)預(yù)算對(duì)邊緣節(jié)點(diǎn)部署性能的影響

Fig.6 Impact of different missing data lengths on the accuracy of missing sensing data recovery圖6 不同缺失數(shù)據(jù)長(zhǎng)度對(duì)缺失感知數(shù)據(jù)恢復(fù)精度的影響

Fig.7 Impact of different number of traffic stations on the accuracy of missing sensing data recovery圖7 不同交通站點(diǎn)數(shù)量對(duì)缺失感知數(shù)據(jù)恢復(fù)精度的影響

②評(píng)估不同交通站點(diǎn)數(shù)量對(duì)缺失數(shù)據(jù)恢復(fù)精度的影響.如圖7 所示，實(shí)驗(yàn)結(jié)果表明，隨著交通站點(diǎn)數(shù)量的增多，缺失數(shù)據(jù)的恢復(fù)精度也不斷提高.這是因?yàn)殡S著交通站點(diǎn)數(shù)量的增加，矩陣中非缺失元素的比例增加，從而使得缺失數(shù)據(jù)的恢復(fù)精度也不斷提高.此外，與RF 算法、MR 算法和KNN 算法比較，本文算法的MAPE指標(biāo)分別平均降低50.2%，60.9%，43.8%，MAE指標(biāo)分別平均降低51.2%，64.5%，47.1%.同理，由于KNN 和MR 算法對(duì)矩陣中元素非缺失程度的依賴性，使得其在交通站點(diǎn)數(shù)量較少時(shí)表現(xiàn)出來的性能不夠理想.

此外，本文還對(duì)SVT 算法的收斂性進(jìn)行了驗(yàn)證.首先，隨機(jī)選擇24 個(gè)交通站點(diǎn)24 天的感知數(shù)據(jù)組成實(shí)驗(yàn)數(shù)據(jù)矩陣；然后，利用SVT 算法，設(shè)定不同迭代次數(shù)對(duì)矩陣進(jìn)行恢復(fù)，得到的結(jié)果如圖8（a）所示.可以發(fā)現(xiàn)當(dāng)?shù)螖?shù)達(dá)到90 次后，感知數(shù)據(jù)的恢復(fù)精度基本保持不變.

③評(píng)估缺失感知數(shù)據(jù)自適應(yīng)恢復(fù)的性能.具體地，隨機(jī)選擇16 個(gè)交通站點(diǎn)14 天內(nèi)的感知數(shù)據(jù)組成組成實(shí)驗(yàn)數(shù)據(jù)矩陣.

首先，在實(shí)驗(yàn)前，先探究了該矩陣秩隨時(shí)間變化的情況，結(jié)果如圖8（b）所示.可以發(fā)現(xiàn)，矩陣秩大小會(huì)隨時(shí)間而產(chǎn)生波動(dòng)，如第3 天（4 月25 日，澳大利亞退伍老兵日）、第6 天和第7 天（周末）的感知數(shù)據(jù)矩陣秩產(chǎn)生了較明顯的下降.

然后，分別采用本文提出的自適應(yīng)缺失數(shù)據(jù)恢復(fù)算法，即根據(jù)恢復(fù)結(jié)果，計(jì)算非缺失下限并調(diào)整采樣率和非自適應(yīng)恢復(fù)算法，即采樣率不隨恢復(fù)結(jié)果自適應(yīng)變化，對(duì)該矩陣進(jìn)行數(shù)據(jù)恢復(fù).實(shí)驗(yàn)結(jié)果如圖9 所示，自適應(yīng)恢復(fù)算法比非自適應(yīng)恢復(fù)算法的MAE指標(biāo)和MAPE指標(biāo)分別平均降低40.3%和40.4%.主要原因是感知數(shù)據(jù)矩陣的秩在隨時(shí)間波動(dòng)，即感知數(shù)據(jù)的相關(guān)性程度隨時(shí)間發(fā)生了變化.而非自適應(yīng)恢復(fù)算法并沒有根據(jù)相關(guān)性程度變化及時(shí)調(diào)整元素采樣率，如當(dāng)相關(guān)性程度減小時(shí)，提高采樣率，增加非缺失元素的比例.而本文所提的自適應(yīng)恢復(fù)算法充分考慮了這一因素，因此保證了數(shù)據(jù)的恢復(fù)精度，提高了系統(tǒng)恢復(fù)性能的魯棒性.

此外，本文基于澳大利亞TVVS 系統(tǒng)中600 個(gè)交通站點(diǎn)的感知數(shù)據(jù)，構(gòu)建基于邊緣智能計(jì)算的大規(guī)模交通感知數(shù)據(jù)恢復(fù)原型系統(tǒng)，如圖10 所示.

5 總結(jié)和展望

5.1 工作總結(jié)

本文提出一種基于邊緣智能計(jì)算的城市交通感知數(shù)據(jù)自適應(yīng)恢復(fù)系統(tǒng)，以解決高計(jì)算復(fù)雜度的邊緣節(jié)點(diǎn)部署和高時(shí)空動(dòng)態(tài)性的交通感知數(shù)據(jù)恢復(fù)問題.首先，提出具有理論下界的邊緣節(jié)點(diǎn)次優(yōu)部署算法，以解決邊緣節(jié)點(diǎn)部署這個(gè)NP-hard 問題.然后，提出基于低秩理論的缺失感知數(shù)據(jù)自適應(yīng)恢復(fù)算法，利用低秩理論和奇異值分解，基于恢復(fù)結(jié)果估計(jì)感知數(shù)據(jù)矩陣的非缺失下限，并根據(jù)非缺失下限值的反饋，自適應(yīng)調(diào)整交通站點(diǎn)感知數(shù)據(jù)分配，從而提高數(shù)據(jù)恢復(fù)的精確性和魯棒性.最后，基于實(shí)際大規(guī)模交通感知數(shù)據(jù)集構(gòu)建原型系統(tǒng)，并進(jìn)行實(shí)驗(yàn)評(píng)估，實(shí)驗(yàn)結(jié)果驗(yàn)證所提算法的有效性和魯棒性.

Fig.8 Convergence analysis of SVT and the trend of rank for traffic sensing data matrix圖8 SVT 收斂性分析和交通感知數(shù)據(jù)矩陣秩的變化趨勢(shì)

Fig.9 Evaluation of adaptive recovery performance of missing traffic sensing data圖9 缺失交通感知數(shù)據(jù)自適應(yīng)恢復(fù)性能評(píng)估

Fig.10 Large-scale traffic sensing data recovery prototype system圖10 大規(guī)模交通感知數(shù)據(jù)恢復(fù)原型系統(tǒng)

5.2 研究展望

在將來的工作中，進(jìn)一步改進(jìn)和完善本文存在的缺點(diǎn)和不足，主要包括3 個(gè)方面：1）交通站點(diǎn)的拓?fù)潢P(guān)系與它們感知數(shù)據(jù)的相關(guān)性有關(guān)，因此，如何利用交通站點(diǎn)道路拓?fù)鋱D來進(jìn)一步提高缺失感知數(shù)據(jù)精度是下一步的研究工作.2）本文只是以交通流量這種典型的交通感知數(shù)據(jù)作為例子研究交通感知數(shù)據(jù)恢復(fù)且只考慮了來自靜態(tài)交通感知站點(diǎn)的感知數(shù)據(jù).下一步將延伸和擴(kuò)展到更多不同來源種類的感知數(shù)據(jù)，如來自無人機(jī)感知[44]和人群感知[45]的城市感知數(shù)據(jù)等.3）本文在恢復(fù)交通感知數(shù)據(jù)時(shí)，主要利用感知數(shù)據(jù)之間的時(shí)空相關(guān)性，但這些感知數(shù)據(jù)之間還存在其他多維度的聯(lián)系，如數(shù)據(jù)類型等.下一步將結(jié)合其他多維相關(guān)性進(jìn)一步提高恢復(fù)精度.

致 謝感謝重慶大學(xué)計(jì)算機(jī)學(xué)院張乃凡、程梁華、李耀宇對(duì)本文所做的貢獻(xiàn)！

作者貢獻(xiàn)聲明：向朝參和程文輝提出了論文創(chuàng)新點(diǎn)，設(shè)計(jì)了論文實(shí)驗(yàn)方案，并撰寫了論文；張昭實(shí)現(xiàn)了論文算法；焦賢龍、屈毓錛、陳超和戴海鵬指導(dǎo)了論文寫作.