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

目前，礦產(chǎn)開采仍多為井下開采方式，每年由于各種原因的礦難導致了生命財產(chǎn)的重大損失。經(jīng)調查，多數(shù)礦難是由于事故發(fā)生前未發(fā)現(xiàn)安全隱患或事故發(fā)生后救援不及時而造成的二次災難。

無線傳感器WSN(Wireless Sensor Networks)由于其造價低、易安裝、易維護、環(huán)境適應性強等優(yōu)點［1］，擔負起井下環(huán)境信息采集的任務。但由于井下環(huán)境惡劣［2－4］和節(jié)點能量有限［5］，合理的路由機制是必須的。Qian Siwei和Guo Peng等人給出了一種利用備用節(jié)點來提高網(wǎng)絡整體生命周期的方法［6］。Zhou Gongbo和Zhu Zhencai等人提出了新型鏈型無線傳感器網(wǎng)絡的瓦斯監(jiān)測方案NCWSNFGM (Novel Chain-Type Wireless Sensor Network for Gas Monitoring)［7－8］。李鑒，石馨等人提出了能量均衡的非均勻分簇算法(EBUC-M)［9］。

上述學者均采用分區(qū)或者分簇的方式。分區(qū)方式中，節(jié)點采取輪休的工作模式，該模式雖然可以有效延長網(wǎng)絡壽命，但是會增加信息相鄰節(jié)點的傳送路徑，單次傳送路徑越長，節(jié)點能量消耗越大［10］。分簇方式中，簇頭選舉過程會占用較多時間，加大信息傳送時延，降低網(wǎng)絡的監(jiān)控實時性。本文結合上述算法的優(yōu)點，考慮到下一步工作中網(wǎng)絡會添入移動節(jié)點，為了保持網(wǎng)絡整體的路由統(tǒng)一性，選取基于信息協(xié)商的傳感器路由協(xié)議SPIN(Sensor Protocols for Information via Negotiation)進行改進。改進型算法通過梯度劃分和“三次判定”機制，可有效的延長網(wǎng)絡生命周期，減小信息時延。合理的路由機制對提高井下開采工作的安全保障有重要的意義。

1 狹長直巷道空間模型

井下巷道根據(jù)空間特性和功能，分為垂直巷道、傾斜巷道和水平巷道三大類［10－11］，巷道可看作三維狹長空間，巷道內(nèi)除少部分區(qū)域存在分支巷道外，大部分區(qū)域都可看作狹長巷道，而這些狹長巷道雖然可能存在部分彎曲，但大多數(shù)彎曲半徑較大，也可看成狹長直巷道。因此本文只截取這些巷道中的某一段狹長直巷道來做研究，如圖1所示。

圖1各類節(jié)點在巷道底面的投影

圖1 中黑色圓點表示安置在巷道側壁上的Sink節(jié)點在巷道底面的投影，圓圈表示安置在巷道側壁和巷道頂部的普通節(jié)點在巷道底面的投影，三角形和正方形分別表示巷道內(nèi)的工作人員與礦車。

將圖1簡化后得到圖2。

圖2井下鏈狀無線傳感器網(wǎng)絡

圖2 中黑色圓點表示安置在巷道側壁上的Sink節(jié)點在巷道底面的投影，圓圈表示安置在巷道側壁和巷道頂部的普通節(jié)點在巷道底面的投影。

2 SPIN算法及相關公式

2.1 SPIN算法

SPIN算法采用協(xié)商的方式來解決信息“內(nèi)爆”，其工作過程分為3個階段［12－13］:廣播新數(shù)據(jù)特征ADV(New Data Advertisement)、回復數(shù)據(jù)請求REQ (Request for Data)和傳送數(shù)據(jù)信息DATA(Data Message)。如圖3所示，數(shù)據(jù)傳送前，A節(jié)點廣播ADV信息，其臨近節(jié)點B和節(jié)點C收到廣播后，節(jié)點B表示對A的數(shù)據(jù)感興趣，遂向A發(fā)送接受請求REQ，而后A接收到REQ后建立連接，傳送DATA。

圖3SPIN算法

2.2 SPIN算法相關公式

