基于Q學(xué)習(xí)的多基站分簇拓?fù)淇刂扑惴?

閻新芳，馮　巖，王曉曉

（鄭州大學(xué)信息工程學(xué)院，鄭州450001）

基于Q學(xué)習(xí)的多基站分簇拓?fù)淇刂扑惴?

閻新芳*，馮巖，王曉曉

（鄭州大學(xué)信息工程學(xué)院，鄭州450001）

為了解決無線傳感器網(wǎng)絡(luò)中單基站附近出現(xiàn)的“能量空洞”和網(wǎng)絡(luò)時(shí)延過高等問題，引入多基站分簇拓?fù)淇刂扑惴?。算法根?jù)不同的場景來選擇基站數(shù)目，結(jié)合圖論和定向擴(kuò)散中梯度的思想對網(wǎng)絡(luò)進(jìn)行分簇并運(yùn)用Q學(xué)習(xí)算法對簇頭節(jié)點(diǎn)進(jìn)行周期性的學(xué)習(xí)訓(xùn)練，比較到達(dá)不同基站的不同路徑上的Q值進(jìn)行最優(yōu)路徑的選擇。通過仿真分析表明，該算法相對于單基站分簇算法可以有效延長網(wǎng)絡(luò)的生命周期。

無線傳感器網(wǎng)絡(luò)；分簇拓?fù)淇刂疲欢嗷?；Q學(xué)習(xí)

EEACC:6150Pdoi:10.3969/j.issn.1004-1699.2016.04.019

無線傳感器網(wǎng)絡(luò)［1］WSNs（Wireless Sensor Networks）是由大量的傳感器節(jié)點(diǎn)部署在監(jiān)測區(qū)域內(nèi)，通過節(jié)點(diǎn)間的相互通信所組成的多跳網(wǎng)絡(luò)來感知周圍環(huán)境的各種信息。由于無線傳感網(wǎng)網(wǎng)絡(luò)節(jié)點(diǎn)一次性播撒后，節(jié)點(diǎn)能量不可再生，因此降低網(wǎng)絡(luò)能量消耗、延長網(wǎng)絡(luò)生存期成為傳感網(wǎng)路由協(xié)議的首要設(shè)計(jì)目標(biāo)［2-3］。目前無線傳感器網(wǎng)絡(luò)核心的路由協(xié)議是分簇路由協(xié)議，而作為分簇路由協(xié)議的基礎(chǔ)的多級(jí)簇樹拓?fù)浣Y(jié)構(gòu)由于其能量高效和易于維護(hù)擴(kuò)展等特點(diǎn)被廣泛研究和應(yīng)用［4-7］。

其中基于梯度的分簇拓?fù)淇刂扑惴ǎ?］ETBG （Energy-Aware Topology ProtocolBased on Gradient）根據(jù)節(jié)點(diǎn)的通信半徑把網(wǎng)絡(luò)建成一個(gè)梯度場，對同梯度等級(jí)的節(jié)點(diǎn)進(jìn)行分簇。但該算法中節(jié)點(diǎn)競選簇頭的能力僅考慮能量和距離，生成簇樹的過程僅考慮單個(gè)簇頭節(jié)點(diǎn)的權(quán)值，沒有綜合考慮各方面的因素，未能找到最優(yōu)成樹路徑。而且在大規(guī)模的無線傳感器網(wǎng)絡(luò)中，單基站的ETBG算法由于靠近基站的節(jié)點(diǎn)承擔(dān)大量的數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)而造成過多的能量消耗，從而出現(xiàn)“能量空洞”的問題，嚴(yán)重的縮短了網(wǎng)絡(luò)的生命周期。而章等人提出了Q學(xué)習(xí)算法［8-11］的路由選擇機(jī)制，使數(shù)據(jù)始終沿著能量消耗代價(jià)最小的路徑進(jìn)行數(shù)據(jù)傳輸，在一定程度上避免了使用剩余能量少的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，但是該算法適用于平面路由，在大規(guī)模網(wǎng)絡(luò)中的分層路由中并不適用。

