技术领域

本发明属于通信技术领域，具体涉及一种WSN节点部署优化方法。

背景技术

无线传感器网络(Wireless Sensor Networks,WSN)技术综合了分布式信息处理、嵌入式计算、无线网络与通信和传感器等多项技术，广泛应用于各种领域，是二十一世纪最具影响力的技术之一。无线传感器网络的性能很大程度上取决于WSN节点的地理位置，在满足覆盖区域监测需求的前提下，最大程度地降低网络的部署成本，因此网络拓扑结构的合理性对网络连接和覆盖的性能至关重要。

针对真实三维环境下的WSN节点部署问题，传统方案存在如下四方面问题：

(1)待部署区域采用的是函数生成的曲面，过于规律和平滑，不能模拟实际地形环境的地表特点。

(2)传统方案需要根据曲面函数来估计部署所需的节点数，而实际地形变化不规则，无法得到待部署区域的曲面函数进而无法计算节点数。

(3)传统的球形覆盖模型没有考虑到实际地形对于覆盖范围的影响，在复杂地表环境中，节点的覆盖范围大多为不规则的形状，所以亟需提出一种更符合山区环境的节点覆盖模型。

(4)由于待部署区域地表信息数据量大，新的覆盖模型更为复杂，以往的部署算法会由于计算量大、地形复杂而导致收敛速度过慢、易陷入局部最优等问题。

发明内容

为了克服现有技术的不足，本发明提供了一种基于真实三维地形的WSN节点部署优化方法，提出了基于网格扫描的贪心算法(Greedy algorithm based on gridscanning，GAGS)。首先，为了解决待部署区域地表模型的真实性问题，利用网络地理数据库中下载的真实地形高程数据对地表进行重构建模，避免了由于曲面模型不精确所引入的覆盖误差；其次，针对三维曲面覆盖问题中特有的覆盖盲区问题，提出了一种基于数字高程模型(DEM)数据的概率覆盖模型，该模型综合考虑了信号衰减和地形遮挡因素对于覆盖面积的影响，解决了原有覆盖模型在三维环境下存在覆盖缺陷的问题，因此更接近真实场景；最后，考虑到传统算法在三维环境下寻优速度慢，覆盖性能较差，以及贪心算法在解决最优解问题方面的高效性，本发明采用改进的贪心算法进行求解，用尽可能少的传感器节点实现了对地形的全覆盖。本发明方法在解决真实三维环境下WSN节点部署问题上，无论在部署成本和效率方面均具有显著的优势。

本发明解决其技术问题所采用的技术方案包括如下步骤：

步骤1：建立真实三维地表模型；首先通过网络数据库下载数字高程模型DEM，然后根据DEM点在横纵坐标方向各自的采样数量，对平面区域进行相同数量的网格划分，并对网格点赋予相应的高程值；

步骤2：构建基于DEM数据的WSN概率覆盖模型；

步骤2-1：地形遮蔽对于WSN概率覆盖模型的影响；

将三维地表模型上所有的网格点坐标(xi,yj,z(xi,yj)),i＝1,2...m；j＝1,2...,n存储到矩阵X,Y,Z中，如下式：

X＝[x1,x2,...,xm]

Y＝[y1,y2,...,yn] (1)

其中，z(xi,yj)为网格点(xi,yj)对应的高程坐标值，m、n分别表示网格的长和宽；

对于网格点上感知半径为r的传感器节点，以传感器节点坐标为原点，感知方向角θ(θ∈(0,2π))为步进方向、g/cosθ为步长进行步进，其中g为离散网格点间距；每个步进点的高程值由其周围四个网格点的高程值插值计算得到，由此得感知方向θ上感知范围r内所有步进点的高程值为其中θp表示第p个步进点；

根据高程值利用下式判断感知方向上网格点受地形遮蔽影响情况：

其中，Pter＝1表示网格点不受地形遮蔽的影响，能被传感器节点覆盖；Pter＝0表示网格点受到地形遮蔽的影响无法被覆盖；zi(0≤i≤n)为传感器节点在感知方向上对应步进点的高程值，z0即为传感器节点所在网格点的高程值，zn为传感器节点在感知方向上能够感知到的最远网格点；

使感知方向角θ在[0,2π]范围内进行递增，即能判断传感器节点感知范围内所有网格点受地形遮蔽影响的情况；

