基于贪心思想的三维空间定向混合路由协议*

李晓波，赵作鹏，张娜娜

(中国矿业大学 计算机科学与技术学院，江苏 徐州221116)

0 引 言

《煤炭产业政策》发布以来，煤炭企业提出了转型升级、科技创新、人才强企、安全发展四大战略，煤矿的安全发展刻不容缓，有线监控方式难以实现有效、全面的监测，将使煤矿生产留下巨大的安全隐患［1］。无线传感器网络(WSNs)在民事和军事具有广泛应用［2］，采用无线方式对矿井进行监测可以获得全面的监测数据。WSNs 可根据监测要求部署、更换和增加监测节点，弥补了有线监测方式难以恢复的缺点。煤矿井下空间环境特殊，并且有些区域难以到达，节点能源难以得到补充或更换，因此，设计适用于煤矿监测的路由协议的核心问题之一是设计一种能量均衡和高效利用的策略降低网络能耗，延长网络生命周期。

在前面的研究中，已经提出了多种路由协议:洪泛类协议、基于协商类协议、能源敏感类协议、定向发布类协议和基于分簇的协议等［3，4］，大量研究表明，采用基于分簇的路由算法能极大地提高WSNs 的可扩展性和网络生命周期。文献［5］中LEACH 协议是最早的经典分簇路由算法，但是单跳的通信方式使节点过早死亡。Heinzelman W 等人在文献［6］提出一种集中式的分簇路由协议LEACH—C，该协议均衡了节点的能量消耗。龙际珍等人［7］提出了一种基于LEACH 协议的助理簇头分簇算法，该算法动态地决定是否产生助理簇首，在一定程度上降低了节点的能量消耗并延长了网络生命周期。文献［8］在簇首与Sink 节点采用多跳的通信方式，有利于均衡簇间能量消耗，但是距离Sink 节点近簇首会因转发大量数据而能耗较大，容易导致“热区”问题。

本文根据煤矿井下的环境特点，结合空间镶嵌理论设计了节点部署模型，在研究上述分簇路由协议的基础上，提出了一种基于贪心思想的定向三维空间混合路由(greegy idea directional routing，GIDR)协议。

1 网络模型

1.1 能量模型

本文使用了与文献［6］类似的通信模型，发送端消耗的能量为

接收端的能量消耗为

1.2 空间部署模型

1.2.1 巷道模型

传感器节点的部署是WSNs 中的一个基本问题［9］，建立适合的三维井下节点部署方案具有很强的现实意义。煤矿井下巷道的模型是拱形设计，本文为研究方便将巷道空间模型定义为半球形。根据空间镶嵌理论，具有规则面的空间填充多面体有:三角棱柱、立方体、Johnson 固体第26号等，结合煤矿实际情况，选择三角棱柱作为三维空间填充单元。

根据海莱定理［10］可以通过在每个填充单元内放置k个节点实现k 覆盖，结合煤矿巷道的特点和安全监测的需求，节点部署在三角棱柱的顶点位置。煤矿井下三维拱形结构模型如图1(a)所示。

由于监测环境是三维的井下环境，因此，GPS 定位系统并不能使用，而且空间三维坐标信息比较复杂且不容易获得，但从节点到Sink 节点的平行距离可知，同时，各个节点沿巷道壁的弧度信息容易获取，因此，本文将三维空间坐标信息简化为二维坐标，如图1(b)所示。

图1 巷道空间部署模型Fig 1 Roadway space deployment model

在二维空间中，X 轴表示沿着巷道底部中心轴线距离Sink 节点的距离，Y 表示节点到巷道底部的弧长，本文中由于节点部署模型已确定，节点的Y 坐标取值有三种，分别为为巷道的半径)。在狭长的巷道中已知两点的坐标分别为ni(xi，yi)，nj(xj，yj)，利用几何知识可以计算出两个节点之间的距离dij

1.2.2 工作面模型

采煤工作面环境比较特殊，同时也是监测的关键地带，需要解决不断推进的工作面的节点部署问题。在工作面有支架对巷道进行掩护和支撑，假定支架为掩护式，本文将节点部署在支架上，由于液压支架的位置已知，部署在支架上节点的位置信息即为已知。不同位置的顶板压力有所不同，因此，需要在不同的位置部署节点，节点部署情况如图2所示，分别在A，B，C，D，E 部位部署传感器节点。

