WSNs断网情况下汇聚点选取与优化研究*

迟百川, 曹江涛, 张 一, 耿立群

(1.辽宁石油化工大学 信息与控制工程学院，辽宁 抚顺 113001； 2.空军航空大学 飞行训练基地二团，黑龙江 哈尔滨 150111)

WSNs断网情况下汇聚点选取与优化研究*

迟百川1, 曹江涛1, 张 一1, 耿立群2

(1.辽宁石油化工大学 信息与控制工程学院，辽宁 抚顺 113001； 2.空军航空大学 飞行训练基地二团，黑龙江 哈尔滨 150111)

无人值守的无线传感器网络(WSNs)在严酷环境中易出现断网情况，数据的传输受到限制，造成网络不可用。利用移动Sink访问汇聚点(CP)收集数据是一种有效的解决方案。但现有的研究中没有明确给出最佳CP的存在区域和CP 的选取对Sink节点移动路径的影响。为此，提出了最佳CP存在区域的划分方法，并确定了该区域大小。在含有100个节点的WSNs上进行仿真验证，结果表明:该划分方法下Sink节点最优移动路径的变化呈单调递减，并最终趋于稳定。

无线传感器网络；移动Sink；区域划分；最优路径

0 引 言

近年来，无线传感器网络(WSNs)的广泛应用引起了研究界和工程机构的高度关注[1]，其最引人注目的是应用在无人值守的严酷环境(如战场监测、边境保护、太空探索等)中，避免生命危险，减少工作成本，并且提供一个完全自动化的数据收集系统。在WSNs的应用中，传感器节点处理能力有限，所以,期望部署的传感器形成一个连通的网络，在执行任务时，相互协调工作，将收集的数据传送到基站；由于传感器节点是电池供电设备，它们面临能源耗尽、设备不工作的风险；另外，恶劣环境和恶意攻击也使节点容易大规模损坏；在这些情况下，网络的通信链路断开，数据传输受到限制。

为恢复网络连通性，Cerpa A等人曾提出布置冗余节点的方案，通过提高节点密度来恢复WSNs连通性并延长网络使用寿命[2]；Abbasi A等人提出重新布置一些节点的方案，其思想是运用DARA算法来恢复WSNs连通性[3]。虽都解决了WSNs连通性问题，但却不适合极端环境下节点的大规模损坏。因此，用剩余节点建立WSNs各集群的连通性显得至关重要。

在WSNs中引入移动Sink[4]可有效的提升网络性能，包括降低能量消耗[5]、延长网络生存时间[6]等。因此，本文采用移动数据收集器(mobile data collector, MDC)作为移动Sink来恢复断开WSNs的连通性。

汇聚点(CP)的选取决定MDC的移动路径。所以，集群中CP可停留的位置不同，MDC的移动路径也会随之发生相应的变化。现有的研究结果中，如文献[7]，将各集群的中心点与选取的单一代表点(representative point, RP)连线，其与传输半径的交点作为单一CP，再进行数据收集。而文献[8]对其进行了改进，首先采用CURE算法[9]将剩余可用节点划分为集群，然后在每个集群中选取2个CP，再对其进行路径规划，从而缩短了MDC的移动距离，减少了能量消耗和网络延迟。虽然都解决了严酷环境中的断网问题，但没有考虑CP的选取对整个移动路径的影响，形成最优路径时最佳CP的存在区域。

为此，本文从以上2个问题入手，在解决极端环境中WSNs不可用的基础上，提出了最佳CP存在区域的划分方法，分析了集群中CP的选取,即CP在集群中可停留的位置对整个移动路径的影响。

1 网络模型与连通性

首先，定义一个由N个静态传感器节点和一个MDC组成的WSNs。通过聚类算法将N个静态节点大致分为n个集群，集群内部节点通过多跳的方式相互通信，集群间通信受阻。每个传感器节点可以通过GPS或其它定位算法知道各自的位置信息，并且MDC的移动方式可控。

设MDC可以从任意集群出发收集数据，并最终回到始发集群，使得MDC的移动路径形成一个回路。用np和nm来表示CP节点的数量和成员节点的数量,即

N=nP+nm.

(1)

将剩余可用节点进行聚类可有效的减少MDC能量的消耗。本文利用模糊C均值(fuzzy C-means, FCM)聚类算法[10]首先将随机分布的节点划分为集群，并且确保集群内部相互通信，然后通过该算法确定集群中心点，为CP的选取做准备。

假设所有传感器具有相同的传输范围“CR”，为寻找CP在集群中可能停留的位置，做如下定义：