本文在ETBG算法和Q學(xué)習(xí)算法的基礎(chǔ)上，提出了基于Q學(xué)習(xí)的多基站分簇拓?fù)淇刂扑惴ǎ–TQL-MB）。該算法首先根據(jù)不同的場景確定相應(yīng)的基站數(shù)目，然后利用OWA算子多屬性決策的方法［12］將節(jié)點(diǎn)的能量、距離、節(jié)點(diǎn)間的相互作用等因素融合為一個(gè)屬性值來決定節(jié)點(diǎn)競選簇頭的能力，利用定向擴(kuò)散中的梯度思想將網(wǎng)絡(luò)劃分為一個(gè)不均勻的梯度圖并結(jié)合圖論中獨(dú)立集的概念對網(wǎng)絡(luò)進(jìn)行分簇，最后運(yùn)用Q學(xué)習(xí)算法對簇頭節(jié)點(diǎn)進(jìn)行周期性的學(xué)習(xí)訓(xùn)練，比較到達(dá)不同基站的不同路徑上的Q值，選擇整條路徑上Q值最大的路徑為最優(yōu)路徑。

1　基于Q學(xué)習(xí)的單基站分簇算法

1.1Q學(xué)習(xí)

Q-learning是強(qiáng)化學(xué)習(xí)的一種常用算法。強(qiáng)化學(xué)習(xí)系統(tǒng)接受環(huán)境狀態(tài)的輸入s，根據(jù)內(nèi)部的推理機(jī)制，系統(tǒng)輸出相應(yīng)的行為動(dòng)作a。環(huán)境在系統(tǒng)動(dòng)作作用a下，變遷到新的狀態(tài)s′。系統(tǒng)接受環(huán)境新狀態(tài)的輸入，同時(shí)得到環(huán)境對于系統(tǒng)的瞬時(shí)獎(jiǎng)懲反饋r。對于強(qiáng)化學(xué)習(xí)系統(tǒng)來講，其目標(biāo)是學(xué)習(xí)一個(gè)行為策略π:S→A，使系統(tǒng)選擇的動(dòng)作能夠獲得環(huán)境獎(jiǎng)賞的累計(jì)值最大。

Q值的更新公式如式（1）所示:

式中:γ為折扣因子；r（i）是回報(bào)函數(shù)［5］，具體定義如下:

式中:node（i）.w是收到學(xué)習(xí)消息的任意節(jié)點(diǎn)i的權(quán)值；node（j）.w是指發(fā)送學(xué)習(xí)消息的節(jié)點(diǎn)j的權(quán)值；node（j）.cost（i）是指發(fā)送學(xué)習(xí)消息的節(jié)點(diǎn)j到收到消息的節(jié)點(diǎn)i的路徑能量消耗。這樣就可以把節(jié)點(diǎn)的能量、距離、鄰居節(jié)點(diǎn)數(shù)目以及兩節(jié)點(diǎn)間的鏈路通信耗能全部考慮進(jìn)去，更能反映出網(wǎng)絡(luò)的節(jié)點(diǎn)動(dòng)態(tài)，回報(bào)函數(shù)越大，說明該節(jié)點(diǎn)路由的“趨勢”就越強(qiáng)。在該算法中假定γ=1以加快學(xué)習(xí)速度。系統(tǒng)產(chǎn)生該動(dòng)作的趨勢主要決定于環(huán)境的獎(jiǎng)賞值，獎(jiǎng)賞值如果為正則趨勢會(huì)越來越強(qiáng)。換言之，系統(tǒng)要使得（1）式最大化。

1.2單基站算法性能分析

采用文獻(xiàn)［5］中的算法進(jìn)行仿真。為了對Q學(xué)習(xí)算法的性能進(jìn)行評(píng)估，本文首先對該算法在單基站的情況下和ETBG算法進(jìn)行比較。定義從算法開始運(yùn)行到第一個(gè)節(jié)點(diǎn)死亡之間的時(shí)間為網(wǎng)絡(luò)生存期，網(wǎng)絡(luò)生存期同樣可以以數(shù)據(jù)采集總輪數(shù)表示。仿真的參數(shù)設(shè)置為的范圍內(nèi)200個(gè)節(jié)點(diǎn)，在二十個(gè)不同的場景下進(jìn)行仿真，然后取其平均值，可得不同通信半徑下兩種算法的生存期對比圖，如圖1所示。

