宋子暉 李卓 陳昕

摘 要：針對(duì)移動(dòng)群智感知任務(wù)中區(qū)域全覆蓋感知成本過高問題，提出基于壓縮感知的移動(dòng)群智感知任務(wù)分發(fā)（CS-TD）機(jī)制。首先提出了感知任務(wù)整體成本模型，該模型綜合考慮了參與感知任務(wù)的節(jié)點(diǎn)個(gè)數(shù)、節(jié)點(diǎn)的感知次數(shù)與數(shù)據(jù)上傳次數(shù);然后基于成本模型，分析感知節(jié)點(diǎn)的日常移動(dòng)軌跡，結(jié)合壓縮感知數(shù)據(jù)采集技術(shù)，提出了一種基于感知節(jié)點(diǎn)軌跡的壓縮感知采樣方法;其次通過區(qū)域覆蓋最小節(jié)點(diǎn)區(qū)域全覆蓋最少節(jié)點(diǎn)（RCLN）此處的描述，與引言中“區(qū)域全覆蓋最少節(jié)點(diǎn)（Region Covers Least Nodes， RCLN）”是一個(gè)意思嗎？二者是否應(yīng)該統(tǒng)一改為“區(qū)域全覆蓋最少節(jié)點(diǎn)”，其英文全稱和縮寫也應(yīng)改為“Region Covers Least Nodes， RCLN”，請(qǐng)明確。算法，選出最佳節(jié)點(diǎn)集合，對(duì)節(jié)點(diǎn)進(jìn)行任務(wù)分配，利用壓縮感知技術(shù)恢復(fù)節(jié)點(diǎn)數(shù)據(jù);最后在多次感知任務(wù)的迭代中對(duì)感知節(jié)點(diǎn)的可信程度進(jìn)行評(píng)定，保證任務(wù)方案的最優(yōu)性。對(duì)CS-TD分發(fā)模型進(jìn)行多次實(shí)驗(yàn)驗(yàn)證，與已有的CrowdTasker算法相比，CS-TD算法平均成本降低了30%以上。CS-TD模型能有效降低感知節(jié)點(diǎn)的消耗，能在全覆蓋感知任務(wù)中降低整體感知成本。

關(guān)鍵詞：壓縮感知;移動(dòng)群智感知;任務(wù)分發(fā);區(qū)域覆蓋;移動(dòng)軌跡

中圖分類號(hào)： TP393.01

文獻(xiàn)標(biāo)志碼：A

Abstract： Since the cost of mobile crowdsensing in full coverage of area is excessively high， a Compressive Sensing-based mobile crowdsensing Task Distribution （CS-TD） mechanism was proposed. Firstly， an overall cost model of perceived task was proposed. In this model， the number of nodes participating in a perceived task， the number of nodes perceived and data uploaded were comprehensively considered. Then based on cost model， the daily movement trajectory of sensory node was analyzed， by combining with the compressed sensing data acquisition technology， a compressed sensing sampling method based on perceived node trajectory was proposed. Secondly， the optimal node set was selected by the Region Covers Least Nodes （RCLN） algorithm， the tasks were assigned to the nodes， and then the compressed sensing technology was used to recover node data. Finally， the trustworthiness of perceived node was evaluated in iteration of multiple perceived tasks to ensure the optimality of task plan. The CS-TD distribution model was tested several times. Compared with the existing CrowdTasker algorithm， the average cost of CS-TD algorithm is reduced by more than 30%. CS-TD model can effectively reduce consumption of sensing node and reduce overall perceived cost in full coverage sensing task.

Key words： Compressive Sensing （CS）; mobile crowdsensing; task distribution; regional coverage; moving trajectory

0 引言

隨著移動(dòng)互聯(lián)網(wǎng)的發(fā)展，大數(shù)據(jù)處理技術(shù)成熟，移動(dòng)服務(wù)對(duì)數(shù)據(jù)的需求日漸增大。移動(dòng)群智感知作為一種數(shù)據(jù)感知方式，其應(yīng)用已經(jīng)從在交通數(shù)據(jù)采集[1]、空氣質(zhì)量檢測(cè)和噪聲檢測(cè)[2]等領(lǐng)域的服務(wù)中，發(fā)展到實(shí)時(shí)路況、支付寶口碑等多種生活服務(wù)中。例如，在地圖應(yīng)用中，用戶以上傳照片加以描述評(píng)價(jià)，提交發(fā)布者對(duì)該地點(diǎn)的需求數(shù)據(jù)。

相比采用固定傳感裝置采集，移動(dòng)群智感知無需安裝大量固定感知節(jié)點(diǎn);相比數(shù)據(jù)需求方主動(dòng)采集，移動(dòng)群智感知能夠直接利用任務(wù)區(qū)域用戶來進(jìn)行感知任務(wù)，減少感知成本。移動(dòng)感知節(jié)點(diǎn)靈活性強(qiáng)，能實(shí)現(xiàn)個(gè)性化的數(shù)據(jù)采集任務(wù)，同時(shí)能以極高的精度對(duì)區(qū)域數(shù)據(jù)進(jìn)行覆蓋采集。

雖然移動(dòng)群智感知的感知模型優(yōu)于傳統(tǒng)感知方式，但對(duì)區(qū)域全覆蓋的數(shù)據(jù)感知依然使得整體任務(wù)的感知成本過高。多項(xiàng)研究通過減小感知節(jié)點(diǎn)移動(dòng)距離、減少感知節(jié)點(diǎn)采集數(shù)據(jù)量、減少任務(wù)激勵(lì)成本等方案來減少感知任務(wù)總體成本。綜合分析得出感知任務(wù)中的主要成本有：感知節(jié)點(diǎn)參與感知任務(wù)的固定成本，隨任務(wù)量和貢獻(xiàn)度提升的額外成本，感知任務(wù)中感知節(jié)點(diǎn)的移動(dòng)成本，數(shù)據(jù)采集、處理、傳輸成本;由此得出，最小化感知節(jié)點(diǎn)數(shù)量，使每個(gè)節(jié)點(diǎn)能完成盡可能多的任務(wù)，來作為減少感知任務(wù)成本的一種優(yōu)化策略。

