邊緣環(huán)境下的移動(dòng)群智感知任務(wù)在線分發(fā)算法

閆琳琳 鄒國(guó)紅

(鞍山師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院,遼寧鞍山 114007)

0 引言

移動(dòng)群智感知是一種結(jié)合移動(dòng)智能終端設(shè)備和“眾包”的新型感知模式,由多名用戶利用嵌入式傳感器作為感知節(jié)點(diǎn),完成對(duì)本地各類數(shù)據(jù)的采集,并通過(guò)相關(guān)平臺(tái)完成對(duì)數(shù)據(jù)的融合,最終實(shí)現(xiàn)整個(gè)區(qū)域內(nèi)所有用戶的感知[1]。由于移動(dòng)群智感知具備靈活性、低成本、范圍廣等優(yōu)勢(shì),因此被廣泛應(yīng)用于各類環(huán)境感知、基礎(chǔ)設(shè)施感知等領(lǐng)域當(dāng)中[2]。但由于當(dāng)前移動(dòng)群智感知任務(wù)的分發(fā)算法存在諸多問(wèn)題,限制了其發(fā)展,例如存在過(guò)渡獲取用戶信息問(wèn)題;無(wú)法為用戶隱私信息提供保障;分發(fā)任務(wù)與用戶實(shí)際需求不符等問(wèn)題[3]?；诖?本文開展邊緣環(huán)境下的移動(dòng)群智感知任務(wù)在線分發(fā)算法研究。

1 邊緣環(huán)境下的移動(dòng)群智感知任務(wù)在線分發(fā)算法設(shè)計(jì)

1.1 任務(wù)分發(fā)軌跡隱私定義

為確保在對(duì)移動(dòng)群智感知任務(wù)進(jìn)行在線分發(fā)的過(guò)程中,用戶參與者的隱私信息不被泄漏,本文首先對(duì)任務(wù)分發(fā)進(jìn)行軌跡隱私定義[4]。

首先將目的地的隱私定義為非法攻擊者根據(jù)觀察獲取到目的地的概率,其計(jì)算公式為:

其次,在對(duì)位置差分隱私進(jìn)行定義。針對(duì)用戶參與者選擇的每一個(gè)位置,實(shí)現(xiàn)差分隱私保護(hù),將區(qū)域劃分為網(wǎng)格結(jié)果,用戶參與者上報(bào)的位置為網(wǎng)格上的一個(gè)點(diǎn),其在手打擾動(dòng)后的位置也在網(wǎng)格上[5]。在網(wǎng)格當(dāng)中將擾動(dòng)網(wǎng)格集構(gòu)造、上報(bào)概率等進(jìn)行標(biāo)記。根據(jù)擾動(dòng)網(wǎng)格分布函數(shù)引入到網(wǎng)格當(dāng)中,最終數(shù)據(jù)實(shí)際落點(diǎn)即為差分隱私位置節(jié)點(diǎn)。

1.2 基于邊緣環(huán)境的移動(dòng)群智感知分布式任務(wù)獲取

1.2.1 移動(dòng)群智感知任務(wù)競(jìng)爭(zhēng)熱度預(yù)估

引進(jìn)DTA數(shù)據(jù)分布方式,并認(rèn)為提出的每項(xiàng)工作均具備一定競(jìng)爭(zhēng)關(guān)系,只有通過(guò)對(duì)最大化收益進(jìn)行熱度預(yù)估的方式,才能解決競(jìng)爭(zhēng)者熱度不均的問(wèn)題。

為解決此問(wèn)題的直接方式,對(duì)歷史數(shù)據(jù)位置進(jìn)行定位,即按照群智感知方式,假定所有參與者在進(jìn)行任務(wù)獲取中,只能按照規(guī)定要求選擇一個(gè)任務(wù)內(nèi)容,以貪心策略作為選擇依據(jù)[6]。對(duì)任務(wù)競(jìng)爭(zhēng)熱度進(jìn)行預(yù)估,此行為的實(shí)施可用如下計(jì)算公式表示。

