无线传感器网络节点部署研究进展*

凡高娟，郭拯危

(1.河南大学计算机与信息工程学院，河南开封475004;2.南京大学江苏省无线传感网高技术研究重点实验室，江苏南京210003)

0 引言

传感器网络节点部署是实现网络应用的一个基本问题［1］，目的是采用感知受限和能量约束的传感器网络建立一个功能强大的系统。在节点部署中，覆盖、连通性、部署代价、生存时间将对网络的有效性和实用性等起决定性作用。另外，传感器节点处理能力和资源都受限。设计者面临建立高可靠性和长持续性的应用需求与资源受限设备的挑战，所以，必须通过有效的节点部署机制。

根据应用需求和部署条件来选择采用何种部署方案［2］。如传感器通常工作在恶劣环境或人类不能到达的区域，节点往往采用随机部署。此时，节点的数目、感知半径和网络的覆盖率之间的某种函数关系，在初期部署时，根据这种函数关系计算所需节点的数目和调节节点的感知范围和通信范围［3］。

目前在传感器节点部署方面进行了很多研究，节点的部署与网络覆盖、连通和能耗等研究相关。本文从静态部署和动态部署2个方面介绍当前节点部署的研究现状。

1 静态部署

静态部署是根据最优的策略来决定节点的位置，节点放置通常在网络启动之前，并且节点的位置在整个网络生存期间不变。依据部署方法、优化对像和节点的角色，对目前存在的静态部署方法进行归类，如图1所示。

1.1 部署方法

无线传感器网络的部署方法与应用密切相关，根据应用环境的不同，无线传感器网络的部署方法可以分为两类:确定性部署和随机部署两类［4］。

图1 节点静态部署分类Fig 1 Classification of node’s static deployment

确定性部署通常应用于网络的状态相对固定或应用环境、节点位置信息、节点的密度等已知情况下。确定性部署通过对问题进行数学抽象，成为静态优化问题或线性规划问题，如在文献［5］中，得出节点部署达到覆盖所需要的最少节点个数和给出节点相应的位置。在文献［6］中，利用六形网格来部署节点，达到最大的连通覆盖。确定性部署方法简单，但在实际的应用中，尤其是大规模、无人监守的恶劣环境中，随机部署显得更具有优势。当监测区域环境恶劣或存在危险时，随机部署是唯一的选择。此时，通过飞机、炮弹等载体把节点随机抛撒在监测区域内，节点到达地面以后自组成网。这种随机性主要体现在2个方面:一是节点落在监测区域内的位置具有随机性;二是受环境的影响，落在区域内的节点状态具有一定的随机性，某些节点可能会在坠落过程中损坏而失效。因而，在随机部署策略下，为取得较好的覆盖性能，必须投入大量的冗余节点以达到所需要的节点密度。随机部署方式是一种较为经济适用的方法，但不能保证整个监测区域完全覆盖，一般适用于对覆盖要求不太严格的应用环境中。文献［7］分析了渐近性分析方法在实际部署中带来的问题。

在确定性部署与随机部署的选择上，文献［8］指出，在进行节点部署时，分析需要用多少个节点来达到一定的覆盖度，维护k覆盖所需要的节点个数依赖于监测区域的面积和部署策略，作者分析了达到k覆盖在泊松到达部署、均匀部署和格部署3种部署策略下所需要的节点密度，得出格部署在大多数情况下比随机部署需要更少的节点。

1.2 优化对象

根据优化对象对部署进行分类，可以分为基于覆盖、基于网络连通和能量有效性部署三类。

最大化监测区域的覆盖受到越来越多研究者的重视。文献［9］提出故障容错的k连通部署方案，分析用最少的额外节点使网络为k连通;并对于给定的k，可以求得部署的节点个数，用贪婪和分布式方法实现该算法。

文献［10］通过2种基本的部署方法:Square-grid和Hex-grid 2种方法，提出一种自低向上的方法评价网络的生存时间，把单个节点的生存时间和网络的生存时间作为随机变量来模拟，推导概率密度函数。文献［11］分析高斯部署下节点的覆盖与生存时间之间的关系，但没有考虑部署中存在的边界问题。

1.3 节点角色

节点的部署位置不仅影响节点的覆盖与连通，更影响网络的生存时间。一些学者利用不同类型的节点来优化网络性能(增加网络生存时间、最小化数据包延迟等)。节点在网络中可以充当感知节点、中间节点、基站节点或簇头节点。当节点充当不同的角色时，网络的性能参数依赖于节点在网络中的角色。文献［12］通过在室内部署中间节点达到网络的连通性与网络生存时间延长的目的。

2 动态部署

节点动态部署可以追溯到机器人的部署，国内外已有研究机构进行了相关研究，基于动态部署的方式可以分为如下3种，如图2所示。

图2 动态部署分类Fig 2 Classification of dynamic deployment

2.1 增量式节点部署算法

文献［13］提出一种增量式节点部署方法，通过逐个部署节点，利用已经部署的节点计算出下一个节点应该部署的位置，达到网络的覆盖面积最大。该算法需要每个节点都有测距和定位模块，适用于监测区域环境未知的情况。优点是利用最少的节点覆盖监测区域;缺点是部署时间长，部署每一个节点可能需要移动多个节点。

2.2 基于人工势场(或虚拟力)的算法

该类算法把人工势场(或虚拟力)用于移动节点的自展开问题，把网络中的每个节点作为一个虚拟的正电荷，每个节点受到边界障碍和其他节点的排斥，这种排斥力使整个网络中的所有节点向感知网中的其他地域扩散，并避免越出边界，最终达到平衡状态，即达到感知区域的最大覆盖状态。

