平均信息年齡敏感的移動群智感知機制研究

鄭 俊,肖明軍

1(中國科學技術大學 軟件學院,江蘇 蘇州 215000)

2(中國科學技術大學 計算機科學與技術學院,合肥 230027)

3(中國科學技術大學 蘇州高等研究院,江蘇 蘇州 215000)

1 引 言

隨著移動互聯(lián)網(wǎng)的迅猛發(fā)展,移動群智感知成為了一種極具吸引力的數(shù)據(jù)交互模式.典型的移動群智感知系統(tǒng)由一個部署在云上的平臺和一些移動用戶組成.通過云平臺,數(shù)據(jù)需求者們可發(fā)布感知數(shù)據(jù)收集任務并雇傭移動用戶完成感知任務.移動用戶則使用手機、可穿戴設備等移動設備來手機感知數(shù)據(jù)并定期將數(shù)據(jù)傳輸給平臺以換取報酬.

信息年齡定義為從該數(shù)據(jù)的最新版本產生時刻起到現(xiàn)在為止經過的時間.信息年齡是一種新穎的用來表征數(shù)據(jù)的新鮮程度或實時狀態(tài)更新頻率的評價指標.信息年齡追求的目標既不同于確保收到的數(shù)據(jù)更新具有最小的延遲,又不同于最大化通信系統(tǒng)的利用率.最大化通信系統(tǒng)的利用率只需要讓移動用戶盡快發(fā)送數(shù)據(jù)更新包,然而這會導致數(shù)據(jù)包積壓在平臺隊列或通信鏈路中,從而導致數(shù)據(jù)更新延遲.

目前已有許多移動群智感知方向的研究工作,移動群智感知激勵機制的相關研究是其中重要的一環(huán),常見研究方案包括拍賣方案,博弈算法等.但是傳統(tǒng)的移動群智感知激勵機制設計大多致力于最優(yōu)化參與方的經濟效益,沒有把信息新鮮度考慮在內或是作為優(yōu)化目標.移動設備手機或產生的數(shù)據(jù)變化極快,為了保證移動群智感知系統(tǒng)收集的感知數(shù)據(jù)的可用性和有效性,需要保證這些數(shù)據(jù)的實時狀態(tài)更新.因此,在移動群智感知系統(tǒng)中,確定每個移動用戶向平臺更新數(shù)據(jù)的頻率就顯得尤為重要.太慢的數(shù)據(jù)更新頻率會導致數(shù)據(jù)被平臺接受到時就已經過時,因此數(shù)據(jù)的信息年齡偏高.然而,因為移動群智感知系統(tǒng)是多個用戶競爭向一個平臺傳輸數(shù)據(jù)的系統(tǒng),太快的數(shù)據(jù)更新頻率會導致數(shù)據(jù)在平臺處排隊甚至是在鏈路中擁塞,導致實際上數(shù)據(jù)的信息年齡反而升高.因此,如何給每個移動用戶確定一個適當?shù)臄?shù)據(jù)更新頻率使得移動群智感知系統(tǒng)的數(shù)據(jù)的信息新鮮程度滿足要求,是一個具有挑戰(zhàn)性的問題.

為了解決上述挑戰(zhàn),本文提出了平均信息年齡敏感的移動群智感知機制設計.該機制的優(yōu)化目標是推導出移動用戶的平均信息年齡并保證其低于系統(tǒng)給定的閾值,以此來指導移動用戶選擇適當?shù)臄?shù)據(jù)更新頻率.首先本文對移動群智感知系統(tǒng)進行建模并對數(shù)據(jù)新鮮度機制設計進行問題形式化.然后利用排隊論知識,首先推導單個或多個同質的移動用戶的移動群智感知系統(tǒng)的平均信息年齡表征.考慮了3種符合實際的先到先服務隊列設置:到達率和處理率都服從泊松分布,或者到達率服從泊松分布而處理時間固定,或者到達率固定而處理率服從泊松分布,并分別推導出相應的平均信息年齡表達式.以此作為基礎,本文進一步推導出多個同質的移動用戶的移動群智感知系統(tǒng)的平均信息年齡表征,進而給出了信息新鮮度閾值限定下,移動用戶可選的數(shù)據(jù)更新頻率范圍.

