王国玲，杨文忠，张振宇，夏扬波，殷亚博，杨慧婷

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

0 引言

移动无线传感器网络是一种以数据为中心的延迟容忍无线网络[1]，节点由电池提供能量，并且当节点的能量耗尽时给节点充电或更换电池极其困难，其次节点的通信距离有限并且由于节点的移动，节点间的链路连接动态变化[2-3]。在移动无线传感器网络中，设计有效的数据传输策略成为一个研究热点，并且随着人们对移动无线传感器网络的深入研究，使其广泛应用于野生动物监测[4]、移动智能照明控制[5]等。

为了解决移动无线传感器网络的数据传输问题，学者们从不同的角度提出了相应的算法。当考虑节点属性时，文献[6]提出一种具有能量感知且负载均衡的路由算法，根据节点的剩余能量特征选出下一跳节点并进行数据消息的传输。文献[7]提出一种路由算法，考虑节点的位置坐标和剩余能量，最终实现数据消息的传输。文献[8]提出一种路由协议EAEpidemic (Energy Aware Epidemic)，两个节点相遇时彼此交换一个消息，包含节点缓存里的数据消息、能量水平和剩余缓存空间大小，选择剩余能量和剩余缓存大小大于自己的邻居节点，并向该邻居节点复制对方没有的数据消息。文献[9]提出一种基于能耗自选演进机制的延迟容忍网络路由算法，依据节点的剩余能量状态，利用策略博弈模型确定节点是否转发数据消息。文献[10]提出一种路由算法LDM(a new routing algorithm based Location and Direction of Motion)，基于随机运动模型，考虑节点的运动方向与当前位置分三种情况计算节点的传输概率。可以看出上述文献提出的路由算法仅考虑节点的剩余能量、节点的剩余缓存和节点的运动方向，在现实生活中很多数据消息都有延迟要求，并且很多数据消息都是大小不一的，为此仅考虑节点属性设计路由算法，缺乏一定的实用性。

当考虑数据消息属性时，文献[11]提出一个自适应的多步路由协议，选择距离sink节点最近的相遇节点作为转发节点，并且每一步路由都根据数据消息的延迟容忍度计算数据消息的副本数，以便用最少的副本数达到期望的传输概率。文献[12]提出一种路由协议FLDEAR(Fuzzy-Logic based Distance and Energy Aware Routing protocol)，根据数据消息的大小、节点与sink节点的距离以及节点与sink的历史访问频率计算节点的传输概率，从而选择传输概率最大的邻居节点转发数据消息。为了提高数据消息的投递率，文献[13-14]根据数据消息的延迟容忍度对节点队列里的数据消息排序，使得延迟容忍度低的数据消息可以优先转发；可以看出没有考虑节点的剩余能量属性，这样会导致网络中节点的能量消耗不均匀，部分节点过早死亡，从而缩短网络的生命周期。

为了弥补上述的不足，本文提出一种基于虚拟货币的路由策略，在选择下一跳的时候既考虑节点的属性又考虑数据消息的属性，使得提出的路由策略更加合乎现实要求，而且能均衡网络中节点的能量消耗，延长网络的生命周期。需要发送数据消息的一方为买方，接收方为卖方，当买方和卖方相遇时，根据节点的剩余能量和剩余缓存大小以及数据消息的延迟容忍度和数据消息的大小计算出价和要价，当出价大于或等于要价时议价成功，买方向卖方发送数据消息并更新各自的财富值。

1 网络模型和问题描述

1.1 网络模型

本文研究的是同构传感器网络，整个网络的构成包括一个位置固定在正方形监测区域中心的sink节点和分布在该区域内做随机运动的普通传感器节点，如图1所示。普通传感器节点拥有相同的存储空间、相同的通信半径R、相同的初始能量、相同的初始财富值M。

图1 节点的分布

这里的财富值是借鉴经济学里的概念，财富值的大小表示节点的可用资源情况。节点的可用资源指节点的剩余能量和节点的剩余缓存空间。

