礦井無線通信網(wǎng)絡(luò)中LEACH協(xié)議的改進

劉云翔++張偉

摘 要： 針對礦井下無線傳感器網(wǎng)絡(luò)通信的特點，對LEACH協(xié)議分簇進行優(yōu)化，并充分考慮能量和距離的因素，對簇頭節(jié)點的選取進行優(yōu)化，提出基于K?means++聚類的路由算法LEACH?KPPE，有效地改善了LEACH算法中簇頭節(jié)點分布不均、能耗不均以及網(wǎng)絡(luò)的穩(wěn)定性等問題。仿真實驗結(jié)果表明，該算法有效地改善了整個網(wǎng)絡(luò)的能耗，提高了能量的利用率，有效延長了網(wǎng)絡(luò)的生命周期。

關(guān)鍵詞： 礦井； 無線傳感網(wǎng)絡(luò)； LEACH協(xié)議； K?means++算法

中圖分類號： TN915.04?34 文獻標識碼： A 文章編號： 1004?373X（2017）09?0066?04

Abstract： According to the features of the wireless sensor network communication for mine， an LEACH protocol clustering is optimized. The factors of energy and distance are taken into full consideration to optimize the selection of cluster head nodes. The routing algorithm LEACH?KPPE based on K?means++ clustering is proposed to solve the problems of uneven cluster head node distribution， unbalanced energy consumption and network stability existing in the LEACH algorithm. The simulation experiment results show that the LEACH?KPPE algorithm improved the energy consumption of the whole network， enhance the energy utilization， and prolong the network life cycle effectively.

Keywords： mine； wireless sensor network； LEACH protocol； K?means++ algorithm

0 引 言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是由大量具有數(shù)據(jù)采集、數(shù)據(jù)處理以及通信能力的傳感器節(jié)點以自組織方式形成的一種拓撲動態(tài)變化的網(wǎng)絡(luò)[1?3]。其具有抗毀性強、自適應(yīng)性強以及能快速展開等優(yōu)點，因此被廣泛應(yīng)用于工業(yè)控制、環(huán)境監(jiān)測、交通控制、醫(yī)療護理、軍事等重要領(lǐng)域[4?6]。

開采煤炭作業(yè)主要是在井下進行，在無線傳感器網(wǎng)絡(luò)還未普及之前，在礦井下基本使用有線通信裝置。有線通信存在一定的弊端，發(fā)生安全事故時無法精確定位井下事發(fā)地點以及人員位置，煤礦地面人員不能及時準確地獲取井下具體信息[7]，因此不利于井下工作以及安全管理。通過利用無線傳感器網(wǎng)絡(luò)實現(xiàn)井下通信，無線安全系統(tǒng)能夠完善礦井下移動通信系統(tǒng)，并加強了礦井的安全管理。

根據(jù)煤礦井下巷道的特性，其網(wǎng)絡(luò)拓撲結(jié)構(gòu)是帶狀的，而且通信環(huán)境相對惡劣。與一般的無線通信網(wǎng)絡(luò)相同，其節(jié)點工作在一些無人監(jiān)控的區(qū)域，不易維護，自身能量有限且不能再生，所以高效、穩(wěn)定、節(jié)能的路由協(xié)議對整個無線傳感器網(wǎng)絡(luò)來說是相當(dāng)重要的。

LEACH（Low Energy Adaptive Clustering Hierarchy）協(xié)議是目前應(yīng)用較為廣泛的層次路由[8?9]，其能適用于一般的工作環(huán)境。但是針對礦井下的特殊環(huán)境，LEACH協(xié)議已經(jīng)不能滿足其要求，因此本文主要對LEACH協(xié)議進行研究并改進，提出一種基于K?means++聚類的路由算法LEACH?KPPE，使其能高效、穩(wěn)定地在礦井環(huán)境下正常工作。

1 LEACH協(xié)議

1.1 LEACH協(xié)議概述

LEACH協(xié)議是無線傳感器網(wǎng)絡(luò)中應(yīng)用較廣泛的一種層次路由協(xié)議，其工作流程主要分為兩個步驟：生成簇和傳輸數(shù)據(jù)信息。整個過程會周期性地重復(fù)進行，所以可以稱其一個周期內(nèi)的過程為“輪”[10]。每輪中首先從網(wǎng)絡(luò)中的節(jié)點隨機選出若干個較合適的節(jié)點作為簇頭，在選取簇頭前，LEACH算法中給出一個預(yù)先設(shè)定好的閾值此閾值的計算公式為：

