基于时空关注的移动感知节点选择算法

郭 慧,程良伦

(广东工业大学 计算机学院,广州 510006)

0 概述

移动互联网业务正在迅速发展。感知区域的高覆盖率是保证移动感知任务成功执行的基础[1],不同的感知任务有其特定的时空限制,且参与节点也有自身的移动特征[2]。大量移动节点的参与会造成服务器数据冗余,且在节点达到一定数量之后,覆盖率并不会随其数量的增加而提高[3]。因此,选择合适的移动感知节点来执行感知任务势在必行[4]。

文献[5]研究了机会感知中的用户选择:首先研究静态节点选择问题,之后将其推广到具有不确定性移动轨迹的用户移动模型中进行研究。文献[6]提出一种移动群智感知(Mobile Crowdsensing,MCS)系统,文献[7]针对个人用户的能源消耗及由数据传输引起的隐私问题,研究MCS系统中的任务分配问题。为了使选择节点之后得到的覆盖范围最大,研究人员从任务组织者[8]、执行者[9]以及不同的激励代价[10]出发,研究了移动互联网感知用户选择问题。此外,文献[11]针对多节点少任务及多任务少节点2种情况来研究移动互联网感知节点选择;文献[12]在考虑不同的感知数据精度要求及节点的移动性与任务的特定时空属性要求的情况下,研究移动感知中基于位置的近优任务分配算法;文献[13]针对移动感知中基于位置的优化分配算法,提出一种基于链路可靠性的AdHoe网络路由协议(LRBA)分配算法,获得的数据精度是传统算法的5倍。但以上研究绝大多数未考虑任务的特殊时空属性或未研究节点位置之间的关联性。

文献[14]基于联盟的协同方法研究了一种交通信息采集传感器网络任务分配方法;文献[15]提出用自适应随机阈值算法来研究空间众包环境下的3类对象在线任务分配。前者只针对特定的应用,不具有通用性,而后者任务分配时,并未考虑节点冗余问题及覆盖率问题。

本文针对国内外对于移动节点选择忽略研究节点位置的关联性问题,提出一种移动互联网基于时空关注的移动感知节点选择算法。该算法根据节点位置之间的关联性及任务的时空要求来选择移动感知节点。

1 问题描述

假设在一个大区域内有多个移动感知节点,每个节点只能感知一个小区域的信息,且所有移动感知节点的历史轨迹已知但下一时刻的位置未知。根据移动感知节点的感知范围,将区域划分成若干个子区域。如果在一个感知周期内的某个时间段有移动节点经过一个子区域,则认为该子区域在该感知周期内被覆盖。

本文的目标就是在一定的感知周期内,通过研究节点位置之间的关联性,在给定历史轨迹的所有移动节点中选择一个最小数量的移动节点参与者集合,使该集合节点的感知区域覆盖率大于或等于一个提前定义的覆盖阈值。

本文提出的移动节点选择问题可通过以下数学模型来描述:假设所有移动节点的集合为U,U的历史轨迹的集合为Track(U),感知目标区域E;Tu表示从U中选出来的节点集合,Ci(Tu)表示在第i个感知周期,被Tu中的节点覆盖的子区域集合。本文的目标就是从U中选择一个集合Tu,并且选出的集合Tu满足以下的限制:

min|Tu|

(1)

(2)

其中,N表示碳检测任务中的感知周期总数,Rcover表示阈值覆盖率。需要注意的是,提前并不知道节点将何时出现在某个感知区域。

针对上述问题,本文提出移动互联网时空关注的移动感知节点选择算法,其总体流程如图1所示,主要分为3步:

图1 移动节点选择算法总体流程

1)轨迹数据输入。在数据输入阶段,输入全部节点的历史移动轨迹数据,为下一阶段的数据处理做准备。

2)移动节点轨迹预测。在数据处理阶段,将节点的轨迹数据进行映射,通过计算得到每个节点在某个特定周期出现在各小区域范围内的概率,进而预测感知节点的移动概率。

3)移动节点选择。在节点选择阶段,根据数据处理阶段的结果,利用本文的移动互联网时空关注的移动感知节点选择算法,对移动感知节点进行选择。

4)选择的结果输出,并进行性能分析。

2 移动节点轨迹预测

假设所有的参与节点的历史轨迹提前已知,本阶段将利用历史轨迹来计算每个节点的下一周期的移动位置概率。

