应用于无线传感器网络的节点内存资源共享的移动Sink数据采集方法

摘要

本发明公开了一种应用于无线传感器网络的节点内存资源共享的移动Sink数据采集方法。移动Sink沿着预定轨迹以恒定速度移动。在均匀分布于网络中的RP点驻留，采集来自以RP点为树根所成的K跳生成树中节点的数据。发明中定义了缓存告急和时间告急，当节点出现缓存告急，可以通过与同一树中的邻居节点共享内存资源缓解内存压力；当树出现缓存告急，可以通过与邻居树间共享内存资源缓解内存压力。节点间的内存资源共享减少了因节点内存溢出导致的丢包。时间告急时，节点主动向移动Sink上传时间告急的数据包，使数据包不会因为传输延时超出截至时间。

说明书

技术领域

本发明属于无线传感器网络数据采集技术，具体地本发明涉及一种在K跳 生成树拓扑基础上的节点间内存资源共享，进行局部数据采集，并将其应用于无 线传感器网络的移动Sink数据采集方法。

背景技术

无线传感器网络在许多应用中都发挥重要的作用，如常规数据采集、远程恶 意位置监测、应急响应等。无线传感器网络是由部署在监测区域中的大量微型廉 价的传感器节点构成，这些节点通常都是电池供电且内存资源有限。实际应用中， 替换电池通常是不经济也是不可操作的。有限的存储空间限制了节点可存储的感 知数据的数目。因此，网络寿命和缓存溢出是无线传感器网络设计时的两个重要 的参数。

典型的无线传感器网络中，静态Sink节点位于网络中心，节点通过多跳方式 向Sink上传感知数据。节点不但要将自己的数据包发送给Sink，还要负责转发 其他节点发来的数据包。因此，靠近Sink的传感器节点由于较大的数据包转发 任务，能量消耗比距离Sink较远的节点能量消耗快得多，这就是所谓的热区问 题。热区问题导致Sink节点孤立于网络中的其他节点之外，使网络性能下降。

许多研究者提出利用移动Sink解决传感器网络中的热区问题并提高数据采 集有效性。Po-Liang Lin和Ren-Song Ko在2012年的《International Journal of  Distributed Sensor Networks》上发表文章“An Efficient Data-Gathering Scheme for  Heterogeneous Sensor Networks via Mobile Sinks”，通过TDD算法、分配算法和 路径规划，使得节点的内存溢出在给定时间内最小。基于TDD算法完成网络的 分簇，选出簇头和簇内节点(DH和DM)。节点i计算T_elk[i]，每个节点维护一 个时钟并从T_elk[i]倒计时，在时钟计时结束之前，如果没有收到来自邻居节点的 DH广播消息，则自己向周围节点广播DH包，收到该广播包的节点选择内存溢 出时间最小的簇头加入该簇，并返回一个声明自己为DM的包给簇头。为了延 长DH节点的内存溢出时间，进一步提出分配算法。通过选择出数据采样率最大 的前k个成员节点分担DH采集到的数据，延长簇的内存溢出时间。通过DMWFS 算法或者DTSP算法对移动Sink的移动路径进行规划。该算法从节点缓存溢出 的角度对引入移动Sink解决网络热点问题进行算法设计，将网络分成一跳的簇， 由移动Sink遍历所有DH进行数据采集；当移动轨迹确定时，均衡了内存溢出 时间和移动距离两个因素选择权值最小的DH作为下一目标位置。优点是，可以 有效地减少因节点缓存溢出带来的数据包的丢失；但是不适用于大规模网络，因 为遍历一跳簇头进行数据采集对于大规模网络会造成数据传输延时，从而导致数 据包溢出内存。

