移动感知中基于机会型网络的高效信息传输协议

路春辉，夏云霓

移动感知中基于机会型网络的高效信息传输协议

路春辉，夏云霓

对一组移动设备进行数据采集是新兴移动感知系统的重要组成部分。然而现有的数据采集方法在Wi-Fi网络环境下可用于数据上传的机会型有限，不适用于大规模移动感知场景下的数据传输服务。为此，针对传感器数据采集提出一种基于机会型网络的高效信息传输协议。仿真结果表明，该方法可在连接探查间隔不变的情况下将消息传输性能提升 16% -83%，信息传输延时也要低于已有方法。

数据采集；移动感知；机会型网络；信息传输

0　引言

随着移动感知技术[1,2]的迅速发展，目前已经诞生了多种创新性应用和服务。通过从移动设备（比如智能手机）内置的传感器中采集测量数据，我们不用密集部署感知设备即可确定环境中的当前情况及人群行为[3,4]。为了提供这样的移动感知应用，我们需要一种可扩展平台从一组移动设备中采集传感器数据，并传输给网络中的服务器。Wi-Fi热点等公共 IT基础设备在城市中非常普遍（比如火车站和超市中），机会型网络技术为移动感知系统的数据采集提供了一种新方法[5]：每个节点临时性地将传感器数据存储在其本地内存中，当来到Wi-Fi热点附近时将数据上传到服务器。这种方法虽然会导致数据采集存在一定延时，但是可以降低用户参加感知服务的门槛[6]。

为了有效地提升数据上传机会，缓解数据采集延时，本文提出利用短距离无线通信手段在相邻节点间本地共享传感器数据，然后按照机会型方式利用3G或Wi-Fi网络将采集到的数据上传到服务器，便可显著提高数据采集的效率系统架构如图1所示：

图1　本文提出的系统架构

本文提出一种可以在机会型网络中的移动设备间共享传感器数据的高能效信息传输协议。在集会或超市等人群密集场所，人们往往成群结对，且运动特点与同伴类似（比如朋友，家庭或者往同一方向行走的陌生人）。本文方法可根据节点间的无线电连接历史来检测出这些行人群组，并利用群组成员维护一个局域网（即一个聚类）。通过利用聚类成员合作进行相邻节点检测和链路管理，本文方法可提升相邻节点的检测能效，并解决对节点度的约束。

1　传感器数据共享

1.1假设

假设公共场合（比如超市）的人群使用支持 ad-hoc通信功能的移动设备（即移动节点或简称为节点）。为了识别

人群行为或周围场景，持续采集每个节点的传感器数据，并在应用预处理完数据后与环境中的其他节点共享数据。无线访问点（比如Wi-Fi热点）在环境中稀疏部署，当移动节点在访问点周围时，将采集到的传感器数据上传到网络中的服务器。另外假设消息尺寸远小于无线网络带宽,每个节点的缓存空间足够大，缓存溢出现象不会发生。

2.2聚类

本文根据关于节点间无线连接的近期历史数据来检测各组行人。然后，在检测出来的群组成员间形成一个聚类，用于本地合作。每个聚类有一个称为簇头（CH）的特别节点，负责聚类维护及聚类内部的通信控制。设有一个CH u0及其聚类M，N0（t）表示时间t时u0的相邻节点集合，M中的所有聚类成员满足如下条件，如公式（1）：

因此，节点ui与u0的连接时间保持T秒以上才能加入聚类。阈值T应该远大于独立运动的节点的连接持续时间，通过仿真实验或者分析节点的历史轨迹数据可以估计该阈值。在开始时，每个节点形成只有一个聚类成员且节点本身担任CH的聚类。此后，CH周期性地进行连接探查，并更新其聚类中的成员集合，以便所有成员满足式（1）中的条件。

聚类成员不断地维护一个聚类内部连通网络。聚类成员采集到的所有传感器数据迅速通过聚类内部通信链路与聚类其他节点共享。聚类成员采取合作方式对聚类内部链路进行管理，相邻聚类间最多只建立一条通信链路。因为传感器数据迅速在聚类成员中共享，所以可以通过一条通信链路将聚类维护的数据传输给相邻聚类中的所有节点。于是，本文方法通过少量通信链路即可完成聚类间数据传输，降低了节点度约束导致的数据传输延时及链路建立时的开销。

此外，聚类成员在空间上互相之间距离较近，它们的相邻节点集合应该非常类似。利用这一特点，CH在每轮中选择少量聚类成员（称为检测节点）进行相邻节点检测任务。这种方法在保持合适的连接检测性能的同时，降低了非常消耗能量的连接检测平均频率。

