An Improved Routing Algorithm Based on SPIN for WSN in Straight Narrow Tunnel

FANG Wangsheng，SUN Jian

(School of Information Engineering，Jiangxi University of Science and Technology，Ganzhou Jiangxi 341000 China)

An Improved Routing Algorithm Based on SPIN for WSN in Straight Narrow Tunnel

FANG Wangsheng*，SUN Jian

(School of Information Engineering，Jiangxi University of Science and Technology，Ganzhou Jiangxi 341000 China)

In order to effectively alleviate the problem that，the node closer to the Sink node，the earlier it will die in underground chain-type wireless sensor networks，this paper puts forward an improved algorithm based on the SPIN algorithm for WSN in underground，the algorithm combined with the narrow straight roadway model and multiple coverage model，using the gradient method of partitioning and judging the gradient information of received ADV to decision data information receiver，balance the energy consumption of entire network，and extend the network lifetime.The improved energy loss model algorithm can prolong the network lifetime efficiently，simulation results show that the improved algorithm can extend the network lifetime at least 5%than that of NCWSNFGM.

wireless sensor networks;routing algorithm;SPIN;gradient divide;straight narrow tunnel;chaintype networks

目前，矿产开采仍多为井下开采方式，每年由于各种原因的矿难导致了生命财产的重大损失。经调查，多数矿难是由于事故发生前未发现安全隐患或事故发生后救援不及时而造成的二次灾难。

无线传感器WSN(Wireless Sensor Networks)由于其造价低、易安装、易维护、环境适应性强等优点［1］，担负起井下环境信息采集的任务。但由于井下环境恶劣［2－4］和节点能量有限［5］，合理的路由机制是必须的。Qian Siwei和Guo Peng等人给出了一种利用备用节点来提高网络整体生命周期的方法［6］。Zhou Gongbo和Zhu Zhencai等人提出了新型链型无线传感器网络的瓦斯监测方案NCWSNFGM (Novel Chain-Type Wireless Sensor Network for Gas Monitoring)［7－8］。李鉴，石馨等人提出了能量均衡的非均匀分簇算法(EBUC-M)［9］。

上述学者均采用分区或者分簇的方式。分区方式中，节点采取轮休的工作模式，该模式虽然可以有效延长网络寿命，但是会增加信息相邻节点的传送路径，单次传送路径越长，节点能量消耗越大［10］。分簇方式中，簇头选举过程会占用较多时间，加大信息传送时延，降低网络的监控实时性。本文结合上述算法的优点，考虑到下一步工作中网络会添入移动节点，为了保持网络整体的路由统一性，选取基于信息协商的传感器路由协议SPIN(Sensor Protocols for Information via Negotiation)进行改进。改进型算法通过梯度划分和“三次判定”机制，可有效的延长网络生命周期，减小信息时延。合理的路由机制对提高井下开采工作的安全保障有重要的意义。

1 狭长直巷道空间模型

井下巷道根据空间特性和功能，分为垂直巷道、倾斜巷道和水平巷道三大类［10－11］，巷道可看作三维狭长空间，巷道内除少部分区域存在分支巷道外，大部分区域都可看作狭长巷道，而这些狭长巷道虽然可能存在部分弯曲，但大多数弯曲半径较大，也可看成狭长直巷道。因此本文只截取这些巷道中的某一段狭长直巷道来做研究，如图1所示。

图1各类节点在巷道底面的投影

图1 中黑色圆点表示安置在巷道侧壁上的Sink节点在巷道底面的投影，圆圈表示安置在巷道侧壁和巷道顶部的普通节点在巷道底面的投影，三角形和正方形分别表示巷道内的工作人员与矿车。

将图1简化后得到图2。

图2井下链状无线传感器网络

图2 中黑色圆点表示安置在巷道侧壁上的Sink节点在巷道底面的投影，圆圈表示安置在巷道侧壁和巷道顶部的普通节点在巷道底面的投影。