定义一：通过FCM聚类算法形成的n个集群S={S1,S2,S3,…,Sn-1,Sn}，各集群的中心点集合C={C1,C2,C3,…,Cn-1,Cn}，令O为中心点集C的中心点。

定义二：令rb为RP，一个集群中存在多个RP，且满足rb与O之间的欧氏距离比该集群中其余点与O之间的欧氏距离短。

然而，上述寻找CP的方法只适合各集群所在位置的连线呈凸边形的情况。如图1 所示，以4个集群S={S1,S2,S3,S4},每个集群选取2个CP为例。

图1 各集群位置呈凸边形时CP的选取方式

当为凹边形时，需要找出具有凹点的集群，如图2所示。运用FCM算法确定该集群的中心点M,然后连接其余集群的CP。从M向与之最近的边作垂线，令垂线与RP传输范围“CR”的交点为该集群CP的可停留位置(具有凹点的集群取一个CP)。

图2 各集群位置呈凹边形时CP的选取方式

实际上，各集群的位置不仅仅呈现凸边形或凹边形，也可能出现更为复杂的网状结构，但网状结构可分解为若干个凸边形和凹边形的情况。为此，本文只专注于集群位置呈凸边形和凹边形的情况。

部署MDC的主要目的是传输数据，通过设置MDC的移动路径来达到这个目的。假设MDC的移动路径“T”是一个最短循环，每个集群至少包含一个CP。寻找“T”路径等同于旅行商问题，被认为是一个NP-Hard问题[11]。本文采用Dijkstra算法[12]，该算法用于计算一个源节点到其它所有节点的最短代价路径。因此，本文的最短路径T可描述为

(2)

1)分别求最短路径T1,T2,…,Tm;

2)T1,T2,…,Tm之间进行比较，选出最优路径

minroute=min{T1,T2,…,Tm}.

(3)

图3所示为全局最优路径模拟图。图中，虚线框代表集群。

图3 全局最优路径模拟图

同样以4个集群，如图4所示，当各集群位置呈凸边形时，其最短路径T可描述为

(4)

图4 各集群位置呈凸边形时最优路径的形成过程

图5 各集群位置呈凹边形时最优路径的形成过程

2 区域划分

为确定最佳CP的可能存在区域，还需要做如下的定义：

定义四：令lxy为以x为圆心，|xy|为半径的圆弧。

定义五：⊙x定义为以x为圆心的圆；⊙xy定义为以x为圆心，|xy|为半径的圆。

由于集群的位置不同，其最佳CP的存在区域也会随之发生变化。为方便区域划分，假设各集群形状呈圆形，且传感器节点的传输范围被认为是一个点，分以下两种情况进行区域划分:

1)当各集群位置呈凸边形时

如图6所示，图中阴影部分即为最佳CP的选取区域。

图6 凸边形时最佳CP存在区域的划分

SAi=

(5)

2)当各集群位置呈凹边形时

这种情况下，首先需要确定各个集群的CP。区域的划分方法及原理与凸边形的情况一致，这里不在进行赘述。图7中阴影部分即为凹边形时最佳CP的可能存在区域。

图7 凹边形时最佳CP存在区域的划分

3 仿真测试与结果

本文运用Matlab_R2012a作为仿真平台进行结果测试。在100m×100m的范围内随机布置100个节点，运用FCM聚类算法将其聚类形成3～8个集群，并且保证其内部正常通信。定义传感器和MDC的传输范围为10m。

在已形成指定聚类数目的前提下，将每个集群中取2个CP(CTCP)的方式与IDM-KMDC[8]进行比较。IDM-KMDC的主要思想是将节点形成指定数目集群后，在每个集群中选择一个CP，然后运用最小生成树算法[13]进行路径规划，以达到MDC移动路径的最小化。通过以下2个性能指标进行比较：

1)移动总长度(totaltourlength,TTL)：因为移动能减少MDC的使用寿命，所以,最小化MDC的移动路径是该方案的一个设计目标。

2)最大移动长度(maximumtourlength,MTL)：反映MDC完成一个最短循环“T”所移动的最大长度“L”。如果“L”长度过大，将会导致数据收集的延迟增加，所以，需要最小化“L”。

如图8所示，为两种方案下MDC的移动总长度，从图中可知，CTCP方案优于IDM-KMDC。在MDC移动速度确定的情况下，能更好地恢复网络的连通性。图9为两种方案下MDC的MTL，可以看出：CTCP在数据收集的延迟上更低，网络的运行速度更快。

图8 不同方案下TTL的比较

图9 两种方案下的MTL

通过两种方案的比较，可以得知，在已形成指定聚类数目的前提下，CTCP能更快的恢复WSNs的连通性，更适合极端环境中无人值守的WSNs网络节点大规模损坏的情况。证明了集群中选择2个CP时，其形成的路径优于单CP的情况。