本文在最小化參與感知任務(wù)感知節(jié)點(diǎn)數(shù)量的基礎(chǔ)上，使用壓縮感知技術(shù)進(jìn)一步減少節(jié)點(diǎn)的感知和傳輸成本，提出基于壓縮感知的移動(dòng)群智感知任務(wù)分發(fā)（Compressive Sensing-based mobile crowdsensing Task Distribution， CS-TD）機(jī)制?？紤]用戶的日常移動(dòng)軌跡，以最小數(shù)量的感知節(jié)點(diǎn)來完成覆蓋感知任務(wù)，分析其軌跡覆蓋區(qū)域中數(shù)據(jù)的相關(guān)性，利用壓縮感知技術(shù)來減少節(jié)點(diǎn)的測(cè)量和傳輸次數(shù)。本文的主要工作如下：

1）設(shè)計(jì)了區(qū)域全覆蓋最少節(jié)點(diǎn)（Region Covers Least Nodes， RCLN）選擇算法，選擇出最少的感知節(jié)點(diǎn)集合，提出基于感知節(jié)點(diǎn)軌跡的壓縮感知的數(shù)據(jù)采樣方式;同時(shí)為減少軌跡重疊的重復(fù)采樣，保障感知節(jié)最優(yōu)采樣方式，設(shè)計(jì)了感知節(jié)點(diǎn)感知任務(wù)分配方案。

2）利用壓縮感知技術(shù)，對(duì)基于節(jié)點(diǎn)提交的采樣數(shù)據(jù)進(jìn)行重建，恢復(fù)整體感知數(shù)據(jù);同時(shí)利用缺失值恢復(fù)算法，分別對(duì)每個(gè)節(jié)點(diǎn)數(shù)據(jù)通過其他節(jié)點(diǎn)數(shù)據(jù)重構(gòu)對(duì)比，對(duì)節(jié)點(diǎn)進(jìn)行可信度評(píng)估。

3）使用Crowdtasker作為對(duì)比算法，對(duì)CS-TD節(jié)點(diǎn)的成本和整體方案的性能進(jìn)行了仿真實(shí)驗(yàn)。

1 相關(guān)工作

為減少移動(dòng)群智感知中感知任務(wù)成本，已有多項(xiàng)工作，在早期物聯(lián)網(wǎng)模型中，文獻(xiàn)[3]研究了數(shù)據(jù)感知任務(wù)分配方案，假設(shè)一次到達(dá)一個(gè)節(jié)點(diǎn)，優(yōu)化目標(biāo)是感知節(jié)點(diǎn)的利益最大化，未考慮感知任務(wù)的總體成本;以智能手機(jī)作為感知節(jié)點(diǎn)的移動(dòng)群智感知中，文獻(xiàn)[4]以最優(yōu)化感知節(jié)點(diǎn)的智能手機(jī)的能效為目標(biāo)，該文獻(xiàn)假設(shè)任務(wù)是相同的，可以分配給任意工作節(jié)點(diǎn);文獻(xiàn)[5]考慮在智能手機(jī)在與基站通話話時(shí)傳輸數(shù)據(jù)，從而減少智能手機(jī)的傳輸成本，未考慮感知節(jié)點(diǎn)在感知任務(wù)中的多任務(wù)方案來降低成本;文獻(xiàn)[6]在預(yù)算約束條件下，以提高覆蓋質(zhì)量為目標(biāo)進(jìn)行任務(wù)分配。文獻(xiàn)[7-8]等將感知節(jié)點(diǎn)的移動(dòng)距離作為優(yōu)化目標(biāo)來考慮感知任務(wù)的分配。文獻(xiàn)[9]以最小化總體感知成本為目標(biāo)，提出了兩種基于貪婪的遺傳算法來優(yōu)化發(fā)布感知任務(wù)的感知成本。對(duì)于區(qū)域覆蓋的移動(dòng)群智感知任務(wù)，將感知區(qū)域依據(jù)地理位置劃分為多個(gè)基本感知單元，在每個(gè)基本感知單元中招募采集節(jié)點(diǎn)進(jìn)行感知任務(wù)。文獻(xiàn)[10]中提出一種基于壓縮感知的任務(wù)分配模型——SPACE-TA（SPArse Cost-Effective Task Allocation），該模型基于感知任務(wù)數(shù)據(jù)的相關(guān)性，使用時(shí)空壓縮感知采集計(jì)算整體感知數(shù)據(jù)，然后利用貝葉斯推理來驗(yàn)證數(shù)據(jù)質(zhì)量，該模型在保障數(shù)據(jù)質(zhì)量的情況下，有效地減少了參與感知的用戶數(shù)量;但這種方法計(jì)算復(fù)雜性較高，一次感知任務(wù)需要多次測(cè)量恢復(fù)測(cè)量的迭代，感知任務(wù)需要消耗大量時(shí)間。

