礦井下無線傳感器網絡分簇算法研究

徐小玲 劉美

（廣東石油化工學院計算機與電子信息學院）

礦井下無線傳感器網絡分簇算法研究

徐小玲 劉美

（廣東石油化工學院計算機與電子信息學院）

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

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

1引言

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

2 相關工作

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

本文根據井下分簇的要求，把節點與簇首的位置誤差和通信能耗作為優化目標函數的主要指標建立傳感器節點成簇的數學模型，通過采用最近鄰進行初始成簇并采用粒子群優化算法實現節點重新組簇，盡可能快地得到最優成簇結果。

3 節點成簇目標函數設計

3.1 節點成簇能耗考慮

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

節點接收lbit長度數據所消耗能量為：

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

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

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

表1 RSSI與距離的關系

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

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

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

其中，要求一個人員節點只能參加一個簇。即

式中，dmn表示第m個簇首節點與第n個人員節點之間的距離，為使得能耗指標最小化，保證簇內所有人員節點至所選簇首節點之間距離之和最小。

3.2 節點位置誤差考慮

對于k個固定信標節點B1(x1,y1)，B2(x2,y2)，…，Bk(xk,yk)，人員節點M (x,y)至信標節點的距離分別為d1，d2，…，dk。這里若只考慮兩個信標節點B1，B2，假設兩節點的質心在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為權值，體現出距離人員節點距離近的信標節點的權重大，其誤差比較小；而距離人員節點距離遠的信標節點的權重小，其誤差比較大，選擇加權因子能體現各個信標節點對于人員節點位置的決定權的大小，其約束力符合加權質心算法的要求。若把人員節點接收到RSSI值的范圍在－56dBm～－98dBm之間的信標節點加入考慮，則得：

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

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

其中，ρ滿足下面關系

由式(8)、式(9)可以計算出理想簇首節點的位置(xCH，yCH)，那么，距離該點最近的節點應該被選為簇首(xchm，ychm)(m=1,2, …,M)，m為第m個簇。

則人員節點位置誤差可以表示為：

ermn表示第n個人員節點與第m個簇首之間的位置誤差。由于一個人員節點只能參加一個簇。因此，基于人員節點位置誤差的數學模型設計為：

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

4 基于粒子群的分簇算法

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

式中，i=1，2，…N；t為迭代次數；w為加權因子，取值在0.1～0.9之間，c1，c2為學習因子，分別調節向個體最好粒子和全局最好粒子方向飛行的最大步長；r1，r2是[0，1]之間的隨機數。粒子通過不斷學習更新，最后找的Pg就是全局最優解。

然而無線傳感器網絡成簇問題是一個離散型問題，基本的PSO算法是針對連續問題設計的，要解決成簇問題，需要設計一個求解離散問題的PSO算法。具體算法設計如下。

4.1 粒子群初始化

4.1.1 位置的定義

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

其中，M表示簇首個數；N表示人員節點個數；xji=1表示第i個人員節點加入第j個簇中；xji=0表示第i個人員節點個數不加入第j個簇中。

4.1.2 速度的定義

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

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

4.2確定適應值函數、個體極值和全局極值

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

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

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

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

4.3 算法仿真

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

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

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

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

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

5 結論

本文在無線傳感器網絡節點能量、存儲、帶寬資源受限的條件下，重點從通信能耗和位置誤差的角度，通過建立無線傳感器網絡分簇的綜合性能指標，利用離散粒子群優化算法，在實現有效的分簇同時，保證定位精度，達到煤礦井下通過傳感器節點之間的高效協同實現人員跟蹤的目的。

[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] 孫勇,景博.分簇路由的無線傳感器網絡通信模式與能量有效性研究[J].電子與信息學報,2007,29(9): 2262-2264.

[5] 張志東,孫雨耕.無線傳感器網絡能量模型[J].天津大學學報(自然科學版),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年生，助教，碩士，主要從事無線傳感器網絡的研究。

劉美，女，1967年生，副教授，主要從事無線傳感器網絡的研究。

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)