基于机会网络中移动人群感应的邻居协作机制∗

万 辛

（天津市国瑞数码安全系统股份有限公司 天津 100101）

基于机会网络中移动人群感应的邻居协作机制∗

万 辛

（天津市国瑞数码安全系统股份有限公司 天津 100101）

数据采集是新兴移动传感系统的一个基本的构建块，来自于许多的移动设备。在论文中，我们提出了通过机会网络的一个有效的信息扩散协议传感器数据采集。所提出的方法是检测行人群，基于在所检测到的组成员之间的节点和维护本地网络（即一个集群）之间无线连接的历史。通过协同执行集群成员的邻居发现和链路管理，它提高了邻居发现的能源效率，最大限度地减少了信息传递延迟。仿真结果表明，该方法可以提高信息传递性能将近16%～83%以及等效接触探测间隔。

数据采集；机会网络；检测；信息传递；集群

1 引言

移动传感技术使一些创新的应用和服务快速进步。通过在移动设备（例如，智能手机）从内置的传感器收集测量数据，我们可以认识到在没有密集部署传感基础设施的环境中目前的情况和群体行为［1～2］。我们需要一个可扩展的平台，提供这样的移动传感应用，收集一些移动设备到网络服务器的传感器数据。大多数现有的移动传感系统呈现每个节点的传感器数据通过蜂窝网络上传。然而，除了他们移动设备的电池消耗，伴随着数据上传这种方法需要用户支付的3G通信费用。再以物质刺激鼓励人们加入服务，这会不会是许多参与感知场景的最佳解决方案。现在，公共信息科技与产业基础设施，如免费的Wi-Fi热点被广泛提供在城市地区（例如，在火车站和购物中心），对于移动传感系统的数据收集，机会网络将提供一个替代的解决方案：每个节点暂时存储传感器数据在本地存储器上，当周围的Wi-Fi热点出现的时候再上传到服务器上。虽然这可能会产生数据收集的一些额外的延迟，但它会降低用户的门槛及参与感知服务。

这种方法的一个潜在的问题是因为无线接入点，如Wi-Fi热点通常部署稀疏，数据上传的机会是有限的。为了有效地增加上传的机会以及减轻数据收集延迟，传感器数据也在移动设备之间共享。通过短程无线通信相邻节点之间共享本地传感器数据，然后伺机将收集到的数据通过3G和Wi-Fi网络上传到服务器，数据收集的效率将会大幅度提高（图1）。为了在许多的移动设备中交换传感器数据，我们需要解决以下的问题：第一个问题是移动设备的信息传递延迟和能量消耗之间的权衡。在人们频繁移动的情况下，节点之间的接触时间往往是短暂的，往往在几十秒内。在每个节点应该频繁进行邻居发现，以检测这样的短暂接触而减少数据收集延迟，它通常所带来的是严重的能量消耗。第二个问题是对节点密度的鲁棒性。在无线连接的协议如Wi-Fi的点对点（ad-hoc）模式，数据包的接收概率通常会由于信息包的频繁碰撞并伴随着节点密度的增加而下降。在这个意义上说，面向连接的协议，如蓝牙将更适合我们的情况。另一方面，他们经常有一个节点可以保持的通信链路数量的限制。当相邻节点的数量远大于最大程度时，节点需要反复建立和断开通信链路及时向邻居交换传感器数据。因此，链路建立的开销将是不可忽略的，从而可能会降低带宽利用率。大多数现有的路由协议的机会网络通常假设理想的通信，并没有考虑较低层的网络问题。

图1 系统结构

在本文中，在机会网络下移动设备之间共享传感器数据，我们提出了一个高效节能的信息扩散协议。在拥挤的情况下，像一个活动场所和购物中心，人们自然形成群体进行移动（例如，朋友，家庭或陌生人只是移动到同一目的地）。该方法检测这样的行人组基于无线连接节点和维护本地网络（即集群）小组成员之间的历史。通过协同进行集群成员的邻居发现和链路管理，加强了邻居发现与节点的约束处理的能源效率。通过仿真实验使用一个模拟器［3］，我们比较所提出的方法与非协作的方法的性能，所有的节点随机的时间间隔重复邻居发现和发送连接请求到所有检测到的邻居。结果表明，该方法可以提高信息传递性能的16%-83%结果表明，该方法可以提高信息传递性能的16%-83%等效接触探测间隔。

2 机会网中的集群

2.1 机会网络中移动点对点网络的动态集群

