基于轨迹受限的移动Sink低能耗数据收集协议

2017-12-15王传平刘方斌于京杰

数据采集与处理 2017年5期

关键词：全网能耗轨迹

徐佳王传平戴华刘方斌于京杰

(1.南京邮电大学计算机学院，南京,210003;2.南京理工大学连云港研究院，连云港,222006;3.南京军区南京总医院，南京,210002)

基于轨迹受限的移动Sink低能耗数据收集协议

徐佳1,2,3王传平1戴华2刘方斌3于京杰3

(1.南京邮电大学计算机学院，南京,210003;2.南京理工大学连云港研究院，连云港,222006;3.南京军区南京总医院，南京,210002)

无线传感器网络数据收集的能耗问题一直以来都是研究的热点。本文主要研究基于移动Sink轨迹受限的数据收集协议。首先针对轨迹受限的无线传感网络提出一种通用的系统模型，将该问题形式化为最大化降低全网总路径长度轨迹设计问题(Maximizing total length reduction for constrained trajectory,MTRC)，并证明了MTRC为NP-Hard问题；然后设计一种轨迹约束低能耗贪心算法(Trajectory constrain of low energy consumption,TCLEC)，通过TSP近似算法设计最大化降低有效长度的Sink移动轨迹。理论分析和仿真实验结果表明，TCLEC在网络拓扑数据收集树的初始化以及优化方面是高效的，并且相对于同类基于移动Sink的无线传感网络分层数据收集方法,其能耗降低了7%左右。

传感器网络；移动Sink；能量消耗；受限轨迹

引言

随着数字电子技术和无线通信技术的不断进步与发展，无线传感器网络(Wireless sensor networks,WSNs)广泛应用于物品监控、事件探测、目标跟踪和环境感知等领域。在这些应用中，传感器节点主要完成3个方面的工作:(1)从感知环境中采集所需要的数据；(2)将数据进行存储或处理；(3)发送数据或转发其他节点的数据并最终达到数据收集节点。

近年来，人们提出了基于移动Sink的数据收集方案，使用一个或多个移动Sink节点在特定路径上移动，减少传感器节点的数据转发，除了降低能量消耗外，还能使得全网能量消耗更加平均。在WSNs中大部分节点之间进行数据转发需要多跳才能到达，如何降低传感器节点之间的路由跳数，成为降低全网能耗的关键问题。在极端情况下，移动Sink节点可轮询每个节点(称为平面收集方法)，该方法使每个节点与移动Sink节点之间的数据转发只有一跳的距离，虽然此时传感器节点的能耗最小，但是移动Sink进行数据收集的时延也最大。在大规模传感器网络中，这种数据收集方式的工作效率较低。一种可行的解决方法是容忍一定的时延，来弥补传感器节点能量的消耗，使传感器网络的能量消耗和移动Sink收集数据的时延达到一定的平衡。由此引出了基于收集节点的移动Sink数据收集方法，与静态传感器网络不同，该方法需要将整个网络划分成若干个数据收集树，数据收集树的根为收集节点，其余节点将数据转发至对应的收集节点，移动Sink轮询每个收集节点最终获取整个网络的数据。

本文提出一种无线传感网络的数据收集系统模型，并且形式化这种移动轨迹问题为最大化降低全网总路径长度轨迹设计问题(Maximizing total length reduction for constrained trajectory, MTRC)，同时证明MTRC问题是NP-Hard问题；然后提出一种基于贪心策略的贪心算法——低能耗轨迹约束算法(Trajectory constraint of low energy consumption, TCLEC)，通过仿真验证TCLEC算法在优化全网能耗方面的优化效果。仿真结果表明在数据收集时延与其他分层数据收集协议相当的情况下，TCLEC能将全网的总能耗降低7%左右，有效延长了整个网络的生存周期。

1 相关工作