Xu Li等人2012年在《IEEE JOURNAL ON SELECTED AREAS IN  COMMUNICATIONS》上提出“Localized Geographic Routing to a Mobile Sink with  Guaranteed Delivery in Sensor Networks”算法，提出一种完整的定位服务路由协议 ILSR机制(Integrated Location Service and Routing)。在一个连通的网络中，Sink 以较低的速度缓慢移动进行数据收集，移动过程中始终保持与至少一个网络节点 间保持连通。通过对网络中的节点发送的HELLO包的侦听，Sink可以获知网络 中的节点的位置信息。当Sink发现某条新链路，或者发现某条即将或已经断裂 的链路(由Sink的移动造成的)，通过在网络中广播flooding type和routing type 两种类型的数据包，向网络中的部分节点发布自己新的位置信息。节点通过维护 变化缓慢的与Sink通信的下一跳节点而不是Sink的精确的位置信息的改变，有 效的减少位置更新消息在网络中的转发次数，减少了能量开销；此外，由于位置 更新消息带来的开销问题，文章通过LC机制，控制更新消息在网络中的转发范 围，有效地控制了能量的过大开销问题。缺点是，虽然HELLO包不大，但HELLO 消息的不断传播带来的能量消耗累积会随着时间变大。

Liu Danpu等人2013年在《Communications,China》上发表文章 “Energy-efficient transmission scheme for mobile data gathering in Wireless Sensor  Networks”，提出MIHOP机制，将基于分簇的虚拟MIMO和Multi-Hop两种机 制相结合，根据节点与Sink间跳数是否大于一个参照跳数值MH，确定节点与 Sink之间的不同通信模式。Sink沿着预定轨迹进行移动，在特定的点广播 BEACON消息周期性采集来自节点的数据；Sink配置两个天线，其他节点配置 一个天线进行数据上载。为了确定不同范围节点与Sink间的通信模式，在网络 形成阶段，移动Sink在每个数据采集点停留并广播一个BEACON消息，该 BEACON消息中包含MH和K。MH和K分别表示按照多跳方式与Sink通信的 节点的最优最大跳数和节点到Sink的跳数；所有节点确定与Sink的通信模式后， 采用TDMA机制，由Sink确定节点数据传输的顺序。算法的优点是根据节点与 Sink的不同跳数将网络节点分层，不同层采用不同的通信机制，可以最好的利用 现有机制对不同网络规模的适应性，将网络中各层次节点的能耗控制在较低水 平，延长了整个网络的寿命。缺点是没有考虑不同层节点能耗的平衡性，可能存 在某一层节点能耗比其它层快，导致网络分区的出现。

Kwnagcheol Shin和Soontae Kim在2012年的《The Journal of Supercomputing》 提出“Predictive routing for mobile sinks in wireless sensor networks:a  milestone-based approach”。Sink在移动过程中，根据自己移动状态确定进行位置 信息告知的类型。如果sink的移动过程不改变方向，则Sink计算给因移动而新 进入自己通信范围的节点发送位置预测信息，不做大范围的Sink位置预测更新； 如果Sink的移动过程中发生方向改变，则Sink将计算的预测位置、前一个里程 碑节点的坐标消息告诉当前的里程碑节点，收到该消息后，当前的里程碑节点会 形成一个信标消息，该消息中包含有Sink的预测位置、自己的坐标、Sink位置 消息产生的时间以及前一里程碑节点的坐标，根据所获得的前一里程碑节点坐 标，按照贪婪路由的方式，将信标消息转发给前一里程碑节点。参与转发的节点 也能根据信标消息中的信息对自己存储的sink位置、位置产生的时间、信标节 点的坐标进行更新。而且这些转发节点的邻居节点可以通过侦听的方式，来获得 Sink的最新位置信息。算法的特点是当Sink移动方向变化时，小范围更新位置 预测信息，避免大范围广播Sink位置更新消息，减少能量开销；周期性校准Sink 位置信息，提高位置估计的精度。缺点是由于部分节点需通过邻居节点间接获取 Sink位置信息，数据包传输路径会延长。

综上，目前无线传感器网络数据采集时普遍存在的问题是：

1、当移动Sink在网络中进行局部数据收集时，Sink需遍历网络中所有或部分节 点，由于移动Sink速度较低，导致数据传输延时较大；而对因为Sink低速移动 带来的数据传输延时所造成的数据包超出截止日期的情况考虑不足；

2、由于数据向Sink传输存在延时，节点需要对感知到的数据进行缓存，受传感 器节点自身硬件限制，可能存在内存溢出导致数据包丢失；