步骤2-2：信号衰减对WSN概率覆盖模型的影响；

覆盖概率的数学模型见下式(3)：

其中，Psph为球形概率覆盖模型下网格点被感知到的概率，d为网格点与传感器节点之间的距离，R表示不存在信号衰减时的最大感知半径，rs用于表示节点的不确定性感知能力，λ＝d-(R-rs)；α、β是不同的衰减因子，表示不确定感知区域内感知概率的衰减程度；

步骤2-3：综合步骤2-1和步骤2-2，计算基于DEM数据的WSN概率覆盖模型为：

P＝Pter·Psph (4)

步骤3：基于网格扫描贪婪算法思想的部署算法；

首先，明确问题的求解目标：实现三维地表模型下的传感器节点部署，在满足区域覆盖需求的同时，最大限度地提高覆盖率；

式中Coverage为在满足预设覆盖率Ppre条件下的覆盖率，计算公式为被覆盖的网格数与总网格数m×n之比，其中当网格被覆盖的概率p大于概率阈值时，即判定为被覆盖；

其次，确定算法的约束条件：候选节点的部署位置不能超出待部署区域所限定的部署范围，即所有节点均部署在地表模型所划分的网格点上；设传感器节点的坐标为(xi,yj,z(xi,yj))，对应约束条件为：

步骤4：根据网格扫描贪婪算法的思想进行节点遍历；

步骤4-1：结合式(2)-(4)计算任意传感器节点在地形遮挡和信号衰减影响下对其周围网格点的覆盖程度P(k)；

步骤4-2：找到在待部署区域内能够覆盖网格点数最多的节点部署位置，并将该位置添加到候选覆盖集Cov_sel中，如下式(7)所示：

