带有移动Sink的传感器网络回路避免跟踪协议

徐慧芬，邬春学，杨桂松

(上海理工大学 光电信息与计算机工程学院，上海 200093)



带有移动Sink的传感器网络回路避免跟踪协议

徐慧芬，邬春学，杨桂松

(上海理工大学 光电信息与计算机工程学院，上海 200093)

无线传感器网络通常被应用于收集大规模网络中的传感数据，这些收集工作由Sink完成。为了降低网络内能量空洞产生的概率，延长网络寿命，目前多采用移动Sink收集数据。文中提出了一种带有移动Sink的数据收集协议。该协议中，Sink节点能根据相邻足迹节点间坐标夹角的变化,有效回避掉那些回路上的足迹节点，而只保留非回路上的足迹节点。仿真实验结果表明，LAT协议可显著提升数据查询效率，并有效延长了网络寿命。

移动Sink；数据查询； LAT协议；回路避免

无线传感器网络由大量价格低廉，处理能力较弱的传感器节点组成，其应用范围广泛，从精密的军事领域到传感信息繁多的农业领域。这些网络的规模通常较大，网络中节点数量较多，所需采集的数据类型较多，数据量大，且呈现出分布式特征。

在无线传感网中存在一个汇聚节点(Sink)用来收集传感器节点感知到的数据[1-6]。当Sink是静态时，传感器节点会根据指定的位置将感知数据路由给Sink，但这样会使Sink附近的传感器节点能量快速消耗，造成能量黑洞，从而缩短网络寿命。因而现在的研究中，Sink大多是移动的。但由于Sink的移动性，网络中的普通节点不能获得移动Sink的位置信息，无法进行数据传输[7-8]。

有研究者提出了根据Sink的移动轨迹预测进行数据传输的路由协议[9-11]，但该种方法对于Sink轨迹的预测并不适用于实际情况且有移动的局限性[12]。因而，本文提出了一种基于移动Sink的数据查询解决方法，当Sink需要查询其所在区域的传感信息时，首先就近指定一个区域代理节点，然后向该代理节点发送数据查询请求。Sink完成数据查询请求后继续移动，并在之后的移动过程中每隔一段时间记一次足迹节点。随着Sink节点的移动，虽其所标记的足迹节点的坐标连线完整的记录了Sink的移动轨迹，但由于该移动轨迹的随机性而不可避免的会出现路径回路。通过采用LAT算法，可有效解决路径回路的问题。

1 网络模型设计

假设网络中有大量随机部署的传感器节点以及一个或多个移动Sink节点。初始化网络时，每个传感器节点均分配了位置坐标。同时，网络中的节点被划分为以下类型：移动Sink节点，区域代理节点，足迹节点，LAT 节点以及普通节点。其中，区域代理节点和足迹节点均是由Sink节点指定的。

1.1 移动 Sink

网络中的移动Sink节点具有强大的计算能力和存储容量，Sink通过无线的方式和网络中的其他节点交换信息。每个Sink配备有GPS模块，因而可随时获得自身的位置信息。移动Sink节点可收集网络中任何区域的传感信息，当其移动至感兴趣区域时，首先会广播代理请求以指定一个代理节点。

收到广播的传感器节点若不是其他移动Sink的代理节点，则返回一个代理确认消息。Sink从收到的所有代理确认消息中选取距离自身当前位置最近的节点作为该区域的区域代理节点，然后向这一节点发送数据查询请求包，包括所要收集数据的范围，收集周期以及收集的数据类型。

Sink发送完数据查询请求后即离开，其移动路线具有随机性，并每隔一段时间记录一次足迹。代理节点只负责收集数据，并不追踪Sink的位置，因而数据的收集请求是由Sink主动发起的。

1.2 LAT 节点

定义1 LAT 节点是Sink通过LAT协议判断后不在路径回路上的足迹节点。

LAT 节点是足迹节点的子集，规定Sink最先记录的两个足迹节点直接标记为LAT节点。从第3个足迹节点开始，Sink每次记录过足迹节点后，就会根据LAT协议判断上一个足迹节点是否在回路上，若不在回路上，则认为该节点为LAT 节点；若该节点经判断在回路上，则认为其不是LAT节点，并继续判断上一个已认证过的LAT 节点是否在回路上，若该LAT节点也在回路上，则认为其不再是LAT节点，由此递归判断上一个LAT节点直到某个LAT节点不在回路上或只剩下区域节点仍为LAT节点。

2 协议设计

2.1 LAT节点的判断

为了能清楚描述LAT协议的工作机制，在此定义LAT角，并通过比较LAT角来判断一个节点是否处于回路上。

定义2 LAT 角是所判断节点与区域代理节点所在连线和所判断节点与Sink当前位置所在连线形成的≤180°的夹角，图1中∠1。