目前, 已有许多文献对基于分层拓扑的移动Sink数据收集方法进行了研究。Chakrabarti等[1,2]首次提出通过预测Sink节点的移动性以提高传感器网络性能。Sink节点被安置在周期运行的公车上，传感器节点随机分布在固定的公车移动路线两侧。作者利用排队模型分析了丢包率、能耗、数据速率及通信功率之间的关系。文献[1,2]中，所有节点分布在移动Sink一跳通信范围内，传感器节点数据通过单跳通信方式向移动Sink发送数据。在实际应用的复杂场景下，由于受到Sink节点移动轨迹和有效通信距离的限制，并非所有传感器节点都能可以与Sink节点直接进行通信。在延时容忍的无线传感器网络移动数据收集(Wireless sensor network-mobile data collection,WSN-MDC)应用中，只要在规定时间内完成数据传输即可，但时延仍然应该尽可能地缩短[3,4]。文献[3]根据RP 节点的重要程度为其赋予优先访问概率，而He等[4]考虑了节点间感知数据的相似性，对RP 点进行组合。朱林等[5]通过在无线传感网络树形拓扑结构中使用数据集成技术，降低数据包指令的冗余信息，从而降低树形WSN的网络能耗，但对于去除冗余信息时所消耗的能量没有过多的考虑。低功耗自适应集簇分层型协议(Low energy adaptive clustering hierarchy, LEACH)[16]是较早提出的分簇算法，该协议从逻辑上将无线传感网络拓扑结构划分为若干个簇，采用循环随机轮流的方式选举簇首，每个簇中的子节点将数据转发到簇首节点。LEACH 的核心思想是通过随机选择簇首，从而将整个网络的能量负载平均地分配到每个传感器节点上，达到降低网络能源消耗的目的，但簇首的选取有时难以达到理想的效果，并不能很好地解决能量消耗问题。可变轨迹集合点设计(Rendezvous design through variable tracks,RT-VT)算法[7]是一种基于最小生成树(Minimum spanning tree,MST)和施泰纳最小树(Steiner minimum tree,SMT)设计最优路径的方法，解决传感器子节点到其相应收集节点的通信路径问题，使无线传感网络的数据收集时延和能耗更加平均。在分簇的无线传感网络场景下，文献[8]利用预扩散算法(Pre-diffusion algorithm,PDA)提出一种新型的数据收集模型，该方法在固定的移动Sink收集数据轨迹的情况下，通过移动Sink、簇头CH和传感器节点之间的信息传递与交换，确定最终与移动Sink进行交互和收集信息的CH，该方法考虑了移动Sink轨迹长度受限的情况，进一步提高了网络数据收集的性能。但是PDA算法对于传感器节点的能耗没有过多的考虑，尤其是每个簇头的能量消耗，可能会导致传感器节点过早死亡，从而影响传感器网络的整体性能。文献[9]通过建立最大化最小能耗概率模型来寻找各数据收集树的最佳路径长度，但需要重复建立初始收集树，复杂度较高。

2 系统模型和问题形式化

2.1 系统模型

假设在网络中有N个传感器节点随机分布在大小为m×m的范围内，移动Sink沿着收集数据的路径轨迹收集数据。由于传感器节点通信范围有限，所以大部分节点需要多跳才能与移动Sink节点通信。为此，将直接发送数据到移动Sink的传感器节点称为收集节点，其余节点称为普通节点，普通节点将消息传递转发到相应的收集节点，由收集节点转发给移动Sink。图1给出了基于移动Sink的无线传感器网络数据收集树的示意图。

图1 基于移动Sink的无线传感器网络数据收集树 Fig.1 Mobile Sink based data collection in wireless sensor networks

移动Sink节点沿着轨迹M并以恒定速度C移动，进行传感器网络的数据收集，移动Sink移动速度C在Qian[10]和Mario[11]中有较为详细的介绍。传感器节点均匀散布在移动轨迹M两侧，数量为N。假设在时间段T内, 每个传感器节点都会产生r比特数据,且这些数据必须在T时间内传送至移动Sink节点。此处的T表示移动Sink进行一轮数据收集的时延上限。故Sink节点沿着移动轨迹M进行数据收集，并且最终回到出发位置的路径长度上限为Lm=C·T。