Zou Y等人提出VFA算法［14］基本思想是假设部署区域中存在3种力:一是障碍物对节点的斥力，二是对覆盖率要求高的区域产生的引力，三是节点之间产生的引力或斥力。算法计算产生在每个节点上的合力来控制节点之间的距离与节点移动，缺点是没有为可能出现的节点碰撞提供解决方案。优点是算法简单易用，并能达到节点快速扩散到整个感知区域的目的，同时每个节点所移动的路径比较短。

2.3 利用节点间的移动

文献［15］通过利用部分节点的有限移动，完成覆盖空洞，达到网络k覆盖的目的。

3 节点部署方法比较

下面对目前常见的无线传感器网络部署方法进行比较，其结果见表1。

表1 节点部署方法比较Tab 1 Comparison of node deployment methods

通过表1，可以从整体上清晰认识各种部署策略。此外，对相关研究成果的优缺点比较，有助于更加全面的了解已有的部署策略，并进一步发现和考虑一些凾待解决的问题。

4 节点部署中存在的问题

针对以上文献进行分析，节点部署中存在的问题可以归为以下几点:

1)部署误差不可忽视:目前研究假设节点部署不存在部署误差，在部署误差存在的情况下，如何建立有效的模型，在节点感知半径、监测区域面积已知的情况下，确定最佳的部署节点个数。

2)忽略边界因素影响:没有考虑到监测区域边界对于网络的覆盖与连通带来的影响［16］，通常采用渐近性分析方法，基于这些假设的分析结果在实际部署应用中不能达到所需要的覆盖性能。

3)感知和通信模型过于理想:假设传感器节点的感知模型和通信模型是理想的圆盘模型，不能适用于实际环境的感知模型多样化需要。

4)容错部署问题:当网络中某些节点能量耗尽或者发生故障时，可能出现覆盖“空洞”，使得网络出现分割，甚至导致网络的不连通，需要重新对网络进行部署。

5)部署空间扩展问题:大多数无线传感器网络应用是在三维空间中。如何针对具体的WSNs三维空间应用需要设计出有效的算法与协议，是一个很有意义的研究课题。

5 结束语

由于无线传感器网络资源有限且是应用相关的网络，研究人员研究多种节点部署策略来满足其应用需求和新特性。本文从静态和动态2种部署方式介绍了节点部署的分类与应用要求，分析各种部署策略的优势及应用环境。但是，节点部署作为传感器应用的一项关键技术，还有很多问题需要进一步研究，在满意应用需求的同时，充分利用其有限资源。

［1］Kenan X.Device deployment strategies for large-scale wireless sensor networks［D］.QSpace at Queen’s University，2008.

［2］Younis O，Fahmy S.HEED:A hybrid，energy-efficient，distributed clustering approach for Ad Hoc sensor networks［J］.IEEE Transactions on Mobile Computing，2004，3(4):366-379.

［3］Mhatre V.A minimum cost heterogeneous sensor network with a lifetime constraint［J］.IEEE Transactions on Mobile Computing，2005，4(1):4-15.

［4］Romer K，Mattern F.The design space of wireless sensor networks［J］.IEEE Wireless Communications，2004，11(6):54-61.

［5］Shakkottai S，Srikant R，Shroff N.Unreliable sensor grids:Coverage，connectivity and diameter［J］.Ad Hoc Networks，2005，3(6):702-716.

［6］Coskun V.Relocating sensor nodes to maximize cumulative connected cove-rage in wireless sensor networks［J］.Sensors，2008，8:2792-2817.

［7］Balister P，Bollobas B，Sarkar A，et al.Reliable density estimates for coverage and connectivity in thin strips of finite length［C］∥The 13th Annual ACM International Conference on Mobile Computing and Networking，Montréal，Québec，Canada，ACM，2007:75-86.

［8］Zhang H，Hou JC.Is deterministic deployment worse than random deployment for wireless sensor networks［C］∥The 25th IEEE International Conference on Computer Communications，Barcelona，Spain，2006:1-13.

［9］Bredin J L，Demaine E D，Hajiaghayi M，et al.Deploying sensor networks with guaranteed capacity and fault tolerance［C］∥The 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing，Urbana-Champaign，IL，USA，ACM，2005:309-319.

［10］Jain E，Qilian L.Sensor placement and lifetime of wireless sensor networks:Theory and performance analysis［C］∥The IEEE Global Telecommunications Conference，2005:5.

［11］Wang D，Xie B，Agrawal D.Coverage and lifetime optimization of wireless sensor networks with Gaussian distribution［J］.IEEE Transactions on Mobile Computing，2008，7(12):1444-1458.

［12］Tarng J，Chuang B，Liu P.A relay node deployment method for disconnected wireless sensor networks:Applied in indoor environments［J］.Journal of Network and Computer Applications，2009，32(3):652-659.

［13］Hu Y，Kang Z，Shen X.An incremental sensor deployment strategy for wireless sensor networks［C］∥1st International Conference on Information Science and Engineering(ICISE)，2009:4721-4724.

［14］Zou Y，Krishnendu C.Sensor deployment and target localization based on virtual forces［C］∥The Twenty-Second IEEE Annual Joint Conference on Computer and Communications，2003:1293-1303.

［15］Yang X，Hui C，Wu Kui，et al.Modeling detection metrics in randomized scheduling algorithm in wireless sensor networks［C］∥The IEEE Wireless Communications and Networking Conference，Kowloon，2007:3741-3745.

［16］Wan PJ，Yi CW.Coverage by randomly deployed wireless sensor networks［J］.IEEE/ACM Trans on Networks，2006，14(S1):2658-2669.