徐小玲 劉美

（廣東石油化工學(xué)院計(jì)算機(jī)與電子信息學(xué)院）

礦井下無線傳感器網(wǎng)絡(luò)分簇算法研究

徐小玲 劉美

（廣東石油化工學(xué)院計(jì)算機(jī)與電子信息學(xué)院）

礦井下采用分簇解決信息沖突問題，為了同時(shí)滿足人員節(jié)點(diǎn)定位精度和能耗要求，提出了一種基于人員節(jié)點(diǎn)與簇首的位置誤差和通信能量消耗綜合考慮的粒子群分簇算法。仿真結(jié)果表明：在能耗上，基于通信能耗和位置誤差考慮的分簇算法比基于能耗考慮的分簇算法提高了2.22%，但位置誤差卻降低了8.11%。算法在實(shí)現(xiàn)分簇、增加系統(tǒng)可靠性的同時(shí)，最大限度地降低了對資源的使用，滿足了定位精度的要求。在人員密集的煤礦井下，該算法可將位置誤差進(jìn)一步降低。

分簇；位置誤差；能耗；粒子群

1引言

利用無線傳感器網(wǎng)絡(luò)組建的井下安全監(jiān)測系統(tǒng)通過使用功能不同的節(jié)點(diǎn)，隨時(shí)掌握井下人員的動(dòng)態(tài)分布。系統(tǒng)中，人員節(jié)點(diǎn)借助信標(biāo)節(jié)點(diǎn)將井下人員的位置信息傳送到控制臺從而了解礦井下的情況。由于在煤礦主巷道、人車、采掘工作面等區(qū)域人員較為密集，當(dāng)多個(gè)人員節(jié)點(diǎn)同時(shí)與信標(biāo)節(jié)點(diǎn)通信會造成信號沖突，甚至導(dǎo)致網(wǎng)絡(luò)處于癱瘓，通信無法進(jìn)行。為了避免通信沖突，可采用不讓每個(gè)人員節(jié)點(diǎn)都向信標(biāo)節(jié)點(diǎn)發(fā)送信息，而只從中選出一個(gè)代表向信標(biāo)節(jié)點(diǎn)發(fā)送信息，即采用成簇來解決這一問題。

2 相關(guān)工作

近年來，研究人員提出了多種傳感器網(wǎng)絡(luò)的分簇算法，其中W. Heinzelma等人提出的低功耗自適應(yīng)分簇算法LEACH[1]。LEACH有效的節(jié)省了能量消耗，但它沒有考慮到節(jié)點(diǎn)分布的拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)的能量問題，這種情況下簇內(nèi)的能量消耗并不是最優(yōu)值。文獻(xiàn)[2]應(yīng)用粒子群算法解決網(wǎng)絡(luò)分簇問題，提出均勻分簇的思想以最小化節(jié)點(diǎn)能耗。但對于節(jié)點(diǎn)分布不均勻的網(wǎng)絡(luò)，這種分簇方法可能造成各簇?cái)?shù)量規(guī)模相等。而幾何規(guī)模差異較大的情況，會造成簇間消耗能量不均。文獻(xiàn)[3]提出一種具有能量感知能力的分簇策略，采用PSO算法優(yōu)化選擇分簇方式，既最小化簇內(nèi)距離，又最優(yōu)化網(wǎng)絡(luò)能耗，有效延長網(wǎng)絡(luò)生存周期。但它沒有考慮簇頭節(jié)點(diǎn)傳輸信息至基站時(shí)的能耗不均，易導(dǎo)致距離基站較遠(yuǎn)的節(jié)點(diǎn)成塊死亡，網(wǎng)絡(luò)能量消耗不均衡。如Thanongsak H.提出通過中繼傳輸來延長網(wǎng)絡(luò)的生存期，也有少量的文獻(xiàn)研究分簇路由中的簇內(nèi)通信方式，如孫勇等[4]提出了時(shí)分混合通信方案，張志東等[5]提出楔形多跳方案減小網(wǎng)絡(luò)能耗。

本文根據(jù)井下分簇的要求，把節(jié)點(diǎn)與簇首的位置誤差和通信能耗作為優(yōu)化目標(biāo)函數(shù)的主要指標(biāo)建立傳感器節(jié)點(diǎn)成簇的數(shù)學(xué)模型，通過采用最近鄰進(jìn)行初始成簇并采用粒子群優(yōu)化算法實(shí)現(xiàn)節(jié)點(diǎn)重新組簇，盡可能快地得到最優(yōu)成簇結(jié)果。