在一个断断续续连接的移动点对点网络中或机会网络进行高效的信息传递，以及对一些路由协议研究。最直接的方法是路由协议［4］，当节点在其通信范围内其中一个节点在其本地存储复制所有信息。虽然它可以实现最小的信息传递延迟，在没有任何信息之前，它通常会产生过多的冗余信息交换。许多工厂已经扩展了路由协议以应对这个问题，通过预测每个邻居在未来遇到指定节点的概率［5］。基于接触概率，发送者为每个邻居减少冗余信息传输做出复制的决定。由于数据包很少发生碰撞，上述路由协议基本呈现的是一个稀疏的网络。另一方面，为了适用于这样的路由机制为移动人群感应传感器数据扩散，节点频繁的通讯移动这将是必不可少的，以最小的能量开销和实现更高的节点密度的鲁棒性。该方法作为路由协议和蓝牙的MAC/PHY层之间的中间件，弥合这些差距通过机会网络移动实现了人群感应使得传感器数据扩散更高效。

2.2 邻居发现的高效节能及其接触探测

邻居发现（或接触探测）一直被认为在机会网中是一个有效的信息传递的基本构建块。制定接触探测任务使用补充的理论，由于探测是在瞬间完成的，证明了不断探测间隔提供一个最佳的邻居发现可能性。发现通过基于检测到的邻居数量进而动态调整探测间隔以达到高效节能的邻居发现［7］。这两种方法都集中在优化探测间隔，以避免时间冗余，假设每个节点进行独立的接触探测。另一方面，该方法协同执行集群成员之间的接触探测以减少空间冗余，在每一轮，只有少量的集群中的节点执行邻居发现和检测结果与其他成员分享。由于集群成员相互接近时，可以实现合理的邻居检测率与降低探测频率。因此，所提出的协同接触探测机制是现有的优化方法，使接触探测的效率可以进一步提高，基于时间优化策略调整每个集群的探测间隔［6～7］。

在本文中，我们假设人们在一些公共空间（如一个购物中心）移动设备配备点对点通信能力（即移动节点或节点）。认识到群众行为和周围的情况下，传感器数据在每个节点上不断收集和共享其他节点，依赖于应用程序的预处理后的环境。无线访问点（如，Wi-Fi热点）在环境中稀疏部署以便收集传感器数据，当移动节点到访问点周围数据则上传到一个网络服务器。如果用户允许这样做，节点也可以通过蜂窝网络直接上传数据到服务器。我们还假设信息的大小比无线网络带宽足够小。每个节点有足够大的缓冲区空间，因此缓冲区溢出从未发生。

该方法检测行人组基于节点之间无线连接最近的历史。然后在检测组成员之间为本地合作形成一个集群。每个集群有一个特殊的节点称为集群头（CH），在集群内部通信它需要对集群维护和控制。这里我们考虑CH及其集群的情况。该方法假设所有集群成员满足以下条件：

因此节点ui需要保持连通性，随着CHu0超过T秒加入集群。T的临界值应该大于预期接触时间为独立移动的节点，可以通过模拟估计或通过分析历史轨迹数据。除非另外注明，在本文中我们假设T=60秒。注意，在我们的模拟中，在不同组之间节点接触小于临界值88%，最初，每个单个成员节点形成的集群本身需要CH。后来，CH定期执行接触探测并更新成员组的集群，这样所有的成员，满足式（1）。

在集群内部网络集群成员一直保持连接。所有传感器数据收集的成员直接共享集群内部通信链接中集群的其他节点。当通过邻居发现节点在不同的集群中检测，在集群之间检测到的节点建立临时通信链路与邻居交换信息（即传感器数据）。而建立的链接通常是伴随着几秒钟开销，信息交换本身可以在很短的时间内完成，因为信息的大小远小于通信带宽。因此，在该方法中，集群成员协作管理集群内部链接，最多一个通信链路建立相邻之间的集群。由于传感器数据立即在集群成员之间共享，在集群中数据维护可以通过一个通信链路被转移到邻近的集群中的所有节点。因此该方法减轻了信息传递延迟造成的约束程度和链接的开销建立通过聚集集群内部信息交换进入少量的通信链接中。

此外，集群成员在空间上是近距离的，因此他们的邻居集将会彼此相似。基于这一特性，CH随机选择少量的集群成员（称为发现者）在每一轮让他们完成邻居发现。这有效地降低接触探测能源消耗的平均频率，同时保持合理的接触检测能力。

因此该方法减轻了能源消耗和信息传递延迟造成的约束程度通过形成一个集群节点移动作为一个群体和协作执行接触探测，链接管理和信息交换跟集群成员。