在本文的系统模型中，传感器节点密集分布在传感器网络中，每个节点都可通过单跳或多跳与其他节点通信。传感器节点具有相同的配置，能获得自身位置信息，并处于静止状态。移动Sink通过访问收集节点进行全网数据收集。本文不考虑能量控制问题，并假设传感器节点采用相同的发射功率和接收功率，因此能耗与传输节点间的距离无关。采用文献[12]中所述的能耗模型

E≈a(pr+pt)

(1)

传感器节点总能耗E由接收数据总量pr和发送数据总量pt共同决定，其中a为常数，表示传感器节点收发单位比特数据所需的能耗。

(2)

式中：hi表示子节点i到其收集节点的跳数。如果传感器节点i为收集节点，则hi为0。根据式(2)，可将单轮系统总能耗Etotal表述为最小跳数和的形式，即

(3)

2．2 问题形式化

根据式(3)，传感器网络的能耗最小化问题等价于全网普通节点距离其相应的收集节点跳数和的最小化问题，即数据收集树的总路经长度最小化问题。初始数据收集树的收集节点定义为移动Sink通信范围内的传感器节点，本文通过剪枝算法对初始网络拓扑收集树进行剪枝，生成更多收集节点，以降低传感器网络的总路径长度。

设lij为vi和vj之间的欧氏距离，本文的目标是设计移动Sink运动轨迹M，使得在时间周期T内完成所有传感器节点的数据收集回到出发点，并且使得降低的全网总路径长度最大。该问题称为最大化降低全网总路径长度轨迹设计问题(Maximizing total length reduction for constrained trajectory,MTRC)，可表示为

(4)

目标函数

(5)

约束条件

目标函数(5)表示设计移动Sink收集数据的运动轨迹M，使得降低的全网总路径长度最大；约束条件(6)表示移动轨迹M从出发点开始，回到出发点结束；约束条件(7)表示传感器节点之间具有连通性，且每个节点只能被访问一次；约束条件(8)表示M的长度限制。

3 最大化降低全网总路径长度轨迹设计

3．1 MTRC问题的复杂度

根据本文系统模型，解决MTRC问题的关键是如何设计高效的算法对初始化网络拓扑收集树剪枝优化，以降低全网总路径长度和降低全网能耗。通过下面的引理，即使Si为一常量(称为静态MTRC问题)，寻找最优解是NP-Hard的。

引理1静态MTRC问题是NP-Hard问题。

证明：首先证明静态MTRC问题属于NP问题。定义静态MTRC问题的一个实例，验证算法检查移动Sink进行全网的数据收集的轨迹长度M是否超过C·T，并且检查全网的降低全网总路径长度是否至多为k。这一过程可以在多项式时间之内完成。本文通过已知的NP-Hard问题定向运动问题(Orienteering problem,OP)[13]，证明静态MTRC是NP-Hard问题。

OP实例(由X表示)：定义一个图G=(V,A)，其中V={v1,…,vn}表示顶点集，A表示边集。非负的分数Si与每个顶点vi∈V相关，遍历时间tij与每条边aij∈A有关。对于任意正数k，问题是：是否存在一条包含V的子集的哈密顿回路G′(⊂G)，其中，在G′中的每个顶点的分数和不低于k，包括预先设置好的起始顶点(v1)和终止节点(v1)，并且遍历时间不超过Tmax。