將感知任務(wù)與感知節(jié)點(diǎn)的日常軌跡相關(guān)聯(lián)，感知節(jié)點(diǎn)可在日常生活中間接完成感知任務(wù)，不用作出額外的移動(dòng)，從而降低移動(dòng)開銷。對(duì)于移動(dòng)群智感知節(jié)點(diǎn)的移動(dòng)模型分析已有相關(guān)研究，文獻(xiàn)[11]中提出離散馬爾可夫鏈移動(dòng)節(jié)點(diǎn)模型，將感知節(jié)點(diǎn)的移動(dòng)軌跡與任務(wù)分配相結(jié)合。文獻(xiàn)[12]建立移動(dòng)節(jié)點(diǎn)的區(qū)域覆蓋模型，來保障對(duì)感知區(qū)域的覆蓋感知，但基于概率模型只能預(yù)測(cè)感知節(jié)點(diǎn)到相鄰單元的可能性，或者相鄰時(shí)間片的位置，無法將完整用戶軌跡與任務(wù)結(jié)合。日常生活中人們的出行軌跡往往表現(xiàn)出強(qiáng)烈的一致性，如由家到公司上班的路線、公共交通路線等;將感知節(jié)點(diǎn)的軌跡可分成兩類：一類為日常軌跡，表現(xiàn)出周期的相似性;一類是隨機(jī)軌跡，按時(shí)間隨機(jī)性發(fā)生。對(duì)區(qū)域覆蓋感知，可以利用日常軌跡進(jìn)行感知任務(wù)，招募不同屬性的用戶如學(xué)生、公司職員等作為感知節(jié)點(diǎn)，可以將大部分公共場(chǎng)所和公司、學(xué)校、住宅小區(qū)等區(qū)域覆蓋。對(duì)于一些沒有日常軌跡的區(qū)域，便需要考慮使用發(fā)放激勵(lì)的策略來招募節(jié)點(diǎn)主動(dòng)去感知。

使用用戶的日常軌跡，考慮用戶軌跡上的感知數(shù)據(jù)往往具有高度的相關(guān)性[13]。對(duì)于存在冗余和關(guān)聯(lián)的數(shù)據(jù)，總能找到一組不相關(guān)的稀疏基，來對(duì)數(shù)據(jù)進(jìn)行稀疏表示。基于壓縮感知思想，使得用較少的系數(shù)與稀疏基相乘來表示原始數(shù)據(jù)，在采集數(shù)據(jù)時(shí)，通過直接或者間接采集這些少量的系數(shù)就能恢復(fù)原始信號(hào)，可在一定程度上降低采集數(shù)據(jù)時(shí)的測(cè)量開銷[14]。壓縮感知技術(shù)已經(jīng)應(yīng)用于多個(gè)方面[15-17]。在感知任務(wù)中，鄰近區(qū)域的測(cè)量值往往表現(xiàn)出極大的相關(guān)性，文獻(xiàn)[18-19]已證明鄰近區(qū)域中溫度、空氣質(zhì)量等感測(cè)數(shù)據(jù)的稀疏性。

在移動(dòng)群智感知中，若能直接測(cè)得感知任務(wù)的稀疏信號(hào)，就能通過壓縮感知理論計(jì)算出所有的感知數(shù)據(jù)。考慮壓縮感知的測(cè)量信號(hào)的獲取是基于采集矩陣通過對(duì)真實(shí)值線性加權(quán)操作實(shí)現(xiàn)的，而節(jié)點(diǎn)在移動(dòng)過程中正是對(duì)軌跡上感知單元的線性遍歷，因此本文設(shè)計(jì)出基于用戶軌跡的壓縮感知采樣方式來測(cè)量和提交感知數(shù)據(jù)，從而減少總體感知成本。

2 系統(tǒng)模型

2.1 移動(dòng)群智感知任務(wù)模型

對(duì)于區(qū)域覆蓋感知任務(wù)，考慮傳感器的覆蓋范圍、發(fā)布者對(duì)感知區(qū)域覆蓋的精度要求，設(shè)置固定面積的基本感知單元，對(duì)基本感知單元中數(shù)據(jù)的一次有效采集和提交，視作對(duì)該區(qū)域的一次有效感知。本文中對(duì)感知節(jié)點(diǎn)軌跡長(zhǎng)度和任務(wù)量的定義都用基本感知單元個(gè)數(shù)表示。

將整體任務(wù)采集區(qū)域劃分為n個(gè)基本感知單元，記所有基本感知單元集合為：

所有基本采集單元感知數(shù)據(jù)為：

其中：sj為第j個(gè)基本感知單元，xj為第j個(gè)基本感知單元的感知數(shù)據(jù)。

對(duì)于全部感知節(jié)點(diǎn)L*，節(jié)點(diǎn)Pl的軌跡記作：

由感知節(jié)點(diǎn)軌跡覆蓋的基本感知單元集合表示節(jié)點(diǎn)移動(dòng)軌跡，Sl為S的一個(gè)子集。

對(duì)感知節(jié)點(diǎn)Pl分配的感知任務(wù)SlC滿足：

感知節(jié)點(diǎn)Pl提交數(shù)據(jù)為：

其中T表示向量轉(zhuǎn)置。

2.2 壓縮感知任務(wù)模型

根據(jù)壓縮感知理論，定義本文的壓縮感知任務(wù)模型，對(duì)于先驗(yàn)稀疏感知數(shù)據(jù)：

XC=[x1，x2，…，xn′]T（6）式（6）與式（2）是一樣的，還有必要在這里重復(fù)嗎？請(qǐng)明確。若刪除了某一個(gè)公式，需注意公式編號(hào)的調(diào)整，要按照次序依次編號(hào)和引用。

存在特定的過完備稀疏字典[15]：

XC可以通過Ψ稀疏表示，其中Ψ為n′×n′的矩陣。

α為XC在基Ψ對(duì)應(yīng)的稀疏系數(shù)向量，且為k稀疏，即α中只有k個(gè)非0值。對(duì)一維稀疏列向量α作降維操作：

其中Φ*為m×n′的降維矩陣，Y為m維度的測(cè)量值列向量，可知k

壓縮感知的求解過程可以抽象成如下問題：

由式（8）～（9）可知：

其中Φ=Φ*Ψ-1為測(cè)量矩陣，即通過測(cè)量矩陣Φ可以直接對(duì)原始信號(hào)進(jìn)行稀疏采集，采集結(jié)果通過式（10）的l0范數(shù)優(yōu)化問題求解出稀疏系數(shù)α，然后利用式（8）恢復(fù)出原始數(shù)據(jù)。

