Com prehensive Study on the Problem of Mobile Sink Path Planning and the Cluster Head Node Selecting in WSN Data Collection

HUIXiaowei，LIU Yanmei

(School of Electronic and Information Engineering，Liaoning Technical University，Huludao Liaoning，125105，China)

Com prehensive Study on the Problem of Mobile Sink Path Planning and the Cluster Head Node Selecting in WSN Data Collection

HUIXiaowei*，LIU Yanmei

(School of Electronic and Information Engineering，Liaoning Technical University，Huludao Liaoning，125105，China)

For large－scale wireless sensor networks viamulti－hop transmission for data collection，and cause for the energy hole problem，this paper presents amobile Sink based rendevous data gethering(MSRDG)algorithm.The algorithm is based on graph theory tomeet the conditions of delay.Considering the common nodes to the cluster head node routing and mobile Sink traversing path selection problem，a mobile trajectory is composed through a cluster head nodes asmuch as possible.Through the NS－2 simulation software to evaluate performance of the algorithm，results show that the proposed algorithm can reducemultiple hops of the data transfer and the energy consumption of wireless sensor network node，and prolong the life of the network.

WSN;rendevous;mobile Sink;path planning;MSRDG algorithm

无线传感器网络(WSNS)作为物联网的底层技术近年来备受研究者的关注［1－2］。WSN由安置在监测区域中的计算、存储和能量都有限的传感器节点构成，节点将采集的数据以无线多跳的通信方式传输给汇聚节点(Sink)。由于靠近Sink的节点要转发大量的数据容易导致节点过早耗尽能量而失效，即能量空洞现象，降低网络的存活时间。因此，如何有效均衡利用有限能量资源延长网络寿命［3］是WSNS的一个关键问题。

近来的研究表明，在WSN中运用移动Sink进行数据收集［4－5］，数据的多跳传输可以大幅度减少，由于Sink的移动其周围的节点也在不断变化，均衡了节点能量的消耗，防止能量空洞现象的产生。由于Sink节点可以和网内节点以单跳模式进行通信，在一定程度上避免了消息丢失情况的发生。文献［6］让移动Sink沿着固定轨道匀速运行并从相遇的传感器节点收集数据，从而静止节点可预测移动Sink的到达时间并在唤醒和睡眠状态之间高效转换，进而节省能耗。但由于轨道固定，靠近轨道的节点也会过早耗尽能量。文献［7－8］提出了一种基于分区的调度算法PBS(Partition Based Scheduling Algorithm)来调度Sink移动以确保每一个分区内的传感器节点缓冲区不会溢出。不过不适用规模较大的网络。文献［9－10］提出了基于标签覆盖的算法寻找能覆盖所有节点传输范围且长度最短的路径。缺点是时延较大。文献［11］在已取得的技术基础之上，提出一种基于移动汇点的数据收集协议(EEMS)，首先利用分簇技术生成通讯半径相等的簇，由剩余能量相对充足的节点构成簇首，形成通讯骨干网。之后对骨干网采用一种适合资源有限的无线网络的分布式MST算法获得其最小生成树，再借助解决TSP问题的思想，构建一条路径最短的移动轨迹。此方法有效缓解了热点问题的发生。但此方法把移动路径规划和簇头节点选取问题分开考虑，且没有考虑普通节点到簇头节点的路由问题。如果在规模较大的网络，移动路径过长，不能达到时延性要求;如果增大分簇半径R虽可以减小移动路径，但网络总跳数随之增加，开销加大，不能达到最优的效果。

综合利用分簇思想和移动汇点技术，本文针对规模较大且具有时延容忍特性的无线传感器网络提出一种基于移动Sink的簇头节点数据收集MSRDG (Mobile Sink based Rendevous Data Gethering)算法，该算法联合考虑了簇头节点的选取、普通节点到簇头节点的路由和移动Sink路径的启发式算法。算法首先选出最小连通支配集节点作为待选簇头节点，根据待选簇头节点和时延性要求下的轨迹长度L，通过本算法和借助解决TSP问题的思想获得最优的簇头节点集和Sink的移动轨迹。该算法在保证数据时延性要求的条件下，有效的选取尽可能多的簇头节点，减少了传感器节点到汇聚节点的数据传输，从而达到节省能量并延长网络寿命的目的。移动轨迹上Sink节点和簇头节点以单跳方式通信，避免了信道竞争和冲突。