3 節(jié)點(diǎn)成簇目標(biāo)函數(shù)設(shè)計(jì)

3.1 節(jié)點(diǎn)成簇能耗考慮

節(jié)點(diǎn)的能量消耗一般由感應(yīng)、數(shù)據(jù)處理、節(jié)點(diǎn)間的通信三方面構(gòu)成。而占能量消耗主體的就是節(jié)點(diǎn)之間的通信能耗，因此在算法評估時(shí)只考慮通信能耗，忽略其他能耗；本文運(yùn)用無線電通信模型，通信能耗表示為式(1)：

節(jié)點(diǎn)接收lbit長度數(shù)據(jù)所消耗能量為：

其中Eelec表示發(fā)射電路損耗的能量。若傳輸距離小于閾值r，則功率放大損耗采用自由空間模型；若傳輸距離大于等于閾值r，采用多路徑衰減模型。εmp、εfs分別為兩種模型中功率放大所需的能量。由此可見總能量E主要取決于d，通信能量消耗最小化可以等效為d之和最小化。

而距離的測量，由于受傳播環(huán)境的影響，電磁波在井下的傳播不能用自由空間傳播模型來描述，從文獻(xiàn)[6]可知，一種對數(shù)正態(tài)分布模型可對電磁波井下傳播與式(3)近似。

式中，RSSI(d)表示節(jié)點(diǎn)接收的信號強(qiáng)度，單位為dBm；PT為傳送信號的強(qiáng)度，PT?。?5dBm；d0是相對于人員節(jié)點(diǎn)的參考距離，d0取1m；Pr(d0)是該參考點(diǎn)處的信號功率。α則通常是由場地測量得來的經(jīng)驗(yàn)值。而XdB服從均值為0，方差為σdB的正態(tài)分布，但是在確定環(huán)境中的傳播路徑，則與確定的XdB相對應(yīng)。在實(shí)驗(yàn)環(huán)境中，用兩塊CC2430模塊多次測量不同距離下RSSI值，通過估計(jì)得到相應(yīng)的α與XdB。

表1 RSSI與距離的關(guān)系

實(shí)驗(yàn)中設(shè)定d0為1m，測得Pr(d0)=－56dBm。根據(jù)多元回歸分析可得α=2.8305，XdB=40.9388。再通過式(3)可實(shí)現(xiàn)RSSI到d的轉(zhuǎn)換。

在礦井人員跟蹤過程中，在初始時(shí)刻，為保證所有人員節(jié)點(diǎn)不丟失，根據(jù)實(shí)際要求，將接收到相同信標(biāo)且信號強(qiáng)度最強(qiáng)的節(jié)點(diǎn)組成一簇，此時(shí)該信標(biāo)節(jié)點(diǎn)相當(dāng)于一個(gè)臨時(shí)簇首，保證所有人員節(jié)點(diǎn)都可以與信標(biāo)節(jié)點(diǎn)進(jìn)行通信；當(dāng)然，還要在人員節(jié)點(diǎn)中選擇一個(gè)真正簇首節(jié)點(diǎn)。當(dāng)每個(gè)簇選出一個(gè)真正簇首時(shí)，可以用式(4)描述成簇關(guān)系矩陣：

在矩陣A中，行數(shù)表示人員節(jié)點(diǎn)個(gè)數(shù)；列數(shù)表示簇首節(jié)點(diǎn)個(gè)數(shù)。amn為0-1變量，amn=1表示第n（n= 1，2，…，N）個(gè)節(jié)點(diǎn)加入第m個(gè)簇中，即加入簇首節(jié)點(diǎn)m（m=1，2，…，M）所在的簇里，否則amn=0。這里能耗數(shù)學(xué)模型可以描述為式(5)：

其中，要求一個(gè)人員節(jié)點(diǎn)只能參加一個(gè)簇。即

式中，dmn表示第m個(gè)簇首節(jié)點(diǎn)與第n個(gè)人員節(jié)點(diǎn)之間的距離，為使得能耗指標(biāo)最小化，保證簇內(nèi)所有人員節(jié)點(diǎn)至所選簇首節(jié)點(diǎn)之間距離之和最小。

3.2 節(jié)點(diǎn)位置誤差考慮

