WSN中正三角形剖分的异构节点静态部署算法*

金仁成，朱明，车志平，李应琛

(大连理工大学 辽宁省微纳米技术及系统工程重点实验室，大连 116024)



WSN中正三角形剖分的异构节点静态部署算法*

金仁成，朱明，车志平，李应琛

(大连理工大学 辽宁省微纳米技术及系统工程重点实验室，大连 116024)

摘要:针对无线传感器网络异构节点静态部署问题，提出了一种基于正三角形剖分的异构节点部署算法。将监测区域进行正三角形网格划分，利用网格单元顶点及中心位置信息，在正三角形网格单元的顶点处部署感知半径较大的节点，在中心部署感知半径较小的节点，使不同感知半径的节点得到充分利用，保证了监测区域的覆盖率要求。

关键词:无线传感器网络；静态部署；异构；正三角形剖分

引言

无线传感器网络(WSN)节点部署，是在指定的监测区域内，适当布置传感器节点以满足特定需求。传感器节点布置的好坏直接决定了WSN所能提供的“感知”服务质量[1]。通常有2种传感器节点部署策略：确定性部署和随机部署。确定性部署一般用于监测环境简单的情形，借助人工在区域内手动部署节点以满足特定的覆盖要求；而随机部署则更多用于监测环境复杂多变的情况，随机部署后，借助节点的移动能力，采用一些部署算法来实现监测区域的良好覆盖。

针对异构传感器网络节点部署问题，本文以节点感知半径作为异构问题的研究对象，提出了一种基于正三角形剖分的异构节点静态部署算法。运用算法对监测区域进行网格划分，在正三角形网格的顶点处部署感知半径较大的传感器节点，在中心部署感知半径较小的传感器节点，充分利用异构节点不同的感知能力，实现监测区域的良好覆盖。

1问题描述

1.1相关假设

针对本文的研究，做出以下假设：

① 所有的传感器节点具有相同的通信、计算以及移动能力等，只有节点的感知半径存在异构特性。

② 所有传感器节点不可移动，处于同一平面，并且节点的感知范围和通信范围都是理想的圆形。

③ 在异构节点静态部署策略实施后，各类节点之间能够实现良好的通信。

1.2感知模型

为了简化问题研究，作为二元感知模型传感器节点的模型。当点si与P之间的距离在节点的感知范围内时，节点能采集到P点信息的概率为1；当点si与P之间的距离在感知范围外时，节点能采集到P点信息的概率为0，如下所示：

2算法构建

2.1基于正三角形网格的同构节点部署模型

图1　相邻的3个节点　呈正三角形结构

如图1所示，3个感知半径相同的同构节点呈现正三角形结构(图中未画出)时，节点的覆盖率达到82.7%，此时网络的覆盖率最高，节点冗余最小。

2.2基于正三角形剖分的异构节点部署模型

依据参考文献[2]的思想，参考文献[7]对如图1所示的结构进行了变形，并进一步提出了两种感知半径的传感器节点动态部署模型。如图2所示，将图1中的正三角形的边长扩大，图中的节点随正三角形顶点位置的变化而变化。由于节点的感知半径不变，节点位置发生变化时，正三角形的中心必定出现空隙，因此形成覆盖空洞，如图2右侧所示，如果在中心处小圆表示的覆盖空洞处另外部署一个感知半径较小的节点，那么覆盖空洞的问题就可迎刃而解。

图2　相邻的3个节点随正三角形顶点位置变化而出现覆盖空洞

(1) 异构节点区域覆盖建模

图3　异构节点区域覆盖建模

图2只在直观上对呈正三角形结构部署的节点间距离变化造成的空洞进行了展示，并单纯地加入一个感知半径较小的节点来解决覆盖空洞问题。这里，通过建立异构节点区域覆盖模型，来探讨这两类节点之间的数量关系。假设图3所示的一种节点的感知半径为R1，另一种感知半径为R2，并且R1>R2，R1/R2=k。这里，设R1=r，R2=r/k。