发明内容

本发明的目的是为了解决现有技术中节点内存空间有限数据采集技术存在 的不足，提出一种应用于无线传感器网络的节点内存资源共享移动Sink数据采 集方法，节点根据邻居节点间的内存使用情况，向可与之共享内存资源的邻居节 点转发将要溢出的数据包，从而减少数据包因溢出导致的丢包。

为了达到以上目的，本发明提供了一种应用于无线传感器网络的节点间内存 资源共享的移动Sink数据采集方法。包括两个阶段：准备阶段和数据采集阶段；

所述准备阶段，完成以预定RP点为树根的K跳树的构建而不进行数据采集； 所述准备阶段包括两个子部分：树的建立和孤立节点加入生成树；

所述树的建立是指，移动Sink进入网络的第一个Round，按照预定轨迹在 网络中以恒定的速度移动，并以均匀部署于网络中的RP点为树根，构建K跳生 成树；其中，Round是指Sink节点从起始位置开始直至再次回到起始位置的过 程；RP点是预先人为指定的，均匀分布于网络之中供Sink在该处驻留进行数据 采集的地理位置坐标点；

所述构建K跳生成树为：

移动Sink节点到达RP点，向一跳邻居节点广播K跳树建立消息Tree_Msg， 消息中包含Hop，ID_RP，ID_i，E_residual，其中Hop、ID_RP、ID_i、E_residual分别为节 点到RP点的跳数、RP点的ID标识、传感器节点的ID标识、节点的剩余能量； 移动Sink的Hop设为0，E_residual为infinite；初始状态下所有节点的Hop均为 infinite；

直接收到移动Sink广播消息的节点，将自己的Hop设为1并将Tree_Msg 消息中的剩余能量替换成自己的剩余能量，向自己的一跳邻居节点继续广播 Tree_Msg；

中间节点i收到来自邻居节点j的Tree_Msg，如果节点i的HOP为infinite， 则节点i按照Hop升序顺序将发送节点j加入待选父节点列表中；最终，节点i 从待选父节点列表中选择剩余能量大于阈值E_th并且Hop数最小的节点j作为自 己的父节点；当存在多个满足条件的父节点时，则选取剩余能量最大的节点j作 为自己的父节点；如果节点i的所有待选父节点剩余能量均小于E_th，则选择剩 余能量最大的节点作为自己的父节点；确定父节点j后，将节点j的Hop←Hop+1 赋值给节点i，并将E_residual替换成节点i自己的剩余能量后继续转发Tree_Msg；

当Hop＝K，停止继续转发Tree_Msg消息，以该RP为树根的K跳树建立完 成；收到来自不同ID_RP的Tree_Msg则忽略后收到的消息，从而避免节点同时属 于两棵或多棵树；

所述孤立节点加入生成树为：

移动Sink在第一个Round之后，完成整个网络的分簇；T+ε后，网络中的孤立 节点i向周围邻居节点广播Isolated消息，消息中包含自己的ID信息；其中，T为 移动Sink遍历所有RP点所需时间，ε为位于RP点的移动Sink与K跳传感器节点通 信一次的时间；孤立节点是指在T+ε后Hop状态仍为initial的节点；

收到Isolated消息的非孤立节点立即向该节点返回ACK消息，ACK消息表示应 答消息，并成为该节点的父节点，消息中包含该节点到当前移动Sink所在位置的 跳数信息；同时存在多个ACK，节点i选择ACK消息中HOP最小的节点作为自己 的父节点；孤立节点将自己的时钟调整到与父节点时间同步；

所述数据采集阶段为：

生成树建立完成以后，移动Sink在网络中按预定轨迹遍历所有RP点进行数 据采集，采集缓存在各子树上的数据；当出现树缓存告急与时间告急时，节点将 告急后继续采集到的最新数据包按最短路径向Sink路由；移动Sink按预定轨迹 遍历所有RP点，使各节点可以根据时间同步时钟估计当前移动Sink所在位置 Loc，从而保证数据包可以主动向移动Sink上传。

进一步地，数据采集阶段的正常数据上传为：

