然后将算法中使用的分数定义为：
 Score  i j = { 1 Δ T i j ⋅ 1 Δ S i j  for  Γ i j ≡  true  0  otherwise  (4) \text { Score }_{i j}= \begin{cases}\frac{1}{\Delta T_{i j}} \cdot \frac{1}{\Delta S_{i j}} & \text { for } \Gamma_{i j} \equiv \text { true } \\ 0 & \text { otherwise }\end{cases} \tag{4}  Score ij​={ΔTij​1​⋅ΔSij​1​0​ for Γij​≡ true  otherwise ​(4)

仅当等式 (1) 成立时，得分才假定值高于 0，即如果 j 和 i 具有相同的标记参数并且它们一个接一个地被接收。 对于大于 0 的值，值越大，两个 MAC 地址归属于同一源设备的概率越大。

一旦为识别的所有随机 MAC 地址对计算了分数，该算法的任务就是创建可追溯到同一源设备的 MAC 地址列表。现在解释图 4 的流程图中描述的创建列表的过程。每当接收到具有新随机 MAC 地址 M A C j MAC_j MACj​ 的帧时，都会在 M A C j MAC_j MACj​ 和已经在列表中的所有其他随机 MAC 地址之间计算分数。如果尚未创建列表，则不会计算分数；如果所有分数都等于 0，则 M A C j MAC_j MACj​ 肯定属于一个新设备。在这两种情况下，都会创建一个以 M A C j MAC_j MACj​ 作为唯一元素的新列表。否则，识别出与 M A C j MAC_j MACj​ 得分最高的地址 M A C m MAC_m MACm​，即最有可能属于同一设备的地址 M A C m MAC_m MACm​。考虑 M A C m MAC_m MACm​ 所在的列表 L x L_x Lx​，如果 M A C m MAC_m MACm​ 是列表的最后一个元素，则将 M A C j MAC_j MACj​ 附加到列表中。如果列表 L x L_x Lx​ 中的 M A C m MAC_m MACm​ 后面还有另一个 MAC 地址 M A C n MAC_n MACn​，则必须将 S c o r emj Score_{mj} Scoremj​ 与 S c o r emn Score_{mn} Scoremn​ 进行比较：如果前者低于后者，则意味着 M A C m MAC_m MACm​ 和 M A C n MAC_n MACn​ 更有可能属于同一设备，具有关于 M A C m MAC_m MACm​ 和 M A C j MAC_j MACj​。因此，为 M A C j MAC_j MACj​ 找到正确列表的过程再次开始忽略 m。另一方面，如果 S c o r emj Score_{mj} Scoremj​ 高于 S c o r emn ，则 Score_{mn}，则 Scoremn​，则MAC_m$ 和 M A C j MAC_j MACj​ 属于同一设备的概率高于 M A C m MAC_m MACm​ 和 M A C n MAC_n MACn​ 属于同一设备的概率。因此， M A C j MAC_j MACj​ 在 M A C m MAC_m MACm​ 之后被放入 L x L_x Lx​。此外，列表 L x L_x Lx​ 中的以下 MAC 地址不再确定属于同一设备。因此，对于 M A C n MAC_n MACn​ 及其在 L x L_x Lx​ 中的所有后续 MAC 地址，再次重复该过程。

因此，该过程采用递归形式。 最后，所有列表都是其中存在的 MAC 地址可追踪到同一设备的可能性更大的列表。 因此，属于同一列表的所有帧都被标记有相同的 MAC 地址。

3.2、乘客计数算法

一旦解决了去随机化过程，我们需要分析结果数据，这些数据代表被感知设备的唯一 MAC 地址，以便统计公交车上的人数。
对于静态情况，例如，在计算房间中的人数时，需要考虑几个问题才能准确地仅计算公共汽车上的人数。

• 两个连续公交车站之间的距离变化很大，从百分之一米到一两公里不等；
• 未定期发送探测请求；
• 巴士在每一站所用的时间是可变的，并且可能有巴士不停靠的站点；
• 嗅探器可以感应到不在公交车上但在人行道上行走、在公交车站等车或公交车附近的车内的设备；

让我们考虑图 5 中描述的场景； 我们的目标是统计公交车上的人数，并了解最后一站有多少人上下车。 为此，我们定义公共汽车站集合$\mathcal{Z}=\{1,\dots ,z,\dots Z\}$，这样对于每个停靠站 z，我们可以定义到达公共汽车站 t z a t_z^a tza​ 的时间和离开的时间 t z d t_z^d tzd​； 然后，我们称时间花费，公交车在每个站点花费的时间间隔，可以识别如下：
Δ T z S = t z d − t z a (5) \Delta T_z^S=t_z^d-t_z^a \tag{5} ΔTzS​=tzd​−tza​(5)

我们还可以将运行时间确定为公共汽车从一站运行到下一站所需的时间，如下所示：
Δ T z , z − 1 I = t z a − t z − 1 d (6) \Delta T_{z, z-1}^I=t_z^a-t_{z-1}^d \tag{6} ΔTz,z−1I​=tza​−tz−1d​(6)
为了克服前面提到的问题，我们需要过滤数据库中的所有条目。为了解决探测请求接收频率的可变性，对于每个停止 z，我们需要检查一个时间窗口，以便考虑计数 仅算法在间隔中包含的瞬间接收的探测请求：
t ∈ [ t z − 1 a − Δ T W , t z d + Δ T W ] (7) t \in\left[t_{z-1}^a-\Delta T^W, t_z^d+\Delta T^W\right] \tag{7} t∈[tz−1a​−ΔTW,tzd​+ΔTW](7)
其中 Δ T W \Delta T^W ΔTW 是一个固定参数，称为观看时间。

在时间过滤之后，我们需要了解剩余的 Probe Requests 是否由总线上的设备传输。 为此，我们对过滤窗口中的所有条目进行了一系列检查。 执行第一次检查以计算每个 MAC 地址的帧数，即 N iframe N_i^{frame} Niframe​，以便识别仅在公共汽车移动期间短暂遇到的设备，例如行人或驾驶员的智能手机： 如果捕获的帧数低于给定的阈值 x，那么这些设备的请求可能只被嗅探器捕获了几次，然后应该被丢弃。

实施另一项检查来评估来自探测请求的接收功率：接收功率与发送设备相对于嗅探器的距离成反比，因此可以丢弃来自设备的所有探测请求。 远，然后很可能在公交车外，例如一辆汽车在公交车前面移动的情况，如图 5 所示。特别是，我们考虑到来自 M A C i MAC_i MACi​ 的 Probe Requests 的平均功率由 sniffer 必须高于某个阈值 Pth P_{th} Pth​，即 P iavg > Pth P_i^{avg} > P^{th} Piavg​>Pth； 这样做，甚至可以丢弃在交通拥堵中不断移动（功率较低）并再次与公共汽车汇合（功率较高）的汽车的情况。

最后，由于探测请求的发送方式，即通过一系列近时间请求，我们决定考虑另一个参数，即总线 Δ T P \Delta T^P ΔTP 上设备的持久性，计算为最后一帧和第一帧之间的差异 在时间窗口中接收到，即 $t_i^{l*} 和 t if∗ t_{i}^{f*} tif∗​，以评估请求是否属于不同的请求序列。

总而言之，如果满足以下条件，则时间窗口内的通用 MACi 地址的条目（如公式 (7) 所定义）将被考虑用于计数算法：

{ N i f  rame >xP i a v g> P t ht i l ∗− t i f ∗>Δ T P (8) \left\{\begin{array}{l} N_{i}^{f \text { rame }}>x \\ P_{i}^{a v g}>P^{t h} \\ t_{i}^{l^{*}}-t_{i}^{f^{*}}>\Delta T^{P} \end{array}\right. \tag{8} ⎩⎨⎧​Nif rame ​>xPiavg​>Pthtil∗​−tif∗​>ΔTP​(8)
过滤步骤后剩下的唯一 MAC 地址的数量可以粗略估计总线上的设备数量。然而，评估设备板和灯的停止位置仍然很重要。该信息对于构建起点-终点矩阵非常有用，而且对于评估 MAC 地址的第一次或最后一次出现是否距离任何站点都不太远，因此表明另一辆车以相似的速度靠近公共汽车，而不是比乘客登上或离开正在行驶的公共汽车。

对此，我们认为只有在公交车站的时间范围内分别收到第一个或最后一个探测请求时，设备才会从公交车上车或下车。这是必要的，因为无法提前知道何时发送探测请求，所以我们必须保证在到达巴士站之前都有一个警卫时间，\Delta T_{z}^{G_{b}}，在离开它之后，\Delta T_{z}^{G_{l}}，对于那些在到达公共汽车站之前或离开它不久之后发送第一个或最后一个探测请求的不幸情况。

对于每个具有 Δ T S > 0 \Delta T^{S}>0 ΔTS>0 的公交车站，都会有 Δ T zGb + Δ T zGl + Δ T z S \Delta T_{z}^{G_{b}}+\Delta T_{z}^{G_{l}}+\Delta T_{z}^{S} ΔTzGb​​+ΔTzGl​​+ΔTzS​ 的时间范围 可用于接收来自设备的第一个或最后一个探测请求。一般来说，对于每个停止之前和之后的所有停止，保护时间都可以认为是恒定的，因此我们可以将其表示为 Δ T G \Delta T^{G} ΔTG；但是，如果两站之间的运行时间 Δ Tz,z−1 I \Delta T_{z, z-1}^{I} ΔTz,z−1I​ 太小，即小于 Δ T zGb + Δ Tz−1 Gl = 2 Δ T G \Delta T_{z}^{G_{b}}+\Delta T_{z -1}^{G_{l}}=2 \Delta T^{G} ΔTzGb​​+ΔTz−1Gl​​=2ΔTG ，则保护时间必须相应修改为 Δ T zGb = Δ Tz−1 Gl = 0.5 Δ Tz,z−1 I \Delta T_{z}^{G_{b}}=\Delta T_{z-1 }^{G_{l}}=0.5 \Delta T_{z, z-1}^{I} ΔTzGb​​=ΔTz−1Gl​​=0.5ΔTz,z−1I​ 。

我们最终需要了解，对于每个时间窗口和每个设备，该设备是否真的在船上，以及它是否在考虑的时间范围内登机或下车。如图 5 所示，在分析单个时间框架时，我们可以细分不同的行业：

• 扇区 1，在时间窗口开始和停止 z-1 的保护时间开始之间。
• 扇区 2，分析停止 z-1 ，同时考虑防护时间、停止前后以及花费的时间。
• 第 3 部分检查两站之间的时间。
• 扇区 4，它考虑了停止 z 的事件。
• 扇区 5，在停止 z 的保护时间结束和时间窗口之间。

对于每个设备，计数算法首先检查该设备是否已被考虑在船上。如果这是嗅探器第一次收到设备的请求，算法必须了解设备在哪个停止登机：如前所述，设备只有在第一次探测请求时才能登机， t if∗ t_{i}^{f ^{*}} tif∗​ ，当公共汽车在公共汽车站附近时收到。如果在扇区 2 中收到第一个探测请求，则该设备将被计为在 $z-1$ 站上车，如果在扇区 4 中收到第一个探测请求，则该设备将被计为在 z 站上车。在所有其他情况下，即当在扇区 1、3 和 5 内收到探测请求时，设备的所有条目都被认为是虚假的，然后被丢弃。

板载设备被认为是整个时间窗口；在这种情况下，等式 (8) 中描述的下一个时间窗口的帧数条件更新如下：

Niframe + 1 > x N_{i}^{\text {frame}}+1>x Niframe​+1>x

考虑到设备已经在船上。但是，如果设备在下一个时间窗口（即停止 $z+1$）中没有通过过滤步骤，则算法返回到前一个时间窗口，通过分析收到的最后一个探测请求 t il∗ t_{i }^{l^{*}} til∗​。同样，仅当分别在扇区 2 或 4 中接收到最后一个探测请求时，设备才会被计为在 $z-1$ 或 $z$ 站下车，否则将丢弃该设备的所有条目。

值得注意的是，每次公交车到达停靠站 z 时，该算法都能够通过检查下一个时间窗口来计算与上一站相关的乘客数量。

图 4 说明了整个过程的所有步骤。它从探测请求的嗅探开始，到所有公交车站都经过分析以计算乘客数量时结束。

4、 实验

在本节中，评估 iABACUS 的性能。实验的设置包括 Wireshark 嗅探器，设置为监控模式，过滤器仅拾取具有广播目标地址的探测请求帧，即 ff:ff:ff:ff:ff:ff。捕获的帧被发送到 MySQL 数据库，在那里它们被收集和存储。为此，通过 Lua 脚本建立连接，将捕获的帧转发到数据库。然后通过 PHP 应用程序查询数据库。

下面将展示基于此设置的实验结果。第 4.1 节所示的第一个实验是为了在静态场景中测试去随机化算法。稍后，第 4.2 节介绍了在动态场景中对乘客进行计数的测试。

4.1、去随机化算法的准确度评估

第一次测试是在静态场景中进行的，专门用于评估去随机化算法的准确性。测试结果取决于去随机化过程后识别的设备数量，即作为第 3.1 节中描述的去随机化算法的输出生成的列表数量

实验在 15 分钟的时间窗口内在大学房间内进行。以下信息是从房间内的设备所有者那里收集的： 具有活动 Wi-Fi 接口的设备数量；设备的真实 MAC 地址；品牌、操作系统类型和设备版本。
实验中考虑的第一个参数是传输频率。事实上，根据标准，Wi-Fi 的典型传输频带是 2.4 和 5GHz。然而，虽然所有检测到的设备都以 2.4 GHz 传输，但这并不总是在 5 GHz 上得到验证。此外，2.4 GHz Probe Request 帧是最完整和信息最丰富的。因此，2.4 GHz被选为 Wireshark 嗅探器的接收频率。还评估了收集两个频率信息的可能性。但是，由于嗅探器一次只能捕获一个频率的数据，因此需要将两个嗅探器放置在同一点。此外，结合两个嗅探器的捕获和分析更多帧的过程将显着增加系统的计算负载，同时不会提供重要的进一步信息。由于这些原因，接收频率设置为 2.4 GHz 。

为了设置最合适的功率阈值 Pth P^{th} Pth ，将考虑的设备限制在房间内的设备上，评估了接收到的所有探测请求帧的平均功率，如图 6 所示。 正如预期的那样，对于靠近嗅探器的设备测量了最高的平均功率。 此外，可以注意到高于 -51 $\mathrm{dBm}$ 和低于 -61 $\mathrm{dBm}$ 的接收功率值之间存在明显的划分。 随着距离的增加，后一种更高的衰减可以归因于墙壁的存在。 因此，功率阈值设置为 -55 $\mathrm{dBm}$ 。 用于该测试的参数总结在表 3 中。

在这种静态情况下测试的 iABACUS 的最终结果如表 4 所示，其中将提出的算法计算的 MAC 地址数与常见的基于 Wi-Fi 的 APCS 计算的 MAC 地址数进行比较，即系统不考虑 MAC 地址的随机化，只计算识别出的唯一 MAC 地址的数量。从表中的数据可以看出，与不考虑 MAC 地址随机化的普通基于 Wi-Fi 的 APCS 相比，iABACUS 确保获得更准确的结果。特别是，系统返回房间中存在的确切设备数量（即 21 个），而传统程序会记录显着更多的设备数量（即 37 个）。由于普通的基于 Wi-Fi 的 APCS 只能理解 MAC 地址是否是随机的，而不能理解两个不同的随机 MAC 地址是否可以与同一设备相关联，因此它们会将设备与接收到的每个不同的随机 MAC 地址相关联。因此，他们对实现 MAC 地址随机化的设备数量的误差与观察时间窗口相关，在这种情况下等于 15 分钟：时间窗口越长，设备更改其 MAC 的次数越多地址，然后计数的设备数量越高。

4.2、乘客计数实验

为了评估所提出的计数算法的可行性和性能，再现了真实的动态环境。这种动态场景的主要特征是，由于嗅探器本身的移动，人们有可能进出嗅探器字幕的范围。公交车内的嗅探器就是这种情况，人们在公交车站上下车。

实验在意大利卡利亚里市进行。为了限制它们的随机性，我们使用汽车来模拟巴士站位置和所花费时间的现有巴士路径。汽车的路径如图 7 所示，其中还突出显示了所考虑的 13 个站点。涉及的 Wi-Fi 设备数量限制为 8 个，其中三个实现 MAC 地址的随机化。通过分别打开和关闭设备的Wi-Fi接口来模拟人们上下车的事件。实验计划如表 5 所示，它表示对于每个设备，从设备 A 标记到设备 $\mathrm{H}$ ，起点’和目的地’停止；表 5 还显示了执行的三个测试的结果，这将在下面讨论，以淡蓝色突出显示发生错误的单元格。所有的实验都是在午休前或午休期间在中等交通条件下进行的。路径长约 2.4 $\mathrm{km}$ 并且有三个红绿灯：汽车需要大约 $15\min$才能行驶，这也是乘坐公共汽车的乘客的平均时间。

对于嗅探器，第 4 节中描述的相同设置已在以 Raspbian Stretch 作为操作系统的 Raspberry Pi 2 上实现，以提高解决方案的可移植性。 USB Wi-Fi dongle 用作天线，使 Raspberry 能够收集探测请求。汽车的路径已通过 GPS 模块 (GPS GY-NEO-6M v2) 进行监控，每 $5\mathrm{s}$ 将其位置（纬度和经度）发送给 Raspberry。 GPS 信息对于获取每个公交车站的到达时间 t z a t_{z}^{a} tza​ 和出发时间 t z d t_{z}^{d} tzd​ 以及运行时间 Δ Tz,z−1 I \Delta T_{z, z -1}^{I} ΔTz,z−1I​ ，这是我们计数算法的关键参数。此外，GPS 通过比较它们的时间戳来启用与 Raspberry 接收的探测请求的空间映射。

表 6 总结了在执行测试期间考虑的参数值。我们在第一次测试中为参数选择了合理的值；然后我们分析每个测试的结果，将它们与计划的实验进行比较，以便在后续测试中调整它们并纠正算法的错误。

第一次测试的结果显示设备 $\mathrm{A}$ 和 $\mathrm{H}$ 丢失，设备 $\mathrm{D}$ 板在第 4 站而不是第 2 站，而设备 $\mathrm{C}$ 在第 8 站下车而不是停止 9 ;此外，我们个性化了一个新的设备，标记为 $\mathrm{X}$ ，它在实验中没有计划，在第 3 站上车，在第 5 站下车。然后我们逐步分析了旅途中发生的事情：

• 在时间过滤期间，发现对设备 $\mathrm{A}$ 和 $\mathrm{H}$ 的请求少于 5 次，因此由于它们仅在船上停留了一站，因此它们被从算法中丢弃；在我们的实验中，设备通常会发送一系列探测请求，即一组请求，每 40 个 $\mathrm{s}$ ，但处于节能模式的设备可以以较低的频率发送这些请求。通过研究嗅探器的捕获，我们注意到来自设备 $\mathrm{A}$ 和 $\mathrm{H}$ 的探测请求的频率非常低，大约为 2-3 分钟，这意味着设备处于节能模式。
• 我们从公共汽车站 2 的时间窗口中获得了设备 D 的条目，不幸的是，这些条目都没有在正确的扇区中，以便将设备计为已上车，直到汽车到达公共汽车站 4。
• 关于设备C，在分析9号公交车站时，我们发现条目太少（只有3个），所以我们检查了之前的公交车站，即8号公交车站，发现设备最后一次探测请求在Sector 4，所以算法在第 8 站将设备标记为下车。
• 最后，在第 3 站和第 5 站之间，我们遇到了一点交通堵塞，所以我们需要很多时间才能在这条路段上行驶，而且我们的算法能够从另一个设备（可能是来自在我们后面或前面行驶的汽车，然后被算作车上的乘客。

对于第二个测试，我们将时间窗口从 2 增加到 4 $\min$ 并将所需的帧数从 5 减少到 3 ，以使即使处于节能模式的设备也能正确计数；此外，我们还增加了警戒时间 Δ T z G \Delta T_{z}^{G} ΔTzG​ ，这样无论上车还是下车，它都更有可能在正确的公交车站找到设备。我们还决定为接收功率设置一个更保守的阈值，以避免计算来自车外的设备。

通过对第二次测试的分析，我们发现只有一个错误：设备 $\mathrm{C}$ 在 3 号巴士站下车，但在 5 号站再次上车，在 9 号站正确完成行程。通过检查设备发送的请求，我们注意到它们相当有规律（大约每 42 $\mathrm{s}$ 一列请求），但由于某种原因，在停止 3 和 5 附近，嗅探器错过了其中一些，导致检测到奇怪的行为。但是，我们注意到之前的所有错误都已得到纠正，因此我们决定仅进一步减少计数算法考虑 MAC 地址所需的帧数。

在第三次测试中，我们注意到关于设备 C 的问题得到了解决，并且没有计算外部设备，即使需要的帧数等于 1：这是由于算法能够过滤掉大部分探测请求由于功率阈值。但是，我们检测到设备 $\mathrm{D}$ 再次被计为在不同的公交车站上车，就像在第一次测试中发生的那样，但在第二次测试中没有；发生这种情况是因为停止 2 和停止 3 非常接近，因此其中没有扇区 3，并且停止 2 和停止 3 的两个保护时间重叠。然后设备D根据收到的第一个探测请求计为登机：在不幸的情况下，探测请求延迟到停止3，这将导致错误，这是无法避免的。

从这些测试中，我们可以推断出设置算法参数的简单规则。主要目标是不丢弃总线上的任何设备，即使它们处于节能模式：为此，时间窗口应该相当大，以确保检测到至少一个探测请求，而帧数失去意义.然后需要通过使用其他参数（例如功率阈值）来丢弃总线外部的设备。然而，这些规则只能提供关于设置的第一个提示，因为算法需要根据所考虑的特定路线和城市进行调整。

5、 结论和未来工作

本文提出了 iABACUS，一种基于物联网的新型公共交通自动乘客计数系统，它根据安装在公共汽车上的嗅探器收到的 Wi-Fi 探测请求来推断车上人数。 由于最新的移动操作系统引入的 MAC 地址的随机化，当前基于 Wi-Fi 的 APCS 现在已经过时。 出于这个原因，iABACUS 包含一个去随机化算法，以便了解哪些 MAC 地址更有可能被带回同一设备； 该算法在总共 21 台设备上的测试表明，它能够成功识别所有随机 MAC 地址。 此外，我们的测试还强调 MAC 地址的随机化是一个严重的问题，因为即使仅存在三个设备也可能导致在 15 分钟的时间间隔内计数高出六倍。

然后我们通过实际实验研究了计数算法，模拟了一辆汽车的公交车行为，并考虑了八名乘客，在不同的公交车站上下车。 实验是在压力条件下进行的，以强调算法的任何问题。 结果非常好，因为计数算法设置正确时，能够计算所有乘客； 但是，由于设备发送探测请求的频率较低，因此可能会出现与乘客正确上下车有关的随机错误。

在未来的工作中，我们计划考虑真实的用例条件，例如由于巴士尺寸或乘客身体吸收（尤其是拥挤的巴士）、干扰和非线路吸收导致的接收到的 Wi-Fi 信号衰减。视线，影响iABACUS的性能。我们将研究需要多少个嗅探器以及它们的最佳位置，以便正确识别所有车载设备的功率。外部的：使用多个嗅探器，可能设置为在不同的频率通道中累积请求，并汇总它们的结果，可能被证明是一种更好的方法。最后，我们计划研究与两个公共汽车站的接近度相关的随机误差，以便找到与它发生概率的关系。此外，我们计划研究由于我们系统中的未连接用户导致的系统错误；为此，我们旨在将所提出算法的结果与卡利亚里市当地公交车估计的计算乘客人数进行比较，并提出一个适用于我们系统的调整因子。城市之间的未连接用户数量肯定存在差异，因此我们希望每个城市都应该采用类似的方法。

jcg路由器知识网