2.1 数据准备及映射

映射移动轨迹:将感知区域分为若干个固定的子区域,给定所有节点的历史移动轨迹,感知周期也为固定的时间间隔(例如1 h为一个周期),该步骤将每个节点的轨迹映射到N个感知周期。然后计算每个节点在每个感知区域的每个感知周期的平均出现次数λu,i,e(在第4节有具体阐述),本文假设感知节点的出现服从泊松分布[16],表达式如下:

(3)

其中,λu,i,e是泊松密度,指在某感知周期i,感知节点u出现在子区域e的平均次数,n指在特定子周期子区域节点u的出现次数。

2.2 移动节点的预测概率

预测感知节点的移动概率:利用之前得到的λu,i,e来估计节点概率Pi,e(U),节点在每个感知周期i(0≤i≤N)至少在每个目标区域e(e∈E)出现一次的概率。

(4)

3 移动节点选择算法

本节利用第2节得到的各节点在各个周期的概率来选择节点。定义处理过程中得到的全部节点在各周期的概率矩阵集合为元胞数据。一个元胞中包含全部移动节点在对应周期的概率矩阵,即元胞中的一个元素对应一个节点在固定周期的概率矩阵,此处概率矩阵的元素对应固定节点在固定子周期的子区域轨迹概率。其选择算法流程见图2。

图2 移动节点选择算法流程

移动节点选择算法步骤描述如下:

步骤1计算每个节点在全部周期的有效性,得到有效性矩阵Zallturn。

步骤2将节点两两集合,选出有最大有效性的节点,加入Tu。

步骤3将所有剩余的节点与Tu结合,即Tu∪Uremain{j},j∈(1,2,…,h),计算其有效性,选出拥有最大有效性的节点加入Tu。

步骤4循环步骤2,直到得到的覆盖率不再增加,即为最终节点集合Tu。覆盖率是指在特定周期选择的节点对感知区域的覆盖情况,即在感知周期移动节点的移动轨迹对子区的覆盖范围占整体感知区域的比例。

概率矩阵Zallturn计算公式如下:

(5)

E∈{[latmin,latmax][lonmin,lonmax]}

(6)

其中,lat表示维度,lon表示经度。

给定全部相联的集合Tu2∪Uremain{j},本小节计算这些相联集合的Utility,此处每个联合集合的Utility具体是指在全部的感知周期内,感知区域被该相联集合的感知节点覆盖的期望,计算公式如下:

(7)

其中,Qi,e(Tu2∪Uremain{j})指某个给定的区域在某个特定感知周期被集合Tu2∪Uremain{j}覆盖的概率,计算公式如下:

(8)

在以上得到的众多Utility中,选择最大的一个集合,将其作为新的集合进行下一轮的迭代,直到对应的覆盖率不再增加。

例如,假设已知若干节点的历史移动轨迹,首先将各个节点在对应子周期的移动轨迹映射在对应的子区域内,统计一段时间内,节点在该子周期该子区域出现的次数,从而求得平均出现次数,并利用式(3)和式(4)求出节点出现在该区域的概率,再根据式(5)和式(6)求得概率矩阵。接着,先将节点两两结合,根据式(7)和式(8)求出节点关联有效性,选出关联有效性大的节点加入感知节点集合,之后继续将感知节点集合中的节点与剩余节点分别结合,计算关联有效性,直到得到的集合中的覆盖率不再增加即为最终的感知节点集合。

4 仿真与结果分析

本文采用罗马市2014年2月的368辆出租车真实移动轨迹[17]作为仿真数据集,利用仿真软件MatlabR2014b,在Window10平台中仿真本文的节点选择算法。因此,根据罗马市的实际地理位置,本文设定的感知区域为经度坐标区间为[41.65°,42.15°],纬度坐标区间为[12.04°,12.84°]的区域。将目标区域划分成5×8个感知子区域(每个区域的大小为0.1纬度×0.1经度)。感知时间设为8:00—18:00,每个感知子周期设定为1 h,即将整个感知时间划分成10个子区间。选取100个出租车作为移动感知节点,其上均载有CO2传感器。