式中：是網(wǎng)絡(luò)中簇頭占所有節(jié)點比例的期望值；是當(dāng)前周期循環(huán)選取簇頭的輪數(shù)；為不是簇頭節(jié)點的集合。

當(dāng)簇頭確定后，這些簇頭節(jié)點就會向其余節(jié)點發(fā)送消息，接收到信息的節(jié)點同時根據(jù)簇頭發(fā)出的信號強弱來選擇加入哪一個簇群。在完成分簇的工作之后，簇內(nèi)的非簇頭節(jié)點開始采集所需要的信息，然后將采集到的數(shù)據(jù)發(fā)送給自己所在簇的簇頭節(jié)點，接收到數(shù)據(jù)的簇頭節(jié)點對數(shù)據(jù)進行處理和整合，最后再將數(shù)據(jù)發(fā)送給基站。

1.2 LEACH協(xié)議應(yīng)用于煤礦井中的不足

對于不同的應(yīng)用環(huán)境而言，LEACH并不是最優(yōu)的路由協(xié)議，所以在煤礦井下這一特殊的環(huán)境中，LEACH也存在一些不足，其簇頭節(jié)點是隨機選擇的，這樣會導(dǎo)致簇頭節(jié)點分布不均勻，同時剩余能量較少的節(jié)點也有可能被選為簇頭節(jié)點，就會導(dǎo)致簇頭節(jié)點過早死亡，除此之外煤礦井下的通道一般都很長，針對這一特性，LEACH中單跳通信方式不再適用于煤礦井下通信。

2 LEACH?KPPE協(xié)議

針對LEACH應(yīng)用于煤礦井中的一些缺陷，本文在LEACH的基礎(chǔ)上提出一種改進后的LEACH?KPPE協(xié)議。LEACH?KPPE與原有的LEACH協(xié)議在主要工作流程上是一致的，都是周期性進行輪的重構(gòu)，每個輪也都包括建立簇和穩(wěn)定數(shù)據(jù)傳輸兩個階段。

2.1 建立簇階段

在建立簇時，將區(qū)域內(nèi)所有節(jié)點的位置以及剩余能量信息先發(fā)送給基站，再利用K?means++算法對網(wǎng)絡(luò)內(nèi)的節(jié)點進行聚類處理。K?means++是在K?means算法基礎(chǔ)上提出的一種算法，K?means首先從區(qū)域內(nèi)節(jié)點中隨機選擇個節(jié)點作為初始的聚類中心，但不同的聚類中心會出現(xiàn)完全不同的聚類結(jié)果，所以分簇結(jié)果可能不是最優(yōu)的。為解決這一問題，本文采用K?means++算法，其主要的工作過程如下：

（1） 先從區(qū)域內(nèi)節(jié)點中隨機選擇一個節(jié)點作為第一個聚類中心；

（2） 對于區(qū)域內(nèi)的每一個節(jié)點計算其與最近聚類中心（指已經(jīng)存在的聚類中心）的距離

（3） 選擇一個新的節(jié)點作為新的聚類中心，其中較大的節(jié)點被選為新的聚類中心的幾率較大；

（4） 重復(fù)執(zhí)行步驟（2）和步驟（3）直到選出個聚類中心；

（5） 分別計算剩下的節(jié)點到個聚類中心的相異度，將這些節(jié)點分別劃分到與其相異度最低的簇；

（6） 根據(jù)聚類結(jié)果，通過計算每個簇中所有節(jié)點維度的均值來重新更新這個聚類中心；

（7） 重復(fù)步驟（5）和步驟（6），直到準則函數(shù)開始收斂為止，最后每一個聚類就是一個簇。

其中選取新的聚類中心關(guān)鍵在于第（3）步，為了將與被選為下一個聚類中心的概率相關(guān)聯(lián)，先計算每個節(jié)點與其最近的聚類中心的距離并將這些保存到數(shù)組中，對這些距離全部求和得到再取一個隨機值Random并使這個隨機值能落在中，當(dāng)滿足時，此時的節(jié)點就是新的聚類中心。建立簇的流程圖如圖1所示。

