劉宏英 聶文梅

摘要：隨著可內(nèi)嵌多種傳感器的智能手機(jī)的快速普及和應(yīng)用，群智感知計(jì)算技術(shù)作為一種新的感知模式逐步發(fā)展起來(lái)。為了解決人們生活中排隊(duì)時(shí)間的不可預(yù)測(cè)問(wèn)題，本文提出了一個(gè)群智感知系統(tǒng)來(lái)監(jiān)測(cè)并預(yù)測(cè)自動(dòng)取款機(jī)排隊(duì)等待時(shí)間。該系統(tǒng)包括能自動(dòng)探測(cè)等待時(shí)間的智能手機(jī)部分和處理收集數(shù)據(jù)以提供精確等待時(shí)間估計(jì)的云后臺(tái)兩部分。該系統(tǒng)通過(guò)為用戶提供精確的等待時(shí)間來(lái)幫助用戶合理利用排隊(duì)等待時(shí)間。

關(guān)鍵詞：群智感知；智能手機(jī)應(yīng)用；排隊(duì)時(shí)間估計(jì)

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.3969/j.issn.l003-6970.2017.08.015

引言

在現(xiàn)實(shí)生活中，很多公共服務(wù)中都存在排隊(duì)問(wèn)題，這給人們的生活帶來(lái)了很多的不便。如果用戶能確定排隊(duì)時(shí)間，則可以在需要等待時(shí)間內(nèi)進(jìn)行其它事務(wù)處理，而不用一直站在隊(duì)列或服務(wù)場(chǎng)所中長(zhǎng)時(shí)間等待。對(duì)于排隊(duì)等待時(shí)間問(wèn)題的傳統(tǒng)解決方法是基于基礎(chǔ)設(shè)施的方法，如布署的照相機(jī)、傳感器或者由藍(lán)牙、Wifi產(chǎn)生的監(jiān)測(cè)信號(hào)。但這種解決方法不僅造價(jià)昂貴而且不利于規(guī)模擴(kuò)展。我們希望得到一種既可以廣泛使用，又不依賴于基礎(chǔ)設(shè)施，而且還精準(zhǔn)又便于使用的方法來(lái)解決排隊(duì)問(wèn)題。

隨著網(wǎng)絡(luò)技術(shù)和移動(dòng)終端設(shè)備的迅速發(fā)展，智能手機(jī)等移動(dòng)終端設(shè)備集成了各式各樣的傳感器。利用移動(dòng)終端里的傳感器提供以人為中心感知與計(jì)算已成為當(dāng)今社會(huì)發(fā)展的趨勢(shì)。所以通過(guò)群智感知來(lái)解決排隊(duì)監(jiān)測(cè)問(wèn)題是可能的。用智能手機(jī)解決排隊(duì)問(wèn)題需要解決兩個(gè)問(wèn)題。第一是我們?cè)谔綔y(cè)等待時(shí)間要用到手機(jī)中的傳感器，這個(gè)過(guò)程會(huì)使用戶的手機(jī)電池在很短時(shí)間內(nèi)消耗用盡。從而使得用戶不愿意參與排隊(duì)等待時(shí)間監(jiān)測(cè)活動(dòng)。第二是雖然我們系統(tǒng)能自動(dòng)收集大量的等待時(shí)間，但這些數(shù)據(jù)仍太稀疏不能直接得到精確的等待時(shí)間。

本文提出并實(shí)現(xiàn)了基于智能手機(jī)的排隊(duì)等待時(shí)間監(jiān)測(cè)系統(tǒng)。該系統(tǒng)將用戶的智能手機(jī)作為排隊(duì)等待時(shí)間監(jiān)測(cè)終端，獲取參與者的測(cè)量數(shù)據(jù)，在后臺(tái)將采集數(shù)據(jù)進(jìn)行處理，進(jìn)而估計(jì)每個(gè)用戶的準(zhǔn)確等待時(shí)間，以此來(lái)幫助用戶了解自己需要等待多長(zhǎng)時(shí)間。