2.3 感知任務(wù)成本模型

考慮感知任務(wù)中感知成本，定義如表1所示。

對(duì)于參與感知任務(wù)的感知節(jié)點(diǎn)設(shè)置固定成本，總?cè)蝿?wù)的成本受到感知節(jié)點(diǎn)數(shù)量因素影響，參與感知的節(jié)點(diǎn)個(gè)數(shù)越少，整體成本越少;感知節(jié)點(diǎn)每參與一個(gè)基本感知單元任務(wù)產(chǎn)生一個(gè)額外成本，即感知節(jié)點(diǎn)的成本會(huì)隨著感知任務(wù)量的增加而增多。還需要考慮感知節(jié)點(diǎn)的內(nèi)部成本，定義為測(cè)量成本、計(jì)算存儲(chǔ)成本、傳輸成本。定義感知任務(wù)的整體成本：

其中：L為參與感知任務(wù)的感知節(jié)點(diǎn)集合，nl′和ml′分別表示節(jié)點(diǎn)Pl的感知任務(wù)量和測(cè)量值個(gè)數(shù)，λ來調(diào)整感知節(jié)點(diǎn)內(nèi)部成本和不同類型感知任務(wù)成本之間的比例。

2.4 整體優(yōu)化目標(biāo)

問題定義 在區(qū)域全覆蓋感知任務(wù)中，保證感知節(jié)點(diǎn)全覆蓋測(cè)量區(qū)域中所有基本感知單元，最小化任務(wù)整體成本。

3 任務(wù)分發(fā)機(jī)制設(shè)計(jì)

3.1 CS-TD任務(wù)分發(fā)模型

CS-TD任務(wù)分發(fā)機(jī)制流程如圖1所示。通過分析節(jié)點(diǎn)歷史提交數(shù)據(jù)和用戶節(jié)點(diǎn)注冊(cè)信息，提取出全部節(jié)點(diǎn)信息以及每個(gè)節(jié)點(diǎn)的軌跡集合。通過區(qū)域全覆蓋最少節(jié)點(diǎn)（RCLN）算法，選擇出當(dāng)前任務(wù)中的最優(yōu)感知節(jié)點(diǎn)集合并對(duì)選出的感知節(jié)點(diǎn)基于其軌跡分配感知任務(wù)，感知節(jié)點(diǎn)在接收到分配的任務(wù)后，在其軌跡上使用基于感知節(jié)點(diǎn)軌跡的壓縮感知（Node Trajectories Compressed Sensing， NTCS）采樣方式，采集目標(biāo)單元數(shù)據(jù)并提交服務(wù)器。服務(wù)器通過節(jié)點(diǎn)提交的測(cè)量值，利用壓縮感知算法恢復(fù)節(jié)點(diǎn)所覆蓋區(qū)域的感知數(shù)據(jù)。最后，對(duì)感知節(jié)點(diǎn)進(jìn)行可信度分析。

每次感知任務(wù)開始，在服務(wù)器中獲取所有可用的感知節(jié)點(diǎn)，根據(jù)服務(wù)器中存儲(chǔ)感知節(jié)點(diǎn)的軌跡信息和以及可信度，選出最優(yōu)參與感知節(jié)點(diǎn)集合;如圖1中虛線部分，每次感知任務(wù)結(jié)束后，對(duì)感知節(jié)點(diǎn)提交的感知數(shù)據(jù)進(jìn)行可信度分析，分析結(jié)果作感知節(jié)點(diǎn)的可信度，以供下次任務(wù)分配使用。

3.2 區(qū)域全覆蓋最少節(jié)點(diǎn)算法

對(duì)參與感知任務(wù)的移動(dòng)感知節(jié)點(diǎn)的歷史提交數(shù)據(jù)和注冊(cè)信息分析，提取出參與感知節(jié)點(diǎn)的日常移動(dòng)軌跡和可信度。此處默認(rèn)為參與感知節(jié)點(diǎn)充足，能保證感知節(jié)點(diǎn)覆蓋感知整個(gè)感知任務(wù)。選擇出最優(yōu)的參與節(jié)點(diǎn)集合來滿足感知任務(wù)需求。

首先要考慮節(jié)點(diǎn)軌跡對(duì)感知區(qū)域的覆蓋的條件，即滿足對(duì)每個(gè)基本感知單元至少有一個(gè)感知節(jié)點(diǎn)經(jīng)過。從所有感知節(jié)點(diǎn)集合中選擇出最小感知節(jié)點(diǎn)數(shù)量，并保障感知節(jié)點(diǎn)軌跡能完全覆蓋全部基本感知單元。最小化感知節(jié)點(diǎn)數(shù)量，能保障對(duì)每個(gè)參與感知節(jié)點(diǎn)發(fā)放固定激勵(lì)時(shí)，總激勵(lì)最少;同時(shí)，最小化感知節(jié)點(diǎn)數(shù)量，能保證使用NTCS方式采集數(shù)據(jù)時(shí)進(jìn)一步減少總的提交次數(shù)，如圖2所示。

為從所有可用節(jié)點(diǎn)集合中，挑選出最優(yōu)節(jié)點(diǎn)組合，本文設(shè)計(jì)了一個(gè)區(qū)域全覆蓋最少路徑選擇算法。給出問題定義，從節(jié)點(diǎn)集合L*中選出一個(gè)子集L，保證L中的節(jié)點(diǎn)的移動(dòng)軌跡集合并集等于S，并使集合L的元素個(gè)數(shù)最少。

