基于智能手機的排隊時間監測

劉宏英 聶文梅

摘要：隨著可內嵌多種傳感器的智能手機的快速普及和應用，群智感知計算技術作為一種新的感知模式逐步發展起來。為了解決人們生活中排隊時間的不可預測問題，本文提出了一個群智感知系統來監測并預測自動取款機排隊等待時間。該系統包括能自動探測等待時間的智能手機部分和處理收集數據以提供精確等待時間估計的云后臺兩部分。該系統通過為用戶提供精確的等待時間來幫助用戶合理利用排隊等待時間。

關鍵詞：群智感知；智能手機應用；排隊時間估計

中圖分類號：TP301.6 文獻標識碼：A DOI：10.3969/j.issn.l003-6970.2017.08.015

引言

在現實生活中，很多公共服務中都存在排隊問題，這給人們的生活帶來了很多的不便。如果用戶能確定排隊時間，則可以在需要等待時間內進行其它事務處理，而不用一直站在隊列或服務場所中長時間等待。對于排隊等待時間問題的傳統解決方法是基于基礎設施的方法，如布署的照相機、傳感器或者由藍牙、Wifi產生的監測信號。但這種解決方法不僅造價昂貴而且不利于規模擴展。我們希望得到一種既可以廣泛使用，又不依賴于基礎設施，而且還精準又便于使用的方法來解決排隊問題。

隨著網絡技術和移動終端設備的迅速發展，智能手機等移動終端設備集成了各式各樣的傳感器。利用移動終端里的傳感器提供以人為中心感知與計算已成為當今社會發展的趨勢。所以通過群智感知來解決排隊監測問題是可能的。用智能手機解決排隊問題需要解決兩個問題。第一是我們在探測等待時間要用到手機中的傳感器，這個過程會使用戶的手機電池在很短時間內消耗用盡。從而使得用戶不愿意參與排隊等待時間監測活動。第二是雖然我們系統能自動收集大量的等待時間，但這些數據仍太稀疏不能直接得到精確的等待時間。

本文提出并實現了基于智能手機的排隊等待時間監測系統。該系統將用戶的智能手機作為排隊等待時間監測終端，獲取參與者的測量數據，在后臺將采集數據進行處理，進而估計每個用戶的準確等待時間，以此來幫助用戶了解自己需要等待多長時間。

1 相關工作

由于不同場所的排隊問題都有各自的特點，如等待的條件不同，造成每個用戶所需服務的時間也各不相同，從而每個用戶所需等待的時間也不同。這里，為使問題易于處理，我們選取自動取款機服務點作為實驗目標。由于每個用戶的操作基本相同，所以每個用戶的所需服務時間大致一樣，便于估計用戶的等待時間。

本文將實驗點設在了一個自動取款服務點。取款用戶按先進先出的排隊方式取款。用戶排到取款機之后進行自助服務。用戶完成任務之后會立即離開。當然也有特殊情況出現，如有人不取款但在取款機附近停留。我們將這種情況下產生的數據作為異常值來進行處理。我們在自動取款機旁邊安裝一個WiFi Access Point（WAP）。這個WAP的BSSID用于探測用戶的排隊時間。

本文的目的是估算用戶的等待時間，即用戶從到達自動取款機到其開始自助取款操作的時間段。為了掌握等待時間隨時間的變化情況，我們實地觀察了自動取款機一周。通過觀察發現自動取款機的用戶等待時間為3分鐘。觀察表明等待時間不會低于2分鐘，最多為5分鐘。這個時間范圍有助于我們刪除不切實際的異常值。

2 等待時間探測

本文實驗所用系統如圖1所示。該系統由兩部分組成。一部分稱為客戶端，它運行于智能手機，主要用于探測等待時間，并將結果上傳于服務器。另一部分在云端，用于處理收集到的數據。

客戶端由控制器、手機狀態接收器子系統、等待時間探測子系統和數據上傳子系統四個部分組成的。控制器負責管理和處理其它三部分的操作。