2 相關工作

移動群智感知是學術研究中熱門且經典的研究方向.在這個領域有相當多的研究工作[1].例如Zhang等人基于在線反向拍賣設計了3種在線激勵機制[2],實現(xiàn)了平臺效益最大化和保證了拍賣的誠實性.Yang等人針對以平臺為中心的系統(tǒng)設計了一個基于斯塔爾伯格博弈的激勵機制[3],而面對以用戶為中心的系統(tǒng)則轉而采用了基于拍賣的激勵機制.Song等人設計了一個激勵機制用于解決工人選擇問題[4],通過將任務分配問題建模成一個組合多臂老虎機模型,該機制能最小化工人結果的經驗熵.然而,這些現(xiàn)存的工作都只考慮了最大化效益的問題,沒有將信息新鮮度(AgeofInformation,AoI)納入考慮范疇.而隨著移動互聯(lián)網(wǎng)的發(fā)展,對信息新鮮度的要求也與日俱增.因此現(xiàn)有的工作無法解決優(yōu)化目標中涉及到信息新鮮度的激勵機制設計問題.

AoI是一個被廣泛使用的評判信息新鮮度的標準.AoI是指從最新的信息產生依賴經過的時間.在近些年有大量AoI領域的研究工作[5-7].AoI領域的博弈論相關工作主要研究如何最小化AoI花銷[8-12].然而,大多數(shù)研究工作沒有跟迅猛發(fā)展的移動群智感知相結合.而且,為了簡化工作,他們通常不區(qū)分不同的移動用戶,從而將AoI排隊系統(tǒng)視為單源排隊系統(tǒng).相比之下,本文的工作同時考慮了多同質移動用戶和多異質移動用戶競爭的排隊論系統(tǒng),更符合實際情況.

3 模型總覽

移動群智感知系統(tǒng)的整體流程如圖1所示并可以具體描述如下:首先,平臺向移動用戶發(fā)布感知任務,感興趣并樂意參與的N個移動用戶做出回應.其次,平臺決定自己的報價策略,移動用戶決定自己的數(shù)據(jù)傳輸頻率策略.再次,移動用戶以一定頻率向平臺傳輸感知數(shù)據(jù).平臺持續(xù)更新聚合數(shù)據(jù)并進行分析,并向每個用戶支付基于報價策略的報酬.

圖1 系統(tǒng)總體結構圖Fig.1 System overview

4 單(多同質)移動用戶的信息新鮮度研

本章通過分析信息年齡曲線來推導出單個移動用戶或者多個同質移動用戶時平均信息年齡的表達式.多個同質移動用戶是指多個移動用戶的數(shù)據(jù)包很相似,平臺在處理和排隊時不加以特定區(qū)分,一起排隊處理,僅計數(shù)并在結算時加以區(qū)分,因此可以將系統(tǒng)等價為只有一個移動用戶的排隊系統(tǒng).信息年齡的示例曲線如圖2所示.

圖2 信息新鮮度示意圖Fig.2 Example of AoI

因為AoI是從最新收到數(shù)據(jù)包的產生時間開始計算,它實際上包含了鏈路傳輸時間、到達平臺后在隊列中的等待時間等.因此AoI曲線會隨著時間線性增加并在接收到一個新的數(shù)據(jù)包后斷崖式下跌,最終呈現(xiàn)一個鋸齒形.

(1)

從圖2中可以看出,區(qū)域Qi可以被表示為相鄰兩個等腰直角三角形的面積差.定義Xi為數(shù)據(jù)包i-1和數(shù)據(jù)包i的生成時間之間的差值,即Xi=ti-ti-1.則Qi可以被表示為:

(2)

將式(2)代入式(1)中,平均AoI可以被重寫為:

(3)

(4)

則f1正是該移動用戶的數(shù)據(jù)更新頻率,顯然其極限是存在的.則可以重寫平均AoI如下:

(5)