對于k個(gè)固定信標(biāo)節(jié)點(diǎn)B1(x1,y1)，B2(x2,y2)，…，Bk(xk,yk)，人員節(jié)點(diǎn)M (x,y)至信標(biāo)節(jié)點(diǎn)的距離分別為d1，d2，…，dk。這里若只考慮兩個(gè)信標(biāo)節(jié)點(diǎn)B1，B2，假設(shè)兩節(jié)點(diǎn)的質(zhì)心在B12，位置為(x12,y12)，B12到B1和B2的距離分別為d1，d2。顯然可知存在(x12-x1)/d1= (x12-x2)/d2和(y12-y1)/d1=(y12-y2)/d2。得x12=(x1/d1+x2/d2) /(1/d1+ 1/ d2)，y12=(y1/d1+ y2/d2)/(1/d1+ 1/d2)。其中，1/di為權(quán)值，體現(xiàn)出距離人員節(jié)點(diǎn)距離近的信標(biāo)節(jié)點(diǎn)的權(quán)重大，其誤差比較小；而距離人員節(jié)點(diǎn)距離遠(yuǎn)的信標(biāo)節(jié)點(diǎn)的權(quán)重小，其誤差比較大，選擇加權(quán)因子能體現(xiàn)各個(gè)信標(biāo)節(jié)點(diǎn)對于人員節(jié)點(diǎn)位置的決定權(quán)的大小，其約束力符合加權(quán)質(zhì)心算法的要求。若把人員節(jié)點(diǎn)接收到RSSI值的范圍在－56dBm～－98dBm之間的信標(biāo)節(jié)點(diǎn)加入考慮，則得：

在井下信息化管理系統(tǒng)中，為了實(shí)時(shí)監(jiān)控井下人員，在大多數(shù)情況下，只要求人員節(jié)點(diǎn)每隔一個(gè)不長時(shí)間就與信標(biāo)節(jié)點(diǎn)傳遞一次確認(rèn)信息。保證人員節(jié)點(diǎn)在一段時(shí)間內(nèi)不丟失，而不需要知道確切位置，簇首在信標(biāo)節(jié)點(diǎn)傳輸信息時(shí)，把簇首節(jié)點(diǎn)的位置信息作為全簇節(jié)點(diǎn)的位置信息。也就是說，簇首只向信標(biāo)節(jié)點(diǎn)發(fā)送簇首的位置信息及全簇成員的ID號即可。但在一些需要知道某個(gè)簇成員相對確切位置時(shí)，節(jié)點(diǎn)相對于簇首的選擇就非常重要。

對于簇首的選擇，在得到節(jié)點(diǎn)位置后，根據(jù)文獻(xiàn)[7]對通信模型(1)、(2)的研究，單個(gè)簇與信標(biāo)節(jié)點(diǎn)通信總能量消耗最小的滿足條件，即信標(biāo)節(jié)點(diǎn)、簇首、簇的質(zhì)心在同一直線上。假設(shè)信標(biāo)節(jié)點(diǎn)位置為(0，0)，理想簇首位置為(xCH，yCH)，簇內(nèi)節(jié)點(diǎn)的位置為(xi，yi)，簇內(nèi)節(jié)點(diǎn)總數(shù)為n(包括簇首)，則有下列等式：

其中，ρ滿足下面關(guān)系

由式(8)、式(9)可以計(jì)算出理想簇首節(jié)點(diǎn)的位置(xCH，yCH)，那么，距離該點(diǎn)最近的節(jié)點(diǎn)應(yīng)該被選為簇首(xchm，ychm)(m=1,2, …,M)，m為第m個(gè)簇。

則人員節(jié)點(diǎn)位置誤差可以表示為：

ermn表示第n個(gè)人員節(jié)點(diǎn)與第m個(gè)簇首之間的位置誤差。由于一個(gè)人員節(jié)點(diǎn)只能參加一個(gè)簇。因此，基于人員節(jié)點(diǎn)位置誤差的數(shù)學(xué)模型設(shè)計(jì)為：

在完成簇首選擇后，根據(jù)粒子群算法綜合考慮通信能耗和節(jié)點(diǎn)位置誤差重新成簇。成簇目標(biāo)函數(shù)可以設(shè)計(jì)為式(11)，以保證節(jié)點(diǎn)通信能耗與位置誤差最小。

4 基于粒子群的分簇算法

