一种基于真实三维地形的WSN节点部署优化方法.pdf

(19)国家知识产权局(12)发明专利申请(10)申请公布号CN114945181A(43)申请公布日2022.08.26(21)申请号202210384813.XG06F111/04(2020.01)(22)申请日2022.04.13G06F111/08(2020.01)(71)申请人西北工业大学地址710072陕西省西安市友谊西路127号(72)发明人羊彦符雯迪洪国旗刘江浩侯静(74)专利代理机构西安凯多思知识产权代理事务所(普通合伙)61290专利代理师赵革革(51)Int.Cl.H04W16/18(2009.01)H04W84/18(2009.01)G06T17/05(2011.01)G06F30/18(2020.01)G06F111/02(2020.01)权利要求书2页说明书6页附图1页(54)发明名称一种基于真实三维地形的WSN节点部署优化方法(57)摘要本发明公开了一种基于真实三维地形的WSN节点部署优化方法，首先，为了解决待部署区域地表模型的真实性问题，利用网络地理数据库中下载的真实地形高程数据对地表进行重构建模，避免了由于曲面模型不精确所引入的覆盖误差；其次，针对三维曲面覆盖问题中特有的覆盖盲区问题，综合考虑了信号衰减和地形遮挡因素对于覆盖面积的影响，解决了原有覆盖模型在三维环境下存在覆盖缺陷的问题，因此更接近真实场景；最后，考虑到传统算法在三维环境下寻优速度慢，覆盖性能较差，以及贪心算法在解决最优解问题方面的高效性。本发明方法在解决真实三维环境下WSN节点部署问题上，无论在部署成本和效率方面均具有显著的优势。CN114945181ACN114945181A权利要求书1/2页1.一种基于真实三维地形的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中，如下式：其中，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)；α、β是不同的衰减因子，表示不确定感知区域内感知概率的衰减程度；2CN114945181A权利要求书2/2页步骤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)