圖1　不同通信半徑下的生存期對比圖

可以看到，當(dāng)R大于40時(shí)，在ETBG算法中生命周期會(huì)出現(xiàn)明顯的下降，這是因?yàn)殡S著R增大，梯度上限增大，鄰居節(jié)點(diǎn)數(shù)目增多，使得簇的個(gè)數(shù)減少，簇頭之間距離增大，導(dǎo)致簇頭能量消耗更大，數(shù)據(jù)傳輸?shù)妮啍?shù)就會(huì)明顯減少。而引入Q學(xué)習(xí)算法之后，對每個(gè)節(jié)點(diǎn)進(jìn)行周期性的學(xué)習(xí)訓(xùn)練，根據(jù)每條路徑上的Q值選擇最佳的路徑，就解決了ETBG算法生成簇樹過程中未能找到最佳路徑造成的能量在傳輸過程損耗過大的問題，故其生命周期下降速度較ETBG算法更為平緩，R越大CTQL算法的優(yōu)勢就體現(xiàn)的越明顯。

CTQL算法仍還存在一些問題，如簇樹過高會(huì)造成網(wǎng)絡(luò)時(shí)延更長，網(wǎng)絡(luò)能量不均衡會(huì)導(dǎo)致部分節(jié)點(diǎn)過早死亡等，在大規(guī)模的分層路由中并不適用。本文在CTQL算法的基礎(chǔ)上，提出基于Q學(xué)習(xí)的多基站分簇拓?fù)淇刂疲–TQL-MB）算法。

2　基于Q學(xué)習(xí)的多基站分簇算法

多基站的策略將使簇樹更矮，網(wǎng)絡(luò)的魯棒性和擴(kuò)展性更強(qiáng)，能有效解決CTQL算法中時(shí)延過高、能量不均衡的問題，使得生命周期得到有效延長?；镜哪芰咳菀籽a(bǔ)充，多個(gè)基站不僅可以根據(jù)不同的場景分布在不同位置，也可以在必要的情況進(jìn)行移動(dòng)，以照顧能量損耗大的節(jié)點(diǎn)，同時(shí)多個(gè)基站之間也可以進(jìn)行直接的信息交互。

基站位置選擇的原則是盡量以最小的梯度覆蓋整個(gè)網(wǎng)絡(luò)，從而減少由于遠(yuǎn)距離傳輸時(shí)延過大，以及部分節(jié)點(diǎn)轉(zhuǎn)發(fā)過多引起耗能過大導(dǎo)致過早死亡的問題。

算法總體包括以下幾個(gè)過程:構(gòu)建唯一梯度值、簇的確定、建立簇樹。

2.1構(gòu)建唯一梯度值

假設(shè)網(wǎng)絡(luò)中有n（n=1，2，3，…，n為整數(shù)）個(gè)基站，分別為BS1，BS2，…，BSn。首先以基站BSn（n= 1，2，3，…）為中心，以節(jié)點(diǎn)的通信半徑mR（m=1，2，3，…，D/m，D/m為整數(shù)）為半徑發(fā)送梯度劃分消息。任意節(jié)點(diǎn)的初始唯一梯度值L=0。節(jié)點(diǎn)在收到第一個(gè)梯度劃分消息后將其置為自己的唯一梯度值，當(dāng)節(jié)點(diǎn)繼續(xù)收到其他的梯度化分消息時(shí)，將所收到的梯度值與當(dāng)前的梯度值比較，并按以下規(guī)則處理:①如果當(dāng)前梯度值與所收到的梯度值不同，則將唯一梯度值更新為小的梯度值。②如果當(dāng)前梯度值與所收到的梯度值相同，則計(jì)算該節(jié)點(diǎn)到這兩個(gè)梯度值所對應(yīng)的基站的距離d to BSk（k∈n），然后選擇距離基站距離最小的所對應(yīng)的梯度值作為該節(jié)點(diǎn)的唯一梯度值。