粒子群優(yōu)化是通過個(gè)體之間的協(xié)作尋找最優(yōu)解的計(jì)算技術(shù)。算法數(shù)學(xué)描述為：假設(shè)在一個(gè)D維的目標(biāo)空間中，有N個(gè)代表潛在問題解的粒子組成一個(gè)群，其中第i個(gè)粒子表示為一個(gè)D維的向量，Xi= [xi1，xi2，…，xiD]，i=1，2，…，N；第i個(gè)粒子在D維搜索空間中的位置是Xi，飛行速度是Vi=[vi1，vi2，…，viD]；記Pi為第i個(gè)粒子迄今為止搜索到的個(gè)體最優(yōu)位置，Pi=[pi1，pi2，…，piD]；記Pg為粒子群迄今為止搜索到的全局最優(yōu)值，Pg=[pg1，pg2，…，pgD]；每次迭代中粒子按照式(12)、(13)更新速度與位置，則：

式中，i=1，2，…N；t為迭代次數(shù)；w為加權(quán)因子，取值在0.1～0.9之間，c1，c2為學(xué)習(xí)因子，分別調(diào)節(jié)向個(gè)體最好粒子和全局最好粒子方向飛行的最大步長；r1，r2是[0，1]之間的隨機(jī)數(shù)。粒子通過不斷學(xué)習(xí)更新，最后找的Pg就是全局最優(yōu)解。

然而無線傳感器網(wǎng)絡(luò)成簇問題是一個(gè)離散型問題，基本的PSO算法是針對連續(xù)問題設(shè)計(jì)的，要解決成簇問題，需要設(shè)計(jì)一個(gè)求解離散問題的PSO算法。具體算法設(shè)計(jì)如下。

4.1 粒子群初始化

4.1.1 位置的定義

粒子的位置X代表分簇方案，可以表示為X= (X1,X2,…,Xj,…,XM)，1≤j≤M；Xj=(xj1，xj2，…，xji，…，xjN)，1≤i≤N。在對粒子的位置進(jìn)行更新時(shí)，粒子的位置X為一個(gè)用元素為0或1的位置矩陣。

其中，M表示簇首個(gè)數(shù)；N表示人員節(jié)點(diǎn)個(gè)數(shù)；xji=1表示第i個(gè)人員節(jié)點(diǎn)加入第j個(gè)簇中；xji=0表示第i個(gè)人員節(jié)點(diǎn)個(gè)數(shù)不加入第j個(gè)簇中。

4.1.2 速度的定義

離散空間的速度不再是連續(xù)空間所說的速度，而是用來計(jì)算粒子的位置變化的概率值，粒子的速度用一個(gè)矩陣來表示：

式中，vji∈[-vmax，vmax]，j∈{1，2，…，m}，i∈{1，2，…，n}。由于速度是一個(gè)表示粒子的位置變化的概率值，它被限制在[0，1]之間。

4.2確定適應(yīng)值函數(shù)、個(gè)體極值和全局極值

在粒子群算法中，適應(yīng)值函數(shù)作為評價(jià)標(biāo)準(zhǔn)必須要能夠反映所要求解問題的目標(biāo)要求以及約束限制。這里將適應(yīng)值函數(shù)取為目標(biāo)函數(shù)。同時(shí)，根據(jù)無線傳感器網(wǎng)絡(luò)分簇的具體問題，進(jìn)行條件限制。其次，計(jì)算粒子所經(jīng)歷的最好位置pbi(t)，也就是粒子所經(jīng)歷過的具有最好適應(yīng)度的位置，由式(14)確定：

并計(jì)算群體中所有粒子經(jīng)歷過最好位置，即全局最好位置，由式(15)確定：

最后，依據(jù)粒子群公式對粒子的速度和位置進(jìn)行進(jìn)化。算法流程如圖1所示：

圖1 基于粒子群的分簇算法流程圖

4.3 算法仿真

仿真過程中，在120m×120m監(jiān)測區(qū)域內(nèi)，實(shí)驗(yàn)中將120個(gè)傳感器隨機(jī)分布于監(jiān)測區(qū)域內(nèi)模擬120個(gè)井下人員，另外在監(jiān)測區(qū)域上下兩側(cè)各安放4個(gè)信標(biāo)節(jié)點(diǎn)。設(shè)節(jié)點(diǎn)的探測半徑R=60m。實(shí)驗(yàn)中采用一組參數(shù)如下：εmp=0.0013pJ、εfs=10 pJ，根據(jù)計(jì)算可得簇首節(jié)點(diǎn)位置。采樣間隔為1秒；粒子群參數(shù)w=1，c1=c2=2，循環(huán)次數(shù)n=100；仿真結(jié)果如下圖所示：圖中各種相同形狀節(jié)點(diǎn)表示簇節(jié)點(diǎn)，簇首節(jié)點(diǎn)用五角星型表示，圖2為根據(jù)與信標(biāo)節(jié)點(diǎn)的位置，采用最近鄰的初始化分簇，從而形成8個(gè)簇。圖3為基于能耗和位置誤差考慮重新成簇的結(jié)果。