1 系统模型

1.1 网络模型的假设

考虑传感器节点随机地部署在监测区域内，首先对传感器节点和网络模型进行假定:

(1)传感器节点布设后不能移动，具有相同的通信半径R，周期性的产生监测信息，初始能量相同，计算和存储功能都有限，已知自己的地理位置信息。

(2)移动Sink节点具有可控制的移动性。其能量、计算能力、存储容量和传输距离等不受限制。

(3)Sink节点和簇头节点在通信范围内进行数据传输，信息具有完整性且传输时允许有一定的时延T。

1.2 引入图论原理对网络进行描述

本文应用图论对无线传感器网络进行描述。在不考虑空间差异的情况下，可以将无线传感器网络的节点抽象成图的顶点，把网络节点之间的通信关系抽象成图中顶点与顶点之间的连边。

(1)无线传感器网络拓扑图G=(V，E)，其中，V代表WSN各节点的位置，E是边的集合，代表WSN的拓扑，当且仅当传感器节点vi和vj在彼此的通信范围内时，(vi，vj)⊂E。

(2)当系统可容忍的最大延迟时间为T时，移动Sink的最大遍历路径长度为L=m·T其中m为Sink的移动速度。

(3)待选簇头节点集U=(u1，u2…uu)，其中U⊂V，通过迭代计算，得到簇头节点集S=(v'0，v'1，…，v's)其中S⊂U。

(4)普通节点到离自己最近的簇头节点的最短路由的跳数为h(v，v')其中v⊂V，v'⊂S。

(5)MSRDG算法的目的是找到一条访问到簇头节点集中每一个节点的最短遍历路径F(F＜L)，且使每一个普通节点到达路径F的路由向量最小。

2 系统设计

2.1 待选簇头节点集的选取

用图论中的最小连通支配集［12］S作为待选簇头节点集。其中S满足S中的节点是相互连通的且个数最少，同时余下的节点与其中的节点至少有一个是相邻的条件。

2.2 待选簇头节点集的路径规划问题

当待选簇头节点确定后，Sink节点的移动路径问题可看作是旅行货商TSP(Traveling Salesman Problem)问题。通常选用蚁群算法［13］解决此类问题。本文蚁群算法中蚂蚁选择下一个位置的概率公式如(1):

ij距离，nij为到节点j后能收集到信息的节点个数;σ是信息素启发因子，ζ为期望启发式因子;allowedk为第k只蚂蚁下一步允许访问的节点位置即S减去Sink已经访问过的节点。信息量调整方式采用

其中ρ表示信息挥发系数，Δτij(t)为本次循环路径(i，j)上的信息素增量。信息素更新原则为:

其中Q表示信息素强度，在一定程度上影响算法的收敛速度，Lk为第k只蚂蚁在本次循环中所走路径的总长度。上述蚂蚁群所寻的路径即为移动Sink所走的最优路径。

2.3 普通节点到簇头节点的路由问题

本文中所有传感器节点位置是已知且是均匀分布的，普通节点到离自己最近的簇头节点的路由算法采用贪婪转发模式的GPSR［14］(Greedy Perimeter Stateless Routing for Wireless Networks)路由算法。普通节点发送的数据包中封装离自己最近的簇头节点的位置信息，选择邻居节点中距离簇头节点最近的节点作为下一跳路由转发节点，后面接收到数据包的节点不断重复这一过程，直到数据包到达簇头节点。每个普通节点的初始跳数设为0，当传播到一个传感器节点时，由该节点将跳数值加1，到达簇头节点时，跳数值为普通节点到达簇头节点的跳数。所有普通节点到达离自己最近的簇头节点的跳数之和为该网络的传输总跳数。

2.4 待选簇头节点衡量值的设定

移动Sink节点在遍历路径长度为L的限定下，访问的节点越多则普通节点到簇头节点的路由代价越小，所以要使簇头节点尽可能多。

选定待选簇头节点后，还需要根据每个待选簇头节点对结果影响程度移除部分对结果影响较小的待选簇头节点，以确保在限定的最大遍历长度L的条件下目标函数是最优的。当移除待选簇头节点集中的某个节点时，必然使得以此节点为簇头的普通节点要寻求其他离它路径最短的待选节点作为新的簇头节点，以便使数据通过最短路径传输到最近的簇头节点存储，并等待移动Sink的访问。

综合考虑簇头节点的选取、遍历路径规划以及普通节点到簇头节点路由，对待选簇头节点的衡量值做如下定义，如式(4):

其中U为选出的待选簇头节点集，x为其中的一个节点，w(x)代表节点x的衡量值，TSP(U)为遍历待选簇头节点集的最短路径长度，h(v，u)表示舍弃节点x后整个网络中从普通节点到待选簇头节点的传输总跳数，T(x)为节点x的剩余能量，α和β两个参数分别反映舍弃x后新增加的路由跳数和x节点的剩余能量在簇头选择过程中的相对重要性，α +β=1。在上式中，分子表示当从待选簇头节点集中移除x这个节点后，剩余节点的能量一定时，整个网络新增加的普通节点到簇头节点的路由代价，而分母表示除x这个节点后能节省的遍历路径长度。所以w(x)的值越小，表明x节点的移除不但使得普通节点到簇头节点的路由代价增加不大，而且使得移动Sink的遍历路径相比移除x节点前更短，也就是说节点x的移除能以尽可能少的路由代价尽快达到遍历路径长度L的限制，因此，每次应当选取衡量值最小的节点移除。

2.5 MSRDG算法的具体实现过程:

算法的输入为时延性限制的移动轨迹长度条件L、传感器节点的位置信息P和传感器通信半径R，最终输出为簇头节点集以及对簇头节点集的遍历路径F。

(1)移动Sink节点根据输入的传感器节点位置和通信半径R，生成网络拓扑图G(V，E);

(2)使用最小连通支配集算法得到G(V，E)的最小联通支配集作为待选簇头节点集S;

(3)计算待选簇头节点集中每个节点的衡量值以及利用蚁群算法得到最短遍历路径长度l';

(4)判断是否l'≤L，如果是退出循环，如果不是则找到待选簇头节点集中衡量值最小的节点并舍弃该节点，回到步骤(3)进入下一次循环直至退出循环。

3 仿真与分析

本节采用NS－2仿真工具对MSRDG算法的性能进行评价。选择簇头节点个数、网络传输总跳数和网络寿命(网络中第一个节点能量耗尽时，网络已经运行的轮数)作为算法评估指标。在仿真实验中涉及的参数取值为:ρ=0.1，σ=1，ζ=2，Q=1，α =0.8。WSNS节点随机分布在400 m×400 m的区域内，传感器节点数量的变化区域为(100，400)，通信半径为50 m，网络允许的最大时延为20 min，移动Sink以速度m(0.5，1.5)匀速移动，则可得L的取值范围为600 m～1 800 m。

将本算法与文献［11］中同样引入移动汇点的EEMS协议进行比较。仿真结果如图所示，图1给出了在不同的节点个数和移动速度的情况下，采用MSRDG算法得到的簇头节点个数，可以看出簇头的节点个数随着节点个数的增多稍有增加，显示了传感器网络的可扩展性。同时随着移动速度的增加获得的簇头节点个数也增加。

图1 Sink节点在不同移动速度下簇头节点个数对比

图2 中，当节点数目从100增加到400时，图2(a)中，两种算法的传输总跳数都随节点数目增加而增加。MSRDG算法的传输总跳数总是小于EEMS算法，且节点数目越多，MSRDG算法相比EEMS算法的优势越明显。图2(b)中，可以看到，随着节点数目增加，两种算法的网络寿命都随之降低，且MSRDG算法的网络寿命要长于EEMS算法，但差距是逐渐缩小的。

图2 节点数目从100增加到400时的性能

从图3中可以看出，当移动Sink的路径长度从800 m增加到1 600 m时，图3(a)中，两种算法总传输跳数均呈现递减的趋势，且在1 200 m以前，传输总跳数减少较快，而1 200后减少趋势变慢且两种算法的差距变小，这是因为移动Sink遍历路径长度越长，则传输总跳数就会越少，而MSRDG算法的优势难以显现。图3(b)中，随着移动Sink的路径长度L的增加，两种算法的网络寿命都随之延长，且MSRDG算法的网络寿命平均比EEMS算法的网络寿命长5轮左右。

图3 移动Sink的路径长度从800m增加到1600m时的性能

4 结论

本文针对规模较大、数据简单且允许有一定时延的无线传感器网络，提出了一种基于移动Sink的无线传感器网络数据收集节能算法MSRDG。仿真结果表明，MSRDG算法能在保证时延性的条件下尽可能多的有效地选取出簇头节点，以尽可能地减少网络的传输跳数，从而能够节省网络能耗并延长网络寿命。同时Sink节点与轨道上的簇头节点以单跳的方式进行数据传输，提高了通信质量且具有网络可扩展性。

［1］史永彬，叶湘滨，刘培亮.无线传感器网络技术研究现状［J］.国外电子测量技术，2005(11):19－23.

［2］陈靖，吴景东.基于ZigBee协议的无线传感器网络技术的分析和应用［J］.工业控制计算机.2010(11):30－32.

［3］李虹.无线传感器网络中节能相关若干关键问题研究［D］.中国科学技术大学，2007.

［4］张蕾，张堃.无线传感器网络中一种基于移动Sink的数据收集算法［J］.传感技术学报，2012，25(5):673－677.

［5］郜帅，张宏科.时延受限传感器网络移动Sink路径选择方法研究［J］.电子学报，2011(4):742－747.

［6］Chakrabarti Arnab，Sabharwal Ashutosh，Aazhang Behnaam.Using Predictable Observer Mobility for Power Efficient Design of Sensor Networks［J］.Information Processing in Sensor Networks，Apr.2003:129－145.

［7］Yaoyao Gu，Doruk Bozdag.Partitioning Based Mobile Element Scheduling in Wireless Sensor Networks［C］//Proc.Second Annual IEEE Conference on Sensor and AD HOC Communications and Networks，2005:386－395.

［8］Yaoyao Gu，Bozdag D，Ekici E.Mobile Element Based Differentiated Message Delivery in Wireless Sensor Networks［J］.International Symposium on a World of Wireless，Mobile and Multimedia Networks，2006:83－92.

［9］Sugihara R，Gupta R K.Scheduling under Location and Time Constraints for Data Collection in Sensor Networks［C］//Proceedings of the 28th IEEE Real－Time Systems Symposium(RTSS)Work in Progress Session，2007:9－11.

［10］Sugihara R，Gupta R K.Improving the Data Delivery Latency in Sensor Networks with Controlled Mobility［C］//Proceedings of the 4th IEEE International Conference on Distributed Computing in Sensor Systems(DCOSS)，Volume 5067 of LNCS，2008:386－399.

［11］汪林云，刘文军.无线传感器网络中带有移动汇点的能量高效的数据收集协议［J］.传感技术学报，2012，25(5):678－682.

［12］Wu J，Li H.On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks［C］//Proc of the Third InternationalWorkshop on Discrete Algorithms and Methods for Mobile Computing and Communications，1999:7－14.

［13］王佳.WSN中基于改进蚁群算法的移动Agent路径规划［J］.传感技术学报，2011，24(4):609－613.

［14］王丽娟，梁海涛，秦建敏，等.贪婪周边无状态路由转发算法GPSR的分析及改进［J］.太原理工大学学报，2012，43(5): 587－590.

惠晓威(1958－)，男，辽宁省沈阳市人，满族，教授，硕士，研究方向为现代通信、图像识别、信息处理;

刘彦每(1989－)，女，北京人，汉族，硕士研究生，主要研究方向现代通信、图像识别、信息处理。

WSN数据收集中移动Sink的路径规划和簇头节点选取问题的综合研究

惠晓威*，刘彦每

(辽宁工程技术大学电子与信息工程学院，辽宁葫芦岛125105)

针对较大规模的无线传感器网络通过多跳传输进行数据收集而引起的能量空洞问题，提出了一种基于移动Sink的簇头节点数据收集算法(MSRDG)，该算法基于图论原理，在满足时延性的条件下，综合考虑了普通节点到簇头节点路由和移动Sink遍历路经选取的问题，构建了一条通过的簇头节点尽可能多的移动轨迹。通过NS－2仿真软件对算法的性能进行评估，结果显示出该算法能减少数据的多跳传输，降低无线传感器网络节点的能量消耗，延长网络寿命。

无线传感器网络;簇头节点;移动Sink;路径规划;MSRDG算法

TN925.9.3;TP212

A

1004－1699(2014)01－0118－05

2013－10－09修改日期:2013－12－09

C:6150P

10.3969/j.issn.1004－1699.2014.01.022