1 相關(guān)工作

由于不同場(chǎng)所的排隊(duì)問(wèn)題都有各自的特點(diǎn)，如等待的條件不同，造成每個(gè)用戶所需服務(wù)的時(shí)間也各不相同，從而每個(gè)用戶所需等待的時(shí)間也不同。這里，為使問(wèn)題易于處理，我們選取自動(dòng)取款機(jī)服務(wù)點(diǎn)作為實(shí)驗(yàn)?zāi)繕?biāo)。由于每個(gè)用戶的操作基本相同，所以每個(gè)用戶的所需服務(wù)時(shí)間大致一樣，便于估計(jì)用戶的等待時(shí)間。

本文將實(shí)驗(yàn)點(diǎn)設(shè)在了一個(gè)自動(dòng)取款服務(wù)點(diǎn)。取款用戶按先進(jìn)先出的排隊(duì)方式取款。用戶排到取款機(jī)之后進(jìn)行自助服務(wù)。用戶完成任務(wù)之后會(huì)立即離開。當(dāng)然也有特殊情況出現(xiàn)，如有人不取款但在取款機(jī)附近停留。我們將這種情況下產(chǎn)生的數(shù)據(jù)作為異常值來(lái)進(jìn)行處理。我們?cè)谧詣?dòng)取款機(jī)旁邊安裝一個(gè)WiFi Access Point（WAP）。這個(gè)WAP的BSSID用于探測(cè)用戶的排隊(duì)時(shí)間。

本文的目的是估算用戶的等待時(shí)間，即用戶從到達(dá)自動(dòng)取款機(jī)到其開始自助取款操作的時(shí)間段。為了掌握等待時(shí)間隨時(shí)間的變化情況，我們實(shí)地觀察了自動(dòng)取款機(jī)一周。通過(guò)觀察發(fā)現(xiàn)自動(dòng)取款機(jī)的用戶等待時(shí)間為3分鐘。觀察表明等待時(shí)間不會(huì)低于2分鐘，最多為5分鐘。這個(gè)時(shí)間范圍有助于我們刪除不切實(shí)際的異常值。

2 等待時(shí)間探測(cè)

本文實(shí)驗(yàn)所用系統(tǒng)如圖1所示。該系統(tǒng)由兩部分組成。一部分稱為客戶端，它運(yùn)行于智能手機(jī)，主要用于探測(cè)等待時(shí)間，并將結(jié)果上傳于服務(wù)器。另一部分在云端，用于處理收集到的數(shù)據(jù)。

客戶端由控制器、手機(jī)狀態(tài)接收器子系統(tǒng)、等待時(shí)間探測(cè)子系統(tǒng)和數(shù)據(jù)上傳子系統(tǒng)四個(gè)部分組成的?？刂破髫?fù)責(zé)管理和處理其它三部分的操作。

2.1 手機(jī)狀態(tài)接收子系統(tǒng)

手機(jī)狀態(tài)接收器在本應(yīng)用中充當(dāng)通知中心的角色。Android提供的通知服務(wù)能令app知道手機(jī)發(fā)生的各種事件，如登錄、重啟、Wi-Fi連接/斷開、Wi-Fi信號(hào)強(qiáng)度的變化等。這些通知可以使app根據(jù)相關(guān)事件做出不同的反應(yīng)。我們則利用該通知服務(wù)來(lái)更好的探測(cè)等待事件以做出不同的反應(yīng)。

手機(jī)狀態(tài)接收子系統(tǒng)包括三個(gè)不同的接收器，分別是登錄接收器、Wi-Fi狀態(tài)接收器和電源連接接收器。接收器的工作方式如下。首先，每個(gè)接收器要認(rèn)證自己負(fù)責(zé)監(jiān)聽手機(jī)上發(fā)生的特殊事件。只要認(rèn)證的事件發(fā)生，操作系統(tǒng)就廣播一個(gè)特殊目標(biāo)并傳遞該事件的特殊信息到所有認(rèn)證的接收器。我們利用這種機(jī)制為我們的應(yīng)用來(lái)監(jiān)測(cè)所有認(rèn)證的接收器。例如，當(dāng)Wi-Fi連接狀態(tài)發(fā)生變化時(shí)，Wi-Fi狀態(tài)接收器就接到通知。當(dāng)用戶關(guān)掉Wi-Fi后，接收器通知控制器停止正在運(yùn)行的Wi-Fi跟蹤服務(wù)。