定义1 移动模型。采用随机移动模型Random Waypoint，运动的节点通过GPS或其他定位方法知道此次运动起点的位置，并且随机确定此次运动的目的地，朝着目的地以某个位于[vmin,vmax]的速度做匀速直线运动，到达目的地后随机停留一段时间，然后以此次的目的地作为下一次的运动的起点。如图2所示。

图2 节点的运动模型

定义2 议价模型。两个节点相遇时，需要转发或发送数据消息的一方视为买方，接收数据消息的一方视为卖方。买方和卖方都是根据数据的延迟容忍度、数据大小、自己的剩余能量和缓存空间利用率进行定价，当出价大于或等于要价时交易成功，即可进行消息的复制并转发；否则交易失败，节点继续运动，等待跟其他节点的相遇。

定义3 数据消息的延迟容忍度。每个传感器都装有一个计时器，当采集到某个数据并形成数据消息时开始倒计时，如果在数据消息被成功传输到sink节点之前延迟容忍度Tj减为0，则该数据消息失效。为简明起见，数据消息从买方被复制到卖方所花的时间忽略不计。

定义4 缓存空间利用率。缓存空间利用率Sj表示节点j中已占用的空间与初始缓存空间的比值，缓存空间利用率越高，表示剩余缓存空间就越小。sink节点的缓存空间不受限，普通传感器节点的缓存空间都受限，一旦剩余缓存空间为0，则再来数据消息时将与节点缓存队列里延迟容忍度最大的数据消息比较，并决定是否替换。

1.2 问题描述

针对移动无线传感器网络中节点做随机运动的路由问题，前人作了相应的研究，提出了相关的路由算法。可以看出大多都是基于相遇节点的传输概率进行数据消息的复制转发；而且节点在计算传输概率时考虑的因素不全，没有综合考虑节点的属性和数据消息的属性；此外节点在进行随机运动时，其运动速度和运动方向都是随机的，过分依靠节点的传输概率进行数据消息的复制转发意义不是很大，反而会浪费节点宝贵的能量资源和计算资源，甚至会错过最佳的数据消息转发机会。因此有效的数据消息路由算法应该具备以下几个特点：1)下一跳节点的选择应该综合考虑节点的剩余能量、缓存空间大小等节点属性以及数据消息大小、延迟容忍度等数据消息的属性；2)删除无效数据消息，避免无效消息带来的资源浪费，甚至影响有效数据消息的转发和传输；3)均衡整个网络中节点的能量消耗，避免部分节点能量消耗过大，从而延长网络的生命周期。

1.3 能量模型

采用简单无线通信能耗模型[15]。由于通信模块的能量消耗最大[16]，简单起见，只考虑节点在发送数据消息和接收数据时的能量消耗，忽略其他方面带来的能量消耗。节点在发送数据消息时的能量消耗与距离d和数据长度L有关，当d小于距离阈值d0时采用自由空间模型，当d大于距离阈值d0时采用多径衰减模型。

图3 能耗模型

如果节点发送Lb的数据，传输距离为d时，所消耗的能量满足以下公式：

(1)

其中：Eelec为发送的能耗，εfs和εmp是功率放大这部分能耗的系数。

如果节点接收Lb的数据包，那么能量消耗如下：

ERX(l)=lEelec

(2)

本文假设节点的通信半径R小于d0，两个节点相遇时，节点发送长度为Lb的数据消息时能量消耗为：

ERX(l)=lEelec+lεfsd2

(3)

节点发送和接收长度为Lb的数据消息时总能量消耗为：

E(l)=2lEelec+lεfsd2

(4)

2 数据传输机制——DTVC