如图2所示，D节点是Sink的当前位置，C是当前的带判定节点也是上一个记录的足迹节点，节点B是上一个已判定为LAT节点的节点，其中，∠1是判定节点B时的LAT角，∠2是节点C的LAT角。通过比较∠1和∠2的大小可判断节点C是否在回路上。显然，若∠1<∠2，则说明Sink的移动并未产生明显的回路。此时，节点C成为LAT节点；若∠1>∠2，则说明Sink产生了明显的回路，则节点C不能成为LAT节点，且要继续判断节点B是否依然是LAT节点。

图1 LAT 角示意图

图2 移动路线为非回路时LAT角的比较

图3 移动路线为回路时LAT 角的比较

2.2 Sink发送数据收集请求

当Sink需要收集数据时，停止移动，发出数据收集请求，并将此时所有的LAT节点添加到数据包中作为数据包的传输路径。由于在选取LAT节点时筛选掉了一部分足迹节点，因而两个相邻的LAT节点间距可能超过节点的通信范围。在此，采用定向泛洪的方法可解决这一问题。

定向泛洪对节点转发数据的方向进行限制，不允许数据自由地向四面八方扩散[11]。节点收到定向泛洪数据包时，通过判断自身是否在泛洪限制的角度范围来决定是否转发该数据包，这样不但可快速找到目标节点，还可大量减少网络中重复消息的数量。

当数据收集请求到达区域代理节点后，区域代理节点将已采集好的数据生成数据包并将数据收集请求的传播路径反转作为数据包传递给Sink的路径。由此，数据包便可避免通过泛洪找中继节点。一旦数据包到达Sink节点，这次传输就结束了，Sink继续移动准备下一次收集。

3 仿真实验

3.1 实验背景

为Sink设计了4种不同的路线模型，如图4所示。图4(a)为波浪形曲线，用于检测LAT协议对震荡型路线的优化效率；图4(b)为线性，即Sink一直在向远离代理节点的方向移动，此时的情况最为简单，数据只需沿着移动Sink记录的足迹s节点传输即可到达Sink；图4(c)为当路线中出现闭合回路时的情形，该种情况下Sink移动一段时间后回到了原来的位置，这种情况也是LAT 算法效率最高的情况；图4(d)描述的是Sink的路线为随机时的图形，次时的路线是图4 (a)～ 图4 (c)是3种路线的组合，随机路线是最符合实际情况的路线模型。

图4 4种路线模型

3.2 节点密度对路径平均长度的影响

网络的大小设置为500 m×500 m，并依次在网络中部署11×11个节点到20×20个节点，节点的通信半径为60 m，得到如图5所示的趋势图，其中横坐标为网络中的节点个数，纵坐标为相应规模下数据传输的平均路径长度。

由图5可看出，随着网络密度的变大，圆形和线性模型中的平均路径长度均未发生变化，圆形路线下平均路径长度最短，因Sink在移动一段时间后回到了原点，所以其只有两个LAT 节点，且LAT 节点之间的距离小于节点的通信半径，因此圆形模型下的平均路径长度最短；线性模型下的平均路径长度是最多的，这是因Sink沿直线行走，并未产生任何的回路，因而其所记录的所有足迹节点均为LAT节点，也即最终的数据传输路径；随着网络密度的增加，波浪形曲线和随机模型下的曲线平均路径长度并未单一的增加或减少，这是因节点的增加导致节点间距的变化，从而影响LAT节点间泛洪时的中继节点的个数，最终导致路径长度的变化。

由图5可看出，随机路线下LAT协议的性能较好，但在文献[10]所提的算法中，随机路线下算法性能却较差，这是因文献[10]的算法是基于预测的，而随机的路线又难以预测，因而表现不佳。

3.3 通信半径对平均路径长度的影响

图6所示为调整节点的通信半径对平均路径长度的影响。由图中可看出，圆形模型起先路径中有3个节点，通信半径增至40 m后下降为2个节点，这可能是因Sink的起始位置间的距离>35 m且<40 m，使得半径增加后两个节点在通信半径内从而避免了泛洪。波浪模型和随机模型由于通信半径的增加导致泛洪的减少从而减少总的路径长度，但显然通信半径的增加对线性模型并没有任何作用，因线性中并未用到泛洪。

3.4 对网络总能耗的影响

图7为随着通信半径的增加，网络整体能耗的变化趋势，对于线性模型和圆形模型而言，网络总能耗随着通信半径的增大而快速增加。但对于波浪和随机模型，由于通信范围变化和路径长度变化对网络能耗的双重影响，故本图中在路径长度不变时，能耗是增加的，而一旦路径长度降低(通信半径为40 m，55 m，75 m时)，网络能耗随之减少。根据图7，当通信半径设为40 m时，网络的整体能耗最小。

图6 改变节点通信半径对平均路径长度的影响

图7 改变通信半径对网络中总能耗的影响