2.2簇的確定

在確定各個(gè)節(jié)點(diǎn)的唯一梯度值后節(jié)點(diǎn)間進(jìn)行第一次信息交互，以R為功率半徑向其鄰居節(jié)點(diǎn)廣播當(dāng)前狀態(tài)消息，其中包括節(jié)點(diǎn)ID、當(dāng)前剩余能量、唯一梯度值L、狀態(tài)status。每個(gè)節(jié)點(diǎn)將得到的鄰居信息保存在自己的鄰居集中，包括鄰居節(jié)點(diǎn)的狀態(tài)信息并計(jì)算本節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)目。節(jié)點(diǎn)根據(jù)自己鄰居集中的信息，運(yùn)用OWA多屬性決策方法［5］確定自己的權(quán)值。

各個(gè)節(jié)點(diǎn)將自己鄰居中唯一梯度值相同節(jié)點(diǎn)構(gòu)成同梯度等級(jí)集合，然后利用圖論中獨(dú)立集的概念將同一梯度等級(jí)內(nèi)的節(jié)點(diǎn)進(jìn)行比較，如果其權(quán)值最大，則宣布自己成為簇頭節(jié)點(diǎn)，具體方法見文獻(xiàn)［5］。

簇頭確定后，網(wǎng)絡(luò)中的非簇頭節(jié)點(diǎn)按照ETBG算法［4］的策略加入不同的簇，從而完成網(wǎng)絡(luò)的分簇。

2.3建立簇樹

分簇階段完成后，基站BSn（n=1，2，3，…）周期性地向其鄰居節(jié)點(diǎn)發(fā)送學(xué)習(xí)消息learnBSn（n=1，2，3，…），啟動(dòng)路徑建立。學(xué)習(xí)消息中記錄了節(jié)點(diǎn)的Q值、回報(bào)函數(shù)以及節(jié)點(diǎn)的能量信息和權(quán)值，各個(gè)節(jié)點(diǎn)的初始Q值為0。鄰居節(jié)點(diǎn)繼續(xù)向下一梯度的鄰居簇頭節(jié)點(diǎn)發(fā)送學(xué)習(xí)消息直到網(wǎng)絡(luò)中所有簇頭節(jié)點(diǎn)均進(jìn)行學(xué)習(xí)訓(xùn)練。任意節(jié)點(diǎn)如果首次收到學(xué)習(xí)消息則建立Q表儲(chǔ)存學(xué)習(xí)消息中的信息，而收到學(xué)習(xí)消息的節(jié)點(diǎn)只有當(dāng)?shù)较鄳?yīng)基站的距離大于發(fā)送消息的節(jié)點(diǎn)時(shí)才進(jìn)行學(xué)習(xí)訓(xùn)練并按照規(guī)則1～規(guī)則4處理，否則放棄學(xué)習(xí)，避免形成回路。

規(guī)則1如果簇頭節(jié)點(diǎn)收到來自鄰居的簇成員節(jié)點(diǎn)的學(xué)習(xí)消息，根據(jù)式（2）來計(jì)算節(jié)點(diǎn)的回報(bào)函數(shù)，再根據(jù)式（1）更新節(jié)點(diǎn)Q值，并儲(chǔ)存在自己的Q表中，繼續(xù)轉(zhuǎn)發(fā)消息，等待所有基站的學(xué)習(xí)任務(wù)進(jìn)行完后執(zhí)行規(guī)則4。

規(guī)則2如果簇成員節(jié)點(diǎn)收到簇頭節(jié)點(diǎn)的學(xué)習(xí)消息，根據(jù)式（2）計(jì)算回報(bào)函數(shù)，再根據(jù)式（1）來更新節(jié)點(diǎn)的Q值，并儲(chǔ)存在自己的Q表中，繼續(xù)向下在兩跳范圍內(nèi)轉(zhuǎn)發(fā)該學(xué)習(xí)消息，等待所有基站的學(xué)習(xí)任務(wù)都進(jìn)行完則進(jìn)入規(guī)則4。