2.1 手機狀態接收子系統

手機狀態接收器在本應用中充當通知中心的角色。Android提供的通知服務能令app知道手機發生的各種事件，如登錄、重啟、Wi-Fi連接/斷開、Wi-Fi信號強度的變化等。這些通知可以使app根據相關事件做出不同的反應。我們則利用該通知服務來更好的探測等待事件以做出不同的反應。

手機狀態接收子系統包括三個不同的接收器，分別是登錄接收器、Wi-Fi狀態接收器和電源連接接收器。接收器的工作方式如下。首先，每個接收器要認證自己負責監聽手機上發生的特殊事件。只要認證的事件發生，操作系統就廣播一個特殊目標并傳遞該事件的特殊信息到所有認證的接收器。我們利用這種機制為我們的應用來監測所有認證的接收器。例如，當Wi-Fi連接狀態發生變化時，Wi-Fi狀態接收器就接到通知。當用戶關掉Wi-Fi后，接收器通知控制器停止正在運行的Wi-Fi跟蹤服務。

另外，當用戶手機連接到了WAP，用戶就會被網絡定位以確定他距離取款機的距離。

2.2 等待時間探測子系統

探測用戶等待時間的最直接方法是持續跟蹤用戶的位置，以及用戶進入自助取款點的時間和離開時間。但是這樣的做法會導致監測手機的電池快速耗盡，這是智能手機用戶所不愿意的結果。為了減少手機用電量的消耗，我們進行了如下處理。首先，在進行跟蹤用戶位置時，我們只使用網絡定位。其次，我們利用用戶距取款點的距離來動態地決定位置頻率。第三，當探測到用戶在取款點的附近時，我們用WAP的唯一BSSID來確定用戶的當前位置。這有助于節省相當一部分能量。

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

2.3 數據上傳子系統

等待時間探測結束后，得到的數據需要被手機上傳到云端，作為等待時間估計系統的輸入數據。上傳過程大多數情況下都是實時的。但由于手機狀態或是連網情況而有時不能即時傳輸數據。但是即使是滯后傳輸的數據也仍然有用。為了處理這種情況，我們提出一個數據上傳子系統。只要手機狀態接收器通知控制器Wi-Fi可用或是有GSM數據連接時，該系統開始傳輸探測得到的等待時間數據。

因為即使是失敗的數據傳輸也會耗費能量，所以數據上傳器采用簡單的啟發式來增加成功上傳數據的比率。假設手機大多是在家里或是辦公室中進行充電的而且這些地方都有快速而可靠的數據連接甚至是Wi-Fi連接。因此，當手機進行充電時數據上傳就會被觸發。但是有些情況下，雖然手機被充電了，但它沒有可用的數據連接，那么數據上傳子系統會定期檢測數據連接。

當數據被成功上傳后，服務器會發出一個確認信。得到確認信息后，數據上傳子系統會清空數據庫以節省手機的存儲空間。

3 等待時間估計

等待時間估計部分是位于服務器的，它由四部分組成，它們分別是網絡服務、預處理器、模型構建和等待時間估計。網絡服務是作為智能手機與后臺的接口。它用于接收來自智能手機的收集數據并為智能手機提供等待時間查詢結果。預處理器接收到網絡服務傳來的數據并進行異常值處理。當異常值被移除后，等待時間估計模塊進行等待時間估計。

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

設計的估計方法應該能精確捕獲那些變化。

本文采用的估計方法的主要思想是預測查詢值。當系統有足夠的數據時，最后上傳的值能夠反映排隊的實際情況。但是該方法對于采集數據稀少或者數據中有假陽性數據時會失敗。

4 總結

本文提出了一個新的群智感知排隊等待時間監測系統。該系統解決了基于基礎設施的傳統解法弊端，能夠通過智能手機得到自動而準確的等待時間探測，并在云端進行精確等待時間的估計。我們將該系統應用于學校的自動取款機服務點。實驗表明該系統能得到相當精確的等待時間。