为了解决节点基于随机运动模型的路由问题，本文提出了一种基于虚拟货币的低能耗数据传输机制——DTVC(Data Transmission based on Virtual Currency)。数据消息字段如图4所示，Nop表示协议信息，Seq表示数据消息的ID，SID表示源节点ID，JID表示目的节点的ID，L表示数据消息的长度，RSD表示数据消息的延迟容忍度。基本思想描述如下：携带数据消息的节点在随机运动的过程中若与其他节点相遇，先向对方发送一个包含需要转发或传输的数据消息的ID、数据消息的目的节点的ID、数据消息的大小、发送节点的剩余能量以及数据消息的延迟容忍度的hello包；收到hello包后先查看数据消息的ID和目的节点的ID，若接收节点缓存里没有该数据消息，则回复一个包含接收节点的ID、接收节点的剩余能量和该数据消息的ID的ACK确认信息；发送节点查看ACK确认信息后，若接收节点是数据消息的目的节点，则直接发送数据消息，否则根据定价规则进行出价，接收节点根据定价规则进行要价，如果成交则把数据消息发送给接收节点并更新财富值，否则继续运动等待与其他节点相遇。

图4 数据消息的构成

Fig. 4 Composition of data messages

2.1 买方和卖方的定价规则

两个节点相遇后，根据规定的定价机制进行定价，如果买方的出价大于或等于卖方的要价即c≥b，则交易成功。设买方的出价为c，卖方的要价为b，对应如下：

(5)

其中:α、β和γ为节点的剩余缓存空间、数据的延迟容忍度和节点剩余能量对应的权重，且α+β+γ=1，L是数据消息的长度，Tm指当前数据消息m的延迟容忍度，Tinit指数据消息产生时的延迟容忍度，Sj指节点j的空间利用率，Ej_res指节点j的剩余能量，Einit指节点j的初始能量。

(6)

其中:Tinit、Tm和Einit的含义跟上式相同，Sk指节点k的空间利用率，Ek_res指节点k的剩余能量，ω、η和θ是对应的权重，且ω+η+θ=1。买方和卖方按规定的定价机制进行定价，从而决定此次交易是否成功。

2.2 权重的设置

由式(5)可知α、β、γ为节点缓存空间、数据消息延迟容忍度和节点剩余能量对应的权值。矩阵A里的aij表示要素i较要素j的重要程度，所以矩阵的对角线上都取值为1，并且aij=1/aji。对买方来说，希望把延迟容忍度小的数据消息传输出去，并且剩余缓存空间越小以及剩余能量越小越急切把消息传输出去，所以缓存空间较延迟容忍度重要性小一些，较剩余能量重要性也小一些，延迟容忍度较剩余能量重要性小一些。A里的第一行取值为1，1/3和1/5，第二行取值为3,1，1/7，判断矩阵A的全部取值如下：

由式(6)可知ω、η、θ为节点缓存空间、数据消息延迟容忍度和节点剩余能量对应的权值。矩阵B里的每个值的含义与A类似，对卖方来说，当节点的剩余能量很小以及缓存空间小时就不愿意接收消息，所以缓存空间较延迟容忍度重要性大一些，较剩余能量重要性也小一些，延迟容忍度较剩余能量重要性小一些。B里的第一行取值为1、5和1/7，第二行取值为7、1、1/3，判断矩阵B的全部取值如下：

2.3 数据消息的转发

采用动态多副本进行数据消息的转发，具体的转发过程描述如下：

步骤1 准备阶段。节点j携带数据消息s和节点k相遇，首先节点j向节点k发送一个hello包，之后收到来自节点k的确认信息ACK，若节点k的缓存里没有数据消息s并且是数据s的目的节点，节点j直接发送数据消息s，转步骤5；否则节点j根据式(5)计算出价c，转步骤2。

步骤2 服务请求。节点j向节点k发出包含数据消息s的ID、长度l和出价c的服务请求。

步骤3 服务应答。节点k对该请求消息进行查看，如果缓存里的数据消息的ID跟数据消息s的ID都不同，则节点k根据(6)计算要价b，并把b和c进行比较，如果c≥b，给出一个包含数据消息ID以及成交价格0.5(b+c)的确认信息，表示愿意接收该数据消息，转步骤4；否则此次交易失败，节点j携带数据消息s继续运动。

步骤4 数据发送。节点j收到确认信息后，如果节点j对数据s是源节点，需要对数据s进行一次复制；否则不复制直接发送数据消息s给节点k。

步骤5 财富值更新。节点j的财富值减0.5(b+c)，节点k的财富值增加0.5(b+c)。

