移动群智感知中基于节点竞争的数据转发算法

王巧莉，张振宇,，吴晓红

（1.新疆大学信息科学与工程学院，乌鲁木齐830046；2.新疆大学软件学院，乌鲁木齐830008）

群智感知；剩余能量比；节点活跃度；关系强度；数据转发

0 引言

随着大规模感知和数据传输技术的进步，我们已经进入了物联网时代。越来越多的用户设备嵌入了各种各样的传感器，诸如重力传感器、温度计、加速度传感器等，这些传感器可以对人类活动及周围环境进行全方位的感知。群智感知在云端聚合每个用户设备感知到的信息（如环境上下文噪声等级、交通状况等）进行进一步的感知和群体智能的挖掘[1]。

群智感知是以人为中心的网络，持有感知设备的用户具有移动性，这使群智感知网络和传统的传感器网络有很大的不同，表现为部署更加灵活，成本更低廉等；另外人的移动性也提供了更多的机会进行感知覆盖和数据传输。在传输感知数据时，有时并不具备连接蜂窝网络或者互联网的方式进行[2]。感知应用往往会产生大量的数据，会使用户产生大量的流量费用，消耗过多的电量，导致成本过高，并且给蜂窝网络带来了很大的压力。当移动设备密度大，接触频繁，为传输带来更多的机会时，可以使用“存储-携带-转发”的工作模式进行感知数据的传输[3]。目前的移动设备利用短距离通信技术进行数据的传输，直到遇到有充足的电量流量并能够把数据上传至数据中心的终端设备。

1 相关工作

在现有的机会传输方式中，最具代表性的是Epi⁃demic[4]算法，算法采用的是洪泛策略，每个节点都把接收到的消息转发给自己的邻居节点，直至传至目的节点。该方法虽然能得到较高的传输成功率，但是会耗费大量的网络资源。Prophet[5]采用的是概率策略，出于对现实中人的移动行为具有重复性的考虑，根据历史相遇信息计算节点间的传输概率。Spray and Wait[6]也是基于泛洪策略的算法，但在节点相遇时对产生的副本个数进行不同程度的限制，在Spray阶段，向网络中注入限定数量的副本，在Wait阶段，持有这些副本的节点直至遇到目的节点后才进行数据的交付。

以上路由算法都是从持有消息的节点出发，力求找到最优的中继节点转发数据直至到达目的节点，但是并未充分调动所有节点参与数据转发的积极性。本文针对移动群智感知网络场景，提出一种基于节点竞争的转发算法，该算法通过设计竞争服务策略，通过对节点的剩余能量、节点活跃度、节点关系强度、历史转发次数等影响因子的综合考量，得到最优的转发节点，同时给予竞争成功的节点相应的报酬，从而充分调动通信范围内节点进行数据转发的积极性，使更多的节点能够参与到数据转发的过程中，加速数据的转发。

2 基于节点竞争的转发算法

2.1 网络模型

在移动群智感知网络中，持有感知传输设备的人组成了其中的移动节点，在城市中移动节点的密度较大，节点之间会产生更多的相遇机会，可以充分利用这些节点之间的相遇机会进行数据的转发。节点之间采用“存储-携带-转发”的工作模式，利用设备具有的短距离无线通信技术进行数据的交互。持有待转发数据包的节点设定好竞争条件，在通信范围内的节点感知到此信息后参与到竞争转发数据的过程中，循环此过程直至到达目标节点。

图1 节点竞争转发模型

2.2 节点竞争力评价指标

（1）剩余能量比[7]：当我们对中继节点进行选择时，应该首先考虑该节点的能量情况，通过节点剩余能量比来对节点的状态进行判定，节点N在任意时刻t的剩余能量比表示为En（t），Emax为节点能够达到的最大能量，Ecur为节点当前的剩余能量，其公式如（1）所示：

