无线传感器网络中节点部署算法研究综述*

郭秀明，周国民，樊景超

(中国农业科学院 农业信息研究所，北京100081)

0 引 言

无线传感器网络(WSNs)是由大量传感器节点通过无线通信技术形成的多跳网络。凭借其分布式处理带来的监测精度高、容错性能好、覆盖区域大、可远程监控等优点，WSNs 已成为国内外研究的热点［1］。

节点部署和覆盖控制是WSNs 应用中的一个基本问题，它在一定程度上决定了网络感知质量、网络应用成本及使用的能耗［2］。在保证一定的服务质量条件下，如何达到网络覆盖范围最大化，提供可靠的监测和目标跟踪服务，网络覆盖是否存在监测和通信盲区，是否需要重新调整传感器节点分布以完成目标监测和信息获取的任务都是WSNs部署所包含的问题。节点部署具体主要解决以下三个问题:1)节点的种类和数目;2) 节点的部署方式;3) 网络的可靠性与自适应性。

已有众多的研究者提出了很多WSNs 部署方法。本文比较分析目前节点部署方法，分别从部署方式、监测目标、网络架构及节点是否移动等多个角度分析节点部署方法的应用现状。最后，给出了WSNs 部署算法的应用关键点与未来发展趋势。

1 从部署方式上划分

WSNs 的节点部署方式随着应用场景的不同可划分为随机部署和手工部署。在一些环境恶劣的人类很难进入的环境，如，战场、原始森林等，须通过飞机将节点散播到目标区域，节点通过自组网监测信息。但在人类友好的环境，如工厂车间、农田等，人类方便出入和控制，手工部署能精确地放置节点的位置，根据预先的规划部署使用最少的节点实现感兴趣信息的采集，节省成本，延长网络生存周期。

随机部署方式通过飞机抛洒大量的节点到目标区域。高密度的节点组成的网络存在很大的冗余性，目前较多的方法是将节点分组，每一组节点交替轮回的醒来工作，其他组的节点睡眠以节省能量并延长网络生命周期［3～5］。

在农田、工厂等环境，人类出入方便，手工部署能根据监测需求预先设定信息采集和传输方案，及时解决发现的问题，方便更换电源。Shen X 等人［6］在已有部分部署节点的情况下，提出了一种基于网格扫描的再部署方法，能使用最少的节点实现对要求区域的k覆盖。杨明华［7］针对未知环境下移动传感器网络的部署问题，提出了一种基于虚拟力的精确部署算法。刘卉等人［8］设计了等边三角形、正方形、正六边形规则网格的系统节点部署和系统随机节点部署两种方法，并分别给出了两种方法中三种规则网格单元边长最大值的求解方法。李明［9］针对异构传感器网络节点的高密度部署和监测目标非均匀分布的情况，提出了一种基于模拟退火算法的成本最优部署方法。

2 从节点是否移动划分

从节点的位置在网络应用过程中是否变化上划分可以分为静态部署和动态部署。节点的静态部署方案先于网络启动，部署方案独立于网络的状态并且贯穿于整个网络生命周期。静态部署的大部分协议往往只在初始化时计算一次节点的位置，并没有考虑到节点一旦被定位后发生移动和网络运行的动态变化的情况。张轮［10］通过引入粒子群优化方法，在即有的随机布设的WSNs 中，寻找最佳汇聚节点位置。温俊［11］从提高能量效率和降低剩余能量的角度提出了节点数递减的重叠放置方法和节点密度递减的随机部署方法。

网络状态在一些情况下是变化的，应用层对网络造成的影响也会随时间而变化。当新节点的加入或节点耗尽能量时，可利用的网络资源与网络拓扑会发生变化。动态部署能进一步提高网络性能。与首次部署不同的是，这种重新部署是为了适应变化的网络或基于环境的刺激。动态部署需要周期性地检测网络状态和性能以及分析在节点周围可能发生的事情。户晓玲［12］提出了一种新的基于微粒群模型的移动传感器节点位置优化配置算法，建立节点部署优化模型，利用微粒群算法求解该优化模型，优化过程中的最优解作为节点的最终配置位置。Wang Y C［13］考虑了网络启动前使用最少静态节点的放置问题和网络启动后移动节点的移动布局策略问题，对于后者提出了基于竞争和基于模型两种方法。Senturk I F 等人［14］针对中继节点在非连通的WSNs 中担任信息转发和信息采集角色的数目问题提出了一种中继节点的部署方法，既保证网络连通性，又平衡承担信息转发和信息采集的中继节点的个数，以最小化信息链长度，并满足一种强加的覆盖要求。

3 按网络架构划分