另外，當(dāng)用戶手機(jī)連接到了WAP，用戶就會(huì)被網(wǎng)絡(luò)定位以確定他距離取款機(jī)的距離。

2.2 等待時(shí)間探測(cè)子系統(tǒng)

探測(cè)用戶等待時(shí)間的最直接方法是持續(xù)跟蹤用戶的位置，以及用戶進(jìn)入自助取款點(diǎn)的時(shí)間和離開時(shí)間。但是這樣的做法會(huì)導(dǎo)致監(jiān)測(cè)手機(jī)的電池快速耗盡，這是智能手機(jī)用戶所不愿意的結(jié)果。為了減少手機(jī)用電量的消耗，我們進(jìn)行了如下處理。首先，在進(jìn)行跟蹤用戶位置時(shí)，我們只使用網(wǎng)絡(luò)定位。其次，我們利用用戶距取款點(diǎn)的距離來(lái)動(dòng)態(tài)地決定位置頻率。第三，當(dāng)探測(cè)到用戶在取款點(diǎn)的附近時(shí)，我們用WAP的唯一BSSID來(lái)確定用戶的當(dāng)前位置。這有助于節(jié)省相當(dāng)一部分能量。

本系統(tǒng)根據(jù)用戶距自動(dòng)取款點(diǎn)的距離而定期探測(cè)用戶的位置。如果用戶的距離大于閾值，則可計(jì)算出用戶下一時(shí)刻的位置。計(jì)算前提假設(shè)用戶以4.2公里小時(shí)的步行速度接近取款點(diǎn)。因?yàn)閷?shí)驗(yàn)發(fā)現(xiàn)探測(cè)用戶的交通模式（駕車、步行或是騎自行車）比每分鐘檢測(cè)一次網(wǎng)絡(luò)位置更耗能，所以我們做了這樣的假設(shè)。當(dāng)用戶距自動(dòng)取款點(diǎn)的距離小于閾值時(shí)，我們就以每3分鐘一次開始掃描用戶周圍的WAPs。幸而Android提供的API可以掃描周圍的WAPs而不用與它們連接。當(dāng)手機(jī)探測(cè)到自動(dòng)取款機(jī)的BSSID時(shí)，系統(tǒng)就可以確定用戶到達(dá)自動(dòng)取款機(jī)的時(shí)刻為t1，并以每20秒一次的頻率較精確的斷定用戶離開自動(dòng)取款機(jī)的時(shí)刻t2。用戶的等待時(shí)間為t2-t1。由于我們觀察到大多數(shù)取款用戶在取款后立即離開，所以可以假設(shè)計(jì)算得到的等待時(shí)間能夠反映自助取款用戶的等待時(shí)間。

2.3 數(shù)據(jù)上傳子系統(tǒng)

等待時(shí)間探測(cè)結(jié)束后，得到的數(shù)據(jù)需要被手機(jī)上傳到云端，作為等待時(shí)間估計(jì)系統(tǒng)的輸入數(shù)據(jù)。上傳過(guò)程大多數(shù)情況下都是實(shí)時(shí)的。但由于手機(jī)狀態(tài)或是連網(wǎng)情況而有時(shí)不能即時(shí)傳輸數(shù)據(jù)。但是即使是滯后傳輸?shù)臄?shù)據(jù)也仍然有用。為了處理這種情況，我們提出一個(gè)數(shù)據(jù)上傳子系統(tǒng)。只要手機(jī)狀態(tài)接收器通知控制器Wi-Fi可用或是有GSM數(shù)據(jù)連接時(shí)，該系統(tǒng)開始傳輸探測(cè)得到的等待時(shí)間數(shù)據(jù)。