3　合作式连接探查

当节点ui进行相邻节点检测时，它将迅速切换其无线电频率，并不断地发射询问信息。相应地，ui在其相邻节点检测期间，难以对相邻节点的询问做出响应。因此，每个相邻节点uj的检测概率取决于ui检测期间uj处于非检测状态的持续时间（即有效扫描时间Tc）。本文方法通过选择少量检测节点并在聚类成员间共享它们的检测结果，有效提升了能效及对相邻聚类检测过程的响应性。

设M（t）表示时间t时的聚类成员集合，Ni（t）表示成员ui∈M（t）的相邻节点集合。对每个相邻节点u∈Ni（t），u也与其他成员uj相邻的概率与它们的通信范围重叠面积成正比。假设无线传输范围为 R，ui和uj间的距离有rij=r，则上述概率可表示为公式（2）：

这里考虑只有n个聚类成员（即检测节点）D（t）⊆M（t）进行相邻节点检测的情况。假设非检测节点ui和每个聚类成员间的距离服从概率分布f（r），则ui的相邻节点（比如u）被其聚类中的检测节点uj发现的概率为公式（3：

其中Xij表示ui的相邻节点被uj发现这一事件。然后，本文研究非检测节点ui的一个相邻节点被聚类中至少一个检测节点发现的概率。假设u1,u2,,un表示聚类中的n个检测节点，ri1,ri2,,rin表示与每个检测节点的距离。不失一般性，假设ri1≤ri2≤…≤rin，则概率P（Xi1∨Xi2∨…∨Xin）满足如下条件如公式（4）：

对F1（r）求微分，可以获得ri1的概率密度函数如公式（6）：

根据式（3，4，6），我们有公式（7）：

图2　基于协作式连接探查的相邻节点检测概率

当聚类成员间的最大距离为5m时，即使聚类中只有一名成员为检测节点时，非检测节点的相邻节点被检测出来的概率也达84%。因此，通过约束聚类中的检测节点数量，本文方法可以有效降低平均连接探查频率，同时保持合理的连接检测率。

3　协议设计

3.1概述

开始时，每个节点形成规模为1的聚类。然后，每个聚类独立地重复如下 3个阶段进行聚类维护和消息传输。由CH随机确定每一轮的总持续时间（包括3个阶段），如图3所示：

图3　协议设计

请注意，如果聚类只有一个节点，则第2和第3阶段删除。此时，CH处于非检测节点状态直到下一轮开始。

1）聚类维护：CH进行相邻节点检测以获得当前的相邻节点集合（图 3（a））。同时，其他节点保持非检测节点状态，以便对CH的询问做出响应。然后，CH根据收集到的连接性信息来更新其聚类成员。

2）连接探查：CH从聚类成员中选择（n-1）个检测节点（除了CH本身）。然后，被选成员进行相邻节点检测，以检测出与相邻聚类的连接（图3（b））。

3）消息维护：CH与检测节点建立可以与相邻聚类中的节点进行通信的通信链路，以便交换各聚类维护的传感器数据（图 3(c)）。为了接受来自相邻聚类的连接请求，消息交换后迅速拆除聚类间链路。最后，通过聚类内部通信链路在聚类成员间共享接收到的传感器数据。

4.2聚类维护

在聚类维护阶段，CH（比如u0）进入检测节点状态，并向相邻节点广播询问信息。当节点ui接收到询问时，ui返回包括其聚类成员ID（比如蓝牙MAC地址）的询问响应消息。因此，u0获得其当前相邻节点集合N0（t）及检测出来的每个相邻节点的聚类成员｛Mi|ui∈N0（t）｝。如果两个相邻节点ui,uj∈N0（t）属于同一聚类，则Mi=Mj。将聚类成员的ID作为该项目的内容，则CH不用额外建立链路即可采集相邻聚类的信息。

为了缓解丢失连接对聚类维护的影响，本文利用近 W轮期间的连接性历史信息对当前相邻节点集合进行补充，如公式（8）：

相邻节点检测完成后，CH根据连接性历史信息更新其聚类成员。具体来说，它增加和删除相邻节点，以便所有聚类成员ui满足如下条件如公式（9）：

其中T与式（1）相同。根据上述定义，CH u0按照如下步骤更新聚类成员：

1）如果成员ui未包含于当前相邻节点集合N0'（t）中，则将其从聚类中删除。此后，ui成为CH，并形成一个新的单节点聚类。