从网络架构上划分，部署方法可以分为同构部署和异构部署。同构网络中，所有的节点都具有采集、存储、路由、及信息传输的功能，且具有相同的感知距离和通信距离，如图1(a)所示。WSNs 在应用中不仅仅要求能采集到感兴趣的信息，同时节点又必须是连通的，以便采集的信息能传输回汇聚节点。所以，WSNs 部署既要考虑到信息的覆盖和感知，又要考虑到网络连通问题。Zhang H 等人［15］证实，若节点的传输距离大于或等于节点覆盖距离的2 倍，则只要网络是全覆盖的，则网络就是连通的。Bai X 等人［16］提出了一组优化的WSNs 节点部署模型，尤其考虑了节点覆盖距离远小于节点通信距离的情况下。蒋丽萍等人［17］提出了一种分布式k 重覆盖算法，算法采用了感知概率模型，依据节点感知能力的强弱，根据能量大小竞选找出k 组不相交工作节点集，保证监测区域中每一点被k 重覆盖。

为了延长网络生命周期或者最小化传输延迟，一些部署设计为节点定义了不同的角色。如图1(b)所示。权建国等人［18］将节点划分为两类:负责信息感知功能的普通节点和具有较长通信距离负责传输数据的超级节点。Wang C F 等人［19］针对移动汇聚节点的定位问题，提出了一种能量感知的汇聚节点重定位算法，根据感知节点的剩余能量自动调整节点的传输距离和汇聚节点的重定位策略。

图1 同构网络和异构网络示意图Fig 1 Diagram of an isomorphic WSNs and a heterogeneous WSNs

4 从监测目标划分

从监测对象划分，主要可划分为区域监测、目标监测、边缘监测等。区域覆盖的目的是使所监测的区域内所有的点都至少被一个传感器节点覆盖，即整个区域面积都要被感知，如图2(a)所示。He X 等人［20］针对在高密度的节点如何从中选取其子集以实现对整个区域覆盖的问题提出了一种节点划分的方法，并给出了所能划分的最大集合数目的方法，Santpal S D［21］提出了两种有效的传感器节点放置方法，旨在使用最少的传感器实现区域覆盖并能给出节点的放置位置。

目标监测实现对若干离散的目标点的监测［22，23］，如图2(b)所示。郭秀明等人［24］提出了一种基于网格扫描的实现目标点覆盖的确定性节点部署算法，同时引入了概率感知模型，把节点能感知到目标点的最小感知概率值作为整体覆盖水平的评价指标。

边界监测和跟踪是指监测和追踪某一事件的边缘和运动趋势(图2(c))。Subhasri D 等人［25］提出了一种动态边界跟踪算法，融合了空间估算和时间估算技术，和定期更新信息方法来跟踪边界的方法相比，本文所提方法无需动态边界的先前知识且节省能量。Hung K S［26］提出了一种分布式的算法寻找最小的覆盖集以实现对边界的覆盖和监测。通过仿真实验证实了算法的优越性。

区域监测、目标点监测、边界监测是WSNs 应用中常见的三种监测目标，WSNs 会针对实际需求实现不同的监测功能，如，事件监测［27］、三维空间的监测［28］、面积较大的目标的部分监测［29］等。

图2 三种不同的监测对象Fig 2 Three different monitoring objects

5 结束语

本文分析目前WSNs 节点部署方法研究现状，并分别从部署方式、监测目标、网络架构及节点是否移动等多个角度对目前的研究现状进行归纳总结。节点部署是WSNs 应用中的技术，决定了WSNs 应用的性能。不同的应用需求决定不同的WSNs 应用部署方案。合理正确的部署是WSNs 可靠高效运行的基础，但还需要合适的通信协议配合。节点的部署方案和通信协议是相互影响和制约的，只有好的部署方案而缺乏适宜的通信协议，WSNs 仍不能有效运行。目前已有众多研究者分别关注部署策略和WSNs 通信协议的研究，而关于两者之间的关系的研究尚不多见。针对特定的应用场景和需求，研究适宜的节点部署方案及其相应的传输协议为WSNs 的标准化应用打下基础。

［1］ Esch J.A survey on topology control in wireless sensor networks:Taxonomy，comparative study，and open issues［C］∥Proceedings of the IEEE，2013:2534－2537.

［2］ 朱海洋，张 合，马少杰，等.无线传感器网络覆盖质量远程监控系统［J］.传感器与微系统，2014，33(12):107－109.

［3］ Tian D，Georganas N D.A coverage－preserving node scheduling scheme for large wireless sensor networks［C］∥Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications，2002:32－41.

［4］ Gupta H，Zhou Z，Das S R，et al.Connected sensor cover:Self－organization of sensor networks for efficient query execution［J］.IEEE/ACM Transactions on Networking，2006，14(1):55－67.