規(guī)則3如果簇成員節(jié)點(diǎn)收到非簇頭節(jié)點(diǎn)的學(xué)習(xí)消息，根據(jù)式（2）計(jì)算回報(bào)函數(shù)，再根據(jù)式（1）更新Q值，并儲(chǔ)存并繼續(xù)向下一跳范圍內(nèi)轉(zhuǎn)發(fā)該學(xué)習(xí)消息，等待所有基站的學(xué)習(xí)任務(wù)都進(jìn)行完則進(jìn)入規(guī)則4。

規(guī)則4在各個(gè)基站到該節(jié)點(diǎn)的所有路徑的Q值逐步迭代出來后，選出該節(jié)點(diǎn)Q表中BSnQ（n=1，2，3，…）的最大值所對應(yīng)的節(jié)點(diǎn)作為自己的父親節(jié)點(diǎn)，如果該父親節(jié)點(diǎn)為簇成員節(jié)點(diǎn)則其該簇成員節(jié)點(diǎn)聲明自己為網(wǎng)關(guān)節(jié)點(diǎn)。

整個(gè)網(wǎng)絡(luò)的簇頭節(jié)點(diǎn)都遍歷后，算法結(jié)束。每個(gè)節(jié)點(diǎn)都建立到達(dá)基站的最優(yōu)的傳輸路徑。在該算法中，多基站解決了“能量空洞”和時(shí)延問題，生成簇樹的過程中節(jié)點(diǎn)間通信的每一步選擇都綜合考慮了節(jié)點(diǎn)的通信能力、跳數(shù)、剩余能量，從中選擇到達(dá)各個(gè)基站最能均衡能量、節(jié)省能量、延長節(jié)點(diǎn)壽命的路徑選擇路由，因而針對大規(guī)模的無線傳感器網(wǎng)絡(luò)具有一定的實(shí)用價(jià)值和現(xiàn)實(shí)意義。

2.4特例分析

特例:假設(shè)在一個(gè)的區(qū)域內(nèi)隨機(jī)拋灑50個(gè)傳感器節(jié)點(diǎn)，設(shè)定兩個(gè)基站位置分別為（100，0），（100，200）。采用文獻(xiàn)［4］所示能量模型，各個(gè)參數(shù)的設(shè)定如下:網(wǎng)絡(luò)中所有節(jié)點(diǎn)的初始能量為0.5 J，通信半徑為50 m，每接收一位消息耗能50 nJ，每發(fā)送一位消息傳輸1 m距離耗能0.1 nJ。消息包固定長度為128 bit，基站初始Q值為50。假定節(jié)點(diǎn)位置不變且相互間通信正常，不考慮重傳問題并且節(jié)點(diǎn)間不存在單向鏈路。如圖2所示，為運(yùn)行該算法后的簇樹圖，其中“方塊”代表簇頭，“菱形”代表網(wǎng)關(guān)，其余為普通節(jié)點(diǎn)。

圖2中可以看出基站BS1，BS2均發(fā)送一個(gè)學(xué)習(xí)消息，其鄰居節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)。其中基站BS2的鄰居中有簇頭節(jié)點(diǎn)37，該節(jié)點(diǎn)在進(jìn)行學(xué)習(xí)訓(xùn)練后繼續(xù)想起鄰居簇頭轉(zhuǎn)發(fā)學(xué)習(xí)消息，其鄰居節(jié)點(diǎn)中的簇頭節(jié)點(diǎn)按照規(guī)則①進(jìn)行更新，并繼續(xù)向下轉(zhuǎn)發(fā)，非簇頭節(jié)點(diǎn)按照規(guī)則②、規(guī)則③、規(guī)則④進(jìn)行更新；基站BS1的鄰居節(jié)點(diǎn)中無簇頭節(jié)點(diǎn)在，則節(jié)點(diǎn)22作為網(wǎng)關(guān)節(jié)點(diǎn)繼續(xù)轉(zhuǎn)發(fā)學(xué)習(xí)消息，如果作為網(wǎng)關(guān)節(jié)點(diǎn)連接簇樹，則退出其所屬的簇，直接與基站通信。