算法的能量主要消耗在信息的發(fā)送和接收過程中，節(jié)點發(fā)送信息時，能量消耗Etx為:其中l(wèi)為發(fā)送字節(jié)長度;Eelec為接收或發(fā)送每比特數(shù)據(jù)時電路的能量消耗;d為發(fā)送方到接收方之間的距離;d0為臨界距離，d0=(εfs/εamp)1/2。當兩節(jié)點間距離小于臨界距離時，發(fā)送節(jié)點的功率放大損耗采用自由空間模型，εfs為其功耗系數(shù);兩節(jié)點間距離大于臨界距離時，發(fā)送節(jié)點的功率放大損耗采用多路徑衰減模型，εamp為其功耗系數(shù)。

節(jié)點接收數(shù)據(jù)時，其能量消耗Erx為:

節(jié)點轉發(fā)數(shù)據(jù)時，其能量消耗Efs為:

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

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

井下鏈狀分布節(jié)點環(huán)境中，遠離Sink節(jié)點的普通節(jié)點信息只能通過多跳方式將自身收集到的信息傳送到Sink節(jié)點。普通節(jié)點越多，普通節(jié)點距Sink節(jié)點越遠，整個網(wǎng)絡的耗能越多，距離Sink節(jié)點越近的普通節(jié)點耗能越多。假設一個網(wǎng)絡中，有1個Sink節(jié)點和N個普通節(jié)點，該Sink節(jié)點處于網(wǎng)絡初始位置，普通節(jié)點鏈狀分布，一個周期內(nèi)，網(wǎng)絡整體耗能Eall為:

其中最靠近Sink節(jié)點的普通節(jié)點除去傳送自身收集的信息所消耗的能量外，還要額外承擔轉發(fā)其他節(jié)點的信息，這個過程所消耗的能量為(N－1)Efs。過重的轉發(fā)任務會加劇該類節(jié)點的能量消耗，使其過早死亡。

3 改進型SPIN算法與相關公式

3.1 “三次判定”原理

為了更好的緩解信息內(nèi)爆造成的時延和全網(wǎng)能量消耗均衡問題，從而達到延長網(wǎng)絡生命周期的目的。本文在傳統(tǒng)SPIN路由算法中引入梯度概念并采用“三次判定”機制:(1)判定自身梯度;(2)判定接收到的ADV中的梯度信息;(3)判定數(shù)據(jù)信息接收方。完整工作流程如圖4所示。

梯度劃分階段:Sink節(jié)點首先廣播梯度劃分信號，該信號為固定功率為W的信號，各普通節(jié)點根據(jù)接收到的信號強度Wr和劃分規(guī)則劃分自身梯度。規(guī)定距離Sink節(jié)點越遠，梯度值越大。第Kx個梯度的劃分范圍為:

圖4 改進算法流程圖

式(5)中1≤x≤i，Wrx為該梯度內(nèi)節(jié)點接收到信號W的強度。

劃分過程中，Sink節(jié)點的通信半徑R應滿足:

式(6)中L為狹長直巷道長度，D為巷道寬度。

若使劃分后的梯度內(nèi)節(jié)點都滿足單跳通信，則該區(qū)間長度dx應滿足:

式(7)中r為普通節(jié)點的通信半徑。若滿足于相鄰梯度內(nèi)任意兩個節(jié)點都可以進行單跳通信，則該相鄰梯度的區(qū)間長度d*x、d*x－1滿足:

此時，梯度數(shù)量i必須滿足

合理的梯度劃分影響后續(xù)的主要傳輸方式。以上為第1次判定。

傳輸建立階段:高梯度節(jié)點廣播ADV請求，各臨近節(jié)點接收到ADV后，對比ADV與自身的梯度特征值，若對此信息感興趣且ADV中的梯度特征值大于或等于接收節(jié)點自身梯度特征值，則該接收節(jié)點對ADV發(fā)送節(jié)點回饋REQ請求。在REQ請求中，包含該節(jié)點的梯度值和工作狀態(tài)值，處于空閑狀態(tài)的值為0，處于工作狀態(tài)的值為1。此為第2次判定。