式(5)中E[.]是期望運算符,X和T分給是與鏈路傳輸時間和平臺處理時間對應的隨機變量.并且式中平均AoI的計算基于系統(tǒng)服務遍歷性的弱假設,即該系統(tǒng)需要遍歷所有數(shù)據(jù)包而不允許隨意丟棄任何數(shù)據(jù)包.該式是先到先服務隊列系統(tǒng)中處理AoI相關問題的常規(guī)性推導結果.然而,要進一步推導計算平均AoI依然是一個極具挑戰(zhàn)性的任務.首先考慮一種特殊情況,X是系統(tǒng)當前數(shù)據(jù)包和上一個數(shù)據(jù)包的生成時間的差值的隨機變量,而T是描述上述兩個數(shù)據(jù)包的系統(tǒng)時間的隨機變量.這種假設情況下X與T是相互獨立的隨機變量,問題得到簡化并很容易求解.然而實際情況更為復雜,當時間間隔X很大時,意味著系統(tǒng)隊列是空的,此時將產生一小段等待時間和系統(tǒng)時間T.這種情況下的X與T是不再是相互獨立的隨機變量,而是負相關的,這使得E[XT]的計算變得復雜很多.

4.1 M/M/1隊列的信息新鮮度研究

對于數(shù)據(jù)更新包i而言,其系統(tǒng)時間可以表示如下:

Ti=Wi+Hi

(6)

式(6)中Wi和Hi分別表示數(shù)據(jù)更新包i的等待時間和處理時間.接下來分兩種情況討論:第1種情況是當數(shù)據(jù)更新包i產生時,數(shù)據(jù)更新包i-1已經被平臺處理完成,此時Wi=0;第2種情況是數(shù)據(jù)更新包i產生時刻,數(shù)據(jù)更新包i-1正在系統(tǒng)隊列中排隊等待處理或者正在被處理,此時Wi=Ti-1-Xi.綜合考慮這兩種情況,可以將數(shù)據(jù)更新包i的等待時間Wi重寫如下:

Wi=(Ti-1-Xi)+

(7)

注意到Ti-1獨立于Xi.當系統(tǒng)處于穩(wěn)定狀態(tài)時,系統(tǒng)時間T是隨機同分布的,即T=Ti=Ti-1.由排隊論知識可推導出,M/M/1系統(tǒng)中系統(tǒng)時間T的概率密度函數(shù)為:

fT(t)=μ(1-ρ)e-μ(1-ρ)t,t≥0

(8)

則給定Xi=x條件下等待時間Wi的期望值可以表示如下:

(9)

因此,注意到處理時間Hi獨立于Xi,這允許重寫E[XT]=E[XiTi]如下:

E[TiXi]=E[(Wi+Hi)Xi]=E[WiXi]+E[Hi]E[Xi]

(10)

(11)

(12)

4.2 M/D/1隊列的信息新鮮度研究

本章節(jié)考慮M/D/1隊列系統(tǒng),該系統(tǒng)中移動用戶的數(shù)據(jù)包到達服從泊松分布,但平臺的服務時間是固定的.這個設定也比較符合移動群智感知系統(tǒng)中平臺的實際情況,因為在同一個感知任務中,平臺將任務分發(fā)給不同的移動用戶去完成,最終從不同移動用戶處收集的感知數(shù)據(jù)的形式、大小、內容分布等較為相似,因此平臺可以在固定的服務時間內完成處理.

Ti=Wi+C

(13)

其中Wi和C分別表示數(shù)據(jù)更新包i的等待時間和處理時間.于是有式子如下:

E[XiTi]=E[XiWi]+DE[Xi]

(14)

類似公式(9),可推導出式子如下:

(15)

其中,有階躍函數(shù)如下:

(16)

于是可以求得:

(17)

概率密度函數(shù)fY(y)對應的概率分布函數(shù)為:

(18)

同理,將公式(18)代入公式(15)中,可得E[Wi∣Xi=x],再代入公式(11)中,可求得E[WiXi].將E[WiXi]代入公式(5)中,最終可求得平均信息年齡δ.

4.3 D/M/1隊列的信息新鮮度研究

(19)

E[XT]=CE[T]

(20)

將公式(19)、公式(20)代入公式(5)中,可以重寫公式(5)如下:

(21)