完成分簇后還需對簇頭節(jié)點優(yōu)化，因為通過K?means++算法得出的簇頭節(jié)點在位置分布上已經(jīng)達到全局最優(yōu)，但此時選出的簇頭節(jié)點有可能剩余能量較低，這樣就會導(dǎo)致此節(jié)點過早死亡。由簇內(nèi)所有節(jié)點剩余能量的均值得出一個閾值，如果通過K?means++得出的簇頭節(jié)點的剩余能量高于此閾值，則此節(jié)點作為簇頭節(jié)點不更換，否則重新選取剩余能量高于所求閾值且離當(dāng)前簇頭節(jié)點最近的節(jié)點作為新的簇頭節(jié)點。這樣所選出的簇頭節(jié)點在位置分布以及剩余能量上都達到全局最優(yōu)，提升了整個網(wǎng)絡(luò)的能量均衡，延長了整個系統(tǒng)的生命周期。

2.2 數(shù)據(jù)穩(wěn)定傳輸階段

完成分簇工作后，開始進行數(shù)據(jù)傳輸。煤礦井下的通道一般都很長，這樣節(jié)點就會按著通道路線進行分布，從而生成的簇也會按著通道走向呈縱向排列，導(dǎo)致有些簇頭節(jié)點離基站很遠。如果采用LEACH中單跳方式進行通信，離基站很遠的簇頭節(jié)點向基站傳輸數(shù)據(jù)時就會因為消耗大量的能量而過早死亡。因此單一的單跳通信方式不適用于煤礦井下通信，本文在單跳通信的基礎(chǔ)上結(jié)合多跳方式進行數(shù)據(jù)傳輸。在簇內(nèi)其成員節(jié)點與簇頭節(jié)點之間的距離較近，直接使用單跳方式，當(dāng)簇頭節(jié)點離基站較近時也采用單跳方式，如果簇頭節(jié)點離基站較遠，則采用多跳路由傳遞信息。在采用多跳方式時，從簇頭節(jié)點中選出離基站最近的節(jié)點作為目標節(jié)點，離基站較遠的節(jié)點作為源節(jié)點，將其與目標節(jié)點之間的簇頭節(jié)點作為路由中繼，將數(shù)據(jù)發(fā)送給目標節(jié)點，最后由目標節(jié)點將數(shù)據(jù)直接傳給基站。

在源節(jié)點與目標節(jié)點之間進行多跳通信前，利用Floyd算法找出源節(jié)點與目標節(jié)點之間的最短路由。通過Floyd算法求最短路由時，需要對其初始化稍作修改，由于源節(jié)點與目標節(jié)點之間不直接通信，所以一開始將源節(jié)點與目標節(jié)點的距離初始化為無窮大，這樣最終可以由Floyd算法得出從源節(jié)點經(jīng)過若干中間簇頭節(jié)點之后到達目標節(jié)點的最短路由。

3 仿真結(jié)果及分析

本文在Matlab平臺對LEACH以及LEACH?KPPE協(xié)議進行仿真分析，主要通過整個網(wǎng)絡(luò)分簇結(jié)果、能耗以及節(jié)點的存活率這三個方面對比LEACH和LEACH?KPPE算法的性能。本文模擬將100個傳感器節(jié)點分布于100 m×100 m的網(wǎng)絡(luò)區(qū)域中，模擬仿真中參數(shù)設(shè)置如表1所示。

設(shè)定時，LEACH以及LEACH?KPPE算法分簇仿真結(jié)果如圖2所示，其中節(jié)點是隨機分布的，不同的標志符號表示不同的簇。圖2中的表示每個簇的簇頭節(jié)點。為了更有可比性，在LEACH仿真中特意將其初始化簇頭節(jié)點與LEACH?KPPE仿真得出的簇頭節(jié)點設(shè)為一致。對比圖2（a）和圖2（b）可以看出，由LEACH仿真得出的分簇結(jié)果是不均勻的，有的簇中節(jié)點分布過密，除此之外還出現(xiàn)了簇頭節(jié)點分布在簇邊緣的問題。相比而言，由LEACH?KPPE仿真得出的分簇結(jié)果更加均勻，而且簇頭節(jié)點大致分布在每個簇的中心區(qū)域。

圖3為網(wǎng)絡(luò)總能耗與其工作時間之間的關(guān)系變化，工作時間由具體輪數(shù)表示。從圖3中可以看出，相比LEACH算法，改進后的LEACH?KPPE算法在能耗上有明顯的改善。