公式(2)中:tj表示為預(yù)估的任務(wù)競(jìng)爭(zhēng)熱度;Bj表示為用戶貪心指數(shù);nj表示為任務(wù)發(fā)生實(shí)際需求人數(shù);βj表示為任務(wù)競(jìng)爭(zhēng)人數(shù)。輸出tj實(shí)際值,完成對(duì)競(jìng)爭(zhēng)熱度的預(yù)估。

1.2.2 分發(fā)參與者任務(wù)獲取

根據(jù)上述輸出的tj值,對(duì)分發(fā)的參與者任務(wù)進(jìn)行獲取,此過(guò)程中,應(yīng)考慮到實(shí)際需求人數(shù)與競(jìng)爭(zhēng)人數(shù)之間的關(guān)系,并將任務(wù)實(shí)際收益值進(jìn)行期望評(píng)估,根據(jù)參與者的參與情況進(jìn)行數(shù)據(jù)獲取。

此時(shí),可從任務(wù)的隱私性層面進(jìn)行考慮,選擇具備自我約束能力的路徑進(jìn)行執(zhí)行任務(wù)的獲取,確保獲取的參與者任務(wù)數(shù)據(jù)在滿足隱私路徑的前提下,進(jìn)行任務(wù)數(shù)據(jù)獲取[7]。此行可用如下計(jì)算公式表示。

按照上述計(jì)算公式,綜合參與者的分布概率,完成對(duì)分發(fā)參與者任務(wù)的獲取。

1.2.3 參與者選擇與支付決策

為了實(shí)現(xiàn)對(duì)任務(wù)獲取的最優(yōu)化,應(yīng)從全局優(yōu)化角度考慮,假定存在第三個(gè)可信任方,此時(shí)可要求任務(wù)參與者將有關(guān)任務(wù)以資源公開的方式上傳到CTA平臺(tái),根據(jù)平臺(tái)提供的多種決策性行為,進(jìn)行任務(wù)的分配,以此確保任務(wù)分配的合理化[8]。在此基礎(chǔ)上,追蹤任務(wù)在平臺(tái)上的完成方式,假定任務(wù)者或參與者的選擇與支付決策受到一定行為的約束,此時(shí)決策行為的發(fā)生也將發(fā)生對(duì)應(yīng)的轉(zhuǎn)變[9]。針對(duì)每一個(gè)參與者者對(duì)任務(wù)的完成度,對(duì)其進(jìn)行決策閾值與隱私閾值的劃分,最大執(zhí)行任務(wù)的能力作為路徑任務(wù)能力,此時(shí)約束條件成立[10]。此外,為了確保每個(gè)參與者的收益是均等的,應(yīng)根據(jù)任務(wù)數(shù)量進(jìn)行最終的決策。此時(shí)決策行為表示為如下。

公式(4)中:γ表示為支付決策行為;T表示為任務(wù)矩陣;f表示為執(zhí)行任務(wù)的隱私行為。根據(jù)上述計(jì)算公式,當(dāng)γ=1時(shí),即可認(rèn)為任務(wù)存在有效執(zhí)行行為。

1.3 集中式在線任務(wù)分配

通過(guò)上述研究,本文通過(guò)移動(dòng)群智感知任務(wù)預(yù)分配的方式,提取任務(wù)在線分發(fā)軌跡中的隱私閾值?；谏鲜霁@取的移動(dòng)群智感知任務(wù),在邊緣環(huán)境下進(jìn)行尋優(yōu)分配[11]。在此基礎(chǔ)上,通過(guò)邊緣檢測(cè)的方式,集中式在線任務(wù)分配,以分配收益最高的最優(yōu)分配結(jié)果,反復(fù)迭代,直至移動(dòng)群智感知任務(wù)待分發(fā)數(shù)量與目標(biāo)在線分發(fā)能夠完全匹配時(shí),輸出任務(wù)在線分發(fā)結(jié)果[12]。在此過(guò)程中,一旦出現(xiàn)存在未分發(fā)移動(dòng)群智感知任務(wù)時(shí),必須進(jìn)行第二階段的在線分發(fā),保證全部移動(dòng)群智感知任務(wù)能夠在被分發(fā)完畢的情況下,結(jié)束在線分發(fā)算法迭代求解。以此,實(shí)現(xiàn)集中式在線任務(wù)分配。