（2）节点活跃度[8]：首先本文将有限时间序列T划分为以τ为时间间隔的p个时间间隔，那么第m个时间间隔为τm（m＜p），若将在时间间隔τ内与节点i相遇的节点设为集合Si={v1,v2,v3…vn}，则第m-1个时间间隔内节点i的相遇节点集合为Si(τm-1)，相应的在第m个时间间隔内节点i与其他节点相遇的集合为Si(τm)，因此我们将节点i在时间间隔为τm中的活跃度定义如下，其公式如（2）所示：

（3）节点关系强度：可以根据节点间的历史相遇次数来对节点间的社会关系进行衡量，在时间间隔τm内，节点 Ni与节点 Nj之间的关系强度 F（i，j（）τm）可以根据公式（3）进行计算：

其中，E（i，j）（τm）表示节点 i与节点 j在时间间隔τm中的相遇次数，N（iτm）则表示在相同时间间隔内，节点i与所有邻居节点的相遇总次数。

（4）历史转发次数：节点参与消息成功转发过程的次数一定程度上体现了节点的数据转发积极性和有效性，将节点i最近时间范围内的成功转发次数设为Ci，此后根据节点的转发情况对该值进行调整。

2.3 CBOF算法设计

网络中的节点参与数据转发的过程，或多或少都会耗费自己的资源来进行消息的转发，从社会价值的角度分析，参与的节点都期望能够获得相应的利益，而不是无偿的自愿转发，考虑到这样的情形，本文的研究中基于参与转发的节点一定的资金收益，通过节点间竞争转发获得收益来有效调动节点转发数据的积极性。因此，将竞争转发信息CFM（Competition Forward⁃ing Messages）定义为如公式（4）所示的四元组：

其中的Dnode-ID转发消息的目的节点，为其他节点发布当前的竞争转发信息，Forwarding Messages为当前待转发的消息，Time Strap为竞争时间窗，发布竞争消息后在该时间段内接收竞争节点的信息，Reward为消息成功转发至目的节点后，参与转发过程的节点所获得的相应报酬。

首先假设此当前节点i需要将数据转发至目的节点D。当节点i与j相遇时，需要对节点j的消息转发能力 FA（Forwarding Ability）进行评价，如公式（5）所示计算：

节点j的整体效用值计算需要综合考虑当前节点剩余能量比和消息转发能力，计算过程如公式（6）所示：

基于节点竞争转发的算法基本步骤如下：

假设目前有节点i需要转发消息至目的节点D，那么节点i首先要向网络中发布竞争转发信息CFM（Competition Forwarding Messages），等待其他节点对该信息进行反馈，返回其竞争参与意愿，这里假设若目的节点感知到该信息，则不需要进行任何计算，直接返回目的节点确认消息即可，但其他参与竞争转发消息过程的节点则应根据公式（6）计算自身整体的效用值，并返回给竞争信息发布节点。

（1）若感知到该信息的节点中包含目的节点，则目的节点直接返回确认连接进行数据的交付，不需要对自身的效用值进行计算，交付成功后当前节点删除消息；

（2）若感知到该信息的节点中不包含目的节点，则应根据竞争转发消息的节点反馈的效用值和历史转发次数选择出最优的竞争节点，进行数据的交付。当效用值最高的节点与其中一个节点相差的值小于给定的阈值ε时，则比对效用值最大的节点与该节点效用值之间的所有节点的历史转发次数，选出历史转发次数最高的节点，则该节点竞争成功，继续消息的转发过程，直至遇到目的节点。

3 实验仿真

3.1 仿真参数与环境设置

本文通过ONE软件[9]对CBOF算法进行仿真，仿真实验中将节点的移动区域设置为5500m×4500m内，模拟校园中行人真实行走场景，在该场景内的每个行人的移动速度控制在0.5m/s-1.5m/s之间，具体参数设置如表1所示。

表1 参数设置

3.2 仿真结果与性能分析

算法的仿真结果评价指标为交付率、传输延迟、路由开销[10]。

（1）节点数量相同

图2 交付率随节点数量变化图