假设当前有k′个节点进入节点j的通信范围，即有k′个节点与节点j相遇，令Σ={Ψk|1≤k′}表示k′个相遇节点的集合。数据消息传输算法如下：

输入：相遇节点;

输出：满足条件的相遇节点并判断是否需要复制。

Φ=∅

fork=1 tok′

//识别相遇节点

do ifkis sink node

forward message(d,k);

//节点j直接把s发送给k

else nodejandkcalculate the pricecandb

ifc≥bthen

Φ=Φ∪Ψk;

end if

end if

end for

if the data messagesis sensed by nodej

forn=1 to |Φ|

do copy and forward message(s,Φn);

//节点j复制并转发给满足条件的节点Φn

else forn=1 to |Φ|

forward message(s,Φn);

//节点直接转发给满足条件的节点Φn

end for

end for

end if

2.4 算法的性能分析

时间复杂度分析 对于含n个节点的传感器网络，识别邻居节点所花的时间为O(n)，之后节点进行数据消息的复制和传输所花的时间为O(1)，删除无效数据消息所花的时间也为O(1)，所以最终算法的时间复杂度为O(n)。

空间复杂度分析 网络中每个节点存储的数据消息数为O(1)个，对于规模为n的传感器网络，其空间复杂度为O(n)。

2.5 无效数据消息的处理

当sink节点收到某个经过中间节点转发的数据消息后，广播一个包含该数据消息ID的消息，网络中的其他节点查看自己缓存空间里数据消息的ID，若有某个数据消息的ID跟sink节点广播的数据消息ID相同，则直接删除，根据文献[17]可知sink节点广播消息对网络中正常数据消息传输的影响不大，为此本文忽略该影响。此外节点会定期检查自己缓存队列里的数据消息，当数据消息的延迟容忍度减为0时，作删除处理。

3 仿真实验

选取文献[12]提出的路由算法(FLDEAR)、文献[9]提出的路由算法(一种基于能耗自选演绎机制的延迟容忍网络路由算法)和FAD算法作为比较对象，选择的原因是文献[12]和文献[9]提出的路由算法分别是2018年和2017年提出来的，比较新，FAD算法是比较经典的路由算法。四种算法在默认的仿真条件下针对网络生命周期、数据消息传送成功率和每个数据消息的平均副本数这几个性能指标进行比较，并通过改变节点数从而改变节点密度以及改变节点的传输半径观察四种算法中每个数据消息平均副本数和数据消息的投递率；值得注意的是，每个数据消息的平均副本数反映了网络中节点的能量消耗情况，平均副本数越多，能耗越大。此外当节点的缓存空间已满，即缓存空间利用率为100%时，四种路由算法下节点只接收数据延迟容忍度比缓存列表中最大延迟容忍度小的数据，并替换缓存列表中延迟容忍度最大的数据消息。以下实验结果如未特别说明，均为50次实验结果的平均值。

本文依据数据消息的延迟容忍度对消息进行排队，旨在提高网络中数据消息的投递率，因为延迟容忍度越低则优先级越高，可以优先得到传输。实验部分将通过数据消息的投递率和副本数指标对算法进行验证。对于算法的时间效率，可以通过算法的时间复杂度分析得到。

3.1 实验统计量

1)网络生命周期。

本文定义网络的生命周期为从网络开始运行到有一半传感器节点能量耗尽时的时间间隔。

2)数据传送成功率。

指最后被sink节点成功接收的所有数据消息的数目与所有源节点发送的数据消息数目的比值。反映的是在数据消息的有效期内，能够成功被传输到sink节点的数据消息的情况，数据消息投递成功率越高表示网络的效率越高。对应的计算式为：Dsec=Dd/Ds，Dd表示被sink节点成功接收的数据消息的数量，Ds表示所有源节点发送的数据消息的数量。

3)数据消息的平均副本数。

指网络中所有数据消息的数目与不同的数据消息个数的比值。每个数据消息的平均副本数反映数据消息在网络中的冗余度以及网络的能量消耗情况，平均副本数越多，冗余度越大，网络中的能量消耗越多。