4 结束语

本文提出了LAT协议，一种能有效避免回路追踪Sink的路由协议。LAT通过Sink移动时的路线弯曲角度的变化，筛选出一条没有回路的从代理节点到移动Sink节点的数据传输路径。

实验结果表明，LAT协议可显著减少传输路径的平均长度，并使网络的能耗大幅降低，从而延长网络的生命周期，通过改变网络的规模，节点的通信半径，Sink的移动路线模型等参数来观察网络性能的变化，以此判断LAT协议在何种情况下能发挥出自身的优势。结果表明，当Sink的移动路线存在闭合回路时，可发挥最大的优势，且LAT协议在随机路线模型下的表现也较为优秀。因此，LAT协议的提出对于数据收集系统的发展和深入研究具有重要意义。之后，还将进一步研究区域代理节点，将其收集到的数据进行融合处理，以减少其在数据传输过程中消耗的能量。

[1] Haiyun L,Fan Y,Jerry C,et al. TTDD: Two-tier data dissemination in large-scale wireless sensor networks[J]. Wireless Networks , 2005,11(1-2):161-175.

[2] Naveen K P,Anurag Kumar.Relay selection for geographical forwarding in sleep-wake cycling wireless sensor networks[J].IEEE Transactions on Mobile Computing,2013,11(3): 475-488.

[3] Shuai Gao, Sajal K Das.Efficient data collection in wireless sensor networks with path-constrained mobile Sinks[J]. IEEE Transactions on Mobile Computing, 2011,10(4): 592-608.

[4] Yun Youngsang,Xia Ye. Maximizing the lifetime of wireless sensor networks with mobile Sink in delay-tolerant applications[J].IEEE Transactions on Mobile Computing, 2010,9(9): 1308-1318.

[5] Liu Xingcheng,Ma Zaili.Query processing in multi-user scenario for wireless sensor networks[J].IEEE Sensors Journal,2011,11(3): 2533-2541.

[6] Li Zhenjiang,Liu Yunhao.Exploiting ubiquitous data collection for mobile users in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2013,24(2): 312-326.

[7] 魏鹏,路赞赞.无线传感器网络分布式多传感器目标检测[J].电子科技,2014,27(3): 143-146.

[8] 刘睿琼,齐小刚,孙正海.基于节点位置的无线传感器网络分簇路由协议[J].电子科技,2013,26(3):130-133.

[9] Liu Xinxin,Zhao Han.Sink trail:a proactive data reporting protocol for wireless sensor networks[J].IEEE Transactions on Computers, 2013,62(1): 151-161.

[10] Wu Xiuchao,Kenneth N Brown. Analysis of smartphone user mobility traces for opportunistic data collection in wireless sensor networks[J].Pervasive and Mobile Computing, 2013,9(6):881-891.

[11] Saim Ghafoor,Mubashir Husain Rehmani. An efficient trajectory design for mobile Sink in a wireless sensor network[J].Computers and Electrical Engineering, 2013,40(7):2089-2100.

[12] Hyung June Lee,Martin Wicke.Data stashing: energy-efficient information delivery to mobile Sinks through trajectory prediction[C].Stockholm: IPSN, 2010.

[13] Intanagonwiwat C,Govindan R,Estrin D. Directed diffusion:A scalable and robust communication paradigm for sensor networks[C].Egpt:Proceedings of the 6th Annual International Conference on Mobile Computing And Networking,2000.

[14] 张智超.基于不均等分层分簇的无线传感器网络协议[J].电子科技,2015,28(3): 83-86.

A loop Avoidance Tracking Protocol for Data Query in WSNs with Mobile Sink

XU Huifen, WU Chunxue, YANG Guisong

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology,Shanghai 200093, China)

Wireless sensor networks are usually used to collect data from large-scale networks. In order to reduce the energy consumption, mobile Sink is often used to collect the sensing data. In this paper, we propose a loop avoidance tracking (LAT) protocol for data query in WSNs with mobile Sinks. In this protocol, the Sink node can avoid the node in the loops by comparing the changes of angles but reserve the nodes which are not on a loop, and thus the data will be transferred to the Sink on a shorter routing path. The simulation results demonstrate that the proposed protocol improves the query efficient and offers satisfactory performance in prolonging the network lifetime.

mobile Sink; data query; LAT protocol; loop avoidance

2016- 01- 17

上海智能家居大规模物联共性技术工程中心资助项目(GCZX14014)

徐慧芬(1991-)，女，硕士研究生。研究方向：无线传感器网络。邬春学(1964-)，男，博士，教授。研究方向：嵌入式与移动计算，无线传感器网络。杨桂松(1982-)，男，博士，讲师。研究方向：物联网与传感网，机会网络。

10.16180/j.cnki.issn1007-7820.2016.11.040

TN926

A

1007-7820(2016)11-142-04