2）如果相邻聚类Mi中的所有成员满足式（9），则u0将所有这些节点纳入其自身聚类中，且合并M0和Mi。

于是，u0获得其当前成员集合M0'。最后，u0将更新后的成员集合通知给所有的聚类成员，以便开始聚类内部网络（类内网络）的拓扑维护。

3.3聚类间通信

在通信阶段，检测节点ui∈D（t）根据当前相邻节点集合Ni（t）和各个相邻节点的聚类成员信息计算其相邻聚类集合，形成一个连接队列Qi=｛Mj|∃uj∈Ni（t）Mj｝。然后，它从每个相邻聚类Mj∈Qi从Ni（t）Mj中随机选择一个成员，并向其发送一个连接请求。同时，在检测节点间实施如下排斥控制：在向相邻节点uk发送连接请求前，检测节点ui向自己的聚类成员发送LOCK(uk)消息。这可在一段时间内抑制其他检测节点向Mk中的成员进一步发送连接请求。如果与uk的通信链路成功建立，则ui通过发送一条CONNECTED(uk)消息即可通知其他检测节点通信链路已经成功建立。然后，其他检测节点将uk的聚类从其连接队列中删除。如果与uk的通信链路建立失败，则ui试图与聚类中的另一个成员建立一条链路，在相邻聚类间建立了一条跨聚类链路。

4　仿真实验

4.1仿真配置

为了评估本文算法的性能，我们利用ONE模拟器[8]进行仿真实验。假设场地面积50m×50m，Wi-Fi热点个数为20个，有100个移动节点随机走动，每10个节点为一组：我们生成10个参考点，每个参考节点表示每组的平均行为。参考点遵从random waypoint mobility模型，且在场地内独立运动。在每种运动场景中，参考点从场地中随机选择一个目的路点，然后以恒定速度向目的地运动。从0.5 m/s至1.5m/s范围内随机选择一个数值作为移动速度。到达目的路点后，参考点停留120秒，然后向下一目的地运动。当参考点确定了一个新的目的地时，相应的群组成员也选择距离参考点3米之内的各自目的地。。

每个节点每隔 10秒发送一个 2Kb消息（即传感器数据），通过蔓延式路由向环境中的所有节点发送数据。假设消息传递的截止时间为60秒，将消息投递率定义为在截止时间前成功到达节点的消息所占比例。假设蓝牙规格为v2.1+EDR，则无线通信的范围和速度分别设置为 10m和 2Mbps。每个聚类进行连接探查的间隔从Tinq±5.12范围中随机选择，相邻节点检测的持续时间为5.12秒。参数Tinq用于调整每个聚类进行连接探查的平均间隔。默认情况下，我们设置Tinq为15.36秒。在仿真实验中，根据文献[9]中的理论模型确定相邻节点检测概率，并将每个节点通信链路的最大数量限制为7个。我们假设建链的时间开销为2秒。以上述假设为基础，进行了3600秒的仿真实验，并将本文算法与非协作性协议（称为Naïve）做比较。在Naïve协议中，所有节点重复进行设备检测的时间间隔从Tinq±5秒范围内随机确定，并向所有检测出来的相邻节点发送连接请求。

4.2仿真结果

（1）连接检测率：连接持续时间和连接检测率间的关系，如图4所示：

图4　连接检测率

因为一个节点难以检测出正在同时进行相邻节点检测的相邻节点，所以即使所有节点利用Nave算法频繁进行相邻节点检测，仍然会有连接丢失现象。对本文算法来说，由于为了降低能耗而限制了检测节点数量，所以连接探查的空间覆盖范围低于Naïve算法。另一方面，它还缓解了相邻节点间的相邻节点并行检测，因此检测节点可以较高概率检测出它的相邻节点。于是，本文算法检测出短暂连接的性能高于Naïve算法。

（2）移动节点间的消息传输：我们还评估了平均连接探查间隔Tinq变化时的消息传输性能。每个节点的平均设备检测间隔和消息投递率间的关系如图5所示：

图5　消息投递率

当平均设备检测间隔为65秒时，本文算法的检测率为57%。探查间隔较长时造成连接丢失，进而逐渐降低了消息传输性能，但是当平均探查间隔为308秒时投递率仍然达到38%。总体来说，本文算法通过协作式连接探查和基于聚类的链路管理机制，将消息投递率提升了16%-83%。请注意，如果相邻节点检测和消息交换可同时完成（即在理想的通信情况下），则消息投递率为73%。

（3）面向服务器的数据采集：我们评估了服务器的消息采集延时，假设每个聚类中的成员通过3G网络上传接收到的消息。实验中用于信息传输的聚类数量变化情况如图6所示：