圖2　算法運(yùn)行后生成的簇樹圖

例如簇頭節(jié)點(diǎn)17的可能路徑及各個(gè)路徑的Q值如表1所示:

表1　節(jié)點(diǎn)17的Q表

可以看到，其中BS1-22-1-17這條路徑上的Q值最大，則選擇該路徑傳輸數(shù)據(jù)。

3　算法性能分析

對算法的性能進(jìn)行評(píng)估，把該算法和單基站的Q學(xué)習(xí)算法進(jìn)行比較，查看基站個(gè)數(shù)對網(wǎng)絡(luò)生命周期的影響。在仿真的參數(shù)設(shè)置為200 m×200 m的區(qū)域里隨機(jī)拋灑200個(gè)節(jié)點(diǎn)，設(shè)定兩基站時(shí)基站的位置分別是（100，0）（100，200），三基站時(shí)基站的位置分別是（0，0）（100，200）（200，0），檢測整個(gè)網(wǎng)絡(luò)的生命周期在二十次不同的場景下進(jìn)行仿真，然后取其平均值，可得不同通信半徑下不同基站個(gè)數(shù)下網(wǎng)絡(luò)生命周期的對比圖的如圖3所示。

圖3　不同基站個(gè)數(shù)在不同通信半徑下的生存期對比圖

從圖3可以看到，當(dāng)R=30時(shí)單基站的生命周期最短，兩基站的生命周期最長；當(dāng)R=50時(shí)雙基站和三基站情況下生命周期無明顯差別，但均比單基站的生命周期長。

理論上基站越多，網(wǎng)絡(luò)能量消耗越小。而由于本論文中仿真參數(shù)選擇的區(qū)域較小，三個(gè)基站與兩個(gè)基站相比，每個(gè)節(jié)點(diǎn)的學(xué)習(xí)任務(wù)更重，計(jì)算所消耗的能量更多，反而使生命周期減小。

總體上，隨著節(jié)點(diǎn)通信半徑的增加，在網(wǎng)絡(luò)的生存周期內(nèi)，數(shù)據(jù)傳輸?shù)妮啍?shù)在減小。這是因?yàn)殡S著R增大，梯度的上限增大，鄰居節(jié)點(diǎn)的數(shù)目就會(huì)增多節(jié)點(diǎn)間交互信息的能耗必然增加，且形成簇?cái)?shù)也會(huì)減少，同時(shí)簇?cái)?shù)減少還會(huì)造成簇成員數(shù)增加，簇頭能量消耗更大。簇頭之間距離增大導(dǎo)致信息交互所消耗的能量也越大，從而數(shù)據(jù)傳輸?shù)妮啍?shù)就會(huì)減少。

4　結(jié)論

針對單基站CTQL分簇拓?fù)淇刂扑惴ㄖ写嬖诘摹澳芰靠斩础币约熬W(wǎng)絡(luò)能量不均衡，網(wǎng)絡(luò)時(shí)延過高，生成簇樹的路徑不優(yōu)化的問題，提出了CTQL-MB算法。該算法引入了多個(gè)基站，在生成簇樹的過程中通過在簇頭間運(yùn)行Q-learning算法，綜合考慮節(jié)點(diǎn)的剩余能量、路徑通信消耗等因素尋找簇頭節(jié)點(diǎn)到達(dá)哪個(gè)基站才是最優(yōu)路徑，優(yōu)化了數(shù)據(jù)傳輸時(shí)的路徑選擇，節(jié)省了整個(gè)網(wǎng)絡(luò)的能量消耗。仿真結(jié)果表明，CTQL-MB算法相比較CTQL算法有效地延長了網(wǎng)絡(luò)的生命周期。

［1］ Tubaishat M，Madria S.Sensor Networks:An Overview［J］.IEEE Potentials，2003，22（2）:20-23.