未出现缓存告急和时间告急情况下，当移动Sink到达第i棵树的RP点时， 根据时间同步时钟，以RP_i为树根的树上的所有节点，沿着与树建立方向相反的 方向，向移动Sink节点上传数据包，直到移动Sink开始向下一RP点移动；

所述缓存告急包括节点缓存告急和树缓存告急；其中，节点缓存告急是指节 点缓存的数据超过自身容量的P％，P的值根据应用要求设置；树缓存告急是指同 一棵树上所有子树均找不到可以与之进行内存资源共享的邻居子树；

所述时间告急是指，当前时间距离树截止时间为t_stop时，移动Sink仍未出现在 自己所在树的RP点处，其中，t_stop为Sink在一个驻点上的驻留时间。

进一步地，所述缓存告急的节点缓存告急的数据上传为：

节点i出现缓存告急，而父节点未出现缓存告急，则节点i将接收或感知到 的最新数据包上传到父节点；

节点i出现缓存告急，且所有父节点均缓存告急而子节点未发出内存告急， 则节点i将接收或感知到的最新数据包向子节点转移；

节点i出现缓存告急，且所有父节点和子节点均缓存告急，则由节点i所在 子树的叶节点，向从属于同一树中非同一子树上的邻居叶节点发出内存共享请 求，若邻居子树上的叶节点存在可共享内存，则返回Response消息，消息中包 含该节点可用于内存共享的内存资源信息；节点i收到Response消息后，根据 Response消息中的可共享内存资源，把接收或感知到的最新的数据包发送给相应 邻居节点；若未收到来自邻居子树的Response消息，则表明邻居子树中所有节 点均出现缓存告急，此时即为出现树缓存告急现象。

进一步地，所述缓存告急的树缓存告急的数据上传为：

出现树缓存告急，叶节点向从属于不同树的一跳邻居节点发出内存资源共享 请求，收到请求包且处于不同树上的节点，如果存在可共享内存资源，则返回 Response消息；收到Response消息的节点根据Response消息中的可共享内存资 源，把接收或感知到的最新的数据包发送给相应邻居节点；如果所有一跳内的邻 居节点均簇缓存告急，则由叶节点将接收或感知到的最新的数据包主动向移动 Sink传输。

进一步地，所述时间告急数据上传为：

在给定V_sink、N_RP、D_RP和t_stop条件下，如果网络中节点出现时间告急，节 点按照最短路径路由，将树中出现时间告急的数据包向移动Sink主动上传，其 中，V_sink、N_RP、D_RP、t_stop分别指移动Sink移动速度、RP点数目、RP点间距 离、移动Sink在RP点上的驻留时间。

本发明的有益效果：本发明实现了节点内存资源有限情况下的节点间内存资 源共享，降低因内存溢出导致的丢包；生成树构建时通过对跳数距离和节点剩余 能量的考虑，均衡节点间的能量消耗。

附图说明

图1为本发明网络模型；

图2为本发明中移动Sink的工作流程图；

图3为本发明K跳生成树构建流程图；

图4为本发明移动Sink按照预定轨迹在网络中移动示意图；

图5为本发明中K跳生成树示意图。

具体实施方式

本发明通过移动Sink在网络部署区域内按照预定的轨迹进行数据采集，并根 据所述准备阶段和数据采集阶段，提出一种应用于无线传感器网络的移动Sink 数据采集方法。

本发明中主要提出使内存资源有限的节点之间进行内存资源的共享，并以 RP点为树根的K跳生成树为网络拓扑进行数据包的上传。K跳生成树具有如下 特点：

1)剩余能量较多的节点位于生成树的上端，即靠近树根，并拥有多个子节点；

2)剩余能量较多的节点承担较重的数据转发任务；

3)剩余能量较少的节点尽可能位于生成树末端，即远离树根，并拥有较少的子 节点；

4)剩余能量较少的节点承担较低的数据转发任务；

下面结合附图对本发明做更进一步的说明。