一个节点ui执行的邻居发现，它迅速切无线电频率和多次传递查询信息。因此，ui很难响应来自相邻节点的查询在其邻居发现的过程中。因此每个邻居的探测概率uj取决于其处于非发现状态和ui本身的发现过程的持续时间（即有效扫描时间）。邻居探测概率随Tc有效的扫描时间增加，并且当Tc=5.12s时其可达到99%［10］。尽管频繁接触探测需要检测短接触，同时也会使邻居发现相邻节点之间失去联系。此外，大量的电池在发现过程中不断消耗。上一节中提到的，该方法处理问题通过选择少量的发现者和集群成员之间分享他们的检测结果。发现从邻近的集群可以有效地提高能源效率和响应能力。上面的概率可以被定义为

在这里，只有n为集群成员（即发现者）完成邻居发现。假设未发现者ui和每个集群成员之间的距离是一个概率分布 f(r)，一个邻居的ui的概率，假设u被发现是由一个发现者uj的集群得到的：

我 们 假 设 ri1≤ri2≤…≤rin显 然 ，概 率P(Xi1Xi2… Xin)满足以下条件：

既然u1在ui中是最近的发现者，设置F(r)=f(r) dr从ui到发现者的累积分布。累积分布函数的距离在ui和u1之间是由：

通过F1()

r，我们获得ri1的概率密度函数：

基于（3）、（4）和（6），我们得到：

检查接触检测率的发现者，我们通过式（7）推导出P(Xi1Xi2… Xin)的下限。为分析，我们假设集群成员之间的距离是（0，rmax）之间的均匀分布，在rmax是在5～20m之间的变化。基于蓝牙的典型的通信范围无线传输范围R设置为10m。图2显示了一个邻近的非发现者的概率下界是发现在集群中至少有一个发现者，发现者的数量是不同的。当集群成员之间的最大距离是5m，邻近的非发现者可以被发现概率为84%，集群中只有一个成员那就是发现者。因此，通过限制集群中发现者的数量，我们可以有效地减少平均接触探测频率，同时保持合理的接触检测率。

图2 邻居探测概率

最初，每个节点形成一个尺寸为1的集群。然后每个集群独立重复以下三个阶段为了集群维护和信息交换。

1）集群维护：CH执行邻居发现获得当前的邻居集（图3（a））。与此同时，其他节点在未发现状态应对CH的查询，然后CH更新集群的成员基于收集到的连接信息。

2）联系调查：CH从集群成员（CH本身除外）中随机选择（n-1）个发现者。然后选中的成员执行邻居发现与邻近的集群接触检测（图3（b））。

3）信息交换：CH和发现者与邻近的集群中的节点建立通信链接交换传感器数据保持在每个集群（图3（c））。从邻近的集群接受连接请求，信息交换后立即断开集群内部链接。最后，得到了传感器数据通过集群内部通信链接共享到集群成员。

每一轮的总持续时间（三个阶段组成）是随机由CH决定的。注意，如果集群只有一个节点，阶段2）和阶段3）则省略。在这种情况下，CH在未发现的状态，直到下一轮的开始。

图3 协议设计

3 仿真实验

评价该方法的性能，我们使用一个模拟器进行了仿真实验［3］。我们假设100个移动节点绕着50米*50米的区域来回转，形成10节点的组：我们形成10个参考点代表一组的平均行为。参考点遵循随机路径移动模型和独立的移动领域。每一次移动，参考点随机选择一个目的地，路径是以恒定速度从其领域到达目的地。移动速度也决定随机区间0.5 m/s～1.5 m/s。到达路径目的地后，参考点停止长达120s，然后朝着下一个目的地移动。参考点确定一个新的目的地时，相应的小组成员同时挑选自己的目的地，在3m内的参考点。因此我们模拟移动节点基于分组的移动性。

每10s，每个节点生成一个2kb的信息（即传感器数据）和其朝着环境中所有节点的路由协议扩散。我们假设信息传递的最后期限是60s和定义的信息传递率是通过达到最后期限内的节点信息的百分比。假设蓝牙v2.1+EDR，无线通信的范围和速度分别设置为10m和2mbps。每个集群执行随机接触探测间隔Tinq±5.12s，和邻居发现的持续时间是5.12s。Tinq是一个调整每个集群接触探测的平均间隔参数。默认情况下，我们设置Tinq为15.36s。在仿真实验中，我们确定邻居探测概率基于［10］的理论模型和限制通信链路节点最大数量，每个节点一直到7。此外，我们假设一个2s的开销为建立链接。仿真结果：

联系检测率：图4显示了接触持续时间和接触检测率之间的关系。由于一个节点难探测到正在执行邻居发现在同一时间的邻居，即使随着Naive所有节点经常重复邻居发现，一些接触还是被错过。关于该方法，接触探测的空间覆盖将略低于Naive，因为它限制了发现者的数量减轻了能源消耗。另一方面，它也减少了同时存在邻近的节的邻居发现，从而发现可以探测其邻居会有更高的概率。因此，该方法比Naive可以更有效地检测短接触。

图4 接触探测率