［2］ Heinzelman W B，Chandrakasan A P，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Network［J］.Wireless Communications，2002，1（4）:660-670.

［3］ Manjeshwar A，Agrawal D P.TEEN:A Routing Qrotocol for Enhanced Efficiency in Wireless Sensor Networks［C］//IEEE International Prroceedings of 15th Parallel and Distributed Processing Symposium.IEEE Conference Proceedings，2001:2009-2015.

［4］ 閻新芳，朱玉芳，安娜.無線傳感器網(wǎng)絡(luò)中一種分級(jí)簇的優(yōu)化算法［J］.傳感技術(shù)學(xué)報(bào)，2009，22（3）:401-406.

［5］ 閻新芳，王曉曉，馮巖.基于Q學(xué)習(xí)的無線傳感網(wǎng)分簇拓?fù)淇刂扑惴ǎ跩］.鄭州大學(xué)學(xué)報(bào)，2015，36（2）:85-88.

［6］ Yan Xinfang，Zhang Yongkun，Tang Hailing.An ETBG Optimization Algorithm Based on Analytic Hierarchy Process in WSN［C］// Proceedings of ICCSEE'2013:2013.3 The 2nd International Conference on Computer Science and Electronics Engineering.China，2013:1687-1690.

［7］ 何延杰，李臘元，邢明彥.WSN中一種能量均衡的分簇路由協(xié)議的設(shè)計(jì)［J］.傳感技術(shù)學(xué)報(bào)，2009，22（10）:1510-1514.

［8］ Stephen S，Thiel M.A Q-Learning Strategy for LTE Mobility Load Balancing［C］//Andreas Personal Indoor and Mobile Radio Communications（PIMRC）IEEE24thInternationalSymposium 2013:2154-2158.

［9］ Xie Ya，Huang Zhonghua.Study on Statistics Based Q-Learning Algorithm for Multi-Agent System［C］//Intelligent Systems Design and Engineering Applications，2013 Fourth International Conference on DOI:10.1109/ISDEA.2013.541 Publication Year:2013: 595-600.

［10］章韻，王靜玉，陳志.基于Q學(xué)習(xí)的無線傳感器網(wǎng)絡(luò)自組織方法研究［J］.傳感器學(xué)報(bào)，2012，23（11）:1623-1626.

［11］蘇彬庭，方禾，許力.基于Q-Learning的無線傳感器網(wǎng)絡(luò)生命周期平衡路由［J］.信息網(wǎng)絡(luò)安全，2015（4）:74-77.

［12］吳堅(jiān).基于OWA算子理論的混合型多屬性群決策研究［D］.合肥:合肥工業(yè)大學(xué)，2008.

閻新芳（1958-），女，教授，博士，碩士生導(dǎo)師，主要從事無線傳感網(wǎng)等方面研究，iexfyan@zzu.edu.cn；

馮巖（1990-），男，碩士生，主要研究無線傳感網(wǎng)絡(luò)路由算法，120628416@ qq.com。

Clustering Topology Control for Multiple Base Stations in WSNs with Q-Learning*

YAN Xinfang*，F(xiàn)ENG Yan，WANG Xiaoxiao
（School of Information Engineering，Zhengzhou University，Zhengzhou 450001，China）

This paper presents a multiple base stations clustering topology control algorithm to solve the issue of“energy hole”and high network delay near a single base station in wireless sensor networks（WSNs）.The number of base stations is determined according to different scenarios.Our algorithm uses a method of graph theory and the gradient of directional diffusion to clustering.To achieve the clustering topology control，our method exploits Q-learning method，incrementally learning at each node's sufficient network knowledge to choose the best path to base stations. Evaluation of the resulting our algorithm demonstrates its ability to significantly increase the lifetime of network in comparison to the single base station clustering algorithm.

wireless sensor networks；clustering topology control；multiple base stations；Q-learning

TP393

A

1004-1699（2016）04-0578-05

項(xiàng)目來源:河南省科技廳基礎(chǔ)與前沿研究計(jì)劃項(xiàng)目（152300410023）

2015-10-18修改日期:2016-01-18