一种低延迟可靠数据收集算法在带状无线传感网的应用

2020-06-18

矿山机械 2020年6期

大同煤炭职业技术学院山西大同 037000

无线传感器网 WSN (Wireless Sensor Network) 所研究的数据收集是其最基本的问题[1]。对于应用在管道输送、峡谷、野外长城及长距离桥梁的无线传感器网络，其共同的特点表现为长距离的带状结构[2-4]，从两侧聚集到汇聚点 Sink 的数据流，在其附近容易形成严重的热点区，会形成不均衡的能量消耗[5]。传统意义上的 WSN 静态数据收集有较大局限性，然而，采用移动 Sink 数据收集能够在一定程度上缓解热点问题，但因其移动速度不快 (0.4～ 2.5 m/s)，因此，数据收集延迟 6～21 min[6]，无法满足性能的需求。如何在有效延迟内使感知数据传输到 Sink，经典方法是定位数据节点的同时建立通往 Sink 的路径，比如，在网络内部建立广播自身位置的机制，但该方法影响其网络生命期。Y.Yue 等人[7]提出的一种移动 Sink 数据收集协议是基于代理节点的，代理节点保存其位置信息，且随其位置变化而实时更新，而源节点通过代理节点就可获得 Sink 的位置信息。B.V.Cherkassky 等人[8]提出的基于访问与代理节点的协议，访问节点可直接与 Sink 进行通信，代理节点经访问节点传输至 Sink，协议生成代理节点的方式使其能耗较大。R.Rahmatizadeh 等人[9]提出基于 WSN 节能混合路由的方式，通过降低平均跳数与控制消息，使控制消息的开销减少，从而增强网络的寿命。E.B.Hamida 等人[10]提出的 E-TAG 增强跟踪算法与 TAG跟踪算法，使定位 Sink 需要的消息转发跳数得到了降低。M.Frenkel-morgenstern 等人[11]提出的基于查询LBDD 移动 Sink 数据收集方法，通过其给线节点发送查询请求，接收到含有位置信息的查询请求，从而获得最新的节点位置信息，不足之处是线节点变成了热点区域，使网络生命期降低。T.Kato 等人[12]提出的E-TRAIL 协议是基于构建数据传输树产生的，Sink给指定区域里的节点广播其位置信息，其离开传输树后，把其位置信息广播给两跳节点，使源节点到 Sink一直拥有路由路径。以上方法无法满足带状传感器网的应用场景，存在可靠性不足及高延迟的问题。

移动 Sink 带状传感器网的方法是专门针对其延迟性能要求提出的，提出的 DCFAN 数据收集算法是基于同步代理节点转发 Sink，其贡献主要是：根据带状传感网的特点，创建移动 Sink 同步代理节点，进而创建线节点序列以便存储代理节点，然后通过代理节点转发数据至 Sink 节点，代理节点中断输送恢复机制及线节点更新机制使数据传输可靠性得到了保证。

1 网络模型

在带状区域内部节点随机分布，两端分别用 L、R 表示。通信模型与节点感知采用布尔模型[13]，通信与感知半径分别用RT、RG表示。Sink 在 L 侧，在区域内向 R 侧移动收集数据，然后返回初始位置。在L、R 的中心点布置能量较足的节点NL、NR。假设每个节点位置已知，则存储空间与 Sink 的能量没有限制。

2 DCFAN 算法

2.1 线节点

2.1.1 线节点序列构建

同步代理节点的位置信息由线节点来存储。网络模型图如图 1 所示。算法始于节点NL，至NR结束，采用贪心算法确定下一节点，则节点

图1 网络模型图Fig.1 Network model

Nj=argmin∑Nk∈Neighbor (Ni) dist (Nk，NR)，(1)最终形成有序序列L=(LNL，LN1，…，LNR)。若L是连续性的，且其中节点符合带状约束与能量约束条件，则L被称做线节点序列。

(1) 连续性约束假设非空节点集N＝(N0，N1，N2，…，Nk) 中，存在唯一始节点N0与唯一尾节点Nk，任意节点Ni的前驱节点Ni-1与后继节点Ni+1都是唯一的，则N是连续性节点序列。当前驱与后继节点满足

就称为邻居节点；若Ni，Nj同时符合

则称Nj是Ni的后继节点，Ni是Nj的前驱节点。依此创建的序列叫做连续节点序列。

(2) 能量约束序列L=(LNL，LN1，…，LNR)中，任一线节点需符合的能量约束条件。若某个线节点不满足此条件，会使线节点的更新机制触发，从而使数据传输可靠性得到保证。

(3) 带状约束为使带形区域轴两侧的边缘节点不被选做线节点，从而减弱算法性能，增大存储代理节点的能量开销与时间，故而线节点序列L中，任意线节点至中心轴的距离，不大于d。

式中：(xi，yi) 为节点LNi位置的坐标；Ax＋By＋C＝0为带形区域内中心轴方程，由已知的两点坐标进行确定。

2.1.2 线节点更新机制