數(shù)據(jù)傳輸階段:原發(fā)送ADV節(jié)點收到REQ后，根據(jù)REQ中的信息，優(yōu)先選取低梯度且工作狀態(tài)值為0的節(jié)點進行單跳數(shù)據(jù)傳送，其次選取低梯度且工作狀態(tài)為1的節(jié)點進行進入等待狀態(tài)傳輸，當?shù)吞荻葻o合適節(jié)點進行數(shù)據(jù)傳輸時，選取同梯度內(nèi)且工作狀態(tài)為0的節(jié)點進行多跳數(shù)據(jù)轉發(fā)。當有多個相同優(yōu)先級節(jié)點時，隨機選取一個節(jié)點進行數(shù)據(jù)傳送。此為第3次判定。

接收方接收完畢信息后，會再次查看自身梯度，若是自身梯度為1，則直接傳送給Sink節(jié)點，若是自身梯度不為1，則繼續(xù)向低梯度節(jié)點轉發(fā)該信息，直到該信息到達Sink節(jié)點。

通過改進算法的詳細流程，可以看出該算法仍是以多跳為主要方式，通過劃分梯度來減少跳數(shù)，且梯度劃分后，處于最靠近Sink節(jié)點的梯度內(nèi)的普通節(jié)點都能轉發(fā)其他梯度內(nèi)節(jié)點收集到的信息，這樣能平衡原本最靠近Sink節(jié)點的普通節(jié)點的能量消耗，進而延長網(wǎng)絡整體壽命。另一方面，跳數(shù)的減少，直接減小網(wǎng)絡的信息傳送時延，使Sink節(jié)點可以很快的接收到各節(jié)點收集到的信息，時延越短，越能保證信息的實時性和準確性，越能提高井下生產(chǎn)工作的安全保障。不僅如此，通過梯度的劃分，還可以有效的提高服務質量，不會因為某一個節(jié)點出現(xiàn)問題而導致整個網(wǎng)絡出現(xiàn)故障，增強了網(wǎng)絡的可靠性。

3.2 改進SPIN算法相關公式及對比結果

通過改進算法的詳細流程，可以得到改進算法的能量損耗模型。假設網(wǎng)絡中含有N個節(jié)點，i個梯度K1、K2、…、Ki，K1為最靠近Sink節(jié)點的梯度，Ki為最遠離Sink節(jié)點的梯度，相對應的，每個梯度內(nèi)含有n1、n2、…、ni個普通節(jié)點，則任一節(jié)點的能量損耗Es為:

D為該節(jié)點進行過的發(fā)送次數(shù)，包括發(fā)送自身信息和轉發(fā)其他普通節(jié)點信息的次數(shù)。設該節(jié)點為m，所在梯度為Kx，1≤x≤i，其直接向梯度Kx－1的某個節(jié)點進行信息傳送的概率為α，向同梯度內(nèi)某個節(jié)點進行信息傳送的概率為1－α;轉發(fā)信息時，設該節(jié)點直接轉發(fā)梯度Kx+1內(nèi)節(jié)點的信息概率為β，轉發(fā)同梯度內(nèi)節(jié)點信息的概率為1－β，β不為定值，根據(jù)節(jié)點工作狀態(tài)隨機調整，p為m同梯度內(nèi)節(jié)點，q為梯度Kx－1內(nèi)節(jié)點，則:

Wr為該節(jié)點收到的梯度判定信號功率，WT為該節(jié)點所屬的功率范圍的最大值。由式(11)可以看出，同梯度內(nèi)，距離Sink節(jié)點越近的普通節(jié)點，其直接向下一梯度進行信息傳送的概率越高，反之，同梯度內(nèi)距離Sink節(jié)點越遠的節(jié)點，其通過同梯度內(nèi)其他節(jié)點進行轉發(fā)的概率越高。進而得到:

同梯度內(nèi)，若兩端節(jié)點能耗相同，我們可以認定為該網(wǎng)絡能耗均衡，設該梯度Kx內(nèi)，兩端節(jié)點為nx1和nx，nx1為最靠近Sink節(jié)點的普通節(jié)點，nx為距離Sink節(jié)點最遠的普通節(jié)點。則該兩個節(jié)點的能量損耗Esnx1和Esnx為:

根據(jù)α的變動規(guī)律，可將式(15)和式(16)寫為:

因為d(|1+nx－1－q|)≤d0，且d(|nx－p|)≤d0，也就是說該兩個節(jié)點功率損耗的最大值相似，所以我們可以認為該兩個節(jié)點的能量損耗接近均衡。

