一种基于贪心思想的三维矿井混合路由算法

摘要

一种基于贪心思想的三维矿井混合路由算法，属于煤矿井下无线传感器网络数据传输路由算法。首先使用空间镶嵌理论优化节点部署策略，设置适合煤矿井下的部署方案，然后利用贪心思想优化网络的分簇路由算法，使用剩余能量以及转播因子作为簇首选举的权值参照，最后确定权值函数选择最优的下一跳节点，最终形成数据转发的最优路径，降低网络的能量开销和延时时间。利用贪心思想设计具有全局能量高效且均衡、时延较小的无线传感器网络路由算法；根据空间镶嵌理论选用三角棱柱进行三维空间填充，在确定节点位置时将三维空间转换为二维表示。通过感知节点的剩余能量和转播因子进行分簇，在建立簇间路由时利用贪心思想实现簇首与基站最优路径多跳通信。

主权项

一种基于贪心思想的三维矿井混合路由算法，其特征在于：该路由算法，首先使用空间镶嵌理论优化节点部署策略，设置适合煤矿井下的部署方案，然后利用贪心思想优化网络的分簇路由算法，使用剩余能量以及转播因子作为簇首选举的权值参照，最后确定权值函数选择最优的下一跳节点，最终形成数据转发的最优路径，降低网络的能量开销和延时时间；具体步骤如下：(一)节点部署阶段：(1)研究煤矿井下空间特征，选取节点空间部署模型；(2)利用空间镶嵌理论选择适合煤矿井下的填充单元，并对井下空间进行节点的部署；部署后巷道中节点的坐标表示，X轴表示沿着巷道底部中心轴线距离汇聚节点(sink)的距离，Y表示节点到巷道底部的弧长，Y坐标取值有三种分别为0、πr，其中r为巷道的半径；(二)路由建立阶段：a.节点成簇过程：(1)计算网络中节点的阈值T(n)；为延长网络生命的周期，平衡节点的能量消耗问题，在成簇过程中，应尽可能增加剩余能量较高且转播因子较大的节点当选为簇首的概率；(2)网络中的节点产生一个在0～1之间的随机数，如果这个随机数小于阈值T(n)，那么该节点当选为簇首；(3)节点被当选为簇首节点后，向周围节点广播自己成为簇首的消息，其他普通节点收到消息后，根据信号强度等信息，选择最优的簇首加入某个簇，成为该簇的成员；b.混合路由建立过程：(1)判断节点的下一跳节点的候选区域范围；将下一跳节点的定向区域定义在顶角为θ的圆锥区域内，圆锥的轴线平行于巷道的中心线。本文中θ＝60°，即圆锥母线与巷道中心线之间的夹角为30°，若两节点所在的直线与巷道中心线之间的夹角φ小于30°，则该节点在候选区域中；根据能量消耗模型，计算节点n_i传输数据到下一跳节点n_j的剩余能量期望值E_r(i)；$E_r\left(i\right)=\left\{\begin{array}{c}{E}_{current}\left(i\right)-(l·E_{elec}+l·{ϵ}_{fs}·{d_{ij}}^2),(d_{ij}<d_0)\\ E_{current}\left(i\right)-(l·E_{elec}+l·{ϵ}_{mp}·{d_{ij}}^4),(d_{ij}\ge d_0)\end{array}\right.$(2)使用贪心算法将节点的权值函数P(i,j)作为目标函数，将目标函数从大到小排列，选择出目标函数最大的节点作为下一跳节点；P(i,j)＝αE_r(i)+βE(j)+λS(j)(3)网络通过局部最下一跳节点确定整体的最优数据传输路线。