首先,输入出租车10 d的移动轨迹数据,并且对数据进行处理,得到节点在8:00—18:00时间段的位置坐标轨迹数据。然后,映射节点的轨迹数据到对应的目标子区,并对覆盖子区进行统计。图3是8:00—9:00的全部节点在目标区域的映射图。

图3 8:00—9:00时间段的出租车轨迹

处理10 d的全部周期的移动轨迹数据,求得每个节点在每个周期每个子区的平均出现次数,即泊松密度λu,i,e,并根据式(3)和式(4)计算每个节点在每个周期的每个子区的概率。此处得到的概率即为移动节点的移动预测概率。

经过上述计算,对于每个周期都得到一个对应的元胞概率数据。因此,10个周期共可得到10个元胞数据,分别对应感知周期的10个子周期的轨迹概率情况;利用式(5)和式(6)计算每个节点在整个感知周期对应的轨迹概率矩阵Zallturn。

利用上述处理得到的元胞矩阵,根据式(7)和式(8)计算有效性Utility,对本文提出的节点选择算法进行仿真。本文的移动节点选择算法选择的节点,在全部感知周期都参与感知活动。即一旦节点被选择,其就参加全部的感知周期。仿真得到的最终节点集合为Tu1={14,335,363,345,99,205,48,260,347,291,340},集合中的数据代表被选择节点的id值。即这11个节点被选择在8:00—18:00的周期进行感知,且要求在每个子周期,每个节点必须要进行感知活动,其得到的最终覆盖率为75%。本算法选择的最终覆盖情况如图4所示。

图4 本文算法覆盖情况

在图4中,不同的颜色表示不同id的节点在各子区域内的覆盖情况。同种颜色的子区域被相同节点覆盖,但是如果有两个或多个节点都覆盖同一子区,就显示为颜色深的节点颜色。

为了评价节点选择算法的有效性,本文利用其他算法对移动节点进行选择,并对比计算结果。

算法1移动节点部分周期参与感知选择算法,被选择节点只在部分周期参与感知。

仿真得到的最终节点集合为Tu2={287,71,254,287,79,48,340,308,132,22},集合中的数据代表选择的节点id值。与本文提出的算法不同的是该集合中的节点只在固定的周期进行感知。即id=287的节点在8:00—9:00的时间段进行感知,id=71的节点在9:00—10:00的时间段进行感知,以此类推。在一整天的感知结束之后,得到的最终覆盖率为65%。算法1选择的id=287的节点在8:00—9:00时间段的目标区域覆盖情况如图5所示。

图5 算法1中id=287节点在8:00—9:00目标区域覆盖情况

算法2随机选择算法,被选择的节点在整个周期都进行感知。

仿真得到的最终节点集合为Tu3={135,256,175,182,132,170,17,291,348,180,299},集合中的数据代表被选择节点的id值。在选择过程中得到的最大覆盖率为57.5%。算法2的覆盖情况如图6所示。

图6 算法2覆盖情况

与图4相同,图6中不同的颜色表示不同id的节点在各子区域内的覆盖情况。同种颜色的子区域被相同节点覆盖,但是如果有两个或多个节点都覆盖同一子区,就显示为颜色深的节点颜色。

为了使得实验结果更可靠,本文继续处理数据集中的数据,将剩余数据分为5 d的周期和13 d的周期对本文算法及对比算法进行了进一步的测试,得到的5 d周期的本文算法、算法1及算法2的最大覆盖率分别是75.0%、65.0%及57.5%;13 d周期的本文算法、算法1及算法2的最大覆盖率分别是77.5%、70.0%及40.0%。3种算法分别在3种处理周期得到的覆盖率求平均值如表1所示。

表1 3种算法的平均覆盖率 %

根据表1的数据绘制性能曲线如图7所示。由图7可以看出,本文算法由于被选择的节点在整个周期都进行感知,比算法1能获得更高的覆盖率,而算法2是覆盖率最低的算法。

图7 3种算法覆盖率曲线图

5 结束语

本文针对节点位置的关联性问题,提出一种移动互联网时空关注的移动感知节点选择算法,并将其应用于碳检测领域。该算法根据检测节点的历史移动轨迹,预测其未来在该周期内的移动轨迹,并依据移动检测节点轨迹关联有效性选择最优的参与者集合。仿真结果证明,本文算法能使用较小数量的感知节点达到较大的覆盖率。下一步,将本文算法应用于实际碳检测领域,验证其有效性。