該問題可以進(jìn)一步近似為一個(gè)集合覆蓋問題，設(shè)計(jì)用貪婪算法求解。將所有感知節(jié)點(diǎn)按照其優(yōu)先度排序，優(yōu)先度考慮軌跡長(zhǎng)度與節(jié)點(diǎn)可信度。按優(yōu)先度作為選擇感知節(jié)點(diǎn)的標(biāo)準(zhǔn)來選出參與感知任務(wù)節(jié)點(diǎn)，保障區(qū)域全覆蓋。具體求解過程見算法1。

3.3 基于感知節(jié)點(diǎn)移動(dòng)軌跡的壓縮感知數(shù)據(jù)采集

感知節(jié)點(diǎn)由初始位置移動(dòng)到目的位置，在移動(dòng)過程中對(duì)經(jīng)過的每個(gè)基本感知單元進(jìn)行數(shù)據(jù)采集。

對(duì)于節(jié)點(diǎn)Pl其軌跡經(jīng)過nl個(gè)基本感知單元獲得的感知數(shù)據(jù)為：

根據(jù)壓縮感知理論，提出節(jié)點(diǎn)軌跡壓縮感知數(shù)據(jù)采集方式NTCS，定義節(jié)點(diǎn)提交的一個(gè)測(cè)量值為：

其中φij為采集系數(shù)，對(duì)于每個(gè)感知單元，節(jié)點(diǎn)利用ml個(gè)不同的采集系數(shù)，對(duì)當(dāng)前單元的感測(cè)數(shù)據(jù)加權(quán)，形成ml個(gè)測(cè)量值存儲(chǔ)，以后每經(jīng)過一個(gè)感知單元便形成ml個(gè)測(cè)量值，與上一區(qū)域的存儲(chǔ)值相加形成新的ml個(gè)測(cè)量值，直到節(jié)點(diǎn)經(jīng)過軌跡上所有任務(wù)區(qū)域，提交最后存儲(chǔ)的ml個(gè)測(cè)量值。如圖3（b）所示。

NTCS將多個(gè)基本感知單元的數(shù)據(jù)相加后一次提交，降低了數(shù)據(jù)提交次數(shù)，為保障對(duì)任務(wù)數(shù)據(jù)的恢復(fù)質(zhì)量，提交過程中需要提交ml個(gè)數(shù)據(jù)，但ml要遠(yuǎn)小于nl;同時(shí)感知節(jié)點(diǎn)無需實(shí)時(shí)傳輸測(cè)量數(shù)據(jù)，可以在到達(dá)目的地點(diǎn)后通過Wi-Fi來進(jìn)行數(shù)據(jù)傳輸，降低節(jié)點(diǎn)的傳輸開銷。傳輸成本與直接提交相比降低為原來的ml/nl，而且感知節(jié)點(diǎn)移動(dòng)軌跡覆蓋感知單元越多，傳輸成本降低越大。

3.4 基于壓縮感知的軌跡數(shù)據(jù)恢復(fù)算法

任務(wù)分配方案需要考慮壓縮感知恢復(fù)算法中的需求，故在說明對(duì)感知節(jié)點(diǎn)的任務(wù)分配方案之前，首先來介紹壓縮感知對(duì)節(jié)點(diǎn)采集數(shù)據(jù)的恢復(fù)方法。

壓縮感知的信號(hào)重建問題（10）：

s.t. Y=Φ*α（17）式（17）與式（10）是一樣的，還有必要重復(fù)嗎？請(qǐng)明確

實(shí)質(zhì)是對(duì)低維信號(hào)Y進(jìn)行高緯度稀疏重建，其中矩陣Φ*必須滿足有約束等距性質(zhì)（RIP），RIP是為了滿足高維的稀疏信號(hào)α和低維信號(hào)Y的一一對(duì)應(yīng)，使得Y中能完全保留α中的信息。

測(cè)量矩陣的構(gòu)建基于降維矩陣Φ*和稀疏字典Ψ，由式（8）、（9）可知：

Y=Φ*α=Φ*Ψ-1XC=ΦXC（1816）式（18）與式（11）是一樣的，還有必要重復(fù)嗎？請(qǐng)明確

其中Φ=Φ*Ψ-1為測(cè)量矩陣，即通過測(cè)量矩陣Φ可以直接對(duì)原始信號(hào)進(jìn)行稀疏采集，采集結(jié)果通過求解問題（10）來求解出稀疏系數(shù)α，然后利用式（8）恢復(fù)出原始數(shù)據(jù)。

已有多項(xiàng)研究證明，使用隨機(jī)性來構(gòu)建測(cè)量矩陣Φ，且稀疏字典滿足由正交基構(gòu)成時(shí)，可以使得降維矩陣Φ*=ΦΨ滿足RIP[14，21]，即測(cè)量矩陣Φ中的每個(gè)元素都可以用服從同一個(gè)分布的隨機(jī)變量來獲取。節(jié)點(diǎn)在感知中使用相同的隨機(jī)算法在感知節(jié)點(diǎn)中生成測(cè)量系數(shù)。

對(duì)于感知節(jié)點(diǎn)Pl在通過感知軌跡后提交的測(cè)量值：

同時(shí)提交其對(duì)數(shù)據(jù)采集時(shí)生成的測(cè)量系數(shù)：

從稀疏字典中選取相應(yīng)的稀疏基Ψ，計(jì)算出測(cè)量值對(duì)應(yīng)的滿足RIP的降維矩陣：

此過程求解定義如下：

此問題為組合優(yōu)化問題，可以使用求解l1范數(shù)來近似求解l0范數(shù)問題，將組合優(yōu)化問題轉(zhuǎn)換為凸優(yōu)化問題。

然后通過稀疏字典，計(jì)算出感知節(jié)點(diǎn)Pl的任務(wù)區(qū)域的真實(shí)感測(cè)數(shù)據(jù)。

采用l1范數(shù)最小化的方法重建目標(biāo)稀疏時(shí)，測(cè)量值個(gè)數(shù)m滿足：