从图2可以看出，当节点数量比较多的情况下，CBOF算法展现出了更优的性能，这是由于随着节点数量增大，使节点之间相遇的次数大大增加，使更多的节点参与竞争转发的过程，从而选出最优的节点转发数据，并增大了与目的节点相遇的概率，获得较高的交付率。Spray and Wait算法和Prophets算法则相对稳定，并没有随节点数量变化发生明显的波动。而Epidemic算法由于节点的增多导致副本数量增多，而在节点缓存一定的情况下，消息可能会出现溢出或者丢弃等现象导致交付率反而出现下降的趋势。

图3 传输延迟随节点数量变化图

如图3所示，随着节点数量的增多，四种算法的传输延迟均呈现下降趋势，CBOF在节点数量增加到一定数量时延迟减小的程度较明显，而Epidemic算法由于节点自身的缓存有限，并不能达到最优的延迟性能，Prophet算法需要进行传输概率的计算，因此延迟高于其他算法。

图4 路由开销随节点数量变化图

从图4可得节点数量的增多对Epidemic算法的路由开销影响最大，因为算法中产生的副本数量最多，典型的以空间换时间的方法来提升性能，但节点的缓存往往很有限，有时适得其反。Prophet算法的路由开销也有比较明显的上升趋势，而CBOF算法和Spray and Wait算法展现较为稳定的性能，延迟均较低。

（2）缓存空间相同

图5 交付率随缓存大小变化图

从图5所呈现的结果来看，节点缓存的增加有利于提高消息的交付率，四种算法的交付率均出现明显增加的情况，CBOF算法考虑了节点的剩余能量情况，提高节点参与转发的积极性，充分利用缓存，因此得到了较好的性能，而Epidemic算法的交付率随缓存的增加虽有上升的趋势，但仍然无法与副本增长的速度所匹配。

如图6所示，消息的传输延迟随缓存增大而出现增加的趋势，但是CBOF算法考虑节点能量情况以及节点活跃度等因素，充分利用了节点的缓存，并未出现较大的增加现象，而Epidemic算法因为洪泛策略产生的负面影响，传输延迟仍然较大。

图6 传输延迟随缓存大小变化图

图7 路由开销随缓存大小变化图

根据图7可以观察到随着节点缓存的增大，各算法的路由开销均出现明显下降趋势，但Epidemic算法因此为自身特性仍然具有最大的路由开销，CBOF算法则因为考虑了节点与新节点接触的可能性，选择社交关系较强的节点进行消息的转发，使路由开销较小。

（3）运行时间相同

图8 交付率随运行时间变化图

图8说明了随运行时间的增长，交付率呈现出下降的趋势，这是节点的缓存随时间的增长而减小，使部分消息得不到有效转发，造成消息整体的交付率下降，而CBOF算法在运行一段时间后仍然能保持较高的交付率，是因为均衡了网络的能量利用及更多节点参与转发对缓存状况的缓解。

如图9所示，CBOF所选择的中继节点能够影响更多的新节点，从而增大与目的节点的传输概率，因而具有较低的传输延迟，在运行的初期，四种算法均出现了传输延迟快速下降的情况，但在运行的后期逐渐趋于稳定。

图10说明了随着运行时间的增长，CBOF算法的路由开销较小且趋于稳定，Epidemic因为副本数量的剧增保持着最大的路由开销，Prophet算法通过寻优转发节点一定程度降低了路由开销，Spray and Wait算法只是在第一阶段产生一定数量的副本，所以路由开销并不大。

图9 传输延迟随运行时间变化图

4 结语

本文针对群智感知中的数据转发问题，提出一种基于节点竞争的转发算法。通过对参与数据转发的节点提供收益补偿，调动节点参与竞争转发的积极性，达到促进数据转发的目的。根据节点的剩余能量、节点活跃度、节点关系强度、历史转发次数等属性对参与竞争节点进行评价，将转发能力强的节点作为中继节点进行下一步的转发。仿真结果表明，与Epidemic、Prophet及SW等算法相比，在保证较低网络开销的基础上，能够充分利用节点的转发能力，从而提高数据交付率和减少延迟。

图10 路由开销随运行时间变化图