2 SPIN算法及相关公式

2.1 SPIN算法

SPIN算法采用协商的方式来解决信息“内爆”，其工作过程分为3个阶段［12－13］:广播新数据特征ADV(New Data Advertisement)、回复数据请求REQ (Request for Data)和传送数据信息DATA(Data Message)。如图3所示，数据传送前，A节点广播ADV信息，其临近节点B和节点C收到广播后，节点B表示对A的数据感兴趣，遂向A发送接受请求REQ，而后A接收到REQ后建立连接，传送DATA。

图3SPIN算法

2.2 SPIN算法相关公式

算法的能量主要消耗在信息的发送和接收过程中，节点发送信息时，能量消耗Etx为:其中l为发送字节长度;Eelec为接收或发送每比特数据时电路的能量消耗;d为发送方到接收方之间的距离;d0为临界距离，d0=(εfs/εamp)1/2。当两节点间距离小于临界距离时，发送节点的功率放大损耗采用自由空间模型，εfs为其功耗系数;两节点间距离大于临界距离时，发送节点的功率放大损耗采用多路径衰减模型，εamp为其功耗系数。

节点接收数据时，其能量消耗Erx为:

节点转发数据时，其能量消耗Efs为:

E=E+E=2l×Eelec+l×εfs×d2，d≤d0fxrxtx