其中， μ（θ）為測(cè)量矩陣原始矩陣任意兩個(gè)列向量的歸一化內(nèi)積絕對(duì)值的最大值[22]，反映了測(cè)量矩陣的相關(guān)性。

3.5 感知節(jié)點(diǎn)任務(wù)分發(fā)

在選擇出最佳感知節(jié)點(diǎn)集合后，還需要考慮對(duì)節(jié)點(diǎn)的任務(wù)分發(fā)策略。由于感知節(jié)點(diǎn)的移動(dòng)路徑會(huì)存在相互重疊部分，為避免重復(fù)采集，要明確多個(gè)感知節(jié)點(diǎn)經(jīng)過的相同感知單元的任務(wù)分配方案;雖然NTCS可以減小感測(cè)值數(shù)量，由分析可知，測(cè)量值的個(gè)數(shù)取決于真實(shí)采集數(shù)據(jù)的長(zhǎng)度和稀疏度，在節(jié)點(diǎn)的軌跡覆蓋感知單元極少的情況下，達(dá)不到理想效果，雖然本文在節(jié)點(diǎn)選擇時(shí)，已經(jīng)選擇出最優(yōu)的感知節(jié)點(diǎn)集合，但仍然需要根據(jù)節(jié)點(diǎn)軌跡覆蓋單元數(shù)量，來為節(jié)點(diǎn)選擇不同的采集方式。

對(duì)于感知節(jié)點(diǎn)使用基于軌跡的壓縮感知數(shù)據(jù)采集方式，傳輸成本會(huì)隨著感知節(jié)點(diǎn)的軌跡長(zhǎng)度增加而降低，因此考慮按軌跡長(zhǎng)度優(yōu)先策略來為節(jié)點(diǎn)重復(fù)覆蓋的單元分配任務(wù)。具體方案如算法2，這樣能使得軌跡長(zhǎng)的節(jié)點(diǎn)的感知任務(wù)單元更多，保證最優(yōu)的傳輸比。

由此可知，當(dāng)節(jié)點(diǎn)感知單元個(gè)數(shù)在nθ以下時(shí)，使用NTCS數(shù)據(jù)采集方式并沒有減少工作量，故節(jié)點(diǎn)的感知任務(wù)數(shù)少于nθ時(shí)使用基準(zhǔn)測(cè)量方式，即感知節(jié)點(diǎn)測(cè)得數(shù)據(jù)后直接上傳。

3.6 基于缺失值推理的感知節(jié)點(diǎn)可信度

在感知節(jié)點(diǎn)提交所有的測(cè)量數(shù)據(jù)后，對(duì)感知節(jié)點(diǎn)的可信程度作出適當(dāng)?shù)耐茢?，來?duì)感知節(jié)點(diǎn)建立可信等級(jí)，以作為下次感知任務(wù)分配時(shí)的參考，這里采用缺失值推斷技術(shù)[23]。缺失值推斷技術(shù)的前提也是基于感知單元中的感知數(shù)據(jù)的相關(guān)性，這與壓縮感知技術(shù)的使用前提相同。

服務(wù)器恢復(fù)出所有基本感知單元的感知數(shù)據(jù)記作：

對(duì)于任意節(jié)點(diǎn)Pl∈L，其任務(wù)覆蓋單元的感知數(shù)據(jù)記作Xl。

構(gòu)建缺失矩陣l，l為移除節(jié)點(diǎn)Pl的感知數(shù)據(jù)后剩余的感知數(shù)據(jù)，即對(duì)所有xl，xl∈Xl，令xl=0。

利用缺失值矩陣，根據(jù)數(shù)據(jù)實(shí)際地理位置的空間相關(guān)性，利用缺失值恢復(fù)算法R恢復(fù)矩陣中的缺失值：

l為恢復(fù)矩陣，恢復(fù)了節(jié)點(diǎn)的感知數(shù)據(jù)，記作l，ll。

對(duì)Xl和l作誤差計(jì)算，由于每個(gè)節(jié)點(diǎn)感知任務(wù)的感知單元個(gè)數(shù)不同，故求平均誤差。

可信度評(píng)定函數(shù)為：

按照上述定義，對(duì)所有感知節(jié)點(diǎn)逐個(gè)計(jì)算可信度el。可信度可以衡量感知節(jié)點(diǎn)提交的感知數(shù)據(jù)的整體質(zhì)量，對(duì)節(jié)點(diǎn)在感知任務(wù)中的可信程度、工作效用最初做出評(píng)價(jià)。此句不通順，“最初”是否應(yīng)該為“作出”？請(qǐng)明確

4 實(shí)驗(yàn)與仿真評(píng)估

為評(píng)價(jià)分析CS-TD性能，基于Matlab對(duì)CS-TD進(jìn)行仿真實(shí)驗(yàn)，作為比較也實(shí)現(xiàn)了CrowdTasker[6]算法。仿真實(shí)驗(yàn)如下。

4.1 CS-TD感知節(jié)點(diǎn)成本

在CS-TD模型中感知節(jié)點(diǎn)采用NTCS方式采集數(shù)據(jù)，對(duì)于NTCS節(jié)點(diǎn)的感知成本主要取決于節(jié)點(diǎn)的任務(wù)量，實(shí)驗(yàn)考慮不同任務(wù)量下的節(jié)點(diǎn)成本;同時(shí)，感知成本結(jié)構(gòu)也會(huì)影響感知節(jié)點(diǎn)的總成本，實(shí)驗(yàn)參數(shù)設(shè)置見表2，同時(shí)為對(duì)比方便，也將CrowdTasker中感知節(jié)點(diǎn)成本設(shè)定作為參考;最后，為保證壓縮感知恢復(fù)算法能從感知節(jié)點(diǎn)的測(cè)量數(shù)據(jù)中恢復(fù)出完整感知數(shù)據(jù)，故要考慮感知數(shù)據(jù)的稀疏度來確定感知節(jié)點(diǎn)的數(shù)據(jù)采集量。