圖2 采用最近鄰的初始化分簇

圖3 基于能耗和位置 誤差考慮成簇

表2 不同分簇算法能量消耗與位置誤差結(jié)果比較

根據(jù)表2可知，在不同分簇算法的能量消耗中，采用最近鄰方式進(jìn)行初始化分簇時(shí)總能量消耗用距離表示為2082m，而基于能耗和位置誤差考慮的分簇的總能量消耗用距離表示為2128.2m；此能耗與采用最近鄰的初始化分簇相比，提高了2.22%。而各個(gè)簇的位置誤差如表2所示，其中，采用最近鄰方式進(jìn)行初始化分簇，此時(shí)總位置誤差為495.5887m，而基于能耗和位置誤差考慮的成簇的總位置誤差為458.3910m；在位置誤差上與采用最近鄰的初始化分簇相比，提高了8.11%。在煤礦井下非常密集的區(qū)域，尤其在上下班的高峰時(shí)段，基于能耗和位置誤差考慮的分簇算法，在定位精度上更占優(yōu)勢，更有利于煤礦井下人員跟蹤定位的要求。

5 結(jié)論

本文在無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量、存儲、帶寬資源受限的條件下，重點(diǎn)從通信能耗和位置誤差的角度，通過建立無線傳感器網(wǎng)絡(luò)分簇的綜合性能指標(biāo)，利用離散粒子群優(yōu)化算法，在實(shí)現(xiàn)有效的分簇同時(shí)，保證定位精度，達(dá)到煤礦井下通過傳感器節(jié)點(diǎn)之間的高效協(xié)同實(shí)現(xiàn)人員跟蹤的目的。

[1] 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.

[2] Tillett J, Rao R,Sahin F. Cluster-head Identification in Ad hoc Sensor Networks Using Particle Swarm Optimization[C]//Proc. Of IEEE International Conf. on Personal Wireless Communications. New Delhi， India: [s. n.]，2002.

[3] Latiff N M A, Tsimenidis C C, Sharif B S. Energy- aware Clustering for Wireless Sensor Networks Using Particle Swarm Optimization [C]//Proc. of the 18th International Symposium on Personal, Indoor and Mobile Radio Communications. Athens,Greece: [s. n.],2007.

[4] 孫勇,景博.分簇路由的無線傳感器網(wǎng)絡(luò)通信模式與能量有效性研究[J].電子與信息學(xué)報(bào),2007,29(9): 2262-2264.

[5] 張志東,孫雨耕.無線傳感器網(wǎng)絡(luò)能量模型[J].天津大學(xué)學(xué)報(bào)(自然科學(xué)版),2007,40(9):1029- 1034.

[6] Chahe Nerguizian, Charles L.Despins. “Radio- Channel Characterization of an Underground Mine at 2.4GHz”.IEEE Transactionsons on wireless communications,Vol4,No.5，SEPTEMBER 2005：2441-2453.

[7] Gurpreet Singh,GaoXi Xiao. Algorithms for energy-efficient clustering in wireless sensor networks[A]. Communication systems,2006 10th IEEE Singapore International Conference[C], Oct. 2006. 1-5.

徐小玲，女，1981年生，助教，碩士，主要從事無線傳感器網(wǎng)絡(luò)的研究。

劉美，女，1967年生，副教授，主要從事無線傳感器網(wǎng)絡(luò)的研究。

Study on Wireless Sensor Networks Clustering Algorithm for Coal Mine

Xu Xiaoling Liu Mei
(Computer and Electronic Information College, Guangdong University of Petrochemical Technology)

Adopting clustering to solve information conflict and meeting personnel node location accuracy and energy requirement in coal mine, this paper puts forward a kind of clustering method based on the comprehensive consideration of position error between nodes and cluster head and communication energy consumption using particle swarm optimization. Simulation results show that energy consumption of the clustering algorithm mentioned in this paper is increased by 2.22%, location error is reduced by 8.11% comparing with clustering algorithm. The algorithm achieves clustering, increases the system reliability and reduces the use of resources, meets the location accuracy requirement. In a crowded colliery, position error will be further improved.

Clustering; Position Error; Energy Consumption; Particle Swarm Optimization (PSO)