如图1所示为网络模型，网络中包括移动Sink节点，RP点和传感器节点。 移动Sink节点沿着预定轨迹在RP点驻留进行数据采集，网络内随机部署普通传 感器节点，这些节点地理位置信息已知，除了移动Sink外其他节点不可移动。 移动Sink以恒定速度V_sink沿预定轨迹移动。

如图2所示为移动Sink进行数据采集的流程图，具体包括如下步骤：

步骤201，移动Sink发起以RP点为树根的K跳生成树的建立，为准备阶段；

步骤202，移动Sink进行数据采集；

所述步骤201是指Sink在网络中的第一个Round。准备阶段，完成全网以预 定RP点为树根的K跳树的构建而不进行数据采集。准备阶段包括两个子部分： K跳生成树的建立和孤立节点加入生成树。

步骤201中K跳生成树的构建是指，移动Sink进入网络的第一个Round， 按照预定轨迹在网络中以恒定的速度移动，并以均匀部署于网络中的RP点为树 根，构建K跳生成树；其中，Round是指移动Sink节点从起始位置开始直至再 次回到起始位置的过程；RP点是预先人为指定的，均匀分布于网络之中供移动 Sink在该处驻留进行数据采集的地理位置坐标点；

K跳生成树的构建具体执行以下步骤，如图3所示：

步骤301，移动Sink节点发起K跳生成树的构建：

如图4所示，移动Sink按照预定轨迹在网络中遍历所有RP点。移动Sink 节点每到达一个RP点，向一跳邻居节点广播K跳树建立消息Tree_Msg，消息 中包含Hop，ID_RP，ID_i,E_residual，其中Hop、ID_RP、ID_i、E_residual分别为节点到 RP点的跳数、RP点的ID标识、传感器节点的ID标识、节点的剩余能量。移动 Sink的Hop设为0，E_residual为infinite。初始状态下所有节点的Hop均为infinite；

步骤302，中间节点选择父节点及转发树构建消息：

直接收到移动Sink广播消息的节点，将自己的Hop设为1并将Tree_Msg 消息中的剩余能量替换成自己的剩余能量，向自己的一跳邻居节点继续广播 Tree_Msg；

中间节点i收到来自邻居节点j的Tree_Msg，如果节点i的HOP为infinite， 则节点i按照Hop升序顺序将发送节点j加入待选父节点列表中。最终，节点i 从待选父节点列表中选择剩余能量大于阈值E_th并且Hop数最小的节点j作为自 己的父节点；当存在多个满足条件的父节点时，则选取剩余能量最大的节点j作 为自己的父节点；如果节点i的所有待选父节点剩余能量均小于E_th，则选择剩 余能量最大的节点作为自己的父节点。确定父节点j后，将节点j的Hop←Hop+1 赋值给节点i，并将E_residual替换成节点i自己的剩余能量后继续转发Tree_Msg；

步骤303，终止转发K跳生成树建立消息：

直到Hop＝K，停止继续转发Tree_Msg消息，以该RP为树根的K跳树建立 完成。收到来自不同ID_RP的Tree_Msg则忽略后收到的消息，从而避免节点同时 属于两棵或多棵树。

步骤304，孤立节点加入生成树：

移动Sink在第一个Round之后，完成整个网络的分簇；T+ε后，网络中的孤立 节点i向周围邻居节点广播Isolated消息，消息中包含该节点的ID信息。其中，T 为Sink遍历所有RP点所需时间，ε为位于RP点的移动Sink与K跳传感器节点通信 一次的时间；孤立节点是指在T+ε后Hop状态仍为initial的节点。收到Isolated消息 的非孤立节点立即向该节点返回含有到RP的跳数信息的ACK消息，ACK消息表 示应答消息，并成为该节点的父节点，消息中包含该节点到当前移动Sink所在位 置的跳数信息；同时存在多个ACK，节点i选择ACK消息中Hop最小的节点作为自 己的父节点。孤立节点将自己的时钟调整到与父节点时间同步。

如图5所示为按照上述原则构建的以RP点为树根所成的K跳生成树。

步骤202所述数据采集阶段为生成树建立完成以后，Sink在网络中进行数据采 集的过程。数据采集阶段包括：正常数据上传、缓存告急数据上传和时间告急数 据上传；