其中，Num(P(k)表示满足预设覆盖率下的节点部署数量，sensor(k)表示新增节点位置集合；

步骤4-3：设定整个待部署区域内可部署节点的位置集合为遍历域Trav并从Trav中删除已被覆盖的网格点；若在遍历过程中遇到多个节点覆盖率相同，选择坐标最小的节点进行优先部署，直到待部署区域被全覆盖或达到预定覆盖率时，算法迭代结束；具体公式见下式(8)：

其中，ones(m,n)为m×n的单元矩阵，Trav(p,q)表示遍历域中位于(p,q)的点，Trav(i,j)表示表示遍历域中位于(i,j)的点，～(.)表示集合(.)的补集。

优选地，所述真实三维地表模型采用GRID模型。

本发明的有益效果如下：

本发明为了解决待部署区域地表模型的真实性问题，利用网络地理数据库中下载的真实地形高程数据对地表进行重构建模，避免了由于曲面模型不精确所引入的覆盖误差；其次，针对三维曲面覆盖问题中特有的覆盖盲区问题，提出了一种基于数字高程模型(DEM)数据的概率覆盖模型，该模型综合考虑了信号衰减和地形遮挡因素对于覆盖面积的影响，解决了原有覆盖模型在三维环境下存在覆盖缺陷的问题，因此更接近真实场景；最后，考虑到传统算法在三维环境下寻优速度慢，覆盖性能较差，以及贪心算法在解决最优解问题方面的高效性，本方法采用改进的贪心算法进行求解，用尽可能少的传感器节点实现了对地形的全覆盖。仿真结果表明，所提出的算法在部署成本和效率方面都有着显著的优势。

附图说明

图1是本发明方法所构建的三维真实地表模型图。

图2是本发明实施例节点部署分布图。

具体实施方式

下面结合附图和实施例对本发明进一步说明。

一种基于真实三维地形的WSN节点部署优化方法，包括如下步骤：

步骤1：建立真实三维地表模型，本发明采用GRID模型；首先通过网络数据库下载数字高程模型DEM，然后根据DEM点在横纵坐标方向各自的采样数量，对平面区域进行相同数量的网格划分，并对网格点赋予相应的高程值；

步骤2：构建基于DEM数据的WSN概率覆盖模型；

步骤2-1：地形遮蔽对于WSN概率覆盖模型的影响；

将三维地表模型上所有的网格点坐标(xi,yj,z(xi,yj))(i＝1,2...m；j＝1,2...,n)存储到矩阵X,Y,Z中，如下式：

X＝[x1,x2,...,xm]

Y＝[y1,y2,...,yn] (1)

其中，z(xi,yj)为网格点(xi,yj)对应的高程坐标值；

对于网格点上感知半径为r的传感器节点，以传感器节点坐标为原点，感知方向角θ(θ∈(0,2π))为步进方向、g/cosθ为步长进行步进，其中g为离散网格点间距；每个步进点的高程值由其周围四个网格点的高程值插值计算得到，由此得感知方向θ上感知范围r内所有步进点的高程值为

根据高程值利用下式判断感知方向上网格点受地形遮蔽影响情况：

其中，Pter＝1表示网格点不受地形遮蔽的影响，能被传感器节点覆盖；Pter＝0表示网格点受到地形遮蔽的影响无法被覆盖；zi(0≤i≤n)为传感器节点在感知方向上对应步进点的高程值，z0即为传感器节点所在网格点的高程值，zn为传感器节点在感知方向上能够感知到的最远网格点；

使感知方向角θ在[0,2π]范围内进行递增，即能判断传感器节点感知范围内所有网格点受地形遮蔽影响的情况；

步骤2-2：信号衰减对WSN概率覆盖模型的影响；

覆盖概率的数学模型见下式(3)：

其中，Psph为球形概率覆盖模型下网格点被感知到的概率，d为网格点与传感器节点之间的距离，R表示不存在信号衰减时的最大感知半径，rs用于表示节点的不确定性感知能力，λ＝d-(R-rs)；α、β是不同的衰减因子，表示不确定感知区域内感知概率的衰减程度；

步骤2-3：综合步骤2-1和步骤2-2，计算基于DEM数据的WSN概率覆盖模型为：

P＝Pter·Psph (4)

步骤3：基于网格扫描贪婪算法思想的部署算法；

首先，明确问题的求解目标：实现三维地表模型下的传感器节点部署，在满足区域覆盖需求的同时，最大限度地提高覆盖率；

式中Coverage为在满足预设覆盖率Ppre条件下的覆盖率，计算公式为被覆盖的网格数与总网格数m×n之比，其中当网格被覆盖的概率p大于概率阈值时，即判定为被覆盖；

其次，确定算法的约束条件：候选节点的部署位置不能超出待部署区域所限定的部署范围，即所有节点均部署在地表模型所划分的网格点上；设传感器节点的坐标为(xi,yj,z(xi,yj))，对应约束条件为：

步骤4：根据网格扫描贪婪算法的思想进行节点遍历；

步骤4-1：结合式(2)-(4)计算任意传感器节点在地形遮挡和信号衰减影响下对其周围网格点的覆盖程度P(k)；

步骤4-2：找到在待部署区域内能够覆盖网格点数最多的节点部署位置，并将该位置添加到候选覆盖集Cov_sel中，如下式(7)所示：

步骤4-3：从遍历域Trav中删除已被覆盖的网格点；若在遍历过程中遇到多个节点覆盖率相同，选择坐标最小的节点进行优先部署，直到待部署区域被全覆盖或达到预定覆盖率时，算法迭代结束；具体公式见下式(8)：

具体实施例：

首先采集待部署区域的数字高程数据(DEM)，经过插值处理，得到一定精度的地表模型数据，进而构建待部署区域的三维地表模型。然后建立待部署区域节点部署数学模型，采样基于网格扫描的贪心算法，结合基于DEM数据的WSN概率衰减覆盖模型进行求解，求得真实三维地形上实际WSN节点的部署优化方案。

1、采集一块面积为600×600m2的待部署区域地理数据，采样精度g为12m。由2500个DEM数据点构建GRID三维地表模型，如图1所示。

2、设定传感器覆盖模型参数，感知半径R＝5m,r＝1m，衰减因子α＝β＝0.5。建立传感器覆盖模型，具体见公式(2)-(4)。

3、设置执行算法参数，覆盖阈值设为0.8，预设覆盖率Coverage设为1。

4、计算地表模型上任意位置的传感器节点在地形遮挡和信号衰减影响下对其周围网格点的覆盖程度P(k)

5、找到在待部署区域内能够覆盖网格点数最多的节点部署位置，并将该位置添加到候选覆盖集Cov_sel中。

6、从遍历域Trav中删除已被覆盖的网格点。若在遍历过程中遇到多个节点覆盖率相同，选择坐标最小的节点进行优先部署，直到待部署区域达到预定覆盖率时，算法迭代结束。否则，返回第5步。