一种基于覆盖表融合的移动群智感知协作算法*
2018-07-26潘俊虹蒋建武2
潘俊虹**，蒋建武2，吴 薇
(1.武夷学院 数学与计算机学院，福建 武夷山 354300；2.苏州大学 计算机科学与技术学院，江苏 苏州 215006；3.认知计算与智能信息处理福建省高校重点实验室，福建 武夷山 354300)
1 引 言
移动群智感知作为一种新的群智感知模式，近些年来受到了业界的高度关注。移动群智感知利用参与者的移动智能终端如智能手机、平板电脑、智能手环等，收集所处环境信息，通过无线通信网络发送至云端网络服务器，服务器再对数据进行分析和处理，为上层的各种应用提供服务和决策支持[1]。移动用户的参与是移动群智感知最为显著的特征之一。移动群智感知属于参与式感知，参与式感知用户既可以是感知数据的提供者，也可以是感知数据的消费者[2]。移动群智感知目前已经应用在多个领域：文献[3]利用公车乘客随身智能终端感知收集周围信息预测公车到站时间；文献[4]利用市民参与者的手机拍摄照片，来进行水资源质量检测；文献[5]实现了一个由参与者手机收集噪音信息，来实时呈现细粒度的噪音地图系统。
移动群智感知网络本质是一种特殊的无线传感网络，其主要特点在于节点的移动性。由于手机等智能终端设备的普及和用户的移动特性，群智感知网络能以非常低的成本实现大规模和细粒度的感知。移动群智感知涉及到多个方面的策略和技术，包括感知数据采集、分析处理、参与者激励机制、感知数据发送、参与者隐私保护等[6]。本文研究主要内容是移动智能终端感知数据的融合以提升感知网络质量。在移动感知网络场景中，尤其在移动节点集中分布在某一区域，如学校、医院、车站或者某个时间段如下班、放学等情况下，以一定频率对周边环境进行感知，由于这种集中性，感知数据会简单重复叠加产生大量数据冗余，从而降低感知数据质量，浪费参与者设备能量和网络流量。文献[7]利用基于压缩感知数据采样方法，并在服务器上恢复重建感知信息的方式来减少数据传输代价；文献[8]采用基于效用的感知任务迁移实现移动感知节点直接协作来提高感知覆盖率；文献[9]采用线性加权并考虑节点吞吐最期望和能量消耗来解决分布式协作感知问题；文献[10]利用对空间区域划分，并通过skyline查询控制信道传输数据，以消除无线网络感知数据冗余。
本文的主要工作是针对集中性感知数据大幅冗余问题，对感知过程进行时空域划分，并对感知过程进行建模，结合感知充足覆盖的概念，通过在移动节点之间进行感知数据融合，减少节点的采样次数，在不影响感知数据质量的基础上，最大限度地去除冗余数据、优化感知数据，以提升整体感知性能，节约参与者耗能和网络流量。
2 移动感知系统建模
2.1 移动感知时空域划分
移动群智感知基于参与者的智能感知终端，利用参与者的移动实现对物理世界大范围的感知覆盖和信息采集，这样的感知数据在时空上可具有高度的关联特征。为了更好地对这些分布广泛的感知数据进行处理，需要对感知覆盖的时空域进行离散化处理。
假设有由n个移动节点集合U={u1,u2,u3,…,un}构成移动群智感知节点网络，这些节点以一定的轨迹在感知区域内进行移动，并以一定的频率对所处环境进行信息采样。节点ui在t时刻的位置表示为Loci(t)。我们对感知过程的时空域作如下划分：在空间域上，将整个感知区域划分为若干等份的单元格，单元格的大小即为感知空间的粒度，假设感知区域可划分成m个单元格，那么感知区域可表示为C={c1,c2,c3,…,cm}；在时间域上，我们将移动节点感知总时长划分为若干感知周期Tsp，每个感知周期开始，移动感知节点会对周围环境进行采样，并将数据发送至远程服务器。为了便于对感知系统建模，我们引入如下概念：
覆盖周期(Coverage Period)Tcp，由若干(r)个感知周期组成，即Tcp=rTsp。
感知时间跨度(Time span)T，时间跨度表示移动节点总的感知时长，由若干(d)个覆盖周期组成。
感知节点时空域划分如图1所示。
(a)时间域划分
(b)空间域划分图1 感知时空域划分Fig.1 Division of sensing time and space
2.2 感知网络相关定义
定义1 感知覆盖(Sensing Coverage)。当且仅当一个新的感知周期开始，某一个移动节点位置在某个单元格区域内时，称为该单元格被该移动节点覆盖。令δj(Loci(t))表示在t时刻移动节点ui是否覆盖单元格cj,则有
(1)
式中：δj(Loci(t))=1表示ui覆盖了单元格cj，δj(Loci(t))=0表示没有覆盖。在感知采样中，一个单元格只需要被覆盖一次即可，不需要一个单元格被一直覆盖，覆盖周期的大小也就表示了时间维度上的感知粒度。
定义2 覆盖充足度(Coverage Sufficiency Degree)。为第k个覆盖周期(1,2,3，…，d)内单元格cj被网络节点集合U中所有感知节点覆盖的次数总和，记为
(2)
覆盖充足度用来衡量感知过程中的时空覆盖质量，进一步地，我们给出充足感知覆盖的定义。
定义3 充足感知覆盖(Sufficient Sensing Coverage)。当且仅当一个单元格cj∈C在第k(k=1,2,…,d)个覆盖周期内被节点集合U中所有移动节点覆盖次数总和不小于覆盖因子ε(ε≥1)，我们称该单元格被充足覆盖，可描述如下：
CSDj(k)≥ε，k=1,2,…,d。
(3)
定义中覆盖因子的概念类似传统无线传感网的K-覆盖。无线传感网中给定区域中的每一个点都至少被K个传感器感知范围覆盖称为K-覆盖[11]，覆盖因子K决定了无线传感网中的感知数据的冗余度。与此类似，定义3中的覆盖因子ε的取值越大，产生的移动感知数据冗余越多，感知数据的信息蕴含也越多，质量越好，但是消耗参与者的能量和流量等代价也越大。对于本模型中的单元格而言，同一单元格的ε个感知数据可通过一定的方式进行融合，从而进一步提高感知数据的精确度。
本文假设的场景是移动节点集中性很高的区域，如果在这类区域活动，移动节点之间不进行协作，服务器后台也不对其采样过程加以控制，移动节点仍以一定频率进行采样，不仅会造成数据大量冗余，也过多耗费移动节点的能量和数据流量。下文将对感知过程进行分析，并在此基础上提出一种基于覆盖表的协作感知算法，最大程度上减少感知数据冗余，有效提升整个感知网络的性能，缩减移动节点代价，也能提高参与者积极性。
3 无协作感知模式分析
无协作感知模式即移动节点只按照固定频率对周围环境进行感知采样并上传数据，移动节点各自独立进行采样，节点之间没有任何协作，感知网络也没有任何控制措施，若移动节点所处区域是人群较为集中性的区域势必产生大量的感知数据冗余。本文以为CRAWDAD提供的数据集mobilitymodels dataset(v.2009-07-23)[12]为例进行研究。CRAWDAD是美国达特茅斯(Dartmouth)学院的一个无线网络数据公共社区资源，提供无线网络踪迹数据，包括数据本身及其描述文件(元数据)。基于JavaFX平台对数据集感知区域进行时空域划分，将目标感知区域划分成16×28个单元格，每个格子面积为500 m×500 m，感知周期Tsp设为30 s，覆盖周期Tcp设为1 800 s，覆盖因子ε设为1，92个移动节点在4 h之内的移动轨迹如图2所示。图中黑点部分为移动节点的移动轨迹，其中有12个红色边框单元格为4 h感知时间内一直处于充足覆盖的状态。这12个被充足覆盖的单元格被92个移动节点覆盖次数如表1所示。
图2 移动节点轨迹分布图Fig.2 Trajectories of mobile nodes
单元格覆盖次数c147414c148544c161429c1644 594c165155c1801 671c18113 388c18248c19614 073c1972 780c2121 158c21324
由于我们将覆盖周期设置为1 800 s，也就是30 min，因此只需每30 min在每个单元格中采样一次就可满足需要。在整个4 h感知时长内，每次单元格只要被覆盖8次即可。但从表1中可以看出这12个单元格覆盖次数都远远超过8次，其中单元格c181和c196更是分别达到了13 388次和14 073次，是所需覆盖数的1 000倍以上。
进一步地观察图2中单元格c196分别被网络中所有92个节点覆盖的次数，不同的移动节点对于单元格c196覆盖次数差异也很大。在无协作模式下，移动节点覆盖信息只保持在自己手中，节点之间不共享覆盖信息，有些移动节点对单元格覆盖次数较多，而有些节点几乎没有覆盖过单元格c196。由此可见，此场景中移动节点在无协作模式下，冗余感知数据会出现爆发式的增长，这也就大幅度降低了网络感知的质量。因此有必要设计一种控制机制，使得节点之间共享覆盖信息，减少不必要的感知数据，提高感知整体性能。下文将提出一种基于覆盖表的感知融合算法，通过覆盖信息融合机制来控制整个移动感知过程，有效降低感知冗余。
4 基于覆盖表融合的协作感知算法
4.1 感知覆盖表融合算法
从上文分析可知，在集中性较强的场景中，各节点对单元格覆盖的贡献差异很大，主要在于各节点之间没有分享覆盖信息。基于此，本文设计了一种名为感知覆盖表(Sensing Coverage Table,SCT)的存储结构，每个移动节点都在本地维护一张覆盖表，并根据节点和其他节点之间共享的覆盖信息动态更新。SCT结构由一组带有3个属性值
移动节点的SCT动态更新融合算法如下：在每个覆盖周期开始时，节点清空本地SCT，当网络中两个移动节点ui和uj相互靠近并进入彼此的通信范围时，相互交换各自的感知覆盖表SCT，并进行融合处理。首先节点uj发送自己的SCTj给节点ui，对于SCTj中每一组
for each
tag=0;
for each
if(cj==ci) then
tag=1;
if(fi==1 andfj==1) then
ei=min(ei+ej,ε);
fi=0;
else if(ei ei=ej; fi=0; end if end if end for if(tag==0) then add end if end for 移动节点之间的无线智能终端都装备有基于802.11协议的短距离通信接口，邻近的移动节点能组成自组网络实现端对端通信，无需消耗网络流量，同时也可以最大程度地扩散节点对单元格的覆盖贡献信息，如图3所示。因此每个节点都能够准确地了解单元格在当前覆盖周期内被覆盖的情况，为协作感知算法提供了前提条件。 图3 移动节点覆盖信息扩散图Fig.3 Diffusion graph of coverage information of mobile nodes 在上节所述的感知覆盖表融合算法的基础上，我们进一步给出基于SCT融合的移动节点感知算法，其基本思想如下：在每个覆盖周期开始时，移动节点清空本地感知覆盖表SCT，当一个感知周期开始时，节点ui在对单元格cj进行采样之前，先判断本地SCTi中是否有与单元格cj对应的元组，若元组存在且采样次数等于覆盖因子ε，则本次不采样，反之则进行采样，并更新自己的SCT：如果原SCT不存在cj对应的元组，则直接将 fort=TsptoTdo ift%Tsp==0 then; SCTi=NULL; end if 获取当前节点ui的位置:Loci(t) 获取当前节点ui覆盖的单元格cj:δj(Loci(t))=1; ifcjnot inSCTithen 对单元格cj采样; add end if ifcjinSCTiandej<εthen 对单元格cj采样; ej=ej+1; end if end for 本文使用的是来自CRAWDAD网络社区、由Injong Rhee等人提供的韩国科学技术院(Korea Advanced Institute of Science and Technology,KAIST)校园里92个行人4 h内移动轨迹GPS数据，在SUN ONE平台进行仿真实验。我们将整个感知区域划分为200 m×200 m单元格，感知周期Tsp设为30 s，覆盖周期Tcp设为1 800 s，时间跨度T为4 h。移动节点共92个，每个节点通信范围为70 m。 衡量协作感知的性能指标包括平均覆盖延迟(一个单元格平均多长时间被充足覆盖一次)和采样总数(感知网络中所有节点在充足覆盖的单元格中执行的采样总数)。实验仿真对比了3种协作感知模式的性能指标：一是原始感知模式,每一个感知周期开始，只要这个移动节点在有效覆盖的单元格里都进行采样，即不采用节点选择算法，节点与节点之间也没有共享覆盖信息；二是本地控制模式,节点在感知周期到来时，依照本地存储的覆盖表判断是否采样，节点之间也没有通信共享覆盖信息；三是本文所述的基于SCT信息融合的协作感知模式。 表2给出了当覆盖周期Tcp=1 800 s和覆盖因子ε=1时，一些单元格的在不同模式下的平均覆盖延迟。从表2中可以看出，原始感知模式下单元格的平均覆盖延迟最小，本地控制模式次之，基于SCT融合的控制模式平均覆盖延迟最大，但延迟时间均小于所设定的覆盖周期1 800 s。图4给出了在不同时长的覆盖周期在3种不同覆盖因子下，3种感知模式的所有单元格的平均覆盖延迟。可以看出，当覆盖因子ε值增加时平均覆盖延迟相应减少，这是由于节点执行了更多采样导致，虽然降低了覆盖延迟但也消耗了更多的节点能量。 表2 单元格平均覆盖延迟Tab.2 Average coverage delay of cells (a)Tcp=900 s (b) Tcp=1 800 s (c)Tcp=3 600 s图4 3种感知模式平均覆盖延迟时间Fig.4 Average coverage delay time of three sensing models 表3和图5对比了以上3种感知模式下在给定感知时长内所有充足覆盖的单元格采样总数。 表3 3种模式下移动节点采样总数Tab.3 Total number of mobile node sampling in three modes 图5 3种感知模式采样总数对比Fig.5 Comparison of total number of three sensing sampling models 表3和图5显示，基于覆盖表融合协作的感知模式下，采样总数比原始感知模式下采样总数大幅减少，也少于本地控制模式下采样总数。当覆盖因子ε=1时，基于SCT融合的协作感知模式可消除原始感知模式下95.96%的感知冗余数据，也可消除本地控制模式下，36.98%的冗余感知冗余数据；当覆盖因子ε=2时，消除感知冗余幅度分别为95.36%和36.88%；当覆盖因子ε=3时消除感知冗余幅度分别为94.16%和36.82%；当覆盖因子ε=4时，消除感知冗余幅度分别为93.33%和33.82%；当覆盖因子ε=5时，消除感知冗余幅度分别为92.6%和31.23%。可以看出，在ε取值不超过5时，基于SCT融合的协作感知模式感知冗余数据消除率对比原始模式都在92%以上，对比本地控制模式消除率也有31%以上。由此可见，基于SCT融合的移动协作感知模式能有效地消除感知冗余数据，从而减少移动节点的耗能，也节省移动节点的数据流量，同时还可以避免因集中采样传送数据产生的网络拥堵状况。 实验仿真结果如表4数据显示，覆盖因子ε值的逐渐变大，充足覆盖的单元格数逐渐减少，这就表明，随着ε值的增大，如果单元格想要被充足覆盖，必须得到更多的覆盖次数。在理想条件下每个单元格仅需在每个覆盖周期被釆样一次即可，即ε=1，然而实际因素要复杂得多。比如：参与节点的移动轨迹是具有随机性的；某些节点可能在某个时间电量耗尽或者其他不可用状态，例如参与用户正在打电话；仅一个节点的采样数据容易产生测量误差等。因此，必须有一定的覆盖冗余也就是说通常需要ε>1来应对现实中的一些不确定因素的干扰。同时，在节点之间进行覆盖表融合扩散时，用于扩散交换探测邻居节点的周期越短，则覆盖信息在整个网络中传播地越快，但同时也会有更多的能量消耗用于数据传输。需要综合考虑如何进行覆盖因子选取和探测频率的设定，以达到一个最优的效果，这些已经超出本文的研究范围，在此不作赘述。 表4 不同覆盖周期充足覆盖单元格数Tab.4 Time ofsufficient coverage cell in different coverage period 综合以上实验结果可知，使用基于覆盖表信息融合的感知节点协作进行感知数据收集，移动节点之间很大程度上避免了重复感知，相比无协作的原始感知模式和本地控制模式，该算法能大幅消减感知数据冗余，移动节点增加的能耗体现在增加本地节点计算量和节点之间交换融合信息的通信两方面，但由于协作感知算法复杂度较低，移动节点之间以指数形式快速扩散覆盖表信息的相对有限通信能耗，相比每个移动节点在不同的单元格中不断采样向远程服务器发送感知数据来说，移动节点增加这点能耗要少很多。另一方面，基于覆盖表信息融合的方式感知网络单元格平均覆盖延迟时间相对提高了，但实验表明其覆盖延迟时间均在覆盖周期以内，在实时性不强的应用当中，并不影响网络感知的质量。因此从整体上说，该算法较大程度地提升了网络感知数据质量，同时也有效地降低了移动节点耗能。 移动感知网络感知数据冗余度高主要是由无协作模式下移动节点之间没有共享覆盖信息，过多重复采样造成的。本文对感知区域进行时空域划分，并对整个感知过程进行建模，利用感知覆盖表来表示移动节点对单元格的覆盖信息，并设计了一种感知覆盖信息的交换融合算法，通过这种移动协作模式收集感知数据，达到减少重复感知。虽然该算法增加的单元格的覆盖延迟时间，但大幅消除了节点感知冗余数据，达到了节省移动节点能耗和网络流量的目的。但是影响移动感知质量的因素较多，实际情况也更为复杂，因此本文算法也存在一定提升空间：一是算法没有考虑时间维度上，采样数据存在的差异性问题；二是空间划分粒度大小对算法效率的影响；三是如何选取覆盖因子达到节点能耗和感知数据质量的平衡等。我们将对这些方面进行更深入研究，以期进一步提升算法性能。
4.2 基于SCT移动节点协作感知数据收集算法
5 实验仿真及结果分析
5.1 平均覆盖延迟
5.2 移动节点采样总数
5.3 覆盖因子设定
5.4 仿真结果分析
6 结束语
