WSN中一种改进的节点部署方案

张 凯

(武汉理工大学信息工程学院，湖北武汉 430070)

0 引言

无线传感器网络是近年来受到国内外广泛关注的研究热点。在工作过程中节点会不断地感知到周边环境的数据，并将通过无线天线将数据以多跳的方式发送给远方的Sink节点(或称为基站)进行处理，节点的部署方案将直接影响数据收集和网络生存期等性能。因此，如何有效地对节点进行部署［1］成为无线传感网进行数据收集和处理的关键。

1 相关工作

目前，对于无线传感网的节点部署研究工作较多，文献［2］针对传感器网络节点部署时首要考虑的是覆盖问题，提出一种可以满足不同覆盖率要求的节点优化部署算法，在提高节点覆盖性能的同时优化节点数量，降低网络的配置代价。仿真结果证明，该算法可最大化节点的覆盖效率;文献［3］为提高无线传感器网络的节点覆盖度，提出一种目标关联覆盖算法，利用节点间的关联性和动态分组调整覆盖区域，利用贪心算法对覆盖区域进行优化，以保证所关注的目标节点被传感器节点均匀覆盖，同时提高网络资源的利用率。在每个周期内唤醒部分节点，轮流进行工作，以均衡网络能量消耗。实验结果表明，该算法适应性更强，并且能有效降低网络能耗，提高网络性能;文献［4］针对现有的节点调度算法不能同时保证工作节点均匀分布，使网络能耗不均衡的问题，提出了一种与节点位置无关的无线传感器网络覆盖协议(EBLCP)。EBLCP在虚拟坐标的基础上建立临时集，节点只需与邻居中少量节点通信，比较这些节点的剩余能量从而竞选工作节点。实验结果表明，EBLCP能保证较高的覆盖率，并延长网络生存时间。然而，以上的部署算法都是建立在节点的感知范围无边界或者边界效应可以忽略的假设上。事实上，在实际的场景中，边界的存在对于网络的连通覆盖具有重大的影响，而现有的“修补”方法虽然可以保证连通覆盖薄弱区域，但是却提高了网络部署的成本，并会造成节点分布不均匀的状况。针对以上问题，提出了一种改进的无线传感器节点部署算法，理论分析和仿真实验表明，所提出的方案是有效的。

2 相关定义与建模分析

2.1 相关定义

令CN表示节点N的覆盖范围，⊙N表示节点N覆盖圆的圆周。A，B，C，D，E 为凸边形的顶点，如图1所示。

图1 凸角多边形abcde的定义

定义1 内分点(IPD):指凸多边形的内部任一顶点中，位于其他顶点的内角平分线上且与其他顶点的欧式距离为d的点，d∈［0，rN］。如图1中点A1，B1，C1，D1，E1。

定义2 边界线(BL):指从一个内分点到另一个内分点所做的平行于边界的直线。

定义3 边界点(BP):指位于边界线上除内分点以外的其他所有顶点。

定义4 边角交点(IPF):角点的感应圆圈与边点线的交点。

2.2 网络模型

将监测区域π模拟为二维平面内的不规则凸角多边形δ，边界信息已知，凸角多边形其边界顶点位置依据顺时针方向标记为 {a，b，c…}。这里假设无线传感网具有以下性质:

①所有节点部署后保持静止，不再移动;

②所有节点以自身为圆心，在其感知范围为进行感知，所有节点的感知半径一致，均为rsame;

③ 对于任意节点x，y而言，仅当d(x，y)≤rsame时，则认为节点x被节点y覆盖。d(x，y)表示2个节点间的欧式距离。

3 改进的部署方案

本文提出的改进的节点部署方案命名为IDS。它主要由2个部分组成:首先，对于感知区域进行边界的部署，达到保证全连通和覆盖的效果，然后在感知区域内，通过凸多边形生成算法来不断地进行内部部署，递归调用知道整个感知区域被覆盖。

3.1 边界部署

边界部署的主要目的是保证部署后的节点能够覆盖整个感知区域的边界。部署过程如下:①根据δ的顶点信息，确定对应δ每个凸角的角度和角点;②确定与每个内分点对应的边界线;③依据式(1)和式(2)来确定每条边界线上的边界点［1］。