［5］ 蒋 杰，方 力，张鹤颖，等.无线传感器网络最小连通覆盖集问题求解算法［J］.软件学报，2006，17(2):175－184.

［6］ Shen X，Chen J，Sun Y.Grid scan:A simple and effective approach for coverage issue in wireless sensor networks［C］∥IEEE Proceedings of the ICC，2006:480－484.

［7］ 杨明华，曹元大，谭 励，等.一种移动传感器网络精确部署算法［J］.北京理工大学学报，2009，29(1):27－31.

［8］ 刘 卉，孟志军，徐 敏，等.基于规则网格的农田环境监测传感器节点部署方法［J］.农业工程学报，2011，27(8):265－270.

［9］ 李 明，石为人.异构无线传感器网络中基于模拟退火算法的成本最优部署机制［J］.传感技术学报，2010，23(6):855－858.

［10］张 轮，陆 琰，董德存，等.一种无线传感器网络覆盖的粒子群优化方法［J］.同济大学学报:自然科学版，2009，37(2):262－266.

［11］温 俊，窦 强，蒋 杰，等.无线传感器网络中保证覆盖的最少节点部署［J］.国防科技大学学报，2009，31(3):76－81.

［12］户晓玲，曾建潮.基于微粒群模型的移动传感器网络部署研究［J］.计算机技术与发展，2009，19(10):81－88.

［13］Wang Y C，Tseng Y C.Distributed deployment schemes for mobile wireless sensor networks to ensure multilevel coverage［J］.IEEE Transactions on Parallel and Distributed Systems，2008，19(9):1280－1294.

［14］Senturk I F，Akkaya K.Energy and coverage trade－offs in deploying a mix of mobile and stationary relays for disjoint wireless sensor networks［C］∥2013 IEEE Global Communications Conference(GLOBECOM)，2013:249－254.

［15］Zhang H，Hou J C.Maintaining sensing coverage and connectivity in large sensor networks［J］.Ad Hoc Wireless Sensor Networks，2005(1):89－124.

［16］Bai X，Yun Z，Xuan D，et al.Pattern mutation in wireless sensor deployment［C］∥IEEE Proceedings INFOCOM，2010:1－9.

［17］蒋丽萍，王良民，熊书明，等.基于感知概率的无线传感器网络k 重覆盖算法［J］.计算机应用研究，2009，26(9):3484－3489.

［18］权建国，王国军，邢萧飞.无线传感器网络中基于异构节点的覆盖控制算法［J］.传感技术学报，2010，23(6):863－867.

［19］Wang C F，Shih J D，Pan B H，et al.A network lifetime enhancement method for sink relocation and its analysis in wireless sensor networks［J］.IEEE Sensors Journal，2014，14(6):1932 －1943.

［20］He X，Yang H，Gui X.The maximum coverage set calculated algorithm for WSNs area coverage［J］.Journal of Networks，2010，5(6):650－657.

［21］Santpal S D，Krishnendu C.Sensor pacement for effective coverage and surveillance in distributed sensor networks［C］∥Proceedings of IEEE Wireless Communications and Networking Conference，2003:1609－1614.

［22］Mohammad A J，Navid B，Mohammad E，et al.An energy－efficient algorithm for connected target coverage problem in wireless sensor networks［C］∥IEEE International Conference on Computer Science and Information Technology(ICCSIT)，2010:249－254.

［23］何 欣，桂小林，安 健.面向目标覆盖的无线传感器网络确定性部署方法［J］.西安交通大学学报，2010，44(6):6－15.

［24］郭秀明，赵春江，杨信廷，等.基于网格扫描的实现目标点覆盖的确定性传感器节点部署方法［J］.传感技术学报，2012，25(1):104－109.

［25］Subhasri D，Krithi R.Tracking dynamic boundaries using sensor networks［J］.IEEE Transactions on Parallel and Distributed Systems，2011，22(10):1766－1774.

［26］Hung K S，Lui K S.On perimeter coverage in wireless sensor networks［J］.IEEE Transactions on Wireless Communications，2010，9(7):2156－2164.

［27］石为人，杨 斌，许 磊，等.一种事件驱动型无线传感器网络目标追踪算法的研究［J］.传感技术学报，2010，23(1):144－148.

［28］Zhang C，Bai X，Teng J，et al.Constructing low－connectivity and full－coverage three dimensional sensor networks［J］.IEEE Journal on Selected Areas in Communications，2010，28(7):984－992.

［29］Li Y，Vu C，Ai C，et al.Transforming complete coverage algorithms to partial coverage algorithms for wireless sensor networks［J］.IEEE Transactions on Parallel and Distributed Systems，2011，22(4):695－702.