改進型算法中距離Sink節(jié)點最近的普通節(jié)點的能量損耗E1為:

對比SPIN算法中該位置節(jié)點的能量損耗可得:

因為β的取值范圍為0≤β≤1，n1和N均為大于0的正整數(shù)，且n1＜N，所以式(20)的值小于0，即E1＜N×Efs。由此可見，改進型算法可以有效的緩解SPIN算法中該節(jié)點過早死亡的情況。

此時Kx梯度的普通節(jié)點能量總消耗Exall為:

Kx－1梯度的普通節(jié)點能量總消耗為:

q*為Kx－2梯度中的普通節(jié)點，p*為Kx－1梯度中的普通節(jié)點。當節(jié)點數(shù)目nx和nx－1滿足Exall=E*xall時，可認定Kx梯度與Kx－1梯度的能量損耗相等。

接下來對比信息時延，設節(jié)點進行一次接收與發(fā)送所消耗的時間為t，則SPIN算法中最遠端節(jié)點的信息傳送到Sink節(jié)點所需時間Td為:

改進型算法中，最遠端節(jié)點的信息傳送到Sink節(jié)點所需時間T*d為:

將式(23)和式(24)進行對比可得:

因為i＜N，所以式(25)為負數(shù)，即說明改進算法在信息時延上比SPIN算法有更高的效率。

4 仿真結果及分析

仿真工具為MATLAB，實驗參數(shù)為:巷道長度L=500 m，寬度D=3 m，Sink節(jié)點采用有源供電方式，普通節(jié)點初始能量為15 120 000 J(兩節(jié)3 000 mAh的干電池)，Eelec=50 nj/bit，εfs=50 nj/bit，εamp=100 pj/(bit/m2)，監(jiān)測頻率為10 Hz，節(jié)點進行一次接收與發(fā)送所消耗的時間t=0.001 s，控制信息長度為8 byte，DATA數(shù)據(jù)信息長度為32 byte。仿真結果如圖5～圖7所示。

圖5節(jié)點數(shù)目與網(wǎng)絡壽命對比圖

圖5 表示在梯度為8的情況下，節(jié)點數(shù)目對網(wǎng)絡壽命的影響。由圖5可以看出，隨著節(jié)點數(shù)目的增多，3種算法的網(wǎng)絡壽命均逐漸延長，原因在于相鄰節(jié)點間傳輸距離變短，減少了單個節(jié)點單次信息傳送的能量消耗。對比可得，改進型算法比NCWSNFGM方法有小幅提高，其中在節(jié)點個數(shù)為200的情況下，改進型算法的網(wǎng)絡壽命是NCWSNFGM方法的1.05倍，增幅為5%，改進型算法增幅不高的原因在于NCWSNFGM方法采用了數(shù)據(jù)融合技術，去掉了數(shù)據(jù)包中的冗余信息，節(jié)約了能量，而改進型算法中未進行數(shù)據(jù)融合，5%的增幅雖然不高，但是在井下大規(guī)?；虺笠?guī)模無線傳感器網(wǎng)絡中，該數(shù)值的增幅可以有效減少成本和人力支出;相比較SPIN算法，改進型算法的網(wǎng)絡壽命是其2.34倍，增幅為134%。對比可得出:改進型算法可有效延長網(wǎng)絡壽命。

圖6梯度數(shù)目與網(wǎng)絡壽命對比圖

圖6 表示在節(jié)點數(shù)目為100的情況下，梯度數(shù)目對網(wǎng)絡壽命的影響。由圖6可以看出，梯度數(shù)目對SPIN算法幾乎無影響;NCWSNFGM方法在梯度為1時所有節(jié)點都要同時工作，結合數(shù)據(jù)融合技術，網(wǎng)絡壽命優(yōu)于SPIN算法和改進型算法，在梯度數(shù)目為2至4的過程中，網(wǎng)絡壽命出現(xiàn)降低的現(xiàn)象，原因在于該方法中節(jié)點輪休機制，梯度數(shù)目少時單個節(jié)點的覆蓋范圍過大，能量消耗提高，梯度數(shù)目為5時，網(wǎng)絡壽命開始延長，原因在于單個節(jié)點的覆蓋范圍減小，能量消耗降低;改進型算法由于沒有采用數(shù)據(jù)融合技術，在梯度為1的情況下，網(wǎng)絡壽命近似于SPIN算法，隨著梯度數(shù)目的增多，網(wǎng)絡壽命逐漸提高，原因在于梯度增多使節(jié)點在通信半徑內(nèi)，可以將信息更高幾率的直接傳送至低梯度內(nèi)節(jié)點，同時由于未采用輪休機制，降低了單個節(jié)點的覆蓋負擔，減少了能量消耗，且低梯度內(nèi)節(jié)點可更有效的分擔近Sink節(jié)點的信息轉發(fā)工作。