图2 工作面通信空间图Fig 2 Working face communication space

2 GIDR 协议描述

GIDR 协议是一种周期性协议，协议主要包括两个阶段:成簇过程和混合路由转发阶段，路由转发阶段时间大于成簇时间。在选择簇首时引入剩余能量因子和转播因子，在多跳通信时本文利用贪心算法思想求解最优通信路径。

定义1 转播因子:转播因子S(i)表明此节点的转播数据信息的速度，其依赖于节点自身的通信能力。

假设三个节点分别为i，j 和目的节点k，节点i 通过节点j 将数据转发至节点k，节点的转播因子S(i)可表示为

其中，dij为节点i 到节点j 的物理距离，djk为节点j 到节点k 的物理距离，Delayki 为节点i 转发数据到节点k 的延迟时间。

定义2 定向区域:定向区域表示节点选择下一跳节点的候选区域范围。

2.1 成簇过程

与LEACH 协议相似，节点产生一个0 ～1 之间的随机数，当随机数小于阈值T(n)时，则节点当选为簇首。为延长网络生命的周期，平衡节点的能量消耗问题，在成簇过程中，应尽可能增加剩余能量较高且转播因子较大的节点当选为簇首的概率。阈值T(n)的大小由下式确定

其中，p 为簇首在所有节点中所占的百分比，r 为所进行的选举轮数，r mod(1/p)代表的是这一轮循环中当选过簇首节点的节点个数，Ecurrent(n)为该节点当前的剩余能量，Einit(n)为该节点的初始能量，G 为在这一轮循环中未当选过簇首的节点的集合，F(n)由下式确定

式中 Scurrent(n)为当前节点的转播因子，Savg平均转播因子，q 为(0，1)之间的随机数，该数值的大小将在后期的工作中进一步研究。

节点被当选为簇首后，向周围节点广播自己成为簇首的消息，普通节点根据收到的信号强度等信息，选择最优的簇首加入某个簇。簇首产生一个TDMA 定时消息，并将该消息通知到该簇中的所有节点。同时，为了避免其他簇的信号的干扰，簇首可以决定本簇中的所有节点所使用的CDMA 编码。当簇内的各节点收到消息后，节点就会在各自的时间槽内发送数据到簇首。

2.2 混合路由转发阶段

为了减少能耗并保证网络的可靠性，在路由转发阶段采用混合路由转发模型。在多跳通信模式中关键的是如何选择下一跳节点使得路径最优，利用贪心算法思想可以求解最优路径，基本思想是找出整体当中每个小的局部的最优解，并将所有的这些局部最优解合起来形成整体上的一个最优解。

多跳通信方式在跳数相同的情况下中转节点在信息起点到信息终点的直线上时最节省能量，本文将下一跳节点的定向区域定义在顶角为θ(θ=60°)的圆锥区域内，圆锥的轴线平行于巷道的中心线。已知两点ni(xi，yi)，nj(xj，yj)，其中ni为源节点，当节点满足下面公式时，则节点nj在ni的候选区域中

证明如下

其中，dij由式(3)得出，即

说明:由三角函数关系得证。

利用贪心算法选择最优的下一跳节点，下一跳节点nj的选择依据是节点ni的剩余能量期望值Er(i)以及下一跳节点的转播因子S(j)和剩余能量E(j)，节点ni剩余能量期望值越大，则数据传输消耗的能量越少，同时为了保证下一跳节点性能较好，选择剩余能量和转播因子较高的节点作为下一跳节点。

根据能量消耗模型和式(3)，计算节点ni传输数据到下一跳节点nj的剩余能量期望值Er(i)，计算公式

使用贪心算法将节点的权值函数P(i，j)作为目标函数，将目标函数从大到小排列，选择出目标函数最大的节点作为下一跳节点，权值函数P(i，j)的表达式如下

其中，α，β，λ 为常数参数，且α+β+λ=1。节点根据权值函数选取局部最优的下一跳节点，局部最优解组合起来得到最优路径。

3 仿真结果与分析