因?yàn)榧词故鞘〉臄?shù)據(jù)傳輸也會(huì)耗費(fèi)能量，所以數(shù)據(jù)上傳器采用簡(jiǎn)單的啟發(fā)式來(lái)增加成功上傳數(shù)據(jù)的比率。假設(shè)手機(jī)大多是在家里或是辦公室中進(jìn)行充電的而且這些地方都有快速而可靠的數(shù)據(jù)連接甚至是Wi-Fi連接。因此，當(dāng)手機(jī)進(jìn)行充電時(shí)數(shù)據(jù)上傳就會(huì)被觸發(fā)。但是有些情況下，雖然手機(jī)被充電了，但它沒(méi)有可用的數(shù)據(jù)連接，那么數(shù)據(jù)上傳子系統(tǒng)會(huì)定期檢測(cè)數(shù)據(jù)連接。

當(dāng)數(shù)據(jù)被成功上傳后，服務(wù)器會(huì)發(fā)出一個(gè)確認(rèn)信。得到確認(rèn)信息后，數(shù)據(jù)上傳子系統(tǒng)會(huì)清空數(shù)據(jù)庫(kù)以節(jié)省手機(jī)的存儲(chǔ)空間。

3 等待時(shí)間估計(jì)

等待時(shí)間估計(jì)部分是位于服務(wù)器的，它由四部分組成，它們分別是網(wǎng)絡(luò)服務(wù)、預(yù)處理器、模型構(gòu)建和等待時(shí)間估計(jì)。網(wǎng)絡(luò)服務(wù)是作為智能手機(jī)與后臺(tái)的接口。它用于接收來(lái)自智能手機(jī)的收集數(shù)據(jù)并為智能手機(jī)提供等待時(shí)間查詢結(jié)果。預(yù)處理器接收到網(wǎng)絡(luò)服務(wù)傳來(lái)的數(shù)據(jù)并進(jìn)行異常值處理。當(dāng)異常值被移除后，等待時(shí)間估計(jì)模塊進(jìn)行等待時(shí)間估計(jì)。

等待時(shí)間估計(jì)問(wèn)題就是為了任何查詢而使用群智感知數(shù)據(jù)來(lái)估計(jì)排隊(duì)等待時(shí)間。所謂感知數(shù)據(jù)就是從參與者收集的等待時(shí)間。等待時(shí)間通常依賴于一天中的時(shí)段；工作日還是周末；商業(yè)自身的季節(jié)性。對(duì)于校園內(nèi)的自助取款服務(wù)點(diǎn)假期時(shí)的業(yè)務(wù)量要少一些。

設(shè)計(jì)的估計(jì)方法應(yīng)該能精確捕獲那些變化。

本文采用的估計(jì)方法的主要思想是預(yù)測(cè)查詢值。當(dāng)系統(tǒng)有足夠的數(shù)據(jù)時(shí)，最后上傳的值能夠反映排隊(duì)的實(shí)際情況。但是該方法對(duì)于采集數(shù)據(jù)稀少或者數(shù)據(jù)中有假陽(yáng)性數(shù)據(jù)時(shí)會(huì)失敗。

4 總結(jié)

本文提出了一個(gè)新的群智感知排隊(duì)等待時(shí)間監(jiān)測(cè)系統(tǒng)。該系統(tǒng)解決了基于基礎(chǔ)設(shè)施的傳統(tǒng)解法弊端，能夠通過(guò)智能手機(jī)得到自動(dòng)而準(zhǔn)確的等待時(shí)間探測(cè)，并在云端進(jìn)行精確等待時(shí)間的估計(jì)。我們將該系統(tǒng)應(yīng)用于學(xué)校的自動(dòng)取款機(jī)服務(wù)點(diǎn)。實(shí)驗(yàn)表明該系統(tǒng)能得到相當(dāng)精確的等待時(shí)間。