經(jīng)過100次以上的模擬實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖4所示。為了更清楚地分析不同量級(jí)的數(shù)據(jù)量、感知成本結(jié)構(gòu)、稀疏度對(duì)節(jié)點(diǎn)成本的影響，更多實(shí)驗(yàn)結(jié)果如表3所示。CrowdTasker列代表以CrowdTasker中的數(shù)據(jù)采集方式，節(jié)點(diǎn)的感知成本，其余三列為在不同的數(shù)據(jù)稀疏度下，采用NTCS方式的節(jié)點(diǎn)感知成本。圖4和表3綜合分析了在節(jié)點(diǎn)任務(wù)量不同、不同感知節(jié)點(diǎn)成本結(jié)構(gòu)、不同數(shù)據(jù)稀疏度下時(shí)使用NTCS方式的感知節(jié)點(diǎn)的成本。

NTCS考慮用戶軌跡，感知節(jié)點(diǎn)采集多個(gè)感知單元的數(shù)據(jù)。CrowdTasker考慮的是感知節(jié)點(diǎn)的歷史通話記錄，在節(jié)點(diǎn)連接附近運(yùn)營(yíng)商基站通話時(shí)上傳數(shù)據(jù)，只能參與單個(gè)感知單元任務(wù)。

實(shí)驗(yàn)結(jié)果顯示，最優(yōu)的情況是在目標(biāo)感知數(shù)據(jù)稀疏度為5%，CC=1，Ct=50的情況下，與CrowdTasker相比NTCS方式使節(jié)點(diǎn)成本降低了74%。綜合考慮各種情況，平均節(jié)點(diǎn)成本降低了60%。在3.5節(jié)中已說明在任務(wù)數(shù)過少的情況下，NTCS方式不會(huì)表現(xiàn)出優(yōu)勢(shì)，如表3中所示，在任務(wù)數(shù)為1時(shí)，采用NTCS節(jié)點(diǎn)成本高于CrowdTasker節(jié)點(diǎn)成本。

圖4中感知數(shù)據(jù)的稀疏度對(duì)節(jié)點(diǎn)成本表現(xiàn)出一定的影響，根據(jù)壓縮感知理論，數(shù)據(jù)稀疏度決定了感知節(jié)點(diǎn)數(shù)據(jù)采集量，數(shù)據(jù)的稀疏度越低感知節(jié)點(diǎn)采集的數(shù)據(jù)量越少，感知成本越低。

4.2 感知任務(wù)規(guī)模和CS-TD整體效益

實(shí)驗(yàn)使用感知單元全覆蓋的數(shù)據(jù)感知場(chǎng)景，使用CrowdTasker作為對(duì)比算法，比較采用CS-TD任務(wù)分發(fā)機(jī)制的總體成本。CrowdTasker中使用機(jī)會(huì)呼叫上傳，不考慮傳輸開銷;參考文獻(xiàn)[6]中對(duì)固定激勵(lì)和額外激勵(lì)的設(shè)定，對(duì)兩種算法進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)中設(shè)定稀疏度為10%，CS-TD中只考慮節(jié)點(diǎn)具有固定的感知任務(wù)數(shù)量，實(shí)驗(yàn)結(jié)果如圖5所示?？v坐標(biāo)表示與CrowdTasker相比，CS-TD成本降低比。

在總?cè)蝿?wù)量與節(jié)點(diǎn)軌跡長(zhǎng)度數(shù)量級(jí)相當(dāng)時(shí)，部分感知節(jié)點(diǎn)的任務(wù)量波動(dòng)較大，故整體消耗會(huì)出現(xiàn)波動(dòng);當(dāng)總?cè)蝿?wù)量充足時(shí)，CS-TD總感知成本趨于平穩(wěn)。CS-TD在區(qū)域數(shù)據(jù)的稀疏度為10%的情況下，從感知節(jié)點(diǎn)的四組軌跡長(zhǎng)度數(shù)據(jù)的實(shí)驗(yàn)結(jié)果來看，CS-TD的整體成本較均CrowdTasker減小了30%以上。此句不通順，作相應(yīng)修改CS-TD方案下的任務(wù)整體成本較CrowdTasker減小了30%以上。

5 結(jié)語

針對(duì)移動(dòng)群智感知中區(qū)域覆蓋感知任務(wù)的成本過高的問題，本文綜合考慮了節(jié)點(diǎn)移動(dòng)軌跡和最小化節(jié)點(diǎn)數(shù)量，基于壓縮感知理論，設(shè)計(jì)了基于壓縮感知的移動(dòng)群智感知任務(wù)分配方案——CS-TD，進(jìn)一步降低了節(jié)點(diǎn)的測(cè)量和傳輸成本，從而減少了整體感知任務(wù)的綜合成本，通過仿真實(shí)驗(yàn)分析，與已有的算法CrowdTasker相比，CS-TD方案下整體成本至少減小了30%。

參考文獻(xiàn) （References）

[1] HU K， SIVARAMAN V， LUXAN B G， et al. Design and evaluation of a metropolitan air pollution sensing system [J]. IEEE Sensors Journal， 2016， 16（5）： 1448-1459.

[2] MARJANOVIC M， GRUBESA S， ZARKO I P. Air and noise pollution monitoring in the city of Zagreb by using mobile crowdsensing [C]// Proceedings of the 2017 International Conference on Software， Telecommunications and Computer Networks. Piscataway， NJ： IEEE; 2017： 1-5.

[3] HO C J， VAUGHAN J W. Online task assignment in crowdsourcing markets [C]// Proceedings of the 2012 the National Conference on Artificial Intelligence. Los Angeles： AI Access Foundation， 2012： 45-51.