图6　聚类数量

在开始时，因为每个节点形成一个单节点聚类，所以聚类数量为100。此后，通过与相邻聚类合并，聚类规模逐渐上升，最终聚类数量在10到20之间。因为每个节点采集的传感器数据与其他聚类成员迅速共享，超过87%的消息在5秒钟内到达服务器。考虑到仿真期间聚类平均数量为 14.3个，与基于蜂窝的集中式架构相比，在保持数据采集性能的同时，与服务器相连的通信链路数量下降了86%。因此，移动节点间的本地消息交互有效提升了移动感知系统的可扩展性。

5　结论

针对现有信息传输方法无法适用于大规模移动感知应用场景的不足，提出一种基于机会型网络的高能效信息传输协议，可实现机会型网络的移动群组感知。它通过检测出行人群组来形成多个聚类，且聚类中的节点进行协作式链路管理和连接探查。仿真结果表明，本文方法采用相同的连接探查间隔后，可将消息投递率提升16%-83%。下一步工作的重点是对移动感知应用中的数据隐私保护问题进行研究，在保证不泄露客户隐私的前提下，进一步提高移动感知的信息采集效率和效果。

[1] 王田. 一种基于蓝牙名的相对移动感知定位[J]. 计算机仿真,2014,31(4): 290-294

[2] 杜扬,黄河,孙玉娥,等. 地理位置相关移动感知系统任务分配问题研究[J]. 计算机研究与发展,2014,51(11): 2374-2381

[3] Weppner J,Lukowicz P. Bluetooth based collaborative crowd density estimation with mobile phones[C]// 2013 IEEE international conference on Pervasive computing and communications (PerCom). San Diego,California,USA: IEEE Press,2013: 193-200

[4] Wei L Y,Zheng Y,Peng W C. Constructing popular routes from uncertain trajectories[C]//Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. Beijing,China: ACM Press,2012: 195-203

[5] 徐佳,李千目,张宏,等. 机会型网络中的自适应喷雾路由及其性能评估[J]. 计算机研究与发展,2015,47(9): 1622-1632

[6] 冯诚,李治军,姜守旭. 无线移动感知网络上的数据聚集传输规划[J]. 计算机学报,2015,38(3): 685-700

[7] Zaruba G V,Basagni S,Chlamtac I. Bluetrees-scatternet formation to enable Bluetooth-based ad hoc networks[C]// IEEE International Conference on Communications(ICC). Cape Town,South Africa: IEEE Press,2010,1: 273-277

[8] Graeser K,Konge L,Kristensen M S,et al. Airway management in a bronchoscopic simulator based setting: An observational study [J]. European Journal of Anaesthesiology (EJA),2014,31(3): 125-130

[9] Peterson B S,Baldwin R O,Kharoufeh J P. Bluetooth inquiry time characterization and selection [J]. IEEE Transactions on Mobile Computing,2006,5(9): 1173-1187

Efficient Information Transmission Protocol Based on Opportunistic Network in Mobile Sensing

Lu Chunhui1,Xia Yunni2
(1. School of Information Engineering,Guang Dong Engieering Polytechnic,Guangzhou 510520,China; 2. Computer College,Chongqing University,Chongqing 400044,China)

Data collection from a crowd of mobile devices is an essential building block of emerging mobile sensing systems. However,the existing data collection methods cannot be used for the data upload service in the Wi-Fi network environment,and cannot be used for data transfer service in the large scale mobile sensing scene. To solve this problem,an efficient information dissemin- ation protocol for sensor data collection is proposed via an opportunistic network in this paper. The proposed method firstly 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,in order to realize the sensor data sharing between the mobile devices. By collaboratively performing neighbor nodes detection and link management with the cluster members,it enhances energy-efficiency of the neighbor discovery and minimizes the information delivery delay. Simulation results show that the proposed method can improve the message delivery performance by 16%-83% with equivalent contact probing intervals,and the delay of information transmission is also lower than the existing methods.

Data Collection; Mobile Sensing; Opportunistic Network; Information Transmission; Clustering; Neighbor Nodes Detection

TP393

A

1007-757X(2016)03-0033-04

国家自然科学项目资助（61472051/ 020302）。

路春辉（1979-），女，广东工程职业技术学院，信息工程学院，硕士，讲师。研究方向：社交网络、数据挖掘，广州，510520

夏云霓（1980-），男，重庆大学，信息工程学院，博士后，副教授，硕士生导师，研究方向：社交网络、数据挖掘，重庆，400044

（2015.11.06）