数据采集阶段，移动Sink以预定轨迹遍历各RP点，对缓存在各子树上的数 据进行收集。在出现树缓存告急和时间告急时，节点将接收或感知到的数据包根 据最短路径向Sink路由。移动Sink按预定轨迹遍历所有RP点，使各节点根据 时间同步时钟估计当前移动Sink所在位置Loc，从而保证数据包可以主动向移 动Sink上传。

所述节点根据时间同步时钟估计当前移动Sink的所在位置Loc，如图4所示为 移动Sink按预订轨迹移动示意图。移动Sink在RP点驻留时间为t_stop，在两RP点间 移动速度为V_sink，相邻两RP点间欧式距离为D_RP，任意时刻t，可确定移动Sink的 位置信息。如果(k-1)*(t_stop+D_RP/V_sink)≤t≤(k-1)*(t_stop+D_RP/V_sink)+t_stop，则Sink驻留 在ID为k的RP点，k取值为1，2，……，N_RP；如果(k-1)*(t_stop+D_RP/V_sink)+ t_stop≤t≤k*(t_stop+D_RP/V_sink)，则移动Sink在ID为k与k+1的两个RP点间移动。由于移动 Sink仅在RP点采集数据，当移动Sink在两个RP点间移动时，需要按照最短路径 向移动Sink传输数据包的节点，等待t₁＝k*(t_stop+D_RP/V_sink)+t_stop-t时间后，向移动 Sink传输数据包。

下面详细介绍数据采集阶段：

(1)正常数据上传

未出现缓存告急及时间告急情况下，当移动Sink到达第i棵树的RP点时， 根据时间同步时钟，以RP_i为树根的树上的所有节点，沿着与树建立方向相反的 方向，向移动Sink节点上传数据包，直到移动Sink开始向下一RP点移动；

(2)缓存告急数据上传

所述缓存告急包括节点缓存告急和树缓存告急；

1)节点缓存告急数据上传

当节点缓存的数据超过自身容量的P％，P的值根据应用要求设置，则称节 点缓存告急。节点缓存告急时，数据上传过程如下：

节点i出现缓存告急，而父节点未出现缓存告急，则将接收或感知到的最新 数据包上传到父节点；

节点i出现缓存告急，且所有父节点均缓存告急而子节点未发出内存告急， 则将接收或感知到的最新数据包向子节点转移；

节点i出现缓存告急，且所有父节点和子节点均缓存告急，则由节点i所在 子树的叶节点，向从属同一树中非同一子树上的邻居叶节点发出内存共享请求。 若邻居子树上叶节点存在可共享内存，则返回Response消息，消息中包含该节 点可用于内存共享的内存资源信息；收到Response消息的节点根据Response消 息中的可共享内存资源，把接收或感知到的最新的数据包发送给相应邻居节点； 若未收到来自邻居子树的Response消息，则表明邻居子树中所有节点均出现缓 存告急，此时即为出现树缓存告急现象；

2)树缓存告急数据上传

当同一棵树上所有子树均找不到可以与之进行内存资源共享的邻居子树，则 称树缓存告急。树缓存告急时，叶节点向从属于不同树的一跳邻居节点发出内存 资源共享请求，收到请求包且处于不同树上的节点，如果存在可共享内存资源， 则返回应答Response消息。收到Response消息的节点根据Response消息中的可 共享内存资源，把接收或感知到的最新的数据包发送给相应邻居节点；如果所有 一跳内的邻居节点均簇缓存告急，则将接收或感知到的最新的数据包主动向Sink 传输。

(3)时间告急数据上传

时间告急是指，当前时间距离树deadline为t_stop时，Sink仍未出现在自己所在 树的RP点。其中，t_stop为Sink在一个驻点上的驻留时间。当出现时间告急，在给 定V_sink、N_RP、D_RP和t条件下，节点按照最短路径路由，将树中出现时间告急的 数据包向Sink主动上传。其中，V_sink、N_RP、D_RP、t_stop分别指Sink移动速度、RP 点数目、RP点间距离、移动Sink在RP点上的驻留时间。