統(tǒng)計3種算法在梯度為8，節(jié)點數(shù)為100時各1 000輪的平均時延，如圖7所示，可以看出，SPIN算法的時延0.99 s，NCWSNFGM方法的時延為0.014 s，改進型算法的時延為0.027 s。與SPIN算法相比，改進型算法的信息時延僅為SPIN算法的2.7%，但是與NCWSNFGM方法相比，卻是NCWSNFGM方法的193%。由此可以看出，改進型算法相比SPIN算法，信息時延上有很大進步，相比較NCWSNFGM方法，改進型算法有不足，根本原因在于改進型算法中的跳數(shù)比NCWSNFGM方法中多，跳數(shù)的增多導致信息時延變大。

圖7 平均時延柱狀圖

5 總結

本文提出的一種基于SPIN的改進算法，通過引入梯度概念來規(guī)定信息傳送方向，通過“三次判定”來選擇工作流程，均衡網(wǎng)絡能量消耗。通過比較改進前后算法的能量消耗模型可以得出，改進后的算法能有效延長網(wǎng)絡壽命;仿真實驗結果顯示，改進型算法可有效延長網(wǎng)絡壽命并減小信息時延。由于多重覆蓋會產(chǎn)生信息冗余，采取哪種方式進行數(shù)據(jù)融合和該環(huán)境中移動節(jié)點采取哪種路由方式，是下一步需要解決的問題。

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

［2］周公博，朱真才，陳光柱，等.礦井巷道無線傳感器網(wǎng)絡分層拓撲控制策略［J］.煤炭學報，2010，35(2):333－337.

［3］陳鵬，劉愛軍，劉潞峰，等郭華.礦井電磁環(huán)境及電波傳播特性的研究［J］.通信技術，2010，43(3):2010，54－56.

［4］周莉娟，陳光柱，羅成名.采煤工作面無線傳感器網(wǎng)絡的無線通信信道建模［J］.傳感技術學報，2010，23(5):722－726.

［5］呂濤，施偉斌，范坤坤，等.WSN節(jié)點電池供電性能測試研究［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］李鑒，石馨，劉賀平.煤礦巷道無線傳感器網(wǎng)絡非均勻分簇數(shù)據(jù)傳送機制［J］.地球科學:中國地質大學學報，2013(1):195－200.

［10］范新運，王福豹，任豐原.無線傳感器網(wǎng)絡的路由協(xié)議［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路由協(xié)議的改進［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－)，男，教授，碩士研究生導師，主要研究方向為無線傳感器網(wǎng)絡，數(shù)字水印，基因表達式編程等，fangwangsheng@163.com;

孫建(1987－)，男，碩士研究生，研究方向為無線傳感器網(wǎng)絡，sj3344101 @163.com。

狹長直巷道中WSN的SPIN路由算法的改進

方旺盛*，孫建
(江西理工大學信息工程學院，江西贛州341000)

為了解決井下鏈狀無線傳感器網(wǎng)絡中距離Sink節(jié)點越近的節(jié)點越早死亡的問題，提出了一種井下WSN基于SPIN路由協(xié)議的改進算法，該算法結合狹長直巷道模型與多重覆蓋模型，運用梯度劃分的方法，通過判定彼此梯度信息決定數(shù)據(jù)信息接收方，來均衡整個網(wǎng)絡的能量消耗，延長網(wǎng)絡壽命。對比改進前后的能量損耗模型可知，改進后的算法能有效延長網(wǎng)絡壽命，實驗表明，該算法較NCWSNFGM方案可延長至少5%的網(wǎng)絡壽命。

無線傳感器網(wǎng)絡;路由算法;SPIN;梯度劃分;狹長直巷道;鏈狀網(wǎng)絡

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