而平均的系統(tǒng)時間可以表述為式子如下:

(22)

其中:

γ=LX(μ(1-β))

(23)

是到達時間間隔的拉普拉斯變換的解.而此處到達時間間隔固定為C,因此有公式如下:

fX(x)=ε(x-C)

(24)

LX(t)=e-tC

(25)

于是可以重寫γ表達式如下:

(26)

(27)

5 多異構移動用戶競爭的信息新鮮度研究

本章將上述單個或者多個同質移動用戶隊列系統(tǒng)的平均AoI推廣到多異質移動用戶競爭的情形下.此處異質指移動用戶的數(shù)據(jù)包各不相同,平臺排隊時需加以區(qū)分處理.

令T=W+H,此處W和H分別代表系統(tǒng)中所有等待時間和處理時間.H獨立于X,則有:

E(XT)=E(XW)+E(X)E(H)

(28)

(29)

然而,E(XW)的計算是非平凡的,因為X和W并不是相互獨立的而是負相關的.因為當?shù)竭_間隔時間X較大時,意味著多工人競爭的隊列系統(tǒng)仍然可能為空,此時會產生額外的一段等待時間并被記為W.因此問題求解的關鍵轉化為如何求解該非平凡的E(XW).而要求解E(XW)需要用到指數(shù)型隨機變量和泊松過程的相關性質,具體如下.

2.給定X1

fX1∣X1fV∣X1

(30)

引理2.對于給定的速率為f1的泊松過程N(t),和一個與其獨立的指數(shù)型隨機變量X,在[0,X]區(qū)間內的到達數(shù)N(X) 的概率質量函數(shù)PN(X)(n)可表示如下:

PN(X)(n)=(1-γ)γn,n≥0

(31)

這兩個引理的證明較為容易,此處不在贅述.

要設法求得該非平凡的E(XW),令Xj,Wj和Tj分別表示移動用戶i的數(shù)據(jù)包j的到達時間間隔,等待時間及系統(tǒng)時間.于是可以將Wj劃分為如下兩個區(qū)間:

Aj={Xj

(32)

區(qū)間Aj意味著移動用戶i的數(shù)據(jù)包j的到達時間間隔比較短,具體來說是短于該系統(tǒng)處理移動用戶i的數(shù)據(jù)包j-1的系統(tǒng)時間.而區(qū)間Gj則正好相反,表明移動用戶i的數(shù)據(jù)包j的到達時間間隔較長,長于該系統(tǒng)處理移動用戶i的數(shù)據(jù)包j-1的系統(tǒng)時間.于是,通過劃分為兩個區(qū)間,可以將E(XW)重寫如下:

E(XjWj)=E(XjWj|Gj)P[Gj]+E(XjWj|Aj)P[Aj]

(33)

因為該排隊系統(tǒng)只有一個用于服務的平臺,所以移動用戶i的數(shù)據(jù)包與其他所有移動用戶的數(shù)據(jù)包被平臺處理所需的處理時間都是相同的指數(shù)型隨機變量μ.與單個用戶或者多個同質用戶的隊列系統(tǒng)排比,該多移動用戶的隊列系統(tǒng)仍然是M/M/1先到先服務隊列系統(tǒng),只是系統(tǒng)的總負載率變?yōu)榱甩?ρi+ρ-i.當該排隊系統(tǒng)處于穩(wěn)定狀態(tài)時,系統(tǒng)時間Tj-1的指數(shù)為μ-f的概率密度函數(shù)可表示如下:

fT(t)=(μ-f)e-(μ-f)t,t≥0

(34)

此外,系統(tǒng)時間Tj-1與Xj是相互獨立的,因為Tj-1取決于第j-2個數(shù)據(jù)包的處理時間.于是,分兩種情況討論推導后,可得出多異質用戶移動群智感知系統(tǒng)的平均AoI表示成定理形式如下.

(35)

6 實驗評估

本章節(jié)中,使用實驗仿真來詳細評估了單(多同質)和多異質移動用戶情形下的的平均信息年齡表征情況,表明了其正確性和合理性.

6.1 實驗環(huán)境配置