移动节点之间的信息扩散：我们还评估了信息扩散能力，不同的平均接触探测间隔Tinq。图5显示了每个节点的平均设备发现间隔和信息传递率之间的关系。该方法实现了57%传递率，平均设备发现间隔为65秒。长的探测间隔导致错过接触，从而逐渐降低信息扩散能力，它仍然保持38%的传递率，平均探测间隔为308秒。总的来说，通过其协同接触探测和基于集群的链接管理机制，该方法可以提高信息传递率16%～83%。

图5 信息传递率

3）服务器的数据收集：最后，我们评估服务器的信息收集延迟，假设在每个集群成员上传通过3 g网络接收到的信息。图6和图7分别显示延迟时间的概率分布和集群通过实验的数量。最初，每个节点形成一个单节点集群，集群的数量是100。之后，集群逐渐增长通过合并相邻的集群，并最终集群的数量聚集在10～20之间。由于每个节点传感器收集的数据立即与其他集群成员共享，在5秒之内87%以上的信息达到服务器。考虑到集群的平均数量在整个模拟期间为14.3，与集中式蜂窝式架构相比，有效地减少了86%的通信链路的数量，同时保持一个合理的数据采集的性能。因此当地的移动节点之间的信息交换，有效地提高移动传感系统的可伸缩性。

图6 信息传递延迟

图7 集群的数量

4 结语

在本文中，我们提出了一种高效信息扩散协议的移动人群的机会网络传感。该方法检测行人组形成集群，在节点执行链接管理和接触探测下的协作方式。仿真结果表明，该方法可以提高信息传递率16%～83%与等效的接触探测间隔。

［1］J.Weppner，P.Lukowicz.Bluetooth based collaborative crowd density estimation with mobile phones［C］//in Proc.PerCom'13，2013：193-200.

［2］L.-Y.Wei，Y.Zheng，W.-C.Peng.Constructing popular routes from uncertain trajectories［C］//in Proc.KDD'12，2012：195-203.

［3］A.Ker¨anen，J.Ott，T.K¨arkk¨ainen.The ONE Simulator for DTN Protocol Evaluation［C］//in Proc.SIMUTools'09，2009.

［4］A.Vahdat，D.Becker.Epidemic routing for partially-connected ad hoc networks［C］//Tech.Rep.，2000.

［5］J.Burgess，B.Gallagher，D.Jensen，B.Levine.Max-Prop：Routing for vehicle-based disruption-tolerant net-works［C］//in Proc.INFOCOM'06，2006：1-11.

［6］W.Wang，V.Srinivasan，M.Motani.Adaptive contact probing mechanisms for delay tolerant applications［C］//in Proc.MobiCom'07，2007：230-241.

［7］B.Han，A.Srinivasan.eDiscovery：Energy eff i cient device discovery for mobile opportunistic communications［C］//in Proc.ICNP'12，2012：1-10.

［8］P.Basu，N.Khan，T.Little.A mobility based metric for clustering in mobile ad hoc networks［C］//in Proc.ICDCS Workshop，2001：413-418.

［9］C.Konstantopoulos，D.Gavalas，G.Pantziou.Clustering in mobile ad hoc networks through neighborhood stability-based mobility prediction［J］.Comput.Netw.，2008，52（9）：1797-1824.

［10］B.Peterson，R.Baldwin，J.Kharoufeh.Bluetooth inquiry time characterization and selection［J］.IEEE Transactions on Mobile Computing，2006，5（9）：1173-1187.

［11］G.Zaruba，S.Basagni，I.Chlamtac.Bluetrees-scatternet formation to enable bluetooth-based ad hoc networks［C］//in Proc.ICC'01，vol.1，2001：273-277.

A Neighbor Collaboration Mechanism for Mobile Crowd Sensing in Opportunistic Networks

WAN Xin
（Tianjin Guorui Digital Security System Co.，Ltd，Tianjin 100101）

Data collection from a crowd of mobile devices is anessential building block of emerging mobile sensing systems.In this paper，we propose an efficient information diffusion protocolfor sensor data collection via an opportunistic network.The proposed method detects groups of pedestrians based on the history of radio connectivity between the nodes and maintains a local network（i.e.，a cluster）among the detected group members.By collaboratively performing neighbor discovery and link management with the cluster members，it enhances energy-efficiency of the neighbor discovery and minimizes the information deliverydelay.Simulation results show that the proposed method canimprove the message delivery performance by 16%-83%with equivalent contact probing intervals.

data collection，opportunistic network，detects，information delivery，cluster

TP393

10.3969/j.issn.1672-9722.2017.10.023

Class Number TP393

2017年4月12日，

2017年5月19日

万辛，男，博士研究生，工程师，研究方向：通信网络及网络安全。