[4] ZHAO Q， ZHU Y， ZHU H， et al. Fair energy-efficient sensing task allocation in participatory sensing with smartphones [J]. The Computer Journal， 2017， 60（6）： 850-865.

[5] ZHANG D， XIONG H， WANG L， et al. CrowdRecruiter： selecting participants for piggyback crowdsensing under probabilistic coverage constraint [C]// Proceedings of the 2014 ACM International Joint Conference on Pervasive and Ubiquitous Computing. New York： ACM， 2014： 703-714.

[6] XIONG H， ZHANG D， CHEN G， et al. CrowdTasker： maximizing coverage quality in piggyback crowdsensing under budget constraint [C]// Proceedings of the 2015 IEEE International Conference on Pervasive Computing and Communications. Piscataway， NJ： IEEE; 2015： 55-62.

[7] 徐哲，李卓，陳昕.面向移動(dòng)群智感知的多任務(wù)分發(fā)算法[J].計(jì)算機(jī)應(yīng)用，2017，37（1）：18-23.（XU Z， LI Z， CHEN X. Multitask assignment algorithm for mobile crowdsensing [J]. Journal of Computer Applications， 2017， 37（1）： 18-23.）

[8] LIU Y， GUO B， WANG Y， et al. TaskMe： multi-task allocation in mobile crowd sensing [C]// Proceedings of the 2018 IEEE Transactions on Mobile Computing. Piscataway， NJ： IEEE， 2018： 403-414.

[9] XIONG H， ZHANG D， CHEN G， et al. iCrowd： near-optimal task allocation for piggyback crowdsensing [J]. IEEE Transactions on Mobile Computing， 2016， 15（8）： 2010-2022.

[10] WANG L， ZHANG D， YANG D， et al. SPACE-TA： cost-effective task allocation exploiting intradata and interdata correlations in sparse crowdsensing [J]. ACM Transactions on Intelligent Systems & Technology， 2018， 9（2）： 1-28.

[11] AHMED A， YASUMOTO K， YAMAUCHI Y， et al. Distance and time based node selection for probabilistic coverage in people-centric sensing [C]// Proceedings of the 2011 Annual IEEE Communications Society Conference on Sensor. Washington， DC： IEEE Computer Society， 2011： 134-142.

[12] 趙東，馬華東，劉亮.移動(dòng)群智感知質(zhì)量度量與保障[J].中興通訊技術(shù)，2015，21（6）：2-5.（ZHAO D， MA H D， LIU L. Quality measuring and assurance for mobile crowd sensing [J]. ZTE Technology Journal， 2015， 21（6）： 2-5.）

[13] MATTHEW R， ZHANG Y， WALTER W， et al. Spatio-temporal compressive sensing and Internet traffic matrices （Extended Version） [J]. IEEE/ACM Transactions on Networking， 2012， 20（3）： 662-676.

[14] 石光明，劉丹華，高大化，等.壓縮感知理論及其研究進(jìn)展[J].電子學(xué)報(bào)，2009，37（5）：1070-1081.（SHI G M， LIU D H， GAO D H， et al. Advances in theory and application of compressed sensing [J]. Acta Electronica Sinica， 2009， 37（5）： 1070-1081.）

[15] 宋洋，黃志清，張嚴(yán)心，等.基于壓縮感知的無線傳感器網(wǎng)絡(luò)動(dòng)態(tài)采樣方法[J].計(jì)算機(jī)應(yīng)用，2017，37（1）：183-187.（SONG Y， HUANG Z Q， ZHANG Y X， et al.） Dynamic sampling method for wireless sensor network based on compressive sensing [J]. Journal of Computer Applications， 2017， 37（1）： 183-187.）

[16] KONG L， HE L， LIU X Y， et al. Privacy-preserving compressive sensing for crowdsensing based trajectory recovery [C]// Proceedings of the 2015 International Conference on Distributed Computing Systems. Piscataway， NJ： IEEE， 2015： 31-40.

[17] 楊學(xué)峰，程耀瑜，王高.基于小波域壓縮感知的遙感圖像超分辨算法[J].計(jì)算機(jī)應(yīng)用，2017，37（5）：1430-1433.（YANG X F， CHENG Y Y， WANG G. Super-resolution algorithm for remote sensing images based on compressive sensing in wavelet domain [J]. Journal of Computer Applications， 2017， 37（5）： 1430-1433.）

[18] WANG L， ZHANG D， PATHAK A， et al. CCS-TA： quality-guaranteed online task allocation in compressive crowdsensing [C]// Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing. New York： ACM; 2015： 683-694.

[19] HSIEH H P， LIN S D， ZHENG Y. Inferring air quality for station location recommendation based on urban big data [C]// Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM; 2015： 437-446.

[20] CANDES E J， TAO T. Decoding by linear programming [J]. IEEE Transactions on Information Theory， 2005， 51（12）： 4203-4215.

[21] DAVENPORT M A. Random observations on random observations： Sparse signal acquisition and processing [D]. Houston： Rice University， 2010： 1-187.

[22] 王強(qiáng)，張培林，王懷光，等.壓縮感知中測(cè)量矩陣構(gòu)造綜述[J].計(jì)算機(jī)應(yīng)用，2017，37（1）：188-196.（WANG Q， ZHANG P L， WANG H G， et al. Survey on construction of measurement matrices in compressive sensing [J]. Journal of Computer Applications， 2017， 37（1）： 188-196.）

[23] 潘立強(qiáng)，李建中，駱吉洲.傳感器網(wǎng)絡(luò)中一種基于時(shí)空相關(guān)性的缺失值估計(jì)算法[J].計(jì)算機(jī)學(xué)報(bào)，2010，33（1）： 1-11.（PAN L Q， LI J Z， LUO J Z. A Temporal and spatial correlation based missing values imputation algorithm in wireless sensor networks [J]. Chinese Journal of Computers， 2010， 33（1）： 1-11.）