我們采用芝加哥出租車開源數(shù)據(jù)[13]作為真實數(shù)據(jù)集來進行實驗仿真.每一份數(shù)據(jù)都記錄了taxiID,timestamp,trip_miles,trip_seconds及顧客上下車地點等.我們從該開源數(shù)據(jù)庫中選擇了一個27030條數(shù)據(jù)的數(shù)據(jù)集.在實驗仿真中,我們將其看成移動群智感知應用場景,將司機接送乘客看做完成相應的群智感知任務.乘客上下出租車地點看做群智感知中收集數(shù)據(jù)的興趣點(PoI).首先,我們選擇L=15個PoI并找到對應的數(shù)據(jù)庫中的300條出租車行程記錄.其中我們可以選擇N個出租車和M個相應的感知任務.其中N的取值范圍是[50,300],默認值為100.不失一般性,該數(shù)據(jù)集中缺失的少量符合隨機分布的數(shù)據(jù)我們使用高斯分布來生成.

6.2 單(多同質)移動用戶AoI的評估結果

首先,分別觀察單(多同質)移動用戶時,M/M/1,M/D/1,D/M/1這3種先到先服務隊列情形下,改變系統(tǒng)負載率ρ時,平均AoI的變換情況,如圖3所示.隨著系統(tǒng)負載率ρ的增大,3幅曲線的平均AoI都是先減小后增大,存在唯一的最小值.通過具體觀察可知,M/M/1隊列中平均信息年齡取最小值時ρ≈0.53.M/D/1隊列中平均信息年齡取最小值時ρ≈0.625.D/M/1隊列中平均信息年齡取最小值時ρ≈0.515.因此,當系統(tǒng)設定一定的信息新鮮度閾值時,只有中間特定范圍內的ρ滿足系統(tǒng)的信息新鮮度閾值需求.

圖3 單用戶不同隊列AoI圖Fig.3 AoI of single user and different queue

6.3 多異質移動用戶AoI的評估結果

首先測量先到先服務的隊列系統(tǒng)的平均AoI.為了簡化問題和結果的直觀性,假定只存在兩個移動用戶競爭更新數(shù)據(jù),有ρ1+ρ2=ρ.

從圖4(a)可以得出,一個移動用戶的數(shù)據(jù)的平均AoI隨著另一個用戶的AoI的減少而增加.而對于不同的總和ρ而言,與ρ=0.4,0.7,0.8相比,當ρ=0.6時,AoI的總和最小.因此,可以通過調整總和ρ來盡量減小AoI總和,從而保證不超過AoI閾值,使AoI約束得以生效.

圖4 兩競爭用戶AoI圖Fig.4 AoI of two competitive users

從圖4(b)可以得出,隨著總負載ρ的增加,用戶1的AoI逐漸減小,用戶2的AoI逐漸增大,而總AoI先減小后增大,因此AoI總和存在最小值.而對于對稱情況,最小值當用戶1和用戶2的AoI相等時取得.因此可以得出通用性結論:對于多用戶系統(tǒng),AoI閾值約束問題既取悅于總負載ρ,又取決于移動用戶間數(shù)據(jù)更新頻率的分配關系,且平均AoI存在唯一的最優(yōu)值.

綜合上述所有數(shù)據(jù)圖,可以進一步論證本文建模推導的單(多同質)和多異質移動用戶的信息新鮮度表征的正確性和合理性.

7 結 語

本文研究了平均信息年齡敏感的移動群智感知機制設計問題.本文首先給出了移動群智感知中的平均信息年齡的建模和問題形式化.然后逐步推進,先研究了單個或者多個同質用戶情形下的平均信息年齡設計問題,并考慮了3種常見的隊列設置來分別推導其結果.以此作為前提,進一步推導出更符合實際情況的多個異質移動用戶情形下的非平凡的平均信息年齡設計問題,通過一系列復雜的推導過程最終得到表征式.然后,數(shù)值結果的評估結果論證了所設計的所有移動群智感知系統(tǒng)的平均信息年齡的正確性和合理性.未來的工作包括將隊列拓展到后到先服務等其他隊列系統(tǒng),或者同時考慮系統(tǒng)的經濟效益和信息新鮮度問題以達到一種平衡.