3.2 新凸边形的生成

边界部署完成后，δ并没有被完全覆盖，生成了多个边角交点IPF，如图2所示。

图2 边界的生成

由于现在未被覆盖区域的边界形状变得更加复杂，因此GRLD算法的第2部分旨在生成新的边界，形成新的凸多边形区域。思想如下:过每个IPF做平行于对应边界的平行线，以这些平行线的交点为新的顶点，顺时针连接形成新的凸角多边形。

3.2.1 算法2:新凸边形生成算法

3.2.2 算法3:改进后的部署算法

结合算法1和算法2递归调用，即得到本文提出的IDS算法如下:

4 仿真实验

这里使用MATLAB2011对IDS进行仿真实验，并与目前较为典型的部署方案(六边形点阵和四边形点阵)进行了性能比较分析。实验过程中，节点的感应半径设定为5 m，通信半径设为10 m。实验结果如图3(a)所示。

实验结果是当感应区域为三角形、四边形、六边形和任意形状时，使用IDS、六边形点阵和四边形点阵进行部署时，所需要使用到的节点个数比较。结果表明，就达到完全覆盖效果上来看，IDS使用的节点个数是最少的。这主要是因为，IDS方案从边界开始布点，克服了部署后“修补”薄弱区域所需要的节点，从而大大减少了节点感应区域的叠加，增大节点的有效覆盖面积，使得浪费减少。

图3 不同部署方案的节点个数变化

图3(b)表示的是放感知区域面积变化时，使用IDS、六边形点阵和四边形点阵部署的节点个数变化情况，从中可以看出，当δ的面积从4320 m2增大到67500 m2时，IDS所需的节点个数的增幅为1500个，六边形点阵下所需的节点个数的增幅为2100，四边形点阵下的节点增幅为2400个。即IDS只需要增加较少数量的节点就能达到和六边形点阵有更小的节点增幅，说明其相对于四边形点阵、四边形点阵一样的覆盖效果，因此本文的方法更容易扩展，稳定性更好。

5 结束语

如何有效地部署传感网节点对于提高无线传感网的数据传输质量以及延长网络生命周期具有重要的影响。在传统的部署算法上，进一步考虑了边界效应对于网络连通和覆盖的影响，提出了一种改进的节点部署方案IDS。理论分析和仿真实验表明，本文方法是有效的，相比于六边形点阵和四边形点阵的部署效果而言，IDS所需使用的节点个数也更少，且算法更容易扩展。下一步的工作是对现有的部署方案进行拓展，研究三维区域内的确定性部署方案。 ■

［1］LIAO Z，WANG J，WANG X，et al.GRLD:A Seamless Growth Rings like Deployment of Sensors Avoiding Boundary Effects in WSNs［C］∥Wireless Communications and Networking Conference(WCNC)，IEEE，2010:1 －6.

［2］孙泽宇，邢萧飞，魏 巍.无线传感器网络中的目标关联覆盖算法［J］.计算机工程，2011，37(9):138 －140.

［3］朱继华，武 俊，陶 洋.基于覆盖率的传感器优化部署算法［J］.计算机工程，2011，36(3):94 －96.

［4］孙泽宇，邢萧飞，魏 巍.无线传感器网络中的目标关联覆盖算法［J］.计算机工程，2011，37(9):138 －140.

［5］ZHANGH，HOU J C.Maintaining Sensing Coverage and Connectivity in Large Sensor Networks［J］.Ad Hoc ＆Sensor Wireless Networks，2005，1(1):89 －124.

［6］IYENGARR，KAR K，BANERJEE S.Low-coordination Topologies for Redundancy in Sensor Networks［C］∥The 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing，2005:332 －342.

［7］BAIX，XUAN D，YUN Z，etal.Complete Optimal Deployment Patterns for Full-coverage and k-connectivity(k≤6)［C］∥The 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing，2008:401－410.

［8］WANG X，SUN F，KONG X.Research on Optimal Coverage Problem of Wireless Sensor Networks［C］∥International Conference on Communications and Mobile Computing，2009:548－551.