由图3所示几何关系可知:

从而可知，三角形的面积为：

两种感知半径的4个节点的覆盖率为：

(2) 确定异构节点最佳感知半径比例

借助Matlab可以得到覆盖率与感知半径之比k之间的关系图，如图4所示。

图4　覆盖率与感知半径之比之间的关系

(3) 监测区域异构节点部署

经过以上分析，确定了覆盖率取得最大值时两种异构节点感知半径之比。借助参考文献[2]的网格划分思想，针对本文讨论的异构节点部署，对监测区域进行网格划分。以正三角形作为网格划分单元，在网格单元的顶点处部署感知半径较大的节点，在中心部署感知半径较小的节点。

3仿真结果

为了更加详细地展示本文的思想，借助Matlab对上述算法进行仿真实验。在实验中，选取两种感知半径的传感器节点，A类节点的感知半径Ra=4，B类节点的感知半径Rb=0.72，在50×50的监测区域内部署。

首先对监测区域进行三角形网格划分，得到如图5所示的结构。然后，在图5所示的正三角形网格单元的顶点部署A类节点，在中心处部署B类节点。显然，由部署后的结果可知，只在监测区域内的网格单元顶点和中心处部署节点不能满足全覆盖要求，部分区域会出现空洞，因此，需要对部分区域的节点部署位置进行微调，得到如图6所示的结构，其中，圆形节点是在图7的基础上新增加的节点。

图5　异构节点在监测区域内的部署结构图

图7　在正三角形网格单元的顶点及中心部署两种异构节点

结语

参考文献

[1] Li J H,Yu M.Sensor coverage in wireless ad hoc sensor networks[J].International Journal of Sensor Networks,2007,2(3-4):218-229.

[2] 曹峰,刘丽萍,王智.能量有效的无线传感器网络部署[J].信息与控制,2006,35(2):147-153.

[3] 凡志刚,郭文生,桑楠.一种基于蜂窝网格的传感器节点部署算法[J].传感器与微系统,2008(4):15-17.

[4] 周彤,洪炳.基于虚拟力的混合感知网节点部署[J].计算机研究与发展,2015,44(6):965-972.

[5] 冀文娟,石为人,李明,等.异构无线传感器网络中多目标优化节点部署策略[J].传感器与微系统,2012(3):29-31,35.

[6] 俞黎阳,王能,张卫.异构无线传感器网络中异构节点的部署与优化[J].计算机科学,2008(9):48-51.

[7] 陈杰,杜庆伟,李晓禹,等.概率模型下异构传感器网络部署算法的研究[J].小型微型计算机系统,2012(1):49-53.

[8] 冯秀芳,关志艳,全欣娜.基于虚拟力的异构节点网络覆盖增强算法[J].计算机工程,2009(5):103-105.

(责任编辑：薛士然收修改稿日期：2016-01-14)

Heterogeneous Nodes Static Deployment Algorithm Based on Equilateral Triangle Partition in WSN

Jin Rencheng,Zhu Ming,Che Zhiping,Li Yingchen

(Key Laboratory for Micro/Nano Technology and System of Liaoning Province,Dalian University of Technology,Dalian 116024,China)

Abstract：Aiming at the problem of heterogeneous nodes static deployment of the wireless sensor network,a deployment algorithm based on the equilateral triangle partition is proposed.Firstly,the sensing field is drawn into lots of equilateral triangle grids.Then using the location information of each equilateral triangle’s center and vertex,the nodes with bigger sensing range are deployed in the vertex of equilateral triangle grids and the nodes with smaller sensing range in the center of it.Lastly,the nodes with different sensing range can be fully used and the coverage requirement of the sensing field can be ensured at the same time.

Key words:wireless sensor network;static deployment;heterogeneous;equilateral triangle partition

中图分类号:TP393.17

文献标识码:A

* 基金项目：国家重点基础研究发展计划(973计划)资助项目(2009CB320300)；国家“十二五”科技支撑计划资助项目(2011BAG05B02)。