表1为仿真测试所得到数据。当每个集群取多个CP时，MDC的TTL随着集群中CP数量的单调增加而单调减少，并最终稳定,即，由于集群中CP数量的增加，隐藏的较优路径逐渐被发现，直到形成最优路径，即MDC的TTL达到稳定。同时，可根据具体的集群数目选择合适的CP进行路径规划，可以避免不必要的计算量。其仿真图如图10所示。

表1 不同集群数目下对应不同CP的TTL

图10 TTL的变化规律

4 结束语

本文利用MDC作为移动Sink来解决严酷环境中无人值守的WSNs的断网问题。提出了最佳CP可能存在区域的划分方法，并在此基础上证明了CP停留在集群的不同位置，对整个移动路径的影响。通过仿真测试，验证了所得结论的正确性。

[1] Estrin D,Girod L,Pottie G,et al. Instrument the world with wireless sensor networks[C]∥Proc of the Int’l Conf on Acoustics,Speech,and Signal Processing,Prague,Czech Republic,2001:2033-2036.

[2] Cerpa A,Estrin D. ASCENT:Adaptive self-configuring sensor networks topologies[C]∥Proc of the INFOCOM’02,New York,NY,2004::272-285.

[3] Abbasi A ,Akkaya K,Younis M. A distributed connectivity restoration algorithm in wireless sensor and actor networks[C]∥Proc of IEEE LCN’07,Dublin,Ireland,2007:496-503.

[4] 梁俊斌,邓雨荣,郭丽娟,等. 无线传感网中移动数据收集研究综述[J]. 计算机应用与软件,2013,30(5):25-28.

[5] Jain S,Shah R C,Brunette W,et al. Exploiting mobility for energy efficient data collection in wireless sensor networks[J]. Mobile Networks & Applications,2006,11(3):327-339.

[6] Luo J,Hubaux J P. Joint mobility and routing for lifetime elongation in wireless sensor networks[C]∥Proc of the IEEE Int’l Conf on Computer Communications,Hingham,USA,2005:1735-1746.

[7] Senel F,Younis M. Optimized interconnection of disjoint wireless sensor network segments using K mobile data collectors[C]∥Proc of the IEEE Int’l Conf on Comm (ICC’12),Ottawa,Canada,2012:492-496.

[8] Kalyanasundaram B,Younis M. Using mobile data collectors to federate clusters of disjoint sensor network segments[C]∥Proc of the IEEE Int’l Conf on Comm (ICC’13),Maryland,American,2013:1496-1500.

[9] 赵 妍,赵学民. 基于 CURE 的用户聚类算法研究[J]. 计算机工程与应用,2012,48(11):97-101.

[10] 李 雷,罗红旗,丁亚丽. 一种改进的模糊 C 均值聚类算法[J].计算机技术与发展,2009,19(12):71-73.

[11] 郭靖杨. 旅行商问题概述[J]. 大众科技，2006 (8):229-230.

[12] Deng Y,Chen Y,Zhang Y,et al. Fuzzy dijkstra algorithm for shortest path problem under uncertain environment[J]. Applied Soft Computing,2012,12(3):1231-1237.

[13] 徐建军,沙力妮,张 艳,等. 一种新的最小生成树算法[J]. 电力系统保护与控制,2011,39(14):107-112.

Research on selection and optimization of collection points

in WSNs under condition of broken network*CHI Bai-chuan1, CAO Jiang-tao1, ZHANG Yi1,GENG Li-qun2

(1.School of Information and Control Engineering, Liaoning Shihua University, Fushun 113001, China； 2.Training Base Group 2, Aviation University of Air Force,Harbin 150111, China)

Wireless sensor networks (WSNs) that operates unattended in extreme environmental conditions may off the Internet and data transmission is restricted, which make WSNs unavailable. Use mobile sink visit collection points(CP) and collect datas is an effective solution. However, the existing studies do not give solution of how to select the optimum CP and its impact on moving routes are not given. So, present a partition method to find the area where optimal CP placed and ascertain that area size. Simulation test on WSNs that contains 100 nodes is carried out and its results indicate variation of the optimal moving route of sink node is monotone decreasing until stable by this partition method.

wireless sensor networks(WSNs); mobile sink; regional division; optimal path

10.13873/J.1000—9787(2015)04—0034—04

2014—09—11

辽宁省自然科学基金资助项目(2013020024)；国家自然科学基金资助项目(61203021)

TP 393

A

1000—9787(2015)04—0034—04

迟百川(1990-)，男，满族，辽宁本溪人，硕士研究生，研究方向为无线传感器网络。