对应的静态MTRC实例(由Y表示)：定义一个图G=(V,A)，其中V={v1,…,vn}是传感器节点集合，A表示边集。非负的降低路径长度Si与每个顶点vi∈V相关，欧氏距离lij与每条边aij∈A有关。对于k,C和T来说，问题是：是否存在一条包含V的子集的哈密顿回路(移动Sink收集数据轨迹)G′(⊂G)，其中，在G′中的每个传感器节点降低的总路径长度不低于k，包括预先设置好的起始顶点(v1)和终止节点(v1) ，并且以及移动Sink的移动轨迹长度不超过C·T。从X到Y的转化是在多项式时间之内完成的。显然，MTRC问题要比静态的MTRC问题更加复杂。所以得出下述定理1：MTRC问题是NP-Hard问题。

3.2 TCLEC设计与分析

由于MTRC问题是NP-Hard问题，由此本文主要研究相关近似算法解决MTRC问题。TCLEC分为两个阶段，在第一阶段，移动Sink在网络中随机选择一点作为路径起点，并发送广播，移动Sink的通信半径范围内的传感器节点收到消息后成为初始收集节点；初始收集节点继续广播消息，初始收集节点通信半径范围内的传感器节点收到消息后成为该收集节点的子节点；子节点继续广播消息，附近的子节点收到消息后成为广播消息子节点的后继，以此建立初始化网络拓扑收集树。在第二阶段，在满足移动轨迹的限制下，通过基于贪心策略的剪枝算法寻找最优收益比(降低总路径长度与增加轨迹长度的比值)的节点，使之成为新的数据收集节点，直到不再满足移动轨迹限制为止。

3．2．1 第一阶段：初始化数据收集树

定义两类消息格式和一类存储格式：MSG(Id,Prenode,Type,Level)表示广播消息格式，其中，Id为节点标识；Prenode为上一跳节点的Id；Type为节点的类型，其中0代表Sink节点，1代表收集节点，2代表普通节点；Level代表节点的层数。MSG_ACK (Id,Prenode,Nextnode,Type,Level,Num,S)为发送反馈消息格式，其中，Id为节点标识；Prenode为上一跳节点的Id；Nextnode为下一跳节点的Id；Type为节点的类型，其中0代表Sink节点，1代表收集节点，2代表普通节点；Level代表节点的层数；Num表示该节点所具有的子节点个数；S表示以该节点作为收集节点可降低的全网总路径长度。

在移动Sink中顺序存储传感器节点信息，设数据结构为A，节点存储格式为MS(Flag1,Id,Prenode,Nextnode,Type,Level,Num,S,Stotal,Flag2)，其中，Flag1表示传感器节点信息的开始标志位，Flag2表示传感器节点信息的结束标志位，Id表示该传感器节点的标识；Prenode表示该节点的上一跳节点Id；Nextnode代表节点的下一跳节点的Id；Type表示该节点的类型，0代表Sink节点，1代表收集节点，2代表普通节点；Level代表节点的层数；Num表示该节点所具有的子节点个数；S表示以该节点作为收集节点可降低的全网总路径长度；Stotal表示以该节点为根节点的数据收集树的总路径长度。初始化数据收集树算法如算法1所示：

算法1初始化数据收集树算法

Algorithm 1:Initializing data collection tree

while(ReceiveMSG ()) do

Become a child node;

SettingMSG;

SendMSG_ACK();

if(node.type!=0) then SendMSG();

end