LEACH算法在600輪左右網(wǎng)絡(luò)能量已經(jīng)耗盡，而LEACH?KPPE算法直至1 200輪后才耗盡，整個網(wǎng)絡(luò)的工作時間相比LEACH延長了一倍多。將網(wǎng)絡(luò)從開始運行到整個網(wǎng)絡(luò)能量耗盡定義為網(wǎng)絡(luò)的生命周期，改進后的LEACH?KPPE算法有效地延長了整個網(wǎng)絡(luò)的生命周期，所以在能耗性能上LEACH?KPPE算法比LEACH算法表現(xiàn)更好。

圖4是網(wǎng)絡(luò)剩余節(jié)點數(shù)與其工作時間的關(guān)系圖，在LEACH仿真中，網(wǎng)絡(luò)工作100輪后節(jié)點開始出現(xiàn)死亡，在600輪之后節(jié)點全部死亡；而LEACH?KPPE中第一個死亡節(jié)點在520輪之后，并且直到1 250輪之后才沒有剩余節(jié)點，這表明LEACH?KPPE算法更有效地使網(wǎng)絡(luò)中的能量均勻分布，從而有效降低了節(jié)點因能耗過大而過早死亡的概率。

4 結(jié) 論

將無線傳感器網(wǎng)絡(luò)應(yīng)用于工作環(huán)境惡劣的煤礦井下，能夠有效提高對煤礦井下工況以及設(shè)備信息的監(jiān)測效率，對加強煤礦井下的安全管理有著重大意義。路由協(xié)議對無線傳感器網(wǎng)絡(luò)而言是其關(guān)鍵核心所在，所以本文通過K?means++聚類算法對LEACH協(xié)議的分簇方式加以改進，并結(jié)合節(jié)點能量對簇頭選取進行優(yōu)化，并在一些簇頭節(jié)點與基站之間采用多跳方式進行通信，提出一種LEACH?KPPE路由協(xié)議，使其更適用于煤礦井下的無線通信。仿真結(jié)果表明，改進后的協(xié)議在分簇結(jié)果、能耗以及節(jié)點存活率這三個方面相對于LEACH協(xié)議都有著顯著的提高，從而有效地提高了網(wǎng)絡(luò)的生命周期和穩(wěn)定性。

參考文獻

[1] 孫利民，李建中.無線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.

[2] 王殊，閻毓杰，胡富平，等.無線傳感器網(wǎng)絡(luò)的理論及應(yīng)用[M].北京：北京航空航天大學(xué)出版社，2007.

[3] 張海燕，劉虹.基于K?means聚類的WSN能耗均衡路由算法[J].傳感技術(shù)學(xué)報，2011，24（11）：1639?1643.

[4] 林楠，史葦杭.無線傳感器LEACH算法的優(yōu)化及仿真[J].計算機仿真，2011，28（1）：178?182.

[5] 趙秀蘭，許秀蘭，李克清.基于LEACH協(xié)議的差異化分簇路由算法[J].計算機應(yīng)用研究，2013，30（3）：866?868.

[6] 單劍鋒，莊琴清，陳明.基于簇首概率優(yōu)化的LEACH協(xié)議改進[J].計算機技術(shù)與發(fā)展，2013，16（2）：104?108.

[7] 王聯(lián)春.基于GPS技術(shù)的井下人員定位系統(tǒng)應(yīng)用研究[J].煤炭技術(shù)，2012，31（10）：203?204.

[8] HEINZELMAN W R， CHANDRAKASAN A， BALAKBISHNAN H. Energy efficient communication protocol for wireless micro?sensor network [C]// Proceedings of the 33rd Hawaii International Conference on System Sciences. Washington， DC.： IEEE， 2000： 3005?3014.

[9] 劉智珺，李臘元，楊少華.基于能耗均衡的LEACH?DC協(xié)議的設(shè)計[J].計算機工程與設(shè)計，2012，33（4）：1337?1341.

[10] HANDY M J， HAASE M， TIMMERMANN D. Low energy adaptive clustering hierarchy with deterministic cluster?head selection [C]// Proceedings of the 4th IEEE Conference on Mobile and Wireless Communications Networks. Stockholm， Sweden： IEEE， 2002： 368?372.

[11] 林海峰，高德民，蔣安娜.基于流量控制的無線傳感器網(wǎng)絡(luò)生命期算法[J].計算機仿真，2016，33（2）：340?344.

[12] 李軍.無線傳感網(wǎng)絡(luò)自私節(jié)點檢測的軟件設(shè)計與仿真[J].計算機仿真，2016，33（6）：246?249.