线节点因为汇聚点的移动而不断对其存储的同步代理节点信息进行更新，因数据节点发送位置请求消息，使线节点消耗的能量不均衡，局部节点能量会消耗殆尽，从而使线节点序列无法满足连续性约束条件，致使数据传输的可靠性不高。鉴于此，应对能量较低的线节点进行及时更新，更新过程包含消息通知和候补线节点查找 2 个步骤。

(1) 查找候补线节点当线节点LNi不符合式 (4)的条件时，则其邻居节点LNk被选取为新的线节点，且要求LNk同时是LNi-1、LNi与LNi+1的邻居节点，即LNk是LNi-1、LNi与LNi+1通信覆盖区域内具有最大能量的节点，并符合

节点LNi的通信范围用Si来表征。若LNk同时符合带状约束与能量约束的条件，则LNk替换LNi，因此新序列依然是线节点序列。如果没有节点LNk符合此条件，就按最短路径算法[14-16]，起点为LNk-1，查找能替换节点LNi的节点序列，假设此序列中的所有节点都符合带状约束与能量约束条件，则新序列L＝(LNL，LN1，…，Ni-1，Nk1，Nk2，Nkm，Ni+1，…，NR) 即是线节点序列。

(2) 消息通知当LNk或Nk1、Nk2、Nkm接收到节点LNi发送的角色变更消息后，则向其邻居节点发送LN_Notice 的通知消息，以保证所有节点对其邻居节点的线节点信息进行了存储。最后，当邻居节点接收到LNi发送的线节点取消消息后，删除邻居表里的LNi节点信息，以完成更新线节点。

2.2 构造代理节点

2.2.1 构造代理节点的原则

需要定义数据跟随机制以达到 Sink 移动时对数据收集的低延时性能要求。

假设非空节点集N＝(N0，N1，N2，…，Nk)，除了首尾 2 节点之外，余下所有节点Ni都对前驱与后继节点地址进行了存储，因而序列中任意节点可发送到端节点。

代理节点由 Sink 在移动过程中产生，直接进行通信的是直接代理节点，不能直接通信的叫做间接代理节点。如果 Sink 移动到同步代理节点通信范围外，就会导致数据传输中断。为了数据传输的可靠性，Sink 在离开同步代理节点通信范围，产生新的同步代理节点前，需满足条件

代理节点更新频率用参数ε控制，其更新速度随参数值变小而变慢，对数据传输的可靠性影响较大；相反，更新速度过快，会频繁发送控制消息从而使节点能耗增大。为了更新频率与降低通信开销，且满足能量约束条件，代理节点ANi+1应是到 Sink 距离最近的ANi的邻居节点。

Sink 与代理节点ANi的通信覆盖范围用 Sink 与Si来表示。Sink 节点的位置信息与剩余能量在代理节点序列生成的过程中完成收集。Sink 生成代理节点序列的过程如图 2 所示，后继代理节点位置信息存储下来，奠定了通过代理节点跟随机制将数据转发至 Sink的基础。

2.2.2 更新同步代理节点

如果同步代理节点的邻居节点含有线节点类型的节点，则位置消息就直接发送至此线节点。否则，因地理路由算法简单、方便实现、存储空间与计算开销低的优势，源节点至 Sink 数据转发的基础路由可由该算法表征[17-20]。代理节点通过此算法把位置消息发送至邻居节点里距目标点P(xi，yi) 最近的节点。循环此步骤，直至邻居节点是线节点的Nx节点收到此位置消息。然后发送至其邻居线节点，用LNi表示此线节点。节点ANi+1(xANi+1，yANi+1) 至带状区ζ轴线的垂足为此目标点。假设后继与前序节点位置信息已被线节点序列中所有节点存储，使用跟随机制将获得代理节点位置信息的线节点向后继与前序节点分别发送位置消息，直至首尾两端节点都接受此消息，则序列中的同步代理节点就完成了位置信息更新。

2.2.3 代理节点的生命期

用参数T表示代理节点生命期，若任意代理节点的生命期大于T，则此节点失效。随着T值变大，则数据传输的延迟也会随之变大，也会引发网络能量空洞；若值变小，则存储的代理节点极易失效，会造成反复请求发送位置消息，使通信能耗变大[21-22]。所以T值的选取需要综合考虑数据收集延迟与节点的能耗。

2.3 主动定位

2.3.1 请求节点位置信息

移动 Sink 收集数据如图 3 所示。当代理节点失效或者未保存代理节点时，就依据地理路由算法发送节点位置请求消息给最近的线节点，按图 3 所示的路径 1 进行传输。线节点LNi接收含转发节点序列的节点位置请求消息，依据传输路径，发送代理节点位置响应消息给节点Ni，按图 3 所示的路径 2 进行传输。全部节点在位置消息与节点位置响应消息传输过程中同时得到同步代理节点的位置信息[23]。所以，不需要发送请求，就可将节点能耗、控制消息规模、数据收集延迟降低。

图3 移动 Sink 收集数据Fig.3 Data collection by mobile Sink

2.3.2 数据传输