while(ReceiveMSG_ACK()){

if(node.type!=0) then

Reseal broadcast message MSG_ACK;

SendMSG_ACK();

end

if(node.type==0) then Store as MS;

end

该阶段的算法流程为：

(1) 移动Sink发送寻找初始收集节点的广播消息MSG，在其通信半径范围之内的传感器节点接收到此广播消息，返回MSG_ACK确认消息后，成为该Sink节点的孩子节点，即初始收集节点，该收集节点更新其消息MSG并继续广播。

(2) 在该收集节点通信半径范围内的传感器节点接收到广播消息，返回MSG_ACK确认消息，成为该收集节点的子节点，此传感器节点更新消息MSG并继续广播消息。

(3) 重复步骤(2)，直到没有传感器节点落单。当传感器节点没有收到MSG_ACK确认消息，则此传感器节点成为叶子传感器节点。

(4) 叶子传感器节点发送消息MSG_ACK至其父传感器节点，父传感器节点更新自身节点信息、父传感器节点将自身信息和MSG_ACK上一跳信息打包为新的广播信息，继续向上返回消息。

(5) 重复步骤(4)，直到接收到广播信息的传感器节点类型为0，即接收消息的传感器节点为Sink节点时，结束消息转发。Sink节点将全网的传感器节点的数据以MS方式存储。此时初始数据收集树构造完成。

3.2.2 第二阶段：数据收集树的剪枝

Sink节点中顺序存储的传感器网络节点信息转换为van Emde Boas树存储的形式，节点信息的存储格式为：NS(Leftnode,Id,Prenode,Nextnode,Type,Level,Num,S,Rightnode),其中，Leftnode表示该节点的左孩子节点Id；Id表示该节点的标识；Prenode表示该节点的上一跳节点的Id；Nextnode表示该节点的下一跳节点的Id；Type表示该节点的类型，其中1代表收集节点，2代表普通节点；Level代表节点的层数；Num表示该节点所具有的子节点个数；S表示以该节点作为收集节点可降低的全网总路径长度；Rightnode表示该节点的右孩子节点Id。

(1) 将传感器节点的顺序存储转换为van Emde Boas树存储，设存储结构为NS；

(2) 在van Emde Boas树中查找U最大的传感器节点，将其Id记录到B中，根据传感器节点中的Prenodeid值查询该传感器节点的上一跳Id，并将其Id存到B中，直到某个传感器节点的Prenodeid为Null，结束对van Emde Boas树的搜索，此时B中形成一条剪枝链路；

(3) 根据B中存储的剪枝链路对数据收集树进行剪枝操作，栈底节点即为数据收集树的剪枝节点。结合D中的收集节点信息，通过旅行商算法计算移动Sink收集数据轨迹的最短路径。当L≤C·T时，将此收集节点的信息存储至D，更新A中存储的传感器节点信息；

(4) 重复步骤(1～3)，进行下一轮剪枝，选取新的剪枝链路。当L>C·T时，结束对传感器网络拓扑收集树的优化，并放弃本轮剪枝，最终形成移动Sink收集数据的移动轨迹。数据收集树剪枝算法如算法2所示。

算法2数据收集树剪枝算法

Algorithm2:Cutting of data collection tree

while(L

Transfer MS to NS;

for each nodei∈NS doj=argmaxiNS{S/(AddTSP(i))};

k=j;

B.push(k);

k=k->next;

ifk.type!=0 thenB.push(k);

D.push(j);

Update(A);

end

AddTSP(noden){

L=TSP (D);

D.push(n);

Lnew= TSP (D);

ΔL=Lnew-L;

D.remove(n);

return ΔL;

}

3．3 TCLEC算法时间复杂度分析

TCLEC的时间复杂度由while循环决定，传感器网络中每个节点至多被剪枝一次，因此while循环的执行次数最多为O(n)，通过欧氏距离计算移动Sink收集数据的最短路径长度，在近似度为2的情况下，TSP()的时间复杂度为O(n2)，AddTSP()的复杂度也为O(n2)，因此for循环的时间复杂度为O(n3)。在该for循环中，寻找最大U的复杂度为O(n)，所以该算法剪枝操作优化过程的总时间复杂度为O(n5)。实际中，收集节点的数量会远小于总节点数量n，因而O(n5)是非常保守的估计。

4 仿真

在Matlab平台上仿真实现TCLEC算法。为了验证该算法的相关性能，将其与LEACH算法，RT-VT算法和PDA算法在能耗等方面的主要性能进行仿真对比。所设置的仿真场景为500 m×500 m，该场景随机均匀分布了100～1 000个传感器节点，移动Sink的初始位置是(100,100)，传感器网络中的传感器节点之间的通信范围为50 m，传感器节点的初始能量设为5 000 J，移动Sink节点的初始能量设为1×106J，传感器节点收发单位比特数据所需要的能耗a设为1 J，移动Sink移动速度为2 m/s，每个传感器节点数据产生的周期T为1 000 s，每个周期内每个传感器产生500比特数据。仿真结果为经过200次独立实验的平均值。

主要对以下4个方面进行相关实验仿真。

(1) 全网能耗：无线传感网络在移动Sink的数据收集周期内所有传感器节点的能耗总和。图2和图3分别给出了在不同节点数量和Sink不同移动速度下的全网总能耗变化图。

图2 不同节点数量下的全网总能耗图3 Sink不同移动速度下的全网总能耗Fig.2 Energy consumption with different numbers of nodes Fig.3 Energy consumption with different Sink speed

(2) 全网生存周期：以移动Sink节点运动周期(即轮数)为单位，从数据正式采集开始到首个节点能量耗尽时结束所经历的时间。图4和图5分别给出了在不同节点数量和不同Sink移动速度下的全网生存周期变化图。

图4 不同节点数量下的全网生存周期Fig.4 Network lifetime with different number of nodes

图5 Sink不同移动速度下的全网生存周期Fig.5 Network lifetime with different Sink speed

(3) 全网总路径长度：所有传感器节点通过多跳的方式将数据转发到移动Sink节点的总跳数。图6给出了在不同节点数量下4种算法的全网总路径长度的变化图。

(4) 剪枝次数：通过TCLEC算法优化网络拓扑收集树所需的剪枝次数，结果如图7所示。

图6 不同节点数量下的全网总路径长度Fig.6 Total path length with different numbers of nodes

图7 不同节点数量下的数据收集树剪枝次数Fig.7 Numbers of cutting with different numbers of nodes

图2表明，随着节点数量的不断增加，在单轮数据收集时间周期T内，4种算法的全网总能耗也在不断增加。LEACH算法能耗最大；RT-VT通过SMT和MST构建解决方案，但没有考虑传感器节点的多样性以及分布性，全网总能耗相对较高；PDA算法通过传感器节点之间的消息转发和CH节点的状态变化确定CH节点，进而确定移动Sink进行数据收集的移动轨迹，在全网数据收集的性能方面具有较好的优化，但因为CH节点和相关传感器节点需要动态的接收、转发消息以及改变状态，该过程需要过多的能量消耗，所以全网的总体能耗相对较大；TCLEC通过剪枝初始化网络拓扑数据收集树，增加传感器网络数据收集节点，降低全网总能耗，在网络能耗方面相对PDA等算法平均降低了7%左右。

图3表明，在相同的实验仿真场景下，传感器节点数量固定为900，随着移动Sink数据收集移动速度的不断增加，3种不同算法协议的全网总能耗在不断降低。在轨迹长度受限的情况下，移动Sink的移动速度不断增加，则移动Sink可以访问更多的数据收集节点或CH节点，即表示无线传感网络的数据收集节点或者作为收集节点的CH节点数量也在不断增多，从而全网总能耗也在不断降低。所以随着Sink收集数据移动速度的不断增加，全网总能耗也在不断降低。

图4表明，随着节点数量的不断增加，4种算法的全网生存周期不断降低。LEACH算法网络生命周期较短；RT-VT算法随着传感器节点数量的不断增加，通过MST算法增加收集节点的数量，在全网能耗方面有较为明显的优化，使得全网生存周期相对LEACH算法较长；在移动Sink收集数据轨迹预设的情况下，随着传感器节点数量的不断增加，PDA算法通过广播通信和设置CH节点状态，提前设定作为收集节点的CH节点，有效延长了全网生存周期，但是移动Sink收集数据的轨迹动态变化，可能会导致某个负责传递消息和数据收集的CH节点需要进行过多的通信和数据交互，从而提前能量耗尽，进而影响全网生存周期；TCLEC算法通过增加传感器网络收集节点以及通过TSP算法计算移动Sink收集数据最短移动轨迹的方式降低全网总能耗，从而使得在网络生存周期方面相对于另外两种算法具有较好的性能，根据试验仿真，全网生存周期相对优化了9%左右。

图5表明，在相同的实验仿真场景下，传感器节点数量固定为900，随着移动Sink数据收集移动的速度不断增加，3种不同算法协议的全网生存周期也在不断增加。因为3种不同的算法协议在移动Sink数据收集速度不断增大的情况下，全网总能耗在不断降低，意味着全网生存周期在不断增加。所以随着移动Sink移动速度的不断增加，全网生存周期也在不断增加。

图6表明，在移动Sink数据收集轨迹长度受限的情况下，TCLEC算法构造网络拓扑收集树的总路径长度相对较小。TCLEC算法对网络拓扑收集树进行剪枝操作，增加移动Sink收集数据的收集节点，从而降低全网的总路径长度。LEACH算法随机选取簇首节点，以削弱的“热点”问题的影响，但在簇内节点到簇首节点的路径长度方面没有进行优化操作。PDA算法通过预设移动Sink数据收集的移动轨迹和传感器节点之间的通信，确定与移动Sink进行数据交互的CH收集节点的位置，但对于簇内节点到作为数据收集节点的CH节点的路径长度，以及子簇到作为数据收集节点的CH节点的路径长度没有考虑，从而应影响全网的总路径长度。RT-VT基于MST和SMT设计移动基础设施收集数据轨迹，使子节点到其汇聚节点的路径较优。但在选取汇聚节点时，更多局限于子收集树进行选取，使当前子收集树总路径长度达到最优，对全网总路径长度最优没有过多的考虑，使其优化效果要次于TCLEC。

图7表明，随着传感器节点数量增多，剪枝次数也在不断增多。TCLEC协议使用贪心算法最大化收益比，随着网络规模的扩大，收集节点的选择面增大，在同样条件下剪枝次数会增加。

5 结束语

本文将移动Sink的无线传感器网络数据收集的能耗问题建模为最大化降低总路径长度轨迹设计问题MTRC，证明该问题是NP-Hard问题。提出解决此问题的低能耗数据收集协议TCLEC，证明该数据收集协议的算法时间复杂度是O(n5)。在初始数据收集树的基础上，通过剪枝操作优化数据收集树，从而降低全网总路径长度，降低传感器网络总能耗和延长全网生存周期，并从理论上证明了该方法的有效性。仿真实验结果表明与同类协议相比，TCLEC能够有效降低整个传感器网络数据收集的能量消耗和延长网络的生存周期。本文提出了最大化降低总路径长度轨迹设计问题MTRC，但在复杂的无线传感器网络现实应用中，可能面临着传感器节点数量过多，移动Sink轨迹不可控等诸多限制条件，这也是今后进一步研究的方向。

[1] Chakrabarti A, Sabharwal A, Aazhang B. Communication power optimization in a sensor network with a path-constrained mobileobserver[J]. ACM Trans on Sensor Networks, 2006,2(3):297-324.

[2] Chakrabarti A, Sabharwal A, Aazhang B. Using predictable observer mobility for power efficient design of sensor networks[C]∥Proc of the 2nd Int′l Workshop on Information Processing in Sensor Networks (IPSN 2003). Berlin:Springer-Verlag, 2003:129-144.

[3] Zhang X W, Zhang L L. Optimizing energy-latency trade-off in wireless sensor networks with mobile element[C]∥Proc of the IEEEICPADS. New York: IEEE Press, 2010: 534-541.

[4] He L, Pan J P, Xu J D. A progressive approach to reducing data collection latency in wireless sensor networks with mobile elements[J]. IEEE Transactions on Mobile Computing, 2013,12(7):1308-1320.

[5] 朱林,张海.数据集成技术在树型WSN中的应用[J].数据采集与处理,2013,28(6):818-822.

Zhu Lin,Zhang Hai.The application on a technology of data integration in tree structure WSN [J].Journal of Data Acquisition and Processing,2013,28(6):818-822.

[6] 吕涛, 朱清新, 张路桥. 一种基于LEACH协议的改进算法[J]. 电子学报, 2011,39(6):1405-1409.

Lü Tao,Zhu Qingxin, Zhang Luqiao.An improved LEACH algorithm in wireless sensor network[J].Acta Electronica Sinica, 2011,39(6):1405-1409.

[7] Xing G，Wang T，Jia W，et al. Rendezvous design algorithms for wireless sensor networks with a mobile base station[C]//Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing. Hong Kong，China：ACM，2008， 5317 (6) : 231-240.

[8] Zhang Zhongyu,He Zunwen,Jia Jianguang,et al. A new data gathering scheme for trajectory constrained mobile Sink in WSN[C]// 2012 International Conference on Wireless Communications & Signal Processing (WCSP). Huangshan,China:IEEE,2012,10(25-27): 1-6.

[9] 徐佳, 冯鑫, 杨富贵, 等. 最大化最小能耗概率的移动 Sink 无线传感器网络数据收集方法[J]. 电子学报，2015，43(12)：2470-2475.

Xu Jia，Feng Xin， Yang Fugui，et al. A data collection method by maximizing minimum probability of energy consumption for mobile sink based WSNs[J]. Acta Electronica Sinica，2015，43(12)：2470-2475.

[10] Dong Q, Dargie W. A survey on mobility and mobility-aware MAC protocols in wireless sensor networks[J]. Communications Surveys & Tutorials, 2013, 15 (1): 88-100.

[11] Francesco M D, Das S K, Anastasi G. Data collection in wireless sensor networks with mobile elements: A survey[J]. ACM Transactions on Sensor Networks, 2011, 8(1):7.

[12] Tseng Y C,Lai W T,Huang C F,et al. Using mobile mules for collecting data from an isolated wireless sensor network[C]∥Proceedings of 39th International Conference on Parallel Processing. San Diego, CA, United States: IEEE,2010:673-679.

[13] Golden B, Levy L, Vohra R. The orienteering problem[J]. Naval Research Logistics, 1987,34(3):307-318.

LowEnergyConsumptionDataCollectionProtocolBasedonTrajectoryConstrainedMobileSink

Xu Jia1,2,3，Wang Chuanping1， Dai Hua2，Liu Fangbin3，Yu Jingjie3

(1.Department of Computer， Nanjing University of Posts and Telecommunications， Nanjing, 210003， China;2.Lianyungang Institute, Nanjing University of Science and Technology， Lianyungang, 222006， China;3.Nanjing General Hospital of Nanjing Military Command， Nanjing, 210002， China)

Energy consumption problem in wireless sensor networks for data collection has always been a research focus. In this paper, we focus on exploring protocol of designing the constrained trajectory of the mobile sink for data collection. A universal system model for designing constrained trajectory in wireless sensor networks is firstly presented, which is formulated as the problem of the maximum total length reduction for constrained trajectory (MTRC). MTRC is proved to be the problem of NP-hard. Secondly, a greedy algorithm of trajectory constraint of low energy consumption (TCLEC) is designed and the movement trajectory of the mobile sink by maximizing the efficient length reduction is designed through TSP approximate algorithm. Theoretical analysis and simulation results show that the TCLEC algorithm has achieved high computation efficiency in the initialization and optimization of data collection tree of network topology. Compared with other hierarchical data collection methods based on mobile sink, the energy consumption has reduced about 7%.

sensor network; mobile Sink; energy consumption; constrained trajectory

国家自然科学基金(61472193,61472192,61502251,91646116)资助项目;江苏省科技支撑计划(BE2016776)资助项目;江苏省自然科学基金(BK20141429,BK20151511)资助项目。

2015-10-18；

2015-10-29

TP301