3.2 实验设置

使用Matlab作为仿真软件，主要仿真参数设置如表1所示。

表1 仿真实验参数

3.2.1 节点通信半径对性能的影响

传感器节点通信半径越大，与sink节点和网络中其他传感器节点相遇的可能性越大，那么数据消息的投递率也随之变大。为了验证通信半径对算法性能的影响，改变传感器节点的通信半径，并观察4种路由算法下数据消息的投递率和副本数的变化。仿真实验结果如图5所示。

图5 节点通信半径对算法性能的影响

从图5(a)可以看出随着传感器节点的通信半径逐渐增大，4种路由算法对应的消息投递率曲线都呈现上升的变化，其中本文提出的路由算法DTVC的消息投递率高于其他3个算法。这是因为随着节点通信半径的增大，网络中的节点可相遇的节点数增多，所以4种路由算法对应的消息投递率增大。本文提出的路由算法DTVC中，节点在传输数据消息的时候既考虑相遇节点的投递能力又考虑数据消息的延迟容忍度，此外通过删除网络中的无效数据消息，从而节省网络中节点的能量消耗并提高节点缓存空间的有效利用，所以网络中数据消息的投递率最高。FAD算法中，数据消息的传输类似于传染算法，之后依据消息的容错大小决定其转发优先级，但是传感器节点的存储空间有限，随着网络的运行传感器节点的缓存队列很快就会被用完，节点会删除容错最大的数据消息，当网络中节点产生数据消息的频率很高时，数据消息还来不及传输就被节点删除。文献[12]提出的路由算法只考虑传感器节点剩余能量和距离2个因素，没有考虑数据消息的属性，延迟容忍度较低的数据消息可能会因为没有及时被传输而失效。文献[9]提出的路由算法中，传感器节点根据自身的剩余能量决定是否转发接收到的数据消息，导致很多数据消息被中间转发节点直接丢弃，其次没有对节点的缓存队列进行有效地管理。

从图5(b)可以看出随着传感器节点的通信半径逐渐增大，4种路由算法对应的数据消息平均副本数曲线都呈现上升的趋势。其中路由算法DTVC的消息平均副本数低于其他3个算法。这是因为当网络中的节点可相遇的节点数增多时，满足条件的邻居节点数随着增多。本文提出的路由算法DTVC中，为了控制数据消息的副本数，规定只有源节点可以复制数据消息。而其他3个路由算法中，复制数据消息时不分源节点和中继节点，所以会使得数据消息的冗余度大于DTVC。

3.2.2 节点密度对性能的影响

本文通过改变网络中的传感器节点数目控制节点密度。不失一般性，节点密度越大，网络中任意2个节点相遇的可能性也就越大，数据消息的投递率也会随着增大；但是随着节点密度的增加，采用多副本传输时网络中数据消息的副本数也会增多，从而增加网络的负载和能量消耗。图6(a)显示了节点密度对4种算法中数据消息投递率的影响，可以看出随着节点密度的逐渐增大，4种路由算法对应的数据消息投递率都在增大，但是增加的幅度越来越小。这是因为随着节点密度的增大，数据消息可以通过源节点直接传输给sink节点和通过中继节点转发给sink节点的可能性都在增大，但是随着节点数的不断增多，增加的数据消息副本数带来的投递率就不那么明显了。从图6(b)可以看出节点密度对4种算法平均副本数的影响，可以看出消息的副本数随着节点密度的增大而增多。原因如前面所述。

4 结语

本文在前人工作的基础上，通过对移动传感器网络中基于多副本传输的路由问题作进一步研究，当节点做随机运动时提出了低能耗数据消息传输机制DTVC。按照传统思想，发送节点在转发数据消息的时候大多从邻居节点中选择传输概率比自己大的节点，本文不依赖于相遇节点的传输概率，而是根据发送节点和接收节点的属性以及数据消息的属性来决定是否进行数据消息的转发。此外为了减少网络中不必要的能量消耗，删除无效数据消息。下一步的工作是考虑网络异构时如何实现数据的有效传输路由问题。

图6 节点密度对算法性能的影响