表1 兩種分發(fā)算法實(shí)驗(yàn)結(jié)果對(duì)比表Tab.l Comparison of experimental results of two distribution algorithms

2 對(duì)比實(shí)驗(yàn)

本文選擇真實(shí)的數(shù)據(jù)集和人工合成數(shù)據(jù)集作為對(duì)比實(shí)驗(yàn)的測(cè)試案例,分別利用本文提出的移動(dòng)群智感知任務(wù)在線分發(fā)算法和傳統(tǒng)分發(fā)算法,將數(shù)據(jù)集分發(fā)給各個(gè)參與者,最后總結(jié)兩種分發(fā)算法的實(shí)際應(yīng)用效果。將真實(shí)數(shù)據(jù)集設(shè)置為F,分別抽取N和T兩個(gè)地區(qū)用戶的checkin數(shù)據(jù)。實(shí)驗(yàn)過(guò)程中移動(dòng)群智感知數(shù)據(jù)采集場(chǎng)景為平臺(tái)需要對(duì)不同區(qū)域的實(shí)施任務(wù)進(jìn)行調(diào)查。在數(shù)據(jù)集當(dāng)中共包含600個(gè)用戶地址以及400個(gè)移動(dòng)群智感知任務(wù)。實(shí)驗(yàn)開始時(shí),隨機(jī)在數(shù)據(jù)集當(dāng)中選取一個(gè)用戶參與者和一個(gè)任務(wù),為增強(qiáng)本文對(duì)比實(shí)驗(yàn)的魯棒性,每組實(shí)驗(yàn)需要重復(fù)10次,并取10次結(jié)果的均值作為最終的實(shí)驗(yàn)結(jié)果。將正確中選概率作為對(duì)比實(shí)驗(yàn)的評(píng)價(jià)指標(biāo),正確中選概率計(jì)算公式為:

公式(5)中,δ表示為正確中選概率;W表示為10次用戶參與者被正確分配任務(wù)的總數(shù)之和;χ表示為實(shí)驗(yàn)中用戶地址總數(shù),χ取值為600。根據(jù)公式(5),計(jì)算得出兩種分發(fā)算法的正確中選概率,并將其結(jié)果分別進(jìn)行記錄,繪制成如表1所示的實(shí)驗(yàn)結(jié)果對(duì)比表。

由表1中的數(shù)據(jù)可以看出,本文分發(fā)算法正確中選概率明顯高于傳統(tǒng)分發(fā)算法正確中選概率。同時(shí)通過(guò)正確中選概率也能夠進(jìn)一步反映出用戶參與者對(duì)任務(wù)分發(fā)結(jié)果的滿意度。因此,本文分發(fā)算法與傳統(tǒng)分發(fā)算法相比可讓更多用戶參與者得到滿意的任務(wù)。因此,通過(guò)對(duì)比實(shí)驗(yàn)證明,本文提出的邊緣環(huán)境下的移動(dòng)群智感知任務(wù)在線分發(fā)算法,在實(shí)際應(yīng)用中能夠有效提高分發(fā)的精度,將其應(yīng)用于實(shí)際能夠有效提高各類資源的利用效果。

3 結(jié)語(yǔ)

通過(guò)設(shè)計(jì)實(shí)例分析的方式,證明了設(shè)計(jì)任務(wù)在線分發(fā)算法在實(shí)際應(yīng)用中的適用性,以此為依據(jù),證明此次基于邊緣環(huán)境下優(yōu)化設(shè)計(jì)的必要性。因此,有理由相信通過(guò)本文設(shè)計(jì),能夠解決傳統(tǒng)移動(dòng)群智感知任務(wù)在線分發(fā)中存在的缺陷,以此為提高移動(dòng)群智感知任務(wù)在線分發(fā)質(zhì)量提供建議。