论文部分内容阅读
摘要：随着可内嵌多种传感器的智能手机的快速普及和应用，群智感知计算技术作为一种新的感知模式逐步发展起来。为了解决人们生活中排队时间的不可预测问题，本文提出了一个群智感知系统来监测并预测自动取款机排队等待时间。该系统包括能自动探测等待时间的智能手机部分和处理收集数据以提供精确等待时间估计的云后台两部分。该系统通过为用户提供精确的等待时间来帮助用户合理利用排队等待时间。
关键词：群智感知；智能手机应用；排队时间估计
中图分类号：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 总结
本文提出了一个新的群智感知排队等待时间监测系统。该系统解决了基于基础设施的传统解法弊端，能够通过智能手机得到自动而准确的等待时间探测，并在云端进行精确等待时间的估计。我们将该系统应用于学校的自动取款机服务点。实验表明该系统能得到相当精确的等待时间。
关键词：群智感知；智能手机应用；排队时间估计
中图分类号：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 总结
本文提出了一个新的群智感知排队等待时间监测系统。该系统解决了基于基础设施的传统解法弊端，能够通过智能手机得到自动而准确的等待时间探测，并在云端进行精确等待时间的估计。我们将该系统应用于学校的自动取款机服务点。实验表明该系统能得到相当精确的等待时间。