本文利用NS2 对LEACH 协议、LEACH—C 协议和GIDR协议进行了模拟仿真，分别从网络生命周期与网络能量消耗方面来评价新协议的性能。本文以煤矿为背景，仿真时所取的是500 m×10 m 的长带状分布场景(场景1)，作为对比，另一个仿真场景(场景2)为70.7 m×70.7 m，Sink 节点的位置是(80，35)m，其他参数值同带状场景。带状场景的主要仿真参数设置如下:分布区域为500 m×10 m，节点数为100，Sink 节点位置为(510，5)m，节点初始能量为2 J，数据包为4 000 bit，概率因子α，β，λ 分别为0.3，0.6，0.1。

3.1 网络生命周期

如图3 所示，在场景2 中，LEACH—C 协议和GIDR 协议在生命周期上差异较小。然而在场景1 中，GIDR 协议明显优于LEACH 协议和LEACH—C 协议，如图4 所示，最大运行轮数为603 轮，本文对第一个节点死亡轮数、20%节点死亡轮数、50%节点死亡轮数、80%节点死亡轮数以及全部节点死亡轮数进行了比较，结果如表1 所示。

由表1 可以看出:GIDR 协议的第一个节点死亡时间比LEACH，LEACH—C 协议分别推迟了446%，45%，20%，50%，80%节点死亡时间同样得到了很大的改善，GIDR 协议的总运行轮数比LEACH 协议增加了43%，比LEACH—C协议增加了23%。之所以有如此大的改善是由于簇头节点发送数据到基站是经过定向最优的多跳路径通信的，能够延长网络的生命周期。

图3 场景2 中节点存活情况Fig 3 Node survival situation in number 2 scenario

图4 场景1 中节点存活情况Fig 4 Node survival situation in number 1 scenario

表1 三种协议生命周期对比结果Tab 1 Comparison results of lifetime cycle of three protocols

3.2 能量消耗

图5 是在带状场景1 下节点剩余能量和运行轮数之间的关系，从图中可以看出:GIDR 协议的剩余能量总是高于LEACH 协议和LEACH—C 协议。LEACH 协议在前100 轮时，剩余能量曲线成陡然下降趋势，LEACH—C 协议的剩余能量曲线波动比较大，而GIDR 协议的剩余能量曲线整体趋势平缓，说明GIDR 协议能量消耗更加均衡。总体分析看来，GIDR 协议在能量消耗和能耗均衡性方面都比LEACH 协议和LEACH—C 协议更具有优势。

4 结束语

本文针对煤矿井下环境特点，根据空间镶嵌理论进行了节点部署，通过分析监测环境空间特点，提出了一种能够减少能耗开销并均衡能耗的GIDR 协议。该算法在分簇时引入了剩余能量和转播因子，在混合多跳通信时本文通过锥形的定向区域限定了数据传输的方向并减少了其他节点的干扰，利用贪心思想获得最优路径。仿真实验表明:GIDR 协议在能量开销和均衡性等方面具有较好的性能，能够有效地延长网络生存时间，适用于煤矿井下特殊空间环境的安全监测。

图5 场景1 中剩余能量情况Fig 5 Residual energy situation in number 1 scenario

［1］ 申宝宏，雷 毅，郭玉辉.中国煤炭科学技术新进展［J］.煤炭学报，2011，36(11):1779－1783.

［2］ 胡曦明，董淑福，王晓东，等.无线传感器网络的军事应用模式研究进展［J］.传感器与微系统，2011，30(3):1－3.

［3］ 孙利民，李建中，陈 渝.无线传感器网络［M］.北京:清华大学出版社，2005:27－28.

［4］ 唐 勇，周明天，张 欣.无线传感器网络路由协议研究进展［J］.软件学报，2006，17(3):410－421.

［5］ Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-efficient communication protocol for wireless sensor networks［C］∥Proceedings of the 33rd Hawaii International Conference on System Sciences，2000:1－10.

［6］ Heinzelman W，Chandrakasan A，Balakrishnan H.An application specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660－670.

［7］ 龙际珍，陈沅涛，邓冬梅，等.基于LEACH 协议的助理簇头分簇算法［J］.计算机工程，2011，37(7):103－105.

［8］ 童孟军，关华丞.基于蚁群算法的能量均衡多路径路由算法的研究［J］.传感技术学报，2013，26(3):425－434.

［9］ 谢洁锐，刘才兴，胡月明，等.无线传感器网络的部署［J］.传感器与微系统，2007，26(1):4－7.

［10］Bollobas B.The art of mathematics:Coffee time in Memphis［M］.England:Cambridge University Press，2006.