得到同步代理节点位置信息的节点Ni，经算法将数据发给节点ANi。若在 Sink 通信区域内，则将数据直接发给 Sink；若其离开通信区域，则通过跟随机制将数据传至 Sink：Ni→…→ANi→ANi+1→…→Sink，按图 3 所示的路径 3 进行传输；若代理节点的生命期T过大，会导致代理节点传输中断，即后续代理节点能量耗尽，致使数据传输失败。为解决该难题，节点ANk-1得到同步代理节点位置后，则数据传输重启，进而传至 Sink。

2.4 算法局限性

DCFAN 算法如果应用于非带状传感器网络中，会有如下局限性。

(1) DCFAN 算法沿带状区域中心轴构建线节点序列，若将此方法在非带状传感器网络中应用，会使线节点和代理节点与边缘数据节点之间的距离增大，及代理节点的存储和普通节点的能耗增加。

(2) 同步代理节点的形成会受 Sink 移动方式的改变，对算法效率造成影响。移动 Sink 在带状网络带状区内的两端进行固定往返运动，因此，同步代理节点的分布呈现规律性。而 Sink 在非带状网络的运动比较灵活，所以代理节点分布呈现不规则性，对代理节点的更新造成一定的影响，从而使算法性能降低。

3 时间复杂度

假设带状网络节点数量用N表示，P和M分别表示代理节点与线节点的数量。将该算法分成 4 个步骤，每个步骤的时间复杂度为：

(1) 步骤 1 构造线节点序列。该阶段线节点序列只考虑了节点能量与节点位置，时间复杂度最坏情况下是 O(M)；

(2) 步骤 2 更新同步代理节点。该阶段地理路由算法将位置消息发送至邻近线节点，则序列L中的同步代理节点得到更新，时间复杂度最坏情况下是O(N)+O(M)；

(3) 步骤 3 代理节点位置信息请求。请求代理节点信息向最近的线节点，且按原路径返回同步代理节点位置信息，时间复杂度最坏情况下是 O(N)；

(4) 步骤 4 传输源节点数据至 Sink。首先将数据从源节点传输至代理节点，进而通过跟随机制转发至 Sink，时间复杂度最坏情况下是 O(N)+O(P)。

综上所述，该算法的时间复杂度最坏情况下为O(M+N+P)。

4 仿真分析

仿真平台选取软件 MATLAB 7.0，在 900 m×400 m 的带状区域里随机布置 300 个传感器节点，将不同移动 Sink 速度下 LBDD、E-TRAIL 和 DCFAN 算法的平均网络能耗、数据转发延迟性能及转发率进行比较。3 种算法的仿真中，皆用单个移动 Sink，初始能量为 250 mJ，感知半径为 10 m，通信半径为 85 m。

(1) 网络节点平均能耗不同移动 Sink 速度下平均节点能耗如图 4 所示。从图 4 可以看到，3 种算法的平均节点能耗随 Sink 移动速度的增加而变大。DCFAN 算法由于代理节点更新频率随 Sink 移动速度的增加而变大，致使增大了数据传输量，从而使节点能耗变大；而 LBDD 算法由于没有节点更新机制，当传输数据增大时，平均节点能耗更加严重；E-TRAIL算法的分簇过程消耗大量能量，其运行过程中，Sink的线路更新又受限于两跳范围，故能耗较平稳，从图 4 可以看出，E-TRAIL 算法整体平均节点能耗较大，而且变化比较平缓。

图4 不同 Sink 移动速度下平均节点能耗Fig.4 Average node energy consumption at various Sink moving speed

(2) 数据收集延迟在不同移动 Sink 速度下的数据收集延迟如图 5 所示。从图 5 可以看到，3 种算法的数据收集延迟随及 Sink 移动速度的增加而减少。另外，DCFAN 算法性能低于 LBDD 算法，原因在于 DCFAN 算法依赖代理节点将数据转发至 Sink，而 LBDD 算法是直接将数据发送给线节点。E-TRAL的数据收集延迟在 3 种算法中表现最短，原因是簇头节点以多跳的形式将数据直接传输给 Sink，但其是以牺牲网络节点能量来得到优异的数据收集延迟性能。

图5 不同 Sink 移动速度下数据收集延迟Fig.5 Data collection delayat various Sink moving speed

(3) 数据收集率 Sink 节点的数据量和源节点采集的数据量的比称为数据收集率。不同移动 Sink 速度下数据收集率如图 6 所示。从图 6 可以看到，3 种算法的数据收集率随 Sink 移动速度的增加而降低。折线图中 DCFAN 算法的数据收集率在 3 种算法表现最好，原因在于在通信区域内 Sink 收集的节点将数据发给代理节点，然后通过跟随机制传给 Sink，中断处理机制则确保在传输失败后数据传输的可靠性；随网络运行，LBDD 算法在传输大块数据时，会使局部节点的能量消耗殆尽，从而使数据传输可靠性降低；而 E-TRAIL 算法簇头周边节点随其周期性更新，致使负担越来越重，导致节点失效，从而使 Sink 数据收集率降低。