{2l×Eelec+l×εamp×d4，d＞d0(3)

井下链状分布节点环境中，远离Sink节点的普通节点信息只能通过多跳方式将自身收集到的信息传送到Sink节点。普通节点越多，普通节点距Sink节点越远，整个网络的耗能越多，距离Sink节点越近的普通节点耗能越多。假设一个网络中，有1个Sink节点和N个普通节点，该Sink节点处于网络初始位置，普通节点链状分布，一个周期内，网络整体耗能Eall为:

其中最靠近Sink节点的普通节点除去传送自身收集的信息所消耗的能量外，还要额外承担转发其他节点的信息，这个过程所消耗的能量为(N－1)Efs。过重的转发任务会加剧该类节点的能量消耗，使其过早死亡。

3 改进型SPIN算法与相关公式

3.1 “三次判定”原理

为了更好的缓解信息内爆造成的时延和全网能量消耗均衡问题，从而达到延长网络生命周期的目的。本文在传统SPIN路由算法中引入梯度概念并采用“三次判定”机制:(1)判定自身梯度;(2)判定接收到的ADV中的梯度信息;(3)判定数据信息接收方。完整工作流程如图4所示。

梯度划分阶段:Sink节点首先广播梯度划分信号，该信号为固定功率为W的信号，各普通节点根据接收到的信号强度Wr和划分规则划分自身梯度。规定距离Sink节点越远，梯度值越大。第Kx个梯度的划分范围为:

图4 改进算法流程图

式(5)中1≤x≤i，Wrx为该梯度内节点接收到信号W的强度。

划分过程中，Sink节点的通信半径R应满足:

式(6)中L为狭长直巷道长度，D为巷道宽度。

若使划分后的梯度内节点都满足单跳通信，则该区间长度dx应满足:

式(7)中r为普通节点的通信半径。若满足于相邻梯度内任意两个节点都可以进行单跳通信，则该相邻梯度的区间长度d*x、d*x－1满足:

此时，梯度数量i必须满足

合理的梯度划分影响后续的主要传输方式。以上为第1次判定。

传输建立阶段:高梯度节点广播ADV请求，各临近节点接收到ADV后，对比ADV与自身的梯度特征值，若对此信息感兴趣且ADV中的梯度特征值大于或等于接收节点自身梯度特征值，则该接收节点对ADV发送节点回馈REQ请求。在REQ请求中，包含该节点的梯度值和工作状态值，处于空闲状态的值为0，处于工作状态的值为1。此为第2次判定。

数据传输阶段:原发送ADV节点收到REQ后，根据REQ中的信息，优先选取低梯度且工作状态值为0的节点进行单跳数据传送，其次选取低梯度且工作状态为1的节点进行进入等待状态传输，当低梯度无合适节点进行数据传输时，选取同梯度内且工作状态为0的节点进行多跳数据转发。当有多个相同优先级节点时，随机选取一个节点进行数据传送。此为第3次判定。

接收方接收完毕信息后，会再次查看自身梯度，若是自身梯度为1，则直接传送给Sink节点，若是自身梯度不为1，则继续向低梯度节点转发该信息，直到该信息到达Sink节点。

通过改进算法的详细流程，可以看出该算法仍是以多跳为主要方式，通过划分梯度来减少跳数，且梯度划分后，处于最靠近Sink节点的梯度内的普通节点都能转发其他梯度内节点收集到的信息，这样能平衡原本最靠近Sink节点的普通节点的能量消耗，进而延长网络整体寿命。另一方面，跳数的减少，直接减小网络的信息传送时延，使Sink节点可以很快的接收到各节点收集到的信息，时延越短，越能保证信息的实时性和准确性，越能提高井下生产工作的安全保障。不仅如此，通过梯度的划分，还可以有效的提高服务质量，不会因为某一个节点出现问题而导致整个网络出现故障，增强了网络的可靠性。

3.2 改进SPIN算法相关公式及对比结果

通过改进算法的详细流程，可以得到改进算法的能量损耗模型。假设网络中含有N个节点，i个梯度K1、K2、…、Ki，K1为最靠近Sink节点的梯度，Ki为最远离Sink节点的梯度，相对应的，每个梯度内含有n1、n2、…、ni个普通节点，则任一节点的能量损耗Es为:

D为该节点进行过的发送次数，包括发送自身信息和转发其他普通节点信息的次数。设该节点为m，所在梯度为Kx，1≤x≤i，其直接向梯度Kx－1的某个节点进行信息传送的概率为α，向同梯度内某个节点进行信息传送的概率为1－α;转发信息时，设该节点直接转发梯度Kx+1内节点的信息概率为β，转发同梯度内节点信息的概率为1－β，β不为定值，根据节点工作状态随机调整，p为m同梯度内节点，q为梯度Kx－1内节点，则:

Wr为该节点收到的梯度判定信号功率，WT为该节点所属的功率范围的最大值。由式(11)可以看出，同梯度内，距离Sink节点越近的普通节点，其直接向下一梯度进行信息传送的概率越高，反之，同梯度内距离Sink节点越远的节点，其通过同梯度内其他节点进行转发的概率越高。进而得到:

同梯度内，若两端节点能耗相同，我们可以认定为该网络能耗均衡，设该梯度Kx内，两端节点为nx1和nx，nx1为最靠近Sink节点的普通节点，nx为距离Sink节点最远的普通节点。则该两个节点的能量损耗Esnx1和Esnx为:

根据α的变动规律，可将式(15)和式(16)写为:

因为d(|1+nx－1－q|)≤d0，且d(|nx－p|)≤d0，也就是说该两个节点功率损耗的最大值相似，所以我们可以认为该两个节点的能量损耗接近均衡。

改进型算法中距离Sink节点最近的普通节点的能量损耗E1为:

对比SPIN算法中该位置节点的能量损耗可得:

因为β的取值范围为0≤β≤1，n1和N均为大于0的正整数，且n1＜N，所以式(20)的值小于0，即E1＜N×Efs。由此可见，改进型算法可以有效的缓解SPIN算法中该节点过早死亡的情况。

此时Kx梯度的普通节点能量总消耗Exall为:

Kx－1梯度的普通节点能量总消耗为:

q*为Kx－2梯度中的普通节点，p*为Kx－1梯度中的普通节点。当节点数目nx和nx－1满足Exall=E*xall时，可认定Kx梯度与Kx－1梯度的能量损耗相等。

接下来对比信息时延，设节点进行一次接收与发送所消耗的时间为t，则SPIN算法中最远端节点的信息传送到Sink节点所需时间Td为:

改进型算法中，最远端节点的信息传送到Sink节点所需时间T*d为:

将式(23)和式(24)进行对比可得:

因为i＜N，所以式(25)为负数，即说明改进算法在信息时延上比SPIN算法有更高的效率。

4 仿真结果及分析

仿真工具为MATLAB，实验参数为:巷道长度L=500 m，宽度D=3 m，Sink节点采用有源供电方式，普通节点初始能量为15 120 000 J(两节3 000 mAh的干电池)，Eelec=50 nj/bit，εfs=50 nj/bit，εamp=100 pj/(bit/m2)，监测频率为10 Hz，节点进行一次接收与发送所消耗的时间t=0.001 s，控制信息长度为8 byte，DATA数据信息长度为32 byte。仿真结果如图5～图7所示。

图5节点数目与网络寿命对比图

图5 表示在梯度为8的情况下，节点数目对网络寿命的影响。由图5可以看出，随着节点数目的增多，3种算法的网络寿命均逐渐延长，原因在于相邻节点间传输距离变短，减少了单个节点单次信息传送的能量消耗。对比可得，改进型算法比NCWSNFGM方法有小幅提高，其中在节点个数为200的情况下，改进型算法的网络寿命是NCWSNFGM方法的1.05倍，增幅为5%，改进型算法增幅不高的原因在于NCWSNFGM方法采用了数据融合技术，去掉了数据包中的冗余信息，节约了能量，而改进型算法中未进行数据融合，5%的增幅虽然不高，但是在井下大规模或超大规模无线传感器网络中，该数值的增幅可以有效减少成本和人力支出;相比较SPIN算法，改进型算法的网络寿命是其2.34倍，增幅为134%。对比可得出:改进型算法可有效延长网络寿命。

图6梯度数目与网络寿命对比图

图6 表示在节点数目为100的情况下，梯度数目对网络寿命的影响。由图6可以看出，梯度数目对SPIN算法几乎无影响;NCWSNFGM方法在梯度为1时所有节点都要同时工作，结合数据融合技术，网络寿命优于SPIN算法和改进型算法，在梯度数目为2至4的过程中，网络寿命出现降低的现象，原因在于该方法中节点轮休机制，梯度数目少时单个节点的覆盖范围过大，能量消耗提高，梯度数目为5时，网络寿命开始延长，原因在于单个节点的覆盖范围减小，能量消耗降低;改进型算法由于没有采用数据融合技术，在梯度为1的情况下，网络寿命近似于SPIN算法，随着梯度数目的增多，网络寿命逐渐提高，原因在于梯度增多使节点在通信半径内，可以将信息更高几率的直接传送至低梯度内节点，同时由于未采用轮休机制，降低了单个节点的覆盖负担，减少了能量消耗，且低梯度内节点可更有效的分担近Sink节点的信息转发工作。

统计3种算法在梯度为8，节点数为100时各1 000轮的平均时延，如图7所示，可以看出，SPIN算法的时延0.99 s，NCWSNFGM方法的时延为0.014 s，改进型算法的时延为0.027 s。与SPIN算法相比，改进型算法的信息时延仅为SPIN算法的2.7%，但是与NCWSNFGM方法相比，却是NCWSNFGM方法的193%。由此可以看出，改进型算法相比SPIN算法，信息时延上有很大进步，相比较NCWSNFGM方法，改进型算法有不足，根本原因在于改进型算法中的跳数比NCWSNFGM方法中多，跳数的增多导致信息时延变大。

图7 平均时延柱状图

5 总结

本文提出的一种基于SPIN的改进算法，通过引入梯度概念来规定信息传送方向，通过“三次判定”来选择工作流程，均衡网络能量消耗。通过比较改进前后算法的能量消耗模型可以得出，改进后的算法能有效延长网络寿命;仿真实验结果显示，改进型算法可有效延长网络寿命并减小信息时延。由于多重覆盖会产生信息冗余，采取哪种方式进行数据融合和该环境中移动节点采取哪种路由方式，是下一步需要解决的问题。

［1］Stavrou E，Pitsillides A.A Ssurvey on Secure Multipath Routing Protocols in WSNs［J］.Computer Networks，2010，54(13):2215－2238.

［2］周公博，朱真才，陈光柱，等.矿井巷道无线传感器网络分层拓扑控制策略［J］.煤炭学报，2010，35(2):333－337.

［3］陈鹏，刘爱军，刘潞峰，等郭华.矿井电磁环境及电波传播特性的研究［J］.通信技术，2010，43(3):2010，54－56.

［4］周莉娟，陈光柱，罗成名.采煤工作面无线传感器网络的无线通信信道建模［J］.传感技术学报，2010，23(5):722－726.

［5］吕涛，施伟斌，范坤坤，等.WSN节点电池供电性能测试研究［J］.传感技术学报，2013，26(10):1457－1462.

［6］Qian Siwei，Guo Peng，Jiang Tao.A Novel Llifetime-Enhanced Eployment Strategy for Chain-Type Wireless Sensor Networks［C］//IEEE International Conference on Communications(ICC)，2012:513－517.

［7］Zhou Gongbo，Zhu Zhencai，Chen Guangzhu.Et al.Energy-Efficient Chain-Type Wireless Sensor Network for Gas Monitoring［C］//Information and Computing Science，2009(2):125－128.

［8］Zhu Zhencai，Zhou Gongbo，Chen Guangzhu.Chain-Ttype Wireless Underground Mine Sensor Networks for Gas Monitoring［J］.Advanced Science Letters，2011，4(2):391－399.

［9］李鉴，石馨，刘贺平.煤矿巷道无线传感器网络非均匀分簇数据传送机制［J］.地球科学:中国地质大学学报，2013(1):195－200.

［10］范新运，王福豹，任丰原.无线传感器网络的路由协议［J］.计算机测量与控制，2005，13(9):1010－1013.

［11］Han Guorui，Zhang Wenmei，Zhang Y P.An Experiment Study of the Propagation of Radio Waves in a Scaled Model of Long-Wall Coal Mining Tunnels［J］.IEEE Antennas and Wireless Propagation Letters，2009(8):502－504.

［12］沈明玉，郑立坤.WSN中SPIN路由协议的改进［J］.计算机工程，2012，38(5):86－88.

［13］Kulik J，Heinzelman W，Balakrishnan H.Negotiation-Based Protocols for Disseminating Information in Wireless Sensor Networks［J］.Wireless Networks，2002，8(2):169－185.

方旺盛(1963－)，男，教授，硕士研究生导师，主要研究方向为无线传感器网络，数字水印，基因表达式编程等，fangwangsheng@163.com;

孙建(1987－)，男，硕士研究生，研究方向为无线传感器网络，sj3344101 @163.com。

狭长直巷道中WSN的SPIN路由算法的改进

方旺盛*，孙建
(江西理工大学信息工程学院，江西赣州341000)

为了解决井下链状无线传感器网络中距离Sink节点越近的节点越早死亡的问题，提出了一种井下WSN基于SPIN路由协议的改进算法，该算法结合狭长直巷道模型与多重覆盖模型，运用梯度划分的方法，通过判定彼此梯度信息决定数据信息接收方，来均衡整个网络的能量消耗，延长网络寿命。对比改进前后的能量损耗模型可知，改进后的算法能有效延长网络寿命，实验表明，该算法较NCWSNFGM方案可延长至少5%的网络寿命。

无线传感器网络;路由算法;SPIN;梯度划分;狭长直巷道;链状网络

TP212.9

A

1004－1699(2014)04－0564－06

2014－01－17修改日期:2014－03－26

C:6150P

10.3969/j.issn.1004－1699.2014.04.025